2025-11-20T13:28:14.804433

Towards Blackwell Optimality: Bellman Optimality Is All You Can Get

Boone, Tuynman
Although average gain optimality is a commonly adopted performance measure in Markov Decision Processes (MDPs), it is often too asymptotic. Further incorporating measures of immediate losses leads to the hierarchy of bias optimalities, all the way up to Blackwell optimality. In this paper, we investigate the problem of identifying policies of such optimality orders. To that end, for each order, we construct a learning algorithm with vanishing probability of error. Furthermore, we characterize the class of MDPs for which identification algorithms can stop in finite time. That class corresponds to the MDPs with a unique Bellman optimal policy, and does not depend on the optimality order considered. Lastly, we provide a tractable stopping rule that when coupled to our learning algorithm triggers in finite time whenever it is possible to do so.
academic

Towards Blackwell Optimality: Bellman Optimality Is All You Can Get

基本信息

  • 论文ID: 2510.13476
  • 标题: Towards Blackwell Optimality: Bellman Optimality Is All You Can Get
  • 作者: Victor Boone (Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG & IRIT, Université de Toulouse), Adrienne Tuynman (Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL)
  • 分类: cs.LG (Machine Learning)
  • 发表时间: 2025年10月15日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.13476v1

摘要

虽然平均增益最优性是马尔可夫决策过程(MDPs)中常用的性能度量，但它往往过于渐近。进一步结合即时损失的度量导致了偏差最优性的层次结构，一直到Blackwell最优性。本文研究识别此类最优性阶数策略的问题。为此，对于每个阶数，我们构造了一个具有消失错误概率的学习算法。此外，我们刻画了识别算法可以在有限时间内停止的MDP类别。该类别对应于具有唯一Bellman最优策略的MDP，且不依赖于所考虑的最优性阶数。最后，我们提供了一个易处理的停止规则，当与我们的学习算法耦合时，只要可能就会在有限时间内触发。

研究背景与动机

问题定义

本文研究的核心问题是在马尔可夫决策过程中学习高阶最优策略的可识别性问题。具体而言：

  1. 传统平均增益最优性的局限性：在MDP中，传统的平均增益最优性只关注长期渐近性能，忽略了短期即时奖励的重要性。
  2. 高阶最优性的层次结构：从增益最优性到偏差最优性，再到Blackwell最优性，形成了一个完整的最优性层次结构，每个层次都考虑了更细致的性能差异。
  3. 学习难题：论文通过一个简单而深刻的例子（Figure 1）展示了即使在最简单的情况下，学习高阶最优策略也面临着根本性困难。

研究动机

论文的核心动机源于一个重要观察：即使在只有单个未知参数的简单MDP中，学习高阶最优策略也可能是不可能的。这个看似矛盾的现象揭示了高阶最优性学习的本质困难。

现有方法的局限性

  1. 标准学习方法失效：传统的经验最优策略选择在高阶最优性下不再适用
  2. 统计测试的局限：无法通过统计测试确定参数的精确值（如θ=0）
  3. 不连续性问题：最优策略集合在参数空间中的不连续性导致学习困难

核心贡献

  1. 构造了一致性算法HOPE：对于每个最优性阶数n≥-1，提出了Higher Order Policy iteration Epsilonized (HOPE)算法，该算法具有消失的错误概率。
  2. 完全刻画了非退化MDP类别：证明了MDP是非退化的（即识别算法可以在有限时间内停止）当且仅当它具有唯一的Bellman最优策略。
  3. 退化性崩塌定理：证明了所有最优性阶数（从增益最优到Blackwell最优）的非退化MDP类别完全相同，这是一个令人惊讶的结果。
  4. 提供了可计算的停止规则：给出了一个易处理的停止规则，使得HOPE算法在可能的情况下能够在有限时间内停止。

方法详解

任务定义

输入：未知的通信MDP M = (Z, ν, p)，其中Z是状态-动作对空间，ν是奖励函数，p是转移核 输出：n阶最优策略π ∈ Π*_n(M) 目标：构造识别算法使得推荐策略的错误概率趋于0

核心算法架构

HOPE算法 (Algorithm 1)

输入：期望的最优性阶数 n ≥ -1
初始化：t ← 0
循环：
    1. 构造经验MDP M̂_t
    2. 设置 ε ← t^(-1/4)
    3. 计算 ∏_s A_n(s) ← HOPI_{n,ε}(M̂_t)
    4. 推荐 ∏_s A_n(s) 中的任意策略
    5. 均匀采样动作，观察奖励和下一状态
    6. t ← t + 1

HOPI算法的核心思想

HOPI是高阶策略迭代的"epsilon化"版本，关键创新在于：

  1. 软argmax操作：将精确的Bellman方程约束 Δ^π_m(s,a) = 0 松弛为 Δ^π_m(s,a) ≤ ε
  2. 两阶段策略改进：
    • 第一阶段：在已知m-1阶最优的动作中寻找m+1阶改进
    • 第二阶段：进一步细化到m+2阶最优性
  3. 渐进精度控制：选择 ε_t = t^(-1/4) 确保算法的一致性

技术创新点

1. 噪声下的策略迭代

