Provably Efficient Reinforcement Learning with Linear Function Approximation under Adaptivity Constraints
Authors: Tianhao Wang
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
linear function approximation
adaptivity constraint

Abstract: We study reinforcement learning (RL) with linear function approximation under the adaptivity constraint. We consider two popular limited adaptivity models: the batch learning model and the rare policy switch model, and propose two efficient online RL algorithms for episodic linear Markov decision processes, where the transition probability and the reward function can be represented as a linear function of some known feature mapping. In specific, for the batch learning model, our proposed LSVI-UCB-Batch algorithm achieves an $\tilde O(\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature mapping, $H$ is the episode length, $T$ is the number of interactions and $B$ is the number of batches. Our result suggests that it suffices to use only $\sqrt{T/dH}$ batches to obtain $\tilde O(\sqrt{d^3H^3T})$ regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an $\tilde O(\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})$ regret, which implies that $dH\log T$ policy switches suffice to obtain the $\tilde O(\sqrt{d^3H^3T})$ regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm \citep{jin2020provably}, yet with a substantially smaller amount of adaptivity. We also establish a lower bound for the batch learning model, which suggests that the dependency on $B$ in our regret bound is tight.

Provably Efficient Reinforcement Learning with Linear Function Approximation under Adaptivity Constraints
Tianhao Wang*
Dongruo Zhou"
Department of Statistics and Data Science Yale University
Department of Computer Science University of California, Los Angeles
New Haven, CT 06511
Los Angeles. CA 90095 drzhou8cs ucla. edu
tianhao. wang@yale edu
Quanquan Gu
Department of Computer Science University of California, Los Angeles
Los Angeles, CA 90095 gguêcs wwwa. edu
Abstract
We study reinforcement learning (RL) with linear function approximation under the adaptivity constraint. We consider two popular limited adaptivity models: the batch learning model and the rare policy switch model, and propose two efficient online RL algorithms for episodic linear Markov decision processes, where the transition probability and the reward function be represented of some known feature mapping. In specific, for the batch learning model, our proposed LSVI-UCB-Baas
linear function
algorithm achieves an Õ(v da 3 + dHT/ B) regret, where d the dimension of the feature mapping. H is the episode length, T is the number of interactions and B is the number of batches. Our result suggests that suffices to use only /T/dH batches obtain H(T) regret. For the rare policy switch model, our proposed LSVI-UCB- Rare-Shhhh algorithm enjoys an Ö( H + (T(dd))jBBBB regret, which implies that dH log T policy switches suffice to obtain the O(vd=113T) regret. Our algorithms achieve the same regret as the LSVI-UCE algorithm (Jin et al., 2020), yet with a substantially smaller amount of adaptivity. We also establish lower bound for the batch learning model, which suggests that the dependency on B in our regret bound is tight.
Introduction
Real-world reinforcement learning (RL) applications often come with possibly infinite state and action space, and in such situation classical RL algorithmss developed in the tabular setting are not applicable anymore. A popular approach to overcoming this issue is by applying function approximation techniques to the underlying structures of the Markov decision processes (MDPs). For example, one can assume that the transition probability and the reward are linear functions of known feature mapping Φ S x A -> IRd, where S and A are the state space and action space, and d is the dimension of the embedding. This gives rise the so-called linear MDP model (Yang and Wang, 2019; Jin et al., 2020). Assuming access to generative model, efficient algorithms under
Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

this setting have been proposed by Yang and Wang (2019) and Lattimore et al. (2020). For online finite-horizon episodic linear MDPs, Jin et al. (2020) proposed an LSVI-UCB algorithm that achieves Ō( H regret, where H is the planning horizon (i.e., length of each episode) and T is the number of interactions.
However, all the aforementioned algorithms require the agent to update the policy in every episode. In practice, it is often unrealistic to frequently switch the policy in the face of big data, limited computing resources as well as inevitable switching costs. Thus one may want to batch the data stream and update the policy at the end of each period. For example, in clinical trials, each phase (batch) of the trial amounts to applying a medical treatment to batch of patients in parallel. The outcomes of the treatment are not observed until the end of the phase and will be subsequently used to design experiments for the next phase. Choosing the appropriate number and sizes of the batches is crucial to achieving nearly optimal efficiency for the clinical trial. This gives rise to the limited adaptivity setting, which has been extensively studied in many online learning problems including prediction- from-experts (PFE) (Kalai and Vempala, 2005;
Aasa-Bianchi al., 2013), multi-armed bandits (MAB) (Arora et al., 2012; Desa-Bianchi et al., 2013) and online convex optimization (Jaghargh et al., 2019; Chen et al., 2020). to mention a few. Nevertheless, in the RL setting, learning with limited adaptivity is relatively less studied. Bai et al. (2019) introduced two notions of adaptivity in RI., local switching cost and global switching cost, that are defined as follows
K-1 H Nical ΣΣΣDE k= -=s
K-1
(= & Fh (s)) and Nglobal = 1 A
xt1]]
(1.I)
where n² = ( :S + A]nE is the policy for the k-th episode of the MDP, n² 7 *+1 means that there exists some (h, s) E [H] x S such that (s) * (s). and K is the number of episodes. Then they proposed a Q-learning method with UCB2H exploration that achieves regret with tight bounds on the global switching cost.
SA (Tg(T(((g (AH)) local switching cost for tabular MDPs, but they did not provide
In this paper, based on the above motivation, we aim to develop online RL algorithms with linear function approximation under adaptivity constraints. In detail, we consider time time-inhomogeneous episodic linear MDPs (Jin et al., 2020) where both the transition probability and the reward function unknown to the agent. In terms of the limited adaptivity imposed on the agent, we consider two scenarios that have been previously studied in the online learning literature (Perchet et al., 2016; Abbasi-Yadkori Abbasi- Yadkori al., 1): the batch learning model and the rare policy switch model. More
specifically, in the batch learning model (Perchet et al., 2016), the agent is forced to pre-determine the number of batches (or equivalently batch size). Within each batch, the same policy is used to select actions, and the policy is updated only at the end of this batch. The amount of adaptivity in the batch learning model is measured by the number of batches, which is expected be as small as possible. In contrast, in the rare policy switch model (Abbasi- Yadkori et al., 20, the agent can adaptively choose when to switch the policy and therefore start new batch in the learning process as long as the total number of policy updates does not exceed the given budget on the number of policy switches. The amount of adaptivity in the rare policy switch model can be measured by the number of policy switches, which turns out to be the same as the global switching cost introduced in Bai et al. (2019). It worth noting that for the same amount of adaptivity", the rare policy switch model can be seen a relaxation of the batch learning model since the agent in the batch learning model can only change the policy at pre-defined time steps. In our work, for each of these limited adaptivity models, we propose variant of the LSVI-UCB algorithm (Jin et al., 2020), which can be viewed as an RL algorithm with full adaptivity in the sense that it switches the policy at a per-episode scale. Our algorithms can attain the same regret as LSVI-UCB, yet with substantially smaller number of batches/policy switches. This enables parallel learning and improves the large-scale deployment of RL algorithms with linear function approximation.
The main contributions of this paper are summarized as follows:
We say episodic MDP time- inm-mohhooeennsuu if its reward and transition probability are different different stages within each episode. See Definition 3.2 for details.
'The number of batches in the batch learning model is comparable to the number of policy switches in the rare policy switch model.
2

---

For the batch learning model, we propose an LSVI-UCB- -Ct-Bahhhh algorithm for linear MDPs and show that it enjoys Ö(vd H + BB) regret, where d is the dimension of the feature mapping, H is the episode length, T' is the number of interactions and B is the number of batches. Our result suggests that it suffices to use only vT/dH batches, rather than T batches, to obtain the same regret O(v (TT) achieved by LSVI-UCB (Jin et al., 2020) in the fully sequential decision model. We also prove a lower bound of the regret for this model, which suggests that the required number of batches ((VT) is sharp.
For the rare policy switch model, we propose an SEVI-UCB-RareSwinn algorithm for linear MDPs and show that it enjoys an (( // + T/ ( regret, where B is the number of policy switches. Our result implies that dH log T policy switches are sufficient to obtain the same regret O H3T) achieved by LSVI-UCB. The number of policy switches is much smaller than that" of the batch learning model when T is large.
Concurrent to our work, Gao et al. (2021) proposed an algorithm achieving Ō HT) regret with a O(dH log K) global switching cost in the rare policy switch model. They also proved MddH/ log d) lower bound on the global switching cost. The focus of our paper is different from theirs: our goal is to design efficient RL algorithms under switching cost budget B. while their goal is to achieve the optimal rate terms of T with as little switching cost as possible. On the other hand, along its regret bound can imply their results by optimizing our regret bound concerning the switching cost budget B.
for the rare policy switch model, our proposed algorithm
The rest of the paper is organized as follows. In Section we discuss previous works related to this paper, with a focus on RL with linear function approximation and online learning with limited adaptivity. In Section 3 we introduce necessary preliminaries for MDPs and adaptivity constraints. Sections 4 and 5 present our proposed algorithms and the corresponding theoretical results for the batch learning model and the rare policy switch model respectively. In Scction 6 we present the numerical experiment which supports our theory. Finally, conclude our paper and point out future direction in Section 7.
Notation We use lower case letters to denote scalars and use lower and upper case boldface letters to denote vectors and matrices respectively. For any real number o, we write [a]+ max (a, 0). For a vector x E Id and matrix Σ Rdxd we denote by ||x||2 the Euclidean norm and define ||x||= = vx Ex. For any positive integer n, we denote by [n]] the set (1..... n). For any finite set A. denote by |A| the cardinality of A. For two sequences {a,, and } we write an (b,,) there exists an absolute constant C' such that an &Cb,, and we write a, = (2(b,,) if there exists an absolute constant C such that an 2 Cbn- We use Ō()) to further hide the logarithmic factors.
2 Related Works
Reinforcement Learning with Linear Function Approximation Recently, there have been many advances in RL with function approximation, especially the linear case. Jin et al. (2020) proposed an efficient algorithm for the first time for linear MDPs of which the transition probability and the rewards are both linear functions with respect to feature mapping & : S x A + Rdd Under similar assumptions, different settings (e.g., discounted MDPs) have also been studied in Yang and Wang (2019); Du et al. (2020); Zanette et al. (2020): Neu and Pike-Burke (2020) and He et al. (2021). A parallel line of work studies linear mixture MDPs (a.k.a. linear kernel MDPs) based on ternary feature mapping & : S x A x S + Rd (see Jia et al. (2020); Zhou et al. (2021b); Cai et al. (2020); Zhou et al. (2021a)). For other function approximation settings, we refer readers to generalized linear model (Wang et al., (021), general function approximation with Eluder dimension (Wang et al., 2020; Ayoub al., 2020), kernel approximation (Yang et al., 2020), function approximation with disagreement coefficients (Foster et al., 2021) and bilinear classes (Du et al., 2021).
Online Learning with Limited Adaptivity As mentioned before, online learning with limited adaptivity has been studied in two popular models of adaptivity constraints: the batch learning model and the rare policy switch model.
'The number of policy switches is identical to the number of batches in the batch learning model.
3

---

For the batch learning model, Altschuler and Talwar (2018) proved that the optimal regret bound for prediction-from-exppe
(PFE) is Ō 1o when the number of batches B = S2(vT SikvTloog n),, and min(O log // B), T) when B ( T n). exhibiting a phase- ttass-transition phenomenon'. Here is the number of rounds and n. is the number of actions. For general online convex optimization, Chen et al. (2020) showed that the minimax regret bound is D(TvBB) Perchet et al. (2016) studied batched 2-arm bandits, and Gao et al. (2019) studied the batched multi-armed bandits (MAB). Dekel al. (2014) proved Q2T/ / B) lower bound for batched MAB, and Altschuler and Talwar (2018) further characterized the dependence on the number of actions n. and showed that the corresponding T). For batched linear bandits with adversarial contexts, Han al. (2020) showed that the minimax regret bound is Ö +dT B) where d is the dimension of the context vectors. Better rates can be achieved for batched linear bandits with stochastic contexts as shown in Esfandiari al. (2021); Han et al. (2020); Ruan et al. (2020).
minimax regret bound is
For the rare policy switch model, the minimax optimal regret bound for PFE is OV n) in terms of both the expected regret (Kalai and Vempala, 2005; Geulen et al., 2010; Cesa-Bianchi et al., 2013; Devroye et al., 2015) and high-probability guarantees (Altschuler and Talwar, 2018), where T' is the number of rounds, and the number of possible actions. For MAB, the minimax regret bound has been shown to be ((T2/3n) by Arora et al. (2012); Dekel al. (2014). For stochastic linear bandits, Abbasi-Yadkori Yadkori et al. (2011) proposed rarely switching OFUL algorithm achieving O(d'T) regret with ITg batches. Ruan et al. (2020) proposed an algorithm achieving Ö( Ö(VdT) regret with less than O(d ol log 7') batches for stochastic linear bandits with adversarial contexts.
For episodic RL with finite state and action space, Bai et al. (2019) proposed an algorithm achieving O(VI regret with O log(T/(AHH)) local switching cost where S and A are the number of states and actions respectively. They also provided a ! (2HS)) lower bound on the local switching cost that is necessary for sublinear regret. For the global switching cost, Zhang et al. (2021) proposed an MVP algorithm with at most O(SA (og(( HH) global switching cost for time-homogeneous tabular MDPs.
3 Preliminaries
3.1 Markoy Decision Processes
We consider the iimomonoooogess episodic Markov decision process, which is denoted by tuple M(S,A A, H, (rn he(M] hhem)) Here S the state space (may be infinite), A is the action space where allow the feasible action set to change from step step. H is the length of each episode, and Th : S x A - [0. 1] is the reward function for each stage h E [H]. At each stage h [H). (P'(s's sl(ssa) is the transition probability function which represents the probability for state to transit to state s' given action a. A policy æ consists of H mappings, { S -> A) For any policy т,, we define the valuee function Q7, a) and value function VT]((s as follows:
27 =) rx(88 + E,z Σ re( ai) 8h = 8, 8, =
(x) = Q7 (s. (x)),
where a; (-(sss:) and 81+1 P.(, az). The optimal value function V and the optimal (s, action-value function (s, a) are defined as (*))) sup, (s) and Q7 (s. sup, Q% (8, a). respectively. For simplicity, for any function V S - R. we denote (s, = Exr Vs''. In the online learning setting, at the beginning of k-thh episode, the agent chooses policy x² and the environment selects an initial state sf, then the agent interacts with environment following policy
- and receives states sy and rewards ri (s),, af) for h E [H]. To measure the performance of the algorithm, we adopt the following notion of the total regret, which is the summation of suboptimalities between policy x and optimal policy -":
Definition 3.1. We denote T
KH, and the regret Regret(T) defined as
Regret T) = ΣΣ (r((st) VF (st)
They call it B-switching budget setting, which is identical to the batch learning model.

---

3.2 Linear Function Approximation
In this work, we consider a special class of MDPs called linear MDPs (Yang and Wang, 2019; Jin et al.. 2020), where both the transition probability function and reward function can be represented as linear function of given feature mapping Φ : A R.. Formally speaking, we have the following definition for linear MDPs.
Definition 3.2. A, H, (ra (raTEE (Px (PA)) is called linear MDP if there exist known feature mapping ((s,a) a): 8 x A + IR,, unknown measures {ur (U) (1) ... .1h.
(4) hee over
and unknown vectors {0, E R.d he(m with maxде]н) (0) ||0, - vd, such that the following holds for all h E [H]:
For any state-action-ste state triplet (s, a, 8') ES Ax Pr (0(8 un())
For any state-action pair (s, a)
A, (n (0(s, On)
Without loss of generality, we also assume that [ a)]l2 || S 1 for all (s, a) E S A.
With Definition 3.2, it shown in Jin al. (2020) that the action-value function can be written as linear function of the features.
Proposition 3.3 (Proposition 2.3, Jín et al. 2020). For linear MDP, for any policy τ, there ist weight vectors hREA such that for any (s, a, h) E S x x [H], we have (5, = ())s,a), wT)- Moreover, we have |w S v for all h E [M].
Therefore, with the known feature mapping ((:,)), it suffices estimate the weight vectors (wī, he(H) in order to recover the action-value functions. This is the core idea behind almost all the algorithms and theoretical analyses for linear MDPs.
3.3 Models for Limited Adaptivity
In this work, we consider RL algorithms with limited adaptivity. There are two typical models for online learning with such limited adaptivity: batch learning model (Perchet et al., 2016) and rare policy switch model (Abbasi- Yadkori et al., 2011).
For the batch learning model, the agent pre-determines the batch grids = 4 < l2 < ... < Ln < 1B+1 K + 1 at the beginning of the algorithm, where B is the number of batches. The b-th batch consists of 16-th to (4++1 - 1)-th episodes, and the agent follows the same policy within each batch. The adaptivity is measured by the number of batches.
For the rare policy switch model, the agent can decide whether she wants to switch the current policy or not. The adaptivity is measured by the number of policy switches, which is defined as
K Σ
Nswitch
fm o n xt1].
k=1
where T² # x++1 means that there exists some (h, [H] x S such that o (T() # n (s). It worth noting that Newitch is identical to the global switching cost defined in (1.1).
Given a budget on the number of batches or the number of policy switches, aim to design RL algorithms with linear function approximation that can achieve the same regret as their full adaptivity counterpart, e.g., LSVI-UCB (Jin et al., 2020).
4 RL in the Batch Learning Model
In this section, consider RL with linear function approximation in the batch learning model, where given the number of batches B, we need to pin down the batches before the agent starts to interact with the environment.
4.1 Algorithm and Regret Analysis
We propose I.SI-UCC-Batch algorithm as displayed in Algorithm 1, which can be regarded as variant of the LSVI-UCB algorithm proposed in Jin et al. (2020) yet with limited adaptivity.
5

---

Algorithm LLVI-UCB--BaR
Require: Number of batches B, confidence radius 3, regularization parameter À
1: Set b - 1; - (i 1) |K/B| | - 1,
2: for episode k 1, ..... _ do
3: Receive the initial state sf
4: - then
5: b b+ Q 10+1(1)) 5
6:
for stage h= H, H
do A Σト=1 ((5 02 [ AI
7:
w (A))-1E k-1 (65 07)) [ra(%, 4 + maxaeA Q (8422,
8:
9:
D (, 3. (0( (A (),
10:
(; c min(
w + +
h 13+, x argmax (h(:a)
11:
end for
else
13:
U t Q Th t 1
k-1 vh [H]
end if
15:
for stage h 1..... H.HHHo do
Take the action ax x nx (s)) receive the reward (s af) and the next state s/+1
17: end for
end for
Algorithm takes series of batch grids (t1...., tB+1} } input, where the i-th batch starts at i; and ends at t; 1. LSVI-UCB Batch takes the uniform batch grids as selection of grids, i.e., (i 1) [K/B] + 1, E B). By Proposition 3.3, know that for each h [H], the optimal value function Q7, has the linear form (Ø(:)), w Therefore, to estimate the Q7 it suffices to estimate w/- At the beginning of each batch, Algorithm calculates w as an estimate of w by ridge regression (Line 8). Meanwhile, in order to measure the uncertainty w Algorithm sets the estimate 2%(-)) as the summation the linear function (Ø(-; -), wfi and Hoeffding-tyye type exploration bonus term ...)) (Line 10), which is calculated based on the confidence radius 3. Then sets the policy o as the greedy policy with respect Q Within each batch, Algorithm simply keeps the policy used in the previous episode without updating (Line 13). Apparently, the number of batches of Algorithm is B.
Here we would like to make comparison between our LSVI-UCB-Baan and other related algorithms. The most related algorithm LSVI-UCB proposed in Jin al. (2020). The main difference between LSVI-UCB-BBE BBtchh and LSVI-UCB is the introduction of batches. In detail, when B K, LSVI- UCB-Batch degenerates to LSVI-UCB. Another related algorithm is the SBUCB algorithm proposed by Han et al. (2020). Both L.SV-UUC--atte and SBUCB take uniform batch grids as the selection of batches. The difference that SBUCB is designed for linear bandits, which is a special case of episodic MDPs with H 1.
The following theorem presents the regret bound of Algorithm 1.
Theorem 4.1. There exists a constant > 0 such that for any 8 E (0. 1), if we set À 1, B edH Vlog(2dT/// then under Assumption 3.2, the total regret of Algorithm is bounded by
2dT
dHT
T dH +1)
RTgret(T) S2H / Tlog
log
2B log2
2dT
T dH
4eg 2d H Flo
log
8
with probability at least - 8.
Theorem 4.1 suggests that the total regret of Algorithm is bounded by Ö(VEHHT + ddT/BB B). When = 2 DdHH), the regret Algorithm is Ō(V H3T), which the same as that of LSVI-UCB in Jin et al. (2020). However, it is worth noting that LSVI-UCB needs K batches, while Algorithm only requires VT/dH batches, which can be much smaller than K.

---

Algorithm 2 LLVI-UCDBRRaeSSieel
Require: Policy switch parameter n, confidence radius B, regularization parameter À 1: Initialize A, = A = AI for all E [H]
2: for episode k 1, ... K do
3: Receive the initial state sf
4: for stage h 1, H do
5: A Σド=1 (5) 0 ( af + AIa
6: end for
7:
if 3h [ot (o > 1) det AA)) then
8:
2++1 (: f-1 0
9:
for step h H, H 1, do
A₁ A
11:
w + (A )- -1 E O65 07) 1ra(8 (g) + max Q (1)
12:
(+.) B (. (A - (1
(x+)) t min
wT. + + H. h 13 +)() argmax ()(
14:
end for
15:
else
16:
k- vh [H] Q t- Qk-1 . t t- Th
end if
18:
for stage h = ..... H.HHo do
Take the action a n (s), receive the reward rn (s) a and the next state sh441
20: end for
end for
Next, we present lower bound to show the dependency of the total regret on the number of batches for the batch learning model.
Theorem 4.2. Suppose that (d (d-1)H// Then for any batch learning algorithm with B batches, there exists linear MDP such that the regret over the first T rounds is lower bounded by
Regret(T) M(dH dHT/B).
Theorem 4.2 suggests that in order to obtain standard -reggett, the number of batches B should be least in the order of 52( (2(TT), which is similar to its counterpart for batched linear bandits (Han et al., 2020).
RL in the Rare Policy Switch Model
In this section, we consider the rare policy switch model, where the agent can adaptively choose the batch sizes according to the information collected during the learning process.
5.1 Algorithm and Regret Analysis
We first present second algorithm, LSVI-UCB -areeStitch... illustrated in Algorithm 2. Again, due to the nature of linear MDPs, we only need to estimate w by ridge regression, and then calculate the optimistic action-value function using the Hoeffding-type exploration bonus (, :) along with the confidence radius 3. Note that the size of the bonus term in Q is determined by A Intuitively speaking, the matrix A in Algorithm 2 represents how much information has been learned about the underlying MDP, and the agent only needs to switch the policy after collecting significant amount of additional information. This is reflected by the determinant of A and the upper confidence bound will become tighter (shrink) as det(AA A increases. The determinant based criterion similar to the idea of doubling trick, which has been used in the rarely switching OFUL algorithm for stochastic linear bandits (Abbasi- Yadkori et al., 2011) 1), UCRL2 algorithm for tabular MDPs (Jaksch et al., 2010), and UCLK/UCLK+ for linear mixture MDPs in the discounted setting (Zhou al., 2021b.ab
As shown Algorithm 2, for each stage E [H] the algorithm maintains a matrix A which updated at each policy switch (Line 10). For every k E [K], we denote by by the episode from which
7

---

the policy тą is computed. This is consistent with the one defined in Algorithm 1 in Section 4. At the start of each episode k. the algorithm computes (a (Line 5) and then compares them with (Antee( using the determinant-basee exists some E [H] such that det(AA, has increased by some pre-determined parameter v > 1, followed by policy evaluation (Lines 11-13). Otherwise, the algorithm retains the previous policy (Line 16). Here the hyperparameter v controls the frequency of policy switch, and the total number of policy switches can be bounded by function of r7.
criterion (Line 7). The agent switches the policy if there
Algorithm 2 is also a variant of LSVI-UCB proposed in Jin et al. (2020). Compared with LSVI-UCB- Batch in Algorithm for the batch learning model, LSVI-UCB SeL-LUCB---reewiiiee RareSwitch adaptively decides when to switch the policy and can be tuned by the hyperparameter r) and therefore fits into the rare policy switch model.
We present the regret bound of Algorithm 2 in the following theorem.
Theorem 5.1. There exists some constant
0 such that for any ō (0, if set À 3 = cdH (2g( and = (1 + K/d) dB then the number of policy switches Nowich in Algorithm will not exceed B. Moreover, the total regret of Algorithm 2 is bounded by
2dT
V
(
T dH
11
T dH
2dT
Regret(T) & 2H Tlog
+ 2cv
2d 2d H
-1)
log
+1) log
8 (5.1)
with probability at least 8.
A few remarks are in order.
Remark 5.2. Algorithm needs update the value of each (et( and thanks to the special structure of A this can be done efficiently by applying the matrix determinant lemma along with the Sherman Morrison formula for efficiently updating each (Ağ)=1 For simplicity and clarity of the presentation, we do not include these details in the pseudo-code.
Remark 5.3. By ignoring the non-dominating term, Theorem 5.1 suggests that the total regret of Algorithm 2 is bounded by dd dH TT/dH)jjurn Also, if we are allowed to choose B. we can choose B (HH log T') to achieve D(Vd5H131 regret, which the same as that of LSVI-UCB in Jin et al. (2020). This also significantly improves upon Algorithm I when T' is sufficiently large since previously we need B = 22( TT/H). Our result exhibits trade-off between the total regret bound and the number of policy switches, i.e., as the adaptivity budget B increases, the regret bound decreases. This will also be reflected by the numerical results later in Section 6.
Remark 5.4. Concurrent to our work, Gao et al. (2021) proposed an algorithm with B Q(dH log T) policy switches. Note that B 22HH log T) corresponds choosing 1 to be a constant, which can be viewed as a special case of our algorithm. Their algorithm does not adapt to different values of budget Also, they did not study the batch learning model (Section 4) which we think is of equally important practical interest.
Remark 5.5. Gao et al. (2021) established lower bound, which claims that any rare policy switch RL algorithm suffers a linear regret when = ö(dH). However, unlike our lower bound for the batch learning model (Theorem 4.2). their result does not provide fine- tine-grained regret lower bound for arbitrary adaptivity constraint B. It remains an open problem to establish such kind of lower bound for the rare policy switch model.
Numerical Experiment
In this section, we provide numerical experiments to support our theory. We run our algorithms, LSVI-UCB-Baid and LSVI-UCB-RareSSwic on synthetic linear MDP given in Example 6, and compare them with the fully adaptive baseline, LSVI-UCB (Jin et al., 2020).
Example 6.1 (Hard-to-lear linear MDP, Zhou et al. 2021b). Let > 0 be some integer and 5 (0, 1) be constant. The state space S {0, 1} consists of two states, and the action space A -= contains 2d-3 actions where each action is represented by (d -dddimnnsio
8

---

random fully adaptive
random
3.5
3.5
fully adaptive
n=
Average Regret
3.0
40
Average Regret
3.0
n=
30
n= 16
B
n 32
2.0
1.5
1.5
1.0
1.0
500
1000
15:00
2000
2500
560
1000
1500
2000
2500
Episode
Episode
(a) LSVI-UCB-Batt
LSVI-UCB LSV--UCB--areSwichh
Figure I: Plot of average regret (Tegret(Z)) v.s. the number of episodes. The results are averaged over 50 rounds of each algorithm, and the error bars are chosen to be [20%, 80%] empirical confidence intervals.
vector For each state-action pair (s, a) A, the feature vector is given by
((s = ( (-a - 5,6)
== 0, (O..... 0, 0,5,1-01
(6.1)
== 1.
- 2)) and define the corresponding vector-valued measure as For each h E [H], let y E { -
1 1,,) (8) (->7 0, 1)T
==0
(6.2)
8=1
Finally, we set 0₁ = (,, 0,-,,0,5555 26), (1 (1/(1- 28)) R for all h E [H].
is straightforward to verify that the feature vectors in (6. 1) and the vector-valued measures (6.2)
constitute valid linear MDP such that, for all A and h E [H].
8 (a. m)
(s, (0, 0),
+ (a, mh)
(s, = (0, 1),
(s, 1(s 1},
Pn(s'(s,a) =
(s, = (1.0),
1
(8, = (1,
In our experiment", we set H 10, K 2500, 5 0.35 and d = thus .A contains 1024 actions. Now apply our algorithms, LSVI-UCB-Bail and N.V--UCB-RareSwich this linear MDP instance, and compare their performance with the fully adaptive baseline LSVI-UCB (Jin et al., 2020) under different parameter settings. In detail, for LSVI-UCB-Batch. B =3=10 10, 20, 30, 40, 50 respectively; for L.SV--UCB-RareSwiii the average regret (Regret(T)) K) against the number of episodes in Figure 1. In addition to the regret of the proposed algorithms, we also plot the regret of uniformly random policy (i.c., choosing actions uniformly randomly each step) baseline.
the algorithm for we set 2, 4, 8, 16, 32. We plot
that for LSVI-UCB- Batch, when B = VK, achieves similar regret as the fully adaptive LSVI-UCB as collects more and more trajectories. For LSVI-UCB-RareSwiicch RartSwitch, constant value of yields similar order of regret compared with LSVI-UCB suggested by Theorem 5.1. By comparing Figure ((a) and 1 (bb), we can see that the performance of L.SV--UBB. RareSwitch is consistently close that of the fully-adaptive LSVI-UCB throughout the learning process, while the performance gap between LSVI-UCB-Batte and LSVI-UCB is small only when large. This suggests better adaptivity of
From Figure
than LSVI-UCB-Bate which only updates the policy at prefixed time steps, thus being not adaptive enough.
All experiments performed PC with Intel 17-9700K CPU.

---

Moreover, we can also see the trade-off between the regret and the adaptivity level: with more limited adaptivity (smaller B or larger 17) the regret gap between our algorithms and the fully adaptive LSVI-UCB becomes larger. These results indicate that our algorithms can indeed achieve comparable performance as LSVI-UCB, even under adaptivity constraints. This corroborates our theory.
Conclusions
In this work, we study online RL with linear function approximation under the adaptivity constraints. We consider both the batch learning model and the rare policy switch models and propose two new algorithms LSVI-UCB-Batch and LSVI-UCB-RareSwich for each setting. We show that LSVI-UCB Batch enjoys an H dHT/B) regret and LSVI-UCB Rareetchh enjoys an H + (/(HH))/H/) regret. Compared with the fully adaptive LSVI-UCB algo- rithm (Jin al., 2020), our algorithms can achieve the regret with much fewer number of batches/policy switches. We also prove the regret lower bound for the batch learning learning model, which suggests that the dependency on B in LSVI-UCB-Baie is tight.
For the future work, we would like to prove the regret lower bound for the rare policy switching model that explicitly depends on the given adaptivity budget B.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. Part of this work was done when DZ and QG participated the Theory of Reinforcement Learning program at the Simons Institute for the Theory of Computing in Fall 2020. DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, USS-190413, and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
ABBASI- YADKORI, Y., PÁL., D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, vol. 24.
ALTSCHULER, and TALWAR, K. (2018). Online learning switching. Conference On Learning Theory. PMLR.
finite action with limited
ARORA, R., DEKEL, O. and TEWARI, A. (2012). Online bandit learning against an adaptive adversary: from regret policy regret. arXiv preprint arXiv:1206.64400 6400.
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-based reinforcement learning with aalue-targeted regression. In International Conference Machine Learning. PMLR.
BAI Y.. XIE, T., JIANG, N. and WANG, Y.-X. (2019). Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, vol. 32.
CAL, Q. YANG, Z., JIN, C. and WANG, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning. PMLR.
CESA-BIANCHI, N., DEKEL, O. and SHAMIR, O. (2013). Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems, vol. 26.
CHEN, L., YU, Q., LAWRENCE, H. and KARBASI, A. (2020). Minimax regret of switching- constrained online convex optimization: No phase transition. In Advances in Neural Information Processing Systems, vol. 33.
DEKEL, O., DING, J., KOREN, T. and PERES, Y. (2014). Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing.
DEVROYE, L.., LUGOSI, G. and NEU, G. (2015). Random-walk perturbations for online combinato- rial optimization. IEEE Transactions on Information Theory 61 4099-4106.
10

---

DU, S. S., KAKADE, S. M., LEE, J. D., LOVETT, S., MAHAJAN, G., SUN, W. and WANG, R. (2021). Bilinear classes: A structural framework for provable generalization in International Conference on Machine Learning. PMLR.
DU, S. S., KAKADE, S. M., WANG, R. and YANG, F. (2020). Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations.
ESFANDIARI, H., KARBASI, A., MEHRABIAN, A. and MIRROKNI, V. (2021). Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence.
FOSTER, D. J., RAKHLIN, A., SIMCHI-LEVI, D. and XU, Y. (2021). Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- perspective. In Conference Learning Theory.
GAO, M., XIE, T., DU, S. S. and YANG, L. F. (2021). A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.0049)
GAO, Z., HAN, Y., REN, Z. and ZHOU, Z. (2019). Batched multi-armed bandits problem. In Advances in Neural Information Processing Systems, vol. 32.
GEULEN, S., VÓCKING, B. and WINKLER, M. (2010). Regret minimization for online buffering problems using the weighted majority algorithm. In COLT. Citeseer.
HAN, Y., ZHOU, Z., ZHOU, Z., BLANCHET, J., GLYNN, P. W. and YE, Y. (2020), Sequential batch learning in finite-action linear contextual bandits. arXiv preprint arXiv:2004.060 0.000.0006......
HE, J., ZHOU, D. and GU, Q. (2021). Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning. PMLR.
JAGHARGH, M. R. K., KRAUSE, A., LATTANZI, S. and VASSILVTISKII S. (2019). Consistent online optimization: Convex and submodular. In The 22nd International Conference on Artificial Intelligence and Statistics.
JAKSCII, T., ORTNER, R. and AUER, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11 1563-1600.
JIA, Z., YANG, L., SZEPESVARI, C. and WANG, M. (2020). Model-based reinforcement learning with value-targeted regression. Learning for Dynamics and Control. PMLR.
JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR.
KALAI, A. and VEMPALA, S. (2005). Efficient algorithms for online decision problems. Journal of Computer and System Sciences 71 291-307.
LATTIMORE, T., SZEPESVARI, C. and WEISZ, G. (2020). Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning. PMLR.
NEU, G. and PIKE-BURKE, C. (2020). A unifying view of optimism in episodic reinforcement learning. In Advances in Neural Information Processing Systems, vol. 33.
PERCHET, V., RIGOLLET, P., CHASSANG, S., SNOWBERG, E. ET AL. (2016). Batched bandit problems. The Annals of Statistics 44 660-681.
RUAN, Y., YANG, J. and ZHOU, Y. (2020). Linear bandits with limited adaptivity and learning distributional optimal design. arXiv preprint arXiv:2007.0199 09900
WANG, R., SALAKHUTDINOV, R. R. and YANG, L. (2020). Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems, vol. 33.

---

WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY, A. (2021). Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representations.
YANG, L. and WANG, M. (2019), Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning.
YANG, Z., JIN, C., WANG, Z., WANG, M. and JORDAN, M. I. (2020). On function approximation in reinforcement learning: Optimism in the face of large state spaces. In Advances in Neural Information Processing Systems, vol. 33.
ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. PMLR.
ZHANG, Z., J1, X. and Du, S. S. (2021). Is reinforcement learning more difficult than bandits? ? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory. PMLR.
ZHOU, D., GU, Q. and SZEPESVARI, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
ZIOOU, D., HE, J. and GU, Q. (2021b). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The goal of our paper is to develop general algorithms and theoretical analyses for RL with linear function approximation under adaptivity constraints. In this regard, we believe there are no socictal impacts because this paper is mainly a theoretical work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We do not use any existing assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] Our work does not involve human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zxOAQW2o5v", "reviewer": "Reviewer_BH6Q", "summary": "The paper considers RL with limited number of batches. They show that they can achieve the same regret as full adaptivity with lower number of batches. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The result seems well explored. The first result reduces the number of batches to achieve the same regret as with T batches. The second result reduces the number of policy switches. As I see, the result is interesting.\n\nThe related work is well explained, where the related work to this problem exist in different setups, and thus the overall result is not that surprising. Ofcourse, the detailed proof changes with the problem setup. The detailed technical novelty compared to the related works would have improved the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "leZsF61Q4S", "reviewer": "Reviewer_ZiZV", "summary": "This paper considers online episodic RL with linear function approximation under adaptivity constraints. In particular, two types of limited adaptivity models are considered:\n- Batch learning model, where the agent is allowed to update the policy at $B$ pre-specifed batch grids. Using a batched version of LSVI-UCB we can achieve $\\tilde{O}(\\sqrt{d^3 H^3 T} + dHT/B)$ regret with $B$ uniform batch grids, so $\\sqrt{T/dH}$ batches are sufficient. A lower bound is provided which shows the tight dependency on $B$.\n- Rare policy switch model, where the agent is allowed to switch policy ($i.e., \\pi^k \\ne \\pi^{k-1}$) for at most $B$ times. Using a modified version of the rare switching OFUL we can achieve $\\tilde{O}(\\sqrt{d^3 H^3 T[1+ T/(dH)]^{dH/B}} )$ regret with $B$ switches, so $dH \\log T$ switches are sufficient. No lower bound is provided in this setting.\n\nThe authors test out their algorithm with the hard-to-learn linear MDP (Zhou et al. 2021b) and the numerical results match theoretical gurantees.\n\n\n", "questions": "", "limitations": "", "rating": 5, "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": "All references here can be found in the original paper.\n\n### Originality\nOnline learning with adaptivity constraints has been popular recently, but ideas in this paper does not seem too novel to me. \n-  Under the batch learning model, the LSVI-UCB-Batch algorithm is literally LSVI-UCB with Q-function updates only at pre-specified batch grids. The analysis for the upper bound mostly combines techniques from Jin et al. 2020 (to control the LSVI-UCB estimation quality) and Abbasi-Yadkori et al. 2011 (to control the sum of bonus terms). The message that we can use uniform batch grids is somewhat interesting, but it's quite predictive from Han et al. 2020 that uses uniform batches in SBUCB.\n- Under the rare policy switch model, the LSVI-UCB-RareSwitch uses the determinant based criterion from Abbasi-Yadkori et al. 2011 to determine when to switch the policy. My understanding is that they basically changed the OFUL updates in the rarely switching OFUL algorithm (Abbasi-Yadkori et al. 2011) to LSVI-UCB.  Also, in my opinion, providing a reasonable lower bound in this setting could be the most novel contribution, but unfortunately the authors defer that to future work.\n\n### Quality\nOverall this paper tells a clean and complete story (except missing the lower bound for the rare policy switch model) with all arguments well supported.\n- Theory. I briefly checked the proofs in the appendix (which is generally well-orginized), and the high-level ideas look correct to me.\n- Experiments. It is good to see that the numerical experiments matches what the theory predicts (when the linear MDP assumption holds). It would be good to have some extra experiments showing how the proposed algorithms perform under different levels of model misspecification.\n\n### Clarity\nThe paper is clearly written and well organized. It's very easy to follow, and provides enough information to reproduce experimental results.\n\n### Significance\nRL under adaptivity constraints is a relevant problem in many practices, so I agree that the problem studied here can be valuable. However, as a theoretical paper, its technical contributions look somewhat limited. Also, since the paper assumes linear MDP throughout and it often does not hold in practice, the current experiment results may not be strong enough to convince practitioners that the batch schedules / policy update criterion's work well in practice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "To reiterate some concerns I listed in Main Review:\n- I'm mainly concerned with the theoretical novelty of this paper. It would be good if the authors could 1) explicitly explain the novelties in their proof techniques compared to existing work, and 2) provide high-level ideas regarding how to get a lower bound for the rare policy switch model (or some reasonable conjectures of how it should look like).\n- Since the paper assumes linear MDP throughout and it often does not hold in practice, it should be good to either 1) discuss how misspecification can affect the regret rate (Like Theorem 3.2 in Jin et al. 2020), or 2) provide some extra numerical experiments to show how the algorithms perform under misspecification.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "7bjqWav1j56", "reviewer": "Reviewer_w5L3", "summary": "This paper examines two variants of the LSVI-UCB algorithm in limited adaptiveness, which is the case where policies cannot be updated continuously. To deal with the limited adaptivity, the authors consider two models and proposes two algorithms, respectively. The LSVI-UCB-Batch algorithm corresponds to the batch learning model where we update the policy every $K/B$ epochs. The authors prove a $\\tilde{O}(\\sqrt{d^3 H^3 T} + d H T/B)$ regret and a $\\Omega(dH \\sqrt{T} + d H T/B)$ regret lower bound under this scenario. The LSVI-UCB-RareSwitch algorithm corresponds to the rare policy switch model where we update the policy when $det(\\Lambda_h^k) > \\eta det (\\Lambda_h)$. The authors prove a $\\tilde{O}(\\sqrt{d^3 H^3 T[1 + T/(dH)]^{dH/B}})$ regret for this case. Experimental results in this paper show that the performance of both algorithms is comparable to that of the LSVI-UCB algorithm, with a substantially reduced number of policy switches.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nIn Theorem 4.2, by comparing the regret lower bound with the obtained bound of LSVI-UCB-Batch in Theorem 4.1, the authors claim that the dependency of the total regret on the number of batches for the batch learning model is optimal. However, the main term $\\sqrt{d^3 H^3 T}$ does not match the lower bound of $d H \\sqrt{T}$. It would be helpful if the authors could provide a more general analysis of the batch learning model under other RL algorithms, especially those that match the lower bound.\n\nThe focus of this paper is the adaptivity constrained model. However, all the two algorithms proposed are based on the LSVI-UCB algorithm proposed in Jin et al. (2020). Theorem 4.1 of this work extends Theorem 3.1 in Jin et al. (2020) by comparing the difference between $\\Lambda_h^{b_k}$ and $\\Lambda_h^{k}$ in Lemma A.3. Theorem 5.1 of this work further combines the idea of Lemma B.2 (Lemma 12, Abbasi-Yadkori et al. 2011).\n\nThis work provides a new aspect of the LSVI-UCB algorithm, but the novelty is limited if only the LSVI-UCB algorithm is considered.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mentioned in their paper that the LSVI-UCB-RareSwitch algorithm does not have a lower bound result yet.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "4KQtGhc8LN", "reviewer": "Reviewer_LtAC", "summary": "The paper studies learning episodic finite-horizon MDPs featured by the policy adaptivity, in the linear function approximation setting. The authors consider two models of adapting policies: batch learning case and rare policy switch, propose two LSVI-UCB algorithms with policy adaptivity by generalizing the well-known LSVI-UCB algorithm and prove their regret bounds. The proposed algorithms and regret bounds generalize the well-known LSVI-UCB algorithm to have policy adaptivity. The authors also verify the effectiveness via computational experiments. \n\nThe main contribution relies on the proposed two LSVI-UCB algorithms with added policy adaptivity and their regret guarantees. ", "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": "The paper is well written. The main results are well explained and it is easy to follow proof steps. Regarding quality and clarity, I only have a few remarks. \n\n(1). It is nice to match/improve the regret bound for the LSVI-UCB algorithms constrained by the policy adaptivity. For the LSVI-UVB-RareSwitch, it would be better if you could explain the bound on the adaptivity in terms of $B$, and the role of $B$.  \n\n(2). When specialized to the tabular setting, the provided regret bounds both scale poorly in $S$, $A$, if we compare them with [1, 2]. This seems to be the state of the art, but it is worth remaking this issue. \n\n(3). As shown in Theorem 4.1 and Theorem 5.1, the regret bounds match the LSVI-UCB's regret with full adaptivity when $B=O(\\sqrt{ T })$. In practice, $B$ is often the constraint that is fixed and we are free to choose algorithm parameters, e.g. $T$. It would be useful if you could add comments on how to select algorithm parameters like $T$. What does the PAC bounds look like?\n\n(4). It is nice to see the effect of batch size $B$ on the regret in the computational experiment. Did you try other schemes adjusting $B$ like diminishing $B$ as the learned policy goes to be near-optimal? This would add more flexibility of algorithms so that practitioners like.     \n\nOriginality and Significance. The proposed LSVI-UCB algorithms are featured by adaptively switching policies. The method is new in the function approximation setting and the proofs offer a way to deal with samples from adaptively switched policies. The authors also remark a similar work [3] that could be a case of their results. It would be helpful for readers to differentiate them if you could add more comments on the technical side. \n\n\nReferences:\n\n[1] Provably Efficient Q-Learning with Low Switching Cost. NeurIPS. 2019.\n\n[2] Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition. NeurIPS. 2020.\n\n[3] A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost. arXiv:2101.00494.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies reinforcement learning in linear MDPs when the agent is limited in how frequently it can change its policy (e.g., the rarely-switching setting). This setting has been well-developed in simpler problems like online learning and linear bandits, and the theoretical results are what one would expect. The main concern is that the technical novelty is fairly low here, the paper seems to combine known techniques for linear MDPs, with techniques from the bandit literature on limited adaptivity. As such, we recommend rejecting the paper. 
Decision: Accept (Poster)