Expected sample complexity reveals limits in multi-armed bandit learning

Expected Sample Complexity in Multi-Armed Bandits

Machine Learning

Summary

Choosing the best option from many uncertain choices is a common problem in fields like recommendation systems and online advertising. This paper studies how many wrong choices, on average, a decision-making agent makes while learning to pick the best option, introducing a new way to measure this expected number of errors. The authors show how this measure guarantees the agent will almost surely learn the best choice and compare different algorithms under this framework, highlighting differences between algorithms that know how close they want to get to the best and those that don't. Their results also provide lower bounds showing the limits of how efficiently this learning can be done.

What this means in practice

  • For machine learning engineers: Use new expected sample complexity bounds to evaluate and choose bandit algorithms that balance exploration and exploitation with known or unknown error tolerance.
  • For online advertising teams: Apply insights about algorithm performance limits to design ad selection systems with predictable learning behavior over time.

A theory result. No direct application yet.

Authors

Nadav Sukenik, Nadav Merlis

Abstract

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 $ε$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then-$ε$-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 $ε$ and proving a performance separation between the two regimes.
View PDFOpen arXiv