01
前言
双十一刚过，大家要么熬夜加班(比如十方)，要么熬夜购物，是不是都忘了要一起学强化学习了。其实是十方一直没更新(从未见过如此厚颜...)，一元哥已经吐槽十方无数次了，今天必须更，这一系列必须更完。估摸下，原理相关的估计还要更个两三期，看情况开强化学习进阶系列了。
02
往期回顾
第一期介绍了马尔可夫决策过程，以及最重要的值函数。第二期介绍了有模型的动态规划求解方法，先通过迭代法求解值函数，再通过策略评估和策略改善两个过程得到最优决策策略。第三期介绍了无模型的蒙特卡洛解法，无非就是通过采样的方式求解出值函数，然后还介绍了基于异策略重采样方法。
那么这期呢？可能大家都发现规律，每期都在从各种角度求解值函数，没错，这期也不例外，这期介绍基于时间差分的强化学习方法，结合蒙特卡罗和动态规划方法各自的优势，求解值函数。
03
基于时间差分的强化学习方法
蒙特卡罗方法求解值函数问题在哪？效率不高，因为要采样，一条Instance最后一个状态还必须是结束状态。所以出现了时间差分方法(TD)，取前两种算法的精华。时间差分方法的动作值函数更新方式为:
这里大家先理解下差分，在时间序列中，下一个数字减去上一个数字，就叫一阶差分，上式alpha乘的部分就是TD偏差。这式子看着又很面熟对吧，像梯度下降，alpha像学习率。
所以TD偏差到底是什么意思？动作值函数为什么要这样更新呢？光看这个更新方式很难理解，我们先假设动作值函数已知，最优策略也已知，我们再看下TD偏差:
大家觉得这个应该是多少呢？没错，就是0，因为:
所以我们先随机初始化策略和学习率，边采样边更新动作值函数，直到收敛，两种更新算法的伪代码如下:
代码语言：javascript复制同策略的Sarsa方法
init Q(s,a),学习率alpha,折扣因子gamma,贪婪策略
Do {
init t = 0, 状态s[t]
Do{
根据贪婪策略得到a[t],r[t 1],s[t 1],a[t 1]
Q(s[t], a[t]) = Q(s[t], a[t]) alpha * (r[t 1] gamma * Q(s[t 1], a[t 1]) - Q(s[t], a[t]))
t
} while (s[t] 不是最终状态)
} while (Q(s,a)没收敛)异策略的Q-learning方法
init Q(s,a),学习率alpha,折扣因子gamma,行动贪婪策略，目标贪婪策略
Do {
init t = 0, 状态s[t]
Do{
根据行动贪婪策略得到a[t],r[t 1],s[t 1]
根据目标贪婪策略得到a[t 1]使得Q(s[t 1], a[t 1])最大
Q(s[t], a[t]) = Q(s[t], a[t]) alpha * (r[t 1] gamma * Q(s[t 1], a[t 1]) - Q(s[t], a[t]))
t
} while (s[t] 不是最终状态)
} while (Q(s,a)没收敛)看完上述两种更新算法都是用后继一个动作值函数来更新当前动作值函数，能不能利用后继两个状态值函数更新当前状态值函数呢？当然可以，这就是我们要说的TD(λ)算法。
04
TD(λ)算法
我们可以用第n步的值函数更新当前值函数，可以表示为:
这里n取多少不重要，但是我们都已经利用了未来第n步的值函数了，那未来k(0<k<n)步的值函数呢？所以可以加权融合前n步的值函数:
看到这里又要晕了，为什么可以这样加权？因为：
所以：
这里又要注意的是，我们在估计Gt的时候需要已知Rt 1~t n，所以就要先等到采样结束，和前面Q-learning方法边采样变更新不同，我们有没有办法改造此算法，变成边采样边更新呢？当然可以！我们在处于t时刻时，就可以计算t时刻的TD偏差，并更新之前所有状态的值函数了:
Et(s)就是衰减因子，该值大小和过往每个状态和当前状态的距离有关。最后我们给出Sarsa(λ)算法的伪代码:
代码语言：javascript复制同策略的Sarsa(λ)方法
init Q(s,a),学习率alpha,折扣因子gamma,贪婪策略,λ
Do {
init t = 0, 状态s[t], E[s,a] = 0
根据贪婪策略得到a[t]
init history = set()
history.add((s[t], a[t]))
Do{
根据贪婪策略得到a[t],r[t 1],s[t 1],a[t 1]
TD = r[t 1] gamma * Q(s[t 1], a[t 1]) - Q(s[t], a[t])
E[s,a] = 1
for state, action in history:
Q(state, action) = Q(state, action) alpha * TD * E[state, action]
E[state, action] = gamma * λ * E[state, action]
t
} while (s[t] 不是最终状态)
} while (Q(s,a)没收敛)
