Provably Efficient Lifelong Reinforcement Learning with Linear Representation
Authors: Sanae Amani
Lin Yang
Ching-An Cheng
Venue: ICLR 2023 poster (2023)
Keywords: Lifelong RL
Contextual MDP
Regret
Planning calls
Computation sharing
Streaming sequence of adversarial tasks

Abstract: We theoretically study lifelong reinforcement learning (RL) with linear representation in a regret minimization setting. The goal of the agent is to learn a multi-task policy based on a linear representation while solving a sequence of tasks that may be adaptively chosen based on the agent's past behaviors. We frame the problem as a linearly parameterized contextual Markov decision process (MDP), where each task is specified by a context and the transition dynamics is context-independent, and we introduce a new completeness-style assumption on the representation which is sufficient to ensure the optimal multi-task policy is realizable under the linear representation. Under this assumption, we propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks while using only sublinear planning calls. Specifically, for $K$ task episodes of horizon $H$, our algorithm has a regret bound $\tilde{\mathcal{O}}(\sqrt{(d^3+d^\prime d)H^4K})$ using $\mathcal{O}(dH\log(K))$ number of planning calls, where $d$ and $d^\prime$ are the feature dimensions of the dynamics and rewards, respectively. This theoretical guarantee implies that our algorithm can enable a lifelong learning agent to learn to internalize experiences into a multi-task policy and rapidly solve new tasks.

Published as a conference paper at ICLR 2023
PROVABLY EFFICIENT LIFELONG REINFORCEMENT LEARNING WITH LINEAR REPRESENTATION
Sanae Amani
Lin F. Yang University of California, Los Angeles
University of California, Los Angeles
samani@ucla.edo
1 linyangêee. ucla. edu
Ching-An Cheng
Microsoft Research, Redmond Belngannc@iicroooftccom
ABSTRACT
We theoretically study lifelong reinforcement learning (RL) with linear representa- tion in a regret minimization setting. The goal of the agent is to learn a multi-task policy based linear representation while solving a sequence of tasks that may be adaptively chosen based on the agent's 's past behaviors. We frame the problem as linearly parameterized contextual Markov decision process (MDP), where each task is specified by context and the transition dynamics is context-independent and we introduce a new completeness-style assumption on the representation which is sufficient to ensure the optimal multi-task policy is realizable under the linear representation. Under this assumption, we propose an algorithm, called UCB Life- long Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks while using only sublinear planning calls. Specifically, for task episodes of horizon H. our algorithm has a regret bound (( + H based on O log(K)) number of planning calls, where d and d' are the feature dimensions of the dynamics and rewards, respectively. This theoretical guarantee implies that algorithm enable lifelong learning agent learn internalize experiences into multi-task policy and rapidly solve new tasks.
INTRODUCTION
Recently, there has been surging interest designing lifelong learning agents that can continuously learn to solve multiple sequential decision making problems in their lifetimes (Thrun & Mitchell
1995: Khetarpal et al. 2020 Silver et al. 2013 Xic & Finn 202I). This scenario is in particular
motivated by building multi- purti-purpose embodied intelligence, such robots working in weakly structured environment (Roy et al. 2021]. Typically, curating all tasks beforehand for such problems nearly infeasible, and the problems the agent tasked with may be adaptively selected based on the agent's 's past behaviors. Consider a household robot as an example. Since each household is unique, difficult to anticipate upfront all scenarios the robot would encounter. Moreover, the tasks the robot faces are not independent and identically distributed di... Instead, what the robot has done before can affect the next task and its starting state; e.g., if the robot fails to bring a glass of water and breaks it, then the user is likely to command the robot to clean up the mess. Thus, it is critical that the agent continuously improves and generalizes learned abilities to different tasks, regardless of their order.
In this work, we theoretically study lifelong reinforcement learning (RL. in a regret minimization setting (Thrun & Mitchell 1995 Ammar al.) 2015). where the agent needs to solve sequence of tasks using rewards in an unknown environment while balancing exploration and exploitation. Motivated by the embodied intelligence scenario, we suppose that tasks differ in rewards, but share the same state and action spaces and transition dynamics (Xie & Finn 2021). To be realistic, we make no assumptions on how the tasks and initial states are selected" generally we allow them to be chosen from a continuous set by an adversary based on the agent's 's past behaviors. Once task is specified
We adopt stricter definition of lifelong RI. here to distinguish it from multi-task RI,, while there existing works lifelong RI. (e.g. Brunskill [i 2014 : Lecarpentier al. (00T)) assuming i.i.d. tasks.

---

Published as a conference paper at ICLR 2023
and revealed, the agent has one chance (i.e., executing one rollout from its current state) to complete the task and then it moves to the next task.
The agent's goal is to perform near optimally for the tasks it faces, despite the online nature of the problem. This means that the accumulated regret of the learner compared with the best policy for each task should be sublinear in its lifetime. We assume that there is no memory constraint; this usually the case for robotics applications where weal-w interactions are the main bottleneck (Xie & Finn, 2021). Nonetheless, we require that the agent eventually learns to make decisions without frequent deliberate planning, because planning is time consuming and creates undesirable wait time for user-interactive scenarios. In other words, the agent needs to learn a multi-task policy, generalizing from not only past samples but also past computation, to solve new tasks.
Formally, we consider an episodic setup based on the framework of contextual Markov decision process (CMDP) AAbbasi-Yadkorf & Neul 2014 Hallak al., 2015). It repeats the following steps: 1) At the beginning of an episode, the agent is set to an initial state and receives context specifying the task reward, both of which can be arbitrarily chosen. 2) When needed, the agent uses its past experiences to plan for the current task. 3) The agent runs policy in the environment for a fixed horizon in an attempt to solve the assigned task and gains experience from its policy execution. The agent's s performance is measured as the regret with respect to the optimal policy of the corresponding task. We require that, for any task sequence, both the agent's overall regret and number of planning calls to be sublinear in the number of episodes.
While lifelong RL is not new, the realistic need of simultaneously achieving 7) sublinear regret and 2) sublinear number of planning calls for 3) a potentially adversarial sequence of tasks and initial states makes the setup considered here particularly challenging. To our knowledge, existing works only address a strict subset of these requirements; especially, the computation aspect is often ignored. Most provable works in lifelong RL make the assumption that the tasks are finitely many (Ammar
2015; Zhan et al. 2017 Brunskill & Li, 2013). or are i.i.d. (Ammar et al., 2014] Brunskill & Li |i 2014 Abel al.] 20188] Sa by Lecarpentier et al. [002T). while others considering similar setups to
et al.
ours do not provide regret guarantees (Isele et al. |016 Xie & Finn, 2021). On the technical side, the
closest lines of work are Modi & Tewari (2020); Abbasi- Yadkori & Neu (2014) Hallak et al. (2015):
Modi et al. (2018): Kakade et (2020) for contextual MDP and Wu et al. (2021 [Abels et al. (2019)
for the dynamic setting of multi-objective RL, which study the sample complexity for arbitrary task
sequences; however, they either assume the problem is tabular require model-based planning oracle with unknown complexity. Importantly, none of the existing works properly addresses the need of sublinear planning calls, which creates large gap between the abstract setup and practice need.
In this paper, we aim to establish a foundation for designing agents meeting these three practically important requirements, problem which has been overlooked in the literature. As the first step, here we study lifelong RL with linear representation. We suppose that the contextual MDP linearly parameterized (Yang & Wang] 2019 Jin et al. 2020) and the agent needs to learn multi-task policy based on this linear representation. To make this possible, we introduce a new completeness- style assumption the representation which is sufficient to ensure the optimal multi-task policy is realizable under the linear representation. Under these assumptions, we propose the first provably efficient lifelong RL algorithm, Upper Confidence Bound Lifelong Value Distillation (UCBlvd, pronounced as "UC Boulevard"), " that possesses all three desired qualities. Specifically, for K episodes of horizon H, we prove regret bound Ō ((v(d3 + H'd)H*)) using Ö(dH log( ()) planning calls, where d and d' are the feature dimensions of the dynamics and rewards, respectively.
From a high-level viewpoint, UCBIvd uses linear structure to identify what to transfer and operates by interleaving /) independent planning for set of representative tasks and 2) distilling the planned results into a multi-task value-based policy. UCBlvd also constantly monitors whether the new experiences it gained are sufficiently significant, based doubling schedule, to avoid unnecessary planning. On the technical side, UCBIvd's 's design is inspired by single-task LSVI-UCB (Jin et al.) 2020), however, we introduce a novel distillation step based QCQP, along with a new completeness assumption, to enable computation sharing across tasks; we also extend the low-switching cost technique (Abbasi- Yadkori et al. 2011 Gao et al. [221 Wang al. 2021 for single-task RL to the lifelong setup to achieve sublinear number of planning calls.
Notation. Throughout the paper, we use lower-case letters for scalars, lower-case bold letters for vectors, and upper-case bold letters for matrices. The Euclidean-nomm of is denoted by ||x||| We denote the transpose of a vector x by xT. For any vectors x and y, we use (x, y) to denote their
2

---

Published as a conference paper at ICLR 2023
inner product. We denote the Kronecker product by A @ B. Let A E R be a positive definite and v E IRd. The weighted 2-norm of v with respect to A is defined by || == vv VvTAv. Av.. For positive integer n, [n|] denotes the {1, .2]. Finally, we use the notation Ô for big-O O notation that ignores logarithmic factors.
J. For a real number a, we denote {a}+ max(a, 0}.
PRELIMINARIES
We formulate lifelong RL as a regret minimization problem in contextual MDP (Abbasi-Yadkori & Neu 2014; Hallak et al. 2015) with adversarial context and initial state sequences. We suppose that context determines the task reward but does not affect the dynamics. Such a context dependency is common for the lifelong learning scenario where an embodied agent consecutively solves multiple tasks. Below we give the formal problem definition.
Finite-horizon contextual MDP. We consider a finite-horizon contextual MDP denoted by M = (S, A, W, H,P, r), where S is the state space, A is the action space, W is the task context space, H is the horizon (length of each episode), P = (Fr, } l==1 are the transition probabilities, and r = (rx } the reward functions. We allow S and W to be continuous infinitely large, while we assume A is finite such that m can be performed easily. For h E [H] ra 0, w) denotes the reward function whose range is assumed be in [0, 1), and Px a) denotes the probability of transitioning to state s' upon playing action a at state 8. In short, a contextual MDP can be viewed as an MDP with state space S W and action space A where the context part of the state remains constant in an episode To simplify the notation, for any function f, we write PA [f]ss a) = B, [f')..
Policy and value functions. In a finite-horizon contextual MDP, policy π = {= is sequence where Ta S SXW - A determines the agent's action time-step h. Given π,, we define its state value function as (s, w) == E = Th (sh', The (SW,, w), w)]s; s] and its action-valus function as (T, a, w) TA ( a, w) Ph [V ws)(s, a), where Q7+ 0. We denote the optimal policy as 7T, w) == sup, Vr," (s, w). and let Vi = Vi"" and Q7 == Q denote the optimal value functions. Lastly, recall the Bellman equation of the optimal policy:
2% a, w) = r, a, w) + PA[V (., w)((s,)) a), Vi, w) = max Q7 (s, a, w). aEA
(1)
Interaction protocol of lifelong RL. The agent interacts with a contextual MDP M in episodes. For presentation simplicity, we assume that the reward functions r are known, while the transition probabilities P are unknown and must be learned online; we will discuss how reward learning can be naturally incorporated in Section 4.3 At the beginning of episode kt the agent receives a task context w² E: W and is set to an initial state of. both of which can be adversarially chosen. The agent can use past experiences
plan for the current task, if needed. Then the agent executes its policy nh: at each time-step h E [H), it observes the state s%, plays an action o (s w*), observes a reward ri = (s a w and goes to the next state sh+1 according to Py, (.lss, a.)).))))))))) Let K be the total number of episodes. The agent's goal to achieve sublinear regret, where the regret is defined as
RK = ΣK
K (st w²) - VT* (st, w*).
(2)
As the comparator policy above (namely nT" that defines Vi²) also knows the task context, achieving sublinear regret implics that the agent would attain near task-specific optimal performance on average.
Linear Model Representation. We focus on MDPs with linear transition kemels and reward functions (Jin et al. 2020; Yang & Wang 2019) that are encapsulated in the following assumption. Assumption (Linear MDPs). M- = (S, A, H, P, W) is linear MDP with feature maps & S x A- > Rdd and ub S A X W + Rdd That is, for any h. E [H], there exist a vector nn and d measures H₁ = [un (1) ,....,,y (d)JT over S such that F (Pls. a) (M)()) ((s. a)) and rn(s, a, w) = (Th (bss, a, w)) for all (s, a, w) E S x A x W. Without loss of generality, ()(s,a)]l, < 1. [|, w)ll2 s 1, [|))())]22 S Vd, and mall2 I vdl for all (s,a, w,h) e S x Ax W x [M]]
In real-world problems, can use the context to model the task specification of problem. For example, if we want to design household robots to assist humans with a series of tasks like cooking, cleaning, washing dishes, lawn mowing, vacuuming, we can treat the the context natural language
In general, context-dependent dynamics would take the form (a |8, a, w)..
3

---

Published as a conference paper at ICLR 2023
instruction that the human user would give to the robot, and can view the representations 2b and Φ as the embedding of a deep neural network model that has been pre-trained.
Example 1 (Weighted Rewards). An interesting and common special case is *6(s, a, a.) = a)) @ p(w), for some mapping p W + IR". In this case, it holds that d' -nd and (s, a, w) (p(w), rn(s,a)). a)), where ra (s, a) Ax a) E IRm, . some An. BRmxd, is the vector reward functions at time-step h. We can view Th a, w) as weighted reward with weights p(w) that depend on task w. This setting is closely related to Multi-Ohjectivn RL. studied for tabular case in Wul et al. 20 which studies the case where p(w)
R along with tabular S and A.
3 A WARM-UP ALGORITHM FOR LIFELONG RL
We first present a warm-up algorithm based on linear representation, termed Lifelong Least-Squares Value Iteration (Lifelong-LSS) LSVI), in Algorithm T which is straightforward extension of the single- task LSVI-UCB algorithm proposed by Jin et al. (222)) to the lifelong learning setting. The motivation of this warm-up algorithm is to give intuitions how the problem structure in Assumption I used to achieve small regret and discuss the computational difficulty in lifelong learning.
can be
We will show that Lifelong-LSV has a sublinear regret bound, which matches the minimax optimal rate in the special case studied by Wu et al. (202T) in terms of number of objectives, m (see Example D}. However, we will also show that Lifelong-L that the number of planning calls it requires grows linearly with the number of episodes, which would mean the overall computational complexity grows quadratically. This high computation cost is because the agent never learns to internalize the task solving skills but requires going though all past experiences for planning every time new task arrives. Importantly, we will discuss why cannot be made computationally efficient in an easy manner without further assumptions on the representation. This drawback motivates our new completeness assumption and main algorithm, UCBlvd, which is provably efficient in terms of both regret and number of planning calls, in Section 4
is not computationally efficient, in the sense
We remark that Lifelong-LSVI is only a warm-up up algorithm that guides the reader to understand the mechanisms used for addressing the problem, motivates the need for UCBlvd, and shows what regret bound is possible when computational complexity is not concern (though being impractical).
3.1 ALGORITHMIC NOTATIONS
To begin, we introduce the template and the notations that will be used commonly in presenting the warm-up algorithm, Lifelong-LSVI and later our main algorithm, UCBIvd. For each algorithm, first we will define an algorithm-specinn the agent's 's policy at time-step h in episode k; then we present the full algorithm and its analysis using the quantities below, which are defined with respect to each algorithm's 's definition of Q%.
action-value function Q S x A x W + R. which determines
Given (Q% ke]H). we define state value functions and their backups as
(w)) = / V ()d,)))
Ví (s, w) = min max Qh a, w), aEA
(3)
Thanks to the linear MDP structure in Assumption
D it holds that
Fn.
V w) (s. (ws))
(4)
Let > 0 be a constant. We define the X-regularized least squares estimator of 0 (w) as
k-1
(w)) = (Ah
Σ o ( w), where A = Ala +
o h
(5)
7=1
0 and 07 (w) is the solution to min [0=1((0, (63), ah)) - I (5h w)) + Al 012 कं
=
((s a)), and La e gdxd is the identity matrix.
3.2 DETAILS OF LIFELONG-LSVI AND ITS THEORETICAL GUARANTEES
We define the upper confidence bound (UCB) style action-value function of Lifelong-LSVV as follows: rn(s, ()(,,,,w) ( w) + (1r) ((5,,)) + 8 [|] (1)())))))
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Lifelong-ISSV
Set: QH+1( 0, vk E [K] for episodes k = 1,..,, K do
Observe the initial state sf and the task context w"
for time-steps h H,.... 1 do
Compute 0f (w=) as in (5) using 2h+1 defined in (6)
for time-steps / = I,.... H do
Compute (5% w*) for all a E A as in (6)
Play a arg AEA Q (s a, w*) and observe s/41 and r
where 2+++1 and 0% (w) and A are defined in (5) Here, 3 an exploration factor that will be
appropriately chosen in Theorem At episode k. given w², Lifelong-LSVI first performs planning
backward in time based on past data to compute 0% (w*) in (5) using 24++1 defined (6) (Lines
5). Then, in execution, it uses 0% (w*) to compute Q s a, w* for the current state and all a E A
(Line 7 and executes the action with the highest value (Line
We show that Lifelong- -SVI achieves sublinear regret for our lifelong RL setup. The complete proof is reported in Appx. A which follows the ideas of LSVI-UCB (Jin et al. 2020).
Theorem 1. Let T = K.. Under Assumption ! there exists an absolute constant e > 0 such that for any fixed 8 (0, 0.5), if we set X 1 and cll (d+ vd Vlog(dd(T/8) in Algorithum then with probubility least 25, holds that Rx S S ( (Vids (3 dd') H3T
Before introducing our main algorithm in Section 4 we make a few remarks on the regret and number of planning calls of Lifelong-LSVI. First, Theorem limpies that for the special case studied by Wu the regret bound of Lifelong-LSSV becomes ((vmd3 H3T).. This rate optimal in terms of its dependency on as shown in Wu et al. (2021). Furthermore, this rate matches the LSVI-UCB's s regret dependencies on and H for the single-task setting (Jin et al. 2020).
al. (2021) (Example
While Lifelong-LSSV LSVI has decent regret guarantee, it requires computing 0% (w**) for all h E [H], whenever a distinct new task w arrives. Since the number of unique tasks may be as large as K, the total number of planning calls required in Lifelong-LSVI is K in the worst case.
Unfortunately, the number of planning calls of Lifelong-LSVI cannot be easily improved, because under Assumption I alone, the optimal Q-function (s, a, w) of the CMDP can be nonlinear the representation sb. As result, for any algorithm that represents its policy linearly based on both tb and Φ in general it is necessary to recompute the coefficients for every new w to be optimal. For
Lifelong-LS specifically, this nonlinear dependency shows up in 0 (w) of (s, a, w) in (6).
In the next section, we discuss how placing a completeness-style assumption, which ensures Qh a, w) can be linearly parameterized by tb, would circumvent the issue of non-linear de- pendency of the action-value functions on w, and consequently would enable computation sharing to decrease the number of planning calls OdH lo)(K)).
UCB LIFELONG VALUE DISTILLATION (UCBLVD)
In this section, we present our main algorithm, UCB Lifelong Value Distillation (UCBlvd), in Algorithm 2 Under new completeness-style assumption that we will introduce in Section I.] we show that UCBlvd shares the same regret bound as Lifelong-LLSVI but significantly reduces the number of planning calls to be logarithmic in K. In contrast to Lifelong-I_SVI which learns individual action-value function for each w UCBlvd learns a single action-value function for all E W based on (b, a, w) to enable computation sharing across tasks, which is made possible by the extra completeness-sty style assumption. In general, in order to directly extend Lifelong-LSV to only use feature (b,s, a, w) E Rdd with d' > d, we need a context- dependent dynamics structure, which would eventually increase the regret. UCBlyd maintains the same order of regret Lifelong-I.SVI
5

---

Published as a conference paper at ICLR 2023
by separating the planning into novel two-step process: 1) independent planning with &b for set of representative task contexts and 2) distilling the planned results into a multi-tase value function parameterized by t. In addition, UCBlvd runs doubling schedule to decide whether replanning is necessary, which makes the total number of planning calls logarithmic in K.
4.1 ENABLING COMPUTATION SHARING
As lifelong RL with Assumption T alone would require replanning in every episode in general (see Section 3) here we introduce new structural assumptions on v to enable computation sharing across tasks. First, we define the following class of functions
[[ min max aEA
(we, (b(s, a, w)) + Bl "|lx-))) _ .ERR E AE
where 84+ denotes the set of symmetric positive definite matrices. We now state our main completeness-style assumption.
Assumption (Completeness). For any f F and E [H], there exists a vector c/ E Rd with Hvd such that PA (f(..w)) (s. (E), (b, a, w)).
[ &
This assumption says that the backups of functions in F are captured by the feature vp with bounded parameters. The definition of F closely models the structure of nction-value function used by Lifelong-LSVI in (6), except (0, (w), ((s. a)) there is replaced by functions linear in 3b(s, a, w). We will see that the action-value function used by UCBIvd defined in the next section is contained in F. In addition, by setting B = in F and ( we see Q7 a, w) is linearly realizable by up under Assumption We note that similar notion of this assumption is mentioned in previous work for single-task settings under the name of "optimistic closure" " (Wang et al. (020).
2
Inspired by Example we now introduce the next assumption on the structure of a/. Assumption 3 (Mappings). We assume (b(s, a, w) $(s.a) a) & p(w). for some mapping p W for
RT. i.e., d' md. We assume that there is known set {w(1), w(2) ....,,(()] of n task contexts such that p(w) coefficients (ry(w)) such that p(w) Ejetn ()()) We assume Ejemale, S for all w E W and some L < cc.
((((((((()))))))) )is()))) for all w E W. That is, for any W, there exist
Note that, for dimenssammniion representations, such set (p(w always exists. We assume that this set (w()), (!?)).... w(()) is known to the algorithm
4.2 DETAILS OF UCBLVD
We define the UCB style action-value function of UCBlvd as follows:
{ rn(ssa, w) + (Eth (ass((s, ((,, ()) + 2L3 (s (ag))
@ a, w) =
The parameter En is computed by solving the convex quadratically constrained quadratic program (QCQP) in (8), which is defined on set of representative task contexts {w((), wo(2) (n)) in Assumption and state-action pairs = {(,,a) Φ(8, a) are linearly independent vectors.).
kk (()) E 10 bijj))
Σ Σ
(006) (s) (E, ab(s,,ss.. w())))
arg min
(,(o))) jein JEIm] (a.a)ED
s.t. 106) - -% (wo(i))
< 8 Vje [n]
and |1E12 S H H Vmdd
A
will show that the action-value function in (7) is an optimistic estimate of the optimal action-value function.
where (w)) and A defined in (5) In Appx. B.3,
UCBlvd also uses the linear dependency of O) on ab to reduce calls of the planning step in (8). The agent triggers replanning only when it has gathered enough new information compared to the last
update at episode k. This is measured by tracking the variations in Gram matrices { {Af] he[H] (Line for Algorithm 2). Finally, when executing the policy at episode k. the agent chooses the action according to O in Line 10

---

Published as a conference paper at ICLR 2023
Algorithm 2: UCBlvd (UCB Lifelong Value Distillation)
Set: (=+ 0, vk [K], k for episodes k = 1, .............................. K do
Observe the initial state of and the task context w²
if 3h E [H] such that log det A log det A.t > 1 then
k = k
for time-steps h H......00
. do
2 Compute En. as in (8)
for time-steps / -....,, H do Compute (s a, w²) for all A as in 77
Play oa = arg Da Q (sh, h a, wh) and observe sht and r
4.3 THEORETICAL ANALYSIS OF UCBLVD
We present our main theoretical result which shows UCBIvd achieves sublinear regret lifelong RL using sublinear number of planning calls, for any sequence of tasks. The proof is given in Appx. B
Theorem 2. Let T = KH. Under Assumptions 2 and 3) the number of planning calls in Algorithm
2 is at most dH log(1 + dx). and there exists an absolute constant >> 0 such that for any fixed in Algorithm then with
K
ō E (0, 0.,). if we set X = 1 and 3 = cll (d + (odd)/logmmdT)))
probability at least - 26, it holds that R S Ô (LV(ds + mdd H
Theorem 2 shows that UCBlvd has the same regret bound as Lifelong-LSVI in Theorem 1. but reduces the number of planning calls from K to dH log(1 + K/dA). ). As we discussed before, this is made possible by the unique QCQP- distillation step of UCBIvd in (8). If we were simply perform least-squares regression to fit (1b(s, a, w), Eh) to {(d(s, a), 0 (w())) Hejj)) for distillation,
we cannot guarantee the required optimism, because (ó(s, a). (,)() (w) computed based on finite samples can be an irregular function that cannot be modelled by ab(s, a. w).
Remark 1. If the rewards are unknown, we can adopt a slightly different completeness assumption with an extra bonus terms of sb. and then combine tools from linear bandits (Abbasi- Yadkori et al. 2011y and our proof of Theorem 2 Because reward learning affects the radius of the confidence intervals for (w)) the number of planning calls and regret would increase by factors of O(m) and (l)m) respectively, compared those in Theorem 2 See Appx. [or r details.
Remark 2. It is possible to eliminate the assumption that 1b(8,, a. w) (bs a) @ p(w). In this case, our analysis would instead require a set (w) w(2) ..... w(")) of tasks such that 1b(s, a, w) e Span(E w())) jejn)) for all (s, w) E S x A W. In Appx. [ we provide details of this relaxation, and show that this version still enjoys the same planning calls and regret as in Theorem 2
Remark 3. We can eliminate Assumptions [ and 3 and instead design a computaiio-sshaiing version of Lifelong-LSVi under a sightly different completeness assumption with a class F, whose exploration bonus is (s, a, w) [l)] A-1. This assumption naturally includes settings with linear MDP in which dynamics also change with task context, iee,, for all h E [H), it holds that PPN(-18, a, w) = (d') IT Under this assumption, a slightly modified version of Lifelong-LSVi would use Q) (g, a, w) {ru(s, a, w) + (Vt (bs,,, als,a,w) wT), H,H, +==I 1 17, 17, = =bb oh, wT), and 3 (dd).. However, Appx. we show how these new algorithm and assumption result in Ö(mdH) number of planning calls and a regret
(.), ob(s,a, a, w)) for d' unknown measures [p/ ..... Ph
(1)
Bllub(s, a, will (1))+ where 1// -( - 1h. min(maxxes A AL
Whiiee for both settings in this remark and Remark the action-value functions contain exploration bonus in terms of sb, the regret here is better by factor of / /m and this is hecause the multiplicative factor 3 here saves factor /m compared to that in Remark
7

---

Published as a conference paper at ICLR 2023
sealing with d() for settings with (b w) = Φ(s,a) @ p(w). These are worse than the
number of planning calls and regret in Theorem 2 of UCBlvd by a factor of O(m).
Remark A natural followl relaxation of Assumptioo iiis when the equality holds up to an error of
In Appx. F we show that this relaxation results in regret ① ( VmdTC + V md? (ad2)H'r H
and the same number of planning calls as that in Theorem 2 When is sufficiently small, i.e.
Ç = =O de Hmmm),, UCBlvd will still enjoy regret of the same order as that in Theorem ?
4.4 PROOF SKETCH OF THEOREM
Because the proof of planning calls' upper bound follows standard arguments in low switching cost analysis Abbasssi Yadkori al. (201T), I). in this section, we focus on the proof sketch for the regret bound. We start by introducing the high probability event & which is the foundation of our analysis:
& (w) = -00
0%
S (,, E [M] [K]
A
The following lemma highlights the importance of the carefully designed planning step in which which ensures good estimators for Vh+s without the need of bonus term 1b(s, w)ll (at) -1. This step
saves factor (m) in planning calls and regret.
Lemma 1. Let W = {w" T E [K]] U (w : j E [n]]. Under the setting of Theorem and conditioned on events (Ei(w))eeT) defined in ()) for all (s,a, w, h S x Ax W x [ [K].
holds that (Eh, (8, w)) - PA ( (s), s
As the final step in the regret analysis, we use Lemma to prove the optimistic nature of UCBIvd, i.c., Q (s, a, w²) 2 Q% (s, a, w²) for all (s, a, h, k) e S x A [H] [K]. Then following the standard
analysis of single-task LSVI-UCB we derive the regret bound in Theorem 2
4.5 EXPERIMENTS
We implemented main algorithm UCBIvd on synthetic environments and compared its perfor- mance with the warm-up algorithm Lifelong-LSVI LSVI, which is viewed as an idealized baseline ignoring the computational complexity. In all the experiments, the same setting, task sequences and feature mappings were used for both UCBIvd and Lifelong-LSVI Figure Ta depicts per-episode rewards for the main setup considered throughout the paper, and Figure Tb shows those for the setup in Remark The plots verify that Lifelong-Lo LSVI and UCBlvd statistically perform almost the same while UCBlvd uses much smaller numbers of planning calls (1000
20). We remark that Lifelong-LSVI has an overall computation complexity of OK?)), which makes it not practical for the lifelong learning setting, as planning complexity increases linearly with the number of samples. The details on the parameters of simulations are deferred to Appx. H
Per-episode reward
Per-episode reward
2.5
2
1.5
Lifelong LSVI, of planning
Litolong LSVI, of planning calls - 1000
planning -21.833
-CBBid, of planning calls - 21.08
200
400
600
800
1000
200
400
600
800
1000
Episode,
Episade, k
(a) Setting of Theorem d 5, m d'
25
(b) Setting of Remark 2 = 5, d' 10
Figure 1: UCBlvd vs Lifelong-LSSVI. The experimental results include 50 seeds.
8

---

Published as a conference paper at ICLR 2023
5 RELATED WORK
We consider the regret minimization setup of lifelong RL under the contextual MDP framework, where the agent receives tasks specified by contexts in sequence and needs to achieve a sublinear regret for any task sequence. Below, we contrast our work with related work in the literature.
Lifelong RL. Generally lifelong RL studies how to learn to solve a streaming sequence of tasks using rewards. While was originally motivated by the need of endless learning of robots (Thrun &
Mitchell 1995), historically many works on lifelong RL (Ammar et al. 2014,] Brunskill & Li 2014]] Abel et al., 2018a Sa b) Lecarpentier et al. (021) assume that the tasks are i.i.d. (similar to multi-task
RL; see below). There are works for adversaiial sequences, but most of them assume finite number of tasks (Brunskill & Lii 2013] Ammar et al. 2015| ZZhan et al., (017) or are purely empirical (Xie & Finn 2021). The work by Isele et al. (2016) uses contexts enable zero-shot learning like here. but it (as well as most works above) does not provide formal regret guarantees Brunskill & Li 20155)
and Xie & Finn (222)) assume the task identity is latent, which requires additional exploration: in this sense, their problem is harder than the setup here where the task context is revealed. Extending the setup here consider latent context an important future direction.
Contextual MDP and multi-objective RL. Our setup is closely related to the exploration problem studied in the contextual MDP literature, though contextual MDP is originally not motivated from the lifelong learning perspective. A similar mathematical problem appears in the dynamic setup of multi-objective RI. (Wu et al. 2021; AAells et al. (211)) which can be viewed as special case of contextual MDP where the context linearly determines the reward function but not the dynamics. Most contextual MDP works allow adversarial contexts and initial states, but majority of them focuses on the tabular setup (Abbasi- Yadkori & Neu, 2014] Hallak et al. 2015 Modi et al.) 2018
Modi & Tewari 2020 Levy & Mansour| [2022] Wu et al. 2022)) ), whereas
setup allows continuous states. Kakade et al. (020) Du et al. (2019) allow continuous state and action spaces, but the
former assumes planning oracle with unelear computational complexity and the latter focuses on only LQG problems. While generally contextual MDP allows both the reward and the dynamics to vary with contexts, we focus on the effects of context- mentexx-independent dynamics similar to Kakade et al.) (2020): Wu et al. (202I). In particular, the recent work of Wu et al. (202T) is the closest to ours, but they study the sample complexity in the tabular setup with linearly parameterized rewards. In view of Example|| 1 their proposed algorithm has a regret bound Ō( / /min (miifm../s)))) H K). However, they need Tinear number of planning calls. On the contrary, our algorithm, UCBIvd, allows continuous states, nonlinear context dependency, and has both sublinear regret and number of planning calls.
Multi-task RL. Another closely related line of work is multi-task RL. Compared to our setting, multi-task RL assumes that there are beforehand known finite tasks and/or they are i.i.d. samples from a fixed distribution. For example, in Yang et al.] (2020); Hessel et (201)): [Brunskill & L.] (2013); Fifty al. (202I): Zhang & Wang (2021 1): Sodhani et al. (2021). tasks are assumed to be chosen from a known finite set, and in Yang et al. (2020): Wilson et al. (2007); Brunskill & Li ); (unn et al. (00II). tasks are sampled from a fixed distribution. By contrast, our setting provides guarantees on regret and number of planning calls for adversarial task sequences.
6 DISCUSSION
In this paper, we frame lifelong RL contextual MDPs and identify new completeness-style assumption to enable provably efficient lifelong RL with linear representation. We propose UCBivd, an algorithm that simultaneously satisfies the practical need of achieving 1) sublinear regret and 2) sublinear number of planning calls for 3) any sequence of tasks and initial states. Specifically, for K task episodes of horizon H, we prove that UCBlvd has regret bound ((v(d' ( H'd) K) based on Ö(dH log( ()) number of planning calls, where d and d' are the feature dimensions of the dynamics and rewards, respectively. We believe that our results would inspire new research directions in the literature of CMDP and multi-objective RL, existing work to our knowledge does not cover the computation-sharing aspect of lifelong RL. That said, our work's 's limitations motivate further investigations in the following directions: 1) extension to more general class of MDPs, potentially tools, 2) establishing an information-thhereee
using general function prrrxximation/repreeemii lower bound on the number of planning calls/computation complexity.
Ammar et al. 2015 give regret bounds but only for linearized value difference; Brunskill & Li regret bounds only for hnite number of tasks.
2015 show

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work partially supported by DARPA grant 1210011210130 and NSF grant 2221871. Sanae Amani is partially supported by Amazon science hub fellowship.
REFERENCES
Yasin Abbasi-Yadee Yadkori and Gergely Neu. Online learning in mdps with side information. arXiv preprint 1.Xiv:1406.68111 2014.
Yasin Abbasi-Yadeee Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In International Conference on Machine Learning, pp. 10-19, PMLR, 2018a.
David Abel, Yuu Jinnai, Sophie Yue Guo, George Konidaris, and Michael Littman. Policy and value transfer lifelong reinforcement learning. In International Conference on Machine Learning, pp. 20-29, PMLR, 2018b.
Axel Abels, Diederik Roijers, Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. Dynamic weights in multi-objective deep reinforcement learning. In International Conference Machine Learning, pp. 11-20. PMLR, 2019.
Haitham Bou Ammar, Eric Eaton, Paul Ruvolo, and Matthew Taylor. Online multi-task learning for policy gradient methods. In International conference on machine learning, pp. 1206-1214. PMLR, 2014.
Haitham Bou Ammar, Rasul Tutunov, and Eric Faton. Safe policy search for lifelong reinforcement learning with sublinear regret. In International Conference Machine Learning, pp. 2361-2369. PMLR, 2015.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. In Proceedings of the Twenty-Ninth Conference on Uncertainty Artificial Intelligence, pp. 122-131, 2013.
Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning. In International conference on machine learning, pp. 316-3444 PMLR, 2014.
Emma Brunskill and Lihong Li. The online coupon-cclleecor problem and its application lifelong reinforcement learning. arXiv preprint arXiv:1506.033:: 03379, 2015.
Simon S Du, Ruosong Wang, Mengdi Wang, and Lin F Yang. Continuous control with contexts, provably. arXiv preprint arXiv: 13614, 2019.
Chris Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, and Chelsea Finn. Efficiently identifying task groupings for multi-task learning. Advances in Neural Information Processing Systems, 34, 2021.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00490 2021.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv:1502.02255 2015.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech 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-3803, 2019.
David Isele, Mohammad Rostami, and Eric Eaton. Using task features for zero-shot knowledge transfer in lifelong learning. In IJCAI, volume 16, pp. 1620-1626, 2016.
10

---

Published as a conference paper at ICLR 2023
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, 2020.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 33:15312-15325 2020.
Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual reinforcement learning: A review and perspectives. arXiv preprint S.kiv:2002..344990 2020.
Erwan Lecarpentier, David Abel, Kavosh Asadi, Yuu Jinnai, Emmanuel Rachelson, and Michael L Littman. Lipschitz lifelong reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8270-8278, 2021.
Orin Levy and Yishay Mansour. Learning efficiently function approximation for contextual mdp. arXiv preprint arXiv:2203.0099) 2022.
Aditya Modi and Ambuj Tewari. No-regret exploration in contextual reinforcement learning. In Conference on Uncertainty Artificial Intelligence, pp. 829-838. PMLR, 2020.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with continuous side information. In Algorithmic Learning Theory, pp. 597-618. PMLR, 2018.
Nicholas Roy, Ingmar Posner, Tim Barfoot, Philippe Beaudoin, Yoshua Bengio, Jeannette Bohg, Oliver Brock, Isabelle Depatie, Dieter Fox, Dan Koditschek, et al. From machine learning to robotics: Challenges and opportunities for embodied intelligence. arXiv preprint ar 2rXiv22100.553 15245, 2021.
Daniel L Silver, Qiang Yang, and Lianghao Li. Lifelong machine learning systems: Beyond learning algorithms. In 2013 AAAI spring symposium series, 2013.
Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context- based representations. In International Conference on Machine Learning, pp. 9767-9779, PMLR, 2021.
Yanchao Sun, Xiangyu Yin, and Furong Huang. Temple: Learning template of transitions for sample efficient multi-task rl. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9765-9773, 2021.
Sebastian Thrun and Tom M Mitchell. Lifelong robot learning. Robotics and autonomous systems, 15(1-2):25-46. 1995.
Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34: 14544-3--33 2021.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy, Optimism rein- forcement learning with generalized linear function approximation. In International Conference on Learning Representations, 2020.
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: a hierarchical bayesian approach. In Proceedings of the 24th international conference on Machine learning, pp. 1015-1022, 2007.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 34:13112-1331 2021.
Annie Xie and Chelsea Finn. Lifelong robotic reinforcement learning by retaining experiences. arXiv preprint arXiv:2109 00000.99...................00 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features.
In International Conference on Machine Learning, pp. 6995-7004, PMLR, 2019.

---

Published as a conference paper at ICLR 2023
Ruihan Yang. Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft
modularization. Advances Neural Information Processing Systems, 33:4767-47777, 2020.
Yusen Zhan, Haitham Bou Ammar, and Matthew E Taylor. Scalable lifelong reinforcement learning. Pattern Recognition, 72:407-418, 2017.
Chicheng Zhang and Zhi Wang. Provably efficient multi-task reinforcement learning with model transfer. Advances in Neural Information Processing Systems, 34, 2021.
12

---

Published as a conference paper at ICLR 2023
A PROOFS OF SECTION 3
To prove Theorem we will use the high probability event & defined in Lemma 3 to prove the UCB nature of Lifelong- Lisoongg-LViII LSVI in Lemma 4 which is the key to controlling the regret. We first state the following lemma that will be used the proof Lemma 3
Under the setting of Theorem 7 fixed w. there is absolute constant co independent of cg. such that for all (h, R)) E [H] [K], with probability at least 8 holds that
Lemma 2.
let cg be the constant in the definition of 3. Then, for
w))( Σ th. (Vi+220044200) w) - PP ( 053)
S Scoll (d+ Vot) VloR((es + /0),
(At)
where and op are two independent absolute constants.
Proof.
We note that ||ull2 I Vd' (Assumption
[10% (/)p I HVd (Lemma
18 and
(At) - Thus, Lemmas 19 and 21 together imply that for all (h, k))
[H] x K with
probability at least 1 - it holds that
h (V/+z(5h+4: PMIV (.
(AR)
k ( A
1 1 VBd
8 (1))
11
+ 81:222
< 4H²
log
+ d' loog(1 + 4d' /c) + dllog11 + 4Hd/c) + d2 log
+ log
2
dea
A
we let and B = cd + V VlogddT/8) then, there exists an absolute constant that is independent of cæ such that
1 1h (h-n1 (
S C(d' + + log ((cg + 1)dd
(AR)
Lemma 3. Let the setting of Theorem 7
Tholds. The event
E2(w) = (10oicu) (w() A
S <B,A(h,A) [M) [K]
(10)
holds with probability at least ô for a fixed w.
Proof.
k-1
0% (ww) - (10) 0% - (A
Σ
2 V
1++1 (8/+1:
k-1
= =(Att² -1
A
Σ
2 v (8h+1:
k-
>AAt) -1
0 (ww)
(A
-1
Σ
Φ
Vhtt (8/+1) w) - -Pa(Ve w)) w)) a4)))
r=1
92
13

---

Published as a conference paper at ICLR 2023
Thus, order to upper bound 0% (0())
we bound//qqllll and and||a=lląg separately.
A
From Lemma 18 we have
lqqillat /|ox(w))((A33 S VA 0% (1)
S HvAd.
(11)
Thanks to Lemma
for all (w, h, k), with probability at least
6, holds that
||qella:
Ph. Vik (5% w) ( w)]( (()h))))))))
S SaH (d vd)) Vlog(les 1)dd'/1))
(AR)
(12)
where co and og are two independent absolute constants. Combining and for (w, h, k), with probability least 1 5, it holds that
(0)(w)) - 0% (wm))
I sc (d+ VAlog(ddTT/8)
for some absolute constant c
w Under the setting of Theorem and conditioned on events {Ez(w)) wew defined in (TO), and with Qh computed as (6). it holds that (%, a, w) Z (%,s,, a, w) for all (s, o. w, h k) S A W H [K].
Lemma 4. Let W = (w- u²
Proof. We first note that conditioned on events {E2(w) weW [H] x [K]. holds that
h-w for all (s,a
an(s,a,w) w) + (Di(w) (7(ss,, - Pn. [ve [ w) )- - Vitzll, 10) (8,
a) + 0/ (x(w)),(s.0)) - rr (1,8,,
Ps V (1 (s,a)
-P [V2 (. (s)
Pn V
(dk(w) - (ls.)))ss)))
||0(s, (10(s)))l(Az)) (m(w)) (w)
A
s 3 (B)lo(s (1(z))
(Lemma
for any policy
Now, we prove the lemma by induction. The statement holds for H because Q Q141(-....) = Q Qu++( = 0 and thus conditioned on events (E2(w) defined in (10), for all (s, a, w. k) E
Sx Ax W [K]. we have
rn (8, w. (w), (s, $ $
14

---

Published as a conference paper at ICLR 2023
Therefore, conditioned events {Ez(w)) for all (s, k) ES x A W [K]. we have
(H, a, w) & TH (s, a, w) + (w), 0(s a)) + ( (|) = Q (s. a, w).
Now, suppose the statement holds at time-step h + 1 and consider time-step h. Conditioned on events h, 0 S as w) + (w), ((s, a) (5, w) - Pn | w) Vitzal,, w)] (s, + Bll (((()))
(E2(w)) for all (s,a, w, h,,,) k) ES x A W [M]] [K], we have
S <r,(s,, w) (w),
(x, a, w) 3 a (At)
(Induction assumption)
Therefore, conditioned on events {E2(w)) weW for all (s, w h, xx H we have
[K]
(s, w) S r,(s,,, w) + (O)) - ()((s))))((())))))))))))))))))) - (s a, w)
This completes the proof.
A.1 PROOF OF THEOREM
Let 8% = (sh, w²) Vi* (s w and ch+1 = E. [ 15 at t1 Conditioned on events
(E2(w)} wew for all as, w. h) E Ax W H [K], we have
Q, - Q (s,a, = Tr (s, w) + 0 (w)( ((.
Q7 ws + (3 (A)))
I Ph Vx+ (., w) - V (.. w) (s. + 23 (s) 11 (13)
Note that 5% s @h o w² Q (st at, w²). Thus, combining
13 Lemma and union
bound over W. we conclude that for all (h, k) E [M] x [K]. with probability at least 1 8, holds that
8 S ch+i + 1 2/3 (s5 ax) laag
Now, we complete the regret analysis
Rk
- (st, w²
K
(f w²) -VT" (sf,
(Lemma 4
K
Σ
k=1
H1
Σ
ck
23
(s a ((A))
k=
< 2H / Tog d8 + 22 2dl log(1 + K/A)
s ō X(d + dd' H3T)
The third inequality true because of the following: we observe that {ch) is martingale difference sequence satisfying | 2H. Thus, thanks Azuma-Hoeffding inequality, we have
P
$ < 2H / (lo((d
1
(14)
15

---

Published as a conference paper at ICLR 2023
In order to bound Ex=1 Σm=
note that for any / E [H]. we have
(ag)
K
1
(A
K
Pk
(A*)
(Cauchy-Schwand inequality)
h=
b=
(A
det
2K log
(15)
det
(A
2dK log
1 + dx
(16)
In inequality
[5). we used the standard argument in regret analysis linear bandits (Abbasi- Yadkori
al. 2011 Lemma 11) follows:
Σ min (Ivelle, 2 det V n+1 where V, V1
n-1
y.y.
(17)
det Vı
In inequality (16). we used Assumption and the fact that det(A) = II A((A) < (trace( (A)/d)
B PROOFS OF SECTION
We start by introducing the high probability event E,, which is the foundation of our analysis in the following lemma.
Lemma 5. Follow the setting of Theorem
The event
((w) = (lokkw) ((()))
(B, [4] [K]
(18)
A
holds with probability at least 5 for a fixed w.
Proof of Lemma is given in Appx. B.
B. PROOF OF LEMMA 5
First, we state the following lemma that will be used in the proof of Lemma 5
Lemma 6. Under the setting of Lemma 5 let cæ be constant in the definition of B. Then, for fixed w. there an absolute constant co independent of cas such that for all (h, k)) E [H] [K], with probability at least - 8 it holds that
Σ Th. (Vi+z w) PP PP w)) (5)
S Scoll (d+ Vmd) Vlog((es 1)mdd/00)
(A+)
where 6o and eg are two independent absolute constants.
Proof. We note that Tn E < (1 Hd and (A S. Thus, Lemmas 19 and 22 together imply that for all kh,
E [H] [K]. with probability least 1 it holds that
2% (Sh w) PA (3) a7)
(AA)
d
1+ 3212 Vd
1 + log
)
862E2
2 log
md log(1 + 8H 8H Umd/e) dd log
262
8
16

---

Published as a conference paper at ICLR 2023
If we let dH and 3 ca(d Vmd) / log(dT/6) then, there exists an absolute constant C > 0 that is independent of Os such that
hh Vh-1(sh+1: -
I C(md + H log ((cs + 1)mdT/60 /8).
(A%)
Now, begin the formal proof of Lemma 5
k-1
(w) (w) (20) - (AR)
Φ / h+1 (,,, w)
k-1
- -Att) -1
A (1)
Σ
Φ V (sh+1:
(Att)
-1 0 (h())
(Ah) -1
Σ Φ V/
(074110 - ( w)
92
0% 0/(ww)
Thus, in order upper bound 0% (w)
we bound //uld// and separately.
A
From Lemma 18 we have
|| ll 2|10t(w)) | S VA (x /V
S HVAd.
(19)
Thanks to Lemma for all (we h, k)), with probability at least 5, it holds that
k-
Σ Φ (Viz (5 Pa Ph ()) (5) 03)
12 A S
(AA)
S Ho (d Vmm) Vlog((es + 1)mdT
(20)
where cy and C3 are two independent absolute constants.
Combining (19 and (00). for all (h, k) E [M]] x [K]. with probability at least - 6, it holds that
0 - (w)
seH (d+ Vmd) v AllogmdTT/ 18)
A
for some absolute constant >
B.2 PROOF OF LEMMA
Thanks to Assumption and conditioned events (Ei wew one set of solution for
8 is
{ oo% (w0(1)
and En Vh+1 with corresponding zero optimal objective value. Therefore, holds jEin]
that
(6) 0 -$(5.a)) = (Ei. &b (s.a,)l)))) A(i (n) D.
(21)
17

---

Published as a conference paper at ICLR 2023
Let a())) be the i-th element D and be the coefficients such that
((8,a)= E
((s
iE|d
For any triple (s, E x A [n], we have
th, 2b as, woli)) = En ((, 2 p p (w(11)
Σ (((,,)) (5()), (s()) ,a()) @ p (w)(11)
En
EE|4]
Σ
4(s, a)
Eh (8(0) a(
(0 ((()) m(11)
(Assumption
El|
Σ xE[d]
A(s,a) a)
(a1(5) ①
(s (a00))))
(Eqn. 21
kG) (((sa))
0
(22)
For any (s,a,w) E x A W, it holds that
Ph V/l (
(s,a) (0%(w)) ((s,
(Eqn. (4)
vit
ch
ab(s. a, w)
(Assumption 2
Σ (j(w)
Vita 5h 2b (s, a, m(())
(Assumption 3
jE(m]
Σ
ej (u:)
V (120)))) (s)
(Assumption 2
jE[m]
Σ (w)
00% (w)))) ob(s.0)).
(23)
jcmm]
18

---

Published as a conference paper at ICLR 2023
Finally, conditioned events (Ei(w)) weW for all E W [ X [K], it holds that
Eh (()) Ph (V (1, (..2)) ())
(Ehs Shr (h,,bsss, an)) (o)(w),, ((((:)))((s,,)) (((s
Eg cy(w) (fhn (s, w (s, (3,a, - 0% (w)))) (868.1))
SE|m]
(Assumption 3 and Eqn. 23
<
Σ (y(w)
((thn
(t) (in 2b (s, wll)))
0% k())
$ al .0(s,a)
5E|D]
Σ
(2x) ( (o/(1) 0% (w())) ((s
+ Σ (ww)] (0t (mol5)) 0% (wis)) (p(s,
jE(n
jE
Σ (w)
k(i) 0% (wli)) (B(8,a))
+ Σ cg(w) (0% (woli) - 0% (w)(1)) (b 8, a)
jE/m]
5E(n]
(Eqn. (2)
2L3 ( ((())))))))
(Lemma
B.3 PROOF OF OPTIMISTIC NATURE OF UCBLVD
Lemma 7. Let W (w" E [K]) U (wii) j [m]]- Under the setting of Theorem 2 and conditioned on events {Ei(w) wew defined in (9) and with Qi computed as in 7 it holds that
(%(s,,, 2 (%,8,, w) for all (s, a, w. h k) A
[K].
Proof. We first note that conditioned on events [E[(w) wee for all (, [H] x [K]. it holds that
Th ra(s, w) + (hh (5, (T(s,, Vo () Vi w) (s,a)
Sh (5h.6((s,,.)) r,( Ph [v ( (s,a)
ra(s,a, w)
Ehr (s, a,
Phn [v [ ( a)
s 22B al (a
(Lemma I
for any policy π.
Now, we prove the lemma by induction. The statement holds for H because Qitz(.. = (...) = and thus conditioned events {E1 (w)) New defined in (9), for all (8, (8,a, k) E Sx Ax Wx [K], we have
a Str. a,)
Qi, I 625
19

---

Published as a conference paper at ICLR 2023
Therefore, conditioned events {E (E((w) weW for all (s,a, 8 xxxxxA Ax W x [K], we have
Qn(8, w) & as ) + Sen, ()) +2.3) (1(a)))))
rH(s,a,w) + ( ((,,, 2 (2)
(s,
where the first equality follows from the fact that (s, Now, suppose the statement holds at time-step h and consider time-step h. Conditioned events { (w)) for all
(s, w. h, E x A W H x [K], we have
0 S rn(s,a,w)+ +
En. (s,
k
Q%(3,a, w) - PA [ [itz(,, w) - Vi+z((, wi) (s, -23)1066.0)1((4))
Srn(s,a,w) + (5s, (, w) 2T 0(8 a))((
(Induction assumption)
Therefore, conditioned on events {E((w) weW, for all (s, x H x [K] we have
Qh(s, w) S an +
En (Eh
ck wb(s w) +223||0(s,
a,
2 (Em.)()...)) +2L3)
(s, a, w),
where the first equality follows from the fact that (7 a, w) 2 This completes the proof.
B.4 PROOF THEOREM 2
First, we bound the number times Algorithm 2 updates Eht i.c., number of planning calls. Let P be the total number of updates and kp be the episode at which, the agent did replanning for the p-th
time. Note that det A = Ad and det A I traco(A (aacolA////a /a)d = ( + K d
and consequently:
det A/
P
det A
K d)
II
det A
det A kp-1
and therefore
det A
P
det A
K
dh
II
<
1
(24)
det A
det A
Rp-1
dd
Since 1 < det A
Kp for all E [P]. we can deduce from 24 that
det A
det Jt det A
3h E [M]]
such that
happens for at most dH log
number of episodes & E [K]. This concludes that the number
dx
of planing calls in UCBlvd is dH log [
K dx
20

---

Published as a conference paper at ICLR 2023
Now, prove the regret bound.
Let 5% (5 w²) V/ (sh, wn) and sh+1 8 (ottllsh f af +1 Conditioned on events {E1 (w)) new for all (s, a, w, k) S Ax
W x [H] [K], we have
(h a, w) Q (s, a, w) rr (,, w) + ( Eh pb, a, a.)) 27 (s, w) + 2LB o
2 1 w)l((a))-
- Ph (1+ Vitil,, w) (5, + 4L33|0(s, (
(25)
Note that o% s (5 at, w² - Q (s), ax, w² Thus, combining 225 Lemma and union
bound over W, we conclude that for all (h, k) E [H] x [K], with probability at least 1 - 8, it holds that gives
t S Sh+ + o + 4LS ( at) (A))-1
Note that for any positive semi-definite matrices A, B, and C such that A = B + C, we have;
det(A) 2 det(B), det(A) 2 det(C),
(26)
and for any x + 0 ((Abbasi-Yadee Yadkori et 2011 Lemm. 12)):
|
(A)
| [ det(A) ||x| 2
and
(27)
|
B
2
det(B)
det
Now, we complete the regret analysis following similar steps as those of Theorem
proof:
RK
Σ Vi (s w² VT (st, w*)
( w*) -VTT (st,
(Lemma
k=1
H
K
ch
4LB
Φ d ahh) (AS)
k= hm1
km 1 1=1
K H
K
det A det A
+ 4LB
Φ att)
(Eqn. 27
(At)
k= 1=
1=11
< 2H / T Togg(dT//) 83 2dK log(1 + K/A)
< Ô +
B.5 DISCUSSION ON THE TIME COMPLEXITY OF UCBLVD AND LIFELONG-LSVI
In what follows, we clarify on how the time complexity of UCBlvd compares that of Lifelong
LSVI. When we compute (A -1
by the Sherman-Morrison formula, the computational complexity
of Lifelong-LSVI is dominated by Line 5 in computing max Q h+ (1 a) for all T E [k]. This takes (A) per step, which gives total runtime (d)) In UCBlvd, every planning call takes (md A|K + mdd"), where the second term is the time-complexity of thE convex QCQP with m constraints and 2md variables. This gives total runtime of Ó (mH((dd))A) |A|K + m))
Therefore, UCBlvd enjoys a smaller time complexity by a factor of K compared to that of Lifelong- LSVI, which is significant reduction in practical scenarios where K >> d' md.
21

---

Published as a conference paper at ICLR 2023
Algorithm 3: UCBlvd with Unknown Rewards
Set: (++1( vk [K]. k for episodes & = 1,.... K do
Observe the initial state sf and the task context w²
if 3h E [H] such that det A det An
or det A
> then
det A
k k=
for time-steps It H,..., do kk Compute En. in 30
for time-steps / L,..., H do
Compute Q a, w²) for all A as 28
Play ot arg max ( a, wh) and observe sht1 and r
C DETAILS OF REMARK T UCBLND WITH UNKNOWN REWARDS
In order for our analysis to go through, we need slightly different completeness assumption as below:
Assumption 4. Given feature maps Φ S AxA= + R and sb Ax - R.d consider funntiinn
class
F f: f:f(s.w) = min max acA
(2, (s, Bl| a)la + ()) a, wi)la= 3
.EER A AES L A B 0,
Then for any E F, and h E [H], there exists vector E/ E Rd with | s Hvd such that
Ph [f. (8 (5/ (b, (s),
C.I OVERVIEW
Let Tb;,, = 1b( ah, w²). UCBlvd with unknown rewards works with the following action-value functions:
{
()(
En, Vi. w) + 811 + B1] w)
w) a. 1 (28)
where
-1 -ik-1
k-1
A
Σ Wh.rk
and 1 = =Amma + Σ
4b
(29)
and
((DL)) (o1))(((,a))
2
Eno (0
arg min Σ
c5 (s, w
(30)
jE(n)
s. (o sem jE(m) (Sta)D
s.t. g( 0% (w))))
3, Vj [n]
and ||E||, S H HV md,
D {(s,a) $(8,a) a) are d linearly independent vectors.). }. and 0 (w) and A defined in 5
22

---

Published as a conference paper at ICLR 2023
We note that compared action-value function defined in (28) involves extra term
The (b + a)w) ( This term is in fact an upper bound on (s w). Specif-
ically, from Theorem in Abbasi- Yadkori al. 2011). know that for 3 v Amdd, it holds that
7h
x B, v(h, k) [M] x [K].
(31)
Theorem 3. Let T KH. Under Assumptions and 4
the number of planning calls in Algorithm
3 is at most dH log (
K dx
+ mdH log (1 mdx and there exists an absolute constant e >> O
such that for any fixed ò E (0, 0.5), we set 1, 3 cH (md) /log(mdT] /0) and 3 vmn in Algorithm 3 then with probability at least 1 26, holds that
Rx S 22H 22H 4H (LB + K/A) + Bv 2md + K/A)
s 5ō <O(LMPPPHPP
C.2 NECESSARY ANALYSIS FOR THE PROOF OF THEOREM 3
Lemma 8. Let be constant in the definition of B. Then, under Assumptions 7 and 4 for fixed w. there an absolute constant cy independent of ca, such that for all (h, k)) probability at least - 8 it holds that
with
Σ S/. (Vitz w) PAIV (s 03))
S comdH / |lo((cs + 1)mdT//0
(AA)
where and eg are two independent absolute constants.
mh + Eh S Hvmd + K/A and (At) -11 S 1 and ( A
(
Proof. We note that
S }
Thus, Lemmas
19 and 23 together imply that for all (h, k) [H] [K], with probability at least
1 - 8 it holds that
Σ
V
( w) - PAlVA ( w((h.
(AR)-
d
k x X
1+32L238 Vd Xe²
I 2
log
+ md + 8H /md/c) + dl log
2
1 + 8,32 /md
log 111 +
2
+m² 2d log
Xe
If we e dH that is independent of cæ such that
& and 8 = co (mdd) H / Jog(mdT/88) then, there exists an absolute constant C' > 0
1
( (
$ <C( log ((es + 1)m
(AR)-
Lemma 9. Under Assumptions i and 4
if we let 3 = cmdH HallHH/Alogmmmann /Alog(mdT/o) with an absolute
constant c 0, then the event
Eg(w) 0% (w) (m()
3, A(h,k) k) E [H] [K]
(32)
A
holds with probability at least 8 for a fixed w.
23

---

Published as a conference paper at ICLR 2023
Proof. The proof follows the same steps as those of Lemma 5 except that it uses Lemma instead of Lemma due to different structure of action-value functions 2% in this section.
Lemma 10. Let W fw" E [K]] U (wli) : E [n]]}- Under the setting of Theorem and conditioned on events {Ez(w)) wEW defined in . all (8, a, w. h, E Ax W H []. it holds that
K t Ch
Ph (., (s)
<2L3|10(s.
Proof. The proof follows the exact same steps as those of Lemma Is proof.
Lemma 11. Let W {w- T E [K]] U (wl)) : E [n]]. Under the setting of Theorem and
conditioned events (Eg(w)) wew defined in (32), and with Qh computed in 28 it holds that (%, 2 (s,
a, w) for all (s,0, w, h,k) E S A W [H] x [K].
w. h Proof. We first note that conditioned on events {E((w)) wew for all (8, w, [H] x [K], it holds that
x
i + Enz (bs (e) (7, w. - Ph (v++(,, Vh+i (- w) (8,a)
< ih + k
Ens b(s,,,))) an(s,a, Pn Vv (,, w)) (s
Eh ub(s,, a, w) - PPh vR h++1 (., (. as
+ 3/1lbbs, (rrlaaawl((( w)l((xt)
(Eqn. 31
s <2BBllb(ss ()l(()))))))))))))))))))))))))
+ B|leb(8, w/) (xt))
(Lemma 10
for any policy
Now, prove the lemma by induction. The statement holds for H because Q Qu41(1...)
Qu = 0 and thus conditioned events (Eg(w)) defined in 32). for all (8, w,k)
S x Ax W [K]. we have
( n + ck ((,. Q,((,,, w) <200)1(().0)1(())) + B|| ( will
(33)
Therefore, conditioned on events (Ea(w)) for all (s, E
S Ax W [K] we have
(,(,,,, < i En a(s,a,w)
(A$) (a (()()))))(((())==>)))))))))))))) + +2L3)
+1 w) (a:))
nh + *k En ((s,a,
+228||o(s a) (1)))))) (
+ Bl| al (att)
w))
(s,a,,,
where the first equality follows from the fact that Q (s, a, w) 2 0. Now, suppose the statement holds at time-step h 1 and consider time-step h. Conditioned events (Es(w))=ew for all
24

---

Published as a conference paper at ICLR 2023
(s, w. h, k) ES A W H x [K], we have
0 5 पt + Ex. (5, a, w) - (7, wi Ph [hiill,w)- - Vit1,, w) (3,
+ 2L a1) (A+) (a=) + an,,,w)ll (1)(x())))))((x))
< nt E (ss (s, + 2L3 0 ()l(())) B| (s,,, (a:)
(Induction assumption)
Therefore, conditioned on events (Ez(w)) wew for all E x [K] we have
(s, - ?h + Ex ((),
2 + B|| a, (
{ nt En (b
+2L3||0(s, ) ((x)) 3 (x:) (x:)
Q (s,
a, w)
where the first equality follows from the fact that Q7, a, w) 2 0. This completes the proof.
C.3 PROOF OF THEOREM 3
&
First, we bound the number times Algorithm 3 updates En. i.e., number of planning calls. Let be the total number of policy updates and kn be the episode the agent did replanning for the p-th
time. Note that det A = 2d and det A < trace(A /a)a - (A
K d
and consequently:
del A
del A
K
II
$
1
det A
p=1 det Akr
d)
and therefore
det Al
H P
det A Mpp
K
dl
5
1
(34)
det A
det A R
dl
h=1 p=l
We similarly have
H det A K
H
det A kp
mdH
K
II
(35)
h=1 det An
h= p=1 det A,
mdd
Since 1 < det A by
for all [P], we can deduce from
34 and 35 that
pp-1
Fp-1
3h [H]] such that e det A
det A
(36)
det A
det A
happens for at most dH log (1+ K dx
+ mdH log
1
mdx number of episodes k E [K]
This concludes that number of planning calls in Algorithm is at most dH HHlog (1
mdH log 1 max
Now, we prove the regret bound. Let 8%
V (o w²) and sh (h 1st, at/ 8h-1- Conditioned on events (EIww) for all (s, w. h, k) ESxAx
V w*)
25

---

Published as a conference paper at ICLR 2023
W x [H] [K], we have
Qh(s, w) Q (8,a, w) = ( i + En, ((8,,,, w)) Q ( (l) + 3 15(8, a w) (at)
S Ph Vi (.) V w) (8, + (L3) + 20]1 a w w)llab)
(37)
Note that of s @ , of, w²) Q (sh att w²). Thus, combining 37 Lemma and union bound over W. we conclude that for all (h, k) E [H] x [K], with probability at least 1 8, holds that gives
h S ch+1 + 8h + 4L3 ((sh att)
+ 228/ 2b ab w*t
(Af)-1
(af)-1
Now, we complete the regret analysis following similar steps as those of Theorem proof:
K
RK
Vitssi w - Vi=" (sf, w
K
(s w²) - (st w*
(Lemma IT
k
k=1
K
H
K H
K
ch
4LB
Φ S a
+ 2,3
( & wt>l
(A%)
(s.)
k= h=1
1=1
A= hm1
det A det A
det A
4LB
s ( a
23
ub( ais wot)
(a+)
(nh)
h=1
del An
(Eqn. 27
2H 2HH T - (LB 2dBoodlog + Bv 2md log(1 + K/Ai
2 5 (LVAM2P@HTT))
D DETAILS OF REMARK 2 RELAXATION OF ASSUMPTION 3
In this section, we replace Assumption 3 with the following assumption:
Assumption 5. There is known set (w(11, (2))).... ...,, ....,,((m)) of S d' tasks such that ab(s, a, w)
Span { (b((s,a, a, w setm) for all (s, a, w) SS Ax W. This implies that for any (s, a,a.) w)
S Ax W. there exist coefficients (c, w) w)}jei)) such that
(b(s, a, w) Σ a, w.a,w(l))
(38)
jE(n]
Moreover, Eyemml w)l < for all (8, ES
Define the concatenated mapping + a(s, w) = [ (b, a, w) T For any (s. : w) are + d' linearly independent vectors. }.
S
x
A
X
W E
Rd+d' such that
w
W,
define D(w)
Given Assumption 5 we mod-
26

---

Published as a conference paper at ICLR 2023
Algorithm 4: Modified UCBlvd
Set: (++1(- vk [K] k =1 for episodes & = ...... K do
Observe the initial state sf and the task context w².
3h E (H) such that det A det A
> then
k = k for time-steps h = 1 do
kk Compute En. as in (39
for time-steps / l,..., H.HHHe do
Compute (5/, a, w²) for all A as in
Play of arg DAA Q (s a, w²) and observe s/t11 and r
ify the planning step of UCBlvd to the following:
2
En. (0x(0)
k { k())
Σ Σ
(00))
- - &, (s.
arg min {
JEim]
set jE(n] ((wis))((s)))
(39)
s.t. ( 0% (10621)
S B, Vj [n] and ||El22 S H H.d.
A
* is now computed as defined in The only change we make in Algorithm 2 is in Line 9 in which &
(39). We present this modification in Algorithm for completeness.
and [ the number or planning calls in Algorithmm is at most dH log (1 (1+ ) and there exists an absolute constant >> O such that for
Theorem 4. Let T = H.. Under Assumptions
any fixed& 8 E (0, 0.5), if we set À = 1 and 3 cH (d+va) /Alog(ddT//8) Algorithm then with probability at least 1 28, it holds that
RK < 2H Tlog(d (TT SHLB 2dk log(K)= S Ô (LV (d' H
(40)
The only difference is the proof of Lemma] [ which we clarify in the proof of following lemma.
Proof of Theorem 4 follows exactly the steps those of Theorem
2
and if we ler B = cH ( Vd V /llo with an absolute constant > 0, then for all (8, a, w. h, k) E Ax W
Lemma 12. Let W = {wo-
E [K]] U {wii) j E [n]]- Under Assumptions
H x [K] with probability at least 1 5, holds that
( (nn th,
Pn 1/ Vy+t6..w)) (s, ()))(()
Proof. We let (,)
be the ithh element of D(w) and for any triple (s, w) E Sx W. we let (d(s,, w))ie(ata)
(T. (w)
(,(s,,,w) w) (s,a) a) E D(w)) be the coefficients such that }
())
Σ w(),a,,)
sEld-d']
which implies that
((s, Σ d(s,,,,w and ()), Σ d(s,,,,)b,(w)) (41) sEld+d']
vEld+d'
27

---

Published as a conference paper at ICLR 2023
Thanks to Assumption
2
and conditioned on events {&1 (Ei) weW> set of solution for 39 is
@t (wo(i)
with corresponding zero optimal objective value. Therefore, holds and En JE(n]
that
R(1)
th vb (w))))
On 0 =
v(i,)) E [d d") x [r]].
(42)
Moreover, for any triple (8, a) E S A [n], we have
ch 2b (,, (s,a,w(1)
Σ &f (s,a, wl)) (
Sh. (5h
(wol))
(Eqn. 441
El|++)
Σ & (s,a,
( (%% .0.)
(Eqn. 42
sEld+ay
= (0%))) 4(1
(((,)))))
(43)
For any a) E x Ax W. it holds that
Ph Vi Vitt( (.. w)] (s,a) (w). ((ssa))
(Eqn. 44
(b(ss, Ex V
(Assumption
Σ a, w)
En Eh 2t (s.a, wlll))
(Eqn. (38)
jE(m)
Σ a, w)Ph viti (, (s)
(Assumption 2
jE(m]
w) (0h (w))) (5(s.a))
= Σ
a,
(44)
jE(n]
Finally, conditioned on events holds that
(E1 (w)) weew, for all
E Sx W H X [K], it
the (bs a,,,a,,, w) Pn w)] ())c)
(45)
(e, -
(B)(w), (b(,,)))
Σ (s(s,a,w) ((th (s, ss,a, w(l)))
o (wlli)) (b(s..)) 2(s..a)
(Eqns. (38 and 23
JElm]
Σ cy(s,a,w) ( ub (s. (s, mol1))
ACi)
h
dE|m]
(8% 0% *k (wi))) ($(5,a)
+ Σ a,), ( (0) (wli)) 0% (wo61) (b(s,)))
Σ a,
jEIn]
Σ a))
(oh()) - 0% (w)()) (5(5, a))
Σ as,,,, w) 00% (wol))
0 (w()3) (5((,a)))
SE|m]
jE(m)
(Eqn. (2
< 22L (0,3)10(8,00 ((s,a)))((3))
(Lemma
28

---

Published as a conference paper at ICLR 2023
Algorithm 5: Standard Lifelong-LSVV with Computation Sharing
Set: (++
vk [K]. k for episodes & = 1, .......... K do
Observe the initial state of and the task context w².
if 3 E [H] such that det A det A,
then
k
for time-steps h H 1 do
Compute Compute v as in (49)
for time-steps h = 1,..., H do Compute (5%, a, w²) for all A as in 48
Play a arg max Q (s a, w*) and observe s and r
10
E DETAILS REMARK
In this section, we only rely on the following two assumptions:
Assumption 6. Given a feature map sb S x A W Rd", consider function class
f: f(s = min max { (1,, (1, + 3 al) .)" H
{ uE R .320, E S
F f
(46)
Then for any F and e [H], there exists vector v/ E Rd with 1// S Hvd such that
Pn [f,,, w)] (s, a) = (ub(s, w), w/))
(47)
Moreover. for every h E [H], there exists vector nn such that rn w) (m,, (s, w))
Assumption 7. Without loss of generality, (sss,, a, w)ll, I for all (s, S A W, and ||mxll S dd' for all E [H]
E. OVERVIEW
Let T, = ( aj, w*. Standard Lifelong-LSVI with computation sharing works with the follow- ing action-value functions:
(h(s,,, ((m((s.,,,)) + (1/h ((s,,, + al }
(48)
where
-1k-1
A
Σ 1b
min
max
( w²), H and A Al
Σ 4b 1
aEA
(49)
Theorem 5. Let K H. Under Assumptions 0 Hand? 7
the number of planning calls in most (1+ 2xx and there exists absolute constant such that for any fixed 8 (0,0.5), if
d' log
K.
we set and / cd' H (Iog(d'T/8) Algorithm then with probability at least 26, holds that
Rx & 2H /Tog + 4H3 Kog 2o <0(VV'HOO)
29

---

Published as a conference paper at ICLR 2023
E.2
NECESSARY ANALYSIS FOR THE PROOF OF THEOREM 5
Thanks to Assumption 6 we have
Ph V (itt(..w) w)] (s,a) (s, = =(vi ((s,,,))
(50)
where vh = 1/ 1++
Lemma 13. Let cg be constant in the definition of 3. Then, under Assumption there is absolute constant co independent of ca, such that for all (h, k) E [H] x [K], with probability at least
1 ô it holds that
vh. (Vi-2(8h42,, w²) - (0 ((sh)
S cod' H1 H log((cs + 1)d
(A%)
where on and ep are independent absolute constants.
Proof. We note that 7 1 I (1 H) H d' and
A
S - Thus, Lemmas 19 and 24
together imply that for all (h, E [H] x [K]. with probability at least 1 - it holds that
Th Vi+tishhir
w²) PF w [[5 (Kh
(At)-
)
< 2H²
+ A log
+ d' log(1 + 8H /H d²² log
321222203 V Ae²
+ log
1 8 +
82.22
2
X
and = ca(dd + V H / /log(d /5). then, there exists an absolute constant C' that is independent of c3 such that
we let = dH
I.
2
1 w² PA (v 1441 w (. )0 (7) Ph
I CC(d + H ((es + 1))
(A:)
Lemma 14. Under Assumptions constant c > 0, then the event
6 and 7 if we let 3 ed' H /Olog((///) with absolute
E4 E1 (118
S3, (( [K]]
(51)
holds with probability at least 1- 6.
Proof.
2 1/h = 2t/
An k
Σ
4 V bk
(8) (s w²)
-xhh) (xh
-1
Σ
w V V (sh+1, w²)
=
-1
kー Σ
>
A
An
2b
( w²) - -P w [65 a71
(Eqn. 50
30

---

Published as a conference paper at ICLR 2023
Thus, order to upper bound
1 x An we bound /| xs. and q2ll K separately.
From Assumption
we have
|quilla - (xt) s
v | SHVA.
(52)
Thanks to Lemma 13 for all (h, E [H] x [K]. with probability at least
6, holds that
Σ 2h (Vi+z (1 (":""/))="""">""""""")))"">))" Pr PP w (15 ((sh) a
|| At
cod' H S log((es + 1)d
(AR)
(53)
where co and og are two independent absolute constants.
Combining (22) and 53 for (h, k) [H] x [K]. with probability at least holds that
1 1 2 x
S cd' H HaHHHAAoo AloggddT//)
for some absolute constant >
Lemma 15. Let the setting of Lemma 14 holds. Conditioned events & defined in (51). and with Qh computed as in (48). it holds that Q (s,a,, 2 Qī a,(s,,,)) for all (s, w, h, k)
S x A W [H] x [K].
Proof. We first note that conditioned on the event & for (s, a, w. k) it holds that
(K),
Th 1a a, w) + Wh (s, a, a)) - QT w) - Ph w) (x+ (s.a)
rn(s,a, + (1 (8, a, un) rn(s, a,), Pn V V (,, w)] (s)
10,, w)) -Pr, Fn 1 V ())
( p u 1b( a,
ww) w)){
< t wi A: |1 (1, (at)
< B|| a, will (at)
(Lemma 14
for any policy
Now, we prove the lemma by induction. The statement holds for because Q Qi++((....)) O1 = and thus conditioned on the event E,, defined in 5T). for (8, a, wr,k) A [K], we have
rh(s,a,w) + (ui (s, a,), (i, B1|bb(s a, will (at))
Therefore, conditioned on the event E,, for all k) x [K]. we have
(8( rn(s,,, w) (ui, (). ( -::)
rm((s,, + 1588, w)) B|lv((s all Q,,,s,,,
31

---

Published as a conference paper at ICLR 2023
where the first equality follows from the fact that (ir a, w) 2 O. Now, suppose the statement holds at time-step h + and consider time-step h. Conditioned on events ε,, for all (s, a, w, h. k) E
S x Ax W [H] x [K], we have
0 S (s) w) + ph (s, w)) (,(s,,ww) - Ph Vitzl,, w) - Vitz(,, (s,a) + B)| a, a.
< <ma(s,,,w) + p (b, w)) Qh(s,, + + w) (x:)
(Induction assumption)
Therefore, conditioned on events ε,, for all k) W [M] x [K], we have (s, w) (s, w)) (1h ()s,,,,)) | ($s a, w) (A:)
{
}
rn(s,a,w)+ + (1 (1),)))) + (1, (x2) {
(s,a,,, w).
where the first equality follows from the fact that Q7 (s, w) 2 0. This completes the proof.
E.3 PROOF OF THEOREM 5
First, we bound the number of times Algorithm 5 uudates E Let P be the total number of updates and kp be the episode at which, the agent did replanning for the p-th time. Note that det A = A and det An I (race(An)
K /d'' < (* d'
K
d'
and consequently:
det K h det A
det An
K d'>
S
1
Rp det A
and therefore
det An II h=1 det Ån
H
K
H P
det
A kp
K
d'H
1 +
(54)
Kp-1 det
A
d'A
A=1 pm
Since 1 < det A det A
for all p [P], we can deduce from 54 that
such that e << det A
3h E [H]
det A
happens for at most H log 1
K Øx
number of episodes E [K]. This concludes that number of
planning calls in Algorithm is at most d' H log (1 +
K d'x
Now, we prove the regret bound. Let 5 Vh w V (st, w²) and shtz E bh 1st of}
1
5k Conditioned on Es, for all w. A [H] x [K].
we have
al(,,, Q (s,a, w) ra(s, w) (0 b(s, - Q (,,a,w) + 3 (1] as
S Fn Vi+t(..w) (. (s, 23/1 23)10(s.a..)lll))>
(55)
32

---

Published as a conference paper at ICLR 2023
Note that 5x < 2 (5 of w*)
2% (s 0% w* Thus, (55) and Lemma 14 imply that for all
kh, E [H] x [K] holds that
6% $ sh+1 + 5% sbsh ah w²)) ((a))
Now, we complete the regret analysis following similar steps as those of Theorem [ proof:
Rs=
Σ ( w²) VI (of,w*)
V (st w0th Vi (st, w²))
(Lemma [5]
k=1
K
<b( ans wt>/| (x:)
Sh 23
1=
k=
det A
23
xb (1 ans w/ (A%))
(Eqn. (7
det A
k=1k=1
$ 2H / log(d'T (5 4H 2xd K log(1 K/A)
2 Xdd' ( HOT
DETAILS OF REMARKE 4: A MISSPECIFIED SETTING
We first present a definition for an approximate completeness model. Assumption (G-Approximate Completeness). Given feature maps & : A - Rd and up. x A W + IRd' in Assumption 1 consider the function class
f f0. = min {
max aEA
(w, ((s, w)) + (1) .)" H E Rd A A 4.880
For any f F and h E [H] there exists a vector Eh E Rd with [ s Hydd' such that for all (8,a, ASXAx
Ph [f(., w)] (s, (Eh, (s,,a, SC. Theorem 6. Let T KH. Under Assumptions
and the number of planning calls in Algorithm 2 is at most dH log(1 + dx). and there exists an absolute constant c. >> O such that for any fixed 8 (0, 0.5), we set X and = cH + Vmd) loo(mmm) / in Algorithmm 2 then with probability at least 26, it holds that
K.
(VVnTT' + (dd md2 H3T
Rx S
F.1 NECESSARY ANALYSIS FOR THE PROOF OF THEOREM 6
Let (a0))a1)) be the i-th element of D and (c((s,a) be the coefficients such that
Φ(s, a) = Σ ((ss, (s((), (()))
dEId
Then, Tag is positive constant such that Eieja (s, Tup for all (s, E S A.
33

---

Published as a conference paper at ICLR 2023
Lemma 16. Let W fw" T E [K]] U (wl)) : E [n]}} Under the setting of Theorem 6 and
conditioned on events (EI defined (). for all (s,a, w, h) E S Ax W H [K]. it holds that
Sh. (b, a, w))
PhIV (, (, a) s (2T + L Vdd + 21,3 ( a) (A:)())) 1.
Proof. Thanks to Assumption 8 and conditioned on events { (Ei(w) wew one set of feasible parame-
ters for (8) is 0 (w(01)
Vh+1 such that
and &n
jE(N]
( k() 0 ((s.)))
Eh. 1b (s, (ol S <VVmd, (s. E [m] x D.
(56)
For any triple (s, a) E x A [n]. we have
En. 4b (s. (.l.
ck
En Φ a) o (wlii)
Σ a() (50)
(s0) al) 8 p (wo6i))
iE(d)
Eth 26 (s10), aa(1) 20011)
(((s,)
(Assumption
iE|d] [
s v mdc
a) + Σ ((s
(0h0).00 .0 ..((s)).)))
(Eqn. (56)
iE(d
(E(d]
< Lo mdl
0 H(S)
(((5, ((s..))
=
ch ab (s, (llw))) 2 Lov (
0h (()) .((..))) .)) Therefore, for any
Similarly, holds that
(s, (), E S x Ax [n]] it holds that
( (hn 2b (s,a, (aiwwi))))
(0 AC) <b(e)a)) s LoV
(57)
For any (s, a, w) E x A x W. it holds that
Ph Vi+z(..w) w)
(s, a) = ( (w)) (w), o(s,a))
(Eqn. (4)
$ < +
En $5ss,,,0) w.)))
Vi++
(Assumption
= < Σ cj(w)=
En
Vhin
ab (s,a, m(b))
(Assumption
jE/ml
S
1+ Σ cy(2))
Σ
(w)PP
Vita (..200))
())
JE/m]
JE(n]
(Assumption 8)
Σ c)(w) 0% (woli) 08(8,00)
$ 2LC +
(Assumption
JE(n]
Similarly, holds that Pn [ ( (., w) (s. 2 -21 EyE(m) (w()) (0) (106)) ((5,a)
Therefore, for any (s, w) S A x W, it holds that
34

---

Published as a conference paper at ICLR 2023
Pa V (., w) (0, - Σ ()(1) (0% 0% (w)))) (((s,a)
(
(58)
sE(m]
Finally, conditioned on events wwew for all xx W H x [K]. holds that
E
< ch Eni (s, a, w)) - Phh [Vitz( w)] (s, (s,a)
Σ cg(w)) (( 2b (s, (oll))
@ (wrlt) (b(5.a)
S $2LÇ+ +
jE(m)
(Assumption B and Eqn. (58)
((fin Φb (s, w(l1)
2LLÇ
+
Σ cy(wv)
On (iss.a))
k())
jE(m)
+ Σ
Cy (w)
(0%(0) -0% (wol) 01)
+ Σ (((w) (0% (w06))) 0% (wot)) (b(),a)
sE(M)
jE
< (2L + Lsp mdls +
Σ ((w))
(0%
0% (wii) sple..a))
+
Σ ()(w) (0% (wol)1) 0% (w))) .
jC(m]
jE(m)
(Eqn. (57)
(2L + Lo (mV) + 22 213
(Lemma 5
As the final step in the regret analysis, we state the following lemma which uses Lemma 16 to prove the optimistic nature of UCBlvd. Then following the standard analysis single-task LSVI-UCB we derive the regret bound for misspecified settings.
Lemma 17. Let W = {w" T [K] U (wo)) j E [n]]. Under the setting of Theorem and conditioned on events (w)) NEW defined in 9.. and with Qh computed as in 7 holds that (2T. + T (ad
+ 1)C (s, w) (T, a, w) for all (8,a, w. k)
A x W [H] x [K].
Proof. We first note that conditioned on events (w]) (w))]/ww wew for all w, (, xx [H] x [K] it holds that
Th (n a, w) + ( E ((s( a.) (T,s,, Ph [V w) Vitta w) (s,a)
ra(s,a, w) (ch rn (0) Pr [ (v w) (8,a)
Eh (br(bss a, w)) (5s,s,s)),)))
-Ph V/ V (1 as)
< (2L + L&s Vmddc + 2 (1)))))(
((5,
(Lemma 16
for any policy
35

---

Published as a conference paper at ICLR 2023
Now, prove the lemma by induction. The statement holds for H because Q Qu++(()..))
QH+1 ( = 0 and thus conditioned events (w)) wew> defined in @ for all (8, a, w,
S 3X W [K], we have
an w) + En ((,,,, Qn w) S (2L + Lo Vmdds + 2L ((()))
Therefore, conditioned on events (8)(w) wEW for all w,, k) ES x Ax W [K], we have
( (6, mol) (5. + (2L + Lo V
Qh(s,u, w) S Srn(s,a,
[H( + E (s + 2223 11 ( + (2L + Lo md)s
(3, a, w) + (2L + Lo mmd),
where the first equality follows from the fact that Qn 2 0. Now, suppose the statement holds at time-step h - 1 and consider time-step h. Conditioned on events
for all
(s, a, w. h k) E x A x W [H] x [K], we have
* (bs a, w) Qi(s,,, w) - Ph [2tt(., w) - (itt(., (s)
0 S a, +
+ +(I++ Ts (av)d) + 2T, (T 20,000)))
(ra(s,a,w) + ((. ( (2T+ L (o + 1) + +1.3 (T.,
(Induction assumption)
Therefore, conditioned on events {e, (w)) for all (s, x Ax W [K]. we have
(( ((s,.)) + (2T. L (Hd - h 1)5 + 21 (1,,))1((,,
(,( S (n((s,,,)) +
m + Eh ((s + +223)1 of
+ +22 + LD) + 1)
( w) + (2L + Lo LoV h +)C, where the first equality follows from the fact that 07,(v, a, w)) 2 0. This completes the proof.
F.2 PROOF OF THEOREM 6
The proof for establishing the upper bound on the number of planning calls for misspecified settings follows exactly the steps as those in the proof of Theorem 2
Now, we prove the regret bound. Let 5 (i w*) V (st w²) and sh =
8h.1- Conditioned on events (E) wew for all (s, w. h, E SSXAL Ax
W [H] [K], we have
Qh(s, Qu (s,a, rn(s,a, ( ((, -
Q (s,a,w) (L.
S Fn Vith w) (s, (2L Lo 4L3 (((s (1a))-
(59)
36

---

Published as a conference paper at ICLR 2023
Note that 5% s Qx ah w²) - Q (s of w Thus, combining (59 Lemma and union bound over W, we conclude that for all (h, k) E [M] x [K], with probability at least 1 holds that gives
o S S 8ht1 + (2L + Lo LøV + 4L ( ani
(aa)-1
Now, complete the regret analysis following similar steps those of Theorem
I proof:
RK- Σ (bi w² V/ w*)
$ (2L + Lo Mmd)HKK +
($f
(sf,
(Lemma
(2T. + T md)HHKC +
5
k=1
K
S (4L + 2L VLLVMmll M
<h
4LB
Σ
Σ
Φ a (Af)
K
H
K
H
det A
$ (4L + 2 V HK)
4LB
Σ
(s
x
k
att
(at)
V det A (Eqn.
k=
S + V 2H /loggg + 8HLB 2dK log(1+ K/A)
Ō (L Lo LoV HKC + LV A(d mdd)
where the last inequalities follow from the similar steps in the proof of Theorem
G AUXILIARY LEMMAS
Notations. (V) denotes the e-covering number the class of functions mapping R with respect the distance dist(V, V*) ) sup. ((s))
Lemma 18 (Bound on Weights (w)). Under Assumption for any set of action-value functions heeh and (w, h, k) E W x [H] x [K], it holds that
|o% s HVd.
Proof. Recall that (s, w) Is (o' w)ddu,ss) Thus, we have
min (max A ( a, w), and (
|o)(w)) = -11/ (s', (wdd:)))d)()))) < HHd.
Lemma 19 (Lemma D.4 in Jin et al.
2) Let {87 be stochastic process on state space
with corresponding filtration (J == Let {Ø, 1 be an Rd-valued stochastic process where
o, E Fr-1, I, and &, S 1. Let A AL + L -- $- $.. Then with probability at least 1 8, for all and V V such that supses
V V(s)
H. we have
b
k *+*) 2) (++)== + +log
(NG(2)) 5
+ 822
Φr. (V(+)) - ((s
< 2
log
A-1
37

---

Published as a conference paper at ICLR 2023
Lemma 20. For any O, the e-covering number of the Euclidean ball in R' with radius R > 0 is upper bounded by (1+ + 2R/e)".
Lemma 21. For a fixed w, let V denote a class of functions mapping from S to R with following parametric form
V() = min
max (z, a..a,, + (y, o(..))) + B ( (o),,a), aeAA
where the parameters 8 E R. 2 E Rd Ynd| S x Assume (
, y Rd, and Y E Rddd satisfy 3 < B.||2|| - 2, |ly| S y.
< 1 and (bs a, w)ll I for all (s, w) ES x A x W. Then
1+8B2 Vi dea
log (N.(V)) S d + dlog(1 + 4y/c) + d log
Proof. First, reparametrize V by letting Y Y. We have
v() = min {
max (z, sb(,,, a, w)) + ()))(.))) + v VV.. a). (Yb(a)) H aEd
for ||/|| S z, ||y|| S y. and
|
-22 For any two functions V12 V/2 V with parameters respectively, we have
(z) ,. Y and (2² y² Y²)
(2', (2). + (x' ((s + v (s) (
(Vi, V2) (A
sup
- ( (b((,, + (()))()))))+ + +1 (
(2/100) + (y" ()) + V V Y
(z)) + (5" + V Φ Y
sup 41 +
<z z², 2b) + sup
(st y² Φ
T Y -Y2) 0
sup wil -
sup
(because Va vbl I v/a b) for a, b 2
z2|
+ y² y² + Yi Y2
x2 x2
+
y²||
11 -1- 82
(60)
Let C2 and Cy be e/2-covers of {z E Rd
: ||/|| S 2) and fy E Rd ||y/|| S y). respectively, with
respect to the 2-norm, and Cr be an e² 4-covr of (Y E gdxd : |||||r S B' with respect to the Frobenius norm. By Lemma 20 we know
d²
1 8B2 Vd Xea
Ca| S (1 42/e) |cyl S (1+ + 4y/e)4,
|cx| s
According to (60). it holds that N.(V) < C2l ||xx| I, and therefore
1+8B2Vd Xe2
log (N.O3) S l'loo(1 + 42/c) + dlog(1 (1 + 4y/c) + d log
38

---

Published as a conference paper at ICLR 2023
Lemma 22. For fixed w, let V denote class of functions mapping from S to R with following parametrie form
(2, (1, + +LL ((..a) Yá( {()))))(())))) .1
V() min
max aeA
where the parameters 3 E R, 2 E Red and Y E Raxd satisfy 5 S 3 B, [||| S
S S
Assume (ssume|lo(s,u) ([)((s))) a)]l S and (b(( w) s for all (8, w) E E x A W. Then
1 1+
log (Wt(V)) s d' log(1 42/c) + df log
dc
Proof.
First, we reparametrize V by letting Y = Y We have
V(.)
min max (z, &,, a, w)) v v ( aEA
for ||/|| & 2, and Y
B² S
For any two functions V1, V22 E V with parameters (2),8) and
x
2 82)
respectively, we have
dist(V/, 1/2) - sup (s.
(2))00 + T
(p ()
( 2z 2Z a(s, + [ (Y
(22 v5 + i - (222 + +VOT
x Y
sup * +||
/ - 2², .b))
06 (rl (ri-- 822) -p2) Φ
sup 41 +1
sup
*1
(because Vaa vb < v1a a b for a b 2 0)
x²
81 82
z²
y1 Y2
(61)
Let C2 be an e/2-cover of {z E gdd |||ل|| < }} with respect to the 2-norm, and Cy be an e² /4-cover of (Y Raxd || & My }, with respect to the Frobenius norm. By Lemma we know
d
1 (18BB2V
IC, (1 + 42/e)*
|cr| S
dea
According to (11. it holds that Nc(V) - Cx and therefore
1++B2
log (NC(V)) < d' log(1 42/e) + d log
Xe
Lemma 23. For a fixed w. denote a class of functions mapping from S to with following parametric form
V() min aEA (2, ((,, + 2LB (
max
3/ H(
T TY (, a.)
H
39

---

Published as a conference paper at ICLR 2023
where the parameters 3, E R, z
E
Rd.
Y Rddd and Y E Re satisfy 0 S B 1 B.
0 S Blll S z, ||||| - x- and Y S Assume [|b(s, S 1 and 1b(5, a, w|ll s 1
for all (s,a,w) E S x A x W. Then
1 1 1+88A
1 1++BBVVl dc²
log (Nc(V)) S d' log(1 (1 + 42/c) + log
+ d log
dc²
Proof. First, we reparametrize V by letting Z = B and Z = BYY We have
(z, (b., a, w)) + v $61, a) a)( (b) + Vol. a) Z6(., ( a), H }
v() = min
max aEA
for ||z|| $ 2. ||||| I
B X
and
g
For any two functions Vi, V/2 E V with parameters
(x), 2 27)
and (x² Z2, 2²2
respectively, we have
(2.. + / ((s,))
dist(V1, 1/2) s sup (A.
- (z² a(s) + vo(s,a) (20(s [[(ss)) - V V w) T 22 (s
(2'.0) + 1 Zz + V VΦb 2/ - { 25 + V VØ 2 + V 1/ T 22
S 41 ||
sup
ক+* 2 - 2², 25)
T (Z) Zz) Φ + sup
2/ (Z) -2:) 4
sup v +1
sup
(because v -ā- vbl
S v/a bl for a, b 2 0)
z
z2
+ VIZ z²1 + vl [Z) v/2
_
< 2 2²
+ VIZI -1311 + 1|žz 222 F
(62)
Let C2 be an e e/2-cover of (z E Rdd :14| ك }} with respect to the 2-norm, Cz be an 6² /4-cover of
{Z E Rdxd
|Z < /dd,, }. and Cz be an e² /4-cover of {ā E Rd xd'
[ < Bdd
with
respect to the Frobenius norm. By Lemma 20 we know
d²
1 + V
+ 8732 V d'
|al S (1 + 42/0)=" 1ca15
| -
dc2
de²
According to 62 it holds that Nc()) S [C21/Cy), and therefore
1 1+ vd
1 1+8BBval de²
log (Nc(V)) < d' log(1 + 42/c) + log
d²2 logg
da2
Lemma 24. Let V denote a class of functions mapping S to IR with following parametric
v(..)= = min
max a
(z, (6, a) + 2L, V (6, a, .) TYb(....)) .H
where the parameters 3 E R2 z d and Y E Rdd' xd' satisfy S 3 S B, S 2, and -1
Assume Assume/|lb(s, a, w|ll < for all (s, E x A W. Then
1+8B2
log (Nc(V)) < d' log(1 + 4z/e) + d²2 log
Xe
40

---

Published as a conference paper at ICLR 2023
Proof. First, reparametrize V by letting Y B We have
V(...) = min max (z, a), + vab(..,.)) (.p(.. H aEA
for |||||| S 2, and |
B² x.
For any two functions V1, V/2 E V with parameters (at, v.) and
22 8²)
respectively, have
(2)) + V
(V,, V/2= z
sup (vx.,))
( 1b((,, a, w)) +++++//ba /2b(s, a,
(
( (z", (z'.0b) + v V 1
(z"), (z).v)) + Vab
+)))+***++)+ Y2b YYub
s sup
*1
(z) z², mb)
2T (ir- (8)=))) 2/
< sup ~
sup
(because Va vbl s vaa bl for a, b 2 0)
=²
+
Y1 Y
< 2
z²
+
Y1 Y²
(63)
Let C2 be an e/2-cover of (z E Rdd |||||| S =} with respect to the 2-norm, and Cy be an e² //aaan////ooo /4corr
of (Y gd xd'
B² J. with respect to the Frobenius norm. By Lemma 20 we know || _
1 1+8B²V2 d'
|c,| S (1 + 42/e)=
|cr| S
According to
it holds that Nc(V) S C/ /. and therefore
(1+8B2 V
log (Nc(V)) < d' log(1 + 4z/cc + d²2 log
de2
H DETAILS OF THE EXPERIMENTS
In all the experiments, we have chosen 0.01, x= 1, 5, and H = 5. The parameters (nh heej m| are drawn from (00. Iz... In order to tune parameters (M)(-)ee((M) and the feature mappings d such that they are compatible with Assumption 1, we consider that the feature space (Ø(8.0) a)= : (s, a) E S x A} is a subset of the d-dimensional simplex, { E Rd Dd Φ; 1, Φ 2 0, I 1, Vi E [d), and o, (.)..) is an arbitrary probability measure over S for all i E [d].
The results shown in Figure 2a depict averages over 50 realizations for the main setup considered
throughout the paper with m 5 and the results shown in Figure 2b depict averages over 50 realizations, for the more general setup of Remark 2 with d' = 10. For the results shown in Figure 2a the mappings p(w) are drawn from (0, Lm) except for the n m representative tasks (e00))jem introduced in Assumption 3 for which we set p(w(i)) e, for [m]. For the results shown in Figure 2b] the mappings vb(8, a, w) drawn from (0, Tar and we set ub(s, a, w(()) = 0, for
j E [d"], where (w(() Jyeja] are d' representative tasks introduced in Assumption 5 in Appx. D
The parameters (n) heEmH are drawn from (0, Iæ), where d' m d = 25 in Figure 2a In
41

---

Published as a conference paper at ICLR 2023
experiments, the exact same settings are used for both UCBlvd and Lifelong-LSVV in both Figures 2a and 2b We chose fairly large d, m, and d' and by checking online, we noticed that the optimal value of QCQP in (8) happens always be zero. All these together suggest that the assumptions made in the paper approximately hold. Figures 2 and 2b depict the average per-episode reward UCBlvd and state the average number of planning calls and compare them to those of baseline algorithm Lifelong-LSVI, a direct extension of LSVI-UCB in Jin et al. (2020). The results emphasize the value of UCBlvd in terms of requiring much smaller numbers of planning calls. The plots verify that the performances of Lifelong-LSVI and UCBlvd are almost the same statistically, while UCBlvd uses much smaller numbers of planning calls (1000 20).
In Figure [ we plot UCBlvd's number planning calls for different number of task episodes, K, while the setting is same as that in 2a In this figure, empirically verify the logarithmic dependence of number of planning calls on K as suggested by Theorem
3.5
Per-episode reward
Per-episode reward
1.5
0.5
L.feion-LLLV L5V,
1000
Lieeong LSVI, A planning calls UCBBdd plarning calle
1000
--CUill plamning calls 8333
200
400
600
800
1000
200
400
600
800
1000
Episode, &
Episode, k
(a) Setting of Theorem
d == 5. m 5, 25
(b) Setting of Remark d 5, d' 10
Figure 2: UCBlvd Lifelong-LSVI
# of planning calls UCBlvd
20
15
500
1000
1500
2500 3000 3600
Total number of task episodes, K
Figure Setting of Theorem 2 m 5, d'
42


Reviews:
[{"review_id": "ll9EPRXpqg", "reviewer": "Reviewer_yDMc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies **lifelong** reinforcement learning with linear function approximation. In a typical RL setup, the reward function depends only on the state-action pair. The **lifelong** component of this works comes from the assumption that the reward function is dependent on the state-action pair $(s, a)$ in addition to a task context variable, denoted $w$. It is assumed that the agent observes $w$ directly but $w$ is allowed to change from one episode to the next. The paper also addresses how to reduce the number of planning calls in the lifelong learning context.\n\nOverall the contributions, to me, seem two-fold:\n1. Introduces the lifelong RL setup and Lifelong-LSVI, a naive baseline in the lifelong learning problem.\n2. Identifies two assumptions under which a low-switching cost algorithm is possible for lifelong RL. The authors justified the assumption using a toy example (see Example 1).", "summary_of_the_review": "Overall, the paper introduces a novel setting for linear MDP. The authors are able to derive conditions under which low switching cost RL algorithms work. The extra assumptions needed to enable low switching cost RL is unique to the setting and is a novel contribution from the authors. Unfortunately, the mathematical model for lifelong RL seems overly reductionist at this moment and further explanation and justification would be appreciated.", "strength_and_weaknesses": "Strength\n- The setting is novel and is relevant to RL practitioners.\n- Experimental results are able to show that UCBlvd enjoys roughly the same regret while requiring far less calls to the planning subroutine. \n\nWeaknesses\n- The assumption that the reward functions for all tasks are known beforehand is a strong one. In the lifelone learning environment described here, the only source of uncertainty lies in the transition kernel, making the setting close to a single-agent single-task RL problem, which has been thoroughly examined in the linear MDP setting. While Example 1 offers a good intuitive justification, it would be great if the authors could offer more justification for the setting they assume, perhaps in the appendix, similar to the discussion immediately after Assumption 2.\n\n------- Post rebuttal update --------\nMy concerns have been addressed by the authors and I have adjusted my score accordingly.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jQl5eTUVRKn", "reviewer": "Reviewer_vHiq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper may most accurately be summarized as giving polynomial-time algorithms that obtain sublinear regret in linear contextual MDPs when the transition and Q-functions are linear in the state-action features and the context, and that only need to re-solve the MDP logarithmically many times w.r.t. the number of tasks.\n\nMore concretely, the contextual MDP has a fixed dynamics (independent of the context), but reward functions that vary with a side \"context\" w that is known to the learner. The learner interacts with this MDP for K episodes of horizon H. The main assumption is that the transition kernel and Q-function are linear in some known basis functions. A similar assumption was used previously to obtain a polynomial time algorithm for such MDPs sans context; so this paper is essentially extending that line of work to include context.", "summary_of_the_review": "I think there's enough of a contribution to warrant accepting this paper.", "strength_and_weaknesses": "The main strengths of the paper are\n1. It considers the computational cost in this online setting, which is usually ignored (e.g., in bandits) but would indeed be prohibitively substantial here using existing methods.\n2. There is some technical novelty in the design and analysis of the test for the need to recompute the solution towards the above.\n3. There are some experiments, albeit on synthetic tasks, so the method is potentially useable in practice.\n\nThe main weaknesses are\n1. Technically, apart from the analysis of the number of re-solves, it seems to be a straightforward extension of the previous works on the non-contextual MDPs, e.g., Yang & Wang 2019.\n2. The individual planning calls are now more expensive, as they have to solve a QCQP rather than a linear program.\n3. The synthetic experiments don't give a sense of how the algorithm would perform in a real-world setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UEBy3SVxpZ", "reviewer": "Reviewer_hkRh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tackles the challenges of lifelong reinforcement learning. In particular, authors propose an algorithm (UCBvld) for solving sequential contextual Markov decision processes with linear representation which (1) guarantees sublinear regret with (2) a sublinear number of planning calls, even when the sequence of tasks and the initial states are chosen adversarially. \n\nUCBvld has its foundation in LSVI-UCB, with an added distillation step based on a convex quadratically constrained quadratic program defined on a set of representative task contexts (assumed to be known). ", "summary_of_the_review": "The paper tackles an important gap in the RL literature. However, it seems to be of very limited applicability, without any direction for future extension provided. ", "strength_and_weaknesses": "Strengths\n\n* Though quite dense, the work is presented in a digestible way. I found the background, the method and the theoretical part of paper clearly organised and concise. \n* The problem studied is important and relevant, authors have identified gap in the field of RL (theoritical lifelong RL) and provided ideas and tools to start addressing it. \n\nWeaknesses\n* My main concern is that authors have not conveyed if or how the contributions of the work will extend beyond the limited case of linear environment under the completeness assumption. I appreciate that extensions to the non linear case / with fewer assumptions might not be possible yet, but then a discussion around how we expect the performance to be impacted would be necessary (experiments on non synthetic environments could help to show that).\n* The reason for my previous point is that I did not grasp from reading the paper what kind of environments fall into these constraints in practice, so I don't see how it could be applicable. I do not have a strong enough understanding of how reasonable is the completeness-style assumption.\n* The experiment section needs more information. What are the environments? A comparison with another lifelong RL baseline should also be included to be convince readers of UCBlvd's benefits.\n\n\nMinor:\n* page 5 CMDP appears without being defined \n* page 6, $\\boldsymbol S_{++}^d $ is not defined\n* page 6, \"the algoriTheorem\"?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "MYpM5qVJp57", "reviewer": "Reviewer_HSfE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies lifelong reinforcement learning with different tasks. In particular, the paper proposes a new algorithm that is both sample-efficient and computation-efficient. The underlying models are variants of linear MDPs, which are widely studied by the reinforcement learning theory community.", "summary_of_the_review": "The reviewer believes that paper is a little below the acceptance threshold. It will be helpful if the reviewers' concerns mentioned above can be resolved in the author's responses.", "strength_and_weaknesses": "Strength: The paper proposes a novel algorithm which is both sample-efficient and computation-efficient in theory. The computation-efficiency seems appealing and insightful, but some more detailed analysis might be helpful for people to fully understand the contribution. In particular, the paper decreases the $K^2$-cost of planning call to $log(K)$ by skipping planning in the case that no sufficient new information is obtained.\n\nWeakness: 1) The sample-efficiency of the algorithm has very limited insight given previous works. 2) It will be more clear for the readers to understand the contribution of the paper if the paper can explicitly analyze how much computation cost is reduced, rather than just from the reduction of planning calls. In deed, the new algorithm still require to calculate a new covariance matrix in each iteration. When re-planning is triggered, it requires solving a QCQP, which is not required in Algorithm 1. 3) It is not very clear how strong the cross product structure in Assumption 3 is. Does it includes the case where there is only finite number of possible $w$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster