Information-Theoretic Considerations in Batch Reinforcement Learning

Abstract

Value-function approximation methods that operate in batch mode have foundational importance to reinforcement learning (RL). Finite sample guarantees for these methods often crucially rely on two types of assumptions: (1) mild distribution shift, and (2) representation conditions that are stronger than realizability. However, the necessity ("why do we need them?") and the naturalness ("when do they hold?") of such assumptions have largely eluded the literature. In this paper, we revisit these assumptions and provide theoretical results towards answering the above questions, and make steps towards a deeper understanding of value-function approximation.

Published in ICML 2019

References in corpus (10)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• A Theoretical Analysis of Deep Q-Learning
• Near Optimal Behavior via Approximate State Abstraction
• Deep Reinforcement Learning and the Deadly Triad
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• On Oracle-Efficient PAC RL with Rich Observations
• Statistical Linear Estimation with Penalized Estimators: an Application to Reinforcement Learning

Cited by in corpus (54)

• MOReL : Model-Based Offline Reinforcement Learning
• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• COMBO: Conservative Offline Model-Based Policy Optimization
• Safe Reinforcement Learning via Curriculum Induction
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Batch Value-function Approximation with Only Realizability
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• 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
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Reinforcement Learning Approaches for Traffic Signal Control under Missing Data
• Offline RL Without Off-Policy Evaluation
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
• Learning When-to-Treat Policies
• Policy-Aware Model Learning for Policy Gradient Methods
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Nearly Horizon-Free Offline Reinforcement Learning
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Instabilities of Offline RL with Pre-Trained Neural Representation
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
• On Value Functions and the Agent-Environment Boundary
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Fast Rates for the Regret of Offline Reinforcement Learning
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Statistically Efficient Off-Policy Policy Gradients
• Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• False Correlation Reduction for Offline Reinforcement Learning
• Minimax Model Learning
• Offline Contextual Bandits with Overparameterized Models
• Sharp Analysis of Smoothed Bellman Error Embedding