强化学习 | がんばろう

强化学习基础

概述

强化学习（reinforcement learning，RL）：智能体（agent）怎么在复杂、不确定的环境（environment）中最大化它能获得的奖励

**监督学习（supervised learning）**需要大量有标签数据，并且这些数据满足独立同分布，根据错误设计损失函数，通过反向传播来训练神经网络

监督学习的两个假设：

输入的数据（标注的数据）都应是没有关联的
需要告诉学习器正确的标签是什么

在强化学习中，监督学习的两个假设其实都不能得到满足

强化学习和监督学习的区别：

强化学习输入的样本是序列数据，有非常强的连续性，而不像监督学习里面样本都是独立的
学习器不知道每一步正确的动作，学习器需要自己去发现哪些动作可以带来最多的奖励，只能通过不停地尝试来发现最有利的动作
探索（exploration）和利用（exploitation）是强化学习的核心

探索指尝试一些新的动作，可能会得到更多的奖励，也可能没有

利用指采取已知的可以获得最多奖励的动作，重复执行

需要在探索和利用之间进行权衡，这也是在监督学习里面没有的情况
没有非常强的监督者（supervisor），只有奖励信号（reward signal），并且奖励信号是延迟的

当智能体只能看到部分的观测，就称这个环境是部分可观测的（partially observed）

强化学习通常被建模成部分可观测马尔可夫决策过程，可以用一个七元组描述：
$$
({S}, {A}, T, R, \Omega, O, \gamma)
$$

$S$ 表示状态空间，为隐变量
$A$ 为动作空间
$T(s’ \mid s, a)$ 为状态转移概率
$R$ 为奖励函数
$\Omega(o \mid s, a)$ 为观测概率
$O$ 为观测空间；
$\gamma$ 为折扣系数

在连续动作空间中，动作是实值的向量；在离散动作空间中，动作数量是有限的

组成成分

对于一个强化学习智能体，它可能有一个或多个如下的组成成分

策略（policy）
价值函数（value function），价值函数值越大，说明智能体进入这个状态越有利
模型（model），模型表示智能体对环境的状态进行理解

策略是智能体的动作模型，用于把输入的状态变成动作，可分为两种：随机性策略和确定性策略

随机性策略（stochastic policy）

$\pi(a \mid s) = p(a_t = a \mid s_t = s)$ 输入一个状态输出所有动作的概率，对这个概率分布进行采样，可得到智能体将采取的动作

确定性策略（deterministic policy）

直接采取最有可能的动作，即 $a^* = \arg\max_{a} \pi(a \mid s)$

通常情况下，强化学习一般使用随机性策略

价值函数里面有一个折扣因子（discount factor），希望在尽可能短的时间里面得到尽可能多的奖励

模型决定了下一步的状态，下一步的状态取决于当前的状态以及当前采取的动作，由状态转移概率和奖励函数两个部分组成

状态转移概率即
$$
p_{ss’}^{a} = p(s_{t+1}=s’ \mid s_t=s, a_t=a)
$$
奖励函数是指我们在当前状态采取了某个动作，可以得到多大的奖励
$$
R(s,a)=\mathbb{E}\left[r_{t+1}\mid s_t=s,\ a_t=a\right]
$$

智能体的类型

**基于价值的智能体（value-based agent）**显式地学习价值函数，隐式地学习它的策略，策略是其从学到的价值函数里面推算出来的，算法有Q学习（Q-learning）、 Sarsa 等

**基于策略的智能体（policy-based agent）**直接学习策略，给它一个状态，它就会输出对应动作的概率，基于策略的智能体并没有学习价值函数，算法有策略梯度（Policy Gradient，PG）算法等

把基于价值的智能体和基于策略的智能体结合起来就有了演员-评论员智能体（actor-critic agent）

区别：

在基于策略的强化学习方法中，智能体会制定一套动作策略，这个策略是在给定状态下从动作集合中选择一个动作的依据，它是静态的，不随状态变化而变化。强化学习算法直接对策略进行优化，使制定的策略能够获得最大的奖励
在基于价值的强化学习方法中，智能体不需要制定显式的策略，它维护一个价值表格或价值函数，并通过这个价值表格或价值函数来选取价值最大的动作

基于价值迭代的方法只能应用在不连续的、离散的环境下（如围棋或某些游戏领域），对于动作集合规模庞大、动作连续的场景（如机器人控制领域），其很难学习到较好的结果

**有模型（model-based）**强化学习智能体通过学习状态的转移来采取动作

