The authors would like to thank Csaba Szepesvári for helpful discussions. HI thanks Qingfeng Lan for many insightful discussions regarding the experiments. The work was initiated when HI, ZY, ZW and LY was visiting the Simons Institute for the Theory of Computing at UC-Berkeley (Theory of Reinforcement Learning Program).

LSVI-PHE with General Function Approximations
Noise
In the section, we specify how to choose \(\sigma \)  in Algorithm . Note that we use \(\xi _{h,k}^{\tau ,m}\)  for the noise added in episode \(k\) , timestep \(h\) , data from episode \(\tau <k\)  and sampling time \(m\) . Similarly, \(\xi ^{\prime i,m}_{h,k}\)  is for episode \(k\) , timestep \(h\) , regularizer \(p_i(\cdot )\)  and sampling time \(m\) . We set \(\lambda =1\)  in our algorithm. By Lemma REF , there exists \(\beta ^{\prime }(,\delta )\)  such that with probability at least \(1-\delta \) , for all \((k,h)\in [K]\times [H]\) , we have
\(f_h^k(\cdot ,\cdot ):=r(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )\in _h^{k},\) 
where \(_h^k=\lbrace f\in \,|\,\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2+R(f-\widehat{f}_h^{k})\le \beta ^{\prime }(,\delta )\rbrace .\)  By Assumption REF , for each \(_h^k\) , there exists a \(\sigma _{h,k}\)  such that
\(g_{\sigma _{h,k}}(s,a)\ge w(_h^k,s,a).\) 
We define \(\sigma =\max _{k\in [K],h\in [H]}\sigma _{h,k}\)  to be the maximum standard deviation of the added noise.

Concentration
We first define few filtrations and good events that we will use in the proof of lemmas in this section.
Definition A.1 (Filtrations) 
We denote the \(\sigma \) -algbera generated by the set \(\)  using \(\sigma ()\) . We define the following filtrations
\(^k &\stackrel{\text{def}}{=}\sigma \left(\lbrace (s_t^i, a_t^i, r_t^i)\rbrace _{\lbrace i,t\rbrace  \in [k-1]\times [H]}\,\ \bigcup \,\ \lbrace \xi ^{i,j}_{t,l}\rbrace _{i\in [l],\lbrace t,j,l\rbrace  \in [H]\times [M]\times [k-1]} \bigcup \,\ \lbrace \xi ^{\prime i,j}_{t,l}\rbrace _{\lbrace i,t,j,l\rbrace  \in [D]\times [H]\times [M]\times [k-1]}\right),\\_{h,1}^k &\stackrel{\text{def}}{=}\sigma \left(^k \,\ \bigcup \,\ \lbrace (s_t^k, a_t^k, r_t^k)\rbrace _{t\in [h]}\bigcup \,\ \lbrace \xi ^{i,j}_{t,k}\rbrace _{i\in [k],t \ge h,j\in [M]}\bigcup \,\ \lbrace \xi ^{\prime i,j}_{t,k}\rbrace _{i\in [D],t \ge h,j\in [M]}\right),\\_{h,2}^K &\stackrel{\text{def}}{=}\sigma \left(^k\,\ \bigcup \,\ \lbrace (s_t^k, a_t^k, r_t^k)\rbrace _{t\in [h]} \right).\) 

Definition A.2 (Good events)
For any \(\delta > 0\) , we define the following random events
\(\mathcal {G}_{h}^k(\xi , \delta ) &\stackrel{\text{def}}{=}\Bigl \lbrace  \max _{i\in [k],j \in [M]}\left|\xi ^{i,j}_{h,k}\right| \le \sqrt{\gamma _k(\delta )}\bigcap \max _{i\in [D],j \in [M]}|\xi ^{\prime i,j}_{h,k}| \le \sqrt{\gamma _k(\delta )}\Bigr \rbrace ,\\\mathcal {G}(K, H, \delta ) &\stackrel{\text{def}}{=}\bigcap _{k \le K}\bigcap _{h \le H}\mathcal {G}^k_h(\xi ,\delta ),\) 

where \(\gamma _k(\delta )\)  is some constant to be specified in Lemma REF .

Notation:  To simplify our presentation, in the remaining part of this section, we always denote \(\sqrt{\gamma _k}:=\sqrt{\gamma _k(\delta )}\) .
The next lemma shows that the good event defined in Definition REF  happens with high probability.
Lemma A.3 
For good event \((K,H,\delta )\)  defined in Definition REF , if we set \(\sqrt{\gamma _k}=\widetilde{O}(\sigma )\) , then it happens with probability at least \(1-\delta \) .

Recall that \(\xi _{t,l}^{i,j}\)  is a zero-mean Gaussian noise with variance \(\sigma _{t,l}^2\) . By the concentration of Gaussian distribution (Lemma REF ), with probability \(1-\delta ^{\prime }\) , we have
\(|\xi _{t,l}^{i,j}|\le \sigma _{t,l} \sqrt{2\log (1/\delta ^{\prime })}\le \sigma \sqrt{2\log (1/\delta ^{\prime })}.\) 
The same result holds for \(\xi ^{\prime i,j}_{t,l}\) . We complete the proof by setting \(\delta ^{\prime }=\delta /(K+D)MHK\)  and using union bound.
In Definition REF , for a regularizer \(R(f) = \sum _{j=1}^D p_j(f)^2\) , where \(p_j(\cdot )\)  are functionals, we defined the perturbed regularizer as \(\widetilde{R}_\sigma (f)=\sum _{j=1}^D [p_j(f)+\xi ^{\prime }_j]^2\)  with \(\xi ^{\prime }_j\)  being i.i.d. zero-mean Gaussian noise with variance \(\sigma ^2\) . Note that in the algorithm, the variance of the noise for the regularizer is the same as the dataset, which is \(\sigma _{h,k}^2\) .
Recall from Assumption REF  that for any \(V:\rightarrow [0,H]\) , our regularizer \(R\)  satisfies \(R(r+PV)\le B\)  for some constant \(B\in \mathbb {R}\) .
Our next lemma establishes a bound on the perturbed estimate of a single backup.
Lemma A.4  Consider a fixed \(k \in [K]\)  and a fixed \(h \in [H]\) . Let \(_h^k=\lbrace (s_{h}^\tau ,a_{h}^\tau )\rbrace _{\tau \in [k-1]}\)  and \(\widetilde{\mathcal {D}}_{h,V}^{k}=\lbrace (s_{h}^\tau ,a_{h}^\tau , r_{h}^\tau +\xi _{h}^{\tau }+V(s_{h+1}^\tau ))\rbrace _{\tau \in [k-1]}\) . Define
\(\widetilde{f}_{h,V}^{k}= \operatornamewithlimits{arg\,min}_{f\in \mathcal {F}}\Vert f\Vert _{\widetilde{\mathcal {D}}_{h,V}^{k}}^2+\widetilde{R}(f).\)  Conditioned on the good event \((K,H,\delta )\) , with probability at least \(1-\delta \) , for a fixed \(V:\mathcal {S}\rightarrow [0,H]\)  and any \(V^{\prime }:\mathcal {S}\rightarrow [0,H]\)  with \(\Vert V^{\prime }-V\Vert _\infty \le 1/T\) , we have
\(&\left\Vert \widetilde{f}_{h,V^{\prime }}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_hV^{\prime }( \cdot ,\cdot )\right\Vert ^2_{\mathcal {Z}_h^k}+ R\left(\widetilde{f}_{h,V^{\prime }}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_hV^{\prime }( \cdot ,\cdot )\right)\\\le & c^{\prime }\left[\left(H+1 + \sqrt{\gamma _k}\right)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}}\right]^2,\) 

for some constant \(c^{\prime }\) . Here \(B\)  is the bound on the regularizer (Assumption REF ) and \(D\)  is the number of regularizers (Definition REF ). Define this event as \(_{h,V}(\delta )\) .

Recall that for notational simplicity, we denote \([\mathbb {P}_h V_{h+1}](s,a) = \mathbb {E}_{s^{\prime } \sim \mathbb {P}_h(\cdot \,|\, s, a)}V_{h+1}(s^{\prime })\) .
Now consider a fixed \(V:\rightarrow [0,H]\) , and define
\(f_V(\cdot , \cdot ) := r_h(\cdot ,\cdot ) + P_hV( \cdot , \cdot ).\) 
For any \(f \in \) , we consider \(\sum _{\tau \in [k-1]}\chi _h^\tau (f)\)  where
\(\chi _h^\tau (f):=2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau } -V(s_{h+1}^\tau )).\) 
Recalling the definition of the filtration \(_{h,1}^\tau \)  from Definition REF , we note
\(\mathbb {E}[\chi _h^\tau (f)|_{h,1}^\tau ]&=\mathbb {E}[2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))|_{h,1}^\tau ]\\&=2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))\mathbb {E}[(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))|_{h,1}^\tau ]\\&=2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau )-P_hV(s_h^\tau ,a_h^\tau ))\\&=0.\) 

In addition, conditioning on the good event \((K,H,\delta )\) , we have
\(\left|\chi _h^\tau (f)\right|\le 2(H+1+ \sqrt{\gamma _\tau })|f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau )|.\) 
As \(\chi _h^\tau (f)\)  is a martingale difference sequence conditioned on the filtration \(_{h,1}^\tau \)  , by Azuma-Hoeffding inequality, we have
\(\mathbb {P}\left[\left|\sum _{\tau \in [k-1]}\chi _h^\tau (f)\right|\ge \epsilon \right]\le 2\mathrm {exp}\left(-\frac{\epsilon ^2}{8(H+1+\sqrt{\gamma _\tau })^2\Vert f-f_V\Vert ^2_{_h^k}}\right).\) 
Now we set
\(\epsilon &=\sqrt{8(H+1+\sqrt{\gamma _\tau })^2\log \left(\frac{2 \mathcal {N}(,1/T)}{\delta }\right)\Vert f-f_V\Vert _{_h^k}^2}\\&\le 4(H+1+\sqrt{\gamma _\tau })\Vert f-f_V\Vert _{_h^k}\sqrt{\log (2/\delta )+\log \mathcal {N}(,1/T)}.\) 
With union bound, for all \(g\in (,1/T)\) , with probability at least \(1-\delta \)  we have
\(\left|\sum _{(\tau )\in [k-1]}\xi _h^\tau (g)\right|\le 4(H+ 1 + \sqrt{\gamma _\tau })\Vert f-f_V\Vert _{_h^k}\sqrt{\log (2/\delta )+\log \mathcal {N}(,1/T)}.\) 
Thus, for all \(f\in \) , there exists \(g\in (,1/T)\)  such that \(\Vert f-g\Vert _\infty \le 1/T\)  and
\(\left|\sum _{(\tau )\in [k-1]}\chi _h^\tau (f)\right|&\le \left|\sum _{(\tau )\in [k-1]}\chi _h^\tau (g)\right|+2(H+1+\sqrt{\gamma _\tau })\\&\le 4(H+1 +\sqrt{\gamma _\tau })\Vert g-f_V\Vert _{_h^k}\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+2(H+1+\sqrt{\gamma _\tau })\\&\le 4(H+1 + \sqrt{\gamma _\tau })(\Vert f-f_V\Vert _{_h^k}+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+2(H+1+\sqrt{\gamma _\tau }).\\\) 
For \(V^{\prime }:\rightarrow [0,H]\)  such that \(\Vert V-V^{\prime }\Vert _\infty \le 1/T\) , we have \(\Vert f_{V^{\prime }}-f_V\Vert _\infty \le \Vert V^{\prime }-V\Vert _\infty \le 1/T\) .
For any \(f \in \) , we have
\(& \Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2\\=& \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+2\sum _{(s_{h}^\tau ,a_{h}^\tau )\in _h^k}(f(s_{h}^\tau ,a_{h}^\tau )-f_{V^{\prime }}(s_{h}^\tau ,a_{h}^\tau ))(f_{V^{\prime }}(s_{h}^\tau ,a_{h}^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V^{\prime }(s_{h+1}^\tau ))\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+2\sum _{(s_{h}^\tau ,a_{h}^\tau )\in _h^k}(f(s_{h}^\tau ,a_{h}^\tau )-f_{V}(s_{h}^\tau ,a_{h}^\tau ))(f_{V}(s_{h}^\tau ,a_{h}^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))\\&-4(H+1+\sqrt{\gamma _k})\Vert V^{\prime }-V\Vert _\infty |_h^k|\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+\sum _{(\tau ,h)\in [k-1]\times [H]}\chi _h^\tau (f)-4(H+ 1 + \sqrt{\gamma _k})\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2-4(H+ 1 + \sqrt{\gamma _k})(\Vert f-f_V\Vert _{_h^k}+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}-6(H+1 + \sqrt{\gamma _k})\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2-4(H+1 + \sqrt{\gamma _k})(\Vert f-f_{V^{\prime }}\Vert _{_h^k}+2)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}-6(H+1 + \sqrt{\gamma _k}).\\\) 
In addition, using Assumption REF , we have the approximate triangle inequality for the perturbed regularizer:
\(&\widetilde{R}(f)-\widetilde{R}(f_{V^{\prime }})\\=&\sum _{i}^D[p_i(f)+\xi _i^{\prime }]^2-\sum _i^D[p_i(f_{V^{\prime }})+\xi _i^{\prime }]^2\\=&R(f)-R(f_{V^{\prime }})+2\sum _i^D \xi _i^{\prime }(p_i(f)-p_i(f_{V^{\prime }}))\\\ge & c R(f-f_{V^{\prime }})-2R(f_{V^{\prime }})-2\sum _i^D \sqrt{\gamma _k}p_i(f_{V^{\prime }})\\\ge & c R(f-f_{V^{\prime }})-2B-2\sqrt{\gamma _k}\sqrt{BD}.\) 
Summing the above two inequalities we have
\(\Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)-\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\widetilde{R}(f_{V^{\prime }})\ge \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+c R(f-f_{V^{\prime }})-C,\) 
where \(C=4(H+1 + \sqrt{\gamma _k})(\Vert f-f_{V^{\prime }}\Vert _{_h^k}+2)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+6(H+1 + \sqrt{\gamma _k})+2B+2\sqrt{\gamma _k}\sqrt{BD}\) .
As \(\widetilde{f}_{h,V^{\prime }}\)  is the minimizer of \(\Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)\) , we have
\(\Vert \widetilde{f}_{h,V^{\prime }}-f_{V^{\prime }}\Vert ^2_{_h^k}+ c R(\widetilde{f}_{h,V^{\prime }}-f_{V^{\prime }})\le c^{\prime }\left[(H+1 + \sqrt{\gamma _k})\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}}\right]^2.\) 
To prove the above argument, we use the inequality that if we have \(x^2+y\le ax+b\)  for positive \(a,b,y\) , then \(x\le a+\sqrt{b}\)  and \(x^2+y\le (a+\sqrt{b})^2.\)  In addition, we can remove \(c\)  by replacing \(c^{\prime }\)  with \(c^{\prime }/\min \lbrace 1,c\rbrace \)  and then we get our final bound.
Lemma A.5 (Confidence Region) 
Let \(_h^{k,m}=\lbrace f\in |\Vert f-\widetilde{f}_h^{k,m}\Vert _{_h^k}^2+R(f-\widetilde{f}_h^{k,m})\le \beta (,\delta )\rbrace \) , where
\(\beta (,\delta )= c^{\prime }\left[(H+1 + \sqrt{\gamma _k})\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}}\right]^2.\) 
Conditioned on the event \(\mathcal {G}(K, H, \delta )\) , with probability at least \(1-\delta \) , for all \((k,h,m)\in [K]\times [H]\times [M]\) , we have
\(r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )\in _h^{k,m}.\) 

First note that for a fixed \((k,h,m)\in [K]\times [H]\times [M]\) ,
\(=\lbrace \min \lbrace f(\cdot ,\cdot ),H\rbrace \mid f\in (,1/T)\rbrace \cup \lbrace 0\rbrace \) 
is a \((1/T)\) -cover of \(Q_{h+1}^{k,m}(\cdot ,\cdot )\) .
This implies \(\)  is also a \((1/T)\) -cover of \(Q_{h+1}^{k}(\cdot ,\cdot )\) . This further implies
\(=\lbrace \max _{a\in }q(\cdot ,a) \mid q \in \rbrace \) 
is a \(1/T\)  cover of \(V_{h+1}^{k}(\cdot )\)  where we have \(\log (||)=\log \mathcal {N}(,1/T)\) .
For the remaining part of the proof, we condition on \(\bigcap _{V\in }_{h,V}(\delta /||TM)\) , where \(_{h,V}(\delta )\)  is the event defined in Lemma REF . By Lemma REF  and union bound, we have \(\Pr \left[\bigcap _{V\in } _{h,V}(\delta /(8||MT)\right]\ge 1-\delta /(8MT)\) .
Let \(V\in \)  such that \(\Vert V-V_{h+1}^k\Vert _\infty \le 1/T\) . By Lemma REF  we have
\(\left\Vert \widetilde{f}_h^{k,m}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_h V_{h+1}^k(\cdot , \cdot )\right\Vert ^2_{_h^k}+R(\widetilde{f}_h^{k,m}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_h V_{h+1}^k(\cdot , \cdot ))&\\\le c^{\prime }\left[(H+1+ \sqrt{\gamma _k})\sqrt{\log \left(1/\delta \right)+\log \mathcal {N}\left(,1/T\right)}\right]^2,\) 
where \(c^{\prime }\)  is some absolute constant. By union bound, for all \((k,h,m) \in [K]\times [H]\times [M]\)  we have \(r_h(\cdot , \cdot )+P_h V_{h+1}^k( \cdot , \cdot ) \in _{h}^{k,m}\)  with probability \(1-\delta \) .
The last lemma guarantees that \(r_h(\cdot ,\cdot ) + P_hV_{h+1}^k(\cdot ,\cdot )\)  lies in the confidence region \(_h^{k,m}\)  with high probability. Note that the confidence region \(_h^{k,m}\)  is centered at \(\widetilde{f}_h^{k,m}\) , which is the solution to the perturbed regression problem defined in  (REF ). For the unperturbed regression problem and its solution as center of the confidence region, we get the following lemma as a direct consequence of Lemma REF .
Lemma A.6 
Let \(_h^{k}=\lbrace f\in |\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2+R(f-\widehat{f}_h^{k})\le \beta ^{\prime }(,\delta )\rbrace \) , where
\(\beta ^{\prime }(,\delta )\ge c^{\prime }\left[(H+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B}\right]^2.\) 
With probability at least \(1-\delta \) , for all \((k,h,m)\in [K]\times [H]\times [M]\) , we have
\(r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )\in _h^{k}.\) 

This is a direct implication of Lemma REF  with zero perturbance.

Optimism
In this section, we will show that \(\lbrace Q_h^k\rbrace _{(h,k)\in [H]\times [K]}\)  is optimistic with high probability. Formally, we have the following lemma.
Lemma A.7 
Set \(M=\ln (\frac{T||||}{\delta })/\ln (\frac{1}{1-v})\)  in Algorithm . Conditioned on the event \(\mathcal {G}(K, H, \delta )\) , with probability at least \(1-\delta \) , for all \(s\in \mathcal {S}\) , \(a\in \mathcal {A}\) , \(h\in [H]\) , \(k\in [K]\) , we have
\(Q_h^*(s,a)\le Q_h^k(s,a).\) 

For timestep \(H+1\) , we have \(Q_{H+1}^k=Q_{H+1}^*=0\) . By Lemma REF , there exists \(\beta ^{\prime }(,\delta )\)  such that with probability at least \(1-\delta \) , for all \((k,h)\in [K]\times [H]\) , we have
\(f_h^k(\cdot ,\cdot ):=r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )\in _h^{k},\) 
where \(_h^k=\lbrace f\in \,|\,\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2+R(f-\widehat{f}_h^{k})\le \beta ^{\prime }(,\delta )\rbrace .\)
Using notations introduced in Definition REF , let \(g_{h,\sigma }^k\)  be a function such that \(\widetilde{f}_h^{k,m}(s,a)\ge \widehat{f}(s,a)+g_{h,\sigma }^k(s,a)\)  holds with probability at least \(v\) . We set \(M=\ln (\frac{T||||}{\delta })/\ln (\frac{1}{1-v})\)  and then \(\widetilde{f}_h^{k,m}(s,a)\ge \widehat{f}(s,a)+g_{h,\sigma }^k(s,a)\)  with probability at least
\(1-(1-v)^M=1-\frac{\delta }{T||||},\) 
for any \((k,h)\in [K]\times [H]\)  and \((s,a)\in \times \) . By union bound, we have \(\widetilde{f}_h^{k,m}(s,a)\ge \widehat{f}(s,a)+g_{h,\sigma }^k(s,a)\)  for all \((k,h)\in [K]\times [H]\)  and \((s,a)\in \times \)  with probability at least \(1-\delta \)  and we have
\(\widetilde{f}_h^k(s,a)&=\max _{m\in [M]}\widetilde{f}_h^{k,m}(s,a)\\&\ge \widehat{f}_h^k(s,a)+g^k_{h,\sigma }(s,a)\\&\ge \widehat{f}_h^k(s,a)+w(_h^k)\\&\ge f_h^k(s,a),\) 

where the second inequality is from Assumption REF  and the choise of \(\sigma \)  as discussed in Appendix REF . The last inequality follows from the definition of the width function and the previous observation that \(f_h^k(\cdot ,\cdot )\in _h^{k}\)  with probability at least \(1-\delta \) .
Now we induct on \(h\)  from \(h=H\)  to 1.
\(Q_h^*(s,a)&=\min \lbrace  r_h(s,a)+P_h V_{h+1}^*(s,a),H\rbrace \\&=\min \lbrace f_h^k(s,a)+P_h(V_{h+1}^*-V_{h+1}^k)(s,a),H\rbrace \\&\le \min \lbrace \widetilde{f}_h^k(s,a)+P_h(V_{h+1}^*-V_{h+1}^k)(s,a),H\rbrace \\&\le \min \lbrace \widetilde{f}_h^k(s,a),H\rbrace \\&= Q_h^k(s,a).\) 

Thus,
\(V_h^*(s)=\max _a Q_h^*(s,a)\le \max _a Q_h^k(s,a)=V_h^k(s).\) 

where the second inequality is from \(V_{h+1}^*\le V_{h+1}^k\) , which is implied by induction.

Regret Bound
We are now ready to provide the regret bound for Algorithm . The next lemma upper bounds the regret of the algorithm by the sum of the width functions.
Lemma A.8 (Regret decomposition) 
Denote \(b_h^k(s,a)=w(_h^k,s,a)\) . Conditioned on the event \(\mathcal {G}(K, H, \delta )\) , with probability at least \(1-\delta \) , we have
\(\mathrm {Regret}(K)\le \sum _{k=1}^K\sum _{h=1}^{H}b_h^k(s_h^k,a_h^k)+\sum _{k=1}^K\sum _{h=1}^H\zeta _h^k,\) 
where \(\zeta _h^k=P(s_h^k,a_h^k)(V_{h+1}^k-V_{h+1}^{\pi ^k})-(V_{h+1}^k(s_{h+1}^k)-V_{h+1}^{\pi ^k}(s_{h+1}^k))\)  is a martingale difference sequence with respect to the filtration \(_{h,2}^k\) .

We condition on the good events in Lemma REF . For all \((k,h,m)\in [K]\times [H]\times [M]\) , we have
\(\left\Vert r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )-\widetilde{f}_h^{k,m}\right\Vert _{_h^k}^2+R(r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )-\widetilde{f}_h^{k,m})\le \beta (,\delta ).\) 
Recall that \(_h^k=\lbrace f\,|\,\left\Vert r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )-f\right\Vert _{_h^k}^2+R(r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )-\widetilde{f}_h^{k,m})\le \beta (,\delta )\rbrace \)  is the confidence region. Then for \((k,h,m)\in [K]\times [H]\times [M]\) , \(\widetilde{f}_h^{k,m}\in _h^k\) . Defining \(b_h^k(s,a)=w(_h^k,s,a)\) , for all \((k,h,m)\in [K]\times [H]\times [M]\)  we have,
\(b_h^k(s,a)\ge \left|r(s,a)+P(s,a)V_{h+1}^k-\widetilde{f}_h^{k,m}(s,a)\right|.\) 
As \(Q_h^k(s,a)=\min \lbrace \max _{m\in [M]}\lbrace \widetilde{f}_h^{k,m}(\cdot ,\cdot )\rbrace ,H-h+1\rbrace \) , we have
\(b_h^k(s,a)\ge \left|r(s,a)+P(s,a)V_{h+1}^k-Q_h^k(s,a)\right|.\) 
By Lemma REF  and standard telescoping argument, we have
\(\mathrm {Regret}(K)&\le \sum _{k=1}^K V_1^k(s_1^k)-V_1^{\pi _k}(s_1^k)\\&= \sum _{k=1}^K Q_1^k(s_1^k,a_1^k)-Q_1^{\pi ^k}(s_1^k,a_1^k)\\&= \sum _{k=1}^K Q_1^k(s_1^k,a_1^k)-(r(s_1^k,a_1^k)+P(s_1^k,a_1^k)V_2^k)+(r(s_1^k,a_1^k)+P(s_1^k,a_1^k)V_2^k)-Q_1^{\pi ^k}(s_1^k,a_1^k)\\&\le \sum _{k=1}^K b_1^k(s_1^k,a_1^k)+P(s_1^k,a_1^k)(V_2^k-V_2^{\pi ^k})\\&= \sum _{k=1}^K b_1^k(s_1^k,a_1^k)+(V_2^k(s_2^k)-V_2^{\pi ^k}(s_2^k))+\zeta _1^k\\&\le \sum _{k=1}^K \sum _{h=1}^H b_h^k(s_h^k,a_h^k) +\sum _{k=1}^K\sum _{h=1}^H\zeta _h^k.\) 
Lemma A.9 (Time inhomogeneous version of Lemma 10 in [1]}) 
Let \(^{\prime }\)  be a subset of function class \(\) , consisting of all \(f\in \)  such that
\(\Vert f-\upsilon \Vert ^2_{}+R(f-\upsilon ) \le \beta (,\delta ),\) 
where \(v=r + PV\)  as in Assumption REF  and \(\beta (,\delta )\)  as defined in Lemma REF . With probability at least \(1-\delta \) , we have
\(\sum _{k=1}^K \sum _{h=1}^H b_h^k(s_h^k,a_h^k)\le H+4H^3\mathrm {dim_\mathcal {E}}(^{\prime },1/T)+H\sqrt{c\mathrm {dim_\mathcal {E}}(^{\prime },1/T)K\beta (,\delta )},\) 
for some absolute constant \(c>0\) .

Define
\(^{\prime k}_h=\lbrace f\in ^{\prime }\,|\,\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2\le \beta (,\delta )\rbrace =^{\prime }\bigcap \lbrace f\in \,|\,\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2\le \beta (,\delta )\rbrace .\) 
As \(_h^k\subseteq ^{\prime }\)  and \(_h^k\subseteq \bigcap \lbrace f\in \,|\,\Vert f-\widehat{f}_h^{k}\Vert _{_h^k}^2\le \beta (,\delta )\rbrace \) , we have \(_h^k\subseteq _h^{\prime k}\)  and \(w(_h^k,s,a)\le w(_h^{\prime k},s,a)\)  for all \(s,a\) . By Assumption REF , \(^{\prime }\)  has bounded eluder dimension.
Similar to Lemma 10 in [1]}, we have for any \(h\) ,
\(\sum _{k=1}^K b_h^k(s_h^k,a_h^k)\le \sum _{k=1}^K w(^{\prime k}_h,s,a) \le 1+4H^2\mathrm {dim_\mathcal {E}}(^{\prime },1/T)+\sqrt{c\mathrm {dim_\mathcal {E}}(^{\prime },1/T)K\beta (,\delta )}.\) 
Summing over all timestep \(h\)  and we have the bound in the lemma.
Theorem A.10
Under all the assumptions, with probability at least \(1-\delta \) , Algorithm  achieves a regret bound of
\(\mathrm {Regret}(K)\le 4H^3\mathrm {dim_\mathcal {E}}(,1/T)+\sqrt{\mathrm {dim_\mathcal {E}}(,1/T)\beta (,\delta )HT},\) 
where
\(\beta (,\delta )= c^{\prime }\left[(H+1 + \sigma )\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sigma \sqrt{BD}}\right]^2,\) 
for some constant \(c^{\prime }\) .

By Assumption REF , we can consider \(^{\prime }\subseteq \)  as the whole function class in the analysis because it includes all the \(_{h}^k,\forall h,k\) . By Azuma-Hoeffding inequality and Lemma REF , With probability at least \(1-\delta \) , we have
\(\mathrm {Regret}(K)&\le \sum _{k=1}^K\sum _{h=1}^{H}b_h^k(s_h^k,a_h^k)+\sum _{k=1}^K\sum _{h=1}^H\zeta _h^k\\&\le c^{\prime }\left(H+4H^3\mathrm {dim_\mathcal {E}}(,1/T)+H\sqrt{c\mathrm {dim_\mathcal {E}}(,1/T)K\beta (,\delta )}+H\sqrt{KH\log \left(1/\delta \right)}\right),\) 

for some constant \(c^{\prime }\) .
We plug in the definition of \(\beta (,\delta )\)  and \(\sqrt{\gamma _k}=\widetilde{O}(\sigma )\) , then we get the final bound.
Remark A.11 For linear MDP, as shown in Section REF , we have
\(\sigma =2\sqrt{\beta ^{\prime }(,\delta )}=c^{\prime }\left[(H+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B}\right]^2,\) 
\(B=2Hd\)  and \(D=d\) . In addition, we have \(dim_\mathcal {E}(,1/T)=\widetilde{O}(d)\)  [3]} and \(\log \mathcal {N}\left(,1/T\right)=\widetilde{O}(d)\) . As a result, our bound implies a \(\widetilde{O}(\sqrt{H^3d^3T})\)  regret bound for linear MDP.


GFA With Model Misspecification
Assumption F  (Assumption 3 in [1]})
For function class \(\) , there exists a real number \(\zeta \) , such that for any \(V:\rightarrow [0,H]\) , there exists \(g_V\in \)  which satisfies
\(\max _{(s,a)\in \times }\left|g_V(s,a)-r(s,a)-\sum _{s^{\prime }\in }P(s^{\prime }|s,a)V(s^{\prime })\right|\le \zeta .\) 
In addition, we assume \(g_V\)  satisfies Assumption REF , i.e. \(R(g_V)\le B.\)

Lemma B.1  Consider a fixed \(k \in [K]\)  and a fixed \(h \in [H]\) . Let \(_h^k=\lbrace (s_{h}^\tau ,a_{h}^\tau )\rbrace _{\tau \in [k-1]}\)  and \(\widetilde{\mathcal {D}}_{h,V}^{k}=\lbrace (s_{h}^\tau ,a_{h}^\tau , r_{h}^\tau +\xi _{h}^{\tau }+V(s_{h+1}^\tau ))\rbrace _{\tau \in [k-1]}\) . Define
\(\widetilde{f}_{h,V}^{k}= \operatornamewithlimits{arg\,min}_{f\in \mathcal {F}}\Vert f\Vert _{\widetilde{\mathcal {D}}_{h,V}^{k}}^2+\widetilde{R}(f).\)  Conditioned on the good event \((K,H,\delta )\) , with probability at least \(1-\delta \) , for a fixed \(V:\mathcal {S}\rightarrow [0,H]\)  and any \(V^{\prime }:\mathcal {S}\rightarrow [0,H]\)  with \(\Vert V^{\prime }-V\Vert _\infty \le 1/T\) , we have
\(&\left\Vert \widetilde{f}_{h,V^{\prime }}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_hV^{\prime }( \cdot ,\cdot )\right\Vert ^2_{\mathcal {Z}_h^k}+ R(\widetilde{f}_{h,V^{\prime }}(\cdot ,\cdot )-r_h(\cdot ,\cdot )-P_hV^{\prime }( \cdot ,\cdot ))\\\le & c^{\prime }\left[(H+1 + \sqrt{\gamma _k})\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}+\zeta K(H+\sqrt{\gamma _k})}\right]^2,\) 

for some constant \(c^{\prime }\) .

Recall that for notational simplicity, we denote \([\mathbb {P}_h V_{h+1}](s,a) = \mathbb {E}_{s^{\prime } \sim \mathbb {P}_h(\cdot \,|\, s, a)}V_{h+1}(s^{\prime })\) .
Now consider a fixed \(V:\rightarrow [0,H]\) , and define
\(f_V(\cdot , \cdot ) = r_h(\cdot ,\cdot ) + P_hV( \cdot , \cdot ).\) 
By Assumption REF , there exists \(g_V\in \)  such that
\(\max _{(s,a)\in \times }\left|g_V(s,a)-f_V(s,a)\right|\le \zeta .\) 
For any \(f \in \) , consider
\(\chi _h^\tau =2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau } -V(s_{h+1}^\tau )).\) 
First we show that \(\chi _h^\tau (f)\)  is a martingale difference sequence with respect to the filtration \(_{h,1}^\tau \) .
\(\mathbb {E}[\chi _h^\tau (f)|_{h,1}^\tau ]&=\mathbb {E}[2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))|_{h,1}^\tau ]\\&=2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))\mathbb {E}[(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))|_{h,1}^\tau ]\\&=2(f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau ))(f_V(s_h^\tau ,a_h^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau )-P_hV(s_h^\tau ,a_h^\tau ))\\&=0.\) 
In addition, conditioning on good events \((K,H,\delta )\) , we have
\(|\chi _h^\tau (f)|\le 2(H+1+ \sqrt{\gamma _\tau })|f(s_h^\tau ,a_h^\tau )-f_V(s_h^\tau ,a_h^\tau )|.\) 
As \(\chi _h^\tau (f)\)  is a martingale difference sequence conditioned on the filtration \(_{h,1}^\tau \)  , by Azuma-Hoeffding inequality, we have
\(\mathbb {P}\left[\left|\sum _{\tau \in [k-1]}\chi _h^\tau (f)\right|\ge \epsilon \right]\le 2\mathrm {exp}\left(-\frac{\epsilon ^2}{8(H+1+\sqrt{\gamma _\tau })^2\Vert f-f_V\Vert ^2_{_h^k}}\right).\) 
Now we set
\(\epsilon &=\sqrt{8(H+1+\sqrt{\gamma _\tau })^2\log \left(\frac{2 N(,1/T)}{\delta }\right)\Vert f-f_V\Vert _{_h^k}^2}\\&\le 4(H+1+\sqrt{\gamma _\tau })\Vert f-f_V\Vert _{_h^k}\sqrt{\log (2/\delta )+\log \mathcal {N}(,1/T)}.\) 
With union bound, for all \(g\in (,1/T)\) , with probability at least \(1-\delta \)  we have
\(\left|\sum _{(\tau )\in [k-1]}\xi _h^\tau (g)\right|\le 4(H+ 1 + \sqrt{\gamma _\tau })\Vert f-f_V\Vert _{_h^k}\sqrt{\log (2/\delta )+\log \mathcal {N}(,1/T)}.\) 
Thus, for all \(f\in \) , there exists \(g\in (,1/T)\)  such that \(\Vert f-g\Vert _\infty \le 1/T\)  and ,
\(\left|\sum _{(\tau )\in [k-1]}\chi _h^\tau (f)\right|&\le \left|\sum _{(\tau )\in [k-1]}\chi _h^\tau (g)\right|+2(H+1+\sqrt{\gamma _\tau })\\&\le 4(H+1 +\sqrt{\gamma _\tau })\Vert g-f_V\Vert _{_h^k}\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+2(H+1+\sqrt{\gamma _\tau })\\&\le 4(H+1 + \sqrt{\gamma _\tau })(\Vert f-f_V\Vert _{_h^k}+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+2(H+1+\sqrt{\gamma _\tau })\\\) 
For \(V^{\prime }:\rightarrow [0,H]\)  such that \(\Vert V-V^{\prime }\Vert _\infty \le 1/T\) , we have \(\Vert f_{V^{\prime }}-f_V\Vert _\infty \le \Vert V^{\prime }-V\Vert _\infty \le 1/T\) .
For any \(f \in \) , we have
\(& \Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2\\=& \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+2\sum _{(s_{h}^\tau ,a_{h}^\tau )\in _h^k}(f(s_{h}^\tau ,a_{h}^\tau )-f_{V^{\prime }}(s_{h}^\tau ,a_{h}^\tau ))(f_{V^{\prime }}(s_{h}^\tau ,a_{h}^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V^{\prime }(s_{h+1}^\tau ))\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+2\sum _{(s_{h}^\tau ,a_{h}^\tau )\in _h^k}(f(s_{h}^\tau ,a_{h}^\tau )-f_{V}(s_{h}^\tau ,a_{h}^\tau ))(f_{V}(s_{h}^\tau ,a_{h}^\tau )-r_h^\tau (s_h^\tau ,a_h^\tau ) - \xi _{h}^{\tau }-V(s_{h+1}^\tau ))\\&-4(H+1+\sqrt{\gamma _k})\Vert V^{\prime }-V\Vert _\infty |_h^k|\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+\sum _{(\tau ,h)\in [k-1]\times [H]}\chi _h^\tau (f)-4(H+ 1 + \sqrt{\gamma _k})\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2-4(H+ 1 + \sqrt{\gamma _k})(\Vert f-f_V\Vert _{_h^k}+1)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}-6(H+1 + \sqrt{\gamma _k})\\\ge & \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2-4(H+1 + \sqrt{\gamma _k})(\Vert f-f_{V^{\prime }}\Vert _{_h^k}+2)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}-6(H+1 + \sqrt{\gamma _k}).\\\) 
In addition, by Assumption REF , we have
\(&\widetilde{R}(f)-\widetilde{R}(f_{V^{\prime }})\\=&\sum _{i}[p_i(f)-\xi _i^{\prime }]^2-\sum _i[p_i(f_{V^{\prime }})-\xi _i^{\prime }]^2\\=&R(f)-R(f_{V^{\prime }})-2\sum _i \xi _i^{\prime }(p_i(f)-p_i(f_{V^{\prime }}))\\\ge & c R(f-f_{V^{\prime }})-2R(f_{V^{\prime }})-2\sum _i \sqrt{\gamma _k}p_i(f_{V^{\prime }})\\\ge & c R(f-f_{V^{\prime }})-2B-2\sqrt{\gamma _k}\sqrt{BD}.\) 
Summing the above two inequalities we have
\(\Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)-\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\widetilde{R}(f_{V^{\prime }})\ge \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+c R(f-f_{V^{\prime }})-C,\) 
where \(C=4(H+1 + \sqrt{\gamma _k})(\Vert f-f_{V^{\prime }}\Vert _{_h^k}+2)\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+6(H+1 + \sqrt{\gamma _k})+2B+2\sqrt{\gamma _k}\sqrt{DB}\) .
Now we try to replace the \(f_{V^{\prime }}\)  in the RHS with \(g_V^{\prime }\) .
\(&\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\Vert g_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2\\=&\sum _{\tau \in [k-1]}(f_{V^{\prime }}(s_h^\tau ,a_h^\tau )-(r_h^\tau +\xi _h^\tau +V(s_{h+1}^\tau )))^2-\sum _{\tau \in [k-1]}(g_{V^{\prime }}(s_h^\tau ,a_h^\tau )-(r_h^\tau +\xi _h^\tau +V(s_{h+1}^\tau )))^2\\=&\sum _{\tau \in [k-1]}(f_{V^{\prime }}(s_h^\tau ,a_h^\tau )-g_{V^{\prime }}(s_h^\tau ,a_h^\tau ))(f_{V^{\prime }}(s_h^\tau ,a_h^\tau )+g_{V^{\prime }}(s_h^\tau ,a_h^\tau )-2(r_h^\tau +\xi _h^\tau +V(s_{h+1}^\tau )))\\\ge &-\zeta K(4H+2\sqrt{\gamma _k}).\) 

By the boundedness of the regularizer (Assumption REF ), we have
\(\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f_{V^{\prime }})-\Vert g_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\widetilde{R}(g_{V^{\prime }})\ge -\zeta K(4H+2\sqrt{\gamma _k})-B.\) 

Thus we have
\(\Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)-\Vert g_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\widetilde{R}(g_{V^{\prime }})&\ge \Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)-\Vert f_{V^{\prime }}\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2-\widetilde{R}(f_{V^{\prime }})-\zeta K(4H+2\sqrt{\gamma _k})-B\\&\ge \Vert f-f_{V^{\prime }}\Vert _{_h^k}^2+c R(f-f_{V^{\prime }})-C-\zeta K(4H+2\sqrt{\gamma _k})-B.\) 
As \(\widetilde{f}_{h,V^{\prime }}\)  is the minimizer of \(\Vert f\Vert _{\widetilde{}_{h,V^{\prime }}^k}^2+\widetilde{R}(f)\)  for \(f\in \)  and note that \(g_{V^{\prime }}\in \) , we have
\(&\Vert \widetilde{f}_{h,V^{\prime }}-f_{V^{\prime }}\Vert ^2_{_h^k}+ c R(\widetilde{f}_{h,V^{\prime }}-f_{V^{\prime }})\\\le & c^{\prime }\left[(H+1 + \sqrt{\gamma _k})\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}+\zeta K(H+\sqrt{\gamma _k})}\right]^2.\) 
To prove the above argument, we use the inequality that if we have \(x^2+y\le ax+b\)  for positive \(a,b,y\) , then \(x\le a+\sqrt{b}\)  and \(x^2+y\le (a+\sqrt{b})^2.\)  In addition, we can remove \(c\)  by replacing \(c^{\prime }\)  with \(c^{\prime }/\min \lbrace 1,c\rbrace \)  and then we get the final bound.
Lemma B.2 (Misspecified Confidence Region) 
Let \(_h^{k,m}=\lbrace f\in |\Vert f-\widetilde{f}_h^{k,m}\Vert _{_h^k}^2+R(f-\widetilde{f}_h^{k,m})\le \beta (,\delta )\rbrace \) , where
\(\beta (,\delta )= c^{\prime }\left[(H+1 + \sqrt{\gamma _k})\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sqrt{\gamma _kBD}+\zeta K(H+\sqrt{\gamma _k})}\right]^2.\) 
Conditioned on the event \(\mathcal {G}(K, H, \delta )\) , with probability at least \(1-\delta \) , for all \((k,h,m)\in [K]\times [H]\times [M]\) , we have
\(r_h(\cdot ,\cdot )+P_hV_{h+1}^k(\cdot ,\cdot )\in _h^{k,m}.\) 

With Lemma REF , the proof is same as Lemma REF .
Theorem B.3
Under all the assumptions, with probability at least \(1-\delta \) , Algorithm  achieves a regret bound of
\(\mathrm {Regret}(K)\le 4H^3\mathrm {dim_\mathcal {E}}(,1/T)+\sqrt{\mathrm {dim_\mathcal {E}}(,1/T)\beta (,\delta )HT},\) 
where
\(\beta (,\delta )= c^{\prime }\left[(H+1 + \sigma )\sqrt{\log \left(2/\delta \right)+\log \mathcal {N}\left(,1/T\right)}+\sqrt{B+\sigma \sqrt{BD}+\zeta K(H+\sigma )}\right]^2,\) 
for some constant \(c^{\prime }\) .

With Lemma REF , the proof is the same as Theorem REF .

LSVI-PHE with linear function approximation
In this section, we prove Theorem REF . Our analysis specilized to linear MDP setting is simpler and may provide additional insights. In addition, compared to GFA setting, we improve the bound for \(M\)  and it no longer depends on \(||\)  or \(||\) . We first introduce the notation and few definitions that are used throughout this section. Upon presenting lemmas and their proofs, finally we combine the lemmas to prove Theorem REF .
Definition C.1 (Model prediction error) 
For all \((k,h) \in [K]\times [H]\) , we define the model prediction error associated with the reward \(r_h^k\) ,
\(l^{k}_{h}(s,a) = r^k_h (s,a) + \mathbb {P}_{h}V^{k}_{h+1}(s,a) - Q^{k}_h(s,a).\) 
This depicts the prediction error using \(V_{h+1}^k\)  instead of \(V_{h+1}^{\pi ^k}\)  in the Bellman equations (REF ).

Definition C.2 (Unperturbed estimated parameter) 
For all \((k,h) \in [K]\times [H]\) , we define the unperturbed estimated parameter as
\(\widehat{\theta }^{k}_h=(\Lambda _h^k)^{-1}\left(\sum _{\tau =1}^{k-1}[r_h^\tau +V_{h+1}^k(s_{h+1}^\tau )]\phi (s_h^\tau ,a_h^\tau )\right).\) 
Moreover, we denote the difference between the perturbed estimated parameter \(\widetilde{\theta }^{k,j}_h\)  and the unperturbed estimated parameter \(\widehat{\theta _h^k}\)  as
\(\zeta _h^{k,j} = \widetilde{\theta }^{k,j}_h - \widehat{\theta _h^k}.\) 

Concentration
Our first lemma characterizes the difference between the perturbed estimated parameter \(\widetilde{\theta }^{k,j}_h\)  and the unperturbed estimated parameter \(\widehat{\theta }^{k}_h\) .
Proposition C.3 (restatement of Proposition REF ) 
In step 9 of Algorithm REF , conditioned on all the randomness except \(\lbrace \epsilon ^{k,i,j}_{h}\rbrace _{(i,j) \in [k-1]\times [M]}\)  and \(\lbrace \xi ^{k,j}_{h}\rbrace _{j \in [M]}\) , the estimated parameter \(\widetilde{\theta }^{k,j}_h\)  satisfies
\(\zeta _h^{k,j} = \widetilde{\theta }^{k,j}_h - \widehat{\theta }^{k}_h\sim N(0,\sigma ^2(\Lambda _h^k)^{-1}),\) 
where \(\widehat{\theta }^{k}_h=(\Lambda _h^k)^{-1}(\sum _{\tau =1}^{k-1}[r_h^\tau +V_{h+1}^k(s_{h+1}^\tau )]\phi (s_h^\tau ,a_h^\tau ))\)  is the unperturbed estimated parameter from Definiton REF .

From Algorithm REF , note that
\(\widetilde{\theta }^{k,j}_h &= (\Lambda ^{k}_h)^{-1} (\rho _h^k + \xi ^{k,j}_{h})\\&= (\Lambda ^{k}_h)^{-1} \left(\sum _{\tau =1}^{k-1}\left( [ r^\tau _{h} + V_{h+1}^{k}(s_{h+1}^\tau )+\epsilon ^{k,\tau ,j}_{h}] \phi (s_h^\tau ,a_h^\tau ) \right) + \xi ^{k,j}_{h}\right)\\&=(\Lambda ^{k}_h)^{-1} \left(\sum _{\tau =1}^{k-1} [ r^\tau _{h} + V_{h+1}^{k}(s_{h+1}^\tau )] \phi (s_h^\tau ,a_h^\tau ) \right) + (\Lambda ^{k}_h)^{-1}\left(\sum _{\tau =1}^{k-1}\epsilon ^{k,\tau ,j}_{h} \phi (s_h^\tau ,a_h^\tau ) + \xi ^{k,j}_{h}\right)\\&= \widehat{\theta }^{k}_h + (\Lambda ^{k}_h)^{-1}\left(\sum _{\tau =1}^{k-1}\epsilon ^{k,\tau ,j}_{h} \phi (s_h^\tau ,a_h^\tau ) + \xi ^{k,j}_{h}\right).\) 
Since \(\epsilon ^{k,\tau ,j}_{h} \sim N(0,\sigma ^2)\) , note that for \(\tau \in [k-1]\) ,
\(\epsilon ^{k,\tau ,j}_{h} \phi (s_h^\tau ,a_h^\tau ) \sim N(0, \sigma ^2\phi (s_h^\tau ,a_h^\tau )\phi (s_h^\tau ,a_h^\tau )^\top ).\) 
Now, since \(\xi ^{k,j}_{h}\sim (0,\sigma ^2\lambda I_d)\) ,
\((\Lambda ^{k}_h)^{-1}\left(\sum _{\tau =1}^{k-1}\epsilon ^{k,\tau ,j}_{h} \phi (s_h^\tau ,a_h^\tau ) + \xi ^{k,j}_{h}\right) &\sim (\Lambda ^{k}_h)^{-1} \cdot N\left(0, \sigma ^2\left(\sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\phi (s_h^\tau ,a_h^\tau )^\top +\lambda I_d \right)\right)\\&\sim (\Lambda ^{k}_h)^{-1} \cdot N\left(0,\sigma ^2 \Lambda _h^k\right)\\&\sim N(0,\sigma ^2(\Lambda _h^k)^{-1}).\) 

