Abstract

Offline reinforcement learning, which aims at optimizing sequential decision-making strategies with historical data, has been extensively applied in real-life applications. State-Of-The-Art algorithms usually leverage powerful function approximators (e.g. neural networks) to alleviate the sample complexity hurdle for better empirical performances. Despite the successes, a more systematic understanding of the statistical complexity for function approximation remains lacking. Towards bridging the gap, we take a step by considering offline reinforcement learning with differentiable function class approximation (DFA). This function class naturally incorporates a wide range of models with nonlinear/nonconvex structures. Most importantly, we show offline RL with differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning (PFQL) algorithm, and our results provide the theoretical basis for understanding a variety of practical heuristics that rely on Fitted Q-Iteration style design. In addition, we further improve our guarantee with a tighter instance-dependent characterization. We hope our work could draw interest in studying reinforcement learning with differentiable function approximation beyond the scope of current research.

1 Introduction↩︎

Offline reinforcement learning [@lange2012batch; @levine2020offline] refers to the paradigm of learning a policy in the sequential decision making problems, where only the logged data are available and were collected from an unknown environment (Markov Decision Process / MDP). Inspired by the success of scalable supervised learning methods, modern reinforcement learning algorithms (e.g. [@silver2017mastering]) incorporate high-capacity function approximators to acquire generalization across large state-action spaces and have achieved excellent performances along a wide range of domains. For instance, there are a huge body of deep RL-based algorithms that tackle challenging problems such as the game of Go and chess [@silver2017mastering; @schrittwieser2020mastering], Robotics [@gu2017deep; @levine2018learning], energy control [@degrave2022magnetic] and Biology [@mahmud2018applications; @popova2018deep]. Nevertheless, practitioners also noticed that algorithms with general function approximators can be quite data/sample inefficient, especially for deep neural networks where the models may require million of steps for tuning the large number of parameters they contain.¹

On the other hand, statistical analysis has been actively conducted to understand the sample/statistical efficiency for reinforcement learning with function approximation, and fruitful results have been achieved under the respective model representations [@munos2003error; @chen2019information; @yang2019sample; @du2019provably; @sun2019model; @modi2020sample; @jin2020provably; @ayoub2020model; @zanette2020learning; @jin2021bellman; @du2021bilinear; @jin2021pessimism; @zhou2021nearly; @xie2021bellman; @min2021variance; @nguyen2021finite; @li2021sample; @zanette2021provable; @yin2022linear; @uehara2021representation; @cai2022reinforcement]. However, most works consider linear model approximators (e.g. linear (mixture) MDPs) or its variants. While the explicit linear structures make the analysis trackable (linear problems are easier to analyze), they are unable to reveal the sample/statistical complexity behaviors of practical algorithms that apply powerful function approximations (which might have complex structures).

In addition, there is an excellent line of works tackling provably efficient offline RL with general function approximation (e.g. [@chen2019information; @xie2021bellman; @zhan2022offline]). Due to the generic function approximation class considered, those complexity bounds are usually expressed in the standard worst-case fashion \(O(V_{\max}^2\sqrt{\frac{1}{n}})\) which lack the characterizations of individual instance behaviors. However, as mentioned in [@zanette2019tighter], practical reinforcement learning algorithms often perform far better than what these problem-independent bounds would suggest.

These observations motivate us to consider function approximation schemes that can help address the existing limitations. In particular, in this work we consider offline reinforcement learning with differentiable function class approximations. Its definition is given in below.

Definition 1 (Parametric Differentiable Function Class). Let \(\mathcal{S},\mathcal{A}\) be arbitrary state, action spaces and a feature map \(\phi(\cdot,\cdot):\mathcal{S}\times\mathcal{A}\rightarrow \Psi\subset\mathbb{R}^m\). The parameter space \(\Theta\in\mathbb{R}^d\). Both \(\Theta\) and \(\Psi\) are compact spaces. Then the parametric function class (for a model \(f:\mathbb{R}^d\times \mathbb{R}^m\rightarrow \mathbb{R}\)) is defined as \[\mathcal{F}:=\{f(\theta,\phi(\cdot,\cdot)):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},\theta\in\Theta\}\] that satisfies differentiability/smoothness condition: 1. for any \(\phi\in \mathbb{R}^m\), \(f(\theta,\phi)\) is third-time differentiable with respect to \(\theta\); 2. \(f,\partial_\theta f,\partial^2_{\theta,\theta} f,\partial^3_{\theta,\theta,\theta} f\) are jointly continuous for \((\theta,\phi)\).

Remark 1. Differentiable Function Class was recently proposed for studying Off-Policy Evaluation (OPE) Problem [@zhang2022off] and we adopt it here for the policy learning task. Note by the compactness of \(\Theta\), \(\Psi\) and continuity, there exists constants \(C_\Theta,B_{\mathcal{F}},\kappa_1,\kappa_2,\kappa_3>0\) that bounds: \(\left\lVert\theta\right\rVert_2\leq C_\Theta,|f(\theta,\phi(s,a))|\leq B_{\mathcal{F}},\left\lVert\nabla_\theta f(\theta,\phi(s,a))\right\rVert_2\leq \kappa_1,\left\lVert\nabla^2_{\theta\theta} f(\theta,\phi(s,a))\right\rVert_2\leq \kappa_2,\left\lVert\nabla^3_{\theta\theta\theta} f(\theta,\phi(s,a))\right\rVert_2\leq \kappa_3\) for all \(\theta\in\Theta,\; s,a\in\mathcal{S}\times\mathcal{A}\).²

Why consider differentiable function class (Definition 1)? There are two main reasons why differentiable function class is worth studying for reinforcement learning.

Due to the limitation of statistical tools, existing analysis in reinforcement learning usually favor basic settings such as tabular MDPs (where the state space and action space are finite [@azar2013minimax; @azar2017minimax; @sidford2018near; @jin2018q; @cui2020plug; @agarwal2020model; @yin2021near; @yin2021nearoptimal; @li2020sample; @ren2021nearly; @xie2021policy; @li2022settling; @zhang2022horizon; @qiao2022sample; @cui2022offline]) or linear MDPs [@yang2020reinforcement; @jin2020provably; @wang2020reward; @jin2021pessimism; @ding2021provably; @wang2021statistical; @min2021variance] / linear Mixture MDPs [@modi2020sample; @cai2020provably; @zhang2021reward; @zhou2021provably; @zhou2021nearly] (where the transition dynamic admits linear structures) so that well-established techniques (e.g. from linear regression) can be applied. In addition, subsequent extensions are often based on linear models (e.g. Linear Bellman Complete models [@zanette2020learning] and Eluder dimension [@russo2013eluder; @jin2021bellman]). Differentiable function class strictly generalizes over the previous popular choices, i.e. by choosing \(f(\theta,\phi)=\langle \theta,\phi\rangle\) or specifying \(\phi\) to be one-hot representations, and is far more expressive as it encompasses nonlinear approximators.
Practically speaking, the flexibility of selecting model \(f\) provides the possibility for handling a variety of tasks. For instance, when \(f\) is specified to be neural networks, \(\theta\) corresponds to the weights of each network layers and \(\phi(\cdot,\cdot)\) corresponds to the state-action representations (which is induced by the network architecture). When facing with easier tasks, we can deploy simpler model \(f\) such as polynomials. Yet, our statistical guarantee is not affected by the specific choices as we can plug the concrete form of model \(f\) into Theorem 3 to obtain the respective bounds (we do not need separate analysis for different tasks).

Reinforcement learning with function approximation. RL with function approximation has a long history that can date back to [@bradtke1996linear; @tsitsiklis1996analysis]. Later, it draws significant interest for the finite sample analysis [@jin2020provably; @yang2019sample]. Since then, people put tremendous efforts towards generalizing over linear function approximations and examples include Linear Bellman complete models [@zanette2020learning], Eluder dimension [@russo2013eluder; @jin2021bellman], linear deterministic \(Q^\star\) [@wen2013efficient] or Bilinear class [@du2021bilinear]. While those extensions are valuable, the structure conditions assumed usually make the classes hard to track beyond the linear case. For example, the practical instances of Eluder Dimension are based on the linear-in-feature (or its transformation) representations (Section 4.1 of [@wen2013efficient]). As a comparison, differentiable function class contains a range of functions that are widely used in practical algorithms [@riedmiller2005neural].

Offline RL with general function approximation (GFA). Another interesting thread of work considered offline RL with general function approximation [@ernst2005tree; @chen2019information; @liu2020provably; @xie2021bellman] which only imposes realizability and completeness/concentrability assumptions. The major benefit is that the function hypothesis can be arbitrary with no structural assumptions and it has been shown that offline RL with GFA is provably efficient. However, the generic form of functions in GFA makes it hard to go beyond worst-case analysis and obtain fine-grained instance-dependent learning bounds similar to those under linear cases. On the contrary, our results with DFA can be more problem adaptive by leveraging gradients and higher order information.

In addition to the above, there are more connected works. [@zhang2022off] first considers the differentiable function approximation (DFA) for the off-policy evaluation (OPE) task and builds the asymptotic theory, [@fan2020theoretical] analyzes the deep Q-learning with the specific ReLu activations, and [@kallus2020double] considers semi-parametric / nonparametric methods for offline RL (as opposed to our parametric DFA in 1). These are nice complementary studies to our work.

Table 1: Suboptimality gaps for different algorithms with differentiable function class 1. Here we omit the higher order term for clear comparison. With Concentrability, we can only achieve the worst case bound that does not explicit depend on the function model \(f\). With the stronger uniform coverage 3, better instance-dependent characterizations become available. Here \(C_\mathrm{eff}\) is in 2, \(\Sigma^\star\) in 3, \(\Lambda^\star\) in 4 and \(\epsilon_{\mathcal{F}}\) in 1.
Algorithm	Assumption	Suboptimality Gap \(v^\star-v^{\widehat{\pi}}\)
VFQL, Theorem 2	Concentrability 2	\(\sqrt{C_{\mathrm{eff}}}H\cdot\sqrt{\frac{H^2d+\lambda C^2_\Theta}{K}}+\sqrt[\frac{1}{4}]{\frac{H^3d\epsilon_{\mathcal{F}}}{K}} +\sqrt{C_\mathrm{eff} H^3 \epsilon_{\mathcal{F}}}+H\epsilon_{\mathcal{F}}\)
PFQL, Theorem 3	Uniform Coverage 3	\(\sum_{h=1}^H 16 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Sigma^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\)
VAFQL, Theorem 4	Uniform Coverage 3	\(16 d\cdot\sum_{h=1}^H \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Lambda^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\)

1.2 Our contribution↩︎

We provide the first Instance-dependent offline learning bound under non-linear function approximation. Informally, we show that (up to a lower order term) the natural complexity measure is proportional to \(\sum_{h=1}^H\mathbb{E}_{\pi^\star,h}[\sqrt{ g_\theta(s,a)^\top \Sigma^{-1}_h g_\theta(s,a) }]\) where \(g_\theta(s,a):=\nabla f(\theta,\phi(s,a))\) is the gradient w.r.t. the parameter \(\theta^\star\) at feature \(\phi\) and \(\Sigma_h = \sum_i g(s_{i,h},a_{i,h}) g(s_{i,h},a_{i,h})^\top\) is the Fisher information matrix of the observed data at \(\widehat{\theta}\). This is achieved by analyzing the pessimistic fitted Q-learning (PFQL) algorithm (Theorem 3). In addition, we further analyze its variance-reweighting variant, which recovers the variance-dependent structure and can yield faster sample convergence rate. Last but not least, existing offline RL studies with tabular models, linear models and GLM models can be directly indicated by the appropriate choice of our model \(\mathcal{F}\).

2 Preliminaries↩︎

Episodic Markov decision process. Let \(M=(\mathcal{S}, \mathcal{A}, P, r, H, d_1)\) to denote a finite-horizon Markov Decision Process (MDP), where \(\mathcal{S}\) is the arbitrary state space and \(\mathcal{A}\) is the arbitrary action space which can be infinite or continuous. The transition kernel \(P_h:\mathcal{S}\times\mathcal{A} \mapsto \Delta^{\mathcal{S}}\) (\(\Delta^\mathcal{S}\) represents a distribution over states) maps each state action\((s_h,a_h)\) to a probability distribution \(P_h(\cdot|s_h,a_h)\) and \(P_h\) can be different for different \(h\) (time-inhomogeneous). \(H\) is the planning horizon and \(d_1\) is the initial state distribution. Besides, \(r : \mathcal{S} \times{A} \mapsto \mathbb{R}\) is the mean reward function satisfying \(0\leq r\leq1\). A policy \(\pi=(\pi_1,\ldots,\pi_H)\) assigns each state \(s_h \in \mathcal{S}\) a probability distribution over actions by mapping \(s_h\mapsto \pi_h(\cdot|s_h)\) \(\forall h\in[H]\) and induces a random trajectory \(s_1, a_1, r_1, \ldots, s_H,a_H,r_H,s_{H+1}\) with \(s_1 \sim d_1, a_h \sim \pi(\cdot|s_h), s_{h+1} \sim P_h (\cdot|s_h, a_h), \forall h \in [H]\).

Given a policy \(\pi\), the \(V\)-value functions and state-action value function (Q-functions) \(Q^\pi_h(\cdot,\cdot)\in \mathbb{R}^{S\times A}\) are defined as: \(V^\pi_h(s)=\mathbb{E}_\pi[\sum_{t=h}^H r_{t}|s_h=s] ,\;\;Q^\pi_h(s,a)=\mathbb{E}_\pi[\sum_{t=h}^H r_{t}|s_h,a_h=s,a],\;\forall s,a,h\in\mathcal{S},\mathcal{A},[H].\) The Bellman (optimality) equations follow \(\forall h\in[H],s,a\in\mathcal{S}\times\mathcal{A}\):\[\begin{align} &Q^\pi_h(s,a)=r_h(s,a)+\int_\mathcal{S}V^\pi_{h+1}(\cdot)dP_h(\cdot|s,a),\;\;V^\pi_h(s)=\mathbb{E}_{a\sim\pi_h(s)}[Q^\pi_h(s,a)], \\ &Q^\star_h(s,a)=r_h(s,a)+\int_\mathcal{S}V^\star_{h+1}(\cdot)dP_h(\cdot|s,a),\; \;V^\star_h(s)=\max_a Q^\star_h(s,a). \end{align}\]We define Bellman operator \(\mathcal{P}_h\) for any function \(V\in\mathbb{R}^\mathcal{S}\) as \(\mathcal{P}_h(V)=r_h+\int_\mathcal{S}V dP_h\), then \(\mathcal{P}_h(V^\pi_{h+1})= Q^\pi_h\) and \(\mathcal{P}_h(V^\star_{h+1})= Q^\star_h\). The performance measure is \(v^\pi:=\mathbb{E}_{d_1}\left[V^\pi_1\right]=\mathbb{E}_{\pi,d_1}\left[\sum_{t=1}^H r_t\right]\). Lastly, the induced state-action marginal occupancy measure for any \(h\in[H]\) is defined to be: for any \(E\subseteq \mathcal{S}\times\mathcal{A}\), \(d^\pi_h(E):= \mathbb{E}[(s_h,a_h)\in E| s_1\sim d_1,a_i\sim \pi(\cdot|s_i),s_{i}\sim P_{i-1}(\cdot|s_{i-1},a_{i-1}),1\leq i\leq h]\) and \(\mathbb{E}_{\pi,h}[f(s,a)]:=\int_{\mathcal{S}\times\mathcal{A}}f(s,a)d^\pi_h(s,a)dsda\).

Offline Reinforcement Learning. The goal of Offline RL is to learn the policy \(\pi^\star:=\mathop{\mathrm{argmax}}_{\pi}v^\pi\) using only the historical data \(\mathcal{D}=\left\{\left(s_{h}^{\tau}, a_{h}^{\tau}, r_{h}^{\tau}, s_{h+1}^{\tau}\right)\right\}_{\tau\in[K]}^{h\in[H]}\). The data generating behavior policy is denoted as \(\mu\). In the offline regime, we have neither the knowledge about \(\mu\) nor the access to further exploration for a different policy. The agent is asked to find a policy \(\widehat{\pi}\) such that \(v^\star-v^{\widehat{\pi}}\leq\epsilon\) for the given batch data \(\mathcal{D}\) and a specified accuracy \(\epsilon>0\).

2.1 Assumptions↩︎

Function approximation in offline RL requires sufficient expressiveness of \(\mathcal{F}\). In fact, even under the realizability and concentrability conditions, sample efficient offline RL might not be achievable [@foster2021offline]. Therefore, under the differentiable function setting (Definition 1), we make the following assumptions.

Assumption 1 (Realizability+Bellman Completeness). The differentiable function class \(\mathcal{F}\) in Definition 1 satisfies:

Realizability: for optimal \(Q^\star_h\), there exists \(\theta^\star_h\in\Theta\) such that \(Q^\star_h(\cdot,\cdot)=f(\theta^\star_h,\phi(\cdot))\) \(\forall h\);
Bellman Completeness: Let \(\mathcal{G}:= \{V(\cdot)\in\mathbb{R}^\mathcal{S}: such\;that\;\left\lVert V\right\rVert_\infty \leq H\}\). Then in this case \(\sup_{V\in\mathcal{G}}\inf_{f\in\mathcal{F}}\left\lVert f-\mathcal{P}_h(V)\right\rVert_\infty\leq \epsilon_\mathcal{F}\) for some \(\epsilon_\mathcal{F}\geq0\).

Realizability and Bellman Completeness are widely adopted in the offline RL analysis with general function approximations [@chen2019information; @xie2021bellman] and Assumption 1 states its differentiable function approximation version. There are other forms of completeness, e.g. optimistic closure defined in [@wang2019optimism].

Data coverage assumption. Furthermore, in the offline regime, it is known that function approximation cannot be sample efficient for learning a \(\epsilon\)-optimal policy without data-coverage assumptions when \(\epsilon\) is small (i.e. high accuracy) [@wang2021statistical]. In particular, we consider two types of coverage assumptions and provide guarantees for them separately.

Assumption 2 (Concentrability Coverage). For any fixed policy \(\pi\), define the marginal state-action occupancy ratio as \(d^\pi_h(s,a)/d^\mu_h(s,a)\) \(\forall s,a\). Then the concentrability coefficient is defined as \(C_{\text{eff}}:=\sup_\pi \sup_{h\in[H]}\left\lVert d^\pi_h/d^\mu_h\right\rVert_{2,d^\mu_h}^2\), where \(\left\lVert g(\cdot,\cdot)\right\rVert_{2,d^\mu}:=\sqrt{\mathbb{E}_{d^\mu}[g(\cdot,\cdot)^2]}\) and \(C_{\text{eff}}<\infty\).

This is the standard coverage assumption that has has been widely assumed in [@ernst2005tree; @szepesvari2005finite; @chen2019information; @xie2020batch]. In the above, it requires the occupancy ratio to be finitely bounded for all the policies. In the recent work [@xie2021bellman], they prove offline learning with GFA is efficient with only single policy concentrability, we believe similar results can be derived for DFA by modifying their main algorithm (3.2). However, chances are it will end up with a computational intractable algorithm. We leave this as the future work.

Assumption 2 is fully characterized by the MDPs. In addition, we can make an alternative assumption 3 that depends on both the MDPs and the function approximation class \(\mathcal{F}\).³ It assumes a curvature condition for \(\mathcal{F}\).

Assumption 3 (Uniform Coverage). We have \(\forall h\in[H]\), there exists \(\kappa>0\),

\(\mathbb{E}_{\mu,h}\left[\left(f(\theta_1,\phi(\cdot,\cdot))-f(\theta_2,\phi(\cdot,\cdot))\right)^2\right] \geq \kappa\left\lVert\theta_1-\theta_2\right\rVert^2_2, \;\;\forall \theta_1,\theta_2\in\Theta;\) \((\star)\)
\(\mathbb{E}_{\mu,h}\left[\nabla f(\theta,\phi(s,a))\cdot\nabla f(\theta,\phi(s,a))^\top\right]\succ \kappa I, \forall \theta\in\Theta.\) \((\star\star)\)

In the linear function approximation regime, Assumption 3 reduces to 1 since \((\star)\) and \((\star\star)\) are identical assumptions. Concretely, if \(f(\theta,\phi)=\langle \theta,\phi\rangle\), then \((\star)\) \(\mathbb{E}_{\mu,h}[\left(f(\theta_1,\phi(\cdot,\cdot))-f(\theta_2,\phi(\cdot,\cdot))\right)^2]=(\theta_1-\theta_2)^\top\mathbb{E}_{\mu,h}[\phi(\cdot,\cdot)\phi(\cdot,\cdot)^\top](\theta_1-\theta_2)\geq \kappa\left\lVert\theta_1-\theta_2\right\rVert^2_2\) \(\forall \theta_1,\theta_2\in\Theta \Leftrightarrow\) 1 \(\Leftrightarrow (\star\star) \mathbb{E}_{\mu,h}\left[\nabla f(\theta,\phi(s,a))\cdot\nabla f(\theta,\phi(s,a))^\top\right]\) \(\succ \kappa I\). Therefore, 3 can be considered as a natural extension of 1 for differentiable class. We do point that 3 can be violated for function class \(\mathcal{F}\) that is “not identifiable” by the data distribution \(\mu\) (i.e., there exists \(f(\theta_1),f(\theta_2)\in\mathcal{F},\theta_1\neq \theta_2\) s.t. \(\mathbb{E}_{\mu,h}[\left(f(\theta_1,\phi(\cdot,\cdot))-f(\theta_2,\phi(\cdot,\cdot))\right)^2]=0\)). Nevertheless, there are representative non-linear differentiable classes (e.g. generalized linear model (GLM)) satisfying 3.

Example 1 (Linear function coverage assumption [@wang2021statistical; @min2021variance; @yin2022linear; @xiong2022nearly]). \(\Sigma^{\mathrm{feature}}_h:=\mathbb{E}_{\mu,h}\left[\phi(s,a)\phi(s,a)^\top\right]\succ\kappa I\) \(\forall h\in[H]\) with some \(\kappa>0\).

Example 2 (offline generalized linear model [@li2017provably; @wang2019optimism]). For a known feature map \(\phi:\mathcal{S}\times\mathcal{A}\rightarrow \mathcal{B}_d\) and link function \(f:[-1,1]\mapsto [-1,1]\) the class of GLM is \(\mathcal{F}_{\mathrm{GLM}}:=\{(s,a)\mapsto f(\langle \phi(s,a),\theta\rangle):\theta\in\Theta\}\) satisfying \(\mathbb{E}_{\mu,h}\left[\phi(s,a)\phi(s,a)^\top\right]\succ\kappa I\). Furthermore, \(f(\cdot)\) is either monotonically increasing or decreasing and \(0<\kappa\leq |f'(z)|\leq K<\infty,|f^{\prime\prime}(z)|\leq M<\infty\) for all \(|z|\leq 1\) and some \(\kappa,K,M\). Then \(\mathcal{F}_{\mathrm{GLM}}\) satisfies 3, see Appendix 7.

3 Differentiable Function Approximation is Provably Efficient↩︎

In this section, we present our solution for offline reinforcement learning with differentiable function approximation. As a warm-up, we first analyze the vanilla fitted Q-learning (VFQL, Algorithm 2), which only requires the concentrability Assumption 2. The algorithm is presented in Appendix 14.

Theorem 2. Choose \(0<\lambda\leq 1/2C_\Theta^2\) in Algorithm 2. Suppose Assumption 1,2. Then if \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2Hd}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\), with probability \(1-\delta\), the output \(\widehat{\pi}\) of VFQL guarantees \[v^\star - v^{\widehat{\pi}}\leq \sqrt{C_{\mathrm{eff}}}H\cdot\widetilde{O}\left(\sqrt{\frac{H^2d+\lambda C^2_\Theta}{K}}+\sqrt[\frac{1}{4}]{\frac{H^3d\epsilon_{\mathcal{F}}}{K}} \right)+O(\sqrt{C_\mathrm{eff} H^3 \epsilon_{\mathcal{F}}}+H\epsilon_{\mathcal{F}})\]

If the model approximation capacity is insufficient, 2 will induce extra error due to the large \(\epsilon_{\mathcal{F}}\). If \(\epsilon_{\mathcal{F}}\rightarrow 0\), the standard statistical rate \(\frac{1}{\sqrt{K}}\) can be recovered and similar results are derived with general function approximation (GFA) [@chen2019information; @xie2020batch]. However, using concentrability coefficient conceals the problem-dependent structure and omits the specific information of differentiable functions in the complexity measure. Owing to this, we switch to the stronger “uniform” coverage 3 and analyze the pessimistic fitted Q-learning (PFQL, Algorithm 1) to arrive at the conclusion that offline RL with differentiable function approximation is provably efficient.

Motivation of PFQL. The PFQL algorithm mingles the two celebrated algorithmic choices: Fitted Q-Iteration (FQI) and Pessimism. However, before going into the technical details, we provide some interesting insights that motivate our analysis.

First of all, the square error loss used in FQI [@gordon1999approximate; @ernst2005tree] naturally couples with the differentiable function class as the resulting optimization objective is more computationally tractable (since stochastic gradient descent (SGD) can be readily applied) comparing to other information-theoretical algorithms derived with general function approximation (e.g. the maxmin objective in [@xie2021bellman], eqn (3.2)).⁴ In particular, FQI with differentiable function approximation resembles the theoretical prototype of neural FQI algorithm [@riedmiller2005neural] and DQN algorithm [@mnih2015human; @fan2020theoretical] when instantiating the model \(f\) to be deep neural networks. Furthermore, plenty of practical algorithms leverage fitted-Q subroutines for updating the critic step (e.g. [@schulman2017equivalence; @haarnoja2018soft]) with different differentiable function choices.

In addition, we also incorporate pessimism for the design. Indeed, one of the fundamental challenges in offline RL comes from the distributional shift. When such a mismatch occurs, the estimated/optimized \(Q\)-function (using batch data \(\mathcal{D}\)) may witness severe overestimation error due to the extrapolation of model \(f\) [@levine2020offline]. Pessimism is the scheme to mitigate the error / overestimation bias via penalizing the Q-functions at state-action locations that have high uncertainties (as opposed to the optimism used in the online case), and has been widely adopted (e.g. [@buckman2020importance; @kidambi2020morel; @jin2021pessimism]).

