马尔科夫相关概念、公式与用法

马尔科夫相关概念、公式与用法

从马尔科夫性质、马尔科夫链和连续时间过程，到 HMM、MDP、POMDP、MCMC、马尔科夫随机场与排队模型
公式采用 Typora 兼容的 Markdown + LaTeX 写法，可直接渲染。

1. 一条主线：什么叫“马尔科夫”

“马尔科夫”不是某一个单独模型的名称，而是一类条件独立结构的名称。其核心思想是：

在当前状态已经给定的条件下，更久远的历史不再为未来提供额外信息。

设系统在时刻 \(t\) 的状态为 \(X_t\)。一阶马尔科夫性质写作：

\[P(X_{t+1}\mid X_t,X_{t-1},\ldots,X_0) = P(X_{t+1}\mid X_t) \]

它并不是说系统真的“没有历史”，而是说：

你所定义的当前状态 \(X_t\) 已经把预测未来所需的历史信息压缩进去了。

1.1 一个直观例子

假设只记录天气状态：

\[X_t\in\{\text{晴},\text{阴},\text{雨}\} \]

如果明天天气只依赖今天天气，则：

\[P(X_{t+1}=\text{雨}\mid X_t=\text{阴},X_{t-1}=\text{晴}) = P(X_{t+1}=\text{雨}\mid X_t=\text{阴}) \]

但现实天气可能还依赖：

• 气压；
• 湿度；
• 风速；
• 季节；
• 最近几天的气象系统。

这时，“晴、阴、雨”可能不是一个足够完整的状态。我们可以扩大状态：

\[S_t=(\text{天气},\text{气压},\text{湿度},\text{季节}) \]

只要 \(S_t\) 足以总结历史，系统仍然可以被建模成马尔科夫过程。

1.2 马尔科夫化

若原过程满足：

\[X_{t+1}=f(X_t,X_{t-1})+\varepsilon_t \]

那么仅用 \(X_t\) 不能预测未来，因为还需要 \(X_{t-1}\)。

定义新状态：

\[S_t=(X_t,X_{t-1}) \]

则下一状态为：

\[S_{t+1}=(X_{t+1},X_t) \]

此时：

\[P(S_{t+1}\mid S_t,S_{t-1},\ldots) = P(S_{t+1}\mid S_t) \]

这叫作通过扩展状态进行马尔科夫化。

1.3 马尔科夫模型的概念谱系

flowchart TDA[马尔科夫性质] --> B[马尔科夫过程]B --> C[离散时间马尔科夫链 DTMC]B --> D[连续时间马尔科夫链 CTMC]B --> E[连续状态马尔科夫过程]B --> F[半马尔科夫过程]C --> G[吸收链 / 随机游走 / 可逆链]C --> H[隐马尔科夫模型 HMM]F --> I[隐半马尔科夫模型 HSMM]C --> J[马尔科夫奖励过程 MRP]J --> K[马尔科夫决策过程 MDP]K --> L[POMDP]K --> M[CMDP]K --> N[SMDP]K --> O[多智能体 MDP / 马尔科夫博弈]A --> P[马尔科夫随机场 MRF]P --> Q[条件随机场 CRF]C --> R[马尔科夫链蒙特卡洛 MCMC]

需要注意：这张图表达的是概念关联，不是严格的集合包含关系。例如，MRF 使用的是无向图上的局部马尔科夫性质，而不是时间序列上的状态转移。

---

2. 随机过程与马尔科夫过程

2.1 随机过程

随机过程是一族按时间索引的随机变量：

\[\{X_t:t\in T\} \]

其中：

• \(T\) 是时间集合；
• \(X_t\) 是时刻 \(t\) 的随机状态；
• 状态空间记作 \(\mathcal{S}\)。

可按时间和状态是否连续分类：

时间	状态	常见模型
离散	离散	离散时间马尔科夫链
连续	离散	连续时间马尔科夫链
离散	连续	状态空间模型、离散时间扩散模型
连续	连续	布朗运动、扩散过程

2.2 马尔科夫过程

如果对任意时刻 \(t_0<t_1<\cdots<t_n<t\)，都有：

\[P(X_t\in A\mid X_{t_n},X_{t_{n-1}},\ldots,X_{t_0}) = P(X_t\in A\mid X_{t_n}) \]

则称 \(\{X_t\}\) 为马尔科夫过程。

这里 \(A\) 是状态空间中的一个事件集合。

2.3 转移核

在一般状态空间中，不能总用有限矩阵表示转移概率，需要使用转移核：

\[K(x,A)=P(X_{t+1}\in A\mid X_t=x) \]

它表示：当前状态为 \(x\) 时，下一时刻落入集合 \(A\) 的概率。

如果状态空间有限：

\[\mathcal{S}=\{1,2,\ldots,n\} \]

转移核就退化成转移矩阵：

\[P_{ij}=P(X_{t+1}=j\mid X_t=i) \]

---

3. 离散时间马尔科夫链 DTMC

离散时间马尔科夫链通常写作：

\[X_0,X_1,X_2,\ldots \]

它满足：

\[P(X_{t+1}=j\mid X_t=i,X_{t-1},\ldots,X_0) = P(X_{t+1}=j\mid X_t=i) \]

若转移概率不随时间变化，则称为时间齐次马尔科夫链：

\[P(X_{t+1}=j\mid X_t=i)=p_{ij} \]

3.1 转移矩阵

设状态数为 \(n\)，转移矩阵为：

\[P= \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1n}\\ p_{21} & p_{22} & \cdots & p_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ p_{n1} & p_{n2} & \cdots & p_{nn} \end{bmatrix} \]

每一行必须满足：

\[p_{ij}\ge 0, \qquad \sum_{j=1}^{n}p_{ij}=1 \]

3.2 天气例子

状态顺序取：

\[(\text{晴},\text{阴},\text{雨}) \]

转移矩阵为：

\[P= \begin{bmatrix} 0.7 & 0.2 & 0.1\\ 0.3 & 0.4 & 0.3\\ 0.2 & 0.3 & 0.5 \end{bmatrix} \]

第一行表示：

\[\begin{aligned} P(\text{明天晴}\mid\text{今天晴})&=0.7\\ P(\text{明天阴}\mid\text{今天晴})&=0.2\\ P(\text{明天雨}\mid\text{今天晴})&=0.1 \end{aligned} \]

假设今天一定是晴天，初始分布为：

\[\boldsymbol{\mu}_0= \begin{bmatrix} 1&0&0 \end{bmatrix} \]

明天的分布为：

\[\boldsymbol{\mu}_1 = \boldsymbol{\mu}_0P = \begin{bmatrix} 0.7&0.2&0.1 \end{bmatrix} \]

后天的分布为：

\[\boldsymbol{\mu}_2 = \boldsymbol{\mu}_0P^2 \]

先计算：

\[P^2= \begin{bmatrix} 0.57&0.25&0.18\\ 0.39&0.31&0.30\\ 0.33&0.31&0.36 \end{bmatrix} \]

因此：

\[\boldsymbol{\mu}_2= \begin{bmatrix} 0.57&0.25&0.18 \end{bmatrix} \]

也就是说，今天晴天时，后天下雨的概率是 \(0.18\)。

3.3 Chapman–Kolmogorov 方程

从状态 \(i\) 经过 \(m+n\) 步到状态 \(j\)，可以在中间状态 \(k\) 处分解：

\[p_{ij}^{(m+n)} = \sum_k p_{ik}^{(m)}p_{kj}^{(n)} \]

矩阵形式是：

\[P^{m+n}=P^mP^n \]

直观解释：

“从今天到后天”的所有路径，可以按“明天处于哪个状态”进行分类求和。

3.4 高阶马尔科夫链

二阶马尔科夫链满足：

\[P(X_{t+1}\mid X_t,X_{t-1},\ldots) = P(X_{t+1}\mid X_t,X_{t-1}) \]

例如，查询负载正在“快速上升”还是“快速下降”，仅看当前负载可能无法区分，因此下一时刻可能依赖当前值与上一个值。

可以定义：

\[S_t=(X_t,X_{t-1}) \]

将其转成一阶链，但状态数量可能从 \(n\) 增长到 \(n^2\)。

3.5 非齐次马尔科夫链

若转移矩阵随时间变化：

\[P_t(i,j)=P(X_{t+1}=j\mid X_t=i) \]

则：

\[\boldsymbol{\mu}_{t+1} = \boldsymbol{\mu}_tP_t \]

例如：

• 工作日和周末的用户行为不同；
• 白天和深夜的数据库负载不同；
• 软件升级前后故障率发生变化。

此时不能简单使用同一个 \(P^n\)，而应计算：

\[\boldsymbol{\mu}_n = \boldsymbol{\mu}_0P_0P_1\cdots P_{n-1} \]

---

4. 马尔科夫链的长期行为

4.1 平稳分布

分布 \(\boldsymbol{\pi}\) 若满足：

\[\boldsymbol{\pi}=\boldsymbol{\pi}P \]

并且：

\[\sum_i\pi_i=1, \qquad \pi_i\ge 0 \]

则称 \(\boldsymbol{\pi}\) 为平稳分布。

它表示：如果系统已经按照 \(\boldsymbol{\pi}\) 分布，那么再走一步后分布不变。

对前面的天气模型，解方程：

\[\begin{cases} \boldsymbol{\pi}=\boldsymbol{\pi}P\\ \pi_{\text{晴}}+\pi_{\text{阴}}+\pi_{\text{雨}}=1 \end{cases} \]

得到：

\[\boldsymbol{\pi} \approx \begin{bmatrix} 0.4565&0.2826&0.2609 \end{bmatrix} \]

长期来看，约有：

• \(45.65\%\) 的时间为晴天；
• \(28.26\%\) 的时间为阴天；
• \(26.09\%\) 的时间为雨天。

4.2 平稳不等于收敛

存在平稳分布，并不自动意味着从任意初始状态都收敛到该分布。

例如两状态交替链：

\[P= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \]

它的平稳分布是：

\[\boldsymbol{\pi}= \begin{bmatrix} 1/2&1/2 \end{bmatrix} \]

但若从状态 1 出发，分布会在：

\[[1,0],[0,1],[1,0],[0,1],\ldots \]

之间振荡，不会逐步收敛。

4.3 不可约、周期与遍历性

不可约

若任意状态 \(i\) 都能以正概率在有限步内到达任意状态 \(j\)，则链不可约。

形式上，存在某个 \(n\ge 0\) 使得：

\[(P^n)_{ij}>0 \]

周期

状态 \(i\) 的周期定义为：

\[d(i)=\gcd\{n\ge 1:(P^n)_{ii}>0\} \]

若 \(d(i)=1\)，则状态非周期。

遍历链

在有限状态情况下，若链不可约且非周期，则存在唯一平稳分布，并且：

\[\lim_{n\to\infty}P^n = \begin{bmatrix} \boldsymbol{\pi}\\ \boldsymbol{\pi}\\ \vdots\\ \boldsymbol{\pi} \end{bmatrix} \]

也就是说，长期分布与初始状态无关。

4.4 可逆马尔科夫链

若存在平稳分布 \(\pi\) 满足详细平衡条件：

\[\pi_iP_{ij} = \pi_jP_{ji} \]

则链称为可逆链。

左边可理解为平稳状态下从 \(i\) 流向 \(j\) 的概率流量，右边是反向流量。

详细平衡比 \(\pi=\pi P\) 更强。若详细平衡成立，则平稳性自动成立：

\[\sum_i\pi_iP_{ij} = \sum_i\pi_jP_{ji} = \pi_j\sum_iP_{ji} = \pi_j \]

可逆性在 MCMC、排队网络和统计物理中尤其重要。

---

5. 吸收链、随机游走与首次到达

5.1 吸收态

若某状态 \(i\) 满足：

\[P_{ii}=1 \]

则进入后不能离开，称为吸收态。

例子：

• 查询完成；
• 用户永久流失；
• 系统彻底故障；
• 游戏胜利或失败。

5.2 吸收马尔科夫链的标准形式

把暂态放在前面、吸收态放在后面：

\[P= \begin{bmatrix} Q&R\\ 0&I \end{bmatrix} \]

其中：

• \(Q\)：暂态之间的转移；
• \(R\)：暂态到吸收态的转移；
• \(I\)：吸收态保持不变。

基本矩阵定义为：

\[N=(I-Q)^{-1} \]

\(N_{ij}\) 表示从暂态 \(i\) 出发，在被吸收前访问暂态 \(j\) 的期望次数。

从各暂态出发，到吸收前的期望步数为：

\[\boldsymbol{t}=N\boldsymbol{1} \]

进入各吸收态的概率为：

\[B=NR \]

5.3 查询执行流程例子

设状态为：

1. 等待；
2. 执行；
3. 成功；
4. 失败。

转移矩阵：

\[P= \begin{bmatrix} 0.4&0.5&0&0.1\\ 0&0.3&0.6&0.1\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix} \]

其中：

\[Q= \begin{bmatrix} 0.4&0.5\\ 0&0.3 \end{bmatrix}, \qquad R= \begin{bmatrix} 0&0.1\\ 0.6&0.1 \end{bmatrix} \]

基本矩阵为：

\[N=(I-Q)^{-1} = \begin{bmatrix} 1.6667&1.1905\\ 0&1.4286 \end{bmatrix} \]

从“等待”状态出发，吸收前的期望步数约为：

\[1.6667+1.1905=2.8572 \]

吸收概率：

\[B=NR \approx \begin{bmatrix} 0.7143&0.2857\\ 0.8571&0.1429 \end{bmatrix} \]

因此从“等待”开始，最终成功的概率约为 \(71.43\%\)。

5.4 随机游走

一维简单随机游走：

\[X_{t+1}= \begin{cases} X_t+1,&\text{概率 }p\\ X_t-1,&\text{概率 }1-p \end{cases} \]

因为下一位置只依赖当前位置，所以它是马尔科夫链。

应用包括：

• PageRank 与图上的随机游走；
• 用户网页跳转；
• 金融价格的简化模型；
• MCMC 提议过程；
• 扩散和网络传播。

5.5 首次到达时间

从状态 \(i\) 首次到达状态 \(j\) 的时间：

\[T_j=\inf\{t\ge 0:X_t=j\} \]

期望首次到达时间：

\[m_{ij}=E_i[T_j] \]

通常可以建立递推：

\[m_{ij} = 1+\sum_{k\ne j}P_{ik}m_{kj}, \qquad i\ne j \]

其中“\(1\)”表示先走一步，再从新状态继续计算。

---

6. 连续时间马尔科夫链 CTMC

连续时间马尔科夫链的时间 \(t\) 连续，但状态通常离散：

\[X(t)\in\{0,1,2,\ldots\} \]

它适合描述随时可能发生的事件：

• 请求到达；
• 请求完成；
• 机器故障；
• 节点恢复；
• 用户上线和离线。

6.1 生成矩阵

CTMC 使用生成矩阵 \(Q\)：

\[Q= \begin{bmatrix} q_{11}&q_{12}&\cdots\\ q_{21}&q_{22}&\cdots\\ \vdots&\vdots&\ddots \end{bmatrix} \]

对 \(i\ne j\)：

\[q_{ij}\ge 0 \]

对角元素满足：

\[q_{ii}=-\sum_{j\ne i}q_{ij} \]

因此每行和为零。

\(q_{ij}\) 不是概率，而是瞬时转移率：

\[q_{ij} = \lim_{\Delta t\to 0} \frac{P(X(t+\Delta t)=j\mid X(t)=i)}{\Delta t} \]

6.2 停留时间

处于状态 \(i\) 时，离开该状态的总速率为：

\[\lambda_i=-q_{ii} \]

停留时间服从指数分布：

\[T_i\sim\operatorname{Exp}(\lambda_i) \]

其期望为：

\[E[T_i]=\frac{1}{\lambda_i} \]

离开状态 \(i\) 后跳到 \(j\) 的条件概率为：

\[P(i\to j\mid\text{离开 }i) = \frac{q_{ij}}{\lambda_i} \]

6.3 两状态故障恢复系统

设状态：

• \(0\)：正常；
• \(1\)：故障。

故障率为 \(\lambda\)，恢复率为 \(\mu\)：

\[Q= \begin{bmatrix} -\lambda&\lambda\\ \mu&-\mu \end{bmatrix} \]

平稳分布满足：

\[\boldsymbol{\pi}Q=0, \qquad \pi_0+\pi_1=1 \]

解得：

\[\pi_0=\frac{\mu}{\lambda+\mu}, \qquad \pi_1=\frac{\lambda}{\lambda+\mu} \]

若平均每 \(100\) 小时故障一次，则：

\[\lambda=0.01 \]

若平均修复时间为 \(2\) 小时，则：

\[\mu=0.5 \]

可用率为：

\[\pi_0 = \frac{0.5}{0.51} \approx 0.9804 \]

即约 \(98.04\%\)。

6.4 转移概率矩阵

CTMC 在时间间隔 \(t\) 后的转移矩阵为：

\[P(t)=e^{Qt} \]

并满足 Kolmogorov 方程：

\[\frac{dP(t)}{dt}=P(t)Q \]

或：

\[\frac{dP(t)}{dt}=QP(t) \]

取决于使用行向量还是列向量约定。

6.5 CTMC 的限制

CTMC 隐含状态停留时间是指数分布。指数分布具有无记忆性：

\[P(T>s+t\mid T>s)=P(T>t) \]

如果真实查询执行时间呈现：

• 固定阶段；
• 多峰分布；
• 重尾；
• 明显依赖已经执行了多久；

则普通 CTMC 可能不合适，应考虑半马尔科夫过程、相位型分布或一般排队模型。

---

7. 半马尔科夫过程

半马尔科夫过程保留“下一状态主要由当前状态决定”，但允许在状态中的停留时间服从一般分布。

设：

• \(J_n\)：第 \(n\) 次跳转后所处状态；
• \(T_n\)：第 \(n\) 次跳转发生时间；
• \(S_n=T_{n+1}-T_n\)：在状态 \(J_n\) 中的停留时间。

半马尔科夫核可写为：

\[Q_{ij}(t) = P(J_{n+1}=j,S_n\le t\mid J_n=i) \]

7.1 与 CTMC 的区别

CTMC 中：

\[S_n\mid J_n=i \sim \operatorname{Exp}(\lambda_i) \]

半马尔科夫过程允许：

\[S_n\mid J_n=i,J_{n+1}=j \sim F_{ij}(t) \]

其中 \(F_{ij}\) 可以是：

• Gamma 分布；
• Weibull 分布；
• 对数正态分布；
• 经验分布；
• 重尾分布。

7.2 数据库例子

状态为：

\[\{\text{扫描},\text{连接},\text{聚合},\text{完成}\} \]

下一算子阶段可以近似只依赖当前阶段，但每个阶段持续时间不同：

• 扫描可能持续几十毫秒；
• 哈希连接可能持续几秒；
• 聚合可能受分组基数影响；
• 数据溢写时会出现重尾。

若强行用 CTMC，意味着每个阶段随时以固定危险率结束，通常不符合实际。半马尔科夫过程能够显式建模阶段时长。

---

8. 马尔科夫奖励过程 MRP

马尔科夫奖励过程是在马尔科夫链上加入奖励。

通常写成：

\[\mathcal{M}=(\mathcal{S},P,R,\gamma) \]

其中：

• \(\mathcal{S}\)：状态空间；
• \(P\)：转移概率；
• \(R(s)\)：状态的期望即时奖励；
• \(\gamma\in[0,1)\)：折扣因子。

它没有动作，因此系统不能主动选择，只能评价一条既定随机过程的长期收益。

8.1 回报

从时刻 \(t\) 开始的折扣回报为：

\[G_t = R_{t+1} +\gamma R_{t+2} +\gamma^2R_{t+3} +\cdots \]

即：

\[G_t = \sum_{k=0}^{\infty}\gamma^kR_{t+k+1} \]

\(\gamma\) 的含义：

• \(\gamma=0\)：只关心下一步；
• \(\gamma\) 接近 \(1\)：重视长期；
• \(\gamma<1\) 还能保证无限和通常收敛。

8.2 状态价值函数

\[V(s)=E[G_t\mid S_t=s] \]

根据第一步分解：

