Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback

We thank the reviewer for the detailed and constructive comments.

General Acknowledgment on Proof Comments:

We sincerely thank the reviewer for their careful and detailed reading of the proofs. Their understanding is correct, and we very much value their comments and suggestions for improving the clarity and accessibility of the arguments. We will revise the manuscript to address all of the issues raised, including improving transitions between lines, clarifying technical assumptions (e.g., monotonicity and the structure of evolving cost functions), fixing notation inconsistencies, and expanding explanations where necessary to assist the reader in following the derivations.

On the uniqueness of the Nash equilibrium:

We appreciate the reviewer’s careful attention to this point. We do not assume the Nash equilibrium is unique. Our results, including Theorem 5.1, are stated to guarantee convergence to some Nash equilibrium, but not necessarily a specific one. When multiple equilibria exist, the algorithm may converge to any of them, and our current analysis does not control which one is selected. We will revise the manuscript to clarify this point explicitly and avoid any impression that uniqueness is assumed.

On the boundedness of the Bregman divergence and boundary Nash equilibria:

We thank the reviewer for the insightful comment. The reviewer is indeed correct; boundary equilibria are indeed often treated separately in the literature. However, we did not make any assumption that the equilibrium does not live on the boundary; we have to consider the unbounded cases. We will add a discussion of this in the revised manuscript.

Choosing p when learners are (partially) oblivious

We want to remark that our framework does not require full knowledge of the game or of other players’ objectives. The regularizer $p_i$ can be chosen individually (and differently) by each player based solely on their own cost structure. Our theorem and analysis are presented with the same $p$ only for a simpler presentation.

Regarding realistic choices for $p_i$, a few examples include:

For objectives with known curvature, entropic or Mahalanobis-type regularizers (or quadratic forms adapted to the geometry of $c_i$) may also be suitable.

Even if $c_i$ is not uniformly curved, one can often choose a $p_i$ such that $p_i$ has stronger curvature than $c_i$, ensuring $c_i - \kappa p_i$ is convex for some $\kappa$.

On the feasibility of $\hat{x}_i^t$​:

We thank the reviewer for pointing this out. The reviewer is correct​, our construction ensures feasibility by design, and we will make this explicit in the updated manuscript.

On the relationship with Duvocelle’s results:

We thank the reviewer for pointing this out. We will revise the text to clarify the distinction. Duvocelle’s results apply to strongly monotone games, whereas our results hold for general monotone games. Our results therefore, do not overlap.

On the notation $x_i^{t,*}$ and uniqueness (line 300):

We thank the reviewer for the observation. To clarify, $x _i^{t,\ast}​$ refers to one equilibrium point at time, and we do not assume uniqueness of the equilibrium. The analysis holds as long as $x_i^{t,\ast}$​ is any Nash equilibrium, and our results do not require it to be unique. We will revise the notation and clarify this in the text.

On the omission of $D_p$​ from the mirror map in Line 303:

Yes, this is deliberate. The result in this section concerns the convergence of the average iterate result for equilibrium tracking, for which we do not need the additional regularization from $D_p$. The inclusion of $D_p$ is crucial for our last-iterate convergence results, but not necessary for average-iterate convergence. We will clarify this distinction in the revision.

Line 630-631 on self-concordant barrier with linear term:

We will revise the manuscript and note that $h(x)$ is a self-concordant barrier function. Therefore, we consider a function $f(x) = h(x) + \langle a, x \rangle$, it is still a self-concordant barrier function. This is because the third derivative of any linear function is zero, the addition of the linear term does not affect the third derivative of $f$. Since self-concordance is defined in terms of bounds on the third derivative relative to the second derivative, $f$ inherits the self-concordance of $h$.

Line 639, is $p$ defined on $\mathcal{X}_i$ or $\mathcal{X}$.

In our setup, $p$ is defined as a separable function over the combined action space $\mathcal{X} = \prod_{i \in \mathcal{N}} \mathcal{X}i$, meaning $p(x) = \sum{i \in \mathcal{N}} p_i(x_i)$, where each $p_i$ is defined on the individual player’s action space $\mathcal{X}_i$.

Because of this separability, the gradient of $p$ decomposes as, $\nabla p(x) = (\nabla p_1(x_1), \nabla p_2(x_2), \ldots, \nabla p_N(x_N))$, and the Bregman divergence with respect to $p$ satisfies $D_p(x, x') = \sum _{i \in \mathcal{N}} D _p (x_i, x'_i)$ .

Thus, the inner product difference involving $\nabla p(x) - \nabla p(x')$ naturally decomposes into a sum over the players’ individual spaces, which explains why the inequality $\langle \nabla p(x) - \nabla p(x'), x' - x \rangle \leq - \sum_{i \in \mathcal{N}} ( D_{p_i}(x_i, x'i) + D{p_i}(x'_i, x_i) )$ holds.

We hope that this addresses the reviewer's concerns and we welcome any further questions.

We thank the reviewer for their detailed and thoughtful comments. We appreciate the recognition of the importance of the problem we study and would like to clarify a few key points.

On the concern regarding the use of Bregman divergence and the possibility of vacuous bounds

We agree that if $p$ is chosen to be a linear function, the corresponding Bregman divergence becomes zero, and the bound would indeed be vacuous. However, this does not affect the validity of our result, $p$ is a design choice, and our framework allows for choosing $p$ to be sufficiently curved (i.e., not flat), ensuring the Bregman divergence is meaningful. We will clarify this point in the revision to avoid any misunderstanding.

On the issue of uncoupledness and agreement on $p$

It is not necessary for all players to agree on the same function $p$. Our result holds even when each player selects their own $p_i$, as long as the key assumption, namely, that $c_i−\kappa pi$ is convex, is satisfied. In the case where all players use the same $p$, we can express convergence using the total Bregman divergence $\sum_i D_p(x_i, x_i^\ast)$. If players use different pip_ipi​, the result generalizes naturally to $\sum_i D_{p_i} (x_i, x_i^\ast)$. We assume that players take the same $p$ for a simpler presentation. We will revise the manuscript to make these points more explicit and to address the valid concerns raised. Thank you again for the valuable feedback.

We thank the reviewer again for the helpful comments and suggestions.

We will revise Table 1 to include a column specifying the convergence metrics used. Our results are stated in terms of $D_p(x_t, x^\ast)$, which, under Assumption 3.1, can implies that $x_t$ is an $\epsilon$-Nash equilibrium. The result for the linear zero-sum case is stated in terms of the total gap function, which similarly implies an $\epsilon$-NE. Therefore, even though some prior works use the (total) gap function while we use $D_p$, the table remains a meaningful basis for comparison. That said, we do not claim that $D_p$ and the (total) gap function are directly comparable, nor that one necessarily upper bounds the other.

We will add another paragraph following the presentation of Table 1 to explain the differences in convergence metrics and the limitation of $D_p$.

We hope this address the reviewer's concern, and we welcome any further questions.

We thank the reviewer for the detailed and constructive comments. We hope the following clarify the reviewer's concern.

Regarding the confusion in Table 1

We agree that zero-sum games are a subclass of monotone problems, and we apologize for the lack of clarity. The linear zero-sum case does not require stronger assumptions. However, due to the flatness of the cost functions in this setting, our analysis framework requires special treatment. In particular, the Bregman divergence induced by the regularizer ppp becomes ill-defined, which prevents a direct comparison using that measure. Instead, our results for the linear zero-sum case are stated in terms of the standard gap function, $\sum_i <\nabla_i c(x_i), x_i - x_i^\ast >$, which remains meaningful in this context. While this differs in form from the result in the general monotone setting, it is not weaker. We will revise the presentation of Table 1 and the accompanying discussion to clarify this distinction. We will also provide formal, self-contained theorem statements in the main text, including all assumptions and parameter definitions.

Can the authors provide the precise statements for the theorems? The key assumptions were not clear even after reading the appendix.

The only parameters required in our main theorem are $\eta_t$ and $\delta_t$, both of which are stated explicitly in the theorem. We do not rely on any additional hidden assumptions; everything is captured by Assumption 3.1. To improve clarity, we will revise the theorem statement to directly reference Assumption 3.1 and ensure that all relevant parameters and conditions are clearly defined and self-contained.

We thank the reviewer for the encouraging feedback. We're glad the contribution is viewed as significant. We will revise the manuscript accordingly. Specifically, we will:

1. Increase the number of random seeds and include experiments in higher dimensions to better assess variance and scalability.

2. Expand the discussion of experimental results and relate them more clearly to the theoretical findings.

3. Add a brief introduction to mirror descent for clarity.

4. Clarify in Algorithm 1 that zitz_i^tzit​ is sampled uniformly at random from the ddd-sphere, before receiving feedback.

5. Add a remark on the hardness of solving Eq. (1).

6. Fix the typo in Lemma J.2 and restate it as an upper bound.