PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Complexity of Best Arm Identification in Multi-Armed Bandit Models

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier

arXiv:1407.4443v2stat.MLcs.LG

TL;DR

The paper studies the complexity of identifying the m best arms under fixed-budget and fixed-confidence bandit settings. It develops information-theoretic lower bounds and matching strategies in two-armed models, showing that fixed-budget identification can be easier than fixed-confidence identification when parameters are unknown.

  • Problem

    The paper addresses limited complexity guarantees for identifying the m best arms, especially distribution-dependent lower bounds beyond worst-case results and comparisons between fixed-budget and fixed-confidence settings.

  • Method

    The paper derives lower bounds through a change-of-measure inequality linking expected arm draws to Kullback-Leibler divergences and develops deviation bounds for matching algorithms.

  • Results

    For two-armed models, the paper identifies both complexities in important Gaussian and Bernoulli families and shows that unknown parameters can reverse the usual testing advantage of fixed-confidence procedures.

  • Takeaways & Limitations

    The results establish a generic distribution-dependent fixed-confidence lower bound for m-best-arm identification while leaving fixed-budget complexity for more than two arms substantially open.

  • Takeaways & Limitations

    In Bernoulli models, the fixed-budget algorithm requires the unknown quantity α(θ1, θ2), and no universal strategy with the target guarantee is known.

Abstract

from arXiv · show

The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identifying the m best arms. We introduce generic notions of complexity for the two dominant frameworks considered in the literature: fixed-budget and fixed-confidence settings. In the fixed-confidence setting, we provide the first known distribution-dependent lower bound on the complexity that involves information-theoretic quantities and holds when m is larger than 1 under general assumptions. In the specific case of two armed-bandits, we derive refined lower bounds in both the fixed-confidence and fixed-budget settings, along with matching algorithms for Gaussian and Bernoulli bandit models. These results show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-confidence setting, contradicting the familiar behavior observed when testing fully specified alternatives. In addition, we also provide improved sequential stopping rules that have guaranteed error probabilities and shorter average running times. The proofs rely on two technical results that are of independent interest : a deviation lemma for self-normalized sums (Lemma 19) and a novel change of measure inequality for bandit models (Lemma 1).

1. Introduction

The paper studies the complexity of identifying the m best arms in stochastic bandits across fixed-confidence and fixed-budget settings. It develops information-theoretic lower bounds and matching algorithms, especially for two-armed Gaussian and Bernoulli models, and derives them using new change-of-measure and deviation results.

  • Problem formulation: The goal is to identify the m arms with highest expectations using sampling, stopping, and recommendation rules under a unique m-arm boundary.A bandit has K arms with distributions ν_a and expectations μ_a; uniqueness requires μ_[m] > μ_[m+1].
  • Complexity frameworks: The paper defines fixed-confidence complexity through the expected sample count of δ-PAC strategies and fixed-budget complexity through the exponential decay rate of consistent strategies’ failure probabilities.Heuristically, fixed-confidence sample complexity scales as κC(ν) log 1/δ, while fixed-budget error scales as exp(−κB(ν)t).
  • Fixed-confidence results: The paper provides a distribution-dependent information-theoretic lower bound for fixed-confidence identification when m > 1 and a tighter bound for general two-armed models.The results address a gap beyond the available worst-case lower bound for m > 1.
  • Matching algorithms: For two-armed models, matching strategies are established for Gaussian and Bernoulli bandits, while uniform sampling is shown to be exactly or nearly optimal in specified cases.For Gaussian bandits with known, possibly different variances, an algorithm exactly matches the lower bound; for Bernoulli arms, uniform sampling is nearly optimal in most cases.
  • Fixed-budget results: Fixed-budget complexity differs from fixed-confidence complexity in general: κC(ν) = κB(ν) for Gaussian bandits, whereas κC(ν) > κB(ν) for Bernoulli bandits.The comparison uses lower bounds and matching fixed-budget algorithms for two-armed bandits.
  • Technical foundations: The lower bounds rely on a change-of-measure relation connecting expected arm draws to Kullback–Leibler divergences and on a tight deviation inequality for sub-Gaussian martingales.These results are presented as mathematical contributions of broader interest.

2. Generic Lower Bound in the Fixed-Confidence Setting

