Optimism in Reinforcement Learning with Generalized Linear Function Approximation

2019/12/09 by Yining Wang, Ruosong Wang, Wang, Yining +5 · 3 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Smart Grid Energy Management

paper · pdf · doi:10.48550/arxiv.1912.04136

openalex publication_date 2019/12/09 · openalex created_date 2019/12/13 · openalex updated_date 2026/07/28

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 O(√(d³ 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.

Citations

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement\n Learning
• Provably efficient RL with Rich Observations via Latent State Decoding
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Is a Good Representation Sufficient for Sample Efficient Reinforcement\n Learning?
• Provably Efficient Reinforcement Learning with Linear Function Approximation

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• GenAI vs. Human Creators: Procurement Mechanism Design in Two-/Three-Layer Markets
• Regret Bounds for Adaptive Nonlinear Control

Related

• A Unifying View of Optimism in Episodic Reinforcement Learning
• VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation