2025-11-24T11:16:18.396523

Uniform Value and Decidability in Ergodic Blind Stochastic Games

Chatterjee, Lurie, Saona et al.
We study a class of two-player zero-sum stochastic games known as \textit{blind stochastic games}, where players neither observe the state nor receive any information about it during the game. A central concept for analyzing long-duration stochastic games is the \textit{uniform value}. A game has a uniform value $v$ if for every $\varepsilon>0$, Player 1 (resp., Player 2) has a strategy such that, for all sufficiently large $n$, his average payoff over $n$ stages is at least $v-\varepsilon$ (resp., at most $v+\varepsilon$). Prior work has shown that the uniform value may not exist in general blind stochastic games. To address this, we introduce a subclass called \textit{ergodic blind stochastic games}, defined by imposing an ergodicity condition on the state transitions. For this subclass, we prove the existence of the uniform value and provide an algorithm to approximate it, establishing the \textit{decidability} of the approximation problem. Notably, this decidability result is novel even in the single-player setting of Partially Observable Markov Decision Processes (POMDPs). Furthermore, we show that no algorithm can compute the uniform value exactly, emphasizing the tightness of our result. Finally, we establish that the uniform value is independent of the initial belief.
academic

Uniform Value and Decidability in Ergodic Blind Stochastic Games

基本信息

  • 论文ID: 2405.12583
  • 标题: Uniform Value and Decidability in Ergodic Blind Stochastic Games
  • 作者: Krishnendu Chatterjee (IST Austria), David Lurie (NyxAir & Paris Dauphine University), Raimundo Saona (IST Austria), Bruno Ziliotto (Toulouse School of Economics)
  • 分类: math.OC (Optimization and Control), cs.CC (Computational Complexity)
  • 发表时间: arXiv v2, November 21, 2025
  • 论文链接: https://arxiv.org/abs/2405.12583v2

摘要

本文研究盲随机博弈(blind stochastic games)——一类双人零和随机博弈，其中参与者既不观察状态也不接收任何关于状态的信息。论文引入了遍历盲随机博弈(ergodic blind stochastic games)这一子类，通过对状态转移施加遍历性条件来定义。对于这一子类，论文证明了一致值(uniform value)的存在性，并提供了近似算法，建立了近似问题的可判定性。这一可判定性结果即使在单人设置的部分可观测马尔可夫决策过程(POMDPs)中也是新颖的。此外，论文证明了无算法能精确计算一致值，强调了结果的紧致性。最后，论文确立了一致值独立于初始信念。

研究背景与动机

研究问题

本文要解决的核心问题是：在盲随机博弈中，如何刻画长期博弈的价值？具体而言：

  1. 一致值的存在性问题：Ziliotto Zil16已证明一般盲随机博弈可能不存在一致值，那么在什么条件下一致值存在？
  2. 可计算性问题：即使一致值存在，能否通过算法计算或近似它？Madani等人MHC03已证明在一般盲MDP中，计算和近似一致值都是不可判定的。

问题重要性

  1. 理论意义：盲随机博弈是不完全信息博弈的最简单模型，是研究更复杂模型的理论基准。它等价于概率有限自动机，在计算机科学中有广泛应用。
  2. 实际应用：包括无限字符串的简洁规范语言BGB12, CT12、计算生物学中的序列分析DEKM98、语音处理Moh97等。
  3. 方法论贡献：通过识别数据上的条件来确保信念动态呈现遍历行为，这是一个关键的方法论贡献。

现有方法的局限性

  1. 一般盲随机博弈：不保证一致值存在Zil16
  2. 可交换盲随机博弈：VenelVen15证明了一致值存在，但未提供计算算法
  3. 盲MDP：Rosenberg等人RSV02证明一致值存在，但Madani等人MHC03证明计算和近似都不可判定
  4. 现有遍历性研究：主要集中在标准随机博弈或MDP，未系统研究盲随机博弈

研究动机

论文的出发点是通过引入遍历性条件来识别一个可判定的盲随机博弈子类，这个条件：

  • 在博弈论文献中自然且常用
  • 能保证一致值存在
  • 使得近似问题可判定
  • 精确计算仍然不可判定，显示结果的紧致性

核心贡献

论文的主要贡献包括：

  1. 定义遍历盲随机博弈：基于转移矩阵乘积的遍历性质，形式化定义了这一新的博弈子类（定义3.3）
  2. 一致值存在性与近似可判定性（定理3.5）：
    • 证明所有遍历盲随机博弈都有一致值
    • 提供近似算法，建立近似问题的可判定性
    • 复杂度上界为2-EXPSPACE
  3. 精确计算的不可判定性（定理3.6）：
    • 证明即使对于Markov盲MDP（遍历盲随机博弈的子类），精确计算一致值也是不可判定的
    • 这显示了近似可判定性结果的紧致性
  4. 初始信念独立性（定理3.7）：
    • 证明在遍历盲随机博弈中，一致值不依赖于初始信念
  5. 充分条件：识别了几类保证遍历性的转移矩阵类别（C1-C5），包括Markov矩阵、scrambling矩阵、Sarymsakov矩阵等
  6. 验证算法（命题3.9）：提供了验证盲随机博弈是否满足遍历性质的指数空间算法

方法详解

任务定义

盲随机博弈定义为五元组 Γ = (K, I, J, p, g)：

  • K：有限状态集
  • I, J：玩家1和玩家2的有限动作集
  • p: K × I × J → Δ(K)：概率转移函数
  • g: K × I × J → 0,1：阶段奖励函数

关键特征：玩家不观察状态，只知道初始信念b₁ ∈ Δ(K)和历史动作。

一致值定义：博弈Γ有一致值v: Δ(K) → 0,1，如果对所有b₁ ∈ Δ(K)和ε > 0，存在策略(σ*, π*)和n ∈ ℕ*，使得对所有N ≥ n：

  • 玩家1可保证：γ^(b₁)_N(σ*, π) ≥ v(b₁) - ε
  • 玩家2可保证：γ^(b₁)_N(σ, π*) ≤ v(b₁) + ε

其中γ^(b₁)N(σ, π) = 𝔼^(b₁)(σ,π)1/N ∑^N_(m=1) G_m是N阶段平均奖励。

遍历性刻画

核心概念：遍历性系数τ₁。对于随机矩阵P，定义：

