PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Prakhar Singhvi, Yi Zou, Abhishek Bhattacharjee

arXiv:2609.28718v1stat.MLcs.LGmath.STstat.TH

TL;DR

In proportional-horizon Gaussian bandits, the leading posterior uncertainty is the same across causal policies, leaving a distinction between information learned and how actions use it. The paper derives exact regret and optimality results for this setting, showing that greedy selection attains the asymptotic Bayes optimum while Thompson sampling has greater leading regret.

  • Problem

    Cumulative-regret inequalities can give rates without identifying leading loss, learning trajectories, or the cost of randomization in high-dimensional proportional-horizon experiments.

    Source: §1 · p. 1

  • Method

    The paper establishes a policy-uniform posterior uncertainty limit and combines Gaussian posterior identities with posterior geometry and Gaussian decision calculations to derive regret.

    Source: §1 · p. 2

  • Results

    Posterior-mean greedy selection attains the asymptotic Bayes-regret infimum over causal policies, while Thompson sampling incurs a strictly larger leading regret in this model.

    Source: §1 · p. 2, §3 · p. 4

  • Takeaways & Limitations

    The analysis separates policy-independent information acquisition from policy-dependent conversion of posterior knowledge into reward.

    Source: §7 · p. 9

    The conclusions are Bayesian and do not establish uniform-in-parameter frequentist results or exact finite-horizon Bayes optimality for greedy selection.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper studies a proportional-horizon Gaussian bandit in which adaptive choices are made from fresh Gaussian candidate pools. It shows that posterior learning has a policy-independent first-order limit, while decision quality and regret depend on the policy.

1 Introduction

  • A policy-independent first-order posterior uncertainty holds uniformly over causal policies, including rules that use the full candidate pool nonlinearly.A scalar posterior variance function describes leading estimation error across policies.Source: §1 · p. 2
  • Thompson sampling’s posterior draw causes immediate loss that cannot be offset by a first-order improvement in future learning in this experiment.Posterior-mean greedy selection maximizes current conditional expected reward.Source: §1 · p. 2
  • Posterior geometry and Gaussian maxima yield exact leading regret comparisons, but only for the specified proportional Gaussian model.The paper explicitly does not claim a general comparison across contextual distributions.Source: §1 · p. 2
  • Single-round regret remains random with a nondegenerate limiting distribution, although its expected difference converges to a deterministic curve.Cumulative averaging removes this round-specific variation.Source: §1 · p. 2

2 Existing work

Prior work studies regret guarantees for posterior sampling, high-dimensional inference, and exploration-free contextual bandits. This paper distinguishes itself by deriving exact proportional-regime Bayes regret and same-horizon comparisons in a specific Gaussian model.

2 Existing work

  • Posterior-sampling research establishes broad regret guarantees and information-based analyses, while this paper targets exact leading Bayes regret for genuine Gaussian posterior sampling at proportional dimension and horizon.The present analysis separates spectral information acquisition from its conversion into reward.Source: §2 · p. 2
  • Unlike small-gap diffusion limits with stochastic state trajectories, the growing-dimension setting has deterministic normalized posterior states but random single-round candidate-pool losses.The paper adds a policy-uniform trace limit for fresh finite candidate pools.Source: §2 · p. 3
  • Contextual-greedy guarantees use assumptions different from this isotropic Gaussian common-parameter model, whose contribution is an exact proportional Bayes value uniform over competing policies.The result does not introduce the general principle that random contexts can make explicit exploration unnecessary.Source: §2 · p. 3
  • Compared with Bayesian batched-greedy results, this work gives a same-horizon limiting comparison: unbatched posterior-mean greedy selection attains the causal-policy infimum, while Thompson sampling’s excess loss is explicit.The conclusions are narrower in distributional scope and are not distribution-free dominance claims.Source: §2 · p. 3
  • The adaptive spectral comparison uses Gaussian transportation and matrix norm inequalities rather than assuming an unproved Thompson-sampling spectral limit.A fixed fresh Gaussian pool differs substantively from a continuously controlled action space.Source: §2 · p. 3

3 Our contributions

The contributions establish policy-uniform posterior learning and use it to derive exact regret, optimality, and distributional results. In the specified Gaussian experiment, posterior-mean greedy selection attains the asymptotic Bayes optimum.

3 Our contributions

  • A posterior state law identifies covariance trace, posterior-mean norm, estimation error, and parameter overlap uniformly over causal policies, without a postulated state-evolution recursion.The scalar state function is explicit and satisfies a closed differential equation.Source: §3 · pp. 3–4
  • For every fixed posterior covariance multiplier, the paper gives leading Bayes regret and an L1 limit of realized cumulative regret, uniform on compact proportional-time intervals.Thompson sampling and posterior-mean greedy selection correspond to η = 1 and η = 0.Source: §3 · p. 4
  • Posterior-mean greedy selection attains the asymptotic infimum of Bayes regret over all admissible causal policies.The proof combines an exact one-step reward bound with policy-uniform posterior learning to control current decisions and possible future information benefits.Source: §3 · p. 4
  • Thompson sampling’s instantaneous regret ratio to greedy regret is exactly 1 + q(s), and its cumulative ratio lies strictly between one and two at every positive finite proportional horizon.The regret curve is strictly increasing in the posterior covariance multiplier.Source: §3 · p. 4
  • At positive noise the Thompson-to-greedy ratio approaches two at long proportional horizons, but in the sequential vanishing-noise limit it becomes 3/2 after the noiseless interpolation point.The order of limits is stated explicitly.Source: §3 · p. 4
  • Single-round regret has a nondegenerate limiting distribution, alongside a limiting probability of selecting the truly best arm.This distinguishes deterministic expected regret from residual Gaussian decision uncertainty at an individual round.Source: §3 · p. 4

4 The Gaussian bandit experiment

The experiment uses a Gaussian prior, fresh Gaussian candidate arms, and Gaussian reward noise, with policies selecting from each current pool using observed history and randomization. It defines posterior-covariance-scaled policies and regret relative to a benchmark that knows the true parameter.

4 The Gaussian bandit experiment

  • The experiment fixes K ≥ 2 and positive τ and σ, with θ⋆ ∼ N(0, τ^2 I_d), candidate vectors distributed as N(0, I_d/d), and Gaussian noise of variance σ^2.The number of candidates stays fixed as dimension grows.Source: §4 · pp. 4–5
  • At each round the learner observes the candidate pool, chooses an arm, and receives its linear reward plus noise; admissible choices depend only on past history, policy randomization, and the current pool.Policies have no further access to θ⋆ or future variables and may depend on the horizon.Source: §4 · p. 5
  • The posterior-covariance multiplier defines a policy family whose η = 0 and η = 1 cases are posterior-mean greedy selection and Thompson sampling, respectively.Random selection chooses uniformly and independently of the current candidates and observed past.Source: §4 · p. 5
  • Regret is measured against a benchmark that knows θ⋆ and maximizes conditional mean reward in each current pool, excluding observation noise from the difference.The section specifies the information structure, policies, and loss used in the results.Source: §4 · pp. 4–5
  • The deterministic state and regret curves use the expected maximum of K independent standard normals, with continuous extensions at zero and a separate curve for random selection.The single-round loss definition uses correlated Gaussian pairs and the arm maximizing the first coordinate.Source: §4 · pp. 5–6

5 Main results

The main results connect policy-uniform posterior learning to policy-specific regret, identify the first-order Bayes optimum over causal policies, and characterize the randomness remaining in single-round loss.

5.1 Posterior geometry without a policy-specific closure

  • Posterior covariance trace, posterior-mean norm, estimation error, and parameter overlap have L1 limits uniformly over policies at proportional times.The limiting posterior state is represented by a scalar variance function v, and the posterior-mean cosine converges to q(s).Source: §5.1 · p. 6
  • The posterior-mean cosine tends to q(s), while an independent posterior draw has limiting cosine q(s)^2 with the true parameter.The passage attributes this distinction to posterior-sampling variability, not to a different leading posterior covariance.Source: §5.1 · p. 6

5.2 Exact one-step identities

  • Posterior-mean greedy selection attains equality in the one-step reward bound.The bound is evaluated under each policy’s own posterior history and does not compare policies’ posterior means at finite dimension.Source: §5.2 · p. 7

5.3 Exact regret curves and optimality

  • For fixed posterior covariance multiplier η, expected and realized regret have limiting curves, with realized cumulative regret converging in L1.The claims include random selection and hold uniformly over compact proportional-time intervals.Source: §5.3 · p. 7
  • The first-order Bayes-regret infimum is defined over the full causal policy class, but the result is asymptotic rather than finite-dimensional or frequentist minimax.The optimality result is stated for each fixed positive proportional horizon.Source: §5.3 · p. 7
  • Thompson sampling’s instantaneous regret ratio to greedy regret is 1 + q(s), and its cumulative excess regret is positive.The regret curve increases strictly with the posterior covariance multiplier.Source: §5.3 · pp. 7–8

5.4 Single-round fluctuations and best-arm agreement

  • At finite s and positive noise, single-round regret has a nondegenerate limiting distribution rather than converging in probability to its expected limit.The limiting decision loss has expected value μK(1 − c), and its probability of zero loss is strictly between zero and one.Source: §5.4 · p. 8

6 Closed forms and horizon–noise asymptotics

This section gives closed-form cumulative-regret results and examines how the limiting curves behave across horizon and noise regimes. The stated limits apply after the proportional dimension limit and do not establish a joint approximation for arbitrary horizons growing faster than dimension.

Closed-form cumulative regret

  • Theorem 6.1 gives closed-form cumulative regret under Definition 4.4.The section evaluates the regret integrals and describes how the limiting curves vary with horizon or noise.Source: §6 · p. 8

Short and long proportional horizons

  • Theorem 6.2 treats short and long proportional horizons for fixed positive τ and σ.The cited horizon limits concern deterministic curves after the proportional dimension limit, not arbitrary sequences with T/d → ∞.Source: §6 · p. 8

Sequential vanishing-noise limit

  • Theorem 6.3 takes the vanishing-noise limit only after the dimension limit, at fixed τ and Γ.The interpolation point s = 1 reflects the rank of a proportional Gaussian design, not an asserted spectral outlier transition for the adaptive bandit matrix.Source: §6 · p. 9

7 Discussion

In the proportional Gaussian experiment, posterior uncertainty has a universal leading limit, while the policy determines how that information is converted into reward. Greedy optimality is therefore a Bayesian asymptotic result tied to the model’s assumptions, not a general finite-horizon or frequentist guarantee.

7 Discussion

  • The policy-independent leading posterior uncertainty and policy-dependent action direction separate information acquired from the quality of decisions made with it.This separation makes exact optimization over causal policies possible in the specified experiment.Source: §7 · p. 9
  • Greedy optimality relies on isotropic Gaussian priors and candidates, a fixed pool size, fresh pools, and horizons proportional to dimension.Correlated pools, non-isotropic priors, some growing pools, and other horizon scales can change the informational value of actions.Source: §7 · p. 9
  • The state theorem is Bayesian and does not automatically give uniform-in-parameter frequentist conclusions or exact finite-horizon Bayes optimality.The comparison also does not establish that posterior sampling is generally inferior in contextual bandits.Source: §7 · p. 9
  • Instantaneous regret retains random candidate-pool geometry, whereas cumulative regret averages that randomness over a growing number of rounds.These are distinct levels of averaging even when posterior scalar states converge deterministically.Source: §7 · p. 9
  • The analysis uses normalized spectral traces, not the adaptive Gram matrix’s leading eigenvector, and establishes no Thompson-sampling outlier transition.The regret conclusions instead follow from policy-uniform bulk learning and Gaussian decision identities.Source: §7 · p. 9

A Adaptive spectral comparison

The appendix compares adaptively selected designs with independent Gaussian designs to establish a posterior-trace limit uniformly over policies. The independent-design trace is evaluated through the Marchenko–Pastur law, and the comparison transfers that limit to the adaptive setting.

A Adaptive spectral comparison

  • 2 log K/d bounds the conditional squared coupling cost between a selected vector and a standard Gaussian comparison vector.Successive measurable couplings produce mutually independent comparison vectors while preserving the original experiment.Source: A Adaptive spectral comparison · p. 10
  • The selected-design posterior trace converges to the independent-Gaussian trace in expected supremum norm, uniformly over policies.The comparison applies at proportional horizons.Source: A Adaptive spectral comparison · p. 11
  • For fixed s > 0, the independent-design empirical law converges to the Marchenko–Pastur measure, whose resolvent evaluation yields v(s).At s = 0, the trace is identically τ^2.Source: A Adaptive spectral comparison · p. 11
  • Monotonicity and finite-partition bounds give expected supremum-norm convergence of Gaussian trace paths, which the comparison transfers to every policy.The argument uses continuity of v and convergence at fixed partition points.Source: A Adaptive spectral comparison · p. 11

B.1 Proof of Theorem 5.1

The proof uses conditional Gaussian posterior identities and norm concentration to obtain limiting overlaps, then establishes that greedy selection maximizes current expected reward among admissible policies.

B.1 Proof of Theorem 5.1

  • Conditioning on the observed history leaves a Gaussian posterior N(m_t,C_t), with covariance controlled by the observed Gram matrix.The posterior calculation remains valid when the full past candidates and policy seeds are retained.Source: §B.1 · p. 11
  • For s > 0, posterior-mean and parameter norm limits yield the cosine q(s) between the posterior mean and the true parameter.The proof combines uniform bounds on normalized inner products and posterior-error norms.Source: §B.1 · pp. 11–12
  • At s = 0, the cosine tends to zero, including under the deterministic convention for a zero score vector.The argument also covers η = 0 when the number of observations per dimension tends to zero.Source: §B.1 · p. 12

B.2 Proof of Proposition 5.2

  • Greedy selection attains the maximum conditional expected reward, while a random index has zero expected true reward.The expected maximum true reward is µ_K E∥θ⋆∥/√d.Source: §B.2 · p. 12

C.1 Proof of Theorem 5.3

These proofs establish limiting regret results by combining conditional Gaussian calculations with bounds uniform over policies. They also derive comparisons across posterior covariance choices, instantaneous decision loss, horizon lengths, and noise levels.

C.1 Proof of Theorem 5.3

  • The conditional expected regret converges in L1 to its limiting curve, and the realized cumulative regret converges in expected supremum norm.Pointwise convergence and a uniform integrable bound yield the conditional-mean result; martingale bounds control the fluctuations.Source: §C.1 · p. 13

C.2 Proof of Theorem 5.4

  • The policy-uniform lower bound and greedy upper bound coincide, so posterior-mean greedy selection attains the limiting optimal Bayes regret over causal policies.The lower-bound error is independent of the policy, allowing the bound to hold after taking the infimum.Source: §C.2 · p. 14

C.3 Proof of Theorem 5.5

  • The regret curve is strictly increasing in the posterior covariance multiplier, and Thompson sampling’s instantaneous regret ratio to greedy is 1 + q(s).The cumulative regret comparisons follow by integrating the strict instantaneous inequalities.Source: §C.3 · p. 14

D.1 Proof of Theorem 5.6

  • For c < 1, instantaneous decision loss has a nondegenerate limiting distribution, although its mean is μK(1 − c).The limiting score–reward array is Gaussian, and the score and reward maximizers can either agree or differ with positive probability.Source: §D.1 · pp. 14–15

E.1 Proof of Theorem 6.1

  • A change of variables and integration transform the greedy cumulative-regret expression into a closed form.The proof substitutes the change of variables into the regret integral and integrates its polynomial term.Source: §E.1 · p. 15

E.2 Proof of Theorem 6.2

  • The short-horizon expansion follows by substitution, while the large-s expansion yields the long-horizon cumulative asymptotic and a strictly positive leading coefficient for η = 0.The large-s expansion uses v(s) = σ²/s + O(s⁻²).Source: §E.2 · p. 15

E.3 Proof of Theorem 6.3

  • As noise vanishes, the regret formulas converge on finite intervals, and integrating the limiting curves gives cumulative limits and plateau values.The proof uses dominated convergence for the finite-interval integrals.Source: §E.3 · p. 16

Related papers

Loading 2609.28718v1…