$\displaystyle-2\xi\|w_{h}^{\pi}\|_{2}\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}+\left(Q_{h}^{(t)}(x,\hat{\pi}_{h}^{(t)}(x))-Q_{h}^{\pi}(x,\hat{\pi}_{h}^{(t)}(x))\right),$

where the final inequality uses Eq. 49. ∎

Lemma 5.9 establishes that the functions $Q_{h}^{(t)}$ are an approximate
upper bound on $Q_{h}^{\star}$.

######  Lemma 5.9 (Optimism).

Under the event $\mathcal{E}$ of Lemma 5.7, it holds that, for all $x,a,h,t$,

$\displaystyle\varepsilon_{\mathsf{bkup}}\cdot(H-h)+Q_{h}^{(t)}(x,a)\geq$
$\displaystyle Q_{h}^{\star}(x,a)$ (50)
$\displaystyle\varepsilon_{\mathsf{bkup}}\cdot(H+1-h)+V_{h}^{(t)}(x)+F_{h}^{(t)}(x)\geq$
$\displaystyle V_{h}^{\star}(x).$ (51)

###### Proof.

Condition on the event $\mathcal{E}$, and fix $t\in[T]$. We prove the
statement using reverse induction on $h$. The base case $h=H+1$ is immediate
since
$Q_{H+1}^{(t)}(x,a)=Q_{H+1}^{\star}(x,a)=V_{H+1}^{(t)}(x)=V_{H+1}^{\star}(x)=0$
for all $x,a,t$.

Now suppose that the statement of the lemma holds at step $h+1$. For all
$x,a$, we have

$\displaystyle Q_{h}^{(t)}(x,a)=$ $\displaystyle
r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}\left[F_{h+1}^{(t)}(x^{\prime})+V_{h+1}^{(t)}(x^{\prime})\right]$
(52) $\displaystyle Q_{h}^{\star}(x,a)=$ $\displaystyle
r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}\left[V_{h+1}^{\star}(x^{\prime})\right],$
(53)

where Eq. 52 uses the definition of $Q_{h}^{(t)},V_{h}^{(t)}$ in Eqs. 34 and
35. The inductive hypothesis gives that

$\displaystyle\varepsilon_{\mathsf{bkup}}\cdot(H+1-h-1)+V_{h+1}^{(t)}(x^{\prime})+F_{h+1}^{(t)}(x^{\prime})\geq
V_{h+1}^{\star}(x^{\prime})$ (54)

for all $x^{\prime}\in\mathcal{X}$. Combining Eqs. 52 and 53, we see that

$\displaystyle Q_{h}^{(t)}(x,a)-Q_{h}^{\star}(x,a)=$
$\displaystyle\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}\left[F_{h+1}^{(t)}(x^{\prime})+V_{h+1}^{(t)}(x^{\prime})-V_{h+1}^{\star}(x^{\prime})\right]\geq-\varepsilon_{\mathsf{bkup}}\cdot(H-h),$
(55)

where the inequality uses Eq. 54. This verifies Eq. 50 at step $h$.

To establish Eq. 51 at step $h$, set
$(\Sigma^{\prime},\Lambda^{\prime}):=\mathsf{trunc}_{\sigma_{\mathsf{tr}}}({(\beta/\lambda_{1})\cdot(\Sigma_{h}^{(t)})^{-1/2}})$
(per Definition 5.2), so that $(\Sigma^{\prime},\Lambda^{\prime})$ is an
orthogonal pair (note that this is the same choice as is made in the
definition of $F_{h}^{(t)}(\cdot)$ in Eq. 33).

Let $\xi$ be defined as per Definition 5.1, so that $\xi\geq 1$. Now consider
any $x\in\mathcal{X}$ and $\pi\in\Pi$. We consider two cases based on the
value of $x$.

##### Case 1.

In the first case, we assume that

$\displaystyle\max_{a,a^{\prime}\in\mathcal{A}}\|\Lambda^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\leq\xi\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}.$
(56)

Then Lemma 5.8 with $(\Sigma,\Lambda)=(\Sigma^{\prime},\Lambda^{\prime})$ and
$\pi=\pi^{\star}$ gives that

$\displaystyle
V_{h}^{(t)}(x)+2\xi\|w_{h}^{\star}\|_{2}\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\geq$
$\displaystyle
V_{h}^{\star}(x)+\left(Q_{h}^{(t)}(x,\hat{\pi}_{h}^{(t)}(x))-Q_{h}^{\star}(x,\hat{\pi}_{h}^{(t)}(x))\right)$
$\displaystyle\geq$ $\displaystyle
V_{h}^{\star}(x)-\varepsilon_{\mathsf{bkup}}\cdot(H-h),$

where the second inequality uses Eq. 55. We may compute

$\displaystyle
2\xi\|w_{h}^{\star}\|_{2}\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\leq$
$\displaystyle
2\xi\lambda_{1}\cdot\sqrt{2\pi}\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{a\in\mathcal{A}}\langle
w,\phi_{h}(x,a)\rangle\right]\leq F_{h}^{(t)}(x),$

where the first inequality uses Lemmas 5.3 and 4.4 as well as the fact that
$(\Sigma^{\prime})^{2}=\Sigma^{\prime}$, and the second inequality uses the
definition of $F_{h}^{(t)}(\cdot)$ in Eq. 33. It then follows that Eq. 51
holds at step $h$.

##### Case 2.

In the second case, we assume that Eq. 56 does not hold, which implies that

$\displaystyle\max\left\\{\xi\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2},\max_{a,a^{\prime}\in\mathcal{A}}\|\Lambda^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\right\\}$
$\displaystyle\leq$
$\displaystyle\max_{a,a^{\prime}\in\mathcal{A}}\|\Lambda^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\leq\max_{a,a^{\prime}\in\mathcal{A}}\|\phi_{h}(x,a)-\phi_{h}(x,a^{\prime})\|_{2}\leq
2.$ (57)

We will apply Lemma 4.10 with
$(\Sigma,\Lambda)=(\Sigma^{\prime},\Lambda^{\prime})$, the value of $\beta$
set to the present value of $\beta$ (defined in Definition 5.1),
$\varepsilon=\varepsilon_{\mathsf{apx}}$, and $\Phi=\bar{\Phi}_{h}(x)$. We
need to check that Eq. 23 holds; indeed, we have

$\displaystyle\max\left\\{\beta\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2},\max_{a,a^{\prime}\in\mathcal{A}}\|\Lambda^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\right\\}$
$\displaystyle\leq$ $\displaystyle 8\sqrt{2\pi}C_{\ref{lem:phi-what-wt-
diff}}\lambda_{1}HBd\sqrt{\iota}\cdot\max\left\\{\xi\cdot\max_{a,a^{\prime}\in\mathcal{A}}\|\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2},\max_{a,a^{\prime}\in\mathcal{A}}\|\Lambda^{\prime}\cdot(\phi_{h}(x,a)-\phi_{h}(x,a^{\prime}))\|_{2}\right\\}$
$\displaystyle\leq$ $\displaystyle 16\sqrt{2\pi}C_{\ref{lem:phi-what-wt-
diff}}\lambda_{1}HBd\sqrt{\iota},$

where the first inequality uses the definition of $\xi$ in Definition 5.1 and
the second inequality uses Eq. 57. Thus we may apply Lemma 4.10 with
$\zeta=16\sqrt{2\pi}C_{\ref{lem:phi-what-wt-diff}}\lambda_{1}HBd\sqrt{\iota}$.
For $a,a^{\prime}\in\mathcal{A}$, let us write
$\mu^{\star}_{{x,h,a,a^{\prime}}}$ as shorthand for
$\mu^{\star}_{{\bar{\Phi}_{h}(x),\phi_{h}(x,a),\phi_{h}(x,a^{\prime})}}$,
which was defined in Eq. 22. Fix any $a,a^{\prime}\in\mathcal{A}$; then
applying Lemma 4.10 with
$\phi=\phi_{h}(x,a),\phi^{\prime}=\phi_{h}(x,a^{\prime})$, we have

$\displaystyle\frac{1}{\lambda_{1}}\cdot F_{h}^{(t)}(x)\geq$
$\displaystyle\left(\frac{C_{\ref{cor:optimal-
perimeter}}}{\varepsilon_{\mathsf{apx}}}\right)^{2A}\cdot\mathbb{E}_{u^{\prime}\sim\mathcal{N}(0,\Sigma^{\prime})}\mathbb{E}_{v^{\prime}\sim\mathcal{N}(0,\Lambda^{\prime})}\left[F^{\mathsf{tl}}_{h}(x;\beta
u^{\prime},v^{\prime})\right]$
$\displaystyle+\sqrt{2\pi}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{\bar{a}\in\mathcal{A}}\langle
w,\phi_{h}(x,\bar{a})\rangle\right]$ $\displaystyle\geq$
$\displaystyle\|\beta\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\mu^{\star}_{{x,h,a,a^{\prime}}})\|_{2}+\|\Lambda^{\prime}\cdot(\mu^{\star}_{{x,h,a,a^{\prime}}}-\phi_{h}(x,a^{\prime}))\|_{2}-64\sqrt{2\pi}C_{\ref{lem:phi-
what-wt-diff}}\lambda_{1}HBd\sqrt{\iota}\cdot\varepsilon_{\mathsf{apx}}$
$\displaystyle+\sqrt{2\pi}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{\bar{a}\in\mathcal{A}}\langle
w,\phi_{h}(x,\bar{a})\rangle\right]$ $\displaystyle\geq$
$\displaystyle\|\beta\Sigma^{\prime}\cdot(\phi_{h}(x,a)-\mu^{\star}_{{x,h,a,a^{\prime}}})\|_{2}+\|\Lambda^{\prime}\cdot(\mu^{\star}_{{x,h,a,a^{\prime}}}-\phi_{h}(x,a^{\prime}))\|_{2}-\varepsilon_{\mathsf{bkup}}/(2\lambda_{1})$
$\displaystyle+\sqrt{2\pi}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{\bar{a}\in\mathcal{A}}\langle
w,\phi_{h}(x,\bar{a})\rangle\right],$ (58)

where the first inequality follows from the definition of $F_{h}^{(t)}(x)$ in
Eq. 33 and the fact that $\xi\geq 1$, the second inequality uses Lemma 4.10
with the above parameter settings, and the final inequality uses the
definition of $\varepsilon_{\mathsf{apx}}$ in Definition 5.1.

Write
$\mu^{\star}:=\mu^{\star}_{{x,h,\hat{\pi}_{h}^{(t)}(x),\pi_{h}^{\star}(x)}}$.
We now apply Lemma 5.7 with
$\phi=\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))-\mu^{\star}$. Then Lemma 5.7 ensures
that

$\displaystyle\left|\langle
w_{h}^{(t)}-\hat{w}_{h}^{(t)},\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))-\mu^{\star}\rangle\right|\leq$
$\displaystyle\beta\cdot\left\|(\Sigma_{h}^{(t)})^{-1/2}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x)-\mu^{\star})\right\|_{2}.$
(59)

Moreover, since $\mu^{\star}\in\bar{\Phi}_{h}(x)$, we have from the fact that
Eq. 50 holds at step $h$ that

$\displaystyle\langle w_{h}^{(t)}-w_{h}^{\star},\mu^{\star}\rangle\geq$
$\displaystyle-\varepsilon_{\mathsf{bkup}}\cdot(H-h).$ (60)

Finally, we have

$\displaystyle\langle
w_{h}^{\star},\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\rangle\geq$
$\displaystyle-\|w_{h}^{\star}\|_{2}\cdot\|\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\|_{2}.$
(61)

We may now compute

$\displaystyle V_{h}^{(t)}(x)-V_{h}^{\star}(x)=$ $\displaystyle
Q_{h}^{(t)}(x,\hat{\pi}_{h}^{(t)}(x))-Q_{h}^{\star}(x,\pi_{h}^{\star}(x))$
$\displaystyle\geq$ $\displaystyle
Q_{h}^{(t)}(x,\hat{\pi}_{h}^{(t)}(x))-Q_{h}^{\star}(x,\pi_{h}^{\star}(x))+\langle\hat{w}_{h}^{(t)},\mu^{\star}-\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))\rangle$
$\displaystyle=$ $\displaystyle\langle
w_{h}^{(t)}-w_{h}^{\star},\mu^{\star}\rangle+\langle\hat{w}_{h}^{(t)}-w_{h}^{(t)},\mu^{\star}-\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))\rangle+\langle
w_{h}^{\star},\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\rangle$
$\displaystyle\geq$
$\displaystyle-\varepsilon_{\mathsf{bkup}}\cdot(H-h)-\beta\cdot\left\|(\Sigma_{h}^{(t)})^{-1/2}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x)-\mu^{\star})\right\|_{2}-\|w_{h}^{\star}\|_{2}\cdot\|\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\|_{2},$
(62)

where the first inequality uses that
$\hat{\pi}_{h}^{(t)}(x)=\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}}\hat{Q}_{h}^{(t)}(x,a^{\prime})$,
and the second inequality uses Eqs. 59, 60 and 61. Moreover,

$\displaystyle\beta\cdot\left\|(\Sigma_{h}^{(t)})^{-1/2}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x)-\mu^{\star})\right\|_{2}+\|w_{h}^{\star}\|_{2}\cdot\|\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\|_{2}$
$\displaystyle\leq$
$\displaystyle\beta\cdot\left\|(\Sigma_{h}^{(t)})^{-1/2}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x)-\mu^{\star})\right\|_{2}+\lambda_{1}\cdot\|\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x))\|_{2}$
$\displaystyle\leq$
$\displaystyle\lambda_{1}\cdot\left(\|(\beta/\lambda_{1})\cdot\Sigma^{\prime}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))-\mu^{\star})\|_{2}+\|\Lambda^{\prime}\cdot(\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x)))\|_{2}\right.$
$\displaystyle\left.+\sqrt{2\pi}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{a\in\mathcal{A}}\langle
w,\phi_{h}(x,a)\rangle\right]+2\sigma_{\mathsf{tr}}\right),$ (63)

where the first inequality uses that $\|w_{h}^{\star}\|_{2}\leq\lambda_{1}$
(Corollary 4.4) and the second inequality uses Lemma 5.4 with
$\Gamma=(\beta/\lambda)\cdot(\Sigma_{h}^{(t)})^{-1/2}$ and
$\sigma=\sigma_{\mathsf{tr}}$, as well as the fact that
$\|(\Sigma_{h}^{(t)})^{-1/2}\|\leq 1$ (which follows by the choice of
$\lambda=1$ in Definition 5.1), so that $\|\Gamma\|\leq\beta/\lambda_{1}$.

