Regret Analysis of Stochastic Multi-armed Bandit Problem with Clustered Information Feedback

In this paper, we analyze the regret bound of Multi-armed Bandit (MAB) algorithms under the setting where the payoffs of an arbitrary-size cluster of arms are observable in each round. Compared to the well-studied bandit or full feedback setting, where the payoffs of the selected arm or all the arms are observable, the clustered feedback setting can be viewed as a generalization and a connection. We focus on two most representative MAB algorithms: Upper Confidence Bound and Thompson sampling, and adapt them into the clustered feedback setting. Then, we theoretically derive the regret bound for each of them considering the general type of payoffs (value comes from continuous domains). We show that the regret bounds of these two algorithms with clustered information feedback depend only on the number of clusters. Finally, we simulate both synthetic data and real-world data to compare the performance of these algorithms with different numbers of observable payoffs in each round, the results validate our analysis.