The section develops a non-asymptotic, information-theoretic lower bound for fixed-confidence identification of the m best arms, using a new change-of-measure inequality for bandit models. Under identifiable-model and continuity assumptions, the bound applies to any δ-PAC algorithm and yields corresponding complexity lower bounds.

  • Change of measure: A new synthetic change-of-measure inequality directly yields distribution-dependent lower bounds for bandit models.The result generalizes Pinsker’s inequality to bandit models and is used at stopping times.
  • Generic lower bound: Theorem 4 gives a non-asymptotic lower bound on the expected samples required to identify the m best arms when δ ≤ 0.15.It assumes an identifiable class of models whose distribution family satisfies Assumption 3.
  • Generic lower bound: For each top arm a, the expected draw count is bounded using KL(νa, νm+1), while each non-top arm b is bounded using KL(νb, νm).The per-arm bounds contain the factor log(1/2.4δ) and an arbitrarily small additive α before taking α to zero.
  • Generic lower bound: For sufficiently small δ, the lower bound’s right-hand side can be made arbitrarily close to log(1/δ).This provides a tighter form of the inequality in the small-error regime.
  • Extensions: The same change-of-measure technique improves the m = 1 result of Mannor and Tsitsiklis under the stated ϵ-relaxation.The improvement holds for every ϵ > 0 and δ ≤ 0.15.
  • Comparison with KL-LUCB: In canonical one-parameter exponential families, Theorem 4’s lower bound is compared with KL-LUCB’s upper bound to assess the complexity term κC(ν).The family includes Bernoulli distributions and Gaussian distributions with common variances; the comparison also involves Chernoff information.

3. Improved Lower Bounds for Two-Armed Bandits

This section develops a refined, Chernoff-like lower bound for identifying the best arm in two-armed bandits, addressing the mismatch between earlier upper and lower complexity bounds. The bound is tighter for exponential models and shows that uniform sampling can be sub-optimal when arm variances differ.

  • Refined lower bound: Theorem 6 gives a non-asymptotic lower bound on Eν[τ] for every δ-PAC algorithm on an identifiable class of two-armed models.The result applies when µ1 > µ2 and all δ ∈)0, 1].
  • Refined lower bound: The refined bound introduces c∗(ν), a Chernoff-like quantity, and implies κC(ν) ≥1/c∗(ν), with I∗(ν) ≤c∗(ν).The quantities c∗(ν) and I∗(ν) admit explicit expressions for important parametric bandit classes.
  • Uniform sampling: When variances differ, c∗(ν) > I∗(ν), so uniform-sampling strategies are sub-optimal by a factor 1 ≤2(σ2 1 +σ2 2)/(σ1+ σ2)2 ≤2.The comparison identifies a gap between the refined lower bound and the quantity associated with uniform sampling.
  • Comparison with earlier bounds: For two-armed exponential bandit models, Theorem 6’s lower bound on κC(ν) is always tighter than the lower bound of Theorem 4.The two bounds arise from different changes of distribution: Theorem 6 modifies both arms simultaneously, whereas inequality (11) modifies one arm at a time.

4. Matching Algorithms for Two-Armed Bandits

This section presents matching algorithms for two-armed Gaussian and Bernoulli bandits. α-Elimination achieves optimal or near-optimal performance through variance-aware sampling, while SGLRT provides a close-to-optimal Bernoulli procedure with guaranteed δ-PAC behavior.

  • Gaussian bandits: α-Elimination is optimal for Gaussian bandits with known variances and determines the complexity κC(ν).For unequal variances, it uses non-uniform sampling; equal variances admit an improved stopping rule with fewer expected samples.
  • Gaussian bandits: A less conservative exploration rate can preserve the δ-PAC guarantee while stopping earlier than Robbins’ rule.The paper introduces an explicit confidence region based on a new self-normalized deviation inequality, with simulations showing savings in average samples.
  • Gaussian bandits: σ1/(σ1 + σ2) is the optimal asymptotic sampling proportion for arm 1 when Gaussian variances differ.With α = σ1/(σ1 + σ2), α-Elimination is δ-PAC and almost matches the lower bound on Eν[τ] as δ → 0.
  • Bernoulli bandits: For Bernoulli bandits, uniform sampling targets Eν[τ] ≤ log(1/δ)/I∗(ν), because I∗(ν) and c∗(ν) are practically very close.The SGLRT stopping rule is based on the generalized likelihood ratio for testing equality of the two Bernoulli proportions and is δ-PAC.
  • Bernoulli bandits: τ log(1/δ) ≤ (1 + ϵ) I∗(µ1, µ2) a.s. is the stated asymptotic guarantee for SGLRT.The authors conjecture that an exploration rate of order log(log(t)/δ) could also yield a δ-PAC algorithm, supported by numerical experiments.

5. The Fixed-Budget Setting

The section develops fixed-budget complexity bounds, with sharp two-arm comparisons to fixed-confidence complexity and initial lower bounds for more general Gaussian bandits. It also presents static strategies, universal approximations, and limitations for Bernoulli models.

  • The Fixed-Budget Setting: The section introduces new upper and lower bounds on the fixed-budget complexity term κB(ν).These bounds are the central focus of the section.
  • Two-Armed Bandits: For two-armed bandits, matching Gaussian and Bernoulli algorithms show κB(ν) = κC(ν) for Gaussian models but κC(ν) > κB(ν) for Bernoulli models.Theorem 12 supplies analogous lower bounds, while matching algorithms enable the comparison.
  • Two-Armed Bandits: For exponential-family bandits, a static strategy allocating ⌈α(θ1, θ2)t⌉ samples to arm 1 achieves pt(ν) ≤ exp(−tK∗(θ1, θ2)).Consequently, κB(ν) = 1 K∗(θ1, θ2), although the optimal Bernoulli allocation depends on unknown arm means.
  • Two-Armed Bandits: Uniform sampling with empirical best-arm recommendation satisfies pt(ν) ≤ exp(−I∗(ν)t) and approximates the problem-dependent optimum because I∗(ν) is very close to c∗(ν).This provides a simple universal strategy for Bernoulli models, though whether it reaches exp(−K∗(θ1, θ2)t) universally remains unknown.

6. Numerical Experiments

Experiments compare fixed-budget and fixed-confidence identification in two-armed Gaussian and Bernoulli models. They show substantial practical gains from reduced exploration rates and stopping strategies, while fixed-confidence procedures often use about twice as many samples for the same error probability.

  • Gaussian experiments: Figure 5 compares Gaussian models with κC = κB = κ = 8 and κ = 2×104 in fixed-budget and fixed-confidence settings.The models are {N (0.5, 0.25) , N (0, 0.25)} and {N (0.01, 0.25) , N (0, 0.25)}.
  • Gaussian experiments: Three fixed-confidence exploration rates are compared: log(t/δ), log((log(t) + 1)/δ), and log(1/δ).The first is Robbins’ provably-PAC rate; the second is conjectured optimal and almost provably δ-PAC according to Theorem 8.
  • Gaussian experiments: Robbins’ algorithm matches the complexity, but log((log(t)+1)/δ) yields a huge practical reduction in samples.Using β(t, δ) = log(t/δ) produces a threefold increase in average running times on the rightmost Figure 5 plot.
  • Bernoulli experiments: On Bernoulli models, SGLRT nearly matches elimination for 0.51 −0.5 but provides a practical gain for 0.2−0.1.The comparison uses exploration rates log(1/δ) and log((log(t) + 1)/δ), alongside the 1/2-elimination stopping rule.
  • Setting comparison: For the same error probability, fixed-confidence algorithms usually require about twice as many average samples as fixed-budget algorithms.The comparison is between fixed-budget results and the best δ-PAC algorithm, or conjectured δ-PAC SGLRT in the Bernoulli case.

7. Conclusion · Appendix A. Changes of Distributions

The conclusion frames the paper as a principled framework for evaluating best-arm identification and summarizes complete two-arm results alongside a generic lower bound for identifying m best arms. Appendix A establishes the change-of-distribution machinery underlying the key bandit inequalities through likelihood ratios, stopping-time arguments, and a self-normalized bound.

  • 7. Conclusion: The paper’s aim is a principled framework for evaluating fixed-confidence and fixed-budget algorithms that identify the best arm(s).
  • 7. Conclusion: For two-armed bandits, the paper characterizes both settings in important parametric distribution families.Uniform sampling is optimal or nearly optimal for matched-variance Gaussian and Bernoulli distributions, but non-uniform sampling improves performance for distinct Gaussian variances.
  • 7. Conclusion: Fixed-confidence stopping rules based on empirical-mean differences are sub-optimal for Bernoulli distributions.
  • 7. Conclusion: For more than two arms, Theorem 4 gives the first generic distribution-dependent fixed-confidence lower bound for identifying m best arms.The bound does not rely on the sub-Gaussian tail assumption, while existing algorithmic performance bounds leave a small gap.
  • Appendix A. Changes of Distributions: Appendix A relates event probabilities under two mutually absolutely continuous bandit models through the observations’ log-likelihood ratio.The appendix supplies a full proof of Lemma 18 for general changes of distributions, beyond alternatives differing in only one arm.
  • Appendix A. Changes of Distributions: Lemma 19 provides an inequality for the expected log-likelihood ratio at an almost surely finite stopping time, which is used to prove Lemma 1.Its proof handles null and nontrivial events using absolute continuity, Lemma 18, and conditional Jensen’s inequality.
  • Appendix A. Changes of Distributions: The lower-bound proof compares the distributions of the estimated m-best-arm set under models with different optimal-arm sets using a binary testing inequality and KL divergence.It then upper-bounds the KL term through the expected log-likelihood ratio and applies the stopping-time inequality.
  • Appendix A. Changes of Distributions: The appendix derives the likelihood-ratio identity for adaptive bandit observations by induction over rounds and arm-specific i.i.d. samples.The induction uses the common initial action distribution and the recursive decomposition of the log-likelihood ratio when a new arm observation is revealed.