Algorithm 1 description. Inside the backward iteration of PFQL, Fitted Q-update is performed to optimize the parameter (Line 4). \(\widehat{\theta}_h\) is the root of the first-order stationarity equation \(\sum_{k=1}^K\left( f(\theta,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\theta,\phi_{h,k})+\lambda \theta=0\) and \(\Sigma_h\) is the Gram matrix with respect to \(\nabla_\theta f|_{\theta=\widehat{\theta}_h}\). Note for any \(s,a\in\mathcal{S}\times\mathcal{A}\), \(m(s,a):=(\nabla_{\theta} f(\widehat{\theta}_h,\phi(s,a))^{\top} \Sigma_{h}^{-1} \nabla_{\theta} f(\widehat{\theta}_h,\phi(s,a)))^{-1}\) measures the effective sample size that explored \(s,a\) along the gradient direction \(\nabla_\theta f|_{\theta=\widehat{\theta}_h}\), and \(\beta/\sqrt{m(s,a)}\) is the estimated uncertainty at \((s,a)\). However, the quantity \(m(s,a)\) depends on \(\widehat{\theta}_h\), and \(\widehat{\theta}_h\) needs to be close to the true \({\theta}_h^\star\) (i.e. \(\widehat{Q}_h\approx f(\widehat{\theta}_h,\phi)\) needs to be close to \(Q^\star_h\)) for the uncertainty estimation \(\Gamma_h\) to be valid, since putting a random \(\theta\) into \(m(s,a)\) can cause an arbitrary \(\Gamma_h\) that is useless (or might even deteriorate the algorithm). Such an “implicit” constraint over \(\widehat{\theta}_h\) imposes the extra difficulty for the theoretical analysis due to that general differentiable functions encode nonlinear structures. As a direct comparison, in the simpler linear MDP case, the uncertainty measure \(\Gamma_h:=\sqrt{\phi(\cdot,\cdot)^\top(\Sigma^{\mathrm{linear}}_h)^{-1}\phi(\cdot,\cdot)}\) is always valid since it does not depend on the least-square regression weight \(\widehat{w}_h\) [@jin2021pessimism].⁵ Besides, the choice of \(\beta\) is set to be \(\widetilde{O}(dH)\) in Theorem 3 and the extra higher order term \(\widetilde{O}(\frac{1}{K})\) in \(\Gamma_h\) is for theoretical reason only.

Figure 1: Pessimistic Fitted Q-Learning (PFQL)

Model-Based vs. Model-Free. PFQL can be viewed as the strict generalization over the previous value iteration based algorithms, e.g. PEVI algorithm ([@jin2021pessimism], linear MDPs) and the VPVI algorithm ([@yin2021towards], tabular MDPs). On one hand, approximate value iteration (AVI) algorithms [@munos2005error] are usually model-based algorithms (for instance the tabular algorithm VPVI uses empirical model \(\widehat{P}\) for planning). On the other hand, FQI has the form of batch Q-learning update (i.e. Q-learning is a special case with batch size equals to one), therefore is more of model-free flavor. Since FQI is a concrete instantiation of the abstract AVI procedure [@munos2007performance], PFQL draws a unified view of model-based and model-free learning.

Now we are ready to state our main result for PFQL and the full proof can be found in Appendix 9,10,11.

Theorem 3. Let \(\beta=8dH\iota\) and choose \(0<\lambda\leq 1/2C_\Theta^2\) in Algorithm 1. Suppose Assumption 1,3 with \(\epsilon_{\mathcal{F}}=0\).⁶ Then if \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2Hd}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\), with probability \(1-\delta\), for all policy \(\pi\) simultaneously, the output of PFQL guarantees \[v^\pi-v^{\widehat{\pi}}\leq \sum_{h=1}^H 8 dH\cdot \mathbb{E}_\pi\left[\sqrt{\nabla^\top_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))\Sigma^{-1}_h\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K}),\] where \(\iota\) is a Polylog term and the expectation of \(\pi\) is taken over \(s_h,a_h\). In particular, if further \(K\geq \max\{\widetilde{O}(\frac{(\kappa_1^2+\lambda)^2\kappa_2^2\kappa_1^2H^4d^2}{\kappa^6}),\frac{128\kappa_1^4\log(2d/\delta)}{\kappa^2}\}\) we have \[0\leq v^{\pi^\star}-v^{\widehat{\pi}}\leq \sum_{h=1}^H 16 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Sigma^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C'_{\mathrm{hot}}}{K}).\] Here \(\Sigma^{\star}_h=\sum_{k=1}^K \nabla_\theta f({\theta}^\star_h,\phi(s^k_h,a^k_h))\nabla^\top_\theta f({\theta}^\star_h,\phi(s^k_h,a^k_h))+\lambda I_d\) and the definition of higher order parameter \(C_{\mathrm{hot}}\), \(C'_{\mathrm{hot}}\) can be found in List 6.

Corollary 1 (Offline Generalized Linear Models (GLM)). Consider the GLM function class defined in 2. Suppose \(\beta,\lambda,K\) are defined the same as Theorem 3. \(\epsilon_{\mathcal{F}}=0\). Then with probability \(1-\delta\), for all policy \(\pi\) simultaneously, PFQL guarantees \[v^\pi-v^{\widehat{\pi}}\leq \sum_{h=1}^H 8 dH\cdot \mathbb{E}_\pi\left[\sqrt{f'(\langle\widehat{\theta}_h,\phi(s_h,a_h)\rangle)^2\cdot\phi^\top(s_h,a_h)\Sigma^{-1}_h\phi(s_h,a_h) }\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K}).\]

PFQL is provably efficient. Theorem 3 verifies PFQL is statistically efficient. In particular, by Lemma 19 we have \(\left\lVert\nabla_\theta f({\theta}^\star_h,\phi)\right\rVert_{\Sigma_h^{-1}}\lesssim \frac{2\kappa_1}{\sqrt{\kappa K}}\), resulting the main term to be bounded by \(\frac{32dH^2\kappa_1}{\sqrt{\kappa K}}\) that recovers the standard statistical learning convergence rate \(\frac{1}{\sqrt{K}}\).

Comparing to [@jin2021pessimism]. Theorem 3 strictly subsumes the linear MDP learning bound in [@jin2021pessimism]. In fact, in the linear case \(\nabla_\theta f(\theta,\phi)=\nabla_\theta\langle \theta,\phi\rangle=\phi\) and 3 reduces to \(O(dH\sum_{h=1}^H \mathbb{E}_{\pi^\star}[\sqrt{\phi(s_h,a_h)^\top(\Sigma^{\mathrm{linear}}_h)^{-1}\phi(s_h,a_h)}])\).

Instance-dependent learning. Previous studies for offline RL with general function approximation (GFA) [@chen2019information; @xie2020q] are more of worst-case flavors as they usually rely on the concentrability coefficient \(C\). The resulting learning bounds are expressed in the form⁷ \(O(V_{\max}^2\sqrt{\frac{C}{n}})\) that is unable to depict the behavior of individual instances. In contrast, the guarantee with differentiable function approximation is more adaptive due to the instance-dependent structure \(\sum_{h=1}^H \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi)\Sigma^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi)}\right]\). This Fisher-Information style quantity characterizes the learning hardness of separate problems explicitly as for different MDP instances \(M_1\), \(M_2\), the coupled \(\theta^\star_{h,M_1},\theta^\star_{h,M_2}\) will generate different performances via the measure \(\sum_{h=1}^H \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_{h,M_i},\phi)\Sigma^{\star-1}_h\nabla_\theta f({\theta}^\star_{h,M_i},\phi)}\right]\) (\(i=1,2\)). Standard worst-case bounds (e.g. from GFA approximation) cannot explicitly differentiate between problem instances.

Feature representation vs. Parameters. One interesting observation from Theorem 3 is that the learning complexity does not depend on the feature representation dimension \(m\) but only on parameter dimension \(d\) as long as function class \(\mathcal{F}\) satisfies differentiability definition 1 (not even in the higher order term). This seems to suggest, when changing the model \(f\) with more complex representations, the learning hardness will not grow as long as the number of parameters need to be learned does not increase. Note in the linear MDP analysis this phenomenon is not captured since the two dimensions are coupled (\(d=m\)). Therefore, this heuristic might help people rethink about what is the more essential element (feature representation vs. parameter space) in the representation learning RL regime (e.g. low rank MDPs [@uehara2021representation]). We leave the concrete understanding the connection between features and parameters as the future work.

Technical challenges with differentiable function approximation (DFA). Informally, one key step for the analysis is to bound \(|f(\widehat{\theta}_h,\phi)-f(\theta_h^\star,\phi)|\). This can be estimated by the first order approximation \(\nabla f(\widehat{\theta}_h,\phi)^\top\cdot(\widehat{\theta}_h-\theta^\star_h)\). However, different from the least-square value iteration (LSVI) objective [@jin2020provably; @jin2021pessimism], the fitted Q-update (Line 4, Algorithm 1) no longer admits a closed-form solution for \(\widehat{\theta}_h\). Instead, we can only leverage \(\widehat{\theta}_h\) is a stationary point of \(Z_h(\theta):=\sum_{k=1}^K \left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}\left(s^k_{h+1}\right)\right]\nabla f(\theta,\phi_{h,k})+\lambda\cdot \theta\) (since \(Z_h(\widehat{\theta}_h)=0\)). To measure the difference \(\widehat{\theta}_h-\theta^\star_h\), for any \(\theta\in\Theta\), we do the Vector Taylor expansion \(Z_h(\theta)-Z_h(\widehat{\theta}_h)=\Sigma^s_h({\theta}-\widehat{\theta}_{h})+R_K(\theta)\) (where \(R_K(\theta)\) is the higher-order residuals) at the point \(\widehat{\theta}_h\) with \[\label{eqn:covariance95main} \begin{align} &\Sigma^s_h:=\left.\frac{\partial}{\partial \theta}Z_h(\theta)\right|_{\theta=\widehat{\theta}_h}= \frac{\partial}{\partial \theta}\left(\sum_{k=1}^K \left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right]\nabla f(\theta,\phi_{h,k})+\lambda\cdot \theta\right)_{\theta=\widehat{\theta}_h}\\ &=\underbrace{\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi_{h,k})}_{:=\Delta_{\Sigma^s_h}} +\underbrace{\sum_{k=1}^K\nabla_{\theta} f(\widehat{\theta}_h,\phi_{h,k})\nabla_{\theta}^\top f(\widehat{\theta}_{h,k},\phi_{h,k})+\lambda I_d}_{:=\Sigma_h}. \end{align}\tag{1}\] The perturbation term \(\Delta_{\Sigma^s_h}\) encodes one key challenge for solving \(\widehat{\theta}_h-\theta^\star_h\) since it breaks the positive definiteness of \(\Sigma^s_h\), and, as a result, we cannot invert the \(\Sigma^s_h\) in the Taylor expansion of \(Z_h\). This is due to DFA (Definition 1) is a rich class that incorporates nonlinear curvatures. In the linear function approximation regime, this hurdle will not show up since \(\nabla^2_{\theta\theta}f\equiv 0\) and \(\Delta_{\Sigma^s_h}\) is always invertible as long as \(\lambda>0\). Moreover, for the off-policy evaluation (OPE) task, one can overcome this issue by expanding over the population counterpart of \(Z_h\) at underlying true parameter of the given behavior target policy [@zhang2022off].⁸ However, for the policy learning task, we cannot use either population quantity or the true parameter \(\theta^\star_h\) since we need a computable/data-based pessimism \(\Gamma_h\) to make the algorithm practical. Check the following section for more discussions of the analysis.

3.1 Sketch of the PFQL Analysis↩︎

Due to the space constraint, here we only overview the key components of the analysis. To begin with, by following the result of general MDP in [@jin2021pessimism], the suboptimality gap can be bounded by (Appendix 9) \(\sum_{h=1}^H 2 \mathbb{E}_\pi\left[\Gamma_h(s_h,a_h)\right]\) if \(|(\mathcal{P}_h\widehat{V}_{h+1}-f(\widehat{\theta}_h,\phi))(s,a)|\leq \Gamma_h(s,a)\). To deal with \(\mathcal{P}_h\widehat{V}_{h+1}\), by Assumption 1 we can leverage the parameter Bellman operator \(\mathbb{T}\) (Definition 2) so that \(\mathcal{P}_h\widehat{V}_{h+1}=f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi)\). Next, we apply the second-order approximation to obtain \(\mathcal{P}_h\widehat{V}_{h+1}-f(\widehat{\theta}_h,\phi)\approx \nabla f(\widehat{\theta}_h,\phi)^\top (\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h)+\frac{1}{2}(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h)^\top\nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi)(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h)\). Later, we use (1 ) to represent \[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-Z_h(\widehat{\theta}_h)=\Sigma^s_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})+R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})=\Sigma_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})+\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\] by denoting \(\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})=\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\). Now that \(\Sigma_h^{-1}\) is invertible thus provides the estimation (note \(Z_h(\widehat{\theta}_h)=0\)) \[\begin{align} \theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h=\Sigma^{-1}_h\cdot Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\Sigma^{-1}_h\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}}). \end{align}\] However, to handle the higher order terms, we need the explicit finite sample bound for \(\|\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h\|_2\) (or \(\|\theta_h^\star-\widehat{\theta}_h\|_2\)). In the OPE literature, [@zhang2022off] uses asymptotic theory (Prohorov’s Theorem) to show the existence of \(B(\delta)\) such that \(\|\widehat{\theta}_h-\theta^\star_h\|\leq \frac{B(\delta)}{\sqrt{K}}\). However, this is insufficient for finite sample/non-asymptotic guarantees since the abstraction of \(B(\delta)\) might prevent the result from being sample efficient. For example, if \(B(\delta)\) has the form \(e^H\log(\frac{1}{\delta})\), then \(\frac{e^H\log(\frac{1}{\delta})}{\sqrt{K}}\) is an inefficient bound since \(K\) needs to be \(e^H/\epsilon^2\) large to guarantee \(\epsilon\) accuracy.

To address this technicality, we use a novel reduction to general function approximation (GFA) learning proposed in [@chen2019information]. Concretely, we first bound the loss objective \(\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\) via a “orthogonal” decomposition and by solving a quadratic equation. The resulting bound can be directly used to further bound \(\|\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h\|_2\) for obtaining efficient guarantee \(\widetilde{O}(\frac{dH}{\sqrt{\kappa K}})\). During the course, the covering technique is applied to extend the finite function hypothesis in [@chen2019information] to all the differentiable functions in Definition 1. See Appendix 12 for the complete proofs. The full proof can be found in Appendix 9,10,11.

4 Improved Learning via Variance Awareness↩︎

In addition to knowing the provable efficiency for differentiable function approximation (DFA), it is of great interest to understand what is the statistical limit with DFA, or equivalently, what is the “optimal” sample/statistical complexity can be achieved in DFA (measured by minimaxity criteria)? Towards this goal, we further incorporate variance awareness to improve our learning guarantee. Variance awareness is first designed for linear Mixture MDPs [@talebi2018variance; @zhou2021nearly] to achieve the near-minimax sample complexity and it uses estimated conditional variances \(\mathrm{Var}_{P(\cdot|s,a)} (V^\star_{h+1})\) to reweight each training sample in the LSVI objective.⁹ Later, such a technique is leveraged by [@min2021variance; @yin2022linear] to obtained the instance-dependent results. Intuitively, conditional variances \(\sigma^2(s,a):=\mathrm{Var}_{P(\cdot|s,a)} (V^\star_{h+1})\) serves as the uncertainty measure of the sample \((s,a,r,s')\) that comes from the distribution \(P(\cdot|s,a)\). If \(\sigma^2(s,a)\) is large, then the distribution \(P(\cdot|s,a)\) has high variance and we should put less weights in a single sample \((s,a,r,s')\) rather than weighting all the samples equally. In the differentiable function approximation regime, the update is modified to

\[\widehat{\theta}_h\leftarrow \mathop{\mathrm{argmin}}_{\theta\in\Theta}\bigg\{\sum_{k=1}^{K}\frac{\left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right]^{2}}{{\sigma}^2_h(s_h^k,a_h^k)}+\lambda \cdot\left\lVert\theta\right\rVert_2^2\bigg\}\]with \({\sigma}^2_h(\cdot,\cdot)\) estimated by the offline data. Notably, empirical algorithms have also shown uncertainty reweighting can improve the performances for both online RL [@mai2022sample] and offline RL [@wu2021uncertainty]. These motivates our variance-aware fitted Q-learning (VAFQL) algorithm 3.

Theorem 4. Suppose Assumption 1,3 with \(\epsilon_{\mathcal{F}}=0\). Let \(\beta=8d\iota\) and choose \(0<\lambda\leq 1/2C_\Theta^2\) in Algorithm 3. Then if \(K\geq K_0\) and \(\sqrt{d}\geq \widetilde{O}(\zeta)\), with probability \(1-\delta\), for all policy \(\pi\) simultaneously, the output of VAFQL guarantees \[v^\pi-v^{\widehat{\pi}}\leq \sum_{h=1}^H 8 d\cdot \mathbb{E}_\pi\left[\sqrt{\nabla^\top_\theta f(\widehat{\theta}_h,\phi(s_h,a_h)){\Lambda}^{-1}_h\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{\bar{C}_{\mathrm{hot}}}{K}),\] where \(\iota\) is a Polylog term and the expectation of \(\pi\) is taken over \(s_h,a_h\). In particular, we have \[0\leq v^{\pi^\star}-v^{\widehat{\pi}}\leq 16 d\cdot\sum_{h=1}^H \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Lambda^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{\bar{C}'_{\mathrm{hot}}}{K}).\] Here \(\Lambda^{\star}_h=\sum_{k=1}^K \nabla_\theta f({\theta}^\star_h,\phi_{h,k})\nabla^\top_\theta f({\theta}^\star_h,\phi_{h,k})/\sigma^\star_h(s^k_h,a^k_h)^2+\lambda I_d\) and the \(\sigma^\star_h(\cdot,\cdot)^2:=\max\{1,\mathrm{Var}_{P_h}V^\star_{h+1}(\cdot,\cdot)\}\). The definition of \(K_0,\bar{C}_{\mathrm{hot}}\), \(\bar{C}'_{\mathrm{hot}},\zeta\) can be found in List 6.

In particular, to bound the error for \(\boldsymbol{u}_h,\boldsymbol{v}_h\) and \(\widehat{\sigma}^2_h\), we need to define an operator \(\mathbb{J}\) that is similar to the parameter Bellman operator 2. The Full proof of Theorem 4 can be found in Appendix 15. Comparing to Theorem 3, VAFQL enjoys a net improvement of the horizon dependence since \(\mathrm{Var}_{P}(V^\star_h)\leq H^2\). Moreover, VAFQL provides better instance-dependent characterizations as the main term is fully depicted by the system quantities except the feature dimension \(d\). For instance, when the system is fully deterministic (transition \(P_h\)’s are deterministic), \(\sigma^\star_h\approx \mathrm{Var}_{P_h}V^\star_{h+1}(\cdot,\cdot)\equiv 0\) (if ignore the truncation) and \(\Lambda^{\star -1}\rightarrow 0\). This yields a faster convergence with rate \(O(\frac{1}{K})\). Lastly, when reduced to linear MDPs, 4 recovers the results of [@yin2022linear] except an extra factor of \(\sqrt{d}\).

On the statistical limits. To complement the study, we incorporate a minimax lower bound via a reduction to [@zanette2021provable; @yin2022linear]. The following theorem reveals we cannot improve over Theorem 4 by more than a factor of \(\sqrt{d}\) in the most general cases. The full discussion is deterred to Appendix 16.

Theorem 5 (Minimax lower bound). Specifying the model to have linear representation \(f=\langle \theta,\phi\rangle\). There exist a pair of universal constants \(c, c' > 0\) such that given dimension \(d\), horizon \(H\) and sample size \(K > c' d^3\), one can always find a family of MDP instances such that for any algorithm \(\widehat{\pi}\) \[\begin{align} \inf_{\widehat{\pi}} \sup_{M \in \mathcal{M}} \mathbb{E}_M \big[v^{\star} - v^{\widehat{\pi}} \big] \geq c \, \sqrt{d} \cdot \sum_{h=1}^H \mathbb{E}_{\pi^{\star}} \bigg[ \sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(\cdot,\cdot))(\Lambda_h^{\star, p})^{-1} \nabla_\theta f({\theta}^\star_h,\phi(\cdot,\cdot))} \bigg], \end{align}\] where \(\Lambda_h^{\star,p} = \mathbb{E}\Big[ \sum_{k=1}^K \frac{\nabla_\theta f({\theta}^\star_h,\phi(s_h^k,a_h^k)) \cdot \nabla_\theta f({\theta}^\star_h,\phi(s_h^k,a_h^k))^\top}{\mathrm{Var}_h(V_{h+1}^{\star})(s_h^k, a_h^k)} \Big]\).

5 Conclusion, Limitation and Future Directions↩︎

In this work, we study offline reinforcement learning with differentiable function approximation and show the sample efficiency for differentiable function learning. We further improve the sample complexity with respect to the horizon dependence via a variance aware variant. However, the dependence of the parameter space still scales with \(d\) (whereas for linear function approximation this dependence is \(\sqrt{d}\)), and this is due to applying covering argument for the rich class of differentiable functions. For large deep models, the dimension of the parameter can be huge, therefore it would be interesting to know if certain algorithms can further improve the parameter dependence, or whether this \(d\) is essential.

Also, how to relax uniform coverage assumption 3 is unknown under the current analysis. In addition, due to the technical reason, we require the third-order smoothness in Definition 1. If only the second-order or the first-order derivative information is provided, whether learning efficiency can be achieved remains an interesting question. In addition, understanding the connections between the differentiable function approximation and overparameterized neural networks approximation [@thanh2022; @xu2022provably] is important. We leave these open problems as future work.

Lastly, the differentiable function approximation setting provides a general framework that is not confined to offline RL. Understanding the sample complexity behaviors of online reinforcement learning [@jin2020provably; @wang2019optimism], reward-free learning [@jin2020reward; @wang2020reward] and representation learning [@uehara2021representation] might provide new and unified views over the existing studies.

Acknowledgments↩︎

Ming Yin would like to thank Chi Jin for the helpful suggestions regarding the assumption for differentiable function class and Andrea Zanette, Xuezhou Zhang for the friendly discussion. Mengdi Wang gratefully acknowledges funding from Office of Naval Research (ONR) N00014-21-1-2288, Air Force Office of Scientific Research (AFOSR) FA9550-19-1-0203, and NSF 19-589, CMMI-1653435. Ming Yin and Yu-Xiang Wang are gratefully supported by National Science Foundation (NSF) Awards #2007117 and #2003257.

Appendix

6 Notation List↩︎

\(\Sigma^{p}_h(\theta)\)	\(\mathbb{E}_{\mu,h}\left[\nabla f(\theta,\phi(s,a))\cdot\nabla f(\theta,\phi(s,a))^\top\right]\)
\(\kappa\)	\(\min_{h,\theta} \lambda_{\mathrm{min}}(\Sigma^p_h(\theta))\)
\(\sigma_{V}^2(s,a)\)	\(\max\{1,\mathrm{Var}_{P_h}(V)(s,a)\}\) for any \(V\)
\(\delta\)	Failure probability
\(K_0\)	\(\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2Hd}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\)
\(\zeta\)	\(2\max_{s'\sim P(\cdot\|s,a),h\in[H]}\frac{(\mathcal{P}_h{V}^\star_{h+1})(s,a)-r-{V}^\star_{h+1}(s')}{\sigma^{\star}_h(s,a)}\)
\(C_{\mathrm{hot}}=\bar{C}_{\mathrm{hot}}\)	\(\frac{\kappa_1H}{\sqrt{\kappa}}+\frac{\kappa_1^2H^3d^2}{\kappa }+\sqrt{\frac{d^3H^4\kappa_2^2\kappa_1^2}{\kappa^3}}+\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^3+\frac{d^2H^4\kappa_3+\lambda\kappa_1C_\Theta}{\kappa}+\frac{H^3\kappa_2d^2}{\kappa}\)
\(C'_{\mathrm{hot}}=\bar{C}'_{\mathrm{hot}}\)	\(C_{\mathrm{hot}}+\frac{\kappa_1\kappa_2 H^4d^2}{\kappa^{3/2}}\)

7 Further Illustration that Generalized Linear Model Example satisfies 3 ↩︎

Recall the definition in 2, then:

For \((\star\star)\), \[\begin{align} &\mathbb{E}_{\mu,h}\left[\nabla f(\theta,\phi(s,a))\cdot\nabla f(\theta,\phi(s,a))^\top\right]=\mathbb{E}_{\mu,h}\left[f'(\langle \theta,\phi(s,a) \rangle)^2\phi(\cdot,\cdot)\cdot\phi(\cdot,\cdot)^\top\right]\\ &\succ \kappa^2\mathbb{E}_{\mu,h}\left[\phi(\cdot,\cdot)\cdot\phi(\cdot,\cdot)^\top\right] \succ\kappa^3 I, \quad\forall \theta\in\Theta \end{align}\] For \((\star)\), by Taylor’s Theorem, \[\begin{align} &\mathbb{E}_{\mu,h}\left[\left(f(\theta_1,\phi(\cdot,\cdot))-f(\theta_2,\phi(\cdot,\cdot))\right)^2\right]=\mathbb{E}_{\mu,h}[f'(\theta_{s,a},\phi(\cdot,\cdot))^2(\theta_1-\theta_2)^\top\phi(\cdot,\cdot)\phi(\cdot,\cdot)^\top(\theta_1-\theta_2)]\\ &\geq \kappa^2 \mathbb{E}_{\mu,h}[(\theta_1-\theta_2)^\top\phi(\cdot,\cdot)\phi(\cdot,\cdot)^\top(\theta_1-\theta_2)]=\kappa^2 (\theta_1-\theta_2)^\top\mathbb{E}_{\mu,h}[\phi(\cdot,\cdot)\phi(\cdot,\cdot)^\top](\theta_1-\theta_2)\geq \kappa^3\left\lVert\theta_1-\theta_2\right\rVert^2_2 \end{align}\] and choose \(\kappa^3\) as \(\kappa\) in 3.

8 On the computational complexity↩︎

For storage of Pessimistic Fitted Q-learning, at each time step \(h\in[H]\) in Algorithm 1, we need to store \(\widehat{\theta}_h\), \(\Sigma_h\) and \(\nabla f(\widehat{\theta}_h,\phi_{h,k})\). Therefore, the total space complexity is \(O(dH+d^2H+dKH)\). For computation, assuming \(\widehat{\theta}_h\) is solved via SGD and let \(M\) denote the number of gradient steps, then the complexity is dominated by computing \(\widehat{\theta}_h,\Sigma_h\) and \(\Sigma^{-1}_h\), which results in \(O(MH+KdH+d^3H)\) complexity (where \(H\) comes from \(h=H,\ldots,1\)).

The space complexity and computational complexity for VAFQL has the same order as PFQL except that the constant factors are larger.

9 Some basic constructions↩︎

First of all, Recall in the first-order condition, we have \[\left.\nabla_{\theta}\left\{ \sum_{k=1}^{K}\left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}\left(s^k_{h+1}\right)\right]^{2}+\lambda \cdot\left\lVert\theta\right\rVert_2^2\right\}\right|_{\theta=\widehat{\theta}_h}=0,\;\;\forall h\in[H].\] Therefore, if we define the quantity \(Z_h(\cdot,\cdot)\in\mathbb{R}^d\) as \[Z_h(\theta|V)=\sum_{k=1}^K \left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-{V}\left(s^k_{h+1}\right)\right]\nabla f(\theta,\phi_{h,k})+\lambda\cdot \theta,\;\;\forall \theta\in\Theta, \left\lVert V\right\rVert_2\leq H,\] then we have (recall \(\widehat{\theta}_h\in\mathrm{Int}(\Theta)\)) \[Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})=0.\]

In addition, according to Bellman completeness Assumption 1, for any bounded \(V(\cdot)\in\mathbb{R}^\mathcal{S}\) with \(\left\lVert V\right\rVert_\infty \leq H\), \(\inf_{f\in\mathcal{F}}\left\lVert f-\mathcal{P}_h(V)\right\rVert_\infty\leq \epsilon_\mathcal{F}\), \(\forall h\) (recall \(\mathcal{P}_h(V)=r_h+\int_\mathcal{S}V dP_h\)). Therefore, we can define the parameter Bellman operator \(\mathbb{T}\) as follows.

Definition 2 (parameter Bellman operator). By the Bellman completeness Assumption 1, for any \(\left\lVert V\right\rVert_\infty\leq H\), we can define the parameter Bellman operator \(\mathbb{T}:V\rightarrow \theta_{\mathbb{T} V}\in\Theta\) such that \[\theta_{\mathbb{T} V}=\mathop{\mathrm{argmin}}_{\theta\in\Theta}\left\lVert f(\theta,\phi)-\mathcal{P}_h(V)\right\rVert_\infty\] Denote \(\delta_V:=f(\theta_{\mathbb{T} V},\phi)-\mathcal{P}_h(V)\), then we have \(\left\lVert f(\theta_{\mathbb{T} V},\phi)-\mathcal{P}_h(V)\right\rVert_\infty=\left\lVert\delta_V\right\rVert_\infty\leq \epsilon_\mathcal{F}\). In particular, by realizability Assumption 1 it holds \(\theta_{\mathbb{T} V^\star_{h+1}}=\theta^\star_h\) and this is due to \(f(\theta_{\mathbb{T} V^\star_{h+1}},\phi)=\mathcal{P}_h(V^\star_{h+1})=V^\star_h=f(\theta^\star_h,\phi)\).¹⁰

9.1 Suboptimality decomposition↩︎

Denote \(\iota_h(s,a) := \mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{Q}_h(s,a)\), by [@jin2021pessimism] we have the following decomposition.

Lemma 1 (Lemma 3.1 of [@jin2021pessimism]). Let \(\widehat{\pi}=\{\widehat{\pi}_h\}_{h=1}^H\) a policy and \(\widehat{Q}_h\) be any estimates with \(\widehat{V}_h=\langle\widehat{Q}_{h}(s, \cdot), \widehat{\pi}_{h}(\cdot \mid s)\rangle_{\mathcal{A}}\). Then for any policy \(\pi\), we have \[\begin{align} v^{\pi}-v^{\widehat{\pi}}=&-\sum_{h=1}^H E_{\widehat{\pi}}[\iota_h(s_h,a_h)]+\sum_{h=1}^H E_{\pi}[\iota_h(s_h,a_h)] +\sum_{h=1}^H E_{\pi}[\langle\widehat{Q}_{h}\left(s_{h}, \cdot\right), \pi_{h}\left(\cdot \mid s_{h}\right)-\widehat{\pi}_{h}\left(\cdot \mid s_{h}\right)\rangle_{\mathcal{A}}]. \end{align}\] In particular, if we choose \(\widehat{\pi}_h(\cdot|s):=\mathop{\mathrm{argmax}}_{\pi}\langle\widehat{Q}_{h}(s, \cdot), {\pi}(\cdot \mid s)\rangle_{\mathcal{A}}\), then \[\begin{align} v^{\pi}-v^{\widehat{\pi}}=&-\sum_{h=1}^H E_{\widehat{\pi}}[\iota_h(s_h,a_h)]+\sum_{h=1}^H E_{\pi}[\iota_h(s_h,a_h)]. \end{align}\]

Lemma 2. Let \(\widehat{\mathcal{P}}_h\) be the general estimated Bellman operator. Suppose with probability \(1-\delta\), it holds for all \(h,s,a\in[H]\times\mathcal{S}\times{A}\) that \(|(\mathcal{P}_h\widehat{V}_{h+1}-\widehat{\mathcal{P}}_h\widehat{V}_{h+1})(s,a)|\leq \Gamma_h(s,a)\), then it implies \(\forall s,a,h\in\mathcal{S}\times\mathcal{A}\times[H]\), \(0\leq \zeta_h(s,a)\leq 2\Gamma_h(s,a)\). Furthermore, it holds for any policy \(\pi\) simultaneously, with probability \(1-\delta\), \[V_1^{\pi}(s)-V_1^{\widehat{\pi}}(s)\leq \sum_{h=1}^H 2\cdot \mathbb{E}_\pi\left[\Gamma_h(s_h,a_h)\mid s_1=s\right].\]

Proof of Lemma 2. This is a generic result that holds true for the general MDPs and was first raised by Theorem 4.2 of [@jin2021pessimism]. Later, it is summarized in Lemma C.1 of [@yin2022linear]. ◻

With Lemma 2, we need to bound the term \(|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)|\).

10 Analyzing \(|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)|\) for PFQL.↩︎

Throughout this section, we suppose \(\epsilon_{\mathcal{F}}=0\), i.e. \(f(\theta_{\mathbb{T} V},\phi)=\mathcal{P}_h(V)\). According to the regression oracle (Line 4 of Algorithm 1), the estimated Bellman operator \(\widehat{\mathcal{P}}_h\) maps \(\widehat{V}_{h+1}\) to \(\widehat{\theta}_h\), i.e. \(\widehat{\mathcal{P}}_h\widehat{V}_{h+1}=f(\widehat{\theta}_h,\phi)\). Therefore (recall Definition 2) \[\label{eqn:decomp95iota} \begin{align} &\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)=\mathcal{P}_h \widehat{V}_{h+1}(s,a)-f(\widehat{\theta}_{h},\phi(s,a))\\ =&f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\widehat{\theta}_{h},\phi(s,a))\\ =&\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)+\mathrm{Hot}_{h,1}, \end{align}\tag{2}\] where we apply the first-order Taylor expansion for the differentiable function \(f\) at point \(\widehat{\theta}_h\) and \(\mathrm{Hot}_{h,1}\) is a higher-order term. Indeed, the following Lemma 3 bounds the \(\mathrm{Hot}_{h,1}\) term with \(\widetilde{O}(\frac{1}{K})\).

Lemma 3. Recall the definition (from the above decomposition) \(\mathrm{Hot}_{h,1}:=f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\widehat{\theta}_{h},\phi(s,a))-\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\), then with probability \(1-\delta\), \[\left|\mathrm{Hot}_{h,1}\right|\leq \frac{18H^2\kappa_2(\log(H/\delta)+C_{d,\log K})+\kappa_2\lambda C_\Theta^2}{\kappa K},\;\;\forall h\in[H].\]

Proof of Lemma 3. By second-order Taylor’s Theorem, there exists a point \(\xi\) (lies in the line segment of \(\widehat{\theta}_{h}\) and \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\)) such that \[f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\widehat{\theta}_{h},\phi(s,a))=\nabla f(\widehat{\theta}_{h},\phi(s,a))^\top\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)+\frac{1}{2}\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)^\top \nabla^2_{\theta\theta}f(\xi,\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\] Therefore, by directly applying Theorem 6, with probability \(1-\delta\), for all \(h\in[H]\), \[\begin{align} \left|\mathrm{Hot}_{h,1}\right|=&\frac{1}{2}\left|\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)^\top \nabla^2_{\theta\theta}f(\xi,\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\right|\\ \leq &\frac{1}{2}\kappa_2\cdot\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right\rVert_2^2 \leq\frac{18H^2\kappa_2(\log(H/\delta)+C_{d,\log K})+\kappa_2\lambda C_\Theta^2}{\kappa K} \end{align}\] ◻

10.1 Analyzing \(\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\) via \(Z_h\).↩︎

From (2 ) and Lemma 3, the problem further reduces to bounding \(\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\). To begin with, we first provide a characterization of \(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\). Indeed, by first-order Vector Taylor expansion (Lemma 15), we have (note \(Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})=0\)) for any \(\theta\in\Theta\), \[\label{eqn:z95first95order} Z_h({\theta}|\widehat{V}_{h+1})-Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})=\Sigma^s_h({\theta}-\widehat{\theta}_{h})+R_K(\theta),\tag{3}\] where \(R_K(\theta)\) is the higher-order residuals and \(\Sigma^s_h:=\left.\frac{\partial}{\partial \theta}Z_h(\theta|\widehat{\theta}_{h+1})\right|_{\theta=\widehat{\theta}_h}\) with \[\label{eqn:covariance} \begin{align} \Sigma^s_h:=&\left.\frac{\partial}{\partial \theta}Z_h(\theta|\widehat{V}_{h+1})\right|_{\theta=\widehat{\theta}_h}= \frac{\partial}{\partial \theta}\left(\sum_{k=1}^K \left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right]\nabla f(\theta,\phi_{h,k})+\lambda\cdot \theta\right)_{\theta=\widehat{\theta}_h}\\ =&\underbrace{\sum_{k=1}^K\left\{\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi_{h,k})\right\}}_{:=\Delta_{\Sigma^s_h}}\\ +&\underbrace{\sum_{k=1}^K\nabla_{\theta} f(\widehat{\theta}_h,\phi_{h,k})\nabla_{\theta}^\top f(\widehat{\theta}_{h,k},\phi_{h,k})+\lambda I_d}_{:=\Sigma_h}, \end{align}\tag{4}\] here \(\nabla^2=\nabla\bigotimes\nabla\) denotes outer product of gradients.

Note \(\Delta_{\Sigma^s_h}\) is not desirable since it could prevent \(\Sigma^s_h\) from being positive-definite (and it could cause \(\Sigma^s_h\) to be singular). Therefore, we first deal with \(\Delta_{\Sigma^s_h}\) in below.

Lemma 4. With probability \(1-\delta\), for all \(h\in[H]\), \[\begin{align} &\frac{1}{K}\left\lVert\Delta_{\Sigma^s_h}\right\rVert_2=\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi_h)\right\rVert_2\\ \leq& 9\kappa_2 \max(\frac{\kappa_1}{\sqrt{\kappa}},1) \sqrt{\frac{dH^2(\log(2H/\delta)+d\log(1+2C_\Theta H\kappa_3K)+C_{d,\log K})}{K}}+\frac{1}{K}. \end{align}\]

Proof of Lemma 4. Step1: We prove for fixed \(\bar{\theta}\in\Theta\), with probability \(1-\delta\), for all \(h\in[H]\), \[\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\leq 9\kappa_2 \max(\frac{\kappa_1}{\sqrt{\kappa}},1) \sqrt{\frac{H^2(\log(2H/\delta)+C_{d,\log K})}{K}}.\] Indeed, we have \[\label{eqn:difference95one} \begin{align} &\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\\ \leq & \left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\\ +&\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2. \end{align}\tag{5}\] On one hand, by Theorem 6 with probability \(1-\delta/2\) for all \(h\in[H]\) \[\label{eqn:difference95two} \begin{align} &\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2 \leq \kappa_2 \cdot \max_{\theta,s,a}\left\lVert\nabla f(\theta,\phi(s,a))\right\rVert_2\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\\ &\leq\kappa_2 \kappa_1\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\leq \kappa_2\kappa_1\left( \sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\sqrt{\frac{b_{d,K,\epsilon_{\mathcal{F}}}}{\kappa}}+\sqrt{\frac{2H\epsilon_{\mathcal{F}}}{\kappa}}\right). \end{align}\tag{6}\] On other hand, recall the definition of \(\mathbb{T}\), we have \[\begin{align} &\mathbb{E}\left[( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k))\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_{h,k})\middle | s_h^k,a_h^k \right]\\ =&\mathbb{E}\left[ f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\middle | s_h^k,a_h^k \right]\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_{h,k})\\ =&\left((\mathcal{P}_{h}\widehat{V}_{h+1})(s_h^k,a_h^k)-\mathbb{E}\left[ r_{h,k}+\widehat{V}_{h+1}(s_{h+1}^k)\middle | s_h^k,a_h^k \right]\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_{h,k})\\ =&\left((\mathcal{P}_{h}\widehat{V}_{h+1})(s_h^k,a_h^k)-(\mathcal{P}_{h}\widehat{V}_{h+1}(s_{h+1}^k))(s_h^k,a_h^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_{h,k})=0. \end{align}\] Also, since \(\left\lVert\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k))\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\leq H\kappa_2\), denote \(\sigma^2:=K\cdot H^2\kappa_2^2\), then by Vector Hoeffding’s inequality (Lemma 16), \[\mathbb{P}\left(\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\geq t/K\middle| \{s_h^k,a_h^k\}_{k=1}^K\right)\leq d\cdot e^{-t^2/8d KH^2\kappa_2^2}:=\delta\] which is equivalent to \[\mathbb{P}\left(\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\leq \sqrt{\frac{8dH^2\kappa_2^2\log(d/\delta)}{K}}\middle| \{s_h^k,a_h^k\}_{k=1}^K\right)\geq 1-\delta\] Define \(A=\{\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\leq \sqrt{\frac{8dH^2\kappa_2^2\log(d/\delta)}{K}}\}\), then by law of total expectation \(\mathbb{P}(A)=\mathbb{E}[\mathbf{1}_A]=\mathbb{E}[\mathbb{E}[\mathbf{1}_A| \{s_h^k,a_h^k\}_{k=1}^K]] =\mathbb{E}[\mathbb{P}[A| \{s_h^k,a_h^k\}_{k=1}^K]]\geq \mathbb{E}[1-\delta]=1-\delta\), i.e. with probability at least \(1-\delta/2\) (and a union bound), \[\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\leq \sqrt{\frac{8dH^2\kappa_2^2\log(2Hd/\delta)}{K}},\;\forall h\in[H].\] Using above and 5 , 6 and a union bound, w.p. \(1-\delta\), for all \(h\in[H]\), \[\begin{align} \left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2&\leq 6\kappa_2\kappa_1 \sqrt{\frac{H^2(\log(2H/\delta)+C_{d,\log K})}{\kappa K}}+\sqrt{\frac{8dH^2\kappa_2^2\log(2Hd/\delta)}{K}}\\ &\leq 9\kappa_2 \max(\frac{\kappa_1}{\sqrt{\kappa}},1) \sqrt{\frac{dH^2(\log(2H/\delta)+C_{d,\log K})}{K}} \end{align}\] Step2: we finish the proof of the lemma.

Consider the function class \(\left\{f(\bar{\theta}):=\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\bar{\theta},\phi_h)\right\rVert_2\middle|\bar{\theta}\in\Theta\right\}\), then by triangular inequality \[\begin{align} |f(\bar{\theta}_1)-f(\bar{\theta}_2)|\leq& \left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \left[\nabla^2_{\theta\theta} f(\bar{\theta}_1,\phi_h)-\nabla^2_{\theta\theta} f(\bar{\theta}_2,\phi_h)\right]\right\rVert_2\\ \leq& H\cdot \sup_{s,a}\left\lVert\nabla^2_{\theta\theta} f(\bar{\theta}_1,\phi_h)-\nabla^2_{\theta\theta} f(\bar{\theta}_2,\phi_h)\right\rVert_2\leq H\kappa_3\left\lVert\bar{\theta}_1-\bar{\theta}_2\right\rVert_2. \end{align}\] By Lemma 22, the covering number \(\mathcal{C}\) of the \(\epsilon\)-net of the above function class satisfies \(\log \mathcal{C}\leq d\log(1+\frac{2C_\Theta H\kappa_3}{\epsilon}).\) By choosing \(\epsilon = 1/K\), by a union bound over \(\mathcal{C}\) cases we obtain for all \(h\in[H]\) \[\begin{align} &\left\lVert\frac{1}{K}\sum_{k=1}^K\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi_h)\right\rVert_2\\ \leq& 9\kappa_2 \max(\frac{\kappa_1}{\sqrt{\kappa}},1) \sqrt{\frac{dH^2(\log(2H/\delta)+d\log(1+{2C_\Theta H\kappa_3K})+C_{d,\log K})}{K}}+\frac{1}{K}. \end{align}\] ◻

Combing Lemma 4 and Theorem 6 (and a union bound), we directly have

Corollary 2. With probability \(1-\delta\), \[\left\lVert\frac{1}{K}\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2\leq \left\lVert\frac{1}{K}\Delta_{\Sigma^s_h}\right\rVert_2\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\leq \widetilde{O}(\frac{\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^2}{K})\] Here \(\widetilde{O}\) absorbs all the constants and Polylog terms.

Now we select \(\theta = \theta_{\mathbb{T}\widehat{V}_{h+1}}\) in 3 , and denote \(\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})=\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\), then 3 is equivalent to \[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})-Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})=\Sigma^s_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})+R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})=\Sigma_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})+\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\] Note \(\lambda>0\) implies \(\Sigma_h\) is invertible, then we have (recall \(Z_h(\widehat{\theta}_h|\widehat{\theta}_{h+1})=0\)) \[\begin{align} \theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h=&\Sigma^{-1}_h[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})-Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})]-\Sigma^{-1}_h\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\\ =&\Sigma^{-1}_h[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})]-\Sigma^{-1}_h\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\\ \end{align}\] Plug it back to 2 to get \[\label{eqn:main95decomposition} \begin{align} &\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\\ =&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma^{-1}_h[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})]-\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\\ =&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma^{-1}_h[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})+\lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}]\\ -&\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\\ =&\underbrace{\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})]}_{:=I}\\ -&\underbrace{\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \left[\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})+\lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}\right]}_{:=\mathrm{Hot}_2} \end{align}\tag{7}\] We will bound second term \(\mathrm{Hot}_2\) to have higher order \(O(\frac{1}{K})\) in Section 10.5 and focus on the first term. By direct decomposition, \[\begin{align} I:=&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})]\\ =&\underbrace{\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})]}_{:=I_1}\\ +&\underbrace{\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})]}_{:=I_2}\\ +&\underbrace{\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}\left[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \left(\nabla^\top_\theta f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-\nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right)\right]}_{:=I_3}\\ \end{align}\]

10.2 Bounding the term \(I_3\)↩︎

We first bound the term \(I_3\). We have the following Lemma.

Lemma 5. For any fixed \(V(\cdot)\in \mathbb{R}^\mathcal{S}\) with \(\left\lVert V\right\rVert_\infty\leq H\) and any fixed \(\theta\) such that \(\left\lVert\theta_{\mathbb{T}V}-\theta\right\rVert_2\leq \sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\). Let \[\widetilde{I}_3:=\nabla f(\widehat{\theta}_{h},\phi(s,a))^\top\Sigma_h^{-1}\left[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right],\] and if \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1 D^2\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\), then with probability \(1-\delta\), (where \(D=\max\{\kappa_1,\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa}}\}\))

\[|\widetilde{I}_3|\leq 4\kappa_1\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa^3}}\frac{1}{K}+O(\frac{1}{K^{3/2}}).\]

Proof of Lemma 5. Indeed, with probability \(1-\delta/2\), \[\begin{align} |\widetilde{I}_3|=&\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))^\top\Sigma_h^{-1}\left[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right]\right\rVert\\ \leq& \left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_{\Sigma_h^{-1}}\\ \leq& \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_{\Sigma_h^{-1}} \end{align}\] where, under the condition \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\), we applied Lemma 19 .

Next, on one hand, \(\left\lVert\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right\rVert_2\leq \kappa_2\cdot \left\lVert\theta_{\mathbb{T}V}-\theta\right\rVert_2\leq \kappa_2\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\). On the other hand, \[\begin{align} &\mathbb{E}\left[\left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla^\top_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla^\top_\theta f({\theta},\phi_{h,k})\right)\middle| s_h^k,a_h^k\right]\\ =&\mathbb{E}\left[\left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\middle| s_h^k,a_h^k\right]\cdot \left(\nabla^\top_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla^\top_\theta f({\theta},\phi_{h,k})\right)\\ =&\left((\mathcal{P}_{h}V)(s_h^k,a_h^k)-(\mathcal{P}_hV)(s_h^k,a_h^k)\right)\cdot \left(\nabla^\top_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla^\top_\theta f({\theta},\phi_{h,k})\right)=0 \end{align}\] Therefore by Vector Hoeffding’s inequality (Lemma 16) (also note the condition for boundedness \(\left\lVert \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_2\leq H\kappa_2\cdot \left\lVert\theta_{\mathbb{T}V}-\theta\right\rVert_2\leq H\kappa_2\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\)) with probability \(1-\delta/2\), \[\begin{align} &\left\lVert\frac{1}{K}\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_2\\ &\leq \sqrt{\frac{4d\left(H\kappa_2\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\right)^2\log(\frac{d}{\delta})}{K}}\\ &=\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa}}\cdot\frac{1}{K} \end{align}\] and this implies with probability \(1-\delta/2\), \[\begin{align} &\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_2\\ &\leq\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa}} \end{align}\] choose \(u=\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\) in Lemma 19, by a union bound we obtain with probability \(1-\delta\) \[\begin{align} |\widetilde{I}_3|=&\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))^\top\Sigma_h^{-1}\left[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right]\right\rVert\\ \leq& \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\theta_{\mathbb{T}{V}},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right)\right\rVert_{\Sigma_h^{-1}}\\ \leq&\left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\left(2\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa^2K}}+O(\frac{1}{K})\right)\\ =&4\kappa_1\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)\log(d/\delta)}{\kappa^3}}\frac{1}{K}+O(\frac{1}{K^{3/2}}). \end{align}\] ◻

Lemma 6. Under the same condition as Lemma 5. With probability \(1-\delta\), \[|I_3|\leq 4\kappa_1\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+D_{d,\log K}+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)(\log(d/\delta)+D_{d,\log K})}{\kappa^3}}\frac{1}{K}+O(\frac{1}{K^{3/2}}).\]Here \(D_{d,\log K}:=d\cdot\log(1+{6C_\Theta(2\kappa_1^2+H\kappa_2)K})+ d\log(1+{6C_\Theta H\kappa_2K})+ d\log\left(1+{288C_\Theta\kappa_1^2 (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2K^2}\right)+d^2\log\left(1+{288\sqrt{d}B\kappa_1^4K^2}\right)=\widetilde{O}(d^2)\) with \(\widetilde{O}\) absorbs Polylog terms.

Proof of Lemma 6. Define \[h(V,\widetilde{\theta},\theta)=\sum_{k=1}^K \left( f(\widetilde{\theta},\phi_{h,k})-r_{h,k}-{V}(s^k_{h+1})\right)\cdot \left(\nabla_\theta f(\widetilde{\theta},\phi_{h,k})-\nabla_\theta f({\theta},\phi_{h,k})\right),\] then \[\begin{align} &|h(V_1,\widetilde{\theta}_1,\theta_1)-h(V_2,\widetilde{\theta}_2,\theta_2)|\\ \leq& \left|\sum_{k=1}^K \left([f(\widetilde{\theta}_1,\phi_{h,k})-{V}_1(s^k_{h+1})]-[f(\widetilde{\theta}_2,\phi_{h,k})-{V}_2(s^k_{h+1})]\right)\cdot \left(\nabla_\theta f(\widetilde{\theta}_1,\phi_{h,k})-\nabla_\theta f({\theta}_1,\phi_{h,k})\right)\right|\\ +&\left|\sum_{k=1}^K \left(f(\widetilde{\theta}_2,\phi_{h,k})-r_{h,k}-{V}_2(s^k_{h+1})\right)\cdot \left([\nabla_\theta f(\widetilde{\theta}_1,\phi_{h,k})-\nabla_\theta f({\theta}_1,\phi_{h,k})]-[\nabla_\theta f(\widetilde{\theta}_2,\phi_{h,k})-\nabla_\theta f({\theta}_2,\phi_{h,k})]\right)\right|\\ \leq &K\sup_{s,a,s'}\left|[f(\widetilde{\theta}_1,\phi(s,a))-f(\widetilde{\theta}_2,\phi(s,a))]-[{V}_1(s')-{V}_2(s')]\right|_2\cdot 2\kappa_1\\ +&KH\cdot\sup_{s,a}\left\lVert[\nabla_\theta f(\widetilde{\theta}_1,\phi(s,a))-\nabla_\theta f({\theta}_1,\phi(s,a))]-[\nabla_\theta f(\widetilde{\theta}_2,\phi(s,a))-\nabla_\theta f({\theta}_2,\phi(s,a))]\right\rVert_2\\ \leq &K 2\kappa^2_1\left\lVert\widetilde{\theta}_1-\widetilde{\theta}_2\right\rVert_2+2K\kappa_1\left\lVert V_1-V_2\right\rVert_\infty +HK\kappa_2\left\lVert\widetilde{\theta}_1-\widetilde{\theta}_2\right\rVert_2+HK\kappa_2\left\lVert{\theta}_1-{\theta}_2\right\rVert_2\\ =&(2\kappa^2_1+H\kappa_2)K\left\lVert\widetilde{\theta}_1-\widetilde{\theta}_2\right\rVert_2+2\kappa_1K\left\lVert V_1-V_2\right\rVert_\infty+HK\kappa_2\left\lVert{\theta}_1-{\theta}_2\right\rVert_2. \end{align}\] Let \(\mathcal{C}_a\) be the \(\frac{\epsilon/3}{(2\kappa_1^2+H\kappa_2)K}\)-covering net of \(\{\theta:\left\lVert\theta\right\rVert_2\leq C_\Theta\}\), \(\mathcal{C}_V\) be the \(\frac{\epsilon}{6\kappa_1K}\)-covering net of \(\mathcal{V}\) defined in Lemma 23 and \(\mathcal{C}_b\) be the \(\frac{\epsilon}{3H\kappa_2K}\)-covering net of \(\{\theta:\left\lVert\theta\right\rVert_2\leq C_\Theta\}\), then by Lemma 22 and Lemma 23, \[\begin{align} \log|\mathcal{C}_a|\leq d\cdot\log(1+\frac{6C_\Theta(2\kappa_1^2+H\kappa_2)K}{\epsilon}),\;\log|\mathcal{C}_b|\leq d\log(1+\frac{6C_\Theta H\kappa_2K}{\epsilon})\\ \log \mathcal{C}_V\leq d\log\left(1+\frac{288C_\Theta\kappa_1^2 (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2K^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288\sqrt{d}B\kappa_1^4K^2}{\epsilon^2}\right). \end{align}\] Further notice with probability \(1-\delta/2\) (by Lemma 19), for all fixed sets of parameters \(\theta,V\) satisfies \(\left\lVert\theta_{\mathbb{T}{V}}-{\theta}\right\rVert_2\leq\sqrt{\frac{36H^2(\log(2H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\) simultaneously, \[\begin{align} |I_3-\widetilde{I}_3|\leq &\left\lVert\nabla f(\widehat{\theta}_h,\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot \left\lVert h(\widehat{V}_{h+1},\theta_{\mathbb{T}\widehat{V}_{h+1}},\widehat{\theta}_h)-h(V,\theta_{\mathbb{T}{V}},{\theta})\right\rVert_{\Sigma_h^{-1}}\\ \leq & \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right) \cdot \left\lVert h(\widehat{V}_{h+1},\theta_{\mathbb{T}\widehat{V}_{h+1}},\widehat{\theta}_h)-h(V,\theta_{\mathbb{T}{V}},{\theta})\right\rVert_{\Sigma_h^{-1}} \end{align}\] and \(\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_h\right\rVert_2\leq\sqrt{\frac{36H^2(\log(2H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}\) with probability \(1-\delta/2\) by Theorem 6. Now, choosing \(\epsilon = O(1/K^2)\) and by Lemma 5 and union bound over covering instances, we obtain with probability \(1-\delta\) \[|I_3|\leq 4\kappa_1\sqrt{\frac{(144dH^2\kappa_2^2\left(H^2\log(H/\delta)+D_{d,\log K}+C_{d,\log K}\right)+8dH^2\kappa_2^2\lambda C^2_\Theta)(\log(d/\delta)+D_{d,\log K})}{\kappa^3}}\frac{1}{K}+O(\frac{1}{K^{3/2}}).\] ◻

10.3 Bounding the second term \(I_2\)↩︎

In this section, we bound the term \[\begin{align} I_2:={\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})]}. \end{align}\] The following Lemma shows that \(I_2\) is a higher-order error term with rate \(\widetilde{O}(\frac{1}{K})\).

Lemma 7 (Bounding \(I_2\)). If \(K\) satisfies \(K\geq 512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K}{\lambda^2})\right),\) and \(K\geq 4\lambda/\kappa\), then with probability \(1-\delta\) \[|I_2|\leq \widetilde{O}(\frac{\kappa_1^2H^2d^2}{\kappa K})+\widetilde{O}(\frac{1}{K^{3/2}}).\] Here \(\widetilde{O}\) absorbs constants and Polylog terms.

Proof of Lemma 7. Step1. Define \(\eta_k(V):= f(\theta_{\mathbb{T}{V}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-{V}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\) and let \(\left\lVert V(\cdot)\right\rVert_\infty\leq H\) be any fixed function such that \(\sup_{s_h^k,a_h^k,s_{h+1}^k}|\eta_k(V)|\leq \widetilde{O}(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}})\), i.e. arbitrary fixed \(V\) function in the neighborhood (measured by \(\eta_k\)) of \(V^\star_{h+1}\). Then by definition of \(\mathbb{T}\) it holds \(\mathbb{E}[\eta_k(V,\theta)|s_h^k,a_h^k]=0\). Let the fixed \(\theta\in\Theta\) be arbitrary and define \(x_k(\theta)=\nabla_\theta f({\theta},\phi_{h,k})\). Next, define \({G}_h(\theta)=\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top+\lambda I_d\), since \(\left\lVert x_k\right\rVert_2\leq\kappa_1\) and \(|\eta_k|\leq \widetilde{O}(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}})\), by self-normalized Hoeffding’s inequality (Lemma 17), with probability \(1-\delta\) (recall \(t:=K\) in Lemma 17), \[\left\|\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}(V)\right\|_{G_h(\theta)^{-1}} \leq \widetilde{O}(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}})\sqrt{{d}\log \left(\frac{\lambda+K\kappa_1}{\lambda\delta}\right)}.\]

Step2. Define \(h(V,\theta):=\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}(V)\) and \(H(V,\theta):=\left\|\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}(V)\right\|_{G_h(\theta)^{-1}}\), then note by definition \(|\eta_k(V)|\leq 2H\), which implies \(\left\lVert h(V,\theta)\right\rVert_2\leq 2KH\kappa_1\) and \[|\eta_k(V_1)-\eta_k(V_2)|\leq |\mathcal{P}_hV_1-\mathcal{P}_hV_2|+\left\lVert V_1-V_2\right\rVert_\infty\leq 2\left\lVert V_1-V_2\right\rVert_\infty\] and \[\begin{align} \left\lVert h(V_1,\theta_1)-h(V_2,\theta_2)\right\rVert_2\leq& K \max_k\left(2H\left\lVert x_k(\theta_1)-x_k(\theta_2)\right\rVert_2+\kappa_1|\eta_k(V_1)-\eta_k(V_2)|\right)\\ \leq&K(2H\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2+2\kappa_1\left\lVert V_1-V_2\right\rVert_\infty). \end{align}\] Furthermore, \[\begin{align} &\left\lVert G_h(\theta_1)^{-1}-G_h(\theta_2)^{-1}\right\rVert_2\leq \left\lVert G_h(\theta_1)^{-1}\right\rVert_2\left\lVert G_h(\theta_1)-G_h(\theta_2)\right\rVert_2\left\lVert G_h(\theta_2)^{-1}\right\rVert_2\\ \leq& \frac{1}{\lambda^2}K\sup_k\left\lVert\nabla f(\theta_1, \phi_{h,k})\cdot \nabla f(\theta_1, \phi_{h,k})^\top-\nabla f(\theta_2, \phi_{h,k})\cdot \nabla f(\theta_2, \phi_{h,k})^\top\right\rVert_2\\ \leq& \frac{1}{\lambda^2}K\sup_k\left[\left\lVert(\nabla f(\theta_1, \phi_{h,k})-\nabla f(\theta_2, \phi_{h,k}))\cdot \nabla f(\theta_1, \phi_{h,k})^\top\right\rVert_2+\left\lVert\nabla f(\theta_2, \phi_{h,k})\cdot (\nabla f(\theta_1, \phi_{h,k})^\top-\nabla f(\theta_2, \phi_{h,k})^\top)\right\rVert_2\right]\\ \leq&\frac{2\kappa_1 K}{\lambda^2}\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2=\frac{2\kappa_1\kappa_2K}{\lambda^2 }\left\lVert\theta_1-\theta_2\right\rVert_2. \end{align}\] All the above imply \[\begin{align} &|H(V_1,\theta_1)-H(V_2,\theta_2)|\leq \sqrt{\left|h(V_1,\theta_1)^\top G_h(\theta_1)^{-1}h(V_1,\theta_1)-h(V_2,\theta_2)^\top G_h(\theta_2)^{-1}h(V_2,\theta_2)\right|}\\ \leq &\sqrt{\left\lVert h(V_1,\theta_1)-h(V_2,\theta_2)\right\rVert_2\cdot \frac{1}{\lambda}\cdot 2KH\kappa_1} +\sqrt{2KH\kappa_1\cdot \left\lVert G_h(\theta_1)^{-1}-G_h(\theta_2)^{-1}\right\rVert_2\cdot 2KH\kappa_1}\\ +&\sqrt{ 2KH\kappa_1\cdot\frac{1}{\lambda}\cdot \left\lVert h(V_1,\theta_1)-h(V_2,\theta_2)\right\rVert_2}\\ \leq&2\sqrt{K(2H\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2+2\kappa_1\left\lVert V_1-V_2\right\rVert_\infty)\cdot \frac{1}{\lambda}\cdot 2KH\kappa_1}+\sqrt{2KH\kappa_1\cdot \frac{2\kappa_1\kappa_2K}{\lambda^2 }\left\lVert\theta_1-\theta_2\right\rVert_2\cdot 2KH\kappa_1}\\ \leq & \left(4\sqrt{K^3H^2\kappa_1\kappa_2\frac{1}{\lambda}}+\sqrt{8K^3H^2\kappa_1^3\kappa_2\frac{1}{\lambda^2}}\right)\sqrt{\left\lVert\theta_1-\theta_2\right\rVert_2}+4\sqrt{K^3\kappa_1^2H\frac{1}{\lambda}\left\lVert V_1-V_2\right\rVert_\infty} \end{align}\] Then a \(\epsilon\)-covering net of \(\{H(V,\theta)\}\) can be constructed by the union of \(\frac{\epsilon^2}{4\left(4\sqrt{K^3H^2\kappa_1\kappa_2\frac{1}{\lambda}}+\sqrt{8K^3H^2\kappa_1^3\kappa_2\frac{1}{\lambda^2}}\right)^2}\)-covering net of \(\{\theta\in\Theta\}\) and \(\frac{\epsilon^2}{4(4\sqrt{K^3\kappa_1^2H\frac{1}{\lambda}})^2}\)-covering net of \(\mathcal{V}\) in Lemma 23. The covering number \(\mathcal{N}_\epsilon\) satisfies \[\begin{align} \log \mathcal{N}_\epsilon\leq &d\log\left(1+\frac{8C_\Theta\left(4\sqrt{K^3H^2\kappa_1\kappa_2\frac{1}{\lambda}}+\sqrt{8K^3H^2\kappa_1^3\kappa_2\frac{1}{\lambda^2}}\right)^2 }{\epsilon^2}\right)\\ +&d\log\left(1+\frac{8C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\frac{\epsilon^4}{16(4\sqrt{K^3\kappa_1^2H\frac{1}{\lambda}})^4}}\right)+d^2\log\left(1+\frac{8\sqrt{d}B\kappa_1^2}{\frac{\epsilon^4}{16(4\sqrt{K^3\kappa_1^2H\frac{1}{\lambda}})^4}}\right). \end{align}\]

Step3. First note by definition in Step2 \[\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right\rVert_{\Sigma_h^{-1}}=H(\widehat{V}_{h+1},\widehat{\theta}_h)\]and with probability \(1-\delta\) \[\label{eqn:union95ineq} \begin{align} |\eta_k(\widehat{V}_{h+1})|=&|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})|\\ \leq &\kappa_1\cdot \left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\theta^\star_h\right\rVert_2+\left\lVert\widehat{V}_{h+1}-{V}^\star_{h+1}\right\rVert_\infty\\ \leq&\kappa_1\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+C\left(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}}\right)=\widetilde{O}\left(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}}\right) \end{align}\tag{8}\] where the second inequality uses \(\theta_{\mathbb{T}{V}^\star_{h+1}}=\theta^\star_h\)and the third inequality uses Theorem 6 and Theorem 7. The last equal sign is due to \(C_{d,\log K}\leq \widetilde{O}(d^2)\) (recall Lemma 10).

Now choosing \(\epsilon=O(1/K)\) in Step2 and union bound over both 8 and covering number in Step2, we obtain with probability \(1-\delta\), \[\label{eqn:one} H(\widehat{V}_{h+1},\widehat{\theta}_h)=\left\|\sum_{k=1}^{K} {x}_{k} (\widehat{\theta}_h)\eta_{k}(\widehat{V}_{h+1})\right\|_{G_h(\widehat{\theta}_h)^{-1}} \leq \widetilde{O}(\kappa_1H^2\sqrt{\frac{d^2}{\kappa K}})\sqrt{{d}+d^2}=\widetilde{O}(\frac{\kappa_1H^2 d^2}{\sqrt{\kappa K}})\tag{9}\] where we absorb all the Polylog terms. Meanwhile, by Lemma 19 with probability \(1-\delta\), \[\label{eqn:two} \left\lVert\nabla f(\widehat{\theta}_{h},\phi_{s,a})\right\rVert_{\Sigma_h^{-1}}\leq \frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K}).\tag{10}\] Finally, by 9 and 10 and a union bound, we have with probability \(1-\delta\), \[\begin{align} |I_2|:=&\left|{\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})]}\right|\\ \leq &\left\lVert\nabla f(\widehat{\theta}_{h},\phi_{s,a})\right\rVert_{\Sigma_h^{-1}}\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right\rVert_{\Sigma_h^{-1}}\\ =&\left\lVert\nabla f(\widehat{\theta}_{h},\phi_{s,a})\right\rVert_{\Sigma_h^{-1}}\cdot H(\widehat{V}_{h+1},\widehat{\theta}_h)\leq \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\cdot \widetilde{O}(\frac{\kappa_1H^2 d^2}{\sqrt{\kappa K}})=\widetilde{O}(\frac{\kappa_1^2H^2d^2}{\kappa K})+\widetilde{O}(\frac{1}{K^{3/2}}) \end{align}\] where the first inequality is Cauchy–Schwarz inequality. ◻

10.4 Bounding the main term \(I_1\)↩︎

In this section, we bound the dominate term \[I_1:=\nabla f(\widehat{\theta}_{h},\phi(s,a))\Sigma_h^{-1}[\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})].\] First of all, by Cauchy–Schwarz inequality, we have \[\label{eqn:dominate} |I_1|\leq \left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot \left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right\rVert_{\Sigma_h^{-1}}.\tag{11}\] Then we have the following Lemma to bound \(I_1\).

Lemma 8. With probability \(1-\delta\), \[|I_1|\leq 4Hd\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot C_{\delta,\log K}+\widetilde{O}(\frac{\kappa_1}{\sqrt{\kappa}K}),\] where \(C_{\delta,\log K}\) only contains Polylog terms.

Proof of Lemma 8. Step1. Let the fixed \(\theta\in\Theta\) be arbitrary and define \(x_k(\theta)=\nabla_\theta f({\theta},\phi_{h,k})\). Next, define \({G}_h(\theta)=\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top+\lambda I_d\), then \(\left\lVert x_k\right\rVert_2\leq\kappa_1\). Also denote \(\eta_k :=f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\), then \(\mathbb{E}[\eta_k|s_h^k,a_h^k]=0\) and \(|\eta_k|\leq H\). Now by self-normalized Hoeffding’s inequality (Lemma 17), with probability \(1-\delta\) (recall \(t:=K\) in Lemma 17), \[\left\|\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}\right\|_{G_h(\theta)^{-1}} \leq 2H\sqrt{{d}\log \left(\frac{\lambda+K\kappa_1}{\lambda\delta}\right)}.\] Step2. Define \(h(\theta):=\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}\) and \(H(\theta):=\left\|\sum_{k=1}^{K} {x}_{k} (\theta)\eta_{k}\right\|_{G_h(\theta)^{-1}}\), then note by definition \(|\eta_k|\leq H\), which implies \(\left\lVert h(\theta)\right\rVert_2\leq KH\kappa_1\) and by \(x_k(\theta_1)-x_k(\theta_2)=\nabla^2_{\theta\theta}f(\xi,\phi)\cdot(\theta_1-\theta_2)\), \[\begin{align} \left\lVert h(\theta_1)-h(\theta_2)\right\rVert_2\leq& K \max_k\left(H\left\lVert x_k(\theta_1)-x_k(\theta_2)\right\rVert_2\right) \leq HK\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2. \end{align}\] Furthermore, \[\begin{align} &\left\lVert G_h(\theta_1)^{-1}-G_h(\theta_2)^{-1}\right\rVert_2\leq \left\lVert G_h(\theta_1)^{-1}\right\rVert_2\left\lVert G_h(\theta_1)-G_h(\theta_2)\right\rVert_2\left\lVert G_h(\theta_2)^{-1}\right\rVert_2\\ \leq& \frac{1}{\lambda^2}K\sup_k\left\lVert\nabla f(\theta_1, \phi_{h,k})\cdot \nabla f(\theta_1, \phi_{h,k})^\top-\nabla f(\theta_2, \phi_{h,k})\cdot \nabla f(\theta_2, \phi_{h,k})^\top\right\rVert_2\\ \leq&\frac{2\kappa_1 K}{\lambda^2}\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2=\frac{2\kappa_1\kappa_2K}{\lambda^2 }\left\lVert\theta_1-\theta_2\right\rVert_2. \end{align}\] All the above imply \[\begin{align} &|H(\theta_1)-H(\theta_2)|\leq \sqrt{\left|h(\theta_1)^\top G_h(\theta_1)^{-1}h(\theta_1)-h(\theta_2)^\top G_h(\theta_2)^{-1}h(\theta_2)\right|}\\ \leq &\sqrt{\left\lVert h(\theta_1)-h(\theta_2)\right\rVert_2\cdot \frac{1}{\lambda}\cdot KH\kappa_1} +\sqrt{KH\kappa_1\cdot \left\lVert G_h(\theta_1)^{-1}-G_h(\theta_2)^{-1}\right\rVert_2\cdot KH\kappa_1}\\ +&\sqrt{ KH\kappa_1\cdot\frac{1}{\lambda}\cdot \left\lVert h(\theta_1)-h(\theta_2)\right\rVert_2}\\ \leq&2\sqrt{KH\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2\cdot \frac{1}{\lambda}\cdot KH\kappa_1}+\sqrt{KH\kappa_1\cdot \frac{2\kappa_1\kappa_2K}{\lambda^2 }\left\lVert\theta_1-\theta_2\right\rVert_2\cdot KH\kappa_1}\\ \leq & \left(\sqrt{4K^2H^2\kappa_1\kappa_2/\lambda}+\sqrt{2K^3H^2\kappa_1^3\kappa_2/\lambda^2}\right)\sqrt{\left\lVert\theta_1-\theta_2\right\rVert_2} \end{align}\] Then a \(\epsilon\)-covering net of \(\{H(\theta)\}\) can be constructed by the union of \(\frac{\epsilon^2}{\left(\sqrt{4K^2H^2\kappa_1\kappa_2/\lambda}+\sqrt{2K^3H^2\kappa_1^3\kappa_2/\lambda^2}\right)^2}\)-covering net of \(\{\theta\in\Theta\}\). By Lemma 22, the covering number \(\mathcal{N}_\epsilon\) satisfies \[\begin{align} \log \mathcal{N}_\epsilon\leq &d\log\left(1+\frac{2C_\Theta\left(\sqrt{4K^2H^2\kappa_1\kappa_2/\lambda}+\sqrt{2K^3H^2\kappa_1^3\kappa_2/\lambda^2}\right)^2 }{\epsilon^2}\right)=\widetilde{O}(d) \end{align}\]

Step3. First note by definition in Step2 \[\left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right\rVert_{\Sigma_h^{-1}}=H(\widehat{\theta}_h)\] Now choosing \(\epsilon=O(1/K)\) in Step2 and union bound over the covering number in Step2, we obtain with probability \(1-\delta\), \[\label{eqn:three} H(\widehat{\theta}_h)=\left\|\sum_{k=1}^{K} {x}_{k} (\widehat{\theta}_h)\eta_{k}\right\|_{G_h(\widehat{\theta}_h)^{-1}} \leq 2H\sqrt{{d}\left[\log \left(\frac{\lambda+K\kappa_1}{\lambda\delta}\right)+\widetilde{O}(d)\right]}+O(\frac{1}{K}).\tag{12}\] where we absorb all the Polylog terms. Combing above with 11 , we obtain with probability \(1-\delta\), \[\begin{align} |I_1|\leq &\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot \left\lVert\sum_{k=1}^K \left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right\rVert_{\Sigma_h^{-1}}\\ \leq &\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot\left(2H\sqrt{{d}\left[\log \left(\frac{\lambda+K\kappa_1}{\lambda\delta}\right)+\widetilde{O}(d)\right]}+O(\frac{1}{K})\right)\\ \leq&4Hd\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot C_{\delta,\log K}+\widetilde{O}(\frac{\kappa_1}{\sqrt{\kappa}K}), \end{align}\] where \(C_{\delta,\log K}\) only contains Polylog terms. ◻

10.5 Analyzing \(\mathrm{Hot}_2\) in 7 ↩︎

Lemma 9. Recall \(\mathrm{Hot}_2:= \nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \left[\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})+\lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}\right]\). If the number of episode \(K\) satisfies \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\kappa\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\), then with probability \(1-\delta\), \[\left|\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \left[\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})+\lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}\right]\right|\leq \widetilde{O}\left(\frac{\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^2+\frac{d^2H^3\kappa_3+\lambda\kappa_1C_\Theta}{\kappa}}{K}\right)\] where \(\widetilde{O}\) absorbs all the constants and Polylog terms.

Proof of Lemma 9. Step1: we first show with probability \(1-\delta\) \[\left|\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right|\leq \widetilde{O}(\frac{1}{K}).\]

Recall by plug in \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\) in 3 , we have \[Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})-Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})=\frac{\partial}{\partial \theta}Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})+R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}}),\] and by second-order Taylor’s Theorem we have \[\label{eqn:R95k} \begin{align} \left\lVert R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2=&\left\lVert Z_h(\theta_{\mathbb{T}\widehat{V}_{h+1}}|\widehat{V}_{h+1})-Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})-\frac{\partial}{\partial \theta}Z_h(\widehat{\theta}_h|\widehat{V}_{h+1})(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})\right\rVert_2\\ =&\frac{1}{2}\left\lVert(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})^\top\frac{\partial^2}{\partial \theta\partial\theta}Z_h(\xi|\widehat{V}_{h+1})(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h})\right\rVert_2\\ \leq&\frac{1}{2}\kappa_{z_2}\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right\rVert_2^2 \end{align}\tag{13}\] Note \[\label{eqn:covari} \begin{align} \left.\frac{\partial^2}{\partial\theta\theta}Z_h(\theta|\widehat{V}_{h+1})\right|_{\theta=\xi}=&\frac{\partial}{\partial \theta}\Sigma^s_h= \sum_{k=1}^K\frac{\partial}{\partial \theta}\left\{\left( f(\xi,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\xi,\phi_{h,k})\right\}\\ +&\sum_{k=1}^K\frac{\partial}{\partial \theta}\left(\nabla_{\theta} f(\xi,\phi_{h,k})\nabla_{\theta}^\top f(\xi,\phi_{h,k})+\lambda I_d\right) \end{align}\tag{14}\] Therefore, we can bound \(\kappa_{z_2}\) with \(\kappa_{z_2}\leq (H\kappa_3+3\kappa_1\kappa_2)K\) and this implies with probability \(1-\delta/2\), \[\begin{align} \left\lVert R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2\leq &\frac{1}{2}\kappa_{z_2}\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right\rVert_2^2\leq \frac{1}{2}(H\kappa_3+3\kappa_1\kappa_2)K\cdot\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right\rVert_2^2\\ \leq&\frac{1}{2}(H\kappa_3+3\kappa_1\kappa_2)K\cdot\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}\\ \leq& \widetilde{O}((H\kappa_3+3\kappa_1\kappa_2)H^2d^2/\kappa). \end{align}\] And by Corollary 2 with probability \(1-\delta/2\), \[\left\lVert\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2\leq \widetilde{O}(1),\] Therefore, by Lemma 19 and a union bound with probability \(1-\delta\), \[\begin{align} &|\nabla f(\widehat{\theta}_h,\phi(s,a))^\top\Sigma^{-1}_h\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})|=\left|\nabla f(\widehat{\theta}_h,\phi(s,a))^\top\Sigma^{-1}_h\left(\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right)\right|\\ &\leq \left\lVert\nabla f(\widehat{\theta}_h,\phi(s,a))\right\rVert_{\Sigma^{-1}_h}\left\lVert\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_{\Sigma^{-1}_h}\\ &\leq \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\left\lVert\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_{\Sigma^{-1}_h}\\ &\leq \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\left(\frac{C}{\sqrt{ K}}+O(\frac{1}{K})\right)=\widetilde{O}\left(\frac{\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^2+\frac{d^2H^3\kappa_3}{\kappa}}{K}\right) \end{align}\] where \(\widetilde{O}\) absorbs all the constants and Polylog terms. Here the last inequality uses bound for \(\left\lVert R_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2\) and \(\left\lVert\Delta_{\Sigma^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})\right\rVert_2\).

Step2: By Lemma 19, with probability \(1-\delta\), \[\begin{align} &\left|\nabla f(\widehat{\theta}_h,\phi(s,a))\Sigma^{-1}_h \lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}\right| \leq \lambda \left\lVert\nabla f(\widehat{\theta}_h,\phi(s,a))\right\rVert_{\Sigma^{-1}_h}\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_{\Sigma^{-1}_h}\\ &\leq\lambda \left(\frac{2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)\cdot\left(\frac{2C_\Theta}{\sqrt{\kappa K}}+O(\frac{1}{K})\right)=\frac{4\lambda\kappa_1 C_\Theta }{\kappa K}+O(\frac{1}{K^{\frac{3}{2}}}) \end{align}\] ◻

11 Proof of Theorem 3 ↩︎

Now we are ready to prove Theorem 3. In particular, we prove the first part. Also, recall that we consider the exact Bellman completeness (\(\epsilon_{\mathcal{F}}=0\)).

11.1 The first part↩︎

Proof of Theorem 3 (first part). First of all, from the previous calculation (2 ), (7 ), we have \[\begin{align} \left|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)\right| \leq&\left|\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\right|+\left|\mathrm{Hot}_{h,1}\right|\\ \leq&|I_1|+|I_2|+|I_3|+|\mathrm{Hot}_{h,2}|+\left|\mathrm{Hot}_{h,1}\right|\\ \end{align}\]

Now by Lemma 6, Lemma 7, Lemma 8, Lemma 9 and Lemma 3 (and a union bound), with probability \(1-\delta\), \[\begin{align} |I_3|\leq& \widetilde{O}(\sqrt{\frac{d^3H^2\kappa_2^2\kappa_1^2}{\kappa^3}}){\frac{1}{K}},\\ |I_2|\leq& \widetilde{O}(\frac{\kappa_1^2H^2d^2}{\kappa K})+\widetilde{O}(\frac{1}{K^{3/2}}),\\ |I_1|\leq& 4Hd\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot C_{\delta,\log K}+\widetilde{O}(\frac{\kappa_1}{\sqrt{\kappa}K}),\\ |\mathrm{Hot}_{2,h}|\leq& \widetilde{O}\left(\frac{\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^2+\frac{d^2H^3\kappa_3+\lambda\kappa_1C_\Theta}{\kappa}}{K}\right),\\ |\mathrm{Hot}_{1,h}|\leq&\widetilde{O}(\frac{H^2\kappa_2d^2}{\kappa})\frac{1}{K}. \end{align}\] Finally, Plug the above into Lemma 2, by a union bound over all \(h\in[H]\), we have with probability \(1-\delta\), for any policy \(\pi\), \[\begin{align} v^\pi-v^{\widehat{\pi}}\leq& \sum_{h=1}^H 2\cdot \mathbb{E}_\pi\left[|I_1|+|I_2|+|I_3|+|\mathrm{Hot}_{h,2}|+\left|\mathrm{Hot}_{h,1}\right|\right]\\ \leq& \sum_{h=1}^H 8 dH\mathbb{E}_\pi\left[\sqrt{\nabla^\top f(\widehat{\theta}_h,\phi(s_h,a_h))\Sigma^{-1}_h\nabla f(\widehat{\theta}_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K}). \end{align}\] where \(\iota = C_{\delta,\log K}\) only contains Polylog terms and \[C_{\mathrm{hot}}=\frac{\kappa_1H}{\sqrt{\kappa}}+\frac{\kappa_1^2H^3d^2}{\kappa }+\sqrt{\frac{d^3H^4\kappa_2^2\kappa_1^2}{\kappa^3}}+\kappa_2\max(\frac{\kappa_1}{\kappa},\frac{1}{\sqrt{\kappa}})d^2H^3+\frac{d^2H^4\kappa_3+\lambda\kappa_1C_\Theta}{\kappa}+\frac{H^3\kappa_2d^2}{\kappa}\] ◻

11.2 The second part↩︎

Next we prove the second part of Theorem 3.

Proof of Theorem 3 (second part). Step1. Choose \(\pi=\pi^\star\) in the first part, we have \[0\leq v^{\pi^\star}-v^{\widehat{\pi}}\leq \sum_{h=1}^H 8 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))\Sigma^{-1}_h\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K}),\] Next, by the triangular inequality of the norm to obtain \[\begin{align} &\left|\left\lVert\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{-1}}-\left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{-1}}\right|\\ \leq& \left\lVert\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))-\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{-1}}\\ =&\left\lVert\nabla^2_{\theta\theta} f(\xi,\phi(s_h,a_h))\cdot \left(\widehat{\theta}_h-\theta^\star_h\right)\right\rVert_{\Sigma_h^{-1}},\\ \end{align}\] since with probability \(1-\delta\), \[\left\lVert\nabla^2_{\theta\theta} f(\xi,\phi(s_h,a_h))\cdot \left(\widehat{\theta}_h-\theta^\star_h\right)\right\rVert_2\leq \kappa_2 \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2\leq \widetilde{O}\left(\frac{\kappa_1\kappa_2 H^2d}{\kappa}\sqrt{\frac{1}{K}}\right),\] where the last inequality uses part three of Theorem 7. Then by a union bound and Lemma 19, \[\left\lVert\nabla^2_{\theta\theta} f(\xi,\phi(s_h,a_h))\cdot \left(\widehat{\theta}_h-\theta^\star_h\right)\right\rVert_{\Sigma_h^{-1}}\leq \widetilde{O}\left(\frac{\kappa_1\kappa_2 H^2d}{\kappa^{3/2}}\cdot{\frac{1}{K}}\right).\] Step2. Next, we show with probability \(1-\delta\), \[\begin{align} \left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{-1}}\leq 2\left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{\star-1}}. \end{align}\]

First of all, \[\begin{align} &\left\lVert\frac{1}{K}\Sigma_h-\frac{1}{K}\Sigma^\star_h\right\rVert_2=\left\lVert\frac{1}{K}\left(\sum_{k=1}^K \nabla f(\widehat{\theta}_h,\phi(s,a))\nabla f(\widehat{\theta}_h,\phi(s,a))^\top-\nabla f({\theta}^\star_h,\phi(s,a))\nabla f({\theta}^\star_h,\phi(s,a))^\top\right)\right\rVert_2\\ \leq&\sup_{s,a}\left(\left\lVert\left(\nabla f(\widehat{\theta}_h,\phi(s,a))-\nabla f({\theta}^\star_h,\phi(s,a))\right)\nabla f(\widehat{\theta}_h,\phi(s,a))\right\rVert_2\right.\\ +&\left.\left\lVert\left(\nabla f(\widehat{\theta}_h,\phi(s,a))-\nabla f({\theta}^\star_h,\phi(s,a))\right)\nabla f(\widehat{\theta}_h,\phi(s,a))\right\rVert_2\right)\\ \leq& 2\kappa_2\kappa_1 \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2\leq \widetilde{O}\left(\frac{\kappa_2\kappa^2_1H^2d}{\kappa}\sqrt{\frac{1}{K}}\right) \end{align}\]

