arXiv preprint ·
Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Sampling Line-Graph Colorings with Constant Extra Colors
Boolean threshold functions, neuron capacity, and memory retrieval
Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
On the SoS Certifiability of Log-Concave Distributions
Robustness of Diffusion Models under Distribution Shift
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.