Pith. sign in

REVIEW 3 major objections 4 minor 60 references

Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Agent teams can share a single episode and keep regret at 1/√N

desk verdict The main theorem is proven for a different algorithm than the one stated; the optimism lemma's index swap breaks the regret bound, though the problem and idea are sound. read the letter →

arxiv 2501.13394 v3 pith:ZUQQCQNT submitted 2025-01-23 cs.LG cs.AI

Yan Chen , Qinxun Bai , Yiteng Zhang , Shi Dong , Maria Dimakopoulou , Qi Sun , Zhengyuan Zhou This is my paper · ORCID
classification cs.LGcs.AI MSC 68Q3268T05
keywords concurrentreinforcementlearningrandomizedleast-squaresvalueiterationaggregatedstaterepresentationregretboundsmulti-agentexplorationone-episodebufferworst-case
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to prove that a team of agents can explore an unknown environment together using randomized least-squares value iteration (RLSVI) with aggregated states, while keeping only the data from the last episode in memory. In the finite-horizon setting it derives a worst-case regret bound of $\tilde{O}(\epsilon K H N + K H^{5/2}\Gamma\sqrt{N})$; in the infinite-horizon setting the bound is $\tilde{O}(\epsilon T N + \tau^{3/2} T \Gamma \sqrt{N})$. The per-agent regret in both settings decreases as $\Theta(1/\sqrt{N})$, which is the optimal rate in the number of agents. The practical point is that sharing a single episode's experience is enough to get the benefit of concurrent exploration without storing all historical data.

What carries the argument

The machinery is a regularized least-squares Q-update over $\Gamma$ aggregate states, where an $\epsilon$-error aggregation groups state-action pairs into blocks in which the optimal Q-values differ by at most $\epsilon$. Each agent draws Gaussian perturbations $\tilde{Q}$ and reward noise, minimizes a squared temporal-difference loss with weight $\alpha_n=1/(1+n)$ on the empirical Bellman target, and the team updates shared estimates by visitation-weighted averaging. The proof's optimism argument (Lemma 9) uses concentration events $E(\gamma)$ and $G(\gamma)$ and a bonus $\xi$ to show the estimated values stay above $Q^*$; from there the regret bound follows by a recursive decomposition of $\hat{V}-V^*$. The infinite-horizon algorithm replaces episodes with random-length pseudo-episodes and carries the same mechanism through the discounted Bellman recursion.

What would settle it

Run Algorithm 3 on a two-state, two-action MDP with a single aggregate state ($\Gamma=1$) and measure the per-agent regret for $N\in\{1,2,4,8,\dots\}$ over, say, $K=50$ episodes; if the regret curve flattens or rises rather than tracking $1/\sqrt{N}$, the central claim fails. A sharper check is to inspect the optimism inequality in equation (23): compute both sides on a simulated trajectory; if $\bar{Q}^p_{k,h} - Q^*_h$ is ever negative in an episode where the concentration events hold, Lemma 9 is false and the stated bound does not follow.

Watch

Extended reading notes

Core claim

The central discovery is that injecting Gaussian noise into the rewards of a shared one-episode data buffer and solving a regularized least-squares Q-update per agent preserves optimism at the aggregate-state level, so that a society of agents can explore concurrently without a model. For the finite-horizon algorithm (Algorithm 3), the worst-case regret is at most $\tilde{O}(\epsilon K H N + K H^{5/2}\Gamma\sqrt{N})$; for infinite-horizon Algorithm 4 it is $\tilde{O}(\epsilon T N + \tau^{3/2} T \Gamma \sqrt{N})$. These bounds give the per-agent $\Theta(1/\sqrt{N})$ decay, and Algorithm 3 stores only $O(HN)$ transitions rather than $O(KHN)$, at the price of a $\sqrt{K}$ factor in the regret compared to a full-history variant. The bounds also show a linear-in-$\epsilon$ penalty from state aggregation, consistent with the known impossibility of exact optimality when $\epsilon>0$.

Load-bearing premise

For the regret bounds to follow, the randomized value estimates must stay optimistic (never below the optimal value) at every step; the optimism proof relies on replacing the current episode's bootstrap values with the previous episode's per-agent values at one step, and the infinite-horizon result further assumes the optimal policy has bounded reward-averaging time $\tau$.

Editorial extensions

