Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work extends PSRL to the concurrent multi-agent setting. The authors discuss the finite horizon and infinite horizon settings, establishing a $1/\sqrt{n}$ per-agent regret, which is minimax optimal under a Dirichlet prior. For the infinite horizon case, the authors use a doubling schedule. In both settings the authors discuss results under general priors and under Dirichlet priors.
strengths_and_weaknesses: - Paper provides an extension of PSRL to the concurrent case, whereas previous work was based on UCRL-type algorithms.
- Proofs are provided for the theoretical results. The proofs seem correct, though clarity could be greatly improved.
- Please add the assumption that $r \in [0,1]$, even though it does not affect generality of the solution.
- I recommend stating all formal lemmas used from other papers in the appendix. This will greatly increase overall clarity of the proofs.
- It is hard to follow the proofs of the thoerems in the appendix. I recommend going over them too add some more explanations, and possibly divide them into a few more lemmas (if possible).
- Please provide an explicit algorithm in the appendix, where bonuses and posterior definitions are provided.
- Please find a way to put the simulations plots in the front matter - they should not be put in the appendix if they are referenced directly in the paper.
- How do the results in this paper generalize to the frequentist regret setting?
- The contribution of this paper is clear, but I am on the fence w.r.t. the overall strength of this paper. Particularly, theoretical aspects of the paper are standard and not surprising. The improvement the authors make over prior work is unclear. Overall, I worry that the extension the authors make is trivial w.r.t. current work.
- Simulations in this paper are very weak. There are many interesting aspects to test, especially in the frequentist setting, which is usually the relevant setting in real-world problems.

Comments regarding proof of Theorem 3.1 (Appendix):

- Line 519: where did this inequality come from?
- Lines 525-526: I understand what the authors wanted to say, but please rephrase this statement to make it more percise and clear.
- The use of lines 525-529, including Equations B.7 - B.10 is unclear in the final statement. 
- It is unclear what statements the authors are using in the final equations of the proof.

questions: Please see review above
limitations: The authors didn't discuss negative societal impact (I'm unsure how relevant they are either).
Regarding limitations of their work, I didn't find a clear discussion.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the Bayesian regret bound of Concurrent Thompsom Sampling, where n agents interact with the environment simultaneously. The existing works are confined to the optimism-in-face-of-uncertainty principle (UCB). This paper presents the first attempt to analyze posterior sampling based algorithms, both in the episodic and infinite-horizon setting. 


strengths_and_weaknesses: Strengths:
1 This paper provides the first line of theoretical analysis for TS-based algorithm in the concurrent episodic/infinite-horizon RL setting. 
2 While the analysis techniques seem to follow from the seminal works of Benjamin Van Roy, the resulting bounds are good as they are minimax-optimal.
3 The theoretical guarantee is verified by simulation results, which is appreciated as empirical study has been largely ignored in the RL theory community.

Weakness:
1 Comparison to existing works. The paper motivates the use of TS by some empirical works, showing that TS can have advantage as agents can determine their policies individually, while UCB-type algorithms tend to use the same policy. (Line 72-77) This is a good motivation for the use of TS. However, it seems that the analysis of this paper does not verify this potential advantage over UCB-type algorithms theoretically. In particular, the paper does not contain a comparison between them. Are they all minimax-optimal? What is the advantages of TS-based algorithms over a UCB-based one?

2 Simulation result. While it is good to see that the paper contains simulation result, the experiments are not satisfactory as they do not include the UCB-type algorithms as baseline. While I understand that a thoroughly comprehensive comparison between UCB and TS in theroy may need more involved analysis, I strongly recommend the authors to conduct simulations to verify the effectiveness of TS. 

I am willing to raise my score if my major concerns could be addressed.
---------------------- update after rebuttal
I have read the responses from the authors and increase the score to support the acceptance of this work.
questions: See weakness part
limitations: yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers a concurrent RL setup, where a set of agents share experience when individually interacting in the same environment, and optimizing the same reward function. Thompson Sampling (TS) based exploration is considered and corresponding regret bounds are derived for the finite and infinite horizon setting. These bounds extend the TS guarantees for the single-agent RL case to the concurrent RL setup. Moreover, simple simulations are performed showing the computed regrets are of the same order of the obtained bounds.
strengths_and_weaknesses: I have appreciated the motivations for the concurrent RL setup provided in the introduction, and I think the considered problem is interesting and relevant. Moreover, the paper is nicely written and the derived theoretical results are sound both intuitively and technically.
However, I do have a concern: 

- I think most (if not all) of the claims made are under the assumption that the agents reward functions are the same?  This should be clarified better in the introduction. 
questions:  Even if agents have different reward functions, I believe the power of cooperation should still be visible because they interact with the same environment. In such a case:
- I expect some of the guarantees to go through, but how would the overall results change?
- UCRL (or similar) approaches should ensure increased exploration w.r.t. when agents have the same reward. Do you think there is a right measure (in the rewards' space) to quantify this?
limitations: I don't foresee potential negative societal impacts.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies efficient Thompson sampling algorithm for concurrent RL. They mainly consider efficient learning in episodic setting and infinite-horizon setting. For both settings, they provide efficient learning algorithm for general prior and Dirichlet prior. Their regret bounds show that $\sqrt{n}$ speed up is possible when there are $n$ agents sharing the information and exploring the environment simultanously.
strengths_and_weaknesses: Strengths:

To the best of my knowledge, this is the first work studying efficient Thompson sampling algorithm in concurrent setting. The algorithm and analysis is a natural extension of the previous work in the single-agent setting. The paper is well-written and the theoretical results are solid and reasonable.

Weakness:

The authors fail to explain the technical difficulties of concurrent Thompson sampling compared with the single-agent setting. It seems that the algorithm and analysis almost directly follows that in [1,2]. Since the main contribution of this work is their theoretical improvement, I wonder whether there is anything novel in the algorithmic design and the proof technique.



[1] Osband et al. Why is posterior sampling better than optimism for reinforcement learning?

[2] Agrawal et al. Posterior sampling for reinforcement learning: worst-case regret bounds.
questions: It would be helpful for evaluation if the authors could clearly explain the technical difficulties of concurrent PSRL and the methods they used to tackle them. 
limitations: The authors have explained several limitations in the conclusion sections.Other possible directions for improvements are listed as follows:
- This paper does not tackle the communication cost in concurrent learning. It would be interesting to design efficient learning algorithms with efficient communication (e.g. [1,2]).
- There are also works studying efficient PSRL with function approximation. I wonder whether $\sqrt{n}$ speed-up is also possible in the function approximation setting.

[1] Agarwal et al. Communication efficient parallel reinforcement learning.

[2] Wang et al. Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication.
review_title: null

Meta-review: metareview: We thank the authors for their submission.

This well-written paper presents no-Bayesian-regret algorithms for multi-agent cooperative RL. This is the first work to study Thompson sampling algorithms in the context of concurrent RL - where agents interact with the MDP simultaneously. An experimental evaluation is also provided.
confidence: Less certain
Decision: Accept