mlsanityData to 7 Oct 2026

Optimism in Reinforcement Learning with Generalized Linear Function Approximation

arXiv 1912.04136 ↗First posted 9 Dec 2019stat.ML cs.LGcited by 111

Not on the map. Why?

Abstract (arXiv)

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 tildeO(√d3 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.

Key facts. Cited by 111 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 40; 2022: 23; 2023: 22; 2024: 15; 2025: 9; 2026: 2.

111 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2024Bigger, Regularized, Optimistic: scaling for compute and sample-efficient continuous controlcited by 104
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  7. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  8. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  9. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  10. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  11. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  12. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
38 more
  1. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  2. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  3. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  4. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  5. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  6. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  7. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  8. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  9. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  10. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  11. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  12. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  13. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  14. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  15. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  16. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  17. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  18. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  19. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  20. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  21. 2023Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithmscited by 27
  22. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  23. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  24. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  25. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  26. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  27. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  28. 2021Understanding the Eluder Dimensioncited by 19
  29. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  30. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  31. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  32. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  33. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  34. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  35. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  36. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  37. 2021An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximationcited by 13
  38. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13

50 most cited of 111 All 111 (JSON)