acceptodds
Under review as a conference paper at ICLR 2027

When Biased Offline Data Help Online Learning: The Role of Action Contrasts

Abstract

Historical reward levels can be systematically biased while preserving the action comparisons needed for a new decision problem. However, guarantees based on absolute reward-bias bounds can overlook this benefit when all actions share the same reward-level shift. We isolate this information object in a finite-cell Bernoulli contextual bandit by bounding the diameter of source–target reward biases across actions and leaving their common level unrestricted. With a supplied valid relative-bias bound , context cells, actions, balanced source observations, and target rounds, upper and same-model minimax lower bounds share the rate up to logarithms. For fixed , the minimax regret is if and only if and . Unlike absolute-discrepancy models, this class permits a large action-common shift; the familiar minimum-of-two rate is characterized here for that quotient information class. A relative-confidence allocation turns historical contrasts into observable gap bounds and permits any predictable proposal; information-directed sampling is one instantiation, not a condition for validity. When must be learned, target calibration is charged to regret, and a honesty barrier prevents this route from uniformly recovering the strict order gain within the same horizon. Controlled experiments recover the predicted phase boundary, while response-bank experiments expose the finite-sample costs of protection and of learning the contrast certificate.

Primary area:
learning theory
Keywords:
contextual bandits, offline-to-online learning, distribution shift, biased offline data, minimax regret

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_5PUVOpenReview ↗
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 β\beta. The authors establish matching upper and lower bounds on minimax expected regret with the rate Tmin⁡(MK/T,β+MK/N)T\min(\sqrt{MK/T},\beta+\sqrt{MK/N}) 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 β\beta is unknown, the authors use initial online observations to construct valid cell-specific upper bounds βxU\beta_x^U on the true relative bias. They further show that any uniformly valid upper bound on the true relative bias cannot be oP(T−1/2)o_P(T^{-1/2}), 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 β\beta and the offline sample size NN 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 oP(T−1/2)o_P(T^{-1/2}), 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 β\beta. 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 β\beta 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
AuthorsOpenReview ↗

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−θ∣≤β.\mu_{x,a}=u+az_x\theta/2,\qquad \nu_{x,a}=v+az_x\theta_s/2,\qquad |\theta_s-\theta|\le\beta. Recode the action as b=azxb=az_x. Its target mean is then u+bθ/2u+b\theta/2, its source mean is v+bθs/2v+b\theta_s/2, and neither depends on xx. Thus:

QuantitySeparate cell learnersPooling by the known treatment role
Source observations per decision parameterN/(2M)N/(2M)N/2N/2
Unknown target contrastsOne per cellOne shared contrast
Core attainable regret rate$T\min\lbrace \sqrt{M/T},\beta+\sqrt{M/N}\rbrace $$T\min\lbrace T^{-1/2},\beta+N^{-1/2}\rbrace $
Effect of the common level shift v−uv-uDoes not enter the contrast boundDoes not enter the contrast bound

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=8192N=8192, T=8000T=8000, K=2K=2, target contrast θ=0.12\theta=0.12, source contrast θs=0.16\theta_s=0.16, and common level shift v−u=0.20v-u=0.20. The valid contrast bound is 0.040.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.

Cells MMSeparate Relative IDS (ablation)Pooled Relative IDS (ours)Pooled Online IDS (baseline)Regret reduction vs Online IDS [simultaneous 95% interval]
10.000.0037.7337.73 [-27.75, 103.21]
43.860.0013.2013.20 [5.70, 20.70]
1650.330.0014.9614.96 [4.53, 25.39]
64145.600.0010.4710.47 [6.42, 14.52]

Pooled Relative IDS has zero realized pseudo-regret in all 128 runs because 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=64M=64. The paired intervals for the reduction relative to Online IDS exclude zero at M=4,16,64M=4,16,64 and include zero at M=1M=1. These intervals have approximate simultaneous 95% coverage across the four comparisons. The experiment illustrates the pooling reduction proved in Appendix O.3.

AuthorsOpenReview ↗

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:

  1. Our contrast-based bias measure identifies which changes in a shared reward model affect action choice. If target means are ft(x)+ϕ(x,a)⊤θtf_t(x)+\phi(x,a)^\top\theta_t and source means are fs(x)+ϕ(x,a)⊤θsf_s(x)+\phi(x,a)^\top\theta_s, the drift in the contrast between actions a,ba,b is (ϕ(x,a)−ϕ(x,b))⊤(θs−θt)(\phi(x,a)-\phi(x,b))^\top(\theta_s-\theta_t). The baseline change fs−ftf_s-f_t cancels. In a recommendation system, this distinguishes a platform-wide response shift from a change in the relative value of recommendations.
  2. 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.
  3. 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.

AuthorsOpenReview ↗

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.

