Optimal strategies in Markov decision processes with finitely additive evaluations

本文针对使用扩散有限可加测度评估的无限时域马尔可夫决策过程，通过构造反例证明了在缺乏额外假设（如时间价值原则）的情况下，即使状态和动作空间有限，也可能不存在任何最优策略（包括纯策略和随机化策略）。

要点

这是一篇关于决策数学（马尔可夫决策过程，MDP）的学术论文，但它的核心发现非常反直觉：在某些极其特殊的情况下，无论你怎么做，都找不到一个“完美”的决策方案。

为了让你轻松理解，我们把这篇论文里的数学概念变成一个关于**“无限期游戏”**的故事。

1. 背景：一个永远玩下去的游戏

想象你在玩一个无限期的电子游戏。

• 场景：你处于不同的关卡（状态），每个关卡你可以选择不同的操作（动作）。
• 奖励：每次操作，你会得到一些分数（奖励）。
• 目标：你想玩一辈子，并且希望你的总得分尽可能高。

在传统的游戏里，我们通常有两种算分方法：

1. 打折法（Discounting）：今天的 100 分比明天的 100 分值钱。越晚得到的分数，价值越低。
2. 平均法（Average）：不管什么时候，分数都一样重要，我们只看长期的平均分。

这篇论文研究的是第三种、也是最刁钻的算分方法：“模糊加权法”。

2. 核心概念：那个“模糊的裁判”

论文里引入了一个叫做**“扩散电荷”（Diffuse Charge）的东西。你可以把它想象成一个“没有偏见的、但很奇怪的裁判”**。

• 普通裁判：会数每一秒。第 1 秒、第 2 秒……每一秒都有具体的权重。
• 模糊裁判（扩散电荷）：它不关心具体的某一秒。它认为第 1 秒、第 100 秒、第 100 万秒，单独看都没有任何分量（权重为 0）。
• 它怎么算分？：它只看**“模式”**。比如，它可能觉得“所有奇数秒”加起来很重要，或者“所有能被 4 整除的秒”加起来很重要。它把无限的时间流看作一个整体，给不同的时间模式打分。

论文的关键问题：
如果面对这样一个“只看模式、不看具体时刻”的模糊裁判，玩家能不能找到一个**“最优策略”**（即无论怎么变，都能拿到最高分的玩法）？

3. 之前的发现：只要裁判“讲道理”，就有最优解

论文提到，之前的学者（Neyman, 2023）发现，如果这个模糊裁判遵循**“货币的时间价值”原则（简单说：就是它虽然不看具体时刻，但它认为“越早得到的分数越好”或者至少不违背常理），那么玩家一定**能找到一个完美的策略（通常是纯策略，即每次到了某个状态就固定选同一个动作）。

比喻：如果裁判虽然不看秒表，但他遵循“早起的鸟儿有虫吃”的原则，那你只要一直早起，就能赢。

4. 这篇论文的突破：如果裁判“不讲道理”呢？

作者们问：如果裁判完全不讲“时间价值”原则，甚至故意刁难，玩家还能赢吗？

答案是：不能。

作者构造了一个极其精妙的**“奇偶陷阱”游戏**，证明了在这种情况下，根本不存在最优策略。

这个“奇偶陷阱”游戏是这样的：

• 游戏设置：

  • 你在第 1 关（状态 1），有两个选择：
    • 选 A（T）：现在得 1 分，下一关得 0 分。
    • 选 B（B）：现在得 0 分，下一关得 1 分。
  • 然后游戏会自动回到第 1 关，无限循环。
  • 简单来说：你必须在“现在拿分”和“下一轮拿分”之间做选择。

• 裁判的“双重人格”：
  作者设计了一个特殊的模糊裁判，它由两部分组成：

  1. 部分一（关注奇数秒）：它只在乎你在奇数秒（第 1, 3, 5...秒）的表现。如果你在第 1 秒选 A（得 1 分），它很高兴；如果你选 B（得 0 分），它很生气。
  2. 部分二（关注特定的偶数模式）：它只在乎你在某些特定的偶数秒（比如第 2, 4, 8, 16...秒）的表现。它希望你偶尔在第 1 秒选 B（为了在第 2 秒得 1 分）。

