强化学习的数学原理-第7课

2025年12月3日

13:58

时序差分方法

 

TD算法求解状态值. TD learning

════════════════════════════════════════════════════════════════════════════════════════════════════

TD算法：

TD算法也是基于数据的算法，数据形式如上图Experience samples所示，目的是根据这个

experience samples估计策略π的状态值v_π(s)。

 

TD算法的具体做法是：

也就是在t时刻，假设t时刻的数据是（s_t,r_t+1, s_t+1），即t时刻的状态是s_t，那么只更新

s_t这个状态的状态值，其他状态的状态值不变。 表示对s_t这个状态的一个新的估计。

 

总而言之，新的估计值等于旧的估计值+修正项（TD error）。

其中 叫做TD target，因为That is because the algorithm drives v(st) towards  

再来看TD error，

TD error是两个时间步之间的差距，所以算法被称为时序差分算法，TD error反映了v_t和v_π的

差距，如果v_t和v_π相同，TD error的期望是0，如上图所示。

 

刚才介绍的TD算法就是用来估计某个策略π的state value，即policy evaluation，TD算法不是

用来估计state action value的。

policy evaluation其实就是求解bellman公式，之前介绍的求解bellman公式的2种方法（直接求解和

迭代求解）都需要知道model的表达式，而TD算法是Model free的。

 

bellman公式的还有另一种形式，一种期望的形式（其实从状态值的定义就能理解），如下图式5

我们用RM算法来求解这个期望值，得到的就是TD算法。

具体来看如何用RM算法求解这个期望：

 

 

 

式（6）和TD算法有2处地方不同：

• 式6这个RM算法，需要我们反复从当前状态s出发 ，得到r和s'的采样 ，也就是k=1时，我从

当前状态s出发 ，得到r，和新的状态s'，这是第一个采样 ；然后k=2时，还需要从状态s出发 ，

得到r,和新的状态s'，这是第二个采样 ….   而TD算法是基于时序的，是一个trajectory，不存在回

到刚才状态，再重新出发这种操作。解决的方法是根据这个trajectory，如果访问到了状态s，就更新

，如果没有访问到，就不更新，也就是相当于k=1

• 式6中，蓝色的vπ部分，表示策略π的真实的状态值 ，但是我们不知道这个真正的状态值（正是我们

要求的），我们可以用vπ的估计值vk来代替，也是可以收敛的（证明省略）

 

 

既然TD Learning是一种RM算法，那么其收敛性及前提条件就和RM一致。其实需要注意的一点是

这个条件需要对所有的状态都成立，这就要求every state must be visited an infinite (or succiently many) number of times.每个状态都被访问无穷次或足够多次，才能保证趋于无穷。

 

TD算法和MC算法的对比：

• TD算法是一种在线学习算法，每走一步都能进行更新，可以做continuing tasks，一直持续下去，而

MC算法是offline的，必须等到一个episode结束之后 ，才能进行更新

• TD算法是Bootstrapping的，新的估计依赖于之前的估计，需要有个起始的Initial guess，而MC不是
• TD算法的方差小，因为用到的随机变量少，只走了一歩，用到的随机变量也就是R_t+1,S_t+1，而MC的方差大，因为MC走了一个episode，用到的随机变量R_t+1,S_t+1，…R_t+n,S_t+n
• 但是TD有bias，因为有initial guess，但随着迭代增加，会慢慢收敛。MC没有initial guess，没有bias。

 

 

SARSA

════════════════════════════════════════════════════════════════════════════════════════════════════

TD算法是用来求状态值的，但是强化学习需要求最优策略，所以我们需要求得的是state action value，SARSA

就是 algorithm that can directly estimate action values.

SARSA和TD几乎是一个东西，TD是用RM算法求解Bellman公式，SARSA也是，只不过BEllman公式的期望形式变成

state action value q(s,a)了，如下图

SARSA算法：

我们可以结合SARSA和Policy improvment策略（比如Є-greedy）来求解最优策略

在当前的t时刻，根据当前(st,at)，通过和环境交互得到t+1时刻的（rt+1,st+1），然后根据现在的策略

得到t+1时刻的要采取的动作at+1.

每获得一个新的（rt+1,st+1,at+1），都进行q的更新，q更新之后 ，马上根据更新后的q，进行policy的更新

（policy improvement, 用的是Є-greedy的策略，平衡exploration和exploitation）。

 

n-step sarsa

nstep sarsa统一了SARSA和Monte carlo learning

当n=1时，是SARSA，当n=无穷时，是MC learning