Combining Eqs. 62, 63 and 58 and the fact that $\lambda_{1}\geq 1$, it follows
that

$\displaystyle V_{h}^{(t)}(x)-V_{h}^{\star}(x)$ $\displaystyle\geq$
$\displaystyle-\varepsilon_{\mathsf{bkup}}\cdot(H-h)-\|\beta\Sigma^{\prime}\cdot(\phi_{h}(x,\hat{\pi}_{h}^{(t)}(x))-\mu^{\star})\|_{2}-\lambda_{1}\cdot\|\Lambda^{\prime}\cdot(\mu^{\star}-\phi_{h}(x,\pi_{h}^{\star}(x)))\|_{2}$
$\displaystyle-\sqrt{2\pi}\lambda_{1}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,\Sigma^{\prime})}\left[\max_{a\in\mathcal{A}}\langle
w,\phi_{h}(x,a)\rangle\right]-2\lambda_{1}\sigma_{\mathsf{tr}}$
$\displaystyle\geq$
$\displaystyle-\varepsilon_{\mathsf{bkup}}\cdot(H-h)-F_{h}^{(t)}(x)-\varepsilon_{\mathsf{bkup}}/2-2\lambda_{1}\sigma_{\mathsf{tr}}$
(64) $\displaystyle\geq$
$\displaystyle-\varepsilon_{\mathsf{bkup}}\cdot(H+1-h)-F_{h}^{(t)}(x),$ (65)

where the final inequality follows since
$\varepsilon_{\mathsf{bkup}}/2+2\lambda_{1}\sigma_{\mathsf{tr}}\leq\varepsilon_{\mathsf{bkup}}$
by the choice of $\sigma_{\mathsf{tr}}$ in Definition 5.1. This verifies that
Eq. 51 holds at step $h$, completing the proof of the lemma. ∎

######  Theorem 5.10.

For any $\varepsilon_{\mathsf{final}},\delta\in(0,1)$, the policy
$\hat{\pi}:=\frac{1}{T}\sum_{t=1}^{T}\hat{\pi}^{(t)}$ produced by Algorithm 1
has suboptimality bounded by
$V_{1}^{\star}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})\leq\varepsilon_{\mathsf{final}}$
after the algorithm has gathered

$O\left(Hd^{2}\cdot\left(\frac{H^{4}B^{3}dA^{1/2}\log^{1/2}(HABd/(\varepsilon_{\mathsf{final}}\delta))}{\varepsilon_{\mathsf{final}}}\right)^{12A+4}\right)$

samples and used $(HBdA\log(1/(\varepsilon_{\mathsf{final}}\delta)))^{O(A)}$
time.

###### Proof.

Using the fact that
$V_{1}^{\hat{\pi}^{(t)}}(x_{1})=\mathbb{E}^{\hat{\pi}^{(t)}}\left[\sum_{h=1}^{H}r_{h}(x_{h},a_{h})\right]$
as well as the definition of $V_{h}^{(t)}$ in Eqs. 34 and 35, we see that

$\displaystyle V_{1}^{(t)}(x_{1})-V_{1}^{\hat{\pi}^{(t)}}(x_{1})=$
$\displaystyle\sum_{h=2}^{H}\mathbb{E}^{\hat{\pi}^{(t)}}\left[F_{h}^{(t)}(x_{h})\right].$
(66)

Set $\gamma=\sqrt{d}\beta\lambda_{1}\cdot\left(\frac{C_{\ref{lem:sigmap-
bound}}}{\varepsilon_{\mathsf{apx}}}\right)^{2A}$. For each $h\in[H],t\in[T]$,
let us write
$((\Sigma_{h}^{\prime})^{(t)},(\Lambda_{h}^{\prime})^{(t)}):=\mathsf{trunc}_{\sigma_{\mathsf{tr}}}({(\beta/\lambda_{1})\cdot(\Sigma_{h}^{(t)})^{-1/2}})$.
Then under the event $\mathcal{E}$ of Lemma 5.9 (which satisfies
$\operatorname{Pr}(\mathcal{E})\geq 1-\delta/2$),

$\displaystyle V_{1}^{\star}(x_{1})-V_{1}^{\hat{\pi}^{(t)}}(x_{1})\leq$
$\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+V_{1}^{(t)}(x_{1})+F_{1}^{(t)}(x_{1})-V_{1}^{\hat{\pi}^{(t)}}(x_{1})$
$\displaystyle=$ $\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+\sum_{h=1}^{H}\mathbb{E}^{\hat{\pi}^{(t)}}\left[F_{h}^{(t)}(x_{h})\right]$
$\displaystyle\leq$ $\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+\gamma\sum_{h=1}^{H}\mathbb{E}^{\hat{\pi}^{(t)}}\left[\mathbb{E}_{w\sim\mathcal{N}(0,(\Sigma_{h}^{\prime})^{(t)})}\left[\max_{a\in\mathcal{A}}\langle
w,\phi_{h}(x_{h},a)\rangle\right]\right]$ $\displaystyle\leq$ $\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+\gamma\sum_{h=1}^{H}\mathbb{E}^{\hat{\pi}^{(t)}}\left[\sqrt{d}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,(\Sigma_{h}^{\prime})^{(t)})}\left[\phi_{h}(x_{h},\pi_{h,w}(x_{h}))^{\top}(\Sigma_{h}^{\prime})^{(t)}\phi_{h}(x_{h},\pi_{h,w}(x_{h}))\right]^{1/2}\right]$
$\displaystyle\leq$ $\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+\gamma\sqrt{d}\sum_{h=1}^{H}\mathbb{E}^{\hat{\pi}^{(t)}\circ_{h}\tilde{\pi}^{(t)}}\left[\phi_{h}(x_{h},a_{h})^{\top}(\Sigma_{h}^{\prime})^{(t)}\phi_{h}(x_{h},a_{h})\right]^{1/2}$
$\displaystyle\leq$ $\displaystyle
H\cdot\varepsilon_{\mathsf{bkup}}+\gamma\sqrt{d}\cdot\frac{\beta}{\sigma_{\mathsf{tr}}\lambda_{1}}\sum_{h=1}^{H}\mathbb{E}^{\hat{\pi}^{(t)}\circ_{h}\tilde{\pi}^{(t)}}\left[\phi_{h}(x_{h},a_{h})^{\top}(\Sigma_{h}^{(t)})^{-1}\phi_{h}(x_{h},a_{h})\right]^{1/2},$
(67)

where the first inequality uses Lemma 5.9, the second inequality uses Lemma
5.5 together with the definition of $\gamma$, the third inequality uses Lemma
5.3, the fourth inequality uses Jensen’s inequality as well as the definition
of $\tilde{\pi}_{h}^{(t)}$ in 10 of Algorithm 1, and the final inequality uses
the fact that
$((\Sigma_{h}^{\prime})^{(t)},(\Lambda_{h}^{\prime})^{(t)})=\mathsf{trunc}_{\sigma_{\mathsf{tr}}}({\frac{\beta}{\lambda_{1}}\cdot(\Sigma_{h}^{(t)})^{-1/2}})$
together with Lemma 5.2, which implies that
$((\Sigma_{h}^{\prime})^{(t)})^{2}=(\Sigma_{h}^{\prime})^{(t)}\preceq\frac{\beta}{\sigma_{\mathsf{tr}}\lambda_{1}}\cdot(\Sigma_{h}^{(t)})^{-1/2}$.

