acceptodds
Under review as a conference paper at ICLR 2027

Minimax Optimality for Factored Optimal-Transport Distributionally-Robust Policy Learning in Contextual Bandits

Abstract

Offline contextual-bandit policies may be deployed under simultaneous shifts in the context distribution and reward laws. We study policy learning for a factored distributionally robust optimization (DRO) objective that models these shifts through separate ambiguity sets. Optimal transport (OT) ambiguity sets are particularly suitable for this purpose, allowing the transport cost to encode application-specific severity of a shift. We develop a pessimistic OT-DRO learner based on sharp confidence bounds for robust rewards and analyze context estimation using a distribution-dependent concentration bound. Requiring knowledge of neither the behavior policy nor the context distribution, our learner achieves a regret of order . Our robust optimal-policy coverage coefficient is a natural generalization of the single-policy coverage coefficient in prior non-robust pessimism work, capturing the additional statistical difficulty caused by worst-case context shift. A matching lower bound shows that this rate, including its dependence on , is minimax-optimal up to constants.

Primary area:
reinforcement learning
Keywords:
Offline contextual bandits, distributionally robust optimization, optimal transport, pessimistic policy learning, distribution shift, minimax optimality

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_xaPHOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies offline policy learning in finite-context, finite-action contextual bandits under a factored distributionally robust objective, with separate optimal-transport ambiguity sets for the context distribution and for each conditional reward distribution. It proposes a pessimistic learner built on a cellwise confidence bound for the robust reward, and proves a regret bound of order D·C_rob·√(log(|X||A|/δ)/n). Here C_rob is a “robust optimal-policy coverage” coefficient: it requires coverage only along an optimal robust policy, taken in the worst case over admissible context shifts. A matching lower bound shows that this rate is minimax-optimal up to constants. Experiments include synthetic simulations and an application to the Open Bandit Dataset.

Critical strengths
  1. The paper characterizes the rate fully, including its dependence on the coverage coefficient, the log(|X||A|/δ) term, and the confidence level, with explicit constants. Replacing the uniform coverage requirement of prior factored-DRO work with coverage along an optimal policy is a meaningful improvement in the action dimension.
  2. The reward-level bound exploits the fact that the OT dual integrands are monotone in the dual parameter, which reduces a supremum over a continuous parameter to a single DKW application. This removes the dependence on reward-support size in prior work and extends the bound to continuous reward distributions.
Critical weaknesses
  1. The experiments do not test the paper’s main claims. In the synthetic coverage experiment (Appendix E.2), the context distribution is uniform and the optimal action has the same minimum propensity as all suboptimal actions, so C*_rob coincides with the uniform-coverage factor of prior work. The Open Bandit Dataset experiment uses uniform-random logging with no distribution shift. In both experiments, the unrestricted policy class makes the learned policy independent of the context radius ε_X, so context robustness plays no role. An experiment with rarely logged suboptimal actions, a non-uniform context distribution, and a policy class for which ε_X matters is needed.

  2. Combining pessimism with a coverage coefficient taken in the worst case over an ambiguity set closely parallels prior work on robust offline RL, e.g., Shi & Chi (JMLR 2024) and Blanchet et al. (NeurIPS 2023), of which contextual bandits are the horizon-one special case.

Questions for authors

Please see weakness.

2 comments

We thank the reviewer for their feedback on the experimental design and for pointing out the connection to prior work on robust offline RL.

In the synthetic coverage experiment, the context distribution is uniform and the optimal action has the same minimum propensity as all suboptimal actions, so Crob∗C^*_{rob} coincides with the uniform-coverage factor of prior work.

We agree that the two coverage factors coincide in Appendix E.2. That experiment aims to illustrate the predicted scaling with sample size and coverage in this setting.

