11 March 2014 in IEEE Transactions on Information Theory
We consider the problem of distributed online learning with multiple players in multiarmed bandit (MAB) models. Each player can pick among multiple arms. When a player picks an arm, it gets a reward. We consider both independent identically distributed (i.i.d.) reward model and Markovian reward model. In the i.i.d. model, each arm is modeled as an i.i.d. process with an unknown distribution with an unknown mean. In the Markovian model, each arm is modeled as a finite, irreducible, aperiodic and reversible Markov chain with an unknown probability transition matrix and stationary distribution. The arms give different rewards to different players. If two players pick the same arm, there is a collision, and neither of them get any reward. There is no dedicated control channel for coordination or communication among the players. Any other communication between the users is costly and will add to the regret. We propose an online index-based distributed learning policy called dUCB4 algorithm that trades off exploration versus exploitation in the right way, and achieves expected regret that grows at most as near- O(log2T). The motivation comes from opportunistic spectrum access by multiple secondary users in cognitive radio networks wherein they must pick among various wireless channels that look different to different users. This is the first distributed learning algorithm for multiplayer MABs with heterogeneous players (that have player-dependent rewards) to the best of our knowledge.
2 December 2016 in IEEE Transactions on Control of Network Systems
We consider the problem of learning in single-player and multiplayer multi-armed bandit models. Bandit problems are classes of online learning problems that capture exploration versus exploitation tradeoffs. In a multi-armed 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) (and O(log T) under some assumption). It is well known that O(log T) 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(log2 T). 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.
24 December 2010 in Discrete Event Dynamic Systems
25 November 2014 in Queueing Systems
19 December 2016 in IEEE Transactions on Control of Network Systems
We consider optimal control of decentralized LQG problems for plants having nested subsystems controlled by two players with asymmetric information sharing patterns between them. In the main scenario, the players are assumed to have a unidirectional error-free, unlimited-rate communication channel with a unit delay in one direction and no communication in the other. A second model, presented for completeness, considers a channel with no delay in one direction and a unit delay in the other. Delayed information-sharing patterns do not, in general, admit linear optimal control laws and are thus difficult to control optimally. However, in these scenarios, we show that the problems have a partially nested information structure and, thus, linear optimal control laws exist. Summary statistics are identified and analytical solutions to the optimal control laws are derived. State and output feedback cases are solved for both scenarios.
28 October 2019 in IEEE Transactions on Automatic Control