Distributionally Robust Batch Contextual Bandits

The aforementioned applications ²²2Other applications include deploying a personalized education curriculum and/or digital tutoring plan based on students’ characteristics in a different school/district than from where the data was collected. highlight the need to learn a personalization policy that is robust to unknown shifts in another environmentt, an environment of which the decision maker has little knowledge or data. Broadly speaking, there can be two sources of such shifts:

1. 1.

   Covariate shift: The population composition – and hence the marginal distribution of the covariates – can change. For instance, in the product recommendation example, demographics in different markets will be different (e.g. markets in developed countries will have more people that are educated than those in developing countries), and certain segments of the population that are a majority in the old market might be a minority in the new market.

2. 2.

   Concept drift: How the outcomes depend on the covariates and prescription can also change, thereby resulting in different conditional distributions of the outcomes given the two. For instance, in product recommendation, large market segments in the US (e.g. a young population with high education level) choose to use cloud services to store personal data. In contrast, the same market segment in some emerging markets (where data privacy may be regulated differently) may prefer to buy flash drives to store at least some of the personal data.

These two shifts, often unavoidable and unknown, bring forth significant challenges in provisioning a suitable policy in the new environment, at least during the initial deployment phase. For instance, a certain subgroup (e.g. educated females in their 50s or older that live in rural areas) may be under-represented in the old environment’s population. In this case, the existing product recommendation data are insufficient to identify the optimal recommendation for this subgroup. This insufficiency is not a problem in the old environment, because the sub-optimal prescription for this subgroup will not significantly affect the overall performance of the policy given that the subgroup occurrence is not sufficiently frequent. However, with the new population, this subgroup may have a larger presence, in which case the incorrect prescription will be amplified and could translate into poor performance. In such cases, the old policy’s performance will be particularly sensitive to the marginal distribution of the subgroup in the new environment, highlighting the danger of directly deploying the same policy that worked well before.

Even if all subgroups are well-represented, the covariate shift will cause a problem if the decision maker is constrained to select a policy in a certain policy class such as trees or linear policy class, due to, for instance, interpretability and/or fairness considerations. In such cases, since one can only hope to learn the best policy in the policy class (rather than the absolute best policy), the optimal in-class policy will change when the underlying covariate marginal distribution shifts in the new environment, rendering the old policy potentially ineffective. Note that this could be the case even if the covariate marginal distribution is the only thing that changes.

Additionally, even more challenging is the existence of concept drift. Fundamentally, this type of shifts occurs because there are hidden characteristics at a population level (cultural, political, environmental factors or other factors that are beyond the decision maker’s knowledge) that also influence the outcome, but are unknown, unobservable. and different across the environments. As such, the decision maker faces a challenging hurdle: because these population-level factors that may influence the outcome are unknown and unobservable, making it is infeasible to explicitly model them in the first place, let alone deciding what policy to deploy as a result of them. therefore, the decision maker faces an “unknown unknown” dilemma when choosing the right policy for the new environment.

Situated in this challenging landscape, one naturally wonders if there is any hope to rigorously address the problem of policy learning in shifted environments with a significant degree of model uncertainty. This challenge leads to the following fundamental question: Using the (contextual bandits) data collected from one environment, can we learn a robust policy that would provide reliable worst-case guarantees in the presence of both types of environment shifts? If so, how can this be done in a data-efficient way? Our goal is to answer this question in the affirmative, as we shall explain.

To answer this question we adopt a mathematical framework which allows us to formalize and quantify environmental model shifts. First, we propose a distributionally robust formulation of policy learning in batch contextual bandits that accommodates both environment shifts. To overcome the aforementioned “unknown unknown” challenge that presents modelling difficulty, our formulation takes a general, fully non-parametric (and hence model-agnostic) approach to describe the shift at the distribution level: we allow the new environment to be an arbitrary distribution in a KL-neighborhood around the old environment’s distribution. As such, the shift is succinctly represented by a single quantity: the KL-radius $\delta$. We then propose to learn a policy that has maximum value under the worst-case distribution, that is optimal for a decision maker who wishes to maximize value against an adversary who selects a worst-case distribution to minimize value. Such a distributionally robust policy – if learnable at all – would provide decision makers with the guarantee that the value of deploying this policy will never be worse – and possibly better – no matter where the new environment shifts within this KL-neighborhood.

Regarding the choice of $\delta$, we provide two complementary perspectives on its selection process from a managerial viewpoint; each useful in the particular context one is concerned with. First, when data across different environments are available, one can estimate $\delta$ using such data. Such an approach would work well (and is convenient) if the new environment is different in similar ways in nature compared to how those other environments differ. For instance, in the voting application we consider in this paper (the August 2006 primary election in Michigan [35]), voting turnout data from different cities have been collected. As such, when deploying a new policy to encourage voters to vote in a different city, one can use the $\delta$ that is estimated from data across those different cities (we describe the technical procedures for such estimation in Section 6). Second, we can view $\delta$ as a parameter that can vary and that trades off with the optimal distributionally robust value: the larger the $\delta$, the more conservative the decision maker, the smaller the optimal distributionally robust value. We can compute the optimal distributionally robust values (and the corresponding policies) – one for each $\delta$ – for a range of $\delta$s; see Figure 1 for an illustration. Inspecting Figure 1, we see that the difference between the optimal distributionally robust value under $\delta=0$ (i.e., no distributional shifts) and the optimal distributionally robust value for a given $\delta$ representing the price of robustness. If the new environment had actually remained unchanged, then deploying a robust policy “eats” into the value. As such, the decision maker can think of this value reduction as a form of insurance premium budget in order to protect the downside, in case the new environment did shift in unexpected ways. Consequently, under a given premium budget (i.e. the amount of per-unit profit/sales that the decision maker is willing to forgo), a conservative choice would be for the decision maker to select the largest $\delta$ where the difference is within this amount ($\delta^{*}$ in Figure 1), and have the maximum robustness coverage therein. Importantly, if the new environment ends up not shifting in the worst possible way or not as much, then the actual value will only be higher. In particular, if the new environment does not shift at all, then the insurance premium the decision maker ends up paying after using the distributionally robust policy (under $\delta^{*}$) is smaller than the budget, because its value under the old environment is larger than its value under the corresponding worst-case shift. Consequently, selecting $\delta$ this way yields the optimal worst-case policy under a given budget³³3Of course, if the new environment ends up shifting a larger amount than $\delta^{*}$ and also in the worst possible way, then the actual value could be even smaller. However, in such situations, one would be much worse off with just using the old environment’s optimal policy, which is not robust at all..

Second, we show that learning distributionally robust policies can indeed be done in a statistically efficient way. In particular, we provide an algorithmic framework that solves this problem optimally. To achieve this, we first provide a novel scheme for distributionally robust policy evaluation (Algorithm 1) 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 we can solve using Newton’s method. We then 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 where $n$ is the number of data points. Building upon the estimator, we devise a distributionally robust policy learning algorithm (Algorithm 2) and establish that (Theorem 2) it achieves a $O_{p}(n^{-1/2})$ finite-sample regret. Such a finite-sample regret bound informs the decision maker that in order to learn an $\epsilon$-optimal distributionally robust policy, a dataset on the order of $\frac{1}{\epsilon^{2}}$ samples suffice with high probability. Note that this result is true for any $\delta$, where the regret bound itself does not depend on $\delta$. In addition, we also characterize the fundamental limit of this problem by establishing a $\Omega(n^{-1/2})$ lower bound for expected regret, thus making it clear that our policy learning algorithm is statistically optimal in the minimax sense. Taken together, these results highlight that we provide an optimal prescription framework for learning distributionally robust policies.

Third, we demonstrate the empirical efficacy and efficiency of our proposed algorithm by providing extensive experimental results in Section 5. We dedicate Section 6 to the voting problem mentioned previously using our distributionally robust policy learning framework and demonstrate its applicability on a real-world dataset. Finally, we extend our results to $f$-divergence measures and show our framework is still applicable even beyond KL-divergence (Section 7).

As mentioned, our work is closely related to the flourishing and rapidly developing literature on offline policy learning in contextual bandits; see, e.g, [28, 85, 89, 88, 76, 61, 45, 47, 46, 91, 43, 17]. Many valuable insights have been contributed: novel policy evaluation and policy learning algorithms have been developed; sharp minimax regret guarantees have been characterized in many different settings; and extensive and illuminating experimental results have been performed to offer practical advice for optimizing empirical performance. However, this line of work assumes the environment in which the learned policy will be deployed is the same as the the environment from which the training data is collected. In such settings, robustness is not a concern. Importantly, this line of work developed and used the family of doubly robust estimators for policy evaluation and learning [28, 91]. For clarification, we point out that this family of estimators, although related to robustness, does not address the robustness discussed in this paper (i.e. robustness to environment shifts). In particular, those estimators aim to stabilize statistical noise and deal with mis-specified models for rewards and propensity scores, where the underlying environment distribution is the same across test and training environments.

Correspondingly, there has also been an extensive literature on online contextual bandits, for example,  [53, 65, 31, 62, 18, 37, 3, 4, 66, 67, 44, 54, 2, 23, 54], whose focus is to develop online adaptive algorithms that effectively balance exploration and exploitation. This online setting is not the focus of our paper. See [14, 50, 74] for a few articulate expositions. Despite this, we do point out that as alluded to before and whenever possible, online learning can complement the distributionally robust policy learned and deployed initially. We leave this investigation for future work.

Additionally, there is also rapidly growing literature in distributionally robust optimization (DRO); see, e.g, [11, 22, 40, 69, 7, 33, 57, 26, 75, 70, 49, 81, 51, 59, 83, 56, 87, 1, 86, 73, 34, 16, 36, 12, 24, 48, 27, 39]. The existing DRO literature has mostly focused on the statistical learning aspects, including supervised learning and feature selection type problems, rather than on the decision making aspects. Furthermore, much of that literature uses DRO as tool to prevent over-fitting when it comes to making predictions, rather than dealing with distributional shifts. To the best of our knowledge, we provide the first distributionally robust formulation for policy evaluation and learning under bandit feedback and shifted environments, in a general, non-parametric space.

Some of the initial results appeared in the conference version [72], which only touched a very limited aspect of the problem: policy evaluation under shifted environments. In contrast, this paper is substantially developed and fully addresses the entire policy learning problem. We summarize the main differences below:

1. 1.

   The conference version focused on the policy evaluation problem and only studied a non-stable version of the policy evaluation scheme, which is outperformed by the stable policy evaluation scheme analyzed here (we simply dropped the non-stable version of the policy evaluation scheme in this journal version).

2. 2.

   The conference version did not study the policy learning problem, which is our ultimate objective. Here, we provide a policy learning algorithm and establish the minimax optimal rate $O_{p}(n^{-1/2})$ for the finite-sample regret by providing the regret upper bound as well as the matching regret lower bound.

3. 3.

   We demonstrate the applicability of our policy learning algorithms and provide results on a real-world voting data set, which is missing in the conference version.

4. 4.

   We provide practical managerial insights for the choice of the critical parameter $\delta$ which governs the size of distributional shifts.

5. 5.

   We finally extend our results to $f$-divergence measures, a broader class of divergence measures that include KL as a special case.

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 $\mathbf{R}^{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\mathbf{R}$ 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$ iid observed triples that comprise of the training data, where $(X_{i},Y_{i}(a^{1}),\dots,Y_{i}(a^{d}))$ are drawn iid from the fixed underlying distribution described above, and we denote this underlying distribution by $\mathbf{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 observed. Finally, we use $\mathbf{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.

The overlap assumption ensures that some minimum positive probability is guaranteed regardless of the context is. This assumption ensures sufficient exploration in collecting the training data, and indeed, many operational policies have $\epsilon$-greedy components. Assumption 1 is standard and commonly adopted in both the estimation literature ([63, 41, 42]) and the policy learning literature ([85, 89, 47, 76, 90]). Assumption 2 is made to ensure the $O_{p}(n^{-1/2})$ convergence rate.

With the aforementioned setup, the standard goal is to learn a good policy from a fixed deterministic policy class $\Pi$ using the training data, often known as the batch contextual bandits problem (in contrast to online contextual bandits), because all the data has already been collected 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:

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, which is equivalent to minimizing the discrepancy between the performance of the optimal policy and the performance of the learned policy $\pi$.

Using the policy value function $Q(\cdot)$ as defined in Definition 1 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 $\mathbf{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 $\mathbf{P}_{0}$ may not work well under the new test environment.

To address this issue, we propose a distributionally 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 $\mathbf{P}_{0}$. To that end, we start by introducing some terminology. First, the KL-divergence between two probability measures $\mathbf{P}$ and $\mathbf{P}_{0}$, denoted by $D(\mathbf{P}||\mathbf{P}_{0})$, is defined as $D(\mathbf{P}||\mathbf{P}_{0})\triangleq\int\log\left(\frac{d\mathbf{P}}{d\mathbf{P}_{0}}\right)\mathrm{d}\mathbf{P}.$ With KL-divergence, we can define a class of neighborhood distributions around a given distribution. Specifically, the distributional uncertainty set $\mathcal{U}_{\mathbf{P}_{0}}(\delta)$ of size $\delta$ is defined as $\mathcal{U}_{\mathbf{P}_{0}}(\delta)\triangleq\{\mathbf{P}\ll\mathbf{P}_{0}\mid D(\mathbf{P}||\mathbf{P}_{0})\leq\delta\}$, where $\mathbf{P}\ll\mathbf{P}_{0}$ means $\mathbf{P}$ is absolutely continuous with respect to $\mathbf{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}_{\mathbf{P}_{0}}$ instead. We remark that in practice, $\delta$ can be selected empirically. For example, we can collect historical distributional data from different regions and compute distances between them. Then, although the distributional shift direction is unclear, a reasonable distributional shift size $\delta$ can be estimated. Furthermore, we can also check the sensitivity of robust policy with respect to $\delta$ and choose an appropriate one according to a given insurance premium budget. We detail these two approaches in Section 6.4.

In other words, $Q_{\mathrm{\mathrm{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 $\mathbf{P}_{0}$. With this definition, the optimal policy $\pi^{*}_{\mathrm{\mathrm{DRO}}}$ is a policy that maximizes the distributionally robust value function: $\pi^{*}_{\mathrm{\mathrm{DRO}}}\in\arg\max_{\pi\in\Pi}\{Q_{\mathrm{\mathrm{DRO}}}(\pi)\}$. If such optimal policy does not exist, we can always construct a sequence of policies whose distributionally robust value converges to the supremum $\sup_{\pi\in\Pi}\{Q_{\rm DRO}(\pi)\}$. Then, all of our results can generalize to this case. Therefore, for simplicity, we assume the optimal policy exists. To be robust to the changes between the test environment and the training environment, our goal is to learn a policy such that its distributionally robust policy value is as large as possible, or equivalently, as close to the best distributionally robust policy as possible. We formalize this notion in Definition 3.

Several things to note. First, per its definition, we can rewrite regret as $R_{\mathrm{DRO}}(\pi)=Q_{\mathrm{DRO}}(\pi^{*}_{\mathrm{\mathrm{DRO}}})-Q_{\mathrm{DRO}}(\pi)$. Second, the underlying random policy that has generated the observational data (specifically the $A_{i}$s) could be totally irrelevant with the policy class $\Pi$. Third, when a policy $\hat{\pi}$ is learned from data and hence $R_{\mathrm{DRO}}(\hat{\pi})$ is a random variable, then 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$.

Regarding some other definitions of regret, one may consider choices such as

where for a fixed distribution $\mathbf{P}$, one compares the learned policy with the best one that could be done under perfect knowledge of $\mathbf{P}$. In this definition the adversary is very strong in the sense that it knows the test domain. Therefore, a problem of this definition is that the regret does not converge to zero when $n$ goes to infinity (even for a randomized policy $\pi$). We will not discuss this notion in this paper.

In order to learn a distributionally robust policy – one that maximizes $Q_{\mathrm{\mathrm{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.

The proof of Lemma 1 is in Appendix A.2.

The above strong duality allows us to transform the original problem of evaluating $\inf_{\mathbf{P}\in\mathcal{U}_{\mathbf{P}_{0}(\delta)}}\mathbf{E}_{\mathbf{P}}\left[Y(\pi(X))\right]$, where the (primal) variable is a infinite-dimensional distribution $\mathbf{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 $\mathbf{P}_{0}$. This then allows us to use an easily-computable plug-in estimate of the distributionally robust policy value. To easily reference the subsequent analysis of our algorithm, we capture the important terms in the following definition.

$W_{i}(\pi,\alpha)$ is a realization of the random variable inside the expectation in equation (2), and we approximate $\mathbf{E}_{\mathbf{P}_{0}*\pi_{0}}\left[\frac{\exp(-Y(A)/\alpha)\mathbf{1}\{\pi(X)=A\}}{\pi_{0}(A\mid X)}\right]$ by its empirical average $\hat{W_{n}}(\pi,\alpha)$ with a normalization factor $S_{n}^{\pi}$. Note that $\mathbf{E}[S_{n}^{\pi}]=1$ and $S_{n}^{\pi}\rightarrow 1$ almost surely. Therefore, the normalized $\hat{W_{n}}(\pi,\alpha)$ is asymptotically equivalent with the unnormalized $\frac{1}{n}\sum_{i=1}^{n}W_{i}(\pi,\alpha)$. The reason for dividing a normalization factor $S_{n}^{\pi}$ is that it makes our evaluation more stable; see discussions in [72] and [77]. The upper bound of $\alpha^{\ast}(\pi)$ proven in Lemma A11 of Appendix A.3 establishes the validity of the definitions $\alpha^{\ast}(\pi)$, namely, $\alpha^{\ast}(\pi)$ is attainable and unique.

By Hu and Hong [40, Proposition 1 and their discussion following the proposition], we provide a characterization of the worst case distribution in Proposition 1.

Proposition 1 shows that the worst case measure $\mathbf{P}(\pi)$ is an exponentially tilted measure with respect to the underlying measure $\mathbf{P}_{0}$, where $\mathbf{P}(\pi)$ puts more weights on the low end. Since $\alpha^{*}(\pi)$ can be approximated by $\alpha_{n}(\pi)$, and $\alpha_{n}(\pi)$ is explicitly computable as we shall see in Algorithm 1, we are able to understand how the worst case measure behaves. Moreover, we show that the worst case measure $\mathbf{P}(\pi)$ maintains mutual independence when $Y(a^{1}),\ldots,Y(a^{d})$ are mutually independent conditional on $X$ under $\mathbf{P}_{0}$ in the following Corollary.

The proofs of Proposition 1 and Corollary 1 are in Appendix A.2.

To compute $\hat{Q}_{\mathrm{\mathrm{DRO}}}$, one needs to solve an optimization problem to obtain the distributionally robust estimate of the policy $\pi$. As the following lemma indicates, this optimization problem is easy to solve.

The proof of Lemma 2 is in Appendix A.2. Since the optimization problem $\hat{Q}_{\mathrm{\mathrm{DRO}}}=\max_{\alpha\geq 0}\left\{\hat{\phi}_{n}(\pi,\alpha)\right\}$ is maximizing a concave function, it can be computed using the Newton-Raphson method. Based on all of the discussions above, we formally give the distributionally robust policy evaluation algorithm in Algorithm 1. By Luenberger and Ye [55, Section 8.8], we have that $\hat{\phi}_{n}(\pi,\alpha)$ converges to the global maximum $\hat{Q}_{\mathrm{DRO}}(\pi)$ quadratically in Algorithm 1 if the initial value of $\alpha$ is sufficiently closed to the optimal value.

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

Theorem 1 ensures that we are able to evaluate the performance of a policy in a new environment using only the training data even if the new environment is different from the training environment. The proof of Theorem 1 is in Appendix A.3.

We now establish the finite-sample statistical performance guarantee for the distributionally robust optimal policy $\hat{\pi}_{\mathrm{DRO}}$. Before giving the theorem, we first need to define entropy integral in the policy class, which represents the class complexity.

The defined entropy integral is the same as Definition 4 in [91], which is a variant of the classical entropy integral introduced in [29], and the Hamming distance is a well-known metric for measuring the similarity between two equal-length arrays whose elements are supported on on discrete sets [38]. We then discuss the entropy integrals $\kappa^{(n)}\left(\Pi\right)$ for different policy classes $\Pi$.

The entropy integrals for the linear policy classes and decision-tree policy classes are discussed in Section 5.2 and Section 6.2, respectively. For the special case of binary action, we have the following bound for the entropy integral by [60] (see the discussion following Definition 4).

This result can be further generalized to the multi-action policy learning setting, where $d$ is greater than 2; see the proof of Theorem 2 in [60].

Graph dimension is a direct generalization of VC dimension. There are many papers that discuss the graph dimension and also a closely related concept, Natarajan dimension; see, for example, [20, 21, 60, 58].

Theorem 2 demonstrates that with high probability, the distributionally robust regret of the learned policy $R_{\mathrm{DRO}}(\hat{\pi}_{\mathrm{DRO}})$ decays at a rate upper bounded by $O_{p}(\kappa^{(n)}/\sqrt{n})$.

The key challenge to the proof of Theorem 2 is that $Q_{\rm DRO}(\pi)$ is hard to quantify, since it is a non-linear functional of the probability measure $\mathbf{P}$. Thanksfully, Lemmas 5 and 6 allow us to transform the hardness of analysis of $Q_{\rm DRO}(\pi)$ into the well-studied terms such as the quantile and the total variation distance.

The detailed proof is in Appendix A.4. We see those bounds in (5) and (6) for the distributionally robust regret does not depend on the uncertainty size $\delta$. Furthermore, if $\sup_{n}\kappa^{(n)}<\infty$ including the finite policy classes, linear classes, decision-tree policy classes and the case where $VC(\Pi)$ or $Graph(\Pi)$ is finite, we have a parametric convergence rate $O_{p}(1/\sqrt{n})$. Further, if $\kappa^{(n)}=o_{p}(\sqrt{n})$, we have $R_{\mathrm{DRO}}(\hat{\pi}_{\mathrm{DRO}})\rightarrow 0$ in probability. Generally, we may expect the complexities of parametric classes are $O(1)$. Theorem 2 guarantees the robustness of the policy learned from the training environment given sufficient training data and low complexity of the policy class. This result means that the test environment performance is guaranteed as long as test and training environments do not differ too much. We will show this rate is optimal up to a constant in Theorem 3.

In this subsection, we provide a tight lower bound of the distributionally robust batch contextual bandit problem. First we define $\mathcal{P}(M)$ as the collection of all joint distributions of $(X,Y(a^{1}),Y(a^{2}),\ldots,Y(a^{d}),A)$ satisfying Assumption 1. To emphasize the dependence on the underlying distribution $\mathbf{P}_{0}$, we rewrite $R_{\mathrm{DRO}}(\pi)=R_{\mathrm{DRO}}(\pi,\mathbf{P}_{0})$. We further denote $\mathbf{P}^{\pi_{0}}_{0}$ to be the distribution of the observed triples $\left\{X,A,Y(A)\right\}$.