Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learning

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learning

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learning Zijie Cheng∗

Yang Peng†

Zhihua Zhang‡

July 10, 2026

arXiv:2607.08444v1 [stat.ML] 9 Jul 2026

Abstract In this paper, we study quantile-based distributional reinforcement learning from the perspective of statistical efficiency. We focus on distributional policy evaluation, whose goal is to characterize the return distribution, namely the distribution of discounted cumulative rewards under a given policy. To obtain a finite-dimensional representation of the return distribution, we consider the quantile fixed point ηm induced by the quantile-projected distributional Bellman equation. Assuming access to a generative model, we construct a certainty-equivalence estimator pnq

ηm based on an empirical Markov decision process. For a fixed number of quantiles m, we pnq

establish a non-asymptotic error bound for ηm and ηm under the supremum W8 metric, showing a r m{nq with respect to the number of quantiles m and the that the estimation error scales as Op sample size n. This implies that the quantile-based distributional policy evaluation problem can ? be solved with sample efficiency, achieving the optimal parametric n convergence rate. We ? pnq further derive the asymptotic distribution of the standardized quantile parameters npθm ´ θm q and characterize the semiparametric efficiency bound, which is attained by our estimator. Beyond the fixed-dimensional setting, we investigate the asymptotic regime in which the number of quantiles diverges. We characterize the limit covariance structure and show that it matches the semiparametric efficiency bound of the underlying nonparametric model for distributional policy evaluation, showing that quantile-based estimators remain asymptotically efficient in the infinite-dimensional limit. Finally, we establish a Berry–Esseen theorem for smooth functionals ? pnq npηm psq ´ ηm psqqf , thereby providing a foundation for statistically valid inference on a broad class of functionals of the quantile-projected return distribution. ∗

School of Mathematical Sciences, Peking University; email: [email protected]. Yau Mathematical Sciences Center, Tsinghua University; email: [email protected]. ‡ School of Mathematical Sciences, Peking University; email: [email protected]. †

Contents 1 Introduction

1.1

Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Preliminaries

2.1

Problem Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

Metrics on the Space of Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

Distributional Bellman Operator and Quantile Projection Operator . . . . . . . . . .

2.4

Main Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Main Results

3.1 The Quantile Fixed Point Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2

Non-asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4

Limiting Covariance Structure and Efficiency . . . . . . . . . . . . . . . . . . . . . .

3.5

Berry–Esseen Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Proof Outlines

4.1 Analysis of Non-asymptotic Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Analysis of Asymptotic Distribution and Efficiency . . . . . . . . . . . . . . . . . . .

4.3 Analysis of Limiting Covariance Structure and Efficiency . . . . . . . . . . . . . . . .

4.4 Analysis of Berry–Esseen Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Numerical Experiments

5.1

Experimental Setup

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2

Finite-sample Convergence Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Asymptotic Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Validity of Inferential Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Conclusions

A Preliminary Lemmas

A.1 Proof of Proposition 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.2 Other Preliminary Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B Omitted Proofs of Non-asymptotic Analysis

C Omitted Proofs of Asymptotic Analysis

C.1 Proof of Lemma 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.2 Proof of Lemma 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.3 Proof of Lemma 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C.4 Proof of Lemma 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D Omitted Proofs of Limiting Covariance Structure D.1 Proof of Proposition 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.2 Proof of Proposition 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.3 Proof of Lemma 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.4 Proof of Lemma 4.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.5 Proof of Lemma 4.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.6 Proof of Lemma 4.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E Omitted Proofs of Berry–Esseen Bound

E.1 Proof of Lemma 4.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E.2 Proof of Lemma 4.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E.3 Proof of Lemma 4.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

F Technical Lemmas

Introduction

Reinforcement learning has achieved substantial progress across a wide range of domains, including game-playing [44, 53], robotics [22], and large language models [32, 31]. In the classical formulation of reinforcement learning based on the reward hypothesis [46, 47], policy performance is evaluated through expected returns (i.e., the expected discounted cumulative reward). While this criterion provides a principled objective for sequential decision-making, it ignores the distributional characteristics of returns, such as variability, tail risk, and higher-order distributional information. Such considerations are important in many real-world applications. In healthcare, for instance, one is concerned not only with average outcomes but also with adverse or long-tail effects of dynamic 3

treatment regimes, as poor outcomes may have severe consequences for patients [25]. In financial decision-making, investors must balance return and risk, since higher expected returns are typically associated with greater uncertainty [16]. Distributional reinforcement learning [29, 2] generalizes the classical expected-return framework by characterizing the full distribution of return rather than only its expectation. This distributional perspective provides a richer description of uncertainty in the performance of learning agents, capturing variability arising from both the stochastic nature of environments and the randomness induced by the agent’s policy. However, return distributions are generally infinite-dimensional objects, and hence cannot be represented or learned exactly. This motivates finite-dimensional approximations of return distributions, among which categorical and quantile-based representations are two prominent choices. In particular, a widely-used family of algorithms for distributional reinforcement learning is based on the notion of quantile representations, an approach that originated with Dabney et al. [12]. By approximating the return distribution through a finite collection of quantiles, quantile representations provide a flexible and computationally tractable approximation while preserving key distributional information. As a result, quantile-based approaches have been widely adopted in practice and have become a standard paradigm in modern distributional reinforcement learning, underpinning methods such as quantile regression deep Q-network (QR-DQN) [12], implicit quantile network (IQN) [11], and non-crossing quantile regression method [58]. This paradigm has also been successfully applied in a range of settings, including high-altitude balloon guidance [3], robotic manipulation [5], and benchmark simulated domains such as the Arcade Learning Environment [12, 11]. Despite the empirical success of quantile-based distributional reinforcement learning, its statistical foundations remain relatively underdeveloped, with limited understanding of the sampling variability and asymptotic behavior of learned return quantiles. In practical reinforcement learning problems, the return distribution is determined by unknown transition dynamicsand reward distributions, and therefore should be inferred from finite data. This naturally raises a fundamental statistical question: can quantile-based representations support statistically efficient estimation and inference for return distributions? In particular, while quantile approximations provide a tractable finitedimensional parametrization of distributional reinforcement learning, it remains unclear whether the resulting estimators admit finite-sample guarantees, asymptotically valid inferential procedures, and, more fundamentally, whether the statistical efficiency of the original infinite-dimensional problem is preserved under finite-dimensional parametrization. In this paper, we address these questions 4

through a systematic study of estimation and inference for quantile distributional reinforcement learning. From a theoretical perspective, the quantile setting is fundamentally different from the categorical setting. In categorical distributional reinforcement learning, the support locations are fixed and the parametrization is described by a finite-dimensional probability vector. As a result, the corresponding categorical-projected Bellman update acts linearly on the probability vectors, which makes it amenable to tools developed for linear stochastic approximation. In contrast, quantile-based methods have a rather different structure. They parameterize return distributions through inverse distribution functions, incurring an intrinsically nonlinear dependence between the parameters and the underlying distribution. Moreover, the quantile Bellman equation involves non-smooth and asymmetric operations arising from quantile projection and quantile loss. Perturbations of the quantile parameters can affect the induced distribution through indicator-type terms, and errors across different quantile levels may interact nonlinearly. Consequently, classical techniques developed for linear projected operators, as well as many existing results for smooth nonlinear stochastic approximation, do not directly apply. These structural differences give rise to a new class of statistical and analytical challenges. To address them, we develop a unified theoretical framework that characterizes both the finite-sample and asymptotic behavior of quantile-based distributional reinforcement learning estimators.

1.1

Our Contributions

In this paper, we focus on the problem of distributional policy evaluation with quantile parametrization, where the goal is to estimate the return distribution of a given policy using a finite-dimensional quantile representation. We consider a γ-discounted infinite-horizon Markov decision process (MDP) in the tabular setting, where the state space S and the action space A are finite. Given a policy π and quantile level m, let ηm denote the unique fixed point of the projected distributional Bellman equation η “ Πm T π η. Here, Πm represents the quantile projection operator and T π represents the distributional Bellman operator. Our goal is to estimate ηm when the underlying MDP is unknown. We assume that both the distribution of the random reward and the transition probability of the MDP are unknown. Given an offline dataset consisting of n|S||A| samples collected from a generative model, we construct an pnq

xpnq with empirical reward distribution P p and empirical transition kernel Pppnq . empirical MDP M R pnq

Following the certainty-equivalence principle [45, 48], we estimate ηm by the fixed point ηm of the 5

empirical projected distributional Bellman operator Πm Tpnπ , where Tpnπ is the distributional Bellman pnq

xpnq . We refer to ηm as the quantile fixed point estimator. operator associated with M pnq

In this paper, we analyze the statistical properties of the quantile fixed point estimator ηm . Our contributions are summarized as follows, including non-asymptotic guarantees, asymptotic inference, and non-asymptotic Gaussian approximation results, all of which are new to the best of our knowledge. We first establish non-asymptotic estimation guarantees for quantile distributional policy evaluation in Theorem 3.1. Under mild regularity conditions, we prove that the estimation error a pnq r m{nq with respect to m and n. This implies a sample comsupsPS W8 pηm psq, ηm psqq scales as Op ´2 q up to problem-dependent constants. In addition, we provide a non-asymptotic r plexity of Opmε

upper bound on the approximation error induced by quantile discretization in Theorem 3.2, which explicitly characterizes the dependence on the number of quantiles m through the modulus of continuity of the return distribution. We next develop an asymptotic inference theory for quantile distributional policy evaluation. pnq

pnq

Denoting the quantile parameters of ηm and ηm by θm and θm , respectively, we prove in Theorem 3.3 ? pnq that npθm ´ θm q converges weakly to a Gaussian distribution and that the resulting asymptotic covariance matrix attains the semiparametric efficiency bound. As a consequence, for any smooth test ? pnq function f and state s, we establish the asymptotic normality of the functional npηm psq ´ ηm psqqf 2 with asymptotic variance σm,f,s , and construct asymptotically valid confidence intervals for these

functionals. Beyond asymptotic normality, we investigate the behavior of the covariance structure as the 2 quantization level increases. In Theorem 3.4, we prove that σm,f,s converges to a well-defined 2 as m Ñ 8 and characterize this limit through a pair of operators infinite-dimensional limit σf,s 2 coincides associated with the quantile Bellman equation. More importantly, we show that σf,s

exactly with the semiparametric efficiency bound for estimating the functional η π psqf of the infinitedimensional return distribution η π psq. Consequently, the sequence of efficient finite-dimensional quantile estimators preserves asymptotic efficiency in the infinite-dimensional limit. This establishes a rigorous connection between quantile-based approximation and statistically optimal inference, showing that quantile parametrization introduces no asymptotic efficiency loss while providing a tractable finite-dimensional representation. pnq ´1 ? Finally, we establish a Berry–Esseen bound for the scaled functional σm,f,s npηm psq ´ ηm psqqf

in Theorem 3.5, quantifying the rate of convergence to the Gaussian distribution. Specifically, under 6

some regularity conditions, we prove that ˇ „ ? ´ ˇ ȷ ¯ ˇ ˇ n pnq r 9{4 n´1{4 q, ηm psq ´ ηm psq f ď t ´ Φptqˇˇ “ Opm sup ˇˇP σ m,f,s tPR where Φp¨q is the cumulative distribution function of the standard Gaussian distribution. The n´1{4 rate reflects the intrinsic non-smoothness of the quantile projection operator, which induces indicator functions in the fixed-point equation. From a technical perspective, our analysis develops a unified statistical treatment of quantilebased distributional reinforcement learning. The main difficulty stems from the fact that the quantile projected Bellman equation defines an implicitly specified, non-smooth fixed point system. We overcome this challenge by developing a Z-estimation formulation of the quantile Bellman fixed point, which allows us to derive non-asymptotic error bounds and asymptotic properties for the resulting estimator. A second technical challenge comes from the diverging-dimensional nature of the quantile parametrization. To address this issue, we introduce an operator embedding framework based on averaging and interpolation maps between finite-dimensional quantile vectors and functions in a Hilbert space. This allows us to establish operator-level convergence as m Ñ 8 and to connect the resulting limit with the semiparametric efficiency bound of the original distributional policy evaluation problem. Finally, we develop a nonlinear Berry–Esseen expansion for smooth functionals of the implicit fixed-point estimator. Since the estimator does not admit a Bahadur representation, classical quantile process techniques are not applicable. We instead construct a stochastic expansion around the fixed-point equation and control the resulting nonlinear remainder terms induced by the r ´1{4 q Gaussian approximation rate. Bellman operator, yielding an explicit Opn

1.2

Related Works

Distributional Reinforcement Learning. Distributional reinforcement learning has achieved remarkable success in fields such as communications [18], transportation systems [30], and algorithm discovery [14]. A variety of approaches have been proposed to represent return distributions, including categorical representations [2], quantile representations [12], and generative-model-based representations [15, 13]. Among these approaches, quantile representations have become one of the most widely studied paradigms. Starting from the quantile temporal-difference algorithm [12], subsequent works developed more flexible quantile parametrizations through implicit quantile networks [11] and fully parameterized quantile functions [55], among many other variants. 7

Despite the empirical success, theoretical understanding of distributional reinforcement learning remains limited. Early theoretical studies mainly focused on the convergence properties of distributional Bellman operators and distributional temporal-difference learning algorithms. For categorical representations, Rowland et al. [37] provided the first asymptotic convergence analysis for categorical temporal-difference learning and established its consistency. Based on this line of work, Peng et al. [33] derived non-asymptotic convergence rates and sample complexity guarantees for categorical distributional reinforcement learning, while Peng et al. [34] further characterized its finite-sample behavior under linear function approximation. More recently, Wu et al. [54] proposed a likelihood-based framework for offline distributional reinforcement learning and established non-asymptotic estimation guarantees. For quantile-based methods, Rowland et al. [38] extended the asymptotic convergence analysis to quantile temporal-difference learning and established corresponding consistency results. However, their convergence analysis is asymptotic and does not consider sample complexities as well as asymptotic distributions. Separately, Rowland et al. [39] decompose the estimation error of quantile temporal-difference learning into fixed-point bias and finite-sample variance, showing that it can outperform classical temporal-difference learning for expected return estimation. Statistical Analysis of Reinforcement Learning. Statistical analysis in the context of reinforcement learning has drawn growing interest in the community. Existing works have developed a rich set of tools for uncertainty quantification and statistical inference for value functions. Thomas et al. [49] and Jiang and Li [20] proposed high-confidence bounds for value functions in the setting of off-policy evaluation. Hao et al. [17] devised a bootstrapping procedure to perform statistical inference in off-policy evaluation. Yang et al. [56] investigated the asymptotic behavior of distributionally robust value functions and constructed asymptotically valid confidence bounds. Shi et al. [43] modeled the value function with the series/sieve methods and devised confidence intervals for value functions in both the settings of policy evaluation and policy learning. Zhu et al. [59] also constructed asymptotically tight confidence intervals for learned (optimal) value functions. Li et al. [27] and Li et al. [26] considered online statistical inference for value functions in an online reinforcement learning setting. Comparatively fewer works study statistical properties of return distributions and other distributional functionals. Chandak et al. [8] and Huang et al. [19] proposed procedures for estimating cumulative distribution functions and constructing confidence bands. More recently, Qi et al. [36] investigated distributional off-policy evaluation and established finite-sample guarantees under of-

fline data. Zhang et al. [57] studied model-based estimation and statistical inference for return distributions under a generative model setting, establishing non-asymptotic convergence rates and asymptotic normality results. Compared to their work, we focus on quantile parametrizations of return distributions, where the nonlinear quantile projection operator introduces additional analytical challenges absent in nonparametric distribution estimation. Berry–Esseen Bounds for Quantile Estimators. Berry–Esseen bounds for quantile estimators have been extensively studied in the statistics literature. Bahadur–Kiefer representation [1, 21] r ´3{4 q, provided a linear expansion of sample quantiles with a stochastic remainder of order Opn which is fundamental in developing refined probabilistic approximations for quantile estimators. [24] obtained a Opn´1{2 q Berry–Esseen bound for sample quantiles under weakly dependent conditions, relying on the expression of sample quantiles in terms of the empirical distribution function. For quantile regression estimators, Koenker [23] developed a Bahadur representation. Their result was later sharpened to Opplog nq3{2 n´1{2 q Berry–Esseen bounds for regression quantile processes in [35], based on density-level approximation of the estimator whose distribution is generated by the empirical distribution. More recently, Bahadur-type representations have also been developed for algorithmic quantile estimators arising from stochastic optimization procedures. For example, Chen et al. [9] established a Bahadur representation for stochastic gradient-based quantile estimation via a smoothed loss formulation. However, these results rely heavily on the special structure of classical quantile estimators, where the estimator admits an explicit representation in terms of the empirical distribution function. In contrast, the quantile parameters considered in this paper are defined implicitly through a projected Bellman fixed-point equation, and standard Bahadur-type representations are not available. The remainder of this paper is organized as follows. In Section 2, we introduce some basic concepts of distributional reinforcement learning. In Section 3, we present our statistical analysis of quantile distributional reinforcement learning. In Section 4, we provide an outlined proof of results in Section 3. In Section 5, we verify our theoretical findings through numerical simulations. We conclude our work in Section 6. Details of the proof are given in the appendices.

Preliminaries

In this section, we introduce the necessary background for our work. We review the Markov decision process in Section 2.1, followed by metrics on the space of measures in Section 2.2. We 9

introduce distributional Bellman operator and quantile projection operator in Section 2.3. Finally, in Section 2.4, we present the assumptions under which our main theoretical results are established.

2.1

Problem Setup

We consider a discounted Markov decision process (MDP) specified by the tuple M “ xS, A, PR , P, γy, where S and A are finite state space and finite action space respectively, PR : S ˆ A Ñ ∆pr0, 1sq is the distribution of rewards, P : S ˆ A Ñ ∆pSq is the transition probability, and γ P p0, 1q is the discount factor. Here ∆p¨q denotes the set of probability distributions over some set. For a fixed policy π : S Ñ ∆pAq and an initial state S0 “ s P S, a random trajectory tpSt , At , Rt qu8 t“0 can be sampled from the MDP using the following procedure: At | St „ πp¨ | St q, Rt | pSt , At q „ PR p¨ | St , At q, St`1 | pSt , At q „ P p¨ | St , At q. The return of such a trajectory starting from state s is defined as the random variable Gπ psq –

8 ÿ

γ t Rt ,

t“0

which is bounded almost surely by r0, p1 ´ γq´1 s. The value function V π psq is defined by the expected return ErGπ psqs. We further denote by η π psq P ∆pr0, p1 ´ γq´1 sq the distribution of Gπ psq, and denote η π “ pη π psqqsPS for the collection of return distributions across all states.

2.2

Metrics on the Space of Measures

Denote the space of all probability distributions on R as P.

For µ P P, the cumulative

distribution function is defined as Fµ pxq “ µp´8, xs, and the quantile function is defined as Fµ´1 pτ q “ inftx : Fµ pxq ě τ u. For 1 ď p ă 8 and µ, ν P P, the p-Wasserstein metric between µ and ν is defined as

ˆż 1 Wp pµ, νq “

˙1{p ˇ ´1 ˇp ´1 ˇFµ ptq ´ Fν ptqˇ dt ,

and the 8-Wasserstein metric is defined as ˇ ˇ W8 pµ, νq “ sup ˇFµ´1 ptq ´ Fν´1 ptqˇ . tPr0,1s

Suppose µ and ν have cumulative distribution functions Fµ and Fν , respectively. In the case of p “ 1 we have ż W1 pµ, νq “

|Fµ pxq ´ Fν pxq|dx. R

The Kolmogorov–Smirnov metric (KS metric) is defined as KSpµ, νq “ sup |Fµ pxq ´ Fν pxq| . xPR

Moreover, for any extended metric d : P ˆ P Ñ r0, 8s, we can define its supremum extension d¯: P S ˆ P S Ñ r0, 8s as ¯ η 1 q “ sup dpηpsq, η 1 psqq, dpη, sPS

which is an extended metric on P S .

2.3

Distributional Bellman Operator and Quantile Projection Operator

aPA

(1)

aPA,s1 PS

The operator T π : RS Ñ RS is referred to as the Bellman operator, and Equation (1) characterizes V π as its unique fixed point. An analogous relationship holds for the return distributions η π , known as the distributional Bellman equation. That is, for each s P S, η π psq “ rT π η π s psq ” ı – EA„πp¨|sq,R„PR p¨|s,Aq,S 1 „P p¨|s,Aq pbR,γ q# η π pS 1 q ż1 ÿ 1 pbr,γ q# η π ps1 qPR pdr | s, aq. “ πpa | sqP ps | s, aq 0

aPA,s1 PS

Here br,γ : R Ñ R denotes the affine map br,γ pxq “ r ` γx, and g# µ is the pushforward of a measure µ ş1 under g, defined by g# µpBq “ µpg ´1 pBqq for all Borel sets B. The integral 0 pbr,γ q# η π ps1 qPR pdr | s, aq 11

is defined in the sense that for any Borel set B, „ż 1 0

ȷ ż1” ı pbr,γ q# η π ps1 q pBqPR pdr | s, aq. pbr,γ q# η π ps1 qPR pdr | s, aq pBq “ 0

Recall that P is the space of all probability measures on R, and T π : P Ñ P is referred to as the distributional Bellman operator, of which the fixed point is the return distribution η π . Because the exact distribution η π is infinite-dimensional and cannot be computed exactly, we approximate it using a quantile-parameterized distribution. The space of all quantile-parametrized probability distributions is defined as # Pm –

+ m 1 ÿ J m δx | x “ px1 , . . . , xm q P R , x1 ď . . . ď xm , νx “ m i“1 i

which is a mixture of Dirac measures and m P N. We define the quantile projection operator Πm : P Ñ Pm as

Πm ν “

1 ÿ δ ´1 , m i“1 Fν pτi q

S where τi “ 2i´1 2m . We lift Πm to the product space P by defining pΠm ηqpsq – Πm ηpsq for any

η “ pηpsqqsPS P P S . The properties of T π and Πm are summarized in the following proposition. Proposition 2.1. [4] The following statements hold: • T π is γ-contractive under the W̄p metric for every p P r1, 8s, namely for every η, η 1 P P S , W̄p pT π η, T π η 1 q ď γ W̄p pη, η 1 q;

• Πm is non-expansive under the W̄8 metric, namely W̄8 pΠm η, Πm η 1 q ď W̄8 pη, η 1 q for every η, η 1 P P S . It immediately follows from Proposition 2.1 that the quantile projected Bellman operator Πm T π is a γ-contraction in the Polish space pP S , W̄8 q. Hence, the quantile projected Bellman equation η “ Πm T π η admits a unique solution ηm . We define the quantile parameter θm P RSˆrms by m

ηm psq “

1 ÿ δ , m i“1 θm ps,iq

with θm ps, 1q ď ¨ ¨ ¨ ď θm ps, mq for every s P S. 12

2.4

Main Assumptions

For every ps, aq P S ˆ A, we make the following assumption about PR p¨ | s, aq. Assumption 1. For any s P S, a P A, PR p¨ | s, aq is supported on r0, 1s and has a Lebesgue density ps,a . Moreover, ps,a is continuous on r0, 1s and there exists a positive constant C0 such that 0 ă ps,a pxq ď C0 for any x P p0, 1q. The following proposition shows that this assumption leads to a well-behaved return density, and its proof is presented in Appendix A.1. Proposition 2.2. For every s P S, η π psq has a continuous Lebesgue density pηπ psq upper bounded by C0 on r0, p1 ´ γq´1 s. Moreover, pηπ psq pxq ą 0 for any x P p0, p1 ´ γq´1 q and pηπ psq p0q “ pηπ psq pp1 ´ γq´1 q “ 0. Moreover, we make an assumption on the locations of θm . Assumption 2. For every m and ps, iq, ps1 , jq P S ˆ rms, we have θm ps, iq ´ γθm ps1 , jq R t0, 1u. This is a technical condition that excludes boundary-degenerate configurations in which Bellmanshifted quantile locations coincide with the endpoints of the reward support. In particular, it guarantees that the projected Bellman equation is continuously differentiable around the true parameter, thereby ensuring the regularity conditions required by the Z-estimation theory used in subsequent analysis. To carry out non-asymptotic analysis, we impose one of the following two alternative regularity conditions on the reward densities. The first condition assumes that the reward densities are uniformly bounded away from zero, a common assumption in the quantile estimation. Assumption 3. For any s P S, a P A, ps,a is continuous on r0, 1s and there exists a positive constant c0 such that ps,a pxq ě c0 for any x P r0, 1s. The second condition allows reward densities to vanish at the boundary of the support, at the expense of additional smoothness and shape constraints near the endpoints. Assumption 4. For any s P S, a P A, ps,a is Lipschitz continuous on r0, 1s and ps,a p0q “ ps,a p1q “ 0, and there exists κ ą 0 such that ps,a is increasing on r0, κs and decreasing on r1 ´ κ, 1s. 13

The monotonicity conditions near 0 and 1 exclude highly oscillatory boundary behavior and ensure that the density approaches zero in a regular manner. Typical examples include Beta distribution with shape parameters α, β ą 1. Under Assumption 3, we set κ “ 21 . Under Assumption 4, κ is the constant appearing in the assumption. In either case, the parameter κ will be used in the subsequent analysis. Finally, we make the following assumption on the quantile function of the return distribution Fη´1 π psq . Assumption 5. For any s P S, it holds that •

ż 1 F ´1 ptq η π psq 0

ż1

´1 1 1´γ ´ Fη π psq ptq

1´t

dt ă `8,

dt ă `8;

´ ¯ ´1 1 as ϱ Ñ 0. • ωs pϱq – sup|x´y|ďϱ |Fη´1 π psq pxq ´ Fη π psq pyq| “ o 1{ log ϱ This assumption requires that Fηπ psq does not approach 0 or 1 too rapidly near the boundary, and it is rather mild. For example, Fηπ psq pxq „ xc with c ą 0 or even Fηπ psq pxq „ expp´x´b q with 0 ă b ă 1 near 0 satisfies this assumption.

Main Results

In this section, we analyze quantile-projected distributional reinforcement learning from both nonpnq

asymptotic and asymptotic perspectives. We first introduce the quantile fixed point estimator ηm pnq

and establish non-asymptotic convergence rates for W̄8 pηm , ηm q. We also study the asymptotic ? ? pnq pnq behavior of npηm psq ´ ηm psqq and the associated linear functional npηm psq ´ ηm psqqf , showing that quantile-projected distributional policy evaluation is sample-efficient when a generative model is available. We show that these quantities are asymptotically Gaussian and derive explicit expressions for their asymptotic variances. We further characterize the limiting behavior of the asymptotic variance as the quantization level tends to infinity through an operator-theoretic representation. Finally, we establish Berry–Esseen bounds for the Gaussian approximation, providing quantitative guarantees on the accuracy of the asymptotic Gaussian approximation.

3.1

The Quantile Fixed Point Estimator

In this paper, we study the distributional policy evaluation problem, where the goal is to estimate the return distribution η π associated with a fixed policy π. We consider the setting where the 14

underlying MDP is unknown and can only be accessed through a finite dataset. We assume the dataset is sampled from a generative model, which generates a sample of the next state s1 following P p¨ | s, aq and a reward sample r following PR p¨ | s, aq for any given pair ps, aq P S ˆ A. For each pair ps, aq P S ˆ A, we query the generative model n independent times and produces an array ps,aq

tX1

ps,aq

, . . . , Xnps,aq u – tpr1

1ps,aq

, s1

iid

q, . . . , prnps,aq , s1ps,aq qu „ PR p¨ | s, aq b P p¨ | s, aq. n

Given the dataset, we may obtain the empirical estimates of the transition probability and reward distribution as

n ) 1 ÿ ! 1ps,aq pnq 1 p 1 si P ps | s, aq “ “ s1 , n i“1 n ÿ ppnq p¨ | s, aq “ 1 P δ ps,aq p¨q. R n i“1 ri pnq

pnq

p define an empirical MDP M xpnq “ xS, A, P p , Pppnq , γy. Denote the empirical Thus, Pppnq and P R R xpnq as Tp π . Then the empirical quantile projected Bellman distributional Bellman operator of M n pnq pnq equation η “ Πm Tpnπ η admits a unique solution ηm . We also define θm P RSˆrms by m

pnq ηm psq “

pnq

1 ÿ δ pnq , m i“1 θm ps,iq

pnq

with θm ps, 1q ď . . . ď θm ps, mq for every s P S. We call ηm the quantile fixed point estimator throughout the paper. The quantile fixed point estimator can be computed by quantile dynamic programming (QDP), pnq ps,aq pnq namely iterating ηm,k`1 “ Πm Tpnπ ηm,k until convergence. Because we need to sort all ri ` pnq pnq γθm,k ps1 , jq for the computation of quantiles, the computational cost of Πm Tpnπ ηm,k is Op|S|2 |A|mnq. pnq

pnq

Combining this with Proposition 2.1, we know that in order to achieve W̄8 pηm , ηm,k q ď ε, the total computational cost is Op|S|2 |A|p1 ´ γq´1 mn log 1ε q.

3.2

Non-asymptotic Analysis pnq

We first establish a non-asymptotic convergence rate for the quantile fixed point estimator ηm . Theorem 3.1. Suppose that either Assumption 3 or 4 holds. Given any δ P p0, 1q, with probability at least 1 ´ δ, we have c pnq W̄8 pηm , ηm q ď C1 pMq

m logp6|S|m{δq . n

Moreover, we have c ” ı pnq E W̄8 pηm , ηm q ď C1 pMq

m logp6|S|mq , n

where C1 pMq is a constant independent of m and n and only depends on M. The proof of Theorem 3.1 is provided in Section 4.1. Remark 3.1. The proof yields the following characterization of the constant C1 pMq in Theorem 3.1. For sufficiently large m, we have fi´1 , . ´ ¯ 1 – C ´1 fl C1 pMq ď p π max , inf F pτ q , % 1 ´ γ τ Prκ0 {2,1´κ0 {2s η psq ηπ psq 1´γ $ &

sPS

where C is a universal constant and κ0 “

! ´κ¯ ” ´ κ ¯ı) 1 min Fηπ psq ^ 1 ´ Fηπ psq p1 ´ γq´1 ´ . 2 sPS 2 2

In particular, κ0 depends only on the underlying MDP M. ´2 q up to problem-dependent constants suffices to ensure r Theorem 3.1 indicates that n “ Opmε pnq

W̄8 pηm , ηm q ď ε with high probability, which implies distributional policy evaluation with quantile parametrization is sample-efficient. The key idea in our proof is that we first analyze the concentration behaviors of the quantiles of Tpnπ ηm around those of T π ηm . We relate the quantile estimation problem to the analysis of the corresponding empirical distribution functions and perform a variance-dependent analysis via Bernstein-type inequalities. This yields a refined concentration bound that explicitly captures the dependence of the estimation variability on the quantile level. Then we combine this concentration result with the contraction property of the projected Bellman operator and establish the theorem. Moreover, the approximation error of ηm is characterized as follows, the proof of which is provided in Section 4.1. Combined with Proposition 2.2, this theorem implies that the approximation error converges to zero as m Ñ 8. Theorem 3.2. For every m P N, W̄8 pηm , η π q ď p1 ´ γq´1 supsPS ωs pp2mq´1 q.

3.3

Asymptotic Analysis pnq

pnq

We now investigate the asymptotic behavior of ηm , or θm equivalently. To characterize the asymptotic distribution, we introduce two matrices. The matrix Σm captures the sampling variability, 16

which is defined as ÿ

pΣm qps,iq,ps1 ,jq “ 1ts “ s1 u

θm πpa | sq2 CovpR,S̃q„PR p¨|s,aqbP p¨|s,aq pys,i pR, Sq, ysθ1m,j pR, Sqq,

aPA

where y θ : r0, 1s ˆ S Ñ RSˆm is defined as m

θ ys,i pr, s1 q “

1 ÿ 1tr ` γθps1 , kq ă θps, iqu. m k“1

We can also formulate as +

# Σm “ diag

πpa | sq2 VarpR,S̃q„PR p¨|s,aqbP p¨|s,aq

¯ ysθm pR, Sq

aPA

. sPS

The matrix Gm characterizes the local sensitivity of the projected Bellman fixed-point equation with respect to perturbations of the quantile parameters. The entries of Gm are given by pGm qps,iq,ps1 ,jq “ ´ `

γ ÿ πpa | sqP ps1 | s, aqps,a pθm ps, iq ´ γθm ps1 , jqq m aPA m 1tps, iq “ ps1 , jqu ÿ ÿ πpa | sqP ps̃ | s, aqps,a pθm ps, iq ´ γθm ps̃, kqq . m aPA,s̃PS k“1

With the matrices Σm and Gm , we are now ready to characterize the asymptotic distribution of the pnq

estimated quantile parameters θm and the proof is deferred to Section 4.2. Theorem 3.3. Gm is invertible, and ?

` ˘ d pnq ´J npθm ´ θm q Ñ N 0m , G´1 . m Σm Gm

Moreover, the asymptotic covariance matrix coincides with the semiparametric efficiency bound for estimating θm in the model class Q “ tpQs,a qps,aqPSˆA : Qs,a ! λ b #S u, pnq

where λ is the Lebesgue measure on r0, 1s and #S is the counting measure on S. Therefore, θm is semiparametrically efficient. pnq

Theorem 3.3 shows that, for any fixed m, the estimator θm admits a Gaussian limit after 17

normalization by

? n. A key step in the proof is to reformulate the projected Bellman equation as a

finite-dimensional estimating equation and then apply tools from Z-estimation theory. Correspond´J ingly, the asymptotic covariance takes the form G´1 m Σm Gm , reflecting the interaction between the

sampling variability captured by Σm and the local sensitivity of the projected Bellman fixed-point equation encoded by Gm . pnq

Beyond asymptotic normality, Theorem 3.3 also establishes the semiparametric efficiency of θm . ´J This implies that the asymptotic covariance matrix G´1 m Σm Gm coincides with the semiparametric

efficiency bound, and therefore no regular estimator can achieve a uniformly smaller asymptotic covariance matrix. The proof is based on a pathwise differentiability analysis of the projected Bellman fixed-point mapping. By characterizing the response of the fixed point to smooth perturbations of the underlying data-generating distribution, we identify the efficient influence function and show pnq

that θm attains the corresponding efficiency bound. Integral functionals induced by smooth test functions offer a more natural way to compare return distributions. Applying the delta method, we have the following corollary for these functionals. Corollary 3.1. Suppose that f P C 1 r0, p1 ´ γq´1 s. For s P S, define pφm,f,s qs1 ,j “ 1ts1 “ 1

su f pθmmps ,jqq and we have ¯ ? ´ pnq d 2 q n ηm psq ´ ηm psq f Ñ N p0, σm,f,s where ´1 ´J 2 “ φJ σm,f,s m,f,s Gm Σm Gm φm,f,s 1 Proof of Corollary 3.1. For test function f and s P S, define F : RSˆrms Ñ R by F pθq “ m pnq

řm

i“1 f pθps, iqq.

pnq

Then ηm psqf “ F pθm q, ηm psqf “ F pθm q and ∇F “ φm,f,s . The conclusion follows from Theorem 3.3 and the multivariate delta method. The asymptotic normality established above further enables statistical inference for these functionals. By estimating the asymptotic variance with plug-in estimators, we obtain an asymptotically valid confidence interval for ηm psqf . Corollary 3.2. Suppose that f P C 1 r0, p1 ´ γq´1 s, and for each pair ps, aq, we have a density estimator pps,a satisfying ps,a pxq ´ ps,a pxq| Ñ 0 sup |p

(2)

xPr0,1s

p m, Σ p m and φ pm,f,s by replacing ps,a , PR p¨ | s, aq, P p¨ | s, aq, in probability as n Ñ 8. We construct G 18

pnq

p p¨ | s, aq, Pppnq p¨ | s, aq and θm , and θm in the definitions of Gm , Σm , and φm,f,s with pps,a , P R 2 p ´1 p p ´J pm,f,s . Let the confidence interval pJ pm,f,s respectively, and σ “φ m,f,s Gm Σm Gm φ

pm,f,s pnq pm,f,s σ σ pnq psqf ` z α2 ? s, CIpαq “ rηm psqf ´ z α2 ? , ηm n n where z α2 is the upper α2 -quantile of N p0, 1q. Then we have lim P rηm psqf P CIpαqs “ 1 ´ α.

nÑ8

A canonical choice for estimating ps,a is the kernel density estimator. With a bandwidth sequence hn satisfying hn Ñ 0 and nhn Ñ 8, Equation (2) holds in probability [40]. 2 2 pm,f,s Ñ σm,f,s in probability as Proof of Corollary 3.2. By the law of large numbers we know that σ

n Ñ 8 and the conclusion follows from Slutsky’s theorem.

3.4

Limiting Covariance Structure and Efficiency

The asymptotic variance in Corollary 3.1 is expressed through the finite-dimensional matrices Gm and Σm , whose dimensions grow with the quantization level m. To understand the covariance structure underlying quantile-based distributional policy evaluation, it is natural to ask whether the finite-dimensional asymptotic variances admit a well-defined limit as m Ñ 8 and, if so, how this limit relates to the efficiency bound of distributional policy evaluation problem. In this subsection, 2 we answer this question by characterizing the limit of σm,f,s as m Ñ 8 through a pair of operators 0

acting on an appropriate infinite-dimensional Hilbert space. À ř Define L “ sPS L2 r0, 1s, and }ψ}2 “ sPS }ψs p¨q}2L2 for ψ P L. Define the operator K on L by pKψqs pτ q “

1 ´

pηπ psq Fη´1 π psq pτ q

ÿ ¯

ż1 1

πpa | sqP ps | s, aq 0

aPA,s1 PS

´ ¯ ´1 ps,a Fη´1 π psq pτ q ´ γFη π ps1 q ptq ψs1 ptqdt,

r on L is given by and we refer to K as the quantile Bellman operator. The operator Σ ż1 r s pτ q “ pΣψq

´ 0

pηπ psq

As pτ, tq ´ ¯ ψs ptqdt, ¯ ´1 Fη´1 π psq pτ q pη π psq Fη π psq ptq

where A : r0, 1s ˆ r0, 1s Ñ RS is given by ˜ As pτ, tq “

πpa | sq CovpR,Sq„PR p¨|s,aqbP p¨|s,aq

Fηπ pSq

aPA

Fη´1 π psq pτ q ´ R γ

˜ , Fηπ pSq

Fη´1 π psq ptq ´ R

¸¸

r are bounded operators from L to L, whose The following proposition shows that both K and Σ proof is deferred to Appendix D.1. r are bounded operators on L. Moreover, I ´ γK˚ is invertible, where K˚ Proposition 3.1. K and Σ is the adjoint operator of K in L. The limit of asymptotic variance is characterized as follows. The proof of this theorem is presented in Section 4.3. Theorem 3.4. Suppose that either Assumption 3 or 4 holds, and that Assumption 5 holds. For a test function f P C 1 r0, p1 ´ γq´1 s and s0 P S, define ψps, τ q “ 1ts “ s0 uf 1 pFη´1 π psq pτ qq and u˚ “ pI ´ γK˚ q´1 ψ. Then we have 2 r ˚y – σ2 . lim σm,f,s “ xu˚ , Σu f,s0 0

mÑ`8

Moreover, denote η pnq as the fixed point of Tpnπ , namely η pnq “ Tpnπ η pnq . We have ¯ ? ´ pnq d 2 n η ps0 q ´ η π ps0 q f Ñ N p0, σf,s q 0 2 and σf,s coincides with the semiparametric efficiency bound for estimating η π ps0 qf in the model 0

class Q. Theorem 3.4 provides a statistical interpretation of the limiting covariance structure. The r ˚ y first arises as the operator-theoretic limit of the asymptotic variances σ 2 quantity xu˚ , Σu m,f,s0 in the finite-dimensional quantile approximation. Moreover, the theorem shows that this limit coincides exactly with the asymptotic variance of the nonparametric estimator η pnq ps0 qf . Consequently, the sequence of finite-dimensional efficient quantile estimators preserves asymptotic efficiency as the quantization level m Ñ 8. In particular, no statistical efficiency is lost when passing from the original infinite-dimensional return distribution to its finite-dimensional quantile approximation. To gain intuition for the operator K, consider a probability measure vector ν P P S and formally

define Zs ptq “

νs p´8, Fη´1 π psq ptqs ´ ¯. pηπ psq Fη´1 ptq π psq

Whenever the quantities involved are well defined, we have

pγKZqs ptq “

pT π νqs p´8, Fη´1 π psq ptqs ´ ¯ . pηπ psq Fη´1 ptq π psq

Therefore, the operator K can be interpreted as the representation of the Bellman operator acting on distributions after transforming them from the space of probability measures to quantile coordinates. r admits a similar interpretation. As can be viewed as the covariance kernel associated The operator Σ with the stochastic perturbations of the Bellman operator. It is the infinite-dimensional analogue of the covariance matrix Σm . The additional factors ” ´ ¯ ´ ¯ı´1 ´1 pηπ psq Fη´1 . π psq pτ q pη π psq Fη π psq ptq r can be interpreted as the covariance arise from the quantile transformation. Consequently, Σ operator induced by the stochastic perturbations of the Bellman operator when these perturbations are represented in the space of quantile functions. At a technical level, the first challenge is that both Gm and Σm depend on m, and their dimensions diverge as m Ñ 8. To overcome this difficulty, we view the discrete matrices as operators acting on the infinite-dimensional Hilbert space L and establish operator-level convergence. A ´1 , which major obstacle is that the limiting operators contain factors of the form pηπ psq pFη´1 π psq pτ qq

may become singular near the boundary quantile levels. We therefore develop a careful boundary analysis to control these singularities and justify the convergence of both the covariance and Jacobian structures. A second and more subtle challenge is to identify the statistical meaning of the limiting variance. The operator-theoretic limit naturally leads to the representation A

E r ´ γK˚ q´1 ψ , pI ´ γK˚ q´1 ψ, ΣpI

which is expressed entirely in quantile coordinates. In contrast, the semiparametric efficiency bound established in Zhang et al. [57] is formulated in the space of signed measures and involves the resolvent pI ´ T π q´1 acting on distributional perturbations. To bridge this gap, we establish an 21

explicit correspondence between perturbations in the signed measure space and their representations in quantile coordinates. This correspondence shows that the operator K is precisely the distributional Bellman operator expressed on the quantile scale. Combined with an integration-by-parts argument, it allows us to transform the quantile-based limiting variance into the semiparametric efficiency bound.

3.5

Berry–Esseen Bound

In this subsection, we establish a Berry–Esseen bound for the functional

? pnq npηm psq ´ ηm psqqf , which

provides an explicit rate of convergence to the limiting distribution. Theorem 3.5. Suppose that Assumptions 4 and 5 hold, and f P C 1,1 r0, p1 ´ γq´1 s, meaning that f has a Lipschitz continuous derivative on r0, p1 ´ γq´1 s. For every m, n P N, we have ˇ „ ? ´ ˇ ȷ ˆ 9 ˙1 ¯ ˇ ˇ m log m log5 n 4 n pnq ˇ ˇ sup ˇP η psq ´ ηm psq f ď t ´ Φptqˇ ď CpM, f q , σm,f,s m n

(3)

tPR

where Φp¨q is the cumulative distribution function of the standard Gaussian distribution and CpM, f q is a constant independent of m and n. r 9{4 n´1{4 q in Theorem 3.5 shows that the Gaussian approximation error is bounded by Opm Kolmogorov–Smirnov distance. This result is a quantitative refinement of the asymptotic normality established in Corollary 3.1. The convergence rate should be contrasted with the classical quantile estimation literature. For sample quantiles, Berry–Esseen bounds of order Opn´1{2 q are available [24], while for quantile regression estimators nearly optimal Opplog nq3{2 n´1{2 q rates have also been established [35]. The slower n´1{4 rate in our result can be attributed to two major difficulties. First, the projected Bellman equation involves indicator functions and is therefore inherently non-smooth. As a result, the higher-order stochastic expansions available for smooth M -estimators are not directly applicable in our setting. Second, unlike classical quantile estimators, the quantile parameters considered here are defined implicitly through the projected Bellman fixed-point equation and do not admit a direct representation through empirical distribution functions. Consequently, the empirical-distributionbased arguments underlying sharp Berry–Esseen bounds for classical quantile estimators are no longer available. The key idea of the proof is to derive a stochastic expansion of the test functional and decompose it as W ` D, where W is a normalized sum of independent random variables and D is a higher-order 22

remainder term arising from the nonlinearity of the projected Bellman operator. We then apply a Berry–Esseen theorem for general nonlinear statistics to this decomposition. A crucial step is to establish quantitative bounds on the remainder term D by two components: a local empirical-process fluctuation term and a second-order expansion remainder. We further control the effect of replacing a single observation by an independent copy on both components. Combining these bounds with the Berry–Esseen theorem for general nonlinear statistics yields the stated rate. Detailed proofs are provided in Section 4.4.

Proof Outlines

In this section, we present proofs of Theorems 3.1, 3.2, 3.3, 3.4 and 3.5.

4.1

Analysis of Non-asymptotic Bound

The proof of Theorem 3.1 consists of two steps. We first establish a concentration inequality for the empirical Bellman operator evaluated at the population fixed point ηm . This yields a uniform bound on the perturbation of the corresponding quantile functions. We then combine this estimate with the γ-contraction property of Πm T π under W̄8 metric to obtain a fixed-point perturbation bound, which implies Theorem 3.1. The key ingredient is the following concentration result, the proof of which is provided in Appendix B. Lemma 4.1. Suppose that either Assumption 3 or 4 holds. Given s P S and i P rms, for every δ P p0, 1q, we have c ˇ ˇ m logp6{δq ˇ ´1 ˇ ´1 . ˇFpTp π η qpsq pτi q ´ FpT π ηm qpsq pτi qˇ ď CpMq n n m holds with probability at least 1 ´ δ. Here CpMq is a constant independent of m and n. Applying Lemma 4.1 and a union bound over all states and quantile levels, we obtain c ´

W̄8 Πm Tpnπ ηm , Πm T π ηm ď CpMq

m logp6|S|m{δq n

pnq with probability at least 1 ´ δ. Since ηm and ηm are fixed points of Πm T π and Πm Tpnπ , respectively,

we have pnq pnq W̄8 pηm , ηm q ď W̄8 pΠm Tpnπ ηm , Πm Tpnπ ηm q ` W̄8 pΠm Tpnπ ηm , Πm T π ηm q

pnq ď γ W̄8 pηm , ηm q ` W̄8 pΠm Tpnπ ηm , Πm T π ηm q.

Rearranging the above inequality yields Theorem 3.1. The expectation upper bound is derived from Lemma F.4. To prove Theorem 3.2, we use the contraction property of the projected Bellman operator to obtain W̄8 pηm , η π q ďW̄8 pΠm T π ηm , Πm T π η π q ` W̄8 pΠm η π , η π q ďγ W̄8 pηm , η π q ` W̄8 pΠm η π , η π q. By the definition of Πm , we know that # π

W̄8 pΠm η , η q “

max iPrms,sPS

+ ˆ ˙ ˇ ˇ 1 ˇ ´1 ˇ ´1 . max ˇFηπ psq pxq ´ Fηπ psq pτi qˇ ď sup ωs 2m xPr i´1 ,is sPS m m

Therefore, 1 1 W̄8 pηm , η q ď W̄8 pΠm η π , η π q ď sup ωs 1´γ 1 ´ γ sPS π

4.2

1 2m

˙ .

Analysis of Asymptotic Distribution and Efficiency

First, we prove the

pnq

n-consistency of θm under the weaker conditions. The proof of the lemma is

deferred to Appendix C.1. Lemma 4.2. For every fixed m, we have

pnq

npθm ´ θm q “ OP p1q as n Ñ 8.

With Lemma 4.2 in hand, we can reformulate the projected Bellman equation as a finitedimensional Z-estimation problem and establish the asymptotic normality. For brevity, we denote p pnq ppnq ppnq p¨ | s, aq. Define H, Hn : RSˆrms Ñ Qs,a “ PR p¨ | s, aq b P p¨ | s, aq and Q s,a “ PR p¨ | s, aq b P RSˆrms as pHpθqqs,i “

m ÿ ĳ πpa | sq ÿ aPA

pHn pθqqs,i “

ÿ ĳ πpa | sq aPA

and denote phθ pR, Sqqs,i “

m ř aPA

k“1 m ÿ

1tRs,a ` γθpSs,a , kq ă θps, iquQs,a pdpRs,a , Ss,a qq p pnq pdpRs,a , Ss,a qq, 1tRs,a ` γθpSs,a , kq ă θps, iquQ s,a

k“1 πpa|sq řm k“1 1tRs,a ` γθpSs,a , kq ă θps, iqu. m

pnq

Then Hpθm q “ T and Hn pθm q “ T ` εn , where Ts,i “ τi and }εn }8 ď n´1 . The key regularity condition is the non-singularity of the Jacobian matrix, which is established in the following lemma. Lemma 4.3. ∇Hpθm q “ Gm and Gm is invertible for every m P N. The proof of the lemma above is presented in Appendix C.2. Therefore, we have pnq εn “ Hn pθm q ´ Hpθm q pnq pnq pnq “ Hpθm q ´ Hpθm q ` Hn pθm q ´ Hpθm q pnq pnq pnq pnq “ Gm pθm ´ θm q ` oP p}θm ´ θm }q ` Hn pθm q ´ Hpθm q

Denote Zn pθq “ ?

? nrHn pθq ´ Hpθqs and rearranging the terms, we have pnq ´1 pnq npθm ´ θm q “ ´G´1 m Zn pθm q ´ Gm rZn pθm q ´ Zn pθm qs ` oP p1q.

pnq

To control the empirical process remainder Zn pθm q ´ Zn pθm q, we require the following Donsker property, which is proved in Appendix C.3. Lemma 4.4. Denote Hs,i “ thθs,i ´ hθs,im : }θ ´ θm }8 ď p1 ´ γq´1 u, then for every ps, iq, Hs,i is Â aPA Qs,a -Donsker, namely the empirical process indexed by Hs,i satisfies a functional central limit theorem. pnq

By Lemma 4.4 and van der Vaart and Wellner [51], we know that Zn pθm q ´ Zn pθm q “ oP p1q. Finally, by the multivariate central limit theorem, d

´1 ´J ´G´1 m Zn pθm q Ñ N p0m , Gm Σm Gm q,

hence the asymptotic normality follows. To characterize the semiparametric efficiency bound, consider a regular parametric submodel tQϵ u with score g, namely dQϵs,a “ p1 ` ϵgs,a qdQs,a . Denote the distributional Bellman operator ϵ . corresponding to Qϵ as Tϵπ , and the quantile parameters of the fixed point of Πm Tϵπ as θm

The following lemma characterize the pathwise derivative of the parameter and it is proved in Appendix C.4.

Lemma 4.5. Define the matrix Ym P RpSˆrmsqˆpSˆAq by m ␣ ( πpa | sq ÿ 1tRs,a ` γθpSs,a , kq ă θps, iqu pYm qps,iq,ps1 ,aq “ 1 s “ s1 m k“1

Then ˆ

ϵ ˇ dθm ˇ ˇ dϵ ϵ“0

˙ ÿ “´ s,i

EQs1 ,a rpG´1 m pYm ´ EYm qqps,iq,ps1 ,aq gs1 ,a s.

s1 ,a

Lemma 4.5 shows that the efficient influence function of θm is ϕm “ ´G´1 m pYm ´EYm q. According to van der Vaart [50], the efficiency lower bound is given by ´J VarQ pϕm q “ G´1 m Σm Gm .

pnq

Therefore the estimator θm attains the semiparametric efficiency bound and is semiparametrically efficient.

4.3

Analysis of Limiting Covariance Structure and Efficiency

To study the asymptotic variance as m Ñ 8, we introduce an operator-theoretic representation and identify its infinite-dimensional limit. First, we rewrite Gm “ Dm ´ γWm , where pDm qps,iq,ps1 ,jq “ 1tps, iq “ ps1 , jqu

ÿ aPA

ÿ pWm qps,iq,ps1 ,jq “

πpa | sq

P ps1 | s, aq m

aPA

πpa | sq

s̃PS,kPrms

P ps̃ | s, aq ps,a pθm ps, iq ´ γθm ps̃, kqq m

ps,a pθm ps, iq ´ γθm ps1 , jqq.

´1 W and the asymptotic variance can be expressed as Moreover, define Km “ Dm m

2 ´1 ´1 ´1 ´J σm,f,s “ φJ φm,f,s m,f,s pI ´ γKm q pDm Σm Dm qpI ´ γKm q

To identify the limit of this expression, we introduce the averaging and embedding operators ż i Rm : L Ñ R Sˆm

Em : R

Sˆm

Ñ L,

pRm ψqs,i “ m pEm ψqps, τ q “

i´1 m

m ÿ i“1

ψs pτ qdτ,

ψs pτi q1rτi ,τi`1 q pτ q.

Furthermore, we define ψm ps, τ q “ 1ts “ s0 u

m ÿ

´ ¯ ´1 pτ q 1r i´1 , i q pτ q, f 1 FpT i π η qpsq m m

i“1

um “ Em pI ´ γKm q´J Rm ψm r m on L as and Σ r m ψ “ 1 Em D ´1 Σm D ´1 Rm ψ. Σ m m m r denote the limiting operators introduced in Section 3.4. The next lemma establishes Let K and Σ convergence of the discrete operators to their infinite-dimensional counterparts. Its proof is deferred to Appendix D.3. Lemma 4.6. Suppose either Assumption 3 or 4 holds, and that Assumption 5 holds. We have lim }Em Km Rm ´ K} “ 0,

mÑ`8

› › ›r r› lim ›Σ m ´ Σ› “ 0.

mÑ`8

The following proposition summarizes the key properties of the finite-dimensional representation and it is proved in Appendix D.2. Proposition 4.1. The following statements hold: • um is the unique solution in L of the equation J Rm qu “ ψm ; pI ´ γEm Km

2 r m um y; • The asymptotic variance admits the representation σm,f,s “ xum , Σ 0

• As m Ñ 8, ψm Ñ ψ in L; JR . • The adjoint operator of Em Km Rm is given by pEm Km Rm q˚ “ Em Km m

By Proposition 3.1 and Lemma 4.6, we know that I ´ γEm Km Rm is invertible for all sufficiently large m. Then Proposition 4.1 implies that um Ñ u where u “ pI ´ γK˚ q´1 ψ. Consequently, 2 r m um y Ñ xu, Σuy, r σm,f,s “ xum , Σ 0

which proves the first claim of Theorem 3.4. 27

For the second claim of the theorem, first we figure out that Zhang et al. [57] have established that if ν “ pνs qsPS where νs is a finite signed measure on r0, p1 ´ γq´1 s with zero total mass for every s P S, the equation pI ´ T π qµ “ ν admits a unique solution and we denote it as µ “ pI ´ T π q´1 ν. For every s P S, rpI ´ T π q´1 νss is also a finite signed measure on r0, p1 ´ γq´1 s with zero total mass. Furthermore, they established that ¯ ? ´ pnq d 2 q, n η ps0 q ´ η π ps0 q f Ñ N p0, σ rf,s 0 ˘ ` 2 rf,s “ VarpR,Sq rpI ´ T π q´1 νss0 f , σ 0 where ν is a random measure with zero total mass defined as νs pRs , Ss qpBq “

“ ‰ πpa | sq pbRs,a ,γ q# η π pSs,a q pBq ´ η π psqpBq,

aPA

for every Borel set B, and pR, Sq “ pRs,a , Ss,a qps,aqPSˆA „

Qs,a .

s,a 2 2 . We introduce an equivalent representation on a weighted rf,s It remains to identify σ “ σf,s 0 0

quantile space. A weighted L2 r0, 1s space with weight function w is defined as L2w r0, 1s “

" * ż1 |ψ|2 2 ψ | }ψ}w “ ă8 . 0 w

Then we can define Lw “

L2ws r0, 1s

sPS

with norm }ψ}2w “

2 ´1 sPS }ψs p¨q}ws where ws “ pη π psq ˝ Fη π psq . Now we define

