Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension

Introduction

In reinforcement learning (RL), we study how an agent maximizes the cumulative reward by interacting with an unknown environment. RL finds enormous applications in a wide variety of domains, e.g., robotics (Kober et al., 2013), education (Koedinger et al., 2013), gaming-AI (Shalev-Shwartz et al., 2016), etc. The unknown environment in RL is often modeled as a Markov decision process (MDP), in which there is a set of states $\mathcal{S}$ that describes all possible status of the environment. At a state $s\in\mathcal{S}$, an agent interacts with the environment by taking an action $a$ from an action space $\mathcal{A}$. The environment then transits to another state $s^{\prime}\in\mathcal{S}$ which is drawn from some unknown transition distribution, and the agent also receives an immediate reward. The agent interacts with the environment episodically, where each episode consists of $H$ steps. The goal of the agent is to interact with the environment strategically such that after a certain number of interactions, sufficient information is collected so that the agent can act nearly optimally afterward. The performance of an agent is measured by the regret, which is defined as the difference between the total rewards collected by the agent and those a best possible agent would collect.

Without additional assumptions on the structure of the MDP, the best possible algorithm achieves a regret bound of $\widetilde{\Theta}(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$Throughout the paper, we use $\widetilde{O}(\cdot)$ to suppress logarithmic factors. (Azar et al., 2017), where $T$ is the total number of steps the agent interacts with the environment. In other words, the algorithm learns to interact with the environment nearly as well as an optimal agent after roughly $H|\mathcal{S}||\mathcal{A}|$ steps. This regret bound, however, can be unacceptably large in practice. E.g., the game of Go has a state space with size $3^{361}$, and the state space of certain robotics applications can even be continuous. Practitioners apply function approximation schemes to tackle this issue, i.e., the value of a state-action pair is approximated by a function which is able to predict the value of unseen state-action pairs given a few training samples. The most commonly used function approximators are deep neural networks (DNN) which have achieved remarkable success in playing video games (Mnih et al., 2015), the game of Go (Silver et al., 2017), and controlling robots (Akkaya et al., 2019). Nevertheless, despite the outstanding achievements in solving real-world problems, no convincing theoretical guarantees were known about RL with general value function approximators like DNNs.

Does RL with general function approximation learn to interact with an unknown environment provably efficiently?

There is a long line of research on the sample complexity and regret bound for RL in the tabular setting. See, e.g., (Kearns and Singh, 2002; Kakade, 2003; Strehl et al., 2006, 2009; Jaksch et al., 2010; Szita and Szepesvári, 2010; Azar et al., 2013; Lattimore and Hutter, 2014; Dann and Brunskill, 2015; Osband and Van Roy, 2016; Osband et al., 2019; Agrawal and Jia, 2017; Azar et al., 2017; Sidford et al., 2018; Dann et al., 2019; Jin et al., 2018; Zanette and Brunskill, 2019; Zhang et al., 2020; Wang et al., 2020) and references therein. In particular, Jaksch et al. (2010) proved a tight regret lower bound $\Omega(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$ and Azar et al. (2017) showed the first asymptotically tight regret upper bound $\widetilde{O}(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$. Although these algorithms achieve asymptotically tight regret bounds, they can not be applied in problems with huge state space due to the linear dependency on $\sqrt{|\mathcal{S}|}$ in the regret bound. Moreover, the regret lower bound $\Omega(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$ demonstrates that without further assumptions, RL with huge state space is information-theoretically hard to solve. In this paper, we exploit the structure that the value functions lie in a function class with bounded complexity and devise an algorithm whose regret bound scales polynomially in the complexity of the function class instead of the number of states.

Bandits.

Another line of research studies bandits problems with linear function approximation (Dani et al., 2008; Abbasi-Yadkori et al., 2011; Li et al., 2019). These algorithms are later generalized to the generalized linear model (Filippi et al., 2010; Li et al., 2017). A novel work of Russo and Van Roy (2013) studies bandits problems with general function approximation and proves that UCB-type algorithms and Thompson sampling achieve a regret bound of $\widetilde{O}(\sqrt{\dim_{E}\cdot\log(\mathcal{N})T})$ where $\dim_{E}$ is the eluder dimension of the function class and $\mathcal{N}$ is the covering number of the function class. In this paper we study the RL setting with general value function approximation, and the regret bound of our algorithm also depends on the eluder dimension and the log-covering number of the function class. However, we would like to stress that the RL setting is much more complicated than the bandits setting, since the bandits setting is a special case of the RL setting with planning horizon $H=1$ and thus there is no state transition in the bandits setting.

RL with Linear Function Approximation.

Recently there has been great interest in designing and analyzing algorithms for RL with linear function approximation. See, e.g., (Yang and Wang, 2019, 2020; Jin et al., 2019; Cai et al., 2020; Modi et al., 2019; Jia et al., 2019; Zanette et al., 2019; Du et al., 2019; Wang et al., 2019; Du et al., 2020a; Zanette et al., 2020; Du et al., 2020b). These papers design provably efficient algorithms under the assumption that there is a well-designed feature extractor available to the agent and the value function or the model can be approximated by a linear function or a generalized linear function of the feature vectors. Moreover, the algorithm in (Zanette et al., 2020) requires solving the Planning Optimization Program which could be computationally intractable. In this paper, we study RL with general function approximation in which case a feature extractor may not even be available, and our goal is to develop an efficient (both computationally and statistically) algorithm with provable regret bounds without making explicit assumptions on the model.

RL with General Function Approximation.

It has been shown empirically that combining RL algorithms with neural network function approximators could lead to superior performance on various tasks (Mnih et al., 2013; Schaul et al., 2016; Wang et al., 2016; Van Hasselt et al., 2016; Silver et al., 2017; Akkaya et al., 2019). Theoretically, Osband and Van Roy (2014) analyzed the regret bound of Thompson sampling when applied to RL with general function approximation. Compared to our result, Osband and Van Roy (2014) makes explicit model-based assumptions (the transition operator and the reward function lie in a function class) and their regret bound depends on the global Lipschitz constant. In contrast, in this paper we focus on UCB-type algorithms with value-based assumptions, and our regret bound does not depend on the global Lipschitz constant. Recently, Ayoub et al. (2020) proposed an algorithm for model-based RL with general function approximation based on value-targeted regression, and the regret bound of their algorithm also depends on the eluder dimension. On the contrary, in this paper we focus on value-based RL algorithms.

Recent theoretical progress has produced provably sample efficient algorithms for RL with general value function approximation, but many of these algorithms are relatively impractical. In particular, (Jiang et al., 2017; Sun et al., 2019; Dong et al., 2020) devised algorithms whose sample complexity or regret bound can be upper bounded in terms of the Bellman rank or the witness rank. However, these algorithms are not computationally efficient. The algorithm in (Du et al., 2020b) can also be applied in RL with general function approximation. However, their algorithms require the transition of the MDP to be deterministic. There is also a line of research analyzing Approximate Dynamic Programming (ADP) in RL with general function approximation (Bertsekas and Tsitsiklis, 1996; Munos, 2003; Szepesvári and Munos, 2005; Antos et al., 2008; Munos and Szepesvári, 2008; Chen and Jiang, 2019). These papers focus on the batch RL setting, and there is no exploration components in the algorithms. The sample complexity of these algorithms usually depends on the concentrability coefficient and is thus incomparable to our results.

Preliminaries

Throughout the paper, for a positive integer $N$, we use $[N]$ to denote the set $\{1,2,\ldots,N\}$.

A policy $\pi$ chooses an action $a\in\mathcal{A}$ based on the current state $s\in\mathcal{S}$ and the time step $h\in[H]$. Formally, $\pi=\{\pi_{h}\}_{h=1}^{H}$ where for each $h\in[H]$, $\pi_{h}:\mathcal{S}\to\mathcal{A}$ maps a given state to an action. The policy $\pi$ induces a trajectory

where $s_{1}\sim\mu$, $a_{1}=\pi_{1}(s_{1})$, $r_{1}=r(s_{1},a_{1})$, $s_{2}\sim P(s_{1},a_{1})$, $a_{2}=\pi_{2}(s_{2})$, etc.

An important concept in RL is the $Q$-function. Given a policy $\pi$, a level $h\in[H]$ and a state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, the $Q$-function is defined as

Similarly, the value function of a given state $s\in\mathcal{S}$ is defined as

We use $\pi^{*}$ to denote an optimal policy, i.e., $\pi^{*}$ is a policy that maximizes

We also denote $Q_{h}^{*}(s,a)=Q_{h}^{\pi^{*}}(s,a)$ and $V_{h}^{*}(s)=V_{h}^{\pi^{*}}(s)$.

In the episodic MDP setting, the agent aims to learn the optimal policy by interacting with the environment during a number of episodes. For each $k\in[K]$, at the beginning of the $k$-th episode, the agent chooses a policy $\pi^{k}$ which induces a trajectory, based on which the agent chooses policies for later episodes. We assume $K$ is fixed and known to the agent, though our algorithm and analysis can be readily generalized to the case that $K$ is unknown in advance. Throughout the paper, we define $T:=KH$ to be the total number of steps that the agent interacts with the environment.

We adopt the following regret definition in this paper.

The regret of an algorithm $\mathcal{A}$ after $K$ episodes is defined as

where $\pi^{k}$ is the policy played by algorithm $\mathcal{A}$ at the $k$-th episode.

Additional Notations.

Our Assumptions.

Our algorithm (Algorithm 1) receives a function class $\mathcal{F}\subseteq\{f:\mathcal{S}\times\mathcal{A}\rightarrow[0,H+1]\}$ as input. We make the following assumption on the $Q$-functions throughout the paper.

For any $V:\mathcal{S}\rightarrow[0,H]$, there exists $f_{V}\in\mathcal{F}$ which satisfies

The complexity of $\mathcal{F}$ determines the learning complexity of the RL problem under consideration. To characterize the complexity of $\mathcal{F}$, we use the following definition of eluder dimension which was first introduced in (Russo and Van Roy, 2013) to characterize the complexity of different function classes in bandits problems.

Let $\varepsilon\geq 0$ and $\mathcal{Z}=\{(s_{i},a_{i})\}_{i=1}^{n}\subseteq\mathcal{S}\times\mathcal{A}$ be a sequence of state-action pairs.

A state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$ is $\varepsilon$-dependent on $\mathcal{Z}$ with respect to $\mathcal{F}$ if any $f,f^{\prime}\in\mathcal{F}$ satisfying $\|f-f^{\prime}\|_{\mathcal{Z}}\leq\varepsilon$ also satisfies $|f(s,a)-f^{\prime}(s,a)|\leq\varepsilon$.

An $(s,a)$ is $\varepsilon$-independent of $\mathcal{Z}$ with respect to $\mathcal{F}$ if $(s,a)$ is not $\varepsilon$-dependent on $\mathcal{Z}$.

We further assume the function class $\mathcal{F}$ and the state-action pairs $\mathcal{S}\times\mathcal{A}$ have bounded complexity in the following sense.

For any $\varepsilon>0$, the following holds:

there exists an $\varepsilon$-cover $\mathcal{C}(\mathcal{F},\varepsilon)\subseteq\mathcal{F}$ with size $|\mathcal{C}(\mathcal{F},\varepsilon)|\leq\mathcal{N}(\mathcal{F},\varepsilon)$, such that for any $f\in\mathcal{F}$, there exists $f^{\prime}\in\mathcal{C}(\mathcal{F},\varepsilon)$ with $\|f-f^{\prime}\|_{\infty}\leq\varepsilon$;

there exists an $\varepsilon$-cover $\mathcal{C}(\mathcal{S}\times\mathcal{A},\varepsilon)$ with size $|\mathcal{C}(\mathcal{S}\times\mathcal{A},\varepsilon)|\leq\mathcal{N}(\mathcal{S}\times\mathcal{A},\varepsilon)$, such that for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, there exists $(s^{\prime},a^{\prime})\in\mathcal{C}(\mathcal{S}\times\mathcal{A},\varepsilon)$ with $\max_{f\in\mathcal{F}}|f(s,a)-f(s^{\prime},a^{\prime})|\leq\varepsilon$.

Assumption 2 requires both the function class $\mathcal{F}$ and the state-action pairs $\mathcal{S}\times\mathcal{A}$ have bounded covering numbers. Since our regret bound depends logarithmically on $\mathcal{N}(\mathcal{F},\cdot)$ and $\mathcal{N}(\mathcal{S}\times\mathcal{A},\cdot)$, it is acceptable for the covers to have exponential size. In particular, when $\mathcal{S}$ and $\mathcal{A}$ are finite, it is clear that $\log\mathcal{N}(\mathcal{F},\varepsilon)=\widetilde{O}(|\mathcal{S}||\mathcal{A}|)$ and $\log\mathcal{N}(\mathcal{S}\times\mathcal{A},\varepsilon)=\log(|\mathcal{S}||\mathcal{A}|)$. For the case of $d$-dimensional linear functions and generalized linear functions, $\log\mathcal{N}(\mathcal{F},\varepsilon)=\widetilde{O}(d)$ and $\log\mathcal{N}(\mathcal{S}\times\mathcal{A},\varepsilon)=\widetilde{O}(d)$. For quadratic functions, $\log\mathcal{N}(\mathcal{F},\varepsilon)=\widetilde{O}(d^{2})$ and $\log\mathcal{N}(\mathcal{S}\times\mathcal{A},\varepsilon)=\widetilde{O}(d)$.

Algorithm

The full algorithm is formally presented in Algorithm 1. From a high-level point of view, our algorithm resembles least-square value iteration (LSVI) and falls in a similar framework as the algorithm in (Jin et al., 2019; Wang et al., 2019). At the beginning of each episode $k\in[K]$, we maintain a replay buffer $\{(s_{h}^{\tau},a_{h}^{\tau},r_{h}^{\tau})\}_{(h,\tau)\in[H]\times[k-1]}$ which contains all existing samples. We set $Q^{k}_{H+1}=0$, and calculate $Q^{k}_{H},Q^{k}_{H-1},\ldots,Q^{k}_{1}$ iteratively as follows. For each $h=H,H-1,\ldots,1$,

Here, $b^{k}_{h}(\cdot,\cdot)$ is a bonus function to be defined shortly. The above equation optimizes a least squares objective to estimate the next step value. We then play the greedy policy with respect to $Q^{k}_{h}$ to collect data for the $k$-th episode. The above procedure is repeated until all the $K$ episodes are completed.

Stable Upper-Confidence Bonus Function.

With more collected data, the least squares predictor is expected to return a better approximate the true $Q$-function. To encourage exploration, we carefully design a bonus function $b^{k}_{h}(\cdot,\cdot)$ which guarantees that, with high probability, $Q^{k}_{h+1}(s,a)$ is an overestimate of the one-step backup. The bonus function $b^{k}_{h}(\cdot,\cdot)$ is guaranteed to tightly characterize the estimation error of the one-step backup

is the value function of the next step. The bonus function $b^{k}_{h}(\cdot,\cdot)$ is designed by carefully prioritizing important data and hence is stable even when the replay buffer has large cardinality. A detailed explanation and implementation of $b^{k}_{h}(\cdot,\cdot)$ is provided in Section 3.1.

1 Stable UCB via Importance Sampling

In this section, we formally define the bonus function $b^{k}_{h}(\cdot,\cdot)$ used in Algorithm 1. The bonus function is designed to estimate the confidence interval of our estimate of the $Q$-function. In our algorithm, we define the bonus function to be the width function $b^{k}_{h}(\cdot,\cdot)=w(\mathcal{F}^{k}_{h},\cdot,\cdot)$ where the confidence region $\mathcal{F}^{k}_{h}$ is defined so that

with high probability. By definition of the width function, $b^{k}_{h}(\cdot,\cdot)$ gives an upper bound on the confidence interval of the estimate of the $Q$-function, since the width function maximizes the difference between all pairs of $Q$-functions that lie in the confidence region. We note that similar ideas have been applied in the bandit literature (Russo and Van Roy, 2013), in reinforcement learning with linear function approximation (Du et al., 2019) and in reinforcement learning with general function apprximation in deterministic systems (Du et al., 2020b).

To define the confidence region $\mathcal{F}^{k}_{h}$, a natural definition would be

with high probability, and recall that $\mathcal{Z}^{k}=\left\{(s^{\tau}_{h^{\prime}},a^{\tau}_{h^{\prime}})\right\}_{(\tau,h^{\prime})\in[k-1]\times[H]}$ is the set of state-action pairs defined in Line 5. However, as one can observe, the complexity of such a bonus function could be extremely high as it is defined by a dataset ${\mathcal{Z}}^{k}$ whose size can be as large as $T=KH$. A high-complexity bonus function could potentially introduce instability issues in the algorithm. Technically, we require a stable bonus function to allow for highly concentrated estimate of the one-step backup so that the confidence region $\mathcal{F}^{k}_{h}$ is accurate even for bounded $\beta$. Our strategy to “stabilize” the bonus function is to reduce the size of the dataset by importance sampling, so that only important state-action pairs are kept and those unimportant ones (which potentially induce instability) are ignored. Another benefit of reducing the size of the dataset is that it leads to superior computational complexity when evaluating the bonus function in practice. In later part of this section, we introduce an approach to estimate the importance of each state-action pair and a corresponding sampling method based on that. Finally, we note that importance sampling has also been applied in practical RL systems. For instance, in prioritized experience replay (Schaul et al., 2016), the importance is measured by the TD error.

Here we present a framework to subsample a given dataset, so that the confidence region is approximately preserved while the size of the dataset is greatly reduced. Our framework is built upon the sensitivity sampling technique introduced in (Langberg and Schulman, 2010; Feldman and Langberg, 2011; Feldman et al., 2013).

For a given set of state-action pairs $\mathcal{Z}\subseteq\mathcal{S}\times\mathcal{A}$ and a function class $\mathcal{F}$, for each $z\in\mathcal{Z}$, define the $\lambda$-sensitivity of $(s,a)$ with respect to $\mathcal{Z}$ and $\mathcal{F}$ to be

Sensitivity measures the importance of each data point $z$ in $\mathcal{Z}$ by considering the pair of functions $f,f^{\prime}\in\mathcal{F}$ such that $z$ contributes the most to $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}$. In Algorithm 2, we define a procedure to sample each state-action pair with sampling probability proportional to the sensitivity. In this analysis, we show that after applying Algorithm 2 on the input dataset $\mathcal{Z}$, with high probability, the confidence region $\left\{f\in\mathcal{F}\mid\|f-f_{h}^{k}\|_{{\mathcal{Z}}}^{2}\leq\beta\right\}$ is approximately preserved, while the size of the subsampled dataset is upper bounded by the eluder dimension of $\mathcal{F}$ times the log-covering number of $\mathcal{F}$.

The Stable Bonus Function.

With the above sampling procedure, we are now ready to obtain a stable bonus function which is formally defined in Algorithm 3. In Algorithm 3, we first subsample the given dataset $\mathcal{Z}$ and then round the reference function $\bar{f}$ and all data points in the subsampled dataset $\overline{\mathcal{Z}}$ to their nearest neighbors in a $1/(8\sqrt{4T/\delta})$-cover. We discard the subsampled dataset if its size is too large (which happens with low probability as guaranteed by our analysis), and then define the confidence region using the new dataset and the rounded reference function.

We remark that in Algorithm 3, we round the reference function $\bar{f}$ and the state-action pairs in $\mathcal{Z}$ mainly for the purpose of theoretical analysis. In practice, the reference function and the state-action pairs are always stored with bounded precision, in which case explicit rounding is unnecessary. Moreover, when applying Algorithm 3 in practice, if the eluder dimension of the function class is unknown in advance, one may treat $\beta(\mathcal{F},\delta)$ in (4) as a tunable parameter.

2 Computational Efficiency

Finally, we discuss how to implement our algorithm computationally efficiently. To implement Algorithm 1, in Line 8, one needs to solve an empirical risk minimization (ERM) problem which can often be efficiently solved using appropriate optimization methods. To implement Algorithm 3, one needs to evaluate the width function $w(\widehat{\mathcal{F}},\cdot,\cdot)$ for a confidence region $\widehat{\mathcal{F}}$ of the form

which is a constrained optimization problem. When $\mathcal{F}$ is the class of linear functions, there is a closed-form formula for the width function and thus the width function can be efficiently evaluated in this case. To implement Algorithm 2, one needs to efficiently estimate $\lambda$-sensitivity of all state-action pairs in a given set $\mathcal{Z}$. When $\mathcal{F}$ is the class of linear functions, sensitivity is equivalent to leverage score (Drineas et al., 2006) which can be efficiently estimated (Cohen et al., 2015; Clarkson and Woodruff, 2017). For a general function class $\mathcal{F}$, we give an algorithm to estimate the $\lambda$-sensitivity in Appendix A which is computationally efficient if one can efficiently judge whether a given state-action pair $z$ is $\varepsilon$-independent of a set of state-actions pairs $\mathcal{Z}$ with respect to $\mathcal{F}$ for a given $\varepsilon>0$.

Theoretical Guarantee

In this section we provide the theoretical guarantee of Algorithm 1, which is stated in Theorem 1.

Under Assumption 1, after interacting with the environment for $T=KH$ steps, with probability $1-\delta$, Algorithm 1 achieves a a regret bound of

Here we provide an overview of the proof to highlight the technical novelties in the analysis.

In order to show that the confidence region is approximately preserved when using the subsampled dataset $\mathcal{Z}^{\prime}$, we show that for any $f,f^{\prime}\in\mathcal{F}$, $\|f-f^{\prime}\|_{\mathcal{Z}^{\prime}}^{2}$ is a good approximation to $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}$. To show this, we apply a union bound over all pairs of functions on the cover of $\mathcal{F}$ which allows us to consider fixed $f,f^{\prime}\in\mathcal{F}$. For fixed $f,f^{\prime}\in\mathcal{F}$, note that $\|f-f^{\prime}\|_{\mathcal{Z}^{\prime}}^{2}$ is an unbiased estimate of $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}$, and importance sampling proportinal to the sensitivity implies an upper bound on the variance of the estimator which allows us to apply concentration bounds to prove the desired result. We note that the sensitivity sampling framework used here is very crucial to the theoreical guarantee of the algorithm. If one replaces sensitivity sampling with more naïve sampling approaches (e.g. uniform sampling), then the required sampling size would be much larger, which does not give any meaningful reduction on the size of the dataset and also leads to a high complexity bonus function.

When $\mathcal{F}$ is the class of $d$-dimensional linear functions, our upper bound on the size of the subsampled dataset is $\widetilde{O}(d^{2})$. However, in this case, our sampling algorithm (Algorithm 2) is equivalent to the leverage score sampling (Drineas et al., 2006) and therefore the sample complexity can be further improved to $\widetilde{O}(d)$ using a more refined analysis (Spielman and Srivastava, 2011). Therefore, our regret bound can be improved to $\widetilde{O}(\sqrt{d^{3}H^{2}T})$, which matches the bounds in (Jin et al., 2019; Wang et al., 2019). However, the $\widetilde{O}(d)$ sample bound is specialized to the linear case and heavily relies on the matrix Chernoff bound which is unavailable for the class of general functions considered in this paper. This also explains why our regret bound in Theorem 1, when applied to the linear case, is larger by a $\sqrt{d}$ factor when compared to those in (Jin et al., 2019; Wang et al., 2019). We leave it as an open question to obtain more refined bound on the size of the subsampled dataset and improve the overall regret bound of our algorithm.

The Confidence Region.

Our algorithm applies the principle of optimism in the face of uncertainty (OFU) to balance exploration and exploitation. Note that $V^{k}_{h+1}$ is the value function estimated at step $h+1$. In our analysis, we require the $Q$-function $Q^{k}_{h}$ estimated at level $h$ to satisfy

with high probability. To achieve this, we optimize the least squares objective to find a solution $f^{k}_{h}\in\mathcal{F}$ using collected data. We then show that ${f}_{h}^{k}$ is close to $r(\cdot,\cdot)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|\cdot,\cdot)V_{h+1}^{k}(s^{\prime})$. This would follow from standard analysis if the collected samples were independent of $V_{h+1}^{k}$. However, $V_{h+1}^{k}$ is calculated using the collected samples and thus they are subtly dependent on each other. To tackle this issue, we notice that $V_{h+1}^{k}$ is computed by using $f_{h+1}^{k}$ and the bonus function $b_{h+1}^{k}$, and both $f_{h+1}^{k}$ and the bonus function $b_{h+1}^{k}$ have bounded complexity, thanks to the design of bonus function. Hence, we can construct a $1/T$-cover to approximate $V_{h+1}^{k}$. By doing so, we can now bound the fitting error of ${f}_{h}^{k}$ by replacing $V_{h+1}^{k}$ with its closest neighbor in the $1/T$-cover which is independent of the dataset. By a union bound over all functions in the $1/T$-cover, it follows that with high probability,

