acceptodds
Under review as a conference paper at ICLR 2027

Confounded Linear Contextual Bandits

Abstract

This work studies **confounded contextual bandits**, where the reward is modeled as a linear function of the action, additively confounded by a **stochastic** term that is independent of the action. When the confounder is strong, it can dominate and attenuate the treatment effect induced by the chosen action, making reward inference from bandit feedback challenging. To address this, we draw on Neyman orthogonalization and propose a Thompson sampling based algorithm, INF-TS, which achieves regret over a horizon of , where denotes the dimension of the context-action tensor product and is the number of actions. We also prove a lower bound of for the confounded linear contextual bandit problem, showing that INF-TS attains the optimal regret rate in . Empirical results demonstrate that INF-TS outperforms existing methods designed for adversarial confounders in linear contextual bandits under both stochastic and adversarial confounder settings, particularly when the confounding signal dominates the treatment effect.

Primary area:
reinforcement learning
Keywords:
contextual linear bandit, confounded reward, confounding factor, regret minimization, causal inference

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_g2vcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies contextual bandits under confounding, where observed rewards contain an action-independent component that can obscure the true effect of the chosen action. The paper proposes INF-TS, an algorithm that combines Neyman orthogonalization with Thompson sampling to improve decision-making. The paper models rewards as rt(at)r_t(a_t)=xt⊤x_t^\top Θat\Theta a_t+ ϕ(xt)\phi(x_t) + ϵt\epsilon_t, where xtx_t is the context, ata_t is the selected action, Θ\Theta represents the unknown action effects, and ϕ(xt)\phi(x_t) is an action-independent, potentially nonlinear baseline component. The key idea is to estimate and subtract the policy-dependent conditional mean reward, while centering actions by their conditional expectations. This residualization helps cancel the confounding component and isolate the true action effects. INF-TS then uses regularized regression on the residualized data to estimate Θ\Theta, and applies Thompson sampling to balance exploration and exploitation. The theoretical analysis establishes an upper regret bound of $\widetilde O(d \sqrt{ T \log N}) $ and a lower bound of Ω(dTlog⁡N)\Omega(\sqrt{ d T \log N}), where TT is the time horizon, NN is the number of actions, and (d) is the context-action feature dimension. The paper also introduces a cold-start variant that achieves sublinear regret under weaker assumptions. The paper evaluates INF-TS in synthetic environments with varying levels and forms of confounding, as well as a semi-synthetic movie-recommendation task based on movie metadata. Results indicate that conventional Thompson sampling can deteriorate under strong confounding, while INF-TS performs particularly well in stochastic confounded settings and remains competitive in adversarial environments. Overall, the paper’s main contribution is a principled residualization approach for separating action effects from confounding baseline rewards. Its theoretical and empirical results support INF-TS.

Critical strengths

First, the paper provides a principled approach to addressing confounding in contextual bandits by combining residualization inspired by Neyman orthogonalization with Thompson sampling. This allows the algorithm to separate action effects from potentially nonlinear, action-independent baseline rewards, addressing a meaningful limitation of conventional bandit methods. This addresses a substantive challenge: when baseline reward variation overwhelms the action effect, conventional bandit algorithms may struggle to learn which actions are actually better. The proposed method is therefore motivated by a clear problem and offers a coherent solution.

Strong theoretical guarantees, including a lower bound. The paper establishes an upper regret bound of O~(dTlog⁡N)\widetilde O( d \sqrt{T \log N}) and a lower bound. The matching dependence on the time horizon, up to logarithmic factors, provides meaningful theoretical support for the algorithm's efficiency. Establishing a lower bound also helps characterize the difficulty of the underlying problem, rather than evaluating the proposed algorithm in isolation. Although a gap remains in the dimensional dependence, the theoretical results are an important strength.

Critical weaknesses

Assumptions are restrictive.The method assumes that the reward decomposes into a linear context–action treatment effect and an additive, action-independent ϕ(xt)\phi(x_t). This structure is central to the residualization strategy: centering the action can eliminate the baseline while preserving information about the treatment effect.

The empirical study is a bit simple to establish real-world usefulness. The movie-recommendation experiment uses real movie metadata to construct item embeddings, but the reward environment remains semi-synthetic rather than observed recommendation outcomes.

Questions for authors

Q1. What is the computational complexity of the algorithm when action space is large? INF-TS estimates conditional expected actions and uses Monte Carlo estimation of propensities. How do errors in these estimates affect the regret guarantees and empirical performance? In particular, how should I think of the computational and statistical trade-offs as the cardinality of the action space grows?

Q2. How sensitive is INF-TS to violations of the additive, action-independent confounding assumption? The proposed residualization relies on the reward decomposing into a linear context–action treatment effect and an action-independent baseline ϕ(xt)\phi(x_t). I wonder how the proposed methods performs under environment misspecification. Specifically, whether the method remains consistent or achieves sublinear regret when the baseline depends on the action or when the treatment-effect model is misspecified? Any discussion (e.g. theoretical counterexample or a synthetic experiment under these violations) would be helpful.

Q3. What is the fundamental source of the dimensionality gap? Specifically, the upper bound scales as $\widetilde O(d\sqrt{T\log N}) $, whereas the lower bound scales as Ω(dTlog⁡N)\Omega(\sqrt{dT\log N}). Is the extra dimensional dependence caused by the residualization step, the statistical analysis gap, or the Thompson-sampling construction?

4 comments
AuthorsOpenReview ↗

Rebuttal by authors

We thank the reviewer for the constructive questions and for highlighting the limitations of both the model and the empirical study. The updated analysis makes the assumptions behind our warm-start result explicit.

Weakness 1

Thank you for your insightful comment. We agree that the additive, action-independent structure is a substantive modeling assumption. However, we believe that this modeling assumption has real-world applications, see Example 2.2 and 2.3. In online recommendation system and advertising, the assumed additive action-independent but context-dependent confounder ϕ(xt)\phi(x_t) is often observed. Hence, our research question is closely related to realistic decision-making scenarios.

Weakness 2

Thank you for this constructive question. We agree that the movie study is semi-synthetic. It serves three purposes. First, it evaluates the practical applicability of INF-TS in online recommendation systems (cf. Example 2.2). Second, it provides a more realistic item embedding space than the synthetic setting: the embeddings are no longer guaranteed to span Rda\mathbb R^{d_a}, which challenges online causal inference through potential violations of our assumptions. Third, it acts as a stress test through substantially larger candidate sets than the synthetic experiments, with N=100N=100 and N=500N=500 movie items.

