[RL2d] Bellman Equations revisited

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

Trong bài trước, ta có nói Bellman equation là như thế này:

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

Tuy nhiên ta cũng có thể viết lại nó thành thế này:

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

Hàm này gọi là Value function, kí hiệu là V. Thật ra thì nó biểu diễn cùng 1 thứ so với phương trình ở trên, nhưng ta buộc luôn cả action a vào trong hàm reward R(s, a), nghĩa là thay vì nhận được reward tại mỗi state s như trong phương trình U(s), ta sẽ nhận reward sau khi thực hiện action a khi đang đứng tại state s. Vì sự thay đổi này nên hàm max phải được đem ra ngoài cùng. Suy nghĩ thêm một chút thì ta thấy rằng U(s) hay V(s) thật ra đều chỉ cùng 1 thứ, là “giá trị” của mỗi trạng thái s trong dài hạn.

Thật ra thì cuộc đời của một agent trong MDP có thể biểu diễn là một chuỗi các hành động:

s1 –> a1 –> R(s1, a1) —> s2 –> a2 –> R(s2, a2) —> s3 –>a3 –> R(s3, a3) —>….

Nghĩa là agent rơi vào trạng thái s1, thực hiện hành động a1, nhận được reward R(s1, a1) rồi rơi vào trạng thái s2, cứ như vậy lặp lại.

Người Pháp có câu Métro, boulot, dodo, chính là để chỉ cuộc đời kiểu này.

Trong MDP, chuỗi như vậy hàm ý là thật ra ta có thể có nhiều cách viết để biểu diễn trạng thái của agent. Nói cách khác, có nhiều cách khác nhau để viết phương trình Bellman. Điều này dễ thấy nhất nếu ta unroll biểu thức của V(s) theo thời gian:

\displaystyle V\left(s_1\right) = \max_{a_1} \left(R\left(s_1, a_1\right) + \gamma\sum_{s_2}T\left(s_1,a_1,s_2\right)\max_{a_2} \left(R\left(s_2, a_2\right) + \gamma\sum_{s_3}T\left(s_2,a_2,s_3\right)...\right)\right)

Đây là một chuỗi đệ quy, nên tuỳ vào ta “ngắt” chỗ nào thì sẽ được một công thức tương ứng. Chẳng hạn nếu ta ngắt ở \max_a\left(R\left(s_1, a_1\right) ...\right) thì sẽ được công thức V(s) như trên, nhưng nếu ta ngắt ở R\left(s_1, a_1\right)... thì sẽ được:

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

Hàm này rất quan trọng trong RL, gọi là Q-function (Q for quality). Hàm này rất đẹp, vì ta có thể tối đa hoá được Q(s,a) dựa vào Q(s', a') mà không cần biết chính xác giá trị của hàm R và T. Trong khi đó với cách viết của V(s) thì ta phải biết R và T mới có thể tối đa hoá được V(s).

Tiếp tục trong chuỗi Métro, boulot, dodo của MDP (thật ra thay vì gọi MDP, chắc có thể gọi chuỗi này là MBD), ta còn có thể viết thêm một hàm khác như sau:

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

Ý tưởng chủ đạo là ta có một chuỗi vô hạn s, a, r, s, a, r… và việc ta cắt chuỗi này ở chỗ nào để viết thành công thức thật ra không quan trọng về mặt ý nghĩa, nhưng trong một số tình huống, việc cắt ở chỗ nào sẽ cho ta một số lợi thế nhất định khi làm toán.

Và để khỏi thắc mắc, chỉ có 3 cách khác nhau để cắt chuỗi này, gồm có V(s), Q(s,a)C(s,a). Ta còn có thể viết thành bảng, biểu diễn một trong ba biểu thức này bằng một biểu thức khác như sau:

Screen Shot 2016-08-15 at 17.57.44

Đây là bài cuối về Bellman equations (thề!). Từ bài sau sẽ là Học củng cố đàng hoàng.

 

Advertisements

3 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