tf2.0学习（十一）——强化学习

前边介绍了TensorFlow的基本操作和神经网络的很多知识：
tf2.0学习（一）——基础知识
 tf2.0学习（二）——进阶知识
 tf2.0学习（三）——神经网络
 tf2.0学习（四）——反向传播算法
下面介绍一下强化学习

强化学习是机器学习领域，除有监督学习、无监督学习之外的另一个分支，它主要用智能体与环境的交互，来实现获得良好结果的策略。与有监督学习不同，强化学习并没有明确的标注信息，只有来自环境的反馈的奖励信息，通常具有一定的滞后性。本章主要介绍DQN算法和PPO算法。

11.1 先睹为快

本节先通过一个简单的例子，感受一下强化学习的魅力。本节以直观感受为主，不需要掌握细节。

11.1.1 平衡杆游戏

如图所示，平衡杆游戏包含3个部分，杆，小车，滑轨。小车可以在滑轨上自由移动，杆的一侧通过轴承固定在小车上。初始状态时，小车位于滑轨中央，杆竖立在小车上。智能体通过移动小车，来控制杆的平衡。当杆与竖直方向的角度大于某个值或小车偏离中间位置一定距离后，游戏结束。

平衡杆游戏

为了简化环境状态的表示，我们直接取高层的环境变量s作为智能体的输入，它一共包含4个特征，小车位置，小车速度，杆角度，杆速度。智能体的输出动作a为向左移动或向右移动。输出动作施加到平衡杆系统上会产生一个新的状态，并得到一个奖励，这个奖励可以简单设置为1，表示时长加1。在每个时间戳t上面，智能体通过环境状态

s_t

产生动作

a_t

，动作

a_t

到环境上产生新的环境状态

s_{t+1}

，并获得奖励

r_t

。

11.1.2 Gym平台

在强化学习中，可以直接通过机器人与真实环境进行交互，并通过传感器获得环境状态与奖励。但由于真实环境实验有一定复杂性和成本较高的问题，一般在虚拟环境上进行实验。
Gym平台是个虚拟的游戏环境平台，只需要通过少量python代码，就可以实现游戏环境的搭建与交互。

import gym

env = gym.make("CartPole-v1")
observation = env.reset()

for _ in range(1000):
    env.render()
    action = env.action_space.sample()
    observation, reward, done, info = env.step(action)
    if done:
        observation = env.reset()
env.close()

11.1.3 策略网络

下边是强化学习中最为关键的环节，如何进行判断和决策。我们把判断和决策叫做策略（Policy）。策略的输入是状态s，输出是某个具体的动作a或着动作的分布 $\pi_{\theta} (a|s)$ ，其中 $\theta$ 为策略函数 $\pi$ 的参数，可以用神经网络来参数化 $\pi_{\theta}$ 函数。
如下图，神经网络的输入是平衡杆系统的状态s，输出为所有动作的概率 $\pi_{\theta}(a|s)$ ，即P(向左|s)，P(向右|s)。并且：
$\sum_{a \in A} \pi_{\theta}(a|s) = 1$
其中A为所有动作的集合。 $\pi_{\theta}$ 网络代表了智能体的策略，称为策略网络。

策略网络

策略网络的创建过程跟普通网络一样:

class Policy(tf.keras.Model):
    def __init__(self):
        super(Policy, self).__init__()
        self.data = [] 
        self.fc1 = tf.keras.layers.Dense(128, kernel_initializer='he_normal')
        self.fc2 = tf.keras.layers.Dense(2, kernel_initializer='he_normal')

        self.optimizer = tf.optimizers.Adam(learning_rate=0.001)

    def call(self, inputs, training=None):
        x = self.fc1(inputs)
        x = tf.nn.relu(x)
        x = self.fc2(x)
        x = tf.nn.softmax(x, axis=1)
        return x 

    def put_data(self, item):
        self.data.append(item)

11.1.4 梯度更新

如果希望用梯度下降算法来优化网络参数，需要知道每个输入 $s_t$ 的标注信息 $a_t$ ，并且确保输入到损失值是连续可导的。强化学习和传统的有监督学习不同，主要体现在强化学习的标注并没有一个明确的好坏标准。奖励r可以一定程度上反应动作的好坏，但不能直接决定每个时间戳的动作。甚至有些游戏交互过程只有一个最终的代表游戏结果的奖励r，如围棋。那么给每个状态定义一个最优的动作 $a^*_t$ 合理吗。首先游戏中的状态总数是非常巨大的，其次每个状态很难定义一个最优动作，有些动作虽然短期回报不高，但长期回报却是好的。

因此，策略网络的优化目标不应该是让每个输入 $s_t$ 的输出尽量接近标注结果，而是要最大化总回报的期望。总回报是指从游戏开始到游戏结束之间的奖励和 $\sum r_t$ 。

一个好的策略应该能让总回报的期望值最高 $J(\pi_\theta)$ 。根据梯度上升算法，参数更新如下：
$\theta_{t+1} = \theta_{t} + \eta \frac{\partial J(\theta)}{\partial \theta}$

然而遗憾的是，总回报期望 $J({\theta})$ 是环境给的，如果不知道游戏模型，是不可能通过自动微分求得 $\frac{\partial J({\theta})}{\partial \theta}$ 的。

那么能不能在不知道 $J({\theta})$ 的前提下，得到 $\frac{\partial J({\theta})}{\partial \theta}$ 呢，其实是可以的，下面先给出表达式：
$\frac{\partial J({\theta})}{\partial \theta} = \mathbb{E}_{\tau \sim p_{\theta}(\tau) } [(\sum_{t=1}^{T}\frac{\partial}{\partial \theta} log \pi_{\theta}(a_t|s_t))R(\tau)]$

利用上边公式，只需要计算出 $\frac{\partial}{\partial \theta} log \pi_{\theta}(a_t|s_t)$ ，并乘以 $R(\tau)$ 就可以更新计算出 $\frac{\partial J({\theta})}{\partial \theta}$ ，按照 $\theta^{*} = \theta - \eta \frac{\partial L}{\partial \theta}$ 的方式更新策略网络，就可以最大化 $J(\theta)$ 。其中 $R(\tau)$ 为某次交互的总回报， $\tau$ 为交互轨迹 $s_1,a_1,r_1,s_2,a_2,r_2,...s_t,a_t,r_t$ 。

11.2 强化学习问题

首先要了解一下强化学习的相关概念。具有感知和决策能力的对象叫做智能体（Agent）,他可以是一段算法代码，可以是软硬件系统。智能体通过与外界环境进行交互完成某个动作。这里的环境（Environmont）是指接收到智能体的动作而产生影响，并给出相应反馈的外界环境的总和。对于智能体来说，他通过感知外界环境的状态（State），作出相应的动作（Action）。对于环境来说，它从某个初始状态 $s_1$ 开始，通过接受智能体的动作而动态改变自身的状态，并给出相应的奖励（Reward）。

从概率角度描述强化学习过程，包括5个基本对象：

