arXiv 2606.31769v1 · 发布 2026-06-30

策略优化在未知转移的马尔可夫决策过程中实现数据依赖的遗憾界

Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

AUTHORS Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

EVIDENCE 针对未知转移MDP下策略优化的理论遗憾界分析

SCORE 0.9

CATEGORIES TASK rl

PDF ↗ 2606.31769v1.pdf

GENERATED 2026-07-04 02:30:36 UTC

📝 TLDR

针对转移核未知的表格型在线分段MDP，研究策略优化能否同时获得数据相关遗憾界与对抗-随机两全保证。已有工作仅在已知转移下证明可行，本文构造基于乐观FTRL的新算法，结合新颖的乐观Q函数估计器与数据相关转移奖励项。通过损失预测误差控制估计偏差，识别出不可避免的转移依赖复杂度项，最终在未知转移下同时实现一阶、二阶与路径长度界以及随机情形的polylog(T)遗憾。

🧭 速览

动机

研究表格型MDP在转移核未知时，策略优化能否获得对抗与随机两全的数据相关遗憾界，填补已有工作仅在已知转移下的空白。

方法

基于乐观FTRL框架，设计新的乐观Q函数估计器与数据相关转移奖励项，通过损失预测误差控制估计偏差。

结果

在未知转移下同时获得一阶、二阶、路径长度遗憾界及随机情形的polylog(T)间隙依赖遗憾，并识别出不可避免的转移依赖复杂度项。

结论

首次证明策略优化在未知转移下也能达到数据相关的最佳两全遗憾保证，揭示估计转移核的固有复杂度代价。

📊 论文图表(共 6 张)

展开查看 6 张图

TL;DR

本文研究了转移核未知的表格型在线片段MDP中策略优化能否同时获得数据依赖的遗憾界与对抗-随机两全保证。通过设计新颖的乐观Q函数估计器和数据依赖的转移奖励项，结合基于乐观FTRL的算法框架，论文首次在未知转移条件下证明了策略优化可同时实现一阶、二阶、路径长度界以及随机环境下的polylog(T)遗憾，同时识别了不可避免的转移依赖复杂度项。

研究背景与动机

在强化学习的理论研究中，在线马尔可夫决策过程（MDP）一直是一个核心研究场景。考虑一个有限视野的表格型在线片段MDP，智能体在每个回合需要与未知环境交互，损失序列可能由对抗性对手生成。智能体的目标是找到能够最小化累积遗憾的策略——即相对于最优固定策略的累积损失差异。

近年来，策略优化（policy optimization）方法因其实现简洁和理论可解释性而受到广泛关注。Dann等（2023）和Li等（2026）的工作已经证明，当转移核已知时，策略优化能够自适应地获得多种数据依赖的遗憾界：包括一阶界（依赖于累积损失的大小）、二阶界（依赖于损失方差）和路径长度界（依赖于累积值函数的变化）。更重要的是，这些方法能够实现所谓的"对抗-随机两全"（best-of-both-worlds）保证——在对抗性损失下获得最优的 $\tilde{O} (T)$ 遗憾，在随机环境中进一步改进到polylog(T)级别。

然而，这些结果都依赖于一个关键假设：转移核是已知的。在实际应用中，环境的转移 dynamics 通常是未知的，需要从交互数据中学习。当转移核未知时，是否仍能通过纯策略优化的方式获得这些精细的数据依赖保证？这个问题直到这篇论文发表前都是一个开放的理论问题。

值得注意的是，虽然Lee等（2020）已经在未知转移条件下获得了一阶遗憾界，但他们采用的是基于占用测度的全局优化方法，而非策略优化范式。策略优化的优势在于其自然地将策略空间限制在可行策略集合内，理论上应该能够获得更紧的界，但从未在未知转移条件下被证明可行。这促使本文作者去探索这一理论空白，并最终给出了肯定的答案。

方法

本文的核心贡献在于开发了一种基于乐观追随正则化领导者（Optimistic Follow-the-Regularized-Leader, OFTRL）的新算法，能够在转移核完全未知的条件下同时实现多种数据依赖保证。这背后的核心挑战在于：如何在缺乏环境模型的情况下，既保证对未知转移的有效探索，又能在损失预测误差较大时自适应地收紧策略？

乐观FTRL框架继承了Li等（2026）在已知转移条件下的设计思路。算法在每个时间步对每个状态独立执行多臂赌博机优化，目标是最小化一个包含Q函数估计、膨胀探索奖励和策略价值预测的组合损失函数。策略更新通过带log-barrier正则化的优化问题实现，这种设计天然保证了策略的探索性——在缺乏数据的状态-动作对上，正则化项会阻止算法过早地分配零概率。