for some $\beta$ that depends only on the complexity of the bonus function and the function class $\mathcal{F}$.

Regret Decomposition and the Eluder Dimension.

By standard regret decomposition for optimistic algorithms, the total regret is upper bounded by the summation of the bonus function $\sum_{k=1}^{K}\sum_{h=1}^{H}b^{k}_{h}\left(s_{h}^{k},a_{h}^{k}\right)$. To bound the summation of the bonus function, we use an argument similar to that in (Russo and Van Roy, 2013), which shows that the summation of the bonus function can be upper bounded in terms of the eluder dimension of the function class $\mathcal{F}$, if the confidence region is defined using the original dataset. In the formal analysis, we adapt the argument in (Russo and Van Roy, 2013) to show that even if the confidence region is defined using the subsampled dataset, the summation of the bonus function can be bounded in a similar manner.

1 Analysis of the Stable Bonus Function

Our first lemma gives an upper bound on the sum of the sensitivity in terms of the eluder dimension of the function class $\mathcal{F}$.

For a given set of state-action pairs $\mathcal{Z}$,

For each $z\in\mathcal{Z}$, let $f,f^{\prime}\in F$ be an arbitrary pair of functions such that $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq\lambda$ and

is maximized, and we define $L(z)=(f(z)-f^{\prime}(z))^{2}$ for such $f$ and $f^{\prime}$. Note that $0\leq L(z)\leq(H+1)^{2}$. Let $\mathcal{Z}=\bigcup_{\alpha=0}^{\log((H+1)^{2}|\mathcal{Z}|/\lambda)-1}\mathcal{Z}^{\alpha}\cup\mathcal{Z}^{\infty}$ be a dyadic decomposition with respect to $L(\cdot)$, where for each $0\leq\alpha<\log((H+1)^{2}|\mathcal{Z}|/\lambda)$, define

Clearly, for any $z\in\mathcal{Z}^{\infty}$, $\mathsf{sensitivity}_{\mathcal{Z},\mathcal{F},\lambda}(z)\leq 1/|\mathcal{Z}|$ and thus

Now we bound $\sum_{z\in\mathcal{Z}^{\alpha}}\mathsf{sensitivity}_{\mathcal{Z},\mathcal{F},\lambda}(z)$ for each $0\leq\alpha<\log((H+1)^{2}|\mathcal{Z}|/\lambda)$ separately. For each $\alpha$, let

and we decompose $\mathcal{Z}^{\alpha}$ into $N_{\alpha}+1$ disjoint subsets, i.e., $\mathcal{Z}^{\alpha}=\bigcup_{j=1}^{N_{\alpha}+1}\mathcal{Z}^{\alpha}_{j}$, by using the following procedure. Let $\mathcal{Z}^{\alpha}=\{z_{1},z_{2},\ldots,z_{|\mathcal{Z}^{\alpha}|}\}$ and we consider each $z_{i}$ sequentially. Initially $\mathcal{Z}^{\alpha}_{j}=\{\}$ for all $j$. Then, for each $z_{i}$, we find the largest $1\leq j\leq N_{\alpha}$ such that $z_{i}$ is $(H+1)^{2}\cdot 2^{-\alpha-1}$-independent of $\mathcal{Z}^{\alpha}_{j}$ with respect to $\mathcal{F}$. We set $j=N_{\alpha}+1$ if such $j$ does not exist, and use $j(z_{i})\in[N_{\alpha}+1]$ to denote the choice of $j$ for $z_{i}$. By the design of the algorithm, for each $z_{i}$, it is clear that $z_{i}$ is dependent on each of $\mathcal{Z}^{\alpha}_{1},\mathcal{Z}^{\alpha}_{2},\ldots,\mathcal{Z}^{\alpha}_{j(z_{i})-1}$.

Now we show that for each $z_{i}\in\mathcal{Z}^{\alpha}$,

For any $z_{i}\in\mathcal{Z}^{\alpha}$, we use $f,f^{\prime}\in F$ to denote the pair of functions in $\mathcal{F}$ such that $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq\lambda$ and

is maximized. Since $z_{i}\in\mathcal{Z}^{\alpha}$, we must have $(f(z_{i})-f^{\prime}(z_{i}))^{2}>(H+1)^{2}\cdot 2^{-\alpha-1}$. Since $z_{i}$ is dependent on each of $\mathcal{Z}^{\alpha}_{1},\mathcal{Z}^{\alpha}_{2},\ldots,\mathcal{Z}^{\alpha}_{j(z_{i})-1}$, for each $1\leq k<j(z_{i})$, we have

By the monotonicity of eluder dimension, it follows that

Using Lemma 1, we can prove an upper bound on the number of distinct elements in $\mathcal{Z}^{\prime}$ returned by the sampling algorithm (Algorithm 2).

With probability at least $1-\delta/4$, the number of distinct elements in $\mathcal{Z}^{\prime}$ returned by Algorithm 2 is at most

since for any real number $x<1$, there always exists $\widehat{x}\in[x,2x]$ such that $1/\widehat{x}$ is an integer. Let $X_{z}$ be a random variable defined as

By Chernoff bound, with probability at least $1-\delta/4$, we have

Our second lemma upper bounds the number of elements in $\mathcal{Z}^{\prime}$ returned by Algorithm 2.

With probability at least $1-\delta/4$, $|\mathcal{Z}^{\prime}|\leq 4|\mathcal{Z}|/\delta$.

Let $X_{z}$ be the random variable which is defined as

Our third lemma shows that for the given set of state-action pairs $\mathcal{Z}$ and function class $\mathcal{F}$, Algorithm 2 returns a set of state-action pairs $\mathcal{Z}^{\prime}$ so that $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}$ is approximately preserved for all $f,f^{\prime}\in\mathcal{F}$.

With probability at least $1-\delta/2$, for any $f,f^{\prime}\in\mathcal{F}$,

In our proof, we separately consider two cases: $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}<2\lambda$ and $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq 2\lambda$.

Consider $f,f^{\prime}\in\mathcal{F}$ with $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}<2\lambda$. Conditioned on the event defined in Lemma 3 which holds with probability at least $1-\delta/4$, we have $\|f-f^{\prime}\|_{\mathcal{Z}^{\prime}}^{2}\leq|\mathcal{Z}^{\prime}|\cdot\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\leq 8|\mathcal{Z}|\lambda/\delta$. Moreover, we always have $\|f-f^{\prime}\|_{\mathcal{Z}^{\prime}}\geq 0$. In summary, we have

We first show that for any fixed $f,f^{\prime}\in\mathcal{F}$ with $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq\lambda$, with probability at least $1-\delta/(4\mathcal{N}(\mathcal{F},\varepsilon/72\cdot\sqrt{\lambda\delta/(|\mathcal{Z}|)}))$, we have

To prove this, for each $z\in\mathcal{Z}$, define

By union bound, the above inequality implies that with probability at least $1-\delta/4$, for any $(f,f^{\prime})\in\mathcal{C}(F,\varepsilon/72\cdot\sqrt{\lambda\delta/(|\mathcal{Z}|)})\times\mathcal{C}(F,\varepsilon/72\cdot\sqrt{\lambda\delta/(|\mathcal{Z}|)})$ with $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq\lambda$,

Now we condition on the event defined above and the event defined in Lemma 3. Consider $f,f^{\prime}\in\mathcal{F}$ with $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq 2\lambda$. Recall that there exists

such that $\|f-\widehat{f}\|_{\infty}\leq\sqrt{\lambda/(25|\mathcal{Z}|)}$ and $\|f^{\prime}-\widehat{f^{\prime}}\|_{\infty}\leq\sqrt{\lambda/(25|\mathcal{Z}|)}$. Therefore,

Therefore, conditioned on the event defined above, we have

Conditioned on the event defined in Lemma 3 which holds with probability at least $1-\delta/4$, we have

where the last inequality holds since $\|f-f\|_{\mathcal{Z}}\geq\sqrt{\lambda}$.

Combining Lemma 2, Lemma 3 and Lemma 4 with a union bound, we have the following proposition.

With probability at least $1-\delta$, the size of $\mathcal{Z}^{\prime}$ returned by Algorithm 2 satisfies $|\mathcal{Z}^{\prime}|\leq 4|\mathcal{Z}|/\delta$, the number of distinct elements in $\mathcal{Z}$ is at most

and for any $f,f^{\prime}\in\mathcal{F}$,

For Algorithm 3, suppose $|\mathcal{Z}|\leq KH=T$, the following holds.

With probability at least $1-\delta/(16T)$,

where $\underline{\mathcal{F}}=\{f\in\mathcal{F}\mid\|f-\bar{f}\|_{\mathcal{Z}}^{2}\leq\beta(\mathcal{F},\delta)\}$, and $\overline{\mathcal{F}}=\{f\in\mathcal{F}\mid\|f-\bar{f}\|_{\mathcal{Z}}^{2}\leq 9\beta(\mathcal{F},\delta)+12\}$.

$\widehat{w}(\cdot,\cdot)\in\mathcal{W}$ for a function set $\mathcal{W}$ with

for some absolute constant $C>0$ if $T$ is sufficiently large.

For the first part, conditioned on the event defined in Proposition 1, for any $f\in\mathcal{F}$, we have

Therefore, for any $f\in\underline{\mathcal{F}}$, we have $\|f-\bar{f}\|_{\mathcal{Z}}^{2}\leq\beta(\mathcal{F},\delta)$, which implies $\|f-\widehat{f}\|_{\widehat{\mathcal{Z}}}^{2}\leq 3\beta(\mathcal{F},\delta)+2$ and thus $f\in\widehat{\mathcal{F}}$. Moreover, for any $f\in\widehat{\mathcal{F}}$, we have $\|f-\widehat{f}\|_{\widehat{\mathcal{Z}}}^{2}\leq 3\beta(\mathcal{F},\delta)+2$, which implies $\|f-\bar{f}\|_{\mathcal{Z}}^{2}\leq 9\beta(\mathcal{F},\delta)+12$.

For the second part, note that $\widehat{w}(\cdot,\cdot)$ is uniquely defined by $\widehat{\mathcal{F}}$. When $|\overline{\mathcal{Z}}|\geq 4T/\delta$ or the number of distinct elements in $\overline{\mathcal{Z}}$ exceeds

we have $|\widehat{\mathcal{Z}}|=0$ and thus $\widehat{\mathcal{F}}=\mathcal{F}$. Otherwise, $\widehat{\mathcal{F}}$ is defined by $\widehat{f}$ and $\widehat{\mathcal{Z}}$. Since $\widehat{f}\in\mathcal{C}(\mathcal{F},1/(8\sqrt{4T/\delta}))$, the total number of distinct $\widehat{f}$ is upper bounded by $\mathcal{N}(\mathcal{F},1/(8\sqrt{4T/\delta}))$. Since there are at most

distinct elements in $\widehat{\mathcal{Z}}$, while each of them belongs to $\mathcal{C}(\mathcal{S}\times\mathcal{A},1/(8\sqrt{4T/\delta}))$ and $|\widehat{\mathcal{Z}}|\leq 4T/\delta$, the total number of distinct $\widehat{\mathcal{Z}}$ is upper bounded by

2 Analysis of the Algorithm

We are now ready to prove the regret bound of Algorithm 1. The next lemma establishes a bound on the estimate of a single backup.

as defined in Line 5 in Algorithm 1. For any $V:\mathcal{S}\rightarrow[0,H]$, define

For any $V:\mathcal{S}\rightarrow[0,H]$ and $\delta\in(0,1)$, there is an event $\mathcal{E}_{V,\delta}$ which holds with probability at least $1-\delta$, such that conditioned on $\mathcal{E}_{V,\delta}$, for any $V^{\prime}:\mathcal{S}\rightarrow[0,H]$ with $\|V^{\prime}-V\|_{\infty}\leq 1/T$, we have

for some absolute constant $c^{\prime}>0$.

In our proof, we consider a fixed $V:\mathcal{S}\to[0,H]$, and define

For any $f\in\mathcal{F}$, we consider $\sum_{(\tau,h)\in[k-1]\times[H]}\xi_{h}^{\tau}(f)$ where

We have, with probability at least $1-\delta$, for all $f\in\mathcal{C}(\mathcal{F},1/T)$,

We define the above event to be $\mathcal{E}_{V,\delta}$, and we condition on this event for the rest of the proof.

For all $f\in\mathcal{F}$, there exists $g\in\mathcal{C}(\mathcal{F},1/T)$, such that $\|f-g\|_{\infty}\leq 1/T$, and we have

Consider $V^{\prime}:\mathcal{S}\rightarrow[0,H]$ with $\|V^{\prime}-V\|_{\infty}\leq 1/T$. We have

Recall that $\widehat{f}_{V^{\prime}}=\arg\min_{f\in\mathcal{F}}\|f\|_{\mathcal{D}^{k}_{V^{\prime}}}^{2}$. We have $\|\widehat{f}_{V^{\prime}}\|_{\mathcal{D}^{k}_{V^{\prime}}}^{2}-\|f_{V^{\prime}}\|_{\mathcal{D}^{k}_{V^{\prime}}}^{2}\leq 0$, which implies,

for an absolute constant $c^{\prime}>0$. ∎

In Algorithm 1, let $\mathcal{F}_{h}^{k}$ be a confidence region defined as

Then with probability at least $1-\delta/8$, for all $k,h\in[K]\times[H]$,

for some absolute constant $c^{\prime}>0$. Here $\mathcal{W}$ is given as in Propostion 2.

For all $(k,h)\in[K]\times[H]$, the bonus function $b_{h}^{k}(\cdot,\cdot)\in\mathcal{W}$. Note that

I.e., there exists $q\in\mathcal{Q}$ such that $\|q-Q_{h+1}^{k}\|_{\infty}\leq 1/T$. This implies

is a $(1/T)$-cover of $V_{h+1}^{k}$ with $\log(|\mathcal{V}|)\leq\log|\mathcal{W}|+\log\mathcal{N}(\mathcal{F},1/T)+1$. For each $V\in\mathcal{V}$, let $\mathcal{E}_{V,\delta/(8|\mathcal{V}|T)}$ be the event defined in Lemma 5. By Lemma 5, we have $\Pr\left[\bigcap_{V\in\mathcal{V}}\mathcal{E}_{V,\delta/(8|\mathcal{V}|T)}\right]\geq 1-\delta/(8T)$. We condition on $\bigcap_{V\in\mathcal{V}}\mathcal{E}_{V,\delta/(8|\mathcal{V}|T)}$ in the rest part of the proof.

