Poster
in
Workshop: Optimization for ML Workshop
Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
Jing Dong · Baoxiang Wang · Yaoliang Yu
Abstract:
We study the problem of no-regret learning algorithms for general monotone and smooth games and their last-iterate convergence properties. Specifically, we investigate the problem under bandit feedback and strongly uncoupled dynamics, which allows modular development of the multi-player system that applies to a wide range of real applications. We propose a mirror-descent-based algorithm, which converges in and is also no-regret. The result is achieved by a dedicated use of two regularizations and the analysis of the fixed point thereof. The convergence rate is further improved to in the case of strongly monotone games.Motivated by practical tasks where the game evolves over time, the algorithm is extended to time-varying monotone games. We provide the first non-asymptotic result in converging monotone games and give improved results for equilibrium tracking games.
Chat is not available.