mlsanityData to 7 Oct 2026

Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation

arXiv 2303.01464 ↗First posted 2 Mar 2023cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We present the OMG-CMDP! algorithm for regret minimization in adversarial Contextual MDPs. The algorithm operates under the minimal assumptions of realizable function class and access to online least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient online regression oracles), simple and robust to approximation errors. It enjoys an widetildeO(H2.5 √ T|S||A| ( R(O) + H log(δ-1) )) regret guarantee, with T being the number of episodes, S the state space, A the action space, H the horizon and R(O) = R(OsqF) + R(OlogP) is the sum of the regression oracles' regret, used to approximate the context-dependent rewards and dynamics, respectively. To the best of our knowledge, our algorithm is the first efficient rate optimal regret minimization algorithm for adversarial CMDPs that operates under the minimal standard assumption of online function approximation.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 19 of its 32 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

19 of 32 references.

References · 19

  1. 2021Convex optimizationcited by 2,479
  2. 2019Introduction to Multi-Armed Banditscited by 475
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2015Contextual Markov Decision Processescited by 213
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  6. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  7. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  9. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
7 more
  1. 2017Markov Decision Processes with Continuous Side Informationcited by 54
  2. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  3. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  4. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  5. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  6. 2022Learning Efficiently Function Approximation for Contextual MDPcited by 10
  7. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 3.

9 papers.

  1. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  2. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  3. 2025Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guaranteescited by 3
  4. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  5. 2025Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contextscited by 0
  6. 2025Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewardscited by 0
  7. 2026Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedbackcited by 0
  8. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0
  9. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 0