On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
This work addresses theoretical guarantees for offline RL with dependent data, which is incremental but important for applications where data collection is costly or risky.
The paper tackles the sample complexity of vanilla model-based offline reinforcement learning with dependent samples, providing high-probability polynomial bounds for off-policy evaluation and optimization under coverage assumptions, and introduces an estimator that outperforms the sample-mean for near-deterministic dynamics.
Offline reinforcement learning (offline RL) considers problems where learning is performed using only previously collected samples and is helpful for the settings in which collecting new data is costly or risky. In model-based offline RL, the learner performs estimation (or optimization) using a model constructed according to the empirical transition frequencies. We analyze the sample complexity of vanilla model-based offline RL with dependent samples in the infinite-horizon discounted-reward setting. In our setting, the samples obey the dynamics of the Markov decision process and, consequently, may have interdependencies. Under no assumption of independent samples, we provide a high-probability, polynomial sample complexity bound for vanilla model-based off-policy evaluation that requires partial or uniform coverage. We extend this result to the off-policy optimization under uniform coverage. As a comparison to the model-based approach, we analyze the sample complexity of off-policy evaluation with vanilla importance sampling in the infinite-horizon setting. Finally, we provide an estimator that outperforms the sample-mean estimator for almost deterministic dynamics that are prevalent in reinforcement learning.