# Eluder-based Regret for Stochastic Contextual MDPs

arXiv: https://arxiv.org/abs/2211.14932 · HTML: https://mlsanity.com/paper/2211.14932/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Markov Decision Processes with Continuous Side Information](https://mlsanity.com/paper/1711.05726/) (2017)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization](https://mlsanity.com/paper/1307.4847/) (2013)
- [Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP](https://mlsanity.com/paper/2207.11126/) (2022)
- [Learning Efficiently Function Approximation for Contextual MDP](https://mlsanity.com/paper/2203.00995/) (2022)

## Built on by (most cited first, 9 of 9)

- [On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2305.11283/) (2023)
- [Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation](https://mlsanity.com/paper/2303.01464/) (2023)
- [Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL](https://mlsanity.com/paper/2402.05724/) (2024)
- [Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17796/) (2024)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Optimal Regret for Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2602.13700/) (2026)
- [Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation](https://mlsanity.com/paper/2602.13706/) (2026)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)

## 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.