强化学习

背景

监督学习旨在通过训练集中的已知标签\(y\)来训练模型, 使模型的输出尽可能模仿这些标签, 通常用于分类或回归任务. 例如, 将不同类型的宝可梦进行分类, 在这种情况下, 输入有一个正确答案或者标签, 模型试图预测每个输入的标签.

但是, 在一些复杂任务中, 如让机器人学会骑自行车中, 定义"正确答案"非常困难, 很难提供明确的监督信号去指导算法模仿, 因此监督学习不适合这类问题.

定义

强化学习可以用来解决上述问题, 可以通过婴儿学习的类比来解释: 婴儿在成长过程中没有明确的老是指导, 而是通过与环境的互动积累经验. 例如, 婴儿通过玩耍, 挥动手臂或四处观察等活动, 接受到来自环境的正面(如称赞)和负面(如批评)反馈, 这些反馈塑造了他们的行为和性格, 这种试错和反馈的过程类似于强化学习中的"反馈机制".

强化学习的目标是学习如何做出一系列良好的决策. 智能体, Agent根据当前的状态\(s_t\)采取行动\(a_t\), 并根据从环境中获得的奖励来调整其策略, 通过试错来最大化累计奖励. 这种奖励可以用奖励函数\(r_t\)来描述, 它是一个标量, 反馈智能体在\(t\)时刻的表现好坏.

Tip

"奖励假设"告诉我们"所有目标都可以通过最大化预期的累计奖励来描述", 这意味着, 只要能够设计一个合适的奖励函数, 我们就可以通过强化学习实现各种复杂的目标, 涵盖从游戏到机器人控制的不用应用场景.

在每一个时间步, 智能体接受状态\(s_t\)和奖励\(r_t\), 执行行动\(a_t\). 环境接受行动\(a_t\), 更新状态为\(s_{t+1}\), 并发出新奖励\(r_{t+1}\). 历史\(H_t=s_1, r_1, a_1, ..., a_{t-1}, s_t, r_t\)记录了智能体从开始到当前时间步\(t\)为止所有的状态, 行动和奖励, 接下来的行动\(a_t\)取决于这个历史.

马尔可夫决策过程

马尔可夫决策过程, Markov Decision Process, MDP, 是用于定义强化学习问题的数学框架, MDP通常通过五元组\((\mathcal{S}, \mathcal{A}, \mathcal{R}, \mathbb{P}, \gamma)\)来表示:

\(\mathcal{S}\): 表示所有可能的状态集合, 即智能体在环境中可能遇到的不同状态
\(\mathcal{A}\): 表示所有可能的行动集合, 即智能体可以采取的各种行动
\(\mathcal{R}\): 表示在特定的状态和行动下, 奖励值的分布
\(\mathbb{P}\): 表示给定当前的状态和所选行动后, 转移到下一个状态的概率分布
\(\gamma\): 折扣因子, 用于确定未来奖励的价值, 较低的\(\gamma\)会让智能体更关注当前的奖励, 较高的\(\gamma\)会让智能体考虑长期的回报

在马尔可夫决策过程中, 假设只需要关注当前状态\(s_t\)就可以决定下一步, 而不依赖于更早的历史.

智能体由三个部分组成:

