# Tractable and Provably Efficient Distributional Reinforcement Learning with
General Value Function Approximation

Taehyun Cho1, Seungyub Han1, Kyungjae Lee2, Seokhun Ju1, Dohyeong Kim1,
Jungwoo Lee1
1 Seoul National University, 2 Chung-Ang University
{talium, seungyubhan, qwerty7525<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Distributional reinforcement learning improves performance by effectively
capturing environmental stochasticity, but a comprehensive theoretical
understanding of its effectiveness remains elusive. In this paper, we present
a regret analysis for distributional reinforcement learning with general value
function approximation in a finite episodic Markov decision process setting.
We first introduce a key notion of Bellman unbiasedness for a tractable and
exactly learnable update via statistical functional dynamic programming. Our
theoretical results show that approximating the infinite-dimensional return
distribution with a finite number of moment functionals is the only method to
learn the statistical information unbiasedly, including nonlinear statistical
functionals. Second, we propose a provably efficient algorithm, SF-LSVI,
achieving a regret bound of $\tilde{O}(d_{E}H^{\frac{3}{2}}\sqrt{K})$ where
$H$ is the horizon, $K$ is the number of episodes, and $d_{E}$ is the eluder
dimension of a function class.

##  1 Introduction

Distributional reinforcement learning (DistRL) [7, 41, 13, 30] is an advanced
approach to reinforcement learning (RL) that focuses on the entire probability
distribution of returns rather than solely on the expected return. By
considering the full distribution of returns, distRL provides deeper insight
into the uncertainty of each action, such as the mode or median. This
framework enables us to make safer and more effective decisions that account
for various risks [14, 46, 22, 29], particularly in complex real-world
situations, such as robotic manipulation [10], neural response [36],
stratospheric balloon navigation [8], algorithm discovery [19], and several
game benchmarks [6, 34].

Although distRL has a solid theoretical basis and demonstrates effective
empirical performance, its efficiency and tractability are still not fully
understood. In practice, distributions contain an infinite amount of
information, and we should resort to approximations using a finite number of
parameters or statistical functionals, such as categorical [7] and quantile
representations [16]. However, not all statistical functionals can be learned
through the Bellman operator, as the meaning of statistical functionals is not
typically preserved after updates. For example, the median is not preserved
under the Bellman updates, as the median of a mixture of two distributions
does not necessarily equate to the mixture of their medians. Hence, a distinct
analysis is required to determine whether there exists a corresponding Bellman
operator for each statistical functional that ensures commutativity. Rowland
et al. [41] defined Bellman closedness as a property of statistical
functionals that can be exactly learned by the existence of a corresponding
Bellman operator.

At this point, we take a closer look at the distributional Bellman update and
revisit what additional properties of statistical functionals beyond Bellman
closedness are needed to construct tractable algorithms. In doing so, we
identify and provide the following challenges that arise when statistical
functionals are used to express the update process:

Figure 1: Venn-Diagram of Statistical Functional Classes. The diagram shows
the category of statistical functional. (Yellow) Within the linear statistical
functional class, Rowland et al. [41] demonstrated that the solution of
Bellman closedness is uniquely represented by polynomial exponential
functionals. (Red) We extend this concept by introducing Bellman unbiasedness,
which not only covers moment functionals but also central moment functionals
from the broader class including nonlinear statistical functionals. (A)
Maximum and minimum functionals are Bellman closed, while those are not
unbiasedly estimatable. (B) Median and quantile functionals are neither
Bellman closed and unbiased, highlighting that they are not proper to encode
the distribution.

  * •

Representing a mixture distribution with a finite, fixed number of parameters
inevitably leads to approximation errors during the update process. For
example, when expressing the mixture of two distributions, each represented by
$N$ parameters, compressing $2N$ into $N$ parameters in the mixture results in
inevitable information loss.

  * •

Due to the unknown nature of the transition probability
$\mathbb{P}(\cdot|s,a)$, the target distribution is estimated by sampling the
next state $s^{\prime}$. For a tractable algorithm, it is crucial that the
statistical functionals of the target distribution can be unbiasedly estimated
using the statistical functionals from the sampled distribution.

In this paper, we describe the statistical functional and sketch of the
distribution, and introduce the additional approximation errors that can occur
with the distRL method. We define the notion of Bellman unbiasedness, a
property for representing the distribution tractably and prove that the moment
functional is the only solution that satisfies this property, including
nonlinear statistical functionals. Based on this property, we propose a
provably efficient statistical functional reinforcement learning algorithm
with general value function approximation, denoted as SF-LSVI. We will discuss
the inherent issues of distributional Bellman completeness, a structural
assumption previously defined in the literature [49, 11], and investigate the
benefits of redesigning this concept using a sketch.

In summary, our main contributions are as follows:

  * •

Introduce a key property of Bellman unbiasedness for collections of
statistical functionals (sketch) and show that the moment functionals are the
unique structure that can be unbiasedly estimated and exactly learned from
distributions, including nonlinear statistical functionals.

  * •

Revisit the existing concept of distributional Bellman Completeness through a
statistical functional lens. We enhance the tractability by using moment
functional, that the agent can only access a finite-dimensional embedding
space. This removes the misspecification errors commonly encountered when
discretizing infinite-dimensional distributions.

  * •

Propose a tractable and provably efficient distributional RL algorithm called
SF-LSVI, achieving a tightest regret upper bound
$\tilde{O}(d_{E}H^{\frac{3}{2}}\sqrt{K})$ 111We ignore poly-log terms in
$H,S,A,K$ in the $\tilde{O}(\cdot)$ notation. in distributional framework. Our
framework yields a better regret bound with a weaker structural assumption
compared to prior results.

##  2 Related Work

#### Distributional RL.

In classical RL, the Bellman equation, which is based on expected returns, has
a closed-form expression. However, it is questionable whether any statistical
functionals of return distribution always have their corresponding closed-form
expressions. Rowland et al. [41] introduced the notion of Bellman Closedness
for collections of statistical functionals that can be updated in a closed
form via Bellman update. They showed that the only Bellman-closed statistical
functionals in the discounted setting are the moments
$\mathbb{E}_{Z\sim\eta}[Z^{k}]$. More recently, Marthe et al. [35] proposed a
general framework for distRL, where the agent plans to maximize their own
utility functionals instead of expected return and formalized the property of
Bellman Optimizability. They proved that the only $W_{1}$-continuous and
linear Bellman Optimizable statistical functionals are shown to be exponential
utilities $\frac{1}{\lambda}\log\mathbb{E}_{Z\sim\eta}[\exp(\lambda Z)]$ in
the undiscounted setting.

In practice, C51 [7] and QR-DQN [16] are notable distributional RL algorithms
where the convergence guarantees of sampled-based algorithms are proved [40,
42]. Dabney et al. [15] expanded the class of policies on arbitrary distortion
risk measures by taking the based distribution non-uniformly and improve the
sample efficiency from their implicit representation of the return
distribution. Cho et al. [12] highlighted the drawbacks of optimistic
exploration in distRL, introducing a randomized exploration method that
perturbs the return distribution when the agent selects their next action.

Table 1: Comparison for different methods under distributional RL framework.
$\mathcal{H}$ represents a subspace of infinite-dimensional space
$\mathcal{F}^{\infty}$. To bound the eluder dimesion $d_{E}$, Wang et al. [49]
and Chen et al. [11] assumed the discretized reward MDP.

Algorithm | Regret | Eluder dimension $d_{E}$ | Bellman Completeness | MDP assumption |  | Tractability of
---
Distribution Estimation
| O-DISCO
---
[49]
$\tilde{\mathcal{O}}(\text{poly}(d_{E}H)\sqrt{K})$ | $\text{dim}_{E}(\mathcal{H},\epsilon)$ | distributional BC |  | discretized reward,
---
small-loss bound
✗
| V-EST-LSR
---
[11]
$\tilde{\mathcal{O}}(d_{E}H^{2}\sqrt{K})$ 222In Chen et al. [11], the regret bound is written as $\tilde{O}(d_{E}L_{\infty}(\rho)H\sqrt{K})$, where $L_{\infty}(\rho)$ represents the lipschitz constant of the risk measure $\rho$, i.e., $|\rho(Z)-\rho(Z^{\prime})|\leq L_{\infty}(\rho)\|F_{Z}-F_{Z^{\prime}}\|_{\infty}$. Since $L_{\infty}(\rho)\geq H$ in risk-neutral setting, we translate the regret bound into $\tilde{O}(d_{E}H^{2}\sqrt{K})$. | $\text{dim}_{E}(\mathcal{H},\epsilon)$ | distributional BC |  | discretized reward,
---
lipschitz continuity
✗
[3pt]  SF-LSVI [Ours] | $\tilde{\mathcal{O}}(d_{E}H^{\frac{3}{2}}\sqrt{K})$ | $\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$ | statistical functional BC | none | ✓

#### RL with General Value Function Approximation.

Regret bounds have been studied for a long time in RL, across various domains
such as bandit [32, 1, 43], tabular RL [28, 3, 38, 39, 26], and linear
function approximation [27, 51, 52]. In recent years, deep RL has shown
significant performance using deep neural networks as function approximators,
and attempts have been made to analyze whether it is efficient in terms of
general function approximation. Wang et al. [50] established a provably
efficient RL algorithm with general value function approximation based on the
eluder dimension $d_{E}$ [43] and achieves a regret upper bound of
$\tilde{O}(\text{poly}(d_{E}H)\sqrt{K})$. To circumvent the intractability
from computing the upper confidence bound, Ishfaq et al. [25] injected the
stochasticity on the training data and get the optimistic value function
instead of upper confidence bound, enhancing computationally efficiency.
Beyond risk-neutral setting, several prior works have shown regret bounds
under risk-sensitive objectives (e.g., entropic risk [20, 33], CVaR [5]),
which align with our approach in that they are built on a distribution
framework. Liang and Luo [33] achieved the regret upper bound of
$\tilde{O}(\exp(H)\sqrt{|\mathcal{S}|^{2}|\mathcal{A}|H^{2}K})$ and the lower
bound of $\Omega(\exp(H)\sqrt{|\mathcal{S}||\mathcal{A}|HK})$ in tabular
setting.

#### DistRL with General Value Function Approximation.

Recently, only few efforts have aimed to bridge the gap between two fields.
Wang et al. [49] proposed a distributional RL algorithm, O-DISCO, which enjoys
small-loss bound by using a log-likelihood objective. Similarly, Chen et al.
[11] provided a risk-sensitive reinforcement learning framework with static
lipschitz risk measure. While these studies analyze within a distributional
framework, they do not address the intractability of implementation in
infinite-dimensional space of distributions. In contrast, our approach focuses
on a statistical functional framework, providing a detailed comparison with
other distRL methods as shown in Table 1.

##  3 Preliminaries

#### Episodic MDP.

We consider a episodic Markov decision process which is defined as a
$\mathcal{M}=(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$ characterized by state
space $\mathcal{S}$, action space $\mathcal{A}$, horizon length $H$,
transition kernels $\mathbb{P}=\\{\mathbb{P}_{h}\\}_{h\in[H]}$, and reward
$r=\\{r_{h}\\}_{h\in[H]}$ at step $h\in[H]$. The agent interacts with the
environment across $K$ episodes. For each $k\in[K]$ and $h\in[H]$,
$\mathbb{H}_{h}^{k}=(s_{1}^{1},a_{1}^{1},\dots,s_{H}^{1},a_{H}^{1},\dots,s_{h}^{k},a_{h}^{k})$
represents the history up to step $h$ at episode $k$. We assume the reward is
bounded by $[0,1]$ and the agent always transit to terminal state
$s_{\text{end}}$ at step $H+1$ with $r_{H+1}=0$.

#### Policy and Value Functions.

A (deterministic) policy $\pi$ is a collection of $H$ functions
$\\{\pi_{h}:\mathcal{S}\rightarrow\mathcal{A}\\}_{h=1}^{H}$. Given a policy
$\pi$, a step $h\in[H]$, and a state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, the $Q$ and $V$-function are defined
as
$Q_{h}^{\pi}(s,a)(:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R})\coloneqq\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\mid
s_{h}=s,a_{h}=a\right]$ and
$V_{h}^{\pi}(s)(:\mathcal{S}\rightarrow\mathbb{R})\coloneqq\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\mid
s_{h}=s\right].$

#### Random Variables and Distributions.

For a sample space $\Omega$, we extend the definition of the $Q$-function into
a random variable and its distribution,

$\displaystyle
Z_{h}^{\pi}(s,a)(:\mathcal{S}\times\mathcal{A}\times\Omega\rightarrow\mathbb{R})\coloneqq\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\mid
s_{h}=s,a_{h}=a,a_{h^{\prime}}=\pi_{h^{\prime}}(s_{h^{\prime}}),$
$\displaystyle\eta_{h}^{\pi}(s,a)(:\mathcal{S}\times\mathcal{A}\rightarrow\mathscr{P}(\mathbb{R}))\coloneqq\text{law}(Z_{h}^{\pi}(s,a)).$

Analogously, we extend the definition of $V$-function by introducing a bar
notation.

$\displaystyle\bar{Z}_{h}^{\pi}(s)(:\mathcal{S}\times\Omega\rightarrow\mathbb{R})\coloneqq\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\mid
s_{h}=s,a_{h^{\prime}}=\pi_{h^{\prime}}(s_{h^{\prime}}),$
$\displaystyle\bar{\eta}_{h}^{\pi}(s)(:\mathcal{S}\rightarrow\mathscr{P}(\mathbb{R}))\coloneqq\text{law}(\bar{Z}_{h}^{\pi}(s)).$

Note that $\bar{Z}^{\pi}_{h}(s)=Z^{\pi}_{h}(s,\pi(s))$ and
$\bar{\eta}_{h}^{\pi}(s)=\eta_{h}^{\pi}(s,\pi(s))$. We use $\pi^{\star}$ to
denote an optimal policy and denote
$V_{h}^{\star}(s)=V_{h}^{\pi^{\star}}(s),Q_{h}^{\star}(s,a)=Q_{h}^{\pi^{\star}}(s,a),\eta_{h}^{\star}(s,a)=\eta_{h}^{\pi^{\star}}(s,a)$,
and $\bar{\eta}_{h}^{\star}(s)=\bar{\eta}_{h}^{\pi^{\star}}(s)$. For
notational simplicity, we denote the expectation over transition,
$[\mathbb{P}_{h}V_{h+1}^{\pi}](s,a)=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a)}V_{h+1}^{\pi}(s^{\prime})$,
$[\mathbb{P}_{h}\bar{Z}_{h+1}^{\pi}](s,a)=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a)}\bar{Z}_{h+1}^{\pi}(s^{\prime})$,
and
$[\mathbb{P}_{h}\bar{\eta}_{h+1}^{\pi}](s,a)=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a)}\bar{\eta}_{h+1}^{\pi}(s^{\prime}).$
333Note that
$\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a)}\bar{\eta}^{\pi}_{h+1}(s^{\prime})$
is a mixture distribution. For brevity, we refer to $\bar{\eta}^{\pi}$ simply
as $\bar{\eta}$.

In the episodic MDP, the agent aims to learn the optimal policy through a
fixed number of interactions with the environment across a number of episodes.
At the beginning of each episode $k(\in[K])$, the agent starts at the initial
state $s_{1}^{k}$ and choose a policy $\pi^{k}$. In step $h(\in[H])$, the
agent observes $s^{k}_{h}(\in\mathcal{S})$, takes an action
$a^{k}_{h}(\in\mathcal{A})\sim\pi^{k}_{h}(\cdot|s^{k}_{h})$, receives a reward
$r_{h}(s^{k}_{h},a^{k}_{h})$, and the environment transits to the next state
$s^{k}_{h+1}\sim\mathbb{P}_{h}(\cdot|s^{k}_{h},a^{k}_{h}).$ Finally, we
measure the suboptimality of an agent by its regret, which is the accumulated
difference between the ground truth optimal and the return received from the
interaction. The regret after $K$ episodes is defined as
$\text{Reg}(K)=\sum_{k=1}^{K}V_{1}^{\star}(s_{1}^{k})-V_{1}^{\pi^{k}}(s_{1}^{k}).$

#### Distributional Bellman Optimality Equation.

Recall that $\eta^{\star}_{h}$ satisfies the distributional Bellman optimality
equation:

$\displaystyle\eta_{h}^{\star}(s,a)=(\mathcal{T}_{h}\eta_{h+1}^{\star})(s,a)$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a),a^{\prime}\sim\pi_{h}^{\star}(\cdot|s^{\prime})}[(\mathcal{B}_{r_{h}})_{\\#}\eta_{h+1}^{\star}(s^{\prime},a^{\prime})]$
$\displaystyle=(\mathcal{B}_{r_{h}})_{\\#}[\mathbb{P}_{h}\eta_{h+1}^{\star}](s,a)$

where $\mathcal{B}_{r}:\mathbb{R}\rightarrow\mathbb{R}$ is defined by
$\mathcal{B}_{r}(x)=r+x$, and $g_{\\#}\eta\in\mathscr{P}(\mathbb{R})$ is the
pushforward of the distribution $\eta$ through $g$, i.e.,
$g_{\\#}\eta(A)=\eta(g^{-1}(A))$ for any Borel set $A\subseteq\mathbb{R}$.

#### Additional Notations.

For a given $N$, we denote an $N-$dimensional function class
$\mathcal{F}^{N}\coloneqq\mathcal{F}^{(1)}\times\dots\times\mathcal{F}^{(N)}\subseteq\Big{\\{}f=[f^{(1)},\cdots,f^{(N)}]:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{N}\Big{\\}}.$
Given a dataset
$\mathcal{D}=\\{(s_{t},a_{t},[z_{t}^{(1)},\dots,z_{t}^{(N)}])\\}_{t=1}^{|\mathcal{D}|}\subseteq\mathcal{S}\times\mathcal{A}\times\mathbb{R}^{N}$,
a set of state-action pairs
$\mathcal{Z}=\\{(s_{t},a_{t})\\}_{t=1}^{|\mathcal{Z}|}\subseteq\mathcal{S}\times\mathcal{A}$
and for a function $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{N}$,
we define the norm
$\|f^{(n)}\|_{\infty},\|f\|_{\infty,1},\|f\|_{\mathcal{D}},\|f\|_{\mathcal{Z}}$
as written in Appendix A. For a set of (vector-valued) functions
$\mathcal{F}^{N}\subseteq\\{f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{N}\\}$,
the width function of $(s,a)$ is defined as
$w^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(n)}}(\mathcal{F}^{N},s,a)\coloneqq\max_{f,g\in\mathcal{F}^{N}}|f^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(n)}}(s,a)-g^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(n)}}(s,a)|$.

##  4 Statistical Functionals in Distributional RL

Figure 2:  Illustrative representation of sketch-based Bellman updates for a
mixture distribution. Instead of updating the distributions directly, each
sampled distribution is embedded through a sketch $\psi$ (e.g., mean $\mu$,
quantile $q_{i}$). The transformation $\phi_{\psi}$ aims to compress the
mixture distribution into the same number of parameters, ensuring unbiasedness
to prevent information loss.

###  4.1 Bellman Unbiasedness

We revisit the definitions of statistical functionals and illustrate the
property of Bellman closedness described in Bellemare et al. [9]. Then we
introduce another pivotal property, Bellman unbiasedness, required for
learning in terms of statistical functionals, rather than approximated
distribution.

######  Definition 4.1 (Statistical functionals, Sketch; [9]).

A statistical functional is a mapping from a probability distribution to a
real value $\psi:\mathscr{P}(\mathbb{R})\rightarrow\mathbb{R}$. A sketch is a
vector-valued function
${\psi}_{1:N}:\mathscr{P}(\mathbb{R})\rightarrow\mathbb{R}^{N}$ specified by
an $N$-tuple where each component is a statistical functional,

${\psi}_{1:N}(\cdot)=(\psi_{1}(\cdot),\cdots,\psi_{N}(\cdot)).$

We denote the domain of sketch as $\mathscr{P}_{\psi_{1:N}}(\mathbb{R})$ and
its image as
$I_{\psi_{1:N}}=\\{\psi(\bar{\eta}):\bar{\eta}\in\mathscr{P}_{\psi_{1:N}}(\mathbb{R})\\}.$
We further extend to state return distribution functions
$\psi_{1:N}(\bar{\eta})=\Big{(}\psi_{1:N}(\bar{\eta}(s)):s\in\mathcal{S}\Big{)}.$

######  Definition 4.2 (Bellman closedness; [41]).

A sketch ${\psi}_{1:N}$ is Bellman closed if there exists an operator
$\mathcal{T}_{\psi_{1:N}}:I_{\psi_{1:N}}^{\mathcal{S}}\rightarrow
I_{\psi_{1:N}}^{\mathcal{S}}$ such that

$\psi_{1:N}(\mathcal{T}\bar{\eta})=\mathcal{T}_{\psi_{1:N}}\psi_{1:N}(\bar{\eta})\quad\text{for
all }\bar{\eta}\in\mathscr{P}(\mathbb{R})^{\mathcal{S}}$

which is closed under the distributional Bellman operator
$\mathcal{T}:\mathscr{P}(\mathbb{R})^{\mathcal{S}}\rightarrow\mathscr{P}(\mathbb{R})^{\mathcal{S}}$.

Bellman closedness is the property that a sketch are exactly learnable when
updates are performed from the infinite-dimensional distribution space to the
finite-dimensional embedding space. Notably, Rowland et al. [41] showed that
the only finite linear statistical functionals that are Bellman closed are
given by the collections of statistical functionals where its linear span is
equal to the set of exponential-polynomial functionals where $\psi_{0}$ is the
constant functional equal to $1$.

######  Remark 4.3.

Rowland et al. [41] discussed only linear statistical functionals when
defining a sketch, leaving open questions about the Bellman closedness of
nonlinear statistical functionals such as variance, central moments, or
quantiles. However, it is noteworthy that nonlinear statistical functionals,
such as maximum or minimum, can also be Bellman closed. In their proof, there
might be an ambiguity regarding the assumption that the corresponding sketch
Bellman operator for quantile is linear. In this paper, we show the non-
existence of sketch Bellman operator for quantile and discuss in detail in
Appendix B.1.

######  Theorem 4.4.

Quantile functional cannot be Bellman closed under any additional sketch.

We investigate whether there exists another sketch that is both nonlinear and
Bellman closed, and introduce additional conditions under which the Bellman
closed property might be missing. During the implementation phase, it is
important to note that the agent does not have access to the transition
kernel. Specifically, the agent can only access the empirical transition
kernel $\hat{\mathbb{P}}$ which is derived from a finite number of sample
estimates. This limitation implies that the operator should be treated as an
empirical operator $\hat{\mathcal{T}}_{\psi}$, rather than
$\mathcal{T}_{\psi}$. Therefore, we introduce a new notion of Bellman
unbiasedness that allows us to unbiasedly estimate the expected distribution
$(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})]$,
which is a mixture by transitions, from the sample distribution
$(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime})$.

${\eta}$${\mathcal{T}\eta}$${\psi(\mathcal{T}\eta)}$${\psi(\eta)}$${\mathcal{T}_{\psi}\psi(\eta)}$

${\eta}$${\mathcal{T}\eta}$${\psi(\mathcal{T}\eta)}$${\psi(\eta)}$${\hat{\mathcal{T}}_{\psi}\psi(\eta)}$${{\mathbb{E}_{\mathbb{P}}[{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\phi_{\psi}\circ}\hat{\mathcal{T}}_{\psi}\psi(\eta)]}}$
Sample next state Unbiasedly estimate

Figure 3: (Left) Bellman Closedness. (Right) Bellman Unbiasedness. The above
path represents an ideal distributional Bellman update. Due to the infinite-
dimensionality, the update process should be represented by using a finite-
dimensional embedding (sketch) $\psi$. Since the transition kernel
$\mathbb{P}$ is unknown, the below path describes that the implementation
should sample the next state and update by using $\hat{\mathcal{T}}_{\psi}$
with the empirical transition kernel $\hat{\mathbb{P}}$. A sketch $\psi$ is
Bellman unbiased if $\hat{\mathcal{T}}_{\psi}\circ\psi$ can unbiasedly
estimate $\psi\circ\mathcal{T}$ through some transformation $\phi_{\psi}$.

######  Definition 4.5 (Bellman unbiasedness).

A sketch ${\psi}$ is Bellman unbiased if there exists an integer $k$ and a
corresponding vector-valued estimator
$\phi_{\psi}=\phi_{\psi}(\psi(x_{1}),\cdots,\psi(x_{k})):(I_{\psi}^{\mathcal{S}})^{k}\rightarrow
I_{\psi}^{\mathcal{S}}$ where the sketch of expected distribution
$(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})]$
can be unbiasedly estimated by $\phi_{\psi}$ using the $k$ samples from the
sketch of the sample distribution
$(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime})$, i.e.,

$\displaystyle\mathbb{E}_{s^{\prime}_{1},\cdots,s^{\prime}_{k}\sim\mathbb{P}(\cdot|s,a)}\Bigg{[}{\phi_{\psi}}\Bigg{(}\underbrace{\psi\Big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime}_{1})}_{\hat{\mathcal{T}}_{\psi}\psi(\eta)}\Big{)},\cdots,\psi\Big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}(s_{k}^{\prime})\Big{)}\Bigg{)}\Bigg{]}$
$\displaystyle=\psi\Big{(}(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})]\Big{)}.$

Bellman unbiasedness is another natural definition, similar to Bellman
closedness, which takes into account a finite number of samples for the
transition. As a simple example, median functional is not Bellman unbiased as
the sample median is not an unbiased estimate of the median functional. In
general, there is no unbiased estimator for the median, implying that the
median functional cannot be unbiasedly estimated within an embedding space
represented by a finite number of statistical functionals. On the other hand,
variance functional is a nonlinear statistical functional but can be
unbiasedly estimated. Then, the following question naturally arises;

“Which sketches are unbiasedly estimatable under the sketch-based Bellman
update?”

The following lemma answers this question.

######  Lemma 4.6.

Let $F_{\bar{\eta}}$ be a CDF of the probability distribution
$\bar{\eta}\in\mathscr{P}_{\psi}(\mathbb{R})^{\mathcal{S}}$. Then a sketch is
Bellman unbiased if and only if the sketch is homogeneous over
$\mathscr{P}_{\psi}(\mathbb{R})^{\mathcal{S}}$ of degree $k$, i.e., there
exists some vector-valued function
$h=h(x_{1},\cdots,x_{k}):\mathcal{X}^{k}\rightarrow\mathbb{R}^{N}$ such that

$\psi(\bar{\eta})=\int\cdots\int
h(x_{1},\cdots,x_{k})dF_{\bar{\eta}}(x_{1})\cdots dF_{\bar{\eta}}(x_{k}).$

Lemma 4.6 states that in statistical functional dynamic programming, the
unbiasedly estimatable embedding of a distribution can only be structured in
the form of functions that are homogeneous of finite degree. (e.g., variance
functional is a homogeneous of degree $2$ [23]). Taking this concept further
and combining it with the results on Bellman closedness, we prove that even
when including a nonlinear statistical functional, the only sketch that can be
unbiasedly estimated in a finite-dimensional embedding space is the moment
functional.

######  Theorem 4.7.

The only finite statistical functionals that are both Bellman unbiased and
closed are given by the collections of $\psi_{1},\dots,\psi_{N}$ where its
linear span $\\{\sum_{n=0}^{N}\alpha_{n}\psi_{n}|\ \alpha_{n}\in\mathbb{R}\
,\forall N\\}$ is equal to the set of exponential polynomial functionals
$\\{\eta\rightarrow\mathbb{E}_{Z\sim\eta}[Z^{l}\exp{(\lambda Z)}]|\
l=0,1,\dots,L,\lambda\in\mathbb{R}\\}$, where $\psi_{0}$ is the constant
functional equal to $1$. In discount setting, it is equal to the linear span
of the set of moment functionals
$\\{\eta\rightarrow\mathbb{E}_{Z\sim\eta}[Z^{l}]|\ l=0,1,\dots,L\\}$ for some
$L\leq N$.

Compared to Rowland et al. [41], our results extend beyond linear statistical
functionals to include unbiasedly estimatable nonlinear statistical
functionals, showing the uniqueness of the moment functional. Our theoretical
results not only show that high-order central moments such as variance or
skewness are exactly learnable, but also reveal that other nonlinear
statistical functionals like median or quantiles inevitably involve
approximation errors due to biased estimations. In Section 4.2, we emphasize
that unbiasedly estimable sketches play an important role in mitigating
misspecification errors, thereby enabling us to achieve sublinear regret.

###  4.2 Statistical Functional Bellman Completeness

We consider distributional reinforcement learning with value function
approximation. For successful TD learning, reinforcement learning with
function approximation commonly requires the assumption, Bellman Completeness,
that after applying Bellman operator, the output lies in the function class
$\mathcal{F}$ [50, 4, 25]. On the other hand, our approach receives a tuple of
function class
$\mathcal{F}^{N}\subseteq\\{f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{N}\\}$
as input to represent $N$-moment of distribution. Building on this, we assume
that for any $\bar{\eta}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$, the sketch
of target function that results from applying sketch Bellman operator lies in
the function class $\mathcal{F}^{N}$.

In the seminal works, Wang et al. [49] and Chen et al. [11] assumed that the
function class
$\mathcal{H}\subseteq\\{\eta:\mathcal{S}\times\mathcal{A}\rightarrow\mathscr{P}([0,H])\\}$
follows the distributional Bellman Completeness assumption, i.e., if
$\eta\in\mathcal{H}$ for all $\pi,h\in[H]$, then
$\mathcal{T}_{h}^{\pi}\eta\in\mathcal{H}$. However, since the distributional
Bellman operator mixes distributions for the next state transition, it implies
that a function class $\mathcal{H}$ must be closed under mixture. Due to this
closedness under mixture, both previous studies assumed a discretized reward
MDP, which requires the prior knowledge that outcomes of return distribution
are additively closed. In general, representing a distribution with a fixed
number of parameters inevitably increases the required number of parameters
due to the emergence of a mixture distribution. Consequently, trying to
represent it with a limited number of parameters leads to approximating the
learning outcome, thereby causing model misspecification which generally
introduces an additional linear regret. Precisely, a regret lower bound with
model misspecification error $\zeta$ is known as $\Omega(\zeta K)$ in a linear
bandit setting [52]. Therefore, assuming Bellman Completeness on the
distribution space is invalid as it significantly constrains the MDP structure
or causes linear regret.

To circumvent this issue, we revisit the assumption of distributional Bellman
completeness through the statistical functional lens. We propose a new
framework that matches a finite number of all statistical functionals to the
target function, rather than the entire distribution itself.

######  Assumption 4.8 (Statistical Functional Bellman Completeness).

For any distribution $\bar{\eta}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$ and
$h\in[H]$, there exists $f_{\bar{\eta}}\in\mathcal{F}^{N}$ which satisfies

