PaperlayerView exact revision on arXiv

Source-linked AI summary

Expected Sample Complexity in Multi-Armed Bandits

Nadav Sukenik, Nadav Merlis

arXiv:2610.09929v1cs.LGstat.ML

TL;DR

Sample-complexity frameworks can be tailored to a suboptimality level or success probability, with fixed-probability guarantees allowing catastrophic failure. This paper introduces expected sample complexity and ACE, proves convergence and regret implications, and finds different instance-dependent rates when ε is known versus unknown.

  • Problem

    Existing sample-complexity guarantees are tailored to a suboptimality level or success probability, and fixed-probability guarantees leave a constant chance of infinitely many suboptimal rounds.

    Source: §1 · p. 1

  • Method

    The paper introduces expected sample complexity under ACE and analyzes deterministic policies and randomized algorithms for known-ε and unknown-ε settings.

    Source: §1 · p. 1, §5 · p. 5

  • Results

    The instance-independent rate is ~Θ(1/ε^2) in both regimes, while instance-dependent rates differ and knowing ε improves expected sample complexity as ε becomes small.

    Source: §6 · p. 8

  • Takeaways & Limitations

    Uniformly bounded expected sample complexity implies almost-sure convergence to the optimal expected reward and explicit expected regret bounds.

    Source: §1 · p. 1

Abstract

from arXiv · show

Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level $\epsilon$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then-$\epsilon$-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in $\epsilon$ and proving a performance separation between the two regimes.

1 INTRODUCTION

The paper introduces expected sample complexity and the ACE framework to address limitations of existing sample-complexity guarantees. It connects uniformly bounded expected sample complexity to almost-sure convergence and expected regret bounds, then studies deterministic and randomized policies across known- and unknown-ε regimes.

1 INTRODUCTION

  • Existing sample-complexity algorithms may be tailored to a particular ε or success probability, with smaller ε potentially causing high regret or infinite sample complexity and failure risking infinitely many suboptimal rounds.Source: §1 · p. 1
  • ACE measures the expected number of rounds in which a policy is expected to act ε-suboptimally over an infinite horizon.The framework is introduced to address existing sample-complexity frameworks’ tailoring to a suboptimality level and probability of success.Source: §1 · p. 1
  • Uniformly bounded expected sample complexity implies almost-sure convergence to the optimal expected reward and yields explicit expected regret bounds.These guarantees contrast with the fixed-probability guarantees of other sample-complexity frameworks.Source: §1 · p. 1
  • Deterministic algorithms cannot have finite expected sample complexity on every Bernoulli-bandit instance, motivating analysis of randomized algorithms.Source: §1 · p. 1
  • For known ε, the paper proposes a successive-elimination–ε-greedy hybrid; for unknown ε, it analyzes Thompson sampling.The upper bounds are complemented by nearly matching lower bounds, and the two regimes have different achievable guarantees.Source: §1 · p. 2

2 RELATED WORK

Related work presents expected regret and PAC sample complexity as established measures in bandits and reinforcement learning. It identifies limited treatment of randomized policies and persistent fixed-probability failure in PAC extensions as gaps addressed by the paper’s framework.

2 RELATED WORK

  • Expected regret measures cumulative reward difference from the best arm, while Thompson sampling is a randomized algorithm with demonstrated empirical performance.Thompson sampling is inspired by Bayesian statistics.Source: §2 · p. 2
  • Sample complexity counts ε-suboptimal interaction rounds over an infinite horizon, and PAC analysis is distinct from best-arm identification.PAC and its extensions are commonly used to analyze the metric (Domingues et al., 2021); best-arm identification instead seeks a near-optimal arm with high probability.Source: §2 · p. 2
  • Prior sample-complexity work largely focused on deterministic algorithms, despite the prevalence of stochastic algorithms such as Thompson sampling and PPO.The paper’s framework distinguishes guarantees available to randomized and deterministic algorithms.Source: §2 · p. 2
  • Uniform-PAC and uniform last-iterate strengthen vanilla PAC guarantees but retain a constant probability of potentially catastrophic failure (Dann et al., 2017; Liu et al., 2024).Source: §2 · p. 2
  • Lenient regret combines regret and sample-complexity notions in a single performance measure (Merlis and Mannor, 2021).Source: §2 · p. 2

3 SETTING

The section establishes the stochastic bandit setting and contrasts expected regret and sample-complexity measures with PAC-style guarantees. It introduces expected sample complexity and the ACE framework for analyzing it.

