TL;DR
This paper tackles a crucial limitation in offline Reinforcement Learning (RL): the assumption that data is collected by a single, static policy. They introduce a more realistic setting where data collection policies can adapt over time, showing that existing theoretical guarantees for policy evaluation and learning still hold. This work is important because it brings offline RL closer to real-world scenarios where data is often gathered dynamically.
What Problem Does This Paper Address?
Offline Reinforcement Learning (RL) aims to train RL agents using pre-collected datasets, avoiding the need for risky online exploration. However, a major hurdle is the theoretical assumption that these datasets are generated by a single, "good" logging policy, meaning the data points are independent and identically distributed (i.i.d.). This assumption is often unrealistic. In practice, data is frequently collected over time, with the data collection strategy potentially adapting based on previous observations. This adaptive nature leads to dependencies between trajectories, violating the i.i.d. assumption. The paper addresses this gap by developing theoretical guarantees for offline RL in a more flexible setting where the data collection policy can adapt based on previously collected data.
Methods
The core contribution is the introduction of the Adaptive Offline RL (AORL) setting. This setting allows for datasets to be collected by an adaptive logging algorithm, where each new trajectory's logging policy can depend on all previously collected trajectories. To analyze this, they introduce a "tape machine" model, which visualizes data collection as adaptively querying entries from a table of transitions. This model allows them to leverage existing i.i.d. results by conditioning on the number of queries to each "row" of the table.
Key techniques include:
- Adaptive Offline Policy Evaluation (AOPE) and Adaptive Offline Policy Learning (AOPL): These are the adaptive counterparts to standard OPE and OPL.
- TMIS (Tabular Marginalized Importance Sampling) estimator: This is the standard estimator used for policy evaluation.
- "Burning data": A technique to create a "burned dataset" D' by keeping only the first $N := \min_{h,s,a} n_{h,s,a}$ observations from each row of the tape machine. This transformation allows them to recover near-optimal worst-case bounds by reducing the problem to a generative model setting.
- Instance-dependent bounds: Beyond worst-case bounds, they derive bounds that are tighter for specific problem instances, highlighting the importance of how "pivotal" transitions are and how likely the target policy is to visit them.
Datasets
The paper does not introduce new datasets. Instead, it proposes a new setting for data collection (adaptive logging) and uses this setting to analyze existing theoretical problems (OPE and OPL). Their numerical experiments use data generated by an optimistic exploration algorithm (UCB-VI) and a corresponding "Shadow" dataset generated by the same policies but without adaptivity, to empirically compare adaptive vs. non-adaptive data collection.
Key Insights and Ideas
- Realism in Data Collection: The most significant insight is that offline RL theory can be extended to more realistic, adaptive data collection scenarios without losing theoretical guarantees. This bridges a gap between theoretical assumptions and practical data generation.
- The "Tape Machine" Model: This novel modeling approach is key to porting i.i.d. results to the adaptive setting. It provides a structured way to think about adaptively collected data.
- Adaptive Data Can Influence Error Sign: Empirically, they observe that even with the same logging policies, adaptive data collection can lead to different signed behaviors of estimation error, suggesting that adaptivity can introduce biases (e.g., negative bias for suboptimal policies).
- Instance-Dependent Bounds Matter: The instance-dependent bounds reveal that the structure of the MDP and the target policy significantly influence estimation error. This suggests that adaptive loggers could be designed to prioritize data collection in regions that are both highly visited by the target policy and where transitions are more "pivotal" (i.e., have higher uncertainty in their outcomes).
Key Results
- Near-Optimal Worst-Case Bounds: They show that minimax-optimal rates for OPE and policy learning can be recovered in the adaptive setting, provided an exploration assumption is met. This is achieved by adapting existing results from the i.i.d. setting.
- Instance-Dependent Bounds: They derive tighter, instance-dependent bounds for AOPE. These bounds decompose error based on state-action visitations and transition "pivotality," offering more granular insights than worst-case bounds.
- Empirical Validation: Simulations using UCB-VI as an adaptive logger show that adaptive data can lead to measurable differences in estimation error behavior compared to non-adaptive data, particularly for suboptimal policies, suggesting potential negative bias. The magnitude of error, however, was found to be comparable.
Limitations and Future Work
- Tabular MDPs: The theoretical results are currently limited to tabular MDPs. Extending these methodologies to MDPs with continuous state spaces is identified as important future work.
- Exploration Assumption: The theoretical results often rely on an exploration assumption (Assumption 2), which guarantees a minimum number of visits to state-action pairs. While this assumption is satisfied by reward-free exploration algorithms, it's a condition that needs to be met.
- Computational Constraints: The authors mention that computational resources limited their ability to fully explore certain conjectures, such as the extent of negative bias in estimates for suboptimal policies.
- Understanding Beneficial Adaptivity: While the paper handles arbitrary adaptivity, it raises the question of whether specific forms of adaptivity (e.g., optimistic exploration) can be beneficial for learning high-value policies, which is explored empirically but warrants further theoretical investigation.