mlsanityData to 14 Oct 2026

Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

arXiv 2605.00393 ↗First posted 1 May 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks, as conventional regret minimization algorithms require repeated, costly calls to planning and statistical estimation oracles. While recent advances have explored offline oracle-efficient algorithms, their computational complexity typically scales with the cardinality of the state and action spaces, rendering them intractable for large-scale or continuous environments. In this paper, we address this fundamental limitation by studying offline oracle-efficient episodic RL through the lens of log-barrier and log-determinant regularization. Specifically, for tabular Markov Decision Processes (MDPs), we propose a novel algorithm that achieves the optimal tildeO(√T) regret bound while requiring only O(Hloglog T) calls to both the offline statistical estimation and planning oracles when T is known and O(Hlog T) calls when T is unknown. Crucially, this oracle complexity is entirely independent of the size of the state and action spaces. This strict independence drastically reduces the planning oracle complexity, representing a substantial improvement over existing offline oracle-efficient algorithms (Qian et al., 2024). Furthermore, we demonstrate the versatility of our framework by generalizing the algorithm to linear MDPs featuring infinite state spaces and arbitrary action spaces. We prove that this generalized approach successfully attains meaningful sub-linear regret. Consequently, our work yields the first doubly oracle-efficient (i.e., efficient with respect to both statistical estimation and policy optimization) regret minimization algorithm capable of solving MDPs with infinite state and action spaces, significantly expanding the boundaries of computationally tractable RL.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 60 references that are in the map. First posted on arXiv 1 May 2026.

Builds on

15 of 60 references.

References · 15

  1. 2023Safe RLHF: Safe Reinforcement Learning from Human Feedbackcited by 656
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  4. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
  5. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  6. 2024Constrained Reinforcement Learning with Smoothed Log Barrier Functioncited by 15
  7. 2024Online Estimation via Offline Estimation: An Information-Theoretic Frameworkcited by 13
  8. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  9. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  10. 2025Wild refitting for black box predictioncited by 5
  11. 2026Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Banditscited by 4
  12. 2026Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictorscited by 3
3 more
  1. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 2
  2. 2025Constrained Online Decision-Making: A Unified Frameworkcited by 1
  3. 2026How Log-Barrier Helps Exploration in Policy Optimizationcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learning
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2025Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  5. 2026A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
  6. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  7. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  8. 2021Nearly Horizon-Free Offline Reinforcement Learning