Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

Abstract

We study the real-valued combinatorial pure exploration of the multi-armed bandit (R-CPE-MAB) problem. In R-CPE-MAB, a player is given d stochastic arms, and the reward of each arm s\1, , d\ follows an unknown distribution with mean _s. In each time step, a player pulls a single arm and observes its reward. The player's goal is to identify the optimal action ^* = _ A ^ from a finite-sized real-valued action set A R^d with as few arm pulls as possible. Previous methods in the R-CPE-MAB assume that the size of the action set A is polynomial in d. We introduce an algorithm named the Generalized Thompson Sampling Explore (GenTS-Explore) algorithm, which is the first algorithm that can work even when the size of the action set is exponentially large in d. We also introduce a novel problem-dependent sample complexity lower bound of the R-CPE-MAB problem, and show that the GenTS-Explore algorithm achieves the optimal sample complexity up to a problem-dependent constant factor.

Tasks

Reproductions