Best of Both Worlds: Regret Minimization versus Minimax Play
Authors: Adrian Müller
Jon Schneider
Stratis Skoulakis
Luca Viano
Volkan Cevher
Venue: ICML 2025 poster (2025)
Keywords: online learning
game theory
regret minimization
Primary area: theory->game_theory
TL;DR: Combining regret minimization and minimax play allows to exploit weak strategies while risking only constant expected loss.

Abstract: In this paper, we investigate the existence of online learning algorithms with bandit feedback that simultaneously guarantee $O(1)$ regret compared to a given comparator strategy, and $\tilde{O}(\sqrt{T})$ regret compared to any fixed strategy, where $T$ is the number of rounds. We provide the first affirmative answer to this question whenever the comparator strategy supports every action. In the context of zero-sum games with min-max value zero, both in normal- and extensive form, we show that our results allow us to guarantee to risk at most $O(1)$ loss while being able to gain $\Omega(T)$ from exploitable opponents, thereby combining the benefits of both no-regret algorithms and minimax play.

Best of Both Worlds:
Regret Minimization versus Minimax Play
Adrian Müller
Jon Schneider
22 Stratis Skoulakis
3 Luca Viano" " Volkan Cevher
Abstract
vations, and Bob does likewise. Both players then receive their respective costs in this round prior to moving to the next round.
In this paper, we investigate the existence of on- line learning algorithms with bandit feedback that simultaneously guarantee ((1) regret compared to given comparator strategy, and Ö(VT) re- gret compared to any fixed strategy, where I' is the number of rounds. We provide the first af- firmative answer to this question whenever the comparator strategy supports every action. In the context of zero-sum games with min-max value zero, both in normal- and extensive form, we show that our results allow us guarantee to risk most (1)) loss while being able to gain (2(T)) from exploitable opponents, thereby combining the benefits of both no-regret algorithms and min- imax play.
To minimize her cumulative cost, Alice could compute an equilibrium strategy and simply play it in every round (min- imax play (Von Neumann & Morgenstern, 2007)). This way, she would be guaranteed to never lose anything to Bob in expectation. However, she might also not win anything from Bob even if he plays suboptimal (non-equilibrium) strategies. A classic example of this dilemma is Rock-Paper- Scissors, for which the min-max strategy the uniform strategy, which wins zero even from an opponent that al- ways plays Rock. Alternatively, Alice could run learning algorithm (regret minimization 2006)). This way, her average cost would approach the one of the best strategy in hindsight, allowing her to exploit such opponents. However, by running such an algorithm she would have to deviate from the equilibrium strategy, thereby risking incurring a significant amount of costs during learn- ing. More formally, there are two popular lines of thought how Alice could minimize her overall cost over the T rounds of play:
Dessa-Binnchi & Lugosi,
1. Introduction
Two-player zero-sum games form one of the most funda- mental classes studied in game theory, capturing direct competition between two opposing agents. In a zero-sum game, Alice and Bob choose mixed strategies μ E P and E P', respectively, from some strategy polytopes P and Pp Their expected payoffs are specified by fune- tion V. Alice aims to minimize V(,,v,, whereas Bob aims to maximize it. This definition subsumes the classical normal-form zero-sun games ( (Von Neumann & Morgen- stern, 2007) like Pock--aape--Scissors, as well as the more complex extensive- zero-sum games (Osborne & Ru- binstein, 1994), such as Heads-up Poker. zero-sum game called fair if its min-max value zero, meaning that minger max V(H,v) 0. This models the fact that none of the players has strategic advantage due to the struc- ture of the game. For instance, game is always fair if it is symmetric, i.e. when P = p' and V(,,v) v) = (V p.), as is the case for many games of interest. Now suppose Alice repeatedly plays a fair zero-sum game against her unknown opponent Bob for T consecutive rounds. In each round, she chooses her next strategy based all her previous obser-
1) Min-Max Equilibrium: In every round t, Alice simply selects the min-max strategy μ² = μ=* E arg mingeP maxver" ((,, v).. She then loses at most V == min max ((,,v) units to Bob. For fair zero-sum games, we have V O, meaning that she will not lose anything in expectation. However, for example in normal-form games, she also never wins any units if μ²' is full-support (Braggion et al., 2020), and even otherwise may not win anything (Section 5). In summary:
Alice is guaranteed not to lose anything, but might not win anything even if Bob plays poorly.
2) Regret Minimization: Alice selects μ³² E P according no-regret algorithm. Then she can guarantee that, no mat- ter Bob's 's strategies v v',... p'....,,'' vT E P', the regret compared to any fixed strategy satisfies
T
Ev v4) Σ ((AN
'ETH Zürich "Google Research AAarhus University *EPFL. Correspondence to: Adrian Miller @admuell@cthz.chhh
In fair zero-sum games, plugging in the equilibrium /t ,r", we have V(u, v²) < V* 0. This means that the above regret guarantee ensures that Alice might lose most
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Regret Minimization vs Minimax Play
O(VT) units to Bob, which can be significant amount. Indeed, one expects there are cases where she does (Sec- tion 5) since there is matching regret lower bound. How- ever, if Bob plays sub-optimally, it may be the case that min Dx= Viu, )²) = (T)), meaning that Alice
To the best of our knowledge, this is the first result of its kind under bandit feedhack.
We complement this regret guarantee with a lower bound for NFGs, showing that the regret bound cannot be im- proved significantly (Section 3.3). This illustrates that our algorithm is close to optimally exploiting weak strategies, as desired.
wins (T) units. As a result:
Alice risks losing O ((VT) units, but can win up to (T)) if Bob plays sub-optimally.
We then transfer our insights the more challenging framework of extensive-form games (EFGs). This is specifically relevant since in stateful games, it is essential to consider bandit feedback. By proposing a correspond- ing algorithm for EFGs, we show that even in such interac- tive games with imperfect information, we can answer our main question in the affirmative (Section 4.2). We gener- alize our lower bound to this setting, too (Section 4.3).
Whether Alice will choose to play 1) a min-max equilibrium or 2) according to a no-regret algorithm depends on how risk-averse Alice is how willing Alice is to risk O(VT) units in the hope of winning ( This naturally raises the question of whether we can have the best of both worlds:
Question 1. In a fair zero-sum game, can Alice risk losing al most 0(1) units, but still be able to win up (T) if Bob plays sub- sub-optimally?
Finally. we numerically evaluate our algorithm in simple EFG environments (Section 5), showing that our results are not merely of theoretical interest. Indeed, our findings con- firm our theoretical insights and demonstrate strong results even when the min-max equilibrium is not full-support.
In this paper, we answer this question in the affirmative by resolving the following fairly more general question from online learning with adversarial linear costs. We explain the reduction in Section 2.
1.1. Related Work
Question 2. Is it possible to guarantee ((1) regret com- pared to a specific strategy while maintaining Ö T() regret compared to any fixed strategy?
In online learning under full information feedback, it is known that one can achieve constant regret against cer- tain comparator strategy while maintaining the near-optimal worst-case regret guarantee as desired in Question 2 (Hutter et al., 2005; Even-Dar et al., 2008; Kapralov & Panigrahy, 201 Koolen, 2013; Sani et al., 2014; Orabona & Pál, 2016; Cutkosky & Orabona, 2018: Orabona, 2019), one notable example being the Phased Aggression template of Even-Dar et al. (2008). This allows us to directly answer Question I affirmatively for NFGs if full information is available, via the reduction in Section 2. While this reduction is direct, we are not aware of any prior work making this connection, even under full full-information feedback.
Question 2 is known to admit relatively simple positive answer in the so-called full-information case (Section 1.1). Crucially, in this work we are interested in the bandit feed- back setting, modeling the fact that Alice only observes the realized cost and not the cost for all actions she could have taken instead. We formalize this learning goal in Sec- tions 3.1 and 4.1.
We present our results in the context of fair zero-sum games. However, they hold far beyond fair, zero-sum, or even two- player games (Question 2): for any sufficiently explorative comparator strategy, one can guarantec constant regret com- pared to it while still having rate-optimal regret compared to any fixed strategy μu, even under bandit feedback. Our results may thus be of independent interest to the online learning community, as we discuss in Section 1.I.
In stark contrast, under bandit senditfeeebaat feedbuck, Lattimore (2015) showed that in multi-armed bandits, O(1) regret compared to a single comparator action (i.e. a deterministic strategy) implies worst-case regret of ?( compared to some other action. This rules out a positive answer to our Ques- tion 2 if the comparator strategy is arbitrary. We show that, perhaps surprisingly, it is possible to circumvent this lower bound under the minimal possible assumption that the com- parator strategy plays each action with non-zero probability 8 (while maintaining the optimal order of /T regret).
Contributions. Our main contributions are the following:
We first devise an algorithm for normal-form games (NFGs) under bandit feedback that interpolates between playing the min-max equilibrium and no-regret learning- We prove that if the min-max equilibrium is supported on the whole action space', then our algorithm indeed satisfies the desiderata of our main question (Section 3.2).
Similar to our motivation, Ganzfried & Sandholm (2015) consider Safe Opponent Exploitation deviating from the min-max strategy while ensuring at most the cost of the min- max value. Different from our work, their algorithms rely on best-responding to some opponent model whenever the algorithm has accumulated enough utility to risk losing it again. While the authors provide safety guarantees, they do
This assumption is also necessary, but can easily be relaxed, the cost of slightly weaker guarantees on when Alice take advantage of sub-optimal play hy Boh. See Remark 3.1.
2

---

Regret Minimization vs Minimax Play
not provide any theoretical exploitation guarantee. In con- trast, our algorithm has provably vanishing regret compared to the best static response against the opponent.
Question 2 Answers Question 1. Now suppose Alice was able to guarantee (OLM). As we explain in Sections 3.1 and 4.1, both for NFGs and EFGs, we can write the expected cost in round t as linear function of the strategy, i.e.
Regarding the extension of our results to EFGs, we leverage relatively recent theoretical advancements regarding online mirror descent in EFGs, most notably Kozuno et al. (2021); Bai et al. (2022). Finally, we refer to Appendix A for an extended discussion of related work.
E [V x²] = E [(u
for some cost vector c¹. Alice can now set / "² = arg min, max, V(H,v) to be a min-max equilibrium.
Since V(n", v) S V*= for fair zero-sum games, the first part of (OLM) implies
2. Preliminaries
In this section, we introduce the relevant notation and ex- plain how Question 2 answers Question 1.
T BB( [0] + 0(1) s 0(1,,
Σ B[V
Notation. As usual, O-notation expresses asymptotic behavior, and Ó-notation hides poly-logarithmic factors. We denote the n-ddimensional simplex by A,, and define [n] := {l.... .1... Moreover, denotes the i-th the stan- dard basis vector of R", and (..-) the Euclidean inner prod- uct. Finally, we write Lg for the indicator function of an event E.
no matter Bob's play. Alice will thus lose at most a constant amount in expectation. Furthermore, if (for example) Bob plays a fixed strategy D' = V E P' that is suboptimal in the sense that min, V(p,v) = - 0, then the second part in (OLM) shows
(Safe) Online Linear Minimization. In Protocol we in- troduce the framework of online linear minimization (Hazan, 2019, OLM) with adversarial costs. In addition to this stan- dard framework, Alice receives special comparator struf- egy o E PP she considers "safe". The motivation for this is that we can later choose μ to be a min-max equilibrium μ², which is safe in the sense of guaranteeing zero expected loss in fair zero-sum games. Alice would like to be essentially at least as good as this comparator strategy.
Σ E [V
S min Σ V(u.)) + +(VT) < -O(T),
and Alice will linearly exploit Bob. We will thus state our results in terms of safe OLM, keeping in mind that the above reduction will automatically answer our initial Question 1.
3. Normal-Form Games
Suppose Alice and Bob repeatedly play a normal-form zero- sum game for T rounds, which means the following. In each round f, they simultaneously submit actions a' E [A], b [B] by sampling from mixed strategies μ² E E vt E Ag. respectively. Alice receives cost Ua+, = (eat, Ues:) and Bob receives cost -Uaa , for some fixed cost matrix U e RAxB with entries in [0,1]. 1]. Alice's expected cost given n², D² V(u², v²) == Eawp' bonp' [Ua,a] = (u², Un²). We consider bandit feedback, meaning that Alice only observes her cost Uatsz v and not the cost of actions she could have taken instead.
Protocol (Safe) Online Linear Minimization
Require: Special comparator μ e P. for round = ,, T do
Alice chooses her next μ² P.
Bob chooses the cost vector c¹.
Alice suffers expected cost (u', .ct.. Goal: R(p²)= < (1) and ma R(x)= S Ö(VT).
We define Alice's expected regret compared to a strategy
E P by
3.1. From NFGs to Online Linear Minimization By defining Alice's cost function as
T R(p)= = Σ E (ut u,,e)]
d' := Ues E TR.
we see that Alice's expected cost is E [V v²) E [Uaeas]] = E E ct)], as a' ~ n². We are thus in the setting of OLM (Protocol 1) over P = AA. Notably, Alice does not observe the full cost function ef but only its entry d' (aaa)= = Un sy at the chosen action (bandit feedback). We
The expected regret max, R(n)= = Σt El'', c') min, Σi= E [K,,") then measures the regret compared to the best fixed strategy z in hindsight. Under safe OLM (Question 2), we understand the problem of simultaneously guaranteeing
MMore generally, Bob is exploitable in this sense if he plays an oblivious sequence of strategies o¹ with min, E, V(n, D²) e (T)) We briefly discuss the adaptive case in Appendix A.
R(y²) S O()), and
max R(n)= S Ö(VT). (OLM) PEP
3

---

Regret Minimization vs Minimax Play
formally consider Protocol for any adversarially picked cost functions c¹. From Section 2 we know that it is now sufficient to set j μr and guarantee (OLM),
plex restricted to A'. This means that if Bob plays subop- timally, Alice can still guarantee to win ((T) whenever these actions allow her to do so (while u¹ itself does not guarantee this), as we indeed observe in Section 5.
Protocol 2 Bandit Feedback over the Simplex (NFGs)
Our Algorithm. In this section, we present Algorithm I and explain its key steps, Our algorithm is inspired by the Phased Aggression algorithm, originally proposed by Even- Dar et al. (2008) for the full-information setting. We briefly note that a direct application of existing full-information algorithms is not possible. This is because, in the bandit setting, Alice only observes her realized cost and not the cost of the other possible actions she could have chosen. We will thus combine the phasing idea of Even- wer- et al. (2008) with appropriately full cost function. Note that the same adaptation would not yield our result for full-information algorithms other than Phased Aggression.
Require: Special comparator μ E AA. for round { = .,, 'I' do
Alice chooses her next action a' ~ n² E AA- D NFG: df Uey Alice suffers and observes cost da'). P NFG: Uat
Bob chooses costs ct E TR.
3.2. Upper Bound
Our first main result shows that if the special comparator strategy lies in the interior of the simplex, we are able to guarantee constant regret to it while maintaining low regret to any strategy at the optimal rate in T. Note that the result concerns the general Protocol 2 and thus covers any NFG, which need not be fair or zero-sum (or even two-player).
seportance-weigheee estimators of the
We now give an outline of Algorithm 1. In every round i, the Phased Aggression algorithm plays convex combination between the comparator strategy μº and the strategy jit chosen by a no-regret algorithm (which runs in parallel). That is, the played strategy is n² = aqt + (1 - a) for some a E (0, 1]. Whenever the algorithm estimates that the comparator μ is a poor choice, it increases a by a factor of two (so that it puts less weight on μz and more on the no-regret iterates) and restarts the no-regret algorithm. We group all rounds according to these restarts and call them phases k- = 1.2..... During each phase, a is constant.
Theorem 3.1. Let 8 E (0. Consider any mixed strategy oe E AA such that μ² (a) 2 for all a E [A], Under bandit feedback (Protocol 2). for any sequence of &t E [0, Algorithm I achieves
R(u9) 1 and max R(x) 10000000000 A
Now consider any zero-sum NFG with min-max max value V If the min-max max strategy μ² is full-support, then Alice can run Algorithm 1. The above theorem and the reduction from Section 2 guarantee that in expectation: Alice will lose at most V* + 1 units while winning S?TT) if Bob plays (oblivious) strategies that are linearly exploitable. In particular, if the game is fair (V* = 0), Alice will lose at most 1 unit in expectation. The latter is guaranteed for instance if the zero-sum NFG is symmetric (i.e. A B and U -.T).
Within this phasing scheme, the specifics of our algorithm are as follows. The no-regret algorithm of our choice is on- line mirror descent (Hazan, 2019, OMD) with the standard KL divergence (plle') == Ea uaaa log(u(a) (a)) as regularizer. In every round t, the algorithm plays its cur- rent action a' ~ ja' and observes its cost (Line 4). It uses this to construct an (unobserved) full cost function (Line 5). The algorithm then performs one iteration of OMD with the estimated costs (Line 11). This procedure is repeated until a new phase is started (Line 6), which happens if the comparator juf is performing poorly under the estimated ts of the current phase.
weiigted estimator ō of the
Lattimore (2015)'s result implies that the assumption on 2 is also necessary. In addition, we show in Theorem 3.2 that a multiplicative dependence on 8-1 is unavoidable. We remark that min-max strategies μz of various zero-sum games are o-bounded away from zero. For example in Rock- Paper-Scissors μ* = (1/3, 1/3, 1/3). More importantly, even when this not the case, we remark the following.
Regarding computation, the OMD update can be imple- mented in closed form as fa*+(()) x (a(())xx(( exp(-r' (a)). We can check the if-condition in Line 6 by directly comput- ing the maximum in O(A) time.
Remark 3.1. Alice can apply the result even in zero-sum games with min-max strategies μ² A that are not full- support. Indeed, she can consider the subset of actions A' : {a E [A]: μ²¹ (a) > 0}. Then, our algorithm run on A' still guarantees R(x²) I O(1), meaning that Alice can lose at most O(1) in fair zero-sum games. A1 the same time, our algorithm guarantees that ETEE EVV v²)] < min Σt= E VV, +O)((TT) where A is the sim-
Regret Analysis. In this section we provide a proof sketch of Theorem 1. We defer the full proof to Appendix B.
We first introduce some notation. We index the variables by their respective phase l 2 1: Phase & lasts from start, to start - 1 and uses linear combinations with at = min(1, 2# 22-1/R) /R) (Lines 7, 9). By design, there are at most
4

---

Regret Minimization vs Minimax Play
Algorithm 1 Phased Aggression with Importance- Weightting
Require: Number of rounds T, comparator margin ö, regret upper bound R t 8-1 /2T log( 77 f V82 log(A)/
OMD learning rates
/ (A)(A)((AT)
1 1: Initialize (a) - (a) +- X for all [A], initialize t- 1/R, start +- 1, +- (counts phase).
2: for round f ,,..., do
3: Alice chooses jz E A. Bob selects cost c'.
D in NFGs: d' = Uee
4: Alice suffers and observes cost ca(a") for a' ~ -p..
5: Alice builds cost estimator (a) + d'(a') {a' a).
(a(a)
6:
if m Ej=stor (2) 10 > 2R and < 1 then k +- k + 1, start 4- 1.41 1. (a) + A for all a E [A].
7:
D If comparator performs poorly, new phase
8:
RReinitialliz OMD
9:
Update a t min {2 1/, 13.
b Increase or for upcoming phase
10:
else
> OMD update
11:
f1-1 t- arg min (1/ (u, (²) + DxL (K)l)))))) with r/ = 1 if 1, and n/' = 1 Play shifted OMD to fe by
12:
tl ap'tt (1 (1-a)) a..
1+ [log2 (R)] phases, where R is known regret upper bound for OMD input to the algorithm. The overall regret is at most the sum of regrets across all phases, and we will thus analyze each phase separately. To this end, let
We are now ready to prove Theorem 3.1. First, consider the case that = is never reached. Note that our cost estimates are unbiased, i.e. E (a)) = caa It is thus suf- ficient if we can bound R²a As there are O(log R)) phases, Lemma 3.1 implies max, R(n) - O(R R). Moreover, the previous two lemmas geometrically balance the regret compared to μ to be most 1, and we conclude. Second, suppose now that a is reached. The final phase will then simply be OMD with standard importance importance-weighting (a.k.a. Exp3), as we put no weight on the special compara- tor μº" While we cannot apply Lemma 3. we can directly bound the remaining expected regret of Exp3 (Orabona, 2019). We can thus use the same argument as before, with one additional phase.
starte--11
R*
Σ starts
(c,
denote the estimated regret during phase k. By convention, start++1 == T + 1 if k is the last phase. The following lemma bounds this estimated regret for phases with a² < 1.
Lemma 3.1 (During normal phases). Let k be such that
k 1. Then for all μ E AA.
(n) S 2R +2 28-1 / log(A) + +2
3.3. Lower Bound
We will now show that regarding the guarantee we provided in Theorem 3.1, a multiplicative dependence on the inverse of the "exploration gap" is indeed unavoidable.
and for the special comparator R² (nO)) < 2
The first part of the theorem establishes a worst-case bound on the estimated regret. Such a bound would normally not be possible for importance-weiggnee cost estimators. In our case, during phases with * < 1, we put constant weight the comparator strategy μº, which in turn is lower bounded by 6 > 0. Our estimated costs (Line 5) will thus be upper bounded, which is a key step in the proof. The second part of the theorem easily follows using the definition of a
Theorem 3.2. Let d E 1/A]. There is a comparator nº E AA with all (a)))) 2 8 such that for any algorithm for Protocol 2 there is a sequence c¹ c.....,c"' d E [0, 1] such that: If RR(()) S O(1), then
max R(1) 2 2(V0-1T -8 8-3/4T1/4). PEAA
The key idea of our proof is that any algorithm with low regret compared い¹ = (1 8, 6) for A actions will need to play action I most of the time if one can information- theoretically not detect that action 2 is. in fact, minimally better. We defer the proof to Appendix B.2. Finally, we remark that if the cost functions are stochastic rather than adversarial, we can match this lower bound up to logarithmic factors, see Appendix B.3.
Next, suppose the algorithm exits phase as the if- condition in Line 6 holds. The following lemma establishes that exiting the phase is justified in the sense that we per- form sufficiently well compared to the special comparator, according to the estimated costs.
Lemma 3.2 (Exiting a phase). Let le be such that a < 1. If Algorithum I exits phase k. then R. (110) E -
5

---

Regret Minimization vs Minimax Play
4. Extensive-Form Games
Assumption 4.1. Tree structure: For any state
In this section, we present our results for EFGs. We start by giving the definition of EFGs, using the notation that appeared in Kozuno et al. (2021); Bai et al. (2022); Fiegel al. (2023a;b), see Appendix C.1 for a brief discussion. For
8h E
Su. there exists unique sequence
01-10 bn-1) leading Sh.
Perfect recall: Let s be such that x(s)= =x(s", Then: - -hhere exists h E [H] such that 8,8' E &Sn.
clarity, we present the !wo-player zero-sum case, although our results readily generalize to arbitrary EFGs.
Let (s1, (,1,a),...;Bh-1 18 be the unique path lead- ing to s and (s), "s.., .......,..... x/ the unique path leading to s'. Then all E 1]: x(5k) x(s)) and aj; = d'g.
Definition 4.1. A two-player zero-sum EFG is tuple (H, H.S. V.A, B, P, V, u), where
The analogous assumplion holds for y in lieu of xc.
there are 2 players, Alice and Bob. A [A] and B = [B] denote their respective sets of possible actions.
Tree structure states that the game proceeds in rounds dur- ing which the players cannot loop back to a previous state. We remark that this also justifies not explicitly indexing the transitions, rewards, policies, and treeplex strategies by steps h to cover non-stationary dynamics. Perfect recall establishes that the players never forget the history of play. They can only consider two states as the same infoset if the observations so far have been the same (Hoda et al., 2010). The latter implies that infosets are partitioned along the horizon, i.e. X' Uhetn An, and the same holds for y and the states.
S denotes the set of states of the game, H E N is the horizon of the game, At stage h E [H], Sn. S denotes the possible states.
P := (po.P) p) is the transition kernel; the game's state is sampled according to Sh+1 ~ p(1]sh, an, by) upon ac- tions (an, bn)) E EA> x B in state 86. E S. The initial state is sampled according to 81 ~ Po E As.
u(s, a, b) E [-1,1] is Alice's random cost (and Bob's reward) for actions (a,b) A x B chosen in state s E S, with mean u(s, a. b).
Alice observes information sets (infosets) from X (1x)= = X). and Bob from Y. Alice's 's infosets are described by a surjective function x: S + X (resp. y: S + y for Bob).
Online Learning in EFGs. Now suppose Alice and Bob repeatedly play an EFG for T' consecutive rounds. In each round t E [T), Alice and Bob select a pair of policies (T T/B) E II x II'. Then a trajectory (sf af, bf uu,....,8f &.r, B/g b/r, is sampled according to the policies (T'A- T/3) and Alice suffers cost Σx= "/, as summarized in Protocol 3.
The idea behind infosets is that Alice has imperfect infor- mation about the state of the game: she cannot differentiate between sates s, s' E that belong at the same infoset, i.e. when ass) = x=s'). ). The same holds for Bob with y in lieu of x. This is reflected in the definition of the policy sets.
Protocol 3 Bandit Feedback over Policies (EFGs)
Definition 4.2. A policy is a mapping T: X' - A.. We denote the set of all such policies by IL. The policy set II' for Bob consists of all mappings n': AB.
Require: A comparator policy T" E II.
for round / 1, ,,..., T, do Alice selects T' E 11, Bob sclects T'B e II'.
We let π (a|x)) denote the probability of playing action
Alice obtains costs Σ uh and observes trajectory (af,af uf...., 2/ 0'H u/z))
a E A in states E S from infoset x = =sss E X. As Alice cannot differentiate between states s, E S from the
same infoset, she must act the same way =(s) = x(s').
Similarly, for Bob we write N² 2b(b)) for y E y
We remark that in EFGs, we are naturally in the ban- dit feedback setting as Alice only observes the trajectory (x), aj, uf,...,,ry "yy d'y u Under Under,ulllinfee call-information feed- back, Alice would observe Bob's actual policy T'B E II'.
Definition 4.3. Given policies (TA, BB) E II x II', the expected total cost for Alice equals
H Σ
wss ans bn)
TB) = E
Remark 4.1 (Importance of bandit feedback in EFGs), In EFGs, bandit feedback is considerably more natural than full-information feedback. This is due to the fact that when playing against Bob, the realized samples are only observed along one single trajectory in the game tree. Observing full information would thus mean knowing Bob 's counterfactual policy in states that have never been visited during play, which is not realistic.
where (sh, On, by.) are the state and actions at stage h E [H] via ag ~ =T(-po(s)) by ~ TB(-))(s)),, and 8h-1 p(- (s-s an, bb).
For the remainder of the section, we make the following as- sumptions, which are standard in the EFG literature (Kozuno et al., 2021; Bai et al., 2022; Fiegel et al., 2023a;b).
6

---

Regret Minimization vs Minimax Play
4.1. From EFGs to Online Linear Minimization
Theorem 4.1. Let 8 E (0, 1/A). For any special compara-
As mentioned, we once more resort to the more general OLM problem. Yet this time, our strategy polytope will be the so-called treeplex P = T rather than the simplex. The following definition provides an equivalent characteri- zation of a policy. It will allow us to view the expected cost ( T as a (bi-) (bi-)r function (Hoda et al., 2010).
tor nº E T such that pf 0) 2 6 for all x, o, Algorithm 2 achieves (for any e 's from Equation (2))
R(pF) 1 and
max NET
R(H) S SŌ 6(55 105500110H (5HTHT
Definition 4.4. A vector Ps E R A belongs to the treeplex T iff for all oh E Nn and a E A.
If the EFG is fair zero-sum game, Alice can now choose min-max equilibrium Jt" = p² as the comparator. If μ² has full support, the reduction from Section 2 then shows that Alice achieves the best of both worlds guarantee from Question
u(an: a) 2 0,
EanEAH(TTN an) = 1( (1-1);
Remark 4.3. The dependence on X is as good as desired in the sense that there is a VX lower bound in the unconstrained case. The dependence on H is less crucial for many relevant EFGs, as we often have X = A# and so H is a logarithmic See Bai el al. (2022).
where (#R-1, is the unique predecessor pair reaching Tn- We consider a() for the root by convention. We define the treeplex T' over Bob's 's infosets Y' analogously.
Remark 4.2. There is the following equivalence between Definitions 4.2 and 4.4, Given a policy π E II. we can de- fine a unique Pt E by (r 0n) = II T map ), where the (IZ, ( form the unique path (Ih, an). Vice- versa, given μ. T, we can recover the corresponding policy via Tz(a|x) p(z,a)) Ee ulx, a'). The same equivalence holds between Bob's 's policies II' and treeplex strategies T'.
Our Algorithm. Algorithm 2 is similar to our algorithm for the simplex. It combines the Phased Aggression scheme with importance-weighheed OMD. However, in the EFG case. we have to generalize these notions to the treeplex.
In particular, we use OMD with the so-called dilated KL. divergence as regularizer (Line 11). As we will see in the regret analysis, to this end it is crucial that use an un- balanced dilated KL divergence D (Kozuno et al., 2021) in the phases with a < 1 and a balanced KL divergence Dhal (Bai et al., 2022) if a = 1 is reached. In Appendix C.2, we formally define the divergences and confirm that they allow for an efficient closed-form implementation. This is crucial as we want to avoid costly projections onto the treeplex by any means. Moreover, we can efficiently check Line 6 via standard dynamic programming over the set of policies (or solving an LP over the treeplex).
By convention, we thus identify policies (T'..T')) with their corresponding treeplex strategies (u²; v²) and write V(n', va) for Alice's expected cost. The following lemma (Kozuno et al., 2021) shows that this definition indeed allows us to view Protocol 3 as a (safe) OLM problem (Protocol 1).
Lemma 4.1. For any state 8 E Sn infoset x = x(s) E X, and action a E A, let ($1, bi, ..... 8h-1, b be the unique path leading to s. Let p(s) == Po(s1)
an, ), and consider
d(x,a)== = Σ p(s) v' (v((),)) m(s, b). (2)
Regret Analysis. Our analysis follows a similar argument as in Section 3 and we defer the proofs to Appendix C.3. The main technical challenge is to transfer the regret bounds for importance-weigee weighted OMD from the simplex (with KL) to the treeplex T (with dilated KL).
s: =(,)=x, BEB
Then (p, = (u,'') for all μ TT
Alice does not observe the full cost function c', as we are in the bandit feedback setting. Yet, this lemma establishes that Protocol over the treeplex P T covers EFGs. Thus, it is sufficient to solve the safe OLM problem (OLM).
In addition, we now require careful analysis to obtain a mild dependence on the number of infosets X and actions A, in the following sense. First, when upper bounding the estimated regret in analogy to Lemma 3.1 (a < 1), we analyze OMD with the unbalanced dilated KL divergence by adapting the argument of Kozuno et al. (2021) to our importance-weighinnn Using the (more sophisticated) bal- anced KL here would introduce factor of VA. Second, once a = 1 in the final phase, we analyze the expected regret of balanced OMD instead, by adapting the argument of Bai et al. (2022) to our cost esti- mators. Using the unbalanced divergence would introduce an extra factor of vX, which can be prohibitively large.
4.2. Upper Bound
As in the simplex case, our Algorithm 2 guarantees Equa- tion (OLM) for any policy of E T that is d-bounded away from the boundary of the strategy polytope. Once more, we can resort to a restricted action set to relax this assumption (Remark 3.1). The result itself applies to any EFG with tree structure and perfect recall and is not restricted to the zero-sum or two-player case, since we can simply modify the costs in Equation (2) accordingly.
additional undesired
7

---

Regret Minimization vs Minimax Play
Algorithm 2 Phased Aggression with Importance- Weihhting for EFGs
Require: Number of rounds T, comparator margin 8, regret bound R + 8-1 / VS log A)T, learning rate +
X log( log(A)/(SHPT), balanced learning rate < VXAlog(A)((HTT)
1: Initialize (# a) =1²² (Nh, < R (h [M], Th E Xn, a A), < 1/R, start <- 1, <- (counts phase).
2: for round f ,,..., , do
3: Alice chooses u² E TT Bob selects strategy v¹ E T
> and thus cost c' via Equation (2)
4: Alice obtains costs Σ uh, observes trajectory (+f, aj uj ...... In dn ug))
D VV v²) expectation
) ( 5: Alice builds cost estimator d' (#h. t- 1[(2)
())
/ (ax.o)
6:
if maxxxe Ej=stm (2) pb) > 2R and a < 1 then
7:
start 1 + 1, k 1.
If comparator performs poorly, next phase b. Initialize uniform policy b Increase a for upcoming phase > OMD update
8:
a) Ab
1 (h E [H] T/h An, E A).
9:
Update min
f2 /R, 1}.
10: else
11:
arg mighte (n c²) + () arg mighen (T (1,, 2t) + Dbal (H(l(²))
(if a < 1), (if a = 1).
11+ t apt 1 + (1 (1-a) ap
Play shifted OMD to je by
4.3. Lower Bound
Remark 5.1. The min-max equilibriim Kuhn Poker is not full-support (6 0 in Theorem 4.1). As seen in Remark 3. 3.1, we can easily circumvent this issue by considering only the actions in the support of the equilibrium. For Kuhn Poker, this results in = 1/3. Algorithm is then still guaranteed not to lose anything while being able to compete with the best response within the support of the equilibrium.
As in the case NFGs, we show that our guarantees for Algorithm 2 are close to being tight for EFGs of arbitrary depth. Our proof reduces EFG of depth H to the simplex case from Theorem 3.2. See Appendix C.5 for the proof.
Theorem 4.2. Lei A 2 2, H 2 1, and 5 E (0, There exists an EFG of depth H with X = ((A such that for any μt E T with minz,a 1f (x. a) = 8, there is an adversary such that for any algorithm: Rf < (1), then
We consider the following baseline algorithms Alice could play over T rounds of Kuhn poker:
max R(n) 2 8-33/1/4 TET
1) play the Min-Max equilibrium x² in every round; or
2) run OMD with dilated KI.; or
5. Experimental Evaluations
3) run Algorithm 2 with comparator policy x*.
We experimentally compare Algorithm 2 for EFGs to the standard OMD algorithm with dilated KL (Kozuno et al., 2021) as well as to minimax play. Our evaluations con- firm our theoretical findings, revealing that Algorithm 2 can achieve the best of both no-regret algorithms and minimax play. They also show that our motivating question from Sec- tion is indeed of practical relevance. We provide further details and evaluations in Appendix D.
We consider two types of experiments: First, we run the three algorithms against each other to check which of the algorithms risks losing units to others (All vs All). Second, we evaluate how well each algorithm allows Alice to exploit exploitable strategies (All vs Exploitable Strategies). We repeat each experiment times.
All vs All. In Figure we plot the total amount (of units) each algorithm wins. As Figure 2 shows, both Min-Mat -ax and Algorithm never incur losses while both gain a significant amount against OMD. Indeed, (symmetrized) Kuhn poker is symmetric zero-sum game, the min-max equilibrium is guaranteed not to lose. The same holds for our Algorithm 2. In contrast, a no-regret algorithm such as OMD can lose up to O(VT) units. Interestingly, it does lose a similar amount against our Algorithm 2.
We consider Kuhn poker (Kuhn, 1950), which serves as a simple yet fundamental example of two-player zero-sum imperfect information EFGs. Kuhn poker a common 3-card simplification of standard poker, where each player selects one card from the deck (Jack, Queen, King] without replacement and initially bets one unit.3
Kuhn Poker.
Phttps://en kipeiii htapppeda.or/////eeeeee.e org/ wiki Kuhn _ooer
8

---

Regret Minimization vs Minimax Play
100
100
100
50
-50
100
600
600
Alg. 2 vs Min-Max
OMD Min-Max
Alg. 2 OMD
Figure 2: All vs all comparison for T 1000 rounds. The x-axis displays the round t, and the y-axis displays how much the respective algorithm (Min-Max, OMD, Algorithm 2) gained from the other.
150
Mir-llax
150
Min Mn-Max
200
100
40
Curs
Camuativ
Cumulttiv
-20
0
200
400
600
800
1030
200
450
600
BG0
1800
200
400
600
800
1000
Round
All vs BluffJ
All vs RaiseKQ
All vs RandMinMax
Figure 3: All Bob comparison for T = 1000 rounds. The x-axis displays the round t, and the y-axis displays how much Min-Max, OMD, and Algorithm 2 gained from the second algorithm so far. The y-axes have varying scales for readability.
All vs Exploitable Strategies. We now compare the per- formance of Min-Max, OMD and Algorithm 2 against the following reasonable but suboptimal strategies. The goal is to understand their ability to exploit weak strategies. We consider:
6. Conclusion
In this paper, showed how provably exploit suboptimal strategies with essentially expected risk in repeated zeto- sum games by combining regret minimization and minimax play. More generally, we believe that our novel results for adversarial bandits leading to these guarantees may be of independent interest. We hope that our work inspires future research on safe online learning. including settings like convex-concave games, learning with feedback graphs, and establishing no-swap-regret guarantees.
a) BluffU: Bob plays the min-max equilibrium, except that he bets (bluffs) when he has Jack;
b) RaiseKQ: Bob raises/calls if and only if he has a King Queen, and checks/folds otherwise;
c) RandMinMax: Each round, with probability 0.2, he plays the uniform strategy, and else the min-max one.
Impact Statement
In Figure 3 we present the amount (of units) each algorithm wins against these exploitable strategies. We first consider All BluffJ & All RaiseKQ. Algorithm plays conser- vatively and gains an amount similar to Min-Max until it takes off and starts exploiting Bob ncar-optimally, as OMD would. OMD, in turn, first loses a certain amount money and only matches the gain Min-Max after exploring suf- ficiently, then having the same slope Algorithm The min-max equilibrium itself does not exploit BluffJ all and exploits RaiseKQ sub-optimally. In these cases, our algorithm suffers neither of the two drawbacks of losing money or not exploiting the weak strategy. Finally, in All vs RandMinMax, our Algorithm 2 improves slightly over Min-Max. OMD gains at the same rate after losing an initial amount to its opponent.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
A Acknowledgments
Adrian Müller would like to thank Gergely Neu for previous discussions regarding the stochastic case. Stratis Skoulakis supported by the Villum Young Investigator Award (Grant no. 72091). 1). This work is funded (in part) through PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. This work was sup- ported by Hasler Foundation Program: Hasler Responsible (project number 21043). Research was sponsored by the

---

Regret Minimization vs Minimax Play
Army Research Office and accomplished under Grant Number W91 ANN--24-1-0048 This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 1200011.
Cai, L.,, Weinberg, S. M., Wildenhain, E., and Zhang, S. Selling multiple no-regret buyers. In International Conference Web and Internet Economics, pp. 113-129. Springer, 2023.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
References
Ananthakrishnan, N., Haghtalab, N., Podimata, C., and Yang, K. Is knowledge power? on the (im) possibility of learning from strategic interaction. arXiv preprint arXiv:2408.08277 08222, 2024.
Chen, Y. and Lin, T. Persuading a behavioral agent: Ap- proximately best responding and learning. arXiv preprint arXiv:2302.03719 2023.
Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. In Con- ference On Learning Theory, pp. 1493-1529. PMLR, 2018.
Arunachaleswaran, E. R., Collina, N., and Schneider, Pareto-optimal algorithms for learning in games. In Pro- ceedings of the 25th ACM Conference on Economics and Computation, pp. 490-510, 2024.
Auer, P., Casa-eeaaBane Bianchi, N., Freund, Y., and Schapire, E. The adversarial multi-armed
Damer, S. and Gini, M. Safely using predictions in general- sum normal form games. In Proceedings of the 16th conference on autonomous agents and multiagent systems, pp. 924-932, 2017.
Gambling in a rigged casino: bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-331. IEEE, 1995.
Deng. Y., Schneider, J., and Sivan, B. Strategizing against no-regret learners. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Auer, P., Jakseh, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained mdps. arXiv preprint arXiv:2003.02/89 2020.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
Even-Dar, E., Kearns, M., Mansour, Y., and Wortman, J. Regret to the best vs. regret to the average. Machine Learning, 72(1):21-37, 2008.
Bai, Y., Jin, C., Mei, S., and Yu, T. Near-optimal learning of extensive-form games with imperfect information. In International Conference on Machine Learning, pp. 1337- 1382. PMLR, 2022.
Fan, Z., Kroer, C., and Farina, G. On the optimality of dilated entropy and lower bounds for online learning in extensive-form games. arXiv preprint arXiv:2410.23338, 2024.
Bernasconi, M., Cacciamani, F., Castiglioni, M., Marchesi, A., Gatti, N., and Trovò, F. Safe learning in tree-form sequential decision making: Handling hard and soft con- straints. In International Conference on Machine Learn- ing, pp. 1854-1873, PMLR, 2022.
Farina, G., Kroer, C., and Sandholm, Online convex opti- mization for sequential decision processes and extensive- form games. In AAAI Conference Artificial Intelli- gence, 2019.
Bernasconi-de Luca, M., Cacciamani, F,, Fioravanti, S., Gatti, N., Marchesi, A., and Trovò, Exploiting oppo- nents under utility constraints in sequential games. Ad- vances in Neural Information Processing Systems, 34: 13177-13188, 2021.
Farina, G., Schmucker, R., and Sandholm, T. Bandit linear optimization for sequential decision making and extensive-form games. AAAI Conference on Artificial Intelligence, 2021.
Braggion, E., Gatti, N., Lucchetti, R., Sandholm, T., and Von Stengel, B. Strong nash equilibria and mixed strate- gies. International Journal of Game Theory, 49:699-710, 2020.
Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Adapting to game trees in zero-sum imper- fect information games. International Conference on Machine Learning, pp. 10093-10135. PMLR, 2023a.
Brown, W., Schneider, J., and Vodrahalli, K. Is learn- ing in games good for the learners? In sevethh Conference on Neural Information Processing Systems, 2023. URL https://openrevierr net/Eorunt id= [d=jR2FkqM66S
Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Local and adaptive mirror descents in extensive-fome games. arXiv preprint arXiv:2309.00656 2023b.
10

---

Regret Minimization vs Minimax Play
Ganzfried, S. and Sandholm, T. Safe opponent exploita- tion. ACM Transactions Economics and Computation (TEAC), 3(2):1-28, 2015.
Koolen, W. M. The pareto regret frontier. Advances in
Neural Information Processing Systems, 26, 2013.
Kozuno, T., Ménard, P., Munos, R., and Valko, M. Model- free learning for two-player zero-sum partially observ- able markov games with perfect recall. arXiv preprint 1.Xiv:2106.6625 2021.
Ganzfried, S. and Sun, Q. Bayesian opponent exploitation in imperfect-information games. In 2018 IEEE Conference on Computational Intelligence and Games (CIG). pp. 1-8. IEEE, 2018.
Kuhn, H. W. A simplified two-person poker. Contributions to the Theory of Games, 1(97-103):2, 1950.
Garcelon, E.,, Ghavamzadeh, M., Lazaric, A., and Pirotta, M. Conservative exploration reinforcement learning. In International conference on artificial intelligence and statistics, pp. 1431-1441. PMLR, 2020.
Lanctot, M., Waugh, K.,, Zinkevich, M., and Bowling, M. Monte carlo sampling for regret minimization in exten- sive games. Advances in neural information processing systems, 22, 2009.
Ge, Z., Xu, Z., Ding, T., Meng. L., An, B., Li, W., and Gao, Y. Safe and robust subgame exploitation in imperfect in- formation games. In Forty-first International Conference on Machine Learning, 2024.
Lattimore, T. The pareto regret frontier for bandits. Ad- vances in Neural Information Processing Systems, 28, 2015.
Guruganesh, G., Kolumbus, Y., Schneider, J., Talgam- Cohen, I., Vlatakis Vlatakis-Gkaragkon Gkaragkounis, E.-V., Wang, J. R., and Weinberg, S. M. Contracting with learning agent. arXiv preprint arXiv:2401.16199 2024.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Liu, M., Wu, C., Liu, Q., Jing, Y., Yang, J., Tang, P., and Zhang, C. Safe opponent-exploitation subgame refine- ment. Advances in Neural Information Processing Sys- tems, 35:27610-27666 27622, 2022.
Haghtalab, N., Podimata, C., and Yang. K. Calibrated stack- elberg games:
Learning optimal commitments against calibrated agents, Advances in Neural Information Pro- cessing Systems, 36, 2024.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint viola- tion for constrained mdps. Advances in Neural Informa- tion Processing Systems, 34:17183 14417183-1719,, 2021.
Hazan, E.
Introduction online convex optimization. CoRR, abs/1909.052000 2019. URL http://arxiv: org/ httg/ab//11e /aabb///999..00 19w.1/9999.000....
Maiti, A., Jamieson, K., and Ratliff, L. J. Logarithmic regret for matrix games against adversary with noisy bandit feedback. arXiv preprint arXiv:2306.13233 2023.
Hoda, S., Gilpin, A., Peña, J., and Sandholm, T. Smoothing techniques for computing nash equilibria of sequential games. Math. Oper. Res., 35(2):494-51,, 2010.
Mansour, Y., Mohri, M., Schneider, J., and Sivan, B. Strate- gizing against learners in bayesian games. In Conference on Learning Theory, pp. 5221-5252. PMLR, 2022.
Hutter. M., Poland, J., and Warmuth, M. Adaptive online prediction by following the perturbed leader. Journal of Machine Learning Research, 6(4), 2005.
Orabona, F. A modern introduction to online learning. arXiv preprint 191. 19119 2019.
Jakobsen, S. K., Sørensen, T. B., and Conitzer, V. Timeabil- ity of extensive-form games. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 191-199, 2016.
Orabona, F. and Pál, D. Coin betting and parameter-fres on- line learning, Advances in Neural Information Processing Systems, 29, 2016.
Kapralov, M. and Panigrahy, R. Prediction strategies without loss. Advances in Neural Information Processing Systems, 24, 2011.
Osborne, M. J. and Rubinstein, A. A course in game theory. MIT Press, 1994.
Ponsen, M. J. V., de Jong, S., and Lanctot, M. Computing approximate nash equilibria and robust best-responses using sampling. J. Artif. Intell. Res., 42:575-605, 2011. URL https: http:://ap...mmmtttcccooooo semanticschola.. org org/CorppusD::634555
Kolumbus, Y. and Nisan, N. How and why to manipulate your own agent: On the incentives of users of learning agents. Advances in Neural Information Processing Sys- tems, 22880-280944 2022a.
Kolumbus, Y. and Nisan, N. Auctions between regret- minimizing agents. In Proceedings of the ACM Web Conference 2022, pp. 100-111, 2022b.
Sani, A., Neu, G., and Lazaric, A. Exploiting easy data in online optimization. Advances in Neural Information Processing Systems, 27, 2014.

---

Regret Minimization vs Minimax Play
der Hoeven, D., Cutkosky, A., and Luo, H. Comparator- adaptive convex bandits. Advances in Neural Information Processing Systems, 33:19795-19804, 2020.
Von Neumann, J. and Morgenstern, O. Theory of games and economic behavior: 60th anniversary commemorative edition. In Theory of games and economic behavior. Princeton university press, 2007.
Wu, Y., Shariff, R., Lattimore, T., and Szepesvári, C. Conser- vative bandits. In International Conference on Machine Learning, pp. 2254-1262. PMLR, 2016.
Zhang, B. and Sandholm, T. Subgame solving without common knowledge. Advances in Neural Information Processing Systems, 34:23993-24004, 2021.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete informa- tion. Advances in neural information processing systems, 20, 2007.
12

---

Regret Minimization vs Minimax Play
A. Further Related Work
Safe Opponent Exploitation. While there have been some approaches to safe learning in games (Ponsen et al., 2011; Farina et al., 2019; Zhang& & Sandholm, 2021; Bernasconi-de Luca et al., 2021; Bernasconi et al., 2022: Ge et al., 2024), all these works are fairly different from our learning problem. Related to Ganzfried & Sandholm (2015); Ganzfried & Sun (2018), the works of Damer & Gini (2017); Liu et al. (2022) provide algorithms that interpolate between being safe and exploitive through a specific parameter. However, these algorithms may incur up to ((T') regret compared to the best fixed strategy in hindsight. Recently, Maiti et al. (2023) proved the first instance-dependent poly-logarithmic regret bound for noisy 2 x 2 NFGs, which naturally relates to our desired regret bound. However, such bounds become vacuous when the game matrix does not have pairwise distinct entries and assume to observe the opponent's 's action (which corresponds to full information in our feedback model).
Exploiting Adaptive Opponents. If Bob is oblivious and plays a fixed sequence of (mixed) strategies. then any regret Alice incurs is potential utility she could gain by playing a no-regret strategy (e.g., the best-of-both-worldd strategy we present). However, if Bob is adaptive, switching to a no-regret strategy does not necessarily allow Alice to recover additional utility (Bob could, for example, react to this by playing his minimax strategy). There is a line of recent work (Deng et al., 2019; Mansour et al., 2022: Kolumbus & Nisan, 2022b;a; Brown et al., 2023: Cai et al.. 2023; Chen & Lin, 2023; Haghtalab et al., 2024; Ananthakrishnan et al., 2024; Guruganesh et al., 2024; Arunachaleswaran al., 2024) on how to play against sub-optimal adaptive strategies (e.g. other learning algorithms) in various settings, although almost all of this work only pertains to general sum games. It is an interesting open question to understand to what extent we can obtain similar boot-ol-both-worldds results for adaptive opponents in zero-sum games.
Comparator-Adaptive OL with Full Information. In online learning (OL) under full information feedback, Hutter et al. (2005); Even-Dar et al. (2008); Kapralov& & Panigrahy (2011); Koolen (2013); Sani et al. (2014) establish (with various emphases) that safe OLM over the simplex in the sense of Equation (OLM) is possible. Using so-called parameter-fre free methods from the online convex optimization literature instead (Orabona & Pál, 2016; Cutkosky & Orabona, 2018; Orabona, 2019, c.g.), one can (after a simple shifting argument) achieve similar guarantees in the full information setting. For our purposes, the most notable of the above algorithms is the Phased Aggression template of Even-Dar et al. (2008), as it is the only one we were able to adapt to the bandit feedback setting while maintaining the rate-optimal regret guarantee. While the application of the above type of algorithms fair zero-sum (normal-form) games is direct (Section 2). we are not aware of any prior work making this connection, even under full-information feedback.
Comparator-Adaptive OL with Bandit Feedback. Lattimore (2015) establishes a sharp separation between full informa- tion and bandit feedback. The author shows that (()) regret compared to a single comparator action implies a worst-case regret of ((AT)) for some other action. This rules out algorithms that resolve question even in the simple normal-form case under bandit feedback. The key to this lower bound is that the algorithm has to play the special comparator essentially every time, thereby not exploring any other options (as the comparator strategy is deterministic) and thus not knowing whether it is safe to switch the arm. The minimal assumption we can make on the comparator strategy is thus that it plays every action with a non-zero probability. In addition to the mentioned works from the online convex optimization literature, van der Hoeven et al. (2020) remarkably analyzes bandit convex optimization algorithms that adapt to the comparator. However, unlike in the full information case, is not possible to turn them into an algorithm for safe OLM (as the shifting argument one can use for full-information parameter-free methods like Orabona & Pál (2016); Cutkosky & Orabona (2018); Orabona (2019) does no longer work under bandit feedback).
Relation to Safe Reinforcement Learning. closely related line of work that of conservative bandits (Wu et al., 2016) and conservative RL (Garcelon al., 2020). In conservative exploration, algorithms are designed obtain least a (1-a)-fraction -fraction of the return of comparator, which in motivating example, however, means that the algorithm may suffer a linear loss of in the worst case. We thus believe that independently of our motivation from game-theoretic viewpoint, our results nicely complement existing OL literature. In constrained (or safe) reinforcement learning (Badanidiyuru et al., 2018; Efroni et al., 2020), both the regret and the cumulative violation of a constraint are considered. However, even in the stochastic case the goal of constant regret compared to some known strategy can only be realized if there exists a strategy with a strictly larger return (Liu et al., 2021) for the environment, and in the adversarial case even this reduction fails.
OL in (Extensive-Form) Games While online learning (OL) in NFGs can readily be reduced to the problem of learning from experts becomes more difficult in the case of EFGs (Osboree & Rubinstein, 1994) due to the presence of (imperfectly observed) states and transitions. ofate-of-the-arr art algorithms for no-regret learning in EFGs are based on online mirror descent (OMD)
& Lugosi, 2006) (full information) or multi-armed bandits (Lattimore & Szepesvári, 2020), it
13

---

Regret Minimization vs Minimax Play
the treeplex, which leads near-optimal regret bounds in the full information setting (Farina et al., 2021; Fan et al., 2024) and the bandit setting (Farina al., 2021; Kozuno al., 2021; Bai al., 2022; Fiegel al., 2023a). Alternative approaches are based counterfactual regret minimization (Zinkevich al., 2007; Lanctot et al., 2009), which however do not guarantee bound on the actual regret (see Bai et al. (2022, Theorem 7)).
B. Deferred Proofs for Normal-Form Games B.1. Upper Bound
First, note that our cost estimates are unbiased, i.c. E [a) = E [c'()), and [((2., = EE u²) Fi-I]]
[[' | E [c' (a')), where Ft the o-algebra induced by all random variables prior to sampling a'. Further, WLOG assume that the cost functions are bounded via c [0, 1| The reduction from NFGs with matrix entries Ua,6 [-1, then simply via et (a) (1 /22, where the shifting and scaling does not change the regret bound. By convention
start&+1 T + 1 if & is the last phase.
Theorem 3.1. Let 6 & (0, 1/A]. Consider any mixed strategy je E E such that (= 2 for all E [A]. Under bandit feedback (Protocol 2), for any sequence of c' E [0, 1]A, Algorithm achieves
max R(u) S (5
R(n0) 1 and
AEAA
Proof. Case 1: not reached. Suppose first the algorithm ends in phase k < 1 + log2 (R) at time step T. By Lemma 3.1, w.r.t. any comparator
Σ (6 (c, - (2R+2) k O(Rlog(R))
All previous phases must have been exited, so by Lemmas 3.1 and 3.2 we have
T
k-1
(e,
12)) 5 2h-
Σ
2 2h (2*-1-1) =1.
[=1
1=1
Taking expectation yields the claim.
Case 2: is reached. Next, suppose the phase a was reached and simply Exp3 was in the final phase k. As before
starty -1
(d, - 11) S 2 (R)log(()).
For the final phase, note that Algorithm plays Exp3 for < T rounds, with uniform initialization. By the standard Exp3 analysis (Orabona, 2019, Sec. 10.1), this phase has expected regret
log(A) + _AT AT <A
E
Σ
(d, - 1u)
8-1 /olloo/AAAA R.
(4)
(=stait++1
/
2log(A) A) and 5 < 1/A. Thus for any comparator μ E AA have AT
since
(e 11 11) s (((Roo)(R).
E
Finally, for the special comparator note that all phases 1 < l have been left and thus by Lemma 3.2 and Equation (4)
T
k-1
E
Σ
(c', u² -10 < R -
Σ
24 R- (2k-1 1) < 1,
==1
where the last step used that & min(1, 21,22-1/A1 RR and thus 2
14

---

Regret Minimization vs Minimax Play
Recall that
starte+41 -1
+ -1
starte+1 -1
(u):
(1)
Σ
Ce 1 u) a
Σ
(c' - 11) + +(1 (1-a*)
Σ E-statt
(e, 1n)
(5)
sstart
smstarty
measures Alice's estimated regret.
Lemma 3.1 (During normal phases). Let le be such that a* < 1. Then for all E A
(x) 2 + 28- / 2 log (A) + +2,
for the special comparator R&t (x²) < 2
Proof. WLOG suppose that R = 2" is power of 2, else we can run the algorithm for I such that R is the next largest power of two and pay a constant factor in the regret. For the first term Equation (5), we analyze OMD to bound +1 (c', fil - p)) almost surely, making use of the fact that èt is bounded. Indeed, recall
2t starly
c'(a")
1 1 fa' = =a} s p²(a) (((a)
(a))
We have a = 2 < (10 1/2,
1 (a) < (a)a) a²) (1 a (a) S
2
(a)
8"
Moreover, čt is zero outside the visited a². Thus, by Lemma B.I, almost surely for first term in Equation (5)
starte (d' -)
log(A) 2nI8 2-8' (2T R.
(6)
n
statt
For the second term in Equation (5), note that since the if condition may only hold at t' starts+1 1.
starle-11
claa)
(e n) 22
(1
5 +
(7)
imstarly
Linearly combining Equations (6) and (7),
start
start 11 -1
R²(1)) (1) =
(e - n) + (1 a*)
a
Σ
(e < 22
t starts
L= starts
for any For the special comparator, by Equation (6)
starte-1-1
starte41 -1
(x()) a
Σ s=stare
(C,
( -2²) + (#
Σ t=statt
(2 p0) S (2"-1/R)R- 2
Lemma B.1 (OMD with bounded surrogate costs). Let n > O, and L. > 0. Let (E),, be cost functions such that for all t, 0 < (a) < L (for all a), and moreover é' (a) = 0 if + a' for some arbitrary d'. Set p (a) = 1/A and consider the scheme 4 11 = arg An (1, e² + D( ( for < T'. Then we have for all E Aa
Tr
n1 6²) log(A)
Σ
(at
1TT
2
15

---

Regret Minimization vs Minimax Play
Proof. From Orabona (2019, Sec. 10.1), find that a.s.
T 1)
T
log( A)
log(A) (a))2 x (a)(c(a)) 1
log(A) + 2 L
Σ
+
2
7
2
11
1=1
Lemma 3.2 (Exiting a phase). Let & be such that 8 < 1. If Algorithm exits phase k, then R*C) S -2h-1
Proof. At t s 1 the if condition implies maxuEAA Σ, =jsstrt -1 (e), pb (f 11) > 2R, when let μ¹ be maximizer, we find
sturt +-
Mtrtl++1 +1
(0 - )1)) =0
Σ
(e - 1C)
starle+11
starts
(, n²) + a
Σ t=start
(6' 1e)
statt
Sa R + a (-2R)
2*
where we used Equation (6) the last inequality.
B.2. Lower Bound Theorem 3.2. Let 8 E (0,1 There is a comparator pº AA with all pf(a) 2 5 such that for any algorithm for Protocol 2 there is sequence c² ,...,c'' cT j0, 11ah such that: If R( - 01), then
max R(x) 2 1(V0-17 8-3/4/1144). A
Our lower bound becomes vacuous in the regime where 5 < O(T=1), which is when a direct application of Lattimore (2015) shows a trivial (2(T) lower bound.
Proof. It is sufficient to prove the lower bound for A = 2 actions as we can assign the same distribution to all but one action. We prove a lower bound for stochastic cost functions, which immediately implies the same bound for adversarially chosen costs. Consider the following setup with two different environments. The first action deterministically gives cost C₁ = 1/2 in both environments. In the first environment (-), action two samples costs according
Ber(? -TT distribution with expected cost c = - -711/2 We will choose > 0 later and for now, only require y < 2 / in order for the sampling to be well-defined. Symmetrically, in the second environment (+), action two samples costs according to Ber( + 1/21/2 distribution with expected cost c+ 1 1//-1 We consider the case that the special comparator is μz (1 6, 8, E Ag. In the following, R(4) denotes the regret compared to μ E A in the worst environment. We fix arbitrary algorithm and index regret and expectation with + to indicate which probability space (environment) are referring to.
Now let N₂ be the number of times action two is chosen during the T interactions. The requirement on the regret w.r.t the special comparator (together with the standard regret decomposition (Lattimore & Szepesvári, 2020, Sec. 4.5)) shows
1 2 R(p9) 2 (+) E+ [Na] (+7I 1/(+
and thus
E. [Na] 1111// 8T.
16

---

Regret Minimization vs Minimax Play
Plugging this into Lemma B.2, we have (if 7 2v2
[- +
1T12 + 6T) + +TV2 -7
$- + 8T + TVV +8/1211/3
---1/112 +T + + 2/551/277
Using this in the regret decomposition on (-), we see for the second action E2 = (0, E A
R(e2) (e2)
2 + 8T + (3)
T (-7T-1123)
2 1 8/T - 228') + 1/11/2
(1 8)7 v22012222) T2/2 /27
We can now choose = 100 062 for a sufficiently small absolute constant e to show that
R(e2) 2 2 2 - 0 0(5-3//411/4)
(8)
This bound holds when y 1 12 i... 8 2 cTT for some large enough absolute constant e'.
2/2
Lemma B.2 (Entropy inequality Bernoulli,, In the setup of Theorem 3.2, we have
112222
E- N22 <E N2) + T
(TT-1/2)2 E+ [N2].
In particular for y < _T2/ we have E_ [N2] S E_ [N2]] + 2E+ [N2 1/2.
2V2
Proof. Via Pinsker's and the chain rule for the KL divergence (c.f. Auer et al. (1995) and Lattimore (2015, Appendix))
E_ [2 - E+ [N2] S T
2 E+ [N2] XL(X)
where ~ Ber(} + c) and Y Ber(} - c) for c = 7T 1/2 We conclude by computing
1 +c
E log
KL(XI|Y)
2 +
log
+
2
1
E
+ E
+
1
+
1
é
2 +
1
+
=2c
2
2
2
+
2
1
26
2c
2
B.3. The Stochastic Case As claimed the main part, we now sketch how the Õ(V5-1T) lower bound from Section 3.3 can be matched (up to logarithmic terms) if the costs are stochastic and not adversarial. This improves slightly over our result for the adversarial case.
17

---

Regret Minimization vs Minimax Play
Theorem B.I. Let 8 (0, 1) and consider Protocol 2 but where all et (a) qa are i.id for some fixed distribations qa with support in [0, 1). Then there is algorithm such that for any specified pº E A with all p((a) 8 and all distributions q. we have
R(4) 21 and
mAx R(4) I =0 llgg(T)) (TT -5- 5-31og(T)) PEAA
For E [A], let the a-th action's reward distribution qa have mean 1 - Max and write for the corresponding vector. We thus consider maximization of the rewards c that have means m. This is just for convenience to better highlight the relation of our algorithm to the classic UCB algorithm (Lattimore & Szepesvári, 2020). As for the rewards, we index the entries of strategy μ E A as paa = p(a). Fix an arbitrary a* E arg max, ma- The (random) pseudo-regret of the algorithm is
R
Σ (ma- (p', m)))
Algorithm. Construct m² = (mi,... maa)). गा (m ....... for the actions after playing and observing rounds. Formally,
) to be the vectors of lower and upper confidence bounds
m == m by
m = m + by,
where r is the average reward among the rounds in which the a-th action is chosen during rounds 1, ..... ,t (and zero if not defined), and b9, is confidence walf-width be specified. With this, set M = [m', m,mm == [mf, ml] | [m²a m Consider the following update. Let
and in round 1, update
arg max min yEA me me m7
(p 1e, m)
(9)
Regret analysis. First, note that conditioned on E M we have
= min (n² p², m) I max min (μ --,,)))))))))))) min MEM.
(1 -4. s (pttt~ pl.m)
(10)
MEM!
μεAN MEM!
Hence, the algorithm monotonically improves, i.e. (1e+1, m) 2 (p', m). if all confidence intervals include the true mean.
As for the confidence intervals, set by == 2 (og((T"A/C) where n², is the number of times that action is chosen in rounds ,....,t. Then by Hoeffding's inequality, with probability at least Ç. for all E [7] we have m E int(MM). We call this event G.
By finding the closed form of the update rule in Equation (9) and the lower bound μ μC, it is not hard to the following.
Lemma B.3. Conditioned on G, we have pha 2 p.. 2 8 for all t E [T']
Using Hoeffding's inequality and a union bound, we thus get the following concentration.
Lemma B.4. Condition on G and let Ç' E (0, 1). Then with probability least 5', we have
n 2 öt 22t
22t \ogo(T/)C"
We now ready prove Theorem B.I. Condition on G and on the event in Lemma B.4. This occurs with probability at least 1 - C
First, we consider the regret compared to St. By the monotonicity property in Equation (10),
(p', m) 2 (p'-1, m) 2 (p²,m) (4e, m).
18

---

Regret Minimization vs Minimax Play
Setting <= 2T
and integrating out the regret of most T under the failure event:
(10 - ,t, m)) S Prr[G]
Σ (A - 2², m) G + Pr[GIT
=1.
We now consider the worst case (pseudo-) regret R. Note that for the minimax problem in Equation (9), strong duality holds and we can fix saddle point (p', m'') such that (for all (H, m)) E AA A1
(1 - n m²) S (ut nt me) s (pt 1 m)
(11)
Under the success events, have n/a 2 88 21 log (T/S)) ((g)) by Lemma B.4. Now when 2 40 := -85-2log(T/C)) then naa 2 28-1 12-V2221100 (TT()( and hence
4 4log(T?A/C)
by 1 21
(12)
8t
We have
T
R. 88 log((T())
Σ (ma- - (n', m)) S 80- Plog(T/C)
Σ Emm= - (x', m)))
t=
where the instantaneous regret for 2 to is (with 11" = =
ma- - (n', m))
= (1r - p/: m)
= (1r - n¹, in ++
> + (xt - 3 m - ii mi(1)
S (1e+1 11' m)) + {1¹ ,1m )
(by Equation (11) and m E M(+1)
(ett1 (²'m)) m) {pt b- 1) + (1t)
S (1't1 1r', m) + {p" ,b) + (u',b")
(as b+1 b)
Hence,
T
R. <88 2-80-2lo((T/())) + (pu
1000 m) + Σ ((xt,6)) (at,09))
+
t=
T
T
log(TT(") + ++
Σ
b
+
(p',6")
t=
t=
T 2
4log TTA/))
T
<88 log(T/()) + +1+
Σ
(p'
(by Equation (12))
8t
t=
log (TT
<o 8 Log(T
Σ
(")
8
t=
with probability least 1 ç 5". Using DL, El 80 < O(VA AT log (AT (Auer et al., 2008), 8 < 1/A and integrating out the regret under the failure event yields the result.
C. Deferred Proofs for Extensive-Form Games
C.1. EFG Background
The following remark clarifies that the Markov game we defined in Section (which more common in the machine learning literature) indeed covers the case of imperfect information EFGs (which are more common in the game theory literature).
19

---

Regret Minimization vs Minimax Play
Remark C.I. The notion of EFG in Defimition 4.1 from Section usually referred as tree-structured perfect- recall partially-ohservabee Markov game (TP-POMG). This also covers the notion of perfect-recall imperfect information extensive-form games (P-IIEFG) (Osborne & Rubinstein, 1994) that satisfy the timeability condition Jakobsen et al. (2016), In fact, more careful look reveals that the results directly generalize to any P-IIEFG without timeability (see Bai et al. (2022) for this brief discussion).
For further clarification, we remark that usually, both the cost function u, the transition probabilities p and the policies x (and treeplex strategies ji) may be non-stationary in the sense that they explicitly vary across the stages h E [H] of the EFG, However, as we assume tree structure and perfect recall, the state space and infoset space are partitioned along the stages anyway, which is why WLOG we omit the explicit dependence of the above functions the stage h. Finally, to be precise, our algorithm assumes to know the tree structure of the game (but not necessarily the transitions), an assumption that can be removed (Fiegel et al., 2023a).
C.2. OMD over the Treeplex
The unbalanced and balanced dilated KL divergence are defined as follows:
TT (z/2z)
D(ul(()== Σ
((x, log
Ter (a/x))
TEA aEA
a( log Tu(a|as))
(ullee) Σ
Σ
M.ballshh a) Typ (a(x))
h= E... aEAA
where Tp is the policy corresponding the treeplex strategy μa and pha is the unique strategy corresponding to the balanced exploration policy
[C (a()))
(N' E (1....,h-11))
h (a(awe) =
(N' E (h....,H))
with (a Nr, being set of infosets at step h reachable from (Iwr, a) (i.e. the unique path to such infoset goes through (Iw, a)), and (xx)) == USEAC ())
Computation of Unbalanced OMD. For completeness, we restate the closed-form implementation of case one in Equation (3) with the unbalanced dilated divergence D) from Kozuno et al. (2021, Appendix B). In the setup of Equation (3), let A' E II be the policy corresponding to A², Then we have a closed-form
* (axlar)) =# *an ( exp (1 {at- = an) (-né' an) log(Z - (o)())))
and 4 **+1(112)))=) (- for all other 2y # 2/. Here, 2%, is
z = A' (at (x)) + #' *a l=t) exp (-né' (ah ahj + log(Zh+1))
and Zir == 1.
Computation of Balanced OMD. For completeness, we also restate the closed-form implementation of case two in Equation (3) with the balanced dilated divergence D from Bai et al. (2022, Al Algorithm 5). Once more, let n be the policy corresponding to f². Then we have a closed form for the next iterate, namely
# *** ( = #² (an ( exp {an = aid boppbal.l (ah,, of) at)) + ( at log log(Z/+1)
log (Zh))
a ( ah+1))
and in the other infosets # + (anl2n) = aan (n). Here,
1= (fa exp ( (Trybab bol.
(a an) log( (og(Z)+)) bol (zh, ah oe) (oh, af) + a (1hht: ah+1))
and Z Z =
20

---

Regret Minimization vs Minimax Play
C.3. Upper Bound
First, note that due to the peporttaceeweiigtinng by the rollout policies the cost estimators are unbiased (Kozuno et al., 2021): (z, a)] = E (2r, a)], and E [²","" = E [E ((c,, n²)) F,-1]] - = Ke'ss u²), where Fz-1 is the o-algebra induced by all random variables prior to sampling the trajectory (s) ai bj. , uq ...., S a'z: b " Further, WLOG assume that the costs u(s, a, b) used to defnn the cost function ct in Equation (2) are bounded in [0, 1]. While in EFGs we assumed u(s, a, b) E [-1, l], we can simply replace them by (1 + u(s, b))/2 without changing the regret bound. With this, we can prove the desired upper bound by resorting to the estimated regret
start
(n) = Σ
(0, - 11)
(d 1t 11) + +(1 a*
Σ
(13)
t start,
s=ttatte
start
By convention +1 7 + if l is the last phase.
Theorem 4.1. Let 8 E (0, 1/A] For any special comparator μe E T such that ( a) 2 8 for all a, Algorithm 2 achieves (for any c' 's from Equation (2))
R(x") S 1, and
max PET
R(u) S (000'~'XH')
Proof. Case 1: a = is not reached. Suppose first the algorithm ends phase with a 1 at time step T. By Lemma C.I, w.I.t any comparator
T
Σ
(c. p) S (2R+ 2H) k O(Rlog(R)).
All previous phases must have been exited, so by Lemmas C.1 and C.2 we have
E (d, v²) 2k-11
Σ 2 2 (2h-1-1) 1)==1. =1
Taking expectation yields the claim.
Case 2: a = is reached. Next, suppose a* = 1 was reached. Then balanced mirror descent was run in the final phase k. As before
starty Σ
- n) < (2R 2H) k O(Rlog()))
For the final phase, note that the algorithm runs balanced OMD with importance weights and uniform initialization for S T rounds. Thus by Lemma C.5, this phase has expected regret
E
Σ
(c, pt - -m) ST + 1 D - (ulle
Ststtatee
STHST + (A)og(A)
(by Bai et al. (2022, Lemma C.7))
<V XAHH3 AoAHHllg(A)))
(since
X log( V
2H*7
<R.
(14)
using 8 < 1/A. Thus for any comparator, have
E
(c' μ¹ 11)
{O(Rlog(R)) + R O(R R
21

---

Regret Minimization vs Minimax Play
Finally, for the special comparator, we note that all phases k with a have been left and thus by Lemma C.2 and Equation (14)
Σ (, 119) S R
Σ P=1
2k = R (24-1 -) 1
where the last step used that a min(1, 1, 2 /R} and thus R < 2
The following lemma establishes the statement from Lemma 3.1, generalized to EFGs. The second part of the lemma is essentially the same. Once more, the fact that 1a is lower bounded comes into play when upper bounding the estimated cost functions.
Lemma C.1 (During normal phases). Let le be such that a < 1. Then for all μ T. almost surely
Rh (n) S 2R + 2H 26" /8X log( A)T 2H,
for the special comparator almost surely Rst (x²) - 2
Proof. WLOG suppose that = 2" is a power of 2, else we can run the algorithm for T' such that the next largest power of two and pay constant factor in the regret. For the first term Equation (13), we analyze unbalanced OMD bound - (C', pt pu) almost surely, making use of the fact that e is bounded. Recall
11 (1rh, af)) = (Ih, a)) uf
(zh, a) =
1e (1hhha)) a)
1r (In
Now since R 2" a power of 2, we have a# = 2/ 1 < 2loR, (R) R -R-1RR-11 1/2,
1
2
axn, S ()) auj a) + (1 (1))
S
(zn,
8
Moreover, ét is outside the visited ((af,a)))) a))). Thus, by Lemma C.3, for the first term in Equation (13) almost surely
Maarte441
C 11) (A) 4H + 1)
S8 1oXHPoog & R.
logH)lg((A)))
(15)
8²
For the second term in Equation (13), note that since the if may only hold at t' start; 1,
starbe
Σ
(d - u) S 2R ( .1²) < 2R 2H.
(16)
Emstarty
Linearly combining Equations (15) and (16),
(*) a
Σ
(C fi - u) + a
Σ
(G 11) 2R 2H
I=start
for any μ. and for the special comparator 1 we have by Equation (15)
starty
starte -1
(x²) a
Σ
(c, + (1 a
Σ
(6 - (22-11/R) -
startt
I=stoott
Now suppose the algorithm exits a phase k. The following result mimics Lemma 3.2 for the case of EFGs, and we resort to essentially the same proof.
22

---

Regret Minimization vs Minimax Play
Lemma C.2 (Exiting a phase). Let k be such that a < and suppose Algorithm exits phase & time step starl 1. Then almost surely R (1C) S -28-1
Proof. The if condition implies max Σ
(0, ,10 11) > 2R, when we let μ² be maximizer, find -imetti
starle+1 -1 stsarlyy
starl+ -1
(C, 1²¹ 11)) =a
(e, fr 1e))
startt
starle41 -1
starll+11 -1
pr 1²)) + a
Σ
(c, 14 - 1c)
tsstarl
<aa R + a (-2R) 2k-1
using Equation (15) in the last inequality.
C.4. Auxiliary Lemmas: OMD on the EFG Tree Unbalanced OMD Lemmas.
Lemma C.3 (Bandit OMD with bounded surrogate costs), Let > 0, and L > Let (C") be cost functions such that for all 0 S e (2rh, a)) S L (for all Fh a), and moreover dt (rh, a) 0 if (2 a) F (1h ah)) where shy a² are arbitrary. Set je (2% a) 1/Ah and consider the scheme
1
p arg min (u, + D(ull/it)
WET
17
for S T Then have for all á E T
T
Xlog(A)
Σ
(p 0,0's
+H 1)L2T'
n
Proof. By Lemma C.4,
D(AllA") 11 +
- = - D(NIIA)))+++ + (D(R')1a't)) -((A
<p f,, (.)
Thus (using D 2 0), we have a regret bound of
T
(p' - -,,0) s= (((IIl))) + T
E
Σ
For the first term we easily have ((All=") S X log(A) (Kozuno et al., 2021, Lemma 6). For the second term, by Lemma C.4, we have
"
D(i = =(ii'laa41 -
< <n (a', -D(a"((á)
+ +log(Z)) - Σ h=1
(t af (shh ah) + log (Zi),
using that al is zero outside ((xh, ())))a By Equation (17) and log(1 + x)) S x,
H
h-1
log( (1
<
p (1% ahh exp
exp
(4 abr))
(exp (-ne" ( ahl) - 1)
hml
Σ
pf (4hh ahh exp
d (ahy ane)
(- ( at) + (s/,
1=1
W=1
23

---

Regret Minimization vs Minimax Play
where we used exp(-2) S 1 -y+ 1²2 for y O. We thus find, using et tthroughout
H
((
jt' (1) df)c ai) + log(Zi)
h=1
Σ
j (1 a (ah
H
(-n
h-1
p (xh ah) exp (nn
Σ N==1
dir)) (ater
a'
(-ne (ah ah) + 722t(at, d)))))
j (1h agh (2 (1/ a/))
1 1-exp exp
Σ
-17
h/=l
h-1
17
pt (x an. exp
"
Σ
Et
(xhr, dhi))
d' (a og)²
h=1
h'=1
jl' (2h d ah))
|I-exp]
-11
Σ
h-1
Cxte oki))
1=1
h==1
(a a (xh.
H
h-1 ((the ohr))
H
Σ h=1
p' (xh, a/) a ohl
Σ
+ >
(l a (2h, of)
where used 1 - exp(-x) x in the last step. Finally, using the bound on the cost functions and the fact that all jt (ah a < 1, we find
D( S S (
Summing over t concludes the proof.
In the setup of Lemma C.3, let # E IT be the policy corresponding ji and recall (Appendix C.I)
/ =1,
%/1 (an (x1) exp (1 {at an} (- (xh, an) + log (
Σ
4/
=1 * (a (++ + #' (af, (ar) exp (- (2/, af,) + log (zg(2
The following lemma is a slight generalization of Kozuno al. (2021). Indeed, the proof only uses that at is zero outside of the visited ((2), af )). not whether normalize by Å μ² or from which policy the trajectory (2 of),, is sampled from. The same holds for the following closed form of 2 (Kozuno et al., 2021, c.f. Lemma 6):
Σ p² (att,, exp -1 Σ (lelmohhr)) ) (exp (-né" (ate, ohr)) - 1).
z =+
(17)
Lemma C.4 (Kozuno et al. (2021), Lemma 7), In the setup of Lemma C.3, we have
D(ullatt)) D(Hll(²) 17 (n,c*) e²) + 10g(2;)
a.s. for all 1 L μ ET
24

---

Regret Minimization vs Minimax Play
Balanced OMD Lemmas. Recall the definition of ce from Equation (2), for which e is unbiased estimator. Again, recall that WLOG replaced assume a(s,a,b) [0 (by rescaling via (1 + u(s, a, b)) for simplicity, without changing the regret bound.
Lemma C.5. Lett > O. Set P (Ih, a) = 1/A" and with costs costs from Equation f2) Protocol 3 consider the scheme
((xn, a) = (o/p uh.
é' (xh, a)
(L(In;a)
(1,0') ( - -
p++1 arg min NET
for S T" Then for all ji E T
T
5 HHH S T HTT + 1 Dho
E
Σ (pt - pr. c))
Proof. By Lemma C.6, we have
(Dh
D) (ail(())) = (2, + =
Thus,
T
T
1 E - Doal (
=E
(i, + Σ =
[=1
T
+ TH3
SB
Σ (a 1''
2 T
(by Lemma C.7)
T
+ HH
Σ (a f1 ,')
2
as E (2, Fi-1]] = c'(x,, a). Using Dall 2 we conclude
T Σ
TH T"
E
- p,,t)
As before, the following lemma from Bai et al. (2022, Lemma D.7) does not use the specific form of the cost estimates but only the update rules.
Lemma C.6. In the setup of Lemma C.5. for all μ E T, we have
log Zi) bal, (zf af)
Doat (ullatt+)) - DDbol (m]l = T (M,
(H, et) + TEi.
We introduce some extra notation for convenience: Let A E II be the policy corresponding to j and set
8 = " an), # = # *'(aa
e = at (x/
and consider the functions
(c) = (CH) == log (1 #/1 # exp(- exp((BB((H)) 18
- (6) : (Ch.Hr log (1 (1- 2 # exp(() (5) cn))) 13 (h < H),
25

---

Regret Minimization vs Minimax Play
and the values
1
3% : (2))
log(Zi (%)
log (1 o + #i. exp(5) - (()))) (h E [M]
Ph
3%
for the input at. The following lemma now lets us bound the remaining term in the proof of Lemma C.5.
Lemma C.7. In the setup of Lemma C.5, have
T Σ
Σ E
[
S
B
11'T..
t=
Proof. By Lemma C.8 and as ét is unbiased,
T
T
TH
T
H
H
E
S
E
20)]
E
Mish
ballh (Ih, an 1ih ane (xw ax)
2
1=1
1=1
1=1 R= h b/ He
T
T
11
11
TH
Σ
E Kat,
c
E (xn,, an an) an (ane, and
2
1=1
1=1 H b/=h
T'
TH3 T
< - Σ
E ((t'cC)]
Lemma C.8 (Bai et al. (2022), Lemma D.11). We have
H
H
E S (1i,
TH
Σ
an Phh (#w, ax ) (Irss aw),
2
where ahtta (ah (t)) = 1 - # (ana (xn.) along the unique path (Im",an") )m leading from step + 1 to (at af.).
The proof is the same as in Bai et al. (2022).4
C.5. Lower Bound
Theorem 4.2. Let A 2, H 2 1, and 8 E (0,1). There exists EFG of depth H with X +(A") such that for any o E T with min,,a (x, a)) = 5, there is an adversary such that for any algorithm:: If R( S 0(1), then
max R(n) 2 NE
Proof. Consider A-nary tree with X = O(A#) leaves and where each infoset corresponds to unique state. As for the transitions, the learner is deterministically sent to leaf s (a1...., ..) upon playing as in each step h. Since 6 = ming, (x, a). there also exists leaf information set r = (s)) and and an action a such that μ² a) = 8. Now
consider two environments in which all state-action triples have cost one, except for the cost in leaf s, which is either sampling according to the (+) or (-) environment from Theorem 3.2. We are thus effectively simulating a two-armed bandit with comparator (1 8, 8) with the same construction as in the simplex case. The derivation in Theorem 3.2 thus concludes the proof.
*There, in (ii) we still have ji' (0m,,, ( ( an) S 1. All other properties used in the proof hold for general è 2 0 (in particular Lemma D.9 and 10, although stated for É [0, 11
26

---

Regret Minimization vs Minimax Play
D. Further Experimental Evaluations
In this section, we provide further details regarding our experimental evaluations in Section 5.
All vs Exploitable Strategies. In addition to Section 5, we compare the performance of Min-Max, OMD and Algorithm against a couple of other exploitable strategies strategies. We consider the following constant strategies:
RaiseK: Bob raises/calls if and only he has a King, and checks/folds otherwise.
RandMinMax(aa) Bob plays perturbed version of the Min-Max strategy: In every round, with small probability a, he will play the uniform strategy, and otherwise the Min-Max strategy.
In Figure 4, we present the amount of money that each of Min-Max, OMD, and Algorithm 2 extract with respect to the aforementioned exploitable strategies. Specifically, Figure 4 reveals the following.
Min- Max
Max
GMD
OMI
DMD
Outs
Clrrc
Dure
-60 Ourrattio
-20
20-
80
-60
440
100
1000
fourd
Aaund
Round
All vs RandMinMax(0.05)
All vs RandMinMax(0.1)
All vs (4ndMinMaxx0.155)
350
Min-Max
OHD
Ours
200
250
60
150
200
500
350
20
200
-00
000
300
1000
200
400
520
680
2002
200
400
500
800
1002
Bouns
All vs RandMinMax(0.3)
All vs RandMinMax(0.5)
All vs RaiseK
Figure 4: All vs Bob comparison for T 1000 rounds. The x-axis displays the round t, and the y-axis displays how much Min-Max, OMD, and Algorithm 2 gained from the second algorithm so far. The y-axes have varying scales for readability.
All RandMinMax(a): In all plots, Algorithm 2 achieves at least the gain of the min-mat equilibrium and in fact always improves slightly over it. For small values of (e.g. a 0.05), meaning that Bob plays (reasonable) strategy very close to the min-max equilibrium, OMD always loses money while Algorithm 2 wins linearly. For larger values of a (e.g. a = 0,1, 0. 0.15,00 0.3), OMD loses an initial amount but slowly starts catching up towards a total positive gain for very large T. Finally, when a is large (c.g. a = 0.5), meaning that Bob plays a highly suboptimal (and not exploitative) strategy, OMD is able to obtain a positive gain much quicker and eventually surpasses our Algorithm (as is not restricted to the support of the min-max equilibrium, which in this case is of advantage).
All RaiseK:
Notice that min-max equilibrium does not exploit RaiseK all. At the same time, OMD exploits it lincarly right away, extracting a near-optimal gain from the opponent. Our Algorithm 2 also exploits RaiseK linearly at comparable slope, however starting exploitation somewhat delayed due to the risk-averse nature of the algorithm. However, our algorithm consistently exploits weak opponents significantly better than the min-max strategy all cases, and unlike OMD does so while not risking to lose essentially any money.
In summary, our experimental evaluations reveal the following insights that are in accordance with our theoretical findings: If Alice plays Algorithm 2, she secures at least the gain of the min-max strategy, thus not losing against any opponent. Yet, she is able to better exploit strategies that deviate from the min-max strategy, at a level often comparable to standard no-regret algorithms.
Implementation Details. In all experiments, we average n = runs of repeated play (plotting Alice's 's average cumulative expected gain), and plot one standard deviation. In all algorithms, we used the same learning fixed rates (n ~ 1/VT) and the (unbalanced) dilated KI. divergence for fairness and simplicity. We provide the code in the supplementary material.
27


Reviews:
[{"review_id": "CTm3FhjaM5", "reviewer": "Reviewer_JKhZ", "summary": "This paper derives regret upper bounds that vary depending on the comparator in the setting of online learning with bandit feedback. Specifically, the paper proposes an algorithm that simultaneously achieves an $O(1)$ regret upper bound when the comparator of the regret lies in the interior of the probability simplex, which is the feasible region, and an $O(\\sqrt{T})$ regret upper bound otherwise. \nThe authors primarily discuss this in the context of symmetric two-player zero-sum normal-form games and further extend their analysis to extensive-form games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing valuable feedback! \n\n\n> 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.\n\n**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.\n\n\n---\n\n\n> 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.\n\n**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.\n\n\n---\n\n\n> This work focuses on symmetric games. Can the authors address this limitation?\n\n\n**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.\n\n\n\n\n---\n---\n\n\n**Additional minor clarifications:**\n\n> 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. \n\n**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.\n\n> In Line 46, the term \"the best strategy\" is ambiguous, making it difficult to understand.\n\n**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.\n\n> in Line 89, the phrase \"a special ('safe') comparator strategy\" is unclear at this point.\n\n**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.* \n\n> 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.\n\n**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.", "claims_and_evidence": "Yes, all propositions and claims in the paper are with proofs or references.", "methods_and_evaluation_criteria": "Yes, the proposed algorithms are variants of existing algorithms in online learning and are thus valid. Moreover, the evaluation metrics (i.e. regrets) are standard in the literature.", "theoretical_claims": "I have reviewed the claims in the main body and confirmed that there are no major issues.", "experimental_designs_or_analyses": "Yes, I have briefly checked the experimental setup and results and confirmed that there are no major issues.", "relation_to_broader_scientific_literature": "In the context of games, I have not seen an approach that achieves different regret upper bounds depending on the comparator.  \nFrom the paper, the motivation of deriving different regret upper bounds based on the comparator is unclear.  \nFor more detailed comments, see the section Other Strengths and Weaknesses below.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The major issue with this paper is the unclear motivation for its contributions. The authors derive different regret upper bounds depending on whether the comparator, but it is difficult to see how these bounds offer advantages from the perspective of learning in games. What are the benefits of achieving a lower regret when choosing the minimax policy ${argmin}_\\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.\n\nAdditionally, some statements are inaccurate, and certain terms are used in a non-standard manner, making the paper a little harder to understand. For example, in Line 17, the statement \"the regret compared to any fixed strategy $\\mu$ satisfies … $\\leq O(\\sqrt{T})$\" depends on the algorithm being used, and such a regret upper bound is not necessarily always achievable. Moreover, in Line 46, the term \"the best strategy\" is ambiguous, making it difficult to understand. Similarly, in Line 89, the phrase \"a special ('safe') comparator strategy\" is unclear at this point. Additionally, 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.\n\nThis work focuses on symmetric games. Can the authors address this limitation?\n\nIt 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.", "other_comments_or_suggestions": "no", "questions_for_authors": "The reviewer expects the authors to address the questions raised in Other Strengths and Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NlEChxosJl", "reviewer": "Reviewer_ZxCd", "summary": "The paper proposes a bandit algorithm for two-player symmetric zero-sum games that guarantees $O(1)$ regret against the minimax strategy and $O(\\sqrt{T})$ regret against any strategy.\n\n## update after rebuttal\nI keep my score, which remains positive.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing valuable feedback! \n\n> The related work and its comparisons with the manuscript can be more adequately discussed.\n\n**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. \n\n---\n\n> Further discussions and comparisons with Lattimore (2015) and Ganzfried & Sandholm (2015) will be appreciated.\n\n**Response:** Further comparisons with Lattimore (2015):\n\nLattimore (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.\n\n\nAdditional comments regarding Ganzfried & Sandholm (2015):\n\nGanzfried & 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.\n\n---\n\n\n**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.", "claims_and_evidence": "I do not see any problematic claims.", "methods_and_evaluation_criteria": "I do not see any major issues with the methods.", "theoretical_claims": "The proofs seem correct.", "experimental_designs_or_analyses": "The numerical experiments seem sound.", "relation_to_broader_scientific_literature": "The developments seem novel and of interest to a variety of fields because of the game theoretic implications.", "essential_references_not_discussed": "There does not appear to be missing essential references.", "other_strengths_and_weaknesses": "The regret guarantees in both directions is a strength.\n\nThe related work and its comparisons with the manuscript can be more adequately discussed.", "other_comments_or_suggestions": "Further discussions and comparisons with Lattimore (2015) and Ganzfried & Sandholm (2015) will be appreciated.", "questions_for_authors": "I have no further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CoJxZXoOyt", "reviewer": "Reviewer_XQ49", "summary": "In this paper, the goal is to develop a bandit algorithm that guarantees simultaneously constant regret with respect to a given strategy and $\\sqrt{T}$ regret with respect to the best strategy in hindsight.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing valuable feedback! \n\n> 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.\n\n**Response:** Indeed, the high-level difference between the algorithms is using Exp3 as a base algorithm. In addition to this:\n- We use importance weighting according to the algorithm's iterates $\\mu^t$, not the Exp3 iterates $\\hat{\\mu}^t$ as usual. \n- We modify the condition for entering a new phase as the true cost vectors are not observed. \n- We switch the learning rate in the last possible phase (see below).\n\nThis 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.\n\n---\n\n> What is the novelty in the presented reduction from OLM to NFG or EFG ?\n\n\n**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.\n\n---\n\n\n**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.", "claims_and_evidence": "- An extension of the phased algorithm of Even-Dar to the bandit case\n- An analysis showing good regret with respect to both the given strategy and the best strategy in hindsight as long as the given strategy has a probability of playing any arm bounded away from zero.\n- An application of their approach to NFG and EFG (with lower bounds).\n\nI think the above claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The main focus of this work is theoretical. Some simulations are presented based on the game of Kuhn poker. I mostly see them as checks that the theory indeed works.", "theoretical_claims": "I did not check the details of the proofs of theoretical claims. The claims themselves seem plausible.", "experimental_designs_or_analyses": "I did not check the experimental designs or analyses.", "relation_to_broader_scientific_literature": "I think the relevant literature is correctly cited.", "essential_references_not_discussed": "I did not find any missing references.", "other_strengths_and_weaknesses": "I think the paper is overall well written and the idea of looking for a strategy that simultaneously guarantees constant regret with respect to another (known strategy) and $\\sqrt{T}$ regret with respect to the best strategy in hindsight is interesting.\n\nI think the novelty of the work can be challenged\n- 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. \n- What is the novelty in the presented reduction from OLM to NFG or EFG ?", "other_comments_or_suggestions": "See \"strengths and weaknesses\" section.", "questions_for_authors": "See \"strengths and weaknesses\" section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F0P9Akes0w", "reviewer": "Reviewer_aZNc", "summary": "This submission studies whether an algorithm can achieve O(1) regret compared to a specific fixed comparitor strategy while also guaranteeing O(T^0.5) regret compared to the best strategy in hindsight in symmetric two-player zero-sum games. The authors focus on bandit feedback settings, where the learner only observes the cost of their chosen action. The authors answer this answer affirmatively in symmetric two-player zero-sum games by introducing algorithms that nagivate the trade-off between no-regret learning and minimax equilibrium strategies in both normal-form and extensive-form games. \n\nThe authors’ algorithm is a generalization of the “phased aggression” approach of Even-Dar et al. 2008, which was originally proposed for the full information setting. At a high level, the algorithm plays a convex combination between the comparator strategy and the strategy chosen by a no-regret algorithm at each time-step. Whenever the algorithm estimates that the comparator is a poor choice, it decreases the weight on the comparator strategy (thereby increasing the weight on the no-regret strategy). The authors use importance weighting to estimate the losses of each action, given the bandit feedback present. The no-regret algorithm used is online mirror descent with the KL divergence regularizer. \n\nThe regret guarantees for this algorithm suffer a multiplicative dependence on a term corresponding to the “exploration gap”. However, the authors prove a lower bound which shows that this dependence is indeed necessary. The authors also extend their results to handle extensive-form games. Their algorithm for this setting is similar, but uses online mirror descent with an unbalanced dilated KL divergence regualrizer as the no-regret algorithm. As was the case in normal-form games, the authors show that their performance guarantees are “nearly tight” by providing a corresponding lower bound. \n\nFinally, the authors empirically evaluate their algorithm for extensive-form games on Kuhn poker and compare its performance to standard no-regret learning and minimax play. Their empirical evaluations largely confirm their theoretical findings, i.e. the proposed results gives “best of both worlds” performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our paper and providing valuable feedback! \n\n## **Remark on non-symmetric games:**\n\n> What are the barriers preventing you from extending your results to non-symmetric zero-sum games? \n\n**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$.\n\nMore 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. \n\nWe will move these remarks to a more prominent place in the writing so it is clear that the limitations are not necessary.\n\n---\n\n> Or to no-swap-regret?\n\n**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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This submission belongs to the literature on learning and equilibrium computation in games. Specifically, this work is the first to study best-of-both-worlds performance under bandit feedback in symmetric, zero-sum games.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The authors are the first to provide compelling results for best of both worlds learning in two-player zero-sum games under bandit feedback. Their algorithms are natural generalizations of those for the full information setting, and they provide nearly matching upper- and lower-bounds. A minor weakness is the restriction to zero-sum games that are symmetric, although there are many zero-sum games which satisfy this property.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "What are the barriers preventing you from extending your results to non-symmetric zero-sum games? Or to no-swap-regret?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the following "best of both worlds" problem: in a minimax game, a player would like to simultaneously achieve a constant regret against the Nash equilibrium strategy, and a $\widetilde{O}(\sqrt{T})$ regret against all fixed plays. Although in general this task was shown to be impossible in the literature, for symmetric zero-sum games with a lower bound on the pmf of the mixed Nash equilibrium, this task is shown to be possible for both normal and extensive forms. A tight lower bound on the pmf lower bound is also given in this paper. 

All reviewers are positive about this paper, but the support is not super enthusiastic mainly because the lower bound assumption may not be practical in many scenarios. In addition, the algorithmic novelty compared with the existing work is limited. Despite these concerns, reviewers think this paper establishes a significant result, which they (and I) recommend to accept.
Decision: Accept (poster)