Nhập môn Reinforcement Learning: Finite Markov Decision Processes (MDP)

Sau khi tìm hiểu và làm quen với các dạng bài toán bandit cơ bản ở phần trước, chúng ta sẽ gác lại nó và đi vào vấn đề chính của RL. Hay nói một cách rõ ràng hơn, chúng ta sẽ đi sâu vào format chuẩn của các bài toán RL thực tế: Finite Markov Decision Processes (MDPs).

Trước khi giải quyết bất cứ bài toán RL nào, việc hiểu rõ frame của hệ thống thông qua MDP là điều kiện tiên quyết.

1. Agent-Environment Interface (Giao tiếp giữa Agent và Môi trường)

MDPs mang hàm nghĩa của một frame dành cho các vấn đề học tập thông qua tương tác (interaction) với mục tiêu đạt được kết quả mong muốn.

Trong đó:

• Đối tượng học tập (learner) hay người đưa ra quyết định được gọi là Agent.
• Thứ mà Agent giao tiếp, tương tác cùng, bao gồm tất cả những gì nằm bên ngoài Agent, được gọi là Environment (Môi trường).

Sự tương tác giữa chúng là liên tục không ngừng: Agent lựa chọn hành động (action) và Environment sẽ phản hồi lại bằng cách đưa Agent tới một trạng thái (state) mới. Đồng thời, Environment cũng trả về một tín hiệu gọi là reward (phần thưởng) – một giá trị số học mà Agent luôn cố gắng để tối đa hóa theo thời gian.

(Hình ảnh minh họa vòng lặp Agent - Environment)

Nói chính xác hơn, Agent và Environment giao tiếp với nhau dưới dạng các chuỗi thời gian rời rạc (discrete time steps), $t = 0, 1, 2, 3, \dots$ Tại mỗi thời điểm $t$:

• Agent nhận một biểu diễn (representation) của môi trường là state $S_t \in \mathcal{S}$.
• Dựa trên state đó, Agent đưa ra một hành động $A_t \in \mathcal{A}(s)$.
• Một time step sau (ở $t+1$), là hệ quả của action trên, Agent nhận được một giá trị phần thưởng $R_{t+1} \in \mathcal{R}$ và chuyển sang một state mới là $S_{t+1}$.

Tất cả kết hợp lại, ta có một chuỗi sequence kinh điển trong RL:

$$S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots$$

Trong finite MDP, các tập $\mathcal{S}$ (states), $\mathcal{A}$ (actions), và $\mathcal{R}$ (rewards) đều có số lượng phần tử giới hạn. Do đó, các biến ngẫu nhiên $R_t$ và $S_t$ sẽ có một phân phối xác suất rời rạc, phụ thuộc hoàn toàn vào state và action ở bước ngay trước đó.

Hàm xác suất biến động (dynamics) của MDP được định nghĩa:

$$p(s', r | s, a) \doteq \Pr\{S_t=s', R_t=r | S_{t-1}=s, A_{t-1}=a\}$$

Dấu $\doteq$ thể hiện đây là một định nghĩa. Công thức này cho thấy xác suất rơi vào trạng thái $s'$ và nhận phần thưởng $r$ hoàn toàn phụ thuộc vào trạng thái $s$ và hành động $a$ ở bước trước đó. Nếu state $s$ mang đủ mọi thông tin cần thiết từ quá khứ để quyết định tương lai mà không cần giữ lại toàn bộ lịch sử, ta gọi đó là Markov property (Tính chất Markov).

Ví dụ thực tế: Robot nhặt lon

Hãy tưởng tượng bạn có một con robot dọn vệ sinh.

• State ($\mathcal{S}$) có thể đơn giản là lượng pin: {high, low}.
• Action ($\mathcal{A}$) có thể là: {search, wait, recharge}. Tùy vào trạng thái pin (high hay low), robot sẽ quyết định hành động đi tìm lon rác, đứng yên đợi, hay quay về trạm sạc. Mỗi hành động lại dẫn đến xác suất thay đổi pin (state) và nhận phần thưởng (thu được lon rác hoặc bị sập nguồn) khác nhau.

