Batch Value-function Approximation with Only Realizability

2020/08/11 by Tengyang Xie, Nan Jiang, Xie, Tengyang +1 · 14 citations
Computer Science · Engineering · #Reinforcement Learning in Robotics #Machine Learning and Algorithms #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.2008.04990

Abstract

We make progress in a long-standing problem of batch reinforcement learning (RL): learning Q^⋆ 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.

Citations

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization

Cited by

• Bellman Calibration for V-Learning in Offline Reinforcement Learning
• Selecting Belief-State Approximations in Simulators with Latent States
• Is Pessimism Provably Efficient for Offline RL?
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Near-Optimal Offline Reinforcement Learning via Double Variance\n Reduction
• Finite-Time Bounds for Average-Reward Fitted Q-Iteration
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees
• Inverse Reinforcement Learning with Just Classification and a Few Regressions
• Instabilities of Offline RL with Pre-Trained Neural Representation
• Implicit Under-Parameterization Inhibits Data-Efficient Deep\n Reinforcement Learning
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Offline Policy Selection under Uncertainty

Related

• Information-Theoretic Considerations in Batch Reinforcement Learning
• A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL