[RL3b] Temporal Difference Learning – intuition

[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
[RL3a] Reinforcement Learning context
[RL3b] Temporal Difference Learning – intuition

Như đã nói trong bài trước, ta sẽ tập trung vào Model-free RL, trong đó ta muốn học trực tiếp giá trị của các trạng thái V(s) từ tập huấn luyện <s, a, r>^*.

Cụ thể, tập huấn luyện sẽ gồm nhiều episodes, mỗi episode là một chuỗi s_1 \overset{r_1}{\longrightarrow} s_2 \overset{r_2}{\longrightarrow} s_3 \longrightarrow ... \longrightarrow s_F mà agent thực hiện cho đến khi kết thúc cuộc đời của nó. Chẳng hạn nếu là chơi cờ thì tập huấn luyện sẽ gồm nhiều trận đấu, mỗi trận là một chuỗi các nước đi. Từ tập huấn luyện này, ta tìm cách ước lượng V(s).

Tại sao lại ước lượng V(s), khi trong bài trước ta nói rằng Model-free RL tìm cách ước lượng giá trị Q(s, a)? Nhắc lại rằng ta có thể tính Q(s, a) từ V(s), R(s, a)T(s, a, s'), như đã nói trong bài này, mà R(s, a)T(s, a, s') có thể ước lượng một cách đơn giản từ tập huấn luyện (chẳng hạn dùng maximum likelihood), nên một khi có V(s) ta hoàn toàn có thể tính Q(s, a) nếu muốn. Tuy nhiên mục tiêu cuối cùng của RL vẫn là tìm ra policy tối ưu, chứ không phải tìm V(s) hay Q(s,a), mà từ V(s) vẫn có thể dùng \arg\max để tìm policy tối ưu, thành ra V(s) hay Q(s, a) cũng không còn quan trọng nữa.

Mọi chuyện sẽ dễ dàng hơn khi ta xem ví dụ sau. Cho một MDP với mô hình chuyển trạng thái T và hàm reward R như sau:

markov_states

Mô hình này có 6 trạng thái. Khi chuyển từ s_1 sang s_3 thì reward nhận được là +1, nghĩa là R(s_1, a) = +1. Tương tự như vậy cho các trạng thái khác. s_F là trạng thái cuối cùng, trò chơi kết thúc khi agent đi đến trạng thái này.

Đặc biệt từ trạng thái s_3, agent có thể tới s_4 với xác suất 0.9, và tới s_5 với xác suất 0.1, nghĩa là T(s_3, a, s_4) = 0.9T(s_3, a, s_5) = 0.1. Trong cả hai trường hợp, reward đều là 0.

Giờ ta thả 5 agent vào mô hình này, quan sát được các chuỗi trạng thái như sau:

1. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
2. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_5 \overset{+10}{\longrightarrow} s_F
3. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
4. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
5. s_2 \overset{+2}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_5 \overset{+10}{\longrightarrow} s_F

Giả sử rằng ta không biết mô hình MDP như trong hình, mà chỉ biết 5 episodes như trên. Bài toán RL là ước lượng mô hình MDP từ các episodes (training set) này.

Ở đây có 2 chuyện ta có thể làm:

  1. Ước lượng mô hình MDP (tức là ước lượng TR)
  2. Ước lượng V(s)

Ta sẽ xem lần lượt 2 chuyện này.

1. Ước lượng mô hình MDP

Cách dễ nhất để làm chuyện này là dùng maximum likelihood. Chẳng hạn nhìn vào 5 episodes trên ta thấy từ s_1 lúc nào cũng đi tới s_3 với reward bằng +1, nên theo maximum likelihood thì T(s_1, a, s_3) = 1R(s_1, a) = +1.

Một trường hợp thú vị hơn là từ s_3 ta có 3 lần đi đến s_4, và 2 lần đi đến s_5. Vậy suy ra T(s_3, a, s_4) = 3/5 = 0.6T(s_3, a, s_5) = 2/5 = 0.4.

Có bạn sẽ bảo: ủa vậy sai rồi, vì theo mô hình như trong sơ đồ trên, thật ra T(s_3, a, s_4) = 0.9, T(s_3, a, s_5) = 0.1.

Đương nhiên là sai, vì ta ước lượng tham số chỉ dựa vào 5 episodes. Nếu có nhiều dữ liệu hơn, có thể ước lượng của ta sẽ gần hơn với mô hình MDP đã cho.

Như vậy ta đã thấy việc ước lượng T và R từ chuỗi <s, a, s'>^* là rất đơn giản. Nhưng như ta đã nói, ta sẽ tập trung vào model-free RL, nên phần này xem như là làm chơi cho biết. Ta tập trung chủ yếu vào phần sau.

2. Ước lượng V(s)

Nhắc lại rằng theo định nghĩa \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).   (1)