2. Goals and Rewards (Mục tiêu và Phần thưởng)

Trong RL, mục tiêu của Agent được formalize (chính thức hóa) thông qua một tín hiệu đặc biệt là reward, được truyền từ Environment sang Agent ở mỗi time step ($R_t \in \mathbb{R}$).

Mục tiêu của Agent không phải là ăn phần thưởng lớn nhất ngay lập tức, mà là tối đa hóa tổng reward nhận được trong dài hạn (cumulative reward).

Điều này dẫn tới một quy tắc gọi là Reward hypothesis:

Tất cả những gì ta gọi là "mục tiêu" hay "chủ đích" đều có thể được tính toán bằng việc tối đa hóa giá trị kỳ vọng (expected value) của tổng hợp tín hiệu reward nhận được.

Nếu ta muốn con robot học đi bộ, ta cấp reward cho sự dịch chuyển tịnh tiến lên phía trước. Nếu ta muốn agent giải mê cung, ta cho reward là $-1$ cho mỗi bước đi để thúc ép nó tìm đường ra nhanh nhất có thể. Reward mà ta setup mang hàm ý tổng quát cho bài toán tối ưu mà ta muốn AI giải quyết.

3. Returns and Episodes

Mục tiêu là tối đa hóa cumulative reward trong dài hạn, vậy ta định nghĩa đại lượng đó như thế nào? Trong RL, ta gọi đó là Return (Lợi tức) - ký hiệu là $G_t$.

Cách đơn giản nhất, Return là tổng chuỗi reward từ thời điểm $t$ cho tới kết thúc:

$$G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \dots + R_T$$

Trong đó $T$ là bước cuối cùng (thời điểm kết thúc trò chơi hoặc hoàn thành task). Những bài toán có điểm kết thúc rõ ràng như vậy (thắng/thua một ván cờ, chơi hết màn game,...) được gọi là Episodic tasks (Bài toán có hồi kết). Mỗi chuỗi con độc lập như vậy gọi là một Episode. Mỗi episode kết thúc tại một trạng thái đặc biệt gọi là terminal state.

Nhưng trong thực tế, nhiều agent phải hoạt động liên tục không giới hạn (ví dụ: một robot duy trì hoạt động trong nhà máy, một bộ điều khiển nhiệt độ). Đây gọi là Continuing tasks.

Vấn đề nảy sinh: Nếu bài toán không có hồi kết ($T = \infty$), thì tổng lợi tức $G_t$ có thể tiến tới vô hạn. Toán học không thích điều này. Để giải quyết, ta đưa vào một khái niệm gọi là Discounting (Chiết khấu).

Dựa vào cách tiếp cận này, Agent sẽ tối ưu hóa Expected discounted return:

$$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

Trong đó, $\gamma$ (gamma) là một tham số với $0 \leq \gamma \leq 1$, được gọi là discount rate (tỉ lệ chiết khấu).

Ý nghĩa của Discount rate:

• Nó thể hiện giá trị của phần thưởng theo thời gian: một reward nhận được ở $k$ time steps trong tương lai sẽ chỉ có trọng số là $\gamma^{k-1}$.
• Nếu $\gamma = 0$: Agent sẽ cực kỳ "myopic" (cận thị). Nó chỉ quan tâm tới việc tối đa hóa phần thưởng ngay trước mắt ($R_{t+1}$) mà không thèm đoái hoài gì tới tương lai.
• Khi $\gamma$ tiến gần về $1$: Agent trở nên "nhìn xa trông rộng" hơn, tính toán kỹ lưỡng hơn các phần thưởng ở xa trong tương lai.

Từ công thức trên, ta có thể rút ra một phương trình đệ quy cực kỳ đẹp mắt và dễ tính toán cho các thuật toán sau này:

$$G_t = R_{t+1} + \gamma G_{t+1}$$

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

Đến đây, chúng ta đã set up xong toàn bộ khung xương (framework) của một bài toán Reinforcement Learning thông qua MDP. Bước tiếp theo, chúng ta sẽ xem xét cách mà Agent đánh giá xem một state là "tốt" hay "xấu" - đó chính là Value Functions và phương trình nền tảng Bellman Equations.

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