马尔可夫决策过程可以用四元组表示，即状态集合、动作集合、状态转移函数和奖励函数
$$
\langle S,A,P,R\rangle
$$
当智能体知道状态转移函数$P(s_{t+1}\mid s_t,a_t)$和奖励函数$R(s_t,a_t)$后，它就能知道在某一状态下执行某一动作后能带来的奖励和环境的下一状态，这样智能体就不需要在真实环境中采取动作，直接在虚拟世界中学习和规划策略即可

但真实情况是状态转移函数和奖励函数很难估计，甚至连环境中的状态都可能是未知的，这时就需要采用免模型强化学习

免模型强化学习没有对真实环境进行建模，智能体只能在真实环境中通过一定的策略来执行动作，等待奖励和状态迁移，然后根据这些反馈信息来更新动作策略，这样反复迭代直到学习到最优策略

有模型强化学习和免模型强化学习的区别：

有模型强化学习是指根据环境中的经验，构建一个虚拟世界，同时在真实环境和虚拟世界中学习；
免模型强化学习是指不对环境进行建模，直接与真实环境进行交互来学习到最优策略

免模型强化学习通常属于数据驱动型方法，需要大量的采样来估计状态、动作及奖励函数，从而优化动作策略

测试智能体在 Gym 库中某个任务的性能时，出于习惯使然，学术界一般最关心 100 个回合的平均回合奖励

总结

强化学习中的损失函数与深度学习中的损失函数有什么区别呢？

深度学习中的损失函数的目的是使预测值和真实值之间的差距尽可能小，而强化学习中的损失函数的目的是使总奖励的期望尽可能大

马尔可夫决策过程(MDP)

马尔可夫过程(MP)

在随机过程中，**马尔可夫性质（Markov property）**是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态

在已知当前状态$X_t$的情况下，未来状态$X_{t+1}$的概率分布不再依赖更早的历史
$$
p(X_{t+1}=x_{t+1}\mid X_{0:t}=x_{0:t}) = p(X_{t+1}=x_{t+1}\mid X_t=x_t)
$$

不是说“过去完全没用”，而是说当前状态已经把过去对未来有用的信息总结完了

离散时间的马尔可夫过程也称为马尔可夫链（Markov chain）

状态转移矩阵类似于条件概率，表示当知道在状态 $s_t$ 时，到达下面所有状态的概率

每一行描述的是从一个节点到达所有其他节点的概率
$$
P = \begin{pmatrix}
p(s_1 \mid s_1) & p(s_2 \mid s_1) & \cdots & p(s_N \mid s_1) \\
p(s_1 \mid s_2) & p(s_2 \mid s_2) & \cdots & p(s_N \mid s_2) \\
\vdots & \vdots & \ddots & \vdots \\
p(s_1 \mid s_N) & p(s_2 \mid s_N) & \cdots & p(s_N \mid s_N)
\end{pmatrix}
$$

马尔可夫奖励过程(MRP)

在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function）

奖励函数 $R$ 是一个期望，另外定义了折扣因子 $\gamma$，如果状态数有限，那么 $R$ 可以是一个向量

**范围（horizon）**是指一个回合的长度（每个回合最大的时间步数），它是由有限个步数决定的

**回报（return）**可以定义为奖励的逐步叠加，假设时刻 $t$ 后的奖励序列为 $r_{t+!}, r_{t+2},\cdots$，则回报为：
$$
G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 r_{t+4} + \cdots + \gamma^{T-t-1}r_T
$$
越往后得到的奖励，折扣越多

当有了回报之后，就可以定义状态的价值了，就是状态价值函数（state-value function）

状态价值函数被定义成回报的期望，期望也可以看成未来可能获得奖励的当前价值的表现
$$
V^t(s)=\mathbb{E}[G_t \mid s_t=s] = \mathbb{E}[r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+\cdots+\gamma^{T-t-1}r_T\mid s_t=s]
$$
使用折扣因子的原因如下

有些马尔可夫过程是带环的，它并不会终结，避免无穷的奖励
并不能建立完美的模拟环境的模型，对未来的评估不一定是准确的，对未来的评估增加一个折扣，把这个不确定性表示出来
如果奖励是有实际价值的，更希望立刻就得到奖励

可以把折扣因子设为 0，只关注当前的奖励；也可以把折扣因子设为 1，对未来的奖励并没有打折扣

折扣因子可以作为强化学习智能体的一个超参数（hyperparameter）来进行调整

最主要的问题：怎么计算它的价值函数

蒙特卡洛采样(MC)：从某个状态，反复模拟很多条轨迹，得到很多次累计回报，然后取平均
动态规划/贝尔曼方程：不靠大量随机轨迹取平均，而是利用状态转移概率$P(s’\mid s)$和奖励$R(s)$ 不断迭代 Bellman 方程，直到价值函数收敛