3.1 Multi-Armed Bandits

  • Each of K arms yields bounded stochastic rewards; the policy selects arms from observed history, and each arm’s mean determines its suboptimality gap.The section also defines the minimum and maximum positive gaps.Source: §3.1 · p. 2

3.2 Expected Regret, Lenient Regret and Sample Complexity

  • Expected regret measures cumulative reward loss, while sample complexity counts rounds when the policy’s expected suboptimality exceeds ε; lenient regret instead concerns realized actions.The policy-gap formulation is presented as useful for deriving convergence, expected-regret, and PAC guarantees.Source: §3.2 · p. 3

3.3 PAC, Uniform-PAC and Uniform Last-Iterate

  • PAC and U-PAC algorithms target a specified ε and confidence δ, leaving performance at smaller ε and constant-probability catastrophic failure as concerns.U-PAC addresses some parameter-specific drawbacks, but still permits catastrophic failure with constant probability; ULI implies U-PAC and inherits its disadvantages.Source: §3.3 · pp. 3–4

3.4 Expected Sample Complexity and the ACE Framework

  • Expected sample complexity counts the expected number of rounds when a policy is expected to act ε-suboptimally over an infinite horizon, and ACE analyzes this measure.U-ACE requires ACE bounds for every ε > 0.Source: §3.4 · p. 4

4 PROPERTIES OF (U-)ACE ALGORITHMS

The section establishes convergence and regret properties of ACE policies, then shows deterministic policies cannot achieve U-ACE across all Bernoulli bandit instances. These findings motivate the focus on stochastic policies.

Convergence

  • ϵ-ACE implies that the policy gap’s limit superior is at most ϵ almost surely; U-ACE therefore yields almost-sure convergence of expected reward to the optimum.The policy sequence itself need not converge, although its expected reward converges to the optimal expected reward.Source: §4 · p. 4

Expected regret

  • For polynomial U-ACE bounds, expected regret is sublinear; when α = 1, the section reports a logarithmic regret bound.The stated general bound assumes mU−ACE(ϵ, ν) ≤ Cνϵ^-α for α > 1.Source: §4 · p. 4

Deterministic-policy impossibility

  • For every deterministic policy with K ≥ 2, some Bernoulli bandit instance gives infinite expected sample complexity, precluding universal U-ACE guarantees.For ϵ below the minimum positive gap, expected sample complexity counts suboptimal-arm plays, linking the impossibility to known lower bounds on those plays.Source: §4 · pp. 4–5

Motivation for stochastic policies

  • The deterministic-policy impossibility and the cited bounds’ inapplicability to stochastic policies motivate analyzing stochastic algorithms, which the section says can combine near-optimal expected regret, U-ACE, and finite PAC bounds.The stated finite (ϵ, δ)-PAC bound applies for all ϵ > 0.Source: §4 · p. 5

5 ALGORITHMS FOR THE ACE FRAMEWORK

The section analyzes ACE sample complexity in two regimes: algorithms that receive ε and algorithms that do not. Their expected sample-complexity guarantees differ, with separate algorithms and lower bounds for each setting.

5 ALGORITHMS FOR THE ACE FRAMEWORK

  • The expected sample-complexity dependence on ε differs between algorithms that receive ε and those that do not.The paper presents this as a separation between non-uniform and uniform algorithms.Source: §5 · p. 5

5.1 Non-Uniform Algorithms

  • SETε-G combines an initial successive-elimination phase with an ε-greedy phase to explore early, then exploit while retaining exploration against misidentification.The algorithm is proposed for the regime where ε is known.Source: §5.1 · p. 5
  • SETε-G is near-optimal in the non-uniform setting, up to logarithmic factors in K and 1/ε.The authors complement its ACE upper bound with an almost-matching lower bound.Source: §5.1 · p. 6
  • When ε is large relative to instance gaps, exploration to ε-accuracy is appropriate; when ε is very small, more aggressive exploration is preferable.Source: §5.1 · p. 6

5.2 Uniform Algorithms

  • Lower bounds show that uniform algorithms retain a polynomial dependence on 1/ε, even without the consistency assumption.The paper describes the bounds as establishing a separation from the non-uniform setting.Source: §5.2 · p. 7
  • Thompson sampling is shown to be U-ACE, and the uniform regime has worse expected sample-complexity bounds than the non-uniform regime.The paper also states that U-ACE yields expected-regret guarantees and almost-sure convergence.Source: §5.2 · p. 7
  • For Thompson sampling, the instance-independent rate in ε is optimal, while its bound matches the lower bound in ε up to logarithmic factors.The authors attribute part of the K factor in the result to a lemma and leave tightening the K-dependence to future work.Source: §5.2 · p. 8

