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

Nhập môn Reinforcement Learning: Monte Carlo Methods và Temporal-Difference (TD) Learning

Chào mọi người. Ở tập trước, chúng ta đã thấy sự xịn xò của Dynamic Programming (DP) trong việc tìm ra optimal policy. Nhưng DP có một điểm yếu "chí mạng": nó đòi hỏi chúng ta phải có một perfect model của environment (biết chính xác ma trận xác suất chuyển đổi $p$ ).

Hãy tưởng tượng bạn đang lập trình một con xe tự hành. Làm sao bạn có thể viết ra chính xác phương trình toán học mô tả độ ma sát của từng hạt cát trên đường, lực cản của từng ngọn gió, hay hành vi ngẫu nhiên của một người đi bộ? Không thể nào!

Trong thực tế, môi trường là một hộp đen (black-box). Agent phải tự ném mình vào đó, thử nghiệm (trial-and-error), ăn đòn, nhận phần thưởng và tự đúc kết kinh nghiệm. Các phương pháp học trực tiếp từ kinh nghiệm mà không cần biết trước dynamics của môi trường được gọi là Model-free Methods.

Hôm nay, chúng ta sẽ tìm hiểu hai trụ cột lớn nhất của Model-free RL: Monte Carlo (MC) và Temporal-Difference (TD) Learning.

1. Monte Carlo Methods (Học từ toàn bộ Episode)

Ý tưởng của Monte Carlo (MC) cực kỳ hoang dã và tự nhiên: "Cứ chơi đi, chơi xong ván rồi tổng kết xem được bao nhiêu điểm, từ đó đánh giá các bước đi trước đó".

Thay vì dùng phương trình Bellman để tính toán kỳ vọng của mọi nhánh rẽ có thể xảy ra (như DP), MC dùng phương pháp Sample-Average (lấy trung bình mẫu) mà chúng ta đã làm quen ở bài Multi-armed Bandit.

Để tính state-value $v_\pi(s)$ của một policy $\pi$ , MC làm như sau:

Cho Agent chạy một hoặc nhiều episodes dựa trên policy $\pi$ .
Với mỗi lần Agent đi qua state $s$ , ta ghi lại tổng Return $G_t$ mà nó nhận được tính từ $s$ cho tới cuối ván.
$v(s)$ đơn giản sẽ là trung bình cộng của tất cả các $G_t$ này.

Theo luật số lớn (Law of Large Numbers) trong xác suất thống kê, khi số lượng sample (episodes) tiến tới vô cực, giá trị trung bình này sẽ hội tụ chính xác về giá trị thực $v_\pi(s)$ .

Công thức update (dưới dạng incremental) trông quen thuộc thế này:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]$

Điểm mạnh của MC:

Hoàn toàn Model-free: Chả cần biết xác suất $p(s',r|s,a)$ là cái quái gì. Chỉ cần trải nghiệm thực tế hoặc qua một bộ simulator là đủ.
Ít bị thiên vị (Unbiased): Vì nó dùng Return $G_t$ thực tế để update, nên không bị sai số dây chuyền.

Điểm yếu của MC:

Bạn phải đợi tới khi kết thúc episode thì mới biết được $G_t$ để mà update.
Nếu bạn đang làm một task kéo dài vô tận (Continuing tasks) hoặc một ván game quá dài, MC trở nên vô dụng vì nó học quá chậm.
Variance (phương sai) cực cao: Có quá nhiều sự kiện ngẫu nhiên diễn ra trong một episode, làm cho $G_t$ dao động cực mạnh giữa các ván chơi.

2. Temporal-Difference (TD) Learning (Sự kết hợp hoàn hảo)

Nếu MC là kiểu học "xong xuôi mới rút kinh nghiệm", thì TD Learning là kiểu "đi một bước, đoán một bước, sai đâu sửa đó ngay lập tức". TD là sự pha trộn những gì tinh túy nhất của Monte Carlo và Dynamic Programming.

Giống MC, TD là Model-free và học thẳng từ raw experience. Nhưng giống DP, TD không cần đợi đến hết ván. Nó update giá trị dự đoán của mình dựa trên một dự đoán khác ngay ở bước tiếp theo. Kỹ thuật "lấy mỡ nó rán nó" này trong RL gọi là Bootstrapping.

Phương trình TD(0) - Trái tim của TD Learning

Hãy nhìn lại công thức update của MC:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]$

MC dùng $G_t$ (tổng Return thực tế tới cuối game) làm Target để hướng tới.

