Q-Learning: Học Bằng Thử Và Sai

Bài toán của Pixel

Với chừng đó thông tin, nhiệm vụ của Pixel là tối đa hoá tổng những con số ấy, cộng dồn theo thời gian. Không ai dạy nó luật chơi — nó phải tự suy ra, bằng cách chơi.

Đó chính là bài toán Reinforcement Learning đặt ra. Và Q-Learning là một trong những câu trả lời lâu đời và cứng cựa nhất cho bài toán đó.

Nghe hơi giống cách người ta huấn luyện một con chó: không giải thích khái niệm "ngồi xuống" là gì, chỉ thưởng snack mỗi khi con chó tình cờ làm đúng. Nhưng có một khác biệt: chẳng có bàn tay nào đứng ngoài chỉnh hành vi của Pixel cả. Nó phải tự mò, tự thử, tự sai, và — quan trọng nhất — tự ghi nhớ.

Chính chữ "tự ghi nhớ" đó là chỗ Q-Learning bước vào.

Giờ thì Pixel vẫn đang đứng ở góc lưới ô vuông, chưa biết gì cả.

Hãy xem nó bắt đầu như thế nào.

Trạng thái, hành động, phần thưởng

Pixel đứng ở ô góc trái. Việc đầu tiên nó nhận ra: nó đang ở một chỗ cụ thể, trong một tình huống cụ thể — gọi là trạng thái (state). Mỗi ô trên lưới là một trạng thái khác nhau.

Từ trạng thái đó, nó có thể làm vài việc: đi lên, đi xuống, đi trái, đi phải. Mỗi lựa chọn như vậy là một hành động (action).

Nó chọn đại một hướng — đi lên. Ô mới. Trạng thái mới. Và ngay sau đó, thế giới trả lời bằng một con số: phần thưởng (reward), đúng như đã nói ở phần trước.

Ba thứ đó — trạng thái, hành động, phần thưởng — là toàn bộ những gì Pixel có để làm việc. Câu hỏi còn lại: làm sao từ đó suy ra hành động nào tốt?

Nghe thì trừu tượng. Nhưng nếu bỏ hết mọi lựa chọn hành động, chỉ giữ lại đúng một phép cập nhật duy nhất, chuyện gì sẽ xảy ra?

Thử xem.

Demos

Q-Learning, nhìn thấy tận mắt

Đọc công thức là một chuyện. Thấy nó chạy thật, từng bước một, là chuyện khác hẳn.

Hai demo dưới đây cùng một mục đích: giúp bạn nhìn thấy Q-Learning học, không chỉ đọc về nó.

• Demo 1 cắt bỏ hết mọi thứ gây rối — không có lựa chọn, không có nhiều hướng đi — chỉ giữ lại đúng phép cập nhật, để bạn thấy giá trị lan dần từ đích ngược về điểm xuất phát.
• Demo 2 trả lại cho Pixel quyền lựa chọn: nhiều hành động, một mê cung nhỏ, và phải tự tìm đường.

Giờ trả lại cho Pixel những gì nó vừa mất: nhiều ô để đi, nhiều hướng để chọn.

Phép cập nhật vẫn y hệt — chỉ có một chỗ thay đổi: giờ nó phải quyết định sẽ làm gì tiếp theo, trước khi biết chuyện gì xảy ra.

Khai thác hay khám phá?

Pixel giờ đã có chút hiểu biết: vài ô nó tin là ổn, một hai ô nó nghi là bẫy. Nhưng "tin" và "nghi" không phải "chắc chắn."

Nếu Pixel luôn chọn hành động nó tin là tốt nhất — gọi là khai thác (exploitation) — nó có thể mắc kẹt mãi với con đường tạm ổn tìm ra đầu tiên, trong khi một con đường ngắn hơn chưa từng được thử. Nếu nó luôn chọn hành động ngẫu nhiên — khám phá (exploration) — nó chẳng bao giờ dùng được những gì đã học.

Cách giải quyết dùng trong demo và code ở bài này gọi là ε-greedy:

• với xác suất ε, chọn một hành động ngẫu nhiên (khám phá)
• với xác suất 1 − ε, chọn hành động Pixel tin là tốt nhất, tức argmax Q(s, a) (khai thác)

ε càng lớn, Pixel càng hay thử cái mới. ε càng nhỏ, Pixel càng bám sát những gì đã biết. Ở demo dưới, kéo thanh trượt "Khám phá ε" để thấy tận mắt hai thái cực đó.

Ở trên là Q-Learning chạy ngay trong trình duyệt, viết bằng JavaScript, cho dễ nhìn.

Nhưng nếu bạn muốn tự tay chạy lại, sửa phần thưởng, đổi kích thước lưới — thì mã Python bên dưới là bản để bạn nghịch.

Cài đặt bằng Python

Đúng bài toán ở demo trên — lưới 5×5, một đích, hai bẫy — viết lại bằng Python và NumPy:

import numpy as np
import random

N = 5
START = (0, 0)
GOAL = (4, 4)
TRAPS = {(1, 3), (3, 1)}
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # lên, xuống, trái, phải

alpha = 0.3
gamma = 0.9
epsilon = 0.2
episodes = 200
max_steps = 100

Q = np.zeros((N, N, len(ACTIONS)))


def step(state, action):
    r, c = state
    dr, dc = ACTIONS[action]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < N and 0 <= nc < N):
        nr, nc = r, c
    if (nr, nc) == GOAL:
        return (nr, nc), 10, True
    if (nr, nc) in TRAPS:
        return (nr, nc), -10, True
    return (nr, nc), -1, False


def choose_action(state, eps):
    if random.random() < eps:
        return random.randrange(len(ACTIONS))
    r, c = state
    return int(np.argmax(Q[r, c]))


for ep in range(episodes):
    state = START
    for t in range(max_steps):
        action = choose_action(state, epsilon)
        next_state, reward, done = step(state, action)
        r, c = state
        nr, nc = next_state
        best_next = 0 if done else np.max(Q[nr, nc])
        Q[r, c, action] += alpha * (reward + gamma * best_next - Q[r, c, action])
        state = next_state
        if done:
            break

Toàn bộ thuật toán nằm trong đúng một dòng: Q[r, c, action] += alpha * (reward + gamma * best_next - Q[r, c, action]) — công thức ở phần trước, viết lại bằng code.

Một chi tiết dễ bị bỏ sót: khi done là True (Pixel vừa tới đích hoặc sa bẫy), không có "bước kế tiếp" nào để tính giá trị tốt nhất — nên best_next phải là 0, không phải Q[nr, nc]. Bỏ chi tiết if done này thường không gây lỗi rõ ràng ngay (vì ô đích và ô bẫy không bao giờ được chọn làm điểm xuất phát của một bước đi, nên giá trị của chúng vốn dĩ vẫn luôn là 0) — nhưng viết tường minh ra vẫn tốt hơn: dễ đọc hơn, và không còn âm thầm dựa vào một sự trùng hợp.

Sau khi train xong, xem Pixel đi đường nào bằng chính sách đã học (không còn khám phá ngẫu nhiên nữa):

def run_greedy():
    state = START
    path = [state]
    for _ in range(40):
        r, c = state
        action = int(np.argmax(Q[r, c]))
        state, reward, done = step(state, action)
        path.append(state)
        if done:
            break
    return path

print(run_greedy())

Muốn nghịch thêm, vài chỗ đáng sửa trước tiên:

• TRAPS — đổi vị trí hoặc thêm bẫy, xem đường đi học được thay đổi ra sao.
• epsilon — để cao suốt quá trình train (không giảm dần) là một sự đơn giản hoá. Thử giảm dần epsilon theo từng episode, Pixel sẽ khai thác nhiều hơn về cuối.
• N — tăng kích thước lưới lên 10×10 hoặc hơn, rồi xem episodes cần bao nhiêu mới đủ để hội tụ.

Chỉnh cái cuối cùng đó đủ lâu, bạn sẽ đụng đúng vấn đề mà phần tiếp theo nói tới.

Cách sửa phổ biến nhất: thay cái bảng bằng một mạng neural. Thay vì tra một ô có sẵn, mạng đó ước lượng Q-value trực tiếp từ trạng thái đầu vào — kể cả những trạng thái nó chưa từng thấy. Gọi là Deep Q-Network (DQN).

Nguyên tắc lõi — thử, sai, cập nhật theo đúng công thức ở phần trước — không đổi. Chỉ có nơi lưu trữ hiểu biết là đổi: từ một cái bảng, thành trọng số của một mạng neural.

Đọc thêm

• An Introduction to Q-Learning: A Tutorial For Beginners — DataCamp
• Q-Learning in Reinforcement Learning — GeeksforGeeks
• Reinforcement Q-Learning from Scratch in Python with OpenAI Gym — LearnDataSci
• Reinforcement Learning Explained Visually (Part 4): Q-Learning, step-by-step — Towards Data Science
• Q-Learning By Examples — Revoledu