MDPs and Exact Solution Methods

一、马尔科夫决策过程(MDPS)

MDP定义：

：智能体的状态集合。
：智能体可以选择的行动集合。
：转变函数，定义智能体当前状态为，采取动作，进入状态的概率。
：奖励函数，为上述转变分配奖励。
：初始状态。
：折扣因子，对未来奖励的折扣。
：范围，智能体行动的时间。

MDP求解：

在一个MDP中，我们想要找到一个最优的策略(policy)

对于一个给定的状态和时间，策略给出一个行动。
最优策略指能使奖励的期望最大的策略。

如果环境是确定的，那么只需要一个最优的plan，即一系列的行动，从起始点到终点。

二、精确求解方法

目标：最大化随时间累计，折扣后奖励总和的期望值。

（一）、值迭代

最优值方程：

从状态出发并采取最优行动时的折扣奖励总和。

示例点击展开查看

算法：

示例点击展开查看

注意这个机器人朝向，三个箭头说明一次行动中只有三个可能的方向（这也是在笔者和室友后期验算时，发现怎么算怎么不对，最后才定位出的问题）。在agent的一次action中，它会根据最优的action选定一个方向，有0.8的概率按照最优方向行动，有0.1的概率偏向最优方向相对的左侧和右侧。

第0次迭代时，所有的都被赋为0。

第1次迭代时，有奖励的状态被赋值为相应的奖励值（按照公式计算不知道咋算，按照示例来看应该直接赋值就好）。

第2次迭代时，则根据上一次迭代的值进行计算（奖励和惩罚区域始终保持不变）：

以为例（其余相邻都是0，无需计算，惩罚区域无法跳出），我们采取的最佳action肯定是往右：需要注意，由于最佳action是向右，所以noise产生的偏差应该是向上或者向下，分别有0.1的概率，而向上撞墙会保持原地。

关于reward，按照例子来看，每一步的奖励始终为0。

第3次迭代时，需要根据公式更新相邻格：处的最优方向向右，处的最优方向向上。相应更新迭代值即可。

第4次迭代计算过程省略了。只需要记住最优action的方向和可能偏移的方向即可。

第100次迭代时，值迭代已趋近收敛。

收敛速度往往与折扣因子有关，折扣因子越趋近0，收敛速度越快。

理论：

值迭代总是会收敛。在收敛处，我们能获得带折扣因子的无限期问题的最优值函数，它满足贝尔曼(Bellman)方程：（感觉有点小问题，第一个应该是小写，第一个应该是小写？同时，这里的应该也是概率函数？）

为了获取最优的行动，只需要根据下面步骤执行：

执行值迭代过程，直到收敛。
获得，通过反推下一步行动：

无限期策略是稳定的，状态下的最优行动在任何时间都是相同的。

直觉：

随着范围的增大，步之后能获取的奖励和随之缩减，最终趋于0，因此最终趋于。

定义：Max-Norm（最大范数）

解释：这是最大范数（max-norm，也叫∞-norm）的定义。它表示向量中所有状态对应的值的最大绝对值。

定义：γ-压缩映射（γ-Contraction）

一个更新操作是 max-norm 下的 γ-压缩映射，当且仅当：

解释：这是“压缩映射”的定义。它说明更新操作会将任意两个输入的差异（在 max-norm 下）收缩最多 γ 倍。如果，我们称这个操作是“收缩的”。

定理：压缩映射必收敛到唯一不动点

Banach Fixed Point Theorem（巴拿赫不动点定理）

如果一个映射是压缩映射（在完备空间中），则存在唯一不动点，并且从任意初始点迭代最终都收敛于它。

事实：值迭代是一个 γ-压缩映射

令为Bellman更新操作，即：

我们可以证明：

推论：值迭代收敛到唯一固定点

因为值迭代是 γ-压缩映射，根据不动点定理，值函数会收敛到唯一固定点 ( )。

补充事实：误差界估计（用于停止条件）

若满足：

则有：

解释：这个不等式用于衡量我们与最优值函数的距离。

意思是：如果连续两次更新的差距已经很小（小于 ε）了，那么我们离最终解也不会太远。

（二）、策略迭代

不同于值衡量状态的值，值衡量的是一个状态下的行动的价值。

表示从状态出发执行动作，并之后采取最优策略时的期望总回报。

最优 Q 值的贝尔曼方程：含义解释：

外层是对所有可能下一状态的期望；
：从执行动作到达的概率；
：即时奖励；
：折扣因子；
：表示在下一个状态采取最优动作的最大回报。

这是“先拿奖励，再考虑未来的最优行为”的形式。

Q值迭代：这是值迭代的 Q 值形式，含义是：

每一步更新 Q 值时，使用当前的来近似未来的最大期望回报，重复迭代直到收敛为。

示例点击展开查看

策略评估：

回顾上面的值迭代：对于给定策略，策略评估如下：收敛时有如下公式：在此基础上，我们可以建立一个算法，对其进行评估，用评估结果再优化策略，这就是策略迭代的大致思路。

策略迭代：

策略迭代由两大步骤组成，并反复进行直到策略收敛：

1. 策略评估（Policy Evaluation）

给定当前策略，我们要计算它的状态值函数。

不断迭代直到收敛；

2. 策略改进（Policy Improvement）

用当前的值函数来生成一个更好的策略。 有效性证明：

这个“评估-提升”的循环是保证有效的，它最终一定会停止，并且停止时找到的就是最优策略和最优价值函数。

