# Truncated LinUCB for Stochastic Linear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 65 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests](https://mlsanity.com/paper/2003.00359/) (2020)
- [Nonparametric Stochastic Contextual Bandits](https://mlsanity.com/paper/1801.01750/) (2018)
- [Stochastic Linear Contextual Bandits with Diverse Contexts](https://mlsanity.com/paper/2003.02681/) (2020)
- [Recent progress in log-concave density estimation](https://mlsanity.com/paper/1709.03154/) (2017)
- [Learning for Dose Allocation in Adaptive Clinical Trials with Safety Constraints](https://mlsanity.com/paper/2006.05026/) (2020)

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

- [Bellman-sufficient Information Complexity](https://mlsanity.com/paper/2606.11171/) (2026)

## Abstract (arXiv)

This paper considers contextual bandits with a finite number of arms, where the contexts are independent and identically distributed d-dimensional random vectors, and the expected rewards are linear in both the arm parameters and contexts. The LinUCB algorithm, which is near minimax optimal for related linear bandits, is shown to have a cumulative regret that is suboptimal in both the dimension d and time horizon T, due to its over-exploration. A truncated version of LinUCB is proposed and termed "Tr-LinUCB", which follows LinUCB up to a truncation time S and performs pure exploitation afterwards. The Tr-LinUCB algorithm is shown to achieve O(dlog(T)) regret if S = Cdlog(T) for a sufficiently large constant C, and a matching lower bound is established, which shows the rate optimality of Tr-LinUCB in both d and T under a low dimensional regime. Further, if S = dlogkappa(T) for some kappa>1, the loss compared to the optimal is a multiplicative loglog(T) factor, which does not depend on d. This insensitivity to overshooting in choosing the truncation time of Tr-LinUCB is of practical importance.