强化学习数学基础

写在前面

该系列是作者学习西湖大学赵世钰老师的《强化学习的数学原理》这一课程所总结的知识点，通过记录课程笔记加深印象，以及建立起自己的知识框架。

基础概念

网络上关于强化学习的直观例子材料不胜枚举，这里不在介绍。数学上，强化学习中有以下重要的基础概念：

• State：用于描述智能体目前的状态，由所有状态所组成的集合称为状态空间（state space） ；

• Action: 对于当前状态下，智能体所才能采取的可能动作，所以动作是绑定状态的，在状态 下的所有可能动作所组成的集合，称为关于该状态的动作空间（Action space of a state） ;

• State transition：当采取一个动作后，智能体从一个状态转移至另一个状态，这样的过程称为状态转移；

• State transition probability：以概率的形式描述状态转移过程，即 ，对于确定性（deterministic）系统，该概率取值为0/1，对于随机性（stochastic）系统，则该概率取值为0和1之间。

• Policy：描述智能体在一个状态下采取某个动作的策略。用 表示，例如 表示智能体在状态 下采取动作 的概率。仍可分为确定性策略和随机性策略。

• Reward：用于描述智能体在一个状态下采取某个动作所能获得的奖励，用 表示。与Policy相同，数学上仍表述为条件概率形式，例

• Trajectory：表示智能体的轨迹，代表智能体与环境的交互规程。应用上面所定义的基础概念，其本质是state-action-reward的链式过程。

• Return：表示智能体在以上Trajectory中所获得的奖励总和。它能够用来评判一个policy的好坏。

• Discounted return：在return基础上，加了个折扣因子 （0-1之间），作为我们对短期和长期收益注重比例的调节工具。 。此外，加上折扣因子，return的值就会变得有限（finite）即收敛，因为reward有界，而 。

• Episode：智能体按照一个策略与环境进行交互，最终停留在我们所定义的终止状态（terminated state），这个Trajectory就称为一个Episode。因此，episode本质是一个有限的trajectory。

• Markov decision process（MDP）：

  将上面所定义的基础概念串起来，其中包括集合（sets）、概率转移和策略三部分：

  • Sets：

    • state： ;
    • action：
    • reward：
  • Probability distribution:

    • State transition probability：
    • Reward probability：
  • Policy:

  值得注意的是，状态转移概率和奖赏概率是系统的固有属性，我们无法改变；强化学习的目标是要学习到一个好的policy，根据在这个过程中我们是否知道状态转移概率和奖赏概率，即是否掌握该系统的物理模型，强化学习的应用分为model-based（掌握）和model-free（不掌握）。

  MDP有一个重要的特性，即memoryless property，即

贝尔曼等式（Bellman Equation）

考虑如下单步过程：

其实以上单步过程也是off-policy强化学习进行模型训练的样本收集方式 ，这里简单提一下，后续章节会详细阐述；

• 表示离散时间，即一种序关系，因为MD过程本来就是序列形式；
• 分别表示 时间所对应的state和action；
• 表示采取动作 后所获得奖励；

（注意：大写表示一种分布，表示随机变量整体；小写就表示采样出的一个样本，这是一种约定的规范，下同）

回顾第一章的基础概念章节：

• 决定于 ;
• 决定于 ;
• 决定于 ;

扩展到多步trajectory：

定义折扣return为：

• 其中

再上一章，我们提到return能够用来评判一个policy的好坏，而 是随机变量，存在不确定性，怎么比？那就求期望，即得到了State value的定义：

• 它是关于 的函数；
• 它是基于policy的；
• 它反映状态的值，如果其值较大，证明在状态下采取策略 得到的收益大；

进一步拆解上式：

首先计算第一项 ：

计算第二项：

合并上述两项，得到贝尔曼等式：

• 可以看出中框号里面，第一项是短期收益，第二项是长期收益；
• 第二项还是state value，即 和 都是待求的，所以是一种bootstrapping式的结构；
• 上式是假设离线情况，连续则应用积分形式；

对于一个给定系统和给定policy，我们怎么求解任一状态下的state value呢？

为了求解任一状态下的state value，我们需要列出任一状态下的如上公式，为了计算，需要给出matrix-vector形式的贝尔曼等式：

recall that：

重写为：

为了将上式写成matrix-vector形式，我们对 进行编号，即：

带上了编号，我们很容易看出上式写成matrix-vector形式为：

所以，当我们知道系统属性 ，求解贝尔曼等式，显然有：

此外，还可以更方便的迭代式算法：

怎么证明这种迭代式算法能够求到 ？

定义 ，因此 ，

由于 ，所以

由于 并且 中的每个元素都小于1，所以 最终会收敛到0，证毕；

上面定义了state value，作为策略在state粒度好坏的表征；我们还可以从action上进行体现，相似的定义，action value也是期望:

• 是关于state-action pair的函数
• 同样， 基于

再走一遍，观察element-wise粒度的action value，回顾state value：

其中 中框号内的就是action value，即:

所以，state-value与action-value的关系，在贝尔曼等式中体现为：

贝尔曼最优等式(Bellman optimality equation,BOE)

我们在上一章节说，return能够用来评判一个policy的好坏，并且引出了其期望形式，定义为state value。

那么什么是最优的策略呢？

定义：当一个策略 ，相比于其他任意策略 ，对于所有state ，都存在

数学定义为：

向量形式为：

• 从上式中， 即使结果（左式），也是过程（右式），比较tricky

如何求解呢？为了分析，写出element-wise形式：

由于 ，我们求解右式，为了让其最大，显然需要选择能够使 最大的那个动作，即：

当： ，其中

BOE表示为 ，令： ，则BOE就变为 ，而 被我们根据贪婪策略选择动作后，简化为

如何求解这个式子？我们有三个疑问：

• 该式是否可求解？即最优策略是否存在？
• 解是否唯一？即最优策略是否唯一？
• 最优策略是确定性还是随机性的？

Contraction mapping theorem

通过引入contraction mapping theorem来回答上述三个疑问，回顾我们的问题，我们需要求解问题

更通用的：

• Fixed point： 对于函数 是一个固定点，如果满足
• Contraction mapping： 成为收缩映射，如果满足

  • 其中 ，例如 ，对于任意 满足

Theorem: For any equation that has the form ，if is a contraction mapping, then

• Existence: there exists a fixed point satisfying
• Uniqueness: the fixed point is unique
• Algorithm: consider a sequence where