bellman

[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.

(more…)

Advertisements

[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?

(more…)