For each $h\in[H],t\in[T]$, let us define

$\displaystyle\Gamma_{h}^{(t)}:=\mathbb{E}^{\hat{\pi}^{(t)}\circ_{h}\tilde{\pi}^{(t)}}\left[\phi_{h}(x_{h},a_{h})\phi_{h}(x_{h},a_{h})^{\top}\right].$

Next, for each $t\in[T]$ and $h\in[H]$, we will now apply Lemma 6.3 with $P$
given by the distribution of $\phi_{h}(x_{h},a_{h})$ for
$(x_{h},a_{h})\sim\mathbb{P}^{\mathsf{unif}(\\{\hat{\pi}^{s}\circ_{h}\tilde{\pi}^{(s)}\\}_{s=1}^{t-1}\\})}$.
Write

$\displaystyle\Lambda_{h}^{(t)}=\mathbb{E}^{\mathsf{unif}(\\{\hat{\pi}^{(s)}\circ_{h}\tilde{\pi}^{(s)}\\})_{s=1}^{t-1}}[\phi_{h}(x_{h},a_{h})\phi_{h}(x_{h},a_{h})^{\top}],$

so that for each $i\in[n]$,
$\mathbb{E}[\phi_{h}(x_{h}^{(t,i,h)},a_{h}^{(t,i,h)})\phi_{h}(x_{h}^{(t,i,h)},a_{h}^{(t,i,h)})^{\top}]=\Lambda_{h}^{(t)}$.
Then Lemma 6.3 together with the definition of $\Sigma_{h}^{(t)}$ in 5 of
Algorithm 1 gives that, since $\lambda\geq C_{\ref{lem:psd-
concentration}}d\log(2THn/\delta)$ (per Definition 5.1),

$\displaystyle\operatorname{Pr}\left(\frac{1}{3}(\lambda
I+n\Lambda_{h}^{(t)})\preceq\Sigma_{h}^{(t)}\preceq\frac{5}{3}(\lambda
I+n\Lambda_{h}^{(t)})\right)\geq 1-\delta/(2TH).$ (68)

Let $\mathcal{E}^{\prime}$ denote the event that Eq. 68 holds for all
$h\in[H],t\in[T]$, so that $\mathcal{E}^{\prime}$ occurs with probability at
least $1-\delta/2$. Since $n\geq 3T$, we have that
$\frac{n}{3}\Lambda_{h}^{(t)}\succeq\sum_{s=1}^{t}\Gamma_{h}^{(s)}$, and
therefore, under $\mathcal{E}^{\prime}$, we have
$\tilde{\Sigma}_{h}^{(t)}:=\frac{\lambda}{3}I_{d}+\sum_{s=1}^{t}\Gamma_{h}^{(s)}\preceq\Sigma_{h}^{(t)}$.
Next, we may compute, for each $h\in[H]$,

$\displaystyle\sum_{t=1}^{T}\mathbb{E}^{\hat{\pi}^{(t)}\circ_{h}\tilde{\pi}^{(t)}}[\phi_{h}(x_{h},a_{h})^{\top}(\Sigma_{h}^{(t)})^{-1}\phi_{h}(x_{h},a_{h})]=$
$\displaystyle\sum_{t=1}^{T}\langle\Gamma_{h}^{(t)},(\Sigma_{h}^{(t)})^{-1}\rangle\leq\sum_{t=1}^{T}\langle\Gamma_{h}^{(t)},(\tilde{\Sigma}_{h}^{(t)})^{-1}\rangle\leq
2d\log(2T),$ (69)

where the final inequality uses Lemma 6.4 together with the fact that
$\lambda/3\geq 1$. Combining Eq. 67 and Eq. 69, and using Jensen’s inequality,
we obtain that under $\mathcal{E}\cap\mathcal{E}^{\prime}$ (which occurs with
probability at least $1-\delta$), for sufficiently large constants
$C,C^{\prime}$,

$\displaystyle\sum_{t=1}^{T}(V_{1}^{\star}(x_{1})-V_{1}^{\hat{\pi}^{(t)}}(x_{1}))\leq$
$\displaystyle
TH\varepsilon_{\mathsf{bkup}}+\frac{H\gamma\beta\sqrt{d}}{\sigma_{\mathsf{tr}}\lambda_{1}}\cdot\sqrt{2Td\log(2T)}$
$\displaystyle\leq$ $\displaystyle
TH\varepsilon_{\mathsf{bkup}}+\frac{4Hd\beta^{2}\lambda_{1}}{\varepsilon_{\mathsf{bkup}}}\cdot\left(\frac{C_{\ref{lem:sigmap-
bound}}}{\varepsilon_{\mathsf{apx}}}\right)^{2A}\cdot\sqrt{2Td\log(2T)}$
$\displaystyle\leq$ $\displaystyle
TH\varepsilon_{\mathsf{bkup}}+\frac{CH^{6}B^{5}d^{3}\iota}{\varepsilon_{\mathsf{bkup}}}\cdot\left(\frac{C_{\ref{cor:optimal-
perimeter}}}{\varepsilon_{\mathsf{apx}}}\right)^{4A}\cdot\left(\frac{C_{\ref{lem:sigmap-
bound}}}{\varepsilon_{\mathsf{apx}}}\right)^{2A}\cdot\sqrt{2Td\log(2T)}$
$\displaystyle\leq$ $\displaystyle
TH\varepsilon_{\mathsf{bkup}}+\frac{CH^{6}B^{5}d^{3}\iota}{\varepsilon_{\mathsf{bkup}}}\cdot\left(\frac{C^{\prime}H^{3}B^{3}d\sqrt{\iota}}{\varepsilon_{\mathsf{bkup}}}\right)^{6A}$
$\displaystyle\leq$ $\displaystyle
T\varepsilon_{\mathsf{final}}/2+CH^{3}B^{2}d^{2}\sqrt{\iota}\left(\frac{2C^{\prime}H^{4}B^{3}d\sqrt{\iota}}{\varepsilon_{\mathsf{final}}}\right)^{6A+1},$
(70)

where the second inequality uses the definition of
$\gamma,\sigma_{\mathsf{tr}}$, and the remaining inequalities use the
definitions of
$\varepsilon_{\mathsf{apx}},\beta,\lambda_{1},\varepsilon_{\mathsf{final}}$ in
Definition 5.1. Next, we have the following claim:

######  Claim 5.11.

The choice of $T,\iota$ (in Definition 5.1) ensures that $T\geq
d\cdot\left(\frac{C_{\ref{thm:policy-
learning}}^{1/2}H^{4}B^{3}d\sqrt{\iota}}{\varepsilon_{\mathsf{final}}}\right)^{6A+2}$.

Claim 5.11 is proved at the end of the section. By Claim 5.11, as long as the
constant $C_{\ref{thm:policy-learning}}$ is chosen sufficiently large, the
expression in Eq. 70 is bounded above by $T\varepsilon_{\mathsf{final}}$.
Hence the policy $\hat{\pi}:=\frac{1}{T}\sum_{t=1}^{T}\hat{\pi}^{(t)}$
satisfies
$V_{1}^{\star}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})\leq\varepsilon_{\mathsf{final}}$.

Altogether, Algorithm 1 collects $THn\leq O(HT^{2})\leq
O\left(Hd^{2}\cdot\left(\frac{H^{4}B^{3}dA^{1/2}\log^{1/2}(HABd/(\varepsilon_{\mathsf{final}}\delta))}{\varepsilon_{\mathsf{final}}}\right)^{12A+4}\right)$
trajectories.

