Distributionally robust stochastic optimal control

Consider the Stochastic Optimal Control (SOC) (discrete time, finite horizon) model (e.g., [1]):

where $\Pi$ is the set of polices satisfying the constraints

Here variables $x_{t}\in{\mathbb{R}}^{n_{t}}$, $t=1,...,T+1$, represent the state of the system, $u_{t}\in{\mathbb{R}}^{m_{t}}$, $t=1,...,T$, are controls, $\xi_{t}\in\Xi_{t}$, $t=1,...,T$, are random vectors, $\Xi_{t}$ is a closed subset of ${\mathbb{R}}^{d_{t}}$, $f_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}$, $t=1,...,T$, are cost functions, $c_{T+1}(x_{T+1})$ is a final cost function, $F_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}^{n_{t+1}}$ are (measurable) mappings and ${\cal U}_{t}$ is a (nonempty) subset of ${\mathbb{R}}^{m_{t}}$. Values $x_{1}$ and $\xi_{0}$ are deterministic (initial conditions); it is also possible to view $x_{1}$ as random with a given distribution, this is not essential for the following discussion.

• •

  Unless stated otherwise we assume that the probability law of the random process $\xi_{1},...,\xi_{T}$ does not depend on our decisions.

The optimization in (1.1) is performed over policies $\pi\in\Pi$ determined by decisions $u_{t}$ and state variables $x_{t}$ considered as functions of $\xi_{[t-1]}=(\xi_{1},...,\xi_{t-1})$, $t=1,...,T$, and satisfying the feasibility constraints (1.2). We also denote $\Xi_{[t]}:=\Xi_{1}\times\cdots\times\Xi_{t}$. For the sake of simplicity, in order not to distract from the main message of the paper, we assume that the control sets ${\cal U}_{t}$ do not depend on $x_{t}$. It is possible to extend the analysis to the general case, where the control sets are functions of the state variables.

Consider Banach space $C(\Xi_{t})$ of continuous functions $\phi:\Xi_{t}\to{\mathbb{R}}$ equipped with the sup-norm $\|\phi\|_{\infty}=\sup_{\xi\in\Xi_{t}}|\phi(\xi)|$. The dual space of $C(\Xi_{t})$ is the space of finite signed measures on $\Xi_{t}$ with respect to the bilinear form $\langle\phi,\gamma\rangle=\int\phi d\gamma$ (Riesz representation).

The risk neutral SOC model (1.1) was thoroughly investigated. On the other hand, the analysis of its distributionally robust counterpart is more involved. The distributionally robust approach to Markov Decision Processes (MDPs) can be traced back to [7] and [10]. The origins of distributional robustness can be also related to the dynamic game theory (e.g., [8] and references there in). By duality arguments the distributionally robust formulations are closely related to the risk averse settings. The aim of this paper is to describe and formulate certain related questions in the framework of the SOC model. In particular we consider randomized policies and give necessary and suffcient conditions for existence of non-randomized optimal policies. We also discuss a relation between the nested risk averse and game formulations of distributionally robust problems.

In the distributionally robust counterpart of the risk neutral SOC problem (1.1) it is assumed that the probability law of the data process $\xi_{t}$ is not specified exactly, but rather is a member of a specified so-called ambiguity set of probability distributions. This modeling concept could be applied in various contexts, such as the Inventory Model discussed in Section 4, where the order quantity must be determined in the presence of uncertain demand distributions. Specifically, consider the setting where there is ambiguity set ${\cal P}_{t}^{\xi_{[t-1]}}$ of probability measures on $\Xi_{t}$, depending on the history $\xi_{[t-1]}=(\xi_{1},...,\xi_{t-1})$ (cf., [11]). That is, ${\cal P}_{t}^{\xi_{[t-1]}}={\mathbb{M}}_{t}(\xi_{[t-1]})$, where ${\mathbb{M}}_{t}:\Xi_{[t-1]}\rightrightarrows{\mathfrak{M}}_{t}$ is the respective multifunction. Here ${\mathbb{M}}_{1}(\cdot)\equiv{\cal P}_{1}$ for some pre-determined ${\cal P}_{1}\subset{\mathfrak{M}}_{1}$.

We view the distributionally robust counterpart of problem (1.1) as a dynamic game between the decision maker (the controller) and the adversary (the nature). Define history of the decision process as

At stage $t=1,...,T$, based on $\mathfrak{h}_{t}$ the nature chooses a probability measure $P_{t}\in{\cal P}_{t}^{\xi_{[t-1]}}$, at the same time the controller chooses its action $u_{t}\in{\cal U}_{t}$. For a realization of $\xi_{t}\sim P_{t}$, the next state $x_{t+1}=F_{t}(x_{t},u_{t},\xi_{t})$ and so on the process is continued. (It is also possible to let the ambiguity set ${\cal P}_{t}^{\xi_{[t-1]}}$ depend on the past actions $u_{[t-1]}=(u_{1},\ldots,u_{t-1})$; this does not change the essence of our discussion for the dynamic game.) We write the corresponding distributionally robust problem as

where $\Pi$ is the set of polices of the controller and $\Gamma$ is the set of policies of the nature (cf., [13, p. 812]).

Unless stated otherwise we make the following assumptions about ${\cal U}_{t},\Xi_{t},f_{t},F_{t}$.

The dynamic equations of the dual of problem (2.9) are: $Q_{T+1}(x_{T+1},\xi_{[T]})=f_{T+1}(x_{T+1})$ for all $\xi_{[T]}\in\Xi_{[T]}$, and for $t=T,...,1$,

For a given $P_{t}$ (and $x_{t}$) the maximization in the right hand side of (3.1) is over all probability measures $\mu_{t}$ supported on the set $\Xi_{t}$. It is straightforward to see that the maximum is attained at Dirac measure²²2We denote by $\delta_{a}$ the Dirac measure of mass one at point $a$. which depends on $u_{t}$. Therefore it suffices to perform the minimization in (3.1) over Dirac measures $\mu_{t}=\delta_{u_{t}}$, and hence we can write equation (3.1) in the following equivalent way

Similar to Proposition 2.2, it can be shown that the value functions $Q_{t}(\cdot)$ are well-defined and continuous. By the standard theory of min-max, we have that $Q_{t}(\cdot)\leq V_{t}(\cdot)$. We next establish that equality indeed holds when the multifunctions ${\mathbb{M}}_{t}$, $t=1,...,T$, are convex-valued, i.e., the sets ${\cal P}_{t}^{\xi_{[t-1]}}={\mathbb{M}}_{t}(\xi_{[t-1]})$ are convex for all $\xi_{[t-1]}$.

It could be worth mentioning here that the duality of the game formulation (when considering randomized policies $\widehat{\Pi}$ of the controller) does not require the convexity of ${\cal U}_{t}$ or any assumptions on the transition functions $F_{t}$.

We have the following necessary and sufficient condition for the existence of a non-randomized optimal policy of the controller (cf., [9, Theorem 2.2]).

In particular, we have the following result (cf., [5]).

In many interesting applications the considered problem is convex in the sense of Corollary 4.1. In such cases there is no point of considering randomized policies. As an example consider the classical Inventory Model (cf., [18]).

There are several ways how the ambiguity sets can be constructed. We discuss now an approach which can be considered as an extension of the risk averse modeling of multistage stochastic programs.

Let ${\mathbb{P}}$ be a probability measure on a (closed) set $\Xi\subset{\mathbb{R}}^{d}$, and ${\cal P}$ be a set of probability measures on $\Xi$ absolutely continuous with respect to ${\mathbb{P}}$. Consider the corresponding distributionally robust functional

defined on an appropriate space ${\cal Z}$ of random variables $Z:\Xi\to{\mathbb{R}}$. Such functional can be considered as a coherent risk measure (e.g., [14, Chapter 6]). The functional ${\cal R}$ is law invariant if ${\cal R}(Z)={\cal R}(Z^{\prime})$ when $Z$ and $Z^{\prime}$ are distributionally equivalent, i.e., ${\mathbb{P}}(Z\leq z)={\mathbb{P}}(Z^{\prime}\leq z)$ for any $z\in{\mathbb{R}}$. The law invariant coherent risk measure can be considered as a function of the cumulative distribution function (cdf) $H_{Z}(z):={\mathbb{P}}(Z\leq z)$.

An important example of law invariant coherent risk measure is the Average Value-at-Risk