\[V(s) = R(s) + \gamma\sum_{s'}P(s,s')V(s') \]

这就是 Bellman 方程。

矩阵形式：

\[\boldsymbol{V} = \boldsymbol{R} + \gamma P\boldsymbol{V} \]

因此：

\[\boldsymbol{V} = (I-\gamma P)^{-1}\boldsymbol{R} \]

8.3 天气奖励例子

沿用天气转移矩阵。设每天的舒适度奖励为：

\[R= \begin{bmatrix} 3\\ 1\\ -2 \end{bmatrix} \]

分别表示晴、阴、雨。取：

\[\gamma=0.9 \]

解：

\[\boldsymbol{V} = (I-0.9P)^{-1}R \]

得到：

\[\boldsymbol{V} \approx \begin{bmatrix} 14.711\\ 10.425\\ 6.296 \end{bmatrix} \]

这并不意味着晴天当天奖励是 \(14.711\)，而是：

从晴天开始，未来所有折扣舒适度奖励的期望总和约为 \(14.711\)。

8.4 MRP 的用途

MRP 适合：

• 评价固定调度策略；
• 评价固定缓存策略；
• 计算系统状态的长期收益；
• 在强化学习中评价某个策略。

事实上，一个 MDP 固定策略后，就会诱导出一个 MRP。

---

9. 马尔科夫决策过程 MDP

MDP 在 MRP 基础上增加动作：

\[\mathcal{M} = (\mathcal{S},\mathcal{A},P,R,\gamma) \]

其中：

\[P(s'\mid s,a) \]

表示在状态 \(s\) 执行动作 \(a\) 后转移到 \(s'\) 的概率。

奖励可以写成：

\[R(s,a) \]

或更完整地写成：

\[R(s,a,s') \]

9.1 交互过程

每个时间步：

1. 观察状态 \(S_t\)；
2. 选择动作 \(A_t\)；
3. 获得奖励 \(R_{t+1}\)；
4. 转移到状态 \(S_{t+1}\)。

即：

\[S_t \xrightarrow{A_t} (R_{t+1},S_{t+1}) \]

9.2 策略

随机策略：

\[\pi(a\mid s) = P(A_t=a\mid S_t=s) \]

确定性策略：

\[a=\pi(s) \]

固定策略后，状态转移矩阵变为：

\[P_\pi(s,s') = \sum_a\pi(a\mid s)P(s'\mid s,a) \]

奖励变为：

\[R_\pi(s) = \sum_a\pi(a\mid s)R(s,a) \]

因此 MDP 在固定策略 \(\pi\) 下变成 MRP。

9.3 策略价值函数

\[V^\pi(s) = E_\pi[G_t\mid S_t=s] \]

Bellman 期望方程：

\[V^\pi(s) = \sum_a\pi(a\mid s) \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V^\pi(s') \right] \]

9.4 动作价值函数

\[Q^\pi(s,a) = E_\pi[G_t\mid S_t=s,A_t=a] \]

满足：

\[Q^\pi(s,a) = \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') + \gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a') \right] \]

9.5 最优价值函数

\[V^*(s)=\max_\pi V^\pi(s) \]

Bellman 最优方程：

\[V^*(s) = \max_a \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V^*(s') \right] \]

动作价值形式：

\[Q^*(s,a) = \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma\max_{a'}Q^*(s',a') \right] \]

最优策略可由：

\[\pi^*(s) = \arg\max_a Q^*(s,a) \]

得到。

9.6 为什么 Bellman 方程成立

未来总回报可以拆成：

\[G_t=R_{t+1}+\gamma G_{t+1} \]

因此：

\[\begin{aligned} V^\pi(s) &=E_\pi[G_t\mid S_t=s]\\ &=E_\pi[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ &=E_\pi[R_{t+1}+\gamma V^\pi(S_{t+1})\mid S_t=s] \end{aligned} \]

它表达的不是神秘公式，而是非常简单的递归思想：

当前价值 = 立即收益 + 折扣后的下一状态价值。

9.7 网格导航例子

机器人位于二维网格中。

状态：

\[s=(x,y) \]

动作：

\[a\in\{\uparrow,\downarrow,\leftarrow,\rightarrow\} \]

奖励：

• 到达终点：\(+100\)；
• 撞墙：\(-10\)；
• 普通移动：\(-1\)。

若向右动作有 \(0.8\) 概率成功，\(0.1\) 概率偏上，\(0.1\) 概率偏下，则：

\[P(s'\mid s,\rightarrow) \]

不是确定的。

假设某位置执行“向右”：

• 以 \(0.8\) 概率到达价值为 \(10\) 的状态；
• 以 \(0.1\) 概率到达价值为 \(5\) 的状态；
• 以 \(0.1\) 概率撞墙并留在价值为 \(6\) 的状态；
• 每次移动即时奖励均为 \(-1\)；
• \(\gamma=0.9\)。

则该动作的价值为：

\[\begin{aligned} Q(s,\rightarrow) &=0.8(-1+0.9\times 10)\\ &\quad+0.1(-1+0.9\times 5)\\ &\quad+0.1(-1+0.9\times 6)\\ &=0.8\times 8+0.1\times 3.5+0.1\times 4.4\\ &=7.19 \end{aligned} \]

对其他动作也这样计算，选择 \(Q\) 最大的动作。

9.8 价值迭代

初始化 \(V_0(s)\)，反复更新：

\[V_{k+1}(s) = \max_a \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V_k(s') \right] \]

直到变化很小：

\[\max_s|V_{k+1}(s)-V_k(s)|<\varepsilon \]

然后提取策略：

\[\pi(s) = \arg\max_a \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V(s') \right] \]

9.9 策略迭代

策略迭代交替进行：

1. 策略评价：求当前策略 \(\pi\) 的 \(V^\pi\)；
2. 策略改进：对每个状态选更优动作。

策略改进：

\[\pi_{\text{new}}(s) = \arg\max_a \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V^\pi(s') \right] \]

若策略不再变化，则达到最优策略。

9.10 MDP 与强化学习

MDP 是问题模型；强化学习是求解未知或部分未知 MDP 的方法。

若 \(P\) 和 \(R\) 已知，可用动态规划。

若转移模型未知，只能通过交互采样，可用：

• Q-learning；
• SARSA；
• DQN；
• Actor–Critic；
• PPO。

Q-learning 更新：

\[Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1} +\gamma\max_{a'}Q(S_{t+1},a') -Q(S_t,A_t) \right] \]

方括号中的量称为时序差分误差：

\[\delta_t = R_{t+1} +\gamma\max_{a'}Q(S_{t+1},a') -Q(S_t,A_t) \]

---

10. 约束、部分可观测与半马尔科夫决策

10.1 约束马尔科夫决策过程 CMDP

普通 MDP 常把所有目标揉进一个奖励：

\[R_t = -\alpha\cdot \text{延迟} -\beta\cdot \text{能耗} \]

但权重 \(\alpha,\beta\) 很难解释，也不保证严格满足 SLO。

CMDP 直接写成：

\[\max_\pi J_R(\pi) \]

约束：

\[J_{C_k}(\pi)\le d_k, \qquad k=1,\ldots,m \]

其中：

\[J_R(\pi) = E_\pi\left[ \sum_{t=0}^{\infty}\gamma^tR_t \right] \]

\[J_{C_k}(\pi) = E_\pi\left[ \sum_{t=0}^{\infty}\gamma^tC_{k,t} \right] \]

数据库节能例子：

\[\min_\pi E_\pi[\text{Energy}] \]

满足：

\[P_\pi(\text{Latency}>L_{\text{SLO}})\le 0.01 \]

以及：

\[E_\pi[\text{Temperature}]\le T_{\max} \]

10.2 拉格朗日方法

可构造：

\[\mathcal{L}(\pi,\lambda) = J_R(\pi) - \lambda\left(J_C(\pi)-d\right) \]

其中：

\[\lambda\ge 0 \]

当约束经常被违反时，提高 \(\lambda\)，让策略更重视约束成本。

需要注意：拉格朗日训练只是在一定条件下求约束问题，实际系统还需要安全边界、回退策略和在线监控。

10.3 部分可观测马尔科夫决策过程 POMDP

普通 MDP 假设真实状态 \(S_t\) 可直接观察。POMDP 中只能观察：

\[O_t \]

模型通常写成：

\[(\mathcal{S},\mathcal{A},P,R,\Omega,O,\gamma) \]

其中观测模型为：

\[O(o\mid s,a) = P(O_{t+1}=o\mid S_{t+1}=s,A_t=a) \]

智能体维护信念状态：

\[b_t(s)=P(S_t=s\mid o_{1:t},a_{1:t-1}) \]

信念更新：

\[b_{t+1}(s') = \eta\, O(o_{t+1}\mid s',a_t) \sum_s P(s'\mid s,a_t)b_t(s) \]

其中 \(\eta\) 是归一化常数。

直观例子

真实瓶颈状态：

\[S_t\in \{ \text{CPU受限}, \text{内存受限}, \text{I/O受限} \} \]

但系统只能观察：

\[O_t= ( \text{IPC}, \text{LLC Miss}, \text{带宽}, \text{I/O等待} ) \]

一次较高的 LLC miss 不一定证明系统就是内存受限，所以应维护概率：

\[b_t= \begin{bmatrix} 0.15&0.75&0.10 \end{bmatrix} \]

表示当前有 \(75\%\) 概率处于内存受限状态。

10.4 半马尔科夫决策过程 SMDP

普通 MDP 把每个动作看成持续一个固定时间步。SMDP 允许动作持续 \(\tau\) 个真实时间单位。

转移可写作：

\[P(s',\tau\mid s,a) \]

累计奖励需要考虑动作持续时间：

\[Q(s,a) = E\left[ R(s,a,\tau) + \gamma^\tau \max_{a'}Q(s',a') \right] \]

数据库例子

动作“把哈希连接迁移到 GPU”可能持续 \(20\) ms，而动作“提高 CPU 频率”可能在 \(1\) ms 内生效。

若把两者都当成一个相同长度的离散步，会歪曲：

• 时间成本；
• 累计能耗；
• 未来奖励的折扣；
• 决策频率。

10.5 平均奖励 MDP

持续运行的服务器不一定适合折扣目标。可优化长期平均奖励：

\[\rho^\pi = \lim_{T\to\infty} \frac{1}{T} E_\pi \left[ \sum_{t=0}^{T-1}R_t \right] \]

例如：

• 每秒平均吞吐；
• 每小时平均能耗；
• 每焦耳查询数；
• 长期 SLO 违约率。

10.6 多智能体 MDP 与马尔科夫博弈

有多个智能体时：

\[P(s'\mid s,a_1,\ldots,a_n) \]

智能体 \(i\) 的奖励：

\[R_i(s,a_1,\ldots,a_n) \]

例子：

• 多租户争抢 CPU；
• CPU 控制器和 GPU 控制器分别调频；
• 多个查询调度器竞争内存带宽。

若各方目标不同，就更像马尔科夫博弈，而不是单智能体 MDP。

---

11. 隐马尔科夫模型 HMM 与 HSMM

11.1 HMM 的结构

HMM 中真实状态不可直接观察：

\[Z_1,Z_2,\ldots,Z_T \]

只能看到观测：

\[X_1,X_2,\ldots,X_T \]

假设：

\[P(Z_t\mid Z_{1:t-1})=P(Z_t\mid Z_{t-1}) \]

以及：

\[P(X_t\mid Z_{1:t},X_{1:t-1}) = P(X_t\mid Z_t) \]

联合分布：

\[P(Z_{1:T},X_{1:T}) = P(Z_1) \prod_{t=2}^{T}P(Z_t\mid Z_{t-1}) \prod_{t=1}^{T}P(X_t\mid Z_t) \]

11.2 HMM 的三个组成部分

1. 初始状态分布：

\[\pi_i=P(Z_1=i) \]

2. 状态转移矩阵：

\[A_{ij}=P(Z_{t+1}=j\mid Z_t=i) \]

3. 发射概率：

\[B_j(x)=P(X_t=x\mid Z_t=j) \]

11.3 服务器瓶颈识别例子

隐藏状态：

\[Z_t\in \{ C,M,I \} \]

分别代表：

• \(C\)：计算受限；
• \(M\)：内存受限；
• \(I\)：I/O 受限。

观测可离散化为：

\[X_t\in \{ \text{高IPC}, \text{高CacheMiss}, \text{高IOWait} \} \]

发射概率可能为：

\[B= \begin{bmatrix} 0.8&0.15&0.05\\ 0.1&0.8&0.1\\ 0.1&0.2&0.7 \end{bmatrix} \]

第一行表示：计算受限状态下，观测到高 IPC 的概率为 \(0.8\)。

即使某一时刻观测到高 Cache Miss，也不能只凭单点判定内存受限；HMM 会结合前后时刻与状态转移规律进行平滑推断。

11.4 前向算法

目标是计算观测序列概率：

\[P(X_{1:T}) \]

定义：

\[\alpha_t(j) = P(X_{1:t},Z_t=j) \]

初始化：

\[\alpha_1(j)=\pi_jB_j(X_1) \]

递推：

\[\alpha_{t+1}(j) = B_j(X_{t+1}) \sum_i\alpha_t(i)A_{ij} \]

最终：

\[P(X_{1:T})=\sum_j\alpha_T(j) \]

直观上，\(\alpha_t(j)\) 汇总了所有“以状态 \(j\) 结束且能生成前 \(t\) 个观测”的路径概率。

11.5 Viterbi 算法

目标是求最可能的隐藏状态序列：

\[Z_{1:T}^* = \arg\max_{Z_{1:T}} P(Z_{1:T}\mid X_{1:T}) \]

定义：

\[\delta_t(j) = \max_{Z_{1:t-1}} P(Z_{1:t-1},Z_t=j,X_{1:t}) \]

递推：

\[\delta_{t+1}(j) = B_j(X_{t+1}) \max_i\left[ \delta_t(i)A_{ij} \right] \]

并记录达到最大值的前驱状态，最后回溯路径。

11.6 Baum–Welch 算法

当 \(A\)、\(B\)、\(\pi\) 未知时，可以用 Baum–Welch 算法估计参数。它是 EM 算法在 HMM 上的特例：

1. E 步：根据当前参数计算隐藏状态的后验概率；
2. M 步：用这些软计数重新估计转移和发射参数；
3. 反复迭代直到似然不再明显提高。

它通常只能保证收敛到局部最优，因此初始化很重要。

11.7 HMM 的隐含持续时间问题

HMM 中，如果某状态自循环概率为 \(a_{ii}\)，状态持续 \(d\) 步的概率为：

\[P(D=d) = a_{ii}^{d-1}(1-a_{ii}) \]

这是几何分布。

它意味着每一步离开状态的概率恒定，与已经持续多久无关。

11.8 隐半马尔科夫模型 HSMM

HSMM 显式建模持续时间：

\[P(D=d\mid Z=i) \]

例如“内存受限阶段”可能典型持续 \(50\) 到 \(200\) ms，而不是几何分布。

HSMM 适用于：

• 查询执行阶段识别；
• 用户行为阶段；
• 语音片段；
• 设备运行模式；
• 持续时间有明确结构的序列。

---

12. 马尔科夫随机场、条件随机场与马尔科夫毯

前面模型主要描述时间序列。马尔科夫随机场描述的是无向图上的局部依赖。

12.1 马尔科夫随机场 MRF

设无向图：

\[G=(V,E) \]

每个节点对应随机变量 \(X_i\)。局部马尔科夫性质为：

\[X_i \perp\!\!\!\perp X_{V\setminus(\{i\}\cup N(i))} \mid X_{N(i)} \]

意思是：

给定节点 \(i\) 的邻居后，\(X_i\) 与其他非邻居节点条件独立。

12.2 团分解

严格为正的 MRF 可写成 Gibbs 形式：

\[P(X=x) = \frac{1}{Z} \prod_{C\in\mathcal{C}} \psi_C(x_C) \]

其中：

• \(\mathcal{C}\)：最大团集合；
• \(\psi_C\)：非负势函数；
• \(Z\)：配分函数。

\[Z = \sum_x \prod_{C\in\mathcal{C}} \psi_C(x_C) \]

势函数不是概率，只有整体除以 \(Z\) 后才归一化。

12.3 图像去噪例子

每个像素有真实标签：

\[Y_i\in\{0,1\} \]

观测到带噪像素 \(X_i\)。定义能量：

\[E(Y) = \sum_i \phi_i(Y_i,X_i) + \beta \sum_{(i,j)\in E} \mathbf{1}[Y_i\ne Y_j] \]

概率：

\[P(Y\mid X) = \frac{1}{Z(X)} \exp(-E(Y)) \]

第一项鼓励标签符合观测；第二项鼓励相邻像素标签一致。

\(\beta\) 越大，图像越平滑，但过大可能抹掉边缘。

12.4 条件随机场 CRF

CRF 直接建模：

\[P(Y\mid X) \]

线性链 CRF 常写成：

\[P(Y\mid X) = \frac{1}{Z(X)} \exp \left( \sum_{t=1}^{T} \sum_k \lambda_k f_k(Y_{t-1},Y_t,X,t) \right) \]

它与 HMM 的区别：

HMM	CRF
建模 \(P(X,Y)\)	建模 \(P(Y\mid X)\)
是生成模型	是判别模型
对观测生成过程有较强独立假设	可使用丰富、重叠的输入特征
适合生成与隐状态推断	适合条件序列标注

12.5 马尔科夫毯

在贝叶斯网络中，节点 \(X\) 的马尔科夫毯包括：

• 父节点；
• 子节点；
• 子节点的其他父节点。

给定马尔科夫毯后：

\[X \perp\!\!\!\perp V\setminus(\{X\}\cup MB(X)) \mid MB(X) \]

直观上，马尔科夫毯是预测 \(X\) 所需的最小局部信息边界。

用途包括：

• 特征选择；
• 局部推断；
• 因果图分析；
• Gibbs 采样。

---

13. 马尔科夫链蒙特卡洛 MCMC

MCMC 不是为了描述某个现实系统的自然状态变化，而是为了人为构造一条马尔科夫链来采样。

目标：从难以直接采样的目标分布 \(\pi(x)\) 中获得样本。

核心方法：

1. 构造转移核 \(P(x'\mid x)\)；
2. 使 \(\pi\) 成为其平稳分布；
3. 运行链；
4. 丢弃初始烧入阶段；
5. 用后续样本估计期望。

若：

\[X^{(1)},X^{(2)},\ldots,X^{(N)}\sim \pi \]

近似成立，则：

\[E_\pi[f(X)] \approx \frac{1}{N} \sum_{n=1}^{N}f(X^{(n)}) \]

13.1 为什么需要 MCMC

贝叶斯后验：

\[P(\theta\mid D) = \frac{P(D\mid\theta)P(\theta)} {P(D)} \]

其中：

\[P(D) = \int P(D\mid\theta)P(\theta)\,d\theta \]

高维积分往往无法解析计算。MCMC 绕过归一化常数，只需知道未归一化密度：

\[\tilde{\pi}(\theta) \propto P(D\mid\theta)P(\theta) \]

13.2 Metropolis–Hastings

当前状态为 \(x\)。

1. 从提议分布采样：

\[x'\sim q(x'\mid x) \]

2. 计算接受率：

\[\alpha(x,x') = \min \left( 1, \frac{\pi(x')q(x\mid x')} {\pi(x)q(x'\mid x)} \right) \]

3. 以概率 \(\alpha\) 接受 \(x'\)，否则留在 \(x\)。

对称提议的简化

若：

\[q(x'\mid x)=q(x\mid x') \]

则：

\[\alpha(x,x') = \min\left(1,\frac{\pi(x')}{\pi(x)}\right) \]

数值例子

目标分布未归一化权重：

\[\tilde{\pi}(0)=1, \quad \tilde{\pi}(1)=2, \quad \tilde{\pi}(2)=1 \]

真实归一化分布为：

\[\pi= \begin{bmatrix} 1/4&1/2&1/4 \end{bmatrix} \]

当前在 \(x=0\)，提议到 \(x'=1\)，对称提议下：

\[\alpha = \min\left(1,\frac{2}{1}\right) =1 \]

一定接受。

若当前在 \(x=1\)，提议到 \(x'=2\)：

\[\alpha = \min\left(1,\frac{1}{2}\right) =0.5 \]

只以一半概率接受。这样链会更多地停留在高概率状态 1。

13.3 详细平衡

MH 通过构造转移核满足：

\[\pi(x)P(x,x') = \pi(x')P(x',x) \]

即详细平衡，因此 \(\pi\) 是平稳分布。

但需要强调：

• 详细平衡是充分条件，不是必要条件；
• 非可逆 MCMC 也可以具有目标平稳分布。

13.4 Gibbs 采样

对多变量：

\[X=(X_1,\ldots,X_d) \]

依次从完整条件分布采样：

\[X_1^{(t+1)} \sim P(X_1\mid X_2^{(t)},\ldots,X_d^{(t)}) \]

\[X_2^{(t+1)} \sim P(X_2\mid X_1^{(t+1)},X_3^{(t)},\ldots) \]

直到更新全部变量。

Gibbs 采样可视为接受率恒为 1 的特殊 MH。

13.5 HMC

Hamiltonian Monte Carlo 为参数 \(\theta\) 引入动量 \(p\)：

\[H(\theta,p) = U(\theta)+K(p) \]

其中：

\[U(\theta)=-\log\pi(\theta) \]

通过近似哈密顿动力学在高概率区域内远距离移动，减少随机游走。

它适合：

• 高维连续参数；
• 可计算梯度的后验分布；
• 参数相关性较强的问题。

13.6 收敛与有效样本

MCMC 样本通常相关，不能把 \(N\) 个样本当作 \(N\) 个独立样本。

自相关：

\[\rho_k = \operatorname{Corr}(X_t,X_{t+k}) \]

有效样本量近似为：

\[N_{\text{eff}} \approx \frac{N} {1+2\sum_{k=1}^{\infty}\rho_k} \]

若样本高度相关，\(N_{\text{eff}}\) 可能远小于 \(N\)。

常见诊断：

• 多链比较；
• \(\hat{R}\)；
• 有效样本量；
• 轨迹图；
• 自相关图；
• 后验预测检查。

“跑了很多步”并不等于“已经收敛”。

---

14. 与排队论和负载建模相关的模型

14.1 生灭过程

生灭过程是一类 CTMC，状态为：

\[0,1,2,\ldots \]

只允许：

\[n\to n+1 \]

和：

\[n\to n-1 \]

对应速率：

\[\lambda_n, \qquad \mu_n \]

平稳概率满足局部平衡：

\[\pi_n\lambda_n = \pi_{n+1}\mu_{n+1} \]

因此：

\[\pi_n = \pi_0 \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}} \]

14.2 M/M/1 队列

假设：

• 到达间隔指数分布，速率 \(\lambda\)；
• 服务时间指数分布，速率 \(\mu\)；
• 一个服务器。

状态 \(N(t)\) 是系统内请求数。

定义：

\[\rho=\frac{\lambda}{\mu} \]

当：

\[\rho<1 \]

系统稳定，平稳分布为：

\[\pi_n=(1-\rho)\rho^n \]

平均系统请求数：

\[L=\frac{\rho}{1-\rho} \]

平均响应时间：

\[W=\frac{1}{\mu-\lambda} \]

平均排队等待时间：

\[W_q=\frac{\lambda}{\mu(\mu-\lambda)} \]

数值例子

若：

\[\lambda=8\ \text{个请求/秒}, \qquad \mu=10\ \text{个请求/秒} \]

则：

\[\rho=0.8 \]

平均响应时间：

\[W=\frac{1}{10-8}=0.5\ \text{秒} \]

尽管平均服务时间只有：

\[\frac{1}{\mu}=0.1\ \text{秒} \]

由于排队，平均响应时间增加到 \(0.5\) 秒。

这说明当利用率接近 \(1\) 时，延迟会非线性急剧上升。

14.3 马尔科夫调制泊松过程 MMPP

普通泊松过程到达率固定：

\[N(t)\sim\operatorname{Poisson}(\lambda t) \]

真实负载往往在高峰、低峰之间切换。

设隐藏 CTMC：

\[Z(t)\in\{1,\ldots,K\} \]

在状态 \(i\) 下，到达率为：

\[\lambda_i \]

例如：

\[\lambda_{\text{低峰}}=10, \qquad \lambda_{\text{高峰}}=100 \]

隐藏状态在低峰与高峰间按马尔科夫链切换。这能产生：

• 突发性；
• 时间相关性；
• 方差大于均值的过度离散。

14.4 马尔科夫到达过程 MAP

MAP 比 MMPP 更一般。它用两个矩阵表示：

• \(D_0\)：不产生到达的隐藏状态转移；
• \(D_1\)：伴随一次到达的状态转移。

总生成矩阵：

\[Q=D_0+D_1 \]

MMPP 是 MAP 的特殊情况，其中到达通常不改变隐藏状态，或具有更受限的结构。

MAP 适合拟合：

• 数据库突发查询；
• 网络包到达；
• 云函数请求；
• 多阶段业务流量。

---

15. 如何选择合适的马尔科夫模型

15.1 快速选择表

问题特征	推荐模型
离散时间、状态可见、无决策	DTMC
事件随时发生、状态离散	CTMC
状态停留时间不是指数分布	半马尔科夫过程
给既定随机过程计算长期收益	MRP
状态可见，需要选择动作	MDP
有能耗、SLO、温度等硬约束	CMDP
真实状态不可直接观察	POMDP
动作持续时间不同	SMDP
隐藏阶段随时间转移	HMM
隐藏阶段持续时间有明确分布	HSMM
无向图上的局部依赖	MRF
条件序列标注	CRF
从复杂后验分布采样	MCMC
到达和完成事件建模	CTMC / 排队模型
突发到达率随隐藏模式切换	MMPP / MAP

15.2 建模时应依次回答的问题

问题 1：状态是什么

状态应当尽可能满足：

\[P(S_{t+1}\mid S_t,\text{历史}) \approx P(S_{t+1}\mid S_t) \]

若不满足，可：

• 加入最近窗口统计；
• 加入趋势；
• 加入队列长度；
• 加入硬件计数器；
• 加入当前执行阶段；
• 使用 RNN 或非马尔科夫模型。

问题 2：状态能否直接观察

• 能观察：MDP、DTMC；
• 只能观察噪声信号：HMM、POMDP；
• 隐藏状态不一定具有真实物理含义：仍可作为统计潜变量。

问题 3：时间是固定步长还是事件驱动

• 每秒、每分钟采样：离散时间；
• 请求到达时决策：事件驱动；
• 动作持续时间不同：SMDP；
• 任意时刻故障：CTMC。

问题 4：是否有控制动作

• 没有：马尔科夫链、HMM；
• 有：MDP、CMDP、POMDP、SMDP。

问题 5：目标是预测、控制还是推断

• 预测状态演化：马尔科夫链；
• 推断隐藏状态：HMM；
• 找最优动作：MDP；
• 后验采样：MCMC；
• 图结构依赖推断：MRF/CRF。

15.3 何时不应强行使用马尔科夫模型

以下情形需谨慎：

1. 未来显著依赖长历史，而状态难以压缩；
2. 状态空间巨大，样本不足；
3. 转移规律快速变化；
4. 观测间隔不规则但模型仍按固定步处理；
5. 只相关但无因果依据，却试图做因果解释；
6. 奖励设计与真实业务目标不一致；
7. 在线探索可能造成危险或严重 SLO 违约。

可替代或组合的方法包括：

• ARIMA；
• 状态空间模型；
• Gaussian Process；
• RNN/LSTM/Transformer；
• 生存分析；
• 排队网络；
• 鲁棒优化；
• 模型预测控制；
• 上下文多臂老虎JI。

---

16. 数据库与异构计算中的完整建模例子

下面以“异构 CPU 上的数据库节能调度”为例，展示不同马尔科夫模型怎样对应不同假设。

16.1 问题描述

系统具有：

• P-core 与 E-core；
• 可调 CPU 频率；
• 多查询并发；
• 延迟 SLO；
• 内存带宽瓶颈；
• 动态到达负载。

目标是：

在满足延迟和吞吐要求的条件下，降低长期能耗。

16.2 用 MDP 建模

状态：

\[S_t= ( q_t, u_t^P, u_t^E, b_t, m_t, f_t ) \]

其中：

• \(q_t\)：队列长度；
• \(u_t^P\)：P-core 利用率；
• \(u_t^E\)：E-core 利用率；
• \(b_t\)：内存带宽；
• \(m_t\)：查询类型或执行阶段；
• \(f_t\)：当前频率。

动作：

\[A_t= ( n_t^P, n_t^E, \operatorname{DOP}_t, f_t^{\text{new}} ) \]

即时奖励：

\[R_t = -\alpha E_t -\beta L_t -\eta\mathbf{1}[L_t>L_{\text{SLO}}] \]

转移：

\[P(S_{t+1}\mid S_t,A_t) \]

表示资源配置会影响：

• 查询完成速度；
• 下一时刻队列；
• 温度；
• 能耗；
• 带宽竞争。

16.3 为什么简单 MDP 可能不够

部分可观测

真实瓶颈状态无法直接观察，只能看到性能计数器，因此更接近 POMDP。

信念状态：

\[b_t(z) = P( Z_t=z \mid \text{IPC、Cache Miss、带宽、延迟历史} ) \]

动作持续时间不同

改变线程亲和性、迁移数据、调整 GPU 执行位置所需时间不同，因此更接近 SMDP。

有硬约束

系统不能接受“平均奖励很好，但偶尔严重超时”，因此更适合 CMDP：

\[\min_\pi E_\pi[\text{Energy}] \]

约束：

\[P_\pi(L_t>L_{\text{SLO}}) \le 0.01 \]

到达具有突发性

可用 MMPP 描述查询到达状态：

\[Z_t^{\text{load}} \in \{ \text{低峰}, \text{普通}, \text{突发} \} \]

16.4 分层模型

一个更实际的架构是：

flowchart TDA[硬件计数器与查询观测] --> B[HMM/HSMM 瓶颈状态识别]C[MMPP/MAP 负载模式估计] --> D[状态构造]B --> DD --> E[CMDP/POMDP 调度器]E --> F[P/E 核数、DOP、亲和性、DVFS]F --> G[数据库执行]G --> AG --> C

不同模型分工：

• HMM/HSMM：识别隐藏瓶颈阶段；
• MMPP/MAP：估计负载模式；
• CMDP：处理能耗目标与 SLO 约束；
• SMDP：处理动作持续时间；
• MCMC：估计性能模型参数的不确定性。

16.5 奖励设计的数值例子

假设某时间窗内：

• 能耗 \(E_t=20\) J；
• P95 延迟 \(L_t=120\) ms；
• SLO 为 \(100\) ms；
• 权重 \(\alpha=0.1\)；
• 权重 \(\beta=0.01\)；
• 违约惩罚 \(\eta=10\)。

则：

\[\begin{aligned} R_t &= -0.1\times 20 -0.01\times 120 -10\times 1\\ &=-2-1.2-10\\ &=-13.2 \end{aligned} \]

若另一配置能耗为 \(28\) J，但延迟为 \(90\) ms：

\[R_t = -0.1\times 28 -0.01\times 90 = -3.7 \]

虽然第二个配置更耗电，但由于避免了 SLO 违约，其奖励更高。

这也暴露了加权奖励的敏感性：\(\eta\) 的选择会显著改变策略，因此严格 SLO 通常更适合 CMDP。

16.6 状态设计的陷阱

若状态只写：

\[S_t=(\text{CPU利用率}) \]

则两个 CPU 利用率都为 \(90\%\) 的场景可能完全不同：

1. 高 IPC、低 miss，属于计算受限；
2. 低 IPC、高 LLC miss，属于内存受限。

相同状态却需要不同动作，说明状态不满足充分性。

应加入：

\[S_t= ( \text{CPU利用率}, \text{IPC}, \text{LLC Miss}, \text{内存带宽} ) \]

或使用隐藏状态模型压缩这些指标。

---

17. 常见误区

17.1 “马尔科夫就是完全没有记忆”

错误。

更准确的说法是：

给定当前状态后，历史不再提供额外预测信息。

如果当前状态包含历史窗口、累计量和阶段信息，系统仍可满足马尔科夫性质。

17.2 “所有时间序列都可以用一阶马尔科夫链”

理论上可以不断扩大状态，但状态空间可能指数膨胀，实际不可用。

17.3 “有平稳分布就一定会收敛”

错误。周期链可能存在平稳分布，却从特定初始状态持续振荡。

17.4 “转移矩阵元素和生成矩阵元素都是概率”

错误。

DTMC 中：

\[P_{ij}\in[0,1] \]

CTMC 中：

\[q_{ij} \]

是速率，可以大于 \(1\)；对角项还是负数。

17.5 “HMM 的隐藏状态一定是真实物理状态”

不一定。隐藏状态可能只是统计聚类出来的模式。要把它解释为“CPU受限”等物理概念，需要额外验证。

17.6 “MDP 一定要用强化学习”

错误。若转移概率和奖励已知，可以用价值迭代、策略迭代或线性规划。

17.7 “奖励越复杂越好”

错误。复杂奖励可能导致：

• 权重难调；
• 目标冲突被掩盖；
• 策略钻奖励漏洞；
• 训练不稳定。

硬约束更适合 CMDP 或安全控制机制。

17.8 “MCMC 样本越多就一定越准”

若链未混合或高度自相关，很多样本仍可能只覆盖后验的一小部分。

17.9 “马尔科夫模型能证明因果关系”

一般不能。转移概率描述条件分布，不自动等于干预因果效应。

\[P(Y\mid X) \]

与：

\[P(Y\mid do(X)) \]

不是一回事。

---

18. 公式速查表

18.1 马尔科夫性质

\[P(X_{t+1}\mid X_t,\ldots,X_0) = P(X_{t+1}\mid X_t) \]

18.2 状态分布演化

\[\boldsymbol{\mu}_{t+1} = \boldsymbol{\mu}_tP \]

\[\boldsymbol{\mu}_{t+n} = \boldsymbol{\mu}_tP^n \]

18.3 平稳分布

\[\boldsymbol{\pi} = \boldsymbol{\pi}P \]

18.4 详细平衡

\[\pi_iP_{ij} = \pi_jP_{ji} \]

18.5 CTMC 生成矩阵

\[q_{ii} = -\sum_{j\ne i}q_{ij} \]

\[P(t)=e^{Qt} \]

18.6 MRP Bellman 方程

\[V(s) = R(s) + \gamma\sum_{s'}P(s,s')V(s') \]

\[\boldsymbol{V} = (I-\gamma P)^{-1}\boldsymbol{R} \]

18.7 MDP Bellman 期望方程

\[V^\pi(s) = \sum_a\pi(a\mid s) \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V^\pi(s') \right] \]

18.8 Bellman 最优方程

\[V^*(s) = \max_a \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s') +\gamma V^*(s') \right] \]

18.9 Q-learning

\[Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1} +\gamma\max_{a'}Q(S_{t+1},a') -Q(S_t,A_t) \right] \]

18.10 HMM 联合分布

\[P(Z_{1:T},X_{1:T}) = P(Z_1) \prod_{t=2}^{T}P(Z_t\mid Z_{t-1}) \prod_{t=1}^{T}P(X_t\mid Z_t) \]

18.11 POMDP 信念更新

\[b_{t+1}(s') = \eta\, O(o_{t+1}\mid s',a_t) \sum_sP(s'\mid s,a_t)b_t(s) \]

18.12 MCMC 估计

\[E_\pi[f(X)] \approx \frac{1}{N} \sum_{n=1}^{N}f(X^{(n)}) \]

18.13 Metropolis–Hastings 接受率

\[\alpha(x,x') = \min \left( 1, \frac{\pi(x')q(x\mid x')} {\pi(x)q(x'\mid x)} \right) \]

18.14 M/M/1 队列

\[\rho=\frac{\lambda}{\mu} \]

\[\pi_n=(1-\rho)\rho^n \]

\[W=\frac{1}{\mu-\lambda} \]

---

结语

“马尔科夫”相关模型看似繁多，但可以用三个问题统一理解：

1. 当前状态是否足以概括历史？
2. 真实状态能否观察，是否允许采取动作？
3. 目标是描述演化、推断隐藏状态、优化决策，还是从复杂分布采样？

最重要的不是先决定“我要使用 MDP、HMM 或 MCMC”，而是先明确：

\[\text{状态} + \text{时间尺度} + \text{观测机制} + \text{动作} + \text{目标} \]

模型名称只是这些假设的组合。状态定义是否合理，通常比选择某个更复杂的算法更重要。