基于值函数的学习方法：贝尔曼方程，动态规划、蒙特卡洛、时续差分、Q网络。
强化学习基于值函数的学习方法。最重要要是SARSA、Q学习、DQN。但是这些都依赖于前面的动态规划和蒙特卡罗方法。
贝尔曼和贝尔曼最优方程
- \(V(s)\)函数和\(Q(s,a)\)函数
- 贝尔曼方程（选择所有可能的均值）
- 贝尔曼最优方程（直接选择最大值）
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^*(s) = \max_\limits{a} E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma V^*(s^\prime)] \] \(Q(s,a)\)函数的贝尔曼最优方程 \[ Q^*(s, a) = E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma \max_\limits{a\prime}Q^*(s^\prime, a^\prime)] \]
值函数的学习方法
- 穷举所有策略选择最好策略（没用）
- 迭代优化策略，根据策略的值函数去优化策略 （重点）
- 动态规划（已知状态转移概率\(p(s^\prime \mid s, a)\)和奖励函数\(r(s, a, s^\prime)\)）
- 蒙特卡罗方法（不知模型），先采一些样本，再优化
- 时序差分学习算法：SARAS和Q学习
- 深度Q网络
值函数（\(V^\pi(s)\)、\(Q^\pi(s, a)\) ）用来对策略\(\pi(a \mid s)\)进行评估。
1. 穷举策略法
如果策略有限，可以对所有策略进行评估，选出最优策略 \[ \forall s, \qquad \pi^* = \arg \max_\limits{\pi} V^\pi(s) \] 策略空间\(\vert \mathcal A\vert^{\vert \mathcal S\vert}\)非常大，根本无法搜索。
2. 迭代法优化策略
步骤如下，直到收敛
- 随机初始化一个策略
- 计算该策略的值函数：
动态规划，蒙特卡罗 - 根据值函数来设置新的策略
比如
给一个初始策略\(\pi(a\mid s)\)， 根据\(Q^\pi(s, a)\)去不断迭代去优化，得到新的策略函数\(\pi^\prime (a\mid s)\)（确定性策略），直到收敛。 \[ \pi^\prime (a\mid s) = \begin {cases} & 1 & a = \arg \max_\limits{\hat a}Q^\pi(s, \hat a) \\ & 0 & \text{others}\\ \end {cases} \] 新策略的值函数会不断变大： \[ Q^{\pi^\prime}(s, \hat a) \ge Q^\pi(s, \hat a) \]
动态规划算法
总体思想
- 思想：已知模型，通过贝尔曼方程来迭代计算值函数，通过值函数去优化策略为固定策略
- 两种方法：策略迭代-贝尔曼方程（所有可能的均值），值迭代-贝尔曼最优方程（直接）
- 缺点：要求模型已知，效率太低
基于模型的强化学习，叫做模型相关的强化学习，或有模型的强化学习。
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)\)
- 效率太低：可以通过神经网络来近似计算值函数
策略迭代算法
- 已知模型：状态转移概率\(p(s^\prime \mid s, a)\)和奖励函数\(r(s, a, s^\prime)\)
- 使用
贝尔曼方程迭代计算\(V^{\pi}(s)\)，求均值， \(V^{\pi}(s) = E_{a}E_{s^\prime}[r(s,a,s^\prime)+ \gamma V^\pi(s\prime)]\)- 利用\(V^{\pi}(s)\)去计算\(Q^{\pi}(s,a)\)。求均值，\(Q^\pi(s, a) = E_{s\prime} [r(s, a, s\prime) + \gamma V^\pi(s\prime)]\)
- 根据\(Q^\pi(s, a)\)更新策略\(\pi(s)=a\)，选择最好的动作a，更新为固定策略
1. 初始化策略 \[
\forall s, \forall a, \quad \pi(a \mid s) = \frac{1}{\vert \cal A\vert}
\] 2. 使用贝尔曼方程迭代计算值函数\(V^\pi(s)\) \[
\forall s, \quad
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，更新为固定策略 \[
\forall s, \qquad \pi(s) = \arg \max_\limits{a} Q(s, a)
\] 
值迭代算法
- 最优值函数：最优策略对应的值函数
- 贝尔曼最优方程：\(V^*(s) = \max_\limits{a} E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma V^*(s^\prime)]\) ，直接选择最大的a
- 值迭代算法：最优方程更新值函数\(V(s)\)， 计算\(Q(s,a)\)， 更新策略\(\pi(s)=a\)
1. 最优值函数
最优策略\(\pi^*\)对应的值函数就是最优值函数 \[
V^*(s) = \max_\limits{a} Q^*(s, a)
\] 2. 贝尔曼最优方程 \[
V^*(s) = \max_\limits{a} E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma V^*(s^\prime)]
\]
\[ Q^*(s, a) = E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma \max_\limits{a\prime}Q^*(s^\prime, a^\prime)] \]
3. 值迭代算法
值迭代算法：使用贝尔曼最优方程去更新值函数，收敛时的值函数就是最优值函数，对应的策略也是最优的策略。
1、 初始化值函数 \[ \forall s \in S, \quad V(s) = 0 \] 2、 使用贝尔曼最优方程更新\(V(s)\)，直到收敛 \[ \forall s \in S, \quad V^*(s) = \max_\limits{a} E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma V^*(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\) \[ \forall s, \quad \pi(s) = \arg \max_\limits{a} Q(s, a) \] 5、 输出策略\(\pi\)
蒙特卡罗采样学习方法
- 蒙特卡罗方法：随机游走采集样本，估计 \(Q^\pi(s, a) \approx \frac{1}{N} \sum_{n=1}^NG(\tau^{(n)})\)，根据Q去改进策略
- \(\epsilon 贪心法\): 依概率选择\(\pi^\epsilon (s) = \pi(s)\)
- 同策略和异策略：采样与改进策略相同为同策略
- 需要拿到完整的轨迹才能对策略评估更新模型，效率较低
模型无关的强化学习也称为无模型的强化学习。蒙特卡罗方法：
在不知\(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}^NG(\tau^{(n)})\)
4、基于\(Q^\pi(s, a)\) 去改进策略， \(\epsilon\)贪心法
5、在新的策略下，再去采集样本、去估计Q，再去改进策略，直到收敛
2. 利用和探索
如果采用确定性策略 :
- 则每次试验得到的轨迹是一样的
- 只能计算出\(Q^\pi(s, \pi(s))\) ，无法计算出\(Q^\pi(s, a\prime)\)，即无法计算出其它的\(a\prime\)的Q函数
- 只对当前环境进行了利用，而没有探索
- 而试验的轨迹应该覆盖所有的状态和动作，以找到更好的策略
采用\(\epsilon\)贪心法 \[ \pi^\epsilon(s) = \begin {cases} & \pi(s) & \text{依概率 } 1-\epsilon \\ & a\prime \quad\text{(随机选择)} & \text{依概率 } \epsilon\\ \end {cases} \] 3. 同策略和异策略
- 同策略：采样策略\(\pi^\epsilon(s)\)， 改进策略\(\pi^\epsilon(s)\)， 相同
- 异策略：采样策略\(\pi^\epsilon(s)\)， 改进策略\(\pi(s)\)， 不同。可以使用重要性采样、重要性权重来优化\(\pi\)
时序差分学习算法
总体思想
- 无需知道完整轨迹就能对策略进行评估。时序差分学习=蒙特卡罗+动态规划
- 贝尔曼估计轨迹的回报。\(G(\tau_{0:T}^{(N)}) = r(s, a, s^\prime) + \gamma \cdot \hat Q^\pi_{N-1}(s^\prime, a^ \prime)\)
- 增量计算\(\hat Q_N^\pi(s,a)\)。 \(\hat Q_N^\pi(s,a) = \hat Q_{N-1}^\pi(s,a) + \alpha \cdot \left(G(\tau ^{(N)}) - \hat Q_{N-1}^\pi(s,a) \right)\)
蒙特卡罗方法需要拿到完整的轨迹，才能对策略进行评估。
时序差分学习（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{align} \hat Q_N^\pi(s,a) & = \frac{1}{N} \sum_{i=1}^NG(\tau ^{(i)}) \\ & = \frac{1}{N} \left(G(\tau ^{(N)}) + \color{blue}{\sum_{i=1}^{N-1}G(\tau ^{(i)})} \right) \\ & = \frac{1}{N} \left(G(\tau ^{(N)}) + \color{blue}{(N-1) \hat Q_{N-1}^\pi(s,a)} \right) \\ & = \hat Q_{N-1}^\pi(s,a) + \frac{1}{N} \left(G(\tau ^{(N)}) - \hat Q_{N-1}^\pi(s,a)\right) \end{align} \] 值函数\(\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 \left(G(\tau ^{(N)}) - \hat Q_{N-1}^\pi(s,a) \right) \] 增量 ：实际回报与估计回报直接的误差。 \[ \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^\pi_{N-1}(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{align} G(\tau_{0:T}^{(N)}) & =r(s, a, s^\prime) + \gamma \cdot \color{blue}{G(\tau_{1:T}^{(N)} \mid \tau_{s_1} = s^\prime, \tau_{a_1} = a^\prime)}\\ & \approx r(s, a, s^\prime) + \gamma \cdot \color{blue}{\hat Q^\pi_{N-1}(s^\prime, a^ \prime)} \end{align} \] 3. 两种算法
- SARSA：同策略。采样下一个动作：\(a^\prime = \pi^\epsilon (s^\prime)\)，值函数更新\(Q(s^\prime, a^\prime)\)，更新的Q是关于策略\(\pi^\epsilon\)的
- Q学习算法：直接选择最大的值函数\(\max_\limits{a^\prime}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 (\underbrace{ r+ \gamma \cdot Q(s^\prime, a^\prime)}_{\color{blue}{实际值}} - \underbrace{Q(s, a)}_{\color{blue}{预期值}}) \]
\[ Q(s, a) \leftarrow Q(s, a) + \alpha \cdot (r+ \gamma \cdot Q(s^\prime, a^\prime) - Q(s, a) \]
SARSA算法
- 当前\(s, a\)， 奖励\(r(s, a, s^\prime)\)， 新的\(s^\prime, a^\prime\)， 优化\(Q(s,a)\)
- 贝尔曼估计实际奖励\(G(\tau)\)：\(r+ \gamma \cdot Q(s^\prime, a^\prime)\)
- 增量计算Q：\(Q(s, a) \leftarrow Q(s, a) + \alpha \cdot (r+ \gamma \cdot Q(s^\prime, a^\prime) - Q(s, a))\)
- 更新策略\(\pi(s)\) ：\(\pi(s) = \arg \max_\limits{a \in \cal A} Q(s, a)\)
- 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 \left(G(\tau ^{(N)}) - \hat Q_{N-1}^\pi(s,a) \right) \]
\[ G(\tau_{0:T}^{(N)}) = r(s, a, s^\prime) + \gamma \cdot \hat Q^\pi_{N-1}(s^\prime, a^ \prime) \]
得到： \[ \hat Q_N^\pi(s,a) = (1-\alpha)\cdot \hat Q_{N-1}^\pi(s,a) + \alpha \cdot \left( r(s, a, s^\prime) + \gamma \cdot \hat Q^\pi_{N-1}(s^\prime, a^ \prime)\right) \] 简单点： \[ 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 (\underbrace{ r+ \gamma \cdot Q(s^\prime, a^\prime)}_{\color{blue}{实际值}} - \underbrace{Q(s, a)}_{\color{blue}{预期值}}) \]
3. SARSA算法步骤
输入：状态空间\(\cal S\)， 动作空间\(\cal A\)，折扣率\(\gamma\)， 学习率\(\alpha\)
输出：策略\(\pi(s)\)
1 初始化
随机初始化\(Q(s,a)\)，平均初始化策略\(\pi(s)\) \[ \forall s, \forall a, \quad \pi(a \mid s) = \frac{1}{\vert \cal A\vert} \] 2 计算所有\(Q(s,a)\)， 直到全部收敛
选择初始状态\(s\)，和动作\(a=\pi^\epsilon(s)\)。从\((s, a)\)开始向后执行，直到\(s\)为终止状态
a. 执行动作，得到新状态和新动作
- 当前状态\(s\)，动作\(a\)
- 执行动作\(a\)：得到奖励\(r\)和新状态\(s^\prime\)
- 选择新动作：\(a^\prime=\pi^\epsilon(s^\prime)\)
b. 增量计算 \(Q(s, a)\) \[
Q(s, a) \leftarrow Q(s, a) + \alpha\cdot \left( r + \gamma \cdot Q(s^\prime, a^\prime) - Q(s, a) \right)
\] c. 更新策略\(\pi(s)\) \[
\pi(s) = \arg \max_\limits{a \in \cal A} Q(s, a)
\] d. 状态前进 \[
s \leftarrow s^\prime, \quad a \leftarrow a^\prime
\] 
Q学习算法
- SARAS：\(s,a \to r, s^\prime\)， 选择新状态\(a^\prime = \pi^\epsilon(s^\prime)\)，值函数\(Q(s^\prime, a^\prime)\)
- Q：\(s\)，选择当前动作\(a= \pi^\epsilon(s)\)，\(\to r, s^\prime\)，直接选择最大的值函数\(\max_\limits{a^\prime}Q(s^\prime, a^\prime)\)
SARAS是Q学习算法的一种改进。
1. SARAS
1、当前状态\(s\)，当前动作\(a\) （初始时选择\(a=\pi^\epsilon(s)\)，后续是更新得到的）
2、执行动作\(a\)，得到新状态\(s^\prime\)，得到奖励\(r(s,a,s^\prime)\)
4、依概率选择新动作\(a = \pi^\epsilon(s^\prime)\)，新状态新动作的值函数：\(Q(s^\prime, a^\prime)\)
5、更新Q函数 \[ Q(s, a) \leftarrow Q(s, a) + \alpha\cdot \left( r + \gamma \cdot Q(s^\prime, a^\prime) - Q(s, a) \right) \] 6、更新状态和动作：\(s = s^\prime, a = a^\prime\)
2. Q学习
1、当前状态\(s\)，选择当前动作\(a = \pi^\epsilon(s)\)
2、执行动作\(a\)、得到新状态\(s^\prime\)和奖励 \(r(s,a,s^\prime)\)
3、不依概率选择新动作，而是直接选择最大的值函数\(\max_\limits{a^\prime}Q(s^\prime, a^\prime)\)
4、更新Q函数 \[ Q(s, a) \leftarrow Q(s, a) + \alpha\cdot \left( r + \gamma \cdot \max_{a^\prime} Q(s^\prime, a^\prime) - Q(s, a) \right) \] 5、更新状态：\(s = s^\prime\)
深度Q网络
Q网络
1. Q网络
\(\mathbf s, \mathbf a\) 是状态动作\(s,a\)的向量表达。 用函数\(Q_\phi(\mathbf s, \mathbf a) \approx Q^\pi (s, a)\) 。
参数为\(\phi\)的神经网络\(Q_\phi(\mathbf s, \mathbf a)\)，则称为Q网络。输入两个向量，输出为1个实数。 \[
Q_\phi(\mathbf s) =
\begin{bmatrix}
Q_\phi(\mathbf s, \mathbf a_1) \\
\vdots \\
Q_\phi(\mathbf s, \mathbf a_m) \\
\end{bmatrix}
\approx
\begin{bmatrix}
Q^\pi(s, a_1) \\
\vdots \\
Q^\pi(s, a_1) \\
\end{bmatrix}
\] 2. 两种逼近
学习一组参数\(\phi\)使得\(Q_\phi(\mathbf s, \mathbf a)\)逼近值函数\(Q^\pi(s, a)\)。
蒙特卡罗方法：\(\hat Q^\pi(s, a) = \frac{1}{N} \sum_{n=1}^NG(\tau^{(n)})\)，总回报的平均
时序差分方法：\(E[r + \gamma Q_\phi(\mathbf s^\prime, \mathbf a^\prime)]\)
3. Q学习的目标函数
以Q学习为例，采用随机梯度下降来优化，目标函数（减小差距）如下： \[ L(s, a, s^\prime; \phi) = \left( \underbrace{r + \gamma \cdot \max_{a^\prime} Q_\phi(\mathbf s^\prime, \mathbf a^\prime)}_{\color{blue}{实际目标值}} - \underbrace{Q_\phi(\mathbf s, \mathbf a)}_{\color{blue}{\text{网络值}}} \right)^2 \] 一般，标记是一个标量，不包含参数；不依赖于网络参数，与网络独立。 \[ J(\theta) = \frac{1}{2m} \sum_{i=1}^m\left ( \underbrace{y^{(i)}}_{\color{blue}{\text{实际目标值}}} - \underbrace{f_\theta(\mathbf x^{(i)}) }_{\color{blue}{网络值}} \right)^2 \] 两个问题：
- 实际目标值不稳定。参数学习的目标依赖于参数本身。label本身也包含参数
- 样本之间有很强的相关性
Deep Q Network
深度Q网络（deep Q-networks, DQN）
- 目标网络冻结。在一个时间段，固定目标值中的参数
- 经验回放。构建经验池来去除数据相关性
经验池。最近的经历组成的数据集
带经验回放的DQN算法
带经验回放的深度Q网络。
1. 初始化经验池、Q网络参数、目标Q网络参数
- 经验池： \(\cal D\)，容量为N
- Q网络参数：\(\phi\)
- 目标Q网络的参数：\(\hat \phi = \phi\)
2. 要让\(\forall s, \forall a, \; Q_\phi(\mathbf s,\mathbf a)\)都收敛
每一次初始化起始状态为\(s\)， 遍历直到\(s\)为最终态
3. 每一时刻
生成新数据加入经验池
1、状态\(s\)， 选择动作\(a = \pi^\epsilon(s)\)
2、执行动作\(a\)， 得到\(r\)和\(s^\prime\)
3、\((s,a, r, s^\prime)\) 加入经验池\(\cal D\)
采经验池中采样一条数据计算
1、从\(\cal D\)中采样一条数据，\((ss,aa, rr, ss^\prime)\)。 （去除样本相关性）
2、计算实际目标值\(Q_{\hat \psi}(\mathbf{ss, aa})\)。 （解决目标值不稳定的问题） \[ Q_{\hat \psi}(\mathbf{ss, aa}) = \begin{cases} & rr, & ss^\prime 为终态 \\ & rr + \gamma \cdot \max_\limits{\mathbf a^\prime}Q_{\hat \phi}(\mathbf {ss^\prime}, \mathbf {a^\prime}), &其它 \end{cases} \] 3、损失函数如下，梯度下降法去训练Q网络 \[ J(\phi) = \left ( Q_{\phi}(\mathbf {ss}, \mathbf {aa}) - y \right)^2 =\left ( Q_{\phi}(\mathbf {ss}, \mathbf {aa}) - Q_{\hat \psi}(\mathbf{ss, aa}) \right)^2 \] 状态前进
\(s \leftarrow s^\prime\)
更新目标Q网络的参数
每隔C步更新：\(\hat \phi \leftarrow \phi\)
4. DQN算法中经验池的优点
1、去除样本相关性，避免陷入局部最优
经验池中抽取样本代替当前样本进行训练，打破了与相邻训练样本的相关性，避免陷入局部最优。
2、经验回放类似于监督学习
s
总结
策略迭代
已知模型。利用贝尔曼方程（算均值）迭代计算出\(V(s)\)，再算出\(Q(s,a)\)。选择最好的动作\(a\)去优化策略\(\pi(s)\)。 \[
\forall s, \quad
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)] \]
\[ \forall s, \qquad \pi(s) = \arg \max_\limits{a} Q(s, a) \]
值迭代
已知模型。利用贝尔曼最优方程迭代算出\(V(s)\)，再算出\(Q(s,a)\)。选择最好的动作\(a\)去优化策略\(\pi(s)\)。 \[ \forall s \in S, \quad V^*(s) = \max_\limits{a} E_{s^\prime \sim p(s^\prime \mid s, a)}[r(s, a, s^\prime) + \gamma V^*(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)] \]
\[ \forall s, \quad \pi(s) = \arg \max_\limits{a} 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}^NG(\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 (\underbrace{ r+ \gamma \cdot Q(s^\prime, a^\prime)}_{\color{blue}{实际值}} - \underbrace{Q(s, a)}_{\color{blue}{预期值}}) \]
SARSA
同策略的时序差分算法，是Q学习的改进。
1、当前状态\(s\)，当前动作\(a\) （初始时选择\(a=\pi^\epsilon(s)\)，后续是更新得到的）
2、执行动作\(a\)，得到新状态\(s^\prime\)，得到奖励\(r(s,a,s^\prime)\)
4、依概率选择新动作\(a = \pi^\epsilon(s^\prime)\)，新状态新动作的值函数：\(Q(s^\prime, a^\prime)\)
5、更新Q函数 \[ Q(s, a) \leftarrow Q(s, a) + \alpha\cdot \left( r + \gamma \cdot Q(s^\prime, a^\prime) - Q(s, a) \right) \] 6、更新状态和动作：\(s = s^\prime, a = a^\prime\)
Q学习
1、当前状态\(s\)，选择当前动作\(a = \pi^\epsilon(s)\)
2、执行动作\(a\)、得到新状态\(s^\prime\)和奖励 \(r(s,a,s^\prime)\)
3、不依概率选择新动作，而是直接选择最大的值函数\(\max_\limits{a^\prime}Q(s^\prime, a^\prime)\)
4、更新Q函数 \[ Q(s, a) \leftarrow Q(s, a) + \alpha\cdot \left( r + \gamma \cdot \max_{a^\prime} Q(s^\prime, a^\prime) - Q(s, a) \right) \] 5、更新状态：\(s = s^\prime\)
Q网络
使用神经网络\(Q_{\phi}(\mathbf{s,a})\)去近似值函数\(Q(s,a)\)。两个问题：实际目标值不稳定；样本之间具有强相关性。 \[ L(s, a, s^\prime; \phi) = \left( \underbrace{r + \gamma \cdot \max_{a^\prime} Q_\phi(\mathbf s^\prime, \mathbf a^\prime)}_{\color{blue}{实际目标值}} - \underbrace{Q_\phi(\mathbf s, \mathbf a)}_{\color{blue}{\text{网络值}}} \right)^2 \]
DQN
深度Q网络：
- 目标网络冻结-稳定目标值。\(Q_{\phi}(\mathbf{s,a})\)训练网络，\(Q_{\hat \phi}(\mathbf{s,a})\)目标值网络。定期更新参数\(\hat \phi \leftarrow \phi\)
- 经验池的经验回放-去除样本相关性- 每次采集一条数据放入经验池，再从经验池取数据进行训练。
生成新数据加入经验池
1、状态\(s\)， 选择动作\(a = \pi^\epsilon(s)\)
2、执行动作\(a\)， 得到\(r\)和\(s^\prime\)
3、\((s,a, r, s^\prime)\) 加入经验池\(\cal D\)
采经验池中采样一条数据计算
1、从\(\cal D\)中采样一条数据，\((ss,aa, rr, ss^\prime)\)。 （去除样本相关性）
2、计算实际目标值\(Q_{\hat \psi}(\mathbf{ss, aa})\)。 （解决目标值不稳定的问题） \[
Q_{\hat \psi}(\mathbf{ss, aa}) =
\begin{cases}
& rr, & ss^\prime 为终态 \\
& rr + \gamma \cdot \max_\limits{\mathbf a^\prime}Q_{\hat \phi}(\mathbf {ss^\prime}, \mathbf {a^\prime}), &其它
\end{cases}
\] 3、损失函数如下，梯度下降法去训练Q网络 \[
J(\phi)
= \left ( Q_{\phi}(\mathbf {ss}, \mathbf {aa}) - y \right)^2
=\left ( Q_{\phi}(\mathbf {ss}, \mathbf {aa}) - Q_{\hat \psi}(\mathbf{ss, aa}) \right)^2
\] 状态前进
\(s \leftarrow s^\prime\)
更新目标Q网络的参数
每隔C步更新：\(\hat \phi \leftarrow \phi\)
