强化学习

视频

参考笔记：

https://blog.csdn.net/xyk_hust/category_8003647.html

https://zhuanlan.zhihu.com/c_135909947

https://datawhalechina.github.io/easy-rl/#/

1、介绍

强化学习（reinforcement learning，RL）：Agent（玩家）在复杂、不确定的 environment （环境）中最大化它能获得的奖励

强化学习与其他机器学习范例的不同

• 无监督
• 延迟奖励（反馈）
• 时间很重要
• Agent 的行为会影响其后续接收到的数据

概念

基本元素：Agent、Environment、Goal

• Agent：智能体，玩家

  Agent 可以观察环境，做出行为，从环境获得奖励

• Environment：环境

  Environment 可以接收 Agent 动作，更新环境信息，给 Agent 奖励

• Goal：目标

主要元素：State、Action、Reward

• State：Agent 和 Environment 处于某种状态（环境状态，个体状态）

  History：是观测、行为、奖励的序列：

  $${H}_{t} = {O}_{1},{R}_{1},{A}_{1}~,...,{O}_{t},{R}_{t},{A}_{t}$$

  State 是所有决定将来的已有的信息，是关于历史的一个函数

  $$S_t = f(H_t)$$

  信息状态：包括历史上所有有用的信息，称 Markov 状态

• Reward：

  强化学习主要基于”奖励假设”：所有问题解决的目标都可以被描述成最大化累积奖励

核心元素：Policy、Value（Agent 的主要组成部分）

• 策略 Policy

  输入一个状态输出一个行动。策略是决定个体行为的机制。

• 价值函数 Value Function

  策略函数取决于价值函数

  1. 状态价值函数：输入一个状态，输出一个实数
  2. 状态行动价值函数：在特定状态下，采取某种行动所具有的价值

  未来奖励的预测，用来评价当前状态的好坏程度

  面对两个不同的状态时，个体可以用一个Value值来评估这两个状态可能获得的最终奖励区别，继而指导选择不同的行为，即制定不同的策略

  一个价值函数是基于某一个特定策略的，不同的策略下同一状态的价值并不相同。某一策略下的价值函数用下式表示：

  $$V_\pi(s) = E_\pi[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+... | S_t = s]$$

其他：

• 模型 Model

  个体对环境的一个建模，它体现了个体是如何思考环境运行机制的，个体希望模型能模拟环境与个体的交互机制。

  模型至少要解决两个问题：

  一是状态转化概率，即预测下一个可能状态发生的概率：

  $$\mathcal{P}^a_{ss'}=p[S_{t+1}=s'|S_t=s,A_t=a]$$

  另一项工作是预测可能获得的即时奖励：

  $$\mathcal{R}^a_s=E[R_{t+1}|S_t=s,A_t=a]$$

  模型并不是构建一个个体所必需的，很多强化学习算法中个体并不试图（依赖）构建一个模型

  模型仅针对个体而言，环境实际运行机制不称为模型，而称为环境动力学(dynamics of environment)，它能够明确确定个体下一个状态和所得的即时奖励。

• 序列决策 Sequential Decision Making

  选择一定的行为系列以最大化未来的总体奖励，序列可能是长期的，奖励可能是延迟的，有时候宁愿牺牲即时（短期）的奖励以获取更多的长期奖励

• 马尔可夫属性 Markov Property

  一个状态 S_t 是马尔科夫的，当且仅当：

  $$P[S_{t+1} | S_t] = P[S_{t+1} | S_1,...,S_t]$$

  如果信息状态是可知的，那么所有历史信息都可以丢掉，仅需要 t 时刻的信息状态就可以了。例如：环境状态是 Markov 的，因为环境状态是环境包含了环境决定下一个观测 / 奖励的所有信息；同样，（完整的）历史 H_t 也是马尔可夫的。

  马尔可夫性举例：

  假如个体状态 = 序列中的后三个事件（不包括电击、获得奶酪，下同），事件序列3的结果会是什么？（答案是：电击）

  假如个体状态 = 亮灯、响铃和拉电闸各自事件发生的次数，那么事件序列3的结果又是什么？（奶酪）

  假如个体状态 = 完整的事件序列，那结果又是什么？（未知）

• 完全可观测的环境 Fully Observable Environments

  个体能够直接观测到环境状态。

  在这种条件下: 个体对环境的观测 = 个体状态 = 环境状态，这种问题是一个马尔可夫决策过程（Markov Decision Process， MDP）