TD Learning nhận ra rằng: "Khoan đã, Return $G_t = R_{t+1} + \gamma G_{t+1}$ cơ mà. Vậy tao có thể xấp xỉ $G_{t+1}$ bằng chính cái giá trị ước lượng $V(S_{t+1})$ hiện tại của tao được không?".

Câu trả lời là ĐƯỢC. Thay vì dùng $G_t$ thực tế, thuật toán TD đơn giản nhất (gọi là TD(0) hay One-step TD) sử dụng Target là $R_{t+1} + \gamma V(S_{t+1})$ . Công thức update trở thành:

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

Trong đó:

$R_{t+1} + \gamma V(S_{t+1})$ được gọi là TD Target (Mục tiêu TD). Nó là tổng phần thưởng vừa nhận được cộng với dự đoán giá trị tại trạng thái tiếp theo.
Cụm $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ cực kỳ nổi tiếng, nó mang tên TD Error (Sai số TD). Nó đo lường sự chênh lệch giữa giá trị dự đoán lúc trước và thực tế ở ngay bước sau đó.

Ví dụ để bạn dễ hình dung TD vs MC

Bạn đi từ công ty về nhà, dự đoán mất 30 phút.

Monte Carlo: Bạn đi tới khi bước chân vào nhà, xem đồng hồ mất 45 phút ( $G_t$ ). Bạn update lại bộ não: "À, từ cty về nhà chắc phải tầm 45p".
TD Learning: Bạn mới đi được 5 phút thì gặp kẹt xe ( $R_{t+1}$ ). Bạn đứng giữa dòng xe, ước tính quãng đường còn lại phải mất 40 phút nữa ( $V(S_{t+1})$ ). Ngay lúc đó, bạn tự update não bộ luôn: "Toang rồi, tổng thời gian về nhà sẽ là $5 + 40 = 45$ phút". Bạn không cần đợi về tới nhà mới nhận ra hôm nay mình về muộn!

3. So sánh DP, MC và TD

Để chốt lại, hãy nhìn vào cách 3 thuật toán này cập nhật giá trị (Backup):

Dynamic Programming (DP): Expected update. Nó đứng ở state hiện tại, "nhìn" sang TẤT CẢ các state có thể xảy ra tiếp theo (cần biết mô hình $p$ ), nhân với xác suất, rồi update. (Có Bootstrapping).
Monte Carlo (MC): Sample update. Nó ném Agent đi thử 1 con đường thực tế cho tới tận ĐÍCH (cuối episode), lấy tổng Return thực tế để update state khởi điểm. (KHÔNG Bootstrapping).
Temporal-Difference (TD): Sample update. Nó cho Agent đi 1 BƯỚC THỰC TẾ, lấy reward thực tế cộng với giá trị dự đoán của state kế tiếp để update state hiện tại. (Có Bootstrapping, Không cần model).

Ưu điểm vượt trội của TD Learning:

Không cần biết môi trường (Model-free).
Tốc độ học cực nhanh (Online): Có thể update sau mỗi bước đi, rất phù hợp cho Continuing tasks (không có điểm kết thúc) hoặc các episode siêu dài.
Phương sai (Variance) thấp hơn MC nhiều do chỉ phụ thuộc vào 1 step ngẫu nhiên thay vì nguyên một ván ngẫu nhiên.
Theo các chứng minh thực nghiệm, TD Learning thường hội tụ nhanh hơn MC trên hầu hết các bài toán.

(Thực tế, hệ thống Dopamine trong não người cũng phát ra các xung điện có cơ chế hoạt động giống hệt như TD Error của thuật toán này).

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

Tới đây, chúng ta đã biết cách dùng TD Learning để đánh giá một policy $v_\pi$ (Policy Evaluation). Nhưng còn bước Cải thiện (Policy Improvement) để tìm ra Optimal Policy $\pi_*$ thì sao?

Trong Model-free RL, Agent không thể nào dùng State-value $V(s)$ để đưa ra quyết định được. Nhớ lại Bellman Optimality ở Tập 5: để chọn action từ $V(s)$ , ta phải biết luật của môi trường. Vì không có model, chúng ta bắt buộc phải đánh giá thẳng vào Action-value function $Q(s, a)$ .

Ở bài sau, chúng ta sẽ đi vào phần hấp dẫn nhất: Ứng dụng TD Learning vào Control (Điều khiển) bằng hai thuật toán kinh điển nhất mọi thời đại: SARSA (On-policy) và Q-Learning (Off-policy).

Cảm ơn các bạn đã đồng hành cùng series!

References:

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

ReinforcementLearning