Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics

## Abstract

Abstract We study computationally and statistically efficient Reinforcement Learning algorithms for the linear Bellman Complete setting, a setting that uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR). While it is known from the prior works that this setting is statistically tractable, it remained open whether a computationally efficient algorithm exists. Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic.
Our approach is based on randomization: we inject random noise into least square regression problems to perform optimistic value iteration. Our key technical contribution is to carefully design the noise to only act in the null space of the training data to ensure optimism while circumventing a subtle error amplification issue.

###### Proof.

###### Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics

## 1 Introduction

Various application domains of Reinforcement Learning (RL)—including game playing, robotics, self-driving cars, and foundation models—feature environments with large state and action spaces. In such settings, the learner aims to find a well performing policy by repeated interactions with the environment to acquire knowledge. Due to the high dimensionality of the problem, function approximation techniques are used to generalize the knowledge acquired across the state and action space. Under the broad category of function approximation, model-free RL stands out as a particularly popular approach due to its simplicity of implementation and relatively low sample efficiency in practice. In model-free RL, the learner uses function approximation (e.g., an expressive function class like deep neural networks) to model the state-action value function of various policies in the underlying MDP. In fact, the combination of model-free RL with various empirical exploration heuristics has led to notable empirical advances, including breakthroughs in game playing (Silver et al., ; Berner et al., ), robot manipulation (Andrychowicz et al., ), and self-driving (Chen et al., ). (^†^†^⋆Equal Contribution. Emails: {rw646@cornell.edu, sekhari@mit.edu, akshaykr@microsoft.com, ws455@cornell.edu})

Theoretical advancements have paralleled the practical successes in RL, with tremendous progress in recent years in building rigorous statistical foundations to understand what structures in the environment and the function class suffice for sample-efficient RL. These advancements are supported by optimal exploration strategies that align with the corresponding structural assumptions, and by now we have a rich set of tools and techniques for sample efficient RL in MDPs with large state/action spaces
(Russo and Van Roy, ; Jiang et al., ; Sun et al., ; Wang et al., ; Du et al., ; Jin et al., ; Foster et al., ; Xie et al., ). However, despite a rigorous statistical foundation, a significant challenge remains: many of these theoretically rigorous approaches for rich function approximation are not computationally feasible, and thus have limited practical applicability. For example, many algorithms require solving complex optimization problems that are computationally intractable in practice (Zanette et al., ); others require deterministic dynamics and initial state (Du et al., ); and some methods depend on maintaining large and complex version spaces (Jin et al., ; Du et al., ) which is intractable in terms of both memory and computation.

One of the most striking examples of this statistical computation gap is observed in the Linear Bellman Completeness setting, which is perhaps one of the simplest learning settings. Linear Bellman completeness serves as a bridge between RL and control theory literature as it provides a unified framework to capture both Linear MDPs (Jin et al., ; Agarwal et al., ; Zanette et al., ) and additionally, the Linear Quadratic Regulator (LQR), the two most popular models in RL and control respectively. In particular, the linear Bellman completeness setting captures MDPs where the state-action value function of the optimal policy is a linear function of some pre-specified feature representations (of states and actions), and the Bellman backups of linear state-action value functions are linear (w.r.t. some feature representation). Naturally, for this setting, the learner utilizes the class $\mathcal{F}$ consisting of all linear functions over the given feature representation as the value function class for model-free RL. In addition to considering a linear class, we also assume that the class $\mathcal{F}$ exhibits low inherent Bellman error—–a structural assumption that quantifies the error in approximating the Bellman backup of functions within $\mathcal{F}$. The first assumption, i.e., linearity of optimal state-action value function, is perhaps the simplest modeling assumption one can make in RL with function approximation. Furthermore, emerging evidence suggests that linearity is practically useful, as with adequate feature representation, linear functions can represent value functions in various domains. The second assumption, i.e. low inherent Bellman error of the class, while being a bit mysterious, is a natural condition for statistical tractability for classic algorithms such as Fitted Q-iteration (FQI) and temporal difference (TD) learning with linear function approximation (Munos, ; Zanette et al., ). It is also well-known that linearity alone does not suffice for efficient RL (Wang et al., ; Weisz et al., ).

While the prior works have shown that RL with linear bellman completeness is statistically tractable, and one can learn with sample complexity that scales polynomially with both $d$ and $H$ (where $d$ is the dimensionality of the feature representation and $H$ is the horizon of the RL problem), the proposed algorithms that obtain such sample complexity in the online RL setting are not computationally efficient. Given the simplicity of the problem, it was conjectured that a computationally efficient algorithm should exist. However, no such algorithms were proposed. Unfortunately, the classical approaches of combining supervised learning techniques with RL in the online setting, e.g., value function iteration, which are computationally efficient by design, fail to extend to be statistically tractable due to exponential blowups from error compounding, especially without making unrealistic norm-boundedness assumptions. On the other hand, the techniques of adding quadratic exploration bonuses, e.g., the one proposed in LinUCB (Li et al., ) and used in LSVI for linear MDP, also fail here as Bellman backups of quadratic functions are not necessarily within the linear class $\mathcal{F}$. In fact, the search for a computationally efficient algorithm with large action spaces is open even when the transition dynamics are deterministic.

In this work, we provide the first computationally efficient algorithm for the linear Bellman complete setting with deterministic dynamics, that enjoys regret bound of $\widetilde{O}(d^{5/2}H^{5/2}+d^{2}H^{3/2}T^{1/2})$
for feature dimension $d$, horizon $H$, and number of rounds $T$. Importantly, our algorithm works with large action spaces, stochastic reward functions, and stochastic initial states. The key ideas of our algorithm are twofold: using randomization to encourage exploration and leveraging a span argument to bound the regret.
While adding random noise to the learn parameters has been quite successful in linear function approximation, unfortunately, for our specific setting, since we need to add sufficiently large noise to cancel out the estimation error, blind randomization can cause the corresponding parameters to grow exponentially with the horizon. We avoid paying for this blow-up by only adding noise to the null space of the data. In particular, when the dynamics are deterministic, by adding exploration noise only in the null space, we can learn the value function exactly for any trajectories that lie within the span of the data seen so far. Additionally, a simple span argument bounds the number of times the trajectories fall outside the span of the historical data. Together, these techniques leads to our polynomial sample complexity bound. The resulting algorithm relies on linear regression oracles under convex constraints, which we show can be approximately solved via a random-walk-based algorithm (Bertsimas and Vempala, ).

## 2 Related Works

Computational Efficient RL under Linear Bellman Completeness.
Numerous works have focused on computationally efficient RL within the scope of linear Bellman completeness (LBC). The simplest setting is tabular MDPs where computationally efficient and near-optimal algorithms have been well-known (Azar et al., ; Zhang et al., ; Jin et al., ). Tabular MDPs are generalized by linear MDPs (Jin et al., ), where computationally efficient algorithms are also known (Jin et al., ; Agarwal et al., ; He et al., ). However, in the setting of linear Bellman completeness, which captures linear MDPs, computationally efficient algorithm remains open. Existing works have relied on various assumptions to achieve computational efficiency, such as few actions (Golowich and Moitra, ) and assuming MDPs are “explorable” (Zanette et al., ). We provided a comprehensive overview of the literature in Section 3.2.

Exploration via Randomization.
Random noise has been a powerful alternative to the bonus-based exploration in the RL literature. A typical approach is Randomized Least-Squares Value Iteration (RLSVI) (Osband et al., ), which injects Gaussian noise into the least-squares estimate and achieves near-optimal worst-case regret for linear MDPs (Agrawal et al., ; Zanette et al., ). Similar technique has also been applied to preference-based RL under linear MDPs, resulting in the first computationally efficient algorithm with near-optimal regret guarantees (Wu and Sun, ).
However, these approaches inject random noise on at least the same scale as the estimation error, which results in an exponential norm blow-up of the learned parameters. To mitigate this issue, they truncate the value function at each step. However, this truncation trick is feasible only in low-rank MDPs but becomes challenging under Bellman completeness, as the Bellman backup of truncated value estimates may no longer be linear. Consequently, existing RLSVI algorithms cannot address linear Bellman complete problems. To tackle these challenges, we need new techniques capable of managing exponentially large parameter values.

Beyond Linear Bellman Completeness.
Many structural conditions capture linear Bellman completeness, such as Bilinear class (Du et al., ), Bellman eluder dimension (Jin et al., ), Bellman rank (Jiang et al., ), witness rank (Sun et al., ), and decision-estimation coefficient (Foster et al., ).
While statistically efficient algorithms exist for these settings, no computationally efficient algorithms are known.

## 3 Preliminaries

A finite-horizon Markov Decision Process (MDP) is given by a tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},H,\mathsf{T},r,\mu)$ where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $H\in\mathbb{N}$ is the horizon, $\mathsf{T}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the transition function, $r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the reward function and $\mu\in\Delta(\mathcal{S})$ is the initial state distribution. Given a policy $\pi:\mathcal{S}\mapsto\Delta(\mathcal{A})$, we denote $Q_{h}^{\pi}(s,a)=\mathbb{E}_{\pi}\left[\sum_{i=h}^{H}r_{i}\,|\,s_{h}=s,a_{h}=a\right]$ as the layered state-action value function of policy $\pi$ and $V_{h}^{\pi}(s)=Q_{h}^{\pi}(s,\pi(s))$ as the state value function. The optimal value function is denoted by $V_{h}^{\star}(s)=\max_{\pi}V_{h}^{\pi}(s)$, and the optimal policy is denoted by $\pi^{\star}$.

We focus on the setting of linear function approximation and consider the following linear Bellman completeness, which ensures that the Bellman backup of a linear function remains linear.

###### Definition 1 (Linear Bellman Completeness) .

An MDP is said to be linear Bellman complete with respect to a feature mapping $\phi$ if there exists a mapping $\mathcal{T}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ so that, for all $\theta\in\mathbb{R}^{d}$ and all $(s,a)\in\mathcal{S}\times\mathcal{A}$, it holds that

$$ $\langle\mathcal{T}\theta,\phi(s,a)\rangle=\mathop{\mathbb{E}}_{s^{\prime}\sim \mathsf{T}(s,a)}\max_{a^{\prime}}\left\langle\theta,\phi(s^{\prime},a^{\prime} )\right\rangle.$ $$

Moreover, we require that, for all $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, the random reward is bounded in $[0,1]$ with mean $r_{h}(s,a)=\langle\omega_{h}^{\star},\phi(s,a)\rangle$ for some unknown $\omega_{h}^{\star}\in\mathbb{R}^{d}$.

We assume $\|\phi(s,a)\|_{2}\leq 1$ for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$. Notably, we do not impose any upper bound on $\|\omega_{h}^{\star}\|_{2}$ or any $\ell_{2}$-norm non-expansiveness of the Bellman backup, distinguishing us from existing works—in Section 3.1, we discuss why many existing definitions of linear Bellman completeness fail to capture even tabular MDPs or linear MDPs due to unrealistic $\ell_{2}$-norm boundedness assumptions. We further assume the feature space spans $\mathbb{R}^{d}$, i.e., ${\rm{span}}(\{\phi(s,a):s\in\mathcal{S},a\in\mathcal{A}\})=\mathbb{R}^{d}$; otherwise, we can project the feature space onto its span or use pseudo-inverse in the analysis when needed. We can verify that the linear Bellman completeness captures both linear MDPs and Linear Quadratic Regulators (LQR). The proof is in Appendix D.

Next, we assume the state transition is deterministic.

###### Assumption 1 (Deterministic transitions) .

For all $s\in\mathcal{S}$ and $a\in\mathcal{A}$, there is a unique state $s^{\prime}\in\mathcal{S}$ to which the system transitions to after taking action $a$ on state $s$.

We emphasize that, although the transition is deterministic, the initial state distribution is stochastic (while we assume that $s_{t,1}$ is independently sampled from an initial distribution $\mu$, our results extend to the scenarios when $\{s_{t,1}\}_{t\leq T}$ are adversarially chosen). Additionally, the reward signals are stochastic. Hence, learning is still challenging in this case. The goal is to achieve low regret over $T$ rounds. The regret is defined as

$$ $\displaystyle{\rm{Reg}}_{T}\coloneqq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T} \big{(}V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\big{)}\right].$ $$

The expectation here is taken over the randomness of algorithm and reward signals. While it is defined as an average for simplicity, a concentration inequality can yield the high-probability regret. In this paper, we use asymptotic notations $\widetilde{\Theta}(\cdot)$ and $\widetilde{O}(\cdot)$ to hides logarithmic and constant factors.

###### Definition 1 (Linear Bellman Completeness) .

###### Assumption 1 (Deterministic transitions) .

### 3.1 Other Linear Bellman Completeness Definitions in the Literature

Various other definitions of Linear Bellman Completeness have been considered in the literature. In the following, we demonstrate that most these prior definitions are somewhat limited due to unrealistic $\ell_{2}$-norm assumptions. Below, we present two commonly imposed assumptions found in existing works, and later, we provide examples illustrating their limitations.

(1) Assuming Bounded $\ell_{2}$-norm of Parameters.
Golowich and Moitra (); Zanette et al. (, ) assume that any value function under consideration has its parameters bounded in $\ell_{2}$-norm, i.e., applying the Bellman backup, the resulting state-action value function always lies in $\{Q:Q(s,a)=\langle\phi(s,a),\theta\rangle,\,\|\theta\|_{2}\leq R\}$ where $R$ is a pre-fixed polynomial in the dimension of the feature space. We will show that this assumption is unrealistic since $\|\theta\|_{2}$ is unnecessarily bounded under linear Bellman completeness.

(2) Assuming Non-expansiveness of Bellman Backup in $\ell_{2}$-norm. Song et al. () assume that, after applying the Bellman backup, the $\ell_{2}$-norm of the value function parameters will not increase. In particular, for any $\theta$, they assume the existence of parameter $\theta^{\prime}$ such that $\|\theta^{\prime}\|_{2}\leq\|\theta\|_{2}$ and $\langle\phi(s,a),\theta^{\prime}\rangle=\mathop{\mathbb{E}}_{s^{\prime}\sim
\mathsf{T}(s,a)}\max_{a^{\prime}}\langle\phi(s^{\prime},a^{\prime}),\theta\rangle$ for all $s,a$. This assumption is even stronger than the previous one and does not hold even in tabular MDPs, as we will show in the second example below.

The following example demonstrates that the two assumptions do not generally hold under linear Bellman completeness by showing that the $\ell_{2}$-norm amplification can actually be arbitrarily large.

###### Example 1 (Arbitrarily Large $\ell_{2}$ -norm on Parameters) .

Consider an MDP with two states $\{s_{1},s_{2}\}$, a single action $a$, and horizon $H=1$. The agent starts at the initial state $s_{1}$, and on taking the action $a$, deterministically transitions to $s_{2}$. We define the feature vectors $\phi(s_{1},a)\coloneqq(\varepsilon,0)^{\top}$ and $\phi(s_{2},a)=(1,0)^{\top}$ for some $\varepsilon>0$. We can verify that linear Bellman completeness is satisfied—for any $\theta=(a,b)^{\top}$, we have $\mathcal{T}\theta=(a/\varepsilon,0)^{\top}$. However, assuming $b=0$, the $\ell_{2}$-norm of $\mathcal{T}\theta$ is $\varepsilon^{-1}$ times that of $\theta$. Since $\varepsilon$ can be arbitrarily small, the resulting $\ell_{2}$-norm amplification can be arbitrarily large.

As the above example leverages a careful design of the feature representation, one might hope that non-expansiveness could hold under stronger representation assumptions (e.g., when state space is tabular). Unfortunately, the following example shows that Bellman backup can be expansive even in tabular MDPs.

###### Example 2 (Expansiveness of Bellman Backup in $\ell_{2}$ -norm) .

Consider a tabular MDP with $H=2$, $S$ states $\{s_{1},\dots,s_{S}\}$ in the first layer, a single state $\overline{s}$ in the second layer, and a single action $a$. On taking action $a$ in any state in the first-layer, the agent deterministically transitions to $\overline{s}$, and on taking action $a$ in $\overline{s}$ deterministically yields a reward of 1. Since linear Bellman completeness captures tabular MDPs with one-hot encoded features where $\phi(s_{i},a)=e_{i}\in\mathbb{R}^{S+1}$ for $i\leq S$ and $\phi(\overline{s},a)=(0,\dots,0,1)^{\top}$. Note that the state-action value function at the second layer can be parameterized by $\theta_{2}=(0,\dots,0,1)^{\top}$. However, applying the Bellman backup, sine the return-to-go for any first-layer state $s_{i}$ is 1 (because $\overline{s}$ always yields a reward of 1), the backed-up value function must be parameterized by $\theta_{1}=(1,1,\dots,1)^{\top}$. Here, we find that $\|\theta_{1}\|_{2}/\|\theta_{2}\|_{2}=\sqrt{S}$, thus showing that Bellman backup cannot guarantee non-expansiveness of the $\ell_{2}$-norm.

In contrast, our definition does not assume any $\ell_{2}$-norm bound or $\ell_{2}$-norm non-expansiveness of the parameters. Unfortunately, without these assumptions, the ground truth parameter of the optimal value function can exponentially blow up with the horizon, thus invalidating prior works. Our key contribution is to provide an algorithm that is computationally efficient even if the underlying parameter norm blows up.

###### Example 1 (Arbitrarily Large ℓ 2 subscript ℓ 2 \ell_{2} roman_ℓ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT -norm on Parameters) .

###### Example 2 (Expansiveness of Bellman Backup in ℓ 2 subscript ℓ 2 \ell_{2} roman_ℓ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT -norm) .

### 3.2 Other Prior Works on Linear Bellman Completeness

In this section, we review prior efforts on efficient RL under linear Bellman completeness and discuss various assumptions and limitations underlying these approaches.

Algorithms under Generative Access.
A generative model takes as input a state-action pair $(s,a)$ and returns a sample $s^{\prime}\sim\mathsf{T}(\cdot\,|\,s,a)$ and the reward signal. With such a generative model, Linear Least-Squares Value Iteration (LSVI) can achieve statistical and computational efficiency (Agarwal et al., ). However, generative access is a rather strong assumption, and in contrast, our work aims to operate under the much weaker online access model.

Algorithms under Explorability Assumption.
Zanette et al. () propose a reward-free algorithm under the assumption that every direction in the parameter space is reachable. While the algorithm is computationally efficient, this assumption seems strong. When translating it into tabular MDPs, it assumes that any state can be reached with a probability bounded below by some positive constant. This does not hold if there are unreachable states or even if the probability of reaching them is exponentially small. Additionally, they assume $\ell_{2}$-norm boundedness of parameters, which is unrealistic as discussed in the previous section.

Computationally Intractable Algorithms.
Zanette et al. () present a computationally intractable algorithm that requires solving an intractable optimization problem. Furthermore, their approach relies on the unrealistic $\ell_{2}$-norm bound assumption on the parameters. In comparison, we only rely on access to a squared loss minimization oracle.

Few action MDPs.
Golowich and Moitra () propose a computationally efficient algorithm under linear Bellman completeness, inspired by the bonus-based exploration approach in LSVI-UCB (Jin et al., ) for Linear MDPs. While their algorithm extends to stochastic MDPs, both the sample complexity and running time have exponential dependence on the size of the action space. Additionally, they also assume $\ell_{2}$-norm boundedness of the parameters. In comparison, our algorithm extends to possibly infinite action spaces but relies on the transition dynamics to be deterministic (though, the initial state could be stochastic).

Deterministic Rewards or Deterministic Initial State.
Some prior works provide computationally and statistically efficient algorithms under stronger assumptions that can also be extended for the linear Bellman completeness settings (under similarly stronger assumptions). Du et al. () provide an algorithm based on a span argument that is efficient for MDPs that have linear state-action value function for the optimal policy (a.k.a. the Linear $Q^{\star}$ setting), deterministic transition dynamics, deterministic initial state $s_{1}$, and stochastic rewards. Unfortunately, their approach crucially relies on the initial state $s_{1}$ being deterministic and cannot extend to more general settings with stochastic initial states, as we consider in our paper. Another line of work due to Wen and Van Roy () considers the $Q^{\star}$-realizable setting with deterministic dynamics, deterministic rewards, stochastic initial states, and bounded eluder dimension, and can be extended to the linear bellman completeness setting when both rewards and dynamics are deterministic. However, their algorithm fails to converge when rewards are stochastic and is thus not applicable to the problem setting that we consider in this paper.

Efficient Algorithm in the hybrid RL setting.
Song et al. () develop efficient algorithms for the hybrid RL setting, where the learner has access to both online interaction and an offline dataset. However, they do not have an fully online algorithms and their approach assumes non-expansiveness of the $\ell_{2}$-norm of the Bellman backup.

Finally, we emphasize again that none of the prior works address the problem under both stochastic initial states and rewards and large action spaces. This is the gap we aim to fill with this work.

## 4 Algorithm

In this section, we present our algorithm for online RL under linear Bellman completeness. See Algorithm 1 for pseudocode.
The input to the algorithm consists of three components. First, the noise variances, $\{\sigma_{h}\}_{h=1}^{H}$ and $\sigma_{{\rm{R}}}$, control the scale of the random noise. Second, a D-optimal design (defined below) for the feature space.

###### Definition 2 (D-optimal design) .

The D-optimal design for the set of features $\Phi=\{\phi(s,a):s\in\mathcal{S},a\in\mathcal{A}\}$ is a distribution $\rho$ over $\Phi$ that maximizes $\log\det\left(\sum_{\phi\in\Phi}\rho(\phi)\phi\phi^{\top}\right)$.

There always exist D-optimal designs with at most $O(d^{2})$ support points (Lemma 23). Many efficient algorithms can be applied to find approximate D-optimal designs such as the Frank-Wolfe. Lastly, the algorithm requires a constrained squared loss minimization oracle $\mathcal{O}^{{\rm{sq}}}$. Note that we are not requiring any strong oracle, and we introduce an instantiation of $\mathcal{O}^{{\rm{sq}}}$ in Section 7. For now, we assume the oracle is exact, and later we will consider approximate oracles (Section 5.2).

Figure: Algorithm 1 Null Space Randomization for Linear Bellman Completeness

The algorithm begins by initializing the covariance matrix $\Sigma_{1,h}$ for all $h\in[H]$ using the optimal design, which differs from most standard LSVI-type algorithms where the it is initialized to the identity matrix. We believe that the identity matrix is unsuitable here since we do not assume any $\ell_{2}$-norm bound on the parameters. Additionally, recalling that we assume the feature space spans $\mathbb{R}^{d}$, it ensures $\Sigma_{t,h}$ is invertible for all $t$ and $h$. Otherwise, pseudo-inverses can be used instead.

At each round $t\in[T]$, the algorithm operates in a backward manner starting from the last horizon $H$. For each $h\in[H]$, it first constructs the orthogonal projection matrix $P_{t,h}$ onto the span of the historical data.
It then decomposes the D-optimal design points into the span and null space components using the projection and constructs $\Lambda_{t,h}$. By separating the span and null space components, it facilitates clearer concentration bounds for the subsequent Gaussian noise.

The algorithm then performs constrained squared loss regression to estimate the value function and reward function. Here we define $\mathscr{O}(W)\coloneqq\{\theta\in\mathbb{R}^{d}:|\langle\theta,\phi(s,a)
\rangle|\leq W\text{ for all }s\in\mathcal{S},a\in\mathcal{A}\}$ for any $W>0$. This *convex* constrained set is defined by the $\ell_{\infty}$-functional-norm bound instead of the $\ell_{2}$-norm because we do not assume any bound on the $\ell_{2}$-norm of the learned parameters. Here we define $W_{h}=\widetilde{\Theta}((d\sqrt{mH})^{H-h}(d^{3/2}+d\sqrt{mH}))$ (detailed definition deferred to Appendix B). We note that although $W_{h}$ appears exponential, which may seem suspicious, this does not affect our sample efficiency due to the span argument that we introduce in the analysis. We note that prior RLSVI algorithms used truncation on value functions to explicitly avoid such an exponential blow-up. However, truncation does not work for linear Bellman completeness setting since the Bellman backup on a truncated value function is not necessarily a linear function anymore.

Next, the algorithm perturbs the estimated parameters by adding Gaussian noise. The noise for the value function act only in the null space of the data covariance matrix. This ensures optimism while keeping the estimate accurate in the span space. It is a key modification from the standard RLSVI algorithm. The perturbation for the reward function is standard.

Finally, the algorithm constructs the value function for the current horizon and define policy as the greedy policy with respect to this value function. The trajectory is generated by the greedy policy, and the covariance matrix is then updated.

###### Definition 2 (D-optimal design) .

## 5 Analysis

In this section, we provide the theoretical guarantees of Algorithm 1. A proof sketch can be found in Section 6 and detailed proofs are in Appendix B. We first consider the case where the squared loss minimization oracle is exact. We then extend the analysis to the approximate oracle and the low inherent linear Bellman error setting in subsequent sections.

### 5.1 Prelude: Learning with Exact Square Loss Minimization Oracle

We first consider the most ideal setting where the squared loss minimization oracle is exact.

###### Assumption 2 (Exact Squared Loss Minimization Oracle) .

10 of Algorithm 1 is solved exactly.

Then, we have the following regret bound. A proof sketch is provided in Section 6 for the readers convenience, and the full proof can be found in Appendix B.

###### Theorem 1 (Regret Bound with Exact Oracle) .

Under Assumptions 2 and 1,
executing Algorithm 1 with parameters $\sigma_{{\rm{R}}}=\widetilde{\Theta}(\sqrt{dH\log(HT)})$ and $\sigma_{h}=\widetilde{\Theta}((d\sqrt{mH})^{H-h+1}(\sqrt{d}+\sqrt{mH}))$, we have

$$ $\displaystyle{\rm{Reg}}_{T}=\widetilde{O}(d^{5/2}H^{5/2}+d^{2}H^{3/2}\sqrt{T}).$ $$

This result has several notable features. First, it does not depend on the number of actions. The only requirement for the action space is the ability to compute the argmax. Second, the $\sqrt{T}$-dependence on $T$ is optimal, as it is necessary even in the bandit setting. Additionally, we emphasize that the dependence on $\sqrt{T}$ arises solely from reward learning due to the application of elliptical potential lemma. In fact, if the reward function is known, our regret bound can be as small as $\widetilde{O}(dH^{2})$, depending on $T$ up to logarithmic factors. We elaborate on this observation in Section 6. As a standard practice, Theorem 1 can be converted into a sample complexity bound.

###### Corollary 1 (Sample Complexity Bound) .

Let $\varepsilon\leq 1$.
Under the same setting as Theorem 1, letting $T\geq\Omega(d^{4}H^{3}/\varepsilon^{2})$, we get that the policy $\widehat{\pi}$ chosen uniformly from the set $\pi_{1},\dots,\pi_{T}$ enjoys performance guarantee $\mathop{\mathbb{E}}[V^{\star}-V^{\widehat{\pi}}]\leq\varepsilon$.

###### Assumption 2 (Exact Squared Loss Minimization Oracle) .

###### Theorem 1 (Regret Bound with Exact Oracle) .

###### Corollary 1 (Sample Complexity Bound) .

### 5.2 Learning with Approximate Square Loss Minimization Oracle

###### Assumption 3 (Approximate Squared Loss Minimization Oracle) .

We assume access to an approximate squared loss minimization oracle $\mathcal{O}^{{\rm{sq}}}_{{\rm{apx}}}$ that takes as input a problem of the form:
$\operatorname*{argmin}_{\theta\in\mathscr{O}(W)}g(\theta)\coloneqq\sum_{(\phi(
s,a),u)\in\mathcal{D}}(\langle\theta,\phi(s,a)\rangle-u)^{2}$
where $\mathscr{O}(W)=\{\theta\in\mathbb{R}^{d}\mid{}\lvert\langle\theta,\phi(s,a)
\rangle\rvert\leq W\}$ for some $W\in\mathbb{R}$ is a convex set, and $\mathcal{D}$ is a dataset of tuples $\{(\phi(s,a),u)\}$. The oracle returns a point $\widehat{\theta}$ that satisfies
$g(\widehat{\theta})-\min_{\theta\in\mathscr{O}(W)}g(\theta)\leq\varepsilon^{2}
_{1}$
and
$\widehat{\theta}\in\mathscr{O}(W+\varepsilon_{2})$
where $\varepsilon_{1},\varepsilon_{2}\leq 1$ are precision parameters of the oracle.

With approximate oracle, the regret bound depends on an additional quantity defined below.

###### Assumption 4 .

There exists a constant $\gamma>1$ such that, for any $r\leq d$, and for any $\phi_{1},\phi_{2},\dots,\phi_{r}\in\Phi$, the eigenvalue of the matrix
$\Sigma\coloneqq\sum_{i=1}^{r}\phi_{i}\phi_{i}^{\top}$
is either zero or at least $1/\gamma^{2}$.

As a concrete example, it holds with $\gamma=1$ when the MDP is tabular. This assumption implies that the eigenvalues of $\Sigma^{\dagger}$ are at most $\gamma^{2}$. Consequently, for any vector $\phi\in\Phi$, we have $\|\phi\|_{\Sigma^{\dagger}}\leq\|\phi\|_{2}\gamma\leq\gamma$. This lower bound on the norm of any vector is exactly what we need for the analysis of an approximate oracle, while Assumption 4 simply serves as a sufficient condition for it.
The following theorem provides the regret bound with the approximate oracle in terms of parameters $\varepsilon_{1},\varepsilon_{2}$ and $\gamma$.

###### Theorem 2 (Regret Bound with Approximate Oracle) .

Under Assumptions 3, 1 and 4, executing Algorithm 1 with $\sigma_{{\rm{R}}}=\widetilde{\Theta}(\sqrt{dH})$ and $\sigma_{h}=\widetilde{\Theta}((d\sqrt{mH})^{H-h+1}(\varepsilon_{1}\gamma\sqrt{
H}+\sqrt{d}+\sqrt{mH})$, we have

$$ $\displaystyle{\rm{Reg}}_{T}=\widetilde{O}\big{(}d^{5/2}H^{5/2}+d^{2}H^{3/2} \sqrt{T}+\varepsilon_{1}\gamma\big{(}dH^{2}+d^{3/2}H\sqrt{T}\big{)}\big{)}.$ $$

Compared to Theorem 1, the regret bound has an additional term that depends on the approximation error $\varepsilon_{1}\gamma$. Typically, $\varepsilon_{1}$ can be exponentially small with respect to the relevant parameters, as we later discuss in Section 7. Hence, we allow $\gamma$ to be exponentially large. Moreover, we note that $\varepsilon_{2}$ does not appear in the regret bound since it only affects the constraint violation of the regression, whose effect to the statistical guarantees is of lower order. In addition, we emphasize that the regret bound does not depend on the number of actions, and the dependence on $T$ remains optimal, similar to the previous theorem.

###### Assumption 3 (Approximate Squared Loss Minimization Oracle) .

###### Assumption 4 .

###### Theorem 2 (Regret Bound with Approximate Oracle) .

#### 5.2.1 Learning with Low Inherent Linear Bellman Error

Now we consider the setting where the MDP has low inherent linear Bellman error.

###### Definition 3 (Inherent Linear Bellman Error) .

Given $\varepsilon_{\rm{B}}\leq 1$, an MDP $\mathcal{M}$ is said to have $\varepsilon_{\rm{B}}$-inherent linear Bellman error with respect to a feature mapping $\phi$ if there exists a mapping $\mathcal{T}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ so that, for all $\theta\in\mathbb{R}^{d}$ and all $(s,a)\in\mathcal{S}\times\mathcal{A}$, it holds that
$|\langle\mathcal{T}\theta,\phi(s,a)\rangle-\mathop{\mathbb{E}}_{s^{\prime}\sim
\mathsf{T}(s,a)}\max_{a^{\prime}}\left\langle\theta,\phi(s^{\prime},a^{\prime}
)\right\rangle|\leq\varepsilon_{\rm{B}}$.
Moreover, we require that, for all $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, the random reward is bounded in $[0,1]$ with $|r_{h}(s,a)-\left\langle\omega_{h}^{\star},\phi(s,a)\right\rangle|\leq
\varepsilon_{\rm{B}}$ for some unknown $\omega_{h}^{\star}\in\mathbb{R}^{d}$.

With low inherent Bellman error, Assumption 4 is still necessary. The following theorem provides the regret bound in this case. We assume the exact oracle for simplicity.

###### Theorem 3 (Regret Bound with Low Inherent Bellman Error) .

Assume the MDP has $\varepsilon_{\rm{B}}$-inherent Bellman error.
Under Assumptions 2, 1 and 4,
when executing Algorithm 1 with parameters $\sigma_{{\rm{R}}}=\widetilde{\Theta}(\sqrt{dH+\varepsilon_{\rm{B}}HT})$ and $\sigma_{h}=\widetilde{\Theta}((d\sqrt{mH})^{H-h+1}(\varepsilon_{\rm{B}}\gamma
\sqrt{HT}+\sqrt{\varepsilon_{\rm{B}}T}+\sqrt{d}+\sqrt{mH}))$, we have

$$ $\displaystyle{\rm{Reg}}_{T}=\widetilde{O}$ $\displaystyle\Big{(}d^{5/2}H^{5/2}+d^{2}H^{3/2}\sqrt{T}+\sqrt{\varepsilon_{\rm {B}}}\big{(}d^{2}H^{5/2}\sqrt{T}+d^{3/2}H^{3/2}T\big{)}+\varepsilon_{\rm{B}} \gamma\big{(}dH^{2}\sqrt{T}+d^{3/2}HT\big{)}\Big{)}.$ $$

Compared to Theorem 1, the regret bound includes two additional terms that depend on the inherent linear Bellman error $\varepsilon_{\rm{B}}$. For both terms, the dependence on $T$ is linear. We believe this is unavoidable, as it also appears in previous work (Zanette et al., ). In addition, it is worth noting that the regret bound does not depend on the number of actions, and the dependence on $T$ remains optimal, similar to all previous theorems.

###### Definition 3 (Inherent Linear Bellman Error) .

###### Theorem 3 (Regret Bound with Low Inherent Bellman Error) .

## 6 Proof Overview

In this section, we provide an sketch of the proof of Theorem 1 (exact oracle and zero inherent linear Bellman error). The detailed proofs are deferred to Appendix B. To better convey the intuition, we now assume that the reward function is known, as reward learning is largely standard. In particular, we temporarily remove the estimation and perturbation of rewards (10 and 12) and simply assume $\overline{\omega}_{t,h}=\omega_{h}^{\star}$ in 13.

### 6.1 Span Argument

The very first step of our analysis revolve around two complimentary cases – whether the trajectory at round $t$ is in the span of the historical data or not. Let $\mathcal{D}_{t,h}\coloneqq\left\{\phi(s_{i,h},a_{i,h})\right\}_{i=1}^{t}$ and define $\mathfrak{E}^{{\rm{span}}}_{t}$ as the event that the trajectory at round $t$ is in the span of the historical data, i.e.,

$$ $\displaystyle\mathfrak{E}^{{\rm{span}}}_{t}\coloneqq\left\{\forall h\in[H]\>: \>\phi(s_{t,h},a_{t,h})\in{\rm{span}}(\mathcal{D}_{t-1,h})\right\}.$ (3) $$

(1) In-span case. When the trajectory generated in the round $t$ is completely within the span of historical data, we can assert that the value function estimation is accurate under $\pi_{t}$. Particularly, by linear Bellman completeness, the Bayes optimal of the regression in 10 zeros the empirical risk, as formally stated in the following lemma.

###### Lemma 1 .

For any $t\in[T]$, we have
$\sum_{i=1}^{t-1}(\langle\widehat{\theta}_{t,h},\phi(s_{i,h},a_{i,h})\rangle-
\overline{V}_{t,h+1}(s_{i,h+1}))^{2}=0$.

Define $U_{t}(\cdot)$ as a version of $\overline{V}_{t}(\cdot)$ that minimizes $\overline{V}_{t}(s_{t,1})$ while satisfying the high probability bound (precise definition provided at the beginning of Section B.2).
It implies the following.

###### Lemma 2 .

For any $t\in[T]$, whenever $\mathfrak{E}^{{\rm{span}}}_{t}$ holds, we have
$\overline{V}_{t}(s_{t,1})=U_{t}(s_{t,1})=V^{\pi_{t}}(s_{t,1}).$

To understand Lemma 2, we consider two fact: (1) $\pi_{t}$ is the optimal policy for the estimated value function $\overline{V}_{t}$, and (2) both $\overline{V}_{t}$ and $U_{t}$ has accurate value estimate for the trajectory induced by $\pi_{t}$, starting from $s_{t,1}$, because it is in the span of the historical data when $\mathfrak{E}^{{\rm{span}}}_{t}$ holds.

(2) Out-of-span case. When any segment of the trajectory is not within the span, we simply pay $H$ in regret and can assert that this will not occur too many times. To see this, we observe the following fact: whenever $\mathfrak{E}^{{\rm{span}}}_{t}$ does not hold, there must exists $h\in[H]$ such that $\dim{\rm{span}}(\mathcal{D}_{t,h})=\dim{\rm{span}}(\mathcal{D}_{t-1,h})+1$ by definition. Since the dimension of spans cannot exceed $d$ for any $h\in[H]$, the case that $\mathfrak{E}^{{\rm{span}}}_{t}$ does not hold cannot happen for more than $dH$ times. We formally state it in the following lemma.

###### Lemma 3 .

We have
$\sum_{t=1}^{T}{\mathbf{1}}\{\left(\mathfrak{E}^{{\rm{span}}}_{t}\right)^{
\complement}\}\leq dH.$

Hence, we have the following decomposition:

$$ $\displaystyle V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})={\mathbf{1}}\{\mathfrak{ E}^{{\rm{span}}}_{t}\}\Big{(}V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}+ \underbrace{{\mathbf{1}}\{(\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\Big {(}V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}}_{\leq\ dH^{2}\text{ when summed over }t}$ $$

Therefore, we only need to focus on the rounds where $\mathfrak{E}^{{\rm{span}}}_{t}$ holds. This will be the aim of the subsequent sections.

###### Lemma 1 .

###### Lemma 2 .

###### Lemma 3 .

### 6.2 Exploration in the Null Space

Lemma 1 implies that the estimation error only comes from the null space of the historical data, i.e., ${\rm{null}}(\{\phi(s_{i,h},a_{i,h}):i=1,\dots,t-1\})$. Therefore, we only need to explore in this null space.
While adding explicit bonus is infeasible under linear Bellman completeness, we add noise (12) that can cancel out the estimation error in the null space. This achieves the following:

###### Lemma 4 (Optimism with constant probability) .

Denote $\mathfrak{E}^{{\rm{optm}}}_{t}$ as the event that $V^{\star}(s_{t,1})\leq\overline{V}_{t}(s_{t,1})$.
Then, for any $t\in[T]$, we have
$\operatorname{Pr}(\mathfrak{E}^{{\rm{optm}}}_{t})\geq\Gamma^{2}(-1)$
where $\Gamma$ is the cumulative distribution function of the standard normal distribution.

This result has been the key idea in randomized RL algorithms, such as RLSVI. In the next section, we will explore how this lemma is utilized.

###### Lemma 4 (Optimism with constant probability) .

### 6.3 Proof Outline

In this section, we outline the structure of the whole proof.
Let $\widetilde{V}$ denote an i.i.d. copy of $\overline{V}$, and ${\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t},{\widetilde{\mathfrak{E}}}^{{\rm{
optm}}}_{t}$ denote the counterpart of $\mathfrak{E}^{{\rm{span}}}_{t},\mathfrak{E}^{{\rm{optm}}}_{t}$ for $\widetilde{V}$. We first invoke Lemma 2 and get

$$ $\displaystyle\ {\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\Big{(}V^{\star}( s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}={\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_ {t}\}\Big{(}V^{\star}(s_{t,1})-U_{t}(s_{t,1})\Big{)}\leq V^{\star}(s_{t,1})-{ \mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})$ where the last step is by the non-negativity of $V^{\star}$ . Next, we apply Lemma 4 and get $\displaystyle\leq\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\Big{[}\min\{ \widetilde{V}_{t}(s_{t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U _{t}(s_{t,1})\,\Big{|}\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\Big{]}$ Split it into two parts: $\displaystyle=\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\Big{[}{\mathbf{1}}\{{ \widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\Big{(}\min\{\widetilde{V}_{t}(s_ {t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\Big{)} \,\Big{|}\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\Big{]}$ $\displaystyle\quad+\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\Big{[}{\mathbf{1}} \{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{\complement}\}\Big{(}\min\{ \widetilde{V}_{t}(s_{t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U _{t}(s_{t,1})\Big{)}\,\Big{|}\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t} \Big{]}$ Note that the quantity inside the first expectation is non-negative, so we can peel off the conditioning event; the quantity in the second term is simply upper bounded by $H$ . Hence, we have $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V}_{t }}\Big{[}{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\Big{(} \min\{\widetilde{V}_{t}(s_{t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_ {t}\}U_{t}(s_{t,1})\Big{)}\Big{]}+\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_ {\widetilde{V}_{t}}\Big{[}{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span }}}_{t})^{\complement}\}H\Big{]}$ Now we split the first term into two parts again: $\displaystyle=\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V}_{t}} \Big{[}{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\min\{ \widetilde{V}_{t}(s_{t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U _{t}(s_{t,1})\Big{]}$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V}_ {t}}\Big{[}{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{ \complement}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\Big{]}+\frac{1} {\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\Big{[}{\mathbf{1}}\{({ \widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{\complement}\}H\Big{]}$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V}_{t }}\Big{[}{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\min\{ \widetilde{V}_{t}(s_{t,1}),H\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U _{t}(s_{t,1})\Big{]}+\frac{2}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}_{\widetilde{V }_{t}}\Big{[}{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{ \complement}\}H\Big{]}$ where we used the fact that ${\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\leq H$ . Taking the expectation over the randomness of the algorithm and use the tower property, which converts $\widetilde{V}$ into $\overline{V}$ , we obtain $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\Big{[}{\mathbf{1} }\{\mathfrak{E}^{{\rm{span}}}_{t}\}\min\{\overline{V}_{t}(s_{t,1}),H\}-{ \mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\Big{]}+\frac{2}{ \Gamma^{2}(-1)}\mathop{\mathbb{E}}\Big{[}{\mathbf{1}}\{(\mathfrak{E}^{{\rm{ span}}}_{t})^{\complement}\}H\Big{]}$ $$

The first term is upper bounded by zero due to Lemma 2, and the second term is upper bounded by $dH^{2}$ by Lemma 3 when summed over $t$. This finishes the proof.

###### Remark 1 (Span Argument and Exponential Blow-Up) .

In the proof sketch above, we did not utilize any $\ell_{2}$-norm bound on $\overline{\theta}_{t,h}$ or $\widehat{\theta}_{t,h}$ as did in many prior works. We actually cannot leverage them since they can be exponentially large due to the addition of exponentially large noise. This phenomenon is widely observed in the literature (e.g., Agrawal et al. (); Zanette et al. ()) and is addressed through truncation. However, truncation does not work under linear Bellman completeness, as the Bellman backup of a truncated value function is not necessarily linear. This is why we use the span argument to circumvent this issue.

###### Remark 1 (Span Argument and Exponential Blow-Up) .

## 7 Opening the Black-Box: Implementing Squared Loss Minimization Oracles in Algorithm 1

The following computationally efficient implementations rely on the observation that a square loss minimization objective over a convex domain can be cast as a convex set feasibility problem—given a convex set $\mathcal{K}$, return a point $\widehat{\theta}\in\mathcal{K}$. Thus, we can use algorithms for convex set feasibility to implement the squared loss minimization oracles. However, even given this observation, our key challenge for an efficient algorithm is that the corresponding convex set could be exponentially large and only be described using exponentially many number of linear constraints. Fortunately, various works in the optimization literature propose computationally efficient procedures to find feasible points within such ill-defined sets, under mild oracle assumptions.

### 7.1 Computationally Efficient Convex Set Feasibility

In this section, we paraphrase the work of Bertsimas and Vempala () that provide a computationally efficient procedure for finding feasible points within a convex set by random walks. Notably, the computational complexity of their algorithm only depends logarithmically on the size of the convex set, and thus their approach is well suited for the corresponding convex feasibility problems that appear in our approach.
At a high level, they provide an algorithm that takes an input an arbitrary convex set $\mathcal{K}\subseteq\mathbb{R}^{d}$, and returns a feasible point $\widehat{z}\in\mathcal{K}$. Their algorithm accesses the convex set $\mathcal{K}$ via a separation oracle defined as follows:

###### Definition 4 (Separation oracle) .

A separation oracle for a convex set $\mathcal{K}$, denoted by $\mathcal{O}^{{\rm{sep}}}_{\mathcal{K}}$, is defined such that on any input $z\in\mathbb{R}^{d}$, the oracle either confirms that $z\in\mathcal{K}$ or returns a hyperplane $\left\langle a,z\right\rangle\leq b$ that separates the point $z$ from the set $\mathcal{K}$.

In order to ensure finite time convergence for their procedure, they assume that the convex set $\mathcal{K}$ is not degenerate and is bounded in any direction. This is formalized by the following assumption:

###### Assumption 5 .

The convex set $\mathcal{K}$ is $(r,R)-$Bounded, i.e. there exist parameters $0<r\leq R$ such that (a) $\mathcal{K}\subseteq\mathbb{R}_{\infty}(R)$, and (b) there exists a vector $z\in\mathbb{R}^{d}$ such that the shifted cube $(z+\mathbb{R}_{\infty}(r))\subseteq\mathcal{K}$.

The computationally efficiency, and the convergence guarantee, of the algorithm of Bertsimas and Vempala () are:

###### Theorem 4 ( Bertsimas and Vempala ( 2004 ) ) .

Let $\delta\in(0,1)$ and $\mathcal{K}\subset\mathbb{R}^{d}$ be an arbitrary convex set that satisfies Assumption 5 for some $0\leq r\leq R$.
Then, Algorithm 2 (given in the appendix), when invoked with the separation oracle $\mathcal{O}^{{\rm{sep}}}_{\mathcal{K}}$ w.r.t. $\mathcal{K}$, returns a feasible point $\widehat{z}\in\mathcal{K}$ with probability at least $1-\delta$. Moreover, Algorithm 2 makes
$O\left(d\log\left(\nicefrac{{R}}{{\delta r}}\right)\right)$ calls to the oracle $\mathcal{O}^{{\rm{sep}}}_{\mathcal{K}}$ and runs in time $O\left(d^{7}\log\left(\nicefrac{{R}}{{\delta r}}\right)\right)$.

Notice that both the number of oracle calls and the computation time only depend logarithmically on $R$ and $r$, and thus their procedure can be efficiently implemented for our applications where $\nicefrac{{R}}{{r}}$ may be exponentially large in the corresponding problem parameters.

###### Definition 4 (Separation oracle) .

###### Assumption 5 .

###### Theorem 4 ( Bertsimas and Vempala ( 2004 ) ) .

### 7.2 Computationally Efficient Estimation of Value Function (Eqn ( 1 ) )

We now described how to use the convex set procedure of Bertsimas and Vempala () for convex set feasibility to estimate the parameters for the value functions in (1) in Algorithm 1. Note that for any time $t$ and horizon $h\in[H]$, the objective in (1) is the optimization problem

$$ $\displaystyle\widehat{\theta}_{t,h}$ $\displaystyle\leftarrow\operatorname*{argmin}_{\theta\in\mathscr{O}(W_{h})} \sum_{i=1}^{t-1}\Big{(}\left\langle\theta,\phi(s_{i,h},a_{i,h})\right\rangle- \overline{V}_{t,h+1}(s_{i,h+1})\Big{)}^{2},$ (4) $$

where $W_{h}=\widetilde{\Theta}((d\sqrt{mH})^{H-h}(\varepsilon_{1}d\gamma\sqrt{H}+d^{
3/2}+d\sqrt{mH}))$. We provide a computationally efficient procedure to approximately solve the above given a linear optimization oracle over the feature space.

###### Assumption 6 (Linear optimization oracle over the feature space) .

Learner has access to a linear optimization oracle $\mathcal{O}^{{\rm{lin}}}$ that on taking input $\theta\in\mathbb{R}^{d}$, returns a feature $\phi(s^{\prime},a^{\prime})\in\operatorname*{argmax}_{s,a}\langle\theta,\phi(s
,a)\rangle$.

The key observation that we use is that under linear Bellman completeness (Definition 1), and deterministic dynamics (5), any solution $\theta$ for (4) must satisfy $\sum_{i=1}^{t-1}(\left\langle\theta,\phi(s_{i,h},a_{i,h})\right\rangle-
\overline{V}_{t,h+1}(s_{i,h+1}))^{2}=0$. On the other hand, the converse also holds that any point $\theta\in\mathscr{O}(W_{h})$ for which the objective value is 0 0 must be a solution to (4). Thus, the minimization problem in (4) is equivalent to finding a feasible point within the convex set

$$ $\displaystyle\mathcal{K}\vcentcolon={}\left\{\theta\in\mathbb{R}^{d} \leavevmode\nobreak\ \Bigg{\mid}{}\begin{matrix}&\left(\left\langle\theta,\phi (s_{i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\right)^{2}=0 \leavevmode\nobreak\ \text{for all}\leavevmode\nobreak\ i\leq t\\ &\lvert\left\langle\theta,\phi(s,a)\right\rangle\rvert\leq W_{h}\leavevmode \nobreak\ \text{for all}\leavevmode\nobreak\ s,a\end{matrix}\right\}$ (5) $$

Given the above reformulation of the optimization objective (4) as a feasibility problem, we can now use the procedure of Bertsimas and Vempala () for finding $\theta_{t,h}\in\mathcal{K}$. However, we first need to define a separation oracle for the set $\mathcal{K}$ and verify Assumption 5.
Unfortunately, there may not exist any $r>0$ for which $(z+\mathbb{R}_{\infty}(r))\subseteq\mathcal{K}$ for some $z\in\mathbb{R}^{d}$ and thus the above $\mathcal{K}$ may not satisfy Assumption 5. This can, however, be easily fixed by artificially increasing the set $\mathcal{K}$ to allow for some approximation errors. In particular, let $\varepsilon>0$ and define the convex set

$$ $\displaystyle\mathcal{K}_{\textsc{apx}}\vcentcolon={}\left\{\theta\in\mathbb{R }^{d}\leavevmode\nobreak\ \Bigg{\mid}{}\begin{matrix}&\left\langle\theta,\phi( s_{i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\leq\varepsilon \leavevmode\nobreak\ \text{for all}\leavevmode\nobreak\ i\leq t\leavevmode \nobreak\ \leavevmode\nobreak\ \\ &\left\langle\theta,\phi(s_{i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_ {i,h+1})\geq-\varepsilon\leavevmode\nobreak\ \text{for all}\leavevmode\nobreak \ i\leq t\\ &\lvert\left\langle\theta,\phi(s,a)\right\rangle\rvert\leq W_{h}+\varepsilon \leavevmode\nobreak\ \text{for all}\leavevmode\nobreak\ s,a\end{matrix}\right\}.$ (6) $$

Clearly, since there exists at least one point $\theta_{t,h}\in\mathcal{K}$, we must have that $(\theta_{t,h}+\mathbb{R}_{\infty}(\varepsilon))\subseteq\mathcal{K}_{\textsc{
apx}}$. To ensure an outer bounding box for the set $\mathcal{K}_{\textsc{apx}}$, we need to make an additional assumption:

###### Assumption 7 .

Let $\Phi=\{\phi(s,a)\mid s,a\in\mathcal{S}\times\mathcal{A}\}$. There exist some $R\geq 0$ such that $\frac{1}{R}e_{i}\in\Phi$, where $e_{i}$ denotes the unit basis vector along the $i$-th direction in $\mathbb{R}^{d}$.

The above assumption ensures that $\mathcal{K}\subseteq\mathbb{B}_{\infty}(W_{h}R)$. Note that we can tolerate the parameter $R$ to be exponential in the dimension $d$ or the horizon $H$. Finally, a separation oracle can be implemented using $\mathcal{O}^{{\rm{lin}}}$ (see Algorithm 4 for details). Thus, one can use Algorithm 2 (given in appendix), due to Bertsimas and Vempala (), and the guarantee in Theorem 4 to find a feasible point in $\mathcal{K}_{\textsc{apx}}$, which corresponds to an approximate solution to (4)

###### Theorem 5 .

Let $\varepsilon>0$, $\delta\in(0,1)$, and suppose Assumption 7 holds with some parameter $R>0$. Additionally, suppose Assumption 6 holds with the linear optimization oracle denoted by $\mathcal{O}^{{\rm{lin}}}$. Then, there exists a computationally efficient procedure (given in Algorithm 4 in the appendix), that for any $t\in[T]$ and $h\in[H]$, returns a point $\widehat{\theta}_{t,h}$ that, with probability at least $1-\delta$, satisfies

$$ $\displaystyle\sum_{i=1}^{t-1}\Big{(}\left\langle\widehat{\theta}_{t,h},\phi(s_ {i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\Big{)}^{2}\leq T \varepsilon\qquad\text{and}\qquad\widehat{\theta}_{t,h}\in\mathscr{O}(W_{h}+ \varepsilon).$ $$

Furthermore, Algorithm 4 takes $O(d^{7}\log(\frac{R}{\delta\varepsilon}))$ time in addition to $O(d\log(\frac{THR}{\delta\varepsilon}))$ calls to $\mathcal{O}^{{\rm{lin}}}$.

The above techniques and Algorithm 4 can be easily extended to get a computationally efficient procedure to estimate the reward parameter in (2). The main difference, however, is that the value of the optimization objective in (2) is not zero at the minimizer (due to stochasticity). Thus, we need to construct a set feasibility problem for every desired target value of the objective function within the grid $[0,\varepsilon,2\varepsilon,\dots,2-\varepsilon,2]$, and use a separating hyperplane w.r.t.  the ellipsoid constraint in (2) to implement the separating hyperplane for $\mathcal{K}_{\textsc{apx}}$ (which can be easily implemented using projections).

###### Assumption 6 (Linear optimization oracle over the feature space) .

###### Assumption 7 .

###### Theorem 5 .

## 8 Conclusion

In this paper, we develop a computationally efficient RL algorithm under linear Bellman completeness with deterministic dynamics, aiming to bridge the statistical-computational gap in this setting.
Our algorithm injects random noise into regression estimates only in the null space to ensure optimism and leverages a span argument to bound regret. It handles large action spaces, random initial states, and stochastic rewards. Our key observation is that deterministic dynamics simplifies the learning process by ensuring accurate value estimates within the data span, allowing noise injection to be confined to the null space. Extending our algorithm to stochastic dynamics remains an open challenge.

#### Acknowledgements

We thank Zeyu Jia, Noah Golowich, and Sasha Rakhlin for useful discussions. AS acknowledges support from the Simons Foundation and
NSF through award DMS-2031883, as well as from the DOE through award DE-SC0022199.

## Appendix A Table of Notation

We list the notation used in this paper in table 1, for the convenience of reference.

**Table 1: Notation used in the paper.**
| Symbol | Description |
| --- | --- |
| $\mathscr{O}(W)$ | $\{\theta\in\mathbb{R}^{d}:|\langle\theta,\phi(s,a)\rangle|\leq W\text{ for all<br>}s\in\mathcal{S},a\in\mathcal{A}\}$ |
| $\mathbb{B}_{\infty}(W)$ | $\{\theta\in\mathbb{R}^{d}:\|\theta\|_{\infty}\leq W\}$ |
| $\mathbb{B}_{2}(W)$ | $\{\theta\in\mathbb{R}^{d}:\|\theta\|_{2}\leq W\}$ |
| $\eta_{t,h}$ | $\mathcal{T}(\overline{\omega}_{t,h+1}+\overline{\theta}_{t,h+1})-\widehat{<br>\theta}_{t,h}$ |
| $\eta^{{\rm{R}}}_{t,h}$ | $\omega^{\star}_{h}-\widehat{\omega}_{t,h}$ |
| $\xi^{{\rm{R}}}_{t}$ | $\overline{\omega}_{t,h}-\widehat{\omega}_{t,h}$ |
| $\xi^{{\rm{P}}}_{t,h}$ | $\overline{\theta}_{t,h}-\widehat{\theta}_{t,h}$ |
| $\mathfrak{E}^{{\rm{high}}}$ | High probability event, defined in Definition 5 |
| $\mathfrak{E}^{{\rm{span}}}_{t}$ | Event that trajectory at round $t$ is within the span of historical data, defined in (3) |
| $\mathfrak{E}^{{\rm{optm}}}_{t}$ | Optimism event at round $t$, defined in Lemma 14 |
| $U_{t,h}$ | Value function lower bound, defined in Section B.2 |
| $B^{{\rm{R}}}_{{\rm{err}}}$ | Upper bound of $\|\widehat{\omega}_{t,h}-\omega^{\star}_{h}\|_{\Sigma_{t}}$, defined in Definition 5 |
| $B^{{\rm{P}}}_{{\rm{err}}}$ | Upper bound of $\|\widehat{\theta}_{t,h}-\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}<br>_{t,h+1})\|_{\widehat{\Sigma}_{t,h}}$, defined in Lemma 7 |
| $B^{{\rm{R}}}_{{\rm{noise}}}$ | Upper bound of $\|\xi^{{\rm{R}}}_{t,h}\|_{\Sigma_{t,h}}$, defined in Definition 5 |
| $B^{{\rm{P}}}_{{\rm{noise}},h}$ | Upper bound of $\|\xi^{{\rm{P}}}_{t,h}\|_{\Lambda_{t,h}}$, defined in Definition 5 |
| $B_{\phi}^{{\rm{R}}}$ | Upper bound of $\sum_{t=1}^{T}\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}$ defined in Lemma 16 |
| $B_{\phi}^{{\rm{P}}}$ | Upper bound of $\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\|\phi(s_{t,h},a_{<br>t,h})\|_{\widehat{\Sigma}^{\dagger}_{t,h}}$, defined in Lemma 16 |
| $B_{V}$ | Upper bound of $|\overline{V}_{t}|$ conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$ and $\mathfrak{E}^{{\rm{high}}}$, defined in Lemma 13 |
| $\Sigma_{t,h}$ | $\sum_{i=1}^{m}\rho_{i}\phi_{i}\phi_{i}^{\top}+\sum_{i=1}^{t-1}\phi(s_{i,h},a_{<br>i,h})\phi^{\top}(s_{i,h},a_{i,h})$ |
| $\widehat{\Sigma}_{t,h}$ | $\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\phi^{\top}(s_{i,h},a_{i,h})$ |
| $W_{h}$ | Recursively defined as $W_{h-1}=W_{h}+2\varepsilon_{2}+\sqrt{2d}\cdot B^{{\rm{P}}}_{{\rm{noise}},h}+<br>\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}+1$ |
|  | with $W_{H+1}=1$ |

## Appendix B Full Proof for Section 5

In this section, we present and prove the following main theorem, which provides the regret bound in terms of parameters $\varepsilon_{1}$, $\varepsilon_{2}$, and $\varepsilon_{\rm{B}}$. Setting $\varepsilon_{1}=\varepsilon_{2}=\varepsilon_{\rm{B}}=0$ yields Theorem 1, setting $\varepsilon_{\rm{B}}=0$ yields Theorem 2, and setting $\varepsilon_{1}=\varepsilon_{2}=0$ yields Theorem 3.

###### Theorem 6 .

Assume the MDP has $\varepsilon_{\rm{B}}$-inherent linear Bellman error.
Under Assumptions 1, 3 and 4,
when executing Algorithm 1 with parameters $\sigma_{{\rm{R}}}=\sqrt{H}B^{{\rm{R}}}_{{\rm{err}}}$ and $\sigma_{h}\geq\sqrt{H}(\sqrt{3}\gamma B^{{\rm{P}}}_{{\rm{err}}}+\sqrt{8m}(W_{h
}+\varepsilon_{2}))$, we have

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\Big{(}V^{\star}(s_{t,1})- V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle=\widetilde{O}\bigg{(}d^{5/2}H^{5/2}+d^{2}H^{3/2}\sqrt{T}+ \varepsilon_{1}\gamma\Big{(}dH^{2}+d^{3/2}H\sqrt{T}\Big{)}$ $\displaystyle\quad+\sqrt{\varepsilon_{\rm{B}}}\Big{(}d^{2}H^{5/2}\sqrt{T}+d^{3 /2}H^{3/2}T\Big{)}+\varepsilon_{\rm{B}}\gamma\Big{(}dH^{2}\sqrt{T}+d^{3/2}HT \Big{)}\bigg{)}.$ $$

Exact value of parameters $\sigma_{{\rm{R}}}$ and $\sigma_{h}$ in Theorem 6.
We define $W_{H+1}=1$ and recursively define $W_{h-1}=W_{h}+2\varepsilon_{2}+\sqrt{2d}\cdot B^{{\rm{P}}}_{{\rm{noise}},h}+
\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}+1$. Plugging the definition of all these symbols involved and ignoring lower order terms (i.e., logarithmic and constant terms), we get

$$ $\displaystyle W_{h-1}\approx d\sqrt{mH}\cdot W_{h}+\varepsilon_{1}\cdot d \gamma\sqrt{H}+\varepsilon_{\rm{B}}\cdot d\gamma\sqrt{HT}+\sqrt{\varepsilon_{ \rm{B}}}\cdot d\sqrt{T}+d^{3/2}.$ (7) $$

Solving this recursion, we get

$$ $\displaystyle W_{h}$ $\displaystyle\approx\big{(}d\sqrt{mH}\big{)}^{H+1-h}+\big{(}d\sqrt{mH}\big{)}^ {H-h}\big{(}\varepsilon_{1}\cdot d\gamma\sqrt{H}+\varepsilon_{\rm{B}}\cdot d \gamma\sqrt{HT}+\sqrt{\varepsilon_{\rm{B}}}\cdot d\sqrt{T}+d^{3/2}\big{)}$ $\displaystyle\approx\big{(}d\sqrt{mH}\big{)}^{H-h}\big{(}\varepsilon_{1}\cdot d \gamma\sqrt{H}+\varepsilon_{\rm{B}}\cdot d\gamma\sqrt{HT}+\sqrt{\varepsilon_{ \rm{B}}}\cdot d\sqrt{T}+d^{3/2}+d\sqrt{mH}\big{)}.$ $$

We insert this into the value of $\sigma_{h}$ and get

$$ $\displaystyle\sigma_{h}\approx\big{(}d\sqrt{mH}\big{)}^{H-h+1}\big{(} \varepsilon_{1}\cdot\gamma\sqrt{H}+\varepsilon_{\rm{B}}\cdot\gamma\sqrt{HT}+ \sqrt{\varepsilon_{\rm{B}}}\cdot\sqrt{T}+d^{1/2}+\sqrt{mH}\big{)}.$ $$

We can also get the value of $\sigma_{{\rm{R}}}$ as

$$ $\displaystyle\sigma_{{\rm{R}}}\approx\sqrt{H}\Big{(}\sqrt{d\log(HT)}+ \varepsilon_{1}+\sqrt{\varepsilon_{\rm{B}}T}\Big{)}.$ $$

Define $\Lambda=\sum_{i=1}^{m}\rho_{i}\phi_{i}\phi_{i}^{\top}$. It is straightforward that both $\Lambda$ and $\Lambda_{t,h}$ (constructed in 8 of Algorithm 1) are invertible. We define $\lambda\coloneqq\max_{s,a}\|\phi(s,a)\|_{\Lambda^{-1}}$ and $\lambda_{t,h}\coloneqq\max_{s,a}\|\phi(s,a)\|_{\Lambda^{-1}_{t,h}}$.

###### Lemma 5 .

The matrices $\Lambda$ and $\Lambda_{t,h}$ are invertible. Furthermore, we also have that

- •
$\lambda\leq\sqrt{d}$;
- •
$\lambda_{t,h}\leq\sqrt{2d}$ for all $t\in[T]$ and all $h\in[H]$.

###### Proof of Lemma 5 .

By the last item in Lemma 23, we have $\lambda\leq\sqrt{d}$. In what follows, we will show that $\Lambda\preceq 2\Lambda_{t,h}$, which implies $\lambda_{t,h}\leq\sqrt{2}\lambda\leq\sqrt{2d}$.

For any $x\in\mathbb{R}^{d}$, we have

$$ $\displaystyle x^{\top}\Lambda x$ $\displaystyle=\sum_{i=1}^{m}\rho_{i}(x^{\top}\phi_{i})^{2}=\sum_{i=1}^{m}\rho_ {i}\left(x^{\top}\phi^{\parallel}_{t,h,i}+x^{\top}\phi^{\perp}_{t,h,i}\right)^ {2}$ $\displaystyle\leq 2\sum_{i=1}^{m}\rho_{i}\left(x^{\top}\phi^{\parallel}_{t,h,i }\right)^{2}+2\sum_{i=1}^{m}\rho_{i}\left(x^{\top}\phi^{\perp}_{t,h,i}\right)^ {2}$ (using $(a+b)^{2}\leq 2a^{2}+2b^{2}$ ) $\displaystyle=2x^{\top}\Lambda_{t,h}x.$ $$

This implies that $\Lambda\preceq 2\Lambda_{t,h}$.
∎

###### Theorem 6 .

###### Lemma 5 .

###### Proof of Lemma 5 .

### B.1 High-probability Event and Boundedness

###### Lemma 6 (Reward estimation) .

With probability at least $1-\delta$, for any $t\in[T]$ and $h\in[H]$,

$$ $\displaystyle\left\|\widehat{\omega}_{t,h}-\omega^{\star}_{h}\right\|_{\Sigma_ {t}}\leq\sqrt{1030(1+\varepsilon_{2})^{4}d\log\big{(}8(1+\varepsilon_{2})e^{2} T^{2}H/\delta\big{)}+4\varepsilon_{1}^{2}+16(1+\varepsilon_{2})(1+\varepsilon_ {\rm{B}}T)}.$ $$

###### Proof of Lemma 6 .

For the ease of notation, we fixed $t$ and $h$ in the proof and simply write the regression problem as

$$ $\displaystyle\widehat{\omega}\leftarrow\operatorname*{argmin}_{\omega\in \mathscr{O}(1)}\sum_{i=1}^{n}\left(\omega^{\top}\phi_{i}-r_{i}\right)^{2}$ $$

where we have dropped the subscripts $t$ and $h$ for notational simplicity. Here $\phi_{i}$ and $r_{i}$ are abbreviated notations for $\phi(s_{i,h},a_{i,h})$ and $r_{i,h}$, respectively, and $n=t-1$.

Note that, due to approximate oracle (Assumption 3), $\widehat{\omega}$ actually belongs to $\mathscr{O}(1+\varepsilon_{2})$ instead of $\mathscr{O}(1)$. Denote $\mathcal{C}$ as an $\ell_{1}$-norm $\alpha$-cover (Definition 6) on $\mathscr{O}(1+\varepsilon_{2})$ such that for any $\omega\in\mathscr{O}(1+\varepsilon_{2})$, there exists a $\widetilde{\omega}\in\mathcal{C}$, such that $\sum_{i=1}^{n}|\omega^{\top}\phi_{i}-\widetilde{\omega}^{\top}\phi_{i}|/n\leq\alpha$. Since $\mathscr{O}(1+\varepsilon_{2})$ is a linear function class, which has pseudo-dimension $d$ (Definition 8), we have

$$ $|\mathcal{C}|\leq\big{(}8(1+\varepsilon_{2})e^{2}/\alpha\big{)}^{d}$ (8) $$

by Lemma 27. Now define $z^{\omega}_{i}=(\omega^{\top}\phi_{i}-r_{i})^{2}-((\omega^{\star})^{\top}\phi_
{i}-r_{i})^{2}$. Then we have $|z^{\omega}_{i}|\leq 4(1+\varepsilon_{2})^{2}$, and

$$ $\displaystyle\mathop{\mathbb{E}}_{i}[z^{\omega}_{i}]$ $\displaystyle=\mathop{\mathbb{E}}_{i}\left[(\omega^{\top}\phi_{i}-(\omega^{ \star})^{\top}\phi_{i})(\omega^{\top}\phi_{i}+(\omega^{\star})^{\top}\phi_{i}- 2r_{i})\right]$ $\displaystyle=\mathop{\mathbb{E}}_{i}\left[(\omega^{\top}\phi_{i}-(\omega^{ \star})^{\top}\phi_{i})\left(\omega^{\top}\phi_{i}-(\omega^{\star})^{\top}\phi _{i}+2\left((\omega^{\star})^{\top}\phi_{i}-r_{i}\right)\right)\right]$ $\displaystyle\geq(\omega^{\top}\phi_{i}-(\omega^{\star})^{\top}\phi_{i})^{2}-4 (1+\varepsilon_{2})\varepsilon_{\rm{B}},$ and moreover, $\displaystyle\mathop{\mathbb{E}}_{i}[(z^{\omega}_{i})^{2}]$ $\displaystyle=\mathop{\mathbb{E}}_{i}\left[(\omega^{\top}\phi_{i}-(\omega^{ \star})^{\top}\phi_{i})^{2}(\omega^{\top}\phi_{i}+(\omega^{\star})^{\top}\phi_ {i}-2r_{i})^{2}\right]\leq 16(1+\varepsilon_{2})^{2}(\omega^{\top}\phi_{i}-( \omega^{\star})^{\top}\phi_{i})^{2}$ $$

We note that $z_{i}^{\omega}-\mathop{\mathbb{E}}_{i}z^{\omega}_{i}$ is a martingale difference sequence and $|z_{i}^{\omega}-\mathop{\mathbb{E}}_{i}z^{\omega}_{i}|\leq 8(1+\varepsilon_{2}
)^{2}$. Applying Freedman’s inequality (Lemma 22) and a union bound over $\omega\in\mathcal{C}$, we have with probability at least $1-\delta$, for all $\omega\in\mathcal{C}$,

$$ $\displaystyle\sum_{i=1}^{n}(\omega^{\top}\phi_{i}-(\omega^{\star})^{\top}\phi_ {i})^{2}-\sum_{i=1}^{n}z_{i}^{\omega}$ $\displaystyle\leq\eta\sum_{i=1}^{n}16(1+\varepsilon_{2})^{2}(\omega^{\top}\phi _{i}-(\omega^{\star})^{\top}\phi_{i})^{2}+\frac{8(1+\varepsilon_{2})^{2}\log(| \mathcal{C}|/\delta)}{\eta}+4(1+\varepsilon_{2})\varepsilon_{\rm{B}}T.$ (9) $$

Recall that $\widehat{\omega}$ is the least square solution. Denote $\widetilde{\omega}\in\mathcal{C}$ as the point that is closest to $\widehat{\omega}$, which means that: $\sum_{i=1}^{n}|\widehat{\omega}^{\top}\phi_{i}-\widetilde{\omega}^{\top}\phi_{
i}|\leq n\alpha$. We can derive the following relationship between $\widehat{\omega}$ and $\widetilde{\omega}$:

$$ $\displaystyle\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star})^{ \top}\phi_{i})^{2}\leq 2\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}- \widetilde{\omega}^{\top}\phi_{i})^{2}+2\sum_{i=1}^{n}(\widetilde{\omega}^{ \top}\phi_{i}-(\omega^{\star})^{\top}\phi_{i})^{2}\leq 2n^{2}\alpha^{2}+2\sum_ {i=1}^{n}(\widetilde{\omega}^{\top}\phi_{i}-(\omega^{\star})^{\top}\phi_{i})^{ 2},$ $\displaystyle\sum_{i=1}^{n}z_{i}^{\widetilde{\omega}}-\sum_{i=1}^{n}z_{i}^{ \widehat{\omega}}=\sum_{i=1}^{n}(\widetilde{\omega}^{\top}\phi_{i}-\widehat{ \omega}^{\top}\phi_{i})(\widetilde{\omega}^{\top}\phi_{i}+\widehat{\omega}^{ \top}\phi_{i}-2r_{i})\leq 4(1+\varepsilon_{2})n\alpha.$ $$

Now plug $\widetilde{\omega}$ into (9) and re-arrange terms, we get:

$$ $\displaystyle\sum_{i=1}^{n}(\widetilde{\omega}^{\top}\phi_{i}-(\omega^{\star}) ^{\top}\phi_{i})^{2}\leq\frac{1}{1-16(1+\varepsilon_{2})^{2}\eta}\sum_{i=1}^{n }z_{i}^{\widetilde{\omega}}+\frac{8(1+\varepsilon_{2})^{2}}{\eta(1-16(1+ \varepsilon_{2})^{2}\eta)}\cdot\log(|\mathcal{C}|/\delta)+\frac{4(1+ \varepsilon_{2})\varepsilon_{\rm{B}}T}{1-16(1+\varepsilon_{2})^{2}\eta}.$ $$

Setting $\eta=(32(1+\varepsilon_{2})^{2})^{-1}$, we get

$$ $\displaystyle\sum_{i=1}^{n}(\widetilde{\omega}^{\top}\phi_{i}-(\omega^{\star}) ^{\top}\phi_{i})^{2}\leq 2\sum_{i=1}^{n}z_{i}^{\widetilde{\omega}}+512(1+ \varepsilon_{2})^{4}\log(|\mathcal{C}|/\delta)+8(1+\varepsilon_{2})\varepsilon _{\rm{B}}T.$ $$

Using the relationships between $\widehat{\omega}$ and $\widetilde{\omega}$ that we derived above, we have:

$$ $\displaystyle\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star})^{ \top}\phi_{i})^{2}$ $\displaystyle\leq 2n^{2}\alpha^{2}+4\sum_{i=1}^{n}z_{i}^{\widetilde{\omega}}+1 024(1+\varepsilon_{2})^{4}\log(|\mathcal{C}|/\delta)+16(1+\varepsilon_{2}) \varepsilon_{\rm{B}}T.$ $\displaystyle\leq 2n^{2}\alpha^{2}+4\sum_{i=1}^{n}z_{i}^{\widehat{\omega}}+102 4(1+\varepsilon_{2})^{4}\log(|\mathcal{C}|/\delta)+16(1+\varepsilon_{2})n \alpha+16(1+\varepsilon_{2})\varepsilon_{\rm{B}}T.$ $$

Since $\widehat{\omega}$ is the (approximate) least square solution, we have $\sum_{i}z_{i}^{\widehat{\omega}}\leq\varepsilon_{1}^{2}$. This implies that:

$$ $\displaystyle\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star})^{ \top}\phi_{i})^{2}\leq 2n^{2}\alpha^{2}+4\varepsilon_{1}^{2}+1024(1+ \varepsilon_{2})^{4}\log(|\mathcal{C}|/\delta)+16(1+\varepsilon_{2})(n\alpha+ \varepsilon_{\rm{B}}T).$ $$

Now plugging the covering number (8) and setting $\alpha=1/n$, we obtain

$$ $\displaystyle\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star})^{ \top}\phi_{i})^{2}$ $\displaystyle\leq 2+4\varepsilon_{1}^{2}+1024(1+\varepsilon_{2})^{4}d\log(8(1+ \varepsilon_{2})e^{2}n/\delta)+16(1+\varepsilon_{2})(1+\varepsilon_{\rm{B}}T)$ $\displaystyle\leq 1026(1+\varepsilon_{2})^{4}d\log(8(1+\varepsilon_{2})e^{2}n/ \delta)+4\varepsilon_{1}^{2}+16(1+\varepsilon_{2})(1+\varepsilon_{\rm{B}}T).$ $$

Finally, we have

$$ $\displaystyle\left\|\widehat{\omega}-\omega^{\star}_{h}\right\|^{2}_{\Sigma_{t }}=\sum_{i=1}^{n}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star})^{\top}\phi_ {i})^{2}+\sum_{i=1}^{m}\rho_{i}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{\star })^{\top}\phi_{i})^{2}.$ $$

Here, with some abuse of notation, the $\phi_{i}$’s in the right term are the support points of the optimal design. The first term is already bounded above. The second term can be bounded by

$$ $\displaystyle\sum_{i=1}^{m}\rho_{i}(\widehat{\omega}^{\top}\phi_{i}-(\omega^{ \star})^{\top}\phi_{i})^{2}\leq\sum_{i=1}^{m}\rho_{i}\cdot 4(1+\varepsilon_{2} )=4(1+\varepsilon_{2}).$ $$

We add it into the constant of the first term. Then, we apply the union bound over all $t\in[T]$ and $h\in[H]$ to get the desired result.
∎

###### Lemma 7 (Value function estimation) .

Suppose that $\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})\in\mathscr{O}(W
_{h})$. Then,

$$ $\displaystyle\sum_{i=1}^{t-1}\left(\left\langle\widehat{\theta}_{t,h},\phi(s_{ i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\right)^{2}\leq \varepsilon_{1}^{2}+T\varepsilon_{\rm{B}}^{2}.$ $$

Furthermore,
$\|\widehat{\theta}_{t,h}-\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}
_{t,h+1})\|_{\widehat{\Sigma}_{t,h}}\leq\sqrt{2\varepsilon_{1}^{2}+4T
\varepsilon_{\rm{B}}^{2}}=:B^{{\rm{P}}}_{{\rm{err}}}.$

###### Proof of Lemma 7 .

The Bayes optimal $\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})$ should achieve the empirical risk of at most $\varepsilon_{\rm{B}}$, i.e.,

$$ $\displaystyle\forall i\in[t-1]:\quad\Big{|}\left\langle\phi(s_{i,h},a_{i,h}), \mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})\right\rangle- \overline{V}_{t,h+1}(s_{i,h+1})\Big{|}\leq\varepsilon_{\rm{B}}.$ $$

Since $\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})$ is realizable (i.e., $\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})\in\mathscr{O}(W
_{h})$), and $\widehat{\theta}_{t,h}$ minimizes the objective up to precision $\varepsilon_{1}$, it should satisfy the following

$$ $\displaystyle\sum_{i=1}^{t-1}\Big{(}\left\langle\widehat{\theta}_{t,h},\phi(s_ {i,h},a_{i,h})\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\Big{)}^{2}\leq \varepsilon_{1}^{2}+T\varepsilon_{\rm{B}}^{2}.$ $$

Combining the above two results, we arrive at the following:

$$ $\displaystyle\sum_{i=1}^{t-1}\left\langle\phi(s_{i,h},a_{i,h}),\,\widehat{ \theta}_{t,h}-\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1}) \right\rangle^{2}$ $\displaystyle\leq 2\sum_{i=1}^{t-1}\Big{(}\left\langle\phi(s_{i,h},a_{i,h}),\, \widehat{\theta}_{t,h}\right\rangle-\overline{V}_{t,h+1}(s_{i,h+1})\Big{)}^{2} +2\sum_{i=1}^{t-1}\Big{(}\overline{V}_{t,h+1}(s_{i,h+1})-\left\langle\phi(s_{i ,h},a_{i,h}),\,\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1}) \right\rangle\Big{)}^{2}$ (using $(a+b)^{2}\leq 2a^{2}+2b^{2}$ ) $\displaystyle\leq 2\varepsilon_{1}^{2}+4T\varepsilon_{\rm{B}}^{2}.$ $$

This implies that

$$ $\displaystyle\left\|\widehat{\theta}_{t,h}-\mathcal{T}(\overline{\omega}_{t,h} +\overline{\theta}_{t,h+1})\right\|^{2}_{\widehat{\Sigma}_{t,h}}\leq 2 \varepsilon_{1}^{2}+4T\varepsilon_{\rm{B}}^{2}.$ $$

∎

###### Definition 5 (High-probability events) .

Define event $\mathfrak{E}^{{\rm{high}}}$ as

$$ $\displaystyle\mathfrak{E}^{{\rm{high}}}\coloneqq$ $\displaystyle\left\{\forall t\in[T],\forall h\in[H]:\|\xi^{{\rm{P}}}_{t,h}\|_{ \Lambda_{t,h}}\leq\sigma_{h}\sqrt{2d\log(6dH^{2}T^{2})}=:B^{{\rm{P}}}_{{\rm{ noise}},h}\right\}$ $\displaystyle\ \cap\left\{\forall t\in[T],\forall h\in[H]:\|\xi^{{\rm{R}}}_{t, h}\|_{\Sigma_{t,h}}\leq\sigma_{{\rm{R}}}\sqrt{2d\log(6dHT^{2})}=:B^{{\rm{R}}}_ {{\rm{noise}}}\right\}$ $\displaystyle\ \cap\left\{\forall t\in[T],\forall h\in[H]:\left\|\eta^{{\rm{R} }}_{t,h}\right\|_{\Sigma_{t,h}}\leq B^{{\rm{R}}}_{{\rm{err}}}\right\}$ $$

where $B^{{\rm{R}}}_{{\rm{err}}}\coloneqq\sqrt{1030(1+\varepsilon_{2})^{4}d\log\big{(
}24(1+\varepsilon_{2})e^{2}T^{3}H^{2}\big{)}+4\varepsilon_{1}^{2}+16(1+
\varepsilon_{2})(1+\varepsilon_{\rm{B}}T)}$.

###### Lemma 8 .

We have $\operatorname{Pr}(\mathfrak{E}^{{\rm{high}}})>1-1/(HT)$.

###### Proof of Lemma 8 .

Below we show that each event defined in Definition 5 holds with probability at least $1-1/(3HT)$. Then, by union bound, we have the desired result.

Proof of the first event.
The way we generate $\xi^{{\rm{P}}}_{t,h}$ is equivalent to first sampling $\zeta_{t,h}\sim\mathcal{N}(0,(\sigma_{h})^{2}\Lambda_{t,h}^{-1})$ and then set $\xi^{{\rm{P}}}_{t,h}\leftarrow(I-P_{t,h})\zeta_{t,h}$. By Lemma 20 and the union bound, we have

$$ $\displaystyle\operatorname{Pr}\left(\forall t\in[T],\forall h\in[H]:\|\zeta_{t ,h}\|_{\Lambda_{t,h}}>\sigma_{h}\sqrt{2d\log(6dH^{2}T^{2})}\right)\leq 1/(3HT).$ $$

Then, by definition, we have

$$ $\displaystyle\|\xi^{{\rm{P}}}_{t,h}\|_{\Lambda_{t,h}}^{2}$ $\displaystyle=\|(1-P_{t,h})\zeta_{t,h}\|_{\Lambda_{t,h}}^{2}$ $\displaystyle=\zeta_{t,h}^{\top}(I-P_{t,h})\sum_{i=1}^{m}\Big{(}\phi^{ \parallel}_{t,h,i}(\phi^{\parallel}_{t,h,i})^{\top}+\phi^{\perp}_{t,h,i}(\phi^ {\perp}_{t,h,i})^{\top}\Big{)}(I-P_{t,h})\zeta_{t,h}$ $\displaystyle=\zeta_{t,h}^{\top}\sum_{i=1}^{m}\phi^{\perp}_{t,h,i}(\phi^{\perp }_{t,h,i})^{\top}\zeta_{t,h}$ $\displaystyle\leq\zeta_{t,h}^{\top}\sum_{i=1}^{m}\Big{(}\phi^{\parallel}_{t,h, i}(\phi^{\parallel}_{t,h,i})^{\top}+\phi^{\perp}_{t,h,i}(\phi^{\perp}_{t,h,i}) ^{\top}\Big{)}\zeta_{t,h}$ $$

where the third step holds by the fact that $\phi^{\perp}$ is in the null space and $\phi^{\parallel}$ is in the span. Hence, we conclude that
$\|\xi^{{\rm{P}}}_{t,h}\|_{\Lambda_{t,h}}\leq\|\zeta_{t,h}\|_{\Lambda_{t,h}}.$

Proof of the second event.
Applying Lemma 20 and the union bound, we have

$$ $\displaystyle\operatorname{Pr}\left(\forall t\in[T]:\|\xi^{{\rm{R}}}_{t}\|_{ \Sigma_{t}}>\sigma_{{\rm{R}}}\sqrt{2d\log(6dHT^{2})}\right)\leq 1/(3HT).$ $$

Proof of the third event.
This is directly from Lemma 6.
∎

###### Lemma 9 (Boundness of parameters) .

Under Assumption 4, conditioning on $\mathfrak{E}^{{\rm{high}}}{}$, the following hold for all $t\in[T]$ and $h\in[H]$:

- 1.
$\max_{s,a}|\langle\phi(s,a),\widehat{\theta}_{t,h}\rangle|\leq W_{h}+
\varepsilon_{2}$;
- 2.
$\max_{s,a}|\langle\phi(s,a),\mathcal{T}(\overline{\omega}_{t,h}+\overline{
\theta}_{t,h+1})\rangle|\leq W_{h}$;
- 3.
$\|\eta_{t,h}\|_{\widehat{\Sigma}_{t,h}}\leq B^{{\rm{P}}}_{{\rm{err}}}$;
- 4.
$\|\eta_{t,h}\|_{\Lambda}\leq 2(W_{h}+\varepsilon_{2})\sqrt{m}$;
- 5.
$\|\eta_{t,h}\|_{\Lambda_{t,h}}\leq\sqrt{3}\gamma B^{{\rm{P}}}_{{\rm{err}}}+
\sqrt{8m}(W_{h}+\varepsilon_{2})$ ;
- 6.
$\max_{s,a}|\langle\phi(s,a),\overline{\theta}_{t,h}\rangle|\leq W_{h-1}-\sqrt{
2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}-1-\varepsilon_{2}$
- 7.
$\max_{s}\overline{V}_{t,h}(s)=\max_{s,a}|\overline{Q}_{t,h}(s,a)|\leq W_{h-1}$.

###### Proof of Lemma 9 .

Fix $t\in[T]$. We prove these items by induction on $h$. The base case ($h=H+1$) clearly holds since there is actually nothing at $(H+1)$-th step. Now assume they hold for $h+1$, and we will show that they hold for $h$ as well.

Proof of Item 1. It is simply by 10 of Algorithm 1 and Assumption 3.

Proof of Item 2. By linear Bellman completeness (Definition 1), for any $s,a$, we have,

$$ $\displaystyle|\left\langle\phi(s,a),\mathcal{T}(\overline{\omega}_{t,h}+ \overline{\theta}_{t,h+1})\right\rangle|$ $\displaystyle=\left|\mathop{\mathbb{E}}_{s^{\prime}\sim\mathsf{T}(s,a)}\max_{a ^{\prime}}\left\langle\phi(s^{\prime},a^{\prime}),\,\overline{\omega}_{t,h}+ \overline{\theta}_{t,h+1}\right\rangle\right|$ $\displaystyle\leq\max_{s,a}\left|\left\langle\phi(s,a),\,\overline{\omega}_{t, h}+\overline{\theta}_{t,h+1}\right\rangle\right|$ $\displaystyle\leq\max_{s,a}|\left\langle\phi(s,a),\widehat{\omega}_{t,h}\right \rangle|+\max_{s,a}\left|\left\langle\phi(s,a),\xi^{{\rm{R}}}_{t,h}\right \rangle\right|+\max_{s,a}\left|\left\langle\phi(s,a),\overline{\theta}_{t,h+1} \right\rangle\right|$ $\displaystyle\leq(1+\varepsilon_{2})+\max_{s,a}\|\phi(s,a)\|_{\Sigma_{t,h}^{-1 }}\|\xi^{{\rm{R}}}_{t,h}\|_{\Sigma_{t,h}}+(W_{h}-\sqrt{2d}\cdot B^{{\rm{R}}}_{ {\rm{noise}}}-1-\varepsilon_{2})$ $\displaystyle\leq 1+\varepsilon_{2}+\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}} +(W_{h}-\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}-1-\varepsilon_{2})=W_{h}.$ $$

Proof of Item 3. This is directly from Lemma 7.

Proof of Item 4. By triangle inequality, we have

$$ $\displaystyle\|\eta_{t,h}\|_{\Lambda}=\left\|\widehat{\theta}_{t,h}-\mathcal{T }(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})\right\|_{\Lambda}\leq \left\|\widehat{\theta}_{t,h}\right\|_{\Lambda}+\left\|\mathcal{T}(\overline{ \omega}_{t,h}+\overline{\theta}_{t,h+1})\right\|_{\Lambda}\leq 2(W_{h}+ \varepsilon_{2})\sqrt{m}.$ $$

where the last step is by

$$ $\displaystyle\left\|\widehat{\theta}_{t,h}\right\|_{\Lambda}=\sqrt{\sum_{i=1}^ {m}\left\langle\phi_{i},\,\widehat{\theta}_{t,h}\right\rangle^{2}}\leq\sqrt{ \sum_{i=1}^{m}(W_{h}+\varepsilon_{2})^{2}}=(W_{h}+\varepsilon_{2})\sqrt{m}$ $$

and the similar for $\mathcal{T}(\overline{\omega}_{t,h}+\overline{\theta}_{t,h+1})$.

Proof of Item 5. By definition, we have

$$ $\displaystyle\|\eta_{t,h}\|^{2}_{\Lambda_{t,h}}$ $\displaystyle=\sum_{i=1}^{m}\rho_{i}\bigg{(}\left\langle\phi^{\parallel}_{t,h, i},\,\eta_{t,h}\right\rangle^{2}+\left\langle\phi^{\perp}_{t,h,i},\,\eta_{t,h} \right\rangle^{2}\bigg{)}$ $\displaystyle=\sum_{i=1}^{m}\rho_{i}\bigg{(}\left\langle P_{t,h}\phi_{i},\, \eta_{t,h}\right\rangle^{2}+\left\langle(I-P_{t,h})\phi_{i},\,\eta_{t,h}\right \rangle^{2}\bigg{)}$ $\displaystyle\leq\sum_{i=1}^{m}\rho_{i}\bigg{(}3\left\langle P_{t,h}\phi_{i}, \,\eta_{t,h}\right\rangle^{2}+2\left\langle\phi_{i},\,\eta_{t,h}\right\rangle^ {2}\bigg{)}$ (using $(a+b)^{2}\leq a^{2}+b^{2}$ ) $\displaystyle\leq 3\sum_{i=1}^{m}\rho_{i}\bigg{(}\left\|\phi^{\parallel}_{t,h, i}\right\|^{2}_{\widehat{\Sigma}^{\dagger}_{t,h}}\left\|\eta_{t,h}\right\|^{2} _{\widehat{\Sigma}_{t,h}}\bigg{)}+2\|\eta_{t,h}\|^{2}_{\Lambda}$ (Cauchy-Schwartz, Lemma 25 ) $$

We have $\|\phi^{\parallel}_{t,h,i}\|_{\widehat{\Sigma}^{\dagger}_{t,h}}=\|P_{t,h}\phi_
{i}\|_{\widehat{\Sigma}^{\dagger}_{t,h}}=\|\phi_{i}\|_{\widehat{\Sigma}^{
\dagger}_{t,h}}$ by Lemma 26. By Assumption 4, this is upper bounded by $\gamma$. The second term, $\|\eta_{t,h}\|_{\widehat{\Sigma}_{t,h}}$, is upper bounded by $B^{{\rm{P}}}_{{\rm{err}}}$ by Item 3.

Hence, we have

$$ $\displaystyle\|\eta_{t,h}\|^{2}_{\Lambda_{t,h}}$ $\displaystyle\leq 3\gamma^{2}(B^{{\rm{P}}}_{{\rm{err}}})^{2}+2\|\eta_{t,h}\|^{ 2}_{\Lambda}$ $\displaystyle\leq 3\gamma^{2}(B^{{\rm{P}}}_{{\rm{err}}})^{2}+8(W_{h}+ \varepsilon_{2})^{2}m.$ ( Item 4 ) $$

Proof of Item 6. We have

$$ $\displaystyle\max_{s,a}\left|\left\langle\phi(s,a),\overline{\theta}_{t,h} \right\rangle\right|$ $\displaystyle=\max_{s,a}\left|\left\langle\phi(s,a),\,\widehat{\theta}_{t,h}+ \xi^{{\rm{P}}}_{t,h}\right\rangle\right|$ $\displaystyle\leq\max_{s,a}|\left\langle\phi(s,a),\widehat{\theta}_{t,h}\right \rangle|+\max_{s,a}\left|\left\langle\phi(s,a),\xi^{{\rm{P}}}_{t,h}\right \rangle\right|$ $\displaystyle\leq W_{h}+\varepsilon_{2}+\max_{s,a}\|\phi(s,a)\|_{\Lambda_{t,h} ^{-1}}\|\xi^{{\rm{P}}}_{t,h}\|_{\Lambda_{t,h}}$ $\displaystyle\leq W_{h}+\varepsilon_{2}+\sqrt{2d}\cdot B^{{\rm{P}}}_{{\rm{ noise}},h}$ ( Lemma 5 ) $\displaystyle=W_{h-1}-\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}-1-\varepsilon _{2}.$ $$

Proof of Item 7. We have

$$ $\displaystyle|\overline{Q}_{t,h}(s,a)|$ $\displaystyle=|\langle\phi(s,a),\overline{\theta}_{t,h}\rangle+\langle\phi(s,a ),\overline{\omega}_{t,h}\rangle|$ $\displaystyle\leq|\langle\phi(s,a),\overline{\theta}_{t,h}\rangle|+|\left \langle\phi(s,a),\widehat{\omega}_{t,h}\right\rangle|+|\left\langle\phi(s,a), \xi^{{\rm{R}}}_{t}\right\rangle|$ $\displaystyle\leq(W_{h-1}-\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}-1- \varepsilon_{2})+(1+\varepsilon_{2})+\sqrt{2d}\cdot B^{{\rm{R}}}_{{\rm{noise}}}$ $\displaystyle=W_{h-1}.$ $$

and also, $\max_{s}|\overline{V}_{t,h}(s)|=\max_{s,a}|\overline{Q}_{t,h}(s,a)|\leq W_{h-1}$.
∎

###### Lemma 6 (Reward estimation) .

###### Proof of Lemma 6 .

###### Lemma 7 (Value function estimation) .

###### Proof of Lemma 7 .

###### Definition 5 (High-probability events) .

###### Lemma 8 .

###### Proof of Lemma 8 .

###### Lemma 9 (Boundness of parameters) .

###### Proof of Lemma 9 .

### B.2 Value Decomposition

We note that, at any round $t\in[T]$, conditioning on all information collected up to round $t-1$, the randomness of $\overline{V}_{t}$ only comes from the Gaussian noise $\{\xi^{{\rm{P}}}_{t,h},\xi^{{\rm{R}}}_{t,h}\}_{h=1}^{H}$. In other words, $\overline{V}_{t}$ can be considered a functional of the Gaussian noise. In light of this, we define

$$ $\displaystyle V_{t,h}[{\check{\xi}}^{{\rm{P}}}_{1},\dots,{\check{\xi}}^{{\rm{P }}}_{H},{\check{\xi}}^{{\rm{R}}}_{1},\dots,{\check{\xi}}^{{\rm{R}}}_{H}](\cdot)$ $$

as a functional of the noise variable, which maps the given noise variable to the value function produced by the algorithm by replacing the random Gaussian noise with the variable ${\check{\xi}}^{{\rm{P}}}_{1},\dots,{\check{\xi}}^{{\rm{P}}}_{H},{\check{\xi}}^
{{\rm{R}}}_{1},\dots,{\check{\xi}}^{{\rm{R}}}_{H}$. By definition, we immediately have

$$ $\displaystyle\overline{V}_{t,h}(\cdot)=V_{t,h}[\xi^{{\rm{P}}}_{t,1},\dots,\xi^ {{\rm{P}}}_{t,H},\xi^{{\rm{R}}}_{t,1},\dots,\xi^{{\rm{R}}}_{t,H}](\cdot).$ $$

Next, we define $U_{t}$ as the minimum of the following program

$$ $\displaystyle\min_{{\check{\xi}}^{{\rm{P}}}_{1},\dots,{\check{\xi}}^{{\rm{P}}} _{H},{\check{\xi}}^{{\rm{R}}}_{1},\dots,{\check{\xi}}^{{\rm{R}}}_{H}}V_{t,1} \left[{\check{\xi}}^{{\rm{P}}}_{1},\dots,{\check{\xi}}^{{\rm{P}}}_{H},{\check{ \xi}}^{{\rm{R}}}_{1},\dots,{\check{\xi}}^{{\rm{R}}}_{H}\right](s_{t,1})$ $\displaystyle\text{s.t.}\quad\forall h\in[H]:\|{\check{\xi}}^{{\rm{P}}}_{t,h} \|_{\Lambda_{t,h}}\leq B^{{\rm{P}}}_{{\rm{noise}},h},\quad\|{\check{\xi}}^{{ \rm{R}}}_{t,h}\|_{\Sigma_{t,h}}\leq B^{{\rm{R}}}_{{\rm{noise}}}.$ $$

In other words, $U_{t}$ achieves the minimum value at $s_{t,1}$ while satisfying the high-probability constraints ($\mathfrak{E}^{{\rm{high}}}{}$) on the noise variable. We denote ${\underline{\xi}}^{{\rm{P}}}_{1},\dots,{\underline{\xi}}^{{\rm{P}}}_{H},{
\underline{\xi}}^{{\rm{R}}}_{1},\dots,{\underline{\xi}}^{{\rm{R}}}_{H}$ as the minimizer of the above program, and will always use underlined variables to represent the intermediate variables corresponding to $U_{t}$ (such as $\underline{\widehat{\theta}}$, $\underline{\overline{\theta}}$, $\underline{\widehat{\omega}}$, $\underline{\overline{\omega}}$, $\underline{\overline{Q}}$, $\underline{\overline{V}}$) to distinguish them from the variables corresponding to $\overline{V}_{t}$, (${\widehat{\theta}}$, ${\overline{\theta}}$, ${\widehat{\omega}}$, ${\overline{\omega}}$, $\overline{Q}$, $\overline{V}$). We note that, under $\mathfrak{E}^{{\rm{high}}}{}$, we directly have $U_{t}(s_{t,1})\leq\overline{V}_{t}(s_{t,1})$.

Below is the a decomposition lemma under deterministic transition. We denote $\{s_{t,h},a_{t,h}\}_{h=1}^{H}$ as the trajectory generated by executing $\pi_{t}$ with initial state $s_{t,1}$, and $\{s^{\star}_{t,h},a^{\star}_{t,h}\}_{h=1}^{H}$ denote the trajectory generated by executing $\pi^{\star}$ with initial state $s^{\star}_{t,1}=s_{t,1}$.

###### Lemma 10 (Value decomposition under deterministic transition) .

Under deterministic transition (Assumption 1), we have

$$ $\displaystyle V^{\pi_{t}}(s_{t,1})-\overline{V}_{t}(s_{t,1})=$ $\displaystyle\sum_{h=1}^{H}\Big{(}\overline{V}_{t,h+1}(s_{t,h+1})-\left\langle \overline{\theta}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle+\left\langle\omega^ {\star}_{h}-\overline{\omega}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\Big{)};$ (10) $\displaystyle V^{\star}(s_{t,1})-\overline{V}_{t}(s_{t,1})\leq$ $\displaystyle\sum_{h=1}^{H}\Big{(}\overline{V}_{t,h+1}(s^{\star}_{t,h+1})- \left\langle\overline{\theta}_{t,h},\phi(s^{\star}_{t,h},a^{\star}_{t,h}) \right\rangle+\left\langle\omega^{\star}_{h}-\overline{\omega}_{t,h},\phi(s^{ \star}_{t,h},a^{\star}_{t,h})\right\rangle\Big{)}.$ (11) $$

Similarly, we have

$$ $\displaystyle V^{\pi_{t}}(s_{t,1})-U_{t}(s_{t,1})\leq\sum_{h=1}^{H}\Big{(}U_{t ,h+1}(s_{t,h+1})-\left\langle\underline{\overline{\theta}}_{t,h},\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\omega^{\star}_{h}-\underline{\overline{ \omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\Big{)}.$ (12) $$

###### Proof of Lemma 10 .

We will prove (10) and (11) altogether, and then prove (12).

Proof of (10) and (11).
We consider an arbitrary policy $\pi$. Let $\{s^{\prime}_{t,h},a^{\prime}_{t,h}\}_{h=1}^{H}$ denote the deterministic trajectory generated by $\pi$ with initial state $s^{\prime}_{t,1}=s_{t,1}$. By definition, we have

$$ $\displaystyle V^{\pi}(s^{\prime}_{t,1})-\overline{V}_{t}(s^{\prime}_{t,1})$ $\displaystyle=Q_{1}^{\pi}(s^{\prime}_{t,1},\pi(s^{\prime}_{t,1}))-\max_{a} \overline{Q}_{t,1}(s^{\prime}_{t,1},a)$ $\displaystyle\leq Q_{1}^{\pi}(s^{\prime}_{t,1},\pi(s^{\prime}_{t,1}))- \overline{Q}_{t,1}(s^{\prime}_{t,1},\pi(s^{\prime}_{t,1}))$ (13) $\displaystyle=V_{2}^{\pi}(s^{\prime}_{t,2})+r_{h}(s^{\prime}_{t,1},a^{\prime}_ {t,1})-\left\langle\overline{\theta}_{t,1},\phi(s^{\prime}_{t,1},\pi(s^{\prime }_{t,1}))\right\rangle-\left\langle\overline{\omega}_{t,h},\phi(s^{\prime}_{t, 1},\pi(s^{\prime}_{t,1}))\right\rangle$ (by definition) $\displaystyle=\Big{(}V_{2}^{\pi}(s^{\prime}_{t,2})-\overline{V}_{t,2}(s^{ \prime}_{t,2})\Big{)}+\Big{(}\overline{V}_{t,2}(s^{\prime}_{t,2})-\left\langle \overline{\theta}_{t,1},\phi(s^{\prime}_{t,1},\pi(s^{\prime}_{t,1}))\right \rangle\Big{)}+\left\langle\omega^{\star}_{h}-\overline{\omega}_{t,h},\phi(s^{ \prime}_{t,1},a^{\prime}_{t,1})\right\rangle$ $$

Recursively expanding the first term, we obtain

$$ $\displaystyle V^{\pi}(s^{\prime}_{t,1})-\overline{V}_{t}(s^{\prime}_{t,1})\leq \sum_{h=1}^{H}\Big{(}\overline{V}_{t,h+1}(s^{\prime}_{t,h+1})-\left\langle \overline{\theta}_{t,h},\phi(s^{\prime}_{t,h},a^{\prime}_{t,h})\right\rangle+ \left\langle\omega^{\star}_{h}-\overline{\omega}_{t,h},\phi(s^{\prime}_{t,h},a ^{\prime}_{t,h})\right\rangle\Big{)}.$ $$

This proves (11) by specifying $\pi=\pi^{\star}$. Similarly, (10) can be proved by observing that the only inequality (13) becomes equality when $\pi=\pi_{t}$.

Proof of (12). The proof is quite similar. We have

$$ $\displaystyle V^{\pi_{t}}(s_{t,1})-U_{t}(s_{t,1})$ $\displaystyle=Q_{1}^{\pi_{t}}(s_{t,1},{\pi_{t}}(s_{t,1}))-\max_{a}\underline{ \overline{Q}}_{t,1}(s_{t,1},a)$ $\displaystyle\leq Q_{1}^{\pi_{t}}(s_{t,1},{\pi_{t}}(s_{t,1}))-\underline{ \overline{Q}}_{t,1}(s_{t,1},{\pi_{t}}(s_{t,1}))$ $\displaystyle=V_{2}^{\pi_{t}}(s_{t,2})+r_{h}(s_{t,1},a_{t,1})-\left\langle \underline{\overline{\theta}}_{t,1},\phi(s_{t,1},{\pi_{t}}(s_{t,1}))\right \rangle-\left\langle\underline{\overline{\omega}}_{t,h},\phi(s_{t,1},a_{t,1})\right\rangle$ (by definition) $\displaystyle=\Big{(}V_{2}^{\pi_{t}}(s_{t,2})-U_{t,2}(s_{t,2})\Big{)}+\Big{(}U _{t,2}(s_{t,2})-\left\langle\underline{\overline{\theta}}_{t,1},\phi(s_{t,1},{ \pi_{t}}(s_{t,1}))\right\rangle\Big{)}+\left\langle\omega^{\star}_{h}- \underline{\overline{\omega}}_{t,h},\phi(s_{t,1},a_{t,1})\right\rangle$ $$

Recursively expanding the first term, we obtain

$$ $\displaystyle V^{\pi_{t}}(s_{t,1})-U_{t}(s_{t,1})\leq\sum_{h=1}^{H}\Big{(}U_{t ,h+1}(s_{t,h+1})-\left\langle\underline{\overline{\theta}}_{t,h},\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\omega^{\star}_{h}-\underline{\overline{ \omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\Big{)}.$ $$

This completes the proof.
∎

###### Lemma 11 .

For any $t\in[T]$, conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$, we have the following (in)equalities:

$$ $\displaystyle\overline{V}_{t}(s_{t,1})$ $\displaystyle=\sum_{h=1}^{H}\bigg{(}\left\langle\widehat{\theta}_{t,h}- \mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1}),\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\overline{\omega}_{t,h},\phi(s_{t,h},a_{t,h} )\right\rangle\bigg{)},$ $\displaystyle U_{t}(s_{t,1})$ $\displaystyle\geq\sum_{h=1}^{H}\bigg{(}\left\langle\underline{\widehat{\theta} }_{t,h}-\mathcal{T}(\underline{\overline{\theta}}_{t,h+1}+\underline{\overline {\omega}}_{t,h+1}),\phi(s_{t,h},a_{t,h})\right\rangle+\left\langle\underline{ \overline{\omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}.$ $$

###### Proof of Lemma 11 .

We will prove the two statements separately, but the proofs are quite similar.

Proof of the first statement.
By Lemma 10, we have

$$ $\displaystyle\overline{V}_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1})$ $\displaystyle=\sum_{h=1}^{H}\bigg{(}\left\langle\widehat{\theta}_{t,h},\phi(s_ {t,h},a_{t,h})\right\rangle+\left\langle\xi^{{\rm{P}}}_{t,h},\phi(s_{t,h},a_{t ,h})\right\rangle-\overline{V}_{t,h+1}(s_{t,h+1})+\left\langle\overline{\omega }_{t,h}-\omega^{\star}_{h},\phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}$ $$

By linear Bellman completeness (Definition 1), there exists a vector, denoted by $\mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1})$, such that $\overline{V}_{t,h+1}(\cdot)=\langle\phi(\cdot,a),\mathcal{T}(\overline{\theta}
_{t,h+1}+\overline{\omega}_{t,h+1})\rangle$. Hence, we can rewrite the above as

$$ $\displaystyle\overline{V}_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1})$ $\displaystyle=\sum_{h=1}^{H}\bigg{(}\left\langle\widehat{\theta}_{t,h}- \mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1}),\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\xi^{{\rm{P}}}_{t,h},\phi(s_{t,h},a_{t,h}) \right\rangle+\left\langle\overline{\omega}_{t,h}-\omega^{\star}_{h},\phi(s_{t ,h},a_{t,h})\right\rangle\bigg{)}.$ $$

Note that by definition of $V^{\pi_{t}}$ we have $V^{\pi_{t}}(s_{t,1})=\sum_{h=1}^{H}\langle\omega^{\star},\phi(s_{t,h},a_{t,h})\rangle$. Hence, the above implies

$$ $\displaystyle\overline{V}_{t}(s_{t,1})=\sum_{h=1}^{H}\bigg{(}\left\langle \widehat{\theta}_{t,h}-\mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega} _{t,h+1})+\xi^{{\rm{P}}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle+\left\langle \overline{\omega}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}.$ $$

We can remove $\xi^{{\rm{P}}}_{t,h}$ since $\langle\xi^{{\rm{P}}}_{t,h},\phi(s_{t,h},a_{t,h})\rangle=0$ conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$.

Proof of the second statement.
By Lemma 10, we have

$$ $\displaystyle V^{\pi_{t}}(s_{t,1})-U_{t}(s_{t,1})\leq\sum_{h=1}^{H}\Big{(}U_{t ,h+1}(s_{t,h+1})-\left\langle\underline{\overline{\theta}}_{t,h},\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\omega^{\star}_{h}-\underline{\overline{ \omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\Big{)}$ $$

Again, by the definition of $V^{\pi_{t}}$, we conclude that

$$ $\displaystyle U_{t}(s_{t,1})\geq\sum_{h=1}^{H}\bigg{(}\left\langle\underline{ \overline{\omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle+\left\langle \underline{\widehat{\theta}}_{t,h}-\mathcal{T}(\underline{\overline{\theta}}_{ t,h+1}+\underline{\overline{\omega}}_{t,h+1})+{\underline{\xi}}^{{\rm{P}}}_{t, h},\phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}.$ $$

We can remove ${\underline{\xi}}^{{\rm{P}}}_{t,h}$ since $\langle{\underline{\xi}}^{{\rm{P}}}_{t,h},\phi(s_{t,h},a_{t,h})\rangle=0$ conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$.
∎

The following lemma shows that, conditioning on the span event $\mathfrak{E}^{{\rm{span}}}_{t}$, the value function $\overline{V}_{t}$ cannot deviate too much from the value function $V^{\pi_{t}}$ on average.

###### Lemma 12 .

For any $t\in[T]$, under Assumption 4 and conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$ and $\mathfrak{E}^{{\rm{high}}}$, we have

$$ $\displaystyle\sum_{t=1}^{T}\Big{(}\overline{V}_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1 })\Big{)}\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H+(B^{{\rm{R}}}_{{\rm{noise}}}+B ^{{\rm{R}}}_{{\rm{err}}})\cdot B_{\phi}^{{\rm{R}}}.$ $$

###### Proof of Lemma 12 .

We apply Lemma 11 to decompose $\overline{V}_{t}$ and obtain

$$ $\displaystyle\sum_{t=1}^{T}\Big{(}\overline{V}_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1 })\Big{)}$ $\displaystyle=\sum_{t=1}^{T}\bigg{(}\left\langle\widehat{\theta}_{t,h}- \mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1}),\phi(s_{t,h}, a_{t,h})\right\rangle+\left\langle\overline{\omega}_{t,h}-\omega^{\star}_{h}, \phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}$ Applying Cauchy-Schwartz yields $\displaystyle\leq\sum_{t=1}^{T}\bigg{(}\left\|\widehat{\theta}_{t,h}-\mathcal{ T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1})\right\|_{\widehat{ \Sigma}_{t,h}}\left\|\phi(s_{t,h},a_{t,h})\right\|_{\widehat{\Sigma}^{\dagger} _{t,h}}+\left\|\overline{\omega}_{t,h}-\omega^{\star}_{h}\right\|_{\Sigma_{t,h }},\left\|\phi(s_{t,h},a_{t,h})\right\|_{\Sigma_{t,h}^{-1}}\bigg{)}$ We apply Lemma 7 and Assumption 4 to the left term and Lemmas 6 and 16 and Definition 5 to the right. Then, we obtain $\displaystyle\leq H\cdot B^{{\rm{P}}}_{{\rm{err}}}\gamma+(B^{{\rm{R}}}_{{\rm{ noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot B_{\phi}^{{\rm{R}}}.$ $$

This completes the proof.
∎

The following lemma establishes upper bounds on the value functions when conditioning on the span event $\mathfrak{E}^{{\rm{span}}}_{t}$.

###### Lemma 13 .

For any $t\in[T]$, conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$ and $\mathfrak{E}^{{\rm{high}}}{}$, we have

$$ $\displaystyle|U_{t}(s_{t,1})|\leq H\cdot(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R }}}_{{\rm{err}}})\cdot\sqrt{d}+H\cdot(1+B^{{\rm{P}}}_{{\rm{err}}}\gamma).$ $$

Moreover, we have

$$ $\displaystyle|\overline{V}_{t}(s_{t,1})|\leq H\cdot(B^{{\rm{R}}}_{{\rm{noise}} }+B^{{\rm{R}}}_{{\rm{err}}})\cdot\sqrt{d}+H\cdot(1+B^{{\rm{P}}}_{{\rm{err}}} \gamma).$ $$

We abbreviate $B_{V}:=H\cdot(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot\sqrt
{d}+H\cdot(1+B^{{\rm{P}}}_{{\rm{err}}}\gamma)$.

###### Proof of Lemma 13 .

We will first prove the second statement and then the first statement.

Proof of the second statement.
Applying Lemma 11 and the triangle inequality, we have the following

$$ $\displaystyle|\overline{V}_{t}(s_{t,1})|$ $\displaystyle\leq\left|\sum_{h=1}^{H}\left\langle\overline{\omega}_{t,h},\phi( s_{t,h},a_{t,h})\right\rangle\right|+\left|\sum_{h=1}^{H}\left\langle\widehat{ \theta}_{t,h}-\mathcal{T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1}) ,\phi(s_{t,h},a_{t,h})\right\rangle\right|$ $\displaystyle=:\mathtt{T}_{1}+\mathtt{T}_{2}.$ $$

We bound the two terms separately. For $\mathtt{T}_{1}$, we have

$$ $\displaystyle\mathtt{T}_{1}$ $\displaystyle=\left|\sum_{h=1}^{H}\left\langle(\overline{\omega}_{t,h}- \widehat{\omega}_{t,h})+(\widehat{\omega}_{t,h}-\omega^{\star})+\omega^{\star} _{h},\phi(s_{t,h},a_{t,h})\right\rangle\right|$ $\displaystyle\leq\sum_{h=1}^{H}\left(\|\overline{\omega}_{t,h}-\widehat{\omega }_{t,h}\|_{\Sigma_{t,h}}+\|\widehat{\omega}_{t,h}-\omega^{\star}_{h}\|_{\Sigma _{t,h}}\right)\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}+V^{\pi_{t}}$ (Cauchy-Schwartz) $\displaystyle\leq H\cdot(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R}}}_{{\rm{err}}} )\cdot\sqrt{d}+H.$ ( Definitions 5 and 5 ) $$

For $\mathtt{T}_{2}$, we can use Cauchy-Schwartz:

$$ $\displaystyle\mathtt{T}_{2}$ $\displaystyle=\left|\sum_{h=1}^{H}\left\langle\widehat{\theta}_{t,h}-\mathcal{ T}(\overline{\theta}_{t,h+1}+\overline{\omega}_{t,h+1}),\phi(s_{t,h},a_{t,h}) \right\rangle\right|$ $\displaystyle\leq\sum_{h=1}^{H}\|\widehat{\theta}_{t,h}-\mathcal{T}(\overline{ \theta}_{t,h+1}+\overline{\omega}_{t,h+1})\|_{\widehat{\Sigma}_{t,h}}\|\phi(s_ {t,h},a_{t,h})\|_{\widehat{\Sigma}_{t,h}^{\dagger}}$ (Cauchy-Schwartz, Lemma 25 ) $\displaystyle\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H.$ ( Assumptions 4 and 7 ) $$

Proof of the first statement.
We prove it by establishing a lower bound and an upper bound of $U_{t}(s_{t,1})$ separately. We start with the lower bound, whose derivation is similar to the second statement we just proved above:

$$ $\displaystyle U_{t}(s_{t,1})$ $\displaystyle\geq\sum_{h=1}^{H}\bigg{(}\left\langle\underline{\widehat{\theta} }_{t,h}-\mathcal{T}(\underline{\overline{\theta}}_{t,h+1}+\underline{\overline {\omega}}_{t,h+1}),\phi(s_{t,h},a_{t,h})\right\rangle+\left\langle\underline{ \overline{\omega}}_{t,h},\phi(s_{t,h},a_{t,h})\right\rangle\bigg{)}$ ( Lemma 11 ) $\displaystyle\geq-B^{{\rm{P}}}_{{\rm{err}}}\gamma H-\left|\sum_{h=1}^{H}\left \langle(\underline{\overline{\omega}}_{t,h}-\underline{\widehat{\omega}}_{t,h} )+(\underline{\widehat{\omega}}_{t,h}-\omega^{\star}_{h})+\omega^{\star}_{h}, \phi(s_{t,h},a_{t,h})\right\rangle\right|$ (following a similar argument as above) $\displaystyle\geq-B^{{\rm{P}}}_{{\rm{err}}}\gamma H-\sum_{h=1}^{H}\left(\| \underline{\overline{\omega}}_{t,h}-\underline{\widehat{\omega}}_{t,h}\|_{ \Sigma_{t,h}}+\|\underline{\widehat{\omega}}_{t,h}-\omega^{\star}_{h}\|_{ \Sigma_{t,h}}\right)\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}$ (Cauchy-Schwartz) $\displaystyle\geq-B^{{\rm{P}}}_{{\rm{err}}}\gamma H-H\cdot(B^{{\rm{R}}}_{{\rm{ noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot\sqrt{d}.$ ( Lemma 8 ) $$

The upper bound of $U_{t}(s_{t,1})$ is a consequence of the second statement we just proved above:

$$ $\displaystyle U_{t}(s_{t,1})$ $\displaystyle\leq\mathop{\mathbb{E}}[\overline{V}_{t}(s_{t,1})\,|\,\mathfrak{E }^{{\rm{high}}}{}]$ (by definition) $\displaystyle\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H+H\cdot(B^{{\rm{R}}}_{{\rm{ noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot\sqrt{d}+H.$ $$

We finish the proof by combining the lower and upper bounds.
∎

###### Lemma 10 (Value decomposition under deterministic transition) .

###### Proof of Lemma 10 .

###### Lemma 11 .

###### Proof of Lemma 11 .

###### Lemma 12 .

###### Proof of Lemma 12 .

###### Lemma 13 .

###### Proof of Lemma 13 .

### B.3 Exploration in the Null Space

###### Lemma 14 (optimism with constant probability) .

For any $t\in[T]$, denote $\mathfrak{E}^{{\rm{optm}}}_{t}$ as the event that

$$ $\displaystyle V^{\star}(s_{t,1})\leq\overline{V}_{t}(s_{t,1})+B^{{\rm{P}}}_{{ \rm{err}}}\gamma H.$ $$

Then, under Assumption 4 and conditioning on the high-probability event $\mathfrak{E}^{{\rm{high}}}$, we have

$$ $\displaystyle\operatorname{Pr}\left(\mathfrak{E}^{{\rm{optm}}}_{t}\right)\geq \Gamma^{2}(-1)$ $$

where $\Gamma(\cdot)$ is the CDF of the standard normal distribution.

###### Proof of Lemma 14 .

By Lemma 10, we have:

$$ $\displaystyle V^{\star}(s_{t,1})-\overline{V}_{t}(s_{t,1})$ $\displaystyle\leq\sum_{h=1}^{H}\Big{(}\overline{V}_{t,h+1}(s^{\star}_{t,h+1})- \left\langle\overline{\theta}_{t,h},\phi(s^{\star}_{t,h},a^{\star}_{t,h}) \right\rangle+\left\langle\omega^{\star}_{h}-\overline{\omega}_{t,h},\phi(s^{ \star}_{t,h},a^{\star}_{t,h})\right\rangle\Big{)}$ $\displaystyle=\underbrace{\sum_{h=1}^{H}\Big{(}\overline{V}_{t,h+1}(s^{\star}_ {t,h+1})-\left\langle\widehat{\theta}_{t,h},\phi(s^{\star}_{t,h},a^{\star}_{t, h})\right\rangle\Big{)}}_{\rm(i)}-\underbrace{\sum_{h=1}^{H}\left\langle\xi^{{ \rm{P}}}_{t,h},\phi(s^{\star}_{t,h},a^{\star}_{t,h})\right\rangle}_{\rm(ii)}$ $\displaystyle+\underbrace{\sum_{h=1}^{H}\left\langle\omega^{\star}_{h}- \widehat{\omega}_{t,h},\phi(s^{\star}_{t,h},a^{\star}_{t,h})\right\rangle}_{ \rm(iii)}-\underbrace{\sum_{h=1}^{H}\left\langle\xi^{{\rm{R}}}_{t,h},\phi(s^{ \star}_{t,h},a^{\star}_{t,h})\right\rangle}_{\rm(iv)}.$ $$

Note that, given any state-action-state triple $(s,a,s^{\prime})$, we have

$$ $\displaystyle\overline{V}_{t,h+1}(s^{\prime})-\left\langle\widehat{\theta}_{t, h},\phi(s,a)\right\rangle=\left\langle\mathcal{T}(\overline{\omega}_{t,h+1}+ \overline{\theta}_{t,h+1})-\widehat{\theta}_{t,h},\phi(s,a)\right\rangle=\left \langle\eta_{t,h},\phi(s,a)\right\rangle.$ $$

Plugging this back to (i), we obtain

$$ $\displaystyle{\rm(i)}-{\rm(ii)}$ $\displaystyle\leq\sum_{h=1}^{H}\left\langle\eta_{t,h}-\xi^{{\rm{P}}}_{t,h}, \phi(s^{\star}_{t,h},a^{\star}_{t,h})\right\rangle=:\sum_{h=1}^{H}\left\langle \eta_{t,h}-\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star}\right\rangle$ $$

where we abbreviate $\phi_{h}^{\star}:=\phi(s^{\star}_{t,h},a^{\star}_{t,h})$.
Next, we split it into two parts:

$$ $\displaystyle{\rm(i)}-{\rm(ii)}$ $\displaystyle\leq\sum_{h=1}^{H}\left\langle\eta_{t,h},P_{t,h}\phi_{h}^{\star} \right\rangle+\sum_{h=1}^{H}\left\langle\eta_{t,h},(I-P_{t,h})\phi_{h}^{\star} \right\rangle-\sum_{h=1}^{H}\left\langle\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star}\right\rangle$ $\displaystyle\leq\sum_{h=1}^{H}\|\eta_{t,h}\|_{\widehat{\Sigma}_{t,h}}\|P_{t,h }\phi_{h}^{\star}\|_{\widehat{\Sigma}^{\dagger}_{t,h}}+\sum_{h=1}^{H}\|\eta_{t ,h}\|_{\Lambda_{t,h}}\|(I-P_{t,h})\phi_{h}^{\star}\|_{\Lambda_{t,h}^{-1}}-\sum _{h=1}^{H}\left\langle\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star}\right\rangle$ (Cauchy-Schwartz, Lemma 25 ) $\displaystyle\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H+\sum_{h=1}^{H}\|\eta_{t,h} \|_{\Lambda_{t,h}}\|(I-P_{t,h})\phi_{h}^{\star}\|_{\Lambda_{t,h}^{-1}}-\sum_{h =1}^{H}\left\langle\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star}\right\rangle$ ( Assumption 4 and Lemmas 26 and 7 ) $\displaystyle\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H+\sqrt{H\sum_{h=1}^{H}\| \eta_{t,h}\|^{2}_{\Lambda_{t,h}}\|(I-P_{t,h})\phi_{h}^{\star}\|^{2}_{\Lambda_{ t,h}^{-1}}}-\sum_{h=1}^{H}\left\langle\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star}\right\rangle$ (Cauchy-Schwartz) $$

Recall that $\xi^{{\rm{P}}}_{t,h}$ is sampled from $\mathcal{N}(0,\sigma_{h}^{2}(I-P_{t,h})\Lambda_{t,h}^{-1}(I-P_{t,h}))$. Therefore,

$$ $\displaystyle\sum_{h=1}^{H}\left\langle\xi^{{\rm{P}}}_{t,h},\phi_{h}^{\star} \right\rangle\sim\mathcal{N}\left(0,\sum_{h=1}^{H}\sigma_{h}^{2}\big{\|}(I-P_{ t,h})\phi_{h}^{\star}\big{\|}_{\Lambda_{t,h}^{-1}}^{2}\right).$ $$

Since $\sigma_{h}\geq\sqrt{H}\|\eta_{t,h}\|_{\Lambda_{t,h}}$ under high-probability event $\mathfrak{E}^{{\rm{high}}}$, we have

$$ $\displaystyle\operatorname{Pr}\big{(}{\rm{(i)}-\rm{(ii)}}\leq B^{{\rm{P}}}_{{ \rm{err}}}\gamma H\big{)}\geq\Gamma(-1).$ $$

Next, we consider ${\rm(iii)}-{\rm(iv)}$. By a similar argument, we have

$$ $\displaystyle{\rm(iii)}-{\rm(iv)}$ $\displaystyle=\sum_{h=1}^{H}\left\langle\omega^{\star}_{h}-\widehat{\omega}_{t ,h},\phi_{h}^{\star}\right\rangle-\sum_{h=1}^{H}\left\langle\xi^{{\rm{R}}}_{t, h},\phi_{h}^{\star}\right\rangle$ $\displaystyle\leq\sum_{h=1}^{H}\|\omega^{\star}_{h}-\widehat{\omega}_{t,h}\|_{ \Sigma_{t,h}}\|\phi_{h}^{\star}\|_{\Sigma_{t,h}^{-1}}-\sum_{h=1}^{H}\left \langle\xi^{{\rm{R}}}_{t,h},\phi_{h}^{\star}\right\rangle$ $\displaystyle\leq\sqrt{H\cdot\sum_{h=1}^{H}\|\omega^{\star}_{h}-\widehat{ \omega}_{t,h}\|^{2}_{\Sigma_{t,h}}\|\phi_{h}^{\star}\|^{2}_{\Sigma_{t,h}^{-1}} }-\sum_{h=1}^{H}\left\langle\xi^{{\rm{R}}}_{t,h},\phi_{h}^{\star}\right\rangle.$ $$

Recall that $\xi^{{\rm{R}}}_{t}$ is sampled from $\mathcal{N}(0,\sigma_{{\rm{R}}}^{2}\Sigma_{t,h}^{-1})$, and thus, we have

$$ $\displaystyle\sum_{h=1}^{H}\left\langle\xi^{{\rm{R}}}_{t},\phi_{h}^{\star} \right\rangle\sim\mathcal{N}\left(0,\sum_{h=1}^{H}\sigma_{{\rm{R}}}^{2}\big{\| }\phi_{h}^{\star}\big{\|}_{\Sigma_{t,h}^{-1}}^{2}\right).$ $$

Therefore, since $\sigma_{{\rm{R}}}\geq\sqrt{H}\|\omega^{\star}_{h}-\widehat{\omega}_{t,h}\|_{
\Sigma_{t}}$ (Lemma 9), we have

$$ $\displaystyle\operatorname{Pr}\left({\rm(iii)}-{\rm(iv)}\leq 0\right)\geq \Gamma(-1).$ $$

Since the two events are independent, the probability that both events happen is at least $\Gamma^{2}(-1)$.
∎

###### Lemma 15 .

The number of times $\mathfrak{E}^{{\rm{span}}}_{t}$ does not hold will not exceed $dH$, i.e.,

$$ $\displaystyle\sum_{t=1}^{T}{\mathbf{1}}\left\{(\mathfrak{E}^{{\rm{span}}}_{t}) ^{\complement}\right\}\leq dH.$ $$

###### Proof.

By definition, when $\mathfrak{E}^{{\rm{span}}}_{t}$ does not hold, there exists $h\in[H]$ such that $\phi(s_{t,h},a_{t,h})$ is not in the span of $\{\phi(s_{i,h},a_{i,h})\}_{i=1}^{t-1}$. That means, the dimension of the span should increase by exactly one after this iteration, i.e.,

$$ $\displaystyle\dim\left({\rm{span}}\left(\{\phi(s_{i,h},a_{i,h})\}_{i=1}^{t} \right)\right)=\dim\left({\rm{span}}\left(\{\phi(s_{i,h},a_{i,h})\}_{i=1}^{t-1 }\right)\right)+1.$ $$

However, the dimension cannot exceed $d$, so it can only increase at most $d$ times. This argument holds for any $h\in[H]$, and thus, the total number of times $\mathfrak{E}^{{\rm{span}}}_{t}$ does not happen will not exceed $dH$.
∎

###### Lemma 16 .

For any $h\in[H]$, it holds that

$$ $\displaystyle\sum_{t=1}^{T}\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}$ $\displaystyle\leq d\sqrt{2T\log(T+1)}=:B_{\phi}^{{\rm{R}}},$ $\displaystyle\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\| \phi(s_{t,h},a_{t,h})\|_{\widehat{\Sigma}^{\dagger}_{t,h}}$ $\displaystyle\leq\gamma d\sqrt{2dT\log\left(2T\gamma^{2}\right)}=:B_{\phi}^{{ \rm{P}}}.$ $$

###### Proof of Lemma 16 .

We prove the two inequalities separately.

Proof of the first inequality.
For any $t\in[T]$ and $h\in[H]$, we have the following bound on the norm of features (Lemma 5):

$$ $\displaystyle\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}\leq\|\phi(s_{t,h},a _{t,h})\|_{\Lambda^{-1}}\leq\sqrt{d}.$ $$

Hence, by Cauchy-Schwartz, we have

$$ $\displaystyle\sum_{t=1}^{T}\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}$ $\displaystyle\leq\sqrt{T\cdot\sum_{t=1}^{T}\|\phi(s_{t,h},a_{t,h})\|^{2}_{ \Sigma_{t,h}^{-1}}}$ $\displaystyle=\sqrt{T\cdot\sum_{t=1}^{T}\min\left\{\|\phi(s_{t,h},a_{t,h})\|^{ 2}_{\Sigma_{t,h}^{-1}},\,d\right\}}$ $\displaystyle\leq\sqrt{Td\cdot\sum_{t=1}^{T}\min\left\{\|\phi(s_{t,h},a_{t,h}) \|^{2}_{\Sigma_{t,h}^{-1}},\,1\right\}}$ $\displaystyle\leq\sqrt{Td\cdot 2d\log(T+1)}$ (elliptical potential lemma, Lemma 21 ) $\displaystyle=d\sqrt{2T\log(T+1)}.$ $$

Proof of the second inequality.
We divide the rounds into $d$ consecutive blocks, in each of which the rank of $\widehat{\Sigma}_{t,h}$ remains the same. To be specific, let $t_{1},t_{2},\dots,t_{d},t_{d+1}$ be a sequence of integers such that for any $i\in[d]$ and any $t\in\{t_{i},t_{i+1},\dots,t_{i+1}-1\}$, we have $\mathrm{rank}(\widehat{\Sigma}_{t,h})=i$.

We will apply the elliptical potential lemma to each block separately. Now let’s fix $i\in[d]$ and consider the $i$-th block. Let the reduced eigen-decomposition of $\widehat{\Sigma}_{t_{i},h}$ be $\widehat{\Sigma}_{t_{i},h}=UDU^{\top}$ where $U\in\mathbb{R}^{d\times i}$ and $D\in\mathbb{R}^{i\times i}$. For each $t\in\{t_{i},t_{i+1},\dots,t_{i+1}-1\}$, since $\phi(s_{t,h},a_{t,h})$ is in the span of $\widehat{\Sigma}_{t,h}$ conditioning on $\mathfrak{E}^{{\rm{span}}}_{t}$, there exists a vector $x_{t}$ such that $\phi(s_{t,h},a_{t,h})=Ux_{t}$.

For any $t\in\{t_{i},t_{i+1},\dots,t_{i+1}-1\}$, we have

$$ $\displaystyle\|\phi(s_{t,h},a_{t,h})\|^{2}_{\widehat{\Sigma}^{\dagger}_{t,h}}$ $\displaystyle=\phi(s_{t,h},a_{t,h})^{\top}\widehat{\Sigma}^{\dagger}_{t,h}\phi (s_{t,h},a_{t,h})$ $\displaystyle=\phi(s_{t,h},a_{t,h})^{\top}\left(\widehat{\Sigma}_{t_{i},h}+ \sum_{j=t_{i}}^{t-1}\phi(s_{j,h},a_{j,h})\phi^{\top}(s_{j,h},a_{j,h})\right)^{ \dagger}\phi(s_{t,h},a_{t,h})$ $\displaystyle=x_{t}^{\top}U^{\top}\left(UDU^{\top}+\sum_{j=t_{i}}^{t-1}Ux_{j}x _{j}^{\top}U^{\top}\right)^{\dagger}Ux_{t}$ $\displaystyle=x_{t}^{\top}\left(D+\sum_{j=t_{i}}^{t-1}x_{j}x_{j}^{\top}\right) ^{-1}x_{t}.$ $$

Define $D_{t}=D+\sum_{j=t_{i}}^{t-1}x_{j}x_{j}^{\top}$.
Hence, we have

$$ $\displaystyle\sum_{t=t_{i}}^{t_{i+1}-1}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}} }_{t}\}\|\phi(s_{t,h},a_{t,h})\|_{\widehat{\Sigma}^{\dagger}_{t,h}}=\sum_{t=t_ {i}}^{t_{i+1}-1}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\|x_{t}\|_{D_{t} ^{-1}}.$ $$

By Assumption 4, the eigenvalues of $D$ are lower bounded by $1/\gamma^{2}$. And clearly, its eigenvalues are upper bounded by $t_{i}\leq T$. Therefore, we have

$$ $\displaystyle\sum_{t=t_{i}}^{t_{i+1}-1}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}} }_{t}\}\|x_{t}\|_{D_{t}^{-1}}$ $\displaystyle\leq\sqrt{T\cdot\sum_{t=t_{i}}^{t_{i+1}-1}{\mathbf{1}}\{\mathfrak {E}^{{\rm{span}}}_{t}\}\|x_{t}\|^{2}_{D_{t}^{-1}}}$ $\displaystyle=\sqrt{T\cdot\sum_{t=t_{i}}^{t_{i+1}-1}{\mathbf{1}}\{\mathfrak{E} ^{{\rm{span}}}_{t}\}\min\left\{\|x_{t}\|^{2}_{D_{t}^{-1}},\gamma^{2}\right\}}$ $\displaystyle\leq\gamma\sqrt{T\cdot\sum_{t=t_{i}}^{t_{i+1}-1}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{span}}}_{t}\}\min\left\{\|x_{t}\|^{2}_{D_{t}^{-1}},1\right\}}$ $\displaystyle\leq\gamma\sqrt{T\cdot 2d\log\left(T\gamma^{2}(1+1/d)\right)}$ (elliptical potential lemma, Lemma 21 ) $\displaystyle\leq\gamma\sqrt{T\cdot 2d\log\left(2T\gamma^{2}\right)}.$ $$

This finishes the summation of one block. Notice that we have $d$ such blocks, we complete the proof by multiplying the above by $d$.
∎

###### Lemma 14 (optimism with constant probability) .

###### Proof of Lemma 14 .

###### Lemma 15 .

###### Proof.

###### Lemma 16 .

###### Proof of Lemma 16 .

### B.4 Main Steps of the Proof

Let $\widetilde{V}_{t}(s_{t,1})$ denote an i.i.d. copy of $\overline{V}_{t}$ conditioned on initial state $s_{t,1}$ and ${\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}$ and ${\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}$ denote the counterparts of $\mathfrak{E}^{{\rm{optm}}}_{t}$ and $\mathfrak{E}^{{\rm{high}}}{}$ but for $\widetilde{V}_{t}(s_{t,1})$.

The proof starts with the following decomposition of the regret:

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\Big{(}V^{\star}(s_{t,1})- V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\Big{(} V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[{\mathbf{1}}\{(\mathfrak{E}^{{\rm{ high}}}{})^{{\complement}}\}\sum_{t=1}^{T}\Big{(}V^{\star}(s_{t,1})-V^{\pi_{t} }(s_{t,1})\Big{)}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{( \mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\Big{(}V^{\star}(s_{t,1})-V^{ \pi_{t}}(s_{t,1})\Big{)}\right]$ $$

We will later show that the second and third terms can be easily bounded separately by observing the following two fact: (1) the probability that $\mathfrak{E}^{{\rm{high}}}{}$ doesn’t hold is very small, and (2) the number of times $\mathfrak{E}^{{\rm{span}}}_{t}$ doesn’t hold is also small. Hence, it remains to bound the first term, which is the most challenging. The most of the proof below is devoted to bounding it.

As the first step, we will add some necessary event conditions to the first term, using the following lemma.

###### Lemma 17 (Adding necessary event conditions) .

It holds that

$$ $\displaystyle\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{high}}} {}\}\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\Big{(}V^{ \star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[\sum_{t=1}^{ T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{ \mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t} \cap\mathfrak{E}^{{\rm{high}}}{}\}\widetilde{V}_{t}(s_{t,1})-{\mathbf{1}}\{ \mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\cdot\Big{(}dHB_{V}+B^{{\rm{P}}}_{{ \rm{err}}}\gamma H+(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R}}}_{{\rm{err}}}) \cdot B_{\phi}^{{\rm{R}}}+dH^{2}+1\Big{)}$ $$

where the expectation $\mathop{\mathbb{E}}_{\widetilde{V}_{t}}$ is taken over the randomness of $\widetilde{V}_{t}$ (an i.i.d. copy of $\overline{V}_{t}$) only.

###### Proof of Lemma 17 .

We have

$$ $\displaystyle\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{high}}} {}\}\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\Big{(}V^{ \star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\left(V^{\star}(s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{ {\rm{span}}}_{t}\}V^{\pi_{t}}(s_{t,1})\right)\right]$ ( $V^{\star}$ is non-negative) Plugging the condition on ${\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}$ ( Lemma 14 ), we get $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[\min\{H, \widetilde{V}_{t}(s_{t,1})\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}V^{ \pi_{t}}(s_{t,1})\,\middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t} \right]\right]+B^{{\rm{P}}}_{{\rm{err}}}\gamma H$ We aim to add two event indicators, ${\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}$ and ${\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}$ , and thus split the whole thing into several terms: $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}(s_{t,1})-{\mathbf{ 1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}V^{\pi_{t}}(s_{t,1})\right)\,\middle|\,{ \widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{\mathbf {1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{\complement}\}\left(\min\{ H,\widetilde{V}_{t}(s_{t,1})\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}V ^{\pi_{t}}(s_{t,1})\right)\,\middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}} _{t}\right]\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{\mathbf {1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{\complement}\}\left(\min \{H,\widetilde{V}_{t}(s_{t,1})\}-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \}V^{\pi_{t}}(s_{t,1})\right)\,\middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm }}}_{t}\right]\right]$ $\displaystyle\quad+B^{{\rm{P}}}_{{\rm{err}}}\gamma H$ $\displaystyle=:\mathtt{T}_{1}+\mathtt{T}_{2}+\mathtt{T}_{3}+B^{{\rm{P}}}_{{\rm {err}}}\gamma H.$ $$

Below we bound each term separately.

Bounding $\mathtt{T}_{1}$.
To bound $\mathtt{T}_{1}$, we will first drop the conditioning event ${\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}$ to make things cleaner. To that end, we re-arange it in the following way

$$ $\displaystyle\mathtt{T}_{1}$ $\displaystyle=\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{high}} }{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[\underbrace{ {\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}(s_{t,1})-{\mathbf{ 1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right)+{\mathbf{1}}\{( \mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\cdot B_{V}}_{(*)}\,\middle|\,{ \widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{span}}}_{t}\}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \}(U_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1}))\,\middle|\,{\widetilde{\mathfrak{E}}}^ {{\rm{optm}}}_{t}\right]\right]$ $\displaystyle\quad-\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{(\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\cdot B_{V}\, \middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ $\displaystyle=:\mathtt{T}_{1.1}+\mathtt{T}_{1.2}+\mathtt{T}_{1.3}.$ $$

The reason we did this is that we want to make sure $(*)$ is non-negative, so we can drop the conditioning event ${\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}$. To see why it is non-negative, we consider two cases: first, if $\mathfrak{E}^{{\rm{span}}}_{t}$ holds, then we already have ${\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\}({\widetilde{V}_{t}}
(s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1}))\geq 0$ by definition of $U_{t}(s_{t,1})$;
second, if $\mathfrak{E}^{{\rm{span}}}_{t}$ does not hold, then we have ${\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{
\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1})+{\mathbf{1}}\{(
\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\cdot B_{V}\geq 0$ by Lemma 13.

Hence, for $\mathtt{T}_{1.1}$, we can drop the conditioning event using the following rule (for non-negative variable $X$):

$$ $\displaystyle\mathop{\mathbb{E}}[X\,|\,\mathfrak{E}]=\mathop{\mathbb{E}}[X \cdot{\mathbf{1}}\{\mathfrak{E}\}]/\operatorname{Pr}(\mathfrak{E})\leq\mathop{ \mathbb{E}}[X\}]/\operatorname{Pr}(\mathfrak{E})$ $$

and using Lemma 14 to get

$$ $\displaystyle\mathtt{T}_{1.1}$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[{\mathbf{1}} \{\mathfrak{E}^{{\rm{high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}( s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right)+{ \mathbf{1}}\{(\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\cdot B_{V}\right ]\right]$ $\displaystyle=\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{ V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{ \widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}(s_{t,1} )-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right)\right]\right]$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[{\mathbf{1 }}\{\mathfrak{E}^{{\rm{high}}}{}\}\sum_{t=1}^{T}{\mathbf{1}}\{(\mathfrak{E}^{{ \rm{span}}}_{t})^{\complement}\}\cdot B_{V}\right]$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[{\mathbf{1}} \{\mathfrak{E}^{{\rm{high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}( s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right) \right]\right]$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\cdot dHB_{V}$ ( Lemma 15 ) $$

For $\mathtt{T}_{1.2}$, we apply Lemma 12 to get

$$ $\displaystyle\mathtt{T}_{1.2}$ $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{span}}}_{t}\}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \}(\overline{V}_{t}(s_{t,1})-V^{\pi_{t}}(s_{t,1}))\,\middle|\,{\widetilde{ \mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ ( $\overline{V}_{t}\geq U_{t}$ conditioning on $\mathfrak{E}^{{\rm{high}}}{}$ ) $\displaystyle\leq B^{{\rm{P}}}_{{\rm{err}}}\gamma H+(B^{{\rm{R}}}_{{\rm{noise} }}+B^{{\rm{R}}}_{{\rm{err}}})\cdot B_{\phi}^{{\rm{R}}}.$ $$

We simply upper bound $\mathtt{T}_{1.3}$ by zero. Plugging all these upper bounds back, we obtain

$$ $\displaystyle\mathtt{T}_{1}$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[{\mathbf{1}} \{\mathfrak{E}^{{\rm{high}}}{}\}\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\left({\widetilde{V}_{t}}( s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right) \right]\right]$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\cdot dHB_{V}+B^{{\rm{P}}}_{{\rm{ err}}}\gamma H+(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot B_ {\phi}^{{\rm{R}}}$ $\displaystyle=\frac{1}{\Gamma^{2}(-1)}\mathop{\mathbb{E}}\left[\sum_{t=1}^{T} \ \mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{ \mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t} \cap\mathfrak{E}^{{\rm{high}}}{}\}\widetilde{V}_{t}(s_{t,1})-{\mathbf{1}}\{ \mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+\frac{1}{\Gamma^{2}(-1)}\cdot dHB_{V}+B^{{\rm{P}}}_{{\rm{ err}}}\gamma H+(B^{{\rm{R}}}_{{\rm{noise}}}+B^{{\rm{R}}}_{{\rm{err}}})\cdot B_ {\phi}^{{\rm{R}}}$ $$

This is the final bound of $\mathtt{T}_{1}$ we need. Next, we go back to bound $\mathtt{T}_{2}$ and $\mathtt{T}_{3}$.

Bounding $\mathtt{T}_{2}$. We upper bound the value function inside the expectation by $H$ and obtain

$$ $\displaystyle\mathtt{T}_{2}$ $\displaystyle\leq H\cdot\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{ \rm{high}}}{}\}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{\complement}\}\, \middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ $\displaystyle\leq H\cdot\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb {E}}_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{ high}}}{})^{\complement}\}\,\middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}} _{t}\right]\right]$ (dropping $\mathfrak{E}^{{\rm{high}}}{}$ ) $\displaystyle=H\cdot\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\operatorname{Pr} \left(({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{\complement}\cap{ \widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right)/\operatorname{Pr}\left({ \widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right)\right]$ $\displaystyle\leq\frac{HT}{\Gamma^{2}(-1)}\cdot\operatorname{Pr}\left(( \mathfrak{E}^{{\rm{high}}})^{\complement}\right)$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}.$ ( Lemma 8 ) $$

Bounding $\mathtt{T}_{3}$. Similar, we upper bound the value function inside the expectation by $H$ and obtain

$$ $\displaystyle\mathtt{T}_{3}$ $\displaystyle\leq H\cdot\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{ \rm{high}}}{}\}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\widetilde{V}_{t}}\left[{ \mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{\complement}\}\, \middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\right]\right]$ $\displaystyle\leq H\cdot\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb {E}}_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{ span}}}_{t})^{\complement}\}\,\middle|\,{\widetilde{\mathfrak{E}}}^{{\rm{optm} }}_{t}\right]\right]$ (dropping $\mathfrak{E}^{{\rm{high}}}{}$ ) $\displaystyle=H\cdot\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}} _{\widetilde{V}_{t}}\left[{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span }}}_{t})^{\complement}\cap{\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t}\}\right ]/\operatorname{Pr}({\widetilde{\mathfrak{E}}}^{{\rm{optm}}}_{t})\right]$ $\displaystyle\leq H\cdot\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb {E}}_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{ span}}}_{t})^{\complement}\}\right]/\operatorname{Pr}({\widetilde{\mathfrak{E} }}^{{\rm{optm}}}_{t})\right]$ $\displaystyle\leq\frac{H}{\Gamma^{2}(-1)}\cdot\mathop{\mathbb{E}}\left[\sum_{t =1}^{T}{\mathbf{1}}\{(\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\right]$ (tower rule) $\displaystyle\leq\frac{dH^{2}}{\Gamma^{2}(-1)}$ ( Lemma 15 ) $$

Plugging all these back, we conclude the proof.
∎

The following lemma refines the event conditions established in Lemma 17 to make the whole thing more manageable.

###### Lemma 18 (Refining event conditions) .

It holds that

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high} }}{}\}\widetilde{V}_{t}(s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \cap\mathfrak{E}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{} \cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_ {\widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}} }{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1} )-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+dHB_{V}+2B_{V}/H.$ $$

###### Proof of Lemma 18 .

We start with refining the event conditions on the first term. We remove unneeded events by splitting the first term into two parts:

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high} }}{}\}\widetilde{V}_{t}(s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \cap\mathfrak{E}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{} \cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle=\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1}) -{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \cap{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{ {\rm{span}}}_{t}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad-\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E} }_{\widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high }}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\cap(\mathfrak{E}^{{\rm{ high}}})^{\complement}\}\widetilde{V}_{t}(s_{t,1})\right]\right]$ $$

Here, using Lemma 13, the last term can be bounded by

$$ $\displaystyle-\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\cap(\mathfrak{E}^{{\rm{high }}})^{\complement}\}\widetilde{V}_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ {\mathbf{1}}\{( \mathfrak{E}^{{\rm{high}}})^{\complement}\}B_{V}\right]\leq B_{V}/H$ $$

where we used Lemma 8 in the last inequality.

Now we seek to remove unneeded event conditions on $U_{t}$ as well. We notice the following decomposition

$$ $\displaystyle{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{ \rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{}\cap{\widetilde{ \mathfrak{E}}}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})$ $\displaystyle\geq{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^ {{\rm{high}}}{}\}U_{t}(s_{t,1})$ $\displaystyle\quad-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E }^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{\complement }\}U_{t}(s_{t,1})$ $\displaystyle\quad-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E }^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t})^{ \complement}\}U_{t}(s_{t,1}).$ $$

Plugging this back, we obtain

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high} }}{}\}\widetilde{V}_{t}(s_{t,1})-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t} \cap\mathfrak{E}^{{\rm{high}}}{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{high}}}{} \cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_ {\widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}} }{}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1} )-{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_ {\widetilde{V}_{t}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap \mathfrak{E}^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{ \complement}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_ {\widetilde{V}_{t}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap \mathfrak{E}^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}) ^{\complement}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\quad+B_{V}/H$ $$

The first term is exactly what we want. Now we bound the middle two terms separately below:

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap \mathfrak{E}^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{ \complement}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap \mathfrak{E}^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{high}}}{})^{ \complement}\}B_{V}\right]\right]$ ( Lemma 13 ) $\displaystyle\leq T\cdot\operatorname{Pr}(({\widetilde{\mathfrak{E}}}^{{\rm{ high}}}{})^{\complement})B_{V}$ $\displaystyle\leq B_{V}/H$ ( Lemma 8 ) $$