• 部分可观测的环境 Partially Observable Environments

  个体间接观测环境，如一个交易员只能看到当前的交易价格。

  在这种条件下：个体状态 ≠ 环境状态

  这种问题是一个部分可观测马儿可夫决策过程。个体必须构建它自己的状态呈现形式，比如：

  1. 记住完整的历史，这种方法比较原始、幼稚

     $$S^a_t = H_t$$

  2. Beliefs of environment state：个体可以利用已有经验（数据），用各种个体已知状态的概率分布作为当前时刻的个体状态的呈现：

     $$S^a_t=(P[S^e_t=s^1],...,P[S^e_t=s_n])$$

  3. Recurrent neural network：不需要知道概率，只根据当前的个体状态以及当前时刻个体的观测，送入循环神经网络(RNN)中得到一个当前个体状态的呈现：

     $$S^a_t = \sigma(S^a_{t-1}W_s+O_tW_o)$$

个体的分类

个体分为如下三类:

1. 仅基于价值函数的 Value Based：在这样的个体中，有对状态的价值估计函数，但是没有直接的策略函数，策略函数由价值函数间接得到。
2. 仅直接基于策略的 Policy Based：这样的个体中行为直接由策略函数产生，个体并不维护一个对各状态价值的估计函数。
3. 演员-评判家形式 Actor-Critic：个体既有价值函数、也有策略函数。两者相互结合解决问题。

根据个体在解决强化学习问题时是否建立一个对环境动力学的模型，将其分为两大类：

1. 不基于模型的个体: 这类个体并不视图了解环境如何工作，而仅聚焦于价值和/或策略函数。
2. 基于模型的个体：个体尝试建立一个描述环境运作过程的模型，以此来指导价值或策略函数的更新。

学习和规划

• 学习：环境初始时是未知的，个体不知道环境如何工作，个体通过与环境进行交互，逐渐改善其行为策略。
• 规划: 环境如何工作对于个体是已知或近似已知的，个体并不与环境发生实际的交互，而是利用其构建的模型进行计算，在此基础上改善其行为策略。

一个常用的强化学习问题解决思路是，先学习环境如何工作，也就是了解环境工作的方式，即学习得到一个模型，然后利用这个模型进行规划。

探索和利用

强化学习类似于一个试错的学习，个体需要从其与环境的交互中发现一个好的策略，同时又不至于在试错的过程中丢失太多的奖励。探索和利用是个体进行决策时需要平衡的两个方面。

一个形象的比方是，当你去一个餐馆吃饭，“探索”意味着你对尝试新餐厅感兴趣，很可能会去一家以前没有去过的新餐厅体验，“利用”则意味着你就在以往吃过的餐厅中挑一家比较喜欢的，而不去尝试以前没去过的餐厅。这两种做法通常是一对矛盾，但对解决强化学习问题又都非常重要。

预测和控制

在强化学习里，我们经常需要先解决关于预测（prediction）的问题，而后在此基础上解决关于控制（Control）的问题。

预测：给定一个策略，评价未来。可以看成是求解在给定策略下的价值函数（value function）的过程。How well will I(an agent) do if I(the agent) follow a specific policy?
控制：找到一个好的策略来最大化未来的奖励。

2、马尔可夫决策过程（MDPs）

2.1、马尔科夫过程

• Markov 作用：描述环境、几乎所有 RL 问题都可被定义为 MDPs 问题

• Markov 性质（Markov Property）：有了 S_t，就可以丢掉 S₁,...S_t，当前状态就可以决定未来

  $$P[S_{t+1}|S_t]=P[S_{t+1},...,S_t]$$

• Markov 过程（马尔科夫链 ，Markov Chain）

  具有 Markov Property 的 s 到 s’ 事件发生的概率：

  $$\mathcal{P}_{ss'}=P[S_{t+1}=s'|S_t=s]$$

  因此，状态转移矩阵（横竖坐标为不同状态）：

  $$P=\begin{bmatrix} P_{11}& \cdots & P_{1n}\\ \vdots& & \\ P_{n1}& \cdots &P_{nn} \end{bmatrix}$$

  马尔科夫过程（MP 又称 Markov Chain）是一个无记忆的随机过程，可以用一个 元组 <S,P> 表示

  • S 是有限数量的状态集
  • P 是状态转移概率矩阵

  学生马尔科夫过程：

  

