PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets

Arda Güçlü, Subhonmesh Bose, John R. Birge

arXiv:2609.32149v1stat.MLcs.LG

TL;DR

In spherical linear bandits, effective learning requires both sufficient exploration to improve parameter estimates and controlled cost from acquiring information. The paper develops an optimism-agnostic regret framework based on these requirements and shows that variants of Thompson sampling and UCB meet them, yielding order-optimal regret.

  • Problem

    For spherical linear bandits, regret reflects both imprecise parameter estimates and the cost of acquiring information, motivating a common way to analyze how exploration and exploitation jointly control regret.

    Source: §1 · p. 1

  • Method

    The paper decomposes regret into precision and information-acquisition costs, then uses information growth and controlled action deviation to analyze algorithms without relying on optimism.

    Source: §1 · p. 3

  • Results

    Variants of Thompson sampling and UCB satisfy the framework's inference and action-concentration conditions and achieve order-optimal regret.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    Sufficient information growth and controlled deviation provide a modular basis for analyzing and designing exploration rules on spherical action sets.

    Source: §1 · p. 6, §7 · p. 26

    Finite-horizon empirical averages diagnose self-correction but do not establish the required property at the simulated horizon.

    Source: §6 · p. 24

Abstract

from arXiv · show

Linear bandits model sequential decision-making problems with noisy rewards that are linear in the decision variable, where an agent must simultaneously learn about an unknown parameter that governs the mean rewards, while maximizing (expected) rewards over time. Two prominent algorithmic families--upper confidence bound (UCB) and Thompson sampling (TS)--achieve a balance of exploration (to estimate said parameter) and exploitation (utilization of knowledge about it) across time. The quality of estimation of that parameter depends on the eigenvalues of a design matrix. In this paper, we begin by showing that if the inference quality obtained from exploration, encoded in the minimum eigenvalue of the design matrix, grows $\gtrsim \sqrt{t}$ with time $t$, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability $\mathcal{O}(\sqrt{T}\log T)$-regret rate over a time-horizon $T$ for spherical action sets. This analysis is algorithm-agnostic and follows an alternative route to the classical optimism-based elliptical-potential argument for regret analysis. Then, we illustrate that variants of UCB and TS satisfy the inference and concentration properties and in turn, enjoy optimal regret rate. In effect, our results provide a modular framework that can be used to analyze linear bandit algorithms and explicitly connect quality of parameter estimation to optimal regret accumulation.

1 Introduction

For linear bandits on spherical action sets, the paper decomposes regret into the cost of imprecise decisions and the cost of acquiring information. It develops an optimism-agnostic framework in which sufficient information growth and controlled deviation from the estimated greedy action yield order-optimal regret, and applies the framework to variants of Thompson sampling and UCB.

  • Spherical geometry decomposes regret into the cost of imprecise decisions and the cost of moving away from the estimated greedy action to acquire information.The two costs are distinct but dynamically linked.Source: §1 · pp. 1, 3
  • Sufficient information growth together with controlled deviation from the estimated greedy action gives order-optimal high-probability regret, and variants of Thompson sampling and UCB satisfy these conditions.The framework connects inference quality to regret accumulation without requiring optimism-based analysis.Source: §1 · pp. 1–4
  • The analysis reduces spherical linear bandit regret to driving an information variable to a critical scale while controlling cumulative deviation from the estimated greedy action.These requirements are presented as interpretable sufficient conditions for optimal cumulative regret.Source: §1 · pp. 3–4
  • The framework avoids the optimism-shortfall and elliptical-potential lemma used in the classical route, bounding regret through estimation accuracy and cumulative deviation from the estimated greedy action.Source: §1 · p. 5
  • A shared self-correction property lets deterministic optimism-based UCB and randomized Thompson sampling be analyzed through their information growth rather than their different exploration mechanisms.For UCB, the analysis replaces the confidence ellipsoid with a containing confidence box while preserving optimism.Source: §1 · pp. 2, 4, 6
  • The same requirements serve as a design principle for exploration rules that need not use horizon-dependent confidence sets calibrated to preserve optimism.The paper describes UCB-type variants designed around information growth and concentrated exploitation.Source: §1 · p. 6

2 A Modularized Framework for Regret Bounds

For spherical-action linear bandits, this section gives two conditions under which a policy achieves order-optimal regret with high probability. The conditions separate estimation quality from how concentrated the selected actions are.

2 A Modularized Framework for Regret Bounds

  • The framework requires guaranteed inference and concentrated explorations as complementary policy properties.The inference property controls estimation error, while the exploration property controls cumulative deviation from the estimated greedy action.Source: §2 · p. 7
  • Under the stated bandit assumptions, satisfying both conditions guarantees high-probability order-optimal regret.The environment has bounded nonzero parameter norm, i.i.d. zero-mean sub-Gaussian noise, and a spherical action set.Source: §2 · p. 7
  • The section’s regret bound follows by combining these properties under the spherical-action setting.The proof uses the Lipschitz continuity of the optimal-action map to relate estimation accuracy and action deviation to regret.Source: §2 · pp. 7–8

3 The Inference Dynamics

This section shows how a self-correction condition on information growth yields guaranteed inference, which—together with concentrated actions—supports the regret bound. It then explains how linear TS and UCB satisfy the condition through different exploration mechanisms.

