Pure Exploration Bandit Problem with General Reward Functions Depending on Full Distributions
This addresses a theoretical limitation in bandit algorithms for applications requiring full distribution information, though it appears incremental in extending existing frameworks.
The paper tackles the pure exploration bandit problem where reward functions depend on entire distributions rather than just means, adapting racing and LUCB frameworks to design algorithms with correctness guarantees and sample complexity upper bounds.
In this paper, we study the pure exploration bandit model on general distribution functions, which means that the reward function of each arm depends on the whole distribution, not only its mean. We adapt the racing framework and LUCB framework to solve this problem, and design algorithms for estimating the value of the reward functions with different types of distributions. Then we show that our estimation methods have correctness guarantee with proper parameters, and obtain sample complexity upper bounds for them. Finally, we discuss about some important applications and their corresponding solutions under our learning framework.