2.2、马尔科夫奖励过程

马尔科夫奖励过程（Markov Reward Processes）在马尔科夫过程的基础上增加了奖励 R 和衰减系数 γ：<S,P,R,γ>。

• Reward 是一个 奖励函数。在 S 状态下的奖励是某一时刻 t 处在状态 s下在下一个时刻 t+1 能获得的 奖励期望：（当进入某个状态会获得相应的奖励）

  $$R_s = E[R_{t+1}|S_t=s]$$

• Discount factor 折扣因子 / 衰减系数 Discount Factor：γ∈ [0, 1]

• Return 回报

  回报 G_t 是从 t 时刻开始往后所有的奖励的有衰减的总和（γ 接近 0，则表明趋向于近期性评估；γ接近1则表明偏重考虑远期的利益。）

  $$G_t = R_{t+1} + \gamma R_{t+2}+...=\sum_{k=0}^{\infty} \gamma^kR_{t+k+1}$$

• Value Function

  价值函数给出了某一状态或某一行为的 长期价值

  一个马尔科夫奖励过程中某一状态的 价值函数 为 从该状态开始 的 马尔可夫链 收获的 期望

  $$v(s) = E[G_t|S_t=s]$$

  价值可以仅描述状态，也可以描述某一状态下的某个行为，在一些特殊情况下还可以仅描述某个行为。

  在整个视频公开课中，除了特别指出，约定用 状态价值函数 或 价值函数 来描述针对状态的价值；用 行为价值函数 来描述某一状态下执行某一行为的价值，严格意义上说行为价值函数是 状态行为对价值函数 的简写。

• Bellman 方程 for MRPs

  先尝试用价值的定义公式来推导看看能得到什么：

  $$\begin{aligned} v(s) & =\mathbb{E}\left[G_t \mid S_t=s\right] \\ & =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\ldots \mid S_t=s\right] \\ & =\mathbb{E}\left[R_{t+1}+\gamma\left(R_{t+2}+\gamma R_{t+3}+\ldots\right) \mid S_t=s\right] \\ & =\mathbb{E}\left[R_{t+1}+\gamma G_{t+1} \mid S_t=s\right] \\ & =\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_t=s\right]\end{aligned}$$

  将 G_t+1 变成了 v(S_t+1)。其理由是收获的期望等于收获的期望的期望。下式是针对 MRP 的 Bellman 方程：

  $$V(s)=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]$$

  

该方程看出 v(s) 由两部分组成：

• 该状态的即时奖励期望，即时奖励期望等于即时奖励，因为根据即时奖励的定义，它与下一个状态无关
• 下一时刻状态的价值期望，可以根据下一时刻状态的概率分布得到其期望。如果用s’表示s状态下一时刻任一可能的状态

那么 Bellman 方程可以写成：

