No-regret learning for repeated non-cooperative games with lossy bandits
This paper considers no-regret learning for repeated continuous-kernel games
with lossy bandit feedback. Since it is difficult to give the explicit model of
the utility functions in dynamic environments, the players' action can only be
learned with bandit feedback. Moreover, because of unreliable communication
channels or privacy protection, the bandit feedback may be lost or dropped at
random. Therefore, we study the asynchronous online learning strategy of the
players to adaptively adjust the next actions for minimizing the long-term
regret loss. The paper provides a novel no-regret learning algorithm, called
Online Gradient Descent with lossy bandits (OGD-lb). We first give the regret
analysis for concave games with differentiable and Lipschitz utilities. Then we
show that the action profile converges to a Nash equilibrium with probability 1
when the game is also strictly monotone. We further provide the mean square
convergence rate $\mathcal{O}\left(k^{-2\min\{\beta, 1/6\}}\right)$ when the
game is $\beta-$ strongly monotone. In addition, we extend the algorithm to the
case when the loss probability of the bandit feedback is unknown, and prove its
almost sure convergence to Nash equilibrium for strictly monotone games.
Finally, we take the resource management in fog computing as an application
example, and carry out numerical experiments to empirically demonstrate the
algorithm performance.