Nhập môn Reinforcement Learning: Policies, Value Functions và Bellman Equations

Chào mọi người, ở bài trước chúng ta đã set up xong bộ khung của một bài toán RL thông qua Finite MDP, hiểu được cách Agent giao tiếp với Environment và mục tiêu tối thượng của nó là tối đa hóa Expected return ($G_t$).

Nhưng câu hỏi đặt ra là: Làm thế nào để Agent biết một state là "tốt" hay "xấu"? Làm sao nó biết chọn action nào để dẫn tới cái expected return cao nhất đó?

Hôm nay chúng ta sẽ giải quyết câu hỏi này bằng cách đi vào trái tim của mọi thuật toán Reinforcement Learning: Value Functions và Bellman Equations. Phần này toán khá nặng, các bạn hãy chuẩn bị sẵn tinh thần nhé.

1. Policies và Value Functions

Hầu hết các thuật toán RL đều dựa trên việc ước lượng các Value Functions (Hàm giá trị). Nói một cách đơn giản, hàm giá trị dùng để đánh giá xem việc Agent ở tại một state nhất định (hoặc thực hiện một action nhất định tại state đó) là tốt tới mức nào. Tốt ở đây chính là lượng expected return mà Agent có thể thu được trong tương lai.

Tất nhiên, số reward thu được trong tương lai phụ thuộc hoàn toàn vào những hành động mà Agent sẽ thực hiện. Do đó, Value function phải được định nghĩa dựa trên một thứ gọi là Policy (Chính sách).

Policy ($\pi$)

Policy là cách mà Agent ánh xạ (mapping) từ state hiện tại sang action. Nếu Agent sử dụng policy $\pi$ tại thời điểm $t$, thì $\pi(a|s)$ chính là xác suất mà $A_t = a$ nếu $S_t = s$. Nói trắng ra, $\pi$ là bộ não của Agent. Nó quy định xác suất chọn hành động $a$ khi đang đứng ở trạng thái $s$.

State-value function ($v_\pi$)

Khi đã có một policy $\pi$, ta định nghĩa State-value function của một state $s$ (ký hiệu là $v_\pi(s)$) là expected return (lợi tức kỳ vọng) khi Agent bắt đầu từ $s$ và bám theo policy $\pi$ cho tới cuối:

$$v_\pi(s) \doteq \mathbb{E}_\pi [G_t | S_t = s] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \Big| S_t = s \right]$$

$\mathbb{E}_\pi$ là giá trị kỳ vọng khi Agent theo policy $\pi$. Nếu Agent đang ở state $s$, $v_\pi(s)$ cho nó biết: "Nếu mày cứ đi theo chiến thuật $\pi$ này, trung bình mày sẽ kiếm được chừng này điểm".

Action-value function ($q_\pi$)

Tương tự, ta có hàm đánh giá việc chọn một hành động cụ thể $a$ tại state $s$, sau đó mới tiếp tục đi theo policy $\pi$. Ký hiệu là $q_\pi(s, a)$ và được gọi là Action-value function:

$$q_\pi(s, a) \doteq \mathbb{E}_\pi [G_t | S_t = s, A_t = a] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \Big| S_t = s, A_t = a \right]$$

$q_\pi$ cực kỳ quan trọng trong các model-free methods (như Q-Learning mà ta sẽ học sau này), vì nó chỉ thẳng cho Agent biết action nào đang là tốt nhất mà không cần biết rules của environment.

2. Phương trình Bellman (Bellman Expectation Equation)

Điểm ăn tiền nhất của value functions trong RL là chúng thỏa mãn một tính chất đệ quy cực kỳ đẹp. Đối với bất kỳ policy $\pi$ và state $s$ nào, giá trị của $s$ luôn có thể phân tích thành: Reward ngay lập tức + Giá trị của state tiếp theo.

Nhớ lại công thức tính Return ở bài trước: $G_t = R_{t+1} + \gamma G_{t+1}$. Lắp nó vào định nghĩa của $v_\pi(s)$, ta có một phương trình kinh điển:

$$v_\pi(s) \doteq \mathbb{E}_\pi [G_t | S_t = s]$$

$$= \mathbb{E}_\pi [R_{t+1} + \gamma G_{t+1} | S_t = s]$$

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

Phương trình cuối cùng chính là Bellman Equation cho $v_\pi$. Nhìn mớ toán này có vẻ đáng sợ, nhưng thực chất nó mô tả một logic rất tự nhiên. Hãy bóc tách nó ra:

1. $\sum_a \pi(a|s)$: Agent thử tất cả các action $a$ có thể làm tại state $s$, nhân với xác suất nó sẽ chọn action đó (do policy $\pi$ quyết định).
2. $\sum_{s', r} p(s', r|s, a)$: Với mỗi action $a$, environment sẽ đưa Agent tới state $s'$ và trả về reward $r$. Ta tính tổng tất cả các trường hợp này nhân với xác suất xảy ra của chúng (hàm $p$ của MDP).
3. $\left[ r + \gamma v_\pi(s') \right]$: Đây là giá trị đạt được của nhánh đó, gồm reward hiện tại $r$ cộng với giá trị (đã discount) của state tiếp theo $\gamma v_\pi(s')$.

Tóm lại, Bellman Equation cho thấy giá trị của một state $s$ chính là kỳ vọng của các kết quả có thể xảy ra, lấy trung bình theo xác suất chọn action của $\pi$ và xác suất phản hồi của environment $p$.

(Note: Nếu bạn vẽ cái này ra giấy dưới dạng một cái cây rẽ nhánh, bạn sẽ có khái niệm gọi là Backup diagram - dùng rất nhiều để minh họa thuật toán).

3. Optimal Value Functions (Hàm giá trị tối ưu)

Giải quyết một bài toán RL đồng nghĩa với việc tìm ra một policy đem lại nhiều reward nhất trong dài hạn.

Một policy $\pi$ được định nghĩa là tốt hơn hoặc bằng policy $\pi'$ nếu expected return của nó lớn hơn hoặc bằng $\pi'$ trên mọi states. Tức là: $\pi \geq \pi'$ khi và chỉ khi $v_\pi(s) \geq v_{\pi'}(s)$ với mọi $s \in \mathcal{S}$.

Sẽ luôn có ít nhất một policy tốt hơn hoặc bằng tất cả các policy còn lại. Ta gọi đó là Optimal policy, ký hiệu là $\pi_*$. Tất cả các optimal policies đều chia sẻ chung một state-value function tối ưu, gọi là Optimal state-value function, $v_*(s)$:

$$v_*(s) \doteq \max_\pi v_\pi(s)$$

Và tương tự, chúng cũng chia sẻ chung một Optimal action-value function, $q_*(s, a)$:

$$q_*(s, a) \doteq \max_\pi q_\pi(s, a)$$

Để hiểu rõ sự liên kết, $q_*(s, a)$ có thể viết dưới dạng $v_*(s)$ như sau:

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

Điều này có nghĩa: Giá trị tối ưu của việc chọn action $a$ tại state $s$ chính là expected reward nhận được lập tức cộng với giá trị tối ưu của state tiếp theo.

4. Bellman Optimality Equation (Phương trình tối ưu Bellman)

Vì $v_*$ là hàm giá trị của policy tối ưu, nó phải thỏa mãn điều kiện tự nhiên tả trị của một state phải bằng với expected return của hành động tốt nhất từ state đó. Khác với Bellman equation thông thường (tính trung bình qua các actions), Bellman Optimality Equation sẽ lấy giá trị Max:

$$v_*(s) = \max_{a \in \mathcal{A}(s)} q_{\pi_*}(s, a)$$

$$= \max_a \mathbb{E}_{\pi_*} [G_t | S_t = s, A_t = a]$$

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

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

Hai phương trình cuối cùng chính là form chuẩn của Bellman Optimality Equation cho $v_*(s)$.

Tương tự, đối với $q_*(s, a)$, phương trình tối ưu Bellman là:

$$q_*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \Big| S_t = s, A_t = a \right]$$

$$= \sum_{s', r} p(s', r|s, a) \left[ r + \gamma \max_{a'} q_*(s', a') \right]$$

Đối với finite MDP, Bellman optimality equation cho $v_*$ là một hệ gồm $N$ phương trình phi tuyến (với $N$ là số lượng states). Nếu biết rõ dynamics của môi trường (hàm $p$), theo nguyên tắc ta có thể giải hệ phương trình này bằng các phương pháp giải quyết hệ phương trình phi tuyến tính.

Một khi đã có $v_*$, việc tìm ra optimal policy $\pi_*$ cực kỳ đơn giản. Tại bất kỳ state $s$ nào, sẽ có ít nhất một action đạt được giá trị max trong phương trình Bellman optimality. Mọi policy gán xác suất $>0$ cho các action tối ưu này (và $0$ cho các action còn lại) đều là optimal policy. Nói cách khác, khi có $v_*$, Agent chỉ cần tỏ ra greedy (tham lam) ở mỗi step là đủ để tối ưu hóa toàn bộ quá trình dài hạn. Nếu có $q_*$ thì việc này còn dễ hơn nữa, Agent thậm chí không cần biết dynamics $p$ của môi trường, chỉ cần nhìn vào $q_*$ và chọn action có giá trị cao nhất là xong.

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

Mặc dù Bellman optimality equations cung cấp một lời giải toán học cực kỳ hoàn hảo để tìm optimal policy, trong thực tế ta hiếm khi tính toán trực tiếp được nó do 3 giới hạn:

1. Hiếm khi ta biết được chính xác hàm dynamics $p$ của môi trường.
2. Năng lực tính toán (Computational cost) là có giới hạn, đặc biệt khi state space quá lớn.
3. Không đủ bộ nhớ, ví dụ trò chơi Backgammon có $10^{20}$ states, không thể nào lưu trữ hết được.

Do đó, các thuật toán RL thực tế sinh ra là để tìm cách xấp xỉ (approximate) lời giải của Bellman equation thay vì giải nó một cách tuyệt đối. Ở phần sau, chúng ta sẽ bước sang một chương mới, khám phá cách dùng Dynamic Programming (Quy hoạch động) để giải quyết các MDP khi biết trước môi trường.

Cảm ơn các bạn đã đọc đến đây, phần này toán nhiều chắc cũng lú lắm rồi . Hẹn gặp lại!

References:

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