贝尔曼方程：
$$
V(s)=R(s)+\gamma \sum_{s’\in S} p(s’ \mid s)V(s’)
$$
贝尔曼方程定义了状态之间的迭代关系

证明通过全期望公式
$$
\mathbb{E}\left[V(s_{t+1}) \mid s_t\right]=\mathbb{E}\left[\mathbb{E}\left[G_{t+1}\mid s_{t+1}\right]\mid s_t\right]=\mathbb{E}\left[G_{t+1}\mid s_t\right]
$$
如果 $X$ 和 $Y$ 都是离散型随机变量，则条件期望（conditional expectation）$\mathbb{E}[X \mid Y = y]$ 定义为
$$
\mathbb{E}[X \mid Y = y] = \sum_x x , p(X = x \mid Y = y)
$$
可以把贝尔曼方程写成矩阵的形式：
$$
\begin{pmatrix}V(s_1) \\
V(s_2) \\
\vdots \\
V(s_N)
\end{pmatrix}=
\begin{pmatrix}
R(s_1) \\
R(s_2) \\
\vdots \\
R(s_N)
\end{pmatrix}+
\gamma
\begin{pmatrix}
p(s_1 \mid s_1) & p(s_2 \mid s_1) & \cdots & p(s_N \mid s_1) \\
p(s_1 \mid s_2) & p(s_2 \mid s_2) & \cdots & p(s_N \mid s_2) \\
\vdots & \vdots & \ddots & \vdots \\
p(s_1 \mid s_N) & p(s_2 \mid s_N) & \cdots & p(s_N \mid s_N)
\end{pmatrix}
\begin{pmatrix}
V(s_1) \\
V(s_2) \\
\vdots \\
V(s_N)
\end{pmatrix}
$$
把贝尔曼方程写成矩阵形式后，可以直接得到解析解
$$
\begin{aligned}
V &= R + \gamma P V \\
I V &= R + \gamma P V \\
(I - \gamma P)V &= R \\
V &= (I - \gamma P)^{-1} R
\end{aligned}
$$
但是直接求逆的复杂度是$O(N^3)$，对大矩阵求逆不现实，通过解析解去求解的方法只适用于很小量的马尔可夫奖励过程

通过**自举（bootstrapping）**的方法不停地迭代贝尔曼方程，当最后更新的状态与上一个状态的区别并不大的时候，更新就可以停止，把贝尔曼方程变成贝尔曼更新，这样就可以得到状态的价值

马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策

状态转移也多了一个条件，未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作
$$
p(s_{t+1} \mid s_t, a_t)
$$
对于奖励函数，它也多了一个当前的动作，变成了
$$
R(s_t = s, a_t = a)=
\mathbb{E}\left[r_t \mid s_t = s, a_t = a\right]
$$
策略定义了在某一个状态应该采取什么样的动作

知道当前状态后，可以把当前状态代入策略函数来得到一个概率
$$
\pi(a \mid s) = p(a_t = a \mid s_t = s)
$$
已知马尔可夫决策过程和策略 $\pi$，可以把马尔可夫决策过程转换成马尔可夫奖励过程

状态转移函数$P(s’\mid s, a)$基于它当前的状态以及它当前的动作

已知策略函数，也就是已知在每一个状态下，可能采取的动作的概率，所以就可以直接把动作进行加和
$$
P_{\pi}(s’ \mid s) = \sum_{a \in A} \pi(a \mid s) p(s’ \mid s, a)
$$
对于奖励函数，也可以把动作去掉，这样就会得到类似于马尔可夫奖励过程的奖励函数
$$
r_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) R(s,a)
$$
马尔可夫过程/马尔可夫奖励过程的状态转移与马尔可夫决策过程里面的状态转移的差异

价值函数

马尔可夫决策过程中的价值函数可定义为
$$
V_{\pi}(s) = \mathbb{E}_{\pi}\left[ G_t \mid s_t = s \right]
$$
引入 Q 函数（Q-function），也被称为动作价值函数（action-value function）

定义的是在某一个状态采取某一个动作，它有可能得到的回报的一个期望
$$
Q_{\pi}(s,a) = \mathbb{E}{\pi}\left[ G_t \mid s_t = s, a_t = a \right]
$$
对 Q 函数中的动作进行加和，就可以得到价值函数
$$
V{\pi}(s) = \sum_{a \in A} \pi(a \mid s) Q_{\pi}(s,a)
$$
对 Q 函数的贝尔曼方程进行推导