mlsanityData to 7 Oct 2026

Eluder-based Regret for Stochastic Contextual MDPs

arXiv 2211.14932 ↗First posted 27 Nov 2022cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We present the E-UC3RL algorithm for regret minimization in Stochastic Contextual Markov Decision Processes (CMDPs). The algorithm operates under the minimal assumptions of realizable function class and access to offline least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient offline regression oracles) and enjoys a regret guarantee of widetildeO(H3 √T |S| |A|dE(P) log (|F| |P|/ δ) )) , with T being the number of episodes, S the state space, A the action space, H the horizon, P and F are finite function classes used to approximate the context-dependent dynamics and rewards, respectively, and dE(P) is the Eluder dimension of P w.r.t the Hellinger distance. To the best of our knowledge, our algorithm is the first efficient and rate-optimal regret minimization algorithm for CMDPs that operates under the general offline function approximation setting. In addition, we extend the Eluder dimension to general bounded metrics which may be of separate interest.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 43 references that are in the map. First posted on arXiv 27 Nov 2022.

Builds on

24 of 43 references.

References · 24

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2015Contextual Markov Decision Processescited by 213
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  8. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  11. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  12. 2018Practical Contextual Bandits with Regression Oraclescited by 92
12 more
  1. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  2. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  3. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  4. 2017Markov Decision Processes with Continuous Side Informationcited by 54
  5. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  6. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  7. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  8. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  9. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  10. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  11. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  12. 2022Learning Efficiently Function Approximation for Contextual MDPcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 2; 2026: 3.

9 papers.

  1. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  2. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  3. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  4. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  5. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  6. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
  7. 2025Constrained Online Decision-Making: A Unified Frameworkcited by 0
  8. 2026Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedbackcited by 0
  9. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0