6 CONCLUSIONS AND FUTURE WORK

The paper introduces expected sample complexity and ACE, showing that U-ACE implies expected-regret bounds and almost-sure convergence. It finds different instance-dependent rates for known and unknown ε and identifies further settings for study.

6 CONCLUSIONS AND FUTURE WORK

  • U-ACE guarantees imply expected-regret bounds and almost-sure convergence to the optimal expected reward.Source: §6 · p. 8
  • The instance-independent rate is ~Θ(1/ε^2) whether ε is known or unknown, but the instance-dependent rates differ; for small ε, knowing it in advance improves expected sample complexity.The authors identify this as the first separation result between known-ε and uniform sample-complexity bounds.Source: §6 · p. 8
  • The paper identifies expected sample complexity in other sequential decision problems, including tabular RL and linear bandits, as future directions.Source: §6 · p. 8

AI use statement

  • AI tools assisted some lower-bound derivations, Figure 1 generation, Figure 2 code, proof checking, and paper revision; authors report checking assisted proofs line by line.Source: AI use statement · p. 9

Supplementary Materials

The supplementary material supplies concentration tools and formalizes the interaction model used in the proofs. It then establishes convergence and expected-regret consequences of ACE guarantees.

A.1 Useful Facts

  • A maximal Hoeffding bound controls deviations of an adaptively sampled arm’s empirical mean after at least n draws.It bounds the probability that such a deviation occurs at any time t with N_t ≥ n.Source: §A.1 · p. 12

A.2 Interaction Protocol and Filtrations

  • The interaction protocol makes the policy history-measurable, then reveals internal randomization so the action is determined before its reward is observed.This timing makes A_t measurable with respect to G_{t−1}, giving E[X_t|G_{t−1}] = μ_A_t.Source: §A.2 · p. 13

A.3 The Table Model

  • The table model pre-generates independent reward samples for each arm and uses the next unused sample when that arm is selected.The empirical mean is defined from the first k samples in an arm’s row.Source: §A.3 · p. 13

B.1 Proof of claim 1

  • The proof of Claim 1 uses a per-arm decomposition to relate expected regret to the arm-level quantities in its claim.The supplied proof text says it rewrites expected regret and combines per-arm relations by definition.Source: §B.1 · p. 14

B.2 Proof of Proposition 1

  • An ε-ACE policy satisfies lim sup_t Δ_πt ≤ ε almost surely; the supplementary proof also gives convergence when the guarantee holds for a sequence ε_k = 1/k.The sequence argument yields Pr(lim_t→∞ Δ_πt = 0) = 1.Source: §B.2 · p. 15

B.3 Proof of Claim 2

  • ACE guarantees also yield finite-horizon expected-regret bounds, including a logarithmic bound when α = 1.For α > 1, the stated bound scales as T^(1−1/α); for α = 1, the passage gives R_T(π,ν) ≤ C_ν.Source: §B.3 · p. 16

B.4 Proof of Claim 3

For K ≥ 2, deterministic policies cannot have finite ε-ACE sample complexity on every Bernoulli-bandit instance. The proof covers both consistent and inconsistent policies.

B.4 Proof of Claim 3

  • For any deterministic policy and K ≥ 2, some Bernoulli-bandit instance has infinite expected ε-sample complexity.The proof treats consistent and inconsistent policies separately.Source: §B.4 · p. 17
  • For a consistent policy, the Lai–Robbins lower bound implies diverging regret on an instance with positive minimum gap, hence infinite ε-sample complexity.This argument applies for ε below the minimum gap.Source: §B.4 · p. 17
  • For an inconsistent policy, a sequence of horizons with regret growing at least as cT^p also implies infinite ε-sample complexity.Monotonicity of expected regret extends the divergence to the full horizon sequence.Source: §B.4 · p. 17

C.1 Proof of Theorem 1

The proof analyzes the known-ε explore-then-ε-greedy algorithm in successive-elimination and ε-greedy phases. On a good event, elimination controls which arms remain available and how often suboptimal arms are chosen.

C.1 Proof of Theorem 1

  • The algorithm’s analysis splits expected sample complexity between successive elimination and the ε-greedy phase, with ε known to the algorithm.Each phase is analyzed separately after the elimination stopping round.Source: §C.1 · p. 18
  • On the good event, an optimal arm is never eliminated, while suboptimal arms are eliminated after a number of epochs tied to their gaps.Each suboptimal arm is pulled for at most min{n(Δ_a), n_ε} epochs during elimination.Source: §C.1 · pp. 18–19
  • After elimination on the good event, surviving arms have gap at most ε/4, and eliminated arms do not become empirically best again.Thus the empirical-best arm chosen during the ε-greedy phase has gap at most ε/4.Source: §C.1 · p. 20
  • The ε-greedy analysis combines a uniform bound on choosing a bad arm with a decaying probability bound to sum the sample-complexity tail.The analysis applies to arms with Δ_a > 3ε/4.Source: §C.1 · pp. 21–22

C.2 Technical Lemmas for the Proof of Theorem 1

The technical lemmas establish monotonicity of the confidence radius and a bound used to control sums in the main theorem’s proof.

C.2 Technical Lemmas for the Proof of Theorem 1

  • The confidence radius β_n decreases with n.The proof verifies this by showing the function defining the radius is decreasing for x ≥ 1.Source: §C.2 · p. 23
  • In the cited passage, Lemma 5 assumes 0 < q < 1 and λ ∈ (0, 1]; it does not state a bound or theorem-proof substitution.Source: §C.2 · p. 23

C.3 Proof of Proposition 2

The proofs establish their claims through a two-instance construction, a contradiction with the Lai–Robbins lower bound, and a change-of-measure argument relating infinite-pull events across instances.

C.3 Proof of Proposition 2

  • A fixed policy incurs high expected sample complexity on at least one of two constructed bandit instances.The proof chooses a least-played suboptimal arm on one instance to define the second instance.Source: §C.3 · p. 25

D.1 Proof of Proposition 3

  • The proposed bound contradicts the Lai–Robbins lower bound for sufficiently large horizons, yielding the desired result.The proof considers small ε and derives a contradiction for T greater than a stated threshold.Source: §D.1 · p. 27

D.2 Proof of Proposition 4

  • A change-of-measure lemma transfers the event of infinitely many pulls of arm 2 from ν′ to ν when it occurs almost surely under ν′.The proof uses this implication to argue that at least one of the two instances has infinite expected cumulative policy gap.Source: §D.2 · pp. 28–29

D.3 Proof of Theorem 2

This section proves Theorem 2’s sample-complexity bounds for Algorithm 2, first establishing an instance-dependent upper bound that accounts for conditional policies, the infinite horizon, and multiple optimal arms. It then derives the desired instance-independent bound by maximizing that bound with b = 3K.

D.3 Proof of Theorem 2

  • Unlike regret analysis, expected sample complexity requires tracking the policy’s conditional distribution, and its infinite horizon requires delicate event tracking.Source: §D.3 · p. 30
  • The proof cannot reduce to a unique optimal arm by monotonicity, so it designs events agnostic to both the number of optimal arms and the chosen optimal representative.The passage notes that playing an optimal arm need not conditionally decrease the next-step policy gap.Source: §D.3 · p. 30
  • The proof concludes with the desired instance-dependent upper bound for Algorithm 2’s policy.The argument combines bounds for its component terms and notes that the number of suboptimal arms M is at most K.Source: §D.3 · pp. 30, 38
  • Applying the maximization argument with b = 3K to Theorem 2’s instance-dependent bound yields the desired instance-independent bound.The argument uses that f′′ is negative at x∗, so f is maximized there.Source: §D.3 · p. 39

D.4 Adding an optimal arm can increase the finite-horizon expected sample complexity

The section compares Thompson sampling on two Bernoulli instances, one with a unique optimal arm and one with an additional optimal arm. Simulations show that adding the optimal arm can increase finite-horizon expected sample complexity after enough rounds, which the authors relate to slower posterior concentration.

D.4 Adding an optimal arm can increase the finite-horizon expected sample complexity

  • The comparison uses a two-armed instance with a unique optimal arm and an augmented three-armed instance with two optimal arms; arm 2 is the sole suboptimal arm in both, with gap 1.Source: §D.4 · p. 39
  • Adding an optimal arm can strictly increase expected sample complexity after enough rounds.The figure plots estimated expected sample complexity against rounds for ε = 0.018; the experiment uses 100,000 simulations.Source: Figure 2 · p. 40, §D.4 · p. 40
  • Splitting observations between two optimal arms can slow their individual posterior concentration enough to outweigh the added arm’s direct competition with the suboptimal arm.This is the authors’ intuition for the observed example.Source: §D.4 · p. 40
  • Because the analyzed quantity need not improve monotonically with the number of optimal arms, the authors use an event agnostic to their number and to the choice of optimal representative in Lemma 11.The example illustrates why a point-wise monotonicity reduction used in prior Thompson-sampling analyses is unavailable here.Source: §D.4 · pp. 39–40
Loading 2610.09929v1…