Online Learning in Decentralized Multiuser Resource Sharing Problems
  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.