Appendix B. A Short Proof of Burnetas and Katehakis’ Lower Bound on the Regret

The appendix proves Burnetas and Katehakis’ regret lower bound for identifiable bandit classes. The argument compares a model with a unique optimal arm to an alternative where a sub-optimal arm becomes optimal, yielding the Kinf-based sampling constraint.

  • Theorem 21: Theorem 21 states that uniformly efficient algorithms must satisfy the regret lower bound for every model in an identifiable bandit class.The condition is RT(ν) = o(T^α) for every α ∈ (0, 1] whenever ν has a unique optimal arm.
  • Theorem 21: The bound uses Kinf(p; µ), defined as the infimum KL divergence to distributions in P with mean exceeding µ.Kinf(p; µ) = inf {KL(p, q) : q ∈ P and E_X∼q[X] > µ}.
  • Proof: The proof fixes a model where arm 1 is uniquely optimal and constructs an alternative model where arm 2 becomes uniquely optimal.It suffices to establish the inequality for sub-optimal arm a = 2.
  • Proof: A change-of-measure argument analyzes an event that is unlikely under the original model but likely under the alternative, because the optimal arm is sampled extensively in one model and sparingly in the other.The event is combined with Lemma 1 at the almost-sure stopping time σ = T and Markov’s inequality.

Appendix C. Properties of K∗and K∗in Exponential Families

Appendix C characterizes K∗ and K∗ in one-parameter exponential families through divergence geometry and convexity. It establishes an ordering between the associated complexity terms and identifies self-conjugacy of the log-partition function as the condition for equality.

  • Definitions: K∗ and K∗ are defined through equal-Kullback–Leibler-divergence parameters, using K(θ1, θ∗) = K(θ2, θ∗) and K(θ∗, θ1) = K(θ∗, θ2), respectively.The first construction varies the second argument, whereas the second varies the first.
  • Complexity comparison: Convexity implies K∗(θ1, θ2) ≥ 1 K(θ1, θ2) + 1 K(θ2, θ1).Figure 7 geometrically compares the complexity terms appearing in Theorems 4 and 6.
  • Convexity properties: K(θ1, θ2) is twice differentiable and strictly convex in its second argument, with K∗ corresponding to the maximal gap.The maximum is achieved at θ∗ satisfying ˙b(θ∗) = µ∗.
  • Uniform sampling: Uniform sampling yields I∗ equal to the gap at θ = (θ1 + θ2)/2, confirming that I∗ is smaller than K∗(θ1, θ2).The comparison is presented through the gap interpretation in Figure 8.
  • Equality condition: Equality between K∗ and K∗ for all parameter values is achievable only when the log-partition function b is self-conjugate.The appendix also gives the dual mean-parameter representation, where K(µ1, µ2) is twice differentiable and strictly convex in its first argument.

Appendix D. Proof of Theorem 9 · Appendix E. A Refined Exploration Rate for α-Elimination

