TD Qlearning

Temporal-Difference Q-learning

Introduction

• Sarsa estimates the action values of a given policy $\pi$
• Q-learning estimates the optimal action values

Algorithm

• $\text{Sarsa}$

$$\begin{array}{rl}{q}_{k+1}(s_t,a_t)& =q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-\left[r_{t+1}+\gamma q_k(s_{t+1},a_{t+1})\right]\right],\\ q_{k+1}(s,a)& =q_k(s,a),\forall (s,a)\ne (s_t,a_t).\end{array}$$

• $\text{Q-learning}$

$$\begin{array}{rl}{q}_{k+1}(s_t,a_t)& =q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-\left[r_{t+1}+\gamma \underset{a\in \mathcal{A}}{\max }{q}_k(s_{t+1},a)\right]\right],\\ q_{k+1}(s,a)& =q_k(s,a),\forall (s,a)\ne (s_t,a_t).\end{array}$$

• the TD target in Q-learning is $r_{t+1}+\gamma {\max }_{a\in \mathcal{A}}{q}_k(s_{t+1},a)$
• the TD target in Sarsa is $r_{t+1}+\gamma q_k(s_{t+1},a_{t+1})$

What does Q-learning do mathematically?

It aims to solve Bellman optimality equation in terms of action values:

$$q(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }q(S_{t+1},a^{\prime })\right|S_t=s,A_t=a],\forall s,a.$$

Off-policy vs. On-policy

在TD learning的task中一般有两个policy：

1. behavior policy：用来生成experience samples
2. target policy：用来不断更新towards optimal policy

那么下面就可以定义on-policy和off-policy的概念：

• $\text{On-policy}$: behavior policy和target policy是一样的
• $\text{Off-policy}$: behavior policy和target policy是不一样的

Advantages of off-policy learning

It can search for the optimal policy on the experience samples generated by any other policy(behavior policy).

举例说明就是：考虑这样一种情况：我们的behavior policy是比较随机的（说好听点叫 exploratory ，比较倾向于去探索的），但是我们的target policy是比较稳定的（说好听点叫 exploitative ，比较倾向于去利用已有的信息）

• 如果这个时候用on-policy的方法去更新的话很可能会导致我们的policy不能继续优化了（因为用target policy生成的experience是比较稳定单一的结果）
• 但是如果用off-policy的方法去更新的话（此时是用behavior policy去生成丰富多样的experience），我们就仍可以继续去搜索最优的policy。

Sarsa and MC are on-policy

• Sarsa aims to evaluate a given policy $\pi$ by solving $$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })\right|s,a],\forall s,a.$$
• MC aims to evaluate a given policy $\pi$ by solving $$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t|S_t=s,A_t=a\right],\forall s.$$ where $G_t=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{T-t-1}{R}_T$ is the return from time $t$.
• $\pi$ is the behavior policy and the target policy in both cases.

Q-learning is off-policy

• Q-learning aims to solve the BOE $$q(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }q(S_{t+1},a^{\prime })\right|S_t=s,A_t=a],\forall s,a.$$
• the algorithm is $$q_{k+1}(s_t,a_t)=q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-\left[r_{t+1}+\gamma \underset{a\in \mathcal{A}}{\max }{q}_k(s_{t+1},a)\right]\right].$$ which requires $(s_t,a_t,r_{t+1},s_{t+1})$.
• the behavior policy is the one for generating $a_t$ in $s_t$, which can be any policy.

Implementation

Version 1

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Policy Search by Q-learning(on-policy version) with }\epsilon \text{-Greedy}\\ & \text{Initialization: }\text{Initial policy }{\pi }_0(a|s)\text{, value function }q(s,a)\text{ for all }(s,a).\text{ Step size }\alpha \in (0,1].\\ & \text{For each episode, do:}\\ & \text{Initialize state }{s}_0.\\ & \text{Select action }{a}_0\text{ using }{\pi }_0(s_0).\\ & \text{While }{s}_t\text{ is not the target state, do:}\\ & \text{Execute }{a}_t\text{, observe }{r}_{t+1},s_{t+1}.\\ & \text{Select }{a}_{t+1}\text{ using }{\pi }_t(s_{t+1}).\\ & \text{Update }q(s_t,a_t):\\ & q(s_t,a_t)\leftarrow q(s_t,a_t)-\alpha \left[q(s_t,a_t)-\left[r_{t+1}+\gamma \underset{a}{\max }q(s_{t+1},a)\right]\right]\\ & \text{Update policy for }{s}_t:\\ & {\pi }_{t+1}(a|s_t)\leftarrow \{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{if }a=\arg {\max }_{a^{\prime }}q(s_t,a^{\prime })\\ \frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{otherwise}\end{array}\\ & s_t\leftarrow s_{t+1},a_t\leftarrow a_{t+1}\end{array}}$$

