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

2023/08/20 by Nakamura, Shintaro, Sugiyama, Masashi
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2308.10238

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 \boldsymbolπ^* = \argmax_{\boldsymbolπ ∈ A} \boldsymbolμ^\top\boldsymbolπ from a finite-sized real-valued action set A⊂ ℝ^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.

Related

• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
• Thompson Sampling for (Combinatorial) Pure Exploration
• Thompson Sampling for Combinatorial Semi-Bandits
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• Optimal Exploration is no harder than Thompson Sampling