Expected Sample Complexity in Multi-Armed Bandits
A new expected sample-complexity measure for stochastic bandits separates known and unknown suboptimality and rules out deterministic algorithms.
The paper studies sample complexity in stochastic multi-armed bandits through a new expected sample-complexity measure in the approximately correct in expectation (ACE) framework. ACE guarantees imply almost-sure convergence to the optimal expected reward, unlike high-probability guarantees, and convert into explicit expected regret bounds. Deterministic algorithms cannot obtain favorable ACE bounds. For known suboptimality the authors give an explore-then-epsilon-greedy algorithm, and for unknown suboptimality they analyze Thompson sampling, with nearly matching lower bounds that separate the two regimes.
- Defines expected sample complexity under approximately correct in expectation.
- ACE implies almost-sure convergence to the optimal expected reward.
- Deterministic algorithms cannot obtain favorable ACE bounds.
- Known epsilon uses explore-then-epsilon-greedy; unknown epsilon uses Thompson sampling.
- Nearly matching lower bounds separate the known and unknown epsilon regimes.
From the original article
1 min read at arxiv.orgSample 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).
By Nadav Sukenik · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.