# Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 19 Nov 2024.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Action Centered Contextual Bandits](https://mlsanity.com/paper/1711.03596/) (2017)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [A Triangle Inequality for Cosine Similarity](https://mlsanity.com/paper/2107.04071/) (2021)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Linear bandits with polylogarithmic minimax regret](https://mlsanity.com/paper/2402.12042/) (2024)
- [On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix](https://mlsanity.com/paper/2011.09288/) (2020)
- [Learning to Route Efficiently with End-to-End Feedback: The Value of Networked Structure](https://mlsanity.com/paper/1810.10637/) (2018)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [On the Minimax Regret for Linear Bandits in a wide variety of Action Spaces](https://mlsanity.com/paper/2301.03597/) (2023)

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

- [A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets](https://mlsanity.com/paper/2609.32149/) (2026)

## Abstract (arXiv)

We propose and analyze TRAiL (Tangential Randomization in Linear Bandits), a computationally efficient regret-optimal forced exploration algorithm for linear bandits on action sets that are sublevel sets of strongly convex functions. TRAiL estimates the governing parameter of the linear bandit problem through a standard regularized least squares and perturbs the reward-maximizing action corresponding to said point estimate along the tangent plane of the convex compact action set before projecting back to it. Exploiting concentration results for matrix martingales, we prove that TRAiL ensures a Omega(√T) growth in the inference quality, measured via the minimum eigenvalue of the design (regressor) matrix with high-probability over a T-length period. We build on this result to obtain an O(√T log(T)) upper bound on cumulative regret with probability at least  1 - 1/T over T periods, and compare TRAiL to other popular algorithms for linear bandits. Then, we characterize an Omega(√T) minimax lower bound for any algorithm on the expected regret that covers a wide variety of action/parameter sets and noise processes. Our analysis not only expands the realm of lower-bounds in linear bandits significantly, but as a byproduct, yields a trade-off between regret and inference quality. Specifically, we prove that any algorithm with an O(Tα) expected regret growth must have an Omega(T1-α) asymptotic growth in expected inference quality. Our experiments on the Lp unit ball as action sets reveal how this relation can be violated, but only in the short-run, before returning to respect the bound asymptotically. In effect, regret-minimizing algorithms must have just the right rate of inference -- too fast or too slow inference will incur sub-optimal regret growth.