If this is right

  • In the finite-horizon setting, running Algorithm 3 with $N$ agents and $K$ episodes gives per-agent regret $\tilde{O}(\epsilon K H + K H^{5/2}\Gamma/\sqrt{N})$, so the per-agent cost falls as $1/\sqrt{N}$.
  • The one-episode buffer reduces space complexity from $O(KHN)$ to $O(HN)$, so the cluster's memory no longer grows with the number of episodes.
  • The infinite-horizon algorithm reaches the same $\Theta(1/\sqrt{N})$ per-agent rate, with the reward-averaging time $\tau$ replacing $H$ in the horizon-dependent term.
  • A full-history variant of the finite-horizon algorithm improves the regret by a factor of $\sqrt{K}$, showing that the memory-regret trade-off is governed by a $\sqrt{K}$ factor.
  • Because the bound is worst-case over MDPs with $\epsilon$-error aggregation, the algorithm remains provably efficient even when state-action pairs are grouped into $\Gamma$ abstract states.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof's optimism induction (Lemma 9) substitutes previous-episode value estimates for the same agent's current-episode bootstrap values at one critical step; if that substitution cannot be justified, the regret bound would need a different argument, and a targeted re-derivation or counterexample along equation (23) would settle it.
  • The $\Theta(1/\sqrt{N})$ per-agent rate suggests that the benefit of adding agents should saturate only as $N$ grows beyond the problem's intrinsic scale; testing on a fixed MDP class with larger $N$ than the paper's experiments would show where the curve bends away from $1/\sqrt{N}$.
  • The same one-episode buffer idea could be transferred to nonlinear function approximation or stochastic rewards; the paper's analysis covers deterministic bounded rewards, but the persistence of an aggregation-error term suggests the qualitative trade-off would remain.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies concurrent reinforcement learning with N agents interacting with a common environment and proposes finite-horizon and infinite-horizon randomized least-squares value iteration (RLSVI) algorithms with aggregated state representations. The main theoretical claims are worst-case regret bounds of O~(εKHN + KH^{5/2}Γ√N) for the finite-horizon one-episode-buffer algorithm (Theorem 2) and O~(εTN + τ^{3/2}TΓ√N) for the infinite-horizon version (Theorem 7), giving per-agent regret that decays as Θ(1/√N). The algorithms store only the last episode (or pseudo-episode) of data, reducing space complexity by a factor of K relative to all-history RLSVI analyses at the cost of a √K factor in the regret. Numerical experiments illustrate the predicted 1/√N trend and the replication code is provided.

Significance. If the regret bounds were valid, the paper would make a useful contribution: it would provide the first theoretical analysis of a model-free concurrent RLSVI algorithm with aggregated states, a concrete space-regret trade-off, and a Θ(1/√N) per-agent speedup under worst-case (not Bayesian) regret. The paper also ships replication code and states a falsifiable scaling law. However, the central proof of optimism (Lemma 9, Appendix C) rests on an unjustified substitution of current-episode bootstrap values by previous-episode per-agent quantities, so the main theorems are not established. Because this gap is load-bearing for the regret recursions in Lemmas 10-11 and for Theorem 7, the claimed contributions remain conditional.

major comments (3)
  1. [Appendix C, Lemma 9, display leading to Eq. (23)] The derivation replaces the current-episode bootstrap value \hatt V^p_{k,h+1}(s^p_{k-1,h+1}) and the current-episode perturbation \tilde Q^p_{k,h}(s^p_{k-1,h},a^p_{k-1,h}) with the previous-episode per-agent quantities \hatt V^j_{k-1,h+1}(s^j_{k-1,h+1}) and \tilde Q^j_{k-1,h}(s^j_{k-1,h},a^j_{k-1,h}) in the averaged first-order expression for \bar Q^p_{k,h}. This substitution is not a consequence of Algorithm 3: the loss minimized by \bar Q^p_{k,h} uses \hatt Q^p_{k,h+1}, the same agent's current-episode next-stage estimate, and the current-episode noise \tilde Q^p_{k,h}. The concentration events E(γ) and G(γ) in equations (18)-(19) bound exactly the episode k-1 averages, so they cannot be invoked for the k-indexed bootstrap errors after the shift. The nonnegativity of (25) and the induction \hatt V^p_{k,h} ≥ V^*_h both rely on this step, so Lemma 9, and consequently the regret recursions in Lemmas 10-11 and Theorem 2, are not proven.
  2. [Appendix D, Lemma 15, Eq. (48)-(50)] The infinite-horizon analysis repeats the same index shift: in the display leading to (48), the current-pseudo-episode bootstrap \hatt V^p_k(s^j_{k-1,h+1}) and perturbation \tilde Q^p_{k,h} are replaced by the previous-pseudo-episode quantities \hatt V^j_{k-1}(s^j_{k-1,h+1}) and \tilde Q^j_{k-1,h}. The same unsupported substitution is then used to conclude optimism in (49). Since Lemma 15 is the basis for part (b) of the regret decomposition and for Theorem 7, the infinite-horizon bound inherits the gap.
  3. [Appendix B, Algorithm 3, and Section 3] The pseudocode for Algorithm 3 constructs the perturbed data sets \tilde D^p_{kh} from D^k_h, the tuples collected during episode k, while the main text (Section 3) and the proof of Lemma 8 condition on the trajectory of episode k-1 and use the counts N_{k-1,h}(γ). These are different data-generating processes: under the pseudocode, the empirical rewards and transitions used in the loss are from the episode that has just been executed, whereas the analysis is valid only for a version that uses the previous episode's data. The proof of the first-order condition and the concentration argument therefore do not apply to Algorithm 3 as written, and the paper does not state which version of the algorithm is actually analyzed.