状态s
反应了环境的状态特征，在时间戳t上的状态记为 $s_t$ ，他可以是原始的视觉图像，语音，文本等信息，也可以是高层抽象的特征，如小车速度，位置等数据。
动作a
智能体通过感知环境状态后作出的行为，在时间戳t上记作 $a_t$ 。
策略 $\pi(a|s)$
代表了智能体的决策模型，接受输入状态s，给出决策后执行动作的概率分布 $p(a|s)$ ，满足
$\sum_{a \in A}\pi(a|s) = 1$
这种具有一定随机性的概率输出称为随机性策略。对应的为确定性策略。
奖励 $r(s, a)$
表示环境s在接受动作a之后，给出的反馈信号，一般是个标量，在一定程度上表明了动作的好坏。在时间戳t上的奖励记作 $r_t$ ，奖励一般具有滞后性。
状态转移概率 $p(s^{'}|s, a)$
表示当前状态s在接受动作a之后，改变后的状态 $s^{'}$ 的概率分布，满足
$\sum_{s^{'} \in S}p(s^{'}|s, a) = 1$

智能体与环境的交互

11.2.1 马尔科夫决策过程

智能体从环境的初始状态 $s_1$ 开始，通过策略模型 $\pi(a|s)$ 采取某个具体的动作 $a_1$ 执行，环境收到动作 $a_1$ 的影响，根据状态转移模型 $p(s^{'}|s, a)$ 产生新的状态 $s_2$ ，同时给出智能体的反馈信号：奖励 $r_1$ 。如此循环，知道游戏结束，产生了一系列的有序数据:
$s_1, a_1, r_1, s_2, a_2, r_2 ... s_T$

这个序列代表了智能体与环境的一次交互过程，叫做轨迹（Trajectory），记作 $\tau$ ，一次交互过程叫做一个回合（Episode），T表示该回合的时间戳数。

在状态 $s_1, s_2, s_3, ... s_t$ 之后出现 $s_{t+1}$ 的概率 $p(s_{t+1} | s_1, s_2, ... s_t)$ 是非常重要的，但是他的计算非常复杂，为了简化我们假设状态 $s_{t+1}$ 至于上一个状态 $s_t$ 相关。即：
$p(s_{t+1} | s_1, s_2, ... s_t) = p(s_{t+1} | s_t)$

当一个状态只与它上一个状态相关，跟之前的状态都不相关时，这个性质叫做马尔科夫性，具有马尔科夫性的序列 $s_1, s_2, s_3, ... s_t$ 叫做马尔可夫过程。

如果将执行动作a也考虑进去的话，那么下一步的状态就跟上一步的状态和动作相关，即
$p(s_{t+1} | s_1, a_1, s_2, a_2, ... s_t, a_t) = p(s_{t+1}|s_t, a_t)$
我们把动作和状态的序列 $s_1, a_1, s_2, a_2, ... s_T$ 叫做马尔科夫决策过程（MDP）。
现在我们看某个轨迹：
$\tau = s_1, a_1, r_1, s_2, a_2, r_2, ... s_T$
发生 $p(\tau)$ 的概率为：
$p(\tau) = p(s_1, a_1, r_1, s_2, a_2, r_2, ... s_T)$
$=p(s_1)\pi(a_1|s_1)p(s_2|s_1, a_1)\pi(a_2|s_2)p(s_3|s_1,a_1,s_2,a_2)...$
引入马尔科夫后，简化为：
$p(\tau) = p(s_1) \prod_{t=1}^{T-1}\pi(a_t|s_t)p(s_{t+1}|s_t, a_t)$
马尔科夫决策过程如下所示：

马尔科夫决策过程

如果能获得状态转移概率 $p(s_{t+1}|s_t, a_t)$ 和奖励模型 $r(s, a)$ ，可以直接迭代计算值函数，这种已知环境模型的方法叫做给予模型的强化学习。但现实世界中的环境模型大多是未知的，这种模型无关的方法叫做模型无关的强化学习，接下来主要介绍模型无关的强化学习算法。

11.2.2 目标函数

每次智能体与环境交互的过程都会得到一个滞后的奖励信号
$r_t = r(s_t, a_t)$
一次交互轨迹 $\tau$ 的累积激励：
$R(\tau) = \sum_{t=1}^{T-1} r_t$

有些时候需要权衡近期激励与长期激励的重要性，更多的是使用随着时间衰减的折扣回报：
$R(\tau) = \sum_{t=1}^{T-1} \gamma^{t-1}r_t$

其中 $\gamma \in [0, 1]$ 叫做折扣率。

强化学习的目标是最大化期望回报:
$J(\pi_{\theta}) = \mathbb{E}_{\tau \sim p(\tau)} [R(\tau)] = \mathbb{E}_{\tau \sim p(\tau)} [\sum_{t=1}^{T-1} \gamma^{t-1}r_t]$

其中 $p(\tau)$ 表示轨迹的分布。它由状态转移概率 $p(s^{'}|s, a)$ 和策略 $\pi(a|s)$ 共同决定，策略 $\pi$ 的好坏可以通过 $J(\pi_{\theta})$ 来衡量，期望回报越大策略越优良，反之策略越差。

11.3 策略梯度方法

强化学习就是找到最优策略 $\pi_{\theta}(a|s)$ 使得期望回报 $J(\theta)$ 最大，这类优化问题和有监督优化类似，需要求解期望回报对于网络参数 $\theta$ 得偏导数 $\frac{\partial J(\theta)}{\partial \theta}$ ，在利用梯度下降算法更新参数：
$\theta^{*} = \theta + \eta \frac{\partial J}{\partial \theta}$
其中 $\eta$ 为学习率。

现在问题是求 $\frac{\partial J}{\partial \theta}$ ：
$\frac{\partial J}{\partial \theta} = \frac{\partial}{\partial \theta} \int \pi_{\theta}(\tau)R(\tau)d\tau$
再将导数符号放到积分符号内部：
$= \int(\frac{\partial \pi_{\theta}(\tau)}{\partial \theta})R(\tau)d\tau$

$=\int \pi_{\theta}(\tau) (\frac{1}{\pi_{\theta}(\tau)} \frac{\partial}{\partial \theta} \pi_{\theta}(\tau)) R(\tau) d\tau$

由于：
$\frac{dlog(f(x))}{dx} = \frac{1}{f(x)} \frac{d f(x)}{dx}$
因此：
$\frac{1}{\pi_{\theta}(\tau)}\frac{\partial \pi_{\theta}(\tau)}{\partial \theta} = \frac{\partial log \pi_{\theta}(\tau)}{\partial \theta}$
带入：
$= \int \pi_{\theta}(\tau) (\frac{\partial}{\partial \theta} log \pi_{\theta}(\tau))R(\tau) d\tau$

即：
$\frac{\partial J}{\partial \theta} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} [\frac{\partial}{\partial \theta} log \pi_{\theta}(\tau)R(\tau)]$

其中 $log \pi_{\theta}(\tau)$ 代表了轨迹 $\tau = s_1, a_1, s_2, a_2, ... s_T$ 的概率值再取log。又由于 $R(\tau)$ 可以由采样得到，所以问题的关键变成了 $\frac{\partial}{\partial \theta} log \pi_{\theta}(\tau)$ 。
$\frac{\partial}{\partial \theta} log \pi_{\theta}(\tau) = \frac{\partial}{\partial \theta} log \left(p(s_1) \prod_{t=1}^{T-1}\pi_{\theta}(a_t|s_t)p(s_{t+1} | s_t, a_t) \right)$
$=\frac{\partial}{\partial \theta} \left( log p(s_1) + \sum_{t=1}^{T-1} log \pi_{\theta}(a_t|s_t) + logp(s_{t+1}|s_t, a_t) \right)$
$=\sum_{t=1}^{T-1}\frac{\partial}{\partial \theta} log \pi_{\theta}(a_t|s_t)$
再将其带入 $\frac{\partial J}{\partial \theta}$ ：
$\frac{\partial J}{\partial \theta} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[\left( \sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta} (a_t|s_t) R(\tau) \right)\right]$

策略梯度算法流程

11.3.1 REINFORCE 算法

根据大数法则，将上边期望写成多条 $\tau^{n},n \in [1, N]$ 轨迹的采样均值。
$\frac{\partial J(\theta)}{\partial \theta} = \frac{1}{N} \sum_{n = 1}^{N}\left[\left(\sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta}(a_t^{(n)}|s_t^{(n)}) R(\tau)^{(n)} \right) \right]$
其中N为轨迹的数量。得到梯度之后，再根据梯度上升算法更新参数 $\theta$ 。这种算法称为REINFORCE算法。

REINFORCE算法：

随即初始化参数 $\theta$
repeat:
根据策略 $\pi_{\theta}(a_t\|s_t)$ 与环境交互，产生多条轨迹 $\tau^{(n)}$
计算 $R(\tau^{(n)})$
计算 $\frac{\partial J(\theta)}{\partial \theta} = \frac{1}{N} \sum_{n = 1}^{N}\left[\left(\sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta}(a_t^{(n)}\|s_t^{(n)}) R(\tau)^{(n)} \right) \right]$
更新网络参数 $\theta^{'} = \theta + \eta \frac{\partial J(\theta)}{\partial \theta}$
until: 训练达到指定回合数
输出策略网络: $\pi_{\theta}(a_t \| s_t)$

11.3.2 原始策略梯度的改进

原始的REINFORCE算法由于优化轨迹之间的方差很大，收敛速度较慢，训练过程并不够平滑。我们可以功过方差缩减的思想从因果性和基准线两个角度进行改进。
因果性 考虑 $\frac{\partial J(\theta)}{\partial \theta}$ 的票导数表达式，对于时间戳为t的动作 $a_t$ ，它对 $\tau_{1:t-1}$ 并没有影响，只对后续的回报 $\tau_{t:T}$ 起作用。
$\frac{\partial J(\theta)}{\partial \theta} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[\left( \sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta} (a_t|s_t) R(\tau_{t:T}) \right)\right]$
$= \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[\left( \sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta} (a_t|s_t) \hat{Q}(s_t, a_t) \right)\right]$
其中 $\hat{Q}(s_t, a_t)$ 表示状态 $s_t$ 执行动作 $a_t$ 后 $\pi_{\theta}$ 的回报值。

基准线 真实环境的奖励 $r_t$ 并不是分布在0周围的。很多游戏的奖励全是正数，使得 $R(\tau)$ 总是大于0的。会导致网络倾向于增加所有采样到的动作的概率，而为采样到的动作出现的概率也就相应的下降了。这并不是我们希望的，我们希望 $R(\tau)$ 能分布在0附近。因此引入一个偏置b，作为基准线，它代表了回报 $R(\tau)$ 的平均水平。
$\frac{\partial J(\theta)}{\partial \theta} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[\left( \sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta} (a_t|s_t) (\hat{Q}(s_t, a_t) - b) \right)\right]$
根据推算，添加基准线并不会改变 $\frac{\partial J(\theta)}{\partial \theta}$ 。

11.3.3 带基准的REINFORCE算法

基准线b可以通过蒙特卡洛算法进行估计。
$b = \frac{1}{N}\sum_{n=1}^{N}R(\tau_{t:T}^{(n)})$

种算法称为REINFORCE算法。

带基准的REINFORCE算法：

随即初始化参数 $\theta$
repeat:
根据策略 $\pi_{\theta}(a_t\|s_t)$ 与环境交互，产生多条轨迹 $\tau^{(n)}$
计算 $\hat{Q}(s_t, a_t)$
通过蒙特卡洛算法计算b
计算 $\frac{\partial J(\theta)}{\partial \theta} = \frac{1}{N} \sum_{n = 1}^{N}\left[\left(\sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta}(a_t^{(n)}\|s_t^{(n)}) （\hat{Q}(s_t, a_t) - b） \right) \right]$
更新网络参数 $\theta^{'} = \theta + \eta \frac{\partial J(\theta)}{\partial \theta}$
until: 训练达到指定回合数
输出策略网络: $\pi_{\theta}(a_t \| s_t)$

11.3.4 重要性采样

前边介绍的策略梯度方法在更新网络参数后，策略网络 $\pi_{\theta}(a_t | s_t)$ 即发生了改变，必须使用新的策略网络进行采样，而前边采样的历史轨迹数据则不能使用，采样效率非常低下。怎么提高采样效率，重用过去旧策略产生的轨迹数据呢？

在统计学中，重要性采样技术可以通过一个分布q来计算原分布p的期望。考虑轨迹 $\tau$ 采样自分布p，我们希望估计轨迹 $\tau \sim p$ 的期望 $\mathbb{E}_{\tau \sim p}[f(\tau)]$ ：
$\mathbb{E}_{\tau \sim p}[f(\tau)] = \int p(\tau)f(\tau)d\tau$
$=\int \frac{p(\tau)}{q(\tau)}q(\tau)f(\tau)d\tau$
$= \mathbb{E}_{\tau \sim q}\left[ \frac{p(\tau)}{q(\tau)} f(\tau) \right]$

通过推到我们发现， $f(\tau)$ 的分布可以不从原分布p中进行采样，而通过另一个分布q中进行采样，只需要乘以 $\frac{p(\tau)}{q(\tau)}$ 的一个比率。这在统计学中叫做重要性采样。

令待优化目标策略分布为 $p_{\theta}(\tau)$ ，历史的某个策略分布为 $p_{\tilde{\theta}}(\tau)$ ，我们希望用历史的采样轨迹 $\tau \sim p_{\tilde{\theta}}(\tau)$ 来估计目标策略网络的期望回报。
$J(\theta) = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} [R(\tau)]$
$=\sum_{t=1}^{T-1}\mathbb{E}_{s_t \sim p_{\theta}(s_t)} \mathbb{E}_{a_t \sim \pi_{\theta}(a_t|s_t)}[r(s_t, a_t)]$
根据冲采样技术：
$=\sum_{t=1}^{T-1}\mathbb{E}_{s_t \sim p_{\tilde{\theta}}(s_t)} \left[ \frac{p_{\theta}(s_t)}{p_{\tilde{\theta}}(s_t)} \mathbb{E}_{a_t \sim \pi_{\tilde{\theta}}(a_t|s_t)} \left[ \frac{\pi_{\tilde{\theta}}(a_t|s_t)}{\pi_{\theta}(a_t|s_t)} r(s_t, a_t) \right] \right]$
我们认为状态 $s_t$ 在不同策略下出现的概率分布近似相等， $\frac{p_{\tilde{\theta}}(s_t)}{p_{\theta}(s_t)} = 1$ 。
$=\sum_{t=1}^{T-1}\mathbb{E}_{(s_t, a_t) \sim p_{\tilde{\theta}}(s_t, a_t)}\left[\frac{\pi_{\tilde{\theta}}(a_t | s_t)}{\pi_{\theta}(a_t|s_t)} r(s_t, a_t) \right]$

