Đăng nhập

Chương 9·Bài 9.1

Reinforcement learning

Một robot đi trên hành lang có ba vị trí: 0 là cửa, 1 là giữa đường, 2 là bàn trả sách. Môi trường đủ nhỏ để ta tính tay đáp án bằng phương trình Bellman, rồi mới kiểm một agent tự học từ trải nghiệm.

Ví dụ 1: Phần thưởng ở bước cuối vẫn được tính vào return

Robot có hai hành động: đứng chờ, hoặc đi sang phải một ô. Đứng chờ bị trừ 1 điểm. Đi sang một ô chưa phải đích cũng bị trừ 1 điểm. Bước vào ô 2 thì được 5 điểm, và lượt chơi kết thúc. Ô đích là trạng thái kết thúc, nên không được gọi thêm bước nào từ đó.

Python
import numpy as np

def step(state, action):
    assert state in [0, 1] and action in [0, 1]
    following = state if action == 0 else state + 1
    terminal = following == 2
    return following, 5.0 if terminal else -1.0, terminal

state, rewards = 0, []
for action in [1, 1]:
    state, reward, terminal = step(state, action)
    rewards.append(reward)
    if terminal:
        break
assert rewards == [-1.0, 5.0] and state == 2
for gamma in [1.0, 0.9, 0.5]:
    value = sum(gamma ** t * reward for t, reward in enumerate(rewards))
    print("gamma:", gamma, "return:", f"{value:.2f}")
print("chờ ở ô 0:", step(0, 0))

Đi thẳng từ cửa tới bàn mất hai bước, nhận chuỗi thưởng −1 rồi 5. Return là tổng thưởng, trong đó thưởng ở bước t được nhân với γt\gamma^t. Với γ=1\gamma=1, return là 4. Với γ=0.9\gamma=0.9, return là −1+0.9⋅5=3.5-1+0.9\cdot5=3.5. Gamma càng nhỏ, phần thưởng ở xa càng bị coi nhẹ.

Trạng thái kết thúc chỉ cắt bỏ những gì xảy ra sau khi vào đích. Nó không xóa 5 điểm của chính bước vào đích. Dòng cuối cho thấy đứng chờ ở cửa thì vẫn ở cửa, vẫn bị trừ điểm, và lượt chơi chưa kết thúc.

Ví dụ 2: Tính Bellman, và kiểm target có bị lẫn giá trị ô đích không

Khi đã biết luật của hành lang, ta có thể xét cả hai hành động ở mỗi ô và chọn cái tốt hơn. Đó là value iteration. Ô 1 có giá trị 5, vì chỉ cần một bước là tới đích. Ô 0 có giá trị −1+0.9⋅5=3.5-1+0.9\cdot5=3.5. Sau đó ta viết hàm tính target cho Q-learning, và cố tình đặt giá trị Q ở ô đích là 999, để xem code có lỡ cộng giá trị tương lai sau khi đã kết thúc hay không.

Python
import numpy as np

gamma = 0.9
def step(state, action):
    assert state < 2
    following = state if action == 0 else state + 1
    terminal = following == 2
    return following, 5.0 if terminal else -1.0, terminal

V = np.zeros(3)
for _ in range(100):
    previous = V.copy()
    for state in [0, 1]:
        options = []
        for action in [0, 1]:
            following, reward, terminal = step(state, action)
            options.append(reward + gamma * (0 if terminal else previous[following]))
        V[state] = max(options)
    if np.max(np.abs(V - previous)) < 1e-12:
        break
assert np.allclose(V, [3.5, 5.0, 0.0])

def target(reward, following_values, terminal):
    return reward if terminal else reward + gamma * np.max(following_values)

print("V*:", V.tolist())
print("target terminal:", target(5.0, np.array([999.0, 999.0]), True))
print("target chưa terminal:", target(-1.0, np.array([2.0, 5.0]), False))
assert target(5.0, np.full(2, 999.0), True) == 5.0

Value iteration hội tụ về [3.5, 5, 0], khớp tính tay. Ô đích có giá trị 0, vì sau đó không còn gì để nhận. Phương pháp này cần biết trước luật của môi trường. Nó chưa phải là học từ trải nghiệm.

Hàm target có hai nhánh. Bước vào đích thì target chỉ là phần thưởng, bằng 5, và con số 999 bị bỏ qua đúng như mong muốn. Bước chưa kết thúc thì target là phần thưởng cộng gamma nhân giá trị tốt nhất ở ô sau: −1+0.9⋅5=3.5-1+0.9\cdot5=3.5. Cần phân biệt hai lý do dừng. Nếu một lượt bị dừng giữa hành lang chỉ vì hết số bước cho phép, robot chưa tới đích, nên target vẫn phải cộng giá trị tương lai.

Ví dụ 3: Agent tự học, rồi được kiểm bằng đường đi

Agent bắt đầu với bảng Q toàn số 0, chơi 400 lượt, mỗi lượt tối đa 12 bước. Mỗi bước, với xác suất 0.25 agent chọn ngẫu nhiên một trong hai hành động để khám phá, còn lại thì chọn hành động có Q cao nhất. Học xong, ta đánh giá bằng cách cho agent luôn chọn hành động tốt nhất, và trong lúc đánh giá thì bảng Q không được cập nhật.

Python
import numpy as np

def step(state, action):
    assert state in [0, 1] and action in [0, 1]
    following = state if action == 0 else state + 1
    terminal = following == 2
    return following, 5.0 if terminal else -1.0, terminal

rng = np.random.default_rng(91)
Q = np.zeros((3, 2))
visits = np.zeros((3, 2), dtype=int)
gamma, alpha, epsilon = 0.9, 0.3, 0.25
for _ in range(400):
    state = 0
    for _ in range(12):
        if rng.random() < epsilon:
            action = int(rng.integers(2))
        else:
            tied = np.flatnonzero(Q[state] == Q[state].max())
            action = int(rng.choice(tied))
        following, reward, terminal = step(state, action)
        target = reward if terminal else reward + gamma * Q[following].max()
        Q[state, action] += alpha * (target - Q[state, action])
        visits[state, action] += 1
        state = following
        if terminal:
            break

saved_Q = Q.copy()
state, path, rewards = 0, [0], []
for _ in range(6):
    state, reward, terminal = step(state, int(np.argmax(Q[state])))
    path.append(state)
    rewards.append(reward)
    if terminal:
        break
observed_return = sum(gamma ** t * reward for t, reward in enumerate(rewards))
assert path == [0, 1, 2] and np.isclose(observed_return, 3.5)
assert np.array_equal(Q, saved_Q) and np.all(Q[2] == 0)
assert np.all(visits[:2] > 0)
print("Q (cột chờ, đi phải):", Q.round(3).tolist())
print("đường greedy:", path, "return:", f"{observed_return:.3f}")
print("mọi cặp không-terminal đã được thử:", bool(np.all(visits[:2] > 0)))

Bảng Q có một hàng cho mỗi ô và một cột cho mỗi hành động. Ở ô 0, đi phải có Q bằng 3.5, cao hơn đứng chờ. Ở ô 1, đi phải có Q bằng 5. Cả hai khớp với giá trị Bellman tính ở ví dụ 2. Hàng của ô đích vẫn bằng 0, vì từ đó không bao giờ có bước cập nhật nào. Khi có nhiều hành động cùng Q cao nhất, agent chọn ngẫu nhiên giữa chúng, để không luôn nghiêng về hành động đầu tiên.

Đường đi khi chọn tốt nhất là 0, 1, 2: hai bước, đúng là đường ngắn nhất, và return bằng 3.5 như tính tay. Mọi cặp ô và hành động chưa kết thúc đều đã được thử ít nhất một lần, nhờ phần khám phá ngẫu nhiên. Kết quả này kiểm chính sách từ ô 0 trong đúng môi trường này. Nó không chứng minh Q-learning với learning rate cố định luôn hội tụ trong mọi bài toán.

Mục lục