(1) 保证收敛 (Guarantee to converge)
- 每次“策略提升”，新策略要么比老策略好，要么和老策略一样好（在已经达到最优的情况下）。它永远不会变得更差。
- 因为策略总是在变好（或者不变），所以除非已经达到最优，否则你不会重复遇到同一个策略。
(2) 收敛即最优 (Optimal at convergence)
- 算法收敛（停止）的标志是：在“策略提升”那一步，发现新策略和老策略一模一样了，没有任何改进空间了。
- 这意味着对于每个状态，当前策略所选择的动作，本身就已经是那个能最大化“下一步期望价值”的动作了（也就是满足了策略提升的条件）。

最大熵公式

次优解分布:

传统的RL算法（比如我们上面讨论的Policy Iteration）通常致力于找到一个唯一的、最好的策略。但这种做法有其局限性。我们退而求其次，寻找一个次优解的分布，有如下好处：

更鲁棒的策略 (More robust policy)

如果环境发生变化，这个次优解的集合中，可能仍然有适用于新情况的好解法。

问题：如果你只知道那条唯一的“最快路线”，万一这条路上突然发生了交通事故（环境变化），你就懵了，不知道该怎么办。你的策略瞬间失效。
解决方案：如果你有好几条备选的“优秀路线”，当主路线堵车时，你可以立刻从中选择另一条路绕过去。你的整体策略对意外情况的抵抗能力（即鲁棒性）就大大增强了。
在RL中，一个只学习到最优策略的智能体，在环境发生微小变化时（例如，某个关键路径被阻挡），可能会表现得非常糟糕。但如果它掌握了多个次优策略，它就能快速适应，从“备用方案”中拿出一个来执行，表现得更加稳定和可靠。

更鲁棒的学习过程 (More robust learning)

如果我们能保持一个次优解的集合，我们的智能体在学习过程中就能收集到更有价值的探索数据。

这主要关乎“探索与利用 (Exploration-Exploitation) ”的权衡问题。

问题：智能体为了学习，不能只执行它当前认为最好的动作（利用），也需要尝试一些未知的动作来发现可能更好的新策略（探索）。但怎么探索是个大学问。
解决方案：如果智能体心中有好几个“优秀解法”，它的探索就可以是“在这些优秀解法之间进行尝试”。
通过这种方式，智能体收集到的数据都是来自于“高水平尝试”，数据质量非常高。这可以帮助它学得更快、更稳定，并且避免过早地锁定在某个局部最优解上，从而更容易找到全局最优解。

熵：

定义一：熵是随机变量X不确定性的度量 (measure of uncertainty)。

定义二：熵是（平均而言）编码随机变量X所需要的比特数 (number of bits required to encode X)。

数学公式:

：代表整个随机事件”。
：代表一个具体的可能结果。
：代表结果 xi 发生的概率。
：它代表了单个结果发生时所包含的“信息量”。
- 如果一个事件概率很高，p(xi)→1，那么 log2p(xi)→0。这件事发生不意外，信息量为0。
- 如果一个事件概率很低，p(xi)→0，那么 log2p(xi) 是个很大的负数，所以 −log2p(xi) 就是个很大的正数。这件事的发生非常意外，信息量巨大！
∑ip(xi)…：最后，我们把每个可能结果的“信息量”乘以它自己发生的“概率”，然后全部加起来。这其实就是在计算整个事件X的“平均信息量”或“平均意外程度”，也就是熵。

最大熵MDP：

在常规的MDP公式的基础上，引入了熵的参数。新引入的内容会观察策略的熵。

是权衡因子，用于平衡奖励和熵。

约束优化：

在约束优化中，我们会在一些约束条件下求解最值问题。比如在的条件下求的最大值。

为了求解，我们引入拉格朗日函数，并改为求如下值：在最优处时，满足如下条件：

拉格朗日原理概述点击展开查看

拉格朗日原理概述：

问题设定：
- 我们希望最大化或最小化一个目标函数。
- 同时，必须满足一个或多个约束条件。
拉格朗日函数：
- 为了将约束条件引入到优化问题中，我们构造拉格朗日函数：
- 这里，是拉格朗日乘子，用于调整约束的影响。
求解步骤：
- 对拉格朗日函数进行偏微分，得到以下条件：
- 第一个条件指示在优化点上，函数的变化率为零；第二个条件确保约束条件被满足。
几何解释：
- 几何上，优化问题可以看作是在某个函数的等高线（或曲面）上寻找最优点，而约束条件则像是这条等高线与某个边界的交点。拉格朗日乘子帮助我们找到这些交点。

1. 目标函数

最大化期望奖励和策略熵的加权和。熵代表策略的随机性，是权衡因子。

2. 约束条件

策略是一个概率分布，所有动作的概率之和必须为1。

3. 求解方法

这是一个带约束的优化问题，使用拉格朗日乘子法。构造拉格朗日函数。对的变量和 求偏导并令其为0来寻找最优解。

4. 最终解

最优策略的形式是一个 Softmax 分布。奖励越高的动作，被选中的概率就呈指数级越高。其中是归一化项（也叫配分函数），用来确保所有概率之和为1。

紧接上一步，开始计算我们找到的最优策略所对应的最优价值（Optimal Value, V）。

回顾价值公式：

接着，将上一页推导出的最优Softmax策略 代入上方的价值公式中。

化简得到最终结果：

在此基础上，我们希望把我们之前讨论的单步最大熵解法，推广到了更普遍的多步强化学习问题中。

这个算法是一种基于动态规划的递归方法。在还剩步时，处于状态的价值，记为，可以被分解为两部分：

执行一个动作后获得的即时价值
进入下一个状态后，在剩下步中所能获得的价值。

这就得到了最大熵贝尔曼方程： $这部分就是$ 这里的就是最大熵Q值。它代表了在状态执行动作，并在后续所有步骤中都遵循最优策略所能得到的期望总价值。

既然问题结构相同，我们就可以直接套用单步问题的解，只需把替换成即可。