On Tractable $\Phi$-Equilibria in Non-Concave Games

Thanks for your positive review and constructive comments! We will add a note on the trivial regime where $\delta = O(\epsilon)$. We will update Table 1 to distinguish our contributions better. Below, we address your questions.

Q: Could you elaborate on Corollary 1? It is not obvious to me how that bound follows from Theorem 2.

A: We will add the proof of Corollary 1 in the revised version of the paper. In Corollary 1, we consider the case where $\Phi$ is the class of $M$-Lipschitz functions from $[0,1]^d$ to $[0,1]^d$ and the utility is $G$-Lipschitz. The $\alpha$-covering number of $\Phi$ satisfies $\log N(\alpha) = \Theta((1/\alpha)^d)$ (this fact is also used in [1, Example 23]). Thus, we can run Algorithm 1 over the finite $\alpha$-cover of $\Phi$. This leads to a regret bound of $\sqrt{T(M/\alpha)^d)} + \alpha G T$, where the second term is due to the covering error. By choosing $\alpha = M T^{-1/(d+2)}$, we get regret bound $O(c \cdot T^{(d+1)/(d+2)})$ where c is some constant that only depends on $G$ and $M$.

[1] Stoltz, Gilles, and Gábor Lugosi. "Learning correlated equilibria in games with compact sets of strategies." Games and Economic Behavior, 2007

Q: I find it interesting that the algorithms in this paper are presented as randomized algorithm outputting a single $x^t$ rather than a deterministic algorithm outputting a distribution $\mu_t \in \Delta(\mathcal{X})$ (as done by Peng and Rubinstein [2024], Dagan et al [2024], and Zhang et al [2024]). At least with your techniques, this difference seems to be an unavoidable consequence of the fact that the utilities ut are nonlinear, and therefore one cannot say $\mathbb{E}_{\phi \sim p}[u^t(\phi(\cdot))] = u^t( \mathbb{E}\_{\phi \sim p} \phi(\cdot))$. Do I understand this correctly?

A: Two issues prevent us from outputting a distribution. The first one, as you pointed out, is the nonlinearity of the utility function. The second is that the distribution we constructed has an exponentially large support of |\Phi|^\sqrt{T}. To achieve an $\varepsilon$-approximate $\Phi$-equilibrium, we need $T$ to be $\textnormal{poly}(1/\varepsilon)$, so outputting the entire distribution requires time exponential in $1/\varepsilon$. Instead, using a sampling procedure allows us to significantly improve the dependence on $1/\varepsilon$ and obtain an algorithm whose running time is only polynomial in $1/\varepsilon$.

Q: If I understood the previous point correctly: in Theorem 5, the nonlinearity of ut is a nonissue by assumption. So, is it possible to de-randomize that result by instead deterministically outputting the uniform distribution $\mu^t = \\{x_1, \ldots, x_K\\}$?

A: We can derandomize this result by directly outputting the distribution $\mu^t$. In this case, we allow the algorithm to output a mixed strategy and consider regret over the expected utility in each iteration. Thank you for this insightful observation.

Q: Is there an efficient algorithm for $\Phi^{\mathcal{X}}\_{\textnormal{Beam}}(\delta)$-regret minimization?

A: We currently don’t have an efficient algorithm and believe this is an interesting open question. We introduce $\Phi^{\mathcal{X}}\_{\textnormal{Beam}}(\delta)$-regret to show that even for simple local strategy modification sets $\Phi(\delta)$, the landscape of efficient local $\Phi(\delta)$-regret minimization is already quite rich, and many basic and interesting questions remain open.

Q: Do the results of this paper have any novel implications for interesting special cases, such as nonconvex-concave zero-sum games, or simply the classical setting of concave no-regret learning? For example the results of Section 4 seem to have interesting (new?) implications for local (mixed) Nash equilibria in nonconvex-nonconcave zero-sum games.

A: To the best of our knowledge, the notion of $\Phi_{\textnormal{proj}}$-regret is new, and its efficient minimization is unknown even in the classical setting of no-regret learning with concave utilities. We think our upper and lower bound results for the $\Phi_{\textnormal{proj}}$-regret are, therefore, interesting even in this setting. We do not see any immediate implications for local mixed Nash equilibria in nonconvex-nonconcave zero-sum games, but this is a very interesting open question.

Thank you for the positive review and constructive comments on the structure and presentation of the paper!

We will incorporate your suggestions and improve the presentation in the revised version of the paper. Since one more page is allowed in the camera-ready version, we will assign more space to the finite $\Phi$ setting and include Algorithms 1 and 2 and relevant discussions in the main paper. We will also adjust the structure of section 4 and make all statements in the main paper more concise.

Complexity of our algorithms: The algorithms we study (except for Algorithms 1 and 3) are gradient-based algorithms like gradient descent and optimistic gradient descent, which have efficient practical implementations. Regarding the complexity of the sampling procedure (Algorithm 2), the per-iteration complexity is exactly $\sqrt{T} \cdot |\Phi|$, where we need to sample from a distribution that supports on $|\Phi|$ points, evaluate the strategy modification function $\phi$, and repeat the above procedure for $\sqrt{T}$ steps. The above complexity analysis for Algorithm 2 is tight. There is an equivalent implementation that improves the expected running time by a factor of 2: we could first sample a number N uniformly between $[1, \sqrt{T}]$ and then only run the sampling procedure for $N$ steps rather than $\sqrt{T}$ steps, and finally return the last point. This improves the expected per-iteration complexity to $(\sqrt{T} \cdot |\Phi|) / 2$. We will add the discussion in the revised version of the paper.

Thank you for your very positive review. Below, we address your questions.

Q: I found some papers showing that for Markov games, the CE or CCE can be learned in polynomial time. For example Jin, Chi, et al. "V-Learning--A Simple, Efficient, Decentralized Algorithm for Multiagent RL." arXiv preprint arXiv:2110.14555 (2021). From my understanding, when setting their horizon H = 1, the Markov game seems to be a classical game. Is there any difference between this setting and yours?

A: If the horizon $H = 1$, then a general-sum Markov game becomes a general-sum normal-form game where each player’s utility function is linear in their own strategy. This is a special case of the non-concave games we consider in this paper since, in a non-concave game, each player’s utility could be non-concave in their own strategy. Additionally, Markov games with $H \ge 1$ are special cases of non-concave games that include additional structure, such as the Markovian property. Since our focus is on the more general class of non-concave games, these specific results do not apply.

Q: Is there any applications of $\Phi$-equilibrium? For example, when do we need to efficiently solve some $\Phi$-equilibrium?

A: The notion of $\Phi$-equilibrium is very general. If $\Phi$ is all constant strategy modifications, the corresponding $\Phi$-equilibrium coincides with the notion of coarse correlated equilibrium (CCE); If $\Phi$ is all strategy modifications, then the corresponding $\Phi$-equilibrium coincides with the notion of correlated equilibrium (CE). CE and CCE are both central and classical notions extensively studied in the literature and used in practice. Generally, a $\Phi$-equilibrium guarantees that no single agent has an incentive to unilaterally deviate by using strategy modifications from their set $\Phi_i$. This provides a stability guarantee that we believe will be relevant for many economics and machine learning applications, including game AI and multi-agent reinforcement learning.

Q: The definition of $\Phi$-equilibrium looks really similar to the Correlated Equilibrium (CE) in your Definition 6. Is CE as the same as $\Phi$-equilibrium if $\Phi$ is chosen as the whole space?

A: Yes. If we choose $\Phi$ as all possible strategy modifications, the corresponding $\Phi$-equilibrium is exactly CE.