PaperlayerView exact revision on arXiv

Source-linked AI summary

Best-Arm Identification in Linear Bandits

Marta Soare, Alessandro Lazaric, Rémi Munos

arXiv:1409.6110v2cs.LG

TL;DR

The paper asks how to identify the best arm with fixed confidence in a linear bandit while minimizing samples. It characterizes complexity and develops allocation strategies that exploit global linear structure, finding direction-focused sampling and connections to G-optimal experimental design.

  • Problem

    The paper studies fixed-confidence best-arm identification when arm rewards depend linearly on an unknown parameter, where sampling can inform rewards of other arms.

  • Method

    It characterizes complexity through optimal designs and develops G, XY, and adaptive allocation strategies that target uncertainty in relevant arm-difference directions.

  • Results

    The analysis shows that linear complexity incorporates gap structure and arm correlations, reduces to a quantity comparable to HMAB for canonical-basis arms, and connects G-allocation to G-optimality.

  • Takeaways & Limitations

    Best-arm identification can exploit global linear structure by sampling informative arms to improve estimates of near-optimal arms rather than estimating every arm uniformly.

  • Takeaways & Limitations

    The model assumes a finite arm set, bounded arm norms, bounded noise, and a positive minimum gap; adaptive allocation analysis also incurs a cost for discarding suboptimal directions.

Abstract

from arXiv · show

We study the best-arm identification problem in linear bandit, where the rewards of the arms depend linearly on an unknown parameter $θ^*$ and the objective is to return the arm with the largest reward. We characterize the complexity of the problem and introduce sample allocation strategies that pull arms to identify the best arm with a fixed confidence, while minimizing the sample budget. In particular, we show the importance of exploiting the global linear structure to improve the estimate of the reward of near-optimal arms. We analyze the proposed strategies and compare their empirical performance. Finally, as a by-product of our analysis, we point out the connection to the $G$-optimality criterion used in optimal experimental design.

1 Introduction

The paper studies pure-exploration best-arm identification in stochastic linear bandits, where observations inform estimates of multiple arms through an unknown linear parameter. This global structure changes sampling: even sub-optimal arms can help distinguish near-optimal candidates.

  • 1 Introduction: The paper focuses on pure exploration, where the learner allocates a limited budget to identify the best arm rather than maximize cumulative reward.
  • 1 Introduction: Linear bandits replace separate mean-reward estimation with estimation of the d features of θ*, allowing one pull to inform other arms.An arm’s expected reward is a linear combination of its features and the unknown parameter.
  • 1 Introduction: Unlike MAB strategies, linear-bandit strategies may sample a sub-optimal arm because it provides information about θ* useful for discriminating near-optimal arms.After most arms are discarded, MAB concentrates on the remaining candidates, whereas a linear-bandit strategy can seek informative arms elsewhere in X.

2 Preliminaries

The paper formalizes a finite linear-bandit model with bounded arms, bounded noise, and a unique best arm separated by a positive minimum gap. It defines fixed-confidence best-arm identification and introduces least-squares tools for controlling prediction errors under fixed or adaptive allocations.

  • 2 Preliminaries: Arms x ∈ X have expected rewards x⊤θ* and bounded ℓ2-norm L, while observed rewards add zero-mean i.i.d. noise bounded in [−σ; σ].The best arm maximizes x⊤θ*, and the minimum gap satisfies ∆min > 0.
  • 2 Preliminaries: The (ǫ, δ)-best-arm identification objective is to return an arm with simple regret at most ǫ with probability at least 1−δ while minimizing steps; the paper focuses on ǫ = 0.The analysis provides high-probability sample-complexity bounds.
  • 2 Preliminaries: In MAB, best-arm-identification complexity is characterized by inverse pairwise gaps, with HMAB determining error probability in fixed-budget settings and sample complexity in fixed-confidence settings.
  • 2 Preliminaries: Ordinary least squares estimates θ* from observed arm-reward pairs, and concentration inequalities provide high-probability prediction-error bounds.Adaptive allocations require a different high-probability bound from the one for fixed sequences.
  • 2 Preliminaries: A design λ records pull proportions over X, with design matrix Λλ = P_x∈X λ(x)xx⊤; an allocation induces λ through empirical pull frequencies.The allocation design matrix satisfies A_xn = nΛ_λxn.

3 The Complexity of the Linear Best-Arm Identification Problem

