Provably efficient multi-task reinforcement learning with model transfer
Authors: Chicheng Zhang
Zhi Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-task learning
Provably efficient reinforcement learning
Model transfer

Abstract: We study multi-task reinforcement learning (RL) in tabular episodic Markov decision processes (MDPs). We formulate a heterogeneous multi-player RL problem, in which a group of players concurrently face similar but not necessarily identical MDPs, with a goal of improving their collective performance through inter-player information sharing. We design and analyze a model-based algorithm, and provide gap-dependent and gap-independent regret upper and lower bounds that characterize the intrinsic complexity of the problem.

Provably Efficient Multi-Tasi Reinforcement Learning with Model Transfer
Chicheng Zhang University of Arizona chi chichengoss arizona. edu
Zhi Wang
University of California San Diego zhiwangdeng ucsd. edu
Abstract
We study multi-task reinforcement learning (RL) in tabular episodic Markov deci- sion processes (MDPs). We formulate heterogeneous multi-player RL problem, in which group of players concurrently face similar but not necessarily identical MDPs, with a goal of improving their collective performance through inter-player information sharing. We design and analyze algorithm based on the idea of model transfer, and provide gap-dependent and eap-independent upper and lower bounds that characterize the intrinsic complexity of the problem.
1 Introduction
In many real-world applications, reinforcement learning (RI.) agents can be deployed as a group to complete similar tasks the same time. For example, healthcare robotics, robots are paired with people with dementia to perform personalized cognitive training activities by learning their preferences [42, 21]; in autonomous driving, a set of autonomous vehicles learn how to navigate and avoid obstacles in various environments [27]. In these settings, each learning agent alone may only be able to acquire limited amount data, while the agents as a group have the potential to collectively learn faster through sharing knowledge among themselves. Multi-task learning [7] is practical framework that can be used to model such settings, where set of learning agents share/transfer knowledge improve their collective performance.
Despite many empirical successes of multi-task RI. (see, e.g., [51, 28, 27J) and transfer learning for RI. (see, e.g., [26, 39]), a theoretical understanding of when and how information sharing or knowledge transfer can provide benefits remains limited. Exceptions include [16, 6. 11, 17, 32, 25], which study multi-task learning from parameter representation transfer perspectives. However, these works still do not provide a completely satisfying answer: for example, many application scenarios, the reward structures and the environment dynamics only slightly different for each task this is, however, not captured by representation transfer [11, 17] or existing works on clustering- based parameter transfer [16, 6]. In such settings, is it possible design provably efficient multi-task RL algorithms that have guarantees never worse than agents learning individually, while outperforming the individual agents in favorable situations?
In this work, we formulate an online multi-task RL problem that applicable to the aforementioned settings. Specifically, inspired the e-Multi-Player Episodic Reinforcement Learning (abbreviated as e-MPERL) problem, which all tasks share the same state and action spaces, and the tasks are assumed to be similar-i.e. the dissimilarities between the environments of different tasks (specifically, the reward distributions and transition dynamics associated with the players/tasks) are bounded in terms of dissimilarity parameter e 2 0. This problem not only models concurrent RL [34, 16] as a special case by taking = 0, but also captures richer multi-task RL settings when is nonzero. We study regret minimization for the c-MPRII. problee, specifically:
recent study multi-task multi-armed bandits [43], we formulate
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1. We identify problem complexity notion named subpar state-action pairs, which captures the amenability information sharing among tasks c-MPERL problem instances. As shown in the multi-task bandits literature (e.g.. [43]), inter-task information sharing is nor always helpful to reduce the players' collective regret. Subpar state-action pairs, intuitively speaking, are clearly suboptimal for all tasks, for which we can robustly take advantage of (possibly biased) data collected for other tasks to achieve a lower regret in a certain task.
2. In the setting where the dissimilarity parameter is known, we design model-based algorithm MULTI-TASK-EUL -AELLER (Algorithm 1), which is built upon state-of-the-ar thatt algo- rithms for learning single-task Markov decision processes (MDPs) [3, 46, 36], as well as algorithmic ideas of model transfer in RL [39]. MULTI-TASK-BULL dissimilarity assumption to robustly take advantage of information sharing among tasks, and achieves regret upper bounds in terms of subpar atatenaction pairs, in both (value function suboptimality) gap-dependent and gap-independens fashions. Specifically, compared with a baseline algorithm that does not utilize information sharing, MULTIITASK -AS---AAS-- has regret guarantee that: (1) is never worse, i.e., it avoids negative transfer [33]; (2) can be much superior when there are a large number of subpar state-action pairs.
crucially utilizes the
3. We also present gap-dependent and gap-indepennent regret lower bounds for the 6-MPERL problem in terms of subpar state-action pairs. These lower bounds nearly match the upper bounds when the episode length of the MDP is a constant. Together, the upper and lower bounds characterize the intrinsic complexity of the e-MPERL problem.
2 Preliminaries
Throughout this paper, we denote by [n] == { n2. For a set A in a universe U, we use AC U \ to denote its complement. Denote by A (XX the set of probability distributions over X. For functions f.g. we use f S 9 or
O(g) (resp. f ス 9 or f [(g)) to denote that there exists some constant e > O, such that f S cg (resp. f 2 cg), and use f = 9 to denote f S 9 and f ス simultaneously. Define a V : max(a, b), and a A b == min(a, b). We use E to denote the expectation operator, and use var to denote the variance operator. Throughout, we use Ō(.) and S2(-) notation to hide polylogarithmic factors.
Multi-task RL in episodic MDPs. We have a set of M MDPs {Mp Ao. p-11 each associated with a player p E [M]] Each MDP Mp regarded as a task. The MDPs share the same episode length H E N,,, finite state space S. finite action space A, and initial state distribution Po E A(S). Let 1 be default terminal state that is not contained in S. The transition probabilities P, F x A - A(S (-)) and reward distributions Tp S x A - A[(0, 1)) of the players are not necessarily identical. We assume that the MDPs are layered', in that the state space S can be partitioned into disjoint subsets (S,) p=1 where Pa is supported on St, and for every p E [M]. h E [H] and every E Sp, E A, (- s, a) is supported on S here, we define S {1}. We denote by S := [S] the size of the state space, and A := |A| the size of the action space.
Interaction process. The interaction process between the players and the environment is as follows: at the beginning, both (r and (P are unknown to the players. For each episode E [K], conditioned on the interaction history up to episode k 1, each player p E [M] independently interacts with its respective MDP Mp: specifically, player p starts with state st ~ Po, and every step (layer) h E [H], it chooses action -/. transitions to next state &t kh ~ Pp o ah and receives stochastic immediate reward rh.p ~ rrp( ship. oh.p)): after all players have finished their k-th episode, they can communicate and share information. The goal of the players is to maximize their expected collective reward E <>* M D kh.p
M
Policy and value functions. A deterministic, history-independee policy π is mapping from S to A, which can be used by a player to make decisions in its respective MDP. For player and step h, we
'This is a standard assumption (see, e.g., [44]). It is worth noting that any episodic MDP (with possibly nonstationary transition and reward) can be converted to layered MDP with stationary transition and reward, with the state space size being H7 times the size of the original state space.

---

use Vi SA + [0, H| and Qh.p Sh x A + [0, H] to denote its respective value and action- value functions, respectively. They satisfy the following recurrence known as the Bellman equation:
Vh [M] (s) (s, (s))), (s,p(s Rp a) + ((Pp)it
where we use the convention that vH+1p(1) (1) = O, and for f Su41 - R. (s,.)(s,a) = Exesh Pp(s' s, f('),, and as) = (pprp(-1s.a) [f] is the expected immediate reward of player p. For player p and policy n, denote by Vo.p E Esyopo (v))(s)) its expected reward.
For player p. we also define its optimal value function Vi S₁ - [0, H) and the optimal action- value function @h.pp Sh x A - [0, using the Bellman optimality equation:
vh E [ Vh (s) = max Qh (8. a), Qh a) = Rp(s. + (Pp (PPVit1,))s.a)) a),
(1)
where we again use the convention that -=+ = 0. For player denote by Vo, EsI-po (Vttp(t)) its optimal expected reward.
Given a policy æ, as Vi, for different h is are only defined in the respective layer Sn, we "collate" the value functions (h ) and obtain single value function V S [U + R. Formally, for every h E [H + 1] and E Sh.
(s) == (s).
We define 27 V Q similarly. For player p. given its optimal action value function Q7 any of its greedy policies (5) E argmax,e. (7 (s.s a) is optimal with respect to Mp.
Suboptimality gap. For player p. we define the suboptimality gap of state-action pair (s, as - - - Q2(s, (s.a.. a). We define the mininum suboptimality gap of player as gap = (s.)), gap a), and the minimum suboptimality gap over all players as gapmin
min gapp.min For player p E [M]. define Zp.opt == (s, a) gap, (s, a) = 0} as the set of optimal state-action pairs with respect to p.
Performance metric. We measure the performance of the players using their collective regret, i.e., over total of episodes, how much extra reward they would have collected expectation if they were executing their respective optimal policies from the beginning. Formally, suppose for each episode k. player p executes policy n² (p), then the collective regret the players defined as:
K
Reg( K)
ΣΣ
Vo,p
Vor
Baseline: individual STRONG-EULER. A naive baseline for multi-task RL is to let each player run separate RL algorithm without communication. For concreteness, we choose let each player run the state of the art STRONG-EULER algorithm [36] (see also its precursor EULER [46]), which enjoys minimax gap-independent [3, 8] and gap-dependent regret guarantees, and refer to this strategy as individual STRONG-EULES Specifically, as it is known that STRONG-EULER
BERONG-EULER has collective regret of S² A). addition, by union bound and summing up the gap-dependent regret guarantees of STRONG-EULER for the M MDPs altogether, it can be checked that with probability 8. individual STRONG-EULER has collective regret of order2
has regret of Ö(VH'SAK + S² A), individual
O(MVH'SA
MSAK 8
H
H gap, sap,(s,a) a)
SA gapmin min
In
Σ
Σ
+ S
A
gapp.min
PE[M]
(p.0)
(2 p.ope
'The originally-staten gap-depeneeee dependeennnnt regret bound of STRONG-BULER ([36), Corollary 2.1) uses slightly different notion of suboptimality gap, which takes an extra minimum over all steps. A close examination of their proof shows that STRONG- STRONG-EULLER has regret bound (2) in layered MDPs, See also Remark 21 in Appendix C.4.

---

Our goal is to design multi-task RL algorithms that can achieve collective regret strictly lower than this baseline both sup-dependent and sap-indeppendet fashions when the tasks are similar.
Notion of similarity. Throughout this paper, we will consider the following notion of similarity between MDPs in the multi-task episodic RL setting.
Definition 1. A collection of MDPs (M is said be e-dissimilar, if for all p,q q [M], and (8, E
Rp(s.a) Rg(s,a)| (Pp(-1s.0) P.(-1s.a)lla c H
this happens, call (Mp) an AMMlti-Playee Episodic Reinforcement Learning (abbrev. c-MPERL) problem instance.
If the MDPs in (Mp) are 0-dissimilar, then they are identical by definition, and our interaction protocol degenerates to the concurrent RL protocol [34]. Our dissimilarity notion complementary to those of [6, 16]: they require the MDPs to be either identical, or have well-separated parameters for least one state-action pair; in contrast, our dissimilarity notion allows the MDPs to nonidentical and arbitrarily close.
We have the following intuitive lemma that shows the closeness of optimal value functions of different MDPs, terms of the dissimilarity parameter e:
Lemma 2. If (Mp)
c-dissimilar, then for every P.q E [M] and (s, E x (7(s,a) (7 a) < 2He; consequently, ggpp,(s.a) gs,, S 4Hc.
M
Algorithm
We now describe our main algorithm, MULTI-TASK-EULER (Algorithm 1). Our model-based algo- rithm is built upon recent works on episodic RL that provide algorithms with sharp instance-dependent guarantees in the single task setting [46, 36]. In nutshell, for each episode & and each player the algorithm performs optimistic value iteration construct nigghprrobabllin upper and lower bounds for the optimal value and action value functions Vi and 17 and uses them to guide its exploration and decision making process.
Empirical estimates of model parameters. For each player p, the construction of its value func- tion bound estimates relies on empirical estimates on its transition probability and expected reward function. For both estimands, we use two estimators with complementary roles, which are two different points of the bias- variance tradeoff spectrum: one estimator uses only the player's own data (termed individual estimate), which has large variance; the other estimator uses the data collected by all players (termed aggregate estimate), which has lower variance but can easily be biased, as transition probabilities and reward distributions are heterogeneous. Such algorithmic idea of "model transfer", where one estimates model in one task using data collected from other tasks has appeared in prior works (e.g., [39]). Specifically, at the end episode k. for every E [H] and (s, a) E SA A, the algorithm maintains its empirical count of encountering (s, a) for each player p. along with its total empirical count across all players, respectively:
M
(s == Σ ((hh =s,a)) n(8, = Σ
Σ
(s, (3)
1=1
1=1
The individual and aggregate estimates of immediate reward R(s, a) are defined as:
Σi=1 1 (shhpr (h.p)) (8, (s,a) Thup
1 (loh.p hh,p) (s, a) rha
Rp(s,a)==
a)
np(s,a) a)
n(s, a)
(4)

---

Algorithm 1: MULTI-TASK-BULBR
Input: Failure probability 8 (0, 1). dissimilarity parameter 2 Initialize: Set (L) = 0 for all p in [M], where - is the only state in S#+11 ;
for k 1,2,..... ..., K do
for p = 1,2...., do
// Construct optimal value estimates for player
for h = H. 1,.... do
for (8,a)= E S₁ x A do
Compute:
ind-Qp(s, a) Rp(s,a) (P,V,) + ind-by
7
ind-Q, (s, - R (P,K,),,)) (sd)
agg-Q, (8, R(s,a)+ + (PV,),,))) as)) agg-Q Q (s, a) R(s,o) + (PV))(ss, agg-by(s, a):
10
Update optimal action value function upper and lower bound estimates:
(s(),) min H - h i, a). agg- Qp(,a)(s)))
Q (s,aa max ind-- (s, agg- (s, for 8 E Sn. do Define n² (p) argmax (s,aa) Update ps(s) Qp (p) K,(s) Q,, (s, (D))s).
13
15
// All players p interact with their respective environments, and update reward and transition estimates
for p 1, do Player p executes policy (p) on MM and obtains trajectory (s hh h.p h.pp h=1- Update individual estimates transition probability P, reward Ry and count up using the first parts of Equations (3), (4) and (5). Update aggregate estimates of transition probability P. reward and count n(::.) using the second parts of Equations (3), (4) and (5).
17
18
19
Similarly, for every h [H] and (s,a,8") Sn A Sh+1, we also define the individual and aggregate estimates of transition probability as:
Py (s,))= = Et_ (1sh oh 1//1 (s, (s,a.s')
ap(
(5)
P(s' s,a) = Σk Eper
((s) an sh+ (s, (')
n(s,a) a)
If If, a) = we define A(s, a) = and (P's' s,
| and if (s, a) 0, we define Rp(s, a) and P (s' | a) [S. The counts and reward estimates can be maintained by MULTI-TASK-FULFFR efficiently an incremental manner.
Constructing value function estimates via optimistic value iteration. For each player p. based on these model parameter estimates, MULTI-TASK- -UCLRR performs optimistic value iteration to
compute the value function estimates for states at all layers (lines 3 to 15). For the terminal layer + 1, (1) = trivially, so nothing needs
done. For earlier layers E [H], MULTI-TASK- -EULER iteratively builds its value function estimates in backward fashion. At the time of estimating values for layer h, the algorithm has already obtained optimal value es-
timates for layer h + 1. Based on the Bellman optimality equation (I), MUL.T--TASK-EULL.

---

estimates (27,s, a)) (07(s,a))sEss i... (Vp(5))eeS.44 and (Vp(s))eES...) (lines 5 to 12).
using model parameter estimates and its estimates of (V) ES SSS
Specifically, MULTI-TASK-EULER constructs estimates of Q2(8, a) for all 8 E S₁ E A in two different ways. First, uses the individual estimates of model of player p to construct ind-Q, and ind-Qp- upper and lower bound estimates of Qp (lines and 9); this construction is reminiscent of EULER and STRONG-EULER [46, 36], in that if we were only to use ind-Q, and ind-Qp our opti- mal action value function estimate Qp and Op" our algorithm becomes individual STRONG-EULER. The individual value function estimates are key to establishing SALLT-TASS--ULLREE ' fall-back guarantees, ensuring that it never performs worse than the individual STRONG-EULER baseline. Second, it uses the aggregate estimate of model to construct agg-Q, p lower bound estimates of Q2 (lines and 7); this construction unique the multitask learning setting, and is our new algorithmic contribution.
pp
and agg-Q,, also upper and
To ensure that agg Qp and ind-Qp (resp. agg-Q, and ind-Q,) Q are valid upper bounds (resp. lower bounds) of Q7 MULTI-TASE -ELLER adds bonus terms ind-by(s, a) and agg-bp(s. a), respectively. in the optimistic value iteration process, to account for estimation error of the model estimates against the true models. Specifically, both bonus terms comprise three parts:
ind-b,(s, a) = brw (ni(ss,), 0) + Uprob (Pp( 8, a), up (p((s,)) (), V kp.0) +
bser (Ppl- 8, a). (p, i)) V p. Kp:
agg-bp(s, a): = brw (n(s, a). + Uprot (P(- s, a). a. m(s, V p. v.
bstr (P( 8, a), ((s a), V). Km.
where
L(n) n
brw (n, (2)x))=11 = A x+
var g'n
V(s') L(n)
Uprob U: n. V.V = A 2n +
n
Bying
(V(s') - [(()))2) M(n) HL(m)
+ n
n
S Eging (V(s') - V(s)))2 L(n) HSL(n)
bar V.n.V.V., = k +
and [(n) x In( MSAn
The three components in the bonus terms serve for different purposes:
1. The first component accounts for the uncertainty the reward estimation: with prob- ability 1 O()), at)ss,a= a)( s brw (n,(s,a),0). and R(s,a) RR( < brw (n(s, (n(ss,),e))
2. The second component accounts for the uncertainty in estimating (PPV)))s, a): with proba- bility - 0()), (O)) (s, a) S bprab (Pp(. 8, 8, (,,)),)(s a). Vp. Kp: and (1V))) a) S Upros (iP( 18 n(s, V, E,,e).

---

3. The third component accounts for the lower order terms to ensure
strong
optimism
[36]: with probability - O(6), (P, pp)(V, (),(s))))
butr (Pp( 8, a) up (s, a) V K).
and PP)P - (s))
bprob (P(-) (((.)s.).. n(s, a), V c).
Based on the above concentration inequalities and the definitions of bonus terms, it can shown inductively that, with probability 1 O()), both agg-Qp and ind-Qp (resp. agg-Q, and ind- valid upper bounds (resp. lower bounds) of Op
Finally, observe that for any (s, a) E S, (s. a) has range [0, H-h+1]. By taking intersections of all confidence bounds of Q7 it has obtained, MULTI-TASK-EUU lower bound estimates for Q7 a). Qp (s, a) and L, (s, a) respectively, for (s, a) E Sh A (line 11 to 12). Similar ideas on using data from multiple sources to construct confidence intervals and guide explorations have been used by [37, 43] for multi-task noncontextual and contextual bandits. Using the relationship between the optimal value V (s) and and optimal action values ( a) A
constructs its final upper and
MULTII-AAK-EULLR also constructs upper and lower bound estimates for Vū V (s) and V (s))). respectively for s E S₁ (line 15).
Executing optimistic policies. At each episode k. for each player p, its optimal action-value function upper bound estimate Q₂ induces a greedy policy л T²()) 8 - argmax 2p a) (line 14); the player then executes this policy at this episode to collect a new trajectory and use this to update its individual model parameter estimates. After all players finish their episode kt, the algorithm also updates its aggregate model parameter estimates (lines to 19) using Equations (3), (4) and (5), and continues to the next episode.
4 Performance guarantees
Before stating the guarantees of Algorithm 1, we define an instance-dependent complexity measure that characterizes the amenability to information sharing.
Definition 3. The set of subpar state-action pairs is defined as:
I. = (s, a) E x A: 7p (s, 96He).
where we recall that gap, a) = Vi (s) (s.
Definition 3 generalizes the notion of subpar arms defined for multi-task multi-armed bandit learn- ing [43] in two ways: first, is with regards to state-action pairs as opposed to actions only; second, in RI., suboptimality gaps depend optimal value function, which in turn depends on both immediate reward and subsequent long-term return.
To ease our later presentation, also present the following lemma.
Lemma 4, For any (s,a) a) E Ic we have that: for all p E [M), (8, a) & Zp,opt- where we recall that Zpropt (s,a) a) gap, (s, = =0} is the set of optimal state- trate-action pairs with respect to p. (2) for all p.q E [M], (s, a) 2 1 (s.
The lemma follows directly from Lemma 2: its proof can be found in the Appendix along with proofs of the following theorems. Item implies that any subpar state-action pair is suboptimal for all players. In other words, for every player p. the state-action space S x A can be partitioned to three disjoint sets: Ie, Zp.opt. (I, U ) Item implies that for any subpar (s, a), its suboptimal gaps with respect to all players are within constant of each other.
4.1 Upper bounds
With the above definitions, we are now ready to present the performance guarantees of Algorithm 1. We first present a gap-independent collective regret bound of MULTTI-TASK-FUTT
7

---

Theorem 5 (Gap-independent bound). If {Mp] p=1 satisfies that with probability 1-
are e-dissimilar, then MULTI-TASK-EUUAE EULER
Reg(K)= S (M V + + S
We again compare this regret upper bound with individual STRONG-EULER'S gap independent regret bound. Recall that individual STRONG-EULER guarantees that with probability 6,
() s [M + MH
We focus on the comparison on the leading terms, i.c., the v K terms. As MV ~ M H + M / 1 K, we see that an improvement in the collective regret bound comes from the contributions from subpar state-action pairs: the M V HH|I. K term is reduced |K, factor of Ō M improvement. Moreover, if | SA and M > MULTI-TASK- provides a regret bound of lower order than individual STRONG-EULER.
We next present gap-dependent upper bound on its collective regret.
Theorem 6 (Gap-dependent upper bound). If ( x=1 [Mp}== are e-dissimilar then MULTI-TASK-EUUI
satisfies with probability
MSAK
H
1 gap, (8,
Reg(K) K) S In(
Σ
Σ
Σ
gapp.min (Z.p)))
PE[M]
(
H minp (8)
MSAK
MSA gaPmin
+ In(
M
8
(S.a)ET.
where recall that gapp,min (ap)
(s, a),, and gapmin min, gapp.min-
Comparing this regret bound with the regret bound obtained by the individual STRONG-EULER baseline, recall that by summing over the regret guarantees STRONG-EULER for all players p E [M], and taking union bound over all p, individual STRONG-EULDE guarantees a collective regret bound of
Reg(K) S In(
MSAK
H
Σ
1
+
8
gapp,min
gap, (8,,) a)
ME[M]
(4,a)E7p.og
(Z.)E(I.UZp.opll
Σ
11
Inf
MSAK
2 Aln
SA gap min
(s.a)ET, PE[M] (s,
5
that holds with probability 1-6 We again focus on comparing the leading terms, i.e., the terms that have polynomial dependences on the suboptimality gaps in the above two bounds. It can be seen that an improvement in the regret bound by MULTI-TASS TAATI--TAK--UUTS -ULFRR comes from the contributions from the subpar state-action pairs: for each (8, E Ie, the regret bound is reduced from Σpe[M) (epp( to
H²
1 improvement. Recent work of [44] has shown that in the single-task miny (s.a) factor of O ((1)
H
3aa with a sharper problem-dependent complexity setting, it is possible to replace E(.n)) gapp.mtn term that depends on the multiplicity of optimal state-action pairs. We leave improving the guarantee of Theorem 6 in a similar manner as interesting open problem.

---

Key to the proofs of Theorems 5 and 6 is new bound on the surplus [36] of the value function estimates. Our new surplus bound is minimum of terms: one depends on the usual state- action visitation counts of player p, the other depends on the task dissimilarity parameter and the state-action visitation counts of all players. Detailed proofs can be found at Appendix C.
4.2 Lower bounds
To complement the above upper bounds, we now present gap-dependent and gap-independent regret lower bounds that also depends our subpar state-action pair notion. Our lower bounds are inspired by regret lower bounds for episodic RL [36, 8] and multi task bandits [43].
Theorem (Gap-independent lower bound). For any A 2 2, H 2 2, 5 4H, SA, M MN,, and 1 E N with 1+ [ SA and 1 < SA 4(S + H),, there exists some that satisfies: for any algorithm Alg, there exists an e-MPERL problem instance with S states, A actions, M players
and an episode length of such that
I TOXT
2 I, and
E (PEAAI(K) 2 Ω (M + + VMHHIK)
We also present gap-dependent lower bound. Before that, we first formally define the notion of sublinear regret algorithms: for any fixed e, we say that an algorithm Alg is a sublinear regret algorithm for the e-MPERL problem if there exists some C 0 (that possibly depends the state-action space, the number of players, and c) and a < 1 such that for all K and all e-MPERL
environments, (RegAi((K). S CKa
N. be any set of values that satisfies: (1) each As.app E [0, H/48), f2r every (s, E [S] [M]. there exists at least one action a [A] such that Seap 0, and (3) every (8,a) E [Si] x [A] and p,q E [M), Aas.p As,a.l I c/4. There exists an c-MPERI. problem instance with states, actions, M
Theorem 8 (Gap-dependent lower bound). Fix 2 O. For any S N, A 4 with S 2 2(H 1), let S1 S 2(H 1); and let { (Ae..p) (S:
H
players and an episode length of H. such that = [S.]. |Sp for all 2, and
gap,(s, a) = Asa.ps V(s, a. p) E [S1] [A] [M]; for this problem instance, any sublinear regret algorithu for the c-MPERL problem must satisfy:
H
H²
(eggAg((K) (K) 2 Ω InK
Σ
+
gap, (3,
min, gap, gap,
PE[M] (s.a) (crwaar))
(
(s,)(5
Comparing the lower bounds with MULTI-TASK-EULEES regret upper bounds in Theorems and we see that the upper and lower bounds nearly match for any constant H. When H is large, key difference between the upper and lower bounds is that the former are in terms I,, while the latter are in terms of Ie: f). We conjecture that our upper bounds can be improved by replacing I, with Ie & our analysis uses clipping trick similar to [36], which may be the reason for suboptimal dependence on H. We leave closing this gap as an open question.
Related Work
Regret minimization for MDPs. Our work belongs to the literature of regret minimization for MDPs, e.g., [5, 18, 8, 3, 9, 19, 10, 46, 36, 49, 45, 44]. In the episodic setting, [3, 10, 46, 36, 49] achieve minimax VH²SAK regret bounds for general stationary MDPs. Furthermore, the EULER algorithm [46] achieves adaptive problem-depencee dependenn regret guarantees when the total reward within an episode is small when the environmental norm of the MDP small. [36] refine EULER, proposing STRONG- EULER that provides more fine-grad fine-grained depeneenndnnt (log K) regret guarantees. [45, 44) show that the optimistic Q-learning algorithm [19] and its variants can also achieve gap-dependent logarithmic regret guarantees. Remarkably, [44] achieve regret bound that improves over that of [36]. in that replaces the dependence on the number of optimal state-action pairs with the number of non-unique state-action pairs.
JIRONG-EULERR

---

Transfer and lifelong learning for RL. A considerable portion of related works concerns transfer learning for RL tasks (see [40, 24, 50] for surveys from different angles), and many studies investigate a batch setting: given some source tasks and target tasks, transfer learning agents have access to batch data collected for the source tasks (and sometimes for the target tasks as well). In this setting, model-based approaches have been explored in e.g. [39]; theoretical guarantees for transfer of samples across tasks have been established in c.g., [25, 41]. Similarly, sequential transfer has been studied under the framework of lifelong RL in e.g., [38, 1, 15, 22]-in this setting, agent faces sequence of RL tasks and aims to take advantage of knowledge gained from previous tasks for better performance in future tasks; in particular, analyses on the sample complexity of transfer learning algorithms are presented in [6. 29] under the assumption that an upper bound on the total number of unique (and separated) RL tasks is known. We note that, in contrast, we study an online setting in which no prior data are available and multiple RL tasks are learned concurrently by RI. agents.
Concurrent RL. Data sharing between multiple RL agents that learn concurrently has also been investigated in the literature. For example, in [20, 35, 16, 12], a group of agents interact in parallel with identical environments. Another setting is studied in [16], in which agents solve different RI. tasks (MDPs); however, similar to [6, 29], it is assumed that there is a finite number of unique tasks, and different tasks are well-separated. i.c., there is a minimum gap. In this work, we assume that players face similar but not necessarily identical MDPs, and we do not assume a minimum gap. [17] study multi-task RL with linear function approximation with representation transfer, where is assumed that the optimal value functions of all tasks are from low dimensional linear subspace. Our setting and results are most similar to [32] and [13]. [32] study concurrent exploration in similar MDPs with continuous states in the PAC setting; however, their PAC guarantee does not hold for target error rate arbitrarily close to zero; in contrast, our algorithm has a fall-back guarantee, in that it always has sublinear regret. Concurrent RL. from similar linear MDPs has also been recently studied in [13]: under the assumption of small heterogeneity between different MDPs (a setting very similar to ours), the provided regret guarantee involves a term that is linear in the number of episodes, whereas our algorithm in this paper always has a sublinear regret; concurrent RL under the assumption of large heterogeneity is also studied in that work, but additional contextual information is assumed to be available for the players to ensure a sublinear regret.
Other related topics and models. In many multi-agent RL models [47, 31], a set of learning agents interact with common environment and have shared global states; in particular, [48] study the setting with heterogeneous reward distributions, and provide convergence guarantees for two policy gradient-based algorithms. In contrast, in our setting, our learning agents interact with separate environments. Multi-agent bandits with similar, heterogeneous reward distributions are investigated in [37, 43]; herein, we generalize their multi-task bandit problem setting to the episodic MDP setting.
6 Conclusion and Future Directions
In this paper, we generalize the multi-task bandit learning framework in [43] and formulate a multi- task concurrent RL problem, in which tasks are similar but not necessarily identical. We provide a provably efficient model-based algorithm that takes advantage of knowledge transfer between different tasks. Our iistance-depender regret upper and lower bounds formalize the intuition that subpar state-action pairs are amenable to information sharing among tasks.
There still remain gaps between our upper and lower bounds which can be closed by either a finer analysis or a better algorithm: first, the dependence on I, in the upper bound does not match the dependence of Te(+/H)) in the lower bound when H is large; second, the gap-dependent upper bound has 0(1**) dependence, whereas the gap-dependent lower bound only has ?(112) dependence; third, the additive dependence on the number of optimal state-action pairs can potentially be removed by new algorithmic ideas [44].
Furthermore, one major obstacle in deploying our algorithm in practice is its requirement for knowledge of e; an interesting avenue is to apply model selection strategies in bandits and RL to achieve adaptivity to unknown e. Another interesting future direction to consider more general parameter transfer for online RI, for example, in the context of function approximation.
10

---

7 Acknowledgements
We thank Kamalika Chaudhuri for helpful initial discussions, and thank Akshay Krishnamurthy and Tongyi Cao for discussing the applicability of adaptive RL in metric spaces to the multitask RL problem studied in this paper. CZ acknowledges startup funding support from the University of Arizona. ZW thanks the National Science Foundation under IIS 1915734 and CCF 1719133 for research support.
References
[1] David Abel, Yuu Jinnai, Sophie Yue Guo, George Konidaris, and Michael Littman. Policy and value transfer lifelong reinforcement learning. In International Conference on Machine Learning, pages 20-29. PMLR, 2018.
[2] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International conference on algorithmic learning theory, pages 150-165. Springer, 2007.
[3] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[4] Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008, pages 335-342. Omnipress, 2008.
[5] Peter L Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 35 42- 2009.
[6] Emma Brunskill and Lihong Li. Sample complexity of multi-tan sasti-task reinforcement learning. In Proceedings of the Twenty-Ninte Conference Uncertainty in Artificial Intelligence, pages 221-131,33 2013.
[7] Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
[8] Christoph Dann and Emma Brunskill. Sample complexity episodic fixed-horizon reinforce- ment learning. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volumm 2, pages 2818-2826, 2015.
[9] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5717-5727, 2017.
[10] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
[11] Carlo D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowledge in multi-task deep reinforcement learning. In International Conference on Learning Representations, 2020.
[12] Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforce- ment learning. In International Conference on Machine Learning, pages 1271-1279, PMLR, 2018.
[13] Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2 1..Xx:2203..00 103.04972 2021.
[14] David Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.

---

[15] Francisco M Garcia and Philip S Thomas. A meta-mdp approach to exploration for lifelong reinforcement learning. arXiv preprint arXiv:1902.00843, 2019.
[16] Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[17] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. arXiv preprint arXiv:2102.04132 2021.
[18] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 (1(4), 2010.
[19] Chi Jin, Zeyuan Allen-Zhu, Sehastien Bubeck, and Michael Jordan. Is q-learning provably ef- ficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868 4878, 2018.
[20] R Matthew Kretchmar. Parallel reinforcement learning. In The 6th World Conference on Systemics, Cybernetics, and Informatics. Citeseer, 2002.
[21] Alyssa Kubota, Emma IC Peterson, Vaishali Rajendren, Hadas Grzis, and Laurel D) Riek. Jessie: Synthesizing social robot behaviors for personalized neurorehabilitation and beyond. In Proceedings of the 2020 ACM/IEEE International Conference on Human-Roue Robot Interaction, pages 121-130, 2020.
[22] Nicholas C Landolfi, Garrett Thomas, and Tengyu Ma. A model-based approach for sample- efficient multi-task reinforcement learning. arXiv preprint 100::0007.49944 2019.
[23] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[24] Alessandro Lazaric. Transfer in reinforcement learning: a framework and a survey. In Rein- forcement Learning, pages 143-173 Springer, 2012.
[25] Alessandro Lazaric and Marcello Restelli. Transfer from multiple mdps. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[26] Alessandro Lazaric, Marcello Restelli, and Andrea Bonarini. Transfer of samples in batch reinforcement learning. Proceedings of the 25th international conference on Machine learning, pages 344-551, 2008
[27] Xinle Liang, Yang Liu, Tianjian Chen, Ming Liu, and Qiang Yang. Federated transfer reinforce- ment learning for autonomous driving. arXiv preprint 19X10:1910.06001, 2019.
[28] Boyi Liu, Lujia Wang, and Ming Liu. Lifelong federated reinforcement learning: a learning architecture for navigation in cloud robotic systems. IEEE Robotics and Automation Letters, 4(4):4555 4562, 2019.
[29] Yao Liu, Zhaohan Guo, and Emma Brunskill. Pac continuous state online multitask reinforce- ment learning with identification. In Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 16, page 438 088-446,77 2016.
[30] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. COLT, 2009.
[31] Afshin OroojlooyJadid and Davood Hajinezhad. A review of cooperative multi-agent deep reinforcement learning. arXiv preprint 1XXi:1908.00966 2019.
[32] Jason Pazis and Ronald Parr. Efficient pac-optimal exploration in concurrent, continuous state mdps with delayed updates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016
[33] Michael Rosenstein, Zvika Marx, Leslie Pack Kaelbling, and Thomas G. Dietterich. To transfer or not to transfer. In NIPS 2005 workshop transfer learning, 2005.
12

---

[34] David Silver, Leonard Newnham, David Barker, Suzanne Weller, and Jason McFall. Concurrent reinforcement learning from customer interactions. International conference on machine learning, pages 924-932. PMLR, 2013.
[35] David Silver, Leonard Newnham, David Barker, Suzanne Weller, and Jason McFall. Concurrent reinforcement learning from customer interactions. In International conference on machine learning, pages 224-932. PMLR, 2013.
[36] Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. arXiv preprini VrXiv:/905.0380 2019.
[37] Marta Soare, Ouais Alsharif, Alessandro Lazaric, and Joelle Pineau. Multi-task linear bandits. NIPS2014 Workshop on Transfer and Multi-task Learning: Theory meets Practice, 2014.
[38] Fumihide Tanaka and Masayuki Yamamura. Multitask reinforcement learning on the distribution of mdps. In Proceedings 2003 IEEE International Symposium on Computational Intelligence in Robotics and Automation, volume 3, pages 1108-113. IEEE, 2003.
[39] Matthew E Taylor, Nicholas K Jong, and Peter Stone. Transferring instances for model-base reinforcement learning. In Joint European conference machine learning and knowledge discovery in databases, pages 488-505. Springer. 2008.
[40] Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.
[41] Andrea Tirinzoni, Mattia Salvini, and Marcello Restelli. Transfer of samples in policy search via multiple importance sampling. In International Conference on Machine Learning, pages 6264 6274. PMLR, 2019.
[42] Konstantinos Tsiakas, Cheryl Abellanoza, and Fillia Makedon. Interactive learning and adap- tation for robot assisted therapy for people with dementia. In Proceedings of the 9th ACM International Conference on PErvasive Technologies Related to Assistive Environments, pages 1-4, 2016.
[43] Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel Riek, and Kamalika Chaudhuri. Mul- titask bandit learning through heterogeneous feedback aggregation. In International Conference on Artificial Intelligence and Statistics, pages 1531-1539. PMLR, 2021.
[44] Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint mrXiv:2102.0469)) 2021.
[45] Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMIR, 2021.
[46] Andrea Zanette and Emma Brunskill. Tighter problem regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
[47] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprini 1rXiv:191..1065: 2019.
[48] Kaiqing Zhang, Zhuoran Yang. Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872 5881. PMLR, 2018.
[49] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learn- ingvia reference-advantee decomposition. Advances in Neural Information Processing Systems, 33, 2020.
[50] Zhuangdi Zhu, Kaixiang Lin, and Jiayu Zhou, Transfer learning in deep reinforcement learning: A survey. arXiv preprint arXiv:2009.07888 2020.
[51] Hankz. Hankui Zhuo Wenfeng Feng, Qian Xu, Qiang Yang, and Yufeng Lin. Federated reinforcement learning. arviv preprint 1r0iv:I901 08277,, 2019.
13


Reviews:
[{"review_id": "uqALhXrKLnU", "reviewer": "Reviewer_tFPt", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "-Pros\n\n-- This paper provides a clear problem formulation and theoretical derivation.\n\n-Cons:\n\n-- No experiment results to show the superiority of the proposed algorithm, even in a toy environment.\n\n\nFrankly 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "rOOZnWUFdS", "reviewer": "Reviewer_VyG2", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "I found the paper well-organized and largely digestible, despite the technical nature of the information content.\n\nMulti-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.\n\nThe discussion on where the improvement comes from in Theorem 5 is nicely stated.\n\nI 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.\n \n# Small Comments\nFootnote 1: Isn’t this assumption necessarily true for MDPs with fixed horizon H?\nTypo line 11 of algorithm? (ind-Q floor should be agg-Q ceiling?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nThis 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.\n\nIt 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "kXZky7Marj2", "reviewer": "Reviewer_GxNs", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "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.\n\n\nQuality: 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.\n\n\nClarity: 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. \n\n\nSignificance: 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.\n\n\nMinor comments:\n1. 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).\n2. Overflow of equations in the end of page 5.\n3. The \"e.g.\" is misplaced (should be outside \"[]\") in line 267. Same as in line 289.\n\n\nOverall, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. Both limitations and potential societal impact have been discussed appropriately. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "OX3r3drkwK", "reviewer": "Reviewer_Bk4C", "summary": "This paper is about multi-task learning in episodic tabular MDPs. M learner's interact with M tabular MDPs\nwith a shared state/action space but (potentially) different transition and reward functions. The authors\nassume that the mean rewards are epsilon close over all state/action pairs and that the transition kernels are epsilon/H close\nin L1 over all state/action pairs where H is the episode length. The learner's have unlimited communication at the end\nof every episode.\n\nThe main contribution is a new algorithm and analysis showing that the information sharing can help when epsilon is small and\nthe number of state/action pairs with a large V^*(s) - Q*(s,a) gap is large. The basic idea is to maintain empirical estimates\nof transitions and rewards for each learner individually and also an aggregate of all estimates. Of course the latter is somehow\nan estimate of some average reward/transitions, so the algorithm adds to the corresponding confidence bounds a term that depends\non epsilon. Besides the modified bonus terms, the learner uses essentially an instance of the Euler algorithm for each MDP.\nThat's quite a natural idea, and the resulting bounds make sense. \n\nThe authors also provide lower bounds. These are of a minimax-ish flavour and show that there /exist/ MDPs where the upper bounds\nare tight. I find this to be only quite weak evidence that the upper bounds are expressed using the \"right\" quantities, if such\nthings even exist.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Clarity:\n\nThe paper is generally very easy to read. I did collect quite a long list of minors below that the authors might find useful for\nimproving the manuscript.\n\n\nCorrectness:\n\nThe results pass basic sanity checks, but I did not check at all the proofs.\n\n\nImpact:\n\nTabular MDPs won't find applications anytime soon (especially in complicated settings like this), so the main question is \nwhat will be the theoretical impact. Actually the authors could do a lot better to explain the impact of the technical contribution. See\nthe next comment.\n\n\nNovelty:\n\nThe 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\nlike about the first thing you would try.\n\nWhat 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, \nwhat parts will I find most exciting and why? How can I use the ideas in my papers? This is especially important because \nthe analysis is borrowing (as it must) a lot of material from the Euler analysis.\n\n\nOverall:\n\nThe 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\nsome new and useful techniques. Nevertheless I lean towards acceptance.\n\n\nMinors:\n\n* What if epsilon is unknown? Can you prove a lower bound in this case?\n\n* 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. \nMaybe the 'real' bound depends on some other complexity measures? Or there is a non-trivial Pareto frontier?\n\n* L55. What is the complement of a set without a universe?\n\n* 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.\n\n* L64. Some people might like a definition of Delta(S).\n\n* 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\nin S. And yet P_H(. | s, a) in Delta(S).\n\n* L70. Some readers might like to know a little about the independence structure here.\n\n* L77. More pettyness, but there is some dangerous language in these definitions. \"expected return of player p conditioned on ...\" which measure exactly\nare 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\nthat the right way to define these value functions is via the Bellman equations, which are written just below anyways. \n\n* L82. Maybe I missed it, but is R_p(s, a) defined? It should be the mean of r_p(s, a).\n\n* L82. Since you have a layered MDP, I am wondering if you really need the h indices in the value function notation?\n\n* 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\nthat 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\nnon-standard.\n\n* 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.\n\n* 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\nto overcome the fact that the data collected by a learning algorithm may be biased. \n\n* L218. I find it a bit hard to believe there are no log factors in the dominant terms of Theorem 5 and similar results.\n\n* L244. I am uncomfortable with the Big-O notation used in the statement of this theorem.\n\n* 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\nso 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\nby such and such. Also, T should be K in this definition, right?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concerns about this aspect.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8ARU8bxAaPj", "reviewer": "Reviewer_p2Ef", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "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.\n\nGiven 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?\n\nThe 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.\n\nAn 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. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)