一、时序推理与马尔可夫模型

1.1 时序推理的需求

• 语音识别

• 机器人定位

• 医疗监控

1.2 马尔可夫模型 (Markov Models / Markov Chains)

1.2.1 定义与核心概念

• 状态 (State):
变量 在特定时间 的取值，记为 。
note that:
，或者其具体的取值，是一个包括了所有变量的取值的列向量

• 状态值：从状态s开始，未来能够获得的期望累积折扣奖励。它衡量了一个状态的好坏程度

• 马尔可夫性 (Markov Property):
给定当前状态，未来状态的概率分布仅依赖于当前状态，而与过去的状态无关。即“未来与过去在给定现在的情况下条件独立”。当前状态捕获了历史中的所有相关信息。
🌻
也叫做无记忆性

• 转移概率 (Transition Probabilities / Dynamics) :
模型从一个状态转移到另一个状态的概率，描述了状态随时间的演变。
具体来说，两种可能状态的情况下，状态分布的演化可以写成：

• 平稳性假设 (Stationarity Assumption): 转移概率 在所有时间点 都相同。
也就是说，上述紫色的状态矩阵在马尔可夫假设下是稳定不变的

1.2.2 联合分布

• 根据链式法则：

• 利用马尔可夫假设 ()，简化为：

1.2.3 隐含的条件独立性

1.2.4 示例：天气模型

• 状态:

• CPT（联合概率分布律）表示：

• 马尔科夫链的两种等价表示：

• 尝试往前推演？👉套用上面的矩阵！

1.2.5 Mini-Forward 算法

• 递推公式:

1.2.6 平稳分布 (Stationary Distributions)

• 对于许多马尔可夫链，当时间步数足够多时，初始状态分布的影响会逐渐消失。

• 系统最终会达到一个平稳分布 ，该分布不随时间改变，且与初始分布无关。

• 平稳分布的性质:

二、隐马尔可夫模型 (HMMs)

2.1 HMM 的核心思想

• 存在一个底层的、不可观测的马尔可夫状态链 。

• 在每个时间步，系统根据当前真实状态 产生一个可观测的输出（证据或发射）。

2.2 HMM 的定义

• 初始状态分布 : 第一个时刻处于各个隐藏状态的概率。

• 状态转移概率 : 隐藏状态之间转移的概率。

• 发射概率 (Emission Probabilities) : 在某个隐藏状态 下，观测到某个证据 的概率。

2.4 HMM 的联合分布

1. 当前状态 仅依赖于前一状态 。

2. 当前观测 仅依赖于当前状态 。

2.5 HMM 中的推理任务

2.5.1 滤波 (Filtering / Monitoring)

• 任务: 追踪当前时刻 的隐藏状态的概率分布，即信念状态 (Belief State)

• 过程: 从初始信念 开始，随着时间的推移和新观测的获得，不断更新信念状态。卡尔曼滤波器 (Kalman Filter) 是一个著名的滤波算法实例。

2.5.2 示例：机器人定位

• 隐藏状态: 机器人在地图中的真实位置。

• 观测: 机器人传感器读到的墙壁信息。

• 模型:
• 运动模型: 描述机器人执行动作后可能到达的位置（有噪声）。
• 传感器模型: 描述在特定位置传感器给出特定读数的概率（有噪声）。

• 通过结合运动模型（时间推移）和传感器模型（观测更新）来估计机器人的位置分布。

2.5.3 推理步骤：在线信念更新

1. 时间推移 (Passage of Time / Prediction):
根据前一时刻的信念和状态转移模型，预测当前时刻的信念。



• 记为

2. 观测更新 (Observation Update / Measurement Update):
结合当前时刻的观测和发射模型，修正预测的信念。



• 记为
• 这一步后需要归一化以确保概率和为1。

三、马尔可夫决策过程 (MDPs)

3.1 MDP 的定义

• 状态集状态集合 : 环境可能处于的所有状态。

• 动作集合 : 智能体在每个状态下可以执行的所有动作。

• 转移函数 或 : 在状态 执行动作 后，转移到状态 的概率。这描述了环境的动态 (dynamics)。

• 奖励函数 : 在状态 执行动作 并转移到状态 后，智能体获得的即时奖励
• 有时也简化为 (离开状态 的奖励) 或 (进入状态 的奖励)。

• 折扣因子 : 用于衡量未来奖励相对于当前奖励的重要性。

3.2 MDP 的马尔可夫性

3.3 策略 (Policies)

• 策略 :
一个从状态到动作的映射 ()，规定了智能体在每个状态 下应该采取的动作

