Concurrent Reinforcement Learning with Aggregated States via  Randomized Least Squares Value Iteration
Authors: Yan Chen
Qinxun Bai
Yiteng Zhang
Maria Dimakopoulou
Shi Dong
Qi Sun
Zhengyuan Zhou
Venue: ICML 2025 poster (2025)
Keywords: worst-case regret bound
RL theory
randomized least squares value iteration
multi-agent learning
aggregated states
concurrent learning
Primary area: reinforcement_learning->multiagent
TL;DR: We prove worst-case regret bound for concurrent RLSVI, reducing the space complexity by a factor of  $K$  with only a $\sqrt{K}$  regret increase compared to the single-agent version of \citep{agrawal2021improved,russo2019worst}

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 $\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$ while incurring only a $\sqrt{K}$ increase in the worst-case regret bound, compared to Russo (2019) and Agrawal et. al (2021). Interestingly, our algorithm improves the worst-case regret bound of Russo (2019) by a factor of $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.

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Yan Chen Qinxun Bai? Yiteng Zhang? Maria Dimakopoulou
+ Shi Dong
Sun Zhengyuan Zhou 67
Abstract
1. Introduction
The field reinforcement learning (RL) is dedicated to de- signing agents that interact with an unknown environment, aiming to maximize the total amount of reward accumu- lated throughout the interactions (Sutton & Barto, 2018) 8). When the environment is complex yet the learning budget is limited, an agent has to efficiently explore the environ- ment, giving rise to the well-known exploration-exploiee 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 po- tential scalability in large applications.
Designing learning agents that explore efficiently in a complex environment has been widely recog- nized as fundamental challenge in reinforcement learning. While number of works have demon- strated 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 soci- cty 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 ran- domized least-squares value iteration (RLSVI) with aggregated state representation. We demon- strate polynomial worst-case regret bounds in both finite- and infinite-horizon environments. In both setups the per-agent regret decreases an highlighting the advan-
Randomized least-squares value iteration (RLSVI) repre- sents one example of such randomization-base algorithms (Osband al., 2019). On high level, RLSVI injects Gaus- sian noise into the rewards in the agent's previous trajec- tories, and allows the agent to learn a randomized value function from the perturbed dataset. With judicious noise in- jection, the resultant value function approximates the agent's 's posterior belief of state values. By acting greedily with respect to such randomized value function, the agent effec- tively executes an approximated version of posterior sam- pling 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,, RISVI 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).
optimal rate of θ tage 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 while incurring only a VK 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 1/2 matching the improve- ment in (Agrawal et al., 2021). However, this result is achieved through fundamentally differ- ent algorithmic enhancement and proof technique. Additionally, we conduct numerical experiments to demonstrate our theoretical findings.
In this work, we look into RLSVI from the perspective of concurrent learning (Silver et al., 2013). Specifically, con- current 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 collaborative setting has useful ap- plications in a variety of realms, such as robotics (Gu et al., 2017), biology (Sinai et al., 2020), and recommendation
'Duke University 'Horizon Robotics Inc 'UC Berkeley 'Uber GGoogle DeepMind 'New York University " 'Areaa Technologies. Correspondence to: Zhengyuan Zhou <z @ ainea-ai.com>..
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
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 RI. Another example is a team of virtual agents conduct- ing circuit design, proceeding in parallel the design-cireuit evaluation (via a rimdesg loop. Here, they are cooperatively exploring the vast and complex design space, aiming quickly identify optimal design that meets all the sepe requirement'. Importantly, although all agents share the identical goal, coordination between agents is non- trivial. 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 coordinated style is provably efficient (Chen et al., 2022), compared to the earlier cooperative UCRL type of algorithms ?. 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 pol- icy, 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.
performance towards the optimal policy in the environment. The efficiency is established through regret analysis. Ad- ditionally, for aggregated state representation setup, the performance typically will not converge to optimal solu- tion if E > O, and our result establishes that the cumulative performance loss is no greater than (e)) per period per agent. This is consistent with the findings of (Dong et al., 2019b) for single-agent scenario. Our worst-case regret bound improves upon (Russo, 2019) by a factor of H1/2, matching the improvement in (Agrawal et al., 2021) but achieved through a fundamentally different technique and proof approach.
One major difference between our algorithm and those from current literature of RL.VVI in tabular setup is that, the al- gorithms in (Russo, 2019; Agrawal et al., 2021) require storing the historical trajectories from the very beginning while our algorithm only stores the trajectories from the last episode for the finite-horizon case or the last pseudo- episode (defined in Section 4) for the infinite-horizon case. This is because for concurrent setup, the computational cost of storing all historical data scales at least linear in K H N for finite horizon and TN for infintie horizon, which is infeasible for problems of practical scale.
In both cases, the regret dependence on the total number of samples is optimal, signaling well cell-coordinated informa- tion sharing among the agents. To our best knowledge, this work presents the first theoretical analysis of a model-free concurrent RL algorithm with aggregated states.
Besides theoretical contributions, our analysis also sheds light on the empirical role of discount factor in RL. In prac- tical applications, a discount factor is usually not subsumed under the environment definition. Rather than prescribing a specific learning target that involves a decaying sequence of rewards, discount factors often simply function as a tuning parameter of the algorithm that keeps the value updates sta- ble. In this work, similar as in (Xu et al., 2022), when the decision horizon is infinite, the discount factor only shows up in the algorithm and does not appear in the learning tar- get. The sole purpose of introducing discount factor is to decompose the single stream of interactions into "pseudo- episodes" that facilitate decision makiin... Such view aligns with the authentic role of discount factor in agent design, and distinguishes this work from earlier RL theory literature discounted regret such as (Dong et al., 2019a). While (Xu et al., 2022) focuses on PSRL, this paper is the first to extend the same view to a model-free algorithm that enjoys empirical successes.
Our Contributions We model the environment as a Markov decision process (MDP) with T aggregated states, and show theoretically that a cohort of N agents, concur- rently running RLSVI and sharing interaction trajectories with each other, are able to efficiently improve their joint
For instance, Arena, a world Icading startup that specializes in applying Al to shorten the hardware design loop, utilizes RL to speed up the circuit design, test and debugging cycles.
"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 sam- ple complexity performance measure (i.c. how many samples are needed to learn an e-optimal policy) under both finite action space setting and infinite action space setting. More specifically, (Guo& & Brunskill, 2015) provided high-probability bound of Ō(SAA + SAn) ) for the sample complexity with x agents inter- acting in the environment. Their algorithm was extended from MBIE(sce (Strehl & Littman, 2008)), with single agent perform- ing concurrent RL across a set of n infinite-horizon MDPs. The results there show that with sharing samples from copies of the same MDP linear speedup in the sample complexity of learn- ing can be achieved. But regret bound was derived there for concurrent RL.
Related Work Multi-agent Reinforcement Learning (MARL) has been widely studied to address problems in a variety of applications like robotics, telccommunications and e-commerce (Buşoniu et al., 2010). Scenarios of MARL.
2

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
include fully cooperative (Abed-alguni et al., 2015; Zhang et al., 2010), fully competitive (Bansal et al., 2017; Wang & Klabjan, 2018) and other more general settings (Ryu et al., 2021; Lowe et al., 2017). Under these settings, group of agents share and interact with a common random envi- ronment (Shoham& & Leyton-Brone BBrown 2008; Vlassis, 2022: Weiss, 1999). There are certain challenges of multi-agent systems as pointed out by (Zhang et al., 2021). For example, the agents may have non-unique learning goals (Shoham et al., 2003). Besides, the concurrent learning structure of MARL problem can cause the environment faced by each individual to be non-stationary. Particularly in some set- tings, the action taken by one agent affects the reward of other opponent agents and the evolution of the state (Zhang et al., 2021). Furthermore, to handle non-stationarity of the problems, the agents may need form the joint action space, and the dimension the action spaces can increase exponentially with the number of agents (Kulkarni & Tai, 2010).
As an outline of the rest of the paper, in Section 2, we define the finite-horizon case and introduce concurrent learning framework with aggregated states. In Section 3, we summarize the finite-horizon concurrent RLSVI algorithm in Algorithm 3 and provide its worst-case regret bound in Theorem 2. Section focuses on the infinite-horizon con- current learning framework with aggregated states, with the aufinite-hrizon concurrent RLSVI algorithm summarized in Algorithm 4. The corresponding worst-case regret bound is provided in Theorem 7 of Section 5. Numerical results of both algorithms are reported in Section 6. We also include Table in Appendix A comparing our approach with prior work.
2. Finite- Concurent Learning
In this section, we consider a cision Process (MDP) M = (H,S, S,A, P, R). There are N agents interacting with the same environment across K episodes. Each episode contains H periods. For episode k E [K], period h E [H], and agent p E [N], we use &h to denote the state that the agent resides in, ah,, the action that the agent takes, and P reward that it receives, where r : S A + [0, is a deterministic reward function. Let the information set Hr [( " r r h E [H] be the trajectory dur- ing episode k for all the agents. The transition kernel P is defined as a (s') = P2 (sh+1= = s' an = a, sh. = =s)
Markov De-
We study the MARL problem under a concurrent learning framework involving homogeneous agents with a common learning goal. The agents interact with the unknown envi- ronment independently in parallel, and draw actions from commonly shared action space. They communicate and share information according to some strategically devised schedule. All the agents share the same reward functions ac- cording to the states and actions they take. This is different from the Markov game setup (Szepesvári & Littman, 1999; Littman, 2001) where the reward is influenced by the joint action of all the agents in the system.
ki = r (x))) the
The expected reward that an agent receives state s when follows policy क at step h is represented by (M,,,=(s) E |EMEA (a(as) ((aass-((s)))) ((ssa))] We assume that all agents start from a deterministic initial state $ = {s ppe[n] with $ = sf. Vk,p. In this work we consider deterministic rewards, which can be viewed as mappings from S to A, but all our results apply to the environments with bounded rewards without change. We say that agent p [N] follows policy x if for all h E [H] af = Tr (s We use V. e RS to denote the value function associated with policy x in period h E [M], such that
We apply concurrent learning (Min et al., 2023; Dubey & Pentland, 2021) concept with the Randomized Least- Squares Value Iteration (RLSVI) learning framework with aggregated state representations (Dong et al., 2019b; Van Roy, 2006). On the one hand, RLSVI leverages random perturbations to approximate the posterior, applying frequen- tist regret analysis in the tabular MDP setting (Osband et al., 2016), inspiring works that focus on theoretical analyses to improve worst-case regret in tabular MDPs (Russo, 2019;
Agrawal et al., 2021) and linear settings (Zanette et al., 2020; Ishfaq et al., 2023; Dann et al., 2021). On the other hand, while a large body of literature is established on tabular rep- resentations (Agarwal et al., 2020; Azar et al., 2011; Auer et al., 2008; Jiang et al., 2017: Jin et al., 2018; Osband et al., 2013; 2016; Strehl & Littman, 2008), aggregated state repre- sentation offers an approach to reduce statistical complexity given the fact that the data requirement and learning time scales with the number of state-action pairs in tabular repre- sentations. In this paper, we present a concurrent version of the randomized least-squared value iteration algorithm with aggregated states in Enite-horizonn and infinite-horizon set- tings, and we provide their corresponding worst-case regret bounds and numerical performances.
H Σ
E
R (15))11 =
where the expectation is taken over all possible transitions, and we set (s) = 0 for all E S. The optimal value function is denoted as (s) = ma (s). which is the value function associated with the optimal policy. For all s E S, h E [H] and policy म, the value function the unique solution to the Bellman equations
V (s) = RR, + (Pshstos(')VV
#ES
3

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
When is the optimal policy π², there should be Vi (s) (s), and have
For the first empirical estimation method, define ng, (s, a) to be the number of times action a has been sampled in state 8, period & during episode k by all the agents p [N]]
(i(() a (o)
(s)
SES
T (s, a)
Σ p=1
(shnn (s, (s.
For each policy æ, we also define the state-action value func- tion of Q-function of state-action pair (s, a) as the expected return when agent takes action state s, and then follows policy so that
Define the empirical mean reward for period h during episode by
Exn { - (s, rk-
H Σ
n 1
(s)aa = Rh,s,atB.
(
=s, s,
and Ys' E S, define the empirical transition probabilities for period h during episode k as
Correspondingly, we define
Po (d)) Ep 1 [
(7, Rn,sa + Ps (s,
(oh- oh 1 o -1-1) = (8,,a,8)
where we use the notation Pa. Pr)(s, = [v(')- Thus by definition (s, a) is the maximum realizable ex- pected return when the agent starts from state s and takes action a at period h. From the optimality of V*, we have
(V(s))-
1R-1, (8,
If (h, 8, a) is never sampled during episode k - 1, we set Rk Rhe 0 E R and Pk Ph, = 0 E R$ Note that R and pk are computed from the trajectory from episode k 1.
Vy = max (7(s,a), Vh E [H] aEA
The second method stores all historical data up to the current episode, with the reward and transition probability estima- tions defined as:
Furthermore, under the assumption that the reward is bounded between 0 and 1, we have
(ST dhin)= = (s, a) r.. i=0 (8,0)))
S VI S V S H, 4h (H,
Bk.cu1 K,8,0
Regret under Finite Horizon Case The goal of an RL al- gorithm is for the agents to learn a good policy through con- secutively interacting with the random environment, without prior knowledge about the transition probability P and the reward R. Formally, given æ (M²P) kE[K),)EEE[)) with each agent p E [N] taking policy = during each episode k [K], the cumulative expected regret incurred over K periods and N agents is defined
( I Ep
1, ah shh+2) = (8, )'5))
2iz0 (s,a)
2.1. Aggregated-state Representations
Many RL algorithms aim to estimate the value of each state- action pair (e.g. under a tabular representation), but this can be infeasible some setup where SA is large, since both the required sample size and computational cost will scale up at least linearly in SA. One alternative approach is to consider aggregated- state representations (Dong et al., 2019b; 9b; Wen & Van Roy, 2017; Jiang et al., 2017), which reduces complexity and can accelerate learning by focusing on aggregated state-action pairs. This method partitions the space of state-action pairs into I' blocks, each block can be viewed as an aggregate state, so that the value function representation only needs to maintain one value estimate per aggregated state. Formally, let & be the set of all aggregated states, and let Φ : S x A + & be the mapping from state- action pairs to aggregated states at period h. Without loss of generality, we let tb = [T]. We define the aggregated representation as follows:
N K
Regret (M, K,K, H,K,H,
EVT -7(4)))V++088)) 1=1
(1)
Empirical Estimation We examine two types of empiri- cal estimation methods below. The first method stores data from single episode only, meaning the empirical counts used by the agents to evaluate policies are derived from just one episode. We take this limitation into account because, as the number of agents N increases, storing all historical data becomes practically infeasible. For the second method, we store all historical data; specifically, at each episode k; the buffer retains data from all episodes prior to k. This results in a space complexity of (KHN..

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Definition 1. We say that { is an e-error aggregated state-representation (or c-error aggregation) of MDP, if for all s, E S. a,a' E A and h e [H] such that (, a) = 0n(s', a'), we have
Each agent computes the values for aggregated states us- ing a backward approximation, where during episode k, the uncapped value of aggregated state y during period h computed by agent p is
[Q)(, - Vh(b S.
(2,(()
arg min C(QIQR, D ( QER
When < <= 0 in Definition 1, we say that the aggregation sufficient, and one can guarantee that an algorithm finds the optimal policy as K + so. When
+1Q 1, Cha
0, there exists an MDP such that no RL algorithm with aggregated state representation can find the optimal policy (Van Roy, 2006). In this case, the best we can do is to approximate the optimal policy with the suboptimality bounded by a function of e.
where (N)-1,a is defined as (7) for n = N Na-1 and we set terminal values as +1,)+1(7) = 0. and the reg- ularization noise 0h E RRSx is an independently sam- pled random vector, such that for each (s,a) E 8 x A, 3g
S (s, ~ (0: (+Neettt(otaa)) ): .B is tuning param- eter, and
3. Finite-horizon Algorithm and Regret Bound
The concurrent RLSVI R for the finite-horizon case are Algorithm 1 and Algorithm 3.
[(Q Quexis D) E(eende)D 1Q f- (11-))@-11
-a(r max.' Queu (s', a') d'))}²
Tradeoff: Regret Reduction vs. Sample Complexity Al- gorithm and Algorithm 3 reflect a trade-off between re- ducing the worst-case regret and the consideration for the sample complexity in practice. Algorithm stores all his- torical data, while Algorithm 3 retains only the data from the previous episode. Although Algorithm 1 achieves lower regret due to its larger data storage, it becomes impractical when N is large. Therefore, for practical reasons, we use Algorithm 3 in our numerical experiments. We first describe Algorithm 3, with Algorithm following a similar structure, differing only in the buffer size (i.e. the amount of data stored for policy evaluation).
(5)
Here the regularized loss function defined in (5) is such that Q(?) as the computed value of aggregated state y = on (s, a) for some pair (s, approximates
(1 ( LN a'EA
Q ,a)).
And since aN, 1M((T) = I+-No-1.41)) as defined in Theo- rem 2, we see that when (7) increases, the algorithm puts more weight on the value learned from the previous episode. At the end of episode k, after each agent inter- acts with the environment, the algorithm takes a weighted average of the values learned by each agent p E [N]. by taking
We initialize the all the aggregated state values H, i.e. (7()) H for all h E [H]. At the beginning of each episode, all the agents restart at initial states $1 = {s with agent p starting from state sf. During pre-round (episode 0), each agent randomly samples their initial trajectory (s0.1, "6, ",,,., &0, oh, r IN with o0, = s.. 10,1)
N 1 (h 7 (7)
Qx,(77) = (7.
Σ p=1
(6)
During each episode h E [K], each agent samples ran- dom vector with independent components wh E RSA where (h, 8, a) (O, of,,, 8, a)) and (z 8, a) where Bx is tuning parameter, N N a)) )) is the total number of times that aggre- gated state (n (x, a) is reached at period h across all agents during episode k 1. Given WtP we construct a randomized perturbation of the empirical MDP for agent p as
for each y E I, where (7) is the total number of times that aggregated state 7 appears during episode l period h.
Given tuning parameter 3 (aR we denote Algo- rithm 3 by RLSVI While Algorithm 3 is based on the RLSVI algorithm of (Russo, 2019), there are some notable differences. The algorithm of (Russo, 2019) is with single- agent, and at each time period during episode k;, the agent needs keep all the trajectory prior episode k which can be infeasible for multiple agents, because the space can grow very fast. In our algorithm, we only keep the historical data of the last episode, to make the algorithm computationally feasible. This leverages the fact that with N agents interacting with the random environment, the information within one single episode is already rich. Al- gorithm 3 is also related to the aggregated-stee -tate algorithm
91 V (o
M (H, SH, Rtt + WP)),
(4)
where the empirical distributions Re ps are computed as in (2) and (3). During each episode k E [K], the data set DP contains perturbation of samples from episode & - for time period used by agent p.
5

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
proposed by (Dong et al., 2019b), where the authors ap- ply the aggregated-state idea optimisitic variant of Q-learning a fixed-horizon episodic Markov decision process based on the previous UCB-type result by (Jin et al., 2020). Our work incorporates this idea in the concurrent randomized least square value iteration.
Since the only difference between the algorithms is the amount of data stored, and their structures identical, we only prove (9), with (8) following immediately by reducing factor of K from the regret bound in (9). We omit the redundant proof for Algorithm and defer the proof for (9) to Appendix C.
Algorithm I follows a similar structure, with (e,A (s, a)) redefined as the total number of times the aggregated state Φn (s, a) is visited at period h across all agents up to and including episode k. We denote it by RLSVIE to indicate that Algorithm uses the full history up to the current episode.
Comparison with worst-case regret bounds from (Russo,
2019; Agrawal et al., 2021) A worst-case regret bound of (3H253////RR was obtained in (Russo, 2019) for a single-agent version of RLSVI algorithm. This bound was improved later by (Agrawal et al., 2021) to ((H5/2/AA)) For the single-agent case with N = 1. Algorithm results in a worst-case regret bound of Ö(v OVVKH5/2T H$/2T), which translates into Ö(HTTVT) So our bound matches that of (Agrawal et al., 2021) if = x A and S ~ vT. Algorithm 3 implies worst-case regret bound of OKK of (Agrawal et al., 2021; Russo, 2019) comes from the fact we only keep the trajectories of the agents from the previous episode rather than all the episodes up to the current period as in (Russo, 2019; Agrawal et al., 2021) to reduce space complexity. The extra term for both algorithms comes from model misspecification of state-aggregation formula- tion, which is similar to the result in (Dong et al., 2019b).
With the employment of aggregated state and the modified loss function for the learning process, the result highlights that the per-agent regret decreases at rate of θ VN The concurrent learning algorithm for the finite- horizon case is Algorithm 3. The worst-case regret bound for Algorithm 3 provided in the next section.
Here an extra K compared to that
3.1. Worst-case Regret Bound
Let M be the set of MDPs with episode number K, horizon H, state space size S, action space size A, transition prob- abilities P. and rewards It bounded in [0, 1]. Let N be the number of agents interacting in the same environment. We use M = (K, H. A, P, R) to denote an MDP in M.
At each time period h. each agent gets N samples of tuples (s, a, r; s"), and they share information by the aggregation of information through the computation of a weighted Q-value (6) at the end of each episode. With this trick, though agents learn their own policies concurrently in parallel within each episode, we able obtain a sub-linear worst-case regret bound of (VVN) with respect to the number of agents.
Suppose { JNE is an e-error aggregation (defined as in Definition 1) of the underlying MDP. For a tuming parameter sequences 3- = {8n JnN,, a- = {an) 5 = {Ehhne where 3n- 1 3 (2gg2HTT)) an 14m and
2
En =et 2a H / Vlog (2KK//
V /max (n, 13 20 V BB-1 log(2K HN/8)
4. Infinite-horizon Concurrent Learning
(n + 1) max(n, 1}
We now turn to the hnfinite-horizon case. Consider an un- known fixed environment as M = (T, A,,,, S, P,r, N), with N agents interacting in M. Here A = [A]] is the action space, S = [S] is the state space, P(s' | s, a) is the transi- tion probability from 8 E S to s' E S given action E A. After agent selects action of at state si the agent observes Sh+ and receives a fixed reward rft1 = r(st' a²) where r E [0. 1]. A stochastic policy π can be represented by a probability mass function T (T((s;) that an agent assigns to actions in A given situation state st. For a policy म, we denote the average reward starting at state
We now provide our main results for the finite-horizon case. As explained, Algorithm stores all historical data, while Algorithm 3 retains only the previous episode, making it straightforward that Algorithm has a space complexity of O(K N),, while Algorithm 3 has a space complexity of O(HN), and their worst-case regret bounds are Theorem 2. Algorithm 1 has a worst-case regret bound
sup Regret(M, [M, K,N, N, RLSVI
MEM
(8)
< &H(eVKHN + H//IVK.N
Algorithm 3 has worst-case regret bound
Am (s) lim inf E 7-
1 T
Tt+l 81
(10)
sup Regret K,N, N, n, RLSVIS,a.E) MEM
< <O(CKHN + KVN),
For any state s E S, denote the optimal average reward as Xx = sup, (s). We consider MDP, which is defined as follows:
where Ō(-) hides the dependence on logarithmic
6

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Definition 3 (Weakly-communicating MDP), MDP is weakly communicating if there exists closed subset of states, where each state within is reachable from any other state within that set under some deterministic stationary reward. And there exists a transient subset of states (possibly empty) under every policy.
for E Eg, and Eg denotes the time steps within pseudo- episode k. So the discounted regret is random variable depending the algorithm's random sampling, and the random lengths of the pseudo-episodes, and as result,
4 EH
( Ta PRtoT M
For any s E S and a E A. denote Ps.as'' = P(s"|s, (1s"|s,a). a). For each policy и define transition probabilities under π as Pa Pa = EnEA (a))s) and reward as Ta, EGEAT(als)re ((als)r(s..)
A=
E
o (P - PRROTTND) M
Regret The optimal average reward X. is state- independent under a weakly-communicating MDP. The agent p selects policy kD and executes within the kth pseudo-episode. The cumulative expected regret incurred by the collection of policies time steps and across N agents with the fixed environment M is
Pseudo-episodes We extend our concurrent learning framework for the finite-horizon case to the uninite-horizon case by incorporating the idea of pseudo-episodes from (Xu et al., 2022). Suppose time step is the beginning of a pseudo-episode when we sample a random variable H Geometric(1 n),, where Geometric(1 - 7) is geo- metric distribution with parameter 7/. In the numerical experiment (section 6), we set 0.99. The agents com- pute new policies respectively according to the collected trajectories from last speudo-episodd, and sample their own MDPs respectively at time steps + 1,...., + H - 1. Now the beginning of the next pseudo-episode is set as t + H. We use H,,,,, - - (sf.at a. r to denote the tra- jectories of all agents from time step i to time step f-- For policy n, denote the d-discounted value function V E RRS, then we have
("""" (e((K) pE[N] over T
K Σ
== EK
/ M
(12)
where the expectation is taken over the random seeds used by the randomized algorithm, conditioning on the true MDP M. In the following, we denote (s a k. as the state, action and reward for agent during pseudo-episod k and period h.
Empirical Estimation We let nu a) be the total num- ber of times that (s, a)-iir appears during the ttth pseudo- episode, such that
H-1
V = EH
Σ hm
P
M =
E
Σ 1h=0
Ph n
M
(11)
N fx11-1
where the expectation is taken over the random episode length H. A policy is said to be optimal if 1/2 sup,r V.
(s,
Σ
Σ 1 1 = =(s)))))=(ssa)}
For optimal policy, we also write (s) (s) the optimal value. Note that V E R$ satisfies the Bell- man equation V = ra + nP, V7. For any (s, a). define (2, a) = r(s.a) + 7PVP(()) (s), where we use the notation that P2 (s) = E.'mP.. (o) (s').. Correspondingly, define
Then Vs', the empirical estimate P (s'|s, a) of the transition probability for pseudo-episode k is
Pr ss' () Σ Pp=1 EiELL 1 [[ s4, (s, 8')
(7 a) = r(s, a) + (s))
ng- 1 (8,
(13)
By definition, we have (s) A (s)s.)).
The empirical estimate of the corresponding reward is
Rs a) Σx [(( = (s, EiEEr_, r(5 af) (s,)
Discounted Regret To analyze the algorithm over T time steps, consider K arg maxik: to T as the number of pesudo-episodes until time T'. We use the convention that tk+1= = T+1. Given a discount factor [0, 1), define the dpdisccutted regret up to time T as Regret, ,, (M, T, T) = Ek= Ag. where A& is the total regret of all agents over meudo-episode k: A& = E V2" (s Vi (s where V/- = v policy ~ is computed from the trajec- tory H4g-1 from pseudo-episode & by agent p. and of ~ π (. (: 8)), 2p P(+ a²), r(sh, af)
(14)
For the second empirical estimation method, we utilize the full historical data, and similar to the finite-horizon case, the empirical estimates for transition probability and reward are
foulll (s')s, D Exe EiEF, 1 of, (s,
Σ/=1 ()(),a)
7

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
R (s,a)
Bx. 1 on "tt and
Epmi Eizo 1 ((, a. = = (s.a)) af) --1 - a))
2a, logg(2TN//)))
Sn =ct (1 - 1) max n, 1]
(15)
Aggregated States We extend the aggregated states in the finite-horizon case to the infinite horizon case. Let & be the set of all aggregated states, and let ø S x A + Φ be the mapping from state-action pairs to aggregated states.
2an V (B-1 log (2TN/6)
v(n + max maxx
Theorem (Infinite-horizon Worst-case Regret Bound). Algorithm 2 has a worst-case regret bound
We let [T] The aggregated representation for the infinite-horizon case is defined as follows:
SUPMEM Regret [M, T,N, RLSVI (ull) S &(eeVTN + (TT).
3,0.
(16)
Definition 4. We say that an E-error aggregated state- representation (or e-error aggregation) of an MDP, for all s, s' E S. a, a' A such that Φ(s, a)) 0(s', a'), we have (s, (s's ,a)) S.
Algorithm has a worst-case regret bound
SUPMEM Regret(M. T,N, N,RLLA RLSVVI...)) I SÕ(ENN +
(17)
We are now ready present the concurrent learning al- gorithm for the infinite-horizon case and the theoretical guarantee, as detailed in the next section.
Note that the bound in (17) matches that of the finite- horizion case (9) by noting that T KH for the finite- horizon case. And 73/2 corresponds to the H3/2 factor in the finite-horizon case bound by noting that taking = H makes the condition holds in Definition 5 in the finite- horizon case with T = H.. Similar to the finite-horizon case, (16) follows directly from (17) with /T reduction, as Algorithm utilizes the full history. whereas Algorithm retains only the last pseudo-episode. The intuition and worst-case regret comparison follow the discussion after Theorem 2.
5. Infinite-Horizon Algorithm and Regret Bound
The concurrent learning algorithm for the anfiite-hooizon MDP is summarized as Algorithm 4. Our result is based on the following definition of reward averaging time proposed by (Dong et al., 2022).
Definition 5. The reward averaging time Ta of policy π is the smallest value t E [0, 2o) such that VT 2 0,8 E S,
Ex
E. T1+1 9o = s T An (s) ST.
6. Numerical Experiments
Typically the regret bounds established the literature re- quires assessing an optimal policy within bounded time. Examples include episode duration (Osband et al., 2013; Jin et al., 2018), diameter (Auer et al., 2008), span (Bartlett & Tewari, 2012). Policies that require intractably large amount of time are infeasible in practice. So we impose the following assumption:
We present numerical results for both finite-horizon and infinite-horizon cases in Figure 1. For the finite-horizon case (S, A, K, H) or the infinite-horizon case (S, T), the transition probabilities are drawn from Dirichlet distribution, and rewards, fixed as deterministic, are uni- formly distributed on [0, 1]. forming inherent features of the MDP class. The finite-horizon case settings are (i)
K = 20, H = 30, = 5, A = 5; (ii) = 25, H 10: (iii) K 30, H 50, S
Assumption 6. For any weakly communicating MDP M with state space S and action space A, 3r < oo such that Tx S T.
40,
10,
with 20, A 20. The infinite-horioon case settings
T == 300 and (i) S 5, A 5; (ii) S = 20, A 20; (iii)
S = 30, A 30, where 17 0.99 in the pseudo-episode sampling. Under each setting, we compare the results for
When x² is an optimal policy for M, Tx Ta is equiva- lent to the notion of span in (Bartlett & Tewari, 2012). Let M be the set of finnite-horizon weakly- communicaimiiii MDPs with state space size S, action space size A, rewards bounded in [0, 1] that satisfy Assumption Let N be the number of agents interacting in the same environment. Re- call that is given by Assumption 6.
= 1,3, 5, 7, 10, 15, 20, 30, 40, 50, with = 0. We set r) = 0.99.
For each agent number N in the finite-horizon setting, we sample 500 MDPs from the defined class. For each sam- pled MDP, we compute the cumulative regret over time and then identify the maximum regret across all 500 instances, representing the worst-case regret in our analysis.
Suppose {Φ} is an e-error aggregation (defined as in Definition 4) of the underlying MDP. For a tuning pa- rameter sequences B = {8nheen, a = fan)nes. = (En)e where for i as the index of pseudo-episode,
For the anfiite-hhorioon setting, we estimate regret by av- eraging over 50 geometric segmentations of [T) per MDP,
8

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
consistent with the definition of infinite-horizon regret based on pseudo-episodes in (12). The worst-case regret then obtained by taking the maximum across 500 sampled MDPs.
consequences of our work, which we feel must be specifically highlighted here.
Figure illustrates a 1 1/VN decreasing trend in per-agent regret for both settings, consistent with our theoretical predictions. The replication code is available at ht ttsp:: //github. com/ yz htapg///rlliiiieeee risvi_code.
References
Abed-alguni, B. H., Chalup, S. K., Henskens, F. A., and Paul, D. J. A multi-agent cooperative reinforcement learn- ing model using hierarchy of consultants, tutors and workers. Vietnam Journal of Computer Science, 2:213- 226, 2015.
Reba-lletoon Besdggert Regret
Agarwal, A., Bird, S., Cozowicz, M., Hoang, L., Langford, J., Lee, S., Li, J., Melamed, D., Oshri, G., Ribas, O., al. Making contextual decisions with low technical debt. arXiv preprint arXiv:1606.03900 2016.
X009
regresd 500/01 rigins
4067
10gm
0223
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. Op- timality and approximation with policy gradient methods in markov decision processes. In Conference Learning Theory, pp. 64 66. PMLR, 2020.
52223
30
Agrawal, P., Chen, J., and Jiang, N. Improved worst-case regret bounds for randomized least-squares value itera- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6566-6573 2021.
WirBeellttoon Tentgent Bagnet
Trubl Andil Twit3
5500 Hights
10000 100700
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
12322
Azar, M. G., Munos, R., Ghavamzadeh, M., and Kappen, H. Speedy q-learning. In Advances in neural information processing systems, 2011.
2382
Marbo Agent 111
Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mor- datch, Emergent complexity via multi-agent competi- tion. arXiv preprint arXiv: 1710::77, 2017.
Figure 1. Per-agent regret number of agents for finite-horizon (top panel) and infinite-horizon (bottom panel) settings. The solid curves represent the per-agent worst-case regret computed from 500 random environments. The dashed ones are the reference curves of constant/ / /N fitting the (1///N) trend as we show in our theoretical results.
Bartlett, P. L. and Tewari, A. Regal: A regularization based algorithm for reinforcement learning in weakly commu- nicating mdps. arXiv preprint arXiv:1205.2661. 2012.
Buçoniu, L., Babuška, R., and De Schutter, Multi-agent reinforcement learning: An overview. Innovations in multi-agent systems and applications-I, pp. 183-221, 2010.
Acknowledgements
We gratefully acknowledge the support from the NSF grant CCF-2312205 and the ONR grant ONR 13983263. We would like to thank Pratap Ranade and Engin Ural for in- spiring discussions on society of agents that have helped shape and push ambitious vision of this research agenda, for which this work is only initial step.
Chen, Y.. Dong, P., Bai, Q.. Dimakopoulou, M.. Xu, W., and Zhou, Z. Society of agents: Regret bounds of concurrent thompson sampling. In Advances in Neural Information Processing Systems, 2022.
Impact Statement
Dann, C., Mohri, M., Zhang, T., and Zimmert, J. A prov- ably efficient model-fred posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 14:12000-12011 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Desai, N., Critch, A., and Russell, S. J. Negotiable rein- forcement learning for pareto optimal sequential decision- making. Advances in Neural Information Processing Systems, 31, 2018.
Ishfaq, H., Lan, Q. Xu, P., Mahmood, A. R., Precup, D., Anandkumar, A., and Arizzadenesheli, K. Prov- able and practical: Efficient exploration in reinforce- ment learning via langevin monte carlo. arXiv preprint arXiv:2305. 18246, 2023.
Dimakopoulou, M. and Van Roy, Coordinated explo- ration in concurrent reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 1271-1279. PMLR, 2018.
Janz, D., Hron, J., Mazur, P., Hofmann, K., Hernández- Lobato, M., and Tschiatschek, S. Successor uncertain- ties: exploration and uncertainty in temporal difference learning. Advances in Neural Information Processing Systems, 32, 2019.
Dimakopoulou, M., Osband, I., and Van Roy, B. Scal- able coordinated exploration in concurrent reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Jiang. N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Con- ference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Dong, K., Wang. Y., Chen, X., and Wang. L. Q-learning with UCB exploration is sample efficient for aufiite-horizon MDP. arXiv preprini 1rXXiv/901.000 0.0311,,,,,,,... 2019a.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q- g-learning provably efficient? Advances in neural infor- mation processing systems, 31, 2018.
Dong, S., Van Roy, B., and Zhou, Z. Provably efficient reinforcement learning with aggregated states. arXiv preprint arXiv: 1rXiv:9122.06366, 2019b.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Dong. S., Van Roy, B., and Zhou, Z. Simple agent, complex environment: Efficient reinforcement learning with agent states. Journal of Machine Learning Research, 23(255): 1-54, 2022.
Kim, M. Thompson sampling for stochastic control: The finite parameter case. IEEE Transactions on Automatic Control, (2(12)6411-6422 2017.
Dubey, A. and Pentland, A. Provably efficient cooperative multi-agent reinforcement learning with function approx- imation. arXiv preprint arXiv:2103.04972 2021.
Kulkarni, J. and Tai, Probability collectives: multi- agent approach for solving combinatorial optimization problems. Applied Soft Computing, 10(3):759-771, 2010.
Dwaracherla, V., Lu, X., Ibrahimi, M.. Osband, I., Wen, Z., and Van Roy, B. Hypermodels for exploration. arXiv preprint arXiv:2006.0744 2020.
Littman, M. L. Value-function reinforcement learning in markov games. Cognitive systems research, 2(1):55-66, 2001.
Fellows, M., Hartikainen, K., and Whiteson, S. Bayesian bellman operators. Advances in Neural Information Pro- cessing Systems, 34: 14:13641-13655 2021.
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competite environments. Advances in neu- ral information processing systems, 30, 2017.
Gu, S., Holly, E., Lillicrap, T., and Levine, S. Deep rein- forcement learning for robotic manipulation with asyn- chronous off- off-policy updates. 2017 IEEE international conference on robotics and automation (ICRA). pp. 3389- 3396. IEEE, 2017.
Min, Y., He, J., Wang, T., and Gu, Q. Cooperative multi- agent reinforcement learning: Asynchronous commu- nication and linear function approximation. In Inter- national Conference on Machine Learning, pp. 24785- 24811. 1. PMLR, 2023.
Guo, Z. and Brunskill, E. Concurrent pac rl. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 30, 2015.
Osband, I. and Van Roy. B. Model-based reinforeement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Ishfaq, H., Cui, Q. Nguyen, V., Ayoub, A., Yang. Z., Wang, Z., Precup, D., and Yang, L. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pp. 4607-461 PMLR, 2021.
Osband, I. and Van Roy, B. On optimistic versus randomized exploration reinforcement learning. arXiv preprint arXiv:1706.0424: 2017.
10

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Osband, I., Russo, D., and Van Roy, B. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Taiga, A. A., Courville, A., and Bellemare, M. G. Introduc-
ing coordination in concurrent reinforcement learning. In ICLR 2022 Workshop Gamification and Multiagent Solutions, 2022.
Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. Deep exploration via bootstrapped DQN, Advances neural information processing systems, 29, 2016.
Van Roy, B. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 31(2):234-245 2006.
Osband, I,, Van Roy, B., Russo, D. J., Wen, Z., et al. Deep exploration via randomized value functions. J. Mach. 2019.
Vlassis, N. A concise introduction to multiagent systems and distributed artificial intelligence. Springer Nature, 2022.
Learn. Res.,
Pazis, J. and Parr, R. Efficient pac-optimal exploration in concurrent, continuous state mdps with delayed updates. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 30, 2016.
Wang, X. and Klabjan, D. Competitive multi-agent in-
verse reinforcement learning with sub-optimal demonstra- tions. In International conference on machine learning. pp. 5143-5151. PMLR, 2018.
Russo, D. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Weiss, G. Multiagent systems: a modern approach to dis- tributed artificial intelligence. MIT press, 1999.
Russo, D. and Van Roy, B. Learning to optimize via poste- rior sampling. Mathematics of Operations Research, 39 (4):1221-1243,, 2014.
Wen, Z. and Van Roy, B. Efficient reinforcement learn- ing in deterministic systems with value function gener- alization. Mathematics of Operations Research, 42(3): 762-782, 2017.
Ryu, H., Shin, H., and Park, J. Cooperative and competi- tive biases for multi-agent reinforcement learning. arXiv preprint arXiv:2101.06890 2021.
Xu, W., Dong, S., and Van Roy, B. Posterior sampling for continuing environments. ArXiv preprint, 2022. URL ht/p/axxvvvvvo http://aaaxiiv.ooa///////////// 15931.
Shoham, Y. and Leyton-Brown, K. Multiagent systems: Al- gorithmic, game-theoretic, and logical foundations. Cam- bridge University Press, 2008
Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020.
Shoham, Y., Powers, R., and Grenager, T. Multi-agent reinforcement learning: a critical survey. Technical report, Citeseer, 2003.
Zhang, K., Yang, Z., and Başar, T. Multi-agent reinforce- ment learning: A selective overview of theories and algo- rithms. Handbook of reinforcement learning and control, pp. 321-384, 2021.
Silver, D., Newnham, L., Barker, D., Weller, S., and McFall, Concurrent reinforcement learning from customer inter- actions. In International conference machine learning, pp. 924-932. PMLR, 2013.
Zhang, P., Ma, X., Pan, Z., Li, X., and Xie, K. Multi-agent cooperative reinforcement learning in 3d virtual world. In Advances in Swarm Intelligence: First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part 1, pp. 731-739. Springer, 2010
Sinai, S., Wang, R., Whatley, A., Slocum, S., Locane, E., and Kelsic, E. D. Adalead: simple and robust adap- tive greedy search algorithm for sequence design. arXiv preprint arXiv:2010.02144 2020.
Strehl, A. L. and Littman, M. L. An analysis of model- based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8): 1309- 1331, 2008
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Szepesvári, C. and Littman, M. L. A unified analysis of value-function fone-fu-uciioobeeedddd reinforeement-leamine algorithms. Neural computation, 11(8):211722600, 1999.

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
A. Comparison Table: Existing Work vs. Our Approach
Table 1. Comparison of regret bounds for various RLSVILSVI algorithms
Agent
Sctup
Algorithm
Regret Bound
Regret-Type
Data Stored
Numerical
Single
Tabular
RLSVI (Russo, 2019)
5 VAK)
Worst-case
All-history
N/A
Single
Tabular
RLSVI (Agrawal et al., 2021)
O S AA
Worst-case Bayes
All-history
N/A
Multi
Tabular
Concurrent RLSVT (Taiga al., 2022)
N/A
All-history
Synthetic
Multi
Linear Functional
Concurrent LSVI (Desai al., 2018)
Ö(H'V
Worst-case
All-history
N/A
Approximation
Linear Functional
Multi
Concurrent LSVI (Min et al., 2023)
((HVKKN)
Worst-case
All-history
N/A
Approximation
Multi
Tabular
Concurrent RLSVT (ours-1)
Ö(H2/ST KNN
Worst-case
All-history
N/A
Multi
Tabular
Concurrent SVT (ours-2)
O(H"TTVN Worst-case
One episode
Synthetic
We outline several key observations for Table below:
The methods marked as "N/A" " in the "numerical" column store all agents' trajectories at every step, making them computationally infeasible as N grows large. These approaches (including our first finite-horizon algorithm, second-to- last row in the table) provide only theoretical analyses without numerical results.
Although Taiga et al. (2022) stores all data empirically, their RLSVI algorithm assumes known parametric feature matrix, making it simpler to implement than ours. Also they evaluate only Bayes regret-less stringent than our worst-case regret- and provide empirical results exclusively on synthetic data without theoretical guarantees.
The last row corresponds to storing only the latest episode data, increasing the regret bound by a factor of VK but reduces space complexity by factor of K, making it computationally feasible.
B. Algorithms
Algorithm and Algorithm 3 finite-horizon algorithms, where the former stores all historical data, and the latter only keeps one episode in the buffer. Algorithm and Algorithm 4 are infinite-horizon algorithms,, where the former stores all historical data and the latter only keeps one pseudo-episode.
12

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Algorithm Concurent RLSVI: Finite-Horizon Storing All Historical Data
Data: K, 81, (dx )
Tuning parameters {Be)KeN
Define constants ag +- 1- 1.2....
<* Define squared temporal difference error x/
A(Q) Qk-1,h: Quex. &, a) E(sana)ED( - -1-0----00------00----
a(r + max. EA Qnexi d²)))²
Initialize:
%o (1) = H, 4h E [H] [ E [N]
Each agent randomly samples the initial trajectory ( o r............................... 6 0
H 0.11p=m with s6,1 = 8
(7) Σ
(s o 7). vy h [M]
p=1
compute Qo by (6)
for episode = 1,2, 1.. do
/*Each agent rollouts in the evironment* for p p=rp= do parallel+/
*Executed for period h .,..., H do
o,, arg max bh - ( ( (+ a)) observe reward rh and next state s kth++1
Dj + Dr U Uf af 2 k o k
end end
/vvisitation of aggregated-states>
Nk,((7) + E En ( a''N) = Vy
/*Construct perturbed data sets and sample regularization noise Q+/ for [N] and E [ do /xExecuted in parallel*/
For any ()) E S A, sample array Q% ~ N (0, (o /* Draw prior sample +/ D 0
for (s, E DD do
Sample w (s, ~ ~N( N((1, (0, I+Nan((n(saa)) Dr Dr U a, 8'))
end
end
#Estimate perturbed data*/ for p por==1..... NN do /*Executed in parallel*/
Define terminal value Qk (1) +- H [
for period h = H. .. do
(h,(1) arg min L(Q)Q=-1.)) Q Dh + I|Q (N) Rh 11.. Vy [r] (7)(7) - min (7), H), by e []]
end
1 - sf
end
Update (7), Vy E by (6)
end
13

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Algorithm 2 Concurent RLSVV: Infinite-Horizonn Storing All Historical Data
Data:
Discount factor 7,, l0 = 1, 1, 0, X1 = 0, A, N,T, é, tuning parameters {Bx MEN.S.M Initialize (*) + 0, vy E [[ E [K]; Q0(7) - v
Define constants 04 + (1 + t), = 1,2,...
* Define squared temporal difference error */ [(Q Q mexts D, 7, = (e n ( a a)Q anf( maxa'e Queals',
Sample Ho ~ Geometric(1 7), set Ho -- min m T + -
Each agent randomly samples the initial trajectory {s oi p ........ H. H. Ho with s0, sy Ho
k k 1, ls
tR the start time of pseudo-episode k
while t < T do
Sample ~ Geometrie(1 - '7)
H mi,
t++1 tx H (the start time of pseudo-episode
/*Each agent rollouts in the environment x/ forp p= 1....... N do
*Executed in parallel*/
ort=t,,.... t.1, af araggmax (o(s, a)) observe reward of and next state 1
Dr DD DR U ((5), ap. ((11)
end
/* Visitation of aggregted-states +/
Nx-1(7) + Ep= E (o(s),a) = 7h Vn E
end
* Construct perturbed datasets and sample regularization noise Q +/ for p E [N] and = 441
* Executed in parallel +/
Sample array (s) a) N(0, Nr (6 ) ((s.))
Ax -
/* Draw prior sample
< +-
for (s, r',) E Da do
/* Randomly perturb data x/ ( Sample (s,a) ~ NO( No 1(0(8,))+1) Hr < Hg ((s,a,r wP, s')
end end
* Estimate Q on perturbed data +/
for 1... N do
>* Executed in Parallel x/
Define terminal value Qh (7)
Vy [T]
for t = t&+1 - -1, 1,....th do
/x Estimate Q on noisy data x/
Q + arg min L(Q QR-1, Pun Hb. &. aN, (6)))()))) 11Q naN, ((7) 2111
Q + min 1. Vy E [T]
end
sf,
s/. Vp [N].
end
Qe(r)= Σx Eier 1((6, (f)
Vn T
Ne(7)
t 4+1. k. + 1+1
end
14

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Algorithm 3 Concurent RLSVI: Finite-Horizon (Storing the Data of One Episode)
Data: K, S,A,N,,, (ox ) k=1 Tuning parameters (EE) Define constants a + 1/(1 + +t, t- 1,2....
/* Define squared temporal difference error x/
[(Q) Qk- Qeen, D, a) = ((aandre - - (11-a)0=1n((0(ss000 - a(r + max Quex((', d))))²
Initialize:
0% (y) H, wh [H], [F], E [N]
Each agent randomly samples the initial trajectory ( (611:%,11 o r 0. H H r 0.11p=1 with 8/11 =8
N (7) = Σ
(s (,,)) = >) vy E h [H]
p=1
compute Qo, by (6)
for episode =,2,.... do / />ach agent rollouts in the evironment*
for l,..,. N do + *Executed in parallel+/
for period h = l...., Ho
K,,, + arg ma ( a)) observe reward kh and next state s kk,+1 D + D U {(s a r, s x
end end
WWisiitation of sngregated-statess.
Nk.(1) + Ep=1 1f ( = >) by E [T] [H]
/*Construct perturbed data sets and sample zeqularization noise Q+/ for forp [N] and [H]
/+Executed in parallel+/
For any as E ES (s, N (0, (o /* Draw prior sample +/ P 0
A, sample array
for (s, (s,a,r,s)) E D do
Sample wn (s, ~ N (0, [+Naa(
D% - DP U [(s a + wP, s')
end end
/ + #Estimate on perturbed data+/ for p 1... do / /*Executed in parallel*/
Define terminal value Qh (n) + H E
for period H,...,
(rr(T) + arg mingeR L(Q)Qx-1.M) Qu Dr D (, + I|Q aN. (h Vy E [T]
(7, - (7), Vy E [1]
end
$11 s/. Di,- 0
end
Update Qx.((T), Vy E [T]by (6)
end
15

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Algorithm 4 Concurent RLSVI: Infinite-Horizon (Storing the Data of One Pseudo-episode)
Data:
Discount factor 7,, lo = 1, 1 1, k = 0, X1 = A, 6, tuning parameters {3x MENN..m Initialize (7) + 0, vy E
Define constants 0ę + 11 [T] k E [K]; Q(()) + e
1,2,
* Define squared temporal difference error */
[(Q) Q Qext m, a) " (e nf - 71 - a)Q a)) an(( + max Queals' (
Sample Hg ~ Geometric(1 7), set Hg f- min Hb, 7 +
Each agent randomly samples the initial trajectory (6),1 o 0.10 n. o r 1. with s6, Ho
& k 1, & the start time of pseudo-episode &
while t S T do
Sample ~ Geometric(1 - '7)
t&+1 6 12
H (the start time of pseudo-episode k
/>Each agent rollouts in the environment x/ for L...,, do
/EExeutted in parallel*/ for tort=1 l.,..,,, ..s....,44111-1 1 of + arg aax (o(s, a)) observe reward ri and next state 1/
De DR U ((6 af o s(1))
end
/* Visitation of aggregated-stater +/
- Nx-1(7) + Ep En Ho(s = = Vy E [T]
end
Construct perturbed datasets and sample regularization noise Q +/ for E [N] and = .,....,, --., 11 do /+ Executed in parallel +/
AN (
Sample array (s, a) ~O, N 1 (ss
/* Draw prior sample
Hg +
for (s,a,r, Dz do
/* Randomly perturb data +/
Sample (s, ~ NOO, AN. (((ca()
(
He - H. a(s, + wP, s²)
end end
* Estimate Q on perturbed data */ for p = I....., N do
* Executed in Parallel */
Define terminal value (i + [r]
for = (x+1 1,..., l do
/+ Estimate Q on noisy data */
Q arg minqER L(Q Qk-1, Qhin Hb, aN)- + 11Q naNx-1 Q.
Q t min 1-n 1. By E [T]
end
sh Vp [N]: D₁ V.
end
Σn Eleus 1(0(0)
Qx(r)= = EY
Ne(7))
l + 1411 k t- k+1
end
16

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
C. Proofs for the Finite-Horizon Case
In this section, we prove the worst-case regret bound for the finite-horizon case. We use the following notations:
(():: (r)) the number of visits to aggregate state at period h from episodes 0 to A: 1.
(1): total number of agents who visit aggregate state yy during episode l and period h.
rpP the greedy policy with respect to &i i.e. the policy that the agent p follows to produce the trajectory
$1 1, K......, k o
K. r R
7/ (s): the state value function estimate at period h, induced by Q (7) through
V 1 (s)
max .EA
(
VP(M, ):: the value function corresponding to policy æ from the initial state s7. where of is the initial state of agent at the beginning of each episode. For the true MDP we have (s = VP(M, T).
V (st) V*MM" T)):: the value function corresponding to MDP M/" with initial state of and policy nhp, where MDP M kp defined as (4).
For any 7 E [T]. we define the following events:
No (7)
E(7) =
Σ
1f0n(s 110 HV (8%-1)))) Ps (5 (5 (582
N N1-1
(18)
2H (og((K
(NN-1A(7)
Ne-1a(7)
960)=
Σ
(o 7) 1. 1, oz 1.
Nk-1,1(7)
1=1
(19)
V /BB (og228))
S2
(W + 1)
C.1. Proof of Finite-Horizon Main Result: Theorem 2
Proof of Theorem 2. Following the derivation of (37) and (38) in Lemma 11, have
EnErry DK VNL 1n(741 EH ΣK
k= Ejer Ej=1
1,1()) 1
43
(20)
< Sk Σ# Exerr 2 2v/ s KHT Σk= Σ# Exerry Nn.(77)= 2
2KH
and
N Σ K k= Σk= VNx-inilll
- m= Ek=l EyE[r] Ej V3
K
NK-11(())
DH ΣK Σve(r] 2 2 NVNa-1,647
< 2/ HKT -1 k Ene(r) N4-1,1(7)
2HKVTN.
Under events E(GL)) Vith E [T). we have
17

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
RMg K, N, RLSVI3,..)) ,L, = Ex Ep= (i V (5 S E Ep=r Vx,1(s9) V - (sf).
Recall from Lemma 11 that when ((hhk) and G(Tkh)) hold for all The E [T'} with probability 1 28, we have
N
K
Σ
Vp 1 (+f) - 1770019
p=l
k=1
HcKHN SKH&VTN (og(2KHN/8)) + 32H VKTN (logHHKN/5) +2K /OOTT//N//OHHKTYY//ZZTHH (/1/2
Note that by (18), (19) and the first statement of Lemma 10, we have
P(E(TRA) Tee AK E PH (N])
2 1 1 (PEE (P(E(T)A) )9) + ((G((T))))
(21)
2 1 - 2NH66/(2HH) 21-
Hence with probability
36, we have
RMgret(M, K, N, H. RLSVI
- 2cKHN + 8K /VN (og(2KHN/8) + 33H (og(HHKN/) VIN
So we obtain (9).
C.2. Lemmas for State-Aggreeatioon Results
Lemma 8 (Concentration Bound). Conditioning on D3: = UpE(N) Enewnttk-uan I 1 the trajectories of episode k- across all agents, for every possible ThA on (8h "b in episode k. event E(TRA) defined in (18) and event ((- both hold with probability 1 - 8/(2KHN).
Proof of Lemma 8. By Höeffding's inequality, conditional on the trajectory during episode k - 1, with probability 1 5/)2KHN), we have
No- La-
2H / (og(2KHN/O))
(1 Ph Ph (1
(22)
N (TRA)
NNx-L,
Additionally, recall from Algorithm 3 that for k: 2 2, the random perturbation during episode k - 1 is drawn from normal
distribution Q% (5 1, - (0, (
B6-1
and since (n ( 1/ ne in (24),
we have Qh_,, 1, (s) 1, a() NO, Ne 2.4 2.4 Also note that the random perturbations Q 1 d(-1.) are i.i.d. across E [N], hence by Höeffding bound, conditioning on Dr, with probability 5/(2KH we have
A
No. (T
BR-1
log(2K HN/0)
Σ
1n) s2
N (P
2 (TR)) +
NR-1,6((PR.)
Thus the result follows.
Lemma 9 (Optimism). When events E(TTt)) and G( hold for all Thh. in episode k and for all k E [K], E [N], the on-policy error VP (s) VV (s) lower bounded by zero for any & E S. [K] P (N).
18

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Proof of Lemma 9. Recall from Algorithm that the unclipped value function estimates (. in episode & can be written
(2,(())= arg minQeR
- (Nz-1 (0))
- (1- (N)-1
-N (G) 1. -aN (a a) + max (5) + 110 aN---
By first-order condition, we have
= 22 (1aa) - ENI-Lu(T) - (1 - ON 1e
-aN- -aN--a())(((s, + maxied Oh (
+2 Σ (1.0))ppt.oo(aa)))))00000 (Q%, - aN aN- 0h a)),
so by calculation we have
(7)
-(N-LAG) + N1-1,1(7) (s.a) son (s,a)=y
Σ
(1 -1-00 -N (A-
taN, (n(t)(((ssa)
+ max QP a'EA k (2,b+1(s,dd) + aN. (h,
=(N-LA(1) + (1-1 Co CN (n. w.)
Σ
(1 (
+an- ( 1h + Vp (h AN QR o
=[N-LA67 + (1 aN Q (N7- (77
Σ
(f - ( (h oh-ww)
= - + - -1- (N) Qu-
N2-1,((7)
ON4 1.1(2)
( oh a Vh (8
(1-1,1(7)
Na-1,b(7)
=NN-1A(7) + N6-1,(77
Σ
(1-aN, a- aH QR
+a In)) k- a.) + k,
Vp ( (8h (8h (5 of o,
where in the above derivation we used the fact that Ep- 1 (cr (s
= = ( =N)-1.()).
Thus for 2h Φr( (8 a.. with dh (s/- 1, 1. d 1.1) = The in the following, we have
19

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
( a. - - ( H.
Ne-Tialoess (72a)
1
=MN_LA(1) + N1-1n
(1- 11 - gk,))
+ON
(
V2 1 ( 15
No 2alhhd
-NN-110(7)
1
(1 (1-aN, 1n( 1 ( Σ
Nx-1,((
Ne-1,h(tha)
ON. 1,1()
(12-1,, 1,4 1,) 1
V2 (. + 1,- a 1,,1,
+ 1,-
- 1 (2
+ NR-1,11
(0% -- IN I
(7 k, (
2-c
Nu- Na-1,
2 -c+ ENN-LN)) + Nk-1,
Σ
Qh de
1=1
Ny Na-iaalhhs)
(1 1,4 (sk- 1 ol 11) V2
( + (
No- 1.
-Q7( 1,4 -
(23)
where we use the definition of c-error aggregation as in Definition in the last inequality above, and the right hand side of (23) equal
NE-1A(TEE)
(1-aNz 1n(s(r))
RHS of (23) =1) ENa-LA(T)
C Q (5k-5k1 of I,
Nx-1,1(7)
Nu IM((Tha) Σ
(,7-1,
I
N I1
+ (N
Viti
1=1
(
ON. 1.1()
(Viii ( PA P
NR-1,
No Ne-I.
-2) - (NZ-1,6(T)
ON ONN-LA
Σ
N
F=1
1
Σ
Vitn (
N8-1,1
NA-1
(V
PAV (
(1
(24)
where the equalities (1) and (2) the fact that
Qn = ra(s', (')) P PAVii (s',a'), (6',0'88x
20

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Suppose events E(hhh) and (( hold for all Thh in episode k. then by (18),(19), have
Nu N.-1.a
N0 H 1og((KKHN/)
(N N 11-1.1(T
(Vi+2(5k (
and
20 1. 34 1o
1,
1,
((N max
So recall from (7)
(7 + 20 1,1(7 11 ( (ON22KHN/0)
2 V4-
V(Ne-IA max M 1}
thus have
Chalsen (5k akpn) 2 No 2j=1 La-ia (V (V
(25)
Note that when N1-1,, = 0, then (1) = 1 (7) H. and we define terminal values as H with (2)411(7)
Oh (he+1(7) H, so by plugging H in (25), for any possible y E [T), we have Rg 2 Q2 (7). Thus
Vn 2 (s)(), Vs E S,E E [K], E [N].
Furthermore, suppose that at period h, have
VP (s) (s) 2 (s),,,, As S [N],
then from (25) we have
Ne-Im(ou(s.a)
Q2,-i(s,a) - -Q,(s))) (o-
Σ
(VZ (VL-LMtISS-INnn
( 2 0,
which implies that
(s, ()) ((s,a) x A
By maximizing over A on both sides above, have
VP VILLA V Vs E S, [K].
Thus by induction, we conclude that when events E(T,,) and ((> hold for all Nh, in episode & for all & E [K], we have
(2, (8) 2 (s), Vs E [
Lemma 10. Suppose events E(TTi)) and G(-kk)) hold for all Thoo for all & E [K] and (N), then we have
Ex K==1 [2 (sh.))
< 22 - 1h+
K ΣΣΣ
+4Hl 1og
1
1
Emh V NN--Le 1+ N,
N K
B 1og(
(ng_,(7 + 1
+ N Nx-1,e(PPa)
8= pm 2=2
21

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Proof of Lemma 10. By (23) have
Q ( (M
Q% (
N Ne-1aalths)
=NN, 1,666) (N-1
E
(1 aN- 11-
1kI,, - N ok,n)
Q%
+oN (stn 1o 1 1
- + h- 1 k- 1 22-1, R- 1 o -11,)
V2
Ny 1al
= (NN + (1
Σ
+ ON.-
Σ
[1 1
(5 1
of + k- (8 1h (k-1,,)))
(7
Q7 1
Ne-1,n( Σ
aN1-1.1
(0 1 - (h ,
Nx-1,
1=1
Se
Ne-1in(tks)
sct ENe- In(1)) +
Σ
(1 (a
(1
Ni-1in(tha)
Σ
11 ( + V ((-1ntz(((/1n44)
NK-1,N(ThN)
1=1
-Qh
(26)
where we use the definition of c-error aggregation as in Definition I in the last inequality above, and the right hand side of (26) is equal to
Ne-1,h(TEss)
aN, )
RHS of (26) =0) + ENe-L.b(7) + Nx-1,1(7)
Σ
(
- (h 1 (.
1=1
ONL-1a(TEN Ne-1na(1ha) Σ
No- N1-1,1
J=1
NE-1 Σ
+ aNe-La(fbe)
W - Vntt (
F=1
1
aNE 1m(3()
Σ
(V
PaVi+ (
No No-1a
aN--1A
Σ
=2) 6 ENi-La(1))
(
Ne-1.((hh))
Σ
Vh+ (s
No-1A
aN
Σ
(Vi+2(s/-1
N1-1,A(P
(27)
where the equalities (1) and (2) above use the fact that
(n(s',a') ra(s', a') + PA P (s,,a')
22

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Now suppose ((7kk) and ((())) holds for all aggregated states TA during period k for all p E [N].
By definition, note that
(s (o S ( ( ak,) S (s - ak
(28)
Denote
D = (. - (ok
(29)
then under events (( and G(vhh):
20
Bk- Be-
Rhalsha ckwn - ( aR Set ENo-1 +
V(NK-22 2,6 (Tkh( + (,0(
2 N.. H 1ogg22
A
k,h+1 +
N,-1,6 (Tkh)
(NL-LM(1RE))
(30)
Since (1hhh) and G(T hold for all 2h E [T], and recall from (7)
20 ( H V
(ogg22KHN/8)
20 20 BR log
(7ha), =c
/max(No-LNN(W)-1)
((N max max 13
so we have
N K
k. (PE
<En EK Q2
k==
k=1
ON H Vlg((22
$ 2KNE
(31)
N K ON, INt BR log (OSKHNH//
((N
+ 1)NNK 1) (7hx)
Σ A
k=1
For any 7 E (T), for ob such that ou ( k an 7, denote
N Na-1a(()
1
Be(+2())=
Σ
AP 2
Ne-1,1(7)
Note that
Ne-1.a 1N
Σ
(1
Σ ane Laftt
Σ
(32)
K
N
<
P
k1
1=1 pm1
where the last inequality above follows from Lemma 9.
Hence by above recursion and (31) we have that when 8 (n and ((-Ph) hold for all >h (T), we have
23

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
H
Ep=1
R=
R
k. k.b
bo V
I 2 - 1 h
VBB-1 1ogKH/0(2 t=h VNN-L,l1ke) 1+ No. (Tke)
1
H N
ΣΣΣ
2 V
(NR-2A(TRW) + IL 1+ Nx-1.e(f,,))
(33)
Lemma 11. Suppose E(hhh) and ((TTh)) hold all Rhh E [T), then with probability 26, we have
K
ΣΣ p=1
E. (s9) V (o9)
2 + 4881 (1gg2KNN/)) + K2' Vlog(HKN/6)
+2KH HDOT
Proof of Lemma 11. Note that
VEnlSh V/- (
(sh,))
VP (RAlhR - ( k, a
k.h + (
k. k. Vatao
(sP
-TT (Sh o. ( K k, + (5
07 (st
k. k.
=Q (5 n (7 ( k.h) + PAV h+ (5 k,++1)
PAV h+l (5 (5
(34)
-1Ô7. (oh h.) (7 k ngk,)]] + [V (xx44))
Viri (
([PPVT+1 (1)))) Vi
(s (x44))) + h+1 (s (8)))))
Ph Vitt (sy
= =1ÔT"" (5h k (7 xn
IV R,444 (s (p)))) V (K D k1++1
+[Pn h (6 - V + [M (ok - Pn VA (s (sh,
Summing over k 1,2, ... K, by (28), (31), (32) and (33) of Lemma 10 have
N K
VP k,h
(sh.h) - - (sk.h)
N
K
k. (ok,h42) - V (sP R.)+)))
AP
CN H k=
K +2KNE ΣΣ
VN
p=lk=
(35)
N K
AN aN B6-1 (2g(2KNN/0)
K
N
P
+ 1)N& (TR.))
1+ N 1.
k
k=
1=1
PAVit (8h,41) V (sp,++1)
k=
Ii (sh - Pa P (
Note that (35) recursive. Recall that sh = o7 for any le E [K].p P E [M). Thus by Lemma 10, when E and (()
24

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
hold for all The for all [ E [N], we have
K (5)) 7Nd (5f)
K
N
H
x 2cKHN + 4H (og(22
1,
1+ NA-1. (7th))
p 1=1
(36)
ΣΣΣ
Bk-1 log (K H N/8) h= V(N6-2M 1) -
HNK
1
1 ++ N1-11,0(Th))
K N
Vh+t (sb,42) PA PA (sk,N)-
k=1p=1
Further note that
PA PAVaii ( (++
K N
ΣΣΣ
(oh [h,))= = [PA (5t Vn+i (5 (x4))
=
>E|L k=1
and
N K
V - (h++1s
K
ΣΣΣ ME
i = - (8thh/1 (5
By Azuma-Höeffding 's inequality, with probability 2 1-8/
Hon 7P V ( (sh,641)
V (s S 211 / (1 (1)
T log 3
k=1p=1
and with probability 8/T, we have
ΣΣ 10 ab. VV Vh (Sk
2H - 2H V n (7)
log 8"
thus by summing over all the possible The [T], with probability 25,
PAVV (5 V (5P, 1) (PVV (5h Vi+t(Sh.
Vo
< 4H Σ
Vnk (*) (7))
log 8
>E(l"
25

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Finally, note that
1 1
(,
1
No 1
yE[r]
K H
00
H K
(37)
5(1) Σ
Σ
Na (a-1
Σ 1/50 (2)
ΣΣΣ 2 Nx-1
[E[
1=1k=1
S(3) 2,
HKT ΣΣΣ N4-1,(()
Σ
h= yE/1
2HKVTN
where (1) and (3) hold by Cauchy's 's inequality, and (2) holds because / <2 Furthermore, we also have
E EnEry (n((()) S / E Enery (7) = VH²KTN.
(38)
Additionally, note that whenever
2 (Thn))
we have
H N ΣEΣ
1
2, + I.A + (A
(39)
H
Bk_
2 (1hn) 1+ No. N1-1.A(TEA)
h=1p=1
and note that
H N K
K H
Na.(7))
ΣΣΣ
V N +1+ 1+ NN-IM (1)
+11+
(N=-LA() +11+ Ne)(())
h=1 2=2
k= h= 1
ΣΣΣ I= (NL-LA())
ΣΣΣ
HNaAlr (2al)211)) 1)3
KHT ΣΣΣ Nun(7)= KHIVN, k=
k= VNLA(T)
(40)
where equality (I) holds because (7) is the number of agents that reach aggregated state y at period h during episode k. And the last inequality holds by Cauchy's inequality. Recall that 3r = 1133 H2T(2k thus by (39),
B 2
L+Ne-n S XH//V//////XXXH////////X/
-p=1 k=2
(41)
Thus by (36), when events E(Th)) and ((T hold for all 7hh E [T]. with probability - 20, we have
N K
( - (sf)
p=1k=1
< H + 4KH2VTN (o + 32112 (iggH//)))
+2KH N (Dgg///HTT/T/OOXHHHHHHH (og(2KNN/)).
26

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
D. Proofs for the Infinite-Horizon Case
Additional notations For true MDP M and policy a we denote the discounted value function under и at state a as. V (s) (s). We denote V as the discounted value function under the optimal policy x².
During each eseudo-episode & E [K], each agent samples a random vector with independent components wh RM,5A, where (h, a) ~ of 8, a)) and @x s.a) = V V ( where 3r is a tuning parameter,
Nk NI-1,a(((s, (L(()()))) a)) the total number times that aggregated state ((8, a) is reached across all agents during episode 1. Given w we construct randomized perturbation of the empirical MDP for agent p as
M (T ph. R W N),
(42)
where the empirical distributions pk and empirical rewards Rt are computed as in (13) and (14). During each pseudo-episode E [K], the data set 0 contains perturbation of samples from pseudo-episode used by agent p.
We define the following events:
8'())== { N1-1(7)
Σ hE(Ha-i!
16 - - -PV.
(43)
2H /og (TN/6)
s
(Nx-1A(7)
s'6))==
1
Σ
Σ
- I. ok
Nk-1(7)
1=1 WE HE(He-1l
(44)
2/ Bk- log(TN// v (N + 1)NN-1177)
Lemma 12 (Lemma of (Dong et al., 2022)). For all n, s E S and 1j E 10, V2(s) ) TT. T
Remark 13. For weakly communicating M, the optimal average reward is state independent, under Assumption 6, almost surely for any s' E S, we have (V) (s' < 2r. < 2T.
Regret Decomposition Recall that Regret M, N, RLSVIS, denotes the regret under infinite-horizon case for MDP M. Here K arg max(k: tx T}. We put K explicitly here derive the regret bound in way dependent the random K. Let H2 be the length of pseudo-episode k. So we can decompose the regret as
Regret
M, T, N, RLSVI 9,a.g)
EK, EKH H
Σ p=
N
K
Etn (). - R2P) [M]
Ha
EK.H.
Σ
H& - -En Ex=
14 Σth R.
M
p=l
ki
(45)
N
K
N
EK.H.
(2(( - V (ch.))
1=
k=1
(a)
(6)
Recall from (11) that V,", V xxp < Note that (a) in (45) is the difference between the optimal average reward weighted by the pseudo-horizons and the discounted reward, and part (b) is the sum of the differences between the optimal discounted value and cumulative the discounted value of the employed policies throughout pseudo-episodes by all agents. We provide an upper bound for the worst-case regret by bounding (a) and (b) respectively.
27

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
D.I. Proof for Infinite-Horizon Main Result: Theorem 7
Proof of Theorem 7. By Azuma-Höefiding inequality, conditional on the trajectory during pseudo-episode k with probability 1 (2TN,,, we have
1
Nk. (1)
2 / log 2/o)
PA PA < 11 N2. (7))
NR-1 (7)
Additionally, recall from Algorithm that (8 %/1 ~ N (0,
Ne-1(1)=1 Note that conditional on the
trajectories during pseudo-episode - 1, the random perturbations are i.i.d. across j [y): E [Hg-1], thus by Höefdding's inequality, conditional on the trajectory during pseduo-period k with probability 6/(2T N). we have
3k-1
10g(2TN/6)
Σ
1 1 $2
N (7)
N (7) +
N1-
So have
- P(E ((TTA))))) The vk E (K], h E - P(E()) WE [T.pE (N)
2 1
(P(E()))) P(G())))) 2 1- 2NT5/ 21 PE
Σ
(46)
By Lemma 15 and Lemma 14, with probability 1 - 35, we have
TN - T)T + +1]
Regret(M, T, N, RLSVI R.
+ [11 ((1-1)T++ + + (1 ++vNNun VNlog(NT)
VNT
8T TN (ogo((2TN)))
8T-3/2T Nogg((TTT) log
(47)
7
(1 17)
4K NT (og(T/5)
+ TN..
n
Recall that 5 max(T, T), so with probability 1- have
+N T)T + 1]
Regret (M,, RLSVI
+ [(1
T) + 117 (1+ v N (log(NT)
NNT
8T TN (og(67)/5)
//3/ (ogg(2rTT) log
(1 7)
(1 - -))
4K /TT log /0)
2mcTN.
1- 1
When 77 such that (1-n)² I C for constant C, is bounded from below, have
Regret N, RLSVI
$ 2cNN - 2TVNT + 4T (NT)(NT)
+160 max(73/2 1)TT TN log (277) (6TN/8))
D.2. Lemmas for bounding (a) and (b) in (45)
Lemma 14 (Bound for (a) of (45)). EHA.K Exe Ek Had, - V2
71
+ [(1 n)T +
VNT
[]r (1 + /N (log(NT)).
28

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Proof of Lemma 14. Note that the expected length of each pseudo-episode is independent of the policy and is equal to T-
Thus for K fixed, Ems Ex Ex= k=1 H - (s =
pp=
N
V2
(
thus
k=
--
K
N
K
X
E
HgA.
S R
V2
By Lemma 12, know that
S So that for any p E [M]. for any fixed K,
I-n
K
(2((s)
S KT.
Note that "h1 are sampled i.idd across p at the beginning of each pseudo-episode k. Höeffding's 's inequality shows that for any > 0,
A
2c
P
(2(S%.) 2 (T)
s sexp
4NK222
Take
c= KT log(NT),
we then have
K
I
Σ
x
( 2 KT (1+ VN log(NT)) $ 'NNT
p=1
Thus conditioning on the total number of pseudo-episodes K,
N
K
TKN
EK
VNT + Kr (1+ v N log(NT))
Further note that since H₂ Geometric(1 1)) and are i.i.d. across k; so
B[K] S (1 7) +1
Hence by taking expectation over K, we have
N
K
+ [[K]T (1+ Volog((T)
p=1 km -
NT
T D) +1]
+ +[(1 (1-11)T- + 1|/ (1+ v N (Noo(NTT)
VNT
Lemma 15 (Bound for (b) of (45)). Suppose events E (7) and G¹ (1) hold for any y [T], then with probability 1 - 28, have
8T PN (2T
8/3/2
N (2r(2r(7)) log(27N/8)
Σ pp Ex=1 k=
V M (8h.1)
(1 )2
1-n m
47 NT
(og(
+ 2n
7
29

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Proof of Lemma 15. Recall from Algorithm 4 that the unclipped value function estimates 2%aa during pseudo-episode time period h E [FRx (recall that H3. here is random)
(7) = arg min
E(saaronts (Q (Ne-16)) - -1 (x
(M a) + max QP (8 + ||0 -
NO 1100 22.11 1
So similar to the derivation in the proof of Lemma 10, we have
1 N1-1(1)
( 1()) + N1-1(1)
Σ
(1 (1- aN (0=-16)))
taN=-t))((($ k- ) + (8k--11,14))) + Qk ( a211))))
By definition, we have (7) = 0% (7). We denote Q%(7) = Qh, in the following. Thus for any = (s k xg during pseudo-episode k with <6 I.)) = in the following, where state-action pairs during pseudo-period - (note that we don't distinguish between different pseudo periods now), where E 21.2...., Hk-1), and Hx-1 1 is the random length of pseudo-episode k and recall that Nx)1(7) Ep= Eneihaiil (6 10- 1,, = 7). so we have
- come from all the
Qhi kn (0
No-1(1)
NEN, 167)
1
Σ
(1 1--NN OONNN-i1ii 160) ak 1
N7-1(9)
5=1
11)
1N7--1(7)
+ (5 + C (5k- للسل
+1
17)
(
N2-1,1(7) Σ
Nx-1(7)
Ne-1(1)
SE+ + Nx-1(7)
1
Σ
(1- (I- akW - (
(48)
1=1
No 1(7)
aN--1(7) +1 NK-1,(7))
Σ
(,
+ ( + 1
1,)1
p=1
Nx-1
=C+ - ON 167)
Σ
No-1(9)
j=1
No. 160
17
(V2 (6% (86 ( 1,+1)
17)
(12-1(7))
(
PAV
(7-1(1))
1=1
where we used the fact that under optimal policy x" for the true MDP, we have
(.'s'a = r(s' a') + (
and under the optimal policy n k-15 1J under MDP M k 1.j we have
a') - n 1s) Q =
=
Now suppose that events 8d (1h1)) and G (7% hold for all aggregated states 7he during pseudo-perido k for all k E [K]. Then by similar derivation as that for the finite-horion case in Lemma 9, we have
TP (s) V.(s) 2 O, Vs E S, E [K] K E [N].
(49)
30

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
We denote
2. (o V.
Note that
(s Va((k,,)) & (k - -2 ok, S (sk Q7 R.
By (48) we have
(o - (0
No-1(>)
"1
(1 (x=
- ak-
12-1(7))
5=1
No 197)
(7))
Σ
( - V/2 ( + Iu - -
+1| 17)
p=1
(Q I k d
No-1
+1
1.h(7)
(Q RR - Q7 12
N2. 17)
No 1e)
T/E (No-1(7)
+
1
Σ
(1- (100
(50)
Nx-1(7)
5=1
Na-1(7)
(7)-1(7)
Σ
(-1 (- 1 1
(8- + 1 (6-1
+1 N1-1,1
p=1
N4 1())
-1(N--117) +NE a
Σ
(
N7-1(7)
j=1
Na-1(1)
(V2 (sk_1,044)
Nx-1(7)
f=1
Ne-1(1)
(NN--((1) -1 NN-1((
Σ
where the inequality follows by definition of e-error aggregated states as in Definition 4. Then by similar derivation as for (32), by summing from the i-th pseudo-episode to K-th pseudo-episode, we have
K
4n
K
Tog(27N/0))
2N
VN--LA(TE))
km
p=1
N
K
Nk-1, (Tha))
ONe
A 1
NR- (TKh)
Then by similar derivation as in (33) under events El (1Ph) and G (7hb)) for all The across K pseudo-episodes and p agents, we have
4n
Σ
Ep=1
ΣK
S
2TENN
H₂
+
1 (og(2TTN/))
ΣΣΣ Am
v NN--Le
(1 1 Nr- 11
kmi
N
VB log 2/0)
1
4n
t= pm k=++1 V (N + 1)N
1 + Ne-1ze(Th.))
31

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
Then following similar steps in the proof of Lemma 11, we have 2, -VE, -V (o
V (o - V7 (6%,,)
1Q kk
n (s Q2 h. L. + k - V (sk++1)) 1
(51)
[V? (5 (s%,b+)) Ph
V xtep (sk 1)].
Note that (51) is recursive, when events El (n&r) and G' (rhr) hold for all aggregated states 7kh during pseudo-perte it for all & E [K], we have
ΣΣ
k.1 (6)) (s9)
N Ha
4
1
2 21tTNN +
(log(2TN/5)
1 h-1
VN 1 + 1
x=1p=1ha1
K
Be log N/5)
(52)
((Na-2 + 1) 1+ 1
HE
PA.V. (+ - (sk,))))))
V VTL (x+,11)) P Vil (S (s
Note that
H
4
1
22
1
1
NN- (Thhh)
1 1N
k=
K
Hy
N
4
<
(0g(2TN/8))
1
NN-- (1hh))
1 N (7h2h)
1=1
p=1
4
H&
Nz-1(1)
<
(og(27N/8)
1/j
1
h=1
7E[T]
Hy
4
Mog(2TN/8))
Σ
2/ Nx-1(7)
(53)
nE(T)
K H
8
<
11 (1og(2TN/6)
r Na-1(1)
h=
TETT]
8
8/TN log (2TNN
K
(1 1og
VTNH&-IS
H
--
(1-
8 (NNoog22TN
8T WT.NNoog(2TN/)
H
11-1)2
(1 (1-1) 1)2
Next, note that 3x=
1 1 (2g(2rkk), following similar steps as (53) and (40) we have
K
H
N
Ba log 2T)
1
3/3/TTT N log(22117) log 2/))
(54)
VN 2
N (P
7)2
==
p=1
Additionally, denote NE. (7) as the number of times that aggregated state y attained during pseudo-episode and pseudo
32

---

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration
period h, then by Azuma-Höeffdding' inequality, with probability 26, have
Σ (1V2 xtp (st,11)) - V xhp (s (,h+1) (5k,41)) 6
4
Σ
V
/ log 8"
p=1
yE(T]
Hence with probability 1 - 28,
(P
(5 1] [V (5 (5,
PA V7 (sh kk,b+1))
k=1i=1
4v (T)(
K Hx
4 TN WTTNNog (og()
K H
ΣΣ
7"
Σ TE(T]
(Na())
1 h-1
(55)
1-
1-
1hm1
4K (KvTT TN (1/6) (1 17)2
Thus by (52), (53), (54), (55), when events El (nhA) and G' (1h1) hold for all aggregated states Th during gpeudo-peride k for all & E [K], with probability - 26, we have
ST IN log (og(277))) (1 n)
8/ N log (2TT7) log(27N/0)
Σ (S9) (s))
(1 - n))
(56)
4K (Tg(())))
(1 - n)
Finall, by (49), when events 8 (nhch) and G (with) hold for all aggregated states Thh during pseudo-perido ks for all ls E [K].
V. V.A (s) V.(s) 2 0, Ys E e [K].E [N],
And with probability -28, we have
8T V TN (2T
8/3/2TT N log(2~117) (2g(22
Ep
K k=1 (+(
V
FeP. (o.1)
47 NT (0))
7
33


Reviews:
[{"review_id": "FmJh48aKeT", "reviewer": "Reviewer_zmC5", "summary": "The paper adapts the concurrent learning framework via randomized least squares value iteration with an aggregated state representation, to improve exploration efficiency and the worst-case regret bound. Extensive experiments are conducted to support the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and constructive comments. We are aware that our experiments are only on synthetic data. We would like to emphasize two points regarding the role of experiments in this work.  \n\nFirstly, the main focus and contribution of our work is the first theoretical analysis of concurrent model-free RLSVI algorithms. It is worth noted that neither of the two most closely related papers [1,2] (single-agent RLSVI) includes any numerical results.  \n\nSecondly, we conduct experiments on synthetic data to specifically validate the theoretical findings in a controlled manner. This approach aligns with existing literature of theory papers. It is also worth noted that, unlike [1,2], our theoretical results are based on practical, storage-efficient algorithms. With carefully designed numerical validations, they provide valuable insights for practitioners.\nWe will add a table comparing with existing theoretical results to discuss the practical implications in terms of scalability and computational efficiency.\n\nThat said, we agree with the reviewer that experiments on real-world data would be an interesting direction to extend the current work, and we plan to explore it in the future.\n\n[1] Russo, Daniel.``Worst-case regret bounds for exploration via randomized value functions.\" Advances in Neural Information Processing Systems 32 (2019). \n\n[2] Agrawal, Priyank, Jinglin Chen, and Nan Jiang.``Improved worst-case regret bounds for randomized least-squares value iteration.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.", "claims_and_evidence": "The claims are well supported by evidence.", "methods_and_evaluation_criteria": "The methods and evaluation make sense to me.", "theoretical_claims": "Yes. The proofs are correct.", "experimental_designs_or_analyses": "Yes, the experimental designs are valid.", "relation_to_broader_scientific_literature": "The paper is related to the concurrent randomized least-squares value iteration literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strength\n- The paper focuses on an important problem in RL, with sound proof of the worst-case regret bound over the existing ones.\n\nWeakness\n- The experiments are only on the synthetic datasets. With experiments on the real-world datasets, it could demonstrate the improvements better.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tjzLjNZ2a8", "reviewer": "Reviewer_n92W", "summary": "The paper presents a novel approach to concurrent reinforcement learning (RL) using Randomized Least Squares Value Iteration (RLSVI) with aggregated states. The authors propose a framework where multiple agents interact with a common environment, sharing their experiences to improve decision-making collectively. The paper also discusses the role of the discount factor in RL, arguing that it serves primarily as a tuning parameter to stabilize value updates rather than being an intrinsic part of the environment.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and constructive comments.  \n\n1. We would like to emphasize two points regarding the role of experiments in this work. First, the primary contribution of this paper is theoretical analysis of concurrent model-free RLSVI algorithms. Notably, neither of the two most closely related works [1,2], which focus on single-agent RLSVI, includes numerical results. Second, our experiments using synthetic data are explicitly designed to validate theoretical findings in a controlled environment, a common practice in theoretical literature. Importantly, unlike [1,2], our theoretical results are derived from practical, storage-efficient algorithms, and the corresponding numerical validations provide valuable insights for practitioners. Nevertheless, we agree with the reviewer that extending experiments to real-world datasets would be an interesting direction for future exploration, which we plan to pursue.\n\n2. For scalability, as detailed in lines 248–258 (paragraph under equation (6)), prior approaches [1,2] require storing all historical data, making them computationally impractical at scale, while ours is storage-efficient. Following the reviewer's suggestion, we provide a comparison table below to explicitly contrast our approach with existing related work, including the two most closely related work [1,2] on single-agent RLSVI:\n\n| Agent | Setup        | Algorithm                   | Regret Bound                         | Regret-Type | Data Stored  | Numerical |\n|-------|--------------|-----------------------------|--------------------------------------|-------------|--------------|-----------|\n| Single| Tabular      | RLSVI [1]                   | $\\tilde{O}(H^3S^{3/2}\\sqrt{AK})$                  | Worst-case  | All-history  | N/A       |\n| Single| Tabular      | RLSVI [2]                   | $\\tilde{O}(H^{5/2}S\\sqrt{AK})$                 | Worst-case  | All-history  | N/A       |\n| Multi | Tabular      | Concurrent RLSVI [3]        | N/A                                  | Bayes       | All-history  | Synthetic |\n| Multi | Linear Functional Approximation  | Concurrent LSVI [4]         | $\\tilde{O}(H^2\\sqrt{d^3KN})$                       | Worst-case  | All-history  | N/A       |\n| Multi | Linear Functional Approximation  | Concurrent LSVI [5]         | $\\tilde{O}(H\\sqrt{dKN})$                     | Worst-case  | All-history  | N/A       |\n| Multi | Tabular      | Concurrent RLSVI (**ours-1**)| $\\tilde{O}(H^{5/2}\\Gamma\\sqrt{KN})$        | Worst-case  | All-history  | N/A       |\n| Multi | Tabular      | Concurrent RLSVI (**ours-2**)| $\\tilde{O}(H^{5/2}\\Gamma K\\sqrt{N})$       | Worst-case  | One episode  | Synthetic |\n\nThe following discussions will be added to paper:\n\n-  $\\Gamma$ denotes the size of aggregated states. This reduces complexity and accelerates learning by focusing on grouped state-action pairs.\n\n- To the best of our knowledge, all existing concurrent RLSVI work focuses on finite-horizon case, while we also cover the infinite-horizon case. The regret bound for the infinite-horizon case is similar to that of the finite-horizon case, by replacing $KH$ with total time steps $T$. \n\n- The methods marked as \"N/A\" in the \"numerical\" column store all agents' trajectories at every step, making them computationally infeasible as $N$ grows large. These approaches (including our first finite-horizon algorithm, second-to-last row in the table) provide only theoretical analyses without numerical results.\n\n- Although [3] stores all data empirically, their RLSVI algorithm assumes a known parametric feature matrix, making it simpler to implement than ours. Also they evaluate only Bayes regret—less stringent than our worst-case regret—and provide empirical results exclusively on synthetic data without theoretical guarantees.\n\n- The last row corresponds to storing only the latest episode data, increasing the regret bound by a factor of $\\sqrt{K}$ but reduces space complexity by a factor of $K$, making it computationally feasible.\n\n[1] Russo, Daniel. \"Worst-case regret bounds for exploration via randomized value functions.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[2] Agrawal, Priyank, Jinglin Chen, and Nan Jiang. ``Improved worst-case regret bounds for randomized least-squares value iteration.\" Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, 2021.\n\n[3] Taiga, Adrien Ali, Aaron Courville, and Marc G. Bellemare. \"Introducing Coordination in Concurrent Reinforcement Learning.\" ICLR 2022 Workshop on Gamification and Multiagent Solutions.\n\n[4] Desai, Nishant, Andrew Critch, and Stuart J. Russell. \"Negotiable reinforcement learning for pareto optimal sequential decision-making.\" Advances in Neural Information Processing Systems 31 (2018).\n\n[5] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: asynchronous communication and linear function approximation.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "See the comments below", "methods_and_evaluation_criteria": "See the comments below", "theoretical_claims": "See the comments below", "experimental_designs_or_analyses": "See the comments below", "relation_to_broader_scientific_literature": "See the comments below", "essential_references_not_discussed": "See the comments below", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper addresses an important problem in RL, particularly in the context of multi-agent systems.\n\n- The theoretical results are novel and provide improvements over existing bounds.\n\n- The empirical results are consistent with the theoretical predictions, providing strong evidence for the efficacy of the proposed algorithms.\n\nWeaknesses:\n\n- The empirical validation is limited to synthetic environments. It would be beneficial to see how the algorithm performs in more complex, real-world scenarios.\n\n- The paper could benefit from a more detailed discussion of the practical implications of the theoretical results, particularly in terms of scalability and computational efficiency.", "other_comments_or_suggestions": "I suggest adding a ​systematic comparison table to explicitly contrast the proposed approach with existing concurrent RL methods, highlighting theoretical guarantees, empirical performance, and practical considerations to emphasize its novelty and superiority.", "questions_for_authors": "- How does the proposed algorithm compare to other concurrent RL algorithms in terms of both theoretical guarantees and empirical performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cg8RG3h3y7", "reviewer": "Reviewer_35te", "summary": "The authors extend the classic Least Squares Value Iteration (LSVI) method to the setting of multi-agent systems, and show guarantees for a randomized variant.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive feedback! \n\n1. We will add an impact statement later :)\n\n2. [2] improves the regret bound of [1] by using clipping in their algorithm to avoid unreasonable estimates of the value functions. The rest of their algorithm closely follows [1], using a similar proof approach: constructing a confidence set for the empirical MDP to bound its deviation from the true MDP. They decompose regret similarly to [1] and get a tighter upper bound for the approximation error of the $Q$-value function due to their clipping technique.\n\n     Our paper uses a different algorithm from [2] and proof strategy to improve the regret bound of [1]. Firstly, we do information aggregation at the aggregated-state level, unlike the algorithms in [1,2] that record the information for every pair of $(s,a)$. Secondly, we use a different loss function and penalty term for updating the estimates of $Q$-value functions. By the first-order condition the estimated $Q$-value function is updated according to the derivation between line 1004 and line 1028, $\\alpha$ and $\\xi$ are carefully chosen based on concentration lemma 8, so that (i) Lemma 9 holds, which is a key step to the proof of Lemma 10 using iteration trick; (ii) the term in (37) between line 1375 and line 1389 can be controlled by a tight upper bound using Cauchy-Schwarz inequality.  \n\n3. $V_h^{\\pi}(s)$ is the value function of adopting policy $\\pi$ at state s during period h, which is a standard definition (see e.g. [3]). We include $h$ in the subscript because we consider inhomogeneous transition probabilities and reward functions (i.e. the transition probabilities and reward functions are allowed to be different at each period $h$ in our model). \n\n4. On the one hand, $R_{h,s,a}^{k,\\textrm{full}}$ and $\\hat P_{h,s,a}^{k,\\textrm{full}}(s')$ \nare estimates of rewards $R_{h,s,a}$ and transition probability $P_{h,s,a}(s')$  used in episode $k$ based upon all the historical data across all agents from episode $0$ to $k-1$, where $R_{h,s,a}$ is the reward received by state-action pair $(s,a)$ at time step $h$, and $P_{h,s,a}(s')$ is the probability of transferring to state $s'$ if taking action $a$ at state $s$ during time step $h$.  On the other hand, $\\hat P_{h,s,a}^k$ and $\\hat R_{h,s,a}^{k}$ only uses data in episode $k-1$ (much less data compared to the previous two estimates). The algorithm utilizing $R_{h,s,a}^{k,\\textrm{full}}$ and $\\hat{P}_{h,s,a}^{k,\\textrm{full}}(s')$ has a lower regret bound because we use more data in the buffer (information set), but can be computationally infeasible especially as the number of agents gets large, as we explained in the paper. \n\n5. As we pointed out at the beginning of subsection 2.1, when $SA$ is too large, the algorithm can be computationally infeasible. So we aggregate the state-action pairs that have close $Q$-values under optimal policy. By $\\epsilon$-error aggregated state-representation, we aggregate all those $(s,a)$ in the same block if the differences of their $Q_h^*$ values are less than $\\epsilon$ according to definition 1. \n\n6. Here in (4) randomization is applied to the value function estimates by perturbing observed rewards to drive exploration, which is essential to randomized LSVI algorithm (see [4] for more details).\n\n7. As we responded in the 2nd point, $\\xi_n$ is a parameter carefully derived based upon the concentration bound in Lemma 8 in Appendix B, to make Lemma 9 hold, and to control the terms by a tight upper bound in the proof. This is a technical term and is important to make the algorithm and the proof work. \n\n8. We thank the reviewer for the suggestion about more future work. We will extend this in a revised version later. For example, we plan to implement our algorithm on real-world data, and derive concurrent RL results on function approximation beyond the current tabular setup, and compare our results with the existing concurrent functional approximation literature (e.g. [5,6]). \n\n[1] Russo, Daniel. \"Worst-case regret bounds for exploration via randomized value functions.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[2] Agrawal, Priyank, Jinglin Chen, and Nan Jiang. ``Improved worst-case regret bounds for randomized least-squares value iteration.\" Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, 2021.\n\n[3] Bertsekas, Dimitri, and John N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.\n\n[4] Osband, Ian, et al. \"Deep exploration via randomized value functions.\" Journal of Machine Learning Research 20.124 (2019): 1-62.\n\n[5] Desai, Nishant, Andrew Critch, and Stuart J. Russell. \"Negotiable reinforcement learning for pareto optimal sequential decision-making.\" Advances in Neural Information Processing Systems 31 (2018).\n\n[6] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: asynchronous communication and linear function approximation.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, to some extent.", "experimental_designs_or_analyses": "Yes, to some extent.", "relation_to_broader_scientific_literature": "The theoretical guarantees cover an important gap in the literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "None.\n\nThe writing is clear!", "other_comments_or_suggestions": "None.", "questions_for_authors": "Please put an Impact Statement :)\n\nPage 2:\nLine 94:\nCan you please elaborate on the difference of the techniques used?\n\nPage 3:\nWhy is $V_h^\\pi(s)$ defined in this way?\n\nPage 4:\nCan you please further explain $\\hat R_{h, s, a}^{k, \\texttt{full}}$ and $\\hat P_{h, s, a}^{k, \\texttt{full}}(s')$?\n\nPage 4:\nCan you please elaborate on the concept of aggregated-state representations?\n\nPage 5:\nI do not understand the perturbation that is captured by Equation (4).\n\nPage 6:\nCan you please clarify the choice of Equation (7)?\n\nPage 8:\nMore discussion on future work is required! :)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a concurrent reinforcement learning framework based on randomized least-squares value iteration (RLSVI) in multi-agent systems to address the problem of exploration. It demonstrates improvements in efficiency and provides theoretical worst-case regret guarantees, supported by synthetic experiments.

All reviewers agree on the clear motivation and contribution of the proposed method, the soundness and clarity of the theoretical analysis, the validity of the experimental setup, and the overall rigor of the presentation. A common concern was the lack of experiments on real-world tasks and the need for more detailed discussion on the implications and comparisons of the results. The authors addressed these points by explaining the rationale behind using controlled experiments and providing a systematic comparison with prior works. Reviewer 35te also raised several technical questions, which were adequately addressed in the rebuttal.

The authors' response was thorough and resolved most of the reviewers' concerns. Given its novelty, technical depth, and relevance, this paper would be a valuable addition to ICML.
Decision: Accept (poster)