目录
- 引入
- TD learing of state values
- TD learing of action values Sarsa
- TD learing of action values Expected Sarsa
- TD learing of action values n-step Sarsa
- TD learing of optimal action values：Q-learning
- a unified point of view
引入
这三个例子是层层递进的，都可以用\(RM\)算法去解决
TD learing of state values
这个算法是求解给定策略\(\pi\)的\(state \; value\)，为什么求解\(state \; value\)其实就又回到了之前的\(PE\)，有了\(state \; value\)就可进行\(policy \; improvement\)
\(TD \; learning\)是指的一类强化学习算法。
\(TD \; learning\)也是一种\(model \; free\)的算法他也是依赖于\(data\)
\(TD \;\)算法需要的数据有\((s_0,r_1,s_1,...,s_t,r_{t+1},s_{t+1},...)\),表示成另一种形式就是\((s_t,r_{t+1},s_{t+1})\)这些数据的生成依赖于给定的策略\(\pi\)
下面是\(TD\)算法的形式
\[v_{t+1}(s_t)=v_t(s_t)-\alpha_t (s_t)\left[ v_t(s_t) - [r_{t+1}+\gamma v_t(s_{t+1})] \right] \]\[v_{t+1}(s) = v_t(s), \forall s \neq s_t \]\(where \; t = 0,1,2,...\)，这里\(v_t(s_t)\)是\(state \; value \; v_{\pi}(s_t)\)的估计
\(\alpha_t(s_t)\)是状态\(s_t\)在\(t\)时刻的学习率
- 在\(t\)时刻，只有被\(visited\)的\(state \; s_t\)被更新，而其他未被访问的\(states \; s \neq s_t\)保持不变
- 一般第二个式子很多地方都会省略，但这里写出来更清楚
- \(TD \; target \;\):\(\bar{v_t}r_{t+1} +\gamma v(s_{t+1})\)实际上希望\(v_t\)朝着\(TD \; target\)的方向去改进
- \(TD \; error \;\)\(\delta_t = v(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})] = v(s_t) - \bar{v_t}\)
为什么把\(\bar{v_t}\)叫做\(TD \; target ？\)
这是因为算法是要将\(v(s_t)\)朝着\(\bar{v_t}\)的方向改进,也就是说下一个时刻 \(v(s_t)\)离\(\bar{v_t}\)会更接近,所以\(\bar{v_t}\)叫做\(TD \; target\)
\[v_{t+1}(s_t)=v_t(s_t)-\alpha_t(s_t)[v_t(s_t)-\bar{v_t}] \]对上面的方程进行等价变形
\[v_{t+1}(s_t) - \bar{v_t}=v_t(s_t)-\bar{v_t}-\alpha_t(s_t)[v_t(s_t) - \bar{v_t}] \]\[v_{t+1}(s_t)- \bar{v_t} = [1-\alpha_t(s_t)][v_t(s_t) - \bar{v_t}] \]上面的方程在描述一件事情：\(v_t\)和\(\bar{v_t}\)之间差的变化，左边是\(t+1\)时刻的，右边是\(t\)时刻的.
对上面方程两边求绝对值.
\[\mid v_{t+1}(s_t)- \bar{v_t} \mid = \mid [1-\alpha_t(s_t)]\mid \mid [v_t(s_t) - \bar{v_t}] \mid \]因为\(\alpha_t(s_t)\)是一个比较小的正数,所以\(0<1-\alpha_t(s_t)<1\)
所以就有：
\[\mid v_{t+1}(s_t)- \bar{v_t} \mid \le \mid [v_t(s_t) - \bar{v_t}] \mid \]上面的式子就说明在下一个时刻\(t+1\),\(v(s_t)\)离\(\bar{v_t}\)的距离更近了，所以这个算法就是把\(v_t(s_t)\)朝着\(\bar{v_t}\)的方向改进.
如何理解\(TD \; error\)
\[\delta_t = v(s_t) - [r_{t+1}+\gamma v(s_{t+1})] \]- 描述在两个时刻上面的\(difference\)
- 描述\(v_{\pi}和v_{t}\)之间的误差，也就是说当\(v_t=v_{\pi}\)时\(\delta_t=0\),反过来说当\(\delta_t\neq0\)时，\(v_t \neq v_{\pi}\)
上面的\(TD\)算法仅仅能用来估计\(state \; value\),不能直接估计\(action \; value\)，同时也不能找到\(optimal \; policies\)
TD learing of action values Sarsa
\(Sarsa\)算法及其变形在做的事情是给定一个策略能够估计出来一个\(action \; value\)，这也是\(policy \; evaluation \; (PE)\)的过程，然后再结合\(policy \; improvement \; (PE)\)就可以找到最优策略.
\(First\),给定一个\(policy \; \pi\)去估计\(action \; value\)
假设我们有一些\(experience \; \{(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\}_t\)
有了上面的\(experience\)，我们就可以进行算法了
\[q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-\alpha_t(s_t, a_t)[q_t(s_t, a_t)-[r_{t+1}+\gamma q_{t}(s_{t+1}, a_{t+1})]] \]\[q_{t+1}(s,a)=q_{t}(s,a), \forall(s,a) \neq(s_t,a_t) \]\(where \; t=0,1,2,...\)
- \(q_t(s_t,a_t)\)是\(q_{\pi}(s_t,a_t)\)的一个估计
- \(\alpha_t(s_t,a_t)\)是依赖于\((s_t,a_t)\)的学习率
\(sarsa\)算法是\(state \; action \; reward \; state \; action \;\)的首字母的缩写
\(sarsa\)算法和上面的\(TD \; learning\)基本上是一摸一样的，只不过是将对状态的估计，变成了对动作\((action \; value)\)的估计
\(sarsa\)实际上也是在求解一个贝尔曼公式，只不过这个贝尔曼公式的形式和\(TD \; learning\)中的贝尔曼公式的形式不同
\[q_{\pi}(s,a)=\mathbb{E}[R+\gamma q_{\pi}(S^{'}, A^{'}|s,a)], \forall s,a \]和之前使用\(state \; value\)不同的是，这个贝尔曼期望方程是使用\(action \; value\)来表示的,刻画了不同的\(action \; value\)之间的关系.
上面算法只是对\(action \; value\)进行求解，为了找到最优策略，还需要进行\(policy \; improvement(PE)\)
实际上\(Sarsa\)算法通常就指的是将\(Sarsa\)和\(policy \; improvement \; step\)
注意上面\(policy \; improvement\)是采用的之前内容中的\(\epsilon-gready\)算法
关于传统的\(Policy \; iteration\)和广义的\(GPI\)
TD learing of action values Expected Sarsa
这个算法和下面的\(n-step \; sarsa\)算法实际上是没有那么重要的，但是从一个经典算法出发,然后去推广改进,这种思路对于做研究来说是非常常见的
相比于原始的\(sarsa\)，需要计算期望，也就需要更大的计算量，但是随机性减少了
TD learing of action values n-step Sarsa
\(n-step \; Sarsa\)包含了\(Sarsa\)和\(Monte \; Carlo \; learning\)两种方法
先复习一下\(action \; value\)的定义
\[q_{\pi}(s,a)=\mathbb{E}[G_t \mid S_t = s, A_t = a] \]\(discounted \; return\)的写法有很多种形式
\(Sarsa \leftarrow G_t^{(1)} = R_{t+1}+ \gamma q_{\pi}(S_{t+1}+A_{t+1})\)
\[\leftarrow G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 q_{\pi}(S_{t+2}+A_{t+2}) \]\[n-step \; Sarsa \leftarrow G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ...+\gamma^n q_{\pi}(S_{t+n}+A_{t+n}) \]\[MC \leftarrow G_t^{\infty} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}+... \]
- \(n-step \; sarsa\)所需要的数据既不像\(sarsa\)那样只需要前面5个\((s_t, a_t,r_{t+1},s_{t+1},a_{t+1})\)也不像\(MC\)那样需要整个\(episode\)d额全部，而是只需要中间一部分
- 存在问题，在\(t\)时刻是不知道后面\((r_{t+n},s_{t+n}, a_{t+n})\)的,在t时刻虽然得到了一些数据，但是不不能立刻去更新，而是需要等待，等待需要的数据都收集到，才能进行更新
\(online\)和\(offline\)，\(MC\)方法是\(offline\)的，\(Sarsa\)是\(online\)
而\(n-step \; sarsa\)是一种特殊的\(onlilne\)的
TD learing of optimal action values：Q-learning
终于结束了\(Sarsa\)来到了大名鼎鼎的\(Q-learning\)
\(Q-learning\)是直接估计\(optimal \; action \; value\)不需要去做\(policy \; evaluation\)和\(policy \; improvement\),而是能直接去估计最优的\(action \; value\)
下面是\(Q-learning \; algorithm :\)
\[q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-\alpha_t(s_t,a_t)\left[ q_t(s_t,a_t)-[r_{t+1}+\gamma \max_{a \in A}q_t(s_{t+1},a] \right] \]\[q_{t+1}(s,a)=q_t(s,a), \forall (s,a) \neq (s_t,a_t) \]\(Q-learning\)和\(Sarsa\)非常相似，它们之间的区别仅仅在于\(TD \; target\)不同
\(Q-learning\)中\(TD \; target\)是\(r_{t+1} + \gamma \max_{a \in A}q(s_{t+1}, a)\)
\(Saras\)中的\(TD \; target\)是\(r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})\)
\(Q-learning\)在数学上是在求解一个用\(action \; value\)表示的贝尔曼最优方程
\[q(s,a)=\mathbb{E}[R_{t+1} + \gamma \max_{a}q(S_{t+1},a|S_t=t,A_t=a)], \forall s,a \]上面的就是大名鼎鼎的\(Q-learning\)了，经过前面\(TD \; learning\)还有贝尔曼方程的铺垫，\(Q-learning\)理解起来就简单多了，下面是关于\(Q-leanring\)的一些性质
\(Off-policy\) \(vs\) \(on-policy\)
在\(TD \; learning\)中存在两个\(policy\)
- 一个是\(behavior \; policy\)是用来和环境交互生成\(experience \; samples\)的
- 另一个是\(target \; policy\)是用来不断朝着\(optimal \; policy\)去更新的
on-policy：\(behavior \; policy\)和\(target \; policy\)是相同的
off-policy：\(behavior \; policy\)和\(target \; policy\)是可以不相同的
\(Sarsa\)是一种\(on-policy\)的算法，而\(Q-learning\)是\(off-policy\)的算法
如何判断一个算法是\(on-policy\)还是\(off-policy\)的
- 看算法在解决什么数学问题
- 可以看执行算法需要什么东西
两种\(q-learning\)的算法伪代码
\(off-policy\)可以直接使用\(Gready\)是因为不需要用\(target \; policy\)去探索生成数据，因为生成数据是\(\pi_b\)的事情
a unified point of view
