# Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration

arXiv: https://arxiv.org/abs/2501.13394 · HTML: https://mlsanity.com/paper/2501.13394/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 35)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Emergent Complexity via Multi-Agent Competition](https://mlsanity.com/paper/1710.03748/) (2017)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [AdaLead: A simple and robust adaptive greedy search algorithm for sequence design](https://mlsanity.com/paper/2010.02141/) (2020)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Hypermodels for Exploration](https://mlsanity.com/paper/2006.07464/) (2020)
- [Successor Uncertainties: Exploration and Uncertainty in Temporal Difference Learning](https://mlsanity.com/paper/1810.06530/) (2018)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2103.04972/) (2021)
- [Provably Efficient Reinforcement Learning with Aggregated States](https://mlsanity.com/paper/1912.06366/) (2019)
- [Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization](https://mlsanity.com/paper/1307.4847/) (2013)
- [Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/2010.12163/) (2020)
- [Coordinated Exploration in Concurrent Reinforcement Learning](https://mlsanity.com/paper/1802.01282/) (2018)
- [Bayesian Bellman Operators](https://mlsanity.com/paper/2106.05012/) (2021)
- [Competitive Multi-agent Inverse Reinforcement Learning with Sub-optimal Demonstrations](https://mlsanity.com/paper/1801.02124/) (2018)

## 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.