传统策略迭代要求精确满足Bellman方程，但在学习环境下这是不可能的。HOPI通过引入松弛参数ε，使得算法能够在噪声环境下正确工作。

2. 破碎技术 (Shattering)

Proposition 5：对于任何单链Bellman最优策略π和精度ε > 0，存在M' ∈ M使得d_∞(M,M') < ε且π是M'的唯一增益最优策略。

这一技术通过两步实现：

  • 首先通过惩罚非最优动作使π成为唯一Bellman最优策略
  • 然后通过遍历变换使π成为唯一增益最优策略

3. 停止规则设计

定义阈值函数：

β(M) := min{d_min(Δ*)/((1+4α)(2+sp(b*))), 1/α}

其中α是最坏到达时间，该阈值提供了邻域半径的精确度量。

理论结果

主要定理

定理1 (一致性)

对于所有n ≥ -1，HOPE(n)算法对于Π*_n是一致的。

定理2 (非退化性刻画)

设n ≥ -1。MDP M相对于Π*_n(M)是非退化的当且仅当M具有唯一的Bellman最优策略。

推论3 (退化性崩塌)

相对于Π_{-1}, Π0, Π_1, ..., Π∞的退化模型集合完全相同。

证明思路

非退化性的必要性 (定理4)

如果M是非退化的，则存在策略π ∈ Π*(M)在M的邻域内保持最优。证明使用了算法决策的连续性。

充分性 (定理10-11)

通过构造显式的停止规则和置信区间，证明具有唯一Bellman最优策略的MDP确实是非退化的。

实验设置与结果

理论验证

论文主要是理论工作，通过严格的数学证明验证了所有主要结果。关键的验证包括：

  1. 算法正确性：证明HOPI在无噪声情况下返回正确的最优策略集合
  2. 一致性保证：证明HOPE算法的错误概率确实趋于0
  3. 停止规则有效性：证明提出的停止规则确实能在有限时间内触发

复杂性分析

  • 时间复杂度：判断Bellman最优策略唯一性的时间复杂度为O(|Z| + |S|^4)
  • 样本复杂度：虽然论文没有给出精确的样本复杂度界，但证明了在非退化情况下算法必定收敛

相关工作

最优臂识别

与多臂赌博机中的最优臂识别问题相关，但MDP设置下的状态依赖性使问题更加复杂。

平均奖励强化学习

近年来在(ε,δ)-PAC设置下识别增益最优策略的工作，但这些工作主要关注近似最优性而非精确最优性。

Blackwell最优性计算

Grand-Clément和Petrik (2023)等人基于折扣因子的历史定义研究Blackwell最优策略的计算复杂性。

确定性MDP中的相关结果

Boone和Gaujal (2023)在确定性转移MDP中研究了Blackwell最优策略的可学习性，本文将其推广到随机情况。

结论与讨论

主要结论

  1. Bellman最优性是根本限制：所有高阶最优性的可学习性都归结为Bellman最优性的唯一性
  2. 退化性的普遍性：不同最优性阶数的退化MDP类别完全相同
  3. 算法的存在性：尽管面临困难，一致性算法确实存在

局限性

  1. PAC设置的缺失：论文主要关注精确最优性，未涉及近似最优性的学习
  2. 样本复杂度界：没有提供精确的样本复杂度分析
  3. 实际应用：理论结果可能限制了在实际问题中的应用

未来方向

  1. PAC框架扩展：研究近似最优策略的学习
  2. 样本复杂度分析：建立精确的样本复杂度界
  3. 算法优化：改进HOPE算法的实际性能

深度评价

优点

  1. 理论深度：提供了高阶最优性学习问题的完整理论刻画
  2. 结果意外性：退化性崩塌定理是一个令人惊讶且深刻的结果
  3. 技术创新：破碎技术和软argmax策略迭代展现了技术创新性
  4. 写作清晰：论文结构清晰，数学证明严谨

不足

  1. 实用性限制：理论结果表明大多数实际MDP可能是退化的
  2. 计算复杂性：虽然提供了多项式时间算法，但常数可能很大
  3. 实验验证缺失：作为纯理论工作，缺乏实验验证

影响力

  1. 理论贡献：为强化学习理论提供了重要的负面结果
  2. 方法启发：破碎技术可能在其他问题中有应用
  3. 研究方向：为后续研究指明了PAC设置的重要性

适用场景

  1. 理论研究：为强化学习理论研究提供重要参考
  2. 算法设计：为设计实际的策略学习算法提供理论指导
  3. 问题分析：帮助理解MDP结构对学习难度的影响

参考文献

论文引用了强化学习和马尔可夫决策过程领域的重要文献，包括：

  • Puterman (1994): 马尔可夫决策过程的经典教科书
  • Blackwell (1962): Blackwell最优性的原始定义
  • Kaufmann et al. (2016): 最优臂识别的复杂性理论
  • Boone and Gaujal (2023): 确定性MDP中Blackwell最优性的可学习性

这篇论文通过严格的理论分析揭示了强化学习中一个基本而深刻的现象：高阶最优性的学习难度完全由Bellman最优性的结构决定。这一结果不仅具有重要的理论意义，也为实际算法设计提供了重要指导。