Provably Efficient Reinforcement Learning with Linear Function Approximation under Adaptivity Constraints
Year: 2022

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 Õ( √ d3H3T +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 √ T/dH batches to obtain Õ( √ d3H3T ) regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an Õ( √ d3H3T [1 + T/(dH)]dH/B) regret, which implies that dH log T policy switches suffice to obtain the Õ( √ d3H3T ) regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al., 2020), 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.

text: √ d3H3T +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 √ T/dH batches to obtain Õ( √ d3H3T ) regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an Õ( √ d3H3T [1 + T/(dH)]dH/B) regret, which implies that dH log T policy switches suffice to obtain the Õ( √ d3H3T ) regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al., 2020), 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.

heading: 1 Introduction
text: Real-world reinforcement learning (RL) applications often come with possibly infinite state and action space, and in such a situation classical RL algorithms 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 a known feature mapping φ : S ×A → Rd, where S and A are the state space and action space, and d is the dimension of the embedding. This gives rise to the so-called linear MDP model (Yang and Wang, 2019; Jin et al., 2020). Assuming access to a generative model, efficient algorithms under
∗Equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 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 Õ( √ d3H3T ) 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 a 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 predictionfrom-experts (PFE) (Kalai and Vempala, 2005; Cesa-Bianchi et al., 2013), multi-armed bandits (MAB) (Arora et al., 2012; Cesa-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 RL, local switching cost and global switching cost, that are defined as follows
Nlocal = K−1∑ k=1 H∑ h=1 ∑ s∈S 1{πkh(s) 6= πk+1h (s)} and Nglobal = K−1∑ k=1 1{πk 6= πk+1}, (1.1)
where πk = {πkh : S → A}h∈[H] is the policy for the k-th episode of the MDP, πk 6= πk+1 means that there exists some (h, s) ∈ [H]×S such that πkh(s) 6= π k+1 h (s), and K is the number of episodes.
Then they proposed a Q-learning method with UCB2H exploration that achieves Õ( √ H3SAT ) regret with O(H3SA log(T/(AH)) local switching cost for tabular MDPs, but they did not provide tight bounds on the global switching cost.
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-inhomogeneous2 episodic linear MDPs (Jin et al., 2020) where both the transition probability and the reward function are 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 et 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 to be as small as possible. In contrast, in the rare policy switch model (Abbasi-Yadkori et al., 2011), the agent can adaptively choose when to switch the policy and therefore start a 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 is worth noting that for the same amount of adaptivity3, the rare policy switch model can be seen as 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 a 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 a 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:
2We say an episodic MDP is time-inhomogeneous if its reward and transition probability are different at different stages within each episode. See Definition 3.2 for details.
3The number of batches in the batch learning model is comparable to the number of policy switches in the rare policy switch model.
• For the batch learning model, we propose an LSVI-UCB-Batch algorithm for linear MDPs and show that it enjoys an Õ( √ d3H3T + 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 √ T/dH batches, rather than T batches, to obtain the same regret Õ( √ d3H3T ) 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 Õ( √ T ) is sharp.
• For the rare policy switch model, we propose an LSVI-UCB-RareSwitch algorithm for linear MDPs and show that it enjoys an Õ( √ d3H3T [1 + T/(dH)]dH/B) 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̃( √ d3H3T ) achieved by LSVI-UCB. The number of policy switches is much smaller than that4 of the batch learning model when T is large.
Concurrent to our work, Gao et al. (2021) proposed an algorithm achieving Õ( √ d3H3T ) regret with a O(dH logK) global switching cost in the rare policy switch model. They also proved a Ω(dH/ 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 a switching cost budget B, while their goal is to achieve the optimal rate in terms of T with as little switching cost as possible. On the other hand, for the rare policy switch model, our proposed algorithm (LSVI-UCB-RareSwitch) along its regret bound can imply their results by optimizing our regret bound concerning the switching cost budget B.
The rest of the paper is organized as follows. In Section 2 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 Section 6 we present the numerical experiment which supports our theory. Finally, we conclude our paper and point out a 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 a, we write [a]+ = max(a, 0). For a vector x ∈ Rd and matrix Σ ∈ Rd×d, we denote by ‖x‖2 the Euclidean norm and define ‖x‖Σ = √ x>Σx. For any positive integer n, we denote by [n] the set {1, . . . , n}. For any finite set A, we denote by |A| the cardinality of A. For two sequences {an} and {bn}, we write an = O(bn) if there exists an absolute constant C such that an ≤ Cbn, and we write an = Ω(bn) if there exists an absolute constant C such that an ≥ Cbn. We use Õ(·) to further hide the logarithmic factors.

heading: 2 Related Works
text: 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 a feature mapping φ : S ×A → Rd. 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 a ternary feature mapping ψ : S ×A× 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., 2021), general function approximation with Eluder dimension (Wang et al., 2020; Ayoub et 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 we 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.
4The number of policy switches is identical to the number of batches in the batch learning model.
For the batch learning model, Altschuler and Talwar (2018) proved that the optimal regret bound for prediction-from-experts (PFE) is Õ( √ T log n) when the number of batches B = Ω( √ T log n), and min(Õ(T log n/B), T ) when B = O( √ T log n), exhibiting a phase-transition phenomenon5. Here T 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 Õ(T/ √ B). Perchet et al. (2016) studied batched 2-arm bandits, and Gao et al. (2019) studied the batched multi-armed bandits (MAB). Dekel et al. (2014) proved a Ω(T/ √ 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 minimax regret bound is min(Õ(T √ n/ √ B), T ). For batched linear bandits with adversarial contexts, Han et al. (2020) showed that the minimax regret bound is Õ( √ dT+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 et al. (2021); Han et al. (2020); Ruan et al. (2020). For the rare policy switch model, the minimax optimal regret bound for PFE is O( √ T log 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 n is the number of possible actions. For MAB, the minimax regret bound has been shown to be Õ(T 2/3n1/3) by Arora et al. (2012); Dekel et al. (2014). For stochastic linear bandits, Abbasi-Yadkori et al. (2011) proposed a rarely switching OFUL algorithm achieving Õ(d √ T ) regret with log(T ) batches. Ruan et al. (2020) proposed an algorithm achieving Õ( √ dT ) regret with less than O(d log d log T ) 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̃( √ H3SAT ) regret with O(H3SA log(T/(AH))) local switching cost where S and A are the number of states and actions respectively. They also provided a Ω(HSA) 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 log(KH)) global switching cost for time-homogeneous tabular MDPs.

heading: 3 Preliminaries

heading: 3.1 Markov Decision Processes
text: We consider the time-inhomogeneous episodic Markov decision process, which is denoted by a tuple M(S,A, H, {rh}h∈[H], {Ph}h∈[H]). Here S is the state space (may be infinite), A is the action space where we allow the feasible action set to change from step to step, H is the length of each episode, and rh : S × A → [0, 1] is the reward function for each stage h ∈ [H]. At each stage h ∈ [H], Ph(s′|s, a) is the transition probability function which represents the probability for state s to transit to state s′ given action a. A policy π consists of H mappings, {πh : S → A}h∈[H]. For any policy π, we define the action-value function Qπh(s, a) and value function V π h (s) as follows:
Qπh(s, a) = rh(s, a) + Eπ [ H∑ i=h ri(si, ai) ∣∣∣∣sh = s, ah = a], V πh (s) = Qπh(s, πh(s)), where ai ∼ πi(·|si) and si+1 ∼ Pi(·|si, ai). The optimal value function V ∗h and the optimal action-value function Q∗h(s, a) are defined as V ∗(s) = supπ V π h (s) and Q ∗ h(s, a) = supπ Q π h(s, a), respectively. For simplicity, for any function V : S → R, we denote [PV ](s, a) = Es′∼P(·|s,a)V (s′). In the online learning setting, at the beginning of k-th episode, the agent chooses a policy πk and the environment selects an initial state sk1 , then the agent interacts with environment following policy πk and receives states skh and rewards rh(s k h, a k h) for h ∈ [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 πk and optimal policy π∗: Definition 3.1. We denote T = KH , and the regret Regret(T ) is defined as
Regret(T ) = K∑ k=1 [ V ∗1 (s k 1)− V π k 1 (s k 1) ] .
5They call it B-switching budget setting, which is identical to the batch learning model.

heading: 3.2 Linear Function Approximation
text: 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 a linear function of a given feature mapping φ : S × A → Rd. Formally speaking, we have the following definition for linear MDPs. Definition 3.2. M(S,A, H, {rh}h∈[H], {Ph}h∈[H]) is called a linear MDP if there exist a known feature mapping φ(s, a) : S × A → Rd, unknown measures {µh = (µ(1)h , · · · , µ (d) h )}h∈[H] over
S and unknown vectors {θh ∈ Rd}h∈[H] with maxh∈[H]{‖µh(S)‖2, ‖θh‖} ≤ √ d, such that the following holds for all h ∈ [H]:
• For any state-action-state triplet (s, a, s′) ∈ S ×A× S, Ph(s′|s, a) = 〈φ(s, a),µh(s′)〉.
• For any state-action pair (s, a) ∈ S ×A, rh(s, a) = 〈φ(s, a),θh〉.
Without loss of generality, we also assume that ‖φ(s, a)‖2 ≤ 1 for all (s, a) ∈ S ×A.
With Definition 3.2, it is shown in Jin et al. (2020) that the action-value function can be written as a linear function of the features. Proposition 3.3 (Proposition 2.3, Jin et al. 2020). For a linear MDP, for any policy π, there exist weight vectors {wπh}h∈[H] such that for any (s, a, h) ∈ S × A × [H], we have Qπh(s, a) = 〈φ(s, a),wπh〉. Moreover, we have ‖wπh‖2 ≤ 2H √ d for all h ∈ [H].
Therefore, with the known feature mapping φ(·, ·), it suffices to estimate the weight vectors {wπh}h∈[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.

heading: 3.3 Models for Limited Adaptivity
text: 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 1 = t1 < t2 < · · · < tB < tB+1 = K + 1 at the beginning of the algorithm, where B is the number of batches. The b-th batch consists of tb-th to (tb+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
Nswitch = K−1∑ k=1 1{πk 6= πk+1},
where πk 6= πk+1 means that there exists some (h, s) ∈ [H]× S such that πkh(s) 6= π k+1 h (s). It is worth noting that Nswitch 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, we 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).

heading: 4 RL in the Batch Learning Model
text: In this section, we 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.

heading: 4.1 Algorithm and Regret Analysis
text: We propose LSVI-UCB-Batch algorithm as displayed in Algorithm 1, which can be regarded as a variant of the LSVI-UCB algorithm proposed in Jin et al. (2020) yet with limited adaptivity.
Algorithm 1 LSVI-UCB-Batch Require: Number of batches B, confidence radius β, regularization parameter λ
1: Set b← 1, ti ← (i− 1) · bK/Bc+ 1, i ∈ [B] 2: for episode k = 1, 2, . . . ,K do 3: Receive the initial state sk1 4: if k = tb then 5: b← b+ 1, QkH+1(·, ·)← 0 6: for stage h = H,H − 1, . . . , 1 do 7: Λkh ← ∑k−1 τ=1 φ(s τ h, a τ h)φ(s τ h, a τ h) > + λI
8: wkh ← (Λkh)−1 ∑k−1 τ=1 φ(s τ h, a τ h) · [rh(sτh, aτh) + maxa∈AQkh+1(sτh+1, a)]
9: Γkh(·, ·)← β · [φ(·, ·)>(Λkh)−1φ(·, ·)]1/2 10: Qkh(·, ·)← min{φ(·, ·)>wkh + Γkh(·, ·), H − h+ 1}+, πkh(·)← argmaxa∈AQkh(·, a) 11: end for 12: else 13: Qkh ← Q k−1 h , π k h ← π k−1 h , ∀h ∈ [H] 14: end if 15: for stage h = 1 . . . , H do 16: Take the action akh ← πkh(skh), receive the reward rh(skh, akh) and the next state skh+1 17: end for 18: end for
Algorithm 1 takes a series of batch grids {t1, . . . , tB+1} as input, where the i-th batch starts at ti and ends at ti+1 − 1. LSVI-UCB-Batch takes the uniform batch grids as its selection of grids, i.e., ti = (i− 1) · bK/Bc+ 1, i ∈ [B]. By Proposition 3.3, we know that for each h ∈ [H], the optimal value function Q∗h has the linear form 〈φ(·, ·),w∗h〉. Therefore, to estimate the Q∗h, it suffices to estimate w∗h. At the beginning of each batch, Algorithm 1 calculates w k h as an estimate of w ∗ h by ridge regression (Line 8). Meanwhile, in order to measure the uncertainty of wkh, Algorithm 1 sets the estimate Qkh(·, ·) as the summation of the linear function 〈φ(·, ·),wkh〉 and a Hoeffding-type exploration bonus term Γkh(·, ·) (Line 10), which is calculated based on the confidence radius β. Then it sets the policy πkh as the greedy policy with respect to Q k h. Within each batch, Algorithm 1 simply keeps the policy used in the previous episode without updating (Line 13). Apparently, the number of batches of Algorithm 1 is B.
Here we would like to make a comparison between our LSVI-UCB-Batch and other related algorithms. The most related algorithm is LSVI-UCB proposed in Jin et al. (2020). The main difference between LSVI-UCB-Batch and LSVI-UCB is the introduction of batches. In detail, when B = K, LSVIUCB-Batch degenerates to LSVI-UCB. Another related algorithm is the SBUCB algorithm proposed by Han et al. (2020). Both LSVI-UCB-Batch and SBUCB take uniform batch grids as the selection of batches. The difference is 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 c > 0 such that for any δ ∈ (0, 1), if we set λ = 1, β = cdH √ log(2dT/δ), then under Assumption 3.2, the total regret of Algorithm 1 is bounded by
Regret(T ) ≤2H √ T log ( 2dT
δ
) + dHT
2B log 2 log
( T
dH + 1
)
+ 4c √ 2d3H3T log ( 2dT
δ
) log ( T
dH + 1 ) with probability at least 1− δ.
Theorem 4.1 suggests that the total regret of Algorithm 1 is bounded by Õ( √ d3H3T + dHT/B). When B = Ω( √ T/dH), the regret of Algorithm 1 is Õ( √ d3H3T ), which is 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 1 only requires √ T/dH batches, which can be much smaller than K.
Algorithm 2 LSVI-UCB-RareSwitch Require: Policy switch parameter η, confidence radius β, regularization parameter λ
1: Initialize Λh = Λ0h = λId for all h ∈ [H] 2: for episode k = 1, 2, . . . ,K do 3: Receive the initial state sk1 4: for stage h = 1, 2, · · · , H do 5: Λkh ← ∑k−1 τ=1 φ(s τ h, a τ h)φ(s τ h, a τ h) > + λId 6: end for 7: if ∃h ∈ [H],det(Λkh) > η · det(Λh) then 8: QkH+1(·, ·)← 0 9: for step h = H,H − 1, · · · , 1 do
10: Λh ← Λkh 11: wkh ← (Λkh)−1 ∑k−1 τ=1 φ(s τ h, a τ h) · [rh(sτh, aτh) + maxa∈AQkh+1(sτh+1, a)] 12: Γkh(·, ·)← β · [φ(·, ·)>(Λkh)−1φ(·, ·)]1/2 13: Qkh(·, ·)← min{φ(·, ·)>wkh + Γkh(·, ·), H − h+ 1}+, πkh(·)← argmaxa∈AQkh(·, a) 14: end for 15: else 16: Qkh ← Q k−1 h , π k h ← π k−1 h , ∀h ∈ [H] 17: end if 18: for stage h = 1 . . . , H do 19: Take the action akh ← πkh(skh), receive the reward rh(skh, akh) and the next state skh+1 20: end for 21: end for
Next, we present a lower bound to show the dependency of the total regret on the number of batches for the batch learning model. Theorem 4.2. Suppose thatB ≥ (d−1)H/2. Then for any batch learning algorithm withB batches, there exists a linear MDP such that the regret over the first T rounds is lower bounded by
Regret(T ) = Ω(dH √ T + dHT/B).
Theorem 4.2 suggests that in order to obtain a standard √ T -regret, the number of batches B should be at least in the order of Ω( √ T ), which is similar to its counterpart for batched linear bandits (Han et al., 2020).

heading: 5 RL in the Rare Policy Switch Model
text: 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.

heading: 5.1 Algorithm and Regret Analysis
text: We first present our second algorithm, LSVI-UCB-RareSwitch, as illustrated in Algorithm 2. Again, due to the nature of linear MDPs, we only need to estimate w∗h by ridge regression, and then calculate the optimistic action-value function using the Hoeffding-type exploration bonus Γkh(·, ·) along with the confidence radius β. Note that the size of the bonus term in Qkh is determined by Λ k h. Intuitively speaking, the matrix Λkh 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 a significant amount of additional information. This is reflected by the determinant of Λkh, and the upper confidence bound will become tighter (shrink) as det(Λkh) increases. The determinant based criterion is 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), UCRL2 algorithm for tabular MDPs (Jaksch et al., 2010), and UCLK/UCLK+ for linear mixture MDPs in the discounted setting (Zhou et al., 2021b,a).
As shown in Algorithm 2, for each stage h ∈ [H] the algorithm maintains a matrix Λh which is updated at each policy switch (Line 10). For every k ∈ [K], we denote by bk the episode from which
the policy πk 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 {Λkh}h∈[H] (Line 5) and then compares them with {Λh}h∈[H] using the determinant-based criterion (Line 7). The agent switches the policy if there exists some h ∈ [H] such that det(Λkh) has increased by some pre-determined parameter η > 1, followed by policy evaluation (Lines 11-13). Otherwise, the algorithm retains the previous policy (Line 16). Here the hyperparameter η controls the frequency of policy switch, and the total number of policy switches can be bounded by a function of η.
Algorithm 2 is also a variant of LSVI-UCB proposed in Jin et al. (2020). Compared with LSVI-UCBBatch in Algorithm 1 for the batch learning model, LSVI-UCB-RareSwitch adaptively decides when to switch the policy and can be tuned by the hyperparameter η 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 c > 0 such that for any δ ∈ (0, 1), if we set λ = 1, β = cdH √ log(2dT/δ) and η = (1 +K/d)dH/B , then the number of policy switches Nswitch in Algorithm 2 will not exceed B. Moreover, the total regret of Algorithm 2 is bounded by
Regret(T ) ≤ 2H √ T log ( 2dT
δ
) + 2c √ 2d3H3T · √( T
dH + 1
) dH B
log
( T
dH + 1
) log ( 2dT
δ ) (5.1)
with probability at least 1− δ.
A few remarks are in order.
Remark 5.2. Algorithm 2 needs to update the value of each det(Λkh), and thanks to the special structure of Λkh, this can be done efficiently by applying the matrix determinant lemma along with the Sherman Morrison formula for efficiently updating each (Λkh)
−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 Õ( √ d3H3T [1 + T/(dH)]dH/B). Also, if we are allowed to choose B, we can choose B = Ω(dH log T ) to achieve Õ( √ d3H3T ) regret, which is the same as that of LSVI-UCB in Jin et al. (2020). This also significantly improves upon Algorithm 1 when T is sufficiently large since previously we need B = Ω( √ T/dH). Our result exhibits a 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 = Ω(dH log T ) policy switches. Note that B = Ω(dH log T ) corresponds to choosing η 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 B. 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 a lower bound, which claims that any rare policy switch RL algorithm suffers a linear regret when B = õ(dH). However, unlike our lower bound for the batch learning model (Theorem 4.2), their result does not provide a fine-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.

heading: 6 Numerical Experiment
text: In this section, we provide numerical experiments to support our theory. We run our algorithms, LSVI-UCB-Batch and LSVI-UCB-RareSwitch, on a synthetic linear MDP given in Example 6.1, and compare them with the fully adaptive baseline, LSVI-UCB (Jin et al., 2020).
Example 6.1 (Hard-to-learn linear MDP, Zhou et al. 2021b). Let d > 0 be some integer and δ ∈ (0, 1) be a constant. The state space S = {0, 1} consists of two states, and the action space A = {±1}d−3 contains 2d−3 actions where each action is represented by a (d − 3)-dimensional
vector a. For each state-action pair (s,a) ∈ S ×A, the feature vector is given by
φ(s, a) = { (−a>, 1− δ, δ)> s = 0, (0, . . . , 0, δ, 1− δ) s = 1. (6.1)
For each h ∈ [H], let γh ∈ {±δ/(d− 2)}d−2 and define the corresponding vector-valued measure as
µh(s) =
{ (γ>h , 1, 0) > s = 0
(−γ>h , 0, 1)> s = 1 . (6.2)
Finally, we set θh ≡ (0, . . . , 0,−δ/(1− 2δ), (1− δ)/(1− 2δ)) ∈ Rd for all h ∈ [H].
It is straightforward to verify that the feature vectors in (6.1) and the vector-valued measures in (6.2) constitute a valid linear MDP such that, for all a ∈ A and h ∈ [H],
rh(s,a) = 1{s = 1}, Ph(s′|s,a) =  1− δ − 〈a, γh〉 (s, s′) = (0, 0), δ + 〈a,γh〉 (s, s′) = (0, 1), δ (s, s′) = (1, 0),
1− δ (s, s′) = (1, 1).
In our experiment6, we set H = 10, K = 2500, δ = 0.35 and d = 13, thus A contains 1024 actions. Now we apply our algorithms, LSVI-UCB-Batch and LSVI-UCB-RareSwitch, to 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, we run the algorithm for B = 10, 20, 30, 40, 50 respectively; for LSVI-UCB-RareSwitch, we set η = 2, 4, 8, 16, 32. We plot 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 a uniformly random policy (i.e., choosing actions uniformly randomly in each step) as a baseline. From Figure 1, we can see that for LSVI-UCB-Batch, when B ≈ √ K, it achieves a similar regret as the fully adaptive LSVI-UCB as it collects more and more trajectories. For LSVI-UCB-RareSwitch, a constant value of η yields a similar order of regret compared with LSVI-UCB as suggested by Theorem 5.1. By comparing Figure 1(a) and 1(b), we can see that the performance of LSVI-UCBRareSwitch is consistently close to that of the fully-adaptive LSVI-UCB throughout the learning process, while the performance gap between LSVI-UCB-Batch and LSVI-UCB is small only when k is large. This suggests a better adaptivity of LSVI-UCB-RareSwitch than LSVI-UCB-Batch, which only updates the policy at prefixed time steps, thus being not adaptive enough.
6All experiments are performed on a PC with Intel i7-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 η) 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.

heading: 7 Conclusions
text: 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-RareSwitch for each setting. We show that LSVI-UCB-Batch enjoys an Õ( √ d3H3T + dHT/B) regret and LSVI-UCB-RareSwitch enjoys
an Õ( √ d3H3T [1 + T/(dH)]dH/B) regret. Compared with the fully adaptive LSVI-UCB algorithm (Jin et al., 2020), our algorithms can achieve the same regret with a 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-Batch 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, IIS-1904183 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.

Review summaries:
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.

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.   The main contribution relies on the proposed two LSVI-UCB algorithms with added policy adaptivity and their regret guarantees. 

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.  

This paper considers online episodic RL with linear function approximation under adaptivity constraints. In particular, two types of limited adaptivity models are considered: - 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$. - 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.  The authors test out their algorithm with the hard-to-learn linear MDP (Zhou et al. 2021b) and the numerical results match theoretical gurantees.