精读笔记

Problem Setting

论文实际解决的是：给定有限 POMDP、折扣无限时域、memoryless stochastic policies，刻画所有可实现 value functions 的集合 V={V^π}。这不是求最优 policy，也不是给 RL 算法，而是问 value space 中哪些点是某个 observation-policy 的 Bellman fixed point。

真正困难点在于 partial observability 打破了 MDP 中最关键的 state-wise decoupling。在 fully observable MDP 中，每个 state 的 action distribution 可以独立调节，value feasibility 最终落到每个 state 上的 convex hull / halfspace 条件，因此几何是 polyhedral。POMDP 中一个 observation-policy 同时影响多个 latent states；β 把 policy 参数线性混合后再进入 transition 和 reward，导致 Bellman residual 的可调方向相互耦合。关键矛盾是：Bellman 方程对固定 policy 是线性的，但当 policy 只能通过 observation 控制 latent-state action distribution 时，可行解集合不再是线性/多面体对象。

以前方法卡在两个方向：MDP value polytope 理论依赖 full observability；POMDP rational parametrization 能说明 value 是 policy 参数的有理函数，但不直接给出 value image 的边界和 exact feasibility 判据。

Motivation

已有路线缺的不是另一个 POMDP solver，而是一个能解释 memoryless POMDP optimization landscape 的几何语言。经验上 POMDP policy optimization 有多个局部最优、对初始分布敏感、policy improvement 不成立；但这些现象如果只从 belief-state complexity 或 nonconvex optimization 角度看，会显得过于粗糙。

作者的核心观察是：Bellman 方程可以看作参数化线性系统，policy 只是在改变系统矩阵和右端项。对于 fixed x，问题等价于是否存在 policy 参数让 Bellman residual 为零。这和 parametric interval linear systems 的 solvability theory 高度匹配。换句话说，作者不是从 dynamic programming 出发，而是把 POMDP value feasibility 重新放进 real algebraic geometry / parametric linear systems 框架。

关键缺口是：MDP 中的 polytope 结果无法解释 POMDP 的曲边界；occupancy measure 的半代数结果没有直接给 value set 的全局结构；而本文要补的是 value-function feasible set 本身的 exact semi-algebraic characterization。

Core Idea

核心想法很干净：把 Bellman equation 写成 A(p)x=b(p)，其中 p 是 observation-conditioned memoryless policy，A(p), b(p) 对 p 仿射线性。于是 feasible value set 是一个 affine-parametric linear system 在 policy simplex 上的 solution set。这个视角把 POMDP 的非线性从 Bellman fixed point 中剥离出来，定位到“参数受耦合约束的线性系统解集”。

理论上它成立的原因是：对固定 policy，折扣因子保证 I-γP^π 可逆；对固定 candidate value x，Bellman residual 对 policy 参数是线性的。因此“是否存在 policy 使 x 可行”本质上是一个线性可行性问题，只是系数依赖 x。进一步，线性可行性随 x 变化的投影天然是 semi-algebraic 的；作者给出的贡献是把这个事实做成 explicit determinantal / zonotope 条件，而不是只引用抽象量词消去。

和 prior 的本质区别在于：MDP geometry 是从 policy simplex 的 product structure 推出 polytope；本文是从 parametric linear system 的 residual zonotope 推出 semi-algebraic set。partial observability 被解释为让原本可分的 hyperplane boundary 合并、弯曲并产生 higher-degree algebraic components。

Method

方法的关键不是某个复杂构造，而是三次重写。

第一，把 observation-policy π 映射到 effective state-policy τ=π∘β。这个步骤把 partial observability 的影响压缩成一个线性 map 的 image polytope。它解决的问题是：policy 变量到底如何进入 latent-state Bellman equation。核心变化是 latent states 的 action distributions 不再独立，而是被 β 的列空间/行结构耦合。

