Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints

Introduction

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 prediction-from-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

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-inhomogeneous We 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. 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 adaptivity The number of batches in the batch learning model is comparable to the number of policy switches in the rare policy switch model., 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:

For the batch learning model, we propose an LSVI-UCB-Batch algorithm for linear MDPs and show that it enjoys an $\widetilde{O}(\sqrt{d^{3}H^{3}T}+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, rather than $T$ batches, to obtain the same regret $\widetilde{O}(\sqrt{d^{3}H^{3}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 $\widetilde{O}(\sqrt{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 $\widetilde{O}(\sqrt{d^{3}H^{3}T[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 $\widetilde{O}(\sqrt{d^{3}H^{3}T})$ achieved by LSVI-UCB. The number of policy switches is much smaller than that The number of policy switches is identical to the number of batches in the batch learning model. of the batch learning model when $T$ is large.

Concurrent to our work, Gao et al. 2021 proposed an algorithm achieving $\widetilde{O}(\sqrt{d^{3}H^{3}T})$ regret with a $O(dH\log K)$ global switching cost in the rare policy switch model. They also proved a $\Omega(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.

Related Works

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.

For the batch learning model, Altschuler and Talwar 2018 proved that the optimal regret bound for prediction-from-experts (PFE) is $\widetilde{O}(\sqrt{T\log n})$ when the number of batches $B=\Omega(\sqrt{T\log n})$, and $\min(\widetilde{O}(T\log n/B),T)$ when $B=O(\sqrt{T\log n})$, exhibiting a phase-transition phenomenon They call it $B$-switching budget setting, which is identical to the batch learning model.. 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 $\widetilde{O}(T/\sqrt{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 $\Omega(T/\sqrt{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(\widetilde{O}(T\sqrt{n}/\sqrt{B}),T)$. For batched linear bandits with adversarial contexts, Han et al. 2020 showed that the minimax regret bound is $\widetilde{O}(\sqrt{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(\sqrt{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 $\widetilde{O}(T^{2/3}n^{1/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 $\widetilde{O}(d\sqrt{T})$ regret with $\log(T)$ batches. Ruan et al. 2020 proposed an algorithm achieving $\widetilde{O}(\sqrt{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 $\widetilde{O}(\sqrt{H^{3}SAT})$ regret with $O(H^{3}SA\log(T/(AH)))$ local switching cost where $S$ and $A$ are the number of states and actions respectively. They also provided a $\Omega(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.

Preliminaries

We denote $T=KH$, and the regret $\text{Regret}(T)$ is defined as

2 Linear Function Approximation

For any state-action pair $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, $r_{h}(s,a)=\langle\bm{\phi}(s,a),\bm{\theta}_{h}\rangle$.

Without loss of generality, we also assume that $\|\bm{\phi}(s,a)\|_{2}\leq 1$ for all $(s,a)\in{\mathcal{S}}\times\mathcal{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.

For a linear MDP, for any policy $\pi$, there exist weight vectors $\{\mathbf{w}_{h}^{\pi}\}_{h\in[H]}$ such that for any $(s,a,h)\in{\mathcal{S}}\times\mathcal{A}\times[H]$, we have $Q_{h}^{\pi}(s,a)=\langle\bm{\phi}(s,a),\mathbf{w}_{h}^{\pi}\rangle$. Moreover, we have $\|\mathbf{w}_{h}^{\pi}\|_{2}\leq 2H\sqrt{d}$ for all $h\in[H]$.

Therefore, with the known feature mapping $\bm{\phi}(\cdot,\cdot)$, it suffices to estimate the weight vectors $\{\mathbf{w}_{h}^{\pi}\}_{h\in[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 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 $1=t_{1}<t_{2}<\cdots<t_{B}<t_{B+1}=K+1$ at the beginning of the algorithm, where $B$ is the number of batches. The $b$-th batch consists of $t_{b}$-th to $(t_{b+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

where $\pi^{k}\neq\pi^{k+1}$ means that there exists some $(h,s)\in[H]\times{\mathcal{S}}$ such that $\pi_{h}^{k}(s)\neq\pi_{h}^{k+1}(s)$. It is worth noting that $N_{\text{switch}}$ 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).

RL in the Batch Learning Model

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.

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 takes a series of batch grids $\{t_{1},\dots,t_{B+1}\}$ as input, where the $i$-th batch starts at $t_{i}$ and ends at $t_{i+1}-1$. LSVI-UCB-Batch takes the uniform batch grids as its selection of grids, i.e., $t_{i}=(i-1)\cdot\lfloor K/B\rfloor+1,i\in[B]$. By Proposition 3.3, we know that for each $h\in[H]$, the optimal value function $Q_{h}^{*}$ has the linear form $\langle\bm{\phi}(\cdot,\cdot),\mathbf{w}_{h}^{*}\rangle$. Therefore, to estimate the $Q_{h}^{*}$, it suffices to estimate $\mathbf{w}_{h}^{*}$. At the beginning of each batch, Algorithm 1 calculates $\mathbf{w}_{h}^{k}$ as an estimate of $\mathbf{w}_{h}^{*}$ by ridge regression (Line 8). Meanwhile, in order to measure the uncertainty of $\mathbf{w}_{h}^{k}$, Algorithm 1 sets the estimate $Q_{h}^{k}(\cdot,\cdot)$ as the summation of the linear function $\langle\bm{\phi}(\cdot,\cdot),\mathbf{w}_{h}^{k}\rangle$ and a Hoeffding-type exploration bonus term $\Gamma_{h}^{k}(\cdot,\cdot)$ (Line 10), which is calculated based on the confidence radius $\beta$. Then it sets the policy $\pi_{h}^{k}$ as the greedy policy with respect to $Q_{h}^{k}$. 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$, LSVI-UCB-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.

There exists a constant $c>0$ such that for any $\delta\in(0,1)$, if we set $\lambda=1$, $\beta=cdH\sqrt{\log(2dT/\delta)}$, then under Assumption 3.2, the total regret of Algorithm 1 is bounded by

Theorem 4.1 suggests that the total regret of Algorithm 1 is bounded by $\widetilde{O}(\sqrt{d^{3}H^{3}T}+dHT/B)$. When $B=\Omega(\sqrt{T/dH})$, the regret of Algorithm 1 is $\widetilde{O}(\sqrt{d^{3}H^{3}T})$, 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 $\sqrt{T/dH}$ batches, which can be much smaller than $K$.

Next, we present a lower bound to show the dependency of the total regret on the number of batches for the batch learning model.

Suppose that $B\geq(d-1)H/2$. Then for any batch learning algorithm with $B$ batches, there exists a linear MDP such that the regret over the first $T$ rounds is lower bounded by

Theorem 4.2 suggests that in order to obtain a standard $\sqrt{T}$-regret, the number of batches $B$ should be at least in the order of $\Omega(\sqrt{T})$, 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.

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 $\mathbf{w}_{h}^{*}$ by ridge regression, and then calculate the optimistic action-value function using the Hoeffding-type exploration bonus $\Gamma_{h}^{k}(\cdot,\cdot)$ along with the confidence radius $\beta$. Note that the size of the bonus term in $Q_{h}^{k}$ is determined by $\bm{\Lambda}_{h}^{k}$. Intuitively speaking, the matrix $\bm{\Lambda}_{h}^{k}$ 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 $\bm{\Lambda}_{h}^{k}$, and the upper confidence bound will become tighter (shrink) as $\det(\bm{\Lambda}_{h}^{k})$ 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; Zhou et al. 2021a).

As shown in Algorithm 2, for each stage $h\in[H]$ the algorithm maintains a matrix $\bm{\Lambda}_{h}$ which is updated at each policy switch (Line 10). For every $k\in[K]$, we denote by $b_{k}$ the episode from which the policy $\pi_{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 $\{\bm{\Lambda}_{h}^{k}\}_{h\in[H]}$ (Line 5) and then compares them with $\{\bm{\Lambda}_{h}\}_{h\in[H]}$ using the determinant-based criterion (Line 7). The agent switches the policy if there exists some $h\in[H]$ such that $\det(\bm{\Lambda}_{h}^{k})$ has increased by some pre-determined parameter $\eta>1$, followed by policy evaluation (Lines 11-13). Otherwise, the algorithm retains the previous policy (Line 16). Here the hyperparameter $\eta$ controls the frequency of policy switch, and the total number of policy switches can be bounded by a function of $\eta$.

Algorithm 2 is also a variant of LSVI-UCB proposed in Jin et al. 2020. Compared with LSVI-UCB-Batch 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 $\eta$ and therefore fits into the rare policy switch model.

We present the regret bound of Algorithm 2 in the following theorem.

There exists some constant $c>0$ such that for any $\delta\in(0,1)$, if we set $\lambda=1$, $\beta=cdH\sqrt{\log(2dT/\delta)}$ and $\eta=\left(1+K/d\right)^{dH/B}$, then the number of policy switches $N_{\text{switch}}$ in Algorithm 2 will not exceed $B$. Moreover, the total regret of Algorithm 2 is bounded by

Algorithm 2 needs to update the value of each $\det(\bm{\Lambda}_{h}^{k})$, and thanks to the special structure of $\bm{\Lambda}_{h}^{k}$, this can be done efficiently by applying the matrix determinant lemma along with the Sherman Morrison formula for efficiently updating each $(\bm{\Lambda}_{h}^{k})^{-1}$. For simplicity and clarity of the presentation, we do not include these details in the pseudo-code.

By ignoring the non-dominating term, Theorem 5.1 suggests that the total regret of Algorithm 2 is bounded by $\widetilde{O}(\sqrt{d^{3}H^{3}T[1+T/(dH)]^{dH/B}})$. Also, if we are allowed to choose $B$, we can choose $B=\Omega(dH\log T)$ to achieve $\widetilde{O}(\sqrt{d^{3}H^{3}T})$ 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=\Omega(\sqrt{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.

Concurrent to our work, Gao et al. 2021 proposed an algorithm with $B=\Omega(dH\log T)$ policy switches. Note that $B=\Omega(dH\log T)$ corresponds to choosing $\eta$ 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.

Gao et al. 2021 established a lower bound, which claims that any rare policy switch RL algorithm suffers a linear regret when $B=\widetilde{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.

Numerical Experiment

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).

Let $d>0$ be some integer and $\delta\in(0,1)$ be a constant. The state space ${\mathcal{S}}=\{0,1\}$ consists of two states, and the action space $\mathcal{A}=\{\pm 1\}^{d-3}$ contains $2^{d-3}$ actions where each action is represented by a $(d-3)$-dimensional vector $\mathbf{a}$. For each state-action pair $(s,\mathbf{a})\in{\mathcal{S}}\times\mathcal{A}$, the feature vector is given by

For each $h\in[H]$, let $\bm{\gamma}_{h}\in\{\pm\delta/(d-2)\}^{d-2}$ and define the corresponding vector-valued measure as

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 $\mathbf{a}\in\mathcal{A}$ and $h\in[H]$,

In our experiment All experiments are performed on a PC with Intel i7-9700K CPU., we set $H=10$, $K=2500$, $\delta=0.35$ and $d=13$, thus $\mathcal{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 $\eta=2,4,8,16,32$. We plot the average regret ($\text{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\approx\sqrt{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 $\eta$ 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-UCB-RareSwitch 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.

Moreover, we can also see the trade-off between the regret and the adaptivity level: with more limited adaptivity (smaller $B$ or larger $\eta$) 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-RareSwitch for each setting. We show that LSVI-UCB-Batch enjoys an $\widetilde{O}(\sqrt{d^{3}H^{3}T}+dHT/B)$ regret and LSVI-UCB-RareSwitch enjoys an $\widetilde{O}(\sqrt{d^{3}H^{3}T[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.

References

Checklist

Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes]

Did you describe the limitations of your work? [Yes]

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 societal impacts because this paper is mainly a theoretical work.

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [Yes]

Did you include complete proofs of all theoretical results? [Yes]

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [No]

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]

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]

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [N/A] We do not use any existing assets.

Did you mention the license of the assets? [N/A]

Did you include any new assets either in the supplemental material or as a URL? [N/A]

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] Our work does not involve human subjects.

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Additional Details on the Numerical Experiments

We also provide log-scaled plot of the average regret in Figure 2. We can see that the slope of the average regret curves for our proposed algorithms is similar to that of the fully adaptive LSVI-UCB, all indicating an $\widetilde{O}(1/\sqrt{T})$ scaling.

A.2 Misspecified Linear MDP

We also empirically evaluate our algorithms on linear MDP with different levels of misspecification. In particular, based on the linear MDP instance constructed in Example 6.1, we follow the definition of $\zeta$-approximate linear MDP in Jin et al. 2020, and consider a corrupted transition given by

where $f:\mathcal{A}\to[0,\zeta]$, $\zeta\in(0,1)$ and $g:\mathcal{A}\to{\mathcal{S}}$ are unknown. The two additional functions, $f$ and $g$, can be constructed by random sampling before running the algorithms, and the magnitude of $\zeta\in(0,1)$ characterizes the level of model misspecification. All the other components of the model and the experiment configurations remain the same as those in Section 6.

Under this misspecified model with levels $\zeta=0.05,0.1,0.2,0.4$, we run LSVI-UCB-Batch with $B=50$ and LSVI-UCB-RareSwitch with $\eta=8$ respectively. We plot the average regret of the algorithms in Figure 3. We can see that our algorithms can still achieve a reasonably good performance under considerable levels of model misspecification.

Appendix B Proofs of Theorem 4.1

For simplicity, we use $b_{k}$ to denote the batch $t_{b}$ satisfying $t_{b}\leq k<t_{b+1}$. Let $\Gamma_{h}^{k}(\cdot,\cdot)$ be $\beta\cdot[\bm{\phi}(\cdot,\cdot)^{\top}(\bm{\Lambda}_{h}^{k})^{-1}\bm{\phi}(\cdot,\cdot)]^{1/2}$ for any $h\in[H],k\in[K]$. First, we need the following lemma which gives $\text{Regret}(T)$ a high probability upper bound that depends on the summation of bonuses.

With probability at least $1-\delta$, the total regret of Algorithm 1 satisfies

Let $\beta$ be selected as Theorem 4.1 suggests. Then the summation of all the per-episode bonuses is bounded by

It is worth noting that the per-episode bonuses are not generated from our algorithm, but instead are some virtual terms that we introduce to facilitate our analysis. Equipped with Lemma B.2, we only need to bound the difference between delayed bonuses and per-episode bonuses. We consider all the indices $(k,h)\in[K]\times[H]$. The next lemma suggests that considering the ratio between delayed bonuses and per-episode bonuses, the ‘bad’ indices, where the ratio is large, only appear few times. This is also the key lemma of our analysis.

then we have $|\mathcal{C}|\leq dHK\log(K/d+1)/(2B\log 2)$.

With all the above lemmas, we now begin to prove our main theorem.

Suppose the event defined in Lemma B.1 holds. Then by Lemma B.1 we have that

holds with probability at least $1-\delta$. Next, we are going to bound $I$. Let $\mathcal{C}$ be the set defined in Lemma B.3. Then we have

where the first inequality holds due to the definition of $\mathcal{C}$, and the second one holds trivially. Therefore, substituting (B.2) into (B.1), the regret can be bounded by

where the second inequality holds due to Lemmas B.2 and B.3 and the fact that $T=KH$. This completes the proof. ∎

The following two lemmas in Jin et al. 2020 characterize the quality of the estimates given by the LSVI-UCB-type algorithms.

With probability at least $1-\delta$, we have $Q_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$ for all $(s,a,h,k)\in{\mathcal{S}}\times\mathcal{A}\times[H]\times[K]$.

There exists some constant $c$ such that if we set $\beta=cdH\sqrt{\log(dT/\delta)}$, then for any fixed policy $\pi$ we have for all $(s,a,h,k)\in{\mathcal{S}}\times\mathcal{A}\times[H]\times[K]$ that

which together with the definition of $Q_{h}^{b_{k}}$ and Lemma B.5 implies that

where the first inequality holds due to the algorithm design, the second one holds due to Lemma B.5. Meanwhile, notice that $0\leq V_{h}^{b_{k}}(s_{h}^{k})-V_{h}^{*}(s_{h}^{k})\leq V_{h}^{b_{k}}(s_{h}^{k})-V_{h}^{\pi^{k}}(s_{h}^{k})\leq H$, then we have

where the second inequality holds since $V_{h+1}^{b_{k}}-V_{h+1}^{\pi^{k}}\geq 0$. Recursively expand the above inequality, and we have

Therefore, the total regret can be bounded as follows

with probability at least $1-\delta/2$. By a union bound over the event $\mathcal{E}$ and the convergence of the martingale, with probability at least $1-\delta$, we have

B.2 Proof of Lemma B.2

We need the following lemma to bound the sum of the bonus terms.

We can bound the summation of $\Gamma_{h}^{k}(s_{h}^{k},a_{h}^{k})$ as follows:

where the inequality holds due to Cauchy-Schwarz inequality. Furthermore, by Lemma B.6, we have

where the second inequality holds due to Lemma C.1. That finishes our proof. ∎

B.3 Proof of Lemma B.3

First, let $\mathcal{C}_{h}$ denote the indices $k$ where $(k,h)\in\mathcal{C}$, then we have $|\mathcal{C}|=\sum_{h=1}^{H}|\mathcal{C}_{h}|$. Next we bound $|\mathcal{C}_{h}|$ for each $h$. For each $k\in\mathcal{C}_{h}$, suppose $t_{b}\leq k<t_{b+1}$, then we have $b_{k}=t_{b}$ and

where the first inequality holds since $\bm{\Lambda}_{h}^{t_{b+1}}\succeq\bm{\Lambda}_{h}^{k}$, the second inequality holds due to Lemma C.2, the third one holds due to the definition of $\mathcal{C}_{h}$. Thus, let $\widehat{\mathcal{C}}_{h}$ denote the set

we have $|\mathcal{C}_{h}|\leq\lfloor K/B\rfloor\cdot|\widehat{\mathcal{C}}_{h}|$. In the following we bound $|\widehat{\mathcal{C}}_{h}|$. Now we consider the sequence $\{\log\det(\bm{\Lambda}_{h}^{t_{b+1}})-\log\det(\bm{\Lambda}_{h}^{t_{b}})\}$. It is easy to see $\log\det(\bm{\Lambda}_{h}^{t_{b+1}})-\log\det(\bm{\Lambda}_{h}^{t_{b}})\geq 0$, therefore

where the last inequality holds due to Lemma C.1. Therefore, (B.4) and (B.5) suggest that $|\widehat{\mathcal{C}}_{h}|\leq d\log(K/d+1)/(2\log 2)$. Finally, we bound $|\mathcal{C}|$ as follows, which ends our proof.

Appendix C Proof of Theorem 5.1

Now we provide the proof of Theorem 5.1. We continue to use the notions that have been introduced in Section 4. We first give an upper bound on the determinant of $\bm{\Lambda}_{h}^{k}$.

Let $\{\bm{\Lambda}_{h}^{k},(k,h)\in[K]\times[H]\}$ be as defined in Algorithms 1 and 2. Then for all $h\in[H]$ and $k\in[K]$, we have $\det(\bm{\Lambda}_{h}^{k})\leq(\lambda+(k-1)/d)^{d}$.

where the inequality follows from the assumption that $\|\bm{\phi}(s,a)\|_{2}\leq 1$ for all $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Since $\bm{\Lambda}_{h}^{k}$ is positive semi-definite, by inequality of arithmetic and geometric means, we have

Next lemma provides a determinant-based upper bound for the ratio between the norms $\|\cdot\|_{\mathbf{A}}$ and $\|\cdot\|_{\mathbf{B}}$, where $\mathbf{A}\succeq\mathbf{B}$.

The switching cost of Algorithm 2 is characterized in the following lemma.

For any $\eta>1$ and $\lambda>0$, the global switching cost of Algorithm 2 is bounded by

Let $\{k_{1},k_{2},\cdots,k_{N_{\text{switch}}}\}$ be the episodes where the algorithm updates the policy, and we also define $k_{0}=0$. Then by the determinant-based criterion (Line 7), for each $i\in[N_{\text{switch}}]$ there exists at least one $h\in[H]$ such that

By the definition of $\bm{\Lambda}_{h}^{k}$ (Line 5), we know that $\bm{\Lambda}_{h}^{j_{1}}\succeq\bm{\Lambda}_{h}^{j_{2}}$ for all $j_{1}\geq j_{2}$ and $h\in[H]$. Thus we further have

Applying the above inequality for all $i\in[N_{\text{switch}}]$ yields

as we initialize $\bm{\Lambda}_{h}^{0}$ to be $\lambda\mathbf{I}_{d}$. While by Lemma C.1, we have

Therefore, combining the above two inequalities, we obtain that

First, substituting the choice of $\eta$ and $\lambda=1$ into the bound in Lemma C.3 yields that $N_{\text{switch}}\leq B$.

Next, we bound the regret of Algorithm 2. The result of Lemma B.1 still holds here, thus it suffices to bound the summation of the bonus terms $\Gamma_{h}^{b_{k}}(s_{h}^{k},a_{h}^{k})$. Note that $b_{k}\leq k$, and thus $\bm{\Lambda}_{h}^{k}\succeq\bm{\Lambda}_{h}^{b_{k}}$ for all $(h,k)\in[H]\times[K]$. Then by Lemma C.2 we have

for all $(h,k)\in[H]\times[K]$, where the second inequality holds due to the algorithm design. Hence, we have

where the second inequality follows from Lemma B.2. Therefore, we conclude by Lemma B.1 that

holds with probability at least $1-\delta$. Finally, substituting the choice of $\eta$ into (C.2) finishes our proof. ∎

Appendix D Proofs of Theorem 4.2

In this section, we prove the lower bound for the batch learning model.

The MDP is defined as follows. The states space ${\mathcal{S}}$ consist of has $d+1$ states $x_{0},\cdots,x_{d}$, and the action space $\mathcal{A}$ contains two actions $\mathbf{a}_{1}=(0,1)^{\top},\mathbf{a}_{2}=(1,0)^{\top}$. For any $\bm{\gamma}=(\mathbf{b}_{1,1}^{\top},\cdots,\mathbf{b}_{H,d}^{\top})^{\top}$, the feature mapping is defined as

for every $i\in[d]$ and $j\in\{1,2\}$. We further define the vector-valued measures as

for every $i\in[d]$, $j\in\{1,2\}$ and $h\in[H]$. Finally, for each $h\in[H]$, we define

Based on the above definition, we have the following transition dynamic:

For any $i\in[d]$, $x_{i}$ can only transit to $x_{0}$ or $x_{i}$.

For any episode starting from $x_{0}$, there is no regret.

For any episode starting from some $x_{i}$ with $i\in[d]$, suppose $h$ is the first stage where the agent did not choose the "right" action $\mathbf{a}=\mathbf{b}_{h,i}$, then the regret for this episode is $H-h$.

Now we show that for any deterministic algorithm The lower bound of random algorithms is lower bounded by the lower bound of deterministic algorithms according to Yao’s minimax principle. , there exists a $\bm{\gamma}\in\Gamma$ such that the regret is lower bounded by $dHT/B$. Suppose $1=t_{1}<\cdots<t_{B+1}=K+1$. We can treat all episodes in the same batch as copies of one episode, because all actions taken by the agent, transitions and rewards are the same. When $B\geq dH$, there exists $\mathcal{C}=\{c_{1,1},\cdots,c_{H,d}\}\subset[B]$ with $|\mathcal{C}|=dH$ such that

For simplicity, we denote the $i$-th batch as the collection of episodes $\{t_{i},\cdots,t_{i+1}-1\}$. Now we carefully pick the starting state $s_{0}^{i}$ for the episodes in the $i$-th batch.

For any batch whose starting episode does not belong to $\mathcal{C}$, we set the starting states of the episodes in this batch as $x_{0}$. In other words, for $i\notin\mathcal{C}$, we set $s_{0}^{t_{i}}=\cdots=s_{0}^{t_{i+1}-1}=x_{0}$.

For any batch whose starting episode lies in $\mathcal{C}$, for $i=c_{h,j}\in\mathcal{C}$, we set $s_{0}^{t_{c_{h,j}}}=\cdots=s_{0}^{t_{c_{h,j}+1}-1}=x_{j}$.

We consider the regret over batches $c_{1,i},\cdots,c_{H,i}$. Since the algorithm, transition and reward are all deterministic, then the environment can predict the agent’s selection. Specifically, suppose the agent will always take action $\mathbf{a}$ at $h$-th stage in the episodes belonging to the $c_{h,j}$-th batch, where $h\leq H/2$. Then the environment selects $\mathbf{b}_{h,j}$ as $(1,1)^{\top}-\mathbf{a}$, i.e., the other action. Therefore, the agent will always pick the “wrong" action when she firstly visits state $x_{j}$ at $h$-th stage, which occurs at least $H-h\geq H/2$ regret. Moreover, since for the batch learning model, all the actions are decided at the beginning of each batch, then the $H/2$ regret will last $(t_{c_{h,j}+1}-t_{c_{h,j}})$ episodes. Taking the summation, we have

Finally, replacing $d$ by $(d-1)/2$, we can convert our feature mapping from a $(2d+1)$-dimensional vector to a $d$-dimensional vector and complete the proof. ∎