and for the other term we also have

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap \mathfrak{E}^{{\rm{high}}}{}\cap({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}) ^{\complement}\}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\mathop{\mathbb{E}}_{ \widetilde{V}_{t}}[{\mathbf{1}}\{({\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t} )^{\complement}\}]B_{V}\right]$ ( Lemma 13 ) $\displaystyle=B_{V}\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{( \mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\right]$ (tower rule) $\displaystyle\leq dHB_{V}.$ ( Lemma 15 ) $$

Hence, putting all together, we complete the proof.
∎

The following lemma provides a final bound for the first term in Lemma 18.

###### Lemma 19 (Final bound) .

It holds that

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1}) -{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle\leq 2HB^{{\rm{P}}}_{{\rm{err}}}B_{\phi}^{{\rm{P}}}+2(B^{{\rm{R}} }_{{\rm{err}}}+B^{{\rm{R}}}_{{\rm{noise}}})\cdot HB_{\phi}^{{\rm{R}}}.$ $$

###### Proof of Lemma 19 .

By tower rule, we have

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\ \mathop{\mathbb{E}}_{ \widetilde{V}_{t}}\left[{\mathbf{1}}\{{\widetilde{\mathfrak{E}}}^{{\rm{high}}} {}\cap{\widetilde{\mathfrak{E}}}^{{\rm{span}}}_{t}\}\widetilde{V}_{t}(s_{t,1}) -{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \}U_{t}(s_{t,1})\right]\right]$ $\displaystyle=\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E }^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\overline{V}_{t}(s_{t,1}) -{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\cap\mathfrak{E}^{{\rm{high}}}{} \}U_{t}(s_{t,1})\right]$ We plug in the result in Lemma 11 and get $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \left\langle\widehat{\theta}_{t,h}-\mathcal{T}(\overline{\theta}_{t,h+1}+ \overline{\omega}_{t,h+1}),\phi(s_{t,h},a_{t,h})\right\rangle\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \left\langle\mathcal{T}(\underline{\overline{\theta}}_{t,h+1}+\underline{ \overline{\omega}}_{t,h+1})-\underline{\widehat{\theta}}_{t,h},\phi(s_{t,h},a_ {t,h})\right\rangle\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \left\langle\overline{\omega}_{t,h}-\underline{\overline{\omega}}_{t,h},\phi(s _{t,h},a_{t,h})\right\rangle\right]$ Applying Cauchy-Schwartz inequality to each term yields $\displaystyle\leq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \left\|\widehat{\theta}_{t,h}-\mathcal{T}(\overline{\theta}_{t,h+1}+\overline{ \omega}_{t,h+1})\right\|_{\widehat{\Sigma}_{t,h}}\left\|\phi(s_{t,h},a_{t,h}) \right\|_{\widehat{\Sigma}^{\dagger}_{t,h}}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \left\|\mathcal{T}(\underline{\overline{\theta}}_{t,h+1}+\underline{\overline{ \omega}}_{t,h+1})-\underline{\widehat{\theta}}_{t,h}\right\|_{\widehat{\Sigma} _{t,h}}\left\|\phi(s_{t,h},a_{t,h})\right\|_{\widehat{\Sigma}^{\dagger}_{t,h}}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{ \mathfrak{E}^{{\rm{high}}}{}\cap\mathfrak{E}^{{\rm{span}}}_{t}\}\sum_{h=1}^{H} \Big{(}\|\overline{\omega}_{t,h}-\omega^{\star}_{h}\|_{\Sigma_{t,h}}+\|\omega^ {\star}_{h}-\underline{\overline{\omega}}_{t,h}\|_{\Sigma_{t,h}}\Big{)}\|\phi( s_{t,h},a_{t,h})\|_{\Sigma_{t,h}^{-1}}\right]$ $$

The first two terms can be bounded by $HB^{{\rm{P}}}_{{\rm{err}}}B_{\phi}^{{\rm{P}}}$ using Lemmas 7 and 16. For the last term, conditioning on $\mathfrak{E}^{{\rm{high}}}$, we have

$$ $\displaystyle\|\overline{\omega}_{t,h}-\omega^{\star}_{h}\|_{\Sigma_{t,h}}$ $\displaystyle\leq\|\overline{\omega}_{t,h}-\widehat{\omega}_{t,h}\|_{\Sigma_{t ,h}}+\|\widehat{\omega}_{t,h}-\omega^{\star}_{h}\|_{\Sigma_{t,h}}\leq B^{{\rm{ R}}}_{{\rm{err}}}+B^{{\rm{R}}}_{{\rm{noise}}}$ $$

and similarly for $\|\omega^{\star}_{h}-\underline{\overline{\omega}}_{t,h}\|_{\Sigma_{t,h}}$. Also, applying Lemma 16, we have

$$ $\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\|\phi(s_{t,h},a_{t,h})\|_{\Sigma_{t, h}^{-1}}\leq HB_{\phi}^{{\rm{R}}}.$ $$

Inserting all these back, we get the upper bound of

$$ $\displaystyle 2HB^{{\rm{P}}}_{{\rm{err}}}B_{\phi}^{{\rm{P}}}+2(B^{{\rm{R}}}_{{ \rm{err}}}+B^{{\rm{R}}}_{{\rm{noise}}})\cdot HB_{\phi}^{{\rm{R}}}.$ $$

Hence, we complete the proof.
∎

###### Proof of Theorem 6 .

We have

