Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks
Authors: Ziping Xu
Zifan Xu
Runxuan Jiang
Peter Stone
Ambuj Tewari
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning; Multitask Learning; Exploration
Primary area: reinforcement learning
TL;DR: We rigorously show that algorithm running myopic exploration with policy-sharing across tasks can be sample-efficient when the task set is diverse.

Abstract: Multitask Reinforcement Learning (MTRL) approaches have gained increasing attention for its wide applications in many important Reinforcement Learning (RL) tasks. However, while recent advancements in MTRL theory have focused on the improved statistical efficiency by assuming a shared structure across tasks, exploration--a crucial aspect of RL--has been largely overlooked. This paper addresses this gap by showing that when an agent is trained on a sufficiently diverse set of tasks, a generic  policy-sharing algorithm with myopic exploration design like $\epsilon$-greedy that are inefficient in general can be sample-efficient for MTRL. To the best of our knowledge, this is the first theoretical demonstration of the "exploration benefits" of MTRL. It may also shed light on the enigmatic success of the wide applications of myopic exploration in practice. To validate the role of diversity, we conduct experiments on synthetic robotic control environments, where the diverse task set aligns with the task selection by automatic curriculum learning, which is empirically shown to improve sample-efficiency.

Published as a conference paper at ICLR 2024
SAMPLE EFFICIENT MYOPIC EXPLORATION THROUGH MULTITASK REINFORCEMENT LEARNING WITH DI-
VERSE TASKS
Ziping Xu Zifan Xu², Runxuan Jiang", Peter Stone Ambuj Tewari l Harvard University, The University of Texas Austin, University of Michigan, 'Sony Al "This work was done while Z.X. was a Ph.D. student at the University of Michigan.
ABSTRACT
Multitask Reinforcement Learning (MTRL) approaches have gained increasing attention for its wide applications in many important Reinforcement Learning (RL) tasks. However, while recent advancements in MTRL theory have focused on the improved statistical efficiency by assuming shared structure across tasks, exploration-a crucial aspect of RI.haas been largely overlooked. This paper ad- dresses this gap by showing that when an agent trained on a sufficiently diverse set of tasks, a generic policy-sharing algorithm with myopic exploration design like c-greedy that are inefficient in general can be sample-efficient for MTRL. To the best of our knowledge, this is the first theoretical demonstration of the "exploration benefits" of MTRL. It may also shed light on the enigmatic success of the wide applications of myopic exploration in practice. To validate the role of diversity, we conduct experiments on synthetic robotic control environments, where the diverse task set aligns with the task selection by automatic curriculum learning, which is empirically shown to improve sample-efficiency.
INTRODUCTION
Learning often involves solving multitask problems. For instance, robotic control agents are trained to simultaneously solve multiple goals in multi-goal environments (Andreas et al..
Reinforcement
2017, Andrychowicz et al., 2017). In mobile health applications. RL is employed to personalize
sequences treatments, treating each patient as distinet task (Yom-Tov Tov et al. 2017 Forman et al.
2019 Liao et al. 2020 Ghosh et al. (203). Many algorithms (Andreas et al., 2017] Andrychowicz
ct al. 2017 Hessel et al. 2019] Yang et al. 2020) have been designed to jointly learn from multiple
tasks. These show significant improvement over those that learn each task individually. To provide explanations for such improvement, recent advancements in Multitask Reinforcement Learning (MTRL) theory study the improved statistical efficiency in estimating unknown parameters by assuming a shared structure across tasks (Brunskill & Li, (2013) Calandriello et al. 2014: [eehara
al. 2021 Xu et al. 2021 Zhang & Wang [021 Lu et al.) 2021 Agarwal al. 2022] Cheng et al.
2022
Yang et al.) 2022a). Similar setups originate from Multitask Supervised Learning, where has
been shown that learning from multiple tasks reduces the generalization error by a factor of 1/ N compared single-task learning with N being the total number of tasks (Maurer et al. 2016 Du
ct al. 2020). Nevertheless, these studies overlook an essential aspect of RL, namely exploration.
To understand how learning from multiple tasks, as opposed single-task learning, could potentially benefit exploration design, we consider a generic MTRL scenario, where an algorithm interacts with a task set M in rounds T. In each round, the algorithm chooses an exploratory policy æ that used to collect one episode worth of data in task M E M of its own choice. A sample-efficient algorithm should output a near-optimal policy for each task in a polynomial number of rounds.
Exploration design plays an important role in achieving sample-efficient learning. Previous sample- efficient algorithms for single-task learning (M = 1) heavily rely on strategic design on the exploratory policies, such as Optimism in Face of Uncertainty (OFU) (Auer et al.] 2008 Bartlett
Tewari 2009 Dann et al. 2017) and Posterior Sampling (Russo & Van Roy| 2004)) Osband &
Van Roy| 2017). Strategic design criticized for either being restricted to environments with strong
structural assumptions, or involving intractable computation oracle, such as non-convex optimization
[Tiang 2018 Jin al. 2021a). For instance, GOLF (Jin al. 2021a), model-free general function

---

Published as a conference paper at ICLR 2024
approximation online learning algorithm, involves finding the optimal Q-value function f in function class F. It requires the following two intractable computation oracles in T
F U E FF; : has low empirical Bellman error) and f( arg max (881, ()).
(I)
JEF
In contrast, myopic exploration design like c-greedy that injects random noise to a current greedy policy is easy implement and performs well in wide range of applications (Mnih et al. [015]
Kalashnikov et al. 2018), while it is shown to have exponential sample complexity in the worst case for single-task learning (Osband et al. 2019). Throughout the paper, we ask the main question:
Can algorithms with myopic exploration design be sample-eficciet for MTRL?
In this paper, we address the question by showing that simple algorithm that explores one task with e-greedy policies from other tasks can be sumple-efficien if the task set M adequately diverse. Our results may shed some light on the longstanding mystery that e-greedy is successful in practice, while being shown sample-inefficien in theory. We argue that in an MTRL setting, e-greedy policies may no longer behave myopically, as they explore myopically around the optimal policies from other tasks. When the task set is adequately diverse, this exploration may provide sufficient coverage. is worth-noting that this may partially explain the success of curriculum learning in RL (Narvekar et al., 2020), that is the optimal policy of one task may easily produce a good exploration for the next task, thus reducing the complexity of exploration. This connection will be formally discussed later.
To summarize our contributions, this work provides a general framework that converts the task of strategic exploration design into the task of constructing diverse task set in an MTRL setting, where myopic exploration like e-greedy can also be samplc-efficient. We discuss a sufficient diversity condition under general value function approximation setting (Jin et al. 2021a; Dann et al.) 2022). We show that the condition guarantees polynomial sample-complexity bound by running the aforementioned algorithm with myopic exploration design. We further discuss how to satisfy the diversity condition in different case studies, including tabular cases, linear cases and linear quadratic regulator cases. In the end, we validate our theory with experiments on synthetic robotic control environments, where we observe that a diverse task set is similar to the task selection of the sfatc-of-the- automatic curriculum learning algorithm, which has been empirically shown to improve sample efficiency.
PROBLEM SETUP
The following are notations that will be used throughout the paper.
Notation. For positive integer H, we denote [H] == (l..... H.. For a discrete set A, we denote AA by the set of distributions over A. We use O and 52 denote the asymptotic upper and lower bound notations and use Ô and Ω to hide the logarithmic dependence. Let {1:heij be the standard basis that spans Rd. We let N₂ (p) denote the foe covering number function class F at scale p. For class F, we denote the N N-times Cartesian product of F by (F) OF
2.1 PROPOSED MULTITASK LEARNING SCENARIO
Throughout the paper, we consider each task as episodic MDP denoted by M (S,A, A, H. PM, RM,), where is the state space, A is the action space. H E N represents the horizon length in each episode, PM (Pr.M) [ is the collection of transition kernels, and RM = (Ra, ) is the collection of immediate reward functions. Each PA.M S x A + ASS) and each RA S x A + [0, 1]. Note that we consider a scenario in which all the tasks share the same state space, action space, and horizon length.
An agent interacts with an MDP M in the following way: starting with fixed initial state $1, at each step h [H). the agent decides an action on and the environment samples the next state 8h+1 ~ PR.M (- 8h, 0x) and next reward ry = RA, (8h, a.). An episode is sequence of states, actions, and rewards (51, 41, Tl........ SH, an, HH, 5H+)). ). In general, we assume that the sum of rn is upper bounded by for any action sequence almost surely. The goal of agent is to maximize the cumulative reward EH k= T'k by optimizing their actions.
2

---

Published as a conference paper at ICLR 2024
The agent chooses actions based Markovian policies denoted by (TA)ee( and each TT is mapping S + AA. where A is the set of all distributions over A. Let II denote the space of all such policies. For finite action space, we let Tn (a s) denote the probability of selecting action a given state 8 at the step h. In case of the infinite action space, we slightly abuse the notation by letting (- 8) denote the density function.
Proposed multitask learning scenario and objective. We consider the following multitask RL learning scenario. An algorithm interacts with a set of tasks M sequentially for T rounds. At the each round 6, the algorithm chooses an exploratory policy, which is used to collect data for one episode in task M .M of its own choice. At the end of T rounds, the algorithm outputs a set of policies {TM J. The goal of an algorithm is to learn a near-optimal policy TM for each task M E M. The sample complexity of an algorithm is defined as follows.
Definition 1 (MTRL Sample Complexity). An algorithm L is said to have cemple-complextte of CMM R. X IR + N for a task set M if for any 3 > 0, E (0,1), it outputs a 3-optimal policy ι for each MDP M E . with probability at least 1 - 8, by interacting with the task set for Cf (3, rounds. We omit the notations for L and M when they are clear froa the context to ease presentation.
A sample-efficient algorithm should have sample-complexity polynomial in the parameters of interests. For the tabular case, where the state space and action space are finite, C(3, 5) should be polynomial in |S), [A], .M]. H, and 1/3 for a sample-efficient learning. Current state-of-the art algorithm (Zhang et al. 202T) on a single-task tabular MDP achieves sample-complexity of ((S)|AA// This bound translates to a MTRL sample-complexity bound of ([|M]|||| by running their algorithm individually for each M E M. However, their exploration design closely follows the principle of Optimism in Face of Uncertainty, which is normally criticized for over-exploring.
2.2 VALUE FUNCTION APPROXIMATION
We consider the setting where value functions are approximated by general function classes. Denote the value function of an MDP M with respect a policy by
(T, a) E. [rn + V (S6+1) 8h = 8, az Vi = E.M [QT.M (8h, ax) 88 = =].
a]
where by Ex we take expectation over the randomness of trajectories sampled by policy on MDP
M and we let (M) = 0 for all s E S and ı E II. We denote the optimal policy for MDP
M by TM The corresponding value functions are denoted by VILM and Qi.M which shown to
satisfy Bellman Equation T/. Qh+1,M Qi,.. where for any S x A + [0, 1]. (TM g) (s,a) Eira- + max ($h+1, .a) Sh s, ar = a].
The agent has access to a collection of function classes JF (Fr S x A + [0, Hee We assume that different tasks share the same set of function class. For each f E F. we denote by fn E Fr. the h-th component of the function f. We let . = {T/, Jaee be the greedy policy with T/ (s) = arg m A fn (s, a). When it clear from the context, we slightly abuse the notation and let f E (F)SIM) be joint function for all the tasks. We further let sas denote the function for the task M and f0.M denote its h-th component.
Define Bellman error operator EM such that EM f -T, fu+1 for any E F. The goal of the learning algorithm is to approximate Q7,M through the function class Fr by minimizing the empirical Bellman error for each step and task M.
To provide theoretical guarantee on this practice, make the following realizability and completeness assumptions. The two assumptions and their variants are commonly used in the literature (Dann et al. 2017 Jin et al. 2021a).
Assumption 1 (Realizability and Completeness). For any MDP M considered in this paper, we assume is realizable and complete under the Bellman operator such that Q as E For all h E [H] and for every h [H]. fh41 E Fr+1 there is fr. E Fr, such that fr. = TM futi.
"This bound under the regime with 1/B > |8|
3

---

Published as a conference paper at ICLR 2024
2.3 MYOPIC EXPLORATION DESIGN
As opposed to carefully designed exploration, myopic exploration injects random noise to the current greedy policy. For given greedy policy т, we use ехрl(π) to denote the myopic exploration policy based Depending on the action space, the function expl can take different forms. The most common choice for finite action spaces is c-greedy, which mixes the greedy policy with a random action: cxpl(x;;(a s) (1 - (A) (a s)+ As it is main study of exploration strategies, we let expl be e-greedy function if not explicitly specified. For continuous action space, we consider exploration with Gaussian noise: expl(Tx)(c s) s)= (1 )T (a + exp(-a² (opp(=a/20))111 k Gaussian noise is useful for Linear Quadratic Regulator (LQR) setting (discussed in Appendix F)
MULTITASK RL ALGORITHM WITH POLICY-SHARING
In this section, we introduce a generic algorithm (Algorithm D for the proposed multitask RI. scenario without any strategic exploration, whose theoretical properties will be studied throughout the paper. In a typical single-task learning, a myopically exploring agent samples trajectories by running its current greedy policy estimated from the historical data equipped with naive explorations like c-greedy.
In light of the exploration benefits of MTRL, we study A a counterpart of the single-task learning scenario in the MTRL setting, Algorithm[[ maaintains dataset for each MDP separately and different tasks interact in the following way: in each round, [ exxploress every MDP with an exploratory policy that the mixture (defined in Definition 2 of greedy policies of all the MDPs in the task set (Line 8). One way to interpret Al Algorithm| is that we share knowledge across tasks by policy sharing instead of parameter sharing or feature extractor sharing in the previous literature.
explores
Definition 2 (Mixture Policy). For set of policies { we denote Mixture (T; (fTT) ())) by the mixture of N policies, such that before the start of an episode, samples I ~ Unif then runs policy T1 for the rest of the episode.
The greedy policy is obtained from an offline learning oracle Q (Line 4) that maps dataset D = {(s, a; Ti, ) to a function f E F, such that Q(D) is an approximate solution to the following minimization problem arg fe Em (fn, 0:) - ri max. fhit1 a'))) In practice, one can run fitted Q-iteration for an approximate solution.
Connection to Hindsight Experience Replay (HER) and multi-goal RL. We provide some justifications for the choice of the mixture policy. HER a common practice (Andrychowicz et al. 2017) in the multi-gow RL setting (Andrychowicz et al. 2017 Chane 2022), where the reward distribution is function of goal-parameters. HER relabels the rewards in trajectories in the experience buffer such that they were as if sampled for a different task. Notably, this exploration strategy is akin to randomly selecting task and collecting a trajectory on using its own epsilon-greedy policy, followed by relabeling rewards to simulate trajectory on, which is equivalent to Algorithm|] T Yang et al. (2022b); Zhumabekov et al. (2023) also designed an algorithm with ensemble policies, which is shown to improve generalizability. It is worth noting that the ensemble implementation of Algorithm|]] [ and that Zhumabekovv et al. (2023) differs. In Algorithm 1, policies mixed trajectory-wist
et al.] 2021 Liu et al.
with one policy randomly selected for the entire episode. In contrast, Zhumabekov et al. (2023) mixes policies on a step-wise basis for a continuous action space, selecting actions as a weighted average of actions chosen by different policies. This distinction is vital in showing the rigorous theoretical guarantee outlined in this paper.
Connection to curriculum learning. Curriculum learning is the approach that learns tasks in a specific order to improve the multitask learning performance (Bengio et al., 2009). Although Algorithm [ does not explicitly implement curriculum learning by assigning preferences to tasks, improvement could be achieved through adaptive task selection that may reflect the benefits of curriculum learning. Intuitively. any curricula that selects tasks through an order of M,,..., .M is implicitly included in Algorithm [ as it explores all the MDPs in each round with the mixture of all epsilon-greed policies. This means that the cample-copllxxtty of Algorithm provides an upper bound on the sample complexity of underlying optimal task selection. A formal discussion is deferred to Appendix B
Note that we consider more general setup, where the exploration prohability can depend on h.
4

---

Published as a conference paper at ICLR 2024
Algorithm I Generic Algorithm for MTRL with Policy-Sharing
1: Input: function class F = Fi X .... Fu+1, task set M, exploration function expl
2: Initialize D0.M < for all E .M
3: for round 1, ..... [T/ M do
4: Offline learning oracle outputs fr,M ((D)-1,M) for each M
Offline learning
5: Set myopic exploration policy &t.M + expl(T for each M
6: Set म. + Mixture((@r,au MEM)
Share policies
7:
for M E .M do
Sample one episode Tr.M on MDP M with policy # 9: Add ar,ar to the dataset: Dr,Mr +- 1,- J {Te,M)
8:
Collect new trajectory
10: end for
11:
end for
12:
Return AM = Mixture((fi) (M. for each M
States
M₁
N States
N tasks
Single e-greedy visits goal state with prob. r
My
Figure 1: A diverse grid- task it represents single-task and multitask learning scenario, respectively. The triangles represent the starting state and the stars represent the goal states, where an agent receives a positive reward. The agent can choose to move forward or backward.
long hallway with N + states, From the left the right,
GENERIC SAMPLE COMPLEXITY GUARANTEE
In this section, rigorously define the diversity condition and provide a sumple-complexin upper bound for Algorithm]] ! exploration in multitask setting.
We start with introducing an intuitive example on how diversity encourages
Motivating example. Figure introoduces a motivating example of grid-world environment on a long hallway with N + 1 states. Since this is deterministic tabular environment, whenever task collects an episode that visits its goal state, running an offline policy optimization algorithm with pessimism will output its optimal policy.
Left penal of Figure T is a single-task learning, where the goal state is N steps away from the initial state, making exponentially hard visit the goal state with e-greedy exploration. Figure on the right demonstrates a multitask learning scenario with N tasks, whose goal states "diversely" distribute along the hallway. A main message of this paper is the advantage of exploring one task by running the e-greedy policies of other tasks. To see this, consider any current greedy policies (π1, T2.... TN) n optimal for My. Since π;-1 optimal, by running an e-greedy of ;;- on MDP M,, we have a probability of [ improve its policy to optimal the next round. Such improvement can only
Let be the first non-optimal policy, i.e. all ,
Ex)e; to visit the goal
of M,, allowing happen for N times and all policies will be optimal within polynomial (in N) number of rounds if we choose E₁ 1/(h + 1). Hence, myopic exploration with diverse task leads to sample-efficiens learning. The rest of the section can be seen as generalizing this idea to function approximation.
4.1 MULTITASK MYOPIC EXPLORATION GAP
Dann et al. 2022) proposed an assumption named Myopic Exploration Gap (MEG) that allows efficient myopic exploration for single MDP under strong assumptions the reward function, or on the mixing time. We extend this definition to the multitask learning setting. For the conciseness of the notation, let expl(f) denote the following mixture policy Mixture((expl((<1 MEM)

---

Published as a conference paper at ICLR 2024
for a joint function (FF)&IM) Intuitivelyy large myopic exploration gap implies that within all the policies that can be learned by the current exploratory policy, there exists one that can make significant improvement on the current greedy policy.
Definition& 3 (Multitask Myopic Exploration Gap (Multitask MEG)). For any M, a function class F. a joint function f E (F)@|M), we say that f has ((S.M, Fymyopic exploration gap, where a aff,M, F) is the value to the following maximization problem:
max sup (Vi.s - V.N.). s.t. for all f' E F and E [H] MEM
feJ,021 VC
II (s)))))))3 s cE
[(e f') ax))]
B. [[E) (') an))² S & ((E) (s) an))²
Let MU,M,FF,, F), be the corresponding M E M and e that altains the maximization.
Design of myopic exploration gap. To illustrate the spirit of this definition, we specialize to the tabular case, where conditions in Definition Jeaitioonnnnnnnn be replaced by the concentrability (Jin et al. 20216)
condition: for all 8, a. h E S x A x [H], we require
5 (8, a) S M
expli) (s, a) and M (8, a) S CPh,M (s.
explis)
(2)
where (s, (s. a) is the occupancy measure, i.e. the probability of visiting (s, a) at the step h by running policy π on MDP M. The design of myopic exploration gap connects deeply to the theory of offline Reinforcement Learning. For a specific MDP M, Equation (2) defines set of policies with concentrability assumption (Xie et al. 2021) that can be accurately evaluated through the offline data collected by the current behavior policy. As an extension to the Single-task MEG in Dann et al. (2022), Multitask MEG considers the maximum myopic exploration gap over a set of MDPs and the behavior policy is a mixture of all the greedy policies. Definition reduces to the Single-task MEG when the task set M is singleton.
4.2 SAMPLE COMPLEXITY GUARANTEE
We propose Diversity in Definition 5 which relies on having lower bounded Multitask MEG for any suboptimal policy. We then present Theorem that shows an upper bound for sample complexity of AlgorithmD | by assuming diversity.
Definition 4 (Multitask Suboptimality). For a mullitask RL problem with MDP set M and value function class F. Let FB C (F)SlM be the 3-suboptimal class, such that for any f E Fg, there exists fM and JIM is B-suboptimal for MDP M. i.e. VI S max Vi,as B.
Definition 5 (Diverse Tasks). For some function ā [0,1] + R. and ē : [0, we say that 2 a(3)
tasks set is (ā. diveirss if any f E Fg has multitask myopic exploration gap and cff, M,, S 8(B) any constant 3 > O.
To simplify presentation, we state the result here assuming parametric growth of the Bellman cluder dimension and covering number, that is dgE (F, < d log(1/p) and (o S
denver log(1/p), where dimpe(F, II p) is the Bellman- (p). A formal definition of Bellman-Fluude dimension is deferred to Appendix This parametric growth rate holds for most of the regular classes including tabular and linear Russo & Van Roy, 2013). Similar assumptions are made in Chen et al. (022a)).
dimension of class F and N2(p)
NA. F
Theorem (Upper Bound for Sample Complexity). Consider a multitask RL problem with MDP set M and value function class F such that M is (ā, dideiere. Then Algorithm 7 with e-greedy exploration function has sample-complexiry
C(3,8) 3 8(1 (IMPIP df. BE yoner In ((3) d
2²(3) In (1/6))
4.3 COMPARING SINGLE-TASK AND MULTITASK MEG
The sample complexity bound in Treduces to the single-task sample complexity in Dann et al.) (202)) when M is singleton. To showcase the potential benefits of multitask learning, we provide

---

Published as a conference paper at ICLR 2024
comprehensive comparison between Single-task and Multitask MEG. We focus discussion VI on JF because F) I ((max, VL. V[.M V.MM (. < (f,,M and cff, F) only impacts sample complexity bound through a logarithmic term.
We first show that Multitask MEG is lower bounded by Single-task MEG up to a factor of 1/ /IM Proposition 1. Let M be any set of MDPs and F be any function class. We have that a(f.M, 2 (M,, fo all f E (F)S1M) and M E M.
Proposition iimmediately implies that whenever all tasks in task set can be learned with myopic exploration individually (see examples in Dann et al. (2022)), they can also be learned with myopic exploration through MTRL. with Algorithm with an extra factor of [M|? which still polynomial in all the related parameters.
We further argue that Single-task MEG can easily be exponentially small in H, in which case, myopic exploration fails.
Proposition 2. Let M be a tabular sparse-reward MDP, i.e, RA.M (s, a) = 0 at all (s, a, h) except for a goal tuple (s,, aq: h2) and R ($r: 0.) = 1. Recall 17, (s, a) = E =ea=a= Then
af,, (M), S max(uf, (s,, -.) ! (st, (:) Pha
expl((r)) (st, at)/ (5t, ac) S / expl((rt az).
Un,
# Sparse-reward MDP is widely studied in goal-conditioned RL, where the agent receives non-zero
reward only when it reaches goal-state (Andrychowicz et al., 2017: Chane-Sane et al. 2021). Proposition implies that a single-task MEG can easily be exponentially small in H as long as one can find a policy π such that its e-greedy version, expl(T), visits the goal tuple (st, a, h2)
with probability that is exponentially small in H. This is true when the environment requires the agent to execute a fixed sequence of actions to reach the goal tuple as it is the case in Figure [ Indeed, in the environment described in the left panel of Figure [ policy that always moves left
S V | (c./2) S -H/2, This is also consistent with our previous discussion that e-greedy requires !2(2 number of episodes to learn the optimal policy in the worst case. As we will show later in Section 5.1 Multitask MEG for the tabular case can be lowered bounded by 22( [T/(AAI|M|FT)) H)) for adequately diverse task set M, leading to an exponential separation between Single-task and Multitask MEG.
will have (f,, F) S Ph: (exp((x()(s
5 LOWER BOUNDING MYOPIC EXPLORATION GAP
Following the generic result in Theorem the key to the problem is to lower bound myopic exploration gap a()). this section, we lower bound (3) for the linear MDP case. We defer an improved analysis for the tabular case and the Linear Quadratic Regulator cases to Appendix Ft
Linear MDPs have been an important case study for the theory of RL (Wang et al. 2019 Jin et al.. 2020b; Chen al.) (2022b). It is more general case than tabular MDP and has strong implication for Deep RL, In order to employ e-greedy, we consider finite action space, while the state space can be infinite.
Definition 6 (Linear MDP Jin et al. (2020b).. An MDP is called linear MDP if its transition probability and reward function admit the following form. Pa(s' s, s,a) = (0n(s, a), un(s))) for some known function 6b : S x A + (Rr = and unknown function Ph S + (R+)d, (s. (6n(s, a),))) for unknown parameters 0 Without loss of generality, we assume [ (s, a)ll <
for all s, a, h E S x A x H. and max (ll [ 110.111 <
for all s, h E S x [H].
An important property of Linear MDPs that the value function also takes the linear form and the linear function class defined below satisfies Assumption] [
Proposition (Proposition 2.3 (Jin et al. (020b)). For linear MDPs, we have for any policy n. Th, (8, a) (cn. (s, a), W WT,M): where W On.M + V V (os))p((ss"ddd E Rd. Therefore, we only need to consider Fr = {(,, a) + (s, a), w E Rdd ||lll & 2/d).
Now we are ready to define diverse set of MDPs for the linear MDP case.
Note that we consider non-negative measure jAb-
7

---

Published as a conference paper at ICLR 2024
Definition 7 (Diverse MDPs for linear MDP case). We say M is a diverse set of MDPs for the linear MDP case, they share the same feature extractor on and the same measure Ph (leading to the same transition probabilities) and for any h E [H]. there exists subset {Ma, h hield] C. M, such that the reward parameter Mn.M., 1; and all the other Ow, 0 with ht' # h, where 1, is the onehot vector with a positive entry at the dimension i.
We need the assumption that the minimum eigenvalue of the covariance matrix is strictly lower bounded away from 0. The feature coverage assumption is commonly use in the literature that studies Linear MDPs (Agarwal et al. 2022). Suppose Assumption 2 hold, we have Theorem 2 which lower bounds the multitask myopic exploration gap. Combined with Theorem T we have comple-complxxty bound of Ó(M (ILMMHSAAAAAA (AA1 with [M] 2 d.
Assumption 2 (Feature coverage), For any v E g and [v] > 0 for all i E [d], there exists a
policy πT such that E=IVVT (Sh; an)) 2 for some constant bi 0.
Theorem 2. Consider M to be a diverse set as in Definition 7 Suppose Assumption 2 holds
and < / then we have for any f E FB, olf,F, MM) = 2(( /Bb) by setting
GA = 11/hh+ Proof of Theorem criticaall relies on iteratively showing the following lemma, which can be interpreted showing that the feature covariance matrix induced by the optimal policies is full rank.
Lemma 1. Fix a step h and fix a 3 /1. Let {Ti)==1 be d policies such that n, is a B- Then we have
optimal policy for Ma, as in Definition 7
Let # = (exture((exp(mm))]))
Amin
2 en [1k=] (1 -w))
5.1 DISCUSSIONS ON THE TABULAR CASE
Diverse tasks in Definition 7 when specialized to the tabular case, corresponds to S x H sparse- reward MDPs. Interestingly, similar constructions are used in reward-free exploration (Jin et al.) 2020a), which shows that by calling online-learinng oracle individually for all the sparse reward MDPs, one can generate a dataset that outputs a near-optimal policy for any given reward function. We want to point out the intrinsic connection between the two settings: our algorithm, instead of generating an offline dataset all at once, generates an offline dataset at each step la that is sufficient to learn near-optimal policy for MDPs that corresponds to the step + 1.
Relaxing coverage assumption. Though feature coverage Assumption (A (Assumption 2 is handy for our proof as guarantees that any 6-optimal policy (with 3 < b1/2) has probability least / to visit their goal state, this assumption may not be reasonable for the tabular MDP case. Intuitively, without this assumption, a 3-optimal policy can be an arbitrary policy and we can have at most such policies in total leading to cumulative error of S3. A naive solution is to request a S S-H accuracy at the first step, which leads to exponential cumple-copplexity In Appendix G we show that an improved analysis can be done for the tabular MDP without having to make the coverage assumption. However, an extra price of SH has to be paid.
6 IMPLICATIONS OF DIVERSITY IN DEEP RL
Though this is paper focusing on the theoretical justification, add some preliminary discussion on what diversity means in Deep RL. Thus far. we have provided concrete example for diverse task set in tabular and linear MDPs with lower bounded Multitask MEG. is often the case that in Deep RL, a pretrained feature extractor is used to generate embeddings for Q-value function and then linear mapping is applied to generate the final output (Bhateja al. 2023 Hejna III Sadigh 2023). This manner is similar to the setup in linear MDPs. We have shown that to achieve diversity for linear MDPs, one important property is to have a full rank covariance matrix of the embeddings at each step h if the optimal policy is executed (Lemma []. In this section, we conduct simple simulation studies on BipedalWalke Walker (Portelas et al. 2020), a robotic control environment, to verify that whether a more spread spectrum of the covariance matrix of the embeddings would lead to better sample efficiency.
We found in the experiments that the subset of tasks that leads to more spread spectrum is similar to the task selection of automatic curriculum learning, which has been empirically shown learn more sample efficiently. Due to the page limit we provide a high-level summary of the simulation study and the readers can find full details in Appendix []]
Experiment setup. The learning agent is embodied into a bipedal walker whose motors are controlled by continuous actions of torques. The objective of the agent is move forward as far as possible,
8

---

Published as a conference paper at ICLR 2024
while crossing stumps with varying heights at regular intervals. An environment or task, denoted as Mp.g. is controlled by a parameter vector (p. 9). where p and q denote the heights of the stumps and the spacings between the stumps, respectively. Intuitively, challenging environments have higher and denser stumps. The agent is trained by Proximal Policy Optimization (PPO) (Schulman et al. 2017) with standard actor-critic framework (Konda & Tsissikii that regularizes entropy. Detailed training setup can be found in Appendix
1999) and with Boltzmann exploration
Proper level of heights leads to more spread spectrum. We evaluate the extracted feature the end of the training generated by near-optimal policies on 100 tasks with different parameter vectors (p. 9). We then compute the covariance matrix of the features for each task, whose spectrum are shown in Figure (a). We observe that the eigenvalues can be 10 times higher for environments with an appropriate height (1.0-2.3), compared to extremely high and low heights, while they are roughly the same at different levels of spacings. This indicates that choosing an appropriate height is the key to properly scheduling tasks.
Coincidence with automatic curriculum learning. In fact, the task selection is similar to the tasks selected by the state-of-the-art Automatic Curriculum Learning (ACL). We investigate the curricula generated by ALP-GM (Portelas et al. 2020), well-established curriculum learning algorithm, for training an agent in the Bipedal environment for 20 million timesteps. Figure (b) gives the density plots of the ACL task sampler during the training process, which shows significant preference over heights in the middle range, with little preference over spacing. Since ACL has been shown to significantly improve the learning performance in BipedalWalke this is strong evidence that the diversity notation discussed in this paper truly leads to a better sample complexity even when Deep RL is employed.
Eespert Log Scaket Eyeraahes 2rvert He
IN
You 100.00
You LSC-000
Figure 2: (a) Boxplot of the log-scaled eigenvalues of sample covariance matrices of the trained embeddings generated by the near optimal policies for different environments. (b) Task preference of automatically generated curriculum 5M and 10M training steps respectively. The red regions are the regions where a task has a higher probability to be sampled.
7 DISCUSSIONS
In this paper, we propose new perspective to understand the sample efficiency of myopic exploration design through diverse multitask learning. We show that by learning a diverse set of tasks, a multitask RL algorithm with myopic exploration design can be sample-efficien This paper is promising first step towards understanding the exploration benefits of MTRL.
Towards diversity for general function classes. Despite the rich discussion on explicit form of diversity set for tabular and linear MDP cases, how to achieve diversity for any general function class is an open problem. Recalling our proof for the Linear MDP case, a sufficient condition is to include a set of MDPs for each step h, such that the state distribution generated by their optimal policies satisfy the concentrability assumptions. In other words, any MDP with positive reward only the step h + can be offline- for general function classes poses the question on the number of tasks it takes to have sufficient coverage at the each step. We give a more detailed discussion of this topic in Appendix
through the dataset collected by these optimal policies. The diversity
Improving sample-complexity bound. Our sample complexity bound instance, Theorem [ specialized to the tabular case has an upper sample complexity bound of |M 1 A² / and the current optimal bound is JM| SA///// 3 if tasks are learned independently. We conjecture that this gap may originate from two factors. First, the nature of the myopic exploration makes it less efficient because the exploration are conducted in layered manner. Second, our algorithm collects trajectories for every MDP with the mixture of all the policy in each round, which may be improved if a curriculum is known beforehand.
be sub-optimal. For

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENT
Prof. Tewari acknowledges the support of NSF via grant IIS-2007055. Prof. Stone runs the Learning Agents Research Group (LARG) UT Austin. LARG research is supported in part by NSF (FAIN- 2019844, NRT-2125558), ONR 1000014-1-22460 ARO (220),621), Bosch, Lockheed Martin, and UT Austin's 's Good Systems grand challenge. Prof. Stone also serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas Austin in accordance with its policy on objectivity in research.
Part of this work is completed while Dr. Ziping Xu a postdoe at Harvard University. He is supported by Prof. Susan A. Murphy through NIH/NIDA P50DA054039, NIH/NIBIB, OD P41EB028242 and NIHNIDCRR UH3DE028723.
REFERENCES
Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning. arXiv preprint arXiv:2205.14571, 2022.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International Conference Machine Learning, pp. 166-175. PMLR, 2017.
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 2008.
Peter Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference, pp. 35 42. AUAI Press, 2009.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Currieulum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009.
Chethan Bhateja, Derek Guo, Dibya Ghosh, Anikait Singh, Manan Tomar, Quan Vuong, Yevgen Chebotar, Sergey Levine, and Aviral Kumar. Robotic offline rl from internet videos via value- function pre-training. arXiv preprint arXiv:2309. 13041, 2023.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. arXiv preprint 1309, 6821, 2013.
Daniele Calandriello, Alessandro Lazaric, and Marcello Restelli. Sparse multi-task reinforcement learning. Advances in neural information processing systems, 27, 2014.
Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International Conference on Machine Learning, pp. 1430-1440. PMLR, 2021.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free free exploration in non-lineat rl. arXiv preprint 107700 2022a.
Liyu Chen, Rahul Jain, and Haipeng Luo. Improved no-regret algorithms for stochastic shortest path with linear mdp. International Conference on Machine Learning, pp. 3204-3245. PMLR, 2022b.
Yuan Cheng, Songtao Feng, Jing Yang, Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning. arXiv preprint arXiv:2206.0594 2022.
Will Dabney, Georg Ostrovski, and André Barreto. eexteedll (epsilon) -greedy explo- ration. arXiv preprint 200.0/00000/88. 2020.
10

---

Published as a conference paper at ICLR 2024
Chris Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Guarantees for epsilon-greedy reinforcement learning with function approximation. In International Conference on Machine Learning. pp. 4666 4689. PMLR, 2022.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Simon Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint UrXiv:2002.094334 2020.
Milad Farjadnasab and Maryam Babazadeh. Model-free lqr design by q-function learning. Automatica, 137:1 10060, 2022.
Evan M Forman, Stephanie G Kerrigan, Meghan L Butryn, Adrienne S Juarascio, Stephanie M Manasse, Santiago Ontañón, Diane H Dallal, Rebecca Crochiere, and Danielle Moskow. Can the artificial intelligence technique of reinforcement learning to optimize treatment for weight loss? Journal of behavioral medicine, 42:276-290, 2019.
wattiinuuuslymmoiioon digital data
Susobhan Ghosh, Raphael Kim, Prasidh Chhabria, Raaz Dwivedi, Predrag Klasjna, Peng Liao, Kelly Zhang, and Susan Murphy. Did we personalize? assessing personalization by an online reinforcement learning algorithm using resampling. arXiv preprint crXiv:2304.05365, 2023.
Alex Graves, Mare G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In international conference on machine learning, pp. 1311-1320 PMLR, 2017.
Donald Joseph Hejna III and Dorsa Sadigh. Few-shot preference learning for human-in-the-loop rl. In Conference on Robot Learning, pp. 2014-2025, PMLR, 2023.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp- 3796 -8003, 2019.
Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander Hauptmann. Self-paced curriculum learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Nan Jiang. Pac reinforcement learning with an imperfect model. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. International Conference on Machine Learning, pp. 4870-4879, PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances neural information processing systems, 34:13406 13418. 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference Machine Learning, pp. 5084-5096. PMLR, 2021b.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pp. 651-673. PMLR, 2018.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
11

---

Published as a conference paper at ICLR 2024
Man Li, Jiahu Qin, Wei Xing Zheng, Yaonan Wang, and Yu Kang. Model-free design of stochastic lqr controller from a primal dual optimization perspective. Automatica, 140:1 140:110253, 2022a.
Qiyang Li, Yuexiang Zhai, Yi Ma, and Sergey Levine. Understanding the complexity gains of single-task with curriculum. arXiv preprint arXiv:2212.12800 2022b.
Peng Liao, Kristjan Greenewald, Predrag Klasnja, and Susan Murphy. Personalized heartsteps: A reinforcement learning algorithm for optimizing physical activity. Proceedings of the ACM on Interactive. Mobile, Wearable and Ubiquitous Technologies, 4(1):1-22, 2020.
Minghuan Liu, Menghui Zhu, and Weinan Zhang. Goal-conditioned reinforcement learning: Problems and solutions. arXiv preprint arXiv:2201.0822 2022.
Yao Liu and Emma Brunskill. When simple exploration is sample efficient: Identifying sufficient conditions for random exploration to yield pac algorithms. arXiv preprint arXiv: 0180.000055 2018.
Rui Lu, Gao Huang, and Simon S Du the power multitask representation learning in linear mdp. arXiv preprint arXiv:2106.08053 2021.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Parede The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-33 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7540):529 50399-5333300 2015.
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. The Journal of Machine Learning Research, 21 21(1):7382-7431, 2020.
Ian Oshand and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(124):1-62, 2019.
Anastasia Pentina, Viktoriia Sharmanska, and Christoph H Lampert. Curriculum learning of multiple tasks. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 5492-5500, 2015.
Rémy Portelas, Cédric Colas, Katja Hofmann, and Fierre-yves Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In Conference on Robot Learning, pp. 835-853. PMLR, 2020.
Clément Romac, Rémy Portelas, Katja Hofmann, and Fierre-Yves Oudeyer. Teachmyagent: a benchmark for automatic curriculum learning in deep rl. In International Conference on Machine Learning, pp. 9052-9063. PMLR, 2021.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. Nature, 323(6088) 1986.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 191 2014.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Max Simchowitz and Dylan Foster. Naive exploration optimal for online lqr. In International Conference Machine Learning, pp. 8937-8948. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2024
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852-7866 2020.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. arXiv preprint arXiv:2 10.04652, 2021.
Ruosong Wang. Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 13:17816-1788 2020.
Xin Wang, Yudong Chen, and Wenwu Zhu. A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5555-457 2021.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXi:: 2019.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
Ziping Xu and Ambuj Tewari. Representation learning beyond linear prediction functions. Advances in Neural Information Processing Systems, 34:4792-4880 4804, 2021.
Ziping Xu and Ambuj Tewari. On the statistical benefits of curriculum learning, In International Conference on Machine Learning, pp. 24663-24682. PMLR, 2022.
Ziping Xu, Amirhossein Meisami, and Ambuj Tewari. Decision making problems with funnel
structure: A multi-task learning approach with application to email marketing campaigns. In International Conference on Artificial Intelligence and Statistics, pp. 127-135. PMLR, 2021.
Jiaqi Yang. Qi Lei, Jason D Lee, and Simon Du. Nearly minimax algorithms for linear bandits with shared representation. arXiv preprint arXiv:2203. 15664, 2022a.
Ruihan Yang, Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. Advances in Neural Information Processing Systems, 33:4767-4777, 2020.
Zhengyu Yang, Kan Ren, Xufang Luo, Minghuan Liu, Weiqing Liu, Jiang Bian, Weinan Zhang, and Dongsheng Li. Towards applicable reinforcement learning: Improving the generalization and sample efficiency with policy ensemble. arXiv preprini wrXiv:2205.09284 2022b.
Elad Yom-Tov, Guy Feraru, Mark Kozdoba, Shie Mannor, Moshe Tennenholtz, and Irit Hochberg. Encouraging physical activity in patients with diabetes: intervention using a reinforcement learning system. Journal of medical Internet research, 19(10);338, 2017.
Chicheng Zhang and Zhi Wang. Provably efficient multi-task reinforcement learning with model transfer. Advances in Neural Information Processing Systems, 34:19771-19783, 2021.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. -538. PMLR, 2021.
Abilmansur Zhumabekov, Daniel May, Tianyu Zhang, Aakash Krishna GS, Omid Ardakanian, and Matthew Taylor. Ensembling diverse policies improves generalizability of reinforcement learning algorithms in continuous control tasks. 2023.
13


Reviews:
[{"review_id": "IeDtRxOaXv", "reviewer": "Reviewer_E4JK", "summary": "This paper claims that in the scenario of multitask-RL, a naive exploration strategy is enough. It formalizes their intuition in Def 3 and provide the theoretical guarantee in Theorem 1.", "questions": "1. What does Def 3 mean in linear MDP?\n\n2. Can you provide an example where Def 3 holds and the coverage of the base policies is poor?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proof seems to be sound.", "weaknesses": "1. It provides a possible explanation to explain the success of naive exploration in the case of multitask RL. However, it is hard to validate such explanation.\n\n2. The intuition of the proof is that, if we have a base policy class with good coverage, we are able to find the optimal policy by combining the base policies with naive exploration. However, it have been well known that exploration is simple when we have good coverage. Therefore, their contribution seems not novel enough. \n\n[1]. Xie, Tengyang, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. \"The role of coverage in online reinforcement learning.\" arXiv preprint arXiv:2210.04157 (2022).", "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": "", "extra_scores": {}}, {"review_id": "OCZJWj4pOX", "reviewer": "Reviewer_q9zq", "summary": "This paper studies the potential exploration benefits of multitask reinforcement learning from a theoretical perspective. This paper shows that when the set of tasks is diverse enough (measured by multitask MEG), a generic policy-sharing algorithm with myopic exploration is sample-efficient. Importantly, such myopic exploration is common in practice, and computationally efficient (unlike GOLF which requires solving nested optimization oracles). The paper also gives concrete examples of tabular/linear MDPs such that the diversity condition is satisfied. In the end, the paper validates the proposed theory with experiments and builds connections with curriculum learning.", "questions": "- Is it possible to relax Definition 7?\n\n- The offline learning oracle solves  $f_1,...,f_h$ simultaneously. Can you do them sequentially and have similar guarantees?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The general idea of this paper is novel and natural. Sample efficiency of myopic exploration is an important topic.\n\n- The paper is very well-written.\n\n- The theoretical results are sound.\n\n- Discussion on limitations and comparison with prior works are adequate.", "weaknesses": "- The only weakness of this paper in my opinion is that examples where multitask MEG is bounded are too restrictive. Definition 7 is a very strong requirement, and intuitively, diverse tasks can be defined more general. Moreover, the feature coverage assumption is additional since it is not needed for learning linear MDPs with strategic exploration.", "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": "", "extra_scores": {}}, {"review_id": "zi5ZaIKCF8", "reviewer": "Reviewer_ZHzf", "summary": "This paper studies the statistical efficiency of exploration in Multitask Reinforcement Learning (MTRL). The authors show that when an agent is trained on a sufficiently diverse set of tasks, a generic policy-sharing algorithm with myopic exploration design like ϵ-greedy that are inefficient in general can be sample-efficient for MTRL. To validate the role of diversity, the authors conduct experiments on synthetic robotic control environments, where the diverse task set aligns with the task selection by automatic curriculum learning, which is empirically shown to improve sample-efficiency.", "questions": "Please refer to Weaknesses for my questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper shows that when an agent is trained on a sufficiently diverse set of tasks, a generic policy-sharing algorithm with myopic exploration design like ϵ-greedy that are inefficient in general can be sample-efficient for MTRL.\n2.\tThe paper is well-written and easy to follow.\n3.\tTo the best of my knowledge, this is the first theoretical demonstration of the \"exploration benefits\" of MTRL, which is insightful for future research on efficient exploration in deep RL.", "weaknesses": "1.\tThe assumption that the task set is adequately diverse may be too strong in deep RL. Although the authors discuss implications of diversity in deep RL, it remains unclear to me. The authors may want to provide more insight into how to define and design a diverse task set for efficient exploration in deep RL.", "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": "", "extra_scores": {}}, {"review_id": "zq1rjdahJk", "reviewer": "Reviewer_GSze", "summary": "This paper studies the use of multitask training to enable myopic (overly simplistic) exploration methods to discover solutions to difficult MDPs which would otherwise not be tractable to learn directly.", "questions": "-While I generally follow the argument, this paper has some rough grammar and odd word choice in places. I'd recommend a thorough editing pass to improve the language.\n\n-The explanation of the multitask setup in Section 2.1 confused me as to how the tasks are getting selected. Is there a structure or order in which tasks are chosen among M?\n\n-Likewise Definition 1 is a little confusing. C is a function of beta and delta? I'm confused as to why sample complexity doesn't depend on either the algorithm itself or the task(s) being learned. The following paragraph seems to think C is a function of the MDP, but this isn't part of the definition.\n\n-How does algorithm 1 differ from the cited Zhumabekov 2023 policy ensemble method? It seems like algorithm 1 is essentially an ensemble of policies, of which one is sampled for each episode?\n\n-How does this idea of multitask myopic exploration differ from normal goal-directed RL methods like hindsight experience replay? The motivating example in Figure 1 seems roughly in line with such methods, and seems like it should share their limitations (e.g. large state spaces and low-dimensional manifolds of interesting/human-relevant tasks).\n\n -I find the term \"myopic exploration gap\" a little confusing. I understand the intuition (how much could a myopic exploration method improve upon the current best policy at any given time), but I wouldn't call that a gap. Maybe something like \"myopic exploration potential?\" A gap would imply it is comparing myopic exploration to another (optimal?) exploration algorithm. I know this term is coming from previous literature, but it seems confusing unless I'm misunderstanding the definition here.\n\n-Doesn't PPO (like all on-policy policy gradient methods) have issues with epsilon greedy optimization due to it's off-policyness? How did you resolve this issue for the experiments?\n\n-In the tabular case, multitask myopic exploration relies on coverage assumptions in the space of possible tasks (if I understand correctly), but it's not tractable to assume this in the deep RL case. Did this factor come up in the BipedalWalker experiments at all? Do the assumptions (mostly, at least) hold?\n\n-Some more details/analysis on the deep RL experiments in the main paper would be appreciated, such as performance/training curves. I realize the focus of the paper is tabular/theoretical, but this topic has a lot of connections to methods used in deep RL (such as goal-directed RL and automatic curricula, as noted), and in my opinion exploring that connection further would be very interesting.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The core argument of this paper is salient and interesting, and seems to be well supported by the theoretical arguments. The experimental validation in a deep RL context is also appreciated in what is otherwise a theory paper.", "weaknesses": "I'm not well versed in recent theoretical/tabular RL exploration literature, so I can't speak very well to the novelty and significance there, but in a deep RL context this work seems relevant, but also very closely related to existing approaches such as goal-conditioned RL (Hindsight Experience Replay in particular) and to some extent automatic curriculum generation methods. \n\nI think these connections are very interesting, and this theoretical analysis isn't redundant with that work, but it does leave me feeling like this paper would me more interesting/have a stronger contribution if that connection were explored more. As it is I'm left feeling that while this specific argument is to my knowledge novel, it overlaps a lot with prior work. \n\nIn addition, I also felt like the presentation of the paper needs some significant polish. There's some issues with grammar and odd phrasing throughout the paper, and I while I appreciate the intuition provided for various definitions/theorems I felt like I frequently lost the thread on those.\n\nOverall, I think this is solid work that could be high impact, but it needs a little more polish to really shine. As such I'm inclined to recommend rejection, but I also admit that I don't have a good sense of the impact on the tabular RL exploration literature, so I will caveat that I can't properly evaluate that aspect and I will defer to other reviewers there.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)