Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers
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.
Related
- Spectral Universality for Matrices with Non-Linear Correlated Entries
- Adaptive multi-resolution Gaussian processes: Scalable exact inference with naturally data-sparse covariance matrices
- AdaPS-LiNGAM: Adaptive Predecessor Selection for Linear Non-Gaussian Acyclic Models under Small-Sample Settings
- Quantitative universality for products of i.i.d. random matrices
- Quantitative eigenvector universality for generalized Wigner matrices
BibTeX
@misc{manikantan2026adaptive,
title = {{Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers}},
author = {Sudarshan Manikantan and Abhishek Bhattacharjee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30321},
eprint = {2609.30321},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30321},
}
RIS
TY - UNPB
TI - Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers
AU - Sudarshan Manikantan
AU - Abhishek Bhattacharjee
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.30321
UR - https://arxiv.org/abs/2609.30321
AB - 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.
ER -