AssumptionRole in the argumentWhy the stated result uses it
Valid supplied β\betaRetains a target-optimal action during source filtering; bounds source-assisted gapsAn underestimated bound can discard the target-optimal action; the claimed source-assisted guarantee then need not hold
Freely varying finite-cell parametersLets the lower bound place independent difficult decisions in MM cellsThe factor MM is no longer intrinsic if cells share known decision parameters
Uniform i.i.d. contextsGives the visit-count distribution used by the stated lower boundThat lower-bound calculation is not automatically the rate for every arrival process
Balanced source samplingConverts per-pair uncertainty into MK/N\sqrt{MK/N}Total NN can conceal missing information about a relevant action
Bernoulli rewardsProvides the stated KL intervals and hard instancesThese 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.

AssumptionWeaker condition or diagnosticResult retained
Exact contrast toleranceAllow extra drift ε\varepsilon and use the valid bound β+ε\beta+\varepsilonCore rate increases by at most TεT\varepsilon and retains its online cap; Appendix O.5
Separate cellsKnown action relabelings with common relabeled reward lawsPooling removes MM in the reduction above; Appendix O.3
Uniform arrivalsNonanticipating arrivals with fixed conditional reward lawsThe upper-bound proof uses realized visit counts; ∑xKTx≤MKT\sum_x\sqrt{KT_x}\le\sqrt{MKT}
Balanced source countsUse each pair's observed count and its own confidence width; inspect coverage of all relevant actionsValid filtering and count-dependent upper bounds; no rate based on total NN alone
Bernoulli observationsIndependent rewards in [0,1][0,1]Mean-preserving Bernoullization gives the upper rate; the Bernoulli subfamily supplies the lower bound

For the bounded-reward extension, replace each observed reward YY by $\mathbf1\lbrace U\le Y\rbrace $ using a fresh independent uniform UU. 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 T\sqrt T 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.

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

This paper studies the online Contextual bandit problem with finite contexts and actions, and a biased offline data source. The authors propose a new assumption called relative action bias, which measures the bias of the offline data source is controlled across actions under the level β\beta: max⁡a(νx,a−μx,a)−min⁡a(νx,a−μx,a)≤β,∀x\max_a (\nu_{x,a} - \mu_{x,a}) - \min_a (\nu_{x,a} - \mu_{x,a}) \leq \beta, \forall x. This bias assumption is more general than the single-action bias assumption in MIN-UCB. The authors propose an information-directed sampling (IDS) algorithm to resolve the online contextual bandit problem with a biased offline data source. The authors prove that the proposed algorithm achieves the minimax optimal regret bound up to logarithmic factors when the relative action bias upper bound is given. The authors also provide an explore-then-commit style algorithm for the case where β\beta is unknown, and show that no target-only calibration can certify a sharper confidence interval. The authors conduct experiments on both controlled Bernoulli instances and real response banks, and show that the proposed algorithm outperforms several baselines in terms of regret in the controlled instances, but only performs middlingly on the real response banks.

Critical strengths
  1. The author extends the constraint on the bias to a more general form, which is the relative action bias. Compared to the previous work, such as the single-action bias of MIN-UCB, satisfying the relative action bias is a more realistic and practical assumption.

  2. The proposed algorithm achieves the minimax optimal regret bound up to logarithmic factors when the relative action bias upper bound is given. The lower bound regret has two terms: one is TMK/(N+T)T\sqrt{MK/(N+T)}, which is the sampling error from the offline data source, and the other is Tmin⁡(β,MK/T)T\min(\beta,\sqrt{MK/T}), which is the bias error from the offline data source. The upper bound given in Theorem 1 matches the lower bound up to logarithmic factors, which shows that the proposed algorithm is minimax optimal.

  3. The author provides an explore-then-commit style algorithm for the case where β\beta is unknown (Section5). It allocates a fixed number of cc target samples to each action in each context cell, computes a per-cell upper confidence bound βxU\beta^U_x from the source and pilot confidence intervals, and then runs the relative-confidence rule with βxU\beta^U_x in place of β\beta. The pilot rounds and the calibration risk contribute to the regret in Eq.(11), so the guarantee has the cost of learning β\beta. In the appendix, the author provides Proposition2, showing that no target-only calibration can certify a sharper confidence interval, which clarifies that the strict order gain of Corollary1 requires an externally supplied β\beta.

  4. The author gives an experiment among 5 problem settings (five source mechanisms on controlled Bernoulli instances and five real response banks), and compares the proposed algorithm with a large number of baselines, including target-only methods (Online IDS, Thompson sampling, LinMED, Exp-KL-MS), direct source reuse (Source IDS, TS, greedy) and bias-aware methods (MIN-UCB, Anchor-TS). The results are strong on the controlled instances with a supplied β\beta (Table2), where Relative IDS has the lowest regret at every source budget, but only middling on the real response banks (Table4).

Critical weaknesses
  1. The writing is not clear in some parts, especially the problem definition. The authors should clearly define the problem in the first three sections. Additionally, I am glad to see that the authors admit to using AI tools to help with writing, but this does not mean that AI tools can help with presenting your ideas clearly. In many parts of the paper, the writing should be more concise and clear. For example, in Section 3, we can see that the authors give a lot of details about the algorithm, but it is better to give a clear and self-contained algorithm description in the main text, which will save readers a lot of time in understanding the proposed algorithm.

  2. The contribution of the paper is mixed with the related work. The authors claim that the constraint on the bias assumption is more general than MIN-UCB, but the reward assumption is more restrictive than MIN-UCB, since the reward in this paper is Bernoulli while the reward in MIN-UCB is 1-sub-Gaussian. The authors should clearly state the contribution of the paper and the difference between this paper and MIN-UCB.

  3. Why did the authors introduce the relative action bias? Does it have any practical applications that the single-action bias cannot cover but the relative action bias can cover?

Questions for authors

There are some minor questions I would like to ask the author to clarify:

  1. In line 134, why do we need to make NN is divisible by MKMK?

  2. In line 140, what is exactly the definition of νx,a\nu_{x,a}? Does it mean the mean of the source sample for cell xx and action aa?

  3. In line 194, what is the definition of Lt,aL_{t,a} and Ut,aU_{t,a}? Are we assuming that the tt is the time step in the online learning process?

  4. What is the exact problem solved by this paper? It is hard to find the problem definition clearly in the paper. I expected to see a clear problem definition in the first three sections, but I could not find it. In lines 148-150, it seems that the authors give a problem definition, but it is too vague to interpret. I would like to see a clear problem definition, as the authors did in section 3, lines 191-202 for the source-active set. (Although there are some notations not defined clearly in that part either.)

  5. What is the proposed algorithm? I understand that the authors propose an information-directed sampling (IDS) algorithm and give an illustration in Figure 1 and a description in Appendix E.3. It is better to have a clear and self-contained algorithm description in the main text, since the proposed algorithm is also the main contribution of the paper.

  6. In section 5, the authors propose an explore-then-commit style algorithm for the case where β\beta is unknown. How to choose the number of pilot rounds cc? Is it a fixed number or a function of TT? How does it affect the regret bound in Eq.~(11)?

10 comments
AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your comments on clarity (1)

We sincerely thank you for the careful reading and detailed suggestions on the problem definition, algorithm, notation and practical applications. We also appreciate your recognition of the minimax result. Below, we respond point by point and indicate the corresponding changes in the blue-marked manuscript.

1. How we revised the manuscript to improve clarity (W1; Q1–Q5)

Section 2 now states the learning problem, and Section 3 explains the complete algorithm, including what each formula computes and how that quantity is used to choose the next action. The table below gives the clarification for each concern and its location in the revised manuscript. All these changes are marked blue.

Point clarified (review reference)Answer or specific clarification in the revised manuscriptLocation
State the learning problem precisely (W1/Q4)We define the available source data, chosen-action target feedback, admissible mean class, adaptive policies and minimax regret objective togetherSection 2
Why must NN be divisible by MKMK? (Q1)Balanced allocation gives each cell–action pair exactly N/(MK)N/(MK) source observations. Divisibility makes this count an integer; it is not an additional statistical assumptionSection 2, source-sampling definition
What is νx,a\nu_{x,a}? (Q2)It is the unknown population mean of source rewards for cell xx, action aa. We distinguish it from the empirical source mean ν^x,a\widehat\nu_{x,a}Section 2, mean definitions
What are Lt,a,Ut,aL_{t,a},U_{t,a} and tt? (Q3)tt is the global target round. The endpoints form the current cell's KL interval using earlier observations of action aa, with interval [0,1][0,1] before its first observation. The separate clock ℓ\ell counts visits to that cellSection 3, after Eq. (3), and Algorithm 1
Give a self-contained main-text algorithm (W1/Q5)Algorithm 1 states initialization, gap calculation, proposal and exploration selection, action sampling, and the updates before the detailed derivationSection 3, Algorithm 1
Explain the formulas rather than accumulate details (W1)We explain why Eq. (3) uses the inner minimum and outer maximum. In the two-action example, source and target bounds 0.160.16 and 0.090.09 give dt,2=0.09d_{t,2}=0.09Section 3, after Eq. (3)
Explain the quantities and reasoning used by the exploration rule (W1/Q5)We state what Q,JQ,J sum, why controlling QQ gives the online cap, and why the minimizing exploration action makes a feasible allocation possibleSection 3, allocation paragraph and Eq. (4)
Identify the algorithmic contribution (Q5)We explain that a source-filtered target-UCB rule also attains the same worst-case regret caps. Our cumulative allocation rule retains those caps while allowing any predictable proposal, including an IDS proposal based on a misspecified posteriorSection 3, final paragraph
Explain the IDS operation (Q5)We identify squared posterior expected regret and information gain in Eq. (5). Each new proposal is drawn from the latest IDS distribution; the posterior updates after every reward, while recomputation is periodicSection 3, Eq. (5) and following text
State precisely what is more general than MIN-UCB (W2)We distinguish the broader relative-bias class within the common Bernoulli setting from the reward-law assumptions: our main result uses Bernoulli rewards, whereas MIN-UCB allows 1-sub-Gaussian rewardsSection 4
Give a practical source of relative-bias information (W3)The main text now introduces a reporting-channel example: an action-independent intercept change preserves contrasts when the slope and latent responses remain unchanged. The appendix gives the RAPPOR calculationSection 5, measurement-design paragraph; Appendix O.2
Clarify what happens after calibration (Q6; Summary/Strengths)The pilot rewards initialize counts and the posterior once; actions then continue adapting to new rewards, without committing to a fixed action. Every pilot round, including unfinished pilots, contributes to the cost in Eq. (11)Section 5
Explain how the pilot length is chosen and enters the bound (Q6)We state that cc is fixed before deployment and may depend on the known TT. It affects both the pilot cost BTB_T and the subsequent gap costs QxQ_x; development selects cc before validationSection 5, opening and paragraph after Eq. (11)
Distinguish the comparisons in the response-bank results (Summary/Strengths)We distinguish the full method's net gain over Online IDS from the matched comparisons isolating the source prior and testing the learned boundSection 6; diagnostic details in Appendix O.4
AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your questions on the problem and algorithm (2)

We study how much biased historical rewards can reduce worst-case target regret when the learner observes only the reward of its chosen action. The learner is given a valid upper bound on the change in action contrasts between the source and target environments. The precise problem is:

Given: MM context cells, KK actions, NN historical reward observations, and a valid bound β\beta. The unknown source and target means satisfy max⁡a(νx,a−μx,a)−min⁡a(νx,a−μx,a)≤βfor every x.\max_a(\nu_{x,a}-\mu_{x,a})-\min_a(\nu_{x,a}-\mu_{x,a})\le\beta\quad\text{for every }x.

Observe and act: in target round tt, observe XtX_t, choose AtA_t, and see only YtY_t for that action.

Goal: determine the smallest worst-case expected regret against the best target action in each cell, inf⁡πsup⁡(ν,μ)∈CβEπ∑t=1T(max⁡aμXt,a−μXt,At).\inf_\pi\sup_{(\nu,\mu)\in\mathcal C_\beta}\mathbb E_\pi\sum_{t=1}^T\left(\max_a\mu_{X_t,a}-\mu_{X_t,A_t}\right).

Answer: matching upper and lower bounds of order Tmin⁡{MK/T,β+MK/N}T\min\lbrace\sqrt{MK/T},\beta+\sqrt{MK/N}\rbrace, up to logarithms. Theorem 1 establishes the rate; Corollary 1 characterizes strict improvement over online-only learning.

The minimax model assumes N/(MK)N/(MK) independent Bernoulli source observations per cell–action pair, uniform i.i.d. contexts, and Bernoulli target rewards. The policy can use all observed source data and past chosen-action rewards. Target means and rewards of unchosen actions are unobserved.

Relative IDS uses the current gap bounds to determine how much exploration to mix with its proposed action. During initialization, source confidence intervals and β\beta determine each cell's fixed active set. The learner constructs a source-conditioned prior and initializes the target counts and accumulators Q,JQ,J to zero. Each subsequent visit to the cell follows these steps:

StepOperationWhat the next step uses
1. Bound the gapsFor each candidate action, take the tighter source/target bound against each competitor, then the maximum over competitors; compute inverse-count weightsGap upper bounds dtd_t and weights hth_t
2. Form the recommendationRefresh the IDS distribution on schedule, draw its proposal btb_t, and select the exploration action minimizing dt,a2/ht,ad_{t,a}^2/h_{t,a}A preferred action and an exploration candidate
3. Allocate only the required explorationChoose the smallest mixing probability satisfying the cumulative constraint; use zero if possibleThe distribution from which the executed action is drawn
4. Observe and updateReceive only the executed action's reward; update its statistics, the joint posterior, QQ and JJThe state for the next visit to this cell

The algorithmic contribution is an exploration allocation rule that guarantees regret control without requiring a correct posterior. For every data-dependent proposal, the rule must allow a feasible exploration choice and control the accumulated expected gap cost. On the confidence event, the action with the largest target UCB satisfies da2≤Chad_a^2\le Ch_a, so the exploration candidate minimizing this ratio satisfies the same inequality. Combining it with the previous prefix constraint and Cauchy–Schwarz shows that full exploration is feasible. The rule then selects the smallest feasible mixture, retaining the proposed action whenever the constraint allows. The proof combines this cumulative control with actual pull counts to obtain the online regret cap. A source-filtered target-UCB rule also attains the same worst-case caps. Our allocation rule retains those caps for any predictable proposal, including an IDS proposal based on a misspecified posterior.

AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your comments on MIN-UCB (3)

2. The distinction from MIN-UCB (W2–W3)

Thank you for pointing out the distinction between the bias assumption and the reward distribution. Our relative-bias assumption allows a broader range of source–target discrepancies within the common Bernoulli setting. For example, a common shift can change every reward level while preserving all action advantages. The reward-distribution assumptions differ: MIN-UCB allows 1-sub-Gaussian rewards, whereas our main theorem uses Bernoulli rewards. Appendix O.3 extends our result to bounded rewards, as summarized below:

