Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focus on collaborative multi-agent RL. In this setting, all agents share the same state-action space and transition probabilities but may have with different rewards. In this setting, they introduce an assumption inspired from collaborative filtering, that the reward matrix of the N users have low rank. Given this assumption, they provide algorithms for efficient learning in two settings: tabular MDPs
and linear MDPs. When the number of agents N is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which is exponentially better than the naive approach.
strength_and_weaknesses: Strengths
1) The paper is generally well written.
1) The paper examines an interesting setting based on reasonable assumptions that may emerge in real applications.
2) The paper combines a lot of ideas from various lines of literature (e.g., MDPs, low rank matrix completion, multi-agent mean-field RL). 


Weaknesses
1) The results do not seem particularly surprising given the prior work.
2) Although the authors try to incentivise the model via real world applications no effort is put into testing these ideas on an actual benchmark. 




clarity,_quality,_novelty_and_reproducibility: The paper is well written. Breaking down the algorithm in different phases helps with parsing some of the key ideas/steps.

summary_of_the_review: An interesting theoretical paper on multi-agent RL. The practical applications of the proposed scheme are less clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors studied the problem of multi-user collaborative reinforcement learning under the assumption that the reward matrix is low-rank. They proposed a sample-efficient algorithm for tabular MDPs and linear MDPs by exploiting the low-rank structure to incorporate the techniques from matrix completion. In particular, they showed that the total sample complexity for every user scales as $O(N+|\mathcal{S}||\mathcal{A}|)$ instead of  $O(N|\mathcal{S}||\mathcal{A}|)$ in tabular MDPs and $O(N+d)$ instead of $O(Nd^2)$ in linear MDPs. This is a significant improvement. 
strength_and_weaknesses: $\textbf{Strength}$: (1) In this work, the authors incorporated the low-rank structure into the algorithm design and sample complexity analysis of the multi-user reinforcement learning. It is interesting to see a significant improvement in sample complexity by fully exploiting the low-rank structure in the reward matrix. This could motivate researchers by incorporating other structures into reinforcement learning. 

(2)  Generally, the paper is well-presented and easy to read. The main contributions are stated clearly.

$\textbf{Weaknesses}$: (1) There are many low-rank examples in collaborative filtering literature. However, it is rare to see examples of the low-rank reward matrix in reinforcement learning. It would be more convincing if the authors could provide some examples with explanations on the assumption that the reward matrix is low-rank in reinforcement learning. This is very important in clarifying the significance of this work.

(2)  The notation is a little confusing in this paper. For example, what is the definition of $\Delta$ in $\Delta(A)$?  What is $da$ in $\pi_h(da|s)$ on Page 3? 

(3) Some assumptions in the paper are not well presented and motivated. For example, Are there any interpretations of Assumption (Lin) 4? 

(4) It would be good if the authors could provide some instances of random vectors that satisfy the requirement in Eq. (2). 


clarity,_quality,_novelty_and_reproducibility: 
$\textbf{Clarity}$ & $\textbf{Quality}$: In general, it is joyful to follow the whole paper. The basic setups and contributions of the problem are well presented. The related literature about reinforcement learning and matrix completion is well-surveyed. However, insights into many assumptions and equations are not provided. This could make the readers difficult to understand some parts of the paper. Another minor comment is that the authors should cite some most recent works on low-rank matrix estimation. 

$\textbf{Novelty}$: In general, the idea of this work is new and interesting. In particular, incorporating the low-rank structure into the study of reinforcement learning could significantly improve the sample complexity in learning. The only concern is whether it is reasonable to assume the low rankness of the reward matrix in reinforcement learning. The authors should provide more explanations on this. 

$\textbf{Reproducibility}$: There are no experiments in this paper. The reproducibility could be significantly improved if the experiments are provided and the code could be released.
summary_of_the_review: 
At first, I have to claim that I am not an expert on reinforcement learning and I don’t know the related latest results. According to my understanding of this paper and the cited papers, the authors applied the techniques from matrix completion to the multi-user reinforcement learning problem. The theoretical contributions of this work are rather solid and strong. However, the discussions of the assumptions and theoretical results compared to the existing results are missing. Then, the readers don’t well understand the significance of these results.



$\textbf{Typo}$: (1) In Algorithm 1, “compete” should be “complete”. 
(2) In Theorem 2, “Assumption” should be “Assumptions”.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of multi-agent reinforcement learning under the structure of low-rank rewards. Specifically, multiple agents share the same transition distributions while having different rewards, which are assumed to be represented by a low-rank matrix. Both tabular and linear MDPs are investigated. 

The main idea is first to use reward-free algorithms to estimate transition structure (which is the same across different agents); then input designed rewards to the reward-free output to obtain exploration policies that only interest in collecting rewards (which are constructed to have reward samples satisfying specific properties); at last, use low-rank matrix estimation techniques to obtain the reward matrices for all agents from the samples in the second step. 

The main technical difficulties are in how to obtain proper reward samples and how to use these samples. For tabular MDP, the idea is to encourage explorations of important states (determined by the reward-free outputs) and use existing techniques to perform the matrix estimation. The design in linear MDP is more challenging (thus more complicated) where the authors propose a newly crafted matrix estimation algorithm and carefully design the sampling strategy in MDP to meet the required sample properties. 

With the above techniques, sample complexity analyses are performed on both tabular and linear MDP settings. Compared with learning individually, the designs are shown to be effective in leveraging the low-rank structure to decrease the sample complexity.
strength_and_weaknesses: Strength:
+ The consideration of low-rank structure is reasonable and I believe is an important direction to be explored in RL, especially to break the curse of multi-agent;
+ This work nicely adopts existing techniques in reward-free explorations and matrix estimations, while also bringing new developments, especially in sampling strategies to guarantee specific sample properties and an extended matrix completion technique. The combination is inspiring;
+ I am not very familiar with matrix completion, but the proposed techniques (i.e., how to maintain the isotropic property in samples and how to perform matrix estimation with row-wise linear measurements) may be of independent merits.

Weakness:
I am overall satisfied with the technical side of this work. However, I found the presentation not very clear. One potential reason may be that I am more from an RL background instead of matrices analysis. However, I believe it is still important to illustrate key intuitions clearly. Especially, many interesting designs are left unexplained (some even not mentioned explicitly). 
- For example, in the tabular setting, Algorithm 2 is designed to stop when rewards of important states are sufficiently collected, while the importance of states is measured by (in some sense) their "achievability" characterized by the value obtained from reward-free outputs. I believe this part is important; however, it is not mentioned in Sec. 3.1, instead in the analysis (i.e., beneath Assumption (Tab) 2), a connection between incoherence and the redundant states is discussed. 
- Similarly, for linear MDP, no verbal explanation other than the algorithm box (Alg. 2) illustrates how to perform Step 1 in Phase 2, which essentially designs rewards in unexplored directions for the reward-free outputs to explore more.
- Also, the theoretical analysis part lacks certain illustrations. The two parts of Theorem 1 comes from reward-free exploration and reward query, respectively, while the choice of parameter p is also not intuitive (which seems to directly contribute to the second term). A similar illustration is also missing for linear MDP, as it is not explicitly mentioned the meaning of the three parts in the sample complexity.

Other than the above concerns on clarity, I also have certain confusion about the intuition and statement of the results. Hopefully, the authors can help me clarify these questions:
- Typically in RL studies, the main difficulty is to learn the transitions (thus many works even assume the rewards are known). However, in this work, the difficulty is in learning the rewards, as there are N agents with N different reward dynamics. Thus, for the results, the authors emphasize the regime of large N, which makes the cost for reward learning dominate. Then, the benefit seems to come from the shared transitions, as it does not depend on the identity of the agent. I am just wondering whether this is suitable/fair to compare with letting each agent learn individually and whether this is any more suitable baseline.
- It is a bit hard for me to interpret the results in Theorems 1 and 2. Especially, in Theorem 1, when the first term has a stronger dependency on epsilon; however the authors emphasize the dependency on the second term. For example, when epsilon = 1/N, the first term is dominating. For Theorem 2, it is even more complicated with more parameters involved. Hopefully, the authors can provide a more formal and detailed discussion of the results.
- I believe there should be works in matrix analysis handling noisy observations, and thus I am wondering whether this work can accommodate noisy rewards. If not, hopefully, the authors can illustrate the difficulties.
clarity,_quality,_novelty_and_reproducibility: My main concern with this work is its clarity. I believe some additional efforts can largely benefit the interpretation of the algorithms and results. Other than the presentation, I believe this work is of good quality and makes a reasonable contribution to the theoretical understanding of multi-agent RL. I have not checked all the proofs but from what I read, the authors involve sufficient proof details.
summary_of_the_review: This work studies the problem of multi-agent RL, especially under the structure of low-rank rewards. Techniques are required from both RL and matrix analysis. On the RL side, for the shared transitions, reward-free explorations are first adopted, and later sample strategies are carefully constructed to obtain samples with certain properties. On the matrix analysis side, sampling requirements are first identified for the RL part and with these properties, existing techniques are adopted for the tabular setting while a new estimation technique is proposed for the linear setting. The combination of these techniques leads to performance improvements which are demonstrated theoretically. However, the presentation does not make me satisfied and I believe also does not fully demonstrate the techniques/results in this work as many key illustrations are missing, which leads to my recommendation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the offline RL setting under N user-specific MDPs. The author addresses the sample efficiency and the exploration of collaborative reward function. The solution assumes a low-rank structure between user reward functions and use the idea of collaborative filtering to reduce the required number of samples for each user MDP.

A special problem definition:
* Same state/action space and transition function across users;
* Personalized reward function, assumed to be low-rank;
* Goal: learn optimal policies for N user-specific MDPs
* Goal2: improve sample efficiency. 

The main intuition:
When multiple user MDPs are collaboratively learned, the low-rank nature can derive a solution that can collaborate the learnings of MDPs and reduce the number of sample required for each user MDP.

Proposed algorithm:
1. Reward free exploration: uniformly pick user MDP for a given trajectory and generate optimal policy function \Pi(R) and its estimator V(\Pi(R)).
2. Query the reward matrix: use these functions to sample and collect user-wise rewards of state-action pairs or sample linear measurements
3. Complete or estimate the reward matrix: recover the full matrix from the sampled records for each user; 
4. Computing optimal policy: find the optimal policy on the full matrix.

Contribution:
* An RL algorithm with a proven sample efficiency boost.
* An algorithm for efficient matrix completion for tabular MDP.
* An algorithm for efficient policy sampling and estimation that satisfies given statistics.

strength_and_weaknesses: Strength:

1.The motivation of this paper is very interesting. The low-rank assumption is very common in recommendation settings.

2.The theoretical result is sound and impressive.

Weakness:

1.The paper is not quite easy to follow. It is hard for people who are not familiar with reward free RL to get the main idea of the method.

2.The paper makes the low-rank assumption, but they do not justify whether it is reasonable.

3.The paper does not discuss it's limitation and conclude the paper.

4.It would be better to have a experiment to validate the effectiveness over baselines, even in a tabular game.

5.The collaborative MDP problem setting in the paper restrict the transition functions to be the same across MDPs, so it is equivalent to stating a single MDP with personalized reward function. The paper would have greater impact if it considers a more realistic setting where user transitions are non-deterministic and personalized as well.


Minor issues:
* Introduction, first paragraph, "is smaller the number" --> "is smaller than the number";
* 
* Since you are borrowing the insight of collaborative filtering, in the motivating example, better briefly introduce the insight of your method. For example, stating that you can borrow the "exploration of similar users and assume that similar users generate similar responses."
* Problem setting, 2nd paragraph, "A_h = \pi_h(S_h)" --> "A_h \sim \pi_h(S_h)"
* Problem setting, "linear MDP setting" section, better state that \phi represents transition embedding and \psi represents reward embedding when first introduced. 
* Section 3.2, Phase 2 step 1, "query obtain samples" --> "query/obtain samples"?
* An inconsistent notation: in problem setting you use e_i for different embedding dimensions, but in section 6 you state that i represents a user.


Questions to authors:
* Main points mentioned in weakness;
* Do you have explanation on why linear MDP has total complexity O(N+d)?
* Should it be G_h in the last two lines of Algorithm 1 instead of G?
clarity,_quality,_novelty_and_reproducibility: 1.The paper is not easy to follow.

2.The results are impressive and novel.

3.The paper does not provide any experimental results.
summary_of_the_review: Overall, the paper is interesting and novel. It is important to leverage the low-rank property of reward function in RL. But the clarity is low and there is no experimental result.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on multi-user reinforcement learning with low-rank rewards. This paper considers the problem where all the users play in the MDPs with the same dynamics but different reward functions. Exploiting the low-rank property of the reward matrix, the authors design two novel sampling algorithms for tabular and linear MDPs respectively. Combined with the designed matrix completion algorithm with row-wise linear measurements, the sampling algorithms are shown to enjoy low sample complexities.
strength_and_weaknesses: Strength:

This paper designs novel efficient algorithms for collaborative multi-user reinforcement learning with low-rank reward matrices. The improvements in sample complexities from $O(N|S| |A|)$ to $O(N+|S| |A|)$ and from $O(Nd^{2})$ to $O(N+d)$ are very interesting and important for the research in this field.

Weaknesses:

Technical issues:
1. Since the authors adopt the big O notation like $O(N+|S| |A|)$ in the paper, I assume that this paper concerns the regime where $N$ and $|S| |A|$ both increase to infinity. The authors need to clarify whether they allow $r$ also increases according to Assumption 1. If so, then the exponential improvement claimed in Remark 1 is suspectable, since $r$ can also scale linearly in  $|S| |A|$. If not, such exponential improvement is unfair, since Dann and Brunskill 2015 does not impose such strong low-rank assumption. A minor typo is that $O(N+|S| |A|)$ is not fully correct, and it should be $\tilde{O}(N+|S| |A|)$ according to Theorem 1. 

2. In the proof of Theorem 1, the value of $p$ needs more clarification. Lemmas 5 and 7 require the condition that $p<1/2$, which is not a trivial condition according to the presented proof. Concretely, in the proof of Theorem 1, it is required that $m\leq Np|\mathcal{G}_{h}^{c}/2|$, i.e., p\geq 2/(N|\mathcal{G}_{h}^{c}/2|) C_{1}\max(\mu_{1}^{2},\mu_{0})r(N+|\mathcal{G}_{h}^{c}/2|)\log^{2}|\mathcal{G}_{h}^{c}/2|\logH\delta. You need more assumptions on $r$ or $\mu_{1},\mu_{0}$ even to guarantee that $p\leq 1$. In such case, you can not let $C_{1}$ small enough, since it requires that $C_{1}$ is large enough in your proof.

3. For the proof of Theorem 3, could the author explain how to prove the first inequality in (48)? It seems not a trivial claim.


Writing issues:

1. The writing of the proof contains some vague words, and it is very hard to understand. For example, claim 3 needs the definition of the so-called 'correct marginal distribution'. I guess 'correct' means that they have the same distributions as original $J_{h}$ and $I_{h}$.

2. Please arrange the Appendix such that the statements of the proposition/lemma are before the proof of them. Otherwise, it is quite confusing with reading your deferred proofs part without the statement of what to prove.

3. The writing of the main paper is poor. There are a lot of typos, e.g. it should be 'smaller than the number of' in the first paragraph of the introduction. Also, please first state the equation/theorem and then refer to it, e.g. on the top of page 9, the reference to equation 2 is confusing.

I will be very happy to increase my scores if the authors resolve my technical concerns.
clarity,_quality,_novelty_and_reproducibility: Clarity: The writing of the main paper and the appendix is poor according to the points above. 

Quality: The proof of main theorems seems to have some problems and needs further clarification.

Novelty: This paper presents the novel and meaningful sample complexities improvements on the collaborative multi-user reinforcement learning problem.

Reproducibility: N.A.
summary_of_the_review: In summary, this paper presents interesting results on the collaborative multi-user reinforcement learning problem. Novel sampling algorithms are designed, and the improved sample complexities are derived. However, the presentation of the paper needs more improvements, and some technical issues remain to be solved.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper consider a collaborative multi-agent RL problem where the reward matrix of the N users has a low-rank structure. The authors design algorithms that explore rewards collaboratively with N user-specific MDPs and can learn rewards efficiently in two key settings: tabular MDPs and linear MDPs. The sample complexity is reduced over non-collaborative algorithms. The reviewers and I found that the paper is well motivated and the results are generally sound. 

This is a borderline paper that warranted a discussion among the reviewers, which I conducted. The discussion coalesced around the weaknesses of the paper which everyone felt should be addressed in a proper revision before it is published in a future conference. 

1) Lack of experimental results even on toy datasets. The authors try to motivate the model via real world applications no effort is put into testing these ideas on an actual benchmark. 

2) Lack of clarity in writing. Admittedly, this paper contains some complicated ideas, having to amalgamate terminologies from the RL literature and the matrix completion literature. However, several reviewers complained about the clarity of the writing and the vagueness in some of the mathematical exposition. They provided some concrete suggestions for the authors to improve their work on. Hence, I strongly suggest to the authors to take these into account for a future conference submission. 
justification_for_why_not_higher_score: There are two weaknesses that the reviewers and I feel should be fixed before the paper is ready for acceptance.
justification_for_why_not_lower_score: Can't go lower
Decision: Reject