Finally, we analyze the computation time of Algorithm 1. It is straightforward
to see that each step of the algorithm can be implemented in
$\operatorname{poly}(T)$ time, with the exception of the computation of
$F_{g}^{(t)}(x_{g}^{(t,i,h)})$ in Eq. 6, which requires integrating a
nonlinear function over a Gaussian (see Eq. 33). To handle this difficulty, we
discuss a slight modification of our algorithm and its analysis which proceeds
by approximating this integral. To efficiently approximate the result of each
such integration, we use $O(\log(T/\delta)/\varepsilon_{\mathsf{apx}}^{2})$
draws from the appropriate Gaussian to approximate each integral to within
$\varepsilon_{\mathsf{apx}}$. The error term of $\varepsilon_{\mathsf{apx}}$
that arises in this approximation leads to an additional error term of
$\varepsilon_{\mathsf{apx}}$ in Eq. 42 (Lemma 5.7), which in turn leads to an
additional term of $-\varepsilon_{\mathsf{apx}}$ in Eq. 64. By an appropriate
choice of the constants in Definition 5.1, we can ensure that
$\varepsilon_{\mathsf{apx}}+\varepsilon_{\mathsf{bkup}}/2+2\lambda_{1}\sigma_{\mathsf{tr}}\leq\varepsilon_{\mathsf{bkup}}$,
which ensures that Eq. 65 still holds. The remaining details of the proof
remain unchanged. ∎

###### Proof of Claim 5.11.

Note that, since $n=3T$ and by the definition of $T$ in Definition 5.1, for
sufficiently large constants $C,C^{\prime}$ (independent of
$C_{\ref{thm:policy-learning}}$), we have $\iota\leq
C\cdot(\log(HBd/\delta)+\log(T))\leq C^{\prime}\cdot
A\log\left(\frac{C_{\ref{thm:policy-
learning}}HBdA}{\varepsilon_{\mathsf{final}}\delta}\right)$. Then

$\displaystyle d\cdot\left(\frac{C_{\ref{thm:policy-
learning}}^{1/2}H^{4}B^{3}d\sqrt{\iota}}{\varepsilon_{\mathsf{final}}}\right)^{6A+2}\leq
d\cdot\left(\frac{\sqrt{C^{\prime}}\log^{1/2}(C_{\ref{thm:policy-
learning}})\cdot C_{\ref{thm:policy-
learning}}^{1/2}H^{4}B^{3}dA^{1/2}\log^{1/2}(HBdA/(\varepsilon_{\mathsf{final}}\delta))}{\varepsilon_{\mathsf{final}}}\right)^{6A+2}.$

As long as $C_{\ref{thm:policy-learning}}$ is chosen sufficiently large so
that $\sqrt{C^{\prime}}\log^{1/2}(C_{\ref{thm:policy-
learning}})C_{\ref{thm:policy-learning}}^{1/2}\leq C_{\ref{thm:policy-
learning}}$, the right-hand side of the above expression is bounded above by
$T$, as desired. ∎

##  6 Useful lemmas

###  6.1 Concentration

######  Lemma 6.1 (Concentration for self-normalized process; e.g., Theorem
D.3 of [JYWJ20]).

Fix $n\in\mathbb{N}$ and let $\varepsilon_{1},\ldots,\varepsilon_{n}$ be
random variables which are adapted to a filtration $(\mathcal{F}_{i})_{0\leq
i\leq n}$. Suppose that for each $i\in[n]$,
$\mathbb{E}[\varepsilon_{i}|\mathcal{F}_{i-1}]=0$ and
$\mathbb{E}[e^{\lambda\varepsilon_{i}}|\mathcal{F}_{i-1}]\leq
e^{\lambda^{2}\sigma^{2}/2}$. Suppose that $\phi_{1},\ldots,\phi_{n}$ is a
sequence which is predictable with respect to $(\mathcal{F}_{i})_{0\leq i\leq
n}$, i.e., $\phi_{i}$ is measurable with respect to $\mathcal{F}_{i-1}$ for
all $i\in[n]$. Suppose that $\Gamma_{0}\in\mathbb{R}^{d\times d}$ is positive
definite, and let
$\Gamma_{i}=\Gamma_{0}+\sum_{j=1}^{i}\phi_{j}\phi_{j}^{\top}$. Then for any
$\delta>0$, with probability at least $1-\delta$,

$\displaystyle\left\|\sum_{i=1}^{n}\phi_{i}\varepsilon_{i}\right\|_{\Gamma_{i}^{-1}}^{2}\leq
2\sigma^{2}\log\left(\frac{\det(\Gamma_{t})^{1/2}\det(\Gamma_{0})^{-1/2}}{\delta}\right).$

In the special case that the random variables $\varepsilon_{i}$ are i.i.d., we
obtain the following:

######  Corollary 6.2 (Concentration for self-normalized process; i.i.d.
data).

Fix $n\in\mathbb{N}$, and let $\varepsilon_{1},\ldots,\varepsilon_{n}$ be
independent real-valued random variables, so that for each $i\in[n]$,
$\mathbb{E}[\varepsilon_{i}]=0$ and
$\mathbb{E}[e^{\lambda\varepsilon_{i}}]\leq e^{\lambda^{2}\sigma^{2}/2}$ for
all $\lambda\in\mathbb{R}$. Let $\phi_{1},\ldots,\phi_{n}\in\mathbb{R}^{d}$ be
given. Suppose that $\Gamma_{0}\in\mathbb{R}^{d\times d}$ is positive
definite, and let
$\Gamma_{i}=\Gamma_{0}+\sum_{j=1}^{i}\phi_{j}\phi_{j}^{\top}$. Then for any
$\delta>0$, with probability at least $1-\delta$,

$\displaystyle\left\|\sum_{i=1}^{n}\phi_{i}\varepsilon_{i}\right\|_{\Gamma_{i}^{-1}}^{2}\leq
2\sigma^{2}\log\left(\frac{\det(\Gamma_{t})^{1/2}\det(\Gamma_{0})^{-1/2}}{\delta}\right).$

######  Lemma 6.3 (Lemma 39 of [ZCA21]).

There is a constant $C_{\ref{lem:psd-concentration}}>0$ so that the following
holds. Suppose $P$ is a distribution supported on the unit Euclidean ball in
$\mathbb{R}^{d}$. Write $\Sigma=\mathbb{E}_{\phi\sim P}[\phi\phi^{\top}]$.
Suppose $n\in\mathbb{N},\delta>0,\lambda$ are given so that $\lambda\geq
C_{\ref{lem:psd-concentration}}d\log(n/\delta)$. Suppose
$\phi_{1},\ldots,\phi_{n}\sim P$ are i.i.d. Then

$\displaystyle\operatorname{Pr}\left(\frac{1}{3}(\lambda
I+n\Sigma)\preceq\lambda
I+\sum_{i=1}^{n}\phi_{i}\phi_{i}^{\top}\preceq\frac{5}{3}(\lambda
I+n\Sigma)\right)\geq 1-\delta.$

###  6.2 Elliptical potential

The below lemma generalizes the elliptical potential lemma.

######  Lemma 6.4.

