A Principled Path to Fitted Distributional Evaluation
Authors: Sungee Hong
Jiayi Wang
Zhengling Qi
Raymond K. W. Wong
Venue: NeurIPS 2025 spotlight ()
Keywords: distributional reinforcement learning
fitted-q evaluation
off-policy evaluation
Primary area: theory

Abstract: In reinforcement learning, distributional off-policy evaluation (OPE) focuses on estimating the return distribution of a target policy using offline data collected under a different policy. This work focuses on extending the widely used fitted Q-evaluation---developed for expectation-based reinforcement learning---to the distributional OPE setting. We refer to this extension as fitted distributional evaluation (FDE). While only a few related approaches exist, there remains no unified framework for designing FDE methods. To fill this gap, we present a set of guiding principles for constructing theoretically grounded FDE methods. Building on these principles, we develop several new FDE methods with convergence analysis and provide theoretical justification for existing methods, even in non-tabular environments. Extensive experiments, including simulations on linear quadratic regulators and Atari games, demonstrate the superior performance of the FDE methods.

A Principled Path to Fitted Distributional Evaluation
Sungee Hong Texas A&M University
Jiayi Wang University of Texas at Dallas
Zhengling Qi
George Washington University
Raymond K. W. Wong Texas A&M University
Abstract
In reinforcement learning, distributional off-policy evaluation (OPE) focuses estimating the return distribution of a target policy using offline data collected under different policy. This work focuses extending the widely used fitted for expectation- bbased reinforcement learning-to the distributional OPE setting. We refer this extension as fitted distributional evalua- tion (FDE). While only few related approaches exist, there remains no unified framework for designing FDE methods. To fill this gap, we present a set of guiding principles for constructing theoretically grounded FDE methods. Building on these principles, develop several new FDE methods with convergence analysis and provide theoretical justification for existing methods, even in non-tabular environ- ments. Extensive experiments, including simulations on linear quadratic regulators and Atari games, demonstrate the superior performance of the FDE methods.
cevaluation-develloy
Introduction
In reinforcement learning (RL), the return, defined as the cumulative sum of (discounted) rewards, is a fundamental measure for how well the underlying policy performs. Traditional RI assesses policies by calculating the expected return, whereas distributional RL [5) focuses on the full distribution of return, providing a richer and more complete understanding of the policy behavior. Leveraging distributional properties beyond the expectation (e.g., risk, multimodality) enables the handling of more general tasks, such as risk assessment (27) and risk-sensitive policy learning [c.g.. [5] 32] Therefore, distributional RL has found applications across various domains [e.g..
In this paper, we focus on addressing off off-po evaluation (OPE) problems within distributional RL, referred to distributional OPE. The goal is estimate the return distribution of target policy using data collected under different policy known as the behavior policy. Many distributional OPE methods extend existing OPE techniques from traditional RI., including temporal difference (TD) methods [c. [4 65 52) and model-based approaches [c.g..31]] Bellman residual minimization. well-studied method in traditional RL [e.g.. 33 21 48), was recently adapted for distributional OPE by (26). Another key methodology. fitted Q-evaluation (FQE)-an an iterative algorithm extensively analyzed in traditional RL [e.g.. 10 69
46 59 has also been recently extended to the distributional setting 32 63) In this work, we focus on the distributional extension of FQE.
Unlike FQE, where the discrepancy function (squared lolsoss) is defined over real numbers, distri- butional extensions operate directly on distributions, making the choice of discrepancy non-trivial. Although statistical distances are natural candidates for measuring diserepancy between distributions, some well-known distances (e.g., total variation distance) perform poorly. Existing distributional developed based specific discrepancy functions. [32] utilizes the
extensions of FQE [32 63
p-powered Wasserstein-p metric, whereas [63] is based on log- se-likelihood (closely related to Kull-
back-Leibler (KL) divergence). A general guideline for selecting appropriate discrepancy functions
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in FDE remains unclear, leaving practitioners without systematic guidance for developing valid FQE extensions tailored to their specific needs. In this puper, we address this gap by proposing unified framework for FDE that clarifies the role of discrepancy function selection and enables analysis under broad class of discrepancy functions and general conditions (including non-tabular settings, i.e., inifinite state-action space). Along the way, we establish several guiding principles and provide theoretical support for our framework. Beyond these general principles, we present concrete examples of discrepancy functions derived from our framework, accompanied by their statistical analyses, offering readily applicable discrepancy functions for practitioners. Additionally, our general framework gives rise to FDE methods that overcome some challenges faced by existing distributional OPE approaches (beyond those FQE extensions). In particular, many of such FDE methods support multi-dimensional returns, which are incompatible with widely used quantile-based based methods [e.g.. Furthermore, we provide examples of FDE methods with theoretical guarantees for unbounded distributions, in contrast to conventionally assumed bounded distributions [e.g.. 63 45)
15 32 47
Our key contributions are summarized as follows. (1) Principled Framework for Fitted Distributional Evaluation: We introduce guiding principles for constructing theoretically grounded extensions of FQE to the distributional OPE problems, which we term fitted distributional evaluation (FDE) methods. In particular, we show that functional Bregman divergences are natural candidates for the discrepancy measures within this framework. See Section 2 (2) Survey of Valid Discrepancy Measures: Leveraging the proposed framework, we derive many examples and discover novel discrepancy measures that have not previously been considered as objective functions for distributional OPE. See Tables I and 2 (3) Unified Statistical Convergence Analysis: We provide comprchensive convergence analysis covering a broad class of FDE methods in tabular (i.e., finite state-action space) and non-tabular settings. This significantly expands the set of distributional OPE methods with theoretical guarantees in non-tabular scenarios. See Section
2 Fitted distributional evaluation in off-policy settings
Consider homogeneous Markov decision process (S, where S and A refer to the state and action spaces, p is the transition probability, and 7 E [0, 1) is the discount factor. More specifically, the transition probability p represents the conditional distribution of reward R E Id and next state S' E conditional on the current state E S and action A E A. We shall focus on the evaluation of stationary target policy क : S - A(A) under infinite-horizon setting. Consider trajectory ((St, Ae, Re) Re) generated by iteratively sampling from the target policy and the transition probability: A (:()S.) and RG, Se41 p(-|S,, At) (and some initial distribution of So). The return of the trajectory is defined by E120 7 RR, Unlike traditional RL which focuses on the policy value, i..., the expectation of return, distributional RL considers the whole distribution of return. Analogously to Q-function estimation in traditional RL, the policy evaluation problem in distributional RI., known as distributional policy evaluation, aims to estimate the conditional distribution of return Y, PSSA (with P C A(R") as convex set of probability measures"). ). where (s, a) E P refers to the probability measure of Σi20 7' RR under и starting from the initial state-action pair 8, a. We are interested in distributional policy evaluation in the off-policy setup, where data are collected under different policy, resulting in distributional mismatch. More specifically, we shall assume that the data consisting of tuples in the form (S, A, R, S') that are generated by S ~ μ., A ~ b(-1S) with b being the behavior policy, and followed by (R, S*) ~ p(-1S, A). We further let (S, A) p p b.
2.1 Fitted distributional evaluation algorithm
In traditional RL, fitted Q-evaluation (FQE) [e.g..
10
30
58
29 46 59 is popular approach to
estimate fuuuction,, i.e., (s. == E( R,
It motivated by the Bellman equation
(s, -RR ('v((1)) { R R++ mn
(BTT (s),s, 8, SaeSa A, (1)
where T" : S + SxA is known as the Bellman operator. Based on the contractive property of TT with respect to Los Loo-norm norm, iterative application of the Bellman operator yields convergence towards
For our objective functions to be well-defined, P. should be closed under push- forwarf mapping with respect affine maps: g(z) = 72 for any r in the support of the reward distribution. See Appendix C.1.2

---

the unique target. i.e., lim (B*))+=+"") T Qu = QT in L noom for an initial value Qo. However, the Bellman operator is often unknown and so the evaluation of the RHS in rendering this approach impractical. Instead, given a data set 'D = {(si, di ri, s ) FQE aims to iteratively approximate Qi R B Q 1 by minimizing the mean squared error
(
Q: = arg min
Σ (SDD),
- fr + ((s.a)
EA (0 13))
(t2 1), (2)
QEO
D
sample-approxiimaed RHS of 1" (t,)
where Q R.SA is chosen function class. Suceinctly stated, FQE consists of iteratively solving re- gression problems with predictions Q(s, a) and the Bellman backup toockupr++-ee ++ (t where the squared Ez-loss is used to measure the discrepancy.
We aim to extend FQE for distributional policy evaluation, where the quantity of interest is the whole conditional distribution Yx PSxA instead of the conditional mean Q. RRSAA, To this end, define the distributional Bellman operator T .pSxA -> pSxA by
-/ JRAXSXA ( # rss a d')dd (a' (a'ls' (dp(( ( a)),,,,
(T =
where (9r))# # : P is the push-forward mapping with respect the function gray (x) + ye, that maps the distribution of any random vector X to the distribution of r + 7.X. Analogously to (T) T, is the solution to the distributional Bellman equation: Y = T*Y, As in FQE, would like to form a sequence Y, = T-T, based on the data. In a similar spirit of FQE, given a single observation (s, a, s'), we compute the distributional Bellman backup
V-(r: (', (.-)) =- (0..))# Y a'-
d')dd((a'sss)) P.
(4)
as the target. Then we aim to optimize the prediction (ss, a) such that some discrepancy measure is minimized. Specifically, consider an appropriate mapping d P P - [0, oo). we then formulate distributional extension of FQE by performing iterative minimization:
Y, arg min TEM
Σ (s.D),)')ED
o(T(s,o), V s t 1,
(5)
[P]
where M C A is chosen set of conditional distributions. We call the resulting method fitted distributional evaluation (FDE). See Algorithm[1] ii Appendix its full algorithm. In passing,
[22 also discussed distributional FQE extension with the same name, but there are some key differences as will be explained in Remark 2.1
In FQE, it is straightforward to choose squared fz-loss for minimization as the Bellman backup is real number. However, in FDE, the distributional Bellman backup is a distribution. Thus, to construct a FDE algorithm, key question is:
How to choose d correctly to build a theoretically grounded FDE?
This question is indeed non-trivial. While many known statistical distances are natural candidates for measuring discrepancy between two probabilities, a number of them fail. For instance, total variation distance can perform poorly shown in Section 4 (also Figure T.. A major reason total variation distance does not lead to [3]. See Section 2.33 for more details. This may not be surprising, as the core motivation behind FQE is the contraction argument, which likely extends to its distributional counterpart, FDE. However, metric that guarantees contraction of the distributional Bellman operator may also fail. One example is the (expectation-extendde) or supremun-extendeed Wasserstein distance due biased gradient [7]. The issue originates from the sample approximation based on the Bellman backup in (5). which will be explained in Section 2.4 In Section 2.2] we will outline several principles to choose valid discrepancy D. based on motivating error-bound analysis. Remark 2.1. Two existing methods share a similar construction with FDE. Crucially, both focus exclusively on specific objective functions, without any general guideline on how to select an appropriate divergence d. First, (3 formulated their objective using powered Wasserstein-p) metric (see their Equation (4)). Instead of applying the distributional Bellman backup V (4) based
is that (the expected-extendee exxtended or cypremuu-eextendee contraction of the distributional Bellman operator
3

---

single sample, [32 estimates 7 by leveraging the entire data to approximate the transition dynamics with conditional empirical distributions. However, this approach generally fails to yield consistent estimates in non-tabular settings (i.e., |S x A| oo), introducing potential bias. The second method fitted likelihood evaluation (FI.E) [63], which based on log-likelihood. Unlike FDE, FLE uses only single draw from the distribution Bellman backup, leading to information loss. Moreover, FLE restricted to the cases where the return distributions have densities. Theoretically, their statistical convergence rate (see their Corollary 4.14) is also slower than ours; see details in Section 3.2
2.2 A motivating error-bound analysis
To motivate theoretically grounded FDE method, we begin with error-bound analysis. Firstly, the metric under which the distributional Bellman operator is contractive plays a crucial role. Definition 2.2. (Contraction-inducin metric) Let be metric over PSxA, We call it contraction- inducing metric if 7 is Ç-contraction with respect to rj. i... i( T.T. S 5 (T,,, T2) for constant Ç (0, 1).
We will focus exclusively on contraction-induss inducing metrics under which T is contractive. Given a contraction-induus inducing metric rj. derive the inequality for any sequence To...., Ty E PSSA (see Appendix C
T Σ t=1
T(T, Ix)
7 5² (To Imn
(6)
iteration-level
shrinks
T-0000
which provides an upper bound for (T Tx). referred to as the fj-error of Ty. Roughly speaking,
the second term <² TT n) in the enror upper bound (6) becomes negligible we increase
T, due to ( E (0, 1). Then, to ensure small fj-error of Tr, it suffices to additionally require that i,,,, (-, converges. This is the essential goal of the minimization (5). To build successful FDE method, we lay out the following principles to choose a valid pair (f7, 0):
(P1) ij is contraction-inducing metric;
(P2) For any given T E pSxA, the unique minimizer of the population objective F(T; TT): Es Arp, R.S' ((-1..)) (O( A), ND, (R, S", r)) is Y = T.
(P3) For any Ý E PSxA, there exists a function g IR + [0, oo) such that: (i) g(L) = 0 and is continuous at g = minr F(T; i); (ii)
- g( (F( f)) for any Y E PSSA
(P2) ensures that the minimizer of the population objective PCM:M,-1 of (5) is the target T 1-1- In addition, (P3) indicates that sufficiently small value of F(Y; ---1) implies closeness between Y and T-, with respect to the metric ýj. In the following subsections, around these three principles. With the systematic construction based on these principles, we are able to construct wide range of FDEs, even with choices of d that have never been used in the current literature of distributional RL (see Table 2). The above principles do not address the finite-sample error, but we will provide a unified statistical analysis for broad class of FDEs in Section 3
will center discussion
2.3 Contraction-inducing metries
In this subsection, we will focus on the choices of contraction contraction-inducing metrics (PI). To broaden the choices of valid discrepancy d (see (P3)), we describe two classes of contraction-induuin over pSxA, The first class comprises supremum-extended metrics 77. which are well studied in the literature [e.g.. 42 40 6). whereas the second class consists of inpectation-extendee metrics 8 which have received significantly less attention but are particularly useful for large or continuous state-action spaces.
metrics
Supremum extension defined as
Given a probability metric 7) over P, its supremum-extended metric is
7o0 (T, T2) = sup (P(T((ss,) ( Yı, T2 e PSxA.
{
(7)
s.a
Uniqueness is only required to hold almost surely over the data generating distribution

---

If the individual probability metric satisfies (i) scale-sensitivity (e-sensitivity), (ii) location- insensitivity (regularity) and (ii)) g-convexity. collectively denoted by (S-L-C) with definitions deferred to Appendix C.4 then Tho is a contraction-inducing metric with = 7f (proof in Ap- pendix C.3.2p. Our result is a slight extension from Theorem 4.25 of [G), not requiring that R and S' to be independent conditioned on S, A. We have listed three examples that satisfy (S-L-C) in Table of Appendix C.4| along with a survey of other well-known probability metrics that fail to satisty (S-L-C). Examples include total variation distance (TVD) whose supremum extension is not guaranteed to be a inntractioniinuucing metric 5
However, controlling supremum uppremum-ettended metric requires uniform control of probability metrics over all state-action pairs. For large or infinite state-action space, supremum- eetuunded metries can be
challenging to control, which limits the choice of discrepancy d in view of (P3). This is related to the fundamental difficulty for using an expectation-ban control a supermum- -aaeed quantity 7 Indeed, existing analyses of statistical error bounds in 1/oc
criterion (or the sample version in (5) to
for distributional OPE methods mainly focus on tabular setting (IS A| < oo) [e.g..
Expectation extension In view of the above explanation, we also introduce expectation eexetnddoon-xteededd metrics which are more compatible with the expectation-basee criterion (P3). Given probability metric vi over P and a parameter y 2 1, an expectation-extendee metric is defined as
nd..9 ( 12) = [S..And { 17 (T1 T2 A)) (2..)
(8)
where d, E A(S x A) is defined as d, = (1 -1- 1
di with (E) == P((S,, e S|.o, Ag Ps A, T A2) for / 2 1). The distribution dz has appeared commonly in the RL literature [e.g., 39 68 66). and is important for ensuring contraction-inducing property as in Theorem below. Note that the supremum-extended metric 1/ (7) can be regarded as special case of ide.g when + oo (under appropriate conditions of dz). Expectation-extendde metrics (based on possibly different distributions in the expectation) have been recently used for distributional OPE 663 26]. Here, we provide a new result that facilitates the construction of a -ontractooninndccing expectation-extended metric as follows, with the corresponding proof given in Appendix C.3.I
Theorem 2.3. Suppose that probability metric n over P satisfies (S-L-C) with convexity parameter q M2 1 and sensiivvny parameter e > 1/(2g) (see (15) of Appendix C.4). Then the expectation-
extended metric ad a is a contraction-inducii metric with Ç = zo defined in Definition 2.2
2.4 Discrepancy measures
We will now provide some guideline on the choice of discrepancy d. Based on (P2), we would ask how to choose d such that, for any Y E PSSA
PS.A-O.RSST- (( ())
T arg min T'PSSA
(9)
where the minimizer is unique up to almost surely equivalence. Note that E( n (R, S T)JS A = af = T= s, a) for any (s, a) E x A. As such, we hope that this conditional expectation of random measure is the minimizer of the expected discrepancy. In the case of FQE where the discrepancy is defined between two scalar values (see )2, it is well known that minimizing the expected squared loss yields the conditional expectation. However, extending this property to settings where the discrepancy is defined between two measures is less obvious. Nevertheless, we show that a broad family of discrepancies-tthe functional extension of Bregman divergences--oes satisfy this desirable property. This result significantly expands the possible construction of FDE. The formal definition of functional Bregman divergence (43 is technically involved and thus deferred to Definition Cf of Appendix C.I.I] Before further discussion of functional Bregman divergences, we present the following key result, which we prove in Appendix C.1.2
Theorem 2.4. A functional Bregman divergence ò satisfies for any P E A(S x A), transition p. and target policy n.
Despite the technically involved definition of functional Bregman divergence, it has a close relation- ship with strictly proper scoring rule, which has been broadly studied in statistics literature, A scoring rule S(.,)) P x Ωx + R (with 2x being the corresponding support space of P, say Rdd) is strictly
5

---

23 with equality holding only when P = Q. Given a strictly proper scoring rule S. we can always build functional Bregman divergence by letting d(P.Q = () S(P, Q) 2 O, and vice versa (see Definition 3.8 and Theorem 4.1 of (3).. This linkage, together with Theorem 2.4 provides justifications to many examples that have been used in distributional RL, including logarithmic scoring rule [e.g. 63 61 that corresponds to Kullback-eeibler (KL) divergence, and squared maximum mean discrepancy (MMD) with specific kernels [40]. More interestingly, we also find (and analyze) various examples that have never been used in distributional RL, including squared MMD with additional kernels and Le distance based on density functions (see T) Finally, our result also provides justifications for adopting other strictly proper scoring rules (c.g., survival, spheric, Hyvärinen, Tsallis, Brier scoring rules) [c.g.. [3 43 [6]., which are not analyzed in this work.
proper if ()Q.Q) 2 Q) where S(P.Q) := ر2 S(P. ((P.2)dO0 (2) [x)
Remark 2.5. With appropriate differentiability condition, the property P also implies that expected gradient of d (S,, A), Vn (R, S" T)- (with respect to Y) becomes zero at T= This is a crucial unbiased gradient property for building TD-based or more general gradient-based algorithms. Despite our focus on FDE, we note that Theorem 2.4 also provides justifications for building such algorithms (e.g.. TD update based on squared- -MD in [40 67) via functional Bregman divergence.
Next, we discuss the last principle (P3). Unlike (P1) and (P2), which involve single quantity (either 7 or d), (P3) requires establishing an appropriate relationship between the contraction-inducing metric n and the discrepancy d. Since each discrepancy has its own relationship with different probability metrics 7) (prior to their extension to 7j). the discussion of (P3) becomes specific to each pair (7,, d). While a certain level of generalization is possible-for the squared form of some probability metric (i.e., d = =m²). rj can be controlled under conditions such as Assumption 3.2 this framework does not accommodate other divergences (c.g., KL divergence). Additionally, depending on the cardinality of S x A. different forms of î may be employed (c.g.. f = 17co or ij = a)...)) Consequently, unlike (PI) and (P2), it is challenging to establish a concise guideline choose (f). d) based on (P3). Instead, we study number of examples (Table [ for Tise and T ij = r),...). Section 3 provides statistical convergence analyses of FDE methods based on different choices of d.
3 Theoretical results
First, we make the modeling in 55 explicit and write = Me == (To E PSxA : E θ}. We =
assume that the offline dataset D ($s, Ti, s s consists of N independently and identically distributed draws according to: (st, a.) ~ p and rú st ~ pp(-|s,, a.). To simplify the theoretical analysis, we will slightly modify the objective function (5) so that
non-overlapping subsets of data in each iteration. That is, the data is first split into T equally sized partitions, i.e., D = Use[T D, with DD,| = n = N/T (assuming that is divisible by T. without loss of generality), and, at the 1-th iteration, we obtain the estimator fn = arg mingge (r,r(010m,c1)) where
(0000
(TTo(s, a), V- 8, Y ( (s.a.ne")DD
Σ
(10)
For convergence of iteration-level error in 6 i.e., 77 (T..).. o...' T S 0, T To,,. should be accommodated in the chosen model, which is implied by the completeness assumption:
Assumption 3.1. (Completeness) For V0 e θ, T = Ta for some 8' E θ.
This assumption is common in the analysis of many iteration-based RL algorithms [e.g., 60 24.
13 6 63
By Assumption 3.1 there exists a value 6., E ① such that To,, -T"Y
Our results are divided into the following two subsections. In Section 3.1 we focus exclusively on divergences that can be expressed as squared metrics and consider the ta tabular setting. In this case, we can obtain near-minimax optimal convergence rates for various FDEs (see Table ( In Section 3.2 we broaden the analysis to cover a wider range of divergences in both tabular and non-tabular settings (see Table p), establishing theoretical guarantees for many FDEs under more general conditions.
3.1 Squared metric divergence under tabular setting
Under tabular setting (i.e., S x A| < o0), we shall assume that every state-action pair can be observed with non-zero probability, which is at least Pmin = minsa p(s, a) > 0, where p represents

---

the probability mass function of (S, A) in the data generating distribution. In this subsection, we focus on a class of functional Bregman divergences that are squared metrics, i.e., m for some induced metric mn associated with an appropriate inner product space (g, (t. m)) More specifically, we require that each probability distribution μ. E P admits a unique representation G(-lp) E G, and that m(41: M22) [G(-)m4) G(-) (22)ll holds for any M1, /2 E P. (It is possible that some element in G does not correspond to any element in P.) The inner product structure supports a stronger theoretical analysis, leading to near-min mear-minimxx optimal convergence rate established in Theorem 3.3 The precise requirement (including an additional technical condition) for the metric m are formally (IPS)
stated in Definition C.2 of Appendix C.6 We will refer to such metrics metrics. Under mild conditions, squared IPS metrics d = m² are functional Bregman divergences (see Appendix C.9.I). Examples of functional Bregman divergence d that can be represented as squared IPS metrics are listed in Table T
cuner-product-ppeet
See Appendix C for the their technical constructions.
Regarding (P3), we assume that 7) can be well-bounded by m in the following assumption.
Assumption 3.2. The probabaility metric 1) satisfies (S-L-C). For any Pl, P2 E P, there exist some constants Csurr 0, 5 > 6D such that
n(4 12) S Csurr m((1, (12) co.
Theorem 3.3. Suppose Assumptions 3.1 and 3.2 hold. Moreover, given a probability metric n that
satisfies (S-L-C) with convexity parameter 2 and scale-sensitivity parameter e. >> O (i.e., (13) of Appendix C.4 consider the FDE with a functional Bregman divergence m2² where is an IPS metric (Definition C.2 of Appendix C.6). Assume that there exists Cman m E =0,,00 (0) such that
Cmaz.m
sup sup [IG(()To(ss a))lm & Cmmas 2 sup 0
s', }mm) (11)
8 r,s'
Then for any da (0, 1). by letting = 1/ 12- -logi/7( (ogg//ooglll [og(4[8xAA100) J, we have, with probability larger than 50.
N
Too (Y Ix) S go (
(log1/> N. log log(logı 17 N)
4 x A
6/2
cD
log
+
N
5p
Pmin 2
for a constant > that does not depend on any N, A1, 60-
shows valid examples of (d = m², 17). along with the parameters presented in Theorem 3.3 The second last column determines the convergence rate (N6622 up to a logarithmic order), which depends on the moment cover unbounded distributions. We can see that 12, dr.,. MMD achieves Op(N Op(N))((2)) (up to logarithmic order) in W -e for bounded distributions (i.e., r = oo), where W pp.co is the supremum extension (7) of W, metric. For p 1, the convergence rate is (near- )optimal, aligning with the minimax optimal convergence rate for 11,0-- -error shown in Theorem B.1 of 455 (up to a logarithmic order). To our knowledge, there
See Appendix C.6 for its proof and more detailed bound 21 Table
degree > (defined in Table D for those that
no corresponding minimax result for distributional OPE problems when > 1. However, 1/(pp(p) comparable the optimal convergence rate of empirical probability measure (Theorem of [18]
Table 1:
Comparison of different FDE methods under tabular setting. See Appendix A for definitions of the suggested examples of d m² and Tee and the corresponding probability space P, such that (a.o) Me S PSAA 2 1 is an integer, and > is such that supsce sups,a Ez (s..o) [|| ["} < co.
d(= m²)
c
8
6
Cramér : 12
Wp.0o
1
1/p
0
MMD-Energy: MMD
MMD
B/2
0
PDF-L2 df
Wp.0
2(r-p)
0
(dFF2))P
MMD-Matem: MMD?
W Pp.0
P-P
0
(d++2r
MMD-RBF MMD
W Wp.oc
2(r-p)
23/2
(((p+d/22
FRBP
(d+22))p
T (p/2)
MMDDRBF-transfommed MMD
W Wpo
1/p
23/2
r(p++d/21
off
T(x/2)
MMD-Coulomb 2
W
1
1/p
0
p.0c
7

---

3.2 General divergence under possibly non-tabular setting
In this subsection, we will discuss general state-action spaces that can be either tabular or non-tabular. As explained in Section 2.3] controlling Tox -eror (like Theorem Theorem 3.3) by an expectation- based objective function is challenging and requires strong assumptions for non-tabular settings. We now shift our focus to the more compatible (expectation-based) Ad, -bbound. In this subsection, we move beyond squared IPS metrics discussed Section [.T and allow d to be more general functional Bregman divergence. Some standard conditions are needed to establish the convergence. Specifically, we assume that the data distribution (p) sufficiently covers the target distribution (dx) (see Assumption C.4), and that the model class satisfies an entropy condition characterized by complexity coefficient a E (0) (see 23 of Assumption C,3
The larger the a, the more complex
the model class.
Table 2 summarizes the theoretical guarantee for a broad class of d based on our theorems. All error bounds are developed using empirical process theory for M-estimation (see Theorem D.Ip. However, different classes of d require separate ways to verify the required modulus condition (Condition 2 of Theorem D.ID. resulting in different convergence rates. To apply the empirical process theory, we introduce surrogate metric for the construction of entropy conditions (e.g., see m in Appendices and and C.15 Informally, this surrogate metric is required to be able to control the differences in the objective function. However, unlike Theorem 3.3 we do not require the divergence to be explicitly constructed from the metric, hence accommodating broader class of divergences. Based on this, we present two general theorems. Theorem C,5 assumes that the surrogate metric is induced by a normed space, while Theorem C.II applies to general surrogate metries. Although Theorem C.3 supports a more limited set of divergences, it provides stronger convergence rate guarantees compared to Theorem C.11 In terms of the scope of applicable divergence choices, we have the following inclusion relationships:
Theorem 3.3 (tabular)
C Theorem C.5 (general)
C Theorem C.I1 (general).
However, the strength of the convergence rate guarantees follows the reverse order. Note that Theorem 3.3 only applies to the tabular case. We remark that some important divergences (e.g.. KL. divergence) are not covered in the aforementioned theorems, requiring separate analysis (see Corollary B.9).
Due to space limitation, we only present a simplified version of Theorem C.5 for reference. The error bound in Theorem [CIII shares similar form.
Let be probability metric that satisfies (S-L-C) with 2 and e > 1/(2q). Suppose Assumptions 3.1 3.2 C.3 and C.od. By letting 8'
Theorem 3.4 (Simplified version of Theorem
T 2(-1)+a 1og/// / NJ with 8' = min 1/g), the corresponding FDE achieves
N
gd or or rx) S x Op
2 60-
log1/7
We now turn to Table 2 which provides several examples of divergences D. (See Appendix A for definitions and Corollaries B.T in Appendix B for detailed bounds.) The table summarizes the pairs (0, (d,..) in Columns 1-2, along with their ability to handle unbounded return distributions, distributions without densities, and their associated return dimensionality considerations (Columns 3-5). If convergence cannot be guaranteed due to a nonzero ég. the corresponding convergence rate omitted. To the best of our knowledge, (63] is the only existing work that provides statistical convergence analysis for distributional OPE in non-tabular settings. In comparison, our FDE method using = l2 (the first row of Table 2 consistently achieves faster convergence rates, as compared to the rate of their FLE method obtained in [63]. across all degrees of Wasserstein metric p > 1 and model complexities (0,2), 2). See (12) of Appendix B. for details.
4 Experiments
We evaluate our FDE methods with baselines through experiments linear quadratic regulator
(LQR) and Atari games. LQR is parametric setting widely studied in RL. literature [e.g.. 9 63 37
Codes available at

---

Table 2:
Comparison of different FDE methods under general state-action space. See Ap- pendix for definitions of examples of and q p 2 an integer, and r p satisfies e s.. (z-Te(s.a) [1] < co. Convergence rates are displayed up to logarithmic order.
Ad..
unbounded
density-free
rate
reference
2
p.dv.p
X
N
Theorem 3.4
MMD
W 1, MMD B,dr,1
/
2
1
N
Theorem
3.4
1=1
MMD
21
Theorem
B>1
-20e=p)
Li,
W p.dx.
X
21
N
(6430))
Theorem
3.4
MMD
W p.
/
X
21
N
[4422jp 24a
Theorem
3.4
MMD
W
p.d.
/
21
Theorem
3.4
RBP 5
MMD
W p.d,,
X
21
Theorem
3.4
MMD
cou
p.d.,
X
#1
N
(6ma)
Theorem
C.11
KL
p.d..
21
N
Corollary B.9
For the LQR experiment, we have compared FDE methods (PDFL2, RBF, Matern, Energy, KL). All of these FDE methods outperformed the baseline FLE [63]. Due space limitations, defer the details to Appendix
Atari games are common testbeds for distributional RL methods [e.g.. 15 40 the proposed FDE methods with FLE [63], QRDQN [13] and IQN
We compared 14]. Among these methods, caanttleebasedd modeling, and adopted Gaussian mixture modeling
52
65
QRDQN and IQN rely (GMM, see details in Appendix(E.2. E.2.I) to model distributions for all other methods. In our experiments, tested different numbers of mixtures / quantiles (M 10. 100, 200) and considered multiple Atari games: Atlantis, Breakout, Enduro, KunfuMaster, Pong. Qbert, Spacelnvader. We estimated Y, -pSx in two different environments (deterministic / random reward), each having different target policies. For each environment, we collected offline data from two different behavior policies (representing strong and weak coverage), with three different sample sizes (N 2K, 5K, 10K). See Appendices E.2.2 and E.2.4 for algorithmic details.
have included the following methods: (i) baseline methods (FLE, QRDQN, IQN), (ii) our FDE methods (KL, Energy, PDF-L2, RBF), (iii) non- con-functional Bregman divergence (TVD) that we did not study. Figure D which contains these methods in order from left to right for four different games, shows the inaccuracy comparison with specific environment and behavior policy. TVD shows improvement of accuracy through iterations, corroborating our proposal to build the objective functions based on functional Bregman divergence in Section 2.4 On the contrary, FDE methods (particularly, KL and Energy) not only decrease the inaccuracy, but also outperform the baseline methods in most games with respect to mean inaccuracy and variance.
In our simulations,
10K and M = 200 under a
AbortisWoframeskiovv
BreikouuthoFFmmssii-vu
EnduroNoframeskippvd
KungF waw.ruuuuasttteffaaemeeee
10
Fracurscy
Paccurccy
F.B
K3N
Enwegy
voruz
100
TVo
F.E
ORION
KNN
roruz
no0
TVo
ORIONN
K04
Energy
POTUz
RBF
TVD
F.E
QROON
KON
Energy
RBF
TVo
Figure I: Mean (dots) and confidence region (mean STD) for seeds based on N 10K samples:
W Wiiiaacurracy (Y-axis) for each method (X-axis) for the games with M = 200. See Figures 3 for simulation results in all seven games.

---

Besides the four settings of Figure 11 we have more results for a wide range of different settings (i.e., seven games, two environments, two behavior policies, three mixture sizes and three sample sizes). Overall, FDE methods outperformed the baseline methods. More details can be found in Appendix F.2 Moveover, we also demonstrated that another functional Bregman divergence- the Hyvärinen divergence, which was not part of our main buddy-perform well in practice, supporting our discussion in Section 2.4 See Figures 3 and Tables 33 of Appendix E.2.5
5 Discussion
central goal of this work is to explore how to choose d for constructing a theoretically sound FDE method. At high level, different d respond differently deviation between Y and v,, in (5). much like how various loss functiins behave differently in empirical risk minimization. Therefore, the choice of divergence should be tailored to the specific problem hand. To move toward principled framework for choosing in specific applications, we believe the first step is to identify what constitutes a valid candidate. To date, this question remains largely unaddressed in the literature, and only few valid choices have been identified let alone systematically compared. Our work makes substantial progress on this front. While comparative analyses of certain functional Bregman divergences do exist and may provide practical guidance, we acknowledge that this work does not yet offer a comprehensive guide for selecting among them practice.
Besides, we acknowledge several other technical limitations of our study. First, while our framework establishes the sufficiency of using functional Bregman divergence ensure the property ( (The- orem 2.4). the necessity remains an open question. Second, for simplicity, our theoretical analysis assumes data splitting, leading to independent samples at each iteration. It would be valuable to extend the analysis to scenarios where data are reused across iterations. Finally, our theorems rely on the completeness assumption (Assumption (.I),, which may be overly restrictive practical settings. We could introduce term that quantifies violations of this assumption via the inherent Bellman error 38 and incorporate into our final bound. We leave such an extension for future work.
Acknowledgments and Disclosure of Funding
Portions of this research were conducted with the advanced computing resources provided by Texas A&M High Performance Research Computing. The work of Jiayi Wang is partly supported by the National Science Foundation (DMS-2401272) and Texas Artificial Intelligence Research Institute (TAIRT).
References
[1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[2] Alquier and M. Gerber. Universal robust regression via maximum mean discrepancy. Biometrika, 111(1):71-92 2024.
[3] A. Banerjee, X. Guo, and H. Wang. On the optimality of conditional expectation as a bregman predictor. IEEE Transactions Information Theory, 51(7):26642266, 2005.
[4] M. G. Bellemare, S. Candido, P. Castro, J. Gong, M. C. Machado, S. Moitra, S. S. Ponda, and Z. Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-88) 2020.
[5] M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective on reinforcement learning. In International conference machine learning, pages 449-458. PMLR. 2017.
[6] M. G. Bellemare, W. Dabney, and M. Rowland. Distributional reinforcement learning. MIT Press, 2023.
[7] M. G. Bellemare, I. Danihelka, W. Dabney, S. Mohamed, B. Lakshminarayanan, S. Hoyer, and R. Munos. The cramer distance as a solution to biased wasserstein gradients. arXiv preprint 1754v 2017.
10

---

[8] C. Bodnar, A. Li, K. Hausman, P. Pastor, and M. Kalakrishnan. Quantile qt-opt for risk-aware vision-based robotic grasping. arXiv preprint 19100077 2019.
[9] Bradtke. Reinforcement learning applied to linear quadratic regulation. Advances in neural information processing systems, 5, 1992.
[10] S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22:33-57, 1996.
[11] D. Chafai, A. Hardy, and M. Maïda. Concentration for coulomb gases and coulomb transport inequalities. Journal of Functional Analysis, 275(6):1447-145) 2018.
[12] S. Chaudhari, D. Arbour, G. Theocharous, and N. Vlassis. Distributional off off-policy evaluation for slate recommendations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages
2024.
[13] J. Chen and N. Jiang. Information-theorre considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1051. PMLR, 2019.
[14] 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.
[15] W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 32, 2018.
[16] A. P. Dawid and M. Musio. Theory and applications of proper scoring rules. Metron, 126 183, 2014.
[17] A. Fawzi, M. Balog, Huang, T. Hubert, B. Komera-Paredes, M. Barekatain, A. Novikov, F. J. R. Ruiz, J. Schrittwiesrr, G. Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53, 2022.
[18] N. Fournier and A. Guillin. On the rate of convergence wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707-738, 2015.
[19] B. A. Frigyik, S. Srivastava, and M. R. Gupta. Functional bregman divergence and bayesian estimation of distributions. IEEE Transactions on Information Theory, 54(11):5130-5139, 2008.
[20] S. A. Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
[21] M. Geist, B. Piot, and O. Pietquin. Is the bellman residual a bad proxy? Advances in Neural Information Processing Systems, 30, 2017.
[22] J. Gerstenberg, R. Neininger, and D. Spiegel. On policy evaluation algorithms in distributional reinforcement learning. arXiv preprint 1411: 2024.
[23] T. Gneiting and A. E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-373 2007.
[24] N. Golowich and A. Moitra. Linear bellman completeness suffices for efficient online reinforce- ment learning with few actions. In The Thirty Seventh Annual Conference on Learning Theory, pages 1939-1999 1981. PMLR, 2024.
[25] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf. and A. Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[26] S. Hong, Z. Qi, and R. K. Wong. Distributional off-po evaluation with bellman residual minimization. arXiv preprint arXiv:2402.0/900, 2024.
[27] A. Huang, L. Leqi, Z. Lipton, and K. Azizzadenesheli. Off-policy risk assessment for markov decision processes. International Conference on Artificial Intelligence and Statistics, pages 5022-5050. PMLR, 2022.

---

[28] A. Korba, F. Bach, and C. Chazal. Statistical and geometrical properties of the kernel kullback- leibler divergence. Advances in Neural Information Processing Systems, 17135566-2266 2024.
[29] I. Kostrikov and O. Nachum. Statistical bootstrapping for uncertainty estimation in off-policy evaluation, arXiv preprint arXiv:2007.13609, 2020.
[30] H. Le, C. Voloshin, and Y. Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
[31] C. E. Luis, A. G. Bottero, J. Vinogradska, F. Berkenkamp, and J. Peters. Value-distributional model-base reinforcement learning. Journal of Machine Learning Research, 25(298):1-444 2024.
[32] Y. Ma, D. Jayaraman, and O. Bastani. Conservative offline distributional reinforcement learning. Advances in neural information processing systems, 34:19235-1999 2021.
[33] O.-A. Maillard, R. Munos, A. Lazaric, and Ghavamzadeh. Finite-samp unite-sample analysis of bellman residual minimization. In Proceedings of 2nd Asian Conference on Machine Learning, pages 299-314. JMLR Workshop and Conference Proceedings, 2010.
[34] E. Mammen and S. van de Geer. Penalized quasi-likelihood estimation in partial linear models. The Annals of Statistics, 250))1014-1035, 1997.
[35] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 51897540):599-33,, 2015.
[36] T. Modeste and C. Dombry. Characterization of translation invariant mmd rd and connections with wasserstein distances. Journal of Machine Learning Research, 25(237):1-39, 2024.
[37] A. N. Moghaddam, A. Olshevsky, and B. Gharesifard. Sample complexity of the linear quadratic regulator: A reinforcement learning lens. arXiv preprint arXiv:2404. 10851, 2024.
[38] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
[39] O. Nachum, Y. Chow, B. Dai, and L. Li. Dualdice: Behavior-agnostic estimation discounted stationary distribution corrections. Advances in neural information processing systems, 32, 2019.
[40] T. Nguyen-Tang, S. Gupta, and S. Venkatesh. Distributional reinforcement learning via moment matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9144 9152, 2021.
[41] S. Nietert, Z. Goldfeld, and K. Kato. Smooth p-wasserstein distance: structure, empirical approximation, and statistical applications. In International Conference on Machine Learning, pages 8172-8183 8183. PMLR, 2021.
[42] E. Odin and A. Charpentier. Dynamic Programming in Distributional Reinforcement Learning. PhD thesis, Université du Québec Montréal, 2020.
[43] E. Y. Ovcharov. Proper scoring rules and bregman divergence. Bernoulli, 24(1):53-79, 2018.
[44] V. M. Panaretos and Y. Zemel. Statistical aspects of wasserstein distances. Annual review of statistics and its application, 6:405-431, 201.9
[45] Y. Peng, L. Zhang, and Z. Zhang. Near minimax-optimil distributional temporal difference algorithms and the freedman incquality in hilbert spaces. CoRR, 2024.
[46] J. C. Perdomo, A. Krishnamurthy, P. Bartlett, and S. Kakade. A complete characterization of linear estimators for offline policy evaluation. Journal of machine learning research, 24(284):1- 50, 2023.
12

---

[47] 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-different learning. Journal of Machine Learning Research, 25(163):1-47, 2024.
[48] E. Saleh and N. Jiang. Deterministic bellman residual minimization. In Proceedings of Optimization Foundations for Reinforcement Learning Workshop at NeurIPS, 2019.
[49] D. Sejdinovic, B. Sriperumbudur, A. Gretton, and K. Fukumizu. Equivalence of distance- and rkhs-based statistics in hypothesis testing. The annals of statistics, pages 2263-2291, 2013.
[50] R. Selten. Axiomatic characterization of the quadratic scoring rule. Experimental Economics, 1(1):43-61, 1998.
[51] B. Sen. A gentle introduction to empirical process theory and applications. Lecture Notes, Columbia University, 11:28-29, 2018.
[52] K. Sun, Y. Zhao, Y. Liu, W. Liu, B. Jiang. and L. Kong. Distributional reinforcement learning via sinkhorn iterations. urXiv preprint arXiv:220.000669, 2022.
[53] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[54] S. van de Geer. Regression analysis and empirical processes. CWI, 1988.
[55] A. W. Van der Vaart and J. A. Wellner. Weak convergence. Springer, 1996.
[56] T. Vayer and R. Gribonval. Controlling wasserstein distances by kernel norms with application to compressive statistical learning. Journal of Machine Learning Research, 24(149):1-51, 2023,
[57] R. Vershynin. High- probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[58] C. Voloshin, H. M. Le, N. Jiang, and Y. Yue. Empirical study of off-policy policy evaluation for reinforcement learning. arXiv preprint
2019.
[59] J. Wang, Z. Qi, and R. K. Wong. A fine-grained analysis of fitted q-evaluation: beyond parametric models. arXiv preprint arXiv:2406. 10438, 2024.
[60] K. Wang, O. Oertell, A. Agarwal, N. Kallus, and W. Sun. More benefits of being distributional: Second-order bounds for reinforcement learning. arXiv preprint Xxii:2442.07198, 2024.
[61] K. Wang, K. Zhou, R. Wu, N. Kallus, and W. Sun. The benefits of being distributional: Small- loss bounds for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
[62] R. Wang. S. S. Du. L. Yang, and R. R. Salakhutdinov. On reward-free reinforcement learn- ing with linear function approximation. Advances in neural information processing systems, 33:17816-17826, 2020.
[63] R. Wu, M. Uehara, and W. Sun. Distributional offline policy evaluation with predictive error guarantees. arXiv prepriní arXiv:2302.094555 2023.
[64] P. R. Wurman, S. Barrett, K. Kawamoto, J. MacGlashan, K. Subramanian, T. J. Walsh, R. Capo- bianco, A. Devlic, F. Eckert, F. Fuchs, et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896):223 228, 2022.
[65] 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.
[66] A. Zanette. When is realizability sufficient for off-policy reinforcement lcarning? In Interna- tional Conference on Machine Learning, pages 40637 40668. PMLR, 2023.
[67] P. Zhang, X. Chen, L. Zhao, W. Xiong, T. Qin, and T.-Y. Liu. Distributional reinforcement learning for multi-dimensional reward functions. Advances in Neural Information Processing Systems, 34:1519-111111 1529, 2021.
13

---

[68] R. Zhang, B. Dai, L. Li, and D. Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09072. 2020.
[69] R. Zhang, X. Zhang, C. Ni, and M. Wang. Off-policy fitted q-evaluation with differentiable function approximators: Z-cstimation and inference theory. International Conference on Machine Learning, pages 15713-26749, PMLR, 2022.
[70] Y. Zhang, X. Cheng, and G. Reeves. Convergence of gaussian-smootien optimal transport distance with sub-gamma distributions and dependent samples. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2021.
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No]. or [NA]
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] providedd proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract contains the summary of the paper's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
14

---

The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We mentioned limitations of our research in the last section of our main text.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Every theorems and lemmas explicitly mention the necessary assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
15

---

Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have elaborated the algorithmic details used in constructing experiment settings.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The data that we used are either simulated on our own, or already made public by OpenAL. All the simulation details in Appendices(E.1 and E.2 After acceptance of the paper, we disclosed the URL to the github repository that contains our Python codes (that have created) which are used for simulations.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cd
for more details.
16

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7 //nips. http://cpppp.ccccceeeeeeee/eeeee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have specified all the algorithmic details including hyperparameters in Appendices T and E.2
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The simulation results contain the mean inaccuracy and standard deviation, thereby providing an error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
17

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (lype of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We specified all the computation details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is purely about methodology of machine learning. Our goal lies in presenting methods and proving their theoretical convergences.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
18

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research does not contain any data or models that could risky. We have used only public open-source data that is available from OpenAl.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The data that we use are open-source data, available from OpenAl.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppsai thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- e-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
19

---

The data that we use are open-source data, available from OpenAl. There are new assets whose documentations are needed. After acceptance, we only added URL the github repository that contains our Python codes (that we have created) which are used in simulations.
Justification:
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our research does contain any crowdsourcing or study over human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: In our study, there was no participation of human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
20

---

Answer:
[NA]
Justification:
LLM is not used in developing the core methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
Table of contents in Appendix
Definitions of metrics and divergences
24
A.I
cnntractioninduccin metrics
24
A.2
Divergences
24
FDE methods for general state-action space
26
B. Cramér FDE
26
B.2
Energy FDE
26
PDF-12 FDE
27
4
MMDD-Matem FDE
27
B.5 5
MMD-RBF FDE
28
B.6
FDB
28
7
MMD-Coulomb FDE
29
B.8 KI. FDB
29
Technical proofs
30
C.1
Functional Bregman divergence
30
Technical definition)
Proof of Theorem
30
How bounding iteration-level error leads to final inaccuracy
................................
31
How extended metrics become intttraactioninnduuce metrics
................................
31
C.3.1
Expectation-extension
31
C.3.2
Supremum-extension
32
C.4
Examples of probability metric
................................
32
Functional spaces and corresponding norms
33
C.6
Proof for Theorem 3.3
34
C.6.1
Outline of proof
34
C.6.2
Proof
................................
35
C.7
Parameters of Examples in Table
37
C.8
Theorem C.5 and its proof
38
C.8.I
Outline of prooi
39
C88.2
Convergence in single step
39
C.8.3
Convergence through multiple steps
40
21

---

C.8.4
Satisfaction of the condition of Lemma C.7 in heorem
41
C.9
About IPS metrics
43
C.9,
How squared IPS metric becomes a functional Bregman divergence
43
C.9.2 How IPS Properties imply NS Properties
43
C.10 Proof for Corollary B.1
45
C.11 Proof of Corollary B.2
46
C. 12 Proof for Corollary B.4
48
C.13 Proof of Corollary B.5
48
C.14 Proofs based on Gaussian regularizer
48
14.1 Proof for Lemma C.9
49
C. 14.2 Proof for Corollary B.6
49
C.14.3 Proof for Corollary B.7
49
C.15
Alternative for violation of (NS4)
50
C.15.1 Proof for Theorem
51
C. 15.2 Proof for Corollary 8.8
53
C.13.3 Proof for Corollary B.3
54
C.16 Proof for Corollary B.9
54
C.16.1
Quadratic lower bound
55
C. 162
Convergence of modulus
55
C. 16.3 Consistence
57
16.4 Finalization
58
C.17 Comparison and examples on Cramér FDB
59
C.17.1
Comparison between Cramér FDE and FLB
59
C. 17.2
Example Linear MDP
60
C. 1.33 Example 2: Linear Quadratic Regulator
61
D Auxiliary proofs for Appendix
63
D.I Supporting theorem
63
Proof of Lemma
63
D.3 Proof of Lemma C.8
63
D.4 Proof of Lemma
64
D.4.J Conditioned event
64
D.4.2 Concentration of modulus
65
D.5 Satisfaction of the condition of Lemma C.7 in
Theorem
66
Experiment Details
67
E.1
Details in Linear Quadratic Regulator
67
Data collection and model
67
E.1.2
Data splitting
67
3
Closed form for gaussian distributions
68
22

---

.4
Simulation results
68
F.2
Details in Atari games
70
E.2.1
Deep Neural Network structure
70
E.2.2
Algorithmic details
70
E E.2.3
Closed / approximated form
71
E.2.4
Simulation settings
72
2.5
Simulation results
72
E,3
Computation resources
84
23

---

A Definitions of metrics and divergences
Following is the generalized algorithm of FDE methods.
Algorithm Fitted distributional evaluation
Input: Functional Bregman divergence d (Tables 12. Model M, Initial Yo E M, Data D
Output: Yr
for / 1 to 7 do
Perform the minimization (5) obtain Y,-
end for
For Tables ! and 2 of Section 3 shall define the necessary concepts needed to understand the objective functions and contraction-induccng metrics.
A.1
Contraction-induccing metries
Following are the individual metrics that satisfy (S-L-C) and their supremum 7 and expectation- extensions (8) (which are cuntractioniinducin metrics (Definition 2.2) that we used in Tables and
2
Wasserstein-p metric is defined as follows, with J(11. 112) being the possible joint distributions of X 11 and Y 12:
1/v
EEXX- YIIP
(p (2) = inf
(p21).
Its supremum and expectation extensions are defined as follows, with their contractive factors (ç of Definition 2.2
W p.co (Y,, T2) == sup w, (s,,a,,
with ( = 7,
8.0
Wp p.d. v (1,, 12)
E
WW (T, T2(s, with ( = -- $
MMD-Energy is defined as the square-rooted form of following MMD-squared (with X, X' p and Y,Y' ~ 22 all being indepenent)
MMD (Mr, (22 (K B Y`) --
with ka y) = || + | | 2||
(0 (0< < 2).
Its supremum and expectation extensions are defined as follows, with
MMD (T,, T2) == sup (S).) T2(s,))) (0< MMD 3,d,, (Y,, T2) BRand [MD T2(sa)) (1< <) with ( イ 1x1
with = 7
s.a
A.2 Divergences
Functional Bregman divergences (choices suggested in Tables and are what determine the objective functions and their corresponding choices of P, whose elements can be used as inputs Our model should satisfy Me S PSAAA
For Cramér FDE,
12 and corresponding P:
12 (2) = /(a
bb F(#|m)) F(z)a2) dz with F(-I)) being edf of P,
P = A(bi, b2]) = {probability measures of distributions bounded in (b,, dz] C RR.

---

For Energy FDE, we use d MMD3 and corresponding P (X, X' ~ p1 and Y, Y ~ 22 being mutually independent):
= + -
with kz(z, == || + | - 11----1- y/1 <0< < 2),
P =W A(RR)) (d 1): ||Ex~ (ka HHH < <o> with H.g being the RKHS of kernel kg.
For PDF-L2 FDE, we use d = -di and corresponding P: (11, = {
- -[(]))))[[(=)))] d= with s(Iu)) being pdf of μ E P,
P { {uE ( (d22) STa ((elu)d= < 00 )o)
For MMD-Matern FDE, we use d = MMD; and corresponding P (X, X ~ in and Y, Y' ~ p2 being mutually independent):
MMD m2) = Re X)) ((,,(Y,
(X,
2 1 yll x Ky
v 2v 22.11x -x--1 ---l >
with (x, = T(v)
for some Mat > 0, 0,
Mat
MMat
p E (d 2 1) || [ (x,,))
(X,
HHl oo}
with Hy being the RKHS of kernel ky-
For MMD-RUM RRF- FDE, we use d = MMD? and corresponding P (X,X' in and Y, Y' ~ p2 being mutually independent):
MMD? ORBF (H1, == EKKonEP (X, + ElKoRRP (Y, 22 B Bhhansr (X,
-1
with
kORBP (x, = (2 ORBF exp
|x - y1p) 4ORBE2
P A(R") (d 1): [Bx~μ [Ex=uthonnd with HoRRE being the RKHS of kornr.
Shounr (x,)))ll < <o0
For MMD-RBF-transformed FDE, we use d = MMD and corresponding P (with conditions of function f and definition of ly are mentioned in Equations 8 and 10 of (70)) (X, X' ~ p1 and Y, Y' μ2 being mutually independent):
MMD? (a, (un, u2) == Bl
EE (K - 2- 22. (X,
with kx,,,)(x, = exp (- Xx |X-
- y11²)
x |x+y||
15
402
V20
D (u E A(RR)) (d 1) [R Mho (X, )) c0)
with Hir,f) being the RKHS of k(o.f)
For MMD-Coulomb FDE, we use d = MMD cou and corresponding P (X, X' ~ #n and Y, Y ~ p2 being mutually independent):
MMD oo (Hi, p2) == Efhicon (X,X)) X')) B (Kooou (Y, ()) 2 E (ilkkonnX,Y00 (x y) = (- -loo |x - yll if d=2 with kcou(X, = N0 (cou)
||xx y
if d23
P= P= A(R)) (d 2 2): Eexxuttioo (X, ))) < 0o) with Homn being the RKHS of know-
For FDE, we use 0 = KL(U2, u1) and corresponding P: (L(H2l1m1) = { f(2)H2) log
f(z f(2(/1) dz, with f(-lu) being pdf of μ E P
P= p=(uE A(X) with X C Rdd (d 2 1) a has density f(:l)) > 0 on X.)..
25

---

B
FDE methods for general state-action space
B.1 Cramér FDE
We construct our objective function [0 based on Cramér distance d 13. and refer this as Cramér FDE. Assuming bounded variables in R. i.e. Z(s, a; 0) E [a, bj for all a E S x A and 0 E θ we with proof and detailed bound in Appendix C.
obtain the following based on Theorem C.5
Corollary B.1. Under Assumptions 3.1
C.4
our estimator
10 based on d t2 achieves the
following in bounded support in I. say a. bj-
Wpddg p (or xx)
Op
N
1-
1og18 N
Here, S means upper-bounded by RHS multiplied by some constant that does not depend on and N.
Although Cramér FDE is limited in bounded uni-dimensional distributions, we can provide direct comparison with FLE under exactly the same conditions, at least for 1. Assuming bounded return distribution with the same model complexity log (Fe. || 00,,,,0, <) S c (where Fe 1og represents the conditional pdf family modeled by @), Cramér FDE achieves faster convergence rate than FLE uniformly for all 2 and a E (0, 2). See Appendix C.17.1 for its proof.
FLE: ; W p Ix) Ör(N
VS
Cramér: W p.dd Tx) 2 ÓOp(N P(SS ).
(12)
Here, Öp indicating the convergence rate, allowing up to logarithmic difference from the conventional Op. We have suggested two examples for Cramér FDE, in which FLE cannot provide a valid bound due to no conditional densities. The first example linear MDP (Appendix CC17.2) that frequently assumed in both traditional and distributional RL [e.g.. 622 46 61. Cramér FDE achieves
rate of (p(N)))(3)) The second example is Linear Quadratic Regulator (Appendix C.1.3)), which has been also been frequently mentioned in traditional RL [c.g.. 9 ( and recently applied in distributional RL under finite-borizontal setting [63]. We extended this towards the Sinite-horizontaa setting. For bounded distributional families, Cramér FDE achieves Wp. pp.d. p. convergecee rate of ONNNN11(0 For unbounded distributional families, its generalized extension Energy FDE (introduced the following subsection) achieves W1,d, 1,,d,,--ooverre conveerence rate of Ô (PN
W
B.2 Energy FDE
Now, we will assume multi-dimensional return (d 2 1), but still bounded. Here, we use d = MMD with 3 E 21, which we name as Energy FDE. MMD, is the MMD (17) with the following
ko 3) = || + || 8
||x - y/l
(1 < 3
Unlike the tabular setting (supported by Theorem 3.3 where we could apply 3 E (0, 1), we have (second statement of Corollary B.2).
to limit to B E (0, 1). But
extend the result into
Considering that 12 4MMD)_ for d = 77 Energy FDE be viewed extension of Cramér FDE. Proofs and detailed bounds are in Appendix C.Il
Corollary B.2. Under Assumptions
3.1 C.4 estimator
10 based on MMD3 with 3 2 1
can achieve the following bound bounded support of Rd
MMD 9,d,, (Yor, Tz) S
1
s-r Op
N
(1< <),
1-
1og1/7
N
1t 1+
MMD, d. (Top, rx)
1og(1/7))
Op (log (log.V) N)
22.
N
24a
-1 (8=1).
26

---

This result can further be used to bound W.d,,1 -inacurraa based on the relationship between MMD, and W based on (36), which is introduced by [36]. Based on Wp(,, v) S D' " (n, v) (suggested by 44
w/
where D E (0, x) represents the diameter of support of bounded distributions, we can further bound W p. Tx) - (2(
wh/p I.d, (Tor: Tx) However, these are still
restricted bounded distributions.
Therefore, let us introduce the case where Energy FDE can bound the inaccuracy for unbounded distributions even without s, a-conditional densities, based on _.d...-inaccurre end, we assume that the r-th moment (r > 1) of the distributions are uniformly bounded, i.e., M, == supsee e [BI) () < cc. See Appendix C.15.3 for proof, which is based on the alternative Theorem [C.I1]
Towards that
3 Corollary B.3. Under Assumptions 3.1 C.4 our estimator 10 based on d = MMD (3 1),
we have following. Assuming that supace sup,,a [s a; 0)ll < co and sups,a [[((( a) ll < 0o
where R(s, a) indicates the reward vector conditioned on we have
1
( (log N)²
20-1)+0
with 1= r(2d + 3)
W 1,d, (Y or a 1 1-11/2
N
Here, having finite values of higher moments (i.e., larger r > 1) leads to tighter convergence rate.
Bounded variables (r oc) will give us I 2d leading to W 1. 1 (Te, Ix) Op πąイ))ー)
In case of d = and r = oo, does not degenerate into that of Corollary B.I since they are based upon different proof structures.
B.3 PDF-L2 FDE
Now let construct the objective function (0) with df.., namely PDF-L2 method. By assuming existence of conditional densities, PDF-L2 method can achieve faster convergence rate for unbounded
distributions than Energy FDE (Corollary B.3). Proof and detailed bound are Appendix CC.12
Corollary B.4. Under Assumptions following bound in Rdd Assuming M, supgge sup,,a (B Z(s a; () /r oo with r >> p and supace sups.s.a ff(()s,,))) < 0c.
3.1 C.4 our estimator
10) based on d = di,, can achieve the
3(r-p) 24a (4+2r)p
W p.d.. (Ter, 1x) S
Op
N
1ogi/7 N
We can see that PDF-L2 method not only provides Wndd -bound for all p 2 1, but also provides faster convergence rate than Energy FDE (Corollary B.3) in the case of p for all > 1, d. 2 and a E (0, 2).
B.4
MMD-Matern FDE
56 has shown that MMD based on translation invariant kernels, i.e., k(x, y) = Ka <x (xxxy. y). can bound Wasserstein metrics when the distributions have smooth enough densities (see their Theorem 15).
One such example is MMD-Matem,, which is the MMD (17) with following kernel with parameters
v > and Mat > 0 (assumed to fixed) and K,, being modified Bessel function,
/2 (
21-V"
122 ||x
yll
ky (x, = r(p)"
Kr
TMat
Matt
We will treat Mat > as fixed constant since we are more interested v. is well-known that 1 corresponds to Laplace kernel and + oc corresponds to RBF kernel. It leads to following result (proof and detailed bound in Appendix C.13).
Corollary B.5. Under Assumptions 3.1 C.4 our estimator
10 based on MMD?, can achieve
the following bound in Rd. Assuming M, == supsee sup,..
[E
Z(s a; 1/ < o0 with p
and its conditional densities having Sobolev norms [[ (s, a) (u4d/2(Rd) < ((< oo), we have
1
Op
N
(d+22))
W p.d, xp (Yor, or, Tx)
1- 1-
1og1/> / N
27

---

Although this can be applied for unbounded distributions as PDF-L2 method (Corollary [B.4). its bound always looser than that of PDF-L2 method, as shown in its convergence rate which half times that of PDF-12 method. This is since the proof of bounding Wasserstein metric by MMD-Matern is based on the following logic.
2ir-p)
W Wp(m: U2) S d (11, MMD, dd-2rpp (21,
See Section 2.4 of [56] for details. This applies for all possible MMD's associated with translation- invariant kernels, other than MMD-Matem.
B.5 MMD-RBF FDE
Since MMD-Matern that is shown above covers the case of 0 < y < oo and requires smooth enough densities. MMD-RBF (corresponding to MMD-Mater with oc) is used lot in many machine learning areas (e.g., kernel support vector machine).
KRRPP y)
(2VT)a OBBF
exp
xx
yl3
with øBBF > 0.
It is also used in distributional reinforcement learning (MMDRL by [40]). They only used it in simulations, without any theoretical justification due to their failure to provide a contraction-inducct metric based on MMD-RBF. Following lemma can provide justification of its practice (proof and detailed bound Appendix (.pendix(C.14.2) not requiring the existence of conditional densities.
Corollary B.6. Under Assumptions 3.1
C.4 assuming M, supsee sups,a [El] //
oo with > p, our estimator 10 based on d MMD øRBF
with ORBF ON can achieve the
let
following bound Rdd
(Crrasbow)
17a/s' (177'0
W P Ix) S
C(p, d, (N,,p)
1 1-7"
1-
N
20r-p) 2Ta (142))P
N
2
T((p + d)/2)
x Orl
logi/7 N
T(p/2) ON
now ran--andom quantity decreasing by ax -00
Fixing ON = OBBF > O leads to an irreducible term at the end. Of course, we can shrink it by letting ON - 0. However, other terms (e.g. C(p, d, N.))), (oN) can increase with ON - leaving the optimal rate of ON to be intractable.
Although we cannot show that MMD-RBF can shrink Wasserstein inaccuracy to zero, it can bound gaussian-smoothed Wasserstein metric We (J,, v) W,(uua, v/*a,) where indicates convolution and a is the probability measure of N a² Ia). This widely used an alternative for Wasserstein metric that is difficult to be computed in high dimensions d > [e.g.. 770, 41). Thus, we have made separate lemma (Lemma C.9 that can accommodate many other probability distances that can bound smoothed gaussain Wasserstein metric, which includes MMD-Two-Moment.
B.6 MMD-RBF-transformed FDE
70 suggested an MMD (17) with the following kernel which is RBF kernel multiplied with an extra term. We will refer to its corresponding MMD MMD RBF-ttaansfoonttte denoting it as MMD (a.f)-
k (x,,)(x.y) = exp (-
||x
y/
(1x+X|I)
402
V20
The conditions of density function and definition of Is are mentioned in Equations 8 and 10 of 70 Assuming bounded kernel (:.) < oo for fixed value O, we can achieve the following. Proof and detailed bound are in Appendix C.14.3
28

---

Corollary B.7. Under Assumptions 3.1
C.4 our estimator 10
based on d = di can achieve the
following bound in R&, if we have k( o0 for fixed value of
1/2
-1/p 2+a
P Tx)
ON
(( max
C Cbrckk (ON)
140/2
-Op
N
log1/7 N
1
2 22-1
[([p + d)/2)
((p/2)
ON
We can let ON - 0 as N - However, the optimal rate is intractable.
One example of such f is generalized beta-prime distributions: f(z) -z))= - (
with
2n5
E (0, d + 2p] and X E (0, oc), which leads Two-moment kernel (see Definition of (70). They have shown that such f(,f)) is bounded in their Section 3.2 for bounded distributions.
B.7 MMD-Coulomb FDE
MMDDCoulumb is an MMD which corresponds to the following kernel.
(cow) yx-y)=
- log ||x - yll
if d 2
kiow (x. y) = Ki0
x y1l2-d
if d 2 3
We can see that k(:s-) .) < oo does not hold, leading to violation of the first statement of (23). Since we
cannot apply Theorem C.3 we should resort Theorem C.I instead,, which gives us the following
result for MMD-Cone CoD-Coulomb Proof and detailed bound are in Appendix C.15.2
Corollary B.8. Under Assumptions 3.1
C.4
our estimator 10 based on d MMD con can achieve
the following bound. Assuming bounded support in R (d 2 2) and supace sup,,a Ecou. (Te(s, a)) < oo with Evon (p) Keou y ()((d))((d))) we have
1 log(1/7)
M) (1og N) N
W p.d.op (orr Tx) S 1 1-27-
Op
We can further bound W p. ditional distributions. Note that the condition E(To(s, a)) oo does not allow nonzero probability to any points.
( gT,, Tx) D2(1-3)
3). w/r
( xx) if assume bounded con-
B.8
KL FDE
Interestingly enough, convergence of FLE 663 can also be shown by Theorem D.I However, since it based on maximium likelihood, which is not squared metric, we could fit this into the structure of neither Theorem C.5 nor C.11 Instead, we developed method that uses log-likelihood (or equivalently, KL divergence), based on Theorem D.I] See Appendix f6 its proof. Note that this is different from FLE in the sense that it fully utilizes the closed form density of T 0 (s', a') and
o (a'ls') needed for V (r, s', ( in computing the objective function [O).. This is free from MC етrоr caused by sampling from V>(r, s', (......) as 63
did.
Corollary B.9. Under Assumptions 3.1 C.4 our estimator 1O with d = KL (Kullback Leibler di-
vergence) achieves the following bound. Assuming bounded distributions and existence of conditional densities, we have following with T
1i-
2+a
1/p
-oogg//
N).
-//-
N
W p.ds (Yor, Tx)
Or
1 1-1
log1/4 N
Here, have log M (F 11l11111..00 ()) S Obrack -a for some a E (0,2) with F1/2 being the squared conditional densities, i.e.. F1/2 [ (-1 .....)) A}.

---

C
Technical proofs
C.1
Functional Bregman divergence
C.1.1 Technical definition
Bregman divergence was originally developed to measure discrepancy between two real vectors, It measures the difference between the value of the convex function ø at IR and its first-order approximation at y E I
yx = x(x) (oVi-dlyy-VV()))))) (V
After defining scalar-valued convex function & over functional inner product space, they can also be extended to functional objects based on Frechet derivative [19].
D g) = + ((g) - (f g)
Based on the fact that each probability measure can have its own functional representation (e.g.. density functions), probability measures. Following is the technical definition of functional Bregman divergence for two probability measures P. Q E P (Section 3.2 of (43).
also extend functional Bregman divergence into discrepancy between two
Definition C.1. Linear span of P, namely spanP, a collection of signed measures, and let 4 S span'P be convex subset that contains P, i.e., P U. Let L(P) be the functional space where its arbitrary element f satisfies Jay [f
for Vu E P with 22x being the support space. Now, assume strictly convex function Ø U R that has subgradient 4 :u + L(P) which satisfies ((Q) 2 (P)) (Q P) + ((P) for all P.Q U, where f . == Jox fdu for any f E L(P) and E spanP. Then we can build a functional Bregman divergence 24 U - R4 on l as follows (Definition 3.8 of 43
d o(P =())))=()))) (P) (Q (PP).
Since functional Bregman divergence in Definition C. IS based strictly convex function +, equality Q) = 0 holds only when P = Q. This is needed to ensure that T*Y becomes the unique minimizer of (9. Note that this is stronger than general definition of functional Bregman divergence (e.g., Definition 3.8 of (43) that is based on standard convex function (which may not be strictly convex).
C.1.2 Proof of Theorem 2.4
We will treat both S, A ~ and R, S' ~ -.....1S,AA to be random. Let Y2 Y2 E pSSA be arbitrary. We obtain the following, by using the same logic that used in their Theorem 1,
E O(T v (R, Ta))
= D ( T2)) क ((T2(S, 40 (T((T(S)))) (R, (S),
Letting T2 = Y and r, = T, we have
E क (T (TV
E
か* (T A)) F V. (R, - -T
5,A -0;
B D(F (.. -. - (TT
30

---

Then, the following holds based on T T*I2(s,a) = (.
E D A), (R 12)) -
-
- -R(0 -T( A)) (V= ((S,A))))
= (ES A), (TT23
Therefore, have
T2)) 3, +E +B (R, (T))
E
(13)
where (T,, T2) B (S, A2, ()), Note that we definition of our empirical and
population objective functions ( and ( already require V sr; E P. Otherwise, they will not be defined. Then, by convexity of P, we have T* a) P, since a convex combination over S ~ p(l|s, a) (see definition 3). This leads to satisfaction of since P is a convex set.
assume that P is closed under push-forward mapping with respect to single-sample Bellman backup functions {gr,> for all E R2 that can be observed. For single-sampe Bellman backup function defined as (r.- == r + ya and X ~ μ4, its result of push-forward mapping (grw)) #1 is defined as the distribution of + +X. Being closed under push-forward mapping means that (9r,)) E P holds for any probability measure μ E P and any r E Rd that can be observed. Then, for an arbitrary T E P55A, we can ensure that ,r, s', s', T) E P holds for any target policy x : - A (AA) and observable (r, s') E IRd S, by its definition (4) and convexity of P.. Then, our objective functions (5) and (9) can always be defined.
To ensure ( P.
C.2 How bounding iteration-level error leads to final inaccuracy
By Definition 2.2 can prove (6) based on T T
i( xx) i((T, Tr,
T T-
T-1, xx) S i(T, TT + ((TT-,,
(T T T (-1 + 5t iTY, Tx).
This leads to (6)
C,3
How extended metries become contraction-inducing metries
C.3.1
expectation-exteesion
Let us show that the expectation-extendee (8) metric satisfies Definition 2.2
TT = EEg R
} 27
(
(T
Letting pr (r, a')s, p(r, s(),s(ss,)) a) <aaalaaaa (a'ls') and temporarily using as probability measure, have
Here, the (A) part can be bounded as follows based on Properties 15
(A) sp ( d')dp" (r, d.'1s,,)), / (nna) To(s', a d') (1,6,,
$ f n2
(grx) To(s' d') di (r, $ 04 [ ( To (r,',
(14)
31

---

where we have used the (C) property of (15) in the second line, and the (S) and (L) properties of the last line. Then, have
15
{{ pa Ta }
29
T T2) <p 204 Es
ld 19
q 2m Bagand By (
5 --200-1 L. sndde { 17 (Ti(s,))) (T) Ta(s,a))
We acknowlegge that the last line can be shown by the trick used by 163 i.e. Rx,an 17' (8, a|s, s y ds a). This finally leads to
Ad o (T",,, - 2े (M,,, T2).
C.3.2 Supremum-extension
We can apply the same logic to supremum-extension
Taking up from
14 we have
(A) S 7 sup (s,,a,, T2(s,
6,0
Taking supremum over S A on the LHS gives us nh 1, T"2 S 409. 77x
( (T,, T2), leading
Too (T,,,, TT) S 70 x7 (T,, T2). Although Theorem 4.25 of [6] presented the same statement, their proof requires an additional assumption, i.e., Rt and S' (generated from p(-- |s, a)) being independent. We did not require this assumption.
C.4 Examples of probability metric
To construct metric ij over pSxA that satisfies Definition 2.2 we will assume to have a probability
metric 77 over P that satisfies the following three properties of (I5) with some >> 0 and 1. We copied the terminologies from [6] (see their Definitions 4.22, 4.23, 4.24). In the first two properties,
[(X) denotes the probability measure of random vector X Rd and pl, H2 X P. E ((X) for some space X can be arbitrary in the third property.
(S) e-scale-sensitiie (T((x)),, ((Y)) S r (((())
(15)
(L) location
insensitive location-insensitive
n(C(X 2), C(Y + 2)) S (((()), ((Y) for arbitrary R
(C) g-convex 178 { (L(t)dd(z), p2(z)dr(z)) < / n/ ( p2(x) (2(e) ddr(s).
Note that if some 2 satisfies the Property-3, then any q' 2 g also satisfies it by Jensen's inequality,
Here are the examples that satisfy the properties in 15 We specify the values of c, > 0 for each
n. Then, specify the contractive factor < -f 2n for their corresponding expectation-exteedee metrics 8 (Note that the supremum-extension
has < = =.)
Wasserstein-p metric (Wp): c= 1,
4 + s
(16)
8
1
= - (
MMD-Energy (MMDg): c=
q 2 and
>
2
3
CDF T.p metric (lp)
g2p 5 = ワク +
Here are the definition of above metrics. W, is the Wasserstein metric, which is defined as follows
with ((1,H2) being the possible joint distributions X #i and Y u2.
1/v
= inf
X Y|P
It is straightforward to see Properties and 2 hold with c 1. Property 3 is shown to hold by 26 (see their Appendix A.3.1).
32

---

MMD (maximum-mee mean discrepancy) 25 associated with a kernel k(-,-) defined as
MMD (22) == [ X, X')
(((K(Y))))
()),
(17)
with X, X #n and Y, Y' μ2 are all independent. MMD, is associated with Energy kernel (x, = |x| |y|l ||x -yl (0 < B 2), Properties 1 and 2 are straightforward show with c = 3/2. Property 3 can be shown with q = 1, since MMD can be expressed as the norm of embeddings, i.e., MMD (H1, U2) [| Kiza ll where Ky is the mean embedding of μ and || 11 is the corresponding RKHS norm of RKHS H.
difference between two
( p1 (1())d((())) / (eald())))) = 1/ (m)(a))((a)) - (patt)dd((x)
MMDA
S [1 - Ki (xdd(x))= MMD (m) (2(r))d(((
Ip is the metric between edf's of 1-dimensional random variable. Letting F; be the edf of μái define
(R In(s)
Lp(nn; p2)
Propertics and 2 are shown with c = 1/p by Proposition 3.2 of [42). Property 3 can be shown by using the fact that Ip is a functional 4, norm between cdf's. The same logic holds for dz,,'
Table 3 also contains the survey of other well-known probability metrics. We will skip proof for their satisfaction or non-satis saissfaasaatoon of each property. With f; and F; being the pdf and edf of probability measure μi.
Hellinger metrie: h(11, U2) =- {t (Viie) vf2(z)
1/2
de
1/P
PDF Lp-metrie: dz, (1i, U2))
fi(2) f2(=) de
Rd
Discrepancy metrie: (pI,
sup
[mI p22
(B)
closed balls B
Kolmogorov metrie: dx (K4, == sup - sER
Table 3: Survey of metrics: If it satisfies c-scale-sensitive or g-convexity, the corresponding value of > or q 2 are specified.
Location-insensittve
Scale-sensitive
Convex
Wasserstein- (W,) p)
q p
MMD-Energy (MMD, with B < 2) MMD-Matern (MMD, with 0 < oc)
3/2
2
X
q 12
CDF-Lp (lp)
1/p
92
PDF-Lp : 1 refers to 2xTVD
x
q 921
Hellinger metric
d/4
X
Discrepancy metric
q 92
Kolmogorov metric
X
q 221
In Table 3 MMD's 's associated with any kernel satisfy convexity with g = 1. However, MMD-Energ was far the only example that we have found, which satisfies all three properties. In the definitions of Wasserstein metric and MMD-Fnergy (Appendix C.4), the Fuclidean norm used can be
replaced with another norm on IRd, See Example 11 of [23] and Proposition 3 of 49 for extensions of MMD-Energy, and <K! for extensions of Wasserstein metrics.
C.5 Functional spaces and corresponding norms
Following are examples of the functional inner product space (g, (m)) and its corresponding probability space P that we have used for our methods in Section 3.1
33

---

For m la (only applying for d = 1). the functional representer is the cdf, denoted by F(-pp). The functional space is the functional L2 space. that is 9 {F : X - R F()) xo with X' = [b1 b2) $ R being bounded support. The equipped inner product (-; "mm)m= (--) is defined as (Fi, F2) Lg := Jx Fi F2 The functional representer of Y To(s, a) E P. namely Fo Fo a)
will be an element of the following set F:
m = 12 (d =
F F - [0 F is edf.) Σ G,
P
(X)) (probabilityy measures that have support in X².
For = dr.g. the functional representer is the pdf, denoted by f(|uu). The functional space is the functional L2 space, that is G := {f X - R: f < oo) with X' C E being the support. The equipped inner product (5, mm = (t is defined as (fi. f2) == Jx fi (=)522 The functional representer of Te(s, a) E P. namely fe(-ls, a) will be an element of the following set F:
F let { x - is a pdf and [[ < <oo} &
m dLz
P let E 1 has pdf and (1(()))) < co}.
For MMD, (maximum mean discrepancy associated with some kernel), the functional represen- ter is the kernel mean embedding, sc(11p) = Ez (k(Z.))) The functional space is the RKHS cor- responding to the given kernel, i.c., 9 = {Σ==1 a k(2,, E R, 24 E X. n E NJ with X C Rd being the support. The equipped inner product the corresponding RKHS inner product, (::) (x that is defined as (Eiz a,k(x,, :), Σi= By,(zz, := Σ Eド= functional representer of To(3, a) E P. namely ka(-)s, a) will be an element of the following set H:
af)). The
= MMD H. let
{n X' + R k()) Ezz ( }}} for some E P}
p {MEP ||((||)]1 < c.).
C.6 Proof for Theorem 3.3
Definition C.2 Unner-prodduc--ppcce metric). The probability metric m over P is called an inner- product-space metric (IPS metric, in short) if there exists an inner product space (G, (z)))) where any element μ P can be uniquely (up to equivalence under zero induced norm [lm) represented by the corresponding element G(-Im) E & such that
(IPSI) The probability m expressed as the norm of difference between functional representers, i.e., m(H1. P2) = [[G(-)/)) G(-Ip2)llms where ||m is the induced norm by the inner product:
(IPS2) Functional representers of probability measures are unbiased with respect probabil- ity mixture. That is, for u(-) 2 + P and arbitrary probability P over 2, we have G(-I.J ((][(((2)PP))) = G(I)(2))dP(())
It is possible that there exists an element in G that does not represent any μ E P.
C.6.1 Outline proof
The first step is to obtain the convergence of single iteration at t-th step. i.e., Tox Moo (Y B,... T B... ,)
Op(L/ve /n). This is similar Lemma 10 of (2, which demonstrates that empirical probability mea- sure converges towards the underlying probability measure in Op(1/
/ (2) rate with respect to MMD. We can generalize the argument to IPS metrics (listed in Appendix C.5 that have corresponding inner product spaces of functional elements. We can form the analogy to the empirical probability measure under tabular setting to simplify the arguments.
The second step to obtain convergence
different steps' estimations. Here, there are two things that play role in determining /-th estimation, i.e., the previous iterate and the data used in the 1-th iteration (denoted as D,, or the 1-th subdataset). Although the previous iterate depends on all previous datasets, i.c., D1. D we can utilize the independence among datasets.
34

---

C.6.2 Proof
Assuming |S A| oc, each state-action pair can be observed with probability at least Pmin inf,,e p(s, a) where p(s, a) = P(S, A = s, aj. We can always assume Pmin without loss of generality, since we exclude of p(8, a) and p(r, s'|s, a) as Ú(s, a) and p(r, |ss a), we can copy the logic of (13) to obtain the following equivalence for nn defined in 100
with p(s, a) > 0 from S x A. Denoting the empirical estimate
E)(,,a) of To(s, B (8.00)
nn. = arg min BEG 8,a
Here, 7" is defined accordingly to B only replacing p(r, s'|s, a) with p(r, s'|s,a).
m into squared form of probability metric so that satisfies relaxed triangular inequality, that is, (P, S 2- 2- (P, R) + m2 (R, Q)). With fixed 0n and its corresponding value fo D, such that Te... T T"To we have following,
Now, we restrict
dn.e_."
(O,,(On. S 2. m (T a.... T" On ) + mi (T on To..)
S my (.... g 0m.e-1) S 4 sup
To. (8, g ono (0.
(18)
n
where (
(8,, 02) =
m² To, To, (s) a.). To (on
(19)
n
Given that To.,, T a.., 1' this comes down to showing T towards T 8_. (s, a) for each s, a. Towards that end, we will assume that each a is observed sufficiently many times. We define the following event along with two probability vectors R.SAA.
a... (s. a) converges in m
Ωo = -- E || plloo S Pumin } with p== (p(s,a) & p p (p(s, a)).
By Lemma A.3 of 126), have
1 P(()) P( pllco Pmiu) <PPp1 pll PPin)) S exp( exp
-n
Pmin 2).
128
Note that conditioning on Po has no effect on the randomness of r, ~ p(... a) for each
Denote its conditional expectation and probability as B(...) .) := E(... (82)) and .P....) - P(... (..).
Based on the IPS Properties of Definition C.2 and (I]. we obtain the following for a fixed 8, a, (s.a)
assuming that we have collected {(s, Ti, s)) for the We acknowledge that this proof is highly based on Lemma 10 of 22]
n(s,a)
on. (6sa0) =B Te.. n(x,a)
V (n b/, T 1
To (8, ( T
m
n(s.a)
G( To. To a)) 0 (n(ss
E
Σ
V
(n 8/6 To
n(8,a)
E
a(s,a) Σ
G( G( ( s/c N N
G(- To,
=
35

---

(s.a)
||[( M ( T (o...-))) (s,)))
n(8,0) a)
2m1
Σ B G(..VVv (ran Yo 1on..-1)) G(. (s.
n(s,a)
a)²
inf
G( 1 s'y, -(
n(saa)
El|G( 1V, 8t, Tome )) ElG as)
n(s,
(Vx(ri, - 2 -2. (CG To Gi a)))) }
n(saa)
B3 B ( d/ Tom..-))]1 (8, T"T 8m. (8,
a(s,a)
1=1
<
Cmaan
1
2
Cman, n(, n 0(88818)) a) > n.
Pmin
under No.
n(s,00 a)
Punin
2
Then, using [EX)= s (T(X2)31122 we have
m Te., (s, T T To... (5,a)} (s,
5 Vn
C1/2 mazzm
Pmin
Temporarily making notation simplification (ri, 8)), define
n(s,a)
(211 ....... ",, Zn(s,))) == m To., (s. n(s,a) a)
V where W == 11 (r,, 8/s Tam. .)-
Since we have following where W' = V for j # and V = (2/i To To,,--,, T),
(0 1 =n((,a))
06211.... 2 Zn(s,a))
1 ((x.a)
n(xaa)
m To (s) a).
V
m To. (s,
a)
V
a(s,a)
n(s, a)
1=1
a(s.a
n(x.a)
1 n(ssa))
G(-NV,)
G(INV))
G(- - G((
n(s,a)
n(s,a)
n(s, a)
1=1
1=1
Cmaamm
r2,5, a)
Then, by McDiarmid's inequality (e.g., Theorem 2.9.1 of [57
we obtain
p m(T.....(ss. a), To. 21
21.
< 2 exp
-42 ACmaz.
n(s,aj
-1 Puvin
< 2 exp
4C2 ma
Now considering the conditional probabilty for Ωo, we have
2
sup Yo., a), T a (8,a)} S 8,a
Vn V
1/2
man.m
+ t.
with probability larger than
Punin
exp( exp(
Pmin 2)
IS Al exp
exep
(-n Punin
-unin 2.t?
128
4C² mar.m
Letting t
402 mmuus.
log(
18x1| for arbitrary 80 E (0, 1), given that we have sufficiently large 80
n N-Paii
such that
exp( ) exp( -n
Pmin 2) < 6p.
1
(20)
4
128
2
36

---

we have following with probability larger than 1 50.
(T TT (o.,, (s, 2 max 13 of
4/8 Al
log
6,0
PPmin
80
Note that we have following under Sg that leads to p(s, s u)(
Σ p(s,a),
m (fn,1, 0x,e)
m² m²(To,, (s, Ts, Pmin
m (One,,
Puin
8,0
"i 0,,t) B. (m Bn.. (s, Tv., (s,
(T
- (Ton., a), Te.,, (s, = m (0 O2,z)
sup mi (To. (s.a), T=I TT (s, by 18
mox (0n,1, 0,,t) $
mu To, (s, a), T T On (3,0)}.
Pmin 8.0
Then, have following with probability larger than 1 8g.
( m. 13 of /1 -log
4|5 x A 50
) }
mao (0n,es 0..e) S
0V1
Pmin
Under Assumption 3.2 we have Tex (6n,e On,,) S Ceurr m (fn.t: 0,,,) + co. which allows to
N bound M/ ( aY T 6.. ) for all E [T]. Now letting T. we have following with probability
larger than T ōū, the inaccuracy so (T Tx) can be bounded by following based on (6)
{ max maax.Cmam 1} x
1
5
CRurY
Csurr
--
I-5
Pmii
(((N log 1
4/8 x Al (11Sx
8/2
}1
1
co 55 (To Tx) with <=> by
80
1-
under the premise that (20) holds with n N/T. This is possible since different subdatasets (Di...., Dr) are non-overlapping and independently collected.
N Now we choose T _ 1l-og/// (oo((1 ). which also leads to 5" RJ + -log( (og((1xx)) ( )) For sufficiently large N, 220 holds with n N/T and 5n replaced with / for sufficiently large
N. Note that have
4|8 A
1
N
)
{108 log
4 Al
log
logi/y
+ log
N/T
5T/T
2N
1og(4|S x Al/80)
5n
8
1
4|8 A
1
log1/y
N
log
+ log
logi/7 N)
2N
c
8n
c
Thus, with probability larger than - 6o. we have
1
11)
770 (Tor, Tx) S 1-
Osurr
mmax{Cmaz,nr
(21)
Pmin
o ( N logg/y N. log
1
5 A/S AA, + log -l.////77 No)
6/2
1
80
1 1-
-0-
C.7 Parameters Examples in Table
For all other examples except for the first two examples of Table the values of Coury and Cmann are the same with what we have derived in the proofs of corollaries of Appendix B For their values. refer to the proof of each corollary of its subsections (which are shown in Appendices C.10 C.16).
37

---

Here, we will only present the first two examples of Table ! whose values of Csurr and Caazm are different from those of Appendix[B
For m = l2, we need to assume that return distributions are 1-dimension and bounded, i.e.,
As, az E [a, bi for all a,a S x A and 0 6. By Lemma C.8 and & 212, we have Csurr
(b a) * and = 1/p.
2
W (P.Q) S 22. (2,,()
6 b- )
(P(.QQ) 12 2 (PQQ).
(b - ap-1
We also have Cmaz.m C. a)1/
For m = MM we need to assume D < 0o (where D > 0 is the diameter of support). Since the corresponding kernel can be considered as k(x.y) = || - -yll we have Cma = C D8/2 We have Ceury 1 and ô since m.
C.8 Theorem C.5 and its proof
Now we shall present and prove the non-simplified version of Theorem 3.4 For our analysis, we define the population objective function and the target parameter each iteration:
ER.S { (0 (TTo(s, VR T T 1)....)).
(0
Σ (s,a)E2,
(22)
where Z, = {(s, (s, }.}. Note that we have 0z,, arg minøge Fn, (010,,,))))))) Like Section 3.I] our objective functions should have connection with the surrogate metric m, although D may not necessarily be the squared form of m (i.e., d * m²). With m being a probability metric for P and extended metrics Mp.1, Mm,1, m. for M C -SSA (defined in (24). they should satisfy
following Assumption C.3 with [lzz(n) being conddiiito subgaussian norm (defined in (30 of Appendix C.10).
Assumption C.3 (Norm-space association). The functional Bregman divergence and probability metric m over P form a norm-space association (NS association, in short) if there exists an norm space (9. ll Ilm) where any element E P can be uniquely (up to equivalence under zero norm || ml represented by the corresponding element G(-Ip) E g such that
(NSI) The Zy-conditioned modulus (0,00,,,)))))
(01,,(000
Fn,e (00,(00),,)))))
(O..((0.. (O., 10nt-1)) is a mean-zero sub- gaussiasssnnnn process with respect to 1,,1. That is, for any Z, C S x A and d,,c-1 E O, we have
(A, A, (0 (00g))0,.- I Vn
Ceuby mn (0,, (01,
(NS2) We have (n.c(010n.t-) -0..(00..000.... X m',, (0, 0..e) for some / > 2. Here, the value of A > 0 does not depend on 2,, 0, 0n,e-1 (or 0.,t such that Yo.,, = T (...).)))
(NS3) Mn, (θ..r: f.,;) , O converges in rate that does not depend on 0_,--1 (and thereby O.,;) and the deterministic sequence Z,.
(NS4) Elements of Me C PSxA has a corresponding element Ge C gSxA where is a functional norm space with || |l such that [|G Gpz Il m[J1, H2). With the extended norm ml corresponding to moo (see (24) and some E (0, 2), it satisfies
sup sup (G([])sa)) < xo & logNN](GG, (lm,,,;)) Cbrack 9c8 2,8.0
(23)
It is possible that there exists an element in G that does not represent any μ E P.
Under coverage assumption (Assumption C.4 we can obtain Theorem with proof in the subsections of Appendix C.8
38

---

Assumption C.4. (Coverage) Ceover = s.ee marn T p/ (T)TT < co.
Theorem C.5. Suppose Assumptions 3.1 3.2
C.4 hhold Moreover, given probability metric that satisfies (S-L--C) with convexity parameter q 2 and scale-sensitivity parameter > 1/(2g) (i.e, (15) of Appendix C.4,, consider the FDE with a functional Bregman divergence satisfying Assumption with 8' min 1/g).
C.3 of Appendix C.8 Then, by letting T have
c- 1 8'
2((1-1)+0 -l0g1/7 NJ
24
-af 20-1)+a
T (Yor, Tx) S
1- -------- Co Cpp
Op
N
2² 2/ ED.
1081/7 N
1 1-
where Co > O a constant that contains the effect of the parameters Csurr. Ceaver, Obracko Csubg etc (defined in (27) of Appendix C.8 Note that need q > 1/(2c) to ensure 7- z (0,
C.8.1 Outline of proof
The first step (Appendix C.8.2) is to obtain the convergence of single iteration at 1-th step. Temporarily assuming that the state-action pairs 2, are given (i.e., fixed or conditioned), we obtain the convergence
with respect to the semi-metric 7,,1 24) that is based on 2,. Towards that end, we resort to standard
M-estimation theory (Theorem D.I) Unlike the tabular case (Theorem 3.3), the model complexity
plays a role in the convergence rate. Then, we can obtain the same convergence rate in (sample-free
metric) 1, based on the fact that the probability metric m has a corresponding functional norm space (see Theorem 2.3 of 34
The second step (Appendix C.8.3) is to combine the convergences of multiple iterations into the final bound for the T-th iteration, just like we did in Theorem 3.3 (Appendix (.6). So, shares many similar ideas. However, unlike the previous Theorem 3.3 this requires us to handle the coverage. The inaccuracy metric .g..9 is constructed based on d. whereas the collected state-action pairs are generated by We need to take into account the misalignment between the two underlying distributions, quantified by Coover (Assumption C.4).
C.8.2 Convergence in single step
Lemma C.6. Assume that our objective functions 10 and 22 and satisfy Assumption Conditioning any given value of On,t-1 (previous ileration value), under Assumptions 3.1 have
C.3
C.4
Oabber (Crobe C 2C/2
v2
-14072
( T (m,-,))
-Op 2リー1
1 aa/2
The proof of Lemma C.6 is as follows. Let Dr: ((86, Ti, ()))
With the norm representation of the surrogate metric m, i.e., m(ui, H2) == (( - (m1lm. then we can build its extension as follows:
empirical norm 1m,1 I|Go, Go, 1m, (1 n
Σ |GGo, az) - Go, a:))la
1/2
expectation norm : (0,1(01,03) = |Go, - -Gozlmap
E Es (-|s,a) -Ga, (-1s, a)
supremum norm
(01,0)
|.Go, Goz Il == sup ||o (+18, - Go (-11, (1.1s,a)lle a)lma
(24)
Define e == {0 θ obtain
mn (0, 0,.e) S 6}. By (NSI), we can apply Theorem 8.1.3 of [57 to
R sup (010 5 Vn" BEER
C.
-.suby 1:a
Vlog.N mn,1,
C Ceuba 1- Viog.rIoh mn.1, e)de 5
C
Couub /-"
e)de.
Vn
Vn
39

---

Let Chound == supaee s. Go((]s, a)l E (0, oo). Here, we let G-1 ...) == 1 and 9/ GG Gef. Note that we have G)(z]s,a) I 1 and
G-( ...)
Chound
log 1og llm, E) = log 1og Ilm Chound E) S Cbrack Corund E
(25)
Let Letm Obound 1m,,1 m/1,1 Chound mp,,,m'. == Oround -ma, and we have m/,, (8,, 02)
||G,, Gbg mmm (0,, 02) = GC,, G.yllmmp (0, =- 1|C², Gby lm
This leads to
log.V mo,, <) S log NO, m c/ e/Cbound) S log N Il llm.0 c/ Chbound)
< log. No S 1lm 26/ Obound) Obrack Obound' (
2t
-a
S Cbrack
2
Chound
E
sup REAA
An (010m00 0m.0-111 S
C Vn
-Cuuh C
V2
1
82-
1
xx/2
We have consistency M.n1 (0m.ss 02,5) +P by (NS3).
Then, we can apply Theorem
D. to obtain
V2
Mn.1 (0,)) S Csubg C.
-Op (n (1-1)11
1 xx/2
Using 2+a 2 21-1++0 due to / 2 2, we can apply logic of Theorem 6.3.2 of [54] (or equivalently,
Theorem 2.3 of (34), based (2 a) I and 25 This gives the same asymptotic bound
for mp,1 (Qn,e, O), and further applying Assumption C.4 gives us Lemma C.6
C.8.3 Convergence through multiple steps
Now let us bound (N..q(On.t (2,1) with q 2 1, with Assumption 3.2 (a29 + 122) to obtain the following with o' let qō:
We use (a + 6)29 s 229-1.
Md (0,. O2.z) = (1 B.., (0, a), T B (8, ()))))))
< TF. 220-1. { C2g 2
(M on (8, m
(s, + +
x + 2 3/4 co < 2 - 2/4 Csurr (E(m200(T Bn, (s) T To On (s, (n,
2C [Bim2d Cr (s, T o (), + 2 :/- cc.
Assume bounded random variable X such that X S Cmaztm Since I//Cnazim 1, we have the following if 1 S P1 S P2.
X
X
Pl
Pz
P1
PI
P2
E
E
IE
Cmmaam
Cmazim
Cmaaim (E) ( gmiva
[
1/p2
2l
maxim
If we have < g', letting pl = 2,p2 2g' gives us
$ (E(m²(T (T. (s, T Ina (s,a)))+)
Tir. (on,,(0n, s 20 surr
mazim
+ 2 24 -0
( 01 2 m
2C eurr
m 1 (0n,t; 02.s) + 22- 112 -60-
If we have o' S 1, then we have nd, o (in,e O2.) S 2Cturr mi.. (Ōn,c- 00.,) +22 to .eo by Jensen's
inequality (even for of < 1). Thus, we have following with 8' min 1/9).
n 0,,)) S 20eur m 166.0
m md (Ōn,e. 0,,,) + 2-2-22 1/4 60
(26)
40

---

Restoring the iteration index E [T'] (i.e., B2 -n,e), we have following by 66
(d Tx) T Td, (To, To, To,,) 5F -d (Yoos Tr)
T -x- ( (To,; 1) 1-70-3
surr
maxtll- #1000)
2 20
+ + - ao T)
Recall that the data (which are independently collected) are split into non-overlapping subdatasets DD= = Ui=, Dr (see Section 3). This ensures that 0n,r-1 can be considered as given constant at each
(-th iteration.
Lemma C.7. With X,,t = 10-0p(n for some >> 0 which can be possibly dependent for different & E N. assuming lim - SuPtEN E E/ncl < co, then we have Σ C. 1.0p(rt n 1/b). See Appendix D.2 for proof.
Xn,t
In our case, letting Xn,t
m dr, (T
B....' T" (....
(where n affects On,
arg mingee (0,r(010m..-1)) we show that the condition of Lemma C.7 can be satisfied. We will defer the proof to Appendix C.8.4 for the sake of simplicity. Then, combining with Lemma C.6 and letting N/T with
logi/7 Nj. we have
11-1)+a
Co .p.0pp
N
21-1)++
ad (T " rx) S
x 2y
logi/y
24
2
27
60.
where
Co == Csurr Ouarim
((1
2e 18,00
Cenver X
(27)
V2-
8'
1-44079
Osubg C2/2
1 1--0/ a/2
2(1 - 1) +
with Cmazim =
ae mac ()))) For Cmazim = 0o, we let Co
mazimn
1. This validates
Theorem
C.8.4 Satisfaction of the condition Lemma C.7
Theorem
Stage-1: Apply peeling argument
Arbitrarily choose integer M N and sequence (6,)
can use the logic of standard proof convergence in M-estimation (e.g., Section 5.1 of (5T). Define
Z, = {(s a.) (s,, ag, rı, st) E Dr} and Sn, (0 θ 2/22-1 8n mm, 0..)) 2 8n and we can obtain the following.
Mm,1 (On,,, 0,,)) 21 6n (2,2)=- - 20-1 5n < mm, ( 0,,1) 2 8, Ze
32M
IP
sup
{ (0, F., (0, 20 Ze
{
BESm..
J2M
1n (000m,,.-1)) 2 2')-1(1-1) .0% (.)
<
P
sup
by (NS2)
12
$
2 ( 81
E
sup
An (1 Zz
J2M
(8. (..00...5500 5211-66
41

---

C
Csubg 2-1
brack
V2 a
1
6g
81-0/2-1.
(20)1-a/2-1
by (NS4)
1- a12
Vn
J2M
C
Osuby
Cback
V2 V2a
1
(2 8n) 2-/2-212-1
1- a/2
a/2-1
Vn
Cc
= C2 Vn
(2M 8n)
10/2-0/2-11
For arbitrary > 0, choose M N and 8, 0 be such that 2 on Then, have
P(mn,1 (On,t 0,,) Z C2 Vn cl-a/2-1
Now letting 1-a/2-11 v é for arbitrary O, we have following with = 2(1-11 + a and C2 > O not depending on d (and thereby (x,z),
1/0 mn, (6n,t: 02,t) > 2 2z) S2 b/b/2
Based on the above tail probability, we can bound the expectation as follows,
B 1b. mn,1 (On,e Onst) 21 % P
E
Pnnlib n//b
1n, (On,t, 0a,t) 2 21 dt
=1+ /
1/b 12/10. Mn,1 mm,
C2
Oag) 2 l Zz dl 51+
(28)
b/2 -
Note that the bound does not depend on Z,
Stage-2: Convert the m, into pp -boud First fix (0, 1). Based on Lemma 6.3.4 of [54], we have Les ag (that do not depend on dn,--1) such that following holds
Go, Gozllm. - 1
1 se 2 1-
1 ex-eepx( L3 xT=²))
sup |Goo Gay Ilm 1//
|Gog, 02llm.n
ae
Denoting the event Pgg and note that this only regards to the observation of 2, and not the rs 8 p(... 18s, 0:). Then, we have
E Ammp, 0,.1) E mp, (on,e, Bn,e) (100011111111 (mp.1 O.,c) I Le dec.n-1 n-1/6)3
BR m Oa.)) 1 ( (0,)) Lic n -2/0
$ L. 1/6b b E
mpp 0,,e)
Oa,)) > Iee dennn n n-1/b) 52 -P((2E)
E mp (0n,e, 0..z) 1 mm.1 (On.t (r.)))0..)) > Lo n 11/6) 22 } -P(()))
< TTe 11/b E
1
mn, (0 Omtt) s2 Cmazim exp(-aee 1 n :²2)
1-c
La I-c
1
[1
b/2-1)
C2
+ +
1166
b/2
The last line holds due to (88) since 2g only regards to Z. Also, C3 > 0 is some large value such that Cmazim exp(-ac
L3 25² < C33 n -1/b holds for sufficiently large
42

---

Stage-3: Showing the satisfaction
We can further derive the following.
E (mmaa (n,e) S
C
LE m (6n.e 0r,))
cover
E Em 0un)) 6'
S cover
by Jensen's inequality (:: 8 S 1)
2 C4 66/6
for some constant C4 > that does not depend on n or Then, the condition of Lemma C.7 satisfied with degree 2(1-1)+a
C.9 About IPS metries
C.9.1 How squared IPS metric becomes functional Bregman divergence
Assume an IPS metric (Definition C.2 where G(-IP) can be defined for dirac delta P = 6x. This accommodates (i) P) being edi with (t, and (ii) G(-IP) being kernel mean embedding with (x. See Appendix C.5 for their detailed explanation. Define the score S(P.x) == - ||G((-
G(-16x) where &x denotes dirac delta at x. Then we have
S(P,x)
- ((C()P)-G(((6x)11)))
-Rx-O ( 1[G(1162)) 2. (G(IP), (.11))))m
-IG(-1P)) + +
G(11))
Since we have f S(Q, x)Q(() -I) + Ex-o |G[ 6x)) this leads to a valid func- tional Bregman divergence as follows (based equivalence stated before (5).
- - G(-1Q) -((II)))
s(Q.x)d((x)
s(P.x)
Of course, there being pdf with ) However, this case is shown to make a functional Bregman divergence
where G(-IP) does not exist for dirac delta's, most representatively G(-IP)
(Section 4.1 of (23
C.9.2 How IPS Properties imply NS Properties
Under (IPSI), (IPS2) of Definition C.2 and (T], we shall show (0, m) with m² satisfies NS Properties of Section 3.2 with ( 2, X and Csubg Cmanmm-
(NS1) can be shown as follows. With A = m² (To(s,, a,), W (R,, S Y (,,,,))) where (r, s', T) == (9 T('s, (')
(due to convexity of P. provided that P
isfies the assumption of Theorem 2.4)
:. (0, - (02 (0))
Σ - -
1 Σ1Ae -B(A-)}
1=1
Since we have ( (0.,.1)) An (02 (1) SC. + Ei A1 AA 11 by Propo-
sition 2.6.1 and Lemma 2.6.8 [57]. we shall bound 1A - -.
14 m² Te, (si, a.), as), V (r,, (r..,),, s/ To Tom, m 3 (st,
(8t, az), v (T S/ I Iom.-1)
< C Cmann. mY (s,, a;), Yo, (8;, a;)).
Here, Cmaz.m > 0 is constant (that depends on the corresponding kernel k) such that
m(To(s a), V (r, s Y Ton 10....)) < Cmaa,m
sup sup sup T.x'
0,0m.t1E00
Iet C. supp /2, v)
For m = MMD bounded kernel k(.,),, we can let Cman.
(29)
a.ve
43

---

Thus we have
Csuby vn
(A,(0110n, (n((0100nt- _ Min (0), with Csubg = C C Cmar,
(NS2) can be shown as follows,
Fo. -
"
I m² ammmmnrn (T)());a)) (R,, Si Ton. (aa)))) m2 (To.,, a:), (R,,,,, St Ton, .
n
The terms within the curly bracket can be rewritten as follows with temporarily letting V Vr Vr(R,, S% T
|[G(I)a((s, az)) - G(- [| a))) (st, - -2 (G(-) a.)) G(-ITe,, (st, G(-IV ())
(s))
Taking its expectation so that ((GG(IV)) G(-IT (s;, a:)) have A = 1 as follows,
12
(0 --1 1) Fr. 1n
[Gi, (: a:)) Σ ( ai))
2
a:l), G(- (
(si, a;)))
a:)) G(- 1
= m (0, 0..).
(NS3) can be shown follows. Let us define the following.
1
F", F0,,(010m,t-1)== =
||G[ To(s,)()
n
- D,,,, (s))),))) }.
1 Fr. (0,,(000m,-1):==
(o(s;,
- 2. 2. (2.(T((TT(ss GG-- s T Ton. 11
(o,, we can see Fn, 0n, (n.((0..(0n,.t11) = (0,c(0) P (0. Likewise, we have (0,0(
Based on our derivations for Fa, Fn,,(1(mn,ti))
Fn.e(0,,e) (0,,c(mn,t1)) ( (0)0,,,11) - Fr (0,, (0,,0,,,0mm.1 (m,t-1). Then, we have the following based on
derivations for (NS2),
m (B On,e)))))))- F", (b,, 10 10,,t-1) - Fr, (n,t-1)
Fr Fh, (0n. (0.,00..111 Fr1 (0 (0m,e(0 (0,,00,..)))) + Frr (m.e(0me100n.--) (0,, (0,,c(0mt-1))
< sup
F (0 - (010m +1 (0..
F² (0, (n.t-1))
(f),, (0 (0 (0)
(.,,,(0,) (0,,e0m..t (0 Fy. (0,, -Fmnt01,,00nn---1]]
sup #E0
+
Frr
F (O,, (0,,,)00,,1)))
A, (010 + (0 - Fr, 10m,,-1),
sup
44

---

Using subgaussianity that we have shown for (NS1), since subgaussian constant does not depend on f, we can apply Theorem 8.1.6 of [57] (probabilistic tail for Dudley's inequality) to obtain probabiliiticc convergence of the term supgee
A (010m,e-))), Regarding the second term, we have
|F (1),(00,))),,..-))) (0.,(00,000
(s. G(-ITa,, (s;,,:)))
a:l)) m
m
- GB. G(-dal)))GGG./llleeo G(-IV=(RR Sy To )
Letting X; (G(-ITe e.,, (s,, a:),, GI- (s; ()))) we have Xx,| S C Caaz. by Cauchy- Schwartz inequality. Then, we can apply Hoeffiding's 's inequality for bounded random variables (e.g., Theorem 2.2.6 of [57]) to obtain probabilistic bound that does not depend on 0n,1-1-
(NS4) is straightforward. However, the two statements of 23 need to be assumed.
C.10 Proof for Corollary B.1
For the case of (0, m. 11) = (12, 1,, Wp). we have g p. 1.
1= 2, 1, Csuby C p
Caurr D' Go
Based on the fact that 12 = 2 is equivalent to let MMD 8=1"
7 for d = 1, where energy distance E MMD with 3 = 1,
Let us first verify (NS1). We obtain the following for Fr,, (1)0 Temporarily ignoring o,,
since we have (01) - A,, = (0,,,(0,10n.) (9)
Fn, 01 (n10,,-1)]- - (Fn.e(2))m,.1))))
let (f) = (o..(010mn.11)) (f) (((()(0n.e)) We will ignore the notation -n.e-1 for the sake of convenience.
( 2 A (1) + (2), where
(0) = f -E(()) } ( =
9 E(os) }
where / = 2 (s; a;; 0) -ry Zs(5 13; f,
| and of = E Za ag; 0) ( a;; f)]l with A ~ (-15)). Let us only deal with the first term, since the second term can be handled via analogous approach. Letting of = 1 E(J.), we have A (1) (0) Σ Tz.
In order to derive its probabilistic bound, we shall bound the following term.
1 1 x 222 (2)(())
(0,) - (02)1 (2())) n
where
(30)
(Xllez())== inf { t {t>0) 0; F. exp exx(exxx2 (12
X (1))())
sup | x) x|]]]||*|=
(2)(())
where the inequality holds by Proposition 2.6.1 of [57]. In defining
|| [l))(()) X and mean random
variable (d = 1) and vector (d 1). Further using the fact that (1)) is valid norm, we can derive the following where E,, := E(... (2t),
| xx (w22()) S 111 ffth
+ EE 1l2
- (
2 a
:: ||4 A (1)11
S Σ 11 11 (p))(() + E. (11
fsr 12 (m)
n
where the last inequality is based on Proposition 2.6.1 of (57. Based on technique suggested in Appendix A.6 of (26), we can derive pol - ffal S W (To, (1), (s1,0))) 3))). which leads to following based Example 2.5.8 of [57].
C n²
as), WT (T, as), To, ax)) = C.
| R (e:) (02)
Σ
(81. (B..0()..))))
45

---

Applying the same logic to A (0), we obtain Csubg = C. It is trivial to show A,, (0) is mean-zero. (NS2) can be shown follows
F Fn,1(0(0m,ti))) Fn..(0.,.00...111 1
(To(s; T" (5..)
1=1
Here, & is energy disance defined ((PQQ) 2 YI BIJx X E|y
Y'I for
X, X id Q and Y, ~ P. Using the following lemma (proof in Appendix D.3. desired result with À = 2/ a).
we obtain the
Lemma C.8. Assume 1 S p S r, and let P, be probability measures for arbitrary random vectors of d 1. We have
E(P,Q) S2 22.,(()))))) S (.P..Q).
P, E Plu, b), we have
2 (b a 2r
W (P,(P,
<
W (P())))
(b a 2p-1
(NS3) can be shown by following. 0n equivalent Ōn arg minsee Fr. F (0,0,,,),,.))) where Fx (010 is defined as follows (instead of what we defined in Appendix C.9.2).
2
Z (st, a;; Rs 7 LS A/; Pn 1)ll 1
(s,, Zo(st, a;; 0)],
n
with RG, S ~ ((....s;,.a)) Then we have following with the same logic shown in Appendix C.9.2
W. (0.n.(0m.e: O21)) S F (6 10 - (0,10,,,00,..
A. (0 (010m,t-)) 1) + Fr (00((0.,(00n.t-1) F² F%, 100000,,100m---))
sup 8Ee
Just as Appendix C.9.2 we can show A,, nf|0n,t-1) , by applying Dudley's inequality (Theo- rem 1.6.6 of (57)) and show (0., 1-1) n (0,, 10...1)))1 , with Hoeffding's inequality for bounded random variables (Theorem 2.2.6 of (57).
Now let us show (NS4). Every μ E A[a b)) has a corresponding function function F E F, where F represents the edf family. We let Fe == (Fo(..... FS Fols, a) is the edf of To a)), and we have Fo(-)-- -.))))))))))) ) & 1. Based on W1(H1. = F1 - Felle, with functional norm || Il. =
(
we can define extended norms 24 with || I| = 11.
w//p, where D indicates the diameter of the support of return distribution (D b- in I-dimensional case). This leads to Csurr = (b - a) aa1 11p
Lastly, by Section 2.3 of 44 we have Wp < D
and 1/p. Then, by applying Theorem C.5
we obtain the following bound for wp.d. (Tor, Tx),
(b
1-
Coover
11/2 brack
V2
1/p
1/2 1-0/2
20
Zp
a/2
22+ a
N
2+0
x0p
logi/y N
C.11 Proof of Corollary B.2
For the case of (0, m))) = (MMD3, MMDs, MMD+), we have = 1, 5 = 1, 1 = 2,
2. Coubg C (Fmax + ²max) 8/2 let (3) with supace sup,,e [| a; 0) =mmax and
sup,,a / [[(s,) a) S Tmaxx Courr 1, E0 O. We need 3 > 1 for g 1 as we mentioned in (16).
46

---

Any pair of (0. m)) = (MMD", MMD) satisfies NS Properties ((NSI)-(NS4) for bounded ker- nels (see Appendix [.9.2). Then, we can apply Theorem C.5 MMD 3, 1 (Tor: 0r: T.)
to obtain the following bound for
Coover
2
v2
I1673
Chrack max
8-1
3
a/2
2
xOp
N
Z+a
1og1/7 N
we want to obtain the result for 3 = 1, we let c 1/2, 9 = 1 + EN for some monotonically
decreasing sequence CN 0 as N + oc, and ((==) C (rmax + //2 Applying this to Theorem C.5
we obtain
MMD 1, (fer Ia) S MMD 1, (Ter, Tx)
C
ITeN mazim
Clover
clbea")
C1/22 V2
1/(1++EN)
1/2
1/01 [ollenl
14a/2
X
1-o4 ax/2
2 + a
constant part
-1/(+()) 2+a
24a LieN
Opf
N
log1/7 N
2 [++xx]
convergent part
Letting yn = [[1+e)
CN
+ 0, we have
1/UN
1/2 -0) 1/(1
1 1 7
lim
lim
lim
log(1/7).
(31)
1/(1 yux)
Therefore, the convergent part can be bounded by constant multiplied by following for sufficiently large N,
1
1424a IteN
oof login7 N
N
24 ItEN
1og(1/7)
U/
(log N)
1- TenN
(log N) TteN
1
-0p (N= TT(N
log(1/7)
log(1/7)
1
1+ 340
(log N) z4o Op { log N
log(1/7)
N
1
1+
Op (log N) 1 rio
1
-N sta
(og(1/>)
where the second last line holds by following.
N
log and only
log N log N log(log N)
1/ log
if and only if
log(log N)
(32)
1 1+ 1/ log N
Then, we finally have
MMD 1.d, (Yor, Tx) S Covver
c(é=1)
Crrack
V2-
1
1/2
14072
1 a/2
(2+
Op
(loggN))
N 2+o
log(1/7)
47

---

C.12 Proof for Corollary B.4
For the case of m)) (d2 d22, Wp). we have q p
2
( 2, 1.
1d42rlp'
(d=2nic
(Va, 13) M, ( 6D = 0. Here, we Osuby = C. +1+ 7 Cig Csuer = 2 (max V2, have Ct2 == sup,,a supsee | [o(ss, a)llza M, == supsee sup,,a [1 a: 1) < 00 and Va is the volume of a unit ball in Rd.
+1++3
Due Appendix C.9.2 it suffices show (IPSI) and (IPS2) of Definition and IPS properties are trivial to show.
have 11//" supaee sups,a 11,o(-18, 8, a) l) Thus we have Cmaz.m = C (1+7 4/2).C1,. We can see CL2 < oo by following, by letting L == supoee supz,s,a Ifo a)l <
11I be shown follows. Letting f(+ss,t) Saca (d)
f ((. - -)///s//''ss// >))l>'" = 1///0/2
1
- -/re ( [[olelssaa
2 dz S
fo(z]s,a) T.
1 T.¹ : Cr2 111
Lastly, by Proposition 13 of (56), we have following under S p T
(d+2p)r MM
zir-p rdt2a
W Wp(n, (2) (max (V, 1))
{dz, (11 (12)
with Ex-Ei {IX |Xp,, 1 Ex-pa [|X 1/v S M and Va being the volume of d-dimensional unit
ball. Thus, we have d
2(r-p) with (d+2r)p
Cuurr 2 (max Va, 1)) 4
M, (1:201p
Applying Theorem C.5 gives us the following bound for W
p. p (Tors Tx),
max Vi, 13) 2
M
ta 22
2d+2
Tmp ta 2010
of CL2 Crack
1
1/2
I
1
29
2p
V2
2(r p) (d + 2r)p (2 ax)
1/2
Zir-p) 140/2 (at2r)p
Op
N
2(m-p) 240 (c+3r)p
1- aa/22"
logi/7 N
C.13 Proof of Corollary B.5
C.3 are satisfied by Appendix C.9.2 since hi is bounded. For the case of (d, m, m) = (MMD MMD,, Wp,, we have = p. = 2, 1, (a(k) let c-(e) Here, we have C(e) < 0o since k, is a bounded function with a fixed value of Mat > 0. Assuming that [] a))l==to/2((=)) < B and M, < co, Theorem 15 and Example 4 of (56) gives us Csurr = C(B, My, d. p, Mat), en = 0, 8 = r-p in Assumption
NS Properties (NS4))(NS4) of Assumption
Cruby
(d+2r)p
3.2
See the detailed form of C(B,r, Mr, 8, d, p, Mat)) > in their Theorem 15. Then, applying p.d. so (Mor) rz).
Theorem C.5 gives us following bound for W
C(B, r, Mr, S, d. Marr)
2
clu) maz
V2
u73 2ar
brack
7
1- c/2
x
N 1og1/7 N
24a
[d422)p
C.14 Proofs based on Gaussian regularizer
Here, we introduce a method by which we can bound W Wp.a, pp.d,p-inaceee .ain.cccnaccraccy based on regularizer (.(+)) (see Definition 20 of (56]). In the following lemma, we use gaussian regularizer ag due to its convenience, however it can be extended to other regularizers (see their Lemma 21). Since our surrogate metric may depend on the value of o O, we will denote it Ma.
48

---

Lemma C.9. Let (-)-) be the density (or probability measure) of o2 and * indicate convolution, Assuming Wp(u og V 0a) S ((a.p). . my (u, v) with p E (0, and my satisfies (NS4), letting d my achieves the following bound (with detailed bound in (3
C(o,p) 0rp .
2
r((p + d)/2) a. T(p/2)
W Wp,d, n (Trr T 1-
1og1/7 N
irreducible for fixed a '>0
C.14.1 Proof for Lemma
C.9
By Lemma 21 of [56] we have the following,
W V)(,,v)= S W( uxx + (ʃ (IlelPaa
1/2
I((p+ + +d/2)
- ao xx 2
r(p/2)
sO(o,p) m d. (1, + 23/2 [((p + d)/2)
T(p/2)
Then, we can apply Assumption 3.2 with Csurr = C(o,p) p). and eg = 23/2 r((p+d/2)
a. Further
T(p/2)
letting m Ma. I = 2, q = p. = I, we can apply Theorem C.5 to obtain the following,
W p.da.p (Tor: xx)) S 72-
C(a, p) Crouer (Ceuby Crrakk
v2
17772
1 1- a/2
-af 24a
N
1 2 $
T((p+ d)/2)
(33)
1og1/7 N
1
T(p/2)
C.14.2 Proof for Corollary B.6
The case (o, (0,m,)) 17) (MMD? 2
TRAP MMD DRBF wp) satisfies Property (NS4), having d 2(r-p) (242r)p
(0, H) C(ORMF,P) p)) = C(p, d, r, M,) (see Theorem 24 of (56) for its detailed form). We also have Csuby (k)
23/4 -RBF d/2 by 29 and Cbrack = Cbrack (FRBF) whose dependence on ØBBF > 0 not clear. Further letting ØRBF = ON + to a monotonically decreasing sequence, applying Lemma C.9 gives
C
Zir-p)
p.d. p. ( Tr: Tx) C(p,d,oN,))
Corack(ON))
v2
140/2
(44arpp
7 2
2d/2
d/2 8//1
oo
1
a/2
2(r-p) 2Ta
or{ 1ogi/> N
(d
T(pp + dd/2)
2
T(p/2)
ON.
2p
C.14.3 Proof for Corollary B.7
The case (D.m,)) m, 1) = (MMD (a,f)) MMD (a.): Wp) satisfies (NS4), having = 1,, C(a, p) = - o by Theorem 2 of (70). which can be applied since the kernel k(a.f) is bounded. We also have Csuby = (k)
cla.f) , which is bounded due to (ta)) < co by 29). along with Obrack = Obrack (a) whose dependence on > 0 is not clear. Further letting o = oo + 0 to monotonically decreasing sequence, applying Lemma C.9 gives us
W Wp.d..p (Yor, Tx) =
ON
Cdlver
(claxe co
V2 a
1#077
1/p
1
1 1 2a22
2p
-1/0
Orl 1og1/y
N
2
[(pp + d)/2)
+ 1
T(p/2) ON-
N
x 1-
Note that for fixed o > 0, we have (f.
< oo as long as (.a,)()))) oo holds.
49

---

C.15 Alternative for violation of (NS4)
In Theorem C.5 (NS4) may not hold. There may not be a corresponding functional norm space (e.g., Wasserstein for d 2 2) or the functional element may be unbounded, that is, supace sup, 2,5,a Gø(z|s, a) oc. For such examples, we should replace (NS3) and (NS4) of Section 3.2 with the following (MS3) and (MS4). We can maintain (NS1) and (NS2) from NS properties, renaming them (MS1) and (MS2).
Assumption C.10 (Metric-space association). The functional Bregman divergence and probability metric m over P form metric- spaci association (MS association, in short) if there exists metric space (G. m) where any element/ μ E P can be uniquely (up to equivalence under zero metric m) represented by the corresponding element G(-In) E 9 such that
(MSI) The Zi-conditioned modulus 6n,00mm,e1) = (Fn..(10nn,.))) - Fn,((000n. (0..((0...0...-1)
(0..(00,,00,,.-- is mean-zero sub- gaussian process with respect to mn,1. That is, for any 2, C S x A and 0 E O, we have
| (0,100.0, - A, (02 (02 Mles(n) S Vn
Centi Mm,, (01, 02).
(MS2) We have F (n, (n.1)) - F (0,,)000.11))))))))) X m',, (0, 0,,e) for some 1 2 2. Here, the value of A > 0 does not depend on Z,, O, On (or O., such that Yo... T 1
(MS3) Mp,, (0n,e, 0m -" O converges in a rate that does not depend on dn,t-1 (or 0,,
(MS4) There exists a constant Cmet E (0, oo) and a E (0,2) such that
diam(O, m-z) < oc & log.V(O, ma <) S Cuuet c
It is possible that there exists an element in G that does not represent any μ E P.
Under these alternative conditions, we can obtain the following theorem, which is proved in Appendix
C.15I
Theorem C.11. Suppose Assumptions 3.7 3.2 C.4 and C3 < oo for Lemma C.12 Moreover given
probability metric that satisfies (S-L-C) with convexity parameter q Z I and scale-sensitivity parameter e > 1/(2q) (i.e., (15) of Appendix C.4), consider the FDE with a functional Bregman
divergence satisfying Assumption C.10 of Appendix C.15
Then, by letting T = - 23
8
10g1/7 NJ with 8' = min(8, 1/4), we have
1
Co or
(log 2)2
201
2 cg
(Tori Ix) N
[1og(1/))
1 1-70-3 c-
N
of
Co:= == Csurr maxx(1 16,00
Covver CBB & B1 max
1 +
where CB is specified in
35 Note that need q 1/(2)) to ensure 7 E (0,
The outline of the proof is very similar to that of Theorem C.5 which is shown in Appendix C.8.1
We first derive the convergence of single iteration, and then later combine multiple convergences altogether. However, the important difference is that cannot employ the same technique that ensures the same convergence rate for M.., and 1p I. since it can violate (23) that is required by Theorem C That is, the functional representation may not be bounded or there may not be
corresponding functional norm space. Therefore, we resort to an alternative theoretical tool (Lemma C.12 with its proof in Appendix (D4) that can possibly lead to slower convergence rate.
Lemma C.12. Assume Assumption 3.7 and C3 > O defined below has finite value. For any |3 we have some sequence 8, = max 5()) (22) such that 8n + 0 as n + oc and following Φ(-) mentioned in Theorem D.1 Here, ((1)) and o are defined as follows:
(2C
1/3
C
-n.82 88
8(1)
& 8 2 ((2) implies
Ceuby Cent 8 2 2C3 exp
Vni
vn
4C3
((8)= == C. 8 2 with Co = C Csubg Cent
& 8'= min 2}.
50

---

Here are the constants:
Cent = C (1 - 02/2) & og =1 (0,1),
C Cihe diiam(;; m & C2 C. Cd==idiam@@mmal
Ci a/2
C3 > is the finite constant that uniformly bounds the modulus An (n(00,, with F(0(0n.-1)= R.s.p,..S'
A), V (R, T (_n,_1)))
(0 -- = (P (000. 11, F(O F(0(0n..-1)
C =
sup
sup
(0 p0)) 00.
0.0m.-1E00 sar,is
C.15.1 Proof for Theorem C.11
In (MS2), take expectation on both sides. Then, the LHS becomes F(0)0,,.-1) - F(O.., (n. where the unconditioned (not conditioned on 2, unlike (22 objective function is defined as follows:
F(0(Ūn,t-1) = OfTTo(S, A), (R, T (b....))
& 0 = arg min F(0)0n,-1).
DE0
For the RHS, we have following,
E (0,,,1(0,0..)) (0,),,)) = E (0, 1/2 2 1
(0,0
(0, (0))) 1/22 by Jensen's inequality = 2 (0, 0.,)) (0,000....)) 0.,.).
1/2
= E
m² (To(Ts ax), To., (s (s), 0z))
Thus we have F(B(@n, - F(0., F(8,,100m1) 2 A m (0,0. ,),,, by which we can replace (MS2).
Now, we shall combine this with (MS3) and Lemma C.12 to apply Theorem D.I We should find 8, and B > 0 that satisfies following with 8 min (3,2).
Co 6.
S Svn.& 6n 8n 2
2C
1/8
Vn.
Csuby Cent 6,
3
3 2 C3
exp
-n-622 -22
-n
4C2
(34)
The first condition of 33 can be rewritten follows,
C
6, 2
requires to confirm 0n < 21.
Remember that B> > 0 is free variable that we choose. There can be two cases: (i) + de and (ii) / >> 2 + og. We will select 33 differently for each case (based on the first two conditions of (34)). and we will hereafter denote selected value as B0-
Let consider the first case. To meet the first two conditions, we solve on.39 /22 Temporarily asuming 3 < 2 (which also needs to be confirmed later), we obtain 80 = 1/(1 (1 + 00 /2)
We can confirm that < 2 + ag implies Bo I 2, and can see ag,3' ag 21.
In the second case, we let 8o This leads to B' 2, and the first conditions of 34 can be summarized as follows,
Co
Log
22C
1/2
I-og
8n,
2
& 6n 2 Vn
nn
We confirm that 3' 200
2(1 - 2) < 27 holds. Incorporating Cases (i) and (ii), let
1
80 min
1 aa/a" 2 < 2.
51

---

With the selected Sus the first two conditions of (34
become following.
1/30
Case (i) 000 : 8n 2 max {Co, 201 1/8.
with 30 = + oxo
Co
Case (ii) 2 00 : 6n 2
for sufficiently large n E N.
Since / < 2 + or is equivalent to ( S
we have
1+00/2 2
1/
1/31
1
6, 2 max 2C1] vn
with
max
1 + 00022"
00
Now we select 8n follows,
5n = (max Co. 201 2CC,
1) 1/8:
(v
log n
1/8:
n
C'
and confirm that third statement of 34 holds follows. Note that the selected value of is Bo, not $1. Using some constant CLHS
and Bo I along with C2 4C2, have
CLHS
agdia
CLHS Vn
log n
LHS
On
2 CLHS (log m))n)///44
Vn
Vn
8288
C2
log
80/8
RHS-
C3 exp
C3
exp
402
402
71
C33
< Cg exp(-llogg log
Since og (0. 1) specified in Lemma C.12 large n. satisfying the third statement of (34).
that LHS is larger than RHS for sufficiently
Now we can apply peeling argument (Theorem D.I to obtain the following,
mp.1 02,1) = Op(6n) Ci-ito CA Op
log n
1/02
log
2d
Mi,, (On,t, 0n,e) = C1/2 max (2C,)
(2C2) 8:10
Op
We can copy the logic of Appendix C.8.3 that we used to prove Theorem C.5 (with satisfaction of its condition deferred in Appendix D.5). We can let
We can apply Lemma
C.7
6'18
8' = min(6, & )
& C == max 20,
20,, (2C2)
and further let
8'
T =
I
28,
log1/
1/
N
N
R CT.
2q
Ignoring the flooring effect, this leads to
log
log( (N/T)
T
1
8'
(log N>²
log N
n N/T
N
23
log(1/7)
N
24
52

---

Then, applying the same logic as Appendix C.8.3 obtain bound nar.. (Tor- Tx) by following.
(extending towards multiple iterations), we finally
Csurr max
CB o0 1og(1/7)
(0((10(177) (log 2
maxim
Cover
70
N
b4 E0:
with 31 max
+
& 9o min
2
7
70
and C := max
Co. 201, 2CC2 81/80
8/0
1
8'
2P1
(35)
1
2,1
where Cg. C1, C2 are defined in Lemma C.12
C.15.2 Proof for Corollary B.8
For the case of (d, m, 77) (MMD 2 cou
MMD cou: Wp). we have = P, - 2, = let cleo)) Csurr = C C.D.
Csuhg
e a)) (kk) C(1 + > supage sup, s,o
V²²
(MSI) and (MS2) are straightforward from Appendix C.9.2 Note that Chida = (doou) derived as follows (for unbounded kernel kcou). Based on Ki = (Myr Kp) (Keon
(29 can be
X x')
with X, sdd μ. we can use |||/||/ Edon (1) to obtain the following.
MMD com ro(s. a), (r(r,'' Y Toma.-1 1 SC.
E1/2 (ool(To(ssa)) + E1/2 (r, 8', T T Be
e1/2 (V, Tg T 1)5 Σ T(d'ss')
( To (2).0))
a'EA
(((2())))) T ( (d), Since we have the following based on definition of (coo) (s',
Σ
Tadlls')
a'EA
kig
Ecou (omn) T To (s,..,''',
E
No
(com)
(n (s', a'; -n 7Zols' :(n,
2- Ecou (s' (s',
This gives us C(A) Clcou)
(MS3) can be shown analogously with Section C.10 (MS4) regards the model complexity that we assume. C3 0 can be shown be bounded by using supage sups,a Ecou (Ye(s, a)) oc, which is assumed in Corollary B.8
We also obtain Ceurr = C D'- Va where V/2 is the volume of a unit ball in Rd, by Theorem 1.1 of [I] as follows,
Wl(,, v) C. D v2/2 -MD cou (H,
Wp v) < D w (1, v) < D + V MMD (1, v). cou
Then applying this into Theorem C.11 gives following bound, since have B1 2/( }a),
D + 2
V Căper C Op (1o((1/7)
(log N)² 2
Wp.
p.de. (Tor: Tx)
N
b= 1-
maxx
(llenw)
C1/2 C1/2 1iam((; wp.o)) 22-0/2 diam(O; W pp,cz)?
*p
where C² is defined accordingly to 35
53

---

C.15.3 Proof for Corollary B.3
For the case of (o, m, 17) = (MMD3 8=1, W1, W1). we have 9 = 1, 5 = 1, r(2d+3) c 1,
Caubg C, Ceurr 1, ED = 0. We need / > for q = 1 as wc mentioned in (16
have already shown in Appendix C.10 This can be copied since 12 is special case of MMD 8=1 for d = 1. However, (MS2) should be changed follows, based on Proposition 17 of [36]: when M, < 0o, we have
(MSI) holds,
C(d, 3,,r,,,,,) MMD B 2114.) with p' = r(d + 2/221/1111 -
(36)
Refer their Proposition 17 for the definition of constant r, 0. This can be developed into
- (0., (m,,,) = MMD (0, 10,1 0m,,)
(To(s, as), (8....).
n
1/0
2 (d., 1
Wi(To(sis ai). To. (st,
2 (,,
{
WT Te (oth
1/00
1 > 2
/
C M,) Whin (0,
(0, 0m,))-
Since we are limiting to 3 = 1, (MS2) is satisfied with X = C(d, (,,, and 1 = / x(24+3)-1 2d +
r-1
(MS3) can be shown analogously to C.10 In the part of applying Hoeffding's inequal- ity (generalized version for unbounded distributions, e.g., Theorem 2.6.2), should assume supsge sup,,a (l] a; 0)l < oo and sup,,a [[(s a) l12 < xc.
(MS4) is what we assume. Finiteness of C3 > 0 can be shown by using the same trick that holds between energy distance and Wassertein- I metric (as we mentioned Appendix (C.0).
An (010 S F (0 -Fn, (0,,,,,,000,11
F(0(0n,t-1) F(..,.10m..-1))
2
Σ S f:- 1 5 9, ) + 2 E(S f4- E(o 9i (
8 sup (00;0..) < 8 diam ( W1,00) < oo by (MS4). dE
Then, we can apply Theorem C.11 to obtain the following bound, since 31 = 1 a/2.
C1/2 Opf log(1/7)
(log N)²
1,de,1 (Tor, Tx) S 11/2
C/ = T- max { 1, 12/ met diam(O; W 2--/22 )-a/3 diam(O; 10000
11w/2
114072
a/2
C.16 Proof Corollary B.9
We acknowledge that the following proof is based upon Chapter of 20 and Section 6.4 of [51] Throughout this proof, we will resort to the following trick shown by (51)
| 2s vs f < IV vil < (1+ Iv2s
+ for Vs, t 2
Now, let us define the following functions. Define E.a to be expectation taken with respect to Enys to be expectation taken with respect to r, ~ p(... 18, a), Eg/ (<-(e',m)) to be expectation
54

---

taken with respect to z' ~ fo f (6, where (1)6(, == I fom,e- (+|s a (TT('sss))
-log [Jo(r 72110, a) + So., + (2+721)8,
(() = Er,aBr," EE 1o (1-10/
2 fo... + +
1 (fo. (r 72 )2)),,)
(0) 1
-log fo(r: + 72 8i, ai) + fo,, (r; 72/188,
Ezg f0 (1/
2. Sa_, (r: y2/1 (1))
Note that it is more appropriate to write it as M(010n.-1)) and (0 will take On,e-1 E θ (along with the corresponding 0,,() as given, and simplify it as M ((10m,t-11) and (0) = Mn Mm(00mne-1) Since the inner part of Es,o of M()) is equivalent to KLD(Jo.,, (-1s, a)ll fol-ls.a)+ fo., (llaa)) 2 0 where equality holds under O = 0,,t, o,,, becomes the 2 minimizer of M (0) with (O.,,) = 0.
However, we
C.16.1 Quadratic lower bound
For fixed s, a, denote Pu(-) (-1,,a) and p(-) fo(-|s, Then, the terms inside E,,o is simplified as follows with q = { + po).
p(2) + po(2)
[po(2=) > >01} =Ezupo { loog ((=)
po(2) 1 (pD(3)) 0
E Egppo
log
2po(2)
((2)
1 log x < x -
2
1-
po(2)d=
Po20 p=(z)
2
/
/
2. 1
Po(2)
vg(z)d=
-2 2. ppll)) + -12=)-2
V.Vpo(z). v v((2) de
Po>0
Po30
(VPo(z) v()) 2 dz
1
/ (V2po(z)- Viro + +))())) 2dz
Po20
1
JP22 (Vpo(z)- vp(z)) 2dz
(1 + v2)² h/((o.
1
(1+
where hg = 1 op
fzlz)) where fi, fz are corresponding pdf's of 11, U2 E P. Allowing abuse of notation, we will allow putting densities instead probabilty measures for the inputs.
Then, since M (0.,)) O, we have the following where ho, defined accordingly to (8).
M(0) - M(O.,r) = Es,a Bew.eoo (1..a) { log fo(2|s, a) + fo., (2)s,a)
1Seo,, (=)0, 0)
2. (2,
Eg {
(1 + 2222
(1 + V222
Here we have h2 (01, 02) = Esaarp (s) To, (s, a))} with 13(To, (s, To,
takes the integral over the support of Tg., (s,a), or fa., (1s, a) > 0.
C.16.2 Convergence of modulus
We recall the following Theorem 6.13 [1
55

---

Theorem C.13. For any class F of measurable functions f X - R with ll S 6, with
X; sid
Po. we have following with S indicating "bounded by some multiplicative constant,"
Σ f(x.) BF(x))
} S
1 + Vn -116,,,,, -1 (II,B)))) (++J1660 Jr 11 (l..B))
(1+/10.)) 82 8²vnn
E
sup FEF
1=1
111 F, I1 = 1/" ViogN (0), -1)de - /-² Ni+ F, Ddc.
I := Ex-eo -1-(11))))
Let us define the following.
a,,s,,,r,,')) = Bo'nom {f log
[Jo(+ so., (r 72
2 fe., (r + 724 s,
x 1 (r + ( > 0)
:. (+) =
n Σ m mol a, r,, = n2 ==1
1
Σ
mo as ar, $/) - mo., (8 as, rs; rs,
M()) = Es,a, (, = -B(mo a, 8') - mo., (s, a, (,, ()))
We also define Me (mo(...) E θ (mo(...) (........)) 0 0), since
have m........) 0. Since mo(s, a, 8') S log and x < log implies exp([xl) - 1 |x| s
4 (exp(-I/7) 1)², we have the following,
|mol|?a. 2. 2. Br Eno f4. (oxpl (- -m,(s,a,r,s)/2)) - }
By (leaa (V fo(r +
a) [ 72'1 fo., (r 721(s,a) 2
So,, + 72'18,
> 01}.
x
Note that (e --, (laa) can be reduced into Ez-fe., (18,,). Again, letting Pu(-) fe...(-1s, a) and p(-) = (-(,s, a) for fixed s, a, along with q (p + po) 22, the term within Ex,a can be rewritten as follows,
Ez-po {( (1(0e) -1) 1(bo())>0)
/
(V
VP(z)) -1) 2
po(z)d=
pO20
SP020 (V
1
Po +D (z) - Vio(z) ) 2
= 70
(Va(z) V/ooz)) 2dz =
dz
2
/ (Vp(z) - Vpo(z)) 2d = (p p).
(VPo - p(2)) v2pp(z)) 2d <
2 0o20
2 po
Then, this leads to | < 2 ho, (0.,e, 0), meaning that ho. 0) < 2 implies
[mme l1 BB S 6. Then, applying Theorem C.13 gives us the following with modulus constructed as An (8) (0,0,,1)= = (f) M(0) (0.,) M(e..)).
E
sup
(0) M())) (O.,) M
BEBtho, (0_ ()) 204
Vn (1, (Ir.)))))))))))))))))))))))))- (1+ 11166.MM.1 (1PO.8)
(37)
82 82
56

---

Now let us simplify the term J1 (8, II Ilp., Assume a bracketing pair mp(.-.) I m....-.), which may not be elements of Me. That is, we have p(-1....) 2 q(-1 (where we can assume -(-1--.) 2 0 but not necessarily conditional probability densities), and
p a) + fo., (z]s,a)
(fo (2ls,)))))) }
mp(s, r') = Ex'-fo E (12.0)
{
- log
2 fe., (2|5,a)
[g(2|s, a) + (2]s.
(Jo 0) }
(,, Ey Bersen (112a)
log
2. fo., (2|s,
The term [|pp(...) mal-". Pl is defined as follows,
E, Er,e { exp (Imp(s, a, s') m, - (m) m, }"
Employing the same trick that we have used before, the term inside Es,a can be bounded follows with (=() = fe.. (+|s, a) for fixed 8, a,
S 4 EEaPo {
{v
p(z) + (=)
-1) 2 I(pO(2) 1(BO(2)>0) 20]
q(2) + Po(2)
(1(z)
-1) -(pp(()> > o1}
4 Berro
with p1 = + po: P2 q 4 Pa
(2(2)
p1(2) (2(2)
- 1) 2
/
(V
VP2(2) -1) 2
/P((2)
4. Jma
po(2)d2 54
+P2(2)dz
1oi0
2 de
p p Po (2) -1
1 PO (z)
Po>U
2
2
5
(Vp(z) v (1(2))
dd = 16 (p) ④)
Pa20
Then, we have [mp....) - mp(-..) )l P S 4. 11 p( ...) V/(.1 .... >lll)llle || 1I is defined
accordingly to 24). Thus we have the following.
log (MM |l .l..,B.e) s log Nf Il -le.. 4/e).
Then, this leads to following by assumption,
(1 ll (l)o.n) S [-' Voog 11- e/2)de S C C brack
1
81-0/22
ax/2
We will later select 6n such that C- brack i-af2 82-0/2 vn 8% and apply Theorem D.1.
C.16.3 Consistence
Before we apply Theorem D.1 let us show ho Ox,)) + O. By Lemma 4.2 of 20 we have following,
(0,,,, 0..e) = Eg
(hō(fe,, (0
(e,,
2 + /2)² E. Enawp { 112 So.. + ff (118,a), So, (1s.(()))))) }
$ (1+ + v2)2 |M(0n.)) (n((n)))
The first inequality holds by following. Letting p be an arbitrary density and 1 (p po), we have
k2 Po) = 2
1
/
(vett
| Po
(x) -VDu(z) dz d==
2
= 1 //50
(VD+po)Ce - /2po(z))
po>0
2
4
po20
/ (Vp(z) vpo(z))2dz
1
2
4(1 2)
2(1 + v2
Po>0
57

---

The second inequality above holds due to following. Note that On, is defined as follows by (TO) with d(P. Q) PL and we have following based on concavity of logarithm function, i... z+y
log 2 2 2
log x + 2 log y for z, y > O.
On. arg min
1
Σ
Eey son (166,7) - log fo(r; 72llo0
BEB TE
a) (x)s,
San. (2|s,
fo.,, (2)s,
Sá., (21s,)) a)
log
1fo.. (z|s, > >0) log (o.,(2)5,,)
1 (2)s, > 0).
2
Then this leads to following which justifies the inequality,
0
<
E B f0. (16622)
log fo... (rr + 72///1,, a.) log fo., (ri + 724 si)
71
2
7
E So (16/20) log (Jom. (T's + 72/101, ai) + Sa., (Ti +
<
72
2. fo.. (r, + (2/1s;;
(f (ri + 72/1s, a;) > x))}
22 (-Mn( + (0x..)) + B.a.ro m (s,a,r,')}
fe., (1,, a) + fön.. (1|,,a)
22. (MM. + (( - E,s hig
So (o,, (15,
The last line above holds, since the term Exano { -ma., (s, can be bounded using the following fact,
/ log p(z) po(z) (Pp((z) > 0) po(=)d= $2 / (V - -1) -))p((s)de 1 logr S V -
D(2)
Po(z)
2
22 I (Vp(z) VPo(z))dz - -2 - -f (Vpo(z) ) dd -2 1..(p.pp
POS0
Using [M(0n..) (,.)) = (0100 since Mn (0..)) M(.,.) 0. we can show the following by Markov's inequality and (37), with probability bound not depending on d
An (n(000 } - 0,
(0),, c) S
E
sup AEB
as long as diam (Fa 1111)) <0.
C.16.4 Finalization
As we mentioned at the end of Appendix C.16.2 we let
8n 0
where Co = C. brack 1-
1
a/2²
1
ITa/2
ho. (Bn,t, 0,,z)
Crack
00
a//2
Now let us bound further bound Wasserstein metric by ho- Considering two densities p and po. we have
f PO20
Ipo(2) - p(=))d== = / (VPo(2) vv(z)) (Vpo=)) + vp(=)|dz
20
(1 1020
(VPo()) - V2(3Te)
1/2
(
(Vpo(=) + vo(3)22
1/2
< 4. ho(po.P)
58

---

This allows us to bound TVD metric as follows,
/loo(s) p(z)ld= - / [mo(2) - p(=)
(mo(2) p(2)]dz
Po>0
p>0
/ (P(()) - p(2)ld2 < 12 (Po.
33.
po20
Based on Wp(P,Q) S D TVD Q) shown Lemma C.6 of 63 this leads Wp(po p) S C. D.D.hi 1/p
110 Pp. p). This leads to following,
p On 0,,() = C. Ceover h/ (Ōn,e: Bn,t)
1/v
1/2 brack
I4072
3/n Op
S C. D. cover
aa22
Letting T -T-
24a 1og1/7 Mj. we apply N/T based (6). and we obtain the following
1/2
bound for W p.dd.pp ( )x),
1/p
D
1/E Ceoser
1
1-a/2
1/p
24a
I u brack
7
- a222 a-a/2
2+a
1 2p
N
21a
x0p
log1/7 N
Of course, we should show that condition of Lemma satisfied before we apply (6. Its proof analogous Appendix D.5 that we used in proving Theorem C.II
C.17 Comparison and examples on Cramér FDE
C.17.1 Comparison between Cramér FDE and FLE
Although FLE [3] did not suggest a probability bound for Wp.d innacccuaca we can utilize their key results (e.g.. their Lemma 4.9) to build such bound. With probability larger than 1 5, we have the following with in a single iteration based on D, with [De] = n:
Vd
10 n
log Nin(Fe, (*DD)))) /
1/20
W p. T b,,,-,) &
C1/2p cover
1-7
Here, || can be any norm that can be defined on Fe. For fair comparison, let us use
V == sup
[= a)(dz,
which is what we already defined in (NS4) (or Appendix C.1en Skipping algebraic details, this leads to following with appropriate choice of T with respect the size of whole data N (D).
W p.de p (Tor, Tx) S Ör(N 2 (1-)))
under
log 10,,, S ea
Assuming the same condition, can also bound ( (le,,, E)) where Fo represents
the conditional edf family, as we have mentioned in Appendix C.10 Letting M = log (Fo, o0, e), there exists pairs of functions (((())---),,4((111 - that serve e-bracketing of Fe. Then, let us define
L,(ls, = 1." 4(els,
U,(vls,a)== = [f" (
There Now arbitrarily pick Fa(-....) ) E Fe, and let its corresponding conditional pdf as Jo(.)...) There exists bracketing pair [4x(7.... u+( .fl..))) such that 4(.....) - fa(. ...) 5 ux ux .... and
59

---

(-..)...))auu 12,)0, S c. Then, not only do we have L+(-I...)) - Fo(:) ...) S UA(-....).
but also
|| ( Un(1).... )ll,,, sup {"
T (1(y)s,a) Us(uls, dy
6 [_ (2 a) dzdy S (b - a) - 11l (bb-o) -). sup / s,a
This further implies 1 |l |1,,,00 (b a) e) S logNV (l,, S E
thereby satisfying the condition of (NS4). This allows us to apply Corollary [..1 yielding
W p.de (Yor, xx) = Op w(e-)).
C.17.2 Example 1: Linear MDP
Let us assume the following model with Q (F)), where F is a collection of cdf's of random variables bounded in (a, bj. Here, we can see 0 as an element H() = ..,,,, with each H F.
Me: = To E (Pla, b)) with To(s, a) has edf Fo(z|s,
(.s.a)..()))
H (F)
where (Ø(s, a). 1k) = & ox(s,a) 2 0 for Vss E S x A, ΣΦ = Esa-p ( a) (s, is non-singular.
(38)
Note that tabular setting (S x Al < xc) is special case of linear MDP model. This is the case with ( a) 1(s, a (s. with 1..... .S Al.
Assumption 3.1 is satisfied when the transition expressed as a linear combination of features (bbss, a), s')) with (rr,s') (0,(r, (x((r, 8')T being valid densities
p(r; s'|s
over R x S. Also assume Assumption C.4
For (NS4), we can use Theorem 2.7.5 of (55 to bound log Nog,Ni I Letting Q Unif[a, b], we have the following,
log.Ni 1FF, [I.,,) NogNN116 (F, (Q), F2 (Q) in the first equality.
-- - C(b - -e-
-
where we have used || - F2ll., ab- |
Arbitrarily choose TH, T E Me and their corresponding edf's FH, (-|s, a) = (Ø(s, a). H.)))
and FH, (-1s, a) = (d(s, a), H2(-)) Then, we can derive the following with Fla, bj being the edf's of bounded random variables in (a, b).
(og,N]](Fe.1] || (l.,,o, c) $ K log. (F b), (].,, S CK a) -7
The first inequality can be verified as follows. Let the bracketing pairs of F be (+(,, u.()), [.a()),, (-) where M logg || e), Make K copies for each pair, that (1))))) have (.), (k) (.),, ... 116 ()), (0 (-)) for each & [K]. This means that we can construct M tuples of
[1 2 11, 1 u (11)) where f1, .J.. [M].
Pick an arbitrary F(-...)) Fe. and it has corresponding H H(HH,,... (HI,.... ,H) such that F(-|s, a)
(Ø(s, a), H())) Since (-) E [7(0)) (1) ... Hx(() E [1(K] (k) for some ji.... ijk E [M] Then, letting Fi(-18,a) a) = Σx (x, a) (.) and (-(),,)) = Ex dn a)u ()), we have F(.I...) E [Fo(.I...) Fa ... We eventually have
"j
[[I((---..) Fu(1... ... L1 sup /" Fu(z)s, Fi(2)s,
K Σ
< sup
()) Uja
(k)
(z) - (10) (z)
(=) dz <
In
(z)
sup
|lu - 1,2 Se,
8.0 km
kE[R]
60

---

which leads to Nij 1| c0. < [M]](F.11 IL,,, c)} Note that we have supage s.p sup; [z s, a)l I 1 and can let Cbrack = CK((b a). a 1 in (NS4). Even- tually this leads OPNNN1/18))) W p. convergeeee in Corollary B. However, FLE cannot suggest meaningful bound since they assume the existence of conditional densities, which may not hold in our edf-based model.
C.17.3 Example 2: Linear Quadratic Regulator
We will denote state-action pairs as 2, a. A= = Rd x Rd,, its conditional reward as R(r, a).
and subsequent stater as x' z' (z, a). We assume the following setting
x' 2'(x,a) a) = Ar + Ba & R(z, a) = x QQ + Ra + eR & T(x) = Kx,
where ER can follow any fixed distribution.
(39)
Temporarily, we will assume bounded distribution for ER (although this can be relaxed for Energy FDE). Letting Eret model.
-0217" with ER,t being iid copies of ER, we assume the following
Me = [To ff (P(I)) SxA where To a) the probability for Ze( a)
(40)
2T Mix a M2x + a M3a + Gret with 0 (M1, M2, Ms) E Rdxxd= Rd. xdz x Rd Xd.
Throughout the proof, we shall assume the analogous statements that 63 suggested in their Lemma B.3, bounding ||=]], ||a]], || p, [|Mllle,
||
Assumption 3.1 can be satisfied with appropriate modeling of θ S RR xd, Rdd x Red xda, By following the same logic shown in D.9 of [63], we can present an example. Skipping all calculations, T Zo (z, a) ToT a) follows a distribution T (z(z, a) E1T Ze (z, }}} Eret with,
T Zo(I, a) - - AT AT
E
+ t + 7. A A + MIKB - MM33+MB)BB }u
+ + R+T- (BIMB+B B }a
Let our model be θ = {(M,, M3): || [F. M| F. | F S m]. T" E MM holds if the following conditions are satisfied,
||Q|| + > || (1+ |K|| + || m S m
7 |||||/ ||B|| {1+ | ||| + | 2m S m
||]| + +| {1+ ||||| + || m S m.
Assumption C.4 can be simplified as follows. For X μ + Exet and Y My Cret, have the following with Px. , Py being their probubility measures and Fx, Fy being their edf's,
W (Pxx Pv)
[x) (y())d IM Mxl Mk Mzl
Note that the second equality holds, since Fy is only a location shift of i.e. (r()) = Fx Px(--10 (My
He)). This leads to the following with 0 = (M MM41) _M(4) and 0g = -MM( (B) ( (B) M2 (B))
_M/
Wi (T, (z, a), Teg a))
(T(((A) M( Jar + a (M( M )r + a (M MR )a (p(x, a), AAB)
where ((x,a) = (o) @ aT)T and some O E R(d=+da) Using the fact that
W, Wi(Te (I, a), Tea aI) A a))((, TOAB, we obtain
sup Wid.i Wid. (Y TT
0 E s 0AB
sup
0.00c0 Wh (Yo, Tx)
B da)? 0
θ E
AB s 0
where
Es.d. == Brand (1( a)p(x, } & Esp == En (ateoo/@(r,,))01 ((1,,))(r,a))
61

---

This is the same result that [63 provided in their Lemma B.2. Lastly, let bound the term log (og,N) 1) for (NS4). First, define
F = pe : x A +R
pa(x, a) = (zs(e.a) (
with llme= - 102 == sup
pol [o, a) - (2,
2,0ESXA
We can N[[(FFell || c) I Mf ll Ilao for the following reason. Letting M
( ll lloo e), there exist bracketing pairs {[4()), 4-1 such that
Vuo F EE [M] such that [1(()) - u, (-)l S..
(i L.)... For an arbitrary Fo ...) E Fe, its corresponding expectation function satisfies 4(x, S ug(2, a) S (z, a) for some E [M] As we have previously mentioned, all Fo (0(-(2,, a) are results of location-shifte of the edf of Gett This leads to Fo Fo -..) (-1 .....,))..)..)))). Fu. (-1 for some i [M] and it satisfies
Now consider the bracketing pairs F.,
[1 ...) Pu, (1. ... )1,,, = [14(()) - ux(-)ls S 6. Thus, we have (Fe ()) S M1)(F e). Further assuming || S D2 and ||a|| S Da, we have
|000 - M0 1000 = sup
x
M1 TT(M(A) - -M,- )x + aT (M,{) -M, y + at (((aaa - -M² )a
3.a
< mmax Dof2
|1.00(4) -M1 11
\ - -1 op + ||.M - M2 1lpp lop +
<3D (.)
where ds(0A,0B)) = max [| - 1 Ie. Il - M F|,, |1
- 11 [1 and Do
m Da). Then, we can bound our target as follows,
(F. ||,,,,,, <) s &N NF) lloo.) N |1. 11 SNO, d3, c
6D9
s SN(0 11001,11-11. 11, 6D6) x N0 || ||5, GD} ( 1|,, 6Dg )
where , = (M, ||Mil S mj. Since O₁ 22 θ with
|| can be perceived as subsets of ||. we can use volume comparison
Fuclidean spaces RRd RRddd Rdudu with Fuclidean norms lemma
3- diam(A, 11 11111)
log. N NA, 11, Sp. p.loog log
for A AER,, Ve diam(,,, II))
This leads to the following.
118 D3 m
log Nog.N] (Fe c),, S de log
Since our term can be bounded by inverse of polynomial (F) 11 112,,00, e) S - with any 0, we can let a. 1//log N.
If we assume bounded distributions of frew, then we can apply Corollary B.I with the same trick (32) wp convereece..... If we assume unbounded distributions, then Energy FDE obtain (r(NN1/8) of W. Wi,d, --inaccuracy by Corollary B.3 For FLE [33, unless have standard parametric distribution for 6ret. (e.g., truncated gaussian), we cannot obtain the bound, since we cannot relate [| ..) - (- Ill and dg (0A.0 0p)-
Cramér FDE obtains ((V-/)(())) of
62

---

D Auxiliary proofs for Appendix
C
D.1 Supporting theorem
Following is a standard convergence theorem in M-estimation. We slightly adapted it from Theorem 6.1 of [51, only modifying I into generalized I 2 2. So we will skip the proof.
Theorem D.I. (Adapted version of Theeorm 6.1 of (51y) Assume that Fn,c(:) + R.. has
minimizer O.. Let 8n 2 0 be a sequence that satisfies the following for 2 on:
1. (8, 0.) (2,8), 8), then (() Fn,,(6.) 120)24 X
2. We have (66) Co 80o with some co (0, such that following holds,
E
sup (00:d.
(Fn, (0,0m0mmm))))) F (00,t0
2(0)
- ((Fn((01(0m.-1)) - -F..(0.18mm,)))) S
Further assume that we have 5n and some estimator such that
((5,)= S vT. 6% & 8n こ 8n & On + 0, in dn.
Then, we have d, (0,, 0.) = (6.))) fr = 0, then we have 8n = Oo n 2211-00)
D.2 Proof of Lemma
C.7
Without loss of generality, we assume Ö We let Zu n// Xn,ts and C
lim lim simsup SuPIEN
E|n2//b Xn,el < 00.
T T Zn. 2
1== T- Zn,il
1
Σ 1=1
<
sup 1E[T]
E Zm
1-6
Then, letting
C I-(
é, we have
C
P T- Zn,t 2
21=11- -- 8
Thus have ΣT= (h- 1o-t.Xn,tt 0p( -n -1/b), More generally, have ΣT (T-t.Xn,
Č. Op(( 1/0).
D.3 Proof of Lemma C.8
Showing the upper bound is easy. Let X, X sid Q and Y, Y sed P. Based on technique shown in Appendix A.6 of 26
derive
Q) - - Y| B| - X'II + [E| Y Y - Y'Il
< W. Q) + (P,Q) 2 (P,Q))
Due to Jensen's 's inequality, it is straightforward to see (P,QQ) < W,(P.Q) for <
Now let us show the lower bound. We assume that X P and Y Q have bounded support b).
and we denote their edf's ''' as Fp and Fq. Letting U Unif a, b], we have
(PP.Q) = (b a) [U) Fo(U))lz,ar) where |X (2, == (
< (b - a) (F)(U) Fo(UU)l<a(T))
by Jensen's 's inequality
(b - 1)/2 12P
63

---

where = [Fp(z) - Px denotes Cramér distance. Since Energy distance is equivalent to Cramér distance in ID domain 77. that is JE(P, Q) (2,, Q), this leads to
2 b-a (P..QQ)
E(P = 2.
Using Q) 2- (b a) - Q) that was shown by 44 (see their Section 2.3), we can show the lower bound.
D.4 Proof of Lemma C.12
D.4.1 Conditioned event
Let f,,t-1 E θ be fixed. Then, we have unique value of 0z,, arg mingge F(01@,,c-1). Based on this, we define the following:
x m² (Te(s), az), Te.,, (s), where 84, ~
sid P. & y; : X B(X,), Os = Nm,, (0,,,, = {0 e (0, <d]
With Ω being the probability space, we define the following event based on 3 E (0, whose exact value will later be determined,
(() -((9)) $ 800
Ω =
w E
sup BE8g
(41)
-=1
S 60) (: y = 0). (w) (w) y (w)
w EQ
sup
#c
Prior to calculating its probability P(S2s,, let us first show its sub- uub-gaussianity. Since || ll norm (Example 2.5.7 of (57)), we can use its convexity to derive
| r llee I |x ll E||X 11
Assume that 0,,0g 0g E θg- Then, we have
|X - x = m 2 m Te, (81, a1), (81. m² (T (81, a1), Yo., (r),
m (To, (1), To. a1)} mTTo, 01), To (81, a1)}
x mf (81, a1), To., (51, a1)} + m m (82 To. (s1
$ 2- diam(Os; mxx) m (0, 62).
where diam Moo) = #2ee, mao (0,, 02). This leads to || - y S C diam (9x; mxx) m, 02). Then, by applying Theorem 8.1.6 of (7]. we have the following bound for arbitrary u 0,
1 (Y. - v.a..) S
C
{ { v VlogNN())) Macs c)de
diam((Qs; Vn
sup 0E
+u- diam (5; moo)
with probability larger than 1 - 2 exp(-u?).
Using the constants defined in Lemma C.12 let u -n- 88-88/1 88//C2 to show that the following holds with probability larger than 1 exp( - -n -828 /4C2),
Σ (Y v000))
C1 + 8
sup 0
for 4g > 0.
Vn
i=1
64

---

Now, we assume the following:
20 1/0
Criterion-I: 82
(42)
vn
Since we have 1008
we have vn"
(P(2)) =
sup AEes
E (V v/o1)
S 8
2 21-2 2xp=2-epp((- 828 /4C2).
(43)
Under Ωgg we have the following. Suppose 0 E Gg. In other words, m0, B2,,) < 5. Then, have
n X B(X9) s
[ (0,
-0,,10,00.))
where
1/2
1 Σ
Mm.1 1 (01,
m² {To, (oi, (og ai)
i=1
This leads to the following with 3' = min [min(3,2] [3,2].
m (0, S m. 0..) m (m,,) (0, (0,0..)) s 5 8 2.88 88 where we assumed 5 E (0, 1) without loss of generality. Then, we have the following.
Under Ωs for 40 E Os. (0,1(0,0 S 22. 88//2 holds.
D.4.2 Concentration of modulus
Assume that Z, {(s a;) {;);;=
given (fixed). However, there still exists randomness in the
transition rs, s -p(... . [s a.). For this conditional probability, denote its corresponding conditional
expectation as Ez, (...) == E(... (2,) and its corresponding sub- sub-gaussian norm as || (l))())) Then, sup OgG:m., (S..0..)....88.1
by Dudley's inequality (Theorem 8.1.3 of (57) and (MS1), we obtain following.
Ez, sup AA, (010,, Ez. 1EEe
| (010,, 01) under Ωg (41
Csuba
log (0.. V2. -2-83'12) 829 mm, e)
Vn
VI--2'/2
Csuba
log NoN (0,,e, v2 58112), Mm, c)de
Vn
12
C Csuby
Mog,N(O,
Vn
By Assumption of Lemma
C.12 we have
C3s Dc.
Then, we have the following.
E
sup Á, (010m..-1))
OEO,
E
sup i
Q6
P((s))
+E sup
(010m,,
12/
F((2))
BE6s
520
E
sup å (010
Q8
+ E
sup
Á (0) n, z)1
528
2exp
-n
by 43
4C2
12688122
Csulg
(n--22) 828
log N(, mms c)de + C. exp
AC2
Crubg Vn
-n. 623 629
Cent 5.2 228
C3 exp
4C²
65

---

Then, we set another criterion as below,
Criterion-2:6 6 2 5(2),
where ( is such that > 2 implies
n1 6
Vn Couby
Cent 8 8
C3 exp
(44)
4C2
This leads following bound, whose RHS does not depend on 0 p- O
E sup A (010 Lees
2C
Csubg
Cent 8'
(45)
Vn
D.5 Satisfaction of the condition of Lemmal C.7 in Theorem C.11
Before bounding Ad (T er. xx) based on 6 we first apply Lemma C.7 by letting Xn, m ( TTT 0 )- Proving lim sup, suPten El 1/6 .xn,tl < oo is the analogous to (Y
Appendix C.8.4 We do not need Stage 2 of Appendix C.8.4 Skipping the details, we can repeat
Stage of Appendix DopendixxC...4tto obtain the following, with A, ( defined in Lemma C.12
IP m (0.1 2 2M S Σ on
x 22220-011 8
E
sup mp (2.
A (0(0
32M
Using 45 and letting 3' minf +000/2 2} with ag = 1 - a/2 (as chose within the proof of we can take up the above inequality as
Theorem C.1 of Appendix C.15.I).
Db
P mp, (p Ba,)) 2 2M 88
C
Conty Cent
2
(2 6n) Can'
Vn.
After that, copying the remaining logic of Appendix
C.8.4 will give us the desired result.
66

---

E Experiment Details
E.1 Details in Linear Quadratic Regulator
LQR is parametric environment with deterministic transitions and Gaussian noise in the rewards. It can be verified that Assumption C.4 holds given the chosen behavior policy, and Assumptions i. satisfied under the appropriate model space, both of which we will present. We will compare the performance of the baseline method FLE [63] with proposed FDE method using different functional Bregman divergences: Energy (3 = 1), Laplace (Matern with v = 1), RBF, PDF-L2, KL. The evaluation is based on the W 1ii.,,,-inacccraae
The proposed FDE methods using different functional Bregman divergences outperform FLE in terms of both mean inaccuracy and stability (as measured by standard deviation), as visualized in the inaccuracy graphs of Figure 2 This performance gap is expected, as FLE does not make use of the closed-fore form density of (r, R.,..,) making it suffer from large Monte Carlo errors. See Table in Appendix E. 1.4 for detailed inaccuracy results.
E.1.1 Data collection and model
Our offline data are collected as follows. States x = - sin sin02) OT) are generated with r Unif 1]. 0₂ Unif[0, 2T.. Given the state, action is generated by behavior policy b(alz) = 1/5 with a = Rot(O, )x where Rot(O.) is the (counter-clockwiss angle 0₂ Unif(0, 2m im Gn 5x). Since the all æ within the unit circle has positive density value 5:
rotation matrix with
and Rot(O.) = K holds with positive probability, Assumption C.4 is satisfied.
We assume deterministic target policy (which, for the time being, be regarded abuse of notation). With Gaussian noise added to the reward 6R ~ NO,, our goal is to estimate Y, pSxA, States x S and actions SAAC R² Matrices A, B, Q, R E 2x2 that control the environment dynamics (corresponding to p(r, s'1s, 8, a)) are as follows (but unknown in the simulations).
S A with
are both generated from a continuous subset of R² (i.e.,
(xx a) = Ax + Ba & R(z, a)
x TQ= + a Ra + ER
&
T (x) Kx,
0.6 0
0.2
0
& Q = 4
1
2
1
& B
&
R =
0.8
0
0.1
1
Letting K be the identity matrix, assumed y 0.99 and oo 1.
Return distribution model based on (40) of Appendix C.17.3 can be written follows,
Me= = { To E (P(R)) SxA where To a) is the probability for Za (zz, a)
xT M + a M2 + a M3a + N N(10
with 0 = (M1, M2. M3) E R222x3
Note that this setup satisfies Assumption 3.1 (proof Appendix C.17.3.
E.1.2 Data splitting
We applied the same splitting rule data D = U|_ D, by selecting the following T. We acknowledge that we did not strictly apply the rule of Theorem C.5 that will lead to asymptotic convergence with the suggested rate.
1. We used the rule of Theorem C.5 with the parameters of Energy FDE with inaccuracy measured with Wasserstein-1 metric 8,8 1, 1, 1). We also used a since it is a parametric model.
2. We divided it with a constant Cdivide > 0 and then choose the floored integer as follows. Since larger discount rate shall require bigger subdatasets (i.c., larger [DrD, we let Cdivide 5 for 7 = 0.99.
min 1/g]
T
2(1 - 1) + logi/7 N
Cacvide
24
3. Allocate the same number of samples into each of the subdatasets, and then put all the remaining samples to the last one Dr.
67

---

E.1.3 Closed form for gaussian distributions
Since we have gaussian conditional densities, we have used the following closed form. For MMD that we have used (Energy, Laplace, RBF), we have the following with k(x, y) ku(x y) with mutually independent X, X' P and Y, Y Q.
MMD P, Q) = ( X x)) + -2 -Y)
- -
Defining Ko(u, (z~NN(H.22) (ko(2)}; we have following for Energy distance which has ko(y) = l1yl.
Ku(u, ku( = (
[
2
exp
(-
112 20²
+
111
(1
2Φ
114 (-11)) ))
RBF kernel with ko(y) exp(-y) /AORBF2) have the following.
(-
4
2
Ko(H, 02) ) = exp
(- "AonFr" + 20
1
2BRB
Laplace kernel with ko(v) hap(-lyl/oLaap has
0²
Ko(u, exp
①
L0L
2
Eexp
TLap
(-" p
+ exp
20
2
TTap
TT.pp
For PDF-L2, we used the following formula for @(-11, 02) represents the density function of N(,, || 00 02)1
2
(- [11 n22
VATOz
V2T =02)
cxp
2 + o2)
For KL Divergence, we have
of (11 - n22
(L(N(H), || N (Hz 02)) = log
d2 +
20
2
Within our simulations, have used fixed values of Lap OBB
E.1.4 Simulation results
We have applied L-BFGS-B algorithm solving the minimization problem of (5) at each iteration i E [T]. For the initial value of L-BFGS-B algorithm, we always used the previous iterate 0n.-11- Simulation results visualized in Figure 2. with details in Table
68

---

Inaccuracy Blg scale)
Size
Figure 2: W 1, inaccuracy (Y-axis: logarithmic scale) for different sample sizes N (X-axis) through 50 simulations. Shaded areas are (mean + STD/ /50) regions for each method, with thick lines being the means.
Table 4: Mean W I,d,, -inaccuracy over 50 simulations (standard deviation in parentheses)
N
Energy
Laplace
RBF
PDF-L2
KL
FLE
300
0.627
0.3361
0.3074
0.2643
0.6302
I.5668
(0.5522)
(0.2142)
(0.1776)
(0.1493)
(0.5493)
(0.2838)
350
0.3453
0.2648
0.2471
0,2105
0.3453
I.5537
(0.2095)
(0.1396)
(0.1287)
(0.1096)
(0.2093)
(0.2734)
400
0.3082
0.2557
0.2261
0,2128
0.3078
1.5348
(0. (0.1758)
(0.1294)
(0.1056)
(0.1025)
(0.1755)
(0.2568)
450
0.2221
0.1771
0.1773
0.1710
0,2222
1.5293
(0. (0.1268)
(0.0782)
(0.0765)
(0.0744)
(0.1269)
(0.2485)
500
0.2143
0.1962
0.1747
0.1480
0,2143
1,5597
(0. 1037)
(0.0946)
(0.0723)
(0.0574)
(0.1037)
(0.3352)
550
0.2114
0.1821
0.1686
0.1577
0,2115
1,4932
(0.1250)
(0.0951)
(0.0913)
(0.0841)
(0.1251)
(0.2865)
600
0.
0.1766
0.1658
0.1466
0.1897
1,5288
(0.0889)
(0.0890)
(0.0829)
(0.0759)
(0.0891)
(0.2571)
650
0. 1683
0.1518
0.1496
0.1392
0.1684
1,4921
(0.0936)
(0.0809)
(0.0780)
(0.0749)
(0.0936)
(0.3214)
700
0.1507
0.1459
0.1424
0.1358
0.1506
1.5143
(0.0733)
(0.0628)
(0.0611)
(0.0517)
(0.0733)
(0.3056)
750
0.1343
0.1313
0.1297
0.1215
0.1343
1.4949
(0.0702)
(0.0682)
(0.0656)
(0.0585)
(0.0702)
(0.3226)
0.1198
0.1177
0.1146
0.1091
0.1198
1,5040
(0.0512)
(0.0553)
(0.0576)
(0.0517)
(0.0512)
(0.3862)
850
0. 0.1199
0.1150
0.1100
0.1047
0.1199
1,5714
(0.0479)
(0.0470)
(0.0476)
(0.0484)
(0.0479)
(0.3766)
900
0.1
0. 1098
0.7072
0,1059
0.1136
1.5689
(0.0493)
(0.0450)
(0.0448)
(0.0429)
(0.0494)
(0.3886)
950
1.1
0.1063
0.1010
0.0940
0.1113
1.5502
(0.0448)
(0.0405)
(0.0404)
(0.0381)
(0.0448)
(0.3319)
1000
0. 1003
0.0983
0.0947
0.0944
0.1003
1.4774
(0.0438)
(0.0467)
(0.0452)
(0.0463)
(0.0438)
(0.2979)
69

---

E.2 Details in Atari games
E.2.1 Deep Neural Network structure
Our model consists of two parts: (i) CNN layers that reduce x 84 x 84 image into 512 features, (ii) multiple layers that transform 512 features into |A| x M 3. Part (i) is identical to the structure of 35 that first applied DQN in Atari games. After training the optimal model via DQN (with the same network structure with 35 for ourselves,
copied this part (i), and then freezed it, assuming that this part already performs good recognition of the image. Part (ii) contains the components that trained in methods. To make the model sufficiently complex, we included multiple hidden layers that reduce the 512 features into 512 + 450 - 400 + 350 + 300 - 250 + 200 + 150 + 128 |A) (M 3). with each layer containing ReLU. For given input image, the model outputs three parameters (weight, mean, variance) for each gaussian mixture component, for every action as follows.
M
a)) = E a; ()) (s) where M = 10, 100, 200. a;
m=1
Here, Wm represents gaussian component for the GMM model, which together sum up to 1, i.e.,
Em= ()) 1.
For quastile-based methods, we preserve the same layers, except that the output distribution has M quantiles instead of [ x 3) parameters. That is, this consists of multiple hidden layers that reduce the 512 features into 512 -> 450 + 400 350 300 250 - 200 150 - 128 - (A] M, to form the following distributions based on dirac-delta's 's 6pz-
To(s,a) a)
Σ
8m (m as,,;
where
M 10, 100, 200.
Note that GMM modeling (asymptotically) accommodate dirac delta based modeling with sufficiantly small variance values o (s, a; 0) Ro and equal weights wm (s, a; 0) = 1/M.
E.2.2 Algorithmic details
Our goal is to estimate y E -PSXA, Here, the target policy is π = n- which is the ppsilon-greede
variant (e-g., see Section 2.2 of (53) of DON-trained policy 355 with 6 ctar- We collected
offline data (N = 2K, 5K, 10K) through the trajectory of an agent following a behavior policy
b n² with Cbh For most cases, we let Cbch > Caar so simulations, we applied FDE methods based on Algorithm with T = 50. Minimization of (5) of Algorithm is done stochastically by Adam. In each (-th iteration (t 1.... ,T), we ran 1000 stochastic gradient updates, each based on a batch of 32 randomly selected samples. For practicality, unlike LQR simulations shown in Appendix E.1.2] we did instead reused samples throughout multiple iterations.
satisfy Assumption C.4 In all
data splitting for each iteration, but
When measuring the inaccuracy, instead of Wi.d.. Tx) that requires heavy computation to approximate, we computed Wi (r T d is approximated with 1000 pre-sampled observations of state-action pairs. These are sampled by Algorithm 2 which is commonly used strategy of sampling s,a dz (e.g., see Algorithm I of (.). Using the pre-sampled state-action pairs g(mm), (1)) (m 1, 1,... 1000), we sample (m) Ye, (s(m), (a(m)) for each m, by which we approximate r Based on the same s((m), (m). we can also sample z(m) ~ (s(m), (m)) by forming a long enough trajectory starting from initial state-action pair s(m)) (mm) and adding the consecutive rewards. This gives us approximation of T
where rd- == -SxA T(x, (s, a) E P. Here,
Although our theorems (Theorems 3.4 C.Il give us bounds for il (T Tx), this can also lead to bound for r(rd= rd*). This is due to the following inequality based on convexity of (5 and (16) in Appendix C.4
W, (T r I ( Tz).
70

---

Algorithm 2 Sampling m state-action pairs from d
Input: Initial state distribution 14, target policy n, discount rate 7, transition P())s,a)
2: Output: State-action pairs {(((m) (mm"))] 10m
3: for m = 1 to 1000 do
4: Sample Seur jr and aeur T(- Seur)
5: Accept <- False
6: while not Accept do
7:
Sample U ~ (O,
8:
if U < 1 y then
9:
Accept True
else
11:
Sample s' P(. Sour: Oeur)
12:
Sample a' ~ π 5²)
13:
(Scur: Ocur) aa)
14: end
15:
end while
16: (s(m), (m)) + (Seury aeur)
17:
output (s(m), am))
18:
end for
E.2.3 Closed / approximated form
computed single term in (10). i.e., To_.. (o...1)) )). for MMD methods and PDF-L2. Since Laplace FDE had ill per- formance due to its numerical difficulties that we aforementioned, we excluded it. For other methods (i.e., KI., TVD, Hyvärinen divergences), we not have closed form objective func- tion for GMM. Therefore, we approximated it with Monte Carlo approximation by 2//2,6 widd (r + Mia (s', 0-1,,, 7² of (s', "','''00) with j2 1,.... M and 1,... B, which represents a single mixture component of L s I
Based the formula of Appendix E.1.3
o(Yo(s,a), a), V (r,r,'', s',
For KL FDE, we convert maximizing the expected aigllikelhhod, with individual term being as follows. Here, P(( is the density of the probability measure P and 6(-1p,, (²) means the density of [(, o²). When computing the density of (x, S ) we sampled a' (-|ss) instead of
making use of T (a' for all a' E A in every method, for the sake of computational convenience.
{ log ((Z)
Ez E2' (rot
M w (s','';0-1)
B
M
W/ as Hlsfabi Ps (s,a;)), (0,00))))
log
B
J1=1
For Hyvärinen divergence, we instead maximized Hyvärinen score with individual term being (1,s',T, "rss',T.....) Sz (Z', To(s, a)) as follows, which computed by MC approximation in the same way (assuming GMM for P),
8² log [( +
1 @
log s(:1p) 2 0z
(H, = 022
Σ M Wy (z-H,)² 2
((2;11900))
j=l Wi (=سيجعك) مiž of)
M
Σ == Wi - 2lz (2:130007)
2
f=1 wi o(z U1j. 03)
71

---

For TVD, we approximated ()f()I)((s;,a)) - f(-1 V (rs, s To Tom,e-1 db)lla, by using the density ratio follows,
(())))((,a))
1
M
Bz:w0. (r.
Σ 12
W3 W5 "s',''''' 0110
f T
B
Σ- 1 "ij (s, 0 2 (8, of (8, a: a))
1
B
Σ jzml w/s ('', 0-1) 2 ./r + (8' 1), 72 of (s', d'; 0-11))
hm
We let B = 100 and B = 50 for deterministic transition and stochastic transition. respectively, which we will explain in the following subsection (Appendix E.2.4). We added term Evar = 1.0 to the variance (s. a; 8) in PDF-L2, KL, TVD, to prevent explosion of density values, thereby mitigating numerical instability, and used the same value for the tuning parameter of RBF FDE. i.e. ORBF = 1.0. For Hyvärinen, we put Evar 10.0 since it was more prone to numerical instabilities. Even so, we could not run simulations for M 200 due to numerical instabilities. The good thing about Energy FDE is that it does not require any tuning parameter, which makes it more user-friendly (and performance was good as well).
E.2.4 Simulation settings
In simulations, we always assumed 7 0.95. Every time reward is observed, we clipped it between 10 and 10, and then multiplied it by a fixed constant (20 in our case). Then, we tried two different settings: (i) deterministic transition p(r, s' s as,a) as the original Atari games, (ii) added small noise (O, 1) to every reward to make it more random (which makes it a better environment to apply distributional RL). We also tried two behavior policies for each setting, which leads different coverage.
First, let start with Setting-1, 11 deterministic transition. Here, the target policy is Tha. (Ctar-greee greedy version of (but Cbch- 0.4, 0.5 for Enduro and Pong prevent sparse observation of rewards). Of course, weak coverage (i.e., Cbeb being a lot bigger than (ar) leads to worse performance. Results are visualized in the first two rows of Figures 3 for N = 10K (Tables 19 for N 2K, 5K, 10K). In the simulations, M refers to the number of gaussian mixtures in GMM model and the number of quantiles in quantile-based models (QRDQN, IQN).
optimal policy π²) with etrr = 0.3. The behavior policy is Ehch = 0.4, 0.8
Second, we ran simulations on Setting-2, random transition (or reward). Here, the target policy is πT (deterministic policy learned by DQN) in all games except Breakout. In Breakout, we let π = =.... with étar = 0.3 to prevent the agent from being stuck at certain point (not proceeding with the game and repeating the same actions). The behavior policy has Ebch 0.1, 0.5 for all games (Chch = 0.1, 0.3 for Pong only). Results are visualized in the last two rows of Figures for N 10K (Tables 20 33 for N 2K, 5K, 10K).
In our simulations, we have tried 7 games, 3 different sample sizes (N 2K, 5K, 10K), 3 different number of mixtures (M 10, 100, 200), 2 different environments (random / deterministic reward), 2 different behavior policies (good or bad coverage). These amount to x 3 x x x 2 252 different settings, each leading to various shapes of return distributions. In each setting, we have applied different methodologies (FLE, QRDQN, IQM, KL, Energy, PDF-L2, RBF, TVD, Hyvärinen) we plotted (mean + STD) area for each method.
under 5 different seeds. In Figures 5
E.2.5 Simulation results
Simulation results for each of the aforementioned 252 settings are shown in Figures 3 and Tables 3 As we have stronger coverage (i.c., Ebch being closer to etar), we achieve lower inaceuracy levels. In many cases, we could see that the inaccuracy levels generally became lower with larger sample sizes. We could also see that density modeling (based on gaussian mixture models) helps improving the accuracy, even when the reward is deterministic. This can be seen by comparing our methods (KL, Energy, PDF-L2, RBF) with quantile-based methods (QRDQN, IQN) that use the same number of M (number of gaussian components in GMM or number of quantiles). Moreover, TVD does not improve the accuracy throughout iterations. This corroborates our claim in Theorem 2.4 since TVD is not a functional Bregman divergence.
72

---

Since it is difficult to compare the performances for every single setting, we summarized the perfor- mances of each method in [ We have grouped the 252 settings into four categories based on (i) deterministic / random reward and (ii) strong/ weak coverage. In each category (which consists of 84 settings), we measured the rank values of nine methods (with being the best and being the worst) based on their mean inaccuracy in each setting, and then recorded the mean of rank values. Our FDE methods (KL, Energy. Hyvärinen) showed the highest three accuracies most categories. Although KL FDE recorded the highest mean of rank in all four categories, it does not mean that we should always resort to KL FDE. There have been well-known criticism on KL divergence (e.g., unbounded divergence value, high sensitivity the tails of distributions, necessity that probability measure is absolutely continuous to the other, inability to consider closeness in outcome values) [e.g.. (e.g..28.55 (2,5288,5) 77.
Table Mean of rank values of inaceuracy under all settings of each category. Three methods with best accuracies are boldfaced in each category.
Category
Method
Reward
Cover
FLEE
QRD
IQN
KI.
Energy
PDF
RBF
TVD
Hyv
Deterministic
Strong
3.60
6.19
8.25
1.77
3.36
4.38
5.03
8.11
2.78
Deterministic
Weak
3.00
6.39
8.30
1.84
3.14
4.69
5.47
8.09
2.42
Random
Strong
4.42
5.30
7.00
3.03
3.15
4.07
4.07
8.63
3.59
Random
Weak
3.76
6.09
7.31
2.34
3.61
4.46
4.23
8.61
2.40
Deskoatle te vesinnel
Dvd wiahteeeiooo
Zaree wyplerticcheeeeeeg..
5
) inaccuracy in each games (columns) for different methods with M = 10, N = 10K: (rowl) deterministic transition with strong coverage (Ebeh. = 0.4). (row2) deterministic transition with weak coverage (Ebeh. 0.4), (row3) random transition with strong coverage (Ench = 0.1), (row4) random transition with weak coverage (Ebch > 0.1).
Figure (Mean STD) of W1 (r d
73

---

Aearrs vitormttiooo
Enskorte oe
Drs staterentood
Figure (Mean = STD) of W (T " -inaccuracyy in each games (columns) for different methods with M 100, N = 10K: (rowl) deterministic transition with strong coverage (Cbeh 0.4), (row2) deterministic transition with weak coverage (Cbeh > 0.4), (row3) random transition with strong coverage (Cbeh. 0.1), (row4) random transition with weak coverage (Cbeh 0.1).
74

---

Eeakorte oe
Des siatemmntord
Mertsfrreeee4
Mtarth St
Deb Delesthhrentoodd
Bu McPhMMersr...o Shemestioo
Figure 5: (Mean = STD) of (T ( -iinaccuracy in each games (columns) for different methods with M 200, N = 10K: (rowl) deterministic transition with strong coverage (Cbeh 0.4), (row2) deterministic transition with weak coverage (Cbeh > 0.4), (row3) random transition with strong coverage (Cbet. 0.1), (row4) random transition with weak coverage (Cbeh 0.1).
75

---

Table 6: Reward-variancee Eps=Small, Game--AlaniiSSoFranes---- v4
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.02
9.84
9.86
2.13
2.54
3.54
3.7
9.85
1.3
10
5K
1.87
9.84
9.86
1.51
2.31
3.6
3.73
9.85
1.29
10K
1.73
9.84
9.86
1.8
2.54
3.59
3.72
9.86
1.34
2K
2.22
4.13
9.85
1.71
2.28
3.54
3.77
9.87
1.77
100
5K
1.88
3.87
9.85
1.67
2.29
3.65
3.44
9.85
1.77
10K
1.85
3.93
9.85
1.93
2.26
3.87
3.42
9.87
1.88
2K
2.27
2.84
9.85
1.93
2.4
3.76
3.63
9.85
NA
200
5K
1.69
2.88
9.38
1.61
2.33
3.34
3.16
9.85
NA
10K
2.39
2.83
9.85
1.68
2.35
3.56
3.24
9.86
NA
Table 7: Reward-variance--. Eps=Small, Game-BreakoutNoFaanett v4
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
3.63
10.87
10.89
6.68
3.37
4.48
4.81
10.89
2.81
10
5K
3.21
10.87
10.9
2.78
3.22
4.39
4.37
10.89
2.58
10K
3.44
10.87
10.89
2.29
3.25
4.18
4.36
10.89
2.91
2K
3.51
4.93
10.89
2.7
3.49
4.56
4.43
10.88
2.91
100
5K
3.47
4.58
10.89
2.9
3.29
4.38
4.22
10.88
3.19
10K
3.24
4.24
10.88
2.37
3.1
4.28
4.29
>100
2.32
2K
3.28
3,88
10.88
3.15
3,41
4.49
4.21
10.9
NA
200
5K
3.39
3.65
10.9
3.02
3.26
4.11
3.92
10.9
NA
10K
4.06
3.19
8.34
2.9
3.23
3.74
3.97
10.9
NA
Table 8: Reward-variance=O, Eps=Small, Gane=-EnduoNoFFrameciiiv
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
12.69
19.25
19.25
12.68
13.0
12.37
12.36
19.25
14.1
5K
>100
19.25
19.25
9.42
11.17
10.89
10.81
19.25
11.32
10K
11.28
19.25
19.25
11.67
11.72
10.98
10.98
19.24
12.17
2K
12.52
15.33
19.26
11.08
12.83
12.31
12.4
19.25
12.99
100
5K
11.51
13.51
19.25
10.64
10.91
10.84
10.93
19.24
10.65
10K
10.95
12.15
19.25
11.46
11.61
10.99
11.0
19.25
12.43
2K
12.6
14.31
19.25
12.24
12.9
12.51
12.57
19.25
NA
200
5K
10.47
12.5
19.26
10.58
11.1
10.89
10.85
19.24
NA
10K
12.11
12.55
19.26
11.65
11.71
10.92
11.0
19.24
NA
76

---

Table 9: Reward-variance-t Eps=Small, Gume-Kungfuussteroorrankkkkk
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.83
9.04
9.25
1.84
2.66
3.61
4.12
9.23
1.91
10
5K
2.82
9.09
9.25
2.85
3.38
4.3
6.7
9.24
2.6
10K
3.1
9.1
9.26
2.57
3.36
4.09
7.8
9.26
2.72
2K
2.53
4.1
9.22
1.42
2.52
3.3
3.62
9.26
2.17
100
5K
2.89
4.8
9.23
2.85
3.38
4.05
4.52
9.25
3.65
10K
>10
4.26
9.23
2.29
3.02
3.94
4.7
9.23
3.03
2K
2.74
3.16
9.24
2.0
2.63
3.38
3.49
9.26
NA
200
5K
3.73
4.19
9.24
2.77
3.43
4.19
4.44
9.24
NA
10K
3.01
3.79
9.23
1.97
3.17
4.43
4.2
9.24
NA
Table 10: Reward-variance-d Eps=Small, Game=-PnggNoraamskkii
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
1.79
4.99
4.99
1.66
1.79
2.42
3.93
4.98
3.2
10
5K
1.57
4.99
4.99
92.04
1.64
2.53
3.92
4.98
2.8
10K
1.92
4.99
4.99
2.05
2.05
2.81
4.22
4.98
3.02
2K
1.53
4.71
4.99
1.76
1.62
2.38
2.41
4.98
2.74
100
5K
1.62
4.61
4.99
1.77
1.65
2.5
2.62
4.98
2.61
10K
>100
4.59
4.99
1.91
2.12
2.81
2.96
4.98
2.92
2K
1.62
2.75
4.99
1.87
1.6
2.32
2.39
4.98
NA
200
5K
4.84
2.62
4.99
1.76
1.63
2.42
2.52
4.99
NA
10K
>100
2.67
4.99
2.04
2.04
2.73
2.99
4.98
NA
Table 11: Reward-variance=0. Eps-Small, Camm=-borttoFFrancsskppvvv
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
>100
21.74
21.82
10.8
11.82
12.74
12.9
21,81
10.87
10
5K
10.96
21.76
21.81
10.79
11.52
12.5
12.09
21.83
10.74
10K
11.2
21.76
21.81
10.29
11.29
11.55
11.45
21.81
10.51
2K
23.68
12.79
21.8
10.69
11.47
12.0
12.29
21.8
10.08
100
5K
10.71
11.94
18.76
10.34
11.26
10.7
11.42
21.81
10.63
10K
10.47
11.65
21.8
9.83
10.65
10.46
10.95
21.79
10.49
2K
11.67
11.88
21.81
10.74
11.37
11.76
11.79
21.81
NA
200
5K
11.19
11.13
21.81
10.22
10.93
10.68
10.81
21.81
NA
10K
>100
10.9
21.8
9.98
10.59
10.21
10.29
21.8
NA
Table 12: Reward-variance-d Eps=Small, Gume=-SpueInvvdersNoFraaaem v4
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
3.02
15.35
15.37
2.73
3.55
5.76
5.82
15.38
2.73
10
5K
2.87
15.35
15.37
2.16
3.72
5.79
5.71
>10
2.2
10K
2.79
15.35
15.37
2.17
3.66
5.63
5.54
15.36
2.88
2K
3.03
4.53
15.37
2.42
3,07
3.73
4.8
15.37
2.38
100
5K
2.58
4.23
14.07
2.15
3.22
3.6
4.31
15.38
2.31
10K
2.43
4.24
15.37
1.93
3.12
3.09
3.91
15.38
2.06
2K
3.39
3.5
15.36
2.54
3.1
3.58
4.06
15.36
NA
200
5K
2.92
3.04
11.07
2.58
3.07
3.22
3.74
15.38
NA
10K
2.43
3.14
15.37
2.07
2.67
2.82
2.88
15.37
NA
77

---

Table 13: Reward-variancc=O. Eps=Big, Gume=AAlantisNNoFrnessspp
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.31
9.84
9.86
2.34
3.09
3.82
3.91
9.86
1,5
10
5K
1.87
9.84
9.86
1.67
2.53
3.5
3.56
9.87
1.88
10K
2.55
9.84
9.86
1.98
2.87
3.82
3.78
9.85
1.58
2K
2.25
4.5
9.85
2.18
2.81
3,9
3.91
9.87
1.46
100
5K
2.42
4.17
9.86
1.97
2.36
3.22
3.46
9.85
1.49
10K
2.02
4.54
9.85
2.14
2.51
3.88
3.92
9.85
1.74
2K
2.65
3.32
9.86
2.2
2.77
4.21
3.92
9.84
NA
200
5K
1.8
3.06
9,86
1.7
2.39
3.78
3.78
9.85
NA
10K
1.81
3.26
9.85
2.12
2.7
4.27
3.84
9.86
NA
Table 14: Reward-variancess Eps=Big, Gume-BrrakoutooFrrmekk... v4
M
N
FLE
QRI)
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
7.14
10.88
10.9
6.66
7.29
9.31
7.95
10.9
6.72
5K
6.13
10.88
10.9
5.6
6.87
8.25
8.39
10.89
6.02
10K
6.45
10.88
10.9
5.09
6.74
8.17
8.01
10.88
5.98
2K
6.66
8.97
10.89
6.73
7.08
7.13
7.37
10.89
6.28
100
5K
6.8
8.24
10.89
6.13
6.6
7.15
7.09
10.9
6.18
10K
6.56
8.37
10.89
6.08
6.55
6.82
6.83
> >100
6.07
2K
7.25
7.98
10.9
6.75
7,03
7.21
7.45
10.88
NA
200
5K
6.67
7.51
10.85
6.42
6.82
7.09
6.92
10.9
NA
10K
6.63
7.57
10.9
6.17
6.54
6.94
6.99
10.87
NA
Table 15: Reward-variance=0,, Eps-Big, Game-EEnduuNoFFameski--
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
16.85
19.26
19.25
16.72
16.65
16.97
17.78
19.24
17.6
10
5K
15.46
19.26
19.26
15.33
15.29
15.34
16.22
19.24
16.8
10K
15.68
19.26
19.26
15.85
15.7
17.29
17.59
19.25
17.12
2K
16.79
18.53
19.25
16.7
16.7
16.42
16.88
19.24
17.2
100
5K
15.69
18.5
19.26
15,42
15.34
14.79
15.9
19.24
16.25
10K
15.23
19.14
19.25
15.89
15.65
15.19
15.89
19.25
16.81
2K
16.99
17.94
19.25
16.58
16.73
16.48
16.75
19.25
NA
200
5K
15.6
17.13
19.25
15.28
15.27
14.89
15.8
19.25
NA
10K
15.5
17.53
19.26
15.81
15.65
14.88
15.39
19.25
NA
Table 16: Reward-variances Eps=Big, Game=KKnnffuMasccNoooFraaaeee
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
8.37
9.24
9.24
8.02
8.19
9.12
9.21
9.24
8.23
10
5K
8.07
9.24
9.25
7.73
8.03
9.15
9.22
9.25
7.75
10K
7.86
9.24
9.24
7.6
7.95
9.13
9.21
9.24
7.71
2K
8.16
9.2
9.24
8,05
8.16
8.11
8.76
9.22
8.06
100
5K
7.94
9.2
9.23
7.67
7.92
8.44
8.94
9.26
7.67
10K
7.89
9.2
9.24
7.55
7.77
7.75
8.98
9.23
7.6
2K
8.29
9.09
9.23
8.05
8.1
8.2
8.86
9.25
NA
200
5K
8.0
9.0
9.24
7.64
7.94
8.25
8.75
9,23
NA
10K
7.71
8.93
9.24
7.52
7.73
8.07
8.88
9.23
NA
78

---

Table 17: Reward-variance=0,, Eps=Big, Game-PonggooFraeskkip-o
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.36
4.99
4.99
2.33
2.51
2.95
3.35
4.98
3.1
10
5K
>100
4.99
4.99
2.26
2.66
3.51
3.78
4.98
3.05
10K
2.13
4.99
4.99
2.18
2.32
3.19
3.54
4.98
2.9
2K
2.16
3.86
4.6
2.41
2.4
3.57
>100
4.98
2.57
100
5K
2.23
3.78
4.99
2.46
2.76
3.71
3.71
4.98
3.16
10K
2.24
4.11
4.99
2.25
2.34
3.22
3.49
4.98
3.0
2K
2.43
2.54
4.99
2.58
2.44
3.13
3.51
4.98
NA
200
5K
2.43
2.58
4.99
2.57
2.55
3.56
3.71
4.98
NA
10K
2.19
2.59
4.99
2.19
2.42
3.0
3.74
4.99
NA
Table 18: Reward-variance-O,, Eps=Big, Game--hhetNoFrameekipp
M
N
FLE
QRI)
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
14.35
21.8
21.81
12.08
14.59
15.56
15.6
21.81
13.04
5K
14.27
21.8
21.82
12.62
14.72
15.8
15.63
21.82
12.88
10K
14.75
21.8
21.81
13.96
15.1
15.91
15.89
21.8
13.06
2K
>100
15.4
21.81
14.24
14.31
15.64
15.43
>00
12.68
100
5K
13.95
15.84
21.81
13.91
14.7
15.81
15.7
21.82
13.22
10K
15.8
16.35
21.81
13.99
14.93
15.79
15.79
21.79
13.03
2K
14.03
14.72
20.51
12.97
14.14
15.45
15.57
21.81
NA
200
5K
13.71
14.69
21.82
13.69
14.7
16.06
15.9
21.8
NA
10K
14.79
15.22
21.13
13.9
14.87
16.16
16.17
21.82
NA
Table 19: Reward-variance=O, Eps-Big, Game-fpecchnaddenooFaanciiiii
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
7.26
15.36
15.38
7.39
8.12
9.22
9.34
>100
5.95
10
5K
7.24
15.36
15.37
6.91
7.81
8.88
8.94
15.37
5.8
10K
6.33
15.36
15.37
6.17
7.45
8.69
8.58
15.37
4.72
2K
7.87
9.29
14.73
7.45
7.85
8.95
8.91
15.39
5,89
100
5K
7.26
9.09
15.37
6.78
7.59
9.1
8.65
>100
5.47
10K
6.64
8.06
15.38
6.19
6.8
8.79
8.48
>10
5.04
2K
7.5
8.13
15.37
7.41
7.92
9.0
8.5
15.38
NA
200
5K
6.98
7.92
15.37
6.7
7.45
8.68
8.59
15.37
NA
10K
6.55
6.88
15.36
6.18
7.11
8.09
8.43
15.38
NA
Table 20: Reward-variance-1 Eps=Small, Gamo=AllaatisNoFFanekkki v4
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
9.3
15.58
16.0
8.67
9.79
10.64
10.86
>10
8.66
10
5K
7.43
15.34
16.37
6.61
8.23
9.8
9.69
16.96
6.88
10K
8.01
15.47
16.14
7.46
8.78
9,98
10.01
16.95
7.09
2K
8.96
10.37
16.05
8.52
9.81
10.71
10.78
16.89
8.14
100
5K
7.87
8.96
13.8
6.38
7.73
9.28
9.13
16.95
6.47
10K
7.27
8.35
15.89
7.39
8.34
9.87
9.68
16.95
7.31
2K
8.04
9.62
12.89
8.71
9.66
10.34
10.34
16.89
NA
200
5K
7.51
8.09
16.08
6.91
7.73
8,47
8.4
16,95
NA
10K
7.67
7.87
14.63
7.41
8.44
9.3
9.33
16.95
NA
79

---

Table 21:
Eps=Small, Game-Breakouttooraaassk-----
M
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
7.94
7.45
8.91
7.96
6.21
4.47
4.66
>100
8.2
5K
7.75
7.23
8.26
6.41
6.88
4.97
4.88
10.89
8.56
10K
7.57
7.35
8.45
6.27
5.76
3.84
3.6
10.9
8.29
2K
7.62
4.8
7.58
7.65
6.48
3.94
5.52
>00
7.87
100
5K
8.17
6.02
7.09
7.15
6.34
6.49
6.32
10.89
9.81
10K
6.8
4.72
6.58
6.52
6.88
5.72
5.66
>100
7.92
2K
7.14
5.58
9.33
7.51
6.38
5.43
5.9
>10
NA
200
5K
8.37
6.77
6.52
7.14
7.37
6.28
6,35
10.88
NA
10K
7.67
5.37
7.97
6.84
5.62
5.62
6.03
10.9
NA
Table 22: Reward-variance=l, Eps=Small, Game--EndrooNoFrmesiigg
M
N
FLE
QRI
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
16.47
30.61
28.15
16.11
15.65
19.27
20.04
35.43
16.65
5K
12.88
28.69
27.79
14.16
13.99
17.56
17.3
35.44
13.75
10K
12.94
28.97
34.49
13.01
15.23
17.04
17.01
35.42
13.94
2K
15.29
20.12
29.65
17.63
17.02
18.45
18.9
35,43
16.91
100
5K
13.21
17.4
25.74
14.44
13.07
15.42
14.12
35.43
14.17
10K
19.26
17.35
33.79
14.46
12.57
15.89
16.2
35.42
14.24
2K
16.47
18.94
28.05
17.57
16.25
18.12
18.14
35,43
NA
200
5K
13.48
16.46
32.63
12.04
14.91
14.96
15.53
35.43
NA
10K
23.39
14.49
33.97
14.49
13.34
15.79
15.63
35.42
NA
Table 23: Reward-variance=1l, Eps=Small, Gamn=KKungFuMaacceeaaaaaannnp
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
5.28
13.84
14.28
4.71
5.38
6.15
5.67
16.35
4.47
10
5K
5.18
13.79
15.45
4.53
6.39
6.74
6.99
16.21
4.91
10K
5.47
13.67
11.28
4.08
5.7
6.41
6.78
16.26
4.91
2K
5.06
6.52
14.1
4.27
4.64
5.45
5.17
16.36
3.94
100
5K
5.04
6.82
15.51
4.39
6.12
6.36
5,82
16.23
3.86
10K
5.57
6.61
15.33
4.4
5.02
5.61
5.95
16.25
3.8
2K
4.43
5.73
15.26
3.51
4.7
5.17
5.2
16.37
NA
200
5K
5.29
5.44
14.88
5.34
5.33
6.4
6.19
16.23
NA
10K
7.53
5.85
15.38
4.3
4.99
5.71
5.54
16.24
NA
Table 24: Reward-variance-- Eps=Small, Game--PngNoorameeskie
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.07
4.4
3.98
1.57
1.62
1.54
1.58
5,82
1.66
10
5K
2.23
4.91
5,4
1.84
1.87
1.71
1.64
5,94
1.87
10K
2.29
4.97
4.01
1.83
1.89
1.65
1.74
5,98
1.99
2K
1.85
2.4
3.32
1.63
1.59
1.3
1,36
5.82
1.67
100
5K
2.11
2.52
3.16
1.87
1.8
1.38
1.4
5,93
1.94
10K
2.74
2.8
3.48
1.97
1.84
1.46
1,56
5.98
1.74
2K
1.75
1.64
3.03
1.64
1.54
1,39
1.35
5,82
NA
200
5K
2.35
1.78
3.39
1,79
1,86
1.38
1.4
5,93
NA
10K
2.2
2.06
4.84
1.86
1.8
1.59
1.46
5.99
NA
80

---

Table 25: Reward-variance=1, Eps=Small, Game=OhertNoFrrmexippy
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
55.54
20.34
18.33
17.53
16.87
19.14
19.07
30.08
21.31
5K
20.71
18.41
10.83
20.86
17.7
>100
19.07
30.23
22.11
10K
20.08
23.4
29.16
19.75
17.04
19.03
18.54
30.31
20.86
2K
>100
21.99
17.19
21.47
18.71
19.38
19.61
>100
21.05
100
5K
21.43
11.46
28.83
21.11
14.68
19.5
19.5
30.22
21.13
10K
44.06
16.0
29.07
17.35
19.83
19.44
19.15
>100
20.9
2K
20.54
21.43
24.77
21.07
17.79
19.62
19.48
30.07
NA
200
5K
20.55
18.94
24.2
21.18
17.11
19.36
19.94
>100
NA
10K
19.93
16.07
28.88
17.77
13.27
19.67
19.39
30.3
NA
Table 26: Reward-variance=1, Eps=Small, Game-SSaactnvvdeesooFaaasasee
M
N
FLE
QRI)
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
2.45
15.31
7.41
1.79
2.75
4.52
4.17
>100
1.53
5K
2.7
15.73
10.72
2.65
3.91
4.95
5.39
19.05
2.16
10K
2.63
15.6
11.07
2.02
2.98
4.44
4.6
>100
1.56
2K
6.26
3.75
13.67
1.88
2.38
2.79
2.98
18.93
1.54
100
5K
3.1
4.07
8.68
2.39
2.81
3.91
4.18
19.05
1.68
10K
3.89
3,94
12.68
1.77
2.93
3.05
3.2
19.2
1.5
2K
2.44
2.62
13.69
1.86
2.46
2.66
2.83
18.93
NA
200
5K
3.53
2.86
8.45
2.27
3.4
3.44
3.77
>100
NA
10K
2.7
2.81
6.55
2.27
2.67
2.71
2.44
19.2
NA
Table 27: Reward-variance=1, Eps-Big, Game-AAlantiSNoFrrmesspppp
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
8.59
15.19
15.67
8.08
9.23
10.4
10.41
16.47
7.87
10
5K
8.62
15.5
14.08
8.41
9.38
10.5
10.42
>10
7.95
10K
8.47
15.57
15.11
8.35
9.41
10.62
10.54
16.81
8.23
2K
8.02
9.79
15.67
7.99
9.06
10.31
10.17
16.47
8.11
100
5K
8.85
9.95
13.83
8.42
9.06
10.38
10.33
16.63
8.57
10K
8.49
10.13
15.36
8.24
9.06
10.49
10.64
16.8
7.76
2K
8.29
9.0
14.87
8.04
8.86
9.82
10.08
16.47
NA
200
5K
8.99
8.29
15.71
7.82
9.09
9.95
10.09
16.63
NA
10K
8.54
9.32
13.2
8.18
9.28
10.29
9.96
16.8
NA
Table 28; Reward-variancee Eps=Big, Cunc-BBrakkuttooorueeippp
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
3.22
9.3
7.43
2.58
3.24
4.47
4.47
10.52
2.94
10
5K
3.8
9.44
10.19
2.72
3.66
4.87
4.85
>10
3.27
10K
3.57
9.64
10.28
3.0
3.93
4.8
4.79
10.81
3.07
2K
>00
4.23
7.17
2.44
3.39
4.13
4.15
10.52
2.79
100
5K
3.49
4.67
8.32
3.32
3.68
4.27
4.71
10.73
3,07
10K
3.98
4.97
7.5
3.21
3.65
4.89
4.77
10.83
3.21
2K
3.73
3.55
8.33
2.45
3.25
4.13
3.65
10.52
NA
200
5K
4.11
3,98
9.21
2.66
3.67
4.28
4.22
10.72
NA
10K
3.58
4.27
10.09
3.22
3.75
4.54
4.44
10.82
NA
81

---

Table 29: Reward-variance-,, Eps=Big, Game-EnduroNo
M
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
32.27
34.71
32.87
32.4
32.41
32.06
32.08
35.28
32.38
5K
31.56
34.54
34.43
31.49
31.36
31.01
30.99
35.24
31.42
10K
31.51
34.7
34.37
31.46
31.41
31.18
31.1
35.39
31.46
2K
32.27
33.53
32.97
32.33
32.29
31.98
32.01
35.26
32.32
100
5K
31.47
33.19
32.92
31.32
31.37
30.72
30.86
35.24
31.38
10K
31.65
33.67
35.27
31.52
31.56
31,18
31.07
35.39
31.59
2K
32.19
33.08
34.61
32.37
32.28
32.0
32.06
35,27
NA
200
5K
31.37
32.5
34.32
31.13
31.32
32.18
30.89
35.24
NA
10K
31.52
32.86
35.26
31.46
31.47
31.12
31.01
35.38
NA
Table 30: Reward-variances Eps=Big, Gamee-Kungfuuasteeoorramssappp
M
N
FLE
QRI
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
12.89
15.41
14.16
12.92
13.21
13.4
13.69
16.17
12.75
5K
12.76
15.31
13.43
12.53
11.82
13.05
13.13
16.08
12.63
10K
12.86
15.4
15.97
12.54
12.97
13.14
13.12
16.06
12.26
2K
13.05
14.31
15.68
12.89
13.15
13.16
13.08
16.16
12.77
100
5K
12.52
14.06
15.89
12.6
12.95
13.0
12.98
16.07
12.67
10K
12.92
14.05
15.99
12.67
12.82
12.92
12.9
16.06
12.35
2K
12.8
13.64
15.63
12.85
13.06
13.16
13.21
16.17
NA
200
5K
12.94
13.37
15,89
12.55
12.96
13.06
12.93
16.07
NA
10K
13.17
13.36
15.75
12.59
12.84
13.08
13.0
16.06
NA
Table 31: Reward-variance=1,, Eps=Big, Came-PongNNoFrameskiivv
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
3.26
4.99
3.71
3.08
3.07
2.8
2.86
5,94
3.15
10
5K
3.98
5.17
5.95
3.9
3.72
3.7
3.66
5.92
3.82
10K
4.25
5.24
12.39
4.03
3.9
3.83
3.82
5.97
4.01
2K
3.38
3.44
4.14
3.1
3.01
2.31
2.44
5.95
3.27
100
5K
4.9
4.1
3.79
3.87
3.73
3.14
3.12
5.92
3.68
10K
4.17
4.16
5.52
3.9
3.88
3.39
3.23
5.98
3.84
2K
3.42
2.91
1.73
3.06
2.98
2.36
2.37
5.94
NA
200
5K
3.91
3.67
4.7
3.64
3.74
3.1
3.19
5.92
NA
10K
4.29
3.68
5.33
4.0
3.85
3.34
3.36
5.98
NA
Table 32: Reward Eps=Big, Game--hortNoFrameskkpp
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
20.91
28.59
29.96
19.67
21.92
22.96
23.01
30.16
20.76
5K
20.15
28.36
29.58
18.3
20.7
21.67
21.93
30.11
19.52
10K
19.81
28.37
29.8
19.19
20.87
21.84
21.81
30.24
18.97
2K
20.77
22.46
29.32
19.01
21.59
22.53
22.69
30.17
20.81
100
5K
20.26
21.62
29.26
19.7
20.14
21.3
21.35
30.11
19.38
10K
19.68
21.31
28.75
19.83
20.11
20.8
20.65
>10
18.92
2K
21.34
20.79
29.01
20.68
21.54
22.19
22.05
30.16
NA
200
5K
19.63
20.54
29.7
19.52
20.04
20.73
21.01
30.11
NA
10K
19.67
20.24
27.25
19.54
20.26
20.19
20.52
30.23
NA
82

---

Table 33: Reward-variance=1, Eps=Big, Cane-SSaceladdeekoorraasppp v4
M
N
FLE
QRD
IQN
KLD
ENE
PDF
RBF
TVD
HYV
2K
6.15
16.76
11.54
5.91
7.54
9.86
9.78
18.89
5.33
10
5K
6.76
16.75
9.79
5.61
7.38
9.4
9.62
18.91
5.02
10K
5.1
16.81
16.36
5.81
6.92
9.34
9.21
19.06
5.41
2K
6.35
7.91
12.26
5.56
6.25
8.23
7.71
18.88
5.98
100
5K
6.55
7.94
16.3
5.57
6.61
7.59
7.86
18.9
5.14
10K
6.14
7.67
12.07
4.86
6.07
7.3
7.18
19.05
5,41
2K
6.21
6.8
10.59
5.4
6.95
7.87
7.43
18.88
NA
200
5K
6.2
6.87
13.29
5.31
6.38
7.1
7.14
18.91
NA
10K
5.83
6.43
10.75
4.86
6.33
6.95
6.78
19.05
NA
83

---

E.3
Computation resources
Our simulations are extensive. We used high performance computing system. For LQR simulation (Appendix E.T), we have used CPU, 2GB memory. A single run of single method under a fixed setting takes approximately 20 seconds. For Atari games' simulation (opendix(E.2).... we have used GPU, 10GB memory. A single run of a single method under a fixed setting takes approximately 700 seconds.
84


Reviews:
[{"review_id": "hm8xIrxKXN", "reviewer": "Reviewer_peoQ", "summary": "The paper addresses the problem of distributional off-policy evaluation, and proposes a framework for designing extensions of fitted-Q evaluation to the distributional setting. Fitted distributional evaluation (FDE) replaces the regression of the scalar Bellman backup with the minimization of a discrepancy measure between a learned conditional return distribution and the distributional Bellman backup. The authors propose a set of guiding principles for choosing a discrepancy and a metric on the space of distributional Q-functions such that the resulting FDE scheme can converge with respect to this metric. The authors provide results on how to extend metrics on real numbers to contractive metrics on distributional Q-functions, in particular for expectation-extended metrics. Furthermore, the class of functional Bregman divergences is shown to be a suitable choice for a discrepancy measure. Bounds are derived for the discrepancies defined as squared metrics in the tabular setting, and for expectation-based metric extensions with general functional Bregman divergences, leading to new FDE variants. Experimental results on a linear quadratic regulator align with the derived convergence rates, whereas inaccuracies on Atari games do not closely follow the theoretical results but tend to outperform the considered baselines.", "questions": "Questions:\n\n* Why was a Gaussian mixture model chosen to model the return distribution? This seems like an important design choice but I am missing a justification/discussion.\n\nTypos:\n\n* Line 216: “used” twice.\n* Closing bracket missing in line 221.\n* Article missing before “corresponding supremum-extended metric” in line 160.", "limitations": "Yes, limitations are addressed in the discussion section.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n* The paper is well-written, and follows a clear structure.\n\n* The claims are well supported by the theoretical results in the paper.\n\n* Distributional off-policy evaluation is a relevant problem for real-world applications, in particular when safety matters. The paper addresses this problem in a principled and comprehensive manner that, to the best of my knowledge, is not available yet.\n\n* The authors offer a good discussion on the limitations of their framework, such as the focus on Bregman divergences, or the completeness assumption for the model class.\n\n### Weaknesses:\n\n* The paper is quite comprehensive to a point where it feels like even a very condensed version of the content barely fits into the main text. That makes it hard to read for someone not familiar with this research area.\n\n* The results on the Atari environments are difficult to interpret as they differ a lot from game to game. It is not entirely clear to me which design choices in implementing the algorithms lead to these results. Some qualitative analysis of the learned return distributions could help form a better understanding. However, I do acknowledge that the main contribution of the paper is clearly not empirical.\n\n* The behavior policy in the Atari experiments probably leads to quite similar behavior as the evaluated policy as they are both epsilon greedy with different epsilon parameters. It would be interesting to additionally consider distinct policies.\n\n* The paper makes several assumptions about coverage, for example in line 255 (total coverage of the state-action space), or in line 296 (coverage of the target distribution). However, also principle (P2) looks like it requires total coverage of the state-action space as it requires the Bellman update to be the unique minimizer of the population objective. A discussion of the role of these coverage assumptions and how they could be relaxed would be interesting from a practical perspective.", "was_revised": true, "final_justification": "I recommend acceptance of the submission for its principled and comprehensive treatment of distributional off-policy evaluation. The authors responded to the concerns raised by other reviewers and me regarding the high density of the main text and the long appendix which can make navigating the text difficult. The authors outlined planned changes to improve readability and minor issues with the writing.", "rebuttal": "Thank you very much for your efforts. Below are our responses to your comments.\n\n## Weakness-1: Too condensed.\n\nWe agree that we have a significant amount of content to fit into the paper. Other reviewers have made some suggestions to improve the readability. We will revise the paper to address these comments. We plan to add more details (e.g., adding Theorem C.4 as suggested by Reviewer HoeH) to the main text. We also plan to add proof sketch/outline (as suggested by Reviewer vbgr). Besides, we will add a table of content in the supplementary material for easier navigation of the supplementary material.\n\n## Weakness-2: Difficulty in interpreting the simulation results of Atari games\n\nIn Figure 1, except TVD (not a functional Bregman divergence) whose inaccuracy value stayed still throughout iterations, all other methods have at least shown improvement of accuracy. This demonstrates the validity of our FDE methods that are based on functional Bregman divergences. Furthermore, we can see that our FDE methods generally have lower mean inaccuracy values (dots in Figure 1) and more stable estimation (smaller standard deviation) than the baseline methods (FLE, QRDQN, IQN). Our settings can be categorized into four groups depending on random / deterministic transition and strong / weak coverage (explained in Lines 1542-1554). In the table below, we presented the mean of the rank values (1 being the best and 9 being the worst) of inaccuracies shown in Tables 5-32. We can see that our three FDE methods (KL, Energy, Hyvarinen) outperform baseline methods (FLE, QRDQN, IQN) in most settings.\n\n| Reward type   | Coverage |  FLE | QRDQN |  IQN |   KL | Energy | PDFL2 |  RBF |  TVD | Hyvarinen |\n|---------------|----------|-----:|------:|-----:|-----:|-------:|------:|-----:|-----:|----------:|\n| Deterministic | Strong   | 3.603 | 6.190 | 8.254 | 1.778 | 3.365 | 4.381 | 5.032 | 8.111 | 2.786 |\n| Deterministic | Weak     | 3.000 | 6.397 | 8.302 | 1.841 | 3.143 | 4.698 | 5.476 | 8.095 | 2.429 |\n| Random        | Strong   | 4.429 | 5.302 | 7.000 | 3.032 | 3.159 | 4.079 | 4.079 | 8.635 | 3.595 |\n| Random        | Weak     | 3.762 | 6.095 | 7.317 | 2.349 | 3.619 | 4.460 | 4.238 | 8.619 | 2.405 |\n\nSince the learned distribution is a conditional distribution, analyzing it requires examining many distributions—one for each state-action pair—which makes it difficult to compare them and identify patterns. That said, we appreciate your suggestions.\n\n## Weakness-3: Distinct policies in experiments.\n\nIn Appendix E.2.4, we have included four pairs of target and behavior policies for each of the seven Atari games. These include epsilon values being 0.3 (target) and 0.8 (behavior) for the deterministic transition (Lines 1542-1548), or 0 (target) and 0.5 (behavior) for the random transition (Lines 1549-1554). Although the target and behavior policies are both epsilon-greedy variants for the same DQN-trained policy $\\pi_*$, \nthe differences between these epsilon values amount to 0.5, which is large enough to make the target and behavior policies distinct. For each target policy, we have tried two choices of epsilon values for the behavior policy (slightly larger and much larger epsilon than the epsilon value for the target policy), to empirically verify the effects of coverage constant (Assumption C.3). Indeed, larger epsilon value for the behavior policy leads to larger inaccuracy levels, since they represent weaker coverage. This can be seen by comparing Row 1 and Row 2, or comparing Row 3 and Row 4 of Figures 3, 4, and 5. \n\n## Weakness-4: Total coverage of all state-action pairs.\n\nThank you for your comment. In (P2), we made a mistake in our writing-the uniqueness is only required up to the support of $\\rho$ (i.e., almost everywhere w.r.t. $\\rho$). We will revise the paper accordingly. Therefore, the updated (P2) does not require total coverage of all state-action pairs. Without total coverage, we can still achieve the convergence in expectation-extended metrics in Section 3.2, i.e., Theorems C.4 and C.11.\n\n## Question-1: Why Gaussian mixture model?\n\nThe Gaussian mixture model (GMM) is mainly chosen as a flexible model given its ability to approximate smooth densities well with sufficiently large number of components. Since a key prior work FLE [1] also used GMM in their simulations, we simply adopt the same choice in our experiments. For our experiments, certain divergences (among the variations of our FDE method) and existing method (like FLE [1]) require existence of density, which is conveniently satisfied by the use of GMM.\n\n## Question-2: Typos\n\nThank you for your careful reading. We will fix them. \n\n## References\n\n[1] Wu et al. Distributional offline policy evaluation with predictive error guarantees. ICML. 2023."}, {"review_id": "gzjpgr42pC", "reviewer": "Reviewer_HoeH", "summary": "This paper focuses on the fitted distributional evaluation setting in distributional RL. They propose general approaches, fitted distributional evaluation, which aim to be a class of evaluation method and thus unify many existing approahces. Convergece guarantees are provided under different specification of the proposed framework, also ranging from tabular to non-tabular. Extensive experiments are conducted to support their theoretical claims.", "questions": "Does the theory work in undiscounted finite horizon setting? My take is that discounting has been important in the analysis because contraction is heavily used.", "limitations": "Limitations are discussed in the last section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper looks at distributional evaluation from a very general perspective. It abstracts the discrepancy in Bellman error into Bregman divergences. By doing this it opens up a new class of algorithms for distributional evaluation.\n\nRegarding theory, I have not checked the proofs (since the paper comes with extremely long appendices), but all results intuitively make sense. One suggestion is to move some more general results back to the main contents. While Theorem 3.3 might be a bit straightforward as it might be based on point-wise concentration and a union bound since visitation lower bound $p_{min}$ is assumed, which is quite strong (apologies if I am wrong), it is dominated by the more off-policy Theorem C.4 in the appendix, which I find more  interesting. Hence I would suggest moving Theorem C.4 to the main content at least. Right now it looks like many interesting results are all in the appendix.\n\nExperiments support the theory by showing that  the proposed method performs well. One improvement could be to evaluate on multimodal distributions. Atari games are known have a single mode in return, which is a very special class of distributions though being common.", "was_revised": true, "final_justification": "I am keeping my positive score.", "rebuttal": "Thank you very much for your efforts. Below are our responses to the comments you provided.\n\n## Weakness-1: Moving general results to the main text.\n\nThank you for your suggestion. Due to the page limit, we summarize our result in Equation 12, which accommodates other statements (Theorems C.4, C.11).  Based on your comment, we plan to add more details (e.g., Theorem C.4) to the main text.\n\nHowever, we would like to clarify two points. First, $p_{min}>0$ is not a strong assumption for the error bound guarantee in sup-norm metric (more specificially, $\\eta_\\infty$) in Theorem 3.3, since it is a strong uniform guarantee on every single state-action pair. For finitely many state action pairs (i.e., tabular setting in Theorem 3.3), $p_{min}>0$ is satisfied as long as every state-action pair has positive probability to be observed, as also assumed in [1], [2], [3]. Second, Theorem C.4 does not dominate Theorem 3.3. Although Theorem C.4 can accommodate all the functional Bregman divergences that can be applied in Theorem 3.3 (i.e., squared IPS metrics introduced in Section 3.1), they demonstrate slower convergence rates. This is explained in Lines 315-316. Indeed, Theorem 3.3 is significant as this shows near-optimal convergence rate for several divergences in tabular setting. Prior to our work, there is only one existing work [1] that shows optimal convergence rate (in tabular setting). See discussion after Theorem 3.3.\n\n## Weakness-2: Multi-modal returns\n\nNote the return distributions depend on the choices of target policies. Moreover, we have also included experiments with modified environments with stochastic transitions (in addition to the original deterministic transitions), which obviously affect the shape of return distributions. Empirically, we observed examples that generate (marginal) return distributions that have multiple modes in our Atari game experiments.\n\n## Question-1: Finite horizontal setting\n\nOur statistical error bounds (Theorems 3.3, C.4, C.11) do not apply to the finite horizontal settings. For finite horizontal setting, the algorithm will need to be modified. See, e.g., Section 2.1 of [4]. Note that there would be a set of return distributions defined over time, which are characterized by a series of distributional Bellman equations (which is different from that of the infinite horizon). And such relationship would be used for the finite horizontal extension, instead of the fixed-point characterization in the infinite horizontal setup.\n\nYet, we believe that a key part of work still provides insight for the construction of such distributional extension of the FQE.\nBased on a similar argument for (P2) and in Section 2.4, functional Bregman divergences are still expected to be natural candidates for finite-horizon extension.\n\n## References\n\n[1] Peng et al. Statistical efficiency of distributional temporal difference learning. NeurlIPS. 2024. \n\n[2] Rowland et al. An analysis of quantile temporal-difference learning. JMLR. 2024. \n\n[3] Ma et al. Conservative offline distributional reinforcement learning. NeurlIPS. 2021. \n\n[4] Wu et al. Distributional offline policy evaluation with predictive error guarantees. ICML. 2023."}, {"review_id": "n6vqYsI5dU", "reviewer": "Reviewer_NswW", "summary": "This paper designs a framework for specifying offline distributional\npolicy evaluation algorithms: algorithms that estimate the distribution\nover returns achieved by a given policy based on a fixed dataset.\nParticularly, the paper demonstrates convergence results of their fitted\ndistributional policy evaluation meta-algorithm for a very broad family\nof objective / loss functions. The paper concludes with a demonstration\nof such methods evaluating return distributions in Atari, where the\nproposed methods achieve accurate return distribution predictions as\nmeasured by a Wasserstein metric.", "questions": "I split this section into two parts, namely \"critical questions\" and\n\"ancillary questions\". The former includes questions which may\ndirectly influence my score, and the latter includes questions for\nclarification / curiosity.\n\n\n## Critical Questions\n\n1.  I am having trouble understanding what $m$ is in section 3.1, or at\n    least what the IPS is that is being referred to. Outside of the MMD\n    (where the IPS is obvious), what are examples of these IPS? Can you\n    give explicit examples for e.g. KL divergence, or scoring rules\n    that you outlined earlier?\n2.  In Assumption 3.2, what is $\\eta$? I'm assuming it's some metric\n    over $\\mathcal{P}$, but how does this relate to, say, $\\mathfrak{d}$?\n3.  In the proof of Theorem 3.3, how did you arrive at equation (33)\n    from the line preceding it? How do you neglect the $\\bar{m}_{n, 1}$\n    term?\n4.  In the experimental section, it is not entirely clear how you're\n    measuring \"inaccuracy\". Upon reading the appendix, it says it is\n    averaging 1-Wasserstein distance estimates over 100 pre-sampled\n    state-action pairs. How did you sample these state-action pairs?\n\n\n## Ancillary Questions\n\n1.  In your definition of expectation extension of metrics, why do you\n    prohibit the \"$L^1$ version\"? In other words, why are all exponents\n    $2q$ and not $q$?", "limitations": "Limitations are addressed adequately.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\nThis paper takes a really deep dive into the convergence of fitted\ndistributional policy evaluation methods. The results extend to a\ntruly vast family of metric / loss functions, and analysis ranges from\ntabular to continuous state-action spaces. Additionally, the paper\ntreats the multidimensional reward setting, which has shown to be\nchallenging particularly in distributional RL.\nThe paper, while largely theoretical in nature, is nicely supplemented\nwith nontrivial experiments.\n\nI also really appreciated the sections in the appendix that explicitly\nstate the convergence rates for a wide variety of divergences explicitly.\n\n\n## Weaknesses\n\nAside from difficulties following the math due primarily to unclear\nnotation and undefined terms, the main criticism I have for this paper\nis that the motivation is not very strong.\nThis paper seems very clearly parallel to [1], effectively justifying\nthe use of alternative loss functions for their algorithm. It's not\nabundantly clear what this gets you. Reading over the paper, it looks\nlike:\n\n1.  [1] is restricted to reward functions with bounded range, unlike\n    this paper.\n2.  The convergence rates derived in this work are favorable to those\n    of [1] for certain divergences.\n3.  As per the introduction, \"A general guideline for selecting\n    appropriate discrepancy functions in FDE remains unclear, leaving\n    practitioners without systematic guidance for developing valid FQE\n    extensions tailored to their specific needs\". This feels fairly\n    unrelatable. Besides the points mentioned above, what are other\n    reasons why practitioners might feel inclined to deviate from [1]?\n\nTo be clear, I don't mean to suggest that this work has no value in\nlight of [1]; rather, I'm suggesting that the narrative could be\nimproved to make the value more clear.\n\nMoreover, while the paper is already dense and page limits exist, I\nstill believe this paper deferred *a lot* of material to the\nappendix. It would really be a stretch for a reader to understand the\npaper (even just the theorem *statements* and experiments) without\nreading the appendix.\n\nI mention in more detail some of the specific issues I had with\nfollowing certain parts of the proofs / math throughout the remainder of the review.\n\n\n## Minor Issues\n\n1.  On line 85, it says \"the Bellman operator is often unknown and so\n    **as** the evaluation of the RHS (1), rendering this approach\n    impractical\". There's a few issues here:\n    1.  There is a problem in the sentence at the \"**as**\", the sentence is\n        broken.\n    2.  $(\\mathcal{B}^\\pi)^\\infty Q_0$ doesn't really make sense. This\n        would be impossible to compute even if you know\n        $\\mathcal{B}^\\pi$ exactly and had an oracle for evaluating\n        it. The statement should really be $(\\mathcal{B}^\\pi)^k Q_0 \\to Q_\\pi$.\n    3.  When $\\mathcal{S}$ or $\\mathcal{A}$ are infinite, even with\n        perfect knowledge of the MDP parameters, $\\mathcal{B}^\\pi$ can\n        be intractable to compute.\n2.  On line 94, you define $(g\\_{r,\n       \\gamma})\\_\\\\#:\\mathcal{P}\\to\\mathcal{P}$ as the push-forward measure\n    of the function $g_{r, \\gamma}$. I've never seen the pushforward\n    defined this way before (e.g., defining the map $f_\\sharp$ on\n    measures), it's actually pretty clever. But then\n    $(g\\_{r,\\gamma})\\_\\\\#$ is technically not the push-forward measure\n    (rather, $(g\\_{r, \\gamma})\\_\\\\#\\Upsilon(s, a)$ is). Maybe \"push-forward map\" instead?\n3.  In the discussion starting on line 110, perhaps in Remark 2.1, the\n    work of [1] should be mentioned, it is indeed highly related to\n    what you're proposing here. You did cite this work elsewhere, but\n    it would help contextualize in this section how your proposal differs\n    from theirs. For instance, you compare to a method in Remark 2.1\n    that you claim is limited to tabular MDPs, but the method of [1]\n    has no such limitation.\n4.  The notation $\\tilde{\\eta}$ for a metric on\n    $\\mathcal{P}^{\\mathcal{S}\\times\\mathcal{A}}$ is really confusing,\n    since $\\eta$ is usually used to denote return distribution\n    functions (see e.g. 2, 3).\n5.  The term \"contractive metric\" is strange. It's not the metric\n    that's contractive, it's the operator.\n6.  In the discussion about MMD metrics in distributional RL on line\n    213, the work of [4] discusses a broader family of MMD kernels that\n    lead to contractive Bellman operators for multidimensional rewards.\n7.  In Figure 1, the axis labels / tick labels are much too small.\n\n\n## References\n\n1.  Wu, Uehara & Sun (2023) Distributional Offline Policy Evaluation with Predictive Error Guarantees, ICML.\n2.  Bellemare, Dabney & Munos (2017) A Distributional Perspective on Reinforcement Learning, ICML.\n3.  Bellemare, Dabney & Rowland (2023) Distributional Reinforcement Learning, The MIT Press.\n4.  Wiltzer, Farebrother & Gretton et al. (2024) Foundations of Multivariate Distributional Reinforcement Learning, NeurIPS.", "was_revised": true, "final_justification": "The authors' responses were satisfactory. I still maintain that the overall message could be strengthened and the motivation for the work is not especially strong, but I do appreciate the rigor and I think the distributional RL community are likely to find some of the results useful.", "rebuttal": "Thank you very much for your efforts. Please find our responses to your comments below.\n\n## Weakness-1: Motivation; Value in light of FLE [1]\n\nThank you for your question. As emphasized in Section 2.1, a central goal of this work is to explore how to choose $\\mathfrak{d}$ in order to develop a theoretically sound FDE method. Note that [1] focuses exclusively on the log-likelihood criterion (which is closely related to KL divergence), and it \\textit{does not provide direct insight} into this crucial question. To address it, we propose a theoretically motivated requirement for $\\mathfrak{d}$ and show that functional Bregman divergences naturally satisfy this requirement, making them compelling candidates (see Theorem 2.4).\n\nAt a high level, different divergences respond differently to deviation between $\\Upsilon$ and $\\Psi_\\pi$ (see Equation (5)), much like how various loss functions behave differently in empirical risk minimization. Therefore, the choice of divergence should be tailored to the specific problem at hand. Relying on a single divergence (such as KL) across all settings is unlikely to be optimal. In fact, there have been well-known criticism of KL divergence (e.g., unbounded divergence value, high sensitivity to the tails of distributions, necessity that one probability measure is absolutely continuous to the other, inability to consider closeness in outcome values), as discussed in [3], [4], [5]. Even in general statistical estimations, these limitations have motivated extensive research into alternative divergences beyond KL divergence [2].\n\nTo move toward a principled framework for choosing $\\mathfrak{d}$ in specific applications, we believe the first step is to identify what constitutes a valid candidate. To date, this question remains largely unaddressed in the literature, and only a few valid choices have been identified - let alone systematically compared. Our work makes substantial progress on this front. While comparative analyses of certain functional Bregman divergences do exist and may provide practical guidance, we acknowledge that our paper does not yet offer a comprehensive decision-making framework for selecting among them in practice. We believe further investigation is needed to better understand the trade-offs between different functional Bregman divergences in the context of distributional OPE. Besides, identifying less common functional Bregman divergences that may be especially useful for distributional OPE is also interesting (e.g., Hyvarinen divergence which performed well in Atari games; see Tables 5-32). We believe they are important directions for future research. We will revise the paper to more clearly communicate these motivations and contributions.\n\n## Weakness-2: Many materials in the appendix.\n\nOther reviewers have made some suggestions to improve the readability. We will revise the paper to address these comments. We plan to add more details (e.g., adding Theorem C.4 as suggested by Reviewer HoeH) to the main text. We also plan to add proof sketch/outline (as suggested by Reviewer vbgr). Besides, we will add a table of content in the supplementary material for easier navigation of the supplementary material.\n\n## Minor issues\n\nThank you very much for your suggestions and careful reading. Due to space limitation, we do not respond to them one by one. We will address these issues in the revised version.\n\n## Question-1: Examples of IPS metrics\n\nIn Section 3.1, the study is restricted to the case when the functional Bregman divergence is given as $\\mathfrak{d}=m^2$ for some IPS metric $m$ (i.e., there exists an IPS metric such that the divergence is the squared IPS metric), and Table 1 presents examples of the functional Bregman divergence that can be written as a squared form of an IPS metric (Definition C.13). We have listed three examples of IPS metric in Appendix C.5, along with their corresponding inner products. Note that KL divergence is not a squared IPS metric and so is not included in Table 1, and the result of Section 3.1 (Theorem 3.3) does not apply to KL divergence. We have proved the convergence of FDE based on KL divergence separately in other results (Corollary B.9). (See Lines 317-318.)\n\n## Question-2: Relationship between $\\eta$ and $\\mathfrak{d}$\n\n$\\eta$ is a probability metric over $\\mathcal{P}$, whose extension (either supremum-extension or expectation-extension of Equations 7 and 8) ensures that Bellman operator is a contraction (Definition 2.2). In our paper, we bound the inaccuracy of our estimation only based on the metric $\\eta$ that satisfies Definition 2.2 (see Theorems 3.3, C.4, C.11), by using an $\\mathfrak{d}$-based objective function (Equation 5). To successfully achieve this, we need a surrogate metric $m$ that links $\\mathfrak{d}$ and $\\eta$, which satisfies a series of properties (Assumption C.2 for Theorem C.4, Assumption C.9 for Theorem C.11) along with Assumption 3.2. Note that $m$ is used for quantifying the model complexity (see NS4 of Assumption C.2 and MS4 of Assumption C.9). One special case is using the divergence that has the form of $\\mathfrak{d}=m^2$ with $m$ being an IPS metric (Definition C.13), but our results are not limited to squared IPS metics (as mentioned in Lines 310-311, 805).\n\nWe remark that the divergence in Theorem C.11 requires Assumption C.9, not Assumption C.2. We will fix this typo.\n\n## Question-3: Clarification of a proof step\n\nThank you for your careful reading. In the line before Equation 33, there was a typo. $\\bar{m}_{n,1}$ should be replaced by its squared term. Then this solves the issue. As we mentioned in Line 1186, we can follow the logic of the proof for (14) to show the inequality. We will correct it in the revised version.\n\nBefore we procced, we would like to apologize for the typos listed above, which have caused unnecessary confusions. We will proofread the revised version carefully.\n\n## Question-4: Clarification of inaccuracy measure\n\nWe sampled 1000 state-action pairs from $d_\\pi$ (Line 1509) according to Algorithm 1 of [6] (which we will clarify in the revised version). Since sampling from $d_\\pi$ takes a long time for large $\\gamma$, we saved the samples for each game (namely, pre-sampled observations) so that we can re-use them whenever we measure inaccuracy. To further clarify, we are not averaging Wasserstein-1 metric values for each pre-sampled observations of state-action pairs. Instead, we are calculating a single Wasserstein-1 metric value between the $S,A$-marginalized distributions in Line 1507 (which is also used by [1]). If necessary, we shall elaborate the algorithmic details of calculating this quantity.\n\n## Ancillary Question 1: Can we adopt $L_1$ form of expectation-extension?\n\nNote that bounding $L_2$ version of expectation-extended metric (in the results of Theorems C.4, C.11) already implies bounding $L_1$ version of expectation-extended metric, by the fact that $L_1$ norm is bounded by $L_2$ norm for probability spaces.\n\nBut, as you mentioned, there is no need to exclude $L_1$ version of expectation-extension, which can also make the Bellman operator a contraction by the same proof structure based on Appendix C.3.1.\n\n## References\n\n[1] Wu et al. Distributional offline policy evaluation with predictive error guarantees. ICML. 2023.  \n\n[2] Gneiting et al. Strictly proper scoring rules, prediction, and estimation. JASA. 2007. \n\n[3] Korba et al. Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence. NeurlIPS. 2024. \n\n[4] Selten. Axiomatic characterization of the quadratic scoring rule. Experimental Economics 1.1. 1998. \n\n[5] Bellemare et al. The Cramer distance as a solution to biased wasserstein gradients. arXiv preprint. 2017. \n\n[6] Agarwal et al. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. JMLR. 2021."}, {"review_id": "f9rjYYNVr1", "reviewer": "Reviewer_vbgr", "summary": "The paper proposes Fitted Distributional Evaluation (FDE), a principled extension of fitted‑Q evaluation to distributional off‑policy evaluation.\nFirst, they choose a contractive metric for the distributional Bellman operator (Section 2.3).\nSecond they optimize a matching functional Bregman divergence (Section 2.4).\nThen they) prove that, under this metric‑loss link, the Bellman backup is the population minimiser (Theorem 2.4).\nStatistically, Theorem 3.3 yields near‑minimax sample‑complexity in the tabular case, while Tables 1 and 2 list many valid metric/divergence pairs—including new ones such as PDF‑L2 and MMD‑Coulomb—and extend guarantees to continuous state–action spaces (Theorems C.4/C.11). There are also some synthetic experiments on a linear‑quadratic regulator (LQR) and seven Atari games show FDE variants (KL, Energy, PDF‑L2, RBF) reducing mean Wasserstein‑1 error compared with FLE, QR‑DQN, IQN, and a TV‑distance baseline (Figure 1).", "questions": "1. What happens when Assumption 3.1 fails? Can you provide a bound with an inherent Bellman‑approximation term or show an empirical study? \n2. Could uniform‑stability or mixing arguments allow reuse of the full dataset instead of the per‑iteration split? \n3. Which theorem, beyond Corollary B.9, ensures convergence for KL, given that Section 2.4 says the main framework excludes it?", "limitations": "The authors acknowledge strong assumptions (completeness, data splitting, contractive metrics). Experiments also omit high‑dimensional continuous‑control domains.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths:\n1. The three‑principle recipe clearly explains why certain popular distances (for example, total variation) fail and how to build safe objectives.\n2. The finite‑sample analysis is tight: Theorem 3.3 matches known lower bounds for W1 in tabular MDPs and the appendix extends the result to non‑tabular settings.\n3. Empirical results, though compact, are consistent with the theory and illustrate the failure of TV distance.\n\n## Weaknesses:\n1. Assumption 3.1 (completeness) is strong and rarely satisfied in deep RL; the analysis also relies on splitting the dataset across iterations (Equation 10), which hurts sample efficiency.\n2. Section 2.4 states that the metric‑loss link does not accommodate KL divergence, yet KL is used in experiments; only Corollary B.9 in the appendix gives a guarantee, so the main text feels incomplete.\n3. Experiments cover only one continuous‑control task and seven Atari games, with no statistical tests or hyper‑parameter ablations.\n4. Dense notation and appendix‑only proofs (for example, the entire proof of Theorem 3.3) make the paper hard to digest. Especially since the appendix is more than 50 pages. I would suggest condensing the paper significantly and providing proof sketches in the main text.", "was_revised": true, "final_justification": "The paper proposes a unified framework for distributional FQE which yields some improvements over prior FQE in theory and practice. The analysis appears fairly standard but should be valuable to the community nonetheless.", "rebuttal": "Thank you very much for your efforts. Please find our responses to your comments below.\n\n## Weakness-1, Question-1,2: Relaxing the strong assumptions\n\nWe acknowledge that both completeness (Assumption 3.1) and data splitting are limitations of the current work. While these are substantial directions that cannot be handled by the current work, we agree these limitations are worthy to be addressed. However, it is also true that these are standard limitations of many iteration-based RL algorithms. Many papers assume completeness (e.g., papers listed in Lines 247-248) and adopt similar strategies to data splitting or equivalently fresh samples in each iteration (e.g., [1], [2]) for theoretical convenience.\n\nAnswer to your Question 1: When Assumption 3.1 (Bellman completeness) fails, we will have a non-negligible approximation error, similar to FQE,  at each iteration of our proposed FDE algorithm. Such an approximation error can be quantified by inherent distributional Bellman error, which can be similarly defined by adapting from the standard notion in FQE. See [3] and [4] for more details. \n\nAnswer to your Question 2: Thanks for your suggestions. Due to the general choice of functional Bregman divergences, conducting a systematic study of the dependence across iterations—and thereby understanding the mixing properties—is nontrivial. To sidestep the complexities of this dependence, one possible alternative is to explore uniform convergence. However, we have not pursued these directions rigorously and therefore prefer not to make any speculative claims.\n\n## Weakness-2, Question-3: KL divergence can be accommodated in Section 2.4.\n\nWe believe there is misunderstanding. KL divergence is a functional Bregman divergence, and so Theorem 2.4 of Section 2.4 covers KL divergence. See our discussion in Lines 212-214. Therefore, KL divergence is included in our main framework of FDE. However, when it comes to obtaining statistical error bound in Section 3, we need a separate theoretical analysis for KL divergence. We proved the convergence of our FDE based on KL divergence in Corollary B.9.\n\n## Weakness-3: Statistical tests and hyperparameter ablations\n\nWe have provided standard deviations (Atari games in Figures 1, 3-5) and error bars (LQR simulations in Figure 2) for the numerical results that allow assess for statistical significance. As for hyperparameter ablations, we indeed have varied the model complexity (the number of Gaussian mixture components as detailed in Appendix E.2.1.). For the experimental setups, we have included two levels of epsilon values for behavior policies (representing weak and strong satisfaction of Assumption C.3) and two different transitions (random and deterministic). Since we evaluated 7 Atari games, our experimental setup therefore includes $2$ (behavior policies) $\\times$ $2$ (transitions) $\\times$ $7$ (Atari games) $=28$ configurations. Each was tested with three levels of model complexity ($M=10,100,200$; see Lines 1490-1491), resulting in a substantial number of experiments. The outcomes are visualized in Figures 3-5. We believe this comprehensive evaluation sufficiently demonstrates our main conclusion that the methods developed within our framework are working.\n\n## Weakness-4: Proofs are all in Appendix.\n\nThank you for your suggestion. Based on your comment, we will add proof sketch/outline. Moreover, we will add a table of content in the supplementary material for easier navigation of the supplementary material.\n\n## References\n\n[1] Peng et al. Statistical efficiency of distributional temporal difference learning. NeurlIPS. 2024. \n\n[2] Wu et al. Distributional offline policy evaluation with predictive error guarantees. ICML. 2023.  \n\n[3] Duan et al. Risk bounds and rademacher complexity in batch reinforcement learning. ICML. 2021. \n\n[4] Golowich et al. The role of inherent bellman error in offline reinforcement learning with linear function approximation. arXiv preprint. 2024."}]

Author rebuttal:

Meta-review: The paper considers off policy evaluation for distributional RL, extending fitted Q evaluation (FQE) to the distributional setting. The authors unify treatments of distributional FQE and allows analysis under a range of discrepancy functions and general conditions including infinite spaces. The authors analyze valid discrepancy functions, introducing novel examples, and present convergence results for tabular and non-tabular settings. Empirical evaluations are conducted for linear quadratic regulator (LQR) and Atari games. 

Strengths of the paper include the detailed theoretical analysis, and the nice discussion of limitations. One reviewer also noted explicit convergences rates in the appendices. Weaknesses of the paper noted by reviewers include the density of the exposition, and the clarity of positioning with respect to the literature. Reviewers were by and large satisfied with responses to concerns about density. The question of clarity of contribution were not completely resolved, but the reviewer was nevertheless positive about the paper. 

Given that reviewers were uniformly positive about the contribution of this work, I recommend acceptance.
Decision: Accept (spotlight)