$f_{\bar{\eta}}(s,a)=\psi_{1:N}\big{(}(\mathcal{B}_{r_{h}})_{\\#}[\mathbb{P}_{h}\bar{\eta}](s,a)\big{)}\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}$

######  Assumption 4.9 (Model Misspecification).

There exists a set of function $\mathcal{F}^{N}$ and a real number $\zeta>0$,
such that for any $\bar{\eta}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$ and
$h\in[H]$, there exists $f_{\bar{\eta}}\in\mathcal{F}^{N}$ which satisfies

$\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|f_{\bar{\eta}}(s,a)-\psi_{1:N}\big{(}(\mathcal{B}_{r_{h}})_{\\#}[\mathbb{P}_{h}\bar{\eta}](s,a)\big{)}\right\|\leq\zeta\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

We call $\zeta$ the misspecification error.

##  5 Algorithms

In this section, we propose SF-LSVI for distributional RL framework with
general value function approximation. Leveraging the result from Theorem 4.7,
we introduce a moment least square regression. This allows us to capture a
finite set of moment information from the distribution, which can be
unbiasedly estimated, thereby leading to the truncated moment problem. Unlike
previous work [49, 11] that estimates in infinite-dimensional distribution
spaces, our method enables tractable distribution estimation in finite-
dimensional embedding spaces without approximation error.

Algorithm 1 Statistical Functional Least Square Value Iteration
(${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\texttt{SF-
LSVI}}(\delta)$)

Input: failure probability $\delta\in(0,1)$ and the number of episodes $K$

1: for episode $k=1,2,\dots,K$ do

2: Receive initial state $s_{1}^{k}$

3: Initialize $\psi_{1:N}(\bar{\eta}_{H+1}^{k}(\cdot))\leftarrow\bm{0}^{N}$

4: for step $h=H,H-1,\dots,1$ do

5:
$\mathcal{D}_{h}^{k}\leftarrow\left\\{s_{h^{\prime}}^{\tau},a_{h^{\prime}}^{\tau},\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h^{\prime}}^{\tau}})_{\\#}\bar{\eta}_{h+1}^{k}(s_{h^{\prime}+1}^{\tau})\Big{)}\right\\}_{(\tau,h^{\prime})\in[k-1]\times[H]}$
// Data collection

6:
$\tilde{f}^{k}_{h,\bar{\eta}}\leftarrow\arg\min_{f\in\mathcal{F}^{N}}\|f\|_{\mathcal{D}_{h}^{k}}$
// Distribution Estimation

7: $b_{h}^{k}(\cdot,\cdot)\leftarrow
w^{(1)}((\mathcal{F}^{N})^{k}_{h},\cdot,\cdot)$

8:
$Q^{k}_{h}(\cdot,\cdot)\leftarrow\min\\{(\tilde{f}^{k}_{h,\bar{\eta}})^{(1)}(\cdot,\cdot)+b^{k}_{h}(\cdot,\cdot),H\\}$

9: $\pi^{k}_{h}(\cdot)=\arg\max_{a\in\mathcal{A}}Q^{k}_{h}(\cdot,a)$ ,
$V^{k}_{h}(\cdot)=Q^{k}_{h}(\cdot,\pi^{k}_{h}(\cdot))$ // Optimistic planning

10: $\psi_{1}\Big{(}\eta^{k}_{h}(\cdot,\cdot)\Big{)}\leftarrow
Q^{k}_{h}(\cdot,\cdot)$,
$\psi_{2:N}\Big{(}\eta^{k}_{h}(\cdot,\cdot)\Big{)}\leftarrow\Big{(}\min\\{(\tilde{f}^{k}_{h,\bar{\eta}})^{(n)}(\cdot,\cdot),H\\}\Big{)}_{n\in[2:N]}$

11: $\psi_{1}\Big{(}\bar{\eta}^{k}_{h}(\cdot,\cdot)\Big{)}\leftarrow
V^{k}_{h}(\cdot)$,
$\psi_{2:N}\Big{(}\bar{\eta}^{k}_{h}(\cdot)\Big{)}\leftarrow\psi_{1:N}\Big{(}\eta^{k}_{h}(\cdot,\pi^{k}_{h}(\cdot))\Big{)}_{n\in[2:N]}$

12: for $h=1,2,\dots,H$ do

13: Take action $a^{k}_{h}\leftarrow\pi^{k}_{h}(s^{k}_{h})$

14: Observe reward $r^{k}_{h}(s^{k}_{h},a^{k}_{h})$ and get next state
$s^{k}_{h+1}$.

#### Overview.

At the beginning of episode $k\in[K]$, we maintain all previous samples
$\\{(s^{\tau}_{h^{\prime}},a^{\tau}_{h^{\prime}},r^{\tau}_{h^{\prime}})\\}_{(\tau,h^{\prime})\in[k-1]\times[H]}$
and initialize a sketch $\psi_{1:N}(\bar{\eta}^{k}_{H+1}(\cdot))=\bm{0}^{N}$.
For each step $h=H,\dots,1$, we compute the normalized sample moments of
target distribution
$\\{(\mathcal{B}_{r_{h^{\prime}}^{\tau}})_{\\#}\bar{\eta}^{k}_{h+1}(s_{h^{\prime}+1}^{\tau})\\}_{h^{\prime}\in[H]}$
with the help of binomial theorem,

$\displaystyle\psi_{n}\Big{(}(\mathcal{B}_{r_{h^{\prime}}^{\tau}})_{\\#}\bar{\eta}_{h}(s_{h^{\prime}+1}^{\tau})\Big{)}$
$\displaystyle=\mathbb{E}[(\bar{Z}_{h+1}^{k}(s_{h^{\prime}+1}^{\tau})+r_{h^{\prime}}^{\tau})^{n}]{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}/H^{n-1}}$
$\displaystyle=\sum_{n^{\prime}=0}^{n}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H^{n^{\prime}}}\psi_{n^{\prime}}\Big{(}\bar{\eta}_{h}(s_{h^{\prime}+1}^{\tau})\Big{)}(r_{h^{\prime}}^{\tau})^{n-n^{\prime}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}/H^{n-1}}$

and iteratively solve the $N$-moment least square regression

$\displaystyle\tilde{f}^{k}_{h,\bar{\eta}}\leftarrow\arg\min_{f\in\mathcal{F}}\sum_{\tau=1}^{k-1}\sum_{h^{\prime}=1}^{H}\Big{(}\sum_{n=1}^{N}f^{(n)}(s_{h^{\prime}}^{\tau},a_{h^{\prime}}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h^{\prime}}^{\tau}})_{\\#}\bar{\eta}_{h+1}^{k}(s_{h^{\prime}+1}^{\tau})\Big{)}\Big{)}^{2}$

based on the dataset $\mathcal{D}^{k}_{h}$ which contains the sketch of
temporal target
$\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h^{\prime}}^{\tau}})_{\\#}\bar{\eta}_{h+1}^{k}(s_{h^{\prime}+1}^{\tau})\Big{)}$.
Then we define
$Q^{k}_{h}(\cdot,\cdot)=\min\\{(\tilde{f}^{k}_{h,\bar{\eta}})^{(1)}(\cdot,\cdot)+b^{k}_{h}(\cdot,\cdot),H\\}$
and choose the greedy policy $\pi^{k}_{h}(\cdot)$ with respect to $Q^{k}_{h}$.
We repeat the procedure until all the $K$ episodes are completed.

######  Remark 5.1.

For an optimistic planning, we define the bonus function as the width function
$b^{k}_{h}(s,a)\coloneqq w^{k}_{h}((\mathcal{F}^{N})^{k}_{h},s,a)$ where
$(\mathcal{F}^{N})^{k}_{h}$ denotes a confidence region at step $h$, episode
$k$. When $\mathcal{F}$ is a linear function class, the width function can be
evaluated by simply computing the maximal distance of weight vector. For a
general function class $\mathcal{F}$, computing the width function requires to
solve a set-constrained optimization problem, which is known as NP-hard [17].
However, a width function is computed simply for optimistic exploration, and
approximation errors are known to have a small effect on regret [1].

##  6 Theoretical Analysis

In this section, we provide the theoretical guarantees for SF-LSVI under
assumption 4.8. We apply proof techniques from Wang et al. [50] and extend the
result to a statistical functional lens. First, we generalize the concept of
eluder dimension [43] to the vector-valued function, which has been widely
used in RL literatures [4, 50, 27] to measure the complexity of learning with
the function approximators.

######  Definition 6.1 ($\epsilon$-dependent, $\epsilon$-independent, Eluder
dimension for vector-valued function).

Let $\epsilon\geq 0$ and
$\mathcal{Z}=\\{(s_{i},a_{i})\\}_{i=1}^{n}\subseteq\mathcal{S}\times\mathcal{A}$
be a sequence of state-action pairs.

  * •

A state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$ is
$\bm{\epsilon}$-dependent on $\mathcal{Z}$ with respect to $\mathcal{F}^{N}$
if $\|f-g\|_{\mathcal{Z}}\leq\epsilon$ for any vector-valued function
$f,g\in\mathcal{F}^{N}$, then
$|f^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1)}}(s,a)-g^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1)}}(s,a)|\leq\epsilon$.

  * •

An $(s,a)$ is $\bm{\epsilon}$-independent on $\mathcal{Z}$ with respect to
$\mathcal{F}^{N}$ if $(s,a)$ is not $\epsilon$-dependent on $\mathcal{Z}$.

  * •

The $\bm{\epsilon}$-eluder dimension
$\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$ of a vector-valued function class
$\mathcal{F}^{N}$ is the length of the longest sequence of elements in
$\mathcal{S}\times\mathcal{A}$ such that, for some
$\epsilon^{\prime}\geq\epsilon$, every element is
$\epsilon^{\prime}$-independent on its predecessors.

We assume that the function class $\mathcal{F}^{N}$ and state-action space
$\mathcal{S}\times\mathcal{A}$ have bounded covering numbers.

######  Assumption 6.2 (Covering number).

For any $\epsilon>0$, the following holds:

  * •

there exists an $\epsilon$-cover
$\mathcal{C}(\mathcal{F}^{N},\epsilon)\subseteq\mathcal{F}^{N}$ with size
$|\mathcal{C}(\mathcal{F}^{N},\epsilon)|\leq\mathcal{N}(\mathcal{F}^{N},\epsilon)$,
such that for any $g\in\mathcal{F}^{N}$, there exists
$g^{\prime}\in\mathcal{C}(\mathcal{F}^{N},\epsilon)$ with
$\|g-g^{\prime}\|_{\infty,1}\leq\epsilon$.

  * •

there exists an $\epsilon$-cover
$\mathcal{C}(\mathcal{S}\times\mathcal{A},\epsilon)$ with size
$|\mathcal{C}(\mathcal{S}\times\mathcal{A},\epsilon)|\leq\mathcal{N}(\mathcal{S}\times\mathcal{A},\epsilon)$,
such that for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, there exists
$(s^{\prime},a^{\prime})\in\mathcal{C}(\mathcal{S}\times\mathcal{A},\epsilon)$
with $\max_{f\in\mathcal{F}}|f(s,a)-f(s^{\prime},a^{\prime})|\leq\epsilon$

The following two lemmas give confidence bounds on the sum of the $l_{2}$
norms of all normalized moments.

######  Lemma 6.3 (Single Step Optimization Error).

Consider a fixed $k\in[K]$ and a fixed $h\in[H]$. Let
$\mathcal{Z}_{h}^{k}=\\{(s_{h}^{\tau},a_{h}^{\tau})\\}_{\tau\in[k-1]}$ and
$\mathcal{D}^{k}_{h,\bar{\eta}}=\Big{\\{}\Big{(}s_{h}^{\tau},a_{h}^{\tau},{\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h^{\prime}}}^{\tau})_{\\#}\bar{\eta}(s_{h^{\prime}+1}^{\tau})\Big{)}}\Big{)}\Big{\\}}_{\tau\in[k-1]}$
for any $\bar{\eta}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$. Define
$\tilde{f}_{h,\bar{\eta}}^{k}=\arg\min_{f\in\mathcal{F}^{N}}\|f\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}}}$.
For any $\bar{\eta}$ and $\delta\in(0,1)$, there is an event
$\mathcal{E}(\bar{\eta},\delta)$ such that conditioned on
$\mathcal{E}(\bar{\eta},\delta)$, with probability at least $1-\delta$, for
any $\bar{\eta}^{\prime}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$ with
$\|\psi_{1:N}(\bar{\eta}^{\prime})-\psi_{1:N}(\bar{\eta})\|_{\infty,1}\leq
1/T$ ,we have

