# No-regret learning for repeated non-cooperative games with lossy bandits

arXiv: https://arxiv.org/abs/2205.06968 · HTML: https://mlsanity.com/paper/2205.06968/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 14 May 2022.

## Builds on (most cited first, 22 of 22)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control](https://mlsanity.com/paper/2006.10820/) (2020)
- [Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1912.03719/) (2019)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [Distributed Online Linear Regression](https://mlsanity.com/paper/1902.04774/) (2019)
- [Learning with minimal information in continuous games](https://mlsanity.com/paper/1806.11506/) (2018)
- [Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization](https://mlsanity.com/paper/1610.04702/) (2016)
- [Personalized Optimization with User's Feedback](https://mlsanity.com/paper/1905.00775/) (2019)
- [No-regret Learning in Cournot Games](https://mlsanity.com/paper/1906.06612/) (2019)
- [Continuous-time Discounted Mirror-Descent Dynamics in Monotone Concave Games](https://mlsanity.com/paper/1912.03460/) (2019)
- [Decentralized Learning for Channel Allocation in IoT Networks over Unlicensed Bandwidth as a Contextual Multi-player Multi-armed Bandit Game](https://mlsanity.com/paper/2003.13314/) (2020)
- [A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods](https://mlsanity.com/paper/1703.05388/) (2017)
- [Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1707.01965/) (2017)
- [Predictive Online Convex Optimization](https://mlsanity.com/paper/1905.06263/) (2019)
- [Stochastic generalized Nash equilibrium seeking in merely monotone games](https://mlsanity.com/paper/2002.08318/) (2020)
- [Distributed No-Regret Learning in Multi-Agent Systems](https://mlsanity.com/paper/2002.09047/) (2020)
- [Training Generative Adversarial Networks via stochastic Nash games](https://mlsanity.com/paper/2010.10013/) (2020)
- [Secure Mobile Edge Computing in IoT via Collaborative Online Learning](https://mlsanity.com/paper/1805.03591/) (2018)

## Abstract (arXiv)

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 Oleft(k^-2minβ, 1/6right) 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.