minor comments (4)
  1. [Abstract and Section 1] There are repeated typos: 'concurent' should be 'concurrent', and 'tender' in the abstract should be 'render' (or similar). Several other grammatical slips appear throughout the paper.
  2. [Section 3, Eq. (7)] The definition of ξ_n uses β_{k-1} even though n is a generic count N_{k-1,h}(γ); the dependence on the episode index k should be made explicit (e.g., ξ_{k,n}) to avoid confusion in Lemma 9 and the regret bound.
  3. [Lemma 10] The statement mixes the indices h and ℓ inside the sums: the left-hand side uses h, but the display contains terms such as N_{k-1,ℓ}(γ^p_{kℓ}) and γ^p_{kh}. This should be cleaned up for readability.
  4. [Theorem 2 proof] The probability accounting is inconsistent: the proof first obtains a 1-2δ event and then a 1-δ event, and concludes 'with probability 1-3δ'; the final statement should specify the exact probability regime being claimed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the regret bound is derived, not assumed; the Lemma 9 concern is a proof gap, not a circular reduction.

full rationale

The paper's central claims—finite- and infinite-horizon worst-case regret bounds and the per-agent 1/sqrt(N) rate—are derived from concentration inequalities, first-order optimality conditions of the regularized least-squares loss, and an induction over episodes, rather than being encoded in the tuning parameters or assumed in the cited lemmas. The constants beta, alpha, and xi are chosen from Hoeffding-type bounds and the epsilon-aggregation error; none contains the final regret rate. The 1/sqrt(N) per-agent statement is the arithmetic consequence of dividing a total regret bound of order sqrt(N) by N. Self-citations to Chen et al. (2022), Dong et al. (2019b), and Dong et al. (2022) supply background, the aggregation setup, and the reward-averaging-time lemma; the latter is an elementary parameter-free bound with stated assumptions and is not the concurrent RLSVI result, so it is not load-bearing circularity. The proof-validity concern about Lemma 9—the replacement of the current-episode bootstrap/noise terms by previous-episode quantities in display (23)—is a possible gap in the optimism argument, not a circular reduction: the theorem does not assume that replacement as an input, and if the substitution is unjustified the stated bound is unproven rather than equivalent to its own conclusion. The statement that Algorithm 1's bound follows by a sqrt(K) reduction is an omitted routine proof, not a circular step.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard MDP assumptions, the existence of an ε-error aggregation, and a proof step that effectively assumes current-episode bootstrap values can be replaced by previous-episode per-agent values. The tuning parameters are hand-set rather than data-fitted, and no new physical or model entities are postulated.

free parameters (3)
  • β_k (RLSVI noise scale) = 0.5 H^3 log(2 H Γ k) finite horizon; 0.5 τ^3 log(2 τ Γ k) infinite horizon
    Chosen by hand in Theorem 2 and Theorem 7 to balance concentration and regret terms; no data fitting, but the central bound depends on this choice.
  • ξ_n (aggregation bonus and noise bonus) = ε plus concentration terms in equations (7) and (15)
    Hand-set offset in the loss function; it guarantees optimism in Lemma 9 only under the assumed concentration events E and G.
  • α_n (update weight) = 1/(1+n)
    Standard RLSVI weight chosen by hand; determines how strongly the new episode's data updates the value estimate.
assumptions (4)
  • standard math Standard Bellman optimality and Hoeffding/Azuma concentration inequalities hold.
    Used throughout Appendix C and D to bound empirical transition errors, perturbation sums, and martingale differences.
  • domain assumption Finite-horizon MDP has H periods, deterministic rewards in [0,1], and all agents start from a fixed initial state s_1; infinite-horizon MDP is weakly communicating and satisfies Assumption 6 (bounded reward averaging time τ for the optimal policy).
    Statements in Sections 2, 4, and Assumption 6 define the problem class; the infinite-horizon regret bound is only claimed for MDPs in this class.
  • domain assumption The given map φ_h (or φ) is an ε-error aggregated state representation (Definitions 1 and 4).
    The regret bounds contain explicit ε terms because aggregation is approximate; the optimism proof also uses the ε-closeness of Q* values within each aggregate.
  • ad hoc to paper In Lemma 9, the current-episode bootstrap value \hat V^p_{k,h+1} can be replaced by previous-episode per-agent values \hat V^j_{k-1,h+1} in the averaged first-order condition.
    This replacement appears at equation (23) and is not a consequence of Algorithm 3's loss, which uses \hat Q^p_{k,h+1} for the same agent p. The optimism induction depends on this step.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration." pith.science (2026). https://pith.science/paper/ZUQQCQNT

