stat.MLSep 23, 2026

Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers

Authors: Sudarshan Manikantan, Abhishek Bhattacharjee

Organizations: Abstract Math Institute

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Adaptive arm selection changes the distribution of the observations collected by a bandit algorithm, but it need not change their limiting empirical spectrum. We study Gaussian bandit designs in which the dimension and the number of observations grow proportionally. A quantitative coupling theorem compares the design generated by any causal selection rule with an independent Gaussian design. If the logarithm of the number of available arms is sublinear in the dimension, the empirical spectral distribution converges to the Marchenko-Pastur law, uniformly over the selection rule. Consequently, Gaussian Bayesian bandits have policy-independent first-order limits for posterior mean-square uncertainty, squared posterior covariance, and information acquisition. For linear-score selection, we obtain the exact conditional arm distribution and show that two-arm selection produces an exactly Wishart Gram matrix in every dimension, despite its nonzero conditional mean. For a fixed selection direction, we identify an explicit eigenvalue and eigenvector transition governed by the second moment of a Gaussian maximum. A counterexample shows that a direction's overlap with a reference signal does not determine this transition. Finally, an exponentially large arm pool permits a different bulk limit, establishing the order-sharpness of the arm-growth condition. These results distinguish global spectral stability from directional effects in adaptive bandit data.

More in this topic

Gaussian Process Bandits

See all 15 papers

Explore similar work

CardsList
Sep 23, 2026

Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits

We study Bayesian linear bandits with an isotropic Gaussian parameter, independent Gaussian candidate arms, and Gaussian reward noise when the horizon is proportional to the dimension. The normalized posterior uncertainty has an explicit limit that is uniform over all causal policies. Gaussian posterior identities then determine the limiting parameter overlaps without an assumed closure of the adaptive recursion. These results yield exact regret curves for Thompson sampling, posterior-mean greedy selection, and a family of policies that scale the posterior sampling covariance. The normalized realized cumulative regret converges in L1, uniformly on compact proportional-time intervals. A policy-uniform lower bound identifies the limiting optimal Bayes regret and proves that posterior-mean greedy selection attains it. Thompson sampling incurs a strictly larger leading regret; its instantaneous regret ratio relative to greedy selection lies between one and two and approaches two at long proportional horizons. Closed-form cumulative curves also identify a different comparison in the vanishing-noise limit. Finally, the instantaneous regret converges to a nondegenerate Gaussian decision-loss distribution, rather than to its mean. The analysis separates the amount of information acquired by a bandit policy from the quality of the decisions made using that information.

Prakhar Singhvi, Yi Zou, Abhishek Bhattacharjee

Abstract Math Institute

Thompson SamplingMulti-Armed BanditsBayesian Decision Theory
AskPDF
May 15, 2026

On the Power of Adaptivity for ε\varepsilon-Best Arm Identification in Linear Bandits

We study the minimax sample complexity of ε\varepsilon-best arm identification in linear bandits. Given a compact action set X\mathcal{X} that spans Rd\mathbb{R}^d and an unknown reward vector θ∈Rdθ\in\mathbb{R}^d, the goal is to output an arm x^∈X\widehat{x}\in\mathcal{X} such that ⟨x^,θ⟩≥max⁡x∈X⟨x,θ⟩−ε\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon with probability at least 1−δ1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right), where w(X)w(\mathcal{X}) is a Gaussian width term dependent on X\mathcal{X}, and we prove a matching lower bound Ω ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right) for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ2\ell_2 ball, mm-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set X\mathcal{X} for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ2\ell_2-norm estimation subroutine: we design an adaptive algorithm that uses O ⁣(dlog⁡(1/δ)ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right) samples from the unit ℓ2\ell_2 ball in Rd\mathbb{R}^d and outputs an estimate r^\widehat r satisfying ∣r^−∥θ∥2∣≤ε|\widehat r-\|θ\|_2|\le \varepsilon with probability at least 1−δ1-δ, where θθ is the unknown reward vector.

Arnab Maiti, Yunbei Xu, Kevin Jamieson

University of Washington · National University of Singapore

Multi-Armed BanditsBest-Arm IdentificationAdaptive Sampling
AskPDF
Mar 10, 2026

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability~\citep{laiwei82} as a sufficient condition for valid inference under adaptivity. This paper first provides a refined stability condition, stated in terms of the iterates of an online algorithm, and shows that a large class of regularized stochastic-mirror-descent-style algorithms satisfy it. This refined condition allows us to strengthen the asymptotic results of~\citet{laiwei82} in several ways. First, we derive a non-asymptotic Berry--Esseen bound for the empirical reward estimates under adaptive sampling. Second, we derive matching non-asymptotic upper and lower bounds on the regret of the proposed algorithm, yielding a precise characterization of its regret. Third, we show that these regularized algorithms preserve asymptotic normality and valid inference under a prescribed level of adversarial corruption. Finally, we show that regularization is necessary rather than incidental: Lai--Wei stability is incompatible with the optimal O(T)O(\sqrt{T}) regret rate -- the rate attained by unregularized algorithms such as EXP3 -- so that a controlled, polylogarithmic inflation in regret is the price of valid inference.

Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2

Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata

Multi-Armed BanditsAlgorithmic StabilityAdaptive SamplingStochastic Optimization
AskPDF