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

Nhập môn Reinforcement Learning: Dynamic Programming (Quy hoạch động)

Chào mọi người, ở bài trước chúng ta đã mổ xẻ Value Functions và Bellman Equations. Ta đã biết đích đến của RL là tìm ra hàm giá trị tối ưu ( $v_*$ hoặc $q_*$ ), từ đó suy ra chính sách tối ưu ( $\pi_*$ ). Nhưng làm thế nào để thực sự "tính" ra được chúng bằng code?

Hôm nay chúng ta sẽ giải quyết bài toán đó bằng một nhóm thuật toán có tên là Dynamic Programming (DP) - Quy hoạch động.

Lưu ý quan trọng: Trong RL, thuật ngữ DP được dùng để chỉ các thuật toán dùng để tính toán ra optimal policies với giả định rằng ta có một perfect model của environment (tức là ta biết trước chính xác hàm dynamics $p(s', r | s, a)$ ). Trong thực tế, điều kiện này hiếm khi xảy ra, nhưng DP vẫn cực kỳ quan trọng vì nó cung cấp nền tảng lý thuyết vững chắc cho hầu hết các thuật toán RL thực chiến sau này (như Q-Learning hay Actor-Critic).

Thuật toán DP trong RL xoay quanh 2 core steps: Policy Evaluation (Đánh giá chính sách) và Policy Improvement (Cải thiện chính sách).

1. Policy Evaluation (Dự đoán / Đánh giá chính sách)

Đầu tiên, giả sử ta đang có một policy $\pi$ ngẫu nhiên. Làm sao ta biết policy này tốt hay dở? Ta phải tính được state-value function $v_\pi$ của nó. Quá trình tính toán ra $v_\pi$ cho một policy $\pi$ bất kỳ được gọi là Policy Evaluation.

Nhớ lại phương trình Bellman cho $v_\pi$ ở bài trước:

$v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) \left[ r + \gamma v_\pi(s') \right]$

Nếu environment có $N$ states, ta sẽ có một hệ gồm $N$ phương trình tuyến tính với $N$ ẩn (chính là $v_\pi$ của $N$ states). Ta hoàn toàn có thể giải hệ này bằng toán học thuần túy. Tuy nhiên, tính toán ma trận rất tốn kém khi state space lớn. Thay vào đó, DP sử dụng phương pháp Iterative (Lặp).

Ta khởi tạo một mảng $v_0(s)$ cho tất cả các state (có thể khởi tạo bằng 0). Sau đó, ta dùng phương trình Bellman như một công thức cập nhật (update rule) để tính $v_1$ , $v_2$ , $v_3$ ...:

$v_{k+1}(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) \left[ r + \gamma v_k(s') \right]$

Ý nghĩa của công thức này rất trực quan: Giá trị mới của state $s$ (ở bước $k+1$ ) được tính bằng expected return của các states tiếp theo (dựa trên giá trị cũ ở bước $k$ ). Một vòng lặp đi qua toàn bộ các states $\mathcal{S}$ để update giá trị được gọi là một sweep. Khi $k \to \infty$ , chuỗi $\{v_k\}$ được chứng minh là sẽ hội tụ chính xác về $v_\pi$ .

Trong thực hành code, ta sẽ dừng vòng lặp khi sự thay đổi giá trị giữa 2 bước $\max_{s \in \mathcal{S}} |v_{k+1}(s) - v_k(s)|$ nhỏ hơn một ngưỡng $\theta$ (theta) cực nhỏ nào đó.

2. Policy Improvement (Cải thiện chính sách)

Ok, bây giờ ta đã có $v_\pi$ để biết policy hiện tại $\pi$ xịn tới đâu. Câu hỏi đặt ra là: Liệu ta có thể tìm ra một policy $\pi'$ nào đó tốt hơn $\pi$ không?

Giả sử tại state $s$ , thay vì chọn action theo policy $\pi$ , ta tò mò muốn thử chọn một action $a$ khác đi ( $a \neq \pi(s)$ ), và sau đó từ state tiếp theo ta lại ngoan ngoãn đi theo policy $\pi$ như cũ. Giá trị của việc "phá lệ 1 bước" này chính là action-value function $q_\pi(s, a)$ :

$q_\pi(s, a) = \sum_{s', r} p(s', r|s, a) [r + \gamma v_\pi(s')]$

Policy Improvement Theorem chỉ ra rằng: Nếu $q_\pi(s, a) > v_\pi(s)$ , có nghĩa là việc "phá lệ" chọn action $a$ tại state $s$ đem lại kỳ vọng phần thưởng cao hơn là việc bám theo policy cũ. Vậy thì tội gì không đổi policy?

Từ đó, ta xây dựng một policy mới (gọi là $\pi'$ ) bằng cách tỏ ra Greedy (Tham lam). Tại mỗi state $s$ , ta chọn action đem lại giá trị $q_\pi$ lớn nhất:

$\pi'(s) \doteq \arg\max_a q_\pi(s, a) = \arg\max_a \sum_{s', r} p(s', r|s, a) [r + \gamma v_\pi(s')]$

Bằng cách luôn chọn hành động nhìn có vẻ tốt nhất trong ngắn hạn (dựa trên giá trị đánh giá $v_\pi$ ), policy mới $\pi'$ đảm bảo sẽ tốt hơn hoặc ít nhất là bằng với policy cũ $\pi$ . Nếu $\pi' = \pi$ , điều đó có nghĩa là policy của ta đã hội tụ, và nó chính là Optimal Policy ( $\pi_*$ ).

3. Policy Iteration (Lặp chính sách)

Khi ghép 2 quy trình trên lại với nhau, ta có một thuật toán hoàn chỉnh để tìm ra Optimal Policy. Quy trình này gọi là Policy Iteration:

Khởi tạo một policy ngẫu nhiên $\pi_0$ .
Evaluation: Đánh giá $\pi_0$ để tìm ra $v_{\pi_0}$ .
Improvement: Dùng $v_{\pi_0}$ để update thành policy $\pi_1$ (tham lam hơn).
Lặp lại bước 2 và 3 cho đến khi policy không thay đổi nữa.

Chuỗi tiến hóa sẽ trông như thế này:

$\pi_0 \xrightarrow{E} v_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} v_{\pi_1} \xrightarrow{I} \pi_2 \xrightarrow{E} \dots \xrightarrow{I} \pi_* \xrightarrow{E} v_*$

(E: Evaluation, I: Improvement)

Điểm mạnh của Policy Iteration là nó hội tụ cực kỳ nhanh về policy tối ưu, thường chỉ mất một vài vòng lặp.

4. Value Iteration (Lặp giá trị)

Policy Iteration có một nhược điểm: Ở mỗi bước Evaluation, nó đòi hỏi ta phải quét qua (sweep) toàn bộ state space nhiều lần để update value function cho tới khi hội tụ hoàn toàn. Nếu state space lớn, việc này siêu tốn tài nguyên.

Liệu ta có thực sự cần đợi $v_\pi$ hội tụ hoàn toàn rồi mới tính Improvement không? Câu trả lời là không. Ta hoàn toàn có thể rút ngắn bước Evaluation lại (thậm chí chỉ sweep đúng 1 lần) mà thuật toán vẫn đảm bảo hội tụ. Phương pháp này gọi là Value Iteration.

Thay vì đánh giá và cải thiện tách biệt, Value Iteration gộp chúng lại bằng cách update thẳng giá trị state dựa trên phương trình tối ưu Bellman (Bellman Optimality Equation):

$v_{k+1}(s) \doteq \max_a \mathbb{E} [R_{t+1} + \gamma v_k(S_{t+1}) | S_t = s, A_t = a]$

$= \max_a \sum_{s', r} p(s', r|s, a) [r + \gamma v_k(s')]$

Notice sự khác biệt: Trong Policy Evaluation, ta dùng $\sum_a \pi(a|s)$ (lấy trung bình theo policy). Còn trong Value Iteration, ta lấy thẳng $\max_a$ (lấy giá trị của action tốt nhất).

Thuật toán Value Iteration sẽ liên tục sweep qua các states, update giá trị bằng toán tử Max này. Khi mảng $v$ hội tụ (sự thay đổi giữa các step vô cùng nhỏ), ta thu được $v_*$ . Từ $v_*$ , ta chỉ cần làm 1 bước Greedy để trích xuất ra Optimal policy $\pi_*$ .

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

Cả Policy Iteration và Value Iteration đều là những giải pháp toán học hoàn hảo. Nhưng như tôi đã nhấn mạnh ở đầu bài, chúng có một điểm yếu chí mạng: Chúng yêu cầu phải biết trước toàn bộ dynamics của môi trường (hàm $p$ ). Nghĩa là Agent phải "nhìn thấu" quy luật vận hành của vũ trụ (environment) trước cả khi tương tác với nó.

Điều này giống như việc chơi game mà bạn có sẵn source code của game vậy. Trong thực tế, AI làm gì có đặc quyền đó! Chưa kể, nếu state space quá khổng lồ (như cờ vây với $10^{170}$ states), việc quét qua mảng state (sweeps) để update là điều không tưởng, dẫn đến khái niệm "Curse of Dimensionality" (Lời nguyền không gian đa chiều).

Vậy làm sao để Agent tự học ra Optimal Policy thông qua kinh nghiệm thực chiến (trial-and-error) mà không cần biết trước laws của environment? Chúng ta sẽ bước sang một chương hoàn toàn mới của RL: Monte Carlo Methods và Temporal-Difference Learning (TD).

Hẹn gặp lại các bạn ở bài viết sau!

References:

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

ReinforcementLearning