@misc{pith2026250113394,
  author       = {Pith},
  title        = {Pith review of: Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZUQQCQNT}},
  note         = {Machine review of arXiv:2501.13394}
}
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 {\it concurently} explore an environment. The theoretical results %that we established in this work tender an affirmative answer to this question. We adapt the concurrent learning framework to \textit{randomized least-squares value iteration} (RLSVI) with \textit{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 \cite{russo2019worst} and \cite{agrawal2021improved}. 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 \citep{agrawal2021improved,russo2019worst}. Additionally, we conduct numerical experiments to demonstrate our theoretical findings.

Figures

Figures reproduced from arXiv: 2501.13394 by the authors.

Figure 1
Figure 1. illustrates a 1/ √ N decreasing trend in per-agent regret for both settings, consistent with our theoretical predictions. The replication code is available at https: //github.com/yz2/rlsvi_code [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 45 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    H., Chalup, S

    Abed-alguni, B. H., Chalup, S. K., Henskens, F. A., and Paul, D. J. A multi-agent cooperative reinforcement learning model using a hierarchy of consultants, tutors and workers. Vietnam Journal of Computer Science, 2: 0 213--226, 2015

    work page 2015

  3. [3]

    Making Contextual Decisions with Low Technical Debt

    Agarwal, A., Bird, S., Cozowicz, M., Hoang, L., Langford, J., Lee, S., Li, J., Melamed, D., Oshri, G., Ribas, O., et al. Making contextual decisions with low technical debt. arXiv preprint arXiv:1606.03966, 2016

    work page Pith review arXiv 2016

  4. [4]

    M., Lee, J

    Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp.\ 64--66. PMLR, 2020

    work page 2020

  5. [5]

    Improved worst-case regret bounds for randomized least-squares value iteration

    Agrawal, P., Chen, J., and Jiang, N. Improved worst-case regret bounds for randomized least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.\ 6566--6573, 2021

    work page 2021

  6. [6]

    Near-optimal regret bounds for reinforcement learning

    Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008

    2008

  7. [7]

    G., Munos, R., Ghavamzadeh, M., and Kappen, H

    Azar, M. G., Munos, R., Ghavamzadeh, M., and Kappen, H. Speedy q-learning. In Advances in neural information processing systems, 2011

    work page 2011

  8. [8]

    Emergent complexity via multi-agent competition

    Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I. Emergent complexity via multi-agent competition. arXiv preprint arXiv:1710.03748, 2017

    arXiv 2017

Show all 60 references
  1. [9]

    Bartlett, P. L. and Tewari, A. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint arXiv:1205.2661, 2012

    2012 arXiv

  2. [10]

    Multi-agent reinforcement learning: An overview

    Bu s oniu, L., Babu s ka, R., and De Schutter, B. Multi-agent reinforcement learning: An overview. Innovations in multi-agent systems and applications-1, pp.\ 183--221, 2010

    2010

  3. [11]

    Society of agents: Regret bounds of concurrent thompson sampling

    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

    2022

  4. [12]

    A provably efficient model-free posterior sampling method for episodic reinforcement learning

    Dann, C., Mohri, M., Zhang, T., and Zimmert, J. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34: 0 12040--12051, 2021

    2021

  5. [13]

    Desai, N., Critch, A., and Russell, S. J. Negotiable reinforcement learning for pareto optimal sequential decision-making. Advances in Neural Information Processing Systems, 31, 2018

    2018

  6. [14]

    and Van Roy, B

    Dimakopoulou, M. and Van Roy, B. Coordinated exploration in concurrent reinforcement learning. In International Conference on Machine Learning, pp.\ 1271--1279. PMLR, 2018

    2018

  7. [15]

    Scalable coordinated exploration in concurrent reinforcement learning

    Dimakopoulou, M., Osband, I., and Van Roy, B. Scalable coordinated exploration in concurrent reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018

    2018

  8. [16]

    Q -learning with UCB exploration is sample efficient for infinite-horizon MDP

    Dong, K., Wang, Y., Chen, X., and Wang, L. Q -learning with UCB exploration is sample efficient for infinite-horizon MDP . arXiv preprint arXiv:1901.09311, 2019 a

    1901 arXiv

  9. [17]

    Provably efficient reinforcement learning with aggregated states

    Dong, S., Van Roy, B., and Zhou, Z. Provably efficient reinforcement learning with aggregated states. arXiv preprint arXiv:1912.06366, 2019 b

    1912 arXiv

  10. [18]

    Simple agent, complex environment: Efficient reinforcement learning with agent states

    Dong, S., Van Roy, B., and Zhou, Z. Simple agent, complex environment: Efficient reinforcement learning with agent states. Journal of Machine Learning Research, 23 0 (255): 0 1--54, 2022

    2022

  11. [19]

    and Pentland, A

    Dubey, A. and Pentland, A. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04972, 2021

    2021 arXiv

  12. [20]

    Hypermodels for exploration

    Dwaracherla, V., Lu, X., Ibrahimi, M., Osband, I., Wen, Z., and Van Roy, B. Hypermodels for exploration. arXiv preprint arXiv:2006.07464, 2020

    2006 arXiv

  13. [21]

    Bayesian bellman operators

    Fellows, M., Hartikainen, K., and Whiteson, S. Bayesian bellman operators. Advances in Neural Information Processing Systems, 34: 0 13641--13656, 2021

    2021

  14. [22]

    Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates

    Gu, S., Holly, E., Lillicrap, T., and Levine, S. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA), pp.\ 3389--3396. IEEE, 2017

    2017

  15. [23]

    and Brunskill, E

    Guo, Z. and Brunskill, E. Concurrent pac rl. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2015

    2015

  16. [24]

    Randomized exploration in reinforcement learning with general value function approximation

    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--4616. PMLR, 2021

    2021

  17. [25]

    R., Precup, D., Anandkumar, A., and Azizzadenesheli, K

    Ishfaq, H., Lan, Q., Xu, P., Mahmood, A. R., Precup, D., Anandkumar, A., and Azizzadenesheli, K. Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. arXiv preprint arXiv:2305.18246, 2023

    2023 arXiv

  18. [26]

    M., and Tschiatschek, S

    Janz, D., Hron, J., Mazur, P., Hofmann, K., Hern \'a ndez-Lobato, J. M., and Tschiatschek, S. Successor uncertainties: exploration and uncertainty in temporal difference learning. Advances in Neural Information Processing Systems, 32, 2019

    2019

  19. [27]

    Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp.\ 1704--1713. PMLR, 2017

    2017

  20. [28]

    Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018

    2018

  21. [29]

    Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp.\ 2137--2143. PMLR, 2020

    2020

  22. [30]

    Kim, M. J. Thompson sampling for stochastic control: The finite parameter case. IEEE Transactions on Automatic Control, 62 0 (12): 0 6415--6422, 2017

    2017

  23. [31]

    Kulkarni, A. J. and Tai, K. Probability collectives: a multi-agent approach for solving combinatorial optimization problems. Applied Soft Computing, 10 0 (3): 0 759--771, 2010

    2010

  24. [32]

    Littman, M. L. Value-function reinforcement learning in markov games. Cognitive systems research, 2 0 (1): 0 55--66, 2001

    2001

  25. [33]

    I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I

    Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competitive environments. Advances in neural information processing systems, 30, 2017

    2017

  26. [34]

    Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation

    Min, Y., He, J., Wang, T., and Gu, Q. Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation. In International Conference on Machine Learning, pp.\ 24785--24811. PMLR, 2023

    2023

  27. [35]

    and Van Roy, B

    Osband, I. and Van Roy, B. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014

    2014

  28. [36]

    and Van Roy, B

    Osband, I. and Van Roy, B. On optimistic versus randomized exploration in reinforcement learning. arXiv preprint arXiv:1706.04241, 2017

    2017 arXiv

  29. [37]

    ( M ore) efficient reinforcement learning via posterior sampling

    Osband, I., Russo, D., and Van Roy, B. ( M ore) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013

    2013

  30. [38]

    Deep exploration via bootstrapped DQN

    Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. Deep exploration via bootstrapped DQN . Advances in neural information processing systems, 29, 2016

    2016

  31. [39]

    J., Wen, Z., et al

    Osband, I., Van Roy, B., Russo, D. J., Wen, Z., et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20 0 (124): 0 1--62, 2019

    2019

  32. [40]

    and Parr, R

    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 Intelligence, volume 30, 2016

    2016

  33. [41]

    Worst-case regret bounds for exploration via randomized value functions

    Russo, D. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019

    2019

  34. [42]

    and Van Roy, B

    Russo, D. and Van Roy, B. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39 0 (4): 0 1221--1243, 2014

    2014

  35. [43]

    Cooperative and competitive biases for multi-agent reinforcement learning

    Ryu, H., Shin, H., and Park, J. Cooperative and competitive biases for multi-agent reinforcement learning. arXiv preprint arXiv:2101.06890, 2021

    2021 arXiv

  36. [44]

    and Leyton-Brown, K

    Shoham, Y. and Leyton-Brown, K. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008

    2008

  37. [45]

    Multi-agent reinforcement learning: a critical survey

    Shoham, Y., Powers, R., and Grenager, T. Multi-agent reinforcement learning: a critical survey. Technical report, Citeseer, 2003

    2003

  38. [46]

    Concurrent reinforcement learning from customer interactions

    Silver, D., Newnham, L., Barker, D., Weller, S., and McFall, J. Concurrent reinforcement learning from customer interactions. In International conference on machine learning, pp.\ 924--932. PMLR, 2013

    2013

  39. [47]

    Sinai, S., Wang, R., Whatley, A., Slocum, S., Locane, E., and Kelsic, E. D. Adalead: A simple and robust adaptive greedy search algorithm for sequence design. arXiv preprint arXiv:2010.02141, 2020

    2010 arXiv

  40. [48]

    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 0 (8): 0 1309--1331, 2008

    2008

  41. [49]

    Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018

    2018

  42. [50]

    and Littman, M

    Szepesv \'a ri, C. and Littman, M. L. A unified analysis of value-function-based reinforcement-learning algorithms. Neural computation, 11 0 (8): 0 2017--2060, 1999

    2017

  43. [51]

    A., Courville, A., and Bellemare, M

    Taiga, A. A., Courville, A., and Bellemare, M. G. Introducing coordination in concurrent reinforcement learning. In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022

    2022

  44. [52]

    Performance loss bounds for approximate value iteration with state aggregation

    Van Roy, B. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 31 0 (2): 0 234--244, 2006

    2006

  45. [53]

    A concise introduction to multiagent systems and distributed artificial intelligence

    Vlassis, N. A concise introduction to multiagent systems and distributed artificial intelligence. Springer Nature, 2022

    2022

  46. [54]

    and Klabjan, D

    Wang, X. and Klabjan, D. Competitive multi-agent inverse reinforcement learning with sub-optimal demonstrations. In International conference on machine learning, pp.\ 5143--5151. PMLR, 2018

    2018

  47. [55]

    Multiagent systems: a modern approach to distributed artificial intelligence

    Weiss, G. Multiagent systems: a modern approach to distributed artificial intelligence. MIT press, 1999

    1999

  48. [56]

    and Van Roy, B

    Wen, Z. and Van Roy, B. Efficient reinforcement learning in deterministic systems with value function generalization. Mathematics of Operations Research, 42 0 (3): 0 762--782, 2017

    2017

  49. [57]

    Posterior sampling for continuing environments

    Xu, W., Dong, S., and Van Roy, B. Posterior sampling for continuing environments. ArXiv preprint, 2022. URL https://arxiv.org/abs/2211.15931

    2022

  50. [58]

    Frequentist regret bounds for randomized least-squares value iteration

    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

    1954

  51. [59]

    Multi-agent reinforcement learning: A selective overview of theories and algorithms

    Zhang, K., Yang, Z., and Ba s ar, T. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pp.\ 321--384, 2021

    2021

  52. [60]

    Multi-agent cooperative reinforcement learning in 3d virtual world

    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 I 1, pp.\ 731--739. Springer, 2010

    2010

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.