PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sudarshan Manikantan, Abhishek Bhattacharjee

arXiv:2609.30321v1stat.MLcs.LGmath.PRmath.STstat.TH

TL;DR

Adaptive selection makes bandit observations dependent on prior decisions, leaving the proportional-dimensional spectrum difficult to characterize. The paper couples adaptive Gaussian designs to independent ones and establishes policy-uniform bulk and Bayesian limits alongside directional selection effects. It also identifies settings where outliers or a changed bulk persist.

  • Problem

    In proportional-dimensional bandits, adaptive selection makes collected design columns dependent and non-Gaussian, complicating spectral analysis.

    Source: §1 · pp. 1–2

  • Method

    A quantitative coupling compares designs from causal selectors with independent Gaussian designs, alongside exact analysis of linear-score selection and fixed-direction effects.

    Source: §1 · p. 2

  • Results

    For subexponential arm pools, the bulk spectrum is policy-independent, while fixed directions can produce outliers and two-arm linear-score selection yields an exactly Wishart Gram matrix.

    Source: §8 · p. 9

  • Takeaways & Limitations

    Global spectral stability does not rule out directional deformation, and equal first-order learning quantities do not imply equal action quality.

    Source: §8 · p. 9

    The bulk comparison metric does not control a single extreme eigenvalue at order one.

    Source: §5.1 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

Adaptive selection makes the collected design dependent on past decisions, complicating spectral analysis in the proportional regime. The paper separates policy-invariant bulk behavior from selection-induced directional effects and develops consequences for Bayesian uncertainty and information.

1 Introduction

  • In the proportional regime, replacing an independent Gaussian Gram matrix by its expectation loses first-order spectral information, while adaptive columns are generally dependent and non-Gaussian.A nontrivial empirical spectral distribution remains when observations and dimension are comparable.Source: §1 · pp. 1–2
  • For subexponential candidate pools, selection leaves the leading empirical spectrum unchanged for every causal policy, even though directional deformations can persist.The paper distinguishes the distribution of all eigenvalues from a small number of distinguished eigenvalues and directions.Source: §1 · p. 2
  • A quantitative coupling compares any adaptively selected design with an independent Gaussian matrix without requiring policy convergence or independent selected columns.The argument combines conditional-distribution domination by pool size with Gaussian transportation and sums the resulting costs across the experiment.Source: §1 · p. 2
  • For Gaussian Bayesian bandits, posterior uncertainty limits apply under Thompson sampling, greedy selection, and every other admissible policy.Policies can collect the same first-order information while using it differently to choose arms.Source: §1 · p. 2
  • Linear-score selection admits an exact decomposition into a Gaussian maximum and an independent orthogonal Gaussian component, with distinct raw-second-moment and centered-covariance coefficients.The two-arm outer-product distribution agrees exactly with its Gaussian counterpart, while a fixed direction can produce an explicit outlier transition.Source: §1 · p. 2

2 Existing work

Prior work supplies independent-design spectral tools, Gaussian transportation inequalities, and analyses of bandit algorithms and spiked matrices. This paper uses these foundations to address the proportional-dimensional spectrum of designs selected from fresh Gaussian candidate pools.

Sample covariance limits and regularized estimation

  • Marchenko–Pastur and resolvent theory describe the independent Gaussian reference design, but do not directly cover columns selected using previous rewards.Dobriban and Wager (2018) derive proportional ridge prediction and classification limits; the present paper establishes uniform validity of the reference law for adaptive selectors.Source: §2 · p. 2

Transportation and matrix comparison

  • The policy-uniform spectral comparison combines Gaussian transportation with Gram-matrix norm inequalities; neither tool alone gives the adaptive conclusion.The resulting comparison requires a bound on the logarithm of candidate-pool size.Source: §2 · pp. 2–3

Spiked random matrices

  • The fixed-direction result parallels spiked covariance transitions, with a spike parameter determined by a Gaussian maximum rather than a centered Gaussian row.Baik et al. (2005), Baik and Silverstein (2006), and Paul (2007) provide related transition and eigenvector analyses; this paper asserts no spectral-edge fluctuation theorem.Source: §2 · p. 3

Bandit algorithms and adaptive covariance geometry

  • Unlike LinUCB analyses on a learner-controlled unit ball, this paper studies fresh independent Gaussian candidates, whose pool-size restriction enables distributional domination.Fan et al. (2025) analyze eigenvalues and eigenvectors generated by LinUCB on the Euclidean unit ball.Source: §2 · p. 3

Exploration from random contexts and matrix-valued bandits

  • The spectral statement applies to every causal policy, including policies not selected for low regret, and does not replace regret analyses.The paper studies the proportional-dimensional spectrum of collected designs rather than cumulative reward guarantees.Source: §2 · p. 3

3 Our contributions

The contributions establish policy-uniform bulk and Bayesian limits while identifying exact and asymptotic directional effects. They also delimit extrapolations from overlap curves and from subexponential candidate pools.

Our contributions

  • The results quantitatively separate global spectrum, posterior information, and directional concentration in Gaussian bandit data.The comparison theorem bounds quadratic coupling cost by 2n log K/d without requiring a prescribed direction, exploration schedule, stability condition, or limiting allocation law.Source: §3 · pp. 3–4
  • When n/d has a finite positive limit and log K = o(d), the empirical spectral distribution converges to Marchenko–Pastur uniformly over policies.Convergence is in expected Wasserstein distance; a resolvent equation and regularized inverse-trace limit also follow.Source: §3 · p. 4
  • Posterior covariance, realized squared estimation error, and mutual information have explicit Bayesian limits that hold uniformly over policies.The posterior trace converges uniformly over compact proportional-time intervals; a conditional normal approximation for squared posterior error separates Bayesian uncertainty quantification from fixed-parameter frequentist claims.Source: §3 · p. 4
  • For two candidates, every predictable linear-score policy produces an exactly Wishart Gram matrix at every finite dimension and horizon, despite a nonzero conditional mean.The selected-arm outer product has precisely the Gaussian outer-product law.Source: §3 · p. 4
  • The fixed-direction outlier transition specifies the largest and second eigenvalues and leading-eigenvector overlap, with threshold γβ2 K = 1.The theorem concerns a static directional experiment, not a fully adaptive Thompson-sampling trajectory.Source: §3 · p. 4
  • Identical overlap curves can yield different largest-eigenvalue limits, while exponentially many arms can produce a rescaled Marchenko–Pastur bulk.Together these results identify information missing from overlap curves and establish order-sharpness of the subexponential pool-growth condition.Source: §3 · p. 4

4 Adaptive Gaussian bandit designs

The section specifies an adaptive experiment in which each round offers fresh Gaussian candidates and the policy selects using observed history, a fresh seed, and the current pool. It defines the collected Gram matrix and spectral quantities, then gives linear-score and Bayesian specializations.

Adaptive experiment

  • Each round presents K independent N(0, Id/d) candidates, and an admissible policy selects using the observed history, fresh randomization, and current candidate pool.Every subsequent candidate pool is independent of the entire past, and the policy cannot access future pools.Source: §4 · pp. 4–5
  • The selected covariates form Xn, and their Gram matrix is Gn = XnXTn; the number of arms may vary with dimension.The section says its normalization matches d−1ZZT for n independent standard Gaussian columns when n/d → γ, whose first moment is γ.Source: §4 · p. 5

Spectral and transportation quantities

  • The spectral measure assigns mass 1/d to each eigenvalue of a positive semidefinite matrix, while the reference spectral law is parameterized by γ.The section also defines Wasserstein distances, relative entropy, and nuclear, Frobenius, and operator norms.Source: §4 · p. 5

Linear-score selection

  • A linear-score policy selects the candidate maximizing its inner product with a history-measurable unit direction; βK is the second moment of the K-way Gaussian maximum minus one.The definition also names the Gaussian maximum MK and its mean μK.Source: §4 · p. 5

Gaussian Bayesian bandit

  • The Bayesian specialization uses an independent Gaussian prior on the parameter and independent Gaussian observation noise, with mutual information defined against the prior.The provided definition specifies prior variance τ2 and noise variance σ2.Source: §4 · p. 5

5 Main results

The results establish policy-uniform bulk and posterior limits while identifying additional exact structure under linear-score selection. The comparison is a bulk statement and does not control individual extreme eigenvalues.

5.1 A quantitative comparison with independent Gaussian data

  • The quantitative comparison couples adaptive prefixes with independent Gaussian vectors and bounds normalized Lipschitz spectral-statistic differences, without asserting independence from the selected design.The comparison also bounds the Wasserstein distance between the Gram matrices.Source: §5.1 · p. 6
  • When n_d/d → γ ∈ (0, ∞) and log K_d = o(d), every admissible policy has the same limiting empirical spectral distribution and normalized Lipschitz spectral traces.The theorem is a bulk statement; its metric does not control a single extreme eigenvalue at order one.Source: §5.1 · p. 6

5.2 Exact selected-arm laws

  • Under linear-score selection, the selected arm has an exact decomposition into a Gaussian maximum along the score direction and independent orthogonal Gaussian noise.The rank-one coefficient in the raw second moment differs from the coefficient in the centered covariance because the Gram matrix is uncentered.Source: §5.2 · p. 7
  • For K = 2 (and also K = 1), the Gram matrix has an exact Wishart distribution in every dimension, despite the selected vector's nonzero conditional mean.The identity concerns outer products, not the selected vectors.Source: §5.2 · p. 7

5.3 Posterior uncertainty in Gaussian bandits

  • For log K_d = o(d), posterior uncertainty and information limits are policy-independent in the proportional regime, with a conditional normal approximation for squared posterior error.The approximation is a conditional posterior and joint Bayesian coverage statement, not conditional-on-θ⋆ frequentist coverage for a fixed unknown parameter.Source: §5.3 · pp. 7–8

6 Directional outliers and the limits of overlap information

A fixed selection direction yields an explicit eigenvalue and eigenvector transition, while a counterexample shows that overlap with one reference signal does not determine spectral extremes. The policies in that counterexample nevertheless share the same limiting empirical spectral distribution.

6 Directional outliers and the limits of overlap information

  • For a fixed direction, the transition threshold is β_K√γ = 1; the second eigenvalue converges to b_γ in both cases, K = 3 has threshold γ = 4π²/3, and K ≤ 2 has no fixed-direction upper outlier.The theorem concerns a static directional experiment.Source: §6 · p. 8
  • Two deterministic policies can have zero overlap with the reference signal at every round yet exhibit different Gram-matrix spectral extremes.Both empirical spectral distributions converge to μ_γ, so the contrasting extremes do not entail different limiting bulk laws.Source: §6 · p. 8
  • Overlap with a single reference signal does not characterize the persistence of directions orthogonal to it, so scalar overlap alone cannot justify a general adaptive outlier theorem.Source: §6 · p. 8

7 Exponentially many arms can change the bulk

With exponentially many candidates, selecting the largest-norm arm can change the limiting bulk spectrum. The resulting law differs from the Marchenko–Pastur law, establishing sharpness in the order of the pool-size condition, but not a necessary condition for every policy.

7 Exponentially many arms can change the bulk

  • For Kd = ⌈eαd⌉, largest-norm selection yields a bulk limit different from µγ when nd/d → γ ∈ (0, ∞).The passage identifies the law as a rescaling of µγ but does not provide enough of the theorem statement to specify the rescaling.Source: §7 · p. 8
  • This establishes sharpness in the order of log Kd, not a necessary condition for every individual policy.Some policies retain the Gaussian bulk with a larger pool because they do not use the additional choices.Source: §7 · p. 9

8 Discussion

The discussion distinguishes stability of the empirical bulk from directional and Bayesian effects of selection. It also specifies where the results stop: fixed-direction transitions do not establish adaptive-direction transitions, and the comparison relies on substantive candidate-pool assumptions.

8 Discussion

  • A persistent direction can produce an order-one outlier whose location and alignment are not recoverable from the bulk law.The bulk remains unchanged at leading order for bounded or subexponentially growing pools, irrespective of the feedback-driven policy.Source: §8 · p. 9
  • All admissible policies have the same first-order posterior mean-square uncertainty and mutual information, but this does not imply equal action quality.Policies may use a posterior mean, a posterior draw, or no reward information while collecting the same leading-order information.Source: §8 · p. 9
  • With two candidates, linear-score selection preserves the Gaussian outer-product distribution, so the Gram matrix is exactly Wishart at every dimension.For three or more candidates, an additional second moment appears in a persistent direction but remains negligible for normalized bulk statistics.Source: §8 · p. 9
  • The fixed-direction transition does not establish a learning-induced transition for Thompson sampling; that requires control of temporal geometry.The results also do not provide edge fluctuation laws, arbitrary-policy anisotropic resolvent limits, or second-order posterior-risk differences.Source: §8 · p. 9
  • The comparison is bounded by candidate-pool assumptions: correlated candidates, continuous action sets, exponential pools, or non-Gaussian laws without the transportation property may change the argument.Theorem 7.2 exhibits a changed bulk with an exponential pool in the same Gaussian model.Source: §8 · p. 9

A Proofs of the main results

The proofs couple adaptively selected observations to independent Gaussian vectors, transfer spectral limits, and then derive directional and Bayesian consequences. They establish uniformity over policies where the comparison bounds apply, while treating persistent and changing directions separately.

A.1 Proof of Theorem 5.1

  • A conditional selected-vector law is dominated by K times the Gaussian law, giving a KL bound and a Gaussian quadratic coupling that can be summed over rounds.The resulting comparison vectors are independent across rounds, and the cumulative squared coupling cost is bounded by 2n log K/d.Source: §A.1 · p. 10

A.2 Proof of Theorem 5.2

  • The coupling and independent-design Marchenko–Pastur limit yield convergence in expected Wasserstein distance uniformly over policies when both comparison terms vanish.The proof uses the comparison matrix's policy-independent marginal law to justify the supremum.Source: §A.2 · pp. 10–11

A.3 Proof of Corollary 5.3

  • The proof of Corollary 5.3 transfers resolvent and regularized trace limits through Lipschitz functions and selects the positive-root branch of the transform equation.Substituting z = −λ gives the second equation, whose positive root is the displayed formula.Source: §A.3 · p. 11

A.4 Proof of Proposition 5.4

  • Linear-score maximization decomposes each selected vector into a Gaussian maximum along the fixed direction and an independent orthogonal Gaussian component.The conditional-density calculation yields moment identities, including a distinct coefficient for centered covariance.Source: §A.4 · p. 11

A.5 Proof of Corollary 5.5

  • With two candidates, symmetrizing the selected-vector density shows its outer product has the Gaussian outer-product law, so the roundwise matrices sum to a Wishart matrix.The proof obtains independence across rounds by iterated conditioning.Source: §A.5 · p. 11

A.6 Proof of Theorem 5.6

  • Completing the square gives the Gaussian posterior in (4.2); coupled-prefix and spectral-comparison arguments yield uniform-over-policy convergence of normalized traces to v(s), while expected W1 convergence yields the information limit.Source: §A.6 · p. 12

A.7 Proof of Corollary 5.7

  • Conditioned on the data, squared error is a weighted sum of independent centered Gaussian-square variables, to which Berry–Esseen gives the asserted approximation bound.Using ci ≤ τ^2 and the positive limit for d^-1 tr Cn^2 yields the rate.Source: §A.7 · p. 12

B Proofs of the directional results

B.1 Proof of Theorem 6.1

The fixed-direction proof reduces the selected design to a Gaussian block plus a rank-one component determined by Gaussian maxima. It derives a threshold for an outlier and contrasts persistent and changing orthogonal directions.

B.1 Proof of Theorem 6.1

  • An outlier eigenvalue lies above the edge exactly when βK√γ > 1; otherwise the top eigenvalue converges to bγ, and its overlap vanishes in the subcritical and critical cases.The selected component satisfies ∥w∥²/n → 1 + βK in probability.Source: §B.1 · pp. 13–14

B.2 Proof of Proposition 6.2

  • For two policies whose directions are orthogonal to the reference signal, a persistent direction has the fixed-direction outlier limit, while cycling through orthogonal coordinates yields the Gaussian upper edge.The two policies share the same empirical spectral law.Source: §B.2 · p. 14

C Proof of Theorem 7.2

The proof controls the selected vectors through the concentration of the largest pool norm and a coupling to Gaussian vectors. This yields the Gaussian Marchenko–Pastur limit for the Gram matrix.

C Proof of Theorem 7.2

  • For each fixed r > 1, the chi-square upper tail has exponential rate −(r − 1 − log r)/2, proved by Chernoff bounding and a change of measure.The lower bound uses Gaussian coordinates with variance r′ > r, then lets r′ decrease to r.Source: C Proof of Theorem 7.2 · p. 15
  • The largest squared norm in a pool converges in probability to r_alpha, and its square root converges in L2.Uniform tail control also gives convergence of the squared norm in L1.Source: C Proof of Theorem 7.2 · p. 15
  • Rotational invariance represents each selected vector as √Sd times an independent uniform sphere direction, enabling coupling to a Gaussian vector.Different rounds yield independent copies; the Gaussian comparison uses an independent chi-square radius.Source: C Proof of Theorem 7.2 · p. 15
  • The Gaussian Marchenko–Pastur law and first-moment convergence, combined with the coupling and Wasserstein triangle inequality, establish the spectral limit.The coupling compares the Gram matrix with a scaled Gaussian design in normalized nuclear norm.Source: C Proof of Theorem 7.2 · p. 15

Related papers

Loading 2609.30321v1…