Second, by Lemma 20 with probability \(1-\delta\) \[\left\lVert\frac{\Sigma^{\star}_h}{K}-\mathbb{E}_\mu[\nabla_\theta f({\theta}^\star_h,\phi)\nabla_\theta f({\theta}^\star_h,\phi)^\top]-\frac{\lambda}{K}\right\rVert\leq \frac{4 \sqrt{2} \kappa_1^{2}}{\sqrt{K}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}\] This implies \[\begin{align} \left\lVert\frac{\Sigma^{\star}_h}{K}\right\rVert\leq &\left\lVert\mathbb{E}_\mu[\nabla_\theta f({\theta}^\star_h,\phi)\nabla_\theta f({\theta}^\star_h,\phi)^\top]\right\rVert+\frac{\lambda}{K}+\frac{4 \sqrt{2} \kappa_1^{2}}{\sqrt{K}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}\\ \leq & \kappa_1^2+\lambda +{4 \sqrt{2} \kappa_1^{2}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}\\ \end{align}\] and also by Weyl’s spectrum theorem and under the condition \(K\geq \frac{128\kappa_1^4\log(2d/\delta)}{\kappa^2}\), with probability \(1-\delta\) \[\begin{align} \lambda_{\min}(\frac{\Sigma^{\star}_h}{K})\geq &\lambda_{\min}\left(\mathbb{E}_\mu[\nabla_\theta f({\theta}^\star_h,\phi)\nabla_\theta f({\theta}^\star_h,\phi)^\top]\right)+\frac{\lambda}{K}-\frac{4 \sqrt{2} \kappa_1^{2}}{\sqrt{K}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}\\ \geq &\kappa+\frac{\lambda}{K}-\frac{4 \sqrt{2} \kappa_1^{2}}{\sqrt{K}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}\geq \frac{\kappa}{2}\\ \end{align}\] then \(\left\lVert(\frac{\Sigma^{\star}_h}{K})^{-1}\right\rVert\leq \frac{2}{\kappa}\). Similarly, with probability \(1-\delta\), \(\left\lVert(\frac{\Sigma_h}{K})^{-1}\right\rVert\leq \frac{2}{\kappa}\). Then by Lemma 21, \[\begin{align} \left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s,a))\right\rVert_{K\Sigma_h^{-1}}\leq& \left[1+\sqrt{\left\lVert K\Sigma_h^{\star-1}\right\rVert\left\lVert\Sigma_h^\star/K\right\rVert\cdot\left\lVert K\Sigma_h^{-1}\right\rVert\cdot\left\lVert\Sigma_h/K-\Sigma_h^\star/K\right\rVert}\right]\cdot \left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s,a))\right\rVert_{K\Sigma_h^{\star-1}}\\ \leq&\left[1+\sqrt{\frac{4}{\kappa^2}O(\kappa_1^2+\lambda)\widetilde{O}\left(\frac{\kappa_2\kappa^2_1H^2d}{\kappa}\sqrt{\frac{1}{K}}\right)}\right]\cdot \left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s,a))\right\rVert_{K\Sigma_h^{\star-1}}\\ \leq& 2\left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s,a))\right\rVert_{K\Sigma_h^{\star-1}}\\ \end{align}\]as long as \(K\geq \widetilde{O}(\frac{(\kappa_1^2+\lambda)^2\kappa_2^2\kappa_1^2H^4d^2}{\kappa^6})\). The above is equivalently to \[\left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{-1}}\leq 2\left\lVert\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))\right\rVert_{\Sigma_h^{\star-1}}.\] Combining Step1, Step2 and a union bound, we have with probability \(1-\delta\), \[\begin{align} 0\leq &v^{\pi^\star}-v^{\widehat{\pi}}\leq \sum_{h=1}^H 8 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))\Sigma^{-1}_h\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K})\\ \leq& \sum_{h=1}^H 8 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Sigma^{-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C_{\mathrm{hot}}}{K})+\widetilde{O}\left(\frac{\kappa_1\kappa_2 H^4d^2}{\kappa^{3/2}}\cdot{\frac{1}{K}}\right)\\ \leq &\sum_{h=1}^H 16 dH\cdot \mathbb{E}_{\pi^\star}\left[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Sigma^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\right]\cdot\iota+\widetilde{O}(\frac{C'_{\mathrm{hot}}}{K}) \end{align}\]where \(C'_{\mathrm{hot}}=C_{\mathrm{hot}}+\frac{\kappa_1\kappa_2 H^4d^2}{\kappa^{3/2}}\). ◻

12 Provable Efficiency by reduction to General Function Approximation↩︎

In this section, we bound the accuracy of the parameter difference \(\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\) via a reduction to General Function Approximation scheme in [@chen2019information].

Recall the objective \[\label{eqn:parameter95o} \begin{align} \ell_h(\theta):=\frac{1}{K} \sum_{k=1}^{K}\left[f\left(\theta, \phi(s_h^k,a_h^k)\right)-r(s_h^k,a^k_h)-\widehat{V}_{h+1}\left(s_{h+1}^k\right)\right]^{2}+\frac{\lambda}{K} \cdot\left\lVert\theta\right\rVert_2^2 \end{align}\tag{15}\] Then by definition, \(\widehat{\theta}_h:=\mathop{\mathrm{argmin}}_{\theta\in\Theta}\ell_h(\theta)\) and \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\) satisfies \(f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi)=\mathcal{P}_h \widehat{V}_{h+1}+\delta_{\widehat{V}_{h+1}}\). Therefore, in this case, we have the following lemma:

Lemma 10.

Fix \(h\in[H]\). With probability \(1-\delta\), \[\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})+\lambda C_\Theta^2}{K}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}.\] where the expectation over \(\mu\) is taken w.r.t. \((s_h^k,a_h^k,s_{h+1}^k)\) \(k=1,...,K\) only (i.e., first compute \(\mathbb{E}_\mu[\ell_h(\theta)]\) for a fixed \(\theta\), then plug-in either \(\widehat{\theta}_{h+1}\) or \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\)). Here \(C_{d,\log(K)}:=d\log(1+{24C_\Theta (H+1)\kappa_1}K)+ d\log\left(1+{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{\kappa_1\kappa_2/\lambda})^2}K^2\right)+d^2\log\left(1+{288H^2\sqrt{d}\kappa_1^2}K^2/\lambda\right)\).

Proof of Lemma 10. Step1: we first prove the case where \(\lambda=0\).

Indeed, fix \(h\in[H]\) and any function \(V(\cdot)\in\mathbb{R}^\mathcal{S}\). Similarly, define \(f_V(s,a):=f(\theta_{\mathbb{T}V},\phi)=\mathcal{P}_h V+\delta_V\). For any fixed \(\theta\in\Theta\), denote \(g(s,a)=f(\theta,\phi(s,a))\). Then define¹¹ \[X(g,V,f_V):=(g(s,a)-r-V(s'))^2-(f_V(s,a)-r-V(s'))^2.\] Since all episodes are independent of each other, \(X_k(g,V,f_V):=X(g(s_h^k,a^k_h),V(s_{h+1}^k),f_V(s_h^k,a^k_h))\) are independent r.v.s and it holds \[\label{eqn:ell95diff} \frac{1}{K}\sum_{k=1}^K X_k(g,V,f_V)=\ell(g)-\ell(f_V).\tag{16}\] Next, the variance of \(X\) is bounded by: \[\begin{align} &\mathrm{Var}[X(g,V,f_V)]\leq \mathbb{E}_\mu[X(g,f,f_V)^2]\\ =&\mathbb{E}_\mu\left[\left(\left(g(s_h,a_h)-r_h-V(s_{h+1})\right)^2-\left(f_V(s_h,a_h)-r_h-V(s_{h+1})\right)^2\right)^2\right]\\ =&\mathbb{E}_\mu\left[(g(s_h,a_h)-f_V(s_h,a_h))^2(g(s_h,a_h)+f_V(s_h,a_h)-2r_h-2V(s_{h+1}))^2\right]\\ \leq&4H^2\cdot\mathbb{E}_\mu[(g(s_h,a_h)-f_V(s_h,a_h))^2]\\ \leq &4H^2\cdot \mathbb{E}_\mu\left[\left(g(s_h,a_h)-r_h-V(s_{h+1})\right)^2-\left(f_V(s_h,a_h)-r_h-V(s_{h+1})\right)^2\right]+8H^3 \epsilon_{\mathcal{F}}\;\;(*)\\ =&4H^2\cdot \mathbb{E}_\mu[X(g,f,f_V)]+8H^3 \epsilon_{\mathcal{F}} \end{align}\] where the step \((*)\) comes from \[\label{eqn:decomp} \begin{align} &\mathbb{E}_\mu\left[\left(g(s_h,a_h)-r_h-V(s_{h+1})\right)^2-\left(f_V(s_h,a_h)-r_h-V(s_{h+1})\right)^2\right]\\ =&\mathbb{E}_\mu\left[\left(g(s_h,a_h)-f_V(s_h,a_h)\right)\cdot\left(g(s_h,a_h)+f_V(s_h,a_h)-2r_h-2V(s_{h+1})\right)\right]\\ =&\mathbb{E}_\mu\left[\left(g(s_h,a_h)-f_V(s_h,a_h)\right)\cdot\left(g(s_h,a_h)-f_V(s_h,a_h)+2f_V(s_h,a_h)-2r_h-2V(s_{h+1})\right)\right]\\ =&\mathbb{E}_\mu\left[\left(g(s_h,a_h)-f_V(s_h,a_h)\right)^2\right]+\mathbb{E}_\mu\left[2(g(s_h,a_h)-f_V(s_h,a_h))\mathbb{E}_{P_h}[f_V(s_h,a_h)-r_h-V(s_{h+1})\mid s_h,a_h]\right]\\ \geq &\mathbb{E}_\mu\left[\left(g(s_h,a_h)-f_V(s_h,a_h)\right)^2\right]-2H \left\lVert\delta_V\right\rVert_\infty \geq \mathbb{E}_\mu\left[\left(g(s_h,a_h)-f_V(s_h,a_h)\right)^2\right]-2H \epsilon_{\mathcal{F}} \end{align}\tag{17}\] where the last step uses law of total expectation and the definition of \(f_V\).

Therefore, by Bernstein inequality, with probability \(1-\delta\), \[\begin{align} &\mathbb{E}_\mu[X(g,f,f_V)]-\frac{1}{K}\sum_{k=1}^K X_k(g,f,f_V)\\ \leq & \sqrt{\frac{2\mathrm{Var}[X(g,f,f_V)]\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}\\ \leq & \sqrt{\frac{8H^2\mathbb{E}_\mu[X(g,f,f_V)]\log(1/\delta)}{K}}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}. \end{align}\] Now, if we choose \(g(s,a):= f(\widehat{\theta}_h,\phi(s,a))\), then \(\widehat{\theta}_h\) minimizes \(\ell_h(\theta)\), therefore, it also minimizes \(\frac{1}{K}\sum_{k=1}^K X_i(\theta,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})\) and this implies \[\frac{1}{K}\sum_{k=1}^K X_k(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})\leq \frac{1}{K}\sum_{k=1}^K X_k({\theta}_{\mathbb{T}\widehat{V}_{h+1}},\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})=0.\] Therefore, we obtain \[\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\leq \sqrt{\frac{8H^2\cdot\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\log(1/\delta)}{K}}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}.\] However, the above does not hold with probability \(1-\delta\) since \(\widehat{\theta}_h\) and \(\widehat{V}_{h+1}:=\min\{\max_a f(\widehat{\theta}_{h+1},\phi(\cdot,a))-\sqrt{\nabla f(\widehat{\theta}_{h+1},\phi(\cdot,a))^\top A\cdot\nabla f(\theta,\phi(\cdot,a))},H\}\) (where \(A\) is certain symmetric matrix with bounded norm) depend on \(\widehat{\theta}_h\) and \(\widehat{\theta}_{h+1}\) which are data-dependent. Therefore, we need to further apply covering Lemma 24 and choose \(\epsilon=O(1/K)\) and a union bound to obtain with probability \(1-\delta\), \[\begin{align} \mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]&\leq \sqrt{\frac{8H^2\cdot\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})](\log(1/\delta)+C_{d,\log K})}{K}}+\frac{7H^2(\log(1/\delta)+C_{d,\log K})}{3K}\\ &+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}} \end{align}\] where \(C_{d,\log(K)}:=\log(1+{24C_\Theta (H+1)\kappa_1}K)+ d\log\left(1+{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{\kappa_1\kappa_2/\lambda})^2}K^2\right)+d^2\log\left(1+{288H^2\sqrt{d}\kappa_1^2}K^2/\lambda\right)\).¹² Solving this quadratic equation to obtain with probability \(1-\delta\), \[\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})}{K}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}\] Now according to 16 , by definition we finally have with probability \(1-\delta\) (recall the expectation over \(\mu\) is taken w.r.t. \((s_h^k,a_h^k,s_{h+1}^k)\) \(k=1,...,K\) only) \[\label{eqn:result95bound} \begin{align} &\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h+1})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]=\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\\ &\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})}{K}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}. \end{align}\tag{18}\]

Step2. If \(\lambda>0\), there is only extra term \(\frac{\lambda}{K}\left(\left\lVert\widehat{\theta}_h\right\rVert_2-\left\lVert{\theta}_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\right)\leq \frac{\lambda}{K}\left\lVert\widehat{\theta}_h\right\rVert_2\leq \frac{\lambda C_\Theta^2}{K}\) in addition to above. This finishes the proof. ◻

Theorem 6 (Provable efficiency (Part I)). Let \(C_{d,\log K}\) be the same as Lemma 10. Then denote \(b_{d,K,\epsilon_{\mathcal{F}}}:= \sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}\), with probability \(1-\delta\) \[\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\leq \sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\sqrt{\frac{b_{d,K,\epsilon_{\mathcal{F}}}}{\kappa}}+\sqrt{\frac{2H\epsilon_{\mathcal{F}}}{\kappa}},\;\forall h\in[H].\]

Proof of Theorem 6. Apply a union bound in Lemma 10, we have with probability \(1-\delta\), \[\label{eqn:inter95one} \begin{align} &\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(H/\delta)+C_{d,\log K})+\lambda C_\Theta^2}{K}+b_{d,K,\epsilon_{\mathcal{F}}},\;\;\forall h\in[H]\\ \Rightarrow&\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})-\frac{\lambda}{K}\left\lVert\widehat{\theta}_{h}\right\rVert_2^2]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda}{K}\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2]\leq \frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{K}+b_{d,K,\epsilon_{\mathcal{F}}} \end{align}\tag{19}\] Now we prove for all \(h\in[H]\), \[\label{eqn:inter95two} \mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]\leq\mathbb{E}_\mu\left[\ell_h(\widehat{\theta}_{h})-\frac{\lambda\left\lVert\widehat{\theta}_{h}\right\rVert_2^2}{K}\right]-\mathbb{E}_\mu\left[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2}{K}\right]+2H\epsilon_{\mathcal{F}}.\tag{20}\] Indeed, similar to 18 , by definition we have \[\begin{align} &\mathbb{E}_\mu\left[\ell_h(\widehat{\theta}_{h})-\frac{\lambda\left\lVert\widehat{\theta}_{h}\right\rVert_2^2}{K}\right]-\mathbb{E}_\mu\left[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2}{K}\right]=\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\\ =&\mathbb{E}_\mu\left(\left[f\left(\widehat{\theta}_h, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right]^{2}-\left[f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right]^{2}\right)\\ =&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]\\ +&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(s_h,a_h))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s_h,a_h))\right)\cdot\left(f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right)\right]\\ =&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]\\ +&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(s_h,a_h))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s_h,a_h))\right)\cdot\mathbb{E}\left(f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\middle |s_h,a_h\right)\right]\\ \geq &\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]-2H\epsilon_{\mathcal{F}} \end{align}\] where the third identity uses \(\mu\) is taken w.r.t. \(s_h,a_h,s_{h+1}\) (recall Lemma 10) and law of total expectation. The first inequality uses the definition of \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\).

Now apply Assumption 3, we have \[\begin{align} &\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]\geq \kappa\left\lVert\widehat{\theta}_{h}-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert^2_2,\\ \end{align}\] Combine the above with 19 and 20 , we obtain the stated result. ◻

Theorem 7 (Provable efficiency (Part II)). Let \(C_{d,\log K}\) be the same as Lemma 10 and suppose \(\epsilon_{\mathcal{F}}=0\). Furthermore, suppose \(\lambda\leq 1/2C_\Theta^2\) and \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\). Then, with probability \(1-\delta\), \(\forall h\in[H]\), \[\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f(\theta^\star_h,\phi(s,a))\right|\leq \left(\kappa_1H\sqrt{\frac{36H^2(\log(H^2/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^2d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K}).\] Furthermore, we have with probability \(1-\delta\), \[\begin{align} \sup_{h}\left\lVert\widehat{V}_{h}-V^\star_{h}\right\rVert_\infty\leq &\left(\kappa_1H\sqrt{\frac{36H^2(\log(H^2/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^2d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\\ =&\widetilde{O}\left(\kappa_1H^2\sqrt{\frac{d^2}{\kappa}}\sqrt{\frac{1}{K}}\right) \end{align}\] where \(\widetilde{O}\) absorbs Polylog terms and higher order terms. Lastly, it also holds for all \(h\in[H]\), w.p. \(1-\delta\) \[\begin{align} \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2\leq& \left(\kappa_1H\frac{\sqrt{72H^2(\log(H^2/\delta)+C_{d,\log K})+4\lambda C_\Theta^2}}{\kappa }+\frac{4H^2d\kappa_1}{{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\\ =&\widetilde{O}\left(\frac{\kappa_1H^2d}{\kappa}\sqrt{\frac{1}{K}}\right) \end{align}\]

Proof of Theorem 7. Step1: we show the first result.

We prove this by backward induction. When \(h=H+1\), by convention \(f(\widehat{\theta}_h,\phi(s,a))=f(\theta^\star_h,\phi(s,a))=0\) so the base case holds. Suppose for \(h+1\), with probability \(1-(H-h)\delta\), it holds true that \(\sup_{s,a}\left|f(\widehat{\theta}_{h+1},\phi(s,a))-f(\theta^\star_{h+1},\phi(s,a))\right|\leq C_{h+1}\sqrt{\frac{1}{K}}+a(h+1)\), we next consider the case for \(t=h\).

On one hand, by Theorem 6, we have with probability \(1-\delta/2\), \[\begin{align} &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ \leq &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))\right|+\sup_{s,a}\left|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ =&\sup_{s,a}\left|\nabla f(\xi,\phi(s,a))^\top(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})\right|+\sup_{s,a}\left|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\theta_{\mathbb{T}V^\star_{h+1}},\phi(s,a))\right|\\ \leq & \kappa_1\cdot\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2+\sup_{s,a}\left|\mathcal{P}_{h,s,a}\widehat{V}_{h+1}-\mathcal{P}_{h,s,a}{V}^\star_{h+1}\right|\\ \leq&\kappa_1\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\left\lVert\widehat{V}_{h+1}-V^\star_{h+1}\right\rVert_\infty, \end{align}\] Recall \(\widehat{V}_{h+1}(\cdot):=\min\{\max_a f(\widehat{\theta}_{h+1},\phi(\cdot,a))-\Gamma_{h}(\cdot,a),H\}\) and \(V^\star_{h+1}(\cdot)=\max_a f(\theta^\star_{h+1},\phi(\cdot,a))=\min\{\max_a f(\theta^\star_{h+1},\phi(\cdot,a)),H\}\), we obtain \[\label{eqn:V95to95f} \begin{align} \left\lVert\widehat{V}_{h+1}-V^\star_{h+1}\right\rVert_\infty\leq \sup_{s,a}\left|f(\widehat{\theta}_{h+1},\phi(s,a))-f(\theta^\star_{h+1},\phi(s,a))\right|+\sup_{h,s,a}\Gamma_h(s,a) \end{align}\tag{21}\] Note the above holds true for any generic \(\Gamma_h(s,a)\). In particular, according to Algorithm 1, we specify \[\Gamma_{h}(\cdot, \cdot)= dH\sqrt{\nabla_{\theta} f(\widehat{\theta}_h,\phi(\cdot,\cdot))^{\top} \Sigma_{h}^{-1} \nabla_{\theta} f(\widehat{\theta}_h,\phi(\cdot,\cdot))}\left(+\widetilde{O}(\frac{1}{K})\right)\] and by Lemma 19, with probability \(1-\delta\), \[\Gamma_h\leq \frac{2dH\kappa_1}{\sqrt{\kappa K}}+\widetilde{O}(\frac{1}{K})\]

and by a union bound this implies with probability \(1-(H-h+1)\delta\), \[\begin{align} &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ \leq& C_{h+1}\sqrt{\frac{1}{K}}+\kappa_1\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\frac{2dH\kappa_1}{\sqrt{\kappa K}}+\widetilde{O}(\frac{1}{K}) :=C_h\sqrt{\frac{1}{K}}+\widetilde{O}(\frac{1}{K}) \end{align}\] Solving for \(C_h\), we obtain \(C_h\leq \kappa_1H\sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+H\frac{2dH\kappa_1}{\sqrt{\kappa }}\) for all \(H\). By a union bound (replacing \(\delta\) by \(\delta/H\)), we obtain the stated result.

Step2: Utilizing the intermediate result 21 , we directly have with probability \(1-\delta\), \[\sup_{h}\left\lVert\widehat{V}_{h}-V^\star_{h}\right\rVert_\infty\leq \sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|+\frac{2dH\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K}),\] where \(\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\) can be bounded using Step1.

Step3: Denote \(M:=\left(\kappa_1H\sqrt{\frac{36H^2(\log(H^2/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^2d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\), then by Step1 we have with probability \(1-\delta\) (here \(\xi\) is some point between \(\widehat{\theta}_h\) and \(\theta^\star_h\)) for all \(h\in[H]\) \[\begin{align} &M^2\geq \sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|^2\\ \geq &\mathbb{E}_{\mu,h}[(f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a)))^2]\geq \kappa \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2^2 \end{align}\] where the last inequality is by Assumption 3. Solve this to obtain the stated result. ◻

13 With positive Bellman completeness coefficient \(\epsilon_{\mathcal{F}}>0\)↩︎

In Theorem 3, we consider the case where \(\epsilon_{\mathcal{F}}=0\). If \(\epsilon_{\mathcal{F}}>0\), similar guarantee can be achieved with the measurement of model misspecification. For instance, the additional error \(\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}\) will show up in Lemma 10 (as stated in the current version), \(\sqrt{\frac{b_{d,K,\epsilon_{\mathcal{F}}}}{\kappa}}+\sqrt{\frac{2H\epsilon_{\mathcal{F}}}{\kappa}}\) will show up in Lemma 6. Then the decomposition in 2 will incur the extra \(\delta_{\widehat{V}_{h+1}}\) term with \(\delta_{\widehat{V}_{h+1}}\) might not be \(0\). The analysis with positive \(\epsilon_{\mathcal{F}}>0\) will make the proofs more intricate but incurs no additional technical challenge. Since the inclusion of this quantity is not our major focus, as a result, we only provide the proof for the case where \(\epsilon_{\mathcal{F}}=0\) so the readers can focus on the more critical components that characterize the hardness of differentiable function class.

14 VFQL and its analysis↩︎

We present the vanilla fitted Q-learning (VFQL) Algorithm 2 as follows. For VFQL, no pessimism is used and we assume \(\widehat{\theta}_h\in\Theta\) without loss of generality.

Figure 2: Vanilla Fitted Q-Learning (VFQL)

14.1 Analysis for VFQL (Theorem 2)↩︎

Recall \(\iota_h(s,a) := \mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{Q}_h(s,a)\) and the definition of Bellman operator 2. Note \(\min\{\cdot,H-h+1\}^+\) is a non-expansive operator, therefore we have \[\begin{align} |\iota_h(s,a)|=&|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{Q}_h(s,a)|=\left|\min \left\{ \mathcal{P}_h \widehat{V}_{h+1}(s,a), H-h+1\right\}^{+}-\min \left\{f(\widehat{\theta}_h,\phi(\cdot,\cdot)), H-h+1\right\}^{+}\right|\\ \leq &\left|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-f(\widehat{\theta}_h,\phi(\cdot,\cdot))\right|\leq \left|f(\theta_{\mathbb{T}\widehat{V}_{h+1}})-f(\widehat{\theta}_h,\phi(\cdot,\cdot))\right|+\epsilon_{\mathcal{F}}. \end{align}\] By Lemma 1, we have for any \(\pi\), \[\label{eqn:vfql95decom} \begin{align} v^{\pi}-v^{\widehat{\pi}}=&-\sum_{h=1}^H E_{\widehat{\pi}}[\iota_h(s_h,a_h)]+\sum_{h=1}^H E_{\pi}[\iota_h(s_h,a_h)]\leq \sum_{h=1}^H E_{\widehat{\pi}}[|\iota_h(s_h,a_h)|]+\sum_{h=1}^H E_{\pi}[|\iota_h(s_h,a_h)|]\\ \leq& \sum_{h=1}^H \mathbb{E}_{\widehat{\pi}}[|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))-f(\widehat{\theta}_h,\phi(\cdot,\cdot))|]+\sum_{h=1}^H \mathbb{E}_{{\pi}}[|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))-f(\widehat{\theta}_h,\phi(\cdot,\cdot))|]+2H\epsilon_{\mathcal{F}}\\ \leq&\sum_{h=1}^H \sqrt{\mathbb{E}_{\widehat{\pi}}[|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))-f(\widehat{\theta}_h,\phi(\cdot,\cdot))|^2]}+\sum_{h=1}^H \sqrt{\mathbb{E}_{{\pi}}[|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))-f(\widehat{\theta}_h,\phi(\cdot,\cdot))|^2]}+2H\epsilon_{\mathcal{F}}\\ \leq& 2 \sqrt{C_{\mathrm{eff}}}\sum_{h=1}^H \sqrt{\mathbb{E}_{\mu,h}[|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))-f(\widehat{\theta}_h,\phi(\cdot,\cdot))|^2]}+2H\epsilon_{\mathcal{F}} \end{align}\tag{22}\] where the second inequality uses Cauchy inequality and the third one uses the definition of concentrability coefficient 2.

Next, for VFQL, there is no pessimism therefore the quantity \(B\) in Lemma 24 is zero, hence the covering number applied in Lemma 10 is bounded by \(C_{d,\log(K)}\leq \widetilde{O}(d)\) and \[\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})+\lambda C_\Theta^2}{K}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+4H\epsilon_{\mathcal{F}}.\] Now leveraging 19 and 20 in Theorem 6 to obtain \[\begin{align} \mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]\leq&\mathbb{E}_\mu\left[\ell_h(\widehat{\theta}_{h})-\frac{\lambda\left\lVert\widehat{\theta}_{h}\right\rVert_2^2}{K}\right]-\mathbb{E}_\mu\left[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2}{K}\right]+2H\epsilon_{\mathcal{F}}\\ \leq& \frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{K}+b_{d,K,\epsilon_{\mathcal{F}}}+2H\epsilon_{\mathcal{F}} \end{align}\]

Plug the above into 22 , we obtain with probability \(1-\delta\), for all policy \(\pi\), \[\begin{align} &v^\pi-v^{\widehat{\pi}}\leq 2\sqrt{C_{\mathrm{eff}}}H \sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{K}+b_{d,K,\epsilon_{\mathcal{F}}}+2H\epsilon_{\mathcal{F}}}+2H\epsilon_{\mathcal{F}}\\ = &2\sqrt{C_{\mathrm{eff}}}H \sqrt{\frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{K}+\sqrt{\frac{16H^3\epsilon_{\mathcal{F}}(\log(1/\delta)+C_{d,\log K})}{K}}+6H\epsilon_{\mathcal{F}}}+2H\epsilon_{\mathcal{F}}\\ =&\sqrt{C_{\mathrm{eff}}}H\cdot\widetilde{O}\left(\sqrt{\frac{H^2d+\lambda C^2_\Theta}{K}}+\sqrt[\frac{1}{4}]{\frac{H^3d\epsilon_{\mathcal{F}}}{K}} \right)+O(\sqrt{C_\mathrm{eff} H^3 \epsilon_{\mathcal{F}}}+H\epsilon_{\mathcal{F}}) \end{align}\] This finishes the proof of Theorem 2.

15 Proofs for VAFQL↩︎

In this section, we present the analysis for variance-aware fitted Q learning (VAFQL). Throughout the whole section, we assume \(\epsilon_{\mathcal{F}}=0\), i.e. the exact Bellman-Completeness holds. The algorithm is presented in the following. Before giving the proofs of Theorem 3, we first prove some useful lemmas.

Figure 3: Variance-Aware Fitted Q Learning (VAFQL)

15.1 Provable Efficiency for Variance-Aware Fitted Q Learning↩︎

Recall the objective \[\begin{align} \ell_h(\theta):=\frac{1}{K} \sum_{k=1}^{K}\left[f\left(\theta, \phi(s_h^k,a_h^k)\right)-r(s_h^k,a^k_h)-\widehat{V}_{h+1}(s_{h+1}^k)\right]^{2}/\widehat{\sigma}^2_h(s_h^k,a_h^k)+\frac{\lambda}{K} \cdot\left\lVert\theta\right\rVert_2^2 \end{align}\] Then by definition, \(\widehat{\theta}_h:=\mathop{\mathrm{argmin}}_{\theta\in\Theta}\ell_h(\theta)\) and \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\) satisfies \(f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi)=\mathcal{P}_h \widehat{V}_{h+1}(s_{h+1}^k)\) (recall \(\epsilon_{\mathcal{F}}=0\)). Therefore, in this case, we have the following lemma:

Lemma 11. Fix \(h\in[H]\). With probability \(1-\delta\), \[\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})+\lambda C_\Theta^2}{K}\] where the expectation over \(\mu\) is taken w.r.t. \((s_h^k,a_h^k,s_{h+1}^k)\) \(k=1,...,K\) only (i.e., first compute \(\mathbb{E}_\mu[\ell_h(\theta)]\) for a fixed \(\theta\), then plug-in either \(\widehat{\theta}_{h+1}\) or \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\)). Here \(C_{d,\log(K)}:=d\log(1+{24C_\Theta (H+1)\kappa_1}K)+ d\log\left(1+{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{\kappa_1\kappa_2/\lambda})^2}K^2\right)+d^2\log\left(1+{288H^2\sqrt{d}\kappa_1^2}K^2/\lambda\right)+d\log(1+{16C_\Theta H^2\kappa_1K})+d\log(1+{32C_\Theta H^3\kappa_1}K)\).