新颖的Q函数估计器是本文最关键的技术创新。作者设计了两套互补的估计器，分别适用于全信息设置和赌博机设置。在全信息设置中，估计器选取使当前策略Q值最小的置信集内转移核；在赌博机设置中，估计器则结合了当前回合的即时损失反馈与基于历史数据的预测。具体而言，赌博机估计器包含一个核心项（基于最优转移核和当前策略的价值估计）、一个偏差修正项（利用损失预测误差来控制估计偏差）和一个转移奖励项（用于处理转移估计的不确定性）。

数据依赖的转移奖励项是整个设计的精髓所在。这一项通过损失预测误差来控制估计器的偏差，其精妙之处在于将不依赖于预测误差的部分按照 $ρ_{t} (s)^{2}$ 进行缩放，而非传统的 $ρ_{t} (s)$ 。这种设计的效果是双重的：一方面，当损失预测准确时，这一项可以非常小，从而允许算法更激进地利用数据；另一方面，在最坏情形下（预测完全失败），该项的贡献仅为polylog(T)级别，不会导致遗憾界退化到 $\tilde{O} (T)$ 。

损失预测序列的设计进一步强化了算法的数据依赖特性。算法维护一个指数加权的损失预测 $m_{t}$ ，当某个状态-动作对被访问时，预测会向实际损失方向更新。通过精心选择遗忘因子和更新机制， $m_{t}$ 能够以指数速度收敛到最优固定预测，从而使得预测误差项在长期平均意义上趋于零。

转移依赖复杂度项是本文揭示的一个重要发现。通过深入分析，作者证明了存在一个不可避免的转移依赖复杂度项，其形式为：

Q_{π^{1 : T}}^{trans} (ℓ) := \forall t, s, a : ∣ ϕ_{t} (s, a) ∣ = ℓ_{t} (s, a) sup t = 1 \sum T s, a \sum q^{π_{t}} (s, a) Var_{s^{'} \sim P (\cdot ∣ s, a)} [V^{π_{t}} (s^{'}; ϕ_{t})]

这一项度量了算法所访问策略的分布与真实转移核相互作用产生的固有复杂度。最关键的是，作者证明了这一项满足自界性质：其期望值可以由一阶损失项和遗憾本身联合上界，这意味着在"好"的情形下（策略变化平缓或损失可预测），这一复杂度项会自然变小。

实验与结果

本文是一篇纯理论工作，所有结果均通过严格的数学推导证明。论文提供了详尽的上界分析和配套的下界证明（Proposition 4.3），后者通过构造一个时不变但转移结构特殊的MDP实例，证明了转移依赖复杂度项是任何算法都必须承受的固有代价。

论文给出了两个核心定理，分别对应全信息设置和赌博机设置。全信息设置下的遗憾界为：

Reg_{T} (π) ≲ H^{2} S A lo g^{2} (T) \cdot min {L (π), H T - L (π), Q_{\infty}, V_{1}} + S^{2} A lo g^{2} (T) E [Q_{π^{1 : T}}^{trans} (ℓ)] + H S^{3/2} A^{3/2} lo g^{2} (T)

这一结果有几点值得注意。首先，第一项中的 $H^{2} S A$ 去除了先前策略优化算法中的额外 $H$ 因子，首次在全信息设置下达到与占用测度方法相当的 $\tilde{O} (H^{2} S^{2} A T)$ 最坏情形率。其次，转移依赖复杂度项以 $S^{2} A lo g^{2} (T)$ 的形式出现，这是不可避免的。第三，在随机环境下，当最小间隙 $Δ_{m i n}$ 有界时，遗憾可以进一步改进到 $\tilde{O} (H^{2} S^{2} A lo g^{2} (T) / Δ_{m i n})$ 的gap-dependent级别。

赌博机设置下的遗憾界与全信息设置保持相同的结构，但最坏情形率从 $\tilde{O} (H^{2} S^{2} A T)$ 退化到 $\tilde{O} (H^{4} S^{2} A T)$ ，这是由于缺乏全信息反馈所导致的额外估计难度。在随机环境下，gap-dependent项则呈现为 $\tilde{O} (H^{2} S^{4} A lo g^{2} (T) / Δ_{m i n})$ ，与全信息设置相比多了 $S^{2} / H^{2}$ 的因子。