Version 2

off-policy的优点其实是包括了exploration在里面，我们用 exploratory(random) 的behavior policy ${\pi }_b$去生成experience samples即可，这样我们就可以把上面的算法的$\epsilon$-greedy的部分去掉，因为我们已经有了exploration的部分了。

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Optimal Policy Search by Q-learning(off-policy version)}\\ & \text{Initialization: }q(s,a),\alpha \in (0,1].\\ & \text{For each episode generated by }{\pi }_b,\text{do:}\\ & \text{For }t=0,1,2,\dots \text{ in the episode, do:}\\ & \text{Observe experience: }(s_t,a_t,r_{t+1},s_{t+1})\\ & \text{Update }q(s_t,a_t):\\ & q(s_t,a_t)\leftarrow q(s_t,a_t)-\alpha \left[q(s_t,a_t)-\left(r_{t+1}+\gamma \underset{a}{\max }q(s_{t+1},a)\right)\right]\\ & \text{Update target policy }{\pi }_T\text{ for }{s}_t:\\ & {\pi }_T(a|s_t)\leftarrow \{\begin{array}{ll}1,& \text{if }a=\arg {\max }_{a^{\prime }}q(s_t,a^{\prime })\\ 0,& \text{otherwise}\end{array}\end{array}}$$

Version 3

上面的算法例子非常清晰的包括了policy evaluation和policy improvement两个部分，但实际上我们发现压根就不需要把policy improvement部分写出来，因为在policy evaluation部分我们就直接得用greedy的方法去更新q值了（即只要有Q table的存在我们就可以不断更新下去），而且上面的版本的${\pi }_b$并没有写出是如何得到的，实际上在Sutton的书里6.5小结给出了更清晰的算法描述（用上一步得到的Q的greedy作为${\pi }_b$，这样再加一个$\epsilon$-greedy decay我们就可以实现模型的从一开始的 exploration 慢慢转向 exploitation），因此再将其改动一下：

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Q-learning(off-policy TD control)}\\ & \text{Initialization: }q(s,a),\alpha \in (0,1],\epsilon \in (0,1],\text{small decay rate }\phi \in (0,1].\\ & \text{For each episode, do:}\\ & \text{Initialize state }{s}_0.\\ & \text{Select action }{a}_0\text{ using }\epsilon \text{-greedy}\text{ w.r.t. }q(s_0,a).\\ & \text{While }{s}_t\text{ is not the target state, do:}\\ & \text{Execute }{a}_t\text{, observe }{r}_{t+1},s_{t+1}.\\ & \text{Select }{a}_{t+1}\text{ using }\epsilon \text{-greedy}\text{ w.r.t. }q(s_{t+1},a).\\ & \text{Update }q(s_t,a_t):\\ & q(s_t,a_t)\leftarrow q(s_t,a_t)-\alpha \left[q(s_t,a_t)-\left(r_{t+1}+\gamma \underset{a}{\max }q(s_{t+1},a)\right)\right]\\ & \epsilon \leftarrow \epsilon \times \phi \end{array}}$$

解释

w.r.t. = with respect to，这里的意思是说我们在选择action的时候是根据Q值来选择的（或者翻译成关于）。这里如果用数学来表示就是：

$$\pi (a|s)=\{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|},& \text{if }a=\arg {\max }_{a^{\prime }}q(s,a^{\prime })\\ \frac{\epsilon }{|\mathcal{A}(s)|},& \text{otherwise}\end{array}$$

这里的$\pi$就是我们的behavior policy，select action就是指从${\pi }_b(s_{\text{current}})$中采样即可。

这样做有几个优点：

1. we have relatively exploration(random) behavior policy: last step’s Q
2. we also have relatively exploitation(greedy) target Policy: current step’s Q
3. 通过$\epsilon$-greedy decay（随着$\phi$的decay，$\phi \to 0$），我们可以逐渐从exploration转向exploitation，实现了一个丝滑的转换
4. 我们现在依然是off-policy的，因为我们的behavior policy和target policy是不一样的，依然保持之前的优点
5. 但其实也可以一直保持一个比较小的$\epsilon$（或者迭代到最后不不让其收敛到0，加一个小小的bias就行），这样就可以一直保持exploration的能力（${\pi }_b$就是$\epsilon$-greedy sample的Q，而${\pi }_T$就是$\arg \max$的Q）