• 为什么没有最优解？（死循环）：

  • 如果你总是选 A（为了讨好“部分一”）：你在奇数秒拿满分，但在偶数秒全是 0 分。裁判的“部分二”会觉得你太笨了，因为它看重那些偶数秒的得分，你的总分被拉低了。
  • 如果你总是选 B（为了讨好“部分二”）：你在奇数秒全是 0 分，奇数秒的“部分一”会把你打得很惨。
  • 如果你交替选（A, B, A, B...）：
    • 你在奇数秒得 1 分，偶数秒得 1 分。看起来完美？
    • 错！ 因为裁判的“部分二”非常挑剔，它要求的不是简单的交替，而是基于2 的幂次（2, 4, 8, 16...）的复杂模式。
    • 如果你为了迎合“部分二”的复杂模式，你就必须在某些奇数秒牺牲分数（选 B），这会让“部分一”扣分。
    • 如果你为了迎合“部分一”一直选 A，又会让“部分二”扣分。

结论：无论你制定什么策略（纯的、随机的、固定的、变化的），你总能找到一个更聪明的策略来稍微提高一点点分数，但永远无法达到那个理论上的最高分（1 分）。就像你追着一只永远跑在你前面一步的兔子，永远抓不住。

5. 其他有趣的发现

论文还讨论了两种情况：

1. 如果裁判是“死板的”（只关注具体的某几秒，比如只算前 100 秒）：那你肯定有最优解，就像玩普通游戏一样。
2. 如果裁判是“混合怪”（既看具体秒数，又看模糊模式）：作者举了个例子，说明这种情况下也可能没有最优解。这就好比你想同时最大化“现在的存款”和“未来的平均收入”，有时候这两个目标会打架，让你怎么做都不满意。

总结：这篇论文告诉我们什么？

用大白话总结就是：

在无限期的决策游戏中，如果评价标准（裁判）变得过于抽象和复杂（既不看具体时刻，又对时间模式有极其刁钻的要求），那么**“完美”是不存在的**。

你总是可以做得“更好一点”，但永远无法做到“最好”。这打破了人们通常认为的“只要规则确定，就一定能找到最佳方案”的直觉。

生活中的启示：
这就像你在生活中做决定。如果你试图同时满足所有不同维度的评价标准（比如：既要现在立刻爽，又要未来长期稳，还要符合某种极其复杂的道德或社会模式），你可能会发现，根本没有一个完美的方案能让你在所有方面都达到顶峰。你只能不断逼近，但永远无法到达那个“绝对完美”的终点。

技术摘要

论文技术总结

1. 研究背景与问题定义 (Problem)

• 研究对象：无限时域马尔可夫决策过程（MDP），具有有限的状态空间和动作空间。
• 核心挑战：传统的 MDP 通常使用折扣因子（discount factor）或长期平均奖励（long-term average reward）来评估策略。本文研究的是更一般的评估方式：决策者通过一个给定的**扩散电荷（diffuse charge）**来聚合无限的时间序列期望奖励。
  • 扩散电荷：定义在自然数集 $\mathbb{N}$ 上的有限可加概率测度，且对每个单点集的测度为 0（即 $\mu(\{n\}) = 0$）。
  • 收益定义：策略 $\sigma$ 的收益 $u_\mu(\sigma)$ 定义为期望奖励序列关于该电荷 $\mu$ 的积分。
• 核心问题：
  • 已知 Neyman [2023] 证明了：如果聚合电荷满足“货币时间价值原则”（Time Value of Money principle，即满足特定的极限不等式条件），则存在纯策略最优解。
  • 本文要解决的问题：当聚合电荷不满足货币时间价值原则时，是否仍然存在最优策略（无论是纯策略还是随机化策略）？

2. 方法论与模型构建 (Methodology)

• 数学工具：
  • 有限可加测度理论：利用 ZFC 公理体系下的电荷（Charges）理论，特别是扩散电荷（Diffuse charges）和频率电荷（Frequency charges）。
  • 拓扑学：在电荷集合 $\Delta_f$ 上引入逐点收敛拓扑（topology of pointwise convergence），利用其紧性（Compactness）来构造反例中的极限电荷。
  • 积分理论：定义关于有限可加测度的积分，用于计算策略收益。
• 模型设定：
  • 定义了一个名为“偶数或奇数 MDP"（Even-or-Odd MDP）的特定模型。
  • 状态空间：$S = \{1, 2, 3\}$，初始状态为 1。
  • 动作与转移：
    • 在状态 1：选择动作 $T$（获得奖励 1，下一状态为 2）或 $B$（获得奖励 0，下一状态为 3）。
    • 在状态 2 和 3：只有唯一动作，奖励分别为 0 和 1，且下一状态均回到状态 1。
    • 这是一个确定性转移系统。
  • 策略困境：在奇数阶段，决策者必须在“现在得 1 未来得 0"（选 $T$）和“现在得 0 未来得 1"（选 $B$）之间做选择。

