Reinfocement Learning

六、随机近似与随机梯度下降（Stochastic Approximation & Stochastic Gradient Descent）

6.1 Robbins-Monro Algorithm

Stochastic approximation (SA) 是指一大类求根和优化问题的随机迭代算法，与许多其他求根算法相比，SA 的强大之处在于它无需知道目标函数的表达式或其导数。Robbins-Monro算法是SA领域的开创工作。

假定我们想要此等式的根 $w$：$g(w)=0$

当函数 $g$ 的表达式已知或者它的导数已知的时候，求解当然很简单。但是当 $g$ 未知的时候，问题就困难起来了。Robbins-Monro 算法是这样解决的：
$$w_{k+1}=w_k-a_k\stackrel{\sim }{g}(w_k,{\eta }_k)$$
其中 $w_k$ 是对第 $k$ 次根的估计，$\stackrel{\sim }{g}(w_k,{\eta }_k)=g(w_k)+{\eta }_k$ 是第 $k$ 个带有噪声（误差）的观测（输出），$a_k$ 是正系数。

显然这个算法并不依赖于函数 $g$，但依赖于输入序列 $w_k$ 和带有噪声输出序列 $\stackrel{\sim }{g}(w_k,{\eta }_k)$，框图如下：

最终 $w_{k+1}$ 能收敛到根 $w^{\ast }$。收敛性在此不做证明。

来看一个平均值求解的例子。如何求平均值，把所有数加起来除以个数当然能求得。但这样做的弊端是我必须要获取所有的数据后才能求其均值，如何使用迭代的方式求解呢？

我们可以假设 $w_{k+1}=\frac{1}{k}\underset{i=1}{\sum ^k}{x}_i$，则 $w_k=\frac{1}{k-1}\underset{i=1}{\sum ^{k-1}}{x}_i$，所以 $w_{k+1}$ 可以由 $w_k$ 表示：
$$w_{k+1}=\frac{1}{k}\underset{i=1}{\sum ^k}{x}_i=\frac{1}{k}(\underset{i=1}{\sum ^{k-1}}{x}_i+x_k)=\frac{1}{k}((k-1)w_k+x_k)=w_k-\frac{1}{k}(w_k-x_k)$$
就像这样：

如果把 $\frac{1}{k}$ 变为 ${\alpha }_k$ 还能成立吗？可以用上述的 Robbins-Monro Algorithm 来证明 $w_{k+1}$ 仍然能收敛到期望。

问题转换为当 ${\alpha }_k\ne \frac{1}{k}$ 时，$w_{k+1}$ 还能收敛到期望 $\mathbb{E}[X]$ 吗？

我们有 $w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$

建立如下函数 $g(w)=w-\mathbb{E}[X]$，如果 $g(w)=0$，根即为期望。

现输入一个 $w$，如何得到其噪音的观测呢？
$$\stackrel{\sim }{g}(w,\eta )=g(w)+\eta =(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)=w-x$$
现考虑 $w_k$ 序列并带入到 Robbins-Monro 公式中得：
$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$
即得到证明：即使 ${\alpha }_k\ne \frac{1}{k}$ 时，$w_{k+1}$ 仍能收敛到期望 $\mathbb{E}[X]$ ？

6.2 随机梯度下降

Stochastic gradient descent（SGD）被广泛应用于机器学习和强化学习，但后面可以发现它实际上就是一种特殊的 Robbins-Monro 算法。

假设我们要求解一个最优化问题 $w$ 何值时，$J(w)$ 最小：
$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]$$

${\alpha }_k$ 是学习率（步长），$\nabla$ 表示梯度，采用梯度下降的方法一定能找到一个局部极小值

期望很难求，用蒙特卡洛估计依靠数据近似期望

但每一次更新 $w_k$ 时，都需要进行多次采样，现实中可能行不通

与 GD 相比使用随机梯度来代替真实的梯度，与 BGD 相比，使 $n=1$，即采样一次。

例子：

为什么 SGD 是可以收敛的呢？同样时使用 Robbins-Monro 证明。

现在有目标函数 $J(w)=\mathbb{E}[f(w,X)]$

