强化学习数学基础（5）

写在前面

该系列是作者学习西湖大学赵世钰老师的《强化学习的数学原理》这一课程所总结的知识点。

回顾

在上一章节，我们引入了随机近似理论，并介绍了其中代表性工作RM算法。它提供了一种在不知道函数形式的情况下，解决求根问题的一种增量迭代式方案，在满足一些条件的基础上，数学上能够严格证明收敛。我们上上章节使用monte carlo所解决的mean estimation问题也可以用RM算法进行求解，在深度学习中广泛应用的随机梯度下降可是RM算法的一种应用。

本章要介绍RL中的重要算法——时间差分算法（Temporal-Difference Learning，TD），Monte carlo是我们介绍的第一个model-free方法，而TD则是在我们上一章所介绍的RM工作基础上的第二个model-free方法。

我们再来回顾下，Monte-carlo是怎么引入的？因为在求解optimal bellman equation问题的policy iteration方法中，在policy evaluation步骤里，我们需要求解state-value；如果我们掌握系统/环境的物理模型，即model-based的情况下，我们可以通过求解bellman equation的closed-form solution或者iteration method解决。但在model-free的情况下我们怎么求解？通过monte carlo方法进行mean estimation，在大数定律的保障下，对state-value进行无偏估计，但monte carlo的缺点在于效率比较慢，即只有等到experience结束，我们才能进行估计，即它是一种non-incremental的算法；怎么解决？我们在上一章节介绍了随机近似理论，其代表性工作RM算法是一种incremental解决mean estimation problem的方案，所以，我们是否可以将RM算法应用于policy iteration中进行state-value的求解呢？本章所要介绍的TD算法正用于解决该问题。

Temporal-Difference Learning

在RM算法中，我们所解决的mean estimation问题定义如下：

为什么要强调iid呢？

因为保证RM算法收敛的条件中，需要噪声 期望为0；

• 将上述问题重构为root-finding问题，即定义 ，需要求 的解；
• 则RM算法中
• 可得RM算法迭代式为：

TD learning of state values

由于它是一种model-free的算法，那么没有模型，就需要有数据；TD learning所需的数据形式为 ，其由给定的policy 产生。

TD learning算法为：

其中 表示对state value 的估计值。 表示学习率。 被称为TD target ， 则被称为TD error 。

那么它是怎么和RM算法有关呢？

关于state value的定义为：

这也是bellman equation的一种表达形式；

将其转化为root-finding problem，即：

其带噪观察值为：

因此，RM算法的迭代式为：

那么，求解该迭代式所需要数据依赖为：

• experience set for
• is known

关于第一个依赖，由于真实数据是process的，因此被替换为 ；因此，对于 ，我们每次（即 ）迭代哪个 是依据状态转移的。

关于第二个依赖，由于我们无法提前知道 ，因此其被替换为估计值；

如此一来，它还会收敛吗？

Theorem（Convergence of TD Learning）

By the , converges with probability 1 to for all As if and for all .

（证明略）

现在比较下TD learning和MC learning的区别：

• TD是online的，每接受到一个reward，即获得 后，就能获取update state values；而MC是offline的，它只有等到一个episode结束，收集到全部数据才会更新，并且有数据利用效率低下的问题；
• TD能够处理连续任务，MC只能处理存在终止状态的episodic任务；
• TD是bootstrapping的，因此，它依赖对state value的initial guess，而MC不需要；因此TD的偏差在初始时是比MC大的，但会随着迭代慢慢降低；
• 关于variance，由于TD比MC依赖更少的随机变量（MC依赖整个序列），所以TD的方差应该比MC低。

TD learning of action values: Sarsa

由于policy ietration是直接估计的action value，因此我们希望TD learning能够直接估计action value。模仿state value的迭代，可推action value的迭代式估计为：

• 是 的估计；
• 学习率 依赖 ；

计算上式需要有什么数据依赖呢？ ，因此experience为

该算法也被称为Sarsa算法，即state-action-reward-state-action的缩写。

Sarsa算法所解决的数学问题是什么呢？

将Sarsa嵌入policy iteration中用于在policy iteration步骤中更新action value就得到了Sarsa policy iteration算法。

Variant of Sarsa

• the Expected Sarsa

  其中：

  从迭代式中可以看出，与Sarsa相比，其数据依赖由 转变为

• N-step Sarsa

  其数据依赖为

​ 所以，当 ，其退化为普通的Sarsa算法，而当 时，其变为MC算法；

TD learning of optimal action values:Q-learning

Q-learning可以说是被应用RL的最广泛的算法之一；Sarsa算法本质是估计given policy 下的action value，只不过当其配合policy improvement步骤，可以用于寻找 potimal policies。

而Q-learning则可以直接估计最优action value，因此根据bellman optimality equation，其对应的策略也为最优策略。其算法为：

其数据依赖为：

此处引入一个重要概念，Q-learning为off-policy算法，什么是on-policy和off-policy？

首先介绍behavior policy和target policy：

behavior policy：指用于产生experience样本的策略；

target policy：指不断向最优策略更新；

当behavior policy与target policy一致，则称为on-policy；否则为off-policy

off-policy有什么优势？

• 它能够基于其他策略所产生的experience样本进行最优策略的搜索；例如，behaviour policy可以是纯探索，如果我们想对所有state-action pairs估计其action value，我们可以使用探索策略来产生对足够多的对每一个state-action pair都能够访问的episodes；

而on-policy则需要进行online与环境交互，如Sarsa policy iteration，在policy improvement步骤，通过 -greedy平衡探索和利用。

判断本章节所介绍的算法是否属于off-policy：

• Sarsa是on-policy算法，Sarsa的experience sample为 ，其中 是基于 产生的，因此其target policy 与生成experience sample的behavior policy 一样，所以是off-policy算法；
• MC也是on-policy算法，因为其依赖的数据为 ，behavior policy与target policy一致；
• Q-learning是off-policy算法，其experience sample为 ；所以behaviour policy所产生的 可以是任何，target policy则会收敛至最优策略。

总结

本章在前一章节RM算法的基础介绍TD算法，将其用于在policy evaluation步骤中action value；从最常见的Sarsa算法到其各种变体，如Expected Sarsa、n-step Sarsa以及Q-learning；最后根据behaviour policy与target policy是否一致，可将上述算法分为on-policy和off-policy，其中应用广泛的Q-learning算法属于off-policy。