Statistical Efficiency of Distributional Temporal Difference Learning
Authors: Yang Peng
Liangyu Zhang
Zhihua Zhang
Venue: NeurIPS 2024 oral (2024)
Keywords: Distributional Reinforcement Learning
Distributional Temporal Difference Learning
Sample Complexity
Primary area: reinforcement_learning

Abstract: Distributional reinforcement learning (DRL) has achieved empirical success in various domains.
One of the core tasks in the field of DRL is distributional policy evaluation, which involves estimating the return distribution $\eta^\pi$ for a given policy $\pi$.
The distributional temporal difference learning has been accordingly proposed, which
is an extension of the temporal difference learning (TD) in the classic RL area.
In the tabular case,  Rowland et al. [2018] and Rowland et al. [2023] proved the asymptotic convergence of two instances of distributional TD, namely categorical temporal difference learning (CTD) and quantile temporal difference learning (QTD), respectively.
In this paper, we go a step further and analyze the finite-sample performance of distributional TD.
To facilitate theoretical analysis, we propose a non-parametric distributional TD learning (NTD).
For a $\gamma$-discounted infinite-horizon tabular Markov decision process,
we show that for NTD we need $\widetilde O\left(\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+1}}\right)$ iterations to achieve an $\varepsilon$-optimal estimator with high probability, when the estimation error is measured by the $p$-Wasserstein distance.
This sample complexity bound is minimax optimal (up to logarithmic factors) in the case of the $1$-Wasserstein distance.
To achieve this, we establish a novel Freedman's inequality in Hilbert spaces, which would be of independent interest.
In addition, we revisit CTD, showing that the same non-asymptotic convergence bounds hold for CTD in the case of the $p$-Wasserstein distance.

Statistical Efficiency of Distributional Temporal Difference Learning
Yang Peng"
Liangyu Zhang
Zhihua Zhang
Abstract
Distributional reinforcement learning (DRL) has achieved empirical success various domains. One core task in the field of DRL is distributional policy evalua- tion, which involves estimating the return distribution 1)" for given policy x. The distributional temporal difference learning has been accordingly proposed, which is an extension of the temporal difference learning (TD) in the classic RL area. In the tabular case, Rowland et al. [2018] and Rowland et al. [2024a] proved the asymptotic convergence of two instances distributional TD, namely categori- cal temporal difference learning (CTD) and quantile temporal difference learning (QTD), respectively. In this paper, we go step further and analyze the finite- sample performance of distributional TD. To facilitate theoretical analysis, propose non- con-mmamctiicc distributional temporal difference learning (NTD). For a d-discounted infinite-horizon tabular Markov decision process, show that for
NTD we need Ō ( iterations to achieve an E-optimal estimator with high probability, when the estimation error measured by the p- Wasserstein dis- tance. This sample complexity bound is minimax optimal up to logarithmic fac- tors in the case of the 1-Wasserstein distance. To achieve this, we establish novel Freedman's 's inequality in Hilbert spaces, which would be of independent interest. addition, we revisit CTD, showing that the same non-asymptotic convergence bounds hold for CTD in the case of the p- Wasseesstninn distance for 2 1.
Introduction
In high-stake applications of reinforcement learning (RL), such as healthcare [Lavori and Dawson, 2004, [Böck et all 2022 and finance Ghysels et al., 2005], only considering the mean of returns is insufficient. is necessary take risk and uncertainties into consideration. Distributional reinforce- ment learning (DRL) Morimura et all [2010), Bellemare et al. [2017] 2023] addresses such issues by modeling the complete distribution of returns instead of their expectations.
In the field of DRL, one of the most fundamental tasks is to estimate the return distribution vy for given policy स, which is referred to distributional policy evaluation. Distributional temporal difference learning (TD) is probably the most widely-used approach for solving the distributional policy evaluation problem. A key aspect of implementing a distributional TD algorithm is how to represent the return distribution, an mnfinite-dimensiona object, via computationally feasible fiite-dimensional parametrization. This has led the development two special instances of dis- tributional TD: categorical temporal difference learning (CTD) [Blllemare et all, 2017] and quantile temporal difference learning (QTD) [Dabney et al., 2018). These algorithms provide computation- ally tractable parametrizations and updating schemes of the return distribution.
School of Mathematical Sciences, Peking University: email: pengyang@pku. edu.. cn. $ 'School of Statistics Management, Shanghai University of Finance and Economics; email: edu. cn.
Schooo of Mathematical Sciences, Peking University; email: zhzhangemath pku. edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Previous theoretical works have primarily focused on the asymptotic behaviors of distributional TD. In particular. Rowland et [2018] Rowland et all [2024al showed the asymptotic convergences of CTD and QTD in the tabular case, respectively. A natural question arises: can we depict the sta- tistical efficiency of distributional TD by non-asymptotic results similar to the classic TD algorithm ML et al. 2024
1.1 Contributions
In this paper, we manage to answer the above question affirmatively in the synchronous setting Kakadee, 2003, Kearns all, 2002] Firstly, we introduce non non-parametric distributional temporal difference learning (NTD) in Section 3 which is not practical but aids theoretical understanding.
iterations are sufficient to yield an estimator vj" such that the p- p-Wasserstein metric between rj" and 17 is less than E with high probability (Theorem 4.1). This bound is minimax optimal (Theorem [.I in the 1-Wasserstein metric case, if we neglect all loga- rithmic terms. Next, we revisit the more practical CTD, and show that, in terms of the p-Wasserstein metric, CTD and NTD have the same non-asymptotic convergence bounds (Theorem 4.2). It is worth pointing out that to attain such tight bounds in Theorem 4. we establish Freedman's in- equality in Hilbert spaces (Theorem A.2). We would believe it is of independent interest beyond the current work.
We show that (AP(I
1.2 Related Work
Non-asymptotic results of DRL. Recently, there has been an emergence of work focusing on results of the distributional policy evaluations.
Wu et al.
[003] studied the offline distributional policy evaluation problem. They solved the prob- lem via fitted likelihood estimation (FLE) inspired by the classic offline policy evaluation algorithm fitted Q evaluation (FQE), and provided generalization bound in the p- Wasserstein metric case.
Zhang et al
2023] proposed to solve distributional policy evaluation by the model-based ap- proach and derived corresponding sample complexity bounds, namely Ô (-1(1-))+ in the
p- Wassersttii metric case, and Ö (.ا--1) in both the Kolmogorov Dolmogorov-Smiroov -mirnov metric and total variation metric under different conditions. Rowland et al. (2024b] proposed direct categorical fixed- point computation (DCFP), a model-based version of CTD, in which they constructed the estimator by solving linear system directly instead of performing an iterative algorithm. They showed that the sample complexity of DCFP is Ö マリリーンア>
in the 1-Wasserstein metric case by introducing the novel stochastic categorical CDF Bellman operator and equation. Their result matches the mini- max lower bound (up to logarithmic factors) ğž (111)) proposed in [Zhang et all 2023], which implies that learning the full return distribution can be as sample-efficient as learning just its expecta- tion. It's worth noting that the algorithms analyzed in both [Zhang et all, (2223) and (Rowland et all 2024b) are model-based, hence they are less similar to practical algorithms. While distributional TD analyzed in this paper, model-free method, is practical, and also involves more complicated theoretical analysis.
Böck and Heitzinger [2022] also considered model-free method. They proposed speedy categorical policy evaluation (SCPE), which can be regarded as CTD with an additional acceleration term. They
showed that the sample complexity of SCPE is Ō (अ<ーー1)) in the 1-Wasserstein metric case.
Compared to [Böck and Heitzinger, 20221. our work shows that even if we do not introduce any acceleration techniques to the original CTD algorithm, it still possible to attain the near-minimax optimal sample complexity bounds. Thus, we give sharper bounds based on a simpler algorithm.
Table gives more detailed comparisons of sample complexity with the previous work in the 1- Wasserstein metric. Note that solving distributional policy evaluation can also address the traditional
'Throughout this paper, the notation ʃ(-) = Ô (g()) (/(-) = át (g())) means that f(-) is order-wise no larger (smaller) than g(.), ignoring logarithmic factors poly(log (S], log (A] log( T-)) log()) ( (og())), as [S] [A], T :. 00.

---

Sample Complexity
Algorithms
Task
(Gheshlaghi Azar et al., 2013]
Model-based
PE
-(1-)))
[Li et al. 2024]
Ö c-11 -111))
TD (Model-free)
PE
[Rowland et al., 2018]
Asymptotic
CTD (Model-free)
DPE
RRowland et al., 2024a
Asymptotic
QTD (Model-free)
DPE
[Rowland et al. 2024b]
DCFP (Model-based)
DPE
Böcc and Heitzinger, 2022]
0
SCPE (Model-free)
DPE
Our Work
CTD (Model-free)
DPE
(-(1-))
Table 1. Sample complexity of algorithms for solving policy evaluation (PE) in the &oo norm, and distributional policy evaluation (DPE) in the supreme 1-Wasserstein metric.
policy evaluation task by taking expectation of the return distribution estimator. And the supreme Wasserstein metric error of the return distribution estimator is not smaller than the foe error of the induced value function estimator (see the proof of Theorem B B.Ilin in Appendix we have also listed the sample complexity of the policy evaluation task in Table for comparison.
Freedman's inequality. Freedman's inequality was originally proposed in (Fredmmnn 1975
can be viewed as a Bernstein's inequality for martingales, which is crucial for analyzing stochas- tic approximation algorithms. Tropp [2011] generalized Freedman's inequality to matrix martin- gales. And Talebi et al. [2022] established Freedman inequalities for martingales in the setting of noncommutative probability spaces. The closest literature to ours [Tares and Yad, [014] and
MMattnez- and Ramdas, [2024], where they provided special case of our Theorem A.2 with H 0 independently. When H O, we can only utilize the deterministic upper bound on the quadratic variation rather than the sigh-probability upper bound. In certain problems, such as the distributional TD learning we aim to investigate, it is impossible to achieve the optimal upper bound using the H = O version. Martinez-Taboaaa and Ramdas, 2024 also proposed an empirical Freedman's inequality (2, D)-smooth Banach space, which can be used construct confidence sets or perform hypothesis testing. To the best of our knowledge, we are the first to present this version (Theorem A.2) of Freedman's inequality in Hilbert spaces]
The remainder of this paper is organized as follows. In Section 2 we introduce some background of DRL and state Freedman's inequality in Hilbert spaces. Section we revisit distributional TD and propose NTD for further theoretical analysis. In Section we analyze the -onttttpt convergence bounds of NTD and CTD. Section | presents proof outlines of our theoretical results, and Dection[]coonluuee
our work. We put the detailed results with Freedman's 's inequality in Hilbert spaces in Appendix [ and the minimax lower bound of the distributional policy evaluation task in Appendix B
2 Background
An infinite-horizor tabular Markov decision process (MDP) is defined by 5-tuple M = (S. A. PR. P.7),, where S represents finite state space, A finite action space, PR the distri- bution of rewards, P the transition dynamics, i.e., Pn[-Is, (s,ss) a) E A ((0. 1J). P(-|s, a) E A (S) for any state action pair (s, a) E S x A, and y (0, 1) discount factor. Here we use A(-) to represent the set of all probability distributions over some set. Given policy π: S - A (AA and an initial state sg = s E S, a random trajectory {(Se, ae, ()) can be sampled from M: 0z St ~ T(. st). r: (st, az) ~ PR( St, at), 81+1 (st,
P(- 8t, oz) for any E N. Given a trajectory, we We denote return distribution 17" as the
define the return by (s) = Ee rtr, E 0. probability distribution GO (s), and 17th := (17((s) (s)) The expected return V*(s) = EG" (s) is
the value function in the traditional RL setting.
'In this paper, we assume that all the Hilbert spaces we encounter are separable, which can avoid measura- bility issues, ensure that the expectation can be defined, and guarantee tightness of any distribution. See Pisier 2016] for more details about probability in Hilbert space
3

---

2.1 Distributional Bellman Equation and Operator
Recall that the classic policy evaluation aims at computing the value functions V It known that V = (V*(s))EES satisfy the Bellman equation. That is, for any E S,
(*) [TT (s) = (1 Ir + 7V (s)))
(I)
The operator T R R is called the Bellman operator, and V is fixed point of T
The task of distribution policy evaluation is finding 17" given some fixed policy и. 17" satisfies a distributional version of the Bellman equation (I. That is, for any 8 E E.S.
17 (s) = ()) = B- (aa)
(0rs7) 11 (6))
(2)
where b R -> an affine function defined by bn (2) r + ya. And s 11 is the push forward
measure y through any function f: IR R. so that f* 1l (a(f-((A) for any Borel set A,
- A ( () is known
8
where (A) = (r: [xx A). The operator T": A
0, r
as the distributional Bellman operator, and 1y" is a fixed point 7 For notational simplicity, we
denote a ((o)--))) S from now on.
2.2 T Contraction in '
A key property of the Bellman operator T that it is a y-contraction w.r.t. the supreme norm (i.e. to norm). However, before we can properly diseuss the contraction properties of T", we need to specify a metric d on P. And for any metric on P. we denote d as the corresponding supreme metric on go, i.e., d (n, == max.es d (1{(),, (s)) for any 11, E G.
Suppose 1 and are two probability distributions on R with finite p-moments for P E oo). The p-Wasserstein metric between and v is defined as W W,(,,,) = (inf Jize - - yl" n(dx, dy)) 1/p Each element x E I(H, v) is a coupling of μ and v, i.e. joint distribution on R22 with prescribed marginals and v on each "axis." When = 1 we have Wi(, v) = Js [xx(x)) - Fo(x))da where F2. and F, are the cumulative distribution function of and v, respectively. It can be shown that 7 is 7-contraction w.r.t. the supreme p-Wasserstein metric Wp
Proposition 2.1. |Bellmarre et al, 2023, Propositions 4.15] The distributional Bellman operator a conntraccion on 3oS w.r.t the supreme p- Wasserstein metric for p E [1, oo). That is, for any n' E g0S, we have W, (T" Th I TW n').
The lp metric between a and v is defined as fp(u, v) = -F, dx) forp E [s, and T is 7 cootracction w.r.t. the supreme l, metric Epp Proposition 2.2. Bellemare et al. 2023, Propositions 4.20] The distributional Bellman operator is -o-oottraction on 9pS w.E.t. the supreme Ep metric for p E (o). That is, for any n, n.al E gos we have Ep n. T"m)) I 7t (p),,)))))
1
Note that the & metric coincides with the 1- I-Wasserstein metric. And the lg metric is also called the Cramér metric, which plays important role in subsequent analysis because the zero-mass signed measure space equipped with this metric (M, I1-Ile.) (defined in Section 5.1 is a Hilbert space]. Thereby, can apply Freedman's inequality in Hilbert spaces.
2.3 Freedman's Inequality in Hilbert Spaces
Just as Freedman's inequality is essential for the theory of TD (Theorem in Li all 2024()), a Hilbert space version of Freedman's inequality is indispensable for deriving the minimax non- asymptotic convergence bound for distributional TD. At the moment, we state a Hilbert space ver- sion of the original Freedman's 's inequality (Theorem 1.6 in [Freedman, 1975]), and more detailed results can be found Appendix[A]
'In fact, the space (M. (11,,))),) is not complete. However, the completeness property does not affect the non-asymptotic analysis, see Section 5, for more details.

---

Let X' be a Hilbert space, {Xi] be an X'-valued martingale difference sequence adapted to the filtration {Fi) Y _j
Xj be the corresponding martingale, and W; اj= o3 be the corresponding quadratic variation process. Here of == 1 ||, and E, [1] == IE [[]]]] denotes the conditional expectation.
Theorem 2.1 (Freedman's inequality in Hilbert spaces). Suppose maxie(n) | S b for some
constant b > 0. T'hen, for any ε and a > 0, the following inequality holds
{
2²/2 02 + be/3
IP (3k (n), ||Y&|| 2 E and W S d2) S 2exp
3 Distributional Temporal Difference Learning
If the MDP M -S, AS PR, P.7) is known, and because V is the fixed point of the contraction 7", V can be evaluated via the famous dynamic programming (DP) algorithm. To be concrete, for any initialization (0) E IR., if we define the iteration sequence V(K+1) = TT (V(()) for & E N,
we have limg- [v() V* = 0 by the contraction mapping theorem (Proposition 4.7 in Bellemare et al. 2023l).
Similarly, the distributional dynamic programming algorithm defines the iteration sequence as (k+11 1) for any initialization 17( In the same way, we have limg->oo (1)) nnn) for p E [1, oo] and lim (,)
, s7") for p E (1)
In most application scenarios, the transition dynamic P and reward distribution Pr are unknown, and instead can only get samples of P and Pn in streaming manner. In this paper, we as- sume a generative model [[akaade, 2003, Kearns et all 2002) is accessible, which generates in- dependent samples for all states in each iteration, i.e., in the 1-th iteration, we collect sample a,(s) π[- s). (s)) ~ P(-|s, az (s)) ~ PR(--s, (s)) for each s E S. Similar to TD (Sutton, 1988 in classic RL, distributional TD also employs the stochastic approximation (SA) [Robbins and Monro, [195]] technique to address the aforementioned problem and can be viewed as an approximate version of distributional DP.
Non-parametric Distributional TD ference learning (NTD), which is helpful in the theoretical understanding of distributional TD. In the setting of NTD, we assume the return distributions can be precisely updated without any parametriza- tion. For any initialization ng So the updating scheme is given by
We first introduce non-parametric distributional temporal dif-
ni = (1 - a m + az T3 n"
for any 2 1. Here a is the step size. The empirical Bellman operator at the t-th iteration T, is defined as
(T," 1) (s) = (b))()))) (1(+(+1)))
which is an unbiased estimator of (T m) (s). It evident that NTD is a SA modification of distribu- tional DP. Consequently, we can analyze NTD using the techniques from the SA area.
Categorical Distributional TD Now, we revisit the more practical CTD. In this case, the updates in CTD is computationally tractable, due to the following categorical parametrization of probability distributions:
K
K
= Px
Pro : Po. Px 2
0,
Pk -
k=
k=
where K N. and 0 < Zo
HK S
1 1- fixed points of the support. For simplicity,
assume { 1 equally-spacee i.e., 26 バ(ー We denote the gap between two points by LK = K
When updating the return distributions, we need to evaluate the fy-projection Pk. 1gg ;= argmin øx f2(p, fi). can be shown (Proposition 5.14 in Bellemare et al. ) that the projection is uniquely given by
of PK. 1k S
Pk ( where p4(H) Exap (1-
X Ih
I Σ
KK
k=0
5

---

(a)+ == max {ar 0} for any E RR It is known that Ig is n w.r.t. the Cramér metric (Lemma 5.23 in [Bellemare all 2023I), i.e. &g H kx S (2(,. for any μ.v E P. For any 7 E yos E S, we slightly abuse the notation and define (TTx)) (s) == [ky(s)) 1T is still non-expansive w.r.t. lg. Hence Tx. == x T is vn-contraction w.r.t. l2, we denote its unique fixed point as 177 E L. The approximation error induced by categorical parametrization given by (Proposition 3 in Rowland et al. (2018))
En ,n n7
1
Wi(n", ,n* S - K.K S (K(1-))34 (3)
1
VK(1-7)
v1
Now, we are ready to give the updating scheme of CTD, given any initialization nă E PP.
Te = =1 a: n + a 7 M
for any 2 1. We can find that the only difference between CTD and NTD lies in the additional application of the projection operator II at each iteration in CTD.
4 Statistical Analysis
In this section, we state our main results. For both NTD and CTD, we give the non-asymptotic convergence rates of W,, Wn n7") and (2 .77",, respectively.
4.1 Non-asymptotic Analysis of NTD
We first provide non-asymptotic convergence rate of Wi (17, n") for NTD, which is minimax optimal (Theorem B.J up to logarithmic factors.
Theorem 4.1 (Sample complexity of NTD in the 1-Wasserstein metric). Given any (0, 1) and E E (0, 1), let the initialization be ni E go, the total update number T satisfy
C 1g T T2
S
log
e² - 7)3
8
for some large universal constant C > 1, i.e. T = (=(1-))))) and the step size an satisfy
1 (1-11111 logt
1
S <
cs(1 1as(1-111 VT
log
for some small universal constants 02 > C3 0. Then, with probability at least 1 8, the last iterate estimator satisfies W1 (n7,"")) E.
Because W1 (np n²) _ always holds, we can translate the high probability bound to mean error bound, that is,
8 1-7 < 2
W1 (1 77)] s c(1 6)
we take 5 S 6(1- 7)- In the subsequent discussion, we will not state the mean error bound conclusions for the sake of brevity.
The key idea of our proof to first expand the error term W, (n 17") over the time steps. Then can be decomposed into an initial error term and a martingale term. The initial error term becomes smaller as the iteration goes due to the contraction properties of T To control the martingale term, we first use the basic inequality (Lemma E.. Wi (H, S vー Ea (u, v). which allows to
analyze this error term in the Hilbert space (M, lI,, defined in Section 5.1 Consequently, we can bound it using Freedman's 'ss inequality in the Hilbert space (Theorem A.2). A more detailed outline of proof can be found in Section 5.2
Combining Theorem with basic inequality Wp(n,n/) S (1->)² W (n,,1) n/) for any n,, n
S (Lemma we can derive that Ō ()([-1))
iterations are sufficient to ensure

---

Wp(n7.17 S. As pointed out in the example after Corollary 3.1 in Zhhan et al. 2023], when p the slow rate in terms is inevitable without additional regularity conditions.
Although the 1-Wasserstein metric cannot bound the Cramér metric properly, by making slight mod- ifications the proof have the following non-asymptotic convergence rate of (2 """, See Appendix for our proof.
Corollary 4.1 (Sample complexity of NTD in the Cramér metric). Given any 8 E (0.1) and e (0, 1), let the initial value T/ PS, the total update number T satisfy
C1 log
log S T
T2
=2 -1- 7)3/2
for some large universal constant C > i.e, T (रा1-
and the step size Os, satisfy
1
c211vvil S <
1 ca(1-v T
log
log
for some small universal constants estimator satisfies lg (1117")) S.
C3 >> 0. Then, with probability at least 1 - 8, the last iterate
4.2 Non-asymptotic Analysis of CTD
We first state parallel result to Theorem
Theorem 4.2 (Sample complexity of CTD in the 1-Wasserstein metric). Given any E (0, 1) and E E (0, 1), suppose K T-q' the initial value nō S the total update number T satisfies
C log 3 T
S T
T2
log
e1 7)3
6
for some large universal constant C > i.e, T = =
and the step size On satisfies
S 04 S
c1-1v/ii logt
ca(1-
log
for some small universal constants 02 > C3 > O. Then, with probubility at least 1 5, the last iterate estimator satisfies W1 (mr,, 17t.K) S
2. Furthermore, according to the upper bound 3 of
the approximation error W1 (1TT.K, ,n")., we take K {11-))33+ have Wa (n n7) S.
Note that the order (modulo logarithmic factors) of sample complexity of CTD is better than the previous results of SCPE [Böck and Heitzinger, 2022 and we do need the additional term
introduced in the updating scheme of SCPE.
The proof of this theorem is almost the same that of Theorem 4.1 we outline the proof in Sec- tion 5.2 The W1 metric result can be translated into sample complexity bound Ô ( in the W, metric. We comment that this theoretical result matches the sample complexity bound in the model-based setting [Rowland all 2024b).
As in the NTD setting, we have the following non-asymptotic convergence rate of (2 17") as corollary of Theorem 4.2 See Appendix CC5 for the proof.
Corollary 4.2 (Sample complexity of CTD the Cramér metric). For any given E (0, 1) and E (0, 1), suppose K T-x. the initialization is nă S. the total update number T satisfies
C1 log
I
T2
log
22 2/22
8
for some large universal constant C > 1, i.e., T
(
and the step size as satisfies
04 5
cx(1-17) logt
1
Cal1-/T
lng
for some small universal constants Co > C3 > O. Then, with probability least 1 8, the last iterate estimator satisfies E2 (177, 177, f. Furthermore, according to the upper bound 3 of the
approximation error &g (11 .1")), if we take K > ना- we have Eg (17. S e.
7

---

Proof Outlines
In this section, we will outline the proofs of our main theoretical results (Theorem Corollary 4.
Theorem 4.2 and Corollary Before diving into the details of the proofs, we first define some notation.
5.1 Zero-mass Signed Measure Space
To analyze the distance between the estimator and the ground-truth vy", we will work with the zero- mass signed measure space M defined as follows
M: == j:: l is a signed measure with |aa| (RR oo, (R) = 0, supp(1) S [0,
where |a| is the total variation measure of μr, and supp(a) is the support of μ. See [Bggahhx 2007 for more details about signed measures.
For any ja MM, define its cumulative function as (x) x)0, We can check that F2 is linear w.r.t 14, that is, FautDu = aF + 3F, for any a, 3 E I, μe, v M.
To analyze the Cramér metric case, we define the following Cramér inner product on M:
(n, := L. (z)dz.
It is easy to verify that (s)) is indeed an inner product on M. The corresponding norm, called the Cramér norm, given by I|elles / Vunni - So (Fu(x))² dx. We have vs 12 E . and |||| v2lle, l2 (v1, for any vI, v1, U2 E P.
The W1 norm on M is defined as ||mlw, := -6= (F)()))) dr. We have ||u] - 22 12llw, = Wi (v1, (2) for any Vl; 1/2 E G.
We can extend the distributional Bellman operator T and the Cramér projection operator II nat- urally to M Here, the product space M is also a Banach space, and we use the supreme norm: [|nlle, == max,es [117()) lle and [| == max.es [ln(s]]l,, for any E MS. We denote by I the identity operator in M
When the norm ||-I| is applied to E ((X), where X' any Banach space, and L(X) is the space of all bounded linear operators in X. we refer |||]| to the operator norm of A, which is defined as ||||| = suPmexx.lnn]=1 || With this notation, L(X) = (A: A is a linear operator mapping from X' to X, and ||||| < oo).
Proposition 5.1. Tx and IR are linear operators in MS. Furthermore, |T S V7.
|| 5% ||Tx, 1, and ||Txl 1.
The proof of the last inequality can be found in the proof of Lemma C.4 while the remaining results are trivial. We omit the proofs for brevity.
Moreover, we have the following matrix (of operators) representations of T and Ilk: T E L(M)SxS for any 1 E MS.
M(a| P) 10,0) S. ((m)) [s [T(,ss)))()) s'ES
(T" = Σ
OEA.'ES
where (8, E L(M) for any EM
(' Σ x(a ( s)) s,a)) I' (brr) uPn(dr ss))).
aEA
It can be verified that [|T(s, S Vn T(a s)P(s' ss (sPT(()))))) Similarly, [[T(s, s'll S (s'ss)) and 11x diag(Ilk) lnses L(M)SxS. With these represen- tations, Tx E L(M)SxS can be interpreted matrix multiplication, where the scalar mul- tiplication replaced by the composition of operators. It can be verified that (Ix Tx) (8, 8') = Ilx (s, and TT) (s,s')lle, $ <77"'(s'
8

---

where Cs > > 0 are small constants satisfying CyCs R and C4 > 1 is a large constant once we have established the conclusion Remark 1: In Lemma E.2 we show that both (M, I-lle,) and (M, are separable. And in complete. To resolve this problem, we will their completions to replace them without loss of generality, because the completeness property does not affect the separability. For simplicity,
Lemma E.3 we show that (M, ll Il:
still use .M to denote the completion space. According to the BLT theorem [TThorem 5.19 Hunter and Nachtergaels, 2001], any bounded linear operator can be extended to the completion space, and still preserves its operator norm.
5.2 Analysis of Theorems 4.1 and 4.2
For simplicity, we abbreviate both |1-1,, and 11-1le, as 1-11 in this part. For all E [T] := {1, ... h) we denote T. == T," T = T = nf" for NTD; T. == Ig T II
7) : 1)
for CTD: and T) == V/ A. 1k - 1j E M for both NTD and CTD. According to K for CTD. Our goal is to bound the W1 norm of the
Lemma E.4 E gps for NTD and ? P
error term |Arlla llw. This can be achieved by bounding | as |rrlw, S --i ||
According to the updating rule, we have the enror decomposition
A 1/
(1 (12 (2)))11 04 TT -1 !!
= (1 -
+ 0n (Tem)-1 1 - TTn)
( 1- ar (Te T) M/--1 T (Mt-1 7)
= [1 - oI + T A + az (Te - T) 9/-1-
Applying it recursively, we can further decompose the error into two terms
AT [1 oz I a: Do
II [1 0z)I i=t-1
a, +a. - T)
m--1:
(
where Ih As is defined as A,A,- ... A₁ for any operators or matrices {As) throughout the paper. Term (I) an initial error term that becomes negligible when is large because is contraction. Term (II) can be bounded via Freedman's 's inequality in the Hilbert space (Theorem Combining the two upper bound, we can establish recurrence relation. Solving this relation will lead to the conclusion.
We first establish the conclusion for step sizes that depend T. Specifically, consider
C4 log 3 T
S
T
22 7)3 log
1
< ag 5
6:11 RY log
ca(1-
log
depending only on os and cs. As shown in Appendix C. in this setting, can recover the original conclusion stated in the theorem.
Now, we introduce the following useful quantities involving step sizes and y
a1(1 - vF)),
if k = 0, if < k < t,
5 = an k+ (1 -a; vi),
aT,
if
The following lemma provides useful bounds for g(t)
Lemma 5.1. Suppose cocs
< . Then, for all t >
log 7. have that
T
1 8 S 72 for 0 k < 2
(t)
2log T
for
t
St.
(1
/
2

---

The proof can be found in Appendix C.2 The upper bound term (I) given by
From now we only consider
2
T log
(1) - II
& II ((1 (11-as)+ouv)) VI- vI-7
1
VI-2T²
where | V So dr -1
As for term (II), have the following upper bound with high probability by utilizing Freedman's 's's inequality (Theorem A.2).
Lemma 5.2. For any 8 E (0, 1). with probability least 6, we have for all t 2 0o log in the NTD case,
II
[11- - a;)I + a: a: (Th T) Th
1=k+1
(log* T) (oog (S(T)
< 311
1+
max ttt/2ck
A
7)-T
The conclusion still holds for the CTD case if we take 2 2411-)33 +1
The proof can be found in Appendix C.3 Combining the two results, we find the following recur- rence relation in terms of the Wi norm holds given the choice of T', with probability at least for all 2 eg log
(S(T) (log" T) log
(1 (1+
|
S /I -1-7 ||1|| S 35
max h: t/t//ckke
3)
In Theorem C
we solve the relation and obtain the error bound of the last iterate estimator:
Arlli, S (
(1og" T) (log IS!T (log* T) (log (SIT)
(1 7)-7)37
(1 3T
where C7 > 1 is large universal constant depending on co. Now, we can obtain the conclusion if taking C4 2 2C7 and T Ca log"
(01-7) log |S[T
6 Conclusions
In this paper we have studied the statistical performance of the distributional temporal difference learning (TD) from non-asymptotic perspective. Specifically, we have considered two instances of distributional TD, namely, the non-parametric distributional TD (NTD) and the categorical distri-
butional TD (CTD). For both NTD and CTD, we have shown that ( iterations are
sufficient achieve p- passsssesteiin s-optimal estimator, which minimax optimal (up logarith- mic factors). We have established a novel Freedman's 's inequality in Hilbert spaces to prove these theoretical results, which has independent theoretical value beyond the current work. We leave the details to Appendix A
Acknowledgments and Disclosure of Funding
This work has been supported by the National Key Research and Development Project of China (No. 2022YFA1004002) the National Natural Science Foundation of China (No. 12271011 and No. 12350001), and the MOE Project Key Research Institute of Humanities and Social Sciences
(No.221JD11000)
10

---

References
M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective on reinforcement learning.
In International conference machine learning, pages 449 458.. PMLR, 2017.
M. G. Bellemare, Dabney, and M. Rowland. Distributional Reinforcement Learning. MIT Press, 2023. http::/wwww.dsstrbbtii.ooo
M. Böck and C. Heitzinger. Speedy categorical distributional reinforcement learning and complexity analysis. SIAM Journal on Mathematics of Data Science, 4(2):675-693, 2022. doi: 10.1137/ 20M1364436. URL fattps:///ol org/ 10. 1117 20M1364466
M. Böck, J. Malle, D. Pasterk, H. Kukina, R. Hasani, and C. Heitzinger. Superhuman performance sepsis mimic-iii data by distributional reinforcement learning. PL.8 One, 17(1 (7(1)):20775358 2022.
I. Bogachev. Measure theory, volume 1. Springer, 2007.
W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
V. H. de la Pena. A general class of exponential inequalities for martingales and ratios. The Annals of Probubility, 27(1):537-564, 1999.
R. Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
D. A. Freedman. On tail probabilities for martingales. The Annals of Probability, pages 100-118. 1975.
M. Gheshlaghi Azar, R. Munos, and H. J. Kappen. Minimax pac bounds the sample complexity of reinforcement learning with generative model. Machine learning, 91:325-349, 2013.
E. Ghysels, P. Santa-Cli Clata, and R. Valkanov. There is risk-return trade-off after all. Journal of financial economics, 76(3):509-548; 2005.
J. K. Hunter and B. Nachtergaele. Applied analysis. World Scientific Publishing Company, 2001.
S. M. Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, 2003.
M. Kearns, Y. Mansour, and A. Y. Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine learning, 19119,208, 2002.
P. W. Lavori and R. Dawson. Dynamic treatment regimes: practical design considerations. Clinical trials, 1(1):9-20, 2004.
G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 72(1):222-236, 2024.
D. Martinez-Taboada and A. Ramdas. Empirical bernstein smooth banach spaces. arXiv preprint arXiv:2409.060600 2024.
Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Nonparametric return dis- tribution approximation for reinforcement learning. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 799-806, 2010.
A. Pananjady and M. J. Wainwright, Instance-dependen -bundds for policy evaluation in tabular reinforcement learning. IEEE Transactions on Information Theory, 67(1):566-585, 2020.
I. Pinelis. Optimum bounds for the distributions of martingales banach spaces. The Annals of Probability, pages 1679-1706, 1994.
G. Pisier. Martingales in Banach Spaces. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016. doi: 10. 1001000///09781336688800

---

H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statis- tics, pages 400-407, 1951.
M. Rowland, M. Bellemare, W. Dabney, R. Munos, and Y. W. Teh. An analysis of categorical distributional reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 29-37. PMLR, 2018.
M. Rowland, R. Munos, M. G. Azar, Y. Tang, G. Ostrovski, A. Harutyunyan, K. Tuyls, M. G. Bellemare, and W. Dabney. An analysis of quantile temporal-difference learning. Journal of Machine Learning Research, 25(163):1-47, 2024a.
URL
http://jmlz: http:///...rr..pppp/////////////
html
M. Rowland, K. Wenliang, R. Munos, C. Lyle, Y. Tang, and W. Dabney, Near-minimax-optmmall distributional reinforcement learning with generative model. arXiv preprint arXiv:4402.07599, 2024b.
R. Sutton. Learning to predict by the methods temporal differences. Machine learning, 3:9 44, 1988.
A. Talebi, G. Sadeghi, and M. Moslehian. Freedman inequality in noncommutative probability spaces. Complex Analysis and Operator Theory, 16(2):22, 2022.
P. Tarres and Y. Yao. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Transactions on Information Theory, 6019):5716-5735, 2014.
Tropp. Freedman's inequality for matrix martingales.
Electronic Communications doi: 1622 URL
in Probability, 16(none):262 270, 2011.
attps:///dt org/ 10. 1214/ECP v16-1166111 1624
C. Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
R. Wu, M. Uchara, and Sun. Distributional offline policy evaluation with predictive error guar- antees. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pro- ceedings Machine Learning Research, pages 37685-37713 PMLR, 23-29 Jul 2023. URL https://proceeeings mlr. www.spressssvvee wu23s. html
L. Zhang, Y. Peng, J. Liang, W. Yang, and Z. Zhang. Estimation and inference in distributional reinforcement learning. arXiv preprint (tti:2309.172223 2023.
12

---

A The Key Lemma: Freedman's Inequality in Hilbert Spaces
Freedman's inequality, proposed [Freedman. 1975], can viewed as a Bernstein's 's inequality for martingales, which is crucial for analyzing stochastic approximation algorithms. Compared to the Azuma-Hoefin Hoeffding inequality which only utilizes the boundedness of martingale difference sequences, Freedman's inequality incorporates second-order information, namely the quadratic vari- ation (cumulative conditional variance) of martingales. This may leads to a sharper concentration result. It has various generalizations, such matrix Freedman's 's inequality [Tropp, 2011]). However, to the best of our knowledge, a Freedman's 's inequality in Hilbert spaces has not been established yet. Just Freedman's 's inequality is essential for the theory of TT (Theorem 1 in [Li et all 2024)), it is indispensable for deriving the minimax non-asymptotic convergence bound for distributional TD.
In this section, we will present a Freedman's inequalities in Hilbert spaces. Firstly, we will state a Hilbert space version of the original Freedman's inequality (Theorem 1.6 [Freedman 1975).
After that, we state a generalization of more powerful version (Theorem 6 in [Li al. 2024
to Hilbert spaces. We will provide self-contained proofs in Appendix A primarily inspired by Theorem 3.2 in [Pinelis [1944]. The necessary knowledge of martingale theory for the proofs can be found in any standard textbook, such as [Durrett 2019].
Let A' be Hilbert space, {Xi)== be an X'-valued martingale difference sequence adapted to the filtration {F Y; == Ej=x,, X, be the corresponding martingale, W; := Σ o3 be the cor- responding quadratic variation process. Here of Ey-1 || and E, []] E [1FF is the conditional expectation.
Theorem A.1 (Freedman's inequality Hilbert spaces). Suppose max
X S b for some
constant 6 >
0. Then, for any E, >> 0, the following inequality holds
{
2²/2
PP (ak (.). || 2 E and We S o²) S 2xxp
(4)
02 bE/3
Now, are ready to state the generalization of Theorem 6 in [ al 2024 to Hilbert spaces, which is used in our non-asymptotic analysis.
Theorem A.2 (Freedman's 's inequality in Hilbert spaces with bounded quadratic variation). Suppose maX |X I b and Wn S o² for some constants b, > 0 almost surely. Then, for any 8 (0, 1), and any positive integer H 1, with probability at least 1 - 8, for all k [m]. the
following inequality holds
02
2H1 + - bog 3
211
|& S V mmx WK: 28
log
(5)
5
The proof can be found in Appendix A.2
Remark 2: Theorem 2.1 can be straightforwardly extended to the case where (I)x:)), satisfies
the Bernstein condition (Theorem 1. 1.2A in (de Penal, 1999]), thereby relaxing the boundedness
assumption on ||X,||- Namely, E;- ||x,|| < fklo for some b > O, and for all E [n].
l E (2, In this case, Freedman's 's inequality still holds, albeit with a worse constant.
{
e²/2 o2 +
P (Bk E [n].s.t s.t. ||all 2 and W S o²) I 22exp
(6)
The proof only requires making appropriate modifications after the fifth line Equation that Bernstein condition holds if maxte(x) || |X,|| < b.
122.
Note
A.1 Proof of Theorem 2.1
Proof. For any A 0, 0] and j [m], let @(t) = (t) := := cosh (A [ +x,
Ej-1 cosh (Au()), where v(l) : | + + iX,ll. We aim to use the Newton-Leibniz formula to es-
tablish the relationship between x(1) = B.-1 cosh (> (Y)]) and d(0) = cosh (> (A1 I)). This will
allow us to construct a positive supermartingale (B.) By utilizing the positive supermartingale and optional stopping theorem, we can derive the desired concentration inequality.
13

---

Firstly, we calculate the derivative of Φ.
(1) (Y + xz) u(t)
(7)
(1()) = XE
(sinh (Au(()) u (1)
= XB sinh (Xu(t)) ( +0-1ttx,, xX,,
(8)
u(t)
sinh (Au(()) (x)-1,X3)
e'(0) AE -1
x(0)
Asinh (A1-)) (Y E1 [X,])
(9)
|Yي-1
= 0.
By utilizing Newton-Leibnin formula, we have
((1) = 2(0) + [ d'(s)ds
= 6 + S J'" d"(t)dtds
(10)
= (0) + !. (1 1) (1)dt.
Now, we calculate the second order derivate of db
d (sinh (Au(t)) v' (6))
6"(t)= AE,-1
XE
(u((t)) cosh (Au(t)) + u" sinh (Au(t))
< -
((v'(1)) + (()((())) cosh (Ae(())]
(11)
X2
2 Ej-1
(w²)" (1) cosh (Au(t))
= X E
[|Ix,|| cosh (A ||Y 1 + tX511)
I X2 cosh (A A II) Ej-1 ||x exp (At [Ix,
where in the third line, we used v²) = |X u(t) -Xx1xxx,,,)> inequality, and h(z) cosh((x) - sinh(r)) 2 0 for any 2
m1e)
2 0 by Cauchy-Schwarz
a²(()
0, the inequality holds be-
cause h()) = and k'(x) = ss)nh(r) 2 0 for any x 2 0. In the fourth line, we used
(u²)"(0) (1) (cv((t))² + (t)()((t) In the fifth line, we used
d² (v²)" dta || + 1x dt
d (x 2|
|1
And in the last line, we used
cosh (A 1|1 + +x,ll))
cosh (A |1) exp (At ||X,I)),
this holds since
exp (A 414
exp (-X||X S |<,p::/))|__oop/llyl.//a/-0-/11- exp (At [|x;
14

---

Hence, we can derive the following inequality for all j [n]
- [cosh (A ( = + I." (1 -))0" (t)d"
<osh (A -lll) + X² cosh (A || 13-1 |1x211? I.' [11 (1-t) t) exp (At ||x (1) dt
||x,,12 exp (A ||x II) - X||X|| -1
cosh (A | I)) + X² cosh (A ||, - (1) -1
X x
E
exp (A |XX (I) A ||X,|| /1I cosh (A|
-Ej-1
+
(I] 6+2
cosh (A -1)))
(12)
(k + 2)
k=
X
X
2
Ab
<R,
cosh (A1)))-111)
2
3
k=
X²o7
1 +
cosh (A ||Yg-1ll)
2(1 Xb/3)
X²07
< Sexp
cosh (A || j1)-- ||),
22(1 -X/33)
which holds for any À E (0, }). In the fifth line, we used Taylor expansion e. = Ek p..
4 In the
sixth line, we used (k: + 2) 2 2(3%) and ||x < b. In the seventh line, we used Taylor expansion
I- = Σt=o x² for x E (-1,,) 1).
Let Bo = 1, Bi = exp
Aw 2(1-A6/3 A6/3)
cosh (A || [), then
XWW,-1
X²03
EB-1BB = exp
exp
2(1 Ab/3) }
E.-1 [cosh (A [|X]]D]
2(1 Xb/3)
A²W,11
(13)
eexp
2(1 \b/3) / cooh (A 1|/-//ll)
= -Bir1
ie.. (B.), ) is positive supermartingale. By optional stopping thcorem (Theorem 4.8.4 [Drrett 201 for any stopping time T, we have E [B,] EE [Bo] =
$} be a stopping time, and inf = cc. Define event Let = inf (K [m] ||
A = {3k E [n], s.t. || 2 and Wa S 02)
(14)
15

---

then on A, we have 7 < co. ||+|| 2 and W, I o², noting that Wa is non con-decressing with k. Our goal is to provide an upper bound for ((A).
1
P(A) E
B
1(A)
B
E Br] R
((4)
B
AaW.
exp
2(1 X6/3)
E
(A ||) I(A)
cosh
(15)
X2r² exp
2[1 2(1-3b/3) Xb/37
E
I(A)
cosh (AE)
X20² 2(1 2(133b/3)
2cxp
-E
/ P((A),
where in the second line, used Schwarz inequality. In the third line, used E [B,] < 1. In the fourth line, we used ||Y, || 2 E and W, S o² on A, and cosh(z) (x) increasing when æ 2 In the last line, used cosh(1) ee.
Hence for any À E (0, )
X²02 P(A) s 2exp -dE+ 2(1 - ((1-bb/3)
(16)
we can choose
o-beb/3 E (0, 2)), then
(A+)² 0²
P(A) 2exp
- +
2(1 x+b/3)
E²
a²
c²
2exp
+
(17)
02 eb/3
2
eb/3
(02 + eb/3)²
ṭ +sb/3
6//2
2exp
02 + eb/3
which is the desired conclusion.
A.2 Proof of Theorem A.2
Proof. According Theorem for any E, O, we have
{
52/2
P(ak [n), || 2 and W. < < < 2exp
(18)
x22+b//3
We can check that when E = 4482 loō2log? 2/ + + log 2. the upper bound on RHS is less than Hence,
3k E [n], ||| 2
472 log
blog 5
and W. S $0² 56.
(19)
16

---

For each k E [n], define the events
H
|| 2
max
Wki
2
0²
log
2H
8
4
3
blog
2H
S¹
((k)
||xi||
Z
0²
log
2H
4
blog
2H
and
Wi S
o²
28
8
2
0²
2H
4
2H
and o²
o²
||&|l
log
b
log
Wv 2
IsASH- -
2h-1
8
3
2
(20)
By the definition, we only need to show P (UEEM)] U44 I 6. Since Wx S Wn S 0² almost
surely, we find that (R) S Uneun
h. (we will justify this later). Then UkEln H S
(k)
Unem Ukejnj Bi. By the inequality 19 with x²
प and setting ô as H. we have
5
(Uke|m) Ph.H) i
6 for all h E [H]. By the union bound, we can arrive at the conclusion:
H
P
U kE(N)
H
S 6.
(21)
H.
A=1
AE(m]
To justify (k) S Uneto Ble we can consider the decomposition
H
U AE(M
(k) (H
nc/,
(22)
where
σ² H.H W4 <
= { 0²
σ²
(k)
(k)
Wx
ishs
(23)
28
2h
2h-
The decomposition holds because W₁ S Wn S 0² almost surely. We only need to show that for each h E [H].
H/W k
C B h,H
(24)
On the event H n
(k) ( H. we have
02
2H
2H 8
|| 2 V
8
max
WR.
log
b log
2
8
3
(25)
4 0²
2H
2H
log
b
log
24
8
3
8
hence (( n ((k)
(b)k) B
S
B Minimax Lower Bound of Distributional Policy Evaluation
In this section, still consider infinite-horizon tabular MDP defined in Section 2 and assume generative model accessible. For any positive integer D, we define 21 (D) as the set of all MDPs with state space size |S| D. For any MDP M and policy æ, denote Vi as the corresponding value function, and 7 as the corresponding return distribution.
Now, we can state the minimax lower bound of the distributional policy evaluation task in the 1- Wasserstein metric.
Theorem B.1 (Minimax lower bound of distributional policy evaluation in the 1-Wasserstein metric).
D. the following result holds For any positive integer D 2 3, and sample size T 2 I log 2,
log
inf sup sup E W1 (i, nhr]] 2 M M)) x
(1 3/2
T
17

---

Here, c, C. > O are universal constants, and the infimum ñ E " ranges over all measurable functions of T samples from the generative model.
The theorem states that for any algorithm, there exist corresponding MDP . and policy म, such that to ensure E [ (f) mhrr) S for some & > 0, least 52 (<((1-))) samples are required.
Proof of Theorem B. For any v E gD we define V(n) E RDD as the entry-wise expectation of r). And recall the dual representation of 1 1-Wasserstein metric
It is easy to check that V(nis V (Corollary 5.16 in [Villani et al 2009))
Wi (u, =
sup f: f is Lipschhix
[x [S(X) - By [S()],,
VI 3,
(26)
we have W1 (f, mr) 2 (V(()) VM ao Hence
inf sup ())
sup E W1 [h)]
2 inf sup sup E (1) VM [ool Mc -
inf sup sup V V
v M)
(27)
log D T
(1 7/3/2
where the second inequality holds because (ń) E R² is also a measurable function of T sam-
ples from the generative model, and the infiruum V E ER ranges over all measurable functions of T' samples from the generative model. And the last inequality due to Theorem 2(b) in Panaanaay and Wainwright 2020].
C Omitted Proofs in Section 5
C.1 Remove the Dependence on T for Step Sizes
We have shown that the conclusion holds for
C4 log T
| T
T 2
log
(28)
e² 7)3
1
I a4 5
(29)
+ 0-11-
ca(1-
log T
log
T
where cacs < 5. C5 cg and C4 > O.
Then for some 02 > C3 > O to determined, now we assume
Sa S
(30)
(1-3 Iog"1
1+
log
Next, will show that if we consider the result of the T T-th iteration with this step size scheme as the initialization
new iteration process, then the step sizes the subsequent 7 iterations lie in the previously established range. If this is done, the conclusion still holds if we choose T > 20, log T =²(1-y)a log 5 since the initialization nT,2
[S]r
SSS (or DS in the case of CTD) independent
of the samples obtained for T < S.
For any T < 1 < T, we denote 7 t. T we can see that there exist C2 > c3 > 0, such that the last inequality in both of the following lines hold simultaneously, which is desired.
ã = a S
(31)
ca (T+222
cal1- /20 Tog (T/2)
1
log log" (T+T/2)
log T
and
ā = 0₁
(32)
call +11+1/2
2ca /2
cs /71/22
log (T+T/2)
loga (T/2)
log (T/2)
18

---

C.2 Range of Step Size
Proof of Lemma 5
log 2 T 205
(1
2
(33)
7/T
+
log'
For any 0 S k < 1
v7)] 1/22
P
01/2
log² T
1/2
200T
log" T
2ng Ing
2c₂T
(34)
log T 4og 06
log² T
lag
203
72
where in the last inequality, we used C5 S 3
And for any < k < 4
21og² T
8 aab S coll A log T
<
(35)
(1 V5TT"
C.3
Concentration of the Martingale Term
Proof of Lemma 5.2 We will show that the inequality holds for each / 2 T union bound. For any S, we denote
and then apply the
ca log
1 II [1- aT - T) mn-1 (+), 1=++1
(=) = 10) (8) or
(36)
(t) for brevity, then LHS in the lemma equals EE Se for each
where we omit the superscript
t. Let FR denote the o-field that contains all information up to time step k then ((x(s) is ( difference sequence:
E [s()s) = og
Il i=++1
[1 B [[To T) m--1 (s) 0.
(37)
the first equality holds because a Bochner integral can be exchanged with a bounded linear operator (see Pisier [2016) for more details about Bochner integral), and the second equality holds due the definition of the empirical distributional Bellman operator.
We hope use Freedman's 's inequality (Theorem A.2 to bound this martingale. To this end, we need to give a deterministic upper bound of the martingale difference sequence, and an upper bound of its quadratic variation.
19

---

Deterministic upper bound of maX [|)(-))] can be bounded as follow
The norm of the martingale difference [((x
[k<(( s ||cell
S 00k
II [01 ox)o + azT] 11 T) nE- i=k+1
(38)
S 0kk
a;) II ((1- - a:) + +0.57) VT-7
k=++
8
VI-7
Hence, maxkej [[<(())]| <
maxkeld ((0)
VI-7
VI--
max
21ox 7
(1 V3/T
2
= b. (1-7)5/2T
4log
Upper bound of quadratic variation.
Now, let's calculate the quadratic variation.
We first introduce some notations. For any N, denote Var(E) :- (1 [IEE()]P]]] SES
ERS.
.ES E I for any random element & in MMS. (E) = [xx [IE(()]IP)
For any & E SM. we define its one-step update Cramér variation (5 Var (IT -T)s) R.S. where 7 a random operator and has the same distribution as Tí.
For any E RSS, we say I y if ass) I y(s) for all E S. In this part, |||||| = || = max,es [z())), va = (ss)) SES"
And for any U E S |U|| == |U] =
suP |||=||= |Ux||| max,ee Eves (U(ss'))
For any {xx C S we denote maXte(N] Bg (maxkeju) xn (S))
We denote SxS as the identity matrix, IRS the all-ones vector, and P p E BSSs i.e., P(s, s') = pr (s'ls) E.EA (s'sss)
With these notations, the quadratic variation is W, == Et=l Vara-1 (Sk). To bound the quadratic variation We, we need to bound Vark-1 (Cx).
Lemma C.1.
Vark-1 (Gx) (()
II <=++1
[(1 o;) + a: a (m=-1).
20

---

Hence, the quadratic variation W can be bounded as follow
W.
Vara-1 (Sk)
II (a-0:)[+a//7P/000))
1=1
i=++1
1/2
II i=++1
[11 o;) + /
110 (1k 1)l 1 +
II i=++1
10 aa-a:)) aa
k
k=//2+1
1/2
Σ
(8(00
1 +
max
3(0)
Σ
II
[11 --)) + a aiv
l: l/t/ccke
k=1
k=t/2-1
i=++1
2 2log T
2(1 7)T3
(1
V
Σ
O
(1 - 03)) ai /PP
max ktt/2ckst
(11-11)
k=1/2+1
k=++1
4log" T
2(1- 2(1-7)78 1
(I
PPP)
max
(T%-1))
(1 7)T
A: 112/2ckkt
(39)
where in the fourth line, we used
:
II [[1 -a) + +avppP
II [[1 a.) +av-l 3/% i=+1
ak
i=k+1
and
|| (1t- 1)ll 1 de
1-
In the last line, we used the fact that max o (1k- 2 and the following lemma:
Lemma C.2. For any E N, (as)se(e)
E [0, 1]", the following inequality holds entry-wise:
Σ
akk II I a (1-)))
(40)
1=
(=++1
According to 39 we have the following deterministic upper bound for |WWll max.es Wi(s),
1
1lg T
Wil S
(I /PP)-11
max k: k/
(n=-))))
2(1 - 7)T3
(1 - 7)T
1
8log"
< 2(1 7
(1 3)
(41)
9 10g" 3 T
(1 3T
Let H = 2ogg 1-
we have
2
9 glog 3
<
(42)
2H
(1 -)
21

---

By applying Freedman's 's inequality (Theorem A.2 and utilizing the union bound over 8 E S, we obtain with probability at least 6, for all E and S
Σ k=1
(a(s)
SES
<V
8
W. 28 1
o²
log
8 log
1-2
4 blog
8| log 1-7
9 glog" T
|S/T
S
SV
16
W. +
log
3b log
(1 ?)T
6
8
(log T) (log I
12 (log" T) (log 1817
o
<
[I VTP)-1
( + 3- + ktt/2ckgt
3//2T 1,
(1 7)T
(43)
where we used log 8|S T 1-2 The following lemmas are required for deriving the upper bound, which hold for both cases of NTD and CTD.
log SST in the second line, which holds due to the choice of T
Lemma C.3. For any E [T].
(m)) a()) S 4 4| 1| 1.
Lemma C.4.
4 1. (I - - - 1-7
Combining the upper bound with the two lemmas, we get the desired conclusion
Σ
(s(s)
k=1
SES
(log*1) T) (log ISTT
12 (log r) (log SS|T
8
<81
4 max ktt/2ckgt
| (I- (PP) 11
1
(1 7)T
(1 3//2T
(log" T)
ISIT) log 0 (1 7)2
12 (log" T) (log
1.S1T"
0
$221
1+
| AA--llin
1
1
ktt/2cket
(1 733/2T
ISIT) (log* T) (log
(1+ max l: 1/2////
<34
(1 2
(44)
where the last line, we used that, excluding the constant term, the first term is larger than the second term, given the choice of T
C. log
log |S|
3-1 [3-
C.4 Solve the Recurrence Relation
Theorem C.I. Suppose for all
T ca log
(log* T) [lg (ST
|Arlw, < 35
a
1+ kxx/2<kst
max
|A
(1
3T
Then there exists some large universal constant C7 > 0, such that
(log"T) (log |S|T
(log3 T) (log 181T
|rllw, CG
(1 (1
(1 3T
22

---

Proof. For any 2 O, we denote
0A = max
||eellss
2t
cB log T S SIST
T
(45)
for 0 S k < loga (ce Io). We can see that || | S for any valid k. Hence, it suffices to
show the upper bound holds for up for any valid k. It can be verified that uo T-y. and for k 2
(log² T) log 1S|T
uk+1 S 351
(1 + uR).
(46)
(1-7)3T
We first show that once us S 1, the subsequent values of ux+z will also remain upper bounded by 1. Namely, if up for some & 2 then
(log" 3 T) (log IST
uk+1 S 351
S 1,
(47)
(1-2)3T
if 2450 log 6 (1->)*
Let = inf {k: us 1}. then for any lo >> т, we have
2 (log* T) log [
04 S 35
(1 (1-78 73
=: a.
(48)
For A: T, we have wa 2 1 and thereby
(log* T) (log
[5 8
Ux+1 S 351
Uu a
(49)
- 3T-7)
i.e.
1 (log un - 2 log a).
log ub+1 - 2 log a
z
(50)
Apply it recursively, we have
(1)
1
k+1
log Uk+1
2loga +
(log uo log a),
(51)
i.e.,
1/2k
Ug S a²
1/2 S = 22(1-1/2*) u
a
Uk+1
(1
1/2
(52)
To sum up, for any 2 0, uk+1 is always less than the sum of the upper bounds in cases of l: > and & < T,
Wk+1 Sa 21 11-2)
1
(53)
Note that, a (1-11/2) S max (a, vaj, and if we take & 2 eg log log +-, for any constant Cg. we 0(1). We can take the constant es small enough such that es log log 1-y loga (cs log T) (this can be done and os universal since - o(T)), and thereby we can find valid k* 2 log log
have (1-y)1/2*
1 1- + 1. Then
(log² T) (log |S|r (log T) (log IS
| 5 ug. Or
(54)
(1 733
(1 11-7337 3T
which is the desired conclusion, and C7 is some large universal constant related to es.
23

---

C,5 Analysis of Corollaries 4.1 and
The difference in the proof compared Section 5.2 arises in Lemma 5.2 when we control term (II).
Now we further bound the result in Lemma C33 by the Cramér norm of the emror term,
o (m)) - (n) - 4 | is
VI-y | 1.
(55)
In the same way, we can derive the following recurrence relation: with probability at least 1 8, for all t 2 T 06 log.
|S (log T) (log
0
| S |
1+
max l: t/2<ck/
|
(56)
(1 75/2/
By repeating the reasoning of Theorem
we can obtain the desired conclusion,
(V
(log) T) (log ISIT
(log* T) (log S
Arll c
(57)
(1 (1-7) 23-/2/
(1 - 7/-////27
which is less than if we take C4 2 207 and 2
C2 log log 1SIT (113))677
Here, C7 > is a large
6
universal constant depending
C.6 Proof of Lemma C
Proof. We first introduce some notations. For any matrix of operators U E L (M)SxS, we denote U(s) = (L(s, s')sssss E (M) as the s-row of 4. And for any & E M we define the vector inner product operation U(s)E = EEessl(s, s')E(s') E M.
We need the following lemma, which holds for both cases of NTD and CTD.
Lemma C.S. For any E M. E N. (ax) E [0, let Un I-= [(1 o;) I + a; U, Ih (1 - a;) + as p). un = II [11 az) + aivil then for any s, E S, we have
(4,(ss'')ll" u, Un( ||||3
Utilizing this lemma, we get the following result. Recall that 7 is a random operator and has the same distribution Ti. Then, for any non-random E MS.
(n) T]el(?
(T
E
Σ (s, ( (5')
=E
s'ES
Σ (3, - T((')E
-E
(58)
Σ E. (( (('')E T(''5)]1
e'ES
Sun Σ
Un s'I TF
[ (0615-7(865)))
T(825))
PeS
=un Σ (')
e's
=u, Un())(()))))
24

---

where we used different rows of T are independent, and (s')) { is an unbiased estimator of T(()) E M. Hence, Var (un -T)) z un (E)
Now, we ready bound Var (Sx)
1 (Sc) = 0z. Vark-
II 1=++1
((1 - a,) aaT - TT 1
$ 0%
II i=k+1
[11 a:) + tivl
II
[11 (Pplooimm))) (59)
k=++
= 04 2
II [(1 - a
k=++
C.7 Proof of Lemma C.2
Proof.
Σ k=t/2+1
II i=++1
[1-a))++av77
Σ
II
[1- -
VIP)(I VFP)-1
k=1/241 1=k11
[1 - (1- (1- (--)-P)- (60)
Σ
-
kst/241 1i=k+1
t=k
(I- (1 (1- 0;) -
(1-V1P)- -
1=//2+1
<(I-Vi V)-)
where the inequality holds entry-wise since verify that all entries of (I /7P)-1
Ex (VTP)* and (1 a.) a 5P are non-negative.
C.8 Proof of Lemma C,3
Proof. For any S,
(s))ss) (s)
F2 (o) E [F))) Fermcola)) } dr
E
F2 (im))
IE
F2 (o
(F (0)) + (x)
-Frrnoon dx
{
(F(Tm))e) ((F))(o)(z)) (F(Fm))))()) + F (+)))
(61)
(F(rmo))()) (()))))(()) (P(rm)))( + Permcc) jda
+
E [(F - ((Fo) (x) + (FTmOO)()) - F(rm)oo)()) do 7 (m - n) (s) w.
2
+ IT (n - n) (+)l
-2
25

---

In the case of ITD, T and T are y-contraction w.r.t. the supreme 1- 1-Wasserstein metric, hence
(1n)(s) (1)) 2 E || T (m - (+)
+ +IIT(nn 1mm]
71) (6)]lms
(62)
S 4y || nlw,
1 4 Dellw.
In the case of CTD, if we show II is non-expansive w.r.t. 1-Wasserstein metric, the conclusion still holds. For any 2, E then & S 1, by the definition of IT K. we have
0, T- such that x < we denote E [xx Tk+1) and E (11,4141).
(x,)
Jk+1 11
SoL
y
Ihe
85R121
(63)
LK
iK
II (6,) = J141 -2 8zy +
y1 31
(64)
UK
KK
If k 1, we can check that Wi (TI dx
y. If W1 (II 0g) S W1 01 Tk+11) + W1 (IK+1, + W1 (2z, [x = (r++1 x) + (.i
LK M-
1, we have
ex
Hence, for any V1. 1/2 E 9 and for any transport plan K E [ v2), the previous results tell us the cost of the transport plan 1g E I (IkKy, [xx2)) induced by II is no greater than the cost of K. Consequently, Wi (Ixm, 1x22) S (i v2), ie., II is non- expansive w.r.t. I-Wasserstein metric, which desired.
Tk+1) + (y I2n)
C.9 Proof of Lemma
Proof. Firstly, show that for any O, we have || /PP) -00| -
[| - / ml
(I VTP) (I-
(I VTP)- [11 (1- 1 vi(1 /TP)] (I 7P) -P) '2/
[[(1 - (- + / (I- 'vo
$ - (1-v7)
+ / | - -7 PP
(65)
11 11 + +v7) (11-)P)-1v)
V
< 2 - -P -ol|
In the case of NTD, by Corollary D.I we have
( (1)) I-
(66)
In the case of CTD, by Corollary 5.12 in Rowland et al. 2024bl. we have
( (n)ll S I-
(67)
given K > -
C.10 Proof of Lemma C.5
Proof. We proof this result by induction. For n we have Uo I, Uo I, uo 1, thereby the inequality holds trivially. Suppose the inequality holds true for n - 1. To prove that the inequality holds for n, it is sufficient to show that, for any μ M,
[I(11 )a.) + ax T(s, s')] ull < [(1-a.) + an v [(1 an. + an P(s, s')] ||]l2
where 62.0' = 1 if = s', and 0 otherwise.
26

---

LHS can be bounded as follow
[I[(1 - an)os,s' + an T (8, 1/|
-(1 an) ||1l + 2(1 an and (p, (s,, s')n) a [T s ulll <(1 - a1-=an)88 do. 1|al1 + 2(1 an.andes ||l T (s, s') )ll + a [ s ntll
(68)
where we used Cauchy-Schwarr inequality. We need to give an upper bound for []( )ull
Note that (M (s, s²) = kT (s. and ||Tx|| = 1, we only need to consider the case of
NTD, by the definition of (s,, 8'), we have
2
/ Fy x--
(T(ss's)pl1
s')p1l
Σ LaEA
((lss)
Pa(dr(s,a) de
7
72
8(),
((a)s) s,
Fy
---)))
x r
Pn(dr(s,a))
dx
P(s,8")
LREA
(69)
s /
E (ann(())
Fg
x r
s'
dx
?
x 2
< P(s, s') E sa)
Fp
dz
s'
7
=yP(s, 8') ||||
where we used Jensen's inequality and Fubini's theorem. Substitute it back to the upper bound,
[[[(1 an) + a, ((s,(ss,s0 s') [e]
<( 25, |//11 + 2(1 - an an)an 8 ||l (s,, s')all + (
< (1 an) 2² 0s 2(1 an ann.. (s, P(s s1) ||ll
(70)
[11 an 2 o an BnV5P(s, 8)] ||1l2
$ [1 - an) + an [[1 an )5 + on (P),
8'))
which is desired.
D Stochastic Distributional Bellman Equation and Operator
In this section, we use the same notations in Appendix C and only consider the NTD setting. Inspired by stochastic categorical CDF Bellman operator introduced (Rowland et all 2024b), we introduce stochastic distributional Bellman operator 9 A bound for - (( in the case NTD. For any A random element go with law Φb
(.pS) A (g0S) to derive upper
(gs) we denote ns be the
= Law (Tn)).
J :Φ==
(71)
where (Tn))(w) = (TA)()) go for any Ω, Ω is the corresponding probability space, and T independent of no. In this part, 7 does not consist of II since we only consider the NTD setting.
We consider the 1- L-Wssserttein metric W1 A (gOS). the space of all probability measures on the space (g9S, E2). Since (gSS) [2) is Polish (complete and separable), the space (A (gS). Wi) is also Polish (Theorem 18 in [Villani et all 2009g).
Proposition D.I. The stochastic distributional Bellman operator T is Vi-contraction on (gS)) ), i.e., for any $ &' E A (gS), we have
W1 (I V7W1 (7. (')
27

---

Proof. Let K² E [ 6') be the optimal coupling between Φ and Ø'. The existence of n² is guaranteed by Theorem 4.1 in |Villani et al., 2009]. And let the random element = (ε),E2) in (goS)² 2 has the law K", where & and & are both random elements in gos We denote I k* = Law (TE, (I
KEI(9 x1) 1 1008 (5,55) K. (dE,
Wi (F0,
inf
1 1 1089
(5, 5') In' (ds, de')
E 1 (TEI, TE2)
S WB
[&2 (E1, E2)
(72)
v / 15s8
Es (E,EE) x² (ds, de')
/
inf
la (2,55) k: (dE, dg')
)ET( 1808
kET(O))))
=
By the proposition and contraction mapping theorem, there exists unique fixed point of T, denote 2b E (go)) as the fixed point. Hence, the stochastic distributional Bellman equation reads
+/ ワ
(73)
We denote The as the random element in S with law s, then T The and Th have the same law. As shown in the following proposition, The can be regarded noisy version of Proposition D.2.
E [m 17,
where the expectation is regarded as the Bochner integral in the space of all finite measures on PS which is normed linear space equipped with Cramér metric its norm.
Proof.
E [ww]
EE
Tny
E E
TTi
m
(74)
[Trw]
TE (nw).
where we used 7 independent of 7 Since EE [nw] is the fixed point of T, we have E [nw] 77.
Based on the concepts of T and sb we can obtain the following second order distributional Bellman equation, which is similar to the classic second-order Bellman equation (Lemma 7 in GGeeshlaghi Azar et all 2013)).
||| (Tm) (s) n(s)) (1) EES NTD setting. We denote a := (1) for simplicity, and Σ = (E [I m(s)]²])
Recall the one-step Cramér variation o (n) E
IRS used in the
sES RRS.
Proposition D.3 (Second order distributional Bellman equation).
Σ = 3=o+>PX
28

---

Proof. For any E S
E(s) E (s) [1]]]
E (Tn))) (8) - -7(8)) 1|]
(75)
E (T (s) (Fn) (s) + (Tn) (s) mns) |1
E (T1) (8) 715)) |
E || (Tmxz) (8) (Fn) (0))(²]
where the last equality holds since the cross term zero as below
(s) (s(s, (TT)) (s) [T)) (s)
E (T) (s) nss), (TT))) (8) (Tn) (s) [
E ((( - (s)) E
(Tmw) (s) (s) [] (Tn) (s)
(76)
E [< (TTn (8) m(s))
=0.
The first term in 75 is (s). we need deal with the second term.
(nw) (8) - (Tn) (8)
E
E (Tm))) (s) (Fn) [s)] mo
|mo]
E
10
(Fim)toreD)
(x=-) Fo(o((s))
x (²=r))²
2
=E
o)) (1a)))))0)
dr n
7
-177((')-n(5)))) - -(>')l
Σ
((8))))
8' ES
aEd
Σ P(s,'')((s))
EES
(77)
Put these together, and we can arrive at the conclusion.
Now, we can derive a tighter upper bound for |[]-))))-on)] Corollary D.I.
( s [| | < 1-7
Proof. Note that all entries of (I (I--P)-1- Em (1 are positive, thereby (I- <
(1 1 (- = E, and (s)) = E [|)]()) - ((>)|??] s 2o dx = + for any 8 S.
E Other Technical Lemmas
Lemma E.1 (Basic Inequalities for Metrics on the Space of Probability Measures). For any
V1 9, we have (2)()2 s Wi(1i, s - (2() and (v()) s
"-- WP
(v),
29

---

Proof. By Cauchy-Schwarz inequality.
W1 Wi(v1, 1/2)
[F, (x)
Fuz((a) (x))
%
12dry
[F) Fos (o:)
1
(2(1).
And
(2(11, 122
FF, (2) Frz(z)) ?d
[2, (z) dr (11.1.2))
And
W2()1002)
1/v
inf kET())))s)
( [o) |x vl mlde, du)
1/0
/ 1 x 21 m(dx, dy)
inf
(1 - (1-7) 1
WP (2).
(1 (1-7)1-
Lemma E.2. (M, I1llles) and (M, (M.II-lw,) are separable.
Proof. Recall that (L, Wi) is separable [Theorem 6.18 Villani al., 20091 and by Lemma E. the Cramér distance & can be bounded by 1-Wasserstein distance W,, hence (3P f2) is also separable.
Let be either W1 f2, and A be the countable dense subset of (g) d). For any
0, E M,
we denote á == [n((R)- Then we can find a E Q P4, E s.t. |q
2μ
1 |e| (R) S e||ll,,
M((R)
2
d(ū+, (++) 3q d(pr.ū-) 3q
Note that the set of all possible J++ ja- is countable. Let
= qü, then we have
filla
quIlaa + 119
Alla
[ |m| (TR) - 4)17
+ a (1 - -x4) - (ii -ila
d
Illalla
|m| (RR)
+ q 11/4 -l+lld + + 11āe_ P-1ld
2
[xc| (R)
||4| (IR)
lllllla
+ c
+ q 3g
6 ||
|M| (R)
3g
=
Hence we have found a countable dense subset for (M, (l.) for d = W, b. Therefore, (M, (1lle)) and (M, (l; are separable.
30

---

Lemma E.3. (M, Il-lw,, ) is not complete.
Proof. Consider the Cauchy sequence in (M, pn = Di
(
82 which satis-
27
fies || - Mn+ llw, S E g S Z but its limit Di=l (
(di+
81 $ M
because its total variation is infinity, Hence, this is Cauchy sequence without a limit, implying the space not complete.
Lemma E.4 (Range of T/: ), Suppose that at 10, for all t 2 O. Assume that njg PS, then we have, for all t 2 O, oi E gp in the case of NTD. Similarly, assume that no E P then we have, for all 2 O, nf E P in the case of CTD.
Proof. We will only prove the case of NTD, and the proof for CTD is similar by utilizing the property of the projection operator lkx: go + P
K. We prove the result by induction. It is trivial that
T E gos for = O. Suppose that 1/. E gos recalll the updating scheme NTD
n (1 04 az) at TTT n-
(78)
It is evident that S is convex set, considering that . is subset of the product signed measure space, which is linear space. Therefore, we only need show that T, nh- PpS which trivially holds since 7," is random operator mapping from gos gos and n E gos, By applying the induction argument, we can arrive at the conclusion.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The theoretical assumptions used the paper are widely accepted and sup- ported by rich body of references in the literature, and the references are cited in our paper.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification:
Our paper provide the full set of assumptions and self-contained proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Given that our paper focuses on the theoretical analysis of existing popular algorithms, it does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
33

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Given that our paper focuses on the theoretical analysis of existing popular algorithms, does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see
NeurlPS code and
data submission guidelines for more de-
tails.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines httt::://aips.ccpppbltt/////// wwtcc//cpccc/ccccccccccccccccllt httplliccggie////ee
for more details. The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Given that paper focuses on the theoretical analysis of existing popular algorithms, does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Given that our paper focuses on the theoretical analysis of existing popular algorithms, it does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
34

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: Given that our paper focuses on the theoretical analysis of existing popular algorithms, does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't i make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htthicsshtttt:////
Answer: [Yes]
Justification:
The research conform with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper only focuses theory, hence there is no negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our paper only focuses on theory.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwtpsssappppsososooooocoo cow.co/////c//o com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "qEY71bwfTO", "reviewer": "Reviewer_bMoZ", "summary": "This paper presents last-iterate error bounds for distributional\ntemporal difference learning in the $W_p$ and Cramér metrics. The\nresults apply to a nonparametric/intractable distributional TD algorithm\n(where return distributions can be represented exactly) and a tractable\nprojected distributional TD algorithm with finite categorical\nparameterizations of return distributions. Using a novel Hilbert space\nmartingale inequality, the paper achieves tighter bounds than existing\nresults in the literature, as well as generalizations to more metric\nspaces.", "questions": "In Theorem 4.2, you claim that the sample complexity bound does not\ndepend on the number of bins $K$. However, you also assume an explicit\nlower bound on $K$, so naturally the sample complexity bound does depend\non $K$ in some capacity. Can anything be said about the sample\ncomplexity (e.g., as a function of $K$) when\n$K\\leq 4\\epsilon^{-2}(1-\\gamma)^{-2}$?\n\nIs the derivative computed on the second step of equation (29) correct?\nIt looks like you went from $\\lambda$ to $\\lambda^2$, but I believe only\non of the terms on the RHS should incur an extra $\\lambda$ factor. My\ncomputation is\n\n\\begin{align*}\n\\phi''(t) &= \\lambda\\mathbb{E}\\_{j-1}\\left\\\\{\\frac{\\mathrm{d}}{\\mathrm{d}t}[\\sin(\\lambda u(t))u'(t)]\\right\\\\}\\\\\\\\\n&= \\lambda\\mathbb{E}_{j-1}\\left(u'(t)\\frac{\\mathrm{d}}{\\mathrm{d} t}\\sinh(\\lambda u(t)) + \\sinh(\\lambda u(t))\\frac{\\rm d}{\\mathrm{d}t}u'(t)\\right)\\\\\\\\\n&= \\lambda\\mathbb{E}\\_{j-1}\\left(\\lambda (u'(t))^2\\cosh(\\lambda u(t)) + \\sinh(\\lambda u(t))u''(t)\\right).\n\\end{align*}", "limitations": "Limitations are adequately discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper is very technically precise, and mostly well written. The Hilbert\nspace Freedman inequality that was derived for the purpose of proving several\nresults in the paper seems useful. Moreover, the error bounds generalize and/or\nimprove upon the existing results on non-asymptotic sample complexity in\ndistributional RL.", "weaknesses": "Many of the mathematical derivations were very quick and at times\ndifficult to follow (particularly, in the appendix). While the work of\nRowland et al. 2024 studies an algorithm that is less similar to\npractical distributional RL methods, the conclusion of their work is\nfairly similar (distributional RL has the same statistical efficiency as\nexpected-value RL). Their work does not cover all $W_p$ distances unlike\nthis work, and the dependence on $p$ is interesting; it is also\ninteresting, again, that this work provides a certificate for good\nstatistical efficiency with a stochastic approximation TD algorithm.\nThat said, the paper does not do an excellent job of motivating why this\nnovelty is exciting.\n\nMoreover, since the Hilbert space Freedman inequality appears to be an\nimportant contribution, I believe this should have been included in the\nmain text (even just the statement of the theorem).\n\nFinally, I suspect there is a slight mathematical mistake in Appendix A,\nthough I don't expect it substantially changes the results; see the\nQuestions section.\n\n## Minor Issues\n\n\"Temporal Difference\" should really be \"Temporal Difference Learning\".\n\nLine 159 says \"the projection is unique and uniquely given by\" – this is\na little redundant, should be either \"the projection is uniquely given\nby\" or \"the projection is unique and is given by\".\n\nLine 168 mentions the BLT theorem without any citation — it might be\nnice to include a reference here, since \"BLT theorem\" may not be a\nfamiliar term to some.\n\nAt the end of line 275, there are two periods.\n\nOn line 425, \"forth\" -\\> \"fourth\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable review and constructive suggestions. \nWe are very glad to know thatyou think our theoretical results are technically precise, and acknowledge the contribution of the proposed Freedman's inequality.\n\nRegarding the weaknesses and questions, we provide the following detailed responses:\n> Weakness 1: Many of the mathematical ... (particularly, in the appendix). \n\nWe thank the reviewer's comment regarding the presentation of the mathematical derivations. We will add more explanations to make our proof easier to follow.\n\n> Weakness 2: While the work of Rowland et al. 2024 ... why this novelty is exciting.\n\nWe are grateful to the reviewer for raising this issue, and we will provide a\nfurther comparison with [Rowland et al., 2024]. The DCFP method proposed by\n[Rowland et al., 2024] can be seen as an extension of the certainty equivalence\nmethod (also called model-based approach) in traditional RL to the domain of\nDRL. In DCFP, one needs to estimate the distributional Bellman operator using\nall samples, and then substitute it for the ground-truth one in the distributional\nBellman equation to solve for the estimator of $\\eta^\\pi$This can be considered as a\nplug-in estimator, which is less similar to practical algorithms.\n\nIn contrast, the CTD analyzed in this paper can be viewed as an extension\nof TD. Compared to DCFP, CTD is more similar to practical algorithms and\ninvolves a more complex analysis.\n\nIn terms of proof techniques, [Rowland et al., 2024] introduced the important\ntools: the stochastic categorical CDF Bellman equation, to derive tight sample\ncomplexity bounds for the model-based method DCFP. The tools are also used\nin our paper. Compared to DCFP, the analysis of CTD (a model-free method)\nis more challenging. For instance, some probabilistic tools used for analyzing\nstochastic approximation problems in Hilbert spaces are not available, such as\nthe Freedman’s inequality. We overcame these difficulties and obtained tight\nsample complexity bounds. We believe that our findings will be of interest to\nresearchers working on distributional reinforcement learning and related areas.\n\nWe will revise the manuscript to include the discussion above, which we\nbelieve will provide a clearer context for our work.\n\n> Weakness 3: Moreover, since the Hilbert space ... just the statement of the theorem).\n\nWe thank the reviewer for recognizing the contribution of the Hilbert space\nFreedman’s inequality. We will add a new section after the Background to\ninclude the inequality in the revised manuscript.\n\n> Weakness 4: Finally, I suspect there is a slight mathematical mistake...\n\nWe thank the reviewer for spotting the typographical error. Equation (29)\nshould be corrected to \n\n$ \\phi^{\\prime\\prime}(t)=\\lambda\\mathbb{E}_{j-1}\\left\\lbrace\\frac{d}{dt}\\left[\\sinh\\left(\\lambda u(t)\\right)u^\\prime(t)\\right]\\right\\rbrace$\n\n$ =\\lambda \\mathbb{E}_{j-1}\\left[\\lambda\\left(u^\\prime(t)\\right)^2\\cosh\\left(\\lambda u(t)\\right)+u^{\\prime\\prime}(t)\\sinh\\left(\\lambda u(t)\\right)\\right] $\n\n$ \\leq \\lambda^2 \\mathbb{E}_{j-1}\\left[\\left(\\left(u^\\prime(t)\\right)^2+u^{\\prime\\prime}(t)u(t)\\right)\\cosh\\left(\\lambda u(t)\\right)\\right] $\n\n$ =\\cdots$\n\nwhere in the third line, we used $\\sinh(\\lambda u(t))\\leq \\lambda u(t)\\cosh(\\lambda u(t))$ (since $\\lambda>0$ and $h(x)=x\\cosh(x)-\\sinh(x)\\geq 0$ for any $x\\geq 0$), and $u^{\\prime\\prime}(t)=\\frac{\\|\\|X_j\\|\\|^2u(t)-\\frac{\\langle Y_{j-1}+tX_j,X_j\\rangle^2}{u(t)}}{u^2(t)}\\geq 0$ by Cauchy-Schwarz inequality. \nNo further modifications are needed for subsequent proofs.\n\n> Minor Issues\n\nWe are grateful to the reviewer for identifying these issues in our manuscript.\nWe have fixed them and added a reference to the BLT theorem ([Hunter and\nNachtergaele, 2001], Theorem 5.19).\n\n> Question: In Theorem 4.2, you claim that the sample complexity bound does not depend on the number of bins $K\\cdots$\n\nWe appreciate the reviewer's questions and are sorry that our original statement was unclear. \nThe original idea that once \n$K> \\frac{4}{1-\\gamma}$ ($K>\\frac{4}{\\varepsilon^2(1-\\gamma)^2}$ in line 206, 297, 577 is a typo), we can choose step size $\\alpha_t$ and total update steps $T$ independent of $K$ to get the desired conclusion. \nWhen proving Theorem 4.2, the condition $K> \\frac{4}{1-\\gamma}$ is only utilized in the proof of Lemma B.3 (see Equation (81)), which ensures that the variance term $\\|\\|(I-\\gamma P)^{-1}\\sigma(\\eta)\\|\\|$ can be finely controlled by $\\frac{2}{1-\\gamma}$, while the naive upper bound is $\\frac{1}{(1-\\gamma)^{2}}$.\nThis is because when $K> \\frac{4}{1-\\gamma}$, the variance term under the CTD setting approaches that under the NTD setting, allowing us to derive that $T=\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ is sufficient to make sure $\\bar{W}_1\\(\\eta^\\pi_T,\\eta^{\\pi,K})\\leq \\varepsilon$.\nWhen $K\\leq \\frac{4}{1-\\gamma}$, we can obtain a sub-optimal result: $T=\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^4}\\right)$ is sufficient to make sure $\\bar{W}_1(\\eta^\\pi_T,\\eta^{\\pi,K})\\leq \\varepsilon$, through an analysis that does not use variance information (e.g. Hilbert space Azuma-Hoeffding inequality).\n\nIn fact, Theorem 4.2 only guarantees $\\bar{W}_1(\\eta^\\pi_T,\\eta^{\\pi,K})\\leq \\frac{\\varepsilon}{2}$.\nTo ensure that the desired error term $\\bar{W}_1(\\eta^\\pi_T,\\eta^{\\pi})\\leq\\varepsilon$, we need $\\bar{W}_1(\\eta^{\\pi,K},\\eta^{\\pi})\\leq\\frac{1}{\\sqrt{1-\\gamma}}\\bar{\\ell}_2(\\eta^{\\pi,K},\\eta^{\\pi})\\leq\\frac{\\varepsilon}{2}$, at which point $K\\geq\\frac{4}{\\varepsilon^2(1-\\gamma)^3}$, and therefore the condition $K> \\frac{4}{1-\\gamma}$ in Theorem 4.2 naturally holds.\n\nWe will revise the manuscript to clarify these points and add a more detailed\nexplanation to ensure the argument is clear and logical for the readers. We would\nlike to express our gratitude once again for the reviewer’s insightful question.\n\n## Reference \nJohn K Hunter and Bruno Nachtergaele. Applied analysis. World Scientific\nPublishing Company, 2001.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "UY9PEWEQmc", "reviewer": "Reviewer_CFYY", "summary": "The paper investigates the statistical efficiency of distributional temporal difference (TD) algorithms in reinforcement learning, focusing on non-asymptotic results. The authors introduce a non-parametric distributional TD algorithm (NTD), analyze its sample complexity with respect to the p-Wasserstein metric and Cramer metric, and show the near minimax optimality. They also revisit the categorical TD (CTD) and prove that it shares similar non-asymptotic convergence bounds with NTD.", "questions": "- In Theorem 4.2, I am curious about the derivation of the statement that the number of atoms required for CTD to converge is $\\tilde{O}(1/\\epsilon^2 (1-\\gamma)^2)$.\n\n- Additionally, DCFP also achieves the same sample complexity with categorical representation, so a detailed explanation of the differences between these two papers would be beneficial.", "limitations": "The paper clarifies the limitations by making assumptions for theoretical explanations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The notation is standard and clear, and the related work on sample complexity of distributional RL is well-written, making it easy to understand the authors' theoretical contributions.\n \n- The proposed analysis of NTD and CTD provides a tighter near-minimax optimal sample complexity bound compared to previous methods. \n\n- A new Freedman's inequality is presented, which seems to be useful for further research.\n\n- The bound on $\\beta_k^{(t)}$ presented in Eq. (18) is impressive and appears highly useful.", "weaknesses": "As a minor comment, it would be helpful to present sample complexities of this paper and related work in a table to help understand the authors' contributions. \n\nThe matrix-wise distributional bellman operator $\\mathcal{T}(s,s')$ presented on line 257-259 uses the same notation as the standard, which can be misleading.\n\nTypos:\n- In Line 105, the font for $T^{\\pi}$ should be corrected to calligraphic.\n- In lines 211,212, $K \\geq \\frac{4}{\\epsilon^2 (1-\\gamma)^3}$ should be $K \\geq \\frac{4}{\\epsilon^2 (1-\\gamma)^2}$.\n- On line 275, the period is written twice.\n- Line 510 should be corrected to $\\log$, not $\\log_2$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments. \nWe are very glad to know that\nyou find our results solid and novel.\nRegarding the weaknesses and\nquestions, we provide the following detailed responses:\n\n> Weakness 1: As a minor ... understand the authors' contributions.\nThanks for your suggestion of presenting a sample complexities table, we agree with\nyou that it will help readers better understand the results in our paper.\n\nWe will add the following table in the revised version.\nIn the table, when the task is distributional policy evaluation, the sample complexity is defined in terms of the $W_1$ metric as the measure of error. \nThis allows for a clearer comparison of results with those in the standard policy evaluation task.\n| Paper | Sample Complexity | Method | Task|\n|-------|-------|-------|-------|\n|[Gheshlaghi Azar et al., 2013] | $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ | Model-based | Policy evaluation|\n|[Li et al., 2024] | $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ | TD (Model-free) | Policy evaluation|\n|[Rowland et al., 2024] | $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ | DCFP (Model-based) | Distributional policy evaluation|\n|[Rowland et al., 2018] | Asymptotic | CTD (Model-free) | Distributional policy evaluation|\n|[Rowland et al., 2023] | Asymptotic | QTD (Model-free) | Distributional policy evaluation|\n|[Bock and Heitzinger, 2022] | $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^4}\\right)$ | SCPE (Model-free) | Distributional policy evaluation|\n|this work | $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ | CTD (Model-free) | Distributional policy evaluation|\n\nHere, DCFP method proposed by [Rowland et al., 2024] can be seen as an extension of the certainty\nequivalence method (also called model-based approach) in traditional RL to the\ndomain of DRL. And SCPE proposed by [Bock and Heitzinger, 2022] can be\nregarded as CTD with an additional acceleration term.\n\n> Weakness 2: The matrix-wise ... can be misleading\n\nWe appreciate your valuable suggestions. \nIn the subsequent versions, we will consider revising the notation, such as $\\mathcal{T}_{s,s^\\prime}$, to prevent any potential misunderstanding by the readers.\n\n> Typos\n\nWe are grateful for your careful reading and for identifying these typos. \nWe will correct them in the subsequent version of the manuscript. \n\nHowever, regarding the third point you raised, on lines 211 and 212, where it states $K\\geq\\frac{4}{\\varepsilon^2(1-\\gamma)^3}$ \n, there is no typographical error. \nThis is because we require $\\bar{W}_1(\\eta^{\\pi,K},\\eta^{\\pi})\\leq\\frac{\\varepsilon}{2}$ to hold, and since $\\bar{W}_1(\\eta^{\\pi,K},\\eta^{\\pi})\\leq\\frac{1}{\\sqrt{1-\\gamma}}\\bar{\\ell}_2(\\eta^{\\pi,K},\\eta^{\\pi})\\leq\\frac{1}{\\sqrt{K}(1-\\gamma)^{3/2}}$ according to Equation (7), we need to take $K\\geq\\frac{4}{\\varepsilon^2(1-\\gamma)^3}$.\nAnd we would like to clarify a related typo in line 206 (Theorem 4.2), 297, 577: $K\\geq\\frac{4}{\\varepsilon^2(1-\\gamma)^2}$ should be corrected to $K\\geq\\frac{4}{1-\\gamma}$.\nWe sincerely apologize for the confusion this may have caused.\n\n> Question 1: In Theorem 4.2, I am curious about ... $\\widetilde{O}\\left(\\frac{4}{\\varepsilon^2(1-\\gamma)^2}\\right)$\n\nAs previously mentioned, in the conditions for Theorem 4.2, the statement $K\\geq\\frac{4}{\\varepsilon^2(1-\\gamma)^2}$ should be corrected to $K\\geq\\frac{4}{1-\\gamma}$. \nWe sincerely apologize for this mistake again.\nIn the proof of Theorem 4.2, the condition $K\\geq\\frac{4}{1-\\gamma}$ is only utilized in the proof of Lemma B.3 (see Equation (81)), which ensures that the variance term $\\|\\|(I-\\gamma P)^{-1}\\sigma(\\eta)\\|\\|$ can be finely controlled by $\\frac{2}{1-\\gamma}$, while the naive upper bound is $\\frac{1}{(1-\\gamma)^{2}}$.\nThis is because when $K>\\frac{4}{1-\\gamma}$, the variance term under the CTD setting approaches that under the NTD setting, allowing us to derive the tight sample complexity bound.\nSpecifically, following the proof of Corollary 5.12 in page 20 of [Rowland et al., 2024], if we take $K>\\frac{4}{1-\\gamma}$, we also have $\\frac{2}{K\\sqrt{1-\\gamma}}+\\frac{1}{K^2(1-\\gamma)^2}<\\frac{1}{2}\\sqrt{1-\\gamma}+\\frac{1}{16}<1$, which leads to the desired conclusion $\\|\\|(I-\\gamma P)^{-1}\\sigma(\\eta)\\|\\|\\leq\\frac{2}{1-\\gamma}$.\n\n> Question 2: Additionally, DCFP ... be beneficial.\n\nWe appreciate your valuable suggestion, and we will provide a\nfurther comparison with [Rowland et al., 2024]. The DCFP method proposed by\n[Rowland et al., 2024] can be seen as an extension of the certainty equivalence\nmethod (also called model-based approach) in traditional RL to the domain of\nDRL. In DCFP, one needs to estimate the distributional Bellman operator using\nall samples, and then substitute it for the ground-truth one in the distributional\nBellman equation to solve for the estimator of $\\eta^\\pi$This can be considered as a\nplug-in estimator, which is less similar to practical algorithms.\n\nIn contrast, the CTD analyzed in this paper can be viewed as an extension\nof TD. Compared to DCFP, CTD is more similar to practical algorithms and\ninvolves a more complex analysis.\n\nIn terms of proof techniques, [Rowland et al., 2024] introduced the important\ntools: the stochastic categorical CDF Bellman equation, to derive tight sample\ncomplexity bounds for the model-based method DCFP. The tools are also used\nin our paper. Compared to DCFP, the analysis of CTD (a model-free method)\nis more challenging. For instance, some probabilistic tools used for analyzing\nstochastic approximation problems in Hilbert spaces are not available, such as\nthe Freedman’s inequality. We overcame these difficulties and obtained tight\nsample complexity bounds. We believe that our findings will be of interest to\nresearchers working on distributional reinforcement learning and related areas.\n\nWe will revise the manuscript to include the discussion above, which we\nbelieve will provide a clearer context for our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "PUeIYELXIf", "reviewer": "Reviewer_KRno", "summary": "This paper studies the finite sample performance/non-asymptotic analysis of distributional temporal difference by providing a tighter (minimax optimal) bound than previous works. They propose the non-parametric distributional TD without incorporating any parameterization error. By leveraging the conclusion that the zero-mass signed measure space with the cramer metric is a Hilbert space, the authors propose a novel Freedman’s inequality (Theorem A.2) in the stochastic approximation literature, which is used to derive the sample complexity results for the distributional TD.", "questions": "How to show the bounds in Theorems 4.1 and 4.2 are minimax optimal? Is it possible to conduct some toy examples to verify them?", "limitations": "Some assumptions may not be clearly stated in the main content. It is not very clear in what detailed conditions the derived bounds are minimax optimal.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "* It is reasonable to investigate the non-asymptotic convergence of distributional TD.\n\n* The resulting conclusions in Theorems 4.1 and 4.2 are technically sound based on the stochastic approximation proof technique.", "weaknesses": "* The theoretical contribution is within a limited scope. Since the asymptotic and non-asymptotic convergence of distributional TD have already been investigated, this paper only contributes to providing tighter non-asymptotic bounds (by using a generative model), which is thus limited in the research scope. The current version is not well-motivated to me.\n\n* The proposed non-parametric distributional TD is impractical, which is mainly helpful for theoretical results. As CTD also follows the same updating rule, the theoretical results in Sections 4.1 and 4.2 apply in a parallel manner, which may not be novel.\n\n* The proposed Freedman’s inequality is one kind of invariant of its vanilla version, which may be sufficiently valued, as far as I can tell. If the authors think this inequality should be viewed as a main theoretical contribution, it should be emphasized and submitted as a stochastic approximation paper in applied probability instead of RL. As for the current version, I acknowledge that this inequality is useful for the finite sample analysis, but the authors are suggested to put more thought into how to posit this contribution more reasonably.\n\n* The writing needs substantial improvement. While it is basically clear, I find it hard to understand some parts of the paper. For example, CTD uses the approximation in (8), where $\\eta$ should be $\\hat{\\eta}$. Some related works are missing beyond QTD and CTD, such as kernel-based or sample-based TD methods [1].\n\n[1] Distributional Bellman Operators over Mean Embeddings (ICML 2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's time and effort in reviewing our paper.\nWe are glad to hear that the reviewer finds it reasonable to investigate the non-asymptotic convergence of distributional TD.\nWe are also happy to know the reviewer thinks our theoretical results are technically sound.\nBelow, we hope our rebuttal can address the reviewer's concerns.\n\n> Weakness 1: Since the asymptotic ... limited in the research scope.\n\nWe respectfully disagree with the reviewer on this point. From our perspective,\nmany important works in the ML theory community focus on improving existing\ntheoretical results. We would like to stress that our improvement is especially\nsignificant as we actually prove the near-minimax-optimal sample complexity\nbounds. We would also like to clarify the problem setting in our paper. The\nsetting we adopt is called the synchronous setting, which can be widely seen in\nthe RL theory literature [Wainwright, 2019, Li et al., 2024]. Such a setting is\nalso adopted in the asymptotic and non-asymptotic analysis of distributional TD\nas mentioned by the reviewer [Rowland et al., 2018, 2023, Bock and Heitzinger,\n2022]. See also the sample complexity table of DRL in https://openreview.net/forum?id=eWUM5hRYgH&noteId=5fyooKmeuH.\n\n> Weakness 2: The proposed ... may not be novel.\n\nAs we claim in the paper, NTD is only a simplified, conceptual algorithm and we use it to make our theoretical analysis more accessible to readers.\nIn contrast, the CTD algorithm is widely used in practical applications, and our non-asymptotic bounds help to build a solid theoretical understanding of its performance.\nWe feel a bit confused as the reviewer states that NTD is not significant because it is impractical and the analysis of CTD is not significant because it is parallel to the analysis of NTD.\nWe kindly request the reviewer to add further explanations as we feel we may misunderstand the reviewer's concerns.\n\n> Weakness 3: The proposed Freedman’s ... contribution more reasonably.\n\nWe are glad to hear the reviewer acknowledged that the proposed Freedman’s\ninequality can be a contribution of independent interest. But we kindly disagree\nwith the reviewer’s comment that the proposed Freedman’s inequality can be\nviewed as a main theoretical contribution only in a stochastic approximation\npaper in applied probability instead of RL. As the novel Freedman’s inequality\nis developed as a key technique tool for our theoretical analysis, we feel\nit can be an important theoretical contribution of this paper. And we thank\nthe reviewer for the suggestion that we should better posit such a contribution\n(possibly following the advice of Reviewer bMoZ to add it to the main paper).\n\n> Weakness 4: The writing ... sample-based TD methods.\n\nWe thank the reviewer for the comment about the typo and have fixed it.\nWe would appreciate it if the reviewer could point out the parts he/she feels are\nhard to understand, which could greatly help us to improve the quality of our\npaper. We are glad to include the paper [Wenliang et al., 2023] in our literature\nreview. We would also discuss more papers on sample-based TD as the reviewer\nsuggests.\n\n> Questions: How to show ... verify them?\n\nSince the value function $V^\\pi(s)=\\mathbb{E}_{G\\sim\\eta^\\pi(s)}\\left[G\\right]$, and $W_1$ metric satisfies \n\n$W_1(\\mu,\\nu)=\\sup_{f\\colon Lip(f) \\leq 1} \\|\\mathbb{E}[f(X)] -\\mathbb{E}[f(Y)] \\|$, where $X\\sim\\mu$ and $Y\\sim\\nu$,\n\nwe always have \n\n$ \\sup_{s}\\|\\widehat V^\\pi(s)-V^\\pi(s)\\|\\leq \\sup_{s}W_1(\\eta^\\pi(s),\\hat\\eta^\\pi(s))    $\n\nTherefore, any lower bound for the problem of standard policy evaluation would be a valid lower bound for the problem we consider.\nSince $\\widetilde{\\Omega}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ is a lower bound for the standard policy evaluation (see [Pananjady and Wainwright,\n2020], Theorem 2(b)), it is also a lower bound for our problem.\nTherefore, the $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2 (1-\\gamma)^3}\\right)$ upper bound we show matches the lower bound (up to logarithmic factors) and is thus near-minimax-optimal.\n\nWe would like to express our gratitude for your inquiry. We will revise the manuscript to clarify this point and ensure that our exposition is as precise and understandable as possible.\n\n> Limitations: Some assumptions ... minimax optimal.\n\nWe believe that we have clearly stated the theoretical assumptions in the main text, and the points made by other reviewers: \"This paper is very technically precise\" (bMoZ) and \"The paper clarifies the limitations by making assumptions for theoretical explanations\" (CFYY) also support this view.\nWe would be grateful if the reviewer could specify which assumptions have not been explicitly stated, as this would greatly assist us in enhancing the quality of our work.\nThe topic of minimax-optimality has already been discussed in our response to the questions part. \n\n## References\nMohammad Gheshlaghi Azar, R´emi Munos, and Hilbert J Kappen. Minimax pac\nbounds on the sample complexity of reinforcement learning with a generative\nmodel. Machine learning, 91:325–349, 2013.\n\nAshwin Pananjady and Martin J Wainwright. Instance-dependent ℓ∞-bounds\nfor policy evaluation in tabular reinforcement learning. IEEE Transactions on\nInformation Theory, 67(1):566–585, 2020.\n\nMartin J Wainwright. Stochastic approximation with cone-contractive operators:\nSharp ℓ∞-bounds for q-learning. arXiv preprint arXiv:1905.06265, 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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 reviewers are generally strongly positive that this paper makes substantive contributions to understanding the sample complexity of distributional RL that are enabled by interesting technical contributions. I believe this paper will be of broad interest to the community.
Decision: Accept (oral)