The paper defines linear best-arm-identification complexity through an optimal allocation that shrinks a confidence set into the cone where the true best arm is optimal. This complexity incorporates both reward gaps and geometric correlations among arm-difference directions.

  • The Complexity of the Linear Best-Arm Identification Problem: The proposed complexity extends MAB complexity by evaluating the best allocation through an oracle with access to θ*.
  • The Complexity of the Linear Best-Arm Identification Problem: Each arm’s optimality region C(x) is an intersection of half-spaces, and the regions partition parameter space into cones.The cone C(x*) contains parameters for which x* is optimal.
  • The Complexity of the Linear Best-Arm Identification Problem: The oracle stops when the confidence set S*(xn) is contained in C(x*), because then all plausible parameter estimates select the true optimal arm.Overlap with multiple cones represents ambiguity among possible optimal arms.
  • The Complexity of the Linear Best-Arm Identification Problem: The oracle allocation minimizes the number of pulls needed to shrink uncertainty along optimal-arm difference directions below their corresponding gaps.It targets directions in Y* rather than seeking a uniformly accurate estimate of θ*.
  • The Complexity of the Linear Best-Arm Identification Problem: HLB is defined by an optimal design minimizing the maximum gap-normalized uncertainty over Y*, thereby combining inverse squared gaps with correlations among arms.For canonical-basis arms, HMAB ≤ HLB ≤ 2HMAB.
  • The Complexity of the Linear Best-Arm Identification Problem: The resulting oracle sample complexity is N* = c^2HLB log_n(K^2/δ), while ∆min and the geometry of X determine the problem-dependent scale.The numerator can depend on dimensionality, arm norms, and the norms of optimal-arm directions.

4 Static Allocation Strategies

The practical static strategies replace the unavailable oracle allocation with computable confidence-set stopping and two fixed allocations. G-allocation targets uniform accuracy over arms, while XY-allocation focuses estimation on pairwise directions relevant to identifying the best arm.

  • Practical stopping: The oracle cannot be implemented because θ^*, the gaps, and the relevant directions are unknown; practical algorithms therefore use empirical stopping and static allocations.The empirical criterion tests whether a computable confidence set lies inside one arm's optimality cone.
  • Practical stopping: Static strategies stop when the empirical confidence set is contained in a single optimality cone, certifying one returned best arm.This replaces the oracle's confidence-set condition with a sample-based criterion centered on the OLS estimate.
  • G-allocation: G-allocation minimizes a worst-case prediction-error bound, producing uniform estimation accuracy over all arms in X.Its formulation coincides with the G-optimal design criterion from optimal experimental design.
  • G-allocation: G-allocation is worst-case optimal up to constants, even though it is completely static.The theorem applies when the allocation is implemented with a β-approximate method and the empirical stopping condition is used.
  • XY-allocation: XY-allocation directly reduces uncertainty in pairwise directions Y, making it a transductive variant of G-optimal design.Unlike G-allocation, it targets the empirical gaps required by the stopping condition rather than all arm predictions uniformly.
  • XY-allocation: XY-allocation may be arbitrarily better than G-allocation because it targets the stopping condition more directly.The comparison is stated as a possible instance-dependent advantage, not as a universal improvement.

5 XY-Adaptive Allocation Strategy

XY-Adaptive alternates between eliminating dominated arms and reallocating samples toward directions involving the remaining potentially optimal arms. Its complexity reflects both oracle identification difficulty and the cost of discarding suboptimal directions.

  • Algorithm: A dominated arm is removed when another arm is certified to outperform it under the empirical confidence analysis.The remaining non-dominated arms define the directions that still require accurate estimation.
  • Algorithm: XY-Adaptive runs in phases, using prior samples to remove dominated arms and define directions for the next static allocation.The phase structure preserves the validity of fixed-allocation concentration bounds within each phase.
  • Phase scheduling: Phase lengths are chosen so uncertainty over active directions reaches a fraction α of the previous iteration's performance.This length can be computed before a phase begins from the active directions and prior allocation uncertainty.
  • Sample complexity: XY-Adaptive's sample complexity scales with the maximum of oracle complexity N^* and the cost M^* of discarding suboptimal directions.Unlike G and XY, it has no direct dependence on d or Δ_min outside the logarithmic term.
  • Sample complexity: The adaptive strategy can approach oracle performance when discarding suboptimal directions costs less than identifying the best arm.The stated bound includes a multiplicative factor 16/α in this regime.

6 Numerical Simulations

The simulations compare XY-Adaptive with oracle, static, and fully adaptive alternatives across dimensions. XY-Adaptive quickly focuses on the informative direction and gains increasing budget advantages over static allocations as dimension grows.

  • Experimental setup: The experiments compare XY-Adaptive with XY-Oracle, XY, G, and fully adaptive XY at confidence δ = 0.05.Sampling budgets are averaged over 100 runs for d = 2 . . . 10.
  • Results: XY-Adaptive identifies the most important direction after few phases and produces an allocation that mimics the oracle.The reported behavior concerns shrinking uncertainty in the direction ỹ.
  • Results: Static XY and G treat all directions as equally important, so they continue sampling until uncertainty is below Δ_min in every direction.This contrasts with XY-Adaptive's gap-sensitive focus.
  • Results: As dimension increases, the budget difference between XY-Adaptive and static strategies increases.Additional dimensions have little to no impact on XY-Oracle and XY-Adaptive because the important direction remains ỹ.

7 Conclusions