3. 关键贡献与主要结果 (Key Contributions & Results)

本文的主要贡献是否定了在任意扩散电荷下最优策略存在的普遍性，具体通过以下两个部分展示：

A. 主要定理：最优策略的不存在性 (Theorem 3)

• 构造：作者构造了一个极其微妙的扩散电荷 $\mu$，它是两个部分的凸组合：$\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$。
  • $\mu_0$：集中在奇数阶段上的电荷。
  • $\mu^*$：通过一列电荷 $\{\mu_n\}$ 的聚点构造而成，该电荷在特定的偶数子集序列 $\{E_n\}$ 上具有测度 1，但在频率意义下这些集合的测度趋于 0。
• 结论：在这个构造的 MDP($\mu$) 中，不存在任何最优策略（既没有纯策略，也没有随机化策略）。
• 证明逻辑：
  1. 上确界为 1：通过构造一系列策略 $\sigma_n$，可以证明收益的上确界 $v_\mu = 1$。这些策略在特定的有限集合上表现完美，随着 $n \to \infty$，收益趋近于 1。
  2. 无法达到 1：证明任何固定策略 $\sigma$ 的收益严格小于 1。
     • 如果策略在某个阶段 $t$ 的期望奖励 $> 1/2$，则必须在 $t$ 和 $t+1$ 之间做出权衡（因为 $r_t + r_{t+1} = 1$）。
     • 利用 $\mu_0$ 和 $\mu^*$ 的构造特性（特别是 $\mu^*$ 对集合 $E_n$ 的测度为 1，而 $E_n$ 在平移后与奇数集不交），推导出任何试图最大化收益的策略都会导致在 $\mu_0$ 或 $\mu^*$ 分量上的损失，从而无法同时满足两个分量的最优性。
  3. 矛盾：假设存在收益为 1 的策略会导致逻辑矛盾，因此最优策略不存在。

B. 辅助结果：平稳策略的失效 (Example 4)

• 即使存在纯最优策略，也不一定是平稳策略（Stationary Strategy）。
• 作者构造了另一个电荷 $\mu'$，使得在“偶数或奇数 MDP"中存在纯最优策略（通过交替选择 $T$ 和 $B$），但任何平稳策略（即只依赖当前状态的概率分布）的收益都严格低于最优值（$1/2 < 1$）。

C. 非扩散电荷的情况 (Section 5)

• 如果电荷不是扩散的（即包含可加部分），通常存在最优策略（如折扣 MDP）。
• 但如果电荷是“可加部分 + 扩散部分”的混合，且扩散部分权重为正，则可能再次出现最优策略不存在的情况（如 Example 5 所示，结合了折扣和平均奖励的混合评估）。

4. 意义与影响 (Significance)

1. 理论突破：推翻了“在有限状态/动作 MDP 中，只要评估是线性的，就必然存在最优策略”的直觉。证明了在缺乏“货币时间价值原则”等额外假设时，最优策略的存在性无法保证。
2. 对 Neyman [2023] 的补充：Neyman 的结果表明在满足特定条件（货币时间价值）下存在稳健的最优策略。本文通过反例表明，一旦脱离这些条件，即使允许随机化策略，最优性也可能完全丧失。
3. 对决策理论的启示：
   • 揭示了无限时域决策中，评估函数的拓扑性质（如电荷的构造方式）对策略存在性的决定性作用。
   • 表明在某些复杂的长期评估标准下，决策者可能面临“没有最佳选择”的困境，只能不断逼近最优值而无法达到。
4. 方法论创新：展示了如何利用有限可加测度的拓扑性质（聚点构造）来构建反例，为处理非标准评估下的动态规划问题提供了新的数学视角。

5. 总结

这篇论文通过精妙的数学构造，证明了在具有有限可加扩散电荷评估的无限时域 MDP 中，最优策略可能根本不存在。这一发现填补了现有文献的空白，强调了在动态决策模型中评估机制（Aggregation Mechanism）的具体性质对于解的存在性至关重要。它提醒研究者和实践者，在应用非标准评估（如某些形式的长期平均或混合评估）时，必须谨慎对待最优策略的存在性假设。