[Tutorial] Implement các thuật toán Reinforcement Learning - DDPG (Bài 1)

deep-learning
tensorflow
tutorial
machine-learning
openai-gym

#1

I - Lời nói đầu

Bên cạnh sự phát triển của Computer Vision, Natural Language Processing, các thuật toán Reinforcement Learning cũng đạt được những thành tựu đáng ngạc nhiên trong những năm gần đây - nhóm các nhà khoa học thuộc DeepMind tạo AI để chơi game Atari với thuật toán Deep Q-Network (DQN), AlphaGo, AlphaZero chơi thắng nhà vô địch thế giới trong môn cờ vây hay gần đây là AI chơi Dota chiến thắng trong các trận 5v5 với con người.
Các kĩ thuật đằng sau những thành tựu đó là gì và làm sao để implement các thuật toán đó, series này sẽ nói về các thuật toán Reinforcement Learning và cách implement các thuật toán Deep Reinforcement Learning với Tensorflow trên môi trường được cho bởi OpenAIGym. Bài viết này hệ thống lại những gì mình học được trong thời gian qua. Bài viết hơi nhiều toán, nhưng những phép toán rất tự nhiên và không khó, hy vọng các bạn đủ kiên nhẫn, kết quả cuối cùng rất hay.

Mỗi bài trong chuỗi được chia làm 2 phần:

  • Lý thuyết đằng sau các thuật toán.
  • Cách implement một mô hình đơn giản với Tensorflow để giải các bài toán trên OpenAIGym.

Bài viết này dựa trên bài giảng của giáo sư Sergey Levine thuộc đại học UC Berkeley và sách Introduction to Reinforcement Learning của giáo sư Sutton và Barto, các bạn có thể tìm thấy link cho bài giảng tại đây và sách tại đây.

2 - Reinforcement Learning

Reinforcement Learning hay học củng cố/tăng cường, là lĩnh vực liên quan đến việc dạy cho máy (agent) thực hiện tốt một nhiệm vụ (task) bằng cách tương tác với môi trường (environment) thông qua hành động (action) và nhận được phần thưởng (reward). Cách học này rất giống với cách con người học từ môi trường bằng cách thử sai. Lấy ví dụ 1 đứa vào mùa đông đến gần lửa thì thấy ấm, đứa trẻ sẽ có xu hướng đến gần lửa nhiều hơn (vì nhận được phần thưởng là ấm áp), nhưng chạm vào lửa nóng, đứa trẻ sẽ có xu hướng tránh chạm vào lửa (vì bị là bỏng tay).
[ảnh]
Trong ví dụ trên, phần thưởng xuất hiện ngay, việc điều chỉnh hành động là tương đối dễ. Tuy nhiên, trong các tình huống phức tạp hơn khi mà phần thưởng ở xa trong tương lai, điều này trở nên phức tạp hơn. Làm sao để đạt được tổng phần thưởng cao nhất trong suốt cả quá trình? Reinforcement Learning (RL) là các thuật toán để giải bài toán tối ưu này.
Dưới đây là định nghĩa của các thuật ngữ hay xuất hiện trong RL:

  • Environment (môi trường): là không gian mà máy tương tác.
  • Agent (máy): máy quan sát môi trường và sinh ra hành động tương ứng.
  • Policy (chiến thuật): máy sẽ theo chiến thuật như thế nào để đạt được mục đích.
  • Reward (phần thưởng): phần thưởng tương ứng từ môi trường mà máy nhận được khi thực hiện một hành động.
  • State (trạng thái): trạng thái của môi trường mà máy nhận được.
  • Episode (tập): một chuỗi các trạng thái và hành động cho đến trạng thái kết thúc s_1,a_1,s_2,a_2,...s_T, a_T
  • Accumulative Reward (phần thưởng tích lũy): tổng phần thưởng tích lũy từ 1 state đến state cuối cùng. Như vậy, tại state s, agent tương tác với environment với hành động a, dẫn đến state mới s_{t+1} và nhận được reward tương ứng r_{t+1}. Vòng lặp như thế cho đến trạng thái cuối cùng s_T.

Trong phần dưới đây, mình sẽ dùng các thuật ngữ tiếng Anh để các bạn tiện theo dõi thay vì dịch sang tiếng Việt.

2.1 - Ví dụ

Xem ví dụ dưới đây từ openAIGym, environment có tên MountaincontinuousCar-v0, đây cũng là ví dụ trong phần implementation.

  • Goal: mục đích của bài toán là xây dựng policy để điều khiển xe lên đến được chỗ cắm cờ.
  • Environment: dốc và xe chạy trong đó
  • State: trạng thái của xe có 2 dimension, tọa độ của xe theo trục x và vận tốc của xe tại thời điểm đo.
  • Action: Lực được truyền cho xe để điều khiển, lực này không đủ mạnh để đẩy xe 1 lúc lên đến cờ, xe sẽ cần đi qua đi lại 2 bên mặt nghiên để tăng tốc đến chỗ cắm cờ.
  • Reward: với mỗi step mà xe không đến được cờ, agent nhận reward r=-\frac{-a^2}{10}, xe đến được cờ thì nhận reward là 100. Như thế, nếu agent điều khiển xe mà xe không lên được thì sẽ bị phạt.
  • Terminal state: nếu agent lên đến được cờ hoặc là số step vượt quá 998 steps.

3 - Policy Gradient

