Probabilistic Guarantees for Adversarial Linear Contextual Bandits

We study the adversarial linear contextual bandit problem, in which an oblivious adversary fixes a sequence of loss vectors while the per-round context (action set) is generated stochastically. In the standard setting where contexts are drawn i.i.d. from a fixed distribution, near-optimal regret bounds are known, but only in expectation. We prove the first such bound that holds with high probability, resolving an open problem stated by Neu and Olkhovskaya [2020], Olkhovskaya et al. [2023] and Dai et al. [2024]. Specifically, the regret is at most $O\big( d^3\sqrt{\log(K)T}\mathrm{polylog}(T/\delta) \big)$ with probability at least $1-\delta$ over $T$ rounds, where $K$ is the number of actions and $d$ is the dimension of the actions. We then ask whether high-probability guarantees can be extended beyond i.i.d. contexts. Although fully adversarial contexts make sublinear regret impossible in this setting, we show that two natural relaxations remain tractable: (i) non-stationary but independent contexts, whose per-round distributions do not deviate too much from a fixed reference distribution, for which we obtain a high-probability regret bound of $O\big(d^3 \sqrt{\log(K)T}\mathrm{polylog}(T/\delta) + d^{5/2}V\mathrm{polylog}(T/\delta)\big)$, where $V$ is the cumulative total variation distance of the per-round distributions from the reference; and (ii) stationary but dependent exponentially mixing contexts, like, for instance, uniformly ergodic Markov chains, for which we obtain a high-probability bound of $O\big(C_\textrm{mix} d^3 \sqrt{\log(K)T}\mathrm{polylog}(T/\delta) \big)$, where $C_\textrm{mix}$ is a constant that depends on the mixing time. Technically, our results build on the recent reduction from adversarial linear contextual bandits to misspecified linear bandits by Van Erven et al. [2025]. All three results are obtained from a single base algorithm under different hyperparameter choices, some of which are functions of data-dependent quantities that are unknown in advance. We resolve this by automatically tuning the hyperparameters using the Corral algorithm of Agarwal et al. [2017]. For this purpose, we develop a new high-probability variant of Corral, since the original version only has guarantees in expectation.