11.3.5 PPO算法

引入了重要性采样技术后，采样效率大大提升。比较流行的Off-Policy算法有TRPO和PPO，其中TRPO是PPO算法的前身。
TRPO 为了约束目标策略 $\pi_{\tilde{\theta}}(a_t|s_t)$ 和采样策略 $\pi_{\theta}(a_t|s_t)$ 之间的距离，TRPO算法用KL散度来计算两个策略之间的期望距离，并作为优化问题的约束项。
$\theta^{*} = \arg \underset{\theta} {max} \hat{\mathbb{E}}\left[\frac{\pi_{\tilde{\theta}}(a_t | s_t)}{\pi_{\theta}(a_t|s_t)} \hat{A}_t \right]$
$s.t. \mathbb{\hat{E}}\left[D_{KL}(\pi_{\theta}(|s_t) || \pi_{\tilde{\theta}}(|s_t)) \right] <= \delta$

PPO 将TRPO中的约束条件作为惩罚项加进了损失函数。
$\theta^{*} = \arg \underset{\theta} {max} \hat{\mathbb{E}}\left[\frac{\pi_{\tilde{\theta}}(a_t | s_t)}{\pi_{\theta}(a_t|s_t)} \hat{A}_t \right] - \beta \mathbb{\hat{E}}\left[D_{KL}(\pi_{\theta}(|s_t) || \pi_{\tilde{\theta}}(|s_t)) \right]$

