mlsanityData to 14 Oct 2026

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

arXiv 2502.06051 ↗First posted 9 Feb 2025cs.LG cs.AI math.STcited by 10

On the map: Offline RL and imitation learning from data → Offline RL algorithms

also in 1 more
Abstract (arXiv)

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 tildeTheta(ε-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 tildeO(ε-1) sample complexity under single-policy concentrability for the first time via a novel pessimism-based analysis, surpassing existing tildeO(ε-1) bound under all-policy concentrability and tildeO(ε-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 tildeTheta(ε-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.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 50 of its 84 references that are in the map. First posted on arXiv 9 Feb 2025.

Builds on

50 of 84 references.

Closest ancestors · 12

Same direction, newest first

  1. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning2 Oct
  2. 2023Importance-Weighted Offline Learning Done Right27 Sep
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  6. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  7. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  9. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  10. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  11. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  12. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 38

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2018Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Reviewcited by 482
  7. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  8. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  9. 2019A Theory of Regularized Markov Decision Processescited by 286
  10. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  11. 2024Self-Play Preference Optimization for Language Model Alignmentcited by 232
  12. 2023Nash Learning from Human Feedbackcited by 224
26 more
  1. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  2. 2017A unified view of entropy-regularized Markov decision processescited by 182
  3. 2018Understanding the impact of entropy on policy optimizationcited by 176
  4. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  5. 2015Contextual Dueling Banditscited by 101
  6. 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
  7. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  8. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  9. 2024Correlated Proxies: A New Definition and Improved Mitigation for Reward Hackingcited by 50
  10. 2024Offline Regularised Reinforcement Learning for Large Language Models Alignmentcited by 48
  11. 2015Fighting Bandits with a New Kind of Smoothnesscited by 47
  12. 2018On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradientcited by 43
  13. 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
  14. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  15. 2018Bayesian Counterfactual Risk Minimizationcited by 28
  16. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  17. 2024Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimizationcited by 22
  18. 2022PAC-Bayesian Offline Contextual Bandits With Guaranteescited by 20
  19. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  20. 2024Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learningcited by 16
  21. 2019Regularization Matters in Policy Optimizationcited by 13
  22. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  23. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 12
  24. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  25. 2024Scalable Online Exploration via Coverabilitycited by 10
  26. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 7.

10 papers.

  1. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  2. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 10
  3. 2025Improved Bounds for Private and Robust Alignmentcited by 5
  4. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 5
  5. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 4
  6. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 4
  7. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3
  8. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analysescited by 2
  9. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 1
  10. 2026Fast Rates for Offline Q-Learning with KL Regularizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  2. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
  3. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  4. 2021Nearly Horizon-Free Offline Reinforcement Learning
  5. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  6. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits
  7. 2024A Fast Convergence Theory for Offline Decision Making
  8. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning