Marthe Alexandre
email: alexandre.marthe@ens-lyon.fr

Umpa

Aurelien Garivier
email: aurelien.garivier@ens-lyon.fr

Claire Vernade
email: claire.vernade@uni-tuebingen.de

Beyond Average Return in Markov Decision Processes

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.

Introduction

Reinforcement Learning (RL) has emerged as a flourishing field of study, delivering significant practical applications ranging from robot control and game solving to drug discovery or hardware design [START_REF] Lazic | Data center cooling using model-predictive control[END_REF][START_REF] Popova | Deep reinforcement learning for de novo drug design[END_REF][START_REF] Volk | Alphaflow: autonomous discovery and optimization of multi-step chemistry using a self-driven fluidic lab guided by reinforcement learning[END_REF][START_REF] Mirhoseini | Chip placement with deep reinforcement learning[END_REF]. The cornerstone of RL is the "return" value, a 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 to be solved through dynamic programming with the Bellman equations [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]Barto, 2018, Szepesvári, 2010]. RL theory has seen considerable expansion, with a renewed interest for the consideration of more rich descriptions of a policy's behavior than the sole average return. At the other end of the spectrum, the so-called Distributional Reinforcement Learning (DistRL) approach aims at studying and optimizing the entire return distribution, leading to impressive practical results [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF][START_REF] Hessel | Rainbow: Combining Improvements in Deep Reinforcement Learning[END_REF][START_REF] Wurman | Outracing champion Gran Turismo drivers with deep reinforcement learning[END_REF][START_REF] Fawzi | Discovering faster matrix multiplication algorithms with reinforcement learning[END_REF]. 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 [START_REF] Bernhard | Addressing inherent uncertainty: Risk-sensitive behavior generation for automated driving using distributional reinforcement learning[END_REF][START_REF] Mowbray | Distributional reinforcement learning for scheduling of chemical production processes[END_REF].

Despite recent progress, the full understanding of the abilities and limitations of DistRL to compute other functionals remains incomplete, with the underlying theory yet to be fully understood. Historically, the theory of RL has been established for discounted MDPs, see e.g. [START_REF] Sutton | Reinforcement learning: An introduction[END_REF][START_REF] Watkins | Q-learning[END_REF][START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF], Bellemare et al., 2023] for modern reference textbooks. Recently more attention was drawn to the undiscounted, finite-horizon setting [Auer, 2002, 37th Conference on Neural Information Processing Systems (NeurIPS 2023). [START_REF] Osband | more) efficient reinforcement learning via posterior sampling[END_REF][START_REF] Jin | Is q-learning provably efficient? Advances in neural information processing systems[END_REF][START_REF] Ghavamzadeh | Exploration in reinforcement learning[END_REF], 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 DistRL.

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 [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF]'s results on Bellman closedness and provide their adaptation to 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 a 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 a 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 not extend the class of functionals for which planing is possible beyond what is already allowed by classical dynamic programming.

Background

We introduce the classical RL framework in finite-horizon tabular Markov Decisions Processes (MDPs). We write P(R) the space of probability distributions on R. A finite-horizon tabular MDP is a tuple M = (X , A, p, R, H), where X is a finite state space, A is a finite action space, H is the horizon, for each h ∈ [H], p h (x, a, •) is a transition probability law and R h (x, a) is a reward random variable with distribution ϱ h . The parameters (p h ) and (R h ) define the model of dynamics. A deterministic policy on M is a sequence π = (π 1 , . . . , π H ) of functions π h : X → A.

Reinforcement Learning traditionally focuses on learning policies optimizing the expected return. For a given policy π, the Q-function maps a state-action pair to its expected return under π:

Q π h (x, a) = E ϱ h [R h (x, a)] + s ′ p h (x, a, x ′ )Q π h+1 (x ′ , π h+1 (x ′ )), Q π H+1 (x, a) = 0 . (1)
When the model is 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:

Q * h (x, a) = E ϱ h [R h (x, a)] + x ′ p h (x, a, x ′ ) max a ′ Q * h+1 (x ′ , a ′ ), Q * H+1 (x, a) = 0 . (2)
Solving this equation when the model is known is also called Planning. When it 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.

Distributional RL

Distributional RL (DistRL) refers to the approach that tracks not just a 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 [START_REF] Bellemare | Distributional Reinforcement Learning[END_REF] 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 [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF] to more complex metrics [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF], Dabney et al., 2018a[START_REF] Liang | Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds[END_REF].

At state-action (x, a), let Z π h (x, a) denote the future sum of rewards when following policy π and starting at step h, also called return. It verifies the simple recursive formula Z

π h (x, a) = R h (x, a) + Z π h+1 (X ′ , π h+1 (X ′ )) where X ′ ∼ p h+1 (x, a, •). Its distribution is η = (η π h (x, a)) (x,a,h)∈X ×A×[H]
and is 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 ν 1 , ν 2 ∈ P(R), we denote their convolution by ν 1 * ν 2 (t) = R ν 1 (τ )ν 2 (t -τ )dτ . For any two independent random variables X and Y , the distribution of the sum Z = X + Y is the convolution of their distributions:

ν Z = ν X * ν Y . Thus, the law of Z π h (x, a) is ∀x, a, h, η π h (x, a) = ϱ h (x, a) * x ′ p h (x, a, x ′ )η π h (x ′ , π h+1 (x ′ )) . ( 3
)
This equation is a distributional equivalent to Eq. ( 1) and thus defines a distributional Bellman operator η π h = T π h η π h+1 . Obviously, from a practical point of view, distributions form a non-parametric family that is not computationally tractable. It is necessary to choose a parametric (thus incomplete) family to represent them. Even the restriction to discrete reward distributions is not tractable, since the number of atoms in the distributions may grow exponentially with the number of steps1 [START_REF] Achab | Robustness and risk management via distributional dynamic programming[END_REF]: approximations are unavoidable. The most natural solution is 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 to Eq. ( 1) in DistRL hence writes

∀x, a, h, ηπ h (x, a) = Π ϱ h (x, a) * x ′ p h (x, a, x ′ )η π h+1 (x ′ , π h+1 (x ′ )) , ( 4
)
where Π is the projector operator on the parametric family. The full policy evaluation algorithm in DistRL is summarized in Alg.1.

Algorithm 1 Policy Evaluation (Dynamic Programming) for Distributional RL Input: model p, reward distributions ϱ h , policy π to evaluated, Π projection.

Data: η ∈ R H|X ||A|N ∀x, a ∈ X × A, η H (x, a) = δ 0 for h = H -1 → 0 do η h (x, a) = ϱ h (x, a) * x ′ p h (x, a, x ′ )η h+1 (x ′ , π h+1 (x ′ )) ∀x, a ∈ X × A η h (x, a) = Π (η h (x, a)) ∀x, a ∈ X × A end for Output: η h (x, a)∀x, a, h
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 of the source distribution. One main benefit is that it does not require a previous knowledge of the support of the distribution, and allows for unbounded distributions.

The quantile projection is defined as

Π Q µ = 1 N N -1 i=0 δ zi , with (z i ) i chosen such as F µ (z i ) = 2i + 1 2N , (5)
which corresponds to a minimal W 1 distance: Π Q µ ∈ arg min μ= i δi/N W 1 (µ, μ), where W 1 (., .) is the Wasserstein distance defined for any distributions

ν 1 , ν 2 as W 1 (ν 1 , ν 2 ) = 1 0 F -1 ν1 (u) -F -1 ν2 (u) du.
Note that this parametrization might admit several solutions and thus the projection may not be unique. For simplicity, we overload the notation to

Π Q η = (Π Q η(x, a)) (x,a)∈X ×A
For a Q-value distribution η with support of length ∆ η , and parametrization of resolution N , [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] prove that the projection error is bounded by

sup (x,a)∈X ×A W 1 (Π Q η(x, a), η(x, a)) ≤ ∆ η 2N . (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 [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF][START_REF] Rowland | An Analysis of Categorical Distributional Reinforcement Learning[END_REF]][Bellemare et al., 2023] in Appendix B.

Beyond expected returns

The expected value is an important functional of a probability distribution, but it is not the only one of interest in decision theory -especially when a 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 on certain quantiles.

Expected Utilities are of the form E[f (Z)], or f dν, where Z is the return of distribution ν and f is an increasing function. For instance, when f is a 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 as exponential utility, exponential risk measure, or generalized mean according to the context:

U exp (ν) = 1 λ log E exp(λX) X ∼ ν and λ ∈ R . ( 7
)
This family of utilities has a variety of applications in finance, economics, and decision making under uncertainty [START_REF] Föllmer | Stochastic Finance: An Introduction in Discrete Time[END_REF]. They can be considered as a risk-aware generalization of the expectation, with benefits such as accommodating a wide range of behaviors [START_REF] Shen | Risk-sensitive reinforcement learning[END_REF] from risk-seeking when λ > 0, to risk-averse when λ < 0 (the limit λ → 0 is exactly the expectation). To fix ideas, U exp N (µ, σ 2 ) = µ + λσ 2 : each λ captures a certain quantile of the Gaussian distribution.

Distorted means, on the other hand, involve taking the mean of a random variable, but with a different weighting scheme [Dabney et al., 2018a]. The goal is to place more emphasis on certain quantiles, which can be achieved by considering the quantile function F -1 of the random variable and a continuous increasing function β : [0, 1] → [0, 1]. By applying β to a 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 of this new random variable, given by the formula β ′ (τ )F -1 (τ )dτ . If β is the identity function, the result is the classical mean. When β is τ → min(τ /α, 1), we get the α-Conditional Value at Risk (CVaR(α)) of the return, a risk measure widely used in risk evaluation [START_REF] Rockafellar | Optimization of conditional value-at-risk[END_REF].

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 to 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, as was already noticed in the 1980's [START_REF] Sobel | The variance of discounted Markov decision processes[END_REF]. Recently, [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] showed that for utilities in discounted MDPs, this is essentially all that can be done. More precisely, they introduce the notion of 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 [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF]). A set of statistical functionals {s 1 , . . . s K } is said to be Bellman closed if for each (x, a) ∈ X × A, the statistics s 1:K (η π h (x, a)) can be expressed in closed form in terms of the random variables R h (x, a) and (s

1:K (η π h+1 (X ′ , A ′ )), A ′ ∼ π(x), X ′ ∼ p h (x, A ′ , •), independently of the MDP.
Importantly, in the undiscounted setting, [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF](Appendix B, Theorem 4.3) show that the only families of utilities that are Bellman closed are of the form {x → x ℓ exp(λx)|0 ≤ ℓ ≤ L} for some L < ∞. 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 RL (see Appendix A.3). Some important metrics such as the CVaR or the quantiles are not known to belong to any Bellmanclosed set and hence cannot be easily computed. For this kind of function of the return, the knowledge of the transitions and the values in 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 [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] (see Eq.( 6)), we prove that the Wasserstein distance error between the exact and approximate distribution of the Q-values of a policy is bounded. Proposition 1. Let π be a policy and η π the associated Q-value distributions. Assume the return is bounded on a interval of length ∆ η ≤ H∆ R , where ∆ R is the support size of the reward distribution. Let ηπ be the Q-value distributions obtained by dynamic programming (Algorithm 1) using the quantile projection Π Q with resolution N . Then,

sup (x,a,h)∈(X ,A,[H]) W 1 (η π h (x, a), η π h (x, a)) ≤ H ∆ η 2N ≤ H 2 ∆ R 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-expansion property of the Bellman operator [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF]. The details can be found in Appendix C

The key question is 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 ν 1 , ν 2 be return distributions. Then:

|s(ν 1 ) -s(ν 2 )| ≤ LW 1 (ν 1 , ν 2 ) .
Both family of functionals are treated separately, but lays a similar bound. The utility bound is the direct application of the Kantorovitch-Rubenstein duality, while the distorted mean one is a direct majoration in the integral. Again, the details are provided in the Appendix.

This property allows us to prove a maximal upper bound on the estimation error for those two families. Theorem 1. Let π be a policy. Let η π be the Q-value return distribution associated to π with the return bounded on a interval of length ∆ η ≤ H∆ R where ∆ R is the support size of the reward distribution. Let ηπ be the approximated return distribution computed with Algorithm 1, for the projection Π Q with resolution N . Let s be either an expected utility or a distorted mean, and L the Lipschitz coefficient of its characteristic function. Then:

sup x,a,h |s(η π h (x, a)) -s(η π h (x, a))| ≤ LH ∆ η 2N ≤ LH 2 ∆ R 2N .
Note that depending on the choice of utilities, the Lipschitz coefficient L may also depend on H and ∆R. For instance, in a stationary MDP, the Lipschitz constant of the exponential utility depends exponentially on ∆ η . For the CVaR(α), however, L is constant and only depends on α ∈ (0, 1).

Experiment: empirical validation of the bounds on a simple MDP We consider a simple Chain MDP environment of length H = 70 equal to the horizon (see Figure 1 (right)) [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF], with a single action leading to the same discrete reward distribution for every step. We consider a Bernouilli reward distribution B(0.5) for each state so that the number of atoms for the return only grows linearly2 with the number of steps, which allows to compute the exact distribution easily. 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 2.

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 at 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. 1 upper bounds the distance between distributions by the cumulative projection error so we plot this quantity to help validating it.

We also empirically validate Theorem 1 by computing the CVaR(α) for α ∈ {0.1, 0.25}, corresponding respectively to distorted means with Lipschitz constants L = {10, 4}. We compute these statistics for both distributions and report the maximal error together with the theoretical bound, re-scaled3 by a factor 5. Figure 2 (Left) shows an impressive correspondence of the theory and the empirical results despite a constant multiplicative gap.

Planning

Planning refers to the problem of returning a policy that optimizes our objective for a given model and reward function (or distribution in DistRL). It shares with policy evaluation the property to be grounded on a Bellman equation: see 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 Bellman-closed 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 a Bellman Equation. In fact, for the exponential utilities, such Bellman Equation exists and allows for the planning problem to be solved efficiently [START_REF] Howard | Risk-Sensitive Markov Decision Processes[END_REF]:

Q λ h (x, a) = U λ exp (R h (x, a)) + 1 λ log x ′ p h (x, a, x ′ ) exp λ max a ′ Q λ h+1 (x ′ , a ′ ) (8)
with Q λ H+1 (x, a) = 0 . However, the question of the existence of Optimal Bellman Equations for non-utility functionals remains open (e.g. quantiles). More generally, an efficient planning strategy is not known. To address these questions, we consider the most general framework, DistRL, and recall the theoretical DP equations for any statistical functional s in the Pseudo4 -Algorithm 2. DistRL offers the most comprehensive, or 'lossless', approach, so if a statistical functional cannot be optimized with Alg. 2, then there cannot exist a Bellman Operator to perform exact planning.

Algorithm 2 Pseudo-Algorithm: Exact Planning with Distributional RL 1:

Input: model p, reward R, statistical functional s 2: Data: η ∈ R H|X ||A|N , ν ∈ R H|X |N 3: ∀x ∈ X , ν x H+1 = δ 0 4: for h = H → 1 do 5: η h (x, a) = ϱ (x,a) h * x ′ p a h (x, x ′ )ν x ′ h+1 ∀x, a ∈ X × A 6: ν x h = η h (x, a * ) , a * ∈ arg max a s(η h (x, a)) ∀x ∈ X 7: end for 8: Output: η h (x, a) ∀x, a, h
We formalize this idea with the new concept of Bellman Optimizable statistical functionals: Definition 2 (Bellman Optimizable statistical functional). A statistical functional s is called Bellman optimizable if, for any MDP M, the Pseudo-Algorithm 2 outputs an optimal return distribution η = η * that verifies:

∀x, a, h, s(η * h (x, a)) = sup π s(η π h (x, a)) . (9)
Remark. This definition is equivalent to the satisfaction of an Optimal Distributionnal Bellman equation. Indeed, a statistical functional s is Bellman Optimizable if and only if, for any (X , A, ϱ, p, η), s verifies sup

a x ′ s ϱ * x ′ p(x ′ )η(x ′ , a x ′ ) = s ϱ * x ′ p(x ′ )η(x ′ , a * x ′ )
with a ⋆ x ∈ arg max a s(η(x, a))

We can now state our main results that characterizes all the Bellman optimizable statistical functionals. First, we prove that such a functional must satisfy two important properties. Lemma 2. A Bellman optimizable functional s satifies the two following properties:

• Independence Property: If ν 1 , ν 2 ∈ P(R) are such that s(ν 1 ) ≥ s(ν 2 ), then ∀ν 3 ∈ P(R), ∀λ ∈ [0, 1], s(λν 1 + (1 -λ)ν 3 ) ≥ s(λν 2 + (1 -λ)ν 3 )) .
• Translation Property: Let τ c denote the translation on the set of distributions:

τ c δ x = δ x+c . If ν 1 , ν 2 ∈ P(R) are such that s(ν 1 ) ≥ s(ν 2 ), then ∀c ∈ R, s(τ c ν 1 ) ≥ s(τ c ν 2 ) .
Indeed, the expectation and the exponential utility both satisfy these properties (see Appendix A.2). Each property is implied by an aspect of the Distributional Bellman Equation (Alg. 2, line 5) and the proof (in Appendix E) unveils these important consequences of the recursion identities.

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 it 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 [START_REF] Neumann | Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition)[END_REF]. 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 s 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 ∀ν 1 , ν 2 ∈ P(R), we have [START_REF] Neumann | Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition)[END_REF][START_REF] Grandmont | Continuity properties of a von neumann-morgenstern utility[END_REF].

s(ν 1 ) > s(ν 2 ) ⇐⇒ U f (ν 1 ) > U f (ν 2 ) [von
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, momentoptimal 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 W 1 -continuous functional satisfies this property.

Theorem 2. Let ϱ be a return distribution. The only W 1 -continuous Bellman Optimizable statistical functionals of the cumulated return are exponential utilities

U exp (ϱ) = 1 λ log E ϱ [exp(λR)] for λ ∈ R, with the special case of the expectation E ϱ [R] when λ = 0.
Of course, if U (ρ) is a utility and ψ is a monotonous scalar mapping, ψ(U (ρ)) is an equivalent utility: one should understand in the previous theorem that a W 1 -continuous Bellman Optimizable statistical functional is equivalent to U exp (ϱ) for some λ ∈ R. We chose here to define U exp (ϱ) = 1 λ log E ϱ [exp(λR)] with the log and the factor 1/λ since it results in a normalized utility that tends to the expectation when λ goes to 0. The full proof of Theorem 2 is provided in Appendix E.

We make a 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 W 1 -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 DistRL. 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 [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF][START_REF] Hessel | Rainbow: Combining Improvements in Deep Reinforcement Learning[END_REF]. Some advantages of learning the distribution lies in the enhanced robustness offered in the richer information learned [START_REF] Rowland | The Statistical Benefits of Quantile Temporal-Difference Learning for Value Estimation[END_REF], particularly when utilizing neural networks for function approximation [START_REF] Dabney | Distributional Reinforcement Learning With Quantile Regression[END_REF][START_REF] Barth-Maron | Distributed distributional deterministic policy gradients[END_REF][START_REF] Lyle | A Comparative Analysis of Expected and Distributional Reinforcement Learning[END_REF].

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 learnt5 . 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 a lesser known version of Q-Learning [START_REF] Watkins | Q-learning[END_REF] that extend this celebrated algorithm to exponential utilities. We provide the pseudo-code for the algorithm proposed by Borkar Algorithm 3 Q-Learning for Linear and Exponential Utilities 1: Input: (α t ) t∈N , transition and reward generator.

Q h (x, a) ← H , ∀(x, a, h) ∈ X × A × [H] 2: Utilities: Linear (Z → λZ + b) or Exponential (Z → log(E exp(λZ))/λ) 3: for episode K = 1, . . . , K do 4: Observe x 1 ∈ X 5:
for step h = 1, . . . , H do 6:

Choose action a h ∈ arg max a∈A Q h (x h , a)

7:

Observe reward r h and transition x h+1 and update for chosen objective: 8: Linear Util.:

Q h (x h , a h ) ← (1 -α k )Q h (x h , a h ) + α k [λ(r h + max a ′ Q h+1 (x h+1 , a ′ )) + b] 9: Exponential Util.: Q h (x h , a h ) ← 1 λ log (1 -α k )e λ•Q h (x h ,a h ) + α k e λ[r h +max a ′ Q h (x h+1 ,a ′ )] 10:
end for 11: end for 12: Output: Q h (x, a)∀x, 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 [START_REF] Watkins | Q-learning[END_REF].

Discussions and Related Work

The Discounted Framework We focused in this article on undiscounted MDPs, and it is important to 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 γ [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF]. When it comes to Bellman Optimization, the necessary translation property becomes an affine property : ∀c, γ, s(τ γ c ν 1 ) > s(τ γ c ν 2 ) where τ γ c is the affine operator such that τ γ c δ x = δ γx+c . This property is not upheld by the exponential utility. Nonetheless, there exists a method to optimize the exponential utility through dynamic programming in discounted MDPs [START_REF] Chung | Discounted MDP's: Distribution Functions and Exponential Utility Maximization[END_REF]. This approach requires modifying the functional to optimize at each step (the step h is optimized with the utility x → exp(γ -h λ x)), but it also implies a loss of policy stationarity, property usually obtained in dynamic programming for discounted finite-horizon MDPs [START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

Utilizing functionals to optimize expected return. DistRL has also been used in Deep Reinforcement learning to optimize non-Bellman-optimizable functionals such as distorted means [START_REF] Ma | DSAC: Distributional Soft Actor Critic for Risk-Sensitive Reinforcement Learning[END_REF], 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 as a change in the exploration process, and the resulting risk-sensitive behaviors seem to be relevant in adequate environments.

Dynamic programming for the optimization of other functionals

To optimize other statistical functionals such as CVaR and other utilities such as moments with Dynamic Programming, [START_REF] Bäuerle | Markov Decision Processes with Average-Value-at-Risk criteria[END_REF] and [START_REF] Bäuerle | More Risk-Sensitive Markov Decision Processes[END_REF] propose to extend the state space of the original MDP to X ′ = X × R by theoretically adding a continuous dimension to 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 formulation of RL through the empirical state distribution [START_REF] Hazan | Provably efficient maximum entropy exploration[END_REF]. Algorithms can be derived by noticing that utilities like the CVar are equivalent to solving a convex RL problem [START_REF] Mutti | Convex reinforcement learning in finite trials[END_REF].

Conclusion

Our work closes an important open problem in the theory of 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 DistRL.

A Additional remarks

The Wasserstein metric is defined as

W 1 (ν 1 , ν 2 ) = 1 0 F -1 ν1 (u) -F -1 ν2 (u) du and the Cramer metric as ℓ 2 (ν 1 , ν 2 ) = +∞ -∞ |F ν1 (u) -F ν2 (u)| 2 du 1 2
. For both metrics, we de-

fine their supremum ℓ 2 (η 1 , η 2 ) = sup (x,a)∈X ×A ℓ 2 (η 1 (x, a), η 2 (x, a)) and W 1 (η 1 , η 2 ) = sup (x,a)∈X ×A W 1 (η 1 (x, a), η 2 (x, a)).
A.1 Remarks on the recursive definition of the Q-value distribution

The notation of the Q-value distribution η is often deceivingly complex compared to the actual object it means to represent. While the 'usual' expected Q-function Q(x, a) is simply understood as the expected return of a policy at state-action pair (x, a), DistRL requires us to keep a notation for the complete distribution of the return. In other words, the Q-value distribution η

(x,a)
π,h should be understood as the distribution of the random variable Z = R + Z(S ′ ), which is the convolution of the individual distributions of these two independent random variable. It can also be written:

∀x, a, h, η π h (x, a) = x ′ ,a ′ p h (x, a, x ′ )π x ′ h+1 (a ′ )η π h+1 (x ′ , a ′ )(• -r)R (x,a) h (dr) . ( 10
)
A.2 Linear and Exponential Utilities satisfy the properties of Lemma 2 Independence Property Any utility U f verifies the independence property. Let

ν 1 , ν 2 , ν 3 ∈ P(R), λ ∈ [0, 1]. Assume U f (ν 1 ) ≥ U f (ν 2 ). Then, U f (λν 1 + (1 -λ)ν 3 ) = f d(λν 1 + (1 -λ)ν 3 ) = λ f dν 1 U f (ν1) +(1 -λ) f dν 3 ≥ λ f dν 2 U f (ν2) +(1 -λ) f dν 3 = f d(λν 2 + (1 -λ)ν 3 ) = U f (λν 2 + (1 -λ)ν 3 )
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

ν 1 , ν 2 ∈ P(R), c ∈ R. Assume that U exp (ν 1 ) ≥ U exp (ν 2 ) and U mean (ν 1 ) ≥ U mean (ν 2 ). Then, U exp (τ c ν 1 ) = exp(r)dτ c ν 1 (r) = exp(r + c)dν 1 (r) = exp(c) exp(r)dν 1 (r) = exp(c)U exp (ν 1 ) ≥ exp(c)U exp (ν 2 ) = . . . = U exp (τ c ν 2 ) U mean (τ c ν 1 ) = λτ + b + cdτ = c + U mean (ν 1 ) ≥ c + U mean (ν 2 ) = . . . = U mean (τ c ν 2 )
A.3 Policy Evaluation for linear combinations of moments [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] prove a necessary condition on Bellman-closed utilities, namely that they should be a family of the form {x → x ℓ exp(λx)|0 ≤ ℓ ≤ L} for the undiscounted, finite-horizon setting. In the discounted case, the necessary condition is only valid for λ = 0, 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, a similar result has not yet been proved. We provide here the sufficient condition for families of the form {x → x ℓ exp(λx)|0 ≤ ℓ ≤ L}. We show that they are Bellman-closed and that this implies that they can be computed by DP.

Let's consider the family s k (ν) = r k exp(λr)dν(r) for k ∈ [n] and some fixed λ ∈ R.

sn(η π h (x, a)) = E [Z π h (x, a) n exp(λZ π h (x, a))] = E (R h (x, a) + Z π h+1 (X ′ , A ′ )) n exp(λ(R h (x, a) + Z π h+1 (X ′ , A ′ )) = E x ′ ,a ′ ER h ,Z h+1 (R h (x, a) + Z π h+1 (x ′ , a ′ )) n exp(λ(R h (x, a) + Z π h+1 (x ′ , a ′ ))|X ′ = x ′ , A ′ = a ′ = x ′ ,a ′ p h (x, a, x ′ )π x ′ h (a ′ )ER h ,Z h+1 (R h (x, a) + Z π h+1 (x ′ , a ′ )) n exp(λ(R h (x, a) + Z π h+1 (x ′ , a ′ )) = x ′ ,a ′ p h (x, a, x ′ )π x ′ h (a ′ )ER h ,Z h+1 n k=0 n k R h (x, a) n-k exp(λR h (x, a))Z π h+1 (x ′ , a ′ ) k exp(λZ π h+1 (x ′ , a ′ ) = x ′ ,a ′ p h (x, a, x ′ )π x ′ h (a ′ ) n k=0 n k ER h R h (x, a) n-k exp(λR h (x, a)) EZ h+1 Z π h+1 (x ′ , a ′ ) k exp(λZ π h+1 (x ′ , a ′ ) = x ′ ,a ′ p h (x, a, x ′ )π x ′ h (a ′ ) n k=0 n k ER h R h (x, a) n-k exp(λR h (x, a)) s k (η π h+1 (x ′ , a ′ ))
This first proves that this family of statistical functional is Bellman closed: they can be expressed as a 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 a natural way to evaluate these functionals by DP.

B Categorical Projection: an alternative parametrization

The categorical projection was proposed and studied in [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF], [START_REF] Rowland | An Analysis of Categorical Distributional Reinforcement Learning[END_REF], [START_REF] Bellemare | Distributional Reinforcement Learning[END_REF]. For a bounded return distribution, it spreads a fixed number N of Diracs evenly over the support and used weight parameters to represent the true distribution. The parameter N is often referred to as the resolution of the projection. More precisely, on a support [V min , V max ],

we write ∆ = Vmax-Vmin N -1 the step between atoms

z i = V min + i∆, i ∈ [[0, N -1]].
We define the projection of a given Dirac distribution δ y on the parametric space

P C (R) = { i p i δ zi | 0 ≤ p i ≤ 1, i p i = 1} by Π C (δ y ) =      δ z0 y ≤ z 0 zi+1-y zi+1-zi δ zi + y-zi zi+1-zi δ i+1 z i < y < z i+1 δ z N -1 y ≥ z N -1 (11)
This definition can naturally be extended to any bounded distribution ν, and by extension, Π C η = (Π C η(s, a)) (s,a)∈X ×A . This linear operator minimizes the Cramér distance of the parametrization to the parametric space [START_REF] Rowland | An Analysis of Categorical Distributional Reinforcement Learning[END_REF].

This projection verifies this approximation bound, analog to the quantile projection,

sup (x,a)∈X ×A ℓ 2 (Π C η(x, a), η(x, a)) ≤ ∆ η N . (12)
Using the property that

W 1 (ν 1 , ν 2 ) ≤ √ ∆ η ℓ 2 (ν 1 , ν 2 )
, the results with the quantile projection can be adapted for the categorical projection, adding

√

∆ η factors to the bounds.

This parametrization has the nice property of preserving the mean of the distribution. Yet, even for risk-neutral RL, Quantile-based DistRL algorithm seem to work better and display better properties [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 η π the associated Q-value distributions.

Assume the return is bounded on a interval of length ∆ η ≤ H∆ R , where ∆ R is the support size of the reward distribution. Let ηπ be the Q-value distributions obtained by dynamic programming (Algorithm 1) using the quantile projection Π Q with resolution N . Then,

sup (x,a,h)∈(X ,A,[H]) W 1 (η π h (x, a), η π h (x, a)) ≤ H ∆ η 2N ≤ H 2 ∆ R 2N .
To avoid clutter of notation, we denote W 1 (η, η) := sup (x,a)∈X ×A W 1 (η(x, a), η(x, a)).

Proof. First recall that for any Q-value distribution (η h ) h∈ [H] , with the return bounded on an interval of length ∆ η ≤ H∆ R , and Π one of the projection operator of interest with resolution n, we have the following bound on the projection estimation error due to [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] (Eq (6)):

W 1 (Πη, η) ≤ ∆ η 2N . ( 13
)
At a fixed step h ∈ [H], we have the following inequality:

W 1 (η π h , η π h ) = W 1 (ΠT π h ηπ h+1 , T π h η π h+1 ) ≤ W 1 (ΠT π h ηπ h+1 , T π h ηπ h+1 ) + W 1 (T π h ηπ h+1 , T π h η π h+1 ) (14) ≤ H ∆ R 2N + W 1 (η π h+1 , η π h+1 ) . (15)
Where ( 14) is due to the triangular inequality with T π h ηπ h+1 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 [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF]:

W 1 (T η 1 , T η 2 ) ≤ W 1 (η 1 , η 2 ) .
Using it recursively starting from h = 1, and using the fact that ηπ H = η π H we get:

W 1 (η π 1 , η π 1 ) ≤ H ∆ R 2N + W 1 (η π 2 , η π 2 ) ≤ 2H ∆ R 2N + W 1 (η π 3 , η π 3 ) ≤ • • • ≤ H 2 ∆ R 2N .

C.2 Proof of Lemma 1

We recall the statement of Lemma 1: Let s be either a utility or a distorted mean and let L be the Lipschitz coefficient of its characteristic function. Let ν 1 , ν 2 be return distributions. Then:

|s(ν 1 ) -s(ν 2 )| ≤ LW 1 (ν 1 , ν 2 ) .
Proof. We prove the property for each family of utilities separately:

Case 1: s is a utility. There exists f such that s(ν) = f dν. Let L f be its Lipsichtz constant. The Kantorovitch-Rubenstein duality [START_REF] Villani | Topics in Optimal Transportation[END_REF] states that:

W 1 (ν 1 , ν 2 ) = 1 L f sup ||g|| L ≤L f g dν 1 -g dν 2 , ( 16
)
where || • || L is the Lipschitz norm. We then immediatly get:

L f W 1 (ν 1 , ν 2 ) ≥ f dν 1 -f dν 2 = |s(ν 1 ) -s(ν 2 )| . ( 17
)
Case 2: s is a distorted mean. There exists g such that s(ν) = 1 0 g ′ (τ )F -1 ν (τ )dτ . Let L g be its Lipschitz coefficent. Thus:

|s(ν 1 ) -s(ν 2 )| = 1 0 g ′ (τ ) F -1 ν1 -F -1 ν2 (τ ) dτ ≤ ||g ′ || ∞ 1 0 F -1 ν1 (τ ) -F -1 ν2 (τ ) dτ ≤ L g W 1 (ν 1 , ν 2 ) .

D About the tightness of Theorem 1

The upper bound provided by Theorem 1 is mainly based on Proposition 1. The latter is obtained by summing, for every step, the Projection Bound by [START_REF] Rowland | Statistics and Samples in Distributional Reinforcement Learning[END_REF] (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 it would require to 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 of 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 us consider a family of distributions for which the projection error is tight:

Proposition 2. Let N ∈ N, ∆ ∈ R + . Consider z i = i∆ N . The distribution ν N,∆ = 1 2N N -1 i=0 (δ zi + δ zi+1 )
has a support of length ∆ and verifies

W 1 (ν N,∆ , Π Q ν N,∆ ) = ∆ 2N .
Proof. The cumulative distribution function (CDF) the distribution ν N,∆ is

F ν N,∆ (x) =    0 x < 0 = z 0 , 2i+1 2N = τ i z i ≤ x < z i+1 , 1 x ≥ 1 = z N .
We write τ i = 2i+1 2N , so that ∀i ∈ [|0, N -1|], F ν N,∆ (z i ) = τ i . We now explicit the projection of ν N,∆ and the Wasserstein distance relative to it. A possible Quantile projection is

Π Q ν N,∆ = 1 N N -1 i=0 δ zi , and W 1 (ν N,∆ , Π Q ν N,∆ ) = 1 0 |F -1 ν (w) -F -1 Π Q ν (w)|dw = N -1 i=0 i+1 N i N |F -1 ν (w) -F -1 Π Q ν (w) zi |dw = N -1 i=0 τi i N | F -1 ν (w) zi -z i |dw + i+1 N τi | F -1 ν (w) zi+1 -z i |dw = N -1 i=0 1 2N (z i+1 -z i ) ∆ N = N -1 i=0 ∆ 2N 2 = ∆ 2N
The value distribution of the following time steps is 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 Π Q T ν N1∆1 = ν N2∆2 , where the Bellman operator simply consists in the added reward distribution.

Proposition 3. Let N ∈ N, ∆ ∈ R + . Consider ϱ = 1 2 (δ 0 + δ ∆ N -1
). Then there exists a Quantile projection operator

Π Q such that ϱ * Π Q (ν N,∆ ) = ν N,(∆+ ∆ N -1 ) Proof. We consider Π Q (ν N,∆ ) = 1 N N -1 i=0 δ i∆ N -1 . Since ∀i, i∆ N -1 ≤ z i < (i+1)∆ N -1 , we have F (z i ) = τ i , verifying that it is indeed a valid Quantile Projection. Hence, ϱ * Π Q (ν N,∆ ) = 1 2 (δ 0 + δ ∆ N -1 ) * 1 N N -1 i=0 δ i∆ N -1 = 1 N N -1 i=0 1 2 (δ 0 + δ ∆ N -1 ) * δ i∆ N -1 = 1 2N N -1 i=0 δ i∆ N -1 + δ (i+1)∆ N -1 = ν N,(∆+ ∆ N -1 )
The last egality comes down to noticing that i∆ N -1 = i N (∆ + ∆ N -1 ).

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 ∈ N, ∆ 0 ∈ R + . Consider the sequence ∆ h+1 = ∆ h (1 + 1 N -1 ) and ϱ h = 1 2 (δ 0 + δ ∆ h N -1
). Consider Π Q as in Prop. 3. Consider the MDP with only one state x and action a, reward distribution ϱ h , horizon H. Consider ηh 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:

W 1 (Π Q η h , η h ) = ∆ h 2N
While the projection error is maximal in such instance, it was verified experimentally that the bound in Prop. 1 was still not tight. This comes from the fact that the Bellman operator is not a non-contraction is this case, and that the triangular inequality used to sum the projection error is not tight either.

We hence found that every inequality used in proving Theorem 1 can be tight, but there does not seem to exist an instance for which all the inequalities are tight at the same time, meaning that this bound would be 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 of Lemma 2 (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 the full 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 s be a Bellman optimizable statistical functional that does not satisfy the Independence property. That is, there exists ν 1 , ν 2 , ν 3 ∈ P(R) and λ ∈

[0, 1] such that s(ν 1 ) ≥ s(ν 2 ) but s(λν 1 + (1 -λ)ν 3 ) < s(λν 2 + (1 -λ)ν 3 ) .
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 2 actions, a unique but random and non-rewarding one (a 0 ) and a final deterministic step (a 1 or a 2 ) to a rewarding state. Thus, by construction, the optimal strategy is (a 0 , a 2 ) that leads to End 2 with probability λ (and End 3 with probability 1 -λ). The true optimal distribution at Start state is η * 0 = λν 2 + (1 -λ)ν 3 . We compute the distributions output by the algorithm: The output return distribution η 0 is not the true optimal η * 0 for s so the algorithm is incorrect which is a contradiction as s is assumed to be Bellman optimizable. Hence the property is needed.

H = 2 : η 2 (
Translation Property Let s be a Bellman optimizable statistical functional that does not verify the Translation Property, i.e. there exists ν 1 , ν 2 ∈ P(R), c ∈ R such that s(ν 1 ) ≥ s(ν 2 ) but s(τ c ν 1 ) < s(τ c ν 2 ) . Then consider MDP in Fig. 4 (right). The optimal strategy is again (a 0 , a 2 ) by construction. The algorithm output the following distribution: So here again, the algorithm does not output an optimal distribution for s, hence the necessity of the property.

This proof shows that both properties are necessary, but not that they are 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 we already know is bellman optimizable.

E.2 Proof of Theorem 2

Proof. For any return distribution ν, let s(ν) be the considered functional. Since we assume that s is W 1 -continuous Bellmman optimizable, the by the Independence Property (Lemma 2) we know from the Expected Utility Theorem that we can assume: s(ν) = s f (ν) = R f (x)dν(x) for some continuous, monotonous mapping f . Without loss of generality, we may assume by a density argument that f is twice continuously differentiable.

By the Intermediate Value Theorem, we can then define ϕ(h) = f -1 ( 1 2 (f (0) + f (h))), so that 1 2 (f (0) + f (h)) = f (ϕ(h)) and in particular ϕ(0) = f -1 (f (0)) = 0.

A very special case is when f is constant, which satisfies the theorem. We now assume that there exists point x 0 such that f ′ does not vanish on a neighborhood of x 0 . On this neighborhood, using the inverse function theorem, ϕ is also twice differentiable. Without loss of generality, we assume that x 0 = 0.

For any fixed h > 0, we consider the probability distributions ν 1 = 1 2 (δ 0 + δ h ) and ν 2 = δ ϕ(h) . Remark that s f (ν 1 ) = f dν 1 = 1 2 (f (0) + f (h)) and s f (ν 2 ) = f (ϕ(h)) = 1 2 (f (0) + f (h)) by definition of ϕ, so s f (ν 1 ) = s f (ν 2 ) .

The Translation property implies that for all x ∈ R, s f (ν 1 ) ≤ s f (ν 2 ) =⇒ s f ν 1 (• + x) ≤ s f ν 2 (• + x) and s f (ν 1 ) ≥ s f (ν 2 ) =⇒ s f ν 1 (• + x) ≥ s f ν 2 (• + x) . Hence, ∀x ∈ R, 1 2 f (x) + f (x + h) = f (x + ϕ(h)). This equation can be differentiated twice with respect to h. For any value of x, we obtain:

1 2 f ′ (x + h) = ϕ ′ (h)f ′ (x + ϕ(h)
) and ( 18)

1 2 f ′′ (x + h) = ϕ ′′ (h)f ′ (x + ϕ(h)) + ϕ ′ (h) 2 f ′′ (x + ϕ(h)) . (19)
Recall that by definition, ϕ(0) = 0. Now, for x = 0, Eq. ( 18) yields 1 2 f ′ (0) = ϕ ′ (0)f ′ (ϕ(0)) = ϕ ′ (0)f ′ (0) and, since f ′ (0) ̸ = 0, ϕ ′ (0) = 1 2 . Now, choosing h = 0 in (19) and plugging in the values of ϕ(0) and ϕ ′ (0), we obtain for all x ∈ R:

1 4 f ′′ (x) = ϕ ′′ (0)f ′ (x) .
We then consider two cases, depending on whether ϕ ′′ (0) is null or not.

Case 1: ϕ ′′ (0) = 0. The equation simply becomes f ′′ (x) = 0, hence f is affine: ∃ a, b ∈ R, f (x) = ax + b.

Case 2: ϕ ′′ (0) ̸ = 0. We write β = 4ϕ ′′ (0). The differential equation becomes f ′′ (x) = βf ′ (x), whose solutions are of the form

∃ c 1 , c 2 , β, f (x) = c 1 exp(βx) + c 2 .
Hence, f can only be the identity or the exponential, up to an affine transformation.

Figure 1 :

 1 Figure 1: A Chain MDP of length H with deterministic transition and identical reward distribution for each state.

Figure 2 :

 2 Figure 2: Left: Validation of Theorem 1 on CVaR(α) 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 2.

Figure 3 :

 3 Figure 3: Evaluation of the Wasserstein Distance between the true value distribution and the approximated one, in the MDP described in Corollary 1 .

  End 1, a * ) = δ 0 , η 2 (End 2, a * ) = δ 0 , η 2 (End 3, a * ) = δ 0 H = 1 : η 1 (Left, a * = arg max a s(ν a )) = ν 1 , η 2 (Right, a * = a 1 , a 2 ) = ν 3 H = 0 : η 0 (Start, a * = a 0 ) = λν 1 + (1 -λ)ν 3

Figure 4 :

 4 Figure 4: Left: Independence Property Counter Example, Right: Translation Property Counter Example. Each arrow represents a state transition, which is characterized by the action leading to the transition, the probability of such transition, and the reward distribution of the transition.

H

  = 2 : η 2 (Left, a * ) = δ 0 , η 2 (Right, a * ) = δ 0 H = 1 : η 1 (Step, a * ) = ν 1 H = 0 : η 0 (Start, a * ) = τ c ν 1

The support of the return (sum of the rewards) is incremented at each step by a number of atoms that depend on the current support.

At round h ∈ [H], the support of the return is {0, 1, ..., h}, so h atoms.

Scaling by a constant factor allows us to show the corresponding quadratic trends.

This theoretical algorithm handles the full distribution of the return at each step, which cannot be done in practice.

Either explicitly (model-based RL) or implicitly (model-free RL, considered here).

Acknowledgements

Alexandre Marthe and Aurélien Garivier acknowledge the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d'Avenir (ANR-16-IDEX-0005), Chaire SeqALO (ANR-20-CHIA-0020-01), and Project FOUNDRY in PEPR-IA. Claire Vernade is funded by the Deutsche Forschungsgemeinschaft (DFG) under both the project 468806714 of the Emmy Noether Programme and under Germany'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.AI for their support.


Adrien Coiffard
email: adrien.coiffard@inrae.fr

Raphaële Préget
email: raphaele.preget@inrae.fr

Mabel Tidball
email: mabel.tidball@inrae.fr

Préget R †1

Conservation auctions: an online double constraint reverse auction experiment

Keywords: Reverse auctions, Conservation auctions, Double constraint

come

Introduction

Conservation auctions are a widely studied tool used to allocate agri-environmental payments to farmers [START_REF] Schilizzi | An overview of laboratory research on conservation auctions[END_REF][START_REF] Whitten | Conservation tenders in developed and developing countries status quo, challenges and prospects[END_REF][START_REF] Bingham | Ecosystem services auctions: the last decade of research[END_REF].

The farmers' costs of complying with the agri-environmental contract are private information. Because of this asymmetry of information, auctions are theoretically more cost-effective than fixed payment schemes in allocating contracts [START_REF] Ferraro | Asymmetric information and contract design for payments for environmental services[END_REF][START_REF] Viaggi | Evaluating the potential contribution of contract auctions to Agri-Environmental Policy efficiency: A simulation model for Emilia-Romagna (Italy)[END_REF]. The Conservation Reserve Program (CRP) [START_REF] Hellerstein | The US Conservation Reserve Program: The evolution of an enrollment mechanism[END_REF] in the US and ecoTender in Australia [START_REF] Stoneham | Creating physical environmental asset accounts from markets for ecosystem conservation[END_REF] are well-known examples of large scale conservation auction applications. Competitive bidding is also encouraged by the European Common Agricultural Policy (CAP) to allocate agri-environmental contracts, yet the implementation of conservation auctions in Europe is not much widespread (e.g [START_REF] Ulber | Implementing and evaluating the effectiveness of a payment scheme environmental services from agricultural land[END_REF]. Conservation auctions are reverse auctions because the auctioneer is the buyer (of environmental services) and the bidders are the sellers (providers of environmental services), typically farmers. Conservation auctions are multi-unit auctions, as the auctioneer commonly establishes agri-environmental contracts with several farmers, resulting in multiple winning bidders. In such reverse auctions, the maximum number of contracts to be allocated can be announced to the bidders (hereafter Target auctions). Nevertheless, in practice, the auctioneer generally announces his available budget as a constraint (hereafter Budget auctions). To our knowledge, auction theory, which takes into account bidders interactions, does not consider the case of budgetconstrained reverse auctions.1 Therefore, it is difficult to predict how farmers bid in such situations. The performance of Target and Budget reverse auctions has been compared in few experimental papers [START_REF] Schilizzi | Assessing the Performance of Conservation Auctions : An Experimental Study[END_REF][START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF][START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF].

In this paper, we experimentally study the multi-unit reverse auction format where both the target constraint and the budget constraint are announced (hereafter Double constraint auction). In a Double Constraint auction, units are ranked by the auctioneer in ascending order of price and purchased from the cheapest bid until either the target or the budget constraint is exhausted. We consider only the discriminatory payment rule, i.e., winning bidders receive the price they bid. Our main research question is how the Double Constraint auction performs compared to the auctions in which only one of the two constraints is announced (Target or Budget).

For simplicity, we assume that each farmer can only offer a single contract and that each contract has the same value for the auctioneer. In other words, we assume that each farmer's contract provides the same value of environmental services. This is a strong assumption as many aspects of agri-environmental contracts can influence the level of environmental services provided (number of hectares covered by the contract, location of the farm, etc.). In practice, the auctioneer usually needs to compute an environmental benefit index to weight price offers submitted by farmers (see [START_REF] Glebe | Scoring two-dimensional bids: How cost-effective are agri-environmental auctions?[END_REF]. This aspect of conservation auctions is not considered in this paper, which allows us to consider a much simpler auction format where farmers compete only on price, and where the auctioneer simply selects the lowest bids. In conservation auctions, the target is the amount of environmental services to be purchased. In our simplified context, where each farmer provides the same amount of environmental services, the target is the number of contracts or units, i.e., the number of winning farmers. The budget spent in such Target auctions can be very high (depending on the bid offers) and may exceed the maximum budget available for the purchase of contracts [START_REF] Viaggi | Evaluating the potential contribution of contract auctions to Agri-Environmental Policy efficiency: A simulation model for Emilia-Romagna (Italy)[END_REF]. Indeed, in practice, any auctioneer's budget is limited. To avoid exceeding his budget in Target auctions, the auctioneer can announce a reserve price beyond which offers cannot be accepted [START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF]. This reserve price may be kept secret (see [START_REF] Schilizzi | An overview of laboratory research on conservation auctions[END_REF]. Here we propose an alternative auction design, the Double Constraint auction, in which a budget constraint is announced in addition to the target constraint.

To measure auction performance, we do not consider a specific demand function for the auctioneer, but only assume that the marginal utility of environmental services is strictly positive. Additionally, the auctioneer is assumed not to have any strong constraint: neither to meet the announced environmental target nor the announced budget. This is generally the case as the environmental benefits are complex to define and the auctioneer usually has some leeway in setting the budget for the environmental program.

We use the experimental data obtained in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF], and we propose new treatments using the same methodology. As in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF] we first consider two equivalent constraints to make treatment results comparable. To set equivalent constraints, we first run the Target auction treatment. Then, we use the average budget spent in the Target treatment to set the budget constraint in the Budget treatment. The new Double Constraint auction treatment allows us to study the impact of adding a second equivalent constraint in either the Target or the Budget auction. We also run two other new treatments to better understand the impact of announcing a higher budget constraint in the Budget auction and the Double Constraint auction.

The experiment is conducted online and monetarily incentivized, but is not contextualized to the case of conservation auctions. Indeed, our subjects are not farmers, so giving them instructions related to farmers and environment services may cause confusion. The instructions given to subjects only state that each of them has a single unit to sell. Our experiment relies on the strategy method to obtain the subjects' bidding function: we ask subjects to fill out a decision table in which they indicate the amount of their bid corresponding to every possible cost. Auction outcomes can be simulated ex post from these functions, for any set of costs. By simulating the auction outcomes for all the possible cost sets for a given group of bidders, we generate a very rich data set. Considering the average of the auction outcomes on exhaustive costs arrangements avoids using arbitrary bidders' cost draws. In the data analysis, the participants are randomly attributed to a single auction group, so that the average outcomes at the group level are independent observations. Therefore, the combination of the strategy method with auction outcome simulations is very useful and allows us to obtain a large sample of independent auction data.

The paper is organized as follows. A literature review on conservation auctions is presented in Section 2. Next, the auction game and experimental design are presented in Section 3 along with the criterion we use to compare the different auction formats and information about the online implementation of the experiment and data. In Section 4, we present the results of the treatments. Finally, we discuss our results and conclude in Section 5.

Literature on conservation auctions

Conservation auctions are among the main areas of application of reverse auctions and are covered by an extensive literature. In practice, conservation auctions deviate significantly from theoretical auction models, and most research on conservation auctions is empirical, often using an experimental approach.

A significant body of literature on conservation auctions has compared discriminatory and uniform payment rules using laboratory experiments [START_REF] Cason | A laboratory comparison of uniform and discriminative price auctions for reducing non-point source pollution[END_REF][START_REF] Liu | Balancing Cost Effectiveness and Incentive Properties in Conservation Auctions : Experimental Evidence from Three Multi-award Reverse Auction Mechanisms[END_REF], numerical simulations [START_REF] Hailu | What format for multi-unit multiple-bid auctions?: Agent-based simulation of auction performance and nonlinear bidding behaviour[END_REF][START_REF] Iftekhar | How well do conservation auctions perform in achieving landscape-level outcomes? A comparison of auction formats and bid selection criteria[END_REF] or observational data [START_REF] Windle | Exploring the efficiencies of using competitive tenders over fixed price grants to protect biodiversity in Australian rangelands[END_REF][START_REF] Deng | Green auctions and reduction of information rents in payments for environmental services: An experimental investigation in Sunan County, Northwestern China[END_REF]. In a discriminatory auction, winning bidders receive their bid, whereas in a uniform price auction, all winning bidders receive the same price (generally the highest winning bid). Overall, these studies have shown that discriminatory-price auctions are more cost-effective than uniform price auctions [START_REF] Cason | A laboratory comparison of uniform and discriminative price auctions for reducing non-point source pollution[END_REF][START_REF] Windle | Exploring the efficiencies of using competitive tenders over fixed price grants to protect biodiversity in Australian rangelands[END_REF][START_REF] Deng | Green auctions and reduction of information rents in payments for environmental services: An experimental investigation in Sunan County, Northwestern China[END_REF][START_REF] Duke | The Effect of Information on Discriminatory-Price and Uniform-Price Reverse Auction Efficiency: An Experimental Economics Study of the Purchase of Ecosystem Services[END_REF][START_REF] Liu | Balancing Cost Effectiveness and Incentive Properties in Conservation Auctions : Experimental Evidence from Three Multi-award Reverse Auction Mechanisms[END_REF], although this result may be sensitive to the level of competition [START_REF] Hailu | What format for multi-unit multiple-bid auctions?: Agent-based simulation of auction performance and nonlinear bidding behaviour[END_REF][START_REF] Iftekhar | How well do conservation auctions perform in achieving landscape-level outcomes? A comparison of auction formats and bid selection criteria[END_REF] and the interval of bidders' costs [START_REF] Iftekhar | How well do conservation auctions perform in achieving landscape-level outcomes? A comparison of auction formats and bid selection criteria[END_REF]. Low participation and anti-competitive behaviors (collusion) are also major issues in auctions [START_REF] Klemperer | What really matters in auction design[END_REF] and are equally important when implementing conservation auctions. Indeed, studies show that the cost-effectiveness of conservation auctions may be drastically reduced in the case of low participation [START_REF] Palm-Forster | Too burdensome to bid: Transaction costs and pay-for-performance conservation[END_REF][START_REF] Rolfe | Increasing environmental outcomes with conservation tenders: The participation challenge[END_REF]. Collusion between bidders is typically overlooked in laboratory or online experiments, as subjects usually do not know the other bidders, which reduces collusion risk. Yet in practice, farmers are not monitored during the bidding process and may easily collude in some cases [START_REF] Packman | Conservation Auctions in Manitoba: A summary of a series of workshops[END_REF].

However, what interests us more here is the impact of the auctioneer's announced constraint. Once the units are ranked, a stopping rule must be defined to indicate when the buyer stops purchasing the highest ranked units. In conservation auctions, typically the auctioneer has a limited budget available and tries to achieve the highest possible environmental target. Thus, in practice, the auctioneer usually purchases units in ascending order of price until this budget constraint is exhausted. Note that the level of the budget constraint may or may not be an-nounced to the bidders [START_REF] Messer | When Does Public Information Undermine the Efficiency of Reverse Auctions for the Purchase of Ecosystem Services?[END_REF]. Nevertheless, when no constraint is announced, it is particularly difficult for bidders to define their bid. As explained in the introduction, an alternative to this budget constraint auction is to announce a target constraint, which means that the cheapest units are purchased until the environmental target (i.e., the targeted number of units) is met.

To our knowledge, three experimental studies have compared Target and Budget reverse auctions [START_REF] Schilizzi | Assessing the Performance of Conservation Auctions : An Experimental Study[END_REF][START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF][START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF]. [START_REF] Schilizzi | Assessing the Performance of Conservation Auctions : An Experimental Study[END_REF] and [START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF] conducted laboratory experiments set in an agri-environmental context. They use a between-subject design in which student subjects submit bids in several auction periods to generate more observations. In contrast, [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF] uses the strategy method, which allows to obtain the complete bidding strategy of all subjects and to carry out the experiment online. Furthermore, the experimental protocol is completely decontextualized. [START_REF] Schilizzi | Assessing the Performance of Conservation Auctions : An Experimental Study[END_REF] and [START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF] found mixed results: Target auctions performed equally or slightly better than Budget auctions in the early stages, but the auction performance deteriorates more slowly in Budget than in Target auctions after several auction periods. In a one-shot setting, [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF] found that for the same average budget spent, the Budget auction allows the auctioneer to buy significantly more units on average than does the Target auction. The issue (Target vs. Budget) is not only addressed in experiments but also with multi-agent models [START_REF] Hailu | Assessing the performance of auctions for the allocation of conservation contracts: Theoretical and computational approaches[END_REF][START_REF] Lan | Auctions for buying back groundwater for environmental purposes: Which design performs better[END_REF]. [START_REF] Hailu | Assessing the performance of auctions for the allocation of conservation contracts: Theoretical and computational approaches[END_REF] found that both formats performed similarly, whereas [START_REF] Lan | Auctions for buying back groundwater for environmental purposes: Which design performs better[END_REF] found that the auction performance was equal or higher in Budget than in Target auctions. However, announcing a Target auction only is not completely credible in practice, because farmers know that the buyer's budget is generally quite limited. In conservation auctions, the auctioneer usually has an implicit reserve price [START_REF] Schilizzi | An overview of laboratory research on conservation auctions[END_REF]. Announcing the reserve price increases the auction's efficiency according to Holmes (2010) (based on observational data) and [START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF] (in an experimental study).

In this paper, instead of a reserve price, we study the impact of announcing both a target and a budget constraint to bidders, which to our knowledge has never been considered in the literature on reverse auctions. We also investigate the impact of increasing the size of the budget announced in a Budget auction. [START_REF] Howard | Evaluating the tradeoff between cost effectiveness and participation in agricultural conservation programs[END_REF] showed that the performance of conservation auctions decreases with the budget size. Their objective was to elicit farmers' home-grown values for different types of conservation contracts (different agricultural practices) and considering different types of policy interventions, including reverse auctions, using a choice experiment. However, note that in their study, the budget constraint is not announced to the farmers, whereas in our experiment it is, and subjects might adjust their bids according to the announced budget constraint.

The experiment

The experiment was conducted online with subjects from the general population. For better control (e.g., heterogeneity of subjects' perceptions regarding the agri-environmental context), the protocol is completely decontextualized. In section 3.1, we describe the auction game and the different auction formats. In our between-subject design, subjects are randomly assigned to a single treatment: either Target, a Budget, or a Double Constraint auction. Section 3.2 explains how we obtain the complete bidding strategy of all the bidders using the strategy method. Section 3.3 details how we calculate the outcomes (number of units sold and budget spent) of an auction in each treatment, and then how we simulate a large number of auctions at the group level to finally derive the average outcomes at the treatment level. The synthetic criterion used to compare the auction treatments is presented in section 3.4, and finally, we present the online implementation of the experiment and the data in section 3.5.

The auction game and the different auction formats

The auction game considered is the same as the one presented in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF]. Subjects are the bidders who want to win conservation contract payments. Conservation contracts are assimilated to units of a homogeneous good, which are assumed to be perfectly divisible for the auctioneer (the experimenter). Each bidder i proposes a bid b i to sell his unit. The provision cost of the bidder's unit is identically and independently drawn from a uniform distribution in the interval [c,c], which is common knowledge. The number of bidders N who participate in the auction is exogenous and common knowledge. The auctioneer ranks the N bids b i in ascending order of price. Let (r) = 1, ..., N denote the rank of ranked bids.

b (1) ≤ b (2) ≤ ... ≤ b (N )
The auctioneer purchases the cheapest units first. The payment rule considered is the discriminatory payment, i.e., winning bidders are paid their bid. The number of winning bids is defined by the announced constraint(s) and the constraint(s) is(are) announced to the bidders before they submit their bid. Three auction formats are considered. In the Target auction, the auctioneer announces the number of units to be purchased (M ) and accepts the cheapest bids until this target is achieved. As bidders only bid for one unit, the target constraint is also the number of winning bidders. In the Budget auction, the auctioneer accepts the cheapest bids until the predetermined fixed budget (B) is entirely spent. In a Double Constraint auction, the buyer announces both the target (M ) and the budget constraint (B) and stops purchasing units as soon as one constraint is reached. In case of a tie, the buyer purchases the same fraction from each tied unit.2 In Budget and Double Constraint auctions, the auctioneer may split up the last unit to fill the budget constraint.

The strategy method

Figure 1: Decision table

As in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF], we use the strategy method of [START_REF] Selten | Die Strategiemethode zur Erforschung des eingeschränkt rationalen Verhaltens im Rahmen eines Oligopolexperiments[END_REF]. This method allows us to obtain the entire bidding function of the subjects and to conduct the experiment online without requiring the subjects to be connected simultaneously. Subjects are told that groups of N bidders will be randomly made ex-post and that the cost used for their payment will also be randomly drawn expost for each of them from a uniform distribution (single one-shot auction). More precisely, costs are multiples of five between 0 and €100 (21 possible cost values). The principle of the strategy method is to ask each subject what he would bid for every possible cost draw (see Figure 1). By collecting the entire bidding strategy of each subject, the strategy method subsequently allows to simulate a large number of one-shot auctions. This is an advantage over most auction experiments, which typically involve a few auction groups per treatment and several periods with different cost draws in order to generate more (non-independent) observations. Indeed, in such multi-period experiments, bidders do not play a one-shot auction but repeated or sequential auctions.

Computation of auction outcomes (M and B)

To fully take advantage of having the entire bidding strategy of all the subjects, the auction results are computed for all possible cost configurations. In other words, for each possible cost arrangement k = 1, ...K within an auction group g, we identify corresponding bids and compute auction outcomes: the budget spent in the Target auctions (B T C gk ), the number of units purchased in the Budget auctions (M BC gk ) and both outcomes in the Double Constraint auction treatments (M DC gk and B DC gk ). So let first define auction results at the level of one auction.

•The number of units purchased: In a Target auction, the number of units purchased is always equal to the announced constraint (M ). We assume that M is an integer with 0 < M < N . M BC gk , the quantity purchased in a Budget auction for a group g and a costs draw k, is given by

M BC gk =    N if B ≥ N r=1 b (r)gk t + B- t r=1 b (r)gk b k(t+1) if t r=1 b (r)gk ≤ B < t+1 r=1 b (r)gk (1)
where t is a positive integer such as 0 < t < N and B is the announced budget constraint.

Similarly, M DC gk , the quantity purchased in a Double Constraint auction for a group g and a costs draw k, is given by

M DC gk =    M if M r=1 b (r)gk ≤ B t + B- t r=1 b (r)gk b k(t+1) if t r=1 b (r)gk ≤ B < t+1 r=1 b (r)gk (2)
where t is a positive integer such as 0 < t < M and B is the announced budget constraint.

•The budget spent: The budget spent in a Target auction for a group g and a costs draw k is B T C gk = M r=1 b (r)gk . In a Budget auction, the budget spent is usually the announced constraint B. However, if B allows the auctioneer to buy all the units offered by the N bidders (i.e., no constraint is exhausted), there may be an excess budget E gk

E gk = 0 if B ≤ N r=1 b (r)gk B -N r=1 b (r)gk if B > N r=1 b (r)gk
.

(3) Thus, the budget spent in the Budget auction is B BC gk = B -E gk . The budget spent in a Double Constraint auction is computed as

B DC gk = M r=1 b (r)gk if M r=1 b (r)gk ≤ B B else . ( 4
)
To calculate the average outcomes for any auction treatment X (X = T C, BC, or DC), we first average the auction outcomes (the number of units sold and the budget spent) over all cost draws k at the level of each group g (M X g and B X g ). This provides an exact mean for each group in the different treatments that takes into account the entire bidding functions of the N bidders of each group since all the bidders' costs are used.

We constitute random groups of N bidders in each treatment (between-subject design experiment) such that each subject belongs to a single group. Therefore, group-level means are independent observations. The number of auction groups (G) in each treatment is the number of independent observations. Finally, in each treatment X, group-level values are averaged again over all groups (g = 1, ..., G) to provide treatment-level outcomes (M X and B X ). As group-level means are independent observations, we can compute standard deviations and test statistics to compare auction outcomes at the treatment level.

Computation of the performance criterion

As explained in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF], constraints in Target and Budget treatments (M and B respectively) are defined as equivalent constraints. The Budget constraint is the average budget spent in Target, so the budget spent in both treatments is about the same. Budget is found better than Target because the Budget treatment allows purchasing significantly more units on average than the Target treatment.

Here, we use these two equivalent constraints simultaneously in our Double Constraint treatment. So no more than M units can be purchased and the budget spent is at most B. Each constraint is likely to be saturated in a certain number of cases, which would lead on average at the treatment level to M DC < M and B DC < B. In this case, no conclusion could be drawn about a difference in performance using M and/or B as performance criteria.

The objective of the auctioneer is both to maximize the environmental benefits (the number of units purchased) and to minimize the budget spent. Therefore, to take into account both average outcomes of the treatment, the synthetic criterion we use is the average unit cost (hereafter U C X ), defined at the treatment level as the ratio B X /M X . We assume that the auctioneer prefers to use the auction format that minimizes U C X .

Online implementation and experimental data

Anonymous subjects are from the Foule Factory panel.3 They are not only students, as in most lab experiments, and so they are more representative of the general population. A description of the subject sample is made in Table 1. Auction groups of four bidders (N = 4) are formed ex-post anonymously. Subjects received a lump sum payment of €2.5 based on an announced duration of 15 minutes to answer the survey. To compute the auction payoffs, we randomly drew one cost for each bidder among the 21 possible costs. The bid corresponding to that cost was used to determine whether a bidder succeeded in selling his unit according to the bids offered by the three other bidders of his group. Every winning bidder received an extra payment defined as his bid minus his cost (discriminatory payment). The subjects who did not succeed in selling their unit received no extra payment. They received only the lump sum participation payment. The average auction payoff was €2.88 per subject (including subjects who did not win the auction game, about 50% of the sample).

We use data from five experimental treatments, whose parameters are presented in Table 2. We use the Target and Budget treatments presented in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF], here denoted as TC1 and BC1, respectively. In addition, we consider three new treatments: BC2 (where the announced budget is increased), DC1 (with constraints from TC1 and BC1) and DC2 (with constraints from TC1 and BC2). The budget announced in BC1 (€72) is the average budget obtained in TC1, see [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF]. To study the impact of the budget size, a larger budget is used in BC2 (€120), which corresponds to the theoretical budget obtained on average in a group of four bidders when they all bid, as in the equilibrium strategy in [START_REF] Hailu | Assessing the performance of auctions for the allocation of conservation contracts: Theoretical and computational approaches[END_REF]. Instructions for the DC1 treatment can be found in Appendix A.1. Some comprehension questions were also submitted to subjects before the experiment (see Appendix A.2).

Results

The results in this section are based on a single set of randomly selected independent groups for each treatment. However, we conducted additional simulations with alternative group sets in each treatment and found that all the results are robust.

Announcing both a target and a budget constraint

In the DC1 treatment, subjects face the target constraint M = 2 and the budget constraint B = 72. Results given in Table 3 show that the average unit cost U C is significantly lower in DC1 than in BC1 and TC1. Therefore, the Double Constraint auction is found to be more cost-effective than both Target and Budget constraint auctions. If the auctioneers' main objective is to maximize cost-effectiveness, using both equivalent constraints simultaneously in a Double Constraint auction appears to be a reasonable thing to do.

As expected, the average number of units purchased (outcome M ) and the average budget spent (outcome B) are lower in DC1 than in TC1 and BC1 (see Section 3.4). Table 3 shows that these differences are significant. Consequently, if the auctioneer has a strong constraint, either meet the target or spend the entire budget, he should only announce this constraint.

Among all simulated auctions for the treatment DC1, we observe that the target constraint is reached first 51.65% of the time; in these cases, a part of the budget is not spent. Conversely, in 47.18% of the cases, the budget constraint is reached first, so the targeted number of units is not met. Finally, in 1.17% of the cases, both constraints are simultaneously exhausted. These proportions, close to 50/50, are not surprising, since both constraints are defined in [START_REF] Coiffard | Target versus budget reverse auctions: an online experiment using the strategy method[END_REF] to obtain a kind of equivalence between TC1 and BC1.

Announcing the same target but a larger budget constraint

In the DC1 treatment, the budget spent on average is only €58.01. In this section, we consider another Double Constraint treatment (DC2) with the same target constraint, but with a higher budget constraint, in order to have an ex-post average spent budget closer to €72. This new budget constraint B = 120€ is the average budget spent when all subjects adopt the theoretical equilibrium bidding function in TC1.4 Indeed, we have no insights, other than the value predicted by the theory, to help us set a higher value for B in the DC2 treatment. Here we compare DC2 with TC1 and with a new budget treatment (BC2), where the constraint is set to B = 120 as in DC2.

Results presented in Table 4 shows that U C is significantly lower in DC2 than in BC2, but, it is significantly higher in DC2 than in TC1 at the ten percent significance level. To provide additional evidence on the latter result, we can rely on M to compare TC1 and DC2 as, by chance, the average budget spent in DC2 (€73.92) is not significantly different from the €72.32 spent on average in TC1 (Wilcoxon rank-sum test, p-value = 0.11). We find M to be significantly lower in DC2 than in TC1, but the difference is very small, only 0.04 units.

Thus, if the auctioneer's budget constraint is relatively high (€120), our results suggest that it is on average more cost-efficient to announce both the target and the budget constraints (DC2) instead of only announcing a budget constraint (BC2). However, compared with announcing both constraints (DC2), it is on average more interesting to only announce the target constraint (TC1). Out of all simulated auctions for the DC2 treatment, it is very often the target constraint that is reached first (85.53% of auctions), whereas it is the budget in only 13.70% of cases, and both constraints are met simultaneously in 0.77% of the cases. Therefore, it is worth considering that the Double Constraint auction eliminates the risk of overspending for the buyer, compared to the Target auction TC1.5

Increasing the budget constraint

This section analyzes how cost-effectiveness is affected, within the same auction format, by an increase of the announced budget constraint from €72 (BC1 and DC1) to €120 (BC2 and DC2).

The results presented in Table 5 indicate a significant increase in U C (i.e, a decrease in cost-effectiveness) when the size of the announced budget is increased for both auction formats (Budget and Double Constraint). Although increasing the budget allows for the purchase of more units on average (M BC1 < M BC2 and M DC1 < M DC2 ), the increase in M does not compensate for the higher budget spent.

Discussion and conclusion

We propose an auction format that combines a budget constraint and a target constraint, i.e., a Double Constraint auction. To study the impact of announcing both the target and the maximum available budget in conservation auctions, we conducted an online decontextualized experiment with 705 subjects. Thanks to the strategy method and auction outcome simulations, we compared the performance of the different auction formats at the treatment level according to a criterion that combines both average auction outcomes: the average number of units purchased and the average budget spent. More precisely, we assume that the objective of the auctioneer is to minimize a synthetic criterion defined at the treatment level as the average unit cost of conservation contracts, i.e., the ratio of the average budget spent over the average number of purchased units.

Our results show that with equivalent target and budget constraints (each constraint has about a 50% chance of being the binding constraint), the Double Constraint auction (DC1) outperforms the Target auction (TC1) in terms of costeffectiveness. However, a Double Constraint auction may not be advisable if the budget constraint is relatively large, and may not be saturated in most cases. Indeed, with the same target but an increased budget, the cost-effectiveness becomes lower in DC2 than in TC1. Therefore, our second main conclusion is that it is better to announce only the target when the budget available (to reach this target) is relatively high. This is in line with results from [START_REF] Boxall | An experimental examination of target based conservation auctions[END_REF]. Nevertheless, other experiments with more restrictive budget constraints need to be performed in order to reinforce these results.

The Double Constraint auction thus seems particularly beneficial when the funds dedicated to a conservation program are scarce and the auctioneer's objective is to get the highest environmental benefit for each euro spent. However, in practice, it is not always easy to determine ex-ante which constraint (target or budget) is the most binding.

Our last finding is that increasing the budget in Budget and Double Constraint auctions allows the auctioneer to purchase more units, on average, but at the cost of a (much) lower cost-effectiveness. This result is consistent with what [START_REF] Howard | Evaluating the tradeoff between cost effectiveness and participation in agricultural conservation programs[END_REF] found regarding the impact of a higher budget.

However, it is worth noting that, as in most auction experiments and models, we have considered a game in which the number of bidders is exogenous and common knowledge. The number of bidders is also the same in all our treatments, whereas in practice, it is endogenous and may depend on the auction format. On the one hand, a higher budget may increase participation by attracting more farmers. This could in turn increase the auction cost-effectiveness [START_REF] Rolfe | Increasing environmental outcomes with conservation tenders: The participation challenge[END_REF]. On the other hand, presenting a target constraint as a collective environmental objective may encourage more farmers to participate in conservation auctions. Indeed, the procedure may appear more rewarding to farmers than competing to win the largest share of an announced budget. Considering that endogenous participation goes beyond the scope of this paper, it should be kept in mind when implementing conservation auctions, as should the question of the appropriate spatial scale of the conservation auction.

A Content of the experiment

Table 1 :

 1 Sample description

	Sample description	Value
	Number of subjects	705
	Age (mean, SD)	39.81 (12.8)
	Income (proportion of €1,900 or more)	0.40
	Gender (proportion of female)	0.51
	Education (proportion of bachelor's degree or beyond)	0.47
	Student (proportion of students)	0.09

Table 2 : Experimental treatments Treatment Number of subjects * Nb auction group Target constraint Budget constraint

 2 Some subjects were removed randomly in TC1 and BC1 to create groups of four subjects.

	TC1	131	32	2 units	-
	BC1	198	49	-	€72
	BC2	128	32	-	€120
	DC1	120	30	2 units	€72
	DC2	128	32	2 units	€120

*

Table 3 :

 3 Comparison of treatments with equivalent constraints

	Outcome	TC1 DC1 (1) (2)	Diff. (2)-(1)	BC1 DC1 (3) (4)	Diff. (4)-(3)
	M	2	1.78	-0.22 * * *	2.14	1.78 -0.36 * * *
		(.)	(0.05)		(0.10) (0.05)
	B	72.32 58.01 -14.31 * * * 71.91 58.01 -13.9 * * *
		(6.56) (3.33)		(0.04) (3.33)
	UC	36.16 32.53 -3.63 * * * 33.68 32.53 -1.15 * *
		(3.28) (2.33)		(1.68) (2.33)
	Standard deviations in parentheses.
	Wilcoxon rank-sum tests.
	* p<0.1, ** p<0.05, *** p<0.01

Table 4 :

 4 Comparison of treatments with a higher budget

	Outcome	TC1 DC2 (1) (2)	Diff. (2)-(1)	BC2 DC2 (3) (4)	Diff. (4)-(3)
	M	2	1.96 -0.04 * * *	2.74	1.96	-0.78 * * *
		(.)	(0.01)		(0.13) (0.01)
	B	72.32 73.92	1.60	119.08 73.92 -45.16 * * *
		(6.56) (6.22)		(0.47) (6.22)
	UC	36.16 37.64	1.48 *	43.52 37.64 -5.88 * * *
		(3.28) (3.38)		(2.33) (3.38)
	Standard deviations in parentheses.
	Wilcoxon rank-sum tests
	* p<0.1, ** p<0.05, *** p<0.01

Table 5 :

 5 Comparison of treatments when the budget increases

	Outcome	BC1 BC2 (1) (2)	Diff. (2)-(1)	DC1 DC2 (3) (4)	Diff. (4)-(3)
	M	2.14	2.74	0.60 * * *	1.78	1.96	0.18 * * *
		(0.10) (0.13)		(0.05) (0.01)
	B	71.91 119.08 47.17 * * * 58.00 73.92 15.92 * * *
		(0.04) (0.47)		(3.33) (6.22)
	UC	33.76 43.52 9.84 * * * 32.53 37.64 5.11 * * *
		(1.68) (2.33)		(2.33) (3.38)
	Standard deviations in parentheses.
	Wilcoxon rank-sum tests
	* p<0.1, ** p<0.05, *** p<0.01

A.1 Instructional video for DC1 treatment (Translated slides from French to English) CEE-M Working Papers 1 -2023

	WP 2023-01	Pauline Castaing & Antoine Leblois « Taking firms' margin targets seriously in a model of competition in supply »
	WP 2023-02	Sylvain Chabé-Ferret, Philippe Le Coënt, Caroline Lefébvre, Raphaële
		Préget, François Salanié, Julie Subervie & Sophie Thoyer « When Nudges Backfire: Evidence from a Randomized Field Experiment to Boost Biological Pest Control »
	WP 2023-03	Adrien Coiffard, Raphaële Préget & Mabel Tidball « Target versus budget reverse auctions: an online experiment using the
		strategy method »
	WP 2023-04	Simon Mathex, Lisette Hafkamp Ibanez & Raphaële Préget « Distinguishing economic and moral compensation in the rebound effect: A theoretical and experimental approach »
	WP 2023-05	Simon Briole, Augustin Colette & Emmanuelle Lavaine « The Heterogeneous Effects of Lockdown Policies on Air Pollution »
	WP 2023-06	Valeria Fanghella, Lisette Ibanez & John Thøgersen « To request or not to request: charitable giving, social information, and spillover »
	WP 2023-07	Francisco Cabo, Alain Jean-Marie & Mabel Tidball
		« Positional and conformist effects in public good provision. Strategic interaction and inertia »
	WP 2023-08	Adrien Coiffard, Raphaële Préget & Mabel Tidball
		« Conservation auctions: an online double constraint reverse auction experiment »

1 CEE-M Working Papers / Contact : laurent.garnier@inrae.fr  RePEc https://ideas.repec.org/s/hal/wpceem.html  HAL https://halshs.archives-ouvertes.fr/CEE-M-WP/

[START_REF] Latacz-Lohmann | Auctioning Conservation Contracts: A Theoretical Analysis and an Application[END_REF] propose a budget-constrained auction model, but within the framework of decision theory (as opposed to game theory), i.e., they do not consider strategic interactions of bidders.

In practice this tie rule is probably not the most pertinent, but it is easy to implement in the experiment and is the same as drawing a winner among the ties.

Participants are paid to complete surveys. See https://www.wirk.io/en/50kfreelancers-in-france/ (former web address: https://www.foulefactory.com/en/)

This can be done, as the closed formula for the optimal bid is known in the Target auction[START_REF] Hailu | Assessing the performance of auctions for the allocation of conservation contracts: Theoretical and computational approaches[END_REF][START_REF] Liu | Balancing Cost Effectiveness and Incentive Properties in Conservation Auctions : Experimental Evidence from Three Multi-award Reverse Auction Mechanisms[END_REF].

The budget spent is over €120 in 12.57% of all simulated auctions in TC1.

19 20

A.2 Comprehension questions in DC1 (Translated from

French to English)