Appendix D proves δ-PAC correctness and bounds the expected sample complexity of α-elimination using the exploration rate β(t, δ) = log(t/δ) + 2 log log(6t). The proof combines tail bounds, auxiliary inequalities, and Lemma 22, with constants that worsen as the approximation parameter ϵ tends to zero.

  • Appendix D. Proof of Theorem 9: β(t, δ) = log(t/δ) + 2 log log(6t) is used to establish that α-elimination is δ-PAC.The proof assumes µ1 > µ2 and analyzes the stopping time defined through the empirical difference dt.
  • Appendix D. Proof of Theorem 9: The α-elimination error probability is bounded through a series whose convergence is ensured by the selected exploration rate.The displayed bound is distributed across the supplied proof fragments.
  • Appendix D. Proof of Theorem 9: The expected sample complexity is controlled by first bounding the probability that the stopping time τ exceeds a deterministic time T.The subsequent inequality uses a Chernoff bound under a condition involving the mean gap µ1 − µ2.
  • Appendix D. Proof of Theorem 9: The proof derives an upper bound on σ2 and then uses bound (23) to control the relevant stopping-time quantity.The argument proceeds by introducing an upper bound on T ∗.
  • Appendix D. Proof of Theorem 9: For r ∈ [0, e/2 − 1], sufficiently large t satisfy β(t, δ) ≤ log(t^(1+r)/δ), enabling an upper bound on T ∗.This step also invokes bound (23).
  • Appendix D. Proof of Theorem 9: Lemma 22 supplies the auxiliary implication needed to bound the final stopping-time expression.It applies for every β, η > 0 and s ∈ [1, e/2].
  • Appendix D. Proof of Theorem 9: Applying Lemma 22 with η = δ, s = 1 + r, and β = (1 − γ)^3(µ1 − µ2)^2/(2(σ1 + σ2)^2) yields the stated bound.The proof introduces the factor R(µ1, µ2, σ1, σ2, γ, r) = 1 + r (1 − γ)^3.
  • Appendix D. Proof of Theorem 9: For fixed ϵ > 0, choosing r and γ sufficiently small gives a bound with constant C independent of δ, while C diverges as ϵ tends to zero.The proof then concludes Theorem 9; the supplied passages contain no separate text labeled Appendix E.

E.1 Proof of Theorem 8 · E.2 Proof of Lemma 7. · Appendix F. Bernoulli Bandit Models

The appendices establish Theorem 8 and Lemma 7 through technical probability arguments involving Gaussian sums, subgaussian super-martingales, geometric time blocks, and parameter choices. No passage supplied here provides substantive content for Appendix F on Bernoulli bandit models.

  • E.1 Proof of Theorem 8: The proof of Theorem 8 reduces to establishing the bound specified after equation (15).The reduction is stated directly as the proof’s starting point.
  • E.1 Proof of Theorem 8: The argument uses that sums of independent standard normal variables are Gaussian.This identifies the distributional fact invoked in the proof.
  • E.1 Proof of Theorem 8: Setting z = log(1/δ), the proof applies Lemma 7 with x = z + 3 log z and β = 3/2.These parameter choices connect the theorem proof to the bound supplied by Lemma 7.
  • E.2 Proof of Lemma 7.: The proof of Lemma 7 begins by stating three technical lemmas, with some proofs partly omitted.The supplied passage explicitly characterizes the supporting lemmas and their presentation.
  • E.2 Proof of Lemma 7.: Lemmas 23 and 25 analyze times satisfying (1 + η)k−1 ≤ t ≤ (1 + η)k, with Lemma 25 then proved using Lemma 23.The passages identify the geometric time-block condition and the dependency between the lemmas.
  • E.2 Proof of Lemma 7.: For σ-subgaussian variables, W_t = exp(λS_t − tλ^2σ^2/2) is a super-martingale, enabling a bound for every positive u.The super-martingale property is the key probabilistic tool highlighted in the proof.
  • E.2 Proof of Lemma 7.: The proof defines η ∈ (0, e−1], z_k = x + β log(k log(1 + η)), and λ_k, then chooses η^2 = 8/x under x ≥ 8(e−1)^2.The resulting exponential bound uses A(η), its lower bound from Lemma 24, and A(η) ≤ 1.
  • E.2 Proof of Lemma 7.: The final step combines the lower bound on A(η) from Lemma 24 with the upper bound A(η) ≤ 1.The supplied fragment also records an intermediate expression ending in “2 + 1”.

F.1 Proof of Lemma 11 · F.2 An Asymptotic Bound for the Stopping Time · Appendix G. Upper and Lower Bounds in the Fixed-Budget Setting

