- 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 = + + , where is the context, is the selected action, represents the unknown action effects, and 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 , 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 , where is the time horizon, 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 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 . 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 . 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 . Is the extra dimensional dependence caused by the residualization step, the statistical analysis gap, or the Thompson-sampling construction?
4 comments
Rebuttal continued
Question 2 continued
By contrast, an omitted action-dependent term contributes which need not vanish and can bias both treatment-effect estimation and subsequent action selection. The same problem can arise if is a misspecified model of the action-dependent reward, hence unrestricted action dependence makes 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 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, , , and --the leading TS term matches the lower bound's dependence on and when the additive term is lower order; minimax optimality in 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!
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) 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, 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=100 and N=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 N actions, exact computation requires the probability of N−1 simultaneous Gaussian score-difference inequalities. The corresponding Gaussian can be degenerate and has rank at most d, so this need not be a nonsingular (N−1)-dimensional integral; nevertheless, computing all N such polyhedral Gaussian probabilities is the main bottleneck as N grows.
With maintained inverses or factorizations, the treatment-effect and nuisance ridge updates cost O(d2) and O(q2) per round, respectively. One Gaussian pseudo-posterior draw costs O(d2) and scoring all N actions costs O(Nd). With K Monte Carlo draws, the expected action can be estimated directly as the average of the K selected actions, at approximate cost O(K(d2+Nd)+q2) per round. This avoids computing all Gaussian orthant probabilities and makes the statistical--computational trade-off explicit through K.
Suppose the K Monte Carlo action draws are conditionally independent and identically distributed given Ft, and are independent of the draw used to take the actual action. Then the Monte Carlo average satisfies E[∥e^t−et∥22∣Ft]≤K1 under our unit-norm action assumption, so its typical error decreases as K−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 gives E[(at−et)⊗xt∣Ft,e^t]=(et−et)⊗xt, rather than being exactly centered. A finite-K theorem would therefore need to track the accumulated centering errors, potentially with K 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, E[zt{rt−μ^t(xt)−zt⊤θ}∣Ft]=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.