Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff
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.
Introduces LOLIPOP, an offline-oracle-efficient algorithm for stochastic tabular contextual MDPs that reduces regret minimization and reward-free exploration to O(H log T) or O(H log log T) calls to an offline density estimation (MLE) oracle.
Problem
Achieving optimal regret for general stochastic contextual MDPs (tabular, finite model class, realizability) with an offline density estimation oracle while making few oracle calls, as opposed to O(T) calls in prior work.
Approach
Layerwise exploration-exploitation: each epoch is split into H segments, each with a new randomized policy built as an inverse-gap-weighting distribution over a policy cover, using "trusted occupancy measures" that clip transitions with low reachability so that the analysis works with Hellinger-accurate offline density estimators rather than online ones.
Key results
- Regret bound Reg(T) ≲ sqrt(H^7 S^4 A^3 T log(|M| log log T/δ) log log T) using O(H log log T) MLE oracle calls when T is known.
- Without knowing T, regret ≲ sqrt(H^7 S^4 A^3 T log(|M| log T/δ)) with O(H log T) oracle calls.
- Reward-free RL sample complexity O(H^7 S^4 A^3 log(|M|/δ)/ε^2) with O(H) MLE oracle calls, with a matching lower bound up to poly(H,S,A).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LOLIPOP instead of E2D | CMDP learning with a general finite model class · General finite model class CMDPs; i.i.d. contexts | oracle calls: $O(T)$ calls to an online oracle -> $O(\log T)$ or $O(\log\log T)$ calls to an offline oracle | Helped |
| use LOLIPOP instead of RM-UCDD | CMDP learning · General finite model class CMDPs; i.i.d. contexts | regret rate: Suboptimal -> Optimal | Helped |
| use LOLIPOP instead of RM-UCDD | CMDP learning · General finite model class CMDPs; i.i.d. contexts | offline oracle calls: $O(T)$ calls to an offline oracle -> $O(\log T)$ or $O(\log\log T)$ calls to an offline oracle | Helped |
| use LOLIPOP instead of CMDP-VR | CMDP learning · General finite model class CMDPs; i.i.d. contexts | offline oracle calls: $O(T)$ calls to an offline oracle -> $O(\log T)$ or $O(\log\log T)$ calls to an offline oracle | Helped |
| use the known-T epoch schedule $\tau_m = 2(T/H)^{1-2^{-m}}$ | LOLIPOP · CMDPs; known T | offline MLE oracle calls: $O(H\log T) -> O(H\log\log T)$ | Helped |
Limitations
- Tabular CMDPs only; extension to linear or low-rank CMDPs is left open.
- Requires a Hellinger-accurate offline density estimation oracle; offline regression oracles are insufficient for the analysis.
- Regret bound has poly(H,S,A) factors that are not tight relative to the lower bound.
Experimental setup
Metrics: regret sample complexity
Baselines: E2D RM-UCDD CMDP-VR Version Space Averaging + E2D
Builds on: FALCON inverse gap weighting E2D RM-UCDD CMDP-VR
Closest papers by meaning
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.88)
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.87)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.87)
- Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage (NeurIPS 2024 · similarity 0.87)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.87)
- Eluder-based Regret for Stochastic Contextual MDPs (ICML 2024 · similarity 0.86)
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.