3 The Inference Dynamics

  • The condition requires near-uniform conditional growth of an information statistic on nested high-probability events, but does not itself require actions near the estimated greedy action.It controls information accumulation; it does not imply the separate concentrated-exploration property.Source: §3 · p. 9
  • Self-correction plus concentrated actions yields the inference and action properties needed for the regret guarantee.Theorem 3.2 turns Property 3.1 into guaranteed inference; Theorem 2.5 then applies when concentrated exploration also holds.Source: §3 · pp. 9, 10, 14
  • Theorem 3.2 derives time-indexed minimum-eigenvalue growth of order √t, yielding the guaranteed-inference property.The theorem establishes this growth uniformly after burn-in with high probability.Source: §3 · pp. 9–10
  • Linear TS and UCB obtain self-correction differently: TS through conditional expected information, and UCB through a pathwise action bound.The section identifies these distinct routes as producing the common inference mechanism.Source: §3 · p. 14

4 Analysis of Linear Thompson Sampling

The section verifies that linear Thompson sampling satisfies the framework’s self-correction and concentrated-exploration properties, subject to a burn-in initialization condition. The resulting policy therefore achieves order-optimal regret.

4 Analysis of Linear Thompson Sampling

  • Perturbation anti-concentration supports a lower bound on the predictable design matrix, while moment bounds control exploration costs.The analysis uses the conditional second-moment lower bound and second- and fourth-moment bounds on perturbations.Source: §4 · pp. 14–15
  • With λmin,mT ≥ (log T)^2 and the stated assumptions, linear TS satisfies both required properties for sufficiently large T.Theorem 4.3 establishes self-correction and concentrated explorations, which imply the order-optimal regret guarantee through the framework.Source: §4 · pp. 16, 18
  • A coordinate-wise exploratory burn-in can provide the required minimum-eigenvalue initialization.Cycling through the canonical basis vectors makes the design matrix proportional to the identity at the end of each cycle.Source: §4 · p. 18

5 Analysis of UCB

This section verifies that the analyzed UCB policy satisfies the self-correction and concentrated-exploration conditions, so it inherits the framework’s regret guarantee. Its proof uses information growth and action concentration, not optimism itself.

5 Analysis of UCB

  • With λmin,mT ≥ (log T)^2, Algorithm 2 satisfies self-correction and concentrated explorations for sufficiently large T.These properties give the framework’s inference and regret guarantees.Source: §5 · pp. 19–21
  • The proof does not require optimism or confidence-set inclusion; it requires sufficient information growth and controlled deviation from the estimated greedy action.The box-shaped set helps characterize the selected action, but optimism is described as a means of generating the desired exploration behavior rather than a proof prerequisite.Source: §5 · pp. 21–22
  • Replacing the confidence radius with a sufficiently large constant preserves both required properties under the same initialization condition.Corollary 5.2 requires ρ ≥ λUCB θmax and λmin,mT ≥ (log T)^2.Source: §5 · p. 22
  • Unlike the paired-action mechanism of LinUCB-VN, the paper’s conditional drift condition accommodates randomized policies and simpler one-action-per-round UCB.LinUCB-VN enforces growth pathwise through paired perturbations, while this analysis abstracts it as a conditional per-step requirement.Source: §5 · p. 22

6 What Happens in Short Horizons?

At a short horizon where initialization for the asymptotic guarantees is unattainable, the experiments compare Thompson sampling and Box UCB. Fixed-radius Box UCB behaves similarly to Thompson sampling, while the horizon-dependent radius produces stronger information growth and higher regret.

6 What Happens in Short Horizons?

  • At the tested horizon with n = 10, the initialization requirement cannot be met, although cycling an orthonormal basis can produce the required eigenvalue growth over time.The experiments compare TS and two Box UCB variants across ten repetitions using paired true parameters and noise sequences.Source: §6 · pp. 22–23
  • Empirical drift estimates average observed trajectories, whereas theoretical C4 is a uniform conditional lower bound; these estimates diagnose but do not establish Property 3.1 at the simulated horizon.Source: §6 · p. 24
  • Tail-fit λmin,t exponents were 0.5091, 0.5162, and 0.5367, while regret exponents were 0.4986, 0.5030, and 0.5167 for TS, fixed-radius Box UCB, and horizon-dependent Box UCB, respectively.The exponents come from log-log fits over the final 1% of rounds; the authors caution that multiplicative constants distort raw log-ratios at finite horizons.Source: §6 · pp. 23–24, Figure 2 · p. 25
  • Full-horizon and tail drift estimates differed by 2.6% for TS, 2.6% for fixed-radius Box UCB, and 6.7% for horizon-dependent Box UCB; the latter estimates were about six times larger.Source: §6 · p. 25
  • The horizon-dependent Box UCB radius yields stronger information acquisition and larger cumulative regret than TS or fixed-radius Box UCB, exposing a finite-horizon exploration cost.Source: §6 · pp. 24–25

7 Conclusions

The conclusion presents an optimism-agnostic framework linking inference quality and action concentration to order-optimal regret, while identifying open questions about necessity, dimension dependence, and broader settings.

7 Conclusions

  • Sufficient inference growth and controlled deviation from the estimated greedy action yield order-optimal regret for TS and UCB variants without requiring optimism.A self-correction mechanism gives Ω(√t) growth of the minimum eigenvalue under the stated assumptions.Source: §7 · p. 26
  • The analysis tracks regret and inference scaling over time, not optimal dependence on problem dimension; recovering that dependence is future work.The proposed technique's dimension dependence is not optimized.Source: §7 · p. 26
  • The analysis establishes sufficient conditions for near-optimal regret, but whether they are necessary remains open, including whether λ_min,t must grow at Ω(√t) with high probability.The paper notes prior necessity results in expectation and calls for analogous high-probability requirements.Source: §7 · p. 26
  • Extending the framework beyond the Euclidean unit ball and to adaptive problems such as linear quadratic regulators and Markov decision processes remains future work.Such extensions require suitable inference-quality measures and mechanisms that improve them while controlling exploration cost.Source: §7 · p. 26
Loading 2609.32149v1…