MDP同态（Markov Decision Process Homomorphisms）**是强化学习中用于**状态-动作空间抽象（State-Action Abstraction）**和**对称性利用（Symmetry Exploitation）的严格代数框架。

其核心思想是将一个庞大、复杂的底层 MDP 映射到一个较小的、等价的抽象 MDP 上。在此映射下，系统忽略冗余细节并利用对称性，同时在数学上**严格保证最优价值函数和最优策略的无损推导**。

以下是 MDP 同态的严谨数学定义及其理论性质。

## 一、 数学定义

设原（底层）MDP 为 $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$，抽象（简化）MDP 为 $\overline{\mathcal{M}} = \langle \overline{\mathcal{S}}, \overline{\mathcal{A}}, \overline{P}, \overline{R}, \gamma \rangle$。

一个从 $\mathcal{M}$ 到 $\overline{\mathcal{M}}$ 的 **MDP 同态** 是一个满射元组 $h = (f, \{g_s\}_{s \in \mathcal{S}})$，其中：

1. $f: \mathcal{S} \to \overline{\mathcal{S}}$ 是状态空间的满射映射。
    
2. $g_s: \mathcal{A} \to \overline{\mathcal{A}}$ 是在给定底层状态 $s$ 下，动作空间的满射映射。（注意：动作的映射是**依赖于当前状态**的，这是其区别于普通状态聚合的关键）。
    

为了使 $h$ 成为一个合法的 MDP 同态，必须对所有 $s \in \mathcal{S}$、$a \in \mathcal{A}$ 以及所有抽象目标状态 $\overline{s}' \in \overline{\mathcal{S}}$，严格满足以下两个条件：

### 1. 奖励等价性 (Reward Equivalence)

底层 MDP 在状态 $s$ 执行动作 $a$ 获得的即时奖励，必须等于在抽象 MDP 中对应状态 $f(s)$ 执行对应动作 $g_s(a)$ 的奖励：

$$R(s, a) = \overline{R}(f(s), g_s(a))$$

### 2. 转移等价性 (Transition Equivalence / Block Probability)

在底层 MDP 中，从状态 $s$ 执行动作 $a$，转移到所有能映射到目标抽象状态 $\overline{s}'$ 的底层状态集合（即 $f^{-1}(\overline{s}')$ 构成的等价类）的概率之和，必须等于抽象 MDP 中的单步转移概率：

$$\sum_{s' \in f^{-1}(\overline{s}')} P(s' | s, a) = \overline{P}(\overline{s}' | f(s), g_s(a))$$