Recall that $f_{h}^{k}$ is the solution of the optimization problem in Line 8 of Algorithm 1, i.e., $f^{k}_{h}=\operatorname*{arg\,min}_{f\in\mathcal{F}}\|f\|_{\mathcal{D}^{k}_{h}}^{2}$. Let $V\in\mathcal{V}$ such that $\|V-V^{k}_{h+1}\|_{\infty}\leq 1/T$. Thus, by Lemma 5, we have

for some absolute constant $c^{\prime}$. Therefore, by a union bound, for all $(k,h)\in[K]\times[H]$, we have $f_{h}^{k}(\cdot,\cdot)-\left(r(\cdot,\cdot)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid\cdot,\cdot)V_{h+1}^{k}(s^{\prime})\right)\in\mathcal{F}_{h}^{k}$ with probability at least $1-\delta/8$. ∎

The above lemma guarantees that, with high probability, $r(\cdot,\cdot)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid\cdot,\cdot)V_{h+1}^{k}(\cdot,\cdot)$ lies in the confidence region. With this, it is guaranteed that $\left\{Q_{h}^{k}\right\}_{(h,k)\in[H]\times[K]}$ are all optimistic, with high probability. This is formally presented in the next lemma.

With probability at least $1-\delta/4$, for all $(k,h)\in[K]\times[H]$, for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Let $\mathcal{E}$ be the event that for all $(k,h)\in[K]\times[H]$, $r(\cdot,\cdot)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid\cdot,\cdot)V_{h+1}^{k}(s^{\prime})\in\mathcal{F}_{h}^{k}$. By Lemma 6, $\Pr[\mathcal{E}]\geq 1-\delta/8$. Let $\mathcal{E}^{\prime}$ be the event that for all $(k,h)\in[K]\times[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, $b_{h}^{k}(s,a)\geq w(\mathcal{F}^{k}_{h},s,a)$. By Proposition 2 and union bound, $\mathcal{E}^{\prime}$ holds failure probability at most $\delta/8$. In the rest part of the proof we condition on $\mathcal{E}$ and $\mathcal{E}^{\prime}$.

for any $(s,a)\in\mathcal{S}\times\mathcal{A}$ we have

Now we prove $Q_{h}^{*}(s,a)\leq Q_{h}^{k}(s,a)$ by induction on $h$. When $h=H+1$, the desired inequality clearly holds. Now we assume $Q_{h+1}^{*}(\cdot,\cdot)\leq Q^{k}_{h+1}(\cdot,\cdot)$ for some $h\in[H]$. Clearly we have $V_{h+1}^{*}(\cdot)\leq V^{k}_{h+1}(\cdot)$. Therefore, for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,

The next lemma upper bounds the regret of the algorithm by the sum of $b^{k}_{h}(\cdot,\cdot)$.

In our proof, for any $(k,h)\in[K]\times[H-1]$ define

By Azuma-Hoeffding inequality, with probability at least $1-\delta/4$,

We condition on the above event in the rest of the proof. We also condition on the event defined in Lemma 7 which holds with probability $1-\delta/4$.

It remains to bound $\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h}^{k}(s_{h}^{k},a_{h}^{k})$, for which we will exploit fact that $\mathcal{F}$ has bounded eluder dimension.

With probability at least $1-\delta/4$, for any $\varepsilon>0$,

for some absolute constant $c>0$. Here $\beta(\mathcal{F},\delta)$ is as defined in (4).

Let $\mathcal{E}$ be the event that or all $(k,h)\in[K]\times[H]$,

By Proposition 2, $\mathcal{E}$ holds with probability at least $1-\delta/4$. In the rest of the proof, we condition on $\mathcal{E}$.

Let $\mathcal{L}=\{(s_{h}^{k},a_{h}^{k})\mid b_{h}^{k}(s_{h}^{k},a_{h}^{k})>\varepsilon\}$ with $|\mathcal{L}|=L$. We show that there exists $(s_{h}^{k},a_{h}^{k})\in\mathcal{L}$ such that $(s_{h}^{k},a_{h}^{k})$ is $\varepsilon$-dependent on at least $L/\dim_{E}(\mathcal{F},\varepsilon)-H$ disjoint subsequences in $\mathcal{Z}^{k}\cap\mathcal{L}$. We demonstrate this by using the following procedure. Let $\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{L/\dim_{E}(\mathcal{F},\varepsilon)-1}$ be $L/\dim_{E}(\mathcal{F},\varepsilon)-1$ disjoint subsequences of $\mathcal{L}$ which are initially empty. We consider

for each $k\in[K]$ sequentially. For each $k\in[K]$, for each $z\in\{(s_{1}^{k},a_{1}^{k}),(s_{2}^{k},a_{2}^{k}),\ldots,(s_{H}^{k},a_{H}^{k})\}\cap\mathcal{L}$, we find $j\in[L/\dim_{E}(\mathcal{F},\varepsilon)-1]$ such that $z$ is $\varepsilon$-independent of $\mathcal{L}_{j}$ and then add $z$ into $\mathcal{L}_{j}$. By the definition of $\varepsilon$-independence, $|\mathcal{L}_{j}|\leq\dim_{E}(\mathcal{F},\varepsilon)$ for all $j$ and thus we will eventually find some $(s_{h}^{k},a_{h}^{k})\in\mathcal{L}$ such that $(s_{h}^{k},a_{h}^{k})$ is $\varepsilon$-dependent on each of $\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{L/\dim_{E}(\mathcal{F},\varepsilon)-1}$. Among $\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{L/\dim_{E}(\mathcal{F},\varepsilon)-1}$, there are at most $H-1$ of them that contain an element in

and all other subsequences only contain elements in $\mathcal{Z}^{k}\cap\mathcal{L}$. Therefore, $(s_{h}^{k},a_{h}^{k})$ is $\varepsilon$-dependent on at least $L/\dim_{E}(\mathcal{F},\varepsilon)-H$ disjoint subsequences in $\mathcal{Z}^{k}\cap\mathcal{L}$.

On the other hand, since $(s_{h}^{k},a_{h}^{k})\in\mathcal{L}$, we have $b_{h}^{k}(s_{h}^{k},a_{h}^{k})>\varepsilon$, which implies there exists $f,f^{\prime}\in\mathcal{F}$ with $\|f-f_{h}^{k}\|_{\mathcal{Z}^{k}}^{2}\leq 9\beta+12$ and $\|f^{\prime}-f_{h}^{k}\|_{\mathcal{Z}^{k}}^{2}\leq 9\beta+12$ such that $f(z)-f^{\prime}(z)>\varepsilon$. By triangle inequality, we have $\|f-f^{\prime}\|_{\mathcal{Z}^{k}}^{2}\leq 36\beta+48$. On the other hand, since $(s_{h}^{k},a_{h}^{k})$ is $\varepsilon$-dependent on at least $L/\dim_{E}(\mathcal{F},\varepsilon)-H$ disjoint subsequences in $\mathcal{Z}^{k}\cap\mathcal{L}$, we have

