🗒️赵世钰老师的【强化学习的数学原理】
00 分钟
2021-7-2
2024-4-15
type
status
date
slug
summary
tags
category
icon
password
 
 
以下是关于强化学习的总结
第1章《基本概念》为强化学习的基础概念做了介绍,并为后续更高级主题的讨论奠定了基础。以下是本章的关键概念和部分的概要:
  • 强化学习概念介绍: 本章以马尔可夫决策过程(MDP)的背景开始,强调了强化学习在需要决策的广泛场景中的适用性。这里引入的基本原则,如状态、行动和奖励,对于理解余下内容至关重要。
  • 格子世界示例: 使用一个简单而具有说明性的格子世界例子来具体演示强化学习的概念。在这个示例中,一个机器人在格子中导航,目标是到达目标单元格同时避开禁止的单元格。这个场景概括了在有限制和目标的环境中导航的挑战,贯穿全书作为一个反复提及的参考。
  • 状态和行动: 本章详细讨论了格子世界中的状态和行动概念。状态代表机器人在格子上的位置,行动是机器人可以执行的可能移动。这一部分为理解代理如何与环境交互奠定了基础。
  • 状态转移: 状态转移的讨论探讨了行动如何使代理从一个状态转移到另一个状态。这一节既讨论了确定性转移也讨论了随机转移,强调了理解环境动态对于有效决策的重要性。
  • 策略: 策略指导代理在每个状态下的行动,引导其在环境中的行为。章节讨论了确定性和随机策略,展示了它们如何影响代理通过格子世界的路径。
  • 奖励: 奖励概念作为基于代理行动的反馈机制被引入。奖励影响学习过程,鼓励导致期望结果的行为。章节讨论了格子世界示例中如何分配奖励及其对策略学习的影响。
  • 轨迹、回报和情节: 本节解释了状态、行动和奖励序列(轨迹)如何促进代理的学习。它引入了回报(累积奖励)和情节的概念,后者是到达终止状态或无限持续的序列。
  • 马尔可夫决策过程: 本章在MDPs框架下形式化了前面介绍的概念,为理解强化学习提供了数学基础。这一节强调了马尔可夫性质对于建模决策问题的重要性。
  • 总结和问答: 章节以关键点的总结和相关于强化学习概念的常见问题的答疑结束。这最后一部分加强了读者的理解并解决了潜在的混淆区域。
总体而言,第1章在强化学习的基础上建立了坚实的基础,使用格子世界示例来阐释关键概念。这些基础对于理解后续章节讨论的更复杂的算法和策略至关重要,包括贝尔曼方程、值迭
代和策略迭代、蒙特卡洛方法、时差方法以及各种形式的函数逼近和策略优化。
 
在第2章《状态值与贝尔曼方程》中,主要介绍了强化学习中的几个关键概念和数学表达,下面是这些核心内容及其对应的方程:

核心概念:状态值和行动值

  • 状态值(vπ(s))表示在策略π下从状态s开始的预期回报。
  • 行动值(qπ(s, a))表示在策略π下从状态s开始并采取行动a的预期回报。

贝尔曼方程

贝尔曼方程描述了状态值或行动值之间的递归关系,是强化学习中评估策略和寻找最优策略的关键工具。

状态值的贝尔曼方程

这里,是在状态s下选择行动a的策略概率,分别是给定状态和行动下获得奖励r和转移到状态s'的概率,γ是折扣因子,表示未来奖励的当前价值。

行动值的贝尔曼方程

行动值的贝尔曼方程将一个行动的值与其可能导致的下一个状态的值联系起来,形成了一个关于行动值的递归表达式。

从贝尔曼方程计算状态值

利用贝尔曼方程可以通过迭代或者闭式解的方式来计算状态值。迭代方法是强化学习中常用的一种技术,它通过反复更新状态值直至收敛到稳定的解。

从状态值到行动值的转换

状态值和行动值之间可以相互转换,这为评估和改进策略提供了灵活的工具。通过计算和比较所有可能行动的行动值,可以找到最优行动,从而改进策略。
通过细致解读本章内容,可以深入理解强化学习中状态值和行动值的概念,以及贝尔曼方程如何作为连接这些概念的桥梁,帮助我们评估和优化策略。
 
