From the archives
Maximin Action Identification: A New Bandit Framework for Games
Historical material. Affiliations, schedules and roles on this page describe their original context.
We study an original problem of pure exploration in a strategic bandit model motivated by
Monte Carlo Tree Search. It consists in identifying the best action in a game, when the
player may sample random outcomes of sequentially chosen pairs of actions. We propose two
strategies for the fixed-confidence setting: Maximin-LUCB, based on lower-and
upper-confidence bounds; and Maximin-Racing, which operates by successively eliminating
the sub-optimal actions. We discuss the sample complexity of both methods and compare
their performance empirically. We sketch a lower bound analysis, and possible connections
to an optimal algorithm.
Emilie's presentation at COLT on youtube
