基于值函数的学习方法：贝尔曼方程，动态规划、蒙特卡洛、时续差分、Q网络。

强化学习基于值函数的学习方法。最重要要是SARSA、Q学习、DQN。但是这些都依赖于前面的动态规划和蒙特卡罗方法。

强化学习基础笔记

贝尔曼和贝尔曼最优方程

1. $V(s)$函数和$Q(s,a)$函数
2. 贝尔曼方程（选择所有可能的均值）
3. 贝尔曼最优方程（直接选择最大值）

V函数与Q函数

V函数：以s为初始状态，执行策略$\pi$得到的期望回报（所有轨迹回报的均值）

$$V^{\pi }(s)=E_{\tau \sim p(\tau )}[\sum _{t=0}^{T-1}{r}_{t+1}\mid {\tau }_{s_0}=s]$$

Q函数：以s为初始状态，执行动作a，执行策略$\pi$得到的期望回报

$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

利用V函数去计算Q函数

$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

贝尔曼方程

$V(s)$的贝尔曼方程，选择所有a的期望回报， 也是Q函数的均值，$V(s)=E_a[Q(s,a)]$

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

$Q(s,a)$函数的贝尔曼方程

$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma E_{a\prime \sim \pi (a\prime \mid s\prime )}[Q^{\pi }(s\prime ,a\prime )]]$$

贝尔曼最优方程

$V(s)$函数的贝尔曼最优方程，实际上是直接选择所有a中的最大回报 ：

$$V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$

$Q(s,a)$函数的贝尔曼最优方程

$$Q^{\ast }(s,a)=E_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma \underset{a\prime }{max}{Q}^{\ast }(s^{\prime },a^{\prime })]$$

值函数的学习方法

1. 穷举所有策略选择最好策略（没用）
2. 迭代优化策略，根据策略的值函数去优化策略 （重点）
3. 动态规划（已知状态转移概率$p(s^{\prime }\mid s,a)$和奖励函数$r(s,a,s^{\prime })$）
4. 蒙特卡罗方法（不知模型），先采一些样本，再优化
5. 时序差分学习算法：SARAS和Q学习
6. 深度Q网络

值函数（$V^{\pi }(s)$、$Q^{\pi }(s,a)$ ）用来对策略$\pi (a\mid s)$进行评估。

1. 穷举策略法

如果策略有限，可以对所有策略进行评估，选出最优策略

$$\mathrm{\forall }s,{\pi }^{\ast }=\arg \underset{\pi }{max}{V}^{\pi }(s)$$

策略空间$|\mathcal{A}{|}^{|\mathcal{S}|}$非常大，根本无法搜索。

2. 迭代法优化策略

步骤如下，直到收敛

1. 随机初始化一个策略
2. 计算该策略的值函数：动态规划， 蒙特卡罗
3. 根据值函数来设置新的策略

比如

给一个初始策略$\pi (a\mid s)$， 根据$Q^{\pi }(s,a)$去不断迭代去优化，得到新的策略函数${\pi }^{\prime }(a\mid s)$（确定性策略），直到收敛。

