[RL2b] Markov Decision Process – 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

Lại nói tiếp về MDP. Trong bài trước, ta đã thấy utility của một chuỗi trạng thái được định nghĩa là discounted reward \displaystyle U\left(s_0, s_1, ...\right) = \sum_{t=0}^\infty \gamma^t R\left(s_t\right).

Nhắc lại rằng trong ngữ cảnh của MDP, thì ta cần tìm 1 policy \pi sao cho nó tối đa hoá discounted reward của agent. Còn nhớ \pi là một hàm theo trạng thái s, theo đó \pi\left(s\right) trả về một hành động mà agent có thể thực hiện tại trạng thái s. Mặt khác ta biết MDP là một quá trình xác suất, nên với mỗi hành động \pi\left(s\right) mà agent thực hiện, trạng thái kế tiếp của nó được xác định dựa trên xác suất chuyển trạng thái trong transition model.

Nói tóm lại, ngay cả khi cho trước một policy \pi, thì discounted reward của agent tuân theo policy đó, kí hiệu \displaystyle \sum_{t=0}^\infty \gamma^t R\left(s_t\right) \vert \pi, cũng là một biến ngẫu nhiên.

Do đó, mục tiêu của MDP là tìm policy tối ưu \pi^* sao cho nó tối đa hoá kì vọng của biến ngẫu nhiên nói trên:

\displaystyle \pi^* = \arg\max_\pi E\left[\sum_{t=0}^\infty \gamma^t R\left(s_t\right) \vert \pi\right]

Cho trước một policy \pi, ta cũng có thể định nghĩa utility của một trạng thái s như sau:

\displaystyle U^\pi\left(s\right) = E \left[\sum_{t=0}^\infty \gamma^t R\left(s_t\right) \vert \pi, s_0 = s\right]

Nhớ rằng trong phần trước, ta chỉ có thể định nghĩa utility của một chuỗi trạng thái U\left(s_0, s_1, ...\right). Nhưng khi cho trước một policy \pi, thì ta có thể định nghĩa utility cho một trạng thái bất kì s chính bằng kì vọng của tổng discounted reward khi đi theo policy \pi và bắt đầu từ trạng thái s. Ta cần phép tính kì vọng vì nhớ rằng cho trước policy \pi thì tổng discounted reward là một biến ngẫu nhiên.

Cần phân biệt rằng U\left(s\right)delayed reward tại trạng thái s khi đi theo một policy nào đó, khác hẳn với immediate reward R\left(s\right).

Còn một thành phần nữa của MDP mà ta chưa nhắc đến là transition model T\left(s, a, s'\right). Ta có thể “nhét” transition model vào bằng cách tính policy bắt đầu từ một trạng thái cho trước s, theo đó policy tối ưu bắt đầu từ s sẽ là:

\displaystyle \pi^*\left(s\right) = \arg\max_a \sum_{s'} T\left(s, a, s'\right)U\left(s'\right)

Ta dùng U\left(s\right) để kí hiệu utility tại s khi đi theo policy tối ưu: U\left(s\right) = U^{\pi^*}\left(s\right).

Và ta có đủ  gia vị để viết công thức quan trọng nhất của MDP – công thức Bellman:

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

Công thức này chứa đựng toàn bộ tinh thần của MDP, trong đó có tập trạng thái, tập hành động, reward R, transition T,… Policy tối ưu là policy cực đại utility này tại mỗi trạng thái, nói cách khác nếu giải được phương trình này thì ta có thể giải được MDP.

Trong bài tiếp theo ta sẽ xem một số phương pháp kinh điển để giải phương trình này.

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