Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Yan Chen, Qinxun Bai, Yiteng Zhang, Maria Dimakopoulou, Shi Dong, Qi Sun, Zhengyuan Zhou · 2025
Read Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration by Yan Chen, Qinxun Bai, Yiteng Zhang, Maria Dimakopoulou, Shi Dong, Qi Sun, Zhengyuan Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13394.txt.
Introduction
Yan Chen and six co-authors study concurrent reinforcement learning with aggregated states in a 2025 paper. To learn well in a hard world, an agent must explore with care. Tricks that randomize a value function work for a lone agent. If a team of agents can gain from the same trick was not clear on paper.
Their answer is yes. The team set a group of agents to learn at once, with a randomized least-squares method and states lumped into groups. Bounds on the worst-case regret are proved in closed form, for runs that end and for runs that go on. The bounds grow in a mild, polynomial way.
Catalog record
| CREATOR | Yan Chen, Qinxun Bai, Yiteng Zhang, Maria Dimakopoulou, Shi Dong, Qi Sun, Zhengyuan Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13394
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration Yan Chen, Qinxun Bai, Yiteng Zhang, Maria Dimakopoulou, Shi Dong, Qi Sun, Zhengyuan Zhou Abstract 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 concurently explore an environment. The theoretical results established in this work tender an affirmative answer to this question. We adapt the concurrent learning framework to randomized least-squares value iteration (RLSVI) with aggregated 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 Θ ( 1 N ) \Theta\left(\frac{1}{\sqrt{N}}\right) , highlighting the advantage of concurent learning. Our algorithm exhibits significantly lower space complexity compared to ( Russo, 2019 ) and ( Agrawal et al., 2021 ) . We reduce the space complexity by a factor of K K while incurring only a K \sqrt{K} increase in the worst-case regret bound, compared to ( Agrawal et al., 2021 ; Russo, 2019 ) . Interestingly, our algorithm improves the worst-case regret bound of ( Russo, 2019 ) by a factor of H 1 / 2 H^{1/2} , matching the improvement in ( Agrawal et al., 2021 ) . However, this result is achieved through a fundamentally different algorithmic enhancement and proof technique. Additionally, we conduct numerical experiments to demonstrate our theoretical findings. $\dagger$ $\dagger$ footnotetext: Corresponding author. 1 Introduction The field of reinforcement learning (RL) is dedicated to designing agents that interact with an unknown environment, aiming to maximize the total amount of reward accumulated throughout the interactions ( Sutton & Barto, 2018 ) . When the environment is complex yet the learning budget is limited, an agent has to efficiently explore the environment, giving rise to the well-known exploration-exploitation trade-off. A large body of works in the RL literature have addressed the challenge related to smartly balancing this trade-off. Among the many proposed methods, algorithms based on randomization are receiving growing attention, both theoretically ( Russo & Van Roy, 2014 ; Fellows et al., 2021 ) and empirically ( Osband et al., 2016 ; Janz et al., 2019 ; Dwaracherla et al., 2020 ) , due to their effectiveness and potential scalability in large applications. Randomized least-squares value iteration (RLSVI) represents one example of such randomization-based algorithms ( Osband et al., 2019 ) . On a high level, RLSVI injects Gaussian noise into the rewards in the agent’s previous trajectories, and allows the agent to learn a randomized value function from the perturbed dataset. With judicious noise injection, the resultant value function approximates the agent’s posterior belief of state values. By acting greedily with respect to such randomized value function, the agent effectively executes an approximated version of posterior sampling for reinforcement learning (PSRL), whose efficacy has been substantiated in previous works ( Osband et al., 2013 ; Russo & Van Roy, 2014 ; Xu et al., 2022 ) . Compared with PSRL, RLSVI circumvents the need of maintaining a model of the environment, severing huge computational cost. Since its advent, RLSVI has been studied extensively in theoretical contexts, such as ( Russo, 2019 ) and ( Ishfaq et al., 2021 ) . In this work, we look into RLSVI from the perspective of concurrent learning ( Silver et al., 2013 ) . Specifically, concurrent RL studies the problem where a cohort of agents interact with one common environment, yet are able to share their experience with each other in order to jointly improve their decisions. Such a collaborative setting has useful applications in a variety of realms, such as robotics ( Gu et al., 2017 ) , biology ( Sinai et al., 2020 ) , and recommendation systems ( Agarwal et al., 2016 ) . For instance, a team of drones may be cooperatively executing a search and rescue mission in a given terrain, and cooperatively learning to identify the locations of assets requires efficient concurrent RL. Another example is a team of virtual agents conducting circuit design, proceeding in parallel the design-circuit evaluation (via a simulator)-redesign loop. Here, they are cooperatively exploring the vast and complex design space, aiming to quickly identify an optimal design that meets all the sepc requirements 1 1 1 For instance, Arena, a world leading startup that specializes in applying AI to shorten the hardware design loop, utilizes RL to speed up the circuit design, test and debugging cycles. . Importantly, although all agents share the identical goal, coordination between agents is nontrivial. In fact, as shown in ( Dimakopoulou & Van Roy, 2018 ; Dimakopoulou et al., 2018 ) , a poorly coordinated multi-agent algorithm can drastically undermine the overall learning performance. Results in the existing theoretical literature on concurrent RL have demonstrated that PSRL ( Osband & Van Roy, 2017 ; Kim, 2017 ; Osband & Van Roy, 2014 ) in a coordinated style is provably efficient ( Chen et al., 2022 ) , compared to the earlier cooperative UCRL type of algorithms 2 2 2 It is perhaps not surprising that UCRL algorithms are the first family of algorithms that have been adapted to the concurrent RL settings ( Guo & Brunskill, 2015 ) and ( Pazis & Parr, 2016 ) . In particular, concurrent UCRL has been analyzed for the sample complexity performance measure (i.e. how many samples are needed to learn an \epsilon -optimal policy) under both finite action space setting and infinite action space setting. More specifically, ( Guo & Brunskill, 2015 ) provided a high-probability bound of \tilde{O}(\frac{S^{2}A}{\epsilon^{3}}+\frac{SAn}{\epsilon}) for the sample complexity with n agents interacting in the environment. Their algorithm was extended from MBIE(see ( Strehl & Littman, 2008 ) ), with a single agent performing concurrent RL across a set of n infinite-horizon MDPs. The results there show that with sharing samples from copies of the same MDP a linear speedup in the sample complexity of learning can be achieved. But no regret bound was derived there for concurrent RL. . As pointed out in ( Chen et al., 2022 ) , “these sample-complexity guarantees notwithstanding, concurrent UCRL algorithms suffer from the critical disadvantage of no coordinated exploration: since the upper confidence bounds computed by aggregating all agents’ data are the same the entire team, each agent would follow the exact same policy, thereby yielding no diversity in exploration." However, despite the exploration advantage offered by concurrent Thompson sampling given in a very recent work ( Chen et al., 2022 ) , it remains unclear whether the same level of efficiency can be extended to cooperative model-free agents, which are computationally more scalable. Our Contributions We model the environment as a Markov decision process (MDP) with \Gamma aggregated states, and show theoretically that a cohort of N agents, concurrently running RLSVI and sharing interaction trajectories with each other, are able to efficiently improve their joint performance towards the optimal policy in the environment. The efficiency is established through regret analysis. Additionally, for