其中 $f^{-1}(\overline{s}') = \{s' \in \mathcal{S} \mid f(s') = \overline{s}'\}$。

如果存在上述映射，我们称 $\mathcal{M}$ **同态映射**于 $\overline{\mathcal{M}}$，记作 $\mathcal{M} \succ_h \overline{\mathcal{M}}$。

## 二、 核心理论保证

MDP 同态的最重要价值在于它保留了计算最优控制所需的所有关键结构，从而提供了以下严格的理论保证：

### 1. 价值函数等价 (Optimal Value Equivalence)

如果 $\mathcal{M} \succ_h \overline{\mathcal{M}}$，则底层 MDP 与抽象 MDP 的最优动作价值函数 $Q^*$ 和最优状态价值函数 $V^*$ 是精确等价的：

$$Q^*(s, a) = \overline{Q}^*(f(s), g_s(a))$$

$$V^*(s) = \overline{V}^*(f(s))$$

这意味着，无论原空间有多复杂，我们只需在更小的 $\overline{\mathcal{S}} \times \overline{\mathcal{A}}$ 空间中计算 $\overline{Q}^*$，就可以直接查表得到原空间的最优 $Q$ 值。

### 2. 策略提升 (Policy Lifting)

在抽象 MDP $\overline{\mathcal{M}}$ 中求解得到的最优策略 $\overline{\pi}^*$，可以无损地“提升（Lift）”回原 MDP，形成底层空间的最优策略 $\pi^*$：

$$\pi^*(a|s) = \overline{\pi}^*(g_s(a) | f(s))$$

对于确定性策略，若 $\overline{\pi}^*(f(s)) = \overline{a}$，则在原空间中，执行集合 $g_s^{-1}(\overline{a})$ 中的**任意**动作都能保证全局最优性。

## 三、 特例：MDP 自同构与对称性 (Automorphisms & Symmetry)

MDP 同态的一个极其重要的特例是 **MDP 自同构 (MDP Automorphism)**，这在处理多智能体或机器人空间对称性时是核心理论基础。

当抽象 MDP 与底层 MDP 完全相同（即 $\overline{\mathcal{M}} = \mathcal{M}$），且 $f$ 和 $g_s$ 都是双射（Bijections）时，该同态被称为自同构。

- 所有 MDP 的自同构在函数复合运算下构成一个**自同构群 (Automorphism Group)**，记作 $\text{Aut}(\mathcal{M})$。
    
- **物理意义：** 这捕捉了环境中的刚体对称性或置换不变性。例如，在一个包含多个同质机器人手臂的装配任务中，交换机器人 A 和机器人 B 的身份，或者将工作台旋转 90 度，环境的转移和奖励动态本质上是不变的。利用 $\text{Aut}(\mathcal{M})$，可以通过等变神经网络（Equivariant Neural Networks）直接将这种结构先验注入到深度强化学习（DRL）中，大幅压缩探索空间。
    

## 四、 互模拟 (Bisimulation) 与同态的关系

在强化学习文献中，经常与 MDP 同态一起出现的是**互模拟度量（Bisimulation）**。

- **强互模拟 (Strong Bisimulation)** 是一种纯粹的_状态_聚合。它要求只有当两个状态对**所有相同动作**的奖励和转移概率分布相同时，这两个状态才等价。
    
- **MDP 同态是互模拟的泛化**。在 MDP 同态中，动作的等价性由 $g_s(a)$ 定义，它允许底层系统在不同状态下采用_物理上不同但逻辑上等效_的动作（例如：面对北方时执行“向前运动”与面对东方时执行“向右运动”在相对坐标系下是同态映射）。这赋予了 MDP 同态在多任务强化学习 (MTRL) 和层次化强化学习 (HRL) 的 Skill/Option 定义中更强大的表征能力。
    

## 五、 近似同态 (Approximate Homomorphisms)

在连续状态空间中，精确满足转移和奖励的等式通常是不可能的。因此，理论往往扩展为界定抽象误差的**近似 MDP 同态**。通常引入 Wasserstein 距离 $W_1$ 来衡量概率分布的差异：

$$ \sup_{s, a} \left| R(s, a) - \overline{R}(f(s), g_s(a)) \right| \le \epsilon_R $$

$$ \sup_{s, a} W_1\Big( P(\cdot | s, a), \overline{P}(\cdot | f(s), g_s(a)) \Big) \le \epsilon_P $$

在这种近似下，可以证明最优价值函数的误差边界被限制在 $\mathcal{O}\left(\frac{\epsilon_R + \gamma \epsilon_P}{(1-\gamma)^2}\right)$ 范围内，这为基于对比学习 (Contrastive Learning) 和隐空间表征 (Latent Representation) 构建低维动态模型的算法提供了严谨的数学底座。


---


# MDP homomorphism 的详细严谨解释

## 1. 核心直觉

**MDP homomorphism** 可以翻译为 **MDP 同态映射**。其核心作用是：把一个较大的 MDP 映射到一个较小的抽象 MDP，同时尽量保持原 MDP 中与决策有关的结构。

更精确地说，MDP homomorphism 不是任意压缩状态，也不是普通神经网络 embedding，而是一种满足特定结构保持条件的映射：


$$
M \longrightarrow \bar M  
$$


其中 ($M$) 是原始 MDP，($\bar M$) 是抽象 MDP。

它希望把原 MDP 中“等价”的状态—动作对合并起来：
$$
(s,a) \sim (s',a')  
$$

如果两个状态—动作对具有相同的即时奖励，并且在抽象状态空间中具有相同的转移分布，那么它们可以被视为等价。

因此，MDP homomorphism 的核心不是单纯状态聚合，而是：

$$
\boxed{  
\text{状态—动作对的结构保持型抽象}  
}  
$$

Abel 等人也概括说，MDP homomorphism 通过合并可以视为等价的 state-action pairs 来压缩 MDP。([Proceedings of Machine Learning Research](https://proceedings.mlr.press/v108/abel20a/abel20a.pdf "aistats2020_vpsa.pdf"))

---

# 2. 从 MDP 定义开始

设原始 MDP 为：
$$
M=(\mathcal S,\mathcal A,R,P,\gamma)  
$$
其中：
$$
\mathcal S  
$$
是状态空间；
$$
\mathcal A  
$$
是动作空间；
$$
R:\mathcal S\times\mathcal A\to\mathbb R  
$$
是奖励函数；
$$
P(s'\mid s,a)  
$$
是转移概率；
$$
\gamma\in[0,1)  
$$
是折扣因子。

抽象 MDP 记为：
$$
\bar M=(\bar{\mathcal S},\bar{\mathcal A},\bar R,\bar P,\gamma)  
$$
其中 ($\bar{\mathcal S}$) 和 ($\bar{\mathcal A}$) 通常比原始空间小。

MDP homomorphism 的目标是构造一个从 ($M$) 到 ($\bar M$) 的映射：
$$
h:M\to \bar M  
$$
使得原 MDP 中的决策问题可以在抽象 MDP 中求解，再映射回原 MDP。

---

# 3. MDP homomorphism 的形式定义

经典有限 MDP 情形中，MDP homomorphism 通常写作：

$$
h=(f,g_s)  
$$
其中：
$$
f:\mathcal S\to\bar{\mathcal S}  
$$
是状态抽象映射；
$$
g_s:\mathcal A\to\bar{\mathcal A}  
$$
是状态相关的动作抽象映射。

注意这里的动作映射写成 ($g_s$)，而不是单纯 ($g$)，因为动作的抽象意义可以依赖当前状态 ($s$)。Rezaei-Shoshtari 等人总结 Ravindran 与 Barto 的有限 MDP homomorphism 定义时，也将其写成由状态映射 ($f$) 和动作映射 ($g_s$) 构成的满射，并要求奖励不变和转移等变条件成立。[https://proceedings.neurips.cc/paper_files/paper/2022/file/7f44f98e5e70dea605d0c5baca231c58-Paper-Conference.pdf]

状态—动作对的映射为：
$$
h(s,a)=(f(s),g_s(a))  
$$
也就是：
$$
(s,a)\mapsto(\bar s,\bar a)  
$$
其中：
$$
\bar s=f(s)  
$$
$$
\bar a=g_s(a)  
$$
==因此，MDP homomorphism 实际上是在抽象 **state-action pair**，而不只是抽象 state。==

---

# 4. 条件一：奖励保持 reward invariance

如果：
$$
h(s,a)=h(s',a')  
$$
也就是说：
$$
f(s)=f(s')  
$$
$$
g_s(a)=g_{s'}(a')  
$$
那么两个原始状态—动作对应该具有相同的即时奖励：
$$
R(s,a)=R(s',a')  
$$
等价地，可以定义抽象奖励函数：
$$
\bar R(\bar s,\bar a)
=
R(s,a)  
$$
只要：
$$
\bar s=f(s),\qquad \bar a=g_s(a)  
$$
这个定义必须是良定义的。所谓良定义，就是如果多个原始状态—动作对都映射到同一个抽象状态—动作对，它们给出的奖励必须一致：
$$
h(s,a)=h(s',a')  
\Rightarrow  
R(s,a)=R(s',a')  
$$
否则：
$$
\bar R(\bar s,\bar a)  
$$
无法唯一确定。

因此，奖励保持条件可以写成：
$$
\boxed{  
\bar R(f(s),g_s(a))=R(s,a)  
}  
$$
该条件表示：抽象后的状态—动作对不能丢失即时奖励信息。

---

# 5. 条件二：转移保持 transition consistency / equivariance

仅保持即时奖励还不够。强化学习关心长期回报，所以还必须保持转移结构。

原始 MDP 中：

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

表示从 (s) 执行动作 (a) 后到达具体状态 (s') 的概率。

但抽象 MDP 不关心具体 (s')，只关心它属于哪个抽象状态：
$$
\bar s'=f(s')  
$$
因此，抽象转移概率应为：
$$
\bar P(\bar s'\mid \bar s,\bar a)  
$$
如果：
$$
\bar s=f(s),\qquad \bar a=g_s(a)  
$$
那么要求：
$$
\boxed{  
\bar P(\bar s'\mid f(s),g_s(a))
=
\sum_{s'\in f^{-1}(\bar s')}  
P(s'\mid s,a)  
}  
$$
其中：
$$
f^{-1}(\bar s')
=
{x\in\mathcal S:f(x)=\bar s'}  
$$
表示所有被映射到抽象状态 ($\bar s'$) 的原始状态集合。
这个条件的含义是：

> 原始状态—动作对 ($(s,a)$) 转移到某个抽象状态块 ($\bar s'$) 的总概率，必须等于抽象 MDP 中从 ($(f(s),g_s(a))$) 转移到 ($\bar s'$) 的概率。

Rezaei-Shoshtari 等人的定义中也给出同样形式：抽象转移概率等于原始转移概率在对应状态块上的求和。

---

# 6. 为什么转移条件要对状态块求和？

因为抽象 MDP 看不到具体状态，只看到抽象状态。

假设：
$$
f(s_1)=f(s_2)=\bar s_A  
$$
$$
f(s_3)=f(s_4)=\bar s_B  
$$
如果从某个原始 ($(s,a)$) 出发：
$$
P(s_3\mid s,a)=0.2  
$$
$$
P(s_4\mid s,a)=0.5  
$$


那么从抽象角度看，转移到 ($\bar s_B$) 的概率是：
$$
P(s_3\mid s,a)+P(s_4\mid s,a)=0.7  
$$
因此：
$$
\bar P(\bar s_B\mid f(s),g_s(a))=0.7  
$$
抽象 MDP 不区分 ($s_3$) 和 ($s_4$)，只关心是否进入同一个抽象状态块。

这就是转移保持条件中求和的原因。

---

# 7. 等价类与商 MDP

MDP homomorphism 会诱导一个等价关系。

如果：
$$
h(s,a)=h(s',a')  
$$

则称：


$$
(s,a)\sim_h(s',a')  
$$


也就是两个状态—动作对在同态映射下等价。

等价类为：


$$
[(s,a)]_h
=
\{(x,b):h(x,b)=h(s,a)\}  
$$


抽象 MDP ($\bar M$) 可以理解为原始 MDP 对这些等价类取商之后得到的 **quotient MDP**：
$$
\bar M=M / \sim_h  
$$
也就是说，抽象状态—动作对：


$$
(\bar s,\bar a)  
$$
对应原始 MDP 中一整组等价的状态—动作对。

Rezaei-Shoshtari 等人也明确说，抽象 MDP 实际上是基于 homomorphism map 得到的 quotient MDP。

---

# 8. **MDP homomorphism 的本质：保持 Bellman 结构**

MDP homomorphism 之所以重要，是因为它保持 Bellman 递归需要的信息。

原始 Bellman 最优方程为：
$$
Q^*(s,a)
=
R(s,a)  
+  
\gamma  
\sum_{s'}P(s'\mid s,a)  
\max_{a'}Q^*(s',a')  
$$
如果奖励保持：
$$
R(s,a)=\bar R(f(s),g_s(a))  
$$
并且转移到抽象状态块的概率保持：
$$
\bar P(\bar s'\mid f(s),g_s(a))
=
\sum_{s'\in f^{-1}(\bar s')}  
P(s'\mid s,a)  
$$
那么抽象 MDP 中也可以写出对应 Bellman 方程：
$$
\bar Q^*(\bar s,\bar a)
=
\bar R(\bar s,\bar a)  
+  
\gamma  
\sum_{\bar s'}  
\bar P(\bar s'\mid \bar s,\bar a)  
\max_{\bar a'}\bar Q^*(\bar s',\bar a')  
$$
在同态条件成立时，有：
$$
\boxed{  
Q^*(s,a)=\bar Q^* (f(s),g_s(a))  
}  
$$
以及：
$$
\boxed{  
V^*(s)=\bar V^*(f(s))  
}  
$$

这就是 **optimal value equivalence**。Rezaei-Shoshtari 等人总结 MDP homomorphism 的意义时，明确写到它保证原 MDP 与抽象 MDP 之间的最优价值等价，并允许在抽象 MDP 中学习最优策略再提升回原 MDP。

---

# 9. 策略如何从抽象 MDP 提升回原 MDP？

设抽象策略为：
$$
\bar\pi(\bar a\mid \bar s)  
$$
它在抽象状态 ($\bar s$) 下选择抽象动作 ($\bar a$)。

原始 MDP 中状态为 ($s$)，对应抽象状态： 
$$
\bar s=f(s)  
$$
如果原始动作 ($a$) 被映射为：
$$
g_s(a)=\bar a  
$$
那么可以把抽象策略提升为原始策略：
$$
\pi^\uparrow(a\mid s)  
$$
一种常见定义是把抽象动作概率分配给它的原始动作原像：
$$
\pi^\uparrow(a\mid s)
=
\frac{  
\bar\pi(g_s(a)\mid f(s))  
}{  
|g_s^{-1}(g_s(a))|  
}  
$$
其中：
$$
g_s^{-1}(\bar a)
=
\{a\in\mathcal A:g_s(a)=\bar a\}  
$$
也就是所有被映射到同一个抽象动作 ($\bar a$) 的原始动作。

更一般地，只要求：
$$
\sum_{a\in g_s^{-1}(\bar a)}  
\pi^\uparrow(a\mid s)
=
\bar\pi(\bar a\mid f(s))  
$$
这表示：抽象动作 ($\bar a$) 的概率质量，应该等于原始策略在所有对应原始动作上的概率总和。Rezaei-Shoshtari 等人也给出了这种 lifting 条件。

---

# 10. 一个简单例子：左右对称的 CartPole

考虑 CartPole 中的左右对称结构。

如果杆向右倾斜，并且推车向右运动，那么一个合理动作可能是“向右推”。对应地，如果整个场景左右镜像，杆向左倾斜、推车向左运动，那么合理动作应当是“向左推”。

设状态变换为镜像：
$$
L(s)  
$$
动作变换为：
$$
L(\text{left})=\text{right}  
$$
$$
L(\text{right})=\text{left}  
$$
如果环境完全左右对称，则：
$$
R(s,a)=R(L(s),L(a))  
$$
并且：
$$
P(s'\mid s,a)  
$$
与：
$$
P(L(s')\mid L(s),L(a))  
$$
具有对应关系。

那么：
$$
(s,\text{right})  
$$
和：
$$
(L(s),\text{left})  
$$
就是等价状态—动作对。

van der Pol 等人在 MDP Homomorphic Networks 中也用 CartPole 左右翻转作为例子，说明 ($(s,\leftarrow)$) 与 ($(L[s],\rightarrow)$) 可以在水平翻转下对称，并可通过约束策略满足对应关系来减少解空间。(https://www.fransoliehoek.net/docs/VanDerPol20NeurIPS.pdf)

此时，MDP homomorphism 会把这些对称 pair 合并，使学习系统可以从一个 pair 的经验泛化到另一个 pair。

---

# 11. MDP homomorphism 与 symmetry 的关系

很多 MDP homomorphism 来自环境对称性。

若存在一组变换 ($G$)，对于任意 ($g\in G$)，状态动作变换：
$$
(s,a)\mapsto(g_s(s),g_a(a))  
$$
保持奖励和转移结构：
$$
R(g_s(s),g_a(a))=R(s,a)  
$$
$$
P(g_s(s')\mid g_s(s),g_a(a))=P(s'\mid s,a)  
$$
则这些变换诱导出状态—动作等价类。

于是可以把同一对称轨道上的状态—动作对合并：
$$
(s,a)\sim(g_s(s),g_a(a))  
$$
这就是 symmetry-induced MDP homomorphism。

van der Pol 等人将 MDP homomorphism 用于深度 RL 中的群对称结构，指出 MDP homomorphic networks 通过在等价 state-action pairs 之间 tying weights 来减少自由度，并在实验中提升收敛速度。https://www.fransoliehoek.net/docs/VanDerPol20NeurIPS.pdf

---

# 12. MDP homomorphism 与 state abstraction 的区别

普通 state abstraction 只定义：
$$
f:\mathcal S\to\bar{\mathcal S}  
$$


它只合并状态。

而 MDP homomorphism 定义：
$$
h(s,a)=(f(s),g_s(a))  
$$

它合并的是状态—动作对。

这是关键区别。

在普通 bisimulation 或 state abstraction 中，两个状态是否等价，通常要求它们在所有动作下都有相同奖励和相同转移结构：
$$
R(s_1,a)=R(s_2,a),\quad \forall a  
$$

$$
P(\cdot\mid s_1,a)=P(\cdot\mid s_2,a),\quad \forall a  
$$

这非常严格，因为要求动作一一对应且动作语义完全相同。

但 MDP homomorphism 允许动作也被映射：
$$
a\mapsto g_s(a)  
$$

因此两个状态可以在“重新解释动作”之后等价。

例如：
$$
\text{向左推}  
$$
在左镜像状态中对应：
$$
\text{向右推}  
$$
普通 state abstraction 很难表达这种关系；MDP homomorphism 可以表达。

---

# 13. MDP homomorphism 与 bisimulation 的关系

**Bisimulation** 通常定义在状态之间。两个状态 ($s_i,s_j$) bisimilar，如果对每个动作 ($a$)：


$$
R(s_i,a)=R(s_j,a)  
$$

并且对每个等价类 ($C$)：

$$
P(C\mid s_i,a)=P(C\mid s_j,a)  
$$

这个定义要求两个状态在同一个动作 ($a$) 下行为一致。

Rezaei-Shoshtari 等人总结说，bisimulation metrics 要求动作精确匹配，而 MDP homomorphism 和 lax bisimulation 去掉了这种强限制，因此具有更大的建模灵活性；lax bisimulation 将等价关系扩展到 state-action equivalence。(https://proceedings.neurips.cc/paper_files/paper/2022/file/7f44f98e5e70dea605d0c5baca231c58-Paper-Conference.pdf)

所以区别可以写成：

$$
\text{bisimulation: } s_i\sim s_j  
$$
$$
\text{MDP homomorphism: } (s_i,a_i)\sim(s_j,a_j)  
$$

前者主要比较状态，后者比较状态—动作对。

---

# 14. 为什么动作映射必须依赖状态？

动作在不同状态下可能具有不同语义。

例如在网格世界中，动作集合为：
$$
\mathcal A={\text{up},\text{down},\text{left},\text{right}}  
$$
如果环境有旋转对称性，那么在旋转后的状态中：
$$
\text{up}  
$$
可能对应原环境中的：
$$
\text{right}  
$$
动作的抽象意义依赖当前状态所处的对称变换。因此需要：
$$
g_s(a)  
$$
而不是固定的：
$$
g(a)  
$$
这使得 MDP homomorphism 能表达更丰富的结构。

---

# 15. MDP homomorphism 为什么能提升样本效率？

如果许多状态—动作对被映射到同一个抽象状态—动作对：
$$
h(s_1,a_1)=h(s_2,a_2)=\cdots=h(s_k,a_k)  
$$
那么在抽象 MDP 中，只需要学习一个值：
$$
\bar Q(\bar s,\bar a)  
$$
就可以代表多个原始值：
$$
Q(s_1,a_1),Q(s_2,a_2),\dots,Q(s_k,a_k)  
$$
如果同态条件准确成立，则：
$$
Q^*(s_i,a_i)=\bar Q^*(\bar s,\bar a)  
$$
因此，一个样本可以对整个等价类提供信息。

这就是样本效率提升的来源：
$$
\boxed{  
\text{多个原始状态—动作对共享同一个抽象经验}  
}  
$$
Rezaei-Shoshtari 等人也指出，抽象 critic 训练在简化问题上，每个抽象 state-action pair 代表所有在 homomorphism relation 下等价的原始 state-action pairs，因此可以提高 sample efficiency。

---

# 16. MDP homomorphism 与 value preservation

MDP homomorphism 最重要的性质是 **价值保持**。

对最优价值函数，有：
$$
V^*(s)=\bar V^*(f(s))  
$$
$$
Q^*(s,a)=\bar Q^*(f(s),g_s(a))  
$$
对对应的 lifted policy，也有：
$$
V^{\pi^\uparrow}(s)=\bar V^{\bar\pi}(f(s))  
$$
$$
Q^{\pi^\uparrow}(s,a)=\bar Q^{\bar\pi}(f(s),g_s(a))  
$$
直观解释是：

> 如果抽象 MDP 保留了奖励和转移结构，那么在抽象 MDP 中计算出的长期回报，应当等于原 MDP 中对应状态—动作对的长期回报。

Rezaei-Shoshtari 等人给出有限情形下的 value equivalence 定理：若 (\bar M) 是有限 MDP (M) 的 homomorphic image，则对应策略的值函数在原 MDP 和抽象 MDP 中等价。

---

# 17. Approximate MDP homomorphism

严格 MDP homomorphism 要求：
$$
\bar R(f(s),g_s(a))=R(s,a)  
$$
$$
\bar P(\bar s'\mid f(s),g_s(a))
=
\sum_{s'\in f^{-1}(\bar s')}P(s'\mid s,a)  
$$
完全成立。

但现实中很难完全满足，尤其在连续状态、连续动作、函数近似和采样噪声存在时。因此引入 approximate MDP homomorphism。

近似条件可以写成：
$$
|R(s,a)-\bar R(f(s),g_s(a))|\le \varepsilon_R  
$$
$$
D\left(  
P_f(\cdot\mid s,a),  
\bar P(\cdot\mid f(s),g_s(a))  
\right)  
\le \varepsilon_P  
$$
其中 ($P_f$) 表示原始转移经过 ($f$) 推到抽象状态空间后的分布：
$$
P_f(\bar s'\mid s,a)
=
\sum_{s'\in f^{-1}(\bar s')}P(s'\mid s,a)  
$$
($D$) 可以是 total variation、Wasserstein/Kantorovich 距离等。

近似 homomorphism 意味着价值不再完全相等，但可以得到误差界：
$$
|Q^*(s,a)-\bar Q^*(f(s),g_s(a))|  
\le  
\text{function of }(\varepsilon_R,\varepsilon_P,\gamma)  
$$
Rezaei-Shoshtari 等人也指出，由于 MDP homomorphism 对奖励或转移变化敏感，approximate MDP homomorphism 允许奖励与转移保持条件近似成立。

---

# 18. 连续 MDP homomorphism

经典 MDP homomorphism 首先定义在有限 MDP 上。但连续控制中：
$$
\mathcal S\subseteq\mathbb R^n  
$$
$$
\mathcal A\subseteq\mathbb R^m  
$$
状态和动作都是连续的。

此时不能简单使用有限集合求和，而需要用测度论语言定义：
$$
P(B\mid s,a)  
$$
其中 ($B$) 是可测状态集合。

状态映射：
$$
f:\mathcal S\to\bar{\mathcal S}  
$$

动作映射：
$$
g_s:\mathcal A\to\bar{\mathcal A}  
$$
需要满足可测性、可微性等条件。

抽象转移条件从有限求和变成 pushforward measure 条件：
$$
\bar P(\bar B\mid f(s),g_s(a))
=
P(f^{-1}(\bar B)\mid s,a)  
$$
其中 ($\bar B\subseteq\bar{\mathcal S}$) 是抽象状态空间中的可测集合。

Rezaei-Shoshtari 等人在 NeurIPS 2022 工作中扩展了连续状态和动作空间上的 MDP homomorphism，并指出连续情形需要谨慎处理可测性和可微性问题。

---

# 19. 与 SALE / TD7 中 state-action representation 的关系

SALE 学习的是状态—动作嵌入：


$$
z_s=f(s)  
$$

$$
z_{sa}=g(z_s,a)  
$$


这和 MDP homomorphism 有相似之处：二者都关注 state-action structure。

但二者目标不同。

MDP homomorphism 的目标是：
$$
\boxed{  
\text{构造保持奖励与转移结构的抽象 MDP}  
}  
$$
SALE 的目标是：
$$
\boxed{  
\text{学习对 actor-critic 有用的状态—动作特征}  
}  
$$
因此，MDP homomorphism 更偏理论抽象：
$$
(s,a)\mapsto(\bar s,\bar a)  
$$

要求奖励和转移结构保持。

SALE 更偏深度表征学习：
$$
(s,a)\mapsto z_{sa}  
$$
目标是通过 latent dynamics 和辅助损失改善 value learning / policy learning。

原文中说已有 state-action representation 方法如 MDP homomorphism 更强调 abstraction，而 SALE 更强调 feature learning，含义正是如此。

---

# 20. MDP homomorphism 的严格判断标准

两个状态—动作对：
$$
(s_1,a_1)  
$$
$$
(s_2,a_2)  
$$
可以合并，当且仅当它们满足：

## 20.1 即时奖励相同
$$
R(s_1,a_1)=R(s_2,a_2)  
$$
## 20.2 对抽象状态块的转移概率相同

对任意抽象状态 ($\bar s'$)：
$$
\sum_{x\in f^{-1}(\bar s')}  
P(x\mid s_1,a_1)
=
\sum_{x\in f^{-1}(\bar s')}  
P(x\mid s_2,a_2)  
$$
也就是说，它们不必转移到完全相同的具体状态，但必须以相同概率转移到相同抽象状态块。

这点非常重要。

MDP homomorphism 不要求：
$$
P(x\mid s_1,a_1)=P(x\mid s_2,a_2)  
\quad \forall x  
$$
只要求：
$$
P(f(x)=\bar s'\mid s_1,a_1)
=
P(f(x)=\bar s'\mid s_2,a_2)  
\quad \forall \bar s'  
$$

因此，它允许在抽象状态块内部有不同细节，只要这些细节对抽象决策无关。

---

# 21. 为什么 MDP homomorphism 是“同态”？

在代数中，同态表示保持结构的映射。例如群同态保持乘法结构：
$$
\phi(xy)=\phi(x)\phi(y)  
$$
MDP homomorphism 保持的是 MDP 的决策结构：

$$
\text{reward structure}  
$$
$$
\text{transition structure}  
$$
$$
\text{Bellman structure}  
$$
因此，它不是任意映射，而是满足：
$$
\text{原始奖励}
=
\text{抽象奖励}  
$$
$$
\text{原始转移经过抽象映射后的分布}
=
\text{抽象转移分布}  
$$
从而保证：
$$
\text{原始 Bellman 方程}  
$$
和：
$$
\text{抽象 Bellman 方程}  
$$
相容。

这就是 “homomorphism” 这个术语的来源。

---

# 22. 最小抽象与冗余消除

如果 MDP 中存在大量冗余结构，例如对称状态、重复子任务、局部结构相同的区域，则 MDP homomorphism 可以把它们压缩。
理想情况下，抽象 MDP 是原始 MDP 的最小等价表示：
$$
\bar M = M / \sim_h  
$$
其中所有不可区分的状态—动作对都被合并。
van der Pol 等人说明，MDP homomorphism 可以去除原 MDP 描述中的冗余，即等价状态—动作对，从而得到更小的状态—动作空间，并更容易构建策略。

---

# 23. 一个具体离散例子

设原始 MDP 有四个状态：
$$
\mathcal S={s_1,s_2,s_3,s_4}  
$$
两个动作：
$$
\mathcal A={a,b}  
$$
希望把状态合并为：
$$
f(s_1)=f(s_2)=\bar s_A  
$$
$$
f(s_3)=f(s_4)=\bar s_B  
$$
假设：
$$
R(s_1,a)=R(s_2,b)=1  
$$
并且：
$$
P(s_3\mid s_1,a)=0.4,\quad P(s_4\mid s_1,a)=0.6  
$$
$$
P(s_3\mid s_2,b)=0.2,\quad P(s_4\mid s_2,b)=0.8  
$$
虽然具体 next-state 分布不同，但对抽象状态块 ($\bar s_B$) 的总概率都是：
$$
P(f(s')=\bar s_B\mid s_1,a)=1  
$$
$$
P(f(s')=\bar s_B\mid s_2,b)=1  
$$
如果对其他抽象状态块的概率也一致，并且奖励一致，那么：
$$
(s_1,a)\sim(s_2,b)  
$$
它们可以映射到同一个抽象状态—动作对：
$$
h(s_1,a)=h(s_2,b)=(\bar s_A,\bar a)  
$$
注意：这里 ($a$) 和 ($b$) 是不同原始动作，但可以在不同状态下映射到同一个抽象动作 ($\bar a$)。这正体现了 MDP homomorphism 相比普通 state abstraction 的优势。

---

# 24. MDP homomorphism 的局限

MDP homomorphism 也有重要限制。

第一，严格条件很强。真实任务中很少存在完全相同的奖励与转移结构。

第二，学习 homomorphism 本身很难。需要判断哪些状态—动作对在长期决策上等价，这通常需要大量数据。

第三，在连续控制中，精确等价几乎不存在，只能学习近似 homomorphism。

第四，如果抽象过粗，会丢失关键信息，导致价值误差或策略退化。

第五，如果环境没有明显对称性或重复结构，则 homomorphism 带来的压缩收益有限。Rezaei-Shoshtari 等人也指出，复杂度降低程度依赖环境中的近似对称性。

---

# 25. 总结
MDP homomorphism 可以严格概括为：
$$
\boxed{  
h(s,a)=(f(s),g_s(a))  
}  
$$
其中 ($f$) 抽象状态，($g_s$) 抽象动作，并满足：
$$
\boxed{  
\bar R(f(s),g_s(a))=R(s,a)  
}  
$$
$$
\boxed{  
\bar P(\bar s'\mid f(s),g_s(a))
=
\sum_{x\in f^{-1}(\bar s')}  
P(x\mid s,a)  
}  
$$

这两个条件保证抽象 MDP 保持原 MDP 的奖励结构和转移结构，从而得到：
$$
\boxed{  
Q^*(s,a)=\bar Q^*(f(s),g_s(a))  
}  
$$
$$
\boxed{  
V^*(s)=\bar V^*(f(s))  
}  
$$
因此，MDP homomorphism 的本质是：
$$
\boxed{  
\text{一种保持 Bellman 决策结构的状态—动作抽象}  
}  
$$
它与普通 state abstraction 的区别在于：它不仅合并状态，还允许在不同状态下重新解释动作，从而合并等价的状态—动作对。它与 SALE 这类 deep representation learning 的关系在于：二者都关注 state-action structure，但 MDP homomorphism 更强调严格抽象与价值保持，SALE 更强调通过状态—动作特征提升 actor-critic 学习性能。