11.4 值函数方法

策略梯度方法通过直接参数化策略网络，从而获得更好的策略模型。还有一种通过建模值函数间接获得策略的方法，我们统称为值函数方法。

11.4.1 值函数

在强化学习中，有两给值函数，分别是状态值函数和状态-动作值函数，两者均表示在策略 $\pi$ 下的期望回报，轨迹起点定义不一样。
状态值函数(State Value Function，简称V函数)，它定义为状态从 $s_t$ 开始，在策略 $\pi$ 控制下能获得的期望回报：
$V^{\pi}(s_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[ R(\tau_{t:T}) | \tau_t = s_t \right]$
其中：
$R(\tau_{t:T}) = r_t + \gamma R(\tau_{t+1:T})$
因此：
$V^{\pi}(s_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[ r_t + \gamma R(\tau_{t+1:T}) \right]$
$=\mathbb{E}_{\tau \sim p(\tau)}\left[ r_t + \gamma V^{\pi}(s_{t+1}) \right]$
最优策略 $\pi^*$ :
$\pi^* = \arg \underset{\pi} {max} V^{\pi}(s), s \in S$
此时状态值函数取最大时：
$V^*(s) = \underset{\pi}{max} V^{\pi}(s), s \in S$
对于最优策略，同样满足：
$V^*(s_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[ r_t + \gamma V^*(s_{t+1}) \right]$
状态值函数的前提是，在某个策略下上述所有计算均是计算最优策略下的状态值函数。

状态-动作值函数(State-Action Value Function，也叫Q函数)，它定义为从状态 $s_t$ 并执行动作 $a_t$ 的双重设定下，在策略 $\pi$ 控制下能获得的期望回报值。
$Q^{\pi}(s_t, a_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[ R(\tau_{t:T}) | \tau_{s_t} = s_t, \tau_{a_t} = a_t \right]$
通过推到可得：
$Q^{\pi}(s_t, a_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[r(s_t, a_t) + \gamma V^{\pi}(s_{t+1}) \right]$
其中 $s_t, a_t$ 为确定值，因此 $r(s_t, a_t)$ 也为确定值。
V函数和Q函数存在如下关系：
$V^{\pi}(s_t) = \mathbb{E}_{a_t \sim \pi(a_t|s_t)} [Q^{\pi}(s_t, a_t)]$
即当 $a_t$ 采样自策略 $\pi(a_t|s_t)$ 时， $Q^{\pi}(s_t, a_t)$ 的期望与 $V^{\pi}(s_t)$ 相等。在最优策略 $\pi^*(a_t|s_t)$ 下，有如下关系：
$Q^*(s_t, a_t) = \underset{\pi}{max} Q^{\pi}(s_t, a_t)$
$\pi^*(a_t|s_t) = \underset{a_t}{argmax}Q^*(s_t, a_t)$
也满足：
$V^*(s_t) = \underset{a_t}{max}Q^*(s_t, a_t)$
此时：
$Q^{*}(s_t, a_t) = \mathbb{E}_{\tau \sim p(\tau)}\left[r(s_t, a_t) + \gamma V^{*}(s_{t+1}) \right]$
$=\mathbb{E}_{\tau \sim p(\tau)}\left[r(s_t, a_t) + \gamma \cdot \underset{a_t}{max}Q^*(s_t, a_t)\right]$
我们如下定义优势值函数:
$A^{\pi}(s, a) = Q^{\pi}(s, a) - V^{\pi}(s)$

11.4.2 值函数估计

值函数的估计主要有蒙特卡洛法和时序差分法。

蒙特卡洛法
蒙特卡洛算法其实就是通过采样策略 $\pi(a|s)$ ，生成多条轨迹 $\tau^{(n)}$ 来估计Q和V的。
$Q^{\pi}(s, a) = \mathbb{E}_{\tau \sim p(\tau)}[R(\tau_{s_0 = s, a_0 = a})]$
$Q^{\pi}(s, a) = \frac{1}{N}\sum_{n=1}^{N}[R(\tau^{(n)}_{s_0 = s, a_0 = a})]$
其中 $\tau^{(n)}_{s_0 = s, a_0 = a}$ 表示第n的采样轨迹，起始状态为s，起始动作为a。V函数可以用同样的方式估计：
$V^{\pi}(s) = \frac{1}{N}\sum_{n=1}^{N}[R(\tau^{(n)}_{s_0 = s})]$

时序差分方法
该方法利用了值函数的贝尔曼方程性质
$V^{\pi}(s_t) = V^{\pi}(s_t) + \alpha \cdot (r_t + \gamma \cdot V^{\pi}(s_{t+1}) - V^{\pi}(s_t))$
$Q^*(s_t, a_t) = Q^*(s_t, a_t) + \alpha \cdot \left( r(s_t, a_t) + \gamma \cdot \underset{a_{t+1}}{max}Q^*(s_{t+1}, a_{t+1}) -Q^*(s_t, a_t) \right)$

11.4.3 策略改进

我们需要根据值函数间接的推到策略模型。
首先来看如何从V函数推导策略模型：
$\pi^* = \underset{\pi}{argmax} V^{\pi}(s)$
由于状态空间S和动作空间A都是十分巨大的，因此这种方法很难实行。考虑Q函数推导策略模型：
$\pi^{'}(s) = \underset{\pi}{argmax}Q^{\pi}(s, a)$
通过这种方式，可以在任意状态s下，通过遍历动作A选出动作。

但是策略 $\pi^{'}(s)$ 是确定性策略，在相同状态下产生的动作也相同，那么每次交互产生的轨迹可能是相似的。因此让策略以一定概率采取随机策略：
$\pi^{\epsilon}(s_t) = \left\{ \begin{aligned} \underset{a}{argmax} Q^{\pi}(s, a)， 1-\epsilon的概率 \\ 随机选取动作， \epsilon的概率 \end{aligned} \right.$

11.4.4 SARSA算法

该算法通过如下方式估计Q函数：
$Q^{\pi}(s_t, a_t) = Q^{\pi}(s_t, a_t) + \alpha \left( r(s_t, a_t) + \gamma Q^{\pi}(s_{t+1}, a_{t+1}) - Q^{\pi}(s_t, a_t) \right)$
在轨迹的每一步，只需要 $s_t, a_t, r_t, s_{t+1}, a_{t+1}$ 即可更新一次Q网络。属于On-Policy算法。

11.4.5 DQN算法

2015年，DeepMind提出了利用深度神经网络实现Q Learning算法。
Q Learning：
$Q^*(s_t, a_t) = Q^*(s_t, a_t) + \alpha \left( r(s_t, a_t) + \gamma \cdot \underset{a_{t+1}}{max}Q^*(s_{t+1}, a_{t+1}) - Q^*(s_t, a_t) \right)$
用神经网络来参数化Q函数，并利用梯度下降算法更新参数，目标函数如下：
$L = \left( r_t + \underset{a_{t+1}}{max} Q_{\theta}(s_{t+1}, a_{t+1}) - Q_{\theta}(s_t, a_t) \right)^2$

11.4.6 DQN变种

Dueling DQN
将目标中的Q网络和估值中的Q网络分离：
$L = \left( r_t + \gamma \cdot \tilde{Q}\left( s_{t+1}, \underset{a}{max} Q_{\theta}(s_{t+1}, a) \right) - Q_{\theta}(s_t, a_t) \right)^2$

DQN 网络(上)和 Dueling DQN 网络(下)

11.5 Actor-Critic方法

再介绍原始梯度策略的时候，为了缩减方差，我们引入了基准线b：
$\frac{\partial J(\theta)}{\partial \theta} = \mathbb{E}_{\tau \sim p(\tau)} \left[ \sum_{t=1}^{T-1} \frac{\partial}{\partial \theta} log \pi_{\theta} (a_t | s_t) (R(\tau) - b ) \right]$

其中b可以通过蒙特卡洛算法估计， $b = \frac{1}{N} \sum_{n=1}^{N} R(\tau^{(n)})$ 。如果把 $R(\tau)$ 理解成 $Q^{\pi}(s_t, a_t)$ 的估计值 $\tilde{Q^{\pi}}(s_t, a_t)$ ，基准线b理解成状态 $s_t$ 的平均值 $V^{\pi}(s_t)$ ，那么 $R(\tau) - b$ 就是有事函数 $A^{\pi}(s, a)$ 。其中基准线 $V^{\pi}(s_t)$ 如果使用神经网络来估计，就是本章要介绍的Actor-Critic算法（AC算法）。策略网络 $\pi_{\theta}(a_t|s_t)$ 叫做Actor，用来生产策略并于环境交互， $V_{\phi}^{\pi}(s_t)$ 是Critic网络，用来评估当前状态的好坏。

对于Actor网络，目标是最大化期望回报，通过 $\frac{\partial J(\theta)}{\partial \theta}$ 来更新网络参数:
$\theta^* = \theta + \eta \cdot \frac{\partial J (\partial)}{\partial \theta}$

对于Critic网络，目标是通过MC或TD算法获得准确的 $V_{\phi}^{\pi}(s_t)$ 的估值：
$\phi = \underset{\phi}{argmin} \ dist(V_{\phi}^{\pi}(s_t), V_{target}^{\pi}(s_t))$

11.5.1 Advantage AC 算法

上边介绍的通过优势值函数 $A^{\pi}(s, a)$ 的Actor-Critic算法叫做Advantage Actor-Critic算法，是目前最主流的Actor-Critic算法。

11.5.2 A3C 算法

A3C算法，Asynchronous Advantage Actor-Critic是DeepMind基于Advantage Actor-Critic算法提出来的异步版本。将 Actor-Critic 网络部署在多个线程中同时进行训练，并通过全局网络来同步参数。这种异步训练的模式大大提升了训练效率，训练速度更快，并且算法性能也更好。

A3C算法

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 221,198评论 6赞 514
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,334评论 3赞 398
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 167,643评论 0赞 360
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,495评论 1赞 296
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,502评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,156评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,743评论 3赞 421
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,659评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,200评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,282评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,424评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,107评论 5赞 349
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,789评论 3赞 333
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,264评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,390评论 1赞 271
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,798评论 3赞 376
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,435评论 2赞 359