mlsanityData to 7 Oct 2026

√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

arXiv 1909.02506 ↗First posted 5 Sep 2019cs.LG stat.MLcited by 20

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very large state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we develop an online learning algorithm that learns the optimal value function while at the same time achieving very low cumulative regret during the learning process. Our learning algorithm, Adaptive Value-function Elimination (AVE), is inspired by the policy elimination algorithm proposed in (Jiang et al., 2017), known as OLIVE. One of our key technical contributions in AVE is to formulate the elimination steps in OLIVE as contextual bandit problems. This technique enables us to apply the active elimination and expert weighting methods from (Dudik et al., 2011), instead of the random action exploration scheme used in the original OLIVE algorithm, for more efficient exploration and better control of the regret incurred in each policy elimination step. To the best of our knowledge, this is the first √n-regret result for reinforcement learning in stochastic MDPs with general value function approximation.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 4; 2023: 7; 2024: 1.

20 papers.

Sort:

  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. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  4. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  5. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  6. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  7. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  8. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  9. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  10. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  11. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  12. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
8 more
  1. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  2. 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
  3. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  4. 2022Provably Efficient Kernelized Q-Learningcited by 4
  5. 2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
  6. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 4
  7. 2023Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimensioncited by 3
  8. 2023The Effective Horizon Explains Deep RL Performance in Stochastic Environmentscited by 3