Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
Year: 2021

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 an algorithm based on the idea of model transfer, and provide gap-dependent and gap-independent upper and lower bounds that characterize the intrinsic complexity of the problem.

heading: 1 Introduction
text: In many real-world applications, reinforcement learning (RL) agents can be deployed as a group to complete similar tasks at the same time. For example, in 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 a limited amount of data, while the agents as a group have the potential to collectively learn faster through sharing knowledge among themselves. Multi-task learning [7] is a practical framework that can be used to model such settings, where a set of learning agents share/transfer knowledge to improve their collective performance.
Despite many empirical successes of multi-task RL (see, e.g., [51, 28, 27]) and transfer learning for RL (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 or representation transfer perspectives. However, these works still do not provide a completely satisfying answer: for example, in many application scenarios, the reward structures and the environment dynamics are 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 to 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 is applicable to the aforementioned settings. Specifically, inspired by a recent study on multi-task multi-armed bandits [43], we formulate the �-Multi-Player Episodic Reinforcement Learning (abbreviated as �-MPERL) problem, in 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 a dissimilarity parameter � ≥ 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 �-MPERL problem, specifically:
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
1. We identify a problem complexity notion named subpar state-action pairs, which captures the amenability to information sharing among tasks in �-MPERL problem instances. As shown in the multi-task bandits literature (e.g., [43]), inter-task information sharing is not 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 a model-based algorithm MULTI-TASK-EULER (Algorithm 1), which is built upon state-of-the-art algorithms for learning single-task Markov decision processes (MDPs) [3, 46, 36], as well as algorithmic ideas of model transfer in RL [39]. MULTI-TASK-EULER crucially utilizes the dissimilarity assumption to robustly take advantage of information sharing among tasks, and achieves regret upper bounds in terms of subpar state-action pairs, in both (value function suboptimality) gap-dependent and gap-independent fashions. Specifically, compared with a baseline algorithm that does not utilize information sharing, MULTI-TASK-EULER has a 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.
3. We also present gap-dependent and gap-independent regret lower bounds for the �-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 �-MPERL problem.

heading: 2 Preliminaries
text: Throughout this paper, we denote by [n] := {1, . . . , n}. For a set A in a universe U , we use AC = U \ A to denote its complement. Denote by Δ(X ) the set of probability distributions over X . For functions f, g, we use f � g or f = O(g) (resp. f � g or f = Ω(g)) to denote that there exists some constant c > 0, such that f ≤ cg (resp. f ≥ cg), and use f � g to denote f � g and f � g simultaneously. Define a ∨ b := max(a, b), and a ∧ b := min(a, b). We use E to denote the expectation operator, and use var to denote the variance operator. Throughout, we use Õ(·) and Ω̃(·) notation to hide polylogarithmic factors.
Multi-task RL in episodic MDPs. We have a set of M MDPs � Mp = (H,S,A, p0,Pp, rp) �M p=1
, each associated with a player p ∈ [M ]. Each MDP Mp is regarded as a task. The MDPs share the same episode length H ∈ N+, finite state space S , finite action space A, and initial state distribution p0 ∈ Δ(S). Let ⊥ be a default terminal state that is not contained in S . The transition probabilities Pp : S × A → Δ(S ∪ {⊥}) and reward distributions rp : S × A → Δ([0, 1]) of the players are not necessarily identical. We assume that the MDPs are layered1, in that the state space S can be partitioned into disjoint subsets (Sh)Hh=1, where p0 is supported on S1, and for every p ∈ [M ], h ∈ [H], and every s ∈ Sh, a ∈ A, Pp(· | s, a) is supported on Sh+1; here, we define SH+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 (rp)Mp=1 and (Pp)Mp=1 are unknown to the players. For each episode k ∈ [K], conditioned on the interaction history up to episode k − 1, each player p ∈ [M ] independently interacts with its respective MDP Mp; specifically, player p starts with state sk1,p ∼ p0, and at every step (layer) h ∈ [H], it chooses action akh,p, transitions to next state skh+1,p ∼ Pp(· | skh,p, akh,p) and receives a stochastic immediate reward rkh,p ∼ rp(· | skh,p, akh,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 ��K k=1 �M p=1 �H h=1 r k h,p � .
Policy and value functions. A deterministic, history-independent policy π is a mapping from S to A, which can be used by a player to make decisions in its respective MDP. For player p and step h, we
1This 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 a layered MDP with stationary transition and reward, with the state space size being H times the size of the original state space.
use V πh,p : Sh → [0, H] and Qπh,p : Sh ×A → [0, H] to denote its respective value and action-value functions, respectively. They satisfy the following recurrence known as the Bellman equation:
∀h ∈ [H] : V πh,p(s) = Qπh,p(s,π(s)), Qπh,p(s, a) = Rp(s, a) + (PpV πh+1,p)(s, a), where we use the convention that V πH+1,p(⊥) = 0, and for f : Sh+1 → R, (Ppf)(s, a) :=�
s�∈Sh+1 Pp(s � | s, a)f(s�), and Rp(s, a) := Er̂∼rp(·|s,a) [r̂] is the expected immediate reward
of player p. For player p and policy π, denote by V π0,p = Es1∼p0 � V π1,p(s1) � its expected reward.
For player p, we also define its optimal value function V �h,p : Sh → [0, H] and the optimal actionvalue function Q�h,p : Sh ×A → [0, H] using the Bellman optimality equation:
∀h ∈ [H] : V �h,p(s) = max a∈A Q�h,p(s, a), Q � h,p(s, a) = Rp(s, a) + (PpV �h+1,p)(s, a), (1)
where we again use the convention that V �H+1,p(⊥) = 0. For player p, denote by V �0,p = Es1∼p0 � V �1,p(s1) � its optimal expected reward.
Given a policy π, as V πh,p for different h’s are only defined in the respective layer Sh, we “collate” the value functions (V πh,p) H h=1 and obtain a single value function V π p : S ∪ {⊥} → R. Formally, for every h ∈ [H + 1] and s ∈ Sh, V πp (s) := V π h,p(s). We define Qπp , V � p , Q � p similarly. For player p, given its optimal action value function Q � p, any of its greedy policies π�p(s) ∈ argmaxa∈A Q�p(s, a) is optimal with respect to Mp.
Suboptimality gap. For player p, we define the suboptimality gap of state-action pair (s, a) as gapp(s, a) = V � p (s)−Q�p(s, a). We define the mininum suboptimality gap of player p as gapp,min = min(s,a):gapp(s,a)>0 gapp(s, a), and the minimum suboptimality gap over all players as gapmin =
minp∈[M ] gapp,min. For player p ∈ [M ], define Zp,opt := � (s, a) : gapp(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 a total of K episodes, how much extra reward they would have collected in expectation if they were executing their respective optimal policies from the beginning. Formally, suppose for each episode k, player p executes policy πk(p), then the collective regret of the players is defined as:
Reg(K) =
M�
p=1
K�
k=1
� V �0,p − V π k(p) 0,p � .
Baseline: individual STRONG-EULER. A naive baseline for multi-task RL is to let each player run a separate RL algorithm without communication. For concreteness, we choose to 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-EULER. Specifically, as it is known that STRONG-EULER has a regret of Õ( √ H2SAK + H4S2A), individual STRONG-EULER has a collective regret of Õ(M √ H2SAK +MH4S2A). In addition, by a 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 1− δ, individual STRONG-EULER has a collective regret of order2
ln
� MSAK
δ
�   �
p∈[M ]
  �
(s,a)∈Zp,opt
H3
gapp,min +
�
(s,a)∈ZCp,opt
H3
gapp(s, a)
 +MH4S2A ln SA
gapmin
 .
(2)
2The originally-stated gap-dependent regret bound of STRONG-EULER ([36], Corollary 2.1) uses a slightly different notion of suboptimality gap, which takes an extra minimum over all steps. A close examination of their proof shows that STRONG-EULER 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 in both gap-dependent and gap-independent 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 (Mp)Mp=1 is said to be �-dissimilar, if for all p, q ∈ [M ], and (s, a) ∈ S ×A,
��Rp(s, a)−Rq(s, a) �� ≤ �, �Pp(· | s, a)− Pq(· | s, a)�1 ≤ �
H .
If this happens, we call (Mp)Mp=1 an �-Multi-Player Episodic Reinforcement Learning (abbrev. �-MPERL) problem instance.
If the MDPs in (Mp)Mp=1 are 0-dissimilar, then they are identical by definition, and our interaction protocol degenerates to the concurrent RL protocol [34]. Our dissimilarity notion is complementary to those of [6, 16]: they require the MDPs to be either identical, or have well-separated parameters for at least one state-action pair; in contrast, our dissimilarity notion allows the MDPs to be nonidentical and arbitrarily close.
We have the following intuitive lemma that shows the closeness of optimal value functions of different MDPs, in terms of the dissimilarity parameter �:
Lemma 2. If (Mp)Mp=1 are �-dissimilar, then for every p, q ∈ [M ], and (s, a) ∈ S × A,���Q�p(s, a)−Q�q(s, a) ��� ≤ 2H�; consequently, ���gapp(s, a)− gapq(s, a) ��� ≤ 4H�.

heading: 3 Algorithm
text: We now describe our main algorithm, MULTI-TASK-EULER (Algorithm 1). Our model-based algorithm is built upon recent works on episodic RL that provide algorithms with sharp instance-dependent guarantees in the single task setting [46, 36]. In a nutshell, for each episode k and each player p, the algorithm performs optimistic value iteration to construct high-probability upper and lower bounds for the optimal value and action value functions V �p and Q � p, 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 function 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 at 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 of episode k, for every h ∈ [H] and (s, a) ∈ Sh ×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:
np(s, a) :=
k�
l=1
1 � (slh,p, a l h,p) = (s, a) � , n(s, a) := k�
l=1
M�
p=1
1 � (slh,p, a l h,p) = (s, a) � . (3)
The individual and aggregate estimates of immediate reward R(s, a) are defined as:
R̂p(s, a) :=
�k l=1 1 � (slh,p, a l h,p) = (s, a) � rlh,p
np(s, a) , R̂(s, a) :=
�k l=1 �M p=1 1 � (slh,p, a l h,p) = (s, a) � rlh,p
n(s, a) .
(4)
Algorithm 1: MULTI-TASK-EULER Input :Failure probability δ ∈ (0, 1), dissimilarity parameter � ≥ 0. Initialize: Set Vp(⊥) = 0 for all p in [M ], where ⊥ is the only state in SH+1 ;
1 for k = 1, 2, . . . ,K do 2 for p = 1, 2, . . . ,M do
// Construct optimal value estimates for player p
3 for h = H,H − 1, . . . , 1 do 4 for (s, a) ∈ Sh ×A do 5 Compute: 6 ind-Qp(s, a) = R̂p(s, a) + (P̂pV p)(s, a) + ind-bp(s, a); 7 ind-Q
p (s, a) = R̂p(s, a) + (P̂pV p)(s, a)− ind-bp(s, a);
8 agg-Qp(s, a) = R̂(s, a) + (P̂V p)(s, a) + agg-bp(s, a); 9 agg-Q
p (s, a) = R̂(s, a) + (P̂V p)(s, a)− agg-bp(s, a);
10 Update optimal action value function upper and lower bound estimates: 11 Qp(s, a) = min � H − h+ 1, ind-Qp(s, a), agg-Qp(s, a) � ;
12 Q p (s, a) = max
� 0, ind-Q
p (s, a), agg-Q p (s, a)
� ;
13 for s ∈ Sh do 14 Define πk(p)(s) = argmaxa∈A Qp(s, a) ; 15 Update V p(s) = Qp � s,πk(p)(s) � , V p(s) = Qp � s,πk(p)(s) � .
// All players p interact with their respective environments, and update
reward and transition estimates
16 for p = 1, 2, . . . ,M do 17 Player p executes policy πk(p) on Mp and obtains trajectory (skh,p, akh,p, rkh,p)Hh=1. 18 Update individual estimates of transition probability P̂p, reward R̂p and count np(·, ·)
using the first parts of Equations (3), (4) and (5). 19 Update aggregate estimates of transition probability P̂, reward R̂ and count n(·, ·) using the
second parts of Equations (3), (4) and (5).
Similarly, for every h ∈ [H] and (s, a, s�) ∈ Sh × A × Sh+1, we also define the individual and aggregate estimates of transition probability as:
P̂p(s� | s, a) := �k l=1 1 � (slh,p, a l h,p, s l h+1,p) = (s, a, s �) �
np(s, a) ,
P̂(s� | s, a) := �k l=1 �M p=1 1 � (slh,p, a l h,p, s l h+1,p) = (s, a, s �) �
n(s, a) .
(5)
If n(s, a) = 0, we define R̂(s, a) := 0 and P̂(s� | s, a) := 1|Sh+1| ; and if np(s, a) = 0, we define R̂p(s, a) := 0 and P̂p(s� | s, a) := 1|Sh+1| . The counts and reward estimates can be maintained by MULTI-TASK-EULER efficiently in an incremental manner.
Constructing value function estimates via optimistic value iteration. For each player p, based on these model parameter estimates, MULTI-TASK-EULER performs optimistic value iteration to compute the value function estimates for states at all layers (lines 3 to 15). For the terminal layer H + 1, V �H+1(⊥) = 0 trivially, so nothing needs to be done. For earlier layers h ∈ [H], MULTI-TASK-EULER iteratively builds its value function estimates in a backward fashion. At the time of estimating values for layer h, the algorithm has already obtained optimal value estimates for layer h + 1. Based on the Bellman optimality equation (1), MULTI-TASK-EULER
estimates (Q�p(s, a))s∈Sh,a∈A using model parameter estimates and its estimates of (V � p (s))s∈Sh+1 , i.e., (V p(s))s∈Sh+1 and (V p(s))s∈Sh+1 (lines 5 to 12).
Specifically, MULTI-TASK-EULER constructs estimates of Q�p(s, a) for all s ∈ Sh, a ∈ A in two different ways. First, it uses the individual estimates of model of player p to construct ind-Q
p and
ind-Qp, upper and lower bound estimates of Q � p (lines 8 and 9); this construction is reminiscent of EULER and STRONG-EULER [46, 36], in that if we were only to use ind-Q p and ind-Qp as our optimal action value function estimate Qp and Qp, our algorithm becomes individual STRONG-EULER. The individual value function estimates are key to establishing MULTI-TASK-EULER’s 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 and agg-Qp, also upper and
lower bound estimates of Q�p (lines 6 and 7); this construction is unique to the multitask learning setting, and is our new algorithmic contribution.
To ensure that agg-Qp and ind-Qp (resp. agg-Qp and ind-Qp) are valid upper bounds (resp. lower bounds) of Q�p, MULTI-TASK-EULER adds bonus terms ind-bp(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-bp(s, a) := brw � np(s, a), 0 � + bprob � P̂p(· | s, a), np(s, a), V p, V p, 0 � +
bstr � P̂p(· | s, a), np(s, a), V p, V p, 0 � ,
agg-bp(s, a) := brw � n(s, a), � � + bprob � P̂(· | s, a), n(s, a), V p, V p, � � +
bstr � P̂(· | s, a), n(s, a), V p, V p, � � ,
where
brw (n,κ) := 1 ∧ κ+Θ �� L(n)
n
� ,
bprob
� q, n, V , V ,κ � := H ∧ 2κ+Θ   ����vars�∼q � V (s�) � L(n)
n +
����Es�∼q � (V (s�)− V (s�))2 � L(n)
n +
HL(n)
n
 ,
bstr
� q, n, V , V ,κ � := κ+Θ   ����S Es�∼q � (V (s�)− V (s�))2 � L(n) n + HSL(n) n   ,
and L(n) � ln(MSAnδ ). The three components in the bonus terms serve for different purposes:
1. The first component accounts for the uncertainty in the reward estimation: with probability 1 − O(δ), ���R̂p(s, a)−Rp(s, a) ��� ≤ brw � np(s, a), 0 � , and ���R̂(s, a)−Rp(s, a) ��� ≤
brw � n(s, a), � � .
2. The second component accounts for the uncertainty in estimating (PpV �p )(s, a): with probability 1−O(δ), ���(P̂pV �p )(s, a)− (PpV �p )(s, a) ��� ≤ bprob � P̂p(· | s, a), np(s, a), V p, V p, 0 �
and ���(P̂V �p )(s, a)− (PpV �p )(s, a) ��� ≤ bprob � P̂(· | s, a), n(s, a), V p, V p, � � .
3. The third component accounts for the lower order terms to ensure strong optimism [36]: with probability 1 − O(δ), ���(P̂p − Pp)(V p − V �p )(s, a) ��� ≤
bstr � P̂p(· | s, a), np(s, a), V p, V p, 0 � , and
���(P̂− Pp)(V p − V �p )(s, a) ��� ≤
bprob � P̂(· | s, a), n(s, a), V p, V p, � � .
Based on the above concentration inequalities and the definitions of bonus terms, it can be shown inductively that, with probability 1−O(δ), both agg-Qp and ind-Qp (resp. agg-Qp and ind-Qp) are valid upper bounds (resp. lower bounds) of Q�p.
Finally, observe that for any (s, a) ∈ Sh×A, Q�p(s, a) has range [0, H−h+1]. By taking intersections of all confidence bounds of Q�p it has obtained, MULTI-TASK-EULER constructs its final upper and lower bound estimates for Q�p(s, a), Qp(s, a) and Qp(s, a) respectively, for (s, a) ∈ 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 �p (s) and and optimal action values � Q�p(s, a) : a ∈ A � ,
MULTI-TASK-EULER also constructs upper and lower bound estimates for V �p (s), V p(s) and V p(s), respectively for s ∈ Sh (line 15).
Executing optimistic policies. At each episode k, for each player p, its optimal action-value function upper bound estimate Qp induces a greedy policy π
k(p) : s �→ argmaxa∈A Qp(s, 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 k, the algorithm also updates its aggregate model parameter estimates (lines 16 to 19) using Equations (3), (4) and (5), and continues to the next episode.

heading: 4 Performance guarantees
text: 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) ∈ S ×A : ∃p ∈ [M ], gapp(s, a) ≥ 96H� � ,
where we recall that gapp(s, a) = V � p (s)−Q�p(s, a).
Definition 3 generalizes the notion of subpar arms defined for multi-task multi-armed bandit learning [43] in two ways: first, it is with regards to state-action pairs as opposed to actions only; second, in RL, suboptimality gaps depend on optimal value function, which in turn depends on both immediate reward and subsequent long-term return.
To ease our later presentation, we also present the following lemma. Lemma 4. For any (s, a) ∈ I�, we have that: (1) for all p ∈ [M ], (s, a) /∈ Zp,opt, where we recall that Zp,opt = � (s, a) : gapp(s, a) = 0 � is the set of optimal state-action pairs with respect to p; (2)
for all p, q ∈ [M ], gapp(s, a) ≥ 12gapq(s, a).
The lemma follows directly from Lemma 2; its proof can be found in the Appendix along with proofs of the following theorems. Item 1 implies that any subpar state-action pair is suboptimal for all players. In other words, for every player p, the state-action space S ×A can be partitioned to three disjoint sets: I�, Zp,opt, (I� ∪Zp,opt)C . Item 2 implies that for any subpar (s, a), its suboptimal gaps with respect to all players are within a constant of each other.

heading: 4.1 Upper bounds
text: 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 MULTI-TASK-EULER.
Theorem 5 (Gap-independent bound). If � Mp �M p=1
are �-dissimilar, then MULTI-TASK-EULER satisfies that with probability 1− δ,
Reg(K) ≤ Õ � M � H2|IC� |K + � MH2|I�|K +MH4S2A � .
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 1− δ,
Reg(K) ≤ Õ � M √ H2SAK +MH4S2A � .
We focus on the comparison on the leading terms, i.e., the √ K terms. As M √ H2SAK � M � H2|I�|K + M � H2 ��IC�
��K, we see that an improvement in the collective regret bound comes from the contributions from subpar state-action pairs: the M � H2|I�|K term is reduced to � MH2|I�|K, a factor of Õ( � 1 M ) improvement. Moreover, if ��IC� �� � SA and M � 1, MULTI-TASK-EULER provides a regret bound of lower order than individual STRONG-EULER.
We next present a gap-dependent upper bound on its collective regret. Theorem 6 (Gap-dependent upper bound). If � Mp �M p=1
are �-dissimilar, then MULTI-TASK-EULER satisfies with probability 1− δ,
Reg(K) � ln(MSAK δ )   �
p∈[M ]
  �
(s,a)∈Zp,opt
H3
gapp,min +
�
(s,a)∈(I�∪Zp,opt)C
H3
gapp(s, a)
 +
�
(s,a)∈I�
H3
minp gapp(s, a)
 + ln( MSAK δ ) ·MH4S2A ln MSA gapmin ,
where we recall that gapp,min = min(s,a):gapp(s,a)>0 gapp(s, a), and gapmin = minp 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 of STRONG-EULER for all players p ∈ [M ], and taking a union bound over all p, individual STRONG-EULER guarantees a collective regret bound of
Reg(K) � ln(MSAK δ )   �
p∈[M ]
  �
(s,a)∈Zp,opt
H3
gapp,min +
�
(s,a)∈(I�∪Zp,opt)C
H3
gapp(s, a)
 +
�
(s,a)∈I�
�
p∈[M ]
H3
gapp(s, a)
 + ln( MSAK δ ) ·MH4S2A ln SA gapmin ,
that holds with probability 1− δ. 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-TASK-EULER comes from the contributions from the subpar state-action pairs: for each (s, a) ∈ I�, the regret bound is reduced from � p∈[M ] H3
gapp(s,a) to
H3
minp gapp(s,a) , a factor of O( 1M ) improvement. Recent work of [44] has shown that in the single-task setting, it is possible to replace �
(s,a)∈Zp,opt H3 gapp,min with a sharper problem-dependent complexity
term that depends on the multiplicity of optimal state-action pairs. We leave improving the guarantee of Theorem 6 in a similar manner as an interesting open problem.
Key to the proofs of Theorems 5 and 6 is a new bound on the surplus [36] of the value function estimates. Our new surplus bound is a minimum of two terms: one depends on the usual stateaction 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.

heading: 4.2 Lower bounds
text: To complement the above upper bounds, we now present gap-dependent and gap-independent regret lower bounds that also depends on 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 7 (Gap-independent lower bound). For any A ≥ 2, H ≥ 2, S ≥ 4H , K ≥ SA, M ∈ N, and l, lC ∈ N with l + lC = SA and l ≤ SA− 4(S +HA), there exists some � that satisfies: for any algorithm Alg, there exists an �-MPERL problem instance with S states, A actions, M players and an episode length of H such that ���I � 192H ��� ≥ l, and
E � RegAlg(K) � ≥ Ω � M √ H2lCK + √ MH2lK � .
We also present a gap-dependent lower bound. Before that, we first formally define the notion of sublinear regret algorithms: for any fixed �, we say that an algorithm Alg is a sublinear regret algorithm for the �-MPERL problem if there exists some C > 0 (that possibly depends on the state-action space, the number of players, and �) and α < 1 such that for all K and all �-MPERL environments, E � RegAlg(K) � ≤ CKα.
Theorem 8 (Gap-dependent lower bound). Fix � ≥ 0. For any S ∈ N, A ≥ 2, H ≥ 2, M ∈ N, with S ≥ 2(H − 1), let S1 = S − 2(H − 1); and let � Δs,a,p � (s,a,p)∈[S1]×[A]×[M ] be any set of values that satisfies: (1) each Δs,a,p ∈ [0, H/48], (2) for every (s, p) ∈ [S1]× [M ], there exists at least one action a ∈ [A] such that Δs,a,p = 0, and (3) for every (s, a) ∈ [S1]× [A] and p, q ∈ [M ],��Δs,a,p −Δs,a,q
�� ≤ �/4. There exists an �-MPERL problem instance with S states, A actions, M players and an episode length of H , such that S1 = [S1], |Sh| = 2 for all h ≥ 2, and gapp(s, a) = Δs,a,p, ∀(s, a, p) ∈ [S1]× [A]× [M ]; for this problem instance, any sublinear regret algorithm Alg for the �-MPERL problem must satisfy:
E � RegAlg(K) � ≥ Ω   lnK   � p∈[M ]
�
(s,a)∈IC (�/192H) :
gapp(s,a)>0
H2
gapp(s, a) +
�
(s,a)∈I(�/192H)
H2
minp gapp(s, a)     .
Comparing the lower bounds with MULTI-TASK-EULER’s regret upper bounds in Theorems 5 and 6, we see that the upper and lower bounds nearly match for any constant H . When H is large, a key difference between the upper and lower bounds is that the former are in terms of I�, while the latter are in terms of IΘ( �H ). We conjecture that our upper bounds can be improved by replacing I� with IΘ( �H )—our analysis uses a clipping trick similar to [36], which may be the reason for a suboptimal dependence on H . We leave closing this gap as an open question.

heading: 5 Related Work
text: 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 √ H2SAK regret bounds for general stationary MDPs. Furthermore, the EULER algorithm [46] achieves adaptive problem-dependent regret guarantees when the total reward within an episode is small or when the environmental norm of the MDP is small. [36] refine EULER, proposing STRONG-EULER that provides more fine-grained gap-dependent O(logK) 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 a regret bound that improves over that of [36], in that it replaces the dependence on the number of optimal state-action pairs with the number of non-unique state-action pairs.
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 e.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, an agent faces a 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 well-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 RL 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 RL 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.e., 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 it is assumed that the optimal value functions of all tasks are from a 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 a 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 a 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.

heading: 6 Conclusion and Future Directions
text: In this paper, we generalize the multi-task bandit learning framework in [43] and formulate a multitask 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 instance-dependent 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 IΘ(�/H) in the lower bound when H is large; second, the gap-dependent upper bound has O(H3) dependence, whereas the gap-dependent lower bound only has Ω(H2) 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 �; an interesting avenue is to apply model selection strategies in bandits and RL to achieve adaptivity to unknown �. Another interesting future direction is to consider more general parameter transfer for online RL, for example, in the context of function approximation.

heading: 7 Acknowledgements
text: 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.

Review summaries:
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.

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.

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.  

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.