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(d^3\sqrt{\log (K)T}\mathrm{polylog}(T/\delta ))$ 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(d^3\sqrt{\log (K)T}\mathrm{polylog}(T/\delta )+d^{5/2}V\mathrm{polylog}(T/\delta ))$, 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(C_{\text{mix}}{d}^3\sqrt{\log (K)T}\mathrm{polylog}(T/\delta ))$, where $C_{\text{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.