$${\pi }^{\prime }(a\mid s)=\{\begin{array}{lll}& 1& a=\arg \underset{\hat{a}}{max}{Q}^{\pi }(s,\hat{a})\\ & 0& \text{others}\end{array}$$

新策略的值函数会不断变大：

$$Q^{{\pi }^{\prime }}(s,\hat{a})\ge Q^{\pi }(s,\hat{a})$$

动态规划算法

总体思想

1. 思想：已知模型，通过贝尔曼方程来迭代计算值函数，通过值函数去优化策略为固定策略
2. 两种方法：策略迭代-贝尔曼方程（所有可能的均值），值迭代-贝尔曼最优方程（直接）
3. 缺点：要求模型已知，效率太低

基于模型的强化学习，叫做模型相关的强化学习，或有模型的强化学习。

1. 动态规划思想

• 已知模型：状态转移概率$p(s\prime \mid s,a)$ 和奖励$r(s,a,s\prime )$
• 可以通过贝尔曼方程或贝尔曼最优方程来迭代计算值函数$V(s)$ ，再通过$V(s)$去计算$Q(s,a)$
• 通过值函数来优化策略，一般为优化为固定策略$\pi (s)=a$

2. 两种方法

• 策略迭代算法 ： 贝尔曼方程更新值函数，算出所有值函数，计算均值
• 值迭代算法：贝尔曼最优方程更新值函数，直接优化计算最大值

3. 缺点

• 要求模型已知：$p(s\prime \mid s,a)$、 $r(s,a,s\prime )$
• 效率太低：可以通过神经网络来近似计算值函数

策略迭代算法

1. 已知模型：状态转移概率$p(s^{\prime }\mid s,a)$和奖励函数$r(s,a,s^{\prime })$
2. 使用贝尔曼方程迭代计算$V^{\pi }(s)$，求均值， $V^{\pi }(s)=E_a{E}_{s^{\prime }}[r(s,a,s^{\prime })+\gamma V^{\pi }(s\prime )]$
3. 利用$V^{\pi }(s)$去计算$Q^{\pi }(s,a)$。求均值，$Q^{\pi }(s,a)=E_{s\prime }[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$
4. 根据$Q^{\pi }(s,a)$更新策略$\pi (s)=a$，选择最好的动作a，更新为固定策略

1. 初始化策略

$$\mathrm{\forall }s,\mathrm{\forall }a,\pi (a\mid s)=\frac{1}{|\mathcal{A}|}$$

2. 使用贝尔曼方程迭代计算值函数$V^{\pi }(s)$

$$\mathrm{\forall }s,V^{\pi }(s)=E_{a\sim \pi (a\mid s)}{E}_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

3. 利用值函数$V^{\pi }(s)$计算$Q^{\pi }(s,a)$

$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

4. 根据$Q^{\pi }(s,a)$更新策略，选择最好的动作a，更新为固定策略

$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

值迭代算法

1. 最优值函数：最优策略对应的值函数
2. 贝尔曼最优方程：$V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$ ，直接选择最大的a
3. 值迭代算法：最优方程更新值函数$V(s)$， 计算$Q(s,a)$， 更新策略$\pi (s)=a$

1. 最优值函数

最优策略${\pi }^{\ast }$对应的值函数就是最优值函数

$$V^{\ast }(s)=\underset{a}{max}{Q}^{\ast }(s,a)$$

2. 贝尔曼最优方程

$$V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$$$Q^{\ast }(s,a)=E_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma \underset{a\prime }{max}{Q}^{\ast }(s^{\prime },a^{\prime })]$$

3. 值迭代算法

值迭代算法：使用贝尔曼最优方程去更新值函数，收敛时的值函数就是最优值函数，对应的策略也是最优的策略。

1、 初始化值函数

$$\mathrm{\forall }s\in S,V(s)=0$$

2、 使用贝尔曼最优方程更新$V(s)$，直到收敛

$$\mathrm{\forall }s\in S,V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$

3、 计算$Q(s,a)$

$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

4、 更新策略$\pi (s)=a$

$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

5、 输出策略$\pi$

蒙特卡罗采样学习方法

1. 蒙特卡罗方法：随机游走采集样本，估计 $Q^{\pi }(s,a)\approx \frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$，根据Q去改进策略
2. $ϵ\mathrm{贪}\mathrm{心}\mathrm{法}$: 依概率选择${\pi }^{ϵ}(s)=\pi (s)$
3. 同策略和异策略：采样与改进策略相同为同策略
4. 需要拿到完整的轨迹才能对策略评估更新模型，效率较低

模型无关的强化学习也称为无模型的强化学习。蒙特卡罗方法：

在不知$p(s\prime \mid s,a)$、 $r(s,a,s\prime )$ 的情况下， 需要智能体和环境进行交互，并且收集一些样本。然后根据这些样本去求解马尔可夫决策过程最优策略

Q函数$Q^{\pi }(s,a)$，初始状态为$s$， 执行动作$a$后，策略$\pi$能得到的期望总回报。

$$Q^{\pi }(s,a)=E_{\tau \sim p(\tau )}[G(\tau )\mid {\tau }_{s_0}=s,{\tau }_{a_0}=a]$$

模型未知，Q函数可以通过采样来计算。

1. 蒙特卡罗方法

1、从状态$s$、 动作$a$开始随机游走探索环境， 采集N个样本（N个轨迹）

2、得到N个轨迹${\tau }^{(1)},\cdots ,{\tau }^{(N)}$，得到它们的总回报$G({\tau }^{(1)}),\cdots ,G({\tau }^{(N)})$

3、利用轨迹的总回报去估计出$Q^{\pi }(s,a)$ 。 $Q^{\pi }(s,a)\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$

4、基于$Q^{\pi }(s,a)$ 去改进策略， $ϵ$贪心法

5、在新的策略下，再去采集样本、去估计Q，再去改进策略，直到收敛

2. 利用和探索

如果采用确定性策略 :

• 则每次试验得到的轨迹是一样的
• 只能计算出$Q^{\pi }(s,\pi (s))$ ，无法计算出$Q^{\pi }(s,a\prime )$，即无法计算出其它的$a\prime$的Q函数
• 只对当前环境进行了利用，而没有探索
• 而试验的轨迹应该覆盖所有的状态和动作，以找到更好的策略

采用**$ϵ$贪心法**

$${\pi }^{ϵ}(s)=\{\begin{array}{lll}& \pi (s)& \text{依概率 }1-ϵ\\ & a\prime \text{(随机选择)}& \text{依概率 }ϵ\end{array}$$

3. 同策略和异策略

• 同策略：采样策略${\pi }^{ϵ}(s)$， 改进策略${\pi }^{ϵ}(s)$， 相同
• 异策略：采样策略${\pi }^{ϵ}(s)$， 改进策略$\pi (s)$， 不同。可以使用重要性采样、重要性权重来优化$\pi$

时序差分学习算法

总体思想

1. 无需知道完整轨迹就能对策略进行评估。时序差分学习=蒙特卡罗+动态规划
2. 贝尔曼估计轨迹的回报。$G({\tau }_{0:T}^{(N)})=r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime })$
3. 增量计算${\hat{Q}}_N^{\pi }(s,a)$。 ${\hat{Q}}_N^{\pi }(s,a)={\hat{Q}}_{N-1}^{\pi }(s,a)+\alpha \cdot (G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))$

