Robust Knowledge Transfer in Tiered Reinforcement Learning
Authors: Jiawei Huang
Niao He
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning Theory
Transfer RL
Tiered RL
TL;DR: We provide algorithms for robust knowledge transfer in RL, when both source and target tasks are learning in parallel, without knowledge on models' similarity. We further extend the results to the case when multiple source tasks are avilable.

Abstract: In this paper, we study the Tiered Reinforcement Learning setting, a parallel transfer learning framework, where the goal is to transfer knowledge from the low-tier (source) task to the high-tier (target) task to reduce the exploration risk of the latter while solving the two tasks in parallel. Unlike previous work, we do not assume the low-tier and high-tier tasks share the same dynamics or reward functions, and focus on robust knowledge transfer without prior knowledge on the task similarity. We identify a natural and necessary condition called the ``Optimal Value Dominance'' for our objective. Under this condition, we propose novel online learning algorithms such that, for the high-tier task, it can achieve constant regret on partial states depending on the task similarity and retain near-optimal regret when the two tasks are dissimilar, while for the low-tier task, it can keep near-optimal without making sacrifice. Moreover, we further study the setting with multiple low-tier tasks, and propose a novel transfer source selection mechanism, which can ensemble the information from all low-tier tasks and allow provable benefits on a much larger state-action space.

Robust Knowledge Transfer in Tiered RL
Jiawei Huang
Niao He Department of Computer Science ETH Zurich j jiawei. hewggihuaannninn ethz.ch
Department Computer Science ETH Zurich
jiawei www.huannnnnnncc.. ethz. ch
Abstract
this paper, we study the Tiered Reinforcement Learning setting, a parallel transfer learning framework, where the goal is transfer knowledge from the low-tier (source) task to the high-tier (target) task to reduce the exploration risk of the latter while solving the two tasks in parallel. Unlike previous work, do not assume the low-tier and high-tier tasks share the same dynamics or reward functions, and focus robust knowledge transfer without prior knowledge the task similarity. We identify a natural and necessary condition called the "Optimal Value Dominance" for objective. Under this condition, online learning algorithms such that, for the high-tier task, it can achieve constant regret on partial states depending on the task similarity and retain near-optimal regret when the two tasks are dissimilar, while for the low-tier task, it can keep near-optimal without making sacrifice. Moreover, multiple low-tier tasks, and propose a novel transfer source selection mechanism, which can ensemble the information from all low-tier tasks and allow provable benefits on much larger state-action space.
propose novel
further study the setting with
Introduction
Comparing with individual learning from scratch, transferring knowledge from other similar tasks or side information has been proven to be an effective way to reduce the exploration risk and improve sample efficiency in Reinforcement Learning (RL). Multi-Tan RL (MT-RL) [29] and Transfer are two mainstream knowledge transfer frameworks; however, both are subject to limitations when dealing with real-world scenarios. MT-RL studies the setting where a set of similar tasks are solved concurrently, and the main objective is to accelerate the learning by sharing information of all tasks together. However, in practice, in many MT-RL scenarios, the tasks are not equally important and we more interested in the performance of certain tasks. For example, in robot learning. a few robots are more valuable and hard to fix, while the others are cheaper or just simulators. Most existing works MT-RL treat all tasks equally and focus primarily the reduction of the total regret of all tasks as a whole 3 36 I1], with no guarantee of improving a particular task. In contrast, transfer RL distinguishes the priority of different tasks by categorizing them into source and target tasks and aims at transferring the knowledge from source tasks (or some side information like value predictors) facilitate the learning of target tasks [21 27 10] However, key assumption in transfer RL is that the source task is completely solved before the learning of the target task, and this is not always practical. For example, in some sim-to-real domain, the source task simulator may require long time to solve (5), and in some ussrrinteraction scenarios [3]. the source and target tasks refer to different user groups and they have to be served simultancously. In these cases, it's more reasonable to solve the source and target tasks in parallel and transfer the information immediately once available.
RL [26] 18 37
Recently, proposed a new "parallel knowledge transfer" framework, called Tiered RL, which B
is promising to fill the gap. Tiered RL considers the when source task M, and target task
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Mn are learned in parallel, by two separate algorithms Alg and Alg", and its goal is to reduce the exploration risk and regret in learning Mn by leveraging knowledge transfer from MI to Min- [33 showed that under the strong assumption that ML. MIn it's possible to achieve constant regret in learning MD while keeping regret in ML. optimal in gap-dependent setting. Yet, their algorithm based on Pessimistic Value Iteration (PVI) [66] can be hardly applied when the assumption Mro = Mμi breaks, given its pure exploitation nature, making their result very restrictive.
In this paper, we study the general Tiered RL setting without prior knowledge about how similar the tasks are ] The key question we would like to address is: Can we design algorithms s.t.: (1) Regret in ML keeps near-optimal; (2) Regret in Mn achieves provable benefits when ML. and Mln are similar while retaining near-optimal otherwise? Note for Alg we expect it to achieve near-optimal regret bounds, which is reasonable since the source task is often important and our results still hold if relaxing it. As for Alg"i we expect it to be robust, i.e., it can adaptively exploit from M1. if it is close to Mμ. while avoiding negative transfer in other cases. Notably, our setting strictly generalizes [ and is much more challenging, for balancing the exploitation from Mr and exploration from Mn without prior knowledge of task similarity. We give positive answers to the above question in this paper and demonstrate provable benefits with robust knowledge transfer for Tiered RL framework. Below, we summarize our main contributions in three aspects.
Our first contribution is identify essential conditions and notions about when and how our objective is achievable. We first provide a mild condition called Optimal Value Dominance (OVD), and in Sec. 3 we justify its necessity to our objective by lower bound result. Our lower bound holds even if Mr. is fully known to the learner, and therefore, also justifies the necessity of similar assumptions in previous transfer RL literatures O 10] Besides, we introduce the notion of transferable states to characterize states on which Mμ: is expected to achieve benefits by transferring knowledge from M We believe those findings also provide useful insights for further works.
As our second contribution, in Sec. 4 we propose novel algorithms for Tiered Multi-Armed Bandit (MAB) and Tiered RL, which can achieve robust parallel transfer by balancing between pessimism- based exploitation from ML. and optimism-baa -based online learning in MIn. Depending on the similarity between ML and Ma, our algorithms can enjoy constant regret proportion of state-action pairs or even on the entire Mn by leveraging information from ML. while timely interrupting negative transfer and retaining near-optimal regret states dissimilar between two tasks. Moreover, in the bandit setting, our result implies a strictly improved regret bound when ME+ = ML.. compared with previous results under the same setting [22 [3).
Beyond the single low-tier task setting, in many real-world scenarios, it's reasonable to assume there multiple different low-tier tasks ML {Mo,, 1W available. As our third contribution, in Sec. 5 we extend our algorithm to this setting with a new source task selection mechanism. By novel techniques, we show that, even if each Mao, may only share similarity with Mi on a small portion of states, we are able to ensemble the information from each source task together to achieve constant regret much larger state action space "stitched" from the transferable state-action set in each individual ML at the expense of an additional log W factor in regret. Besides, our algorithm is still robust model difference and retains near-optimal regret in general. Although we only study the Tiered RL setting in this paper, we believe our task selection strategy can be applied to standard transfer RL setting [9] 10) when multiple (partially correct) side information or value predictors provided. which is an interesting direction for future work. Finally, we conduct experiments in toy examples verify our theoretical results.
1.1 Closely Related Work
For the lack of space, we only discuss closely related work here and defer the rest to Appx. A.2 The most related to us is the Tiered RL framework [13). which originally motivated by Tiered structure in user-oriented applications. However, they only studied the case when Mμ = ML.. which limits the practicability of their algorithms. Although there is sequence of work studying parallel transfer learning in multi-agent system 25 19]. but they mainly focused on heuristic empirical algorithms and did not have theoretical guarantees.
Transfer RL 37 compared to learning from scratch, can reduces exploration risk of target task by leveraging information in similar source tasks side information 21 9 [0]. Comparing with
We defer the detailed framework Appx. A.1 for completeness, which is the same as Fr. 1 in [3
2

---

transfer RL setting, our parallel transfer setting has some additional challenges. Firstly, Mi can only leverage estimated value/mode//optimal policy from MI. with uncertainty, which implies we need additional efforts to control failure events with non-zero probability comparing with normal transfer RL. setting. Secondly, the constraints on the optimality of Regret, (Ma), although reasonable, restrict the transferable information because in ML estimation uncertainty can only be controlled on those states frequently visited. Moreover, none of these previous work studies how to leverage multiple partially correct side information like what we did in Sec. 5 In MT-RL setting, the benefits of leveraging information gathered from other tasks has been observed from both empirical and theoretical works [1 3 g 24 36 M.. But MTRL treats each task equally, and the reduction of total regret over all tasks does not directly imply benefits achieved in a particular task.
2 Preliminary and Problem Formulation
Tiered Stochastic MAB and Tiered Episodic Tabular RL In Tiered MAB setting, we consider a low-tier task ML. and a high-tier task Mi sharing the arm/action space A = 21, ..., A). By pulling the arm E [A] in Mis or MMi. the agent can observe a random variable rL) or THe E [0, 1]. We will use (i) = (i) and (i)(i) E[r (i)] to denote the expected return of the i-th arm in ML and MHi respectively, and note that it's s possible that (Lo(i) A (H)(
For Tiered RL, we assume that two tasks ML. A, FLo. and Mn = (S, H. share the finite state S and action space A across episode length H (i.e. Sn = A. A for any h E [H), but may have different lime-dependent transition and reward functions Pi. = 'H = { W.l.o.g., we assume the
h==,, T' initial state 81 is fixed, and the reward functions 1i. and Th are deterministic and bounded by [0, 1]. In episodic MDPs, we study the time-dependent policy specified as π == [ HH} with Th Sr - A(AA) for all h E [H.]. where ((As) denotes the probability simplex over the action space. With a slight abuse of notation, when Th is a deterministic policy, we use Ty : Sr + An to denote the deterministic mapping. Besides, we use Q7 (s, a) = E| (sw,,,a))))
(PPr...) }
) and Ih =
an)) 82 8, On- = Enwr Q7 (5, a)] denote the value function for at step h [H]. and denote ()))) == Pr(#s, = (T) and ( == Pr(*;- a, |T) as the state and state-action occupancy w.r.t policy π. We use IT" denote the optimal policy, and V Qi, dž as a short note when n². To avoid confusion, we will specify the policy and value functions in ML and Mμ by Lo and Hi in subscription, respectively. For example, in Mi we have TLo == { ... Lo, J. Dioc /V and Cia, /V.,, d Lo,h di and similarly for MHT.
a, a) (s)
Dap-Dependent Setting Throughout, we focus on gap-dependent setting 17 23 34 7. Below we introduce the notion of gap for ML as an example, and those for Mμi follows similarly. In MAB case, the gap in ML w.r.t. arm is defined as (i) == maxjelA (Loo)))LLo(i)) Vi [A]. and for tabular RL setting, we have Ao a4) == ( - Qio, an), wh E [H] s,. Sz an E An. We use Loimin to refer the minimal gap such that Assh;a)) 2 ALa,iin for all non-optimal actions an. and use Amin ;= Lin(AL,minn min to denote the minimal gap over two tasks. In the gap-dependent setting, we assume Amin 0.
Knowledge Transfer from Multiple Low-Tier Tasks In this case, we assume there are W > 1= > and all the tasks share the same state and action spaces but may have different transition and reward function. We defer the extended framework for this setting to Appx. A We specify the task index
1 different source tasks ML = {Mo,,
[W] in sub-scription to distinguish the notation for different source tasks (e.g. FLo,w, (DO.,.)) Moreover, we define Amin := mii mim. .... ALo, Wimin: AHi }. For convenience, in the rest of the paper, we use TRL-MST (Tiered RL with Multiple Source Task) as a short abbreviation for this setting.
1.iin
Performance Measure We use Pseudo-Regre as performance measure: Regret (MLo) == 1=1 (T - 1ith (s1) where K is
ΣK (s1) - vith(ss)] Regretx (Mn) = ΣK
the number of iterations, }
1 km are generated by the algorithms. 1K km and {
Frequently Used Notations We denote [n] {1. 2, .... n1. Given transition matrix P. S x A + ASS), and a function V: : - R. we use PV an) as a short note of E,r-P(().a) (V J. We will use 'i../ in to denote the optimal arm in bandit setting, and /i.// काj denotes the optimal policy in RI. setting. In TRL-MST setting, we use // / "L v to distinguish different source tasks.
3

---

2.1 Assumptions and Characterization of Transferable States
Throughout the paper, we make several assumptions. The first one is the uniqueness of the optimal policy, which is common in the literature [22 4]
Assumption A. Both MLo (or {Mo,,
ha (
and Mn have unique optimal arms/policies.
Next, we introduce new concept called "Optimal Value Dominance" (OVD for short), which says that for each state (or at least those states reachable by optimal policy in M1.)). the optimal value of
Mi is approximate overestimation for the optimal value of Mn. In Sec. we will use lower bound to show such a condition is necessary to attain the robust transfer objective.
Assumption B. In single source task setting, we assume Mi has Optimal Value Dominance (OVD) over Mni s.t., vh E [H]. for all 8% E S₁, (or only for those S/ with Lo, (8%) > 0), we have: ( 2 VR, (sn) 2(1+1)) TRL-MST setting, we assume each ML, has OVD over MH:
We remark that Assump. B is rather mild condition that naturally holds with reward shaping. Note that since (+) S
h. by shifting the reward function of ML T (-x = (L). + immediately obtain the OVD property. Even though, such reward shift may impair the set of transferable states as we will introduce in Def. 2.2 We provide several reasonable settings in Appx. [A.3 including identical model [13], small model difference, and known model difference, where Assump. B is satisfied and there exists a non-empty set of transferable states, We also point that several existing work on transfer RL assumed something similar even stronger 9 which we defer a thorough discussion to Appx. A.2
Assumption C. The learner has access a quantity Amin satisfying 0 < Amin Amin-
The final one is about the knowledge of a lower bound of Amin which can always be satisfied by choosing Amin = 0. Nevertheless, it would be more beneficial if the learner has access to some quantity Amia closer to Amia than O. As we introduce below, the magnitude of Amia is related to how we quantify the similarity between MLo and My and which states we expect to benefit from knowledge transfer. Below we focus on the single source task setting and defer the discussion for TRL-MST setting to Sec. S
Definition 2.1 (s-Close). Task Mn is s-close to task Mi on sp at step for some >>
0,
(s,) - VHi (sk) S e and (st. = (sh).
Definition 2.2 (A- -D-rrassferable States). State 8n is X-transferable for some À 0, if di (8N) À and Mi is Amin -close to ML. 8s. The set of X-transferable states at h E [H] is denoted as -/A- 4(H+1)
We regard 8h in MLo has transferable knowledge Mu, if it can be reached by optimal policy in ML and the optimal value and action at 8 for two tasks are similar. Here the condition dio(ss) > is necessary since in ML., only the states reachable by Tio can be explored sufficiently by Alg' due its near optimal regret. Combining with Assump. B one can observe that the value difference on transferable states are controlled by | (sn) VH, (sn)) (sx)) 0 )سرو < 0 Aia)))) ). As we will show in Thm. 3.2 in Sec. 3 the term O(Amin) is indeed unimprovable if we expect robustness.
3 Lower Bound Results: Necessary Condition for Robust Transfer
Now we establish lower bounds that show Assump. B is necessary and how the magnitude of Amin restricts the robust transfer objective. The results in this section are based on two-armed Bernoulli bandits for simplicity, and the proofs are deferred to Appx. B By extending these hard instances to RL case, there is gap caused by the additional π in Assump. B and Def. 2.2 which comes from the requirement of our algorithm design, and we leave it to the future work.
Justification for Assump. B We show that if Assump. B is violated, it is impossible to have algorithms (Alg'a, Lo Alg to simultancously achieve constant regret when Mr. = MIn- while retaining sub-linear regret for all the cases regardless of the similarity between ML. and Mnn- Here we require constant regret on Mr. Mn since we believe it is a minimal expectation to achieve benefits in transfer when
For convenience, include the bandit setting special case with H O: also Def. 2.1
2.2 and F.I

---

the two tasks are identical. Intuitively, without Assump. B even if we know pLo( = ( we cannot ensure L is the optimal arm in MH. Then, if (Alg" Lo Alg Mi MHi, the algorithm must stop exploration on the arm o Lo after finite steps, and thus, suffers from linear regret in another instance of MHi where iia A 'in-
achieve constant regret on
Moreover, Thm. 3.1 holds even if the learner has full information of Moo where the setting de- generates to normal transfer RL since there is no need to explore Mo This explains why similar assumptions Assump. B Brre considered in previous transfer RL works [0
Theorem 3.1. Under the violation of Assump. even regardless of the optimality of Alg" for each algorithm pair (Alg" )lgh cannot simultaneously (1) achieve constant regret for the case when Mio MH and (2) ensure sub-linear regret in all the other cases.
Amin in Tolerance Error Inevitable Next, we show that, if MH and Mi are A-close for some A 2 Amin in general cannot expect achieve constant regret Mu by leveraging ML without other loss. Similar to Thm. 3.1. the main idea is to construct different instances for Mi with different optimal arms and cannot be distinguished within finite number of trials.
Theorem 3.2. (Transferable States are Restricted by Aminl I Under Assump.
B regardless of the optimality of Alg" 1" given arbitrary Amin and arbitrary A E (Agin Amini for each algorithm pair (Alg"a ), cannot simultaneously (1) achieve constant regret for the when MLo and Mui with minimal gap Amiu are A-close, and (2) ensure sub-linear regret in all other cases.
4 Robust Tiered MAB/RL with Single Source Task
In this section, study Tiered MAB and Tiered RL when single low-tier task ML available. The key challenge compared with [3] is that we do not have knowledge about whether ML and Mn are similar or not so the pure exploitation will not work. Instead, the algorithm should be able to identify whether ML. and Mu are close enough to transfer by data collected so far, and balance between the exploration by itself and the exploitation from Mi the same time.
To overcome the challenge, we identify a state-wise checking event, such that, under Assump. B if 8n, is transferable, the event is true almost all the time, and otherwise, every mistake will reduce the uncertainty so the chance the event holds is limited. By utilizing it, our algorithm can wisely switch between optimistic exploration and pessimistic exploitation and achieve robust transfer. In Sec. 4.1 we start with the MAB setting and illustrate the main idea, and in Sec. 4.2, we generalize our techniques to RL setting, and discuss how to overcome the challenges brought by state transition.
4.1 Robust Transfer in Tiered Multi-Armed Bandits
The algorithm is provided in Alg. We choose Alg as UCB, and Alg as an exploitation-or-UU UCB style algorithm branched by a checking event in line which is the key step to avoid negative transfer.
Algorithm 1: Robust Tiered MAB
Initilize: a > 2; (1), N (t), (t), (h((1) + O, Vi A: f(k) 16A 1)²
Pull each arm at the beginning A iterations
3 for k = A + 1, A + 2, K do
pi.(1) - -t.0)) +
2cx log F(R) (E
#o + arg max; Tho
* + aL.
(1,(1) + ((.) (1)
2cx log [(K] (O)
Lo + arg max, _ (i).
*
phi(()) + Phi (1)
2ex F(k]
# arg max, Tim (i).
(1)
i' (mtt)) S P
+ and Aik (mft)) > k/2 then म + at. else THe <- _/.
Interact Maa/ MLo by / / Update N/++) /Nok+
1 and empirical mean PLa /PA
sk++ k+1
end
Key Insights: Separation between Transferable and Non-Transferable Cases To understand our checking event, we consider the following two cases: (1) Mi and MH are s-close, and (2) in it
5

---

(in the rest cases we have 'Hi 't but [Lo > Mmil ( + E, so exploiting from ML is harmless).
Recall Assump. in Case have Mia ((io) S pm (mn(
while Case 2, with an appropriate Amia Amin), ), we have PLo (ti.)) 2 MHi (H))) Amin 2 M
(Hi(8 (8),)) + Am(ii.))
choice of E (e.g. which reveals the separation between two cases. As a result, we can construct an uncertainty- upper bound ( (f[.) for y (fL.). should expect the event & = ()o < / (* + e almost always be true in Case 1, while in Case 2, everytime& & occurs and Alg" takes ii.. the "self-correction" triggered: the uncertainty is reduced so the estimation Pin (zin) gets closer to (l (L and because of the separation between MLO (+n)) and (H)() the number of times that & is true is limited. The remaining issue that we do not know (L and i and we approximate them with LCB value M4 (-) and its greedy policy. The additional checking event N (=f.) > k/2 is used to increase the confidence that mia = d.o once transfer, which also contributes to reducing the regret. Finally, to achieve constant regret, we use control the total failure rate to be Σ k constant C. We summarize the main result Thm. 4.1 and defer the proof to Appx. C
C for some
Theorem 4.1. [Tiered MAB with Single Source Tasks] Under Assump. A
B
and by rumning Alg.
with Sugin and a > 2, we always have Regret x (Mu) = O OmEsm()) (m( log K). Moreover
Aman -close, we have: Regret g (Mm) = O am))))) (g( log A
if Mm and ML are 4
Amin
As we can see, our algorithm can automatically achieve constant regret if tasks are similar while retaining near-optimal otherwise. Notably, even when Mni ML,,
Comparison with [22 13
regret bound o (()))(()) Amity) is strictly better than O
min - Antt)) in [22 and
(A i)( (1)
(1y in 13 under the same setting.
Amfi)
4.2 Robust Transfer in Tiered Tabular RL
In this section, we focus on RL setting. We provide the algorithm in Alg. 2 where we defer the details of Modell.earnin function and the requirements for Bonus function to Appx. D.I In the following, we first highlight our main result.
Theorem 4.2. [Tiered RL with Single Source Tasks] Under Assump. B and Cond. D.1 for Alg
and Cond. D.3 for Bonus function, by running Alg. 2 with Amin
4(H+1) a > 2, an arbitrary X >> O,
we have
Regret (Ma) O(SH)
Σ h=1
H
Σ
H Amin
Ani(Sh, an) log(SAHK)).
Here the set Cº C Sp. X An captures the benefitable state-action pairs to be introduced later. For simplicity, in Thm. 44. above, we omit all constant terms independent with K that may include A-1, A or log 1/d7 The complete version of Thm. 4.2 can be found in Thm. D.16 As we can
see, comparing with pure online learning algorithms 123 34 77, in our setting, Mr only suffers
non-constant regret on subset of the state-action space. The SH factor may be further improved by
choosing better Bonus functions than our Example D.4 given in Appx. D.I
Different from the bandit setting, the state transition causes more challenges. In the following, first explain the algorithm design to highlight how we overcome the difficulties, and then provide the analysis and proof sketch. Detailed proofs can be found in Appx. [
Technical Challenges and Algorithm Design Similar to MAB setting, for ML. we choose an arbitrary near-optimal algorithm, and for Mn we set up a state-wise checking event Vio,, (.) S
Ōh OH. = + in line 15 to determine whether exploit from ML not. Here Vl and Q Q & serve as lower and upper bounds for Vi and Q and VL,, and T are constructed by Pessimistic Value Iteration [6). which can be shown to converge to Vi and TLo,h- respectively. Similar to [33.
for the choice of Al and the bonus term used to construct lower/upper confidence estimation, we consider general algorithm framework under Cond. D.I and Cond. D.3 in Appx. D.I
To overcome challenges resulting from state transition, make two major modifications when moving from MAB to RL setting. First of all, because of the constraint on the optimality of Alg

---

Algorithm 2: Robust Tiered RL
Input: Ratio À E (0, 1); a > 2; Auxiliary functions Bonus and Modell earnning Sequence of confidence level (dx) 122 with 8І- = =1/SAHK" := A Amin/ (oinn/((1 /4H + 1) for some Amin S Amin
2 Initialize: LL Dit - U: Vk, V (),H41 O (),+11 VA H4 2 Hi H41
0.
for k 1, do
To (D
(Poo, 18 t ModelLearning ( (bi Mi < Bonus(Dio>> 5x).
5
for h = H, H 1..., 1 do
La,h (..)) < m0 (o, Pion Vto.b - b (::)).
1o, (.) max. p (,,a), (.o,(()) +- arg max, 2 (:aa).
end
H Th=1 ModelLLarningg(D (H= (HHAA H
Bonus 1 8g).
10
11
for h H, H 1..., 1 do
2 (.))) -- max m0, (H, + T (i - (. )
12
13
O (..)) f- mmin(H,,n,,h (:..) + Pot Vi
Hi.44 (::-) 6h (:--)].
14
for 8n Sp, do
VV lo.h (8n) - Sh. (sh. Iin.) + and max, N Ni. (8h, a) > 3 then
15
16
8 "In (8h) t- arg maxa Ni (sh, a). ). "Trust and Exploit" Branch
17
end
else THe (.) & arg max, a (.a. /1 "Explore by itself" Branch: Hi (sk) & min H, @i. (sh. * + 1
18
H (QHi, (sh, T - Q (sh, mb))
19
20
Hi (s)) = HiA (f).
21
end
end
Deploy TH to Mo MHi and get o Thi and update D D
end
we cannot expect Mr. to provide useful information those (8,, an) with di (8%, ax) = 0 since they will not explored sufficiently. Therefore, the checking event in line [5] we include criterion, where À is prper-parameter chosen and input to the
max, .V a) > ((Ak) algorithm. Intuitively, for all sh. an, we should expect N Lo (Sh, ax) = Ö(dr, an) k) when & is large enough. Therefore, by comparing No,, with Ak, we can filter out those sy with dia to avoid harm from inaccurate estimation.
Secondly and more importantly, different from MAB setting, besides the error occurred at a par- ticular step, we also need to handle the error accumulated during the hack-propagation process of value iteration. our case, this is reflected by the loss of overestimation when we incorporate selective exploitation into the optimism- based exploration framework. To see this, suppose at some Sh, have overestimation optimal value QHa, denoted as Q QHL When the checking cri- terion is satisfied, if we mimic the MAB setting, i.c., assign Too, to k THis and update value by V (sk) (sh, a when of. (sx) * (sn), VHi,, is no longer guarantced to be an overestimation for Vi (sn). As Vi (st) involves in back-propagation, will pull down the estimation value for its ancestor states, thus reducing the chance to visit SΛ and slowing down the "self-correetion process" which works well in MAB setting.
The key insight to overcome such difficulty is that, if the checking event holds yet (sn))) * TH. (sh),, the gap between Qi mio) and Qi, (sh, mta) should not be small, and we can show that Q (sh, at.) Qi T(.)) 2 Qin,n(sh mta) + O H AHi (sh, m(a)) with the choice of
7

---

== O(5mia// H). Therefore, revising ( moo) by adding H/H of the gap O (sh, mfo Vin, (Lo) (line 19h is enough to guarantee the overestimation. Lastly, since Q (8h, Too in unknown, we construct underestimation Q (sh; mLo) and use it instead. As result, we have the following theorem, where the clip function is defined by Clip[æ/[w == x T[ 2 w].
Theorem 4.3. There exists Kust Poly(S, A, A, Amin), such that, for all k 2 Kosti on some event EN with IP(Ex) S 36x, we have Qin. (8h: un) S Qin. (Sh; an); Vin S V Vi,.(())) 4h [M], 8h E Sh. On E As and
Amin 4eH
V Am(snsan)
(811 - VH, (s1) S 2elE
Σ
Clip
min H, 4b (sh, an))
(1)
4e
Benefits of Knowledge Transfer We first take look ls 2 host. As implied from Eq. (I). we can upper bound the regret on each Sh. On by summing over the RHS of Eq. (.. Note that by Cond. [D.3] 1 ah) = O Poly(SAH) log and E[ (sh; an)]
k-1 d= (sh. an), we can establish the
VNa,a (
near-optimal regret bound with similar techniques in (33 regardless of the similarity between MH and MLo Moreover, because of the knowledge transfer from MLo, we can achieve better regret bounds for MH. In the following, we characterize three subclasses of state-action pairs, on which Alg only suffers constant regret. First of all, for those 5Λ E Z we can expect the checking event almost always hold for arbitrary k. Hence, when k is large enough, "i6, (9%) = (sk) 2 "inA (8K), implying Alg Hi will almost never take sub-optimal actions at 8h since then. We denote this first subclass as Cl.A == ((sh,a))s*, E 2 an F (sa)) Secondly, note that, given a state 8h. if all possible trajectories starting from 81 to 8h have overlap with C for some h' E [h - 1], when k is large enough, THe will almost have no chance to reach 5n and will not suffer the regret at Sh. For convenience, we define function Block( (C).. (C),A1A-1 1--1 IM=1: sn) which takes True for those states described above, and takes False for the others. Then, we define the second subclass by CZ.2 : [((n, an) )n)) |Bloc)llll( ( ( J 8h) = True, 8h & Z an E An.. Finally, for those 8h, ap with din (8h; an) > O, we can show (sh,
(in((% k,)k. Therefore, b (*), an) x
log k\ V M/M (5h, an) in Eq. ① will decay and the clipping operator will take effect, which leads to constant regret. This third subclass is denoted by C2 := {ss,, [d]]d (sh, an) > 0}. Based on the above discussion, we define C₁ == ChA. UCA U.₁, be the benefitable states set in Thm. 4.2
For k S Koat, for the lack of overestimation, we simply use to upper bound the value gap V y
This results in a PSly(S, A, H, X- A burn-in term, which was omitted in Thm. 4.2 since is independent with K. Besides, by the definition of host in Thm. 4.3 we can see the trade-off of choosing X: smaller À can enlarge C₁ so we have constant regret on more state-action pairs, while it also results in the delay of overestimation by the larger host-
Constant Regret in the Entire MDP We may expect constant regret in the entire MHi in some special cases. Note that, if vh E [M]] Vsa, with dig (5x) ) > O, Sh, E Z we have C, = S₁ x An. Regret x (MHi) will be independent w.r.t. K. From this perspective, if À is chosen appropriately, e.g. S min,, din (s)), we can recover the constant regret under the setting ML. Mn in [13]
Choice of X In this paper, we do not treat À as parameter optimize. In practice, without prior knowledge about max,, (sx), one may choose X = O(1/S) to ensure some chance that transferable states exist, since there exists at least some states satisfying di (sn) 2 1/S.
Robust Tiered MAB/RL with Multiple Low-Tier Tasks
Now, we focus on the case when source task set Mio := {Mo 1 is available (see Frw. 5 in Appx. A Our objective is to achieve benefits on those states 8n, as long as there exists some task W E [WT such that Mr and MHi are close on 3h, while retaining near-optimal regret in other cases under Assump. The key challenge comparing with single task case is that, Alg has to identify for each state which task in Mio is the appropriate one to leverage. The main novelty and contribution
8

---

in this section is a task selection mechanism we call "Trust rill Failure", which can automatically adapt the similar task if it exists. We first highlight the main results for MAB and RL setting.
Theorem 5.1. [Tiered MAB with Multiple Source Tasks] Under Assump.
B and by run-
ning Alg. 3 with MLo = (M ) and Mto with & Auii and a > 2, we always have:
Regret& x (Mu) O(Esm())>0 Am((i) (o))W Moreover, if at least one task in Mio is Agin.
close to MHI, we further have: Regret, & (MH) O Am)())0 Am(() log AW
Amin
Theorem 5.2. (Tiered RL with Multiple Source Tasks] Under Assump. by running Alg.
C and Cond. D.3
F.4
7 in Appx. F.1
with Amin. 4(H+1))
and any X O. we have
H Regretg x (Mm) = o SH
Σ h=
Σ
Amin A
1
llg Jog(SAHWK))
Au((shas) an)
(N), X. \c (CA.
Algorithm 3: Robust Tiered MAB with Multiple Source Tasks
Initilize: a > 2; (1), NE (f), (t), (1)()) t O, Vi E A: f(k) == 16T 1)? 2 Pull each arm at the beginning A iterations. Set w + Null.
for k + 1, 2.... K do
for w = 2.,... W do
piu (i) t p.., (i) +
2a lng. f(k)
T f arg max, pio w (i),
Tio.w + #Lo
Nia,
1i,,00 (i) (
2a log F(K) Nio
I arg max, 1 (i).
end
p (i) + P (1) + 2a F(R)
TH +- arg max; (H)(()
I (w E [W]l
(It
THe ( and Nik Lo (II ( > k/22
I* = 0 then wx Lo,00
Null, कli #H
11
else
12
ww # Null and wk E Ih then w + wk
=k
"Hi Lo,
f- =
else if wk 1 + Null and Ew E I such that THi arg max; Noo, (i) then
13
14
t t w, Mtn + ato.
15
end
16
else with Uni end
m THi
+ Ik
17
Interact with MHi (Mo JW by Thi (mto, W
18
Update [ 11 Nx++ and empirical mean (F 1 26+1 for each arm.
19
Lo
20 end
For the lack of space, in the following, we only analyze the bandit setting to explain the key idea of our task selection strategy. For the RL setting, we defer to Appx. F the algorithm Alg. 7 detailed
version of Thm. 5.2 (Thm. D.16). defintion of transferable set C₁ C,7 (Def. F.2 and technical details.
Algorithm Design and Proof Sketch for Bandit Setting The algorithm is provided in Alg. 3 Comparing with Alg. ii single task setting, the main difference the task selection strategy from line tto to line 17 We first examine each source task with a checking event similar to single task setting, and collect those feasible tasks passing the test to I Intuitively, for those ML close to M1., we expect MI E I holds almostly for arbitrary > O, while for the other Mi if takes the position of n following Mo.,'' will reduce the uncertainty and will be ruled out from It eventually. So we expect w can "escape" from dissimilar source tasks but be absorbed to the similar task exists. Therefore, if T empty, Alg Hi will do exploration by itself. Otherwise, we choose one from = to transfer the action until it fails on the checking event. However, for any the algorithm chosen, those "marginally similar" source tasks (denoted as ML..)), which are e' clooe to My for some s' only slightly larger than E, may cause some trouble. Because the checking event

---

will finally eliminate Mr since they are not E-close, but it may occupy the position w for a long time before elimination, especially when e' is extremely close After eliminating ML, Alg needs to re-select one from I Now since other sub-optimal arms in Mu haven't been chosen for a long time and the confidence level 6, = O(1/k") is decreasing, Ih will include those dissimilar tasks again, which causes difficulty identify the true similar task. To solve this issue, once the previous trusted task fails, we give priority to the task recommending the same action as the previous one (line T4 As result, since Mo, and Marwe share the optimal action, after the elimination of ML can expect w only switch among those tasks ML.. with T -Hi We highlight this technical novelty to Lem. 5.3 below, and defer all the proofs to Appx.
Lemma 5.3. [Absorbing Similar Task] Under Assump. A B Band
C there exists constant c² s.t., if there exists at least one w E [W] such that Mio, is Squu close to Mm, by running Alg. with log oAW, we have Pr(TTi o (nn) = O p
E Amin and a 2, any lo 2 K- = c² 4
o.A.
32
Amio
min
Experiments
In this section, we evaluate our most representative algorithm, Alg. 7, in multiple source tasks setting.
Experiments Setting We set S A = 3 and H = 5. The details for construction of source and target tasks are defered to Appx. G We adapt StrongEuler in [4] as online learning algorithm to solve source tasks, and use the bonus function in 23 as the bonus function in our Alg. 7. We evaluate algorithm when W 0, 2, 5, where W means the high-tier task Mi simply solved by normal online learning method (StrongEuler) without any parallel knowledge transfer. We choose À 0.3 1/S in Alg. 7, and in the MDP instance test, across all S H 15 states, for W = 1, 2, 5, the number of transferable states would be 6, 9 and 13, respectively.
We choose iteration number K 1e7, where we start the transfer since A: = 5c5 avoid large "burn-in" terms. As we can sec, after the transfer starts, the regret in target task will suddenly increase for while, because the target task has make some mistakes and learn from it as a result of the model uncertainty. However, because of our algorithm design, the negative transfer will terminate after very short period. As predicted by our theory, by adding more and more source tasks which can introduce new transferable states, the target task will suffer less and less regret.
6000
Regret
5900
5700
5600
0.5
10
[transfor starts)
Iterations (1e6)
Figure 1: Regret in the Target Task given Multiple Source Tasks We report the result when W source tasks are available with W =0, 0, The shadows indicate 96% confidence interval.
7 Conclusion and Future Work
In this paper, we study how do robust parallel transfer RL when single or multiple source tasks are avilable, without knowledge on models' similarity. The possible future directions include relaxing assumptions, better strategies leveraging multiple source tasks, and identifying mild structural assumptions allowing for more aggressive transfer, and we defer to Appx. A.4 for more details.
Code available httpa///ct/a/oeteooaaaaaaa/aaa/a -tt.://oddbtt--Teee----
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Andreas Krause for valuable discussion. The work is supported by ETH research grant and Swiss National Science Foundation (SNSF) Project Funding No. 200021- 207343.
References
[1] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
[2] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[3] Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning, 2013.
[4] Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizabilityy: the power of gaps. arXiv preprint arXiv:2203.13935. 2022.
[5] HeeSun Choi, Cindy Crump, Christian Duriez, Asher Elmquist, Gregory Hager, David Han, Frank Hearl, Jessica Hodgins, Abhinandan Jain, Frederick Leve, et al. On the use of simulation in robotics: Opportunities, challenges, and suggestions for moving forward. Proceedings of the National Academy of Sciences, (18(():+197885111 2021.
[6] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning, 2017.
[7] Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL / http:s////oennreeee...ee. Saammidddcuuq@hB3300
[8] Carlo D' Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, Jan Peters, et al. Sharing knowledge in multi-task deep reinforcement learning. In 8th International Conference Learning Representations, (ICLR) 2020, Addis Ababa, Ethiopia, April 26-30, 2020, pages 1-11. OpenReview. net, 2020.
[9] Noah Golowich and Ankur Moitra. Can q-learning be improved with advice? In Conference on PMLR, 2022.
Learning Theory, pages
[10] Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai Sham M. Kakade, and Sergey Levine. Unpacking reward shaping: Understanding the benefits of reward engineering on sample complexity. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL net/ Net//oruumiddDD X3kH BkpN
[11] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pages 4358. PMLR, 2021.
[12] Jiawei Huang. Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie-Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. arXiv preprint arXiv:2202.064/ 064.0 2022.
[13] Jiawei Huang, Li Zhao, Tao Qin, Wei Chen, Nan Jiang, and Tie- Liu. Tiered reinforce- ment learning: Pessimism in the face of uncertainty and constant regret. arXiv preprint ar0iv:2005.1 /2418 2022.
[14] Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2758, 2020.
11

---

[15] Chi Jin, Zeyuan Allen-Zhi Sebastien Bubeck, and Michael Jordan. Is q-leamiig provably efficient? arXiv preprint arXiv:1807.03765 2018.
[16] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
[17] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[18] Alessandro Lazaric. Transfer in reinforcement learning: a framework and a survey. Rein- forcement Learning, pages 143-173 Springer, 2012.
[19] Yongyuan Liang and Bangwei Li. Parallel knowledge transfer in multi-agent reinforcement learning, 2020.
[20] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Advances neural information processing systems, 33; 1264-1274, 2020.
[21] Timothy A Mann and Yoonsuck Choe. Directed exploration in reinforcement learning with transferred knowledge. In European Workshop on Reinforcement Learning, pages 59-76. PMLR, 2013.
[22] Chloé Rouyer and Yevgeny Seldin. Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227-3249, PMLR, 2020.
[23] Max Simchowitz and Kevin G Jamicson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances Neural Information Processing Systems, 32, 2019.
[24] Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context- based representations. In International Conference on Machine Learning, pages 9767-9779. PMLR, 2021.
[25] Adam Taylor, Ivana Dusparic, Maxime Guériau, and Siobhán Clarke. Parallel transfer learning multi-agent systems: What, when and how transfer? In 2019 International Joint Conference on Neural Networks (IJCN), pages 1-8. IEEE, 2019.
[26] Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: survey. Journal of Machine Learning Research, 10(7), 2009.
[27] Volodymyr Tkachuk, Sriram Ganapathi Subramanian, and Matthew E. Taylor. The effect of q-function reuse on the total regret of tabular, model-free, reinforcement learning, 2021.
[28] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.062200 2021.
[29] Nelson Vithayathil Varghese and Qusay H Mahmoud. survey of multi-task deep reinforcement learning. Electronics, 9(9):1363, 2020.
[30] Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning, arXiv preprint
2022.
[31] Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: hierarchical bayesian approach. In Proceedings of the 24th international conference on Machine learning, pages 1015-1022, 2007.
[32] Tengyang Xie, Ching-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.
[33] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27440 2021.
12

---

[34] Haike Xu, Tengyu Ma, and Simon Du. Fine- ainengrained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Conference Learning Theory, pages 4438 4472. PMLR, 2021.
[35] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730-27277 2775. PMLR, 2022.
[36] Chicheng Zhang and Zhi Wang. Provably efficient multi- task reinforcement learning with model transfer. Advances in Neural Information Processing Systems,
2021.
[37] Zhuangdi Zhu, Kaixiang Lin, and Jiayu Zhou. Transfer learning in deep reinforcement learning: survey, arXiv preprint arXiv:2009.07880 2020.
13


Reviews:
[{"review_id": "lLrIfjebWp", "reviewer": "Reviewer_G1Lf", "summary": "The paper extends the work of Huang et al (2022) on Tiered Reinforcement Learning (where the objective is to transfer knowledge from the low tier (risk-tolerant) source task to a high-tier (risk-averse) target task while solving the two two tasks in parallel) by relaxing the assumptions of identical reward and transition functions in the source and target tasks.\nThe paper first identifies ‘Optimal Value Dominance’ a necessary condition to keep the source algorithm near-optimal while achieving provable benefits for the regret in the high-tier algorithm when Low and High tier tasks are similar.\nThe paper then proposes algorithms for tiered multiarmed bandit and tiered reinforcement learning with regret lower bounds depending on the similarity between the low- and high-tier tasks, with an improved lower bound for the case when the tasks are the same compared to Huang et al (2022).\nFinally, the paper also considers a case when there are multiple low-tier tasks, in which the most similar states to the high-tier task are chosen from any of the low tier tasks for an additional log W factor in regret.", "questions": "What do you mean by ‘back-propagation process of value iteration’ (line 255)? I am familiar with the concepts of backpropagation and value iteration individually, but their combination is rather ambiguous to me.\n\nHow would one go about choosing the lambda hyperparameter before beginning to solve the tasks? ", "limitations": "The authors are upfront about the limitations, such as the unique optimal policy assumption, and mention in the appendix that the avoidance of the lower bound knowledge about the minimal gap would be beneficial. Concerns for negative societal impact in this theoretical paper are not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality\n\nThe paper extends the framework (multiple low-tier tasks) of and relaxes some of the assumptions (non-identical reward and transition function among the low- and high-tier tasks) of a previous paper on Tiered RL.\n\nQuality\n\nThe paper is mostly well-written, clear and concise. The paper motivates the problem setting well in the introduction, and places it well in the literature. The concepts are introduced and explained in a logical order.\n\nClarity\n\nThe paper has a similar structure to Huang et al (2022). It is mostly clear and easy to follow, although certain parts do feel a bit rushed. (I will mention them in the Weaknesses part.)\n\nSignificance\n\nThe paper contributes a few findings in Tiered RL that could be useful to the community: it proves a tighter lower bound for the case when the lower and higher tier tasks are the same, and proves lower bounds for the case when the reward and transition functions differ depending on the difference in the gaps. It also introduces to setting when there are multiple low-tier tasks.", "weaknesses": "The work in this paper results from a minor relaxation of certain assumption in Huang et al (2022), and a lot of possible extensions and improvements are left for future work.\n\nThe RL results depend on a hyperparameter, lambda that needs to be chosen wisely.\n\nMinor typos/grammar/style issues that did not affect the rating of this paper:\n\nLines 37, 41 and 52: “In [13]” is considered bad style, either write Author et al (year) [13], or better yet just cite the claim.\n\nLines 62: conceptions -> findings\n\nLines 67-68, starting with while: that subsentence makes no sense, please rephrase\n\nThe sentence on lines 125-127 seems like it belongs to the Frequently Used Notations subsection, not to 2.1\n\nLine 165: no need for ‘actually’\n\nLine 166: ‘leave it to the future work’ -> ‘leave it for future work’\n\nLine 176: remove ‘kind of’ or replace with ‘may [explain]’\n\nLine 177 is -> are, literatures -> papers/works/publications\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. We will fix the typos as mentioned. Below we address the main questions raised by the reviewer. \n\n### “this paper results from a minor relaxation of…”\n\nWe humbly disagree to credit our contributions as “minor relaxation” of the assumptions.\n\nFirst of all, removing the assumption that the low-tier and high-tier tasks share the transition and reward functions is highly non-trivial and of great practical value, which is also noted by Reviewer 5dMC and Reviewer 9F2D . The sharing model assumption in Huang et al (2022) requires very strong prior knowledge (and often unrealistic), which allows simple algorithm design based on PVI. Moreover, without such prior knowledge, the problem becomes much more challenging as we need a carefully designed strategy to identify and avoid negative transfer. We introduce several novel components, including (1) a branching condition to decide transfer or not (noted in our Algs. 1,2), (2) value adjustment to re-ensure overestimation, etc, which are substantially different from PVI in [1].\n\nSecondly, we generalize the results of tiered RL from single source task to multiple different source tasks, which is another substantial extension. This requires the introduction of a novel source task selection mechanism to ensemble information from low-tier tasks , which has not been studied in existing literature and can be of independent interest for transfer learning. \n\n### The choice of hyperparamter $\\lambda$\n\nWe want to highlight that we do not treat $\\lambda$ as a parameter to be optimized.\nInstead, we are interested in studying the effect of this parameter on the regret.\nMoreover, our main results will not be undermined if the choice of $\\lambda$ is not ideal (as long as keep it away from 0), since as we proved, the regret is always at least near optimal and \\lambda will only affect the size of transferrable states. \n\nIn practice, without prior knowledge about $\\max_s d^*_{\\text{Lo}}(s)$, one can choose \\lambda to be around $\\Theta(1/S)$, since for each layer $h$, there exists at least one state such that $d^*_{\\text{Lo}}(s_h)\\geq 1/S$, or one can choose it to be constant level to avoid large “burn-in” terms.\n\n### “back-propagation process of value iteration”\nIt refers to the backward update $V_h(\\cdot) \\gets \\max_{a_h} r_h(\\cdot,a_h) + \\mathbb{P}_h V\\_{h+1}(\\cdot) + (bonus)$, which computes value functions from back to the front. We will modify the wording. \n\n[1] Huang et. al.,  Tiered reinforcement learning: Pessimism in the face of uncertainty and constant regret. \n"}, {"review_id": "BmS4Rj9ORb", "reviewer": "Reviewer_5dMC", "summary": "This paper studies the tiered reinforcement learning setting, a transfer learning setting where the goal is to transfer information from a low tier task to a higher tier one while learning both to solve both tasks in parallel.\nContrary to prior work the author do not assume that both tasks share the same rewards and dynamics, they show it is still possible to benefit from the low tier task to learn the higher tier one. The author also extend their work by considering multiple low tier tasks and present selection mechanism which can gather information the different tasks.\n", "questions": "In the multiple source tier setting is there a point where adding more tasks with a low similarity with the high tier tasks can hurt performance?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Overall this is a solid paper, while technical the paper is well written and properly organized.\nRemoving the assumption that the low and high tier sources share the same dynamics and rewards makes this setting much more applicable and interesting.\nThe setup with multiple low tier tasks is also valuable could have many applications.", "weaknesses": "It would have been interesting to add empirical evaluations of the proposed algorithms to understand their actual performance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive and valuable feedback. Below we address the questions raised by the reviewer. \n\n### For the experiments\nWe conduct some empirical evaluation on toy examples, which well verifies our theory. Please refer to our global response for more details.\n\n### More tasks could be harmful\nThanks for the interesting question. One direct observation is that, for the fixed failure rate, we need to adjust the bonus term by a $\\log W$, where $W$ is the number of source tasks. Therefore, it could be harmful if one continuously adds source tasks which cannot enlarge the set of transferable states. It might be interesting to study how to select tasks which have more potential to introduce new transferable states, but it is out of the scope of this paper."}, {"review_id": "hWnKAInro9", "reviewer": "Reviewer_9F2D", "summary": "The authors propose a robust parallel knowledge transfer reinforcement learning algorithm for single or multiple source tasks without knowledge on model similarity using the previously defined Tiered Reinforcement Learning framework. The paper remove the limitation on prior knowledge about the task similarity to generalize the framework. The main contribution is three-fold: 1) Establish necessary conditions for lower regret bound, 2) propose robust parallel transfer algorithms for reinforcement learning and its special case, multi-armed bandits, and 3) describe a new source task selection mechanism that guarantees constant regret for larger space of state-action pairs using multiple low-tier tasks.\n", "questions": "Please provide the appendices to complete the evaluation of the work on soundness and its relation to prior work.\n", "limitations": "The authors do not provide limitations of the proposed approach. There are no societal issues related to this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Originality. Removing the assumption on task similarity poses new challenges to guarantee lower regret bounds that are not trivial. The new algorithm to solve the general knowledge transfer require learning whether low-tier and high-tier tasks are similar from observed data and balance between exploration and exploration from the low-tier model at the same time. The lower bounds from simplifying the general case simplify to the prior work under the similarity conditions between low- and high-tier tasks. Therefore, the lower bounds are sound. To extend the approach for the high-tier task to leverage multiple low-tier tasks, the authors describe a method called “trust till failure” that still guarantees lower bounds on regret.\n\nQuality & Clarity. The contribution and novelty is well defined. The definitions and equations are sound.\n\nSignificance. The proposed approach generalizes the previous work to a larger class of problems while still maintaining lower bounds on regret minimization.", "weaknesses": "Originality & Significance. To remove the limitation of task similarity for generalization is not trivial. However, the motivation for generalization is lacking with few references to potential robotics applications. The paper can benefit from providing an illustrative example or toy problems to motivate new class of problems the proposed method can be applied to. \n\nQuality. I am assuming the authors made a mistake and uploaded the incomplete paper. The related work is supposed to be in the Appendix but there are no Appendices attached to the submitted paper. Without these Appendices, it is difficult to compare how the new method compared to prior work. There are several grammatical errors and the conclusion section does not talk about the limitations of the current approach. The future work is also in Appendix which is not included in the paper.\n\nClarity. It is not clear how parallel knowledge transfer is any different from meta-learning and/or why it is not a special case of meta-learning. It will be good to discuss when the learning methods overlap or differ under which conditions to better motivate the approach. Specifically, for the use case of multiple low-tier learners with a single high-tier learner. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. Below we address the concerns raised by the reviewer. \n\n### About the appendix\nWe  are afraid the reviewer might have overlooked the **Supplementary Material** part of the submission, where we include the full paper with appendix in a zip file. \n\nIf space allowed, we are happy to move part of the related work (currently in Appx A.2 and A.3) and future work (currently in Appex A.5) from the supplementary material to the main paper in the revision for ease of reading and completeness.  We kindly invite the reviewer to check these discussions in the Appendix.\n\n### Lack of motivation and illustration on toy problems\nThanks for the suggestion. We will strengthen our motivation by highlighting other potential applications and theoretical gaps in the existing work. Following the suggestion, we have now included some numerical illustration on a toy example which showcases the performance of our proposed algorithm and validates our theory. Please refer to our global response and the attached PDF for more details. \n\n### Difference with Meta-Learning\n\nIn general, meta learning is about learning to learn from **metadata**. Here learning to learn means it learns an algorithm instead of outputting a policy, and metadata refers to the data about data, for example, properties about the algorithm used, learning task itself, etc.\n\nIn contrast, in our Tiered RL setting, like transfer RL, we distinguish the importance of tasks and directly use the **data from other source tasks** to accelerate the policy learning in the \"high-tier\" tasks.\nIn another word, meta learning considers to use “high-order” data to learn an algorithm, while we target at using normal data from source tasks to benefit “high-tier” tasks.\n\n\n### Limitations of the proposed approach \n\nWe have discussed some limitations of our results  and open problems in Appedix A.5, for instance, the dependency gap in the lower bound for RL case (see also lines 164-166),  the OVD assumptions. Following the suggestion of the reviewer, we will assemble these limitations in an explicit section in the main paper."}, {"review_id": "GVCPmaDHiq", "reviewer": "Reviewer_BLAr", "summary": "The authors look at the tiered reinforcement learning setting, which is a parallel transfer learning framework where the goal is to transfer knowledge from a low-tier source task to a high-tier target task in order to reduce the exploration risk of the high-tier task. Additionally, these tasks are solved in parallel. Contrary to previous related work, the authors do not assume the low-tier and high-tier tasks share dynamics or reward functions and focus on robust knowledge transfer without prior knowledge on task similarity. The authors use a condition called the “Optimal Value Dominance” to propose novel online learning algorithms that can achieve constant regret on partial states depending on the task similarity and near-optimal regret when the two tasks are dissimilar. Furthermore, for low-tier tasks, these algorithms keep near-optimal regret at very little cost. The authors also study the scenario when multiple low-tier tasks are present and propose a novel transfer source selection algorithm that can gather knowledge from all low-tier tasks and produce benefits on a much larger state-action space.", "questions": "* What type of data have others used on this problem or similar RL problems? Can it be leveraged in this setting as well?", "limitations": "* The authors did not address the fact that they did not perform any experiments with either synthetic or real data on their model.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The regret analysis of the robust tiered multi-armed bandit (MAB) models was very thorough.", "weaknesses": "* No experiments that compared performance with other tiered RL algorithms\n* It would have nice to have had the related work in the manuscript instead of as a supplement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address the concerns raised by the reviewer. \n\n### Experiments that compared performance with other tiered RL algorithms\nWe highlight that the general setting of tiered RL without prior knowledge of task similarity and/or with multiple source tasks has not been studied in the literature (which is precisely the gap our work aims to fill in); thus there exists no benchmarks or state-of-the-art baselines in this case for us to run comparison with. \n\nFollowing the reviewer’s comment, we have now conducted some empirical evaluation of our algorithm on toy examples, which well verifies our theory. Please refer to our global response and PDF attached there for more details.\n\n### Related work \nThanks for the suggestion. We are happy to move part of the related work (currently in Appx A.2 and A.3) from the supplementary material to the main paper in the revision for ease of reading and completeness as long as the space allows.  We apologize for the inconvenience and invite the reviewer to check these discussions in the Appendix for now. \n### “What type of data …”\nTo our knowledge, there is no prior work studying the theory of parallel transfer RL with single or multiple source tasks.\nFor the normal transfer/multi-task RL setting, it is studied to transfer a fixed well-learned value functions [2], or data collected from other tasks [3]. \nIn our setting, the source tasks are not solved in advance, and the target task should leverage the information from them once available, so we transfer the trajectory data in source tasks directly, which actually contains all the raw information and can be used to further construct value or transition estimations.\n\n[1] Huang et. al.,  Tiered reinforcement learning: Pessimism in the face of uncertainty and constant regret. \n\n[2] Noah Golowich and Ankur Moitra. Can q-learning be improved with advice?\n \n[3] Chicheng Zhang and Zhi Wang. Provably efficient multi-task reinforcement learning with model transfer."}, {"review_id": "6qnwrdiyix", "reviewer": "Reviewer_MBdo", "summary": "The paper presents an extension of \"Tiered-RL\", a multi-fidelity RL framework where a \"low-fidelity\" environment is executed in parallel with the \"high-fidelity\" environment, with the purpose of training faster while keeping near-optimal regret. The paper is a theoretical exploration without empirical evaluation", "questions": "- A doubt regarding the setting. Would the agent care about the performance in all tiers? Or is it only important to optimize the performance in the highest tier? If only the highest tier matter, the setting is exactly the same as in multi-fidelity RL as said in the \"weaknesses\" section, otherwise, I would need more clarification of in which practical application this modeling would be useful.", "limitations": "No foreseeable negative societal impact", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper presents a deep theoretical evaluation of a setting that is very relevant yet not very methodologically-explored: When we have related tasks of varied importances to be solved (such as sim2real), and one task can be leveraged to learn faster another one.\n- An algorithm able to guarantee near-optimal regret while training in multiple tasks might be of use in security-critical applications such as robotics or medical domains.", "weaknesses": "- While the theoretical results sound exciting, I would expect at least a simple empirical evaluation of the proposed algorithm to be provided to show how hard it is to actually implement the algorithm in a practical domain. \n\n- The \"Tiered RL\" setting sounds very similar (if not exactly the same) as the multi-fidelity RL modeling, that wasn't even cited by the authors. While there is still a novelty in the exact way the problem is solved by running all \"tiers\" (or fidelities) in parallel, the problem formulation seems exactly like multi-fidelity MDPs to me, and I would suggest to use the same multi-fidelity MDP formulation to keep consistency in the literature. Multi-fidelity MDPs are explicitly modeled in this paper:\n \nSilva, Felipe Leno, et al. \"Toward Multi-Fidelity Reinforcement Learning for Symbolic Optimization.\", Adaptive and Learning Agents (ALA) workshop, 2023.\n\nAnd the multi-fidelity RL problem has been explored in a similar way in the following papers\n\nSami Khairy and Prasanna Balaprakash. 2022. Multifidelity reinforcement learning with control variates. arXiv preprint arXiv:2206.05165 (2022).\n\nMark Cutler, Thomas J Walsh, and Jonathan P How. 2014. Reinforcement learning with multi-fidelity simulators. In 2014 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 3888–3895.\n\nAt the very least all of those papers should have been included to your related works section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address the concerns raised by the reviewer. \n\n### Experiment\nThanks for the suggestion. We conduct some empirical evaluation of our algorithm on  toy examples, which well validates our theory. Please refer to our global response for more details.\n\n### Difference with Multi-fidelity RL and Questions about the setting\nThanks for pointing out the references on multi-fidelity RL. We will properly cite them and add discussions about it.  We believe our Tiered RL setting has fundamental differences from multi-fidelity RL setting. \nMulti-fidelity RL considers the case when both low-fidelity, cheap data and high-fidelity, expensive data are available, and aims at solving the task with least queries to high-fidelity simulators by leveraging low-fidelity data.\nIn contrast, as we motivated in our introduction, the Tiered RL setting sits in between transfer RL and Multi-Task RL, where source and multiple tasks are solved in parallel. With close inspection, we can see\n\n(1) In multi-fidelity RL, although there are simulators at different levels, there is only one task to be solved, while in Tiered RL, we have to solve source and target tasks. \nMore importantly, as we clearly mentioned in the ontroduction section (line 45-48), although we want to benefit target tasks by knowledge transfer, we still expect source tasks do not sacrifice for that and still retain near-optimal regret. This objective inherits from [1], and it is reasonable for user-interacting applications with “tiered customer” structure. Please refer to [1] for more concrete examples.\n\n(2) In multi-fidelity RL, it is assumed that the low-fidelity data is cheap and abundant. However, in Tiered RL, like multi-task RL, the tasks are solved in parallel, so the samples from low-tier tasks are still limited (in each iteration, either source or target tasks can only collect one trajectory).  The data scarce in source tasks also makes our setting more challenging.\n\n\n[1] Huang et. al., Tiered reinforc ment learning: Pessimism in the face of uncertainty and constant regret."}]

Author rebuttal:
We thank reviewers for their hard work and valuable feedbacks.

## General Remarks on Experiments
Several reviewers (Reviewer 5dMC, Reviewer 9F2D, Reviewer BLAr, Reviewer MBdo) pointed out the lack of empirical evaluations as a main weakness. In our humble opinion, as a theory paper, our results provide a solid understanding on the provable benefits and fundamental limits with robust knowledge transfer in tiered RL. We believe the results are already interesting on their own, both from theoretical and technical perspectives. Note that the majority of the references (e.g., [9, 36]) that we cited in the paper (many also published at ICML/NeurIPS) do not contain any numerical results. 

Nevertheless, we agree with the reviewer that some empirical validation can still be valuable.  Note that the general setting of tiered RL without prior knowledge of task similarity and/or with multiple source tasks has not been studied in the literature (which is precisely the gap our work aims to fill in); thus there exists no benchmarks or state-of-the-art baselines in this case.  A reasonable experiment would be to validate the performance of our own algorithms. To this end, we select the most representative Tiered RL algorithm, Alg. 7 in multiple source tasks setting, and evaluate it on a toy tabular MDP task. In the PDF attached in this response, we report the numerical results.  

As we can see from Figure 1, 
* After the transfer is activated, the regret in the target task will suddenly increase for a while, because the target task has to make some mistakes and learn from it as a result of the model uncertainty. However, because of our algorithm design, the negative transfer will terminate after a very short period.
* If we add more source tasks which can introduce new transferable states, the target task will suffer less regret.

We believe this experiment well verifies our theory prediction and we are happy to add these and more experimental results in the revision if the reviewers find them necessary.   

Below we provide details on the experimental setups. 

### Construction of Source and Target Tasks
We set $S=A=3$ and $H=5$. We first randomly construct the transition function of the high-tier task $M\_{\text{Hi}}$ (i.e. $\mathbb{P}\_{\text{Hi}}$ are randomly sampled and normalized to make sure their validity). 
Then, similarly, we randomly construct the reward function of $M_{\text{Hi}}$ and shift the reward function to ensure $M_{\text{Hi}}$ has unique optimal policy and $\Delta_{\min, \text{Hi}} = 0.1$.

Next, we construct the source tasks by randomly permute the transition matrix of $M_{\text{Hi}}$. In another word, for any $s_h$, we randomly permute $a_1,a_2,a_3$ to $a_1',a_2',a_3'$ and assign $\mathbb{P}\_{h,\text{Lo}}(\cdot|s_h,a_i') \gets \mathbb{P}\_{h,\text{Hi}}(\cdot|s_h,a_i)$ for $i\in[3]$. In this way, the Optimal Value Dominance (OVD) condition is ensured, and we can expect some of $s_h$ are transferable when $\pi^*_{\text{Lo}}(s_h) = \pi^*_{\text{Hi}}(s_h)$.
When the number of source tasks $W > 1$, we repeat the above process and construct $W$ different source tasks.

### Experiments Setting
We adapt StrongEuler in [1] as online learning algorithm to solve source tasks, and use the bonus function in [1] as the bonus function in our Alg. 7.

We evaluate our algorithm when $W = 0, 1, 2, 5$, where $W = 0$ means the high-tier task $M_{\text{Hi}}$ is simply solved by normal online learning method (StrongEuler) without any parallel knowledge transfer.
We choose $\lambda = 0.3 \approx 1/S$ in Alg. 7, and in the MDP instance we test, **among all $S\cdot H=15$ states, for $W=1,2,5$, the number of transferable states would be 6, 9 and 13, respectively**.

We evaluate for $K = 1e7$ iterations, where we start the transfer from $k=5e5$, in order to avoid large "burn-in" terms because of the large uncertainty in source tasks in early stage. Each curve is averaged over 20 runs, and the shadows indicate 96% confidence intervals.


[1] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. (NeurIPS 2019)

Meta-review: The paper studies a specific transfer learning paradigm where knowledge is transferred from a low-tier (source) task to a high-tier (target) task. While all reviewers agree that more solid empirical evaluation would make the paper much stronger, there is consensus that the setting, the algorithmic and theoretical contributions are sufficient to accept the paper.

I would suggest the authors to integrate reviews and rebuttal into the final version of the paper. In particular, provide strong motivations for the setting and clarify the technical challenges and the value of the theoretical results.
Decision: Accept (poster)