下界证明通过构造一个具有特殊转移结构的MDP，展示了即使在最有利的数据条件下（ $Q_{\infty} = V_{1} = 0$ ），任何算法仍必须承受 $Ω (H^{2} S A T)$ 的遗憾。这一下界与全信息设置的上界匹配，说明在该设置下算法已经接近最优。

讨论与可借鉴点

本文解决了Dann等（2023）提出的开放问题，首次在转移核未知的条件下证明了纯策略优化方法可以实现精细的数据依赖遗憾界。这一结果不仅是技术层面的突破，更揭示了策略优化与模型学习方法在信息论复杂度上的本质差异。

从方法论角度看，本文最重要的借鉴点在于如何设计数据依赖的估计器偏差控制机制。传统方法往往通过方差项或置信半径来上界估计偏差，但这会导致在最坏情形下的 $\tilde{O} (T)$ 增长。本文通过将估计偏差约化为损失预测误差，并精心设计预测误差的缩放方式，成功实现了当预测准确时偏差项趋于零、当预测失败时偏差项仍保持polylog(T)级别的效果。这一设计思路可以推广到其他具有预测结构的在线学习问题中。

转移依赖复杂度项的识别是本文的另一个重要贡献。这一发现揭示了在未知转移MDP中学习的固有复杂度结构：即使损失序列完全可预测，算法仍然必须为估计转移核付出代价。这一项通过与累积值函数方差的关系，与一阶损失项和遗憾本身建立了自界联系，从而在"好"的情形下自动收紧。

然而，本文也存在若干局限性。首先，赌博机设置下的gap-dependent界与全信息设置存在 $S^{2} / H^{2}$ 的差距，这是否是最优的仍是开放问题。其次，本文限制于表格型MDP，无法直接扩展到使用函数逼近的大规模问题。第三，算法中虚拟回合机制的设计增加了实现的复杂度。最后，gap-dependent polylog(T)界与最小最大下界之间仍存在对数因子级别的差距，是否可以完全消除尚不清楚。

对于未来研究而言，几个方向值得关注：如何将数据依赖保证扩展到聚合反馈设置？如何设计方差感知的gap-dependent界以进一步改进随机环境下的 regret？转移依赖复杂度项在函数逼近设置下会呈现何种形式？这些问题都为后续研究提供了丰富的探索空间。

摘要

我们研究在线片段式表格马尔可夫决策过程中的策略优化问题，其转移核未知，目标是获得兼顾两全的保证以及数据依赖的遗憾界。近期的工作（Dann 等，2023；Li 等，2026）表明，策略优化能够针对对抗性损失和随机性损失自适应地获得一阶、二阶以及路径长度遗憾界，但这些结果仅在转移已知的前提下成立。当转移核未知时，策略优化是否仍能获得此类数据依赖的保证仍是一个未解决的问题。我们通过开发一种基于乐观的追随正则化领导者（follow-the-regularized-leader）的新算法解决了这一问题，该算法在未知转移的情况下实现了上述保证。其关键要素在于一种新颖的乐观 Q 函数估计器设计，以及一个数据依赖的转移奖励项，该奖励项通过损失预测误差来控制估计器的偏差。进一步的分析揭示了一个不可避免的转移依赖复杂度项，它刻画了估计转移核的固有代价。因此，我们在同时实现随机环境下与间隙（gap）相关的 polylog(T) 遗憾的同时，获得了一阶、二阶以及路径长度遗憾界，其中包含转移依赖的复杂度项。

Abstract

We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic $Q$ -function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent $polylog (T)$ regret in the stochastic regime.

论文详细总结（自动生成）

论文总结：策略优化在未知转移 MDP 中实现数据依赖的遗憾界

1. 核心问题与整体含义

1.1 研究背景

本文研究在线片段式表格 MDP（episodic tabular MDP）中的策略优化（policy optimization）问题，其中转移核 $P$ 固定但未知，且损失序列可能对抗性生成。目标是同时获得：

对抗-随机两全（best-of-both-worlds） 保证
数据依赖（data-dependent） 的遗憾界

1.2 现有工作的空白

Dann 等（2023） 和 Li 等（2026） 已证明策略优化在已知转移下能实现一阶、二阶、路径长度界
Lee 等（2020） 在未知转移下获得了一阶界，但仅通过占用测度全局优化，而非策略优化
开放问题：策略优化在未知转移下能否同时获得三类数据依赖保证 + 两全保证？

1.3 本文解决的核心问题

策略优化 未知转移 一阶 + 二阶 + 路径长度 + gap-dependent polylog (T) 界

并识别出不可避免的转移依赖复杂度项 $Q_{π^{1 : T}}^{trans} (ℓ)$ 。

