mlsanityData to 14 Oct 2026

Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration

arXiv 2501.13394 ↗First posted 23 Jan 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Designing learning agents that explore efficiently in a complex environment has been widely recognized as a fundamental challenge in reinforcement learning. While a number of works have demonstrated the effectiveness of techniques based on randomized value functions on a single agent, it remains unclear, from a theoretical point of view, whether injecting randomization can help a society of agents it concurently explore an environment. The theoretical results %that we established in this work tender an affirmative answer to this question. We adapt the concurrent learning framework to textitrandomized least-squares value iteration (RLSVI) with textitaggregated state representation. We demonstrate polynomial worst-case regret bounds in both finite- and infinite-horizon environments. In both setups the per-agent regret decreases at an optimal rate of Thetaleft(frac1√Nright), highlighting the advantage of concurent learning. Our algorithm exhibits significantly lower space complexity compared to citerusso2019worst and citeagrawal2021improved. We reduce the space complexity by a factor of K while incurring only a √K increase in the worst-case regret bound, compared to citepagrawal2021improved,russo2019worst. Additionally, we conduct numerical experiments to demonstrate our theoretical findings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 35 of its 58 references that are in the map. First posted on arXiv 23 Jan 2025.

Builds on

35 of 58 references.

References · 35

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  3. 2016Deep Exploration via Bootstrapped DQNcited by 527
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2013Learning to Optimize Via Posterior Samplingcited by 256
  9. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2017Deep Exploration via Randomized Value Functionscited by 156
  12. 2017Emergent Complexity via Multi-Agent Competitioncited by 120
23 more
  1. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  3. 2020AdaLead: A simple and robust adaptive greedy search algorithm for sequence designcited by 65
  4. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  5. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  6. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  7. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 43
  8. 2020Hypermodels for Explorationcited by 37
  9. 2018Successor Uncertainties: Exploration and Uncertainty in Temporal Difference Learningcited by 35
  10. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  11. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  12. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  13. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  14. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  15. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  16. 2018Coordinated Exploration in Concurrent Reinforcement Learningcited by 17
  17. 2021Bayesian Bellman Operatorscited by 16
  18. 2018Competitive Multi-agent Inverse Reinforcement Learning with Sub-optimal Demonstrationscited by 11
  19. 2018Scalable Coordinated Exploration in Concurrent Reinforcement Learningcited by 10
  20. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  21. 2021Cooperative and Competitive Biases for Multi-Agent Reinforcement Learningcited by 5
  22. 2022Posterior Sampling for Continuing Environmentscited by 4
  23. 2017On Optimistic versus Randomized Exploration in Reinforcement Learningcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Asymptotically optimal reinforcement learning in Block Markov Decision Processes
  2. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
  3. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games
  4. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback
  5. 2024Refining Minimax Regret for Unsupervised Environment Design
  6. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
  7. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  8. 2024Achieving Constant Regret in Linear Markov Decision Processes