蒙特卡罗方法需要拿到完整的轨迹，才能对策略进行评估。

时序差分学习（temporal-difference learning）结合了动态规划和蒙特卡罗方法。

1. 增量计算${\hat{Q}}_N^{\pi }(s,a)$

蒙特卡罗方法：从状态$s$，动作$a$开始，随机游走，采样N个样本

$G({\tau }^{(N)})$ ：第N次试验的总回报

${\hat{Q}}_N^{\pi }(s,a)$ ：第N次试验后值函数的平均值，推导如下：

$$\begin{array}{rl}{\hat{Q}}_N^{\pi }(s,a)& =\frac{1}{N}\sum _{i=1}^{N}G({\tau }^{(i)})\\ & =\frac{1}{N}(G({\tau }^{(N)})+\sum _{i=1}^{N-1}G({\tau }^{(i)}))\\ & =\frac{1}{N}(G({\tau }^{(N)})+(N-1){\hat{Q}}_{N-1}^{\pi }(s,a))\\ & ={\hat{Q}}_{N-1}^{\pi }(s,a)+\frac{1}{N}(G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))\end{array}$$

值函数${\hat{Q}}_N^{\pi }(s,a)$ ： 第N次后的平均 = N-1次后的平均 + 一个增量， $\alpha$是一个较小的权值。

$${\hat{Q}}_N^{\pi }(s,a)={\hat{Q}}_{N-1}^{\pi }(s,a)+\alpha \cdot (G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))$$

增量 ：实际回报与估计回报直接的误差。

$$\delta =G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a)$$

2. 贝尔曼方程估计$G({\tau }^{(N)})$

从$s,a$开始，采样下一步的状态和动作$(s^{\prime },a^{\prime })$ ，得到奖励$r(s,a,s^{\prime })$。

无需得到完整的轨迹去计算总回报，使用贝尔曼方程去估计第N次试验后面$(s^{\prime },a^{\prime })$的总回报。

使用N-1次实验后的${\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime })$，去估计第N次试验中后续$(s^{\prime },a^{\prime })$的总回报 $G({\tau }_{1:T}^{(N)}\mid {\tau }_{s_1}=s^{\prime },{\tau }_{a_1}=a^{\prime })$。

$$\begin{array}{rl}G({\tau }_{0:T}^{(N)})& =r(s,a,s^{\prime })+\gamma \cdot G({\tau }_{1:T}^{(N)}\mid {\tau }_{s_1}=s^{\prime },{\tau }_{a_1}=a^{\prime })\\ & \approx r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime })\end{array}$$

3. 两种算法

• SARSA：同策略。采样下一个动作：$a^{\prime }={\pi }^{ϵ}(s^{\prime })$，值函数更新$Q(s^{\prime },a^{\prime })$，更新的Q是关于策略${\pi }^{ϵ}$的
• Q学习算法：直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$更新，更新的Q是关于策略$\pi$的。

4. 蒙特卡罗方法和时序差分方法比较

• 蒙特卡罗方法：需要完整路径才能知道总回报，不依赖马尔可夫性质
• 时序差分学习：只需要一步就能知道总回报，依赖于马尔可夫性质

5. 总结

贝尔曼估计总回报（马尔可夫性，动态规划）

$$G(\tau )\leftarrow r(s,a,s^{\prime })+\gamma \cdot Q(s^{\prime },a^{\prime })$$

增量更新值函数（蒙特卡罗）

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (G(\tau )-Q(s,a))$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值}}{\underbrace{r+\gamma \cdot Q(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{Q(s,a)}})$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a)$$

SARSA算法

1. 当前$s,a$， 奖励$r(s,a,s^{\prime })$， 新的$s^{\prime },a^{\prime }$， 优化$Q(s,a)$
2. 贝尔曼估计实际奖励$G(\tau )$：$r+\gamma \cdot Q(s^{\prime },a^{\prime })$
3. 增量计算Q：$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$
4. 更新策略$\pi (s)$ ：$\pi (s)=\arg \underset{a\in \mathcal{A}}{max}Q(s,a)$
5. SARAS：优化所有$Q(s,a)$直到收敛。对每一个$s,a$，每一步状态转移，计算Q，直到s为终止状态

SARASState Action Reward State Action算法，是一种同策略的时序差分学习算法。

1. 思想目的

要算出${\hat{Q}}_N^{\pi }(s,a)$，只需知道下面三项：

• 当前状态和动作$(s,a)$
• 得到的奖励$r(s,a,s^{\prime })$
• 下一步的状态和动作$(s^{\prime },a^{\prime })$

不断优化Q函数，减少实际值和预期值的差距。

2. 核心计算

结合增量计算${\hat{Q}}_N^{\pi }(s,a)$ ， 贝尔曼方程估计$G({\tau }^{(N)})$

$${\hat{Q}}_N^{\pi }(s,a)={\hat{Q}}_{N-1}^{\pi }(s,a)+\alpha \cdot (G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))$$$$G({\tau }_{0:T}^{(N)})=r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime })$$

得到：

$${\hat{Q}}_N^{\pi }(s,a)=(1-\alpha )\cdot {\hat{Q}}_{N-1}^{\pi }(s,a)+\alpha \cdot (r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime }))$$

简单点：

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (G(\tau )-Q(s,a))$$$$G(\tau )\leftarrow r(s,a,s^{\prime })+\gamma \cdot Q(s^{\prime },a^{\prime })$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值}}{\underbrace{r+\gamma \cdot Q(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{Q(s,a)}})$$

3. SARSA算法步骤

输入：状态空间$\mathcal{S}$， 动作空间$\mathcal{A}$，折扣率$\gamma$， 学习率$\alpha$

输出：策略$\pi (s)$

1 初始化

随机初始化$Q(s,a)$，平均初始化策略$\pi (s)$

$$\mathrm{\forall }s,\mathrm{\forall }a,\pi (a\mid s)=\frac{1}{|\mathcal{A}|}$$

2 计算所有$Q(s,a)$， 直到全部收敛

选择初始状态$s$，和动作$a={\pi }^{ϵ}(s)$。从$(s,a)$开始向后执行，直到$s$为终止状态

a. 执行动作，得到新状态和新动作

• 当前状态$s$，动作$a$
• 执行动作$a$：得到奖励$r$和新状态$s^{\prime }$
• 选择新动作：$a^{\prime }={\pi }^{ϵ}(s^{\prime })$

b. 增量计算 $Q(s,a)$

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$$

c. 更新策略$\pi (s)$

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

d. 状态前进

$$s\leftarrow s^{\prime },a\leftarrow a^{\prime }$$

Q学习算法

1. SARAS：$s,a\to r,s^{\prime }$， 选择新状态$a^{\prime }={\pi }^{ϵ}(s^{\prime })$，值函数$Q(s^{\prime },a^{\prime })$
2. Q：$s$，选择当前动作$a={\pi }^{ϵ}(s)$，$\to r,s^{\prime }$，直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$

SARAS是Q学习算法的一种改进。

1. SARAS

1、当前状态$s$，当前动作$a$ （初始时选择$a={\pi }^{ϵ}(s)$，后续是更新得到的）

2、执行动作$a$，得到新状态$s^{\prime }$，得到奖励$r(s,a,s^{\prime })$

4、依概率选择新动作$a={\pi }^{ϵ}(s^{\prime })$，新状态新动作的值函数：$Q(s^{\prime },a^{\prime })$

5、更新Q函数

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$$

6、更新状态和动作：$s=s^{\prime },a=a^{\prime }$

2. Q学习

1、当前状态$s$，选择当前动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$、得到新状态$s^{\prime }$和奖励 $r(s,a,s^{\prime })$

3、不依概率选择新动作，而是直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$

4、更新Q函数

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot \underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })-Q(s,a))$$

