Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits

📄 arXiv: 2502.06051 📥 PDF

作者: Qingyue Zhao, Kaixuan Ji, Heyang Zhao, Tong Zhang, Quanquan Gu

分类: cs.LG, cs.AI, math.ST, stat.ML

发布日期: 2026-02-28

💡 一句话要点

提出针对离线策略学习的$f$-散度正则化分析方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 离线强化学习 样本复杂度 f-散度正则化 反KL散度 悲观分析 上下文赌博机 强凸散度

📋 核心要点

  1. 现有的离线强化学习算法在样本复杂度分析上存在不足，尤其是在正则化目标下的具体数据覆盖条件方面。
  2. 论文提出了一种新颖的悲观分析方法，首次在单策略集中性下实现了反KL散度的$ ilde{O}( ext{ε}^{-1})$样本复杂度。
  3. 通过数值实验验证了理论结果，并扩展了对上下文对抗性赌博机的分析，展示了该方法的有效性。

📝 摘要（中文）

许多离线强化学习算法依赖于$f$-散度正则化，但其样本复杂度在正则化目标下的紧密分析仍然缺乏，尤其是在具体数据覆盖条件方面。本文研究了实现$ ilde{ heta}( ext{ε}^{-1})$样本复杂度的确切集中性要求，首次通过新颖的悲观分析方法在单策略集中性下实现了反Kullback-Leibler（KL）散度的$ ilde{O}( ext{ε}^{-1})$样本复杂度，超越了现有的$ ilde{O}( ext{ε}^{-1})$和$ ilde{O}( ext{ε}^{-2})$界限。此外，对于强凸$f$的散度，尽管反KL不属于此类，我们证明了即使没有悲观估计或单策略集中性，仍可实现$ ilde{ heta}( ext{ε}^{-1})$的样本复杂度。我们还通过数值实验验证了理论结果，并将分析扩展到上下文对抗性赌博机。

🔬 方法详解

问题定义：本文解决了离线强化学习中样本复杂度分析不足的问题，特别是在$f$-散度正则化下的具体数据覆盖条件缺乏紧密分析。

核心思路：通过引入悲观分析方法，论文在单策略集中性下首次实现了反KL散度的$ ilde{O}( ext{ε}^{-1})$样本复杂度，突破了现有的界限。

技术框架：研究框架包括对样本复杂度的理论分析、悲观估计的应用以及数值实验的验证，重点关注反KL散度和强凸散度的特性。

关键创新：最重要的创新在于首次在单策略集中性下实现了反KL散度的$ ilde{O}( ext{ε}^{-1})$样本复杂度，并提出了近似匹配的下界，强调了单策略集中性对样本复杂度的乘法依赖性。

关键设计：论文中设计了新的悲观估计方法，并对样本复杂度的参数设置进行了详细分析，确保了理论结果的有效性和实用性。

📊 实验亮点

实验结果表明，使用新提出的悲观分析方法，反KL散度在单策略集中性下的样本复杂度达到了$ ilde{O}( ext{ε}^{-1})$，相比于现有方法的$ ilde{O}( ext{ε}^{-2})$，提升了样本效率，验证了理论分析的有效性。

🎯 应用场景

该研究的潜在应用领域包括在线广告推荐、个性化内容推荐和医疗决策支持等。通过提高离线策略学习的样本效率，能够在数据稀缺的情况下优化决策过程，具有重要的实际价值和未来影响。

📄 摘要（原文）

Many offline reinforcement learning algorithms are underpinned by $f$-divergence regularization, but their sample complexity defined with respect to regularized objectives still lacks tight analyses, especially in terms of concrete data coverage conditions. In this paper, we study the exact concentrability requirements to achieve the $\tilde{\Theta}(\epsilon^{-1})$ sample complexity for offline $f$-divergence-regularized contextual bandits. For reverse Kullback-Leibler (KL) divergence, arguably the most commonly used one, we achieve an $\tilde{O}(\epsilon^{-1})$ sample complexity under single-policy concentrability for the first time via a novel pessimism-based analysis, surpassing existing $\tilde{O}(\epsilon^{-1})$ bound under all-policy concentrability and $\tilde{O}(\epsilon^{-2})$ bound under single-policy concentrability. We also propose a near-matching lower bound, demonstrating that a multiplicative dependency on single-policy concentrability is necessary to maximally exploit the curvature property of reverse KL. Moreover, for $f$-divergences with strongly convex $f$, to which reverse KL does not belong, we show that the sharp sample complexity $\tilde{\Theta}(\epsilon^{-1})$ is achievable even without pessimistic estimation or single-policy concentrability. We further corroborate our theoretical insights with numerical experiments and extend our analysis to contextual dueling bandits. We believe these results take a significant step towards a comprehensive understanding of objectives with $f$-divergence regularization.