AspectMIN-UCBThis paper
Bias informationEach action's absolute discrepancy is boundedDifferences between action biases are bounded
Inclusion within Bernoulli reward modelsAn absolute bound VV implies a relative bound 2V2VA relative bound need not imply an absolute bound that vanishes with it
Reward law in the main theorem1-sub-GaussianBernoulli
Extension established in Appendix O.3—Independent rewards in [0,1][0,1], by mean-preserving Bernoullization

The broader bias-information class is established within the common Bernoulli setting. Our extension covers independent rewards in [0,1][0,1], while MIN-UCB also covers unbounded 1-sub-Gaussian rewards. To establish the extension, transform a bounded reward YY into 1{U≤Y}\mathbf1\lbrace U\le Y\rbrace using a fresh independent uniform UU. The transformed reward has the same mean, so pseudo-regret is preserved. Applying the Bernoulli algorithm to these observations gives the upper rate. Bernoulli rewards are themselves a bounded-reward subfamily, so the lower bound also applies.

A relative-bias certificate can distinguish target environments that remain indistinguishable from historical data and an absolute-bias bound alone. Appendix O.1 constructs two target environments with the same source reward distribution and valid absolute bound, but opposite best actions. Any learner given only that information incurs Ω(T)\Omega(\sqrt T) regret in at least one environment, however large the source sample is. A valid β=0\beta=0 certificate rules out the environment with reversed action ordering. With N≍T2N\asymp T^2, source-greedy achieves O(1)O(1) worst-case regret over this smaller information class. Thus, the two types of certificate support different worst-case regret rates.

The experiment with supplied bias bounds directly compares the methods. At T=32768T=32768, we used sixteen paired seeds and supplied each method with a valid bound of the type it requires:

Source mechanismRelative IDS (ours)MIN-UCB baselineOnline IDS baseline
Shared means0.000.00192.78
Common +0.1+0.1 shift0.00257.47192.78

Lower total regret is better. Under the common shift, Relative IDS has zero regret versus 257.47 for MIN-UCB and 192.78 for Online IDS. The zero entries are exactly zero in all sixteen runs (Tables 10–11). Both source-assisted methods reach zero when means agree; preserving contrasts allows Relative IDS to retain that result after the common shift.

This advantage also holds across the broader experiment with supplied bounds: Relative IDS has lower mean regret than each of the 19 external baseline configurations at every source budget and overall (Table 2). Averaged across all 45 settings, mean regret is 59.87 versus 108.34 for the strongest external baseline, source-assisted empirical Anchor-TS (σ=0.5\sigma=0.5), a 44.7% reduction. All 19 overall paired intervals favor Relative IDS (Table 8).

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

The paper studies online contextual bandits with possibly biased offline rewards, assuming a supplied bound (with a parameter beta) on how much source and target pairwise reward differences can differ. This can permit large (supposedly) action-independent reward shifts.

The operational chain of the method, as per my understanding, is as follows:

i) Filter actions: Use offline confidence intervals and \beta to remove actions that cannot be optimal in the target environment. ii) Bound remaining gaps: For each action, compare its lower confidence limit with competitors’ upper limits, using both datasets and adding \beta to the offline differences. Keep the tighter bound for each comparison, then take the largest to bound how much worse that action could be than the best one. iii) Propose an action: Use an IDS (information directed sampling) posterior to propose an action iv) Apply the guard: Play the action proposed by IDS if a cumulative confidence constraint is satisfied; otherwise, randomize between it and an exploration action. v) Observe and update: Use the target reward to update the online statistics, posterior, and cumulative quantities.

Interestingly, when \beta is unknown, an initial target-data collection phase estimates an upper bound, with its cost included in regret.

The authors establish matching minimax rates up to logarithmic factors, characterize when offline data improve the worst-case regret order, and derive trajectory-dependent regret bounds and limitations of bias calibration. Experiments investigate transfer gains and the costs of calibration and guarding.

Critical strengths

i) Matching regret bounds for a meaningful extension of the bias model. Theorem 1 establishes upper and lower bounds under the same assumptions, quantifying how source sample size and contrast mismatch affect achievable regret. The model accommodates common reward shifts that absolute-bias guarantees, such as MIN-UCB (Cheung and Lyu, ICML 2024), can treat pessimistically. Preserving treatment effects across environments is already studied in Effect-Invariant Mechanisms for Policy Generalization (Saengkyongam et al., JMLR 2024), the contribution here is the specific sequential regret characterization under approximate preservation of action differences.

ii) Explicit accounting for the difficulty of obtaining bias information. The paper includes the online samples needed to estimate the bias bound in the learning budget. It also shows that, even when the true mismatch is zero, T online observations cannot generally certify that the mismatch is much smaller than 1/\sqrt{T}. This clarifies the difference between knowing a small bias bound in advance and having to establish one from data.

Critical weaknesses

i) Overall, the writing often seems to be overly compressed and abrupt, presenting a succession of ideas without sufficient argumentative development. It lacks the explanatory transitions, motivations and intermediate reasoning needed to guide the reader through the logical progression - and most important the operational chain of the method... (Figure 2 is very helpful to clarify that, though). The succession of so many small paragraphs is somehow strange to me. Maybe this is subjective.

ii) I am not yet convinced that the contribution is sufficiently significant relative to existing work. Preserving treatment effects across environments is already central to effect invariance (Saengkyongam et al., JMLR 2024), and learning action differences rather than rewards is studied in contextual bandits (Carranza et al., AISTATS 2023). Neither connection is discussed in the paper, leaving an important gap in its positioning. MIN-UCB also already provides regret guarantees for using biased offline data under supplied absolute-bias bounds (Cheung and Lyu, ICML 2024). The specific contribution here is a sequential regret characterization under approximate preservation of action contrasts, whose significance needs clearer justification.

iii) The usefulness of the method depends heavily on knowing a sufficiently small, valid \beta. This requires quantitative control over changes in pairwise reward gaps, which is stronger than assuming that the best action remains unchanged. To my understanding, for fixed numbers of contexts and actions, the strict asymptotic improvement requires \beta=o(T^{-1/2}). Yet the paper’s own calibration lower bound shows that, using at most T target observations, a uniformly valid estimate cannot generally certify a bound this small—even when the true mismatch is zero and unlimited offline data are available. Thus, the proposed “estimate then transfer” extension does not uniformly recover the central improvement established with a supplied bound, while also consuming part of the online budget... This is an informative limitation, but it leaves the practical contribution conditional on access to strong (and to my mind, idealistic and not realistic) external information. Finite-horizon gains remain possible; however, the paper needs stronger evidence that estimating the bound yields enough benefit to justify its cost. This is particularly disappointing as the paper only considers a tabular contextual bandit setting...

Questions for authors
  1. In what practical settings can a valid, sufficiently small \beta be supplied without costly target calibration?

  2. When does estimating \beta provide a net benefit over online-only learning after accounting for calibration costs?

  3. What is the substantive advance over effect invariance (Saengkyongam et al., 2024) and treatment-effect bandits (Carranza et al., 2023)?

10 comments
AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your question on novelty (1)

We sincerely thank you for recognizing the matching regret bounds and our explicit accounting for the cost of obtaining bias information. We also appreciate your detailed suggestions on the paper's significance, practical motivation and exposition. Below, we address these concerns and indicate the corresponding revisions, which are marked blue in the manuscript.

1. What our results add beyond prior work (W2; Q3)

Thank you for highlighting the connections to effect invariance and treatment-effect bandits. Our central question is: how much target interaction can historical rewards save when reward levels differ across environments but action contrasts remain reliable? For example, a platform change may shift every email message's response rate while preserving the advantage of one message over another. The practical question is whether historical responses justify fewer new trials, and how much change in those advantages can be tolerated.

Accurate reward prediction and reliable action selection require different information. A large common shift makes historical reward predictions inaccurate but leaves the best action unchanged. A much smaller action-dependent shift can reverse the best action. Effect invariance explains why stable treatment effects support generalization, and treatment-effect bandits use effect estimates to choose actions. We study what these ideas imply with finitely many biased source observations and a limited budget of target interactions. Specifically, we determine what information permits an improvement in the minimax regret order and what it costs to obtain that information. With an absolute-bias bound, the same historical data may be consistent with target environments having opposite action orderings. A sufficiently precise contrast certificate can distinguish between those environments.

The technical challenge is to prove matching bounds for the original reward observations and to control regret even when the algorithm's posterior is misspecified. The learner observes the reward of one chosen action at a time. Converting rewards to pairwise comparisons can give an upper bound, but the resulting comparisons may discard information. A lower bound for comparison feedback therefore need not apply to a learner that retains the original rewards. We construct two families of hard instances directly in the reward model: one captures finite-source sampling error, and the other captures uncertainty about target contrasts. For the algorithm, source and target confidence intervals bound each action's gap. Our cumulative allocation rule controls the accumulated expected gap cost for any predictable proposal, including an IDS proposal with a misspecified posterior. A source-filtered target-UCB rule also achieves the worst-case caps. Our allocation rule preserves those caps while allowing the learner to use a different predictable proposal. Combining the upper and lower bounds gives Tmin⁡{MK/T,β+MK/N}T\min\lbrace\sqrt{MK/T},\beta+\sqrt{MK/N}\rbrace up to logarithms. For fixed M,KM,K, strict order improvement occurs exactly when N/T→∞N/T\to\infty and βT→0\beta\sqrt T\to0.

The counterintuitive conclusion is that systematically biased reward levels can still permit bounded regret, whereas even unlimited history can leave a worst-case T\sqrt T learning cost when only an absolute-bias bound is supplied. The analysis also distinguishes the benefit of knowing that contrasts are stable from the cost of establishing that stability using target observations:

Information available to the learnerProven consequenceMeaning for target experimentation
A fixed absolute-bias bound and arbitrarily many source rewardsA compatible target world requires Ω(T)\Omega(\sqrt T) regretMore history alone cannot determine which target ordering is valid
A valid β=0\beta=0 certificate and N≍T2N\asymp T^2Source-greedy achieves O(1)O(1) worst-case regret over the zero-diameter classHistorical contrasts can remove the growing exploration cost even with a constant common shift
At most TT target observations to obtain the certificateUniformly valid certification cannot generally reach o(T−1/2)o(T^{-1/2})The information needed for strict order improvement has a separate acquisition cost

Appendix O.1 establishes the comparison in the first two rows. It constructs two target environments with the same source reward distribution and valid absolute bound, but opposite optimal actions. The zero-diameter certificate rules out the reversed ordering. Proposition 2 establishes the separate certification lower bound in the last row. Thus the information supplied about source–target differences determines how much historical data can reduce the regret order, even when the historical reward predictions themselves are inaccurate.

AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your question on novelty (2)

The experiment with supplied bounds illustrates the common-shift result directly. With a common +0.1+0.1 shift at T=32768T=32768, mean total regret is 0.00 for Relative IDS (ours), 257.47 for MIN-UCB and 192.78 for Online IDS (baselines) over sixteen paired seeds (Tables 10–11; lower is better). Across the broader 45-setting experiment, our overall mean is 59.87 versus 108.34 for the strongest external baseline, source-assisted empirical Anchor-TS (σ=0.5\sigma=0.5), a 44.7% reduction (Table 2). Each bias-aware method receives a valid bound of the type it requires.

Appendix O.1 compares the regret achievable when learners observe rewards and receive either absolute or relative bias certificates. The table below explains how this result and the other contributions relate to the cited work:

WorkConnectionAdditional question answered here
Saengkyongam et al., JMLR 2024Proposition 4 separates a shared treatment effect from an environment-dependent baseline; Theorem 9 gives policy generalization under its assumptionsFinite historical samples, approximate invariance, and sequential target regret, with matching lower bounds
Carranza et al., AISTATS 2023Online decisions can be based on treatment-effect estimation rather than the full reward surfaceHow biased historical observations change the necessary target budget, and what it costs to certify their usefulness
Cheung and Lyu, ICML 2024MIN-UCB combines online and source-assisted uncertainty under supplied absolute-bias boundsWhich reward discrepancies may be ignored, and the corresponding information-class separation
He et al., NeurIPS 2025, HybElimUCB-RAPairwise preference information can assist online reward decisionsMatching bounds for learners observing original rewards; Appendix O.1 also shows how a modified preference-style filter recovers the upper rate

At β=0\beta=0, our mean decomposition is the two-environment, finite-cell form of effect invariance. Our contribution is to quantify how much target interaction a finite historical sample can save when that invariance holds only approximately, with matching bounds for learners observing the original rewards.

The analysis provides tools that can be reused in contextual bandits with shared structure (W3). A contrast-based bias bound specifies which historical action comparisons remain reliable. Source–target gap bounds use this information to compare candidate actions, and cumulative allocation gives a regret guarantee for any predictable proposal. Appendix O.3 applies these tools when action correspondences are known and the relabeled reward distributions are shared: pooling then removes the factor MM from the rate. In Appendix O.6, pooled Relative IDS has zero pseudo-regret in all 128 runs, while separate Relative IDS reaches mean regret 145.60 at M=64M=64 under the same historical budget. These tools suggest how to use shared features to transfer action contrasts; the certification analysis identifies the target-data cost of verifying that such transfer is justified.

AuthorsOpenReview ↗

Thanks for the review, and here is the kind response to your question on the bias bound (3)

2. Where a useful bound can come from and how its precision affects regret (W3; Q1)

Thank you for asking how a small, valid bound can be obtained in practice. A known measurement design, an existing bias certificate, or independently collected target-reference data can supply a bound without using rounds from the decision horizon. The required information concerns the magnitude of contrast drift. Knowing that the best action remains unchanged is insufficient because it does not bound changes in the gaps between actions. The table states the conditions required for each source of information:

Source of informationValid contrast boundConditions that must be checked
An existing absolute-bias certificate VVβ=2V\beta=2VThe certificate covers every relevant action
Reporting design with means αe+λeθa\alpha_e+\lambda_e\theta_aβ≤∣λs−λt∣\beta\le \lvert\lambda_s-\lambda_t\rvertStable latent action responses, known channel slopes
The same design with latent drift bounded by ε\varepsilon in oscillationβ≤∣λs−λt∣+λtε\beta\le \lvert\lambda_s-\lambda_t\rvert+\lambda_t\varepsilonThe drift allowance covers the change in latent contrasts
Independent reference target observationsA simultaneous, count-based upper boundCoverage and population compatibility of the reference data

Appendix O.2 gives a numerical example using a single-bit RAPPOR reporting channel. Its intercept changes by 0.250.25, while equal channel slopes and stable latent responses preserve a 0.0250.025 action gap. With 10510^5 independent source reports per action, 4rs≃0.0202<0.0254r_s\simeq0.0202<0.025, so the source filter removes the inferior action on the confidence event. In this constructed example, the equal slopes and latent-response stability provide the contrast certificate. Appendix O.1 separately shows how absolute and relative certificates lead to different attainable regret rates.

Recorded data can also supply the bound before learning starts. On the Hillstrom randomized email trial, counts from 19,219 recorded customers give contrast bounds of about 0.070.07–0.160.16 per cell (Appendix H.6). With these bounds supplied before the first target round, Relative IDS has mean regret 10.75 versus 42.31 for the Online IDS baseline (74.6% lower) and 76.86 for the MIN-UCB baseline (86.0% lower) at the largest source budget (Table 16; lower is better). MIN-UCB receives a valid absolute bound from the same counts.

The theory also quantifies the cost of allowing more contrast drift. If residual modeling error enlarges the valid diameter from β0\beta_0 to β0+ε\beta_0+\varepsilon, the learner can use the enlarged bound. The core rate becomes Tmin⁡{MK/T,β0+ε+MK/N}.T\min\lbrace \sqrt{MK/T},\beta_0+\varepsilon+\sqrt{MK/N}\rbrace . The increase in this rate is at most TεT\varepsilon, and the online regret cap is preserved. Appendix O.5 proves this statement when the supplied bound includes the additional drift; validity of the enlarged bound remains a condition of the result.

We also tested sensitivity to the precision of the supplied bound. The controlled experiment uses true diameter 0.040.04, M=4M=4, K=2K=2, N=8192N=8192, T=8000T=8000, and 32 independent seeds. Every supplied bound in the table is valid. The experiment changes the precision of that bound while holding the environment fixed.

Bound supplied to Relative IDSMean total regret (lower is better)
0.04 (tight valid bound)3.86
0.0610.88
0.0820.23
0.1217.42
0.216.49
2.0 (conservative baseline)28.98

The tight valid bound reduces mean regret from 28.98 to 3.86, an 86.7% reduction relative to the conservative bound 22. All five informative bounds have lower sample mean regret than the conservative baseline. These figures compare sample means on the same 32-seed instance. Appendix O.5 provides the separate worst-case guarantee for additional contrast drift.

Comments on the paper

1 comment
AuthorsOpenReview ↗

A Kind General Response to All Reviewers and Dear AC

A Kind General Response to All Reviewers and Dear AC

We sincerely thank the reviewers for their positive assessment of our theoretical results (Matching regret bounds for a meaningful extension of the bias model [L4B8], the proposed algorithm is minimax optimal [1utb], a clear theoretical limit on how much offline data can improve online learning under the assumed structure [5PUV]). We also deeply appreciate the valuable suggestions for improvement. In the revised manuscript, with changes marked blue, we have addressed the following points:

  1. Clarification of the Problem, Algorithm and Assumptions:

    • Defining the source data, target feedback, model and minimax objective together in Section 2, and presenting the complete decision sequence in Algorithm 1 in Section 3 (L4B8–W1; 1utb–W1/Q1–Q5).
    • Explaining what each formula computes and how its result is used, with a table in each relevant reply identifying the revision for every writing concern (L4B8–W1; 1utb–W1).
    • Deriving a valid bias bound from a measurement design under the stated stability conditions, and extending the analysis to unequal source counts, nonuniform arrivals and bounded rewards in Appendices O.2–O.3 (L4B8–W3/Q1; 5PUV–W1/Q1).
  2. Clarification of Core Contributions and Technical Challenges:

    • Explaining how finite, biased historical rewards can reduce target interaction even when reward levels differ. We identify the technical challenge of proving lower bounds for the original reward observations and the conditions for a strict improvement in regret order. Section 1 and Appendix O.1 distinguish these results from effect invariance, treatment-effect bandits and MIN-UCB (L4B8–W2/Q3; 1utb–W2–W3).
    • Showing how our tools apply when contexts share structure: Appendix O.3 proves that known action correspondences and common reward distributions after relabeling allow observations to be pooled, removing the factor MM from the regret rate (5PUV–W1/Q2).
  3. Additional Experiments and Quantitative Comparisons:

    • Identifying the baseline and quantifying the improvement: with supplied bias bounds, Relative IDS has 44.7% lower overall mean regret than the strongest external baseline, source-assisted empirical Anchor-TS (σ=0.5\sigma=0.5) (Table 2, L4B8–W2/Q3; 1utb–W2–W3).
    • Evaluating paid calibration on fresh seeds and across six pilot sizes. Including every calibration round, OBD mean regret is 19.6% below Online IDS in the original validation and 19.0% below it on fresh seeds. All six sizes have a positive simultaneous net-gain interval on OBD. Sections 5–6 and Appendices O.4–O.6 explain pilot selection and distinguish the full method's benefit from the source-prior contribution, the learned-bound comparison and the guard's cost (L4B8–W3/Q2; 1utb–Q6; 5PUV–W2).
    • Testing pooling under shared structure: pooled Relative IDS has zero pseudo-regret in all 128 runs, while separate-cell mean regret reaches 145.60 at M=64M=64 under the same historical budget (Appendix O.6, 5PUV–W1/Q2).

Thank you again for the time and care invested in these reviews. We welcome further questions and would be happy to discuss any aspect of the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.