On regret-optimal learning in decentralized multiplayer multiarmed bandits

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Naumaan Nayyar, Dileep Kalathil, Rahul Jain
Journal/Conference Name IEEE Transactions on Control of Network Systems
Paper Category
Paper Abstract We consider the problem of learning in single-player and multiplayer multiarmed bandit models. Bandit problems are classes of online learning problems that capture exploration versus exploitation tradeoffs. In a multiarmed bandit model, players can pick among many arms, and each play of an arm generates an i.i.d. reward from an unknown distribution. The objective is to design a policy that maximizes the expected reward over a time horizon for a single player setting and the sum of expected rewards for the multiplayer setting. In the multiplayer setting, arms may give different rewards to different players. There is no separate channel for coordination among the players. Any attempt at communication is costly and adds to regret. We propose two decentralizable policies, E3 (E-cubed) and E3-TS, that can be used in both single player and multiplayer settings. These policies are shown to yield expected regret that grows at most as O(log1+ϵT). It is well known that logT is the lower bound on the rate of growth of regret even in a centralized case. The proposed algorithms improve on prior work where regret grew at O(log2T). More fundamentally, these policies address the question of additional cost incurred in decentralized online learning, suggesting that there is at most an ϵ-factor cost in terms of order of regret. This solves a problem of relevance in many domains and had been open for a while.
Date of publication 2016
Code Programming Language MATLAB
Comment

Copyright Researcher 2022