pK̄ψqs ptq “

xT̄s,s1 pt, ¨q, ψs1 p¨qyws1

s1 PS

pΣ̄ψqs ptq “ xAs pt, ¨q, ψs p¨qyws , where T̄s,s1 pt, τ q “

´ ¯ ´1 πpa | sqP ps1 | s, aqps,a Fη´1 π psq ptq ´ γFη π ps1 q pτ q .

aPA

The following lemma provides an equivalent representation of the limiting variance. Lemma 4.7. I ´ γ K̄ is invertible and we have 2 “ VarpR,S 1 q σf,s 0

ˆA rpI ´ γ K̄q

´1

Zss0 , f

˝ Fη´1 π ps q 0 ws0

where Z is a mean zero random vector function defined as ˜ Zs pt; Rs , Ss q “

πpa | sqFηπ pSs,a q

Fη´1 π psq ptq ´ Rs,a

aPA

´ t.

The key observation is that the random vector function Z provides a quantile-space representation of the signed measure ν. Under this identification, the operator γ K̄ acts as the distributional Bellman operator T π on the cumulative mass functions of signed measures, which we summarize in the following lemma. Lemma 4.8. We have Zs pt; Rs , Ss q “ νs pRs , Ss qp´8, Fη´1 π psq ptqs, and pγ K̄Zqs pt; Rs , Ss q “ pT π νqs pRs , Ss qp´8, Fη´1 π psq ptqs. Therefore, rpI ´ γ K̄q´1 Zss ptq “ rpI ´ T π q´1 νss p´8, Fη´1 π psq ptqs. The proofs of Lemma 4.7 and 4.8 are presented in Appendix D.4 and D.5 respectively. By the two lemmas we have A

rpI ´ γ K̄q´1 Zss , f 1 ˝ Fη´1 π psq

ż 1 “pI ´ T π q´1 ν ‰ pR , S qp´8, F ´1 ptqs ´ ¯ s s π s ´ ¯ η psq “ f 1 Fη´1 π psq ptq dt ws 0 pηπ psq Fη´1 π psq ptq ż p1´γq´1 “ ‰ “ pI ´ T π q´1 ν s pRs , Ss qp´8, xsf 1 pxq dx 0

“ ´ rpI ´ T π q´1 νss f, where the last equality follows from integration by parts and the conclusion follows. Finally, in order to establish the semiparametric efficiency result in the infinite-dimensional problem, we prove the following lemma.

Lemma 4.9. Suppose ψ “ pψs qsPS where ψs is Lipschitz continuous for every s. Denote the fixed point of Tϵπ as ηϵπ and define Y by ␣ ( Ys,ps1 ,aq “ 1 s “ s1 πpa | sqpbRs,a ,γ q# η π pSs,a q, namely Y is a matrix whose entries are random measures with shape S ˆ pS ˆ Aq. Then for any bounded score function g satisfying EQs,a rgs,a s “ 0, ˇ dxηϵπ , ψy ˇˇ ˇ ˇ dϵ

ÿ “ s1 ,a

ϵ“0

where xη, ψy “

ř sPS

“ @ ` ˘ D‰ EQs1 ,a gs1 ,a pI ´ T π q´1 Y¨,ps1 ,aq ´ EY¨,ps1 ,aq , ψ ,

ψs dηpsq.

Lemma 4.9 is proved in Appendix D.6. According to van der Vaart [50], when ψs1 “ 1 ts1 “ su f , the efficiency lower bound is given by ÿ

VarQs1 ,a

`@ D˘ pI ´ T π q´1 pY¨,ps1 ,aq ´ EY¨,ps1 ,aq q, ψ

s1 ,a

«˜

¸ ÿ

“VarQ

π ´1

pI ´ T q

Y¨,ps,aq ´ EY¨,ps,aq

aPA

ff f

` ˘ 2 “VarQ rpI ´ T π q´1 νss f “ σf,s .

4.4

Analysis of Berry–Esseen Bound

In this section we present the proof of Theorem 3.5. The proof is based on the following Berry–Esseen theorem for general nonlinear statistic due to Chen and Shao [10], Shao and Zhang [41], Shao and Zhou [42]. Theorem 4.1. Let T “ W ` D where W “

řn

i“1 ξi with ξi “ hi pXi q P R, Eξi “ 0,

řn

i“1 E|ξi |

2 “ 1.

Let O be a measurable set, then for any random variables ∆ ě |D|1O and ∆piq independent of Xi , sup |PrT ď ts ´ Φptq| À tPR

n ÿ

E|ξj |3 ` E∆ `

j“1

n ÿ

Er|ξj ||∆ ´ ∆pjq |s ` PpOc q,

i“j

where Φp¨q is the cumulative distribution function of standard normal distribution.

We apply Theorem 4.1 to the normalized functional T –

¯ ? ´1 ´ pnq nσm,s,f ηm psq ´ ηm psq f.

To this end, we decompose T “ W ` D, where W is the linear term arising from the empirical ? ´1 process and D is the nonlinear remainder. Define Gn pθq “ nφJ m,f,s Gm rHn pθq ´ Hpθqs, then we have T “ W ` D, where ?

1 ÿ ´1 ? ξi φJ G rH pθ q ´ Hpθ qs – ´ n m m σm,s,f m,f,s m n i“1 ? ? n J n J pnq pnq pnq D“ φm,f,s G´1 rH pθ q ´ Hpθ qs ´ φ G´1 rHpθm q ´ Hpθm q ´ Gm pθm ´ θm qs n m m m σm,s,f σm,s,f m,f,s m ? ÿ m ” ı n ´1 pnq pnq pnq f pθm ps, iqq ´ f pθm ps, iqq ´ f 1 pθm ps, iqqpθm ps, iq ´ θm ps, iqq . ´ σm,s,f rGn pθm q ´ Gn pθm qs ` m i“1

W “´

The following lemma, proved in Appendix E.1, shows that the remainder term D can be controlled by two simpler quantities. In addition, À in the following three lemmas hides a positive constant independent of m and n. pnq

Lemma 4.10. Suppose that Assumptions 4 and 5 hold. Define On “ t}θm ´ θm }8 ď δn u, and we have |D|1On À ∆1 ` ∆2 , where C is a universal constant and ∆1 “

sup

|Gn pθq ´ Gn pθm q|

}θ´θm }8 ďδn

›2 ? ›› pnq 1 › ∆2 “ mn´ 2 ` m n ›θm ´ θm › 1On . 8

Therefore, to apply Theorem 4.1, we need to control the expectations of ∆1 and ∆2 . Morepiq

piq

over, it remains to construct suitable random variable ∆1 , ∆2 and control the difference terms appearing in Theorem 4.1. To this end, we introduce a sample-replacement construction. Let ps,aq

r tpX 1

ps,aq

rn ,¨¨¨ ,X

pjq

qups,aqPSˆA be an iid copy of the samples. We can define Hn pθq, Gn pθq, ∆1 ,

pjq

ps,aq

π by replacing X On and Tpn,j j

ps,aq

r with X j

pn,jq

for all ps, aq. Moreover, define θm

to be the fixed

π and point of Πm Tpn,j

? › pn,jq 1 ›2 pjq ∆2 “ mn´ 2 ` m n ›θm ´ θm › 1Opjq . n 8 ›

›

With these definitions in hand, the required bounds are summarized in Lemma 4.11 and 4.12, whose proofs are deferred to Appendix E.2 and E.3 respectively.

Lemma 4.11. Suppose that Assumptions 4 and 5 hold. We have n ÿ

(4)

E|ξi |3 À m2 n

i“1

and E∆1 À m log m E∆2 À

ˆ a

log n δn m log m ` ? n

˙ (5)

m2 log m ? n

(6)

Lemma 4.12. Suppose that Assumptions 4 and 5 hold. For every m, n, we have n ÿ

pjq

E|ξj ||∆1 ´ ∆1 | À mn 2

a δn

(7)

j“1 n ÿ

« 3 pjq E|ξj ||∆2 ´ ∆2 | À m2 n 2

j“1

nδn2 δn2 exp ´ m log m ˆ

˙ `

m log m n

˜c

δn m log m log n ` ` δn2 n n

¸ff

(8) Now we can present the proof of the Berry–Esseen bound. Proof of Theorem 3.5. Choose c δn “ CpM, f q

m log m log n n

for a sufficiently large constant CpM, f q independent of m and n. Substituting the bounds in Lemmas 4.10, 4.11 and 4.12 into Theorem 4.1, we obtain 1 « 1 ff ˇ „ ? ´ ˇ ˆ 9 ȷ ˆ 9 ¯ 5 ˙4 5 ˙4 ˇ ˇ n m log m log n m log m log n sup ˇˇP η pnq psq ´ ηm psq f ď t ´ Φptqˇˇ À 1` . σm,f,s m n n

tPR

If pm9 n´1 log m log5 q1{4 ě 1, the conclusion follows trivially. Otherwise, 1 ˇ „ ? ´ ˇ ȷ ˆ 9 ¯ 5 ˙4 ˇ ˇ m log m log n n sup ˇˇP η pnq psq ´ ηm psq f ď t ´ Φptqˇˇ À 2 . σm,f,s m n

tPR

Therefore Theorem 3.5 holds.

Numerical Experiments

In this section we conduct numerical simulations to validate our theoretical findings as well as the proposed inferential procedures.

5.1

Experimental Setup

π sinpπxq1r0,1s pxq, ps2 pxq “ 4xp1 ´ x2 q1r0,1s pxq, 2

which satisfy Assumption 4. We choose f pxq “ sin x ´ x cos x as the test function. We conduct the experiments under m P t20, 50, 100u and n P t10, 100, 1000, 10000u. For each pair pm, nq, we pnq

perform 1000 independent Monte Carlo replications. In each replication, ηm and ηm are computed via quantile dynamic programming.

5.2

Finite-sample Convergence Behavior

We investigate the finite-sample convergence behavior and verify our non-asymptotic results. We pnq

pnq

report the average of W̄8 pηm , ηm q over the 1000 replications and regress log W̄8 pηm , ηm q on log n. The results are presented in Figure 1 and Table 1. The estimated slopes for all cases are consistently close to ´ 12 , with R2 values exceeding 0.999, providing strong numerical evidence for 1

the n´ 2 convergence rate established in Theorem 3.1. We also observe that the estimated intercepts exhibit only a weak dependence on m over the range considered in the experiment.

0.2 0.4

0.2

W distance fitted line, slope=-0.5095

0.4

0.6

0.8

1.0

log(W )

0.4

log(W )

0.2

W distance fitted line, slope=-0.5022

1.0

1.2

1.4

1.6

1.8

1.0

1.5

2.0

2.5 log(n)

3.0

3.5

1.8

4.0

1.0

1.5

2.0

2.5 log(n)

3.0

3.5

4.0

W distance fitted line, slope=-0.5114

1.8

1.0

1.5

2.0

2.5 log(n)

3.0

3.5

4.0

pnq

Figure 1. The statistical error W̄8 pηm , ηm q with different sample sizes. From left to right: m “ 20, m “ 50, m “ 100.

m 20 50 100

slope -0.5022 -0.5095 -0.5114

intercept 0.5881 0.6457 0.6447

R2 0.9999 0.9998 1.0000

Table 1. Estimated regression coefficients and coefficient of determination (R2 ) for the regression of pnq log W̄8 pηm , ηm q on log n under different choices of m.

5.3

Asymptotic Normality

We next investigate the asymptotic normality of the test functional predicted by Corollary 3.1. Figure 2 presents the QQ plots of the standardized estimator ? n σm,f,s1

´ ¯ pnq ηm ps1 q ´ ηm ps1 q f

for n “ 10000 and different choices of m. In all cases, the empirical quantiles closely follow the reference line, indicating good agreement with the standard normal distribution. An additional numerical evidence is provided in Table 2. The empirical skewness and excess kurtosis are both close to zero for all values of m, suggesting that the standardized estimator is approximately symmetric and exhibits Gaussian-like tail behavior. Moreover, the Shapiro–Wilk test does not reject the null hypothesis of normality at the 0.05 significance level in any of the cases considered. These observations are consistent with the asymptotic normality established in Corollary 3.1.

Sample Quantiles

3 2 1 0 1 2 3

1 0 1 Theoretical Quantiles

? pnq Figure 2. The QQ plot of standardized estimator npηm ps1 q ´ ηm ps1 qqf {σm,f,s1 for sample size n “ 10000. From left to right: m “ 20, m “ 50, m “ 100.

m 20 50 100

skewness 0.0347 0.0485 -0.1411

excess kurtosis -0.2063 -0.2085 -0.0679

Shapiro–Wilk p-value 0.2491 0.4592 0.2873

Table 2. Skewness, excess kurtosis, and Shapiro–Wilk p-values of the standardized estimator under sample size n “ 10000 and different choices of m.

m “ 20 m “ 50 m “ 100

n “ 10 0.859 0.832 0.854

n “ 100 0.940 0.950 0.934

n “ 1000 0.944 0.945 0.966

n “ 10000 0.948 0.957 0.966

Table 3. Coverage rate of our proposed confidence interval for ηm ps1 qf under different choices of m and n.

5.4

Validity of Inferential Procedures

Finally, we evaluate the finite-sample performance of the proposed inferential procedure. Following Corollary 3.2, we estimate the reward density ps1 and ps2 using Gaussian kernel density estimators with Scott’s rule for bandwidth selection [40]. Based on the resulting plug-in variance estimator pnq

2 σ pm,f,s σm,f,s1 n´ 2 . , we construct nominal 0.95 confidence intervals for ηm ps1 qf by ηm ps1 qf ˘ 1.96p 1

The coverage rates over 1000 independent Monte Carlo replications are reported in Table 3. For all choices of m, the coverage probabilities increase rapidly as the sample size grows. While noticeable finite-sample deviations are observed when n “ 10, the coverage rates are already close to the nominal 0.95 level for n “ 100, and remain stable for larger sample sizes. These results provide strong numerical evidence for the validity of the plug-in confidence intervals proposed in Corollary 3.2.

Conclusions

In this paper, we have analyzed the statistical performance of distributional reinforcement learning with quantile parametrization from both non-asymptotic and asymptotic perspectives. We have pnq

presented non-asymptotic rate for W̄8 pηm , ηm q. We have also derived that the standardized quantile ? pnq parameter npθm ´ θm q converges weakly to a Gaussian distribution and that our quantile fixed pnq

point estimator θm is semiparametrically efficient. Moreover, we have established a Berry–Esseen ? pnq bound for the statistical functional npηm psq ´ ηm psqqf given an initial state s. Based on our theoretical findings, we have devised inferential procedures for integral functionals induced by smooth test functions of the quantile fixed point ηm . Beyond these finite-dimensional results, we have studied the asymptotic regime where the number of quantiles m increases to infinity. By developing an operator-theoretic representation of the quantile-projected Bellman equation, we have characterized the limiting covariance structure and proved that the asymptotic variance converges to the semiparametric efficiency bound of the underlying non-parametric model for distributional policy evaluation. These findings reveal that quantile parametrization preserves the statistical efficiency of the underlying distributional policy evaluation problem in the large-quantile limit. This provides a theoretical justification for the widespread use of quantile-based methods in distributional reinforcement learning. One future direction is to improve the dependence on the number of quantiles m in the Berry– Esseen bound. Another promising direction for future work is to extend the present theory beyond the model-based setting considered in this paper. This includes both offline reinforcement learning without access to a generative model and online quantile-based algorithms such as quantile temporal difference learning. This might give rise to a wider range of inferential applications in reinforcement learning.

References [1] R. R. Bahadur. A note on quantiles in large samples. The Annals of Mathematical Statistics, 37(3):577–580, 1966. [2] M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective on reinforcement learning. In International conference on machine learning, pages 449–458. PMLR, 2017. [3] M. G. Bellemare, S. Candido, P. S. Castro, J. Gong, M. C. Machado, S. Moitra, S. S. Ponda, 36

and Z. Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77–82, 2020. [4] M. G. Bellemare, W. Dabney, and M. Rowland. Distributional Reinforcement Learning. MIT Press, 2023. http://www.distributional-rl.org. [5] C. Bodnar, A. Li, K. Hausman, P. Pastor, and M. Kalakrishnan. Quantile qt-opt for risk-aware vision-based robotic grasping. arXiv preprint arXiv:1910.02787, 2019. [6] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013. [7] H. Brézis. Functional analysis, Sobolev spaces and partial differential equations. Springer, 2011. [8] Y. Chandak, S. Niekum, B. da Silva, E. Learned-Miller, E. Brunskill, and P. S. Thomas. Universal off-policy evaluation. Advances in Neural Information Processing Systems, 34:27475–27490, 2021. [9] L. Chen, G. Keilbar, and W. B. Wu. Smoothed sgd for quantiles: Bahadur representation and gaussian approximation, 2025. [10] L. H. Chen and Q.-M. Shao. Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli, 13(2), 2007. [11] W. Dabney, G. Ostrovski, D. Silver, and R. Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pages 1096–1105. PMLR, 2018. [12] 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. [13] T. Doan, B. Mazoure, and C. Lyle. Gan q-learning. arXiv preprint arXiv:1805.04874, 2018. [14] A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera-Paredes, M. Barekatain, A. Novikov, F. J. R Ruiz, J. Schrittwieser, G. Swirszcz, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47–53, 2022. [15] D. Freirich, T. Shimkin, R. Meir, and A. Tamar. Distributional multivariate policy evaluation and exploration with the bellman gan. In International Conference on Machine Learning, pages 1983–1992. PMLR, 2019. 37

[16] E. Ghysels, P. Santa-Clara, and R. Valkanov. There is a risk-return trade-off after all. Journal of financial economics, 76(3):509–548, 2005. [17] B. Hao, X. Ji, Y. Duan, H. Lu, C. Szepesvari, and M. Wang. Bootstrapping fitted q-evaluation for off-policy inference. In International Conference on Machine Learning, pages 4074–4084. PMLR, 2021. [18] Y. Hua, R. Li, Z. Zhao, X. Chen, and H. Zhang. Gan-powered deep distributional reinforcement learning for resource management in network slicing. IEEE Journal on Selected Areas in Communications, 38(2):334–349, 2019. [19] A. Huang, L. Leqi, Z. Lipton, and K. Azizzadenesheli. Off-policy risk assessment for markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 5022–5050. PMLR, 2022. [20] N. Jiang and L. Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652–661. PMLR, 2016. [21] J. Kiefer. On bahadur’s representation of sample quantiles. The Annals of Mathematical Statistics, 38(5):1323–1342, 1967. [22] J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238–1274, 2013. [23] R. Koenker. Quantile regression [m]. Econometric Society Monographs, Cambridge University Press, Cambridge, 2005. [24] S. N. Lahiri and S. Sun. A Berry–Esseen theorem for sample quantiles under weak dependence. The Annals of Applied Probability, 19(1):108 – 126, 2009. [25] P. W. Lavori and R. Dawson. Dynamic treatment regimes: practical design considerations. Clinical trials, 1(1):9–20, 2004. [26] X. Li, J. Liang, and Z. Zhang. Online statistical inference for nonlinear stochastic approximation with markovian data. arXiv preprint arXiv:2302.07690, 2023. [27] X. Li, W. Yang, J. Liang, Z. Zhang, and M. I. Jordan. A statistical analysis of polyak-ruppert averaged q-learning. In International Conference on Artificial Intelligence and Statistics, pages 2207–2261. PMLR, 2023. 38

[28] P. Massart. The tight constant in the dvoretzky-kiefer-wolfowitz inequality. The annals of Probability, pages 1269–1283, 1990. [29] T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Nonparametric return distribution approximation for reinforcement learning. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 799–806, 2010. [30] F. Naeem, S. Seifollahi, Z. Zhou, and M. Tariq. A generative adversarial network enabled deep distributional reinforcement learning for transmission scheduling in internet of vehicles. IEEE Transactions on Intelligent Transportation Systems, 22(7):4550–4559, 2020. [31] OpenAI. Gpt-4 technical report, 2023. [32] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155, 2022. [33] Y. Peng, L. Zhang, and Z. Zhang. Statistical efficiency of distributional temporal difference learning. Advances in Neural Information Processing Systems, 37:24724–24761, 2024. [34] Y. Peng, K. Jin, L. Zhang, and Z. Zhang. A finite sample analysis of distributional td learning with linear function approximation. arXiv preprint arXiv:2502.14172, 2025. [35] S. Portnoy. Nearly root-$n$ approximation for regression quantile processes. Annals of Statistics, 40:1714–1736, 2012. [36] Z. Qi, C. Bai, Z. Wang, and L. Wang. Distributional off-policy evaluation in reinforcement learning. Journal of the American Statistical Association, 120(551):1517–1530, 2025. [37] M. Rowland, M. Bellemare, W. Dabney, R. Munos, and Y. W. Teh. An analysis of categorical distributional reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 29–37. PMLR, 2018. [38] 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. arXiv preprint arXiv:2301.04462, 2023.

[39] M. Rowland, Y. Tang, C. Lyle, R. Munos, M. G. Bellemare, and W. Dabney. The statistical benefits of quantile temporal-difference learning for value estimation. In International Conference on Machine Learning, pages 29210–29231. PMLR, 2023. [40] D. W. Scott. Multivariate density estimation. Wiley Online Library, 2015. [41] Q.-M. Shao and Z.-S. Zhang. Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548 – 1576, 2022. [42] Q.-M. Shao and W.-X. Zhou. Cramér type moderate deviation theorems for self-normalized processes. Bernoulli, 22(4), 2016. [43] C. Shi, S. Zhang, W. Lu, and R. Song. Statistical inference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(3):765–793, 2022. [44] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018. [45] H. A. Simon. Dynamic programming under uncertainty with a quadratic criterion function. Econometrica, Journal of the Econometric Society, pages 74–81, 1956. [46] R. S. Sutton. The reward hypothesis, 2004. URL http://incompleteideas.net/rlai.cs. ualberta.ca/RLAI/rewardhypothesis.html. [47] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018. [48] H. Theil. A note on certainty equivalence in dynamic planning. Econometrica: Journal of the Econometric Society, pages 346–349, 1957. [49] P. Thomas, G. Theocharous, and M. Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2015. [50] A. van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000. [51] A. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Nature, 2023. 40

[52] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/9781108231596. [53] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350–354, 2019. [54] R. Wu, M. Uehara, and W. Sun. Distributional offline policy evaluation with predictive error guarantees. arXiv preprint arXiv:2302.09456, 2023. [55] D. Yang, L. Zhao, Z. Lin, T. Qin, J. Bian, and T.-Y. Liu. Fully parameterized quantile function for distributional reinforcement learning. Advances in neural information processing systems, 32, 2019. [56] W. Yang, L. Zhang, and Z. Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6):3223–3248, 2022. [57] L. Zhang, Y. Peng, J. Liang, W. Yang, and Z. Zhang. Estimation and inference in distributional reinforcement learning. The Annals of Statistics, 53(5):1987–2011, 2025. [58] F. Zhou, J. Wang, and X. Feng. Non-crossing quantile regression for distributional reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020. [59] Y. Zhu, J. Dong, and H. Lam. Uncertainty quantification and exploration for reinforcement learning. Operations Research, 2023.

Preliminary Lemmas

A.1

Proof of Proposition 2.2

Proof. Define GπH psq “

H ÿ

γ t Rt ,

t“0

H pG s pxq “

qpτ qpR τ pxq

all possible length-H path τ

pR s,a0 p¨q ˚

is the density of random variable

pR s1 ,a1 p¨{γq γ

řH

t“0 γ

2 pR s2 ,a2 p¨{γ q ˚ γ2

¸ ¨¨¨

ff H pR sH ,aH p¨{γ q ˚ pxq γH

t pR | τ q. Here pR pxq is the density of P pdr | s, aq and t R s,a

ˇ ˇ ˇ G ˇ ˇ ˇ H ˇ pRt | τ q „ PR p¨ | st , at q. According to Lemma F.5, supx ˇpR τ pxq ď C0 . Thus supx ps pxq ď C0 , hence GπH psq has bounded density. This also implies ˇ G ˇ ˇFs H pxq ´ FsGH pyqˇ ď C0 |x ´ y| , namely the distribution function of GπH psq is C0 -Lipschitz continuous. Let FsG pxq be the distribution function of Gπ psq. For any x, we have ˇ G ˇ ˇFs H pxq ´ FsG pxqˇ “ PpGπH psq ď xq ´ PpGπ psq ď xq ˆ ˙ γH π π ď PpGH psq ď xq ´ P GH psq ` ďx 1´γ ˇ ˆ ˙ˇ ˇ G γ H ˇˇ GH H ˇ “ ˇFs pxq ´ Fs x´ 1´γ ˇ C0 γ H . ď 1´γ 42

The inequality above implies that }FsGH ´ FsG }8 Ñ 0 as H Ñ 8. To prove the existence and H properties of the density of the return, we establish the equicontinuity of pG s . In fact, we only need

R to notice that pR s,a0 p¨q ˚ rps1 ,a1 p¨{γq{γs is uniform continuous on R for any pa0 , s1 , a1 q and hence has

a modulus of continuity ωs,a0 ,s1 ,a1 pϱq ă 8. Therefore, by Lemma F.6, we know that the continuity H satisfies of modulus of pG s

ωsH pϱq ď

max pa0 ,s1 ,a1 qPAˆSˆA

ωs,a0 ,s1 ,a1 pϱq ă `8.

Applying Arzela–Ascoli theorem, we deduce that η π psq has continuous density pηπ psq upper bounded by C0 and pηπ psq p0q “ pηπ psq pp1 ´ γq´1 q “ 0. To prove that pηπ psq ą 0 on p0, p1 ´ γq´1 q, we use the distributional Bellman equation. Suppose that there exists x P p0, p1 ´ γq´1 q and s P S such that pηπ psq pxq “ 0, then by distributional Bellman equation, ÿ

ż πpa | sqP ps1 | s, aq

ps,a px ´ γyqpηπ ps1 q pyqdy “ 0.

aPA,s1 PS

By Assumption 1 and the continuity of pηπ ps1 q , we know that there exists s1 such that pηπ ps1 q “ 0 on rpx ´ 1q{γ, x{γs X r0, p1 ´ γq´1 s. Denote bl pxq “ px ´ lq{γ, l “ 0, 1 and use the argument repeatedly, then we deduce that for every N , there exists sN P S such that „ pN q pN q psN pyq “ 0, y P rb1 pxq, b0 pxqs X

pN q

where bl

ȷ 1 , 0, 1´γ pN q

is the N -times composition of bl . However, since x P p0, p1 ´ γq´1 q, b0 pxq Ñ `8 and

pN q

b1 pxq Ñ ´8 as N Ñ `8. Therefore, for sufficiently large N , r0, p1 ´ γq´1 s Ď rb1 pxq, b0 pxqs. This implies that there exists s such that pηπ psq ” 0, which is a contradiction. Therefore, Proposition 2.2 holds.

A.2

Other Preliminary Lemmas

In this subsection, we prove several lemmas about T π ηm , which will be useful in the following proofs. First, we prove that the density of T π ηm converges uniformly. › › Lemma A.1. For every s P S, limmÑ`8 ›ppT π ηm qpsq ´ pηπ psq ›8 “ 0.

Proof. We have ˇ ˇ ˇppT π η qpsq pxq ´ pηπ psq pxqˇ m ˇ ffˇˇ « ˇ ÿ ż m ÿ ˇ ˇ ` ˘ 1 ps,a x ´ γθm ps1 , jq ´ ps,a px ´ γyqpηπ ps1 q pyqdy ˇˇ “ ˇˇ πpa | sqP ps1 | s, aq m j“1 ˇ ˇaPA,s1 PS « ff m ´ ¯ˇ ´ ¯ ÿ 1 ÿ ˇˇ ˇ ´1 ´1 1 πpa | sqP ps | s, aq ď ˇps,a x ´ γFpT π ηm qps1 q pτj q ´ ps,a x ´ γFηπ ps1 q pτj q ˇ m j“1 aPA,s1 PS ˇ ˇ m ˇ1 ÿ ´ ¯ ˇ ´ ¯ ż1 ÿ ˇ ˇ πpa | sqP ps1 | s, aq ˇ ps,a x ´ γFη´1 ` ps,a x ´ γFη´1 π ps1 q pτ q dτ ˇ π ps1 q pτj q ´ ˇ ˇ m 0 1 j“1 aPA,s PS

–I1 ` I2 To bound I2 , we notice that as m Ñ `8, ˇ ˇ m ˇ1 ÿ ´ ¯ ż1 ´ ¯ ˇ ˇ ˇ ´1 ´1 ps,a x ´ γFηπ ps1 q pτj q ´ ps,a x ´ γFηπ ps1 q pτ q dτ ˇ ˇ ˇ m j“1 ˇ 0 m ż j ˇ ´ ¯ ´ ¯ˇ ÿ m ˇ ˇ ´1 ď pτ q ´ p x ´ γF pτ q ˇps,a x ´ γFη´1 s,a π ps1 q η π ps1 q j ˇ dτ. j“1

j´1 m

´1 ´1 For j such that 0 P rx ´ γFη´1 π ps1 q ppj ´ 1q{mq, x ´ γFη π ps1 q pj{mqs or 1 P rx ´ γFη π ps1 q ppj ´ 1q{mq, x ´

γFη´1 π ps1 q pj{mqs, we have ż j ˇ ´ ¯ ´ ¯ˇ m ˇ 2C0 ˇ ´1 ´1 p x ´ γF pτ q ´ p x ´ γF pτ q ˇ s,a s,a η π ps1 q η π ps1 q j ˇ dτ ď m . j´1 m

Therefore, as m Ñ 8, ˇ ˇ m ˇ1 ÿ ´ ¯ ż1 ´ ¯ ˇ ˇ ˇ ´1 ´1 p x ´ γFηπ ps1 q pτj q ´ ps,a x ´ γFηπ ps1 q pτ q dτ ˇ ˇ ˇ ˇ m j“1 s,a 0 ď

4C0 ` m

sup

|ps,a pyq ´ ps,a pzq| Ñ 0.

y,zPr0,1s, |y´z|ďωs1 pp2mq´1 q

To bound I1 , for every s1 P S and x, define ! ´ ¯´ ¯ ) ´1 ´1 S0 ps , xq “ j P rms : x ´ γFpT π ηm qps1 q pτj q x ´ γFηπ ps1 q pτj q ď 0 , ! ´ ¯´ ¯ ) ´1 ´1 S1 ps1 , xq “ j P rms : x ´ γFpT x ´ γF pτ q ´ 1 ď 0 , j π η qps1 q pτj q ´ 1 π 1 η ps q m 1

S2 ps1 , xq “rms ´ S0 ps1 , xq Y S1 ps1 , xq, then m ´ ¯ˇ ´ ¯ 1 ÿ ˇˇ ˇ ´1 ´1 x ´ γF pτ q x ´ γF pτ q ´ p p ˇ s,a s,a η π ps1 q j ˇ pT π ηm qps1 q j m j“1

2C0 p|S0 ps1 , xq| ` |S1 ps1 , xq|q ` m

sup

|ps,a pyq ´ ps,a pzq|.

y,zPr0,1s, |y´z|ďW̄8 pT π ηm ,η π q

j P S0 ps1 , xq is equivalent to „

hence

ˆ ˙ȷ ˆ ˙ȷ „ x x τj ´ Fηπ ps1 q ď 0, τj ´ FpT π ηm qps1 q γ γ

ˇ ˆ ˙ˇ ˆ ˙ ˇ › x ˇˇ ›› 1 x 1 ˇ |S0 ps , xq| ď ˇFpT π ηm qps1 q ´ Fηπ ps1 q ď FpT π ηm qps1 q ´ Fηπ ps1 q ›8 . ˇ m γ γ

Similarly, › › 1 |S1 ps1 , xq| ď ›FpT π ηm qps1 q ´ Fηπ ps1 q ›8 . m However, W̄8 pT π ηm , ηq ď γ W̄8 pηm , ηq Ñ 0 as m Ñ `8 by Theorem 3.2, which implies pT π ηm qps1 q converges to η π ps1 q weakly. Since Fηπ ps1 q is continuous, }FpT π ηm qps1 q ´ Fηπ ps1 q }8 Ñ 0 by Lemma F.7. Therefore we have I1 Ñ 0 as m Ñ 8 and the conclusion follows. Next, we prove that the density at the quantiles are strictly positive. Lemma A.2. For every m, s, i, ppT π ηm qpsq pθm ps, iqq ą 0. Proof. We assume there exists m, s, i such that «

ff m 1 ÿ 1 ppT π ηm qpsq pθm ps, iqq “ πpa | sqP ps | s, aq ps,a pθm ps, iq ´ γθm ps , jqq “ 0. m 1 j“1 aPA,s PS ÿ

We can assume πpa | sqP ps1 | s, aq ą 0 for all a, s1 without loss of generality. By Assumption 1 and 2, θm ps, iq ´ γθm ps1 , jq P Rzr0, 1s for every ps1 , jq. Therefore, there exists sufficiently small δ0 ą 0 such that θm ps, iq ´ γθm ps1 , jq P Rzr´2δ0 , 1 ` 2δ0 s and hence ppT π ηm qpsq pxq “ 0 for x P rθm ps, iq ´ δ0 , θm ps, iqs. Therefore, FpT π ηm qpsq pθm ps, iq ´ δ0 q “ FpT π ηm qpsq pθm ps, iqq “ τi . However, ´1 this contradicts the definition of θm ps, iq as θm ps, iq “ FpT π η qpsq pτi q. m

Finally we prove the following lemma, which provides a lower bound of the density function of T π ηm at the boundary and is essential in the following analysis. ´1 ´1 Lemma A.3. Suppose either Assumption 3 or 4 holds. For every m, s and x P rFpT π η qpsq p0q, FpT π η qpsq p0q` m m

κs, we have (9)

FpT π ηm qpsq pxq À xppT π ηm qpsq pxq. ´1 ´1 Similarly, for x P rFpT π η qpsq p1q ´ κ, FpT π η qpsq p1qs, we have m m

´ 1´F

pT π η

m qpsq

pxq À

´1 FpT π η qpsq p1q ´ x m

(10)

ppT π ηm qpsq pxq

Proof. We only prove Equation (9) and (10) can be proved similarly. Denote ␣ ( Spxq “ ps1 , jq : x ´ γθm ps1 , jq P r0, 1s . ´1 ´1 1 1 Then for every x P rFpT π η qpsq p0q, FpT π η qpsq p0q ` κs and ps , jq P Spxq, x ´ γθm ps , jq P r0, κs. m m

Suppose Assumption 3 holds and we have » ÿ

FpT π ηm qpsq pxq “

πpa | sq –

aPA,s1 PS

fi ż P ps1 | s, aq x

ps1 ,jqPSpxq

» ÿ

πpa | sq –

ď aPA,s1 PS

ps,a pz ´ γθm ps1 , jqqdz fl

P ps1 | s, aq

ps1 ,jqPSpxq

Cxfl

Cx πpa | sq – c aPA,s1 PS 1 ÿ

P ps1 | s, aq

ps ,jqPSpxq

“

ps,a px ´ γθm ps1 , jqqfl

C xp π pxq. c pT ηm qpsq

Suppose Assumption 4 holds. By the monotoncity of ps,a , we have żx ps,a pz ´ γθm ps1 , jqqdz ď xps,a px ´ γθm ps1 , jqq. 0

Therefore, » FpT π ηm qpsq pxq “

ÿ aPA,s1 PS

πpa | sq –

fi ÿ ps1 ,jqPSpxq

ż P ps1 | s, aq x m

ps,a pz ´ γθm ps1 , jqqdz fl

» ÿ

πpa | sq –

ď aPA,s1 PS

ps1 ,jqPSpxq

fi P ps1 | s, aq xps,a px ´ γθm ps1 , jqqfl m

“xppT π ηm qpsq pxq.

Omitted Proofs of Non-asymptotic Analysis

We need a technical lemma first. Lemma B.1. For every m P N and s P S, we have ´ ¯ ˇ ˇ ´1 ˇF π ˇ ˇ pT ηm qpsq FpT π ηm qpsq pτi q ` u ´ τi ˇ ˇ ˇ ě cpMq ą 0, inf ˇ ˇ τi p1 ´ τi qu iPrms,0ă|u|ďp1´γq´1 ˇ ˇ where cpMq is a constant that does not depend on m. Proof of Lemma B.1. We denote

Vm,s pτ, uq “

´ ¯ ´1 FpT π ηm qpsq FpT π η qpsq pτ q ` u ´ τ m τ p1 ´ τ qu

´ ¯ ´1 π η qpsq F p pτ q ` tu dt π pT m 0 pT ηm qpsq

ş1 “

τ p1 ´ τ q

Define κ0 “

! ´ ´κ¯ ” 1 κ ¯ı) min Fηπ psq ^ 1 ´ Fηπ psq p1 ´ γq´1 ´ . 2 sPS 2 2

By Lemma A.1, Vm,s uniformly converges to

Vs pτ, uq “

´ ¯ ´1 FpT π ηm qpsq FpT π η qpsq pτ q ` u ´ τ m τ p1 ´ τ qu

´ ¯ ´1 π psq F π p pτ q ` tu dt η 0 η psq

ş1 “

τ p1 ´ τ q

on S “ rκ0 , 1 ´ κ0 s ˆ r´p1 ´ γq´1 , p1 ´ γq´1 s. Therefore, there exists a positive integer M which only depends on M such that for every m ą M and s P S, inf Vm,s pτ, uq ě

pτ,uqPS

1 inf Vs pτ, uq 2 pτ,uqPS

and › › κ › ´1 ´1 › sup ›FpT ´ F π η qpsq η π psq › ď 2 . m sPS

Fix s P S and for pτ, uq satisfying " ˆ ˙* ) ! ´τ ¯ 1 ´1 ´1 ´1 ´1 p2τ p2τ , F ´ 1q ď F pτ q ` u ď max F q , F p1 ` τ q , min Fη´1 π psq η π psq η π psq η π psq η π psq 2 2 we have ´ ¯ ´1 FpT π ηm qpsq FpT pτ q ` u ´τ π η qpsq m

Vs pτ, uq ě

inf τ Prκ0 {2,1´κ0 {2s

´ ¯ pηπ psq Fη´1 π psq pτ q .

Otherwise, we have Vs pτ, uq ě

max tτ, 1 ´ τ u 1´γ ě . 2τ p1 ´ τ qu 2

Now we consider the case where τi P r0, κ0 s and m ą M , and the case where τi P r1 ´ κ0 , 1s can be dealt with similarly. For τi P r0, κ0 s, when ´1 ´1 ´1 ´1 FpT π η qpsq pτi q ` u ě FpT π η qpsq p2τi q, or FpT π η qpsq pτi q ` u ď FpT π η qpsq pτi {2q, m m m m

we have

´ ¯ ˇ ˇ ´1 ˇF π ˇ ˇ pT ηm qpsq FpT π ηm qpsq pτi q ` u ´ τi ˇ 1´γ 1 ˇ ˇě ě . ˇ ˇ τ p1 ´ τ qu 2p1 ´ τ qu 2 i i i ˇ ˇ

´1 Otherwise, we have FpT π η qpsq p2τi q ď κ and m

´ ¯ ´1 FpT π ηm qpsq FpT π η qpsq pτi q ` u ´ τi m u

“ ppT π ηm qpsq pξq

´1 ´1 where FpT π η qpsq pτi {2q ď ξ ď FpT π η qpsq p2τi q. Therefore, m m

´ ¯ ˇ ˇ ´1 ˇF π ˇ ˇ pT ηm qpsq FpT π ηm qpsq pτi q ` u ´ τi ˇ τi {2 1´γ ˇ ˇÁ ě . ˇ ˇ τ p1 ´ τ qu τ p1 ´ τ qξ 2 i i i i ˇ ˇ by Lemma A.3. Therefore, for every m ą M and s P S, " ´ ¯* 1 ´1 inf Vm,s pτi , uq ě min 1 ´ γ, inf pηπ psq Fηπ psq pτ q 4 sPS,τ Prκ0 {2,1´κ0 {2s iPrms,0ă|u|ďp1´γq´1 For m ď M and τi , Wm,s,i puq – Vm,s pτi , uq is continuous and positive by Assumption 2, therefore has a positive lower bound.

Proof of Lemma 4.1. For u ą 0, denote ∆` s,i puq “ FpT π ηm qpsq pθm ps, iq ` uq ´ τi ,

∆´ s,i puq “ τi ´ FpT π ηm qpsq pθm ps, iq ´ uq.

Fix s P S and i P rms and we have ) ! ´1 pτ q ´ F pτ q ě u F ´1 i i π pT ηm qpsq pTpnπ ηm qpsq ! ) “ FpTp π ηm qpsq pθm ps, iq ` uq ´ FpT π ηm qpsq pθm ps, iq ` uq ď ´∆` puq s,i $ n , & ÿ πpa | sqP ps1 | s, aq . 1 pnq Ď pFps,a ´ Fs,a qpθm ps, iq ` u ´ γθm ps1 , jqq ď ´ ∆` puq s,i % 1 m 3 a,s ,j , $ . ď & ÿ πpa | sq 1 rPppnq ps1 | s, aq ´ P ps1 | s, aqsFs,a pθm ps, iq ` u ´ γθm ps1 , jqq ď ´ ∆` puq % 1 m 3 s,i a,s ,j * ď " pnq 1 ` Zs,i ď ´ ∆s,i puq 3 p3q

p1q

p2q

pnq

ÿ πpa | sq

–As,i Y As,i Y As,i , where Zs,i “

a,s1 ,j

pnq rPppnq ps1 | s, aq ´ P ps1 | s, aqspFps,a ´ Fs,a qpθm ps, iq ` u ´ γθm ps1 , jqq.

Applying Bernstein’s inequality (Lemma F.2) and we have « ´ P

pkq As,i

2 Cnp∆` s,i puqq

¯ ď exp ´

τi p1 ´ τi q ` ∆` s,i puq

ff .

p3q

pnq

for k “ 1, 2. To bound PpAs,i q, we bound the MGF of the random variable Zs,i . Denote m

ws,i,a,s1 “

1 ÿ ppnq pF ´ Fs,a qpθm ps, iq ` u ´ γθm ps1 , jqq m j“1 s,a

and for λ P R, we have ˜ pnq E exppλZs,i q ď

ÿ aPA

πpa | sqE exp λ

¸ ” ı ws,i,a,s1 Pppnq ps1 | s, aq ´ P ps1 | s, aq .

s1 PS

pnq

Condition on Fps,a and we have ˜ ES 1ps,aq exp λ ˜

¸ ” ı pnq 1 1 ws,i,a,s1 Pp ps | s, aq ´ P ps | s, aq

s1 PS n ÿ ÿ

¸ ” ı λ 1ps,aq 1 1 “ES 1ps,aq exp ws,i,a,s1 1tSi “ s u ´ P ps | s, aq n i“1 s1 PS ¸ff « ˜ n ” ı n λÿ ÿ 1ps,aq ws,i,a,s1 1tSi “ s1 u ´ P ps1 | s, aq “ ES 1ps,aq exp n i“1 s1 PS and

ˇ ˇ ˇÿ › › ” ıˇ ˇ ˇ › pnq › 1ps,aq ws,i,a,s1 1tSi “ s1 u ´ P ps1 | s, aq ˇ ď 2 ›Fps,a ´ Fs,a › . ˇ ˇ1 ˇ 8 s PS

Therefore, ˆ pnq E exppλZs,i q ď E exp

›2 ˙ Cλ2 ›› ppnq › ›Fs,a ´ Fs,a › n 8

pnq by Hoeffding’s lemma (Lemma F.1). By DKW inequality (Lemma F.3), }Fps,a ´ Fs,a }8 is ?Cn -sub-

gaussian. Therefore, pnq E exppλZs,i q ď

ˆ 2˙ ˆ ˙´ 21 Cλ Cλ2 ď exp 1´ 2 n n2

pnq

for |λ| À n1 , which implies that Zs,i is Cn -sub-exponential. We conclude that ¯ ´ ¯ ´ p3q puq . P As,i ď exp ´cn∆` s,i Therefore, ” P F ´1 pπ

pTn ηm qpsq

« ı ´1 pτi q ´ FpT π η qpsq pτi q ě u ď 3 exp ´ m

2 Cnp∆` s,i puqq

τi p1 ´ τi q ` ∆` s,i puq

A similar argument yields that « ” P F ´1 pπ

´1 pτi q ´ FpT π η qpsq pτi q ď ´u m pTn ηm qpsq

ı ď 3 exp ´

2 Cnp∆´ s,i puqq

τi p1 ´ τi q ` ∆´ s,i puq

and hence » ˇ ı ”ˇ ˇ — ˇ ´1 pτi q ´ FpT P ˇF ´1 π η qpsq pτi qˇ ě u ď 6 exp –´ m pTp π η qpsq n

´ ¯2 ´ Cn ∆` puq ^ ∆ puq s,i s,i ´ τi p1 ´ τi q ` ∆` s,i puq ^ ∆s,i puq

fi ffi fl .

´ Lemma B.1 implies that mint∆` s,i puq, ∆s,i puqu ě cτi p1 ´ τi qu and we have

„ ȷ ˇ ı CcpMq2 nτi p1 ´ τi qu2 ˇ ´1 pτi q ´ FpT pτ q ě u ď 6 exp ´ i ˇ π η qpsq m pTn ηm qpsq 1 ` cpMqu

”ˇ ˇ P ˇF ´1 pπ

where C is a universal constant and cpMq is the constant defined in Lemma B.1. Let the right hand side equal δ and we derive that with probability at least 1 ´ δ, ˇ ˇ ˇ ´1 ˇ ´1 F pτ q ´ F pτ q ˇ pTp π η qpsq i pT π ηm qpsq i ˇ ď n

C cpMq

«c

ff m logp6{δq m logp6{δq ` , n n

where C is a universal constant. Finally, we notice that from the proof of Lemma B.1, cpMq À 1 ´ γ. Therefore, if

c C

m logp6{δq Á 1, n

we have ˇ ˇ ˇ ´1 ˇ ´1 pτ q ˇFpTp π η qpsq pτi q ´ FpT i ˇď π η qpsq m n

C cpMq

m logp6{δq n

always holds. Otherwise, ˇ Cp1 ` Cq ´1 pτi q ´ FpT π η qpsq pτi qˇ ď m pTn ηm qpsq cpMq

ˇ ˇ ´1 ˇF p π

m logp6{δq . n

Therefore Lemma 4.1 holds.

Omitted Proofs of Asymptotic Analysis

C.1

Proof of Lemma 4.2

Proof. Since we only need to prove the conclusion for every fixed integer m, the constants in this proof may depend on m. We know that › › › pnq › ›θm ´ θm ›

pnq “ W̄8 pηm , ηm q ď

1 W̄8 pΠm Tpnπ ηm , Πm T π ηm q 1´γ 51

“

ˇ ˇ 1 ˇ ˇ ´1 pτ q ´ F pτ q sup ˇF ´1 i pT π ηm qpsq i ˇ . 1 ´ γ sPS,iPrms pTpnπ ηm qpsq

Using the same notation and argument as in Appendix B, we deduce that for u ą 0, ˇ

”ˇ ˇ P ˇF ´1 pπ

„

ˇ ´1 pτi q ´ FpT π η qpsq pτi qˇ ą u m pTn ηm qpsq

À exp ´Cn

¯2 ȷ

´ ∆` s,i puq ^ ∆s,i puq

According to Lemma A.2, for every ps, iq, there exists sufficiently small ups, iq ą 0 such that 1 ppT π ηm qpsq pxq ě ppT π ηm qpsq pθm ps, iqq, x P rθm ps, iq ´ ups, iq, θm ps, iq ` ups, iqs. 2 Therefore, ˇ

”ˇ ˇ P ˇF ´1 pπ

ˇ ´1 pτi q ´ FpT π η qpsq pτi qˇ ą u m pTn ηm qpsq

` ˘ À exp ´Cnu2 , u ď ups, iq,

and « ff ż ups,iq ˇı ? ` ˘ ` ˘ ˇ ´1 pτi q ´ FpT n exp ´Cnups, iq2 ` exp ´Cnu2 du π η qpsq pτi qˇ À m pT η qpsq

”? ˇ ˇ E n ˇF ´1 pπ n

À ups, iq´1 . Therefore, ?

„ pnq nEr}θm ´ θm }8 s À |S|m

min

ȷ´1 ups, iq .

sPS,iPrms

The right hand side does not depend on n and the conclusion follows.

C.2

Proof of Lemma 4.3

Proof. A direct calculation shows that ∇Hpθm q “ Gm . For every ps, iq, We have ÿ pGm qps,iq,ps,iq ´

ˇ ˇ ˇpGm qps1 ,jq,ps,iq ˇ

ps1 ,jq‰ps,iq

ff m 1 ÿ 1 ps,a pθm ps, iq ´ γθm ps , jqq “p1 ´ γq πpa | sqP ps | s, aq m j“1 aPA,s1 PS ÿ

“p1 ´ γqppT π ηm qpsq pθm ps, iqq ą 0,

where the last inequality follows from Lemma A.2. Therefore Gm is diagonal dominant and hence invertible.

C.3

Proof of Lemma 4.4

Proof of Lemma 4.4. We prove a upper bound of the VC dimension of the function class Hs,i . We rs,i “ thθ pR, Sq : }θ ´ θm }8 ď p1 ´ γq´1 u. only need to bound the VC dimension of H s,i For any pR, Sq and k, denote 1tRs,a ` γθpSs,a , kq ă θps, iqu “ 1tℓR,S,a,k pθq ą 0u, where ℓR,S,a,k pθq “ θps, iq ´ γθpSs,a , kq ´ Rs,a is an affine function defined on RSˆm . Denote the maximum shattered set as tpRptq , S ptq , uptq qu, t “ 1, . . . , N , then the value of 1thθs,i pRptq , S ptq q ą uptq u is defined by the signs of N |A|m affine functions t “ 1, . . . , N, a P A, k “ 1, . . . , m

ℓRptq ,S ptq ,a,k pθq,

However, N |A|m hyperplanes separates RSˆm into at most |S|m ÿ ˆ j“0

N |A|m j

ˆ ď

eN |A|m |S|m

˙|S|m

areas. Therefore, ˆ N

eN |A|m |S|m

˙|S|m ,

which indicates that N À |S|m logp|A|mq. Since every function ϕ in Hs,i satisfies }ϕ}8 ď 1, this class is

aPA Qs,a -Donsker according

to van der Vaart and Wellner [51].

C.4

Proof of Lemma 4.5

Proof. Define the model family Q “ tpQs,a qs,a : Qs,a ! λ b #S , @ps, aqu , where λ is the Lebesgue measure on r0, 1s and #S is the counting measure on S. We can regard the fixed point of the projected Bellman operator as a functional θm : Q Ñ RSˆrms . For every bounded efficient score g satisfying EQ rgs “ 0, define dQϵs,a “ p1 ` ϵgs,a qdQs,a . Then we differentiate

ϵ q “ T with regard to ϵ and derive H ϵ pθm

ˇ ϵ ˇ dθm ˇ Gm ˇ dϵ ˇ

ϵ“0

ˇ dH ϵ pθm q ˇˇ ` ˇ ˇ dϵ

“ 0.

ϵ“0

However, a direct calculation shows that ˜

ˇ dH ϵ pθm q ˇˇ ˇ ˇ dϵ

¸ @ D “ pYm qps,iq,¨ , g ,

ϵ“0

s,i

where the inner product is defined as xg1 , g2 y “

EQs,a rg1,s,a g2,s,a s .

s,a

Therefore Lemma 4.5 holds.

Omitted Proofs of Limiting Covariance Structure

D.1

Proof of Proposition 3.1

r are bounded operators in L. For K and every ψ P L such that Proof. First we prove that K and Σ }ψ} “ 1, ´ ¯ ˇ2 ˇ ´1 ˇ ĳ ˇ ř 1 πpa | sqP ps1 | s, aqps,a F ´1 pτ q ´ γF ptq ÿ ˇ a,s ˇ η π psq η π ps1 q 2 ˇ ˇ dτ dt ´ ¯ }Kψ} ď ˇ ˇ ´1 ˇ ˇ pηπ psq Fηπ psq pτ q sPS r0,1s2 ´ ¯ ş1 ř ´1 ´1 1 | s, aqp ż 1 πpa | sqP ps F pτ q ´ γF ptq dt ÿ s,a a,s1 0 η π psq η π ps1 q ďC0 dτ ´ ¯2 sPS 0 pτ q pηπ psq Fη´1 π psq ż ÿ 1 C C |S| ´ 0 ¯ dτ “ 0 . “ ´1 1´γ sPS 0 pη π psq Fη π psq pτ q r denote Therefore K is bounded. For Σ, ˜ Ys pr, s1 ; τ q “ Fηπ ps1 q

Fη´1 π psq pτ q ´ r γ

and define independent random variables pRs,a , Ss,a q „ Qs,a . We notice that ff2

« |As pτ, tq|2 “

πpa | sq2 Cov pYs pRs,a , Ss,a ; τ q, Ys pRs,a , Ss,a ; tqq

aPA

ff «

« ÿ

Varpπpa | sqYs pRs,a , Ss,a ; τ qq

Varpπpa | sqYs pRs,a , Ss,a ; tqq

aPA

« ÿ “Var

πpa | sqYs pRs,a , Ss,a ; τ q ¨ Var

« ÿ

πpa | sqYs pRs,a , Ss,a ; tq

aPA

ďτ p1 ´ τ qtp1 ´ tq. where the last inequality follows from ´ ¯ πpa | sqYs pRs,a , Ss,a ; tq “ FpT π ηπ qpsq Fη´1 ptq “t π psq

ÿ E aPA

and 0 ď

aPA πpa | sqYs pRs,a , Ss,a ; tq ď 1. Therefore, for any ψ P L with }ψ} “ 1,

ˇ ˇ2 ˇ ˇ ˇ ˇ As pτ, tq ˇ ˇ dτ dt ´ ¯ ´ ¯ ˇ ˇ ´1 ´1 ˇ ˇ π π p F pτ q p F ptq sPS η psq η psq η π psq η π psq r0,1s2 fi2 » ż ÿ— 1 tp1 ´ tq ffi ď – ´ ¯2 dtfl ´1 0 p π sPS η psq Fη π psq ptq ff2 « ÿ ż p1´γq´1 Fηπ psq pxqp1 ´ Fηπ psq pxqq “ dx pηπ psq pxq 0 sPS

ĳ › › › r ›2 ÿ ›Σψ › ď

By Proposition 2.2, we only need to prove that for some δ0 ą 0, ż δ0 0

Fηπ psq pxq dx ă `8. pηπ psq pxq

According to distributional Bellman equation, ř 1 Fηπ psq pxq a,s1 πpa | sqP ps | s, aqFs,a ˚ pη π ps1 q p¨{γqpxq “ ř . 1 pηπ psq pxq a,s1 πpa | sqP ps | s, aqps,a ˚ pη π ps1 q p¨{γqpxq

However, argue as in the proof of Lemma A.3, we know that Fs,a pxq À xps,a pxq for x P r0, κs. Therefore, şx Fs,a ˚ pηπ ps1 q p¨{γqpxq Fs,a px ´ yqpηπ ps1 q py{γqdy “ ş0x ps,a ˚ pηπ ps1 q p¨{γqpxq 0 ps,a px ´ yqpη π ps1 q py{γqdy şx px ´ yqps,a px ´ yqpηπ ps1 q py{γqdy ď 0 şx ďκ 0 ps,a px ´ yqpη π ps1 q py{γqdy r is bounded. for x P r0, κs, which implies that Σ By the property of the integral operator we know that K is compact. Therefore the Fredholm alternative [7] implies that I ´ γK˚ is invertible if and only if it is injective. Therefore, it suffices to prove injectivity. Define L8 “

8 sPS L r0, 1s with norm }ψ}8 “ sups }ψs }8 . We have

}γKψ}8 ď }ψ}8

sup

γ ´

ÿ ¯

ż1 1

πpa | sqP ps | s, aq

Fη´1 aPA,s1 PS π psq pτ q ´ ¯ γppT π ηπ qpsq Fη´1 π psq pτ q ´ ¯ “ γ }ψ}8 , “ }ψ}8 sup sPS,τ Pp0,1q pηπ psq Fη´1 π psq pτ q sPS,τ Pp0,1q pη π psq

´ ¯ ´1 ps,a Fη´1 pτ q ´ γF ptq ψs1 ptqdt π psq η π ps1 q

which imlies that γK is a γ-contraction on L8 . Therefore, for every v P L8 , the Neumann series zv –

8 ÿ

pγKqk v

k“0

is well-defined in L8 and zv satisfies that pI ´ γKqzv “ v. Now suppose that there exists w P L such that pI ´ γK˚ qw “ 0, then for every v P L8 Ă L, we have xw, vy “ xw, pI ´ γKqzv y “ xpI ´ γK˚ qw, zv y “ 0. However, L8 is dense in L, so w “ 0, which implies that I ´γK˚ is injective and hence invertible.

D.2

Proof of Proposition 4.1

J R u shows that u ptq ” ups, iq for Proof. For the first claim, the expression u “ ψm ` γEm Km m s

t P rpi´1q{m, i{mq for every s P S and i P rms. Therefore, the vector u0 – pups, iqqsPS,iPrms P RSˆrms

satisfies J pI ´ γKm qu0 “ φm,f,s .

The existence can be checked directly and the uniqueness is deduced from the invertibility of I ´γKm . The second claim can also be checked directly. For the third claim, we notice that }ψm ´ ψ}2 À

m ´ ¯ˇ2 ¯ 1 ÿ ˇˇ 1 ´ ´1 ˇ pτ q ˇf FpT π ηm qps0 q pτi q ´ f 1 Fη´1 i ˇ π ps q 0 m i“1 m ż i ˇ ´ ´ ¯ˇ2 ¯ ÿ m ˇ ˇ ´1 1 F pτ q ` pτ q ´ f ˇ dτ ˇf 1 Fη´1 i π ps q η π ps0 q 0 i“1

i´1 m

ˇ ˇ 1 ˇf pyq ´ f 1 pzqˇ `

sup |y´z|ďW̄8 pT π ηm ,η π q y,zPr0,p1´γq´1 s

sup |t1 ´t2 |ďp2mq´1 t1 ,t2 Pr0,1s

ˇ ´ ´ ¯ˇ ¯ ˇ ˇ 1 ´1 1 F pt q pt q ´ f ˇf Fη´1 π ps q 1 η π ps0 q 2 ˇ 0

The first term tends to 0 as m Ñ 8 because of the continuity of f 1 om r0, p1 ´ γq´1 s and Theorem 3.2. The second term tends to 0 because of the continuity of f 1 ˝ Fη´1 π ps q on r0, 1s. 0 For the fourth claim, we notice that Em Km Rm is an integral operator expressed as pEm Km Rm ψqs pτ q “

ÿ ż1 s1 PS

m ÿ

ff pKm qps,iq,ps1 ,jq 1r i´1 , i q pτ q1r j´1 , j q ptq ψs1 ptqdt. m

i,j“1

Therefore, the adjoint operator pEm Km Rm q˚ is given by ÿ ż1

rpEm Km Rm q ψss pτ q “

s1 PS

m ÿ

ff pKm qps1 ,jq,ps,iq 1r i´1 , i q pτ q1r j´1 , j q ptq ψs1 ptqdt. m

i,j“1

JR . Therefore pEm Km Rm q˚ “ Em Km m

D.3

Proof of Lemma 4.6

Proof. Define 1

ps,s q Tm pτ, tq “

´ ¯ ÿ 1 ´1 ´1 ´ ¯ πpa | sqP ps1 | s, aqps,a FpT pτ q ´ γF ptq , π η qpsq pT π ηm qps1 q m ´1 ppT π ηm qpsq FpT aPA π η qpsq pτ q m (11)

psq Bm pτ, tq “

As,m pτ, tq ´ ¯ ´ ¯, ´1 ´1 ppT π ηm qpsq FpT π η qpsq pτ q ppT π ηm qpsq FpT π η qpsq ptq m m

(12)

where As,m pτ, tq “

πpa | sq2 CovpR,Sq„PR p¨|s,aqbP p¨|s,aq pYs,m pR, S; τ q, Ys,m pR, S; tqq ,

aPA m

Ys,m pR, S; τ q “

1 ÿ 1tR ` γθm pS, jq ă FT´1 π η psq pτ qu, m m k“1

and 1

T ps,s q pτ, tq “

pηπ psq Fη´1 π psq pτ q

B psq pτ, tq “

´ pηπ psq

´ ¯ ´1 pτ q ´ γF ptq , πpa | sqP ps1 | s, aqps,a Fη´1 π psq η π ps1 q

aPA

As pτ, tq ¯ ´ ¯. ´1 pηπ psq Fηπ psq ptq

Fη´1 π psq pτ q

Then we can check that m ´ ¯ ÿ ż1 ÿ ps,s1 q pEm Km Rm ψqs pτ q “ Tm pτi , τj q1r i´1 , i q pτ q1r j´1 , j q ptq ψs1 ptqdt,

pKψqs pτ q “ r m ψqs pτ q “ pΣ

s1 PS 0 i,j“1 ÿ ż1 ps,s1 q

s1 PS 0 ż1 ÿ m 0 i,j“1

pτ, tqψs1 ptqdt,

´ ¯ psq Bm pτi , τj q1r i´1 , i q pτ q1r j´1 , j q ptq ψs ptqdt, m

ż1 B psq pτ, tqψs ptqdt.

r s pτ q “ pΣψq 0

Therefore for every ψ P L with }ψ} “ 1, we have ˇ ˇ m ´ ˇ ¯ˇ2 ÿ 1 1 ˇ ps,s q ˇ pτ, tq ´ T ps,s q pτi , τj q1r i´1 , i q pτ q1r j´1 , j q ptq ˇ dtdτ ˇT m m m m ˇ ˇ 2 r0,1s i,j“1

ÿ ĳ

}pEm Km Rm ´ Kqψ}2 ď

s,s1 PS

m 1 ÿ ÿ 1 1 |T ps,s q pτi , τj q ´ T ps,s q pτi , τj q|2 m2 s,s1 PS i,j“1 m

The first term vanishes as m Ñ `8 because of the properties of piecewise constant approximation. Now we bound the second term. For every ϵ ą 0, we decompose the first term as 1 m2

¸ ÿ

ÿ `

τi ďϵ ps,s1 q

By Lemma A.1, }Tm

ϵăτi ă1´ϵ

s,s1 PS,jPrms

` τi ě1´ϵ

ps,s q |Tm pτi , τj q ´ T ps,s q pτi , τj q|2 .

´ T ps,s q }8 Ñ 0 on rϵ, 1 ´ ϵs ˆ r0, 1s. Therefore the third summation vanishes 58

as m Ñ 8. Now we bound the first summation, and the second can be dealt with similarly. We have 1 ÿ m2 τ ďϵ i

“

ps,s q |Tm pτi , τj q|2

s,s1 PS,jPrms

ÿ 1 ÿ

ÿ 1

« ÿ

´ ¯2 m ´1 s1 ,j ppT π ηm qpsq FpT pτ q i π η qpsq m ÿ 1 ÿ 1 ´ ¯ ďC0 ´1 m π p F pτ q τi ďϵ pT ηm qpsq sPS pT π ηm qpsq i sPS

m τ ďϵ

ff ´ ¯ 2 ´1 πpa | sqP ps1 | s, aqps,a FT´1 π η psq pτi q ´ γFT π η ps1 q pτj q m m

aPA

By Lemma A.3, we know that for sufficiently large m and sufficiently small ϵ, 1 ÿ m τ ďϵ p i

´1 1 1 ÿ FpT π ηm qpsq pτi q ´ ¯À ´1 m τ ďϵ τi i pT π ηm qpsq FpT π ηm qpsq pτi q ´1

1 ÿ Fηπ psq pτi q ` ď W̄8 pT ηm , η q i m τ ďϵ τi τi ďϵ i ˆ ˙ ´1 1 1 ÿ Fηπ psq pτi q À logpϵmq ¨ sup ωs ` 2m m τ ďϵ τi sPS π

ÿ 1

where the last inequality follows from Lemma 3.2. We deduce from Assumption 5 that for sufficiently small ϵ, 1 ÿ lim sup mÑ`8 m τ ďϵ p i

pT π ηm qpsq

´ ¯À ´1 FpT π η qpsq pτi q m

ż ϵ F ´1 ptq η π psq t

dt.

Put all together and we derive that for every sufficiently small ϵ ą 0, lim sup sup }pEm Km Rm ´ Kqψ}2 mÑ`8 }ψ}“1

ÿ À sPS

˜ż ϵ F ´1 η π psq ptq 0

dt `

ż 1 p1 ´ γq´1 ´ F ´1 ptq η π psq 1´ϵ

1´t

¸ dt

ÿĳ

|T ps,s q |2

` s,s1

Sϵ

Where Sϵ “ r0, 1s ˆ r0, 1szrϵ, 1 ´ ϵs ˆ r0, 1s. Let ϵ Ñ 0 and we conclude that Em Km Rm is bounded on L and }Em Km Rm ´ K} Ñ 0 as m Ñ 8. r m ´ Σ} r Ñ 0, we only need to prove By a similar argument, we know that in order to prove }Σ

that for every s P S, 1 lim sup lim sup 2 mÑ`8 m ϵÑ0

˜ ÿ

m ÿ

τi ě1´ϵ

j“1

ÿ ` τi ďϵ

psq |Bm pτi , τj q|2 “ 0.

First, denote Qs,a “ PR p¨ | s, aq b P p¨ | s, aq and define independent random variables pRs,a , Ss,a q „ Qs,a . We notice that ff2

« ÿ

|As,m pτ, tq| “

πpa | sq CovQs,a pYs,m pRs,a , Ss,a ; τ q, Ys,m pRs,a , Ss,a ; tqq

aPA

ff « ÿ

VarQs,a pπpa | sqYs,m pRs,a , Ss,a ; τ qq

ff ÿ

aPA

VarQs,a pπpa | sqYs,m pRs,a , Ss,a ; tqq

aPA

ff ÿ

“Var

ff ÿ

πpa | sqYs,m pRs,a , Ss,a ; τ q ¨ Var

aPA

πpa | sqYs,m pRs,a , Ss,a ; tq

aPA

ďτ p1 ´ τ qtp1 ´ tq where the last inequality follows from ÿ E

´ ¯ ´1 ptq “t πpa | sqYs,m pRs,a , Ss,a ; tq “ FpT π ηm qpsq FpT π η qpsq m

aPA

and 0 ď

aPA πpa | sqYs,m pRs,a , Ss,a ; tq ď 1. Therefore, we only need to prove that

1 ÿ mÑ`8 m τ ďϵ

lim sup lim sup ϵÑ0

τi ´ ¯2 “ 0. ´1 ppT π ηm qpsq FpT π ηm qpsq pτi q

Apply Lemma A.3 and we derive that 1 ÿ m τ ďϵ

τi ´ ¯2 ´1 i pτ q ppT π ηm qpsq FpT i π η qpsq m ” ı2 ´1 ´1 ÿ FpT π η qpsq pτi q 1 1 ÿ FpT π ηm qpsq pτi q m À ď . m τ ďϵ τi p1 ´ γqm τ ďϵ τi i

Therefore, for every s P S and sufficiently small ϵ, 1 lim sup 2 mÑ`8 m

¸ ÿ

m ÿ

τi ě1´ϵ

j“1

` τi ďϵ

psq |Bm pτi , τj q|2 À

ż ϵ F ´1 ptq η π psq 0

dt `

ż 1 p1 ´ γq´1 ´ F ´1 ptq η π psq 1´ϵ

1´t

dt.

Let ϵ Ñ 0 and the conclusion follows.

D.4

Proof of Lemma 4.7

Proof. First we prove the boundedness of K̄ and the invertibility of I ´ γ K̄. We have

ÿ › ›2 sup ›K̄ψ ›w ď

}ψ}w “1

sPS

ˇ ´ ¯ˇ2 ˇ ˇ ´1 ´1 ÿ ˇπpa | sqP ps1 | s, aqps,a Fηπ psq pτ q ´ γFηπ ps1 q ptq ˇ ws pτ qws1 ptq

r0,1s2 a,s1

dtdτ

ÿ ż 1 C2 C 2 |S| 0 ď dτ “ 0 . ws pτ q 1´γ sPS 0 To prove the invertibility, we define # L8 w r0, 1s “

+ |ψptq| ă `8 , ψ| }ψ}w,8 “ sup tPr0,1s wptq

and L8 w “

L8 ws r0, 1s

sPS

with }ψ}w,8 “ supsPS }ψs }ws ,8 for ψ P L8 w . A similar calculation as in Appendix D.1 shows that ˚ γ K̄ is a γ-contraction on L8 w . Therefore, I ´ γ K̄ is injective on Lw and the Fredhlom alternative

implies that it is invertible. Now we prove that pI ´ γ K̄˚ q´1 ψ “ pI ´ γK˚ q´1 ψ a.e., and we only need to prove that for every ϕ P L, xψ, ϕy “ xpI ´ γK˚ qū˚ , ϕy, where we denote ū˚ “ pI ´ γ K̄˚ q´1 ψ and the inner product is taken in L. We define W by pWϕqs “ ws ϕs , then xpI ´ γK˚ qū˚ , ϕy “ xū˚ , pI ´ γKqϕy “ xū˚ , WpI ´ γKqϕyw “ xψ, pI ´ γ K̄q´1 WpI ´ γKqϕyw . A direct calculation shows that pI ´ γ K̄qWϕ “ WpI ´ γKqϕ, hence we have xpI ´ γK˚ qū˚ , ϕy “ xψ, Wϕyw “ xψ, ϕy.

Moreover, we have ␣ ( CovpR,Sq pZs pτ ; R, Sq, Zs1 pt; R, Sqq “ 1 s “ s1 As pτ, tq. Therefore, CovpR,Sq pZs pτ ; R, Sq, Zs pt; R, Sqq ˚ ūs pτ qū˚s ptqdτ dt w pτ qw ptq 2 s s r0,1s sPS « ż ff2 ÿ 1 Zs pt; R, Sqū˚ ptq s “EpR,Sq dt ws ptq sPS 0 `@ D ˘ “VarpR,Sq Z, pI ´ γ K̄˚ q´1 ψ w ´@ D ¯ “VarpR,Sq rpI ´ γ K̄q´1 Zss , ψs ws .

2 σf,s “

D.5

ÿĳ

Proof of Lemma 4.8

Proof. We prove the following general version: if ν “ pνs qsPS where νs is a finite signed measure on r0, p1 ´ γq´1 s with zero total mass for every s P S, and Zsν ptq “ νs p´8, Fη´1 π psq ptqs, then pγ K̄Z ν qs ptq “ pT π νqs p´8, Fη´1 π psq ptqs. In fact,

pγ K̄Z ν qs ptq “γ

πpa | sqP ps1 | s, aq

“γ

ws1 pτ q

a,s1

´ ¯ ´1 ż 1 ps,a F ´1 ptq ´ γF pτ q νs1 p´8, Fη´1 π π 1 π ps1 q pτ qs η psq η ps q ż1

πpa | sqP ps | s, aq

a,s1

dτ

´ ¯ ps,a Fη´1 π psq ptq ´ γx νs1 p´8, xsdx

“pT π νqs p´8, Fη´1 π psq ptqs. Therefore, denote µ “ pI ´ T π q´1 ν and we have ´1 rpI ´ γ K̄qZ µ ss pt; Rs , Ss q “ rpI ´ T π qµss p´8, Fη´1 π psq ptqs “ νs p´8, Fη π psq ptqs “ Zs pt; Rs , Ss q

and Lemma 4.8 holds.

D.6

Proof of Lemma 4.9

Proof. For any bounded efficient score g, We have xηϵπ , ψy ´ xη π , ψy “ ϵ

T π ηϵπ ´ T π η π ,ψ ϵ

B `

Tϵπ η π ´ T π η π ,ψ ϵ

B `

pTϵπ ´ T π qpηϵπ ´ η π q ,ψ ϵ

F .

Therefore, B

pI ´ T π qpηϵπ ´ η π q ,ψ ϵ

C ÿ

EQs,a rgs,a Y¨,ps,aq s, ψ

pTϵπ ´ T π qpηϵπ ´ η π q ,ψ ϵ

“ s,a

Now we prove that B lim

ϵÑ0

pTϵπ ´ T π qpηϵπ ´ η π q ,ψ ϵ

F ,

“ 0.

We have B

pTϵπ ´ T π qpηϵπ ´ η π q ,ψ ϵ

ff ÿ

πpa | sqrpbRs,a ,γ q# pηϵπ pSs,a q ´ η π pSs,a qqf sgs,a pRs,a , Ss,a q

“E sPS,aPA

and for every pr, s1 q, ˇ ˇ ˇpbr,γ q# pηϵπ ps1 q ´ η π ps1 qqf ˇ ď W1 ppbr,γ q# ηϵπ ps1 q, pbr,γ q# η π ps1 qq “

inf

X„ηϵπ ps1 q,Y „η π ps1 q

E |pr ` γXq ´ pr ` γY q|

“ W1 pηϵπ ps1 q, η π ps1 qq. However, W̄1 pηϵπ , η π q ď W̄1 pTϵπ ηϵπ , Tϵπ η π q ` W̄1 pTϵπ η π , T π η π q ď γ W̄1 pηϵπ , η π q ` W̄1 pTϵπ η π , T π η π q and W1 pTϵπ η π psq, T π η π psqq “

sup f is 1´Lip

|Tϵπ η π psqf ´ T π η π psqf | À ϵ}g}8 .

Combine the two equations and we know that ˇB π Fˇ ˇ pTϵ ´ T π qpηϵπ ´ η π q ˇ ˇ ˇ “ Opϵq. , ψ ˇ ˇ ϵ The proof is completed by the linearity of I ´ T π . 63

Omitted Proofs of Berry–Esseen Bound

In this section, À hides positive constants which are independent of m and n and only depend on M and f . First, we figure out that Theorem 3.4 implies that 0 ă inf σm,f,s ď sup σm,f,s ă `8. m

E.1

Proof of Lemma 4.10

Proof. For any θ P RSˆm , we define pDpθqqps,iq,ps1 ,jq “ 1tps, iq “ ps1 , jqu

πpa | sq

aPA

πpa | sq

pW pθqqps,iq,ps1 ,jq “

s̃PS,kPrms

P ps1 | s, aq m

aPA

P ps̃ | s, aq ps,a pθps, iq ´ γθps̃, kqq m

ps,a pθps, iq ´ γθps1 , jqq,

Gpθq “ Dpθq ´ γW pθq. Theorem 3.4 implies that suppI ´ Km q´J φm,f,s ă 8. m

Therefore, ´1 pnq pnq |φJ m,f,s Gm rHpθm q ´ Hpθm q ´ Gm pθm ´ θm qs| ż1› › ” ´ ¯ ı › ´1 › pnq pnq À D G θ ` tpθ ´ θ q ´ Gpθ q pθ ´ θ q › m m m m m › dt. m m 8

We have |Dpθ1 q ´ Dpθ2 q|ps,iq,ps,iq ď

ÿ aPA

πpa | sq

ÿ P ps̃ | s, aq s̃,k

À |θ1 ps, iq ´ θ2 ps, iq| `

|ps,a pθ1 ps, iq ´ γθ1 ps̃, kqq ´ ps,a pθ2 ps, iq ´ γθ2 ps̃, kqq|

1 }θ1 ´ θ2 }1 , m

and |W pθ1 q ´ W pθ2 q|ps,iq,ps1 ,jq À

1 r|θ1 ps, iq ´ θ2 ps, iq| ` |θ1 ps1 , jq ´ θ2 ps1 , jq|s. m

Therefore, 1 }θ1 ´ θ2 }1 , m 1 }W pθ1 q ´ W pθ2 q}8 À }θ1 ´ θ2 }8 ` }θ1 ´ θ2 }1 , m }Dpθ1 q ´ Dpθ2 q}8 À }θ1 ´ θ2 }8 `

where }A}8 of a matrix A is defined as }A}8 “ sup}x}8 “1 }Ax}8 “ supi

j |Aij |.

Moreover,

according to Lemma A.3, we know that " max sPS,iPrms

´1 pDm qps,iq,ps,iq À max

θm ps, iq p1 ´ γq´1 ´ θm ps, iq , max max sPS,τi ďϵ sPS,τi ě1´ϵ τi 1 ´ τi

* À m.

Therefore, › ›2 › pnq › ´1 pnq pnq |φJ m,f,s Gm rHpθm q ´ Hpθm q ´ Gm pθm ´ θm qs| À m ›θm ´ θm › . 8

pnq

Since }Hn pθm q}8 ď n´1 , we have ˇ ? ˇ › ˇ › ´1 › ›› ˇ n J m › pnq ´1 pnq › › ˇ ˇ rH pθ q ´ Hpθ qs D G rH pθ q ´ Hpθ qs À φ › n m m › À ? . n m m ˇ m 8 ˇ σm,s,f m,f,s m n 8 Finally, ˇ ˇ? m ” ˇ nÿ ıˇ ˇ ˇ pnq pnq f pθm ps, iqq ´ f pθm ps, iqq ´ f 1 pθm ps, iqqpθm ps, iq ´ θm ps, iqq ˇ ˇ ˇ ˇ m i“1 ? ÿ ż m ˇˇ ˇ ¯ 1ˇ ´ n ˇ 1 ˇ ˇ pnq ˇ pnq À ps, iq ´ θm ps, iqq ´ f 1 pθm ps, iqqˇ ˇθm ps, iq ´ θm ps, iqˇ dt ˇf θm ps, iq ` tpθm m i“1 0 ›2 ? ›› pnq › À n ›θm ´ θm › . 8

Therefore, ˆ |D|1On À

sup

}Gn pθq ´ Gn pθm q} `

}θ´θm }8 ďδn

“ ∆1 ` ∆2

›2 ˙ ? ›› pnq m › ? ` m n ›θm ´ θm › 1On n 8

E.2

Proof of Lemma 4.11

Proof. We prove Equation (5) first. First, for every ps, iq P S ˆ rms, define ps,iq

Fδ

“ thθs,i pR, Sq ´ hθs,im pR, Sq : }θ ´ θm }8 ď δu.

According to Appendix C.3, ps,iq

VCpFδ

q À m log m,

where VCp¨q denotes the Vapnik–Chervonenkis dimension of a function class [52]. Notice that for fixed pR, Sq, |Rs,a ´ rθpSs,a , kq ´ γθps, iqs ´ Rs,a ` rθm pSs,a , kq ´ γθm ps, iqs| ď p1 ` γq }θ ´ θm }8 ,

(13)

therefore the following function is an envelop function of Fδ : ps,iq Fδ pR, Sq “

m ÿ πpa | sq ÿ aPA

1t|Rs,a ´ rθm pSs,a , kq ´ γθm ps, iqs| ď p1 ` γqδu.

k“1

According to van der Vaart and Wellner [51], for every ps, iq, › › › › ? › › sup | npH pθq ´ H pθ qq | › n n m ps,iq › ›}θ´θm }8 ďδn ›

ψ1

log n a À ? ` δn m log m, n

where the ψ1 norm of a random variable X is defined as }X}ψ1 “ inftt ą 0 : E expp|X|{tq ď 2u. Therefore, › › › ›? › ›› › › npHn pθq ´ Hn pθm qq› › sup › 8› ›}θ´θm }8 ďδn

ˆ À log m

ψ1

˙ log n a ? ` δn m log m , n

and « › › E∆1 Àm ›pI ´ γKm q´J φm,f,s ›1 E ˆ Àm log m

ff sup

}θ´θm }8 ďδn

log n a ? ` δn m log m . n

›? › › npHn pθq ´ Hn pθm qq›

To prove Equation (4), we figure out that ¯1 ´ ¯1 ´ 2 2 E |ξi |4 E |ξi |3 ď E |ξi |2 › ´1 ›2 › À m2 , À ›Dm 8 where the second inequality follows from the boundedness of hθs,im . Finally, Equation (6) follows from Theorem 3.1.

E.3

Proof of Lemma 4.12

Proof. We prove Equation (7) first. We have pjq

|∆1 ´ ∆1 | À n´ 2

ˇ ıˇ ” ˇ ˇ J θ r θm r θ θm p X qq pX q ´ ph p X q ´ h h pX q ´ h ˇ ˇφm,f,s G´1 j j j j m

sup }θ´θm }8 ďδn 1

À mn´ 2

› ı › › ”› › › › θ rj q›› rj q ´ hθm pX ›h pXj q ´ hθm pXj q› ` ›hθ pX

sup

}θ´θm }8 ďδn

r is an iid copy of the samples, Since X ´

pjq

E|∆1 ´ ∆1 |2

ff 1

¯1

´ 12

À mn

sup

›2 › › › θ ›h pXj q ´ hθm pXj q›

pjq

E|∆1 ´ ∆1 |2

¯1 2

}θ´θm }8 ďδn

By Equation (13), we have

À mn´ 2 δn2 .

Now Equation (7) follows from Cauchy’s inequality. pjq

To prove Equation (8), we can decompose |ξj ||∆2 ´ ∆2 | as follows: ? pjq |ξj ||∆2 ´ ∆2 | À m n

„

› › › › ›2 !› ) › pnq › › pnq › › pn,jq › |ξj | ›θm ´ θm › 1 ›θm ´ θm › ď δn , ›θm ´ θm › ą δn 8 8 8 › ›2 !› › › › ) › pn,jq › › pnq › › pn,jq › ` |ξj | ›θm ´ θm › 1 ›θm ´ θm › ą δn , ›θm ´ θm › ď δn 8 8 8 › › › ¯› › ´› › › pn,jq › › pnq › pnq pn,jq › ` |ξj | ›θm ´ θm › ` ›θm ´ θm › ›θm ´ θm › 8 8 8 › › › !› )ȷ › pnq › › pn,jq › 1 ›θm ´ θm › ď δn , ›θm ´ θm › ď δn 8

We bound the three terms respectively. First, „ › › › ›2 !› › )ȷ › › › pn,iq › › pnq › pnq ´ θm › ą δn ´ θm › ď δn , ›θm E |ξj | ›θm ´ θm › 1 ›θm 8 8 8 › )ı ” !› › › pn,jq ďδn2 E |ξj |1 ›θm ´ θm › ą δn ˆ ˙ 8 2 nδn ďmδn2 exp ´ , m log m and the second term satisfies the same upper bound. pnq

pn,jq

For the third term, denote A “ t}θm ´ θm }8 ď δn , }θm

´ θm }8 ď δn u and we have

› ¯› › › › ı ” ´› › › pnq › › pn,jq › pnq pn,jq › ´ θm E |ξj | ›θm ´ θm › ›θm ´ θm › ` ›θm › 1A 8 8 8 ˆ › ˙ 1 ˆ „› ȷ˙ 1 › › 1 4 4 ` ˘ › pnq ›4 4 › pnq pn,jq › À E|ξj |2 2 E ›θm ´ θm › E ›θm ´ θm › 1A 8

c À

„ „› ȷȷ 1 ›4 4 m log m › pnq pn,jq › E ›θm ´ θm › 1A n 8

By Taylor’s expansion, on the event A, pnq pnq Hpθm q ´ Hpθm q “ Gm pθm ´ θm q ` R n ; pn,jq pn,jq Hpθm q ´ Hpθm q “ Gm pθm ´ θm q ` Rn,j ,

where according to Appendix E.1, › › › pnq › }Rn }8 À ›θm ´ θm › ď δn2 , 8 › › › pn,jq › }Rn,j }8 À ›θm ´ θm › ď δn2 . 8

. Moreover, pnq pnq pnq Hpθm q ´ Hpθm q “ ´rHn pθm q ´ Hpθm qs ´ rHn pθm q ´ Hpθm qs ` rHn pθm q ´ Hpθm qs ` εn pn,jq pn,jq pn,jq Hpθm q ´ Hpθm q “ ´rHnpjq pθm q ´ Hpθm qs ´ rHnpjq pθm q ´ Hpθm qs ` rHnpjq pθm q ´ Hpθm qs ` εn,j .

Subtract the two equations and we have › › › pnq pn,jq › q ´ Hpθm q› 1A ›Hpθm 8

1 1 À `? n n

ff sup

}θ´θm }8 ďδn

› ›? › npHn pθq ´ Hn pθm qq› ` 8

sup

›? › › › › npHnpjq pθq ´ Hnpjq pθm qq›

}θ´θm }8 ďδn

Moreover, › › ´1 › › › ´1 › › À m. ›Gm › ď ›pI ´ γKm q´1 › ›Dm 8 8 8 Therefore, › › ¯› › › ı ” ´› › pn,jq › › pnq › pnq › pn,jq › E |ξj | ›θm ´ θm › ›θm ´ θm ´ θm › ` ›θm › 1A 8 8 8 › › « ff c › 3 › › ›› ? m log m 1 1 › 2 › npHn pθq ´ Hn pθm qq› › ` δn À `? › sup 8› n n n ›}θ´θm }8 ďδn 4 c „ ˆ ˙ ȷ 3 a 1 log n m log m 1 ` δn2 À `? δn m log m ` ? n n n n Put three parts together and we conclude that (8) holds.

Technical Lemmas

Lemma F.1 (Hoeffding’s Lemma). Suppose X P ra, bs is a random variable with EX “ 0, then for any λ P R, E exp pλXq ď exp

ˆ 2 ˙ λ pb ´ aq2 8

Proof. See [6, Lemma 2.2]. Lemma F.2 (Bernstein’s Inequality). Let X1 , ¨ ¨ ¨ , Xn be independent, mean zero random variables, such that |Xi | ď K for all i. Then for every t ą 0, we have ˇ «ˇ ff ˆ ˙ n ˇÿ ˇ t2 {2 ˇ ˇ P ˇ Xi ˇ ě t ď 2 exp ´ 2 , ˇi“1 ˇ σ ` Kt{3 where σ 2 “

řn

2 i“1 EXi is the variance of the sum.

Proof. See [52, Theorem 2.8.4]. Lemma F.3 (Dvoretzky-Kiefer-Wolfowitz (DKW) Inequality). Let X1 , . . . , Xn be real-valued i.i.d. random variables with cumulative distribution function F p¨q. Let Fn denote the associated empirical

distribution function defined by Fn pxq “ n1

řn

i“1 1 tXi ď xu. Then we have for any ϵ ą 0,

ȷ „ 2 P sup |F pxq ´ Fn pxq| ą ϵ ď 2e´2nϵ . xPR

Proof. See [28]. Lemma F.4. Let X1 , ..., XN be any N ě 2 random variables such that for any λ P R, ` ˘ E exp pλXi q ď exp σ 2 λ2 . Then E max |Xi | ď 3σ

log N .

iPt1,...,N u

Proof. For any λ P R, E exppλ|Xi |q ď ErexppλXi q ` expp´λXi qs ď 2 exppσ 2 λ2 q. Therefore, for every λ ą 0, ˆ ˙ ˆ ˙ exp λE max |Xi | ď E exp λ max |Xi | iPt1,...,N u

iPt1,...,N u

“ E max exppλ|Xi |q iPt1,...,N u

N ÿ

E exppλ|Xi |q ď 2N exppσ 2 λ2 q,

i“1

where the first inequality follows from Jensen’s inequality. Take λ “ σ ´1 E max |Xi | ď 2σ iPt1,...,N u

logp2N q ď 3σ

logp2N q and we have

log N .

Lemma F.5. Suppose X1 , ..., XN are a sequence of independent random variables. Xi has density ř pi pxq and N i“1 Xi has density ppxq. If supxPR p1 pxq ď C, then supxPR ppxq ď C. Proof. We have ppxq “ rpppp1 ˚ p2 q ˚ p3 q ¨ ¨ ¨q ˚ pN s pxq,

ş where rf ˚ gs pxq – R f px ´ yqgpyqdy. Therefore, if supxPR p1 pxq ď C, then ż pp1 ˚ p2 qpxq “

ż p1 px ´ yqp2 pyqdy ď

Cp2 pyqdy “ C

and the proof is completed by deduction. Lemma F.6. Suppose X1 , ..., XN are a sequence of independent random variables. Xi has density ř pi pxq and N i“1 Xi has density ppxq. If p1 has modulus of continuity ω1 pϱq, namely for every ϱ ą 0, sup |p1 pxq ´ p1 pyq| – ω1 pϱq ă `8, |x´y|ďϱ

then sup |ppxq ´ ppyq| – ωpϱq ď ω1 pϱq. |x´y|ďϱ

Proof. We have ppxq “ rpppp1 ˚ p2 q ˚ p3 q ¨ ¨ ¨q ˚ pN s pxq, ş where rf ˚ gs pxq – R f px ´ yqgpyqdy. Therefore, if |x ´ y| ď ϱ, ż | pp1 ˚ p2 q pxq ´ pp1 ˚ p2 q pyq| ď

ż |p1 px ´ zq ´ p1 py ´ zq|p2 pzqdz ď ω1 pϱq

p2 pzqdz “ ω1 pϱq.

The proof is completed by deduction. Lemma F.7. Let tFn uně1 and F be distribution functions on R. Suppose that Fn converges to F weakly, and that F is continuous on R. Then as n Ñ 8, }Fn ´ F }8 – sup |Fn pxq ´ F pxq| Ñ 0. xPR

Proof. Fix ϵ ą 0. Since F is continuous and satisfies lim F pxq “ 0, lim F pxq “ 1, xÑ8

xÑ´8

there exist a ă b such that F pxq ď ϵ, x ď a; F pxq ě 1 ´ ϵ, x ě b. 71

Since F is continuous on the compact interval ra, bs, there exists δ ą 0 such that for any |x´y| ď δ, |F pxq ´ F pyq| ď ϵ. Denote M “ tpb ´ aq{δu ` 1 and pM ` 1q points xi “ a `

i pb ´ aq, i “ 0, . . . , M, M

then xi ´ xi´1 ď δ. Because each xi is a continuity point of F and Fn pxi q Ñ F pxi q, there exists N such that for all n ě N and i “ 0, . . . , M , |Fn pxi q ´ F pxi q| ă ϵ. For any n ě N and x P ra, bs, choose i such that xi´1 ď x ď xi . Using the monotonicity of Fn , we have Fn pxq ´ F pxq ď pFn pxi q ´ F pxi qq ` pF pxi q ´ F pxqq ď 2ϵ. Similarly, Fn pxq ´ F pxq ě pFn pxi´1 q ´ F pxi´1 qq ´ pF pxq ´ F pxi´1 qq ě ´ε ´ ε “ ´2ε. Thus for every x P ra, bs, |Fn pxq ´ F pxq| ď 2ϵ. It remains to control the tails. For x ď a, monotonicity gives |Fn pxq ´ F pxq| ď Fn paq ` F paq ď ϵ ` 2F paq ď 3ϵ. Similarly, for x ě b, |Fn pxq ´ F pxq| ď p1 ´ Fn pxqq ` p1 ´ F pxqq ď ϵ ` 2p1 ´ F pbqq ď 3ϵ. Combining the three regions, sup |Fn pxq ´ F pxq| ď 3ϵ xPR

for all n ě N . Therefore the conclusion holds.

Record · ID 353070 · SHA-256 e48bf51a8b96dcd6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.