Khi áp dụng vào trong mỗi episode trong training set, vì ta quan sát được các trạng thái cho đến cuối cùng, nên không còn hàm \max nữa. Chẳng hạn với chuỗi đầu tiên s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F thì ta có:

V(s_F) = 0 (giả sử vậy đi)
V(s_4) = R(s_4, a) + \gamma T(s_4, a, s_F) V(s_F) = 1
V(s_3) = R(s_3, a) + \gamma T(s_3, a, s_4) V(s_4) = 0 + \gamma 0.9
V(s_1) = R(s_1, a) + \gamma T(s_1, a, s_3) V(s_3) = 1 + \gamma\left(\gamma 0.9\right) = 1 + 0.9 \gamma^2

Nói chung cứ như vậy ta có thể tính được V(s) cho mỗi episode, tuỳ vào giá trị của \gamma.

Tuy nhiên để ý rằng trong tính toán ở trên ta đã “cheat” bằng cách dùng kiến thức ta đã biết từ mô hình MDP, rằng T(s_3, a, s_4) = 0.9. Trong thực tế khi học, ta chưa biết giá trị của T, thành ra một cách “ngây thơ” nhất, ta sẽ giả sử T(s, a, s') = 1 cho mọi s và s’. Như vậy các phép tính ở trên sẽ thành:

V(s_F) = 0
V(s_4) = R(s_4, a) + \gamma T(s_4, a, s_F) V(s_F) = 1
V(s_3) = R(s_3, a) + \gamma T(s_3, a, s_4) V(s_4) = 0 + \gamma
V(s_1) = R(s_1, a) + \gamma T(s_1, a, s_3) V(s_3) = 1 + \gamma^2

Trở lại với tập huấn luyện:

1. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
2. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_5 \overset{+10}{\longrightarrow} s_F
3. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
4. s_1 \overset{+1}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_4 \overset{+1}{\longrightarrow} s_F
5. s_2 \overset{+2}{\longrightarrow} s_3 \overset{+0}{\longrightarrow} s_5 \overset{+10}{\longrightarrow} s_F

Để đơn giản hơn nữa, ta sẽ giả sử luôn là \gamma = 1. Như vậy có thể thấy trong episode số 1, ta có V_1(s_1) = 2, trong episode số 2, ta có V_2(s_1) = 11, trong episode số 3, ta có V_3(s_1) = 2 v.v… Giả sử ta mới chỉ quan sát được 3 episode đầu tiên, thì rõ ràng với maximum likelihood, ta sẽ có V(s_1) = (2 + 11 + 2)/3 = 5.

Với episode số 4, ta có V_4(s_1) = 2. Ta dễ dàng ước lượng giá trị mới của V(s_1)V(s_1) = (3 * 5 + 2) / 4 = 17/4 = 4.25

Có bạn lại bảo: ủa vậy sai rồi, với \gamma=1, dùng công thức huyền thoại \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), ta sẽ tính được V(s_1) = 2.9 (lưu ý V(s_3) = 0 + (0.9 * 1 + 0.1 * 10) = 1.9).

Đương nhiên là sai, vì ta mới chỉ quan sát được 4 episodes.

Một cách tổng quát hơn, gọi V_{T}\left(s\right) là giá trị của V(s) sau khi quan sát episode thứ T, R_T(s) là reward mà agent nhận được cho trạng thái s trong episode T. Như trong ví dụ trên, khi T=4 thì V_{T-1}(s_1) = V_3(s_1) = 5, V_T(s_1) = V_4(s_1) = 4.25R_T(s_1) = R_4(s_1) = 2.

Dùng toán phổ thông, ta có thể tính V_T(s) từ V_{T-1}(s) như sau:

\displaystyle V_T(s) = \frac{(T-1)V_{T-1}(s) + R_T(s)}{T}
\displaystyle V_T(s) = \frac{T-1}{T}V_{T-1}(s) + \frac{1}{T}R_T(s)
\displaystyle V_T(s) = V_{T-1}(s) + \alpha_T\left(R_T(s) - V_{T-1}(s)\right)    (2)

với \alpha_T = \frac{1}{T} gọi là learning rate, và rõ ràng là \alpha_T càng nhỏ khi T càng lớn (càng học nhiều episode thì \alpha_T càng nhỏ).

Công thức (2) là tinh thần chung của Temporal Difference Learning. Rõ ràng ta cập nhật V_T(s) với mỗi episode, dựa vào “độ lỗi” tính bởi \left(R_T(s) - V_{T-1}(s)\right) , được weight bằng learning rate. Độ lỗi này thực chất là sự khác biệt giữa reward trong episode mới và ước lượng hiện tại của V(s), do đó đây được gọi là Temporal Difference Learning.

Ta sẽ phát biểu Temporal Difference Learning một cách hình thức trong bài sau.

Advertisements

One comment

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