# First- and Second-Order Bounds for Adversarial Linear Contextual Bandits

arXiv: https://arxiv.org/abs/2305.00832 · HTML: https://mlsanity.com/paper/2305.00832/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 1 May 2023.

## Builds on (most cited first, 11 of 11)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits](https://mlsanity.com/paper/1802.03386/) (2018)
- [Efficient Sampling from Time-Varying Log-Concave Distributions](https://mlsanity.com/paper/1309.5977/) (2013)

## Built on by (most cited first, 19 of 19)

- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning](https://mlsanity.com/paper/2403.05385/) (2024)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction](https://mlsanity.com/paper/2508.11931/) (2025)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [Eluder dimension: localise it!](https://mlsanity.com/paper/2601.09825/) (2026)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity](https://mlsanity.com/paper/2412.14744/) (2024)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)
- [Mixing Makes Markovian Contexts Cheap for Linear Bandits](https://mlsanity.com/paper/2603.12530/) (2026)
- [Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2609.09907/) (2026)

## Abstract (arXiv)

We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of K arms to change over time without restriction. Assuming the d-dimensional contexts are drawn from a fixed known distribution, the worst-case expected regret over the course of T rounds is known to scale as tilde O(√Kd T). Under the additional assumption that the density of the contexts is log-concave, we obtain a second-order bound of order tilde O(K√d VT) in terms of the cumulative second moment of the learner's losses VT, and a closely related first-order bound of order tilde O(K√d LT^*) in terms of the cumulative loss of the best policy LT^*. Since VT or LT^* may be significantly smaller than T, these improve over the worst-case regret whenever the environment is relatively benign. Our results are obtained using a truncated version of the continuous exponential weights algorithm over the probability simplex, which we analyse by exploiting a novel connection to the linear bandit setting without contexts.