Optimal Regret for Policy Optimization in Contextual Bandits
Not on the map. Why?
Abstract (arXiv)
We present the first high-probability optimal regret bound for a policy optimization technique applied to the problem of stochastic contextual multi-armed bandit (CMAB) with general offline function approximation. Our algorithm is both efficient and achieves an optimal regret bound of widetildeO(√ K|A|log|F|), where K is the number of rounds, A is the set of arms, and F is the function class used to approximate the losses. Our results bridge the gap between theory and practice, demonstrating that the widely used policy optimization methods for the contextual bandit problem can achieve a rigorously-proved optimal regret bound. We support our theoretical results with an empirical evaluation of our algorithm.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 34 of its 52 references that are in the map. First posted on arXiv 14 Feb 2026.
Builds on
34 of 52 references.
References · 34
- 2022Training language models to follow instructions with human feedbackcited by 15,712
- 2017Proximal Policy Optimization Algorithmscited by 14,441
- 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
- 2015Continuous control with deep reinforcement learningcited by 3,279
- 2020Learning to summarize from human feedbackcited by 2,562
- 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 1,916
- 2015End-to-End Training of Deep Visuomotor Policiescited by 847
- 2022Improving alignment of dialogue agents via targeted human judgementscited by 527
- 2019Introduction to Multi-Armed Banditscited by 475
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
- 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
22 more
- 2019Provably Efficient Exploration in Policy Optimizationcited by 203
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
- 2018Practical Contextual Bandits with Regression Oraclescited by 92
- 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
- 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
- 2018A Contextual Bandit Bake-offcited by 64
- 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
- 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
- 2018Logistic Regression: The Importance of Being Impropercited by 40
- 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
- 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
- 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
- 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
- 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
- 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
- 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
- 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
- 2014Normalized Online Learningcited by 7
- 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
- 2025Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedbackcited by 6
- 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
Built on by
Citing papers per year: 2026: 1.
1 paper.