Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
<|reference_start|>Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games: Last-iterate behaviors of learning algorithms in repeated two-player zero-sum games have been extensively studied due to their wide applications in machine learning and related tasks. Typical algorithms that exhibit the last-iterate convergence property include optimistic and extra-gradient methods. However, most existing results establish these properties under the assumption that the game is time-independent. Recently, (Feng et al, 2023) studied the last-iterate behaviors of optimistic and extra-gradient methods in games with a time-varying payoff matrix, and proved that in an unconstrained periodic game, extra-gradient method converges to the equilibrium while optimistic method diverges. This finding challenges the conventional wisdom that these two methods are expected to behave similarly as they do in time-independent games. However, compared to unconstrained games, games with constrains are more common both in practical and theoretical studies. In this paper, we investigate the last-iterate behaviors of optimistic and extra-gradient methods in the constrained periodic games, demonstrating that similar separation results for last-iterate convergence also hold in this setting.<|reference_end|>
@article{feng2024last-iterate,
    title={Last-iterate Convergence Separation between Extra-gradient and Optimism
  in Constrained Periodic Games},
    author={Yi Feng, Ping Li, Ioannis Panageas, Xiao Wang},
    journal={arXiv preprint arXiv:2406.10605},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.10605},
    primaryClass={cs.LG cs.GT}
}