Expected Sample Complexity in Multi-Armed Bandits

TL;DR

The paper introduces expected sample complexity as a performance measure for multi-armed bandits, analyzing it under an approximately correct in expectation (ACE) framework. It establishes that ACE guarantees ensure almost sure convergence to optimal reward and provides tight bounds for both known and unknown suboptimality levels, showing a fundamental gap between deterministic and stochastic algorithms.

Why It Matters

Expected sample complexity offers a more robust performance metric than traditional high-probability bounds, enabling stronger theoretical guarantees for decision-making under uncertainty. This framework improves the understanding of algorithmic behavior in stochastic environments and informs the design of more efficient exploration strategies.

Key Findings

• Deterministic algorithms cannot achieve favorable expected sample complexity bounds, highlighting a fundamental advantage of stochastic methods.
• The paper derives nearly matching lower bounds for both known and unknown suboptimality levels, proving that the proposed algorithms are optimal in terms of ε dependence.