Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation
Not on the map. Why?
Abstract (arXiv)
We introduce textttOPO-CMDP, the first policy optimization algorithm for stochastic Contextual Markov Decision Process (CMDPs) under general offline function approximation. Our approach achieves a high probability regret bound of widetildeO(H4√T|S||A|log(|F||P|)), where S and A denote the state and action spaces, H the horizon length, T the number of episodes, and F, P the finite function classes used to approximate the losses and dynamics, respectively. This is the first regret bound with optimal dependence on |S| and |A|, directly improving the current state-of-the-art (Qian, Hu, and Simchi-Levi, 2024). These results demonstrate that optimistic policy optimization provides a natural, computationally superior and theoretically near-optimal path for solving CMDPs.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 32 of its 45 references that are in the map. First posted on arXiv 14 Feb 2026.
Builds on
32 of 45 references.
References · 32
- 2022Training language models to follow instructions with human feedbackcited by 15,712
- 2017Proximal Policy Optimization Algorithmscited by 14,441
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
- 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
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
- 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2015Contextual Markov Decision Processescited by 213
20 more
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
- 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
- 2017Markov Decision Processes with Continuous Side Informationcited by 54
- 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
- 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
- 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
- 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
- 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
- 2022Learning Efficiently Function Approximation for Contextual MDPcited by 10
- 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
- 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
- 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
- 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited 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
- 2024Sample Complexity Characterization for Linear Contextual MDPscited by 4
Built on by
Not cited yet.