Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes Axel Benyamine, Julien Grand-Clément, Marek Petrik, Michael I. Jordan, Alain Durmus Abstract In this paper, we propose a general theory of ambiguity-averse MDPs, which treats the uncertain transition probabilities as random variables and evaluates a policy via a risk measure applied to its random return. This ambiguity-averse MDP framework unifies several models of MDPs with epistemic uncertainty for specific choices of risk measures. We extend the concepts of value functions and Bellman operators to our setting. Based on these objects, we establish the consequences of dynamic programming principles in this framework (existence of stationary policies, value and policy iteration algorithms), and we completely characterize law-invariant risk measures compatible with dynamic programming. Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it. 1 Introduction Markov Decision Processes (MDPs) are a model of sequential decision-making in which an agent repeatedly interacts with a system to optimize rewards over a (possibly infinite) horizon ( 45 ) . It is well-documented that the performance of a policy, which dictates the choice of actions given the current state of the system, may severely deteriorate when the model parameters (such as the transition probabilities across states) are incorrect ( 11 ) . This epistemic uncertainty may occur in applications with high stakes, e.g., healthcare ( 17 ; 55 ) and vehicle routing ( 40 ) . The issue of model errors has been addressed in several ways in the literature. Robust MDPs (RMDPs) posit that the true parameters belong to an uncertainty set and optimize for the worst-case parameter realization ( 29 ; 42 ; 59 ) ; the uncertainty set represents all plausible parameter realizations and can be estimated from a dataset. RMDPs are among the most well-studied MDP models with uncertain kernels, and under appropriate rectangularity assumptions, they can be solved efficiently via dynamic programming ( 59 ; 21 ) . Several other frameworks for MDPs with uncertain parameters exist, e.g., multi-model MDPs ( 55 ; 56 ) that optimize over the average of the return across plausible parameters, models based on value at risk (percentile optimization) ( 11 ; 43 ; 3 ) , conditional value at risk ( CVaR ) ( 36 ; 35 ) and the entropic risk measure ( ERM ) ( 50 ) . Overall, several “uncertain MDP” models have been introduced independently, each with its own ad hoc analysis. For some models, computing an optimal policy is tractable via dynamic programming (RMDPs), for others, computing an optimal policy is NP-hard (e.g., for multi-model MDPs and percentile optimization), and for others, the answers to these questions are unknown (e.g., models based on CVaR and ERM ). One may wonder whether there is a common perspective unifying these models, and, crucially from an application standpoint, whether one could design new models with favorable tractable properties (beyond RMDPs). In this work, we propose a unifying model for MDPs with uncertain parameters. Our contributions are as follows. • We propose ambiguity-averse MDPs , a principled approach to epistemic uncertainty in MDPs, where the uncertain transition probabilities are modeled as random variables, and the return is estimated using a risk measure capturing the agent’s risk preferences. This model unifies most of the literature on MDPs with parameter uncertainty. We then introduce the generalization of the dynamic programming principle for ambiguity-averse MDPs, which states that ambiguity-averse value functions are fixed points of some Bellman operator. • For a broad class of risk measures satisfying a set of axioms, we prove that the fundamental properties of the Bellman operators (monotonicity and contraction) are preserved. We then establish that dynamic programming implies key structural and computational guarantees, most notably, the existence of stationary optimal policies and the validity of value and policy iteration algorithms. • Finally, we fully characterize the risk measures for which ambiguity-averse MDPs satisfy dynamic programming. Surprisingly, we show that, under a law-invariance and monotonicity assumption, or under a continuity assumption, dynamic programming forces the objective to collapse to only robust, optimistic, or risk-neutral MDPs (we refer to Theorem 4.4 and Theorem 4.5 for formal statements). Overall, our work provides a unified perspective on parameter uncertainty in MDPs within the dynamic programming framework. On the one hand, dynamic programming enables several desirable tractability properties, however it also severely limits the choice of risk models (among law-invariant risk measures). Our work emphasizes that designing further tractable ambiguity-averse MDP instances requires either going beyond dynamic programming and allowing, for instance, state-augmentation ( 8 ) , or solutions based on direct gradient descent of the returns ( 58 ) , or sticking to dynamic programming but going beyond law-invariance (e.g., focusing on nested risk measures ( 51 ) ). In the rest of the paper, we first provide background on MDPs and risk measures, then introduce the framework of ambiguity-averse MDPs, and finally state our main results on the algorithmic implications of dynamic programming and characterize risk measures compatible with dynamic programming. All the proofs are detailed in the appendices and we provide a literature review in Appendix C . Notations Random variables are denoted by a capital letter and a tilde, e.g., \tilde{X} or \tilde{S} . We denote by L_{c}^{\infty}(B) the set of bounded random variables with convex support (see for instance Definition A.1 ) that are almost surely in B . The simplex over a set \mathcal{S} is denoted by \Delta(\mathcal{S}) . For two vectors v,w\in\mathbb{R}^{\mathcal{S}} , the inequality v\leqslant w is component-wise: v(s)\leqslant w(s),\forall\;s\in\mathcal{S} . 2 Preliminaries We first introduce (nominal) MDPs and risk measures. 2.1 Nominal MDPs A (discounted) MDP is a tuple {\sf M}_{P}=(\mathcal{S},\mathcal{A},r,P,\gamma,\mu) , where \mathcal{S},\mathcal{A} are finite state and action spaces, r\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}\times\mathcal{S}} represents the instantaneous rewards; i.e., r(s,a,s^{\prime})\in\mathbb{R} is the reward when taking action a in state s and moving to state s^{\prime} , and P is a (fixed) transition probability kernel in \Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} . The vector \mu\in\Delta(\mathcal{S}) is the initial probability distribution, and the scalar \gamma\in[0,1) is a discount factor. A history-dependent policy maps any finite history (s_{0},a_{0},s_{1},...,s_{t}) up to period t\in\mathbb{N} to a distribution over actions in \Delta(\mathcal{A}) . A stationary policy can be identified with a map \mathcal{S}\rightarrow\Delta(\mathcal{A}) . The set of history-dependent (resp. stationary) policies is denoted by \Pi_{\sf H} (resp. \Pi_{\sf S} ). The goal of the decision-maker is to find an optimal policy that maximizes the expected discounted return; i.e., to solve \sup_{\pi\in\Pi_{\sf H}}\mathbb{E}^{\pi,P}_{\mu}\left(\sum_{t=0}^{\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right)\;, (1) where (\tilde{S}_{t},\tilde{A}_{t}) is the (random) state-action pair visited at time t and \mathbb{E}^{\pi,P}_{\mu} is the expectation with the measure induced by \pi,P,\mu over the trajectories (\tilde{S}_{t},\tilde{A}_{t})_{t\in\mathbb{N}} . Note that the discounted return is equal to \mu^{\top}V^{\pi,P} with V^{\pi,P}\in\mathbb{R}^{\mathcal{S}} the value function which characterizes the return obtained starting from each state and is defined as follows: V^{\pi,P}(s)=\mathbb{E}^{\pi,P}_{s}\left(\sum_{t=0}^{\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right)\;, (2) for \pi\in\Pi_{\sf H} and s\in\mathcal{S} . Given some transitions P and a stationary policy \pi\in\Pi_{\sf S} , the associated Bellman operator is denoted as T^{\pi,P}:\mathbb{R}^{\mathcal{S}}\rightarrow\mathbb{R}^{\mathcal{S}} with, for v\in\mathbb{R}^{\mathcal{S}},s\in\mathcal{S} , \displaystyle T^{\pi,P}v(s) \displaystyle=\sum_{a\in\mathcal{A}}\pi(s,a)\sum_{s^{\prime}\in\mathcal{S}}P(s,a,s^{\prime})\left(r(s,a,s^{\prime})+\gamma v(s^{\prime})\right)\;. (3) T^{\pi,P} is a contraction for the \ell_{\infty} -norm, and its unique fixed-point is the value function V^{\pi,P} ( 45 ) : V^{\pi,P}=T^{\pi,P}V^{\pi,P}\;. (4) Moreover, the optimal value function V^{P}\in\mathbb{R}^{\mathcal{S}} defined as V^{P}(s)=\sup_{\pi\in\Pi_{\sf H}}V^{\pi,P}(s) for s\in\mathcal{S} , satisfies the following Bellman optimality equations: V^{P}(s)=\max_{\pi\in\Pi_{\sf S}}T^{\pi,P}V^{P}(s),\forall\;s\in\mathcal{S}\;. (5) A stationary optimal policy can be computed by choosing a policy that attains the \max in the right-hand side of ( 5 ). The fact that value functions and optimal value functions satisfy fixed-point equations as in ( 4 ) and ( 5 ) is usually referred to as the dynamic programming principle ( 57 ; 21 ) and plays a central role in the favorable tractability properties of nominal MDPs. In particular, computing an optimal policy can be done efficiently by iteration, policy iteration, linear programming, and gradient descent ( 45 , see, e.g.,) . One of the main objectives of our work is to understand, in the case where the transition probabilities are uncertain, when a similar dynamic programming principle holds. To this end, we rely on risk measures that we now introduce. 2.2 Risk measures A risk measure is a map from random variables to \mathbb{R} . Examples include the expectation: \rho(\tilde{X})=\mathbb{E}(\tilde{X}) and the Value-at-Risk ( {\sf VaR}_{\alpha} ) defined as the upper (1-\alpha) -quantile of \tilde{X} : {\sf VaR}_{\alpha}(\tilde{X})=\inf\{x\in\mathbb{R}\;|\;\mathbb{P}(\tilde{X}\leqslant x)>1-\alpha\} for some \alpha\in(0,1) , as well as the essential infimum ( \operatorname{ess\,inf} ) and the essential supremum ( \operatorname{ess\,sup} ), defined as \displaystyle\operatorname{ess\,inf}(\tilde{X}) \displaystyle=\sup\{b\in\mathbb{R}\;|\;\mathbb{P}(\tilde{X}M)=0 so that \operatorname{ess\,sup}(\tilde{X})\leqslant M . Additionally, since M\in{\sf supp}(\tilde{X}) , any neighborhood of M has positive mass, i.e. for every \epsilon>0 we have \mathbb{P}(\tilde{X}>M-\epsilon)>0 . We conclude that M-\epsilon\leqslant\operatorname{ess\,sup}(\tilde{X}) for any \epsilon>0 , i.e. we conclude that M\leqslant\operatorname{ess\,sup}(\tilde{X}) . Therefore we have shown that M=\operatorname{ess\,sup}(\tilde{X}) , which concludes the proof. ∎ • The Value-at-Risk ( {\sf VaR}_{\alpha} ) is defined as the upper (1-\alpha) -quantile: {\sf VaR}_{\alpha}(\tilde{X})=\inf\{x\in\mathbb{R}\;|\;\mathbb{P}(\tilde{X}\leqslant x)>1-\alpha\} for some \alpha\in(0,1) , and the Conditional Value-at-Risk ( {\sf CVaR}_{\alpha} ) is the expectation of the worst (1-\alpha) -fraction of \tilde{X} . CVaR can be computed via the following formula: {\sf CVaR}_{\alpha}(\tilde{X})=\sup_{\xi\in\mathbb{R}}\xi-\frac{1}{1-\alpha}\mathbb{E}(\max\{\xi-\tilde{X},0\})\;. (10) CVaR is a concave risk measure, and positively homogeneous, thus CVaR is coherent. In contrast, VaR is only monetary. Note we can extend CVaR by continuity, as {\sf CVaR}_{0}(\tilde{X})=\mathbb{E}(\tilde{X}),{\sf CVaR}_{1}(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . • The Entropic Risk Measure ( ERM ) at risk level \beta\in\mathbb{R} is defined as {\sf ERM}_{\beta}(\tilde{X})=\frac{1}{\beta}\log(\mathbb{E}(\exp(\beta\cdot\tilde{X}))) extended by continuity as {\sf ERM}_{0}(\tilde{X})=\mathbb{E}(\tilde{X}){\sf ERM}_{+\infty}(\tilde{X})=\operatorname{ess\,sup}(\tilde{X}),{\sf ERM}_{-\infty}(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . ERM is convex for \beta>0 and concave for \beta\leqslant 0 . The Entropic Value-at-Risk ( EVaR ) is defined as {\sf EVaR}_{\alpha}(\tilde{X})=\sup_{\beta>0}{\sf ERM}_{\beta}(\tilde{X})+\frac{\log(1-\alpha)}{\beta}\;. We note that ERM is concave but not coherent, while EVaR is a coherent risk measure. We refer to 25 for recent advances in using ERM and EVaR in risk-averse MDPs. For the sake of readability, we summarize the properties of some common risk measures in Table 2 . Table 2: Properties of some common risk measures. The term “Monetary” means that the risk measure is monotone and translation-invariant. The column “ W^{1} - C^{0} ” refers to the continuity in the W^{1} -sense defined in Appendix H.3 (see Definition H.7 ). Risk properties Risk measure Notation Coherent Concave Monetary Law invariant W^{1} - C^{0} Expectation \mathbb{E}(\tilde{X}) \checkmark \checkmark \checkmark \checkmark \checkmark Essential Supremum \operatorname{ess\,sup}(\tilde{X}) \times \times \checkmark \checkmark \times Essential Infimum \operatorname{ess\,inf}(\tilde{X}) \checkmark \checkmark \checkmark \checkmark \times Value-at-Risk {\sf VaR}_{\alpha}(\tilde{X}) \times \times \checkmark \checkmark \times Cond. Value-at-Risk {\sf CVaR}_{\alpha}(\tilde{X}) \checkmark \checkmark \checkmark \checkmark \checkmark Entropic Risk Measure {\sf ERM}_{\beta}(\tilde{X}) \times \checkmark (for \beta\leqslant 0 ) \checkmark \checkmark \checkmark Entropic Value-at-Risk {\sf EVaR}_{\alpha}(\tilde{X}) \checkmark \checkmark \checkmark \checkmark \checkmark Note that most of this work focuses on risk measures that are law-invariant. For the sake of completeness, we provide a simple example of a non-law-invariant risk measure below. Example A.3 (A Non-Law-Invariant Risk Measure) . Consider a probability space (\Omega,\mathcal{F},\mathbb{P}) where \Omega=\{\omega_{1},\omega_{2}\} with \mathbb{P}(\{\omega_{i}\})=1/2 for i\in\{1,2\} . Define a risk measure \rho as follows: for a random variable \tilde{X}:\Omega\to\mathbb{R} , let \rho(\tilde{X})=\tilde{X}(\omega_{1})+\mathbb{E}[\tilde{X}] , i.e., the risk measure depends explicitly on the value at a specific outcome \omega=\omega_{1} in addition to the expectation. This risk measure is not law-invariant . To see this, consider two random variables: \displaystyle\tilde{X}(\omega) \displaystyle=\begin{cases}10&\text{if }\omega=\omega_{1}\\ 0&\text{if }\omega=\omega_{2}\end{cases} \displaystyle\tilde{Y}(\omega) \displaystyle=\begin{cases}0&\text{if }\omega=\omega_{1}\\ 10&\text{if }\omega=\omega_{2}\end{cases} Both \tilde{X} and \tilde{Y} have the same law: each takes the value 10 with probability 1/2 and the value 0 with probability 1/2 . However, we have: \displaystyle\rho(\tilde{X}) \displaystyle=\tilde{X}(\omega_{1})+\mathbb{E}[\tilde{X}]=10+10/2=15 \displaystyle\rho(\tilde{Y}) \displaystyle=\tilde{Y}(\omega_{1})+\mathbb{E}[\tilde{Y}]=0+10/2=5 Since \rho(\tilde{X})\neq\rho(\tilde{Y}) despite the fact that \tilde{X},\tilde{Y} have the same law, the risk measure \rho is not law-invariant. The dependence on the specific outcome \tilde{X}(\omega_{1}) violates law-invariance because the risk measure distinguishes between different realizations of the same distribution. In the context of ambiguity-averse MDPs, non-law-invariant risk measures would depend on the specific sample path or realization of the uncertain transition kernel, rather than only on its distribution. This makes them less interpretable and difficult to work with, as they require tracking which particular realization of the uncertainty occurred, rather than just its statistical properties. Remark A.4 . We conclude by noting that risk measures are sometimes introduced for minimizing costs (e.g. this is the point of view adopted in 52 ), instead of maximizing rewards as in the present paper. These two settings are equivalent, in the sense that if we have a risk measure \phi for minimizing costs, then we can consider the risk measure for maximizing reward \rho(\tilde{X}):=-\phi(-\tilde{X}) , which induces the same preferences over the random variables \tilde{X} modeling rewards than the risk measure \phi over random variables -\tilde{X} modeling costs. It is worth noting that, in the cost minimization framework, the role of concavity is replaced by that of convexity and translation invariance becomes \phi(\tilde{X}+c)=\phi(\tilde{X})-c for \tilde{X} a random variable and c\in\mathbb{R} . Appendix B Randomization and Risk Measure for Ambiguity-Averse MDPs In this section, we provide a rigorous foundation for the ambiguity-averse MDPs introduced in Section 3 . We decide to keep this construction in the appendices to simplify the exposition of our results in the main body. Overall, our goal is to provide a rigorous framework for the objective functions of the form \pi\mapsto\rho(\mu^{\top}V^{\pi,\tilde{P}}) that appear in the ambiguity-averse MDP optimization problem ( 6 ). Recall that by definition, a risk measure is a map from the set of real random variables L(\Omega,\mathcal{F},\mathbb{P}) . However, to rigorously model ambiguity-averse MDPs, we need one probability space (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) per instance {\sf M} of ambiguity-averse MDP, and in principle, there is a distinct risk measure for each ambiguity-averse MDP instance (since the set of arguments (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) depends on the instance). We therefore extend the notion of risk measure (defined in Appendix A for a single probability space) to risk measures for ambiguity-averse MDPs (Definition B.2 ), which can take as arguments random variables induced by different ambiguity-averse MDP instances (i.e., induced by different probability spaces). Notation for sets of ambiguity-averse MDPs Recall that we denote by \mathcal{M}_{c} the class of all “convex, product” ambiguity-averse MDPs, i.e. the set of all {\sf M}_{\nu}=(\mathcal{S},\mathcal{A},r,\nu,\gamma,\mu) with any \mathcal{S},\mathcal{A},r,\gamma,\mu , and any \nu with convex support and product structure. We also denote by \mathcal{M} the set of all ambiguity-averse MDPs, i.e. the set of all {\sf M}_{\nu}=(\mathcal{S},\mathcal{A},r,\nu,\gamma,\mu) with any \mathcal{S},\mathcal{A},r,\gamma,\mu and any \nu (not necessarily with convex support or product structure). Probability space for an instance. We first define a probability space (\Omega,\mathcal{F},\mathbb{P}) for each ambiguity-averse MDP. We first provide a slightly more rigorous definition of an ambiguity-averse MDP, which allows us to define a distribution over sequences of transition probabilities directly. Definition B.1 . A (discounted) ambiguity-averse MDP is a tuple {\sf M}_{\hat{\nu}}=(\mathcal{S},\mathcal{A},r,\hat{\nu},\gamma,\mu) where \mathcal{S},\mathcal{A},r,\gamma,\mu are defined exactly as in nominal MDPs (see Section 2 ) and \hat{\nu} is a probability distribution over the set \left(\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}}\right)^{\mathbb{N}} of feasible sequences of transition probabilities. When \hat{\nu} is equal to \nu^{\otimes\mathbb{N}} for a certain measure \nu\in\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} , {\sf M}_{\hat{\nu}} corresponds to an ambiguity-averse MDP with resampled kernels according to \nu . Here \nu^{\otimes\mathbb{N}} is the i.i.d. distribution over the path space (\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}})^{\mathbb{N}} . When \hat{\nu} is equal to the distribution of (\tilde{P}_{t})_{t\in\mathbb{N}} such that \tilde{P}_{0}\sim\nu and \tilde{P}_{t}=\tilde{P}_{0} for any t , {\sf M}_{\hat{\nu}} corresponds to an ambiguity-averse MDP with static kernel. For any ambiguity-averse MDP {\sf M}_{\hat{\nu}}=(\mathcal{S},\mathcal{A},r,\hat{\nu},\gamma,\mu)\in\mathcal{M} , we define the uncertainty in the model transition kernel sequences via a probability space (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) , where: • (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}}) is a measurable space with \Omega_{{\sf M}}=\left(\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}}\right)^{\mathbb{N}} the set of transition kernel sequences and \mathcal{F}_{{\sf M}} the canonical \sigma -field \mathcal{B}(\Omega_{{\sf M}})=\mathcal{B}(\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}})^{\otimes\mathbb{N}} , • \mathbb{P}_{{\sf M}}=\hat{\nu} is a probability measure on (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}}) . Without loss of generality, we consider (\tilde{P}_{t})_{t\in\mathbb{N}} to be the canonical process \tilde{P}_{t}:(p_{s})_{s\in\mathbb{N}}\mapsto p_{t} . In particular, it follows law \hat{\nu} in the sense of Definition B.1 . When \hat{\nu} is non-atomic (i.e., it has no set of positive measure that contains no subsets of smaller positive measure), the probability space (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) is nonatomic (i.e., it supports a random variable uniformly distributed on [0,1] ) and therefore the space L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) is rich enough to contain real bounded random variables with arbitrary distributions, see for instance 10 . Note that by Definition 3.1 , the set \mathcal{M}_{c} of all ambiguity-averse MDPs such that the measure has convex support and product structure contains ambiguity-averse MDPs with non-atomic measure in both static kernels or resampled kernels cases (say for example the ambiguity-averse MDP of Example E.1 in both static and resampled cases). Formally, denoting by \mathfrak{D} the set of all distributions with bounded support (i.e., \mathfrak{D} is the set of non-decreasing right-continuous functions F:\mathbb{R}\to[0,1] that attain both 0 and 1 ), for any F\in\mathfrak{D} there exists {\sf M}_{\nu}\in\mathcal{M}_{c} and \tilde{X}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) such that F_{\tilde{X}}=F , where F_{\tilde{X}} is the distribution function of \tilde{X} under \mathbb{P}_{{\sf M}_{\nu}} defined through F_{\tilde{X}}(x)=\mathbb{P}_{{\sf M}}(\tilde{X}\leqslant x) . Notation for sets of random variables Throughout this work, we denote by L^{\infty}(B)=\cup_{{\sf M}\in\mathcal{M}}L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};B) the set of all bounded real random variables with support in B\subseteq\mathbb{R} across all these probability spaces, and by L^{\infty}_{c}(B)=\cup_{{\sf M}\in\mathcal{M}}L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};B) its analog restricted to random variables with convex supports in B . Note that, by nonatomicity of some probability spaces (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) (for example the one of Example E.1 whether we consider static or resampled kernels), the set L^{\infty}(\mathbb{R}) (resp. L^{\infty}_{c}(\mathbb{R}) ) is rich enough to contain real bounded random variables (resp. bounded real random variables with convex support) with arbitrary distributions. Risk measures We now define the notion of risk measure for ambiguity-averse MDPs: Definition B.2 (Risk Measure for Ambiguity-Averse MDPs) . A risk measure for ambiguity-averse MDPs is a family \rho=(\rho_{{\sf M}})_{{\sf M}\in\mathcal{M}} where each \rho_{{\sf M}} is a risk measure on the corresponding probability space: \forall{\sf M}\in\mathcal{M},\quad\rho_{{\sf M}}:L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\to\mathbb{R}\;. We also define the following properties of a risk measure \rho . We say that a risk measure \rho is: • law-invariant on L^{\infty}(\mathbb{R}) (resp. L^{\infty}_{c}(\mathbb{R}) ) if for any {\sf M},{\sf M}^{\prime}\in\mathcal{M} and \tilde{X},\tilde{X}^{\prime}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\times L^{\infty}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) (resp. L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\times L^{\infty}_{c}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) ), F_{\tilde{X}}=F_{\tilde{X}^{\prime}}\implies\rho_{{\sf M}}(\tilde{X})=\rho_{{\sf M}^{\prime}}(\tilde{X}^{\prime})\;. • non-constant on L^{\infty}(\mathbb{R}) (resp. L^{\infty}_{c}(\mathbb{R}) ) if there exists {\sf M},{\sf M}^{\prime}\in\mathcal{M} and \tilde{X},\tilde{X}^{\prime}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\times L^{\infty}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) (resp. L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\times L^{\infty}_{c}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) ) such that \rho_{{\sf M}}(\tilde{X})\neq\rho_{{\sf M}^{\prime}}(\tilde{X}^{\prime})\;. • monotone on L^{\infty}(\mathbb{R}) (resp. L^{\infty}_{c}(\mathbb{R}) ) if for any {\sf M}\in\mathcal{M} and \tilde{X},\tilde{Y}\in L^{\infty}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) (resp. L^{\infty}_{c}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};\mathbb{R}) ) such that \tilde{X}\geqslant\tilde{Y} a.s., \rho_{{\sf M}}(\tilde{X})\geqslant\rho_{{\sf M}}(\tilde{Y})\;. For ease of notation, we drop the subscript {\sf M} when considering risk measures for ambiguity-averse MDPs that are law-invariant on L^{\infty}(\mathbb{R}) (resp. L^{\infty}_{c}(\mathbb{R}) ) and note \rho_{{\sf M}}(\tilde{X}) as \rho(\tilde{X}) for \tilde{X}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) (resp. \tilde{X}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) ). As expected, we also have the following characterization of law-invariant risk measures for ambiguity-averse MDPs: Proposition B.3 (Existence and Uniqueness of \varrho ) . If \rho is a risk measure for ambiguity-averse MDPs that is law invariant on L^{\infty}(\mathbb{R}) , then there exists a unique functional \varrho:\mathfrak{D}\rightarrow\mathbb{R} such that: \rho_{{\sf M}}(\tilde{X})=\varrho(F_{\tilde{X}})\,,\quad\forall{\sf M}\in\mathcal{M},\forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\;. The proof directly follows from Proposition 1 in 10 . Proof. Denoting by {\sf M}_{0} the MDP of Example E.1 (whether we consider static or resampled kernels), we have that (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is nonatomic, so by Proposition 1 in 10 there exists a unique functional \varrho:\mathfrak{D}\to\mathbb{R} such that for any \tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) : \rho_{{\sf M}_{0}}(\tilde{X})=\varrho(F_{\tilde{X}}). Now, for any {\sf M}\in\mathcal{M} and \tilde{X}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) , because (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is nonatomic, there exists \tilde{X}_{0}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that F_{\tilde{X}}=F_{\tilde{X}_{0}} . Therefore, by law invariance of \rho : \rho_{{\sf M}}(\tilde{X})=\rho_{{\sf M}_{0}}(\tilde{X}_{0})=\varrho(F_{\tilde{X}_{0}})=\varrho(F_{\tilde{X}})\;. Finally, if \varrho,\varrho^{\prime} are such that \forall{\sf M}\in\mathcal{M},\forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\quad\varrho^{\prime}(F_{\tilde{X}})=\rho_{{\sf M}}(\tilde{X})=\varrho(F_{\tilde{X}}) , then, because (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is nonatomic, for any F\in\mathfrak{D} there exists \tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that F_{\tilde{X}}=F , and therefore \varrho^{\prime}(F)=\varrho(F) . This shows uniqueness of \varrho . ∎ Remark B.4 . When adding or multiplying random variables \tilde{X} and \tilde{Y} , it is important to note that the risk measure \rho is only defined on bounded random variables living in one of the probability spaces \left((\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}})\right)_{{\sf M}\in\mathcal{M}} . Consequently, to make sense of expressions like \rho(\tilde{X}+\tilde{Y}) or \rho(\tilde{X}\cdot\tilde{Y}) , the random variables \tilde{X} and \tilde{Y} must be defined on the same probability space (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) for some ambiguity-averse MDP {\sf M}\in\mathcal{M} . When we state properties like additivity or multiplicativity for independent random variables, we implicitly assume they are defined on the same probability space and are independent with respect to the probability measure on that space. For instance, a rigorous formulation of Statement 3 of Proposition 4.3 would be: Additive independence on L^{\infty}_{c} : \text{For any }{\sf M}\in\mathcal{M}\text{ and independent }\tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\text{ we have }\rho(\tilde{X}+\tilde{Y})=\rho(\tilde{X})+\rho(\tilde{Y}). B.1 More details on resampled kernels In this section, we provide more details on the resampled kernels setup. Value functions for sequences of kernels For \pi\in\Pi_{\sf H} and s\in\mathcal{S} , we naturally extend the definition of the value function for nominal MDPs (see Equation ( 2 )) to the case of a non-random transition kernel sequence (P_{t})_{t\in\mathbb{N}} that changes over time. In this setup, the value function V^{\pi,(P_{t})_{t\in\mathbb{N}}}\in\mathbb{R}^{\mathcal{S}} depends on \pi and (P_{t})_{t\in\mathbb{N}} and can be written as, for s\in\mathcal{S} , V^{\pi,(P_{t})_{t\in\mathbb{N}}}(s)=\mathbb{E}^{\pi,(P_{t})_{t\in\mathbb{N}}}_{s}\Big(\sum_{t=0}^{\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\Big)\;. where \mathbb{E}^{\pi,(P_{t})_{t\in\mathbb{N}}}_{s} is the expectation over the random trajectories (\tilde{S}_{t},\tilde{A}_{t})_{t\in\mathbb{N}} starting in state s , with the distribution over trajectories induced by \pi and (P_{t})_{t\in\mathbb{N}} . In the paper, we choose to overload the notation V^{\pi,\tilde{P}} when \tilde{P}=(\tilde{P}_{t})_{t\in\mathbb{N}} for the sake of simplicity (instead of writing V^{\pi,(\tilde{P}_{t})_{t\in\mathbb{N}}} ). Dynamic programming for non-i.i.d. kernels We provide here a brief discussion of the case of resampled kernels with non-i.i.d. kernels. In particular, assume that \tilde{P}_{t}\sim\nu_{t} for each period t\in\mathbb{N} with each \nu_{t} having a product structure, \tilde{P}_{t}\perp\!\!\!\perp\tilde{P}_{t}^{\prime} for each t\neq t^{\prime} , but where the law \nu_{t} may be different at each period. To recover a dynamic programming equation, one needs to index value functions with a time index t\in\mathbb{N} , a situation similar to the case of finite horizon MDPs (see Chapter 4 in 45 ). For distributionally robust MDPs, 60 , the case of non-i.i.d. resampled kernels is called nonstationary model and the case of i.i.d. resampled kernels is called stationary model , see beginning of Section 4 in 60 ; the term stationary / nonstationary refers to the to the stationarity of the sequence (\nu_{t})_{t\geqslant 0} which is a stationary sequence of \nu_{t}=\nu_{t^{\prime}},\forall\;t,t^{\prime}\in\mathbb{N} . A central result shown by 60 is the case of i.i.d. resampled kernels and non-i.i.d. resampled kernels are equivalent in the sense that they yield the same optimal value functions and optimal policies (see Theorem 4.1 and Theorem 4.2 in 60 ). This diminishes the practical interest of the non-i.i.d. case, and this is one of the main reasons why we left a more formal analysis of this non-i.i.d. framework for future work. Appendix C Connection with previous models In this section, we provide rigorous reformulations of several of the common variants of MDPs as ambiguity-averse MDPs. We also provide a literature review, discussing the connection of ambiguity-averse MDPs with risk-averse MDPs. C.1 Reformulations and related work on MDPs with uncertain parameters In this appendix we provide a rigorous reformulation of some of the classical variants of MDP models as ambiguity-averse MDPs. We summarize these reformulations in Table 1 . Nominal MDPs Consider a nominal MDP with transition probability P\in\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} . We note that in the standard MDP model, the transition probabilities are fixed over time. Therefore, the transition kernel sequence is static. Consider a Dirac measure \nu that puts all its mass at P:\nu=\delta_{P} (we denote by \delta_{x} the distribution that puts a mass of 1 on an element x ). Then \rho(\mu^{\top}V^{\pi,\tilde{P}})=\rho(\mu^{\top}V^{\pi,P}) . We additionally choose \rho=\mathbb{E}^{\nu} . Because \mu^{\top}V^{\pi,P} is a constant, we get that \rho(\mu^{\top}V^{\pi,P})=\mu^{\top}V^{\pi,P} and we recover the standard objective for nominal MDPs. This shows the following proposition. Proposition C.1 . Any nominal MDP with transition kernel P can be reformulated as an ambiguity averse MDP with \nu=\delta_{P} and \rho(\tilde{X})=\mathbb{E}^{\nu}(\tilde{X}) . Robust MDPs and Optimistic MDPs There are two main frameworks for robust MDPs [ 29 , 42 , 59 ] . An uncertainty set \mathcal{P}\subseteq\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} is s-rectangular if it satisfies the following Cartesian product property: \mathcal{P}=\times_{s\in\mathcal{S}}\mathcal{P}_{s} for some \mathcal{P}_{s}\in\Delta(\mathcal{S})^{\mathcal{A}} for each state s\in\mathcal{S} . Note that if \nu is a distribution over \Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} with product structure, then its support {\sf supp}(\nu)\subseteq\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} is a compact, s-rectangular uncertainty set. We first focus on the model introduced in the seminal paper on s-rectangular robust MDPs [ 59 ] , which analyzes \sup_{\pi\in\Pi_{\sf H}}\inf_{P\in\mathcal{P}}\mu^{\top}V^{\pi,P} (11) for some convex compact s-rectangular uncertainty set \mathcal{P} . Note that here the transition probabilities P are fixed over time, so that we are in the static kernel case as described in Definition 3.2 . This model can be recovered by choosing a distribution \nu supported on \mathcal{P} for the distribution of the random variable \tilde{P} , and \mathcal{P} such that {\sf supp}(\nu)=\mathcal{P} , and \rho(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . In this case, we indeed have, following Lemma A.2 , that \operatorname{ess\,inf}\mu^{\top}V^{\pi,\tilde{P}}=\inf_{P\in{\sf supp}(\nu)}\mu^{\top}V^{\pi,P}=\inf_{P\in\mathcal{P}}\mu^{\top}V^{\pi,P} so that we have shown the following proposition. Proposition C.2 . Consider a robust MDP as in ( 11 ) with convex compact s-rectangular uncertainty set \mathcal{P} . We can reformulate any robust MDPs as in ( 11 ) with an ambiguity-averse MDP with product structure and static kernels with distribution \nu supported on \mathcal{P} and \rho(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . A second popular model of RMDPs allows the transition kernel to change over time and focuses on solving \sup_{\pi\in\Pi_{\sf H}}\inf_{P\in\mathcal{P}^{\mathbb{N}}}\mu^{\top}V^{\pi,P} (12) where \mathcal{P}^{\mathbb{N}} is the set of sequences of kernels: \mathcal{P}^{\mathbb{N}}=\{\left(P_{t}\right)_{t\in\mathbb{N}}\;|\;P_{t}\in\mathcal{P},\forall\;t\in\mathbb{N}\} for some uncertainty set \mathcal{P}\subseteq\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} . Note that Proposition 2.2 in 19 shows that ( 11 ) and ( 12 ) coincide (Proposition 2.2 in 19 in fact shows a stronger statement for history-dependent transition probabilities, but these include as a special case Markovian transition probabilities, so we indeed have that the two optimization problems ( 11 ) and ( 12 ) coincide). We can reformulate ( 12 ) as an ambiguity-averse MDP with the same setup as for ( 11 ) but where we allow for resampled kernels. Indeed, writing \nu^{\otimes\mathbb{N}} for the law of the i.i.d. sequence of kernels (\tilde{P}_{t})_{t\in\mathbb{N}} where \tilde{P}_{t}\sim\nu for each period t\in\mathbb{N} , we get that {\sf supp}(\nu^{\otimes\mathbb{N}})={\sf supp}(\nu)^{\mathbb{N}} , so that we obtain that for resampled kernels \operatorname{ess\,inf}\left(\mu^{\top}V^{\pi,\tilde{P}}\right)=\inf_{(P_{t})_{t\in\mathbb{N}}\in{\sf supp}(\nu^{\otimes\mathbb{N}})}\mu^{\top}V^{\pi,P}=\inf_{(P_{t})_{t\in\mathbb{N}}\in{\sf supp}(\nu)^{\mathbb{N}}}\mu^{\top}V^{\pi,P}=\inf_{(P_{t})_{t\in\mathbb{N}}\in\mathcal{P}^{\mathbb{N}}}\mu^{\top}V^{\pi,P} for \mathcal{P}={\sf supp}(\nu) . We have shown the following proposition. Proposition C.3 . Consider a robust MDP as in ( 12 ) with convex compact s-rectangular uncertainty set \mathcal{P} . We can reformulate any robust MDPs as in ( 12 ) with an ambiguity-averse MDP with product structure and resampled kernels with distribution \nu supported on \mathcal{P} for i.i.d. kernels and \rho(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . We also note that robust MDPs with non-rectangular uncertainty sets have been studied in the literature, e.g. the r-rectangular model [ 18 ] or model based on \ell_{1} -norm between the kernels [ 30 ] , but dynamic programming does not hold for these models in all generality , i.e. for all possible choices of instantaneous rewards. In particular, it is shown in 21 that s-rectangularity (implied by the product structure for the distribution \nu over kernels) is a necessary condition for dynamic programming to hold, and r-rectangular models can only satisfy weaker forms of dynamic programming (i.e. they require strong assumptions, e.g. that the rewards do not depend on the next state, see 21 ). Finally, we note that the case of optimistic MDPs, which focus on \sup_{\pi\in\Pi_{\sf H}}\sup_{P\in\mathcal{P}}\mu^{\top}V^{\pi,P} can be reformulated analogously as for RMDPs by choosing a distribution \nu over the transition probabilities in \Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} with {\sf supp}(\nu)=\mathcal{P} and \rho=\operatorname{ess\,sup} . As noted in 29 , 17 and proved in 15 , the results for robust MDPs extend to optimistic MDPs and in particular 1 and 2 hold for \rho=\operatorname{ess\,sup} in both the static and resampled kernel cases. Multi-model MDPs Multi-model MDPs (MMDPs) consider an optimization problem of the form \sup_{\pi\in\Pi_{\sf H}}\mathbb{E}^{\nu}(\mu^{\top}V^{\pi,\tilde{P}}). (13) This model has received many different names in the literature. For instance, 32 , 55 focus on this model in the case of finite horizon MDPs, and 32 also treats the case of discounted return (infinite-horizon MDPs). The multi-model MDP framework has been reintroduced and studied independently over the years, and is also called soft-robust MDPs [ 12 , 36 ] , concurrent MDPs [ 6 , 7 ] , and multiple-environment MDPs [ 46 ] . The optimization problem ( 13 ) is known to be NP-hard for static kernels, even in the case of supports of cardinality two, e.g. 32 proved that the following problem is NP-hard \sup_{\pi\in\Pi_{\sf H}}\frac{1}{2}\mu^{\top}V^{\pi,P_{1}}+\frac{1}{2}\mu^{\top}V^{\pi,P_{2}}. The same result for discounted return (infinite-horizon MDPs) is present in [ 6 ] . The following reformulation of MMDPs as ambiguity-averse MDPs is straightforward. Proposition C.4 . Consider a multi-model MDP as in ( 13 ), with static or resampled kernels. Then we can model it as an ambiguity-averse MDP {\sf M}_{\nu} with the distribution \nu using \rho(\tilde{X})=\mathbb{E}^{\nu}\left(\tilde{X}\right) . We note that multi-model MDPs also arise as a special case of distributionally robust MDPs (see Appendix B.1 and Equation 15 below) where there is only a single possible distribution \nu (and not a full set of possible probability distributions \mathcal{V} ). Given the seminal results for distributionally robust MDPs as in Section 4 in 60 , we know that multi-model MDPs with resampled kernels satisfy 1 and 2 . It is known that multi-model MDPs with static kernels do not satisfy 1 and 2 , and for the sake of completeness, we reprove this in Example 3.8 . Percentile optimization Percentile optimization [ 38 , 11 , 43 , 61 ] optimizes for the Value-at-Risk ( VaR ) at a certain risk level \alpha\in(0,1) , i.e. it optimizes \sup_{\pi\in\Pi_{\sf H}}{\sf VaR}_{\alpha}\left(\mu^{\top}V^{\pi,\tilde{P}})\right). (14) where \tilde{P} is random and follows a distribution \nu (typically assumed uniform). Note that it is NP-hard to compute an optimal policy for general distributions (corollary 1 in 11 ). The following reformulation is straightforward. Proposition C.5 . Consider a percentile optimization problem as in ( 14 ). Then it can be formulated as an ambiguity-averse MDP with \rho(\tilde{X})={\sf VaR}_{\alpha}(\tilde{X}) and a distribution \nu for static kernels. Other recent work The authors in 36 consider optimizing for a convex combination of expectation and the Conditional Value-at-Risk ( CVaR ), i.e. optimizing \pi\mapsto(1-\lambda)\mathbb{E}(\mu^{\top}V^{\pi,\tilde{P}})+\lambda{\sf CVaR}(\mu^{\top}V^{\pi,\tilde{P}}) for some \lambda\in[0,1] . This optimization problem can be cast as an ambiguity-averse MDP using the risk measure \rho(\tilde{X})=(1-\lambda)\mathbb{E}(\tilde{X})+\lambda{\sf CVaR}(\tilde{X}) . C.2 Other related work Robust MDPs with uncertain rewards An alternative robust MDP model considers that the rewards r\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}\times\mathcal{S}} are uncertain while the transitions are known and fixed, or that both rewards and transitions are uncertain, e.g. 15 , 13 , 5 , 1 ; it is also possible to analyze distributionally robust MDPs with both uncertain rewards and transitions, as in the seminal papers [ 60 ] . RMDPs with uncertain rewards represent a simpler optimization problem compared to RMDPs with uncertain transitions, because value functions are linear in the rewards (this follows from the linearity of the expectation operator) but depend in a non-linear fashion on the transition probabilities. In our paper, we decide to focus solely on the case of uncertain kernels for the sake of conciseness, noting that our framework could be extended to also model uncertain rewards, at the cost of heavier notations. Distributionally robust MDPs DRMDPs are introduced in 60 as the following optimization problem: \sup_{\pi\in\Pi_{\sf H}}\inf_{\nu\in\mathcal{V}}\mathbb{E}^{\nu}(\mu^{\top}V^{\pi,\tilde{P}}) (15) where \mathcal{V} is a set of probability distribution over the sequences of transition probabilities (P_{t})_{t\in\mathbb{N}} . For ambiguity-averse MDPs to cover this setting, we would need to define them with sets of distributions \mathcal{V} instead of a single distribution \nu . Note that DRMDPs also consider the case of uncertain transition kernels that can change over time in a non-i.i.d. fashion, so that we would need a different set \mathcal{V}_{t} of possible distributions \nu_{t} for the transition probabilities at each period t . This complicates the formulation of the optimization problem ( 6 ), which requires to define risk measures with arguments to have multiple distributions (one per choice of \nu\in\mathcal{V} ). In principle, this can be done with the notion of an ambiguous probability space (see 10 ), but it appears beyond the scope of this paper. Necessary and sufficient conditions for dynamic programming There are numerous papers obtaining necessary and sufficient conditions for the existence of dynamic programming in the context of MDPs. The authors in 21 focus on robust MDPs with an uncertainty set \mathcal{P} , and show that a dynamic programming equation holds for policy evaluation if and only if \mathcal{P} is an s-rectangular uncertainty set. The authors in 39 focus on risk-averse MDPs with a finite horizon (in the framework of distributional reinforcement learning) and show that for a Bellman optimality equation to hold it is necessary that the risk measure is {\sf ERM}_{\beta} for some \beta\in\mathbb{R} ; the sufficiency is proved in 27 . The authors in 49 focus on distributional reinforcement learning and define Bellman closedness for a set of statistics, as the property that these statistics can be jointly optimized by dynamic programming (e.g., this is the case for the set consisting of the expectation and the variance [ 54 ] ). The authors in 49 show that the only sets of Bellman closed statistics are sets of moments (see Theorem 4.3 in 49 ). Risk-averse MDPs In risk-averse MDPs, the transition probabilities P and the rewards r are known, and the risk measures are with respect to the distribution over the trajectories induced by pairs of policies and transition kernels, i.e., risk-averse MDPs aim at solving \sup_{\pi\in\Pi_{\sf H}}\rho\left(\sum_{t=0}^{+\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right)\;. (16) It is also common to focus on the case of finite-horizon MDPs, i.e., to optimize, for a given horizon T\in\mathbb{N} , the following objective: \sup_{\pi\in\Pi_{\sf H}}\rho\left(\sum_{t=0}^{H}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right)\;. (17) The existence of dynamic programming equations in risk-averse MDPs has been studied extensively, often using the terms “dynamic consistency” or “time consistency” for risk measures. Informally, a risk measure is time consistent when the risk preferences do not change throughout the execution [ 48 , 28 ] . Time consistency is typically a weaker requirement than our 1 and 2 because it is sufficient that it holds only for \gamma=1 . Several works from the risk-averse MDP literature study necessary and sufficient conditions for the time-consistency of risk measures. 31 shows that only law-invariant, time-consistent, and relevant risk measures are the entropic risk measure, which subsumes the expectation operator. Relevance is a technical condition that excludes risk measures that are insensitive to the \operatorname{ess\,inf} of the random variable. Similar results have been derived in later work, including the restriction for law-invariant coherent risk measures [ 53 ] , and for law-invariant and W^{1} -continuous (see Appendix H.3 ) risk measures [ 39 ] . Despite some superficial similarity to our results, the literature on the time consistency of risk-averse MDPs does not apply to ambiguity-averse MDPs. There is a fundamental difference in the setup of the two problems. In risk-averse MDPs, the risk aversion with respect to randomness is in the returns of the uncertain histories (or trajectories). As a result, we derive that the properties of ambiguity-averse MDPs stem from the interaction between the risk measure, the expectation operator, and the discount factor. Interestingly, one can use dynamic programming to compute policies for risk-averse MDPs using one of the following two approaches: • Dropping the law-invariance condition: nested risk measures. If one drops the law-invariance requirement for the risk measure, it is possible to recover a dynamic programming equation over the set of states using nested risk measures [ 51 ] (also called Markov or iterated risk measures). Intuitively, nested risk measure replacing the objective \rho\left(\sum_{t=0}^{+\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right) by applying the risk measure \rho repeatedly, i.e., informally it corresponds to optimizing ~\rho\left(r(\tilde{S}_{0},\tilde{A}_{0},\tilde{S}_{1})+\rho\left(\gamma r(\tilde{S}_{1},\tilde{A}_{1},\tilde{S}_{1})+\rho\left(\gamma r(\tilde{S}_{2},\tilde{A}_{2},\tilde{S}_{2})+....\right)\right)\right). (18) From the above equation, one can construct a dynamic programming equation and derive value iteration algorithms [ 51 ] to compute optimal Markov policies. However, nested risk measures are not law-invariant, and their values can depend on the order in which rewards are accrued, complicating their interpretation. That is, the quantity in ( 18 ) differs from the original objective \rho\left(\sum_{t=0}^{+\infty}\gamma^{t}r(\tilde{S}_{t},\tilde{A}_{t},\tilde{S}_{t+1})\right) [ 28 ] . • Extended state space. For most common risk measures, including VaR , CVaR , EVaR , ERM , one can formulate dynamic programming equations after augmenting the state space with an additional variable. The particular augmentation depends on the risk measure. For example, to optimize discounted risk-averse objectives with ERM and EVaR , one can augment the state space with the current time step, yielding Markov-optimal policies [ 25 ] . When the objective is VaR , one can construct a dynamic program that augments the state space with the risk level \alpha\in[0,1] [ 33 , 24 , 23 ] , resulting in a history-dependent policy. When the objective is a CVaR , one can construct a dynamic program by augmenting the state space with a real variable that keeps track of the accumulated rewards [ 2 ] and compute an optimal history-dependent policy. When evaluating a fixed policy with the CVaR objective, one can construct a dynamic programming that augments the state with the risk level \alpha\in[0,1] , similarly to VaR . However, the risk-level augmentation fails for CVaR when optimizing a policy [ 24 , 16 ] . Bayes-adaptive MDPs Epistemic uncertainty over MDPs parameters has been studied extensively in the context of Bayes-adaptive MDPs [ 22 ] . Most research on Bayes-adaptive MDPs has focused on reinforcement learning algorithms that compute history-dependent policies for the risk-neutral objective. For the discussion of the differences with the risk-averse setting, we refer the interested reader to 35 . Appendix D Proof of Proposition 3.7 Proof of Proposition 3.7 . 1. Let v,w\in\mathbb{R}^{\mathcal{S}} with v\leqslant w . Since T^{\pi,P} is a monotone operator for any realization of the transition probabilities P , that T^{\pi,\tilde{P}}v\leqslant T^{\pi,\tilde{P}}w almost surely. Since \rho is a monotone risk measure, we obtain that \rho\left(T^{\pi,\tilde{P}}v\right)\leqslant\rho\left(T^{\pi,\tilde{P}}w\right), (19) which proves that T^{\pi,\nu,\rho} is a monotone operator for each \pi\in\Pi_{\sf S} . The fact that T^{\nu,\rho} is a monotone operator follows directly from taking the supremum over \pi\in\Pi_{\sf S} on both sides of ( 19 ). 2. Let v\in\mathbb{R}^{\mathcal{S}},c\in\mathbb{R} . We have T^{\pi,\nu,\rho}(v+c\cdot 1_{\mathcal{S}})=\rho(T^{\pi,\tilde{P}}(v+c\cdot 1_{\mathcal{S}}))=\rho(T^{\pi,\tilde{P}}v+c\cdot 1_{\mathcal{S}})=\rho(T^{\pi,\tilde{P}}v)+c\cdot 1_{\mathcal{S}}=T^{\pi,\nu,\rho}v+c\cdot 1_{\mathcal{S}}, where the first equality is by definition of the operator T^{\pi,\nu,\rho} , the second equality is because T^{\pi,\tilde{P}} is translation-invariant for any realization of \tilde{P} , the third equality is from the translation-invariance of \rho , and the last equality is again by definition of ours operators. This proves that T^{\pi,\nu,\rho} is translation-invariant. The proof for T^{\nu,\rho} follows the same line, using additionally that \max_{s\in\mathcal{S}}\{w(s)+c\}=\max_{s\in\mathcal{S}}\{w(s)\}+c for any w\in\mathbb{R}^{\mathcal{S}} and c\in\mathbb{R} . 3. A direct calculation shows that the composition of a non-expansive risk measure and a contraction remains a contraction. Lemma 4.3 in 14 shows that a monotone, cash-invariant risk measure is non-expansive (this is also a consequence of Crandall-Tartar theorem [ 9 ] ), in the sense that |\rho(\tilde{X})-\rho(\tilde{Y})|\leqslant\operatorname{ess\,sup}|\tilde{X}-\tilde{Y}|,\quad\forall\;\tilde{X},\tilde{Y}\;. (20) Note that in [ 14 ] this result is written an \ell_{\infty} -norm for random variables, but for the sake of clarity we choose to use the notation \|\cdot\|_{\infty} only for functions in \mathbb{R}^{\mathcal{S}} in this paper. For the sake of completeness, we provide a concise proof of ( 20 ) here. Let \delta=\operatorname{ess\,sup}|\tilde{X}-\tilde{Y}|. By definition, |\tilde{X}-\tilde{Y}|\leqslant\delta a.s. so that \tilde{Y}-\delta\leqslant\tilde{X}\leqslant\tilde{Y}+\delta a.s.. Using the monotonicity of \rho we get that \rho(\tilde{Y}-\delta)\leqslant\rho(\tilde{X})\leqslant\rho(\tilde{Y}+\delta) . Using translation invariance we get that \rho(\tilde{Y})-\delta\leqslant\rho(\tilde{X})\leqslant\rho(\tilde{Y})+\delta so that |\rho(\tilde{X})-\rho(\tilde{Y})|\leqslant\delta , which concludes the proof of ( 20 ). Now we have \displaystyle\|T^{\pi,\nu,\rho}v-T^{\pi,\nu,\rho}w\|_{\infty} \displaystyle=\max_{s\in\mathcal{S}}|\rho(T^{\pi,\tilde{P}}v(s))-\rho(T^{\pi,\tilde{P}}w(s))| \displaystyle\leqslant\max_{s\in\mathcal{S}}\operatorname{ess\,sup}|T^{\pi,\tilde{P}}v(s)-T^{\pi,\tilde{P}}w(s)| \displaystyle\leqslant\max_{s\in\mathcal{S}}\gamma\|v-w\|_{\infty} \displaystyle\leqslant\gamma\|v-w\|_{\infty} where the first line is from the definition of T^{\pi,\nu,\rho} and of the \ell_{\infty} -norm for vectors, the second line is from the non-expansiveness of \rho as in ( 20 ), and the third line is from the fact for each kernel P the operator T^{\pi,P} (for nominal MDPs) is a contraction. Therefore, we have shown \forall\;v,w\in\mathbb{R}^{\mathcal{S}},\|T^{\pi,\nu,\rho}v-T^{\pi,\nu,\rho}w\|_{\infty}\leqslant\gamma\|v-w\|_{\infty}. (21) The contraction property of T^{\nu,\rho} follows directly from taking the supremum over \pi\in\Pi_{\sf S} in the right-hand side of ( 21 ). We next prove the attainability property. We show that for any v\in\mathbb{R}^{\mathcal{S}} , we can find \pi\in\Pi_{\sf S} such that T^{\nu,\rho}v=T^{\pi,\nu,\rho}v , i.e. such that \sup_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}v(s)=\max_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}v(s) for each s\in\mathcal{S} . To prove this, it suffices to show that \pi\rightarrow T^{\pi,\nu,\rho}v(s) is continuous for \pi\in\Pi_{\sf S} (note that \Pi_{\sf S}=\Delta(\mathcal{A})^{\mathcal{S}} is a compact set and that T^{\pi,\nu,\rho}v(s) only depends on the s-th component of \pi ). To prove that \pi\rightarrow T^{\pi,\nu,\rho}v(s) is a continuous function, we use the definition of the Bellman operator: T^{\pi,\nu,\rho}v(s)=\rho(T^{\pi,\tilde{P}}v(s)) . Let \pi\in\Pi_{\sf S} and consider a sequence (\pi_{n})_{n\in\mathbb{N}} of stationary policies such that \lim_{n\rightarrow+\infty}\pi_{n}=\pi . Then \displaystyle|T^{\pi_{n},\nu,\rho}v(s)-T^{\pi,\nu,\rho}v(s)| \displaystyle=|\rho(T^{\pi_{n},\tilde{P}}v(s))-\rho(T^{\pi,\tilde{P}}v(s))| \displaystyle\leqslant\operatorname{ess\,sup}|T^{\pi_{n},\tilde{P}}v(s)-T^{\pi,\tilde{P}}v(s)| where the first equality uses the definition of the Bellman operator and the inequality uses the non-expansivity of \rho (Equation ( 20 ), similarly as in the proof for the contraction property of the operators in the third point above). Now from the definition of the operator T^{\pi,\tilde{P}} we get that for any P\in\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} we have |T^{\pi_{n},\tilde{P}}v(s)-T^{\pi,\tilde{P}}v(s)|\leqslant C\cdot\|\pi_{n}-\pi\|_{1} where C:=\max_{s,a,s^{\prime}}|r(s,a,s^{\prime}|+\gamma\max_{s\in\mathcal{S}}|v(s)| . Overall we obtained that |T^{\pi_{n},\nu,\rho}v(s)-T^{\pi,\nu,\rho}v(s)|\leqslant C\cdot\|\pi_{n}-\pi\|_{1} and it is therefore straightforward to conclude that \lim_{n\rightarrow+\infty}|T^{\pi_{n},\nu,\rho}v(s)-T^{\pi,\nu,\rho}v(s)|=0 when \pi_{n}\rightarrow\pi , i.e. we have shown that \pi\mapsto T^{\pi,\nu,\rho}v(s) is a continuous function on the compact set \Pi_{\sf S} . By Weierstrass theorem, we conclude that \sup_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}v(s)=\max_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}v(s) . ∎ Appendix E More details on Example 3.4 - 3.8 We provide a very simple example where 1 and 2 fail to hold below. Example E.1 . We consider, for \rho=\mathbb{E} , the static ambiguity-averse MDP of Figure 2 where \tilde{X}\sim\text{Unif([0,1])} . Figure 2: Ambiguity-averse MDP with \mathcal{S}=\{{\sf Start},{\sf End}\} , \mathcal{A}=\{1\} . The edges (s,a,s^{\prime}) are labeled with pairs (P(s,a,s^{\prime}),r(s,a,s^{\prime})) . Explicitly, we have \mathcal{S}=\{{\sf Start},{\sf End}\} , \mathcal{A}=\{1\} , discount factor \gamma\in[0,1) and reward function r({\sf Start},1,s^{\prime})=1 and r({\sf End},1,s^{\prime})=0 for any s^{\prime}\in\mathcal{S} . Here, \nu is the distribution of the random matrix \begin{pmatrix}\tilde{X}&1-\tilde{X}\\ 0&1\end{pmatrix} . We consider here the case of static kernels: there is a single sample of \tilde{X} at time t=0 , so that the kernel \tilde{P}_{t} at time t is \displaystyle\tilde{P}_{t}=\begin{pmatrix}\tilde{X}&1-\tilde{X}\\ 0&1\end{pmatrix},\forall t\in\mathbb{N}\;. Explicitly, at any time step, from state {\sf Start} , the system transitions to state {\sf Start} with probability \tilde{X} and to state {\sf End} with probability 1-\tilde{X} , and from state {\sf End} , the system stays in state {\sf End} with probability 1. Because the transitions are only random at {\sf Start} , the transition kernel law \nu of this ambiguity-averse MDP has a product structure over spaces and identical marginals over time (because static), and because the uniform distribution has convex support, the overall transition kernel law has convex support. We consider the unique stationary policy \pi that always takes the single action possible. The random nominal value function under policy \pi and transition kernel sequence \tilde{P} is given by: V^{\pi,\tilde{P}}=\begin{pmatrix}\sum_{t\geqslant 0}\gamma^{t}\tilde{X}^{t}\\ 0\end{pmatrix}=\begin{pmatrix}\frac{1}{1-\gamma\tilde{X}}\\ 0\end{pmatrix}. Therefore, the ambiguity-averse value function under policy \pi is: V^{\pi,\nu,\rho}=\begin{pmatrix}\mathbb{E}\left(\frac{1}{1-\gamma\tilde{X}}\right)\\ 0\end{pmatrix}=\begin{pmatrix}\frac{-\log(1-\gamma)}{\gamma}\\ 0\end{pmatrix}\;. On the other hand, the ambiguity-averse Bellman operator T^{\pi,\nu,\rho} is given by: \displaystyle\forall v\in\mathbb{R}^{2},\quad\quad T^{\pi,\nu,\rho}\begin{pmatrix}v({\sf Start})\\ v({\sf End})\end{pmatrix} \displaystyle=\begin{pmatrix}\mathbb{E}\left(1+\tilde{X}\gamma v({\sf Start})+(1-\tilde{X})\gamma v({\sf End})\right)\\ \mathbb{E}\left(0\cdot\gamma v({\sf Start})+1\cdot\gamma v({\sf End})\right)\end{pmatrix} \displaystyle=\begin{pmatrix}1+\frac{\gamma}{2}v({\sf Start})+\frac{\gamma}{2}v({\sf End})\\ \gamma v({\sf End})\end{pmatrix}\;, and in particular, we have T^{\pi,\nu,\rho}V^{\pi,\nu,\rho}=\begin{pmatrix}1-\frac{\log(1-\gamma)}{2}\\ 0\end{pmatrix}\;. Finally, we have T^{\pi,\nu,\rho}V^{\pi,\nu,\rho}=V^{\pi,\nu,\rho}\Longleftrightarrow-\log(1-\gamma)=\frac{2\gamma}{2-\gamma} , so because the second assertion is not true for any \gamma\in[0,1) , there exists {\sf M}\in\mathcal{M}_{c} and \pi\in\Pi_{S} such that T^{\pi,\nu,\rho}V^{\pi,\nu,\rho}\neq V^{\pi,\nu,\rho} . That is, \mathbb{E} does not satisfy 1 for static kernels. Because there is a single policy, T^{\pi,\nu,\rho}=T^{\nu,\rho} and V^{\pi,\nu,\rho}=V^{\nu,\rho} , so we also have that \mathbb{E} doesn’t satisfy 2 for static kernels. Appendix F Proof of Theorem 4.1 Proof of Theorem 4.1 . Under the assumption that \rho is monotone and translation invariant, from Proposition 3.7 , both T^{\pi,\nu,\rho} (for each \pi\in\Pi_{\sf S} ) and T^{\nu,\rho} are monotone contractions. We first prove that there exists \pi^{\star}\in\Pi_{\sf S} such that V^{\nu,\rho}=V^{\pi^{\star},\nu,\rho} . Indeed, for s\in\mathcal{S} we have V^{\nu,\rho}(s)=T^{\nu,\rho}V^{\nu,\rho}=\max_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}V^{\nu,\rho}(s)=T^{\pi,\nu,\rho}V^{\nu,\rho}(s), where the first equality is from 2 , the second equality follows from the definition of the operator T^{\nu,\rho} as in ( 8 ), and the last equation is from defining the policy \pi^{\star}\in\Pi_{\sf S} attaining the \arg\max in \max_{\pi\in\Pi_{\sf S}}T^{\pi,\nu,\rho}V^{\nu,\rho}(s) for each s\in\mathcal{S} (note that \pi^{\star} exists from the attainability property stated in Proposition 3.7 ) and from the definition of the operator T^{\pi,\nu,\rho} as in ( 7 ). This shows that V^{\nu,\rho} is a fixed point of the contraction operator T^{\pi^{\star},\nu,\rho} . Therefore V^{\nu,\rho} coincides with the fixed point of T^{\pi^{\star},\nu,\rho} , which is equal to V^{\pi^{\star},\nu,\rho} from 1 . We have \sup_{\pi\in\Pi_{\sf H}}\rho\left(V^{\pi,\tilde{P}}(s)\right)=V^{\nu,\rho}(s)=V^{\pi^{\star},\nu,\rho}(s)\leqslant\max_{\pi\in\Pi_{\sf S}}\rho\left(V^{\pi,\tilde{P}}(s)\right)=\max_{\pi\in\Pi_{\sf S}}\rho\left(\mu^{\top}V^{\pi,\tilde{P}}\right), where the first equality is by definition of V^{\nu,\rho} , the second equality was proved in the previous paragraph, and the last equality is by taking the maximum over \Pi_{\sf S} (since \pi^{\star}\in\Pi_{\sf S} ), and the last equality is by the choice of \mu again. Since \Pi_{\sf S}\subseteq\Pi_{\sf H} , in general we also always have \max_{\pi\in\Pi_{\sf S}}\rho\left(V^{\pi,\tilde{P}}(s)\right)\leqslant\sup_{\pi\in\Pi_{\sf H}}\rho\left(V^{\pi,\tilde{P}}(s)\right), from which we conclude that \sup_{\pi\in\Pi_{\sf H}}\rho\left(V^{\pi,\tilde{P}}(s)\right)=\max_{\pi\in\Pi_{\sf S}}\rho\left(V^{\pi,\tilde{P}}(s)\right)=\rho\left(V^{\pi^{\star},\tilde{P}}(s)\right), i.e., we conclude that \pi^{\star} is a stationary optimal policy starting from any state. The fact that T^{\nu,\rho} is a contraction follows from Proposition 3.7 . Additionally, we have defined \pi^{\star} as any policy \pi\in\Pi_{\sf S} such that T^{\nu,\rho}V^{\nu,\rho}=T^{\pi,\nu,\rho}V^{\nu,\rho} , which concludes the proof. ∎ The next corollary shows that when 1 and 2 hold for both static kernels and resampled kernels, then one can choose an optimal policy that is stationary and optimal for both models of kernels. This is stated in the next corollary. Corollary F.1 . Assume that \rho is monotone, translation-invariant. Assume that for static and resampled kernels, 1 and 2 hold. Then there exists a stationary policy that is optimal starting from any state in both the model with static kernels and resampled kernels. Proof of Corollary F.1 . Note that under the assumptions of Corollary F.1 , the operator T^{\nu,\rho} is a contraction, hence it has a unique fixed point. Additionally, this operator only depends on the marginal at time t=0 (in evaluating T^{\nu,\rho}v for some v\in\mathbb{R}^{\mathcal{S}} , the transition kernels are sampled only once before a continuation value of v(s^{\prime}) is obtained at state s^{\prime}\in\mathcal{S} ), so that the operator T^{\nu,\rho} is the same function in the case of static kernels and in the case of resampled kernels. Because 2 holds for both the static and resampled kernels, the optimal value functions for both models of kernels are fixed point of the contraction operator T^{\nu,\rho} . Since a contraction has a unique fixed point, we get that the optimal value functions for both kernel models coincide, and we denote this common optimal value function as V^{\star} . From Theorem 4.1 we know that in both kernel models (static or resampled) we can find a stationary optimal policy as any \pi\in\Pi_{\sf S} such that T^{\nu,\rho}V^{\star}=T^{\pi,\nu,\rho}V^{\star} , which concludes the proof. ∎ Appendix G Proof of Proposition 4.2 The proof of Proposition 4.2 follows from standard arguments in the MDP literature, e.g., Chapter 6 in 45 . The arguments rely entirely on the monotonicity, attainability, and contraction properties of the Bellman operators. Proof of Proposition 4.2 . 1. We start by proving the results for value iteration. Let V^{n}=T^{\nu,\rho}V^{n-1} for n\geqslant 1 and V^{0}\in\mathbb{R}^{\mathcal{S}} . By induction we get that V^{n}=\left(T^{\nu,\rho}\right)^{n}V^{0} for any n\geqslant 0 , and since T^{\nu,\rho} is a contraction, we have that \left(T^{\nu,\rho}\right)^{n}V^{0} converges to the fixed point of the operator T^{\nu,\rho} as n\rightarrow+\infty , i.e. we get that \lim_{n\rightarrow+\infty}\left(T^{\nu,\rho}\right)^{n}V^{0}=V^{\nu,\rho} . Moreover, \|V^{\nu,\rho}-V^{n}\|_{\infty}=\|T^{\nu,\rho}V^{\nu,\rho}-T^{\nu,\rho}V^{n-1}\|_{\infty}\leqslant\gamma\|V^{\nu,\rho}-V^{n-1}\|_{\infty}, where the equality follows by definition of the sequence (V^{n})_{n\in\mathbb{N}} and because V^{\nu,\rho} is a fixed point of T^{\nu,\rho} and the inequality is because T^{\nu,\rho} is a contraction under the assumption of Proposition 4.2 . We conclude by induction that \|V^{\nu,\rho}-V^{n}\|_{\infty}\leqslant\gamma^{n}\|V^{\nu,\rho}-V^{0}\|_{\infty} for any n\in\mathbb{N} . There remains to bound \|V^{\pi^{n},\nu,\rho}-V^{\nu,\rho}\|_{\infty} based on our bound on \|V^{\nu,\rho}-V^{n}\|_{\infty} . Note that \displaystyle\|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|V^{\nu,\rho}-T^{\pi_{n},\nu,\rho}V^{n-1}+T^{\pi_{n},\nu,\rho}V^{n-1}-V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|V^{\nu,\rho}-T^{\nu,\rho}V^{n-1}+T^{\pi_{n},\nu,\rho}V^{n-1}-V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle\leqslant\|V^{\nu,\rho}-T^{\nu,\rho}V^{n-1}\|_{\infty}+\|T^{\pi_{n},\nu,\rho}V^{n-1}-V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|T^{\nu,\rho}V^{\nu,\rho}-T^{\nu,\rho}V^{n-1}\|_{\infty}+\|T^{\pi_{n},\nu,\rho}V^{n-1}-T^{\pi_{n},\nu,\rho}V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle\leqslant\gamma\|V^{\nu,\rho}-V^{n-1}\|_{\infty}+\gamma\|V^{n-1}-V^{\pi^{n},\nu,\rho}\|_{\infty} where the first equality is by adding and substracting the vector T^{\pi_{n},\nu,\rho}V^{n-1} , the second equality is by definition of \pi^{n} for value iteration, the first inequality is by triangle inequality, the third equality is by V^{\nu,\rho} and V^{\pi^{n},\nu,\rho} being the fixed points of T^{\nu,\rho} and T^{\pi^{n},\nu,\rho} following 1 and 2 , and the last inequality is from these operators being contractions. Now we also have \displaystyle\|V^{n-1}-V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|V^{n-1}-V^{\nu,\rho}+V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty}\leqslant\|V^{n-1}-V^{\nu,\rho}\|_{\infty}+\|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty} where the equality is by adding and substracting V^{\nu,\rho} and the inequality follows the triangle inequality. Overall we have shown \displaystyle\|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty}\leqslant\gamma\|V^{\nu,\rho}-V^{n-1}\|_{\infty}+\gamma(\|V^{n-1}-V^{\nu,\rho}\|_{\infty}+\|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty}) which we can rearrange to obtain \|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty}\leqslant\frac{2\gamma}{1-\gamma}\|V^{n-1}-V^{\nu,\rho}\|_{\infty}\;. We therefore conclude that \|V^{\pi^{n},\nu,\rho}-V^{\nu,\rho}\|_{\infty}\leqslant\frac{2\gamma^{n}}{1-\gamma}\|V^{\pi^{0},\nu,\rho}-V^{\nu,\rho}\|_{\infty}. 2. Let n\in\mathbb{N} . We first show that V^{\pi^{n},\nu,\rho}\leqslant V^{\pi^{n+1},\nu,\rho} . We have T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}=T^{\nu,\rho}V^{\pi^{n+1},\nu,\rho}\geqslant T^{\pi^{n},\nu,\rho}V^{\pi^{n},\nu,\rho}=V^{\pi^{n},\nu,\rho} where the first equality is by definition of \pi^{n+1} , where the inequality is from the definition of the Bellman optimality operator T^{\nu,\rho} , and the second equality is from 1 . Therefore we obtain T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\geqslant V^{\pi^{n},\nu,\rho} . Since T^{\pi^{n+1},\nu,\rho} is a monotone increasing contraction under the assumptions of Proposition 4.2 , applying repeatedly the operator T^{\pi^{n+1},\nu,\rho} to the component-wise inequality T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\geqslant V^{\pi^{n},\nu,\rho} yields V^{\pi^{n+1},\nu,\rho}\geqslant V^{\pi^{n},\nu,\rho} . We now prove that V^{\pi^{n},\nu,\rho} converges to V^{\nu,\rho} at a linear rate. We have \displaystyle V^{\nu,\rho}-V^{\pi^{n+1},\nu,\rho} \displaystyle=V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n+1},\nu,\rho} \displaystyle=V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}+T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n+1},\nu,\rho} \displaystyle\leqslant V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho} where we use 1 for the first equality, where we add and subtract the vector T^{\pi^{n},\nu,\rho}V^{\pi^{n+1},\nu,\rho} in the second equality, and where the inequality follows from T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\leqslant T^{\pi^{n+1},\nu,\rho}V^{\pi^{n+1},\nu,\rho} , itself a consequence of V^{\pi^{n},\nu,\rho}\leqslant V^{\pi^{n+1},\nu,\rho} and the fact that T^{\pi^{n+1},\nu,\rho} is a monotone contraction. Now we have \displaystyle\|V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|T^{\nu,\rho}V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle=\|T^{\pi^{\star},\nu,\rho}V^{\nu,\rho}-T^{\pi^{n+1},\nu,\rho}V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle\leqslant\|T^{\pi^{\star},\nu,\rho}V^{\nu,\rho}-T^{\pi^{\star},\nu,\rho}V^{\pi^{n},\nu,\rho}\|_{\infty} \displaystyle\leqslant\gamma\|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty} where the equality uses 2 , the second equality uses the existence of a policy \pi^{\star}\in\Pi_{\sf S} such that T^{\pi^{\star},\nu,\rho}V^{\nu,\rho}=V^{\nu,\rho} (the attainability property from Proposition 3.7 ), the first inequality is from the definition of \pi^{n+1} , and the last inequality is from the operator T^{\pi^{\star},\nu,\rho} being a contraction. By induction we directly obtain that \|V^{\nu,\rho}-V^{\pi^{n},\nu,\rho}\|_{\infty}\leqslant\gamma^{n}\|V^{\nu,\rho}-V^{\pi^{0},\nu,\rho}\|_{\infty} which concludes the proof. ∎ It is also possible to obtain a convex program with V^{\nu,\rho} as a unique solution, as we show in the next proposition. We need here that \rho is a convex risk measure, in the sense defined in Appendix A : \rho(\lambda\tilde{X}+(1-\lambda)\tilde{Y})\leqslant\lambda\rho(\tilde{X})+(1-\lambda)\rho(\tilde{Y}) for any random variables \tilde{X},\tilde{Y} and scalar \lambda\in[0,1] . An example of convex risk measure is the essential supremum. Proposition G.1 . Assume that \rho is monotone, translation-invariant and convex. Then V^{\nu,\rho} can be recovered as the unique solution to the following convex optimization program: \min\left\{\sum_{s\in\mathcal{S}}V(s)\;|\;V\in\mathbb{R}^{\mathcal{S}},V(s)\geqslant T^{\nu,\rho}V(s),\forall\;s\in\mathcal{S}\right\}. Proof. Since \rho is monotone and translation invariant, we know that T^{\nu,\rho} is a monotone contraction from Proposition 3.7 . From the contraction lemma (Lemma 3.1 in 20 ), V^{\nu,\rho} is the unique fixed point of the optimization problem \min\left\{\sum_{s\in\mathcal{S}}V(s)\;|\;V\in\mathbb{R}^{\mathcal{S}},V(s)\geqslant T^{\nu,\rho}V(s),\forall\;s\in\mathcal{S}\right\}\;. It remains to show that this optimization problem is convex. By construction, T^{\pi,P} is a monotone affine operator for each \pi\in\Pi_{\sf S},P\in\Delta(\mathcal{S})^{\mathcal{S}\times\mathcal{A}} . Therefore, v\mapsto T^{\pi,\nu,\rho}v(s) is convex, since by definition T^{\pi,\nu,\rho} is the composition of a convex operator T^{\pi,P} with monotone convex random variable \rho (see Section 3.2.4 in 4 ), and v\mapsto T^{\nu,\rho}v(s) is convex as the pointwise supremum of convex functions (see Section 3.2.3 in 4 ). ∎ Evaluating the Bellman operators The efficient computations of the Bellman operators have been studied in some cases. For robust MDPs, we have, for v\in\mathbb{R}^{\mathcal{S}} and s\in\mathcal{S} , \displaystyle T^{\pi,\nu,\rho}v(s) \displaystyle=\inf_{P\in\mathcal{P}}T^{\pi,P}v(s) \displaystyle T^{\nu,\rho}v(s) \displaystyle=\sup_{\pi\in\Pi_{\sf S}}\inf_{P\in\mathcal{P}}T^{\pi,P}v(s) which shows that evaluating T^{\pi,\nu,\rho}v requires solving linear programs over \mathcal{P} , and evaluating T^{\nu,\rho}v requires solving saddle-point problems over \Pi_{\sf S}\times\mathcal{P} . Under some additional assumptions on the uncertainty set \mathcal{P} , one can evaluate the Bellman operators in polynomial time, e.g., for sets based on weighted \ell_{1} -norm [ 29 , 26 ] , \ell_{2} -norm [ 29 ] , entropy and Kullback-Leibler divergence [ 42 ] , and \ell_{\infty} -norm [ 15 ] . The case of optimistic MDPs can be treated similarly by noting that \operatorname{ess\,sup}(\tilde{X})=-\operatorname{ess\,inf}(-\tilde{X}) . The case of more general risk measures requires resorting to numerical estimates. For instance, for CVaR one can compute {\sf CVaR}(\tilde{X}) by solving the optimization problem ( 10 ), which only involves a supremum over a single real variable. In general, one can result to sample-average approximation or Monte-Carlo methods to estimate VaR or CVaR , and we refer to Chapters 5-6 in 52 for some discussion on this and to 47 for a seminal reference. Appendix H Proofs of Section 4.2 In this appendix we provide the proof for the results stated in Theorem 4.4 and Theorem 4.5 . As discussed in Section 4.2 , some of these results are already known: • For static kernels, the literature on s-rectangular robust MDPs [ 59 ] and optimistic MDPs [ 15 ] show that 1 and 2 hold when \rho\in\{\operatorname{ess\,inf},\operatorname{ess\,sup}\} . • For resampled kernels, a recent result for s-rectangular robust MDPs (Proposition 2.2 in 59 ) and a seminal result in DRMDPs (Theorem 4.1 and Theorem 4.2 in 60 ) show that 1 and 2 are implied by the fact that \rho\in\{\operatorname{ess\,inf},\operatorname{ess\,sup},\mathbb{E}^{\nu}\} . We also recall that \operatorname{ess\,sup},\operatorname{ess\,inf} are not W^{1} -continuous (see Appendix A ). Therefore, we are left with proving that: • For proving Theorem 4.4 , there remains to show that for \rho monotone and law-invariant, 1. for static kernels, each 1 and 2 individually implies \rho\in\{\operatorname{ess\,inf},\operatorname{ess\,sup}\} 2. for resampled kernels, each 1 and 2 individually implies \rho\in\{\operatorname{ess\,inf},\operatorname{ess\,sup},\mathbb{E}^{\nu}\} . • For proving Theorem 4.5 , we show that for \rho W^{1} -continuous and law-invariant, each 1 and 2 individually implies that \rho=\mathbb{E}^{\nu} for both the cases of static and resampled kernels. We then conclude since we know that \rho=\mathbb{E}^{\nu} doesn’t yield dynamic programming equation for static kernels, as highlighted in example E.1 . We provide the proof of Proposition 4.3 in Appendix H.1 , the proof of Theorem 4.4 in Appendix H.2 , and the proof of Theorem 4.5 in Appendix H.3 . In the remainder of this section, we use the notations and the rigorous probabilistic framework introduced in Appendix B . H.1 Proof of Proposition 4.3 We start with the following lemma. Both equations can be derived from 1 or 2 applied to the single-policy MDP structure of Figure 3 . We emphasize here that we only use the single-policy MDP structure of Figure 3 among all the possibilities in \mathcal{M}_{c} (because both conditions 1 and 2 concern all the ambiguity-averse MDPs in \mathcal{M}_{c} ). While the second equation will be useful later to establish that \rho(0)=0 , the first equation alone contains the key property needed to derive all the results of Proposition 4.3 . We recall that (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) is the probability space associated with a specific ambiguity-averse MDP {\sf M} , as defined right after Definition B.2 . Lemma H.1 . Let \rho be a risk measure that is law invariant on L^{\infty}_{c}(\mathbb{R}) . If \rho satisfies 1 or 2 in either the case of static kernels or resampled kernels, then the following statements hold: 1. for any {\sf M}\in\mathcal{M} and independent random variables (\tilde{X},\tilde{Y},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})^{2}\times L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};[0,1]) , \forall\gamma\in[0,1),\quad\rho\Big(\gamma\big(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\big)\Big)=\rho\Big(\gamma\big(\tilde{Z}\rho(\tilde{X})+(1-\tilde{Z})\rho(\tilde{Y})\big)\Big)\;. 2. \forall C\in\mathbb{R},\forall\gamma\in[0,1),\rho(C)=\rho(C+\gamma\rho(0))\;. Proof. Let \rho be a risk measure that is law-invariant on L^{\infty}_{c}(\mathbb{R}) and that satisfies 1 or 2 in either the case of static kernels or resampled kernels and \gamma\in[0,1) . The statement is obvious for \gamma=0 , and we assume \gamma\in(0,1) in the rest of this proof. We will consider an ambiguity-averse MDP with a single possible action, therefore there is a single possible policy (the one that consists in always taking the only possible action with probability 1 ), noted \pi , and 1 or 2 applied to this specific ambiguity-averse MDP yield the exact same conclusion. Let {\sf M}\in\mathcal{M} and (\tilde{X},\tilde{Y},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})^{2}\times L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};[0,1]) be three independent random variables. Because \tilde{X},\tilde{Y} are bounded, there exists a,b,c,d\in\mathbb{R}^{2}\times(\mathbb{R}^{\star})^{2} such that \frac{\tilde{X}-a}{c}\in[0,1] a.s. and \frac{\tilde{Y}-b}{d}\in[0,1] a.s. Our goal is now to define the ambiguity-averse MDP of Figure 3 in such a way that \mathcal{L}(\tilde{X}^{\prime})=\mathcal{L}(\frac{\tilde{X}-a}{c}) , \mathcal{L}(\tilde{Y}^{\prime})=\mathcal{L}(\frac{\tilde{Y}-b}{d}) and \mathcal{L}(\tilde{Z}^{\prime})=\mathcal{L}(\tilde{Z}) , where \mathcal{L}(\cdot) denotes the law of a random variable. Let \mathcal{S}=\{{\sf Start},{\sf Left},{\sf Right},{\sf WinL},{\sf LoseL},{\sf WinR},{\sf LoseR}\} , \mathcal{A}=\{1\} , \gamma\in(0,1) and r a reward function such that r({\sf Left},1,s^{\prime})=a,\,r({\sf Right},1,s^{\prime})=b,\,r({\sf WinL},1,s^{\prime})=\gamma^{-1}c,\,r({\sf WinR},1,s^{\prime})=\gamma^{-1}d and the reward associated with any other transition is equal to 0 . We now define the transition kernel law \nu as \nu=\mathcal{L}\left(\begin{pmatrix}0&\tilde{Z}&1-\tilde{Z}&0&0&0&0\\ 0&0&0&\frac{\tilde{X}-a}{c}&1-\frac{\tilde{X}-a}{c}&0&0\\ 0&0&0&0&0&\frac{\tilde{Y}-b}{d}&1-\frac{\tilde{Y}-b}{d}\\ 0&0&0&0&1&0&0\\ 0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1\end{pmatrix}\right)\;. Because \tilde{X},\tilde{Y},\tilde{Z} all have convex support, the law \nu has convex support and by independence of \tilde{X},\tilde{Y},\tilde{Z} , \nu also has a product structure. Consequently, having \mu\in\Delta(\mathcal{S}) , the tuple (\mathcal{S},\mathcal{A},r,\nu,\gamma,\mu) is a valid ”convex, product” ambiguity-averse MDP that we note {\sf M}^{\prime}\in\mathcal{M}_{c} . The transition kernel sequence now depends on the sampling case: • Static transition kernel sequence: Denoting by \tilde{P} the static transition kernel sequence of the ambiguity-averse MDP {\sf M}^{\prime} , we define \tilde{Z}^{\prime}=\tilde{P}_{t=0}({\sf Start},1,{\sf Left}),\,\tilde{X}^{\prime}=\tilde{P}_{t=0}({\sf Left},1,{\sf WinL}) and \tilde{Y}^{\prime}=\tilde{P}_{t=0}({\sf Right},1,{\sf WinR}) . By construction \tilde{X}^{\prime},\tilde{Y}^{\prime},\tilde{Z}^{\prime} are three independent random variables in L^{\infty}_{c}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};[0,1]) such that \mathcal{L}(\tilde{X}^{\prime})=\mathcal{L}(\frac{\tilde{X}-a}{c}) , \mathcal{L}(\tilde{Y}^{\prime})=\mathcal{L}(\frac{\tilde{Y}-b}{d}) and \mathcal{L}(\tilde{Z}^{\prime})=\mathcal{L}(\tilde{Z}) . In particular, by independence, we also have \mathcal{L}\left((c\tilde{X}^{\prime}+a,d\tilde{Y}^{\prime}+b,\tilde{Z}^{\prime})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y},\tilde{Z})\right) . The transition kernel of {\sf M}^{\prime} is such that {\sf Start} goes to {\sf Left} with probability \tilde{Z}^{\prime} and to {\sf Right} with probability 1-\tilde{Z}^{\prime} . From {\sf Left} , the transition to {\sf WinL} happens with probability \tilde{X}^{\prime} and to {\sf LoseL} with probability 1-\tilde{X}^{\prime} . From {\sf Right} , the transition to {\sf WinR} happens with probability \tilde{Y}^{\prime} and to {\sf LoseR} with probability 1-\tilde{Y}^{\prime} . From {\sf WinL} / {\sf WinR} , the transition goes deterministically to {\sf LoseL} / {\sf LoseR} , and from {\sf LoseL} / {\sf LoseR} , the state self-loops. Figure 3: Ambiguity-averse MDP with \mathcal{S}=\{{\sf Start},{\sf Left},{\sf Right},{\sf WinL},{\sf LoseL},{\sf WinR},{\sf LoseR}\} , \mathcal{A}=\{1\} . The edges (s,a,s^{\prime}) are labeled with pairs (P(s,a,s^{\prime}),r(s,a,s^{\prime})) . On the one hand, because there is a single policy, the ambiguity-averse value function and the optimal ambiguity-averse value function are equal, and V=V^{\pi,\nu,\rho}=V^{\nu,\rho} is given by \displaystyle V({\sf Start}) \displaystyle=\rho\left(\gamma\left(\tilde{Z}^{\prime}(a+\gamma\tilde{X}^{\prime}\cdot\gamma^{-1}c)+(1-\tilde{Z}^{\prime})(b+\gamma\tilde{Y}^{\prime}\cdot\gamma^{-1}d)\right)\right) \displaystyle=\rho\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right) \displaystyle V({\sf Left}) \displaystyle=\rho\left(a+\gamma\tilde{X}^{\prime}\gamma^{-1}c+\gamma(1-\tilde{X}^{\prime})\cdot 0\right)=\rho\left(a+\tilde{X}^{\prime}c\right)=\rho(\tilde{X}) \displaystyle V({\sf Right}) \displaystyle=\rho\left(b+\gamma\tilde{Y}^{\prime}\gamma^{-1}d+\gamma(1-\tilde{Y}^{\prime})\cdot 0\right)=\rho\left(b+\tilde{Y}^{\prime}d\right)=\rho(\tilde{Y}) \displaystyle V({\sf WinL}) \displaystyle=\rho\left(\gamma^{-1}c\right) \displaystyle V({\sf LoseL}) \displaystyle=\rho(0) \displaystyle V({\sf WinR}) \displaystyle=\rho\left(\gamma^{-1}d\right) \displaystyle V({\sf LoseR}) \displaystyle=\rho(0)\;, where the last equalities in the first three lines come from \mathcal{L}\left((c\tilde{X}^{\prime}+a,d\tilde{Y}^{\prime}+b,\tilde{Z}^{\prime})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y},\tilde{Z})\right) and \rho is law-invariant. On the other hand, the operator T=T^{\pi,\nu,\rho}=T^{\nu,\rho} is defined by: \displaystyle\forall v\in\mathbb{R}^{7},\quad T\left(\begin{pmatrix}v({\sf Start})\\ v({\sf Left})\\ v({\sf Right})\\ v({\sf WinL})\\ v({\sf LoseL})\\ v({\sf WinR})\\ v({\sf LoseR})\end{pmatrix}\right)=\begin{pmatrix}\rho\left(\gamma(\tilde{Z}^{\prime}v({\sf Left})+(1-\tilde{Z}^{\prime})v({\sf Right}))\right)\\ \rho\left(a+\gamma(\tilde{X}^{\prime}v({\sf WinL})+(1-\tilde{X}^{\prime})v({\sf LoseL}))\right)\\ \rho\left(b+\gamma(\tilde{Y}^{\prime}v({\sf WinR})+(1-\tilde{Y}^{\prime})v({\sf LoseR}))\right)\\ \rho\left(\gamma^{-1}c+\gamma v({\sf LoseL})\right)\\ \rho\left(\gamma v({\sf LoseL})\right)\\ \rho\left(\gamma^{-1}d+\gamma v({\sf LoseR})\right)\\ \rho\left(\gamma v({\sf LoseR})\right)\end{pmatrix}\;. Then, by 1 or 2 , because {\sf M}^{\prime}\in\mathcal{M}_{c} (and \pi\in\Pi_{S} ), we have V=TV : \left\{\begin{aligned} &\rho\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right)=\rho\left(\gamma\left(\tilde{Z}^{\prime}\rho(\tilde{X})+(1-\tilde{Z}^{\prime})\rho(\tilde{Y})\right)\right)\\ &\rho\left(\tilde{X}\right)=\rho\left(a+\gamma\left(\tilde{X}^{\prime}\rho\left(\gamma^{-1}c\right)+(1-\tilde{X}^{\prime})\rho(0)\right)\right)\\ &\rho\left(\tilde{Y}\right)=\rho\left(b+\gamma\left(\tilde{Y}^{\prime}\rho\left(\gamma^{-1}d\right)+(1-\tilde{Y}^{\prime})\rho(0)\right)\right)\\ &\rho\left(\gamma^{-1}c\right)=\rho\left(\gamma^{-1}c+\gamma\rho(0)\right)\\ &\rho(0)=\rho\left(\gamma\rho(0)\right)\\ &\rho\left(\gamma^{-1}d\right)=\rho\left(\gamma^{-1}d+\gamma\rho(0)\right)\\ &\rho(0)=\rho\left(\gamma\rho(0)\right)\end{aligned}\right. The first equation gives the first part of the desired result after using \mathcal{L}(\tilde{Z}^{\prime})=\mathcal{L}(\tilde{Z}) and law-invariance. We also note that the fourth equation \rho\left(\gamma^{-1}c\right)=\rho\left(\gamma^{-1}c+\gamma\rho(0)\right) holds for any c\in\mathbb{R} . Consequently, we also have \forall C\in\mathbb{R},\rho(C)=\rho(C+\gamma\rho(0)) . • Resampled kernels: Denoting by \tilde{P} the resampled transition kernel sequence of the ambiguity-averse MDP {\sf M}^{\prime}\in\mathcal{M}_{c} , we define, for any t\in\mathbb{N} , \tilde{Z}^{\prime}_{t}=\tilde{P}_{t}({\sf Start},1,{\sf Left}),\,\tilde{X}^{\prime}_{t}=\tilde{P}_{t}({\sf Left},1,{\sf WinL}) and \tilde{Y}^{\prime}_{t}=\tilde{P}_{t}({\sf Right},1,{\sf WinR}) . By construction, for any t\in\mathbb{N} , \tilde{X}^{\prime}_{t},\tilde{Y}^{\prime}_{t},\tilde{Z}^{\prime}_{t} are three independent random variables in L^{\infty}_{c}(\Omega_{{\sf M}^{\prime}},\mathcal{F}_{{\sf M}^{\prime}},\mathbb{P}_{{\sf M}^{\prime}};[0,1]) such that \mathcal{L}(\tilde{X}^{\prime}_{t})=\mathcal{L}(\frac{\tilde{X}-a}{c}) , \mathcal{L}(\tilde{Y}^{\prime}_{t})=\mathcal{L}(\frac{\tilde{Y}-b}{d}) and \mathcal{L}(\tilde{Z}^{\prime}_{t})=\mathcal{L}(\tilde{Z}) . In particular, by independence, for any t_{1},t_{2},t_{3}\in\mathbb{N} we also have \mathcal{L}\left((c\tilde{X}^{\prime}_{t_{1}}+a,d\tilde{Y}^{\prime}_{t_{2}}+b,\tilde{Z}^{\prime}_{t_{3}})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y},\tilde{Z})\right) . Therefore, at time t\in\mathbb{N} , the transition kernel of {\sf M}^{\prime} is such that {\sf Start} goes to {\sf Left} with probability \tilde{Z}^{\prime}_{t} and to {\sf Right} with probability 1-\tilde{Z}^{\prime}_{t} . From {\sf Left} , the transition to {\sf WinL} happens with probability \tilde{X}^{\prime}_{t} and to {\sf LoseL} with probability 1-\tilde{X}^{\prime}_{t} . From {\sf Right} , the transition to {\sf WinR} happens with probability \tilde{Y}^{\prime}_{t} and to {\sf LoseR} with probability 1-\tilde{Y}^{\prime}_{t} . From {\sf WinL} / {\sf WinR} , the transition goes deterministically to {\sf LoseL} / {\sf LoseR} , and from {\sf LoseL} / {\sf LoseR} , the state self-loops. Now, V=V^{\pi,\nu,\rho}=V^{\nu,\rho} from starting at time t=0 in a state s is given by \displaystyle V({\sf Start}) \displaystyle=\rho\left(\gamma\left(\tilde{Z}^{\prime}_{0}(a+\gamma\tilde{X}^{\prime}_{1}\cdot\gamma^{-1}c)+(1-\tilde{Z}^{\prime}_{0})(b+\gamma\tilde{Y}^{\prime}_{1}\cdot\gamma^{-1}d)\right)\right) \displaystyle=\rho\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right) \displaystyle V({\sf Left}) \displaystyle=\rho\left(a+\gamma\tilde{X}^{\prime}_{0}\gamma^{-1}c+\gamma(1-\tilde{X}^{\prime}_{0})\cdot 0\right)=\rho\left(a+\tilde{X}^{\prime}_{0}c\right)=\rho(\tilde{X}) \displaystyle V({\sf Right}) \displaystyle=\rho\left(b+\gamma\tilde{Y}^{\prime}\gamma^{-1}d+\gamma(1-\tilde{Y}^{\prime}_{0})\cdot 0\right)=\rho\left(b+\tilde{Y}^{\prime}_{0}d\right)=\rho(\tilde{Y}) \displaystyle V({\sf WinL}) \displaystyle=\rho\left(\gamma^{-1}c\right) \displaystyle V({\sf LoseL}) \displaystyle=\rho(0) \displaystyle V({\sf WinR}) \displaystyle=\rho\left(\gamma^{-1}d\right) \displaystyle V({\sf LoseR}) \displaystyle=\rho(0) where the last equalities in the first three lines come from the law invariance of \rho and from the fact that \mathcal{L}\left((a+c\tilde{X}^{\prime}_{1},b+d\tilde{Y}^{\prime}_{1},\tilde{Z}^{\prime}_{0})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y},\tilde{Z})\right) and \mathcal{L}\left((a+c\tilde{X}^{\prime}_{0},b+d\tilde{Y}^{\prime}_{0})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y})\right) . To explicitly describe the random return in the first line, we have that starting from position {\sf Start} at time t=0 , the transition to {\sf Left} happens with probability \tilde{Z}^{\prime}_{0} and to {\sf Right} with probability 1-\tilde{Z}^{\prime}_{0} . If the next state is {\sf Left} , then at time t=1 , the transition to {\sf WinL} happens with probability \tilde{X}^{\prime}_{1} and to {\sf LoseL} with probability 1-\tilde{X}^{\prime}_{1} , yielding a total return of a+\gamma\tilde{X}^{\prime}_{1}\cdot\gamma^{-1}c . If the next state is {\sf Right} , then at time t=1 , the transition to {\sf WinR} happens with probability \tilde{Y}^{\prime}_{1} and to {\sf LoseR} with probability 1-\tilde{Y}^{\prime}_{1} , yielding a total return of b+\gamma\tilde{Y}^{\prime}_{1}\cdot\gamma^{-1}d . On the other hand, the operator T=T^{\pi,\nu,\rho}=T^{\nu,\rho} is defined by: \displaystyle\forall v\in\mathbb{R}^{7},\quad T\left(\begin{pmatrix}v({\sf Start})\\ v({\sf Left})\\ v({\sf Right})\\ v({\sf WinL})\\ v({\sf LoseL})\\ v({\sf WinR})\\ v({\sf LoseR})\end{pmatrix}\right)=\begin{pmatrix}\rho\left(\gamma(\tilde{Z}^{\prime}_{0}v({\sf Left})+(1-\tilde{Z}^{\prime}_{0})v({\sf Right}))\right)\\ \rho\left(a+\gamma(\tilde{X}^{\prime}_{0}v({\sf WinL})+(1-\tilde{X}^{\prime}_{0})v({\sf LoseL}))\right)\\ \rho\left(b+\gamma(\tilde{Y}^{\prime}_{0}v({\sf WinR})+(1-\tilde{Y}^{\prime}_{0})v({\sf LoseR}))\right)\\ \rho\left(\gamma^{-1}c+\gamma v({\sf LoseL})\right)\\ \rho\left(\gamma v({\sf LoseL})\right)\\ \rho\left(\gamma^{-1}d+\gamma v({\sf LoseR})\right)\\ \rho\left(\gamma v({\sf LoseR})\right)\end{pmatrix}\;. Then, by 1 or 2 , because {\sf M}^{\prime}\in\mathcal{M}_{c} (and \pi\in\Pi_{S} ), we have V=TV : \left\{\begin{aligned} &\rho\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right)=\rho\left(\gamma(\tilde{Z}^{\prime}_{0}\rho(\tilde{X})+(1-\tilde{Z}^{\prime}_{0})\rho(\tilde{Y})\right)\\ &\rho(\tilde{X})=\rho\left(a+\gamma(\tilde{X}^{\prime}_{0}\rho\left(\gamma^{-1}c\right)+(1-\tilde{X}^{\prime}_{0})\rho(0))\right)\\ &\rho(\tilde{Y})=\rho\left(b+\gamma(\tilde{Y}^{\prime}_{0}\rho\left(\gamma^{-1}d\right)+(1-\tilde{Y}^{\prime}_{0})\rho(0))\right)\\ &\rho\left(\gamma^{-1}c\right)=\rho\left(\gamma^{-1}c+\gamma\rho(0)\right)\\ &\rho(0)=\rho\left(\gamma\rho(0)\right),\\ &\rho\left(\gamma^{-1}d\right)=\rho\left(\gamma^{-1}d+\gamma\rho(0)\right)\\ &\rho(0)=\rho\left(\gamma\rho(0)\right)\end{aligned}\right. The first equation gives \displaystyle\rho\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right) \displaystyle=\rho\left(\gamma(\tilde{Z}^{\prime}_{0}\rho(\tilde{X})+(1-\tilde{Z}^{\prime}_{0})\rho(\tilde{Y}))\right) \displaystyle=\rho\left(\gamma(\tilde{Z}\rho(\tilde{X})+(1-\tilde{Z})\rho(\tilde{Y}))\right)\;, after using the law invariance of \rho and from the fact that \mathcal{L}(\tilde{Z}^{\prime}_{0})=\mathcal{L}(\tilde{Z}) . As in the case of static kernels, the fourth equation implies that \forall C\in\mathbb{R},\rho(C)=\rho(C+\gamma\rho(0)) . ∎ We will use the next technical lemma. Lemma H.2 . Let f:\mathbb{R}\to\mathbb{R} a non-constant function such that \displaystyle\forall(x,y,z)\in\mathbb{R}^{2}\times[0,1],\forall\gamma\in[0,1),\quad f\Big(\gamma\big(zx+(1-z)y\big)\Big)=f\Big(\gamma\big(zf(x)+(1-z)f(y)\big)\Big) (22) \displaystyle\forall C\in\mathbb{R},\forall\gamma\in[0,1)\quad f(C)=f(C+\gamma f(0)) (23) Then f is the identity: f(x)=x,\forall\;x\in\mathbb{R} . Proof. Let f be a non-constant function that satisfies Equations ( 22 )-( 23 ). We first have that f(0)=0 . Indeed, if f(0)\neq 0 , then for any C\in\mathbb{R} , Equation ( 23 ) directly implies that f is constant on any closed interval of length \lvert f(0)/2\rvert>0 and then, splitting the real line with points (n\frac{f(0)}{2})_{n\in\mathbb{Z}} , we get that f is constant on \mathbb{R} , which contradicts the assumption. We show the following auxiliary result: \forall a0 , so f is constant on \mathbb{R} , which contradicts the assumption. Finally, by ( 22 ) with \gamma=z=1/2 and y=0 , we have \forall x\in\mathbb{R},f(x/4)=f\left(\frac{1}{4}x+\frac{1}{4}0\right)=f\left(f(x)/4+f(0)/4\right)=f(f(x)/4)\;, so by injectivity of f , we have \forall x\in\mathbb{R},x/4=f(x)/4 and f is the identity. ∎ We now prove a slightly more general result than Proposition 4.3 : Proposition H.3 . Let \rho be a risk measure that is law-invariant and non-constant on L^{\infty}_{c}(\mathbb{R}) . If \rho satisfies 1 or 2 in either the case of static kernels or resampled kernels, then the following statements hold: 1. \rho coincides with the identity on constant random variables: \quad\forall x\in\mathbb{R},\quad\rho(x)=x 2. \rho is positive homogeneous on L^{\infty}_{c}(\mathbb{R}) : \quad\forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),\forall\alpha\geqslant 0,\quad\rho(\alpha\tilde{X})=\alpha\rho(\tilde{X}) 3. \rho is additive independent on L^{\infty}_{c}(\mathbb{R}) : \text{for any }{\sf M}\in\mathcal{M}\text{ and independent }\tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\quad\rho(\tilde{X}+\tilde{Y})=\rho(\tilde{X})+\rho(\tilde{Y})\;. 4. If \rho is also monotone on L^{\infty}_{c}(\mathbb{R}) , then, \text{for any }{\sf M}\in\mathcal{M}\text{ and independent }\tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}_{+}),\quad\rho(\tilde{X}\tilde{Y})=\rho(\tilde{X})\rho(\tilde{Y})\;. Proof. Let \rho be a risk measure that is law-invariant and non-constant on L^{\infty}_{c}(\mathbb{R}) , and that satisfies 1 or 2 in either the case of static kernels or resampled kernels. By the conclusion of Lemma H.1 we have, for any {\sf M}\in\mathcal{M} and independent random variables (\tilde{X},\tilde{Y},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})^{2}\times L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};[0,1]) , \forall\gamma\in[0,1),\quad\rho\Big(\gamma\big(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\big)\Big)=\rho\Big(\gamma\big(\tilde{Z}\rho(\tilde{X})+(1-\tilde{Z})\rho(\tilde{Y})\big)\Big)\;. (24) and \forall C\in\mathbb{R},\forall\gamma\in[0,1),\rho(C)=\rho(C+\gamma\rho(0)) . We first show that \rho_{\mid\mathbb{R}}:x\in\mathbb{R}\mapsto\rho(x) , the restriction of \rho to \mathbb{R} , is non-constant. In fact, because \rho is non-constant on L^{\infty}_{c}(\mathbb{R}) , there exists \tilde{W}\in L^{\infty}_{c}(\mathbb{R}) such that \rho(\tilde{W})\neq\rho(0) . Then, applying ( 24 ) with \tilde{Y}=0 , \tilde{Z}=1 , \gamma=1/2 and \tilde{X}=2\tilde{W} , we have \rho(1/2\cdot\rho(2\tilde{W}))=\rho(1/2\cdot 2\tilde{W})=\rho(\tilde{W})\neq\rho(0) so \rho(2\tilde{W})/2 is a real number whose image by \rho is different from \rho(0) and \rho_{\mid\mathbb{R}} is non-constant. By Lemma H.2 applied to \rho_{\mid\mathbb{R}} , we now know that \forall x\in\mathbb{R},\,\rho(x)=x . Then, Equation ( 24 ) with \tilde{Z}=\lambda for \lambda\in[0,1] now becomes, for any {\sf M}\in\mathcal{M} and independent random variables \tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) , \forall\lambda\in[0,1],\forall\gamma\in[0,1),\quad\rho\Big(\gamma\big(\lambda\tilde{X}+(1-\lambda)\tilde{Y}\big)\Big)=\gamma\big(\lambda\rho(\tilde{X})+(1-\lambda)\rho(\tilde{Y})\big)\;. (25) Taking \tilde{Y}=0 and \lambda=1 in Equation ( 25 ) we obtain that, \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),\forall\gamma\in[0,1),\quad\rho(\gamma\tilde{X})=\gamma\rho(\tilde{X})\;, which is still true for \gamma=1 . Now take \alpha\geqslant 1 , we have 0\leqslant\frac{1}{\alpha}\leqslant 1 so that \frac{1}{\alpha}\rho(\alpha\tilde{X})=\rho(\frac{1}{\alpha}\alpha\tilde{X})=\rho(\tilde{X}) , i.e. we have shown that \rho is positively homogeneous on L^{\infty}_{c}(\mathbb{R}) : \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),\forall\alpha\geqslant 0,\quad\rho(\alpha\tilde{X})=\alpha\rho(\tilde{X})\;. Then, taking \gamma=\lambda=1/2 in Equation ( 25 ) and using positive homogeneity, we obtain that \rho is additive for independent random variables: \text{for any }{\sf M}\in\mathcal{M}\text{ and independent }(\tilde{X},\tilde{Y})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\quad\rho(\tilde{X}+\tilde{Y})=\rho(\tilde{X})+\rho(\tilde{Y})\;. Finally, if \rho is also monotone, using Equation ( 24 ) with \tilde{Y}=0,\lambda=1 and \gamma=1/2 , we have that for any {\sf M}\in\mathcal{M} and independent random variables (\tilde{X},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}_{+})\times L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};[0,1]) : \rho\Big(\frac{1}{2}\tilde{Z}\tilde{X}\Big)=\rho\Big(\frac{1}{2}\tilde{Z}\rho(\tilde{X})\Big)=\rho(\tilde{X})\rho\Big(\frac{1}{2}\tilde{Z}\Big)\;, where we have used positive homogeneity and the fact that \rho(\tilde{X})\geqslant\rho(0)=0 by monotonicity. Then, by positive homogeneity again, we obtain \rho(\tilde{Z}\tilde{X})=\rho(\tilde{Z})\rho(\tilde{X})\;, which is still true if (\tilde{X},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}_{+})^{2} by positive homogeneity applied to \tilde{Z} . ∎ H.2 Proof of Theorem 4.4 We now provide the proof for Theorem 4.4 . The proof relies on the following representation theorem from 41 , which we state here with the notations and terminology of our paper. Theorem H.4 (Theorem 1 in 41 ) . If a risk-measure \Phi\colon L^{\infty}(\mathbb{R})\to\mathbb{R} coincides with the identity for constants and is law-invariant, monotone and additive independent on L^{\infty} , then there exists a unique Borel probability measure \mu on the extended real line \overline{\mathbb{R}} such that for every \tilde{X}\in L^{\infty}(\mathbb{R}) \Phi(\tilde{X})=\int_{\overline{\mathbb{R}}}{\sf ERM}_{a}(\tilde{X})\,d\mu(a). Remark H.5 . Monotonicity in 41 is defined with respect to the first-order stochastic dominance but, as argued before Theorem 1 in 41 , this is equivalent to our notion of monotonicity because of law-invariance. For the purpose of this work, we need a version of Theorem H.4 for risk measures defined on bounded random variables with a convex support L^{\infty}_{c}(\mathbb{R}) (whereas Theorem H.4 only applies to risk measures on L^{\infty}(\mathbb{R}) ). This is done in the next lemma, which states that an additive independent law-invariant risk measure defined on L^{\infty}_{c}(\mathbb{R}) can be extended to a law-invariant risk measure \mathring{\rho} defined on L^{\infty}(\mathbb{R}) , which preserves its main properties (e.g., additive independence and monotonicity). The key insight is that any random variable with nonconvex support can be represented as the difference of two random variables with convex support by adding an independent uniform noise. This property allows us to define the extension \mathring{\rho} of any random variable with not-necessarily convex support as the difference of the images by \rho of two random variables with convex support and this way preserve the algebraic properties (monotonicity, additive independence, positive homogeneity) required by the representation theorem. We recall that (\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}}) is the probability space associated with a specific ambiguity-averse MDP {\sf M}\in\mathcal{M} , as defined right after Definition B.2 . Lemma H.6 . Let \rho be a risk measure that is law-invariant on L^{\infty}_{c}(\mathbb{R}) . Assume additionally that \rho is additive independent on L^{\infty}_{c}(\mathbb{R}) : \text{for any }{\sf M}\in\mathcal{M}\text{ and independent }\tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\quad\rho(\tilde{X}+\tilde{Y})=\rho(\tilde{X})+\rho(\tilde{Y})\;. Then, there exists risk measure \mathring{\rho} that is law-invariant on L^{\infty}(\mathbb{R}) , that coincides with \rho on L^{\infty}_{c}(\mathbb{R}) (i.e., \forall X\in L^{\infty}_{c}(\mathbb{R}),\,\mathring{\rho}(X)=\rho(X) ) and such that the following statements hold: 1. \mathring{\rho} is additive independent on L^{\infty}(\mathbb{R}) : \text{for any }{\sf M}\in\mathcal{M}\text{ and independent }\tilde{X},\tilde{Y}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}),\quad\mathring{\rho}(\tilde{X}+\tilde{Y})=\mathring{\rho}(\tilde{X})+\mathring{\rho}(\tilde{Y})\;. 2. if \rho is positive homogeneous on L^{\infty}_{c}(\mathbb{R}) , then \mathring{\rho} is positive homogeneous on L^{\infty}(\mathbb{R}) : \Big[\forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),\forall\alpha\geqslant 0,\quad\rho(\alpha\tilde{X})=\alpha\rho(\tilde{X})\Big]\implies\Big[\forall\tilde{X}\in L^{\infty}(\mathbb{R}),\forall\alpha\geqslant 0,\quad\mathring{\rho}(\alpha\tilde{X})=\alpha\mathring{\rho}(\tilde{X})\Big]\;. 3. if \rho is monotone on L^{\infty}_{c}(\mathbb{R}) , then \mathring{\rho} is monotone on L^{\infty}(\mathbb{R}) : \displaystyle\Big[\text{for any }{\sf M}\in\mathcal{M}\text{ and }\tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\text{ s.t. }\tilde{X}\geqslant\tilde{Y}\text{ a.s.},\quad\rho(\tilde{X})\geqslant\rho(\tilde{Y})\Big] \displaystyle\implies\Big[\text{for any }{\sf M}\in\mathcal{M}\text{ and }\tilde{X},\tilde{Y}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})\text{ s.t. }\tilde{X}\geqslant\tilde{Y}\text{ a.s.},\quad\mathring{\rho}(\tilde{X})\geqslant\mathring{\rho}(\tilde{Y})\Big]\;. Proof of Lemma H.6 . Let \rho be a risk measure that is law-invariant and additive independent on L^{\infty}_{c}(\mathbb{R}) . Let {\sf M}_{0}\in\mathcal{M} an ambiguity-averse MDP such that (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is non-atomic (for example the one of Example E.1 ). For any \tilde{X}\in L^{\infty}_{c}(\mathbb{R}) , we define l_{X}=\operatorname{ess\,sup}(\tilde{X})-\operatorname{ess\,inf}(\tilde{X}) . By non-atomicity (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) , there exists \tilde{X}^{\prime},\tilde{U}_{\tilde{X}}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that \mathcal{L}(\tilde{X}^{\prime})=\mathcal{L}(\tilde{X}) , \tilde{U}_{\tilde{X}}\sim\text{Unif}([0,l_{X}]) and \tilde{X}^{\prime},\tilde{U}_{\tilde{X}} are independent. We call \tilde{U}_{\tilde{X}} a noise for \tilde{X}^{\prime} . We now observe that the support of \tilde{X}^{\prime}+\tilde{U}_{\tilde{X}} is the Minkowski sum of {\sf supp}(\tilde{X}^{\prime})\subseteq[\operatorname{ess\,inf}(\tilde{X}),\operatorname{ess\,sup}(\tilde{X})] and of [0,l_{X}] , so it is a closed interval of \mathbb{R} . Therefore, we can now define \mathring{\rho}(\tilde{X}):=\rho(\tilde{X}^{\prime}+\tilde{U}_{\tilde{X}})-\rho(\tilde{U}_{\tilde{X}})\;. (26) Note that by definition, \mathring{\rho} is well defined by law-invariance of \rho and it is itself a law-invariant risk measure on L^{\infty}(\mathbb{R}) (as a difference of two law-invariant risk measures) that coincides with \rho on L^{\infty}_{c}(\mathbb{R}) by additive independence of \rho on L^{\infty}_{c}(\mathbb{R}) . We also have, for any noise \tilde{V}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) independent of \tilde{X}^{\prime} and \tilde{U}_{\tilde{X}} with convex support that includes [0,l_{X}] , \mathring{\rho}(\tilde{X})=\rho(\tilde{X}^{\prime}+\tilde{V})-\rho(\tilde{V})\;. (27) Indeed, \tilde{U}_{\tilde{X}} , \tilde{V} , \tilde{X}^{\prime}+\tilde{U}_{\tilde{X}} , \tilde{X}^{\prime}+\tilde{V} and \tilde{X}^{\prime}+\tilde{U}_{\tilde{X}}+\tilde{V} all have convex support, so, \displaystyle\rho(\tilde{X}^{\prime}+\tilde{V})-\rho(\tilde{V}) \displaystyle=\rho((\tilde{X}^{\prime}+V)+\tilde{U}_{\tilde{X}})-\rho(\tilde{U}_{\tilde{X}})-\rho(\tilde{V}) \displaystyle=\rho((\tilde{X}^{\prime}+\tilde{U}_{\tilde{X}})+\tilde{V})-\rho(\tilde{V})-\rho(\tilde{U}_{\tilde{X}}) \displaystyle=\rho(\tilde{X}^{\prime}+\tilde{U}_{\tilde{X}})-\rho(\tilde{U}_{\tilde{X}}) \displaystyle=\mathring{\rho}(\tilde{X})\;. 1. Let {\sf M}\in\mathcal{M} and two independent random variables \tilde{X},\tilde{Y}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) . There exists independent random variables \tilde{X}^{\prime},\tilde{Y}^{\prime},\tilde{U}_{\tilde{X}},\tilde{U}_{\tilde{Y}}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that \mathcal{L}(\tilde{X}^{\prime})=\mathcal{L}(\tilde{X}) , \mathcal{L}(\tilde{Y}^{\prime})=\mathcal{L}(\tilde{Y}) and \tilde{U}_{\tilde{X}},\tilde{U}_{\tilde{Y}} are noises for \tilde{X}^{\prime} and \tilde{Y}^{\prime} . We now have, \displaystyle\mathring{\rho}(\tilde{X})+\mathring{\rho}(\tilde{Y}) \displaystyle=\rho(\tilde{X}^{\prime}+\tilde{U}_{\tilde{X}})+\rho(\tilde{Y}^{\prime}+\tilde{U}_{\tilde{Y}})-\rho(\tilde{U}_{\tilde{X}})-\rho(\tilde{U}_{\tilde{Y}}) \displaystyle=\rho(\tilde{X}^{\prime}+\tilde{Y}^{\prime}+\tilde{U}_{\tilde{X}}+\tilde{U}_{\tilde{Y}})-\rho(\tilde{U}_{\tilde{X}}+\tilde{U}_{\tilde{Y}}) \displaystyle=\mathring{\rho}(\tilde{X}+\tilde{Y})\;, where the last equality comes from using Equation 27 because \tilde{U}_{\tilde{X}}+\tilde{U}_{\tilde{Y}} has support exactly [0,l_{X}+l_{Y}] and is independent of \tilde{X}+\tilde{Y} . Therefore, \mathring{\rho} is additive independent on L^{\infty}(\mathbb{R}) . 2. Assume that \rho is positive homogeneous on L^{\infty}_{c}(\mathbb{R}) . Then, for any \tilde{X}\in L^{\infty}(\mathbb{R}) and \alpha\geqslant 0 , there exists independent \tilde{X}^{\prime},\tilde{U}_{\tilde{X}}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that \mathcal{L}(\tilde{X}^{\prime})=\mathcal{L}(\tilde{X}) and \tilde{U}_{\tilde{X}} is a noise for \tilde{X}^{\prime} . We now have \displaystyle\alpha\mathring{\rho}(\tilde{X}) \displaystyle=\alpha\rho(\tilde{X}^{\prime}+\tilde{U}_{\tilde{X}})-\alpha\rho(\tilde{U}_{\tilde{X}}) \displaystyle=\rho(\alpha\tilde{X}^{\prime}+\alpha\tilde{U}_{\tilde{X}})-\rho(\alpha\tilde{U}_{\tilde{X}}) \displaystyle=\mathring{\rho}(\alpha\tilde{X})\;, where the last equality comes from using Equation 27 because \alpha\tilde{U}_{\tilde{X}} has support exactly [0,\alpha l_{X}] and is independent of \alpha\tilde{X}^{\prime} . Therefore, \mathring{\rho} is positive homogeneous on L^{\infty}(\mathbb{R}) . 3. Assume that \rho is monotone on L^{\infty}_{c}(\mathbb{R}) . Let {\sf M}\in\mathcal{M} and two random variables \tilde{X},\tilde{Y}\in L^{\infty}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}) such that \tilde{X}\geqslant\tilde{Y} almost surely. There exists random variables \tilde{X}^{\prime},\tilde{Y}^{\prime},\tilde{U}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that \mathcal{L}\left((\tilde{X}^{\prime},\tilde{Y}^{\prime})\right)=\mathcal{L}\left((\tilde{X},\tilde{Y})\right) , \tilde{U}\sim\text{Unif}([0,\max(l_{X},l_{Y})]) and \tilde{U} is independent to both \tilde{X}^{\prime} and \tilde{Y}^{\prime} . In particular, because their joint law is identical, we have \tilde{X}^{\prime}\geqslant\tilde{Y}^{\prime} and adding \tilde{U} we get \tilde{X}^{\prime}+\tilde{U}\geqslant\tilde{Y}^{\prime}+\tilde{U} almost surely. As, \tilde{X}^{\prime}+\tilde{U} and \tilde{Y}^{\prime}+\tilde{U} have convex supports in \mathbb{R} and \mathring{\rho} coincides with \rho on L^{\infty}_{c}(\mathbb{R}) , by monotonicity of \rho on L^{\infty}_{c}(\mathbb{R}) , we have \mathring{\rho}(\tilde{X}^{\prime}+\tilde{U})=\rho(\tilde{X}^{\prime}+\tilde{U})\geqslant\rho(\tilde{Y}^{\prime}+\tilde{U})=\mathring{\rho}(\tilde{Y}^{\prime}+\tilde{U})\;. Now, subtracting by \rho(\tilde{U}) on both side and applying Equation 27 , we get \mathring{\rho}(\tilde{X})\geqslant\mathring{\rho}(\tilde{Y}) . Therefore, \mathring{\rho} is monotone on L^{\infty}(\mathbb{R}) . ∎ By Lemma H.6 , we know that a version of Theorem H.4 holds for risk measures on L^{\infty}_{c}(\mathbb{R}) , that is, if \rho is a risk measure defined on L^{\infty}_{c}(\mathbb{R}) that is monotone, additive independent, coincides with the identity on constant random variable, and law-invariant, then there exists a unique Borel probability measure \mu on \overline{\mathbb{R}} such that \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),\quad\rho(\tilde{X})=\int_{\overline{\mathbb{R}}}{\sf ERM}_{a}(\tilde{X})d\mu(a)\;. We are now ready to prove Theorem 4.4 . Proof of Theorem 4.4 . Let \rho be a risk measure that is law-invariant, non-constant and monotone on L^{\infty}_{c}(\mathbb{R}) and that satisfies 1 or 2 in either the case of static kernels or resampled kernels. By the conclusion of Proposition 4.3 , \rho coincides with the identity on constants, is positive homogeneous and additive independent on L^{\infty}_{c}(\mathbb{R}) . Also, by monotonicity of \rho on L^{\infty}_{c}(\mathbb{R}) , for any {\sf M}\in\mathcal{M} and independent \tilde{X},\tilde{Y}\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R}_{+}) , we have \rho(\tilde{X}\tilde{Y})=\rho(\tilde{X})\rho(\tilde{Y}) . Then, using Lemma H.6 , there exists \mathring{\rho} a risk measure that is law-invariant on L^{\infty}(\mathbb{R}) , coincides with \rho on L^{\infty}_{c}(\mathbb{R}) and is positive homogeneous, additive independent and monotone on L^{\infty}(\mathbb{R}) . In particular, \mathring{\rho} also coincides with the identity on constants. Let now {\sf M}_{0}\in\mathcal{M} an ambiguity-averse MDP such that (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is non-atomic (for example the one of Example E.1 ). Because \mathring{\rho} is monotone, additive independent and law invariant on L^{\infty}(\mathbb{R}) and it coincides with the identity on constants, the specific risk measure \displaystyle\mathring{\rho}_{{\sf M}_{0}}\colon L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) \displaystyle\to\mathbb{R} \displaystyle\tilde{X} \displaystyle\mapsto\mathring{\rho}(\tilde{X}) is a risk-measure on a non-atomic probability space that is law-invariant, monotone, additive independent, and that coincides with the identity on constants. Therefore, by Theorem 1 in 41 , there exists a unique Borel probability measure \mu on \overline{\mathbb{R}} such that \forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})=\int_{\overline{\mathbb{R}}}{\sf ERM}_{a}(\tilde{X})d\mu(a)\;, where {\sf ERM}_{a}(\tilde{X})=\frac{1}{a}\log\mathbb{E}(\exp(a\tilde{X})) if a\in\mathbb{R}^{\star} , {\sf ERM}_{0}(\tilde{X})=\mathbb{E}(\tilde{X}) , {\sf ERM}_{+\infty}(\tilde{X})=\operatorname{ess\,sup}(\tilde{X}) and {\sf ERM}_{-\infty}(\tilde{X})=\operatorname{ess\,inf}(\tilde{X}) . Then, we fix \lambda>0 and define the dilatation map T_{\lambda}:\overline{\mathbb{R}}\to\overline{\mathbb{R}} such that T_{\lambda}(a)=\lambda a if a\in\mathbb{R} and T_{\lambda}(+\infty)=+\infty , T_{\lambda}(-\infty)=-\infty . Noting that for any a\in\overline{\mathbb{R}} and \tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) , we have {\sf ERM}_{a}(\lambda\tilde{X})=\lambda{\sf ERM}_{T_{\lambda}(a)}(\tilde{X}) , we obtain by positive homogeneity of \mathring{\rho} , \displaystyle\forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X}) \displaystyle=\frac{1}{\lambda}\mathring{\rho}_{{\sf M}_{0}}(\lambda\tilde{X})=\frac{1}{\lambda}\int_{\overline{\mathbb{R}}}{\sf ERM}_{a}(\lambda\tilde{X})d\mu(a) \displaystyle=\int_{\overline{\mathbb{R}}}{\sf ERM}_{T_{\lambda}(a)}(\tilde{X})d\mu(a) \displaystyle=\int_{\overline{\mathbb{R}}}{\sf ERM}_{a}(\tilde{X})d(T_{\lambda}\#\mu)(a)\;, where T_{\lambda}\#\mu is the pushforward measure of \mu by T_{\lambda} . By uniqueness of the representation of \mathring{\rho}_{{\sf M}_{0}} , we have \mu=T_{\lambda}\#\mu for any \lambda>0 . We now assume for contradiction that \mu((0,+\infty))>0 . Then, there exists 00 . Taking \lambda>a_{2}/a_{1} , we have that the intervals (\lambda^{n}a_{1},\lambda^{n}a_{2}) for n\in\mathbb{N} are pairwise disjoint and each has the same positive measure under \mu , contradicting the finiteness of \mu . The same argument leads to \mu((-\infty,0))=0 , finally showing that \mu is supported on \{0,-\infty,+\infty\} . Consequently, noting a=\mu(\{0\}) , b=\mu(\{-\infty\}) and c=\mu(\{+\infty\}) , we have a+b+c=1 and \forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})=a\cdot\mathbb{E}(\tilde{X})+b\cdot\operatorname{ess\,inf}(\tilde{X})+c\cdot\operatorname{ess\,sup}(\tilde{X})\;. We now show that a=1,b=1 or c=1 using that for any independent random variables \tilde{X}^{\prime},\tilde{Y}^{\prime}\in L^{\infty}_{c}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}_{+}) , \mathring{\rho}_{{\sf M}_{0}}(\tilde{Z}\tilde{X})=\rho(\tilde{Z}\tilde{X})=\rho(\tilde{Z})\rho(\tilde{X})=\mathring{\rho}_{{\sf M}_{0}}(\tilde{Z})\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})\;. By non-atomicity, for any 0\leqslant x_{1}\leqslant x_{2} and 0\leqslant z_{1}\leqslant z_{2} , there exists independent random variables \tilde{X}^{\prime},\tilde{Z}^{\prime}\in L^{\infty}_{c}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}) such that \tilde{X}\sim\text{Unif}([x_{1},x_{2}]) and \tilde{Z}\sim\text{Unif}([z_{1},z_{2}]) . In particular, because L^{\infty}_{c}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}_{+}) , we have \mathring{\rho}(\tilde{X}\tilde{Z})=\mathring{\rho}(\tilde{X})\mathring{\rho}(\tilde{Z}) . First, noting u=a/2+b and v=a/2+c , we have \displaystyle\mathring{\rho}_{{\sf M}_{0}}(\tilde{X}) \displaystyle=a\frac{x_{1}+x_{2}}{2}+bx_{1}+cx_{2}=ux_{1}+vx_{2}\;, \displaystyle\mathring{\rho}_{{\sf M}_{0}}(\tilde{Z}) \displaystyle=a\frac{z_{1}+z_{2}}{2}+bz_{1}+cz_{2}=uz_{1}+vz_{2}\;, \displaystyle\mathring{\rho}_{{\sf M}_{0}}(\tilde{X}\tilde{Z}) \displaystyle=a\frac{x_{1}z_{1}+x_{1}z_{2}+x_{2}z_{1}+x_{2}z_{2}}{4}+bx_{1}z_{1}+cx_{2}z_{2}\;. so the equality \mathring{\rho}_{{\sf M}_{0}}(\tilde{X}\tilde{Z})=\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})\mathring{\rho}_{{\sf M}_{0}}(\tilde{Z}) gives \displaystyle(ux_{1}+vx_{2})(uz_{1}+vz_{2}) \displaystyle=a\frac{x_{1}z_{1}+x_{1}z_{2}+x_{2}z_{1}+x_{2}z_{2}}{4}+bx_{1}z_{1}+cx_{2}z_{2} \displaystyle u^{2}x_{1}z_{1}+uv(x_{1}z_{2}+x_{2}z_{1})+v^{2}x_{2}z_{2} \displaystyle=\left(u-\frac{a}{4}\right)x_{1}z_{1}+\frac{a}{4}(x_{1}z_{2}+x_{2}z_{1})+\left(v-\frac{a}{4}\right)x_{2}z_{2}\;. Therefore, because this equality holds for any 0\leqslant x_{1}\leqslant x_{2} and 0\leqslant z_{1}\leqslant z_{2} , we have the system of equations: \left\{\begin{aligned} &u^{2}=u-\frac{a}{4}\\ &uv=\frac{a}{4}\\ &v^{2}=v-\frac{a}{4}\end{aligned}\;.\right. From the first and third equations, we have that u and v are roots of the equation X^{2}-X+a/4=0 . If they are equal, then u=v=1/2 since u+v=a+b+c=1 . Then, the second equation gives a=1 . If u\neq v , we immediately have a<1 as a=1 implies u=v . We now prove by contradiction that a=0 . In fact, if a\neq 0 , we have 1-a\in(0,1) and noting w=\min(u,v) , we have that w=\frac{1-\sqrt{1-a}}{2}<\frac{a}{2} which contradicts the non-negativity of b or c . Finally a=0 so u=b and v=c are the two roots of X^{2}-X=0 and \{b,c\}=\{0,1\} . Because a=1,b=1 or c=1 , we now have \left\{\begin{aligned} \forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),&\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})=\mathbb{E}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),&\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})=\operatorname{ess\,inf}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R}),&\quad\mathring{\rho}_{{\sf M}_{0}}(\tilde{X})=\operatorname{ess\,sup}(\tilde{X})\end{aligned},\right. By law-invariance of \mathring{\rho} on L^{\infty}(\mathbb{R}) and non-atomicity of (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) , it directly implies: \left\{\begin{aligned} \forall\tilde{X}\in L^{\infty}(\mathbb{R}),&\quad\mathring{\rho}(\tilde{X})=\mathbb{E}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}(\mathbb{R}),&\quad\mathring{\rho}(\tilde{X})=\operatorname{ess\,inf}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}(\mathbb{R}),&\quad\mathring{\rho}(\tilde{X})=\operatorname{ess\,sup}(\tilde{X})\end{aligned},\right. so the desired result holds because \rho and \mathring{\rho} coincide on L^{\infty}_{c}(\mathbb{R}) : \left\{\begin{aligned} \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),&\quad\rho(\tilde{X})=\mathbb{E}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),&\quad\rho(\tilde{X})=\operatorname{ess\,inf}(\tilde{X})\\ &\text{or }\\ \forall\tilde{X}\in L^{\infty}_{c}(\mathbb{R}),&\quad\rho(\tilde{X})=\operatorname{ess\,sup}(\tilde{X})\end{aligned}\;.\right. ∎ H.3 W^{1} -continuity and Proof of Theorem 4.5 In this section we derive results for the case of W^{1} -continuous functionals. We first define W^{1} -continuity. Definition H.7 . The Wasserstein-1 metric W^{1}(\nu_{1},\nu_{2}) between two laws \nu_{1},\nu_{2} is defined as W_{1}(\nu_{1},\nu_{2})=\int_{0}^{1}|F_{\nu_{1}}^{-1}(u)-F_{\nu_{2}}^{-1}(u)|du\;. A law-invariant risk measure \rho(\tilde{X}) can be written \rho(\tilde{X})=\varrho(\mathcal{L}(X)) for some \varrho that maps laws to scalars, see Proposition Proposition B.3 . With this notation, the risk measure \rho is W^{1} -continuous if for any law \nu with compact supports and any sequence of laws with compact supports (\nu_{n})_{n\in\mathbb{N}} we have \lim_{n\rightarrow+\infty}W_{1}(\nu_{n},\nu)=0\Rightarrow\lim_{n\rightarrow+\infty}\varrho(\nu_{n})=\varrho(\nu)\;. Intuitively, W^{1} -continuity corresponds to a continuity in the quantiles of the law. Table 2 summarizes the W^{1} -continuity properties of common risk measures. Theorem 4.5 provides a complete characterization of W^{1} -continuous, law-invariant risk measures that satisfy 1 or 2 . We first prove that if \rho is a W^{1} -continuous law-invariant risk measure that satisfies 1 or 2 in either the case of static kernels or resampled kernels, then \rho=\mathbb{E} . Proof of Theorem 4.5 . Let \rho a risk measure that is non-constant, W^{1} -continuous and law-invariant on L^{\infty}_{c}(\mathbb{R}) and that satisfies 1 or 2 in either the case of static kernels or resampled kernels. By the conclusion of Proposition 4.3 , \rho coincides with the identity on constants and is positive homogeneous and additive independent on L^{\infty}_{c}(\mathbb{R}) . Let {\sf M}_{0}\in\mathcal{M} an ambiguity-averse MDP such that (\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}}) is non-atomic (for example the one of Example E.1 ). Now, for any \tilde{X}\in L^{\infty}_{c}(\mathbb{R}) , consider a sequence of i.i.d. random variables (\tilde{X}_{i})_{i\in\mathbb{N}}\in L^{\infty}(\Omega_{{\sf M}_{0}},\mathcal{F}_{{\sf M}_{0}},\mathbb{P}_{{\sf M}_{0}};\mathbb{R})^{\mathbb{N}} such that all the \tilde{X}_{i} have the same law as \tilde{X} . By additive independence and positive homogeneity on L^{\infty}_{c}(\mathbb{R}) , we have \forall n\in\mathbb{N},\quad\rho\left(\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}\right)=\frac{1}{n}\sum_{i\leqslant n}\rho(\tilde{X}_{i})=\rho(\tilde{X})\;. Denoting by \nu_{n} the law of the sample mean \frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i} and by \nu=\delta_{\mathbb{E}(\tilde{X})} the Dirac measure concentrated in \mathbb{E}(\tilde{X}) , we now show that W_{1}(\nu_{n},\nu)\to_{n}0 . Indeed, \displaystyle W_{1}(\nu_{n},\nu) \displaystyle=\int_{0}^{1}\left|F_{\nu_{n}}^{-1}(u)-F_{\nu}^{-1}(u)\right|\,du \displaystyle=\int_{0}^{1}\left|F_{\nu_{n}}^{-1}(u)-\mathbb{E}(\tilde{X})\right|\,du \displaystyle=\mathbb{E}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}-\mathbb{E}(\tilde{X})\right|\right)\;, where we have used in first equality that \nu is a Dirac measure and in the second equality that if \tilde{U} is a random variable uniformly distributed on (0,1) , then F_{\nu_{n}}^{-1}(\tilde{U}) has the same distribution as \frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i} . Then, by boundedness of \frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i} , the Dominated Convergence Theorem gives \displaystyle\lim_{n\to\infty}\mathbb{E}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}-\mathbb{E}(\tilde{X})\right|\right) \displaystyle=\mathbb{E}\left(\lim_{n\to\infty}\left|\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}-\mathbb{E}(\tilde{X})\right|\right)=\mathbb{E}[0]=0\;, where the second equality comes from the fact that \left|\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}-\mathbb{E}(\tilde{X})\right|\to 0 almost surely by the Strong Law of Large Numbers. Therefore, using W^{1} -continuity, \displaystyle\rho(\tilde{X}) \displaystyle=\lim_{n\rightarrow+\infty}\rho\left(\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}\right) \displaystyle=\rho\left(\lim_{n\rightarrow+\infty}\frac{1}{n}\sum_{i=1}^{n}\tilde{X}_{i}\right) \displaystyle=\rho(\mathbb{E}(\tilde{X}))=\mathbb{E}(\tilde{X}) where the last equality uses that \rho(c)=c for c\in\mathbb{R} , as shown in Proposition 4.3 . ∎ We can now conclude by noting that it is known that \rho=\mathbb{E} satisfies both 1 and 2 for resampled kernels (this corresponds to distributionally robust MDPs with a set of distribution equal to the singleton \{\nu\} [ 60 ] ) but not for static kernels (as shown in Example 3.4 - 3.8 ). Appendix I Extensions of 1 and 2 to the case of two risk measures Proposition I.1 . Let \rho_{1},\rho_{2} be two risk measures for ambiguity-averse MDPs that are non-constant and law-invariant on L^{\infty}_{c}(\mathbb{R}) and such that one of the two conditions is satisfied in either the case of static kernels or resampled kernels: 1. V^{\pi,\nu,\rho_{1}} is a fixed point of T^{\pi,\nu,\rho_{2}} for any instance {\sf M}_{\nu}\in\mathcal{M}_{c} and stationary policy \pi\in\Pi_{\sf S} , i.e., V^{\pi,\nu,\rho_{1}}=T^{\pi,\nu,\rho_{2}}V^{\pi,\nu,\rho_{1}},\quad\forall{\sf M}_{\nu}\in\mathcal{M}_{c},\forall\pi\in\Pi_{\sf S}\;. 2. V^{\nu,\rho_{1}} is a fixed point of T^{\nu,\rho_{2}} for any instance {\sf M}_{\nu}\in\mathcal{M}_{c} , i.e., V^{\nu,\rho_{1}}=T^{\nu,\rho_{2}}V^{\nu,\rho_{1}},\quad\forall{\sf M}_{\nu}\in\mathcal{M}_{c}\;. Then \forall X\in L^{\infty}_{c}(\mathbb{R}),\rho_{1}(X)=\rho_{2}(X) . Proof. We first show the result for static kernels. We heavily use the intermediary results of the proof of Theorem 4.4 here (see Appendix H ). Keeping the same notations and random variables as in Lemma H.1 , the MDP of Figure 3 and law-invariance lead to the following system for any \gamma\in(0,1),{\sf M}\in\mathcal{M} , independent random variables (\tilde{X},\tilde{Y},\tilde{Z})\in L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};\mathbb{R})^{2}\times L^{\infty}_{c}(\Omega_{{\sf M}},\mathcal{F}_{{\sf M}},\mathbb{P}_{{\sf M}};[0,1]) and (a,c)\in\mathbb{R}\times\mathbb{R}^{\star} such that \frac{\tilde{X}-a}{c}\in[0,1] almost surely, \displaystyle\rho_{1}\left(\gamma\left(\tilde{Z}\tilde{X}+(1-\tilde{Z})\tilde{Y}\right)\right)=\rho_{2}\left(\gamma\left(\tilde{Z}\rho_{1}(\tilde{X})+(1-\tilde{Z})\rho_{1}(\tilde{Y})\right)\right)\;, (28) \displaystyle\rho_{1}\left(\tilde{X}\right)=\rho_{2}\left(a+\gamma\left(\frac{\tilde{X}-a}{c}\rho_{1}\left(\gamma^{-1}c\right)+(1-\frac{\tilde{X}-a}{c})\rho_{1}(0)\right)\right)\;, (29) \displaystyle\rho_{1}\left(\gamma^{-1}c\right)=\rho_{2}\left(\gamma^{-1}c+\gamma\rho_{1}(0)\right)\;. (30) As in the beginning of the proof of Proposition 4.3 , \rho_{1} being non constant on L^{\infty}_{c}(\mathbb{R}) imposes \rho_{2} to be non constant on \mathbb{R} through ( 28 ). Consequently, ( 30 ) imposes \rho_{1}(0)=0 and that \forall x\in\mathbb{R},\rho_{1}(x)=\rho_{2}(x) . Then, by Lemma H.2 , \forall x\in\mathbb{R},\rho_{1}(x)=\rho_{2}(x)=x and Equation ( 29 ) gives the desired result. To prove the results for the case of resampled kernels, we can proceed similarly and use the same MDP instance as in Figure 3 and use law-invariance. ∎