策略: Policy, 定义了每个状态下智能体采取的行动. 通常用\(\pi(a|s)\)表示. 策略可以是确定性的(每个状态对应唯一的行动), 或者是随机性的(每个状态对应行动的概率分布)
价值函数: Value Function, 衡量智能体在某个策略下给定状态或在给定状态下采取行动后的预期回报. 它能帮助智能体判断哪些状态或状态和行动的组合更有利, 常见的价值函数有状态值函数\(V^{\pi}(s)\)和动作值函数\(Q^{\pi}(s, a)\), \(\pi\)是某个特定的策略, 侧重于评估
模型: Model, 用于模拟环境的动态行为. 即预测在某个状态下采取特定行动后, 环境如何变化. 通常提供以下信息: a. 从当前状态\(s\)采取行动\(a\)后, 可能会转移到哪个下一个状态\(s'\); b. 在状态\(s\)执行动作\(a\)后, 可能获得的即时奖励\(r\). 侧重于模拟

Tip

有些RL算法会使用模型来模拟和预见环境的变化, 称为基于模型的算法, 而某些RL算法不需要模型, 称为无模型算法. 如果是基于模型的算法, 直接计算价值函数需要智能体在真实环境中进行多次试错, 以获取足够的数据来估计每个状态或给定状态采取行动后的预期汇报, 这对于一些复杂或者代价高昂的环境来说可能不切实际. 模型可以用来模拟环境, 这样, 智能体可以通过在模型中进行"虚拟"实验来估计价值函数, 而不是每次都与真实环境互动, 使得智能体能够"离线学习", 这种方式既节省了资源, 也加快了学习过程.

例子

假设有一个扫地机器人, 它完成扫地后要回到它的基地, 起始位置可以是任何房间.

如上图, 总共有\(12\)个房间, 机器人完成扫地后可以在任意房间, 意味着总共有\(12\)个状态, 它需要做的是在最少的步骤下回到灰色方块所指示的房间. 它的行为可以是向上, 向下, 向左, 向右. 每次移动都设置为一个负奖励, 表示每走一步就扣一分, 鼓励机器人在最少的步数内到达基地.

策略和最佳策略

例子

策略\(\pi\)是机器人在每个状态下选择的动作规则, 例如, 在每个房间, 机器人可以选择向上, 向下, 向左, 向右. 最优策略\(\pi^*\)是使得奖励总和最大化的策略. 由于初始状态和状态转移概率的不确定性, 如机器人初始可能在任意一个房间, 往各个房间(即下一个状态)走的概率也可能不一样.

在这种情况下, 最优策略需要在所有可能的路径中最大化期望奖励. 使用公式可以表示为\(\pi^*=argmax_{\pi}\mathbb{E}[\sum_{t\geq 0}\gamma^t r_t|\pi]\). \(\sum_{t\geq 0}\)表示的是从时间步\(t=0\)开始一直到未来的所有时间步的奖励\(r_t\)之和, 每个奖励都乘以折扣因子\(\gamma\), 用于表示对未来奖励的重视程度. 条件期望\(\mathbb{E[...|\pi]}\)表示在给定策略\(\pi\)下计算的期望值, 即在该策略引导下, 累积的折扣奖励的期望. 初始状态\(s_0\sim p(s_0)\), 表示机器人初始状态符合一定的概率分布. 行为\(a_t\sim \pi(\cdot |s_t)\), 表示在每个时间步\(t\), 机器人的行为符合概率分布\(\pi(\cdot|s_t)\), 策略\(\pi\)是一个关于状态的概率分布, 描述了在不同状态下选择不同动作的概率. 状态转移\(s_{t+1}\sim p(\cdot | s_t, a_t)\), 表示机器人的下一个状态符合概率分布\(p(\cdot|s_t, a_t)\), 这个转移概率分布描述了在当前状态和采取的动作下, 环境可能转移到的下一个状态的分布.

价值函数

价值函数用于衡量智能体在某个策略下给定状态或在给定状态下采取行动后的预期回报. 根据划线部分的不同, 可以分为两种价值函数: 状态值函数和动作值函数.

状态值函数: 表示在某个策略\(\pi\)下, 特定状态\(s\)的好坏程度. 它定义为从状态\(s\)出发, 遵循策略\(\pi\)所能获得的期望累计奖励. 公式为\(V^{\pi}(s)=\mathbb{E}[\sum_{t\geq 0}\gamma^t r_t|s_0=s, \pi]\)
动作值函数: 表示在某个策略\(\pi\)下, 当在状态\(s\)时执行动作\(a\)的好坏程度. 它定义为首先在状态\(s\)执行动作\(a\), 然后遵循策略\(\pi\)所能获得的期望累计奖励. 公式为\(Q^{\pi}(s, a)=\mathbb{E}[\sum_{t\geq 0}\gamma^t r_t|s_0=s, a_0=a, \pi]\).

Bellman方程

定义\(Q^*(s, a)\)为最优Q值函数, 公式为\(Q^*(s, a)=max_{\pi}\mathbb{E}[\sum_{t\geq 0}\gamma^t r_t|s_0=s, a_0=a, \pi]\), 注意和动作值函数做区分, 这里表示的是在所有可能的策略中, 而动作值函数表示的是在特定的策略下. 最优Q值函数满足以下Bellman方程: \(Q^*(s, a) = \mathbb{E}_{s' \sim \mathcal{E}} \left[ r + \gamma \max_{a'} Q^*(s', a') \,|\, s, a \right]\).