The paper develops linear-bandit best-arm identification strategies and connects their complexity to optimal experimental design and the multi-armed bandit setting. Its XY-Adaptive strategy avoids the dimensionality disadvantage observed for static allocations in the reported experiment.

  • The study characterizes fixed-confidence best-arm identification complexity in linear bandits and connects it to complexity in the multi-armed bandits setting.
  • The G-allocation strategy connects linear-bandit sampling to the G-optimality criterion from optimal experimental design.
  • The XY-allocation introduces an optimal-design problem whose testing arms differ from the arms selected for sampling.
  • XY-Adaptive learns from previous observations without suffering from the dimensionality of the problem, unlike the limitations identified for fully adaptive allocation.

B Proofs

These proofs establish the equivalence-theorem machinery, bound the relevant design quantities through eigenvalue arguments, and recover the standard multi-armed-bandit complexity as a special case.

  • The Kiefer-Wolfowitz equivalence theorem makes three statements about the design criterion equivalent.
  • The proof decomposes the positive-definite design matrix into eigenvalues and bounds its largest eigenvalue using the arms’ squared norms.
  • When arms are canonical basis vectors, the design matrix is diagonal, reducing the linear-bandit analysis to coordinate-wise allocations.
  • The resulting complexity satisfies HMAB ≤ HLB ≤ 2HMAB, showing coherence with existing multi-armed-bandit results.

B.2 Proofs of Theorem 1 and Theorem 2

The theorem proofs derive stopping guarantees by combining confidence events with uncertainty bounds for the G-allocation, then apply the same proof pattern to the second theorem.

  • Theorem 1: The proof of Theorem 1 uses the empirical stopping condition together with the G-allocation uncertainty measure ρG(λ).
  • Theorem 1: A sufficient stopping condition must hold for every arm, yielding an accuracy requirement for the G-allocation.
  • Theorem 1: The bound ρ˜G_n ≤ (1 + β)d determines the accuracy level required before stopping and gives the stated guarantee after inversion.
  • Theorem 2: The proof of Theorem 2 follows the same steps as the proof of Theorem 1.

C Implementation of the Allocation Strategies

The allocation strategies are implemented through continuous optimization or greedy rules followed by efficient rounding, with guarantees on monotonicity, support size, and approximation accuracy.

  • The efficient rounding procedure: The rounding procedure first assigns support-arm frequencies using ceiling operations, then adjusts frequencies until the total allocation equals n.
  • The efficient rounding procedure: The rounding procedure produces a monotonic allocation: moving from n to n + 1 increases only one arm’s pull count by one.
  • Implementation of the G-allocation: The G-allocation can be obtained by optimizing a continuous relaxation and then converting the design into a discrete allocation.
  • Approximation guarantees: The optimal design support has at most d(d + 1)/2 + 1 points when d linearly independent arms are available.
  • Approximation guarantees: Caratheodory’s theorem gives the same support bound for any design because symmetric design matrices are described by d(d + 1)/2 elements.
  • Implementation of the XY-allocation: XY-allocation is NP-hard, so the paper proposes continuous relaxation with rounding or an incremental greedy algorithm for approximate computation.
  • Implementation of XY-adaptive allocation: The XY-adaptive allocation rule coincides with the XY-allocation and inherits its properties.

D Proof of Theorem 3

The proof bounds phase lengths by combining stopping conditions, confidence-set arguments, and allocation-design properties. It also shows that discarded arms cannot remain optimal.

  • Allocation analysis: The analysis uses soft allocations and optimal designs to relate discrete pulls, confidence performance, and sample-complexity bounds.The proof introduces design-based performance quantities and applies the optimal designs defined in Eq. 29.
  • Phase-length bound: Each phase has length bounded by max{M*, 16…}, as stated in Lemma 8.The supplied passage gives the lemma’s bound in truncated form.
  • Phase-length bound: The proof establishes nj ≤ M* in the case where the confidence-set overlap has been eliminated.This follows from the contradiction argument preceding the displayed conclusion.
  • Discarding directions: At n = nj, all directions in Y − Y* have been discarded, leaving bYj ⊆ Y*.The estimation error is sufficiently small for the remaining directions to be restricted to Y*.
  • Eliminating arms: For an unresolved arm x, the proof derives that x is dominated by another arm x′, so x cannot be optimal.This conclusion is obtained from the phase conditions and the non-triggered discarding condition.

E Additional Empirical Results

The additional experiment compares allocation budgets and arm-wise sampling in a five-dimensional linear-bandit instance. Adaptive strategies focus on the most informative direction, while global information sharing reduces uncertainty across directions.

  • Sample allocation: In X ⊆ R5, XY-oracle and XY-adaptive concentrate most samples on arm x2, the most informative direction.XY and G instead allocate samples uniformly over the canonical arms.
  • Sample complexity: Fully-adaptive identifies x2 but retains dimension-linear sample complexity because of an extra d term, canceling its advantage over static strategies.The comparison concerns the bound’s dimension dependence and the resulting budget advantage.
  • Sample complexity: XY-adaptive learns the gaps and allocates samples similarly to XY-oracle without a large sampling-budget loss.Its complexity nevertheless includes the cost of phase re-initializations.
  • Global information: Multiple observations across directions provide mutual information, so each canonical arm can receive fewer pulls than XY-oracle assigns to x2.This shared information reduces overall confidence-set uncertainty.
Loading 1409.6110v2…