Source-linked AI summary
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Tor Lattimore, Csaba Szepesvari
TL;DR
Finite-armed bandit techniques, especially optimism and Thompson sampling, have been extended to stochastic linear bandits, but their asymptotic instance-dependent regret has been less understood. The paper characterizes the optimal asymptotic regret and constructs a strategy achieving it. It finds that optimism-based algorithms can be arbitrarily worse than optimal, and extends this conclusion to Thompson-sampling-based algorithms.
Problem
The paper addresses limited understanding of instance-dependent asymptotic regret in linear bandits, where common approaches generalize optimism and Thompson sampling from finite-armed bandits.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
The authors argue that understanding asymptotics is a useful first step toward optimal finite-time instance-dependent guarantees.
Source: §1 · p. 2The lower-bound analysis requires Gaussian noise, although the upper bound can be relaxed to 1-subgaussian noise.
Source: §1 · p. 1
Abstract
from arXiv · showhide
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case setting, we analyse the asymptotic instance-dependent regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation. For example, for generalised linear bandits and reinforcement learning.
1 INTRODUCTION
The paper studies finite-action stochastic linear bandits, where optimism and Thompson sampling are established approaches. It characterizes optimal asymptotic instance-dependent regret and shows these approaches can be arbitrarily worse, motivating asymptotic analysis as a guide to finite-time guarantees.
1 INTRODUCTION
- The linear bandit generalizes the finite-armed bandit: actions are vectors, and noisy payoffs depend on an unknown parameter through their inner product.The paper assumes a finite action set spanning the parameter space and Gaussian noise; the Gaussian assumption can be relaxed to 1-subgaussian noise for the upper bound but is needed for the lower bound.Source: §1 · p. 1
- Optimism and Thompson sampling are established algorithmic designs for finite-armed bandits that have also been applied to linear bandits.The cited linear-bandit work on these approaches reports good empirical performance or near-minimax guarantees.Source: §1 · p. 1
- The paper characterizes optimal asymptotic instance-dependent regret and shows optimism- and Thompson-sampling-based algorithms can be arbitrarily worse than optimal.These approaches can be near-optimal in the worst case, which can obscure their instance-dependent disadvantages.Source: §1 · p. 1
- Asymptotic analysis can help reveal instance-specific trade-offs and guide the development of finite-time instance-dependent guarantees.The authors note that worst-case optimality can still yield sub-optimal instance-dependent guarantees, as illustrated by MOSS for finite-armed bandits.Source: §1 · p. 2
- Partial monitoring also exhibits failure of optimism, but its analyses do not directly generalize to linear bandits because information transfer between actions requires careful study.In partial monitoring, the learner may not observe the reward even for the action taken.Source: §1 · p. 2
2 NOTATION
The notation section defines the quantities used to express arm values, gaps, pull counts, and policy consistency.
2 NOTATION
- Arm means and gaps quantify expected rewards relative to an optimal action, while pull counts track how often each arm and optimal arms are selected.The section also defines the minimum and maximum positive suboptimality gaps.Source: §2 · p. 2
- A policy is consistent when its regret is subpolynomial in the horizon for every parameter and every p > 0.The section gives equivalent asymptotic formulations using O notation and a logarithmic limit superior.Source: §2 · p. 2
- Vectors indexed by the action set use an arbitrary fixed arm order, so α_x denotes the coordinate associated with arm x.Source: §2 · p. 2
3 LOWER BOUND
For consistent policies, estimating suboptimal-arm gaps must meet a logarithmic confidence-width requirement. The section characterizes the optimal asymptotic regret through an optimization that balances identifying those gaps against regret.
3 LOWER BOUND
- The optimal asymptotic regret is logarithmic and is characterized by the optimization defining c(A, θ).No consistent strategy can avoid allocating samples to identify all suboptimal-action gaps with high confidence; a good strategy minimizes regret subject to that identifiability condition.Source: §3 · pp. 2–3
- A consistent policy’s confidence width for estimating each suboptimal-arm gap must shrink at least logarithmically, with a specific constant.If the expected Gram matrix is not eventually invertible, the policy must suffer linear regret on some problem.Source: §3 · p. 2
- For standard-basis arms with k = d, the section recovers the finite-armed lower bound of Lai and Robbins [1985].Finite-armed UCB can also be applied by ignoring the arm structure.Source: §3 · pp. 2–3
- With α > 1 and sufficiently small ε, Example 4 gives c(A, θ) = 2α², while removing x2 raises the constant to 2ε^-1.The example attributes the difference to x1 and x3 pointing in nearly the same direction: x2 helps distinguish them despite being suboptimal.Source: §3 · p. 3
- The cited partial-monitoring lower-bound works have narrower stated settings: one assumes a finite parameter set, and another restricts observations to a finite set.The section notes that these restrictions limit their applicability to the linear-bandit setting.Source: §3 · p. 3
4 PROOF OF THEOREM 1
The proof compares the learner’s behavior under the true parameter and a nearby alternative that changes the optimal arm. Information-theoretic bounds then constrain how well a consistent policy can distinguish the two.
4 PROOF OF THEOREM 1
- The proof uses Pinsker’s inequality and an information-processing result to relate distinguishability of outcome sequences to expected arm counts and per-arm relative entropies.For the fixed policy and Gaussian-noise linear bandits, the KL divergence between the two sequence distributions is computed exactly.Source: §4 · p. 3
- Comparing the two outcome distributions yields a lower bound on the information the policy must gather to distinguish which arm is optimal.The proof applies the event-based KL inequality and then uses the parameter perturbation to calculate the divergence term.Source: §4 · pp. 3–4
- A nearby parameter θ′ is chosen so that the suboptimal arm x becomes better than x∗, while consistency makes the relevant event probabilities small under both parameters.The proof uses the event that the optimal arm is played at most half the rounds under θ and more than half under θ′.Source: §4 · p. 4
- With multiple optimal arms, the theorem can be extended to suboptimal actions that can be made optimal without making any original optimal action optimal.The remark adjusts the choice of x∗ and counts pulls of all originally optimal actions together.Source: §4 · p. 5
5 CONCENTRATION
The section refines least-squares concentration guarantees for estimating linear-bandit means and gaps. Its stated asymptotic confidence-width term is smaller than the cited earlier guarantee by a factor of d.
5 CONCENTRATION
- The analysis studies the Gram matrix Gt and least-squares estimates of the parameter and suboptimality gaps, using the estimates only when Gt is invertible.The empirical gap for arm x is the largest estimated arm mean minus x’s estimated mean.Source: §5 · p. 5
- The concentration result refines the existing guarantees of Abbasi-Yadkori et al. [2011] and is used to obtain asymptotic optimality.The proof uses a peeling argument.Source: §5 · p. 5
- Asymptotically, fn,1/n ∼ 2 log(n), compared with 2d log(n) in the cited guarantee of Abbasi-Yadkori et al. [2011].The theorem applies for δ ∈ [1/n, 1), sufficiently large n, and a round t0 at which Gt0 is almost surely nonsingular.Source: §5 · p. 5
6 OPTIMAL STRATEGY
The proposed strategy estimates gaps, allocates pulls according to an optimization, and switches to UCB if an anomaly signals that the gap estimates may be inaccurate. A barycentric spanner supplies the warm-up actions.
6 OPTIMAL STRATEGY
- A barycentric spanner is a set of d actions such that every action has a representation as a linear combination with coefficients in [−1, 1]; finite action sets spanning Rd guarantee its existence.In warm-up, the algorithm deterministically chooses actions from a barycentric spanner to obtain a rough estimate of sub-optimality gaps.Source: §6 · p. 5
- The strategy has warm-up, success, and recovery phases, using barycentric-spanner actions to estimate gaps before allocating pulls based on estimated gaps.If an anomaly indicates inaccurate gap estimates, the strategy switches to recovery and plays UCB.Source: §6 · p. 5
- In the success phase, the strategy uses Tn(Δ̂), the solution to the stated optimization with estimated gaps, to set action pull targets.The algorithm continues while the estimated means remain within the stated confidence threshold, then discards the data if it enters recovery.Source: §6 · pp. 5–6
7 PROOF OF THEOREM 10
The proof bounds regret across warm-up, recovery, and success phases. Warm-up is asymptotically negligible, recovery is rare, and the success phase supplies the main asymptotic contribution.
7 PROOF OF THEOREM 10
- The proof controls the probability of F_n by 1/log(n) and F′_n by 1/n; when F′_n fails, success-phase regret is at most logarithmic.Source: §7 · pp. 6–7
- When F_n does not occur, the algorithm never enters recovery and the success-phase regret is asymptotically optimal.Source: §7 · p. 6
- The success-phase analysis combines the phase decomposition and its bounds, then takes n to infinity to complete the theorem.Source: §7 · p. 7
- The warm-up phase lasts d⌈log1/2(n)⌉ rounds and contributes asymptotically negligibly to regret.Source: §7 · p. 7
- The recovery phase occurs only on F_n, whose probability is at most 1/log(n), so its logarithmic regret contributes negligibly in expectation.Source: §7 · p. 7
8 SUB-OPTIMALITY OF OPTIMISM AND THOMPSON SAMPLING
Under stated confidence-set assumptions, the paper constructs a simple linear-bandit instance where optimism explores a costly suboptimal arm too little. Thompson sampling also under-samples that arm, so both approaches can be arbitrarily worse than optimal.
8 SUB-OPTIMALITY OF OPTIMISM AND THOMPSON SAMPLING
- The counterexample uses A = {e1, e2, x}, x = (1 − ε, 8αε), and θ = e1, making e2 costly while x is nearly optimal.Source: §8 · p. 8
- If optimism is consistent and its confidence set contains θ with probability at least 1 − 1/n, then E[T_e2(n)] ≤ 2 + 4α log(n).Source: §8 · p. 8
- For small ε, the optimal regret is c(A, θ) = 128α2, while optimism is suboptimal by an arbitrarily large constant factor when ε ≪ α.Source: §8 · p. 8
- Thompson sampling's posterior concentrates around the optimal action, making the likelihood of sampling e2 vanish once T_e2(t − 1) = Ω(α log(n)).Source: §8 · p. 8
9 SUMMARY
The paper characterises optimal asymptotic regret for finite-action linear bandits with Gaussian noise and shows optimism-based algorithms can be arbitrarily worse than optimal. It also improves a self-normalised concentration guarantee asymptotically.
9 SUMMARY
- The paper characterises optimal asymptotic regret for linear bandits with Gaussian noise and finitely many actions, and shows reasonable optimism-based algorithms can be arbitrarily worse than optimal.Source: §9 · p. 8
- The self-normalised concentration guarantees of Abbasi-Yadkori et al. [2011] are improved by a factor of d asymptotically.Source: §9 · p. 8
A PROOF OF THEOREM 8
- The concentration proof covers transformed action estimates with a finite covering set and controls failure probabilities through union bounds.Source: A PROOF OF THEOREM 8 · p. 11
B PROOF OF COROLLARY 2
The proofs establish the lower-bound implication for consistent strategies and show that their expected Gram matrix is eventually nonsingular. The latter follows by contradiction using an indistinguishable alternative bandit.
B PROOF OF COROLLARY 2
- Consistency forces suboptimal-arm pulls to be subpolynomial in expectation and optimal-arm pulls to grow linearly, supporting the lower-bound argument.Source: B PROOF OF COROLLARY 2 · p. 12
- The proof concludes the lower-bound implication by taking the infimum over ε > 0 of c_ε(A, θ).Source: B PROOF OF COROLLARY 2 · p. 12
C PROOF THAT THE GRAM MATRIX IS EVENTUALLY NON-SINGULAR
- If the expected Gram matrix remained singular, an unplayed direction would yield an indistinguishable alternative parameter with linear regret, contradicting consistency.Source: C PROOF THAT THE GRAM MATRIX IS… · p. 12
E PROOF OF LEMMA 13
The proof handles three cases for the empirical sub-optimality gaps after warm-up. Across the cases, it aims to bound success-phase regret logarithmically, with a leading constant depending on θ and A but not on observed samples.
E PROOF OF LEMMA 13
- Case 1 covers a positive empirical gap for the optimal action; the proof selects a suboptimal arm with zero empirical gap in the while loop.The success-phase regret is bounded after the success phase ends for sufficiently large n.Source: E PROOF OF LEMMA 13 · p. 13
- Case 2 covers a zero empirical gap for the optimal action when the minimum estimated gap exceeds Δmin/4.The proof uses the warm-up-based strategy and bounds its success-phase regret for sufficiently large n.Source: E PROOF OF LEMMA 13 · p. 13
- Case 3 covers a zero empirical gap for the optimal action when the minimum estimated gap is at most Δmin/4.The proof introduces a first time step satisfying a condition for every action, then bounds that time by m2 fn.Source: E PROOF OF LEMMA 13 · p. 13
- The three-case argument bounds regret logarithmically, with a leading constant depending on θ and A but not on observed samples.Combining the case bounds yields a constant independent of n and the estimated gaps.Source: E PROOF OF LEMMA 13 · p. 13