The target of @math -armed bandit problem is to find the global maximum of an unknown stochastic function @math , given a finite budget of @math evaluations. Recently, @math -armed bandits have been widely used in many situations. Many of these applications need to deal with large-scale data sets. To deal with these large-scale data sets, we study a distributed setting of @math -armed bandits, where @math players collaborate to find the maximum of the unknown function. We develop a novel anytime distributed @math -armed bandit algorithm. Compared with prior work on @math -armed bandits, our algorithm uses a quite different searching strategy so as to fit distributed learning scenarios. Our theoretical analysis shows that our distributed algorithm is @math times faster than the classical single-player algorithm. Moreover, the number of communication rounds of our algorithm is only logarithmic in @math . The numerical results show that our method can make effective use of every players to minimize the loss. Thus, our distributed approach is attractive and useful.
The @math -armed bandit problem has been recently intensively studied by many researchers. proposed the Zooming algorithm for solving @math -armed bandits in which payoff function satisfies a Lipschitz condition. Then, presented a tree-based optimization method called HOO. In contrast with the Zooming algorithm, HOO is an anytime algorithm and able to deal with high order smoothness of the objective function. HOO constructs a covering tree to explore the arm space. This structure is also used in many other algorithms in @math -armed bandits, such as the StoSOO algorithm @cite_15 and the HCT algorithm @cite_10 . However, all of these methods are not applicable in the distributed framework.
@cite_15 @cite_10
2115519224 1620761767 2902826155 2949469249
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of @math trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a complete solution for the multi-armed problem in this setting. That is, for every metric space (L,X) we define an isometry invariant Max Min COV(X) which bounds from below the performance of Lipschitz MAB algorithms for @math , and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a solution for the multi-armed bandit problem in this setting. That is, for every metric space we define an isometry invariant which bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback ("best expert") version of the problem, where after every round the payoffs from all arms are revealed. Many real-world problems face the dilemma of choosing best @math out of @math options at a given time instant. This setup can be modelled as combinatorial bandit which chooses @math out of @math arms at each time, with an aim to achieve an efficient tradeoff between exploration and exploitation. This is the first work for combinatorial bandit where the reward received can be a non-linear function of the chosen @math arms. The direct use of multi-armed bandit requires choosing among @math -choose- @math options making the state space large. In this paper, we present a novel algorithm which is computationally efficient and the storage is linear in @math . The proposed algorithm is a divide-and-conquer based strategy, that we call CMAB-SM. Further, the proposed algorithm achieves a regret bound of @math for a time horizon @math , which is sub-linear in all parameters @math , @math , and @math . The evaluation results on different reward functions and arm distribution functions show significantly improved performance as compared to standard multi-armed bandit approach with @math choices. We study exploration in Multi-Armed Bandits in a setting where @math players collaborate in order to identify an @math -optimal arm. Our motivation comes from recent employment of bandit algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the @math players to communicate only once, they are able to learn @math times faster than a single player. That is, distributing learning to @math players gives rise to a factor @math parallel speed-up. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor @math speed-up in learning performance, with communication only logarithmic in @math .