2019/10/21 by Akshayaa Magesh, Venugopal V. Veeravalli, Magesh, Akshayaa +1 · 1 citation
Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.1910.09089
openalex publication_date 2019/10/21 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, i.e., the reward distributions for a given arm are heterogeneous across players. In the case of a collision (when more than one player plays the same arm), we allow for the colliding players to receive non-zero rewards. The time-horizon T for which the arms are played is not known to the players. Within this setup, where the number of players is allowed to be greater than the number of arms, we present a policy that achieves near order-optimal expected regret of order O(log1 + δ T) for some 0 < δ< 1 over a time-horizon of duration T. This paper is accepted at IEEE Transactions on Information Theory.