text:
\begin{document}

\title{Distributional Robust Batch Contextual Bandits}

\author[1]{Nian Si\thanks{niansi@stanford.edu}}
\author[1]{Fan Zhang\thanks{fzh@stanford.edu}}
\author[2]{Zhengyuan Zhou\thanks{zzhou@stern.nyu.edu}}
\author[1]{Jose Blanchet\thanks{jose.blanchet@stanford.edu}}
\affil[1]{Department of Management Science \& Engineering, Stanford University}
\affil[2]{Stern School of Business, New York University}
\date{}

\maketitle
\begin{abstract}
Policy learning using historical observational data is an important problem that has found widespread applications. Examples include selecting offers, prices, advertisements to send to customers, as well as selecting which medication to prescribe to a patient. However, existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment that has generated the data--an assumption that is often false or too coarse an approximation.
In this paper, we lift this assumption and aim to learn a distributional robust policy with incomplete (bandit)  observational data. We propose a novel learning algorithm that is able to learn a robust policy to adversarial perturbations and unknown covariate shifts. We first present a policy evaluation procedure in the ambiguous environment and then give a performance guarantee based on the theory of uniform convergence. Additionally, we also give a heuristic algorithm to solve the distributional robust policy learning problems efficiently.
\end{abstract}
\section{Introduction}

\label{sec:intro} As a result of a digitalized economy, the past decade has
witnessed an explosion of user-specific data across a variety of application
domains: electronic medical data in health care, marketing data in product
recommendation and customer purchase/selection data in digital advertising
\cite{bertsimas2007learning, LCLS2010, chapelle2014, bastani2015online,
SBF2017}. Such growing availability of user-specific data has ushered in an
exciting era of personalized decision making, one that allows the decision
maker(s) to personalize the service decisions based on each individual's
distinct features. The key value added by personalized decision making is
that heterogeneity across individuals, a ubiquitous phenomenon in these
applications, can be intelligently exploited to achieve better outcomes -
because best recommendation decisions vary across different individuals.

Rising to this opportunity, contextual bandits have emerged to be the
predominant mathematical framework that is at once elegant and powerful: its
three components, the contexts (representing individual characteristics),
the actions (representing the recommended items), and the rewards
(representing the outcomes), capture the salient aspects of the problem and
provide fertile ground for developing algorithms that contribute to making
quality decisions. In particular, within the broad landscape of contextual
bandits, the batch\footnote{
Correspondingly, there has also been an extensive literature on online
contextual bandits, for example, ~\cite{LCLS2010,rusmevichientong2010linearly,FCGS2010,
rigollet2010nonparametric, chu2011contextual, goldenshluger2013linear,
AG2013a, AG2013b, RV2014, russo2016information, JBNW2017,
LLZ2017,abeille2017linear,dimakopoulou2017estimation,LLZ2017}, whose focus
is to develop online adaptive algorithms that effectively balance
exploration and exploitation. This is not the focus of our paper and we
simply mention them in passing here. See~\cite{BCN2012,
lattimore2018bandit,slivkins2019introduction} for a few articulate
expositions.} contextual bandits literature has precisely aimed to answer
the following questions that lie at the heart of data-driven decision
making: \textit{given a historical collection of past data that consists of
the three components as mentioned above, how can a new policy (mapping from
contexts to actions) be evaluated accurately, and one step further, how can
an effective policy be learned efficiently?}

Such questions--both policy evaluation and policy learning using historical
data--have motivated a flourishing and rapidly developing line of recent
work~(see, e.g, \cite{langford2011doubly, zhang2012estimating,zhao2012estimating,
zhao2014doubly, swaminathan2015batch, rakhlin2016bistro, kallus2017balanced,
kitagawa2018should, kallus2018confounding, zhou2018offline,
deep-learning-logged-bandit-feedback,chernozhukov2019semi}) that contributed
valuable insights: novel policy evaluation and policy learning algorithms
have been developed; sharp minimax regret guarantees have been characterized
(through a series of efforts) in many different settings; extensive and
illuminating experimental results have been performed to offer practical
advice for optimizing empirical performance.

However, a key assumption underlying the existing batch contextual bandits
work mentioned above is that the future environment in which the learned
policy is deployed stays the same as the past environment from which the
historical data is collected (and the to-be-deployed policy is trained). In
practice, such an assumption rarely holds and there are two primary sources
of such ``environment change":

\begin{enumerate}
\item \textbf{Covariate shift:} The individuals--and hence their
characteristics--in a population can change, thereby resulting in a
different distribution of the contexts. For instance, an original population
with more young people can shift to a population with more senior people.

\item \textbf{Concept drift:} How the rewards depend on the underlying
contexts and actions can also change, thereby resulting in different
conditional distributions of the rewards given the contexts and the actions.
For instance, individuals' preferences over products can shift over time and
sometimes exhibit seasonal patterns.
\end{enumerate}

As a consequence, these batch contextual bandit algorithms are \textbf{
fragile}: should the future environment change, the deployed policy--having
not taken into account the possible environment changes in the future--will
perform poorly. This naturally leads to the following fundamental question:
\textit{Can we learn a \textbf{robust} policy that performs well in the
presence of both of the above environment shifts?} Our goal in
this paper is to provide a framework for thinking about this question and
providing an affirmative answer therein.

\subsection{Our Contributions and Related Work}

Our contributions are threefold. First, we propose a distributionally robust
formulation of policy evaluation and learning in batch contextual bandits,
that accommodates both types of environment shifts mentioned above. Our
formulation postulates that the future environment--characterized by a joint
distribution on the context and all the rewards when taking different
actions--is in a Kullback-Leibler neighborhood around the training
environment's distribution, thereby allowing for learning a robust policy
from training data that is not sensitive to the future environment being the
same as the past. Despite the fact that there has been a growing literature
(see, e.g,
\cite
{bertsimas2004price,delage2010distributionally,hu2013kullback,shafieezadeh-abadeh_distributionally_2015,bayraksan2015data,gao2016distributionally,namkoong2016stochastic,duchi2016statistics,staib2017distributionally,shapiro2017distributionally,lam2017empirical,wolfram2018,sinha2018certifiable,volpi2018generalizing,raginsky_lee,nguyen2018distributionally,yang2018Wasserstein,MohajerinEsfahani2017,zhao2017distributionally,abadeh2018Wasserstein,ZHAO2018262,sinha2018certifiable,gao2018robust,wolfram2018,ghosh2019robust,blanchet2016quantifying,duchi2018learning,duchi2019distributionally,ho2020distributionally})
on distributionally robust optimization (DRO)--one that shares the same
philosophical underpinning on distributionally robustness as ours--the
existing DRO literature has mostly focused on the statistical learning
aspects, including supervised learning and feature selection type problems,
rather than the decision making aspects. To the best of our knowledge, we
provide the first distributionally robust formulation for policy evaluation
and learning under bandit feedback, in a general, non-parametric space.

Second, we provide a novel scheme for distributional robust policy
evaluation (Algorithm~\ref{alg:DRO_evaluation}) that estimates the robust
value of any given policy using historical data. We do so by drawing from
duality theory and transforming the primal robust value estimation
problem--an infinitely-dimensional problem--into a dual problem that is $1$
-dimensional and convex, hence admitting an efficiently computable solution (which is solved using Newton's method).
We then study the efficiency of this distributional robust estimator and establish, in the form of a central limit theorem, that the proposed
estimator converges to the true value at an $O_p\left(n^{-1/2}\right)$ rate ($
n $ is the number of data points).

Third, we build upon this distributional robust policy evaluation scheme to devise a corresponding distributional robust policy learning algorithm (Algorithm~\ref{alg:DRO_policy_learning}) and
provide a finite-sample regret guarantee for this policy learning scheme. In particular, by a uniform-convergence style argument, we show that (Theorem~\ref{thm:pi_policy}) our distributional robust policy learning algorithm achieves the minimax optimal $O_p(n^{-1/2})$ regret. This result highlights the optimality of our procedure and thus satisfactorily settles the learning problem. We also provide extensive experimental results (Section~\ref{sec:numericals})
to demonstrate the efficiency and effectiveness of the proposed
distributional robust policy evaluation and learning schemes.
Finally, we extend our results (Section~\ref{sec:extension}) to $f$-divergence measures (i.e. beyond KL-divergence) and show our framework is more broadly applicable.

\section{A Distributional Robust Formulation of Batch Contextual Bandits}

\label{sec:model}

\subsection{Batch Contextual Bandits}

Let $\mathcal{A}$ be the set of $d$ actions: $\mathcal{A}=\{a^{1},a^{2},
\dots ,a^{d}\}$ and let $\mathcal{X}$ be the set of contexts endowed with a $\sigma$-algebra (typically a
subset of $\reals^{p}$ with the Borel $\sigma$-algebra). Following the standard contextual bandits
model, we posit the existence of a fixed underlying data-generating
distribution on $(X,Y(a^{1}),Y(a^{2}),\dots ,Y(a^{d}))\in \mathcal{X}\times
\prod_{j=1}^{d}\mathcal{Y}_{j}$, where $X\in \mathcal{X}$ denotes the
context vector, and each $Y(a^{j})\in \mathcal{Y}_{j}\subset \reals$
denotes the random reward obtained when action $a^{j}$ is selected under
context $X$.

Let $\{(X_i, A_i, Y_i)\}_{i=1}^n$ be $n$ \textbf{iid} observed triples that
comprise of the training data, where the context and rewards
$(X_i, Y_i(a^1), \dots, Y_i(a^d))$ are
drawn \textbf{iid} from the fixed underlying distribution described above,
and we denote this underlying distribution by $\P _0$. Further, in the $i$
-th datapoint $(X_i, A_i, Y_i)$, $A_i$ denotes the action selected and $Y_i
= Y_i(A_i)$. In other words, $Y_i$ in the $i$-th datapoint is the observed
reward under the context $X_i$ and action $A_i$. Note that all the other
rewards $Y_i(a)$ (i.e. for $a \in \mathcal{A} - \{A_i\}$), even though they
exist in the model (and have been drawn according to the underlying joint
distribution), are not observed.

We assume the actions in the training data are selected by some fixed
underlying policy $\pi_0$ that is known to the decision-maker, where $
\pi_0(a\mid x)$ gives the probability of selecting action $a$ when the
context is $x$.

In other words, for each context $X_i$, a random action $A_i$ is selected
according to the distribution $\pi_0(\cdot \mid X_i)$, after which the
reward $Y_i(A_i)$ is then observed. Finally, we use $
 \P _0*\pi_0 $ to denote the product distribution on space $\mathcal{X}
\times \prod_{j=1}^d \mathcal{Y}_j\times \mathcal{A}$.

We make the following assumptions on the data-generating process.
\begin{assumption}\label{assump:classical}\quad
	The joint distribution $(X, Y(a^1), Y(a^2), \dots, Y(a^d), A)$ satisfies:
	\begin{enumerate}
	\item Unconfoundedness: $((Y(a^1),Y(a^2),\ldots,Y(a^d))$ is independent with $A$ conditional on $X$, i.e.,
	\[((Y(a^1),Y(a^2),\ldots,Y(a^d)) \indep A |X.
	\]

		\item Overlap:
		There exists some $\eta > 0$,  $\pi_0(a\mid x) \ge  \eta$, $\forall (x, a) \in \feas \times \actions$.
		\item Bounded reward support: $0 \leq Y(a^i)\leq M$ for $i=1,2,\ldots,d$.
		\item Positive density: For any $i=1,2,\ldots ,d,$ $Y(a^{i})|X$ has a conditional density $f_{i}(y_i|x)$ and $
f_{i}(y_i|x)$ has a uniform non-zero lower bound i.e., $ f_{i}(y_i|x)\geq \underline{b}>0$ over the interval $[0,M]$.
	\end{enumerate}
\end{assumption}
The overlap assumption ensures that some minimum positive probability is
guaranteed no matter what the context is. This ensures sufficient
exploration in collecting the training data. Assumptions \ref{assump:classical}.1 - \ref{assump:classical}.3 are
standard and commonly adopted in both the estimation literature (\cite
{rosenbaum1983central, imbens2004nonparametric, imbens2015causal}) and the
policy learning literature (\cite{zhang2012estimating,zhao2012estimating,
kitagawa2018should,swaminathan2015batch, zhou2015residual}).
Assumption \ref{assump:classical}.4 is made to ensure the $O_p(n^{-1/2})$ convergence rate.
\begin{remark}
	In standard contextual bandits terminology,
	$\mu_{a} (x)  \triangleq \E_{\P_0}[Y_i(a) \mid X_i = x]$ is known as the mean reward function (for action $a$). Depending on whether one assumes a parametric form of $\mu_{a} (x)$ or not, one needs to employ different statistical methodologies. In particular,  when $\mu_{a} (x)$ is a linear function of $x$, this is known as linear contextual bandits, an important and most extensively studied subclass of contextual bandits.
	In this paper, we do not make any structural assumption on $\mu_{a} (x)$: we are in the non-parametric contextual bandits regime and work with a general underlying data-generating distributions $\P_0$.

\end{remark}

\subsection{Standard Policy Learning}

With the above setup, the standard goal is to learn a good policy from a
fixed deterministic policy class $\Pi$ using the training data. This is often
known as the batch contextual bandits problem (in contrast to online
contextual bandits), because all the data has already been collected at once
before the decision maker aims to learn a policy. A policy $\pi: \mathcal{X}
\rightarrow \mathcal{A}$ is a function that maps a context vector $x$ to an
action and the performance of $\pi$ is measured by the expected reward
this policy generates, as characterized by the policy value function:
\begin{definition}\label{def:policy_value}\quad
	The policy value function $Q: \Pi \rightarrow \reals$ is defined as: $Q(\pi) \triangleq \E_{\P_0}[Y(\pi(X))]$, where the expectation is taken with respect to the randomness in the underlying joint distribution $\P_0$ of $(X, Y(a^1), Y(a^2), \dots, Y(a^d))$.
\end{definition}

With this definition, the optimal policy is a policy that maximizes the
policy value function. The objective in the standard policy learning context
is to learn a policy $\pi$ that has the policy value as large as possible,
or equivalently, to minimize the discrepancy between the performance of the
optimal policy and the performance of the learned policy $\pi$.

\subsection{Distributional Robust Policy Learning}

Using the policy value function $Q(\cdot)$ (as defined in Definition~\ref
{def:policy_value}) to measure the quality of a policy brings out an
implicit assumption that the decision maker is making: the environment that
generated the training data is the same as the environment where the policy
will be deployed. This is manifested in that the expectation in $Q(\cdot)$
is taken with respect to the same underlying distribution $\P_0$. However,
the underlying data-generating distribution may be different for the
training environment and the test environment. In such cases, the policy
learned with the goal to maximize the value under $\P_0$ may not work well
under the new test environment.

To address this issue, we propose a distributional robust formulation for
policy learning, where we explicitly incorporate into the learning phase the
consideration that the test distribution may not be the same as the training
distribution $\P_0$. To that end, we start by introducing some terminology.
First, the KL-divergence between two probability measures $\P $ and $\P _0$,
denoted by $D(\P ||\P _0)$, is defined as $D(\P ||\P _0) \triangleq \int \log\left(
\frac{d\P }{d\P _0}\right){\rm d}\P .$ With KL-divergence, we can define a class
of neighborhood distributions around a given distribution. Specifically, the
distributional uncertainty set $\mathcal{U}_{\P _0}(\delta)$ of size $\delta$
is defined as $\mathcal{U}_{\P _0}(\delta) \triangleq \{\P \ll \P _0\mid D(\P ||\P
_0)\leq \delta\}$, where  $\P \ll \P _0$ means $\P$ is absolutely continuous with respect to $\P _0$. When it is clear from the context what the uncertainty
radius $\delta$ is, we sometimes drop $\delta$ for notational simplicity and
write $\mathcal{U}_{\P _0}$ instead.

\begin{definition}\quad
	For a given $\delta > 0$, the distributionally robust value function $Q_{\mathrm{\rm DRO}}:\Pi \rightarrow \reals$ is defined as: $Q_{\mathrm{\rm DRO}}(\pi) \triangleq\inf_{\P\in\mathcal{U}_{\P_0}(\delta)} \E_{\P}[Y(\pi(X))]$.
\label{def:Q_DRO}
\end{definition}

In other words, $Q_{\mathrm{\rm DRO}}(\pi)$ measures the performance of a policy
$\pi$ by evaluating how it performs in the worst possible environment among
the set of all environments that are $\delta$-close to $\P_0$. With this definition, the optimal policy $\pi^*_\mathrm{\rm DRO}$
is a policy that maximizes the distributionally robust value function:
$\pi^*_\mathrm{\rm DRO} \in \arg \max_{\pi \in \Pi}  \{ Q_\mathrm{\rm DRO} (\pi)\}$. To be robust
to the changes between the test environment and the training environment,
our goal is to learn a policy such that its distributional robust policy
value is as large as possible, or equivalently, as close to the best
distributional robust policy as possible. We formalize this notion next.

\begin{definition}
	The distributional robust regret $R_{\mathrm{\rm DRO}}(\pi)$ of a  policy $\pi \in \Pi$ is defined as
	\\
	$R_{\mathrm{\rm DRO}}(\pi) \triangleq\max_{\pi' \in \Pi}\inf_{\P\in\mathcal{U}_{\P_0}(\delta)}\E_{\P}[Y(\pi'(X))] - \inf_{\P\in\mathcal{U}_{\P_0}(\delta)}\E_{\P}[Y(\pi(X))]$.
\label{def:regret}
\end{definition}

Several things to note.
First, per its definition, we can rewrite regret as
$R_{\rm DRO}(\pi) = Q_{\rm DRO}(\polo_\mathrm{\rm DRO}) - Q_{\rm DRO}(\pi)$.
Second, the underlying random policy that has generated the observational data (specifically the $A_i$'s)
need not be in $\Pi$.
Third, when a policy $\hat{\pi}$ is learned from data and hence a random variable (as will be the case in the current policy learning context),
$R(\hat{\pi}_{\rm DRO})$ is a random variable.
A regret bound in such cases is customarily a high probability bound that highlights
how regret scales as a function of the size $n$ of the dataset, the error probability and other important parameters of the problem (e.g. the complexity of the policy class $\Pi$).

\section{Distributional Robust Policy Evaluation}

\subsection{Algorithm}
\label{sec:alg}
In order to learn a distributionally robust policy--one that maximizes $Q_{
\mathrm{\rm DRO}}(\pi)$--a key step lies in accurately estimating the given
policy $\pi$'s distributionally robust value. We devote this section to
tackling this problem.

\begin{lemma}[Strong Duality] \quad\label{thm:strong_duality}
	For any policy $\pi\in\Pi$, we have
	\begin{align}
	\inf_{\P \in \mathcal{U}_{\P_0}(\delta)}\E_{\P}\left[Y(\pi(X))\right]
	&= \sup_{\alpha\geq 0}\left\{ -\alpha \log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta\right\}\\
	& = \sup_{\alpha\geq 0}\left\{ -\alpha \log\E_{\P_{0}*\pi_{0}}\left[
	\frac{\exp(-Y(A)/\alpha)\mathbf{1}\{\pi(X) = A\}}{\pi_0(A\mid X)}\right] - \alpha \delta\right\},
	\end{align}
where $\mathbf{1}\{\cdot \}$ denotes the indicator function.
\end{lemma}
\begin{proof}{Proof}
	The first equality follows from \citep[Theorem 1]{hu2013kullback}. The second equality holds, because
	for any (Borel measurable) function $f:\reals\rightarrow\reals$ and any policy $\pi\in\Pi$, we have
	\begin{equation}
	\E_{\P}\left[f(Y(\pi(X)))\right] = \E_{\P*\pi_0}\left[\frac{f(Y(\pi(X)))\mathbf{1}\{\pi(X) = A\}}{\pi_0(A\mid X)}\right] =
	\E_{\P*\pi_0}\left[\frac{f(Y(A))\mathbf{1}\{\pi(X) = A\}}{\pi_0(A\mid X)}\right].
	\end{equation}
	Plugging in $f(x) = \exp(-x/{\alpha})$ yields the result.
\end{proof}
\begin{remark}
When $\alpha=0$, by  \citep[Proposition 2]{hu2013kullback}, we can define
\begin{equation*}
 -\alpha\log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta |_{\alpha=0}= \essinf\{Y\},
    \end{equation*}
    where $\essinf$ denotes the essential infimum.
    Furthermore, $-\alpha\log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta$ is right continuous at zero. In fact, Lemma \ref{lemma:ld} in \ref{sec:thm1} shows that the optimal value is not attained at $\alpha = 0$.
\end{remark}

The above strong duality allows us to transform the original problem of
evaluating $Q_{\rm DRO}(\pi)=\inf_{\P \in \mathcal{U}_{\P _0(\delta)}}\mathbf{E}_{\P }\left[
Y(\pi(X))\right]$, where the (primal) variable is a infinity-dimensional distribution $\P $ into
a simpler problem where the (dual) variable is a positive scalar $\alpha$.
Note that in the dual problem, the expectation is taken with respect to the
same underlying distribution $\P _0$. This then allows us to use an
easily-computable plug-in estimate of the distributional robust policy
value.
For ease of reference in the subsequent analysis of our algorithm, we capture the important terms in the following
definition.

\begin{definition}
\label{def:phi_alpha}
	Let $\{(X_i, \W_i, Y_i)\}_{i=1}^n$ be a given dataset.
	We define
	\begin{equation*}W_i(\pi, \alpha) \triangleq \frac{\mathbf{1}\{\pi(X_i) = A_i\}}{\pi_0(A_i\mid X_i)}\exp(-Y_i(A_i)/\alpha), \ S_n^{\pi}\triangleq \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }
	\end{equation*}
	and
	\begin{equation*}
	\hat{W}_n(\pi,\alpha) \triangleq \frac{1}{nS_n^\pi}\sum_{i=1}^{n} W_i(\pi, \alpha).\end{equation*}
	We also define the dual objective function and the empirical dual objective function as
	\[\phi(\alpha,\pi)\triangleq -\alpha \log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta ,\]
	and
	\[\hat{\phi}_{n}(\pi,\alpha) \triangleq -\alpha \log \hat{W}_n(\pi, \alpha) - \alpha \delta,\]
	respectively.

	Then, we define the distributionally robust value estimators and the optimal dual variable using the notation above.
	\begin{enumerate}
		\item
		The distributionally robust value estimator $\hat{Q}_{\mathrm{\rm DRO}}:\Pi \rightarrow \reals$ is defined by $\hat{Q}_{\mathrm{\rm DRO}}(\pi) \triangleq\sup_{\alpha\geq 0}\left\{ \hat{\phi}_{n}(\pi,\alpha)\right\}$.
		\item
		The optimal dual variable  $\alpha ^{\ast }(\pi)$ is  defined by $\alpha ^{\ast }(\pi)\triangleq\arg \max_{\alpha \geq 0}\left\{\phi(\alpha,\pi)\right\}$.
	\end{enumerate}
\end{definition}
Notice that when we compute $\hat{W}_n(\pi,\alpha)$, we divide a
normalization factor $S_n^{\pi}$, which makes our evaluation more stable.

The upper bound of $\alpha^{\ast }(\pi)$ proven in Lemma  \ref{lemma:upper_bd} of  \ref{sec:thm1}
establishes the validity of the definitions $\alpha^{\ast}(\pi)$, namely, $
\alpha^{\ast}(\pi)$ is attainable and unique.

By \citep[Proposition 1]{hu2013kullback} and the discussion  following the proposition, we provide a characterization of the worst case distribution in Proposition \ref{prop:worst_case}.
\begin{proposition}[The Worst Case Distribution]
\label{prop:worst_case}
Suppose that Assumption \ref{assump:classical} is imposed. For any policy $\pi \in \Pi$,  we define  a probability measure $\P(\pi)$ supported on $\mathcal{X}\times
\prod_{j=1}^{d}\mathcal{Y}_{j}$ such that
\[
\frac{{\rm d}\P(\pi)}{{\rm d}\P_0} = \frac{\exp(-Y(\pi(X)/\alpha^*(\pi)))}{\E_{\P_0}[\exp(-Y(\pi(X)/\alpha^*(\pi)))]},
\]
where ${{\rm d}\P(\pi)}/{{\rm d}\P_0}$ is the Radon-Nikodym derivative. Then, we have ${\P(\pi)}$ is the unique worst case distribution, namely
\[\P(\pi) = \argmax_{\P\in\mathcal{U}_{\P_0}(\delta)} \E_\P[Y(\pi(X)].
\]
\end{proposition}
\begin{corollary}
\label{cor:worst_case}
Suppose that Assumption \ref{assump:classical} is imposed and under $\P_0$, $Y(a^{1}),\ldots,Y(a^{d})$ are mutually independent conditional on $X$.  Then, for any policy $\pi \in \Pi$, under the worst case measure $\P(\pi)$,  $Y(a^{1}),\ldots,Y(a^{d})$ are still mutually independent conditional on $X$.
\end{corollary}
The proof of Corollary \ref{cor:worst_case} is in \ref{sec:lma_cvx}.
To compute $\hat{Q}_{\mathrm{\rm DRO}}$, one need to solve
an optimization problem to obtain the distributionally robust estimate of
the policy $\pi$. As the following indicates, this optimization problem is
easy to solve.

\begin{lemma}
\label{lma:cvx}
	The empirical dual objective function $\hat{\phi}_{n}(\pi,\alpha)$ is concave in $\alpha$ and its partial derivative admits the expression
	\begin{eqnarray*}
	\frac{\partial}{\partial \alpha}
	\hat{\phi}_{n}(\pi,\alpha)
	&=& -\frac{\sum_{i=1}^n Y_i(A_i)W_i(\pi,\alpha)} {\alpha S_n^{\pi}\hat{W}_n(\pi, \alpha)}-\log \hat{W}_{n}(\pi,\alpha) - \delta,\\
    \frac{\partial^2}{\partial \alpha^2}
	\hat{\phi}_{n}(\pi,\alpha)
	&=& \frac{(\sum_{i=1}^n Y_i(A_i)W_i(\pi,\alpha))^2} {\alpha^3(S_n^{\pi})^2(\hat{W}_{n}(\pi,\alpha))^2}
	-\frac{\sum_{i=1}^n Y^2_i(A_i)W_i(\pi,\alpha)} {\alpha^3S_n^{\pi}\hat{W}_{n}(\pi,\alpha)}. \\
	\end{eqnarray*}
	Further, if the array $\{Y_i(A_i)\mathbf{1}\{\pi(X_i) = A_i\}\}_{i=1}^n$ has at least two different non-zero entries, then $\hat{\phi}_{n}(\pi,\alpha)$ is strictly-concave in $\alpha$.
\end{lemma}
The proof of Lemma \ref{lma:cvx} is in \ref{sec:lma_cvx}. Since the optimization problem $\hat{Q}_{\mathrm{\rm DRO}}=\max_{\alpha \geq 0}\left\{ \hat{\phi}_{n}(\pi,\alpha) \right\}$ is maximizing a concave function, it can be computed by the Newton-Raphson method. Finally, based on all of the discussions above, we formally give the distributionally robust policy evaluation algorithm in Algorithm~\ref{alg:DRO_evaluation}.
 By \citep[Section 8.8]{luenberger2015linear}, we have Algorithm~\ref{alg:DRO_evaluation} converges to the global maximum   $\hat{Q}_{\mathrm{DRO}}(\pi)$ quadratically, if the initial value of $\alpha$ is sufficiently closed to the optimal value.
\begin{algorithm}[ht]
	\caption{Distributionally Robust Policy Evaluation}
	\label{alg:DRO_evaluation}
	\begin{algorithmic}[1]
		\State \textbf{Input:} Dataset $\{(X_i, \W_i, Y_i)\}_{i=1}^n$, data-collecting policy $\pi_0$, policy $\pi \in \Pi$, and initial value of dual variable $\alpha$.
		\State \textbf{Output:} Estimator of the distributionally robust policy value $\hat{Q}_{\mathrm{\rm DRO}}(\pi)$.

		\Repeat
	    \State Let $W_i(\pi, \alpha) \gets  \frac{\mathbf{1}\{\pi(X_i) = A_i\}}{\pi_0(A_i \mid X_i)}\exp(-Y_i(A_i)/\alpha)$.
		\State Compute $\hat{W}_n(\pi,\alpha) \gets  \frac{1}{n}\sum_{i=1}^{n} W_i(\pi, \alpha)$.
		\State Compute $S_n^{\pi}\gets  \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }$.
		 \State Compute $\hat{W}_n(\pi,\alpha) \gets  \frac{1}{nS_n^{\pi}}\sum_{i=1}^{n} W_i(\pi, \alpha)$.
		\State
		Update $\alpha \gets  \alpha - (\frac{\partial}{\partial \alpha}\hat{\phi}_{n})/ (\frac{\partial^2}{\partial \alpha^2}\hat{\phi}_{n})$.
		\Until{$\alpha$ converge.}

		\State \textbf{Return} $\hat{Q}_{\mathrm{\rm DRO}}(\pi) \gets  \hat{\phi}_{n}(\pi,\alpha)$.
	\end{algorithmic}
\end{algorithm}

\subsection{Theoretical Guarantee of Distributionally Robust Policy
Evaluation}

In the next theorem, we demonstrate that the approximation error for
policy evaluation function $\hat{Q}_{\mathrm{\rm DRO}}(\pi)$ is $O_p(1/\sqrt{n})$
for a fixed policy $\pi$.

\begin{theorem}
	\label{DRO_CLT}
	Suppose Assumption \ref{assump:classical} is enforced, and
	define \[\sigma ^{2}(\alpha )=\frac{ \alpha^{2} }{\E\left[ W_i(\pi, \alpha)\right]^2} \mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi
(X)|X\right) } \left( \exp \left( -Y(\pi (X))/\alpha \right)
-\mathbf{E}\left[ \exp \left( -Y(\pi (X))/\alpha \right) \right] \right)
^{2} \right]. \]
	Then, for any policy $\pi\in\Pi$, we have
	\begin{equation}
	\sqrt{n}\left( \hat{Q}_{\mathrm{\rm DRO}}(\pi)  - Q_{\mathrm{\rm DRO}}(\pi)
	\right) \Rightarrow \mathcal{N}\left( 0,\sigma ^{2}(\alpha ^{\ast }(\pi))\right),
	\end{equation}
	where $\alpha^{\ast}(\pi)$ is defined in Definition \ref{def:phi_alpha}, $\Rightarrow$ denotes convergence in distribution, and $\mathcal{N}(0,\sigma^2)$ is the normal distribution with mean zero and variance $\sigma^2$.
\end{theorem}
\begin{proof}{Sketch of Proof}
The proof is based on the functional central limit theorem \citep[e.g.][Theorem 18.14]{van2000asymptotic} and the Delta theorem \citep[e.g.][Theorem 7.59]{shapiro2009lectures}.

We first show for every $\alpha \in (0,\infty)$,
\[
\sqrt{n}\left( \hat{W}_{n}(\pi ,\alpha )-\mathbf{E}[W_{i}(\pi ,\alpha
)]\right) \Rightarrow Z(\alpha),
\]
where
\[Z(\alpha) \sim \mathcal{N}\left(0, \mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi
(X)|X\right) } \left( \exp \left( -Y(\pi (X))/\alpha \right)
-\mathbf{E}\left[ \exp \left( -Y(\pi (X))/\alpha \right) \right] \right)
^{2} \right] \right). \]
Let $\mathcal{C}([\underline{\alpha}/2,2\overline{\alpha}])$ be the space of continuous functions supported on $[\underline{\alpha}/2,2\overline{\alpha }]$, equipped with the supremum norm, where
$0< \underline{\alpha}\leq\alpha^*(\pi)\leq\overline{\alpha }<\infty$. Then, by the functional central limit theorem \citep[e.g.][Theorem 18.14]{van2000asymptotic}, we have
 \begin{equation*}
\sqrt{n}\left( \hat{W}_{n}(\pi ,\cdot )-\mathbf{E}[W_{i}(\pi ,\cdot
)]\right) \Rightarrow Z\left( \cdot \right) ,
\end{equation*}
in the Banach  space $\mathcal{C}([\underline{\alpha}/2,2\overline{\alpha }])$.

We next apply the Delta theorem  \citep[e.g.][Theorem 7.59]{shapiro2009lectures}, which generalizes the Delta method to the infinity-dimensional space, and obtain that
\begin{equation*}
\sqrt{n}\left( V(\hat{W}_{n}(\pi ,\cdot ))-V(\mathbf{E}[W_{i}(\pi ,\cdot
)])\right) \Rightarrow V_{\mathbf{E}[W_{i}(\pi ,\cdot )]}^{\prime }\left(
Z\right),
\end{equation*}
where $V$ is a functional defined by
\begin{equation*}
V(\psi )=\inf_{\alpha \in \lbrack \underline{\alpha }/2,2\overline{\alpha }
]}\alpha \log \left( \psi (\alpha )\right) +\alpha \delta,
\end{equation*}
and $V_{\mu }^{\prime }\left( \nu \right) $ is the
directional derivative of $V\left( \cdot \right) $ at $\mu $ in the
direction of $\nu$, which is computable by  the Danskin theorem \citep[e.g.][Theorem 4.13]
{bonnansperturbation}.
Finally, we show $\mathbf{P}$($\hat{Q}_{\mathrm{DRO}}(\pi )\neq -V(\hat{W}
_{n}(\pi ,\alpha )))\rightarrow 0$ as $n\rightarrow \infty$, and complete the proof by Slutsky's lemma \citep[e.g.][Theorem 1.8.10]{lehmann2006theory}).
\end{proof}
The detailed proof of Theorem \ref{DRO_CLT} is in \ref{sec:thm1}.
\label{sec:CLT}

\section{Distributionally Robust Policy Learning}
\label{sec:algorithm}

In this section, we study the policy learning aspect of the problem and discuss both the algorithm and its corresponding finite-sample theoretical guarantee.
First, with the distributional robust policy evaluation scheme discussed in the previous section, we can in principle compute the the distributional robust optimal policy $\hat{\pi}_{\rm DRO}$ by picking a policy in the given policy class $\Pi$ that maximizes the value of
$\hat{Q}
_{\rm DRO}$, i.e.
\begin{equation}
\hat{\pi}_{\rm DRO}\in\argmax_{\pi \in \Pi }\hat{Q}_{\rm DRO}(\pi) = \argmax_{\pi
\in \Pi}\;\sup_{\alpha\geq 0}\left\{ -\alpha \log \hat{W}_n(\pi, \alpha) -
\alpha \delta\right\}.
\label{eqn:pi_hat}
\end{equation}

How do we compute $\hat{\pi}_{\rm DRO}$?
In general, this is a computationally intractable problem since
it is highly non-convex in its optimization variables ($\pi$ and $\alpha$ jointly).
However, following the standard tradition in the optimization literature, we can employ certain approximate schemes that, although do not guarantee global convergence, are computationally efficient and practically effective.

A simple and quite effective scheme is alternate minimization, given  in Algorithm \ref{alg:DRO_policy_learning}, where we learn $\hat{\pi}_{\mathrm{\rm DRO}}$ by fixing $\alpha$ and minimizing on $\pi$ and then fixing $\pi$ and minimizing on $\alpha$ in each iteration. Since the value of $\hat{Q}_\mathrm{DRO}(\pi)$ is non-decreasing along the iterations of Algorithm \ref{alg:DRO_policy_learning}, the converged solution obtained from Algorithm \ref{alg:DRO_policy_learning} is a local maximum of $\hat{Q}_\mathrm{DRO}$. In practice, to accelerate the algorithm, we only iterate once for $\alpha$ (line 8) using the  Newton-Raphson step $\alpha \gets \alpha - (\frac{\partial}{\partial \alpha}\hat{\phi}_{n})/ (\frac{\partial^2}{\partial \alpha^2}\hat{\phi}_{n})$.
Subsequent simulations (see next section) show that this is often good enough.

\begin{algorithm}
	\caption{Distributionally Robust Policy Learning}
	\label{alg:DRO_policy_learning}
	\begin{algorithmic}[1]
		\State\textbf{Input:} Dataset $\{(X_i, \W_i, Y_i)\}_{i=1}^n$, data-collecting policy $\pi_0$, and initial value of dual variable $\alpha$.
		\State \textbf{Output:} Distributionally robust optimal policy $\hat{\pi}_{\mathrm{\rm DRO}} $.

		\Repeat
	    \State Let $W_i(\pi, \alpha) \gets  \frac{\mathbf{1}\{\pi(X_i) =  A_i\}}{\pi_0(A_i \mid X_i)}\exp(-Y_i(A_i)/\alpha)$.
		\State Compute $S_n^{\pi}\gets  \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }$.
		\State Compute $\hat{W}_n(\pi,\alpha) \gets  \frac{1}{nS_n^{\pi}}\sum_{i=1}^{n} W_i(\pi, \alpha)$.
		\State
		Update $\pi \gets  \argmin
		_{\pi\in \Pi}\hat{W}_n(\pi,\alpha)$.
		\State
		Update $\alpha \gets \argmax_{\alpha>0}  \{\hat{\phi}_n(\pi,\alpha)\}$.
		\Until{$\alpha$ converge.}

		\State \textbf{Return} $\pi$.
	\end{algorithmic}
\end{algorithm}

\subsection{Statistical Performance Guarantee}

We now establish the finite-sample statistical performance guarantee for the distributional
robust optimal policy $\hat{\pi}_{\rm DRO}$.  Before
giving the theorem, we need to first define entropy integral in the policy
class, which represents the class complexity.
\begin{definition}
	Given the feature domain $\mathcal{X}$, a policy class $\Pi ,$ a set of $n$
	points $\{x_{1},\ldots ,x_{n}\}\subset \mathcal{X}$, define:
	\begin{enumerate}
		\item Hamming distance between any two policies $\pi _{1}$ and $\pi _{2}$ in
		$\Pi :H(\pi _{1},\pi _{2})=\frac{1}{n}\sum_{j=1}^{n}\mathbf{1}\{\pi
		_{1}(x_{j})\neq \pi _{2}(x_{j})\}.$

		\item $\epsilon $-Hamming covering number of the set $\{x_{1},\ldots
		,x_{n}\}:N_{H}^{\left( n\right) }\left( \epsilon ,\Pi ,\{x_{1},\ldots
		,x_{n}\}\right) $ is the smallest number $K$ of policies $\{\pi _{1},\ldots
		,\pi _{K}\}$ in $\Pi $, such that $\forall \pi \in \Pi ,\exists \pi
		_{i},H(\pi ,\pi _{i})\leq \epsilon .$

		\item $\epsilon $-Hamming covering number of $\Pi :N_{H}^{\left( n\right)
		}\left( \epsilon ,\Pi \right) \triangleq\sup \left\{ N_{H}^{(n)}\left( \epsilon ,\Pi
		,\{x_{1},\ldots ,x_{n}\}\right) |x_{1},\ldots ,x_{n}\in \mathcal{X}\right\} .
		$

		\item Entropy integral: $\kappa ^{(n)}\left( \Pi \right) \triangleq\int_{0}^{1}\sqrt{
			\log N_{H}^{\left( n\right) }\left( \epsilon^2 ,\Pi \right) }{\rm d}\epsilon .$
	\end{enumerate}
\end{definition}
Then, Theorem \ref{DRO_Uniform} demonstrates that with high probability, the distributional robust regret   of the learned policy $R_{\rm DRO}(\hat{\pi}_{\rm DRO})$ decays at a rate upper bounded by $O_p(\kappa^{(n)}/\sqrt{n})$. Notice that by Theorem \ref{DRO_CLT}, the lower bound of $R_{\rm DRO}(\hat{\pi}_{\rm DRO})$  is $O_p(1/\sqrt{n})$. Therefore, if $\kappa^{(n)} =O(1)$, the upper bound and lower bound match up to a constant.
\begin{theorem}
Suppose Assumption \ref{assump:classical} is enforced. With probability  at least $1-\varepsilon$, we have
\begin{equation}
R_{\rm DRO}(\hat{\pi}_{\rm DRO})  \leq \frac{4}{\underline{b}\eta\sqrt{n}}\left( (\sqrt{2}+1)\kappa ^{(n)}\left( \Pi \right)  +\sqrt{2\log\left(\frac{2}{\varepsilon}\right)}+C\right), \label{eqn:uniform_bd}
\end{equation}
where $C$ is a universal constant$.$ \label{DRO_Uniform}
\end{theorem}
\begin{proof}{Sketch of proof}
Lemma \ref{lma:quantile} is a key to the proof.
\begin{lemma}
\label{lma:quantile}
For any probability measures $\mathbf{P}_{1},\mathbf{P}_{2}$ supported on $\reals$, we have
\begin{equation*}
\left\vert \sup_{\alpha \geq 0}\left\{ -\alpha \log \mathbf{E}_{\mathbf{P}
_{1}}\left[ \exp \left( -Y/\alpha \right) \right] -\alpha \delta \right\}
-\sup_{\alpha \geq 0}\left\{ -\alpha \log \mathbf{E}_{\mathbf{P}_{2}}\left[
\exp \left( -Y/\alpha \right) \right] -\alpha \delta \right\} \right\vert
\leq \sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left( t\right)
-q_{\mathbf{P}_{2}}\left( t\right) \right\vert,
\end{equation*}
where $\mathbf{
P}$ denotes the $t$-quantile of a probability measure $\P$, defined as
\begin{equation*}
q_{\mathbf{P}}\left( t\right) \triangleq\inf \left\{ x\in \reals:t\leq F_{
\mathbf{P}}\left( x\right) \right\} ,
\end{equation*}
where $F_\P$ is the CDF of $\mathbf{P.}$
\end{lemma}
Furthermore, if probability measures $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ supported
on $[0,M]$, and $\mathbf{P}_{1}$ has a positive density $f_{\mathbf{P}
_{1}}\left( \cdot \right) $ with a lower bound $f_{\mathbf{P}_{1}}\geq
\underline{b}$ over the interval $[0,M]$, we have
\begin{equation*}
\sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left( t\right) -q_{
\mathbf{P}_{2}}\left( t\right) \right\vert \leq \frac{1}{\underline{b}}
\sup_{x\in \lbrack 0,M]}\left\vert F_{\mathbf{P}_{1}}\left( x\right) -F_{
\mathbf{P}_{2}}\left( x\right) \right\vert .
\end{equation*}
 Then, notice that
$R_{\rm DRO}(\hat{\pi}_{\rm DRO})
\leq 2\sup_{\pi \in \Pi }\left\vert \hat{Q}_{\rm DRO}(\pi )-Q_{\rm DRO}(\pi
)\right\vert,$
and
\begin{equation*}
\hat{Q}_{\rm DRO}(\pi )
=\sup_{\alpha \geq 0}\left\{ -\alpha \log \left[ \mathbf{E
}_{\mathbf{\hat{P}}_{n}}\exp \left( -Y_{i}(\pi (X_{i})\right) /\alpha )
\right]  -\alpha \delta \right\}
.
\end{equation*}
where $\mathbf{\hat{P}}_{n}$ is the weighted empirical distribution, defined by
\begin{equation*}
\mathbf{\hat{P}}_{n}^{\pi }\triangleq\frac{1}{nS_{n}^{\pi }}\sum_{i=1}^{n}\frac{
\mathbf{1\{}\pi (X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }
\delta \left( Y_{i},X_{i}\right) .
\end{equation*}
Therefore, by Lemma \ref{lma:quantile}, we have
\begin{eqnarray*}
&&R_{\rm DRO}(\hat{\pi}_{\rm DRO})  \notag \\
&\leq &2\sup_{\pi \in \Pi }\left\vert \sup_{\alpha \geq 0}\left\{ -\alpha
\log \left[ \mathbf{E}_{\mathbf{\hat{P}}_{n}}\exp \left( -Y_{i}(\pi
(X_{i})\right) /\alpha )\right] -\alpha \delta \right\} -\sup_{\alpha \geq
0}\left\{ -\alpha \log \left[ \mathbf{E}_{\mathbf{P}_{0}}\exp \left( -Y(\pi
(X)\right) /\alpha )\right] -\alpha \delta \right\} \right\vert \\
&\leq &\sup_{\pi \in \Pi }\sup_{x\in \lbrack 0,M]}\frac{1}{\underline{b}}
\left\vert \mathbf{E}_{\mathbf{\hat{P}}_{n}}\left[ \mathbf{1}\left\{
Y_{i}(\pi (X_{i}))\leq x\right\} \right] -\mathbf{E}_{_{\mathbf{P}_{0}}}\left[
\mathbf{1}\left\{ Y_{i}(\pi (X_{i}))\leq x\right\} \right] \right\vert  \\
&\leq &\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}
\left\vert \left( \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi
(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}
\left\{ Y_{i}(\pi (X_{i}))\leq x\right\} \right) -\mathbf{E}_{_{\mathbf{P}
_{0}}}\left[ \frac{\mathbf{1\{}\pi (X)=A_{i}\mathbf{\}}}{\pi _{0}\left(
A|X\right) }\mathbf{1}\left\{ Y(\pi (X))\leq x\right\} \right] \right\vert \\
&&+\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}\left\vert
\left( \frac{S_{n}^{\pi }-1}{nS_{n}^{\pi }}\sum_{i=1}^{n}\frac{\mathbf{1\{}
\pi (X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}
\left\{ Y(\pi (X_{i}))\leq x\right\} \right) \right\vert .
\end{eqnarray*}
Define the function classes,
\begin{eqnarray*}
\mathcal{F}_{\Pi }&\triangleq&\left \{\left. f_{\pi }(X,A)=\frac{\mathbf{1}\{\pi
(X)=A\}}{\pi_0(A|X)}\right|\pi \in \Pi \right\}, \text{ and } \\
\mathcal{F}_{\Pi ,x}&\triangleq&\left\{ f_{\pi ,x}(X,Y,A)=
\left. \frac{\mathbf{1\{}\pi (X)=A\mathbf{\}1\{}Y(\pi (X))\leq x\}}{\pi_0(A|X)}\right|\pi \in \Pi ,x\in
\lbrack 0,M]\right\} .
\end{eqnarray*}
By \citep[Theorem 4.10]{wainwright2019high}, we have with probability at least $1-2\exp \left( -
n\epsilon ^{2}\eta ^{2}/2\right) $,
\begin{equation*}
R_{\rm DRO}(\hat{\pi}_{\rm DRO})\leq \frac{2}{\underline{b}}\left( 2\mathcal{R}_{n}\left(
\mathcal{F}_{\Pi ,x}\right)+\epsilon \right) + \frac{2}{
\underline{b}} \left( 2\mathcal{R}_{n}\left(
\mathcal{F}_{\Pi }\right)  +\epsilon \right),
\end{equation*}
where $\mathcal{R}_{n}$ denotes the Rademacher complexity. Finally, by Dudley's theorem \citep[e.g.][(5.48)]{wainwright2019high} and a standard technique to bound the Rademacher complexity, we are able to arrive the desired results.
\end{proof}
The detailed proof is in \ref{sec:proof_uniform}. From \eqref{eqn:uniform_bd},
 we see the bound for  the distributional robust regret  does not depend on the uncertainty size $\delta$. Furthermore, if $\sup_n \kappa ^{(n)} < \infty$, we have a parametric convergence rate $O_p(1/\sqrt{n})$ and if $ \kappa ^{(n)} =o_p(\sqrt{n})$, we have $R_{\rm DRO}(\hat{\pi}_{\rm DRO})\rightarrow0$ in probability.
\label{sec:uniform_convergence}
\section{Numerical Experiments}
\label{sec:numericals}
In this section, we provide discussions on numerical experiments to justify the robustness of the proposed DRO policy $\hat{\pi}_{\rm DRO}$ in the linear policy class. Specifically, Section \ref{sec:numerical_bayes} discuss a notion of the Bayes DRO policy, which is viewed as a benchmark; Section \ref{sec:numerical_linear_class} presents an approximation algorithm to learn a linear policy efficiently; Section \ref{sec:numerical_small} gives a visualization of the learned DRO policy, with a comparison to the benchmark Bayes DRO policy; in Section \ref{sec:numerical_nonlinear}, we study the performance of our proposed estimator, where we learn a linear policy in a non-linear boundary problem.
\subsection{Bayes DRO Policy}
\label{sec:numerical_bayes}
In this section, we give a characterization of the Bayes DRO policy $\overline{\pi}^*_{\rm DRO} $, which maximizes the distributionally robust value function within the class of all measurable policies, i.e.,
\[
\overline{\pi}^*_{\rm DRO}\in \argmax_{\pi \in \overline{\Pi}}\{Q_{\rm DRO}(\pi)\},
\]
where $\overline{\Pi}$ denotes the class of all measurable mappings from $\mathcal{X}$ to the action set $\mathcal{A}$. Despite that the Bayes DRO policy is not learnable given finitely many training samples, it could be a benchmark in the simulation study. Proposition \ref{thm:pi_policy} shows how to compute $\overline{\pi}^*_{\rm DRO}$ if we know the population distribution.
\begin{proposition} \label{thm:pi_policy}Suppose that for any $\alpha>0$ and any $a \in \mathcal{A}$, the mapping $x\mapsto \E_{\P_0}\left[\left. \exp\left(-Y(a)/\alpha\right)\right| X=x \right]$ is measurable. Then, the  Bayes DRO policy is
\[
\overline{\pi}^*_\mathrm{\rm DRO}(x) \in  \argmin_{a\in \mathcal{A}}\left\{ \E_{\P_0}\left[\left. \exp\left(-\frac{Y(a)}{\alpha^*(\overline{\pi}^*_{\rm DRO})}\right)\right| X=x \right]\right\},
\]
 where $\alpha^*(\pi^*_{\rm DRO})$ is an optimizer of the following optimization problem:
\begin{equation}
\alpha^*(\overline{\pi}^*_{\rm DRO})\in \argmax_{\alpha \geq 0} \left \{-\alpha \log\E_{\P_0}\left [\min_{a\in \mathcal{A}}\left\{ \E_{\P_0}\left[\left. \exp\left(-Y(a)/\alpha\right)\right| X\right] \right\}\right] - \alpha \delta \right \}.
\label{eq:alpha_DRO_small}
\end{equation}
\end{proposition}
See \ref{sec:proof_numerical_small} for the proof.
\begin{remark} $\overline{\pi}_{\rm DRO}^*$ only depends on the marginal distribution of $X$ and the conditional distributions of $Y(a^i)|X,i=1,2,\ldots,d$, and the conditional correlation structure of $Y(a^i)|X,i=1,2,\ldots,d$ does not affect $\overline{\pi}_{\rm DRO}^*$.
 \end{remark}
\subsection{Linear Policy Class and Logistic Policy Approximation}
\label{sec:numerical_linear_class}

\newcommand{\Thetalin}{\hat{\Theta}_{\rm{Lin}}}
\newcommand{\pilin}{\hat{\pi}_{\rm{Lin}}}
\newcommand{\Pilin}{\Pi_{\rm{Lin}}}

In this section, we introduce the linear policy class $\Pilin$. We consider $\mathcal{X}$ to be a subset of $\mathbf{R}^p$, and the action set $\mathcal{A}=\{1,2,\ldots,d\}$. To capture the intercept, it is convenient to include the constant variable 1 in $X\in\mathcal{X}$, thus in the rest of Section \ref{sec:numerical_linear_class},  $X$ is a $p+1$ dimensional vector and $\mathcal{X}$ will be a subset of $\mathbf{R}^{p+1}$. Each policy $\pi\in \Pilin$ is parameterized by a set of $d$ vectors $\Theta = \{\theta_a\in\mathbf{R}^{p+1}:a\in\mathcal{A}\} \in \mathbf{R}^{(p+1)\times d}$, and the mapping $\pi: \mathcal{X}\rightarrow \mathcal{A}$ is defined as
\[
\pi_{\Theta}(x) \in  \argmax_{a\in \mathcal{A}} ~
\left\{
\theta_a^{\top} x
\right\}.
\]
The optimal parameter for linear policy class is characterized by the optimal solution of  \linebreak
$\max_{\Theta\in \mathbf{R}^{(p+1)\times d}}
\mathbf{E}_{\mathbf{P}_0}[
Y(\pi_{\Theta}(X))].
$
Due to the fact that
$
\mathbf{E}_{\mathbf{P}_0}[
Y(\pi_{\Theta}(X))]
= \E_{\P*\pi_0}\left[\frac{Y(A)\mathbf{1}\{\pi_{\Theta}(X) = A\}}{\pi_0(A\mid X)}\right]$, the associated sample average approximation problem for optimal parameter estimation is
\[
\max_{\Theta\in \mathbf{R}^{(p+1)\times d}} \frac{1}{n}\sum_{i=1}^{n}\frac{Y_i(A_i)\mathbf{1\{}\pi_{\Theta}(X_{i})=A_{i}\mathbf{\}}}{\pi_{0}\left( A_{i}|X_{i}\right) }.
\]
However, the objective in above optimization problem is non-differentiable and non-convex, thus we approximate the indicator function using a softmax mapping by
$$
\mathbf{1\{}\pi_{\Theta}(X_{i})=A_{i}\mathbf{\}}
\approx
\frac{
\exp(\theta_{A_i}^{\top}X_i)}{ \sum_{a = 1}^{d}\exp(\theta_{a}^{\top}X_i)},
$$
which leads to an optimization problem with smooth objective:
\begin{equation*}

\max_{\Theta\in \mathbf{R}^{(p+1)\times d}} \frac{1}{n}\sum_{i=1}^{n}\frac{Y_i(A_i)
\exp(\theta_{A_i}^{\top}X_i)}{\pi_{0}\left( A_{i}|X_{i}\right) \sum_{a = 1}^{d}\exp(\theta_{a}^{\top}X_i)}.
\end{equation*}
We employ the gradient descent method to solve for the optimal parameter
\[
\Thetalin
\in \argmax_{\Theta\in \mathbf{R}^{(p+1)\times d}}
\left\{
\frac{1}{n}\sum_{i=1}^{n}\frac{Y_i(A_i)
\exp(\theta_{A_i}^{\top}X_i)}{\pi_{0}\left( A_{i}|X_{i}\right) \sum_{a = 1}^{d}\exp(\theta_{a}^{\top}X_i)}\right\},
\]
and define the policy $\pilin\triangleq\pi_{\Thetalin}$ as our linear policy estimator. In Section \ref{sec:numerical_small} and \ref{sec:numerical_nonlinear}, we justify the efficacy of $\pilin$ by empirically showing $\pilin$ is capable of discovering the (non-robust) optimal decision boundary.

As an oracle in Algorithm \ref{alg:DRO_policy_learning}, a similar smoothing technique will be adopted to solve  \linebreak$\argmin_{\pi\in \Pilin}\hat{W}_n(\pi,\alpha)$ for linear policy class $\Pilin$. We omit the details here due to space limit.

We will present an upper bound of the entropy integral $\kappa^{(n)}(\Pilin)$ in Lemma 4. By plugging the result of Lemma \ref{lemma:linear-class-complexity} into Theorem \ref{DRO_Uniform}, One can quickly remark that the regret $R_{\rm{DRO}}(\hat{\pi}_{\rm DRO})$ achieves the optimal asymptotic convergence rate $O_p(1/\sqrt{n})$ given by Theorem \ref{DRO_Uniform}.

\begin{lemma}
\label{lemma:linear-class-complexity} There exists a universal constant $C$ such that $\sup_n \kappa^{(n)}(\Pilin) \leq C\sqrt{dp \log(d)\log(dp)}.$
\end{lemma}

The proof of Lemma \ref{lemma:linear-class-complexity} is achieved by upper bounding $\epsilon $-Hamming covering number  $N_{H}^{\left( n\right)
}\left(\epsilon ,\Pilin \right)$ in terms of a generalization of the Vapnik-Chervonenkis dimension for multiclass problems, called the
\emph{graph dimension} (see definition in \cite{bendavid1995characterizations}), then deploy an upper bound of graph dimension for linear policy class provided in \cite{daniely2012multiclass}.

\subsection{A Toy Example}
\label{sec:numerical_small}
In this section, we present a simple example with an explicitly computable optimal linear DRO policy, in order to justify the effectiveness of linear policy learning introduced in Section \ref{sec:numerical_linear_class} and distributionally robust policy learning in Section \ref{sec:algorithm}.

We consider $\mathcal{X} =\{x =
(x(1),\ldots,x(p))\in \reals^p :\sum_{i=1}^p x(i)^2 \leq1 \}$ to be a $p$-dimensional closed unit ball, and the action set $\mathcal{A}=\{1,\ldots,d\}$.  We assume that $Y(i)$'s are mutually independent conditional on $X$ with conditional distribution
\[
Y(i)|X \sim \mathcal{N}(\beta_i^\top X,\sigma_i^2),\text{ for }i=1,\ldots,d.
\]
for vectors $\{\beta_1,\ldots,\beta_d\} \subset \reals^p$ and $\{\sigma_1^2,\ldots,\sigma_d^2\} \subset \reals_{+}$. In this case, by directly computing the moment generating functions and applying Proposition \ref{thm:pi_policy}, we have
\[
\overline{\pi}^*_\mathrm{\rm DRO}(x) \in  \argmax_{i\in \{ 1,\ldots,d\}}\left\{\beta_i^\top x-\frac{\sigma^2_i}{2\alpha^*(\pi^*_{\rm DRO})}\right\}.
\]
We consider the linear policy class $\Pilin$. Apparently, the DRO Bayes policy $\overline{\pi}^*_\mathrm{\rm DRO}(x)$ is in the class $\Pilin$, thus it is also the optimal linear DRO policy, i.e., $\overline{\pi}_{\rm DRO}^* \in \argmax_{\pi\in\Pilin} Q_{DRO}(\pi)$. Consequently, we can check the efficacy of the distributionally robust policy learning algorithm by comparing $\hat{\pi}_{\rm{DRO}}$ against $\overline{\pi}_{\rm DRO}^*$.

Now we describe the parameter in the experiment. We choose $p = 5$ and $d = 3$. To facilitate visualization of the decision boundary, we set all the entries of $\beta_i$ be $0$ except the first two dimensions. Specifically, we choose
\begin{align*}
    \beta_{1} = (1,0,0,0,0),&&
    \beta_{2} = (-1/2,\sqrt{3}/2,0,0,0),&&
    \beta_{3} = (-1/2,-\sqrt{3}/2,0,0,0).
\end{align*}
and $
    \sigma_{1} = 0.2,
    \sigma_{2} = 0.5,
    \sigma_{3} = 0.8.$
We define the Bayes policy $\bar{\pi}^{\ast}$ as the policy that maximizes $\mathbf{E}_{\mathbf{P}_0}[Y(\pi(X))]$ within the class of all measurable policies. Under above setting, $\bar{\pi}^{\ast}(x)\in \argmax_{i = 1,2,3}\{\beta_i^{\top}x\}$. The feature space $\mathcal{X}$ can be partitioned into three regions based on $\bar{\pi}^{\ast}$: for $i = 1,2,3$, we say $x\in\mathcal{X}$ belongs to Region $i$ if $\bar{\pi}^{\ast}(x) = i$. Given $X$, the action $A$ is drawn according to the underlying data collection policy $\pi_0$, which is described in Table \ref{tab:policy-prob}.
\begin{table}[!ht]
    \centering
    \begin{tabular}{|c|c|c|c|}
         \hline
         &Region 1&Region 2& Region  3\\\hline
         Action 1& 0.50&0.25&0.25\\
         \hline
         Action 2& 0.25&0.50&0.25\\
         \hline
         Action 3& 0.25&0.25&0.50\\
         \hline
    \end{tabular}
    \caption{The probabilities of selecting an action based on $\pi_0$ in linear example.}
    \label{tab:policy-prob}
\end{table}

We generate $\{X_i, A_i, Y_i\}_{i = 1}^n$ according to the   procedure described above as training dataset, from which we learn the non-robust linear policy $\pilin$ and distributionally robust linear policy $\hat{\pi}_{\rm{DRO}}$. Figure \ref{fig:simple-data} presents the decision boundary of four different policies: (a) $\bar{\pi}^{\ast}$;
(b) $\pilin$;
(c) $\bar{\pi}^{\ast}_{\rm{DRO}}$;
(d) $\hat{\pi}_{\rm{DRO}}$, where $n = 5000$ and $\delta = 0.2$. One can quickly remark that the decision boundary of $\pilin$ resembles $\bar{\pi}^{\ast}$; and the decision boundary of $\hat{\pi}_{\rm{DRO}}$ resembles $\bar{\pi}^{\ast}_{\rm{DRO}}$, which demonstrates that $\pilin$ is the (nearly) optimal non-DRO policy and $\hat{\pi}_{\rm{DRO}}$ is the (nearly) optimal DRO policy.

This distinction between $\bar{\pi}^{\ast}$ and $\bar{\pi}^{\ast}_{\rm{DRO}}$ is also apparent in Figure \ref{fig:simple-data}: $\bar{\pi}^{\ast}_{\rm{DRO}}$ is less likely to choose Action 3, but more likely to choose Action 1.
In words, distributionally robust policy prefers action with smaller variance.

\begin{figure}[t!]
    \begin{center}
    \includegraphics[width = \textwidth]{ThreeActBall.pdf}
    \end{center}
    \caption{Comparison of decision boundaries for different policies in linear example: (a) Bayes policy $\bar{\pi}^{\ast}$; (b) linear policy $\pilin$; (c) Bayes distributionally robust policy $\overline{\pi}_{\rm DRO}^*$; (d) distributionally robust linear policy
    $\hat{\pi}_{\rm DRO}$. We visualize the actions selected by different policies against the value of $(X(1),X(2))$. Training set size $n = 5000$; size of distributional uncertainty set $\delta = 0.2$.}
    \label{fig:simple-data}
\end{figure}

\subsection{A Non-linear Boundary Example}\label{sec:numerical_nonlinear}

In this section, we compare the performance of different estimators in a simulation environment where the Bayes decision boundaries are nonlinear.

We consider $\mathcal{X} = [-1,1]^5$ to be a $5$-dimensional cube, and the action set $\mathcal{A}=\{1,2,3\}$. We assume that $Y(i)$'s are mutually independent conditional on $X$ with conditional distribution
\[
Y(i)|X \sim \mathcal{N}(\mu_i(X), \sigma_i^2),\text{ for }i=1,2,3.
\]
where $\mu_i: \mathcal{X}\rightarrow \mathcal{A}$ is a measurable function and $\sigma_i \in \mathbf{R}_{+}$ for $i = 1,2,3$. In this setting, we are still able to analytically compute the Bayes policy $\bar{\pi}^{\ast}(x) \in
\argmax_{i = 1,2,3} \{\mu_i(x)\}
$ and the DRO Bayes $\bar{\pi}^{\ast}_{\rm{DRO}}(x) \in
\argmax_{i = 1,2,3} \left\{\mu_i(x)-\frac{\sigma^2_i}{2\alpha^*(\pi^*_{\rm DRO})}\right\}$.

In this section, the conditional mean $\mu_i(x)$ and conditional variance $\sigma_i$ are chosen as
\begin{align*}
\begin{array}{lr}
    \mu_1(x) = 0.2 x(1),
    &\hspace{1.5in} \sigma_1 = 0.8,
    \\
    \mu_2(x) = 1 - \sqrt{
    (x(1)+0.5)^2+(x(2) - 1)^2
    },
    &\hspace{1.5in} \sigma_2 = 0.2,
    \\
    \mu_3(x) = 1 - \sqrt{
    (x(1)+0.5)^2+(x(2) + 1)^2
    }),
    & \hspace{1.5in}\sigma_3 = 0.4.
    \\
\end{array}
\end{align*}
Given $X$, the action $A$ is drawn according to the underlying data collection policy $\pi_0$ described in Table  \ref{tab:policy-prob-linear}.
\begin{table}[!ht]
    \centering
    \begin{tabular}{|c|c|c|c|}
         \hline
         &Region 1&Region 2& Region  3\\\hline
         Action 1& 0.50&0.25&0.25\\
         \hline
         Action 2& 0.30&0.40&0.30\\
         \hline
         Action 3& 0.30&0.30&0.40\\
         \hline
    \end{tabular}
    \caption{The probabilities of selecting an action based on $\pi_0$ in nonlinear example.}
    \label{tab:policy-prob-linear}
\end{table}

Now we generate the training set $\{X_i, A_i, Y_i\}_{i = 1}^n$ and learn the non-robust linear policy $\pilin$ and distributionally robust linear policy $\hat{\pi}_{\rm{DRO}}$ in linear policy class $\Pilin$, for $n = 5000$ and $\delta = 0.2$. Figure \ref{fig:complex-data} presents the decision boundary of four different policies: (a) $\bar{\pi}^{\ast}$;
(b) $\pilin$;
(c) $\bar{\pi}^{\ast}_{\rm{DRO}}$;
(d) $\hat{\pi}_{\rm{DRO}}$. As $\bar{\pi}^{\ast}$ and $\bar{\pi}^{\ast}_{\rm{DRO}}$ have nonlinear decision boundaries, any linear policy is incapable of accurate recovery of Bayes policy. However, we quickly notice that the boundary produced by $\pilin$ and $\hat{\pi}_{\rm{DRO}}$ are reasonable linear approximation of $\bar{\pi}^{\ast}$ and $\bar{\pi}^{\ast}_{\rm{DRO}}$, respectively. It is also noteworthy that the robust policy prefers action with small variance (Action 2), which is consistent with our finding in Section \ref{sec:numerical_linear_class}.

\begin{figure}[!ht]
    \begin{center}
    \includegraphics[width = \textwidth]{Complex_2.pdf}
    \end{center}
    \caption{Comparison of decision boundaries for different policies in nonlinear example: (a) optimal policy under population distribution $\mathbf{P}_0$; (b) optimal linear policy $\pilin$ learned from data; (c) Bayes distributionally robust policy $\overline{\pi}_{\rm DRO}^*$; (d) distributionally robust linear policy
    $\hat{\pi}_{\rm DRO}$. We visualize the actions selected by different policies against the value of $(X(1),X(2))$. Training size is 5000; size of distributional uncertainty set $\delta = 0.2$.}
    \label{fig:complex-data}
\end{figure}

Now we introduce two evaluation metrics in order to quantitatively characterize the adversarial performance.

\begin{enumerate}
    \item We generate a test set with $n'=2500$ i.i.d. data points sampled from $\P_0$ and evaluate the worst case performance of each policy using $\hat{Q}_{\mathrm{DRO}}$. The results are reported in the first row in Table \ref{tab:policy_learning}.
    \item We first generate $M=100$ independent test sets, where each test set consists of $n'=2500$ i.i.d. data points sampled from $\P_0$. We denote them by  $\left\{\left\{\left(X^{(j)}_i, Y^{(j)}_i(a^1), \dots, Y^{(j)}_i(a^d)\right)\right\}_{i=1}^{n'}\right\}_{j=1}^{M}$. Then, we randomly sample a new dataset around each dataset, i.e., $\left(\tilde{X}^{(j)}_i, \tilde{Y}^{(j)}_i(a^1), \dots, \tilde{Y}^{(j)}_i(a^d)\right)$ is sampled in the KL-ball centered at $\left(X^{(j)}_i, Y^{(j)}_i(a^1), \dots, Y^{(j)}_i(a^d)\right)$. Then, we evaluate each policy using $\hat{Q}_{\mathrm{min}}$, defined by
    \[
    \hat{Q}_{\mathrm{min}}(\pi) \triangleq\min_{1 \leq j \leq M}\left\{ \frac{1}{n'} \sum_{i = 1}^{n'}
    \tilde{Y}^{(j)}_i\left(\pi\left({\tilde{X}_i^{(j)}}\right)\right)\right\}.
    \]
    The results are reported in the second row in Table \ref{tab:policy_learning}.
\end{enumerate}

We compare of adversarial performance of $\pilin$ and $\hat{\pi}_{\rm{DRO}}$ using $\hat{Q}_{\mathrm{DRO}}$ and $\hat{Q}_{\mathrm{min}}$. We fix the $\delta = 0.2$ and size of test set $n' = 2500$. The training set size ranges from $500$ to $2500$. Table \ref{tab:policy_learning} reports the mean and standard deviation of $\hat{Q}_{\mathrm{DRO}}$ and $\hat{Q}_{\mathrm{min}}$ computed using $100$ i.i.d. experiments, where an independent training set and an independent test set are generated from $\mathbf{P}_0$ in each experiment.

\begin{table}[!ht]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|}
         \hline
         \multicolumn{2}{|c|}{}& $n = 500$ & $n = 1000$&  $n = 1500$ &  $n = 2000$ &  $n = 2500$
         \\\hline
         \multirow{2}{*}{$\hat{Q}_{\mathrm{DRO}}$}&
         $\pilin$
         &$0.081\pm 0.044$& $0.103\pm 0.027$ &
         $0.113\pm 0.016$ & $0.114\pm 0.014$ &
         $0.114\pm 0.011$
         \\
         \cline{2-7}
         &$\hat{\pi}_{\rm{DRO}}$
         &$0.094\pm0.039$ & $0.111\pm 0.022$ &
         $0.116\pm 0.015$ & $0.118\pm 0.011$ &
         $0.118\pm 0.010$
         \\
         \hline
         \multirow{2}{*}{$\hat{Q}_{\mathrm{min}}$}&
         $\pilin$
         &$0.214\pm0.039$ & $0.234\pm0.022$
         &$0.241\pm0.015$ & $0.242\pm0.015$
         &$0.243\pm0.014$\\
         \cline{2-7}
         &$\hat{\pi}_{\rm{DRO}}$
         &$0.221\pm0.035$& $0.236\pm0.018$
         &$0.246\pm0.014$ & $0.247\pm0.018$
         &$0.248\pm0.014$\\
         \hline
    \end{tabular}
    \caption{Comparison of adversarial performance in nonlinear example.}
    \label{tab:policy_learning}
\end{table}

We can easily observe from Table \ref{tab:policy_learning} that the adversarial performance of $\hat{\pi}_{\rm{DRO}}$ dominates that of $\hat{\pi}_{\rm{Lin}}$, which implies $\hat{\pi}_{\rm{DRO}}$ is more resilient to adversarial perturbations. We also highlight that $\hat{\pi}_{\rm{DRO}}$ has smaller standard deviation in Table \ref{tab:policy_learning} and the superiority of $\hat{\pi}_{\rm{DRO}}$ is more manifest under smaller training set, indicating $\hat{\pi}_{\rm{DRO}}$ is a more stable estimator compared with $\hat{\pi}_{\rm{Lin}}$.

\section{Extension to $f$-divergence Uncertainty Set}
\label{sec:extension}
In this section, we generalize the KL-divergence to $f$-divergence. Here, we
define $f$-divergence between $\P $ and $\P _0 $ as
\begin{equation*}  \label{def:f-divergence}
D_f(\P ||\P _0)\triangleq\int f\left(\frac{d\P }{d\P _0} \right)d\P _0,
\end{equation*}
where $f:\reals \rightarrow \reals_{+} \cup \{+\infty\}$ is a convex function satisfying $f(1)=0$ and $f(t)=+\infty$ for any $t<0$. Then, define the $f$-divergence uncertainty set as  $\mathcal{U}^f_{\P
_0}(\delta)  \triangleq \{\P \ll \P _0\mid D_f(\P ||\P _0)\leq \delta\}.$ Accordingly,
the distributional robust value function is defined below.
\begin{definition}\quad
\label{def:f-divergence_dro}
	For a given $\delta > 0$, the distributionally robust value function $Q^f_{\mathrm{\rm DRO}}:\Pi \rightarrow \reals$ is defined as: $Q^f_{\mathrm{\rm DRO}}(\pi) \triangleq\inf_{\P\in\mathcal{U}^f_{\P_0}(\delta)} \E_{\P}[Y(\pi(X))]$.
\end{definition}

We focus on Cressie-Read family of $f$-divergence, defined in \cite
{cressie1984multinomial}. For $k\in (1,\infty ),$ function $f_{k}$ is
defined as
\begin{equation*}
f_{k}(t) \triangleq\frac{t^{k}-kt+k-1}{k(k-1)}.
\end{equation*}
As $k\rightarrow 1,$ $f_{k}\rightarrow f_{1}(t)=t\log t-t+1,$which gives
KL-divergence. For the ease of notation, we use $Q_{\mathrm{\rm DRO}}^{k}\left(
\cdot \right) $, $\mathcal{U}_{\P _0}^k (\delta)$, and $D_{k}\left( \cdot
||\cdot \right) $ as shorthands of $Q_{\mathrm{\rm DRO}}^{f}\left( \cdot \right)
$, $\mathcal{U}_{\P _0}^f (\delta)$, and $D_{f}\left( \cdot ||\cdot \right) ,
$ respectively, for $k\in \lbrack 1,\infty ).$ We further define
$k_{\ast }\triangleq k/(k-1),$ and $c_{k}(\delta )\triangleq(1+k(k-1)\delta
)^{1/k}.$  Then, \cite{duchi2018learning}
gives the following duality results.

\begin{lemma}
For any Borel measure $\P$ supported on the space $\mathcal{X}
\times \prod_{j=1}^d \mathcal{Y}_j$ and $k\in (1,\infty ),$ we have
\begin{equation*}
\inf_{\mathbf{Q}\in\mathcal{U}^k_{\P}(\delta)} \E_{\mathbf{Q}}[Y(\pi(X))] =\sup_{\alpha \in \reals}\left\{
-c_{k}\left( \delta \right) {\mathbf{E}}_{\P}\left[ \left( -Y(\pi(X))+\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}
}+\alpha \right\} .
\end{equation*}
\label{lma:f_duality}
\end{lemma}
We then generalize Lemma \ref{lma:quantile} to Lemma \ref
{lma:quantile_f_divergence} for $f_k$-divergence uncertainty set.
\begin{lemma}
For any probability measures $\mathbf{P}_{1},\mathbf{P}_{2}$ supported on $\reals$ and  $k \in [1,+\infty)$,  we have
\label{lma:quantile_f_divergence}
\begin{eqnarray*}
&&\left\vert \sup_{\alpha \in \reals}\left\{ -c_{k}\left( \delta \right)
\mathbf{E}_{\mathbf{P}_{1}}\left[ \left( -Y+\alpha \right) _{+}^{k_{\ast }}
\right] ^{\frac{1}{k_{\ast }}}+\alpha \right\} -\sup_{\alpha \in \reals
}\left\{ -c_{k}\left( \delta \right) \mathbf{E}_{\mathbf{P}_{2}}\left[
\left( -Y+\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}
}+\alpha \right\} \right\vert \\
 &\leq& c_k(\delta) \sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left( t\right)
-q_{\mathbf{P}_{2}}\left( t\right) \right\vert.
\end{eqnarray*}
\end{lemma}
The proof of Lemma \ref{lma:quantile_f_divergence} is in \ref{sec:extension_proof}.
As an analog of Definitions \ref{def:regret}, \ref{def:phi_alpha} and Equation \eqref{eqn:pi_hat}, we further make the following definition.
\begin{definition}
\begin{enumerate}
\item
The distributionally robust value estimator $\hat{Q}^k_{\mathrm{\rm DRO}}:\Pi \rightarrow \reals$ is defined by
\[
\hat{Q}^k_{\mathrm{\rm DRO}}(\pi) \triangleq \sup_{\alpha \in \reals}\left\{
-c_{k}\left( \delta \right) \frac{1}{nS_n^\pi}\sum_{i=1}^n\frac{\mathbf{1}\{\pi(X_i) = A_i\}}{\pi_0(A_i\mid X_i)} \left( \left( -Y(\pi(X))+\alpha \right) _{+}^{k_{\ast }}\right) ^{\frac{1}{k_{\ast }}
}+\alpha \right\}.
\]
\item The distributional robust regret $R^k_{\mathrm{\rm DRO}}(\pi)$ of a  policy $\pi \in \Pi$ is defined as
\begin{equation*}
R^k_{\mathrm{\rm DRO}}(\pi) \triangleq\max_{\pi' \in \Pi}\inf_{\P\in\mathcal{U}^k_{\P_0}(\delta)}\E_{\P}[Y(\pi'(X))] - \inf_{\P\in\mathcal{U}^k_{\P_0}(\delta)}\E_{\P}[Y(\pi(X))].
\end{equation*}
\item The optimal policy $\hat{\pi}^k_{\rm DRO}$  which maximizes the value of $\hat{Q}^k
_{\rm DRO}$ is defined as
\[
\hat{\pi}^k_{\rm DRO}\triangleq\arg \max_{\pi \in \Pi }\hat{Q}^k_{\rm DRO}(\pi).
\]

\end{enumerate}
\end{definition}
By applying Lemma \ref{lma:quantile_f_divergence} and executing the same lines as the proof of Theorem \ref{DRO_Uniform}, we have an analogous theorem below.
\begin{theorem}
Suppose Assumption \ref{assump:classical} is enforced. With probability at least $1-\varepsilon$, we have
\begin{eqnarray}
R^k_{\rm DRO}(\hat{\pi}^k_{\rm DRO})  &\leq& \frac{4c_k(\delta)}{\underline{b}\eta\sqrt{n}}\left( (\sqrt{2}+1)\kappa ^{(n)}\left( \Pi \right)  +\sqrt{2\log\left(\frac{2}{\varepsilon}\right)}+C\right),
\end{eqnarray}
where $C$ is a universal constant$.$
\end{theorem}

We emphasis on the importance of Assumption \ref{assump:classical}.4. Without Assumption \ref{assump:classical}.4, a similar argument with \cite{duchi2018learning} gives the minimax rate
\begin{equation}
R^k_{\mathrm{\rm DRO}}(\hat{\pi}^k_{\rm DRO}) =O_p\left( n^{-\frac{1}{k_* \vee 2}} \log n \right),
\end{equation}
which is much slower than our results under a natural assumption (Assumption \ref{assump:classical}.4).

\section{Conclusion}
We have provided a distributional robust formulation for policy evaluation and policy learning in batch contextual bandits. Our results focus on providing finite-sample learning guarantees,
and it is interesting that such learning is enabled by a dual optimization formulation. An interesting subsequent direction would be to extend the algorithm and results to the Wasserstein distance case for batch contextual bandits, which cannot be admitted as a special case of our $f$-divergence framework.
We leave that for future work.

\bibliographystyle{plain}
\bibliography{references,DR2,DR4,f_divergence}
\setcounter{section}{0} \setcounter{subsection}{0} \setcounter{equation}{0}
\ \renewcommand
{\thesection}{Appendix \Alph{section}}
\renewcommand\thesubsection{\thesection.\arabic{subsection}}
\renewcommand{\theequation}{\Alph{section}.\arabic{equation}}
\renewcommand{\thelemma}{\Alph{section}\arabic{lemma}}
\renewcommand{\thetheorem}{\Alph{section}\arabic{theorem}} \newpage

\section{Proofs of Main Results}
\subsection{Auxiliary Results}
\label{sec:aux} To prove Theorem \ref{DRO_CLT} and \ref{DRO_Uniform},
we first collect some theorems in stochastic optimization \cite{shapiro2009lectures} and complexity theory (\citep
[Section 4]{wainwright2019high}).

\begin{definition}[G\^{a}teaux and Hadamard directional
differentiability]
Let $B_{1}$ and $B_{2}$ be Banach spaces and $G:B_{1}\rightarrow B_{2}$ be a
mapping. It is said that $G$ is directionally differentiable at a considered
point $\mu \in B_{1}$ if the limits
\begin{equation*}
G_{\mu }^{\prime }(d)=\lim_{t\downarrow 0}\frac{G\left( \mu +td\right)
-G(\mu )}{t}
\end{equation*}
exists for all $d\in B_{1}.$

Furthermore, it is said that $G$ is G\^{a}teaux directionally differentiable
at $\mu $ if the directional derivative $G_{\mu }^{\prime }(d)$ exists for
all $d\in B_{1}$ and $G_{\mu }^{\prime }(d)$ is linear and continuous in $d.$
For ease of notation, we also denote $D_{\mu }(\mu _{0})$ be the operator $
G_{\mu _{0}}^{\prime }(\cdot ).$

Finally, it is said that $G$ is Hadamard directionally differentiable at $
\mu $ if the directional derivative $G_{\mu }^{\prime }(d)$ exists for all $
d\in B_{1}$ and
\begin{equation*}
G_{\mu }^{\prime }(d)=\lim_{\substack{ t\downarrow 0  \\ d^{\prime
}\rightarrow d}}\frac{G\left( \mu +td^{\prime }\right) -G(\mu )}{t}.
\end{equation*}
\end{definition}

\begin{theorem}[Danskin theorem, Theorem 4.13 in \protect\cite
{bonnansperturbation}]
Let $\Theta \in \mathbf{R}^{d}$ be a nonempty compact set and $B$ be a
Banach space. Suppose the mapping $G:B\times \Theta \rightarrow \mathbf{R}$
satisfies that $G(\mu ,\theta )$ and $D_{\mu }\left( \mu ,\theta \right) $
are continuous on $O_{\mu _{0}}\times \Theta $, where $O_{\mu _{0}}\subset B$
is a neighborhood around $\mu _{0}.$ Let $\phi :B\rightarrow \mathbf{R}$ be
the inf-functional $\phi (\mu )=\inf_{\theta \in \Theta }G(\mu ,\theta )$
and $\bar{\Theta}(\mu )=\arg \max_{\theta \in \Theta }G(\mu ,\theta ).$
Then, the functional $\phi $ is directionally differentiable at $\mu _{0}$
and
\begin{equation*}
G_{\mu _{0}}^{\prime }(d)=\inf_{\theta \in \bar{\Theta}(\mu _{0})}D_{\mu
}\left( \mu _{0},\theta \right) d.
\end{equation*}
\end{theorem}

\begin{theorem}[Delta theorem, Theorem 7.59 in \protect\cite
{shapiro2009lectures}]
Let $B_{1}$ and $B_{2}$ be Banach spaces, equipped with their Borel $\sigma $
-algrebras, $Y_{N}$ be a sequence of random elements of $B_{1}$, $
G:B_{1}\rightarrow B_{2}$ be a mapping, and $\tau _{N}$ be a sequence of
positive numbers tending to infinity as $N\rightarrow \infty .$ Suppose that
the space $B_{1}$ is separable, the mapping $G$ is Hadamard directionally
differentiable at a point $\mu \in B_{1},$ and the sequence $X_{N}=\tau
_{N}\left( Y_{N}-\mu \right) $ converges in distribution to a random element
$Y$ of $B_{1}.$ Then,
\begin{equation*}
\tau _{N}\left( G\left( Y_{N}\right) -G\left( \mu \right) \right)
\Rightarrow G_{\mu }^{\prime }\left( Y\right) \text{ in distribution,}
\end{equation*}
and
\begin{equation*}
\tau _{N}\left( G\left( Y_{N}\right) -G\left( \mu \right) \right) =G_{\mu
}^{\prime }\left( X_{N}\right) +o_{p}(1).
\end{equation*}
\end{theorem}

\begin{proposition}[Proposition 7.57 in \protect\cite{shapiro2009lectures}]
Let $B_{1}$ and $B_{2}$ be Banach spaces, $G:B_{1}\rightarrow B_{2},$ and $
\mu \in B_{1}.$ Then the following hold: (i) If $G\left( \cdot \right) $ is
Hadamard directionally differentiable at $\mu ,$ then the directional
derivative $G_{\mu }^{\prime }\left( \cdot \right) $ is continuous. (ii) If $
G(\cdot )$ is Lipschitz continuous in a neighborhood of $\mu $ and
directionally differentiable at $\mu ,$ then $G(\cdot )$ is Hadamard
directionally differentiable at $\mu .$
\end{proposition}
\begin{definition}[Rademacher complexity]
	Let $\mathcal{F}$ be a family of real-valued functions $f:Z\rightarrow
	\mathbf{R.}$ Then, the Rademacher complexity of $\mathcal{F}$ is defined as
	\begin{equation*}
	\mathcal{R}_{n}\left( \mathcal{F}\right)\triangleq\mathbf{E}_{z,\sigma}
\left[ \sup_{f\in \mathcal{F}}\left|\frac{1}{n}
	\sum_{i=1}^{n}\sigma _{i}f(z_{i})\right|\right]  ,
	\end{equation*}
	where $\sigma _{1},\sigma _{2},\ldots ,\sigma _{n}$ are i.i.d with the
	distribution $\P \left( \sigma _{i}=1\right) =\P \left( \sigma
	_{i}=-1\right) =1/2.$
\end{definition}

\begin{theorem}[Theorem 4.10 in \cite{wainwright2019high}]
	\label{lemma:rademacher}

	If $f(z)\in  [-B,B],$ we have with probability at least $
	1-\exp \left(- \frac{n\epsilon^2}{2B^2} \right) $,
	\begin{equation*}
		\sup_{f\in \mathcal{F}}\left| \frac{1}{n}\sum_{i=1}^{n}f(z_{i})-\mathbf{E}
		f(z)\right| \leq
		2\mathcal{R}_{n}\left( \mathcal{F}\right) +\epsilon.
	\end{equation*}
\end{theorem}
\begin{theorem}[Dudley's Theorem, (5.48) in \cite{wainwright2019high}]If $f(z)\in  [-B,B],$ we have a bound for the Rademacher complexity,
\label{Dudley}
\begin{equation*}
\mathcal{R}_{n}\left( \mathcal{F}\right) \leq \E\left[ \frac{24}{\sqrt{n}}
\int_{0}^{2B}\sqrt{\log N(t,\mathcal{F}\text{,}\left\Vert \cdot \right\Vert
_{\P_{n}})}{\rm d}t\right] ,
\end{equation*}
where $N(t,\mathcal{F}$,$\left\Vert \cdot \right\Vert _{\P_{n}})$ is $t$
-covering number of set $\mathcal{F}$ and the metric $\left\Vert \cdot
\right\Vert _{\P_{n}}$ is defined by
\begin{equation*}
\left\Vert \cdot \right\Vert _{\P_{n}}\triangleq\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left(
f(z_{i}\right) -g(z_{i}))^{2}}.
\end{equation*}
\end{theorem}
\subsection{Proof of Corollary \ref{cor:worst_case} and  Lemma \protect\ref{lma:cvx} in Section \ref{sec:alg}}
\label{sec:lma_cvx}
\begin{proof}{Proof of Corollary \ref{cor:worst_case}}
Since $Y(a^1),Y(a^2),\ldots,Y(a^d)$ are mutually independent conditional on $X$, and $Y(a^i)|X$ has a density, we can write the joint measure of $Y(a^1),Y(a^2),\ldots,Y(a^d),X$ as
\[
\left(\prod_{i=1}^df_i(y_i|x)   \lambda({\rm d} y_i) \right)\mu({\rm d} x),
\]
where $\lambda$ denotes the Lebesgue measure in $\reals$, and $\mu({\rm d}x)$ denotes the measure induced by $X$ on the space $\mathcal{X}$. Then, by Proposition \ref{prop:worst_case}, we have under $\P(\pi)$, $Y(a^1),Y(a^2),\ldots,Y(a^d),X$ have a joint measure
\begin{eqnarray*}
\frac{\exp(-y_{\pi(x)} /\alpha^*(\pi))}{\E_{\P_0}[\exp(-Y(\pi(X)/\alpha^*(\pi)))]}
\left(\prod_{i=1}^df_i(y_i|x)  \lambda(  {\rm d} y_i) \right)\mu({\rm d} x)
=\left(\prod_{i=1}^df'_i(y_i|x)   \lambda({\rm d} y_i) \right)\mu'({\rm d} x),
\end{eqnarray*}
where
\begin{equation*}
f_i'(y_i|x)=\left\{
\begin{array}{c}
f_i(y_i|x) \\
\frac{\exp(-y_{i} /\alpha^*(\pi))f_i(y_i|x)}{\int\exp(-y_i/\alpha^*(\pi))f_i(y_i|x)\lambda({\rm d} y_i)}
\end{array}
\begin{array}{c}
\text{for } i\neq \pi(x) \\
\text{for } i= \pi(x)
\end{array}
\right.,
\end{equation*}
and
\begin{equation*}
\mu'({\rm d} x)=\frac{\int\exp(-y_i/\alpha^*(\pi))f_i(y_i|x)\mu({\rm d} y_i)}{\E_{\P_0}[\exp(-Y(\pi(X)/\alpha^*(\pi)))]},
\end{equation*}
which completes the proof.
\end{proof}
\begin{proof}{Proof of Lemma \ref{lma:cvx}}
    The closed form expression of $\frac{\partial}{\partial \alpha}\hat{\phi}_{n}(\pi,\alpha)$ and $\frac{\partial^2}{\partial \alpha^2}
	\hat{\phi}_{n}(\pi,\alpha)$ follows from elementary algebra. By the Cauchy Schwartz's inequality, we have
	\[
	    \Big(\sum_{i=1}^n Y_i(A_i)W_i(\pi,\alpha)\Big)^2
	    \leq n S_n^\pi \hat{W}_{n}(\pi ,\alpha)
	    \sum_{i=1}^n Y^2_i(A_i)W_i(\pi,\alpha).
	\]
	Therefore, it follows that
	$\frac{\partial^2}{\partial \alpha^2}
	\hat{\phi}_{n}(\pi,\alpha)\leq 0$. Note that the Cauchy Schwartz's inequality is actually an equality if and only if
	\[
	Y^2_i(A_i)W_i(\pi,\alpha) = cW_i(\pi,\alpha) \quad \mbox{ if } \quad
	W_i(\pi,\alpha)\neq 0
	\]
	for some constant $c$ independent of $i$. Since the above condition is violated if  $\{Y_i(A_i)\mathbf{1}\{\pi(X_i) = A_i\}\}_{i=1}^n$ has at least two different non-zero values, we have in this case $\hat{\phi}_{n}(\pi,\alpha)$ is strictly-concave in $\alpha$.
\end{proof}

\subsection{Proof of the central limit theorem in Section \ref{sec:CLT}}
\label{sec:thm1}

We first give the upper and lower bounds for $\alpha ^{\ast }(\pi)$ in Lemmas \ref{lemma:upper_bd} and \ref{lemma:ld}.

\begin{lemma}[Uniform upper bound of $\protect\alpha ^{\ast }(\pi)$]

\label{lemma:upper_bd} Suppose that Assumption \ref{assump:classical} is
imposed, we have the optimal dual solution $\alpha ^{\ast }(\pi)\leq \overline{
\alpha }:=M/\delta $ .

\end{lemma}

\begin{proof}{Proof}
First note that $\inf_{\P \in \mathcal{U}_{\P _{0}(\delta )}}\mathbf{E}_{\P }
\left[ Y(\pi (X))\right] \geq \essinf{Y(\pi(X))}\geq 0$ and
\begin{equation*}
-\alpha \log \mathbf{E}_{\mathbf{P}_{0}}\left[ \exp \left( -Y(\pi (X)\right)
/\alpha \right] -\alpha \delta \leq M-\alpha \delta .
\end{equation*}
$M-\alpha \delta \geq 0$ gives the upper bound $\alpha ^{\ast }(\pi)\leq
\overline{\alpha }:=M/\delta .$

\end{proof}

\begin{lemma}[Lower bound of $\protect\alpha ^{\ast }(\pi)$]
	\label{lemma:ld} Suppose that Assumption \ref{assump:classical} is
	imposed, we have
$\alpha ^{\ast } (\pi)>0$.
\end{lemma}
\begin{proof}{Proof}
To ease of notation, we abbreviate $Y(\pi (X))$ as $Y.$ It is easy to check
the density of $f_{Y}$ has a lower bound $\underline{b}>0.$ Since $f_{Y}$ is
a continuous function on a compact space, we have $f_{Y}$ is upper bounded.
Let $\overline{b}(\pi)=\sup_{x\in \lbrack 0,M]}f_{Y}(x).$

First, note that $\lim_{\alpha \rightarrow 0}\phi \left( \pi ,\alpha \right)
=0.$ We only need to show $\lim \inf_{\alpha \rightarrow 0}\frac{\partial
\phi \left( \pi ,\alpha \right) }{\partial \alpha }>0.$

The derivative of $\phi \left( \pi ,\alpha \right) $ is given by
\begin{equation*}
\frac{\partial \phi \left( \pi ,\alpha \right) }{\partial \alpha }=-\frac{
\mathbf{E}\left[ Y/\alpha \exp \left( -Y/\alpha \right) \right] }{\mathbf{E}
\left[ \exp \left( -Y/\alpha \right) \right] }-\log \left( \mathbf{E}\left[
\exp \left( -Y/\alpha \right) \right] \right) -\delta .
\end{equation*}
Since $\mathbf{P}_{0 }$ has a continuous density, we have $\log \left(
\mathbf{E}\left[ \exp \left( -Y/\alpha \right) \right] \right) \rightarrow
-\infty .$ Notice that
\begin{equation*}
\mathbf{E}\left[ Y/\alpha \exp \left( -Y/\alpha \right) \right] \leq \alpha
\overline{b}\text{ and }\lim \inf_{\alpha \rightarrow 0}\mathbf{E}\left[
\exp \left( -Y/\alpha \right) \right] /\alpha \geq \underline{b}.
\end{equation*}
Therefore, we have
\begin{equation*}
\lim \sup_{\alpha \rightarrow 0}\frac{\mathbf{E}\left[ Y/\alpha \exp \left(
-Y/\alpha \right) \right] }{\mathbf{E}\left[ \exp \left( -Y/\alpha \right)
\right] }\leq \frac{\overline{b}(\pi)}{\underline{b}}.
\end{equation*}
Therefore, we have the desired result
\begin{equation*}
\lim \inf_{\alpha \rightarrow 0}\frac{\partial \phi \left( \pi ,\alpha
\right) }{\partial \alpha }\rightarrow +\infty,
\end{equation*}
which completes the proof.
\end{proof}

\begin{lemma} We have pointwise central limit theorem,
\begin{eqnarray*}
\sqrt{n}\left( \hat{W}_{n}(\pi ,\alpha )-\mathbf{E}\left[ W_{i}\left( \pi
,\alpha \right) \right] \right) \Rightarrow \mathcal{N}\left( 0,\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi
(X)\mid X\right) } \left( \exp \left( -Y(\pi (X))/\alpha \right)
-\mathbf{E}\left[ \exp \left( -Y(\pi (X))/\alpha \right) \right] \right)
^{2} \right] \right) ,
\end{eqnarray*}
for any $\pi \in \Pi$ and $\alpha>0$.
\label{lma:CLT_pre}
\end{lemma}
\begin{proof}{Proof} After reformulation, we have
\begin{eqnarray*}
\hat{W}_{n}(\pi ,\alpha )-\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right)
\right]  &=&\frac{\frac{1}{n}\sum_{i=1}^{n}W_{i}\left( \pi ,\alpha \right)
-\left( \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1}\left\{ \pi
(X_{i})=A_{i}\right\} }{\pi _{0}\left( A_{i}|X_{i}\right) }\right) \mathbf{E}
\left[ W_{i}\left( \pi ,\alpha \right) \right] }{\frac{1}{n}\sum_{i=1}^{n}
\frac{\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi _{0}\left(
A_{i}|X_{i}\right) }} \\
&=&\frac{\frac{1}{n}\sum_{i=1}^{n}\left( W_{i}\left( \pi ,\alpha \right) -
\frac{\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi _{0}\left(
A_{i}|X_{i}\right) }\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) \right]
\right) }{\frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1}\left\{ \pi
(X_{i})=A_{i}\right\} }{\pi _{0}\left( A_{i}|X_{i}\right) }}.
\end{eqnarray*}
The denominator $\frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1}\left\{ \pi
(X_{i})=A_{i}\right\} }{\pi _{0}\left( A_{i}|X_{i}\right) }\overset{p}{
\rightarrow }1$ and the nominator converges as
\begin{eqnarray*}
&&\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left( W_{i}\left( \pi ,\alpha \right) -
\frac{\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi _{0}\left(
A_{i}|X_{i}\right) }\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) \right]
\right)  \\
&\Rightarrow &N(0,\var \left( W_{i}\left( \pi ,\alpha \right) -\frac{
\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi _{0}\left(
A_{i}|X_{i}\right) }\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) \right]
\right) ,
\end{eqnarray*}
where
\begin{eqnarray}
&&\mathbf{Var}\left( W_{i}\left( \pi ,\alpha \right) -\frac{\mathbf{1}
\left\{ \pi (X_{i})=A_{i}\right\} }{\pi _{0}\left( A_{i}|X_{i}\right) }
\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) \right] \right) \notag \\
&=&\mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) ^{2}\right] -2\mathbf{E}
\left[ \left( \frac{\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi
_{0}\left( A_{i}|X_{i}\right) }\right) ^{2}\exp \left( -Y(\pi (X))/\alpha
\right) \right] \mathbf{E}\left[ W_{i}\left( \pi ,\alpha \right) \right]  \notag \\
&&+\mathbf{E}\left[ \frac{\mathbf{1}\left\{ \pi (X_{i})=A_{i}\right\} }{\pi
_{0}\left( A_{i}|X_{i}\right) }\right] ^{2}\mathbf{E}\left[ W_{i}\left( \pi
,\alpha \right) \right] ^{2}  \label{eq:var_new} \\
&=&\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }\mathbf{E}
\left[ \exp \left( -2Y(\pi (X))/\alpha \right) |X\right] \right] -2\mathbf{E}
\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }\mathbf{E}\left[ \exp
\left( -Y(\pi (X))/\alpha \right) |X\right] \right] \mathbf{E}\left[
W_{i}\left( \pi ,\alpha \right) \right]  \notag \\
&&+\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }\right]
\mathbf{E}\left[ \exp \left( -Y(\pi (X))/\alpha \right) \right] ^{2} \notag\\
&=&\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }
\left( \exp \left( -Y(\pi (X))/\alpha \right) -\mathbf{E}\left[ \exp
\left( -Y(\pi (X))/\alpha \right) \right] \right) ^{2} \right]  .  \notag
\end{eqnarray}
By Slutsky's theorem, the desired result follows.

 \end{proof}

Now we are ready to show the proof of Theorem \ref{DRO_CLT}.

\proof{Proof of Theorem \ref{DRO_CLT}} Notice that
\begin{equation*}
\sqrt{n}\left( \hat{W}_{n}(\pi ,\alpha )-\mathbf{E}[W_{i}(\pi ,\alpha
)]\right) \Rightarrow Z\left( \alpha \right) ,
\end{equation*}
where by Lemma \ref{lma:CLT_pre}
\begin{equation*}
Z\left( \alpha \right) \sim \mathcal{N}\left( 0,\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }
\left( \exp \left( -Y(\pi (X))/\alpha \right) -\mathbf{E}\left[ \exp
\left( -Y(\pi (X))/\alpha \right) \right] \right) ^{2} \right] \right).
\end{equation*}
By Lemma \ref{lemma:ld}, there exists $\underline{\alpha}(\pi)>0$ such that $\alpha^*(\pi) \geq \underline{\alpha}(\pi)$. To ease of notation, we abbreviate $\underline{\alpha}(\pi),\alpha^*(\pi)$ as $\underline{\alpha},\alpha^*$.
Since $\hat{W}_n(\pi ,\alpha )$ is Lipschitz continuous over the set $\alpha \in [\underline{\alpha}/2,2\overline{\alpha}]$, we have
\begin{equation}
\sqrt{n}\left( \hat{W}_{n}(\pi ,\cdot )-\mathbf{E}[W_{i}(\pi ,\cdot
)]\right) \Rightarrow Z\left( \cdot \right) ,
\label{eqn:uniform_conv_alpha}
\end{equation}
uniformly in Banach space $\mathcal{C}([\underline{\alpha}/2,2\overline{\alpha}])$ of
continuous functions $\psi :[\underline{\alpha}/2,2\overline{\alpha}]
\mathcal{\ \rightarrow }\reals$ equipped with the the sup-norm $
\left\Vert \psi \right\Vert :=\sup_{x\in \lbrack \underline{\alpha}/2,2
\overline{\alpha} ]}\psi (x)$ \citep[e.g.][Theorem 18.14]{van2000asymptotic}. $Z$ is a random element in $\mathcal{C}([
\underline{\alpha}/2,2\overline{\alpha}])$.

Define the functionals
\begin{equation*}
G(\psi,\alpha )=\alpha \log \left( \psi (\alpha )\right) +\alpha \delta, \text{ and } V(\psi )=\inf_{\alpha \in \lbrack \underline{\alpha }/2,2\overline{\alpha }
]}G(\psi,\alpha ),
\end{equation*}
for $\psi>0$. By the Danskin theorem \citep[Theorem 4.13]{bonnansperturbation}, $
V\left( \cdot \right) $ is directionally differentiable at any $\mu \in
\mathcal{C}([\underline{\alpha }/2,2\overline{\alpha }])$ with $\mu >0$ and
\begin{equation*}
V_{\mu }^{\prime }\left( \nu \right) =\inf_{\alpha \in \bar{X}\left( \mu
\right) }\alpha \left( 1/\mu (\alpha )\right) \nu (\alpha ),\text{ }\forall
\nu \in \mathcal{C}([\underline{\alpha }/2,2\overline{\alpha }])\mathcal{)}
\text{,}
\end{equation*}
where $\bar{X}\left( \mu \right) =\arg \min_{\alpha \in \lbrack \underline{
\alpha }/2,2\overline{\alpha }])}\alpha \log \left( \mu (\alpha)\right)
+\alpha \delta $ and $V_{\mu }^{\prime }\left( \nu \right) $ is the
directional derivative of $V\left( \cdot \right) $ at $\mu $ in the
direction of $\nu .$ On the other hand, $V(\psi )$ is Lipschitz continuous
if $\psi \left( \cdot \right) $ is bounded away from zero. Notice that
\begin{equation}
\mathbf{E}[W_{i}(\pi ,\alpha )]=\mathbf{E}[\exp \left( -Y(\pi (x))/\alpha
\right) ]\geq \exp \left( -2M/\underline{\alpha }\right).
\label{E_ld}
\end{equation}
Therefore, $V\left( \cdot \right) $ is Hadamard directionally differentiable
at $\mu =\mathbf{E}[W_{i}(\pi ,\cdot )]$ (see, for example, Proposition 7.57
in \cite{shapiro2009lectures}). By the Delta theorem (Theorem 7.59 in \cite
{shapiro2009lectures}), we have
\begin{equation*}
\sqrt{n}\left( V(\hat{W}_{n}(\pi ,\cdot ))-V(\mathbf{E}[W_{i}(\pi ,\cdot
)])\right) \Rightarrow V_{\mathbf{E}[W_{i}(\pi ,\cdot )]}^{\prime }\left(
Z\right) .
\end{equation*}
Furthermore, we know that $\log \left( \mathbf{E}\left( \exp \left( -\beta
Y\right) \right) \right) $ is strictly convex w.r.t $\beta $ given $\mathbf{
Var}\left( Y\right) >0$ and $xf(1/x)$ is strictly convex if $f(x)$ is
strictly convex. Therefore, $\alpha \log \left( \mathbf{E}[W_{i}(\pi ,\alpha
)]\right) +\alpha \delta $ is strictly convex for $\alpha >0$ and thus
\begin{eqnarray*}
&&V_{\mathbf{E}[W_{i}(\pi ,\cdot )]}^{\prime }\left( Z\right) =\alpha ^{\ast
}\left( 1/\mathbf{E}[W_{i}(\pi ,\alpha ^{\ast })]\right) Z\left( \alpha
^{\ast }\right) \\
&\overset{d}{=}&\mathcal{N}\left( 0,\frac{\left( \alpha ^{\ast }\right)
^{2}}{ \mathbf{E}\left[ W_{i}(\pi ,\alpha ^{\ast })\right] ^{2}}\mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi (X)|X\right) }
\left( \exp \left( -Y(\pi (X))/\alpha \right) -\mathbf{E}\left[ \exp
\left( -Y(\pi (X))/\alpha \right) \right] \right) ^{2} \right] \right),
\end{eqnarray*}
where $\overset{d}{=}$ denotes equality in distribution.
By Lemma \ref{thm:strong_duality}, we have that
\begin{equation*}
\hat{Q}_{\mathrm{\rm DRO}}(\pi )=-\inf_{\alpha \geq 0}\left( \alpha \log \left(
\hat{W}_{n}(\pi ,\alpha )\right) +\alpha \delta \right) \text{,}
\end{equation*}
and
\begin{equation*}
Q_{\mathrm{\rm DRO}}(\pi )=-\inf_{\alpha \geq 0}\left( \alpha \log \left(
\mathbf{E}[W_{i}(\pi ,\alpha )]\right) +\alpha \delta \right) =-V(\mathbf{E}
[W_{i}(\pi ,\alpha )]).
\end{equation*}

We remain to show $\mathbf{P}$($\hat{Q}_{\mathrm{\rm DRO}}(\pi )\neq -V(\hat{W}
_{n}(\pi ,\alpha )))\rightarrow 0$, as $n\rightarrow \infty .$  The weak convergence \eqref{eqn:uniform_conv_alpha} also implies the uniform convergence,
\begin{equation*}
\sup_{\alpha \in \lbrack \underline{\alpha }/2,2\overline{\alpha }
])}\left\vert \hat{W}_{n}(\pi ,\alpha )-\mathbf{E}[W_{i}(\pi ,\alpha
)]\right\vert \rightarrow 0\text{ a.s..}
\end{equation*}
Therefore, we further have
\begin{equation*}
\sup_{\alpha \in \lbrack \underline{\alpha }/2,2\overline{\alpha }
])}\left\vert \left( \alpha \log \left( \hat{W}_{n}(\pi ,\alpha )\right)
+\alpha \delta \right) -\left( \alpha \log \left( \mathbf{E}[W_{i}(\pi
,\alpha )]\right) +\alpha \delta \right) \right\vert \rightarrow 0\text{ a.s.
}
\end{equation*}
given $\mathbf{E}[W_{i}(\pi ,\alpha )]$ is bounded away from zero in \eqref{E_ld}.  Let
\begin{equation*}
\epsilon =\min \left\{ \underline{\alpha }/2\log \left( \mathbf{E}
[W_{i}(\pi ,\underline{\alpha }/2)]\right) +\underline{\alpha }\delta /2,2
\overline{\alpha }\log \left( \mathbf{E}[W_{i}(\pi ,2\overline{\alpha }
)]\right) +2\overline{\alpha }\delta \right\} -\left( \alpha ^{\ast }\log
\left( \mathbf{E}[W_{i}(\pi ,\alpha ^{\ast })]\right) +\alpha ^{\ast }\delta
\right)>0 .
\end{equation*}
Then, given the event
\begin{equation*}
\left\{ \sup_{\alpha \in \lbrack \underline{\alpha }/2,2\overline{\alpha }
])}\left\vert \left( \alpha \log \left( \hat{W}_{n}(\pi ,\alpha )\right)
+\alpha \delta \right) -\left( \alpha \log \left( \mathbf{E}[W_{i}(\pi
,\alpha )]\right) +\alpha \delta \right) \right\vert <\epsilon /2\right\} ,
\end{equation*}
we have
\begin{equation*}
\alpha ^{\ast }\log \left( \hat{W}_{n}(\pi ,\alpha )\right) +\alpha ^{\ast
}\delta <\min \left\{ \underline{\alpha }/2\log \left( \hat{W}_{n}(\pi ,
\underline{\alpha }/2)\right) +\underline{\alpha }\delta /2,2\overline{
\alpha }\log \left( \hat{W}_{n}(\pi ,2\overline{\alpha })\right) +2\overline{
\alpha }\delta \right\} ,
\end{equation*}
which means $\hat{Q}_{\mathrm{\rm DRO}}(\pi )=-V(\hat{W}_{n}(\pi ,\alpha ))$ by
the convexity of $\alpha \log \left( \hat{W}_{n}(\pi ,\alpha )\right)
+\alpha \delta .$

Finally, we complete the proof by Slutsky's lemma \citep[e.g.][Theorem 1.8.10]{lehmann2006theory}).:
\begin{eqnarray*}
\sqrt{n}\left( \hat{Q}_{\mathrm{\rm DRO}}(\pi )-Q_{\mathrm{\rm DRO}}(\pi )\right)
&=&\sqrt{n}\left( \hat{Q}_{\mathrm{\rm DRO}}(\pi )+V(\hat{W}_{n}(\pi ,\alpha
))\right) +\sqrt{n}\left( V(\mathbf{E}[W_{i}(\pi ,\alpha )])-V(\hat{W}
_{n}(\pi ,\alpha ))\right)  \\
&\Rightarrow &0+\mathcal{N}\left( 0,\sigma ^{2}(\alpha^* ) \right)
\overset{d}{=}\mathcal{N}\left( 0,\sigma ^{2}(\alpha^* ) \right),
\end{eqnarray*}
where \[\sigma ^{2}(\alpha )=\frac{ \alpha^{2} }{\E\left[ W_i(\pi, \alpha)\right]^2} \mathbf{E}\left[ \frac{1}{\pi _{0}\left( \pi
(X)|X\right) } \left( \exp \left( -Y(\pi (X))/\alpha \right)
-\mathbf{E}\left[ \exp \left( -Y(\pi (X))/\alpha \right) \right] \right)
^{2} \right] \]

\endproof
\subsection{Proof of the statistical performance guarantee in Section \ref{sec:uniform_convergence}}
\label{sec:proof_uniform}

We first give the proof of Lemma \ref{lma:quantile}.

\begin{proof}{Proof of Lemma \ref{lma:quantile}}
Notice that
\begin{eqnarray*}
&&\left\vert \sup_{\alpha \geq 0}\left\{ -\alpha \log \mathbf{E}_{\mathbf{P}
_{1}}\left\{ \exp \left( -Y/\alpha \right) \right\} -\alpha \delta \right\}
-\sup_{\alpha \geq 0}\left\{ -\alpha \log \mathbf{E}_{\mathbf{P}_{2}}\left\{
\exp \left( -Y/\alpha \right) \right\} -\alpha \delta \right\} \right\vert
\\
&\leq &\sup_{\alpha \geq 0}\left\vert \alpha \log \mathbf{E}_{\mathbf{P}_{1}}
\left[ \exp \left( -Y/\alpha \right) \right] -\alpha \log \mathbf{E}_{
\mathbf{P}_{2}}\left[ \exp \left( -Y/\alpha \right) \right] \right\vert  \\
&=&\sup_{\alpha \geq 0}\left\vert \alpha \log \mathbf{E}_{\mathbf{P}_{U}}
\left[ \exp \left( -q_{\mathbf{P}_{1}}\left( U\right) /\alpha \right) \right]
-\alpha \log \mathbf{E}_{\mathbf{P}_{U}}\left[ \exp \left( -q_{\mathbf{P}
_{2}}\left( U\right) /\alpha \right) \right] \right\vert ,
\end{eqnarray*}
where $\mathbf{P}_{U}\sim U([0,1])$ and the last equality is based on the
fact that $q_{\mathbf{P}}\left( U\right) \overset{d}{=}\mathbf{P.}$

Denote $T=\sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left(
t\right) -q_{\mathbf{P}_{2}}\left( t\right) \right\vert $ and we have
\begin{eqnarray*}
&&\alpha \log \mathbf{E}_{\mathbf{P}_{U}}\left[ \exp \left( -q_{\mathbf{P}
_{1}}\left( U\right) /\alpha \right) \right] -\alpha \log \left[ \mathbf{E}_{
\mathbf{P}_{U}}\exp \left( -q_{\mathbf{P}_{2}}\left( U\right) /\alpha
\right) \right]  \\
&=&\alpha \log \left[ \int_{0}^{1}\exp \left( -q_{\mathbf{P}_{1}}\left(
u\right) /\alpha \right) {\rm d}u\right] -\alpha \log \left[ \int_{0}^{1}\exp
\left( -q_{\mathbf{P}_{2}}\left( u\right) /\alpha \right) {\rm d}u\right]  \\
&\leq &\alpha \log \left[ \int_{0}^{1}\exp \left( -q_{\mathbf{P}_{2}}\left(
u\right) /\alpha \right) \exp \left( T/\alpha \right) {\rm d}u\right] -\alpha \log
\left[ \int_{0}^{1}\exp \left( -q_{\mathbf{P}_{2}}\left( u\right) /\alpha
\right) {\rm d}u\right]  \\
&=&T.
\end{eqnarray*}
Similarly, we have
\begin{equation*}
\alpha \log \left[ \mathbf{E}_{\mathbf{P}_{U}}\exp \left( -q_{\mathbf{P}
_{2}}\left( U\right) /\alpha \right) \right] -\alpha \log \left[\mathbf{E}_{
\mathbf{P}_{U}} \exp \left( -q_{\mathbf{P}_{1}}\left( U\right) /\alpha
\right) \right] \leq T.
\end{equation*}
The desired result then follows.

\end{proof}

\begin{lemma}
\label{lma:qtl_bd}
Suppose probability measures $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ supported
on $[0,M]$ and $\mathbf{P}_{1}$ has a positive density $f_{\mathbf{P}
_{1}}\left( \cdot \right) $ with a lower bound $f_{\mathbf{P}_{1}}\geq
\underline{b}$ over the interval $[0,M].$ Then, we have
\begin{equation*}
\sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left( t\right) -q_{
\mathbf{P}_{2}}\left( t\right) \right\vert \leq \frac{1}{\underline{b}}
\sup_{x\in \lbrack 0,M]}\left\vert F_{\mathbf{P}_{1}}\left( x\right) -F_{
\mathbf{P}_{2}}\left( x\right) \right\vert .
\end{equation*}
\end{lemma}
\begin{proof}{Proof}
For ease of notation, let $x_{1}=q_{\mathbf{P}_{1}}\left( t\right) $ and $
x_{2}=q_{\mathbf{P}_{2}}\left( t\right) .$ Since the distribution is
right-continuous with left limits and $\mathbf{P}_{1}$ is continuous, we
have
\begin{equation*}
F_{\mathbf{P}_{2}}\left( x_{2}-\right) \leq t,F_{\mathbf{P}_{2}}\left(
x_{2}\right) \geq t,\text{ and }F_{\mathbf{P}_{1}}\left( x_{1}\right) =t.
\end{equation*}
If $x_{1}\geq x_{2},$ we have
\begin{eqnarray*}
x_{1}-x_{2} &\leq &\frac{1}{\underline{b}}\left( F_{\mathbf{P}_{1}}\left(
x_{1}\right) -F_{\mathbf{P}_{1}}\left( x_{2}\right) \right)  \\
&\leq &\frac{1}{\underline{b}}\left( \left( F_{\mathbf{P}_{1}}\left(
x_{1}\right) -F_{\mathbf{P}_{1}}\left( x_{2}\right) \right) +\left( F_{
\mathbf{P}_{2}}\left( x_{2}\right) -F_{\mathbf{P}_{1}}\left( x_{1}\right)
\right) \right)  \\
&=&\frac{1}{\underline{b}}\left( F_{\mathbf{P}_{2}}\left( x_{2}\right) -F_{
\mathbf{P}_{1}}\left( x_{2}\right) \right) .
\end{eqnarray*}
If $x_{1}<x_{2},$ we construct a monotone increasing sequence $
x^{(1)},x^{(2)},\ldots $ with $x^{(n)}\uparrow x_{2}.$ Since $\mathbf{P}_{1}$
is continuous, we have  $F_{\mathbf{P}_{1}}\left( x^{(n)}\right) \uparrow F_{
\mathbf{P}_{1}}\left( x_{2}\right) .$ Then, notice that
\begin{eqnarray*}
x_{2}-x_{1} &\leq &\frac{1}{\underline{b}}\left( F_{\mathbf{P}_{1}}\left(
x_{2}\right) -F_{\mathbf{P}_{1}}\left( x_{1}\right) \right)  \\
&\leq &\frac{1}{\underline{b}}\left( \left( F_{\mathbf{P}_{1}}\left(
x_{2}\right) -F_{\mathbf{P}_{1}}\left( x_{1}\right) \right) +\left( F_{
\mathbf{P}_{1}}\left( x_{1}\right) -F_{\mathbf{P}_{2}}\left( x^{(n)}\right)
\right) \right)  \\
&=&\frac{1}{\underline{b}}\left( F_{\mathbf{P}_{1}}\left( x_{2}\right) -F_{
\mathbf{P}_{2}}\left( x^{(n)}\right) \right)  \\
&=&\lim_{n\rightarrow \infty }\frac{1}{\underline{b}}\left( F_{\mathbf{P}
_{1}}\left( x^{(n)}\right) -F_{\mathbf{P}_{2}}\left( x^{(n)}\right) \right) .
\end{eqnarray*}
Therefore, for every $t$, we have
\begin{equation*}
\left\vert q_{\mathbf{P}_{1}}\left( t\right) -q_{
\mathbf{P}_{2}}\left( t\right) \right\vert=\left\vert x_{1}-x_{2}\right\vert \leq \frac{1}{\underline{b}}\sup_{x\in
\lbrack 0,M]}\left\vert F_{\mathbf{P}_{1}}\left( x\right) -F_{\mathbf{P}
_{2}}\left( x\right) \right\vert .
\end{equation*}
The desired results then follows.
\end{proof}

By utilizing Lemmas \ref{lma:quantile} and \ref{lma:qtl_bd}, we are ready to
prove Theorem \ref{DRO_Uniform}.

\begin{proof}{Proof of Theorem \ref{DRO_Uniform}}
Recall $R_{\rm DRO}(\hat{\pi}_{\rm DRO})=Q_{\rm DRO}(\pi ^{\ast}_{\rm DRO})-Q_{\rm DRO}(\hat{\pi}_{\rm DRO}).$ Then,
\begin{eqnarray*}
&&R_{\rm DRO}(\hat{\pi}_{\rm DRO}) \\
&=&Q_{\rm DRO}(\pi ^{\ast}_{\rm DRO})-\hat{Q}_{\rm DRO}(\hat{\pi}_{\rm DRO})+\hat{Q}_{\rm DRO}(\hat{\pi}
)-Q_{\rm DRO}(\hat{\pi}_{\rm DRO}) \\
&\leq &\left( Q_{\rm DRO}(\pi ^{\ast}_{\rm DRO})-\hat{Q}_{\rm DRO}(\pi ^{\ast }_{\rm DRO})\right)
+\left( \hat{Q}_{\rm DRO}(\hat{\pi}_{\rm DRO})-Q_{\rm DRO}(\hat{\pi}_{\rm DRO})\right) \\
&\leq &2\sup_{\pi \in \Pi }\left\vert \hat{Q}_{\rm DRO}(\pi )-Q_{\rm DRO}(\pi
)\right\vert.
\end{eqnarray*}
notice that
\begin{equation}
\hat{Q}_{\rm DRO}(\pi )
=\sup_{\alpha \geq 0}\left\{ -\alpha \log \left[ \mathbf{E
}_{\mathbf{\hat{P}}_{n}}\exp \left( -Y_{i}(\pi (X_{i}))\right) /\alpha )
\right]  -\alpha \delta \right\}
.
\end{equation}
where $\mathbf{\hat{P}}_{n}$ is the weighted empirical distribution, defined by
\begin{equation*}
\mathbf{\hat{P}}_{n}^{\pi }\triangleq\frac{1}{nS_{n}^{\pi }}\sum_{i=1}^{n}\frac{
\mathbf{1\{}\pi (X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }
\delta \left( Y_{i},X_{i}\right) .
\end{equation*}

Therefore, we have
\begin{eqnarray}
&&R_{\rm DRO}(\hat{\pi}_{\rm DRO})  \notag \\
&\leq &2\sup_{\pi \in \Pi }\left\vert \sup_{\alpha \geq 0}\left\{ -\alpha
\log \left[ \mathbf{E}_{\mathbf{\hat{P}}_{n}}\exp \left( -Y_{i}(\pi
(X_{i})\right) /\alpha )\right] -\alpha \delta \right\} -\sup_{\alpha \geq
0}\left\{ -\alpha \log \left[ \mathbf{E}_{\mathbf{P}_{0}}\exp \left( -Y(\pi
(X)\right) /\alpha )\right] -\alpha \delta \right\} \right\vert
\label{uniform_bd_1}
\end{eqnarray}

By Lemmas \ref{lma:quantile}, \ref{lma:qtl_bd} and
Assumption \ref{assump:classical}, we have
\begin{eqnarray}
&&\sup_{\pi \in \Pi }\left\vert \sup_{\alpha \geq 0}\left\{ -\alpha \log
\left[ \mathbf{E}_{\mathbf{\hat{P}}_{n}}\exp \left( -Y_{i}(\pi
(X_{i})\right) /\alpha )\right] -\alpha \delta \right\} -\sup_{\alpha \geq
0}\left\{ -\alpha \log \left[ \mathbf{E}_{\mathbf{P}_{0}}\exp \left( -Y(\pi
(X)\right) /\alpha )\right] -\alpha \delta \right\} \right\vert  \notag \\
&\leq &\sup_{\pi \in \Pi }\sup_{x\in \lbrack 0,M]}\frac{1}{\underline{b}}
\left\vert \mathbf{E}_{\mathbf{\hat{P}}_{n}}\left[ \mathbf{1}\left\{
Y_{i}(\pi (X_{i})\leq x\right\} \right] -\mathbf{E}_{_{\mathbf{P}_{0}}}\left[
\mathbf{1}\left\{ Y_{i}(\pi (X_{i})\leq x\right\} \right] \right\vert  \notag
\\
&=&\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}\left\vert
\left( \frac{1}{nS_{n}^{\pi }}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi
(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}
\left\{ Y_{i}(\pi (X_{i})\leq x\right\} \right) -\mathbf{E}_{_{\mathbf{P}
_{0}}}\left[ \mathbf{1}\left\{ Y(\pi (X)\leq x\right\} \right] \right\vert
\notag \\
&\leq &\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}
\left\vert \left( \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi
(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}
\left\{ Y_{i}(\pi (X_{i})\leq x\right\} \right) -\mathbf{E}_{_{\mathbf{P}
_{0}}}\left[ \frac{\mathbf{1\{}\pi (X)=A_{i}\mathbf{\}}}{\pi _{0}\left(
A|X\right) }\mathbf{1}\left\{ Y(\pi (X)\leq x\right\} \right] \right\vert
\label{uniform_bd_1_1} \\
&&+\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}\left\vert
\left( \frac{S_{n}^{\pi }-1}{nS_{n}^{\pi }}\sum_{i=1}^{n}\frac{\mathbf{1\{}
\pi (X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}
\left\{ Y(\pi (X_{i})\leq x\right\} \right) \right\vert .
\label{uniform_bd_1_2}
\end{eqnarray}
For \eqref{uniform_bd_1_1}, by \citep[Theorem 4.10]{wainwright2019high}, we have with
probability $1-\exp \left( -n\epsilon ^{2}\eta ^{2}/2\right) $
\begin{eqnarray}
&&\sup_{\pi \in \Pi ,x\in \lbrack 0,M]}\frac{1}{\underline{b}}\left\vert
\left( \frac{1}{n}\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi (X_{i})=A_{i}\mathbf{\}
}}{\pi _{0}\left( A_{i}|X_{i}\right) }\mathbf{1}\left\{ Y_{i}(\pi
(X_{i})\leq x\right\} \right) -\mathbf{E}_{_{\mathbf{P}_{0}}}\left[ \frac{
\mathbf{1\{}\pi (X)=A\mathbf{\}}}{\pi _{0}\left( A|X\right) }\mathbf{1}
\left\{ Y(\pi (X)\leq x\right\} \right] \right\vert  \notag \\
&\leq &\frac{1}{\underline{b}}\left( 2\mathcal{R}_{n}\left( \mathcal{F}_{\Pi
,x}\right)  +\epsilon \right) ,  \label{final_2}
\end{eqnarray}
where the function class $\mathcal{F}_{\Pi ,x}$ is defined as \[\mathcal{F}_{\Pi ,x}\triangleq\left\{ f_{\pi ,x}(X,Y,A)=
\left. \frac{\mathbf{1\{}\pi (X)=A\mathbf{\}1\{}Y(\pi (X))\leq x\}}{\pi_0(A|X)}\right|\pi \in \Pi ,x\in
\lbrack 0,M]\right\} .\]For \eqref{uniform_bd_1_2}, we have
\begin{equation}
\frac{1}{\underline{b}}\left\vert \left( \frac{S_{n}^{\pi }-1}{nS_{n}^{\pi }}
\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi (X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left(
A_{i}|X_{i}\right) }\mathbf{1}\left\{ Y(\pi (X_{i})\leq x\right\} \right)
\right\vert \leq \frac{1}{\underline{b}}\left\vert S_{n}^{\pi }
-1\right\vert,  \label{final_3}
\end{equation}
Further, by \citep[Theorem 4.10]{wainwright2019high} and the fact $
\frac{\mathbf{1}}{\pi_0(A|X)}\leq \frac{1}{\eta }$ and $\mathbf{E}\left[ \frac{\mathbf{1}\{\pi
(X)=A\}}{\pi_0(A|X)}\right] =1$, we have with probability
at least $1-\exp \left( -{n\epsilon ^{2}\eta ^{2}}/{2}\right) ,$
\begin{equation}
\sup_{\pi \in \Pi }\left\vert S_n^{\pi}-1\right\vert
\leq 2\mathcal{R}_{n}\left( \mathcal{F}_{\Pi }\right)
+\epsilon ,
\label{eq:final_4}
\end{equation}
where $\mathcal{F}_{\Pi }\triangleq\left \{\left. f_{\pi }(X,A)=\frac{\mathbf{1}\{\pi
(X)=A\}}{\pi_0(A|X)}\right|\pi \in \Pi \right\}.$

By combining \eqref{final_2}, \eqref{final_3}, and \eqref{eq:final_4}, we have with probability at least $1-2\exp \left( -
n\epsilon ^{2}\eta ^{2}/2\right) $,
\begin{equation}
R_{\rm DRO}(\hat{\pi}_{\rm DRO})\leq \frac{2}{\underline{b}}\left( 2\mathcal{R}_{n}\left(
\mathcal{F}_{\Pi ,x}\right)  +\epsilon \right) + \frac{2}{
\underline{b}} \left( 2\mathcal{R}_{n}\left(
\mathcal{F}_{\Pi }\right)  +\epsilon \right) .  \notag
\end{equation}
Now, we turn to the Rademacher complexity of the classes $\mathcal{F}_{\Pi ,x}$ and $\mathcal{F}_{\Pi}$. First, for the class $\mathcal{F}_{\Pi}$, notice that
\begin{eqnarray*}
&&\sqrt{\sum_{i=1}^{n}\frac{1}{n}\left( \frac{\mathbf{1}\{\pi _{1}(X_{i})=A_{i}\}}{\pi_0(A_i|X_i)}
-\frac{\mathbf{1}\{\pi _{2}(X_{i})=A_{i}\}}{\pi_0(A_i|X_i)}\right) ^{2}} \\
&=&\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left(\frac{\mathbf{1\{}\pi _{1}(X_{i})\neq
\pi _{2}(X_{i})\mathbf{\}}}{\pi_0(A_i|X_i)} \right) ^{2}} \\
&\leq& \frac{1}{\eta} \sqrt{H\left( \pi _{1},\pi _{2}\right) }.
\end{eqnarray*}
Therefore, the covering number
\begin{equation*}
N\left( t,\mathcal{F}_{\Pi },\left\Vert \cdot \right\Vert _{\P_{n}}\right)
\leq N\left( t,\Pi ,\sqrt{H\left( \cdot ,\cdot \right) }/\eta\right)
=N_{H}^{\left( n\right) }\left(\eta^2 t^{2},\Pi,\{x_1,\ldots,x_n \} \right) \leq  N_{H}^{\left( n\right) }\left( \eta^2t^{2},\Pi \right).
\end{equation*}
For the class $\mathcal{F}_{\Pi ,x}$,  we claim \[N\left( t,\mathcal{F}_{\Pi,x },\left\Vert \cdot \right\Vert
_{\P_{n}}\right) \leq N_{H}^{\left( n\right) }\left(\eta^2 t^{2}/2,\Pi \right)
\sup_{\P}N\left(\eta t/\sqrt{2},\mathcal{F}_{I},\left\Vert \cdot \right\Vert
_{\P}\right) ,\]
 where $\mathcal{F}_{I}=\{f(t)\triangleq\mathbf{1}\left\{ t\leq
x\right\} |x\in \lbrack 0,M]\}.$ For ease of notation,  let
\[N_\Pi(t)=N_{H}^{(n)}\left(\eta^2 t^{2}/2,\Pi \right), \text{ and }N_I(t)=\sup_{\P}N\left( \eta t/\sqrt{2},\mathcal{F}_{I},\left\Vert \cdot \right\Vert
_{\P}\right).
\]
Suppose $\{\pi _{1},\pi _{2},\ldots ,\pi
_{N_\Pi(t) }\}$ is a cover for $
\Pi $ and $\left\{ \mathbf{1}^{\pi }\left\{ t\leq x_{1}\right\} ,\mathbf{1}
^{\pi }\left\{ t\leq x_{2}\right\} ,\ldots ,\mathbf{1}^{\pi }\left\{ t\leq
x_{N_I(t)}\right\} \right\} $ is a cover for $\mathcal{F}_{I}$ under the
distance $\left\Vert \cdot \right\Vert _{\hat{\P}_{\pi }},$ defined by
\begin{equation*}
\hat{\P}_{\pi }\triangleq\frac{1}{n}\sum_{i=1}^n \delta \left\{ Y_{i}(\pi (X_{i}))\right\} .
\end{equation*}
Then, we claim that $\mathcal{F}_{\Pi ,x}^{t}$ is a $t$-cover set for $\mathcal{F
}_{\Pi ,x},$ where $\mathcal{F}_{\Pi ,x}^{t}$ is defined as
\begin{equation*}
\mathcal{F}_{\Pi ,x}^{t}\triangleq\left\{\left.\frac{\mathbf{1\{}\pi _{i}(X)=A\}\mathbf{1}^{\pi_i}\{Y(\pi
_{i}(X))\leq x_{j}\}}{\pi_0(A|X)}\right|i\leq N_\Pi(t)
 ,j\leq N_I(t) \right\}.
\end{equation*}
For $f_{\pi ,x}(X,Y,A)\in \mathcal{F}_{\Pi ,x},$ we can pick $\tilde{\pi},\tilde{x
}$ such that $f_{\tilde{\pi},\tilde{x}}(X,Y,A)\in \mathcal{F}_{\Pi ,x}^{t}$,
$H\left( \pi ,\tilde{\pi}\right) \leq t^{2}/2$ and $\left\Vert \mathbf{1}
\left\{ Y\leq x\right\} -\mathbf{1}\left\{ Y\leq \tilde{x}\right\}
\right\Vert _{\hat{P}_{\tilde{\pi}}}\leq t/\sqrt{2}.$ Then, we have
\begin{eqnarray*}
&&\sqrt{\sum_{i=1}^{n}\frac{1}{n}\left(\frac{ \mathbf{1\{}\pi (X_{i})=A_{i}\mathbf{
\}1\{}Y(\pi (X_{i}))\leq x_{1}\}}{\pi_0(A_i|X_i)}-\frac{\mathbf{1\{}\tilde{\pi}(X_{i})=A_{i}\mathbf{
\}1\{}Y(\tilde{\pi}(X_{i}))\leq \tilde{x}\}}{\pi_0(A_i|X_i)}\right) ^{2}} \\
&\leq &\frac{1}{\eta}\sqrt{H\left( \pi ,\tilde{\pi}\right) +\frac{1}{n}\sum_{i=1}^{n}
\mathbf{1\{}\pi (X_{i})=\tilde{\pi}(X_{i})\mathbf{\}}\left( \mathbf{1\{}Y(
\tilde{\pi}(X_{i}))\leq x\}-\mathbf{1\{}Y(\tilde{\pi}(X_{i}))\leq \tilde{x}
\}\right) ^{2}} \\
&\leq &\frac{1}{\eta}\sqrt{\eta^2t^{2}/2+\eta^2t^{2}/2}=t.
\end{eqnarray*}
From Lemma 19.15 and Example 19.16 in \cite{van2000asymptotic}, we know
\begin{equation*}
\sup_{\P}N\left( t,\mathcal{F}_{x},\left\Vert \cdot \right\Vert _{\P}\right)
\leq K\left( \frac{1}{t }\right) ^{2},
\end{equation*}
where $K$ is a universal constant. Finally, by Dudley's theorem \citep[e.g.][(5.48)]{wainwright2019high}, we have
\begin{equation*}
\mathcal{R}_{n}\left( \mathcal{F}_{\Pi }\right) \leq \mathbf{E} \left[
\int_{0}^{2/\eta}\sqrt{\frac{\log N\left( t,\mathcal{F}_{\Pi },\left\Vert \cdot
\right\Vert _{\P_{n}}\right) }{n}}{\rm d}t \right]\leq \frac{\kappa ^{(n)}\left(
\Pi \right) }{\eta \sqrt{n}},
\end{equation*}
and
\begin{eqnarray*}
\mathcal{R}_{n}\left( \mathcal{F}_{\Pi ,x}\right) &\leq &\frac{1}{\sqrt{n}}
\int_{0}^{2/\eta}\sqrt{\log \left( N_{H}^{\left( n\right) }\left(\eta^2 t^{2}/2,\Pi
\right) \right) +\log \left( \sup_{\P}N\left(\eta t/\sqrt{2},\mathcal{F}
_{x},\left\Vert \cdot \right\Vert _{\P}\right) \right) }{\rm d}t \\
&= &\frac{1}{\eta\sqrt{n}}
\int_{0}^{2}\sqrt{\log \left( N_{H}^{\left( n\right) }\left(s^2/2,\Pi
\right) \right) +\log \left( \sup_{\P}N\left(s/\sqrt{2},\mathcal{F}
_{x},\left\Vert \cdot \right\Vert _{\P}\right) \right) }{\rm d}s  \\
&\leq &\frac{1}{\eta\sqrt{n}}\int_{0}^{\sqrt{2}}\left( \sqrt{\log \left( N_{H}^{\left(
n\right) }\left( s^{2}/2,\Pi \right) \right) }+\sqrt{\log K}+\sqrt{4\log
\left( 1/s \right) }\right) {\rm d}s \\
&\leq &\frac{\sqrt{2}\kappa ^{(n)}\left( \Pi \right) }{\eta\sqrt{n}}+C/\sqrt{n},
\end{eqnarray*}
where $C$ is a universal constant. Therefore, by picking $\varepsilon' =2\exp\left(-n \epsilon^2 \eta^2 /2 \right),$ we have
with probability $1-\varepsilon'$,
\begin{eqnarray}
R_{\rm DRO}(\hat{\pi}_{\rm DRO})  &\leq& \frac{4}{\underline{b}\eta\sqrt{n}}\left( (\sqrt{2}+1)\kappa ^{(n)}\left( \Pi \right)  +\sqrt{2\log\left(\frac{2}{\varepsilon'}\right)}+C\right).
\end{eqnarray}
\end{proof}
\subsection{Proof of the Bayes DRO policy result in Section \ref{sec:numerical_bayes}}
\label{sec:proof_numerical_small}
\begin{proof}{Proof of Proposition \ref{thm:pi_policy}}
By Lemma \ref{thm:strong_duality}, we have
\begin{eqnarray}
	Q_{\rm DRO} (\pi^*_{\rm DRO})
	&=& \sup_{\pi \in \overline{\Pi}} \sup_{\alpha\geq 0}\left\{ -\alpha \log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta\right\}  \notag \\
&=& \sup_{\alpha\geq 0}\sup_{\pi \in \overline{\Pi}}\left\{ -\alpha \log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta\right\}.
\label{eq:numerical_duality}
\end{eqnarray}
The inner maximization \eqref{eq:numerical_duality} can be further simplified as
\begin{eqnarray*}
&&\sup_{\pi \in \overline{\Pi}}\left\{ -\alpha \log\E_{\P_0}\left[\exp(-Y(\pi(X))/\alpha)\right] - \alpha \delta\right\} \\
&=&\sup_{\pi \in \overline{\Pi}}\left\{ -\alpha \log\E_{\P_0}[ \E\left[\exp(-Y(\pi(X))/\alpha)|X]\right] - \alpha \delta\right\} \\
&=&-\alpha \log\E_{\P_0}\left [\inf_{\pi \in \overline{\Pi}} \E\left[\exp(-Y(\pi(X))/\alpha)|X\right] \right] - \alpha \delta.
\end{eqnarray*}
By the moment generating function of normal distributions, we have
\begin{eqnarray*}
\inf_{\pi \in \overline{\Pi}} \E\left[\exp(-Y(\pi(X))/\alpha)|X\right]=\min_{a\in \mathcal{A}}\left\{\E\left[\exp(-Y(a)/\alpha)|X\right]  \right\},
\end{eqnarray*}
and the optimal dual variable is
\begin{equation*}
\alpha^*(\pi^*_{\rm DRO})=\argmax_{\alpha \geq 0} \left \{-\alpha \log\E_{\P_0}\left [\min_{a\in \mathcal{A}}\left\{ \E_{\P_0}\left[\left. \exp\left(-Y(a)/\alpha\right)\right| X\right] \right\}\right] - \alpha \delta \right \}.
\end{equation*}
Finally, we have for any $a \in \mathcal{A}$, the set
\[
\{x \in \mathcal{X}: \pi^*_{\rm DRO} (x) = a\} = \left\{ x \in \mathcal{X}:\E_{\P_0}\left[\left. \exp\left(-Y(a)/\alpha\right)\right| X=x\right]
\leq \E_{\P_0}\left[\left. \exp\left(-Y(a')/\alpha\right)\right| X=x\right],\text{ for }\forall a' \in \mathcal{A}/\{a\}\right\}
\]
is measurable.
\end{proof}
\subsection{Proof of the extension results in Section \ref{sec:extension}}
\begin{proof}{Proof of Lemma \protect\ref{lma:quantile_f_divergence}}
If $k=1$, we have $c_k(\delta)=1$, and thus Lemma \ref{lma:quantile_f_divergence} recovers Lemma \ref{lma:quantile}. For $k\in(1,+\infty)$, notice that
\begin{eqnarray*}
&&\left\vert \sup_{\alpha \in \reals}\left\{ -c_{k}\left( \delta \right)
\mathbf{E}_{\mathbf{P}_{1}}\left[ \left( -Y+\alpha \right) _{+}^{k_{\ast }}
\right] ^{\frac{1}{k_{\ast }}}+\alpha \right\} -\sup_{\alpha \in \reals
}\left\{ -c_{k}\left( \delta \right) \mathbf{E}_{\mathbf{P}_{2}}\left[
\left( -Y+\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}
}+\alpha \right\} \right\vert  \\
&\leq &c_{k}\left( \delta \right) \sup_{\alpha \in \reals}\left\vert
\mathbf{E}_{\mathbf{P}_{1}}\left[ \left( -Y+\alpha \right) _{+}^{k_{\ast }}
\right] ^{\frac{1}{k_{\ast }}}-\mathbf{E}_{\mathbf{P}_{2}}\left[ \left(
-Y+\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}}\right\vert
\\
&=&c_{k}\left( \delta \right) \sup_{\alpha \in \reals}\left\vert \mathbf{
E}_{_{\mathbf{P}_{U}}}\left[ \left( -q_{\mathbf{P}_{1}}\left( U\right)
+\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}}-\mathbf{E}_{
\mathbf{P}_{U}}\left[ \left( -q_{\mathbf{P}_{2}}\left( U\right) +\alpha
\right) _{+}^{k_{\ast }}\right] ^{\frac{1}{k_{\ast }}}\right\vert ,
\end{eqnarray*}
where $\mathbf{P}_{U}\sim U([0,1])$ and the last equality is based on the
fact that $q_{\mathbf{P}}\left( U\right) \overset{d}{=}\mathbf{P.}$

By the triangular inequality in $L^{p}\left( U\right) $ space, we have
\begin{eqnarray*}
&&\left\vert \mathbf{E}_{_{\mathbf{P}_{U}}}\left[ \left( -q_{\mathbf{P}
_{1}}\left( U\right) +\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{
k_{\ast }}}-\mathbf{E}_{\mathbf{P}_{U}}\left[ \left( -q_{\mathbf{P}
_{2}}\left( U\right) +\alpha \right) _{+}^{k_{\ast }}\right] ^{\frac{1}{
k_{\ast }}}\right\vert  \\
&\leq &\mathbf{E}_{_{\mathbf{P}_{U}}}\left[ \left\vert q_{\mathbf{P}
_{1}}\left( U\right) -q_{\mathbf{P}_{2}}\left( U\right) \right\vert
^{^{k_{\ast }}}\right] ^{\frac{1}{k_{\ast }}} \\
&\leq &\sup_{t\in \lbrack 0,1]}\left\vert q_{\mathbf{P}_{1}}\left( t\right)
-q_{\mathbf{P}_{2}}\left( t\right) \right\vert .
\end{eqnarray*}

\end{proof}
\label{sec:extension_proof}
\section{Experiments}
\label{sec:appendix-experiment}
This section provides implementation details for how to compute $\argmin_{\Theta\in \mathbf{R}^{(p+1)\times d}}\hat{W}_n(\pi_{\Theta},\alpha)$ where $\pi_{\Theta}$ is the multilinear policy associated with parameter $\Theta$. Recall the definition of $\hat{W}_n(\pi,\alpha)$ from definition \ref{def:phi_alpha} that
\begin{equation*}
\hat{W}_n(\pi,\alpha) =
\frac{1}{nS_n^\pi}\sum_{i=1}^{n} W_i(\pi, \alpha)
=
\frac{\sum_{i=1}^n
\frac{\mathbf{1}\{\pi(X_i) = A_i\}}{\pi_0(A_i\mid X_i)}\exp(-Y_i(A_i)/\alpha)
}{\sum_{i=1}^{n}\frac{\mathbf{1\{}\pi(X_{i})=A_{i}\mathbf{\}}}{\pi _{0}\left( A_{i}|X_{i}\right) }}
.
\end{equation*}

As we did in Section \ref{sec:numerical_linear_class}, we employ the smooth approximation of the indicator function
$$
\mathbf{1\{}\pi_{\Theta}(X_{i})=A_{i}\mathbf{\}}
\approx
\frac{
\exp(\theta_{A_i}^{\top}X_i)}{ \sum_{a = 1}^{d}\exp(\theta_{a}^{\top}X_i)}.
$$
Now for $i = 1,\ldots, n$, we the smooth weight function
$p_i: \mathbf{R}^{(p+1)\times d} \rightarrow \mathbf{R}_{+}$ as
$$
p_i(\Theta) \triangleq
\frac{\exp(\theta_{A_i}^{\top}X_i)}{\pi_{0}\left( A_{i}|X_{i}\right)
\sum_{a = 1}^{d}\exp(\theta_{a}^{\top}X_i)
},
$$
then the estimator $\hat{W}_n(\pi_{\Theta},\alpha)$ admits the smooth approximation
\begin{equation*}
\hat{W}_n(\pi_{\Theta},\alpha)
\approx
\tilde{W}_n(\pi_{\Theta},\alpha)
\triangleq
\frac{\sum_{i=1}^n
p_i(\Theta) \exp(-Y_i(A_i)/\alpha)
}{\sum_{i=1}^{n} p_i(\Theta)}
.
\end{equation*}
In addition, we have
\begin{align*}
\nabla_{\Theta}
\tilde{W}_n(\pi_{\Theta},\alpha)
&
=\tilde{W}_n(\pi_{\Theta},\alpha) \nabla_{\Theta}
\log \left(
\tilde{W}_n(\pi_{\Theta},\alpha)
\right)\\
&\approx
\tilde{W}_n(\pi_{\Theta},\alpha)
\cdot
\left(
\nabla_{\Theta}
\log \left(
\sum_{i=1}^n
p_i(\Theta) \exp(-Y_i(A_i)/\alpha)
\right)
-\nabla_{\Theta} \log \left(
\sum_{i=1}^{n} p_i(\Theta)
\right)\right)
\\
&=
\tilde{W}_n(\pi_{\Theta},\alpha)
\cdot
\left(
\frac{\sum_{i=1}^n
\nabla_{\Theta}p_i(\Theta) \exp(-Y_i(A_i)/\alpha)}{\sum_{i=1}^n
p_i(\Theta) \exp(-Y_i(A_i)/\alpha)}
-
\frac{\sum_{i=1}^n
\nabla_{\Theta}p_i(\Theta) }{\sum_{i=1}^n
p_i(\Theta)}
\right).
\end{align*}
Therefore, we can employ gradient to descent to solve for $\Theta$ that minimizes $\tilde{W}_n(\pi_{\Theta},\alpha)$, which approximately minimizes $\hat{W}_n(\pi_{\Theta},\alpha)$ as well. This is how we solve for $\argmin_{\Theta\in \mathbf{R}^{(p+1)\times d}}\hat{W}_n(\pi_{\Theta},\alpha)$ in implementation.

\end{document}