Introduction
In Reinforcement Learning (RL), a fundamental distinction exists between "active" learning—where an agent explores its environment to gather information—and "batch" or "offline" learning, where the agent must learn from a pre-collected dataset. While active exploration has been shown to find optimal policies with a polynomial number of samples, many high-stakes applications like healthcare and autonomous driving preclude active experimentation due to safety and ethical risks. In these scenarios, we rely on data generated by a fixed "logging policy."
This paper investigates the fundamental price of this passivity. The authors uncover what they term the "Curse of Passivity," proving that when data is collected via a fixed logging policy rather than active exploration, the sample complexity required to find an optimal policy grows exponentially with the number of states and the planning horizon. This finding suggests that many real-world offline RL scenarios are fundamentally more difficult than previously assumed in theoretical literature.
The Problem: The Price of Being Passive
Previous research in offline RL often bypassed the question of data collection by assuming the provided dataset already possessed "good coverage" of the state-action space. This paper shifts the focus to the data collection mechanism itself: Policy-induced sampling.
In policy-induced sampling, data is generated by following a fixed trajectory dictated by a logging policy $\mu$. This is contrasted with SA-sampling, where an algorithm can query any state-action pair (effectively having access to a simulator). The authors ask: what is the minimum number of samples needed to guarantee that a logging policy provides enough coverage to learn an $\epsilon$-optimal policy?
Theoretical Framework and Methodology
The study utilizes mathematical proofs to establish lower and upper bounds for sample complexity within Markov Decision Processes (MDPs). The analysis covers both tabular MDPs and those utilizing linear function approximation.
The Combination Lock Construction
To establish lower bounds, the authors employ a "combination lock" MDP. In this environment, an agent must execute a precise sequence of actions to reach a rewarding state. Any deviation from this sequence results in the agent being relegated to a "dead-end" state or returned to the start. In an active setting, an agent can systematically test sequences. However, a passive agent following a fixed logging policy relies entirely on the probability of that policy accidentally stumbling upon the correct sequence.
Algorithms Evaluated
The paper evaluates two primary algorithmic paradigms for the upper bounds:
- The Plug-in (Certainty Equivalence) Algorithm: This approach builds a model of the environment using Maximum Likelihood Estimation (MLE) from the observed data and then solves the resulting model.
- Pessimistic Algorithms: These algorithms incorporate a degree of caution regarding state-action pairs that are underrepresented in the dataset, a standard strategy in modern offline RL to avoid overestimating the value of unexplored regions.
Key Insights: The Curse of Passivity
The Exponential Gap
The most significant finding is the jump from polynomial to exponential sample complexity. The authors prove a lower bound of $\Omega(A^{\min(S-1, H)} / \epsilon^2)$, where $A$ represents the number of actions, $S$ the number of states, and $H$ the planning horizon. This demonstrates that the probability of a fixed policy hitting a specific long sequence of "correct" actions decreases exponentially with the length of the sequence, making passive data collection inherently inefficient for complex tasks.
The Inefficacy of "Warm Starts"
A common intuition in RL is that starting with a "good" logging policy (a warm start) might mitigate the difficulty of offline learning. However, the authors prove that even if the logging policy is relatively high-performing, the sample complexity required to improve it to a near-optimal level remains exponential. This suggests that refining a policy offline is nearly as hard as learning one from scratch if the logging policy does not already cover the optimal path extensively.
Average Reward and Infinite Complexity
In settings involving average rewards (without a fixed horizon), the situation worsens. The authors show that sample complexity can effectively become infinite because certain critical states may have a zero probability of being reached by a fixed logging policy, regardless of how much data is collected.
Implications for RL Benchmarking
The paper provides a critical meta-analysis of existing offline RL benchmarks, such as D4RL. The authors argue that many current successes in the field are "biased" because the datasets were collected using noisy versions of near-optimal policies. This high-quality data masks the underlying hardness of the problem. They suggest that the community needs to develop more realistic benchmarks that do not rely on such "expert-adjacent" logging policies to truly test the limits of offline RL algorithms.
Conclusion and Future Work
This research establishes that the "Curse of Passivity" is a fundamental barrier in batch RL. While the results are tight for tabular MDPs, extending these sharp exponential bounds to complex neural network-based function approximators remains an open challenge. Additionally, the authors leave open the question of whether a single uniform stochastic policy is as effective as the mixture of deterministic policies they found to be optimal for data collection. Ultimately, this work serves as a cautionary tale for the deployment of offline RL in domains where exploration is impossible and the logging policy is suboptimal.
Summary updated