Summary
This paper studies the problem of learning in a general monotone game with bandit feedback, with strongly uncoupled dynamics. For smooth cost functions, the authors achieved an $O(T^{-1/4})$ last-iterate convergence rate. For strongly monotone games, the obtained last-iterate convergence matches the state-of-the-art rate $O(T^{-1/2})$. The proposed algorithm uses the standard gradient estimator for BCO, but updates with a slightly different OMD-based algorithm with a different regularizer. When each player runs the same algorithm, the individual regret can also be guaranteed with $O(T^{3/4})$ regret for generally monotone games and $O(T^{1/2})$ for strongly monotone games. Finally, the authors further extended the results to time-varying games, considering two cases: (1) the time-varying game sequence gradually converges to a static game, and (2) the game sequence does not converge, and the performance measure relies on some non-stationarity measures depicting how the game sequence changes.
Strengths
Extending the studies from strongly monotone games to generally monotone ones is meaningful. The proposed algorithm where a new regularizer is used is novel. The authors have also proved a high-probability result for the global convergence rate. And they have also applied their results to the social welfare to validate the importance of their results.
Weaknesses
The core of achieving the last-iterate convergence is inserting a regularizer $p(\cdot)$ into the OMD update. Concretely, in the OMD update, the authors imported an additional additive $\eta (t+1) D_p(x_i, x_i^t)$ into the OMD update. And the core analysis is shown in Lemma J.1 in the appendix. Specifically, by using $\sum_i D_p(x_i^*, x_i^{T+1})$ as the performance measure, the $\eta (t+1) D_p(x_i, x_i^t)$ in the OMD update can be extracted and moved to the left-hand side of the three-point equality of Bregman divergence, dividing both sides by $O(T)$ yields the performance measure on the left-hand side and a term like $(Regret)/T$ on the right-hand side. Consequently, it remains to analyze the regret guarantee of the proposed method and dividing it by $T$ yields the final last-iterate convergence rate.
This idea is novel. However, the key question is how we can access such function $p(\cdot)$. As stated by the authors on Page 5, the function $p(\cdot)$ has to satisfy the condition that $c_i(x_i, x_{-i}) - \kappa p(x_i)$ is convex. To compute such a valid $p(\cdot)$, the algorithm must have the complete information of the original cost function $c_i$, which is not permitted by the learning protocol since $c_i$ is unknown. Otherwise, if $p(\cdot)$ is given by the learning problem, the condition of $c_i(x_i, x_{-i}) - \kappa p(x_i)$ being convex should be an assumption that should be put in Section 3 along with Assumption 3.1. However, I am more inclined to believe that this should not be an assumption since $p(\cdot)$ is something that appears in the algorithm, while assumptions are actually statements about the problem-dependent and algorithm-independent quantities. Can the authors provide some further explanations on this issue?
Questions
1. Can the $O(T^{-1/4})$ last-iterate convergence rate be considered as the $O(T^{3/4})$ regret for bandit convex optimization?
2. For bandit optimization with convex and smooth functions, the state-of-the-art regret is $O(T^{2/3})$ by [1], which seems to correspond to a last-iterate rate of $O(T^{-1/3})$ in the setup of smooth monotone games. Is it possible to improve the current $O(T^{-1/4})$ to $O(T^{-1/3})$?
3. For BCO problems with smooth or strongly convex functions, FTRL seems to be more popular than OMD [1,2]. Is it possible to represent Algorithm 1 using an FTRL-based update rule? Besides, are FTRL and OMD equivalent in the setup of BCO or bandit smooth monotone games?
4. The rates in Table 2 are not last-iterate results. First, the guarantees in Duvocelle et al. (2023) and Yan et al. (2023) are represented in a regret-type rate. Second, the rate in Theorem 6.2 is actually not last-iterate since the performance measure is $\frac{1}{T} \sum_t \cdots$. I suggest that the authors could correct this issue in the next version.
5. It seems that the rates authors mentioned in Duvocelle et al. (2023) and Yan et al. (2023) do not need smoothness? I did not check their results very carefully, and I suggest that the authors could conduct a careful double check about whether the above two works need smoothness. If not, these works seem to be not comparable since Duvocelle et al. (2023) and Yan et al. (2023) focused on strongly monotone games without smoothness while this paper considers monotone smooth games.
6. It should also be made clear that Duvocelle et al. (2023) and Yan et al. (2023) used tracking error $\\|x_t - x^*\\|^2$ as the performance measure, which is different from the measure used in this paper. Thus again I think these works are actually not comparable. Besides, if I am wrong about some statements, it is welcome that the authors could correct me.
6. In Line 287, the authors said that "We show that Algorithm 1 converges to the Nash equilibrium in monotone, strongly monotone, and linear games." It should be made clear that the results for different kinds of games require different parameter configurations.
7. Could the authors provide some explanations about the validness of the permanence measure $\sum_i D_p(x_i^*, x_i^{T+1})$? Why this measure is a valid measure of the distance of the algorithm's output to the Nash equilibrium? The gap using Bregman divergence heavily relies on how convex the function $p(\cdot)$ is. If $p(\cdot)$ is nearly a linear function, this measure seems not to be a good enough performance measure, from my point of view, intuitively. I guess that the authors use this quantity as the performance measure mainly due to technical reasons, as I said in the 'Weaknesses' part?
References:
[1] Improved Regret Guarantees for Online Smooth Convex Optimization with Bandit Feedback, AISTATS 2011
[2] Bandit Convex Optimization: Towards Tight Bounds, NIPS. 2014