Provably Good Batch Reinforcement Learning Without Great Exploration

Abstract

Batch reinforcement learning (RL) is important to apply RL algorithms to many high stakes tasks. Doing batch RL in a way that yields a reliable new policy in large domains is challenging: a new decision policy may visit states and actions outside the support of the batch data, and function approximation and optimization with limited samples can further increase the potential of learning policies with overly optimistic estimates of their future performance. Recent algorithms have shown promise but can still be overly optimistic in their expected outcomes. Theoretical work that provides strong guarantees on the performance of the output policy relies on a strong concentrability assumption, that makes it unsuitable for cases where the ratio between state-action distributions of behavior policy and some candidate policies is large. This is because in the traditional analysis, the error bound scales up with this ratio. We show that a small modification to Bellman optimality and evaluation back-up to take a more conservative update can have much stronger guarantees. In certain settings, they can find the approximately best policy within the state-action space explored by the batch data, without requiring a priori assumptions of concentrability. We highlight the necessity of our conservative update and the limitations of previous algorithms and analyses by illustrative MDP examples, and demonstrate an empirical comparison of our algorithm and other state-of-the-art batch RL baselines in standard benchmarks.

36 pages, 7 figures

References in corpus (5)

• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Safe Policy Improvement with Baseline Bootstrapping
• Approximate Policy Iteration Schemes: A Comparison
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison

Cited by in corpus (24)

• COMBO: Conservative Offline Model-Based Policy Optimization
• Batch Value-function Approximation with Only Realizability
• Is Pessimism Provably Efficient for Offline RL?
• The Importance of Pessimism in Fixed-Dataset Policy Optimization
• Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings
• Offline Reinforcement Learning with Reverse Model-based Imagination
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Offline Reinforcement Learning from Images with Latent Space Models
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Behavioral Priors and Dynamics Models: Improving Performance and Domain Transfer in Offline RL
• Corruption-Robust Offline Reinforcement Learning
• Nearly Horizon-Free Offline Reinforcement Learning
• Fast Rates for the Regret of Offline Reinforcement Learning
• Conservative Data Sharing for Multi-Task Offline Reinforcement Learning
• On the Optimality of Batch Policy Optimization Algorithms
• Improving Long-Term Metrics in Recommendation Systems using Short-Horizon Reinforcement Learning
• PerSim: Data-Efficient Offline Reinforcement Learning with Heterogeneous Agents via Personalized Simulators
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• The Difficulty of Passive Learning in Deep Reinforcement Learning
• Quantile Filtered Imitation Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings