Đã đăng vào khoảng 7 giờ trước 10 phút đọc

Nhập môn Reinforcement Learning: SARSA, Q-Learning và khái niệm On-policy vs Off-policy

Chào mọi người, tiếp nối series, ở tập trước chúng ta đã thấy sự ưu việt của Temporal-Difference (TD) Learning trong việc đánh giá một policy (Policy Evaluation) mà không cần biết trước môi trường (Model-free).

Nhưng nếu chỉ đánh giá xem một policy tốt hay dở thì Agent mãi chỉ là một kẻ quan sát. Để thực sự tạo ra một AI biết "chơi game", chúng ta phải tìm cách tối ưu hóa chính sách đó (Policy Improvement) để đạt được Optimal Policy ( $\pi_*$ ). Quá trình này trong RL được gọi là Control.

Hôm nay, chúng ta sẽ áp dụng TD Learning vào Control thông qua hai thuật toán kinh điển nhất mọi thời đại: SARSA và Q-Learning. Đồng thời, ta sẽ làm rõ hai khái niệm cốt lõi: On-policy và Off-policy.

1. Tại sao lại là Action-Value $Q(s, a)$ mà không phải State-Value $V(s)$ ?

Nhớ lại ở bài Dynamic Programming (DP), khi ta có $V(s)$ , ta làm bước Improvement bằng cách duyệt qua tất cả các state tiếp theo, nhân xác suất $p(s', r | s, a)$ để chọn ra hành động tốt nhất.

Nhưng trong Model-free RL, Agent làm gì có hàm $p$ mà nhân! Nó hoàn toàn mù tịt về việc "hành động $a$ sẽ dẫn tới $s'$ nào". Vì vậy, State-Value $V(s)$ trở nên vô dụng trong việc ra quyết định ở môi trường Model-free.

Giải pháp bắt buộc: Chúng ta phải đánh giá trực tiếp vào Action-Value Function $Q(s, a)$ . Khi đã có bảng $Q(s, a)$ chính xác, Agent không cần biết môi trường hoạt động ra sao. Đang ở state $s$ , nó chỉ việc nhìn vào bảng $Q$ , thấy action nào có giá trị lớn nhất thì vã luôn action đó (Greedy).

Mục tiêu của chúng ta bây giờ là đi tìm $Q_*(s, a)$ .

2. Khái niệm On-policy và Off-policy

Đây là chỗ rất nhiều người bị "lú" khi mới học RL. Khi Agent vừa phải học cách tối ưu hành động, vừa phải duy trì việc "khám phá" (exploration) để không bị kẹt ở local optimum, ta có hai hướng tiếp cận:

On-policy (Học đi đôi với hành): Thuật toán sử dụng và cải thiện cùng một policy. Nghĩa là Agent đang dùng policy $\pi$ để đi lại trong môi trường (thường là $\epsilon$ -greedy để có tính khám phá), thì nó cũng lấy chính những trải nghiệm ngáo ngơ đó để cập nhật hàm $Q$ cho policy $\pi$ .
Off-policy (Học một đằng, làm một nẻo): Thuật toán duy trì hai policy tách biệt.
1. Behavior policy: Policy dùng để khám phá môi trường (đi lại lộn xộn, random bằng $\epsilon$ -greedy).
2. Target policy: Policy đang được update và tối ưu (thường là policy tham lam - Greedy thuần túy). Agent có thể hành động rất ngớ ngẩn (bởi Behavior policy), nhưng não nó lại update giá trị cho một Target policy tối ưu.

Để dễ hiểu:

On-policy giống như bạn vừa chơi vừa tự rút kinh nghiệm từ chính những pha xử lý lỗi của mình.
Off-policy giống như bạn đang đi xe đạp cọc cạch (khám phá), nhưng trong đầu bạn lại đang mô phỏng và tính toán góc cua tối ưu cho một chiếc xe đua F1.

On-policy vs Off-policy (Ảnh minh họa: Sự khác biệt giữa On-policy và Off-policy)

3. SARSA: On-policy TD Control

SARSA là thuật toán đại diện cho On-policy. Tên của nó bắt nguồn từ chuỗi 5 sự kiện liên tiếp mà thuật toán dùng để update giá trị: State, Action, Reward, State (next), Action (next) $\rightarrow$ S-A-R-S-A.

Hãy nhớ lại công thức TD(0) dùng để update $V(s)$ ở bài trước:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$

Bây giờ ta chuyển nó sang cho $Q(s, a)$ . Rất đơn giản, tại state $S_t$ , Agent chọn action $A_t$ (bằng $\epsilon$ -greedy), nhận reward $R_{t+1}$ và bay sang $S_{t+1}$ . Ở $S_{t+1}$ , nó lại dùng chính policy $\epsilon$ -greedy hiện tại để "nhá hàng" trước xem action tiếp theo $A_{t+1}$ sẽ là gì. Khi đã có đủ bộ 5 biến $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ , nó update:

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]$

SARSA Backup Diagram (Backup diagram của thuật toán SARSA - Nguồn: Sutton & Barto)

Tại sao SARSA là On-policy? Vì cái Action tiếp theo $A_{t+1}$ dùng để tính TD Target ( $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ ) được bốc ra từ chính policy $\epsilon$ -greedy mà Agent đang sử dụng để tương tác với môi trường. Có chơi có chịu.

4. Q-Learning: Off-policy TD Control (Bước đột phá của RL)

Được phát minh bởi Chris Watkins vào năm 1989, Q-Learning là một trong những thuật toán vĩ đại nhất của RL. Nó là thuật toán Off-policy.

Thay vì dùng action $A_{t+1}$ ngẫu nhiên từ $\epsilon$ -greedy để tính giá trị cho state tiếp theo như SARSA, Q-Learning mạnh dạn giả định luôn: "Kệ mẹ việc lát nữa tao sẽ đi bước nào, tao sẽ lấy luôn giá trị của action MẠNH NHẤT tại state tiếp theo làm target để update cho state hiện tại!".

Công thức update của Q-Learning chỉ khác SARSA đúng một chữ max:

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) \right]$

Q-Learning Backup Diagram (Backup diagram của thuật toán Q-Learning - Nguồn: Sutton & Barto)

Tại sao Q-Learning là Off-policy?

Behavior policy (cách Agent đi): Vẫn là $\epsilon$ -greedy để thỉnh thoảng đi random khám phá môi trường.
Target policy (cách thuật toán update $Q$ ): Là policy Greedy thuần túy (thể hiện qua toán tử $\max_a$ ). Thuật toán này đang trực tiếp xấp xỉ hàm giá trị tối ưu $Q_*$ mà không thèm quan tâm tới việc Agent đang dùng policy nào để đi. Chỉ cần mọi state-action pairs đều được quét qua liên tục, Q-Learning chắc chắn sẽ hội tụ về $Q_*$ .

5. Ví dụ kinh điển: Vách đá (Cliff Walking)

Để thấy rõ sự khác biệt giữa SARSA và Q-Learning, hãy xem xét bài toán Cliff Walking từ sách của Sutton & Barto.

Agent xuất phát ở góc dưới bên trái (S) và muốn tới đích (G) ở góc dưới bên phải.
Ở giữa S và G là một vách đá. Nếu Agent bước vào vách đá, nó nhận Reward = -100 và bị ném về vạch xuất phát.
Mỗi bước đi bình thường nhận Reward = -1.

Cliff Walking Gridworld (Bài toán Cliff Walking: Con đường an toàn của SARSA (xanh) và tối ưu của Q-Learning (đỏ) - Nguồn: Sutton & Barto)

Khi ta chạy 2 thuật toán này với cùng một $\epsilon$ -greedy policy (tức là thi thoảng 10% Agent sẽ đi random kiểu ngáo ngơ):

Q-Learning (Off-policy): Nó sẽ học được con đường tối ưu tuyệt đối là đi men sát mép vách đá. Tại sao? Vì lúc update, hàm max của nó luôn nhìn thấy đường sát mép là ngắn nhất. Hậu quả: Vì thi thoảng Agent bị bắt ép đi random ( $\epsilon$ -greedy), nó rất hay trượt chân ngã xuống vực và bị -100 điểm. Q-Learning học được đường ngắn nhất, nhưng trong quá trình train nó ăn đòn rất nhiều.
SARSA (On-policy): Nó học được một con đường vòng vèo an toàn xa tít trên cao cách xa vách đá. Tại sao? Vì SARSA lấy chính sách hiện tại (bao gồm cả xác suất đi random rơi xuống vực) để update. Nó nhận ra: "À, thỉnh thoảng tao bị dở hơi đi random, nếu đi sát mép vực thì kiểu gì cũng có ngày rớt". Nên SARSA hạ giá trị của các state sát vách đá xuống, ép Agent đi vòng cho chắc cốp.

Kết luận:

Q-Learning tìm ra đường đi tối ưu (nhưng nguy hiểm nếu tính ngẫu nhiên còn tồn tại).
SARSA tìm ra đường đi an toàn nhất dựa trên mức độ ngẫu nhiên hiện tại của nó. Tùy vào bài toán (ví dụ: làm xe tự lái ngoài đời thực thì không thể dùng Q-Learning để thử đâm vào tường liên tục được), chúng ta sẽ chọn On-policy hay Off-policy cho phù hợp.

6. Pseudocode

Để các bạn dễ hình dung cách triển khai bằng code thực tế, tôi xin tóm tắt lại mã giả của cả hai thuật toán (tham khảo chuẩn từ sách của Sutton & Barto). Nhìn vào đây, bạn sẽ thấy sự khác biệt về luồng thực thi, đặc biệt là lúc chọn hành động tiếp theo ( $A'$ ) nó rõ ràng như thế nào:

Mã giả SARSA (On-policy Control):

Khởi tạo bảng Q(s, a) với giá trị tùy ý (hoặc bằng 0). Với Q(terminal, .) = 0.

Lặp cho mỗi episode:
    Khởi tạo trạng thái ban đầu S
    Chọn action A tại S dựa vào policy hiện tại (vd: ε-greedy suy ra từ Q)
    
    Lặp cho mỗi step của episode:
        Thực hiện action A, quan sát reward R và trạng thái tiếp theo S'
        Chọn action tiếp theo A' tại S' dựa vào policy hiện tại (vd: ε-greedy)
        
        // Update Q theo công thức SARSA
        Q(S, A) ← Q(S, A) + α * [R + γ * Q(S', A') - Q(S, A)]
        
        // Chuyển sang step tiếp theo
        S ← S'
        A ← A'
    Cho tới khi S là trạng thái kết thúc (terminal)

Mã giả Q-Learning (Off-policy Control):

Khởi tạo bảng Q(s, a) với giá trị tùy ý (hoặc bằng 0). Với Q(terminal, .) = 0.

Lặp cho mỗi episode:
    Khởi tạo trạng thái ban đầu S
    
    Lặp cho mỗi step của episode:
        Chọn action A tại S dựa vào Behavior policy (vd: ε-greedy suy ra từ Q)
        Thực hiện action A, quan sát reward R và trạng thái tiếp theo S'
        
        // Update Q theo công thức Q-Learning (Lấy MAX)
        Q(S, A) ← Q(S, A) + α * [R + γ * max_a Q(S', a) - Q(S, A)]
        
        // Chuyển sang step tiếp theo (chỉ gán lại State)
        S ← S'
    Cho tới khi S là trạng thái kết thúc (terminal)

Như bạn có thể thấy, SARSA phải "chọn trước" $A'$ rồi mới dám update $Q$ , và nó dùng luôn $A'$ đó cho bước đi tiếp theo (đúng chuẩn học đi đôi với hành). Trong khi Q-Learning thì mặc kệ, cứ lấy giá trị max để update, sang vòng lặp sau nó mới lại tung xúc xắc chọn $A$ mới (behavior).

Đôi lời trước khi kết thúc

Đến thời điểm này, bằng Tabular Methods (Q-Table lưu mảng giá trị), chúng ta đã giải quyết trọn vẹn bài toán Reinforcement Learning thông qua Q-Learning và SARSA. Agent hoàn toàn có thể tự mò mẫm từ số 0 để làm trùm một môi trường đơn giản.

Nhưng cuộc đời không như mơ. Nếu môi trường không chỉ có 100 states, mà là $10^{170}$ states như Cờ vây, hay states là vô hạn số thực như tọa độ góc của cánh tay robot, thì sao? Chúng ta không thể nào lập một cái bảng (table) để chứa hết được. Bảng sẽ tràn RAM, và thời gian duyệt mảng sẽ là hàng tỷ năm.

Cảm ơn các bạn đã theo dõi!

References:

Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction

ReinforcementLearning