mlsanityData to 14 Oct 2026

Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

arXiv 1905.10389 ↗First posted 24 May 2019cs.LG stat.MLcited by 201

Not on the map. Why?

Cited by 40 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional value and policy functions using given features. However existing methods either have no theoretical guarantee or suffer a regret that is exponential in the planning horizon H. In this paper, we propose an online RL algorithm, namely the MatrixRL, that leverages ideas from linear bandit to learn a low-dimensional representation of the probability transition model while carefully balancing the exploitation-exploration tradeoff. We show that MatrixRL achieves a regret bound Obig(H2dlog T√Tbig) where d is the number of features. MatrixRL has an equivalent kernelized version, which is able to work with an arbitrary kernel Hilbert space without using explicit features. In this case, the kernelized MatrixRL satisfies a regret bound Obig(H2widetildedlog T√Tbig), where widetilded is the effective dimension of the kernel space. To our best knowledge, for RL using features or kernels, our results are the first regret bounds that are near-optimal in time T and dimension d (or widetilded) and polynomial in the planning horizon H.

Key facts. Cited by 201 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 2; 2021: 55; 2022: 42; 2023: 45; 2024: 31; 2025: 16; 2026: 10.

201 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  4. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  5. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  7. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 62
  8. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  9. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  10. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  11. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  12. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
38 more
  1. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  2. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  3. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  4. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  5. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  6. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  7. 2021MobILE: Model-Based Imitation Learning From Observation Alonecited by 44
  8. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  9. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  10. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  11. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  12. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  13. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  14. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  15. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  16. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  17. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  18. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  19. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  20. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  21. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  22. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  23. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  24. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  25. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  26. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  27. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  28. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  29. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  30. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  31. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  32. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  33. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  34. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  35. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  36. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  37. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  38. 2021Efficient Local Planning with Linear Function Approximationcited by 23

50 most cited of 201 All 201 (JSON)