Provably Efficient Reinforcement Learning with Linear Function Approximation

Introduction

Reinforcement Learning (RL) is a control-theoretic problem in which an agent tries to maximize its expected cumulative reward by interacting with an unknown environment over time . Modern RL commonly engages practical problems with an enormous number of states, where function approximation must be deployed to approximate the (action-)value function—the expected cumulative reward starting from a state-action pair—or the policy—the mapping from a state to its subsequent action. Function approximation, especially based on deep neural networks, lies at the heart of the recent practical successes of RL in domains such as Atari games , Go , robotics , and dialogue systems . Moreover, deep neural networks serve as essential components of generic deep RL algorithms, including Deep Q-Network (DQN) , Asynchronous Advantage Actor-Critic (A3C) , and Trust Region Policy Optimization (TRPO) .

Despite the empirical successes of function approximation in RL, most existing theoretical guarantees apply only to tabular RL [see, e.g., 20, 33, 8, 22], in which the states and actions are discrete, and the value function is represented by a table. Due to the curse of dimensionality, only relatively small problems can be tackled by tabular RL. Thus, researchers have turned to function approximation [see, e.g., 40, 12, 43], in theory and in practice. While function approximation greatly expands the potential reach of RL, particularly via deep RL architectures, it raises a number of fundamental theoretical challenges. For example, while the effective state and action spaces can be much larger when function approximation is used, the neighborhoods of most states are not visited even once during a set of learning episodes, which makes it difficult to obtain reliable estimates of value functions [see, e.g., 41, 42, 26]. To cope with this challenge, relatively simple function classes, including linear function classes, are often used. This introduces, however, a bias, even in the limit of infinite training data, given that the optimal value function and policy may not be linear [see, e.g., 10, 11, 43]. Thus, both in theory and in practice, the design of RL systems must cope with fundamental statistical problems of sparsity and misspecification, all in the context of a dynamical system. Moreover, a core distinguishing feature of RL is that it requires addressing the tradeoff between exploration and exploitation. Addressing this tradeoff algorithmically requires exactly the kinds of statistical estimates that are challenging to obtain in the RL setting due to sparsity, misspecification, and dynamics. Thus the following fundamental question remains open:

Is it possible to design provably efficient RL algorithms in the function approximation setting?

By “efficient” we mean efficient in both runtime and sample complexity—the runtime and the sample complexity should not depend on the number of states, but should depend instead on an intrinsic complexity measure of the function class.

Several recent attempts have been made to attack this fundamental problem. However, they either require the access to a “simulator” which alleviates the difficulty of exploration, or assume the transition dynamics to be deterministic , to have a low variance , or are parametrizable by a relatively small matrix , which alleviates the difficulty in estimating the transition dynamics (see Section 1.1 for more details).

Focusing on a linear setting in which the transition dynamics and reward function are assumed to be linear, we present the first algorithm that is provably efficient in both runtime and sample complexity, without requiring additional oracles or stronger assumptions. Concretely, in the general setting of an episodic Markov Decision Process (MDP), we prove that an optimistic version of Least-Squares Value Iteration (LSVI) —a classical algorithm frequently studied in the linear setting—achieves $\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{3}T})$ regret, where $d$ is the ambient dimension of feature space, $H$ is the length of each episode, $T$ is the total number of steps, and $\widetilde{\mathcal{O}}(\cdot)$ hides only absolute constant and poly-logarithmic factors. Importantly, such regret is independent of $S$ and $A$—the number of states and actions. Our algorithm runs in $\mathcal{O}(d^{2}AKT)$ time and $\mathcal{O}(d^{2}H+dAT)$ space, which are again independent of $S$ and thus efficient in practice. In addition, our result is robust to the linear assumption: When the underlying transition model is not linear, but $\zeta$-close to linear in total variation distance (Assumption B), our algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{3}T}+\zeta dHT)$ regret. That is, in addition to the standard $\sqrt{T}$ regret, the algorithm also suffers from a linear regret term that scales with an error $\zeta$ that arises due to the function class misspecification.

Tabular RL is well studied in both model-based and model-free settings . See also for a simplified setting with access to a “simulator” (also called a generative model), which is a strong oracle that allows the algorithm to query arbitrary state-action pairs and return the reward and the next state. The “simulator” significantly alleviates the difficulty of exploration, since a naive exploration strategy which queries all state-action pairs uniformly at random already leads to the most efficient algorithm for finding an optimal policy .

In the episodic setting with nonstationary dynamics and no “simulators,” the best regrets achieved by existing model-based and model-free algorithms are $\widetilde{\mathcal{O}}(\sqrt{H^{2}SAT})$ and $\widetilde{\mathcal{O}}(\sqrt{H^{3}SAT})$ , respectively, both of which (nearly) attain the minimax lower bound $\Omega(\sqrt{H^{2}SAT})$ . Here $S$ and $A$ denote the numbers of states and actions, respectively. Although these algorithms are (nearly) minimax-optimal, they can not cope with large state spaces, as their regret scales linearly in $\sqrt{S}$, where $S$ is often exponentially large in practice [see, e.g., 30, 38, 23, 27]. Moreover, the minimax lower bound suggests that, information-theoretically, a large state space cannot be handled efficiently unless further problem-specific structure is exploited. Compared with this line of work, in the current paper we exploit the linear structure of the reward and transition functions and show that the regret of optimistic LSVI scales polynomially in the ambient dimension $d$ rather than the number of states $S$.

Linear bandits:

To enable function approximation, another line of related work studies stochastic linear bandits or stochastic linear contextual bandits [see, e.g., 5, 16, 28, 35, 14, 2], which is a special case of the linear MDP studied in this paper (Assumption A) with the episode length $H$ set equal to one. See and the references therein for a detailed survey. The best regrets achieved by existing algorithms are $\widetilde{\mathcal{O}}(d\sqrt{T})$ for linear bandits and $\widetilde{\mathcal{O}}(\sqrt{dT})$ for linear contextual bandits , both of which scale polynomially in the ambient dimension $d$. We note, however, that while an MDP has state transition, linear bandits do not. This temporal structure captures the fundamental difference in their difficulties of exploration: a naive adaptation of existing linear bandit algorithms to the linear MDP setting yields a regret exponential in $H$—the length of each episode.

RL with function approximation:

In the setting of linear function approximation, there is a long line of classical work on the design of algorithms, but this work does not provide polynomial sample efficiency guarantees [see, e.g., 12, 29, 41, 33, 9]. Recently, Yang and Wang revisited the setting of linear transitions and rewards (Assumption A), and presented a sample-efficient algorithm assuming the access to a “simulator”. Similar to the case of tabular setting, the “simulator” greatly alleviates the difficulty of exploration. We also note that their very recent work , developed independently of the current paper, provides sample efficiency guarantees for exploration in the linear MDP setting. Compared with the current paper, differs in that requires one additional key assumption—that the transition model can be parameterized by a relatively small matrix. This additional assumption reduces the number of free parameters in the transition model from potentially being infinite (for the case with an infinite number of states) to small and finite, and thus mitigates the challenges in estimating the transition model. As a result, their algorithm and main mechanism are based on estimating the unknown matrix, which differs from our approach. Finally, in a broader context, without the assumption of a linear MDP, sample efficiency guarantees have been established for RL under other assumptions, such as that the transition dynamics are fully deterministic , or have low variances . These assumptions can be potentially restrictive in practice, and may not hold even in the tabular setting. In contrast, our results directly cover the standard tabular case with no extra assumptions.

In the setting of general function approximation, Jiang et al. present a generic algorithm Olive, which enjoys sample efficiency if a complexity measure that they refer to as “Bellman rank” is small. It can be shown that Bellman rank is at most $d$ under Assumption A, and thus Olive is sample efficient in our setting. In contrast to our results, Olive is not computationally efficient in general and it does not provide a $\sqrt{T}$ regret bound. Meanwhile, a recent line of work studies a nonparametric setting with Hölder smooth reward and transition model. The sample complexities provided therein are exponential in dimensionality in the worst case.

Preliminaries

which holds for all $(x,a)\in\mathcal{S}\times\mathcal{A}$. Similarly, the Bellman optimality equation is

This implies that the optimal policy $\pi^{\star}$ is the greedy policy with respect to the optimal action-value function $\{Q^{\star}_{h}\}_{h\in[H]}$. Thus, to find the optimal policy $\pi^{\star}$, it suffices to estimate the optimal action-value functions.

Furthermore, under the setting of an episodic MDP, the agent aims to learn the optimal policy by interacting with the environment during a set of episodes. For each $k\geq 1$, at the beginning of the $k$th episode, the adversary picks the initial state $x^{k}_{1}$ and the agent chooses policy $\pi_{k}$. The difference in values between $V^{\pi_{k}}_{1}(x_{1}^{k})$ and ${V}^{\star}_{1}({x}^{k}_{1})$ serves as the expected regret or the suboptimality of the agent at the $k$-th episode. Thus, after playing for $K$ episodes, the total (expected) regret is

We focus on a setting of a linear Markov decision process, where the transition kernels and the reward function are assumed to be linear. This assumption implies that the action-value function is linear, as we will show. Note that this is not the same as the assumption that the policy is a linear function—an assumption that has been the focus of much of the literature. Rather, it is akin to a statistical modeling assumption, in which we make assumptions about how data are generated and then study various estimators. Formally, we make the following definition.

Without loss of generality, we assume $\left\|{\bm{\phi}(x,a)}\right\|\leq 1$ for all $(x,a)\in\mathcal{S}\times\mathcal{A}$, and $\max\{\left\|{\bm{\mu}_{h}(\mathcal{S})}\right\|,\left\|{\bm{\theta}_{h}}\right\|\}\leq\sqrt{d}$ for all $h\in[H]$.

Recall that we assume the reward functions are bounded in $$, which implies that the value functions are bounded in$[0,H]$. Our choice of normalization conditions in Assumption A implies that the following concrete examples serve as special cases of a linear MDP.

When the feature space, $\{\bm{\phi}(x,a)\colon(x,a)\in\mathcal{S}\times\mathcal{A}\}$, is a subset of the $d$-dimensional simplex, $\{\bm{\psi}|\sum_{i=1}^{d}\psi_{i}=1\text{~{}and~{}}\psi_{i}\geq 0\text{~{}for all~{}}i\}$, a linear MDP can be instantiated by choosing $\mathbf{e}_{i}^{\top}\bm{\mu}_{h}$ to be an arbitrary probability measure over $\mathcal{S}$ and letting $\bm{\theta}_{h}$ be any vector such that $\left\|{\bm{\theta}_{h}}\right\|_{\infty}\leq 1$.

As mentioned earlier, a crucial property of the linear MDP is that, for all policies, the action-value functions are always linear in the feature map $\bm{\phi}$. Therefore, when designing RL algorithms, it suffices to focus on linear action-value functions.

For a linear MDP, for any policy $\pi$, there exist weights $\{\mathbf{w}^{\pi}_{h}\}_{h\in[H]}$ such that for any $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, we have $Q_{h}^{\pi}(x,a)=\langle\bm{\phi}(x,a),\mathbf{w}^{\pi}_{h}\rangle$.

We provide a proof of this proposition in Appendix A, where we also present additional discussion of the basic properties of a linear MDP.

Main Results

In this section, we present our main results, which provide sample complexity guarantees for Algorithm 1 in the linear MDP setting (Theorem 3.1) and in a misspecified setting (Theorem 3.2).

We first lay out our algorithm (Algorithm 1)—an optimistic modification of Least-Square Value Iteration (LSVI), where the optimism is realized by Upper-Confidence Bounds (UCB). At a high level, each episode consists of two passes (or loops) over all steps. The first pass (line 3-6) updates the parameters $(\mathbf{w}_{h},\Lambda_{h})$ that are used to form the action-value function $Q_{h}$. The second pass (line 7-8) executes the greedy policy, $a_{h}=\mathop{\rm argmax}_{a\in\mathcal{A}}Q_{h}(x_{h},a)$, according to the $Q_{h}$ obtained in the first pass. We note $Q_{H+1}(\cdot,\cdot)\equiv 0$ since the agent receives no reward after the $H$th step. For the first episode $k=1$, since the summation in line 4-5 is from $\tau=1$ to , we simply have $\Lambda_{h}\leftarrow\lambda\mathbf{I}$ and $\mathbf{w}_{h}\leftarrow 0$. Line 6 specifies the dependency of the action-value function $Q_{h}$ on the parameters $\mathbf{w}_{h}$ and $\Lambda_{h}$, and no actual updates need to be performed.

The idea of Least-Square Value Iteration stems from the classical value-iteration algorithm, which finds the optimal policy (or action-value function) by applying the Bellman optimality equation Eq. (2) recursively:

Algorithm 1 additionally adds an UCB bonus term of form $\beta(\bm{\phi}^{\top}\Lambda_{h}^{-1}\bm{\phi})^{1/2}$ to encourage exploration, where $\Lambda_{h}$ is the Gram matrix of the regularized least-squares problem, and $\beta$ is a scalar. This form of bonus is common in the literature on linear bandits . Intuitively, $m\mathrel{\mathop{:}}=(\bm{\phi}^{\top}\Lambda_{h}^{-1}\bm{\phi})^{-1}$ represents the effective number of samples the agent has observed so far along the $\bm{\phi}$ direction, and thus the bonus term $\beta/\sqrt{m}$ represents the uncertainty along the $\bm{\phi}$ direction. It is called an upper confidence bound because, by choosing a proper value for $\beta$ we can prove that, with high probability, $Q_{h}$ in line 5 of Algorithm 1 is always an upper bound of $Q_{h}^{\star}$ for all state-action pair (see Lemma B.5).

We are now ready to state our main theorem, which gives a $\sqrt{T}$-regret bound in the linear MDP setting without any further assumptions. Here, $T=KH$ is the total number of steps.

Under Assumption A, there exists an absolute constant $c>0$ such that, for any fixed $p\in(0,1)$, if we set $\lambda=1$ and $\beta=c\cdot dH\sqrt{\iota}$ in Algorithm 1 with $\iota\mathrel{\mathop{:}}=\log(2dT/p)$, then with probability $1-p$, the total regret of LSVI-UCB (Algorithm 1) is at most $\mathcal{O}(\sqrt{d^{3}H^{3}T\iota^{2}})$, where $\mathcal{O}(\cdot)$ hides only absolute constants.

Theorem 3.1 asserts that when $\lambda$ and $\beta$ are set properly, LSVI-UCB will suffer total regret at most $\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{3}T})$. We emphasize that while a naive adaptation of existing linear bandit algorithms to this linear MDP setting easily yields a regret exponential in $H$, our regret is only polynomial in $H$. Avoiding this exponential dependency on the planning horizon is a key step in efficiently solving the sequential RL problem. Additionally, comparing to the minimax regret in a tabular setting, $\widetilde{\Theta}(\sqrt{H^{2}SAT})$, our regret replaces the number of state-action pairs $SA$ by a polynomial dependency on the intrinsic complexity measure of feature space, $d$. In fact, our regret is completely independent of $S$ and $A$, which is crucial in the large state-space setting where function approximation is necessary. Please see also Section 5 for more discussion on the optimal dependencies on $d$ and $H$.

We remark that Algorithm 1 only needs to store $\Lambda_{h},\mathbf{w}_{h}$, $r(x_{h}^{k},a_{h}^{k})$ and $\{\bm{\phi}(x_{h}^{k},a)\}_{a\in\mathcal{A}}$ for all $(h,k)\in[H]\times[K]$, which takes $\mathcal{O}(d^{2}H+dAT)$ space. When we compute $\Lambda_{h}^{-1}$ by the Sherman-Morrison formula, the computational complexity of Algorithm 1 is dominated by line 5 in computing $\max_{a}Q_{h+1}(x^{\tau}_{h+1},a)$ for all $\tau\in[k]$. This takes $\mathcal{O}(d^{2}AK)$ time per step, which gives a total runtime $\mathcal{O}(d^{2}AKT)$.

Finally, similarly to the discussion in Section 3.1 of , our regret bound (Theorem 3.1) directly translates to a sample complexity guarantee (or a PAC guarantee) in the following sense. When the initial state $x_{1}$ is fixed for all episodes, then, with at least constant probability, we can learn an $\varepsilon$-optimal policy $\pi$ which satisfies $V^{\star}(x_{1})-V^{\pi}(x_{1})\leq\varepsilon$ using $\widetilde{\mathcal{O}}(d^{3}H^{4}/\varepsilon^{2})$ samples. The algorithm to achieve this is to simply run Algorithm 1 for $K=\widetilde{\mathcal{O}}(d^{3}H^{3}/\varepsilon^{2})$ episodes, and then output the greedy policy according to the action-value function $Q$ at the $k$th episode, where $k$ is sampled uniformly from $[K]$.

Theorem 3.1 hinges on the fact that the MDP has a linear structure. A natural follow-up question arises: what would happen if the underlying MDP is not linear, and thus misspecified? We first present a definition for an approximate linear model.

Without loss of generality, we assume that $\left\|{\bm{\phi}(x,a)}\right\|\leq 1$ for all $(x,a)\in\mathcal{S}\times\mathcal{A}$, and $\max\{\left\|{\bm{\mu}_{h}(\mathcal{S})}\right\|,\left\|{\bm{\theta}_{h}}\right\|\}\leq\sqrt{d}$ for all $h\in[H]$.

By definition, an MDP is an $\zeta$-approximately linear MDP if there exists a linear MDP such that their Markov transition dynamics and reward functions are close. Here the closeness between transition dynamics is measured in terms of total variation distance.

In general, an algorithm designed for a linear MDP could break down entirely if the underlying MDP is not linear. The following theorem states that this is not the case for our algorithm. It is in fact robust to small model misspecification. To achieve this, we need only to adopt a different hyperparameter $\beta$ in different episodes.

Under Assumption B, there exists an absolute constant $c>0$ such that, for any fixed $p\in(0,1)$, if we set $\lambda=1$ and $\beta_{k}=c\cdot(d\sqrt{\iota}+\zeta\sqrt{kd})H$ in Algorithm 1 with $\iota\mathrel{\mathop{:}}=\log(2dT/p)$, then with probability $1-p$, the total regret of LSVI-UCB (Algorithm 1) is at most \mathcal{O}\bigl{(}\sqrt{d^{3}H^{3}T\iota^{2}}+\zeta dHT\sqrt{\iota}\bigr{)}.

Compared with Theorem 3.1, Theorem 3.2 asserts that the LSVI-UCB algorithm will incur at most an additional $\widetilde{\mathcal{O}}(\zeta dHT)$ regret when the model is misspecified. This additional term is inevitably linear in $T$ due the intrinsic bias introduced by linear approximation. When $\zeta$ is sufficiently small, i.e., the underlying MDP is not far away from being linear, our algorithm will still enjoy good theoretical guarantees.

Theorem 3.2 can also be converted to a PAC guarantee with a similar flavor. When the initial state $x_{1}$ is fixed for all episodes, then, with at least constant probability, we can learn an $\varepsilon$-optimal policy $\pi$ which satisfies $V^{\star}(x_{1})-V^{\pi}(x_{1})\leq\varepsilon+\widetilde{\mathcal{O}}(\zeta dH^{2})$ using $\widetilde{\mathcal{O}}(d^{3}H^{4}/\varepsilon^{2})$ samples.

Mechanisms

In this section, we overview several of the key ideas behind the regret bound in Theorem 3.1. We defer the full proof of Theorem 3.1 and Theorem 3.2 to Appendix B and Appendix C respectively.

In Section 3, we mentioned that the LSVI algorithm is motivated from the Bellman optimality equation Eq. (2). It remains to verify that line 5 in Algorithm 1 indeed well approximates the Bellman optimality equation, which turns out to require not only the linear MDP structure but also hinges on several other facts.

To simplify our presentation, in this section we treat the regularization parameter $\lambda$ loosely as being sufficiently small so that $\Lambda_{h}^{-1}\sum_{\tau=1}^{k-1}\bm{\phi}(x^{\tau}_{h},a^{\tau}_{h})\bm{\phi}(x^{\tau}_{h},a^{\tau}_{h})^{\top}\approx\mathbf{I}$. We will focus in this section on a fixed episode $k$, and drop the dependency of parameters and value functions on $k$ when it is clear from the context. Now, ignoring the UCB bonus, the least-squares solution (line 5) gives the following estimate of the action-value function:

Our analysis depends on the following two key steps.

However, the function $V_{h+1}$ in Algorithm 1 is again computed by least-squares value iteration in later steps $[h+1,H]$ and it thus inevitably depends on the choices of actions $\{a^{\tau}_{h+1}\}_{\tau=1}^{k-1}$, and thus also samples $\{x^{\tau}_{h+1}\}_{\tau=1}^{k-1}$. Therefore, the concentration of self-normalized process does not apply directly. To resolve this issue, we establish the uniform concentration over all value functions in the following class:

Finally, with the above key observations in mind, our proof proceeds by leveraging and adapting techniques from the literature on tabular MDP and linear bandits. Please see Appendix B and C for the details.

Conclusion

In this paper, we have presented the first provable RL algorithm with both polynomial runtime and polynomial sample complexity for linear MDPs, without requiring a “simulator” or additional assumptions. The algorithm is simply Least-Squares Value Iteration—a classical RL algorithm commonly studied in the setting of linear function approximation—with a UCB bonus. We hope that our work may serve as a first step towards a better understanding of efficient RL with function approximation.

We provide a few additional concluding observations.

Theorem 3.1 claims the total regret to be upper bounded by $\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{3}T})$. One immediate question is what the optimal dependencies on $d$ and $H$ are. Since our setting covers the standard tabular setting, as in shown in Example 2.1, a lower bound can be directly obtained through a reduction from the tabular setting, which gives $\Omega(\sqrt{dH^{2}T})$ for the case of nonstationary transitions . We believe the $\sqrt{H}$ difference between this lower bound and our upper bound is expected because the exploration bonus used in this paper is intrinsically “Hoeffding-type.” Using a “Bernstein-type” bonus can potentially help shave off one $\sqrt{H}$ factor (see for a similar phenomenon in the tabular setting).

In contrast, the optimal dependency on dimension $d$ is more important but is also less clear. In the case where the number of actions is very large, one may attempt to use the lower bound in the linear bandit setting, $\Omega(d\sqrt{T})$, for the case $H=1$. We comment that as soon as $H\geq 2$ (where the Markov transition matters), the assumption of a linear MDP imposes structure on the feature space $\{\bm{\phi}(x,a)|(x,a)\in\mathcal{S}\times\mathcal{A}\}$ (see Proposition A.1). Technically, the standard constructions for the hard instances in the linear bandit lower bound do not respect this structure, so the lower bound does not directly apply. It remains an interesting future direction to determine this optimal dependency on $d$.

On the assumption of linear transition dynamics.

Finally, it remains an interesting future question whether an RL algorithm can be proved to be efficient without assuming a linear structure in the transition dynamics.

Acknowledgements

We thank Alekh Agarwal, Zeyuan Allen-Zhu, Sebastian Bubeck, Nan Jiang and Akshay Krishnamurthy for valuable discussions. This work was supported in part by the DARPA program on Lifelong Learning Machines.

References

Appendix A Properties of Linear MDP

In this section, we present some of the basic properties of linear MDPs.

We start with the most important property of a linear MDP: the action-value function is always linear in the feature map $\bm{\phi}$ for any policy.

The linearity of the action-value functions directly follows from the Bellman equation in Eq. (1):

Second, we show that, under mild conditions, the assumption of a linear transition is necessary for the Bellman error to be zero for all policies $\pi$.

We define the function $Q_{0}(\cdot,\cdot)=\bm{\phi}(\cdot,\cdot)^{\top}\mathbf{w}_{0}$. Additionally, let two policies $\pi_{1}$ and $\pi_{2}$ satisfy

where the second equality holds due to Eq. (10). Thus, by combining Eq. (9) and Eq. (A), we have

For a linear MDP, for any $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, we have

In particular, the first condition in Eq. (12) requires the image of $\bm{\phi}$, $\{\bm{\phi}(x,a)|(x,a)\in\mathcal{S}\times\mathcal{A}\}$, to be contained in a $(d-1)$-dimensional hyperphane.

Appendix B Proof of Theorem 3.1

In this section, we prove Theorem 3.1. We first introduce the notation that is used throughout this section. Then, we present lemmas and their proofs. Finally, we combine the lemmas to prove Theorem 3.1.

Throughout this section, we denote $\Lambda_{h}^{k}$, $\mathbf{w}^{k}_{h}$, and $Q_{h}^{k}$ as the parameters and the Q-value function estimate in episode $k$. Denote value function $V_{h}^{k}$ as $V_{h}^{k}(x)=\max_{a}Q_{h}^{k}(x,a)$. We also denote $\pi_{k}$ as the greedy policy induced by $\{Q_{h}^{k}\}_{h=1}^{H}$. To simplify our presentation, we always denote $\bm{\phi}^{k}_{h}\mathrel{\mathop{:}}=\bm{\phi}(x^{k}_{h},a^{k}_{h})$.

First, we prove two lemmas which state that the linear weights $\mathbf{w}_{h}$ in both the action-value functions and Algorithm 1 are bounded.

Under Assumption A, for any fixed policy $\pi$, let $\{\mathbf{w}^{\pi}_{h}\}_{h\in[H]}$ be the corresponding weights such that $Q_{h}^{\pi}(x,a)=\langle\bm{\phi}(x,a),\mathbf{w}^{\pi}_{h}\rangle$ for all $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$. Then, we have

By the Bellman equation in Eq. (1), we know, for any $h\in[H]$:

Since MDP is linear, by definition, this gives:

For any $(k,h)\in[K]\times[H]$, the weight $\mathbf{w}^{k}_{h}$ in Algorithm 1 satisfies:

where the last step is due to Lemma D.1. The remainder of the proof follows from the fact that $\left\|{\mathbf{w}^{k}_{h}}\right\|=\max_{\mathbf{v}:\left\|{\mathbf{v}}\right\|=1}|\mathbf{v}^{\top}\mathbf{w}^{k}_{h}|$. ∎

Second, we present our main concentration lemma, which is crucial in controlling the fluctuations in least-squares value iteration.

Under the setting of Theorem 3.1, let $c_{\beta}$ be the constant in our definition of $\beta$ (i.e., $\beta=c_{\beta}\cdot dH\sqrt{\iota}$). There exists an absolute constant $C$ that is independent of $c_{\beta}$ such that for any fixed $p\in$, if we let $\mathfrak{E}$ be the event that:

For all $(k,h)\in[K]\times[H]$, by Lemma B.2 we have $\|\mathbf{w}_{h}^{k}\|\leq 2H\sqrt{dk/\lambda}$. In addition, by the construction of $\Lambda_{h}^{k}$, the minimum eigenvalue of $\Lambda_{h}^{k}$ is lower bounded by $\lambda$. Thus, by combining Lemmas D.4 and D.6, we have for any fixed $\varepsilon>0$ that:

Notice that we choose the hyperparameters $\lambda=1$ and $\beta=C\cdot dH\iota$ where $C$ is an absolute constant. Finally, picking $\varepsilon=dH/k$, by Eq. (13), there exists a absolute constant $C>0$ that is independent of $c_{\beta}$ such that

Next, we recursively bound the difference between the value function maintained in Algorithm 1 (without bonus) and the true value function of any policy $\pi$. We bound this difference using their expected difference at next step, plus a error term. This error term can be upper bounded by our bonus with high probability. This is the key technical lemma in this section.

There exists an absolute constant $c_{\beta}$ such that for $\beta=c_{\beta}\cdot dH\sqrt{\iota}$ where $\iota=\log(2dT/p)$, and for any fixed policy $\pi$, on the event $\mathfrak{E}$ defined in Lemma B.3, we have for all $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$ that:

for some $\Delta^{k}_{h}(x,a)$ that satisfies $|\Delta^{k}_{h}(x,a)|\leq\beta\sqrt{\bm{\phi}(x,a)^{\top}(\Lambda^{k}_{h})^{-1}\bm{\phi}(x,a)}$.

By Proposition 2.3 and the Bellman equation Eq. (1), we know for any $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$:

Now, we bound the terms on the right-hand side individually. For the first term,

For the second term, given the event $\mathfrak{E}$ defined in Lemma B.3, we have:

for an absolute constant $c_{0}$ independent of $c_{\beta}$, and $\chi=\log[2(c_{\beta}+1)dT/p]$. For the third term,

Finally, since $\langle\bm{\phi}(x,a),\mathbf{w}^{k}_{h}\rangle-Q_{h}^{\pi}(x,a)=\langle\bm{\phi}(x,a),\mathbf{w}^{k}_{h}-\mathbf{w}^{\pi}_{h}\rangle=\langle\bm{\phi}(x,a),\mathbf{q}_{1}+\mathbf{q}_{2}+\mathbf{q}_{3}\rangle$, by Lemma B.1 and our choice of parameter $\lambda$, we have

for an absolute constant $c^{\prime}$ independent of $c_{\beta}$. Finally, to prove this lemma, we only need to show that there exists a choice of absolute constant $c_{\beta}$ so that

where $\iota=\log(2dT/p)$. We know $\iota\in[\log 2,\infty)$ by its definition, and $c^{\prime}$ is an absolute constant independent of $c_{\beta}$. Therefore, we can pick an absolute constant $c_{\beta}$ which satisfies $c^{\prime}\sqrt{\log 2+\log(c_{\beta}+1)}\leq c_{\beta}\sqrt{\log 2}$. This choice of $c_{\beta}$ will make Eq. (14) hold for all $\iota\in[\log 2,\infty)$, which finishes the proof. ∎

Lemma B.4 implies that by adding appropriate bonuses, $Q^{k}_{h}$ in Algorithm 1 can be always an upper bound of $Q^{\star}_{h}$ with high confidence.

Under the setting of Theorem 3.1, on the event $\mathfrak{E}$ defined in Lemma B.3, we have $Q^{k}_{h}(x,a)\geq Q^{\star}_{h}(x,a)$ for all $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$.

First, we prove the base case, at the last step $H$. The statement holds because $Q^{k}_{H}(x,a)\geq Q^{\star}_{H}(x,a)$. Since the value function at $H+1$ step is zero, by Lemma B.4, we have:

Now, suppose the statement holds true at step $h+1$ and consider step $h$. Again, by Lemma B.4, we have:

Lemma B.4 also easily transforms to a recursive formula for $\delta^{k}_{h}=V^{k}_{h}(x^{k}_{h})-V^{\pi_{k}}_{h}(x^{k}_{h})$. This formula will be very useful in proving the main theorem.

By Lemma B.4 we have that for any $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$:

and finally, by Algorithm 1 and the definition of $V^{\pi_{k}}$ we have

Finally, we are ready to prove the main theorem. We restate our main theorem as follows.

We use the notion of $\delta^{k}_{h}$ and $\zeta_{h}^{k}$ as in Lemma B.6. We condition on the event $\mathfrak{E}$ defined in Lemma B.3 with $\delta=p/2$. By Lemmas B.5 and B.6, we have

We now bound the two terms on the right-hand side of Eq. (15) separately. For the first term, since the computation of $V_{h}^{k}$ is independent of the new observation $x^{k}_{h}$ at episode $k$, we obtain that $\{\zeta^{k}_{h}\}$ is a martingale difference sequence satisfying $|\zeta^{k}_{h}|\leq 2H$ for all $(k,h)$. Therefore, by the Azuma-Hoeffding inequality, for any $t>0$, we have

Hence, with probability at least $1-p/2$, we have

where $\iota=\log(2dT/p)$. Furthermore, for the second term, note that the minimum eigenvalue of $\Lambda_{h}^{k}$ is at least $\lambda$ (which equals to 1) for all $(k,h)\in[K]\times[H]$. Also notice that $\|\bm{\phi}_{h}^{k}\|\leq 1$. By Lemma D.2, for any $h\in[H]$, we have

Moreover, note that $\|\Lambda^{k+1}_{h}\|=\|\sum_{\tau=1}^{k}\bm{\phi}^{k}_{h}(\bm{\phi}^{k}_{h})^{\top}+\lambda\mathbf{I}\|\leq\lambda+k$; this gives

Now, by the Cauchy-Schwartz inequality, we have

which yields an upper bound on the second term in Eq. (15). Finally, combining Eq. (15), Eq. (16), Eq. (18), and with our choice of $\beta=c\cdot dH\sqrt{\iota}$ for some absolute constant c, we conclude that with probability $1-p$:

for some absolute constant $c^{\prime}$. This concludes the proof. ∎

Appendix C Proof of Theorem 3.2

In this section, we prove Theorem 3.2. At a high level, the proof structure is similar to the structure in Appendix B. We will particularly focus on the parts that require different treatments in the misspecified setting.

Throughout this section, we denote $\Lambda_{h}^{k}$, $\mathbf{w}^{k}_{h}$, and $Q_{h}^{k}$ as the parameters and the Q-value functions estimated in episode $k$. Denote the value function $V_{h}^{k}$ as $V_{h}^{k}(x)=\max_{a}Q_{h}^{k}(x,a)$. We denote $\pi_{k}$ as the greedy policy induced by $\{Q_{h}^{k}\}_{h=1}^{H}$. To simplify the presentation, we denote $\bm{\phi}^{k}_{h}\mathrel{\mathop{:}}=\bm{\phi}(x^{k}_{h},a^{k}_{h})$.

First, we establish a lemma that is the counterpart of Lemma 2.3 in the misspecified setting: for any policy $\pi$, its action-value function is always close to a linear function.

Since $\bm{\mu}_{h}$ and $\bm{\theta}_{h}$ satisfy Eq.(4), we have:

We can again show that the linear weights defined in Lemma C.1 are bounded.

Under Assumption B, for any policy $\pi$, let $\{\mathbf{w}^{\pi}_{h}\}_{h\in[H]}$ be the corresponding weights as defined in Lemma C.1. Then, we have

Similar to Lemma B.3, we also bound the stochastic noise in concentration.

Under the setting of Theorem 3.2, let $c_{\beta}$ be the constant in our choice of $\beta_{k}$ (i.e. $\beta_{k}=c_{\beta}\cdot(d\sqrt{\iota}+\zeta\sqrt{kd})H$), There exists an absolute constant $C$ that is independent of $c_{\beta}$ such that for any fixed $p\in$, if we let $\mathfrak{E}$ be the event that:

The proof is essentially the same as the proof for Lemma B.3, with the only difference that $\beta_{k}$ is now bounded by $c_{\beta}(d\sqrt{\iota}+\zeta\sqrt{Kd})H$ instead of $c_{\beta}dH\sqrt{\iota}$ as in Lemma B.3. Because $\zeta\leq 1$ as in Assumption B, the new bound of $\beta_{k}$ only affects the choice of absolute $C$ in Lemma C.3. ∎

In the misspecified case, we also need to bound an error term where the noise can be potentially adversarial instead of stochastic. The adversarial noise is precisely due to model misspecification.

where the last inequality is due to Lemma D.1. ∎

Now we are ready to prove the key lemma, which is the counterpart of Lemma B.4.

There exists an absolute constant $c_{\beta}$ such that for $\beta_{k}=c_{\beta}\cdot(d\sqrt{\iota}+\zeta\sqrt{kd})H$ where $\iota=\log(2dT/p)$, and for any fixed policy $\pi$, on the event $\mathfrak{E}$ defined in Lemma C.3, we have for all $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$ that:

for some $\Delta^{k}_{h}(x,a)$ that satisfies $|\Delta^{k}_{h}(x,a)|\leq\beta_{k}\sqrt{\bm{\phi}(x,a)^{\top}(\Lambda^{k}_{h})^{-1}\bm{\phi}(x,a)}+4H\zeta$.

Now, we bound the terms on the right-hand side individually. For the first term,

For the second term, given the event $\mathfrak{E}$ defined in Lemma C.3, we have:

for an absolute constant $c_{0}$ independent of $c_{\beta}$, and $\chi=\log[2(c_{\beta}+1)dT/p]$. For the third term,

For the fourth term, by Lemma C.4, we have

Finally, since $\langle\bm{\phi}(x,a),\mathbf{w}^{k}_{h}-\mathbf{w}^{\pi}_{h}\rangle=\langle\bm{\phi}(x,a),\mathbf{q}_{1}+\mathbf{q}_{2}+\mathbf{q}_{3}+\mathbf{q}_{4}\rangle$, we have:

for an absolute constant $c^{\prime}$ independent of $c_{\beta}$. As in the proof of Lemma B.4, to prove this lemma, we only need to show that there exists a choice of absolute constant $c_{\beta}$ so that $c_{\beta}\geq 2$, and

This can be done by an picking absolute constant $c_{\beta}$ that satisfies $c^{\prime}\sqrt{\log 2+\log(c_{\beta}+1)}\leq c_{\beta}\sqrt{\log 2}$. ∎

