  How can non-communicating agents learn to share congested resources
efficiently? This is a challenging task when the agents can access the same
resource simultaneously (in contrast to multi-agent multi-armed bandit
problems) and the resource valuations differ among agents. We present a fully
distributed algorithm for learning to share in congested environments and prove
that the agents' regret with respect to the optimal allocation is
poly-logarithmic in the time horizon. Performance in the non-asymptotic regime
is illustrated in numerical simulations. The distributed algorithm has
applications in cloud computing and spectrum sharing. Keywords: Distributed
learning, congestion games, poly-logarithmic regret.