The supplied passages establish that KL-LUCB’s confidence-interval stopping rule achieves error probability at most δ, while a separate asymptotic argument gives a high-probability finite stopping-time bound under regularity conditions.

  • F.1 Proof of Lemma 11: KL-LUCB samples both arms uniformly and constructs KL-divergence confidence intervals before selecting the empirical best arm.The intervals use an exploration rate ˜β(t, δ), and stopping occurs when the intervals become separated.
  • F.1 Proof of Lemma 11: The algorithm stops when either arm’s lower confidence bound exceeds the other arm’s upper confidence bound.The recommendation is the empirical best arm at stopping.
  • F.1 Proof of Lemma 11: The error event is bounded by the union of deviations in which one lower confidence bound exceeds its mean or one upper confidence bound falls below its mean.The proof applies an event decomposition and a union bound.
  • F.1 Proof of Lemma 11: δ bounds the final error probability when the exploration rate is set to ˜β(s, δ) = β(2s, δ)/2.The chosen β(t, δ) makes the resulting deviation series at most δ.
  • F.2 An Asymptotic Bound for the Stopping Time: Under uniform sampling and a stopping rule based on continuous f with f(µ1, µ2) ≠ 0 and g(t) = o(t^r) for all r > 0, the stopping time is almost surely finite.The law of large numbers yields P(σ < +∞) = 1.
  • F.2 An Asymptotic Bound for the Stopping Time: For every α ∈ (0, 1), there exists N(ϵ, α, µ1, µ2) such that P(σ ≤ N(ϵ, α, µ1, µ2)) ≥ 1 − α.This follows from almost-sure finiteness of σ and convergence of P(σ ≤ n) to 1.
  • F.2 An Asymptotic Bound for the Stopping Time: A constant C(ϵ, µ1, µ2) independent of δ bounds the remaining term in the stopping-time argument.The bound is obtained using Lemma 22.

G.1 Proof of Theorem 12 · G.2 An Optimal Static Strategy for Exponential Families · G.3 Proof of Theorem 17

These sections prove Theorem 12 via a change-of-measure argument, characterize optimal static sampling in exponential families, and establish Theorem 17 by constructing alternatives that exchange good and bad arms. The results connect error probabilities and KL divergences to sampling allocations and complexity bounds.

  • G.1 Proof of Theorem 12: Theorem 12 applies a change-of-measure inequality at a fixed stopping time to relate the two models’ error probabilities to expected arm pulls and KL divergences.The event is the recommendation of arm 1 under a model whose best arm is 1, while the alternative model’s best arm is 2.
  • G.1 Proof of Theorem 12: Correctness on both models makes the error probabilities asymptotically separated, yielding the theorem’s lower-bound expression after taking a limsup and letting ϵ approach zero.The proof uses Pν′(A) ≤ ϵ ≤ Pν(A) for all sufficiently large t and then optimizes over alternatives with 1 < µ′2.
  • G.2 An Optimal Static Strategy for Exponential Families: For exponential families, the static strategy’s error exponent is governed by gα(θ1, θ2), a weighted sum of KL divergences at the mixture parameter αθ1 + (1 −α)θ2.Here α = n1/(n1+n2), and gα(θ1, θ2) := αK(αθ1 + (1 −α)θ2, θ1) + (1 −α)K(αθ1 + (1 −α)θ2, θ2).
  • G.2 An Optimal Static Strategy for Exponential Families: The maximizing allocation is α∗ = (θ∗−θ2)/(θ1 −θ2), where θ∗ equalizes the two KL divergences at K∗(θ1, θ2).The defining condition is K(θ∗, θ1) = K(θ∗, θ2) = K∗(θ1, θ2).
  • G.2 An Optimal Static Strategy for Exponential Families: Uniform sampling with n1 = n2 = t/2 and recommending the empirical best arm matches the lower bound (17) in Theorem 12.This conclusion is stated for the case µ1 > µ2.
  • G.3 Proof of Theorem 17: Theorem 17 begins by identifying an arm with Eν[Na(t)] ≤ 2σ2t/(H(ν)∆2a), then separates the argument according to whether that arm is good or bad.Case 1 finds a bad arm b with Eν[Nb(t)] ≤ 2σ2t H−(ν)∆2, while Case 2 finds a good arm b with Eν[Nb(t)] ≤ 2σ2t H+(ν)∆2.
  • G.3 Proof of Theorem 17: The proof changes only the less-drawn good and bad arms to form a Gaussian alternative in which their status is exchanged, while ensuring H(ν[a,b]) ≤ H(ν).The original and alternative models have different optimal arms, allowing Lemma 15 to be applied.
Loading 1407.4443v2…