ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning¶

会议: AAAI 2026 arXiv: 2508.03768 代码: 无领域: 强化学习/分布鲁棒优化 关键词: Distributionally Robust RL, Online Learning, f-divergence, Minimax Optimal, Sample Complexity

一句话总结¶

本文研究在线分布鲁棒强化学习，提出了基于 $f$-散度不确定性集的 RVI-$f$ 算法，在 $\chi^2$ 和 KL 散度下均实现了近似极小极大最优的遗憾界，且不依赖任何结构性假设。

研究背景与动机¶

领域现状¶

分布鲁棒强化学习（DRRL）通过在以训练环境为中心的不确定性集上优化最坏情况性能，为 sim-to-real 差距提供了有原则的解决方案。现有研究已在生成模型和离线数据访问设定下取得了丰富成果。

现有痛点¶

现有 DRRL 方法要么依赖生成模型（可任意查询状态-动作对），要么假设离线数据集具有足够覆盖。这些假设在实际部署中难以满足——真实环境未知且数据稀疏，智能体需要自行探索环境。

核心矛盾¶

在线 DRRL 面临信息缺口问题：最坏情况环境覆盖的状态可能在训练过程中从未被访问过，但智能体仍需在这些未知状态下可靠地行动。这导致训练数据分布与评估目标（鲁棒值函数）之间存在固有不匹配。

本文要解决什么¶

在不依赖 fail-state 结构、覆盖率假设或消失最小值假设的条件下，设计具有近最优样本复杂度的在线 DRRL 算法。

切入角度¶

聚焦于 $\chi^2$ 和 KL 两种 $f$-散度不确定性集，利用这些散度的光滑几何性质来缓解信息缺口问题（相比 TV 散度更温和），并通过精心设计的探索奖励实现紧遗憾界。

核心idea一句话¶

通过对鲁棒值函数直接构建置信区间（而非对完整转移动态建模），利用 $f$-散度的对偶表示设计自适应奖励项，实现无结构假设下的近最优在线鲁棒学习。

方法详解¶

整体框架¶

RVI-$f$（Robust Value Iteration with $f$-Divergence）是一个基于模型的元算法，每个 episode $k$ 分三阶段执行： 1. 名义转移估计：用历史数据估计训练环境的经验转移核 $\hat{P}_h^k$ 2. 乐观鲁棒估计：通过乐观上界构建鲁棒值函数的置信区间，确定本轮策略 3. 策略执行与数据收集：执行策略、观察奖励和状态转移、更新数据集

关键设计一：$f$-散度不确定性集的对偶表示¶

做什么：为鲁棒期望值提供可计算的等价形式。

核心思路：利用凸对偶将鲁棒期望转化为一维优化：

对于 $\chi^2$ 散度（$f(t) = (t-1)^2$）： $$\mathbb{E}_{\mathcal{U}_h^\sigma(s,a)}[V] = \sup_{\eta \in [0,H]} \left\{ -\sqrt{\sigma \text{Var}_{P_h^\star(\cdot|s,a)}((\eta - V)_+)} + [\mathbb{P}_h^\star(V - \eta)_+](s,a) \right\}$$

对于 KL 散度（$f(t) = t \log t$）： $$\mathbb{E}_{\mathcal{U}_h^\sigma(s,a)}[V] = \sup_{\eta} \left\{ -\eta \log([\mathbb{P}_h^\star(\exp\{-V/\eta\})](s,a)) - \eta\sigma \right\}$$

设计动机：对偶表示将高维分布优化转化为标量优化，使得鲁棒 Bellman 方程可以高效求解。同时，$\chi^2$ 和 KL 散度的光滑性使得单个罕见状态的影响被散度的几何结构调节，缓解了 TV 散度下的信息缺口问题。

关键设计二：乐观鲁棒估计与奖励项¶

做什么：构建鲁棒值函数的置信区间 $[\underline{Q}_h^k, \overline{Q}_h^k]$，确保真实鲁棒最优值函数以高概率落入其中。

核心思路： $$\overline{Q}_h^k(s,a) = \min\{\overline{R}_h^k(s,a) + B_{k,h}^f(s,a),\; H\}$$

其中 $\overline{R}_h^k$ 是用估计模型计算的鲁棒 Bellman 算子，$B_{k,h}^f$ 是关键的探索奖励项。

对于 $\chi^2$ 散度，奖励项为： $$B_{k,h}^{\chi^2}(s,a) = \sqrt{\frac{\sigma c_1 L \text{Var}_{\hat{P}_h^k}\left[\frac{\overline{V}_{h+1}^k + \underline{V}_{h+1}^k}{2}\right]}{N_h^k(s,a) \vee 1}} + \frac{2\sqrt{\sigma}\mathbb{E}_{\hat{P}_h^k}[\overline{V}_{h+1}^k - \underline{V}_{h+1}^k]}{H} + \text{lower order terms}$$

设计动机：奖励项由三部分组成——方差项（反映估计不确定性）、值域宽度项（反映置信区间质量）和低阶修正项。方差加权的设计使得奖励在频繁访问的状态-动作对上自然收缩，实现紧的遗憾界。

关键设计三：下界构造¶

做什么：通过构造困难实例证明在线 DRRL 的极小极大下界。

核心思路：构造一族困难 RMDP $\{\mathcal{M}_1, \dots, \mathcal{M}_S\}$，每个 $\mathcal{M}_i$ 有 3 个状态、$A$ 个动作、horizon $H$。所有 MDP 共享名义转移，但在 $s_2$ 处不同动作的奖励不同。利用 Bretagnolle-Huber 不等式建立任意算法在这族实例上的遗憾下界。

设计动机：通过精心选择 $\mu^\star = \sqrt{c'A/(SKp)}$ 和最坏情况转移核，使得下界在所有关键参数上与上界匹配。

损失函数¶

优化目标为最小化累积鲁棒遗憾： $$\text{Regret}(K) = \sum_{k=1}^K [V_1^{\star,\sigma}(s_1^k) - V_1^{\pi^k,\sigma}(s_1^k)]$$

实验关键数据¶

主实验对比¶

方法	设定假设	$\chi^2$ Regret	KL Regret
TV-OPROVI	消失最小值	-	-
TV/χ²/KL-ORBIT	覆盖率比 $C_{vr}$	$\tilde{O}(\sqrt{C_{vr}H^4S^3AK})$	额外 $S/(\sigma P_{\min}^\star)$ 因子
RVI-χ² (ours)	无假设	$\tilde{O}(\sqrt{H^4(1+\sigma)SAK})$	-
RVI-KL (ours)	无假设	-	$\tilde{O}(\sqrt{H^4 e^{2H^2}SAK/(P_{\min}^\star \sigma^2)})$

下界匹配性¶

不确定性集	上界	下界	Gap
$\chi^2$	$\tilde{O}(\sqrt{H^4(1+\sigma)SAK})$	$\Omega(\sqrt{H^4(1+\sigma)SAK})$	对数因子
KL	$\tilde{O}(\sqrt{H^4 e^{2H^2}SAK/(P_{\min}^\star\sigma^2)})$	$\Omega(\sqrt{H^4SAK/(P_{\min}^\star\sigma^2)})$	$H$ 依赖

关键发现¶

$\chi^2$ 散度下达到极小极大最优（对数因子内），这是在线 DRRL 中首个无结构假设的最优结果
KL 散度下的指数 $e^{2H^2}$ 不是分析瑕疵，而是 KL 不确定性集几何的固有代价
在 Gambler's Problem 和 Frozen Lake 实验中，方法在分布偏移显著时一致提升最坏情况性能
样本复杂度 $\tilde{O}(H^5(1+\sigma)SA/\varepsilon^2)$ 与生成模型设定的已知结果一致

亮点与洞察¶

首个无结构假设的近最优在线 DRRL 算法：不需要 fail-state、覆盖率比或消失最小值假设
统一的元算法框架：RVI-$f$ 可适配不同 $f$-散度，展现了框架的通用性
紧的极小极大下界：首次为在线设定建立信息论下界，填补了理论空白
深刻的洞察：$\chi^2$ 和 KL 散度的光滑性自然缓解了 TV 散度下需要额外假设才能解决的信息缺口问题

局限性/可改进方向¶

KL 散度下上下界在 $H$ 依赖上仍有差距（$e^{2H^2}$ vs 无指数项）
算法是基于模型的（model-based），需要存储转移核估计，内存开销为 $O(S^2AH)$
仅考虑了表格型 MDP，未扩展到函数近似设定
实验规模较小（Gambler's Problem 和 Frozen Lake），缺少大规模环境验证
KL 散度下需要 $P_{\min}^\star > 0$ 假设，对于稀疏转移环境限制较大
$\sigma$ 很小时，鲁棒界可能相对非鲁棒情况显得松散

评分¶

⭐⭐⭐⭐⭐ (5/5)

优势：理论贡献突出（首次无假设+极小极大最优），算法设计优雅，统一框架适配多种散度，上下界分析完整。

不足：实验部分偏弱，实际应用场景展示不足。