Thus, we have
\(\zeta _h^{k,j} = \widetilde{\theta }^{k,j}_h - \widehat{\theta }^{k}_h\sim N(0,\sigma ^2(\Lambda _h^k)^{-1}).\) 
Lemma C.4 (Lemma B.1 in [5]}) 
Under Definition  REF  of linear MDP, for any fixed policy \(\pi \) , let \(\lbrace \theta _h^\pi \rbrace _{h \in [H]}\)  be the corresponding weights such that \(Q_h^\pi (s,a) = \langle \phi (s,a),\theta _h^\pi \rangle \)  for all \((s,a,h)\in \times \times [H]\) . Then for all \(h\in [H]\) , we have
\(\Vert \theta _h^\pi \Vert  \le 2H\sqrt{d}.\) 

Our next lemma states that the unperturbed estimated weight \(\widehat{\theta }_h^k\)  is bounded.
Lemma C.5 
For any \((k,h) \in [K]\times [H]\) , the unperturbed estimated weight \(\widehat{\theta }^k_h\)  in Definition REF  satisfies
\(\Vert \widehat{\theta }^k_h\Vert  \le 2H\sqrt{kd/\lambda }.\) 

We have
\(\begin{split}\bigl \Vert \widehat{\theta }^k_h \bigr \Vert  &= \Bigl \Vert (\Lambda ^{k}_h)^{-1} \sum _{\tau =1}^{k-1} [r^\tau _{h}(s_h^\tau ,a_h^\tau ) + V_{h+1}^k(s_{h+1}^\tau )]\cdot \phi (s_h^\tau ,a_h^\tau ) \Bigr \Vert  \\&= \Bigl \Vert (\Lambda ^{k}_h)^{-1} \sum _{\tau =1}^{k-1} [r^\tau _{h}(s_h^\tau ,a_h^\tau ) + \max _{a \in } Q_{h+1}^{k}(s_{h+1}^\tau ,a)]\cdot \phi (s_h^\tau ,a_h^\tau ) \Bigr \Vert  \\& \le \frac{1}{\sqrt{\lambda }}\sqrt{k-1} \Bigl (\sum _{\tau =1}^{k-1} \bigl \Vert [r^\tau _{h}(s_h^\tau ,a_h^\tau ) + \max _{a \in } Q_{h+1}^{k}(s_{h+1}^\tau ,a)]\cdot \phi (s_h^\tau ,a_h^\tau )\bigr \Vert ^2_{(\Lambda ^{k}_h)^{-1}} \Bigr )^{1/2}\\& \le \frac{2H}{\sqrt{\lambda }}\sqrt{k-1}\Bigl (\sum _{\tau =1}^{k-1} \Vert \phi (s_h^\tau ,a_h^\tau )\Vert ^2_{(\Lambda ^{k}_h)^{-1}} \Bigr )^{1/2}\\&\le 2H\sqrt{kd/\lambda }.\end{split}\) 
Here, the first inequality follows from Lemma REF . The second inequality follows from the truncation of \(Q_h^k\)  to the range \([0,H-h+1]\)  in Line 11 of Algorithm REF . The last inequality is due to Lemma REF .
For the ease of exposition, we now define the values \(\beta _k(\delta )\) , \(\nu _k(\delta )\)  and \(\gamma _k(\delta )\)  which we use to define our high confidence bounds.
Definition C.6 (Noise bounds)
For any \(\delta > 0\)  and some large enough constants \(c_1\) ,\(c_2\)  and \(c_3\) , let
\(\sqrt{\beta _k(\delta )} &\stackrel{\text{def}}{=}c_1 H\sqrt{d\log (Hdk/\delta )}, \\\sqrt{\nu _k(\delta )} &\stackrel{\text{def}}{=}c_2 H\sqrt{d\log (Hdk/\delta )}, \\\sqrt{\gamma _k(\delta )} &\stackrel{\text{def}}{=}c_3 \sqrt{d\nu _k(\delta )\log (d/\delta )}.\) 

Definition C.7 (Noise distribution)
In Algorithm REF , we set the following values for \(\sigma \)
\(\sigma _k = 2\sqrt{\nu _k(\delta )}.\\\) 
Thus for all \(j \in [M]\) , we have,
\(\lbrace \xi ^{k,j}_{h}\rbrace  \sim \mathcal {N} \bigl (0,4\nu _k(\delta )(\Lambda ^{k}_h)^{-1} \bigr ).\) 

Now, we define some events based on the characterization of the random variable \(\zeta _h^{k,j}\)  as defined in Definition REF .
Definition C.8 (Good events) 
For any \(\delta > 0\) , we define the following random events
\(\mathcal {G}_{h}^k(\zeta , \delta ) &\stackrel{\text{def}}{=}\Bigl \lbrace  \max _{j \in [M]}\Vert \zeta ^{k,j}_{h}\Vert _{\Lambda _{h}^k} \le \sqrt{\gamma _k(\delta )}\Bigr \rbrace ,\\\mathcal {G}(K, H, \delta ) &\stackrel{\text{def}}{=}\bigcap _{k \le K}\bigcap _{h \le H}\mathcal {G}^k_h(\zeta ,\delta ).\) 

Next, we present our main concentration lemma in this section.
Lemma C.9 
Let \(\lambda = 1\)  in Algorithm REF . For any fixed \(\delta > 0\) , conditioned on the event \(\mathcal {G}(K, H, \delta )\) , we have for all \((k,h) \in [K]\times [H]\) ,
\(\Bigl \Vert \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau ) \bigl [\bigl (V^{k}_{h+1} - \mathbb {P}_h V^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau ) \bigr ] \Bigr \Vert _{(\Lambda _h^k)^{-1}} \le c_1 H\sqrt{d\log {(Hdk/\delta )}},\) 
with probability at least \(1-\delta \)  for some constant \(c_1 > 0 \) .

From Lemma REF , we know, for all \((k,h) \in [K]\times [H]\) , we have \(\Vert \widehat{\theta }^k_h\Vert  \le 2H\sqrt{kd/\lambda }\) .
In addition, by construction of \(\Lambda _{h+1}^k\) , the minimum eigenvalue of \(\Lambda _{h+1}^k\)  is lower bounded by \(\lambda \) . Thus we have \(\sqrt{\lambda }\Vert \zeta ^{k,j}_{h+1}\Vert  \le \Vert \zeta ^{k,j}_{h+1}\Vert _{\Lambda _{h+1}^k} \le \sqrt{\gamma _k(\delta )}\) . Finally, triangle inequality implies, \(\Vert \widetilde{\theta }_{h+1}^{k,j}\Vert  =\Vert \widehat{\theta }_{h+1}^k + \zeta ^{k,j}_{h+1}\Vert  \le 2H\sqrt{kd/\lambda } + \sqrt{\gamma _k(\delta )/\lambda }\)  for all \(j\in [M]\) . Combining Lemma REF  and Lemma REF , we have that, for any \(\varepsilon > 0\)  and \(\delta >0\) , with probability at least \(1-\delta \) ,
\(\begin{aligned}[b]& \Bigl \Vert \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )[\bigl (V^{k}_{h+1} - \mathbb {P}_hV^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau )]\Bigr \Vert _{(\Lambda _h^k)^{-1}} \\&\le \Bigl (4H^2\Bigl [\frac{d}{2}\log \Bigl (\frac{k +\lambda }{\lambda }\Bigr ) + d\log \Bigl (1+ \frac{4H\sqrt{kd/\lambda } + 2\sqrt{\gamma _k(\delta )/\lambda }}{\varepsilon }\Bigr ) + \log \frac{1}{\delta }\Bigr ] + \frac{8k^2\varepsilon ^2}{\lambda }\Bigr )^{1/2} \\&\le \Bigl (4H^2\Bigl [\frac{d}{2}\log \Bigl (\frac{k+\lambda }{\lambda }\Bigr ) + d\log \Bigl ( \frac{3(2H\sqrt{kd/\lambda } + \sqrt{\gamma _k(\delta )/\lambda })}{\varepsilon }\Bigr ) + \log \frac{1}{\delta }\Bigr ] + \frac{8k^2\varepsilon ^2}{\lambda }\Bigr )^{1/2} \\&\le 2H\Bigl [\frac{d}{2}\log \Bigl (\frac{k+\lambda }{\lambda }\Bigr ) + d\log \Bigl ( \frac{3(2H\sqrt{kd/\lambda } + \sqrt{\gamma _k(\delta )/\lambda })}{\varepsilon }\Bigr ) + \log \frac{1}{\delta }\Bigr ]^{1/2} + \frac{2\sqrt{2}k\varepsilon }{\sqrt{\lambda }} \\&\le 2H\sqrt{d}\Bigl [\frac{1}{2}\log \Bigl (\frac{k+\lambda }{\lambda }\Bigr ) + \log \Bigl ( \frac{3(2H\sqrt{kd/\lambda } + \sqrt{\gamma _k(\delta )/\lambda })}{\varepsilon }\Bigr ) + \log \frac{1}{\delta }\Bigr ]^{1/2} + \frac{2\sqrt{2}k\varepsilon }{\sqrt{\lambda }}.\end{aligned}\) 
Setting \(\lambda = 1, \, \varepsilon = H\sqrt{d}/k\)  and substituting \(\sqrt{\gamma _k(\delta )} = c_3 \sqrt{d\nu _k(\delta )\log (d/\delta )} \le c_4 Hd \log {(Hdk/\delta )} \)  for some constant \(c_4>0\) , we get
\(\begin{aligned}[b]& \Bigl \Vert \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )[\bigl (V^{k}_{h+1} - \mathbb {P}_hV^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau )]\Bigr \Vert _{(\Lambda _h^k)^{-1}} \\&\le 2H\sqrt{d}\Biggl [\frac{1}{2}\log (k+1) + \log (1/\delta ) + \log \frac{3k[2H\sqrt{dk} + c_4 Hd \log {(Hdk/\delta )}]}{H\sqrt{d}} \Biggr ]^{1/2} + 2\sqrt{2}H\sqrt{d}\\& \le c_1 H\sqrt{{d}\log {(Hdk/\delta )}},\end{aligned}\) 
for some constant \(c_1 >0\) .
Lemma C.10
Let \(\lambda = 1\)  in Algorithm REF . For any \(\delta > 0 \) , conditioned on the event \(\mathcal {G}(K, H, \delta )\) , for any \((h, k) \in [H] \times [K]\)  and \((s,a) \in \times \) , we have
\(\bigl | \phi (s,a)^\top \widehat{\theta }^{k}_h - r_h^k(s,a) - \mathbb {P}_h V^{k}_{h+1} (s,a) \bigr | \le c_2 H\sqrt{d\log (Hdk/\delta )} \bigl \Vert  \phi (s,a) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}},\) 
with probability \(1-\delta \) , where \(c_2> 0\)  is a constant.

Let us denote the inner product over \(\)  by \(\langle \cdot , \cdot \rangle _\) . Using linear MDP assumption for transition kernel from Definition REF , we get
\(\mathbb {P}_h V^{k}_{h+1}(s,a) &= \phi (s,a)^\top \langle \mu _h, V^{k}_{h+1} \rangle _\\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Lambda ^{k}_h\langle \mu _h, V^{k}_{h+1}\rangle _\\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\phi (s_h^\tau ,a_h^\tau )^\top + \lambda {I}\Bigr )\langle \mu _h, V^{k}_{h+1} \rangle _\\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\phi (s_h^\tau ,a_h^\tau )^\top \langle \mu _h, V^{k}_{h+1} \rangle _+ \lambda {I} \langle \mu _h, V^{k}_{h+1} \rangle _\Bigr ) \\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )(\mathbb {P}_h V^{k}_{h+1}) (s_h^\tau , a_h^\tau ) + \lambda {I} \langle \mu _h, V^{k}_{h+1} \rangle _\Bigr ),\) 

where in the last line we rely on the definition of \(\mathbb {P}_h\) .
Using (REF ) we obtain,
\(\phi (s,a)^\top \widehat{\theta }^k_h - r_h^k(s,a) - (\mathbb {P}_h V^{k}_{h+1})(s,a) &= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\sum _{\tau =1}^{k-1} \bigl [r^\tau _{h}(s_h^\tau ,a_h^\tau ) + V_{h+1}^k(s_{h+1}^\tau )\bigr ]\cdot \phi (s_h^\tau ,a_h^\tau ) - r_h^k(s,a) \\& \qquad - \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )(\mathbb {P}_hV^{k}_{h+1}) (s_h^\tau , a_h^\tau ) + \lambda {I} \langle \mu _h, V^{k}_{h+1} \rangle _\Bigr )\\&= \underbrace{\phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\bigl [\bigl (V^{k}_{h+1} - \mathbb {P}_h V^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau )\bigr ] \Bigr )}_{\text{(i)}} \\& \qquad + \underbrace{\phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau )\Bigr ) - r_h^k(s,a)}_{\text{(ii)}} \\& \qquad - \underbrace{\lambda \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\langle \mu _h, V^{k}_{h+1}\rangle _}_{\text{(iii)}}.\) 

In the following we will analyze the each of the three terms in (REF ) separately and derive high probability bound for each of them.
Term (i).
Since \((\Lambda _h^k)^{-1} \succ 0\) , by Cauchy-Schwarz inequality and Lemma REF , with probability at least \(1-\delta \) , we have
\(\begin{aligned}[b]&\phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\bigl [\bigl (V^{k}_{h+1} - \mathbb {P}_hV^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau )\bigr ] \Bigr ) \\& \le \Bigl \Vert \sum _{\tau =1}^{k-1}\phi (s_h^\tau ,a_h^\tau )\bigl [\bigl (V^{k}_{h+1} - \mathbb {P}_hV^{k}_{h+1}\bigr ) (s_h^\tau , a_h^\tau )\bigr ] \Bigr \Vert _{(\Lambda _h^k)^{-1}} \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda _h^k)^{-1}} \\& \le \sqrt{\beta _k(\delta )} \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda _h^k)^{-1}}.\end{aligned}\) 

Term (ii). Note that
\(\begin{aligned}[b]& \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau )\Bigr ) - r_h^k(s,a) \\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau )\Bigr ) - \phi (s,a)^\top w_h \\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau ) - \Lambda ^{k}_h w_h\Bigr ) \\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau ) - \sum _{\tau =1}^{k-1} \phi (s_h^\tau ,a_h^\tau )\phi (s_h^\tau ,a_h^\tau )^\top w_h- \lambda {I}w_h\Bigr ) \\&= \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau ) - \sum _{\tau =1}^{k-1} \phi (s_h^\tau ,a_h^\tau )r_h^\tau (s_h^\tau ,a_h^\tau ) - \lambda {I}w_h\Bigr ) \\&= -\lambda \phi (s,a)^\top (\Lambda ^{k}_h)^{-1} w_h,\end{aligned}\) 
where in the penultimate step, we used the fact \(r_h(s,a) = \langle \phi (s,a), w_h \rangle \)  from Definition REF . Applying Cauchy-Schwarz inequality we obtain,
\( -\lambda \phi (s,a)^\top (\Lambda ^{k}_h)^{-1} w_h &\le \lambda \Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}} \Vert w_h\Vert _{(\Lambda ^{k}_h)^{-1}} \\&\le \sqrt{\lambda }\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}} \Vert w_h\Vert _{2} \\&\le \sqrt{\lambda d}\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}}.\) 
Here the second inequality follows by observing that the smallest eigenvalue of \(\Lambda ^{k}_h\)  is at least \(\lambda \)  and thus the largest eigenvalue of \((\Lambda ^{k}_h)^{-1}\)  is at most \(1/\lambda \) . The last inequality follows from Definition REF . Combining (REF ) and (REF ) we get
\(\phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\Bigl ( \sum _{\tau =1}^{k-1} r_h^\tau (s_h^\tau ,a_h^\tau ) \phi (s_h^\tau ,a_h^\tau )\Bigr ) - r_h^k(s,a) \le \sqrt{\lambda d}\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}}.\) 

Term (iii).
Similar to (REF ), applying Cauchy-Schwarz inequality, we get
\(-\lambda \phi (s,a)^\top (\Lambda ^{k}_h)^{-1}\langle \mu _h, V^{k}_{h+1} \rangle _&\le \lambda \Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}} \Vert \langle \mu _h, V^{k}_{h+1} \rangle _\Vert _{(\Lambda ^{k}_h)^{-1}} \\& \le \sqrt{\lambda }\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}} \Vert \langle \mu _h, V^{k}_{h+1} \rangle _\Vert _2 \\& \le \sqrt{\lambda }\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}}\Bigl (\sum _{\tau =1}^d \Vert \mu _h^\tau \Vert _1^2\Bigr )^\frac{1}{2} \Vert V^{k}_{h+1}\Vert _{\infty } \\& \le H\sqrt{\lambda d}\Vert \phi (s,a)\Vert _{(\Lambda ^{k}_h)^{-1}}.\) 
Here the second inequality follows using the same observation we did for term (ii). The last inequality follows from \(\sum _{\tau =1}^d \Vert \mu _h^\tau \Vert _1^2 \le d\)  in Definition REF  and the clipping operation performed in Line REF  of Algorithm REF . Now combining (REF ), (REF ) and (REF ), and letting \(\lambda = 1\) , we get,
\(\bigl | \phi (s,a)^\top \widehat{\theta }^{k}_h - r_h^k(s,a) - \mathbb {P}_h V^{k}_{h+1} (s,a) \bigr | &\le (\sqrt{\beta _k(\delta )} + H\sqrt{d} + \sqrt{d})\Vert  \phi (s,a) \Vert _{(\Lambda ^{k}_h)^{-1}}\\&= (c_1 H\sqrt{d\log (Hdk/\delta )} + H\sqrt{d} + \sqrt{d})\Vert  \phi (s,a) \Vert _{(\Lambda ^{k}_h)^{-1}}\\&\le c_2 H\sqrt{d\log (Hdk/\delta )}\Vert  \phi (s,a) \Vert _{(\Lambda ^{k}_h)^{-1}},\) 

with probability \(1-\delta \)  for some constant \(c_2 > 0\) .
In addition, If we set \(\theta _h^k: \phi (\cdot ,\cdot )^\top \theta _h^k=r_h^k(\cdot ,\cdot )+\mathbb {P}_{h}V^{k}_{h+1}(\cdot ,\cdot )\)  to be the true parameter and \(\Delta \theta _h^k=\theta _h^k-\widehat{\theta }_h^k\)  to be the regression error, then from the analysis above we can derive that \(\Vert \Delta \theta _h^k\Vert _{\Lambda _h^k}\le \sqrt{\nu _k(\delta )}=c_2 H\sqrt{d\log (Hdk/\delta )}\) .
Lemma C.11 (stochastic upper confidence bound)
Let \(\lambda = 1\)  in Algorithm REF . For any \(\delta > 0 \) , conditioned on the event \(\mathcal {G}(K, H, \delta )\) , for any \((h, k) \in [H] \times [K]\)  and \((s,a) \in \times \) , with probability at least \(1- (\delta + c_0^M)\) , we have
\(l^{k}_{h}(s,a) \le 0,\) 
and
\(-l^{k}_{h}(s,a) \le \Bigl (\sqrt{\nu _k(\delta )} + \sqrt{\gamma _k(\delta )}\Bigr ) \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}},\) 
where \(c_0 = \Phi (1)\) .

Applying Lemma REF , for any \((h, k) \in [H] \times [K]\)  and \((s,a) \in \times \) , we have,
\(\bigl |r^k_h (s,a) +\mathbb {P}_{h}V^{k}_{h+1}(s,a) - \phi (s,a)^\top \widehat{\theta }_h^k \bigr | &\le c_2 H\sqrt{d\log (Hdk/\delta )}\\&=\sqrt{\nu _k(\delta )} \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}},\) 

with probability at least \(1-\delta \) .
As we are conditioning on the event \(\mathcal {G}(K, H, \delta )\) , for any \((h, k) \in [H] \times [K]\)  and \((s,a) \in \times \) , we have
\(\max _{j \in [M]} \bigl |\phi (s,a)^\top \zeta _h^{k,j} \bigr | \le \sqrt{\gamma _k(\delta )} \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}}.\) 
Now from the definition of model prediction error, using (REF ) and (REF ), we get, with probability \(1-\delta \) ,
\(\begin{aligned}[b]- l^{k}_{h}(s,a) &= Q^{k}_h(s,a) - r^k_h (s,a) - \mathbb {P}_{h}V^{k}_{h+1}(s,a) \\& = \min \lbrace \max _{j \in [M]}\phi (s,a)^\top (\widehat{\theta }_h^k + \zeta _h^{k,j}), H \rbrace  - r^k_h (s,a) - \mathbb {P}_{h}V^{k}_{h+1}(s,a) \\& \le \max _{j \in [M]}\phi (s,a)^\top (\widehat{\theta }_h^k + \zeta _h^{k,j}) - r^k_h (s,a) - \mathbb {P}_{h}V^{k}_{h+1}(s,a) \\&= \max _{j \in [M]}\phi (s,a)^\top \zeta _h^{k,j} - \bigl (r^k_h (s,a) +\mathbb {P}_{h}V^{k}_{h+1}(s,a) - \phi (s,a)^\top \widehat{\theta }_h^k \bigr ) \\&\le \bigl |r^k_h (s,a) +\mathbb {P}_{h}V^{k}_{h+1}(s,a) - \phi (s,a)^\top \widehat{\theta }_h^k \bigr | + \max _{j \in [M]} \bigl |\phi (s,a)^\top \zeta _h^{k,j} \bigr | \\& \le \Bigl (\sqrt{\nu _k(\delta )} + \sqrt{\gamma _k(\delta )}\Bigr ) \bigl \Vert \phi (s,a) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}},\end{aligned}\) 
Set \(\theta _h^k: \phi (\cdot ,\cdot )^\top \theta _h^k=r_h^k(\cdot ,\cdot )+\mathbb {P}_{h}V^{k}_{h+1}(\cdot ,\cdot )\)  to be the true parameter and \(\Delta \theta _h^k=\theta _h^k-\widehat{\theta }_h^k\)  to be the regression error. By the concentration part, conditioning on good events,
we have \(\Vert \Delta \theta _h^k\Vert _{\Lambda _h^k}\le \sqrt{\nu _k(\delta )}\)  and \(\Vert \xi ^{k,j}_{h}\Vert _{\Lambda _h^k}\le \sqrt{\gamma _k(\delta )}\)  for all \(j\in [M]\) .
For all \((h,k)\in [H]\times [K]\)  and any \((s,a)\in \times \) , we have
\(l^{k}_{h}(s,a) &= r^k_h (s,a) +\mathbb {P}_{h}V^{k}_{h+1}(s,a) - Q^{k}_h(s,a)\\&= r^k_h (s,a) +\mathbb {P}_{h}V^{k}_{h+1}(s,a) - \min \bigl \lbrace H , \max _{j\in [M]}\phi (s, a)^\top (\widehat{\theta }^k_h + \xi ^{k,j}_{h}) \bigr \rbrace ^+ \\&\le \max \lbrace \phi (s,a)^\top \Delta \theta _h^k-\max _{j\in [M]}\phi (s, a)^\top \xi ^{k,j}_{h},0\rbrace \) 
Now we prove that with high probability, \(\max _{j\in [M]}\phi (s, a)^\top \xi ^{k,j}_{h}-\phi (s,a)^\top \Delta \theta _h^k\ge 0\)  for all \((s,a)\in \times \) . Note that the inequality still holds if we scale \(\phi (s,a)\) . Now we assume all \(\phi (s,a)\)  satisfy \(\Vert \phi (s,a)\Vert _{(\Lambda _h^k)^{-1}}=1\) . Define \((\epsilon )\)  to be a \(\epsilon \) -cover of the ellipsoid \(\lbrace \phi |\Vert \phi \Vert _{(\Lambda _h^k)^{-1}}=1\rbrace \)  with respect to norm \(\Vert \cdot \Vert _{(\Lambda _h^k)^{-1}}\)  and \(\log |(\epsilon )|=\widetilde{O}(d\log (\frac{1}{\epsilon }))\) . For all \(j \in [M]\) , we have,
\(\lbrace \xi ^{k,j}_{h}\rbrace  \sim \bigl (0,4\nu _k(\delta )(\Lambda ^{k}_h)^{-1} \bigr ).\) 
Thus, for all \(j \in [M]\)  and for all \(\phi \in (\epsilon )\)  , we have
\(\bigl \lbrace \phi ^\top \xi ^{k,j}_{h}\bigr \rbrace  \sim \Bigl (0,4\nu _k(\delta )\Vert \phi \Vert ^2_{(\Lambda ^{k}_h)^{-1}}\Bigr ).\) 
Now, for all \(j\in [M]\)  and for all \(\phi \in (\epsilon )\) , we have
\(\mathbb {P}\Bigl (\phi ^\top \xi ^{k,j}_{h} - 2\sqrt{\nu _k(\delta )}\Vert \phi \Vert _{(\Lambda ^{k}_h)^{-1}} \ge 0 \Bigr ) = \Phi (-1).\) 
Now
\(\begin{aligned}[b]\mathbb {P}\Bigl (\max _{j\in [M]}\phi ^\top \xi ^{k,j}_{h} - 2\sqrt{\nu _k(\delta )}\Vert \phi \Vert _{(\Lambda ^{k}_h)^{-1}} \ge 0 \Bigr ) &\ge 1 - (1-\Phi (-1))^M\\&= 1 - \Phi (1)^M \\&= 1 - c_0^M,\end{aligned}\) 
By union bound, with probability \(1-|(\epsilon )|c_0^M\) , the above bound holds for all elements in \(\)  simultaneously.
Now condition on the previous event, for \(\phi =\phi (s,a)\) , we can find a \(\phi ^{\prime }\in (\epsilon )\)  such that \(\Vert \phi -\phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}}\le \epsilon \) . Define \(\Delta \phi =\phi -\phi ^{\prime }\) .
\(\phi ^\top \xi ^{k,j}_{h}-\phi ^\top \Delta \theta _h^k&=\phi ^{\prime \top }\xi ^{k,j}_{h}-\phi ^{\prime \top }\Delta \theta _h^k+\Delta \phi ^\top \xi ^{k,j}_{h}+\Delta \phi ^\top \Delta \theta _h^k\\&\ge \phi ^{\prime \top }\xi ^{k,j}_{h} - 2\sqrt{\nu _k(\delta )}\Vert \phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}} + \sqrt{\nu _k(\delta )}\Vert \phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}}-\epsilon \Vert \xi ^{k,j}_{h}\Vert _{\Lambda ^{k}_h}-\epsilon \Vert \Delta \theta _h^k\Vert _{\Lambda ^{k}_h}\\&\ge \phi ^{\prime \top }\xi ^{k,j}_{h} - 2\sqrt{\nu _k(\delta )}\Vert \phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}} + \sqrt{\nu _k(\delta )}\Vert \phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}}-\epsilon \sqrt{\gamma _k(\delta )}-\epsilon \sqrt{\nu _k(\delta )}\\\) 
Set \(\epsilon =\frac{\sqrt{\nu _k(\delta )}}{\sqrt{\gamma _k(\delta )}+\sqrt{\nu _k(\delta )}}=\widetilde{O}(\frac{1}{\sqrt{d}})\)  and we have, with probability \(1-|(\epsilon )|c_0^M\) ,
\(\max _{j\in [M]}\phi ^\top \xi ^{k,j}_{h}-\phi ^\top \Delta \theta _h^k&\ge \max _{j\in [M]}\phi ^{\prime \top }\xi ^{k,j}_{h} - 2\sqrt{\nu _k(\delta )}\Vert \phi ^{\prime }\Vert _{(\Lambda ^{k}_h)^{-1}}\\&\ge 0.\) 
Finally we have conditioning on good event \(\mathcal {G}(K, H, \delta )\) , with probability at least \(1-|(\epsilon )|c_0^M\) , for all \((s,a)\in \mathcal {S}\times \)  , \(l_h^k(s,a)\le 0\) . As \(\log |(\epsilon )|=\widetilde{O}(d\log (\frac{1}{\epsilon }))\) , we can set \(M=\widetilde{O}(\frac{d\log (1/\epsilon \delta )}{\log (1/c_0)})=\widetilde{O}(d)\)  to have probability \(1-\delta \) .

Regret Bound
Definition C.12 (Filtrations)
We denote the \(\sigma \) -algbera generated by the set \(\)  using \(\sigma ()\) . We define the following filtrations:
\(^k &\stackrel{\text{def}}{=}\sigma \left(\lbrace (s_t^i, a_t^i, r_t^i)\rbrace _{\lbrace i,t\rbrace  \in [k-1]\times [H]}\,\ \bigcup \,\ \lbrace \xi ^{i,j}_{t}\rbrace _{\lbrace i,t,j\rbrace  \in [k-1]\times [H]\times [M]}\right),\\_{h,1}^k &\stackrel{\text{def}}{=}\sigma \left(^k \,\ \bigcup \,\ \lbrace (s_t^k, a_t^k, r_t^k)\rbrace _{t\in [h]}\,\ \bigcup \,\ \lbrace \xi ^{k,j}_{t}: t \le h,\,\ 1\le j \le M\rbrace \right),\\_{h,2}^k &\stackrel{\text{def}}{=}\sigma \left(_{h,1}^k \,\ \bigcup \,\ \lbrace x_{h+1}^k\rbrace \right).\) 

Lemma C.13 (Lemma 4.2 in [6]})
It holds that
\( \begin{aligned}[b]\mathrm {Regret}(T) &= \sum _{k=1}^K \left(V_1^{*}(s_1^k) - V_1^{\pi ^k}(s_1^k)\right) \\&= \underbrace{\sum _{k=1}^K \sum _{ t=1}^H \mathbb {E}_{\pi ^*} \left[ \langle Q_h^k(s_h, \cdot ), \pi _h^*(\cdot \mid s_h) - \pi _h^k(\cdot \mid s_h) \rangle {\,\big |\,}s_1 = s_1^k\right]}_{\text{(i)}} \\& \qquad + \underbrace{\sum _{k=1}^K \sum _{ t=1}^H _h^k}_{\text{(ii)}} \ + \ \underbrace{\sum _{k=1}^K \sum _{ t=1}^H _h^k}_{\text{(iii)}} \\& \qquad + \underbrace{\sum _{k=1}^K \sum _{h=1}^H \left( \mathbb {E}_{\pi ^*}\left[l^{k}_{h}(s_h,a_h) \mid s_1 = s_1^k \right] - l^{k}_{h}(s_h^k,a_h^k) \right)}_{\text{(iv)}},\end{aligned}\) 
where
\(_h^k &\langle (Q_h^k - Q_h^{\pi ^k})(s_h^k, \cdot ), \pi _h^k(\cdot ,s_h^k)\rangle - (Q_h^k-Q_h^{\pi ^k})(s_h^k,a_h^k),\\_h^k &\mathbb {P}_h( (V_{h+1}^k - V_{h+1}^{\pi ^k}))(s_h^k, a_h^k) - (V_{h+1}^k-V_{h+1}^{\pi ^k})(s_h^k).\) 

Lemma C.14 
For the policy \(\pi _h^k\)  at time-step \(k\)  of episode \(h\) , it holds that
\(\sum _{k=1}^K \sum _{ t=1}^H \mathbb {E}_{\pi ^*} \left[ \langle Q_h^k(s_h, \cdot ), \pi _h^*(\cdot \mid s_h) - \pi _h^k(\cdot \mid s_h) \rangle \mid s_1 = s_1^k\right] \le 0,\) 
where \(T = HK\) .

Obvious from the observation that \(\pi ^k_h\)  acts greedily with respect to \(Q_h^k\) . Note that if \(\pi _h^k = \pi _h^*\)  then the difference is 0. Else the difference is negative since \(\pi _h^k\)  is deterministic with respect to its action-values meaning it takes a value of 1 where \(\pi _h^*\)  would take a value of 0 and \(Q_h^k\)  would have the greatest value at the state-action pair that \(\pi _h^k\)  equals one.
Lemma C.15 (Bound on Martingale Difference Sequence) 
For any \(\delta >0\) , it holds with probability \(1-2\delta /3\)  that
\( \sum _{k=1}^K \sum _{ t=1}^H _h^k + \sum _{k=1}^K \sum _{ t=1}^H _h^k \le 2\sqrt{2H^2T\log (3/\delta )}.\) 

Recall that
\(_h^k &\langle (Q_h^k - Q_h^{\pi ^k})(s_h^k, \cdot ), \pi _h^k(\cdot ,s_h^k)\rangle - (Q_h^k-Q_h^{\pi ^k})(s_h^k,a_h^k),\\_h^k &\mathbb {P}_h( (V_{h+1}^k - V_{h+1}^{\pi ^k}))(s_h^k, a_h^k) - (V_{h+1}^k-V_{h+1}^{\pi ^k})(s_h^k).\) 
Note that in line REF  of Algorithm REF , we truncate \(Q_h^k\)  to the range \([0,H-h]\) . Thus for any \((k,t) \in [K]\times [H]\) , we have, \(|_h^k| \le 2H\) . Moreover, since \(\mathbb {E}[_h^k|_{h,1}^k] = 0\) , \(_h^k\)  is a martingale difference sequence. So, applying Azuma-Hoeffding inequality we have with probability at least \(1-\delta /3\) ,
\(\sum _{k=1}^K \sum _{ t=1}^H _h^k \le \sqrt{2H^2T\log (3/\delta )},\) 
where \(T = KH\) .
Similarly, \(_h^k\)  is a martingale difference sequence since for any \((k,t) \in [K]\times [H]\) , \(|_h^k| \le 2H\)  and \(\mathbb {E}[_h^k|_{h,1}^k] = 0\) . Applying Azuma-Hoeffding inequality we have with probability at least \(1-\delta /3\) ,
\(\sum _{k=1}^K \sum _{ t=1}^H _h^k \le \sqrt{2H^2T\log (3/\delta )}.\) 
Applying union bound on (REF ) and (REF ) gives (REF ) and completes the proof.
Lemma C.16 
Let \(\lambda = 1\)  in Algorithm REF . For any \(\delta > 0 \) , conditioned on the event \(\mathcal {G}(K, H, \delta )\) , we have,
\(\sum _{k=1}^K \sum _{h=1}^H \bigl ( \mathbb {E}_{\pi ^*}\left[l^{k}_{h}(s_h,a_h) | s_1 = s_1^k \bigr ] - l^{k}_{h}(s_h^k,a_h^k) \right) \le \bigl (\sqrt{\nu _K(\delta )} + \sqrt{\gamma _K(\delta )}\bigr ) \sqrt{2dHT\log (1+K)},\) 
with probability \(1- (\delta + c_0^M)\) .

By Lemma REF , with probability \(1- (\delta + c_0^M)\)  it holds that
\(\sum _{k=1}^K \sum _{h=1}^H \mathbb {E}_{\pi ^*}\left[l^{k}_{h}(s_h,a_h) | s_1 = s_1^k \right] \le 0,\) 
and
\( \begin{aligned}[b]\sum _{k=1}^K \sum _{h=1}^H - l^{k}_{h}(s_h^k,a_h^k) &\le \sum _{k=1}^K \sum _{h=1}^H \Bigl (\sqrt{\nu _k(\delta )} + \sqrt{\gamma _k(\delta )}\Bigr ) \bigl \Vert \phi (s_h^k,a_h^k) \bigr \Vert _{(\Lambda ^{k}_h)^{-1}}\\&\le \Bigl (\sqrt{\nu _K(\delta )} + \sqrt{\gamma _K(\delta )}\Bigr ) \sum _{k=1}^K \sum _{h=1}^H \bigl \Vert \phi (s_h^k,a_h^k)\bigr \Vert _{(\Lambda ^{k}_h)^{-1}}\\&\le \Bigl (\sqrt{\nu _K(\delta )} + \sqrt{\gamma _K(\delta )}\Bigr ) \sum _{h=1}^H \sqrt{K} \Bigl (\sum _{k=1}^K \bigl \Vert \phi (s_h^k,a_h^k) \bigr \Vert ^2_{(\Lambda ^{k}_h)^{-1}}\Bigr )^{1/2} \\&\le \Bigl (\sqrt{\nu _K(\delta )} + \sqrt{\gamma _K(\delta )}\Bigr ) H\sqrt{2dK\log (1+K)}\\&=\Bigl (\sqrt{\nu _K(\delta )} + \sqrt{\gamma _K(\delta )}\Bigr ) \sqrt{2dHT\log (1+K)}.\end{aligned}\) 
Here the second inequality follows from the fact that both \(\nu _k(\delta )\)  and \(\gamma _k(\delta )\)  are increasinig in \(k\) . The third and the fourth inequalities follow from Cauchy-Schwarz inequality and Lemma REF . Combining (REF ) and (REF ) completes the proof.
Lemma C.17 (Good event probability) 
For any \(K \in \mathbb {N}\)  and any \(\delta > 0\) , we would have the event \(\mathcal {G}(K, H, \delta ^{\prime })\)  with probability at least \(1-\delta \) , where \(\delta ^{\prime } = \delta /MT\) .

By Lemma REF , we have, for any fixed \(t\)  and \(k\) , the event \(\mathcal {G}^k_h(\xi ,\delta ^{\prime })\)  occurs with probability at least \(1- M\delta ^{\prime }\) . Recall from Definition REF  that,
\(\mathcal {G}(K, H, \delta ^{\prime }) = \bigcap _{k \le K}\bigcap _{h \le H}\mathcal {G}^k_h(\xi ,\delta ^{\prime }).\) 
Now taking union bound over all \((t,k) \in [H]\times [K]\) , we have
\(\mathbb {P}(\bigcap _{k \le K}\bigcap _{h \le H}\mathcal {G}^k_h(\xi ,\delta ^{\prime })) \ge 1 - MT\delta ^{\prime } = 1- \delta ,\) 
which completes the proof.
Theorem C.18  Let \(\lambda = 1\) , \(\sigma = \widetilde{O}(H\sqrt{d})\)  and \(M = d\log (\delta /9)/\log c_0\) , where \(c_0 = \Phi (1)\)  and \(\delta \in (0,1]\) . Under Definition REF , the regret of Algorithm REF  satisfies
\(\text{Regret}(T) \le \widetilde{\mathcal {O}}(d^{3/2} H^{3/2} \sqrt{T}),\) 
with probability at least \(1-\delta \) .

[Proof of Theorem REF ]
Let \(\delta ^{\prime } = \delta /9\) . From Lemma REF , the event \(\mathcal {G}(K, H,\delta ^{\prime })\)  happens with probability \(1- \delta ^{\prime }\) . Combining Lemma REF  and Lemma REF  we have that the event \(\mathcal {G}(K, H,\delta ^{\prime })\)  occurs and it holds that
\(\sum _{k=1}^K \sum _{h=1}^H \left( \mathbb {E}_{\pi ^*}\left[l^{k}_{h}(s_h,a_h) | s_1 = s_1^k \right] - l^{k}_{h}(s_h^k,a_h^k) \right) \le \Bigl (\sqrt{\nu _K(\delta ^{\prime })} + \sqrt{\gamma _K(\delta ^{\prime })}\Bigr ) \sqrt{2dHT\log (1+K)},\) 
with probability at least \((1-\delta ^{\prime })(1- (\delta ^{\prime } + c_0^M))\) . Note that \(c_0^M = \delta ^{\prime }\)  and \((1-\delta ^{\prime })(1- (\delta ^{\prime } + c_0^M)) > 1 - 3\delta ^{\prime } = 1 - \delta /3\) .
The martingale inequalities from Lemma REF  happens with probability \(1-2\delta /3\) .
Applying union bound on (REF ), (REF ) and (REF ) gives the final regret bound of \(\widetilde{\mathcal {O}}(d^{3/2}H^{3/2}\sqrt{T})\)  completes the proof.

Auxiliary lemmas 
This section presents several auxiliary lemmas and their proofs.
Gaussian Concentration
Lemma D.1 (Gaussian Concentration [7]})
Consider a \(d\) -dimensional multivariate normal distribution \(\eta \sim (0, A\Lambda ^{-1})\)  where \(A\)  is a scalar. For any \(\delta > 0\) , with probability \(1-\delta \) ,
\(\Vert \eta \Vert _{\Lambda } \le c\sqrt{dA\log (d/\delta )},\) 
where \(c\)  is some absolute constant. For \(d=1\) , we have \(c=\sqrt{2}\) .

Lemma D.2
Consider a \(d\) -dimensional multivariate normal distribution \( (0, A\Lambda ^{-1})\)  where \(A\)  is a scalar. Let \(\eta _1, \eta _2, \ldots ,\eta _M\)  be \(M\)  independent samples from the distribution. Then for any \(\delta > 0\)
\(\mathbb {P}\left(\max _{j \in [M]}\Vert \eta _{j}\Vert _{\Lambda } \le c\sqrt{dA\log (d/\delta )}\right) \ge 1- M\delta ,\) 
where \(c\)  is some absolute constant.

From Lemma REF , for a fixed \(j \in [M]\) , with probability at least \(1-\delta \)  we would have
\(\Vert \eta \Vert _{\Lambda } \le c\sqrt{dA\log (d/\delta )}.\) 
Applying union bound over all \(M\)  samples completes the proof.

Inequalities for summations
Lemma D.3 (Lemma D.1 in  [5]})
Let \(\Lambda _h = \lambda I + \sum _{i=1}^t \phi _i\phi _i^\top \) , where \(\phi _i \in \mathbb {R}^d\)  and \(\lambda > 0\) . Then it holds that
\(\sum _{i=1}^t \phi _i^\top (\Lambda _h)^{-1}\phi _i \le d.\) 

Lemma D.4 (Lemma 11 in  [9]})
Using the same notation as defined in this paper
\(\sum _{k=1}^K \bigl \Vert \phi (s_h^k,a_h^k)\bigr \Vert ^2_{(\Lambda ^k_h)^{-1}} \le 2d\log \Bigl (\frac{\lambda + K}{\lambda }\Bigr ).\) 

Lemma D.5 
Let \(A \in \mathbb {R}^{d\times d}\)  be a positive definite matrix where its largest eigenvalue \(\lambda _{max}(A) \le \lambda \) . Let \(x_1, \ldots , x_{k}\)  be \(k\)  vectors in \(\mathbb {R}^d\) . Then it holds that
\(\Bigl \Vert A\sum _{i=1}^{k}x_i \Bigr \Vert  \le \sqrt{\lambda k}\Bigl (\sum _{i=1}^{k}\Vert x_i\Vert ^2_{A}\Bigr )^{1/2}.\) 

For any vector \(v \in \mathbb {R}^d\) ,
\(\begin{split}\Vert Av\Vert  &= \Vert A^{1/2} A^{1/2} v\Vert  \\&\le \Vert A^{1/2}\Vert  \Vert A^{1/2} v\Vert  \\&= \Vert A^{1/2}\Vert  \Vert v\Vert _A.\end{split}\) 
Here the inequality follows from the definition of the operator norm \(\Vert A^{1/2}\Vert \) . Moreover, \(\Vert A^{1/2}\Vert  \le \sqrt{\lambda }\)  since \(\lambda _{max}(A) \le \lambda \) . Thus,
\( \left\Vert A\sum _{i=1}^{k}x_i\right\Vert  \le \sqrt{\lambda } \left\Vert \sum _{i=1}^{k}x_i \right\Vert _A.\) 
Now by Cauchy-Schwarz inequality,
\(\left\Vert \sum _{i=1}^{k} x_i \right\Vert _A^2 &= \sum _{i=1}^{k} \sum _{j=1}^{k} x_i^\top A x_j \\&\le \sum _{i=1}^{k}\sum _{j=1}^{k} \Vert x_i\Vert _A \Vert x_j\Vert _A \\&= \left(\sum _{i=1}^{k} \Vert x_i\Vert _A\right)^2 \\&\le k \sum _{i=1}^{k} \Vert x_i\Vert _A^2.\) 
Combining (REF ) and (REF ), proves the lemma.

Covering numbers and self-normalized processes
Lemma D.6 (Lemma D.4 in [5]}) 
Let \(\lbrace s_i\rbrace _{i=1}^\infty \)  be a stochastic process on state space \(\)  with corresponding filtration \(\lbrace _i\rbrace _{i=1}^\infty \) . Let \(\lbrace \phi _i\rbrace _{i=1}^\infty \)  be an \(\mathbb {R}^d\) -valued stochastic process where \(\phi _i \in _{i-1}\) , and \(\Vert \phi _i\Vert  \le 1\) . Let \(\Lambda _k = \lambda I + \sum _{i=1}^k \phi _i \phi _i^\top \) . Then for any \(\delta > 0\) , with probability at least \(1-\delta \) , for all \(k \ge 0\) , and any \(V \in \)  with \(\sup _{s \in } |V(s)| \le H\) , we have
\(\Bigl \Vert \sum _{i=1}^k \phi _i \bigl \lbrace  V(s_i) - \mathbb {E}[V(s_i) {\,|\,}_{i-1} ]\bigr \rbrace  \Bigr \Vert ^2_{\Lambda _k^{-1}} \le 4H^2 \Bigl [\frac{d}{2}\log \Bigl (\frac{k+\lambda }{\lambda }\Bigr ) + \log {\frac{_\varepsilon }{\delta }}\Bigr ] + \frac{8k^2\epsilon ^2}{\lambda },\) 
where \(_\varepsilon \)  is the \(\varepsilon \) -covering number of \(\)  with respect to the distance \(\text{dist}(V,V^{\prime }) = \sup _{s \in } |V(s) - V^{\prime }(s)|\) .

Lemma D.7 (Covering number of Euclidean ball, [7]} ) 
For any \(\varepsilon > 0\) , the \(\varepsilon \) -covering number, \(_\varepsilon \) , of the Euclidean ball of radius \(B > 0\)  in \(\mathbb {R}^d\)  satisfies
\(_\varepsilon \le \Bigl (1+ \frac{2B}{\varepsilon }\Bigr )^d \le \Bigl ( \frac{3B}{\varepsilon }\Bigr )^d .\) 

Lemma D.8 
Consider a class of functions \(: \rightarrow \)  which has the following parametric form
\(V(\cdot ) = \Bigl \langle \min \bigl \lbrace  \phi (\cdot ,\cdot )^\top \theta , H\bigr \rbrace ^{+}, \pi (\cdot {\,|\,}\cdot ) \Bigr \rangle _{},\) 
where the parameter \(\theta \)  satisfies \(\Vert \theta \Vert  \le B\)  and for all \((s,a) \in \times \) , we have \(\Vert \phi (s,a)\Vert  \le 1\) . If \(_{,\varepsilon }\)  denotes the \(\varepsilon \) -covering number of \(\)  with respect to the distance \(\text{dist}(V,V^{\prime }) = \sup _{s\in } |V(s) - V^{\prime }(s)|\) , then
\(\log _{,\varepsilon } \le d\log (1+ 2B/\varepsilon ) \le d\log (3B/\varepsilon ).\) 

Consider any two functions \(V_1, V_2 \in \)  with parameters \(\theta _1\)  and \(\theta _2\) , respectively. Note that \(\min \lbrace \cdot , H\rbrace \)  is a contraction mapping. Thus we have
\(\text{dist}(V_1, V_2) &\le \sup _{s} \bigl | \langle \phi (s,\cdot )^\top \theta _1 - \phi (s,\cdot )^\top \theta _2, \pi (\cdot \mid s) \rangle _{} \bigr | \\& \le \sup _{\phi :\Vert \phi \Vert \le 1} \bigl |\phi ^\top \theta _1 - \phi ^\top \theta _2 \bigr | \\& = \sup _{\phi :\Vert \phi \Vert \le 1} \bigl |\phi ^\top \bigl (\theta _1 - \theta _2\bigr ) \bigr | \\& \le \sup _{\phi :\Vert \phi \Vert \le 1} \Vert \theta _1- \theta _2 \Vert _2 \Vert \phi \Vert _2 \\&= \Vert \theta _1 - \theta _2\Vert ,\) 
where the second inequality follows from the triangle inequality and the third inequality follows from the Cauchy-Schwarz inequality.
If \(_{\theta ,\varepsilon }\)  denotes the \(\varepsilon \) -covering number of \(\lbrace \theta \in \mathbb {R}^d {\,|\,}\Vert \theta \Vert  \le B \rbrace \) , Lemma  REF  implies
\(_{\theta ,\varepsilon } \le \Bigl (1+ \frac{2B}{\varepsilon }\Bigr )^d \le \Bigl ( \frac{3B}{\varepsilon }\Bigr )^d.\) 
Let \(_{\theta ,\varepsilon }\)  be an \(\varepsilon \) -cover of \(\lbrace \theta \in \mathbb {R}^d {\,|\,}\Vert \theta \Vert  \le B \rbrace \)  with cardinality \(_{\theta ,\varepsilon }\) . Consider any \(V_1 \in \) . By (REF ), there exists \(\theta _2 \in _{\theta ,\varepsilon }\)  such that \(V_2\)  parameterized by \(\theta _2\)  satisfies \(\text{dist}(V_1,V_2)\le \varepsilon \) . Thus we have
\(\log _{,\varepsilon } \le \log _{\theta ,\varepsilon } \le d\log (1+ 2B/\varepsilon ) \le d\log (3B/\varepsilon ),\) 
which concludes the proof.

Experiment Details
In this section we include the figure for the RiverSwim environment from [12]}.
<FIGURE>