# An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

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

- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge](https://mlsanity.com/paper/2111.01602/) (2021)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)
- [Efficient Kernel UCB for Contextual Bandits](https://mlsanity.com/paper/2202.05638/) (2022)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Choosing Answers in varepsilon-Best-Answer Identification for Linear Bandits](https://mlsanity.com/paper/2206.04456/) (2022)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Mixing Makes Markovian Contexts Cheap for Linear Bandits](https://mlsanity.com/paper/2603.12530/) (2026)
- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)

## Abstract (arXiv)

In the contextual linear bandit setting, algorithms built on the optimism principle fail to exploit the structure of the problem and have been shown to be asymptotically suboptimal. In this paper, we follow recent approaches of deriving asymptotically optimal algorithms from problem-dependent regret lower bounds and we introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We build on a reformulation of the lower bound, where context distribution and exploration policy are decoupled, and we obtain an algorithm robust to unbalanced context distributions. Then, using an incremental primal-dual approach to solve the Lagrangian relaxation of the lower bound, we obtain a scalable and computationally efficient algorithm. Finally, we remove forced exploration and build on confidence intervals of the optimization problem to encourage a minimum level of exploration that is better adapted to the problem structure. We demonstrate the asymptotic optimality of our algorithm, while providing both problem-dependent and worst-case finite-time regret guarantees. Our bounds scale with the logarithm of the number of arms, thus avoiding the linear dependence common in all related prior works. Notably, we establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits. Finally, we verify that our algorithm obtains better empirical performance than state-of-the-art baselines.