这个公式的直观理解就是如果下一个状态-动作\(s', a'\)对应的最优Q值\(Q^*(s', a')\)已知, 那么在状态\(s\)执行动作\(a\)所能获得的最优回报\(Q^*(s, a)\), 等于即时奖励\(r\)加上下一个状态-动作对\(s', a'\)的最优Q值函数的期望值. \(s'\sim \mathcal{E}\)指的是下一个状态\(s'\)符合状态转移概率分布\(p(\cdot|s, a)\).

最优策略\(\pi^*\)指的就是在每个状态下, 都选择能够使得\(Q^*(s, a)\)最大化的动作/行为.

Q学习算法

Q学习算法的目的就是获得所有状态-动作对的最优Q值, 步骤为:

初始化: 对于所有的状态-动作对\(s, a\), 初始化\(Q(s, a)\), 通常为\(0\), 构成的表称为Q表
持续交互:
1. 开始一个新的回合: 随机设定一个初始状态
  1. 根据当前状态\(s\)和策略(如\(\epsilon\)-贪心策略)选择一个动作\(a\)
  2. 执行动作\(a\), 获得即时奖励\(r\)和下一个状态\(s'\)
  3. 我们并不知道每个状态-动作对的最优Q值\(Q^*(s, a)\), 所以需要使用增量更新的方式逐步逼近最优Q值, \(Q(s, a)\): \(Q(s, a)\leftarrow Q(s, a)+\alpha[r+\gamma max_{a'} Q(s', a')-Q(s, a)]\). 这个公式的推导: 在执行动作\(a\)后, 根据Bellman方程, 我们可以算出一个目标Q值, 表示接下来采取最优动作时可以获得地期望回报, 目标Q值为\(R(s, a, s')+\gamma max_{a'}Q(s', a')\). 那么它和当前Q值之间的差距就是增量\(\Delta Q(s, a)=\)目标Q值\(-Q(s, a)=(R(s, a, s') + \gamma max_{a'}Q(s', a'))-Q(s, a)\). 然后, 设置一个学习率\(\alpha\)用来控制差距调整的大小\(\alpha[r+\gamma max_{a'} Q(s', a')-Q(s, a)]\), Q.E.D
  4. 将\(s'\)作为新的当前状态, 如果\(s'\)是终止状态, 回合结束; 如果不是终止状态, 则继续
2. 回合结束? 进行下一个回合
终止: 若达到固定回合数, 或者Q表中所有的Q值变化都很小了, 小于某个阈值近似收敛, 则终止算法, Q表中的值作为学习到的最优Q值.

例子

继续上面的例子. 假设向上走是\(0\), 向下走\(1\), 向左走\(2\), 向右走\(3\).

初始化: 首先, 初始化一个Q表, 这张表是\(12\times 4\), 因为有\(12\)个状态, \(4\)种动作. 初始值全部都是\(0\)
持续交互
1. 开始一个新的回合, 随机设定初始房间为\(8\)
  1. 选择动作: 根据\(\epsilon\)-贪心策略, 机器人在每个房间选择一个动作. 例如在在房间\(8\)选择向上走
  2. 执行动作和接受奖励: 执行动作, 获取即时奖励, 并转移到下一个状态\(s'\). 例如向上走到了房间\(6\), 由于不是目标房间, 即时奖励为\(-1\)
  3. 更新Q值: 用公式更新Q表中\(Q(8, 0)\)的值, 我们可以在当前的Q表中找到\(max_{a'}Q(6, *)\)(初始为\(0\), 后续会慢慢更新), 例如\(a'\)是向下走, \(max_{a'}Q(s', a')=Q(6, 1)\), 如果新的Q值变大了, 说明这个房间\(8\)向上这个方向比较好
  4. 将房间\(6\)设置为新的状态, 重复上述过程
2. 回合结束? 如果它走到了房间\(1\)或房间\(12\), 回合结束, 进行下一个回合
终止: 若达到固定回合数, 或者Q表中所有的Q值变化都很小了, 小于某个阈值近似收敛, 则终止算法, Q表中的值作为学习到的最优Q值

深度Q学习算法

在传统的Q学习中, Q值是保存在Q表中的, 这个方法在小规模的, 离散的状态空间中效果良好, 但是在复杂环境中主要会面临以下问题:

状态空间过大, Q表会变得极其庞大, 导致存储和计算的资源需求变得不现实
无法处理连续状态, 对于很多现实问题, 例如自动驾驶或者机器人控制, 状态(例如位置, 速度, 角度)都是连续的, 无法用有限的Q表表示
难以进行泛化, 传统Q学习在Q表中仅能记录每个具体状态-动作对的Q值, 无法在类似状态之间进行泛化. 这意味着智能体在一个状态下学到的信息无法被类似的状态直接利用

为了解决上述问题, 深度Q学习(DQN)引入了神经网络来近似最优Q值函数, 其结果\(Q_w(s, a)\simeq Q^*(s, a)\), \(w\)为权重. 即给定\(s, a\), 神经网络输出的Q值接近真实的最优Q值.

这种网络被称为"Q网络", 如图.

左图是❌错误的, 这个神经网络接受一个状态和一个动作, 然后输出该特定状态-动作对的Q值\(Q_w(s, a)\). 这个方法的问题在于, 每次只能输出一个特定动作的Q值, 导致效率低下. 特别是在动作空间很大的情况下, 这会导致大量重复计算.

右图是✅正确的, 即只将状态\(s\)输入网络, 然后让网络输出该状态下所有动作的Q值\(Q_w(s, a_1), Q_w(s, a_2), ..., Q_w(s, a_m)\). 这种设计更加高效, 因为对于每个状态\(s\), 网络只需要一次前向传播, 就能计算出所有可能动作的Q值. 在DQN算法中, 通常会将状态\(s\)输入到神经网络, 网络的最后一层输出一个大小为动作数\(m\)的向量, 其中每个元素对应一个一个状态-动作对的Q值.

注意

DQN能够处理连续的状态值, 但是不能处理连续的动作值. 因为DQN的输出层是每个离散动作输出一个Q值. 如果需要处理连续动作空间, 通常会使用其他算法, 如DDPG, SAC, TD3.

损失函数

为了训练Q网络, 我们需要定义一个损失函数\(L\)来最小化Q值的预测误差. 它是预测Q值和目标值之间的均方误差. 根据Bellman方程, 目标Q值为\(r+\gamma max_{a'}Q_w(s', a')\), 所以\(L = \left( r + \gamma \max_{a'} Q_w(s', a') - Q_w(s, a) \right)^2\), 通过最小化这个损失函数, 神经网络会逐步调整权重, 使得\(Q_w(s, a)\)尽可能逼近最优Q值\(Q^*(s, a)\).

经验回放

在连续的时间步中, 状态和动作是相关的, 因此直接使用这些样本进行训练会导致模型学习到时间相关性, 从而影响模型的稳定性.

经验回放是指智能体在环境中收集的经验, 一个四元组(当前状态, 采取的动作, 获得的奖励和到达的下一状态)存储在一个记忆池中, 然后在训练神经网络的时候从这个数据集中随机抽取经验进行预测, 然后根据损失函数更新Q网络的参数. 这种随机抽样能够打破时间上的相关性, 使得训练数据更加多样化, 独立, 从而减少模型的偏差.

算法可以被表示为:

初始化经验回放记忆池\(\mathcal{D}\), 容量为\(N\)
随机初始化Q网络的参数\(\theta\)
持续交互:
1. 开始一个新的回合: 随机设定初始状态序列\(s1=\{x_1\}\), 对其进行预处理\(\phi_1 = \phi(s_1)\), 其中\(x_1\)是初始状态
  1. 根据当前状态\(s\)和\(\epsilon\)-贪心策略选择一个动作\(a_t\)
    1. 以概率\(\epsilon\)选择随机动作: 这是为了探索(exploration), 让智能体有一定的概率选择随机动作\(a_t\), 从而探索更多的状态空间
    2. 以概率\(1-\epsilon\)选择估计最优动作: 这是为了利用(exploitation)当前网络的知识, 选择当前Q网络估计的最优动作\(a_t = argmax_a Q(\phi(s_t), a; \theta)\). 其中, \(\phi(s_t)\)是当前时间步经过预处理后的状态序列, \(a\)动作, \(\theta\)是Q网络当前的参数
  2. 执行选择的动作\(a_t\), 并获得即时奖励\(r_t\)和下一状态\(x_{t+1}\)
  3. 更新状态序列, 然后对其进行预处理, 得到\(\phi_{t+1}\)
  4. 将该经验\((\phi_t, a_t, r_t, \phi_{t+1})\)存储在记忆池\(\mathcal{D}\)中
  5. 从记忆池\(\mathcal{D}\)中随机采样一个小批量的经验\((\phi_j, a_j, r_j, \phi_{j+1})\), 进行预测, 打破样本相关性
    1. 如果\(\phi_{j+1}\)是终止状态, 则直接利用\(r_j\)作为目标Q值, 即\(y_j=r_j\)
    2. 如果\(\phi_{j+1}\)不是终止状态, 则根据Bellman公式有\(y_j=r_j+\gamma max_{a'}Q(\phi_{j+1}, a'; \theta)\)
  6. 计算误差函数\(L = (y_j - Q(\phi_j, a_j;\theta ))^2\)进行梯度下降最小化更新网络参数\(\theta\)
  7. 当记忆池容量已满, 则结束当前回合; 否则, 继续
2. 回合结束? 进行下一回合
终止: 若达到固定回合数, 或所有的Q值变化都很小了, 小于某个阈值近似收敛, 则终止算法

目标网络

第一个场景:

在Q网络中, 网络的参数\(\mathcal{w}\)是在不断更新的, 而目标Q值的计算过程是基于网络的当前参数的, 这会导致目标Q值不太稳定, 导致Q值很难收敛. 为了解决这个问题, DQN引入了一个目标网络, 目标网络的参数由主网络的参数复制而来, 但是在一段时间内保持固定不变. 相应的, 损失函数应该更新为\(L=(r+\gamma max_{a'}Q_{\hat{w}}(s', a') - Q_w(s, a))^2\). \(\hat{w}\)为目标网络的参数.

第二个场景:

在Q网络中, 计算目标Q值时的\(max\)函数很可能会受到噪音的影响, 导致选择的动作不对.

例子

假设智能体在一个简单的游戏环境中, 当前状态\(s\)下有两个可选动作: \(a_1\)和\(a_2\). 假设下一状态\(s'\)有三个可能的动作\(a'_1, a'_2, a'_3\), 并且每个动作的Q值估计如下：

真实的Q值:

\(Q(s', a'_1) = 3.0\)
\(Q(s', a'_2) = 2.9\)
\(Q(s', a'_3) = 2.0\)

噪音影响下的Q值:

\(Q(s', a'_1) = 2.9\)
\(Q(s', a'_2) = 3.1\)
\(Q(s', a'_3) = 2.2\)

这会导致我们选择\(a_2'\)而不是\(a_1'\)

解决这种问题的方法还是使用目标网络. 使用当前网络\(Q_w\)来选择动作\(a'=argmax_{a'}Q_w(s', a')\), 而使用目标网络\(Q_{\hat{w}}\)来评估选择的动作\(Q_{\hat{w}}(s', a')\). 所以损失函数公式进一步改写为\(L=(r+\gamma Q_{\hat{w}}(s', argmax_{a'}Q_w(s', a')) - Q_w(s, a))^2\)

优先级经验回放

这是对普通的经验回放的一种改进方法. 在普通的经验回放中, 都是均匀采样的, 不考虑每条经验的重要性. 但是在实际训练中, 有些经验对网络的改进有很大的影响, 特别是TD误差较大的经验, 因为它们表示了智能体对未来奖励较大的更新需求, 普通的均匀采样可能会浪费资源在较低TD误差的样本上.

TD误差的计算公式为\(|\delta_i|=|r+\gamma max_{a'}Q_{\hat{w}}(s', a') - Q_w(s, a)|\). 将经验的优先级设置为TD误差加上一个小常数来防止优先级为零\(p_i=|\delta_i|+\epsilon\). 然后计算每条经验的被采样概率\(p(i) = \frac{p_i^\alpha}{\sum_k p_k^{\alpha}}\). \(\alpha\)是一个超参数, 控制TD误差的影响程度, 当\(\alpha=0\)的时候退化成均匀采样. 同时, 在实际采样的时候, 可以引入一定的随机性, 以增加样本的多样性, 避免集中在高TD误差的经验上, 同时保留了优先级的优势.

应用

AlphaGo

AlphaGo是从2014年开始由Google DeepMind开发的人工智能围棋软件. 它背后使用的是强化学习, 相关论文: A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.

神经网络

AlphaGo中由两个神经网络: 策略网络(Policy Network)和价值网络(Value Network):

策略网络: 用于生成围棋的落子策略, 对于当前棋盘的状态, 它输出每个可能落子位置的概率. 策略网络最初是通过人类专家对局的数据进行训练. 通过观察专家的走法, 它学习如何根据当前棋盘状态预测下一步的最佳落子位置, 这一阶段帮助AlphaGo建立基础的围棋理解, 模仿人类的策略. 在监督学习完成后, 策略网络进一步通过自我对弈的方式进行强化学习, 它不断和自己下棋, 通过优化获胜几率, 最终开发出新的策略
价值网络: 用于估计当前棋盘的胜负值, 它输出一个值, 该值表示在给定棋盘状态下获胜的可能性. 它的训练方式主要依靠强化学习, 通过大量的自我对弈, 它学会了在任意棋盘下预测当前局面的胜负可能性

搜索过程

AlphaGo大大优化了搜索过程, 如果没有AlphaGo, 我们使用的是完整搜索树, 又叫"穷尽搜索", 其中的每个节点代表棋盘的一个状态, 每条路径代表可能的下一步行动, 这种方式会产生一个庞大的搜索树, 尤其在围棋这类游戏中, 完全搜索完所有的路径是不可能的, 因为节点数量会指数级增长. 策略网络和价值网络大大简化了这棵树:

策略网络减少宽度: 策略网络能够减少在某个局面下需要考虑的落子位置数量. 它通过对可能的落子位置进行概率排序. 重点关注较高概率的几步, 从而缩小搜索空间
价值网络减少深度: 价值网络通过对局面进行评估, 提前得出某些路径的大概率结果, 减少搜索树的深度. 这样可以在关键位置提前终止搜索, 不必深入每一个分支

训练流程

AlphaGo的训练过程可以总结为:

AlphaGo的自我对弈: AlphaGo在每个局面下使用策略网络和价值网络进行选择, 生成一系列局面, 这种自我对弈会产生大量数据
新的策略网络训练: AlphaGo通过自我对弈的结果, 改善策略网络
新的价值网络训练: AlphaGo通过自我对弈的结果, 改善价值网络
在下一轮迭代中使用新的策略网络和价值网络

战果

AlphaZero在不同的棋类游戏中进展神速.

国际象棋: AlphaZero在四小时就超过了顶尖国际象棋引擎StockFish的水平
将棋: AlphaZero在两小时内超过了顶尖象棋引擎Elmo的水平
围棋: AlphaZero在八小时内就超过了AlphaGo的水平

特点

深度学习能够处理复杂棋类游戏中的庞大搜索空间, 通过神经网络预测落子位置和局面胜负概率, 大大提高了搜索效率, 见搜索过程. 自我对弈生成了大量数据用于训练神经网络, 从简单对手逐步提升, 自动构建了一个由弱到强的训练体系, 它不仅可以帮助AlphaZero掌握既定策略, 还可以发现新的策略和方法, 提高棋艺水平.

深度强化学习

RL是一种用于决策制定的通用框架, 旨在训练一个能够自主行动的智能体. 而DL是一种通用的表示学习框架, 用于学习达到目标所需的表示. 而深度强化学习DRL是RL和DL的集合, 通过利用深度神经网络来处理和强化学习过程中的庞大状态和动作空间. 在传统的强化学习中, 智能体的状态和动作空间是非常大或是连续的, 难以有效表示和处理, 而深度学习的优势在于它可以通过神经网络从复杂的高维数据中提取有效特征, 使得它称为强化学习的有效工具. 之前讲的深度Q学习算法就是DRL的一种, 除此之外, 还有策略梯度方法, Actor-Critic方法等等.