[RL3c] TD(lambda) rule

[RL3a] Reinforcement Learning context
[RL3b] Temporal Difference Learning – intuition
[RL3c] TD(lambda) rule

Trong bài trước, ta đã đi đến công thức cập nhật giá trị của trạng thái như sau:

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

trong đó R_T(s) là reward tức thời (immediate reward) của trạng thái s tại thời điểm T. Trong thực tế, tại thời điểm T, agent thực hiện hành động s để tiến tới trạng thái s’ và thu được reward là r: s \overset{+r}{\longrightarrow} s'. Do đó R_T(s) là:

R_T(s) = r + \gamma V_{T-1}(s').

Nhận xét này dẫn ta đến thuật toán TD(\lambda) như sau:

Episode T
  for all s: e(s) = 0;  V_T(s) = V_{T-1}(s)
  After step t: s_{t-1}\overset{r_t}{\longrightarrow} s_t
    e(s_{t-1}) = e(s_{t-1}) + 1
    for all s:
      \displaystyle V_T(s) = V_T(s) + \alpha_T\left[r_t + \gamma V_{T-1}(s_t) - V_{T-1}(s_{t-1})\right]e(s)
      e(s) = \lambda\gamma e(s)

Ở trung tâm thuật toán này là phương trình cập nhật như trên. \gamma là discounted factor của MDP, \lambda là hằng số của thuật toán TD(\lambda), có giá trị trong khoảng [0, 1]. \alpha_T = \frac{1}{T} là learning rate.

Như vậy sử dụng thuật toán này, ta có thể ước lượng giá trị của tất cả các trạng thái, chỉ dựa vào các episodes trong tập huấn luyện. Thuật toán này được cài đặt ở đây.

\lambda là một tham số thú vị. Ta có thể thấy điều này nếu khai triển công thức ở trên theo thời gian (unroll):

E_1: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\right]

E_2: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + \gamma r_{t+2} + \gamma^2 V(s_{t+2}) - V(s_t)\right]

E_\infty: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + ... + \gamma^{k-1} r_{t+k} + \gamma^k V(s_{t+k}) + ... - V(s_t)\right]

Việc khai triển này cũng tương tự như cách mà ta khai triển phương trình Bellman trong bài trước. Hơn nữa, cứ sau mỗi bước cập nhật, ta lại tăng e(s) lên một lượng \lambda. Thành ra có thể hiểu \lambda thể hiện mức độ tin tưởng của ta vào giá trị của s tại thời điểm gần nhất (\lambda = 0) hay rất xa trong quá khứ (\lambda = 1). Bất kì giá trị nào của \lambda nằm giữa 0 và 1 là sự trade-off giữa 2 thái cực trên. Thông thường giá trị của \lambda trong khoảng 0.5-0.7.

Ghi chú về learning rate

Nhớ rằng ta có công thức cập nhật \displaystyle V_T(s) = V_{T-1}(s) + \alpha_T\left(R_T(s) - V_{T-1}(s)\right), và định nghĩa learning rate \alpha_T = \frac{1}{T}. Với learning rate định nghĩa như trên thì ta đảm bảo rằng \lim_{T \rightarrow \infty} V_T(s) = V(s), nghĩa là V_T(s) hội tụ về giá trị “thật” V(s) khi có nhiều episode.

Rõ ràng tính chất hội tụ trên là vô cùng quan trọng, nếu không thì toàn bộ những lí thuyết ta học đều vô nghĩa.

Nhưng hoá ra không phải chỉ có mỗi learning rate \frac{1}{T} là thoả mãn yêu cầu trên. Thực tế thì bất kì learning rate nào thoả mãn 2 điều kiện sau:

\displaystyle \sum_T \alpha_T = \infty
\displaystyle \sum_T \alpha_T^2 < \infty

thì đều khiến cho chuỗi V_T(s) hội tụ.

Thành ra \frac{1}{T}\frac{1}{T^{2/3}} thoả điều kiện trên, trong khi \frac{1}{100}\frac{1}{T^2} hay \frac{1}{T^{1/2}} thì không thoả.

Nếu có dịp ta sẽ trở lại với tính chất này, bằng khái niệm contraction mapping.

 

Advertisements

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