Consider any sequence $\Gamma_{1},\ldots,\Gamma_{T}\in\mathbb{R}^{d\times d}$
of PSD matrices, and suppose that $\operatorname{Tr}\Gamma_{t}\leq 1$ for all
$t\in[T]$. Define $\Sigma_{t}=\lambda I+\sum_{s=1}^{t}\Gamma_{s}$, for some
$\lambda\geq 1$. Then

$\displaystyle\sum_{t=1}^{T}\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle\leq
2d\log(2T).$

###### Proof.

Write $\Sigma_{0}=\lambda I$. Since $\lambda\geq 1$, we have
$\Sigma_{t-1}^{-1}\preceq I_{d}$ and therefore
$\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle\leq\operatorname{Tr}\Gamma_{t}\leq
1$ for all $t\in[T]$. Thus $\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle\leq
2\log(1+\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle)$. Moreover, for each
$t\in[T]$,

$\displaystyle\det(\Sigma_{t})=$ $\displaystyle\det(\Sigma_{t-1}+\Gamma_{t})$
$\displaystyle=$
$\displaystyle\det(\Sigma_{t-1})\cdot\det\left(I+\Sigma_{t-1}^{-1/2}\Gamma_{t}\Sigma_{t-1}^{-1/2}\right)$
$\displaystyle\geq$
$\displaystyle\det(\Sigma_{t-1})\cdot(1+\operatorname{Tr}(\Sigma_{t-1}^{-1/2}\Gamma_{t}\Sigma_{t-1}^{-1/2}))=\det(\Sigma_{t-1})\cdot(1+\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle),$

where the inequality uses that for any real numbers
$\sigma_{1},\ldots,\sigma_{d}\geq 0$, $\prod_{i=1}^{d}(1+\sigma_{i})\geq
1+\sum_{i=1}^{d}\sigma_{i}$, which implies that $\det(I+A)\geq
1+\operatorname{Tr}(A)$ for any PSD matrix $A$ (by taking
$\sigma_{1},\ldots,\sigma_{d}$ to be the eigenvalues of $A$). Telescoping the
above display, we obtain that

$\displaystyle\frac{1}{2}\sum_{t=1}^{T}\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle\leq\sum_{t=1}^{T}\log(1+\langle\Gamma_{t},\Sigma_{t-1}^{-1}\rangle)\leq\log\left(\frac{\det(\Sigma_{T})}{\det(\lambda
I)}\right)\leq\log\left(\frac{\left(\frac{1}{d}\operatorname{Tr}(\Sigma_{T})\right)^{d}}{\det(\lambda
I)}\right)\leq d\log\left(\frac{\lambda d+T}{\lambda d}\right)\leq d\log(2T).$

∎

###  6.3 Performance difference lemma

######  Lemma 6.5 (Performance difference lemma [KL02]).

For any MDP $M$, policies $\pi,\pi^{\prime}\in\Pi$, it holds that

$\mathbb{E}^{\scriptscriptstyle{M,\pi}}\left[\sum_{h=1}^{H}r_{h}(x_{h},a_{h})\right]-\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}\left[\sum_{h=1}^{H}r_{h}(x_{h},a_{h})\right]=\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}\left[V^{\scriptscriptstyle{M,\pi}}_{h}(x_{h})-Q^{\scriptscriptstyle{M,\pi}}_{h}(x_{h},a_{h})\right].$

###  6.4 Linear algebraic lemmas

######  Lemma 6.6.

Two symmetric matrices $\Sigma,\Gamma\in\mathbb{R}^{d\times d}$ commute if and
only if their eigenspaces coincide.

## Acknowledgements

We thank Dylan Foster and Sham Kakade for bringing this problem to our
attention and for helpful discussions.

##  Appendix A Proofs for Section 4

###  A.1 Functions which are not Bellman-linear

######  Proposition A.1.

There is an MDP $M=(H,\mathcal{X},\mathcal{A},(P_{h})_{h},(r_{h})_{h},d_{1})$
with horizon $H=2$ satisfying linear Bellman completeness with respect to some
feature mappings $\phi_{h}$ in dimension $d=1$, together with a vector
$w^{\star}\in\mathbb{R}^{d}$ so that the function

$\displaystyle V_{h}(x):=\max_{a\in\mathcal{A}}\min\left\\{\langle
w^{\star},\phi_{h}(x,a)\rangle,H\right\\}$

is not Bellman-linear at step $2$ (per Definition 3.1).

###### Proof.

We set $H=2,d=1$,
$\mathcal{X}=\\{\mathfrak{s}_{1},\mathfrak{s}_{2,0},\mathfrak{s}_{2,1}\\}$,
and $\mathcal{A}=\\{0,1\\}$, and define:

$\displaystyle\phi_{1}(\mathfrak{s}_{1},0)=1,\phi_{1}(\mathfrak{s}_{1},1)=2,$
$\displaystyle\phi_{2}(\mathfrak{s}_{2,0},0)=H,\phi_{2}(\mathfrak{s}_{2,0},1)=-H,\qquad\phi_{2}(\mathfrak{s}_{2,1},0)=2H,\phi_{2}(\mathfrak{s}_{2,1},1)=-2H.$

The transitions are defined as follows: $(\mathfrak{s}_{1},0)$ transitions to
$\mathfrak{s}_{2,0}$, and $(\mathfrak{s}_{1},1)$ transition to
$\mathfrak{s}_{2,1}$. All rewards are 0. By defining
$\mathcal{T}_{1}w:=H\cdot|w|$, it is readily seen that $M$ is linear Bellman
complete with respect to the above feature mappings.

Let us choose $w^{\star}=1$. Then Bellman-linearity of $V_{2}(x)$ would
require that there is some $\bar{w}\in\mathbb{R}$ so that

$\displaystyle\phi_{1}(\mathfrak{s}_{1},0)\cdot\bar{w}=H,\qquad\phi_{1}(\mathfrak{s}_{1},1)\cdot\bar{w}=H.$

But since $\phi_{1}(\mathfrak{s}_{1},1)=2$ and
$\phi_{1}(\mathfrak{s}_{1},0)=1$, there is no such $\bar{w}$. ∎

Proposition A.1 provides an example for which a function $\hat{Q}_{h}^{(t)}$
as defined in Eq. 4, with $B_{h}^{(t)}\equiv 0$, is so that
$\max_{a\in\mathcal{A}}\hat{Q}_{h}^{(t)}(\cdot,a)$ is not Bellman-linear. We
have considered that case that $B_{h}^{(t)}$ is 0 for simplicity. Note that in
an instantiation of LSVI-UCB, $B_{h}^{(t)}$ would not be identically 0, as it
is defined by Eq. 5. Nevertheless, the example in Proposition A.1 can be
readily modified to account for nonzero quadratic bonus functions
$B_{h}^{(t)}$. In a similar manner, by rescaling the features we may modify
the example to ensure that $\|\phi_{h}(x,a)\|_{2}\leq 1$ for all $h,x,a$ (so
as to satisfy Assumption 2.1).

######  Proposition A.2.

There is an MDP $M=(H,\mathcal{X},\mathcal{A},(P_{h})_{h},(r_{h})_{h},d_{1})$
with horizon $H=2$ satisfying linear Bellman completeness with respect to some
feature mappings $\phi_{h}$ in dimension $d=1$, so that the function

$\displaystyle F_{h}(x):=\max_{a\in\mathcal{A}}\|\phi_{h}(x,a)\|_{2}$

is not Bellman-linear at step 2.

###### Proof.

We set
$H=2,d=1,\mathcal{X}=\\{\mathfrak{s}_{1},\mathfrak{s}_{2,0},\mathfrak{s}_{2,1},\mathfrak{s}_{2,2}\\}$,
$\mathcal{A}=\\{0,1\\}$, and define:

$\displaystyle\phi_{1}(\mathfrak{s}_{1},0)=1,\phi_{1}(\mathfrak{s}_{1},1)=1,$
$\displaystyle\phi_{2}(\mathfrak{s}_{2,0},0)=1,\phi_{2}(\mathfrak{s}_{2,0},1)=-1,\quad\phi_{2}(\mathfrak{s}_{2,1},0)=2,\phi_{2}(\mathfrak{s}_{2,1},1)=0,\quad\phi_{2}(\mathfrak{s}_{2,2},0)=-2,\phi_{2}(\mathfrak{s}_{2,2},1)=0.$

The transition are defined as follows: $(\mathfrak{s}_{1},0)$ transitions to
$\mathfrak{s}_{2,0}$, and $(\mathfrak{s}_{1},1)$ transitions to each of
$\mathfrak{s}_{2,1},\mathfrak{s}_{2,2}$ with probability $1/2$. All rewards
are 0. By defining $\mathcal{T}_{1}w:=|w|$, it is readily seen that $M$ is
linear Bellman complete with respect to the above feature mappings.

But Bellman-linearity of $F_{2}(x)$ would require that there is some
$\bar{w}\in\mathbb{R}$ so that

$\displaystyle\phi_{1}(\mathfrak{s}_{1},0)\cdot\bar{w}=1,\qquad\phi_{1}(\mathfrak{s}_{1},1)\cdot\bar{w}=2.$

No such $\bar{w}$ exists since
$\phi_{1}(\mathfrak{s}_{1},0)=\phi_{1}(\mathfrak{s}_{1},1).$ ∎

Proposition A.2 establishes that, for $B^{\mathsf{quad}}_{h}(x,a;\Sigma)$
defined as in Eq. 5, the mapping
$\max_{a\in\mathcal{A}}B^{\mathsf{quad}}_{h}(\cdot,a;I_{d})$ is, in general,
not Bellman-linear.

###  A.2 Perturbed linear policies

We begin by defining a perturbed version of linear policies.

######  Definition A.1 (Perturbed linear policies).

For $\sigma>0$, $h\in[H]$ and $w\in\mathbb{R}^{d}$, define
$\pi_{h,w,\sigma}:\mathcal{X}\rightarrow\Delta(\mathcal{A})$ by

$\displaystyle\pi_{h,w,\sigma}(x)(a)=\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}\cdot
I_{d})}\left(a\in\mathcal{A}_{h,\theta}(x)\right).$

In words, to draw an action $a\sim\pi_{h,w,\sigma}(x)$, we draw
$\theta\sim\mathcal{N}(w,\sigma^{2}\cdot I_{d})$ and then play
$\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}}\langle\phi_{h}(x,a^{\prime}),\theta\rangle$.
Given $\sigma>0$, we denote the set of all $\pi_{h,w,\sigma^{\prime}}$, where
$w\in\mathbb{R}^{d},\sigma^{\prime}>0$ satisfy
$\sigma^{\prime}/\|w\|_{2}\geq\sigma$, by $\Pi^{\mathsf{Plin},{\sigma}}_{h}$,
and
$\Pi^{\mathsf{Plin},{\sigma}}:=\prod_{h=1}^{H}\Pi^{\mathsf{Plin},{\sigma}}_{h}$.
As a matter of convention we write
$\Pi^{\mathsf{Plin},{0}}_{h}:=\Pi^{\mathsf{lin}}_{h}$ and
$\Pi^{\mathsf{Plin},{0}}=\Pi^{\mathsf{lin}}$. Moreover, we write
$\Pi^{\mathsf{Plin}}_{h}:=\bigcup_{\sigma\geq
0}\Pi^{\mathsf{Plin},{\sigma}}_{h}$ and
$\Pi^{\mathsf{Plin}}=\bigcup_{\sigma\geq 0}\Pi^{\mathsf{Plin},{\sigma}}$.

Note that, for any $c>0$, $\pi_{h,cw,\sigma}=\pi_{h,w,\sigma/{c}}$. Moreover,
note that tie-breaking is not an issue for perturbed linear policies, since
the measure of all $\theta$ so that $|\mathcal{A}_{h,\theta}(x)|>1$ is 0. The
following lemma provides another interpretation of linear policies, as a limit
of perturbed linear policies:

######  Lemma A.3.

For any $w\in\mathbb{R}^{d},h\in[H],x\in\mathcal{X}$, we have

$\displaystyle\pi_{h,w}(a|x)=\lim_{\sigma\rightarrow
0^{+}}\pi_{h,w,\sigma}(a|x)=\lim_{\sigma\rightarrow
0^{+}}\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}\cdot
I_{d})}\left(a\in\mathcal{A}_{h,\theta}(x)\right).$ (71)

###### Proof.

It is straightforward to see that for any $a\not\in\mathcal{A}_{h,w}(x)$,
$\lim_{\sigma\rightarrow
0^{+}}\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}I_{d})}(a\in\mathcal{A}_{h,\theta}(x))=0$.
This verifies Eq. 71 for $a\not\in\mathcal{A}_{h,w}(x)$. Moreover, it also
implies that for each $a\in\mathcal{A}_{h,w}(x)$, we have

$\displaystyle\lim_{\sigma\rightarrow
0^{+}}\left|\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}I_{d})}(a\in\mathcal{A}_{h,\theta}(x))-\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}I_{d})}\left(\langle\theta,\phi_{h}(x,a)\rangle>\max_{a^{\prime}\in\mathcal{A}_{h,w}(x)\backslash\\{a\\}}\langle\theta,\phi_{h}(x,a^{\prime})\rangle\right)\right|=0.$

Since $\langle w,\phi_{h}(x,a)\rangle=\langle w,\phi_{h}(x,a^{\prime})\rangle$
for all $a,a^{\prime}\in\mathcal{A}_{h,w}(x)$, we have that

$\displaystyle\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}I_{d})}\left(\langle\theta,\phi_{h}(x,a)\rangle>\max_{a^{\prime}\in\mathcal{A}_{h,w}(x)\backslash\\{a\\}}\langle\theta,\phi_{h}(x,a^{\prime})\rangle\right)$
$\displaystyle=$
$\displaystyle\operatorname{Pr}_{\theta\sim\mathcal{N}(0,\sigma^{2}I_{d})}\left(\langle\theta,\phi_{h}(x,a)\rangle>\max_{a^{\prime}\in\mathcal{A}_{h,w}(x)\backslash\\{a\\}}\langle\theta,\phi_{h}(x,a^{\prime})\rangle\right)$
$\displaystyle=$
$\displaystyle\operatorname{Pr}_{\theta\sim\nu_{d}}\left(\langle\theta,\phi_{h}(x,a)\rangle>\max_{a^{\prime}\in\mathcal{A}_{h,w}(x)\backslash\\{a\\}}\langle\theta,\phi_{h}(x,a^{\prime})\rangle\right)=\nu_{d}(\mathcal{G}_{h,w}(x,a)),$

where the second equality follows by rescaling. Combining the two displays
above gives the result. ∎

For a randomized policy $\pi$ and $h\in[H]$, we use the shorthand

$\displaystyle\phi_{h}(x,\pi_{h}(x)):=\mathbb{E}_{a\sim\pi_{h}(x)}[\phi_{h}(x,a)].$

Then Lemma A.3 yields that, for any
$h\in[H],w\in\mathbb{R}^{d},f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$,
we have

$\displaystyle\phi_{h}(x,\pi_{h,w}(x))=\lim_{\sigma\rightarrow
0^{+}}\phi_{h}(x,\pi_{h,w,\sigma}(x)),\qquad
f_{h}(x,\pi_{h,w}(x))=\lim_{\sigma\rightarrow 0^{+}}f(x,\pi_{h,w,\sigma}(x)).$
(72)

## References

  * [AJZ22] Alekh Agarwal, Yujia Jin, and Tong Zhang.  Vo$q$l: Towards optimal regret in model-free rl with nonlinear function approximation.  2022\.
  * [AOM17] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 263–272. JMLR.org, 2017.
  * [BB96] Steven J. Bradtke and Andrew G. Barto.  Linear least-squares algorithms for temporal difference learning.  Mach. Learn., 22(1–3):33–57, jan 1996.
  * [BJW19] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff.  Learning two layer rectified neural networks in polynomial time.  In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 195–268. PMLR, 25–28 Jun 2019.
  * [BKSN03] James Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng.  Policy search by dynamic programming.  Advances in neural information processing systems, 16, 2003.
  * [DKJ+19] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford.  Provably efficient rl with rich observations via latent state decoding.  In International Conference on Machine Learning, pages 1665–1674. PMLR, 2019.
  * [DKL+21] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang.  Bilinear classes: A structural framework for provable generalization in rl.  In International Conference on Machine Learning, pages 2826–2836. PMLR, 2021.
  * [DLMW20] Simon S. Du, Jason D. Lee, Gaurav Mahajan, and Ruosong Wang.  Agnostic q-learning with function approximation in deterministic systems: near-optimal bounds on approximation error and sample complexity.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc.
  * [DWX20] Santanu Dey, Guanyi Wang, and Yao Xie.  Approximation algorithms for training one-node relu neural networks.  IEEE Transactions on Signal Processing, PP:1–1, 11 2020.
  * [GHLL17] Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine.  Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates.  In 2017 IEEE international conference on robotics and automation (ICRA), pages 3389–3396. IEEE, 2017.
  * [GKMR20] Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman.  Tight hardness results for training depth-2 relu networks.  In Information Technology Convergence and Services, 2020.
  * [GM24] Noah Golowich and Ankur Moitra.  The role of inherent bellman error in offline reinforcement learning with linear function approximation.  In Reinforcement Learning Conference. Reinforcement Learning Journal, 2024.
  * [GMR22] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi.  Learning in observable pomdps, without computationally intractable oracles.  Advances in Neural Information Processing Systems, 35:1458–1473, 2022.
  * [GMR24] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi.  Exploring and learning in sparse linear mdps without computationally intractable oracles.  In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
  * [HGS16] Hado van Hasselt, Arthur Guez, and David Silver.  Deep reinforcement learning with double q-learning.  In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, page 2094–2100. AAAI Press, 2016.
  * [HZZG23] Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu.  Nearly minimax optimal reinforcement learning for linear Markov decision processes.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 12790–12822. PMLR, 23–29 Jul 2023.
  * [JAZBJ18] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  Advances in neural information processing systems, 31, 2018.
  * [JKA+17] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  Contextual decision processes with low bellman rank are pac-learnable.  In International Conference on Machine Learning, pages 1704–1713. PMLR, 2017.
  * [JLM21] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.  Advances in neural information processing systems, 34:13406–13418, 2021.
  * [JYWJ20] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In Conference on Learning Theory, pages 2137–2143. PMLR, 2020.
  * [KL02] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267–274, 2002.
  * [KLLM22] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan.  Computational-statistical gap in reinforcement learning.  In Conference on Learning Theory, pages 1282–1302. PMLR, 2022.
  * [LMK+23] Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, and Csaba Szepesvári.  Exponential hardness of reinforcement learning with linear function approximation.  In The Thirty Sixth Annual Conference on Learning Theory, pages 1588–1617. PMLR, 2023.
  * [MBFR23] Zakaria Mhammedi, Adam Block, Dylan J Foster, and Alexander Rakhlin.  Efficient model-free exploration in low-rank mdps.  arXiv preprint arXiv:2307.03997, 2023.
  * [MFR23] Zakaria Mhammedi, Dylan J Foster, and Alexander Rakhlin.  Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl.  arXiv preprint arXiv:2304.05889, 2023.
  * [MHKL20] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford.  Kinematic state abstraction and provably efficient rich-observation reinforcement learning.  In International conference on machine learning, pages 6961–6971. PMLR, 2020.
  * [MR07] Francisco S. Melo and M. Isabel Ribeiro.  Convergence of q-learning with linear function approximation.  In 2007 European Control Conference (ECC), pages 2671–2678, 2007\.
  * [MS08] Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  Journal of Machine Learning Research, 9(27):815–857, 2008.
  * [Mun05] Rémi Munos.  Error bounds for approximate value iteration.  In Proceedings of the 20th National Conference on Artificial Intelligence - Volume 2, AAAI’05, page 1006–1011. AAAI Press, 2005.
  * [OVRW16] Ian Osband, Benjamin Van Roy, and Zheng Wen.  Generalization and exploration via randomized value functions.  In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, page 2377–2386. JMLR.org, 2016.
  * [SB18] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  The MIT Press, second edition, 2018.
  * [SWD+17] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  CoRR, abs/1707.06347, 2017.
  * [TvR96] John N. Tsitsiklis and Benjamin van Roy.  Feature-based methods for large scale dynamic programming.  Mach. Learn., 22(1–3):59–94, jan 1996.
  * [WR16] Zheng Wen and Benjamin Van Roy.  Efficient reinforcement learning in deterministic systems with value function generalization, 2016.
  * [WSKS24] Runzhe Wu, Ayush Sekhari, Akshay Krishnamurthy, and Wen Sun.  Computationally efficient rl under linear bellman completeness for deterministic dynamics.  arXiv:2406.11810, 2024.
  * [YLNY21] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin.  Reinforcement learning in healthcare: A survey.  ACM Computing Surveys (CSUR), 55(1):1–36, 2021.
  * [YW20] Lin Yang and Mengdi Wang.  Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10746–10756. PMLR, 13–18 Jul 2020.
  * [ZCA21] Andrea Zanette, Ching-An Cheng, and Alekh Agarwal.  Cautiously optimistic policy optimization and exploration with linear function approximation.  In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4473–4525. PMLR, 15–19 Aug 2021.
  * [ZLKB20a] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent Bellman error.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10978–10989. PMLR, 13–18 Jul 2020.
  * [ZLKB20b] Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill.  Provably efficient reward-agnostic navigation with linear value iteration.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11756–11766. Curran Associates, Inc., 2020.
  * [ZSU+22] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun.  Efficient reinforcement learning in block mdps: A model-free representation learning approach.  In International Conference on Machine Learning, pages 26517–26547. PMLR, 2022.
  * [ZTS+22] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C. Parkes, and Richard Socher.  The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning.  Science Advances, 8(18):eabk2607, 2022.
  * [ZZJ20] Zihan Zhang, Yuan Zhou, and Xiangyang Ji.  Almost optimal model-free reinforcement learning via reference-advantage decomposition.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.