Batch Value-function Approximation with Only Realizability

Abstract

We make progress in a long-standing problem of batch reinforcement learning (RL): learning $Q^{\star }$ from an exploratory and polynomial-sized dataset, using a realizable and otherwise arbitrary function class. In fact, all existing algorithms demand function-approximation assumptions stronger than realizability, and the mounting negative evidence has led to a conjecture that sample-efficient learning is impossible in this setting (Chen and Jiang, 2019). Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure that reduces the learning problem to pairwise comparison, and solves the latter with the help of a state-action partition constructed from the compared functions. We also discuss how BVFT can be applied to model selection among other extensions and open problems.

Published in ICML 2021

References in corpus (10)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Off-Policy Policy Gradient with State Distribution Correction
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm

Cited by in corpus (14)

• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Is Pessimism Provably Efficient for Offline RL?
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Offline Policy Selection under Uncertainty
• Instabilities of Offline RL with Pre-Trained Neural Representation
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Nearly Horizon-Free Offline Reinforcement Learning
• Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• False Correlation Reduction for Offline Reinforcement Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings