Online Learning in Decentralized Multiuser Resource Sharing Problems
This addresses resource allocation problems in decentralized systems like wireless networks or cloud computing, offering a cooperative solution with theoretical guarantees, though it appears incremental in extending regret analysis to more complex models.
The paper tackles decentralized multiuser resource sharing with time-varying, unknown rewards and congestion effects, proposing distributed learning algorithms that achieve logarithmic regret relative to the optimal allocation under i.i.d. and Markovian reward models, as well as communication, computation, and switching costs.
In this paper, we consider the general scenario of resource sharing in a decentralized system when the resource rewards/qualities are time-varying and unknown to the users, and using the same resource by multiple users leads to reduced quality due to resource sharing. Firstly, we consider a user-independent reward model with no communication between the users, where a user gets feedback about the congestion level in the resource it uses. Secondly, we consider user-specific rewards and allow costly communication between the users. The users have a cooperative goal of achieving the highest system utility. There are multiple obstacles in achieving this goal such as the decentralized nature of the system, unknown resource qualities, communication, computation and switching costs. We propose distributed learning algorithms with logarithmic regret with respect to the optimal allocation. Our logarithmic regret result holds under both i.i.d. and Markovian reward models, as well as under communication, computation and switching costs.