Beyond Average Return in Markov Decision Processes
Authors: Alexandre Marthe
Aurélien Garivier
Claire Vernade
Venue: NeurIPS 2023 poster (2023)
Keywords: Markov Decision Process
Dynamic Programming
statistical functionnals
Distributionnal Reinforcement Learning
Policy Evaluation
Planning

Abstract: What are the functionals of the reward that can be computed and optimized exactly in Markov Decision Processes?
In the finite-horizon, undiscounted setting, Dynamic Programming (DP) can only handle these operations efficiently for certain classes of statistics. We summarize the characterization of these classes for policy evaluation, and give a new answer for the planning problem. Interestingly, we prove that only generalized means can be optimized exactly, even in the more general framework of Distributional Reinforcement Learning (DistRL).
DistRL permits, however, to evaluate other functionals approximately. We provide error bounds on the resulting estimators, and discuss the potential of this approach as well as its limitations.
These results contribute to advancing the theory of Markov Decision Processes by examining overall characteristics of the return, and particularly risk-conscious strategies.

Beyond Average Return in Markov Decision Processes
Alexandre Marthe
Aurelien Garivier UMPA UMR 5669 and LIP UMR 5668 Univ. Lyon, ENS de Lyon
UMPA
ENS de Lyon
Lyon, France
allée d'Italie F-69364 Lyon cedex 07, France
alexandre -yyon.
aurelien, har.iim..grii.eereo--ooo.......
Claire Vernade
University of Tuebingen
Tuebingen, Germany
claire. claire. www.eaaddeei--uuuuieeeeeee
Abstract
What are the functionals of the reward that can be computed and optimized exactly in Markov Decision Processes? In the finite- mnite-horizon, undiscounted setting, Dy- namic Programming (DP) can only handle these operations efficiently for certain classes of statistics. We summarize the characterization of these classes for policy evaluation, and give new answer for the planning problem. Interestingly, we prove that only generalized means can be optimized exactly, even in the more general framework Distributional Reinforcement Learning (DistRL). DistRL permits, however, to evaluate other functionals approximately. We provide error bounds on the resulting estimators, and discuss the potential of this approach as well as its limitations. These results contribute to advancing the theory of Markov Deci- sion Processes by examining overall characteristics of the return, and particularly risk-conscious strategies.
Introduction
Reinforcement Learning (RL) has emerged as a flourishing field of study, delivering significant prac- tical applications ranging from robot control and game solving drug discovery hardware design [Lazic et al., 2018, Popova et al., 2018, Volk et al., 2023, Mirhoseini et al., 2020]. The cornerstone of RL the "return" value, sum of successive rewards. Conventionally, the focus is on computing and optimizing its expected value on Markov Decision Process (MDP). The remarkable efficiency of MDPs comes from their ability be solved through dynamic programming with the Bellman equations [Sutton and Barto, 2018, Szepesvári, 2010]. RL theory has seen considerable expansion, with a renewed interest for the consideration of more rich descriptions of policy's 's behavior than the sole average return. At the other end of the spectrum, the so-called Distributional Reinforcement Learning (DistRL) approach aims studying and optimizing the entire return distribution, leading to impressive practical results [Bellemare et al., 2017, Hessel et al., 2018, Wurman et al., 2022, Fawzi al., 2022]. Between the expectation and the entire distribution, the efficient handling of other statistical functionals of the reward appears also particularly relevant for risk-sensitive contexts [Bernhard et al., 2019, Mowbray et al., 2022].
Despite recent progress, the full understanding of the abilities and limitations of DistRL to compute other functionals remains incomplete, with the underlying theory yet be fully understood. His- torically, the theory of RL has been established for discounted MDPs, see e.g. [Sutton and Barto, 2018, Watkins and Dayan, 1992, Szepesvári, 2010, Bellemare al., 2023] for modern reference textbooks. Recently more attention was drawn to the undiscounted, finite-horis moite-horizon setting [Auer, 2002,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Osband et al., 2013, Jin et al., 2018, Ghavamzadeh et al., 2020], for which fundamental questions remain open. In this paper, we explore policy evaluation, planning and exact learning algorithms for undiscounted MDPs for the optimization problem of general functionals of the reward. We explicitly delimit the possibilities offered by dynamic programming as well as DistRI..
Our paper specifically addresses two questions:
(i) How accurately can we evaluate statistical functionals by using DistRL?
(ii) Which functionals can be exactly optimized through dynamic programming?
We first recall the fundamental results in dynamic programming and Distributional RL. Addressing question (i), we refer to Rowland et al. [2019]'s results on Bellman closedness and provide their adaptation undiscounted MDPs. We then prove upper bounds on the approximation error of Policy Evaluation with DistRL and corroborate these bounds with practical experiments. For question (ii), we draw connection between Bellman closedness and planning. We then utilize the DistRL framework to identify two key properties held by optimizable functionals.
Our main contribution is characterization of the families of utilities that verify these two properties (Theorem 2). This result gives a comprehensive answer to question (ii) and closes an important open issue in the theory of MDP. It shows in particular that DistRL does extend the class of functionals for which planing is possible beyond what is already allowed by classical dynamic programming.
2 Background
We introduce the classical RL framework in finite-horizon tabular Markov Decisions Processes (MDPs). We write P (IR) the space of probability distributions R. A finite-horizon tabular MDP is tuple M A R. H), where X' is finite state space, A is a finite action space, H is the horizon, for each h E [H], Ph (xr, a, :) is transition probability law and Ra a) is reward random variable with distribution @h- The parameters (Px) and (Ra) define the model of dynamics. A.
deterministic policy on M sequence π (TI...., HH) of functions TT,
Reinforcement Learning traditionally focuses on learning policies optimizing the expected return. For given policy x, the Q-function maps state-action pair its expected return under
(T( a) Eee, [Ra (xx a' (f (x)))
(0) = (1)
When the model known, the Q-function of a policy can be computed by doing a backward recursion, also called dynamic programming. This is referred to as Policy Evaluation. Similarly, an optimal policy can be found by solving the optimal Bellman equation:
Q7 a) = En, [RA(I, ax) + Epn(a a, x') max Qh+1(1' ,'),
az) =0. (2)
Solving this equation when the model is known is also called Planning. When is unknown, reinforcement learning aims at finding the optimal policy from sample runs of the MDP. But evaluating and optimizing the expectation of the return in the definition of the Q-function above is just one choice of statistical functional. We now introduce Distributional RL and then discuss other statistical functionals that generalize the expected setting discussed so far.
2.1 Distributional RL
Distributional RL (DistRL) refers to the approach that tracks not just statistic of the return for each state but its entire distribution. We introduce here the most important basic concepts and refer the reader to the recent comprehensive survey by Bellemare al. [2023] for more details. The main idea is to use the full distributions to estimate and optimize various metrics over the returns ranging from the mere expectation [Bellemare et al., 2017] to more complex metrics [Rowland al., 2019, Dabney et al., 2018a, Liang and Luo, 2022].

---

At state-action (a, a), let Z (z. a) denote the future sum of rewards when following policy и and starting at step h, also called return. verifies the simple recursive formula 2 (a, a) R, (z, a) t (X', *x+1(X')) where X' ~ Ph+1 (I, .). Its distribution is 1 (17) (x,,))) and often referred to as the Q-value distribution. One can easily derive the recursive law of the return as a convolution: for any two measures Vi E (R)), we denote their convolution by Vi 12 (t) = JR 21 (T))(t - T)dT. For any two independent random variables X and Y, the distribution of the sum Z X + Y is the convolution of their distributions: vz Vx vy. Thus, the law of (x, a)
Vx, a, h, (2, (n) a''
(x', mxt1(1e))
This equation is a distributional equivalent to Eq. (1) and thus defines distributional Bellman operator 1ij = = 1
Obviously, from practical point of view, distributions form non-parametric family that is computationally tractable. It is necessary to choose a parametric (thus incomplete) family to represent them. Even the restriction discrete reward distributions not tractable, since the number of atoms in the distributions may grow exponentially with the number of steps' [Achab and Neu, 2021]: approximations are unavoidable. The most natural solution to use projections of the obtained distribution on the parametric family, at each step of the Bellman operator. This process is called parameterization. The practical equivalent Eq. (1) in DistRL hence writes
Yx, a, h, (2, a) = -11 (z) En a. M' mmna(e")))
(4)
where II is the projector operator on the parametric family, The full policy evaluation algorithm in DistRL is summarized in A.g.1.
Algorithm 1 Policy Evaluation (Dynamic Programming) for Distributional RL
Input: model p. reward distributions 2h. policy to evaluated, II projection.
Data: 1) E IR ((]]AA/
Va, E X' x A,
Th (z, a) 0 60 0 do
for H
Tn (I, a) en (z, a) # Σx Pnla,, a, a, 1'4) (r',Ta+1(1)) ax My (I, a) 11 (n (I, a))
Vx, E X x x
end for
Output: Th (I, a)Vx, a,
Distribution Parametrization The most commonly used parametrization is the so-called quantile projection. It put Diracs (atoms) with fixed weights at locations that correspond to the quantiles the source distribution. One main benefit is that it does not require previous knowledge of the support of the distribution, and allows for unbounded distributions.
The quantile projection is defined as
N-1
1Q
Σ 8Z., with (z)); chosen such as Fz(2;) N 2=0
1
2i +
(5)
2N
which corresponds to minimal W, distance: TQи E arg min S W (p, (i), where (.....) is the Wasserstein distance defined for any distributions V1, as W (vi, v2) = fo (w) du. Note that this parametrization might admit several solutions and thus the projection may not be unique. For simplicity, we overload the notation to IQ = (Ion((,, ())
'The support of the return (sum of the rewards) is incremented at each step by a number of atoms that depend the current support.
3

---

For a Q-value distribution with support of length Ay, and parametrization of resolution N, Rowland al. [2019] prove that the projection error is bounded by
A 2N
Wi (I( S (xxa)XXA
sup
(6)
In Section 3, we extend this result to the full iterative Policy Evaluation process and bound the error on the returned statistical functional in the finite-horizon setting. Note that other studied parametrizations exist but are less practical. For completeness, we discuss the Categorical Projection [Bellemare et al., 2017]]Rowland al., 2018 2Bellleeee et al., 2023] in Appendix B.
2.2 Beyond expected returns
The expected value is an important functional a probability distribution, but it is not the only one of interest in decision theory especially when control of the risk is important. We discuss two concepts that have received considerable attention: utilities, defined as expected values of functions of the return, and distorted means which place emphasis certain quantiles.
Expected Utilities are of the form (Z), or J f dv, where the return of distribution v and is an increasing function. For instance, when is power function, we obtain the different moments of the return. The case of exponential functions plays a particularly important role: the resulting utility is referred to exponential utility, exponential risk measure, or generalized mean according to the context:
1
(nx - log E exp(AX)] X and X E R.
This family of utilities has variety of applications in finance, economics, and decision making under uncertainty [Föllmer and Schied, 2016]. They can be considered as a risk-aware generalization of the expectation, with benefits such as accommodating a wide range of behaviors [Shen et al., 2014] from risk-secking when À > 0, to risk-averse when À < 0 (the limit À + 0 is exactly the expectation). To fix ideas, Uxxp(NVL o²)) = a + Ao²: each captures a certain quantile of the Gaussian distribution.
Distorted means, on the other hand, involve taking the mean of random variable, but with different weighting scheme [Dabney et al., 2018a]. The goal is to place more emphasis on certain quantiles, which can achieved by considering the quantile function F-1 of the random variable and a continuous increasing function 8: [0. 1] + [0. 1]. By applying B to uniform variable on [0, 1] and evaluating F-1 at the resulting value (()). we obtain a new random variable that takes the same values as the original variable, but with different probabilities. The distorted mean is then calculated as the mean this new random variable, given by the formula ( If B is the identity function, the result is the classical mean. When 3 is + min(r /a, 1), we get the a-Conditional Value at Risk (CVaR(a)) (a)) of the return, a risk measure widely used risk evaluation [Rockafellar al., 2000].
3 Policy Evaluation
The theory of MDPs is particularly developed for estimating and optimizing the mean of the return of a policy. But other values associated the return can be computed the same way, by dynamic programming. This includes for instance the variance of the return, or more generally, any moment of order p 2 2, as was already noticed in the 1980's [Sobel, 1982]. Recently, Rowland et al. [2019] showed that for utilities in discounted MDPs, this is essentially all that can be done. More precisely. they introduce the notion Bellman closedness (recalled below for completeness) that characterizes a finite set of statistics that can efficiently be computed by dynamic programming.
Definition 1 (Bellman closedness [Rowland et al., 2019]). A set of statistical functionals functtionl {si,.... .sk.... said to be Bellman closed if for each (a, a) E X x A, the statistics $1.K T (x, a)) can be expressed in closed form in terms of the random variables Rd, (z, a) and (S1.k (T (X', A')), A' (2), X' ~ Phe (z, A', independently of the MDP.
Importantly, in the undiscounted setting, Rowland et al. [2019] (Appendix B, Theorem 4.3) show that the only families of utilities that are Bellman closed are of the form {x ++ xf exp(A>)]00 - l L}

---

for some L < co. Thus, all utilities and statistics of the form of (or linear combinations of) moments and exponential utilities can easily be computed by classic linear dynamic programming and do not require distributional RI. (see Appendix A.3).
Some important metrics such the CVaR or the quantiles are not known belong any Bellman- closed set and hence cannot be easily computed. For this kind of function of the return, the knowledge of the transitions and the values following steps is insufficient to compute the value on a specific step. In general, it requires the knowledge of the whole distribution of each reward in each state. Hence, techniques developed in distributional RL come in handy: for a choice of parametrization. one can use the projected dynamic programming step Eq. (4) to propagate a finite set of values along the MDP and approximate the distribution of the return. In the episodic setting, following the line of Rowland et al. [2019] (see (6)) we prove that the Wasserstein distance error between the exact and approximate distribution of the Q-values of a policy bounded.
Proposition 1. Let t. be policy and nn the associated Q-value distributions. Assume the return is bounded on a interval of length A, S HHAn n. where An is the support size of the reward distribution. Let of be the Q-value distributions obtained by dynamic programming (Algorithm 1) using the quantile projection IQ with resolution N. Then,
AR 2N
sup (..O,))
W (x)
H
2N
This result shows that the loss of information due to the parametrization may only grow quadraticly with the horizon. The proof consists of summing the projection bound in (6) at each projection step, and using the non-cxxansion property of the Bellman operator [Bellemare et al., 2017]. The details can be found in Appendix C
The key question then to understand how such error translates into our estimation problem when we apply the function of interest to the approximate distribution. We provide a first bound on this error for the family of statistics that are either utilities or distorted means.
First, we prove that the utility is Lipschitz on the set of return distributions.
Lemma 1. Let s be either an utility or a distorted mean and let L be the Lipschitz coefficient of its characteristic function. Let vi, V2 be return distributions. Then:
[s(v1) - s(12)) I (WI
Both family of functionals are treated separately, but lays similar bound. The utility bound is the direct application of the Cewooovvicch-uuenstteie duality, while the distorted mean one is direct majoration in the integral. Again, the details are provided in the Appendix.
This property allows
prove a maximal upper bound the estimation error for those two families.
Theorem 1. Let a be policy. Let n7 be the Q-value return distribution associated to with the return bounded on a interval of length Σ. S HAR where AR is the support size of the reward distribution. Let if be the approximated return distribution computed with Algorithm 1, for the projection II with resolution N. Let be either an expected utility or a distorted mean, and the Lipschitz coefficient of its characteristic function. Then:
AR 2N
sup (s( a)) =(1 (z, a))l S LH a,a.k
2H
2N
Note that depending on the choice of utilities, the Lipschitz coefficient L may also depend on H and AR. For instance, in a stationary MDP, the Lipschitz constant of the exponential utility depends exponentially on A,, For the CVaR(a), however, L is constant and only depends on a E (0. 1).
Experiment: empirical validation of the bounds on a simple MDP We consider a simple Chain MDP environment of length H 70 equal the horizon (see Figure (right)) [Rowland et al., 2019]. with single action leading to the same discrete reward distribution for every step. We consider Bernouilli reward distribution ((0.5) for each state so that the number of atoms for the return only grows linearly² with the number of steps, which allows to compute the exact distribution easily.
At round [H], the support of the return is (0, 1, ..., h.), so l atoms.
5

---

R 2h e
R 2h =
1
h
H
vh [H, p(h 1|,, 1)
=1
Figure 1: A Chain MDP of length H with deterministic transition and identical reward distribution for each state.
CV. error
Wasserstein distance
Approximation Error
Scaled CVaR(0.1) I) bound
1.5
Cumulative Projection Error
(V.R(0025)) error
Theoretical Error bound
Error
Scaled (V.R(0 bound
1.0
Timestep h
Timestep h
Figure 2: Left: Validation of Theorem on C() together with the scaled upper bound (see main text for discussion): the quadratic dependence in H is verified. Right: Validation of Proposition 1: The cumulative projection error (dashed blue) is the sum of the projection errors at every time step, and matches the true approximation error (solid blue). The theoretical upper bound (dashed red) differs only by a factor
We compare the distributions obtained with exact dynamic programming and the approximate distribution obtained by Alg 1, with a quantile projection with resolution N 1000. Note that even early stages, when the true distribution has less atoms than the resolution, the exact and approximate distributions differ due to the weights of the atoms in the quantile projection. Figure 2 (Right) reports the Wasserstein distance between the two distributions: the cumulative projection approximation error (dashed blue), the true error between the current exact and approximate distributions (solid blue) and the theoretical bound (red). Fundamentally, the proof of Prop. upper bounds the distance between distributions by the cumulative projection eтrоr so we plot this quantity to help validating it.
We also empirically validate Theorem by computing the CVaR(a) for {0.1, 0.25). correspond- ing respectively to distorted means with Lipschitz constants (10,4) 4). We compute these statistics for both distributions and report the maximal error together with the theoretical bound, re-scaled by a factor 5. Figure 2 (Left) shows an impressive correspondence of the theory and the empirical results despite constant multiplicative gap.
Planning
Planning refers the problem of returning a policy that optimizes objective for given model and reward function (or distribution in DistRI.). It shares with policy evaluation the property to be grounded Bellman equation: Eq. (2) for the classical expected return, which leads to efficient computations by dynamic programming.
For other statistical functionals of the cumulated reward, however, can the optimal policy be computed efficiently? The main result of this section characterizes the family of functionals that can be exactly and efficiently optimized by Dynamic Programming.
In the previous section, we recalled that celman--clssed sets of utilities can be efficiently computed by DP as long as all the values of the utilities in the Bellman-closed family are computed together. For the planning problem, however, we only want to optimize one utility so we cannot consider families as previously. Under this constraint, only exponential and linear expected utilities are Bellman closed and thus can verify Bellman Equation. In fact, for the exponential utilities, such Bellman Equation
Scaling constant factor allows show the corresponding quadratic trends.

---

exists and allows for the planning problem to be solved efficiently [Howard and Matheson, 1972]:
Ch( a) a)= = U (R, a)) + log (m((,,a, exp (A max (ieil(',
(8)
with (2+
However, the question of the existence of Optimal Bellman Equations for non-utility functionals remains open (e.g. quantiles). More generally, efficient planning strategy is known. To address these questions, we consider the most general framework, DistRL, and recall the theoretical DP equations for any statistical functional comprehensive, or 'lossless', approach, so if statistical functional cannot be optimized with Alg. 2, then there cannot exist a Bellman Operator to perform exact planning.
the Pseudo--Alge Algorithh 2. DistRL offers the most
Algorithm 2 Pseudo-Algorithe Exact Planning with Distributional RL
Input: model p. reward R. statistical functional 8
2: Data: E A|AAANNN V E IR N
3: Va X, VH-1
50
4: for h = H + do
5:
"/ (I, a) = Cn
(.,a)
Vx, Vx A a' arg max, (z, Ve X
Ent Ph (1, x')
6:
V Th (1,
7: end for
8: Output: nn (2, a) Yx, a,
We formalize this idea with the new concept of Bellman Optimizable statistical functionals: Definition 2 (Bellman Optimizable statistical functional), statistical functional is called Bellman optimizable if. for any MDP M, the Pseudo-Algoridmm 2 outputs an optimal return distribution 7 1/² that verifies:
Vx, a, h,
a)) sup = = (x)
Remark. This definition equivalent the satisfaction of an Optimal Distributionnal Bellman equa- tion. Indeed. a statistical functional s is Bellman Optimizable if and only if. for any (X.A, m1)
verifies
@* Epla')no'' = =<@e<nnte)mee,
sup ad
with at E arg max, ((1(x, a))
We can now state our main results that characterizes all the Bellman optimizable statistical functionals. First, we prove that such functional must satisfy two important properties.
Lemma 2. A Bellman optimizable functional satifies the two following properties:
Independence Property: If V1, 12 E (RR are such that s(v1) 2 s(v2). then
Vug E (B), [0, 1], s(Ner + (1 (1 Ajus) 2 s(N02 + (1 - A)uz))
Translation Property: Let denote the translation on the set of distributions: T.d = Extc- Vf V2 E (R) are such that s(v1) 2 s(v2), then
Vc E R. s(T.M) 2 S(T,V2)
Indeed, the expectation and the exponential utility both satisfy these properties (see Appendix A.2). Each property is implied by aspect of the Distributional Bellman Equation (Alg. 2, line 5) and the proof (in Appendix E) unveils these important consequences of the recursion identities.
'This theoretical algorithm bandles the full distribution of the return at each step. which cannot be done in practice.

---

Fundamentally, they follow from the Markovian nature of policies optimized this way: the choice of the action in each state should be independent of other states and rely only on the knowledge of the next-state value distribution.
The Independence property states that, for Bellman optimizable functionals, the value of each next state should not depend on that of any other value in the convex combination in the rightmost term of the convolution. In turn, the Translation property is associated to the leftmost term, the reward, and imposes that, for Bellman optimizable functionals, the decision on the best action is independent of the previously accumulated reward.
The Independence property is related to expected utilities [von Neumann et al., 1944]. Any expected utility verifies this property (Appendix A.2) but, most importantly, the Expected Utility Theorem (also known as the Von Neumann Morgenstein theorem) implies that any continuous statistical functional verifying the Independence property can be reduced to an expected utility. This means that for any such statistical functional s, there exists f continuous such that Vun, V2 E (RR), we have s(11)= s(12) + (M( > Uy(12) [von Neumann al., 1944, Grandmont, 1972].
This result directly narrows down the family of Bellman optimizable functionals to utilities. Indeed, although other functionals might potentially be optimized using the Bellman equation, addressing the problem on utilities is adequate to characterize all possible behaviors. For instance, moment- optimal policies that can be found through dynamic programming, can also be found by optimizing an exponential utility function. The next task is therefore to identify all the utilities that satisfy the second property. We demonstrate that, apart from the mean and exponential utilities, no other Wi-continuous functional satisfies this property.
Theorem 2.
Let g be a return distribution. The only W1-continuous Bellman Optimizable statistical functionals of the cumulated return are exponential utilities Uexp(e) 2x log Eg [exp(AR)] for E IR, with the special case of the expectation Eg [R] when À =
Of course, if (p) is utility and s is a monotonous scalar mapping, (p) is an equivalent utility: one should understand in the previous theorem that a Wy-continuous Bellman Optimizable statistical functional is equivalent Uexp (e) for some À E R. We chose here define Uexp (e) log Egg [exp(XRt) with the log and the factor 1/ À since it results in normalized utility that tends to the expectation when À goes to O. The full proof of Theorem 2 is provided in Appendix E.
We make few important observations. First, this result shows that algorithms using Bellman updates to optimize any continuous functionals other than the exponential utility cannot guarantee optimality. The theorem does not apply to non-continuous functionals, but Lemma 2 still does. For instance, the quantiles are not W1 Wi-continuous so Theorem 2 does not apply, but it is easy to prove that they do not verify the Independence Property and thus are not Bellman Optimizable. Also, there might also exist other optimizable functionals, like moments, but they must first be reduced to exponential or linear utilities.
Most importantly, while in theory, DistRL provides the most general framework for optimizing policies via dynamic programming, our result shows that in fact, the only utilities that can be exactly and efficiently optimized do not require to resort to DistLL. This certainly does not question the very purpose of DistRL, which has been shown to play important roles in practice to regularize or stabilize policies and to perform deeper exploration [Bellemare et al., 2017, Hessel et al., 201 8). Some advantages of learning the distribution lies in the enhanced robustness offered in the richer information learned [Rowland et al., 2023], particularly when utilizing neural networks for function approximation [Dabney et al., 2018b, Barth-Maron et al., 2018, Lyle et al., 2019].
5 Q-Learning Exponential Utilities
The previous sections consider the the model, i.e. the reward and transition functions, be known. Yet in most practical situations, those are either approximated or learnt'. After addressing policy evaluation (Section 3) and planning (Section 4), we conclude here the argument of this paper by addressing the question of learning the statistical functionals of Theorem 2. In fact, we simply highlight lesser known version of Q-Leaniing Watkins and Dayan [1992] that extend this celebrated algorithm to exponential utilities. We provide the pseudo-code for the algorithm proposed by Borkar
Either explicitly (model-based RL) implicitly (model-free RL, considered here).
8

---

Algorithm 3 Q-Learning for Linear and Exponential Utilities
Input: (at) transition and reward generator. Qx a) V(z,ah) Ax
2: Utilities: Linear (Z + XZ + b) or Exponential (Z + log (x{{Exx(AZ)))
3: for episode K 1..... K do
4: Observe
X
5: for stepte 1...., H do
6:
Choose action da E arg aa Qn (TA,,)) a)
7:
Observe reward ra and transition 2h+1 and update for chosen objective:
8:
Linear Util.: (T as) + (1 an pn)Qa(T an) + ax (A(n + max Qu+1 d')) +
9:
Exponential Util.: Qu an) 1 log (1 (1- 2 (s(ioo)) + aae tmax, (4 11
10:
end for
end for
12:
Output: Qn a
[2002, 2010] with the relevant utility-based updates in Alg. 3. We refer to these seminal works for convergence proofs. Linear utility updates (line 8) differ only slightly from classical ones for expected return optimization, which have been shown to lead to the optimal value asymptotically [Watkins and Dayan, 1992].
6 Discussions and Related Work
The Discounted Framework We focused in this article on undiscounted MDPs, and is important note that the results differ for discounted scenarios. The crucial difference is that the family of exponential utilities no longer retains Bellman Closed or Bellman Optimizable properties due to the introduction of the discount factor y [Rowland al., 2019]. When it comes to Bellman Optimization, the necessary translation property becomes an affine property Ve, s(T,11)) > s(T3112) where +ß dyz+e- This property not upheld by the exponential utility.
the affine operator such that = Nonetheless, there exists method to optimize the exponential utility through dynamic programming in discounted MDPs [Chung and Sobel, 1987]. This approach requires modifying the functional to optimize at each step (the step h is optimized with the utility + exp(y >> > x:) x)), but it also implies loss of policy stationarity, property usually obtained in dynamic programming for discounted finite-horizon MDPs [Sutton and Barto, 2018].
Utilizing functionals to optimize expected return. DistRL has also been used in Deep Reinforce- ment learning to optimize Han-Bellman-optimize
functionals such as distorted means[Ma et al., 2020, Dabney et al., 2018a]. While, as we proved so, such algorithms cannot lead to optimal policies in terms of these functionals, experiments show that in some contexts they can lead to better expected return and faster convergence in practice. The change of functional can be interpreted the exploration process, and the resulting sesk-sensitvve behaviors seem to be relevant in adequate environments.
change in
Dynamic programming for the optimization of other functionals To optimize other statistical functionals such CVaR and other utilities such moments with Dynamic Programming. Bäuerle and Ott [201 I] and Bäuerle and Rieder [2014] propose to extend the state space of the original MDP X" X R by theoretically adding continuous dimension store the current cumulative rewards. This idea does not contradict our results, and the resulting algorithms remain empirically much more expensive.
Another recent thread of ideas to optimize functionals of the reward revolve around the dual formula- tion of RL through the empirical state distribution [Hazan et al., 2019]. Algorithms can be derived by noticing that utilities like the CVar are equivalent to solving a convex RI. problem [Mutti et al., 2023).
7 Conclusion
Our work closes an important open problem the theory MDPs: we exactly characterize the families of statistical functionals that can be evaluated and optimized by dynamic programming.

---

We also put into perspective the DistRL framework: the only functionals of the return that can be optimized with DistRL can actually be handled exactly by dynamic programming. Its benefit lies elsewhere, and notably in the improved stability of behavioral properties it allows. We believe that, by narrowing down the avenues to explain its empirical successes, our work can contribute to clarify the further research to conduct on the theory of DistRI..
Acknowledgements
Alexandre Marthe and Aurélien Garivier acknowledge the support the Project IDEXLYON the University of Lyon, in the framework of the Programme Investissements d' Avenir (ANR-16-IDEX, 0005), Chaire SeqALO Claire Vernade is funded by the Deutsche Forschungsgemennschatf (DFG) under both the project 468806714 14 of the Emmy Noether Programme and under Germany's 's Excellence Strategy EXC number 2064/1 Project number 390727645. Claire Vernade also thanks the international Max Planck Research School for Intelligent Systems (IMPRS-IS) and Seek. for their support.
and Project FOUNDRY PEPR-IA.
References
M. Achab and G. Neu. Robustness and risk management via distributional dynamic programming. Dec. 2021. arXiv:2112.15430 [cs, math].
Auer. Using confidence bounds for exploitation-exploatiin trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
G. Barth-Maron, M. W. Hoffman, D. Budden, W. Dabney, D. Horgan, D. Tb, A. Muldal, N. Heess, and T. Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint 1rXiv:1804.08617 2018.
M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective on reinforcement learning. In International conference machine learning, pages 449-458. PMLR, 2017.
M. G. Bellemare, W. Dabney, and M. Rowland. Distributional Reinforcement Learning. MIT Press, 2023.
J. Bernhrrd, S. Pollok, and A. Knoll. Addressing inherent uncertainty: Risk-sensitive behavior generation for automated driving using distributional reinforcement learning. In 2019 IEEE Intelligent Vehicles Symposium (/V), pages 2148-2155, 2019. doi: (000//0..0099.8....
V. S. Borkar. Q-learning for risk-sensitive control. Mathematics of operations research, 27(2): 294-311, 2002.
V. S. Borkar. Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems- 2010.
N. Bäuerle and J. Ott. Markov Decision Processes with Average- Value-at- Risk criteria. Mathematical Methods of Operations Research, 74(3):361-379, Dec. 2011. ISSN 1432-2994, 1432-5217. doi: 10.1007/s00186
N. Bäuerle and U. Rieder. More Risk-Sensitive Markov Decision Processes. Mathematics of Operations Research, 39(1): Feb. 2014. ISSN 0364-765X. doi: 10. 00.1287/mor.20113.00 Publisher: INFORMS.
K.-J Chung and M. Sobel. Discounted MDP's: Distribution Functions and Exponential Utility Maximization. SIAM Journal on Control and Optimization, 25(1):49-62, Jan. 1987. ISSN 0363-0129, 1095-7138. doi: 10.1137/0325004.
W. Dabney, G. Ostrovski, D. Silver, and R. Munos. Implicit Quantile Networks for Distributional Reinforcement Learning. In Proceedings of the 35th International Conference on Machine Learning, pages 1096- 1 105. PMLR, July 2018a. ISSN: 2640-3498.
W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional Reinforcement Learning With Quantile Regression. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018b. ISSN 2374-3468. Number: 1.
10

---

A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Comera-Paredess M. Barekatain, A. Novikov, F. J. R. Ruiz, Schrittwieser, G. Swirszez, Silver, D. Hassabis, and Kohli. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53 Oct. 2022. ISSN 1476-4687. doi: 10.100886411366-22--512222 Number: 7930 Publisher: Nature Publishing Group.
H. Föllmer and A. Schied. Stochastic Finance: An Introduction in Discrete Time. De Gruyter, Berlin, Boston, 2016. ISBN 9783110463455 doi: do::10015115997811166666
M. Ghavamzadch, A. Lazaric, and M. Pirotta. Exploration in reinforcement learning. Tutorial at AAAI'20, 2020. URL https://rlgaamazzree wit.err..i.ttuuiii...
J. Grandmont. Continuity properties von neumann-morgensteer utility. Journal of Economic Theory, 4(1):45-57, 1972. ISSN 0022-0531. doi: https://doi.org/10.. wttp/////1111100001101000 (0160022-0033172290166
E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 2681-2691. PMLR, 09-15 Jun 2019. URL https: ctctts::/proceeeiiii http///rrceeee...c.//////// mlr. preas/v97 haa/aaaaaa119 9a html.
M. Hessel, J. Modayil, H. van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver. Rainbow: Combining Improvements in Deep Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10. 16.9/aaa v32i1.11796.
R. A. Howard and J. E. Matheson. Risk-Sensitte Markov Decision Processes. Management Science, 18(7):356 369, Mar. 1972.
C. Jin, Z. Allen S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
N. Lazic, C. Boutilier, T. Lu, E. Wong, B. Roy, M. Ryu, and G. Imwalle. Data center cooling using model-predictive control. Advances in Neural Information Processing Systems, 31, 2018.
H. Liang and Z.-Q. Luo. Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds, Oct. 2022. 10. [cs, stat] version:
C. Lyle, M. G. Bellemare, and P. S. Castro. A Comparative Analysis of Expected and Distributional Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): 4504 1804-451140 4511, July 2019, ISSN 2374-3468. doi: 10. 13..09//
Number: 01.
X. Ma, L. Xia, Z. Zhou, Yang, and Q. Zhao. DSAC: Distributional Soft Actor Critic for Risk- Sensitive Reinforcement Learning, June 2020. arXiv:2004.1 14547 [cs].
A. Mirhoseini, A. Goldie, M. Yazgan, J. Jiang, E. Songhori, S. Wang, Y.-.. Lee, E. Johnson, O. Pathak, S. Bae, et al. Chip placement with deep reinforcement learning. arXiv preprint Niv:20004.10744 2020.
M. Mowbray, D. Zhang, and E. A. D. R. Chanona. Distributional reinforcement learning for scheduling of chemical production processes, 2022.
M. Mutti, R. De Santi, De Bartolomeis, and M. Restelli. Convex reinforcement learning finite trials. Journal of Machine Learning Research, 24(250):1-42, 2023.
I. Osband, D. Russo, and Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
M. Popova, O. Isayev, and A. Tropsha. Deep reinforcemmet learning for de novo drug design. Science advances, 4(7)eeapp7885, 2018.
R. Rockafellar, S. Uryasev, et Optimization of conditional value-at-risk. Journal of risk, 21-42, 2000.
11

---

M. Rowland, M. Bellemare, W. Dabney, R. Munos, and Y. W. Teh. An Analysis of Categorical Distri- butional Reinforcement Learning. In Proceedings of the Twenty-Fiite First International Conference on Artificial Intelligence and Statistics, pages 29 29-37. PMLR, Mar. 2018. ISSN: 2640-3498.
M. Rowland, R. Dadashi, S. Kumar, R. Munos, M. G. Bellemare, and W. Dabney. Statistics and Samples in Distributional Reinforcement Learning. In Proceedings of the 36th International Conference Machine Learning, pages 5528-122 2228-556. PMLR, May 2019. ISSN: 2640-3498.
M. Rowland, Y. Tang, C. Lyle, R. Munos, M. G. Bellemare, and W. Dabney. The Statistical Benefits of Quantile Temporal-Differeene Learning for Value Estimation. 2023.
Y. Shen, M. J. Tobia, Т. Sommer, and K. Obermayer. Risk-sensitive reinforcement learning. Neural Computation, 26(7): 1698)11298-,,8, 2014. doi: 10. 10.1162/NECO_a 00000000
J. Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, 19(4):794-802 Dec. 1982. ISSN 0021-9002, 1475-6072. doi: 10.2307/3213832.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
C. Szepesvári. Algorithms for Reinforcement Learning. Synthesis Lectures Artificial Intelligence and Machine Learning, 4(1):1-103, Jan. 2010. ISSN 1939-4608, 1939-4616. doi: 10,2200/
S00268ED1 VO1 2000100000AAM000
C. Villani. Topics in Optimal Transportation. Graduate studies in mathematics. American Mathe- matical Society, 2003. ISBN 9780821833124. URL https://bookee www.ee.ooooooooooooooooooooooo.. foogle.ft/books770 frd idyFAwAAQBAJ.
A. Volk, R. W. Epps, D. Yonemoto, B. S. Masters, Castellano, K. Reyes, and M. Abolhasani. Alphaflow: autonomous discovery and optimization of multi-step chemistry using self-driven fluidic lab guided by reinforcement learning. Nature Communications, 14(1):1403, 2023.
J. von Neumann, O. Morgenstern, and A. Rubinstein. Theory of Games and Economic Behavior ( (60th Anniversary Commemorative Edition). Princeton University Press, 1944. ISBN 978-0-691- 13061-3.
C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8:279-292, 1992.
R. Wurman, Barrett, K. Kawamoto, J. MacGlashan, Subramanian, T. J. Walsh, R. Capobianco, A. Devlic, F. Eckert, F. Fuchs. L. Gilpin, P. Khandelwal, V. Kompella, H. Lin, P. MacAlppnne D. Oller, T. Seno, C. Sherstan, M. D. Thomure, H. Aghabozorgi. L. Barrett, R. Douglas, D. White- head, P. Dürr, P. Stone, M. Spranger, and H. Kitano. Outracing champion Gran Turismo drivers with deep reinforcement learning. Nature, 602(7896):223- 228, Feb. 2022. ISSN 1476-4687. doi: 000884441586-021-4433535 Number: 7896 Publisher: Nature Publishing Group
12

---

A Additional remarks
The Wasserstein metric is defined (2) So Fin (1) Frz(()) du and the Cramer metric as (2) (I= Fu, (u) (u) du) For both metries, we de- fine their supremum (2 72) = sUP(a,a)XXxA (2 (c, a), (2 a)) and Wi(n: 12) = (x. ( (z, a), (2, a)).
A.1 Remarks on the recursive definition of the Q-value distribution
The notation of the Q-value distribution r is often deceivingly complex compared the actual object it means to represent. While the 'usual' expected Q-function (z a) is simply understood as the expected return of policy at state-action pair (x, a). DistRL requires us keep a notation for the complete distribution of the return. In other words, the Q-value distribution (2.a) should be understood as the distribution of the random variable Z = R Z(S"). which is the convolution of individual distributions of these two independent random variable. can also be written:
77,
(x) = Σ S
pn a' x')x (T (a', a²)( R) ((2.a) (dr).
Vx, a, h,
(10)
of at.
A.2 Linear and Exponential Utilities satisfy the properties of Lemma
Independence Property Any utility Uy verifies the independence property. Let v1, 12, V3. E (R)) x E [0, 1]. Assume (y(1)) (y())) Then,
/ sa(Au + (11)))ss
U,(A1 +1 (1-A)u3)
= > / sau +(1 - 21 sdvs
(g((s)
2 A favz +(1 - 2 savs
Uy(22)
= fd(Auz + +(1-Aluy
UA + (1- A)us))
In particular, the mean and the exponential utility do.
Translation Property This property comes from the linearity of the mean and the multiplicative morphism of the exponential. Let vI, 12 E (R), e R. Assume that Uaxp (v1) Z Uesp (12) and Umean (v1 2 Umean (Vz). Then,
/
Uexp(ToU1)
exp(r)dror1())
/ explr + c)du((r)
exp(c) / (xp(r)ddr
exp(c)Uexp(M))
2 exp(c)Uoxp (Uz)
(TX2(
13

---

Umean (Tcl)) = / Ar + + OdT
+ Umeam (21)
2 c + U Umeam (22)
Umean (Telk)
A.3 Policy Evaluation for linear combinations of moments
Rowland et al. [2019] prove a necessary condition on Bellman-closed utilities, namely that they should be family of the form {x ++ x exp(Ax)]0 < f S L} for the undiscounted, finite-horizon setting. In the discounted case, the necessary condition is only valid for À O. that is, without the exponential. They also prove that moments (without the exponential) also verify the sufficient condition such that in that setting they are the only Bellman-closed families of utilities.
In the undiscounted setting, to the best of our knowledge, similar result has yet been proved. We provide here the sufficient condition for families of the form {x + x² exp(Ax) 0 < & S LJ. We show that they are Bellman-closed and that this implies that they can be computed by DP.
Let's consider the family 8n (V) - f exp(Ar)du(r) for ls E [ri] and some fixed R.
sa (1 (x, E (2, exp(AZ% (x, a))]
E ((Ra(E, a) + Z (X', A')) exp(X(Ra(rra) + (x',(X,,A)))
Es'.a' Zn+1 Zn+1 (Rn(2z a) ( a²)) exp()(R((z + Zhti (4' ,')))'') 30)x'=s',4 =''A'=
Σ (a, a, ) (a 12+1 [2na(z, + 1 (xxp:l" a) (Z4+'''',
Σ ph a, )' (R Zs+1
Σ
Tt
RA a)a (x"= exp(ARa a) ( a²)² 2 .))
bs
Σ z'.a'
(x, 2') (a')
BRA
Hu (x, a)" exp(AHt Bzn+1 Iktile', exp(AZi+
k=
Σ (m,
ERa
Ra a) (x)(A sx (1(tttz('''
This first proves that this family of statistical functional is Bellman closed: they be expressed linear combination of the others. Moreover, on the right-hand side, the expression only depends on the distributions and functionals at the current step h and at the next step h + 1. Thus, it provides natural way to evaluate these functionals by DP.
B Categorical Projection: an alternative parametrization
The categorical projection was proposed and studied in Bellemare et al. [2017], Rowland et al. [2018). Bellemare et [2023]. For a bounded return distribution, it spreads fixed number N of Diracs evenly over the support and used weight parameters represent the true distribution. The parameter N is often referred to as the resolution of the projection. More precisely, on a support [Vmins Vmma].
1]. We define the we write A Vmn-- Vum the step between atoms 2; Vnnn + id, E [0, N
N-1
projection of given Dirac distribution 5, on the parametric space PR) = 1 p:ò2, 0 S P. S 1, Σ, P: = 1) by
8z0
y S 20
Ilo(5))
2141 11 82, + 2:11-;
w-26 8,41
2, < < 2i+1
(1I)
#11-2
8
y N -N
14

---

This definition can naturally be extended to any bounded distribution v, and by extension, Ien (II (x.))xX.A This linear operator minimizes the Cramér distance of the parametrization to the parametric space [Rowland et al., 2018].
This projection verifies this approximation bound, analog the quantile projection,
A
sup (xxA)
((llen(z,a)
(12)
N
Using the property that (2) S (2,, u2), the results with the quantile projection can be adapted for the categorical projection, adding vA,, factors to the bounds.
This parametrization has the nice property preserving the mean of the distribution. Yet, even for risk-neutral RL, Quantile-based DistRL algorithm seem to work better and display better proper- ties(Dabney et al., 2018b,a].
C Proofs for Policy Evaluation with parameterized distributions
C.1 Proof of Proposition 1
We recall the statement of Proposition 1: Let π be a policy and 17 the associated Q-value distributions. Assume the return is bounded interval of length A,, I H AR. where An is the support size of the reward distribution. Let rj be the Q-value distributions obtained by dynamic programming (Algorithm 1) using the quantile projection II with resolution N. Then,
An
I H² AR
sup (IX.,M)
W W1 (2. ( (x,, S H
2N
2N
To avoid clutter of notation, we denote W (() m)) = suP(n.a)xx W (f( ())
Proof. First recall that for any Q-value distribution (1), bEEH) with the return bounded interval of length A,, < HÀn. n. and IT one of the projection operator of interest with resolution n, we have the following bound on the projection estimation error due to Rowland al. [2019] (Eq (6)):
A
W. n) S
(13)
2N
At a fixed step E [H], we have the following inequality:
W WiG mt) WIIT T7 Th 0h+1)
W (IIT 1: 1: Th fh+1) ) W 1 1 Th T'nEi
(14)
H An
+ 2.V
Wi 1)
(15)
Where (14) is due to the triangular inequality with Th f as the middle term. In (15), the first term comes from applying (13) to the first term of the previous line. The second term is a consequence of the non-expansive property of the Bellman operator [Bellemare et al., 2017]:
W WT T S W (1(hh90 72)
Using it recursively starting from h = 1, and using the fact that Ai = nh we get:
AR
AR
H2 Ar
Wi(Mi
W (1
2H
W
(og
m S
S
2N
2N
2N
15

---

C.2 Proof of Lemma
We recall the statement of Lemma 1: Let be either a utility distorted mean and let be the Lipschitz coefficient of its characteristic function. Let v1, be return distributions. Then:
(s(12) - s(v2) _ LW1 (W1, v2).
Proof. We prove the property for each family of utilities separately:
Case 1: 8 is utility, There exists such that s(v) = f fdv. Let Ly be its Lipsichtz constant. The Kantorovitch-Ruuensee duality [Villani, 2003] states that:
1
(f
g [dd dup (dvz))
Wi U2)
sup Sal
(16)
Ly
where || is the Lipschitz norm. We then immediatly get:
L,W1(11,2)) 2 21 I I dui - / duz [s((1) -((22)
(17)
Case 2: 8 a distorted mean. There exists such that s(v) = (F) Let bg be its Lipschitz coefficent. Thus:
- -(12)= L. g'(T) (Fi
- - dr
s 11 //' (r) Frj (T)
< (11,(())))2)
D About the tightness of Theorem 1
The upper bound provided by Theorem is mainly based on Proposition 1. The latter is obtained by summing, for every step, the Projection Bound by Rowland et al. [2019] (Eq. 6). Thus, achieving the bound would requires first to find a problem instance for which, at every step, the projection bound is tight. Then would require verify that the total error is the sum of those projection errors.
The experiment in Figure 2 already shows that summing the total error is very close to the sum the projection errors. However, in that example, the projection error bound is not reached after the first step. In the following, we exhibit an MDP for which the projection bound is tight at every timestep.
First, let consider a family of distributions for which the projection error is tight:
Proposition 2. Let N E M, A E gt Consider 2;
iA N.
The distribution
N-1 Σ
(52, + 82.11)
VNA
2N
1=0
has support of length A and verifies W1 Wi
2N
Proof. The cumulative distribution function (CDF) the distribution VN,A is
x< 0 20
F Fux (x) =
21+1 2N
2, S < 2;t1
r NN
We write 7; and the Wasserstein distance relative to it. A possible Quantile projection IIouN,A # EN- N-1
2++1 2N so that Vi
[[0, N - Few. (2:) = т. We now explicit the projection of VN
16

---

and
= / |F (w)((w) (w)
(
N
Σ
Fu (w) (w)
Fro (w) |dW
N-1
1+1 (w)
Fy (w)
2: +
F (w)
2, dw
==
2+11
3i+1 1 2i
2N
A
2N2
A
2N
The value distribution of the following time steps obtained by applying two operators: the Bellman operator and the projection operator. Here will consider a MDP with only one state. We need to find such operators so that Hl TUN,A VN.A,. where the Bellman operator simply consists in the added reward distribution.
Proposition 3. Let N E N, AER. Consider 160 + 6 x22) ) Then there exists a Quantile
projection operator IQ such that
e * IIQ(NN,)) VN.IAt WAT)
Proof. We consider (Q((NN,)) N Ti, verifying that it is indeed valid Quantile Projection. Hence,
E مي Since Vi, N-T
S 24 <
(+1)) N-1 we have F(z.)
1 N
@ IlQ(,N.))
2
(60
+
8
N
*
Σ
N
(00 +
* +ي
1=0
1 N-1
8 د
+ 8 مسعn
2NN
UN m
The last egality comes down to noticing that N
A4 (A
X/4
)
Here, we take advantage of the fact that the Quantile Projection is not unique (see discussion in section 2.1). By choosing the adapted projection, it is then possible to obtain one of those distribution at every timestep.
Corollary 1. Let N E N. Do E Rt. Consider the sequence Aht1 = Ax + xL)) and e =
1 (ōo 8 (2.). Consider II as in Prop. 3.
17

---

2.0
Vumulative Approximation Error
Wasserstein Distance
True Error
1.5
1.0
0.5
0.0
2
timestep
Figure 3: Evaluation of the Wasserstein Distance between the true value distribution and the approxi- mated one, in the MDP described in Corollary
Consider the MDP with only one state x and action a, reward distribution @h. horizon H. Consider in the value distributions obtained throught dynamic programming with quantile projection. Then, at any timestep h, the error induced by the projection operator matches the bound in Eq. 6:
D 2NN
Wi(IIq mr
While the projection error is maximal in such instance, it verified experimentally that the bound in Prop. was still not tight. This comes from the fact that the Bellman operator not a non-contraction this case, and that the triangular inequality used to the projection error is not tight either.
We hence found that every inequality used in proving Theorem can tight, but there does not seem to exist instance for which all the inequalities are tight at the same time, meaning that this bound would never reached exactly.
E Proof of the main results
The proof of the result is divided in parts. First we show that Bellman optimizable functionals verify the two properties Lemma (Independence and Translation). Then, using those properties, we prove that Bellman optimizable functionals can only be exponential utilities (Theorem 2). Using the known fact that exponential utilities are bellman optimizable, we obtain characterization.
E.1 Proof of Lemma 2
Proof. To prove that each property is necessary, we use a proof by contradiction, and exhibit MDPs where the algorithm is not optimal when the property is not verified.
Independence Property Let Bellman optimizable statistical functional that does satisfy the Independence property. That is, there exists V1, 12, V3 E (RR and X E [0, 1] such that s(M)) s(22) but s(Ne) + A)uz) s(Xe2 (1 A)13).
Then consider the MDP in Fig.4 (left) with horizon H = 2 corresponding to the depth of the tree: The agent starts in Start and must take actions, unique but random and non-rewarding one (ag) and a final deterministic step (a, or a2) to a rewarding state. Thus, by construction, the optimal strategy is (ao. (2) that leads to End with probability À (and End 3 with probability 1 1 A). The true optimal distribution at Start state 17 Avz + (1 A)13. We compute the distributions output by the algorithm:
H
7/ (End 1, 1,a*) 8o, 7 2, a²) ) = 50. To (End 3, a²) 50 M) (Left, at = arg max s(va)) = v1, (Right, a" = =a,,0) V3
H 1:
H = 0:
To (Start, a" =a)) = Av + (1 2)23
18

---

End
End
Right
pla,
plx,2 d
p by
p by
Left
Right
Step
pla.a
plx,a') = 1-A
p dg
Figure 4: Left: Independence Property Counter Example, Right: Translation Property Counter Example. Each arrow represents transition, which is characterized by the action leading the transition, the probability of such transition, and the reward distribution of the transition.
The output return distribution ?/ not the true optimal 176 for s so the algorithm is incorrect which is a contradiction as is assumed to be Bellman optimizable. Hence the property is needed.
Translation Property Let be Bellman optimizable statistical functional that does not verify the Translation Property, i.e. there exists 12 E (RR), c E I such that s(v1) 2 s(V2) but s(Te1) s(T,42) Then consider MDP in Fig.4 (right). The optimal strategy is again (4o; a2) by construction. The algorithm output the following distribution:
H1 = 2:
(Left, a²) = do.
Tz (Right a²) = 60
H 1: M (Step, a²) U1
= 0:: (Start, a²) T
So here again, the algorithm does not output optimal distribution for hence the necessity of the property.
This proof shows that both properties are necessary, but not that they sufficient. The other implication could be proven, but the proof would be unnecessary as those properties are enough to restrict to only 1 class of function for which already know is bellman optimizable.
E.2 Proof of Theorem 2
Proof. For any return distribution 1/, let s(v) be the considered functional. Since we assume that W1 Wi-continuous Bellmman optimizable, the by the Independence Property (Lemmaa 2) know from the Expected Utility Theorem that we can assume: s(v) = (v) = J& f(z)dv(z) for some continuous, monotonous mapping Without loss of generality, may assume by density argument that f is twice continuously differentiable.
By the Intermediate Value Theorem, (f(()) f(h)) f((()) and in particular ((0) ff(() 0.
then define @(h) f- (5((()) f(h))) so that
very special case is when f' constant, which satisfies the theorem. We now assume that there exists point zo such that f' does not vanish on neighborhood of zg. On this neighborhood, using the inverse function theorem, is also twice differentiable. Without loss of generality, we assume that 0.
For any fixed h O, consider the probability distributions 1i (00 6%.) and 1/2 6e(M)- Remark that 8y (y1) = ʃ dej = (((()) + f(h)) and sy(12) = f(((h) ()(()) + f(h)) by definition of o. so (v1) = sy(12)
19

---

The Translation property implies that for all x E R. sy(r1) S s2(12) = s + (1)(++))) S 5/(12(- z)) and (v() 2 5y(12 sa(vi(- + +x)) 2 sy(12(- + z)). Hence, Vx E R.
( f(x + h)) = [(x + ((h).
This equation can be differentiated twice with respect to h. For any value of æ, we obtain:
(x -'0 and
(18)
2 fz = dz) o
((h))
(19)
Recall that by definition, 6(0) 0. Now, for 0, Eq. (18) yields ( = d'(0)
(0))) and, since ('(0) + 0, (0 2"
Now, choosing h 0 in (19) and plugging in the values of x(0) and (0()), we obtain for all E R:
((())="(()))
We then consider two cases, depending on whether (²) is null or not.
Case 1: (0) = 0. The equation simply becomes f"(x) 0, hence f is affine: Ja, b E IR f(x) ax + b.
Case 2: (0) * O. We write 3 = (0). The differential equation becomes f"(x) = (z),
whose solutions are of the form
3,, 02, B, f(x) cı exp(3x) + C2.
Hence, f can only be the identity or the exponential, to an affine transformation.
20


Reviews:
[{"review_id": "6neAjyaMBl", "reviewer": "Reviewer_3Rfs", "summary": "This paper addresses", "questions": "My suggestions has been listed in weaknesses, which I will paraphrase here:\n1. Please fix grammatical errors and add proper references on early works, especially for the sections with propositions.\n2. Please connect your work to more practical applications. I know it might be hard to conduct experiments as additions to this paper, but some discussions would be helpful.\n3. Please give more details about the experiments on functional distance calculation.\n4. Most importantly, please add descriptions on potential limitations, concerns, and societal impacts about the work at the very last of the paper.", "limitations": "Although since it is a theoretical paper, I do not think an external ethical review is needed, the limitations, potential societal impacts and ethical concerns, and future work are lacking. Authors may address it later if applicable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The method is very well-presented, with notations, terms and algorithms put in a very clear and understandable fashion. They are introduced without fancy names and terms, which is great.\n2. The questions are well-stated and addressed respectively from a theoretical perspective, and they are fundamental problems.\n3. The significance of contribution is good. It provides a good starting point to address the statistical functional evaluation problem.", "weaknesses": "1. Some statements in the propositions lack references to earlier works, such as quantile functions an CVaR (metric).\n2. The learning environment description is lacked.\n3. The limitations, potential societal impacts and ethical concerns, and future work are lacking.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our paper. We respond below to your specific concerns but please also check the common response which contains clarifications that were common to all reviewers and will be added to the final version. \n\n- Discussion of Limitations, societal impact and ethical concerns.  \n\nWe have added a paragraph in the discussion about the limitations of our works, potential future work and connections to more practical applications. Thank you for pointing out these points. Regarding societal impact and ethical concerns, given the nature of the paper -- a theoretical result limiting the extent of Distributional RL -- we do not believe it can have any such impact. The Neurips CFP says “The checklist is filled out in the OpenReview submission form, but you may provide additional information in your paper to support your answers (e.g., a limitations section).” and we believe no additional information is needed. If you have a specific concern about the societal impact of our work that we have overlooked, please let us know and we’ll try to address it. \n\n- More details about experiments.  \n\nThank you for the question. As other reviewers have also raised questions about our experiments, we address this in the common response. First we were able to identify a bug in the computation of the Wasserstein distance in our code and we now have correct Figures (see pdf) that show a much tighter bound. Second, we have explored the tightness of our bound and we are able to make comments on it. We will add this discussion and more details about the experiments in the final version. \n\n- Lack of references.  \n\nWe are not sure what you are referring to. The subsection “Beyond Expected Rewards” introduces alternative statistical functionals and for CVaR we cite [Rockafellar, 2000]. Our paper has more than 2 pages of references and we are not sure what is missing. Do you have a pointer to relevant papers we may have missed? \n"}, {"review_id": "PxkfslxUEF", "reviewer": "Reviewer_RipE", "summary": "Classic RL maximizes the (discounted) cumulative reward in Markov Decision Processes (MDPs). This paper studies more general functionals of rewards, such as generalized means. These more general functionals are useful to consider for certain applications, such as those with safety concerns. Furthermore, the study of these more general functionals has been not well understood in the literature. \n\nFor finite-horizon prediction problems, this paper 1) argues that only generalized means of rewards can be obtained exactly using dynamic programming and there is no need to resort to learning the entire distribution of return (I am confused about this part, see Questions), and 2) provides an upper bound of estimation error for utility functionals, which are more general than generalized means, when approximated with Quantile Distributional RL. Both 1) and 2) mirror Rowland et al.'s (2019) results, which were developed concerning the discounted setting.\n\nThe most important result is for finite-horizon control problems. This paper shows that the only Bellman optimizable functionals (those that can be optimized by applying Dynamic Programming to the distribution of return) are generalized means. Combined with a previous result showing that generalized means can be solved using dynamic programming (no distribution involved), this result shows that the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming, which is a much more efficient algorithm. ", "questions": "\"Much of the existing theory is based of discounted MDPs, but many recent efficient RL algorithms with strong guarantees are for finite-horizon, undiscounted setting\" What kind of theory do you mean for discounted MDPs? Could you give examples that illustrate this argument?\n\nCould you point to the result by Rowland et al. (2019) that gives equation 6?\n\nNote that other parameterizations exist but are less practical. Could you explain why is this true or refer to other works that show that this is true?\n\nLine 122-123: when lambda > 0, the utility is higher for Gaussian distribution with a larger sigma (higher variance), so isn't this case risk-seeking?\n\nLine 124: you don't need to mention this axiom at this point. I have been wondering why I need to know this until I found it being used in section 4.\n\nLine 152 is confusing to me: do you mean that for any L >= 1, statistics corresponding to the first L+1 moments form a Bellman closed set? \n\nLine 152: Theorem 4.3 by Rowland et al. (2019) only mentioned moment functionals but not exponential functionals. Furthermore, although you prove in A.3 that sets of multiplication of moments functionals and exponential functionals also form a Bellman closed set in the finite horizon setting, you didn't show that these are the only families of functionals that form Bellman closed sets in this setting.\n\nThe footnote on page 5: how can the support of return be -h + 1 given that all rewards are non-negative?\n\nLine 215: is the question open for utilities other than exponential ones for control problems?\n\nLine 221: why define Bellman optimizability instead of extending the definition of Bellman closeness to control problems? In addition, it is weird to define a quantity, which you want to optimize, using an algorithm that optimizes it. Do you see other ways that make this definition without resorting to a particular algorithm?\n\nLine 241: why does this result narrow down the family Bellman optimizability functionals to utilities? I mean, literally.\n\nSection 5: why would we want to see a new algorithm without any theoretical/empirical study of the algorithm?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The problem that this paper studies is an important one. \n\nThe main result, which shows that the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming, is remarkable.", "weaknesses": "The writing of the paper needs improvements. Specifically:\n1) right now, the presentation of the paper is driven by the technical results that it wants to show, rather than the messages that it wants the readers to know. The paper presents an important result about Distributional RL: the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming. As the authors highlighted in line 260, this result is the most important one and it narrows down the avenues to explain its (distributional RL) empirical success (line 310). However, this result is not outspoken throughout the paper, until an inconspicuous discussion on page 8. Why not say your most important result in the Abstract and the Introduction sections? \n\n2) The notations given background section need to be clearly defined:\nthe notation (z_i)_i needs to be defined.\n\\delta is not defined (line 96).\n\\mu is not defined (line 97).\nF_\\mu is not defined (line 98).\nwhat is \\eta in line 100?\n\\Delta_\\eta is not defined in line 101.\nLine 124: U_f is not defined.\n\n3) typos: extra m at the end of line 209\nline 184: should be \"see Figure1 (left)\"\nline 199: should be \"Figure 2 (left)\"\nthe order of the two subfigures in Figure 2 would better be reversed in accordance to the texts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your in depth review of the paper and the relevant questions that will help clarify it. We now address each raised points : \n\n- About the undiscounted setting theory : \n\nThank you for pointing out this sentence, we agree it was unclear. The goal of this sentence and the following was to justify our choice of studying the finite-horizon setting, which has an impact on our results (discussed in the last section). We rephrase it as follows: \n“Historically, the theory of RL has been established for discounted MDPs (e.g. [Sutton & Barto, 2020; Watkins & Dayan, 1992; Szepesvári, 2010; Bellemare et al., 2023]) but recently more attention was drawn to the undiscounted, finite-horizon setting [Auer, 2002, Osband et al., 2013, Jin et al.,2018, Ghavamzadeh et al., 2020], for which fundamental questions on the theory of MDPs remain open. In this paper...”\nWe also tried to clarify the impact of this choice a bit earlier in the paper and refer to discussions for completeness. \n\n- Precise pointers to Rowland’s work (Eq 6 and Th 4.3 (line 152)) :\n\nThose are actually intermediate results that can be found in the appendix of their paper ([2]). Equation 6 corresponds to Lemma B.2. We also want to point out that [1] contains a similar result with an additional ½ factor in the bound (exercise 5.20). For the theorem 4.3, the result is part of the proof which is divided in two parts. First, they start by reducing the study to the set of functions we discuss (equation 14 in their appendix), and then they show that, because of the discount, the exponential part has to be discarded. In our case, without discount, only the first part still holds and that is what we use. We just need to verify that the set is indeed bellman closed in this setting, which we do in appendix A.3.\n\n- “Line 152 is confusing to me: do you mean that for any L >= 1, statistics corresponding to the first L+1 moments form a Bellman closed set?”\n\nYes, this set of statistics is a Bellman closed set. This was already true and known in the discounted setting considered by Rowland [2]. The difference in ours is the addition of the exponential term in it.\n\n- Relevance and discussion of other parametrizations:\n\nThe only other studied parametrization with theoretical grounds is the Categorical Projection, described and discussed in Appendix B. We omitted it in the main text because it is not essential to our argument. Among its issues is the need for a fixed and known support of the distributions of study and the use of a different metric for the bounds[3]. Moreover, algorithms using the quantile approach display better results [4][5].\n\n- \"Is the question open for utilities other than exponential ones for control problems?\"\n\nTo be precise, whether or not any statistical functional other than the exponential utility can be optimized efficiently in general is still an open question, utility or not. We focused on dynamic programming algorithms and thus on the existence of a Bellman equation to support it. Our claim is that for utilities other than exponential, a policy-improvement type of strategy cannot work. We do not claim that there exists no other algorithm that can compute it, this question remains open and would possibly require a complexity theory analysis, such as proving that it is NP-Hard. This is out of the scope of the paper but is an interesting question. We will clarify that again. In RL, however, the predominance of dynamic programming is fundamental and we believe this justifies that our Theorem remains significant and impactful. \n\n- \"Line 241: why does this result narrow down the family of Bellman optimizability functionals to utilities?\"\n\nThe result does not prevent the existence of non-utilities verifying the property. However, the result implies that studying utilities is enough because if another statistical functional can be optimized by such an algorithm, then there exists a utility that yields the exact same results. Hence, if we know the form of all the utilities that verifies such property, we know the form of all statistical functionals in general.\n\n- \"Line 221: why define Bellman optimizability instead of extending the definition of Bellman closedness to control problems?\"\n\nThis question was raised by several reviewers, so we address this in detail in the global rebuttal.\n\n- \"Section 5: why would we want to see a new algorithm without any theoretical/empirical study of the algorithm?\"\n\nThis is also addressed in the global rebuttal: the algorithm is not new nor ours and we mention it in the paper for completeness of our argument that utilities can be learned. \n\nWe also thank you for pointing out typos and writing errors, we have now fixed them all and made a thorough grammatical pass on the paper. \n\n[1] Distributional Reinforcement Learning, Bellemare et al., 2023  \n[2] Statistics and Samples in Distributional Reinforcement Learning, Rowland et al. 2019  \n[3] An Analysis of Categorical Distributional Reinforcement Learning, Rowland et al. 2018  \n[4] Distributional Reinforcement Learning With Quantile Regression, Dabney et al. 2018  \n[5] Implicit Quantile Networks for Distributional Reinforcement Learning, Dabney et al. 2018"}, {"review_id": "8mbEYzgfEz", "reviewer": "Reviewer_kE1T", "summary": "This paper considers the problem of using distributional reinforcement learning to perform policy evaluation and planning with more general classes of reward functionals than those typically considered in standard Markov decision processes and RL. The paper focuses in particular on dynamic programming methods for obtaining distributional Q functions based on distributional Bellman operators, as well as how to use these methods for planning with the resulting distributional Q functions. The main contributions of the paper are twofold: (1) when performing distributional policy evaluation on general utilities using a certain kind of distributional Q function approximation scheme, worst-case bounds in terms of Wasserstein distance of the approximation from the true distributional Q function are provided; (2) when performing planning using distributional Q functions, a new notion of \"Bellman optimizability\" of reward functionals is given, and it is shown that the only Bellman optimizable reward functionals are the class of exponential utilities. It was previously known that standard (i.e., not distributional) dynamic programming methods (see, e.g., lines 213-214) can be applied to solve planning problems with general utilities, so contribution (2) provides a negative result suggesting that distributional RL methods, though providing a very general framework for performing evaluation and planning via dynamic programming, are not strictly necessary to solve the class of problems to which they are theoretically suited.", "questions": "* Given Theorem 2, what is the main usefulness and impact of the approximation bounds provided in section 3?\n* Why is Bellman optimizability (Definition 2, lines 221-222) the right notion of what it means for a problem to be solvable using distributional RL? Are there incompatible notions of optimality that might invalidate Theorem 2? If not, why not?\n* Why does the assumption regarding the utility integrand $f$ on lines 516-517 in the appendix hold?\n* It is mentioned that policy stationarity is disrupted in the discounted setting on lines 289-290. Can you provide references ensuring sufficiency of stationary policies in the setting you consider?", "limitations": "Aside from the weaknesses and questions above, the authors have adequately addressed the limitations of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is well-written and the results add clarity to the distributional RL landscape that is likely to be of interest to the community. Regarding significance, contribution (1) outlined in the summary given above is potentially useful for a wider range of utilities than previously considered, but the results appear to be straightforward extensions of existing results (see C.1, C.2 in the appendix). The main result of the paper is instead contribution (2), provided in the form of Theorem 2 (lines 248-250). This result delimits the applicability of distributional dynamic programming to classes of utilities that can be handled using non-distributional techniques, suggesting that the primary usefulness of distributional RL methods may be experimental instead of theoretical. It is refreshing to see an ML paper making an effort to soberly clarify the mathematical limits of a particular subfield of ML research. The proof of this result (see D.2) appears to boil down to first constructing a differential equation based on the integrand of the utility, then solving to show that the integrand must correspond to an exponential utility. The proof is not long, but the idea is clever.", "weaknesses": "I have two main concerns regarding the paper:\n* Contributions (1) and (2) are somewhat disjointed. On the one hand, (1) provides reassurances that Algorithm 1 enjoys approximation bounds for a wide variety of different utilities. At the same time, (2) undermines this result by showing that planning using the resulting distributional Q functions is only theoretically meaningful for a much-restricted subset of those utilities. Some clarification of the implications of (2) for (1) would be helpful.\n* In the proof of Theorem 2, it is assumed that the utility integrand $f$ is twice-differentiable and $f'(x) \\neq 0$, for all values of $x$. This assumption is critical to Theorem 2, thus to contribution (2), and thus to the overall contribution of the paper. It is stated on lines 516-517 that this assumption \"could be proven through long and fastidious analysis that is beyond the scope of this article\", yet no indication of how this might be accomplished is provided. Given its importance to the paper, I argue that this is within scope of the article, so that a proof sketch or at least a convincing explanation of why this assumption holds is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive and insightful feedback. Please see our response addressing your concerns and questions: \n\n> About the relevance of section 3 related to theorem 2:\n\nThis matter was addressed in the global rebuttal as it asked by several reviewers\n\n> About the definition of Bellman Optimizabitily:\n\nThis is also addressed in the global rebuttal for the same reasons\n\n> Are there incompatible notions of optimality that might invalidate Theorem 2? If not, why not?\n\nThe question on the existence of other notions of ‘optimality’ is unclear to us. An optimal policy is always one that has the maximal value (regardless of the goal, mean reward, utility, etc). Perhaps you meant ‘notions of optimizability’? \n\n> About the loss of stationarity in the discounted setting on lines 289-290 : \n\nThis is a misunderstanding due to the ambiguity of our phrasing. Another way to write it is the following : ”there exists a method to optimize the exponential utility through dynamic programming in discounted MDPs [Cheung and Sobel, 1987]. This approach requires modifying the functional to optimize at each step. A difference with the risk-neutral objective in discounted MDPs, is that the optimal policy may not be stationary”. We never assumed to have stationary policies in our undiscounted setting.In discounted MDPs, however, it is known that the policy optimizing the expected reward can be chosen to be stationary, and we found relevant to highlight that it is no longer the case when we optimize the exponential utility.\n\n\n> Assumptions in the proof of theorem 2 : Differentiation and non-zero derivative\n\nWe agree with you that Theorem 2 uses strong assumptions with no explanations. In fact, the properties that we claim for the utilities can be proved and we have done it for this response. All details have been added to the appendix:  \n\n1. We can reduce the problem to differentiable utilities thanks to an approximation argument.   \n2. Using the continuity and translation property, we can prove that f is either monotone or constant. Similarly, we prove that f’ is monotone.This implies that the derivative is always non-zero.\nWe will try to convey the main intuition of the proofs of these results here although the full proof does not fit.\n\n\t- For **the differentiation assumption**, a way to look at it is to consider that any integrable function can be arbitrarily approximated with infinitely-differentiable functions (see [1] p119, about the density of differentiable functions in the L_1 space) . Thus, for any function, there exists a differentiable one that is close enough such that optimizing  the initial function becomes the same as optimizing on this differentiable one. Hence, in the same way the Von Neumann - Morgenstein theorem is used to reduce the study to utilities, this approximation allows us to reduce the study to differentiable utilities.\n\n\t- **The monotonicity and convex/concave property** are proven using the translation property to transform a local inequality in a global one. Start by considering 2 points, for instance $0$ and $1$. We assume that $f(0) < f(1)$ and  show that $f$ is increasing. To do so, we use the translation property with $\\nu_1 = \\delta_0, \\nu_2 = \\delta_1$, which gives the following : $\\forall c, f(0 + c) \\leq f(1 + c)$ (a local inequality becomes a global inequality). In particular by choosing $c$ to be successively $1, 2, n, \\dots$, we obtain the chain of inequality $f(0) \\leq f(1) \\leq f(2) \\leq \\dots \\leq f(n)$. Now we do the same starting with $0$ and $1/2$ and $c$ a multiple of $1/2$, to get the chain $f(0) \\leq f(0.5) \\leq f(1) \\leq f(1.5) \\dots$. Halving infinitely by recursion, we obtain that $f$ is monotonous on a dense set of numbers. With density and continuity, $f$ is globally monotonous.\n\tNote that in case of equality on two points, this reasoning proves that $f$ is globally constant. Hence, $f$ is either strictly monotonous or constant.  \n\tFor the monotonicity of $f'$, we use the same idea and show that for any two points, with $f((x_1 + x_2)/2) \\leq (f(x_1) + f(x_2))/2$ (or $\\geq$). This is called midpoint convexity and is equivalent to convexity. (Here, for instance, we start with $\\nu_1 = \\delta_{1/2},\\ \\nu_2 = (1/2) (\\delta_0 + \\delta_1)$)\n\n\t- The strict monotonicity implies that the derivative has a constant sign, while the concavity or convexity implies the monotonicity of the derivative. A function both strictly monotonous and of constant sign cannot ever reach 0..\n\n[1] Functional Analysis Sobolev Spaces and Partial Differential Equations, Haim Brezis, 2010\n"}, {"review_id": "YEKxXUqBqm", "reviewer": "Reviewer_3T3p", "summary": "The paper investigates general functionals of the distribution over returns in three situations:\n1) For policy evaluation, the authors prove some error bounds for a given distributional RL algorithm.\n2) For planning, the authors exhibit the functional form that is optimizable via dynamic programming.\n3) For reinforcement learning, they provide a Q-learning algorithm when the functional is linear or exponential", "questions": "See questions above.\n\nSome minor issues:\n- line 52: p_h -> p_h^a(x, \\cdot) and R_h -> R_h(x, a)\n- line 74: p_{h+1}^a(s, \\cdot)  -> p_{h+1}^a(x, \\cdot)\n- line 95: the definition of \\mathcal P_Q(\\mathbb R) should include the condition in (5)\n- line 96: W_1 should be defined here\n- line 209: m\n- line 222: \\eta vs \\eta^*\n- line 227: missing /extra word?\n- line 239: the other von Neumann-Morgenstern axioms are not needed?\n- line 269: sections addresses\n- line 271: linear of exponential", "limitations": "Not applicable", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper investigates an interesting question, which is useful for sequential decision-making with more sophisticated decision criteria.\n\nThe writing is generally quite clear.", "weaknesses": "The obtained error bound for policy evaluation seems to be very loose, as also suggested by the experiments. Can we say anything about the tightness of this bound?\n\nThe novelty of some of the obtained results seems to be limited:\n1) How different is the known result about Bellman closedness and the new result about Bellman optimizability (Theorem 2)? Isn't the former property a necessary condition for the latter?\n2) Regarding the proposed Q-learning algorithm, the linear case seems to be trivial. For the exponential case, how different is the proposed update compared to Borkar's?\n\nThe paper should be checked for typos (see below for some of them).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive and insightful feedback. Please see our response addressing your concerns and questions : \n\n- The obtained error bound for policy evaluation seems to be very loose, as also suggested by the experiments. Can we say anything about the tightness of this bound?\n\nFirst,as explained in the common response,  we found a mistake , which led to inconsistent Wasserstein distance computation and made our bound look much worse than it actually is. This was solved, and the corrected graphics can be found in the global rebuttal.  \n\nConcerning the tightness of the bound, this was investigated more in detail after the submission and added to the appendix later. Our first find is that this bound is never reached exactly for $H \\geq 1$. Yet, we believe it might not be possible to refine it in general. Indeed, the bound is proven through a main idea that is summing the successive error bounds due to the projection operator. We have made two important observations :\n \nFirst, it is possible to maximize the projection error bound at each step (meaning, at every step h, the error due to the projection operator matches the bound of Eq.6). This implies that the projection bounds cannot be improved, even after successive steps in general.\n\nThen the experiment of the paper with the corrected computation shows that in a simple environment, the sum of the successive projection errors matches very closely the overall error between the true distribution and the approximated one. This implies that the method of the proof is relevant, and may not be improved as well.\n\nCombining those two findings, we could not find an immediate improvement and we are ready to conjecture it cannot be significantly improved in general. \n\n - How different is the known result about Bellman closedness and the new result about Bellman optimizability (Theorem 2)? Isn't the former property a necessary condition for the latter?\n\nThe idea of Bellman Closedness is to find a Bellman Equation. We want to compute the values of the statistics on some state and action recursively, with the values on the other states and actions. That is, we try to find a general formula to write $s(r + PV)$ as a function of $r$ the immediate reward, $P$ the transitions and $s(V)$ where $V$ is the value function and $s$ the statistic. In short, Bellman Closedness is all about computing the values by themselves, by recursion. \n \nWith Bellman optimizability, we check instead if a policy improvement algorithm works and finds the optimal policy, without the concern of computing such values. We assume that we can compute the distribution exactly, and thus have access to the exact values of statistics. We assume that for each state and a current policy, which action maximizes the chosen statistics of the value function. The question we answer is : “Assuming we have access to the value functions for the statistic, will a policy improvement algorithm converge to an optimal policy?”\n\n- Regarding the proposed Q-learning algorithm, the linear case seems to be trivial. For the exponential case, how different is the proposed update compared to Borkar's?\n\nIn this section, we do not propose any new algorithm, both already exist and are mentioned here to recall to the viewer that our theoretical find matches the known algorithm, and to complete the full picture addressed by the paper, that is statistics in different MDP problems : Policy Evaluation, Planning, and finally Reinforcement Learning. This is also addressed in the global rebuttal.\n\n   We also thank you for pointing out typos and writing errors, we have now fixed them all and made a thorough grammatical pass on the paper.\n"}]

Author rebuttal:
**We first want to thank all the reviewers** for their constructive feedback and relevant questions that will help clarify the article. There are a few questions raised by several reviewers that we wish to address here.

### Experiments and tightness of our bound
We first want to point out **a minor but impactful bug discovered in the code**, that falsified the experiments of section 3 on the approximation of distribution and statistics. **The corrected results support even more our bounds, and proof method**. Please see the attached pdf for the corrected figures. The method supposed to return the distribution function would return a density function instead. In the notebook code sent in additional material, this can be fixed by changing the line 176 of the 2nd cell, to `probabilities = list(np.cumsum([self.distrib[atom] for atom in atoms]))` instead of `probabilities = [self.distrib[atom] for atom in atoms]`. The experiment was also changed, using a Binomial with $p=0.5$ as parameter, which is more natural. 


### Organization of the paper. 
A main objective of the paper was to depict a somewhat complete picture of what could be done in Markov Decision Processes with statistics other than expectation of the return. To do so, we wanted to address the 3 main problems that is Policy Evaluation, Control/Planning, and Reinforcement Learning, in that specific order that seemed more natural.
Our central result is Theorem 2 in the Planning section (Section 4), about the Bellman Optimizability. We agree that it is not highlighted enough in the abstract and introduction, which is now corrected.  
The section 3’s role is twofold. First, we address the question of Policy Evaluation in the undiscounted setting, and additionally provide error bounds in the case of finite parametrization of the distribution. Doing so, we are led to introduce the notion of Bellman Closedness from the literature, which is relevant to contrast with the upcoming novel definition of Bellman optimizability. We do not see how we could naturally move Section 4 before Section 3. 

### Q-Learning in Section 5 is not a contribution
**In Section 5, Algorithm 3 is from [Borkar 2002, 2010], and is not a contribution**. The reason why we report it is to complete the argument of the paper by addressing the learnability of utilities, which is the most important problem in RL. We believe that Q-learning for exponential utilities isn’t well known and we wanted to recall its existence. It is true that we do not talk about its theoretical properties, and we have added more references to point to them. We also emphasized again that this algorithm is not a contribution. 

### Definition of the Bellman Optimizability. 
The choice of definition was made according to where the idea came from and what it first implied: the impossibility to optimize other statistics, even with distributional reinforcement learning. Hence the definition using a theoretical distributional algorithm. We acknowledge that this definition is cumbersome and makes it harder to understand all the implications of our main result, the theorem 2. We take into account your feedback, and a new definition, more clear and more related to the Bellman Closedness, will be provided in the final version.


Meta-review: The paper is primarily theoretical and it examines a fundamental questions, namely what functionals of rewards can be computed and optimized exactly in an MDP.

The reviewers agree that the paper makes a contribution to a very fundamental RL question, and the paper is well presented and motivated. The empirical evaluation is somewhat limited, but this is not the purpose of the paper.
Overall, the reviewer finds the paper interesting and recommend acceptance.
Decision: Accept (poster)