Abstract
Reinforcement learning (RL) methods have proved to be successful in many simulated environments. The common approaches, however, are often too sample intensive to be applied directly in the real world. A promising approach to addressing this issue is to train an RL agent in a simulator and transfer the solution to the real environment. When a high-fidelity simulator is available we would expect significant reduction in the amount of real trajectories needed for learning. In this work we aim at better understanding the theoretical nature of this approach. We start with a perhaps surprising result that, even if the approximate model (e.g., a simulator) only differs from the real environment in a single state-action pair (but which one is unknown), such a model could be information-theoretically useless and the sample complexity (in terms of real trajectories) still scales with the total number of states in the worst case. We investigate the hard instances and come up with natural conditions that avoid the pathological situations. We then propose two conceptually simple algorithms that enjoy polynomial sample complexity guarantees with no dependence on the size of the state-action space, and prove some foundational results to provide insights into this important problem.
Introduction: Bridging the Reality Gap
Reinforcement Learning (RL) is notoriously "sample hungry," often requiring millions of trials to learn effective behaviors. To avoid the cost and danger of real-world training—such as crashing a physical drone—researchers frequently rely on simulators. However, simulators are rarely perfect reflections of reality. This "imperfect model" problem leads to a significant dilemma: if the simulator is even slightly inaccurate, an agent might learn a policy that performs brilliantly in simulation but fails catastrophically in the real world.
This paper addresses a fundamental theoretical question: How much real-world data is required to "fix" an imperfect simulator? Specifically, the authors seek "Probably Approximately Correct" (PAC) guarantees where the amount of real-world data needed remains independent of the total number of states $|S|$ and actions $|A|$, provided the simulator is "mostly" correct.
Methods: Iterative Learning and Model Refinement
The authors propose a protocol where a learner alternates between computing a policy in a simulator and collecting trajectories in the real environment to verify and revise the model.
Two conceptually simple algorithms are introduced to manage this interaction:
- MODEL_REPAIR: This algorithm uses real-world data to "patch" the simulator. When the agent follows the simulator's optimal policy in reality and encounters a transition discrepancy, it records the real transition and updates the model accordingly.
- MODEL_PENALIZE: Designed for scenarios where the simulator cannot be modified (e.g., a black-box engine), this "pessimistic" approach identifies state-action pairs where the simulator is incorrect and "penalizes" the agent for visiting them by terminating the simulated episode. This forces the agent to find paths that stay within "trusted" regions of the simulator.
A key technical contribution is the definition of $\xi$-correctness, which quantifies the number of state-action pairs in the simulator that significantly deviate from reality.
Theoretical Insights: The "One-Error" Trap
A major finding of this work is that without interactivity, a simulator that is wrong about just one state-action pair can be information-theoretically useless.
If a simulator erroneously suggests a vital path is blocked (as illustrated in stylized grid world constructions), a non-interactive agent will never attempt that path in the real world, potentially missing the optimal solution entirely. This demonstrates that interactivity is crucial: non-interactive approaches (collecting a batch of data first, then using the model) cannot avoid a sample complexity that scales with the total number of states.
Key Results and Sample Complexity
The most significant "aha moment" is that sample complexity can be made to scale with the number of incorrect state-action pairs ($|X_{\xi-inc}|$) rather than the total number of states ($|S|$). This means in a massive world where the simulator only makes mistakes in a few specific areas, learning can be extremely efficient.
- Independence from $|S|$ and $|A|$: Both algorithms achieve PAC guarantees where the number of real-world trajectories required has zero dependence on the size of the state and action spaces.
- Sample Complexity Bounds:
- MODEL_REPAIR requires roughly $\tilde{O}(|X|^2 H^4 / \epsilon^3)$ trajectories.
- MODEL_PENALIZE improves the dependence on the horizon ($H$), requiring roughly $\tilde{O}(|X|^2 H^2 / \epsilon^3)$ trajectories.
Limitations and Future Work
While foundational, the current theory assumes a finite number of state-action pairs. Extending this to continuous spaces would require "covering arguments" and would depend on the complexity of the error set. Additionally, the efficiency of these algorithms relies on the error set ($|X|$) being relatively small, which may not hold in high-dimensional tasks like vision-based manipulation. Finally, the paper assumes a "computational oracle" that can instantly solve the MDP in simulation, which is itself a difficult task in practice. Future work will explore more sophisticated exploration strategies to further reduce dependence on the number of errors and the horizon $H$.
Summary updated