$$ $\displaystyle\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\Big{(}V^{\star}(s_{t,1})- V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\leq\mathop{\mathbb{E}}\left[{\mathbf{1}}\{\mathfrak{E}^{{\rm{ high}}}{}\}\sum_{t=1}^{T}{\mathbf{1}}\{\mathfrak{E}^{{\rm{span}}}_{t}\}\Big{(} V^{\star}(s_{t,1})-V^{\pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[{\mathbf{1}}\{(\mathfrak{E}^{{\rm{ high}}}{})^{{\complement}}\}\sum_{t=1}^{T}\Big{(}V^{\star}(s_{t,1})-V^{\pi_{t} }(s_{t,1})\Big{)}\right]$ $\displaystyle\quad+\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}{\mathbf{1}}\{( \mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\Big{(}V^{\star}(s_{t,1})-V^{ \pi_{t}}(s_{t,1})\Big{)}\right]$ $\displaystyle=:\mathtt{T}_{\rm{A}}+\mathtt{T}_{\rm{B}}+\mathtt{T}_{\rm{C}}.$ $$

For $\mathtt{T}_{\rm{A}}$, by Lemmas 17, 18 and 19 and re-arranging the results, we have

$$ $\displaystyle\mathtt{T}_{\rm{A}}$ $\displaystyle\leq\frac{1}{\Gamma^{2}(-1)}\cdot\Big{(}2B_{V}(dH+1/H)+HB^{{\rm{P }}}_{{\rm{err}}}\gamma+dH^{2}+1+(B^{{\rm{R}}}_{{\rm{err}}}+B^{{\rm{R}}}_{{\rm{ noise}}})(2H+1)B_{\phi}^{{\rm{R}}}+2HB^{{\rm{P}}}_{{\rm{err}}}B_{\phi}^{{\rm{P }}}\Big{)}$ $\displaystyle=\widetilde{O}\bigg{(}d^{5/2}H^{5/2}+d^{2}H^{3/2}\sqrt{T}+ \varepsilon_{1}\gamma\Big{(}dH^{2}+d^{3/2}H\sqrt{T}\Big{)}$ $\displaystyle\qquad\quad+\sqrt{\varepsilon_{\rm{B}}}\Big{(}d^{2}H^{5/2}\sqrt{T }+d^{3/2}H^{3/2}T\Big{)}+\varepsilon_{\rm{B}}\gamma\Big{(}dH^{2}\sqrt{T}+d^{3/ 2}HT\Big{)}\bigg{)}$ $$

For $\mathtt{T}_{\rm{B}}$, by Lemma 8, we have

$$ $\displaystyle\mathtt{T}_{\rm{B}}\leq HT\cdot\operatorname{Pr}\left((\mathfrak{ E}^{{\rm{high}}}{})^{{\complement}}\right)\leq 1.$ $$

For $\mathtt{T}_{\rm{C}}$, by Lemma 15, we have

$$ $\displaystyle{\texttt{T}}_{\text{C}}\leq H\cdot\mathop{\mathbb{E}}\left[\sum_{ t=1}^{T}{\mathbf{1}}\{(\mathfrak{E}^{{\rm{span}}}_{t})^{\complement}\}\right] \leq dH^{2}.$ $$

Putting everything together, we complete the proof.
∎

###### Lemma 17 (Adding necessary event conditions) .

###### Proof of Lemma 17 .

###### Lemma 18 (Refining event conditions) .

###### Proof of Lemma 18 .

###### Lemma 19 (Final bound) .

###### Proof of Lemma 19 .

###### Proof of Theorem 6 .

## Appendix C Supporting Lemmas

###### Lemma 20 (Gaussian concentration) .

(Abeille and Lazaric, )
Let $x\sim\mathcal{N}\left(0,c\Sigma^{-1}\right)$ for $c\in\mathbb{R}^{+}$and $\Sigma$ a positive definite matrix. Then, for any $\delta>0$, we have $\operatorname{Pr}\left(\|x\|_{\Sigma}>\sqrt{2cd\log(2d/\delta)}\right)\leq\delta$

###### Lemma 21 (Elliptical potential lemma) .

Assume that $X\subseteq\{x:\|x\|_{2}\leq 1\}$ is compact and ${\rm{span}}(X)=\mathbb{R}^{d}$. Let $x_{1},\dots,x_{T}\in X$ be a sequence of vectors, $\Sigma_{1}$ be a positive definite matrix with each eigenvalue bounded within the range of $[a,b]$ for some $a,b>0$, and $\Sigma_{t+1}=\Sigma_{t}+x_{t}x_{t}^{\top}$. Then, we have

$$ $\displaystyle\sum_{t=1}^{T}\min\left\{1,x_{t}^{\top}\Sigma_{t}^{-1}x_{t}\right \}\leq 2d\log\left(\frac{b}{a}+\frac{T}{ad}\right).$ $$

Furthermore, if $\Sigma_{1}$ is constructed via optimal design, i.e., $\Sigma_{1}=\mathop{\mathbb{E}}_{x\sim\rho}xx^{\top}$ where $\rho\in\Delta(X)$ is an optimal design over $X$, then we have

$$ $\displaystyle\sum_{t=1}^{T}\min\left\{1,x_{t}^{\top}\Sigma_{t}^{-1}x_{t}\right \}\leq 2d\log\left(T+1\right).$ $$

###### Proof of Lemma 21 .

First we claim that

$$ $\min\left\{1,x_{t}^{\top}\Sigma_{t}^{-1}x_{t}\right\}\leq 2x_{t}^{\top}\Sigma_ {t+1}^{-1}x_{t}$ (14) $$

To show this, we use Sherman-Morrison-Woodbury formula (Bhatia, ) for rank-one updates to a matrix inverse:

$$ $\displaystyle x_{t}^{\top}\Sigma_{t+1}^{-1}x_{t}$ $\displaystyle=x_{t}^{\top}\left(\Sigma_{t}+x_{t}x_{t}^{\top}\right)^{-1}x_{t}= x_{t}^{\top}\left(\Sigma_{t}^{-1}-\frac{\Sigma_{t}^{-1}x_{t}x_{t}^{\top}\Sigma _{t}^{-1}}{1+\left\|x_{t}\right\|_{\Sigma_{t}^{-1}}^{2}}\right)x_{t}=\left\|x_ {t}\right\|_{\Sigma_{t}^{-1}}^{2}-\frac{\left\|x_{t}\right\|_{\Sigma_{t}^{-1}} ^{4}}{1+\left\|x_{t}\right\|_{\Sigma_{t}^{-1}}^{2}}=\frac{\left\|x_{t}\right\| _{\Sigma_{t}^{-1}}^{2}}{1+\left\|x_{t}\right\|_{\Sigma_{t}^{-1}}^{2}}.$ $$

Now let us consider two cases for the right-hand side of the above:

- Case 1
: $x_{t}^{\top}\Sigma_{t}^{-1}x_{t}\leq 1$. Then, we can lower bound the right-hand side above by $\left\|x_{t}\right\|_{\Sigma_{t}^{-1}}^{2}/2$.
- Case 2
: $x_{t}^{\top}\Sigma_{t}^{-1}x_{t}\geq 1$. Then the right-hand side above is directly at least $1/2$ since the function $x/(1+x)$ is increasing in $x$.

Hence, in both cases, we have $x_{t}^{\top}\Sigma_{t+1}^{-1}x_{t}\geq\min\left\{1,x_{t}^{\top}\Sigma_{t}^{-1}
x_{t}\right\}/2$, which finishes the proof of (14).

Since the log-determinant function is concave, we can obtain that $\log\det\left(\Sigma_{t}\right)-\log\det\Sigma_{t+1}\leq\operatorname{tr}\left
(\Sigma_{t+1}^{-1}\left(\Sigma_{t}-\Sigma_{t+1}\right)\right)$ via first-order Taylor approximation. This gives us the following

$$ $\sum_{t=1}^{T}x_{t}^{\top}\Sigma_{t+1}^{-1}x_{t}=\sum_{t=1}^{T}\operatorname{ tr}\left(\Sigma_{t+1}^{-1}\left(\Sigma_{t+1}-\Sigma_{t}\right)\right)\leq\sum_ {t=1}^{T}\left(\log\det\Sigma_{t+1}-\log\det\Sigma_{t}\right)=\log\left(\frac{ \det\Sigma_{T+1}}{\det\Sigma_{1}}\right)$ $$

where the last step follows from telescoping. Since each eigenvalue of $\Sigma_{1}$ is lower bounded by $a$, we have $\det\Sigma_{1}\geq a^{d}$. Towards an upper bound of $\det\Sigma_{T+1}=\det(\Sigma_{1}+\sum_{t=1}^{T}x_{t}x_{t}^{\top})$, let $(\lambda_{1},\dots,\lambda_{d})$ denote the eigenvalues of $\sum_{t=1}^{T}x_{t}x_{t}^{\top}$, and then we have

$$ $\displaystyle\det\left(\Sigma_{1}+\sum_{t=1}^{T}x_{t}x_{t}^{\top}\right)\leq \prod_{i=1}^{d}\left(b+\lambda_{i}\right)\leq\left(\frac{1}{d}\sum_{i=1}^{d} \left(b+\lambda_{i}\right)\right)^{d}\leq\left(b+\frac{1}{d}\text{tr}\left( \sum_{t=1}^{T}x_{t}x_{t}^{\top}\right)\right)^{d}\leq\left(b+\frac{T}{d}\right )^{d}$ $$

Here, the first step is Weyl’s inequality, the second step is AM-GM inequality, and the last step is because the trace is bounded by $T$. Plugging this upper bound back, we have

$$ $\displaystyle\log\left(\frac{\det\Sigma_{T+1}}{\det\Sigma_{1}}\right)\leq d \log\left(\frac{b}{a}+\frac{T}{ad}\right).$ $$

This completes the proof of the first statement.

For the case where $\Sigma_{1}$ is constructed via optimal design, we can rewrite $\Sigma_{T+1}$ in the following way:

$$ $\displaystyle\Sigma_{T+1}=\mathop{\mathbb{E}}_{x\sim\rho}xx^{\top}+\sum_{t=1}^ {T}x_{t}x_{t}^{\top}=(T+1)\underbrace{\left(\frac{1}{1+T}\cdot\mathop{\mathbb{ E}}_{x\sim\rho}xx^{\top}+\sum_{t=1}^{T}\frac{1}{1+T}\cdot x_{t}x_{t}^{\top} \right)}_{(*)}=:(T+1)\mathop{\mathbb{E}}_{x\sim\rho^{\prime}}xx^{\top}$ $$

where we consider $(*)$ as an expectation of $xx^{\top}$ over a new distribution that we denote by $\rho^{\prime}$. Recall that $\Sigma_{1}$ is constructed via optimal design, which implies $\det\Sigma_{1}\geq\det\mathop{\mathbb{E}}_{x\sim\rho^{\prime}}xx^{\top}$ (Lemma 23). This gives us

$$ $\displaystyle\log\left(\frac{\det\Sigma_{T+1}}{\det\Sigma_{1}}\right)=\log \left(\frac{(T+1)^{d}\det\mathop{\mathbb{E}}_{x\sim\rho^{\prime}}xx^{\top}}{ \det\Sigma_{1}}\right)\leq\log\left(\left(T+1\right)^{d}\right)=d\log\left(T+1 \right).$ $$

This completes the proof.
∎

The following inequality is well-known; we use the version stated in Zhu and Nowak ().

###### Lemma 22 (Freedman’s inequality) .

Let $\left\{X_{t}\right\}_{t\leq T}$ be a real-valued martingale different sequence adapted to the filtration $\mathcal{F}_{t}$, and let $\operatorname{\mathbb{E}}_{t}\left[\cdot\right]\coloneqq\operatorname{\mathbb{
E}}\left[\cdot\mid\mathcal{F}_{t-1}\right]$. If $\lvert X_{t}\rvert\leq B$ almost surely, then for any $\eta\in(0,1/B)$, the following holds with probability at least $1-\delta$:

$$ $\displaystyle\sum_{t=1}^{T}X_{t}\leq\eta\sum_{t=1}^{T}\operatorname{\mathbb{E} }_{t}[X_{t}^{2}]+\frac{B\log(1/\delta)}{\eta}.$ $$

###### Lemma 23 .

(Lattimore and Szepesvári, )
Assume that $\Phi\subseteq\mathbb{R}^{d}$ is compact and ${\rm{span}}(\Phi)=\mathbb{R}^{d}$.
For a distribution $\rho$ over $\Phi$, define $\Lambda(\rho)=\sum_{\phi\in\Phi}\rho(\phi)\phi\phi^{\top}$ and $g(\rho)=\max_{\phi\in\Phi}\|\phi\|_{\Lambda(\rho)^{-1}}^{2}$.
Then, the following are equivalent:

- •
$\rho$ is a minimizer of $g$.
- •
$\rho$ is a maximizer of $f(\rho)\coloneqq\log\det\Lambda(\rho)$.
- •
$g(\rho)=d$.

Furthermore, there exists a minimizer $\rho$ of $g$ such that $|{\rm{supp}}(\rho)|\leq d(d+1)/2$.

Below we show that the Cauchy-Schwarz inequality is still valid when the matrix is not invertible under some conditions. We start with the following lemma.

###### Lemma 24 .

Let $A$ be a positive semi-definite matrix. Let $B$ be a square root of $A$, i.e., $A=BB^{\top}$. Then ${\rm{range}}(A)={\rm{range}}(B)$.

###### Proof of Lemma 24 .

We first show that ${\rm{range}}(A)\subseteq{\rm{range}}(B)$. To see this, for any $y\in{\rm{range}}(A)$, there exists $x$ such that $y=Ax=BB^{\top}x=B(B^{\top}x)$. Hence $y\in{\rm{range}}(B)$. Next, we show that ${\rm{range}}(B)\subseteq{\rm{range}}(A)$. To see this, for any $y\in{\rm{range}}(B)$, there exists $x$ such that $y=Bx$. Let $x=x_{0}+x_{1}$ where $x_{0}\in{\rm{null}}(B)$ and $x_{1}\in{\rm{rowspace}}(B)$. Then, $y=Bx=Bx_{1}$. Since $x_{1}\in{\rm{rowspace}}(B)$, there exists $z$ such that $x_{1}=B^{\top}z$. Thus, $y=Bx_{1}=BB^{\top}z=Az$. Hence, $y\in{\rm{range}}(A)$.
∎

###### Lemma 25 (Cauchy-Schwarz under pseudo-inverse) .

Let $\Sigma$ be a positive semi-definite matrix (that is unnecessarily invertible). Then, for any $x\in{\rm{range}}(\Sigma)$ and any $y\in\mathbb{R}^{d}$, we have

$$ $\displaystyle x^{\top}y\leq\|x\|_{\Sigma^{\dagger}}\|y\|_{\Sigma}.$ $$

###### Proof of Lemma 25 .

Let $B$ denote the square root of $\Sigma$ and force $B$ to be positive semi-definite. One can verify that $BB^{\dagger}$ is the orthogonal projection matrix onto ${\rm{range}}(B)$, and hence, ${\rm{range}}(\Sigma)$ (recalling that ${\rm{range}}(B)={\rm{range}}(\Sigma)$ by Lemma 24). Therefore, for any $x\in{\rm{range}}(\Sigma)$, we have $BB^{\dagger}x=x$. Then, we have

$$ $\displaystyle x^{\top}y=x^{\top}B^{\dagger}By\leq\sqrt{x^{\top}B^{\dagger}B^{ \dagger}x}\sqrt{y^{\top}BBy}=\|x\|_{\Sigma^{\dagger}}\|y\|_{\Sigma}$ $$

where the inequality follows from the standard Cauchy-Schwarz inequality.
∎

###### Lemma 26 (Invariance under projection) .

Let $\Sigma\in\mathbb{R}^{d\times d}$ be a positive semi-definite matrix of rank $r$.
For any vector $\phi\in\mathbb{R}^{d}$, we have $\|\phi\|_{\Sigma^{\dagger}}=\|P\phi\|_{\Sigma^{\dagger}}$ where $P$ is the projection onto the range of $\Sigma$.

###### Proof of Lemma 26 .

Assume the eigen-decomposition of $\Sigma=U\Lambda U^{\top}$, so $\Sigma^{\dagger}=U\Lambda^{\dagger}U^{\top}$. Without loss of generality, we assume $\Lambda$ has all its non-zero elements at the front and zero elements at the back on the diagonal. Denote $U_{r}$ as the matrix obtained by replacing the last $n-r$ columns of $U$ by 0. Note that the first $r$ columns of $U$ is in the range of $\Sigma$, so we must have $PU=U_{r}$. Then, we have the following

$$ $\displaystyle\|P\phi\|_{\Sigma^{\dagger}}^{2}$ $\displaystyle=\phi^{\top}P^{\top}\Sigma^{\dagger}P\phi=\phi^{\top}P^{\top}U \Lambda^{\dagger}U^{\top}P\phi=\phi^{\top}P^{\top}U_{r}\Lambda^{\dagger}U_{r}^ {\top}P\phi=\phi^{\top}U_{r}\Lambda^{\dagger}U_{r}^{\top}\phi=\phi^{\top}U \Lambda^{\dagger}U^{\top}\phi=\|\phi\|_{\Sigma^{\dagger}}^{2}.$ $$

This completes the proof.
∎

###### Lemma 20 (Gaussian concentration) .

###### Lemma 21 (Elliptical potential lemma) .

###### Proof of Lemma 21 .

###### Lemma 22 (Freedman’s inequality) .

###### Lemma 23 .

###### Lemma 24 .

###### Proof of Lemma 24 .

###### Lemma 25 (Cauchy-Schwarz under pseudo-inverse) .

###### Proof of Lemma 25 .

###### Lemma 26 (Invariance under projection) .

###### Proof of Lemma 26 .

### C.1 Pseudo Dimension and Covering Number

###### Definition 6 ( $\ell_{1}$ -Covering number) .

(Definition 4 of Modi et al. ())
Given a hypothesis class $\mathcal{H}\subseteq(\mathcal{Z}\mapsto\mathbb{R})$ and $Z^{n}=(z_{1},\dots,z_{n})\in\mathcal{Z}^{n}$, $\varepsilon>0$, define $\mathcal{N}(\varepsilon,\mathcal{H},Z^{n})$ as the minimum cardinality of a set $\mathcal{C}\subseteq\mathcal{H}$, such that for any $h\in\mathcal{H}$, there exists $h^{\prime}\in\mathcal{C}$ such that $\sum_{i=1}^{n}|h(z_{i})-h^{\prime}(z_{i})|/n\leq\varepsilon$. We define $\mathcal{N}(\varepsilon,\mathcal{H},n)=\max_{Z^{n}\in\mathcal{Z}^{n}}\mathcal{
N}(\varepsilon,\mathcal{H},Z^{n})$.

Below we define the pseudo-dimension (Haussler, ; Modi et al., ).

###### Definition 7 (VC-dimension) .

For hypothesis class $\mathcal{H}\subseteq(\mathcal{X}\rightarrow\{0,1\})$, we define its VC-dimension $\operatorname{VC-dim}(\mathcal{H})$ as the maximal cardinality of a set $X=\left\{x_{1},\ldots,x_{|X|}\right\}\subseteq\mathcal{X}$ that satisfies $\left|\mathcal{H}_{X}\right|=2^{|X|}$ (or $X$ is shattered by $\mathcal{H})$, where $\mathcal{H}_{X}$ is the restriction of $\mathcal{H}$ to $X$, i.e., $\left\{\left(h\left(x_{1}\right),\ldots,h\left(x_{|X|}\right)\right):h\in
\mathcal{H}\right\}$.

###### Definition 8 (Pseudo-dimension) .

For hypothesis class $\mathcal{H}\subseteq(\mathcal{X}\rightarrow\mathbb{R})$, we define its pseudo dimension $\operatorname{Pdim}(\mathcal{H})$ as $\operatorname{Pdim}(\mathcal{H})=\operatorname{VCdim}\left(\mathcal{H}^{+}\right)$, where $\mathcal{H}^{+}=\{(x,\xi)\mapsto\mathbf{1}[h(x)>\xi]:h\in\mathcal{H}\}\subseteq$ $(\mathcal{X}\times\mathbb{R}\rightarrow\{0,1\})$

The following lemma provides a bound on the covering number of a hypothesis class via pseudo dimension.

###### Lemma 27 .

(Corollary 42 of Modi et al. ())
Given a hypothesis class $\mathcal{H}\subseteq\mathcal{Z}\mapsto[a,b]$ with ${\rm{Pdim}}(\mathcal{H})\leq d$, then, for any $n$, we have

$$ $\mathcal{N}(\varepsilon,\mathcal{H},n)\leq\left(4e^{2}(b-a)/\varepsilon\right) ^{d}.$ $$

Note that the right-hand side is independent of $n$.

###### Definition 6 ( ℓ 1 subscript ℓ 1 \ell_{1} roman_ℓ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT -Covering number) .

###### Definition 7 (VC-dimension) .

###### Definition 8 (Pseudo-dimension) .

###### Lemma 27 .

## Appendix D Linear MDPs and LQRs imply Linear Bellman Completeness

It is already well known that linear Bellman completeness captures linear MDPs, as demonstrated in works such as Agarwal et al. (); Zanette et al. (). Here, we show why it also captures LQRs. We start with the definition.

###### Definition 9 (Linear Quadratic Regulator) .

A linear quadratic regulator (LQR) problem is defined by a tuple $(A,B,Q,R)$ where $A\in\mathbb{R}^{d\times d}$, $B\in\mathbb{R}^{d\times m}$, $Q\in\mathbb{R}^{d\times d}$, and $R\in\mathbb{R}^{m\times m}$. The objective is to find a policy $\pi$ that minimizes the following:

$$ $\displaystyle J(\pi)=\mathop{\mathbb{E}}\left[\sum_{h=1}^{H}x_{h}^{\top}Qx_{h} +u_{h}^{\top}Ru_{h}\right]$ $$

where $x_{t+1}=Ax_{h}+Bu_{h}+w_{h}$ where $w_{h}\sim\mathcal{N}(0,\sigma^{2}I)$.

When $R$ is positive definite, we can show that the optimal policy is linear in the state, i.e., $\pi^{\star}(x_{h})=K_{h}x_{h}$ for some matrix $K_{h}$. The proof can be found, for example, in Agarwal et al. (). This is enough for us to show that LQR is captured by linear Bellman completeness. We define the feature map to be the quadratic form, i.e.,

$$ $\displaystyle\phi(x,u)=\begin{bmatrix}{\rm{vec}}(xx^{\top})\\ {\rm{vec}}(uu^{\top})\\ {\rm{vec}}(xu^{\top})\\ 1\end{bmatrix}$ $$

where ${\rm{vec}}(\cdot)$ means the vectorization of a matrix.
Then, we need to show that, for any $x,u$ and any vector $\theta$, the following is a linear function of $x$ and $u$:

$$ $\displaystyle\mathop{\mathbb{E}}_{w\sim\mathcal{N}(0,\sigma^{2}I)}\Big{[}\min_ {u^{\prime}}\left\langle\phi(Ax+Bu+w,u^{\prime}),\,\theta\right\rangle\Big{]}.$ $$

Since the optimal policy is linear in the state, we can write $u^{\prime}=Kx$ for some matrix $K$. Then, the above is equivalent to

$$ $\displaystyle\mathop{\mathbb{E}}_{w\sim\mathcal{N}(0,\sigma^{2}I)}\Big{[}\left \langle\phi\big{(}Ax+Bu+w,K(Ax+Bu+w)\big{)},\,\theta\right\rangle\Big{]}.$ $$

We observe that the feature inside the expectation is a quadratic function of $x$ $u$, and $w$. In other words, there must exist a vector $\theta^{\prime}$ such that

$$ $\displaystyle\left\langle\phi\big{(}Ax+Bu+w,K(Ax+Bu+w)\big{)},\,\theta\right \rangle=\left\langle\begin{bmatrix}{\rm{vec}}(xx^{\top})\\ {\rm{vec}}(uu^{\top})\\ {\rm{vec}}(ww^{\top})\\ {\rm{vec}}(xu^{\top})\\ {\rm{vec}}(xw^{\top})\\ {\rm{vec}}(uw^{\top})\\ \end{bmatrix},\,\theta^{\prime}\right\rangle.$ $$

Since $w$ is sampled from isotropic Gaussian distribution, when taking the expectation, the cross terms ${\rm{vec}}(xw^{\top})$ and ${\rm{vec}}(uw^{\top})$ will vanish, and ${\rm{vec}}(ww^{\top})$ will be the constant vector ${\rm{vec}}(\sigma^{2}I)$. Therefore,
it simply becomes a quadratic function of $x$ and $u$. In other words, there exists a vector $\theta^{\prime\prime}$ such that

$$ $\displaystyle\mathop{\mathbb{E}}_{w\sim\mathcal{N}(0,\sigma^{2}I)}\Big{[}\left \langle\phi\big{(}Ax+Bu+w,K(Ax+Bu+w)\big{)},\,\theta\right\rangle\Big{]}=\left \langle\begin{bmatrix}{\rm{vec}}(xx^{\top})\\ {\rm{vec}}(uu^{\top})\\ {\rm{vec}}(xu^{\top})\\ 1\end{bmatrix},\,\theta^{\prime\prime}\right\rangle=\left\langle\phi(x,u),\, \theta^{\prime\prime}\right\rangle.$ $$

This is exactly what we want to show. We can also easily verify that the reward (cost) function is linear in the quadratic feature. Hence, LQR is captured by linear Bellman completeness.

###### Definition 9 (Linear Quadratic Regulator) .

## Appendix E Computationally Efficient Implementations for Optimization Oracles

The convex programming algorithm given in Algorithm 2 is due to Bertsimas and Vempala (). In the following, we provide an informal description of Algorithm 2 below but refer the reader to Bertsimas and Vempala () for the full details.

At an iteration $t\leq T$, Algorithm 2 stars with a set $\mathcal{D}_{t}$ which contains the set $\mathcal{K}$, and a set of $2N$ points $\mathcal{U}_{t}$ sampled (approximately) uniformly from $\mathcal{D}_{t}$ using the Sampler subroutine in Algorithm 3. It then uses the first $N$ samples from $\mathcal{U}_{t}$ to compute an approximate centroid $z_{t}$ of the set $\mathcal{D}_{t}$ in line 7; the remaining points from $\mathcal{U}_{t}$ are denoted by $\mathcal{V}_{t}$. It then queries the separation oracle $\mathcal{O}^{{\rm{sep}}}_{\mathcal{K}}$ at the point $z_{t}$. If $z_{t}\in\mathcal{K}$, then we terminate and return $z_{t}$. Otherwise, we use the separating hyperplane between $z_{t}$ and $\mathcal{K}$ to shrink the set $\mathcal{D}_{t}$ further into $\mathcal{D}_{t+1}$ in line 13. Finally, it calls Sampler again using the set of points $\mathcal{V}_{t}$ as a warm start to get $2N$ new (approximately) i.i.d. sample from $\mathcal{D}_{t+1}$ in line 14. Equipped with the sets $\mathcal{D}_{t+1}$ and $\mathcal{U}_{t+1}$, another iteration of the algorithm follows.

On receiving a convex set $\mathcal{D}$ and a set of points $\mathcal{V}$, the Sampler protocol in Algorithm 3 first refines $\mathcal{V}$ to $\mathcal{V}^{\prime}$ by disposing off any points $z\in\mathcal{V}$ that do not lie in $\mathcal{D}$. Then, it starts a random ball walk from the samples in $\mathcal{V}^{\prime}$: in order to update the current point $\widehat{z}$ we first sample a point $z^{\prime}$ uniformly from the ellipsoid $\widehat{z}+\eta\Lambda^{\nicefrac{{1}}{{2}}}\mathbb{B}_{d}(1)$ (where $\Lambda$ is defined using the points in $\mathcal{V}^{\prime}$) and then updates $\widehat{z}\leftarrow z^{\prime}$ if $z^{\prime}\in\mathcal{D}$. The analysis of Bertsimas and Vempala () shows that this ball walk mixes fast to a uniform distribution over the set $\mathcal{D}$.

Figure: Algorithm 2 Solving Convex Programs by Random Walks (Bertsimas and Vempala ())

Figure: Algorithm 3 Sampler used in Algorithm 2

## Appendix F Missing Details from Section 7.2

Figure: Algorithm 4 Computationally Efficient Implementation of $\mathcal{O}^{{\rm{sq}}}_{{\rm{apx}}}$ for Value Estimation

### F.1 Computationally Efficient Estimation of Reward Function (Eqn ( 2 ))

The convex set feasibility procedure of Bertsimas and Vempala () can also be used to estimate the parameters for the reward functions in (2) in Algorithm 1. Note that for any time $t$ and horizon $h\in[H]$, the objective in (1) is the optimization problem

$$ $\displaystyle\widehat{\omega}_{t,h}$ $\displaystyle\leftarrow\operatorname*{argmin}_{\omega\in\mathscr{O}(1)}\sum_{i =1}^{t-1}\Big{(}\left\langle\omega,\phi(s_{i,h},a_{i,h})\right\rangle-r_{i,h} \Big{)}^{2}.$ (16) $$

In the following, we provide a computationally efficient procedure, based off on Algorithm 2, to approximately solve the above squared loss minimization problem given a linear optimization oracle over the feature space (Assumption 6). Note that since $r_{i,h}\in[0,1]$, the constraint on the point $\omega$ implies that the objective value in (16) is at most $2$. Thus, we can solve the above optimization problem upto precision $\varepsilon$, by iterating over the set $\Delta\in\{0,\varepsilon,2\varepsilon,\dots,2-\varepsilon,2\}$ in order to solve the set feasibility problem

$$ $\displaystyle\mathcal{K}^{\Delta}_{\textsc{apx}}\vcentcolon={}\left\{\omega\in \mathbb{R}^{d}\leavevmode\nobreak\ \Bigg{\mid}{}\begin{matrix}&\sum_{i=1}^{t-1 }\left(\langle\omega,\phi(s_{i,h},a_{i,h})\rangle-r_{i,h}\right)^{2}\leq\Delta +\varepsilon\\ &\lvert\left\langle\omega,\phi(s,a)\right\rangle\rvert\leq 1+\varepsilon \leavevmode\nobreak\ \text{for all}\leavevmode\nobreak\ s,a\end{matrix}\right\}$ (17) $$

and stopping at the smallest point $\Delta$ for which $\mathcal{K}^{\Delta}_{\textsc{apx}}$ has a feasible solution. It is easy to see that for any $\Delta$, either $\mathcal{K}^{\Delta}_{\textsc{apx}}$ is empty or the shifted cube $\widehat{\omega}_{t,h}+\mathbb{R}_{\infty}(\varepsilon)\subseteq\mathcal{K}^{
\Delta}_{\textsc{apx}}$. Furthermore, under
Assumption 7 we also have that $\mathcal{K}^{\Delta}_{\textsc{apx}}\subseteq\mathbb{R}_{\infty}(R)$ for any $\Delta$. Thus, for any $\Delta$, whenever a feasible solution exists, the set $\mathcal{K}^{\Delta}_{\textsc{apx}}$ satisfies the prerequisites for Theorem 4, where recall that we can tolerate the parameter $R$ to be exponential in the dimension $d$ or the horizon $H$. Furthermore, a separation oracle $\mathcal{O}^{{\rm{sep}}}_{\mathcal{K}^{\Delta}_{\textsc{apx}}}$ can be easily implemented by using the linear optimization oracle $\mathcal{O}^{{\rm{lin}}}$ w.r.t. the feature space (Assumption 6) and by explicitly constructing a separation oracle for the ellipsoidal constraint

$$ $\displaystyle\sum_{i=1}^{t-1}\left(\langle\omega,\phi(s_{i,h},a_{i,h})\rangle- r_{i,h}\right)^{2}\leq\Delta+\varepsilon.$ $$

We provide the implementation of the above in Algorithm 5, which relies on Algorithm 2 for solving the corresponding set feasibility problems. The guarantee in Theorem 4 to find a feasible point in $\mathcal{K}^{\Delta}_{\textsc{apx}}$ (for each $\Delta$) gives the following guarantee on computational efficiency for Algorithm 5.

###### Theorem 7 .

Let $\varepsilon>0$, $\delta\in(0,1)$, and suppose Assumption 7 holds with some parameter $R>0$. Additionally, suppose Assumption 6 holds with the linear optimization oracle denoted by $\mathcal{O}^{{\rm{lin}}}$. Then, for any $t\in[T]$ and $h\in[H]$, Algorithm 5 returns a point $\widehat{\omega}_{t,h}$ that, with probability at least $1-\delta$, satisfies

$$ $\displaystyle\sum_{i=1}^{t-1}\left(\langle\widehat{\omega},\phi(s_{i,h},a_{i,h })\rangle-r_{i,h}\right)^{2}\leq\min_{\omega\in\mathscr{O}(1)}\sum_{i=1}^{t-1} \left(\langle\omega,\phi(s_{i,h},a_{i,h})\rangle-r_{i,h}\right)^{2}+ \varepsilon\qquad\text{and}\qquad\widehat{\omega}_{t,h}\in\mathscr{O}(1+ \varepsilon).$ $$

Furthermore, Algorithm 5 takes $O(\frac{d^{7}}{\varepsilon}\log(\frac{R}{\delta\varepsilon}))$ time in addition to $O(\frac{d}{\varepsilon}\log(\frac{THR}{\delta\varepsilon}))$ calls to $\mathcal{O}^{{\rm{lin}}}$.

Figure: Algorithm 5 Computationally Efficient Implementation of $\mathcal{O}^{{\rm{sq}}}_{{\rm{apx}}}$ for Reward Estimation

###### Theorem 7 .

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: -	Example 1 in Section 3.1 is confusing. First of all, is \mu(s_2) a typo in Line 195? It seems to me that Example 1 proves that, there exists a tabular MDP and a particular feature mapping, such that the norm of the ground-truth parameter has unbounded l2 norm. In other words, this example does not prove that, linear Bellman complete MDPs with unbounded ground-truth parameters is a strict superset of those with bounded ground-truth parameters, since it is still possible that the same MDP can be represented with a different set of features.
soundness: 4
strengths: -	This paper designs the first computationally and statistically efficient algorithm for linear Bellman complete MDPs with deterministic transitions, which serves as a solid step toward solving the long-standing open question about the statistical-computational gap in the Bellman complete setting.
-	This paper is well written, and the algorithm is straightforward and easy to understand. The technical proofs in the appendix is also well written and easy to follow.
-	This paper clearly discussed the limitations of prior works in the linear Bellman complete setting (Section 3.1 and 3.2). Although the idea of adding noise to the regression result is not new, applying this idea to the specific setting requires non-trivial analysis on the exponential blowup of the norm of the parameters, which is novel in this paper.
summary: This paper designs the first computationally and statistically efficient algorithm for linear Bellman complete MDPs with deterministic transitions. Instead of adding a quadratic exploration bonus and truncating the value function, this paper adds carefully designed random noises to the regression results so that it can (a) achieve optimism, and (b) prevent error amplification.
weaknesses: -	My major concern is the organization of this paper --- although the high-level ideas are discussed in detail, all the proofs, including the proof sketch, are deferred to the appendix. I encourage the authors to at least discuss how the key designs of the algorithm (e.g., adding noise to the null space of the current data) enable the regret analysis.
-	One of the major assumptions in this paper is that the transition is deterministic (Assumption 1). However, this assumption is not very well discussed in the paper. The only place where Assumption 1 is used is Lemma 10, which only computes the value decomposition. If I understand correctly, when the transition is not deterministic, a variant of Eq (10) still holds where one only needs to take an expectation w.r.t the randomness of the trajectory on the RHS. Therefore, it is unclear to me what is blocking the analysis from extending to MDPs with stochastic transitions.
-	In the proof sketch (line 885 in particular), the definition of U_t is deferred to Appendix C.2. However, without its definition, it is impossible to understand the proof outline in B.3.
-	Line 1662: typo in the displayed equation, mismatched parenthesis.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. The paper mentions that "Many efficient algorithms can be applied to find approximate D-optimal designs such as the Frank-Wolfe". I think this is the case when S,A are finite, but what if they are infinite? Is there any efficient algorithm?
2. It is not clear why constrained least squares regression, instead of an unconstrained one, is needed since there is no assumption on boundedness of the true parameters. Could you clarify?
3. Even though it acts only on the null space, it was not clear to me why the injected noise (ie \sigma_h) has to be exponential in H
4. Does the algorithm need to know that the MDP has deterministic transitions? In other words, if applied to a stochastic MDP, would the algorithm still make sense or would it break for some reason?
soundness: 3
strengths: 1. Designing RL algorithms with function approximation for large state-action spaces that are not only statistically efficient but also computationally efficient is an important open problem, and this paper makes a good step forward in this direction
2. The "span argument" is interesting and novel
3. Although I only quickly went through the proofs, all results seem sound
4. The paper is very well written: the problem and its technical challenges are well motivated from the very beginning, notation is clear, and the adopted techniques are well justified
5. The examples in 3.1 are interesting to motivate why bounded norm assumptions are unreasonable, and further motivate the paper's contributions
summary: The paper studies RL under linear Bellman completeness (a generalization of low-rank MDPs) and deterministic transition dynamics. It shows how to design the first algorithm that is both statistically and computationally efficient for this setting, and important open question given the intractability of all existing approaches. The main idea is to drive exploration by injecting noise into the least squares estimates, with the main novelty being that this is done only on the null space of the training data to avoid estimation erros from exploding.
weaknesses: 1. The "span argument" is quite interesting, but it also seems quite specific for MDPs with deterministic transitions. Not clear if it extends to stochastic MDPs
2. While a good step forward and a common setting in practice, the assumption of deterministic dynamics may be a limiting factor
3. There is no experiment despite the algorithm being computationally efficient (and, I hope, implementable)
4. Not clear if the dependences on d and H are optimal in the main theorems, or if there is still work to do in that direction

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: * There are some typos: e.g., "to the learn parameters" in p.2, and "where the it is" in p.6.
* Why are the constrained squared loss minimization problems first converted to the convex feasibility problem, and then solved by random walk method that depends on a separation oracle? It seems that when $\mathcal{S}$ and $\mathcal{A}$ are infinite, then it is challenging to design an appropriate separation oracle for $\mathcal{K}$. Even when  $\mathcal{S}$ and $\mathcal{A}$ are finite, then each minimization problem has $d$ decision variables and $2|\mathcal{S}||\mathcal{A}|$ constraints, requiring any separation oracle to evaluate the membership for $2|\mathcal{S}||\mathcal{A}|$ inequality constraints.
soundness: 3
strengths: * The paper achieves computational efficiency alongside a low regret bound. As the authors point out, computational considerations in MDP learning are crucial for practical applicability, particularly given that many recent works focus only on the statistical analysis of MDP learning.
* The idea of injecting random noise exclusively within the null space of the data matrix is brilliant. The insight that this approach promotes efficient exploration of unexplored feature space without redundancy is well-explained throughout the paper. This strategy may be potentially adapted to settings beyond linear Bellman completeness.
summary: The paper proposes a learning algorithm for linear Bellman-complete MDPs with deterministic dynamics. The algorithm randomizes value function estimates to facilitate efficient exploration of the feature space, a commonly used technique. However, the distinguishing feature of this algorithm is that the random noise is injected only into the null space of the collected feature vectors, selectively exploring previously unvisited regions of the feature space and preventing the value function parameters from growing exponentially with the horizon length. Furthermore, the algorithm employs a random walk-based constrained optimization solver, enhancing the computational efficiency of the method. The derived regret bound for the algorithm is optimal in the number of episodes.
weaknesses: * To illustrate the computational efficiency of the method, including a simple numerical demonstration would be beneficial.
* One concern is with the presentation style of the paper. The assumption of deterministic dynamics appears to be critical for the regret analysis, yet it is unclear why stochastic dynamics would impede the success of the method. Although it is mentioned that the deterministic nature of the system enables value decomposition as shown in Lemma 10, the necessity of this condition is not explicitly explained in the main body of the paper.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: In appendix E: LINEAR MDPS AND LQRS IMPLY LINEAR BELLMAN COMPLETENESS, the authors prove a result about the Linear Quadratic Regulator.

At line 2040, the authors claim that, due to the structure of the problem, the optimal actions writes as $Kx$, where $K$ is some matrix. Even if it is true that in the LQR the optimal policy takes this form, I am not convinced from that passage: indeed, what the authors are showing is that

$$E[\phi(x',\pi^*(x'))^\top \theta] = \phi(x,u)^\top \theta',$$

for some $\theta'$, where $\pi^*$ is the optimal policy. While in fact, what they needed to prove is that

$$E[\min_u \phi(x',u)^\top \theta] = \phi(x,u)^\top \theta'.$$

There is a subtle difference between the two things, as first we are using the optimal policy of the MDP, while in the second case $u$ is given by the best action _with respect to the given $\theta$._ Please, correct me if I am wrong.
soundness: 3
strengths: The paper introduces an algorithm based an a very original and novel idea, that is to perturb the parameters of the algorithm with a noise that is sampled from the null-space of the features spanned up to the given episode. This idea, which the authors call Null Space Randomization, may have a broader impact in the statistical learning community.

The paper also introduces some novelty in the proofs of the statistical complexity bounds. Related to the previous point, the authors introduce a Span Argument: indeed, the new features of the state-action pairs visited in the process do not lie outside of the span of the past features too often. In fact, for every time-step h, this can happen at most $d$ times. Using this simple observation, it is possible to avoid exponential blowout in $H$. 
As the problem of exponential blowout in the horizon appears in a wide family of RL with function approximation works, and is usually solved by truncating the value function, which needs to introduce unrealistic assumptions to ensure that truncation does not bring us outside of the function class, I think this is also a major contribution.

Lastly, it is remarkable that the papers deals also with the case of Low Inherent Bellman Error, where the linear model is affected by a misspecification. This scenario, while particularly challenging, is by far more general than assuming exact linearity.

Overall, it is worth mentioning that the algorithm proposed enjoys a regret guarantee which is order-optimal, i.e. scales with $\sqrt T$ (which is the best dependency) in the case of no misspecification. At the opposite side [1], which is perhaps the most recent "competitor" of this work, proves a statistical complexity bound that scales as

$$\varepsilon^{-O(A)},$$

being therefore exponentially dependent on the number of actions and potentially heavily suboptimal even for $A=2$ (due to the $O(\cdot)$). I see this as a major point for this work over the state of the art.


[1]Linear bellman completeness suffices for efficient online reinforcement
learning with few actions.
summary: The paper considers the problem of learning in an MDP that is endowed with a property known in literature of _linear Bellman completeness_. Intuitively, this property ensures that, whenever a function is linear in a given feature map, it remains linear after applying the  Bellman optimality operator.

Even if existing algorithms (Eleanor) achieve optimal regret guarantees for this setting, no algorithm is known to solve it with polynomial _computational complexity_ in every parameter. 

In this paper, the authors solve the problem in case the process is also deterministic.
weaknesses: The only big weakness of the paper is that the setting is very restrictive, and the contribution does not _at first sight_ seem a big improvement over the state of the art.

1. Assuming deterministic dynamics is very restrictive and, most importantly, does not marry very well with Bellmann completeness. Indeed, given the for of the Bellman optimality operator,
$$\mathcal Tf (s,a)=\int_S p(s'|s,a)\max_{a'\in A}f(s',a')\ ds',$$

One may hope that a well-behaved density function $p(s'|s,a)$ helps the result to approach the span of the features by smoothing everything (a smooth function is indeed easier too approximate with a linear feature map) thus reducing the inherent bellmann error. This does not happen in case of deterministic dynamics, as we just get

$$\mathcal Tf (s,a)=\max_{a'\in A}f(p(s,a),a'),$$

which may be only piecewise smooth due to the maximum.

2. As explained in the paragraph "Deterministic Rewards or Deterministic Initial State", an efficient algortihm was already known for the case where the initial state was fixed; generalizing to the case of random $s_1$ is usually easy for general MDPs. Still, it must be noted that the assumption of linear Bellman completeness does not allow for an easy reduction: just creating a fictitious initial state does not work in this case.

Overall, I think these limitations should not divert the attention for the value of the paper, as they are just a consequence of the hardness of the setting.

Meta-review: The paper proposes a computationally tractable algorithm for the linear Bellman complete setting, addressing a problem that has remained open in the literature for years.
It does so with a randomized algorithm that keeps under control the issue of error amplification.
I, and the reviewers, enthusiastically recommended the paper for acceptance.

Decision: Accept (Oral)