基于值函数的策略一般都是离散的动作空间（并不一定都是），因为需要遍历所有的值函数 $Q$ 的动作来找到能让 $Q$ 最大化的动作 $a$。这其实也对我们是一种启发：其实 $Q$ 函数可以做成对动作 $a$ 连续的。每次找最佳 $a$ 需要求 $Q$ 对 $a$ 的极值即可：

[!PDF|annotate] [[policy-gradient.pdf#page=2&selection=71,3,89,12&color=annotate|policy-gradient, p.1]] Most early successful applications of RL use value-based methods (e.g., [ 84 , 79 , 55]), which estimate the expected future rewards to inform the agent’s decisions. However, these methods only indirectly optimize the true objective of learning an optimal policy [ 82 ] and are non-trivial to apply in settings with continuous action spaces [75].

动态规划强化学习算法

只有模型已知，才能使用这种算法。模型指的是 MDP 模型，主要是状态转移概率 $p(s^{\prime}

s, a)$和奖励$r(s,a,s^{\prime})$。这样我们才能直接根据贝尔曼方程来计算值函数，根据最新的值函数优化策略，然后再基于新的策略计算下一轮值函数。贝尔曼方程：

$$V^{\pi}(s)=\mathbb{E}_{a \sim \pi(a | s)} \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} | s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right]$$ $$Q^{\pi}(s, a)=\mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} | s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma \mathbb{E}_{a^{\prime} \sim \pi\left(a^{\prime} | s^{\prime}\right)}\left[Q^{\pi}\left(s^{\prime}, a^{\prime}\right)\right]\right]$$

策略迭代和值迭代算法之间的区别：

策略迭代是把每一个状态的值函数都更新之后，再更新策略，这种对于策略的更新是一次性迈了一大步。

值迭代是在当任何一个状态下，状态值函数更新时，同步更新策略，对策略的更新是相当于是多次迈了小步（学术上来讲，是基于了贝尔曼最优方程）。

策略迭代算法（Policy Iteration）

![[nndl-book.pdf#page=352&rect=26,264,457,583&color=annotate

nndl-book, p.337]]

收敛性证明仍需补充。

值迭代算法（Value Iteration）

可以看到，值迭代直接根据最大的 $a$ 更新值函数，并且选取最大的 $a$ 来更新策略。收敛时的值函数就是最优的值函数，其对应的策略也就是最优的策略。

![[nndl-book.pdf#page=353&rect=32,370,363,512&color=annotate

nndl-book, p.338]]

蒙特卡洛强化学习算法

模型无关（未知）的，基于采样的学习方法。

基于策略 $\pi$ 随机游走，得到 N 条轨迹，然后基于回报来更新 Q 函数：

$$Q^{\pi}(s,a) \approx \hat{Q}^{\pi}(s,a) = \frac{1}{N} \sum_{n=1}^N G(\tau_{s_0=s,a_0=a}^{(n)})$$

在近似估计出 $Q$ 函数 $\hat{Q}^\pi(s,a)$ 后，就可以进行策略改进．然后在新的策略下重新通过采样来估计 $Q$ 函数，并不断重复，直至收敛。

时序差分学习算法

SARSA

SARSA 算法的全称是 State Action Reward State Action，属于时序差分学习算法的一种，其综合了动态规划算法和蒙特卡洛算法，比仅仅使用蒙特卡洛方法速度要快很多。当时序差分学习算法每次更新的动作数为最大步数时，就等价于蒙特卡洛方法。

值函数更新公式的引入：多次试验的平均

SARSA 的核心思想在于增量计算。在蒙特卡洛算法中，我们需要对 $Q$ 函数 $\hat{Q}^{\pi}(s, a)$ 进行有效的估计，假设第 $N$ 次试验后值函数为 $\hat{Q}_{N}^{\pi}(s, a)$ 的平均为：

$$\begin{aligned} \hat{Q}_{N}^{\pi}(s, a) &=\frac{1}{N} \sum_{n=1}^{N} G\left(\tau_{s_{0}=s, a_{0}=a}^{(n)}\right) \\&=\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)+\sum_{n=1}^{N-1} G\left(\tau_{s_{0}=s, a_{0}=a}^{(n)}\right)\right) \\ &=\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)+(N-1) \hat{Q}_{N-1}^{\pi}(s, a)\right) \\ &=\hat{Q}_{N-1}^{\pi}(s, a)+\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)-\hat{Q}_{N-1}^{\pi}(s, a)\right) \end{aligned}$$

其中 $\tau_{s_{0}}=s, a_{0}=a$ 表示轨迹 $\tau$ 的起始状态和动作为 $s$, $a$。

人话：$Q$ 函数估计等于 $N$ 个轨迹所得出来的回报的平均，等于前 $N-1$ 个轨迹和这个（第 $N$ 个）轨迹的总回报的平均。而在第 $N-1$ 次实验时，我们已经基于前 $N-1$ 个轨迹估计出了一个 $Q$ 函数，这就形成了一个迭代计算的方法

省却以上公式的中间过程，我们可以将该公式简化为如下：

$$\hat{Q}_{N}^{\pi}(s, a)=\hat{Q}_{N-1}^{\pi}(s, a)+\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)-\hat{Q}_{N-1}^{\pi}(s, a)\right)$$

也就是当这次采集完轨迹后，更新的量为这次这条轨迹的总回报，减去我们预估的总回报（$Q$）：

$$\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)-\hat{Q}_{N-1}^{\pi}(s, a)\right)$$

在该公式中，值函数 $\hat{Q}^{\pi}(s, a)$ 在第 $N$ 次试验后的值 $\hat{Q}_{N}^{\pi}(s, a)$，即 $N$ 次试验的平均等于前 $N-1$ 次试验再加上一个增量。在该公式中，$1/N$ 可以表示成第 $N$ 次试验相对于前 $N-1$ 次试验的重要性。目前有两个问题：

1. 其实可以调整，因为其表示第 $N$ 次试验的重要性。
2. $Q$ 函数是在每采样完一条轨迹时才更新的，而不是每采样一步就更新；

值函数更新公式的改进：权重参数的调整（解决第一个问题）

更一般性的，我们可以将权重系数 $1/N$ 改成一个比较小的正数 $\alpha$，由此，以上公式可以被改写成为以下：

$$\hat{Q}^{\pi}(s, a) \leftarrow \hat{Q}^{\pi}(s, a)+\alpha\left(G\left(\tau_{s_{0}=s, a_{0}=a}\right)-\hat{Q}^{\pi}(s, a)\right)$$

其中，增量 $\delta \triangleq G\left(\tau_{s_{0}=s, a_{0}=a}\right)-\hat{Q}^{\pi}(s, a)$ 称为蒙特卡洛误差，表示真实的回报与期望回报之间的差距。

值函数更新公式的改进：累积奖励的计算（解决第二个问题）

在上面的公式中，$G\left(\tau_{s_{0}}=s, a_{0}=a\right)$ 为一次试验的完整轨迹所得到的总回报，为了提高效率，放宽模型的约束，可以借助动态规划算法来计算 $G\left(\tau_{s_{0}}=s, a_{0}=a\right)$，而不需要得到完整的轨迹。

从 $s,a$ 开始，采样下一步的状态和动作 $\left(s^{\prime}, a^{\prime}\right)$，并得到奖励 $r(s,a,s^{\prime})$，然后利用贝尔曼方程来近似估计函数 $G\left(\tau_{s_{0}}=s, a_{0}=a\right)$。

$$\begin{aligned} G\left(\tau_{s_0=s, a_{0}=a, s_{1}=s^{\prime}, a_{1}=a^{\prime}}\right) &=r\left(s, a, s^{\prime}\right)+\gamma G\left(\tau_{s 0}=s^{\prime}, a_{0}=a^{\prime}\right) \\ & \approx r\left(s, a, s^{\prime}\right)+\gamma \hat{Q}^{\pi}\left(s^{\prime}, a^{\prime}\right) \end{aligned}$$

相当于把：

$$G\left(\tau_{s_{0}=s, a_{0}=a}\right)$$

改成了：

$$r\left(s, a, s^{\prime}\right)+\gamma \hat{Q}^{\pi}\left(s^{\prime}, a^{\prime}\right)$$

贝尔曼方程的思想精髓在于动态规划，即当前值的计算依赖于上一时刻的值。对于无最终状态的情况，我们定义了折扣率 $\gamma$ 来重点强调现世的回报。

将以上公式结合，可以得到以下计算公式：

$$\hat{Q}^{\pi}(s, a) \leftarrow \hat{Q}^{\pi}(s, a)+\alpha\left(r\left(s, a, s^{\prime}\right)+\gamma \hat{Q}^{\pi}\left(s^{\prime}, a^{\prime}\right)-\hat{Q}^{\pi}(s, a)\right)$$

这种策略学习算法称为 $SARSA$ 算法。

通用 $SARSA$ 算法框架：一个示例

一个通用的 $SARSA$ 算法如下所示：

该算法的大致逻辑如下：

1. 运行完一个回合即一个内循环。
2. 运行直到 $Q$ 函数收敛即为一个外循环。
3. 运行期间动态更新 $Q$ 函数，并基于 $Q$ 函数更新策略 $\pi(s)$。

$SARSA$ 学习算法是一种同策略的时序差分学习算法。

时序差分学习和蒙特卡罗方法的主要不同为：蒙特卡罗需要完整一个路径完成才能知道其总回报，也不依赖马尔可夫性质；而时序差分学习只需要一步，其总回报需要依赖马尔可夫性质来进行近似估计。

Q-learning

$Q$ 学习（$Q-Learning$）算法是一种异策略的时序差分学习算法。在 $Q$ 学习中，$Q$ 函数的估计方法为：

$$Q(s, a) \leftarrow Q(s, a)+\alpha\left(r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)-Q(s, a)\right)$$

相当于让 $Q(s,a)$ 直接去估计最优状态值函数 $Q^{*}(s,a)$。

与 $SARSA$ 异同

$SARSA$ 的迭代公式如下：

$$\hat{Q}^{\pi}(s, a) \leftarrow \hat{Q}^{\pi}(s, a)+\alpha\left(r\left(s, a, s^{\prime}\right)+\gamma \hat{Q}^{\pi}\left(s^{\prime}, a^{\prime}\right)-\hat{Q}^{\pi}(s, a)\right)$$

而 $Q$ 学习算法如下：

$$Q(s, a) \leftarrow Q(s, a)+\alpha\left(r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)-Q(s, a)\right)$$

不管是在 $SARSA$ 算法中，还是在 $Q$ 学习算法中，环境对于当前状态 $s$ 下做出动作 $a$ 的反馈 $r$ 和 $s^{\prime}$ 是不变的。

这里使用 $max$ 的原因是，因为 SARSA 算法本身是同策略的算法，所以其实 $a^\prime$ 就是采样时选的动作，也就是采样时的最佳动作。而 Q learning 因为是异策略算法，我们不能直接使用采样策略的动作 $a^\prime$，不然上面 Q learning 的公式将会退化成为 SARSA 的公式，因此我们要根据我们自己目标策略生成一个动作 $a$，也就是 $max$ 然后基于 $a$ 来计算 $Q$ 函数的值。

下一动作的选择

$SARSA$ 算法与 $Q$ 学习算法对于下一动作 $a^{\prime}$ 的选择都基于采样策略。

状态动作值函数的更新

在 $SARSA$ 算法中，我们使用了同策略下下一状态动作值函数（采样策略）对当前状态动作值函数（目标策略）进行了更新，可知采样策略与更新策略都是策略 $\pi$，所以该算法为同策略的学习算法。

而在 $Q$ 学习算法中，我们可以定义当前策略为 $\pi$，基于当前值函数可计算出的最佳策略为 $\pi^{*}$，在该学习算法中，每一步对于状态动作值函数 $Q(s,a)$ 的更新，都是基于最佳的策略（注意，实际的动作选取并未基于最佳策略，只是在值函数的更新上基于了该最优策略，这是因为回报本身和策略是无关的，只和 $s, a, s^\prime$ 有关），而每一个回合使用的采样策略都是策略 $\pi$，采样策略也会更新，对采样策略 $\pi$ 的更新要到整个算法都结束后才会进行，即

$$\pi(s)=\arg \max _{a \in|\mathcal{A}|} Q(s, a)$$

通用 $Q$ 学习算法框架：一个示例

一个通用的 $Q$ 学习算法如下所示：

该算法的大致逻辑如下：

1. 运行完一个回合即一个内循环。
2. 运行直到 $Q$ 函数收敛即为一个外循环。
3. 运行期间动态更新 $Q$ 函数。
4. 在算法结束时更新策略 $\pi$。

$Q$ 学习算法是一种异策略的时序差分学习算法。

QN 和 DQN

![[nndl-book.pdf#page=358&rect=28,78,458,508&color=annotate

nndl-book, p.343]]

两者区别主要在于 DQN 解决了两个问题：

• 目标不稳定，参数学习目标依赖于参数自身；
• 样本之间具有关联性。

![[nndl-book.pdf#page=359&rect=33,277,362,586&color=annotate

nndl-book, p.344]]