强化学习

强化学习由于其通用性，在许多其他学科中也有研究，如博弈论、控制论、运筹学、信息论、模拟优化、多主体系统、群体智能、统计学和遗传算法。在运筹学和控制文献中，强化学习被称为近似动态编程，或者 神经动态规划。^[3][2]最优控制理论领域也研究了强化学习中令人关心的问题，这个问题主要关注最优解的存在性和表征，以及它们的精确计算算法，而不太关注学习或近似，尤其是在缺乏环境的数学模型的情况下。在经济学和博弈论中，强化学习可以用来解释在有限理性下均衡是如何产生的。

基本的强化学习被建模为一个马可夫决策过程：

• 环境和主体状态的集合，S；
• 主体的动作集合，A；
•   是采取动作   的情况下，从状态   转移到状态  的概率。
•   是采取动作  从   转移到   获得的即时奖励。
• 描述主体能够观察到什么的规则

规则通常是随机的。观察通常包括与最后一次转移相关的标量即时奖励。在许多工作中，主体被假设为可以观察当前的环境状态，这种情况称为“完全可观测”（full observability），反之则称为“部分可观测”（partial observability）。有时，主体可选择的动作集是有限的（零值的平衡是不能再被减少的。例如，如果主体的当前值为3，状态转移将该值减少4，则不允许转移）。

强化学习主体以离散时间步长与其环境交互。在每个时间 t，主体会得到一个观察结果  ，这通常会包括奖励  。然后主体会从一组备选动作中选择一个动作  ，然后这个动作会被作用到环境中。环境进入了一个新的状态  并且与这次转移  相关的奖励   也被确定了下来。强化学习主体的目标是获取尽可能多的奖励。主体可以（可能是随机的）根据历史函数选择任何动作。

当将主体的性能与最优行为主体进行比较时，性能的差异产生了遗憾 的概念 。为了接近最优地行动，主体必须对其行动的长期后果进行推理（即最大化未来收入），尽管这个行动会导致即时奖励可能是负值的。

因此，强化学习特别适合于解决权衡长期和短期回报的问题。它已成功应用于各种问题，包括机器人控制、电梯调度、电信、双陆棋、跳棋^[5]和阿尔法围棋（AlphaGo）。

强化学习的强大功能来源于两个方面：使用样本来优化表现，以及使用函数近似来处理复杂的环境。这两个关键方面使得强化学习可以使用在以下的复杂环境中：

• 环境模型是已知的，但是解析解不存在；
• 仅仅给出环境的模拟模型（模拟优化的问题）；^[6]
• 从环境中获取信息的唯一办法是和它互动。

前两个问题可以被考虑为规划问题（因为还存在某种形式的模型），而最后一个问题可以被认为是真正的学习问题。然而，使用强化学习的方法，这两种规划问题都可以被转化为机器学习问题。

在Burnetas和Katehakis（1997）的多臂老虎机问题和有限状态空间马尔可夫决策过程中，他们对探索与利用之间的权衡进行了最深入的研究。^[7]。

强化学习需要聪明的探索机制。不参考估计的概率分布的随机选择动作性能表现较差。（小的）有限马尔可夫决策过程的情况相当地容易理解。然而，由于缺乏能够很好地随状态数量缩放（或缩放到具有无限状态空间的问题的规模）的算法，因此简单的探索方法是最实用的。

其中一种探索方法就是  -贪婪，当主体在  的概率下选择它认为具有最佳长期效果的行动时。如果没有找到满足这个条件的动作，主体会均匀随机地选择一个动作。这里，   是一个可调参数，有时会根据固定的时间表（使主体逐渐减少探索）或基于启发式自适应地进行更改。^[8]

即使忽视了探索的问题，即使状态是可以观察到的（在之后进行假设），强化学习仍然存在利用过去的经验来找出最佳的动作的问题。

3.1 最优性标准

策略

主体的动作选择被建模为一个映射，名为策略：

策略映射给出了处于状态时  采取动作  的可能性 。^[9]当然也存在着非概率策略。

状态值函数

价值函数   定义为从状态开始  的预期收益 ，即  ，并遵循策略  。因此，粗略地说，价值函数估计给定的状态有“多好”。^[9]

其中随机变量  表示收益，定义为未来折算奖励的总和

其中  是在时间  的奖励，  是折扣率。

该算法必须找到具有最大预期回报的策略。从马尔可夫决策过程理论可知，在一般性的情况下，搜索可以限制在所谓的静态的 策略集合内。如果一个策略动作分布带来的收益只取决于最后访问的状态（来自观测主体的历史），那么它就是 静态的 。搜索可以进一步限制为 确定性的 静态策略。一个确定性静态 策略根据当前状态确定性地选择动作。因为任何这样的策略都可以用从状态集合到动作集合的映射来识别，所以这些策略可以不失一般性地用这样的映射来识别。

3.2 暴力求解

暴力求解方法需要两步：

• 对于每一个可能的策略，在遵循它的时候对收益采样
• 选择预期回报最大的策略

这种方法的一个问题是，策略的数量可能很大，甚至是无限的。另一个问题是收益的方差可能很大，这需要许多样本来准确估计每项策略的收益。

如果我们假设某种结构，允许从一个策略生成的样本影响对其他策略的估计，那么这些问题便可以得到改善。实现这一点的两种主要方法是价值函数估计和直接策略搜索。

3.3 价值函数

价值函数方法试图通过保持对某种策略（通常是“当前的”[同步策略]或者是最优的[异步策略]）的一系列的估计期望收益来找到一种最大化回报的策略。

这些方法依赖于马尔可夫决策过程理论，在马尔可夫决策过程理论中，最优性在某种意义上被定义为比之前的更强的策略：如果一个策略在任何的 初始状态下都能获得最佳预期收益，则称之为最优策略（即初始分布在这个定义中不起作用）。同样，最优策略总是可以在静态策略中找到。

要以正式的方式定义最优性，首先要定义一个策略  的值为

其中  代表从初始状态  下遵循  获得的相应收益 。定义   为  的最大的可能的值，其中  是可以改变的，

在每个状态下实现这些最优值的策略称为最优的。显然，当一个策略能够满足这个最优的情况下，它也一定能满足最大化预期收益  ，因为  ，其中  是从分布  中随机取样的状态 。

虽然状态值足以定义最优性，但定义动作值也是有用的。给定一个状态  行动  和策略  ，在遵循   的前提下  对的动作值定义为

其中   目前表示在遵循  的条件下在状态  时第一次采取行动  所获得的随机收益。

马尔可夫决策过程理论指出，如果  是一个最优策略，我们通过从  中最优地（采取最优行动）选择每个状态  具有最高值的行动。这种最优策略的动作价值函数 (  )被称为最优动作值函数 ，并且通常表示为  。总之，仅知道最优动作价值函数就足以知道如何最优地行动。

假设完全了解马尔可夫决策过程，计算最优动作价值函数的两种基本方法是价值迭代和策略迭代。两种算法都计算一系列函数  （  ）最后收敛到  。计算这些函数涉及计算整个状态空间上的期望，这种计算对于除了最小（有限）马尔可夫决策过程之外的所有马尔可夫决策过程都是不切实际的。在强化学习方法中，通过对样本求平均和使用函数逼近方法来近似期望值，以满足在大的状态动作空间上表示值函数的需要。

蒙特卡罗方法

蒙特卡罗方法可以用于模拟策略迭代的算法。策略迭代包括两个步骤： 策略评估 和策略改进。

蒙特卡洛用于策略评估步骤。在这个步骤中，给定一个静态的、确定性的策略  ，目标是对于所有状态-动作对  计算函数值   （或它们的较好的近似）。假设（为了简单起见）马尔可夫决策过程是有限的，有足够的内存来容纳动作值，并且问题是阶段性的，在每一个阶段之后，会从某个随机的初始状态产生一个新的问题。然后，给定状态-动作对  的值的估计可以通过对来源于这段时间的   的采样收益求平均来计算。给定足够的时间，这个过程可以对动作价值函数  构建一个精确的估计  。到这里就是完整的策略评估步骤的描述。

在策略改进步骤中，通过计算关于  的贪心 策略来得到下一个策略：给定一个状态  ，这个新策略返回一个最大化  的动作。实际上，惰性评估可以将最大化动作的计算推迟到需要的时候。

该过程的问题包括：

• 该程序可能花费太多时间评估次优策略。
• 它使用样本效率低下，因为长轨迹只能提高对单个 启动轨迹的状态-动作对的估计。
• 当沿着轨迹的回报有高方差 时，收敛速度很慢。
• 它只对 阶段性问题 有用。
• 它只对小的、有限的马尔可夫决策过程中有用。

时间差分法

第一个问题是通过允许过程在值确定之前改变策略（在一些或所有状态）来解决的。这本身也可能是个问题，因为它可能会阻碍收敛。大多数当前的算法都是这样做的，导致广义策略迭代 算法的出现。许多玩家-评委（actor-critic） 方法属于这一类。

第二个问题可以通过允许轨迹对其中的任何状态-动作对产生影响来解决。这在一定程度上也有助于解决第三个问题，尽管当回报具有高方差时，Sutton的时域差分方法是一个更好的基于递归贝尔曼方程的解决方案^[10][11]。需要注意的是，时域差分方法中的计算可以是增量的（当每次转移后内存发生改变并且转移被丢弃时），也可以是批处理的（当转移是批处理并且估计值基于批处理计算了一次时）。批处理方法，如最小二乘时差法，^[12]可以更好地使用样本中的信息，而当批处理方法由于其高计算或内存复杂性而不可行时，增量方法是唯一的选择。有些方法试图将这两种方法结合起来。基于时间差分的方法也解决了第四个问题。

为了解决第五个问题，使用了函数逼近方法 。线性函数逼近 从映射开始  给每个状态-动作对分配一个有限维度的向量。然后，状态-动作对  的动作值通过线性组合带有权重  的  来获得：  

然后，算法会调整权重，而不是调整与单个状态-动作对相关联的值。基于非参数统计（这可以看作是构造它们自己的特征）的思想的方法也进行了探索。

值迭代也可以作为产生Q学习算法及其许多变体的起源。 ^[13]

使用动作值的问题在于，他们可能需要对竞争的动作值进行高度精确的估计，而当收益有噪声时，很难获得这些估计。尽管这个问题在某种程度上通过时间差分方法能得到缓解。使用所谓的兼容函数近似方法需要对通用性和效率做出让步。时间差分的另一个具体问题来自于他们对递归贝尔曼方程的依赖。大多数时间差分方法都有一个所谓的  参数  ，它可以在不依赖贝尔曼方程的蒙特卡罗方法和完全依赖贝尔曼方程的基本时间差分方法之间连续插值。这可以有效缓解这个问题。

3.4 直接策略搜索

另一种方法是直接在策略空间（的某个子集）中搜索，在这种情况下，问题变成随机优化的情况。可用的两种方法是基于梯度的方法和无梯度的方法。

基于梯度的方法（策略梯度方法）从有限维（参数）空间到策略空间的映射开始：给定参数向量  ，让  表示与  关联的策略 。通过以下方式定义性能

在温和的条件下，这个函数作为参数向量  的函数是可微的 。如果  的梯度是已知的，可以使用梯度上升的方法。由于梯度的解析表达式不可用，因此只有噪声估计可用。这样的估计可以用许多方法来构建，产生了像威廉姆斯的增强算法这样的算法^[14]方法（在基于模拟的优化文献中称为似然比检验）。^[15]策略搜索方法已经在机器人场景中使用。^[16]许多策略搜索方法可能会陷入局部最优（因为它们是基于局部搜索的方法）。

有很多方法避免依赖梯度信息。这些方法包括模拟退火、交叉熵搜索或进化计算方法。许多无梯度方法可以实现（理论上和极限情况下）全局最优。

给定噪声数据，策略搜索方法可能会缓慢收敛。例如，当轨迹很长且收益的方差很大时，这种情况会发生在阶段性问题中。在这种情况下，依赖时间差异的基于值函数的方法可能会有所帮助。近年来， 玩家-评委方法 被提出后在各种问题上表现良好。^[17]

大多数算法的渐近行为和有限样本行为都是很好理解的。具有可证明良好在线性能（解决探索问题）的算法是已知的了。

大型马尔可夫决策过程的有效探索在很大程度上还没有被探索过（多臂老虎机问题除外）。尽管许多算法出现了有限时间的性能上线，但这些界限的预计会相当宽松，因此需要做更多的工作来更好地理解相对优势和不足。

对于增量算法，渐近收敛问题已经解决。基于时间差分的算法能在比以前更广泛的条件下收敛（例如，当与任意的光滑函数近似一起使用时）。

研究主题包括

• 在大量条件下使用较少（或没有）参数的自适应方法
• 解决大型马尔可夫决策过程中的探索问题
• 大规模经验评估
• 在部分信息下学习和行动（例如，使用预测状态表示）
• 模块化和分层强化学习
• 改进现有的价值函数和策略搜索方法
• 适用于大型（或连续）动作空间的算法
• 迁移学习
• 终身学习
• 高效的基于样本的规划（例如，基于蒙特卡洛树搜索）。
• 软件项目中的缺陷检测^[18]

多主体或分布式强化学习是一个收到关注的话题。相关应用范围正在不断地扩大。^[19]

• 玩家-评委强化学习

强化学习算法，如时间差分学习，正在作为大脑中基于多巴胺的学习模型进行研究。在这个模型中，从黑质到基底神经节的多巴胺能投射作为预测误差。强化学习已经被用作人类技能学习模型的一部分，特别是在技能获取中内隐学习和外显学习之间的相互作用（关于该应用的第一个出版物是在1995-1996年）。^[20]

6.1 深度强化学习

这种方法通过使用深度神经网络扩展强化学习，而无需明确设计状态空间。^[21]谷歌DeepMind学习雅达利游戏的研究^[22]带来了人们对深度强化学习或端到端强化学习的重视。

6.2 逆向强化学习

在逆强化学习（IRL）中，没有给出奖励函数。相反，奖励函数是根据从专家观察到的行为推断出来的。这个想法是模仿观察到的行为，这通常是最优的或接近最优的。^[23]

6.3 学徒学习

在学徒学习中，专家展示目标行为。系统试图通过观察来还原策略。

1. Kaelbling, Leslie P.; Littman, Michael L.; Moore, Andrew W. (1996). "Reinforcement Learning: A Survey". Journal of Artificial Intelligence Research. 4: 237–285. arXiv:cs/9605103. doi:10.1613/jair.301. Archived from the original on 2001-11-20.
2. Dimitri P. Bertsekas and John N. Tsitsiklis. "Neuro-Dynamic Programming", Athena Scientific, 1996,[1]
3. Dimitri P. Bertsekas. "Dynamic Programming and Optimal Control: Approximate Dynamic Programming, Vol.II", Athena Scientific, 2012,[2]
4. van Otterlo, M.; Wiering, M. (2012). Reinforcement learning and markov decision processes. Reinforcement Learning. Adaptation, Learning, and Optimization. 12. pp. 3–42. doi:10.1007/978-3-642-27645-3_1. ISBN 978-3-642-27644-6.
5. , Chapter 11.
6. .
7. Burnetas, Apostolos N.; Katehakis, Michael N. (1997), "Optimal adaptive policies for Markov Decision Processes", Mathematics of Operations Research, 22: 222--255
8. Tokic, Michel; Palm, Günther (2011), http://www.tokic.com/www/tokicm/publikationen/papers/KI2011.pdf |chapter-url= missing title (help) (PDF), KI 2011: Advances in Artificial Intelligence, Lecture Notes in Computer Science, 7006, Springer, pp. 335–346, ISBN 978-3-642-24455-1 Unknown parameter |chapter  = ignored (help)
9. Reinforcement learning: An introduction (PDF).
10. .
11. , §6. Temporal-Difference Learning.
12. .
13. .
14. .
15. .
16. .
17. Juliani, Arthur (2016-12-17). "Simple Reinforcement Learning with Tensorflow Part 8: Asynchronous Actor-Critic Agents (A3C)". Medium. Retrieved 2018-02-22.
18. "On the Use of Reinforcement Learning for Testing Game Mechanics : ACM - Computers in Entertainment". cie.acm.org (in 英语). Retrieved 2018-11-27.
19. "Reinforcement Learning / Successes of Reinforcement Learning". umichrl.pbworks.com. Retrieved 2017-08-06.
20. [3] Archived 2017-04-26 at the Wayback Machine
21. Francois-Lavet, Vincent; et al. (2018). "An Introduction to Deep Reinforcement Learning". Foundations and Trends in Machine Learning. 11 (3–4): 219–354. arXiv:1811.12560. doi:10.1561/2200000071.
22. Mnih, Volodymyr; et al. (2015). "Human-level control through deep reinforcement learning". Nature. 518 (7540): 529–533. Bibcode:2015Natur.518..529M. doi:10.1038/nature14236. PMID 25719670.
23. Ng, A. Y., & Russell, S. J. (2000, June). Algorithms for inverse reinforcement learning. In Icml (pp. 663-670).