5、更新状态：$s=s^{\prime }$

深度Q网络

Q网络

1. Q网络

$\mathbf{s},\mathbf{a}$ 是状态动作$s,a$的向量表达。 用函数$Q_{\varphi }(\mathbf{s},\mathbf{a})\approx Q^{\pi }(s,a)$ 。

参数为$\varphi$的神经网络$Q_{\varphi }(\mathbf{s},\mathbf{a})$，则称为Q网络。输入两个向量，输出为1个实数。

$$Q_{\varphi }(\mathbf{s})=\left[\begin{array}{c}{Q}_{\varphi }(\mathbf{s},{\mathbf{a}}_1)\\ ⋮\\ Q_{\varphi }(\mathbf{s},{\mathbf{a}}_m)\end{array}\right]\approx \left[\begin{array}{c}{Q}^{\pi }(s,a_1)\\ ⋮\\ Q^{\pi }(s,a_1)\end{array}\right]$$

2. 两种逼近

学习一组参数$\varphi$使得$Q_{\varphi }(\mathbf{s},\mathbf{a})$逼近值函数$Q^{\pi }(s,a)$。

蒙特卡罗方法：${\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$，总回报的平均

时序差分方法：$E[r+\gamma Q_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })]$

3. Q学习的目标函数

以Q学习为例，采用随机梯度下降来优化，目标函数（减小差距）如下：

$$L(s,a,s^{\prime };\varphi )={(\underset{\mathrm{实}\mathrm{际}\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })}}-\underset{\text{网络值}}{\underbrace{Q_{\varphi }(\mathbf{s},\mathbf{a})}})}^2$$

一般，标记是一个标量，不包含参数；不依赖于网络参数，与网络独立。

$$J(\theta )=\frac{1}{2m}\sum _{i=1}^m{(\underset{\text{实际目标值}}{\underbrace{y^{(i)}}}-\underset{\mathrm{网}\mathrm{络}\mathrm{值}}{\underbrace{f_{\theta }({\mathbf{x}}^{(i)})}})}^2$$

两个问题：

• 实际目标值不稳定。参数学习的目标依赖于参数本身。label本身也包含参数
• 样本之间有很强的相关性

Deep Q Network

深度Q网络（deep Q-networks, DQN）

• 目标网络冻结。在一个时间段，固定目标值中的参数
• 经验回放。构建经验池来去除数据相关性
• 经验池。最近的经历组成的数据集

带经验回放的DQN算法

带经验回放的深度Q网络。

1. 初始化经验池、Q网络参数、目标Q网络参数

• 经验池： $\mathcal{D}$，容量为N
• Q网络参数：$\varphi$
• 目标Q网络的参数：$\hat{\varphi }=\varphi$

2. 要让$\mathrm{\forall }s,\mathrm{\forall }a,Q_{\varphi }(\mathbf{s},\mathbf{a})$都收敛

每一次初始化起始状态为$s$， 遍历直到$s$为最终态

3. 每一时刻

生成新数据加入经验池

1、状态$s$， 选择动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$， 得到$r$和$s^{\prime }$

3、$(s,a,r,s^{\prime })$ 加入经验池$\mathcal{D}$

采经验池中采样一条数据计算

1、从$\mathcal{D}$中采样一条数据，$(ss,aa,rr,s{s}^{\prime })$。 （去除样本相关性）

2、计算实际目标值$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})$。 （解决目标值不稳定的问题）

$$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})=\{\begin{array}{lll}& rr,& s{s}^{\prime }\mathrm{为}\mathrm{终}\mathrm{态}\\ & rr+\gamma \cdot \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\hat{\varphi }}({\mathbf{ss}}^{\prime },{\mathbf{a}}^{\prime }),& \mathrm{其}\mathrm{它}\end{array}$$

3、损失函数如下，梯度下降法去训练Q网络

$$J(\varphi )={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-y)}^2={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa}))}^2$$

状态前进

$s\leftarrow s^{\prime }$

更新目标Q网络的参数

