时间差分方法(TD方法)

在蒙特卡洛方法中，状态的价值是通过以下公式求出：

其中

是学习率，

是状态

处的折扣累积回报值。其公式推导如下

这种方法有一个缺点，就是在一次试验中需要等到终止状态出现才会结束，所以在这里借鉴动态规划的”自举“思想将其改写，使试验还未结束时就能估计出当前的值函数。

根据前面的知识，我们知道

,将其代入到上式中：

以上就是时间差分方法的值函数更新公式，其中

为TD目标，

称为TD偏差。

时间差分方法分为同策略Sarsa方法和异策略Q-learning方法。

异策略Q-learning方法的伪代码如下^[1]：

贪婪策略（

）：

,当

时表示有90%的概率选取最大动作值，有10%随机选取动作值。

首先需要随机选取一个状态

，在根据

贪婪策略选择动作a，选择之后以状态

为起始状态，然后重复选择下一状态，直到出现终止状态。下一状态

由状态

和动作a确定，动作值函数由公式 :

直到值函数收敛，然后根据策略：

确定最终策略。根据博客

中的例子，由matlab实现代码如下：

1.异策略-Q-learning

function

同策略Sarsa算法和异策略Q-learning算法的主要区别是评估策略的确定方式不同，在Q-learning算法中，评估策略是通过贪心算法的思想得到的，即在求解动作值函数时使用公式：

由公式可以看出下一状态的动作值函数是选取最大的（

），而在同策略sarsa中，其下一状态的动作也是通过

贪婪策略得到。具体matlab代码如下：

2.同策略-sarsa算法^[3]

function

参考

1. ^^ab蒙特卡洛方法 https://zhuanlan.zhihu.com/p/25743759
2. ^Q-learning实现 https://zhuanlan.zhihu.com/p/29213893
3. ^sarsa算法 https://zhuanlan.zhihu.com/p/29283927