$\displaystyle\left\|\tilde{f}_{h,\bar{\eta}^{\prime}}(\cdot,\cdot)-\psi_{1:N}\Big{(}(\mathcal{B}_{r(\cdot,\cdot)})_{\\#}[\mathbb{P}\bar{\eta}^{\prime}](\cdot,\cdot)\Big{)}\right\|_{\mathcal{Z}_{h}^{k}}$
$\displaystyle\leq{c^{\prime}\left(N^{\frac{1}{2}}H\sqrt{\log(1/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T)}\right)}$

for some constant $c^{\prime}>0$.

We remark that using moment functional as a sketch is a unique structure that
leads to a concentration results for the difference between the target and
sampled sketches
$\psi\Big{(}(\mathcal{B}_{r})_{\\#}[\mathbb{P}\bar{\eta}]\Big{)}-\psi\Big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}\Big{)}$,
as the tranformation $\phi_{\psi}$ of moment functional is an identity.
Furthermore, using normalized moments minimizes the size of the confidence
region from $O(H^{N})$ to $O(\sqrt{N})$. This adjustment is akin to scaling
the optimization function in multi-objective optimization to treat each
objective equally, which effectively prevents the model from favoring
objectives with larger scales.

######  Lemma 6.4 (Confidence Region).

Let
$(\mathcal{F}^{N})_{h}^{k}=\\{f\in\mathcal{F}^{N}|\|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)\\},$
where

$\beta(\mathcal{F}^{N},\delta)\geq c^{\prime}\cdot
NH^{2}(\log(T/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T))$

for some constant $c^{\prime}>0$. Then with probability at least $1-\delta/2$,
for all $k,h\in[K]\times[H]$, we have

$\psi_{n}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\in(\mathcal{F}^{N})_{h}^{k}$

Lemma 6.4 guarantees that the sequence of moments from the target distribution
$\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}$
lies in the confidence region $(\mathcal{F}^{N})^{k}_{h}$ with high
probability. Supported by the aforementioned lemma, we can further guarantee
that all $Q$-functions are optimistically estimated with high probability and
derive our final result.

######  Theorem 6.5.

Under Assumption 4.8, with probability at least $1-\delta$, SF-LSVI achieves a
regret bound of

$\text{Reg}(K)\leq
2H\text{dim}_{E}(\mathcal{F}^{N},1/T)+4H\sqrt{KH\log(1/\delta)}$

Under weaker structural assumptions, we show that SF-LSVI enjoys sublinear
regret of order $\tilde{O}(d_{E}H^{\frac{3}{2}}\sqrt{K})$, which is $\sqrt{H}$
better than the state-of-the-art distributional framework algorithm V-EST-LSR
[11]. For the linear MDP setting, we have $d_{E}=\tilde{O}(d)$ and thus the
regret bound of SF-LSVI is $\tilde{O}(\sqrt{d^{2}H^{3}K})$ which matches a
lower bound $\Omega(\sqrt{d^{2}H^{3}K})$ [53]. In our analysis, we highlight
two main technical novelties which significantly reduces the complexity of
regret;

  1. 1.

We refine previous lemma of Osband et al. [39] and Wang et al. [50] to remove
the dependency of $\beta(\mathcal{F}^{N},1/\delta)$ (See Appendix C.4),
ensuring that regret bound depends only on the defined function class, not on
the number of moment extracted.

  2. 2.

As shown in Table 1, we define the eluder dimension $d_{E}$ in a finite-
dimensional embedding space $\mathcal{F}^{N}$, while other methods rely on an
infinite-dimensional distribution space
$\mathcal{H}\subseteq\mathcal{F}^{\infty}$.

##  7 Conclusions

We describe the sources of approximation error inherent in distribution-based
updates and introduce a pivotal concept of Bellman unbiasedness, which enables
to exactly learn the information of distribution. We also present a provably
efficient distRL algorithm, SF-LSVI, with general value function
approximation. Notably, our algorithm achieves a near-optimal regret bound of
$\tilde{O}(d_{E}H^{\frac{3}{2}}\sqrt{K})$, matching the tightest upper bound
achieved by non-distributional framework [53, 24]. One interesting future
direction would be to reformulate the definition of regret as discrepencies in
moments rather than the expected return, and to show the sample-efficiency of
distRL. We hope that our work sheds some light on future research in analyzing
the provable efficiency of distRL.

## References

  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Akhiezer [2020] Naum Ilich Akhiezer.  _The classical moment problem and some related questions in analysis_.  SIAM, 2020.
  * Auer et al. [2008] Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Ayoub et al. [2020] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Bastani et al. [2022] Osbert Bastani, Jason Yecheng Ma, Estelle Shen, and Wanqiao Xu.  Regret bounds for risk-sensitive reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:36259–36269, 2022.
  * Bellemare et al. [2013] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Bellemare et al. [2017] Marc G Bellemare, Will Dabney, and Rémi Munos.  A distributional perspective on reinforcement learning.  In _International Conference on Machine Learning_ , pages 449–458. PMLR, 2017.
  * Bellemare et al. [2020] Marc G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Subhodeep Moitra, Sameera S Ponda, and Ziyu Wang.  Autonomous navigation of stratospheric balloons using reinforcement learning.  _Nature_ , 588(7836):77–82, 2020.
  * Bellemare et al. [2023] Marc G Bellemare, Will Dabney, and Mark Rowland.  _Distributional reinforcement learning_.  MIT Press, 2023.
  * Bodnar et al. [2019] Cristian Bodnar, Adrian Li, Karol Hausman, Peter Pastor, and Mrinal Kalakrishnan.  Quantile qt-opt for risk-aware vision-based robotic grasping.  _arXiv preprint arXiv:1910.02787_ , 2019.
  * Chen et al. [2024] Yu Chen, Xiangcheng Zhang, Siwei Wang, and Longbo Huang.  Provable risk-sensitive distributional reinforcement learning with general function approximation.  _arXiv preprint arXiv:2402.18159_ , 2024.
  * Cho et al. [2023] Taehyun Cho, Seungyub Han, Heesoo Lee, Kyungjae Lee, and Jungwoo Lee.  Pitfall of optimism: Distributional reinforcement learning by randomizing risk criterion.  _arXiv preprint arXiv:2310.16546_ , 2023.
  * Choi et al. [2019] Yunho Choi, Kyungjae Lee, and Songhwai Oh.  Distributional deep reinforcement learning with a mixture of gaussians.  In _2019 International conference on robotics and automation (ICRA)_ , pages 9791–9797. IEEE, 2019.
  * Chow et al. [2015] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone.  Risk-sensitive and robust decision-making: a cvar optimization approach.  _Advances in neural information processing systems_ , 28, 2015.
  * Dabney et al. [2018a] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos.  Implicit quantile networks for distributional reinforcement learning.  In _International conference on machine learning_ , pages 1096–1105. PMLR, 2018a.
  * Dabney et al. [2018b] Will Dabney, Mark Rowland, Marc Bellemare, and Rémi Munos.  Distributional reinforcement learning with quantile regression.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2018b.
  * Dann et al. [2018] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  On oracle-efficient pac rl with rich observations.  _Advances in neural information processing systems_ , 31, 2018.
  * Engert [1970] Martin Engert.  Finite dimensional translation invariant subspaces.  _Pacific Journal of Mathematics_ , 32(2):333–343, 1970.
  * Fawzi et al. [2022] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al.  Discovering faster matrix multiplication algorithms with reinforcement learning.  _Nature_ , 610(7930):47–53, 2022.
  * Fei et al. [2021] Yingjie Fei, Zhuoran Yang, and Zhaoran Wang.  Risk-sensitive reinforcement learning with function approximation: A debiasing approach.  In _International Conference on Machine Learning_ , pages 3198–3207. PMLR, 2021.
  * Feng et al. [2021] Fei Feng, Wotao Yin, Alekh Agarwal, and Lin Yang.  Provably correct optimization and exploration with non-linear policies.  In _International Conference on Machine Learning_ , pages 3263–3273. PMLR, 2021.
  * Greenberg et al. [2022] Ido Greenberg, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor.  Efficient risk-averse reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:32639–32652, 2022.
  * Halmos [1946] Paul R Halmos.  The theory of unbiased estimation.  _The Annals of Mathematical Statistics_ , 17(1):34–43, 1946.
  * He et al. [2023] Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu.  Nearly minimax optimal reinforcement learning for linear markov decision processes.  In _International Conference on Machine Learning_ , pages 12790–12822. PMLR, 2023.
  * Ishfaq et al. [2021] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang.  Randomized exploration in reinforcement learning with general value function approximation.  In _International Conference on Machine Learning_ , pages 4607–4616. PMLR, 2021.
  * Jin et al. [2018] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  _Advances in neural information processing systems_ , 31, 2018.
  * Jin et al. [2020] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020\.
  * Kakade [2003] Sham Machandranath Kakade.  _On the sample complexity of reinforcement learning_.  University of London, University College London (United Kingdom), 2003\.
  * Kim et al. [2023] Dohyeong Kim, Kyungjae Lee, and Songhwai Oh.  Trust region-based safe distributional reinforcement learning for multiple constraints.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Kim et al. [2024] Dohyeong Kim, Kyungjae Lee, and Songhwai Oh.  Trust region-based safe distributional reinforcement learning for multiple constraints.  _Advances in neural information processing systems_ , 36, 2024.
  * Kreuin et al. [1977] Mark Grigorevich Kreuin, AA Nudel, and D Louvish.  _The Markov moment problem and extremal problems_.  American Mathematical Society, 1977.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Liang and Luo [2022] Hao Liang and Zhi-Quan Luo.  Bridging distributional and risk-sensitive reinforcement learning with provable regret bounds.  _arXiv preprint arXiv:2210.14051_ , 2022.
  * Machado et al. [2018] Marlos C Machado, Marc G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling.  Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents.  _Journal of Artificial Intelligence Research_ , 61:523–562, 2018.
  * Marthe et al. [2023] Alexandre Marthe, Aurélien Garivier, and Claire Vernade.  Beyond average return in markov decision processes.  _arXiv preprint arXiv:2310.20266_ , 2023.
  * Muller et al. [2024] Timothy H Muller, James L Butler, Sebastijan Veselic, Bruno Miranda, Joni D Wallis, Peter Dayan, Timothy EJ Behrens, Zeb Kurth-Nelson, and Steven W Kennerley.  Distributional reinforcement learning in prefrontal cortex.  _Nature Neuroscience_ , pages 1–6, 2024.
  * Nguyen-Tang et al. [2021] Thanh Nguyen-Tang, Sunil Gupta, and Svetha Venkatesh.  Distributional reinforcement learning via moment matching.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 9144–9152, 2021.
  * Osband and Van Roy [2016] Ian Osband and Benjamin Van Roy.  On lower bounds for regret in reinforcement learning.  _arXiv preprint arXiv:1608.02732_ , 2016.
  * Osband et al. [2019] Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et al.  Deep exploration via randomized value functions.  _J. Mach. Learn. Res._ , 20(124):1–62, 2019.
  * Rowland et al. [2018] Mark Rowland, Marc Bellemare, Will Dabney, Rémi Munos, and Yee Whye Teh.  An analysis of categorical distributional reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 29–37. PMLR, 2018.
  * Rowland et al. [2019] Mark Rowland, Robert Dadashi, Saurabh Kumar, Rémi Munos, Marc G Bellemare, and Will Dabney.  Statistics and samples in distributional reinforcement learning.  In _International Conference on Machine Learning_ , pages 5528–5536. PMLR, 2019.
  * Rowland et al. [2023] Mark Rowland, Rémi Munos, Mohammad Gheshlaghi Azar, Yunhao Tang, Georg Ostrovski, Anna Harutyunyan, Karl Tuyls, Marc G Bellemare, and Will Dabney.  An analysis of quantile temporal-difference learning.  _arXiv preprint arXiv:2301.04462_ , 2023.
  * Russo and Van Roy [2013] Daniel Russo and Benjamin Van Roy.  Eluder dimension and the sample complexity of optimistic exploration.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Schmüdgen and di Dio [2017] K Schmüdgen and PJ di Dio.  “truncated moment problem: set of atoms and carathéodory numbers.  _Oberwolfach Rep._ , 14:77–79, 2017.
  * Sobel [1982] Matthew J Sobel.  The variance of discounted markov decision processes.  _Journal of Applied Probability_ , 19(4):794–802, 1982.
  * Son et al. [2021] Kyunghwan Son, Junsu Kim, Yung Yi, and Jinwoo Shin.  Disentangling sources of risk for distributional multi-agent reinforcement learning.  2021\.
  * Tamar et al. [2016] Aviv Tamar, Dotan Di Castro, and Shie Mannor.  Learning the variance of the reward-to-go.  _Journal of Machine Learning Research_ , 17(13):1–36, 2016.
  * Teicher [1960] Henry Teicher.  On the mixture of distributions.  _The Annals of Mathematical Statistics_ , 31(1):55–73, 1960.
  * Wang et al. [2023] Kaiwen Wang, Kevin Zhou, Runzhe Wu, Nathan Kallus, and Wen Sun.  The benefits of being distributional: Small-loss bounds for reinforcement learning.  _arXiv preprint arXiv:2305.15703_ , 2023.
  * Wang et al. [2020] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang.  Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.  _Advances in Neural Information Processing Systems_ , 33:6123–6135, 2020.
  * Wang et al. [2019] Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy.  Optimism in reinforcement learning with generalized linear function approximation.  _arXiv preprint arXiv:1912.04136_ , 2019.
  * Zanette et al. [2020] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pages 10978–10989. PMLR, 2020.
  * Zhou et al. [2021] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Conference on Learning Theory_ , pages 4532–4576. PMLR, 2021\.

## Appendix

##  Appendix A Notation

Table 2: Table of notation

Notation | Description
---|---
$\mathcal{S}$ | state space of size $S$
$\mathcal{A}$ | action space of size $A$
$H$ | horizon length of one episode
$T$ | number of episodes
$r_{h}(s,a)$ | reward of $(s,a)$ at step $h$
$\mathbb{P}_{h}(s^{\prime}|s,a)$ | probability transition of $(s,a)$ to $s^{\prime}$ at step $h$
$\mathbb{H}^{k}_{h}$ | history up to step $h$, episode $k$
$N$ | number of statistical functionals
$Q^{\pi}_{h}(s,a)$ | Q-function of a given policy $\pi$ at step $h$
$V^{\pi}_{h}(s)$ | V-function of a given policy $\pi$ at step $h$
$Z^{\pi}_{h}(s,a)$ | random variable of $Q$-function
$\bar{Z}^{\pi}_{h}(s)$ | random variable of $V$-function
$\eta^{\pi}_{h}(s,a)$ | probability distribution of $Q$-function
$\bar{\eta}^{\pi}_{h}(s)$ | probability distribution of $V$-function
$[\mathbb{P}_{h}(\cdot)]$ | expectation over transition $[\mathbb{P}_{h}(\cdot)]=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}}(\cdot)$
$(\mathcal{B}_{r})_{\\#}$ | pushforward of the distribution through $\mathcal{B}_{r}(x)\coloneqq r+x$
$f^{(n)}$ |  $n$-th element of $N$-dimensional vector $f$
$\|f\|_{\infty}$ | max norm of $f:X\rightarrow\mathbb{R}$ defined as $\|f\|_{\infty}\coloneqq\max_{x\in X}|f^{(n)}(x)|$
$\|f\|_{\infty,1}$ |  $l_{1}$-norm of max norm of $f:X\rightarrow\mathbb{R}$ defined as $\|f\|_{\infty,1}\coloneqq\sum_{n=1}^{N}\max_{x\in X}|f^{(n)}(x)|$
$\mathcal{F}^{N}$ | a function class of $N$-dimensional embedding space
$\mathcal{Z}$ | a set of state-action pairs $\mathcal{Z}\coloneqq\\{(s_{t},a_{t})\\}_{t=1}^{|\mathcal{Z}|}$
$\mathcal{D}$ | a dataset $\mathcal{D}\coloneqq\\{(s_{t},a_{t},[d_{t}^{(1)},\cdots,d_{t}^{(N)}])\\}_{t=1}^{|\mathcal{D}|}$
$\|f\|_{\mathcal{Z}}^{2}$ | for $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, define $\|f\|_{\mathcal{Z}}^{2}\coloneqq\sum_{n=1}^{N}\sum_{(s,a)\in\mathcal{Z}}(f^{(n)}(s_{t},a_{t}))^{2}$
$\|f\|_{\mathcal{D}}^{2}$ | for $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, define $\|f\|_{\mathcal{D}}^{2}\coloneqq\sum_{n=1}^{N}\sum_{t=1}^{\mathcal{D}}(f^{(n)}(s_{t},a_{t})-d_{t}^{(n)})^{2}$
$w^{(n)}(\mathcal{F}^{N},s,a)$ | width function of $(s,a)$ defined as $w^{(n)}(\mathcal{F}^{N},s,a)\coloneqq\max_{f,g\in\mathcal{F}^{N}}|f^{(n)}(s,a)-g^{(n)}(s,a)|$
$\tilde{f}^{k}_{h,\bar{\eta}}$ | a solution of moment least squre regression, defined as $\tilde{f}^{k}_{h,\bar{\eta}}\coloneqq\arg\min_{f\in\mathcal{F}^{N}}\|f\|_{\mathcal{D}^{k}_{h}}$
$f_{\bar{\eta}}$ | a target sketch of distribution $\bar{\eta}$, defined as $f_{\bar{\eta}}\coloneqq\psi_{1:N}((\mathcal{B}_{r})_{\\#}[\mathbb{P}_{h}\bar{\eta}])$
$(\mathcal{F}^{N})^{k}_{h}$ | a confidence region at step $h$, episode $k$, defined as $(\mathcal{F}^{N})^{k}_{h}\coloneqq\\{f\in\mathcal{F}^{N}|\ \|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)\\}$
$\psi(\bar{\eta})$ | a statistical functional $\mathscr{P}_{\psi}(\mathbb{R})^{\mathcal{S}}\rightarrow\mathbb{R}^{S}$
$\psi_{1:N}(\bar{\eta})$ | a $N-$collection of statistical functional $\mathscr{P}_{\psi_{1:N}}(\mathbb{R})^{\mathcal{S}}\rightarrow\mathbb{R}^{N\times S}$
$\mathscr{P}_{\psi_{1:N}}(\mathbb{R})$ | a domain of sketch $\psi_{1:N}$
$I_{\psi_{1:N}}$ | an image of sketch $\psi_{1:N}$
$\mathcal{T}$ | distributional Bellman operator, defined as $\mathcal{T}\bar{\eta}\coloneqq(\mathcal{B}_{r})_{\\#}[\mathbb{P}\bar{\eta}]$
$\mathcal{T}_{\psi}$ | sketch Bellman operator w.r.t $\psi$, defined as $\mathcal{T}_{\psi}\psi(\bar{\eta})\coloneqq\psi\Big{(}(\mathcal{B}_{r})_{\\#}[\mathbb{P}\bar{\eta}]\Big{)}$
$\hat{\mathcal{T}}_{\psi}$ | empirical sketch Bellman operator w.r.t $\psi$, defined as $\hat{\mathcal{T}}_{\psi}\psi(\bar{\eta})\coloneqq\psi\Big{(}(\mathcal{B}_{r})_{\\#}[\hat{\mathbb{P}}\bar{\eta}]\Big{)}$
$\mathcal{N}(\mathcal{F}^{N},\epsilon)$ | covering number of $\mathcal{F}^{N}$ w.r.t the $\epsilon-$ball
$\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$ | eluder dimension of $\mathcal{F}^{N}$ w.r.t $\epsilon$

##  Appendix B Related Work and Discussion

###  B.1 Technical Clarifications on Linearity Assumption in Existing Results

#### Bellman Closedness and Linearity.

Rowland et al. [41] proved that quantile functional is not Bellman closed by
providing a specific counterexample. However, their discussion based on
counterexamples can be generalized as it assumes that the sketch Bellman
operator for the quantile functional needs to be linear.

They consider an discounted MDP with initial state $s_{0}$ with single action
$a$, which transits to one of two terminal states $s_{1},s_{2}$ with equal
probability. Letting no reward at state $s_{0}$, $\texttt{Unif}([0,1])$ at
state $s_{1}$, and $\texttt{Unif}([1/K,1+1/K])$ at state $s_{2}$, the return
distribution at state $s_{0}$ is computed as mixture
$\frac{1}{2}\texttt{Unif}([0,\gamma])+\frac{1}{2}\texttt{Unif}([\gamma/K,\gamma+\gamma/K])$.
Then the $\frac{1}{2K}-$quantile at state $s_{0}$ is $\frac{\gamma}{K}$. They
proposed a counterexample where each quantile distribution of state
$s_{1},s_{2}$ is represented as
$\frac{1}{K}\sum_{k=1}^{K}\delta_{\frac{2k-1}{K}}$ and
$\frac{1}{K}\sum_{k=1}^{K}\delta_{\frac{2k+1}{K}}$ respectively, the
$\frac{1}{2K}-$quantile of state $s_{0}$ is
$\psi_{q_{2K}}\Big{(}\frac{1}{2K}\sum_{k=1}^{K}\delta_{\frac{\gamma(2k-1)}{K}}+\delta_{\frac{\gamma(2k+1)}{K}}\Big{)}=\frac{3\gamma}{2K}.$
However, this example does not consider that the mixture of quantiles is not a
quantile of the mixture distribution (i.e.,
$\psi_{q}(\lambda\eta_{1}+(1-\lambda)\eta_{2})\neq\lambda\psi_{q}(\eta_{1})+(1-\lambda)\psi_{q}(\eta_{2})$),
due to the nonlinearity of the quantile functional. Therefore, this does not
present a valid counterexample to prove that quantile functionals are not
Bellman closed.

#### Bellman Optimizability and Linearity.

Marthe et al. [35] proposed the notion of Bellman optimizable statistical
functional which redefine the Bellman update by planning with respect to
statistical functionals rather than expected returns. They proved that
$W_{1}$-continuous Bellman Optimizable statistical functionals are
characterized by exponential utilities
$\frac{1}{\lambda}\log\mathbb{E}_{Z\sim\eta}[\exp(\lambda Z)]$. However, their
proof requires some technical clarification regarding the assumption that such
statistical functionals are linear.

To illustrate, they define a statistical functional $\psi_{f}$ and consider
two probability distributions $\eta_{1}=\frac{1}{2}(\delta_{0}+\delta_{h})$
and $\eta_{2}=\delta_{\phi(h)}$ where
$\phi(h)=f^{-1}\Big{(}\frac{1}{2}(f(0)+f(h))\Big{)}$. Using the translation
property, they lead $\psi_{f}(\eta_{1})=\psi_{f}(\eta_{2})$ to
$\frac{1}{2}(f(x)+f(x+h))=f(x+\phi(h))$ for all $x\in\mathbb{R}$. However,
this equality
$\psi_{f}\Big{(}\frac{1}{2}(\delta_{x}+\delta_{x+h})\Big{)}=\frac{1}{2}(f(x)+f(x+h))$
holds only if $\psi_{f}$ is linear, which is not necessarily a valid
assumption for all statistical functionals.

###  B.2 Existence of Nonlinear Bellman Closed Sketch.

The previous two examples may not have considered the possibility that the
sketch Bellman operator might not necessarily be linear. However, some
statistical functionals are Bellman-closed even if they are nonlinear, so it
is open question whether there is a nonlinear sketch Bellman operator that
makes the quantile functional Bellman-closed. In this section, we present
examples of maximum and minimum functionals that are Bellman-closed, despite
being nonlinear.

In a nutshell, consider the maximum of return distribution at state
$s_{1},s_{2}$ is $\gamma,\gamma+\gamma/K$ respectively. Beyond linearity, the
maximum of return distribution at state $s_{0}$ can be computed by taking the
maximum of these values;

$\max(\max(\bar{\eta}(s_{1})),\max(\bar{\eta}(s_{2})))=\max(\gamma,\gamma+\gamma/K)=\gamma+\gamma/K$

which produces the desired result. This implies the existence of a nonlinear
sketch that is Bellman closed. More precisely, by defining
$\max_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}$ and
$\min_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}$ as the maximum and minimum of the
sampled sketch
$\psi\big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime})\big{)}$ with the
distribution $\mathbb{P}(\cdot|s,a)$, we can derive the sketch Bellman
operator for maximum and minimum functionals as follows;

  * •

$\mathcal{T}_{\psi_{\text{max}}}\Big{(}\psi_{\text{max}}(\bar{\eta}(s))\Big{)}=\max_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\Big{(}\psi_{\text{max}}\big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime})\big{)}\Big{)}$

  * •