2. 方法论

2.1 核心框架：乐观 FTRL（OFTRL）

基于 Li 等（2026）的 OFTRL 策略优化框架，对每个状态 $s$ 独立执行多臂赌博机：

π_{t} (\cdot ∣ s) = ar g π (\cdot ∣ s) \in Δ (A) min {⟨ π (\cdot ∣ s), τ = 1 \sum t - 1 (\hat{Q}_{τ} (s, \cdot) - B_{τ} (s, \cdot)) + Q^{P_{t}^{m}, π_{t}} (s, \cdot; m_{t}) ⟩ + ψ_{t} (π (\cdot ∣ s))}

其中：

$\hat{Q}_{τ}$ ：Q 函数估计器
$B_{τ}$ ：膨胀探索奖励（dilated exploration bonus）
$Q^{P_{t}^{m}, π_{t}}$ ：乐观预测
$ψ_{t} (π (\cdot ∣ s)) = \sum_{a} \frac{1}{η _{t} ( s , a )} lo g \frac{1}{π ( a ∣ s )}$ ：log-barrier 正则化器

2.2 关键技术 1：全信息 Q 函数估计器

选取 $P^{ℓ_{t}} \in ar g min_{\hat{P} \in P_{t}} Q^{\hat{P}, π_{t}} (s, a; ℓ_{t})$ ，设置：

\hat{Q}_{t} (s, a) = Q^{P^{ℓ_{t}}, π_{t}} (s, a; ℓ_{t})

2.3 关键技术 2：赌博机反馈 Q 函数估计器（核心创新）

\hat{Q}_{t} (s, a) = Q^{P_{t}^{m}, π_{t}} (s, a; m_{t}) + \frac{I _{t} ( s , a ) ( L _{t, h} ( s ) - M _{t, h} ( s ))}{q _{t} ( s ) π _{t} ( a ∣ s ) Y _{t}} - C_{t} (s, a) Y_{t}

数据依赖的转移奖励项：

c_{t} (s, a) = \frac{ρ _{t} ( s ) I _{t} ( s , a ) D _{t, h} ( s )}{q _{t} ( s ) π _{t} ( a ∣ s )} + ρ_{t} (s)^{2} H

C_{t} (s, a) = c_{t} (s, a) + \hat{P} \in P_{t} max E_{s^{'} \sim \hat{P}, a^{'} \sim π_{t}} [c_{t} (s^{'}, a^{'}) + C_{t} (s^{'}, a^{'})]

关键设计思想：与预测误差无关的部分按 $ρ_{t} (s)^{2}$ （而非 $ρ_{t} (s)$ ）缩放，使得最坏情形贡献仅为 polylog( $T$ )，数据依赖项由预测误差 $ℓ_{t} - m_{t}$ 控制。

2.4 损失预测序列

m_{t + 1} (s, a) = {(1 - ξ) m_{t} (s, a) + ξ ℓ_{t} (s, a), m_{t} (s, a), I_{t} (s, a) = 1 I_{t} (s, a) = 0

2.5 虚拟回合机制

当 $max_{s, a} η_{t} (s, a) / q_{t} (s) > 1/ (50 H^{3} S^{3} A)$ 时插入虚拟回合，仅更新学习率，使用零损失。虚拟回合数为 $O (H S A lo g^{2} T)$ ，影响为低阶项。

2.6 复杂度度量

转移依赖复杂度项：

Q_{π^{1 : T}}^{trans} (ℓ) := \forall t, s, a : ∣ ϕ_{t} (s, a) ∣ = ℓ_{t} (s, a) sup t = 1 \sum T s, a \sum q^{π_{t}} (s, a) Var_{s^{'} \sim P (\cdot ∣ s, a)} [V^{π_{t}} (s^{'}; ϕ_{t})]

自界（self-bounding）关系：

E [Q_{π^{1 : T}}^{trans} (ℓ)] \leq H (L (π) + Reg_{T} (π))

2.7 关键技术 3：偏差分解

将遗憾分解为三项：

reg：OFTRL 的 regret 项
bias：估计器偏差项
error：使用 $P^{m_{t}}$ 替代真实 $P$ 的误差项

核心引理（Lemma 3.1）：将 regret 约化为上界 $3 \sum V^{P^{B_{t}}, π_{t}} (s_{0}; b_{t})$ 。

3. 实验设计

本文为纯理论论文，没有进行实验验证。所有结果均通过数学分析得出。

4. 资源与算力

不适用。本文为理论分析论文，未使用任何计算资源，无需 GPU 训练。所有结果通过数学推导得到。

5. 实验数量与充分性

实验数量：0 组（纯理论工作）
验证方式：通过理论证明与下界证明（Proposition 4.3）支撑结果的合理性
与现有文献对比：表 1 系统比较了与 Luo 等（2021）、Dann 等（2023）、Li 等（2026）等的遗憾界

6. 主要结论与发现

6.1 主要定理

定理 4.1（全信息设置）：对任意比较策略 $π$ ，

Reg_{T} (π) ≲ H^{2} S A lo g^{2} (T) \cdot min {L (π), H T - L (π), Q_{\infty}, V_{1}} + S^{2} A lo g^{2} (T) E [Q_{π^{1 : T}}^{trans} (ℓ)] + H S^{3/2} A^{3/2} lo g^{2} (T)

随机设置： $Reg_{T} (π) ≲ U + U C + H S^{3/2} A^{3/2} lo g^{2} (T)$ ，其中 $U = H^{2} S^{2} A lo g^{2} (T) / Δ_{m i n}$ 。

定理 4.2（赌博机设置）：

Reg_{T} (π) ≲ H^{3} S^{2} A lo g^{2} (T) \cdot min {L (π), H T - L (π), Q_{\infty}, V_{1}} + S^{2} A lo g^{2} (T) E [Q_{π^{1 : T}}^{trans} (ℓ)] + H^{3/2} S^{7/2} A^{3/2} lo g^{2} (T)

随机设置： $U = H^{2} S^{4} A lo g^{2} (T) / Δ_{m i n}$ 。

6.2 关键发现

1. 首次在未知转移下证明策略优化可同时获得三类数据依赖界 + 两全保证

2. 识别不可避免的转移依赖复杂度项 $Q^{trans}$

3. 全信息设置下，去除了 Q 函数估计的额外 $H$ 因子，首次达到 $\tilde{O} (H^{2} S^{2} A T)$ 的最坏情形率（与占用测度方法相当）

4. 赌博机设置下达到 $\tilde{O} (H^{4} S^{2} A T)$ ，与 Dann 等（2023）相当

6.3 下界（Proposition 4.3）

存在时不变损失序列使得 $Q_{\infty} = V_{1} = 0$ ，但任何算法仍承受 $Ω (H^{2} S A T)$ 遗憾，说明转移依赖项不可避免。

7. 优点

7.1 方法论创新

新颖的乐观 Q 函数估计器设计，将估计器偏差约化为损失预测误差
数据依赖的转移奖励项 $c_{t} (s, a)$ 按 $ρ_{t} (s)^{2}$ 缩放，避免了最坏情形下的 $\tilde{O} (T)$ 退化
统一框架：同一算法模板适用于全信息和赌博机两种反馈设置

7.2 理论贡献

解决了 Dann 等（2023）提出的开放问题
在全信息设置下消除了先前策略优化算法中的额外 $H$ 因子
引入并系统分析了转移依赖复杂度项
下界证明证实该复杂度项的必要性

7.3 表达清晰度

提供详细的技术引理和完整的证明附录
通过具体示例（Appendix B.2）阐明 $Q^{trans}$ 的含义
表 1 清晰展示与现有工作的对比

8. 不足与局限

8.1 理论局限

赌博机设置中随机情形存在额外因子 $S^{2} / H^{2}$ ：gap-dependent 项为 $H^{2} S^{4} A lo g^{2} (T) / Δ_{m i n}$ ，而 Dann 等（2023）对应项为 $H^{2} S^{2} A lo g^{2} (T) / Δ_{m i n}$ ，是否可改进仍是开放问题
赌博机设置中数据依赖界存在 $H$ 因子差距： $H^{3} S^{2} A$ vs 占用测度方法的 $H^{2} S A$ ，归因于 Q 函数估计
最小最大下界 $Ω (H^{2} S A T)$ 与当前最好上界之间仍存在差距

8.2 方法适用性

限于表格型 MDP，无法直接扩展到大规模或函数逼近设置
要求层级（layered）MDP 结构假设
$T \geq max {2, S, A}$ 的假设非本质但需满足

8.3 验证不足

纯理论工作，无实验验证
未在更广泛的设置（如对抗转移、聚合反馈）下验证
留给未来工作的方向：方差感知的 gap-dependent 界、聚合反馈下的数据依赖保证

8.4 表达局限

部分常数（如 $ξ = 1/4$ 、 $η_{1} = 1/ (12 H^{3})$ ）的选择缺乏直观解释
虚拟回合机制的引入增加了算法的实现复杂度

（完）

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。