τ₁(P) := 1/2 max_(k,k̄) ∑^|K|(k'=1) |p(k,k') - p_(k̄,k')|

遍历盲随机博弈（定义3.3）：博弈Γ是遍历的，如果对所有ε > 0，存在整数n₀使得对所有长度n ≥ n₀的动作对序列aⁿ：

τ₁(Tⁿ(aⁿ)) ≤ ε

其中Tⁿ(aⁿ) = P(a₁)P(a₂)···P(aₙ)是前向转移矩阵乘积。

关键性质（命题3.8）：博弈Γ是遍历的当且仅当存在n₀ ≤ (3^|K| - 2^(|K|+1) + 1)/2使得对所有长度n₀的动作对序列：

τ₁(Tⁿ⁰(aⁿ⁰)) < 1

模型架构：抽象随机博弈

论文的核心方法是构造一个抽象随机博弈(abstract stochastic game) G*(b₁, ε)，它是有限状态的，并且能以误差ε近似原始盲随机博弈。

构造步骤：

步骤1：确定时间尺度（命题4.1）

  • 给定ε > 0，计算nε = n₀⌈ln(ε)/ln(sup_(aⁿ⁰) τ₁(Tⁿ⁰(aⁿ⁰)))⌉
  • 对所有长度n ≥ nε的序列aⁿ，有τ₁(Tⁿ(aⁿ)) ≤ ε

步骤2：构造稳定矩阵集

  • T(ε)：所有长度n满足τ₁条件的前向乘积矩阵集合
  • T̃(ε)：抽象稳定矩阵集，对每个Tⁿ ∈ T(ε)，定义T̃ⁿ使得：
    t̃ⁿ_(k,k')(aⁿ) := 1/|K| ∑^|K|(k=1) tⁿ(k,k')(aⁿ)
    即每行都等于所有行的平均值，使矩阵稳定（所有行相同）

步骤3：定义抽象状态空间

抽象信念集：B* := {b* ∈ Δ(K) | ∃T̃ⁿ ∈ T̃(ε) s.t. b* = b₁^⊤T̃ⁿ} ∪ {b₁}

状态空间：X := ⋃^(n-1)_(m=0) (B* × (I × J)^m)

这是有限集，大小为O(|I × J|^(2n))，其中n是双指数的。

步骤4：定义转移和奖励

  • 投影函数proj: X → Δ(K)将抽象状态映射到信念
  • 抽象更新函数ψ*：
    • 若m ∈ 0, n-2：ψ*(x, a) = (b*, a₁, ···, a_m, a)
    • 若m = n-1：ψ*(x, a) = (proj(x)^⊤T̃ⁿ(aⁿ))（重置到新的抽象信念）
  • 转移函数：p*(x'|x, a) = 1若x' = ψ*(x, a)，否则为0（确定性）
  • 奖励函数：g*(x, i, j) = ∑_(k∈K) proj(x)(k)·g(k, i, j)

技术创新点

1. 聚合方案的设计

  • 关键洞察：遍历性保证长度n后，所有转移矩阵的行变得相似（差异≤ε）
  • 稳定化技巧：通过平均化构造稳定矩阵，使得信念更新独立于初始信念
  • 分块结构：每n步重置一次，利用遍历性的"记忆消失"性质

2. 误差控制的精细分析

  • 引理4.2：证明原始博弈和抽象博弈的信念距离有界：
    ||b^(b₁,h_m)(m,σ,π) - proj(x^(b₁,h_m)(m,σ,π))||₁ ≤ 4ε
  • 引理4.3：证明平均奖励差有界：
    |𝔼^(b₁)(σ,π)1/N ∑^N_(m=1) G_m - 𝔼^(b₁)(σ,π)1/N ∑^N_(m=1) G*_m| ≤ 4ε

3. 与baseline的区别

  • vs. VenelVen15的可交换博弈：不仅证明存在性，还提供可判定算法
  • vs. 标准随机博弈遍历性：条件施加在原始数据上，而非信念博弈上
  • vs. 盲MDP文献：首次在双人博弈中建立近似可判定性

4. 不可判定性证明的巧妙性

  • 通过从概率有限自动机(PFA)的普遍性问题归约
  • 构造Restart动作使得盲MDP能模拟PFA
  • 添加状态k̂使所有转移矩阵都是Markov（保证遍历性）
  • 证明接受概率>1/2等价于长期平均值>1/2

实验设置

示例：机器维护问题（例3.1）

问题描述：

  • 状态：K = {Good, Fair, Poor}（机器状况）
  • 动作：I = {Wait, Basic Maintenance, Critical Repair}
  • 玩家监控不可访问的机器，根据历史动作决策

转移矩阵（部分展示）：

Wait动作下：
     G    F    P
G  0.9  0.1  0.0
F  0.0  0.7  0.3
P  0.0  0.1  0.9

验证遍历性：

  • 每个动作的转移矩阵P(i)都是Markov矩阵（至少一列全为正）
  • 因此τ₁(P(i)) < 1对所有i ∈ I成立
  • 满足遍历性质

算法实现（算法1）

输入：初始信念b₁, 盲随机博弈Γ, 精度ε
1. 验证Γ的遍历性质
2. 构造矩阵集T(ε)
3. 从T(ε)导出抽象矩阵集T̃(ε)
4. 构造抽象随机博弈G*(b₁, ε)
5. 计算G*(b₁, ε)的一致值v*(b₁, ε)
输出：v*(b₁, ε)（如果Γ是遍历的）

复杂度分析：

  • 状态数：O(|I × J|^(2n))，其中n ≤ (3^|K| - 2^(|K|+1) + 1)/2
  • 通过实闭域理论，可在PSPACE内求解标准随机博弈CMH08
  • 总体复杂度：2-EXPSPACE

实验结果

主要理论结果

论文主要是理论工作，核心结果总结在表2：

类别一致值存在精确可判定近似可判定值为常数充分条件
遍历盲MDP是不可判定可判定是是
遍历盲随机博弈是不可判定可判定是是
Scrambling隐藏随机博弈?不可判定??是

（粗体表示本文新结果）

定理验证

定理3.5（存在性与可判定性）：

  • 证明策略：通过4步构造
    1. 构造抽象博弈G*(b₁, ε)
    2. 证明信念保持接近（引理4.2）
    3. 证明奖励保持接近（引理4.3）
    4. 利用标准随机博弈的一致值存在性
  • 误差界：|v*(b₁, ε) - v(b₁)| ≤ 4ε
  • 可判定性：通过归约到有限状态随机博弈

定理3.6（不可判定性）：

  • 证明策略：从PFA普遍性问题归约
  • 关键构造：
    • 添加吸收状态k̂
    • Restart动作重置到初始状态
    • 奖励设计使得接受概率>1/2 ⟺ 长期平均>1/2
  • 分离结果：与标准随机博弈（精确可判定OB21）形成对比

定理3.7（初始信念独立性）：

  • 证明要点：在抽象博弈中，不同初始信念只在前nε步有差异
  • 误差界：|v(b₁) - v(b'₁)| ≤ 8ε对任意b₁, b'₁

充分条件的层次结构

论文识别了矩阵类的严格包含关系：

C₅ ⊊ C₄ ⊊ C₃ ⊊ C₂ ⊊ C₁

其中：

  • C₅（Markov）：至少一列全为正
  • C₄（Scrambling）：任意两行有公共后继
  • C₃（Sarymsakov）：任意两个不相交子集要么有公共可达状态，要么可达集合扩大
  • C₂（C₂-矩阵）：SIA且与所有SIA矩阵的乘积仍是SIA
  • C₁（SIA）：Pⁿ收敛到稳定矩阵

所有这些类的转移矩阵都保证盲随机博弈是遍历的。

相关工作

盲随机博弈基础

  1. 标准随机博弈Sha53：完全观测状态
    • Mertens-NeymanMN81：一致值总是存在
    • 算法：OB21等提供计算方法
  2. 盲随机博弈：
    • N阶段值存在vN28
    • ZiliottoZil16：一致值可能不存在的反例
    • VenelVen15：可交换条件下一致值存在（无算法）

单人情形（盲MDP/PFA）

  1. 存在性：Rosenberg等RSV02证明盲MDP的一致值存在
  2. 不可判定性：Madani等MHC03证明计算和近似都不可判定
  3. 有限记忆：Chatterjee等CSZ22证明有限记忆策略足够，但记忆大小无可计算界

遍历性研究

  1. 标准随机博弈：
    • 有限状态HK66, Sob71, Vri03
    • 可数状态Now99
    • 应用：加密货币攻击分析CKGIV18
  2. MDP中的遍历性：
    • 有限状态AS92, HBS87, WSS11
    • 可数状态BSL90, PBS93
    • 综述ABFG+93, Put14
  3. 自动机理论：
    • 单人情形CSV13研究了隔离割点的概率自动机
    • 本文扩展到双人博弈

可判定性研究

  1. 正面结果：
    • 强假设下CH10
    • 其他目标CCT16, CDH13, GO14
  2. 负面结果：
    • ω-正则目标Cha07
    • 部分可观测博弈CCGK16

本文相对优势

  1. vs. VenelVen15：不仅存在性，还有算法
  2. vs. 盲MDP文献：首次建立双人博弈的近似可判定性
  3. vs. 标准遍历性：条件施加在原始数据上，识别信念动态的遍历行为
  4. 新颖性：即使在单人POMDP中，近似可判定性也是新的

结论与讨论

主要结论

  1. 存在性：遍历盲随机博弈总有一致值
  2. 可判定性二分：
    • 近似：可判定（2-EXPSPACE）
    • 精确：不可判定（即使对Markov盲MDP）
  3. 初始信念无关性：一致值是常数函数
  4. 充分条件：识别了5类矩阵类别保证遍历性
  5. 验证算法：指数空间可判定遍历性质

局限性

1. 复杂度

  • 2-EXPSPACE上界较高
  • 实际计算可能不可行
  • 未给出下界

2. 适用范围

  • 仅限遍历情形
  • 遍历条件（式1）需要对所有动作序列一致成立
  • 许多实际博弈可能不满足

3. 精确计算

  • 定理3.6显示精确计算不可判定
  • 只能近似到任意精度
  • 无法判断近似值的质量

4. 扩展性问题

  • 隐藏随机博弈（有信号）的扩展面临重大挑战
  • 随机转移导致误差传播
  • 存在性和可判定性仍开放

未来方向

1. 隐藏随机博弈（第5节讨论）

  • Scrambling隐藏博弈：定义5.2给出了推广
  • 开放问题：
    • 一致值是否存在？
    • 近似是否可判定？
  • 主要障碍：
    • 信念转移变为随机（vs. 盲博弈的确定性）
    • 无法完美耦合原始和抽象博弈
    • 误差可能传播RSV02

2. 复杂度改进

  • 降低2-EXPSPACE上界
  • 建立匹配下界
  • 识别多项式时间可解的子类

3. 算法优化

  • 实际可实现的算法
  • 利用问题结构
  • 近似质量的在线估计

4. 应用探索

  • 机器人导航（部分可观测）
  • 网络安全（攻防博弈）
  • 资源管理（不完全信息）

5. 理论深化

  • 遍历性的其他刻画
  • 与其他博弈类别的关系
  • 多人博弈的推广

深度评价

优点

1. 理论贡献显著

  • 开创性：首次在盲随机博弈中建立近似可判定性
  • 紧致性：不可判定性结果显示近似是最好的可能
  • 统一性：同时处理存在性、可判定性和初始信念独立性

2. 方法论创新

  • 抽象博弈构造：优雅地利用遍历性构造有限近似
  • 稳定化技巧：通过平均化使信念更新独立化
  • 误差分析：精细的ε-控制贯穿整个证明

3. 技术深度

  • 矩阵理论：深入利用遍历系数和矩阵乘积理论
  • 复杂性理论：巧妙的归约证明不可判定性
  • 博弈论：连接多个研究领域（自动机、MDP、随机博弈）

4. 结果完整性

  • 提供充分条件（5类矩阵）
  • 给出验证算法（命题3.9）
  • 包含具体例子（例3.1）
  • 讨论扩展方向（第5节）

5. 写作清晰

  • 结构合理，逻辑清晰
  • 定义严格，符号规范
  • 证明详细，易于验证
  • 相关工作梳理全面

不足

1. 计算复杂度

  • 2-EXPSPACE过高：实际不可行
  • 无下界：不知道是否可改进
  • 无实验：未评估实际性能

2. 适用性限制

  • 遍历条件强：式(1)要求对所有序列一致
  • 有限状态：无限状态空间未考虑
  • 零和假设：一般和博弈未讨论

3. 算法细节

  • 算法1过于抽象：缺乏实现细节
  • 数值稳定性：未讨论浮点计算问题
  • 参数选择：如何选择ε未给出指导

4. 实验验证

  • 仅一个例子：例3.1过于简单
  • 无性能评估：实际运行时间、内存使用未知
  • 无对比：与其他方法（如采样）未比较

5. 扩展性问题

  • 隐藏博弈：主要障碍未解决
  • 多人博弈：未讨论
  • 其他目标：如折扣奖励、可达性未充分探讨

影响力

1. 理论影响

  • 填补空白：在盲随机博弈和POMDP中建立首个近似可判定性结果
  • 方法论：抽象博弈构造可能启发其他不完全信息博弈研究
  • 复杂性理论：精确vs.近似的二分法是重要洞察

2. 实用价值

  • 有限：2-EXPSPACE复杂度限制实际应用
  • 理论指导：识别可处理的子类有价值
  • 基准：可作为其他启发式方法的理论基准

3. 可复现性

  • 理论结果：证明详细，可验证
  • 算法：描述清晰，可实现
  • 例子：简单可重现
  • 代码：未提供实现

4. 后续研究

  • 直接扩展：隐藏博弈、多人博弈
  • 算法改进：降低复杂度、实际实现
  • 应用：具体领域的建模和求解

适用场景

理论上适用：

  1. 小规模问题：状态和动作空间较小
  2. 遍历性强：转移矩阵快速混合
  3. 近似足够：不需要精确值
  4. 离线计算：可容忍高计算成本

具体应用：

  1. 机器维护：如例3.1，状态不可观测的维护决策
  2. 网络监控：基于历史数据的入侵检测
  3. 机器人导航：部分可观测环境中的路径规划
  4. 资源分配：不完全信息下的竞争资源分配

不适用场景：

  1. 大规模系统：状态空间指数爆炸
  2. 非遍历系统：长期依赖历史
  3. 实时决策：计算时间受限
  4. 精确要求：需要精确最优策略

参考文献（精选）

  1. MN81 Mertens & Neyman (1981): 标准随机博弈一致值存在性的奠基性工作
  2. Zil16 Ziliotto (2016): 盲随机博弈一致值可能不存在的反例
  3. MHC03 Madani, Hanks & Condon (2003): 盲MDP不可判定性的经典结果
  4. Sen06 Seneta (2006): 非负矩阵和遍历性理论的权威综述
  5. Ven15 Venel (2015): 可交换随机博弈的一致值存在性
  6. RSV02 Rosenberg, Solan & Vieille (2002): 盲MDP一致值存在性
  7. CSZ22 Chatterjee, Saona & Ziliotto (2022): POMDP中的有限记忆策略
  8. OB21 Oliu-Barton (2021): 标准随机博弈的新算法

总体评价：这是一篇理论深刻、技术扎实的优秀论文。它在盲随机博弈这一基础但困难的问题上取得了重要突破，通过引入遍历性条件巧妙地平衡了一致值的存在性和可计算性。虽然算法复杂度较高限制了实际应用，但其理论贡献和方法论创新对博弈论、自动机理论和计算复杂性理论都有重要意义。论文的紧致性结果（近似可判定但精确不可判定）特别令人印象深刻，清晰地刻画了问题的计算边界。