$\mathcal{T}_{\psi_{\text{min}}}\Big{(}\psi_{\text{min}}(\bar{\eta}(s))\Big{)}=\min_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\Big{(}\psi_{\text{min}}\big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}(s^{\prime})\big{)}\Big{)}$.

###  B.3 Non-existence of sketch Bellman operator for quantile functional

In this section, we prove that quantile functional cannot be Bellman closed
under any additional sketch. First we introduce the definition of mixture-
consistent, which is the property that the sketch of a mixture can be computed
using only the sketch of the distribution of each component.

######  Definition B.1 (mixture-consistent).

A sketch $\psi$ is mixture-consistent if for any $\lambda\in[0,1]$ and any
distributions $\eta_{1},\eta_{2}\in\mathscr{P}_{\psi}(\mathbb{R})$, there
exists a corresponding function $h_{\psi}$ such that

$\displaystyle\psi(\lambda\eta_{1}+(1-\lambda)\eta_{2})=h_{\psi}\Big{(}\psi(\eta_{1}),\psi(\eta_{2}),\lambda\Big{)}.$

Next, we will provide some examples of determining whether a sketch is
mixture-consistent or not.

#### Example 1.

Every moment or exponential polynomial functional is mixture-consistent.

###### Proof.

For any $n\in[N]$ and $\lambda\in\mathbb{C}$,

$\displaystyle\mathbb{E}_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z^{n}\exp(\lambda
Z)]=\lambda\mathbb{E}_{Z\sim\eta_{1}}[Z^{n}\exp(\lambda
Z)]+(1-\lambda)\mathbb{E}_{Z\sim\eta_{2}}[Z^{n}\exp(\lambda Z)].$

∎

#### Example 2.

Variance functional is not mixture-consistent.

###### Proof.

Let $\lambda=\frac{1}{2}$ and $Z,Y$ be the random variables where
$Z\sim\frac{1}{2}\delta_{0}+\frac{1}{2}\delta_{2}$ and
$Y\sim\frac{1}{2}\delta_{k}+\frac{1}{2}\delta_{k+2}$. Then,
$\text{Var}(Z)=\text{Var}(Y)=1$. While RHS is constant for any $k$, LHS is not
a constant for any $k$, i.e.,

$\displaystyle\text{Var}_{X\sim\frac{1}{2}(\frac{1}{2}\delta_{0}+\frac{1}{2}\delta_{2})+\frac{1}{2}(\frac{1}{2}\delta_{k}+\frac{1}{2}\delta_{k+2})}(X)=\frac{1}{4}(k^{2}+5).$

∎

While variance functional is not mixture consistent by itself, it can be
mixture consistent with another statistical functional, the mean.

#### Example 3.

Variance functional is mixture-consistent under mean functional.

###### Proof.

Notice that mean functional is mixture-consistent. We need to show that
variance functional is mixture-consistent under mean functional.

$\displaystyle\text{Var}_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z]$
$\displaystyle=\mathbb{E}_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z^{2}]-(\mathbb{E}_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z])^{2}$
$\displaystyle=\lambda\mathbb{E}_{Z\sim\eta_{1}}[Z^{2}]+(1-\lambda)\mathbb{E}_{Z\sim\eta_{2}}[Z^{2}]-(\lambda\mathbb{E}_{Z\sim\eta_{1}}[Z]+(1-\lambda)\mathbb{E}_{Z\sim\eta_{2}}[Z])^{2}$
$\displaystyle=\lambda(\text{Var}_{Z\sim\eta_{1}}[Z]+(\mathbb{E}_{Z\sim\eta_{1}}[Z])^{2})+(1-\lambda)(\text{Var}_{Z\sim\eta_{2}}[Z]+(\mathbb{E}_{Z\sim\eta_{2}}[Z])^{2})$
$\displaystyle\qquad-(\lambda\mathbb{E}_{Z\sim\eta_{1}}[Z]+(1-\lambda)\mathbb{E}_{Z\sim\eta_{2}}[Z])^{2}.$

∎

This means that to determine whether it is mixture-consistent or not, we
should check it on a per-sketch basis, rather than on a per-statistical
functional basis.

#### Example 4.

Maximum and minimum functional are both mixture-consistent.

###### Proof.

$\displaystyle\max_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z]=\max(\max_{Z\sim\eta_{1}}[Z],\max_{Z\sim\eta_{2}}[Z])$

and

$\displaystyle\min_{Z\sim\lambda\eta_{1}+(1-\lambda)\eta_{2}}[Z]=\min(\min_{Z\sim\eta_{1}}[Z],\min_{Z\sim\eta_{2}}[Z])$

∎

Since maximum and minimum functionals are mixture consistent, we can construct
a nonlinear sketch bellman operator like the one in section B.2. This is
possible because there is a nonlinear function $h_{\psi}$ that ensures the
sketch is closed under mixture.

Before demonstrating that a quantile sketch cannot be mixture consistent under
any additional sketch, we will first illustrate with the example of a median
functional that is not mixture consistent.

#### Example 5.

Median sketch is not mixture-consistent.

###### Proof.

Let $\lambda=\frac{1}{2}$ and $Z,Y$ be the random variables where $Z\sim
0.2\delta_{0}+0.8\delta_{1}$ and $Y\sim 0.6\delta_{0}+0.4\delta_{k}$ for some
$0<k<1$. Then $\psi_{\text{med}}(Z)=1$ and $\psi_{\text{med}}(Y)=0$. However,

$\displaystyle\text{med}_{X=\frac{Z+Y}{2}}[X]=\psi_{\text{med}}(0.4\delta_{0}+0.2\delta_{k}+0.4\delta_{1})=k$

which is dependent in $k$. ∎

######  Lemma B.2.

Quantile sketch cannot be mixture-consistent, under any additional sketch.

###### Proof.

For a given integer $N>0$ and a quantile level $\alpha\in[0,1]$, let
$\lambda=\frac{1}{2}$ and a random variable $Y\sim
p_{y_{0}}\delta_{0}+p_{y_{1}}\delta_{y_{1}}+\cdots+p_{y_{N}}\delta_{y_{N}}(0<y_{1}<\cdots<y_{N}<1)$
where $p_{y_{0}}>\alpha$ so that $\psi_{q_{\alpha}}(Y)=0$. Consider another
random variable $Z\sim p_{z_{0}}\delta_{0}+p_{z_{1}}\delta_{1}$ where
$p_{z_{0}}<\alpha$ so that $\psi_{q_{\alpha}}(Z)=1$. Then the
$\alpha-$quantile of the mixture $X=\frac{Y+Z}{2}$ is

$\psi_{q_{\alpha}}[X]=y_{n}\text{ where }n=\min\left\\{n\leq N\Big{|}\
\frac{1}{2}\sum_{n^{\prime}=0}^{n}p_{y_{n^{\prime}}}+\frac{1}{2}p_{z_{0}}>\alpha\right\\}.$

Letting $p_{z_{0}}=2\alpha-\sum_{n^{\prime}=0}^{n}p_{y_{n^{\prime}}}$, we can
manipulate $\psi_{q_{\alpha}}[X]$ to be any value of $y_{n}$. Hence,
$\psi(q_{\alpha})[X]$ is a function of all possible outcomes of $Y$.

If there exists a finite number of statistical functionals which make quantile
sketch mixture-consistent, then such sketch would uniquely determine the
distribution for any $N$. This results in a contradiction that infinite-
dimensional distribution space can be represented by a finite number of
statistical functional. ∎

######  Lemma B.3.

If a sketch $\psi$ is Bellman closed, then it is mixture-consistent.

###### Proof.

Consider an MDP where initial state $s_{0}$ has no reward and transits to two
state $s_{1},s_{2}$ with probability $\lambda,1-\lambda$ and reward
distribution $\bar{\eta}_{1},\bar{\eta}_{2}$. Since $\psi$ is Bellman closed,
$\psi(\bar{\eta}(s_{0}))$ is a function of $\psi(\bar{\eta}(s_{1}))$ and
$\psi(\bar{\eta}(s_{2}))$, (i.e., $\psi(\bar{\eta}(s_{0}))$ =
$g_{\psi}(\psi(\bar{\eta}(s_{1}))$, $\psi(\bar{\eta}(s_{2})))$ for some
$g_{\psi}$). Since
$\psi(\bar{\eta}(s_{0}))=\psi(\lambda\bar{\eta}(s_{1})+(1-\lambda)\bar{\eta}(s_{2}))$,
it implies that $\psi$ is mixture-consistent. ∎

Combining the results of Lemma B.2 and Lemma B.3, we prove that a quantile
sketch cannot be Bellman closed, no matter what additional sketches are
provided.

##  Appendix C Proof

######  Theorem (4.4).

Quantile functional cannot be Bellman closed under any additional sketch.

###### Proof.

See Lemma B.2 and Lemma B.3. ∎

######  Lemma (4.6).

Let $F_{\bar{\eta}}$ be a CDF of the probability distribution
$\bar{\eta}\in\mathscr{P}(\mathbb{R})^{\mathcal{S}}$. Then a sketch is Bellman
unbiased if and only if the sketch is a homogeneous of degree $k$, i.e., there
exists some vector-valued function
$h=h(x_{1},\cdots,x_{k}):\mathcal{X}^{k}\rightarrow\mathbb{R}^{N}$ such that

$\psi(\bar{\eta})=\int\cdots\int
h(x_{1},\cdots,x_{k})dF_{\bar{\eta}}(x_{1})\cdots dF_{\bar{\eta}}(x_{k}).$

###### Proof.

($\Rightarrow$) Consider an two-stage MDP with a single action $a$, and an
initial state $s_{0}$ which transits to one of terminal state
$\\{s_{1},\cdots,s_{K}\\}$ with transition kernel $\mathbb{P}(\cdot|s_{0},a)$.
Assume that the reward $r(s_{0})=0$. Then
$\bar{\eta}(s_{0})=\sum_{k=1}^{K}\mathbb{P}(s_{k})\delta_{r(s_{k})}$. Note
that $s^{\prime}_{1},\cdots,s^{\prime}_{k}$ are independent and identically
distributed random variable in distribution $\mathbb{P}(\cdot|s,a)$.

$\displaystyle\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{0},a)}\left[\phi_{\psi}\left(\psi\Big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}({s^{\prime}_{1}})\Big{)},\cdots,\psi\Big{(}(\mathcal{B}_{r})_{\\#}\bar{\eta}({s^{\prime}_{k}})\Big{)}\right)\right]=\psi_{1:N}\Big{(}(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{0},a)}[\bar{\eta}(s^{\prime})]\Big{)}$
$\displaystyle\Longrightarrow\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{0},a)}\left[\phi_{\psi}\left(\psi\Big{(}\delta_{r({s^{\prime}_{1}})}\Big{)},\cdots,\psi\Big{(}\delta_{r({s^{\prime}_{k}})}\Big{)}\right)\right]=\psi\Big{(}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{0},a)}[\delta_{r(s^{\prime})}]\Big{)}$
$\displaystyle\Longrightarrow\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{0},a)}\left[\phi_{\psi}\Big{(}g({s^{\prime}_{1}}),\cdots,g({s^{\prime}_{k}})\Big{)}\right]=\psi\Big{(}{\bar{\eta}}({s_{0}})\Big{)}$
$\displaystyle\Longrightarrow\int\cdots\int
h(s^{\prime}_{1},\cdots,s^{\prime}_{k})dF_{\bar{\eta}}(s^{\prime}_{1})\cdots
dF_{\bar{\eta}}(s^{\prime}_{k})=\psi\Big{(}{\bar{\eta}}({s_{0}})\Big{)}.$

($\Leftarrow$)

$\displaystyle\psi\Big{(}(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})]\Big{)}$
$\displaystyle=\int\cdots\int
h(x_{1},\cdots,x_{k})dF_{(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})]}(x_{1}),\cdots,dF_{(\mathcal{B}_{r})_{\\#}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[\bar{\eta}(s^{\prime})](x_{k})}$
$\displaystyle=\int\cdots\int
h(x_{1}+r,\cdots,x_{k}+r)d\Big{(}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}F_{\bar{\eta}(s^{\prime})}(x_{1})\Big{)},\cdots,d\Big{(}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}F_{\bar{\eta}(s^{\prime})}(x_{k})\Big{)}$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\int\cdots\int
h(x_{1}+r,\cdots,x_{k}+r)dF_{\bar{\eta}(s^{\prime})}(x_{1})\cdots
dF_{\bar{\eta}(s^{\prime})}(x_{k})\right]$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\psi\Big{(}(\mathcal{B}_{r})_{\\#}[\bar{\eta}(s^{\prime})]\Big{)}\right]$

∎

######  Theorem (4.7).

The only finite statistical functionals that are Bellman unbiased and closed
are given by the collections of $\psi_{1},\dots,\psi_{N}$ where its linear
span $\\{\sum_{n=0}^{N}\alpha_{n}\psi_{n}|\ \alpha_{n}\in\mathbb{R}\ ,\forall
N\\}$ is equal to the set of exponential polynomial functionals
$\\{\eta\rightarrow\mathbb{E}_{Z\sim\eta}[Z^{l}\exp{(\lambda Z)}]|\
l=0,1,\dots,L,\lambda\in\mathbb{R}\\}$, where $\psi_{0}$ is the constant
functional equal to $1$. In discount setting, it is equal to the linear span
of the set of moment functionals
$\\{\eta\rightarrow\mathbb{E}_{Z\sim\eta}[Z^{l}]|\ l=0,1,\dots,L\\}$ for some
$L\leq N$.

###### Proof.

Our proof is mainly based on the proof techniques of Rowland et al. [41] and
we describe in an extended form. Since their proof also considers the
discounted setting, we will define $\mathcal{B}_{r,\gamma}(x)=r+\gamma x$ for
discount factor $\gamma\in[0,1)$. By assumption of Bellman closedness,
$\psi_{n}\Big{(}(\mathcal{B}_{r,\gamma})_{\\#}\bar{\eta}(s^{\prime})\Big{)}$
will be written as $g(r,\gamma,\psi_{1:N}(\bar{\eta}(s^{\prime}))$ for some
$g$. By assumption of Bellman unbiasedness and Lemma 4.6, both
$\psi_{1:N}(\bar{\eta}(s^{\prime}))$ and
$\psi_{n}\Big{(}(\mathcal{B}_{r,\gamma})_{\\#}\bar{\eta}(s^{\prime})\Big{)}$
are affine as functions of the distribution $\bar{\eta}(s^{\prime})$,

$\displaystyle\psi_{1:N}(\alpha\bar{\eta}_{1}(s^{\prime})+(1-\alpha)\bar{\eta}_{2}(s^{\prime}))$
$\displaystyle=\mathbb{E}_{Z_{i}\sim\alpha\bar{\eta}_{1}(s^{\prime})+(1-\alpha)\bar{\eta}_{2}(s^{\prime})}[h_{1:N}(\bar{Z}_{1},\cdots,\bar{Z}_{k})]$
$\displaystyle=\alpha\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}_{1}(s^{\prime})}[h_{1:N}(\bar{Z}_{1},\cdots,\bar{Z}_{k})]+(1-\alpha)\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}_{2}(s^{\prime})}[h_{1:N}(\bar{Z}_{1},\cdots,\bar{Z}_{k})]$
$\displaystyle=\alpha\psi_{1:N}(\bar{\eta}_{1}(s^{\prime}))+(1-\alpha)\psi_{1:N}(\bar{\eta}_{2}(s^{\prime}))$

and

$\displaystyle\psi_{n}\Big{(}(\mathcal{B}_{r,\gamma})_{\\#}(\alpha\bar{\eta}_{1}(s^{\prime})+(1-\alpha)\bar{\eta}_{2}(s^{\prime}))\Big{)}$
$\displaystyle=\mathbb{E}_{Z_{i}\sim\alpha\bar{\eta}_{1}(s^{\prime})+(1-\alpha)\bar{\eta}_{2}(s^{\prime})}[h_{n}(r+\gamma\bar{Z}_{1},\cdots,r+\gamma\bar{Z}_{k})]$
$\displaystyle=\alpha\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}_{1}(s^{\prime})}[h_{n}(r+\gamma\bar{Z}_{1},\cdots,r+\gamma\bar{Z}_{k})]+(1-\alpha)\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}_{2}(s^{\prime})}[h_{n}(r+\gamma\bar{Z}_{1},\cdots,r+\gamma\bar{Z}_{k})]$
$\displaystyle=\alpha\psi_{n}\Big{(}(\mathcal{B}_{r,\gamma})_{\\#}\bar{\eta}_{1}(s^{\prime})\Big{)}+(1-\alpha)\psi_{n}\Big{(}(\mathcal{B}_{r,\gamma})_{\\#}\bar{\eta}_{2}(s^{\prime})\Big{)}$

Therefore, $g(r,\gamma,\cdot)$ is also affine on the convex codomain of
$\psi_{1:N}$.  Thus, we have

$\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}}[\phi_{\psi_{n}}(r+\gamma\bar{Z}_{1},\cdots,r+\gamma\bar{Z}_{k})]=a_{0}(r,\gamma)+\sum_{n^{\prime}=1}^{N}a_{n^{\prime}}(r,\gamma)\mathbb{E}_{\bar{Z}_{i}\sim\bar{\eta}}[\phi_{\psi_{n^{\prime}}}(\bar{Z}_{1},\cdots,\bar{Z}_{k})]$

for some function $a_{0:N}:\mathbb{R}\times[0,1]\rightarrow\mathbb{R}$. By
taking $\bar{\eta}(s^{\prime})=\delta_{x}$, we obtain

$\phi_{\psi_{n}}(r+\gamma x,\cdots,r+\gamma
x)=a_{0}(r,\gamma)+\sum_{n^{\prime}=1}^{N}a_{n^{\prime}}(r,\gamma)\phi_{\psi_{n^{\prime}}}(x,\cdots,x).$

According to Engert [18], for any translation invariant finite-dimensional
space is spanned by a set of function of the form

$\\{x\mapsto x^{l}\exp(\lambda_{j}x)|\ j\in[J],0\leq l\leq L\\}$

for some finite subset $\\{\lambda_{1},\cdots,\lambda_{J}\\}$ of $\mathbb{C}$.
Hence, each function $x\mapsto\phi_{\psi_{n}}(x,\cdots,x)$ is expressed as
linear combination of exponential polynomial functions. In addition, the
linear combination of $\phi_{\psi_{n}}$ should be closed under composition
with for any discount factor $\gamma\in[0,1]$, all $\lambda_{j}$ should be
zero. Hence, the linear combination of
$\phi_{\psi_{1}},\cdots,\phi_{\psi_{N}}$ must be equal to the span of
$\\{x\mapsto x^{l}|\ 0\leq l\leq L\\}$ for some $L\in\mathbb{N}$.

∎

######  Lemma (6.3).

Consider a fixed $k\in[K]$ and a fixed $h\in[H]$. Let
$\mathcal{Z}_{h}^{k}=\\{(s_{h}^{\tau},a_{h}^{\tau})\\}_{\tau\in[k-1]}$ and
$\mathcal{D}^{k}_{h,\bar{\eta}}=\Big{\\{}\Big{(}s_{h}^{\tau},a_{h}^{\tau},{\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h^{\prime}}}^{\tau})_{\\#}\bar{\eta}(s_{h^{\prime}+1}^{\tau})\Big{)}}\Big{)}\Big{\\}}_{\tau\in[k-1]}$
for any $\bar{\eta}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$. Define
$\tilde{f}_{h,\bar{\eta}}^{k}=\arg\min_{f\in\mathcal{F}^{N}}\|f\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}}}$.
For any $\bar{\eta}$ and $\delta\in(0,1)$, there is an event
$\mathcal{E}(\bar{\eta},\delta)$ such that conditioned on
$\mathcal{E}(\bar{\eta},\delta)$, with probability at least $1-\delta$, for
any $\bar{\eta}^{\prime}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$ with
$\|\psi_{1:N}(\bar{\eta}^{\prime})-\psi_{1:N}(\bar{\eta})\|_{\infty,1}\leq
1/T$ or
$\sum_{n=1}^{N}\|\psi_{n}(\bar{\eta}^{\prime})-\psi_{n}(\bar{\eta})\|_{\infty}\leq
1/T$, we have

$\displaystyle\left\|\tilde{f}_{h,\bar{\eta}^{\prime}}(\cdot,\cdot)-\psi_{1:N}\Big{(}(\mathcal{B}_{r(\cdot,\cdot)})_{\\#}[\mathbb{P}\bar{\eta}^{\prime}](\cdot,\cdot)\Big{)}\right\|_{\mathcal{Z}_{h}^{k}}$
$\displaystyle\leq{c^{\prime}\left(N^{\frac{1}{2}}H\sqrt{\log(1/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T)}\right)}$

for some constant $c^{\prime}>0$.

###### Proof.

Define the sketch of target
$f_{\bar{\eta}}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{N}$,

$\displaystyle
f_{\bar{\eta}}(\cdot,\cdot)\coloneqq\psi_{1:N}\Big{(}(\mathcal{B}_{r(\cdot,\cdot)})_{\\#}[\mathbb{P}\bar{\eta}](\cdot,\cdot)\Big{)}$

for all $i\in[N].$

For any $f\in\mathcal{F}$,

$\displaystyle\|f\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}^{\prime}}}-\|f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}^{\prime}}}$
$\displaystyle=\sum_{n=1}^{N}\sum_{s_{h}^{\tau},a_{h}^{\tau}\in{\mathcal{Z}^{k}_{h,\bar{\eta}^{\prime}}}}\Big{(}f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s_{h+1}^{\tau})\Big{)}\Big{)}^{2}-\Big{(}f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s_{h+1}^{\tau})\Big{)}\Big{)}^{2}$
$\displaystyle=\sum_{n=1}^{N}\sum_{s_{h}^{\tau},a_{h}^{\tau}\in{\mathcal{Z}^{k}_{h,\bar{\eta}^{\prime}}}}(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))^{2}$
$\displaystyle\qquad+2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))\Big{(}f^{(n)}_{\bar{\eta}^{\prime}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s_{h+1}^{\tau})\Big{)}\Big{)}$
$\displaystyle\geq\|f-f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{Z}_{h}^{k}}{-4\sum_{n=1}^{N}\|f_{\bar{\eta}}^{(n)}-f_{\bar{\eta}^{\prime}}^{(n)}\|_{\infty}(H+1)|\mathcal{Z}_{h}^{k}|}$
$\displaystyle\qquad+\sum_{n=1}^{N}\sum_{s_{h}^{\tau},a_{h}^{\tau}\in{\mathcal{Z}^{k}_{h,\bar{\eta}^{\prime}}}}\Big{[}\underbrace{2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))\Big{(}f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}(s_{h+1}^{\tau})\Big{)}\Big{)}}_{\chi_{h}^{\tau}(f^{(n)})}\Big{]}$
$\displaystyle\geq\|f-f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{Z}_{h}^{k}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-4N(H+1)}-\Big{|}\sum_{n=1}^{N}\sum_{s_{h}^{\tau},a_{h}^{\tau}\in\mathcal{Z}^{k}_{h,\bar{\eta}^{\prime}}}\chi^{\tau}_{h}(f^{(n)})\Big{|}.$

For the first inequality, we change the second term from $\bar{\eta}^{\prime}$
to $\bar{\eta}$ which are the $\epsilon$-covers. Notice that $AC-
BC^{\prime}\geq-|AC-
BC^{\prime}|\geq-|(A-B)C|-|(A-B)C^{\prime}|\geq-2|A-B||\max(C,C^{\prime})|$.

$\displaystyle(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))\Big{(}f^{(n)}_{\bar{\eta}^{\prime}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s_{h+1}^{\tau})\Big{)}\Big{)}$
$\displaystyle\qquad-(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))\Big{(}f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}(s_{h+1}^{\tau})\Big{)}\Big{)}$
$\displaystyle\geq-2\|f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})\|$
$\displaystyle\qquad\times\max\Big{(}\Big{|}f^{(n)}_{\bar{\eta}^{\prime}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s_{h+1}^{\tau})\Big{)}\Big{|},\Big{|}f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}(s_{h+1}^{\tau})\Big{)}\Big{|}\Big{)}$
$\displaystyle\geq-2\|f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})\|(H+1)$

For the second inequality, consider
$\bar{\eta}^{\prime}:\mathcal{S}\rightarrow\mathscr{P}([0,H])$ with
$\sum_{n=1}^{N}\|\psi_{n}(\bar{\eta}^{\prime})-\psi_{n}(\bar{\eta})\|_{\infty}\leq
1/T$. We have

$\displaystyle\|f^{(n)}_{\bar{\eta}}-f^{(n)}_{\bar{\eta}^{\prime}}\|_{\infty}$
$\displaystyle=\max_{s,a}\Big{|}\sum_{n^{\prime}=1}^{n}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H^{n^{\prime}}}[\psi_{n^{\prime}}([\mathbb{P}\bar{\eta}](s,a))-\psi_{n^{\prime}}([\mathbb{P}\bar{\eta}^{\prime}](s,a))]r^{n-n^{\prime}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}/H^{n-1}}\Big{|}$
$\displaystyle\leq\sum_{n^{\prime}=1}^{n}\max_{s^{\prime}}\Big{|}\psi_{n^{\prime}}(\bar{\eta}(s^{\prime}))-\psi_{n^{\prime}}(\bar{\eta}^{\prime}(s^{\prime}))\Big{|}$
$\displaystyle\leq 1/T.$

Defining $\mathbb{F}_{h}^{k}$ as the filtration induced by the sequence
$\\{(s_{h^{\prime}}^{\tau},a_{h^{\prime}}^{\tau})\\}_{\tau,h^{\prime}\in[k-1]\times[H]}\cup\\{(s_{1}^{k},a_{1}^{k}),(s_{2}^{k},a_{2}^{k}),\dots,(s_{h}^{k},a_{h}^{k})\\}$,
notice that

$\displaystyle\mathbb{E}\Big{[}\sum_{n=1}^{N}\chi_{h}^{\tau}(f^{(n)})\Big{|}\mathbb{F}_{h}^{\tau}\Big{]}$
$\displaystyle=\sum_{n=1}^{N}2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))(f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-\mathbb{E}\Big{[}\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}{\bar{\eta}}(s_{h+1}^{\tau})\Big{)}\Big{|}\mathbb{F}_{h}^{\tau}\Big{]})$
$\displaystyle=\sum_{n=1}^{N}2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))(f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-\mathbb{E}_{s_{h+1}^{\tau}\sim\mathbb{P}_{h}(\cdot|s_{h}^{\tau},a_{h}^{\tau})}\Big{[}\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}{\bar{\eta}}(s_{h+1}^{\tau})\Big{)}\Big{]})$
$\displaystyle=\sum_{n=1}^{N}2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))(f^{(n)}_{\bar{\eta}}(s_{h}^{\tau},a_{h}^{\tau})-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\mathbb{E}_{s_{h+1}^{\tau}\sim\mathbb{P}_{h}(\cdot|s_{h}^{\tau},a_{h}^{\tau})}[{\bar{\eta}}(s_{h+1}^{\tau})]\Big{)})}$
$\displaystyle=0$

and

$\displaystyle\Big{|}\sum_{n=1}^{N}\chi_{h}^{\tau}(f^{(n)})\Big{|}$
$\displaystyle=\Big{|}\sum_{n=1}^{N}2(f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau}))(f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}{\bar{\eta}}(s_{h+1}^{\tau})\Big{)})\Big{|}$
$\displaystyle\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\max_{n\in[N]}\Big{\\{}2(f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}{\bar{\eta}}(s_{h+1}^{\tau})\Big{)})\Big{\\}}}\sum_{n=1}^{N}\Big{|}f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})\Big{|}$
$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\leq
2(H+1)\sum_{n=1}^{N}\Big{|}f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f_{\bar{\eta}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})\Big{|}}$

In third equality, we emphasize that only Bellman unbiased sketch can derive
the martingale difference sequence which induce the concentration result.
Since every moment functional is commutable with mixing operation, the
transformation $\phi_{\psi_{n}}$ in Definition 4.5 is identity for all
$n\in[N]$. Hence, we choose the sketch as moment which already knows
$\phi_{\psi}$.

By Azuma-Hoeffding inequality,

$\displaystyle\mathbb{P}\Big{[}\Big{|}\sum_{(\tau,h)\in[k-1]\times[H]}\sum_{n=1}^{N}\chi_{h}^{\tau}(f^{(n)})\Big{|}\geq\epsilon\Big{]}$
$\displaystyle\leq
2\exp\Big{(}-\frac{\epsilon^{2}}{2(2(H+1))^{2}\sum_{(\tau,h)\in[k-1]\times[H]}\Big{(}\sum_{n=1}^{N}|f^{(n)}-f_{\bar{\eta}}^{(n)}|\Big{)}^{2}}\Big{)}$
$\displaystyle\leq
2\exp\Big{(}-\frac{\epsilon^{2}}{2(2(H+1))^{2}\sum_{(\tau,h)\in[k-1]\times[H]}\Big{(}N\sum_{n=1}^{N}|f^{(n)}-f_{\bar{\eta}}^{(n)}|^{2}\Big{)}}\Big{)}$
$\displaystyle=2\exp\Big{(}-\frac{\epsilon^{2}}{2N(2(H+1))^{2}\|f-f_{\bar{\eta}}\|_{\mathcal{Z}_{h}^{k}}^{2}}\Big{)}$

where the second inequality follows from the Cauchy-Schwartz inequality.

We set

$\displaystyle\epsilon=\sqrt{8N(H+1)^{2}\|f-f_{\bar{\eta}}\|^{2}_{\mathcal{Z}_{h}^{k}}\log\Big{(}\frac{\mathcal{N}(\mathcal{F}^{N},1/T)}{\delta}\Big{)}}$

With union bound for all $f\in\mathcal{C}(\mathcal{F}^{N},1/T)$, with
probability at least $1-\delta$,

$\displaystyle\Big{|}\sum_{(\tau,h)\in[k-1]\times[H]}\sum_{n=1}^{N}\chi_{h}^{\tau}(f^{(n)})\Big{|}\leq
c^{\prime}N^{\frac{1}{2}}(H+1)\|f-f_{\bar{\eta}}\|_{\mathcal{Z}_{h}^{k}}\sqrt{\log\Big{(}\frac{\mathcal{N}(\mathcal{F}^{N},1/T)}{\delta}\Big{)}}$

for some constant $c^{\prime}>0$.

For all $f\in\mathcal{F}^{N}$, there exists
$g\in\mathcal{C}(\mathcal{F}^{N},1/T)$, such that $\|f-g\|_{\infty,1}\leq 1/T$
or $\sum_{n=1}^{N}\|f^{(n)}-g^{(n)}\|_{\infty}\leq 1/T$ for all $n\in[N]$,

$\displaystyle\Big{|}\sum_{(\tau,h)\in[k-1]\times[H]}\sum_{n=1}^{N}\chi_{h}^{\tau}(f^{(n)})\Big{|}$
$\displaystyle\leq\Big{|}\sum_{(\tau,h)\in[k-1]\times[H]}\sum_{n=1}^{N}\chi_{h}^{\tau}(g^{(n)})\Big{|}+2(H+1)|\mathcal{Z}^{k}_{h}|\sum_{n=1}^{N}\frac{1}{T}$
$\displaystyle\leq
c^{\prime}N^{\frac{1}{2}}(H+1)\|g-f_{\bar{\eta}}\|_{\mathcal{Z}^{k}_{h}}\sqrt{\log\Big{(}\frac{\mathcal{N}(\mathcal{F}^{N},1/T)}{\delta}\Big{)}}+2N(H+1)$
$\displaystyle\leq
c^{\prime}N^{\frac{1}{2}}(H+1)(\|f-f_{\bar{\eta}}\|_{\mathcal{Z}^{k}_{h}}+1)\sqrt{\log\Big{(}\frac{\mathcal{N}(\mathcal{F}^{N},1/T)}{\delta}\Big{)}}+2N(H+1)$
$\displaystyle\leq
c^{\prime}N^{\frac{1}{2}}(H+1)(\|f-f_{\bar{\eta}^{\prime}}\|_{\mathcal{Z}^{k}_{h}}+2)\sqrt{\log\Big{(}\frac{\mathcal{N}(\mathcal{F}^{N},1/T)}{\delta}\Big{)}}+2N(H+1)$

where the third inequality follows from,

$\displaystyle\|f-g\|_{\mathcal{Z}_{h}^{k}}^{2}$
$\displaystyle\leq\sum_{n=1}^{N}\sum_{(\tau,h)\in[k-1]\times[H]}|f^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-g^{(n)}(s_{h}^{\tau},a_{h}^{\tau})|^{2}$
$\displaystyle\leq NT\Big{(}\frac{1}{T}\Big{)}^{2}$ $\displaystyle\leq 1.$

Recall that
$\tilde{f}^{k}_{h,\eta^{\prime}}=\arg\min_{f\in\mathcal{F}}\|f\|^{2}_{\mathcal{D}^{k}_{h,\eta^{\prime}}}$.
We have
$\|\tilde{f}^{k}_{h,\eta^{\prime}}\|^{2}_{\mathcal{D}^{k}_{h,\eta^{\prime}}}-\|{f_{\bar{\eta}^{\prime}}}\|^{2}_{\mathcal{D}^{k}_{h,\eta^{\prime}}}\leq
0$, which implies,

$\displaystyle 0$
$\displaystyle\geq\|\tilde{f}^{k}_{h,\bar{\eta}^{\prime}}\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}^{\prime}}}-\|f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{D}^{k}_{h,\bar{\eta}^{\prime}}}$
$\displaystyle=\|\tilde{f}^{k}_{h,\bar{\eta}^{\prime}}-f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{Z}^{k}_{h}}$
$\displaystyle\qquad+2\sum_{n=1}^{N}\sum_{(\tau,h)\in[k-1]\times[H]}\Big{[}(({\tilde{f}^{k}_{h,\bar{\eta}^{\prime}}})^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-f^{(n)}_{\bar{\eta}^{\prime}}(s_{h}^{\tau},a_{h}^{\tau}))((f_{\bar{\eta}^{\prime}}^{(n)}(s_{h}^{\tau},a_{h}^{\tau})-\psi_{n}\Big{(}(\mathcal{B}_{r_{h}^{\tau}})_{\\#}\bar{\eta}^{\prime}(s^{\tau}_{h+1})\Big{)})\Big{]}$
$\displaystyle\geq\|\tilde{f}^{k}_{h,\bar{\eta}^{\prime}}-f_{\bar{\eta}^{\prime}}\|^{2}_{\mathcal{Z}^{k}_{h}}-c^{\prime}N^{\frac{1}{2}}(H+1)(\|\hat{f}^{k}_{h,\bar{\eta}^{\prime}}-f_{\bar{\eta}^{\prime}}\|_{\mathcal{Z}^{k}_{h}}+2)\sqrt{\log(2/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T)}-6N(H+1).$

Recall that if $x^{2}-2ax-b\leq 0$ holds for constant $a,b>0$, then $x\leq
a+\sqrt{a^{2}+b}\leq c^{\prime}\cdot a$ for some constant $c^{\prime}>0$.

Hence,

$\displaystyle\|\tilde{f}^{k}_{h,\eta^{\prime}}-{f_{\bar{\eta}^{\prime}}}\|_{\mathcal{Z}^{k}_{h}}\leq
c^{\prime}(N^{\frac{1}{2}}H\sqrt{\log(1/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T)})$

for some constant $c^{\prime}>0$. ∎

######  Lemma (6.4).

Let
$(\mathcal{F}^{N})_{h}^{k}=\\{f\in\mathcal{F}^{N}|\|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)\\}$,
where

$\beta(\mathcal{F}^{N},\delta)\geq c^{\prime}\cdot
NH^{2}(\log(T/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T))$

for some constant $c^{\prime}>0$. Then with probability at least $1-\delta/2$,
for all $k,h\in[K]\times[H]$, we have

$\psi_{n}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\in(\mathcal{F}^{N})_{h}^{k}$

###### Proof.

For all $(k,h)\in[K]\times[H]$,

$\mathbf{S}\coloneqq\begin{cases}\Big{\\{}\Big{(}\min\\{f^{(1)}(\cdot,\cdot)+b^{k}_{h+1}(\cdot,\cdot),H\\}\Big{)}\Big{|}\
f\in\mathcal{C}(\mathcal{F}^{N},1/T)\Big{\\}}\cup\Big{\\{}0\Big{\\}}&n=1\\\
\Big{\\{}\Big{(}\min\\{f^{(n)}(\cdot,\cdot),H\\}\Big{)}\Big{|}\
f\in\mathcal{C}(\mathcal{F}^{N},1/T)\Big{\\}}\cup\Big{\\{}0\Big{\\}}&2\leq
n\leq N\end{cases}$

is a $(1/T)$-cover of $\psi_{1:N}({\eta}^{k}_{h+1}(\cdot,\cdot))$ where

$\psi_{1:N}(\eta^{k}_{h+1}(\cdot,\cdot))=\begin{cases}\min\\{(f^{k}_{h+1})^{(1)}(\cdot,\cdot)+b^{k}_{h+1}(\cdot,\cdot),H\\}&n=1\text{
and }h<H\\\ \min\\{(f^{k}_{h+1})^{(n)}(\cdot,\cdot),H\\}&2\leq n\leq N\text{
and }h<H\\\ \bm{0}^{N}&h=H\end{cases},$

i.e., there exists $\psi_{1:N}({\eta})\in\mathbf{S}$ such that
$\|\psi_{1:N}({\eta})-\psi_{1:N}({\eta}^{k}_{h+1})\|_{\infty,1}\leq 1/T$. This
implies

$\bar{\mathbf{S}}\coloneqq\Big{\\{}\psi_{1:N}\Big{(}{\eta}(\cdot,\arg\max_{a\in\mathcal{A}}\psi_{1}({\eta}(\cdot,a)))\Big{)}\mid\psi_{1:N}({\eta})\in\mathbf{S}\Big{\\}}$

is a $(1/T)$-cover of $\psi_{1:N}(\bar{\eta}^{k}_{h+1})$ with
$\log(|\bar{\mathbf{S}}|)\leq\log\mathcal{N}(\mathcal{F}^{N},1/T)$.

For each $\psi_{1:N}(\bar{\eta})\in\bar{\mathbf{S}}$, let
$\mathcal{E}(\bar{\eta},\delta/2|\bar{\mathbf{S}}|T)$ be the event defined in
Lemma 6.3. By union bound for all $\psi_{1:N}(\bar{\eta})\in\bar{\mathbf{S}}$,
we have
$\text{Pr}[\bigcap_{\psi_{1:N}(\bar{\eta})\in\bar{\mathbf{S}}}\mathcal{E}(\bar{\eta},\delta/2|\bar{\mathbf{S}}|T)]\geq
1-\delta/2T$.

Let $\psi_{1:N}(\bar{\eta})\in\bar{\mathbf{S}}$ such that
$\|\psi_{1:N}(\bar{\eta})-\psi_{1:N}(\bar{\eta}_{h+1}^{k})\|_{\infty,1}\leq
1/T$. Conditioned on
$\bigcap_{s_{N}(\bar{\eta})\in\bar{\mathbf{S}}}\mathcal{E}(\bar{\eta},\delta/2|\bar{\mathbf{S}}|T)$
and by Lemma 6.3, we have

$\displaystyle\Big{\|}\tilde{f}^{k}_{h,\bar{\eta}}(\cdot,\cdot)-\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\Big{\|}^{2}_{\mathcal{Z}^{k}_{h}}\leq
c^{\prime}\Big{(}NH^{2}(\log(T/\delta)+\log\mathcal{N}(\mathcal{F}^{N},1/T))\Big{)}$

for some constant $c^{\prime}>0$.

By union bound for all $(k,h)\in[K]\times[H]$, we have
$\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\in(\mathcal{F}^{N})_{h}^{k}$
with probability $1-\delta/2$. ∎

######  Lemma C.1.

Let
$Q^{k}_{h}(s,a)\coloneqq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\min\\{H,\tilde{f}^{k}_{h}(s,a)+b^{k}_{h}(s,a)\\}}$
for some bonus function $b^{k}_{h}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. If $b^{k}_{h}(s,a)\geq
w^{(1)}((\mathcal{F}^{N})^{k}_{h},s,a)$ , then with probability at least
$1-\delta/2$,

$Q^{*}_{h}(s,a)\leq Q^{k}_{h}(s,a)\text{ and }V^{*}_{h}(s)\leq V^{k}_{h}(s)$

for all $(k,h)\in[K]\times[H]$, for all
$(s,a)\in\mathcal{S}\times\mathcal{A}.$

###### Proof.

We use induction on $h$ from $h=H$ to $1$ to prove the statement. Let
$\mathcal{E}$ be the event that for $(k,h)\in[K]\times[H]$,
$\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}^{k}_{h+1}](\cdot,\cdot)\Big{)}\in(\mathcal{F}^{N})^{k}_{h}$.
By Lemma 6.4, $\text{Pr}|\mathcal{E}|\geq 1-\delta/2$. In the rest of the
proof, we condition on $\mathcal{E}$.

When $h=H+1$, the desired inequality holds as
$Q^{*}_{H+1}(s,a)=V^{*}_{H+1}(s)=Q^{k}_{H+1}(s,a)=V^{k}_{H+1}(s)=0$. Now,
assume that $Q^{*}_{h+1}(s,a)\leq Q^{k}_{h+1}(s,a)$ and $V^{*}_{h+1}(s)\leq
V^{k}_{h+1}(s)$ for some $h\in[H]$. Then, for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle Q^{*}_{h}(s,a)$
$\displaystyle=\min\\{H,r_{h}(s,a)+[\mathbb{P}_{h}V^{*}_{h+1}](s,a)\\}$
$\displaystyle\leq\min\\{H,r_{h}(s,a)+[\mathbb{P}_{h}V^{k}_{h+1}](s,a)\\}$
$\displaystyle\leq\min\\{H,\tilde{f}^{k}_{h}(s,a)+w^{(1)}(\mathcal{F}^{k}_{h},s,a)\\}$
$\displaystyle=\min\\{H,Q^{k}_{h}(s,a)-b^{k}_{h}(s,a)+w^{(1)}(\mathcal{F}^{k}_{h},s,a)\\}$
$\displaystyle\leq Q^{k}_{h}(s,a)$

∎

######  Lemma C.2 (Regret decomposition).

With probability at least $1-\delta/4$, we have

$\text{Reg}(K)\leq\sum_{k=1}^{K}\sum_{h=1}^{H}(2b^{k}_{h}(s^{k}_{h},a^{k}_{h})+\xi^{k}_{h}),$

where
$\xi^{k}_{h}=[\mathbb{P}_{h}(V^{k}_{h+1}-V^{\pi^{k}}_{h+1})](s^{k}_{h},a^{k}_{h})-(V^{k}_{h+1}(s^{k}_{h+1})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1}))$
is a martingale difference sequence with respect to the filtration
$\mathbb{F}^{k}_{h}$ induced by the history $\mathbb{H}^{k}_{h}$.

###### Proof.

We condition on the above event $\mathcal{E}$ in the rest of the proof. For
all $(k,h)\in[K]\times[H]$, we have

$\displaystyle\Big{\|}\tilde{f}^{k}_{h,\bar{\eta}}(\cdot,\cdot)-\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\Big{\|}^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta).$

Recall that
$(\mathcal{F}^{N})_{h}^{k}=\\{f\in\mathcal{F}^{N}\mid\|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)\\}$
is the confidence region. Since
$\psi_{1:N}\Big{(}(\mathcal{B}_{r_{h}(\cdot,\cdot)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](\cdot,\cdot)\Big{)}\in(\mathcal{F}^{N})^{k}_{h}$,
then by the definition of width function $w^{(1)}(\mathcal{F}^{k}_{h},s,a)$,
for $(k,h)\in[K]\times[H]$, we have

$\displaystyle{w^{(1)}(\mathcal{F}^{k}_{h},s,a)}$
$\displaystyle\geq\Big{|}\psi_{1}\Big{(}(\mathcal{B}_{r_{h}(s,a)})_{\\#}[\mathbb{P}_{h}\bar{\eta}_{h+1}^{k}](s,a)\Big{)}-(\tilde{f}^{k}_{h,\bar{\eta}})^{(1)}(s,a)\Big{|}$
$\displaystyle=\Big{|}r_{h}(s,a)+[\mathbb{P}_{h}V^{k}_{h+1}](s,a)-(\tilde{f}^{k}_{h,\bar{\eta}})^{(1)}(s,a)\Big{|}.$

Recall that $Q^{*}_{h}(\cdot,\cdot)\leq Q^{k}_{h}(\cdot,\cdot)$.

$\displaystyle\text{Reg}(K)$
$\displaystyle=\sum_{k=1}^{K}V_{1}^{\star}(s_{1}^{k})-V_{1}^{\pi^{k}}(s_{1}^{k})$
$\displaystyle{\leq}\sum_{k=1}^{K}V_{1}^{k}(s_{1}^{k})-V_{1}^{\pi^{k}}(s_{1}^{k})$
$\displaystyle=\sum_{k=1}^{K}Q_{1}^{k}(s_{1}^{k},a_{1}^{k})-Q_{1}^{\pi^{k}}(s_{1}^{k},a_{1}^{k})$
$\displaystyle=\sum_{k=1}^{K}Q_{1}^{k}(s_{1}^{k},a_{1}^{k})-(r_{1}(s_{1}^{k},a_{1}^{k})+[\mathbb{P}_{1}V_{2}^{k}](s_{1}^{k},a_{1}^{k}))+(r_{1}(s_{1}^{k},a_{1}^{k})+[\mathbb{P}_{1}V_{2}^{k}](s_{1}^{k},a_{1}^{k}))$
$\displaystyle\qquad-Q_{1}^{\pi^{k}}(s_{1}^{k},a_{1}^{k})$
$\displaystyle\leq\sum_{k=1}^{K}w^{(1)}((\mathcal{F}^{N})^{k}_{1},s_{1}^{k},a_{1}^{k}){+b^{k}_{1}(s_{1}^{k},a_{1}^{k})}+[\mathbb{P}_{1}(V_{2}^{k}-V_{2}^{\pi^{k}})](s_{1}^{k},a_{1}^{k})$
$\displaystyle\leq\sum_{k=1}^{K}w^{(1)}((\mathcal{F}^{N})^{k}_{1},s_{1}^{k},a_{1}^{k}){+b^{k}_{1}(s_{1}^{k},a_{1}^{k})}+(V_{2}^{k}(s_{2}^{k})-V_{2}^{\pi^{k}}(s_{2}^{k}))+\xi_{1}^{k}$
$\displaystyle\qquad\vdots$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}(w^{(1)}((\mathcal{F}^{N})^{k}_{h},s_{h}^{k},a_{h}^{k}){+b^{k}_{h}(s_{h}^{k},a_{h}^{k})}+\xi_{h}^{k})$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}(2b^{k}_{h}(s_{h}^{k},a_{h}^{k})+\xi_{h}^{k})$

∎

It remains to bound
$\sum_{k=1}^{K}\sum_{h=1}^{H}b^{k}_{h}(s^{k}_{h},a^{k}_{h})$, for which we
will exploit fact that $\mathcal{F}^{N}$ has bounded eluder dimension.

######  Lemma C.3.

If $b^{k}_{h}(s,a)\geq w^{(1)}((\mathcal{F}^{N})^{k}_{h},s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $k\in[K]$ where

$(\mathcal{F}^{N})^{k}_{h}=\\{f\in\mathcal{F}^{N}|\
\|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)\\},$

then

$\sum_{k=1}^{K}\sum_{h=1}^{H}\bm{1}\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}b^{k}_{h}(s^{k}_{h},a^{k}_{h})}>\epsilon\\}\leq\left(\frac{4\beta(\mathcal{F}^{N},\delta)}{\epsilon^{2}}+1\right)\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$

for some constant $c>0$.

###### Proof.

We first want to show that for any sequence
$\\{(s_{1},a_{1}),\ldots,(s_{\kappa},a_{\kappa})\\}\subseteq\mathcal{S}\times\mathcal{A}$,
there exists $j\in[\kappa]$ such that $(s_{j},a_{j})$ is $\epsilon$-dependent
on at least
$L=\lceil(\kappa-1)/\text{dim}_{E}(\mathcal{F}^{N},\epsilon)\rceil$ disjoint
subsequences in $\\{(s_{1},a_{1}),\ldots,(s_{j-1},a_{j-1})\\}$ with respect to
$\mathcal{F}^{N}$. We demonstrate this by using the following procedure. Start
with $L$ disjoint subsequences of
$\\{(s_{1},a_{1}),\ldots,(s_{j-1},a_{j-1})\\}$,
$\mathcal{B}_{1},\mathcal{B}_{2},\ldots,\mathcal{B}_{L}$, which are initially
empty. For each $j$, if $(s_{j},a_{j})$ is $\epsilon$-dependent on every
$\mathcal{B}_{1},\ldots,\mathcal{B}_{L}$, we achieve our goal so we stop the
process. Else, we choose $i\in[L]$ such that $(s_{j},a_{j})$ is
$\epsilon$-independent on $\mathcal{B}_{i}$ and update
$\mathcal{B}_{i}\leftarrow\mathcal{B}_{i}\cup\\{(s_{j},a_{j})\\}$,
$j\leftarrow j+1$. Since every element of $\mathcal{B}_{i}$ is
$\epsilon$-independent on its predecessors, $|\mathcal{B}_{i}|$ cannot get
bigger than $\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$ at any point in this
process. Therefore, the process stops at most step
$j=L\text{dim}_{E}(\mathcal{F}^{N},\epsilon)+1\leq\kappa$.

Now we want to show that if for some $j\in[\kappa]$ such that
$b^{k}_{h}(s_{j},a_{j})>\epsilon$, then $(s_{j},a_{j})$ is
$\epsilon$-dependent on at most $4\beta(\mathcal{F}^{N},\delta)/\epsilon^{2}$
disjoint subsequences in $\\{(s_{1},a_{1}),\ldots,(s_{j-1},a_{j-1})\\}$ with
respect to $\mathcal{F}^{N}$. If $b^{k}_{h}(s_{j},a_{j})>\epsilon$ and
$(s_{j},a_{j})$ is $\epsilon$-dependent on a subsequence of
$\\{(s^{\prime}_{1},a^{\prime}_{1}),\ldots,(s^{\prime}_{l},a^{\prime}_{l})\\}\subseteq\\{(s_{1},a_{1}),\ldots,(s_{\kappa},a_{\kappa})\\}$,
it implies that there exists $f,g\in\mathcal{F}^{N}$ with
$\|f-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)$
and
$\|g-\tilde{f}^{k}_{h,\bar{\eta}}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta(\mathcal{F}^{N},\delta)$
such that
$f^{(1)}(s^{\prime}_{t},a^{\prime}_{t})-g^{(1)}(s^{\prime}_{t},a^{\prime}_{t})\geq\epsilon$.
By triangle inequality, $\|f-g\|^{2}_{\mathcal{Z}^{k}_{h}}\leq
4\beta(\mathcal{F}^{N},\delta)$. On the other hand, if $(s_{j},a_{j})$ is
$\epsilon$-dependent on $L$ disjoint subsequences in
$\\{(s_{1},a_{1}),\ldots,(s_{\kappa},a_{\kappa})\\}$, then

$\displaystyle
4\beta(\mathcal{F}^{N},\delta)\geq\|f-g\|^{2}_{\mathcal{Z}^{k}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\geq\|f^{(1)}-g^{(1)}\|^{2}_{\mathcal{Z}^{k}}}\geq
L\epsilon^{2}$

resulting in $L\leq 4\beta(\mathcal{F}^{N},\delta)/\epsilon^{2}$. Therefore,
we have $(\kappa/\text{dim}_{E}(\mathcal{F}^{N},\epsilon))-1\leq
4\beta(\mathcal{F}^{N},\delta)/\epsilon^{2}$ which results in

$\kappa\leq\left(\frac{4\beta(\mathcal{F},\delta)}{\epsilon^{2}}+1\right)\text{dim}_{E}(\mathcal{F}^{N},\epsilon)$

∎

######  Lemma C.4 (Refined version of Lemma 10 in Wang et al. [50]).

If $b^{k}_{h}(s,a)\geq w^{(1)}((\mathcal{F}^{N})^{k}_{h},s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $k\in[K]$, then

$\sum_{k=1}^{K}\sum_{h=1}^{H}b^{k}_{h}(s^{k}_{h},a^{k}_{h})\leq
H\textnormal{dim}_{E}(\mathcal{F}^{N},1/T).$

###### Proof.

We first sort the sequence
$\\{b^{k}_{h}(s^{k}_{h},a^{k}_{h})\\}_{(k,h)\in[K]\times[H]}$ in a decreasing
order and denote it by $\\{e_{1},\ldots,e_{T}\\}(e_{1}\geq e_{2}\geq\dots\geq
e_{T})$. By Lemma C.3, for any constant $M>0$ and $e_{t}\geq 1/\sqrt{M}T$, we
have

$\displaystyle
t\leq\Big{(}\frac{4\beta(\mathcal{F}^{N},\delta)}{Me_{t}^{2}}+1\Big{)}\text{dim}_{E}(\mathcal{F}^{N},\sqrt{M}e_{t})\leq\Big{(}\frac{4\beta(\mathcal{F}^{N},\delta)}{Me_{t}^{2}}+1\Big{)}\text{dim}_{E}(\mathcal{F}^{N},1/T)$

which implies

$\displaystyle
e_{t}\leq\Big{(}\frac{t}{\text{dim}_{E}(\mathcal{F}^{N},1/T)}-1\Big{)}^{-1/2}\sqrt{\frac{4\beta(\mathcal{F}^{N},\delta)}{M}},$

for $t\geq\text{dim}_{E}(\mathcal{F}^{N},1/T)$. Since we have $e_{t}\leq H$,

$\displaystyle\sum_{t=1}^{T}e_{t}$
$\displaystyle=\sum_{t=1}^{T}e_{t}\bm{1}\\{e_{t}<1/\sqrt{M}T\\}+\sum_{t=1}^{T}e_{t}\bm{1}\\{e_{t}\geq
1/\sqrt{M}T,t<\text{dim}_{E}(\mathcal{F}^{N},1/T)\\}$
$\displaystyle\quad+\sum_{t=1}^{T}e_{t}\bm{1}\\{e_{t}\geq
1/\sqrt{M}T,t\geq\text{dim}_{E}(\mathcal{F}^{N},1/T)\\}$
$\displaystyle\leq\frac{1}{\sqrt{M}}+H\text{dim}_{E}(\mathcal{F}^{N},1/T)+\sum_{\text{dim}_{E}(\mathcal{F}^{N},1/T)\leq
t\leq
T}\Big{(}\frac{t}{\text{dim}_{E}(\mathcal{F}^{N},1/T)}-1\Big{)}^{-1/2}\sqrt{\frac{4\beta(\mathcal{F}^{N},\delta)}{M}}$
$\displaystyle\leq\frac{1}{\sqrt{M}}+H\text{dim}_{E}(\mathcal{F}^{N},1/T)+2\Big{(}{\frac{T}{\text{dim}_{E}(\mathcal{F}^{N},1/T)}-1}\Big{)}^{1/2}\text{dim}_{E}(\mathcal{F}^{N},1/T)\sqrt{\frac{4\beta(\mathcal{F}^{N},\delta)}{M}}$
$\displaystyle=\frac{1}{\sqrt{M}}+H\text{dim}_{E}(\mathcal{F}^{N},1/T)+\sqrt{16\cdot\text{dim}_{E}(\mathcal{F}^{N},1/T)\cdot
T\cdot\beta(\mathcal{F}^{N},\delta)/M}.$

Taking $M\rightarrow\infty$,

$\sum_{k=1}^{K}\sum_{h=1}^{H}b^{k}_{h}(s^{k}_{h},a^{k}_{h})\leq
H\text{dim}_{E}(\mathcal{F}^{N},1/T).$

∎

######  Theorem (6.5).

Under Assumption 4.8, with probability at least $1-\delta$, SF-LSVI achieves a
regret bound of

$\text{Reg}(K)\leq
2H\textnormal{dim}_{E}(\mathcal{F}^{N},1/T)+4H\sqrt{KH\log(2/\delta)}.$

###### Proof.

Recall that
$\xi_{h}^{k}=[\mathbb{P}_{h}(V^{k}_{h+1}-V^{\pi^{k}}_{h+1})](s^{k}_{h},a^{k}_{h})-(V^{k}_{h+1}(s^{k}_{h+1})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1}))$
is a martingale difference sequence where
$\mathbb{E}[\xi^{k}_{h}|\mathbb{F}^{k}_{h}]=0$ and $|\xi^{k}_{h}|\leq 2H$. By
Azuma-Hoeffding’s inequality, with probability at least $1-\delta/2$,

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\xi^{k}_{h}\leq
4H\sqrt{KH\log(2/\delta)}.$

Conditioning on the above event and Lemma C.4, we have

$\displaystyle\text{Reg}(K)$ $\displaystyle\leq
2\sum_{k=1}^{K}\sum_{h=1}^{H}b^{k}_{h}(s^{k}_{h},a^{k}_{h})+\sum_{k=1}^{K}\sum_{h=1}^{H}\xi^{k}_{h}$
$\displaystyle\leq
2H\text{dim}_{E}(\mathcal{F}^{N},1/T)+4H\sqrt{KH\log(2/\delta)}$

∎