第3章《最优状态值与贝尔曼最优方程》进一步深入探讨了强化学习中的核心概念,特别是如何定义和寻找最优策略以及最优状态值。这里是对本章内容的总结,包括关键公式和方程:

最优策略与最优状态值的定义

  • 最优策略是指对于所有状态s,其状态值不小于任何其他策略对应的状态值的策略。
  • 最优状态值是在最优策略下,从状态s开始并遵循该策略所能获得的最大预期回报。

贝尔曼最优方程 (Bellman Optimality Equation)

  • 对于每个状态s,贝尔曼最优方程的元素形式表达为: 其中,表示在状态s下的最优状态值,是从状态s采取行动a转移到状态s'并获得奖励r的概率,是折扣因子。

如何改进策略

  • 通过计算状态值和行动值,可以确定在某状态下采取哪个行动能提高策略的性能。
  • 最优策略可以通过选择具有最大行动值的行动来更新现有策略。

贝尔曼最优方程的求解

  • 贝尔曼最优方程的解包括最优状态值和最优策略。该方程是非线性的,但具有收缩映射的性质,可以通过迭代算法求解。

最优策略的性质

  • *存在性和唯一性:**最优状态值总是存在且唯一的,但最优策略可能不唯一。
  • *决定性:**尽管最优策略可能是随机的,但总存在决定性的贪婪最优策略。
  • *贪婪最优策略:**对于任何状态s,总存在一个贪婪策略选择使行动值最大化的行动,形式上为: 其中,是在状态s采取行动a并遵循最优策略所能获得的最大预期回报。

影响最优策略的因素

  • 折扣因子和奖励函数是影响最优策略选择的主要因素。
  • 折扣因子的大小决定了策略的远见性;奖励函数的设置影响策略的偏好和避障行为。
本章强调了贝尔曼最优方程在寻找最优策略和理解最优状态值方面的核心作用,为理解和应用强化学习算法提供了坚实的理论基础。
 
第4章《值迭代和策略迭代》介绍了强化学习中用于寻找最优策略的三种算法:值迭代、策略迭代和截断策略迭代。这些算法是理解和实施强化学习的关键工具。以下是对这一章内容的总结,包括算法的核心步骤和公式:

值迭代 (Value Iteration)

值迭代是直接求解贝尔曼最优方程的算法,通过反复迭代更新状态值来逼近最优解。每次迭代包括以下两个步骤:
  1. 策略更新 (Policy Update):根据当前的值函数估计来选择最优策略。
  1. 值更新 (Value Update):根据更新后的策略和当前的值函数来更新值函数的估计。
值迭代算法的核心更新公式为:

策略迭代 (Policy Iteration)

策略迭代由两个主要步骤组成,反复执行直到找到最优策略:
  1. 策略评估 (Policy Evaluation):固定策略,计算当前策略下的状态值函数。
  1. 策略改进 (Policy Improvement):根据当前的状态值函数来改进策略。
策略评估的贝尔曼方程为:
策略改进步骤根据当前状态值函数更新策略:

截断策略迭代 (Truncated Policy Iteration)

截断策略迭代是一个介于值迭代和策略迭代之间的算法,它在策略评估步骤中执行有限次迭代,而不是求解直到完全收敛。
截断策略迭代的两个主要步骤为:
  1. 有限次的策略评估:对于每个状态s,执行有限次的策略评估更新。
  1. 策略改进:与策略迭代中的策略改进步骤相同。
这一章通过介绍这三种算法,展示了如何在强化学习中找到最优策略。每种算法都基于贝尔曼方程和最优性原理,通过不同的方式逼近最优策略和最优状态值函数。这些算法为后续章节介绍的模型自由强化学习算法奠定了理论基础。
 
在第5章《蒙特卡洛方法》中,详细介绍了三种基于蒙特卡洛(MC)方法的强化学习算法。这些算法利用样本数据而不依赖于环境模型来学习最优策略。下面是这些算法的核心公式和方程:

MC Basic算法

MC Basic算法通过替换策略迭代中的模型依赖的策略评估步骤为基于MC的模型无关估计来实现。对于给定的策略π和行动a,在状态s下的行动值可以通过以下MC估计得到: 其中,是从状态s采取行动a并遵循策略π得到的第i个回报,n是总的采样次数。

MC Exploring Starts算法

MC Exploring Starts算法要求算法的初始化能够保证所有状态-行动对都有可能被探索到。该算法对MC Basic进行了改进,以更高效地利用样本。行动值的更新公式为: 其中,是从t时刻起在状态s采取行动a获得的回报,是状态s下行动a被采取的总次数。

MC ε-Greedy算法

MC ε-Greedy算法通过ε-贪婪策略来平衡探索和利用,允许在策略改进步骤中以一定概率选择非贪婪行动。对于状态s和行动a,其ε-贪婪策略下的行动值更新公式保持不变,但策略改进使用了ε-贪婪方法:
其中,是在状态s可采取的行动数,是在当前策略下估计的行动值最高的行动。
这些算法展示了如何在不依赖模型的情况下通过直接从环境交互中学习到的经验来估计状态-行动对的值,并据此改进策略。特别是,MC ε-Greedy算法通过调整ε值,在确保算法能够探索所有可能的状态-行动对的同时,也尽可能地利用了已知的最优行动。
 
这些蒙特卡洛(MC)方法实际上用来求解整个强化学习问题中的最优策略,而不仅仅是单个状态\(s\)的最优策略。MC方法通过从环境中收集的样本来估计状态-行动对的值(\(q(s, a)\)),并基于这些估计值来改进策略。这些方法的目标是为整个决策过程找到一个最优策略\(\pi^*\),该策略最大化从任何初始状态开始的长期回报。

如何理解这些算法:

  • MC BasicMC Exploring Starts 算法通过生成情节(episode)并从这些情节中学习来逼近最优策略。它们依赖于策略迭代的框架,即交替进行策略评估和策略改进,以逐步提升策略的性能。这些算法不是为了找到单个状态的最优策略,而是为了整个状态空间找到最优策略。
  • MC ε-Greedy 算法通过在策略改进步骤中采用ε-贪婪策略,平衡了探索和利用,以确保所有状态-行动对都有机会被探索到,从而提高学习过程中的全局优化能力。ε-贪婪策略在选择当前估计的最佳行动(利用)与随机探索其他可能的行动之间找到平衡。
这些方法的共同点在于,它们都旨在通过交互学习来发现能够最大化期望回报的行动策略。通过这种方式,算法可以在整个状态空间内找到优化的行动策略,而不是局限于为单个状态寻找最优策略。通过持续的学习和策略改进,蒙特卡洛方法能够逐渐逼近全局最优策略,这种策略能够在整个环境中提供最好的长期回报。
 
第6章《随机逼近》介绍了强化学习中从具体模型到无模型,从表格表示到函数表示的转变,并介绍了随机逼近的基本工具和算法。这一章是为了准备学习后续章节中的时序差分算法而设立的,因为时序差分算法与本章讨论的算法有着本质的不同。本章虽然没有引入具体的强化学习算法,但为理解后续章节奠定了必要的基础。

6.1 动机示例:平均值估计

本节通过平均值估计问题,演示如何将非增量算法转换为增量算法。考虑随机变量X,目标是估计。假设有一系列独立同分布的样本可以通过下式近似:
这是蒙特卡洛估计的基本思想。接下来,展示了两种计算的方法,非增量方法和增量方法,其中增量算法表达为:

6.2 Robbins-Monro算法

Robbins-Monro (RM) 算法是随机逼近领域的开创性工作。假设我们要找到方程的根,其中\(w\)是未知变量,是一个函数。RM算法可以解决这个问题,即使我们只能获得带有噪声的的观察值。RM算法的表达式为:

6.3 Dvoretzky的收敛定理

Dvoretzky定理是随机逼近领域的经典结果,可用于分析RM算法和许多强化学习算法的收敛性。本定理说明了在满足某些条件下,随机过程会几乎必然收敛到零。

6.4 随机梯度下降 (SGD)

SGD是机器学习领域广泛使用的算法,可以视为RM算法的一个特例。SGD通过使用随机样本替代真实梯度来解决优化问题。对于优化问题,SGD算法的更新规则为:
本章还讨论了SGD的收敛模式、确定性形式的SGD、批量梯度下降(BGD)、SGD以及小批量梯度下降(MBGD)算法,并提供了SGD的收敛性定理和证明。

总结

第6章《随机逼近》通过引入随机逼近的基本概念和算法,如Robbins-Monro算法和SGD算法,为理解和准备后续章节中的时序差分学习算法提供了必要的基础。这些算法在强化学习中的应用是解决根查找或优化问题,特别是在模型未知的情况下,如何利用随机样本来逼近问题的解。
 
第7章《时序差分方法》详细介绍了强化学习中的时序差分(TD)学习方法。这些方法是基于模型无关的,可以在没有环境模型的情况下,通过样本学习来估计状态或动作的价值,并用于寻找最优策略。

7.1 TD状态值学习

TD学习是一类强化学习算法的总称,特指一种用于估计给定策略下状态价值的经典算法。基本TD学习算法的更新公式如下:
其中,是在时刻对状态的价值估计,是学习率,是奖励,是折扣因子。

7.2 Sarsa:动作价值的TD学习

Sarsa算法可以直接估计给定策略下的动作价值。Sarsa的更新公式如下:

7.3 n步Sarsa

n步Sarsa是Sarsa的泛化,可以看作是Sarsa和MC学习的中间形态,其中n=1时退化为Sarsa,n趋向无穷时接近MC学习。n步Sarsa的更新公式为:
其中,是从时刻开始的n步折扣回报。

7.4 Q学习:最优动作价值的TD学习

Q学习直接估计最优动作价值,以此找到最优策略,不需要与策略改进步骤结合。Q学习的更新公式如下:

7.5 统一视角

所有TD算法可以通过以下统一表达式表示:
其中,是不同TD算法中的TD目标。

概括

本章引入了用于强化学习的TD学习方法,包括Sarsa、n步Sarsa和Q学习等算法。这些算法可视为解决贝尔曼或贝尔曼最优方程的特殊随机逼近算法。除了Q学习之外,本章介绍的TD算法用于评估给定策略,通过与策略改进步骤结合,可以用来学习最优策略。Q学习与其他TD算法相比,在概念上略有不同,因为它是离策略的,旨在直接解决贝尔曼最优方程。
 
第8章《值函数逼近》深入探讨了时序差分学习算法,特别是在状态/动作值的表示上采用了不同的方法。之前的章节中,状态/动作值是通过表格的方式表示的。虽然表格方法直观易懂,但它在处理大型状态或动作空间时效率较低。为了解决这个问题,本章引入了函数逼近方法,这已成为表示值的标准方式,也是将人工神经网络作为函数逼近器引入强化学习的起点。函数逼近的思想不仅可以用于表示值,还可以扩展到表示策略,如第9章所介绍的。

8.1 值的表示:从表到函数

这部分通过一个示例展示了表格方法和函数逼近方法之间的差异。假设有个状态,其状态值为。如果使用表格方法,估计的值可以存储在一个表中,直接从表中读取或更新任何值。而函数逼近方法,则是将作为点拟合或逼近成一条曲线。最简单的曲线是直线,可以描述为: 其中,是状态的特征向量。

函数逼近方法的效率

函数逼近方法在存储方面更有效,因为它只需要存储低维的参数向量。这种方法提高存储效率的同时牺牲了准确性,因为直线可能无法准确拟合所有点。

值的更新

当值通过函数表示时,更新一个值的方式完全不同,我们必须通过更新来间接改变值。如何更新以找到最优状态值将在后文详细讨论。

复杂函数的使用

我们可以使用更复杂的函数拥有比直线更强的逼近能力。例如,考虑二阶多项式:
可以使用更高阶的多项式曲线来拟合点。曲线的阶数越高,逼近精度可以提高,但参数向量的维度也会增加,需要更多的存储和计算资源。

8.2 基于函数逼近的状态值TD学习

这部分展示了如何将函数逼近方法整合到TD学习中,以估计给定策略的状态值。这个算法将被扩展用于学习动作值和最优策略。

目标函数

假设分别是状态的真实状态值和近似状态值。需要找到最优的,使得能最好地逼近每个状态的。特别地,目标函数为:
本章引入的函数逼近方法为理解和准备后续章节中的时序差分学习算法提供了必要的基础。这些算法在强化学习中的应用是解决根查找或优化问题.
 
第9章《策略梯度方法》介绍了函数逼近不仅可以用来表示状态/动作值(如第8章所述),也可以用来表示策略。到目前为止,策略通常以表格的形式表示,即所有状态的动作概率存储在一个表中。本章展示了如何通过参数化的函数π(a|s, θ)来表示策略,其中θ是参数向量。当策略以函数形式表示时,可以通过优化某些标量度量来获得最优策略,这种方法被称为策略梯度方法。与本书之前章节讨论的基于价值的方法相比,策略梯度方法基于策略,具有处理大型状态/动作空间更高的效率,以及更强的泛化能力,因此在样本使用方面更加高效。

9.1 策略表示:从表到函数

策略的函数表示法与表表示法的主要区别在于如何定义最优策略、如何更新策略以及如何检索动作的概率。

9.2 定义最优策略的度量

如果策略由函数表示,则存在两种类型的度量用于定义最优策略。一种是基于状态值的,另一种是基于即时奖励的。
  • 度量1:平均状态值,定义为所有状态的状态值的加权平均,权重为d(s),可视为状态s的概率分布。
  • 度量2:平均奖励,定义为所有状态的平均一步奖励,其中dπ是在策略π下的稳态分布。

9.3 度量的梯度

策略梯度方法的核心是计算给定度量相对于θ的梯度,使用基于梯度的方法来最大化这些度量。策略梯度定理提供了J(θ)的梯度的表达式: \[∇θJ(θ) = \sum_{s∈S} η(s) \sum_{a∈A} ∇θπ(a|s, θ)qπ(s, a),\] 其中η是状态分布,∇θπ是π关于θ的梯度。

9.4 蒙特卡洛策略梯度(REINFORCE)

使用梯度上升算法来最大化J(θ),算法通过将真实梯度替换为随机梯度来进行。REINFORCE或蒙特卡洛策略梯度是最早且最简单的策略梯度算法之一。

9.5 总结

本章介绍的策略梯度方法是许多现代强化学习算法的基础,它基于策略。策略梯度方法的最复杂部分是度量的梯度的推导。幸运的是,不同情景下梯度的表达式相似,因此可以总结在策略梯度定理中。对于许多读者来说,了解这个定理的结果就足够了,无需知道证明的细节。
 
 
第10章《演员-评论家方法》详细介绍了将策略基方法与值基方法结合的演员-评论家架构。在此架构中,“演员”代表策略更新步骤,而“评论家”则指值更新步骤。本章阐述了如何通过扩展第9章介绍的策略梯度算法来获得演员-评论家方法,并强调了在学习本章内容之前理解第8章和第9章的重要性。

10.1 最简单的演员-评论家算法 (QAC)

最简单的演员-评论家算法通过扩展策略梯度算法得到,核心公式为:
这显示了如何将策略基方法和值基方法结合起来。在此公式中,需要知道,即行动值的估计,这要求有另一个基于值的算法来生成这个估计值。

10.2 优势演员-评论家 (A2C)

优势演员-评论家算法引入了基线来减少估计的方差,其中优势函数被用于更新策略,而不是行动值的绝对值。该算法的核心是减少估计方差,使学习过程更稳定。

10.3 离线策略演员-评论家

离线策略演员-评论家算法使用重要性采样来利用由不同策略生成的样本,允许使用由行为策略β生成的样本来学习目标策略π。算法的关键步骤为:
其中,是TD误差,用于估计优势函数。

10.4 确定性演员-评论家

确定性演员-评论家方法展示了策略可以强制为确定性,而不是随机的。这对于处理连续动作空间特别重要,因为它天然地是离线策略,并且可以有效处理大型或连续动作空间。

总结

第10章深入探讨了演员-评论家方法,这是结合了策略基方法和值基方法的强化学习算法。通过引入基线和利用重要性采样,演员-评论家方法能够在离线策略的情况下学习,同时引入确定性策略为处理连续动作空间提供了新的途径。这些方法在现代强化学习中广泛使用,为开发更高级的算法如SAC、TRPO、PPO和TD3等提供了基础。
上一篇
计算机组成原理
下一篇
算法设计与分析

评论
Loading...