{'fraction_non_alphanumeric': 0.05200303984366518, 'fraction_numerical': 0.013474227674640226, 'mean_word_length': 4.167040638244827, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 72, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
From Data to Decisions: Distributionally Robust Optimization is Optimal

We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, i.e., a predictor, and an optimizer of the estimated cost function that serves as a near-optimal candidate decision, i.e., a prescriptor. As functions of the data, predictors and prescriptors constitute statistical estimators. We propose a meta-optimization problem to find the least conservative predictors and prescriptors subject to constraints on their out-of-sample disappointment. The out-of-sample disappointment quantifies the probability that the actual expected cost of the candidate decision under the unknown true distribution exceeds its predicted cost. Leveraging tools from large deviations theory, we prove that this meta-optimization problem admits a unique solution: The best predictor-prescriptor pair is obtained by solving a distributionally robust optimization problem over all distributions within a given relative entropy distance from the empirical distribution of the data.


Introduction
We study static decision problems under uncertainty, where the decision maker cannot observe the probability distribution of the uncertain problem parameters but has access to a finite number of independent samples from this distribution. Classical stochastic programming uses this data only indirectly. The data serves as the input for a statistical estimation problem that aims to infer the distribution of the uncertain problem parameters. The estimated distribution then serves as an input for an optimization problem that outputs a near-optimal decision as well as an estimate of the expected cost incurred by this decision. Thus, classical stochastic programming separates the decision-making process into an estimation phase and a subsequent optimization phase. The estimation method is typically selected with the goal to achieve maximum prediction accuracy but without tailoring it to the optimization problem at hand.
In this paper we develop a method of data-driven stochastic programming that avoids the artificial decoupling of estimation and optimization and that chooses an estimator that adapts to the underlying optimization problem. Specifically, we model data-driven solutions to a stochastic program through a predictor and its corresponding prescriptor. For any fixed feasible decision, the predictor maps the observable data to an estimate of the decision's expected cost. The prescriptor, on the other hand, computes a decision that minimizes the cost estimated by the predictor.
The set of all possible predictors and their induced prescriptors is vast. Indeed, there are countless possibilities to estimate the expected costs of a fixed decision from data, e.g., via the popular sample average approximation (Shapiro et al. 2014, Chapter 5), by postulating a parametric model for the exogenous uncertainties and estimating its parameters via maximum likelihood estimation (Dupačová and Wets 1988), or through kernel density estimation (Parpas et al. 2015). Recently, it has become fashionable to construct conservative (pessimistic) estimates of the expected costs via methods of distributionally robust optimization. In this setting, the available data is used to generate an ambiguity set that represents a confidence region in the space of probability distributions and contains the unknown data-generating distribution with high probability. The expected cost of a fixed decision under the unknown true distribution is then estimated by the worst-case expectation over all distributions in the ambiguity set. Since the ambiguity set constitutes a confidence region for the unknown true distribution, the worst-case expectation represents an upper confidence bound on the true expected cost. The ambiguity set can be defined, for example, through confidence intervals for the distribution's moments (Delage and Ye 2010). Alternatively, the ambiguity set may contain all distributions that achieve a prescribed level of likelihood (Wang et al. 2016), that pass a statistical hypothesis test (Bertsimas et al. 2018a) or that are sufficiently close to a reference distribution with respect to a probability metric such as the Prokhorov metric (Erdogan and Iyengar 2006), the Wasserstein distance (Pflug and Wozabal 2007, Mohajerin Esfahani and Kuhn 2018, Zhao and Guan 2018, the total variation distance (Sun and Xu 2016) or the L 1 -norm (Jiang and Guan 2018). Ben-Tal et al. (2013) have shown that confidence sets for distributions can also be constructed using φ-divergences such as the Pearson divergence, the Burg entropy or the Kullback-Leibler divergence. More recently, Bayraksan and Love (2015) provide a systematic classification of φ-divergences and investigate the richness of the corresponding ambiguity sets.
Given the numerous possibilities for constructing predictors from a given dataset, it is easy to lose oversight. In practice, predictors are often selected manually from within a small menu with the goal to meet certain statistical and/or computational requirements. However, there are typically many different predictors that exhibit the desired properties, and there always remains some doubt as to whether the chosen predictor is best suited for the particular decision problem at hand. In this paper we propose a principled approach to data-driven stochastic programming by solving a meta-optimization problem over a rich class of predictor-prescriptor-pairs including, among others, all examples reviewed above. This meta-optimization problem aims to find the least conservative (i.e., pointwise smallest) prescriptor whose out-of-sample disappointment decays at a prescribed exponential rate r as the sample size tends to infinity-irrespective of the true data-generating distribution. The out-of-sample disappointment quantifies the probability that the actual expected cost of the prescriptor exceeds its predicted cost. Put differently, it represents the probability that the predicted cost of a candidate decision is over-optimistic and leads to disappointment in out-of-sample tests. Thus, the proposed meta-optimization problem tries to identify the predictorprescriptor-pairs that overestimate the expected out-of-sample costs by the least amount possible without risking disappointment under any thinkable data-generating distribution.
Our main results can be summarized as follows.
• By leveraging Sanov's theorem from large deviations theory, we prove that the metaoptimization problem admits a unique optimal solution for any given stochastic program.
• We show that the optimal data-driven predictor estimates the expected costs under the unknown true distribution by a worst-case expectation over all distributions within a given relative entropy distance from the empirical distribution of the data. This suggests that, among all possible data-driven solutions, a distributionally robust approach based on a relative entropy ambiguity set is optimal. This is perhaps surprising because the meta-optimization problem does not impose any structure on the predictors, which are generic functions of the data. In particular, there is no requirement forcing predictors to admit a distributionally robust interpretation.
• In contrast to most of the existing work on data-driven distributionally robust optimization, our relative entropy ambiguity set does not play the role of a confidence region that contains the unknown data-generating distribution with a prescribed level of probability (see the discussions of (Lam 2016b, Gupta 2015 below for exceptions). Instead, the radius of the relative entropy ambiguity set coincides with the desired exponential decay rate r of the out-of-sample disappointment imposed by the meta-optimization problem.
• We prove that the optimal (distributionally robust) predictor admits a dual representation as the optimal value of a one-dimensional convex optimization problem that can be solved highly efficiently. For continuously distributed problem parameters this representation seems to be new.
To our best knowledge, we are the first to recognize the optimality of distributionally robust optimization in its ability to transform data to predictors and prescriptors. The optimal distributionally robust predictor identified in this paper can be evaluated by solving a tractable convex optimization problem. Under standard convexity assumptions about the feasible set and the cost function of the stochastic program, the corresponding optimal prescriptor can also be evaluated in polynomial time. Although perhaps desirable, the tractability and distributionally robust nature of the optimal predictor-prescriptor-pair are not dictated ex ante but emerge naturally.
Relative entropy ambiguity sets have already attracted considerable interest in distributionally robust optimization (Ben-Tal et al. 2013, Calafiore 2007, Hu and Hong 2013, Lam 2016b, Wang et al. 2016. Note, however, that the relative entropy constitutes an asymmetric distance measure between two distributions. The asymmetry implies, among others, that the first distribution must be absolutely continuous to the second one but not vice versa. Thus, ambiguity sets can be constructed in two different ways by designating the reference distribution either as the first or as the second argument of the relative entropy. All papers listed above favor the second option, and thus the emerging ambiguity sets contain only distributions that are absolutely continuous to the reference distribution. Maybe surprisingly, the optimal predictor resulting from our meta-optimization problem uses the reference distribution as the first argument of the relative entropy instead. Thus, the reference distribution is absolutely continuous to every distribution in the emerging ambiguity set. Relative entropy balls of this kind have previously been studied by Gupta (2015), Lam (2016a) and Bertsimas et al. (2018b).
Adopting a Bayesian perspective, Gupta (2015) determines the smallest ambiguity sets that contain the unknown data-generating distribution with a prescribed level of confidence as the sample size tends to infinity. Both Pearson divergence and relative entropy ambiguity sets with properly scaled radii are optimal in this setting. In the terminology of the present paper, Gupta (2015) thus restricts attention to the subclass of distributionally robust predictors and operates with an asymptotic notion of optimality. The meta-optimization problem proposed here entails a stronger notion of optimality, under which the distributionally robust predictor with relative entropy ambiguity set emerges as the unique optimizer. Lam (2016a) also seeks distributionally robust predictors that trade conservatism for out-of-sample performance. He studies the probability that the estimated expected cost function dominates the actual expected cost function uniformly across all decisions, and he calls a predictor optimal if this probability is asymptotically equal to a prescribed confidence level. Using the empirical likelihood theorem of Owen (1988), he shows that Pearson divergence and relative entropy ambiguity sets with properly scaled radii are optimal in this sense. This notion of optimality has again an asymptotic flavor in the sense that it refers to sequences of ambiguity sets that converge to a singleton, and it admits multiple optimizers.
The rest of the paper unfolds as follows. Section 2 provides a formal introduction to data-driven stochastic programming on finite state spaces and develops the meta-optimization problem for identifying the best predictor-prescriptor-pair. Section 3 reviews weak and strong large deviation principles, which are then used in Section 4 to determine the unique optimal solution of the metaoptimization problem. An extension to continuous state spaces is discussed in Section 5.
Notation: The natural logarithm of p ∈ + is denoted by log(p), where we use the conventions 0 log(0/p) = 0 for any p ≥ 0 and p log(p /0) = ∞ for any p > 0. A function f : P → X from P ⊆ d to X ⊆ n is called quasi-continuous at P ∈ P if for every > 0 and neighborhood U ⊆ P of P there is a non-empty open set V ⊆ U with |f (P) − f (Q)| ≤ for all Q ∈ V . Note that V does not necessarily contain P. For any logical statement E, the indicator function 1 E evaluates to 1 if E is true and to 0 otherwise.

Data-driven stochastic programming
Stochastic programming is a powerful modeling paradigm for taking informed decisions in an uncertain environment. A generic single-stage stochastic program can be represented as (1) Here, the goal is to minimize the expected value of a cost function γ(x, ξ) ∈ , which depends both on a decision variable x ∈ X and a random parameter ξ ∈ Ξ governed by a probability distribution P . We will assume that the cost γ(x, ξ) is continuous in x for every fixed ξ ∈ Ξ, the feasible set X ⊆ n is compact, and Ξ = {1, . . . , d} is finite. Thus, ξ has d distinct scenarios that are represented-without loss of generality-by the integers 1, . . . , d. We will relax this requirement in Section 5, where Ξ will be modeled as an arbitrary compact subset of d . A wide spectrum of decision problems can be cast as instances of (1). Shapiro et al. (2014) point out, for example, that (1) can be viewed as the first stage of a two-stage stochastic program, where the cost function γ(x, ξ) embodies the optimal value of a subordinate second-stage problem. Alternatively, problem (1) may also be interpreted as a generic learning problem in the spirit of statistical learning theory.
In the following, we distinguish the prediction problem, which merely aims to predict the expected cost associated with a fixed decision x, and the prescription problem, which seeks to identify a decision x that minimizes the expected cost across all x ∈ X.
Any attempt to solve the prescription problem seems futile unless there is a procedure for solving the corresponding prediction problem. The generic prediction problem is closely related to what Le Maître and Knio (2010) call an uncertainty quantification problem and is therefore of prime interest in its own right. Throughout the rest of the paper, we thus analyze prediction and prescription problems on equal footing.
In the what follows we formalize the notion of a data-driven solution to the prescription and prediction problems, respectively. Furthermore, we introduce the basic assumptions as well as the notation used throughout the remainder of the paper.

Data-driven predictors and prescriptors
If the distribution P of ξ is unobservable and must be estimated from a training dataset consisting of finitely many independent samples from P , we lack essential information to evaluate the expected cost of any fixed decision and to solve the stochastic program (1). The standard approach to overcome this deficiency is to approximate P with a parametric or non-parametric estimateP inferred from the samples and to minimize the expected cost underP instead of the true expected cost under P . However, if we calibrate a stochastic program to a training data set and evaluate its optimal decision on a test data set, then the resulting test performance is often disappointingeven if the two datasets are sampled independently from P . This phenomenon has been observed in many different contexts. It is particularly pronounced in finance, where Michaud (1989) refers to it as the 'error maximization effect' of portfolio optimization, and in statistics or machine learning, where it is known as 'overfitting'. In decision analysis, Smith and Winkler (2006) refer to it as the 'optimizer's curse'. Thus, when working with data instead of exact probability distributions, one should safeguard against solutions that display promising in-sample performance but lead to out-of-sample disappointment.
Initially the distribution P is only known to belong to the probability simplex P = {P ∈ d + : i∈Ξ P(i) = 1}. Over time, however, independent samples ξ t , t ∈ N, from P are revealed to the decision maker that provide increasingly reliable statistical information about P .
Any P ∈ P encodes a possible probabilistic model for the data process. Thus, by slight abuse of terminology, we will henceforth refer to the distributions P ∈ P as models and to P as the model class. Evidently, the true model P is an (albeit unknown) element of P. Next, we introduce model-based predictors and prescriptors corresponding to the stochastic program (1), where the true unknown distribution P is replaced with a hypothetical model P ∈ P. Definition 1 (model-based predictors and prescriptors). For any fixed model P ∈ P, we define the model-based predictor c(x, P) = E P [γ(x, ξ)] = i∈Ξ P(i) γ(x, i) as the expected cost of a given decision x ∈ X and the model-based prescriptor x (P) ∈ arg min x∈X c(x, P) as a decision that minimizes c(x, P) over x ∈ X. Note that the model-based predictor c(x, P) is jointly continuous in x and P because Ξ is finite and γ(x, ξ) is continuous in x for every fixed ξ ∈ Ξ. The continuity of c(x, P) then guarantees via the compactness of X that the model-based prescriptor x (P) exists for every model P ∈ P. In view of Definition 1, the stochastic program (1) can be identified with the prescription problem of computing x (P ). Similarly, the evaluation of the expected cost of a given decision x ∈ X in (1) can be identified with the prediction problem of computing c(x, P ). These prediction and prescription problems cannot be solved, however, as they depend on the unknown true model P .
If one has only access to a finite set {ξ t } T t=1 of independent samples from P instead of P itself, then it may be useful to construct an empirical estimator for P .
Definition 2 (Empirical distribution). The empirical distributionP T corresponding to the sample path {ξ t } T t=1 of length T is defined througĥ Note thatP T can be viewed as the vector of empirical state frequencies. Indeed, its i th entry records the proportion of time that the sample path spends in state i. As the samples are drawn independently, the state frequencies capture all useful statistical information about P that can possibly be extracted from a given sample path. Note also thatP T is in fact the maximum likelihood estimator of P . In the following, we will therefore approximate the unknown predictor c(x, P ) as well as the unknown prescriptor x (P ) by suitable functions of the empirical distributionP T .
Definition 3 (Data-driven predictors and prescriptors). A continuous functionĉ : X × P → is called a data-driven predictor ifĉ(x,P T ) is used as an approximation for c(x, P ). A quasi-continuous functionx : P → X is called a data-driven prescriptor if there exists a data-driven predictorĉ withx for all possible estimator realizations P ∈ P, andx(P T ) is used as an approximation for x (P ).
Every data-driven predictorĉ induces a data-driven prescriptorx. To see this, note that the 'arg min' mapping is non-empty-valued and upper semicontinuous due to Berge's maximum theorem (Berge 1963, pp. 115-116), which applies becauseĉ is continuous and X is both compact and independent of P . Corollary 4 in (Matejdes 1987), which applies because P is a Baire space and X is a metric space, thus ensures that the 'arg min' mapping admits a quasi-continuous selector, which serves as a valid data-driven prescriptor. One can show that the set of points where this quasi-continuous prescriptor is discontinuous is a meagre subset of P (Bledsoe 1952). By the Baire category theorem, the points of continuity of the data-driven prescriptor at hand are thus dense in P (Baire 1899). Thus, data-driven prescriptors in the sense of Definition 3 are 'mostly' continuous.
Example 1 (Sample average predictor). The model-based predictor c introduced in Definition 1 constitutes a simple data-driven predictorĉ = c, that is, c(x,P T ) can readily be used as a naïve approximation for c(x, P ). Note that the model-based predictor c is indeed continuous as desired. By the definition of the empirical estimator, this naïve predictor approximates c(x, P ) with which is readily recognized as the popular sample average approximation.

Optimizing over all data-driven predictors and prescriptors
The estimatesĉ(x,P T ) andx(P T ) inherit the randomness from the empirical estimatorP T , which is constructed from the (random) samples {ξ t } T t=1 . Note that the prediction and prescription problems are naturally interpreted as instances of statistical estimation problems. Indeed, data-driven prediction aims to estimate the expected cost c(x, P ) from data. Standard statistical estimation theory would typically endeavor to find a data-driven predictorĉ that (approximately) minimizes the mean squared error E |c(x, P ) −ĉ(x,P T )| 2 over some appropriately chosen class of predictorsĉ, where the expectation is taken with respect to the distribution (P ) ∞ governing the sample path and the empirical estimator. The mean squared error penalizes the mismatch between the actual cost c(x, P ) and its estimatorĉ(x,P T ). Events in which we are left disappointed (c(x, P ) >ĉ(x,P T )) are not treated differently from positive surprises (c(x, P ) <ĉ(x,P T )). In a decision-making context where the goal is to minimize costs, however, disappointments (underestimated costs) are more harmful than positive surprises (overestimated costs). While statisticians strive for accuracy by minimizing a symmetric estimation error, decision makers endeavor to limit the one-sided prediction disappointment.
Definition 4 (Out-of-sample disappointment). For any data-driven predictorĉ the probability P ∞ c(x, P) >ĉ(x,P T ) is referred to as the out-of-sample prediction disappointment of x ∈ X under model P ∈ P. Similarly, for any data-driven prescriptorx induced by a data-driven predictorĉ the probability is termed the out-of-sample prescription disappointment under model P ∈ P.
The out-of-sample prediction disappointment quantifies the probability (with respect to the sample path distribution P ∞ under some model P ∈ P) that the expected cost c(x, P) of a fixed decision x exceeds the predicted costĉ(x,P T ). Thus, the out-of-sample prediction disappointment is independent of the actual realization of the empirical estimatorP T but depends on the hypothesized model P. A similar statement holds for the out-of-sample prescription disappointment.
The main objective of this paper is to construct attractive data-driven predictors and prescriptors, which are optimal in a sense to be made precise below. We first develop a notion of optimality for data-driven predictors and extend it later to data-driven prescriptors. As indicated above, a crucial requirement for any data-driven predictor is that it must limit the out-of-sample disappointment. This informal requirement can be operationalized either in an asymptotic sense or in a finite sample sense.
(i) Asymptotic guarantee: As T grows, the out-of-sample prediction disappointment (2a) decays exponentially at a rate at least equal to r > 0 up to first order in the exponent, that is, (ii) Finite sample guarantee: For every fixed T , the out-of-sample prediction disappointment (2a) is bounded above by a known function g(T ) that decays exponentially at rate at least equal to r > 0 to first order in the exponent, that is, where lim sup T →∞ 1 T log g(T ) ≤ −r. The inequalities (3) and (4) are imposed across all models P ∈ P. This ensures that they are satisfied under the true model P , which is only known to reside within P. By requiring the inequalities to hold for all x ∈ X, we further ensure that the out-of-sample prediction disappointment is eventually small irrespective of the chosen decision. Note that the finite sample guarantee (4) is sufficient but not necessary for the asymptotic guarantee (3). Knowing the finite sample bounds g(T ) has the advantage, amongst others, that one can determine the sample complexity that is, the minimum number of samples needed to certify that the out-of-sample prediction disappointment does not exceed a prescribed significance level β ∈ [0, 1].
At first sight the requirements (3) and (4) may seem restrictive, and the existence of datadriven predictors with exponentially decaying out-of-sample disappointment may be questioned.
Below we will argue, however, that these requirements are in fact natural and satisfied by all reasonable predictors. To see this, note that if the training data is generated by P, then the empirical distributionP T converges P ∞ -almost surely to P by virtue of the strong law of large numbers. Thus, the out-of-sample disappointment of a predictorĉ withĉ(x, P) > c(x, P) must decay to 0 as T grows.
Conversely, ifĉ(x, P) < c(x, P), then the out-of-sample disappointment ofĉ must approach 1 as T tends to infinity. The following example shows that the out-of-sample disappointment generically fails to vanish asymptotically in the limiting case whenĉ(x, P) = c(x, P).
In this case, the sample average predictor approximates the expected cost c(x, P) = i∈Ξ iP(i) by its sample mean c(x,P T ) = 1 T T t=1 ξ t . As the sample size T tends to infinity, the central limit theorem implies that converges in law to a normal distribution with mean 0 and variance which means that the out-of-sample prediction disappointment remains large for all sample sizes.
The sample average predictor hence violates the asymptotic guarantee (3) and the stronger finite sample guarantee (4). Note that by adding any positive constant to the sample average predictor, we recover a predictor with exponentially decaying out-of-sample disappointment.
In the following we call a predictorĉ conservative ifĉ(x, P ) > c(x, P ) for all decisions x ∈ X and estimator realizations P ∈ P. The above discussion shows that if we require the out-ofsample disappointment to decay asymptotically, we must focus on conservative predictors. Basic results from large deviations theory further ensure that the out-of-sample disappointment of any conservative predictor necessarily decays at an exponential rate. Specifically, asymptotic guarantees of the type (3) hold whenever the empirical distributionP T satisfies a weak large deviation principle, while finite sample guarantees of the type (4) hold whenP T satisfies a strong large deviation principle. As will be shown in Section 3, the empirical distribution does satisfy weak and strong large deviation principles. One predictor that fails to be conservative is the sample average predictor.
For ease of exposition, we henceforth denote by C the set of all data-driven predictors, that is, all continuous functions that map X × P to the reals. Moreover, we introduce a partial order C on C defined throughĉ 1 Cĉ2 ⇐⇒ĉ 1 (x, P ) ≤ĉ 2 (x, P ) ∀x ∈ X, P ∈ P for anyĉ 1 ,ĉ 2 ∈ C. Thus,ĉ 1 Cĉ2 means thatĉ 1 is (weakly) less conservative thanĉ 2 . The problem of finding the least conservative predictor among all data-driven predictors whose out-of-sample disappointment decays at rate at least r > 0 can thus be formalized as the following vector optimization problem.
We highlight that the minimization in (5) is understood with respect to the partial order C . Thus, the relationĉ 1 Cĉ2 between two feasible decision means thatĉ 1 is weakly preferred toĉ 2 . However, not all pairs of feasible decisions are comparable, that is, it is possible that bothĉ 1 Cĉ2 and c 2 Cĉ1 . A predictorĉ is a strongly optimal solution for (5) if it is feasible and weakly preferred to every other feasible solution (i.e., everyĉ =ĉ feasible in (5) satisfiesĉ Cĉ ). Similarly,ĉ is a weakly optimal solution for (5) if it is feasible and if every other solution preferred toĉ is infeasible (i.e., everyĉ =ĉ withĉ Cĉ is infeasible in (5)). While vector optimization problems can have many weak solutions, we point out that strong solutions are necessarily unique. To see this, assume for the sake of contradiction thatĉ 1 andĉ 2 are two strong solutions of (5). In this case the strong optimality ofĉ 1 implies thatĉ 2 Cĉ 1 , while the strong optimality ofĉ 2 implies thatĉ 1 Cĉ 2 . These two relations imply thatĉ 1 =ĉ 2 , that is, there cannot be two different strongly optimal solutions.
We are now ready to construct a meta-optimization problem akin to (5), which enables us to identify the best prescriptor. To this end, we henceforth denote by X the set of all data-driven predictor-prescriptor-pairs (ĉ,x), whereĉ ∈ C, andx is a prescriptor induced byĉ as per Definition 3.
Moreover, we equip X with a partial order X , which is defined through Note thatĉ 1 Cĉ2 actually implies (ĉ 1 ,x 1 ) X (ĉ 2 ,x 2 ) but not vice versa. The problem of finding the least conservative predictor-prescriptor-pair whose out-of-sample prescription disappointment decays at rate at least r > 0 can now be formalized as the following vector optimization problem.
Generic vector optimization problems typically only admit weak solutions. In Section 4 we will show, however, that (5) as well as (6) admit (unique) strong solutions in closed form. In fact, we will show that these closed-form solutions have a natural interpretation as the solutions of convex distributionally robust optimization problems.
Remark 1 (Out-of-sample and in-sample performance). The natural performance measure to quantify the goodness of a data-driven prescriptorx is its out-of-sample performance c(x(P T ), P ) under the true model P . As P is unknown, however, the out-of-sample performance cannot be optimized directly. A naïve remedy would be to formulate a meta-optimization problem that minimizes the worst-case (or some average) of the out-of-sample performance ofx across all models P ∈ P. The approach proposed here optimizes the out-of-sample performance implicitly.
Indeed, the meta-optimization problem (6) representsx as a minimizer of some predictorĉ, wherê c(x(P T ),P T ) should be interpreted as the in-sample performance ofx. Instead of minimizing the out-of-sample performance ofx, problem (6) minimizes the in-sample performance ofx but ensures through the constraints on the disappointment that the out-of-sample performance is smaller than the in-sample performance with increasingly high confidence as the sample size grows. In this sense, problem (6) minimizes a tight upper bound on the out-of-sample performance ofx.

Large deviation principles
Large deviations theory provides bounds on the exact exponential rate at which the probabilities of atypical estimator realizations decay under a model P as the sample size T tends to infinity.
These bounds are expressed in terms of the relative entropy ofP T with respect to P.
Definition 5 (Relative entropy). The relative entropy of an estimator realization P ∈ P with respect to a model P ∈ P is defined as where we use the conventions 0 log(0/p) = 0 for any p ≥ 0 and p log(p /0) = ∞ for any p > 0.
The relative entropy is also known as information for discrimination, cross-entropy, information gain or Kullback-Leibler divergence (Kullback and Leibler 1951). The following proposition summarizes the key properties of the relative entropy relevant for this paper.
Proposition 1 (Relative entropy). The relative entropy enjoys the following properties: (i) Information inequality: I(P , P) ≥ 0 for all P, P ∈ P, while I(P , P) = 0 if and only if P = P.
Proof. Assertions (i) and (ii) follow from Theorems 2.6.3 and 2.7.2 in Cover and Thomas (2006), respectively, while assertion (iii) follows directly from the definition of the relative entropy and our standard conventions regarding the natural logarithm.
We now show that the empirical estimators satisfy a weak large deviation principle (LDP). This result follows immediately from a finite version of Sanov's classical theorem. A textbook proof using the so-called method of types can be found in Cover and Thomas (2006, Theorem 11.4.1). As the proof is illuminating and to keep this paper self-contained, we sketch the proof in Appendix A.
Theorem 1 (Weak LDP). If the samples {ξ t } t∈N are drawn independently from some P ∈ P, then for every Borel set D ⊆ P the sequence of empirical distributions If additionally P > 0, then for every Borel set D ⊆ P we have 1 Note that the inequality (7a) provides an upper LDP bound on the exponential rate at which the probability of the eventP T ∈ D decays under model P. This upper bound is expressed in terms of a convex optimization problem that minimizes the relative entropy of P with respect to P across all estimator realizations P within D. Similarly, (7b) offers a lower LDP bound on the decay rate.
Note that in (7b) the relative entropy is minimized over the interior of D instead of D.
If the data-generating model P itself belongs to D, then inf P ∈D I(P , P) = I(P, P) = 0, which leads to the trivial upper bound P ∞ (P T ∈ D) ≤ 1. On the other hand, if D has empty interior (e.g., if D = {P} is a singleton containing only the true model), then inf P ∈int D I(P , P) = ∞, which leads to the trivial lower bound P ∞ (P T ∈ D) ≥ 0. Non-trivial bounds are obtained if P / ∈ D and int D = ∅.
In these cases the relative entropy bounds the exponential rate at which the probability of the atypical eventP T ∈ D decays with T . For some sets D this rate of decay is precisely determined by the relative entropy. Specifically, a Borel set D ⊆ P is called I-continuous under model P if Clearly, every open set D ⊆ P is I-continuous under any model P. Moreover, as the relative entropy is continuous in P for any fixed P > 0, every Borel set D ⊆ P with D ⊆ cl(int(D)) is I-continuous under P whenever P > 0. The LDP (7) implies that for large T the probability of an I-continuous set D decays at rate inf P ∈D I(P , P) under model P to first order in the exponent, that is, we have P ∞ (P T ∈ D) = e −T inf P ∈D I(P ,P)+o (T ) .
If we interpret the relative entropy I(P , P) as the distance of P from P , then the decay rate of P ∞ (P T ∈ D) coincides with the distance of the model P from the atypical event set D; see Figure 1.
Moreover, if D is I-continuous under P, then (8) implies that P ∞ (P T ∈ D) ≤ β whenever where r = inf P ∈D I(P , P) is the I-distance from P to the set D, and β ∈ (0, 1) is a prescribed significance level.
The weak LDP of Theorem 1 provides only asymptotic bounds on the decay rates of atypical events. However, one can also establish a strong LDP, which offers finite sample guarantees. Most results of this paper, however, are based on the weak LDP of Theorem 1.
Theorem 2 (Strong LDP). If the samples {ξ t } t∈N are drawn independently from some P ∈ P, then for every Borel set D ⊆ P the sequence of empirical distributions {P T } T ∈P satisfies Proof. The claim follows immediately from inequality (27) in the proof of Theorem 1 in Appendix A. Note that (27) does not rely on the assumption that P > 0. Visualization of the LDP (7). If D ⊆ P is I-continuous and P / ∈ D, then the probability P ∞ (PT ∈ D) decays at the exponential rate inf P ∈D I(P , P), which can be viewed as the relative entropy distance of P from D.

Distributionally robust predictors and prescriptors are optimal
Armed with the fundamental results of large deviations theory, we now endeavor to identify the least conservative data-driven predictors and prescriptors whose out-of-sample disappointment decays at a rate no less than some prescribed threshold r > 0 under any model P ∈ P, that is, we aim to solve the vector optimization problems (5) and (6).

Distributionally robust predictors
The relative entropy lends itself to constructing a data-driven predictor in the sense of Definition 3.
We will show below that this predictor is strongly optimal in (5).
Definition 6 (Distributionally robust predictors). For any fixed threshold r ≥ 0, we define the data-driven predictorĉ r : X × P → througĥ The data-driven predictorĉ r admits a distributionally robust interpretation. In fact,ĉ r (x, P ) represents the worst-case expected cost associated with the decision x, where the worst case is taken across all models P ∈ P whose relative entropy distance to P is at most r. Observe that the supremum in (10) is always attained because c(x, P) is linear in P and the feasible set of (10) is compact, which follows from the compactness of P and the lower semicontinuity of the relative entropy in P for any fixed P ; see Proposition 1(iii). Note also thatĉ r (x, P ) can be evaluated efficiently because (10) constitutes a convex conic optimization problem with d decision variables.
A particularly simple and efficient method to evaluateĉ r (x, P ) is to solve the one-dimensional convex minimization problem dual to (10) by using bisection or another line search method.
Proposition 2 (Dual representation ofĉ r ). If r > 0 andγ(x) = max i∈Ξ γ(x, i) denotes the worst-case cost function, then the distributionally robust predictor admits the dual representation Proof. See Appendix A.
Remark 2 (Sample average predictor). For r = 0 the distributionally robust predictorĉ r collapses to the sample average predictor of Example 1. Indeed, because of the strict positivity of the relative entropy I(P , P) > 0 for P = P, see Proposition 1(i), we have that As shown in Example 2, the sample average predictor fails to offer asymptotic or finite sample guarantees of the form (3) and (4), respectively.
Remark 3 (Alternative distributionally robust predictors). The relative entropy can also be used to construct a reverse distributionally robust predictorč r ∈ C defined througȟ c r (x, P ) = sup P∈P {c(x, P) : I(P, P ) ≤ r} ∀x ∈ X, P ∈ P.
In contrast toĉ r , the reverse distributionally robust predictorč r fixes the second argument of the relative entropy and maximizes over the first argument. Note thatč r can be viewed as the entropic value-at-risk of the uncertain cost γ(x, ξ); see (Ahmadi-Javid 2012, Theorem 3.3). Another predictor related toĉ is the restricted distributionally robust predictorc r ∈ C defined through where P P expresses the requirement that P must be absolutely continuous with respect to P .
Formally, P P means that P(i) = 0 for all outcomes i ∈ Ξ with P (i) = 0. By (Ahmadi-Javid 2012, Definition 5.1),c r can be interpreted as the negative log-entropic risk of γ(x, ξ).
The predictorsĉ r andč r differ because the relative entropy fails to be symmetric. We emphasize that the reverse predictorč r has appeared often in the literature on distributionally robust optimization, see, e.g., (Ben-Tal et al. 2013, Calafiore 2007, Hu and Hong 2013, Lam 2016b, Wang et al. 2016). The predictorsĉ r andc r differ, too, because of the additional constraint P P , which is significant when not all outcomes in Ξ have been observed. The statistical properties of the predictorc r have been analyzed by Lam (2016a) and more recently by Duchi et al. (2016) from the perspective of the empirical likelihood theory introduced by Owen (1988). The predictorĉ r suggested here has not yet been studied extensively even though-as we will demonstrate belowit displays attractive theoretical properties that are not shared by eitherč r orc r . The difference betweenĉ r andč r orc r is significant. Indeed, bothč r andc r hedge only against models P that are absolutely continuous with respect to the (observed realization of the) empirical distribution P .
While it is clear that the empirical distribution must be absolutely continuous with respect to the data-generating distribution, however, the converse implication is generally false. Indeed, an outcome can have positive probability even if it does not show up in a given finite time series. By taking the worst case only over models that are absolutely continuous with respect to P , both predictorsč r andc r potentially ignore many models that could have generated the observed data.
We first establish thatĉ r indeed belongs to the set C of all data-driven predictors, that is, the family of continuous functions mapping X × P to the reals.
Proposition 3 (Continuity ofĉ r ). If r ≥ 0, then the distributionally robust predictorĉ r is continuous on X × P.
Proof. By Proposition 2, the distributionally robust predictorĉ r admits the dual representation (11). Note that the objective function of (11) is manifestly continuous in (α, x, P ) and that (11) is guaranteed to have a minimizer in the compact interval , whose boundaries depend continuously on (x, P ). Consequently, the predictorĉ r is continuous by Berge's celebrated maximum theorem (Berge 1963, pp. 115-116).
We now analyze the performance of the distributionally robust data-driven predictorĉ r using arguments from large deviations theory. The parameter r encoding the predictorĉ r captures the fundamental trade-off between out-of-sample disappointment and accuracy, which is inherent to any approach to data-driven prediction. Indeed, as r increases, the predictorĉ r becomes more reliable in the sense that its out-of-sample disappointment decreases. However, increasing r also results in more conservative (pessimistically biased) predictions. In the following we will demonstrate that c r strikes indeed an optimal balance between reliability and conservatism.
Proof. From Proposition 3 we already know thatĉ r ∈ C. It remains to be shown that the outof-sample disappointment ofĉ r decays at a rate of at least r. We have c(x, P) >ĉ r (x,P T ) if and only if the estimatorP T falls within the disappointment set D(x, P) = {P ∈ P : c(x, P) >ĉ r (x, P )} .
Therefore, D(x, P) is a subset of I(P) = {P ∈ P : I(P , P) > r} irrespective of x ∈ X. We thus have where the first inequality holds because D(x, P) ⊆ I(P), while the second inequality exploits the weak LDP upper bound (7a). Thus,ĉ r is feasible in (5).
Note that any predictorĉ withĉ r Cĉ has a smaller disappointment set thanĉ r , and thus the out-of-sample disappointment ofĉ decays at least as fast as that ofĉ r . Hence,ĉ is also feasible in (5). In particular, this immediately implies that if we inflate the relative entropy ball of the distributionally robust predictorĉ r to any larger ambiguity set, we obtain another predictor that is feasible in (5). As an example, consider the total variation predictor c tv r (x, P ) = sup P∈P c(x, P) : P − P tv ≤ √ 2r ∀x ∈ X, P ∈ P, where P − P tv denotes the total variation distance between P and P . Pinsker's classical inequality asserts that P − P tv ≤ 2 I(P , P) for all P and P in P. Thus, we haveĉ r Cĉ tv r , which implies that the total variation predictor is feasible in (5). This suggests that (5) has a rich feasible set.
The following main theorem establishes thatĉ r is not only a feasible but even a strongly optimal solution for the vector optimization problem (5). This means that if an arbitrary data-driven predictorĉ predicts a lower expected cost thanĉ r even for a single estimator realization P ∈ P, then c must suffer from a higher out-of-sample disappointment thanĉ r to first order in the exponent.
Proof. Assume for the sake of argument thatĉ r fails to be a strong solution for (5). Thus, there exists a data-driven predictorĉ ∈ C that is feasible in (5) but not dominated byĉ r , that is,ĉ r Cĉ .
This means that there exists x ∈ X and P 0 ∈ P withĉ r (x, P 0 ) >ĉ(x, P 0 ). For later reference we set =ĉ r (x, P 0 ) −ĉ(x, P 0 ) > 0. In the remainder of the proof we will demonstrate thatĉ cannot be feasible in (5), which contradicts our initial assumption.
Let P 0 ∈ P be an optimal solution of problem (10) at P = P 0 . Thus, we have I(P 0 , P 0 ) ≤ r and c r (x, P 0 ) = c(x, P 0 ).
In the following we will first perturb P 0 to obtain a model P 1 that is 2 -suboptimal in (10) but satisfies I(P 0 , P 1 ) < r. Subsequently, we will perturb P 1 to obtain a model P 2 that is -suboptimal in (10) but satisfies I(P 0 , P 2 ) < r as well as P 2 > 0.
In summary, we thus havê where the first equality follows from the definition of , and the second equality exploits (14).
Moreover, the strict inequality holds due to (15), and the weak inequality follows from the definition ofĉ r and the fact that I(P 0 , P 2 ) = r 2 < r.
In the remainder of the proof we will argue that the prediction disappointment P ∞ 2 (c(x, P 2 ) > c(x,P T )) under model P 2 decays at a rate of at most r 2 < r as the sample size T tends to infinity.
In analogy to the proof of Theorem 3, we define the set of disappointing estimator realizations as D(x, P 2 ) = {P ∈ P : c(x, P 2 ) >ĉ(x, P )} .
This set contains P 0 due to the strict inequality in (16). Moreover, asĉ ∈ C is continuous, is an open subset of P. Thus, we find inf P ∈int D(x,P 2 ) I(P , P 2 ) = inf P ∈D(x,P 2 ) I(P , P 2 ) ≤ I(P 0 , P 2 ) = r 2 , where the inequality holds because P 0 ∈ D(x, P 0 ), and the last equality follows from the definition of r 2 . As the empirical distributions {P T } T ∈N obey the LDP lower bound (7b) under P 2 > 0, we finally conclude that The above chain of inequalities implies, however, thatĉ is infeasible in problem (5). This contradicts our initial assumption, and thus,ĉ r must indeed be a strong solution of (5).
Theorem 4 asserts that the distributionally robust predictorĉ r is optimal among all data-driven predictors representable as continuous functions of the empirical distributionP T . That is, any attempt to make it less conservative invariably increases the out-of-sample prediction disappointment. We remark that the class of predictors which depend on the data only throughP T is vast.
These predictors constitute arbitrary continuous functions of the data that are independent of the order in which the samples were observed. As the samples are independent and identically distributed, there are in fact no meaningful data-driven predictors that display a more general dependence on the data.
Note that in the above discussion all guarantees are fundamentally asymptotic in nature. Using Theorem 2 one can show, however, thatĉ r also satisfies finite sample guarantees.
Theorem 5 (Finite sample guarantee). The out-of-sample disappointment of the distributionally robust predictorĉ r enjoys the following finite sample guarantee under any model P ∈ P and for any x ∈ X.
Proof. The proof of this result widely parallels that of Theorem 3 but uses the strong LDP upper bound (9) in lieu of the weak upper bound (7a). Details are omitted for brevity.

Distributionally robust prescriptors
The distributionally robust predictorĉ r of Definition 6 induces a corresponding prescriptor.
Definition 7 (Distributionally robust prescriptors). Denote byĉ r , r ≥ 0, the distributionally robust data-driven predictor of Definition 6. We can then define the data-driven prescriptor x r : P → X as a quasi-continuous function satisfyinĝ x r (P ) ∈ arg min x∈Xĉ r (x, P ) ∀P ∈ P.
Note that the minimum in (18) is attained because X is compact andĉ r is continuous due to Proposition 3. Thus, there exists at least one functionx r satisfying (18). In the next proposition we argue that this function can be chosen to be quasi-continuous as desired.
Proof. Denote by Γ(P ) = arg min x∈Xĉr (x, P ) the argmin-mapping of problem (10), and observe that Γ(P ) is compact and non-empty for every P ∈ P becauseĉ r is continuous and X is compact.
As X is independent of P , Berge's maximum theorem (Berge 1963, pp. 115-116) further implies that Γ is upper semicontinuous. As P is a Baire space and X is a metric space, (Matejdes 1987, Corollary 4) finally guarantees that there exists a quasi-continuous functionx r : P → X witĥ x r (P ) ∈ Γ(P ) for all P ∈ P.
Propositions 3 and 4 imply that (ĉ r ,x r ) belongs to the family X of all data-driven predictorprescriptor-pairs. Using a similar reasoning as in Theorem 3, we now demonstrate that the outof-sample disappointment ofx r decays at rate at least r as T tends to infinity. Thus,x r provides trustworthy prescriptions.
Proof. Propositions 3 and 4 imply that (ĉ r ,x r ) ∈ X . It remains to be shown that the out-ofsample disappointment ofx r decays at a rate of at least r. To this end, define D(x, P) and I(P) as in the proof of Theorem 3, and recall that D(x, P) ⊆ I(P) for every decision x ∈ X and model P ∈ P. Thus, for every fixed estimator realization P ∈ P the following implication holds c(x r (P ), P) >ĉ r (x r (P ), P ) =⇒ ∃x ∈ X with c(x, P) >ĉ r (x, P ) =⇒ P ∈ ∪ x∈X D(x, P) =⇒ P ∈ I(P), which in turn implies for every model P ∈ P. Note that the second inequality in the above expression has already been established in the proof of Theorem 3. Thus, the claim follows.
Next, we argue that (ĉ r ,x r ) is a strongly optimal solution for the vector optimization problem (6).
Proof. Assume for the sake of argument that (ĉ r ,x r ) fails to be a strong solution for (6). Thus, there exists a data-driven prescriptor (ĉ,x) ∈ X that is feasible in (6) but not dominated by (ĉ r ,x r ), that is, (ĉ r ,x r ) X (ĉ,x). This means that there exists P 0 ∈ P withĉ r (x r (P 0 ), P 0 ) >ĉ(x(P 0 ), P 0 ). As X is compact andĉ is continuous, the costĉ(x(P ), P ) of the prescriptorx under the corresponding predictorĉ is continuous in P (Berge 1963, pp. 115-116). Similarly,ĉ r (x r (P ), P ) is continuous in P . Recall also thatx is quasi-continuous and therefore continuous on a dense subset of P (Bledsoe 1952). Thus, we may assume without loss of generality thatx is continuous at P 0 . For later reference we set =ĉ r (x(P 0 ), P 0 ) −ĉ(x(P 0 ), P 0 ) > 0.
In the remainder of the proof we will demonstrate that (ĉ,x) cannot be feasible in (6), which contradicts our initial assumption. To this end, let P 0 ∈ P be an optimal solution of problem (10) at x =x(P 0 ) and P = P 0 . Thus, we have I(P 0 , P 0 ) ≤ r and Next, we first perturb P 0 to obtain a model P 1 that is strictly 2 -suboptimal in (10) but satisfies I(P 0 , P 1 ) = r 1 < r. Subsequently, we perturb P 1 to obtain a model P 2 that is strictly -suboptimal in (10) but satisfies I(P 0 , P 2 ) = r 2 < r as well and P 2 > 0. The distributions P 1 and P 2 can be constructed exactly as in the proof of Theorem 4. Details are omitted for brevity. Thus, we find where the first equality follows from the definition of , and the second equality exploits (19).
Moreover, the strict inequality holds because P 2 is strictly -suboptimal in (10), while the weak inequality follows from the definition ofĉ r and the fact that I(P 0 , P 2 ) = r 2 < r.
It remains to be shown that the prediction disappointment P ∞ 2 (c(x(P T ), P 2 ) >ĉ(x(P T ),P T )) under model P 2 decays at a rate of at most r 2 < r as the sample size T tends to infinity. To this end, we define the set of disappointing estimator realizations as D(P 2 ) = {P ∈ P : c(x(P ), P 2 ) >ĉ(x(P ), P )} .
This set contains P 0 due to the strict inequality in (20). Recall now thatx is continuous at P = P 0 due to our choice of P 0 . As the predictorsĉ andĉ r are both continuous on their entire domain, the compositionsĉ(x(P ), P ) and c(x(P ), P 2 ) are both continuous at P = P 0 . This implies that P 0 belongs actually to the interior of D(P 2 ). Thus, we find inf P ∈int D(P 2 ) I(P , P 2 ) ≤ I(P 0 , P 2 ) = r 2 , where the last equality follows from the definition of r 2 . As the empirical distributions {P T } T ∈N obey the LDP lower bound (7b) under P 2 > 0, we finally conclude that −r < −r 2 ≤ − inf P ∈int D(P 2 ) The above chain of inequalities implies, however, that (ĉ,x) is infeasible in problem (6). This contradicts our initial assumption, and thus, (ĉ r ,x r ) must indeed be a strong solution of (6).
All guarantees discussed so far are asymptotic in nature. As in the case of the predictorĉ r , however, the prescriptorx r can also be shown to satisfy finite sample guarantees.
Theorem 8 (Finite sample guarantee). The out-of-sample disappointment of the distributionally robust prescriptorx r enjoys the following finite sample guarantee under any model P ∈ P.
Proof. The proof of this result parallels those of Theorems 3 and 6 but uses the strong LDP upper bound (9) in lieu of the weak upper bound (7a). Details are omitted for brevity.
We stress that the finite sample guarantees of Theorems 5 and 8 as well as the strong optimality properties portrayed in Theorems 4 and 7 are independent of a particular dataset. They guarantee thatĉ r andx r provide trustworthy predictions and prescriptions, respectively, before the data is revealed.
Remark 4 (Optimal hypothesis testing). Bertsimas et al. (2018b) propose to construct predictors and prescriptors from statistical hypothesis tests. A hypothesis test uses i.i.d. samples ξ 1 , . . . , ξ T drawn from the unknown true distribution P to decide whether the null hypothesis P = P is false for a fixed model P ∈ P. Specifically, the null hypothesis is rejected (it is declared that P = P) if the empirical distributionP T associated with the observed sample path falls outside of a (measurable) acceptance region A T (P) ⊆ P, which depends on the conjectured model P and the sample size T . Otherwise, it is deemed that there is insufficient data to reject the null hypothesis. Bertsimas et al. (2018b) associate with each hypothesis test a predictor which evaluates the worst-case expected cost across all models P ∈ P that pass the hypothesis test in view of the realization P ∈ P T = P ∩ {0, 1/T, . . . , The quality of a hypothesis test is usually measured by its type I error P ∞ (P T ∈ A T (P)), that is, the probability of falsely rejecting the null hypothesis, as well as its type II error Q ∞ (P T ∈ A T (P)), that is, the probability of falsely accepting the null hypothesis if the data follows a distribution Q = P. A particularly popular test is the likelihood ratio test, which uses the acceptance region Zeitouni et al. (1992) prove that the likelihood ratio test is optimal in the following sense. Among all hypothesis tests whose type I error decays at a rate of at least r, lim sup T →∞ 1 T log P ∞ (P T / ∈ A T (P)) ≤ −r, the likelihood ratio test minimizes the nagative decay rate of the type II error lim sup T →∞ 1 T log Q ∞ (P T ∈ A T (P)) simultaneously for all models Q ∈ P with Q = P. Cover and Thomas (2006, Theorem 11.1.2) further establish that the likelihood ratio of an estimator realization P ∈ P T under two alternative distributions Q and P satisfies log(P ∞ (P T = P )/Q ∞ (P T = P )) = −T (I(P , P) − I (P , Q)). The acceptance region of the likelihood ratio test thus simplifies to A T (P) = {P ∈ P T : I(P , P) ≤ r + inf Q =P I(P , Q)} = {P ∈ P T : I(P , P) ≤ r} , where the equality holds because inf Q =P I(P , Q) = 0. Hence, the distributionally robust predictorĉ r that is strongly optimal in the meta-optimization problem (5) coincides with the hypothesis testbased predictor (22) corresponding to the likelihood ratio test.

Extension to continuous state spaces
Assume now that the realizations of the random parameter ξ may range over an arbitrary compact set Ξ ⊆ d that is not necessarily finite. In analogy to the discrete case, we denote by P the family of all Borel probability distributions supported on Ξ. Note that P is now a convex subset of an infinitedimensional space, which significantly complicates the problem of finding optimal predictors and prescriptors. We equip P with the standard topology of weak convergence of distributions, recalling that the weak topology is metrized by the Prokhorov metric (Prokhorov 1956). Consequently, we equip X × P with the product of the standard Euclidean topology on X and the weak topology on P. In the remainder of this section we analyze to what extent-and under what additional conditions-the results for finite state spaces carry over to the more general continuous case. As this analysis requires more subtle mathematical techniques, we relegate all proofs to Appendix A.
We first note that the definitions of model-based predictors and prescriptors require no changes.
In order to evaluate the expectation in the definition of the model-based predictor c(x, P) = Ξ γ(x, ξ)dP(ξ), however, we now need to evaluate an integral with respect to P instead of a finite sum. Throughout this section we assume that the cost function γ(x, ξ) is jointly continuous in x and ξ. This implies via the compactness of X and Ξ that c(x, P) is continuous in x and P, which in turn guarantees that a model-based prescriptor x (P) ∈ arg min x∈X c(x, P) exists for every P ∈ P.
Lemma 1 (Continuity of model-based predictors). If γ(x, ξ) is continuous on the compact set X × Ξ, then c(x, P) is continuous on X × P.
As in the case of a discrete state space, we study data-driven predictors and prescriptors that depend on the training data {ξ t } T t=1 only through the empirical distribution. Because Ξ may now have infinite cardinality, we redefine the empirical distribution asP T = 1 T T t=1 δ ξ t , where δ ξ t denotes the Dirac point mass at ξ t . Using this new definition ofP T , we then define data-driven predictors and prescriptors exactly as in Section 2.1. As Ξ is compact, one can show that P is compact in the weak topology (Prokhorov 1956). Moreover, as the weak topology is metrized by the Prokhorov metric, P constitutes a (locally) compact metric space. The Baire category theorem thus implies that P is a Baire space (Baire 1899). Corollary 4 in (Matejdes 1987, p. 120), which applies because P is a Baire space and X is a metric space, further ensures that for any valid (continuous) predictor c the set-valued mapping arg min x∈Xĉ (x, P ) admits a quasi-continuous selectorx, which serves as a valid data-driven prescriptor. Using the exact same reasoning as in Section 2.1, one can show that the points of continuity of any quasi-continuous prescriptor are dense in P.
The best predictors and predictor-prescriptor-pairs can again be found by solving the metaoptimization problems (5) and (6), respectively. In order to construct near-optimal solutions for these meta-optimization problems, we recall the definition of the relative entropy between arbitrary distributions P and P on a compact set Ξ ⊆ d .
Definition 8 (Generalized relative entropy). The relative entropy of P ∈ P with respect to P ∈ P is defined as where P P means that P is absolutely continuous with respect to P, while dP /dP(ξ) denotes the Radon-Nikodym derivative of P with respect to P, which exists if P P (Nikodym 1930).
The properties of the relative entropy portrayed in Proposition 1 hold verbatim in the more general setting considered here (Van Erven and Harremoës 2014). Using the generalized definition of the relative entropy, the distributionally robust predictorĉ r and the corresponding prescriptor x r can be constructed as in Definitions 6 and 7, respectively. In the following we will show that the predictorĉ r is continuous, which ensures that the prescriptorx r can always be chosen to be quasi-continuous. To this end, we first derive a dual representation forĉ r .
Proposition 5 (Dual representation revisited). If r > 0 andγ(x) = max ξ∈Ξ γ(x, ξ) is the worst-case cost function, then the distributionally robust predictor admits the dual representation Problem (23) has a minimizer α ≤γ (x)−e −r c(x,P ) Proposition 5 extends Proposition 2 to compact continuous state spaces and suggests thatĉ r (x, P ) can be computed via bisection or other line search methods. Thus, the computational tractability of problem (23) largely hinges on our ability to efficiently evaluate the geometric mean exp Ξ log (α − γ(x, ξ)) dP (ξ) for any fixed α. For example, if P coincides with (a realization of) the empirical distributionP T , we recover the geometric mean of α − γ(x, ξ) along a sample path, which can be reformulated as the optimal value of a tractable second-order cone program involving O(T ) constraints and auxiliary variables (Nesterov and Nemirovskii 1994, Section 6.2.3.5).
To our best knowledge, the dual representation (23)  Maybe surprisingly, however, the derivation of (23) provided here is substantially more challenging.
Proposition 6 (Continuity ofĉ r revisited). If r ≥ 0, then the distributionally robust predictorĉ r is continuous on X × P.
Proposition 6 ensures thatĉ r ∈ C. As any continuous predictor induces a quasi-continuous prescriptor, we may thus conclude that there exists a valid distributionally robust prescriptorx r such that (ĉ r ,x r ) ∈ X . It now only remains to establish that these predictors and predictor-prescriptorpairs are the unique strong solutions of the meta-optimization problems (5) and (6), respectively.
In Section 4 this was achieved by leveraging the weak LDP portrayed in Theorem 1. Luckily, this LDP carries over to the more general setting considered here-albeit with a subtle difference.
Theorem 9 (Weak LDP revisited). If the samples {ξ t } t∈N are drawn independently from some P ∈ P, then for every set D ⊆ P the sequence of empirical distributions Proof. See Csiszár (2006, Section 2).
Formally, Theorem 9 is almost identical to Theorem 1. However, the weak LDP upper bound (24a) differs from (7a) in that the minimization over all estimator realizations P on the right hand side runs over the closure of D. This subtle difference invalidates the proof of Theorem 3, and thus we need a new approach to show thatĉ r is feasible in (5). Moreover, the weak LDP lower bound (24b) does not rely on any structural assumptions about P. Note that the condition P > 0 in Theorem 1 was only imposed for convenience to simplify the proof of (7b) in Appendix A.
As in the case of finite state spaces, one can now show that the distributionally robust predictorĉ r is the unique strong solution of the meta-optimization problem (5).
While we did not manage to prove that (ĉ r ,x r ) is feasible in the meta-optimization problem (6), we still could show that it is essentially feasible and strongly optimal in a precise sense.
Theorem 11 asserts that (ĉ r ,x r ) is less conservative than any predictor-prescriptor pair feasible in the meta-optimization problem (6) and that (ĉ r ,x r ) can be made feasible in (6) by shifting the distributionally robust predictorĉ r up by just a tiny amount. For practical purposes this means that (ĉ r ,x r ) is indeed essentially optimal. Whether (ĉ r ,x r ) itself is feasible in (6) remains open.
We also emphasize that the strong LDP portrayed in Theorem 2 has no continuous counterpart, which implies that the finite sample guarantees of Theorems 5 and 8 cannot be generalized.

Appendix A: Proofs
Proof of Theorem 1. Let i t ∈ Ξ be a particular realization of the random variable ξ t for each t = 1, . . . , T , and denote by P the realization of the estimatorP T corresponding to the sequence {i t } T t=1 . The probability of observing this sequence (in the given order) under model P can be expressed in terms of P as Set P T = P ∩ {0, 1/T, . . . , (T − 1)/T, 1} d and note that P ∞ (P T ∈ P T ) = 1. By construction, the cardinality of P T is bounded above by (T + 1) d .
In the following, we denote the set of all sample paths in Ξ T that give rise to the same empirical distribution P ∈ P T by C T (P ). The cardinality of C T (P ) coincides with the number of sample paths that visit state i exactly T · P (i) times for all i ∈ Ξ, that is, we have Stirling's approximation for factorials allows us to bound the cardinality of C T (P ) from both sides in terms of the entropy H(P ) = − d i=1 P (i) log P (i) of the empirical distribution P , that is, An elementary proof of these inequalities that does not involve Stirling's approximation is given by Cover and Thomas (2006, Theorem 12.1.3).
Select an arbitrary Borel set D ⊆ P. For any T ∈ N, we thus have where the first inequality exploits the estimate |P T | ≤ (T + 1) d , the second inequality holds due to (25) and the definition of C T (P ), and the third inequality follows from the upper estimate in (26). Taking logarithms on both sides of the above expression and dividing by T yields Note that the finite sample bound (27) does not rely on any properties of the set D besides measurability.
The asymptotic upper bound (7a) is obtained by taking the limit superior as T tends to infinity on both sides of (27).
As for the lower bound (7b), recall that I(P , P) is continuous in P as P > 0, see Proposition 1(iii), and note that T ∈N P T is dense in int D. Thus, there exists T 0 ∈ N and a sequence of distributions P T ∈ P T , T ∈ N, such that P T ∈ int D for all T ≥ T 0 and inf P ∈int D I(P , P) = lim inf T →∞ I(P T , P).
Fix any T ≥ T 0 and let (i 1 , . . . , i T ) be a sequence of observations that generates P T . Then, we have where the first inequality holds because P T ∈ int D ⊆ D, while the second inequality follows from (25) and the lower estimate in (26). This implies that Taking the limit inferior as T tends to infinity on both sides of the above inequality and using (28) for any r > 0. In the following we denote the objective function of (29) by g(α, ν), which is lower semicontinuous due to our conventions for the logarithm. As g(α, 0) = α and lim ν→∞ g(α, ν) = ∞, there must exist ν (α) ∈ arg min ν≥0 g(α, ν) for any α ≥γ(x). Indeed, if there is i ∈ Ξ with α = γ(x, i) and P (i) > 0, then ν (α) = 0. Otherwise, ν (α) is the unique solution of the first-order optimality condition Thus, the partial minimum is readily recognized as the objective function of problem (11), which is manifestly continuous in α and inherits convexity from g(α, ν). By using Jensen's inequality to interchange the logarithm and the expectation with respect to P in the second expression in (30), we find As r > 0, the above estimate implies that the partial minimum g(α, ν (α)) tends to infinity as α grows.
Combining this upper bound with the lower bound (31) yields the estimate Thus, the claim follows.
Proof of Lemma 1. As the cost function γ(x, ξ) is continuous and its domain X × Ξ is compact, the Heine-Cantor theorem implies that γ(x, ξ) is uniformly continuous on its domain. Consider now an arbitrary converging sequence (x i , P i ), i ∈ N, in X × P, and denote its limit by (x, P). The uniform continuity of the cost function ensures that for every δ > 0 there exists N δ ∈ N such that |γ(x i , ξ) − γ(x, ξ)| ≤ δ uniformly across all ξ ∈ Ξ and i ≥ N δ , which in turn implies that As the integrant γ(x, ξ) on the right hand side of the above inequality is continuous and bounded in ξ, and as the sequence P i , i ∈ N, converges weakly to P, we thus have lim i→∞ Ξ γ(x, ξ)P(dξ) − Ξ γ(x i , ξ)P i (dξ) ≤ δ.
As δ > 0 was chosen arbitrary, we may finally conclude that The claim then follows because the converging sequence (x i , P i ), i ∈ N, was chosen arbitrary.
In order to prove Proposition 5 we need three auxiliary lemmas. As a starting point, we first exploit the definition of the relative entropy between arbitrary distributions on a compact state space Ξ to re-express the distributionally robust predictor explicitly aŝ Under the standing assumptions that X and Ξ are compact, while the cost function γ(x, ξ) is jointly continuous in its arguments, the feasible set of problem (32) can be restricted to distributions P that are absolutely continuous with respect to P except perhaps on the compact set Ξ (x) = arg max ξ∈Ξ γ(x, ξ).
Note that p > 0 for otherwise P p · P c . The constraints of (33) and the construction of P thus imply that P P c P. By the Radon-Nikodym theorem (Nikodym 1930), we then have and for all Borel sets A ⊆ Ξ, where the inequality in the last expression holds because Radon-Nikodym derivatives are pointwise non-negative. In summary, the above reasoning implies that dP dP (ξ) ≤ 1 p · dP dP c (ξ) P-a.s.
In fact, as P P, the above inequality even holds almost surely with respect to P , which in turn implies Thus, P is feasible in (32). Moreover, it is easy to verify that the objective value of P in (32) is equal to that of (P c , p) in (33). Thus, (32) provides an upper bound on (33).
It remains to be shown that (32) provides also a lower bound on (33). To this end, choose any P feasible in (32), define Ξ + = {ξ ∈ Ξ : dP /dP(ξ) > 0} as the (measurable) event in which the Radon-Nikodym derivative of P with respect to P is strictly positive, and set p = P[Ξ + ]. Note that p > 0, for otherwise the relations P[Ξ + ] = 0 and P P would imply via the Radon-Nikodym theorem that Next, we define P c ∈ P through P c [A] = P[A ∩ Ξ + ]/p for all Borel sets A ⊆ Ξ. By construction, P is absolutely continuous with respect to P c . To see this, note that for any Borel set A ⊆ Ξ we have where the implication holds because P P. Conversely, one can also show that P c is absolutely continuous with respect to P . To see this, assume that P c [A] > 0 for some Borel set A ⊆ Ξ. By the construction of P c we thus have P[A ∩ Ξ + ] > 0. The Radon-Nikodym theorem further implies that where the inequality holds because the integral of a strictly positive function over a set of strictly positive measure must be strictly positive. We have thus shown that P c [A] > 0 implies P [A] > 0 or, by contraposition, that P [A] = 0 implies P c [A] = 0. In summary, the above reasoning ensures that P p · P c P .
Using the Radon-Nikodym theorem once again, we have for all Borel sets A ⊆ Ξ that where the last equality holds because dP /dP(ξ) = 0 for all ξ / ∈ Ξ + and because P = p · P c when restricted to the Borel σ-algebra on Ξ + . As the above equality holds for all Borel sets A ⊆ Ξ, we find dP dP c (ξ) = p · dP dP (ξ) P c -a.s. =⇒ 1 p · dP dP c (ξ) = dP dP (ξ) P -a.s., where the implication holds because p > 0 and P P c . The last identity and our standard convention 0 log(0) = 0 ensure that Ξ log 1 p · dP dP c (ξ) dP (ξ) = Ξ log dP dP (ξ) dP (ξ) ≤ r.
Assume now that p < 1, and define P ⊥ ∈ P through P ⊥ [A] = P[A\Ξ + ]/(1 − p) for all Borel sets A ⊆ Ξ. By construction, P ⊥ is thus singular with respect to P c , and we have P = p · P c + (1 − p) · P ⊥ . This implies that If p = 1, on the other hand, we trivially have P = P c and In summary, we have thus shown that for every P feasible in (32) there exists (p, P c ) feasible in (33) with the same or with a larger objective value. This implies that (32) provides a lower bound on (33).
Define now the family of predictorŝ parameterized by r > 0 and ≥ 0. We first show thatĉ r, uniformly approximatesĉ r .
Proof. The claim follows immediately by comparing the absolutely continuous representations forĉ r derived in Lemma 2 with the definition ofĉ r, in (34).
Next, we demonstrate that the predictorsĉ r, defined in (34) admit a dual representation in the form of a univariate convex optimization problem.
Proof. By applying the variable transformations p ← 1 − p and P c ← p · P c , the non-convex optimization problem (34) can be reformulated aŝ which is manifestly convex. The condition P c ≥ 0 abbreviates the requirement that P c is a finite non-negative Borel measure supported on Ξ. Note also that the normalization of P c is now enforced through an explicit constraint. Next, we eliminate the decision variable P c from (36) by re-expressing it in terms of P and the Radon-Nikodym derivative Λ(ξ) = dP c /dP (ξ). In particular, as P c P and P P c , we have dP /dP c (ξ) = (dP c /dP (ξ)) −1 = Λ(ξ) −1 almost everywhere with respect to P . Thus, problem (36) is equivalent tô where the condition Λ ≥ 0 abbreviates the requirement that Λ is a non-negative Borel-measurable function on Ξ. The first (relative entropy) constraint ensures that Λ(ξ) > 0 almost surely with respect to P , while the second (normalization) constraint ensures that the measure induced by Λ and P is finite. Thus, the constraint that P be absolutely continuous with respect to P c , which is explicitly imposed in (36), remains implicitly enforced in (37). The Lagrangian dual of the convex maximization problem (37) is given by where the dual objective function can be represented as By weak duality, the dual problem (38) provides an upper bound onĉ r, (x, P ). Note that the supremum over p ≥ 0 in the definition of g(α, ν) is unbounded ifγ(x) + > α and evaluates to 0 otherwise. Thus, the dual problem (38) includes the implicit constraintγ(x) + ≤ α. We henceforth assume that this constraint holds, and we assume that the logarithm of any nonpositive number is defined as −∞. Under this premise we may remove the redundant constraint Λ ≥ 0 and reformulate the dual objective function as where the supremum over all measurable functions Λ can be moved inside the integral and converted to a supremum over all scalars λ by appealing to (Rockafellar and Wets 1998, Theorem 14.60). The third equality in the last line follows from an explicit solution of the convex maximization problem over λ, which has a unique well-defined solution because γ(x, ξ) − α ≥ for all ξ ∈ Ξ. The dual problem (38) is thus equivalent to min α≥γ(x)+ ,ν≥0 Ξ ν log ν α − γ(x, ξ) dP (ξ) + α + ν(r − 1), which constitutes a finite-dimensional convex minimization problem. If = 0, then (39) can be viewed as a continuous version of (29). The dual objective function g(α, ν) is lower semicontinuous. To see this, note that the function inside the integral in (39) is lower semicontinuous in (α, ν) due to our conventions for the logarithm and because lower semicontinuity is preserved under integration thanks to Fatou's lemma.
Following a similar reasoning as in the proof of Proposition 2, one can now show that the minimum of (39) is always attained by some α and ν and that (39) is equivalent to the one-dimensional convex program which has a minimizer α ≤γ (x)+ −e −r c(x,P ) 1−e −r . Details are omitted for the sake of brevity.
Note that (40) coincides with coincides with the optimization problem on the right hand side of (35).
The above arguments thus imply that (40) provides an upper bound onĉ r, (x, P ). To prove that this upper bound is in fact exact for > 0, it remains to be shown that the duality gap between (37) and (39) vanishes.
We will do so by constructing a pair of primal and dual feasible solutions whose objective values coincide.
For > 0 the minimization problem (39) where λ represents the Lagrange multiplier of the constraint α ≥γ(x) + . Given any solution (α , ν , λ ) of the KKT conditions, we can now introduce a Borel-measurable function Λ (ξ) = ν α −γ(x,ξ) and define p = λ . As α ≥γ(x) + , the function Λ is strictly positive on Ξ. The two stationarity conditions thus imply that (Λ , p ) is feasible in (37). Moreover, we have where the first equality follows from the definition of g, the second equality holds due to the stationarity condition for ν, the fourth equality follows from the definition of Λ and the stationarity condition for α, and the last equality exploits the complementary slackness condition as well as the definition of p .
We have thus shown that the objective value of (Λ , p ) in (37) coincides with the objective value of (α , ν ) in (39), which certifies that the duality gap between (37) and (39) vanishes.
Armed with Lemmas 3 and 4, we are now ready to prove Proposition 5.
Proof of Proposition 5. For every > 0 we havê where the first inequality follows from Lemma 4 for = 0, the equality follows from Lemma 4 for > 0, and the last inequality follows from Lemma 3. As the above inequalities remain valid for all > 0, we may conclude that (23) holds. The claim that the minimization problem on the right hand side of (23) has an optimizer α ≤γ (x)−e −r c(x,P ) 1−e −r follows from Lemma 4.
Proof of Proposition 6. Fix > 0 and recall from Lemma 4 thatĉ r, (x, P ) coincides with the optimal value of the univariate convex minimization problem on the right hand side of (35). Throughout this proof we assume without loss of generality that this problem accommodates the extra constraint α ≤γ (x)+ −e −r c(x,P ) Indeed, Lemma 4 guarantees that this constraint has no impact on the problem's optimal value.
In the first part of the proof we demonstrate that the compactified feasible set (35) with the redundant upper bound on α represents a continuous set-valued mapping parameterized in (x, P ). To this end, we note that the worst-case costγ(x) is continuous in x by Berge's maximum theorem (Berge 1963, pp. 115-116), which applies because Ξ is compact and γ(x, ξ) is jointly continuous in x and ξ. Lemma 1 further implies that c(x, P ) is continuous in x and P . As both the upper and the lower bound on α depend continuously on (x, P ), we conclude that the feasible set mapping is indeed continuous.
In the second part of the proof we argue that the objective function of (35) is continuous in (α, x, P ). To this end, recall that the cost function γ(x, ξ) is uniformly continuous on its compact domain X × Ξ. Consider now an arbitrary converging sequence (α i , x i , P i ), i ∈ N, in R × X × P such that α i ≥γ(x i ) + for all i ∈ N, and denote its limit by (α, x, P ). The uniform continuity of the cost function ensures that for every δ > 0 there exists N δ ∈ N such that |α i − α| ≤ δ and |γ(x i , ξ) − γ(x, ξ)| ≤ δ uniformly across all ξ ∈ Ξ and i ≥ N δ .
As the natural logarithm is Lipschitz continuous on [ , ∞) with Lipschitz constant 1/ , we thus have This implies that As the limit of the chosen sequence satisfies α − γ(x, ξ) ≥ > 0, the integrand on the right hand side of the above inequality is continuous and bounded in ξ. By the definition of weak convergence we thus find As δ > 0 was chosen arbitrary, it follows that Ξ log(α i − γ(x i , ξ))dP i converges to Ξ log(ᾱ − γ(x, ξ))dP , which establishes that the objective function of problem (35) is continuous in (α, x, P ).
In summary, we have shown that the compactified feasible set of problem (35) is continuous in (x, P ) and that the objective function of (35) is continuous in (α, x, P ). Thus,ĉ r, (x, P ) is continuous by Berge's maximum theorem (Berge 1963). Asĉ r, (x, P ) uniformly approximatesĉ r (x, P ) for ↓ 0 (see Lemma 3), and as uniform limits of continuous functions are continuous, we conclude thatĉ r (x, P ) is continuous.
Proof of Theorem 10. We first establish feasibility for r ≥ 0. From Proposition 6 we already know that c r is continuous on X × P, that is,ĉ r ∈ C. To show that the out-of-sample disappointment ofĉ r decays sufficiently fast, we fix any decision x ∈ X and an arbitrary distribution P 0 ∈ P, and we define D(x, P 0 ) = {P ∈ P : c(x, P 0 ) >ĉ r (x, P )} andD(x, P 0 ) = {P ∈ P : c(x, P 0 ) ≥ĉ r (x, P )} as the corresponding strict and weak disappointment sets. Using this notation, we need to demonstrate that the probability of the eventP T ∈ D(x, P 0 ) decays at a rate of at least r. We will prove this assertion by case distinction depending on the probability of the set of worst-case scenarios, Ξ (x) = arg max ξ∈Ξ γ(x, ξ), which is non-empty and compact because γ is continuous and Ξ is compact.
The probability of being disappointed thus vanishes for all T ∈ N. Hence, it trivially decays at any rate.
Case 2: Assume next that P 0 (Ξ (x)) < 1. To prove that the probability of the eventP T ∈ D(x, P 0 ) decays at a rate of at least r, we will first establish the implication P ∈D(x, P 0 ) =⇒ I(P , P 0 ) ≥ r.
Thus, our assumption was false, and hence (41) follows.
All other arguments remain unaffected.
Now that the implication (41) has been established, we demonstrate that the probability of the eventP T ∈ D(x, P 0 ) decays at a rate of at least r. To this end, we first note that the weak disappointment setD(x, P 0 ) includes the strict disappointment set D(x, P 0 ) and is closed because of the continuity ofĉ r established in where the second inequality holds becauseD(x, P 0 ) is closed and contains D(x, P 0 ), while the third inequality follows from (41). Thus, the probability of the eventP T ∈ D(x, P 0 ) decays indeed at a rate of at least r.
As the choice of x ∈ X and P 0 ∈ P was arbitrary, and as Cases 1 and 2 are exhaustive,ĉ r is feasible in (5).
In order to show thatĉ r is strongly optimal in (5) when > 0, we can repeat the proof of Theorem 4 almost verbatim with obvious minor modifications (most notably, there is no need to construct P 2 ).
Proof of Theorem 11. We first establish feasibility for r ≥ 0 and > 0. From Proposition 6 and the subsequent discussion we know thatĉ r is continuous and thatx r can be chosen to be quasi-continuous, which implies that (ĉ r + ,x r ) ∈ X . To show that the out-of-sample disappointment of (ĉ r + ,x r ) decays sufficiently fast, we fix P 0 ∈ P and define D (P 0 ) = {P ∈ P : c(x r (P ), P 0 ) >ĉ r (x r (P ), P ) + } as the corresponding disappointment sets. For any x ∈ X and P 0 ∈ P we further define D (x, P 0 ) = {P ∈ P : c(x, P 0 ) >ĉ r (x, P ) + } andD (x, P) = {P ∈ P : c(x, P) ≥ĉ r (x, P ) + } as the corresponding strict and weak decision-dependent disappointment sets. In order to show that the probability of the eventP T ∈ D (x, P 0 ) decays at a rate of at least r, we observe that whereD (P 0 ) = P ∈ P : max x∈X c(x, P 0 ) −ĉ r (x, P ) ≥ .
The proof of Theorem 10 immediately implies thatD (x, P 0 ) is closed. We will now argue thatD (P 0 ) is also closed. As the model-based predictor c and the distributionally robust predictorĉ r are both jointly continuous in x and P and as the feasible set X is compact, the maximum theorem by Berge (1963, pp. 115-116) implies that the function max x∈X c(x, P 0 ) − c r (x, P ) is continuous in P for any fixed P 0 . Thus,D (P 0 ) is closed as a superlevel set of a continuous function. As D (P 0 ) ⊆D (P 0 ), this implies that cl D (P 0 ) ⊆D (P 0 ).
Next, we will establish the implication P ∈D (x, P 0 ) =⇒ I(P , P 0 ) ≥ r for any > 0. Assume first that P 0 (Ξ (x)) = 1, where Ξ (x) = arg max ξ∈Ξ γ(x, ξ) stands as usual for the (compact) set of worst-case scenarios. Then, for any P ∈ P with I(P , P 0 ) < r we have P P 0 =⇒ P (Ξ (x)) = 1 =⇒ c(x, P 0 ) =ĉ r (x, P ) =⇒ P / ∈D (x, P 0 ), where the first implication holds because the support of P 0 is a assumed to be a subset of Ξ (x) and because the support of any distribution P that is absolutely continuous with respect to P 0 must be contained in the support of P 0 . The second implication follows from the observation that both c(x, P 0 ) andĉ r (x, P ) must evaluate to the worst-case costγ(x) = max ξ∈Ξ γ(x, ξ) because both P 0 and P are supported on the set of worst-case scenarios Ξ (x). Thus, I(P , P 0 ) < r implies P / ∈D (x, P 0 ), whereby (42) follows by contraposition.
Assume next that P 0 (Ξ (x)) < 1. Then (42) is an immediate consequence of the stronger implication (41) derived in the proof of Theorem 10.
In summary, we thus find lim sup where the first inequality follows from the weak LDP upper bound (24a) and the inclusion cl D (P 0 ) ⊆D (P 0 ).
The equality exploits the definition ofD (P 0 ), and the second inequality follows from the inclusion (42), which holds for any > 0. As P 0 ∈ P and > 0 were chosen arbitrarily, (ĉ r + ,x r ) is thus feasible in (6).
To show that (ĉ r ,x r ) is preferred to any feasible solution in (6) when > 0, we can repeat the proof of Theorem 7 almost verbatim with obvious minor modifications (e.g., there is no need to construct P 2 ).