reinforcement learning

[RL4a] Policy Optimization

I thought I would write about some theory behind Reinforcement Learning, with eligibility traces, contraction mapping, POMDP and so on, but then I realized if I go down that rabbit hole, I would probably never finish this. So here are some practical stuff that people are actually using these days.

Two main approaches in model-free RL are policy-based, where we build a model of the policy function, and value-based, where we learn the value function. For many practical problems, the structure of the (unknown) policy function might be easier to learn than the (unknown) value function, in which case it makes more sense to use policy-based methods. Moreover, with policy-based methods, we will have an explicit policy, which is the ultimate goal of Reinforcement learning to control (the other type being learn-to-predict, more on that some other time). With value-based methods, like DQN, we will need to do an additional inference step to get the optimal policy.

The hybrid of policy-based and value-based is called Actor-Critic methods, which hopefully will be mentioned in another post.

One of the most straightforward approach in policy-based RL is, unsurprisingly, evolutionary algorithms. In this approach, a population of policies is maintained and evolutionized over time. People show that this works pretty well, e.g. for the Tetris game. However, due to the randomness, this is apparently only applied to problems where the number of parameters of the policy function is small.

A big part of policy-based methods, however, is based on Policy Gradient, where an exact estimate of the gradient of the expected future reward can be computed. Roughly speaking, there is an exact formulation for the gradient of the policy, which we can then use to optimize the policy. Since Deep Learning people basically worship gradients (pun intended), this method suites very well and became trendy about 2 years ago.

So, what is it all about? It is based on a very simple trick called Likelihood Ratio.


NIPS 2016

So, NIPS 2016, the record-breaking NIPS with more than 6000 attendees, the massive recruiting event, the densest collection of great men with huge egos, whatever you call it.

I gotta write about this. Maybe several hundreds of people will also write something about NIPS, so I would start with something personal, before going to the usual march through papers and ideas, you know…

One of the cool things about this NIPS is I got to listen directly to the very men who taught me so many things during the last several years. Hearing Nando de Freitas talking on stage, I could easily recall his voice, the accent when he says thee-ta (\theta ) was so familiar. Listening to Rajesh Rao talking, I couldn’t help recalling the joke with the adventurer hat he made in order to “moisturise” his Neuroscience lectures. Sorry professor, nice try, but the joke didn’t quite work.

And of course, Yoshua Bengio with his usual hard-to-be-impressed style (although he hasn’t changed much since last time we talked). Also Alex Graves whose works wowed me so many times.

One of the highlights of the days was Jurgen Schmidhuber, with his deep, machine-generated voice, told a deep joke. The joke goes like this:

Three men were sentenced to death because of the invention of technology that causes mass unemployment in some certain industries. They were a French guy named LeCun, a British guy named Hinton and a German guy named Schmidhuber.

Before the execution, the Death asked them: “Any last word?”
– The French guy said: Je veux … (blah blah, in French, I couldn’t get it)
– The German guy: I want to give a final speech about the history of Deep Learning!
– The British guy: Please shoot me before Schmidhuber gives his goddamn speech!

As some of my friends put it: when he can make a joke about himself, probably he is still mentally healthy (pun intended).


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


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


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.


[RL3a] Reinforcement Learning context

[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

Lại nói tiếp chuyện Học củng cố. Trong các bài trước, ta đã xem xét mô hình Markov Decision Process (MDP) và các phương pháp giải MDP. Ta cũng đã nói qua về hàm Q-function, hàm quan trọng nhất trong MDP, có thể dùng để biểu diễn trạng thái của agent. Vì hàm này quan trọng nên viết lại ra đây:

\displaystyle 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)

Đương nhiên nếu ta biết trước mô hình (ma trận chuyển trạng thái T và hàm reward R), thì mọi chuyện không còn gì để bàn. Tưởng tượng là một agent, được thả vào trong môi trường lạ, agent này sẽ thực hiện một loạt các hành động a, rơi vào các trạng thái s và nhận được reward r. Nói cách khác, agent sẽ chỉ nhận được chuỗi <s_1, a_1, r_1>, <s_2, a_2, r_2>, ... và nhiệm vụ của nó là phải tìm ra policy \pi sao cho tối đa hoá expected reward. Reinforcement Learning, do đó, là thuật toán giúp agent tìm ra policy tối ưu, khi nó quan sát được chuỗi <s,a,r>*.

Có nhiều cách để làm việc này , nhưng nhìn chung có 3 cách sau:


  1. Model-based RL: trong cách này, trước tiên ta phải học được mô hình của MDP từ chuỗi <s,a,r>*, chẳng hạn T có thể là maximum likelihood estimation của các trạng thái, R là expected reward của mỗi trạng thái trong training set. Sau đó dùng các thuật toán trong phần trước để giải MDP và tìm ra policy tối ưu.
    Lưu ý là trong cách làm này, ta phải tìm cách ước lượng MDP.
  2. Value-function-based RL: ta tìm cách học trực tiếp hàm Q-function (nôm na là expected reward của agent khi ở trạng thái s và thực hiện hành động a), sau đó tìm policy tối ưu.
  3. Policy Search: trong cách này, ta trực tiếp tìm policy tối ưu từ training set, thay vì phải mô hình hoá Q-function.

Rõ ràng đi từ 1 đến 3 thì yêu cầu của thuật toán càng ngày càng “khó”, vì rõ ràng trong Policy Search thì rất khó để ước lượng trực tiếp policy tối ưu từ training set. Ta nói rằng Model-based RL thì more “supervised”.

Trong thực tế người ta chủ yếu tập trung vào Model-free RL. Chẳng hạn ta sẽ bàn về TD(\lambda) trong phần sau.

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


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