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 to 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., 2011): 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- iim-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 (T)) 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 ! (2H))) 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 iimomonooooeess 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 (s''. 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 (Pr (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 0 [ 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 [Ht (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 . h 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 (Anhee( 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 TTddH)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
=
(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 13, thus .A contains 1024 actions. Now apply our algorithms, LSVI-UCB-Bail and N.V--UCB-RareSwichh 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 -areetchh 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-Bate 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": "XN5jpk4gfAJ", "reviewer": "Reviewer_Xhcq", "summary": "This paper proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch algorithms which can satisfy adaptivity constraints, i.e., the number of policy changes during learning is small. The authors proved regret bounds showing that with a small number of switches, the algorithms can achieve same regret bound as LSVI-UCB.", "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": "Pros:\n\nI think this paper is very well-written and easy to follow. The results are rigorously presented. I did not check the proofs but the results seem to be correct and aligned with prior works.\n\nCons:\n\nI think the novelty of the algorithm design is relatively limited. The LSVI-UCB-Batch is essentially the same as LSVI-UCB with the only difference being that the policy is updated every K/B episodes rather than every episode. The determinant based criterion in LSVI-UCB-RareSwitch also appeared in several prior works.\n\nThe theory only applies to line MDP which is a bit limited in my opinion. But I understand that the recent line of work on provably efficient RL needs such assumption, especially for value-iteration type of algorithms.\n\nMinor:\n\nLine 10 in Algorithm 1: superscript “+” is not defined, similar thing for Algorithm 2.\n\nLine 222:  “In detail, when B = T, LSVI-UCB-Batch degenerates to LSVI-UCB”: should it be T or K? I think by definition B cannot be larger than K. Similar things in lines 233-234.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not see many discussions on the limitations of this work. I did not see any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KoBmPEBlBk6", "reviewer": "Reviewer_FRs1", "summary": "This paper studies linear mdp under two adaptivity models: rare policy switch model and batch learning model. They achieve the same regret as the fully adaptivity setting (LSVI-UCB) with much less number of policy switches ( e.g., in the rare policy switch model, it is $dH \\log T$ vs $T$)", "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": "**Strong points** \n-\tA new result of a sample efficient linear RL with limited adaptivity that seems more comprehensive (as it studies batch learning model as well) than the concurrent work Gao et al. 2021. It also encompasses a result in Gao et al. 2021. \n- This is a complete study with two proposed algorithms and corresponding regret analysis, and lower bound analysis. \n\n**Weak points**\n-\tThe approach and analysis are quite simple as they adopt from Abbasi-Yadkori et al. 2021, Jin et al. 2020 that I am not sure if there is any new technical idea.  For example, Algorithm 2 in the present paper is the same as the algorithm in Figure 3 in Abbasi-Yadkori et al. 2021 except that the former is for linear MDP and the latter is for linear bandits. \n\n**Minor comments**\n-\tFig 1: the colours for B=50 and B=15 are difficult to distinguish. Moreover, it would be nice to have a baseline line there to give the readers an idea of how much regret is “bad”.  The current experimental result shows that LSVI-UCB-Batch and LSVI-UCB-RareSwtich underperform their full adaptivity counterpart LSVI-UCB. Without a baseline, it could be difficult to know if such a gap is substaintial. Moreover, line 312, the authors say that LSVI-UCB-Batch achieves the similar regret as LSVI-UCB, but Fig 1.(a) does not indicate so. \n\n- The current experiment only shows two configurations (B=15,50 and eta=4,8) for each proposed algorithm. It would be an addition if the results for more configurations are presented to show the trade-offs between regret and adaptivity level. \n\n**Questions**: \n-\tLine 88-91: “Our goal is to design efficient RL algorithms under a switching cost budge B while their goal is to achieve the optimal rate in terms of T”: How are these two goals different? \n-\tI would like the authors to comment on the difference between Algorithm 2 of this paper and Algorithm 1 of Gao et al. 2021, and compare their advantages/efficiency in solving the adaptivity constraint problem. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and social impact of their work.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "No concern. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "JtZHKi-iaXo", "reviewer": "Reviewer_3Uwm", "summary": "This paper considers sample-efficient RL in linear MDPs under adaptivity constraints, that is, the number of policy switches during the algorithm execution is constrained to be low. The paper considers two types of adaptivity constraint: the batch learning model (in which the switching schedule is predetermined), and the rare policy switch model (in which the switching schedule can be adaptive). The main contributions of this paper are low-regret algorithms for linear MDPs in both versions of low switching models.", "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": "This paper is an extension of the previous works on low switching cost learning in bandits and tabular MDPs. I think overall the results make good contributions to the literature and contain some interesting theoretical insights. The algorithms for both switching models are fairly clean (the Batch learning model just uses a delayed Q update; the Rare Policy Switch model uses an adaptive switching criterion that depends on the determinant of the cumulative feature covariance matrix). These are analogous to (and not exactly the same as) the per-state exponential switching schedule of Bai et al. 2019 for tabular MDPs. \n\nFurthermore the paper has a small numerical experiment section, which I do appreciate as for an RL theory paper. The particular experiments here show that the low switching cost algorithms do achieve sublinear regret. I wonder if the authors could check whether the avg regret scales as $O(1/\\sqrt{T})$? (e.g. by looking at slope on log scale)?\n\nMy only concern is that the results sound a bit incremental --- I wonder in what sense are the techniques new and different from existing analysis on low switching cost? E.g. by looking at Lemmas A.1, A.2 I get the feeling that the consequence of delayed update here in linear MDP is easier to analyze than in tabular cases, because of the global switching schedule (so that there is only $b_k$, not something like $b_k(s, a)$). Maybe Lemma A.3 and Lemma B.3 may be the key non-trivial ones that allow the result? Could the authors discuss some of the intuitions about these Lemmas and in particular which parts are new? For example, how Lemma B.3 compares with the per-state exponential scheduling in existing low switching cost algorithms for tabular MDPs. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8Ref3E6d4DT", "reviewer": "Reviewer_ZCnH", "summary": "This paper proposed two algorithms for reinforcement learning with linear function approximation under adaptivity constraints.", "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": "Strengths:\nThis papers proves upper bounds on the regret in both the batch learning model and rare policy switch model, which illustrates a trade-off between the regret and global switching cost. It also shows a lower bound in the batch learning model. \n\nWeakness / comments:\n1. It seems that the upper bound in [1] is a special case of Theorem 5.1 when the dependency of regret on $T$ is $\\sqrt{T}$. But the paper does not explain whether this difference of theoretical results comes from the design of the algorithm or the proof techniques. A clearer and complete comparison between [1] and the current paper would be helpful. \n\n2. The lower bound in Theorem 4.2 assumes $B\\geq(d-1)H/2$, while in order to make the upper bound in Theorem 4.1 on the order of $\\widetilde{O}(\\sqrt{d^3H^3T})$, it is required that $B=\\Omega(\\sqrt{T/dH})$. Does this mean the upper bound and lower bound only match when $T=O(d^3H^3)$? If it does, how restrictive is this condition?\n\n[1] Gao, Minbo, et al. \"A provably efficient algorithm for linear markov decision process with low switching cost.\" arXiv preprint arXiv:2101.00494 (2021).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, and I think there is no potential negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch algorithms which can satisfy adaptivity constraints, i.e., the number of policy changes during learning is small. The authors proved regret bounds showing that with a small number of switches, the algorithms can achieve same regret bound as LSVI-UCB. There is a consensus that the paper should be accepted. 
Decision: Accept (Poster)