Robot tới bàn trả sách qua một lưới có ô chắn.

Mỗi lần thử một hành động, rồi thấy vị trí mới và phần thưởng.

Thưởng chỉ có ở đích: một bước còn xa đích có ích không?

Biết bản đồ: BFS là đủ.

Chưa biết kết quả hành động: học từ trải nghiệm.

$S_t$: trạng thái trước hành động.

$A_t$: hành động.

$R_{t+1}$, $S_{t+1}$: kết quả sau hành động.

Tính Markov: biết $S_t, A_t$ là đủ để dự đoán bước kế, không cần lịch sử.

Pin ảnh hưởng di chuyển: thêm mức pin vào trạng thái.

Mỗi bước lùi thêm: $V_d=-1+0.9V_{d-1}$, với $V_1=10$.

print(f"Value iteration tại S: {V[start]:.3f}")
print(f"Giá trị terminal: {V[goal]:.3f}")

Kết quảValue iteration tại S: 3.122
Giá trị terminal: 0.000

Dùng mô hình đã biết: planning, chưa phải học.

Một vòng xét mọi $s$, mọi $a$, mọi $s'$:

• bảng $p$ đầy đủ: $O(|\mathcal S|^2|\mathcal A|)$;
• lưới tất định: $O(|\mathcal S||\mathcal A|)$.

Đồ thị có vòng nên không có thứ tự tính một lần là xong.

Bắt đầu từ $V=0$, mỗi vòng đưa thông tin từ đích lùi thêm một bước.

Bảng (11, 4) lưu giá trị mỗi cặp $(s,a)$.

Target chưa terminal:

$Q=2$, $r=-1$, $\max Q(s',\cdot)=5$.

$\gamma=0.9$, $\alpha=0.2$:

• Target bằng $3.5$.
• TD error bằng $1.5$.
• Q mới bằng $2.3$.

def td_target(reward, next_values, terminated):
    if terminated:
        return reward
    return reward + gamma * np.max(next_values)

Thưởng terminal 10, target bằng 10.

Giới hạn thu mẫu bên ngoài MDP vẫn cho phép bootstrap.

Trong Gymnasium: đọc riêng terminated và truncated.

if rng.random() < epsilon:
    action = int(rng.integers(4))
else:
    best = np.flatnonzero(
        Q[state] == Q[state].max())
    action = int(rng.choice(best))

Exploration thử hành động để biết thêm về environment.

Search mở rộng trạng thái bằng quy tắc đã biết.

Chọn ngẫu nhiên mà không cập nhật Q hoặc policy chưa tạo ra phần học.

Episode đầu, $\alpha=1$, $Q=0$: chỉ cặp cuối nhận target có thưởng 10.

Các cặp trước đã cập nhật khi phía sau còn bằng 0.

Mỗi lần đi lại cùng đường, thông tin lùi thêm một bước.

Experience replay: lưu transition, cập nhật lại nhiều lần.

print("Hành động:", " ".join(actions_taken))
print(
    f"Số bước: {len(actions_taken)}, "
    f"return: {discounted:.3f}"
)

Kết quảHành động: R R U U R
Số bước: 5, return: 3.122

Evaluation tắt exploration và không cập nhật Q.

Đường ngắn nhất dài 5 bước: tối ưu từ S.

Kiểm cả policy: chạy từ mọi ô, so với $V^*$.

$\theta=0$ cho $p=0.5$ và $J'=0.5$.

Gradient ascent với $\eta=0.1$:

Kết quảMột bước exact gradient: theta=0.0500, p=0.5125

Tăng thưởng: dấu cộng. Giảm loss: dấu trừ.

Mẫu gradient:

Với Bernoulli, $\nabla_\theta\log\pi(A)=A-p$.

reward = 3.0 if action else 1.0
sample_gradient = (
    (reward - 2.0) * (action - probability)
)
theta_policy += 0.05 * sample_gradient

Baseline $b=2$ không phụ thuộc vào hành động được chọn.

Kết quảPolicy sau 400 mẫu: p(phải)=0.9641, E[R]=2.9282

Kỳ vọng tính bằng công thức $1+2p$ của bandit.

Kỳ vọng $2.9282$ chưa bằng mức tối đa 3 vì policy vẫn còn ngẫu nhiên.

Gradient $2p(1-p)$ nhỏ dần khi $p$ gần 1: càng chắc chắn càng học chậm.