Best of Both Worlds: Regret Minimization versus Minimax Play

Thank you for carefully reviewing our paper and providing valuable feedback!

Remark on non-symmetric games:

What are the barriers preventing you from extending your results to non-symmetric zero-sum games?

Response: We would like to point out that, in fact, the game in question does not have to be symmetric. It is sufficient if the min-max value of the game is zero. In this case, all our results hold immediately without modifying the statement or proof. The reason we pointed to symmetric zero-sum games as an important example is merely that, in such games, it is easy to prove that its value is always zero. However, there are many asymmetric games in which the value is still zero, and our results readily hold for these games, too. In general, even if the value $V$ of the game is non-zero, our algorithm is guaranteed an expected payoff of at least $V\cdot T - 1$.

More generally, we can readily apply our results even to EFGs that are not zero-sum, or not even two-player (with exactly the same proofs but cost functions defined accordingly). In this case, we guarantee the same expected payoff as the chosen baseline comparator $\mu^c$ (which is considered safe in some sense) up to one additive unit, while still having $O(\sqrt{T})$ regret to any strategy $\mu$. Our motivation for stating the results for symmetric zero-sum games was mainly for illustrative purposes.

We will move these remarks to a more prominent place in the writing so it is clear that the limitations are not necessary.

Or to no-swap-regret?

Response: The obvious idea would be to combine the classical reduction of Blum & Mansour (BM) with our phased algorithm. However, this poses several technical challenges, among which are the following: i) It is unclear how to check the regret condition for entering a new phase for swap regret, as there are exponentially many swap functions. ii) If, instead, we check the regret condition for the $A$ different no-regret algorithms in (BM) individually, then these algorithms may be in different phases, and it is unclear how to combine them into a single policy. Hence, whether we can provide the same guarantees for no-swap regret remains an interesting open question.

Thank you for carefully reviewing our paper and providing valuable feedback!

The algorithm presented by the authors is really close to Even-Dar et al. (2008). Authors should focus on what are the differences beyond simply using Exp3 as a base algorithm.

Response: Indeed, the high-level difference between the algorithms is using Exp3 as a base algorithm. In addition to this:

• We use importance weighting according to the algorithm's iterates $\mu^t$, not the Exp3 iterates $\hat{\mu}^t$ as usual.
• We modify the condition for entering a new phase as the true cost vectors are not observed.
• We switch the learning rate in the last possible phase (see below).

This being said, the main difference lies in the analysis of the algorithm (Section 3.1/Regret Analysis), which is not just a direct combination of the analysis by Even-Dar et al. and the standard Exp3 guarantee. One technical difficulty lies in the fact that the estimated cost functions may be unbounded in general. Our analysis tackles this by a refined treatment of the algorithm's phases: In the last possible phase, the cost estimates can be unbounded but it is sufficient to resort to a regret bound in expectation (which does not need boundedness). In all other phases, for the analysis to go through we need an estimated regret bound with probability one. This is only possible since we are able to bound the estimated costs in these phases due to the comparator assumption and the phasing scheme.

What is the novelty in the presented reduction from OLM to NFG or EFG ?

Response: Technically speaking, the application of safe OLM algorithms to NFGs/EFGs by using e.g. the min-max equilibrium as comparator is relatively straightforward (c.f. Section 2). However, we are not aware of any prior work making this interesting connection to learning in games, even under the easier full-information feedback. We thus view it as an important conceptual contribution of our work.

PS: Please refer to our Remark on non-symmetric games in reply to reviewer aZNc for a common response on the generality of our results beyond symmetric games.

Thank you for carefully reviewing our paper and providing valuable feedback!

It is possible that I have not fully understood the motivation behind this work. If I receive a convincing response on this point, I am willing to raise my score.

Response: From the viewpoint of learning in games, the motivation of our paper is the following: Suppose you play a repeated game such as Rock-Paper-Scissors or Heads-Up Poker against an unknown opponent. Should you rather run a no-regret algorithm, or simply play the Nash equilibrium? The former would guarantee that you linearly exploit the opponent when, for example, they decide to play a static policy that is slightly suboptimal (non-equilibrium). The latter would guarantee you to not lose money (beyond the Nash value of $0$) in expectation. But it is easy to see that neither guarantees both of these preferable properties. Our work states that you can achieve essentially both simultaneously under the given minimal assumption.

What are the benefits of achieving a lower regret when choosing the minimax policy $\arg\min_{\mu} \max_{\nu} V(\mu, \nu)$ as the comparator? If there are advantages to using the minimax policy as the comparator in the context of learning in games, the reviewer would like the authors to clarify them.

Response: This is indeed a key motivation behind our work (c.f. Section 2): Notice that for the minimax policy $\mu^\star$, we have $V(\mu^\star,\nu^t) \leq 0$ no matter what policy $\nu^t$ Bob plays. Hence, a regret bound of $\mathcal{R}(\mu^\star) \leq 1$ compared to the minimax policy implies that $\sum_{t=1}^T \mathbb{E}[V(\mu^t,\nu^t)] - 0\cdot T \leq 1$. This proves that we lose at most $1$ unit to Bob throughout the interactive play (in expectation), no matter Bob's play. Simply running a standard no-regret algorithm would not guarantee this; it can lose up to $\sqrt{T}$ units, which can be a significant amount. But, since we simultaneously maintain $O(\sqrt{T})$ regret compared to any $\mu\neq\mu^\star$, we still enjoy all the benefits of playing a no-regret algorithm, including that we linearly exploit, for example, a static opponent that slightly deviates from the equilibrium.

This work focuses on symmetric games. Can the authors address this limitation?

Response: Yes! Our results hold beyond symmetric games, which only serve as an important motivation. Please refer to our Remark on non-symmetric games in reply to reviewer aZNc.

Additional minor clarifications:

In Line 17, the statement "the regret compared to any fixed strategy $\mu$ satisfies $O(\sqrt{T})$" depends on the algorithm being used, and such a regret upper bound is not necessarily always achievable.

Response: Here, we are referring to any no-regret algorithm that has regret of $O(\sqrt{T})$ uniformly over adversaries and comparators. Such no-regret algorithms exist both for normal- and extensive-form games (for example online mirror descent). The property itself does not depend on the specifics of the algorithm and holds for any such no-regret algorithm.

In Line 46, the term "the best strategy" is ambiguous, making it difficult to understand.

Response: By regret compared to the best strategy in hindsight, we mean that the regret bound holds compared to any strategy $\mu$ (in particular to a minimizer of the observed sequence of play). We are happy to change the wording to "against any fixed strategy $\mu$" for clarity.

in Line 89, the phrase "a special ('safe') comparator strategy" is unclear at this point.

Response: We will change this to the following in the final version: Alice receives a special comparator $\mu^c$ that she considers a 'safe' strategy. The motivation for this is that we can later choose $\mu^c$ to be a minimax equilibrium $\mu^\star$, which is safe in the sense of guaranteeing zero expected loss in symmetric zero-sum games.

In Line 104, the term "the worst-case expected regret $\max_{\mu} \mathcal{R}(\mu)$" is used, but referring to the worst case over the comparator (rather than over a sequence of gradients) in this way is maybe uncommon.

Response: We agree that here the regret refers to the worst case over the comparator. (Note that since our bounds are uniform over the opponent's play, they also hold in the worst case over the sequence of gradients.) We are willing to change this to simply "regret" (as opposed to "regret compared to $\mu$") throughout to avoid confusion.

Thank you for carefully reviewing our paper and providing valuable feedback!

The related work and its comparisons with the manuscript can be more adequately discussed.

Response: We agree that further elaboration on the related work would increase the clarity of the paper. In the current version, an extensive discussion of related work is deferred to Appendix B. We plan to move parts of this to the main text in the camera-ready version.

Further discussions and comparisons with Lattimore (2015) and Ganzfried & Sandholm (2015) will be appreciated.

Response: Further comparisons with Lattimore (2015):

Lattimore (2015) shows that in multi-armed bandits, $O(1)$ regret compared to a single comparator action implies a worst-case regret of $\Omega(AT)$ compared to some other action. In our terminology, a single action corresponds to a deterministic strategy. We show that, perhaps surprisingly, it is possible to circumvent this lower bound if the comparator strategy plays each action with some non-zero probability $\delta>0$ (while maintaining the optimal order of $\sqrt{T}$ regret). As further discussed in the main text, this minimal possible assumption is sensible in various game-theoretic contexts.

Additional comments regarding Ganzfried & Sandholm (2015):

Ganzfried & Sandholm (2015) do not provide any sort of regret guarantees. Instead, they ask the following question: In which rounds of the game is it possible to deviate from the min-max strategy? Their algorithmic approaches rely on best-responding to an opponent model whenever the algorithm has accumulated just enough utility to risk losing it again. While the authors do prove safety guarantees, this is not the case for exploitation. The latter would likely heavily depend on the other player and the quality of the opponent modeling. In our paper, we do not encounter this difficulty because we consider standard regret minimization against any (time-varying) adversary.

PS: Please refer to our Remark on non-symmetric games in reply to reviewer aZNc for a common response on the generality of our results beyond symmetric games.