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

Haichen Hu [email protected], Jian Qian [email protected], David Simchi-Levi [email protected] · 2026

Read Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation by Haichen Hu [email protected], Jian Qian [email protected], David Simchi-Levi [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00393.txt.

Introduction

Haichen Hu, Jian Qian, and David Simchi-Levi attack the computing cost of reinforcement learning in large environments. Standard regret-minimizing algorithms call planning and estimation subroutines again and again, and the bill grows with the number of states and actions, which rules out huge or continuous settings. Oracle-efficient methods try to call those subroutines rarely, but earlier versions still scaled with the environment's size.

Their algorithm, built on log-barrier and log-determinant regularization, keeps the optimal square-root regret rate while making only a doubly-logarithmic number of oracle calls when the horizon is known. Crucially, that count does not depend at all on how many states or actions exist. The framework extends from tabular problems to linear ones with infinite state spaces and arbitrary actions, still with sublinear regret. The authors call it the first doubly oracle-efficient method of its kind for such large problems.

Catalog record

CREATORHaichen Hu [email protected], Jian Qian [email protected], David Simchi-Levi [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE164 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00393

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation Haichen Hu [email protected], Jian Qian [email protected], David Simchi-Levi [email protected] Abstract 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 O ~ ​ ( T ) \widetilde{O}(\sqrt{T}) regret bound while requiring only O ⁡ ( H ​ log ⁡ log ​ T ) O(H\log\log T) calls to both the offline statistical estimation and planning oracles when T T is known and O ⁡ ( H ​ log ⁡ T ) O(H\log T) calls when T 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 ( 41 ) . 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. † † shortheadings: Model-Based Reinforcement Learning with Double Oracle Efficiency / Hu, Qian, and Simchi-Levi † † firstpage: 1 keywords reinforcement learning, log-barrier, log-determinant, trusted occupancy measure, offline estimation oracle, policy optimization oracle. 1 Introduction In recent years, Reinforcement Learning (RL), mathematically grounded in the framework of Markov Decision Processes (MDPs), has emerged as a cornerstone of modern machine learning and artificial intelligence. The paradigm of learning optimal sequential decision-making through environmental interaction has yielded remarkable empirical successes across a diverse array of complex, real-world applications. These range from continuous control in robotics ( 32 ) and autonomous transportation ( 31 ) , to classical operations research domains such as inventory control and supply chain management ( 6 ; 29 ) . Furthermore, RL has recently played a pivotal role in aligning Large Language Models (LLMs) with human intent via Reinforcement Learning from Human Feedback (RLHF) ( 40 ; 10 ) , underscoring its broad applicability and transformative impact. With these broad applications, deploying RL in unknown environments fundamentally requires agents to efficiently navigate the exploration-exploitation trade-off. In the online reinforcement learning setting, an agent must sequentially estimate the underlying environment while actively optimize the executed policies to minimize the cumulative regret against an optimal benchmark. There have been extensive studies on regret minimization algorithms in various MDP models. For tabular MDPs, we have model-based regret minimization ( 2 ; 4 ) and model-free algorithms ( 58 ; 25 ) . For more complex MDPs models, such as linear MDPs, we also have many regret minimization algorithms based on function approximation ( 27 ; 11 ; 30 ; 51 ) . To tackle the intertwined challenges of statistical efficiency and computational complexity under function approximation, a ubiquitous paradigm in the theoretical RL literature is to decouple the two via an oracle-based framework ( 15 ; 9 ) . Generally, algorithms proceed by sequentially estimating the unknown environment or value functions using existing data, often invoking a statistical estimation procedure. The agent then feeds this optimistic, estimated model into a policy optimization oracle or planning oracle to compute the next execution policy ( 54 ; 1 ) . Within this framework, most existing theoretical regret-minimization algorithms require O(T) calls to sequential estimation oracles and policy optimization oracles. Such frequent oracle calls can incur substantial computational costs and time overhead, making these algorithms impractical in many real-world applications. Moreover, reinforcement learning typically relies on online estimation oracles to handle adaptively collected data. In contrast to well-studied offline estimation oracles, where the data are collected i.i.d. ( 45 ; 49 ) , online estimation oracles are currently available only for rather limited function classes ( 20 ) . Their construction remains unclear for many complex model classes, such as deep neural networks. These limitations underscore the need to develop reinforcement learning algorithms that are highly efficient with respect to both policy optimization and offline estimation oracles. To improve policy optimization efficiency, several regret minimization algorithms have been proposed to achieve low switching costs, thereby reducing the computational burden of planning ( 5 ; 42 ; 52 ; 43 ; 18 ) . However, these approaches suffer from several crucial drawbacks. First, they rely on online estimation oracles to update the underlying model. Second, their policy optimization oracle complexity scales with the size of the state and action spaces. Beyond these shared limitations, individual methods exhibit specific weaknesses. For instance, 42 is computationally inefficient as it requires enumerating the entire policy version space, while 52 yields a regret bound that scales exponentially with the feature dimension. Furthermore, although certain algorithms successfully reduce the frequency of actual policy switches, they still necessitate model estimation and policy optimization at every single round ( 18 ) , which is fundamentally not oracle-efficient. From the perspective of offline oracle efficiency, 46 pioneered an efficient algorithm for contextual bandits requiring O(\log\log T) offline regression oracle calls with known T under finite action spaces, which is then generalized to functional regression ( 22 ) and general action spaces ( 44 ) . 55 ; 33 ; 23 ; 35 introduced UCB-style algorithms to address regret minimization in contextual bandits and tabular contextual MDPs. However, these approaches demand O(T) oracle calls and are not truly oracle-efficient. Most notably, 41 proposed the first regret minimization algorithm for tabular MDPs that achieves remarkable efficiency, requiring only O(H\log\log T) offline density estimation oracle calls and O(HSA\log\log T) policy optimization oracle calls during online interactions. Nevertheless, all existing algorithms for reinforcement learning suffer from two primary limitations. First, the number of policy optimization (or planning) oracle calls is either O(T) or scales with the cardinality of the state and action spaces. This dependence becomes computationally prohibitive in environments with large state and action spaces. Therefore, none of them achieves both policy-optimization oracle efficiency and offline estimation oracle efficiency simultaneously. Second, the current literature on offline estimation oracle-efficient regret minimization in reinforcement learning is strictly confined to tabular MDPs ( 41 ) . Consequently, it remains an open question whether offline oracle-efficient algorithms can be developed to achieve sub-linear regret in more complex MDP models. These two limitations naturally motivate the following questions: Can we design a regret minimization algorithm that is efficient with respect to both offline estimation and planning oracles, with oracle call times entirely independent of the state and action space dimensions? Furthermore, can we develop offline oracle-efficient regret minimization algorithms for more complex environments beyond tabular MDPs? Our Contributions. In this paper, we address

Read the complete text