Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Abstract

We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closure," which is strictly weaker than assumptions from prior analyses for the linear setting. With optimistic closure, we prove that our algorithm enjoys a regret bound of $\tilde{O}(\sqrt{d^{3}T})$ where $d$ is the dimensionality of the state-action features and $T$ is the number of episodes. This is the first statistically and computationally efficient algorithm for reinforcement learning with generalized linear functions.

References in corpus (7)

• Off-Policy Deep Reinforcement Learning without Exploration
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Provably efficient RL with Rich Observations via Latent State Decoding
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

Cited by in corpus (41)

• Learning Near Optimal Policies with Low Inherent Bellman Error
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• 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
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Privacy-Preserving Dynamic Personalized Pricing with Demand Learning
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Corruption-robust exploration in episodic reinforcement learning
• Adaptive Discretization in Online Reinforcement Learning
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Adaptive Discretization for Model-Based Reinforcement Learning
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Principled Exploration via Optimistic Bootstrapping and Backward Induction
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Breaking the Deadly Triad with a Target Network
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Efficient Local Planning with Linear Function Approximation
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Learning Stochastic Shortest Path with Linear Function Approximation
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games
• Regret Bounds for Adaptive Nonlinear Control
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation