# Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 12 references that are in the map.
- First posted on arXiv 14 Sep 2026.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)

## Abstract (arXiv)

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let d be the dimension, K be the menu size, and T the time horizon. For 2≤ K≤ d, we prove an upper bound widetilde O(K1/4√dT). When T≥ d2, we further prove a lower bound Omega(K1/4√dT). Thus, for T≥ d2 and 2≤ K≤ d, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on K is optimal. Compared with the previous widetilde O(√dKT) bound, our upper bound improves the dependence on K by a factor of K1/4. For K≥ d, we prove an upper bound widetilde Od,Tleft(√dTmin√ d,(dlog K)1/4right) and a lower bound Omegaleft(√dTminleft√ d,left(fracdlog Klog(2d)right)1/4rightright). Here, widetilde Od,T omits logarithmic factors only in d and T. In particular, for polynomially large K≥ d, the upper and lower bounds both scale as d3/4√ T up to logarithmic factors, improving the standard widetilde O(d√ T) rate by a factor of d1/4. As K grows further, the regret smoothly recovers the d√ T scale once log K reaches order d.