Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper is about multi-task learning in episodic tabular MDPs. M learner's interact with M tabular MDPs
with a shared state/action space but (potentially) different transition and reward functions. The authors
assume that the mean rewards are epsilon close over all state/action pairs and that the transition kernels are epsilon/H close
in L1 over all state/action pairs where H is the episode length. The learner's have unlimited communication at the end
of every episode.

The main contribution is a new algorithm and analysis showing that the information sharing can help when epsilon is small and
the number of state/action pairs with a large V^*(s) - Q*(s,a) gap is large. The basic idea is to maintain empirical estimates
of transitions and rewards for each learner individually and also an aggregate of all estimates. Of course the latter is somehow
an estimate of some average reward/transitions, so the algorithm adds to the corresponding confidence bounds a term that depends
on epsilon. Besides the modified bonus terms, the learner uses essentially an instance of the Euler algorithm for each MDP.
That's quite a natural idea, and the resulting bounds make sense. 

The authors also provide lower bounds. These are of a minimax-ish flavour and show that there /exist/ MDPs where the upper bounds
are tight. I find this to be only quite weak evidence that the upper bounds are expressed using the "right" quantities, if such
things even exist.
main_review: Clarity:

The paper is generally very easy to read. I did collect quite a long list of minors below that the authors might find useful for
improving the manuscript.


Correctness:

The results pass basic sanity checks, but I did not check at all the proofs.


Impact:

Tabular MDPs won't find applications anytime soon (especially in complicated settings like this), so the main question is 
what will be the theoretical impact. Actually the authors could do a lot better to explain the impact of the technical contribution. See
the next comment.


Novelty:

The specific setting is new to my knowledge, though I have not followed in great detail this line of work. The approach (at least in hindsight) feels
like about the first thing you would try.

What is missing from the authors is a clear explanation of the technical novelty of their analysis. If I were to dive into the 40 page appendix, 
what parts will I find most exciting and why? How can I use the ideas in my papers? This is especially important because 
the analysis is borrowing (as it must) a lot of material from the Euler analysis.


Overall:

The topic of study is interesting and the paper is well written. I would be much more excited if the authors can argue convincingly that they have developed
some new and useful techniques. Nevertheless I lean towards acceptance.


Minors:

* What if epsilon is unknown? Can you prove a lower bound in this case?

* L51. Given the minimax nature of the lower bounds, I am not sure the upper and lower bounds truly characterise the complexity of the problem. 
Maybe the 'real' bound depends on some other complexity measures? Or there is a non-trivial Pareto frontier?

* L55. What is the complement of a set without a universe?

* L58. Using a \vee b = min(a, b) and a \wedge b = max(a, b) is a bit of an outrageous choice. Surely you want the other way around.

* L64. Some people might like a definition of Delta(S).

* L68. I am being petty, but the assumptions here say that P_H(. | s, a) must be supported on S_{H+1} = {bot} which is explicitly stated as not being
in S. And yet P_H(. | s, a) in Delta(S).

* L70. Some readers might like to know a little about the independence structure here.

* L77. More pettyness, but there is some dangerous language in these definitions. "expected return of player p conditioned on ..." which measure exactly
are you conditioning on and what event. Does this event really have positive probability (what if the policy will never reach some state). It seems to me
that the right way to define these value functions is via the Bellman equations, which are written just below anyways. 

* L82. Maybe I missed it, but is R_p(s, a) defined? It should be the mean of r_p(s, a).

* L82. Since you have a layered MDP, I am wondering if you really need the h indices in the value function notation?

* L108. The O(sqrt(H^2 SAK)) claim is a bit hard to believe. First, there must be logarithms. Second, are there not lower order terms
that can be dominant in some regimes. I suggest to specify precisely what is meant by Big-O here. From a mathematicians perspective this is quite
non-standard.

* L111. Note that "large enough K" here is not a universal lower bound, but a problem-dependent one. So the use of the lesssim symbol may not be quite justified.

* L140. There is a little danger in calling a players own data unbiased. Even in the single-task setting there needs to be a great deal of effort needed
to overcome the fact that the data collected by a learning algorithm may be biased. 

* L218. I find it a bit hard to believe there are no log factors in the dominant terms of Theorem 5 and similar results.

* L244. I am uncomfortable with the Big-O notation used in the statement of this theorem.

* L249. This definition of a sublinear regret algorithm would be clearer with a few quantifiers. I guess you want to fix a state/action space, episode length and
so forth and then say there exists a constant depending on these things such that for all transition kernels and reward distributions the regret is upper bounded
by such and such. Also, T should be K in this definition, right?
limitations_and_societal_impact: I have no concerns about this aspect.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The submission investigates the problem of multi-task reinforcement learning, which is where a collection of agents simultaneous learn similar tasks, ideally while exploiting the similarities in the task structure. The submission (i) proposes a formalism for this setting and (ii) designs and analyzes a model-based algorithm (Multi-task Euler) for the aforementioned formalism. The main engine Multi-task Euler is the exploitation of "subpar state-action pairs" --- i.e., state-action pairs which are suboptimal across all tasks. When there are many subpar state-action pairs, Multi-task Euler strictly outperforms Euler without information sharing. In any case, Multi-task Euler is never outperformed by Euler without information sharing.
main_review: I found the paper well-organized and largely digestible, despite the technical nature of the information content.

Multi-task learning is an important problem. The formalism suggested by the paper seems reasonable. It seems undesirable that the allowed distance between transition probabilities scales inversely with the horizon length, but I can see how this constraint would be necessary to avoid compounding divergence.

The discussion on where the improvement comes from in Theorem 5 is nicely stated.

I was added as a last minute reviewer and so did not have time to go through the proofs. Additionally, I did not have time to go through the related work, with which I am unfamiliar. Thus, I am unfortunately not able to give an assessment with high confidence. That being said, the work appears both rigorous and topical, and I have no major complaints.
 
# Small Comments
Footnote 1: Isn’t this assumption necessarily true for MDPs with fixed horizon H?
Typo line 11 of algorithm? (ind-Q floor should be agg-Q ceiling?)
limitations_and_societal_impact: It is confusing that the first sentence of the societal impact paragraph is about the work's limitations, rather than its societal impact.

This sentence is worded awkwardly: To avoid unintended consequences when deployed in the real world, another major open problem is to ensure safety of our algorithm under model misspecification.

It also doesn't really clarify the submission's position of the societal impact of the work. If the submission does not believe the work will have any broader societal impact, then it should either simply say so, or remove the (one sentence) societal impact section altogether.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a multi-task RL problem, called epsilon-Multi-Player Episodic Reinforcement Learning. This study got inspired by a recent study on multi-task multi-armed bandits. The assumption is that all tasks are defined with the same state and action spaces, and $epsilon$-dissimilar in terms of transition and reward functions. As the first main contribution, the authors define the notion of subpar state-action pairs which captures the amenability of information sharing among tasks. Then, the author propose a model-based algorithm MULTI-TASK-EULER algorithm, which exploits the given dissimilarity parameter as an advantageous information sharing among tasks to achieve better regret upper bounds in comparing to being without knowing $epsilon$. The authors also present the gap-dependent and gap-independent regret lower bounds. 

main_review: In overall, the paper pursues an interesting research problem. The proposed method makes sense. It's interesting to see how each agent can exploit the knowledge transfer and the disssimilarity level to select actions. Both uncertainty are combined in a principled way to compute LB and UB.

Given the corrections in appendix, would the upper bound in Theorem 6 becomes larger, then how is it compared to the collective regret bound of the individual STRONG-EULER? And how should the discussion about the gap between UB and LB in the paragraph below Theorem 8 change?

The bounds can be arbitrarily large in a factor of H. In RL setting, this would not be interesting, where H can be very large or infinite. It's understandable that the proofs are simply inspired by those in the the multi-task multi-armed bandits paper [37]. However it will become more interesting if the bounds can be independent from H, e.g. with a different objective: infinite-horizon or discounted return.

An important point would be the proposed theory should be backed up by some experiment results, e.g. both on the multi-task multi-armed bandits [37] and one multi-task RL problem. 



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper formulates a multi-task concurrent RL problem, even the tasks are not identical. it also proposes a prototype algorithm for tabular MDPs and provides theory bounds.
main_review: -Pros

-- This paper provides a clear problem formulation and theoretical derivation.

-Cons:

-- No experiment results to show the superiority of the proposed algorithm, even in a toy environment.


Frankly speaking, This paper does not fall in the main scope of my review range, I think the main idea is soundness but without verification of the deduction. It may provide some insight for multi-task RL, however, it's currently far away from the practical condition.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies multi-task reinforcement learning (RL) in tabular episodic MDPs. It studies an online setting, by showing that when the agents are facing similar but different MDPs, their collective performance, in terms of both gap-dependent and -independent regrets, can be improved through information sharing. Almost matching lower bounds are also provided.
main_review: Originality: The multi-task RL definition in this paper, in terms of Definition 1, is new to my knowledge of the literature. The work combines multiple important techniques and ideas from the literature of multi-task bandits and single-task gap-dependent regret analysis. It is very clear how the work differs from the literature, and reading the related work is enjoyable.


Quality: The submission is technically sound, and the claims are well-supported by detailed proofs (though with several errors corrected in the errata in the appendix). This is definitely a complete piece of work. The authors have also done a good job discussing the weaknesses/limitations of the work. I have tried to do some sanity-check of the proofs, which turned out to be correct. However, as the appendix is very long, I may fail to catch some errors, if there are.


Clarity: The paper is well-written, well-organized, and enjoyable to read. It has also adequately informed the reader, by providing enough information to reproduce the results. As a theory paper, the claims are clear to read, and each result is followed by explanations to help the reader understand. 


Significance: The results are important, since a good formulation and a sharp theoretical understanding of multi-task RL is relatively open. The results in this paper would open up several interesting future directions. The setting is defined clearly, and requires significant effort to address (compared to the counterpart in the bandit setting). The main contribution, which concerns how to use the data from other tasks by constructing \bar{agg-Q_p} and \underline{agg-Q_p}, is advancing the SOTA theory of the area, and is unique in the area of multi-task RL, to my knowledge.


Minor comments:
1. In pseudocode of Algorithm 1, it seems that line 2 and line 16 should have the same indent (both are for all p)? It would be clearer to specify the (initial and updated) values of ind-b_p and agg-b_p, and how hat{r} and hat{P} are updated (at least point to some equations in the paper).
2. Overflow of equations in the end of page 5.
3. The "e.g." is misplaced (should be outside "[]") in line 267. Same as in line 289.


Overall, this is a well-written paper, addressing an important theoretical question in RL, though by combining several ideas in the literature. The theoretical results are sound, as both (almost-tight) upper and lower bounds are provided.
limitations_and_societal_impact: Yes. Both limitations and potential societal impact have been discussed appropriately.
review_title: null

Meta-review: The paper presents a method to transform a multi-task MDP into a multi-player game where agents act in related but slightly environments, and share information. Several reviewers commented on the quality and clarity of writing, and while there were many specific technical questions, they were mostly clarified in the responses. One point of criticism from several reviewers is the lack of technical novelty. However, in the discussion, the reviewers also agreed on the importance of multi-task RL and that the theoretical results are state-of-the-art. As stated by two of the reviewers, experiments in common domains could be useful to demonstrate the practical applicability. I encourage the authors to consider this point in future work.
Decision: Accept (Poster)