第二，把 Bellman 方程作为 affine-parametric linear system。A(p)=I-γP^π，b(p)=r^π，二者对 policy 参数线性。这个重写让 feasible value 判定变成：是否存在 p 使 residual 为零。它需要处理 policy simplex 不是 box 的问题，因此作者用 anchor action 构造多个 hyperrectangle parametrizations，并在一定 intersection-preservation 条件下取交恢复 simplex image。

第三，用 parametric interval system 的 exact condition 得到无限族 piecewise-linear inequalities，再用 zonotope membership 得到有限描述。对每个 box-parametric system，midpoint residual C(x) 必须落在 deviation columns D_k(x) 生成的 zonotope 中，即存在 q∈[-1,1]^K 使 D(x)q=C(x)。这一步把“对所有 y 的 support inequality”转成有限的代数可行性。

最后，论文还给出一个更直接的 quantifier-free 描述：把 Bellman 方程和 policy simplex 合并为 C(x)P=f(x), P≥0，然后按 rank C(x)=ρ 分层，用 minors 保证一致性，用 Cramer rule 给出 basic feasible policy 的非负性条件。这个版本更显式，也更说明 semi-algebraic 性质不是偶然。

Key Insight / Why It Works

最重要的 insight 是：POMDP value set 的非线性不是因为 Bellman operator 对 value 非线性，而是因为 feasible policy directions 在 latent-state 层面被 observation kernel 线性耦合后，再通过“存在 policy 参数”的投影形成非线性边界。换句话说，partial observability 把一个本来按 state 分解的 convex-combination 条件变成了全局耦合的 linear feasibility condition；消去 policy 变量后自然产生 determinants 和 higher-degree hypersurfaces。

这也是为什么 MDP 是特殊退化情形：β=identity 时，C(x) 的 determinant factors 分解成 advantage planes Q_s=0 和 Bellman residual planes B_{s,a}=0，边界是 hyperplanes，得到 polyhedral geometry；β 非平凡时，这些 factors 通常不再完全分解，出现 conic / higher-degree components。论文中 2×2×2 例子很有说服力：fully observable 下 sign polynomials 全部分解为线性项；partial observable 下出现 irreducible quadratic。这个例子基本说明了“曲边界从哪里来”。

最可能的核心贡献是 zonotope / determinantal characterization，而不是 policy-gradient 实验。实验只是展示这种几何确实会让优化看起来多峰；理论部分才是新增信息。Theorem 3.7 的无限 inequality 描述概念上漂亮，但计算上不如 Theorem 4.1 / quantifier-free stratification 重要。anchor hyperrectangle construction 是必要技术桥接，但带有一定工程化/证明技巧色彩；真正可迁移的是 residual zonotope view。

这不是 scaling、data coverage、retrieval 或 benchmark trick 类型工作；它是 latent structure / representation of feasibility 的理论重组。若要类比机器学习机制，它给 POMDP policy optimization 提供了一个新的 inductive bias：不要只看 policy parameter landscape，而应看 value image 的 semi-algebraic boundary 和 objective hyperplanes 的接触方式。

Relation To Prior Work

最接近的是三条线。

第一是 Dadashi et al. 的 value function polytope。本文本质上是把那条线从 fully observable MDP 推到 POMDP，但不是简单推广：MDP 结果依赖 state-wise policy independent variation；POMDP 中这个结构消失，所以 polytope 变 semi-algebraic set。论文的贡献在于指出 MDP polytope 是 determinant factors 完全线性分解的退化情形，而不是普遍现象。

第二是 Müller & Montúfar 关于 memoryless POMDP 中 value / occupancy measure rational parametrization 的工作。那条路线强调 policy 参数到 value/occupancy 的有理映射和代数优化；本文关注的是 image set 的 implicit description，即给定 x 是否可实现。两者是同一代数谱系，但本文新增的是 value set boundary / feasibility 的 explicit semi-algebraic geometry。

第三是 robust MDP value geometry / conic hypersurface 类工作。相似点是都发现非标准 MDP 变体会把 polyhedral structure 替换成曲面约束；不同点在于 robust MDP 的非线性来自 adversarial transition uncertainty，本文的非线性来自 observation-induced policy coupling。

