[UCAS强化学习]2·马尔可夫决策过程

1 马尔科夫过程

马尔可夫性质：给定当前状态，未来状态与过去状态（即智能体的历史轨迹）是条件独立的，即： $$P(S_{t+1}|S_t)=P(S_{t+1}|S_1,\dots ,S_t)$$

强化学习主要研究的是具有马尔可夫性的问题。

状态转移矩阵：对于马尔可夫状态 $s$ 和它的后继状态 $s^{\prime }$，记： $${\mathcal{P}}_{s{s}^{\prime }}=P(S_{t+1}=s^{\prime }|S_t=s)$$ 称矩阵 $\mathcal{P}$ 为状态转移矩阵。

定义：马尔可夫过程 (Markov Process) 是一个元组 $⟨\mathcal{S},\mathcal{P}⟩$，其中：

• $\mathcal{S}$ 是一个有限状态集
• $\mathcal{P}$ 是状态转移矩阵

例子：“学生马尔可夫链”的状态转移图和状态转移矩阵：

我们可以从这个马尔可夫过程中采样，得到一些轨迹 (episodes)，例如：

• C1, C2, C3, Pass, Sleep
• C1, FB, FB, C1, C2, Sleep
• C1, C2, C3, Pub, C2, C3, Pass, Sleep
• C1, FB, FB, C1, C2, C3, Pub, C1, FB, FB, FB, C1, C2, C3, Pub, C2, Sleep
• ……

2 马尔可夫奖励过程

在马尔可夫过程中加入奖励，就得到了马尔可夫奖励过程。

2.1 定义

定义：奖励 (reward) $$ 是一个随机变量，表示 $$ 时刻的奖励。为什么说它是一个随机变量呢，因为对于从同一个马尔可夫过程中采样出的不同轨迹，$$ 时刻的奖励是不同的；换句话说，对于某特定采样出的轨迹，其 $$ 时刻的奖励是随机变量 $$ 的某个特定取值。

定义：马尔可夫奖励过程 (Markov Reward Process, MRP) 是一个元组 $$，其中：

• $$ 是一个有限状态集
• $$ 是状态转移矩阵
• $$ 是奖励函数 (reward function)，$$
• $$ 是衰减系数 (discount factor)

例子：“学生 MRP”的状态转移图：

2.2 回报

定义：回报 (return) $$ 是从时间戳 $$ 开始的总加权奖励： $$ 由于 $$ 是随机变量，$$ 自然也是随机变量，其具体取值随采样出的轨迹的不同而不同。

为什么需要衰减系数？

• 数学上处理较为方便
• 避免在循环马尔可夫过程上出现无穷大的回报
• 我们的建模往往不太精准，对未来的把握不是很确定
• 对动物/人类的行为研究表明，我们更喜欢短期（立即的）奖励
• 如果你真的觉得衰减系数不好，那设置 $$ 即可

2.3 价值函数

回报 $$ 是一个随机变量，对于不同的采样结果具有不同的值，为了衡量平均的未来总回报，定义价值函数 (value function) 为 $$ 的期望： $$

例子：仍以“学生 MRP”为例：

【个人认为这一页 slide 上的 $$ 应该写作 $$（随机变量 $$ 的各种可能取值），$$ 应该是这些 $$ 的平均，即 $$ 的期望】

对上述定义的小结：

• 奖励 $$ 是时间 $$ 的函数，是一个随机变量，表示 $$ 时刻获得的奖励
• 奖励函数 $$ 是状态 $$ 的函数，表示在状态 $$ 处获得奖励的条件期望：$$
• 回报 $$ 是时间 $$ 的函数，是一个随机变量，表示从 $$ 时刻开始未来的（加权）总奖励
• 价值函数 $$ 是状态 $$ 的函数，表示在状态 $$ 处未来的（加权）总奖励的条件期望：$$

2.4 贝尔曼方程

根据 $$ 的定义式，有： $$ 这意味着 $$ 由立即奖励 $$ 和衰减后的未来奖励 $$ 构成，我们继续推导： $$ 倒数第二行利用了全期望公式。上式就是贝尔曼方程 (Bellman equation)，我们可以将其写作矩阵形式： $$ 也即： $$ 可以看出，贝尔曼方程是一个线性方程，因而可以直接求解： $$ 然而，矩阵求逆的复杂度是 $$，其中 $$ 是状态数量，因此这种方法只适用于小规模 MRP。在后续课程中我们会学到一些求解大规模 MRP 的迭代算法，包括：

• 动态规划 (Dynamic Programming)
• 蒙特卡洛估计 (Monte-Carlo evaluation)
• 时序差分学习 (Temporal-Difference learning)

3 马尔科夫决策过程

在 MRP 中加入动作 (action)，就得到了马尔科夫决策过程。

3.1 定义

定义：马尔科夫决策过程 (Markov Decision Process, MDP) 是一个元组 $$，其中：

• $$ 是一个有限状态集
• $$ 是一个有限动作集
• $$ 是状态转移矩阵，$$
• $$ 是奖励函数，$$
• $$ 是衰减系数 (discount factor)

注意 $$ 的定义都加上了动作 $$ 作为条件。

例子：“学生 MDP”的状态转移图如下所示：

3.2 策略

定义：策略 (policy) $$ 表示智能体在状态 $$ 的条件下做出各动作的概率分布： $$ 一个策略定义了智能体的行为，它仅依赖于当前状态而与历史无关。虽然上述定义式中写了下标 $$，但是仅是为了书写方便，策略是静态的，和时间无关。

MDP 与 MP 和 MRP 的联系：给出一个 MDP $$ 和一个策略 $$，则：

• $$ 是一个 MP
• $$ 是一个 MRP

其中： $$

这两个式子是条件概率（以 $$ 为条件）下的全概率公式——在状态 $$ 下，依照策略 $$，有 $$ 的概率做出动作 $$，做出动作 $$ 后有 $$ 的概率转移到状态 $$，能获得期望奖励为 $$.

3.3 状态/动作-价值函数

仿照 MRP 中价值函数的定义，加入策略 $$ 的因素，定义状态-价值函数 (state-value function) 为： $$ 换句话说，当我们在对 $$ 采样时，需要依照策略 $$ 来采样。

假若在策略 $$ 下，已知第一步做出了动作 $$，那么在此条件下，定义动作-价值函数 (action-value function) 为： $$ 二者的不同之处在于当前时刻做出的动作 $$ 是按照策略 $$ 采样的还是给定的。

根据条件概率定义和全概率公式，容易知道二者有关系： $$

3.4 贝尔曼期望方程

仿照 MRP 中关于贝尔曼方程的推导，在 MDP 中进行类似推导： $$ 对 $$ 也可以进行类似的推导： $$ 紫色的四个式子分别建立起了 $$ 与 $$、$$ 与 $$、$$ 与 $$、$$ 与 $$ 的关系，对应下面的四张图：

这些方程称作贝尔曼期望方程 (Bellman Expectation Equation).

3.5 最优价值函数

我们做强化学习的最终目的是找到最佳的策略，因此定义最优状态-价值函数和最优动作-价值函数为：

$$ 定理：对于任何 MDP，存在最优策略 $$（不一定唯一），并且 $$，$$.

反之，沿着最大化 $$ 的方向做决策，我们就能得到最优策略，即： $$ 这意味着：对任何 MDP，我们的最优策略都是确定性的（而不是随机的）；只要我们求得 $$，那么就能立刻知道最优策略是什么。

3.6 贝尔曼最优方程

由于最优策略也是策略的一种，所以四个贝尔曼方程自然在最优情况下也成立，略作化简可得： $$ 称它们为贝尔曼最优方程 (Bellman Optimality Equation).

与贝尔曼方程和贝尔曼期望方程不同，由于 $$ 操作的存在，贝尔曼最优方程是非线性的，一般没有闭式解，但存在许多迭代解法，例如：

• 价值迭代 (value iteration)
• 策略迭代 (policy iteration)
• Q-learning
• Sarsa

这些算法我们将在后续课程中学到。

4 MDPs 扩展（了解）

我们之前考虑的 MDPs 都是有限的、离散的、完全可观测的，如果没有这些限制，我们可以对 MDPs 进行扩展。

4.1 无限 MDPs

无限也分好几种：

• 可数无限的状态/动作空间：这种扩展是比较直接的
• 连续的状态/动作空间：Closed form for linear quadratic model
• 时间上连续：需要偏微分方程，Hamilton-Jacobi-Bellman equation 是贝尔曼方程在 $$ 的极限情形

4.2 部分可观测 MDPs

POMDP 是一个具有隐状态的 MDP，是具有动作的隐马尔可夫模型。

定义：POMDP 是一个元组 $$，其中 $$ 的定义不变，新增加了：

• $$：观测 (observations) 的有限集合
• $$：观测函数 (observation function)，$$

回顾：历史 (history) 是动作、观察和奖励的序列： $$ 定义置信状态 (belief state) $$ 是在给定历史的条件下，状态的概率分布： $$ 类似于 MDP 中我们画的两种树，POMDP 也可以规约成两种树：

4.3 各态历经马尔可夫过程

各态历经马尔可夫过程 (Ergodic Markov Process) 具有以下特点：

• 常返 (recurrent)：每一个状态会被无限次访问
• 非周期 (aperiodic)：每一个状态被访问的时间不具有周期性

定理：一个各态历经 MDP 具有极限的平稳分布 $$，满足： $$ 对于任意策略 $$，一个各态历经 MDP 有一个与起始状态无关的每时刻平均奖励 $$： $$ 利用 $$ 的定义，我们可以给出 undiscounted, ergodic MDP 的描述。设 $$ 表示由于从状态 $$ 起始而带来的额外奖励，则 $$ 我们可以相应地推导平均奖励贝尔曼方程 (average reward Bellman equation).