Research map / Bandits and online learning / RL theory and MDPs
Eluder-based Regret for Stochastic Contextual MDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes E-UC^3RL, an oracle-efficient regret algorithm for stochastic contextual MDPs using only offline least-squares and log-loss regression oracles, with regret controlled by a metric Eluder dimension under Hellinger distance.
Problem
Regret minimization in stochastic contextual MDPs under general function approximation, where prior offline-oracle methods required minimum reachability assumptions giving O(sqrt(T)/p_min) or T^{3/4} regret.
Approach
Optimistic-in-expectation algorithm with counterfactual occupancy-based reward bonuses, computed from stabilized log-loss oracle estimates, made stable via an Eluder-dimension argument; plus an extension of the Eluder dimension to general bounded metrics and a multiplicative (Hellinger) value change-of-measure lemma.
Key results
- Regret bound of O~(H^3 sqrt(T|S||A| d_E(P) log(|F||P|/delta))) with high probability, obtained by E-UC^3RL using only offline LSR and LLR oracles.
- Removes the minimum reachability assumption needed by prior offline-oracle CMDP methods, which gave O(sqrt(T)/p_min) regret and T^{3/4} in general.
- Matches the sqrt(T) rate up to H and Eluder-dimension factors; a gap of H^{2.5} and d_P factors versus the lower bound remains.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use offline regression oracles under a bounded Eluder dimension assumption instead of requiring minimum reachability | Stochastic CMDPs · Stochastic CMDPs | regret upper bound: \widetilde{O}(\sqrt{T}/p_{min}) -> \widetilde{O}(\sqrt{T}) | Helped |
Limitations
- Requires a known upper bound on the Eluder dimension of the dynamics class, and regret depends on it.
- Gap of H^{2.5} and Eluder-dimension factors relative to the known lower bound.
- Analysis restricted to finite context and function classes; extension to infinite classes is only sketched via covering numbers.
Experimental setup
Metrics: regret bound (theoretical)
Baselines: Levy et al. minimum-reachability CMDP algorithm (O(sqrt(T)/p_min)) OLIVE E2D GLM-based CMDP regret
Builds on: Eluder dimension UC3RL / counterfactual confidence for contextual bandits log-loss oracle Hellinger bounds (Foster et al.)
Closest papers by meaning
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.88)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.88)
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation (ICLR 2024 · similarity 0.88)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.88)
- Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.