Trong phần dưới đây để ví dụ sinh động, mình giải quyết 1 bài toán game đơn giản, game Hứng Bia.

Gọi \pi_\theta(a|s) = f(s, \theta) là policy của agent, đó hàm phân bố xác suất của action a tại state s.

Trong game Hứng Bia, giả sử ta có 3 action: qua trái, qua phải, đứng yên. Tương ứng với state s hiện tại (vị trí của thùng hứng, vị trí của bia rơi so với thùng, tốc độ của bia rơi…) ta sẽ có 1 phân bố xác suất của 3 action tương ứng, ví dụ [0.1, 0.3, 0.5]. Tổng xác suất của tất cả các hành động tại state s bằng 1, ta có: \sum_{a}\pi_\theta(a|s) = 1.
Gọi p(s_{t+1}|a_t, s_t) là hàm phân bố xác suất của state tiếp theo khi agent tại state s và thực hiện action a. Gọi \tau = s_1, a_1, s_2, a_2,..., s_T, a_T là chuỗi từ state s_1 đến state s_T. Xác suất xảy ra chuỗi \tau:
p_\theta(\tau) = p_\theta(s_1, a_1, s_2, a_2,...s_T, a_T)= p(s_1)\pi_\theta(a_1|s_1)p(s_2|s_1, a_1)\pi_\theta(a_2|s_2)...p(s_{T}|s_{T-1},a_{T-1})\pi_\theta(a_T|s_T) = p(s_1)\Pi_{t=1}^{t=T}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t)

Chúng ta sẽ thấy phân bố xác suất của state p(s_{t+1}|a_t, s_t) sẽ bị loại bỏ trong các phương trình về sau.

Mục tiêu của reinforcement learning:
Tìm \theta sao cho: \theta^* = \arg\max_\theta E_{\tau\sim p_\theta(\tau)}[r(\tau)] = \arg\max_\theta E_{\tau\sim p_\theta(\tau)}[\sum_t r(a_t, s_t)]
Từ công thức ta có thể thấy: \theta^* là bộ tham số sao cho expectation của accumulative reward từ rất nhiều các mẫu \tau khác nhau có được từ việc thực thi theo policy \pi_\theta là lớn nhất.
Sau khi trải qua N episodes khác nhau ta thu được N mẫu \tau khác nhau. Hàm số mục tiêu của bài toán lúc này: J(\theta) = E_{\tau\sim p_\theta(\tau)}[\sum_t r(a_t, s_t)] = \frac{1}{N} \sum_i\sum_t r(a_t, s_t)
J(\theta) chính là trung bình cộng của accumulative reward của episodes khác nhau.

Chúng ta cũng có thể biểu diễn J(\theta) theo phân bố của xác suất phân bố p_\theta(\tau) như sau: J(\theta) = E_{\tau\sim p_\theta(\tau)}[\sum_t r(a_t, s_t)] = \int p_\theta(\tau) r(\tau) dr

Tiếp tục xem xét gradient của hàm mục tiêu:
\nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau)}[\sum_t r(a_t, s_t)] = \int \nabla_\theta p_\theta(\tau) r(\tau) dr

Mà chúng ta lại có: \nabla_\theta p_\theta(\tau) = p_\theta(\tau) \frac{\nabla_\theta p_\theta(\tau)} {p_\theta(\tau)} = p_\theta(\tau)\nabla_\theta \log p_\theta(\tau) – trick này rất thường xuyên được sử dụng
Do đó: \nabla_\theta J(\theta) = \int p_\theta(\tau) \nabla_\theta \log p_\theta(\tau) r(\tau) dr = E_{\tau\sim p_\theta(\tau)}[\nabla_\theta \log p_\theta(\tau) r(\tau)]

Tiếp tục phân tích hàm \log p_\theta(\tau), như ta đã có ở trên p_\theta(\tau) = p(s_1)\Pi_{t=1}^{t=T}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t), ta có: \log p_\theta(\tau) = \log p(s_1) + \sum_{t=1}^{t=T}\log \pi_\theta(a_t|s_t) + \sum_{t=1}^{t=T}\log p(s_{t+1}|s_t, a_t)

Cuối cùng: \nabla_\theta \log p_\theta(\tau) = \sum_{t=1}^{t=T}\nabla_\theta \log \pi_\theta(a_t|s_t)
Kết quả này rất hay vì đạo hàm theo \theta của hàm \log p_\theta(\tau) đã không còn phụ thuộc vào phân bố xác suất chuyển của state p(s_{t+1}|a_t, s_t), nó chỉ phụ thuộc vào phân bố xác suất của action a_i chúng ta thực hiện trên s_i.

Gradient của hàm mục tiêu lúc này: \nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau)}[\nabla_\theta \log p_\theta(\tau) r(\tau)] = E_{\tau\sim p_\theta(\tau)}[\sum_{t=1}^{t=T}\nabla_\theta \log\pi_\theta(a_t|s_t)\sum_{t=1}^{t=T} r(a_t, s_t)]

Tương tự, sau khi trải qua N episodes, expectation của hàm gradient này là: \nabla_\theta J(\theta) = \frac{1}{N}\sum_{i=1}^{N}(\sum_{t=1}^{t=T}\nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}))(\sum_{t=1}^{t=T} r(a_{i,t}, s_{i,t}))

Cuối cùng, chúng ta update \theta như dùng gradient ascent: \theta \leftarrow \theta + \nabla_\theta J(\theta).

