[RL2c] Markov Decision Process – Solving Bellman equation

[RL1] Markov Decision process – Introduction
[RL2a] Markov Decision Process – Discounted Reward
[RL2b] Markov Decision Process – Bellman equation
[RL2c] Markov Decision Process – Solving Bellman equation
[RL3] Q-Learning
[RL4] Game Theory – overview

Trong bài trước, ta dừng lại ở phương trình Bellman:

U\left(s\right) = R\left(s\right) + \gamma \max_a \sum_{s'} T\left(s, a, s'\right) U\left(s'\right)

và nói rằng phương trình này chứa đựng tất cả các thành phần của MDP. Quả thật nếu ta giải được phương trình trên, ta sẽ biết utility cho mỗi trạng thái (tuân theo policy tối ưu), và từ đó có thể lần ngược lại policy tối ưu, nghĩa là giải được MDP.

Vậy làm sao để giải được phương trình này?

1. Value Iteration

Nhận xét rằng nếu gọi n là số lượng trạng thái, thì phương trình Bellman thực chất là một hệ gồm n phương trình với n ẩn (là utility tại mỗi trạng thái U\left(s\right)). Tuy nhiên do sự có mặt của hàm max nên hệ này không có closed-form solution. Giống như các tình huống khác, ta sẽ giải quyết bằng một thuật toán lặp:

  1. Khởi tạo utility tại mỗi trạng thái \hat{U}_{0}\left(s\right)
  2. Cập nhật utility dựa trên các trạng thái kề nó (trong transition model T): \hat{U}_{t+1}\left(s\right) = R\left(s\right) + \gamma \max_a \sum_{s'} T\left(s, a, s'\right)\hat{U}_{t}\left(s'\right)
  3. Lặp bước 2 cho đến khi hội tụ

Thuật toán này gọi là Value Iteration, và cũng được dùng trong thực tế. Mặc dù khởi tạo utility một cách ngẫu nhiên, nhưng sau rất nhiều vòng lặp thì thông tin về utility tại mỗi trạng thái R\left(s\right) sẽ “đè” lên U\left(s\right), làm cho U\left(s\right) càng ngày càng đúng.

Bạn nào không quen thì có thể thấy thắc mắc làm sao thuật toán lởm khởm này chạy được, nhưng well, có người chứng minh là nó sẽ hội tụ rồi.

Sau khi có utility của các trạng thái, thì với mỗi trạng thái, ta có thể tìm một policy hợp lí, từ đó giải được MDP.

2. Policy Iteration

 Thay vì tìm utility, ta có thể tìm trực tiếp policy tối ưu bằng thuật toán như sau:

  1. Khởi tạo policy \pi_0 ngẫu nhiên
  2. Tính utility U_t = U^{\pi_t} dựa trên \pi_t
  3. Cập nhật policy \pi_{t+1} = \arg\max_a \sum_{s'} T\left(s, a, s'\right) U_t\left(s'\right)

Trong bước 3 ta sẽ phải tính utility của các trạng thái, như sau:

U_t\left(s\right) = R\left(s\right) + \gamma \sum_{s'} T\left(s, \pi_t(s), s'\right) U_t\left(s'\right)

đây là hệ n phương trình tuyến tính với n ẩn, nên có thể giải bằng các phương pháp truyền thống.

Mình có implement 2 thuật toán này ở đây, tuy nhiên hình như implementation của policy iterations bị sai. Bạn nào có thời gian sửa giùm thì sẽ vô cùng cảm tạ.

Vậy là hết mấy bài cơ bản lằng nhằng về MDP. Ta sẽ nghiên cứu tiếp Reinforcement Learning đàng hoàng trong các bài sau.

Advertisements

6 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s