Distributionally Robust Markov Decision Processes and their Connection to Risk Measures

Nicole Bäuerle^∗ Department of Mathematics, Karlsruhe Institute of Technology (KIT), D-76128 Karlsruhe, Germany [email protected] and Alexander Glauner^∗ Department of Mathematics, Karlsruhe Institute of Technology (KIT), D-76128 Karlsruhe, Germany [email protected]

Abstract.

We consider robust Markov Decision Processes with Borel state and action spaces, unbounded cost and finite time horizon. Our formulation leads to a Stackelberg game against nature. Under integrability, continuity and compactness assumptions we derive a robust cost iteration for a fixed policy of the decision maker and a value iteration for the robust optimization problem. Moreover, we show the existence of deterministic optimal policies for both players. This is in contrast to classical zero-sum games. In case the state space is the real line we show under some convexity assumptions that the interchange of supremum and infimum is possible with the help of Sion’s minimax Theorem. Further, we consider the problem with special ambiguity sets. In particular we are able to derive some cases where the robust optimization problem coincides with the minimization of a coherent risk measure. In the final section we discuss two applications: A robust LQ problem and a robust problem for managing regenerative energy.

Key words:: Robust Markov Decision Process; Dynamic Games; Minimax Theorem; Risk Measures
AMS subject classifications:: 90C40, 90C17, 91G70

1. Introduction

Markov Decision Processes (MDPs) are a well-established tool to model and solve sequential decision making under stochastic perturbations. In the standard theory it is assumed that all parameters and distributions are known or can be estimated with a certain precision. However, using the so-derived ’optimal’ policies in a system where the true parameters or distributions deviate, may lead to a significant degeneration of the performance. In order to cope with this problem there are different approaches in the literature.

The first approach which is typically used when parameters are unknown is the so-called Bayesian approach. In this setting a prior distribution for the model parameters is assumed and additional information which is revealed while the process evolves, is used to update the beliefs. Hence this approach allows that parameters can be learned. It is very popular in engineering applications. Introductions can e.g. be found in [hernandez2012adaptive] and [BaeuerleRieder2011]. In this paper we are not going to pursue this stream of literature.

A second approach is the so-called robust approach. Here it is assumed that instead of having one particular transition law, we are faced with a whole family of laws which are possible for the transition. In the literature this is referred to as model ambiguity. One way of dealing with this ambiguity is the worst case approach, where the controller selects a policy which is optimal with respect to the most adverse transition law in each scenario. This setting can also be interpreted as a dynamic game with nature as the controller’s opponent. The worst case approach is empirically justified by the so-called Ellsberg Paradox. The experiment suggested by [Ellsberg1961] has shown that agents tend to be ambiguity averse. In the sequel, axiomatic approaches to model risk and ambiguity attitude have appeared, see e.g. [gilboa1989maxmin, maccheroni2006ambiguity]. [EpsteinSchneider2003] investigated the question whether ambiguity aversion can be incorporated in an axiomatic model of intertemporal utility. The representation of the preferences turned out to be some worst case expected utility, i.e. the minimal expected utility over an appropriate set of probability measures. This set of probability measures needs to satisfy some rectangularity condition for the utility to have a recursive structure and therefore being time consistent. The rectangularity property has been taken up by [Iyengar2005] as a key assumption for being able to derive a Bellman equation for a robust MDP with countable state and action spaces. Contemporaneously, [NilimGhaoui2005] reached similar findings, however limited to finite state and action spaces.

[wiesemann2013robust] have considered robust MDP beyond the rectangularity condition. Based on observed histories, they derive a confidence region that contains the unknown parameters with a prespecified probability and determine a policy that attains the highest worst-case performance over this confidence region. A similar approach has been taken in [xu2010distributionally] where nested uncertainty sets for transition laws are given which correspond to confidence sets. The optimization is then based on the expected performance of policies under the (respective) most adversarial distribution. This approach lies between the Bayesian and the robust approach since the decision maker uses prior information without a Bayesian interpretation. All these analyses are restricted to finite state and action spaces. A similar but different approach has been considered in [bauerle2019markov] where parameter ambiguity is combined with Bayesian learning methods. Here the authors deal with arbitrary Borel state and action spaces.

In our paper we will generalize the results of [Iyengar2005] to a model with Borel spaces and unbounded cost function. We consider finite horizon expected cost problems with a given transition law under ambiguity concerning the distribution of the disturbance variables. The problem is to minimize the worst expected cost. This leads to a Stackelberg game against nature. In order to deal with the arising measurability issues which impose a major technical difficulty compared to the countable space situation, we borrow from the dynamic game setup in [Gonzales2002] and [JaskiewiczNowak2011]. The major difference of our contribution compared to these two works is the design of the distributional ambiguity. We replace the topology of weak convergence on the ambiguity set by the weak* topology $\sigma(L^{q},L^{p})$ in order to obtain connections to recursive risk measures in Section 6. Moreover, we rigorously derive a Bellman equation. Note that [jaskiewicz2014robust] treats another robust MDP setup with Borel state and action spaces, however deals with the average control problem. Further, our model allows for rather general ambiguity sets for the disturbance distribution. Under additional technical assumptions our model also comprises the setting of a decreasing confidence regions for distributions. Moreover, we discuss in detail sufficient conditions for the interchange of supremum and infimum. We provide a counterexample which shows that this interchange is not always possible, in contrast to [NilimGhaoui2005], [wiesemann2013robust]. This counterexample also highlights the difference to classical two-person zero-sum games. Further, we are able to derive a connection to the optimization of risk measures in MDP frameworks. In case the ambiguity sets are chosen in a specific way the robust optimization problem coincides with the optimization of a risk measure applied to the total cost.

The outline of the paper is as follows: In the next section we introduce our basic model which is a game against nature concerning expected cost with a finite time horizon. Section 3 contains the first main results. Under integrability, continuity and compactness assumptions we derive a robust cost iteration for a fixed policy of the decision maker and a value iteration for the robust optimization problem. Moreover, we show the existence of optimal deterministic policies for both players. This is in contrast to classical zero-sum games where we usually obtain optimal randomized policies. In Section 4 we consider the real line as state space which allows for slightly different model assumptions. Then in Section 5 we discuss (with the real line as state space) when supremum and infimum can be interchanged in the solution of the problem. Under some convexity assumptions this can be achieved with the help of Sion’s minimax Theorem [Sion1958]. Being able to interchange supremum and infimum sometimes simplifies the solution of the problem. In Section 6 we consider the problem with special ambiguity sets. In particular we are able to derive some cases which can be solved straightforward and situations where the robust optimization problem coincides with the minimization of a coherent risk measure. In the final section we discuss two applications: A robust LQ problem and a robust problem for managing regenerative energy.

2. The Markov Decision Model

We consider the following standard Markov Decision Process with general Borel state and action spaces and restrict ourselves to a model with finite planning horizon $N\in\mathbb{N}$ . Results for an infinite planning horizon can be found in [glauner20]. The state space $E$ is a Borel space with Borel $\sigma$ -algebra $\={(}E)$ and the action space $A$ is a Borel space with Borel $\sigma$ -Algebra $\={(}A)$ . The possible state-action combinations at time $n$ form a measurable subset $D_{n}$ of $E\times A$ such that $D_{n}$ contains the graph of a measurable mapping $E\to A$ . The $x$ -section of $D_{n}$ ,

D_{n}(x)=\{a\in A:(x,a)\in D_{n}\},

is the set of admissible actions in state $x\in E$ at time $n$ . The sets $D_{n}(x)$ are non-empty by assumption. We assume that the dynamics of the MDP are given by measurable transition functions $T_{n}:D_{n}\times\mathcal{Z}\to E$ and depend on disturbances $Z_{1},\dots,Z_{N}$ which are independent random elements on a common probability space $(\Omega,\mathcal{A},\mathbb{P})$ with values in a measurable space $(\mathcal{Z},\mathfrak{Z})$ . When the current state is $x_{n}$ the controller chooses action $a_{n}\in D_{n}(x_{n})$ and $z_{n+1}$ is the realization of $Z_{n+1}$ , then the next state is given by

x_{n+1}=T_{n}(x_{n},a_{n},z_{n+1}).

The one-stage cost function $c_{n}:D_{n}\times E\to\mathbb{R}$ gives the cost $c_{n}(x,a,x^{\prime})$ for choosing action $a$ if the system is in state $x$ at time $n$ and the next state is $x^{\prime}$ . The terminal cost function $c_{N}:E\to\mathbb{R}$ gives the cost $c_{N}(x)$ if the system terminates in state $x$ .

The model data is supposed to have the following continuity and compactness properties.

Assumption 2.1.

(i)

$D_{n}(x)$ are compact and $E\ni x\mapsto D_{n}(x)$ is upper semicontinuous for $n=0,\dots,N-1$ , i.e. if $x_{k}\to x$ and $a_{k}\in D_{n}(x_{k})$ , $k\in\mathbb{N}$ , then $(a_{k})$ has an accumulation point in $D_{n}(x)$ .
(ii)

$T_{n}(x,a,z)$ is continuous in $(x,a)$ for $z\in\mathcal{Z}$ and $n=0,\dots,N-1$ .
(iii)

$c_{n},n=0,\dots,N-1$ , as well as the terminal cost function $c_{N}$ are lower semicontinuous.

For $n\in\mathbb{N}_{0}$ we denote by $\mathcal{H}_{n}$ the set of feasible histories of the decision process up to time $n$

\displaystyle h_{n}=\begin{cases}x_{0},&\text{if }n=0,\\ (x_{0},a_{0},x_{1},\dots,x_{n}),&\text{if }n\geq 1,\end{cases}

where $a_{k}\in D_{k}(x_{k})$ for $k\in\mathbb{N}_{0}$ . In order for the controller’s decisions to be implementable, they must be based on the information available at the time of decision making, i.e. be functions of the history of the surplus process.

Definition 2.2.

(i)

A randomized policy is a sequence $\pi=(\pi_{0},\pi_{1},\dots,\pi_{N-1})$ of stochastic kernels $\pi_{n}$ from $\mathcal{H}_{n}$ to the action space $A$ satisfying the constraint

$\pi_{n}(D_{n}(x_{n})|h_{n})=1,\qquad h_{n}\in\mathcal{H}_{n}.$
(ii)

A measurable mapping $d_{n}:\mathcal{H}_{n}\to A$ with $d_{n}(h_{n})\in D_{n}(x_{n})$ for every $h_{n}\in\mathcal{H}_{n}$ is called (deterministic) decision rule at time $n$ . $\pi=(d_{0},d_{1},\dots,d_{N-1})$ is called (deterministic) policy.
(iii)

A decision rule at time $n$ is called Markov if it depends on the current state only, i.e. $d_{n}(h_{n})=d_{n}(x_{n})$ for all $h_{n}\in\mathcal{H}_{n}$ . If all decision rules are Markov, the deterministic ( $N$ -stage) policy is called Markov.

For convenience, deterministic policies may simply be referred to as policy. With $\Pi^{R}\supseteq\Pi\supseteq\Pi^{M}$ we denote the sets of all randomized policies, deterministic policies and Markov policies. The first inclusion is by identifying deterministic decision rules $d_{n}$ with the corresponding Dirac kernels

\pi_{n}(\cdot|h_{n}):=\delta_{d_{n}(h_{n})}(\cdot),\qquad h_{n}\in\mathcal{H}_{n}.

A feasible policy always exists since $D_{n}$ contains the graph of a measurable mapping.

Due to the independence of the disturbances we may without loss of generality assume that the probability space has a product structure

(\Omega,\mathcal{A},\mathbb{P})=\bigotimes_{n=1}^{\mathbb{N}}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}).

We take $(\Omega,\mathcal{A},\mathbb{P})$ as the canonical construction, i.e.

(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})=\left(\mathcal{Z},\mathfrak{Z},\mathbb{P}^{Z_{n}}\right)\qquad\text{and}\qquad Z_{n}(\bar{\omega})=\omega_{n},\quad\bar{\omega}=(\omega_{1},\dots,\omega_{N})\in\Omega

for all $n=1,\dots,N$ . We denote by $(X_{n}),(A_{n})$ the random state and action processes and define $H_{n}:=(X_{0},A_{0},\ldots,X_{n})$ . In the sequel, we will require $\mathbb{P}_{n}$ to be separable. Additionally, we will assume for some results that $\left(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}\right)$ is atomless in order to support a generalized distributional transform.

Let $n\in\{0,\dots,N-1\}$ be a stage of the decision process. Due to the product structure of $(\Omega,\mathcal{A},\mathbb{P})$ the transition kernel is given by

\displaystyle Q_{n}(B|x,a)=\int 1_{B}\big{(}T_{n}(x,a,z_{n+1})\big{)}\mathbb{P}_{n+1}(\operatorname{d}z_{n+1}),\quad B\in\={(}E),\ (x,a)\in D_{n}.

(2.1)

We assume now that there is some uncertainty about $\mathbb{P}_{n}$ , e.g. because it cannot be estimated properly. Moreover, the decision maker is very risk averse and tries to minimize the expected cost on a worst case basis. Thus, we denote by $\mathcal{M}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ the set of probability measures on $(\Omega_{n},\mathcal{A}_{n})$ which are absolutely continuous with respect to $\mathbb{P}_{n}$ and define for $q\in(1,\infty]$

\mathcal{M}^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})=\left\{\mathbb{Q}\in\mathcal{M}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}):\frac{\operatorname{d}\mathbb{Q}}{\operatorname{d}\mathbb{P}_{n}}\in L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})\right\}.

Henceforth, we fix a non-empty subset $\mathcal{Q}_{n}\subseteq\mathcal{M}^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ which is referred to as ambiguity set at stage $n$ . This can be seen as the set of probability measures which may reflect the law of motion. Due to absolute continuity, we can identify $\mathcal{Q}_{n}$ with the set of corresponding densities w.r.t. $\mathbb{P}_{n}$

\mathcal{Q}_{n}^{d}=\left\{\frac{\operatorname{d}\mathbb{Q}}{\operatorname{d}\mathbb{P}_{n}}\in L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}):\mathbb{Q}\in\mathcal{Q}_{n}\right\}.

(2.2)

Accordingly, we view $\mathcal{Q}_{n}$ as a subset of $L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ and endow it with the trace topolgy of the weak* topolgy $\sigma(L^{q},L^{p})$ on $L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ where $\frac{1}{p}+\frac{1}{q}=1$ . The weak* topology in turn induces a Borel $\sigma$ -algebra on $\mathcal{Q}_{n}$ making it a measurable space. We obtain the following result (for a proof see the Appendix).

Lemma 2.3.

Let the ambiguity set be norm-bounded and the probability measure $\mathbb{P}_{n}$ on $(\Omega_{n},\mathcal{A}_{n})$ be separable. Then $\mathcal{Q}_{n}$ endowed with the weak* topology $\sigma(L^{q},L^{p})$ is a separable metrizable space. If $\mathcal{Q}_{n}$ is additionally weak* closed, it is even a compact Borel space.

In our cost model we allow for any norm-bounded ambiguity set $\mathcal{Q}_{n}\subseteq\mathcal{M}^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ . For applications, a meaningful way of choosing $\mathcal{Q}_{n}$ (within a norm bound) is to take all probability measures in $\mathcal{M}^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ which are close to $\mathbb{P}_{n}$ in a certain metric like e.g. the Wasserstein metric (see e.g. [yang2017convex]). In our setting, that requires absolute continuity, the Kullback–-Leibler divergence could be a natural choice.

The controller only knows that the transition kernel (2.1) at each stage is defined by some $\mathbb{Q}\in\mathcal{Q}_{n+1}$ instead of $\mathbb{P}_{n+1}$ but not which one exactly. We assume here that the controller faces a dynamic game against nature. This means that nature reacts to the controller’s action $a_{n}$ in scenario $h_{n}\in\mathcal{H}_{n}$ with a decision rule $\gamma_{n}:\mathcal{H}_{n}\times A\to\mathcal{Q}_{n+1}$ where $a_{n}\in D_{n}(x_{n})$ . A policy of nature is a sequence of such decision rules $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ . Let $\Gamma$ be the set of all policies of nature. Since nature is an unobserved theoretical opponent of the controller, her actions are not considered to be part of the history of the Markov Decision Process. A Markov decision rule of nature at time $n$ is a measurable mapping $\gamma_{n}:D_{n}\to\mathcal{Q}_{n+1}$ and a Markov policy of nature is a sequence $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ of such decision rules. The set of Markov policies of nature is denoted by $\Gamma^{M}$ . Thus we are faced with a Stackelberg game where the controller is the mover and nature is the follower.

Lemma 2.4.

For $n=0,\dots,N-1$ a decision rule $\gamma_{n}:\mathcal{H}_{n}\times A\to\mathcal{Q}_{n+1}$ induces a stochastic kernel from $\mathcal{H}_{n}\times A$ to $\Omega_{n+1}$ by

\gamma_{n}(B|h_{n},a_{n}):=\gamma_{n}(h_{n},a_{n})(B),\qquad B\in\mathcal{A}_{n+1},\ (h_{n},a_{n})\in\mathcal{H}_{n}\times A.

For a proof of the lemma see the Appendix. In the sequel, it will be clear from the context where we refer to $\gamma_{n}$ as a decision rule or as a stochastic kernel.

The probability measure $\gamma_{n}(\cdot|h_{n},a_{n})$ , which is unknown for the controller, now takes the role of $\mathbb{P}_{n+1}$ in defining the transition kernel of the Markov Decision Process in (2.1). Let

\displaystyle Q_{n}^{\gamma}(B|h_{n},a_{n})=\int 1_{B}\big{(}T(x_{n},a_{n},z_{n+1})\big{)}\gamma_{n}(\operatorname{d}z_{n+1}|h_{n},a_{n}),\;B\in\={(}E),\ h_{n}\in\mathcal{H}_{n},a_{n}\in D_{n}(x_{n}).

(2.3)

As in the case without ambiguity, the Theorem of Ionescu-Tulcea yields that each initial state $x\in E$ and pair of policies of the controller and nature $(\pi,\gamma)\in\Pi^{R}\times\Gamma$ induce a unique law of motion

\displaystyle\mathbb{Q}^{\pi\gamma}_{x}:=\delta_{x}\otimes\pi_{0}\otimes Q_{0}^{\gamma}\otimes\pi_{1}\otimes Q_{1}^{\gamma}\otimes\dots\otimes\pi_{N-1}\otimes Q_{N-1}^{\gamma}

(2.4)

on ${\mathcal{H}}_{N}$ satisfying

	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(X_{0}\in B)$	$\displaystyle=\delta_{x}(B),$
	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(A_{n}\in C\|H_{n}=h_{n})$	$\displaystyle=\pi_{n}(C\|h_{n}),$
	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(X_{n+1}\in B\|(H_{n},A_{n})=(h_{n},a_{n}))$	$\displaystyle=Q_{n}^{\gamma}(B\|h_{n},a_{n})$

for all $B\in\={(}E)$ and $C\in\={(}A)$ . In the usual way, we denote with $\mathbb{E}_{x}^{\pi\gamma}$ the expectation operator with respect to $\mathbb{Q}^{\pi\gamma}_{x}$ and with $\mathbb{E}_{nh_{n}}^{\pi\gamma}$ or $\mathbb{E}_{nx}^{\pi\gamma}$ the respective conditional expectation given $H_{n}=h_{n}$ or $X_{n}=x$ .

The value of a policy pair $(\pi,\gamma)\in\Pi^{R}\times\Gamma$ at time $n=0,\dots,N-1$ is defined as

\displaystyle\begin{aligned} V_{N\pi\gamma}(h_{N})&=c_{N}(x_{N}),&h_{N}\in\mathcal{H}_{N},\\ V_{n\pi\gamma}(h_{n})&=\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[\sum_{k=n}^{N-1}c_{k}(X_{k},A_{k},X_{k+1})+c_{N}(X_{N})\right],&h_{n}\in\mathcal{H}_{n}.\end{aligned}

(2.5)

Since the controller is unaware which probability measure in the ambiguity set determines the transition law in each scenario, he tries to minimize the expected cost under the assumption to be confronted with the most adverse probability measure. The value functions are thus given by

\displaystyle V_{n}(h_{n})=\inf_{\pi\in\Pi^{R}}\sup_{\gamma\in\Gamma}\ V_{n\pi\gamma}(h_{n}),\qquad h_{n}\in\mathcal{H}_{n},

and the optimization objective is

\displaystyle V_{0}(x)=\inf_{\pi\in\Pi^{R}}\sup_{\gamma\in\Gamma}\ V_{0\pi\gamma}(x),\qquad x\in E.

(2.6)

In game-theoretic terminology this is the upper value of a dynamic zero-sum game. If nature were to act first, i.e. if infimum and supremum were interchanged, one would obtain the game’s lower value. If the two values agree and the infima/suprema are attained, the game has a Nash equilibrium, see also Section 5. But note here that players are asymmetric in information in our setting.

Remark 2.5.

[Iyengar2005] does not model nature to make active decisions, but instead defines the set of all possible laws of motion. When each law of motion is of the form (2.4), he calls the set rectangular. Our approach with active decisions of nature based on [Gonzales2002] and [JaskiewiczNowak2011] is needed to construct Markov kernels as in Lemma 2.4 with probability measures from a given ambiguity set. When state and action spaces are countable as in [Iyengar2005] the technical problem of measurability does not arise and one can directly construct an ambiguous law of motion by simply multiplying (conditional) probabilities. The rectangularity property is satisfied in our setting.

Our model feature that there is no ambiguity in the transition functions is justified in many applications. Typically, transition functions describe a technical process or economic calculation which is known ex-ante and does not have to be estimated. The same applies to the cost function.

3. Value Iteration and Optimal Policies

In order to have well-defined value functions we need some integrability conditions.

Assumption 3.1.

(i)

There exist $\alpha,\underaccent{\bar}{\epsilon},\bar{\epsilon}\geq 0$ with $\underaccent{\bar}{\epsilon}+\bar{\epsilon}=1,\alpha\neq 1$ and measurable functions $\underaccent{\bar}{b}:E\to(-\infty,-\underaccent{\bar}{\epsilon}]$ and $\bar{b}:E\to[\bar{\epsilon},\infty)$ such that it holds for all $n=0,\dots,N-1$ , $\mathbb{Q}\in\mathcal{Q}_{n+1}$ and $(x,a)\in D_{n}$

	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[-c_{n}^{-}(x,a,T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\geq\underaccent{\bar}{b}(x),$	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[\underaccent{\bar}{b}(T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\geq\alpha\underaccent{\bar}{b}(x),$
	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[c_{n}^{+}(x,a,T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\leq\bar{b}(x),$	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[\bar{b}(T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\leq\alpha\bar{b}(x).$

Furthermore, it holds $\underaccent{\bar}{b}(x)\leq c_{N}(x)\leq\bar{b}(x)$ for all $x\in E$ .

(ii)

We define $b:E\to[1,\infty),\ b(x):=\bar{b}(x)-\underaccent{\bar}{b}(x)$ . For all $n=0,\dots,N-1$ and $(\bar{x},\bar{a})\in D_{n}$ there exists an $\epsilon>0$ and measurable functions $\Theta_{n,1}^{\bar{x},\bar{a}},\Theta_{n,2}^{\bar{x},\bar{a}}:\mathcal{Z}\to\mathbb{R}_{+}$ such that $\Theta_{n,1}^{\bar{x},\bar{a}}(Z_{n+1}),\Theta_{n,2}^{\bar{x},\bar{a}}(Z_{n+1})\in L^{p}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1})$ and

\displaystyle|c_{n}(x,a,T_{n}(x,a,z))|\leq\Theta_{n,1}^{\bar{x},\bar{a}}(z),\qquad\qquad b(T_{n}(x,a,z))\leq\Theta_{n,2}^{\bar{x},\bar{a}}(z)

for all $z\in\mathcal{Z}$ and $(x,a)\in B_{\epsilon}(\bar{x},\bar{a})\cap D_{n}$ . Here, $B_{\epsilon}(\bar{x},\bar{a})$ is the closed ball around $(\bar{x},\bar{a})$ w.r.t. an arbitrary product metric on $E\times A$ .

(iii)

The ambiguity sets $\mathcal{Q}_{n}$ are norm bounded, i.e. there exists $K\in[1,\infty)$ such that

$\mathbb{E}\left|\frac{\operatorname{d}\mathbb{Q}}{\operatorname{d}\mathbb{P}_{n}}\right|^{q}\leq K$

for all $n=1,\dots,N$ and $\mathbb{Q}\in\mathcal{Q}_{n}$ .

Remark 3.2.

(a)

$\underaccent{\bar}{b},\bar{b}$ are called lower and upper bounding function, respectively, while $b$ is referred to as bounding function. As the absolute value is the sum of positive and negative part, $b$ satisfies for all $n=0,\dots,N-1$ , $\mathbb{Q}\in\mathcal{Q}_{n}$ and $(x,a)\in D_{n}$ :

\mathbb{E}^{\mathbb{Q}}\left[|c_{n}(x,a,T_{n}(x,a,Z_{n+1}))|\right]\leq b(x)\qquad\text{and}\qquad\mathbb{E}^{\mathbb{Q}}\left[|b(T_{n}(x,a,Z_{n+1}))|\right]\leq\alpha b(x)

(b)

Assumptions 3.1 (i) and (ii) are satisfied with $-\underaccent{\bar}{b}=\bar{b}=constant>0$ if the cost functions are bounded.

(c)

If $p=1$ and hence $q=\infty$ , it is technically sufficient if part (ii) of Assumption 3.1 holds under the reference probability measure $\mathbb{P}_{n}$ . Using Hölder’s inequality and part (iii) we get for every $\mathbb{Q}\in\mathcal{Q}_{n+1}$

	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[-c_{n}^{-}(x,a,T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\geq\mathbb{E}\left[-c_{n}^{-}(x,a,T_{n}(x,a,Z_{n+1}))\right]\operatorname{ess\,sup}\frac{\operatorname{d}\mathbb{Q}}{\operatorname{d}\mathbb{P}_{n+1}}\geq K\underaccent{\bar}{b}(x),$
	$\displaystyle\mathbb{E}^{\mathbb{Q}}\left[\underaccent{\bar}{b}(T_{n}(x,a,Z_{n+1}))\right]$	$\displaystyle\geq\mathbb{E}\left[\underaccent{\bar}{b}(T_{n}(x,a,Z_{n+1}))\right]\operatorname{ess\,sup}\frac{\operatorname{d}\mathbb{Q}}{\operatorname{d}\mathbb{P}_{n+1}}\geq\alpha K\underaccent{\bar}{b}(x)$

and analogous results for the upper bounding function. I.e. one simply has to replace $\alpha$ by $K\alpha$ . However, the factor $K\alpha$ may be unnecessarily crude.

The next lemma shows that due to Assumption 3.1 (i) the value (2.5) of a policy pair $(\pi,\gamma)\in\Pi^{R}\times\Gamma$ is well-defined at all stages $n=0,\dots,N$ . One can see that the existence of either a lower or an upper bounding function is sufficient for the policy value to be well-defined. However, for the existence of an optimal policy pair we will need the integral to exist with finite value and therefore require both a lower and an upper bounding function.

Lemma 3.3.

Under Assumption 3.1 it holds for all policy pairs $(\pi,\gamma)\in\Pi^{R}\times\Gamma$ , time points $n=0,\dots,N$ and histories $h_{n}\in\mathcal{H}_{n}$

\frac{1-\alpha^{N+1-n}}{1-\alpha}\underaccent{\bar}{b}(x_{n})\leq V_{n\pi\gamma}(h_{n})\leq\frac{1-\alpha^{N+1-n}}{1-\alpha}\bar{b}(x_{n}).

Proof.

We only prove the first inequality. The second inequality is analogous. We use that

\displaystyle V_{n\pi\gamma}(h_{n})\geq

\displaystyle\sum_{k=n}^{N-1}\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[-c_{k}^{-}(X_{k},A_{k},X_{k+1})\right]+\mathbb{E}_{Nh_{N}}^{\pi\gamma}\left[-c_{N}^{-}(X_{N})\right]

and consider the summands individually. We have $\mathbb{E}_{Nh_{N}}^{\pi\gamma}\left[-c_{N}^{-}(X_{N})\right]\geq\mathbb{E}_{Nh_{N}}^{\pi\gamma}\left[\underaccent{\bar}{b}(X_{N})\right]$ by Assumption 3.1 (i). Since $\gamma_{k}$ is a mapping to $\mathcal{Q}_{k+1}$ it follows from the first inequality of Assumption 3.1 (i) that

	$\displaystyle\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[-c_{k}^{-}(X_{k},A_{k},X_{k+1})\right]=\int\mathbb{E}_{kh_{k}}^{\pi\gamma}\left[-c_{k}^{-}(X_{k},A_{k},X_{k+1})\right]\mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}h_{k}\|H_{n}=h_{n})$
	$\displaystyle=\iiint-c_{k}^{-}\big{(}x_{k},a_{k},T_{k}(x_{k},a_{k},z_{k+1})\big{)}\,\gamma_{k}(\operatorname{d}z_{k+1}\|h_{k},a_{k})\,\pi_{k}(\operatorname{d}a_{k}\|h_{k})\ \mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}h_{k}\|H_{n}=h_{n})$
	$\displaystyle\geq\int\underaccent{\bar}{b}(x_{k})\ \mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}h_{k}\|H_{n}=h_{n})=\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[\underaccent{\bar}{b}(X_{k})\right]$

for $k=n,\dots,N-1$ . Now, the second inequality of Assumption 3.1 (i) yields for $k\geq n+1$

	$\displaystyle\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[\underaccent{\bar}{b}(X_{k})\right]=\int\mathbb{E}_{k-1h_{k-1}}\left[\underaccent{\bar}{b}(X_{k})\right]\mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}h_{k-1}\|H_{n}=h_{n})$
	$\displaystyle=\iiint\!\underaccent{\bar}{b}\big{(}T_{k-1}(x_{k-1},a_{k-1},z_{k})\big{)}\,\gamma_{k-1}(\operatorname{d}\!z_{k}\|h_{k-1},a_{k-1})\,\pi_{k-1}(\operatorname{d}\!a_{k-1}\|h_{k-1})\,\mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}\!h_{k-1}\|H_{n}\!=\!h_{n})$
	$\displaystyle\geq\alpha\int\underaccent{\bar}{b}(x_{k-1})\mathbb{Q}_{x}^{\pi\gamma}(\operatorname{d}h_{k-1}\|H_{n}=h_{n})=\alpha\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[\underaccent{\bar}{b}(X_{k-1})\right].$

Iterating this argument we obtain

\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[-c_{N}^{-}(X_{N})\right]\geq\alpha^{N-n}\underaccent{\bar}{b}(x_{n})\qquad\text{and}\qquad\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[-c_{k}^{-}(X_{k},A_{k},X_{k+1})\right]\geq\alpha^{k-n}\underaccent{\bar}{b}(x_{n}).

Finally, summation over $k$ yields the assertion. ∎

With the bounding function $b$ we define the function space

\mathbb{B}_{b}:=\left\{v:E\to\mathbb{R}\ |\ v\text{ measurable with }\lambda\in\mathbb{R}_{+}\text{ s.t. }|v(x)|\leq\lambda\,b(x)\text{ for all }x\in E\right\}.

Endowing $\mathbb{B}_{b}$ with the weighted supremum norm

\|v\|_{b}:=\sup_{x\in E}\frac{|v(x)|}{b(x)}.

makes $(\mathbb{B}_{b},\|\cdot\|_{b})$ a Banach space, cf. Proposition 7.2.1 in [HernandezLasserre1999].

Having ensured that the value functions are well-defined, we can now proceed to derive the cost iteration. To ease notation we introduce the following operators.

Definition 3.4.

For functions $v:\mathcal{H}_{n+1}\to\mathbb{R}$ s.t. $v(h_{n},a_{n},\cdot)\in\mathbb{B}_{b}$ for all $h_{n}\in\mathcal{H}_{n},a_{n}\in D_{n}(x_{n})$ and $n=0,\ldots,N-1$ let

	$\displaystyle\mathcal{T}_{n\pi_{n}\gamma_{n}}v(h_{n}):=$
	$\displaystyle\iint c_{n}\big{(}x_{n},a_{n},T_{n}(x_{n},a_{n},z_{n+1})\big{)}+v\big{(}h_{n},a_{n},T_{n}(x_{n},a_{n},z_{n+1})\big{)}\,\gamma_{n}(\operatorname{d}z_{n+1}\|h_{n},a_{n})\,\pi_{n}(\operatorname{d}a_{n}\|h_{n})$
	$\displaystyle\mathcal{T}_{n\pi_{n}}v(h_{n}):=$
	$\displaystyle\int\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\int c_{n}\big{(}x_{n},a_{n},T_{n}(x_{n},a_{n},z_{n+1})\big{)}+v\big{(}h_{n},a_{n},T_{n}(x_{n},a_{n},z_{n+1})\big{)}\,\mathbb{Q}(\operatorname{d}z_{n+1})\,\pi_{n}(\operatorname{d}a_{n}\|h_{n})$

Note that the operators are monotone in $v$ .

Proposition 3.5.

Under Assumption 3.1 the value of a policy pair $(\pi,\gamma)\in\Pi^{R}\times\Gamma$ can be calculated recursively for $n=0,\dots,N$ and $h_{n}\in\mathcal{H}_{n}$ as

	$\displaystyle V_{N\pi\gamma}(h_{N})$	$\displaystyle=c_{N}(x_{N}),$
	$\displaystyle V_{n\pi\gamma}(h_{n})$	$\displaystyle=\mathcal{T}_{n\pi_{n}\gamma_{n}}V_{n+1\pi\gamma}(h_{n}).$

Proof.

The proof is by backward induction. At time $N$ there is nothing to show. Now assume the assertion holds for $n+1$ , then the tower property of conditional expectation yields for $n$

	$\displaystyle V_{n\pi\gamma}(h_{n})=\mathbb{E}_{nh_{n}}^{\pi\gamma}\left[c_{n}(X_{n},A_{n},X_{n+1})+\mathbb{E}_{n+1h_{n}A_{n}X_{n+1}}^{\pi\gamma}\left[\sum_{k=n+1}^{N-1}c_{k}(X_{k},A_{k},X_{k+1})+c_{N}(X_{N})\right]\right]$
	$\displaystyle=\iint c_{n}(x_{n},a_{n},x^{\prime})+\mathbb{E}_{n+1h_{n}a_{n}x^{\prime}}^{\pi\gamma}\left[\sum_{k=n+1}^{N-1}c_{k}(X_{k},A_{k},X_{k+1})+c_{N}(X_{N})\right]Q_{n}^{\gamma}(\operatorname{d}x^{\prime}\|h_{n},a_{n})\,\pi_{n}(\operatorname{d}a_{n}\|h_{n})$
	$\displaystyle=\mathcal{T}_{n\pi_{n}\gamma_{n}}V_{n+1\pi\gamma}(h_{n})$

for all $h_{n}\in\mathcal{H}_{n}$ . ∎

Now, we evaluate a policy of the controller under the worst-case scenario regarding nature’s reaction. We define the robust value of a policy $\pi\in\Pi^{R}$ at time $n=0,\dots,N-1$ as

V_{n\pi}(h_{n})=\sup_{\gamma\in\Gamma}V_{n\pi\gamma}(h_{n}),\quad h_{n}\in\mathcal{H}_{n}.

To minimize this quantity is the controller’s optimization objective. For the robust policy value, a cost iteration holds, too. With regard to a policy of nature this is a Bellman equation given a fixed policy of the controller.

Theorem 3.6.

Let Assumptions 2.1, 3.1 be satisfied.

The robust value of a policy $\pi\in\Pi^{R}$ is a measurable function of $h_{n}\in\mathcal{H}_{n}$ for $n=0,\dots,N-1$ . It can be calculated recursively as

	$\displaystyle V_{N\pi}(h_{N})$	$\displaystyle=c_{N}(x_{N}),$
	$\displaystyle V_{n\pi}(h_{n})$	$\displaystyle=\mathcal{T}_{n\pi_{n}}V_{n+1\pi}(h_{n})$

b)

If the ambiguity sets $\mathcal{Q}_{n+1}$ are weak* closed, there exist maximizing decision rules $\gamma_{n}^{*}$ of nature for all $n$ . Each sequence of such decision rules $\gamma^{*}=(\gamma_{1}^{*},\dots,\gamma_{N-1}^{*})\in\Gamma$ is an optimal response of nature to the controller’s policy, i.e. $V_{n\pi}=V_{n\pi\gamma^{*}}$ , $n=0,\dots,N-1.$

Proof.

The proof is by backward induction. At time $N$ there is nothing to show. Now assume the assertion holds at time $n+1$ , i.e. that $V_{n+1\pi}$ is measurable and that for every $\epsilon>0$ there exists an $\frac{\epsilon}{2}$ -optimal strategy $\hat{\gamma}=(\hat{\gamma}_{n+1},\dots,\hat{\gamma}_{N-1})$ of nature. By Proposition 3.5 we have at $n$

	$\displaystyle V_{n\pi}(h_{n})$	$\displaystyle=$	$\displaystyle\sup_{\gamma\in\Gamma}V_{n\pi\gamma}(h_{n})=\sup_{\gamma\in\Gamma}\mathcal{T}_{n\pi_{n}\gamma_{n}}V_{n+1\pi\gamma}(h_{n})\leq\sup_{\gamma\in\Gamma}\mathcal{T}_{n\pi_{n}\gamma_{n}}V_{n+1\pi}(h_{n})\leq\mathcal{T}_{n\pi_{n}}V_{n+1\pi}(h_{n})$		(3.1)
		$\displaystyle\leq$	$\displaystyle\!\!\!\mathcal{T}_{n\pi_{n}\hat{\gamma}_{n}}V_{n+1\pi}(h_{n})+\frac{\varepsilon}{2}\leq\mathcal{T}_{n\pi_{n}\hat{\gamma}_{n}}V_{n+1\pi\hat{\gamma}}(h_{n})\!+\!\varepsilon=V_{n\pi\hat{\gamma}}(h_{n})\!+\!\epsilon\leq V_{n\pi}(h_{n})+\epsilon$		(3.1)

where $\hat{\gamma}_{n}:\mathcal{H}_{n}\times A\to\mathcal{Q}_{n+1}$ is a measurable $\frac{\epsilon}{2}$ -maximizer.

Since $\epsilon>0$ is arbitrary, equality holds. It remains to show the measurability of the outer integrand after the second inequality and the existence of an $\frac{\epsilon}{2}$ -maximizer. This follows from the optimal measurable selection theorem in [Rieder1978]: To see this, first note that the function

f(h_{n},a_{n},\mathbb{Q})=\int c_{n}\big{(}x_{n},a_{n},T_{n}(x_{n},a_{n},Z_{n+1})\big{)}+V_{n+1\pi}\big{(}h_{n},a_{n},T_{n}(x_{n},a_{n},Z_{n+1})\big{)}\operatorname{d}\mathbb{Q},

is jointly measurable due to Lemma 4.51 in [AliprantisBorder2006]. Consequently,

\left\{(h_{n},a_{n},\mathbb{Q})\in\mathcal{H}_{n}\times A\times\mathcal{Q}_{n+1}:f(h_{n},a_{n},\mathbb{Q})\geq\eta\right\}\in\left\{S\times Q:S\in\={(}\mathcal{H}_{n}\times A),\ Q\subseteq\mathcal{Q}_{n+1}\right\}.

for every $\eta\in\mathbb{R}$ . The right hand side is a selection class. Obviously, it holds

\mathcal{H}_{n}\times A\times\mathcal{Q}_{n+1}\in\left\{S\times Q:S\in\={(}\mathcal{H}_{n}\times A),\ Q\subseteq\mathcal{Q}_{n+1}\right\}.

Now, Theorem 3.2 in [Rieder1978] yields that

\mathcal{H}_{n}\times A\ni(h_{n},a_{n})\mapsto\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}f(h_{n},a_{n},\mathbb{Q})

is measurable and for every $\epsilon>0$ there exists an $\epsilon$ -maximizer $\gamma_{n}:\mathcal{H}_{n}\times A\to\mathcal{Q}_{n+1}$ .

For part b) we have to show that there exists not only a $\epsilon$ -maximizer $\hat{\gamma}_{n}$ at (3.1) but a maximizer. This follows from Theorem 3.7 in [Rieder1978]. The additional requirements are that $\mathcal{Q}_{n+1}$ is a separable metrizable space, which holds by Lemma 2.3, and that the set $\{\mathbb{Q}\in\mathcal{Q}_{n+1}:f(h_{n},a_{n},\mathbb{Q})\geq\eta\}$ is compact for every $\eta\in\mathbb{R}$ and $(h_{n},a_{n})\in\mathcal{H}_{n}\times A$ . By assumption, $\mathcal{Q}_{n+1}$ is weakly closed and therefore compact by Lemma 2.3. Since due to Assumption 3.1 the integrand of $f$ is in $L^{p}$ , the mapping $\mathbb{Q}\mapsto f(h_{n},a_{n},\mathbb{Q})$ is continuous for every $(h_{n},a_{n})\in\mathcal{H}_{n}\times A$ . Hence, $\{\mathbb{Q}\in\mathcal{Q}_{n+1}:f(h_{n},a_{n},\mathbb{Q})\geq\eta\}$ is closed as the preimage of a closed set. Since closed subsets of compact sets are compact, the proof is complete. ∎

So far we have only considered the case that the ambiguity set may depend on the time index but not on the state of the decision process. This covers many applications, e.g. the connection to risk measures (see Section 6). Moreover, we can allow any norm bounded ambiguity sets as long as it is independent of the state using the optimal selection theorem by [Rieder1978] in Theorem 3.6. If the ambiguity set is weak* closed, the following generalization is possible.

Corollary 3.7.

For $n=0,\dots,N-1$ let $\mathcal{Q}_{n}$ be weak* closed and

D_{n}\ni(x,a)\mapsto\mathcal{Q}_{n+1}(x,a)\subseteq\mathcal{Q}_{n+1}

be a non-empty and closed-valued mapping giving the possible probability measures at time $n$ in state $x\in E$ if the controller chooses $a\in D_{n}(x)$ . Then the assertion of Theorem 3.6 b) still holds.

Proof.

We have to show the existence of a measurable maximizer at (3.1). The rest of the proof is not affected. Since $\mathcal{Q}_{n+1}$ is weak* closed, it is a compact Borel space by Lemma 2.3. Consequently, the set-valued mapping $\mathcal{Q}_{n+1}(\cdot)$ is compact-valued, as closed subsets of compact sets are compact. In the proof of the theorem it has been shown that the function $f(h_{n},a_{n},\mathbb{Q})$ is jointly measurable and continuous in $\mathbb{Q}$ . Hence, Proposition D.5 in [HernandezLasserre1996] yields the existence of a measurable maximizer. ∎

State dependent ambiguity sets are a possibility to make the distributionally robust optimality criterion less conservative. E.g. they allow to incorporate learning about the unknown disturbance distribution. We refer the reader to [Bielecki2019] for an interesting example where the ambiguity sets are recursive confidence regions for an unknown parameter of the disturbance distribution.

Let us now consider specifically deterministic Markov policies $\pi\in\Pi^{M}$ of the controller. The subspace

\mathbb{B}=\{v\in\mathbb{B}_{b}:\ v\text{ lower semicontinuous}\}.

of $(\mathbb{B}_{b},\|\cdot\|_{b})$ turns out to be the set of possible value functions under such policies. $(\mathbb{B},\|\cdot\|_{b})$ is a complete metric space since the subset of lower semicontinuous functions is closed in $(\mathbb{B}_{b},\|\cdot\|_{b})$ . We define the following operators on $\mathbb{B}_{b}$ and especially on $\mathbb{B}$ .

Definition 3.8.

For $v\in\mathbb{B}_{b}$ and Markov decision rules $d:E\to A$ , $\gamma:D_{n}\to\mathcal{Q}_{n+1}$ we define

$\displaystyle L_{n}v(x,a,\mathbb{Q})$	$\displaystyle=\int c_{n}(x,a,T_{n}(x,a,Z_{n+1}))+v(T_{n}(x,a,Z_{n+1}))\operatorname{d}\mathbb{Q},\quad$	$\displaystyle(x,a,\mathbb{Q})\in D_{n}\times\mathcal{Q}_{n+1},$
$\displaystyle\mathcal{T}_{nd\gamma}v(x)$	$\displaystyle=L_{n}v\big{(}x,d(x),\gamma(x,d(x))\big{)},$	$\displaystyle x\in E,$
$\displaystyle\mathcal{T}_{nd}v(x)$	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}v(x,d(x),\mathbb{Q}),$	$\displaystyle x\in E,$
$\displaystyle\mathcal{T}_{n}v(x)$	$\displaystyle=\inf_{a\in D_{n}(x)}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}v(x,a,\mathbb{Q}),$	$\displaystyle x\in E.$

Note that the operators are monotone in $v$ . Under Markov policies $\pi=(d_{0},\dots,d_{N-1})\in\Pi^{M}$ of the controller and $\gamma=(\gamma_{0},\dots,\gamma_{N-1})\in\Gamma^{M}$ of nature, the value iteration can be expressed with the help of these operators. In order to distinguish from the history-dependent case, we denote the value function here with $J$ . Setting $J_{N\pi\gamma}(x)=c_{N}(x),\ x\in E,$ we obtain for $n=0,\dots,N-1$ and $x\in E$ with Proposition 3.5

	$\displaystyle J_{n\pi\gamma}(x)$	$\displaystyle=\int c_{n}\big{(}x,d_{n}(x),T_{n}(x,d_{n}(x),z_{n+1})\big{)}$
		$\displaystyle\phantom{=\int}\ +J_{n+1\pi\gamma}\big{(}T_{n}(x,d_{n}(x),z_{n+1})\big{)}\,\gamma_{n}(\operatorname{d}z_{n+1}\|x,d_{n}(x))=\mathcal{T}_{nd_{n}\gamma_{n}}J_{n+1\pi\gamma}(x).$

We define the robust value of Markov policy $\pi\in\Pi^{M}$ of the controller as

\displaystyle J_{n\pi}(x)=\sup_{\gamma\in\Gamma^{M}}J_{n\pi\gamma}(x),\qquad x\in E.

When calculating the robust value of a Markov policy of the controller it is no restriction to take the supremum only over Markov policies of nature.

Corollary 3.9.

Let $\pi\in\Pi^{M}$ . It holds for $n=0,\dots,N$ that $J_{n\pi}(x_{n})=V_{n\pi}(h_{n}),\ h_{n}\in\mathcal{H}_{n}.$ I.e., we have the robust value iteration

	$\displaystyle J_{n\pi}(x)$	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\int c_{n}\big{(}x,d_{n}(x),T_{n}(x,d_{n}(x),Z_{n+1})\big{)}+J_{n+1\pi}\big{(}T_{n}(x,d_{n}(x),Z_{n+1})\big{)}\operatorname{d}\mathbb{Q}$
		$\displaystyle=\mathcal{T}_{nd_{n}}J_{n+1\pi}(x).$

Moreover, there exists a Markovian $\epsilon$ -optimal policy of nature and if the ambiguity sets $\mathcal{Q}_{n+1}$ are all weak* closed even a Markovian optimal policy.

Proof.

For $n=N$ the assertion is trivial. Assuming it holds at time $n+1$ , it follows at time $n$ from Theorem 3.6 that

	$\displaystyle V_{n\pi}(h_{n})$	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\int c_{n}\big{(}x,d_{n}(x),T_{n}(x,d_{n}(x),Z_{n+1})\big{)}+J_{n+1\pi}\big{(}T_{n}(x,d_{n}(x),Z_{n+1})\big{)}\operatorname{d}\mathbb{Q}$
		$\displaystyle=J_{n\pi}(x_{n}).$

Replacing $\mathcal{H}_{n}\times A$ by $D_{n}$ , the existence of ( $\epsilon$ -) optimal policies is guaranteed by the same arguments as in the proof of Theorem 3.6. ∎

Let us further define for $n=0,\dots,N$ the Markovian value function

\displaystyle J_{n}(x)=\inf_{\pi\in\Pi^{M}}\sup_{\gamma\in\Gamma^{M}}J_{n\pi\gamma}(x),\qquad x\in E.

The next result shows that $J_{n}$ satisfies a Bellman equation and proves that an optimal policy of the controller exists and is Markov.

Theorem 3.10.

Let Assumptions 2.1, 3.1 be satisfied.

a)

For $n=0,\dots,N-1$ , it suffices to consider deterministic Markov policies both for the controller and nature, i.e. $V_{n}(h_{n})=J_{n}(x_{n})$ for all $h_{n}\in\mathcal{H}_{n}$ . Moreover, $J_{n}\in\mathbb{B}$ and satisfies the Bellman equation

$\displaystyle J_{N}(x)$ $\displaystyle=c_{N}(x),$

$\displaystyle J_{n}(x)$ $\displaystyle=\mathcal{T}_{n}J_{n+1}(x),\qquad x\in E.$

For $n=0,\dots,N-1$ there exist Markov minimizers $d_{n}^{*}$ of $J_{n+1}$ and every sequence of such minimizers constitutes an optimal policy $\pi^{*}=(d_{0}^{*},\dots,d_{N-1}^{*})$ of the controller.
b)

If the ambiguity sets $\mathcal{Q}_{n}$ are weak* closed, there exist maximizing decision rules $\gamma_{n}^{*}$ of nature, i.e. $J_{n}=\mathcal{T}_{d_{n}^{*}\gamma_{n}^{*}}J_{n+1}$ and every sequence of maximizers induces an optimal policy of nature $\gamma^{*}=(\gamma_{0}^{*},\dots,\gamma_{N-1}^{*})\in\Gamma^{M}$ satisfying $J_{n}=J_{n\pi^{*}\gamma^{*}}$ .

Proof.

We proceed by backward induction. At time $N$ we have $V_{N}=J_{N}=c_{N}\in\mathbb{B}$ due to semicontinuity and Assumption 3.1 (i). Now assume the assertion holds at time $n+1$ . Using the robust value iteration (Corollary 3.9) we obtain at time $n$ :

$\displaystyle V_{n}(h_{n})$	$\displaystyle=$	$\displaystyle\inf_{\pi\in\Pi^{R}}\sup_{\gamma\in\Gamma}V_{n\pi\gamma}(h_{n})=\inf_{\pi\in\Pi^{R}}V_{n\pi}(h_{n})=\inf_{\pi\in\Pi^{R}}\mathcal{T}_{n\pi_{n}}V_{n+1\pi}(h_{n})$
	$\displaystyle\geq$	$\displaystyle\inf_{\pi\in\Pi^{R}}\mathcal{T}_{n\pi_{n}}V_{n+1}(h_{n})=\inf_{\pi\in\Pi^{R}}\int\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}J_{n+1}(x_{n},a_{n},\mathbb{Q})\pi_{n}(\operatorname{d}a_{n}\|h_{n})$
	$\displaystyle\geq$	$\displaystyle\inf_{a_{n}\in D_{n}(x_{n})}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}J_{n+1}(x_{n},a_{n},\mathbb{Q})=\mathcal{T}_{n}J_{n+1}(x_{n}).$

Here, objective and constraint depend on the history of the process only through $x_{n}$ . Thus, given the existence of a minimizing Markov decision rule $d_{n}^{*}$ the last expression is equal to $\mathcal{T}_{nd_{n}^{*}}J_{n+1}(x_{n})$ . Again by the induction hypothesis, there exists an optimal Markov policy $\pi=(d_{n+1}^{*},\dots,d_{N-1}^{*})\in\Pi^{M}$ such that

\displaystyle V_{n}(h_{n})\geq\mathcal{T}_{n}J_{n+1}(x_{n})=\mathcal{T}_{nd_{n}^{*}}J_{n+1\pi^{*}}(x_{n})=J_{n\pi^{*}}(x_{n})\geq J_{n}(x_{n})\geq V_{n}(h_{n}).

(3.2)

It remains to show the existence of a minimizing Markov decision rule $d_{n}^{*}$ and that $J_{n}\in\mathbb{B}$ . We want to apply Proposition 2.4.3 in [BaeuerleRieder2011]. The set-valued mapping $E\ni x\mapsto D_{n}(x)$ is compact-valued and upper semicontinuous. Next, we show that $D_{n}\ni(x,a)\mapsto\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}v(x,a,\mathbb{Q})$ is lower semicontinuous for every $v\in\mathbb{B}$ . Let $\{(x_{k},a_{k})\}_{k\in\mathbb{N}}$ be a convergent sequence in $D_{n}$ with limit $(x^{*},a^{*})\in D_{n}$ . The function

\displaystyle(x,a)\mapsto c_{n}\big{(}x,a,T_{n}(x,a,z)\big{)}+v\big{(}T_{n}(x,a,z)\big{)}

(3.3)

is lower semicontinuous for every $z\in\mathcal{Z}$ . The sequence of random variables $\{C_{k}\}_{n\in\mathbb{N}}$ given by

C_{k}:=c_{n}\big{(}x_{k},a_{k},T_{n}(x_{k},a_{k},Z_{n+1})\big{)}+v\big{(}T_{n}(x_{k},a_{k},Z_{n+1})\big{)}

is bounded by some $\bar{C}\in L^{p}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1})$ by Lemma LABEL:thm:abstract_robust_Lpbound. Now, Fatou’s Lemma yields for every $\mathbb{Q}\in\mathcal{Q}_{n+1}$

	$\displaystyle\liminf_{k\to\infty}L_{n}v(x_{k},a_{k},\mathbb{Q})$	$\displaystyle=\liminf_{k\to\infty}\mathbb{E}^{\mathbb{Q}}\Big{[}c_{n}\big{(}x_{k},a_{k},T_{n}(x_{k},a_{k},Z_{n+1})\big{)}+v\big{(}T_{n}(x_{k},a_{k},Z_{n+1})\big{)}\Big{]}$
		$\displaystyle\geq\mathbb{E}^{\mathbb{Q}}\Big{[}\liminf_{k\to\infty}c_{n}\big{(}x_{k},a_{k},T_{n}(x_{k},a_{k},Z_{n+1})\big{)}+v\big{(}T_{n}(x_{k},a_{k},Z_{n+1})\big{)}\Big{]}$
		$\displaystyle\geq\mathbb{E}^{\mathbb{Q}}\left[c_{n}\big{(}x^{},a^{},T_{n}(x^{},a^{},Z_{n+1})\big{)}+v\big{(}T_{n}(x^{},a^{},Z_{n+1})\big{)}\right]=L_{n}v(x^{},a^{},\mathbb{Q}),$

where the last inequality is by the lower semicontinuity of (3.3). Thus, the function $D_{n}\ni(x,a)\mapsto L_{n}v(x,a,\mathbb{Q})$ is lower semicontinuous for every $\mathbb{Q}\in\mathcal{Q}_{n+1}$ and consequently $D_{n}\ni(x,a)\mapsto\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}v(x,a,\mathbb{Q})$ is lower semicontinuous as a supremum of lower semicontinuous functions. Now, Proposition 2.4.3 in [BaeuerleRieder2011] yields the existence of a minimizing Markov decision rule $d_{n}^{*}$ at (3.2) and that $J_{n}=\mathcal{T}_{n}J_{n+1}$ is lower semicontinuous. Furthermore, $J_{n}$ is bounded by $\lambda b$ for some $\lambda\in\mathbb{R}_{+}$ due to Lemma 3.3. Thus $J_{n}\in\mathbb{B}$ . Part b) follows from Theorem 3.6 b). ∎

4. Real Line as State Space

The model has been introduced in Section 2 with a general Borel space as state space. In order to solve the distributionally robust cost minimization problem in Section 3 we needed a continuous transition function despite having a semicontinuous model, cf. the proof of Theorem 3.10. This assumption on the transition function can be relaxed to semicontinuity if the state space is the real line and the transition and one-stage cost function have some form of monotonicity. In some applications this relaxation of the continuity assumption is relevant. Furthermore, a real state space can be exploited to address the distributionally robust cost minimization problem with more specific techniques. In addition to Assumption 3.1, we make the following assumptions in this section.

Assumption 4.1.

(i)

The state space is the real line $E=\mathbb{R}$ .
(ii)

The model data satisfies the Continuity and Compactness Assumptions 2.1 with the transition function $T_{n}$ being lower semicontinuous instead of continuous.
(iii)
The model data has the following monotonicity properties:
- (iii a)
  
  The set-valued mapping $\mathbb{R}\ni x\mapsto D_{n}(x)$ is decreasing.
- (iii b)
  
  The function $\mathbb{R}\ni x\mapsto T_{n}(x,a,z)$ is increasing for all $a\in D_{n}(x),z\in\mathcal{Z}$ .
- (iii c)
  
  The function $\mathbb{R}^{2}\ni(x,x^{\prime})\mapsto c_{n}(x,a,x^{\prime})$ is increasing for all $a\in D_{n}(x)$ .
- (iii d)
  
  The function $\mathbb{R}\ni x\mapsto c_{N}(x)$ is increasing.

With the real line as state space a simple separation condition is sufficient for Assumption 3.1 (ii).

Corollary 4.2.

Let there be upper semicontinuous functions $\vartheta_{n,1},\vartheta_{n,2}:D\to\mathbb{R}_{+}$ and measurable functions $\Theta_{n,1},\Theta_{n,2}:\mathcal{Z}\to\mathbb{R}_{+}$ which fulfil $\Theta_{n,1}(Z_{n+1}),\Theta_{n,2}(Z_{n+1})\in L^{p}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ and

\displaystyle|c_{n}(x,a,T_{n}(x,a,z))|\leq\vartheta_{n,1}(x,a)+\Theta_{n,1}(z),\qquad b(T_{n}(x,a,z))\leq\vartheta_{n,2}(x,a)+\Theta_{n,2}(z)

for every $(x,a,z)\in D\times\mathcal{Z}$ . Then Assumption 3.1 (ii) is satisfied.

Proof.

Let $(\bar{x},\bar{a})\in D_{n}$ . We can choose $\epsilon>0$ arbitrarily. The set $S=[\bar{x}-\epsilon,\bar{x}+\epsilon]\times D_{n}(\bar{x}-\epsilon)$ is compact w.r.t. the product topology. Moreover, $B_{\epsilon}(\bar{x},\bar{a})\cap D_{n}\subseteq S$ since the set-valued mapping $D_{n}(\cdot)$ is decreasing. Due to upper semicontinuity there exist $(x_{i},a_{i})\in S$ such that $\vartheta_{n,i}(x_{i},a_{i})=\sup_{(x,a)\in S}\vartheta_{n,i}(x,a)$ , $i=1,2$ . Hence, one can define

\Theta_{n,i}^{\bar{x},\bar{a}}(\cdot):=\vartheta_{n,i}(x_{i},a_{i})+\Theta_{n,i}(\cdot),\quad i=1,2

and Assumption 3.1 (ii) is satisfied. ∎

The question is, how replacing Assumption 2.1 (ii) by Assumption 4.1 affects the validity of all previous results. The only result that was proven using the continuity of the transition function $T_{n}$ in $(x,a)$ and not only its measurability is Theorem 3.10. All other statements are unaffected.

Proposition 4.3.

The assertions of Theorem 3.10 still hold when we replace Assumption 2.1 by Assumption 4.1. Moreover, $J_{n}$ and $J$ are increasing. The set of potential value functions can therefore be replaced by

\mathbb{B}=\{v\in\mathbb{B}_{b}:\ v\text{ lower semicontinuous and increasing}\}.

Proof.

In the proof of Theorem 3.10 the continuity of $T_{n}$ is used to show that $D_{n}\ni(x,a)\mapsto L_{n}v(x,a)$ is lower semicontinuous for every $v\in\mathbb{B}$ . Due to the monotonicity assumptions

D_{n}\ni(x,a)\mapsto c_{n}\big{(}x,a,T_{n}(x,a,z_{n+1})\big{)}+v\big{(}T_{n}(x,a,z_{n+1})\big{)}

is lower semicontinuous for every $z_{n+1}\in\mathcal{Z}$ . Now the lower semicontinuity of $D_{n}\ni(x,a)\mapsto L_{n}v(x,a)$ and the existence of a minimizing decision rule follows as in the proof of Theorem 3.10. The fact that $\mathcal{T}_{n}v$ is increasing for every $v\in\mathbb{B}$ follows as in Theorem 2.4.14 in [BaeuerleRieder2011]. ∎

In the following Section 5 we use a minimax approach as an alternative way to solve the Bellman equation of the distributionally robust cost minimization problem and to study its game theoretical properties. Subsequently in Section 6, we also consider special choices of the ambiguity set which are advantageous for solving the optimization problem.

5. Minimax Approach and Game Theory

We assume $E=\mathbb{R}$ as in the last section. Compared to a risk-neutral Markov Decision Model, the Bellman equation of the robust model (see Theorem 3.10) has the additional complication that a supremum over possibly uncountably many expectations needs to be calculated. This can be a quite challenging task. Therefore, it may be advantageous to interchange the infimum and supremum. For instance, in applications it may be possible to infer structural properties of the optimal actions independently from the probability measure $\mathbb{Q}$ after the interchange. Based on the minimax theorem by [Sion1958], cf. Appendix Theorem LABEL:thm:A:minimax, this section presents a criterion under which the interchange of infimum and supremum is possible.

Lemma 5.1.

Let Assumptions 3.1, 4.1 be satisfied. Let $A$ be a subset of a vector space, $D_{n}$ be a convex set, $x\mapsto c_{N}(x)$ , $(x,a)\mapsto T_{n}(x,a,z)$ be convex as well as $(x,a,x^{\prime})\mapsto c_{n}(x,a,x^{\prime})$ . Then the value functions $J_{n}$ and the limit value function $J$ are convex.

Proof.

The proof is by backward induction. $J_{N}=c_{N}$ is convex by assumption. Now assume that $J_{n+1}$ is convex. Recall that $J_{n+1}$ is increasing (Proposition 4.3). Hence, for every $z\in\mathcal{Z}$ the function

\displaystyle D_{n}\ni(x,a)\mapsto c_{n}\big{(}x,a,T_{n}(x,a,z)\big{)}+J_{n+1}\big{(}T_{n}(x,a,z)\big{)}

is convex as a composition of an increasing convex with a convex function. By the linearity of expectation,

\displaystyle D_{n}\ni(x,a)\mapsto\mathbb{E}^{\mathbb{Q}}\Big{[}c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+J_{n+1}\big{(}T_{n}(x,a,Z_{n+1})\big{)}\Big{]}

(5.1)

is convex for every $\mathbb{Q}\in\mathcal{Q}_{n+1}$ . As the pointwise supremum of a collection of convex functions is convex, we obtain convexity of $D_{n}\ni(x,a)\mapsto\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}LJ_{n+1}(x,a,\mathbb{Q})$ . Now, Proposition 2.4.18 in [BaeuerleRieder2011] yields the assertion. ∎

The assumptions of Lemma 5.1 are subsequently referred to as convex model.

Theorem 5.2.

Let Assumptions 3.1, 4.1 be satisfied. In a convex model we have for all $n=0,\dots,N-1$

\displaystyle J_{n}(x)

\displaystyle=\inf_{a\in D_{n}(x)}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}J_{n+1}(x,a,\mathbb{Q})=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\inf_{a\in D_{n}(x)}L_{n}J_{n+1}(x,a,\mathbb{Q}),\qquad x\in\mathbb{R}.

Proof.

Let $x\in\mathbb{R}$ be fixed and define $f:D_{n}(x)\times\mathcal{Q}_{n+1}\to\mathbb{R}$ ,

f(a,\mathbb{Q})=L_{n}v(x,a,\mathbb{Q})=\mathbb{E}^{\mathbb{Q}}\Big{[}c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+J_{n+1}\big{(}T_{n}(x,a,Z_{n+1})\big{)}\Big{]}.

The function $f$ is convex in $a$ by (5.1) and linear in $\mathbb{Q}$ , i.e. especially concave. Furthermore, the set $D_{n}(x)$ is compact and it has been shown in the proof of Theorem 3.10 that $f$ is lower semicontinuous in $a$ . Hence, the assertion follows from Theorem LABEL:thm:A:minimax a). ∎

Remark 5.3.

The interchange of infimum and supremum in Theorem 5.2 is based on Sion’s Minimax Theorem LABEL:thm:A:minimax, which requires convexity of the function

\displaystyle a\mapsto\int c_{n}\big{(}x,a,T_{n}(x,a,z)\big{)}+J_{n+1}\big{(}T(x,a,z)\big{)}\,\mathbb{Q}(\operatorname{d}z)

(5.2)

for every $(x,\mathbb{Q})\in\mathbb{R}\times\mathcal{Q}$ . This can be guaranteed by a convex model (cf. Lemma 5.1) which means that several components of the decision model need to have some convexity property. However, these assumptions are quite restrictive. Resorting to randomized actions is a standard approach to convexify (or more precisely linearize) the function (5.2) without assumptions on the model components. Let $\mathcal{P}(D_{n}(x))$ be the set of all probability measures on $D_{n}(x)$ . Then it follows from Sion’s Theorem LABEL:thm:A:minimax that

		$\displaystyle\inf_{\mu\in\mathcal{P}(D_{n}(x))}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\int L_{n}J_{n+1}(x,a,\mathbb{Q})\mu(da)=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\inf_{\mu\in\mathcal{P}(D_{n}(x))}\int L_{n}J_{n+1}(x,a,\mathbb{Q})\mu(da)$		(5.3)
		$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\inf_{a\in D_{n}(x)}L_{n}J_{n+1}(x,a,\mathbb{Q}).$

The last equality holds since $a\mapsto c_{n}\big{(}x,a,T_{n}(x,a,z)\big{)}+J_{n+1}\big{(}T_{n}(x,a,z)\big{)}$ is lower semicontinuous (cf. the proof of Theorem 3.10) and $D_{n}(x)$ is compact. This appears to be a very elegant solution for the interchange problem, but unfortunately, the Bellman equation of the distributionally robust cost minimization problem (2.6) under a randomized action of the controller is given by

	$\displaystyle J_{n}(x)$	$\displaystyle=\inf_{\mu\in\mathcal{P}(D_{n}(x))}\int\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\int c_{n}\big{(}x,a,T_{n}(x,a,z)\big{)}+J_{n+1}\big{(}T_{n}(x,a,z)\big{)}\,\mathbb{Q}(\operatorname{d}z)\,\mu(\operatorname{d}a)$		(5.4)
		$\displaystyle=\inf_{a\in D_{n}(x)}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}J_{n+1}(x,a,\mathbb{Q}),$

cf. Theorems 3.6 and 3.10, and (5.3) does in general not equal (5.4). Recall that in our model nature is allowed to react to any realization of the controller’s action. This was crucial to obtain a robust value iteration in Theorem 3.6. In contrast to that, (5.3) means that nature maximizes only knowing the distribution of the controller’s action. However, in general (5.3) $\neq$ (5.4) as will be shown in the next example.

Example 5.4.

In order to see that (5.3) $\neq$ (5.4) and that infimum and supremum cannot be interchanged in general, consider the simple static counter example $N=1$ , $E=\mathbb{R}$ , $A=[0,1]$ , $D=\mathbb{R}\times A$ , $Z\sim\text{Bin}(1,p)$ , $p\in[0,1]=\mathcal{Q}$ , $T(x,a,z)=-(a-z)^{2}$ and $c(x,a,x^{\prime})=x^{\prime}$ . It is readily checked that Assumption 4.1 is satisfied. Especially, one has constant bounding functions. In this example (5.4) equals

	$\displaystyle\inf_{a\in[0,1]}\sup_{p\in[0,1]}\mathbb{E}^{p}\big{[}c(x,a,T(x,a,Z))\big{]}=\inf_{a\in[0,1]}\sup_{p\in[0,1]}-(1-p)a^{2}-p(a-1)^{2}$
	$\displaystyle=-\sup_{a\in[0,1]}\inf_{p\in[0,1]}(1-p)a^{2}+p(a-1)^{2}=-\sup_{a\in[0,1]}\min\{a^{2},(1-a)^{2}\}=-\frac{1}{4}.$

If the controller chooses $\mu\sim\mathcal{U}(0,1)$ , then (5.3) must be less or equal than

\displaystyle\sup_{p\in[0,1]}\int_{0}^{1}-(1-p)a^{2}-p(a-1)^{2}\,\operatorname{d}a

\displaystyle=\sup_{p\in[0,1]}-\frac{1}{3}(1-p)-\frac{1}{3}p=-\frac{1}{3}.

Indeed we obtain here $\sup_{p\in[0,1]}\inf_{a\in[0,1]}\mathbb{E}^{p}\big{[}c(x,a,T(x,a,Z))\big{]}=-\frac{1}{2}$ . The approach to interchange infimum and supremum through a linearization with randomized actions works when nature only observes the distribution and not the realization of the controller’s action. Also note that the situation here is quite different to classical two-person zero-sum games. The fact that infimum and supremum cannot be interchanged is a consequence of the asymmetric mover/follower situation. The example above with $P_{xa}^{p}=(1-p)a^{2}+p(a-1)^{2}$ and $[0,1]$ discretized can also be used as a counter-example within the setting of [NilimGhaoui2005] and [wiesemann2013robust].

As mentioned before, the distributionally robust cost minimization model can be interpreted as a dynamic game with nature as the controller’s opponent. Since nature chooses her action after the controller, observing his action but not being restricted by it, there is a (weak) second-mover advantage by construction of the game. The fact that infimum and supremum in the Bellman equation can be interchanged means that the second-mover advantage vanishes in the special case of a convex model.

Let additionally the one-stage ambiguity sets $\mathcal{Q}_{n}$ be weak* closed. Now, the conditions of Theorem LABEL:thm:A:minimax b) are fulfilled, too. Then, the ambiguity set is weak* compact by Lemma 2.3 and by Lemma LABEL:thm:abstract_robust_Lpbound we have that $c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+J_{n+1}\big{(}T_{n}(x,a,Z_{n+1})\big{)}$ is in $L^{p}$ . Thus, $\mathbb{Q}\mapsto L_{n}J_{n+1}(x,a,\mathbb{Q})$ is weak* continuous for every $(x,a)\in D$ . This yields that $(a,\mathbb{Q})\mapsto L_{n}J_{n+1}(x,a,\mathbb{Q})$ satisfies the minimax-equality

\min_{a\in D_{n}(x)}\max_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}J_{n+1}(x,a,\mathbb{Q})=\max_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\min_{a\in D_{n}(x)}L_{n}J_{n+1}(x,a,\mathbb{Q})

and Lemma 2.105 in [BarbuPrecupanu2012] implies that for every $x\in\mathbb{R}$ the function has a saddle point $(a^{*},\mathbb{Q}^{*})$ , i.e.

L_{n}J_{n+1}(x,a^{*},\mathbb{Q})\leq L_{n}J_{n+1}(x,a^{*},\mathbb{Q}^{*})\leq L_{n}J_{n+1}(x,a,\mathbb{Q}^{*})

for all $a\in D(x)$ and $\mathbb{Q}\in\mathcal{Q}_{n+1}$ . Such a saddle point constitutes a Nash equilibrium in the subgame scenario $X_{n}=x$ . We will show that Nash equilibria exist not only in one-stage subgames but also globally.

Before, let us introduce a modification of the game against nature where nature instead of the controller moves first. Given a policy of nature, the controller faces an arbitrary but fixed probability measure in each scenario $X_{n}=x$ . Thus, the inner optimization problem is a risk-neutral MDP and it follows from standard theory that it suffices for the controller to consider deterministic Markov policies. Clearly, the controller’s optimal policy will depend on the policy that nature has chosen before. It will turn out to be a pointwise dependence on the actions of nature. To clarify this and for comparability with the original game (2.6), where the controller moves first, we distinguish the following types of Markov strategies of the controller

	$\displaystyle\Pi(\mathbb{R})=$	$\displaystyle\Pi^{M}=\ \left\{\pi=(d_{0},\dots,d_{N-1})\|\,d_{n}:\mathbb{R}\to A\text{ measurable},\,d_{n}(x)\in D_{n}(x),\,x\in\mathbb{R}\right\}$
	$\displaystyle\Pi(\mathbb{R},\mathcal{Q})=$	$\displaystyle\ \left\{\pi=(d_{0},\dots,d_{N-1})\|\,d_{n}:\mathbb{R}\times\mathcal{Q}_{n+1}\to A\text{ measurable},\,d_{n}(x,\mathbb{Q})\in D_{n}(x),\,x\in\mathbb{R}\right\}$

and of nature

	$\displaystyle\Gamma(\mathbb{R})=$	$\displaystyle\ \left\{\gamma=(\gamma_{0},\dots,\gamma_{N-1})\|\ \gamma_{n}:\mathbb{R}\to\mathcal{Q}_{n+1}\text{ measurable}\right\}$
	$\displaystyle\Gamma(\mathbb{R},A)=\Gamma^{M}=$	$\displaystyle\ \left\{\gamma=(\gamma_{0},\dots,\gamma_{N-1})\|\ \gamma_{n}:\mathbb{R}\times A\to\mathcal{Q}_{n+1}\text{ measurable}\right\}.$

The value $J_{n\pi\gamma}$ of a pair of Markov policies $(\gamma,\pi)\in\Gamma(\mathbb{R})\times\Pi(\mathbb{R},\mathcal{Q})$ is defined as in (2.5). The bounds in Lemma 3.3 apply since the proofs do not use properties of the policies. The game under consideration is

\displaystyle\widetilde{J}_{n}(x)=\sup_{\gamma\in\Gamma(\mathbb{R})}\inf_{\pi\in\Pi(\mathbb{R},\mathcal{Q})}J_{n\pi\gamma}(x),\qquad x\in\mathbb{R},\ n=0,\ldots,N.

(5.5)

For clarity, we mark all quantities of the game where nature moves first which differ from the respective quantity of the original game with a tilde. The value of a policy of nature $\gamma\in\Gamma(\mathbb{R})$ is defined as

\displaystyle\widetilde{J}_{n\gamma}(x)=\inf_{\pi\in\Pi(\mathbb{R},\mathcal{Q})}J_{n\pi\gamma}(x),\qquad x\in\mathbb{R}.

The Bellman operator on $\mathbb{B}$ can be introduced in the usual way:

\displaystyle\widetilde{\mathcal{T}}_{n}v(x)

\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}\inf_{a\in D_{n}(x)}L_{n}v(x,a,\mathbb{Q}),\quad x\in\mathbb{R}.

Theorem 5.5.

Let Assumptions 3.1, 4.1 be satisfied, the ambiguity sets $\mathcal{Q}_{n+1}$ be weak* closed and the model be convex.

$\widetilde{J}_{n}\in\mathbb{B}$ for $n=0,\ldots,N$ and they satisfy the Bellman equation

	$\displaystyle\widetilde{J}_{N}(x)$	$\displaystyle=c_{N}(x),$
	$\displaystyle\widetilde{J}_{n}(x)$	$\displaystyle=\widetilde{\mathcal{T}}_{n}\widetilde{J}_{n+1}(x),\qquad x\in\mathbb{R}.$

There exist decision rules $\tilde{\gamma}_{n}:\mathbb{R}\to\mathcal{Q}_{n+1}$ of nature and $\tilde{d}_{n}:\mathbb{R}\times\mathcal{Q}_{n+1}\to A$ of the controller such that $\widetilde{J}_{n}(x)=\mathcal{T}_{\tilde{d}_{n}\tilde{\gamma}_{n}}\widetilde{J}_{n+1}(x)$ and all sequences of such decision rules induce an optimal policy pair $\tilde{\gamma}=(\tilde{\gamma}_{0},\dots,\tilde{\gamma}_{n-1})\in\Gamma(\mathbb{R})$ and $\tilde{\pi}=(\tilde{d}_{0},\dots,\tilde{d}_{n-1})\in\Pi(\mathbb{R},\mathcal{Q})$ i.e. $\widetilde{J}_{n}=J_{n\tilde{\pi}\tilde{\gamma}}$ .

b)

We have that $J_{n}=\widetilde{J}_{n}=\widetilde{J}_{n\tilde{\gamma}}$ .

Proof.

We have for $n$ and $x\in\mathbb{R}$ :

	$\displaystyle J_{n}(x)$	$\displaystyle=\inf_{\pi\in\Pi(\mathbb{R})}\sup_{\gamma\in\Gamma(\mathbb{R},A)}J_{n\pi\gamma}(x)\geq\inf_{\pi\in\Pi(\mathbb{R})}\sup_{\gamma\in\Gamma(\mathbb{R})}J_{n\pi\gamma}(x)\geq\sup_{\gamma\in\Gamma(\mathbb{R})}\inf_{\pi\in\Pi(\mathbb{R})}J_{n\pi\gamma}(x)$
		$\displaystyle\geq\sup_{\gamma\in\Gamma(\mathbb{R})}\inf_{\pi\in\Pi(\mathbb{R},\mathbb{Q})}J_{n\pi\gamma}(x)=\widetilde{J}_{n}(x).$		(5.6)

Let $\pi^{*}=(d_{0}^{*},\dots,d_{N-1}^{*})\in\Pi(\mathbb{R})$ and $\gamma^{*}=(\gamma_{0}^{*},\dots,\gamma_{N-1}^{*})\in\Gamma(\mathbb{R},A)$ be optimal strategies for the original game (2.6). The existence is guaranteed by Theorem 3.10. Then $\tilde{\gamma}=(\tilde{\gamma}_{0},\dots,\tilde{\gamma}_{N-1})$ defined by $\tilde{\gamma}_{n}:=\gamma_{n}^{*}(\cdot,d_{n}^{*}(\cdot))$ lies in $\Gamma(\mathbb{R})$ since the decision rules are well defined as compositions of measurable maps.
We prove all statements simultaneously by induction. In particular we show that there exists a policy $\tilde{\pi}\in\Pi(\mathbb{R},\mathcal{Q})$ such that

J_{n}=\widetilde{J}_{n\tilde{\gamma}}=\widetilde{J}_{n\tilde{\pi}\tilde{\gamma}}.

We show next that $J_{n}\leq\widetilde{J}_{n}$ . From Theorem 5.2 and the induction hypothesis we obtain

\displaystyle J_{n}(x)

\displaystyle=

\displaystyle L_{n}J_{n+1}(x,d_{n}^{*}(x),\tilde{\gamma}_{n}(x))=\inf_{a\in D_{n}(x)}L_{n}J_{n+1}(x,a,\tilde{\gamma}_{n}(x))=\inf_{a\in D_{n}(x)}L_{n}\widetilde{J}_{n+1}(x,a,\tilde{\gamma}_{n}(x)).

Observe that again by the induction hypothesis

$\displaystyle\widetilde{J}_{n\tilde{\gamma}}(x)$	$\displaystyle=$	$\displaystyle\inf_{\pi\in\Pi(\mathbb{R},\mathcal{Q})}J_{n\pi\tilde{\gamma}}(x)=\inf_{\pi\in\Pi(\mathbb{R},\mathcal{Q})}L_{n}J_{n+1\pi\tilde{\gamma}}(x,d_{n}(x,\tilde{\gamma}_{n}(x)),\tilde{\gamma}_{n}(x))$	(5.7)
	$\displaystyle\geq$	$\displaystyle\inf_{a\in D_{n}(x)}L_{n}\widetilde{J}_{n+1\tilde{\gamma}}(x,a,\tilde{\gamma}_{n}(x))=L_{n}\widetilde{J}_{n+1\tilde{\gamma}}(x,\tilde{d}_{n}(x,\tilde{\gamma}_{n}(x)),\tilde{\gamma}_{n}(x))$
	$\displaystyle=$	$\displaystyle L_{n}\widetilde{J}_{n+1\tilde{\pi}\tilde{\gamma}}(x,\tilde{d}_{n}(x,\tilde{\gamma}_{n}(x)),\tilde{\gamma}_{n}(x))=\widetilde{J}_{n\tilde{\pi}\tilde{\gamma}}\geq\widetilde{J}_{n\tilde{\gamma}}.$

We will show below the existence of a minimizer $\tilde{d}_{n}$ in the second line is justified. Thus we get equality in the expression above. Combining the previous two equations above we finally get

\displaystyle J_{n}(x)

\displaystyle=

\displaystyle\inf_{a\in D_{n}(x)}L_{n}\widetilde{J}_{n+1}(x,a,\tilde{\gamma}_{n}(x))=\widetilde{J}_{n\tilde{\gamma}}\leq\widetilde{J}_{n}(x).

In total we have shown that $J_{n}=\widetilde{J}_{n}=\tilde{J}_{n\tilde{\gamma}}=\tilde{J}_{n\tilde{\pi}\tilde{\gamma}}$ . The joint Bellman equation for the controller and nature $\widetilde{J}_{n}=\widetilde{\mathcal{T}}\widetilde{J}_{n+1}$ follows from Theorem 5.2.

Finally, we verify the existence of a minimizer $\tilde{d}_{n}$ . Let $\{(x_{n},a_{n},\mathbb{Q}_{n})\}_{n\in\mathbb{N}}$ be a convergent sequence in $\mathbb{R}\times A\times\mathcal{Q}$ with limit $(x^{*},a^{*},\mathbb{Q}^{*})$ . By dominated convergence (Lemma LABEL:thm:abstract_robust_Lpbound) and the lower semicontinuity of $D_{n}\ni(x,a)\mapsto c_{n}\big{(}x,a,T_{n}(x,a,z_{n+1})\big{)}+v\big{(}T_{n}(x,a,z_{n+1})\big{)}$ for any $v\in\mathbb{B}$ we obtain that the increasing sequence of random variables $\{C_{m}\}_{m}$ given by

C_{m}:=\inf_{k\geq m}c_{n}\big{(}x_{k},a_{k},T_{n}(x_{k},a_{k},Z_{n+1})\big{)}+v\big{(}T_{n}(x_{k},a_{k},Z_{n+1})\big{)}

satisfies

\displaystyle C_{m}

at\eqref{eq:thm5.4}andthat\begin{aligned} \mathbb{R}\times\mathcal{Q}_{n+1}\ni(x,\mathbb{Q})\mapsto\inf_{a\in D(x)}L_{n}\widetilde{J}_{n+1{\tilde{\gamma}}}(x,a,\mathbb{Q})=L_{n}\widetilde{J}_{n+1{\tilde{\gamma}}}(x,\tilde{d}_{n}(x,\mathbb{Q}),\mathbb{Q})\end{aligned}islowersemicontinuous.Thiscompletestheproof.\qed\par\end@proof\par\begin{remark}Notethatincontrasttoclassicalzero-sumgamesweobtaintheexistenceofdeterministicpolicies.\end{remark}\par AsadirectconsequencewegettheexistenceofNashequilibriaonpolicylevel.\par\begin{corollary}Consideraconvexmodelwithweak*closedambiguitysets$\mathcal{Q}_{n+1}$andAssumptions\ref{ass:abstract_robust_finite},\ref{ass:abstract_robust_real}fulfilled.For$x\in\mathbb{R}$weget\begin{aligned} J_{n}(x)=\min_{\pi\in\Pi(\mathbb{R})}\max_{\gamma\in\Gamma(\mathbb{R},A)}J_{n\pi\gamma}(x)=\max_{\gamma\in\Gamma(\mathbb{R})}\min_{\pi\in\Pi(\mathbb{R},\mathcal{Q})}J_{n\pi\gamma}(x)=\tilde{J}_{n}(x).\end{aligned}Consequently,weevenobtain$$J_{n}(x)=\min_{\pi\in\Pi(\mathbb{R})}\max_{\gamma\in\Gamma(\mathbb{R})}J_{n\pi\gamma}(x)=\max_{\gamma\in\Gamma(\mathbb{R})}\min_{\pi\in\Pi(\mathbb{R})}J_{n\pi\gamma}(x).$$\end{corollary}\par\@proof Theorem\ref{thm:abstract_robust_nature_first}impliesequalityin\eqref{eq:abstract_robust_nature_first_proof1},i.e.\begin{aligned} J_{n}(x)&=\min_{\pi\in\Pi(\mathbb{R})}\max_{\gamma\in\Gamma(\mathbb{R},A)}J_{n\pi\gamma}(x)=\inf_{\pi\in\Pi(\mathbb{R})}\sup_{\gamma\in\Gamma(\mathbb{R})}J_{n\pi\gamma}(x)\\ &=\sup_{\gamma\in\Gamma(\mathbb{R})}\inf_{\pi\in\Pi(\mathbb{R})}J_{n\pi\gamma}(x)=\max_{\gamma\in\Gamma(\mathbb{R})}\min_{\pi\in\Pi(\mathbb{R},\mathbb{Q})}J_{n\pi\gamma}(x)=\widetilde{J}_{n}(x).\end{aligned}Itremainstofindoptimalpoliciesforthesecondandfourthequationof\eqref{eq:abstract_robust_Nash_proof}.Let\begin{aligned} \pi^{*}&=(d_{0}^{*},\dots,d_{N-1}^{*})\in\Pi(\mathbb{R}),&\gamma^{*}&=(\gamma_{0}^{*},\dots,\gamma_{N-1}^{*})\in\Gamma(\mathbb{R},A)\\ \text{and}\qquad\qquad\tilde{\gamma}&=(\tilde{\gamma}_{0},\dots,\tilde{\gamma}_{N-1})\in\Gamma(\mathbb{R})&\tilde{\pi}&=(\tilde{d}_{0},\dots,\tilde{d}_{N-1})\in\Pi(\mathbb{R},\mathcal{Q})\end{aligned}beoptimalstrategiesforthefirstandfifthequationof\eqref{eq:abstract_robust_Nash_proof},respectively,whichexistbyProposition\ref{thm:abstract_robust_real}andTheorem\ref{thm:abstract_robust_nature_first}.Then$$\inf_{\pi\in\Pi(\mathbb{R})}\sup_{\gamma\in\Gamma(\mathbb{R})}J_{n\pi\gamma}=\sup_{\gamma\in\Gamma(\mathbb{R})}\inf_{\pi\in\Pi(\mathbb{R})}J_{n\pi\gamma}$$isattainedbytheadmissiblestrategypair$(\hat{\pi},\hat{\gamma})\in\Pi(\mathbb{R})\times\Gamma(\mathbb{R})$whichcanbedefinedby$\hat{d}_{n}:=d_{n}^{*}$and$\hat{\gamma}_{n}:=\gamma_{n}^{*}(\cdot,d_{n}^{*}(\cdot))$oralternativelyby$\hat{d}_{n}:=\tilde{d}_{n}(\cdot,\tilde{\gamma}_{n}(\cdot))$and$\hat{\gamma}_{n}:=\tilde{\gamma}_{n}$for$n=0,\dots,N-1$.\qed\end@proof\par

6. Special Ambiguity Sets

In this section, we consider some special choices for the ambiguity set $\mathcal{Q}_{n+1}$ which simplify solving the Markov Decision Problem (2.6) or allow for structural statements about the solution. We assume a real-valued state space here.

Convex hull. It does not change the optimal value of the optimization problems if a given ambiguity set $\mathcal{Q}_{n+1}$ is replaced by its convex hull $\operatorname{conv}(\mathcal{Q}_{n+1})$ or its closed convex hull $\operatorname{\overline{conv}}(\mathcal{Q}_{n+1})$ , where the closure is with respect to the weak* topology. Clearly, to demonstrate this, it suffices to compare the corresponding Bellman equations.

Lemma 6.1.

Let $\mathcal{Q}_{n+1}$ be any norm bounded ambiguity set. Then it holds for all $v\in\mathbb{B}$ and $x\in\mathbb{R}$

\displaystyle\inf_{a\in D_{n}(x)}\sup_{\mathbb{Q}\in\mathcal{Q}_{n+1}}L_{n}v(x,a,\mathbb{Q})=\inf_{a\in D(x)}\sup_{\mathbb{Q}\in\operatorname{conv}(\mathcal{Q}_{n+1})}L_{n}v(x,a,\mathbb{Q})=\inf_{a\in D(x)}\sup_{\mathbb{Q}\in\operatorname{\overline{conv}}(\mathcal{Q}_{n+1})}L_{n}v(x,a,\mathbb{Q}).

Proof.

Fix $(x,a)\in D_{n}$ . The function $\mathbb{Q}\mapsto L_{n}v(x,a,\mathbb{Q})$ is linear. Thus, for a generic element $\mathbb{Q}=\sum_{i=1}^{n}\lambda_{i}\mathbb{Q}_{i}\in\operatorname{conv}(\mathcal{Q}_{n+1})$ we have

L_{n}v\left(x,a,\sum_{i=1}^{m}\lambda_{i}\mathbb{Q}_{i}\right)=\sum_{i=1}^{m}\lambda_{i}L_{n}v(x,a,\mathbb{Q}_{i})\leq\max_{i=1,\dots,m}L_{n}v(x,a,\mathbb{Q}_{i}),

i.e. there can be no improvement of the supremum on the convex hull. We also have that $\operatorname{\overline{conv}}(\mathcal{Q}_{n+1})$ is metrizable and therefore coincides with the limit points of sequences in $\operatorname{conv}(\mathcal{Q}_{n+1})$ . Since $\mathbb{Q}\mapsto L_{n}v(x,a,\mathbb{Q})$ is weak* continuous (cf. proof of Theorem 3.6), the supremum cannot be improved on the closure either. ∎

Integral stochastic orders on $\mathcal{Q}_{n+1}$ . Following an idea of [Mueller1997], one can define integral stochastic orders on the ambiguity $\mathcal{Q}_{n+1}$ set by

	$\displaystyle\mathbb{Q}_{1}\leq_{\mathbb{B},x,a}\mathbb{Q}_{2}\ :\Longleftrightarrow\$	$\displaystyle L_{n}v(x,a,\mathbb{Q}_{1})\leq L_{n}v(x,a,\mathbb{Q}_{2})\quad\text{for all }v\in\mathbb{B}$
where $(x,a)\in D_{n}$ is fixed and
	$\displaystyle\mathbb{Q}_{1}\leq_{\mathbb{B}}\mathbb{Q}_{2}\ :\Longleftrightarrow\$	$\displaystyle\mathbb{Q}_{1}\leq_{\mathbb{B},x,a}\mathbb{Q}_{2}\quad\text{for all }(x,a)\in D_{n}.$

If there exists a maximal element with respect to one of these stochastic orders, this probability measure is an optimal action for nature (in the respective scenario). The proof of the next lemma follows directly from the Bellman equation and the definition of the orderings.

Lemma 6.2.

(a)

If there exists a maximal element $\mathbb{Q}_{n,x,a}\in\mathcal{Q}_{n+1}$ w.r.t. $\leq_{\mathbb{B},x,a}$ for every $(x,a)\in D_{n}$ , then $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ with $\gamma_{n}(x,a):=\mathbb{Q}_{n,x,a}$ defines an optimal policy.
(b)

If there exists a maximal element $\mathbb{Q}^{*}_{n}\in\mathcal{Q}_{n}$ w.r.t. $\leq_{\mathbb{B}}$ , then $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ with $\gamma_{n}\equiv\mathbb{Q}^{*}_{n}$ defines a constant optimal action of nature. That is, (2.6) can be reformulated to risk-neutral MDPs under the probability measure $\mathbb{Q}^{*}_{n}$ .

In fact, Lemma 6.2 holds for any state space. But it is only a reformulation of what is an optimal action for nature. However, under Assumption 4.1 it has practical relevance when a simpler sufficient condition for the integral stochastic order $\leq_{\mathbb{B}}$ is fulfilled. We give three exemplary criteria:

Let $\mathcal{Z}$ be a partially ordered space, e.g. $\mathcal{Z}=\mathbb{R}^{m}$ , and assume that the transition functions are increasing in $z$ . Then the functions

\displaystyle\mathcal{Z}\ni z\mapsto c_{n}(x,a,T_{n}(x,a,z))+v(T_{n}(x,a,z)),\qquad v\in\mathbb{B},\ (x,a)\in D_{n}

(6.1)

are increasing. Thus, $\mathbb{Q}_{1}\leq_{\mathbb{B}}\mathbb{Q}_{2}$ is implied by the usual stochastic order of the disturbance distributions $\mathbb{Q}_{1}^{Z_{n+1}}\leq_{st}\mathbb{Q}_{2}^{Z_{n+1}}$ and a maximal element of $\mathcal{Q}_{n+1}$ w.r.t. $\leq_{st}$ allows the same conclusion as in Lemma 6.2 b).

2.

Let $\mathcal{Z}$ be a real vector space, assume a convex model (cf. Lemma 5.1) and let the transition functions $T_{n}$ additionally be convex in $z$ . Now, Lemma 5.1 yields that the functions (6.1) are convex as compositions of increasing convex and convex mappings. Consequently, $\leq_{\mathbb{B}}$ is implied by the convex order $\leq_{cx}$ of the disturbance distributions $\mathbb{Q}^{Z_{n+1}}$ .

Convex order on the set of densities. Since the probability measures in $\mathcal{Q}_{n+1}$ are absolutely continuous with respect to the reference probability measure $\mathbb{P}_{n+1}$ , we can alternatively consider the set of densities $\mathcal{Q}_{n+1}^{d}$ (see (2.2)). In general, one has to take care both of the marginal distribution of the density and the dependence structure with the random cost when searching for a maximizing density of the Bellman equation

\inf_{a\in D_{n}(x)}\sup_{Y\in\mathcal{Q}_{n+1}^{d}}\mathbb{E}\Big{[}\Big{(}c_{n}\big{(}x,a,T_{n}(x,a,Z)\big{)}+J_{n+1}\big{(}T_{n}(x,a,Z)\big{)}\Big{)}Y\Big{]}.

However, if $\mathcal{Q}_{n+1}^{d}$ is sufficiently rich, the maximization reduces to comparing marginal distributions.

Definition 6.3.

The set of densities $\mathcal{Q}_{n}^{d}$ is called law invariant, if for $Y_{1}\in\mathcal{Q}_{n}^{d}$ every $Y_{2}\in L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ with $Y_{2}\sim Y_{1}$ is in $\mathcal{Q}_{n}^{d}$ , too.

Lemma 6.4.

Let Assumptions 3.1, 4.1 be satisfied. If $\mathcal{Q}_{n+1}^{d}$ is law invariant,

\sup_{Y\in\mathcal{Q}_{n+1}^{d}}\mathbb{E}\Big{[}\Big{(}c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+v\big{(}T_{n}(x,a,Z_{n+1})\big{)}\Big{)}Y\Big{]},\qquad(x,a)\in D_{n},\ v\in\mathbb{B},

(6.2)

is not changed by restricting the maximization to densities which are comonotonic to the random variable $T_{n}(x,a,Z_{n+1})$ .

Proof.

By Lemma LABEL:thm:abstract_robust_Lpbound $c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+v\big{(}T_{n}(x,a,Z_{n+1})\big{)}$ are in $L^{p}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1})$ for all $(x,a)\in D_{n}$ . Thus the expectation (6.2) exists for all $Y\in L^{q}(\mathcal{Z},\mathfrak{Z},\mathbb{P}^{Z_{n+1}})$ . Note that a product of r.v. with fixed margins is maximized in expectation when the r.v. are chosen comonotonic. Due to the law invariance of $\mathcal{Q}_{n+1}^{d}$ we can find for every $Y\in\mathcal{Q}_{n+1}^{d}$ some $Y^{\prime}\in\mathcal{Q}_{n+1}^{d}$ comonotonic to $c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+v\big{(}T_{n}(x,a,Z_{n+1})\big{)}$ such that $Y^{\prime}\sim Y$ and (6.2) is maximal with $Y^{\prime}$ . Since, the function $\mathbb{R}\ni x^{\prime}\mapsto c_{n}\big{(}x,a,x^{\prime}\big{)}+v\big{(}x^{\prime}\big{)}$ is increasing, this is the same as requiring comonotonicity to $T_{n}(x,a,Z_{n+1})$ . ∎

For the comparison of marginal distributions one would naturally think of stochastic orders. Here, the convex order yields a sufficient criterion for optimality. In order to obtain a connection to risk measures, let us introduce the following notations:

Definition 6.5.

Let $F_{X}$ be the distribution function of a real-valued random variable $X$ .

a)

The (lower) quantile function of $X$ is the left-continuous generalized inverse of $F_{X}$

$F^{-1}_{X}(\alpha):=q^{-}_{X}(\alpha):=\inf\{x\in\mathbb{R}:\ F_{X}(x)\geq\alpha\},\qquad\alpha\in(0,1).$
b)

The upper quantile function of $X$ is the right-continuous generalized inverse of $F_{X}$

$q^{+}_{X}(\alpha):=\inf\{x\in\mathbb{R}:\ F_{X}(x)>\alpha\},\qquad\alpha\in(0,1).$

Lemma 6.6 ([Rueschendorf2009, 2.1]).

For any random variable $X$ on an atomless probability space there exists a random variable $U_{X}\sim\mathcal{U}(0,1)$ such that

\displaystyle q_{X}^{-}(U_{X})=q_{X}^{+}(U_{X})=X\quad\mathbb{P}\text{-a.s.}

The random variable $U_{X}$ is referred to as (generalized) distributional transform of $X$ . Note that if $h:\mathbb{R}\to\mathbb{R}$ is increasing and left-continuous, then $X$ and $h(X)$ have the same distributional transform.

Definition 6.7.

Let $\phi:[0,1]\to\mathbb{R}_{+}$ be increasing and right-continuous with $\int_{0}^{1}\phi(u)\operatorname{d}u=1$ . Functionals $\rho_{\phi}:L^{p}\to\bar{\mathbb{R}}$

\displaystyle\rho_{\phi}(X):=\int_{0}^{1}q_{X}(u)\phi(u)\operatorname{d}u.

are called spectral risk measures and $\phi$ is called spectrum.

When we choose the spectrum $\phi(u)=\frac{1}{1-\alpha}1_{[\alpha,1]}(u)$ then we obtain the Expected Shortfall. Note that every spectral risk measure is also coherent, i.e. monotone, translation-invariant, positive homogeneous and subadditive.

In what follows we assume a non-atomic probability space.

Lemma 6.8.

Let Assumptions 3.1, 4.1 be satisfied, $\mathcal{Q}_{n+1}^{d}$ be law invariant and suppose there exists a maximal element $Y^{*}_{n+1}$ of $\mathcal{Q}_{n+1}^{d}$ w.r.t. the convex order $\leq_{cx}$ .

Then

\displaystyle\rho_{\phi}(X)=\sup_{Y\in\mathcal{Q}_{n+1}^{d}}\mathbb{E}[XY],\qquad X\in L^{p}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1}),

defines a spectral risk measure with spectrum $\phi_{n+1}(u):=q^{+}_{Y^{*}_{n+1}}(u),\ u\in[0,1]$ . In this case, $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ with $\gamma_{n}(x,a)=\phi_{n+1}(U_{T_{n}(x,a,Z_{n+1})})$ is an optimal strategy of nature in (2.6). Here $U_{T_{n}(x,a,Z_{n+1})}$ denotes the distributional transform of $T_{n}(x,a,Z_{n+1})$ .

b)

If additionally, the disturbance space is the real line $\mathcal{Z}=\mathbb{R}$ and the transition function $T_{n}$ is increasing and lower semicontinuous in $z$ , $\gamma=(\gamma_{0},\dots,\gamma_{N-1})$ with $\gamma_{n}\equiv\phi_{n+1}(U_{Z_{n+1}})$ defines a constant optimal action of nature. That is, (2.6) can be reformulated to a risk-neutral MDP with probability measures $\operatorname{d}\mathbb{Q}_{n+1}=\phi_{n+1}(U_{Z_{n+1}})\operatorname{d}\mathbb{P}_{n+1}$ .

Proof.

(a)

It holds $Y^{*}_{n+1}=q^{+}_{Y^{*}_{n+1}}(U_{Y^{*}_{n+1}})\ \mathbb{P}$ -a.s. by Lemma 6.6. Therefore,

\mathcal{Q}_{n+1}^{d}\subseteq\left\{Y\in L^{q}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1}):\ Y\leq_{cx}\phi_{n+1}(U),\ U\sim\mathcal{U}(0,1)\right\},

and the random variables $\phi_{n+1}(U),\ U\sim\mathcal{U}(0,1)$ are contained in both sets due to law invariance. $\rho_{\phi}$ indeed defines a spectral risk measure (see Proposition LABEL:thm:spectral_rm-dual) and $\phi_{n+1}(\tilde{U})$ is an optimal action of nature at time $n$ given $(x,a)$ , where $\tilde{U}$ is the distributional transform of the random variable

c_{n}\big{(}x,a,T_{n}(x,a,Z_{n+1})\big{)}+J_{n+1}\big{(}T_{n}(x,a,Z_{n+1})\big{)}.

Since the function $\mathbb{R}\ni x^{\prime}\mapsto c_{n}\big{(}x,a,x^{\prime}\big{)}+v\big{(}x^{\prime}\big{)}$ is increasing and lower semicontinuous, i.e. left continuous, it follows with Lemma 6.6 that $\tilde{U}=U_{T_{n}(x,a,Z_{n+1})}$ .

(b)

Under the additional assumptions we have that $U_{T_{n}(x,a,Z_{n+1})}=U_{Z_{n+1}}$ . ∎

Recall that the probability space under consideration is the product space. Under the assumptions of Lemma 6.8 b) we can replace the probability measure $\mathbb{P}$ by

\widehat{\mathbb{Q}}:=\bigotimes_{n=1}^{N-1}\mathbb{Q}^{*}_{n},\qquad\operatorname{d}\mathbb{Q}^{*}_{n}=\phi_{n}(U_{Z_{n}})\operatorname{d}\mathbb{P}_{n}

and the optimization problem (2.6) can equivalently be written as

\displaystyle\inf_{\pi\in\Pi^{M}}\mathbb{E}_{x}^{\widehat{\mathbb{Q}}}\left[\sum_{n=0}^{N-1}c_{n}(X_{n},d_{n}(X_{n}),X_{n+1})+c_{N}(X_{N})\right].

(6.3)

With the reversed argumentation of Lemma 6.8 a robust formulation of (6.3) is given by

\displaystyle\inf_{\pi\in\Pi^{M}}\sup_{\mathbb{Q}\in\mathfrak{Q}}\mathbb{E}_{x}^{\mathbb{Q}}\left[\sum_{n=0}^{N-1}c_{n}(X_{n},d_{n}(X_{n}),X_{n+1})+c_{N}(X_{N})\right]

(6.4)

with

\mathfrak{Q}=\left\{\bigotimes_{n=1}^{N-1}\mathbb{Q}_{n}:\ \operatorname{d}\mathbb{Q}_{n}=Y_{n}\operatorname{d}\mathbb{P}_{n},\ Y_{n}\in L^{q}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}),\ Y_{n}\leq_{cx}\phi_{n}(U_{n}),\ U_{n}\sim\mathcal{U}(0,1)\right\}.

The $Y_{n},$ are indeed densities. Now, (6.4) can be interpreted as the minimization of a coherent risk measure $\rho$

\displaystyle\inf_{\pi\in\Pi^{M}}\rho\Big{(}\sum_{n=0}^{N-1}c_{n}(X_{n},d_{n}(X_{n}),X_{n+1})+c_{N}(X_{N})\Big{)}

(6.5)

and the problem can be solved with the value iteration

J_{n}(x)=\inf_{a\in D_{n}(x)}\rho_{n}\Big{(}c_{n}(x,a,T_{n}(x,a,Z_{n+1}))+J_{n+1}(T_{n}(x,a,Z_{n+1}))\Big{)}

where $\rho_{n}(X)=\sup_{Y\in\mathcal{Q}_{n+1}^{d}}\mathbb{E}[XY]$ and $J_{0}(x)$ gives the minimal value (6.4).

Remark 6.9.

Some authors already considered the problem of optimizing risk measures of dynamic decision processes. For example [ruszczynski2010risk] considered Markov risk measures for finite and discounted infinite horizon models. In the final section he briefly discusses the relation to min-max problems where player 2 chooses the measure. [shen2013risk] treat similar problems (also with average cost) with different properties of the risk maps. More specific applications (dividend problem and economic growth) with the recursive entropic risk measures are treated in [BaeuerleJaskiewicz2017, BaeuerleJaskiewicz2018]. In [chow2015risk] the authors treat the dynamic average-value at risk as a min-max problem. For this risk measure there are also alternative ways for the solution, see e.g. [BaeuerleOtt2011],

7. Application

7.1. LQ Problem

We consider here so-called linear-quadratic (LQ) problems. The state and action space are $E=\mathbb{R}$ and $A=\mathbb{R}^{d}$ . Let $U_{1},\dots,U_{n}$ , $V_{1},\dots,V_{N}$ be $\mathbb{R}$ - and $\mathbb{R}^{d}$ -valued random vectors, respectively, and $W_{1},\dots,W_{N}$ be random variables with values in $\mathbb{R}$ . The random elements $\{Z_{n}=(U_{n},V_{n},W_{n})\}_{1\leq n\leq N}$ are independent and the $n$ -th element is defined on $(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ . It is supposed that the disturbances $\{Z_{n}\}_{1\leq n\leq N}$ have finite $2p$ -th moments, $p\geq 1$ . The transition function is given by

T_{n}(x,a,Z_{n+1})=U_{n+1}x+V_{n+1}^{\top}a+W_{n+1}

for $n=0,\dots,N-1$ . Furthermore, let there be deterministic positive constants $Q_{0},\dots,Q_{N}\in\mathbb{R}_{+}$ and deterministic positive definite symmetric matrices $R_{0},\dots,R_{N-1}\in\mathbb{R}^{d\times d}$ . The one-stage cost functions are

c_{n}(x,a,x^{\prime})=c_{n}(x,a)=x^{2}Q_{n}+a^{\top}R_{n}a

and the terminal cost function is $c_{N}(x)=x^{2}Q_{N}$ . Hence, the optimization problem under consideration is

\displaystyle\inf_{\pi\in\Pi^{R}}\sup_{\gamma\in\Gamma}\ \mathbb{E}_{0x}^{\pi\gamma}\left[\sum_{k=0}^{N-1}X_{k}^{2}Q_{k}+A_{k}^{\top}R_{k}A_{k}+X_{N}^{2}Q_{N}\right].

(7.1)

Policy values and value functions are defined in the usual way. For different formulations of robust LQ problems, see e.g. [hansen1999five].

Since $Q_{n}$ and the matrices $R_{n}$ are positive semidefinite, $\underaccent{\bar}{b}\equiv 0$ is a lower bounding function and the one-stage costs are at least quasi-integrable. In the sequel, we will determine the value functions and optimal policy by elementary calculations and will show that the value functions are convex and therefore continuous. Hence, we can dispense with an upper bounding function and compactness of the action space.

Since the Borel $\sigma$ -algebra of a finite dimensional Euclidean space is countably generated, it is no restriction to assume that the probability measures $\mathbb{P}_{n+1}$ are separable. Further, we assume that for $n=0,\dots,N-1$

(i)

the ambiguity sets $\mathcal{Q}_{n+1}\subseteq\mathcal{M}^{q}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1})$ are norm bounded and weak* closed.
(ii)

it holds $\mathbb{E}^{\mathbb{Q}}[W_{n+1}]=0$ for all $\mathbb{Q}\in\mathcal{Q}_{n+1}$ .
(iii)

$W_{n+1}$ and $(U_{n+1},V_{n+1})$ are independent for all $\mathbb{Q}\in\mathcal{Q}_{n+1}$ , i.e. $\mathbb{Q}=\mathbb{Q}_{W_{n+1}}\otimes\mathbb{Q}_{U_{n+1},V_{n+1}}$ .

I.e. Assumption 3.1 is satisfied apart from upper bounding. Theorems 3.6 and 3.10 use the bounding, continuity and compactness assumptions only to prove the existence of optimal decision rules. Thus, we can employ the Bellman equation and restrict the consideration to Markov policies as long as we are able to prove the existence of optimal decision rules on each stage. We proceed backwards. At stage $N$ , no action has to be chosen and the value function is $J_{N}(x)=x^{2}Q_{N}$ . At stage $N-1$ , we have to solve the Bellman equation

$\displaystyle J_{N-1}(x)$	$\displaystyle=\inf_{a\in A}\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}c_{N-1}(x,a)+\mathbb{E}^{\mathbb{Q}}\left[J_{N}(T(x,a,Z_{n+1}))\right]$	(7.2)
	$\displaystyle=\inf_{a\in A}\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}x^{2}Q_{N-1}+a^{\top}R_{N-1}a+\mathbb{E}^{\mathbb{Q}}\left[(U_{N}x+V_{N}^{\top}a+W_{N})^{2}Q_{N}\right]$
	$\displaystyle=\inf_{a\in A}\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}x^{2}Q_{N-1}+a^{\top}R_{N-1}a+\mathbb{E}^{\mathbb{Q}}\left[x^{2}U_{N}^{2}+(V_{N}^{\top}a)^{2}\right.\left.+2xU_{N}V_{N}^{\top}a+W_{N}^{2}\right]Q_{N}$

For the last equality we used that $\mathbb{E}^{\mathbb{Q}}\left[2W_{N}(U_{N}x+V_{N}a)\right]=0$ by assumption. Since $R_{N-1}$ and $Q_{N}$ are positive (semi-) definite, the objective function (7.2) is strictly convex in $a$ . Moreover, it is linear and especially concave in $\mathbb{Q}$ . Finally, $\mathcal{Q}_{N}$ is weak* compact by the Theorem of Banach-Alaoglu [AliprantisBorder2006, 6.21] the objective function (7.2) is continuous in $\mathbb{Q}$ by definition of the weak* topology since the integrand is in $L^{p}(\Omega_{n+1},\mathcal{A}_{n+1},\mathbb{P}_{n+1})$ . Thus, the requirements of Sion’s Minimax Theorem LABEL:thm:A:minimax b) are satisfied and we can interchange infimum and supremum in (7.2), i.e.

	$\displaystyle J_{N-1}(x)$	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}\inf_{a\in A}x^{2}Q_{N-1}+a^{\top}R_{N-1}a+x^{2}\mathbb{E}^{\mathbb{Q}}[U_{N}^{2}]Q_{N}+a^{\top}\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]aQ_{N}$
		$\displaystyle\phantom{=\inf_{a\in A}\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}}\ +2xQ_{N}\mathbb{E}^{\mathbb{Q}}[U_{N}V_{N}^{\top}]a+\mathbb{E}^{\mathbb{Q}}[W_{N}^{2}]Q_{N}$		(7.3)

In order to solve the inner minimization problem it suffices due to strict convexity and smoothness to determine the unique zero of the gradient of the objective function.

		$\displaystyle 0=2R_{N-1}a+2\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]aQ_{N}+2x\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}U_{N}]Q_{N}$
	$\displaystyle\Longleftrightarrow\quad$	$\displaystyle a=-\big{(}R_{N-1}+\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]Q_{N}\big{)}^{-1}\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}U_{N}]Q_{N}x.$

Note that the matrix $\big{(}R_{N-1}+\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]\big{)}Q_{N}$ is positive definite and therefore invertible due to the positive (semi-) definiteness of $R_{N-1}$ and $Q_{N}$ . Inserting in (7.1) gives

$\displaystyle J_{N-1}(x)$	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}\mathbb{E}^{\mathbb{Q}}[W_{N}^{2}]Q_{N}+x^{2}\Big{(}Q_{N-1}+\mathbb{E}^{\mathbb{Q}}[U_{N}^{2}]Q_{N}$
	$\displaystyle\phantom{=\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}}\ -\mathbb{E}^{\mathbb{Q}}[U_{N}V_{N}]\Big{(}R_{N-1}+\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]Q_{N}\Big{)}^{-1}\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}U_{N}]Q_{N}^{2}\Big{)}$
	$\displaystyle=\sup_{\mathbb{Q}\in\mathcal{Q}_{N}}\mathbb{E}^{\mathbb{Q}}[W_{N}^{2}]Q_{N}+x^{2}K_{N-1}^{\mathbb{Q}}=\sup_{\mathbb{Q}_{W_{N}}}\mathbb{E}^{\mathbb{Q}}[W_{N}^{2}]Q_{N}+x^{2}\sup_{\mathbb{Q}_{U_{N},V_{N}}}K_{N-1}^{\mathbb{Q}}$	(7.4)

where

\displaystyle K_{N-1}^{\mathbb{Q}}

\displaystyle=Q_{N-1}+\mathbb{E}^{\mathbb{Q}}[U_{N}^{2}]Q_{N}-\mathbb{E}^{\mathbb{Q}}[U_{N}^{\top}V_{N}]\Big{(}R_{N-1}+\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}V_{N}]Q_{N}\Big{)}^{-1}\mathbb{E}^{\mathbb{Q}}[V_{N}^{\top}U_{N}]Q_{N}^{2}.

Since $J_{n}(x)\geq 0$ for all $x\in\mathbb{R}$ we must have $K_{N-1}^{\mathbb{Q}}>0$ and since $\mathcal{Q}_{N}$ is weak* compact and $\mathbb{Q}\mapsto\mathbb{E}^{\mathbb{Q}}[W_{N}^{2}]Q_{N}+x^{2}K_{N-1}^{\mathbb{Q}}$ weak* continuous, there exists an optimal measure $\gamma_{N-1}(x)=\mathbb{Q}^{*}_{N}=\mathbb{Q}^{*}_{W_{N}}\otimes\mathbb{Q}^{*}_{U_{N},V_{N}}$ which is independent of $x$ due to our independence assumption (iii). Since $J_{N-1}$ is again quadratic we obtain when we define

	$\displaystyle K_{n-1}^{\mathbb{Q}}$	$\displaystyle=Q_{n-1}+K_{n}^{\mathbb{Q}}\Big{(}\mathbb{E}^{\mathbb{Q}}[U_{n}^{2}]-\mathbb{E}^{\mathbb{Q}}[U_{n}^{\top}V_{n}]\Big{(}R_{n-1}/K_{n}^{\mathbb{Q}}+\mathbb{E}^{\mathbb{Q}}[V_{n}^{\top}V_{n}]\Big{)}^{-1}\mathbb{E}^{\mathbb{Q}}[V_{n}^{\top}U_{n}]\Big{)}$
	$\displaystyle L_{n-1}^{\mathbb{Q}}$	$\displaystyle=-\Big{(}R_{n-1}/K_{n}^{\mathbb{Q}}+\mathbb{E}^{\mathbb{Q}}[V_{n}^{\top}V_{n}]\Big{)}^{-1}\mathbb{E}^{\mathbb{Q}}[V_{n}^{\top}U_{n}]$

that $\gamma^{*}_{n}(x)\equiv\gamma^{*}_{n}=\operatorname{argmax}_{\mathbb{Q}_{W_{n}}}\mathbb{E}^{\mathbb{Q}}[W_{n}^{2}]\otimes\operatorname{argmax}_{\mathbb{Q}_{U_{n},V_{n}}}K_{n}^{\mathbb{Q}}$ and $d_{n}^{*}(x)=L_{n}^{\gamma^{*}_{n}}x$ . Since the third term of $K_{n-1}^{\mathbb{Q}}$ is a quadratic form nature should choose $\mathbb{Q}$ such that $\mathbb{E}^{\mathbb{Q}}[V_{n}^{\top}U_{n}]=0$ if possible and maximize the second moment of $U_{n}$ . If this is possible, we obtain $d_{n}^{*}(x)=0$ , i.e. the controller will not control the system. In any case we see here the optimal choice of nature $\gamma^{*}_{n}(x)$ does not depend on $x$ .

When we specialize the situation to $d=1$ we obtain

\displaystyle K_{n-1}^{\mathbb{Q}}

\displaystyle=Q_{n-1}+\Big{(}\mathbb{E}^{\mathbb{Q}}[U_{n}^{2}]-\frac{(\mathbb{E}^{\mathbb{Q}}[U_{n}V_{n}]^{2}}{\frac{R_{n-1}}{K_{n}^{\mathbb{Q}}}+\mathbb{E}^{\mathbb{Q}}[V_{n}^{2}]}\Big{)}K_{n}^{\mathbb{Q}}.

Thus, nature has to maximize the expression in brackets. For a moment we skip the index $n$ . Let us further assume that $(U,V)$ is jointly normally distributed with expectations $\mu_{U}$ and $\mu_{V}$ and variances $\sigma^{2}_{U}$ and $\sigma^{2}_{V}$ and covariance $\sigma_{U,V}$ and that all these parameters may be elements of compact intervals. Then the expression in brackets reduces to

\sigma_{U}^{2}+\mu_{U}^{2}-\frac{(\sigma_{UV}+\mu_{U}\mu_{V})^{2}}{\frac{R}{K^{\mathbb{Q}}}+\sigma_{V}^{2}+\mu_{V}^{2}}.

We see immediately that both $\sigma_{V}^{2}$ and $\sigma_{U}^{2}$ have to be chosen as maximal possible value. The remaining three parameters $\mu_{U},\mu_{V}$ and $\sigma_{UV}$ have to minimize the fraction. If it is possible to choose them such that $\mu_{U}$ is maximal and $\sigma_{UV}+\mu_{U}\mu_{V}=0$ this would be optimal.

7.2. Managing regenerative energy

The second example is the management of a joint wind and storage facility. Before each period the owner of the wind turbine has to announce the amount $a$ of energy she wants to produce. If there is enough wind in the next period she receives the reward $Pa$ where we assume that $P>0$ is the fixed price for energy. Additional energy which may have been produced will be stored in a battery with capacity $K>0$ . If there is not enough wind in the next period, the storage device will be used to cover the shortage. In case this is still not enough, the remaining shortage will be penalized by a proportional cost rate $c>0$ (see [anderson2015optimal] for further background). We consider a robust version here, i.e. the distribution $\mathbb{Q}$ of the produced wind energy varies in a set $\mathcal{Q}$ with bounded support $[0,B]$ . The state is the amount of energy in the battery, hence $E=[0,K]$ . Further $A=[0,B]=D(x)$ and the action is the amount of energy which is bid. We obtain the following Bellman equation:

$\displaystyle J_{n}(x)$	$\displaystyle=$	$\displaystyle\inf_{a\in D(x)}\sup_{\mathbb{Q}\in\mathcal{Q}}\Big{\{}\int_{a}^{B}-aP+J_{n+1}((x+z-a)\wedge K)\mathbb{Q}(dz)$
		$\displaystyle+\int_{0}^{a}-(a\wedge(z+x))P+(a-z-x)^{+}c+J_{n+1}((x+z-a)^{+})\mathbb{Q}(dz)\Big{\}}$
	$\displaystyle=$	$\displaystyle\inf_{a\in D(x)}\sup_{\mathbb{Q}\in\mathcal{Q}}\Big{\{}-aP+\int_{a}^{B}J_{n+1}((x+z-a)\wedge K)\mathbb{Q}(dz)$
		$\displaystyle+\int_{0}^{a}(P+c)(x+z-a)^{-}+J_{n+1}((x+z-a)^{+})\mathbb{Q}(dz)\Big{\}}$

From the last representation we see that

T(x,a,z)=\left\{\begin{array}[]{ll}(x+z-a)\wedge K),&z\geq a\\ (x+z-a)^{+},&0\leq z\leq a\end{array}\right.

and

c(x,a,T(x,a,z))=-aP+\left\{\begin{array}[]{ll}0,&z\geq a\\ (P+c)(x+z-a)^{-},&0\leq z\leq a\end{array}\right.

We see that $D(x)$ is compact and $x\mapsto D(x)$ is lower semicontinuous. $T$ is continuous and $c$ is continuous and bounded. It is easy to see that $J_{n}(x)$ is decreasing in $x$ . Suppose $\mathbb{Q}$ has a minimal element $\mathbb{Q}^{*}$ w.r.t. $\leq_{st}$ . Then we can omit the $\sup_{\mathbb{Q}\in\mathcal{Q}}$ and replace $\mathbb{Q}$ by $\mathbb{Q}^{*}$ . The remaining Bellman equation is then a standard MDP.

8. Appendix

8.1. Additional Proofs

Proof of Lemma 2.3:

Recall that we identify $\mathcal{Q}_{n}$ with the set of the corresponding densities $\mathcal{Q}_{n}^{d}$ . The closure $\overline{\mathcal{Q}}_{n}^{d}$ of $\mathcal{Q}_{n}^{d}$ remains norm bounded. This can be seen as follows: Let $X\in\overline{\mathcal{Q}}_{n}^{d}$ . Then there exists a net $\{X_{\alpha}\}_{\alpha\in I}\subseteq\mathcal{Q}_{n}^{d}$ such that $X_{\alpha}$ [XY] for all Y ∈L^p( Ω_n, A_n, P_n ) with ∥Y∥_L^p=1. By Hölder’s inequality we have for all $\alpha\in I$

\left|\mathbb{E}[X_{\alpha}Y]\right|\leq\mathbb{E}|X_{\alpha}Y|\leq\|X_{\alpha}\|_{L^{q}}\|Y\|_{L^{p}}=\|X_{\alpha}\|_{L^{q}}\leq K.

Thus, $|\mathbb{E}[XY]|\leq K$ . Finally, due to duality it follows

\|X\|_{L^{q}}=\sup_{\|Y\|_{L^{p}}=1}|\mathbb{E}[XY]|\leq K.

The separability of the probability measure $\mathbb{P}_{n}$ makes $L^{p}(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n})$ a separable Banach space. Consequently, the weak* topology is metrizable on the norm bounded set $\overline{\mathcal{Q}}_{n}^{d}$ [Morrison2001, p. 157]. The trace topology on the subset $\mathcal{Q}_{n}^{d}\subseteq\overline{\mathcal{Q}}_{n}^{d}$ coincides with the topology induced by the restriction of the metric [OSearcoid2007, 4.4.1], i.e. $\mathcal{Q}_{n}^{d}$ is metrizable, too.

Since $\overline{\mathcal{Q}}_{n}^{d}$ is norm bounded and weak* closed, the Theorem of Banach-Alaoglu [AliprantisBorder2006, 6.21] yields that it is weak* compact. As a compact metrizable space $\overline{\mathcal{Q}}_{n}^{d}$ is complete [AliprantisBorder2006, 3.28] and also separable [AliprantisBorder2006, 3.26, 3.28]. Hence, $\overline{\mathcal{Q}}_{n}^{d}$ is a Borel Space. The set of densities $\mathcal{Q}_{n}^{d}$ is also separable as a subspace of a separable metrizable space [AliprantisBorder2006, 3.5]. $\Box$

	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(X_{0}\in B)$	$\displaystyle=\delta_{x}(B),$
	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(A_{n}\in C\|H_{n}=h_{n})$	$\displaystyle=\pi_{n}(C\|h_{n}),$
	$\displaystyle\mathbb{Q}^{\pi\gamma}_{x}(X_{n+1}\in B\|(H_{n},A_{n})=(h_{n},a_{n}))$	$\displaystyle=Q_{n}^{\gamma}(B\|h_{n},a_{n})$