Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Authors: Taehyun Cho
Seungyub Han
Seokhun Ju
Dohyeong Kim
Kyungjae Lee
Jungwoo Lee
Venue: ICML 2025 poster (2025)
Keywords: Distributional RL
Regret Minimization
Primary area: theory->reinforcement_learning_and_planning

Abstract: Distributional reinforcement learning improves performance by capturing environmental stochasticity, but a comprehensive theoretical understanding of its effectiveness remains elusive.
In addition, the intractable element of the infinite dimensionality of distributions has been overlooked.
In this paper, we present a regret analysis of 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 which is essential for exactly learnable and provably efficient distributional updates in an online manner.
Among all types of statistical functionals for representing infinite-dimensional return distributions, our theoretical results demonstrate that only moment functionals can exactly capture the statistical information.
Secondly, we propose a provably efficient algorithm, SF-LSVI, that achieves a tight 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.

Bellman Unbiasedness:
Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Taehyun Cho
Seungyub Han
Seokhun Ju
Dohyeong Kim
Kyungjae Lee² Jungwoo Lee!
Abstract
2019), neural response (Muller et al., 2024), stratospherie balloon navigation (Bellemare et al., 2020), algorithm dis- covery (Fawzi et al., 2022), and several game benchmarks (Bellemare et al., 2013; Machado et al., 2018). While the distributional approach offers richer information, two key theoretical challenges are introduced that distinguish from expectation-basee RL.
Distributional reinforcement learning improves performance by capturing environmental stochas- ticity, but a comprchensive theoretical understand- ing of its effectiveness remains elusive. In ad- dition, the intractable element of the infinite di- mensionality of distributions has been overlooked. In this paper, we present regret analysis of dis- tributional reinforcement learning with general value function approximation in a finite episodic Markov decision process setting. We first intro- duce key notion of Bellman unbiasedness which is essential for exactly learnable and provably ef- ficient distributional updates in an online manner. Among all types of statistical functionals for rep- resenting dimiite-dimensionall return distributions, our theoretical results demonstrate that only mo- ment functionals can exactly capture the statistical information. Secondly, we propose provably ef- ficient al algorithm, SF-LSVI, i, that achieves tight regret bound of (dg & V KK) where H is the horizon, K is the number of episodes, and dg the eluder dimension of a function class.
dinnsionii of distribution. In practice, dis- tributions contain an infinite amount of information, and we must resort approximations using finite number of parameters statistical functionals, such as categori- cal (Bellemare et al., 2017) and quantile representations (Dabney et al., 20) However, previous works often con- ducted analyses while overlooking these intractable nature of distributions. Additionally, not all statistical functionals can be exactly learned through the Bellman operator, as the meaning of statistical functionals not preserved after updates. For example, the median is not preserved under the Bellman updates, the median of mixture of two distributions does not equal the mixture of their medians. Thus, fundamental question arises:
"For a given statistical functional, does there exist a corresponding Bellman operator that ensures exactness?"
To formalize this issue, Rowland al. (2019) introduced Bellman closedness, which characterizes statistical function- als that can be exactly learned in the presence of corre- sponding Bellman operator.
Distributional reinforcement learning (DistRL) (Bellemare al., 2017; Rowland et al., 2019; Choi et al., 2019; Kim al., 2024) is advanced approach to reinforcement learn- ing (RL) that focuses 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 vari- ous risks (Chow et al., 2015; Son et al., 2021: Greenberg et al., 2022; Kim et al., 2023), particularly in complex real- world situations, such as robotic manipulation (Bodnar et al.,
Online distributional update. In this paper, we focus on developing an algorithm that efficiently explores from a regret minimization perspective while simultancously per- forming distributional Bellman updates in an online man- ner. One possible approach to addressing this problem to first update the policy using an existing provably effi- cient non-distributional RL algorithm and then estimate the distribution via additional rollouts. However, decou- pling these two processes introduces several drawbacks. First, adding extra rollouts solely for distribution estimation is
Seouul National University, Seoul, South Korea "Korea Uni- versity, Scoul, South Korea. Correspondence to: Kyungjac Lee <kyungjae_Iect Ice ac. Jungwoo Lee <junglec @ anu.ac.r>>.
and the limited number of rollouts inevitably introduce accumulated approximation errors in the estimated distribution throughout the learning process.
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
(General) Statistical Functional
Bellman Closed (Exactly Learnable)
Bellman Unbiased (Provable Efficiency)
Linear Statistical Functional
(A) max, min
z' exp 22
categorical (Rowland et al]
variance, skewness
(B) median, quantile
Figure 1. Venn-Diagram of Statistical Functional Classes. The diagram illustrates categories of statistical functional. (Yellow Blue) Within the linear statistical functional class, Rowland et al. (2019) showed that the only functionals satisfying Bellman closedness are moment functionals. (Red O Blue) We extend this concept by introducing the notion of Bellman unbiavedness, which only covers moment functionals but also includes central moment functionals from the broader class including nonlinear statistical functionals. (Yellow Blue") According to Lemmas 3.2 and 4.4 of Rowland al. (2019), categorical functionals are linear but not Bellman closed. (A) Maximum and minimum functionals are Bellman closed, while they are not unbiasedly estimatable. (B) Median and quantile functionals are neither Bellman closed nor unbiased, highlighting that they are not proper to encode the distribution terms of exactness. The proofs corresponding to each region are provided in Appendix C.
Moreover, the estimation is confined to the return distri- bution of the executed policy, making it difficult to reuse for estimating distributions under different policies, thereby moving further away from off-policyness.
defined in the literature (Wang et al., 2023; Chen et al., 2024) - and investigate the benefits of redesigning this con- cept using a collection of statistical functionals. Finally, we propose a provably efficient statistical functional RL algorithm with general value function approximation, called ES-I.
To overcome those two fundamental challenges inherent to DistRL, take closer look at the distributional Bellman update and revisit what additional properties of statistical functionals, beyond Bellman closedness, are required to construct online DistL algorithms that are not only exactly learnable but also provably efficient in terms of regret. In this context, we identify the following additional issues that arise when using statistical functionals for updates instead of the full distribution:
In summary, our main contributions as follows:
Introduce key property of Bellman unbiasedness for exactly learnable and provably efficient online distRL algorithm. We show that the moment functional is the unique structure in a class including nonlinear statisti- cal functionals.
Representing a mixture distribution with a finite, fixed number of parameters leads to approximation errors during the update. For example, when expressing the mixture of two distributions, each represented by N parameters, compressing 2/ into N parameters in the mixture results in inevitable information loss.
Describe the inherent intractability of infinite- dimensional distributions and analyze how hidden ap- proximation error prevents the design of provably ef- ficient algorithms. To address this, we revisit the ex- isting structural assumption of distributional Bellman Completeness through a statistical functional lens.
Due to the unknown nature of the transition P(-|s, a), the target distribution estimated by sampling the next state s'. Hence, the statistical functionals of the target distribution should be unbiasedly estimated using the statistical functionals from the sampled distribution.
Propose exactly learnable and provably efficient distRL algorithm called SE SF-LSVI, achieving a tight regret up- per bound Od 2 KK). Our framework yields tighter regret bound with weaker structural assump- tion compared to prior results in distRL
In this paper, we introduce a key concept, Bellman unbiased- ness, for precise information learnability of distribution from finite number of samples in online setting. As shown in Figure we prove that the moment functional remains the only solution in a class that includes nonlinear statistical functionals that satisfies both properties. We then discuss the inherent intractability of distributional Bellman completeness (distBC) - a structural assumption previously
1. Related Work
'We ignore poly-log terms in H, S, A, K in the Ō(-) notation. "In Chen et al. (2024). the regret bound is written as Öldg Too H H K), where Troc (p) represents the lipschitz con- stant of the risk measure p, i.c., lp(Z) p(Z')l S Txx( Fz Fz Ioo. Since Lox(p) (p) 2 H in risk-ncutral setting, we translate the regret bound into ( H²² /K).
2

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Table Comparison for different methods under distributional RI. framework. H represents subspace of infinite-dimensione space y To bound the eluder dimesion dg, Wang et al. (2023) and Chen et al. (2024) assumed the discretized reward MDP.
Finite
Exactly
Algorithm
Regret
Eluder dimension dy
Bellman Completeness
MDP assumption
Representation
Leamable
O-DISCO
((poly(dz/I)vK)
dimg(H,
distributional BC
discretized reward, small loss haund
x
x
(Wang al., 2023)
V-EST-LSR
discretized reward,
(Chen et al., 2024)
dimg(H,
distributional BC
lipschitz continuity
x
x
SF-L.VV
[Ours]
Öldg
dimg(
statistical Functional BC
none
Distributional RL.
In classical RL, the Bellman equation, which is based on expected returns, has a closed-form pression. However, it remains unclear whether any statistical functionals of return distribution always have their corre- sponding closed-for 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 Bz~a [ More recently, Marthe et al. (2023) proposed a general framework for distRL, where the agent plans to maximize its own utility functionals instead of expected return, formalizing this property as Bellman Op- timizability. They further demonstrated that in the undis- counted setting, the only Wi-continuous and linear Bellman optimizable statistical functionals are exponential utilities x log (exp
provably efficient RL algorithm with general value function approximation based on the eluder dimension dg (Russo & Van Roy, 2013) and achieves regret upper bound of (p Vk). To circumvent the intractability from computing the upper confidence bound, Ishfaq et al. (2021) 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 (Fei et al., 2021; Liang & Luo, 2022), CVaR (Bastani et al., 2022)), which align with our approach in that they are built on a distribu- tion framework. Liang & Luo (2022) achieved the regret upper bound of ((cxp(H)) / ((² and the lower bound of ((exp(H) ||| HK) in tabular setting.
expressions. Rowland et al. (2019)
In practice, C51 (Bellemare et al., 2017) and QR-DQN (Dabney et al., 2018b) are notable distributional RL. algo- rithms where the convergence guarantees of sampled-based algorithms are proved (Rowland et al., 2018; 2023). Dabney et al. (2018a) 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. (2023) highlighted the drawbacks of optimistic exploration in distRL, introducing a randomized exploration that per- turbs the distribution when the agent selects next action.
DistRL with General Value Function Approximation. Recently, only few efforts have aimed to bridge the gap between two fields. Wang et al. (2023) proposed distri- butional RL algorithm, O-DISCO, which enjoys small-loss bound by using ligeliiiddood objective. Similarly, Chen et al. (2024) provided a risk-sensitive RL framework with static lipschitz risk measure. While these studies analyze within a distributional framework, they do not address the in- space
tractability of implementation in of distributions. In contrast, our approach focuses on a statis- tical functional framework, providing detailed comparison with other distRI. methods shown in Table 1.
RL with General Value Function Approximation. Re- gret bounds have been studied for a long time in online RL, across various domains such as bandit (Lattimore & Szepesvári, 2020; Abbasi- Yadkori et al., 2011; Russo & Van Roy, 2013), tabular RL (Kakade, 2003; Auer et al., 2008; Osband & Van Roy, 2016; Osband et al., 2019: Jin et al., 2018), and linear function approximation (Jin al., 2020; Wang et al., 2019; Zanette et al., 2020). In recent years, deep RL has shown significant performance using deep neural networks as function approximators, and at- tempts have been made to analyze whether it is efficient in terms of general function approximation (Jin et al., 2021; Agarwal et al., 2023). Wang et al. (2020) established
2. Preliminaries
Episodic MDP. We consider a episodic Markov deci- sion process which is defined as a M = (S, P,r) characterized by state space S. action space A, horizon length H, transition kernels IP {I' hel and reward fru hee at step h [H] The agent interacts with the environment across K episodes. For each k E [K] and f E [H], H = (s], aj...., ,11, atp...,. st: at) repre- sents the history up to step h at episode k. We assume the reward is bounded by [o, 1] and the agent always transit to terminal state Send at step H + with rH+1 = 0.
3

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Eploy Twp(nn) 300
((T))
30
1 %
Vo
17
Illustrative representation of sketch-based Bellman updates for a mixture distribution. Instead of updating the distributions directly, each sampled distribution is embedded through sketch &b (e.g.. mean μs, quantile q.). The transformation by. aims to compress the mixture distribution into the same number of parameters, ensuring unbiasedness prevent information loss.
Figure 2.
Policy and Value Functions. A (deterministic) policy is collection of H functions {TT S + A] Given a pol- icy æ, a step h E [H)) and a state-action pair (s, a) E S x A, the Q and V-function are defined as (7, S x A +
sf and choose a policy x²_ In step h(E [H]), the agent observes (E S), takes an action a A) (-(+), receives a reward rı (s%, ag), and the environment transits to the next state sk 1/41 ~ PA (-I5, of).. Finally, we measure the suboptimality of an agent by its regret, which is the ac- cumulated difference between the ground truth optimal and the return received from the interaction. The regret after K episodes is defined as Reg(K) = =EK, (1*( (sf).
R) = Ex Σ# n' mh The aw)
8/ = 8, 02 = a and (T( S + R) = Ex E# The aw) 8/
Random Variables and Distributions. For sample space f2 we extend the definition of the Q-function into random variable and its distribution,
Distributional Bellman Optimality Equation. Recall that 7/ satisfies the following optimality equation:
Z% (s, Ax 2 R)
mi (s, a) = 1h
H
Th (sw, ax) 8h = 8, ag = a. aN = (ww
= (lea)a -x (
M=R
(Br, (Br,)((2) (Po7
7h (s, (:: S A (R)) = law (Z,
where B, : R + R is defined by Bx = r+ and 9#7 E T (R) is the pushforward of the distribution 1) through g (i.e., g (A) = nggg (A)) for any Borel set A C R).
Analogously, we extend the definition of V-function by introducing a bar notation.
T (s)(:: S 1x RR)
H Th (SN,, ) sh = =, = (sAr),
Additional Notations. For given N, we denote an dimensional function class FN = F(l), x... X.() S
{ f [f(), {()] S
A R Given dataset
Th (8)(: S - { = law (z)).
D = {(s), 42, [2]
PP| C S x AxAXR,, a set of state-action pairs Z ((s,,:))) c S and for a function f S x A + R. we define the norm
2
1=
Note that 7x = (+(( and (s) =
(s, (s)). We use n" to denote an optimal pol-
icy i.e. (+1s)
max, VT and de-
|| (0,)))),,l1//ll I|/lIllol.,. II II as written in Appendix A. For set of (vector-valued) functions J. C { S x A + R R, the width function of (s. is defined as to()) ; .s,)) = max (1()) - g(d) (s,a)) a)l-
note (s)(s) = V (s). (s,a)
Q a). a)) mH (s, a), and (s) TH (s). For no- tational simplicity, we denote the expectation over transition, [PAV (
= E (11.a) (h+) Bx ( and
TP [P (s). = E. (4 (s'). For brevity, we refer to 77th simply as n.
3. Statistical Functionals in Distributional RL
In this section, we define two key concepts in the distRL framework: the statistical functional and the sketch. We also illustrate Bellman closedness, a crucial property from Bellemare et al. (2023). Next, we introduce Bellman unbi- asedness, a novel concept that complements the previous property and is essential for provable efficiency. As shown in Figure 2, quantile functionals cannot be updated in an
In the episodic MDP, the agent aims to learn the optimal policy through a fixed number of interactions with the en- vironment across a number of episodes. At the beginning of each episode ke [K]), the agent starts the initial state
' "Note that Ey T (-l..)) (s') a mixture distribution.
4

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
unbiased manner (as proved in Theorem 3.3), demonstrat- ing that only certain sketches can be updated exactly. We then show that the only sketch satisfying both properties is the moment functional, which is unique among statis- tical functionals. Finally, we discuss the intractability of the previous structural assumption, distributional Bellman Completeness, and its tendency to cause linear regret. To address this, we introduce statistical functional Bellman Completeness, relaxed assumption, and explain why it satisfies both properties.
we extend this by showing that "nonlinear" statistical func- tionals, such maximum minimum, can also be Bellman closed. Additionally, while their proof implicitly treated quantiles as linear functionals, we provide a technical clar- ification in Appendix C.I where we formally demonstrate that no sketch Bellman operator exists for quantiles.
3.2. Bellman Unbiasedness
While the intractability caused by infinite-dimensionalty was addressed in Bellman closedness, another intractable element which has not yet fully tackled is the sampling of the next state. During the implementation, note that the agent does not have access to the transition kernel TP. In- stead, the agent can only access the empirical transition kernel P(-|s,a) a) E 1 rived from K sampled next states. This limitation implies that the operator should be treated as an empirical operator Ty. rather than To (i.e., (r) == (BB)) n (Pr))). There- fore, we naturally introduce new notion of Bellman unbi- asedness to unbiasedly estimate the expected distribution ( BP. [ss'), which is a mixture by transitions, from the sample distribution (B.))
3.1. Bellman Closedness
Definition 3.1 (Statistical functionals, Sketch; (Bellemare et al., 2023)). A statistical functional is mapping from probability distribution to real value sh: (R) + R.
s which is de-
A sketch is a vector-valued function $1.N P (R) +
RN specified by an N-tuple where each component is a statistical functional,
v)) (+), ... vn)()).
We denote the domain of sketch as P Pai (R) and its im- age as L = {f) fj E P V (.)). We further extend to state return distribution functions v =
Definition 3.4 (Bellman unbiasedness). A sketch (==
(VI:N((())) : =ES).
1I.N) is Bellman unbiased if a vector-valued estimator Φ = (v.()) . .b))) : (I + I exists where the (77(s))))))((( can be unbiasedly estimated by de using the &s sampled sketches from the sample distribution (B.)) i.e.
Definition 3.2 (Bellman closedness; (Rowland et al., 2019)). A sketch &INN is Bellman closed if there exists an operator TahiN 1 WIN + IS such that
sketch of expected distribution
[7('')
VILN
VIN (Tr) = TyLN VI.N (7) for all r E (R)S
EAE-P do xb ((((B)) .... (1....(((())))))))))))))) (1B.)
which is closed under a distributional Bellman operator T (R)S - (RR)..
k sampled sketehos from sample distribution T. (((())
((B.))
Bellman closedness is the property that a sketch are exactly learnable when updates are performed from the infinite- dimensional distribution space to the finie-dimeesional em- bedding space. While classical Bellman equation implies the existence of Bellman operator for expected values, not all statistical functional has such corresponding Bellman op- erator. Precisely, Rowland et al. (2019) 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 aoponential-polynonee functionals.
Bellman unbiasedness is another natural definition, simi- lar to Bellman closedness, which takes into account fi- nite number of samples for the transition. For example, mean-variance sketch is Bellman unbiased as the following unbiased estimator ((H.0?) exists for sample estimates:
(u,0²) = (((n02)) (101, of), ... (ūx, o
P. I (1 + k
k M
Theorem 3.3. Quantile functional cannot be Bellman closed under any additional sketch.
On the other hand, median functional is not Bellman unbi- ased since there is unbiased estimator for median. Then, the following question naturally arises;
While Rowland et al. (2019) focused on "linear" statistical functionals in defining sketch (i.e., (07) Ezz [h [ for some f),, leaving questions about nonlinear functionals,
"Which sketches are unbiasedly estimatable under the sketch-based Bellman update?"
'In discounted setting, a unique solution hecomes moments. We've overwritten it for convinience.
The following lemma answers this question.
5

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Tn
(TT))
"
>
Tn
(Tn)
(())
(n)
(1)
Ep Sp Tx
Sample nest state
Unbiasedly
ostimate
Figure 3. Bellman Closedness
Figure 4. Bellman Unbiasedness
Figure 5. Illustration of Bellman Closedness and Bellman Unbiasedness. The above path represents an ideal distributional Bellman update. Due to the infnite-dimensionalityy the update process should be represented by using a finitedimenniooal embedding (sketch) es. Since the transition kerne IP is unknown, the below path describes that the implementation should sample the next state and update by using To with the empirical transition kernel IP. A sketch to is Bellman unbiased if T. z can unbiasedly estimate ab o T through some transformation Sa. i... <T(T)) n) Ep(dg [W))).
Lemma 3.5. Let Fg be CDF of the probability distri- bution E Pv (BR). Then sketch is Bellman unbiased if and only if the sketch is homogeneous over (RR) of degree k, i.e., there exists some vector-valued function = =h(rI,". ,x,) x + RN such that "L01,""",,
median or quantiles inevitably involve approximation errors due to biased estimations.
Necessity of Bellman unbiasedness. Bellman unbiased- ness ensures that updates can be unbiasedly performed when only a finite number of sampled sketches are available. In other words, it guarantees that the sequence of sampled sketches forms a martingale, enabling the construction of confidence regions through concentration inequalities. This property is crucial for establishing provable efficiency in terms of regret minimization.
(ti) = 1..0--... x.)dFF()))))). dF
Lemma 3.5 states that in statistical functional dynamic pro- gramming, the unbiasedly estimatable embedding of a dis- tribution can only be structured in the form of functions that are homogeneous of finite degree (Halmos, 1946). To illustrate that homogenity defines a broader class than linear functionals, consider the variance as simple example. Vari- ance is clearly not a linear functional, as it is non-additive. However, it can be written as
Complementary roles of unbiasedness and closedness. At first glance, Bellman Unbiasedness (BU) may appear to be a stricter subset of Bellman Closedness (BC). How- ever, as illustrated in Figure 1, the relationship is more subtle: for example, the categorical sketch is BU but not BC, whereas functionals like the maximum or minimum are BC but not BU. More precisely, BU guarantees the existence of an unbiased estimator of the ground-truth sketch given finite number of sampled sketches. In contrast, BC plays complementary role by ensuring that the update process consistently provide such sketches. If sketch is BU but not BC-as in the case of the categorical sketch-ther thhnn the update process cannot continue providing new sampled sketches, making dynamic programming infeasible.
Var(1) ()) = Rz, ~ [Z EZ (2
72 + 2 = R2 Zz [MZ 2 -2, 7 27,
which implies the homogenity of degree 2. 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 exactly learned and unbiasedly estimated in a embedding space is the moment sketch.
3.3. Statistical Functional Bellman Completeness
Theorem 3.6. The only finite sketches that are both Bellman unbiased and closed are given by collections of th,,... N where its linear span \En= in On E 1R,VN N.VN } is equal to the linear span of the set of exponential polynomial func- tionals {n- + Ez~nl exp (XZ)]l [ 0, 1, ........ L, X E R), where v/ is the constant functional equal to 1.
We consider distributional reinforcement learning with gen- eral value function approximation (GVFA). For successful TD learning. GVFA framework for classical RI. commonly requires the assumption, Bellman Completeness, that after applying Bellman operator, the output lies in the function class J (Wang et al., 2020; Ayoub et al., 2020; Ishfaq et al., 2021). As a natural extension, our approach receives a tuple of function class JF { S x A + R as input to represent N moments of distribution. Building on this, we assume that for any îj S - ( H)), the sketch of target function lies in the function class J.N.
Compared Rowland al. (2019), we extend beyond linear statistical functionals to include nonlinear statistical func- tionals, showing the uniqueness of the moment functional. As shown in Figure 1, our theoretical results not only show that high-order central moments such as variance or skew- ness are exactly learnable and unbiasedly estimatable, but also reveal that other nonlinear statistical functionals like
Assumption 3.7 (Statistical Functional Bellman Complete- ness). For any distribution n : S - {(0, H)) and
6

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
[H]. there exists S E J.N which satisfies
4. SF-LSVI: Statistical Functional Least Square Value Iteration
[n(s,a) ((B,),
V(s,a) ES
In this section, we propose SF-LSVI for distRL frame- work with general value function approximation. Leverag- ing the result from Theorem 3.6, 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 (Shohat & Tamarkin, 1943; Schmüdgen et al., 2017). Unlike previous work (Wang et al., 2023; Chen et al., 2024) that estimates in infinte-dimmnniioall dis- tribution spaces, our method enables to estimate distribution unbiasedly in fiite-diienniionl embedding spaces with- out misspecification error. The pseudocode of SF-LSVI described in Appendix B.
DistBC inevitably leads to linear regret. In the seminal works, Wang et al. (2023) and Chen et al. (2024) assumed that the function class H C {m : S x A + ( H)) follows the distributional Bellman Completeness (distBC) assumption (i.e. if 1) E H for all h & [H], Th"1 & H)) This seems natural, but constructing a dinensiina subspace H that satisfies distBC is quite challenging. Since the distributional Bellman operator is composition of trans- lation and mixing distributions for the next state, it implies that function class H. must be closed under translation and mixture. However, when considering the representation of infinite-dimensionall distributions using a finite number of representations, it is not trivial that the mixture of distri- butions can also be represented with the same number of representations, For example, while Gaussian distribution can be represented using two parameters (H, o²), mixture of K Gaussians generally requires 2K representations.
Overview. At the beginning of episode & E [K], we main- tain all previous samples (6% 1% ) Ar) and initialize a sketch 1/1..v +1 (+)
O For each step h = H, ..... 1, we compute the normalized sample moments of target distribution {BBr,,) > (6)441)) with the help of binomial theorem,
To avoid the issue of closedness under mixture, both previ- ous studies assumed a discretized reward MDP where all outcomes of the return distribution are able to discretized into an uniform grid of finite points. Unfortunately. the approximation error introduced by the discretization is not negligible when it comes regret. This is because model misspecification, which is the error when the model fails to represent the target, typically leads to linear regret.
v/ (BBrz, (T = E[(ZZ k+
(0hr+1) + 17)
Hn-1
Σ Hd' the (mm(sh(4 (r%)))-nn
Ha-1
and iteratively solve the N-moment least square regression
Definition 3.8 (Model Misspecification in distBC). For a given distribution class H. which is the fmite-dimensional subspace of the space of all distribution Fox, we call the misspecification error
fh. + arg min
f()) (1F (p)
feT
Sn (Brz, + Th+h++((h++1))
== inf sup (lf((s,) a) - (Br.) (Pwn(((sss)))) FR (s,a)ESxA
based on the dataset Dj which contains the sketch of tem- poral target VIIN (B.g,/ ) 1 (8% Then we define
for any S + ((), and h E [H]
Q = min (fh,,) (() (.,-) (., H and choose the
Note that ( is strictly positive unless the function ap- proximator fn can represent any distribution in the finite- dimensional subspace 76 generated by translation and mix- ture. In a classical linear bandit setting (Zanette et al., 2020), a lower bound with misspecification error Ç is known to yield linear regret () Therefore, redefining Bellman Completeness within the didiite-dimmnsiinall distribution space is not appropriate, as it either imposes strong con- straints the MDP structure leads to linear regret. To circumvent model misspecification, we revisit the distribu- tional BC through the statistical functional lens. We propose a novel framework that matches a finite number of statistical functionals to the target, rather than the entire distribution itself.
greedy policy (+))) with respect to Q% Next, we update all
N normalized moments of Q-distribution dh1.N (7 (---)
and V -ddistribution VIIN (T))) We repeat the procedure until all the K episodes are completed.
5. Theoretical Analysis
In this section, we provide the theoretical guarantees for SF under Assumption 3.7. Applying proof tech- niques from Wang et al. (2020) and extending the result to a statistical functional lens, we generalize eluder dimension (Russo & Van Roy, 2013) to the vector-valued function, which has been widely used in RL. literatures (Ayoub et al.,
7

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
2020; Wang et al., 2020; Jin al., 2020) to measure the complexity of learning with the function approximators.
Due to the definition of Bellman unbiasedness, we re- mark that moment sketch has a corresponding vector-valued estimator Outua an identity and leads to a concentra- tion results as the sampled sketches forms martingale with respect to the filtration F induced by the history of {(5% d/)re(t- (Le., E. shi: (Brr) ( (((66))))))) [T%] 11 (Br,,) # (P 7 (1,, o5)).
Definition 5.1 (c-dependent, c-independent, Eluder dimen- sion for vector-valued function). Let c 2 0 and Z ((si, a=) 8 x A be sequence of state-action pairs.
A state-action pair (s, a) E S x A is e-dependent on 2 with respect to FN if Il gli 2 S é for any vector-valued function S.g E FN,, then [ (s) (s, a)l E.
Another notable aspect in Lemma 5.3 is using normalized moments E[ // instead of moments [E as it reduces the size of the confidence region from O(HN) to O(vN). This adjustment is akin to scaling the optimization function in multi-objective optimization to treat each ob- jective equally, which effectively prevents the model from favoring objectives with larger scales.
An (s, a) is e-independent on 2 with respect to J. if (s.a) a) is not e-dependent on Z.
The e-eluder dimension dimg(FFNe e) of a vector- valued function class FF is the length of the longest sequence of elements in S A such that, for some é' 2 every element is é' e'independeen on its predeces- sors.
Lemma 5.4 (Confidence Region), Let (FN = is JN |I|s Sh.n S B(FN, ,6); where
B(F", (FF",8)= 2 d' NH2 (log(T/8) (FT
We assume that the function class JFN and state-action space S x A have bounded covering numbers.
for some constant d' > O. Then with probubility at least 8/2, for all ki [R] x [H), we have
Assumption 5.2 (Covering number). For any c > 0, the following holds:
tin (P
E (F
there exists an e-cover C(JN, .c) C J. with size IC(FN, ol S N(FN c), such that for any g JN, there exists s' E C(FFN e)) with ||g - -y'llo,, S.
Lemma 5.4 guarantees that the sequence of moments from the target distribution 1h1.N (BBr...)) (P lies in the confidence region (J*) > with high probability, Sup- ported by the aforementioned lemma, can further guar- antee that all Q- f-ffucttion are optimistically estimated with high probability and derive our final result.
there exists an e-cover C(S e) with size IC(S x A, s NIS x A,e), such that for any (s,a) E S x A, there exists (s',a) E C(S x A, with max (f(s,a) - S(', a(d,a')
Theorem 5.5. Under Assumption 3.7, with probability at least 6, SF-LSVI achieves regret bound of
The following two lemmas give confidence bounds on the sum of the l2 norms of all normalized moments.
Reg(K)== < 2H ,1/T) + 4H V K 1og(1/8)
Lemma 5.3 (Single Step Optimization Error). Con- sider a fixed k E [K] and a fixed h E [A]. Let zk
show that SF-LSVI enjoys near-optimal regret bound of order H VK). which is VH better than the state-of-the- art distRL algorithm V-EST E-SS-LSSRR (Chen et al., 2024). For the linear MDP setting. we have dg = ((d) and thus SF LSVI achieves a tight regret bound as O(v@H H²K) which matches a lower bound O ((vdHH3)) (Zhou et al., 2021). In our analysis, we highlight two main technical novelties which significantly reduces the degree of regret in distRL framework:
Under weaker structural assumptions,
(s5, ()ttkk-111 and Di. { 1To. WINN (1 (+ rE(R-1) for any ;: + + (10, Define Fh.m arg min IIf For any ij and 8 E (0. there is an event E(n, K. such that conditioned on E(n,0), with probability at least - 5, for any of' [|bi.. - (f)loo)) I 1/T .we have
+ ((0, H)) with
[ JI.N (B.c.))
1. We refine previous lemma of Osband et al. (2019) and Wang et al. (2020) to remove the dependency of B(FN, 1/5) (See Appendix D.4), ensuring that regret bound depends only on the pre-defined function class, not on the number of moment extracted.
( NE ,1T))
for some constant c' 0.
8

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
2. As shown in Table 1, we define the eluder dimension dg in dimeesiommeniin embedding space FN, while other methods rely on an infinit--dimensional distribu- tion space H. C F
References
Abbasi-Yadkorts Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
6. Conclusions
Agarwal, A., Jin, Y., and Zhang, T. Vo q I: Towards optimal regret in model-free rl with nonlinear function approxima- tion. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
We describe the sources of approximation error inherent in distribution-based updates and introduce a pivotal con- cept of Bellman unbiasedness, which enables exactly learn the information of distribution. We also present provably efficient online distRL algorithm, SF-LSVI, with general value function approximation. Notably, our algorithm achieves a near-optimal regret bound of H V)), matching the tightest upper bound achieved by mon-nndiie distribsriba framework (Zhou et al., 2021; He et al., 2023). One interesting future direction would be to refor- mulate the definition of regret 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.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 413-44444444 PMLR, 2020.
Bastani, O., Ma, J. Y., Shen, E., and Xu, W. Regret bounds for risk-sensitive reinforcement learning. Ad- vances in Neural Information Processing Systems, 35: 36259-36269, 2022.
Acknowledgements
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.
This work is in part supported by the National Research Foundation of Korea (NRF, (B-20024-004514334400)) RS-
The arcade learning environment: An evaluation plat- form for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
2024-00413957(409)) Institute of Information & commu- nications Technology Planning & Evaluation (ITPP, RS- 2021-11210068(19)) 0021-0-00180(100)
grant funded by the Ministry of Science and ICT (MSIT), grant-in- aid of HANHWA SYSTEMS, Samsung Electronics Co., 0001022102022088700001, Institute of New Media and Com- munications(INMMAC) and the BK21 FOUR program of the Education and Research Program for Future ICT Samsung Electronics Co., 00010020222-0830000 Pioneers, Scoul National University in 2025.
Bellemare, M. G., Dabney, W., and Munos, R. A distribu- tional perspective on reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 449-458. PMLR, 2017.
Bellemare, M. G., Candido, S., Castro, P. S., Gong, J., Machado, M. C., Moitra, S., Ponda, S. S., and Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-888 2020.
Impact Statement
Bellemare, M. G., Dabney, W., and Rowland, M. Distribu- tional reinforcement learming. MIT Press, 2023.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bodnar, C., Li, A., Hausman, K., Pastor, P., and Kalakr- ishnan, M. Quantile qt-opt for risk-aware basedd robotic grasping. arXiv preprint 1000071910 2019.
Chen, Y., Zhang, X., Wang. S., and Huang, I.. Prov- able risk- distributional reinforcement learning with general function approximation. arXiv preprint urXiv:2402. 18159, 2024.
Cho, T., Han, S., Lee, H., Lee, K., and Lee, J. Pitfall of optimism: Distributional reinforcement learning by ran- domizing risk criterion. arXiv preprint 4rX1v:2310.1656, 2023.
9

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Choi, Y., Lee, K., and Oh, S. Distributional deep reinforce- ment learning with mixture of gaussians. In 2019 Inter- national conference robotics and automation (ICRA), pp. 9791-9797. IEEE, 2019.
Jin, C., Allen-Zhu, Z.., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances in neural infor- mation processing systems, 31, 2018.
Jin, C.. Yang. Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Chow, Y. Tamar, A., Mannor, S., and Pavone, M. Risk- sensitive and robust decision-making: evar optimization approach. Advances in neural information processing systems, 28, 2015.
Jin, C., Liu, Q. and Miryooseñi, S. Bellman eluder di- mension: New rich classes of rl problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:13406-1344 2021.
Dabney, W., Ostrovski, G., Silver, D., and Munos, R. Im- plicit quantile networks for distributional reinforcement learning. In International conference machine learn- ing. pp. 1096-0061000 100-1105 1105. PMLR, 2018a.
Kakade, S. M. On the sample complexity of reinforcement learning. University of London, University College Lon- don (United Kingdom), 2003.
Dabney, W., Rowland, M., Bellemare, M., and Munos, R. Distributional reinforcement learning with quantile re- gression. In Proceedings of the AAAI Conference Artificial Intelligence, 201 2018b.
Kim, D., Lee, K., and Oh, S. Trust region- baaeed safe distri- butional reinforcement learning for multiple constraints. In Thirty-seventh Conference Neural Information Pro- cessing Systems, 2023.
Dann, C., Jiang, N., Krishnamurthy, A., Agarwal, A., Lang- ford, J., and Schapire, with rich observations. Advances in neural information processing systems, 31, 2018.
On oracle-efficient pac rl
Kim, D., Lee, K., and Oh, S. Trust region-based safe distri- butional reinforcement learning for multiple constraints. Advances in neural information processing systems, 36, 2024.
Engert, M. Finite dimensional translation invariant sub- spaces, Pacific Journal of Mathematics, 32(2):333-343 1970.
Lattimore, and Szepesvári, Bandit algorithms. Cam- bridge University Press, 2020.
Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera- Paredes, B., Barekatain, M., Novikov, A., Ruiz, J., Schrittweserr J.. Swirszez, G., et Discovering faster matrix multiplication algorithms with reinforce- ment learning. Nature, 610(7930):47-53, 2022.
Liang, H. and Luo. Z.-Q. Bridging distributional and risk- sensitive reinforcement learning with provable regret bounds. arXiv preprint UrXiv:2210.14000 2022.
Fei, Y., Yang, Z., and Wang, Z. Risk-sensitive reinforce- ment learning with function approximation: A debiasing approach. In International Conference on Machine Learn- PMLR, 2021.
Machado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hauskmecht, M., and Bowling, M. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
ing, pp.
Greenberg, I., Chow, Y., Ghavamzadeh, M., and Mannor, S. Efficient risk-averse reinforcement learning. Advances in Neural Information Processing Systems, 35:32639- 32652, 2022.
Marthe, A., Garivier, A., and Vernade, C. Beyond aver- age return in markov decision processes. arXiv preprint arXiv:2310.2026 2023.
Halmos, P. R. The theory of unbiased estimation. The Annals of Mathematical Statisties, 17(1):34 43, 1946.
Muller, T. H., Butler, J. L., Veselic, S., Miranda, B., Wallis, J. D., Dayan, P., Behrens, F.,, Kurth-Nelson, Z., and Kennerley, S. W. Distributional reinforcement learning in prefrontal cortex. Nature Neuroscience, pp. 1-6, 2024.
He, J., Zhao, H., Zhou, D., and Gu, Q Nearly minimax optimal reinforcement learning for linear markov deci- sion processes. International Conference on Machine Learning, pp. 12790-12822. PMIR, 2023.
Osband, I. and Van Roy, B. On lower bounds for regret in reinforcement learning, arXiv preprint 1608. 2016.
Ishfaq, H., Cui, Q. Nguyen, V., Ayoub, A., Yang. 7., Wang, Z., Precup, D., and Yang, L. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pp. 4607-461 PMLR, 2021.
Osband, I., Van Roy, B., Russo, D. J., Wen, Z., et al. Deep exploration via randomized value functions. Mach. Learn. Res., 20(124): 1- -62, 2019.
10

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Rowland, M., Bellemare, M., Dabney, W., Munos, R., and Teh, Y. W. An analysis of categorical distributional re- inforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 29-37. PMLR, 2018.
Rowland, M., Dadashi, R., Kumar, S., Munos, R., Belle- mare, M. G., and Dabney, W. Statistics and samples in dis- tributional reinforcement learning. In International Con- ference on Machine Learning, pp. 5528-5536. PMLR, 2019.
Rowland, M., Munos, R., Azar, M. G., Tang. Y., Ostrovski, G., Harutyunyan, A., Tuyls, K., Bellemare, M. G., and Dabney, W. An analysis of quantile temporal-difference learning. arXiv preprint 3xX1:2331.00466: 2023.
Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Schmüdgen, K. et al. The moment problem, volume 9. Springer, 2017.
Shohat, J. A. and Tamarkin, D. The problem of moments.
Number 1. American Mathematical Soc., 1943.
Son, K., Kim, J., Yi, Y., and Shin, J. Disentangling sources of risk for distributional multi-agent reinforcement learn- ing. 2021.
Wang, K., Zhou, K., Wu, R., Kallus, N., and Sun, W. The benefits of being distributional: Small-loss bounds for reinforcement learning. arXiv preprint 230.:2305.1570. 2023.
Wang, R., Salakhutdinov, R. R., and Yang. L. Reinforce- ment learning with general value function approximation: Provably efficient approach via bounded eluder dimen- sion. Advances in Neural Information Processing Sys- tems, 33:6123-6133 2020.
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. Optimism in reinforcement learning with gener- alized linear function approximation. arXiv preprint vrXiv:1912.04 2019.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020.
Zhou, D., Gu, Q. and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576. PMLR, 2021.

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Appendix
A. Notation
Table 2. Table of notation
Notation
Description
S
stale of size S action space of size A horizon length of one episode
.4
I1
T
number of episodes
(a(s.
reward of (s, at step it
prohability transition of (s, a) to o'
Fg
history to step episode it
N
number of statistical functionals
(g,a,))
O-function of given policy
(7)))
V. f-fnntion given policy step ft random variable (Q-function random variable |'-function
2,, (s.0)
(x)
(6.0))
probability distribution Q-function prohubility distribution V-function
(5())
expectation transition [Fn(-)] Ex
(B-)
pushforward distribution through (x)))
didimensional vector
max norm f: R defined [ max.ex (x))
I norm
/ defined bx. im 2 max (x))
a function class of N-dimensioual embodding space
state-action pairs = ([A6 o:))
a dataset {(te, Gc. (4 11
For S x delime 1f Em (s
IIB
For f: x - deline I = Σn El ad) o.
M a.
width function of (s, a) defined as w " s,,) == max, max (s,)) gi
a solution of moment least squre regression, detined as Ri = argminge 1/1l
fv
a turget sketch of distribution fi, defined as f, > vI. ((8, (Pa)))
(FFM)
confidence region at step h, episode k, defined as (F*) y = 15 F 11 Pho l. B(EN,0)
statistical functional PR))) R
(1.(())
NV collleccioon of statistical functional S (B) BN8
Po.... (B)
domain of sketch sh..
Town
image of sketch thri
T
distribational Bellman operator, delined 7ij (B
sketch Bellman operator defined us Tusk(t) vt (18.) [P]]
To
empirical sketch
operator was detined as T,a0(77 e ba
NIFE .))
covering number of JNN wurt the e-ball
dimg(FNN (t)
eluder dimension F wrte
12

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
B. Pseudocode of SF-LSVI and Technical Remarks
Algorithm Statistical Functional Least Square Value Iteration (SF (LV
Input: failure prohability E (0, 1) and number episodes
1: for episode k = 1, ... do
2: Receive initial state =
3: Initialize 1i.,vv -1 < ON
4: for step h H. H 1,.... do
5:
D shy. a:., u1 w ( (..0)/1)11)
I/ Data collection
6:
fh + arg argmin Dl
Distribution Estimation
7:
( ) + (IFN) (b...))
() + min((Sh.g) ((0 ((.)) (c.)) + H)
8:
9:
(+)- = arg max.eA (%(;a)) (-) (1())
Optimistic planning
10:
1i (v/(..))) + -2)(1)), 1/2.N (v(((-)) + (min(((hss)) (m)) nER.NN
(1)()) ())()) d22.N (v)()) dh (11(, nE(2:N]
11:
12:
for h = 1,2, 1.2...... H. do
13:
Take action o (*)) Observe reward (5 a and get next state s
14:
Remark B.1. For an optimistic planning, we define the bonus function as the width function (s, a) = (FF(N)) )he s, a) where (J denotes a confidence region at step h, episode k. When F is linear function class, the width function can be evaluated by simply computing the maximal distance of weight vector. For a general function class F, computing the width function requires to solve a set-constrained optimization problem, which is known as NP-hard (Dann et al., 2018). However, a width function is computed simply for optimistic exploration, and approximation errors are known have a small effect on regret (Abbasi- Yadkori et al., 2011).
13

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
C. Related Work and Discussion
C.1. Technical Clarifications on Linearity Assumption Existing Results
Bellman Closedness and Linearity. Rowland et al. (2019) proved that quantile functional is not Bellman closed by providing 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 discounted MDP with initial state so with single action which transits to one of two terminal states 51, 82 with equal probability. Letting no reward at state 50, Uni 1J) at state 81, and Uni Unif(1/K, + 1/K]) at state $2, the return distribution at state So is computed as mixture _ 7 + Sonif(//K,) + K]) Then the 2K quantile at state S0 is k- They proposed a counterexample where each quantile distribution of state 81, 82 is represented
as K E d2 and K
Ex= دييعe respectively, the 2K quanttile of state so is Ueax
(1 Ex= k= d-2rー~ x
+ +8 0122+11
22
by However, this example does not consider that the mixture of quantiles is not quantile of the mixture distribution (i.e., Wy (>m + (1 - A)112 + (m)) + (1 (12)) 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. (2023) 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 Wi-continuous Bellman Optimizable statistical functionals are characterized by exponential utilities log /z~n/exp(>X2 [exp(XZ)) However, their proof requires some technical clarification regarding the assumption that such statistical functionals are linear.
To illustrate, they define statistical functional byy and consider two probability distributions m _ + 5n)) and
722 5a(a) where ((h) = f- f (2(((0) + f(h))) Using the translation property, they lead (by(n)) (12) to
[f((z) + f(x + h)) = f(x+ ((h) for all æ e R. However, this equality v (6 + dc+n)) (f(xx) f(x h))
holds only if y/y is linear, which is not necessarily valid assumption for all statistical functionals.
C.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 81, 82 is 7 + 7/K respectively. Beyond linearity, the maximum of return distribution at state so can be computed by taking the maximum of these values;
())))),(7((s1))) )) max(f7(22)) max(y, 7 + 7/K) = +
which produces the desired result. This implies the existence of a nonlinear sketch that is Bellman closed. More precisely, by defining max and min as the maximum and minimum of the sampled sketch a ((B)))+(ss)) with the distribution PP--ss, a), we can derive the sketch Bellman operator for maximum and minimum functionals follows;
Vence Uimax (7(s)) = mmxxx- -P(Iss,)) (mma ((B,),BB))))))) )(s))) = max, PP-IssP(( (r+ U'ax (f(s'))
-Toan (Vimin (T((s)) = miing=-((le.a) Mmin ((B,) minn.=((lss.)) r e'min (T(('))))
14

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
C.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 mixuure-onssisent,, which is the property that the sketch of mixture can be computed using only the sketch of the distribution of each component.
Definition C.1 (mixture-consistent)) A sketch e is mixture-consistent for any v E [0, 1] and any distributions 7/, 7/2 (R), there exists a corresponding function hy such that
(um (1 - v)m2)= ho (122).))
Next, we will provide some examples of determining whether sketch is mixture-consistent or not.
Example 1. Every moment exponential polynomial functional is mixture-consistent.
Proof. For any [N] and Ả C.
Bz-m=tl-umm? exp(AZ)]
exx((A) = zB 1 exp(A2)] + (1 D)E 10th exp(AZ))
Example Variance functional is not mixture-consistent.
Proof. Let v- and Y be the random variables where Z 1 _0 and Y 20z + 20x42. Then, Var(Z) Var(Y) While RHS is constant for any k, LHS is not constant for any ki i.e.
1 2h: + 5).
Var X
4
While variance functional is not mixture consistent by itself, it can be mixture consistent with another statistical functional, the mean.
Example Variance functional is mixture-consistent under mean functional.
Proof. Notice that mean functional is mixture-consssteett. We need to show that variance functional mixture-consistent under mean functional.
Var (1--mm+(1-1))p0))) (1- [Z]
Bzwem+((--v)), [72] -(E (R2zoon+(1-v)n) 12)2
-RZza (2-) - 13) [22] (uR.zam [7] + (1 Ry [2) = u(Varzmm [7] + (Ezzmy [2])2) + (1 v)( Varzzm [7] + (Ez 2
-(1Bzmm [Z] + (1 - 12)1Emmpp 2
This means that to determine whether is mixture-consistent or not, we should check it on per-sketch basis, rather than on a per-statistical functional basis.
15

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Example 4. Maximum and minimum functional are both mixture-consistent.
Proof.
max 2 Bwv (orm)+(1--pp))))
[Z]
max max [2], max (Z))
Zmm91
Z-112
and
min Zriiti (1-V))a
[
min min [Z], min [Z])
Z-m
Zi-12
Since maximum and minimum functionals are mixture consistent, we can construct nonlinear sketch bellman operator like the one in section C.2. This is possible because there a nonlinear function hg 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 median functional that is not mixture consistent.
Example Median sketch is not mixture-consistent.
Proof. Let v = 1 and Z, Y be the random variables where Z 0.266 0.861 and 0.630 + 0.48g for some 1.
Then Wimed = 1 and m/med 0. However,
med
z+x [X] Vined (0.46) + 0.28 + 0.401) k
which is dependent in k. Lemma C.2. Quantile sketch cannot be mixture-consistent, under any additional sketch.
Proof. For a given integer N > 0 and quantile level a E (0, 1), let 1/ and a random variable Y ~ Pyo + Pan dos + + Pux dgx (0 < ... < < 1) where Pyo > so that V'a-quanile [Y] = O. Consider another random variable ~ Pzg 5n + Pz, 51 where Pzo < a so that th Vu-quuntile [ = Then the a quantile of the mixture X Y+Z
)
Vo quantile [X] Un where min N
Pu., + P za.
>
='=UU
Letting Pso - - Py,, can manipulate qua-quaiile [X] to be any value of ya. Hence, qua-qinntle [X] is function
of all possible outcomes of Y.
If there exists finite number of statistical functionals which make quantile sketch mixture then such sketch would uniquely determine the distribution for any N. This results in contradiction that infinite-dimensional distribution space can be represented by a finite number of statistical functional.
Lemma C.3. If sketch vp is Bellman closed, then is mixture-consistemt.
Proof. Consider an MDP where initial state has no reward and transits to two state $1, with probability v, - v and reward distribution fn,, 72. Since vi is Bellman closed, ((((s))) is function of ()(((1))) and v)))(22)), (i.e., (7(())) (*)((()))), ((f((s))) for some go). Since (7((s)) = (Vvū(s1) + (1 v) 82)). it implics that tb is mixture- consistent.
Combining the results of Lemma C.2 and Lemma C.3, we prove that quantile sketch cannot be Bellman closed, no matter what additional sketches are provided.
16

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
D. Proof
Theorem (3.3). Quantile functional cannot be Bellman closed under any additional sketch.
Proof. See Lemma C.2 and Lemma C.3.
Lemma (3.5). Let F2 be a CDF of the probability distribution rj E (R) Then a sketch is Bellman unbiased if and only the sketch is homogeneous of degree k; i.e., there exists some vector-valued function h h( ,Kk) X - R such that
4 : -....MM MOL. " (x)d ... (F)(
Proof. (=) Consider an two-stage MDP with a single action a, and an initial state so which transits to one of terminal state {81, :.. , 88) with transition kernel P(-|sg, a). Assume that the reward r(so) Then 77(s)) ΣX P(sk))r(s))> Note are independent and identically distributed random variable in distribution P(-|s,a).
that 51, -- , s/
Eg ( ( ((BB)))7(6))) - ((B.) = when ((Br)) B (1 2b (Bo)
Bxr-(()oo (ou (u(6ro1)). (006))))....000000
(0((112)) ]]
Exrwe(loona) .. (1 -0(6))))))))))) v (7(s0))
S (k))""")))ddF((),) dFy(s')) = vs ((7(s0))
(=)
*( (B (008))4100
=f... "...
/ /..fsloo M(01
MMa + i + E Foor) d(BBrwr(loo F((o)(2)))
Es [f .....b f... h(a1+ tr, a + dl ( dFF)))((a)) (.)))))))))))))))))
Theorem (3.6). The only finite statistical functionals that are Bellman unbiased and closed are given by the collections of 4/,, ..,...., vi where its linear span {Σ ai 4n Cr E R. VN} is equal to the set of exponential polynomial functionals {11 + E Ez Z exp (XZ)]] 0, 1,..., L X E R), where tho is the constant functional equal 1. In discount setting, it is equal the linear span of the set of moment functionals {1 Ez [z']] [ 0, O,,....,II L} for some L < N.
Proof. Our proof is mainly based on the proof techniques of Rowland et al. (2019) and we describe in an extended form. Since their proof also considers the discounted setting, we will define (x) = + yer for discount factor E [0, 1). By assumption of Bellman closedness, thn (Br.)) will be written as g(r, 7, VI.. (7(s') for some g. By assumption of Bellman unbiasedness and Lemma 3.5, both 1i. (77(s)) and vin (BB.)) are affine as functions of the distribution
17

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
7(s'),
(1-
(22-om(6))((-)))mm [b1:N| (71,' .... , ,7x)] -aRgmm (b (Z1, kx) + (1 - -a) ;,,)
and
en (Brr) (an (s') (1-a))=)))
(0))
+ 1211. " 7Zx)
aB - (n + r 2xx1 + (1 - ax) annin (B 77) (6)) + +(1 a1-a) #+
Mal( + 2a)
-2,,... ..,..,,. 72,)
Therefore, g(r, 7) also affine on the convex codomain of dI... Thus, we have
E Ez Po + 7/,, 77x]] (r(r)))
Σ n'=1
an (r, (Z1, 2x)
for some function CD:N
R x [0, + R. By taking r7(') = Sg, we obtain
Ova (r -0, + yx) ao(r, ?) +
Σ
and ()) (z..... ,.).
According to Engert (1970), for any translation invariant finite-dimensional space is spanned by a set of function of the form
{ar - ot exp(Ax=)1 (J,,OSIs]]
for some finite subset {AI,... } of C. Hence, each function :: + 2e. (x..... ,.) is expressed as linear combination of exponential polynomial functions. In addition, the linear combination of Φv. should be closed under composition with for any discount factor 7 E [0, 1], X, should be zero. Hence, the linear combination of d , Ppr must be equal the span of {a 2'1 S L} for some L N.
Lemma (5.3). Consider a fixed &o E [K] and a fixed h E [H]. Let 2 = {(8) a xx) and D ( )+(((+++)))))))
rE]k-1] for any S + p ([0, HJ). Define fh, arg min |1 For any 7 and E (0, 1), there is an event E(7, 8) such that conditioned on E(j, 8). with probability at least 1 - 8, for any क/ S + ([0, H)) with (1') vi.N (7) /olc.1 I 1/T or Σn (7') - on ( 1/T, we have
{0% Tho shao (8%
[.-)) - VIN (BBr()))
( (PT((.))) 2t
sd [ (N+ log(1/0) log 1/T)
for some constant <'> 0.
Proof. Define the sketch of target fn : A - N
fa(:,) = VIN (BB, (P))(;)))
for all E [N].
18

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
For any / F.
Ilfwrllox lios h.
h,
N
(sh 07) - Un ((B:z) (()+))))((h)+)) (oh+1))) (fin)ssh: - tin ((B:))) (f# (sh
m=1
N
Σ
(f11 - p(x)) (sh+ ( a7,))
0h) )(() (sh, ahl) (117" ( ax) - inn (1B7))
+
2 1 - foy 12
(1 - 11 (H + 1)|2%1
Σ Σ
2(F(1) aht - 1/th'(( (sh aml) (5h an) Un ((B+)))((H++2))
n=1
27 TT E2 h..g'
h.
xx(r(m))
2 I - f -
Σ
Σ
xT(F(m))
==1 E h.R!
For the first inequality, we change the second term from n/' to n which are the e-covers. Notice that AC - BC 2 -IAC - BC'| 2 -I - B)C - a(A - BBC 2 -2|A Bl| max(C, C")].
(sh, ah) - -1²² (sh, alT)) (1 (sh, ah) - uinn ((Brz) 7 (sh+t)))
(sh, ahh) - ((m) (sh. ahl) (1( (1 (8) - -/ (B,3g -Va((1 ((((sh+)))))
2 211 (sh aP)) f/ (5%, am)l
x max (sh- (5h ah) - -/ (Brr)) (BBr))*T(((++)) 157) a77) - un (BBr))
2 (0) - pp (h)) 1)
For the second inequality, consider 7/' : (00, H)) with E 11 (7) S $1/T. We have
| (m)
p(n) 1
1lcc
max
Σ
Hn (PPr) a)) - s/. ([)7"'(s,))))""">> H
s,
n'=1
< Σ
- (o. vx
max
n==1
< 1/T.
Defining F as the filtration induced by the sequence ((%,, (.) ((stt (ff (st), at).......... ..., (s), af)), notice
19

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
that
N
E
xhe (m)
1%
2(f(m)) (0%, 1/ (5% (s)%))a)))) (5)
(5) - -b(0 ((Brz) # ((5((11)))))) |
==1
Σ (m) 07) (0 ( (5) (e Mn (Brr (1 (
(6h. - Un W (e Penceaa (((( 2(5(m) (8) - 107 ())) (6h
=0
and
N
Σ x
Σ (sT (h) 1/ (5%,)))))) (A (5) (5) U/ 7(h
N
s max <
{ (m) (8% (7)) Ain (B.
(B.;))# ) 7+
p(m)
(5h: (1m) a5) (8%
< 2(H + 1)
Σ
((m) (s7 o/)) 11th (sh.
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 commutable with mixing operation, the transformation ov. in Definition 3.4 is identity for all [N]. Hence, we choose the sketch moment which already knows dv.
By Hoeffdig inequality.
2
P
Σ
Σ
2 E < eexp
(T.A)E(k- l| [ n=1
2(2(H + 1))²
EN [f(n)
s2/11)
2²
< 2exp
2(2(H + 1))² [Ix[[[]
NNN 1f(n) - 11
2
eexp
2N + 1)) 1)) f2
where the second inequality follows from the Cauchy-Schwartz inequality.
We set
N(FN ((FN,1/T)
c=
- SN(H + 1)2ll.f
fa fall2; log
8
With union bound for all f E C(FN 1/T), with probability least 1 1- 5,
N
NNFN, 1/T)
Σ
Σ ( SeNt + 1)11 s7ll28 log
5
(r. [M] n=1
for some constant d' 0.
20

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
For all f JRN, there exists g C(FN, ,I/T), such that || glloc,1 S 1/77 Σ [N]
[|
100
1/T for all
Σ Σ [ n=1
Σ
+ +2(H + 1)12%
1
T
(r,))(k--)) [ ==1
==1
NN(FN,1/T)
c (H + 1)llg - full2x V log
+ +2N +1)
(((TV.1/TT))
C + +I](If s1llz + 1) log
+ + +
(N(FN, (((F),1/TT)
S <dN + 1)lIff fallzz + +2) +2) log
+ 22 +1)
8
where the third inequality follows from,
|/ 1 21l S
Σ
(8h, (5 a7)1
n=1
2
2 NT
T
1
Recall that Ph.yy arg min [1 "
We have 11 Pyy
11 11 i S 0, which implies,
2 I1
De. h.:0
11 11by
fri 122x
2 Σ
Σ
ah) (m0 (7) 14 / (f)) (1) (5h. t/a (Brrz)# (8h+2))))
(T, [|x[
2 11 f 1222
d' (H + 1) fzl1 + 2) log(2/8) WON 1/T) 6N 1).
Recall that if x²2 - 2ax b S 0 holds for constant a,b> 0, then <a Va + b d' for some constant d' > 0.
Hence,
I1 - J S SC(N2 1og((1/8) + logNNNN,11 1/T))
for some constant c' > O.
Lemma (5.4). Let (FN = (FEFNIIS 1i,5112 $ BB(FN where
B(FN, .8) 2 d' 2 (T + log 1og.((FM,1/T))
for some constant c' > 0. Then with probability at least 1 8/2,, for all h [K] x [H) we have
vnn
E )F
Proof. For all (k, h) E [K] x [H].
min(f()(,)) + 01+1())), SEC(FN ( }/m]ufo) (in() H3) SEC(FN, 1/T) u()
ufo} n=1
S
2 2<n5N
21

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
(1/T)-cover of 11.N (1 where
m (())) + 0 ()+) min min((Sh 1( (..),
1 and h H
VE ( ()))) =
2 - n2 S N and < H h H
i.e. there exists (v) E S such that (1)) -IN- S 1/T. This implies
s = piin (p(. arg max vi 1 (((()))))) (1) Es}
aEA
is a (o/Ter of 11 (7h+1) with log([S)) S log. 1/T).
For each (1) E S, let (f) 8/2 be the event defined in Lemma 5.3. By union bound for all 4/1. (7) E S, we have Pr[ mest (7), (f7.6/2/S)T) 2 6/2T.
Let (7)) S such that || (7) VIN (1h S 1/T. Conditioned on (ss (72,5/2 and by Lemma 5.3, we have
[h.n((--) Vn (BBr (Path (Fon::)))) S (
for constant d' 0.
By union bound for all hk E [K] we have diIN (Ben)ts)))
(P (Pahh))l()))) (FN) with probability 1-8/2.
Lemma D.1. Ler (s) min(H, fh a) + (s, a)} for some bonus function (s, a) all (s.o) 8 A. If (s, 2 ((F s,a, then with probability at least 1 - 8/2,
(s) s Qh and vs) S (s)
(FN)) By Lemma 5.4, Pr|E| 2 1 1 8/2.. In the rest of the proof, we condition on E. for all hk E [K] for all (s, a) E S A.
Proof. We use induction l from h H to 1 to prove the statement. Let & be the event that for (k, h) E [K] [M]. V1.N (B
When h = H + 1, the desired inequality holds (1441 a) = VH+1 (s) = Q (s, a) = V (s) = 0. Now, assume that (s, a) s (s) and (s) z Vi+ (s) for some h [H]. Then, for all (s, E S x A
(7 (H, [PAV 1 (s)
< (in( + [Fx [1
(s. (
@i - (x, + w (F
()(ss
Lemma D.2 (Regret decomposition). With probability at least 1 8/4, have
K
Reg(K)- Σ
26 (s at) + th)
where t [P h+1 V at) (Vi+t (5 Vital (sh is martingale difference sequence with respect
to the filtration F induced by the history TH
22

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Proof. We condition the above event & in the rest of the proof. For all (k E [K] [H], we have
( - -iiNN ((Br (Pwhhhtt || S <B(F",0)
Recall that (F = If E JN If P & B(FM,6)) is the confidence region. Since
VI.N we have
E (F then by the definition of width function (F,, s, for (k, h) E [K] x [H],
w w 8, 2 | ((Bntsa))llBhhhnnllssss.. - (s, = as + [Pa (PaV - (Ph.n)) (s,
Recall that Q7(s)) S (.())))
K
Reg(K) = Σ (i+(st) - 1/r"(0 (st)
K
(xt) - (st) (xf)
at) Qi" (s),a1)
K
Σ @f at) - (ri(st. + +
+ (mi(st.at) + (31 at))
oi (st. at)
w ((F +)) [Pi( - V att
+
w
(s5)) E
K H
w ( st oh)+b/(st. at) + +
k= h=1
H1
Σ
(2 (5 ( + +%
k=1
It remains to bound Σk= Emt 1/(sst at), for which we will exploit fact that JNN has bounded eluder dimension.
Lemma D.3. (s) 2 (( //x s, a) for all (s) E S x A and Ks E [K] where
(F ソo. = Lf E 1 12, S B(FN, ,0)}
then
(AS(FM.)) .5)
+1) dim (FN, e)
x²
for some constant e > 0.
23

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Proof. We first want show that for any sequence (1)1, (&x ax)} C S x A, there exists j E [x] such that (g) is e-dependent on at least I, [(r: 1)d c)] disjoint subsequences in (1s1,a1),.... 1.a......,-_j11. (8j-1, with respect to FN. We demonstrate this by using the following procedure. Start with L disjoint subsequences of (1),,a)...... (53-1.0)-1); B1, ....... Br. which are initially empty. For each j, if (sy, az) is e-dependent on every B BL. we achieve our goal so we stop the process. Else, we choose i E [r.] such that (*j. uz) is e-independent on B; and update B; + B, u ((s;, az)}. j t jj+L 1. Since every element of B; is e-independent on its predecessors, [B; cannot get bigger than di (JN e) at any point this process. Therefore, the process stops at most step j = Ldimx e) + S K.
Now we want show that if for some j E [n] such that bf (s); a,) > e, then (s), a,) is e-dependent on most 4,(FF 8)/e²
disjoint subsequences in {s1, a1).... (85-1, a)=1) with respect to FN If by, ($j. az) and (sj. (z) is c-dependent
on subsequence of {(11 {(1),a)), ...., (6/, 4)} C ((11,11)..... (sx,0n)) an)). ). it implies that there exists f.g E J.N with || - fh zt S BBFN, .6) and llg fh,, 2 S B(FN, .6) such that (5), (5), af) 2 c. By triangle inequality, |l gll 2 S 4B(FN, .6) On the other hand, if (sj, az) is e-dependent on disjoint subsequences in {(51, (1),,.)..... (5x: an) then
48(FN 6) 2 llf 911222 (1)()) - 9/0 2 LE
resulting in L.S. 48(FN 50)62. Therefore, we have (#/dime(FN, ,c) 15 4B(FN ,5)/2 which results in
(3(F.8) 8)
2 +1 dim=(FF .))
K S
Lemma D.4 (Refined version of Lemma 10 in Wang et al. (2020)). 1f (s.a) a) 2 w( for all (s, a) E ES x A and k E [K]. then
Mhis at) S Hddim(FF,, 1/T).
1=11=1
Proof. We first sort the sequence (b at)) (..)). in decreasing order and denote it by eT](e 2 2 eT). By Lemma D.3, for any constant M > and e, 2 1/VMT, we have
t 5 (B((FN.)) .5)
(48(FN,)) 8)
+ +1) dFN MMe) <
1) dime ,1/T)
Met
Mea
which implies
t (FN,1/T) -1)
11/2
43(FN
e S diN 11/2)
M
fort 2 dim 1/T).
Since we have e S H,
T ed 2 1/V (FM,((F,,1T)))
Σ
elffe <1/\MT) +
=
(=1
1=1
Σ e fer 2 1/VMT,12 dim (F" (FN,1)))
+
<
+ Hdim (FN 1/T)+
Σ
dimg(FN, 1/T) -1)
1
-1/2 /
/A8(JN .))
VM
M
dimg 1/T)SIST
dim 1/T) -1) 1/2
43(FN,
<
+ Hdim (N 1/T) +2
dime(FN, .1/T)
VM
M
+ Hdim (FN 1/T) + v 16 (iidimggFF.. 1/T) T 18/M.
VM
24

---

Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
Taking M - oc,
Mo ah) S Hdimm(F", ,1/T).
Theorem (5.5). Under Assumption 3.7, with probability at least 1 - 8, SF-LSVI achieves regret bound of Reg(K)= - 22Hdimg(F 1/T) 4H KH log(2/))
Proof. Recall that <x [PA h+1 1l
o (1 ( is a martingale difference sequence
where [[ = and |eX1 < 2H. By Azuma-Hoeffding 's inequality, with probability at least - -5/2.
4H KH (2/6)/))
KH
h=1
Conditioning on the above event and Lemma D.4, we have
K
K
Reg( K) < 2
h=1
1= h=1
x 2Hdimg(FN 1/TT) + 4H AH loggg2/
25


Reviews:
[{"review_id": "huadAcwLQD", "reviewer": "Reviewer_fMkS", "summary": "The paper proposes a distributional RL algorithm in the finite horizon episodic MDP setting. They propose bellman unbiasedness, a notion complementary to bellman closeness in prior work. They analyze the regret bound of the algorithm and compare against prior work in the space, showcasing theoretical improvements.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and effort in reviewing our paper. We have organized our responses to your comments below. If any of our reconstructed responses miss the intent of your questions or if there are remaining concerns, please let us know so we can address them.\n\n-------\n### 1. Concrete examples of statistical functionals\n\nIn our paper, we indicated in Figure 1 that max and min are Bellman closed but not unbiased statistical functionals, and the proof for this is provided in Appendix C.2. To make it easier to follow, we will add a note in the main text stating that 'the proof is included in the appendix.' For the categorical sketch, since  Lemma 4.4 of [Rowland et al 2019] proves that it is not Bellman closed, we did not include a separate proof. We will update Figure 1 in the main text to include a reference to their proven result.\n\n\n-----\n### 2. Bellman unbiasedness vs Closedness\n\nFirst, Theorem 4.3 from [Rowland et al 2019] states:\n\n> The only finite sets of statistics of the form $s(\\mu)=\\mathbb{E}_{Z\\sim\\mu}[h(Z)]$ that are Bellman closed are ...\n> \n\nIn other words, they provide theoretical results for sets of \"linear\" statistical functionals that satisfy Bellman closedness. Since max and min are non-linear statistical functionals that fall outside the scope of their theory, we cannot determine whether they are Bellman closed. \n\nSimilarly, since variance is nonlinear, we cannot determine its Bellman closedness using their results. However, since we already know that first and second moments are Bellman closed, we can naturally derive that variance is Bellman closed. Therefore, this indicates that their theory does not sufficiently cover various commonly used statistical functionals. Keeping this in mind and comparing with Rowland's theory, our theory can be interpreted as a generalized result that is helpful to test Bellman closedness for a broader category of unbiasedly estimatable statistical functionals.\n\nAlthough the second question falls outside the scope of our paper, it raises important points to address by breaking it into two parts. \n\n> \"For a given transition kernel, does a nonlinear Bellman closed sketch always have a fixed point?\" \n\nSince Lemma 3 in [Bellemare et al 2017] proves that the distributional update is a contraction, we can see that statistical functionals with bounded values also converge to a fixed point.\n\n> \"In sample-based updates without a given transition kernel, does a nonlinear Bellman closed sketch always have a fixed point?\"\n\nOur paper proves convergence for Bellman unbiased sketches in a scenario with \"only finite sampling allowed without a given transition kernel,\" but does not examine convergence for other Bellman closed sketches. Since max and min are Bellman closed but nonlinear, we cannot use existing linearity-based contraction proofs. A separate proof approach would be needed, making this an interesting direction for future work.\n\n-----\n### 3. Translating results to discount case\n\nWhile regret analysis for the infinite horizon discounted case falls outside the scope of our current paper, we believe it presents an interesting problem. In our results, when performing $N$ sketch-based updates, there is no additional cost beyond the confidence region increasing by a factor of $\\sqrt{N}$, so we expect that in the discount case, there would also be an additional factor of $\\sqrt{N}$ involved.\n\n----\n### 4. Lack of empirical validation\n\nWhile we acknowledge the importance of experimental results, our paper aims to theoretically connect two fields - distRL and General Value Function Approximation (GVFA) - so our main contribution lies in establishing theoretical foundations and broadening understanding. We kindly request that you consider this in your evaluation, as many GVFA papers with similar objectives [Jin et al 2021, Li et al 2024] also do not necessarily include experimental validation.\n\n\n\n----\n### References\n\n- [Rowland et al 2019] : Rowland, Mark, et al. \"Statistics and samples in distributional reinforcement learning.\" *International Conference on Machine Learning*. PMLR, 2019.\n- [Bellemare et al 2017] : Bellemare, Marc G., Will Dabney, and Rémi Munos. \"A distributional perspective on reinforcement learning.\" *International conference on machine learning*. PMLR, 2017.\n- [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\" *Advances in neural information processing systems* 34 (2021): 13406-13418.\n- [Li et al 2024 ] : Li, Yunfan, and Lin Yang. \"On the model-misspecification in reinforcement learning.\" *International Conference on Artificial Intelligence and Statistics*. PMLR, 2024.", "claims_and_evidence": "The theoretical claims made in the paper are fairly clear and backed up by proof.", "methods_and_evaluation_criteria": "There is no empirical evaluation of the theoretical results in this work, which arguably is a place for improving the current paper.", "theoretical_claims": "I have skimmed through certain theoretical arguments in the paper and they generally are sensible to me.", "experimental_designs_or_analyses": "No empirical designs.", "relation_to_broader_scientific_literature": "The paper is generally related to distributional RL and theoretical RL on regret bound for learning efficiency.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is fairly solidly grounded in theoretical discussions and it has made solid theoretical contributions connecting the learning efficiency of distributional RL as measured in regret. I think the paper can use a bit more improvement in presenting concrete examples of statistical functionals to make the results more accessible to algorithmic minded readers and add a section for empirical evaluation.", "other_comments_or_suggestions": "NA", "questions_for_authors": "=== *concrete examples of statistical functionals* ===\n\nI think the paper will be made more accessible to readers less versed in theoretical discussions, to provide a bit more concrete examples on statistical functionals that fall into different categories. For example, in the appendix maybe discuss why max and min functionals are bellman closed (it is easier to see why they cannot be estimated in an unbiased way) and why categorical functionals are not bellman closed.\n\n=== *bellman unbiasedness vs. closeness* ===\n\nI would love to understand better the contribution this work makes in relation to results in Rowland et al 2019. Rowland showed that the only finite bellman closed statistical functions are spanned by finite moments, where as in here the illustration shows that min and max functionals are also bellman closed?\n\nOne implication of bellman closeness is that the statistical functionals can be learned via a recursive bellman backup, does that mean in principle max and min statistical functionals can also be obtained by bellman backup and computed as a fixed point for dynamic programming (though not computable in finite samples due to the lack of unbiasedness).\n\n=== *translating results to discount case* ===\n\nThe discussions are limited to finite horizon episodic MDP - I wonder what happens if we consider infinite horizon discounted MDP with discount $\\gamma$, how should we translate the regret bound in table 1 as a function of $\\gamma$ or is this feasible at all? \n\n=== *empirical validation* ===\n\nI think the paper will benefit greatly from even a simple empirical validation of the results - simulating the regret bound as you would compute in theory, with a tabular mdp environment and see how theoretical insights might be validated. This will be valuable to more empirically minded readers and make a better case for the theoretical results in this work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "ZM2ePRWReR", "reviewer": "Reviewer_yros", "summary": "The paper aims to design provably efficient and exactly learnable distributional reinforcement learning algorithm in an online setting, especially under general value function approximation.\nFor the main findings, they introduce two key properties for statistical functionals: \n(1). Bellman Closedness: The sketch (compressed representation) remains consistent under Bellman updates.\n(2). Bellman Unbiasedness: The sketch can be unbiasedly estimated using sampled next states.\nThey find out that only moment functionals (e.g., mean, variance, higher-order moments) satisfy both properties and prove that quantile-based functionals (like those used in QR-DQN) are neither closed nor unbiased.\nThis work proposes Statistical Functional Least Squares Value Iteration (SF-LSVI) that focuses on matching a finite number of moments of the distribution instead of fitting the full distribution using a learnable and unbiased moment-based Bellman update.\nRather than estimating the full return distribution (which is infinite-dimensional), the paper learns a finite-dimensional sketch composed of moment functionals. These sketches are provably closed under Bellman updates and can be unbiasedly estimated from samples, making them ideal for regret analysis and online learning.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below. If any of our responses fail to address the intent of your questions or if you have remaining concerns, please let us know.\n\n----\n### 1. Lack of empirical validation\n\nWhile we acknowledge the value of experimental results, our primary aim is to establish theoretical connections between distributional RL and General Value Function Approximation (GVFA). Our main contribution lies in developing theoretical foundations and deepening understanding of these fields. We note that many GVFA papers with similar theoretical objectives [Jin et al 2021, Li et al 2024] likewise focus on theoretical advances without experimental validation.\n\n\n\n---\n### 2. Potential applicability in deep reinforcement learning scenarios\n\nThank you for your interest in deep RL applications. Our SF-LSVI algorithm, which learns distributions via moment matching, can be related to MMDQN [Nguyen et al., 2021] when adapted to deep RL. Notably, MMDQN has already demonstrated superior performance compared to C51, QRDQN, and IQN.\n\nWhile MMDQN uses particle-based moment matching, SF-LSVI explicitly constructs and updates predefined moment functionals. Since it is well known that, in truncated moment problems, 10-20 moments typically suffice for reconstructing distributions, we could learn the sketches of distribution (moments) more efficiently than existing distRL methods that require 50-200 statistical functionals.\n\n---\n### References\n\n- [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\" *Advances in neural information processing systems* 34 (2021): 13406-13418.\n- [Li et al 2024] : Li, Yunfan, and Lin Yang. \"On the model-misspecification in reinforcement learning.\" *International Conference on Artificial Intelligence and Statistics*. PMLR, 2024.\n- [Nguyen et al 2021] : Nguyen-Tang, Thanh, Sunil Gupta, and Svetha Venkatesh. \"Distributional reinforcement learning via moment matching.\" *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 35. No. 10. 2021.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria make sense and are well-aligned with the problem the paper addresses.", "theoretical_claims": "(1) Theorem 3.3 shows quantile functional cannot be Bellman closed. It aligns with existing theory.\n(2) Definition of Bellman Unbiasedness and Lemma 3.5 claim: only statistical functionals that are homogeneous of finite degree can be unbiasedly estimated under sketch-based Bellman updates.\nThe logic follows known properties of estimators; similar arguments are used in kernel mean embedding and U-statistics.\n(3) Theorem 3.6 shows only moment functionals are both Bellman closed and unbiased, it's consistent with Rowland et al. (2019) and standard function approximation theory.\n(4) Lemma 5.4 Confidence bound uses martingale concentration inequalities and normalized moment scaling. \n(5) SF-LSVI achieves a regret bound expressed in Theorem 5.5 based on Lemma 5.4, Eluder dimension theory and Martingale-based sketch estimation. The derivation path is well aligned with previous work, with careful adjustments for statistical functional setting.", "experimental_designs_or_analyses": "The main contribution of this work is theoretical, aimed at addressing foundational issues in distributional RL. Instead of providing empirical experiments, the paper provides non-trivial regret bounds and tight complexity analysis, which is already valuable.\nThe proposed method (SF-LSVI) fills a known theoretical gap: regret-optimal DistRL under general function approximation.", "relation_to_broader_scientific_literature": "This paper extends prior work on distributional reinforcement learning and general value function approximation by building on Bellman closedness (Rowland et al., 2019) and eluder dimension-based regret analysis (Wang et al., 2020). \nUnlike previous approaches relying on quantile or full-distribution representations, the authors show that only moment functionals satisfy both Bellman closedness and unbiasedness. They redefine Bellman completeness through a moment-based lens, addressing model misspecification issues found in works like Chen et al. (2024). \nThis work leads to SF-LSVI, a distributional RL algorithm with provable regret guarantees and a strengthened theoretical foundation.", "essential_references_not_discussed": "Related works are well discussed.", "other_strengths_and_weaknesses": "The paper demonstrates strong originality by introducing the novel concept of \"Bellman unbiasedness\" and showing that moment functionals are uniquely suited for provably efficient distributional RL. \nIts theoretical contributions are significant, addressing long-standing challenges in DistRL such as the intractability of full-distribution learning and model misspecification. \nThe work clearly builds on and advances the literature in a well-structured and technically rigorous way. \nHowever, one notable weakness is the lack of empirical validation to support the theoretical findings.\nOverall, the paper is clear and well-motivated, with impactful insights for the theory of distributional reinforcement learning.", "other_comments_or_suggestions": "Empirical validation can be considered, so that we can compare proposed method with quantile based approaches such as QRDQN and IQN in different tasks.", "questions_for_authors": "I am curious about the potential applicability of this approach in deep reinforcement learning scenarios. \nAlthough quantile-based methods have known theoretical limitations, algorithms such as QR-DQN and IQN have demonstrated strong empirical performance across a range of risk-sensitive tasks. \nIt would be interesting to explore whether representations based on moment functionals can be effectively integrated with neural networks, and whether such integration could lead to performance improvements over existing quantile-based approaches like QR-DQN.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NLMYpajt14", "reviewer": "Reviewer_iHHe", "summary": "This paper considers learnability and provable efficiency of distributional RL (distRL). The proposed notion of *Bellman unbiasedness* extends *Bellman closedness* in the literature to address the estimation errors stemming from finite samples. They show that moment functionals are the only finite statistical functionals that are both Bellman unbiased and closed. Built on this result, they introduce SF-LSVI for distRL with general function approximation, which enables estimating the distribution unbiasedly in finite-dimensional embedding spaces without misspecification error.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below. If any of our responses fail to address the intent of your questions or if you have remaining concerns, please let us know.\n\n---\n### 1. The advantage of SF-LSVI over standard expectation-based learning algorithm\n\nSF-LSVI is an algorithm that has the advantage of accurately learning distribution information beyond expectation while maintaining a tight upper bound in terms of standard regret. Therefore, it has the advantage of being able to accurately obtain not only the mean but also various moment information.\n\nHowever, the standard regret measure currently used to evaluate online RL algorithms cannot measure discrepancy in moments other than the first-order moment (expectation). Due to this inherent limitation of the measure, we do not believe it is suitable for distinguishing between the performance of expectation RL and distRL. As we wrote in the Conclusion section, we believe a generalized definition of regret that also evaluates discrepancies occurring in second and higher-order moments is needed, and we are pursuing this in our follow-up research.\n\n---\n### 2. How would parameter N affect learning and sample complexity?\n\nThrough Lemma 5.3, since the size of the confidence region increases as $\\tilde{O}(\\sqrt{N})$, the regret also reflects a factor of $\\tilde{O}(\\sqrt{N})$. Learning $N$ moments can be viewed as increasing the feature dimension by $N$ times, so space complexity adds a factor of $O(N)$, and according to [Jin et al 2020]'s results, (per-step) computational complexity adds a factor of $O(N^2)$. We will add this explanation to Theorem 5.5 for a deeper understanding of the results.\n\n---\n### 3. Relationship between Bellman unbiasedness and closeness\n\nBellman closedness refers to a property of sketches that allows accurate updating of distribution information when the transition kernel is given. However, in sample-based updates, since the transition kernel is not given, additional sketch properties beyond Bellman closedness are needed. Bellman unbiasedness refers to a complementary property that ensures unbiased learning of sketch updates through finite samples, and through this property, we can guarantee tight upper bounds in regret.\n\nThe position of categorical sketch in Figure 1 is based on the results from [Rowland et al 2019]. They showed that categorical sketch is a linear functional (Lemma 3.2 of [Rowland et al 2019]), and by our Lemma 3.5, since all linear functionals are homogeneous over degree 1, categorical sketch is Bellman unbiased.\n\nThe fact that categorical sketch is not Bellman closed was proven in Lemma 4.4 of [Rowland et al 2019], so combining these two results leads to the representation in Figure 1. We will clarify this process more explicitly in Figure 1 and Appendix C.\n\n---\n### 4. Alternative approach to estimate directly on the mixture distributions\n\nA key distinction between \"Bellman unbiasedness\" and \"Bellman closedness\" is that we can learn exact information about the return distribution **without the knowledge of the pre-defined transition kernel**. This means SF-LSVI needs only a finite number of sampled sketches to learn the return distribution unbiasedly, rather than requiring knowledge of the transition kernel.\nAs noted in Line 324, this unbiasedness property allows us to transform the learning process into a martingale, construct confidence regions through concentration inequality, and ultimately develop an algorithm that achieves tight upper bounds.\n\nWhile we could introduce new definitions for sketches (such as max, min) that can be estimated consistently but with bias, constructing confidence regions for non-martingale processes remains largely unexplored without distribution priors. The theoretical analysis of such an approach would likely be extremely challenging.\n\n---\n### References\n\n- [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\" *Advances in neural information processing systems* 34 (2021): 13406-13418.\n\n- [Rowland et al 2019] : Rowland, Mark, et al. \"Statistics and samples in distributional reinforcement learning.\" International Conference on Machine Learning. PMLR, 2019.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "See Questions 3 & 4.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. The proposed *Bellman unbiasedness* extends *Bellman closeness* to finite sample setting, which is meaningful and important for online/offline RL.\n2. The SF-LSVI enables estimating distributions unbiasedly in finite-dimensional embedding spaces, addressing the intractability of implementation in infinite-dimensional space in previous work.\n\n**Weakness:** See Questions.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. Is it possible to show the advantage of SF-LSVI over standard expectation-based learning algorithms? For example, in a cost minimization setting, can it also achieve a small-loss bound as in (Wang et al., 2023)?\n2. How would parameter $N$ affect learning and sample complexity?\n3. Can you elaborate on the relationship between Bellman unbiasedness and closeness? For example, Figure 1 shows that categorical representation is Bellman unbiased but not closed, but I am unable to find the proof for the argument.\n4. In Definition 3.4, $\\phi_\\psi$ maps $k$ sampled sketches to an estimated one. But I feel like there is an alternative approach where we form an estimation directly on the mixture distributions, i.e., $\\\\{ (\\mathcal{B}\\_r)_{\\\\#} \\bar\\eta(s_i') \\\\}\\_{i=1}^k$.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cb8DxPVDuM", "reviewer": "Reviewer_xKcn", "summary": "This paper studies distributional RL, in particular the statistical functional formulation of it. They begin by introducing the concept of Bellman-unbiasedness, obtain results on which equivalent conditions lead to this, and exactly characterize which sets of statistics are both Bellman-unbiased and Bellman-closed, which are the set of the first $N$ moments for any $N>0$. They then introduce an algorithm SF-LSVI which learns these moments, and they prove regret bounds for this algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below.  **Due to character limits, we have focused on addressing what we considered to be the most important comments. We ask for your understanding that we could not provide responses to all questions.**\n\n---\n### 1. Theorem 5.5 says nothing about how well $n$-th moment are learnt.\n\nFirst, we note that our paper investigates the necessary conditions for achieving provable efficiency and **learning all moments simultaneously in distRL** by using finite-dimensional sketch-based updates. \n\nThe reviewer’s concern seems to stem from the observation that standard regret is not well-suited for evaluating the effectiveness of distRL, as it fails to capture discrepancies in higher-order moments (order 2 and above). This may have led to a misunderstanding that SF-LSVI does not achieve moment matching.\nHowever, Lemmas 5.3 and 5.4 theoretically guarantee that all sketches are learned exactly in finite-dimensional spaces. The reason we use the standard regret in our quantitative evaluation is to follow the conventional regret analysis framework in RL literature.\n\n\n----\n### 2. Minor issues on theoretical claims\n\nThank you for the careful review of these points. It can be assured that the issues you raised do not change the theoretical results.\n\n- (A2-1) In Lemma 3.2, since we derive a contradiction when $p_{y_0}>\\alpha$  and $p_{z_0}<\\alpha$ , we cannot include cases where $\\alpha=0 \\text{ or } 1$. Therefore, it is correct to modify it to $\\alpha \\in (0,1)$, which allows us to draw conclusions consistent with existing max and min functionals.\n- (A2-2) If we understood your second point correctly, we believe the above response addresses it. If not, please let us know and we’d be happy to clarify further.\n- (A2-3) Are you referring to $(\\mathcal{B}\\_r)$? For the max functional, since $\\max_{z \\in Z}(Z+r)=\\max_{z \\in Z}(Z)+r$ (and similarly for the min functional), $T_{\\psi_\\text{max}}$ and $T_{\\psi_\\text{min}}$ are valid operators. For clarity, we’ll revise Line 703 as:\n    - $T_{\\psi_\\text{max}}\\Big(\\psi_{\\text{max}}(\\bar{\\eta}(s))\\Big)= \\max_{s' \\sim \\mathbb{P}(\\cdot|s,a)}\\Big(r + \\psi_{\\text{max}}(\\bar{\\eta}(s'))\\Big)$\n\n---\n### 3. Theorem 3.6 essentially reduces to the exact same result of [Rowland et al 2019]\n\nTheorem 3.6 extends the results of [Rowland et al. 2019] by encompassing a broader class of statistical functionals. \nSince [Rowland et al. 2019] only focuses on **linear functionals**  (i.e., $s(\\mu)=\\mathbb{E}_{Z \\sim \\mu}[h(Z)]$), they cannot demonstrate whether variance is a Bellman closed sketch.\n\nHowever, since $$\\text{Var}(\\mu) = \\mathbb{E}\\_{Z\\_1 \\sim \\mu}[(Z\\_1-\\mathbb{E}\\_{Z\\_2 \\sim \\mu}[Z\\_2])^2] = \\mathbb{E}\\_{Z\\_1 ,Z\\_2 \\sim \\mu}[Z\\_1 ^2 -2Z\\_1 Z\\_2+Z\\_2^2]=\\mathbb{E}\\_{Z\\_1 ,Z\\_2 \\sim \\mu }[h(Z\\_1, Z\\_2)],$$ it is a functional that is homogeneous of degree 2. By Lemma 3.5, such functional is Bellman unbiased, and our result, Theorem 3.6 leads to the property that variance is also Bellman closed.\nThat is to say, Theorem 3.6 can be summarized as a generalized conclusion that determines whether unbiasedly estimatable statistical functionals, which represent a broader domain, are Bellman closed.\n\n---\n### 4. Response to [Other Comments and Suggestions]\n\n(A4-1) While $\\eta^{\\star}_h$ is generally not uniquely defined, this occurs in cases where $\\pi^{\\star}$ is not uniquely defined due to the lack of total ordering on distributions in a control case. We will mention this in [Bellemare et al 2017] along with a statement excluding such situations.\n\n(A4-3, 5) We will add text defining linear functionals. As demonstrated earlier with the variance example, homogeneity is a separate concept that does not overlap with linear functionals. Therefore, the statement following Theorem 3.6 is valid.\n\n\n---\n### 5. Response to [Questions For Authors]\nWhile the questions are beyond our current scope, they are insightful, and we would be happy to explore them further. Briefly speaking, we believe that the algorithm cannot achieve the tight regret bound if the bias does not converge to 0 during the learning process.\nHowever, due to the character limit and the possibility that these points are not central to the reviewer’s evaluation, we have chosen not to focus on them here. If the reviewer’s main concerns have been addressed, we will aim to revisit these topics in the next response round, as space permits.", "claims_and_evidence": "I would distill the claims of this paper as (i) introducing and studying the stochastic equivalent of Bellman closedness, and (ii) introducing a distributional RL algorithm SF-LSVI and analyzing its performance. \n\nI believe (i) is well supported, however (ii) is not, for reasons I highlight below. \n\nI think the regret analysis of Section 5 is not what one would want to do in general, and may be answering the wrong question. SF-LSVI is a method for learning a sketch of the first $N$ moments $(s_1,\\dots, s_N)$, but the regret bounds in terms of $Reg(K)$ only measure accuracy in terms of the value function, i.e. the accuracy of $s_1$. Theorem 5.5 says nothing about how well $s_2,\\dots, s_N$ are learnt, and the bound would hold even if they were learnt arbitrarily poorly. It also appears that additionally learning $s_2,\\dots,s_N$ does not improve the regret compared to learning $s_1$ directly. Due to this, I don't believe that the analysis of Section 5 supports the claim that SF-LSVI is an efficient distributional RL algorithm.", "methods_and_evaluation_criteria": "There is no evaluation nor datasets used as this is a work of theoretical nature.", "theoretical_claims": "I carefully checked most proofs. I think there are a couple of minor inaccuracies/issues with some results:\n\n- Lemma C.2. states that the quantile sketch is not mixture-consistent for any quantile level $\\alpha \\in [0,1]$, while Example 4 states that the maximum and minimum functionals are both mixture-consistent. Since these are exactly the quantile sketches for $\\alpha=\\{0,1\\}$ respectively, these results contradict each other.\n\n- There are 2 issues in the proof of Lemma C.2., or at least in my understanding of it. The final step of the proof follows by setting $p_{z_0} = 2\\alpha - \\sum_{n'=0}^n  p_{z_{y_n'}}$, however I think this could be problematic for two reasons. Firstly we must have $p_{z_0}\\geq 0$ as it is a probability measure, however this construction may validate that. Similarly we must also have $p_{z_0}  < \\alpha$ as this is an assumption introduced earlier in the proof, but this assumption can also be broken by the given construction.\n\n- Section C.2. claims to prove that the statistical function $\\psi_{\\text max}$ is Bellman-closed. To do this, they define its corresponding Bellman operator as $T_{\\psi_{\\text max}(\\eta(s))} = \\max_{s' \\sim P(s,a)} \\psi_{\\text max} ( {(B_r) \\sharp} \\eta(s')) $. This is not a valid operator however, as they are applying a nonlinear function to the inside of the statistic $\\psi_{\\text max}$ on the right-hand side, which is **not** valid for the definition of Bellman-closedness. Instead to do this, writing $u= \\psi_{\\text max}(\\eta(s))$, they should introduce a Bellman operator $T_{\\psi_{\\text max}}$ such that $T_{\\psi_{\\text max}(\\eta(s))}$ can be written as a function of $u$.", "experimental_designs_or_analyses": "N/A (no experiments done)", "relation_to_broader_scientific_literature": "The introduction and analysis of Bellman unbiasedness naturally follows from the analysis of Bellman closedness in literature. The regret analysis is similar to previous regret analysis for distributional RL algorithms in literature, as illustrated in Table 1.", "essential_references_not_discussed": "I don't believe there are any essential references not discussed, at least to my knowledge.", "other_strengths_and_weaknesses": "**Strengths**\n- The notion of Bellman unbiasedness is a natural extension of Bellman closedness, and is a valuable step towards understanding and designing sample-based distributional RL algorithms.\n- The SF-LSVI algorithm is a nice distributional RL algorithm to study, as in some ways it is the \"most similar\" to standard RL, and understanding it deeply seems to be a natural step in progress.\n\n**Weaknesses**\n- Theorem 3.6. potentially lacks novelty as in light of Lemma 3.5. it essentially reduces to the exact same result of Theorem 4.9. of Rowland (2019) (if I understand correctly).\n- The choice of regret analysis is questionable and perhaps not the best, as I discussed above. \n- There are a couple of theoretical issues as I discussed above. \n- Many parts of the paper can be improved by a careful re-reading to improve the overall flow, at the moment there are a number of minor grammar mistakes and ill-formed sentences.", "other_comments_or_suggestions": "- There should be a bit more care in the subsection \"Distributional Bellman Optimality Equation\" of Section 2: $\\eta^\\star_h$ is *not* uniquely defined, as opposed to the optimal value function.\n\n- In Lemma C.2. the notation $\\psi_{q_{\\alpha}}$ is used but never defined.\n\n- I believe the authors define a functional to be linear if there exists a function $g$ such that $F(\\mu) = \\int g d\\mu$, however this is never defined in-text. This also overlaps with the definition of homogeneity introduced in Lemma 3.5., I would suggest unifying this notation and cleaning this presentation.\n\n- Section 3 is currently a mix of existing concepts and new concepts/results. I would suggest moving the existing results to a prior section (Section 2 perhaps), so that Section 3 is entirely novel which would make the contribution more clear. \n\n- After Theorem 3.6., it is stated \"we extend beyond linear statistical functionals to include nonlinear statistical functionals, showing the uniqueness of the moment functional.\" This is perhaps misleading since the Bellman unbiased assumption exactly limits to \"linear statistical functionals\", and this is required in the proof.\n\n- In Example 1 of Appendix Section C, $\\lambda$ is overloaded as both the argument of the exponential functional and the mixture coefficient.", "questions_for_authors": "- Rowland et al. (2019) introduce the notion of approximate Bellman closedness for the setting that statistics cannot be learnt exactly (such as quantile RL or categorical RL). What results can be obtained for approximate Bellman unbiasedness?\n- Is unbiasedness the \"best case\" that we'd hope for? What if we have two estimators for a sketch, one which is unbiased and one which is biased but with a lower variance and potentially lower MSE? The bias will likely compound over applications of the operator, but I would imagine if the variance reduction is large enough it could be preferable?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper got overall positive reviews and the reviewers highlight in particular the novelty of the paper. I therefore recommend to accept the paper. There are a range of suggestions by the reviewers to improve the paper and I hope that the authors will consider these suggestions for improving the final version of the paper.
Decision: Accept (poster)