- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This work studies offline-to-online learning in finite-cell Bernoulli contextual bandits, where source and target mean rewards may differ but changes in action contrasts are bounded by a known valid upper bound . The authors establish matching upper and lower bounds on minimax expected regret with the rate up to logarithmic factors.
The authors propose a method that uses offline data to filter actions and adds exploration when needed to control regret, using information-directed sampling (IDS) to guide action selection. When is unknown, the authors use initial online observations to construct valid cell-specific upper bounds on the true relative bias. They further show that any uniformly valid upper bound on the true relative bias cannot be , even at a zero-bias instance.
Controlled simulations and recorded-feedback experiments evaluate Relative IDS under various values of source biases and sample sizes, highlighting both the benefits of offline information and the costs of calibration and exploration.
Critical strengths
-
The action-contrast formulation allows offline data to remain useful even when source and target reward levels are different. The authors establish matching minimax upper and lower bounds (up to logarithmic factors), characterizing how and the offline sample size affect achievable regret. These results provide a clear theoretical limit on how much offline data can improve online learning under the assumed structure.
-
The paper also examines how to obtain a valid relative-bias bound using initial online observations, while accounting for the regret incurred during calibration. The authors prove that a uniformly valid upper bound cannot be , even at a zero-bias instance. This identifies a concrete limitation on obtaining a sufficiently small relative-bias bound from the same online data.
Critical weaknesses
The main results are established under several restrictive assumptions, including i.i.d. uniform contexts over finite cells, Bernoulli rewards, balanced offline sampling, and a known relative-bias bound . Each of these assumptions may be reasonable for isolating and understanding the core offline-to-online problem, and together they allow a precise minimax characterization. However, it remains somewhat unclear what insights these results offer for more general contextual bandits with shared structure across contexts.
The assumption of a known is also important in practice. When the bound is estimated from initial online observations, the empirical benefits are less consistent. The experiments also illustrate that the theoretical protection provided by the exploration guard can come with additional finite-sample regret in some settings. Although the authors explicitly analyze the limitations of estimating a valid bound from online data and carefully account for calibration costs, these issues make it slightly difficult to assess how broadly the theoretical and practical advantages extend beyond the studied setting.
Questions for authors
Could the authors clarify which assumptions, such as independent finite context cells, Bernoulli rewards, and balanced offline sampling, are essential for the main minimax results, and which are mainly used to isolate the role of action-contrast bias? In particular, how might the insights from this analysis inform theoretical understanding, algorithm design, or practical applications in more general contextual bandits with shared structure across contexts?
7 comments
Thanks for the review, and here is the kind response to your question on shared structure (2)
What our tools contribute to algorithm design with shared features
Three parts of our analysis can guide algorithms for contextual bandits with shared features: a bias measure identifying which historical action contrasts remain reliable, confidence bounds for comparing actions, and an allocation argument that controls cumulative exploration. Their uses are as follows:
- Our contrast-based bias measure identifies which changes in a shared reward model affect action choice. If target means are and source means are , the drift in the contrast between actions is . The baseline change cancels. In a recommendation system, this distinguishes a platform-wide response shift from a change in the relative value of recommendations.
- Our gap construction combines source and target information for each action comparison. Intersecting valid source and target contrast intervals gives a tighter interval for that comparison. Taking the largest upper endpoint over competitors then bounds the candidate action's gap. In a shared-feature model, confidence widths would depend on pooled feature observations rather than separate per-cell counts. Data from one customer segment could then tighten action-gap bounds in another through their shared features.
- Our cumulative allocation argument shows what must be controlled to obtain a regret guarantee. A proposal based on source data can be useful before its frequentist gap bounds become tight. A uniform guarantee additionally requires control of cumulative gap cost. Our harmonic-count argument establishes this control for finite cells. In a shared-feature model, the natural counterpart of the pull counts is the pooled design matrix, and that of the harmonic sum is its elliptical potential. To carry the allocation guarantee over, feature-based gap bounds and weights must satisfy the same confidence, feasibility and cumulative-control requirements.
For shared features, these tools give a concrete design: construct confidence bounds for shared action contrasts and allocate exploration using those bounds. Appendix O.3 proves the case of known action correspondences, and Appendix O.6 tests that case experimentally.
Thanks for the review, and here is the kind response to your question on assumptions (3)
2. Which assumptions are essential and which can be checked or relaxed (W1; Q1)
Thank you for asking which assumptions are essential and which simplify the statement of the minimax result. A valid contrast bound supports source-assisted decisions, while several sampling and structural assumptions can be relaxed. Appendix O.3 treats nonuniform arrivals, unequal source counts, bounded rewards and known shared structure. The first table explains the role of each assumption in the main theorem. The second gives the conditions and guarantees for the extensions. Section 4 directs readers to this analysis, and the revisions are marked blue.
| Assumption | Role in the argument | Why the stated result uses it |
|---|---|---|
| Valid supplied | Retains a target-optimal action during source filtering; bounds source-assisted gaps | An underestimated bound can discard the target-optimal action; the claimed source-assisted guarantee then need not hold |
| Freely varying finite-cell parameters | Lets the lower bound place independent difficult decisions in cells | The factor is no longer intrinsic if cells share known decision parameters |
| Uniform i.i.d. contexts | Gives the visit-count distribution used by the stated lower bound | That lower-bound calculation is not automatically the rate for every arrival process |
| Balanced source sampling | Converts per-pair uncertainty into | Total can conceal missing information about a relevant action |
| Bernoulli rewards | Provides the stated KL intervals and hard instances | These exact intervals do not apply unchanged to an arbitrary reward distribution |
The extensions below cover known shared structure, nonuniform arrivals, unequal source counts and bounded rewards. Additional contrast drift is handled by enlarging the valid bias bound. Each row states the condition required and the guarantee that remains available.
| Assumption | Weaker condition or diagnostic | Result retained |
|---|---|---|
| Exact contrast tolerance | Allow extra drift and use the valid bound | Core rate increases by at most and retains its online cap; Appendix O.5 |
| Separate cells | Known action relabelings with common relabeled reward laws | Pooling removes in the reduction above; Appendix O.3 |
| Uniform arrivals | Nonanticipating arrivals with fixed conditional reward laws | The upper-bound proof uses realized visit counts; |
| Balanced source counts | Use each pair's observed count and its own confidence width; inspect coverage of all relevant actions | Valid filtering and count-dependent upper bounds; no rate based on total alone |
| Bernoulli observations | Independent rewards in | Mean-preserving Bernoullization gives the upper rate; the Bernoulli subfamily supplies the lower bound |
For the bounded-reward extension, replace each observed reward by $\mathbf1\lbrace U\le Y\rbrace $ using a fresh independent uniform . This transformation preserves the reward mean and hence the pseudo-regret objective. Applying the Bernoulli algorithm to the transformed observations gives the upper regret bound for bounded rewards.
Contrast information is needed to distinguish target environments with different best actions. Appendix O.1 constructs two target environments with the same historical reward distribution and the same absolute-bias allowance, but opposite best actions. Additional source observations cannot distinguish them; one compatible environment requires order regret. A sufficiently precise contrast certificate rules out the incompatible ordering. The magnitude of the valid bound determines the benefit: a large bound still permits the online regret cap, while a sufficiently small bound permits a strict improvement in the regret order.
Thanks for the review, and here is the kind response to your question on shared structure (1)
We sincerely thank you for recognizing the minimax characterization and the explicit treatment of calibration costs. We also appreciate your suggestions on assumptions, shared structure and empirical benefits. Below, we explain the additional theoretical analysis, experiments and corresponding manuscript revisions.
1. How our results apply to contextual bandits with shared structure (W1; Q2)
Thank you for suggesting that we explain the implications for contextual bandits with shared structure. With known action correspondences and shared reward distributions after relabeling across contexts, Relative IDS can pool biased historical data and
achieve a regret rate independent of the number of contexts. Appendix O.3 proves the reduction. Appendix O.6 tests pooling against separate learners at four context counts, keeping the historical budget fixed.For a practical interpretation, consider two customer segments. Recommendation A in one segment may play the same treatment role as recommendation B in the other. A known correspondence identifies these roles. When rewards have the same distribution after relabeling within each environment, observations can be pooled by role. A platform-wide change in response propensity may shift historical reward levels, while stable relative advantages still allow the pooled history to inform target decisions.
A common shift in reward levels can leave the action contrasts useful for transfer. Action-centered and semiparametric bandits already remove action-independent baselines when comparing actions during online learning. We study the additional value of historical information: how much history about the shared contrast reduces the required target interaction, and what information certifies that benefit.
We reduce the shared-context model to a single two-action bandit. Appendix O.3 takes known labels $z_x\in\lbrace -1,+1\rbrace $ and actions $a\in\lbrace -1,+1\rbrace $, with μx,a=u+azxθ/2,νx,a=v+azxθs/2,∣θs−θ∣≤β. Recode the action as b=azx. Its target mean is then u+bθ/2, its source mean is v+bθs/2, and neither depends on x. Thus:
The relabeling preserves each round's regret and the Bernoulli reward distribution. Applying the one-cell algorithm to the pooled observations therefore gives the second rate. Any one-cell, two-action instance can also be represented in this shared-context model, so the one-cell lower bound applies. These matching bounds use known correspondences and common reward distributions after relabeling.
We tested this reduction at four context counts with the same historical budget. The experiment uses N=8192, T=8000, K=2, target contrast θ=0.12, source contrast θs=0.16, and common level shift v−u=0.20. The valid contrast bound is 0.04. Each row uses 32 new paired seeds. Online IDS is also allowed to pool observations using the known correspondence. Lower total pseudo-regret is better. Pooled Relative IDS has zero regret in every run at all four context counts, compared with baseline means ranging from 10.47 to 37.73.
Pooled Relative IDS has
zero realized pseudo-regret in all 128 runsbecause the combined source sample allows it to filter out the inferior virtual action. With separate learners, the same source budget is divided among more cells, and mean regret reaches 145.60 at M=64. The paired intervals for the reduction relative to Online IDS exclude zero at M=4,16,64 and include zero at M=1. These intervals have approximate simultaneous 95% coverage across the four comparisons. The experiment illustrates the pooling reduction proved in Appendix O.3.