The synthetic confounders also have realistic implications. The linear confounder is intended to represent systematic variation in users' baseline engagement that is approximately linear in the observed user context. For example, some users may have a consistently higher propensity to rate, click on, or watch recommended movies, independently of the particular movie shown. The nonlinear confounder represents more complex context-dependent baseline engagement. A user may, for instance, be highly likely to engage only when several contextual conditions are simultaneously satisfied. These effects may be strongly predictive of the observed reward while remaining independent of the particular movies recommended. The adversarial confounder has a different interpretation. We do not intend it as a literal generative model of movie preferences. Rather, it is included as a robustness stress test and to facilitate comparison with prior semiparametric contextual-bandit methods designed for action-independent adversarial baselines.

Question 1

The current theorem assumes exact propensities. For each of the NN actions, exact computation requires the probability of N−1N-1 simultaneous Gaussian score-difference inequalities. The corresponding Gaussian can be degenerate and has rank at most dd, so this need not be a nonsingular (N−1)(N-1)-dimensional integral; nevertheless, computing all NN such polyhedral Gaussian probabilities is the main bottleneck as NN grows.

With maintained inverses or factorizations, the treatment-effect and nuisance ridge updates cost O(d2)O(d^2) and O(q2)O(q^2) per round, respectively. One Gaussian pseudo-posterior draw costs O(d2)O(d^2) and scoring all NN actions costs O(Nd)O(Nd). With KK Monte Carlo draws, the expected action can be estimated directly as the average of the KK selected actions, at approximate cost O(K(d2+Nd)+q2)O(K(d^2+Nd)+q^2) per round. This avoids computing all Gaussian orthant probabilities and makes the statistical--computational trade-off explicit through KK.

Suppose the KK Monte Carlo action draws are conditionally independent and identically distributed given Ft\mathcal F_t, and are independent of the draw used to take the actual action. Then the Monte Carlo average satisfies E[∥e^t−et∥22∣Ft]≤1K\mathbb E[\|\hat e_t-e_t\|_2^2\mid\mathcal F_t]\leq\frac{1}{K} under our unit-norm action assumption, so its typical error decreases as K−1/2K^{-1/2}. However, our present regret theorem does not cover this approximation. When the approximation draws are independent of the actual action draw, conditioning on e^t\hat e_t gives E[(at−e^t)⊗xt∣Ft,e^t]=(et−e^t)⊗xt,\mathbb E[(a_t-\widehat e_t)\otimes x_t\mid\mathcal F_t,\hat e_t]=(e_t-\widehat e_t)\otimes x_t, rather than being exactly centered. A finite-KK theorem would therefore need to track the accumulated centering errors, potentially with KK increasing over time.

Question 2

The guarantee is robust to poor estimation of an action-independent nuisance, but not to arbitrary violations of action independence or of the linear treatment-effect model. Under the stated additive model, for any predictable μ^t\hat\mu_t, E[zt{rt−μ^t(xt)−zt⊤θ}∣Ft]=0.\mathbb E[z_t\{r_t-\hat\mu_t(x_t)-z_t^\top\theta\}\mid\mathcal F_t]=0. Therefore misspecifying the nuisance feature map does not introduce first-order bias into the treatment-effect moment: it removes the sharper prediction-error guarantee, but clipping still yields the conservative cold-start result.

AuthorsOpenReview ↗

Rebuttal continued

Question 2 continued

By contrast, an omitted action-dependent term ht(x,a)h_t(x,a) contributes E[ztht(xt,at)∣Ft],\mathbb E[z_t h_t(x_t,a_t)\mid\mathcal F_t], which need not vanish and can bias both treatment-effect estimation and subsequent action selection. The same problem can arise if x⊤Θax^\top\Theta a is a misspecified model of the action-dependent reward, hence unrestricted action dependence makes Θ\Theta non-identifiable. A fixed nonzero approximation error can, in the worst case, accumulate linearly in regret, so a general sublinear-regret guarantee would require additional structure.

Question 3

Thank you for your insightful comment. We note this d\sqrt{d} gap also exists in the classic linear contextual bandit (Agrawal et al., 2013). It may reflect looseness in the confidence and anti-concentration analysis, a limitation of this Thompson-sampling construction,. More precisely, under the conditions of our lower-bound theorem--in particular, N=2mN=2^m, 1≤m≤da1\leq m\leq d_a, and T≥σ2d2/8T\geq\sigma^2d^2/8--the leading TS term matches the lower bound's dependence on TT and NN when the additive MT0MT_0 term is lower order; minimax optimality in dd remains open.

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127–135. PMLR, 2013.

Thanks the authors for the detailed rebuttal and response to my questions. The explanation regarding the restrictive assumptions and the clarification of the practicality of the math assumptions relieved my original concern. Also, the reply to the questions are appreciated, though there seems no further numerical results to demonstrate the sensitivity of the method against the confounding assumption. Overall, I am still supportive of the submission and maintain my positive rating of 3. I have no further questions for the paper.

Thank you so much for your positive feedback and continuous support!

Reviewer_qxGUOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies linear contextual bandits where the reward contains an additive, action-independent term ϕ(x)\phi(x) that depends on the user context and can be much larger than the treatment effect. The proposed INF-TS borrows Robinson-style partialling out. It centers the chosen action by its exact Thompson sampling propensity, subtracts an online regression estimate of the policy-induced mean reward, and runs TS on the resulting ridge estimate. The authors prove a regret bound of the same order as linear TS, with and without a warm start, and a lower bound that matches in TT and NN. Experiments on synthetic environments and a semi-synthetic movie recommendation setup show gains over TS and BOSE that grow with the strength of the baseline term.

Critical strengths
  • The core idea is sound and well motivated. A user-level baseline that swamps the item effect is a real issue in recommendation and advertising. Splitting the reward into a treatment part and an action-independent baseline, then using the known TS propensities so that the orthogonalized moment is unbiased for any predictable baseline estimate, is a clean and correct way to handle it. I went through the centered-feature version of the Thompson sampling analysis, and the pieces fit together.
  • The empirical results are consistent across settings. The experiments vary the type and strength of the baseline term and the size of the action set. The gains under strong confounding hold in both the synthetic and semi-synthetic studies. The cold-start comparison and the exact versus Monte Carlo propensity check are useful additions.
  • The paper is clearly written. The motivating examples make the reward model concrete, and Algorithm 1 is easy to follow.
Critical weaknesses
  1. The method is close to existing TS work on semiparametric rewards. Kim and Paik ("Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Model”, ICML 2019) study the same model with an action-independent and possibly history-dependent baseline. They center the chosen feature by its expectation under the TS selection probabilities, need no base action, and obtain regret of the same order as linear TS. INF-TS looks like this approach plus reward residualization by μ^\hat{\mu}. There is also a followup work by the authors on doubly robust TS (Kim, Kim and Paik, NeurIPS 2021). It would help to state exactly what is new relative to these papers and to include Kim and Paik as a baseline.
  2. The regret bound does not reflect the benefit of residualization. The constant c1c_1 has a term proportional to M, which comes from bounding the nuisance error of μ^\hat{\mu}. So the bound does not depend on how well μ^\hat{\mu} fits. When μ^=0\hat{\mu}=0, the same argument gives the smaller bound M, which means that the theorem slightly favors plain action centering over INF-TS. The guarantee also grows linearly with the baseline magnitude, which is the same limitation Section 2.1 attributes to BOSE. I also could not find where the proof uses the stochastic, time-invariant nature of φ. It seems to need only a predictable, bounded nuisance error, which would also cover history-dependent baselines.
  3. Theorem 3.2 states T0T_0 of order dlog⁡Td \log T. However, Lemma C.3 needs T0T_0 to scale with the inverse square of γ\gamma, and Assumption 3.1 forces γ\gamma to be at most 1/d1/d, since the trace of Γt\Gamma_t is at most one. So T0T_0 grows at least quadratically in dd and also with MM. In the paper's own setting this exceeds the horizon.
  4. The lower bound seems to not capture the cost of confounding. The proof of Theorem 3.4 sets ϕ\phi to zero. So the result is a lower bound for the unconfounded bilinear bandit and does not measure any cost of the baseline term. The statement should also list the conditions the construction uses: the number of actions is a power of two, N=2mN = 2^m with mm at most dad_a, and log is base 2. A lower bound that depends on the baseline magnitude, or a result showing it does not matter, would make this part more informative.
  5. The framing and several claims need adjustment. In the problem setting the authors are dealing with, ϕ\phi depends only on the observed context, and the learner knows its own randomization. So this is an omitted main effect rather than confounding in the causal sense. Bareinboim et al. 2015 (which is cited as a reference) studies unobserved confounders. The abstract says INF-TS outperforms Greenewald et al. 2017, but that method is not run. These statements should be aligned with what is actually shown.
Questions for authors

See Weaknesses.

5 comments
AuthorsOpenReview ↗

Rebuttal by authors

We thank the reviewer for the careful and technically detailed feedback. We have substantially revised the manuscript in response.

Weakness 1

We thank the reviewer for highlighting this important work. We have expanded the Related Work section to discuss Kim and Paik (2019) and explicitly compare the theoretical guarantees as well as empirical performance.

Kim and Paik (2019) assumes a bounded and action-independent baseline but may otherwise depend arbitrarily on the filtration. Our baseline ϕ(xt)\phi(x_t) is therefore a structured special case, which is potentially learnable. This distinction motivates the different estimators. Kim and Paik (2019) use raw rewards and a hybrid empirical/conditional covariance estimator: θ^tKP=Bt−1∑s<t2zsrs\hat\theta_t^{KP}=B_t^{-1}\sum_{s<t}2z_sr_s with Bt=I+V^t+VˉtB_t=I+\hat V_t+\bar V_t. In contrast, INF-TS additionally residualizes rewards using an online estimate of the policy-induced conditional mean, exploiting the structure of stochastic context-dependent confounders. Hence it uses θ^t=Vt−1∑s<tzs(rs−μ^s(xs))\hat \theta_t=V_t^{-1}\sum_{s<t}z_s(r_s-\hat\mu_s(x_s)), and exploits the additional structure of our stochastic contextual model.

When the baseline is strong but predictable from the context, subtracting μ^s(xs)\hat\mu_s(x_s) removes much of this action-independent variation before estimating the treatment effect. Kim and Paik’s published estimator does not exploit this predictability, and can be substantially less statistically efficient when the contextual baseline dominates the treatment-effect signal, as observed in our experiments.

The differences in estimators also lead to different proof strategies. Recall our notation ξs=μs(xs)−μ^s(xs)\xi_s=\mu_s(x_s)-\hat\mu_s(x_s). INF-TS estimator satisfies Vt(θ^t−θ)=−λθ+∑s<tzsεs+∑s<tzsξs.V_t(\hat\theta_t-\theta)=-\lambda\theta+\sum_{s<t}z_s\varepsilon_s+\sum_{s<t}z_s\xi_s. For Kim and Paik, Bt(θ^tKP−θ)=−θ+2∑s<tzsεs+2∑s<tzsμs(xs)+∑s<t(zszsT−Es[zszsT])θB_t(\hat\theta_t^{KP}-\theta)=-\theta+2\sum_{s<t}z_s\varepsilon_s+2\sum_{s<t}z_s\mu_s(x_s)+\sum_{s<t}(z_sz_s^T-\mathbb E_s[z_sz_s^T])\theta. Their hybrid estimator therefore introduces an additional covariance-fluctuation term, which is controlled through a separate vector-martingale argument. This term is absent from the INF-TS decomposition. Conversely, because INF-TS does not include V‾t\overline V_t in its design matrix, our proof must translate a self-normalized bound involving V^t+V‾t\widehat V_t+\overline V_t into the empirical VtV_t-norm through an empirical-versus-conditional covariance comparison. Therefore, the appearance of V^t+V‾t\widehat V_t+\overline V_t in our concentration argument is as an auxiliary self-normalizer; unlike in Kim and Paik, it is not the matrix used by the algorithm.

Accordingly, our claimed contribution relative to Kim and Paik is the residual-on-residual estimator tailored to a learnable stochastic, context-dependent baseline, together with its analysis under an empirical-only design matrix and the finite-NN regret and lower-bound results.

Kim and Paik (2019) establish a high-probability regret bound of O~(d3/2T)\widetilde O(d^{3/2}\sqrt{T}) under potentially history-dependent bounded confounders, whereas our expected regret bound is O~(dTlog⁡N)\widetilde O(d\sqrt{T\log N}) under stochastic context-dependent confounding.

We have also implemented Kim and Paik (2019) as an additional benchmark in both our synthetic and semi-synthetic movie recommendation experiments (updated Figures 1 and 4). The results show that INF-TS achieves substantially lower cumulative regret. Specifically, in the synthetic experiments, INF-TS reduces cumulative regret by 77.7% and 62.6% relative to Kim and Paik (2019) under strong linear and nonlinear confounding, respectively.

Weakness 2

We thank the reviewer; this criticism of the previous theorem is valid. Replacing every nuisance error ξt:=μt(xt)−μ^t(xt)\xi_t:=\mu_t(x_t)-\widehat\mu_t(x_t) by the worst-case clipping bound 2M2M established robustness but did not establish a benefit from accurate residualization. The previous upper bound theorem stems from the fact that we impose no estimation error rate assumption on μ^t\hat\mu_t. We have revised the theorem so that the prediction error is retained throughout the concentration and regret arguments.

Let ρT0:=max⁡T0<t≤T∣μt(xt)−μ^t(xt)∣.\rho_{T_0}:=\max_{T_0<t\leq T}|\mu_t(x_t)-\widehat\mu_t(x_t)|. On the event supplied by the new warm-start Lemma 3.2, ρT0≤min⁡2M,rμ(T0,δ)\rho_{T_0}\leq\min\\{2M,r_\mu(T_0,\delta)\\}. The nuisance term in the revised confidence radius is therefore 3min⁡2M,rμ(T0,δ)2log⁡(4/δ)+dlog⁡(1+5(T−T0)d),\sqrt{3}\min\\{2M,r_\mu(T_0,\delta)\\}\sqrt{2\log(4/\delta)+d\log(1+\frac{5(T-T_0)}{d})}, and the corresponding regret contribution is O~(min⁡2M,rμ(T0,δ)d(T−T0)log⁡N)\tilde O(\min\\{2M,r_\mu(T_0,\delta)\\}d\sqrt{(T-T_0)\log N})

This dependence follows directly from the nuisance martingale. With action centering alone, rt=ztTθ+μt(xt)+εt,r_t=z_t^T\theta+\mu_t(x_t)+\varepsilon_t, so its conditional covariance contribution is μt(xt)2Et[ztzt⊤]\mu_t(x_t)^2\mathbb E_t[z_t z_t^\top]. After residualization, rt−μ^t(xt)=zt⊤θ+ξt+εt,r_t-\widehat\mu_t(x_t)=z_t^\top\theta+\xi_t+\varepsilon_t, and this contribution becomes ξt2Et[ztzt⊤]\xi_t^2\mathbb E_t[z_t z_t^\top].

AuthorsOpenReview ↗

Rebuttal continued

Weakness 2 continued

Thus there is a direct continuum. With no residualization, μ^t=0\hat\mu_t=0, action centering alone remains sufficient for sublinear regret, as in the case of Kim & Paik (2019). With an accurate learned estimate, the scale is rμ(T0,δ)r_\mu(T_0,\delta); when this is below the baseline scale it gives a strictly smaller certified nuisance contribution. The oracle choice μ^t=μt\widehat\mu_t=\mu_t removes that contribution entirely. Residualization is therefore not necessary for sublinear regret; its value is to replace dependence on the magnitude of a potentially dominant predictable baseline by dependence on its prediction error. The revised theorem makes this improvement explicit.

Weakness 3

We thank the reviewer for the careful proof reading of our work. We acknowledge that our previous analysis on T0T_0 hides an additional dd factor due to the fact that γ=Θ(1/d)\gamma=\Theta(1/d). We also acknowledge that the previous Assumption 3.1 does not explain the advantages of the warm-start period. The reviewer's insightful comment inspired that the advantage of T0T_0 should be positioned as an exploration period that warm start the nuisance parameter μt\mu_t estimation error. Hence, the revised warm-start assumption instead concerns learnability of the nuisance regression. In INF-TS and its empirical implementation, the nuisance parameters μt\mu_t's are fitted by ridge regression. We define wt=(xt,et)w_t=(x_t,e_t) and m⋆(x,e)=ϕ(x)+xTΘem_\star(x,e)=\phi(x)+x^T\Theta e so that μt(xt)=m⋆(wt)\mu_t(x_t)=m_\star(w_t), and assume a correctly specified qq-dimensional model m⋆(w)=ψ(w)Tβ⋆m_\star(w)=\psi(w)^T\beta_\star. Assuming Σμ,0:=E[ψ(xt,etunif)ψ(xt,etunif)T]⪰κμI\Sigma_{\mu,0}:=\mathbb{E}[\psi(x_t,e_t^{unif})\psi(x_t,e_t^{unif})^T]\succeq\kappa_\mu I for some κμ>0\kappa_\mu>0, the new warm-start Lemma 3.2 proves that, if T0≥8L02log⁡(2q/δ)T_0\geq8L_0^2\log(2q/\delta) with L0=sup⁡w∥Σμ,0−1/2ψ(w)∥2L_0=\sup_w\|\Sigma_{\mu,0}^{-1/2}\psi(w)\|_2, then, with probability at least 1−δ1-\delta, max⁡T0<t≤T∣μ^t(xt)−μt(xt)∣≤rμ(T0,δ):=Cμqlog⁡(eT)+log⁡(1/δ)T0.\max_{T_0<t\leq T}|\widehat\mu_t(x_t)-\mu_t(x_t)|\leq r_\mu(T_0,\delta):=C_\mu\sqrt{\frac{q\log(eT)+\log(1/\delta)}{T_0}}. The revised stochastic-environment assumption explicitly makes (xt,At)(x_t,\mathcal A_t) i.i.d.; hence the warm nuisance inputs (xt,etunif)(x_t,e_t^{\mathrm{unif}}) are i.i.d., and the nuisance-design coverage follows from matrix Chernoff concentration. Subsequent adaptive observations are handled by a self-normalized ridge-regression bound. Under L02=O(q)L_0^2=O(q), a sufficient warm-start T0T_0 length is O~(q)\widetilde O(q).

This revision also clarifies the distinction between the warm-start theorem and the cold-start corollary. The cold-start result requires no nuisance-learning assumption but uses the worst-case clipping bound ∣μt−μ^t∣≤2M|\mu_t-\widehat\mu_t|\leq2M, giving O~((1+σ+2M)dTlog⁡N).\tilde O((1+\sigma+2M)d\sqrt{T\log N}). The revised warm-start theorem retains the prediction error and gives O~((1+σ+min⁡{2M,rμ(T0,δ)})d(T−T0)log⁡N+MT0).\tilde O((1+\sigma+\min\{2M,r_\mu(T_0,\delta)\})d\sqrt{(T-T_0)\log N}+MT_0). Thus the warm start trades the additive exploration cost MT0MT_0 against a nuisance-dependent contribution. Its benefit appears when the contextual baseline is learnable and its prediction error is sufficiently smaller than the baseline scale.

Weakness 4

Thank you for pointing this out. Although the proof was presented using ϕ≡0\phi\equiv0, this restriction is unnecessary. Fix any admissible action-independent baseline ϕ\phi, possibly nonzero, and use the same ϕ\phi across all hard instances ΘU\Theta^U. The baseline cancels from the instantaneous regret. Moreover, for two neighboring instances UU and U′U', the conditional reward means differ by (xtTΘUat+ϕ(xt))−(xtTΘU′at+ϕ(xt))=xtT(ΘU−ΘU′)at.(x_t^T\Theta^U a_t+\phi(x_t))-(x_t^T\Theta^{U'}a_t+\phi(x_t))=x_t^T(\Theta^U-\Theta^{U'})a_t. Thus, the KL/Hellinger divergences used in the two-point testing argument are identical to those in the ϕ=0\phi=0 case, and the resulting Ω(σdTlog⁡N)\Omega(\sigma\sqrt{dT\log N}) lower bound holds for every fixed admissible ϕ\phi.

We have revised the theorem and proof to make this extension explicit and state the construction’s conditions N=2mN=2^m, 1≤m≤da1\le m\le d_a, with base-two logarithms. This result also shows that the standard bilinear-bandit with reward structure xtTΘatx_t^T\Theta a_t difficulty persists under nonzero confounding.

Weakness 5

We thank the reviewer for identifying these framing and empirical overstatements. Although the context-dependent ϕ\phi is not an unobserved confounder of the current randomized action, it enters the adaptive learning loop through observed rewards. Hence, reward signals can distort treatment-effect updates and thereby alter subsequent action randomization, exploration, and regret. Following established semiparametric contextual-bandit terminology (Krishnamurthy et al., 2018), we retain the term ``confounded'' for rewards containing an unknown action-independent baseline outside the parametric treatment-effect model. We now state this convention explicitly and refer to ϕ\phi as a context-dependent baseline or nuisance component throughout the technical discussion.

AuthorsOpenReview ↗

Rebuttal continued

Weakness 5 continued

Greenewald et al. study an important but structurally different problem structure: a distinguished zero or ``do nothing'' action must be available at every round and have zero treatment effect. This structure is natural in the mobile-health applications motivating their work, but it is absent from our movie-recommendation catalogs, which contain no designated reference action with identically zero treatment effect. Hence Greenewald et al. does not apply to our problem directly. We retain Greenewald et al. in the Related Work discussion, but have removed the unsupported empirical implication and now restrict our empirical claims to the methods actually evaluated.

Reviewer_xK81OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper studies a linear contextual bandit, where the reward is confounded by a stochastic term depending on the context -- not on the chosen action -- added to the treatment effect, which is defined to be a bilinear term of both the context and chosen action.

  • The authors address such confoundedness by extending a well-known Neyman orthogonalization to the online learning setting, so that the estimation of the parameter of interest is robust to errors from estimation of nuisance functions.

  • This work proposes an algorithm, INF-TS, which combines the Thompson sampling with residual-on-residual regression, where (i) the reward residual, obtained by subtracting the estimate μ^t(xt)\hat\mu_t(x_t) from the reward rt(at)r_t(a_t), is regressed on (ii) the action residual, obtained by subtracting the expected action vector ete_t from the action vector ata_t, through the feature (at−et)⊗xt(a_t - e_t) \otimes x_t.

    • ete_t is computed from the sampling distribution of TS.
  • INF-TS has regret O~(dTlog⁡N)\tilde O(d\sqrt{T\log N}) with d=dxdad = d_x d_a. The authors also prove a lower bound of Ω(dTlog⁡N)\Omega(\sqrt{dT\log N}).

  • In numerical experiments on a synthetic and a semi-synthetic dataset, the authors report that INF-TS outperforms the baselines when the confounding is strong.

Critical strengths
  • The confounded reward model is motivated by recommendation and advertising examples (example 2.2 and 2.3), where a user-level baseline (corresponding to the confounding term ϕ(xt)\phi(x_t)) can dominate the treatment effect of the item shown (corresponding to the bilinear term xt⊤Θatx_t^\top \Theta a_t).

  • The algorithm is TS combined with a residual-on-residual estimator, and with a generic regression oracle for μ^t\hat\mu_t, so it is conceptually simple.

  • In addition to the upper bound, the paper gives a lower bound, which shows that the dependence on TT is tight up to log factors.

  • The experiments cover several confounder types, a range of confounding strengths and action-set sizes (up to N=500N = 500).

Critical weaknesses
  1. The theoretical contribution relative to existing semiparametric bandit results is unclear and there is a missing related work.

    • Although the authors disclose the distinction of this work to existing semiparametric bandit problems, the work of Kim & Paik (2019) is not discussed in the related work, and the paper compares with it neither in regret bounds nor in experiments.
    • Specifically, Kim & Paik (2019) consider the model where the expected reward of arm aa is νt+⟨θ,bt(a)⟩\nu_t + \langle \theta, b_t(a) \rangle, where νt\nu_t corresponds to the action-independent confounding term ϕ(xt)\phi(x_t) in this problem, and the feature vector bt(a)b_t(a) corrsponds to a⊗xta \otimes x_t.
    • For that model, Kim & Paik (2019) propose a TS algorithm that centers the features using the exact action-selection probabilities, and achieve a regret bound of the same order as LinTS (Agrawal & Goyal, 2013).
    • From my perspective, the analysis in this work also seems similar to that taken in Kim & Paik (2019), especially in using centered features and the self-normalized bound, normalized by the sum of the empirical and conditional covariance matrices (V^t+Vˉt\hat V_t + \bar V_t in Lemma C.1 of this paper).
  2. I could not identify the role of the warm-start period and Assumption 3.1, and some related statements are inconsistent.

    • Corollary 3.3 (Line 327-328) gives the same asymptotic regret rate under weaker assumptions, without a warm-start period or its additive regret penalty. It is therefore unclear what additional theoretical benefit Theorem 3.2 provides.
    • Moreover, Theorem 3.2 sets T0=O(dlog⁡T)T_0 = O(d\log T), which seems to be inconsistent with condition (8) used in its proof.
      • Eq. (8) needs λmin⁡(VT0)≥c12\lambda_{\min}(V_{T_0}) \ge c_1^2. Since ∥zt∥2≤2\Vert z_t\Vert_2 \le 2, it always holds that λmin⁡(VT0)≤λ+tr(∑t≤T0ztzt⊤)/d≤λ+4T0/d\lambda_{\min}(V_{T_0}) \le \lambda + \mathrm{tr}(\sum_{t \le T_0} z_t z_t^\top)/d \le \lambda + 4T_0/d. Hence T0≥d(c12−λ)/4T_0 \ge d(c_1^2 - \lambda)/4, where, with c1c_1 as defined in Theorem 3.2, c12−λ≥σ2dlog⁡(λ+T/d)+2M2dlog⁡(1+5T/d)c_1^2 - \lambda \ge \sigma^2 d\log(\lambda + T/d) + 2M^2 d\log(1 + 5T/d). This already gives T0=Ω(d2(σ2+M2)log⁡T)T_0 = \Omega(d^2(\sigma^2+M^2)\log T).
      • The sufficient condition in Lemma C.3 is even larger. Lemma C.3 requires T0≥8log⁡(d/δ)/γ2+(2B+(16/3)log⁡(d/δ))/γT_0 \ge 8\log(d/\delta)/\gamma^2 + (2B + (16/3)\log(d/\delta))/\gamma with B≥c12−λB \ge c_1^2 - \lambda, and Assumption 3.1 forces γ≤1/d\gamma \le 1/d: by Assumption 2.4, tr(Γt)=E[∥Aˉt−etunif∥22∥xt∥22]≤E[∥Aˉt−etunif∥22]≤E[∥Aˉt∥22]≤1\mathrm{tr}(\Gamma_t) = \mathbb E[\Vert \bar A_t - e^{\mathrm{unif}}_t \Vert_2^2 \Vert x_t\Vert_2^2] \le \mathbb E[\Vert \bar A_t - e^{\mathrm{unif}}_t\Vert_2^2] \le \mathbb E[\Vert \bar A_t\Vert_2^2] \le 1, while Γt⪰γId\Gamma_t \succeq \gamma I_d gives tr(Γt)≥dγ\mathrm{tr}(\Gamma_t) \ge d\gamma. With δ=1/T\delta = 1/T as in the proof of Theorem 3.2, this gives T0=Ω(d2(1+σ2+M2)log⁡(dT))T_0 = \Omega(d^2(1+\sigma^2+M^2)\log(dT)).
      • The additive term (T0+2)M(T_0+2)M is then Ω(d2M(σ2+M2)log⁡T)\Omega(d^2 M(\sigma^2+M^2)\log T), not O(dMlog⁡T)O(dM\log T).
    • The proof of Lemma C.3 uses ∥Yt∥op≤1\Vert Y_t\Vert_{\mathrm{op}} \le 1 (Line 1213), but ∥Zt∥2≤2\Vert Z_t\Vert_2\le 2 only gives ∥Yt∥op≤4\Vert Y_t\Vert_{\mathrm{op}} \le 4.
      • Furthermore, the proof of Lemma C.3 treats Z1,…,ZT0Z_1, \ldots, Z_{T_0} as independent (Line 1211). This requires (xt,At)(x_t, \mathcal A_t) to be independent across rounds, which Assumption 2.1 does not state.
  3. Some parts of the presentation are not clear to follow.

    • The paper relies on DML concepts such as Neyman orthogonality and cross-fitting, mostly without defining them. For example, Section 3.1 says that DML "imposes no estimation rate requirements on the estimation of μ\mu" (Line 204), but does not say what these requirements are or why known propensities remove them.
    • Section 3.1 only shows that the orthogonalized reward is unbiased with the true μt\mu_t, while the estimator in (3) uses μ^t\hat\mu_t. The main text does not explain why the orthogonal estimating moment remains conditionally unbiased after μ^t\hat\mu_t is substituted for the true μt\mu_t, although this seems to be the main point of the orthogonalization. The term μt−μ^t\mu_t - \hat\mu_t is treated only in the proof of Lemma C.1.
    • The regression algorithm R\mathcal R used for μ^t\hat\mu_t in the experiments is not specified.

References

  • Kim & Paik (2019), Contextual multi-armed bandit algorithm for semiparametric reward model, ICML.
Questions for authors
  1. Since the model in this work seems to be a special case of that in Kim & Paik (2019), I find it hard to assess the novelty without a comparison. Could the authors discuss the difference between the two works and add their algorithm as a baseline in the experiments?

  2. Could the authors clarify what subtracting μ^t\hat\mu_t contributes to the regret guarantee?

    • The main claim of the paper is that subtracting μ^t(xt)\hat\mu_t(x_t) removes the confounding component, which makes INF-TS effective when the confounder dominates (Section 3.1; Figure 2).
    • In Lemma C.1, however, the error ξs=μs(xs)−μ^s(xs)\xi_s = \mu_s(x_s) - \hat\mu_s(x_s) is only required to be Fs\mathcal F_s-measurable with ∣ξs∣≤2M|\xi_s| \le 2M, and after Lemma C.2 is applied, ξs2\xi_s^2 is replaced by 4M24M^2.
    • If I read the proof correctly, the same bound then holds with μ^≡0\hat\mu \equiv 0, i.e., without subtracting anything.
  3. The term xt⊤Θatx_t^\top\Theta a_t in the reward is bilinear in the context and action features, so the problem is close to bilinear bandits (Jun et al., 2019).

    • Jun et al. (2019) show that when the d1×d2d_1 \times d_2 parameter matrix has rank r≪min⁡{d1,d2}r \ll \min\{d_1, d_2\}, the regret improves from O~(d1d2T)\tilde O(d_1 d_2\sqrt{T}) for a direct linear reduction to O~((d1+d2)3/2rT)\tilde O((d_1+d_2)^{3/2}\sqrt{rT}). If Θ\Theta has rank r≪min⁡{dx,da}r \ll \min\{d_x, d_a\}, can INF-TS (or a variant) exploit this to get a bound that scales with dx+dad_x + d_a instead of dxdad_x d_a?

References

  • Jun, K.-S., Willett, R., Wright, S., and Nowak, R. (2019), Bilinear bandits with low-rank structure, ICML.
6 comments
AuthorsOpenReview ↗

Rebuttal by authors

We thank the reviewer for the careful and technically detailed feedback. We have substantially revised the manuscript in response.

Weakness 1

We thank the reviewer for highlighting this important work. We have expanded the Related Work section to discuss Kim and Paik (2019) and explicitly compare the theoretical guarantees as well as empirical performance.

Kim and Paik (2019) assumes a bounded and action-independent baseline but may otherwise depend arbitrarily on the filtration. Our baseline ϕ(xt)\phi(x_t) is therefore a structured special case, which is potentially learnable. This distinction motivates the different estimators. Kim and Paik (2019) use raw rewards and a hybrid empirical/conditional covariance estimator: θ^tKP=Bt−1∑s<t2zsrs\hat\theta_t^{KP}=B_t^{-1}\sum_{s<t}2z_sr_s with Bt=I+V^t+VˉtB_t=I+\hat V_t+\bar V_t. In contrast, INF-TS additionally residualizes rewards using an online estimate of the policy-induced conditional mean, exploiting the structure of stochastic context-dependent confounders. Hence it uses θ^t=Vt−1∑s<tzs(rs−μ^s(xs))\hat \theta_t=V_t^{-1}\sum_{s<t}z_s(r_s-\hat\mu_s(x_s)), and exploits the additional structure of our stochastic contextual model.

When the baseline is strong but predictable from the context, subtracting μ^s(xs)\hat\mu_s(x_s) removes much of this action-independent variation before estimating the treatment effect. Kim and Paik’s published estimator does not exploit this predictability, and can be substantially less statistically efficient when the contextual baseline dominates the treatment-effect signal, as observed in our experiments.

The differences in estimators also lead to different proof strategies. Recall our notation ξs=μs(xs)−μ^s(xs)\xi_s=\mu_s(x_s)-\hat\mu_s(x_s). INF-TS estimator satisfies Vt(θ^t−θ)=−λθ+∑s<tzsεs+∑s<tzsξs.V_t(\hat\theta_t-\theta)=-\lambda\theta+\sum_{s<t}z_s\varepsilon_s+\sum_{s<t}z_s\xi_s. For Kim and Paik, Bt(θ^tKP−θ)=−θ+2∑s<tzsεs+2∑s<tzsμs(xs)+∑s<t(zszsT−Es[zszsT])θB_t(\hat\theta_t^{KP}-\theta)=-\theta+2\sum_{s<t}z_s\varepsilon_s+2\sum_{s<t}z_s\mu_s(x_s)+\sum_{s<t}(z_sz_s^T-\mathbb E_s[z_sz_s^T])\theta. Their hybrid estimator therefore introduces an additional covariance-fluctuation term, which is controlled through a separate vector-martingale argument. This term is absent from the INF-TS decomposition. Conversely, because INF-TS does not include V‾t\overline V_t in its design matrix, our proof must translate a self-normalized bound involving V^t+V‾t\widehat V_t+\overline V_t into the empirical VtV_t-norm through an empirical-versus-conditional covariance comparison. Therefore, the appearance of V^t+V‾t\widehat V_t+\overline V_t in our concentration argument is as an auxiliary self-normalizer; unlike in Kim and Paik, it is not the matrix used by the algorithm.

Accordingly, our claimed contribution relative to Kim and Paik is the residual-on-residual estimator tailored to a learnable stochastic, context-dependent baseline, together with its analysis under an empirical-only design matrix and the finite-NN regret and lower-bound results.

Kim and Paik (2019) establish a high-probability regret bound of O~(d3/2T)\widetilde O(d^{3/2}\sqrt{T}) under potentially history-dependent bounded confounders, whereas our expected regret bound is O~(dTlog⁡N)\widetilde O(d\sqrt{T\log N}) under stochastic context-dependent confounding.

We have also implemented Kim and Paik (2019) as an additional benchmark in both our synthetic and semi-synthetic movie recommendation experiments (updated Figures 1 and 4). The results show that INF-TS achieves substantially lower cumulative regret. Specifically, in the synthetic experiments, INF-TS reduces cumulative regret by 77.7% and 62.6% relative to Kim and Paik (2019) under strong linear and nonlinear confounding, respectively.

Weakness 2

We thank the reviewer for the careful proof reading of our work. We acknowledge that our previous analysis on T0T_0 hides an additional dd factor due to the fact that γ=Θ(1/d)\gamma=\Theta(1/d). We also acknowledge that the previous Assumption 3.1 does not explain the advantages of the warm-start period. The reviewer's insightful comment inspired that the advantage of T0T_0 should be positioned as an exploration period that warm start the nuisance parameter μt\mu_t estimation error. Hence, the revised warm-start assumption instead concerns learnability of the nuisance regression. In INF-TS and its empirical implementation, the nuisance parameters μt\mu_t's are fitted by ridge regression. We define wt=(xt,et)w_t=(x_t,e_t) and m⋆(x,e)=ϕ(x)+xTΘem_\star(x,e)=\phi(x)+x^T\Theta e so that μt(xt)=m⋆(wt)\mu_t(x_t)=m_\star(w_t), and assume a correctly specified qq-dimensional model m⋆(w)=ψ(w)Tβ⋆m_\star(w)=\psi(w)^T\beta_\star. Assuming Σμ,0:=E[ψ(xt,etunif)ψ(xt,etunif)T]⪰κμI\Sigma_{\mu,0}:=\mathbb{E}[\psi(x_t,e_t^{unif})\psi(x_t,e_t^{unif})^T]\succeq\kappa_\mu I for some κμ>0\kappa_\mu>0, the new warm-start Lemma 3.2 proves that, if T0≥8L02log⁡(2q/δ)T_0\geq8L_0^2\log(2q/\delta) with L0=sup⁡w∥Σμ,0−1/2ψ(w)∥2L_0=\sup_w\|\Sigma_{\mu,0}^{-1/2}\psi(w)\|_2, then, with probability at least 1−δ1-\delta, max⁡T0<t≤T∣μ^t(xt)−μt(xt)∣≤rμ(T0,δ):=Cμqlog⁡(eT)+log⁡(1/δ)T0.\max_{T_0<t\leq T}|\widehat\mu_t(x_t)-\mu_t(x_t)|\leq r_\mu(T_0,\delta):=C_\mu\sqrt{\frac{q\log(eT)+\log(1/\delta)}{T_0}}.

AuthorsOpenReview ↗

Rebuttal continued

Weakness 2 continued

The revised stochastic-environment assumption explicitly makes (xt,At)(x_t,\mathcal A_t) i.i.d.; hence the warm nuisance inputs (xt,etunif)(x_t,e_t^{\mathrm{unif}}) are i.i.d., and the nuisance-design coverage follows from matrix Chernoff concentration. Subsequent adaptive observations are handled by a self-normalized ridge-regression bound. Under L02=O(q)L_0^2=O(q), a sufficient warm-start T0T_0 length is O~(q)\widetilde O(q).

This revision also clarifies the distinction between the warm-start theorem and the cold-start corollary. The cold-start result requires no nuisance-learning assumption but uses the worst-case clipping bound ∣μt−μ^t∣≤2M|\mu_t-\widehat\mu_t|\leq2M, giving O~((1+σ+2M)dTlog⁡N).\tilde O((1+\sigma+2M)d\sqrt{T\log N}). The revised warm-start theorem retains the prediction error and gives O~((1+σ+min⁡2M,rμ(T0,δ))d(T−T0)log⁡N+MT0).\tilde O((1+\sigma+\min\\{2M,r_\mu(T_0,\delta)\\})d\sqrt{(T-T_0)\log N}+MT_0). Thus the warm start trades the additive exploration cost MT0MT_0 against a nuisance-dependent contribution. Its benefit appears when the contextual baseline is learnable and its prediction error is sufficiently smaller than the baseline scale.

Weakness 3

We thank the reviewer for pointing out these presentation gaps. The relevant statement is not that the residualized reward itself remains unbiased after replacing μt\mu_t by an arbitrary estimate. Rather, the treatment-effect estimating moment remains conditionally centered.

Let ξt:=μt(xt)−μ^t(xt)\xi_t:=\mu_t(x_t)-\widehat\mu_t(x_t). Because μ^t\widehat\mu_t is fitted using observations strictly before tt and evaluated before the current action draw, ξt\xi_t is measurable with respect to the pre-draw information Ft\mathcal F_t. Since zt=(at−et)⊗xtz_t=(a_t-e_t)\otimes x_t and E[zt∣Ft]=0\mathbb E[z_t\mid\mathcal F_t]=0, \begin{align*} \mathbb E[z_t(r_t-\widehat\mu_t(x_t)-z_t^T\theta)\mid\mathcal F_t]=\mathbb E[z_t(\xi_t+\varepsilon_t)\mid\mathcal F_t]=\xi_t\mathbb E[z_t\mid\mathcal F_t]+\mathbb E[z_t\varepsilon_t\mid\mathcal F_t]=0. \end{align*} Equivalently, the derivative of this conditional moment with respect to a perturbation of the nuisance regression is zero because the action residual is conditionally centered. Past-only fitting is the online analogue of sample splitting: it prevents the current reward from entering μ^t\widehat\mu_t and makes the preceding conditional argument valid.

We have also clarified what we mean by no nuisance-rate requirement. No convergence rate for μ^t\hat\mu_t is needed for conditional centering or for the conservative sublinear-regret guarantee based on clipping. Nuisance accuracy nevertheless controls the conditional variance, confidence radius, and resulting regret; the revised Theorem 3.2 quantifies this dependence through rμ(T0,δ)r_\mu(T_0,\delta). Thus a rate is needed to obtain an improvement over the conservative guarantee, although not to retain its validity.

Finally, the revised algorithm now specifies R\mathcal R as past-only ridge regression for m⋆(w)=ψ(w)⊤β⋆m_\star(w)=\psi(w)^\top\beta_\star, which is the exact regressor used in experiments.

Question 1

We thank the reviewer for this important observation. Please refer to our response to Weakness 1.

Question 2

We thank the reviewer; the reviewer's reading of the previous proof is correct. Once the old analysis replaced every ξt2\xi_t^2 by 4M24M^2, it established robustness to nuisance misspecification but did not quantify any advantage from accurate residualization. We have revised the theorem so that the prediction error is retained throughout the concentration and regret arguments.

Let ρT0:=max⁡T0<t≤T∣μt(xt)−μ^t(xt)∣.\rho_{T_0}:=\max_{T_0<t\leq T}|\mu_t(x_t)-\widehat\mu_t(x_t)|. On the event supplied by the new warm-start lemma, ρT0≤min⁡2M,rμ(T0,δ)\rho_{T_0}\leq\min\\{2M,r_\mu(T_0,\delta)\\}. The nuisance term in the revised confidence radius is therefore 3min⁡2M,rμ(T0,δ)2log⁡(4/δ)+dlog⁡(1+5(T−T0)d),\sqrt{3}\min\\{2M,r_\mu(T_0,\delta)\\}\sqrt{2\log(4/\delta)+d\log(1+\frac{5(T-T_0)}{d})}, and the corresponding regret contribution is O~(min⁡2M,rμ(T0,δ)d(T−T0)log⁡N)\tilde O(\min\\{2M,r_\mu(T_0,\delta)\\}d\sqrt{(T-T_0)\log N})

This dependence follows directly from the nuisance martingale. With action centering alone, rt=ztTθ+μt(xt)+εt,r_t=z_t^T\theta+\mu_t(x_t)+\varepsilon_t, so its conditional covariance contribution is μt(xt)2Et[ztzt⊤]\mu_t(x_t)^2\mathbb E_t[z_t z_t^\top]. After residualization, rt−μ^t(xt)=zt⊤θ+ξt+εt,r_t-\widehat\mu_t(x_t)=z_t^\top\theta+\xi_t+\varepsilon_t, and this contribution becomes ξt2Et[ztzt⊤]\xi_t^2\mathbb E_t[z_t z_t^\top].

With no residualization, μ^t=0\hat\mu_t=0, action centering alone remains sufficient for sublinear regret, as in the case of Kim & Paik (2019). With an accurate learned estimate, the scale is rμ(T0,δ)r_\mu(T_0,\delta); when this is below the baseline scale it gives a strictly smaller certified nuisance contribution. The oracle choice μ^t=μt\widehat\mu_t=\mu_t removes that contribution entirely. Residualization is therefore not necessary for sublinear regret; its value is to replace dependence on the magnitude of a potentially dominant predictable baseline by dependence on its prediction error. The revised theorem makes this improvement explicit.

AuthorsOpenReview ↗

Rebuttal continued

Question 3

We thank the reviewer; low rank is indeed a promising structural extension. Jun et al.’s stated ESTR guarantee does not apply directly here: their formal algorithm controls both members of a fixed product arm set and uses designed exploration over selected left–right pairs, whereas our context xtx_t is revealed by the environment and the feasible action set may vary with tt.

Establishing a Jun-type rate would require additional restricted assumptions for the exogenous contexts and time-varying action sets, together with new martingale confidence analysis for the nuisance-residual term. We will identify low-rank INF-TS as an important direction for future work.

Comments on the paper

1 comment

We have addressed the reviewers’ principal shared concern—clarifying INF-TS’s novelty and the provable benefit of residualization relative to prior semiparametric bandits—by adding an explicit comparison with Kim and Paik (2019) [1], deriving a revised regret guarantee that retains the nuisance-prediction error, and conducting new experiments in which INF-TS achieves 77.7% and 62.6% lower cumulative regret than the Kim–Paik algorithm under strong linear and nonlinear confounding, respectively.

Only Reviewer xK81 raised a subsequent concern, asking whether the coverage condition in Assumption 3.1 makes the improved warm-start guarantee narrower than the motivating setting suggests. We responded to this concern in detail, although the reviewer has not posted a further reply. First, the condition holds in our semi-synthetic study’s real movie catalog of 4,803 movies, whose centered covariance satisfies λmin⁡=0.0164>0\lambda_{\min}=0.0164>0. Moreover, under nonlinear confounding, even a misspecified linear nuisance model has a uniform approximation error of only ≈1.025\approx1.025, compared with a synthetic-confounder magnitude of ∥ϕ∥∞≈5.366\|\phi\|_\infty\approx5.366. The coverage condition extends directly to the general dynamic-candidate recommendation setting that motivates our work. Contemporary recommendation systems construct candidate sets from large embedded catalogs. Whenever the centroids of these candidate sets vary in every relevant action-feature direction, Cov⁡(eunif)≻0\operatorname{Cov}(e^{\mathrm{unif}})\succ0; together with coverage of the context distribution induced by a sufficiently diverse user population, this yields the required joint-feature coverage. The large-scale candidate-generation pipelines deployed at YouTube, ByteDance, and Target provide concrete examples of this broader application setting [2–4]. This coverage condition is also analogous to standard covariate-diversity conditions in stochastic contextual bandits [5,6].

Finally, Assumption 3.1 is only one sufficient route to the sharper uniform warm-start rate: Theorem 3.3 accommodates any valid nuisance-prediction guarantee, while Corollary 3.4 retains sublinear regret without nuisance learnability or this coverage condition.

[1] Kim, Gi-Soo, and Myunghee Cho Paik. “Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Model.” Proceedings of the 36th International Conference on Machine Learning, 2019.

[2] Covington, Paul, Jay Adams, and Emre Sargin. “Deep Neural Networks for YouTube Recommendations.” Proceedings of the 10th ACM Conference on Recommender Systems, 2016.

[3] Gao, Weihao, et al. “Deep Retrieval: Learning a Retrievable Structure for Large-Scale Recommendations.” arXiv preprint arXiv:2007.07203, 2020.

[4] Pande, Amit, Kai Ni, and Venkataramani Kini. “SWAG: Item Recommendations Using Convolutions on Weighted Graphs.” 2019 IEEE International Conference on Big Data, 2019.

[5] Bastani, Hamsa, Mohsen Bayati, and Khashayar Khosravi. “Mostly Exploration-Free Algorithms for Contextual Bandits.” Management Science 67.3 (2021): 1329–1349.

[6] Li, Lihong, Yu Lu, and Dengyong Zhou. “Provably Optimal Algorithms for Generalized Linear Contextual Bandits.” International Conference on Machine Learning, 2017.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.