Proof of Lemma 11. Step1: Consider the case where \(\lambda=0\). Indeed, fix \(h\in[H]\) and any function \(V(\cdot)\in\mathbb{R}^\mathcal{S}\). Similarly, define \(f_V(s,a):=f(\theta_{\mathbb{T}V},\phi)=\mathcal{P}_h V\). For any fixed \(\theta\in\Theta\), denote \(g(s,a)=f(\theta,\phi(s,a))\). Moreover, for any \(u,v\in\Theta\), define \[\sigma^2_{u,v}(\cdot,\cdot) := \max\{1,f(v,\phi(\cdot,\cdot))_{\left[0,(H-h+1)^{2}\right]}-\big[f(u,\phi(\cdot,\cdot))_{[0, H-h+1]}\big]^{2}\}\]

Then define (we omit the subscript \(u,v\) of \(\sigma^2_{u,v}\) for the illustration purpose when there is no ambiguity) \[X(g,V,f_V,\sigma^2):=\frac{(g(s,a)-r-V(s'))^2-(f_V(s,a)-r-V(s'))^2}{\sigma^2_{u,v}(s,a)}.\] Since all episodes are independent of each other, \(X_k(g,V,f_V):=X(g(s_h^k,a^k_h),V(s_{h+1}^k),f_V(s_h^k,a^k_h),\sigma^2(s^k_h,a^k_h))\) are independent r.v.s and it holds \[\label{eqn:VA95ell95diff} \frac{1}{K}\sum_{k=1}^K X_k(g,V,f_V,\sigma^2)=\ell(g)-\ell(f_V).\tag{23}\] Next, the variance of \(X\) is bounded by \[\begin{align} &\mathrm{Var}[X(g,V,f_V,\sigma^2)]\leq \mathbb{E}_\mu[X(g,f,f_V,\sigma^2)^2]\\ =&\mathbb{E}_\mu\left[\left(\left(g(s_h,a_h)-r_h-V(s_{h+1})\right)^2-\left(f_V(s_h,a_h)-r_h-V(s_{h+1})\right)^2\right)^2/\sigma^2(s_h,a_h)^2\right]\\ =&\mathbb{E}_\mu\left[\frac{(g(s_h,a_h)-f_V(s_h,a_h))^2}{\sigma^2(s_h,a_h)}\cdot \frac{(g(s_h,a_h)+f_V(s_h,a_h)-2r_h-2V(s_{h+1}))^2}{\sigma^2(s_h,a_h)}\right]\\ \leq&4H^2\cdot\mathbb{E}_\mu[\frac{(g(s_h,a_h)-f_V(s_h,a_h))^2}{\sigma^2(s_h,a_h)}]\\ =&4H^2\cdot \mathbb{E}_\mu\left[\frac{\left(g(s_h,a_h)-r_h-V(s_{h+1})\right)^2-\left(f_V(s_h,a_h)-r_h-V(s_{h+1})\right)^2}{\sigma^2(s_h,a_h)}\right]\;\;(*)\\ =&4H^2\cdot \mathbb{E}_\mu[X(g,f,f_V,\sigma^2)] \end{align}\] \((*)\) follows from that \[\mathbb{E}_\mu\left[\frac{f(\widehat{\theta}_{h},\phi(s_h,a_h))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s_h,a_h))}{\sigma^2(s_h,a_h)}\cdot\mathbb{E}\left(f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\middle |s_h,a_h\right)\right]=0.\]

Therefore, by Bernstein inequality, with probability \(1-\delta\), \[\begin{align} &\mathbb{E}_\mu[X(g,f,f_V,\sigma^2)]-\frac{1}{K}\sum_{k=1}^K X_k(g,f,f_V,\sigma^2)\\ \leq & \sqrt{\frac{2\mathrm{Var}[X(g,f,f_V,\sigma^2)]\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}\\ \leq & \sqrt{\frac{8H^2\mathbb{E}_\mu[X(g,f,f_V,\sigma^2)]\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}. \end{align}\] Now, if we choose \(g(s,a):= f(\widehat{\theta}_h,\phi(s,a))\) and \(u=\boldsymbol{u}_h,v=\boldsymbol{v}_h\) from Algorithm 3, then \(\widehat{\theta}_h\) minimizes \(\ell_h(\theta)\), therefore, it also minimizes \(\frac{1}{K}\sum_{k=1}^K X_i(\theta,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)\) and this implies \[\frac{1}{K}\sum_{k=1}^K X_k(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)\leq \frac{1}{K}\sum_{k=1}^K X_k({\theta}_{\mathbb{T}\widehat{V}_{h+1}},\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)=0.\] Thus, we obtain \[\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)]\leq \sqrt{\frac{8H^2\cdot\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)]\log(1/\delta)}{K}}+\frac{4H^2\log(1/\delta)}{3K}.\] However, the above does not hold with probability \(1-\delta\) since \(\widehat{\theta}_h\), \(\widehat{\sigma}^2_h\) and \(\widehat{V}_{h+1}:=\min\{\max_a f(\widehat{\theta}_{h+1},\phi(\cdot,a))-\sqrt{\nabla f(\widehat{\theta}_{h+1},\phi(\cdot,a))^\top A\cdot\nabla f(\theta,\phi(\cdot,a))},H\}\) (where \(A\) is certain symmetric matrix with bounded norm) depend on \(\widehat{\theta}_h\), \(\widehat{\theta}_{h+1}\) which are data-dependent. Therefore, we need to further apply covering Lemma 25 and choose \(\epsilon=O(1/K)\) and a union bound to obtain with probability \(1-\delta\), \[\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)]\leq \sqrt{\frac{8H^2\cdot\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}},\widehat{\sigma}^2_h)](\log(1/\delta)+C_{d,\log K})}{K}}+\frac{4H^2(\log(1/\delta)+C_{d,\log K})}{3K}.\] where \(C_{d,\log(K)}:=d\log(1+{24C_\Theta (H+1)\kappa_1}K)+ d\log\left(1+{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{\kappa_1\kappa_2/\lambda})^2}K^2\right)+d^2\log\left(1+{288H^2\sqrt{d}\kappa_1^2}K^2/\lambda\right)+d\log(1+{16C_\Theta H^2\kappa_1K})+d\log(1+{32C_\Theta H^3\kappa_1}K)\) (where we let \(B=1/\lambda\) since \(\left\lVert\Lambda_h^{-1}\right\rVert_2\leq 1/\lambda\)). Solving this quadratic equation to obtain with probability \(1-\delta\), \[\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})}{K}.\] Now according to 23 , by definition we finally have with probability \(1-\delta\) (recall the expectation over \(\mu\) is taken w.r.t. \((s_h^k,a_h^k,s_{h+1}^k)\) \(k=1,...,K\) only) \[\label{eqn:VA95result95bound} \mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h+1})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]=\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(1/\delta)+C_{d,\log K})}{K}\tag{24}\] where we used \(f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi)=\mathcal{P}_h \widehat{V}_{h+1}=f_{\widehat{V}_{h+1}}\).

Theorem 8 (Provable efficiency for VAFQL). Let \(C_{d,\log K}\) be the same as Lemma 11. Then, with probability \(1-\delta\) \[\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2\leq \sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}},\;\forall h\in[H].\]

Proof of Theorem 8. Apply a union bound in Lemma 11, we have with probability \(1-\delta\), \[\label{eqn:VA95inter95one} \begin{align} &\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})]\leq \frac{36H^2(\log(H/\delta)+C_{d,\log K})+\lambda C_\Theta^2}{K},\;\;\forall h\in[H]\\ \Rightarrow&\mathbb{E}_\mu[\ell_h(\widehat{\theta}_{h})-\frac{\lambda}{K}\left\lVert\widehat{\theta}_{h}\right\rVert_2^2]-\mathbb{E}_\mu[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda}{K}\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2]\leq \frac{36H^2(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{K} \end{align}\tag{25}\]

Now we prove for all \(h\in[H]\), \[\label{eqn:VA95inter95two} \mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]=\mathbb{E}_\mu\left[\ell_h(\widehat{\theta}_{h})-\frac{\lambda\left\lVert\widehat{\theta}_{h}\right\rVert_2^2}{K}\right]-\mathbb{E}_\mu\left[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2}{K}\right].\tag{26}\] Indeed, identical to 24 , \[\begin{align} &\mathbb{E}_\mu\left[\ell_h(\widehat{\theta}_{h})-\frac{\lambda\left\lVert\widehat{\theta}_{h}\right\rVert_2^2}{K}\right]-\mathbb{E}_\mu\left[\ell_h(\theta_{\mathbb{T}\widehat{V}_{h+1}})-\frac{\lambda\left\lVert\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2^2}{K}\right]=\mathbb{E}_\mu[X(\widehat{\theta}_h,\widehat{V}_{h+1},f_{\widehat{V}_{h+1}})]\\ =&\mathbb{E}_\mu\left(\left[f\left(\widehat{\theta}_h, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right]^{2}/\widehat{\sigma}^2_h(s_h,a_h)-\left[f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right]^{2}/\widehat{\sigma}^2_h(s_h,a_h)\right)\\ =&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2/\widehat{\sigma}^2_h(\cdot,\cdot)\right]\\ +&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(s_h,a_h))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s_h,a_h))\right)\cdot\left(f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\right)/\widehat{\sigma}^2_h(s_h,a_h)\right]\\ =&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2/\widehat{\sigma}^2_h(\cdot,\cdot)\right]\\ +&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(s_h,a_h))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s_h,a_h))\right)\cdot\mathbb{E}\left(f\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}, \phi(s_h,a_h)\right)-r_h-\widehat{V}_{h+1}(s_{h+1})\middle |s_h,a_h\right)/\widehat{\sigma}^2_h(s_h,a_h)\right]\\ =&\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2/\widehat{\sigma}^2_h(\cdot,\cdot)\right] \end{align}\] where the third identity uses law of total expectation and that \(\mu\) is taken w.r.t. \(s_h,a_h,s_{h+1}\) only (recall Lemma 11) so the \(\widehat{\sigma}^2_h\) can be move outside of the conditional expectation.¹³ The fourth identity uses the definition of \(\theta_{\mathbb{T}\widehat{V}_{h+1}}\) since \(f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))=\mathcal{P}_{h,s,a}\widehat{V}_{h+1}\).

Then we have \[\begin{align} &\mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2/\widehat{\sigma}^2_h(\cdot,\cdot)\right]\\ \geq& \mathbb{E}_\mu\left[\left(f(\widehat{\theta}_{h},\phi(\cdot,\cdot))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(\cdot,\cdot))\right)^2\right]/H^2\geq \frac{\kappa}{H^2}\left\lVert\widehat{\theta}_{h}-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert^2_2, \end{align}\] where the third identity uses \(\mu\) is over \(s_h,a_h\) only and the last one uses \(\widehat{\sigma}^2_h(\cdot,\cdot)\leq H^2\). Combine the above with 25 and 26 , we obtain the stated result. ◻

Theorem 9 (Provable efficiency of VAFQL (Part II)). Let \(C_{d,\log K}\) be the same as Lemma 11. Furthermore, suppose \(\lambda\leq 1/2C_\Theta^2\) and \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\). Then, with probability \(1-\delta\), \(\forall h\in[H]\) \[\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f(\theta^\star_h,\phi(s,a))\right|\leq \left(\kappa_1H\sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2dH^3\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K}),\] Furthermore, we have with probability \(1-\delta\), \[\begin{align} \sup_{h}\left\lVert\widehat{V}_{h}-V^\star_{h}\right\rVert_\infty\leq &\left(\kappa_1H\sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2dH^3\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\\ =&\widetilde{O}\left(\kappa_1H^3\sqrt{\frac{d^2}{\kappa}}\sqrt{\frac{1}{K}}\right) \end{align}\] where \(\widetilde{O}\) absorbs Polylog terms and higher order terms. Lastly, it also holds for all \(h\in[H]\), w.p. \(1-\delta\) \[\begin{align} \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2\leq& \left(\kappa_1H\frac{\sqrt{72H^4(\log(H^2/\delta)+C_{d,\log K})+4\lambda C_\Theta^2}}{\kappa }+\frac{4H^3d\kappa_1}{{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\\ =&\widetilde{O}\left(\frac{\kappa_1H^3d}{\kappa}\sqrt{\frac{1}{K}}\right) \end{align}\]

Proof of Theorem 9. Step1: we show the first result.

We prove this by backward induction. When \(h=H+1\), by convention \(f(\widehat{\theta}_h,\phi(s,a))=f(\theta^\star_h,\phi(s,a))=0\) so the base case holds. Suppose for \(h+1\), with probability \(1-(H-h)\delta\), \(\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f(\theta^\star_h,\phi(s,a))\right|\leq C_{h+1}\sqrt{\frac{1}{K}}\), we next consider the case for \(t=h\).

On one hand, by Theorem 8, we have with probability \(1-\delta/2\), \[\begin{align} &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ \leq &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))\right|+\sup_{s,a}\left|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ =&\sup_{s,a}\left|\nabla f(\xi,\phi(s,a))^\top(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})\right|+\sup_{s,a}\left|f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\theta_{\mathbb{T}V^\star_{h+1}},\phi(s,a))\right|\\ \leq & \kappa_1\cdot\left\lVert\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}}\right\rVert_2+\sup_{s,a}\left|\mathcal{P}_{h,s,a}\widehat{V}_{h+1}-\mathcal{P}_{h,s,a}{V}^\star_{h+1}\right|\\ \leq&\kappa_1\sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\left\lVert\widehat{V}_{h+1}-V^\star_{h+1}\right\rVert_\infty, \end{align}\] Recall we have the form \(\widehat{V}_{h+1}(\cdot):=\min\{\max_a f(\widehat{\theta}_{h+1},\phi(\cdot,a))-\Gamma_{h}(\cdot,a),H\}\) and \(V^\star_{h+1}(\cdot)=\max_a f(\theta^\star_{h+1},\phi(\cdot,a))=\min\{\max_a f(\theta^\star_{h+1},\phi(\cdot,a)),H\}\), we obtain \[\label{eqn:VA95V95to95f} \begin{align} \left\lVert\widehat{V}_{h+1}-V^\star_{h+1}\right\rVert_\infty\leq \sup_{s,a}\left|f(\widehat{\theta}_{h+1},\phi(s,a))-f(\theta^\star_{h+1},\phi(s,a))\right|+\sup_{h,s,a}\Gamma_h(s,a) \end{align}\tag{27}\] Note the above holds true for any generic \(\Gamma_h(s,a)\). In particular, according to Algorithm 3, we specify \[\Gamma_{h}(\cdot, \cdot)= d\sqrt{\nabla_{\theta} f(\widehat{\theta}_h,\phi(\cdot,\cdot))^{\top} \Lambda_{h}^{-1} \nabla_{\theta} f(\widehat{\theta}_h,\phi(\cdot,\cdot))}\left(+\widetilde{O}(\frac{1}{K})\right)\] and by Lemma 19, with probability \(1-\delta\) (note here \(\Sigma^{-1}_h\) is replaced by \(\Lambda^{-1}_h\) and \(\left\lVert\Lambda^{-1}_h\right\rVert_2\leq H^2/\kappa\)), \[\Gamma_h\leq \frac{2dH^2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K})\]

and by a union bound this implies with probability \(1-(H-h+1)\delta\), \[\begin{align} &\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\\ \leq& C_{h+1}\sqrt{\frac{1}{K}}+\kappa_1\sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa K}}+\frac{2dH^2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K}):=C_h\sqrt{\frac{1}{K}}. \end{align}\] Solving for \(C_h\), we obtain \(C_h\leq \kappa_1H\sqrt{\frac{36H^4(\log(H/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+H\frac{2dH^2\kappa_1}{\sqrt{\kappa }}\) for all \(H\). By a union bound (replacing \(\delta\) by \(\delta/H\)), we obtain the stated result.

Step2: Utilizing the intermediate result 27 , we directly have with probability \(1-\delta\), \[\sup_{h}\left\lVert\widehat{V}_{h}-V^\star_{h}\right\rVert_\infty\leq \sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|+\frac{2dH^2\kappa_1}{\sqrt{\kappa K}}+O(\frac{1}{K}),\] where \(\sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|\) can be bounded using Step1.

Step3: Denote \(M:=\left(\kappa_1H\sqrt{\frac{36H^4(\log(H^2/\delta)+C_{d,\log K})+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^3d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\), then by Step1 we have with probability \(1-\delta\) (here \(\xi\) is some point between \(\widehat{\theta}_h\) and \(\theta^\star_h\)) for all \(h\in[H]\) \[\begin{align} &M^2\geq \sup_{s,a}\left|f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right|^2\\ &\geq \mathbb{E}_\mu[\left( f(\widehat{\theta}_h,\phi(s,a))-f({\theta}^\star_h,\phi(s,a))\right)^2]\geq \kappa \left\lVert\widehat{\theta}_h-\theta^\star_h\right\rVert_2^2 \end{align}\] where the last step is by Assumption 3. Solving this to obtain the stated result. ◻

15.2 Bounding \(|\widehat{\sigma}^2_h-\sigma^{\star 2}_h|\)↩︎

Recall the definition \(\sigma^{\star 2}_h(\cdot,\cdot)=\max\{1,[\mathrm{Var}_{P_h}V^\star_{h+1}](\cdot,\cdot)\}\). In this section, we bound the term \(|\widehat{\sigma}^2_h-\sigma^{\star 2}_h|:=\left\lVert\widehat{\sigma}^2_h(\cdot,\cdot)-\sigma^{\star 2}_h(\cdot,\cdot)\right\rVert_\infty\) and \[\label{eqn:parameter} \begin{align} \boldsymbol{u}_h = &\mathop{\mathrm{argmin}}_{\theta\in\Theta}\left\{\frac{1}{K} \sum_{k=1}^{K}\left[f\left(\theta, \bar{\phi}_{h,k}\right)-\widehat{V}_{h+1}(\bar{s}_{h+1}^k)\right]^{2}+\frac{\lambda}{K} \cdot\left\lVert\theta\right\rVert_2^2\right\}\\ \boldsymbol{v}_h = &\mathop{\mathrm{argmin}}_{\theta\in\Theta}\left\{\frac{1}{K} \sum_{k=1}^{K}\left[f\left(\theta, \bar{\phi}_{h,k}\right)-\widehat{V}^2_{h+1}(\bar{s}_{h+1}^k)\right]^{2}+\frac{\lambda}{K} \cdot\left\lVert\theta\right\rVert_2^2\right\} \end{align}\tag{28}\] where \[\widehat{\sigma}^2_h(\cdot,\cdot) := \max\{1,f(\boldsymbol{v}_h,\phi(\cdot,\cdot))_{\left[0,(H-h+1)^{2}\right]}-\big[f(\boldsymbol{u}_h,\phi(\cdot,\cdot))_{[0, H-h+1]}\big]^{2}\}\] and true parameters \(\boldsymbol{u}^\star_h,\boldsymbol{v}^\star_h\) satisfy \(f(\boldsymbol{u}^\star_h,\phi(\cdot,\cdot))=\mathbb{E}_{P(s'|\cdot,\cdot)}[V^\star_h(s')],f(\boldsymbol{v}^\star_h,\phi)=\mathbb{E}_{P(s'|\cdot,\cdot)}[V^{\star 2}_h(s')]\). Furthermore, we define \[\sigma^2_{\widehat{V}_{h+1}}(\cdot,\cdot):=\max\{1,[\mathrm{Var}_{P_h}\widehat{V}_{h+1}](\cdot,\cdot)\}\] and the parameter Expectation operator \(\mathbb{J}: V\in\mathbb{R}^{\mathcal{S}}\rightarrow \theta_{\mathbb{J}V}\in\Theta\) such that: \[f(\theta_{\mathbb{J}V},\phi)=\mathbb{E}_{P_h}[V(s')],\;\;\forall \left\lVert V\right\rVert_2\leq \mathcal{B}_{\mathcal{F}}.\] Note \(\theta_{\mathbb{J}V}\in\Theta\) by Bellman completeness, reward \(r\) is constant and differentiability (Definition 1) is an additive closed property. By definition, \[\begin{align} |\widehat{\sigma}^2_h-\sigma^2_{\widehat{V}_{h+1}}|\leq& |f(\boldsymbol{v}_h,\phi)-f(\theta_{\mathbb{J}\widehat{V}^2_{h+1}},\phi)|+|f(\boldsymbol{u}_h,\phi)^2-f(\theta_{\mathbb{J}\widehat{V}_{h+1}},\phi)^2|\\ \leq &|f(\boldsymbol{v}_h,\phi)-f(\theta_{\mathbb{J}\widehat{V}^2_{h+1}},\phi)|+2H\cdot |f(\boldsymbol{u}_h,\phi)-f(\theta_{\mathbb{J}\widehat{V}_{h+1}},\phi)| \end{align}\] and \[\begin{align} |{\sigma}^{\star 2}_h-\widehat{\sigma}^2_h|\leq& |f(\boldsymbol{v}^\star_h,\phi)-f(\boldsymbol{v}_h,\phi)|+|f(\boldsymbol{u}^\star_h,\phi)^2-f(\boldsymbol{v}_h,\phi)^2|\\ \leq &|f(\boldsymbol{v}^\star_h,\phi)-f(\boldsymbol{v}_h,\phi)|+2H\cdot |f(\boldsymbol{u}^\star_h,\phi)-f(\boldsymbol{v}_h,\phi)| \end{align}\]

We first give the following result.

Lemma 12. Suppose \(\lambda\leq 1/2C_\Theta^2\) and \(K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1^3\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\). Then, with probability \(1-\delta\), \(\forall h\in[H]\), \[\begin{align} \left\lVert\boldsymbol{u}_h-\theta_{\mathbb{J}\widehat{V}_{h+1}}\right\rVert_2\leq& \sqrt{\frac{36H^2(\log(H/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa K}},\;\forall h\in[H],\\ \left\lVert\boldsymbol{v}_h-\theta_{\mathbb{J}\widehat{V}^2_{h+1}}\right\rVert_2\leq& \sqrt{\frac{36H^4(\log(H/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa K}},\;\forall h\in[H]. \end{align}\] and \[\begin{align} \sup_{s,a}\left|f(\boldsymbol{u}_h,\phi(s,a))-f(\boldsymbol{u}^\star_h,\phi(s,a))\right|\leq \left(\kappa_1H\sqrt{\frac{36H^2(\log(H^2/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^2d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K}),\\ \sup_{s,a}\left|f(\boldsymbol{v}_h,\phi(s,a))-f(\boldsymbol{v}^\star_h,\phi(s,a))\right|\leq \left(\kappa_1H\sqrt{\frac{36H^4(\log(H^2/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa }}+\frac{2H^3d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K}). \end{align}\] The above directly implies for all \(h\in[H]\), with probability \(1-\delta\), \[\begin{align} |{\sigma}^{\star 2}_h-\widehat{\sigma}^2_h|\leq&\left(3\kappa_1H^2\sqrt{\frac{36H^4(\log(H^2/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa }}+\frac{6H^4d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K})\\ |\widehat{\sigma}^2_h-\sigma^2_{\widehat{V}_{h+1}}| \leq&3H\kappa_1\sqrt{\frac{36H^4(\log(H/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa K}}. \end{align}\]

Proof of Lemma 12. In fact, the proof follows a reduction from the provable efficiency procedure conducted in Section 12. This is due to the regression procedure in 28 is the same as the procedure 15 except the parameter Bellman operator \(\mathbb{T}\) is replaced by the parameter Expectation operator \(\mathbb{J}\) (recall here \(\bar{\phi}_{h,k}\) uses the independent copy \(\mathcal{D}'\) and \(\widetilde{O}(d^2)\) comes from the covering argument.). Concretely, the \(X(g,V,f_V)\) used in Lemma 10 will be modified to \(X(g,V,f_V)=(g(s,a)-V(s'))^2-(f(\theta_{\mathbb{J}V},\phi(s,a))-V(s'))^2\) by removing reward information and the decomposition \[\mathbb{E}\mu\left[(g(s_h,a_h)-V(s_{h+1}))^2-(f(\theta_{\mathbb{J}V},\phi(s_h,a_h))-V(s_{h+1}))^2\right]=\mathbb{E}_{\mu}\left[(g(s_h,a_h)-f(\theta_{\mathbb{J}V},\phi(s_h,a_h)))^2\right]\] holds true. Then with probability \(1-\delta\), \[\begin{align} |{\sigma}^{\star 2}_h-\widehat{\sigma}^2_h|\leq &|f(\boldsymbol{v}^\star_h,\phi)-f(\boldsymbol{v}_h,\phi)|+2H\cdot |f(\boldsymbol{u}^\star_h,\phi)-f(\boldsymbol{v}_h,\phi)|\\ \leq&\left(3\kappa_1H^2\sqrt{\frac{36H^4(\log(H^2/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa }}+\frac{6H^4d\kappa_1}{\sqrt{\kappa }}\right)\sqrt{\frac{1}{K}}+O(\frac{1}{K}). \end{align}\] and \[\begin{align} |\widehat{\sigma}^2_h-\sigma^2_{\widehat{V}_{h+1}}|\leq &|f(\boldsymbol{v}_h,\phi)-f(\theta_{\mathbb{J}\widehat{V}^2_{h+1}},\phi)|+2H\cdot |f(\boldsymbol{u}_h,\phi)-f(\theta_{\mathbb{J}\widehat{V}_{h+1}},\phi)|\\ \leq&\kappa_1\left\lVert\boldsymbol{v}_h-\theta_{\mathbb{J}\widehat{V}^2_{h+1}}\right\rVert_2+2H\kappa_1\left\lVert\boldsymbol{u}_h-\theta_{\mathbb{J}\widehat{V}_{h+1}}\right\rVert_2\\ \leq&3H\kappa_1\sqrt{\frac{36H^4(\log(H/\delta)+\widetilde{O}(d^2))+2\lambda C_\Theta^2}{\kappa K}}. \end{align}\] ◻

15.3 Proof of Theorem 4 ↩︎

In this section, we sketch the proof of Theorem 4 since the most components are identical to Theorem 3. We will focus on highlighting the difference for obtaining the tighter bound.

First of all, Recall in the first-order condition, we have \[\left.\nabla_{\theta}\left\{ \sum_{k=1}^{K}\frac{\left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-\widehat{V}_{h+1}\left(s^k_{h+1}\right)\right]^{2}}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}+\lambda \cdot\left\lVert\theta\right\rVert_2^2\right\}\right|_{\theta=\widehat{\theta}_h}=0,\;\;\forall h\in[H].\] Therefore, if we define the quantity \(Z_h(\cdot,\cdot)\in\mathbb{R}^d\) as \[Z_h(\theta|V,\sigma^2)=\sum_{k=1}^K \frac{\left[f\left(\theta, \phi_{h,k}\right)-r_{h,k}-{V}\left(s^k_{h+1}\right)\right]}{\sigma(s_h^k,a_h^k)}\frac{\nabla f(\theta,\phi_{h,k})}{\sigma(s_h^k,a_h^k)}+\lambda\cdot \theta,\;\;\forall \theta\in\Theta, \left\lVert V\right\rVert_2\leq H,\] then we have \[Z_h(\widehat{\theta}_h|\widehat{V}_{h+1},\widehat{\sigma}_h^2)=0.\]

According to the regression oracle (Line 8 of Algorithm 3), the estimated Bellman operator \(\widehat{\mathcal{P}}_h\) maps \(\widehat{V}_{h+1}\) to \(\widehat{\theta}_h\), i.e. \(\widehat{\mathcal{P}}_h\widehat{V}_{h+1}=f(\widehat{\theta}_h,\phi)\). Therefore (recall Definition 2) \[\label{eqn:VA95decomp95iota} \begin{align} &\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)=\mathcal{P}_h \widehat{V}_{h+1}(s,a)-f(\widehat{\theta}_{h},\phi(s,a))\\ =&f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\widehat{\theta}_{h},\phi(s,a))\\ =&\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)+\mathrm{Hot}_{h,1}, \end{align}\tag{29}\] where we apply the first-order Taylor expansion for the differentiable function \(f\) at point \(\widehat{\theta}_h\) and \(\mathrm{Hot}_{h,1}\) is a higher-order term. Indeed, the following Lemma 3 bounds the \(\mathrm{Hot}_{h,1}\) term with \(\widetilde{O}(\frac{1}{K})\).

Lemma 13. Recall the definition (from the above decomposition) \(\mathrm{Hot}_{h,1}:=f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi(s,a))-f(\widehat{\theta}_{h},\phi(s,a))-\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\), then with probability \(1-\delta\), \[\left|\mathrm{Hot}_{h,1}\right|\leq \widetilde{O}(\frac{1}{K}),\;\;\forall h\in[H].\]

Proof. The proof is identical to that of Lemma 3 but with the help of Lemma 8. ◻

Next, according to the expansion of \(Z_h(\theta|\widehat{V}_{h+1},\widehat{\sigma}^2_h)\), we have

\[\begin{align} \nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)=I_1+I_2+I_3+\mathrm{Hot}_2, \end{align}\] where \[\begin{align} \mathrm{Hot}_2:= &\nabla f(\widehat{\theta}_h,\phi(s,a))\Lambda^{-1}_h \left[\widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})+\lambda \theta_{\mathbb{T}\widehat{V}_{h+1}}\right]\\ \Delta_{\Lambda^s_h}=&\sum_{k=1}^K\frac{\left( f(\widehat{\theta}_h,\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s_{h+1}^k)\right)\cdot \nabla^2_{\theta\theta} f(\widehat{\theta}_h,\phi_{h,k})}{\widehat{\sigma}^2(s_h^k,a_h^k)}\\ \Lambda_h=&\sum_{k=1}^K\frac{\nabla_{\theta} f(\widehat{\theta}_h,\phi_{h,k})\nabla_{\theta}^\top f(\widehat{\theta}_{h,k},\phi_{h,k})}{\widehat{\sigma}^2(s_h^k,a_h^k)}+\lambda I_d\\ \widetilde{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})=&\Delta_{\Lambda^s_h}(\widehat{\theta}_h-\theta_{\mathbb{T}\widehat{V}_{h+1}})+{R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}}) \end{align}\] where \({R}_K(\theta_{\mathbb{T}\widehat{V}_{h+1}})\) is the second order residual that is bounded by \(\widetilde{O}(1/K)\) and \[\begin{align} I_1=&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Lambda_h^{-1}\sum_{k=1}^K \frac{\left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}\\ I_2=&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Lambda_h^{-1}\sum_{k=1}^K \frac{\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-\widehat{V}_{h+1}(s^k_{h+1})+{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}\\ I_3=&\nabla f(\widehat{\theta}_{h},\phi(s,a))\Lambda_h^{-1}\sum_{k=1}^K \frac{\left( f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-r_{h,k}-\widehat{V}_{h+1}(s^k_{h+1})\right)\cdot \left(\nabla^\top_\theta f(\theta_{\mathbb{T}\widehat{V}_{h+1}},\phi_{h,k})-\nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})\right)}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}\\ \end{align}\] Similar to the PFQL case, \(I_2,I_3,\mathrm{Hot}_2\) can be bounded to have order \(O(1/K)\) via provably efficiency theorems in Section 15.1 and in particular, the inclusion of \(\sigma^2_{u,v}\) will not cause additional order in \(d\).¹⁴ Now we prove the result for the dominate term \(I_1\).

Lemma 14. With probability \(1-\delta\), \[|I_1|\leq 4Hd\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Sigma_h^{-1}}\cdot C_{\delta,\log K}+\widetilde{O}(\frac{\kappa_1}{\sqrt{\kappa}K}),\] where \(C_{\delta,\log K}\) only contains Polylog terms.

Proof of Lemma 14. First of all, by Cauchy–Schwarz inequality, we have \[\label{eqn:VA95dominate} |I_1|\leq \left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Lambda_h^{-1}}\cdot \left\lVert\sum_{k=1}^K \frac{\left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}\right\rVert_{\Lambda_h^{-1}}.\tag{30}\] Recall that \(\sigma^2_{u,v}(\cdot,\cdot) := \max\{1,f(v,\phi(\cdot,\cdot))_{\left[0,(H-h+1)^{2}\right]}-\big[f(u,\phi(\cdot,\cdot))_{[0, H-h+1]}\big]^{2}\}.\)

Step1. Let the fixed \(\theta\in\Theta\) be arbitrary and fixed \(u,v\) such that \(\sigma^2_{u,v}(\cdot,\cdot)\geq \frac{1}{2}\sigma^2_{\boldsymbol{u}^\star_h,\boldsymbol{v}^\star_h}(\cdot,\cdot)=\frac{1}{2}\sigma^{\star 2}_h(\cdot,\cdot)\) and define \(x_k(\theta,u,v)=\nabla_\theta f({\theta},\phi_{h,k})/\sigma_{u,v}(s_h^k,a_h^k)\). Next, define \({G}_{u,v}(\theta)=\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top/\sigma^2_{u,v}(s_h^k,a_h^k)+\lambda I_d\), then \(\left\lVert x_k\right\rVert_2\leq\kappa_1\). Also denote \(\eta_k :=[f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})]/\sigma_{u,v}(s_h^k,a_h^k)\), then \(\mathbb{E}[\eta_k|s_h^k,a_h^k]=0\) and \[\begin{align} \mathrm{Var}[\eta_k|s_h^k,a_h^k]=&\frac{\mathrm{Var}[f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})|s_h^k,a_h^k]}{\sigma^2_{u,v}(s_h^k,a_h^k)}\\ \leq&\frac{2\mathrm{Var}[f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})|s_h^k,a_h^k]}{\sigma^{\star 2}_h(s_h^k,a_h^k)}\\ =&\frac{2[\mathrm{Var}_{P_h}V^\star_{h+1}](s_h^k,a_h^k)}{\sigma^{\star 2}_h(s_h^k,a_h^k)}\leq 2, \end{align}\] then by Self-normalized Bernstein’s inequality (Lemma 18), with probability \(1-\delta\), \[\left\|\sum_{k=1}^{K} {x}_{k}(\theta,u,v) \eta_{k}\right\|_{G(\theta,u,v)^{-1}} \leq 16 \sqrt{d \log \left(1+\frac{K \kappa_1^{2}}{\lambda d}\right) \cdot \log \left(\frac{4 K^{2}}{\delta}\right)}+4 \zeta\log \left(\frac{4 K^{2}}{\delta}\right)\leq \widetilde{O}(\sqrt{d})\] where \(|\eta_k|\leq \zeta\) with \(\zeta=2\max_{s,a,s'}\frac{|f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi(s,a))-r-{V}^\star_{h+1}(s')|}{\sigma^{\star}_h(s,a)}\) and the last inequality uses \(\sqrt{d}\geq \widetilde{O}(\zeta)\).

Step2. Define \(h(\theta,u,v):=\sum_{k=1}^{K} {x}_{k} (\theta,u,v)\eta_{k}(u,v)\) and \(H(\theta,u,v):=\left\|h(\theta,u,v)\right\|_{G_{u,v}(\theta)^{-1}}\), \[\begin{align} &\left\lVert h(\theta_1,u_1,v_1)-h(\theta_2,u_2,v_2)\right\rVert_2\leq K \max_k\left\lVert(x_k\cdot\eta_k )(\theta_1,u_1,v_1)-(x_k\cdot\eta_k) (\theta_2,u_2,v_2)\right\rVert_2\\ &\leq K \max_k\left\{H\left|\frac{\nabla f(\theta_1,\phi_{h,k})-\nabla f(\theta_2,\phi_{h,k})}{\sigma^2_{u_1,v_1}(s_h^k,a_h^k)}\right|+H\kappa_1\left|\frac{\sigma^2_{u_1,v_1}(s_h^k,a_h^k)-\sigma^2_{u_2,v_2}(s_h^k,a_h^k)}{\sigma^2_{u_1,v_1}(s_h^k,a_h^k)\sigma^2_{u_2,v_2}(s_h^k,a_h^k)}\right|\right\}\\ &\leq KH\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2+KH\kappa_1 \left\lVert\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right\rVert_2 \end{align}\] Furthermore, \[\begin{align} &\left\lVert G_h(\theta_1,u_1,v_1)^{-1}-G_h(\theta_2,u_2,v_2)^{-1}\right\rVert_2\leq \left\lVert G_h(\theta_1,u_1,v_1)^{-1}\right\rVert_2\left\lVert G_h(\theta_1,u_1,v_1)-G_h(\theta_2,u_2,v_2)\right\rVert_2\left\lVert G_h(\theta_2,u_2,v_2)^{-1}\right\rVert_2\\ \leq& \frac{1}{\lambda^2}K\sup_k\left\lVert\frac{\nabla f(\theta_1, \phi_{h,k})\cdot \nabla f(\theta_1, \phi_{h,k})^\top}{\sigma^2_{u_1,v_1}(s_h^k,a_h^k)}-\frac{\nabla f(\theta_2, \phi_{h,k})\cdot \nabla f(\theta_2, \phi_{h,k})^\top}{\sigma^2_{u_2,v_2}(s_h^k,a_h^k)}\right\rVert_2\\ \leq&\frac{1}{\lambda^2}\left( K\kappa_2\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2+K\kappa_1^2 \left\lVert\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right\rVert_2\right) \end{align}\] All the above imply \[\begin{align} &|H(\theta_1,u_1,v_1)-H(\theta_2,u_2,v_2)|\leq \sqrt{\left|h(\theta_1,u_1,v_1)^\top G_{u_1,v_1}(\theta_1)^{-1}h(\theta_1,u_1,v_1)-h(\theta_2,u_2,v_2)^\top G_{u_2,v_2}(\theta_2)^{-1}h(\theta_2,u_2,v_2)\right|}\\ \leq &\sqrt{\left\lVert h(\theta_1,u_1,v_1)-h(\theta_2,u_2,v_2)\right\rVert_2\cdot \frac{1}{\lambda}\cdot KH\kappa_1} +\sqrt{KH\kappa_1\cdot \left\lVert G_{u_1,v_1}(\theta_1)^{-1}-G_{u_2,v_2}(\theta_2)^{-1}\right\rVert_2\cdot KH\kappa_1}\\ +&\sqrt{ (KH\kappa_1\cdot\frac{1}{\lambda})\cdot \left\lVert h(\theta_1,u_1,v_1)-h(\theta_2,u_2,v_2)\right\rVert_2}\\ \leq&2\sqrt{KH\kappa_1(\left\lVert\theta_1-\theta_2\right\rVert_2+ \left\lVert\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right\rVert_2)\cdot \frac{1}{\lambda}\cdot KH\kappa_1}+\sqrt{K^2H^2\kappa^2_1\cdot \frac{K\kappa_1}{\lambda^2}\left( \kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2+\kappa_1 \left\lVert\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right\rVert_2\right)}\\ \leq & \left(\sqrt{4K^2H^2\kappa_1^2/\lambda}+\sqrt{K^3H^2\kappa_1^3\kappa_2/\lambda^2}\right)\sqrt{\left\lVert\theta_1-\theta_2\right\rVert_2}+\left(\sqrt{4K^2H^2\kappa_1^2/\lambda}+\sqrt{K^3H^2\kappa_1^4/\lambda^2}\right)\sqrt{\left\lVert\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right\rVert_2} \end{align}\] note \[\begin{align} |\sigma^2_{u_1,v_1}(s,a) -\sigma^2_{u_2,v_2}(s,a) |\leq &\left|f(v_1,\phi(s,a))-f(v_2,\phi(s,a))\right|+2H \left|f(u_1,\phi(s,a))-f(u_2,\phi(s,a))\right|\\ \leq&\kappa_1\left\lVert v_1-v_2\right\rVert_2+2H\kappa_1\left\lVert u_1-u_2\right\rVert_2, \end{align}\] Then a \(\epsilon\)-covering net of \(\{H(\theta,u,v)\}\) can be constructed by the union of covering net for \(\theta,u,v\) and by Lemma 22, the covering number \(\mathcal{N}_\epsilon\) satisfies (where \(\widetilde{O}\) absorbs Polylog terms) \[\begin{align} \log \mathcal{N}_\epsilon\leq &\widetilde{O}(d) \end{align}\]

Step3. First note by definition in Step2 \[\left\lVert\sum_{k=1}^K \frac{\left( f(\theta_{\mathbb{T}{V}^\star_{h+1}},\phi_{h,k})-r_{h,k}-{V}^\star_{h+1}(s^k_{h+1})\right)\cdot \nabla^\top_\theta f(\widehat{\theta}_h,\phi_{h,k})}{\widehat{\sigma}^2_h(s_h^k,a_h^k)}\right\rVert_{\Lambda_h^{-1}}=H(\widehat{\theta}_h,\boldsymbol{u}_h,\boldsymbol{v}_h)\] Now choosing \(\epsilon=O(1/K)\) in Step2 and union bound over the covering number in Step2, we obtain with probability \(1-\delta\) (recall \(\sqrt{d}\geq \widetilde{O}(\zeta)\)), \[\begin{align} H(\widehat{\theta}_h,\boldsymbol{u}_h,\boldsymbol{v}_h)\leq &16 \sqrt{d \log \left(1+\frac{K \kappa_1^{2}}{\lambda d}\right) \cdot [\log \left(\frac{4 K^{2}}{\delta}\right)+\widetilde{O}(d)]}+4 \zeta[\log \left(\frac{4 K^{2}}{\delta}\right)+\widetilde{O}(d)]+O(\frac{1}{K})\\ \leq&\widetilde{O}(d)+O(\frac{1}{K}) \end{align}\] where we absorb all the Polylog terms. Combing above with 30 , we obtain with probability \(1-\delta\), \[\begin{align} |I_1|\leq &\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Lambda_h^{-1}}\cdot H(\widehat{\theta}_h,\boldsymbol{u}_h,\boldsymbol{v}_h)\\ \leq &\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Lambda_h^{-1}}\cdot\left[\widetilde{O}(d)+O(\frac{1}{K})\right]\\ \leq&\widetilde{O}\left(d\left\lVert\nabla f(\widehat{\theta}_{h},\phi(s,a))\right\rVert_{\Lambda_h^{-1}}\right)+\widetilde{O}(\frac{\kappa_1}{\sqrt{\kappa}K}), \end{align}\] ◻

Combing dominate term \(I_1\) (via Lemma 14) and all other higher order terms we can obtain the first result together with Lemma 2.

The proof of the second result is also very similar to the proofs in Section 11.2. Concretely, when picking \(\pi=\pi^\star\), we can convert the quantity \[\sqrt{\nabla^\top_\theta f(\widehat{\theta}_h,\phi(s_h,a_h)){\Lambda}^{-1}_h\nabla_\theta f(\widehat{\theta}_h,\phi(s_h,a_h))}\] to \[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Lambda^{-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\] using Theorem 9, and convert \[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Lambda^{-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\] to \[\sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(s_h,a_h))\Lambda^{\star-1}_h\nabla_\theta f({\theta}^\star_h,\phi(s_h,a_h))}\] using Lemma 12.

16 The lower bound↩︎

Theorem 10 (Restatement of Theorem 5). Specifying the model to have linear representation \(f=\langle \theta,\phi\rangle\). There exist a pair of universal constants \(c, c' > 0\) such that given dimension \(d\), horizon \(H\) and sample size \(K > c' d^3\), one can always find a family of MDP instances such that for any algorithm \(\widehat{\pi}\) \[\begin{align} \label{eqn:lower} \inf_{\widehat{\pi}} \sup_{M \in \mathcal{M}} \mathbb{E}_M \big[v^{\star} - v^{\widehat{\pi}} \big] \geq c \, \sqrt{d} \cdot \sum_{h=1}^H \mathbb{E}_{\pi^{\star}} \bigg[ \sqrt{\nabla^\top_\theta f({\theta}^\star_h,\phi(\cdot,\cdot))(\Lambda_h^{\star, p})^{-1} \nabla_\theta f({\theta}^\star_h,\phi(\cdot,\cdot))} \bigg], \end{align}\qquad{(1)}\] where \(\Lambda_h^{\star,p} = \mathbb{E}\Big[ \sum_{k=1}^K \frac{\nabla_\theta f({\theta}^\star_h,\phi(s_h^k,a_h^k)) \cdot \nabla_\theta f({\theta}^\star_h,\phi(s_h^k,a_h^k))^\top}{\mathrm{Var}_h(V_{h+1}^{\star})(s_h^k, a_h^k)} \Big]\).

Remark 11. Note Theorem 5 is a valid lower bound for comparison. This is because the upper bound result holds true for all model \(f\) such that the corresponding \(\mathcal{F}\) satisfies Assumption 1, 3. Therefore, for the lower bound construction it suffices to find one model \(f\) such that the lower bound ?? holds. Here we simply choose the linear function approximation.

16.1 Regarding the proof of lower bound↩︎

The proof of Theorem 5 can be done via a reduction to linear function approximation lower bound. In fact, it can be directly obtained from Theorem 3.5 of [@yin2022linear], and the original proof comes from Theorem 2 of [@zanette2021provable].

Concretely, all the proofs in Theorem 3.5 of [@yin2022linear] follows and the only modification is to replace \[\sqrt{\mathbb{E}_{\pi^{\star}}[\phi]^{\top}\left(\Lambda_{h}^{\star}\right)^{-1} \mathbb{E}_{\pi^{\star}}[\phi]} \leq \frac{1}{2}\left\|\phi\left(+1, u_{h}\right)\right\|_{\left(\Lambda_{h}^{\star, p}\right)^{-1}}+\frac{1}{2}\left\|\phi\left(-1, u_{h}\right)\right\|_{\left(\Lambda_{h}^{\star, p}\right)^{-1}}\] in Section E.5 by \[\begin{align} \mathbb{E}_{\pi^{\star}} \Big[ \sqrt{ \phi(\cdot,\cdot)^{\top} (\Lambda_h^{\star,p})^{-1} \phi(\cdot, \cdot) } \Big] = \frac{1}{2} \big\| \phi(+1, u_h) \big\|_{(\Lambda_h^{\star,p})^{-1}} + \frac{1}{2} \big\| \phi(-1, u_h) \big\|_{(\Lambda_h^{\star,p})^{-1}}, \end{align}\] and the final result holds with \(\phi(\cdot,\cdot)=\nabla_\theta f(\theta^\star_h,\phi(\cdot,\cdot))\) by the reduction \(f=\langle \theta,\phi\rangle\).

17 Auxiliary lemmas↩︎

Lemma 15 (\(k\)-th Order Mean Value Form of Taylor’s Expansion). Let \(k\geq 1\) be an integer and let function \(f:\mathbb{R}^d\rightarrow \mathbb{R}\) be \(k\) times differentiable and continuous over the compact domain \(\Theta\subset \mathbb{R}^d\). Then for any \(x,\theta\in\Theta\), there exists \(\xi\) in the line segment of \(x\) and \(\theta\), such that \[\begin{align} f(x)-f(\theta)=&\nabla f(\theta)^\top (x-\theta)+\frac{1}{2!}(x-\theta)^\top\nabla^2_{\theta\theta} f(\theta)(x-\theta)+\ldots+\frac{1}{(k-1)!}\nabla^{k-1} f(\theta)\left(\bigotimes (x-\theta)\right)^{k-1}\\ +&\frac{1}{k!}\nabla^{k} f(\xi)\left(\bigotimes (x-\theta)\right)^{k}. \end{align}\] Here \(\nabla^{k} f(\theta)\) denotes \(k\)-dimensional tensor and \(\bigotimes\) denotes tensor product.

Lemma 16 (Vector Hoeffding’s Inequality). Let \(X = (X_1,\ldots,X_d)\) be \(d\)-dimensional vector Random Variable with \(E[X]=0\) and \(\left\lVert X\right\rVert_2\leq R\). \(X^{(1)},\ldots,X^{(n)}\)’s are \(n\) samples. Then with probability \(1-\delta\), \[\left\lVert\frac{1}{n}\sum_{i=1}^n X^{(i)}\right\rVert_2\leq \sqrt{\frac{4dR^2}{n}\log(\frac{d}{\delta})}.\]

Proof of Lemma 16. Since \(\left\lVert X\right\rVert_2\leq R\) implies \(|X_j|\leq R\), by the univariate Hoeffding’s inequality, for a fixed \(j\in\{1,...,d\}\), denote \(Y_j:=\frac{1}{n}\sum_{i=1}^n X^{(i)}_j\). Then with probability \(1-\delta\) (note \(|X^{(i)}_j|\leq R\)), \[\mathbb{P}\left(|Y_j|\geq 2\sqrt{\frac{R^2}{n}\log(\frac{1}{\delta})}\right)\leq \delta.\] By a union bound, \[\begin{align} \mathbb{P}\left(\exists \;i\;s.t.\;|Y_j|\geq 2\sqrt{\frac{R^2}{n}\log(\frac{1}{\delta})}\right)\leq d\delta&\Leftrightarrow \mathbb{P}\left(\forall \;i\;\;|Y_j|\leq 2\sqrt{\frac{R^2}{n}\log(\frac{1}{\delta})}\right)\geq 1-d\delta\\ \Leftrightarrow\mathbb{P}\left(\forall \;i\;\;Y_j^2\leq \frac{4R^2}{n}\log(\frac{1}{\delta})\right)\geq 1-d\delta&\Rightarrow \mathbb{P}\left(\left\lVert Y\right\rVert_2\leq \sqrt{\frac{4dR^2}{n}\log(\frac{1}{\delta})}\right)\geq 1-d\delta\\ \Leftrightarrow \mathbb{P}\left(\left\lVert Y\right\rVert_2\leq \sqrt{\frac{4dR^2}{n}\log(\frac{d}{\delta})}\right)\geq 1-\delta.& \end{align}\] ◻

Lemma 17 (Hoeffding inequality for self-normalized martingales [@abbasi2011improved]). Let \(\{\eta_t\}_{t=1}^\infty\) be a real-valued stochastic process. Let \(\{\mathcal{F}_t\}_{t=0}^\infty\) be a filtration, such that \(\eta_t\) is \(\mathcal{F}_t\)-measurable. Assume \(\eta_t\) also satisfies \(\eta_t\) given \(\mathcal{F}_{t-1}\) is zero-mean and \(R\)-subgaussian, i.e. \[\forall \lambda \in \mathbb{R}, \quad \mathbb{E}\left[e^{\lambda \eta_{t} }\mid \mathcal{F}_{t-1}\right] \leq e^{\lambda^{2} R^{2} / 2}\] Let \(\{x_t\}_{t=1}^\infty\) be an \(\mathbb{R}^d\)-valued stochastic process where \(x_t\) is \(\mathcal{F}_{t-1}\) measurable and \(\left\lVert x_t\right\rVert\leq L\). Let \(\Lambda_t=\lambda I_d+\sum_{s=1}^tx_sx^\top_s\). Then for any \(\delta>0\), with probability \(1-\delta\), for all \(t>0\), \[\left\|\sum_{s=1}^{t} {x}_{s} \eta_{s}\right\|_{{\Lambda}_{t}^{-1}}^2 \leq 8 R^{2}\cdot\frac{d}{2} \log \left(\frac{\lambda+tL}{\lambda\delta}\right).\]

Lemma 18 (Bernstein inequality for self-normalized martingales [@zhou2021nearly]). Let \(\{\eta_t\}_{t=1}^\infty\) be a real-valued stochastic process. Let \(\{\mathcal{F}_t\}_{t=0}^\infty\) be a filtration, such that \(\eta_t\) is \(\mathcal{F}_t\)-measurable. Assume \(\eta_t\) also satisfies \[\left|\eta_{t}\right| \leq R, \mathbb{E}\left[\eta_{t} \mid \mathcal{F}_{t-1}\right]=0, \mathbb{E}\left[\eta_{t}^{2} \mid \mathcal{F}_{t-1}\right] \leq \sigma^{2}.\]

Let \(\{x_t\}_{t=1}^\infty\) be an \(\mathbb{R}^d\)-valued stochastic process where \(x_t\) is \(\mathcal{F}_{t-1}\) measurable and \(\left\lVert x_t\right\rVert\leq L\). Let \(\Lambda_t=\lambda I_d+\sum_{s=1}^tx_sx^\top_s\). Then for any \(\delta>0\), with probability \(1-\delta\), for all \(t>0\), \[\left\|\sum_{s=1}^{t} \mathbf{x}_{s} \eta_{s}\right\|_{\boldsymbol{\Lambda}_{t}^{-1}} \leq 8 \sigma \sqrt{d \log \left(1+\frac{t L^{2}}{\lambda d}\right) \cdot \log \left(\frac{4 t^{2}}{\delta}\right)}+4 R \log \left(\frac{4 t^{2}}{\delta}\right)\]

Lemma 19. Let \(\nabla f(\theta,\phi(\cdot,\cdot)):\mathcal{S}\times\mathcal{A}\rightarrow \mathbb{R}^d\) be a bounded function s.t. \(\sup_{\theta\in\Theta}\left\lVert\nabla f(\theta,\phi(\cdot,\cdot))\right\rVert_2\leq \kappa_1\). If \(K\) satisfies \[K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1 B^2\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\] Then with probability at least \(1-\delta\), for all \(\left\lVert u\right\rVert_2\leq B\) simultaneously, it holds that \[\left\lVert u\right\rVert_{\Sigma_h^{-1}}\leq \frac{2B}{\sqrt{\kappa K}}+O(\frac{1}{K})\] where \(\Sigma_h=\sum_{k=1}^K \nabla f(\widehat{\theta}_h, \phi(s_h^k,a_h^k))\cdot \nabla f(\widehat{\theta}_h, \phi(s_h^k,a_h^k))^\top+\lambda I_d\).

Proof of Lemma 19. For a fixed \(\theta\), define \(\bar{G}=\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top+\lambda I_d\), and \(G=\mathbb{E}_\mu[\nabla f(\theta, \phi(s_h,a_h))\cdot \nabla f(\theta, \phi(s_h,a_h))^\top]\), then by Lemma H.5. of [@min2021variance], as long as \[\label{eqn:condition} K\geq \max\{512 \kappa_1^4 \left\lVert G^{-1}\right\rVert^2\log(\frac{2d}{\delta}), 4\lambda\left\lVert G^{-1}\right\rVert_2\},\tag{31}\] then with probability \(1-\delta\), for all \(u\in \mathbb{R}^d\) simultaneously, \(\left\lVert u\right\rVert_{\bar{G}^{-1}}\leq \frac{2}{\sqrt{K}}\left\lVert u\right\rVert_{{G}^{-1}}\). As a corollary, if we constraint \(u\) to the subspace \(\left\lVert u\right\rVert_2\leq B\), then we have: with probability \(1-\delta\), for all \(\{u\in \mathbb{R}^d:\left\lVert u\right\rVert_2\leq B\}\) simultaneously, \[\label{eqn:inter} \left\lVert u\right\rVert_{\bar{G}^{-1}}\leq \frac{2}{\sqrt{K}}\left\lVert u\right\rVert_{{G}^{-1}}=\frac{2}{\sqrt{K}}\sqrt{u^\top G^{-1}u}\leq \frac{2B\sqrt{\left\lVert G^{-1}\right\rVert_2}}{\sqrt{K}}.\tag{32}\]

Next, for any \(\theta\), define \[\begin{align} h_u(\theta):=&\left\lVert u\right\rVert_{\bar{G}^{-1}}=\sqrt{u^\top\bar{G}^{-1}u} =\sqrt{u^\top\left(\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top+\lambda I_d\right)^{-1}u} \end{align}\] and \(\bar{G}(\theta)=\sum_{k=1}^K \nabla f(\theta, \phi(s_h^k,a_h^k))\cdot \nabla f(\theta, \phi(s_h^k,a_h^k))^\top+\lambda I_d\), we have for any \(\theta_1\), \(\theta_2\) \[\begin{align} \left\lVert\bar{G}(\theta_1)-\bar{G}(\theta_2)\right\rVert_2\leq& \left\lVert\sum_{k=1}^K \left(\nabla f(\theta_1, \phi(s_h^k,a_h^k))-\nabla f(\theta_2, \phi(s_h^k,a_h^k))\right)\cdot \nabla f(\theta_1, \phi(s_h^k,a_h^k))^\top\right\rVert\\ +&\left\lVert\sum_{k=1}^K \nabla f(\theta_2, \phi(s_h^k,a_h^k))\left(\nabla f(\theta_1, \phi(s_h^k,a_h^k))-\nabla f(\theta_2, \phi(s_h^k,a_h^k))\right)^\top\right\rVert\\ \leq & K \kappa_2\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2+K \kappa_2\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2\leq 2K \kappa_2\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2. \end{align}\] Use the basic inequality for \(a,b>0\Rightarrow |\sqrt{a}-\sqrt{b}|\leq \sqrt{|a-b|}\), \[\begin{align} \sup_u|h_u(\theta_1)-h_u(\theta_2)|\leq &\sup_u\sqrt{\left|u^\top \left(\bar{G}(\theta_1)^{-1}-\bar{G}(\theta_2)^{-1}\right)u \right|}\leq \sqrt{B^2\cdot\left\lVert\bar{G}(\theta_1)^{-1}-\bar{G}(\theta_2)^{-1}\right\rVert_2}\\ \leq &\sqrt{B^2\cdot\left\lVert\bar{G}(\theta_1)^{-1}\right\rVert_2\left\lVert\bar{G}(\theta_1)-\bar{G}(\theta_2)\right\rVert_2\left\lVert\bar{G}(\theta_2)^{-1}\right\rVert_2}\\ \leq&\sqrt{B^2\frac{1}{\lambda}2K \kappa_2\kappa_1\left\lVert\theta_1-\theta_2\right\rVert_2\frac{1}{\lambda}}=\sqrt{\frac{2B^2K\kappa_1\kappa_2\left\lVert\theta_1-\theta_2\right\rVert_2}{\lambda^2}} \end{align}\] Therefore, the \(\epsilon\)-covering net of \(\{h(\theta):\theta\in\Theta\}\) is implies by the \(\frac{\lambda^2\epsilon^2}{2KB^2\kappa_1\kappa_2}\)-covering net of \(\{\theta:\theta\in\Theta\}\), so by Lemma 22, the covering number \(\mathcal{N}_\epsilon\) satisfies \[\log \mathcal{N}_\epsilon\leq d\log(1+\frac{4B^2K\kappa_1\kappa_2C_\Theta}{\lambda^2\epsilon^2}).\] Select \(\theta=\widehat{\theta}_h\). Choose \(\epsilon=O(1/K)\) and by a union bound over 32 to get with probability \(1-\delta\), for all \(\left\lVert u\right\rVert_2\leq B\) (note By Assumption 3 \(\left\lVert G^{-1}\right\rVert_2\leq 1/\kappa\)), \[\left\lVert u\right\rVert_{\Sigma_h^{-1}}\leq \frac{2B}{\sqrt{\kappa K}}+O(\frac{1}{K})\] if (union bound over the condition 31 ) \[K\geq\max\left\{512\frac{\kappa_1^4}{\kappa^2}\left(\log(\frac{2d}{\delta})+d\log(1+\frac{4\kappa_1 B^2\kappa_2C_\Theta K^3}{\lambda^2})\right),\frac{4\lambda}{\kappa}\right\}\] where this condition is satisfied by the Lemma statement. ◻

Lemma 20. let \(\phi: \mathcal{S}\times\mathcal{A}\rightarrow \mathbb{R}^d\) satisfies \(\left\lVert\phi(s,a)\right\rVert\leq C\) for all \(s,a\in\mathcal{S}\times\mathcal{A}\). For any \(K>0,\lambda>0\), define \(\bar{G}_K=\sum_{k=1}^K \phi(s_k,a_k)\phi(s_k,a_k)^\top+\lambda I_d\) where \((s_k,a_k)\)’s are i.i.d samples from some distribution \(\nu\). Then with probability \(1-\delta\), \[\left\lVert\frac{\bar{G}_K}{K}-\mathbb{E}_\nu\left[\frac{\bar{G}_K}{K}\right]\right\rVert\leq \frac{4 \sqrt{2} C^{2}}{\sqrt{K}}\left(\log \frac{2 d}{\delta}\right)^{1 / 2}.\]

Proof of Lemma 20. See Lemma H.5 of [@yin2022linear] or Lemma H.4 of Lemma [@min2021variance] for details. ◻

Lemma 21 (Lemma H.4 in [@yin2022linear]). Let \(\Lambda_1\) and \(\Lambda_2\in\mathbb{R}^{d\times d}\) are two positive semi-definite matrices. Then: \[\left\lVert\Lambda_1^{-1}\right\rVert\leq \left\lVert\Lambda_2^{-1}\right\rVert+\left\lVert\Lambda_1^{-1}\right\rVert\cdot \left\lVert\Lambda_2^{-1}\right\rVert\cdot\left\lVert\Lambda_1-\Lambda_2\right\rVert\] and \[\left\lVert\phi\right\rVert_{\Lambda_1^{-1}}\leq \left[1+\sqrt{\left\lVert\Lambda_2^{-1}\right\rVert\left\lVert\Lambda_2\right\rVert\cdot\left\lVert\Lambda_1^{-1}\right\rVert\cdot\left\lVert\Lambda_1-\Lambda_2\right\rVert}\right]\cdot \left\lVert\phi\right\rVert_{\Lambda_2^{-1}}.\] for all \(\phi\in\mathbb{R}^d\).

17.1 Covering Arguments↩︎

Lemma 22. (Covering Number of Euclidean Ball)For any \(\epsilon>0\), the \(\epsilon\)-covering number of the Euclidean ball in \(\mathbb{R}^d\) with radius \(R>0\) is upper bounded by \((1+2R/\epsilon)^d\).

Lemma 23. Define \(\mathcal{V}\) to be the class mapping \(\mathcal{S}\) to \(\mathbb{R}\) with the parametric form \[V(\cdot):=\min\{\max_a f(\theta,\phi(\cdot,a))-\sqrt{\nabla f(\theta,\phi(\cdot,a))^\top A\cdot\nabla f(\theta,\phi(\cdot,a))},H\}\] where the parameter spaces are \(\{\theta:\left\lVert\theta\right\rVert_2\leq C_\Theta\}\) and \(\{A:\left\lVert A\right\rVert_2\leq B\}\). Let \(\mathcal{N}^\mathcal{V}_\epsilon\) be the covering number of \(\epsilon\)-net with respect to \(l_\infty\) distance, then we have \[\log \mathcal{N}^\mathcal{V}_\epsilon\leq d\log\left(1+\frac{8C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{8\sqrt{d}B\kappa_1^2}{\epsilon^2}\right).\]

Proof of Lemma 23. \[\begin{align} &\sup_s|V_1(s)-V_2(s)|\\ \leq&\sup_{s,a}\left| f(\theta_1,\phi(s,a))-\sqrt{\nabla f(\theta_1,\phi(s,a))^\top A_1\cdot\nabla f(\theta_1,\phi(s,a))} -f(\theta_2,\phi(s,a))+\sqrt{\nabla f(\theta_2,\phi(s,a))^\top A_2\cdot\nabla f(\theta_2,\phi(s,a))}\right|\\ =&\sup_{s,a}\left| \nabla f(\xi,\phi(s,a))\cdot(\theta_1-\theta_2)-\sqrt{\nabla f(\theta_1,\phi(s,a))^\top A_1\cdot\nabla f(\theta_1,\phi(s,a))} +\sqrt{\nabla f(\theta_2,\phi(s,a))^\top A_2\cdot\nabla f(\theta_2,\phi(s,a))}\right|\\ \leq & \kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+\sup_{s,a}\left| \sqrt{\nabla f(\theta_1,\phi(s,a))^\top A_1\cdot\nabla f(\theta_1,\phi(s,a))} -\sqrt{\nabla f(\theta_2,\phi(s,a))^\top A_2\cdot\nabla f(\theta_2,\phi(s,a))}\right|\\ \leq & \kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+\sup_{s,a}\sqrt{\left|[\nabla f(\theta_1,\phi(s,a))-\nabla f(\theta_2,\phi(s,a))]^\top A_1\cdot\nabla f(\theta_1,\phi(s,a))\right|}\\ +&\sup_{s,a}\sqrt{\left|\nabla f(\theta_2,\phi(s,a))^\top (A_1-A_2)\cdot\nabla f(\theta_1,\phi(s,a))\right|}+\sup_{s,a}\sqrt{\left|\nabla f(\theta_2,\phi(s,a))^\top A_2\cdot[\nabla f(\theta_1,\phi(s,a))-\nabla f(\theta_2,\phi(s,a))]\right|}\\ \leq& \kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+ 2\sup_{s,a}\sqrt{\left\lVert\nabla f(\theta_1,\phi(s,a))-\nabla f(\theta_2,\phi(s,a))\right\rVert_2\cdot B\cdot \kappa_1} +\sqrt{\kappa_1^2 \left\lVert A_1-A_2\right\rVert_2}\\ \leq&\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+ 2\sup_{s,a}\sqrt{\left\lVert\nabla f(\theta_1,\phi(s,a))-\nabla f(\theta_2,\phi(s,a))\right\rVert_2\cdot B\cdot \kappa_1} +\sqrt{\kappa_1^2 \left\lVert A_1-A_2\right\rVert_2}\\ \leq&\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+2 \sup_{s,a}\sqrt{\left\lVert\nabla f(\theta_1,\phi(s,a))\right\rVert_2\cdot\left\lVert\theta_1-\theta_2\right\rVert_2\cdot B\cdot \kappa_1} +\sqrt{\kappa_1^2 \left\lVert A_1-A_2\right\rVert_2}\\ \leq&\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+ 2\sqrt{\kappa_2\cdot\left\lVert\theta_1-\theta_2\right\rVert_2\cdot B\cdot \kappa_1} +\sqrt{\kappa_1^2 \left\lVert A_1-A_2\right\rVert_2}\\ \leq&\left(\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2}\right)\sqrt{\left\lVert\theta_1-\theta_2\right\rVert_2}+\kappa_1\sqrt{\left\lVert A_1-A_2\right\rVert_2}\leq \left(\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2}\right)\sqrt{\left\lVert\theta_1-\theta_2\right\rVert_2}+\kappa_1\sqrt{\left\lVert A_1-A_2\right\rVert_F} \end{align}\] Here \(\left\lVert\cdot\right\rVert_F\) is Frobenius norm. Let \(\mathcal{C}_\theta\) be the \(\frac{\epsilon^2}{4(\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}\)-net of space \(\{\theta:\left\lVert\theta\right\rVert_2\leq C_\Theta\}\) and \(\mathcal{C}_w\) be the \(\frac{\epsilon^2}{4\kappa_1^2}\)-net of the space \(\{A:\left\lVert A\right\rVert_F\leq\sqrt{d}B\}\), then by Lemma 22, \[|\mathcal{C}_w|\leq \left(1+\frac{8C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)^d,\;\; |\mathcal{C}_A|\leq \left(1+\frac{8\sqrt{d}B\kappa_1^2}{\epsilon^2}\right)^{d^2}\] Therefore, the covering number of space \(\mathcal{V}\) satisfies \[\log \mathcal{N}^\mathcal{V}_\epsilon\leq \log(|\mathcal{C}_w|\cdot |\mathcal{C}_A|)\leq d\log\left(1+\frac{8C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{8\sqrt{d}B\kappa_1^2}{\epsilon^2}\right)\] ◻

Lemma 24 (Covering of \(\mathbb{E}_{\mu}(X(g,V,f))\)). Define \[X(\theta,\theta'):=(f(\theta,\phi(s,a))-r-V_{\theta'}(s'))^2-(f_{V_{\theta'}}(s,a)-r-V_{\theta'}(s'))^2,\] where \(f_V:=\mathcal{P}_hV+\delta_V\) and \(V(s)\) has form \(V_\theta(s)\) that belongs to \(\mathcal{V}\) (as defined in Lemma 23). Here \(X(\theta,\theta')\) is a function of \(s,a,r,s'\) as well, and we suppress the notation for conciseness only. Then the function class \(\mathcal{H}=\{h(\theta,\theta'):=\mathbb{E}_\mu[X(\theta,\theta')]|\left\lVert\theta\right\rVert_2\leq C_\Theta, V_\theta\in\mathcal{V}\}\) has the covering number of \((\epsilon+4H\epsilon_{\mathcal{F}})\)-net bounded by \[d\log(1+\frac{24C_\Theta (H+1)\kappa_1}{\epsilon})+ d\log\left(1+\frac{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288H^2\sqrt{d}B\kappa_1^2}{\epsilon^2}\right).\]

Proof of Lemma 24. First of all, \[\begin{align} X(\theta,\theta')=&f(\theta,\phi(s,a))^2-f_{V_{\theta'}}(s,a)^2 -2f(\theta,\phi(s,a))\cdot (r+V_{\theta'}(s'))+2f_{V_{\theta'}}(s,a)\cdot (r+V_{\theta'}(s')), \end{align}\] For any \((\theta_1,\theta'_1)\), \((\theta_2,\theta'_2)\), \[\begin{align} &|X(\theta_1,\theta'_1)-X(\theta_2,\theta'_2)|\leq |f(\theta_1,\phi(s,a))^2-f(\theta_2,\phi(s,a))^2|\\ +&|f_{V_{\theta'_1}}(s,a)^2-f_{V_{\theta'_2}}(s,a)^2|+2|f_{V_{\theta'_1}}(s,a)-f_{V_{\theta'_2}}(s,a)|\cdot (r+V_{\theta'_1}(s'))\\ +&2f_{V_{\theta'_2}}(s,a)\cdot |V_{\theta'_1}(s')-V_{\theta'_2}(s')|+2|f(\theta_1,\phi(s,a))-f(\theta_2,\phi(s,a))|\cdot (r+V_{\theta'_1}(s'))\\ +&2|f(\theta_2,\phi(s,a))|\cdot |V_{\theta'_1}(s')-V_{\theta'_2}(s')|\\ \leq&2H\cdot |f(\theta_1,\phi(s,a))-f(\theta_2,\phi(s,a))|+2H\cdot |f_{V_{\theta'_1}}(s,a)-f_{V_{\theta'_2}}(s,a)|\\ +&4H\cdot |V_{\theta'_1}(s')-V_{\theta'_2}(s')|+4(H+1)\cdot |f(\theta_1,\phi(s,a))-f(\theta_2,\phi(s,a))|\\ \leq& (6H+1)\cdot|f(\theta_1,\phi(s,a))-f(\theta_2,\phi(s,a))|+2H\max_{s'}|V_{\theta'_1}(s')-V_{\theta'_2}(s')|+4H\epsilon_{\mathcal{F}}\\ +&4H\cdot |V_{\theta'_1}(s')-V_{\theta'_2}(s')|\\ \leq &(6H+1)\left\lVert\nabla f(\xi,\phi(s,a))\right\rVert_2\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+6H\left\lVert V_{\theta'_1}-V_{\theta'_2}\right\rVert_\infty+4H\epsilon_{\mathcal{F}}\\ \leq & (6H+1)\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+6H\left\lVert V_{\theta'_1}-V_{\theta'_2}\right\rVert_\infty+4H\epsilon_{\mathcal{F}} \end{align}\] where the second inequality comes from \(f_V=\mathcal{P}_hV+\delta_V\). Note the above holds true for all \(s,a,r,s'\), therefore it implies \[\begin{align} |\mathbb{E}_\mu[X(\theta_1,\theta'_1)]-\mathbb{E}_\mu[X(\theta_2,\theta'_2)]|\leq &\sup_{s,a,s'}|X(\theta_1,\theta'_1)-X(\theta_2,\theta'_2)|\\ \leq&(6H+1)\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+6H\left\lVert V_{\theta'_1}-V_{\theta'_2}\right\rVert_\infty+4H\epsilon_{\mathcal{F}}\\ \end{align}\] Now let \(\mathcal{C}_1\) be the \(\frac{\epsilon}{12(H+1)\kappa_1}\)-net of \(\{\theta:\left\lVert\theta\right\rVert_2\leq C_\Theta\}\) and \(\mathcal{C}_2\) be the \(\epsilon/6H\)-net of \(\mathcal{V}\), applying Lemma 22 and Lemma 23 to obtain \[\log|\mathcal{C}_1|\leq d\log(1+\frac{24C_\Theta (H+1)\kappa_1}{\epsilon}),\quad \log|\mathcal{C}_2|\leq d\log\left(1+\frac{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288H^2\sqrt{d}B\kappa_1^2}{\epsilon^2}\right)\]which implies the covering number of \(\mathcal{H}\) to be bounded by \[\log|\mathcal{C}_1|\cdot|\mathcal{C}_2|\leq d\log(1+\frac{24C_\Theta (H+1)\kappa_1}{\epsilon})+ d\log\left(1+\frac{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288H^2\sqrt{d}B\kappa_1^2}{\epsilon^2}\right).\] ◻

Lemma 25. Denote \(\sigma^2_{u,v}(\cdot,\cdot) := \max\{1,f(v,\phi(\cdot,\cdot))_{\left[0,(H-h+1)^{2}\right]}-\big[f(u,\phi(\cdot,\cdot))_{[0, H-h+1]}\big]^{2}\}\) and define \[\bar{X}(\theta,\theta',u,v):=\frac{(f(\theta,\phi(s,a))-r-V_{\theta'}(s'))^2-(f_{V_{\theta'}}(s,a)-r-V_{\theta'}(s'))^2}{\sigma^2_{u,v}(s,a)},\] where \(f_V:=\mathcal{P}_hV\) and \(V(s)\) has form \(V_\theta(s)\) that belongs to \(\mathcal{V}\) (as defined in Lemma 23). Here \(\bar{X}(\theta,\theta',u,v)\) is a function of \(s,a,r,s'\) as well, and we suppress the notation for conciseness only. Then the function class \(\mathcal{H}=\{h(\theta,\theta',u,v):=\mathbb{E}_\mu[\bar{X}(\theta,\theta',u,v)]|\left\lVert\theta\right\rVert_2\leq C_\Theta, V_\theta\in\mathcal{V}\}\) has the covering number of \(\epsilon\)-net bounded by \[\begin{align} &d\log(1+\frac{24C_\Theta (H+1)\kappa_1}{\epsilon})+ d\log\left(1+\frac{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288H^2\sqrt{d}B\kappa_1^2}{\epsilon^2}\right)\\ &+d\log(1+\frac{16C_\Theta H^2\kappa_1}{\epsilon})+d\log(1+\frac{32C_\Theta H^3\kappa_1}{\epsilon}) \end{align}\]

Proof of Lemma 25. Recall \(\sigma^2_{u,v}(\cdot,\cdot) := \max\{1,f(v,\phi(\cdot,\cdot))_{\left[0,(H-h+1)^{2}\right]}-\big[f(u,\phi(\cdot,\cdot))_{[0, H-h+1]}\big]^{2}\},\) and since \(\max\), truncation are non-expansive operations, then we can achieve for any \(s,a\) \[\begin{align} |\sigma^2_{u_1,v_1}(s,a) -\sigma^2_{u_2,v_2}(s,a) |\leq &\left|f(v_1,\phi(s,a))-f(v_2,\phi(s,a))\right|+2H \left|f(u_1,\phi(s,a))-f(u_2,\phi(s,a))\right|\\ \leq&\kappa_1\left\lVert v_1-v_2\right\rVert_2+2H\kappa_1\left\lVert u_1-u_2\right\rVert_2, \end{align}\] Hence \[\begin{align} &\left|\bar{X}(\theta_1,\theta'_1,u_1,v_1)-\bar{X}(\theta_2,\theta'_2,u_2,v_2)\right|=\left|\frac{X(\theta_1,\theta'_1)}{\sigma^2_{u_1,v_1}}-\frac{X(\theta_2,\theta'_2)}{\sigma^2_{u_2,v_2}}\right|\\ &\leq \left|\frac{X(\theta_1,\theta'_1)-X(\theta_2,\theta'_2)}{\sigma^2_{u_1,v_1}}\right|+\left|\frac{X(\theta_2,\theta'_2)}{\sigma^2_{u_1,v_1}\sigma^2_{u_2,v_2}}\left(\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right)\right|\\ &\leq \left|X(\theta_1,\theta'_1)-X(\theta_2,\theta'_2)\right|+2H^2\left|\sigma^2_{u_1,v_1}-\sigma^2_{u_2,v_2}\right|\\ &\leq \left|X(\theta_1,\theta'_1)-X(\theta_2,\theta'_2)\right|+2H^2 \kappa_1\left\lVert v_1-v_2\right\rVert_2+4H^3\kappa_1\left\lVert u_1-u_2\right\rVert_2\\ &\leq (6H+1)\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+6H\left\lVert V_{\theta'_1}-V_{\theta'_2}\right\rVert_\infty+2H^2 \kappa_1\left\lVert v_1-v_2\right\rVert_2+4H^3\kappa_1\left\lVert u_1-u_2\right\rVert_2 \end{align}\] Note the above holds true for all \(s,a,r,s'\), therefore it implies \[\begin{align} &|\mathbb{E}_\mu[\bar{X}(\theta_1,\theta'_1,u_1,v_1)]-\mathbb{E}_\mu[\bar{X}(\theta_2,\theta'_2,u_2,v_2)]|\\ \leq& (6H+1)\kappa_1\cdot\left\lVert\theta_1-\theta_2\right\rVert_2+6H\left\lVert V_{\theta'_1}-V_{\theta'_2}\right\rVert_\infty+2H^2 \kappa_1\left\lVert v_1-v_2\right\rVert_2+4H^3\kappa_1\left\lVert u_1-u_2\right\rVert_2 \end{align}\] and similar to Lemma 24, the covering number of \(\epsilon\)-net will be bounded by \[\begin{align} &d\log(1+\frac{24C_\Theta (H+1)\kappa_1}{\epsilon})+ d\log\left(1+\frac{288H^2C_\Theta (\kappa_1\sqrt{C_\Theta}+2\sqrt{B\kappa_1\kappa_2})^2}{\epsilon^2}\right)+d^2\log\left(1+\frac{288H^2\sqrt{d}B\kappa_1^2}{\epsilon^2}\right)\\ &+d\log(1+\frac{16C_\Theta H^2\kappa_1}{\epsilon})+d\log(1+\frac{32C_\Theta H^3\kappa_1}{\epsilon}) \end{align}\] Comparing to Lemma 24, the last two terms are incurred by covering \(u,v\) arguments. ◻

Check [@arulkumaran2017deep] and the references therein for an overview.↩︎
Here \(\left\lVert\nabla^3_{\theta\theta\theta} f(\theta,\phi(s,a))\right\rVert_2\) is defined as the \(2\)-norm for 3-\(d\) tensor and in the finite horizon setting we simply instantiate \(\mathcal{B}_{\mathcal{F}}=H\).↩︎
Generally speaking, 2 and 3 are not directly comparable. However, for the specific function class \(f=\langle \theta,\phi\rangle\) with \(\phi=\mathbf{1}(s,a)\) and tabular MDPs, it is easy to check 3 is strong than 2.↩︎
We mention [@xie2021bellman] has a nice practical version PSPI, but the convergence is slower (the rate \(O(n^{-\frac{1}{3}})\)).↩︎
Here \(\Sigma^{\mathrm{linear}}_h:=\sum_{k=1}^K\phi_{h,k}\phi_{h,k}^\top+\lambda I_d\).↩︎
Here we assume model capacity is sufficient to make the presentation concise. If \(\epsilon_{\mathcal{F}}>0\), the complexity bound will include the term \(\epsilon_{\mathcal{F}}\). We include more discussion in Appendix 13.↩︎
Here \(n\) is the number of samples used in the infinite horizon discounted setting and is similar to \(K\) in the episodic setting.↩︎
i.e. expanding over \(Z^p_h(\theta):=\mathbb{E}_{s,a,s'}[(f\left(\theta, \phi(s,a)\right)-r-V^\pi_{h+1}(s'))\nabla f(\theta,\phi(s,a))]\), and the corresponding \(\Delta_{\Sigma^s_h}\) in \(\frac{\partial}{\partial \theta}Z_h(\theta)|_{\theta=\theta^\pi_h}\) is zero by Bellman equation.↩︎
We mention [@zhang2021improved] uses variance-aware confidence sets in a slightly different way.↩︎
Here without loss of generality we assume \(Q^\star_h\) can be uniquely identified, i.e.* there is a unique \(\theta^\star\) such that \(f(\theta^\star_h,\phi)=Q^\star_h\).*↩︎
We abuse the notation here to use either \(X(g,V,f_V)\) or \(X(\theta,V,f_V)\). They mean the same quantity.↩︎
Here in our realization of Lemma 23, we set \(B=1/\lambda\) (since \(\left\lVert\Sigma_h^{-1}\right\rVert_2\leq 1/\lambda\)).↩︎
Recall \(\widehat{\sigma}^2_h\) computed in Algorithm 3 uses an independent copy \(\mathcal{D}'\).↩︎
Note in Lemma 25, we only have additive terms that has the same order has Lemma 24.↩︎

Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient

Abstract

1 Introduction↩︎

1.2 Our contribution↩︎

2 Preliminaries↩︎

2.1 Assumptions↩︎

3 Differentiable Function Approximation is Provably Efficient↩︎

3.1 Sketch of the PFQL Analysis↩︎

4 Improved Learning via Variance Awareness↩︎

5 Conclusion, Limitation and Future Directions↩︎

Acknowledgments↩︎

6 Notation List↩︎

7 Further Illustration that Generalized Linear Model Example satisfies 3 ↩︎

8 On the computational complexity↩︎

9 Some basic constructions↩︎

9.1 Suboptimality decomposition↩︎

10 Analyzing \(|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)|\) for PFQL.↩︎

10.1 Analyzing \(\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\) via \(Z_h\).↩︎

10.2 Bounding the term \(I_3\)↩︎

10.3 Bounding the second term \(I_2\)↩︎

10.4 Bounding the main term \(I_1\)↩︎

10.5 Analyzing \(\mathrm{Hot}_2\) in 7 ↩︎

11 Proof of Theorem 3 ↩︎

11.1 The first part↩︎

11.2 The second part↩︎

12 Provable Efficiency by reduction to General Function Approximation↩︎

13 With positive Bellman completeness coefficient \(\epsilon_{\mathcal{F}}>0\)↩︎

14 VFQL and its analysis↩︎

14.1 Analysis for VFQL (Theorem 2)↩︎

15 Proofs for VAFQL↩︎

15.1 Provable Efficiency for Variance-Aware Fitted Q Learning↩︎

15.2 Bounding \(|\widehat{\sigma}^2_h-\sigma^{\star 2}_h|\)↩︎

15.3 Proof of Theorem 4 ↩︎

16 The lower bound↩︎

16.1 Regarding the proof of lower bound↩︎

17 Auxiliary lemmas↩︎

17.1 Covering Arguments↩︎

Subjects

Updated on Academus

Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient

Abstract

1 Introduction↩︎

1.1 Related works↩︎

1.2 Our contribution↩︎

2 Preliminaries↩︎

2.1 Assumptions↩︎

3 Differentiable Function Approximation is Provably Efficient↩︎

3.1 Sketch of the PFQL Analysis↩︎

4 Improved Learning via Variance Awareness↩︎

5 Conclusion, Limitation and Future Directions↩︎

Acknowledgments↩︎

6 Notation List↩︎

7 Further Illustration that Generalized Linear Model Example satisfies 3↩︎

8 On the computational complexity↩︎

9 Some basic constructions↩︎

9.1 Suboptimality decomposition↩︎

10 Analyzing \(|\mathcal{P}_h \widehat{V}_{h+1}(s,a)-\widehat{\mathcal{P}}_h\widehat{V}_{h+1}(s,a)|\) for PFQL.↩︎

10.1 Analyzing \(\nabla f(\widehat{\theta}_{h},\phi(s,a))\left(\theta_{\mathbb{T}\widehat{V}_{h+1}}-\widehat{\theta}_{h}\right)\) via \(Z_h\).↩︎

10.2 Bounding the term \(I_3\)↩︎

10.3 Bounding the second term \(I_2\)↩︎

10.4 Bounding the main term \(I_1\)↩︎

10.5 Analyzing \(\mathrm{Hot}_2\) in 7↩︎

11 Proof of Theorem 3↩︎

11.1 The first part↩︎

11.2 The second part↩︎

12 Provable Efficiency by reduction to General Function Approximation↩︎

13 With positive Bellman completeness coefficient \(\epsilon_{\mathcal{F}}>0\)↩︎

14 VFQL and its analysis↩︎

14.1 Analysis for VFQL (Theorem 2)↩︎

15 Proofs for VAFQL↩︎

15.1 Provable Efficiency for Variance-Aware Fitted Q Learning↩︎

15.2 Bounding \(|\widehat{\sigma}^2_h-\sigma^{\star 2}_h|\)↩︎

15.3 Proof of Theorem 4↩︎

16 The lower bound↩︎

16.1 Regarding the proof of lower bound↩︎

17 Auxiliary lemmas↩︎

17.1 Covering Arguments↩︎

Subjects

Updated on Academus

7 Further Illustration that Generalized Linear Model Example satisfies 3 ↩︎

10.5 Analyzing \(\mathrm{Hot}_2\) in 7 ↩︎

11 Proof of Theorem 3 ↩︎

15.3 Proof of Theorem 4 ↩︎