$$v(s) = R_s + \gamma \sum_{s'\in S}^{} \mathcal{P_{ss'}}v(s')$$

下图已经给出了 γ=1 时各状态的价值，状态 C₃ 的价值：4.3 = -2 + 1.0 *（0.6 * 10 + 0.4 * 0.8）


• Bellman方程的矩阵形式和求解

  $$v = R + \gamma \mathcal{P}v$$

  结合矩阵的具体表达形式：

  $$\left[\begin{array}{c}v(1) \\ \vdots \\ v(n)\end{array}\right]=\left[\begin{array}{c}\mathcal{R}_1 \\ \vdots \\ \mathcal{R}_n\end{array}\right]+\gamma\left[\begin{array}{ccc}\mathcal{P}_{11} & \ldots & \mathcal{P}_{1 n} \\ \vdots & & \\ \mathcal{P}_{11} & \ldots & \mathcal{P}_{n n}\end{array}\right]\left[\begin{array}{c}v(1) \\ \vdots \\ v(n)\end{array}\right]$$

  Bellman 方程是一个线性方程组，因此理论上解可以直接求解：

  $$\begin{aligned} v & =\mathcal{R}+\gamma \mathcal{P} v \\ (I-\gamma \mathcal{P}) v & =\mathcal{R} \\ v & =(I-\gamma \mathcal{P})^{-1} \mathcal{R}\end{aligned}$$

  计算的复杂度是 O(n³)，直接求解仅适用于小规模的MRPs。
  大规模 MRP 的求解通常使用迭代法。常用的迭代方法有：动态规划 Dynamic Programming、蒙特卡洛评估 Monte-Carlo evaluation、时序差分学习 Temporal-Difference

2.3、马尔科夫决策过程

Markov Decision Process（MDPs）就是在 MRPs 的基础上引入了 Actions

看起来很类似马尔科夫奖励过程，但这里的 P 和 R 都与具体的 行为a 对应，而不像马尔科夫奖励过程那样仅对应于某个 状态

A 表示的是有限的行为的集合。具体的数学表达式如下：

状态转移概率矩阵：

$$\mathcal{P}_{s s^{\prime}}^{a}=\mathbb{P}\left[S_{t+1}=s^{\prime} \mid S_{t}=s, A_{t}=a\right]$$

奖励函数：

$${R}_{s}^{a}=\mathbb{E}\left[R_{t+1} \mid S_{t}=s, A_{t}=a\right]$$

• 策略 Policy

  策略 π 是概率的集合或分布，其元素 π(a|s) 为对过程中的某一状态 s 采取可能的行为 a 的概率

  $$\pi(a|s) = \mathbb{P}[A_t=a|S_t=s]$$

  一个策略完整定义了个体的行为方式，定义了个体在各状态下各可能的行为及其概率

  策略仅和当前的状态有关，与历史信息无关；

  某一确定的策略是静态的，与时间无关；但是个体可以随着时间更新策略。

  当给定一个 MDP：M=<S,A,P,R,γ> 和一个策略 π，那么状态序列 S₁,S₂... 是一个马尔科夫过程 <S,P^π>

  同样，状态和奖励序列 S₁,R₂,S₂,R₃,S₃,... 是一个马尔科夫奖励过程 <<S,P^π,R^π,γ>>，并且在这个奖励过程中满足下面两个方程：

  $$\mathcal{P}_{s,s'}^\pi = \sum_{a\in A} \pi(a|s)\mathcal{P}_{ss'}^a$$

• 基于策略 π 的价值函数

  状态价值函数：表示从状态 s 开始，**遵循当前策略 **时所获得的收获的期望；衡量个体处在状态 s 时的价值大小。数学表示如下

  $$\mathsf{v}_\pi(s)=\mathbb{E}_\pi[G_t|S_t=s]$$

  行为价值函数：对当前状态 s 执行某一具体行为 a 所能的到的收获的期望；衡量对当前状态执行行为 a 的价值大小。

  $$q_\pi(s,a) = \mathbb{E}_\pi[G_t|S_t=s,A_t=a]$$

  

  例如： 2.7 = 0.5 * (-2 + 1 * 7.4) + 0.5 * (0 + 1 * 0)

• Bellman 期望方程

  状态价值函数和行为价值函数与可以改 用下一时刻状态价值函数或行为价值函数来表达，具体方程如下：

  $$\mathsf{v} _\pi(s)=\mathbb{E}\pi[R_{t+1}+\gamma \mathsf{v} _\pi(S_{t+1})|S_t=s]$$

  $$\mathsf{q}_{\pi}(s,a)=\mathbb{E}[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1}) | S_t=s,A_t=a]$$

• Bellman期望方程矩阵形式

  

• 最优价值函数

  选状态价值函数、行为价值函数中价值最大的

  $$v_*=\mathsf{max} v_\pi(s)\\ q_*(s,a)=\mathsf{max}q_\pi(s,a)$$

• 最优策略

  1. 存在一个最优策略，比任何其他策略更好或至少相等；
  2. 所有的最优策略有相同的最优价值函数；
  3. .所有的最优策略具有相同的行为价值函数。

• 寻找最优策略

  可以通过最大化最优 行为价值函数 来找到最优策略：

  

• Bellman 最优方程

  一个 状态 的 最优价值 等于从该状态出发采取的所有行为产生的行为价值中 最大的那个行为价值：

  采取某个行为的最优价值由 两部分组成，一部分是离开状态 s 的 即刻奖励，另一部分则是所有能到达的状态 s’ 的 最优状态价值按出现概率求和

• 求解 Bellman 最优方程

  1. Bellman 最优方程是非线性的
  2. 没有固定的解决方案
  3. 通过一些迭代方法来解决：价值迭代、策略迭代、Q学习、Sarsa等。

3、动态规划

动态规划应用于 MDP 的规划问题（planning）而不是学习问题（learning），就是要知道 状态转移概率 和对应的 reward 才行