Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a new novel algorithm named LRL-OFTRL which can achieve near-optimal for general convex games. In particular, when all players employ LRL-OFTRL, the regret of each player grows in logarithm speed. Their results significantly extend the result derived by Daskalakis et al. [2021] and can be applied to many subareas such as normal-form games, extensive-form games, splittable routing games, and Cournot competition. 
strengths_and_weaknesses: 
Originality: This paper proposes a new novel algorithm named LRL-OFTRL which can achieve near-optimal for general convex games.  

Quality: The theory is technically solid and is supported by proof. This is complete work. 

Clarity: this paper is well written and organized. The main theorems are supported by proof, but I

Significance: This paper proposes a new algorithm with a novel technique that significantly extends and improves the prior works. I think it is novel. 

There are no experiments in this paper. It would make the result more significant if the authors could add some experiments (simulated and/or real data), which (1). shows that the proposed algorithm is implementable, and (2). if possible, show the advantage compared with Kernelized OMWU [Farina et al., 2022].
questions: Since I am not familiar with the area of convex games, I have no technical criticism for this paper.


limitations: The authors have addressed their work's limitations and potential negative social impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies online learning for general convex games, where the decision set of each player is general convex. The authors propose an algorithm and prove an $O(\log T)$ regret each player, where $T$ is the number of rounds. It improves the best $T^{1/4}$ regret achieved by OMD. At the core of their algorithm is a lifting strategy with a regularized FTRL framework that updates both the utility and the regularization parameter simultaneously. 
strengths_and_weaknesses: Strengths:

- The results are important in theory since it provides the first $\log(T)$ type regret for general convex games.
- The discussion is comprehensive. 
- The proof is technically sound.

Weaknesses:
-  There can be more explanation about the problem setting. See questions. 
questions: - The authors mention that their algorithm will achieve an $\sqrt{T}$ regret under the adversarial setting. Can the authors explain what the adversarial setting is since I do not find the definition in the main text?

- From the algorithm description and the proof, it seems that both the theoretical result and the algorithm can be regarded as those counterparts for a 'single-player' setting, since the regret reg_i cares nothing but the relative optimality of player i, and the algorithm also deals nothing with other players. Can the authors explain more about that?


limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers a convex game (i.e., utility functions that are smooth, and convex given the other actions) between n players, where each player gets the gradient of its utility function at the end of every turn (i.e., full information). An optimistic follow-the-regularized-leader variation is proposed such that if all players use this algorithm with the same tuning, they all achieve a regret of O(logT). If this is not the case, each player can detect that and switch to an algorithm that achieves O(sqrt(T)) against an adversary. The algorithm requires to solve an optimization problem, and the paper proposes two oracles that can provide good approximate solutions to this problem, and analyzes the complexity and the implication for the regret bound. 
strengths_and_weaknesses: The paper is very well-written and the results are novel and explained well. General convex games are indeed a very broad and interesting class of games. The math is sound and the technical derivations are neat. I'm a bit hesitant regarding the significance or relevance of the results. Some of these issues can be mitigated or at least be presented more accurately, while others are inherent to the type of question the paper is interested in. I do believe that assuming that this question is interesting, the results of the paper are impressive. 

The first issue is with the motivation: why would anybody need an algorithm with the (impressive) guarantees proven here. Using the same definition of regret for this game scenario is not obvious to me. It compares the sum of rewards of the players with something completely artificial - the sum of rewards the players would have gotten by playing a fixed action, while all players still follow their sequence of play. However, this sequence of play was generated partly in response to the player's actions. The paper does mention one possible motivation, which is to compute the coarse correlated equilibrium of the game. I think that's a good motivation overall, but if the motivation is computational, it sets some different priorities. Most importantly, I'm not sure if the computational complexity offered by this algorithm makes it a good choice (which I discuss below). 

The second issue is with the feedback. Being able to evaluate the gradient in a data-driven scenario is one thing, but being able to do so (with no error) in a game is a different thing. The gradient of player i's utility with respect to its action depends on the actions of other players and this function depends on the structure of the game. I find it a very strong assumption. Even if the algorithm is used to compute a coarse correlated equilibrium (CCE), it's only interesting when the utility functions are unknown - otherwise computing the CCE can be done directly. Providing examples where one easily knows the gradient but not the utility function would help to justify this model, and by that, the motivation of the paper. The examples provided in Section 2.2 are for convex games, and indeed the convexity assumptions are very mild: but the feedback assumption isn't, and I'm not sure how and when it would be satisfied in the given examples. In terms of presentation, the paper claims that the proposed algorithm is an "uncoupled learning algorithm", where uncoupled is defined as "every player is oblivious to the other players’ utilities". First, this definition is soft and vague. Then, it is claimed that the algorithm is even "strongly uncoupled" since players need not have any prior knowledge about the game whatsoever. I don't see how this is the case here if the gradient of the utility function of each player is (indirectly) highly related to the other players' utilities. Is this fair to say the algorithm is uncoupled where all that couples a player to others is given to this player for free, as an arbitrary modeling assumption? Additionally, it seems like the players need to know the Lipschitz parameter L, and the number of players, so I'm not sure if this statement is accurate. 

The third issue, which can be easily fixed, is that the paper makes some over statements or just vague technical ones:

1) The statement that the dynamics are "efficiently implementable" is puzzling to me. The number of oracle calls per iteration is T-dependent. Then, each oracle call needs to give an approximate solution with an error of O(1/T), which will require again T-dependent complexity. The proximal oracle requires O(log(log(T)) calls which is nice, but each call will be complicated to implement (providing more detail here is recommended). There, an alternative linear optimization oracle is proposed, but this one needs poly(T) calls per iteration. Now, T needs to be very large to make the regret improvement from O(log^4(T)) significant. In light of this, in what sense is this efficient? numerical simulations could have helped to demonstrate the that algorithm runs in a reasonable time. I find this issue very important if the motivation of the paper is to compute coarse correlated equilibrium. If the overall computation is infeasible, then it's unclear why the  O(log(T)) regret is worst the struggle. I can see why improving the state-of-the-art regret bound for games might require heavy computational machinery like these oracles, but it looks like the paper is claiming that this computational disadvantage is in fact an advantage. 

The line about the "best-response oracle" is a bit misleading. Usually, best-response is used in finite discrete games where the "oracle" is just going over the actions. In continuous convex games, best-response amounts to solving a convex problem, so it's not any easier or more common. 

Together with the "uncoupling issue" above,  I think that claiming that the algorithm is both uncoupled and efficiently implementable (which is the main presented research question here) is an overstatement (also line 69 and other places). 

2) The assumption that the product of the norms, in line 193, is at most 1, is not exactly without the loss of generality. Indeed, one can always rescale the rewards, but as discussed in lines 275-280, this adds a factor to the regret. This factor is recognized in the comparison in Table 1, but not in other places. I don't see why this assumption is needed, instead of just including this factor. This assumption holds for the simplex as the action space, but not, for example, in a multi-dimensional Cournot competition. It's also easy to miss this assumption which is not given near the assumption on the game or the statement of the results, which makes the regret bounds look better than they are in general action spaces. 

3) The statement that the algorithm can be adaptive so that if player i is instead facing adversarial utilities the regret is O(sqrt(T)) is a bit vague. The meaning of this adaptivity only becomes clear when reading the proof of the Theorem. But then, it looks like this adaptivity requires each player to know the number of players n, and the Lipschitz parameter L. The step size also requires the player to know these parameters, but at least then one imagine what can be done if they don't know them (or what's the resulting factor in the regret). Since, against an adversary, there are no players at all, this means that the player excepts to play against n-1 other players, and if it finds himself playing against any other number (or players with different tuning), the regret can jump to O(sqrt(T)). I still think that this adaptivity is nice, but I think that the statement in the theorem needs to be more rigorous and include all detail and implicit assumptions. 

4) The comparison to Piliouras et al. [2021] is perhaps a bit unfair. Their paper does claim their algorithm is uncoupled, which line 117 here refutes. This seems a very subtle issue given that I'm not sure if the proposed algorithm is uncoupled. I think that discussing how the proposed algorithm is at least "more uncoupled" than Piliouras et al. [2021] is necessary. Then, Table 1 is very confusing with regard to Piliouras et al. [2021]. Where is the T dependence of the regret bound? Also, isn't Piliouras et al. [2021] for finite discrete games, whereas this paper is for continuous games? 

I would be happy if I missed some critical details that can mitigate some of these issues. Disconnected from the confusing motivation, the proposed algorithm is creative and neat. Providing some intuition so why and how this lifting and regularizer do the trick can be interesting. 

Minor Comments:

The title of Section 2.3 seems inappropriate. This should be the problem formulation. 

line 539 - saying that G is defined in (11) can help.

missing period before line 599.

I wasn't able to follow the proof of Proposition 5. What vector is used as the fixed (lambda,y) -star vector here? how come the additional term in the regret bound has the 2 factor, without the 1/(27*eta)? 

questions: 1) What do you mean by "efficiently implantable"? especially in light of algorithms like OMWU that seem far more efficient? 

2) Is there any concrete motivation that I missed, other than computing the coarse correlated equilibrium? would the regret make sense as a benchmark in some game scenarios? 

3) Are there examples for applications where the "full game information" assumption is reasonable? 
limitations: This is a theory pape so there is no societal impact. The technical limitations could be better discussed, as I explain above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the uncoupled learning for general convex games, which is absolutely of interest to the audience in the community of online learning and game theory. The paper presents novel algorithms equipped with strong regret guarantee in the sense that only poly log T regret is incurred for each player; and also the algorithm can be efficiently implemented given a certain oracle. The crucial novelty in the technical stuff lies in the usage of the lifting to ensure nonengativeity of the regret and also the log barrier function to enhance the stability.
strengths_and_weaknesses: The problem studied in this paper is very interesting and challenging. This paper studies the uncoupled learning for general convex games, which is absolutely of interest to the audience in the community of online learning and game theory. The paper presents novel algorithms equipped with strong regret guarantee in the sense that only poly log T regret is incurred for each player; and also the algorithm can be efficiently implemented given a certain oracle. The crucial novelty in the technical stuff lies in the usage of the lifting to ensure nonengativeity of the regret and also the log barrier function to enhance the stability. To the best of my knowledge, there is no similar result of uncoupled learning for convex games even though there is a large body of researches in this thread. The paper writing is of high quality and make the reader feel enjoyable.

The usage of lifting to ensure the nonnegativity is very interesting. Although the lifting idea was used in earlier studies [1,2], using it in uncoupled learning dynamics is very new to the best of my knowledge.

It is a pity that authors fail to cite the two prior works that also use the lifting ideas (in other bandit problems though).
[1] Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs. NeurIPS 2020.

[2] Adaptive Bandit Convex Optimization with Heterogeneous Curvature. COLT 2022.

The authors are suggested to explain more on the lifting operation as stated in Eq. (2). Note that the augmented dimension $\lambda$ also affects the remaining dimensions due to the constraint $y \in \lambda X$, which exhibits salient difference to earlier papers [1,2] that only pave a constant 1 in the augmented dimension. 


Using the self-concordant barrier function for full-information game setting is interesting. This will introduce strengthened stability as argued and proven in the paper, while the log barrier function will also make the dimensional dependency worse. 


minor comments: Line 191. players need not have any prior --> need not to have
questions: See above.
limitations: See above.
review_title: null

Meta-review: metareview: Reviewers are all positive and appreciate the theoretical contributions. Good work! Please make sure you address all the reviewers' comments and incorporate them (and any new experimental results, if applicable) in your camera-ready.
confidence: Certain
Decision: Accept