每隔C步更新：$\hat{\varphi }\leftarrow \varphi$

4. DQN算法中经验池的优点

1、去除样本相关性，避免陷入局部最优

经验池中抽取样本代替当前样本进行训练，打破了与相邻训练样本的相关性，避免陷入局部最优。

2、经验回放类似于监督学习

s

总结

策略迭代

已知模型。利用贝尔曼方程（算均值）迭代计算出$V(s)$，再算出$Q(s,a)$。选择最好的动作$a$去优化策略$\pi (s)$。

$$\mathrm{\forall }s,V^{\pi }(s)=E_{a\sim \pi (a\mid s)}{E}_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

值迭代

已知模型。利用贝尔曼最优方程迭代算出$V(s)$，再算出$Q(s,a)$。选择最好的动作$a$去优化策略$\pi (s)$。

$$\mathrm{\forall }s\in S,V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

蒙特卡罗

未知模型。从$(s,a)$随机游走，采集N个样本。使用所有轨迹回报平均值近似估计$Q(s,a)$ ，再去改进策略。重复，直至收敛。

$$Q^{\pi }(s,a)\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$$

时序差分算法

无需知道完整轨迹就能对策略进行评估。

时序差分学习=动态规划-贝尔曼估计$G(\tau )$ + 蒙特卡罗采样-增量计算$Q(s,a)$

贝尔曼估计轨迹总回报$G(\tau )$

$$G(\tau )\leftarrow r(s,a,s^{\prime })+\gamma \cdot Q(s^{\prime },a^{\prime })$$

增量计算$Q(s,a)$

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值}}{\underbrace{r+\gamma \cdot Q(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{Q(s,a)}})$$

SARSA

同策略的时序差分算法，是Q学习的改进。

1、当前状态$s$，当前动作$a$ （初始时选择$a={\pi }^{ϵ}(s)$，后续是更新得到的）

2、执行动作$a$，得到新状态$s^{\prime }$，得到奖励$r(s,a,s^{\prime })$

4、依概率选择新动作$a={\pi }^{ϵ}(s^{\prime })$，新状态新动作的值函数：$Q(s^{\prime },a^{\prime })$

5、更新Q函数

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$$

6、更新状态和动作：$s=s^{\prime },a=a^{\prime }$

Q学习

1、当前状态$s$，选择当前动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$、得到新状态$s^{\prime }$和奖励 $r(s,a,s^{\prime })$

3、不依概率选择新动作，而是直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$

4、更新Q函数

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot \underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })-Q(s,a))$$

5、更新状态：$s=s^{\prime }$

Q网络

使用神经网络$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})$去近似值函数$Q(s,a)$。两个问题：实际目标值不稳定；样本之间具有强相关性。

$$L(s,a,s^{\prime };\varphi )={(\underset{\mathrm{实}\mathrm{际}\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })}}-\underset{\text{网络值}}{\underbrace{Q_{\varphi }(\mathbf{s},\mathbf{a})}})}^2$$

DQN

深度Q网络：

• 目标网络冻结-稳定目标值。$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})$训练网络，$Q_{\hat{\varphi }}(\mathbf{s}\mathbf{,}\mathbf{a})$目标值网络。定期更新参数$\hat{\varphi }\leftarrow \varphi$
• 经验池的经验回放-去除样本相关性- 每次采集一条数据放入经验池，再从经验池取数据进行训练。

生成新数据加入经验池

1、状态$s$， 选择动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$， 得到$r$和$s^{\prime }$

3、$(s,a,r,s^{\prime })$ 加入经验池$\mathcal{D}$

采经验池中采样一条数据计算

1、从$\mathcal{D}$中采样一条数据，$(ss,aa,rr,s{s}^{\prime })$。 （去除样本相关性）

2、计算实际目标值$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})$。 （解决目标值不稳定的问题）

$$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})=\{\begin{array}{lll}& rr,& s{s}^{\prime }\mathrm{为}\mathrm{终}\mathrm{态}\\ & rr+\gamma \cdot \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\hat{\varphi }}({\mathbf{ss}}^{\prime },{\mathbf{a}}^{\prime }),& \mathrm{其}\mathrm{它}\end{array}$$

3、损失函数如下，梯度下降法去训练Q网络

$$J(\varphi )={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-y)}^2={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa}))}^2$$

状态前进

$s\leftarrow s^{\prime }$

更新目标Q网络的参数

每隔C步更新：$\hat{\varphi }\leftarrow \varphi$