• 最优策略 :
能够使得智能体从任何状态开始，期望的长期累积（折扣）奖励最大化的策略。

3.4 回报与折扣

回报 (Return):

Stationary Preference

折扣 (Discounting):

• 引入折扣因子 是因为：
1. 未来的奖励通常不如即时奖励有价值。
2. 有助于算法在无限期界问题中收敛。
3. 在数学上避免无限的累积奖励。

• 从当前视角来看，一个奖励序列 的折扣效用为:

• 如果奖励有上限 ，则 。

• 这样的话，久远未来的奖励几乎可以忽略不计，解决了无限效用的问题

3.5 最优量与贝尔曼方程

3.5.1 最优状态值函数

• : 从状态 开始，并始终遵循最优策略 行动，所能获得的期望累积折扣奖励。

• 一个理想的假设的函数

3.5.2 最优动作值函数 (Q值函数)

• : 在状态 采取动作 （a不一定是最优策略），然后在此后的所有步骤中都遵循最优策略 行动，所能获得的期望累积折扣奖励。

3.5.3 贝尔曼最优方程 (Bellman Optimality Equations)

1. (状态 的最优值等于在该状态下采取能产生最大Q值的动作所对应的Q值)
也就是保证了动作a也是最优决策

2. (在状态 采取动作 的Q值等于所有可能的下一状态 的（即时奖励 + 折扣后的下一状态最优值）的期望)
其中是状态转移函数，等价于 ，它给出了在状态 s 执行动作 a 后，系统转移到状态 s′ 的概率

四、求解 MDPs (当模型已知时)

4.0 pre：Time-Limited Values

给定一个MDP，定义为从状态s出发，在仅剩k步决策时间的情况下所能获得的最大期望回报。

• 时，，因为没有剩余决策时间

• 时，可以通过以下递归方式计算：

4.1 值迭代 (Value Iteration)

值迭代示例

算例：

for:

so:

类似的方法，我们可以一直迭代到通常而言，这些值最终会收敛，而我们选择的策略也会稳定下来。

上述过程的问题是：

1. 计算复杂，每轮迭代的复杂度是

2. 在收敛之前，我们的策略选择可能已经稳定（例如在，策略已经是最优策略），大量计算被浪费

• 核心思想: 基于贝尔曼最优方程进行迭代更新。算法维护一个当前的值函数估计 ，表示从状态 开始、最多还能进行 步决策时的最优期望回报。

• 初始化: 对所有状态 (如果游戏还剩0步，则期望回报为0)。

• 迭代步骤: 对于每个 ，计算 ：

• 收敛性: 当 或者在有限期界问题中， 会收敛到唯一的 。

• 提取策略: 一旦 收敛，最优策略 可以通过一步前瞻来提取：

4.2 策略迭代 (Policy Iteration)

• 初始化: 从一个任意的初始策略 开始。

• 迭代循环:
1. 策略评估 (Policy Evaluation):
• 目标: 计算当前策略 下（假定为fixed policy）的状态值函数 。
• 满足贝尔曼期望方程：
• 这可以迭代求解 直至收敛(类似值迭代，但动作是固定的)：
或者，对于有限状态，这是一个线性方程组，可以直接求解。
• 策略评估的迭代复杂度为 。
2. 策略改进 (Policy Improvement):
• 目标: 基于刚评估得到的 ，找到一个更好的策略 。
• 对每个状态 ，我们考察如果在这个状态下采取某个动作a，然后再遵循现有的策略，所能获得的回报。将能够把回报最大化的a作为新的策略
• 如果 对所有状态都成立（也就是能够把回报最大化的就是给定的策略），则算法收敛，当前策略即为最优策略 ，其对应的 即为 。否则，令 并返回步骤1。

• 收敛性: 策略迭代保证收敛到最优策略。通常比值迭代需要的迭代次数少，但每次迭代中的策略评估可能计算量较大。

4.3 值迭代 vs. 策略迭代

• 两者都是求解 MDP 的动态规划方法，最终都能找到最优值函数和最优策略。

• 值迭代每轮迭代都更新值函数，并隐式地更新策略（通过 操作）

• 策略迭代显式地维护一个策略，在策略评估阶段固定策略计算其值，然后在策略改进阶段显式更新策略。

• 在实践中，策略迭代有时收敛更快，特别是当策略空间较小时。

五、强化学习 (Reinforced Learning)

5.1 RL 与 MDP 的关系

• MDP 定义了 RL 问题的理论框架 (状态、动作、奖励、转移)。

• RL 提供了在未知或复杂 MDP 环境中，智能体如何通过经验学习来优化其行为（策略）的算法。

• RL 的目标是找到一个策略 来最大化累积奖励。

5.2 RL 的主要方法分类

• 基于模型的 RL (Model-Based RL):
1. 尝试从经验中学习环境的模型 (估计 和 )。
2. 使用学习到的模型进行规划 (例如，使用值迭代或策略迭代) 来找到策略，模仿模型已知时的做法

• 无模型的 RL (Model-Free RL):
• 不尝试学习环境的完整模型
• 直接从经验中学习值函数 (状态值或动作值) 或策略。

5.3 基于模型的学习 (Model-Based Learning)

• 基本思想:
1. 智能体与环境交互，收集样本 。
2. 利用这些样本估计转移概率 和奖励函数 。
• 用频率逼近概率：
• 可以是观测到的奖励的平均值。
3. 一旦有了近似模型 ，就可以将其视为一个已知的 MDP，并使用值迭代或策略迭代等方法求解。

• 优点: 可以更有效地利用数据。

• 缺点: 如果模型学习不准确，会导致次优策略；学习模型本身可能很复杂。

5.4 无模型学习 (Model-Free Learning)

5.4.1 Q学习 (Q-Learning)

• 核心思想: 使用贝尔曼最优方程 作为更新目标，但由于 和 未知，所以使用从环境中采样得到的单个转移 来估计这个期望。

• Q表（Q学习最关键的概念）: 维护一个表格，存储每个状态-动作对 的Q值估计 。Q表形如：

ㅤ

• 是TD目标 (TD target)，是根据最新观测到的数据对 的一个估计。

• 是TD误差 (TD error)。

• 是学习率 (learning rate)，控制新信息覆盖旧信息的程度。

• 异策略 (Off-policy): Q学习可以学习最优策略 ，即使它用来收集经验的策略（行为策略）不是最优的（例如，包含探索的策略）。

• 收敛性: 如果所有状态-动作对都被无限次访问，并且学习率 满足一定的条件（例如，随时间适当减小），学习会收敛到最优的 函数。

• 从Q值提取策略: 一旦 收敛或接近最优，最优策略可以通过在每个状态选择具有最大Q值的动作来获得：。
• 也就是在这张表的每一行找最大值，选择对应的行动

ㅤ

5.4.2 探索 vs. 利用 (Exploration vs. Exploitation)

• 利用 (Exploitation): 根据当前已有的知识，选择当前看来最好的动作，以最大化即时或短期回报。

• 探索 (Exploration): 尝试新的、未知的或当前看来并非最优的动作，以期发现可能更好的状态或奖励路径，从而获得关于环境的更多信息，可能在长期获得更高的回报。

1. -贪婪策略 (-greedy):
• 以概率 选择当前Q值最高的动作 (利用)。
• 以概率 从所有可能的动作中随机选择一个 (探索)。
• 通常是一个小的正数 (例如0.1)。为了保证最终收敛到最优策略， 可以随学习的进行而逐渐减小。
• 贪婪策略问题：
• 在学习完成之后，继续探索会浪费资源
• 解决方案：
• 随着时间的增加，减小；学习完成后减小/停止探索
• 探索函数👇

2. 探索函数 (Exploration Functions):
• 修改Q学习的更新规则或动作选择机制，为那些不常被访问或其价值不确定的状态-动作对赋予一个"探索奖励"或"乐观的初始值"。
• 例如，在选择动作时，不仅仅考虑 ，而是考虑一个函数 ，其中 是 被访问的次数。一个简单的探索函数是：
其中 是值估计， 是访问次数， 是一个控制探索程度的常数。这会鼓励智能体尝试那些访问次数较少的动作

5.5 Q学习的局限性与深度强化学习

• 局限性:
• 需要维护一张Q表格，表格的大小为
• 表格表示的诅咒 (Curse of Dimensionality): 当状态空间或动作空间非常大（甚至是连续的）时，用表格来存储所有Q值变得不可行。

• 深度强化学习 (Deep Reinforcement Learning, DRL):
• 结合深度学习与强化学习。
• 使用深度神经网络 (Deep Neural Networks, DNNs) 作为函数逼近器来估计Q值函数 (例如，Deep Q-Networks, DQN) 或策略函数。
• 输入可以是高维原始数据 (如图像像素)，网络输出Q值或动作概率。
• DRL 已经在许多复杂任务中取得了巨大成功，例如玩 Atari 游戏、围棋 (AlphaGo) 等。