This is the pre-proceedings for the RLC 2026. You may expect minor changes.

ContrastSpanner: Learning Low-Rank Causal Contrasts to Alleviate Power-Set and Eluder Barriers

By Alec Koppel, and Laixi Shi

Reinforcement Learning Journal, vol. 7, 2026, pp. TBD.

Will be presented at the Reinforcement Learning Conference (RLC), Montréal, Quebec, Canada, August 15–17, 2026.

Download:

Keywords: causal contextual bandits, combinatorial interventions, optimal design, spanners,

Abstract:

Causal contextual bandits can expose a *combinatorial intervention set* (e.g., any subset of $m$ nodes in a causal graph $|\mathcal{A}|\approx 2^m$). Two obstacles then dominate theory and practice: a *power-set barrier* (quadratic comparisons over $|\mathcal{A}|$) and, under general function approximation, an *Eluder-dimension barrier* whose scaling is hard to certify and can be exponential. We study a realizable setting where the interventional mean $\mu(x,a)=\mathbb{E}[r\mid x,\text{do}(a)]$ belongs to a rich oracle class, and where *interventional contrasts* exhibit an unknown low-rank geometry. We propose **ContrastSpanner**, which constructs a spanner/$\varepsilon$-net in the *causal contrast space* to *learn* an effective rank $r$ online and to replace explicit $|\mathcal{A}|$ and opaque Eluder dependence by an explicit rank/design complexity in regret. We instantiate the framework with (i) a square-loss regression oracle and (ii) a log-loss oracle (akin to FastCB (Foster & Krishnamurthy, 2021)). We establish sublinear stochastic and minimax regret of the proposed approach holds with high probability under both oracle models, which notably mitigates the aforementioned combinatorial and Eluder scalings. We conduct experiments for a variety of confounder models, with benchmarks against both contextual and causal bandit techniques, in which we observ effective and scalable performance in practice.

Citation Information:

Alec Koppel and Laixi Shi. "ContrastSpanner: Learning Low-Rank Causal Contrasts to Alleviate Power-Set and Eluder Barriers." Reinforcement Learning Journal, vol. 7, 2026, pp. TBD.

BibTeX:
@article{koppel2026contrastspanner,
    title={ContrastSpanner: Learning Low-Rank Causal Contrasts to Alleviate Power-Set and Eluder Barriers},
    author={Alec Koppel and Laixi Shi},
    journal={Reinforcement Learning Journal},
    volume={7},
    pages={},
    year={2026}
}