我想让它取得最小值，那么一个必要条件时取得最小值时的梯度为0，即 ${\nabla }_{w}J(w)=\mathbb{E}[{\nabla }_{w}f(w,X)]=0$

令 $g(w)={\nabla }_{w}J(w)=\mathbb{E}[{\nabla }_{w}f(w,X)]$，此时变成了 $g(w)=0$ 的求根问题

故

七、时序差分方法（Temporal-Difference Learning）

7.1 TD算法介绍

TD 算法是 $model-free$ 的算法

由给定的策略 $\pi$ 在 $t$ 时刻可以得到序列 $\{(s_t,r_{t+1},s_{t+1}){\}}_t$，$s_t$ 表示 $t$ 时刻所在的状态

式中 $v_t$ 代表在 $t$ 时刻状态 $s$ 的 $statevalue$ （即$v_{\pi }$）的估计值，这个式子就是要用 $v_t$ 来不断逼近 $statevalue$

$(1)$ 式表示更新当前状态 $s_t$ 的 $statevalue$ 估计值 $v_{t+1}(s_t)$

$(2)$ 式表示其余状态的的 $statevalue$ 估计值不进行更新

$question1$：为什么 ${\stackrel{-}{v}}_t$ 被称作 $TDtarget$？

$answer1$：因为此算法是要把 $v_t(s_t)$ 朝着 ${\stackrel{-}{v}}_t$ 的方向改进

$question2$： $TDerror$ 是什么？

$answer2$：

• 两个时刻的差值
• 描述了 $v_t$ 与 $v_{\pi }$ 之间的误差

$TDAlgorithmproperties$：

1. 对给定的策略进行 $policyevaluation$ ，即计算 $statevalue$（不能估计 $actionvalue$，不能寻找最优策略）
2. 核心思想就是对于给定的策略，我对状态 $s$ 的 $v_{\pi }$ 有一个估计，这可能是不准确的，此时将得到的 $\{(s_t,r_{t+1},s_{t+1}){\}}_t$ 与估计联系到一起，得到 $TDerror$，这说明了此时的估计是不准确的，并利用 $TDerror$ 来改进当前的估计。

7.2 TD算法的收敛性

TD 算法其实是求解了这样一个贝尔曼公式：

就是把原来的 $G_{t+1}$ 替换成了 $v_{\pi }(S^{\prime })$ ，这是由 $statevalue$ 最初始的定义得到的。

可以用 Robbins-Monro Algorithm 来求解这个公式，首先定义：

如果 $g(v(s))=0$，那么 $v(s)=\mathbb{E}[R+\gamma v_{\pi }(S^{\prime }|s)]$ 成立，就可以用 $v(s)$ 来逼近 $v_{\pi }(s)$。我们有大量 $R,S^{\prime }$ 的数据采样 $r,s^{\prime }$

得到：

此式存在两个问题。

$question1$：式子是由 $\{(s,r,s^{\prime })\}$ 的得到的，如何确保它是按序的呢？

$answer1$：将 $\{(s,r,s^{\prime })\}$ 替换为一个 $trajectory$ 中的 $\{(s_t,r_{t+1},s_{t+1})\}$

$question2$：式中的 $v_{\pi }(s_k^{\prime })$ 是不知道的

$answer2$：用 $v_k(s_k^{\prime })$ 即 $v_{\pi }(s_k^{\prime })$ 的估计值来代替 $v_{\pi }(s_k^{\prime })$ ，仍能使得 $v_k(s)$ 收敛

7.3 TD算法与MC算法的比较

TD Learning	MC Learning
$Online$：能够在收到一个 $reward$ 后立即更新 $state/actionvalue$	$Offline$：必须要等到一个 $episode$ 结束才能计算 $return$
$Continuingtasks$：可以处理连续的任务（$episode$ 无限长)	$Episodictasks$：只能处理一个 $episode$ 有 $terminalstate$ 的任务
$Bootstrapping$：更新 $value$ 依赖于先前 $value$ 的估计值	$Non-bootstrapping$：可以直接估计 $state/actionvalue$
$Lowestimationvariance$：相较于 MC 有较少的随机变量，但是是有偏估计（由初始的估计造成）	$Highestimationvariance$：为估计 $q_{{\pi }_k}(s,a)$ 涉及到的随机变量较多，采样数量少的情况下方差较大，是无偏估计

7.4 Sarsa及其变种

$Sarsa$ 可以给出给定策略 $\pi$ 的 $actionvalue$

假设有集合 $\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}){\}}_t$

形式上跟 $TD$ 算法是一样的，只是 $TD$ 得到的是 $statevalue$ 的估计值，而 $Sarsa$ 是 $acitonvalue$ 的估计值

$Sarsa$ 求解的是这样的贝尔曼公式：

在求得 $actionvalue$ 之后，使用 $ϵ-greedy$ 的策略进行 $policyimprovement$。

算法存在的问题是：如果 $episode$ 不足以覆盖全部的 $(s,a)$，那么可能找不到全局的最优策略。

$ExpectedSarsa$

不需要再对 $a_{t+1}$ 进行采样，$ExpectedSarsa$ 求解的是这样的贝尔曼公式：

$n-stepSarsa$ 需要的集合为 $\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}),...,r_{t+n},s_{t+n},a_{t+n}{\}}_t$，而 $MC$ 是需要整个的 $episode$，即所有的 $state-actionpair$

区别在于后面的 $TDtarget$ 不同

7.5 Q-learning

跟 $Sarsa$ 相比也是 $TDtarget$ 不同，$Q-learning$ 取的是让状态 $s_{t+1}$ 的 $actionvalue$ 取得最大值时的动作 $a$，而 $Sarsa$ 是随机采样一个 $a$

$Q-learning$ 求解的是贝尔曼最优方程：

得到的值是最优的 $actionvalue$，当然对应的是最优策略

7.6 on-policy learning & off-policy learning

在 $TDLearning$ 中有两种策略：

• $behaviorpolicy$：用于生成 $experiencesamples$（即前面所说的 $\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}){\}}_t$ 这样的序列）
• $targetpolicy$：持续向最优策略更新

由此引出 $on-policy$ 与 $off-policy$：

• $on-policy$：$behaviorpolicy$ 与 $targetpolicy$ 相同，即用一个策略 $\pi$ 与环境交互得到 $experience$ 同时改进这个策略 $\pi$ ，再用改进的策略 ${\pi }^{\prime }$ 与环境交互然后再改进直到得到最优策略 ${\pi }^{\ast }$
• $off-policy$：$behaviorpolicy$ 与 $targetpolicy$ 不相同，即用一个策略 $\pi$ 与环境交互得到 $experience$ 同时改进另外一个策略 ${\pi }^{\prime }$ ，再用策略 $\pi$ 与环境交互然后再改进 ${\pi }^{\prime }$ 直到得到最优策略 ${\pi }^{\ast }$

$Sarsa$ 是 $on-policy$：${\pi }_t\to experience\to actionvalueestimation\to {\pi }_{t+1}$，${\pi }_t$ 既是 $behaviorpolicy$ 也是 $targetpolicy$

$Monte-Carlo$ 是 $on-policy$：${\pi }_t\to experience/trajectory\to actionvalueestimation\to {\pi }_{t+1}$，${\pi }_t$ 既是 $behaviorpolicy$ 也是 $targetpolicy$

$Q-learning$ 是 $off-policy$： 由 $s_t$ 选择动作 $a_t$ 的 $behaviorpolicy$ 可以是任意策略， $targetpolicy$ 是根据最大 $actionvalue$ 确定的最优策略

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

用更新的 ${\pi }_{t+1}$ 继续生成 $experience$，在 $policyimprovement$ 阶段采用 $ϵ-greedy$ 是希望策略具有一定的探索性，希望能覆盖到所有的 $(s,a)$

用 ${\pi }_b$ （此策略生成的 $episode$ 会对 $Q-learning$ 的结果产生影响）来生成 $experience$，在 $policyimprovement$ 阶段采用 $greedy$ 是因为我不会用改进的策略来生成 $experience$，所以选最优的即可

7.7 summary

前面介绍的 $TD$ 算法其实都可以用下面的式子统一表示：

不同点在于 $\stackrel{-}{q_t}$：

所有的算法也可以看作是求解贝尔曼公式或者贝尔曼最优公式的随即近似算法：