In order to address your concern, we added a separate experiment in Appendix E.3 of the revised PDF to distinguish the two factors. At each of three sample sizes, we reduce the logging probability of one suboptimal action while keeping the optimal-action logging probabilities fixed. The worst-cell coverage factor rises from 64 to 4096, while Crob⋆C^\star_{\rm rob} stays at 64. Mean robust regret decreases modestly (3.8%–7.6% across the three sample sizes), with all three paired 95% Monte Carlo intervals for the change below zero.

The Open Bandit Dataset experiment uses uniform-random logging with no distribution shift. The unrestricted policy class makes the learned policy independent of the context radius ϵX\epsilon_{\mathcal{X}}, so context robustness plays no role.

It is true that policy selection in the unrestricted OBD experiment is independent of the context radius. In order to address your concern, we added a geographic holdout experiment on the International Stroke Trial in Section 5.3 of the revised PDF. The context distributions of the four held-out countries have total-variation distances of 0.031 to 0.187 from the pooled training distribution, which creates a plausible distributional shift. A 30% average cap on heparin use couples decisions across contexts, allowing the context ambiguity radius ϵX\epsilon_{\mathcal{X}} to affect the learned policy. Table 9 shows that the context radius changes the learned policy in practice.

On the held-out test countries, the selected OT-DRO policy achieved 43.36% AIPW, 7.06 percentage points above the control with both radii set to zero (paired 90% confidence interval [1.24, 11.45]).

Combining pessimism with a coverage coefficient taken in the worst case over an ambiguity set closely parallels prior work on robust offline RL, of which contextual bandits are the horizon-one special case.

We agree that pessimism and robust partial-coverage measures have been studied in offline RL, notably by Shi and Chi (JMLR 2024) and Blanchet et al. (NeurIPS 2023). Their coverage coefficients are based on worst-case occupancy ratios over admissible transition models, whereas ours captures worst-case context shifts through an occupancy-weighted sum of inverse square roots of logged context–action probabilities.

An important distinction lies in the uncertainty being modeled. The cited robust offline RL results consider uncertainty in state transitions while keeping rewards fixed. At H=1H=1, transition uncertainty does not affect the policy value, since the episode terminates after the first reward. In contrast, our setting allows both the initial context distribution and the conditional reward laws to shift under separate OT ambiguity sets. Consequently, our guarantees do not follow directly by specializing these transition-robust RL results to H=1H=1.

Beyond this distinction, we establish a finite-sample regret bound under general OT costs and bounded, potentially continuous rewards, together with a matching minimax lower bound on a constructed family in which both context and reward shifts are active. These results characterize the statistical difficulty of learning under the factored OT-DRO formulation.

AuthorsOpenReview ↗

Two Examples of Context and Reward Shift vs Transition Shift

The following examples show how reward and context ambiguity can each change the optimal decision at H=1H=1, where transition ambiguity in the cited results drops out of the policy value.

Reward shift. Consider a single context with two actions. Action A always pays 1/21/2, while action B pays 00 or 11 with equal probability. Both actions have nominal mean 1/21/2. With squared transport cost and a reward ambiguity radius of 1/41/4, the adversary can reduce A’s reward to zero. Reducing B’s reward to zero would cost 1/21/2, since half its mass starts at 11. Thus B has a strictly positive worst-case mean and is robustly optimal. Therefore, our reward-robust models distinguish the two actions, whereas the horizon-one transition-robust models in the cited papers give both actions the same value.

Context shift. Consider two contexts with nominal probabilities 3/43/4 and 1/41/4, and two policies that always choose action A or always choose action B. Their rewards across the two contexts are (1,0)(1,0) and (0.7,0.5)(0.7,0.5), respectively. With the context distribution fixed, A has the higher value, 0.750.75 versus 0.650.65. With a context OT radius of 1/41/4 and unit cost for moving mass between contexts, the adversary can move 1/41/4 of the probability mass from the first context to the second. The worst-case values are then 0.500.50 for A and 0.600.60 for B. The ranking reverses because the shift changes which contexts the policy faces before it acts. Perturbing a transition after the only action cannot reproduce that change in the cited horizon-one models.

We hope these examples clarify why the horizon-one specialization of the cited transition-robust models does not recover our setting. If time permits before the discussion closes, we would appreciate hearing whether our responses have addressed your concerns.

Reviewer_WrQgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies offline policy learning in finite contextual bandits under separate optimal-transport ambiguity sets for the context distribution and conditional reward distributions. The learner estimates each robust reward through its OT dual, subtracts a confidence penalty, and maximizes the resulting pessimistic robust value. For the unrestricted policy class, policy selection reduces to a per-context argmax.

The authors derive a robust-reward confidence bound that does not depend on reward-support size and a regret bound controlled by a robust optimal-policy coverage coefficient. They also provide a matching worst-case lower bound. Synthetic experiments examine the confidence bound and the dependence of regret on sample size and coverage. On the Open Bandit Dataset, the method achieves the highest reported nominal SNIPS estimates.

Critical strengths

S1. Coverage-dependent regret guarantees.

The upper bound requires action coverage only along an optimal robust policy, rather than uniformly over all actions. The proposed coefficient also captures how admissible context shifts can emphasize poorly covered contexts. The lower bound shows that this dependence can be necessary in the worst case. The learner requires neither the true behavior policy nor the true context distribution.

S2. Robust-reward confidence bound.

The confidence bound does not depend on reward-support size and applies to continuous bounded rewards and general admissible transport costs. This provides a useful improvement over the support-dependent bound of Shen et al. (2024).

Critical weaknesses

W1. Limited practicality beyond the tabular setting.

The approach assumes a finite context space and estimates robust rewards separately for each context–action pair. This is very restrictive for real-world applications where contexts are high-dimensional and continuous, where repeated observations of the same pair can be scarce (e.g., see most OPE/OPL literature). The method does not share information across similar contexts. Applying it in these settings would therefore require discretization or additional modeling, whose effect on the guarantees is not analyzed.

W2. Limited real-data evaluation.

The real-data evaluation is restricted to three campaigns from a single dataset, OBD. The improvements over the closest baseline, factored W-DRO, are around 0.03-0.08 percentage points, without uncertainty estimates for these differences. This makes it difficult to assess the reliability of the improvements. Evaluation on additional datasets and reporting confidence intervals would strengthen the evidence for the method’s practical benefits.

Questions for authors

Q1. Could the authors clarify whether the method and guarantees can accommodate continuous contexts?

Q2. Could the authors expand the real-data experiments?

3 comments

We thank the reviewer for their constructive feedback and for highlighting the coverage-dependent regret guarantee and the robust reward confidence bound for continuous rewards. We address the reviewer's questions below.

Could the authors clarify whether the method and guarantees can accommodate continuous contexts?

The factored objective can be formulated for continuous contexts. Our estimator and regret guarantees assume finite contexts, as do the factored guarantees of Mu et al. (2022, Factored DRO: Factored Distributionally Robust Policies for Contextual Bandits) and Shen et al. (2024, Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Bandits). To handle continuous contexts, Mu et al. (2022, Section 5) propose a practical algorithm using function approximation that may not have the same convergence guarantees.

A regret guarantee for continuous contexts can be obtained by fitting a conditional mean model for each action. Consider binary rewards with absolute transport cost and a compact metric context space with a W1W_1 ambiguity set of fixed positive radius ϵX\epsilon_{\mathcal X}. The worst-case reward is the conditional mean minus ϵY\epsilon_{\mathcal Y}, clipped at zero. A uniform error bound rnr_n for the fitted means therefore also bounds the error in the estimated worst-case rewards. Centering the context ambiguity set at the empirical distribution P^0\widehat P^0 adds at most W1(P0,P^0)/ϵXW_1(P^0,\widehat P^0)/\epsilon_{\mathcal X} to the policy-value error. Maximizing the estimated robust value then gives regret at most 2(rn+W1(P0,P^0)ϵX).2\left(r_n+\frac{W_1(P^0,\widehat P^0)}{\epsilon_{\mathcal X}}\right). For i.i.d. contexts on a compact metric space, the W1W_1 term converges to zero, so the regret bound vanishes whenever rn→0r_n\to 0.

Could the authors expand the real-data experiments? Evaluation on additional datasets and reporting confidence intervals would strengthen the evidence for the method’s practical benefits.

In order to illustrate our practical improvement with reliability, we added a geographic holdout experiment on the International Stroke Trial (IST) in Section 5.3 of the revised PDF. Across four held-out test countries, OT-DRO achieved the highest estimated policy value (43.36% by AIPW), improving on the zero-radii control by 7.06 percentage points (paired 90% confidence interval [1.24, 11.45]). Table 3 reports paired 90% confidence intervals for the improvement over all four baselines, and each interval lies above zero.

Reviewer_WrQgOpenReview ↗

Thank you for the effort!

Many thanks for the authors for their rebuttal. W2 is addressed, but the practical limitation of the finite contexts assumption remains. I will maintain my score.

Thank you again for keeping the positive score and highlighting our coverage coefficient as well as our confidence bound for robust rewards. Those are key ingredients in our regret upper bound, which matches the lower bound up to constants.

We agree that the finite-context assumption limits the applicability of our estimator in high-dimensional settings. We focused on finite contexts to establish, to our knowledge, the first matching minimax regret bounds for offline policy learning in factored distributionally robust contextual bandits.

The factored objective also applies to continuous contexts. Extending the estimator and its guarantees requires additional assumptions and techniques, as illustrated by the regression example in our rebuttal. We appreciate your suggestion to broaden the method’s practical applicability and leave a general extension to continuous contexts and the corresponding minimax analysis to future work.

Reviewer_vKbyOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers a offline policy learning problem with distribution shifts. In particular, a optimal transport type of shift is considered and a distributionally robust optimization (DRO) method is proposed to address the shifted contexts and rewards. A regret bound is proved; it is independent of the reward support cardinality and minimax optimal. Simulation results are provided to validate the effectiveness of the proposed method.

Critical strengths

The paper is easy to follow and the construction of both the method and the results are clear. It shows a clear improvement over the previous method. The reward conditionality independent regret result is interesting as it indicates that less conservative policy learning is possible under distribution shifts.

A lower bound is also provided. Per my knowledge, no such lower bound was studied before. This result shows the effectiveness of the proposed method.

Critical weaknesses

The problem setting is not new. Especially, DROs for contextual bandit / RL under various distance/divergence metrics have been extensively studied. I think one big problem/challenge in DRO is the formulation rather than the proofs of the regrets. For instance, all factored contexts are independent; this makes the optimization problem decoupled but it might be too conservative. For instance, the worst case distribution for similar contexts might be very different under the factor setting. Is this something true for practical applications?

Questions for authors

Can you explain the main difficulty of having the general OT distance in the proofs compared to the standard 1-wasserstein distance?

Can you provide some recommendations on how to select a particular OT distance metric? I believe this is a very important topic in offline RL in general.

1 comment

We thank the reviewer for their constructive feedback and for recognizing the novelty of our matching minimax lower bound as well as the improvement over the previous methods. We address the reviewer's questions below.

The worst case distribution for similar contexts might be very different under the factor setting. Is this something true for practical applications?

We agree that the factored ambiguity set can be conservative when a common change is expected to affect similar contexts in similar ways. Because the set allows their conditional reward laws to shift separately, it can include combinations of shifts that are unlikely to occur together in practice. However, similar contexts do not necessarily experience identical reward shifts, particularly when unobserved factors affect their responses differently. Moreover, the dependence structure between such shifts may not be reliably known, making it difficult to impose appropriate coupling constraints.

A practical advantage of factoring is that context and conditional reward shifts can be modeled and calibrated separately. For example, deployment in a new population may substantially change the mix of contexts while leaving the conditional reward laws largely stable. Mu et al. (2022, Section 6.2) reported that factored DRO outperformed a joint KL-DRO baseline in binary-reward experiments under context shift, while Shen et al. (2024) adopted the same separation in their Wasserstein formulation.

When domain knowledge supports a shared mechanism across similar contexts, coupling their reward shifts is a natural extension.

Can you explain the main difficulty of using general OT costs in the proofs compared to the standard 1-Wasserstein distance?

For the standard 1-Wasserstein distance on [0,D][0,D], the robust reward has the closed form q(x,a)=max⁡0,EY∼Qx,a0[Y]−ϵYq(x,a)=\max\\{0,\mathbb{E}_{Y\sim Q^0_{x,a}}[Y]-\epsilon_{\mathcal Y}\\}. The plug-in error is therefore bounded by the error in estimating the cell mean, so ordinary concentration for a bounded mean suffices.

For general OT costs, the dual optimizes over a continuum of λ\lambda, and we need to control the empirical error uniformly over that family. A simple approach is to discretize λ\lambda and use Lipschitz continuity between grid points with a union bound, but this would add a log⁡m\log m term inside the square root for a cell with mm observations. Meanwhile, our proof, as discussed in Remark 1, uses the pointwise ordering of the dual integrands in λ\lambda. Their level sets are nested, so a layer-cake representation and the Dvoretzky-Kiefer-Wolfowitz inequality give uniform control without the grid penalty.

Our ordered-integrand argument is new relative to the four approaches in Section 1.4 and Table 1. Using this argument, our finite-sample guarantee avoids the known-propensity assumption of Si et al. (2020), the nuisance-rate conditions of Kallus et al. (2022), the extra log⁡n\sqrt{\log n} factor and dual lower bound of Mu et al. (2022), and the reward-support-cardinality term of Shen et al. (2024). Our cellwise bound applies to continuous rewards and helps match the minimax lower bound up to constants.

Can you provide some recommendations on how to select a particular OT distance metric?

Domain knowledge can guide the selection of OT ground costs and ambiguity radii. For context shifts, the ground cost can assign smaller values to transitions between similar contexts, while the radii reflect the anticipated magnitudes of context distribution and conditional reward shifts. Data-driven approaches, including metric learning, may also help construct suitable ground costs when sufficient information is available, as demonstrated by Blanchet et al. (2019) in Data-Driven Optimal Transport Cost Selection for Distributionally Robust Optimization.

When data from multiple environments are available, we recommend selecting the ground costs and radii through validation on environments representative of the intended deployment. We illustrate this approach in the new International Stroke Trial experiment (Section 5.3 of the revised manuscript). Specifically, we compare discrete and normalized Hamming context costs, calibrate candidate context-radius scales using training countries, and select the context cost and both ambiguity radii based on estimated policy value in validation countries. The selected configuration is then evaluated on separate, held-out test countries.

This procedure provides a practical way to select OT costs and ambiguity radii while avoiding the use of test environments for model selection.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions and rebuttal responses

We thank the reviewers for the feedbacks. We added two experiments to the revised manuscript.

  • International Stroke Trial (Section 5.3 and Appendix E.5). The geographic split creates a plausible distributional shift between training and test countries. The restricted policy class allows context radius to change the learned policy. Our method achieved higher estimated policy value than all baselines, with paired confidence intervals supporting each improvement.
  • Synthetic coverage experiment (Appendix E.3). As worst-cell coverage worsened, our robust coverage coefficient stayed fixed and mean robust regret did not increase.

In our individual replies, we also address the following points.

  • Reviewer vKby. We discuss when the factor setting can be conservative, how the proof effectively handles general OT costs, and how to select OT costs and ambiguity radii in practice.
  • Reviewer WrQg. We clarify the finite-context assumption and outline conditions under which a regret guarantee can extend to continuous contexts.
  • Reviewer xaPH. We explain how our guarantees relate to prior work on robust offline RL and why they do not follow directly from its horizon-one specialization.

We would appreciate it if you could read our responses and let us know if any concerns remain. We would be happy to clarify any points before the discussion closes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.