强化学习

视频

参考笔记：

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、Environment、Goal

• Agent：智能体，玩家

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

• Environment：环境

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

• Goal：目标，选择 action 来最大化未来奖励

主要元素：State、Action、Reward、History

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

  Agent：状态中会有对环境总结的状态

  History：是 observations，actions，rewards 的序列的序列：

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

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

  $$S_t = f(H_t)$$

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

• Reward：

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

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

• 策略 Policy

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

• 价值函数 Value Function

  策略函数取决于价值函数

  在当前状态下采取某 action 的好坏程度

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

  在当前 policy 下，获得未来奖励的期望预测，用来评价当前状态的好坏程度

  面对两个不同的状态时，个体可以用一个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、马尔科夫奖励过程

马尔科夫奖励过程（MRPs）在马尔科夫过程的基础上增加了奖励 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 才行

动态规划可完成预测问题和控制问题的求解

• 预测问题：
  • Input：MDP<S;A;P;R;γ> and policy π 或 MRP<S;P^π;R^π;γ>
  • Output：value function v_π
  • 根据当前 MDP 过程，衡量每一个状态的 value
• 控制问题
  • Input：MDP<S;A;P;R;γ> without policy
  • Output：最优 value function，进而输出最优 policy π_*

策略迭代 Policy Iteration

• Policy evaluation ：评估 π 的 value function V_π
• Policy improvement ：根据得到的 V_π，利用贪心算法获得优化的 policy π‘
• 根据得到的 π’ 以及我们的状态转移概率，进行新的一轮 Policy evaluation
• 这个过程一直持续到新旧两轮迭代的相同

价值评估解决方案

• 给定任意一个 policy，通过迭代 Bellman Expectation Equation 找到一个最优 policy
• 初始化一个 value function 的值，比如全部置为1，同时初始化一个 policy。这个初始化不会影响迭代结果，并且，它不会影响收敛速率
• 接着使用 Bellman Expectation Equation，利用已经得到的 value function 来计算新一轮迭代得到的 value function

$$v_{k+1} = \sum_{a\in A}\pi(a|s)(R^a_s + \gamma \sum_{s' \in S}P_{ss'}^av_k(s'))$$

举例：格子世界

• action：上下左右四个方向等概率
• reward：-1（每进行一次 action 奖励为 -1）
• γ：1（折扣因子）


4、不基于模型的预测

上章介绍从理论上解决一个已知的 MDP：

• 通过动态规划，评估给定策略，得到最优价值函数，根据最优价值函数确定最优策略
• 也可以直接进行不基于任何策略的状态价值迭代得到最优价值函数和最优策略

如何直接从 Agent 与环境的交互来得得到一个估计的最优价值函数和最优策略？

• 本讲的内容，聚焦于 策略评估，即预测，在给定的策略同时不清楚 MDP 细节的情况下，估计 Agent 会得到怎样的最终奖励
• 下一讲将利用本讲的主要观念来进行控制进而找出最优策略，最大化 Agent 的奖励。

本章分为三个部分：蒙特卡洛强化学习、时序差分强化学习和介于两者之间的 λ 时序差分强化学习

4.1、蒙特卡洛强化学习 MC

蒙特卡洛强化学习：

• 不清楚 MDP 状态转移及即时奖励的情况下
• 不基于模型本身，直接从完整的 Episode 来学习状态价值
• 通常情况下某状态的价值等于在多个 Episode 中以该状态算得到的所有收获的平均
• 理论上 Episode 越多，结果越准确

完整的 Episode：指必须从某一个状态开始，Agent 与 Environment 交互直到终止状态，环境给出终止状态的即时收获为止

完整的 Episode 包含的信息：状态的转移、使用的行为序列、中间状态获得的即时奖励以及到达终止状态时获得的即时奖励

蒙特卡洛策略评估

**目标：**在给定策略下，从一系列的完整 Episode 经历中学习得到该策略下的状态价值函数

• 基于策略 π 的 Episode 序列：S₁,A₁,R₂,S₂......
• t 时刻 S_t 的收获：G_t = R_t+1 + γR_t+2 +.... γ^T-1R_T
• T 为终止时刻
• 策略 π 下某一状态 s 的价值： V_π(S) = E_π[G_t | S_t = s]

访问蒙特卡洛策略评估

• 首次访问蒙特卡洛策略评估：对于每一个 Episode，仅当该状态第一次出现时列入计算

  • 状态出现的次数加一：N(s) = N(s) + 1
  • 总收获值更新：S(s) + S(s) + G_t
  • 状态 s 的价值：V(s) = S(s) / N(s)
  • 当 N(s) 趋于无穷：V(s) = v_π(s)

• 每次访问蒙特卡洛策略评估：状态 s 每次出现在状态转移链时，计算的具体公式与上面的一样，但具体意义不一样

4.2、时序差分学习 TD

它也从 Episode 学习，但是它可以学习不完整的 Episode

算法在估计某一个状态的价值时，用的是离开该状态的即刻奖励 R_t+1 与下一状态 S_t+1 的预估状态价值乘以衰减系数

• TD 的目标值：R_t+1 + γV(S_t+1)
• TD 误差 R_t+1 + γV(S_t+1) - V(S_t)