Statistical Efficiency of Distributional Temporal Difference Learning

Authors: yang  peng
liangyu  zhang
zhihua  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 05:49:45

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.

Main paper: 
 introduction: 
 In high-stake applications of reinforcement learning (RL), such as healthcare [Lavori and Dawson, 2004, Böck et al., 2022] and finance [Ghysels et al., 2005] , only considering the mean of returns is insufficient. It is necessary to take risk and uncertainties into consideration. Distributional reinforcement learning (DRL) Morimura et al. [2010] , Bellemare et al. [2017 Bellemare et al. [ , 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 η π for a given policy π, which is referred to as 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 infinite-dimensional object, via a computationally feasible finite-dimensional parametrization. This has led to the development of two special instances of distributional TD: categorical temporal difference learning (CTD) [Bellemare et al., 2017] and quantile temporal difference learning (QTD) [Dabney et al., 2018] . These algorithms provide computationally tractable parametrizations and updating schemes of the return distribution.Previous theoretical works have primarily focused on the asymptotic behaviors of distributional TD. In particular, Rowland et al. [2018] and Rowland et al. [2024a] showed the asymptotic convergences of CTD and QTD in the tabular case, respectively. A natural question arises: can we depict the statistical efficiency of distributional TD by non-asymptotic results similar to the classic TD algorithm [Li et al., 2024] ?In this paper, we manage to answer the above question affirmatively in the synchronous setting [Kakade, 2003 , Kearns et al., 2002] . Firstly, we introduce non-parametric distributional temporal difference learning (NTD) in Section 3, which is not practical but aids theoretical understanding. We show that O1 ε 2p (1-γ) 2p+14 iterations are sufficient to yield an estimator ηπ , such that the p-Wasserstein metric between ηπ and η π is less than ε with high probability (Theorem 4.1). This bound is minimax optimal (Theorem B.1) in the 1-Wasserstein metric case, if we neglect all logarithmic 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.1, we establish a Freedman's inequality in Hilbert spaces (Theorem A.2). We would believe it is of independent interest beyond the current work.Non-asymptotic results of DRL. Recently, there has been an emergence of work focusing on finite-sample/iteration results of the distributional policy evaluations. Wu et al. [2023] studied the offline distributional policy evaluation problem. They solved the problem via fitted likelihood estimation (FLE) inspired by the classic offline policy evaluation algorithm fitted Q evaluation (FQE), and provided a generalization bound in the p-Wasserstein metric case. Zhang et al. [2023] proposed to solve distributional policy evaluation by the model-based approach and derived corresponding sample complexity bounds, namely O1 ε 2p (1-γ) 2p+2in the p-Wasserstein metric case, and O1 ε 2 (1-γ) 4in both the Kolmogorov-Smirnov metric and total variation metric under different conditions. Rowland et al. [2024b] proposed direct categorical fixedpoint computation (DCFP), a model-based version of CTD, in which they constructed the estimator by solving a linear system directly instead of performing an iterative algorithm. They showed that the sample complexity of DCFP is O1 ε 2 (1-γ) 3in the 1-Wasserstein metric case by introducing the novel stochastic categorical CDF Bellman operator and equation. Their result matches the minimax lower bound (up to logarithmic factors) Ω 1 ε 2 (1-γ) 3 proposed in [Zhang et al., 2023] , which implies that learning the full return distribution can be as sample-efficient as learning just its expectation. It's worth noting that the algorithms analyzed in both [Zhang et al., 2023] and [Rowland et al., 2024b] are model-based, hence they are less similar to practical algorithms. While distributional TD analyzed in this paper, as a model-free method, is more practical, and also involves a 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 O1 ε 2 (1-γ) 4in the 1-Wasserstein metric case. Compared to [Böck and Heitzinger, 2022] , our work shows that even if we do not introduce any acceleration techniques to the original CTD algorithm, it is still possible to attain the near-minimax optimal sample complexity bounds. Thus, we give sharper bounds based on a simpler algorithm.Table 1 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 traditionalAlgorithms Task [Gheshlaghi Azar et al., 2013 ] O1 ε 2 (1-γ) 32 Background An infinite-horizon tabular Markov decision process (MDP) is defined by a 5-tuple M = S, A, P R , P, γ , where S represents a finite state space, A a finite action space, P R the distribution of rewards, P the transition dynamics, i.e., P R (•|s, a) ∈ ∆ ([0, 1]), P (•|s, a) ∈ ∆ (S) for any state action pair (s, a) ∈ S × A, and γ ∈ (0, 1) a discount factor. Here we use ∆(•) to represent the set of all probability distributions over some set. Given a policy π : S → ∆ (A) and an initial state s 0 = s ∈ S, a random trajectory {(s t , a t , t t ) ∞ t=0 } can be sampled from M :a t | s t ∼ π(• | s t ), r t | (s t , a t ) ∼ P R (• | s t , a t ), s t+1 | (s t , a t ) ∼ P (• | s t , a t ) for any t ∈ N. Given a trajectory, we define the return by G π (s) := ∞ t=0 γ t r t ∈ 0, 1 1-γ .We denote return distribution η π (s) as the probability distribution of G π (s), and η π := (η π (s)) s∈S . The expected return V π (s) = EG π (s) is the value function in the traditional RL setting. 
distributional bellman equation and operator: 
 Recall that the classic policy evaluation aims at computing the value functions V π . It is known that V π = (V π (s)) s∈S satisfy the Bellman equation. That is, for any s ∈ S,V π (s) = [T π (V π )] (s) = E a∼π(•|s),r∼PR(•|s,a),s ′ ∼P (•|s,a) [r + γV π (s ′ )] .(1)The operator T π : R S → R S is called the Bellman operator, and V π is a fixed point of T π .The task of distribution policy evaluation is finding η π given some fixed policy π. η π satisfies a distributional version of the Bellman equation (1). That is, for any s ∈ S,EQUATIONwhere b r,γ : R → R is an affine function defined by b r,γ (x) = r + γx. And f # µ is the push forward measure of µ through any function f : R → R, so that f # µ(A) = µ(f -1 (A)) for any Borel set A,where f -1 (A) := {x : f (x) ∈ A}. The operator T π : ∆ 0, 1 1-γ S → ∆ 0, 1 1-γis known as the distributional Bellman operator, and η π is a fixed point of T π . For notational simplicity, we denote ∆ 0, 1 1-γ as P from now on.A key property of the Bellman operator T π is that it is a γ-contraction w.r.t. the supreme norm (i.e. ℓ ∞ norm). However, before we can properly discuss the contraction properties of T π , we need to specify a metric d on P. And for any metric d on P, we denote d as the corresponding supreme metric on P S , i.e., d (η, η ′ ) := max s∈S d (η(s), η ′ (s)) for any η, η ′ ∈ P S . Suppose µ and ν are two probability distributions on R with finite p-moments for p ∈ [1, ∞]. The p-Wasserstein metric between µ and ν is defined asW p (µ, ν) := inf κ∈Γ(µ,ν) R 2 |x -y| p κ(dx, dy) 1/p . Each element κ ∈ Γ(µ, ν) is a coupling of µ and ν, i.e.,a joint distribution on R 2 with prescribed marginals µ and ν on each "axis." When p = 1 we haveW 1 (µ, ν) = R |F µ (x) -F ν (x)|dx, where F µ and F ν are the cumulative distribution function of µ and ν, respectively. It can be shown that T π is a γ-contraction w.r.t. the supreme p-Wasserstein metric Wp .Proposition 2.1. [Bellemare et al., 2023, Propositions 4.15] The distributional Bellman operator is a γ-contraction on P S w.r.t. the supreme p-Wassersteinmetric for p ∈ [1, ∞]. That is, for any η, η ′ ∈ P S , we have Wp (T π η, T π η ′ ) ≤ γ Wp (η, η ′ ).The ℓ p metric between µ and ν is defined asℓ p (µ, ν) = R |F µ (x) -F ν (x)| p dx 1 p for p ∈ [1, ∞),and T π is γ 1 p -contraction w.r.t. the supreme ℓ p metric lp . Proposition 2.2. [Bellemare et al., 2023, Propositions 4.20] The distributional Bellman operator is a γ 1 p -contraction on P S w.r.t. the supreme ℓ p metric for p ∈ [1, ∞). That is, for any η, η ′ ∈ P S , we have lp (T π η,T π η ′ ) ≤ γ 1 p lp (η, η ′ ).Note that the ℓ 1 metric coincides with the 1-Wasserstein metric. And the ℓ 2 metric is also called the Cramér metric, which plays an important role in subsequent analysis because the zero-mass signed measure space equipped with this metric M, • ℓ2 (defined in Section 5.1) is a Hilbert space5 . Thereby, we can apply Freedman's inequality in Hilbert spaces.Just as Freedman's inequality is essential for the theory of TD (Theorem 1 in [Li et al., 2024] ), a Hilbert space version of Freedman's inequality is indispensable for deriving the minimax nonasymptotic convergence bound for distributional TD. At the moment, we state a Hilbert space version of the original Freedman's inequality (Theorem 1.6 in [Freedman, 1975] ), and more detailed results can be found in Appendix A.Let X be a Hilbert space, {X i } n i=1 be an X -valued martingale difference sequence adapted to the filtration {F i } n i=1 , Y i := i j=1 X j be the corresponding martingale, and W i := i j=1 σ 2 j be the corresponding quadratic variation process. Here σ 2 j := E j-1 X j 2 , andE i [•] := E [•|F i ] denotes the conditional expectation.Theorem 2.1 (Freedman's inequality in Hilbert spaces). Suppose max i∈[n] X i ≤ b for some constant b > 0. Then, for any ε and σ > 0, the following inequality holdsP ∃k ∈ [n], s.t. Y k ≥ ε and W k ≤ σ 2 ≤ 2 exp - ε 2 /2 σ 2 + bε/3 . 
distributional temporal difference learning: 
 If the MDP M = S, A, P R , P, γ is known, and because V π is the fixed point of the contraction T π , V π can be evaluated via the famous dynamic programming (DP) algorithm. To be concrete, for any initialization V (0) ∈ R S , if we define the iteration sequenceV (k+1) = T π (V (k) ) for k ∈ N, we have lim k→∞ V (k) -V π ∞ = 0by the contraction mapping theorem (Proposition 4.7 in [Bellemare et al., 2023] ).Similarly, the distributional dynamic programming algorithm defines the iteration sequence as η (k+1) = T π η (k) for any initialization η (0) . In the same way, we havelim k→∞ Wp (η (k) , η π ) = 0 for p ∈ [1, ∞] and lim k→∞ lp (η (k) , η π ) = 0 for p ∈ [1, ∞).In most application scenarios, the transition dynamic P and reward distribution P R are unknown, and instead we can only get samples of P and P R in a streaming manner. In this paper, we assume a generative model [Kakade, 2003 , Kearns et al., 2002] is accessible, which generates independent samples for all states in each iteration, i.e., in the t-th iteration, we collect sample a t (s) ∼ π(•|s), s t (s) ∼ P (•|s, a t (s)), r t (s) ∼ P R (•|s, a t (s)) for each s ∈ S. Similar to TD [Sutton, 1988] in classic RL, distributional TD also employs the stochastic approximation (SA) [Robbins and Monro, 1951] technique to address the aforementioned problem and can be viewed as an approximate version of distributional DP.Non-parametric Distributional TD We first introduce non-parametric distributional temporal difference 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 parametrization. For any initialization η π 0 ∈ P S , the updating scheme is given byη π t = (1 -α t )η π t-1 + α t T π t η π t-1for any t ≥ 1. Here α t is the step size. The empirical Bellman operator at the t-th iteration T π t is defined as (T π t η) (s) = (b rt(s),γ ) # (η(s t+1 )), which is an unbiased estimator of (T π η) (s). It is evident that NTD is a SA modification of distributional 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:P K := K k=0 p k δ x k : p 0 , . . . , p K ≥ 0 , K k=0 p k = 1 , where K ∈ N, and 0 ≤ x 0 < • • • < x K ≤ 11-γ are fixed points of the support. For simplicity, we assume {x k } K k=0 are equally-spaced, i.e., x k = k K(1-γ) . We denote the gap between two points by ι K = 1 K(1-γ) . When updating the return distributions, we need to evaluate the ℓ 2 -projection of P K , Π K : P → P K , Π K µ := argmin μ∈PK ℓ 2 (µ, μ). It can be shown (Proposition 5.14 in [Bellemare et al., 2023] ) that the projection is uniquely given byEQUATION+ := max {x, 0} for any x ∈ R. It is known that Π K is non-expansive w.r.t. the Cramér metric (Lemma 5.23 in [Bellemare et al., 2023] ), i.e., ℓ 2 (Π K µ, Π K ν) ≤ ℓ 2 (µ, ν) for any µ, ν ∈ P. For any η ∈ P S , s ∈ S, we slightly abuse the notation and define (Π K η) (s) := Π K η(s). Π K is still non-expansive w.r.t. l2 . Hence T π,K := Π K T π is a √ γ-contraction w.r.t. l2 , we denote its unique fixed point as η π,K ∈ P S K . The approximation error induced by categorical parametrization is given by (Proposition 3 in Rowland et al. [2018] )l2 (η π , η π,K ) ≤ 1 √ K(1 -γ) , W1 (η π , η π,K ) ≤ 1 √ 1 -γ l2 (η π , η π,K ) ≤ 1 √ K(1 -γ) 3/2 . (3)Now, we are ready to give the updating scheme of CTD, given any initializationη π 0 ∈ P S K , η π t = (1 -α t )η π t-1 + α t Π K T π t η π t-1for any t ≥ 1. We can find that the only difference between CTD and NTD lies in the additional application of the projection operator Π K at each iteration in CTD. 
statistical analysis: 
 In this section, we state our main results. For both NTD and CTD, we give the non-asymptotic convergence rates of Wp (η π T , η π ) and l2 (η π T , η π ), respectively.We first provide a non-asymptotic convergence rate of W1 (η π T , η π ) for NTD, which is minimax optimal (Theorem B.1) up to logarithmic factors. Theorem 4.1 (Sample complexity of NTD in the 1-Wasserstein metric). Given any δ ∈ (0, 1) and ε ∈ (0, 1), let the initialization be η π 0 ∈ P S , the total update number T satisfyT ≥ C 1 log 3 T ε 2 (1 -γ) 3 log |S| T δ for some large universal constant C 1 > 1, i.e., T = O 1 ε 2 (1-γ) 3, and the step size α t satisfy 11 + c2(1- √ γ)t log t ≤ α t ≤ 1 1 + c3(1- √ γ)t log tfor some small universal constants c 2 > c 3 > 0. Then, with probability at least 1δ, the last iterate estimator satisfies W1 (η π T , η π ) ≤ ε.Because W1 (η π T , η π ) ≤ 1 1-γ always holds, we can translate the high probability bound to a mean error bound, that is,E W1 (η π T , η π ) ≤ ε(1 -δ) + δ 1 -γ ≤ 2εif we take δ ≤ ε(1γ). In the subsequent discussion, we will not state the mean error bound conclusions for the sake of brevity.The key idea of our proof is to first expand the error term W1 (η π T , η π ) over the time steps. Then it 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.1)W 1 (µ, ν) ≤ 1 √ 1-γ ℓ 2 (µ, ν), which allows us to analyze this error term in the Hilbert space (M, • ℓ2 ) defined in Section 5.1. Consequently, we can bound it using Freedman's inequality in the Hilbert space (Theorem A.2). A more detailed outline of proof can be found in Section 5.2.Wp (η, η ′ ) ≤ 1 (1-γ) 1-1 p W 1 p 1 (η, η ′ ) for any η, η ′ ∈ P S (Lemma E.1), we can derive that T = O 1 ε 2p (1-γ) 2p+1iterations are sufficient to ensure Wp (η π T , η π ) ≤ ε. As pointed out in the example after Corollary 3.1 in [Zhang et al., 2023] , when p > 1, the slow rate in terms of ε is inevitable without additional regularity conditions.Although the 1-Wasserstein metric cannot bound the Cramér metric properly, by making slight modifications to the proof we have the following non-asymptotic convergence rate of l2 (η π T , η π ). See Appendix C.5 for our proof.Corollary 4.1 (Sample complexity of NTD in the Cramér metric). Given any δ ∈ (0, 1) and ε ∈ (0, 1), let the initial value η π 0 ∈ P S , the total update number T satisfyT ≥ C 1 log 3 T ε 2 (1 -γ) 5/2 log |S| T δ for some large universal constant C 1 > 1, i.e., T = O 1 ε 2 (1-γ) 5/2, and the step size α t satisfy1 1 + c2(1- √ γ)t log t ≤ α t ≤ 1 1 + c3(1- √ γ)t log tfor some small universal constants c 2 > c 3 > 0. Then, with probability at least 1δ, the last iterate estimator satisfies l2 (η π T , η π ) ≤ ε.We first state a parallel result to Theorem 4.1.Theorem 4.2 (Sample complexity of CTD in the 1-Wasserstein metric). Given any δ ∈ (0, 1) and ε ∈ (0, 1), suppose K > 4 1-γ , the initial value η π 0 ∈ P S K , the total update number T satisfiesT ≥ C 1 log 3 T ε 2 (1 -γ) 3 log |S| T δ for some large universal constant C 1 > 1, i.e., T = O 1 ε 2 (1-γ) 3, and the step size α t satisfies1 1 + c2(1- √ γ)t log t ≤ α t ≤ 1 1 + c3(1- √ γ)t log tfor some small universal constants c 2 > c 3 > 0. Then, with probability at least 1δ, the last iterate estimator satisfies W1 η π T , η π,K ≤ ε 2 . Furthermore, according to the upper bound (3) of the approximation error W1 η π,K , η π , if we take K >4 ε 2 (1-γ) 3 , we have W1 (η π T , η π ) ≤ ε.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 not need the additional term introduced in the updating scheme of SCPE.The proof of this theorem is almost the same as that of Theorem 4.1, we outline the proof in Section 5.2. The W1 metric result can be translated into sample complexity bound O 1 ε 2p (1-γ) 2p+1 in the Wp metric. We comment that this theoretical result matches the sample complexity bound in the model-based setting [Rowland et al., 2024b] .As in the NTD setting, we have the following non-asymptotic convergence rate of l2 (η π T , η π ) as a corollary of Theorem 4.2. See Appendix C.5 for the proof.Corollary 4.2 (Sample complexity of CTD in the Cramér metric). For any given δ ∈ (0, 1) and ε ∈ (0, 1), suppose K > 4 1-γ , the initialization is η π 0 ∈ P S K , the total update number T satisfiesT ≥ C 1 log 3 T ε 2 (1 -γ) 5/2 log |S| T δ for some large universal constant C 1 > 1, i.e., T = O 1 ε 2 (1-γ) 5/2, and the step size α t satisfies1 1 + c2(1- √ γ)t log t ≤ α t ≤ 1 1 + c3(1- √ γ)t log tfor some small universal constants c 2 > c 3 > 0. Then, with probability at least 1δ, the last iterate estimator satisfies l2 η π T , η π,K ≤ ε 2 . Furthermore, according to the upper bound (3) of the approximation error l2 η π,K , η π , if we take K >4 ε 2 (1-γ) 2 , we have l2 (η π T , η π ) ≤ ε.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 conclusions 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to 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 is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors 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 to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to 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, it does not include experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
proof outlines: 
 In this section, we will outline the proofs of our main theoretical results (Theorem 4.1, Corollary 4.1, Theorem 4.2, and Corollary 4.2). Before diving into the details of the proofs, we first define some notation.To analyze the distance between the estimator and the ground-truth η π , we will work with the zeromass signed measure space M defined as followsM := µ : µ is a signed measure with |µ| (R) < ∞, µ(R) = 0, supp(µ) ⊆ [0, 1 1 -γ ] ,where |µ| is the total variation measure of µ, and supp(µ) is the support of µ. See [Bogachev, 2007] for more details about signed measures.For any µ ∈ M, we define its cumulative function asF µ (x) := µ[0, x). We can check that F µ is linear w.r.t. µ, that is, F αµ+βν = αF µ + βF ν for any α, β ∈ R, µ, ν ∈ M.To analyze the Cramér metric case, we define the following Cramér inner product on M:µ, ν ℓ2 := 1 1-γ 0 F µ (x)F ν (x)dx.It is easy to verify that •, • ℓ2 is indeed an inner product on M. The corresponding norm, called the Cramér norm, is given byµ ℓ2 = µ, µ ℓ2 = 1 1-γ 0 (F µ (x)) 2 dx. We have ν 1 -ν 2 ∈ M and ν 1 -ν 2 ℓ2 = ℓ 2 (ν 1 , ν 2 ) for any ν 1 , ν 2 ∈ P.The W 1 norm on M is defined asµ W1 := 1 1-γ 0 |F µ (x)| dx. We have ν 1 -ν 2 W1 = W 1 (ν 1 , ν 2 ) for any ν 1 , ν 2 ∈ P.We can extend the distributional Bellman operator T π and the Cramér projection operator Π K naturally to M S . Here, the product space M S is also a Banach space, and we use the supreme norm:η l2 := max s∈S η(s) ℓ2 , and η W1 := max s∈S η(s) W1 for any η ∈ M S . We denote by I the identity operator in M S .When the norm • is applied to A ∈ L(X ), where X is any Banach space, and L(X ) is the space of all bounded linear operators in X , we refer A to the operator norm of A, which is defined as A := sup η∈X , η =1 Aη . With this notation, L(X ) = {A : A is a linear operator mapping from X to X , and A < ∞}. Proposition 5.1. T π and Π K are linear operators in M S . Furthermore, T π l2 ≤ √ γ,T π W1 ≤ γ, Π K l2 = 1, and Π K W1 ≤ 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 Π K :T π ∈ L(M) S×S for any η ∈ M S , (T π η) (s) = a∈A,s ′ ∈S π(a | s)P (s ′ | s, a) 1 0 (b r,γ ) # η(s ′ )P R (dr | s, a) = s ′ ∈S T π (s, s ′ )η(s ′ ),whereT π (s, s ′ ) ∈ L(M) for any ν ∈ M, T π (s, s ′ )ν = a∈A π(a | s)P (s ′ | s, a) 1 0 (b r,γ ) # νP R (dr | s, a). It can be verified that T (s, s ′ ) ℓ2 ≤ √ γ a∈A π(a | s)P (s ′ | s, a) =: √ γP π (s ′ |s). Similarly, T (s, s ′ ) W1 ≤ γP π (s ′ |s), and Π K = diag Π K M s∈S ∈ L(M) S×S . With these represen- tations, Π K T π ∈ L(M)S×S can be interpreted as matrix multiplication, where the scalar multiplication is replaced by the composition of operators. It can be verified that(Π K T π ) (s, s ′ ) = Π K T π (s, s ′ ), and (Π K T π ) (s, s ′ ) ℓ2 ≤ √ γP π (s ′ |s).Remark 1: Although the spaces M, • ℓ2 and M, • W1 are not complete, we will use their completions to replace them without loss of generality, because the completeness property does not affect the non-asymptotic analysis. For simplicity, we still use M to denote the completion space. And according to the BLT theorem (Theorem 5.19 in [Hunter and Nachtergaele, 2001] ), any bounded linear operator can be extended to the completion space, and still preserves its operator norm. Theorems 4.1 and 4.2 For simplicity, we abbreviate both • l2 and• ℓ2 as • in this part. For all t ∈ [T ] := {1, 2, • • • , T }, we denote T t := T π t , T := T π , η := η π for NTD; T t := Π K T π t , T := Π K T π , η := η π,K for CTD; and η t := η π t , ∆ t := η t -η ∈ M Sfor both NTD and CTD. According to Lemma E.2, η t ∈ P S for NTD and η t ∈ P S K for CTD. Our goal is to bound the W1 norm of the error term ∆ T W1 . This can be achieved by bounding ∆ T , as∆ T W1 ≤ 1 √ 1-γ ∆ T .According to the updating rule, we have the error decomposition∆ t = η t -η = (1 -α t )η t-1 + α t T t η t-1 -η = (1 -α t )∆ t-1 + α t (T t η t-1 -T η) = (1 -α t )∆ t-1 + α t (T t -T ) η t-1 + α t T (η t-1 -η) = [(1 -α t )I + α t T ] ∆ t-1 + α t (T t -T ) η t-1 .Applying it recursively, we can further decompose the error into two terms∆ T = T t=1 [(1 -α t )I + α t T ] ∆ 0 (I) + T t=1 α t T i=t+1 [(1 -α i )I + α i T ] (T t -T ) η t-1 (II).Term (I) is an initial error term that becomes negligible when T is large because T is a contraction. Term (II) can be bounded via Freedman's inequality in the Hilbert space (Theorem A.2). Combining the two upper bound, we can establish a recurrence relation. Solving this relation will lead to the conclusion.We first establish the conclusion for step sizes that depend on T . Specifically, we considerT ≥ C 4 log 3 T ε 2 (1 -γ) 3 log |S| T δ , 1 1 + c5(1- √ γ)T log 2 T ≤ α t ≤ 1 1 + c6(1- √ γ)t log 2 T, where c 5 > c 6 > 0 are small constants satisfying c 5 c 6 ≤ 1 8 , and C 4 > 1 is a large constant depending only on c 5 and c 6 . As shown in Appendix C.1, once we have established the conclusion in this setting, we can recover the original conclusion stated in the theorem. Now, we introduce the following useful quantities involving step sizes and γβ (t) k :=    t i=1 1 -α i (1 - √ γ) , if k = 0, α k t i=k+1 1 -α i (1 - √ γ) , if 0 < k < t, α T , if k = t.The following lemma provides useful bounds for β (t)k . Lemma 5.1. Suppose c 5 c 6 ≤ 1 8 . Then, for all t ≥ T c6 log T , we have thatβ (t) k ≤ 1 T 2 , for 0 ≤ k ≤ t 2 ; β (t) k ≤ 2 log 3 T (1 - √ γ)T , for t 2 < k ≤ t.The proof can be found in Appendix C.2. From now on, we only consider t ≥ T c6 log T . The upper bound of term (I) is given by(I) ≤ t k=1 (1-α k )I+α k T ∆ 0 ≤ t k=1 ((1-α k )+α k √ γ) 1 √ 1-γ = β (t) 0 √ 1-γ ≤ 1 √ 1-γT 2 , where ∆ 0 ≤ 1 1-γ 0 dx = 1 √ 1-γ .As for term (II), we have the following upper bound with high probability by utilizing Freedman's inequality (Theorem A.2). Lemma 5.2. For any δ ∈ (0, 1), with probability at least 1δ, we have for all t ≥ T c6 log T , in the NTD case,t k=1 α k t i=k+1 [(1 -α i )I + α i T ] (T k -T ) η k-1 ≤ 34 log 3 T log |S|T δ (1 -γ) 2 T 1 + max k: t/2<k≤t ∆ k-1 W1 .The conclusion still holds for the CTD case if we take K ≥4 ε 2 (1-γ) 2 + 1.The proof can be found in Appendix C.3. Combining the two results, we find the following recurrence relation in terms of the W1 norm holds given the choice of T , with probability at least 1δ,for all t ≥ T c6 log T ∆ t W1 ≤ 1 √ 1 -γ ∆ t ≤ 35 log 3 T log |S|T δ (1 -γ) 3 T 1 + max k: t/2<k≤t ∆ k-1 W1 .In Theorem C.1, we solve the relation and obtain the error bound of the last iterate estimator:∆ T W1 ≤ C 7    log 3 T log |S|T δ (1 -γ) 3 T + log 3 T log |S|T δ (1 -γ) 3 T    ,where C 7 > 1 is a large universal constant depending on c 6 . Now, we can obtain the conclusion if takingC 4 ≥ 2C 2 7 and T ≥ C4 log 3 T ε 2 (1-γ) 3 log |S|T δ . 
conclusions: 
 In this paper we have studied the statistical performance of the distributional temporal difference learning (TD) from a non-asymptotic perspective. Specifically, we have considered two instances of distributional TD, namely, the non-parametric distributional TD (NTD) and the categorical distributional TD (CTD). For both NTD and CTD, we have shown that O1 ε 2p (1-γ) 2p+1iterations are sufficient to achieve a p-Wasserstein ε-optimal estimator, which is minimax optimal (up to logarithmic factors). We have established a novel Freedman'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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the 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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conform with NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 on theory, hence there is no negative societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 specific 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 the 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Freedman's inequality, proposed in [Freedman, 1975] , can be viewed as a Bernstein's inequality for martingales, which is crucial for analyzing stochastic approximation algorithms. Compared to the Azuma-Hoeffding inequality which only utilizes the boundedness of martingale difference sequences, Freedman's inequality incorporates second-order information, namely the quadratic variation (cumulative conditional variance) of martingales. This may leads to a sharper concentration result. It has various generalizations, such as matrix Freedman's inequality [Tropp, 2011] . However, to the best of our knowledge, a Freedman's inequality in Hilbert spaces has not been established yet. Just as Freedman's inequality is essential for the theory of TD (Theorem 1 in [Li et al., 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 in [Freedman, 1975] ). After that, we state a generalization of a more powerful version (Theorem 6 in [Li et al., 2024] ) to Hilbert spaces. We will provide self-contained proofs in Appendix A.1, primarily inspired by Theorem 3.2 in [Pinelis, 1994] . The necessary knowledge of martingale theory for the proofs can be found in any standard textbook, such as [Durrett, 2019] .Let X be a Hilbert space, {X i } n i=1 be an X -valued martingale difference sequence adapted to the filtration {F i } n i=1 , Y i := i j=1 X j be the corresponding martingale, W i := i j=1 σ 2 j be the corresponding quadratic variation process. Here σ 2 j := E j-1 X j 2 , andE i [•] := E [•|F i ] is the conditional expectation. Theorem A.1 (Freedman's inequality in Hilbert spaces). Suppose max i∈[n] X i ≤ b for some constant b > 0.Then, for any ε, σ > 0, the following inequality holdsEQUATIONNow, we are ready to state the generalization of Theorem 6 in [Li et al., 2024] to Hilbert spaces, which is used in our non-asymptotic analysis. Theorem A.2 (Freedman's inequality in Hilbert spaces with bounded quadratic variation). Suppose max i∈[n] X i ≤ b and W n ≤ σ 2 for some constant b, σ > 0. Then, for any δ ∈ (0, 1), and any positive integer H ≥ 1, the following inequality holds with probability at least 1δEQUATIONThe proof can be found in Appendix A.2.Remark 2: Theorem 2.1 can be straightforwardly extended to the case where ( X i ) n i=1 satisfies the Bernstein condition (Theorem 1.2A in [de la Pena, 1999] ), thereby relaxing the boundedness assumption on X i . Namely,E i-1 X i k ≤ 1 2 k!σ 2 i b k-2for some b > 0, and for all i ∈ [n], k ∈ {2, 3, • • •}. In this case, Freedman's inequality still holds, albeit with a worse constant.EQUATION)The proof only requires making appropriate modifications after the fifth line of Equation ( 12). Note that Bernstein condition holds if max i∈[n] X i ≤ b.A.1 Proof of Theorem 2.1Proof. For any λ > 0, t ∈ [0, 1] and j ∈[n], let φ(t) = φ j,λ (t) := E j-1 cosh (λ Y j-1 + tX j ) = E j-1 cosh (λu(t)), where u(t) := Y j-1 + tX j . We aim to use the Newton-Leibniz formula to establish the relationship between φ(1) = E j-1 cosh (λ Y j ) and φ(0) = cosh (λ Y j-1 ). This will allow us to construct a positive supermartingale(B i ) n i=0. By utilizing the positive supermartingale and optional stopping theorem, we can derive the desired concentration inequality.Firstly, we calculate the derivative of φ.EQUATIONEQUATIONφ ′ (0) = λE j-1 sinh (λu(0)) Y j-1 , X j u(0) = λ sinh (λ Y j-1 ) Y j-1 , E j-1 [X j ] Y j-1 = 0. (9)By utilizing Newton-Leibniz formula, we haveφ(1) = φ(0) + 1 0 φ ′ (s)ds = φ(0) + 1 0 s 0 φ ′′ (t)dtds = φ(0) + 1 0 (1 -t)φ ′′ (t)dt.(10) Now, we calculate the second order derivate of φ.EQUATIONwhere in the third line, we used u ′′ (t) =Xj 2 u(t)- Y j-1 +tX j ,X j u(t) 2 u 2 (t)≥ 0 by Cauchy-Schwarz inequality, and h(x) = x cosh(x)sinh(x) ≥ 0 for any x ≥ 0, the inequality holds because h(0) = 0 and h ′ (x) = x sinh(x) ≥ 0 for any x ≥ 0. In the fourth line, we used u 2 ′′ (t) = 2 (u ′ (t))2 + u ′′ (t)u(t) . In the fifth line, we usedu 2 ′′ (t) = d 2 dt 2 Y j-1 + tX j 2 = d dt (2 Y j-1 + tX j , X j ) = 2 X j 2 .And in the last line, we usedcosh (λ Y j-1 + tX j ) ≤ cosh (λ Y j-1 ) exp (λt X j ) , this holds since exp (λ Y j-1 + tX j ) ≤ exp {λ ( Y j-1 + t X j )} = exp (λ Y j-1 ) exp (λt X j ) , exp (-λ Y j-1 + tX j ) ≤ exp {-λ ( Y j-1 -t -X j )} = exp (-λ Y j-1 ) exp (λt X j ) .Hence, we can derive the following inequality for all j ∈ [n]EQUATIONwhich holds for any λ ∈ (0, 3 b ). In the fifth line, we used Taylor expansion e x = ∞ k=0 x k k! . In the sixth line, we used (k + 2)! ≥ 2(3 k ) and X j ≤ b. In the seventh line, we used Taylor expansionEQUATIONi.e., (B i ) n i=0 is positive supermartingale. By optional stopping theorem (Theorem 4.8.4 in [Durrett, 2019] ), for any stopping time τ , we haveE [B τ ] ≤ E [B 0 ] = 1.Let τ := inf {k ∈ [n] : Y k ≥ ε} be a stopping time, and inf ∅ := ∞. Define an eventEQUATION)then on A, we have τ < ∞, Y τ ≥ ε and W τ ≤ σ 2 , noting that W k is non-decreasing with k. Our goal is to provide an upper bound for P(A).EQUATIONwhere in the second line, we used Cauchy-Schwarz inequality. In the third line, we usedE [B τ ] ≤ 1.In the fourth line, we used Y τ ≥ ε and W τ ≤ σ 2 on A, and cosh(x) is increasing when x ≥ 0. In the last line, we used cosh(x) ≥ 1 2 e x . Hence for any λ ∈ (0, 3 b )EQUATIONwe can choose λ ⋆ = ε σ 2 +εb/3 ∈ (0, 3 b ), thenEQUATIONwhich is the desired conclusion.A.2 Proof of Theorem A.2Proof. According to Theorem 2.1, for any ε, σ > 0, we haveEQUATION)We can check that, when ε = 4σ 2 log 2 δ + 4 3 b log 2 δ , we have the upper bound on RHS is less than δ, henceEQUATION)Define the eventsH H := Y n ≥ 8 max W n , σ 2 2 H log 2H δ + 4 3 b log 2H δ , B 0,H := Y n ≥ 8 σ 2 2 H log 2H δ + 4 3 b log 2H δ and W n ≤ σ 2 2 H-1 B k,H := Y n ≥ 8 σ 2 2 k log 2H δ + 4 3 b log 2H δ and σ 2 2 k ≤ W n ≤ σ 2 2 k-1 , 1 ≤ k ≤ H -1. (20) Since W n ≤ σ 2 , we can verify that H H ⊆ 0≤k<H B k,H . By the inequality (19) with σ2 = σ 2 2 k-1and δ set to be δ H , we haveP (B k,H ) ≤ δ H for all k = 0, 1, • • • , H -1.By the union bound, we arrive at the conclusionEQUATIONIn this section, we still consider infinite-horizon tabular MDP defined in Section 2, and assume a generative model is accessible. For any positive integer D, we define M (D) as the set of all MDPs with state space size |S| = D. For any MDP M and policy π, we denote V π M as the corresponding value function, and η π M 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). For any positive integer D ≥ 3, and sample size T ≥ C 1-γ log D 2 , the following result holdsinf η sup M ∈M(D) sup π E W1 (η, η π M ) ≥ c (1 -γ) 3/2 log D 2 T .Here, c, C > 0 are universal constants, and the infimum η ∈ P D ranges over all measurable functions of T samples from the generative model.The theorem states that for any algorithm, there exist corresponding MDP M and policy π, such that to ensure E W1 (η, η π M ) ≤ ε for some ε > 0, at least Ω 1 ε 2 (1-γ) 3 samples are required.Proof of Theorem B.1. For any η ∈ P D , we define V(η) ∈ R D as the entry-wise expectation of η.It is easy to check that V(η π M ) = V π M . And recall the dual representation of 1-Wasserstein metric (Corollary 5.16 in [Villani et al., 2009] )EQUATIONwe have W1 (η,EQUATIONwhere the second inequality holds because V (η) ∈ R D is also a measurable function of T samples from the generative model, and the infimum V ∈ R D ranges over all measurable functions of T samples from the generative model. And the last inequality is due to Theorem 2(b) in [Pananjady and Wainwright, 2020] .We have shown that the conclusion holds forEQUATIONEQUATIONwhere c 5 c 6 ≤ 1 8 , c 5 > c 6 > 0 and C 4 > 0. Then for some c 2 > c 3 > 0 to be determined, now we assumeEQUATIONNext, we will show that if we consider the result of the T 2 -th iteration with this step size scheme as the initialization of a new iteration process, then the step sizes in the subsequent T 2 iterations lie in the previously established range. If this is done, the conclusion still holds if we choose T ≥ 2C4 log 3 T ε 2 (1-γ) 3 log |S|T δ , since the initialization η π T /2 ∈ P S (or P S K in the case of CTD) is independent of the samples obtained for T 2 < t ≤ T . For any T 2 < t ≤ T , we denote τ := t -T 2 , we can see that there exist c 2 > c 3 > 0, such that the last inequality in both of the following lines hold simultaneously, which is desired.EQUATIONandEQUATIONProof of Lemma 5.1.EQUATIONEQUATION)where in the last inequality, we used c 5 c 6 ≤ 1 8 .EQUATIONProof of Lemma 5.2. We will show that the inequality holds for each t ≥ T c6 log T and then apply the union bound. For any s ∈ S, we denoteEQUATIONwhere we omit the superscript (t) for brevity, then LHS in the lemma equals t k=1 ζ k for each t. Let F k denote the σ-field that contains all information up to time step k,EQUATION)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 to the definition of the empirical distributional Bellman operator.We hope to use Freedman'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.. The norm of the martingale difference ζ k (s) can be bounded as followζ k (s) ≤ ζ k ≤ α k t i=k+1 [(1 -α i )I + α i T ] (T k -T ) η k-1 ≤ α k t i=k+1 ((1 -α i ) + α i √ γ) 1 √ 1 -γ = β (t) k √ 1 -γ . (34) Hence, max k∈[t] ζ k (s) ≤ max k∈[t] β (t) k √ 1-γ ≤ 1 √ 1-γ max 1 T 2 , 2 log 3 T (1- √ γ)T ≤ 4 log 3 T (1-γ) 3/2 T =: b.Upper bound of quadratic variation. Now, let's calculate the quadratic variation.We first introduce some notations. For any k ∈ N, we denote Var(ξ) := E ξ(s)2 s∈S ∈ R S , Var k (ξ) := E k ξ(s) 2 s∈S ∈ R S for any random element ξ in M S .For any ξ ∈ M S , we define its one-step update Cramér variation as σ(ξ) := Var ( T -T )ξ ∈ R S , where T is a random operator and has the same distribution as T 1 .For any x, y ∈ R S , we say x ≤ y if x(s) ≤ y(s) for all s ∈ S. In this part, x :=x ∞ = max s∈S |x(s)|, √ x := x(s) s∈S . And for any U ∈ R S×S , U := U ∞ = sup x∈R S , x =1 U x = max s∈S s ′ ∈S |U (s, s ′ )|.We denote I ∈ R S×S as the identity matrix, 1 ∈ R S as the all-ones vector, and P := P π ∈ R S×S , i.e., P (s, s ′ ) := P π (s ′ |s) = a∈A π(a|s)P (s ′ |s, a).With these notations, the quadratic variation isW t := t k=1 Var k-1 (ζ k ).To bound the quadratic variation W t , we need to bound Var k-1 (ζ k ).Lemma C.1.Var k-1 (ζ k ) ≤ α k β (t) k t i=k+1 [(1 -α i )I + α i √ γP ] σ(η k-1 ).Hence, the quadratic variation W t can be bounded as followW t = t k=1 Var t-1 (ζ k ) ≤ t k=1 α k β (t) k t i=k+1 [(1 -α i )I + α i √ γP ] σ(η k-1 ) ≤ t/2 k=1 α k β (t) k t i=k+1 [(1 -α i )I + α i √ γP ] σ(η k-1 ) 1 + t k=t/2+1 α k β (t) k t i=k+1 [(1 -α i )I + α i √ γP ] σ(η k-1 ) ≤ t/2 k=1 β (t) k 2 1 1 -γ 1 + max k: t/2<k≤t β (t) k t k=t/2+1 α k t i=k+1 [(1 -α i )I + α i √ γP ] σ(η k-1 ) ≤ 1 2(1 -γ)T 3 1 + 2 log 3 T (1 - √ γ)T    t k=t/2+1 α k t i=k+1 [(1 -α i )I + α i √ γP ]    max k: t/2<k≤t σ(η k-1 ) ≤ 1 2(1 -γ)T 3 1 + 4 log 3 T (1 -γ)T (I - √ γP ) -1 max k: t/2<k≤tσ(η k-1 ),(35) where in the fourth line, we usedEQUATIONσ(η k-1 ) ≤ 1 1-γ 0 dx = 1 1 -γ .In the last line, we used the fact that max k: t/2≤k<t σ(η k-1 ) ≥ 0 and the following lemma:Lemma C.2. For any t ∈ N, (α i ) i∈[t] ∈ [0, 1] t , the following inequality holds entry-wise:EQUATION)According to (35), we have the following deterministic upper bound for W t = max s∈S W t (s),EQUATION)By applying Freedman's inequality (Theorem A.2) and utilizing the union bound over s ∈ S, we obtain with probability at least 1δ, for all t ∈ [T ] and s ∈ SEQUATIONwhere we used log8|S|T log 1 1-γ δ≤ 2 log |S|T δ the second line, which holds due to the choice of T . The following lemmas are required for deriving the upper bound, which hold for both cases of NTD and CTD.Lemma C.3. For any t ∈ [T ], σ(η t ) -σ(η) ≤ 4 ∆ t W1 1. Lemma C.4. (I - √ γP ) -1 σ(η) ≤ 4 1 -γ 1.Combining the upper bound with the two lemmas, we get the desired conclusionEQUATION) where in the last line, we used that, excluding the constant term, the first term is larger than the second term, given the choice of T ≥ C4 log 3 T ε 2 (1-γ) 3 log |S|T δ .Theorem C.1. Suppose for all t ≥ T c6 log T ,∆ t W1 ≤ 35 log 3 T log |S|T δ (1 -γ) 3 T 1 + max k: t/2<k≤t ∆ k-1 W1 .Then there exists some large universal constant C 7 > 0, such that∆ T W1 ≤ C 7    log 3 T log |S|T δ (1 -γ) 3 T + log 3 T log |S|T δ (1 -γ) 3 T    .Proof. For any k ≥ 0, we denoteEQUATIONfor 0 ≤ k ≤ log 2 (c 6 log T ). We can see that ∆ T W1 ≤ u k for any valid k. Hence, it suffices to show the upper bound holds for u k for any valid k. It can be verified that u 0 ≤ 1 1-γ , and for k ≥ 0EQUATION)We first show that once u k ≤ 1, the subsequent values of u k+l will also remain upper bounded by 1.EQUATION) if T ≥ 2450 log 3 T log |S|T δ (1-γ) 3.Let τ := inf {k : u k ≤ 1}, then for any k > τ , we haveEQUATION)For k ≤ τ , we have u k ≥ 1 and therebyEQUATIONi.e., log u k+1 -2 log a ≤ 1 2 (log u k -2 log a) .(EQUATIONApply it recursively, we haveEQUATIONi.e.,EQUATION)To sum up, for any k ≥ 0, u k+1 is always less than the sum of the upper bounds in cases of k > τ and k ≤ τ ,u k+1 ≤ a + a 2(1-1/2 k ) 1 (1 -γ) 1/2 k (49)Note that, a 2(1-1/2 k ) ≤ max {a, √ a}, and if we take k ≥ c 8 log log 1 1-γ for any constant c 8 , we have1 (1-γ) 1/2 k = O(1). We can take the constant c 8 small enough such that c 8 log log 1 1-γ < log 2 (c 6 log T ) (this can be done and c 8 is universal since 1 1-γ = o(T )), and thereby we can find a valid k ⋆ ≥ c 8 log log 1 1-γ + 1. ThenEQUATIONwhich is the desired conclusion, and C 7 is some large universal constant related to c 8 .The difference in the proof compared to Section 5.2 arises in Lemma 5.2 when we control term (II). Now we further bound the result in Lemma C.3 by the Cramér norm of the error term,EQUATIONIn the same way, we can derive the following recurrence relation: with probability at least 1δ, for all t ≥ T c6 log TEQUATIONBy repeating the reasoning of Theorem C.1, we can obtain the desired conclusion,EQUATIONwhich is less than ε if we takeC 4 ≥ 2C 2 7 and T ≥ C4 log 3 T ε 2 (1-γ) 5/2 log |S|T δ . C 7 > 1 is a large universal constant depending on c 6 . C.6 Proof of Lemma C.1Proof. We first introduce some notations. For any matrix of operators U ∈ L (M) S×S , we denoteU (s) = (U (s, s ′ )) s ′ ∈S ∈ L (M)S as the s-row of U . And for any ξ ∈ M S , we define the vectorinner product operation U (s)ξ := s ′ ∈S U (s, s ′ )ξ(s ′ ) ∈ M.We need the following lemma, which holds for both cases of NTD and CTD.Lemma C.5. For any ν ∈ M, n ∈ N,(α i ) i∈[n] ∈ [0, 1] n , let U n = n i=1 [(1 -α i )I + α i T ], U n = n i=1 (1 -α i )I + α i √ γP , u n = n i=1 (1 -α i ) + α i √ γ then for any s, s ′ ∈ S, we have U n (s, s ′ )ν 2 ≤ u n U n (s, s ′ ) ν 2 .Utilizing this lemma, we get the following result. Recall that T is a random operator and has the same distribution as T 1 . Then, for any non-random ξ ∈ M S ,EQUATIONwhere we used different rows of T are independent, and T (s′ )ξ is an unbiased estimator of T (s ′ )ξ ∈ M. Hence, Var U n ( T -T )ξ ≤ u n U n σ(ξ).EQUATIONEQUATIONwhere the inequality holds entry-wise since we can verify that all entries of (I -√ γP) -1 = ∞ k=0 √ γP k and (1 -α i )I + α i √ γP are non-negative. C.8 Proof of Lemma C.3Proof. For any s ∈ S,EQUATIONIn the case of NTD, T and T are γ-contraction w.r.t. the supreme 1-Wasserstein metric, henceEQUATIONIn the case of CTD, if we can show Π K is non-expansive w.r.t. 1-Wasserstein metric, the conclusion still holds. For any x, y ∈ 0, 1 1-γ such that x < y, we denote x ∈ [x k , x k+1 ) and y ∈ [x l , x l+1 ), then k ≤ l, by the definition of Π K , we haveEQUATIONEQUATION) If k = l, we can check that W 1 (Π K δ x , Π K δ y ) = ι K y-x ιK = y -x. If k < l, we have W 1 (Π K δ x , Π K δ y ) ≤ W 1 (Π K δ x , x k+1 ) + W 1 (x k+1 , x l ) + W 1 (x l , Π K δ y ) = (x k+1 -x) + (x l - x k+1 ) + (y -x x l ) = y -x.Hence, for any ν 1 , ν 2 ∈ P and for any transport plan κ ∈ Γ(ν 1 , ν 2 ), the previous results tell us the cost of the transport planΠ K κ ∈ Γ (Π K ν 1 , Π K ν 2 ) induced by Π K is no greater than the cost of κ. Consequently, W 1 (Π K ν 1 , Π K ν 2 ) ≤ W 1 (ν 1 , ν 2 ), i.e., Π K is non- expansive w.r.t. 1-Wasserstein metric, which is desired. C.9 Proof of Lemma C.4Proof. Firstly, we show that for any v ≥ 0, we haveEQUATIONIn the case of NTD, by Corollary D.1, we haveEQUATIONIn the case of CTD, by Corollary 5.12 in [Rowland et al., 2024b] , we haveEQUATIONgiven K > 4 1-γ .C.10 Proof of Lemma C.5Proof. We proof this result by induction. For n = 0, we have U 0 = I, U 0 = I, u 0 = 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,[(1 -α n )δ s,s ′ + α n T (s, s ′ )] µ 2 ≤ [(1 -α n ) + α n √ γ] [(1 -α n )δ s,s ′ + α n √ γP (s, s ′ )] µ 2 ,where δ s,s ′ = 1 if s = s ′ , and 0 otherwise.Proof. Let κ ⋆ ∈ Γ (φ, φ ′ ) be the optimal coupling between φ and φ ′ . The existence of κ ⋆ is guaranteed by Theorem 4.1 in [Villani et al., 2009] . And let the random element ξ = (ξ 1 , ξ 2 ) in P S 2 has the law κ ⋆ , where ξ 1 and ξ 2 are both random elements in P S . We denote T κ ⋆ :=EQUATIONBy the proposition and contraction mapping theorem, there exists a unique fixed point of T , we denote ψ ∈ ∆ P S as the fixed point. Hence, the stochastic distributional Bellman equation readsEQUATIONWe denote η ψ as the random element in P with law ψ, then T η ψ and η ψ have the same law. As shown in the following proposition, η ψ can be regarded as a noisy version of η.Proposition D.2.E [η ψ ] = η,where the expectation is regarded as the Bochner integral in the space of all finite measures on P S , which is a normed linear space equipped with Cramér metric as its norm.Proof.EQUATIONwhere we used T is independent ofη ψ . Since E [η ψ ] is the fixed point of T , we have E [η ψ ] = η.Based on the concepts of T and ψ, we can obtain the following second order distributional Bellman equation, which is similar to the classic second-order Bellman equation (Lemma 7 in [Gheshlaghi Azar et al., 2013] ).Recall the one-step Cramér variation σ(η) = E T η (s)η(s) Proof. For any s ∈ S,EQUATIONwhere the last equality holds since the cross term is zero as belowEQUATION)The first term in ( 71) is σ(s), we need to deal with the second term.E T η ψ (s) -T η (s) 2 =E E T η ψ (s) -T η (s) 2 η ψ =E E a(s)∼π(•|s),s ′ (s)∼P (•|s,a(s)),r(s)∼PR(•|s,a(s)) 1 1-γ 0 F (η ψ )(s ′ (s))xr γ -F η(s ′ (s))xr γ (73) Put these together, and we can arrive at the conclusion. Now, we can derive a tighter upper bound for (I -γP ) -1 σ(η) .Corollary D.1.(I -γP ) -1 σ(η) ≤ (I -γP ) -1 σ = Σ ≤ 1 1 -γ .Proof. Note that all entries of (I -γP) -1 = ∞ k=0 (γP ) k are positive, thereby (I -γP ) -1 σ(η) ≤ (I -γP ) -1 σ = Σ, and Σ(s) = E η ψ (s) -η(s) 2 ≤ 1 1-γ 0 dx = 11-γ for any s ∈ S.Lemma E.1 (Basic inequalities for metrics on the space of probability measures). For any µ, ν ∈ P,we have W 1 (µ, ν) ≤ 1 √ 1-γ ℓ 2 (µ, ν) and W p (µ, ν) ≤ 1 (1-γ) 1-1 p W 1 p 1 (µ, ν).Proof. By Cauchy-Schwarz inequality,EQUATIONAndEQUATION)Lemma E.2 (Range of η π t ). Suppose that α t ∈ [0, 1] for all t ≥ 0. Assume that η π 0 ∈ P S , then we have, for all t ≥ 0, η π t ∈ P S in the case of NTD. Similarly, assume that η π 0 ∈ P S K , then we have, for all t ≥ 0, η π t ∈ P S K 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 Π K : P S → P S K . We prove the result by induction. It is trivial that η π t ∈ P S for t = 0. Suppose that η π t-1 ∈ P S , recall the updating scheme of NTDEQUATIONIt is evident that P S is a convex set, considering that P S is a subset of the product signed measure space, which is a linear space. Therefore, we only need to show that T π t η π t-1 ∈ P S , which trivially holds since T π t is a random operator mapping from P S to P S , and η π t-1 ∈ P S . By applying the induction argument, we can arrive at the conclusion.Answer: [Yes] Justification: Our paper provide the full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.Throughout this paper, the notationf (•) = Õ (g(•)) (f (•) = Ω (g(•))) means that f (•) is order-wise no larger (smaller) than g(•), ignoring logarithmic factors poly(log |S| , log |A| , log( 1 1-γ ), log( 1 ε ), log( 1 δ )), as |S| , |A| , 1 1-γ , 1 ε , 1 δ → ∞ .In fact, the space M, • ℓ 2 is not complete. However, the completeness property does not affect the non-asymptotic analysis, see Section 5.1 for more details. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper presents last-iterate error bounds for distributional
temporal difference learning in the $W_p$ and Cramér metrics. The
results apply to a nonparametric/intractable distributional TD algorithm
(where return distributions can be represented exactly) and a tractable
projected distributional TD algorithm with finite categorical
parameterizations of return distributions. Using a novel Hilbert space
martingale inequality, the paper achieves tighter bounds than existing
results in the literature, as well as generalizations to more metric
spaces.
strength_weakness: strength_weakness: Many of the mathematical derivations were very quick and at times
difficult to follow (particularly, in the appendix). While the work of
Rowland et al. 2024 studies an algorithm that is less similar to
practical distributional RL methods, the conclusion of their work is
fairly similar (distributional RL has the same statistical efficiency as
expected-value RL). Their work does not cover all $W_p$ distances unlike
this work, and the dependence on $p$ is interesting; it is also
interesting, again, that this work provides a certificate for good
statistical efficiency with a stochastic approximation TD algorithm.
That said, the paper does not do an excellent job of motivating why this
novelty is exciting.

Moreover, since the Hilbert space Freedman inequality appears to be an
important contribution, I believe this should have been included in the
main text (even just the statement of the theorem).

Finally, I suspect there is a slight mathematical mistake in Appendix A,
though I don't expect it substantially changes the results; see the
Questions section.

## Minor Issues

"Temporal Difference" should really be "Temporal Difference Learning".

Line 159 says "the projection is unique and uniquely given by" – this is
a little redundant, should be either "the projection is uniquely given
by" or "the projection is unique and is given by".

Line 168 mentions the BLT theorem without any citation — it might be
nice to include a reference here, since "BLT theorem" may not be a
familiar term to some.

At the end of line 275, there are two periods.

On line 425, "forth" -\> "fourth".
questions: questions: In Theorem 4.2, you claim that the sample complexity bound does not
depend on the number of bins $K$. However, you also assume an explicit
lower bound on $K$, so naturally the sample complexity bound does depend
on $K$ in some capacity. Can anything be said about the sample
complexity (e.g., as a function of $K$) when
$K\leq 4\epsilon^{-2}(1-\gamma)^{-2}$?

Is the derivative computed on the second step of equation (29) correct?
It looks like you went from $\lambda$ to $\lambda^2$, but I believe only
on of the terms on the RHS should incur an extra $\lambda$ factor. My
computation is

\begin{align*}
\phi''(t) &= \lambda\mathbb{E}\_{j-1}\left\\{\frac{\mathrm{d}}{\mathrm{d}t}[\sin(\lambda u(t))u'(t)]\right\\}\\\\
&= \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)\\\\
&= \lambda\mathbb{E}\_{j-1}\left(\lambda (u'(t))^2\cosh(\lambda u(t)) + \sinh(\lambda u(t))u''(t)\right).
\end{align*}
limitations: limitations: Limitations are adequately discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

The 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.

Typos:
- In Line 105, the font for $T^{\pi}$ should be corrected to calligraphic.
- In lines 211,212, $K \geq \frac{4}{\epsilon^2 (1-\gamma)^3}$ should be $K \geq \frac{4}{\epsilon^2 (1-\gamma)^2}$.
- On line 275, the period is written twice.
- Line 510 should be corrected to $\log$, not $\log_2$.
questions: 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)$.

- 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: limitations: The paper clarifies the limitations by making assumptions for theoretical explanations.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.

* 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.

* 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.

* 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].

[1] Distributional Bellman Operators over Mean Embeddings (ICML 2024)
questions: 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: 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.

Comments: title: Thank you!
Please respond to the authors
Please respond to the authors
Thank you!
comment: We are deeply appreciative of your insightful and beneficial comments on our manuscript. We will incorporate your suggestions (especially modify the statements in line 205-213 including Theorem 4.2) in the revised version.
Thank you for the author's quick response. 
The theoretical results that I thought were ambiguous have been clarified sufficiently, and I hope this is reflected appropriately in the paper. Therefore, I will raise the score to 7.
Thank you very much for your response and new question. We sincerely apologize that our statements in Section 4.2 and replies were unclear and misleading. 
We would like to clarify this point in more details. 

In Theorem 4.2 (line 209), our conclusion is that when $K>\frac{4}{1-\gamma}$, we can choose step size $\alpha_t$ and total update steps $T$ independent of $K$ such that the $W_1$ distance between the estimator $\eta^\pi_T$ and
$\eta^{\pi,K}$ _(instead of $\eta^\pi$)_ $\bar{W}_1(\eta^\pi_T,\eta^{\pi,K})\leq \frac{\varepsilon}{2}$ (both are distributions represented by a finite number of $K$ atoms), we call this estimation error.
In line 210-212, we deal with the approximation error $\bar{W}_1(\eta^{\pi,K},\eta^\pi)$, which is less than $\frac{\epsilon}{2}$ when $K\geq\frac{4}{\varepsilon^2(1-\gamma)^3}$ (now the condition $K> \frac{4}{1-\gamma}$ in Theorem 4.2 naturally holds) according to Equation (7).
In summary, when $K\geq\frac{4}{\varepsilon^2(1-\gamma)^3}$, we have the desired conclusion $\bar{W}_1(\eta^\pi_T,\eta^\pi)\leq\bar{W}_1(\eta^\pi_T,\eta^{\pi,K})+\bar{W}_1(\eta^{\pi,K},\eta^\pi)\leq \epsilon$.

In short, Theorem 4.2 only deals with the estimation error $\bar{W}_1(\eta^\pi_T,\eta^{\pi,K})$, and line 210-212 deal with the approximation error $\bar{W}_1(\eta^{\pi,K},\eta^\pi)$.

We will revise the manuscript to clarify these points and add a more detailed explanation to ensure the argument is clear and logical for the readers.
We would like to express our gratitude once again for the reviewer's insightful question.
Thank you for the detailed response. 
However, I am still not convinced by the authors' answer to Question 1. 
According to the revised conclusion, it seems that it is possible for the number of atoms $K = 4/(1-\gamma) + 1$ to converge to a unique fixed point, $\eta^\pi$, for sufficiently large $T$, independent of the $\epsilon$.
However, $\eta^{\pi, K}$ is a distribution represented by a finite number of $K$ representations, leading to the incorrect conclusion that the discrepancy with $\eta^\pi$ can be reduced by $\epsilon$ with a fixed $K$. 
Could the author provide further clarification on this issue?
Hello reviewer KRno: The authors have responded to your comments. I would expect you to respond in kind.
Hello reviewer CFYY: The authors have responded to your comments. I would expect you to respond in kind.
We would like to express our sincere gratitude again for your constructive and valuable comments suggestions on our paper. We will incorporate the suggestions (especially add more explanations to make our proof easier to follow) in the revised version.
Thanks to the reviewers for their detailed response. I think this paper makes a really nice contribution to the analysis of distributional TD (especially once the proofs are made easier to follow), and I will raise my score to reflect this.