Bilinear Classes: A Structural Framework for Provable Generalization in RL

Abstract

This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear $Q^{\ast }/V^{\ast }$ model in which both the optimal $Q$-function and the optimal $V$-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear $Q^{\ast }/V^{\ast }$ model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.

Expanded extension section to include generalized linear bellman complete and changed related work

References in corpus (16)

• Playing Atari with Deep Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Provably Efficient Reinforcement Learning with Aggregated States

Cited by in corpus (14)

• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Towards General Function Approximation in Zero-Sum Markov Games
• Efficient Local Planning with Linear Function Approximation
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• A Short Note on the Relationship of Information Gain and Eluder Dimension
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Gap-Dependent Bounds for Two-Player Markov Games
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP