- 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
- 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.
- 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
-
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.
-
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
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 , 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 , while action B pays or with equal probability. Both actions have nominal mean . With squared transport cost and a reward ambiguity radius of , the adversary can reduce A’s reward to zero. Reducing B’s reward to zero would cost , since half its mass starts at . 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 and , and two policies that always choose action A or always choose action B. Their rewards across the two contexts are and , respectively. With the context distribution fixed, A has the higher value, versus . With a context OT radius of and unit cost for moving mass between contexts, the adversary can move of the probability mass from the first context to the second. The worst-case values are then for A and 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.
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∗ 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⋆ 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, 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 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=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=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.