数学Prep

Markov Chains

• Markov property（马尔可夫性）：$\text{Pr}(S_{t+1}\mid S_t) = \text{Pr}(S_{t+1}\mid S_1,\cdots,S_{t})$

  下一状态只取决于当前状态，与过去状态无关；当前状态已经包含了历史所有相关信息；当前状态可看作历史的充分统计量

• Time-homogeneity（时齐性）： $\text{Pr}(S_{t+1}\mid S_t=s) = \text{Pr}(S_{t}\mid S_{t-1}=s)$

  从当前状态到下一状态的概率只依赖于当前状态，与时间无关

MDP定义

$\{S_t, A_t, R_t\}_t$序列定义了一个马尔可夫决策过程（MDP），当且仅当满足

• $\text{Pr}(S_{t+1},R_t\mid A_t,S_t) = \text{Pr}(S_{t+1},R_t\mid A_t,S_t,R_{t-1},A_{t-1},S_{t-1},\cdots)$（马尔可夫性）
• $\text{Pr}(S_{t+1}, R_t \mid A_t=a, S_t=s) = \text{Pr}(S_{t}, R_{t-1} \mid A_{t-1}=a, S_{t-1}=s)$（时齐性）

Time-Varying MDPs

在实际场景中往往时齐性的假设会被违反，下面举一些简单的例子来辅助理解：

• 网约车：早高峰路况 ≠ 晚高峰路况，周一模式 ≠ 周末模式。同样的”司机在 A 地、订单在 B 地”这个 $(s, a)$ 对，在工作日早上点的完成率和平日晚上 10 点完全不同。
• 金融市场：同样的仓位策略，在牛市和熊市的转移规律完全不同。

还有课件里的 Intern Health Study：

• 干预衰减（Treatment Effect Decay）：第 1 周发运动提醒短信，实习生很受激励；第 10 周已经麻木；第 20 周甚至可能反感。

  一样的 $(S_t=\text{低落}, A_t=\text{发短信})$，$R_t$ 的分布在第 1 周和第 20 周完全不同。

• 学习效应：患者随着病程推进，自我管理能力在变化。

再拿推荐系统举例：

• 用户连续看了 10 个视频后，对第 11 个同类视频的点击率会下降。

  这不是因为状态 $S_t$ 没记录到”用户疲劳程度”——即使你记录了，“疲劳对点击行为的影响模式本身”也可能随时间改变。

• 用户群体的兴趣漂移（concept drift）。

因此需要考虑将时间变量纳入状态中

Partially Observable MDPs

同样的，完整观测假设也有可能被违反

the Tiger Problem

两扇门，一扇后有老虎，一扇后安全。你可以选择：

1. 直接开门（高风险高回报/高惩罚）

2. 听一下（获得带噪声的信息，再决策）

在 MDP 版本中，假设你直接知道老虎在哪扇门后（完美观测），那么最优策略 trivial：直接开安全的门。

但在 POMDP 版本中，你不知道老虎在哪。你有一个先验信念（比如 50% 在左，50% 在右）。你可以选择：

• exploitation 动作：直接选一扇门开门

• information-gathering 动作：先”听”一下。听的结果（左/右有声音）是带噪声的——可能听错。

那既然看不到真实状态 $S_t$，Agent 该怎么办？答案是：维护一个对当前状态的概率分布：

• 这个 $b_t$ 就是 Belief State（信念状态）。

信念更新就是贝叶斯推断：

每次获得新观测 $o_{t+1}$ 后，Agent 用贝叶斯规则更新信念：

MDP vs TMDP vs POMDP

真实世界
  ├── 是否完全可观测？
  │   ├── 否 → POMDP（需要信念状态 / 拼接观测）
  │   └── 是 → 进入下一问
  │       └── 是否时齐？
  │           ├── 是 → MDP（标准模型，最优策略平稳）
  │           └── 否 → TMDP（最优策略随时间变化）