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

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.

Explore similar work

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

    Sep 23, 2026Prakhar Singhvi, Yi Zou, Abhishek BhattacharjeeThompson SamplingMulti-Armed Bandits

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

    May 15, 2026Arnab Maiti, Yunbei Xu, Kevin JamiesonMulti-Armed BanditsBest-Arm Identification

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

    Mar 10, 2026Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2Multi-Armed BanditsAlgorithmic Stability