Given Lemma C.5, we can now easily proceed to prove that $Q^{k}_{h}$ is a upper bound of $Q^{\star}_{h}$ up to an error that depends linearly on the misspecification $\zeta$.

Under the setting of Theorem 3.2, on the event $\mathfrak{E}$ defined in Lemma C.3, we have $Q^{k}_{h}(x,a)\geq Q^{\star}_{h}(x,a)-4H(H+1-h)\zeta$ for all $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$.

First, we consider the base case. The statement holds for the last step $H$, i.e., $Q^{k}_{H}(x,a)\geq Q^{\star}_{H}(x,a)-4H\zeta$. Since the value function at $H+1$ step is zero, by Lemma C.5, we have:

Now, suppose the statement holds true at step $h+1$, and consider step $h$. Again, by Lemma C.5, we have:

Therefore, we conclude the proof of this lemma. ∎

The gap $\delta^{k}_{h}=V^{k}_{h}(x^{k}_{h})-V^{\pi_{k}}_{h}(x^{k}_{h})$ also has a recursive formula similar to Lemma B.6.

This is because by Lemma C.5, we have for any $(x,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$:

Finally, by Algorithm 1 and the definition of $V^{\pi_{k}}$ we have

Finally, we are ready to combine all previous lemmas to prove the main theorem in the misspecified setting.

The proof of this theorem is similar to that of Theorem 3.1. We condition on the event $\mathfrak{E}$ defined in Lemma C.3. For for any $(k,h)\in[K]\times[H]$, we define $\delta^{k}_{h}=V^{k}_{h}(x^{k}_{h})-V^{\pi_{k}}_{h}(x^{k}_{h})$. By Lemma C.6, we have $Q_{1}^{k}(x,a)\geq Q_{1}^{*}(x,a)-4H^{2}\zeta$ for all $k\in[K]$, which implies that ${V}^{\star}_{1}({x}^{k}_{1})-{V}^{\pi_{k}}_{1}({x}^{k}_{1})\leq\delta_{1}^{k}+4H^{2}\zeta$. Furthermore, by Lemma C.7, on the event $\mathfrak{E}$ we have:

where we use the fact that $T=HK$. Since $\{\zeta^{k}_{h}\}$ is a martingale difference sequence with each term bounded by $2H$, the Azuma-Hoeffding inequality implies that

holds with probability at least $1-p/2$, where $\iota=\log(2dT/p)$. Moreover, by the Cauchy-Schwarz inequality, we have

Moreover, since we set $\beta_{k}=c\cdot(d\sqrt{\iota}+\zeta\sqrt{kd})H$ for some absolute constant $c>0$, we have

Therefore, combining Eq. (21), Eq. (22), and Eq. (23), we have

Finally, combining Eq. (C), Eq. (20), and Eq. (24), we obtain

for some absolute constant $c^{\prime\prime}$. This concludes the proof of the theorem. ∎

Appendix D Auxiliary Lemmas

This section presents several auxiliary lemmas and their proofs.

First, we present a few important short inequalities for summations.

Since $\lambda_{\min}(\Lambda_{0})\geq 1$ and $\|\bm{\phi}_{t}\|\leq 1$ for all $j\geq 0$, we have

Note that, for any $x\in$, it holds that $\log(1+x)\leq x\leq 2\log(1+x)$. Therefore, we have

Moreover, for any $t\geq 0$, by the definition of $\Lambda_{t}$, we have

Therefore, combining Eq. (25) and Eq. (26), we conclude the proof. ∎

D.2 Concentration inequalities for self-normalized processes

Next, we present a few concentration inequalities. The following one provides a concentration inequality for the standard self-normalized processes.

When specializing this concentration inequality to our setting, we require uniform concentration over all value functions $V$ within a function class $\mathcal{V}$. This uniform concentration incurs an additional term that depends logarithmically on the covering number of $\mathcal{V}$.

For any $V\in\mathcal{V}$, we know there exists a $\widetilde{V}$ in the $\varepsilon$-covering such that

where we can apply Theorem D.3 and a union bound to the first term. Also, it is not hard to bound the second term by $8k^{2}\varepsilon^{2}/\lambda$. ∎

To compute the covering number of function class $\mathcal{V}$, we first require a basic result on the covering number of a Euclidean ball as follows. We refer readers to classical material, such as Lemma 5.2 in , for its proof.

Now, we are ready to compute the covering number of $\mathcal{V}$.

Equivalently, we can reparametrize the function class $\mathcal{V}$ by let $\mathbf{A}=\beta^{2}\Lambda^{-1}$, so we have

for $\left\|{\mathbf{w}}\right\|\leq L$ and $\left\|{\mathbf{A}}\right\|\leq B^{2}\lambda^{-1}$. For any two functions $V_{1},V_{2}\in\mathcal{V}$, let them take the form in Eq. (27) with parameters $(\mathbf{w}_{1},\mathbf{A}_{1})$ and $(\mathbf{w}_{2},\mathbf{A}_{2})$, respectively. Then, since both $\min\{\cdot,H\}$ and $\max_{a}$ are contraction maps, we have

where the second last inequality follows from the fact that $|\sqrt{x}-\sqrt{y}|\leq\sqrt{|x-y|}$ holds for any $x,y\geq 0$. For matrices, $\left\|{\cdot}\right\|$ and $\left\|{\cdot}\right\|_{\text{F}}$ denote the matrix operator norm and Frobenius norm respectively.