4 - REINFORCE algorithm

Tổng hợp các kết quả trên ta có thuật toán REINFORCE như dưới đây:

  1. Lấy 1 tập N chuỗi {\tau^i} dựa theo policy \pi_\theta
  2. Tính gradient: \nabla_\theta J(\theta) = \frac{1}{N}\sum_{i=1}^{N}(\sum_{t=1}^{t=T}\nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}))(\sum_{t=1}^{t=T} r(a_{i,t}, s_{i,t}))
  3. Update \theta \leftarrow \theta + \nabla_\theta J(\theta)

Bây giờ hãy dừng lại để xem xét gradient của phương trình mục tiêu. Viết ở dạng đỡ rối mắt hơn ta có: \nabla_\theta J(\theta) = \frac{1}{N}\sum_{i=1}^{N}\nabla_\theta \log \pi_\theta(\tau_i)r(\tau_i)
Đây chính là maximum likelihood estimation MLE tích với accumulative reward. Việc tối ưu hàm mục tiêu cũng đồng nghĩa với việc tăng xác suất để đi theo chuỗi \tau cho accumulative reward cao.

5 - Định nghĩa thêm 1 số khái niệm mới

V^\pi(s): accumulative reward mong đợi tại state s nếu đi theo policy \pi.
Q^\pi(s,a): accumulative reward mong đợi nếu thực hiện action a tại state s nếu đi theo policy \pi.
Quan hệ giữa V^\pi(s)Q^\pi(s,a): V^\pi(s) = \sum_{a \in A}\pi_\theta(s,a)Q^\pi(s,a) - điều này là hợp lý vì \pi_\theta(s,a) là xác suất thực hiện action a tại s.
Ta cũng có như sau:
V^\pi(s_t) = E_\pi[G_t | S=s_t]
Q^\pi(s_t,a_t) = E_\pi[G_t|S=s_t, A=a_t]
Trong đó: G_t=\sum^{\infty}_{k=0}\gamma^kR_{k+t+1}: tổng tất cả các reward nhận được kể từ state s_t đến tương lai, với đại lượng \gamma gọi là discount factor 0 < \gamma < 1. Càng xa hiện tại, reward càng bị discount nhiều, agent quan tâm nhiều hơn đến reward ở gần hơn là ở xa.

5.1 - Bellman Equations

Từ công thức ở trên, ta có:
V^\pi(s_t) = E_\pi[G_t|S=s_t] = E_\pi[\sum^{\infty}_{k=0}\gamma^kR_{k+t+1}|S=s_t]
= E_\pi[\sum^{\infty}_{k=0}\gamma^kR_{k+t+1}|S=s_t] = E_\pi[\sum^{\infty}_{k=0}\gamma^kR_{k+t+1}|S=s_t]
Lấy reward R_{t+1} nhận được khi chuyển từ state s_t sang s_{t+1} ra ngoài dấu \sum, ta được:
E_\pi[R_{t+1} + \gamma\sum^{\infty}_{k=0}\gamma^kR_{k+t+2}|S=s_t] = E_\pi[R_{t+1}|S=s_t] + \gamma E_\pi[\sum^{\infty}_{k=0}\gamma^kR_{k+t+2}|S=s_t]
Khai triển expected value của 2 cụm ở trên ta có: E_\pi[R_{t+1}|S=s_t]=\sum_a \pi(s_t,a) \sum_{s_{t+1}} p(s_{t+1}|s_t, a)R(s_{t+1}|s_t, a)
Và:
\gamma E_\pi[\sum^{\infty}_{k=0}\gamma^kR_{k+t+2}|S=s_t] = \sum_a \pi(s_t,a) \sum_{s_{t+1}} p(s_{t+1}|s_t, a)\gamma E_\pi[\sum^\infty_{k=0} \gamma^k R_{t+k+2} | S = s_{t+1}]
Ta có:
V^\pi(s_t) = \sum_a \pi(s_t,a) \sum_{s_{t+1}} p(s_{t+1}|s_t, a)\Big[R(s_{t+1}|s_t, a) + \gamma E_\pi[\sum^\infty_{k=0} \gamma^k R_{t+k+2} | S = s_{t+1} ]\Big]
Để ý rằng: E_\pi[\sum^\infty_{k=0} \gamma^k R_{t+k+2} | S = s_{t+1}] = V^\pi(s_{t+1})

Cuối cùng ta có:
V^\pi(s_t) = \sum_a \pi(s_t,a) \sum_{s_{t+1}} p(s_{t+1}|s_t, a)\Big[R(s_{t+1}|s_t, a) + \gamma V^\pi(s_{t+1})\Big]
Tương tự với:
Q^\pi(s_t, a_t) = \sum_{s_{t+1}} p(s_{t+1}|s_t, a)\Big[R(s_{t+1}|s_t, a) + \gamma \sum_{a_{t+1}} \pi(s_{t+1}, a_{t+1}) Q^\pi (s_{t+1}, a_{t+1}) \Big]
Mà theo quan hệ giữa V^\piQ^\pi ở trên, thì ta lại có: \sum_{a_{t+1}} \pi(s_{t+1}, a_{t+1}) Q^\pi (s_{t+1}, a_{t+1}) = V^\pi(s_{t+1}), do đó:
Q^\pi(s_t, a_t) = \sum_{s_{t+1}} p(s_{t+1}|s_t, a_t)\Big[R(s_{t+1}|s_t, a_t) + \gamma V^\pi(s_{t+1}) \Big]