看似新的“POMDP 多局部最优”并不是新现象；新的是给它一个几何来源：线性目标在非凸/曲边界 semi-algebraic value set 上优化，局部支撑点可孤立且随初始分布变化。

Dataset / Evaluation

这篇主要是理论论文，evaluation 是数值插图而不是核心证据。实验覆盖两类：小规模 2-state 例子用于可视化 semi-algebraic 边界；随机生成 POMDP 上用多次 policy-gradient 重启观察 value spread、policy spread、多局部最优，以及有限 memory enrichment 后 spread 是否下降。

这些实验能支持的 claim 是有限的：它们说明 partial observability 下确实容易出现多峰优化现象，并且 fully observable baseline 通常没有类似 spread；小例子也很好地展示了边界从直线变成 conic。它们不能严格验证“所有优化困难都由本文刻画的 semi-algebraic boundary 导致”，因为 policy-gradient 的结果还受 softmax 参数化、初始化、步长、停止时间和 clustering tolerance 影响。

没有真实世界任务、没有大规模 benchmark、也没有算法性能 claim，因此不应按 empirical RL paper 的标准解读。数值部分的价值是 diagnostic / illustrative：验证理论图像是否和常见 optimization pathology 对齐，而不是证明一个 practical solver 更强。

Limitation

第一，理论限定在 memoryless stochastic policies。对 POMDP 而言，这既是使问题可代数化的关键前提，也是最大的外部有效性限制。允许 belief-state policies 后，问题会转到连续 belief MDP；允许 finite-memory policies 后，observation space expansion 会指数增长，半代数结构可能仍存在但复杂度和解释性都会恶化。

第二，finite semi-algebraic description 不等于可计算算法。determinantal stratification 需要枚举 rank、row subsets、basis subsets，组合爆炸明显。论文提到相比一般量词消去更低，但这仍然离 scalable POMDP optimization 很远。这里有“把问题转移到代数可行性/符号计算”的倾向。

第三，Theorem 3.7 依赖 simplex image 与 hyperrectangle image intersection 的保持条件；作者给了 generic injectivity sufficient condition，如 |O|≤|S|、|A|≤|S|+1 下 generic α,β,r 成立。但实际结构化 POMDP 经常不是 generic；退化 observation、symmetry、reward sparsity 都可能破坏这些假设。文中未充分说明这些非 generic case 如何处理。

第四，实验对 landscape 的归因不完全干净。多重启 spread 可以来自 semi-algebraic geometry，也可以来自 softmax saturation、梯度条件数、有限迭代不足。作者用 fully observable baseline 控制了一部分，但没有做足够的 optimizer-independent critical point enumeration。因此实验增益/现象来源不应过度解释。

第五，边界条件中的 polynomial degree、component count 与 POMDP 的 observability rank / degree of observability 之间关系还不清楚。没有这个复杂度理论，semi-algebraic characterization 的算法上限很难判断。

Takeaway

• 1. 最值得记住的是建模转向：POMDP value feasibility 可以被看作 affine-parametric Bellman linear system 的 solution set；partial observability 的几何复杂性来自 policy 参数耦合后的消元。
• 2. MDP value polytope 不是一般规律，而是 β=identity 下 polynomial factors 线性分解的退化情形。
• POMDP 中 curved algebraic boundary 是结构性现象，不是优化器 artifact。
• 3. Zonotope membership 是一个可迁移 insight：很多“参数化线性系统的可实现输出集合”都可以通过 midpoint residual 落入 deviation zonotope 来理解，进而得到 semi-algebraic feasibility 条件。

一句话总结

这篇论文把 memoryless POMDP 的 value-function geometry 从 MDP 的 polytope 图景推进到 parametric-linear-system 诱导的 semi-algebraic 图景，真正贡献是解释并刻画 partial observability 如何通过 policy coupling 生成曲边界和多局部最优。