在刚才的SARSA中，我们将q的表达式写成如下的形式：

其中，S'和A’是下一个时刻的状态和动作，我们也可以对q_π(S'，A')继续展开，

SARSA求解的就是，MC求解的就是（即走完这个episode，得到return，作为期望的估计）

 

 

SARSA只需要走一步，就能更新q，而n-step需要走n步，才能更新t时的q(st,at)

 

Since n-step Sarsa includes Sarsa and MC learning as two extreme cases, its

performance is a blend of Sarsa and MC learning:

- If n is large, its performance is close to MC learning and hence has a large

variance but a small bias.

- If n is small, its performance is close to Sarsa and hence has a relatively

large bias due to the initial guess and relatively low variance.

 Finally, n-step Sarsa is also for policy evaluation. It can be combined with

the policy improvement step to search for optimal policies.

 

Q learning

════════════════════════════════════════════════════════════════════════════════════════════════════

Sarsa can estimate the action values of a given policy. It must be combined

with a policy improvement step to find optimal policies.

 Q-learning can directly estimate optimal action values and hence optimal policies.

 不需要在Policy evaluation和policy improvment之间来回交替运行。

 

 

 

Q-learning和SARSA的区别就是TD target不同。

 

Sarsa在数学上解决的是求解bellman方程（即给定一个策略，得到相应的bellman方程，求解这个bellman方程得到这个策略对应的state value,v(s）和state action value，q(s,a)），而Q-learning则解决的是求解bellman最优方程，那么它最后得到的不是某个策略对应的q值，而是最优的q值，即最优策略下的q值。

 

on-policy 和 off policy

在TD learning中，policy可以分为2种：

  1）behavior policy is used to generate experience samples.，是我们生成trajectory时用到的策略

2. target policy，是我们更新的策略

 

on-policy就是behavior policy和target policy一样，也就是用这个策略与环境进行交互，得到experience，同时改进这个策略，改进之后，再用这个策略和环境进行交互。

off-policy就是用策略来和环境交互，得到大量的experience，然后我用这些经验去改进策略 ，这个策略最终会收敛到最优策略。

 

How to judge if a TD algorithm is on-policy or off-policy?

 First, check what the algorithm does mathematically.

 Second, check what things are required to implement the algorithm.

 

Sarsa is on-policy.

 

 

Monte Carlo learning is on-policy.

 

Q-learning is off-policy.

注意，sarsa需要的数据是(st,at,r_t+1,s_t+1,a_t+1)，是个5元组，而Q-learning需要的数据是（st,at,r_t+1,s_t+1）
是个4元组（其实也是需要a_t+1的，只不过选择的是最大的qt对应的那个a）。

 

也就是说sarsa中，生成experience (st,at,r_t+1,s_t+1,a_t+1)时的behavior policy为πt，更新的target policy也是这个πt，只不过是πt+1，然后用πt+1作为新的behavior policy。

 

Since Q-learning is off-policy, it can be implemented in an either on-policy or off-policy fashion.

Q-learning可以是on-policy，也可以是off-policy的，

 

on-policy就是先用policy π采样的experience （st,at,r_t+1,s_t+1），按照上图中update q-value的

式子更新q-value，然后再用Є-greedy的方式更新Policy，再用更新后的Policy继续生成新的experience。

 

off-policy和on-policy的update q-value部分完全一样，其实就是刚才解释的为什么Q-Learning

是off policy一样，只不过在更新target policy时，用greedy的策略，但是这个更新后的target policy

并没有用到他，下面还是用之前 的behavior policy 来生成experience。

上图中的例子，当behavior policy是比较均匀分布的，即探索性较强的，那么off-policy Q-learning

得到的最终策略是最优的。

 

当behavior policy的探索性不强时，off policy Q-learning并不能收敛到最优的策略。

 

 

off-policy的性质很重要，deep learning和TD算法相结合时为什么会选择Q-learning呢？

就是因为Q-learning可以是off-policy的。

 

 

这些算法可以用一个统一的形式来表示，如下图所示

 

所有的算法都可以看作是，用stochastic随机近似，来求解不同形式的bellman方程或bellman最优方程，

 

这些TD算法从本质上来说，是求解一个给定策略的bellman公式，也就是求一个给定策略的v和q

（主要是q），那么怎么来得到最优策略呢，就是把policy evluation和policy improvment结合起来，

最终可以得到最优策略。

其中，monte carlo算法

，这个式子可以说是bellman公式，但其实就是action value的定义。