Tất cả những biến đổi ở trên cho thấy ta có thể biểu diễn giá trị của Q^\piV^\pi tại state s_t với state s_{t+1}. Như vậy, nếu biết được giá trị tại state s_{t+1}, ta có thể dễ dàng tính toán được giá trị tại s_t. Tóm gọn thì ta có 2 phương trình sau:
V^\pi(s_t) = \sum_a \pi(s_t,a) \sum_{s_{t+1}} p(s_{t+1}|s_t, a)\Big[R(s_{t+1}|s_t, a) + \gamma V^\pi(s_{t+1})\Big]
Q^\pi(s_t, a_t) = \sum_{s_{t+1}} p(s_{t+1}|s_t, a_t)\Big[R(s_{t+1}|s_t, a_t) + \gamma V^\pi(s_{t+1}) \Big]

Trở lại với gradient hàm mục tiêu, bây giờ ta có: \nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau), a\sim\pi_\theta}[\nabla_\theta \log\pi_\theta(a|s)Q^\pi(s,a)]

6 - Advantage (lợi thế)

\nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau), a\sim\pi_\theta}[\nabla_\theta \log\pi_\theta(a|s)Q^\pi(s,a)]
Gradient của hàm mục tiêu cho thấy việc tăng khả năng thực hiện action a nếu nhận được Q^\pi(s,a) cao. Giả sử agent ở tại state s, việc ở tại state s là đã có lợi cho agent rồi, thực hiện action a nào cũng cho ra giá trị Q^\pi(s,a) cao thì ta không thể phân tách (discriminate) các action a với nhau và từ đó không biết được action a nào là tối ưu. Do đó ta cần có 1 baseline để so sánh các giá trị Q^\pi(s,a).
Như trong phần 5, ta có V^\pi(s) là expectation của accumulative reward tại state s, không quan trọng tại s agent thực hiện action gì, chúng ta mong đợi 1 accumulative reward là V^\pi(s). Do đó, 1 action a_m được đánh giá là tệ nếu như Q^\pi(s,a_m) < V^\pi(s) và 1 action a_n được đánh giá là tốt nếu như Q^\pi(s,a_n) > V^\pi(s). Từ đây ta có được 1 baseline để so sánh Q^\pi(s,a) đó là V^\pi(s). Gradient của objective function bây giờ có thể viết lại được như sau:
\nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau), a\sim\pi_\theta}[\nabla_\theta \log\pi_\theta(a|s)(Q^\pi(s,a)-V^\pi(s))]

Nếu Q^\pi(s,a)-V^\pi(s) < 0, 2 gradient ngược dấu với nhau, tối ưu hàm mục tiêu sẽ làm giảm gradient của việc thực thi hành động a tại s.

Ta gọi A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s) là Advantage của action a tại state s.

7 - Stochastic Actor-Critic

Stochastic Actor (ngẫu nhiên Actor) ý chỉ policy \pi_\theta(a|s) là một hàm phân phối xác suất của action a tại s. Ta gọi Stochastic Actor để phân biệt với Deterministic Actor (hay Deterministic Policy) mang ý chỉ policy không còn là một hàm phân phối xác suất của các action a tại s, mà dưới s ta chỉ thực hiện chính xác một action nhất định mà thôi a=\mu_\theta(s), hay nói cách khác xác suất thực hiện a tại s bây giờ là 1.

Xem xét gradient của hàm mục tiêu mà ta đã có ở phần trên: \nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau), a\sim \pi_\theta}[\nabla_\theta \log\pi_\theta(a|s)(Q^\pi(s,a)-V^\pi(s))]
Từ Bellman Equation ở trên ta có quan hệ giữa Q^\piV^\pi, lúc này hàm mục tiêu trở thành:
\nabla_\theta J(\theta) = E_{\tau\sim p_\theta(\tau), a\sim \pi_\theta}[\nabla_\theta \log\pi_\theta(a|s)(R + \gamma V^\pi(s_{t+1})- V^\pi(s))]

Hàm mục tiêu phụ thuộc vào 2 thứ: policy \pi_\theta và value function V^\pi. Giả sử ta có một hàm xấp xỉ cho V^\pi(s)V_\phi(s) phụ thuộc vào bộ tham số \phi.

Ta gọi hàm xấp xỉ cho policy \pi_\theta là Actor và hàm xấp xỉ cho value function V_\phi là Critic.

8 - Actor-Critic Algorithm

Từ thuật toán REINFORCE, bây giờ chúng ta sử dụng thêm hàm xấp xỉ cho value function V_\phi, thay đổi một chút ta có như sau:

Batch Actor-Critic:

  1. Lấy 1 chuỗi \tau đến terminal state dựa theo policy \pi_\theta
  2. Fit V_\phi với y = \sum^{T}_i r_i
  3. Tính A(s_t,a_t) = r(s_t, a_t) + \gamma V_\phi(s_{t+1}) - V_\phi(s_{t})
  4. Tính \nabla_\theta J(\theta) = \sum_i \nabla \log \pi_\theta (a_i|s_i) A^\pi (s_i, a_i)
  5. Update \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)

Mà ta có ở trên, ta có thể biểu diễn V_\phi(s) = r + V_\phi(s') theo Bellman Equation, do đó ta có thể update model mà chỉ cần 1 step về phía trước.
Online Actor-Critic:

  1. Dựa theo policy \pi_\theta, thực hiện 1 action a \sim \pi_\theta(a|s) để có (s,a,s',r)
  2. Fit V_\phi (s) với r + V_\phi(s')
  3. Tính A(s_t,a_t) = r(s_t, a_t) + \gamma V_\phi(s_{t+1}) - V_\phi(s_{t})
  4. Tính \nabla_\theta J(\theta) = \sum_i \nabla \log \pi_\theta (a_i|s_i) A (s_i, a_i)
  5. Update \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)

Như vậy, chúng ta cùng lúc update cả 2 hàm xấp xỉ V_\phi\pi_\theta.

9 - Từ Stochastic Actor-Critic tới Q-Learning

Xét một policy như sau:
\pi'(a_t|s_t) = 1 nếu a_t = \arg \max_{a_t} A^\pi(s_t, a_t)
Policy \pi' này là một Deterministic Policy: cho trước một policy \pi và giả sử ta biết được Advantage của các action tại state s_t dưới policy \pi, ta luôn chọn action cho ra giá trị Advantage lớn nhất tại state s_t đó, probability của action đó là 1, tất cả các action khác tại s_t bằng 0.
Policy \pi' sẽ luôn tốt hơn hoặc ít nhất là tương đương với policy \pi. Một policy được đánh giá là tương đương hay tốt hơn khi ta có: V^\pi(s) \leq V^{\pi'} (s) \forall s \in S : với mọi state s trong miền state S, giá trị return V^\pi(s) luôn nhỏ hơn hoặc bằng giá trị return V^{\pi'} (s).
Ví dụ ta có như sau: tại state s, ta có 4 cách đi sang state s' ứng với 4 action và ứng với A^\pi_1, A^\pi_2, A^\pi_3, A^\pi_4. Kể từ state s', ta lại đi theo policy \pi. Từ s sang s', nếu chọn action theo stochastic policy \pi, Expected Advantage là \sum_{a \in A} p(a)A^\pi_a, lượng này chắc chắn nhỏ hơn \max_a A^\pi_a

.

Như vậy, với một policy \pi, ta luôn có thể áp dụng policy \pi' trên đó để được một policy ít nhất là bằng hoặc tốt hơn.
Như vậy, ta có thuật toán bây giờ có thể viết như sau:

  1. Đánh giá A^\pi(s,a) với các action a khác nhau
  2. Tối ưu \pi \leftarrow \pi'

Mà đánh giá A^\pi(s,a) thì cũng tương đương đánh giá Q^\pi(s,a)A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s) = r(s,a) + \gamma V^\pi(s') - V^\pi(s), mà lượng V(s) thì lại không đổi giữa các action a tại state s.
Như vậy, thuật toán trở thành:

  1. Đánh giá Q^\pi(s,a) \leftarrow r(s,a) + \gamma V^\pi(s') với các action a khác nhau
  2. Tối ưu \pi \leftarrow \pi' : chọn ra action cho A cao nhất, hay cũng chính là Q

Đến đây thì thực sự ta không cần quan tâm đến policy nữa, mà bước 2 có thể viết lại thành:

  1. Đánh giá Q^\pi(s,a) \leftarrow r(s,a) + \gamma V^\pi(s') với các action a khác nhau
  2. V^\pi(s) \leftarrow \max_a Q\pi(s,a)

Nếu xử dụng một hàm xấp xỉ cho V_\phi(s), ta có thuật toán như sau:

  1. Đánh giá V^\pi(s) \leftarrow max_a \big(r(s,a) + \gamma V^\pi(s')\big)
  2. \phi \leftarrow \arg min_\phi (V^\pi(s) - V_\phi(s))^2

Thuật toán này không ổn, ở bước 1 ta cần có reward r(s, a) ứng với mỗi action a khác nhau, như vậy ta cần nhiều simulation tại 1 state s. Ta có thể làm tương tự với Q(s,a) thay vì V(s).

  1. Đánh giá y_i \leftarrow r(s,a_i) + \gamma max_{a'} Q_\phi(s', a')
  2. \phi \leftarrow \arg min_\phi (Q_\phi(s, a_i) - y_i)^2 (*)

Đây chính là thuật toán Q-Learning. Để ý rằng, reward r ở trên không phụ thuộc vào state transition - phụ thuộc vào policy \pi dùng để sinh ra sample, nên ta chỉ cần sample (s, a, r, s') là có thể cải thiện được policy mà không cần biết nó được sinh ra từ policy nào. Do đó, thuật toán này được gọi là off-policy. Sau này, chúng ta sẽ có các thuật toán on-policy, các thuật toán on-policy thì phải dựa vào sample được sinh ra tại policy hiện tại để có thể cải thiện policy mới.

Ta có thuật toán Online Q-Learning như sau:

  1. Thực hiện action a để có (s, a, s', r)
  2. Đánh giá y_i \leftarrow r(s,a_i) + \gamma max_{a'} Q_\phi(s', a')
  3. \phi \leftarrow \phi - \alpha \frac{dQ_\phi}{d\phi}(s,a) (Q_\phi(s, a_i) - y_i)

Các bạn để ý bước 3, đó có phải là gradient descent như ở trên chỗ mình đánh dấu (*) không? Không, thực ra chúng ta đã lờ đi phần thay đổi của y_i theo \phi (y_i cũng phụ thuộc vào \phi). Như vậy, mỗi khi update \phi theo thuật toán này, thì giá trị của mục tiêu y_i cũng bị thay đổi theo! Mục tiêu luôn thay đổi khi ta cố gắng tiến gần lại nó, điều này làm cho thuật toán trở nên không ổn định.
Để giải quyết điều này, ta cần một hàm xấp xỉ khác gọi là target network, khác với train network chúng ta vẫn chạy. Target network sẽ được giữ cố định để tính y và update dần dần.
Một vấn đề khác là các sample sinh ra liên tục nên nó rất liên quan (correlation) với nhau. Thuật toán trên cũng giống như Supervised Learning - ta map Q-value với giá trị mục tiêu, ta muốn các sample là độc lập (i.i.d) với nhau. Để phá vỡ correlation giữa các sample, ta có thể dùng 1 experience buffer: 1 list chứa rất nhiều sample (s,a,r,s') khác nhau, và ta chọn ngẫu nhiên 1 batch từ buffer để train thuật toán.

Tóm lại, để thuật toán ổn định và hội tụ, ta cần:

  1. Hàm target network riêng biệt, gọi đó là Q_{\phi'}.
  2. Experience buffer.

Thuật toán bây giờ được viết như sau:

  1. Thực hiện action a_i để có (s_i, a_i, s_i', r_i) và bỏ nó vào buffer.
  2. Lấy ngẫu nhiên 1 batch N sample từ buffer (s_i, a_i, s_i', r_i).
  3. Đánh giá y_i \leftarrow r(s,a_i) + \gamma max_{a'} Q_{\phi'}(s', a') (dùng target network ở đây)
  4. \phi \leftarrow \phi - \alpha \frac{1}{N}\sum_i^N \frac{dQ_\phi}{d\phi}(s,a_i) (Q_\phi(s, a_i) - y_i)
  5. Update target network \phi' \leftarrow (1-\tau)\phi' + \tau \phi (sử dụng \tau \% của train network mới để update target network)

Thuật toán này chính là Deep Q-Network (DQN).

10 - Từ Deep Q-Network đến Deep Deterministic Policy Gradient

Thuật toán DQN đã thành công trong việc sấp xỉ Q-value, nhưng có một hạn chế ở bước 3: chúng ta cần đánh giá Q_{\phi'} với tất cả các action khác nhau để chọn ra Q lớn nhất. Với discrete action space như các game, khi mà action chỉ là các nút bấm lên xuống qua lại, số lượng action là hữu hạn, điều này có thể thực hiện được. Tuy nhiên, với continuous action space, ví dụ action có thể trong khoảng từ 0 đến 1, ta cần có một cách tiếp cận khác.

Cách ta có thể nghĩ đến đó là tìm cách phân nhỏ action space, phân nhỏ continuous space thành các khoảng nhỏ, ví dụ như từ 0 đến 1, ta có thể phân ra làm 5 đến 10 khoảng giá trị có thể rơi vào. Một cách khác đó là sample ngẫu nhiên các action khác nhau trong khoảng cho phép với cùng state s và chọn ra giá trị Q(s,a) lớn nhất (không khả thi khi phải thực hiện nhiều simulation tại state s).

Deep Deterministic Policy Gradient (DDPG) có một cách tiếp cận tinh tế như sau, để ý rằng: max_{a} Q_{\phi}(s, a) = Q_\phi(s, \arg max_a Q_\phi(s,a)).
Bây giờ, nếu như ta có thêm một hàm xấp xỉ \mu_\theta(s) = \arg max_a Q_\phi(s,a), bây giờ ta tìm bộ số \theta sao cho: \theta \leftarrow \arg max_\theta Q_\phi(s,\mu_\theta(s)). Phép tối ưu này xem xét sự thay đổi của Q_\phi theo biến \theta. Ta có thể tính được sự thay đổi này dựa trên chain rule như sau: \frac{dQ_\phi}{d\theta} = \frac{dQ_\phi}{d\mu} \frac{d\mu}{d\theta}.

Để ý rằng, \mu_\theta(s) là một Deterministic Policy, chính vì vậy phương pháp này gọi là Deep Deterministic Policy Gradient.

Thuật toán DDPG như sau:

  1. Thực hiện action a_i để có (s_i, a_i, s_i', r_i) và bỏ nó vào buffer.
  2. Lấy ngẫu nhiên 1 batch N sample từ buffer (s_i, a_i, s_i', r_i).
  3. Đánh giá y_i \leftarrow r(s,a_i) + \gamma Q_{\phi'}(s', \mu_{\theta'}(s')) (dùng cả policy và Q target network ở đây)
  4. \phi \leftarrow \phi - \alpha \frac{1}{N}\sum_i^N \frac{dQ_\phi}{d\phi}(s,a_i) (Q_\phi(s, a_i) - y_i)
  5. \theta \leftarrow \theta - \beta \frac{1}{N}\sum_i^N \frac{d\mu_\theta}{d\theta}(s) \frac{dQ_\phi}{da}(s, a_i)
  6. Update target network \phi' \leftarrow (1-\tau)\phi' + \tau \phi\theta' \leftarrow (1-\tau)\theta' + \tau \theta

11 - Implement DDPG với OpenAI

Như vậy, ta đã đi xong phần lý thuyết. trong phần này, mình sẽ giới thiệu cách dùng OpenAI và implement DDPG đơn giản để giải bài toán Pendulum-v0. Mình sẽ tối giản mọi thứ có thể (buffer, exploring policy…) để thuật toán trở nên dễ đọc nhất. Trước khi vào phần này, các bạn hãy install tensorflowgym với 2 câu lệnh sau trên terminal:
pip install tensorflow
pip install gym

11.1 - Làm quen với OpenAI

env = gym.make('Pendulum-v0') # tạo một environment
env.reset() #  reset lại environment, hàm reset() trả về state đầu tiên của environment
episodes = 10 # ta chạy 10 episodes
steps = 1000 # mỗi episodes ta chạy nhiều nhất 100 steps
for ep in range(episodes):
    state = env.reset()
    for step in range(steps):
        env.render() # gọi hàm render() để sinh ra animation, mình hay tắt đi vì nó gây crash trên window
        action = env.action_space.sample() # lấy 1 action ngẫu nhiên trong action space
        next_state, reward, done, _ = env.step(action) # thực thi action đó trên environment, giá trị trả về là state tiếp theo s', reward nhận được, và done (đã kết thúc episodes hay chưa)

Mục tiêu của ta là tạo một agent để thực hiện action thay cho phần env.action_space.sample() phù hợp để đạt được mục đích.

11.2 - Tạo buffer

Buffer là 1 list các sample (s, a, r, s')

env = gym.make('Pendulum-v0') 
env.reset() 
episodes = 10 
steps = 1000 

BUFFER_SIZE = 1000000 # độ lớn của buffer
buffer = []
for ep in range(episodes):
    state = env.reset()
    for step in range(steps):
        env.render()
        action = env.action_space.sample() 
        next_state, reward, done, _ = env.step(action) 
        
        if len(buffer) >= BUFFER_SIZE: 
             buffer.pop(0)  # nếu buffer đầy thì pop phần tử đầu tiên ra      
        buffer.append([state, action, np.array([reward]), np.array([done]).astype(int), next_state]) #thêm experience mới
        state = next_state #sau khi lưu vào buffer xong thì ta gán state là next_state

11.3 - Tạo Agent

11.3.1 - Định nghĩa structure cho graph của Q Q(s,a) và Policy \mu(s)

def build_graph_Q(state, action):
    with tf.variable_scope('layer0'):
        layer_size = 128
        state0 = tf.layers.dense(state,layer_size)
        action0 = tf.layers.dense(action, layer_size, use_bias=False) 
        layer = action0 + state0 # layer này là 1 Affine Transformation cúa state và action Wt*s + Wt*a + b
        layer = tf.nn.relu(layer)
    
    with tf.variable_scope('layer1'):
        layer_size = 128
        layer = tf.layers.dense(layer, layer_size)
        layer = tf.nn.relu(layer)
        
    with tf.variable_scope('layer2'):
        layer_size = 1
        layer = tf.layers.dense(layer, layer_size)

    return layer

def build_graph_policy(state):
    with tf.variable_scope('layer0'):
        layer_size = 128
        layer = tf.layers.dense(state, layer_size)
        layer = tf.nn.relu(layer)
    
    with tf.variable_scope('layer1'):
        layer_size = 128
        layer = tf.layers.dense(layer, layer_size)
        layer = tf.nn.relu(layer)
        
    with tf.variable_scope('layer2'):
        layer_size = 1
        layer = tf.layers.dense(layer, layer_size)
        layer = tf.nn.tanh(layer)
        layer = tf.multiply(layer, 2) #action space từ -2 đến 2 nên ta dùng activation function tanh() sau đó nhân với 2
    return layer

11.3.2 - Tạo placeholder cho state, next_state, action, reward, terminal:

observations_ph = tf.placeholder(tf.float32, shape=(None, 3), name='observation')
next_observations_ph = tf.placeholder(tf.float32, shape=(None, 3), name='next_observation')
rewards_ph = tf.placeholder(tf.float32, shape=(None, 1), name='reward')
actions_ph = tf.placeholder(tf.float32, shape=(None, 1), name='action')
terminals_ph = tf.placeholder(tf.float32, shape=(None, 1), name='terminal')

11.3.3 - Tạo graph Policy, Q và Target Q

with tf.variable_scope('Actor/eval'):
    policy = build_graph_policy(observations_ph)
with tf.variable_scope('Actor/target'):
    target_policy = build_graph_policy(observations_ph)

with tf.variable_scope('Critic/eval'):
    q = build_graph_Q(observations_ph, actions_ph) 
with tf.variable_scope('Critic/eval', reuse=True):
    q_policy = build_graph_Q(observations_ph, policy)

with tf.variable_scope('Critic/target'):
    target_q = build_graph_Q(next_observations_ph, target_policy)

policy_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='Actor/eval')
target_policy_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='Actor/target')
q_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='Critic/eval')
target_q_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='Critic/target')

11.3.3 - Tạo các operation để update Policy, Q và Target Q

TAU = 0.01
GAMMA = 0.9
LR_Critic = 0.001
LR_Actor = 0.0001

q_target = tf.stop_gradient(rewards_ph + (1-terminals_ph)*GAMMA*target_q)

q_error = 0.5*tf.reduce_mean((q_target - q)**2)
q_train_ops = tf.train.AdamOptimizer(LR_Critic).minimize(loss=q_error, var_list=q_params)

policy_loss = - tf.reduce_mean(q_policy)
policy_train_ops = tf.train.AdamOptimizer(LR_Actor).minimize(loss=policy_loss, var_list=policy_params)

update_policy_ops = [tf.assign(tpp, (1-TAU)*tpp + TAU*pp) for tpp, pp in zip(target_policy_params, policy_params)]
update_q_ops = [tf.assign(tqp, (1-TAU)*tqp + TAU*qp) for tqp, qp in zip(target_q_params, q_params)]

def action_respond(sess, obs):
    action = sess.run(policy, feed_dict={observations_ph: obs})[0]
    return action

def init_training(sess):
    sess.run(update_policy_ops)
    sess.run(update_q_ops)

def get_feed_dict(batch):
    feed_dict = {observations_ph: batch['observations'],
                 actions_ph: batch['actions'],
                 next_observations_ph: batch['next_observations'],
                 rewards_ph: batch['rewards'],
                 terminals_ph: batch['terminals']}
    return feed_dict
    
def do_training(sess, batch):
    feed_dict = get_feed_dict(batch)
    sess.run([q_train_ops, policy_train_ops], feed_dict)
    sess.run(update_policy_ops)
    sess.run(update_q_ops) 

Mình sẽ cập nhật thêm comment code trong thời gian tới. Mình rất mong nhận được feedback từ mọi người.

12. Linh tinh

Trong trường hợp mình muốn optimize 1 lúc nhiều mục đích khác nhau, như ví dụ xe ở trên, vừa muốn xe lên đỉnh vừa muốn xe đi nhanh, thay vì có 1 reward, ta có 1 vector các reward. Ta có thể xây dựng thuật toán để cùng lúc thỏa mãn nhiều objective function được không? Nó lợi thế gì so với combined method, có lợi thế gì so với weighted objective value trong objective function không?


Hỏi về VinAI Residence Program
[07/13/2019 22:19] Em có đọc bài tutori. . .
#2

“…gần đây là AI chơi Dota chiến thắng đội mạnh nhất thế giới.” cái này sai rồi ông bạn ơi. OpenAI mới chỉ thắng team có các pro players hợp lại thôi, chưa đủ trình đánh với các team chuyên nghiệp đâu.


#4

Cám ơn bạn, mình đọc không kĩ.
Mình rất thích project Dota này vì các agent trong game phối hợp với nhau rất tốt chỉ bằng một tham số hợp tác giữa các agent.


#5

Chúc mừng Gonaton với bài viết rất tốt. Một số lỗi nhỏ:

– Xác suất xảy ra chuỗi p(tau) trong phần 3: p(s_2) cần sửa thành p(s_2 | s_1, a_1), và p(s_T) sửa thành p(s_{T+1} | s_T, a_T).

– Hàm log trong Latex cần sửa thành \log\ và hàm argmax sửa thành \argmax

– đạo hàm theo \theta của hàm log p-\theta (\tau) đã không còn phụ thuộc vào phân bố xác suất chuyển… cần chua thêm là chỉ đúng đối với stochastic policies.

Thanks and looking forward to reading your coming posts on deepRL :wink:


#6

Gonaton: add friend FB mình để giao lưu thêm về chuyên môn nhé :blush: fb.com/curiousAI


#7

Thanks bạn @CuriousAI, comment của bạn động viên mình rất nhiều để theo đuổi series trong thời gian tới. Mình đã sửa lại những chỗ sai. Mình cũng thử \argmax nhưng không được. Hiện tại mình đang đến đoạn stochastic policies. Trường hợp Deterministic Policy như Q-learning hay DDPG thì sự xuất hiện của probability of state transition như thế nào bạn nhỉ? Mình đang nghĩ Deterministic Policy là một edge case của Stochastic Policy nên nếu điều đó đúng với Stochastic Policy thì cũng đúng với Deterministic Policy.


#8

Kết bạn fb vs mình đi @CuriousAI


#9

Kết bạn với mình đi @Gonaton


#10

Với stochastic policies, action a được sampled từ distribution \pi(a | s;\theta) nên transition p(s' | s,a) chỉ gián tiếp (implicitly) phụ thuộc tham số \theta. Còn với deterministic policies a = \pi(s;\theta) nên ta có direct dependencies p(s' | s,\pi(s;\theta)). Derivations cho DPG do đó khá involved, xem Appendix B. Proof of Theorem 1 của ICML’14 paper.

Btw, a sampled from distribution \pi(a|s;\theta) = \pi_\theta(a|s) trong Latex dùng ký kiệu \sim: a\sim \pi_\theta(a|s). Tương tự: \tau\sim p_\theta(\tau) thay vì \tau\tilde{}p_\theta(\tau) và nhiều chỗ khác có dùng sampling \sim.


#11

Còn lỗi \argmax ko parsed đúng: có thể xài \arg\max_x f(x) hoặc \text{argmax}_x f(x).


#12

Thanks anh, đúng là ddpg nó involved thật. Hôm em loay hoay mãi gõ ko ra tilde nên để thế, thanks a nhé em chỉnh lại đây


#13

Bài viết hay quá huhu. Rất xúc tích dễ hiểu, hy vọng a sẽ viết thêm.


#14

Bài quá lâu rồi không có hoạt động mới.

Nhưng mình cũng muốn học hỏi về, làm sao để đánh giá (Metric) cho một mô hình Reinforcement Learning thế nào là tốt thế nào là chưa tốt?