Lastly, we apply the above lemma to bound the overall regret.

for some absolute constant $c>0$. Here $\beta(\mathcal{F},\delta)$ is as defined in (4).

In the proof we condition on the event defined in Lemma 9. We define $w_{h}^{k}:=b^{k}_{h}\left(s_{h}^{k},a_{h}^{k}\right)$. Let $w_{1}\geq w_{2}\geq\ldots\geq w_{T}$ be a permutation of $\{w_{h}^{k}\}_{(k,h)\in[K]\times[H]}$. By the event defined in Lemma 9, for any $w_{t}\geq 1/T$, we have

Moreover, we have $w_{t}\leq 4H$. Therefore,

We are now ready to prove our main theorem.

By Lemma 8 and Lemma 10, with probability at least $1-\delta$,

for some absolute constants $c>0$. Substituting the value of $\beta(\mathcal{F},\delta)$ completes the proof. ∎

Model Misspecification

In this section, we study the case when there is a misspecification error. Formally, we consider the following assumption.

There exists a set of functions $\mathcal{F}\subseteq\{f:\mathcal{S}\times\mathcal{A}\rightarrow[0,H+1]\}$ and a real number $\zeta>0$, such that for any $V:\mathcal{S}\rightarrow[0,H]$, there exists $f_{V}\in\mathcal{F}$ which satisfies

We call $\zeta$ the misspecification error.

Our algorithm for the misspecification case is identical the original algorithm except for the change of $\beta(\mathcal{F},\delta)$. In particular, we change the definition of $\beta(\mathcal{F},\delta)$ (defined in (4)) as follows.

for some absolute constant $c^{\prime}>0$. With this, we can now reprove Lemma 5 in the misspecified case.

Suppose $\mathcal{F}$ satisfies Assumption 3. Consider a fixed $k\in[K]$. Let

as defined in Line 5 in Algorithm 1. For any $V:\mathcal{S}\rightarrow[0,H]$, define

For any $V:\mathcal{S}\rightarrow[0,H]$ and $\delta\in(0,1)$, there is an event $\mathcal{E}_{V,\delta}$ which holds with probability at least $1-\delta$, such that conditioned on $\mathcal{E}_{V,\delta}$, for any $V^{\prime}:\mathcal{S}\rightarrow[0,H]$ with $\|V^{\prime}-V\|_{\infty}\leq 1/T$, we have

for some absolute constant $c^{\prime}>0$.

In our proof, we consider a fixed $V:\mathcal{S}\to[0,H]$, and define

Note that unlike Lemma 5, we may have $f_{V}\not\in\mathcal{F}$. By Assumption 3, we immediately have

For any $f\in\mathcal{F}$, we consider $\sum_{(\tau,h)\in[k-1]\times[H]}\xi_{h}^{\tau}(f)$ where

Similar to Lemma 5, we still have, with probability at least $1-\delta$, for all $f\in\mathcal{C}(\mathcal{F},1/T)$,

We define the above event to be $\mathcal{E}_{V,\delta}$, and we condition on this event for the rest of the proof. Similarly, we have, for all $f\in\mathcal{F}$,

Consider $V^{\prime}:\mathcal{S}\rightarrow[0,H]$ with $\|V^{\prime}-V\|_{\infty}\leq 1/T$. We still have

Again by the same argument as in the proof of Lemma 5, we have for any $f\in\mathcal{F}$,

Let $\widetilde{f}_{V^{\prime}}=\arg\min_{f\in\mathcal{F}}\|f-f_{V^{\prime}}\|_{\mathcal{Z}^{k}}^{2}$. Recall that $\widehat{f}_{V^{\prime}}=\arg\min_{f\in\mathcal{F}}\|f\|_{\mathcal{D}^{k}_{V^{\prime}}}^{2}$. We have

Since $\|\widehat{f}_{V^{\prime}}\|_{\mathcal{D}^{k}_{V^{\prime}}}+\|f_{V^{\prime}}\|_{\mathcal{D}^{k}_{V^{\prime}}}\leq 4H\sqrt{T}$, solving the above inequality, we have,

for an absolute constant $c^{\prime}>0$. ∎

Similar to Lemma 6, we have the following lemma.

Suppose $\mathcal{F}$ satisfies Assumption 3. In Algorithm 1, let $\mathcal{F}_{h}^{k}$ be a confidence region defined as

Then with probability at least $1-\delta/8$, for all $k,h\in[K]\times[H]$,

for some absolute constant $c^{\prime}>0$. Here $\mathcal{W}$ is given as in Propostion 2.

The proof is nearly identical to that of Lemma 6. ∎

Combining Lemma 12 with Lemma 7–10, we obtain the following theorem.

Under Assumption 3, after interacting with the environment for $T=KH$ steps, with probability at least $1-\delta$, Algorithm 1 achieves a regret bound of

Conclusion

Acknowledgments

The authors would like to thank Jiantao Jiao, Sham M. Kakade and Csaba Szepesvári for insightful comments on an earlier version of this paper. RW and RS were supported in part by NSF IIS1763562, AFRL CogDeCON FA875018C0014, and DARPA SAGAMORE HR00111990016.

References

Appendix A Estimating the Sensitivity

In this section, we present a computationally efficient algorithm to estimate the $\lambda$-sensitivity of all state-action pairs in a give set $\mathcal{Z}\subseteq\mathcal{S}\times\mathcal{A}$ with respect to a given function class $\mathcal{F}$. The algorithm is formally described in Algorithm 4.

Given a function class $\mathcal{F}$, a set of state-action pairs $\mathcal{Z}$ and an accuracy parameter $\lambda$, Algorithm 4 returns an estimate of the $\lambda$-sensitivity for each $z\in\mathcal{Z}$. With Algorithm 4, we can now implement Algorithm 2 computationally efficiently by replacing (3) in Algorithm 2 with

which we prove in the remaining part of this section.

In our proof we consider a fixed $z\in\mathcal{Z}$. Let $f,f^{\prime}\in F$ be an arbitrary pair of functions such that $\|f-f^{\prime}\|_{\mathcal{Z}}^{2}\geq\lambda$ and

For each $0\leq\alpha<\log((H+1)^{2}|\mathcal{Z}|/\lambda)$, by the definition of $(H+1)^{2}\cdot 2^{-\alpha-1}$-independence, we have