No-regret learning for repeated non-cooperative games with lossy bandits
This work addresses the challenge of learning in dynamic environments with unreliable feedback for applications like fog computing, representing an incremental advance by extending existing methods to handle lossy bandits.
The paper tackles the problem of no-regret learning in repeated non-cooperative games with lossy bandit feedback, where utility functions are unknown and feedback may be randomly lost, by proposing the OGD-lb algorithm. It proves convergence to Nash equilibrium with probability 1 for strictly monotone games and provides a mean square convergence rate of O(k^{-2min{β, 1/6}}) for β-strongly monotone games, with empirical validation in fog computing resource management.
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\{β, 1/6\}}\right)$ when the game is $β-$ 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.