Alternation makes the adversary weaker in two-player games
Authors: Volkan Cevher
Ashok Cutkosky
Ali Kavis
Georgios Piliouras
Stratis Skoulakis
Luca Viano
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Online Learning
Regret Minimization
Game Theory

Abstract: Motivated by alternating game-play in two-player games, we study an altenating variant of the \textit{Online Linear Optimization} (OLO). In alternating OLO,  a \textit{learner} at each round $t \in [n]$ selects a vector $x^t$ and then an \textit{adversary} selects a cost-vector $c^t \in [-1,1]^n$. The learner then experiences cost $(c^t + c^{t-1})^\top x^t$ instead of $(c^t)^\top x^t$ as in standard OLO. We establish that under this small twist, the $\Omega(\sqrt{T})$ lower bound on the regret is no longer valid. More precisely, we present two online learning algorithms for alternating OLO that respectively admit $\mathcal{O}((\log n)^{4/3} T^{1/3})$ regret for the $n$-dimensional simplex and $\mathcal{O}(\rho \log T)$ regret for the ball of radius $\rho>0$. Our results imply that in alternating game-play, an agent can always guarantee $\mathcal{\tilde{O}}((\log n)^{4/3} T^{1/3})$ regardless the strategies of the other agent while the regret bound improves to $\mathcal{O}(\log T)$ in case the agent admits only two actions.

Alternation makes the adversary weaker in two-player games
Volkan Cevher LIONS, EPFL
Ashok Cutkosky Boston University ashok cutkosky.com
Ali Kavis LIONS, EPFL ali ali.kavi@@epfia
Georgios Piliouras SUTD georgios @ sutd.edu.sg
Stratis Skoulakis
Luca Viano LIONS, EPFL
LIONS, EPFL
cistratissskoolakis@cll..hh
luca, viano@epfl.ch
Abstract
Motivated by alternating game-play in two-player games, we study an altenating variant of the Online Linear Optimization (OLO). In alternating OLO, a learner at each round & [n]] selects a vector x' and then an adversary selects a cost-vector d' E (-1, 1]". The learner then experiences cost (c+ (t-1² xf instead of (c²) (cT)Tx² xt in standard OLO. We establish that under this small twist, the 2 (((TT) lower bound on the regret is no longer valid. More precisely, we present two online learning algorithms for alternating OLO that respectively admit ((log n) ///33/233) regret for the n-dimensional simplex and Opp log 7') regret for the ball of radius P > 0. Our results imply that in alternating game-play, an agent can always guarantee Ō((log n) 1/33133 regardless the strategies of the other agent while the regret bound improves to Olog T') in case the agent admits only actions.
Introduction
Game-dynamics study settings at which set of selfish agents engaged in repeated game update their strategies over time their attempt to minimize their overall individual cost. In simultaneous play all agents simultaneously update their strategies, while in alternating play only agent updates its strategy at each round while all the other agents stand still. Intuitively, each agent only updates its strategy in response
observed change in another agent.
Alternating game-play captures interactions arising in various context such as animal behavior, social behavior, traffic networks etc. (see [33 for various interesting examples) and thus has received considerable attention from a game-theoretic point of view I 3
33 41 40). At the same time, altermation has been proven valuable tool in tackling min- problems arising in modern machine learning applications (c.g. training GANs, adversarial examples etc.) and thus has also been studied 10).
from an offline optimization perspective 37 35 21
In the context of two-players, alternating game-play admits the following form: Alice (odd player) and Bob (even player) respectively update their strategies on odd and even rounds. Alice (resp. Bob) should select her strategy at an odd round so as to exploit Bob's strategy of the previous (even) round while at the same time protecting herself from Bob's response in the next (even) round. As result, the following question arises:
QI: How should Alice (resp. Bob) update her actions in the odd rounds so that, regardless of Bob's strategies, her overall cost (over the T rounds of play) is minimized?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Standard and Alternating Online Linear Minimization
Motivated by the above question and building on the recent line of research studying online learning settings with restricted adversaries [15] 5 [4], we study online linear optimization setting
[4]. called alternating online linear optimization. We use the term "alternating" highlight the connection with alternating game-play that we subsequently present in Section 1.2
In Algorithm we jointly present both standard and alternating OLO better illustrate the differences of the two settings.
Algorithm 1 Standard and Alternating Online Linear Minimization
1: Input: A feasibility set D IR" and c (O....,0).
2: for each round / = 1, do
3: The learner selects vector x' E DD based on c!....., d' E [-1,
4: The adversary learns x² E 'D and selects a cost vector cf E [-1, (based on x: ,...,.").
5: The learner learns cf E [-11, 1|" and receives cost,
(ct) (c' + cT Alternating OLM
Standard OLM
6: end for
In both standard and alternating OLO, the adversary selects c' after the the learner's 's selection of x'. The only difference between standard and alternating OLM is that in the first case the learner admits cost (ct) x² while in the second its cost is (c' + 1) xf. An online learning adgorithn"seles x' E D solely based on the previous cost-vector sequence ct ct...., c E [-1, with the goal minimizing the overall cost that is slightly different standard and alternating OLÓ.
The quality of an online learning algorithm A in standard OLO is captured through the notion of regret [23] comparing A's overall cost with the overall cost of the best fixed action,
T I
RA(T): = max c......T
min DED
(C))
When (T) = o the algorithm A is called no-regret since it ensured that regardless of the cost-vector sequence ....,c,, c²,, the time-averaged overall cost of A approaches the time-averaged overall cost of the best fixed action with rate oTT)/T- - O. Correspondingly, the quality an online tc-l)Ta'
learning algorithm A in alternating OLO is captured through the notion of alternating regret,
T Σ (c' +
(T)
max el T
min RED
Σ Ed'+ + +c
(2)
Over the years various no-regret algorithms have been proposed for different OLO setting achieving
(T) = Ô (VT) regret [28 20 43 The latter regret bounds optimal since there is is simple
probabilistic construction establishing that any online learning algorithm A admits (T = 2(VT) when D is the 2-dimensional simplex. This negative results comes from the fact that the adversary has access to the action x' of the algorithm and can appropriately select ct to maximize A's regret.
At a first sight, may seem that the adversary can still enforce Ω (VT) alternating regret to any online learning algorithm A by appropriately selecting e' based on xf and possibly on dt-1 Interestingly enough the construction establishing Q(VT) regret, fails in the case of alternating regret (see Section 2 As result, the following question naturally arises,
I 'hhe notion an online learning algorithm is exactly the same standard and alternating OL.O. the difference concerns the feasibility set D.

---

Q2: Are there online learning algorthm with (VT)
alternating regret?
Apart from its interest in the context of online learning, answering Q2 implies a very sound answer to QT. In Section 1.2 we present the connection between Alternating OLO and Alternating Game-Play.
1.2 Alternating OLO and Alternating Game-Play
Alternating game-play in the context of two-player games can be described formally as follows: Let
(A, B) be game played between Alice and Bob. The matrix E [-1, 1| represents Alice's costs, Aij is the cost of Alice if she selects action i E [rx] and Bob selects action j E [m]] (respectively B E | 1, 1|mxx" for Bob). Initially Alice selects mixed strategy xx' E A.. Then,
the even rounds L = 2, 6, ...,,.............. Bob plays a new mixed strategy y Am and Alice plays x'-1 E An. Alice and Bob incur costs (a'-1)T Ay' and (v') Bx " respectively.
At the odd rounds t 3,5, 2k- 1 Alice plays new mixed strategy x' A, and Bob plays yf E Am. Alice and Bob incur costs (x*) "Ay" Ay" and (y--1) Bx respectively.
From the perspective of Alice (resp. Bob), the question is how to select her mixed strategies xt
2k-1 An so as to minimize her overall cost
T/2-1
(x+) Ay +
Σ (22k+1)7 A(y2h + 22
In Corollary I.I we establish that if Alice uses an online learning algorithm A then her overall regret (over the course of I' rounds of play) most Ral (T/2). As result, in case Q2 admits a positive
answer, then Alice can guarantee most o( (T)) regret and improve over the Ô (VT) regret bound
provided by standard no-regret algorithms 228 20 43 23].
Corollary 1.1. In case Alice (resp. Bob) uses an online learning algorithm A to update her strategies in the odd rounds, 2*2+1 = A(Ay² Ay " 2y for k I..... T/2 1. Then no matter Bob selected sequence y², v2. , E Am.
Ay2k)
T/2-1
T/2-1
(xt) A
Σ (T2k+1)T A +y 2 min k=
AAy +
Σ x A + 2
=EA,
Remark 1.2. remark that Corollary 1.1 refers to the standard notion regret [23 and R /2) appears only as upper bound. We additionally remark that if both Alice and Bob respectively use algorithms A and the context alternating play, then the time-average strategy vector converges with rate O (max ( RT))))/ to Nash Equilibrium in case of zero-sum games (A = - B and to Coarse Correlated Equilibrium for general two-player games [32]. Our objective more general: we focus on optimizing the performance of single player regardless of the actions of the other player.
1.3
Our Contribution and Techniques
In this work answer Q2 the affirmative. More precisely establish that,
There exists an online learning algorithm (Algorithm with alternating regret Ô (llogn)433g)
for D - A, (n-dimensional simplex).
There exists an online learning algorithm (Algorithm 4 with alternating regret O (plog for D = B(c, p) (ball of radius p).
There exists an online learning algorithm with alternating regret O (log 7') for D = A₂ (2-dimensional simplex), through straight-forward reduction from D B(c,p).
Due to Corollary I.] our results provide a non-trivial answer to Q1 and establish that Alice can substantially improve over the O(VT) regret guarantees of standard no-regret algorithms.
3

---

Corollary 1.3. In the context of alternating game play, Alice can always guarantee at most Ô ((log n) /43))//3 regret regardless the actions of Bob. Moreover in case Alice admits only? 2 actions (n = 2), the regret bound improves to O (log T).
Bailey et al. 3 studied alternating game-play in unconstrained two-player games (the strategy space is R" instead of A..) They established that if the z-player (resp. the v-player) uses Online Gradient Descent (OGD) with constant step-size Y > (z22 == x _²h- Ayy*-11 then it experiences at most (11/7) regret regardless the actions of the y-player. In the context of alternating OLM this result implies that OGD admits (11/7) alternating regret as long as if always stays in the interior of D. However the latter cannot be guaranteed for bounded domains (simplex, ball). In fact there is simple example for D = 22 at which OGD with step-size admits (211/ + +T) alternating regret. More recently, 40 studied alternating game-play zero-sum games (B = - They established that if both player adopt Online Mirror Descent (OMD) the individual regret of each player is at most ((T!/3) and thus the time-averaged strategies converge to Nash Equilibrium with O(T-2/3) The setting considered in this works differs because where the y-player can behave ad adversarially.
2/3) rate.
In order to achieve Ô ((logn) (onggn///37)) 1/3T1/3 alternating regret in case D An, first propose an Ö(T\/3) algorithm for the special case of = A2. For this special case our proposed algorithm an optimistic-type of Follow the Regularized Leader (FTRL) with log-barrier regularization. Using the latter as algorithmic primitive, we derive the Ô (log n) //333/1/3)) alternating regret algorithm for D = An. by upper bounding the overall alternating regret by the sum local alternating regret of 2-actions decision points
binary tree at which the leafs corresponds to the actual n actions.
In order to achieve O(p log T) alternating regret for D (B,, p) we follow a relatively different path. The major primitive of our algorithm is FTRL with adaptive step-size 16 5.. The cornerstone of our approach to establish that case Adaptive FTRL admits more than (p log 7) alternating regret, then wnormalized best-response (-c--) can compensate for the additional cost. By using a recent result on Online Gradient Descent with Shrinking Domains [5). we provide an algorithm interpolating between Adaptive FTRL and - that achieves O(p log T') alternating regret.
1.4 Further Related Work
The question of going beyond ((VT) regret in the context of sinultaneous game-play has received a lot of attention. A recent line of work establishes that if both agents simultaneously use the same no-regret afgorithm (in most cases Optimistic Hedge) to update their strategies, then the individual
regret of each agent is ((1) |3 36 26 17].
Our work also relates with the more recent works in establishing improved regret bounds parametrized by the cost-vector sequence c',....,c' c",, sometimes also called "adaptive" regret bounds [16] 29] 38 30
However these parametrized upper bounds focus finding "easy" instances while still maintaining (VVT) in the worst case. Alternating OLO can be considered as providing a slight "hint" to the learner that fundamentally changes the worst-case behavior, since its cost is (c' + c x' with the learner being aware of c' prior to selecting Te, Improved regret bounds under different notions of hints have been established in [4] 5 15
24 39].
Finally our work also relates with the research line of no-regret learning in the context of Extensive
Form Games 44
18 19 and Stackelberg Games [27 22.
2 Preliminaries
We denote with An C R" the n-dimensional simplex, An := fx " 24 2 0 and
Σ x, =].
Bcc, p) denotes the ball of radius p >> 0 centered at c E R BCc, p) := {z E R"
| cll2 S p).
We also denote with [zlp := arg min ||2 12 the projection operator to set D.
2.1 Standard and Alternating Online Linear Minimization
As depicted in Algorithm the only difference between standard and Alternating OLM is the cost of the learner, (ct) x² (OLM) and (e' + dd-1)T xt (Alternating OLM). Thus, the notion of an online learning algorithm is exactly the same in both settings.

---

Definition 2.1. An online learning algorithm A. for an Online Linear Optimization setting with D " IR", is sequence of functions A == (A1, Ac......AA.... where A R x... x X D.
As Definition 2. reveals, the notion of an online learning algorithm depends only on the feasibility set D. As result, an online learning algorithm A simultaneously admits both standard ( and alternating regret (xx(() (see Equations and 2 for the respective definitions). In Theorem 2.2 we present the well-known lower bound establishing that any online learning algorithm A admits RT( (VVT) and explain why it fails in the case of alternating regret Rdd (T))
Proposition 2.2. Any online learning algorithm A
A2, admits regret (A(T) 2 92 (TT)
Proof. Let c be independently selected between (-1,1) and (1,-1) -1) with probability 1/2. Since cf independent of (c',...,,ch d'-1) then Σ E same time, min E ( S ((VT). As a result, Rx(T) 2 ((VT).
[(c)) x²] 0 where x' == Ae(c' ....., cl At the
O
We now explain why the above randomized construction does apply for alternating regret Ret (T). Let A be the best-response algorithm, Ar(c', "icc',,..,,'"1 ,²=,,,=====
rrgminses,(c" x. Since
e' = (1, or e' = (-1,1) we get that min (c'=1 ) = -1 while E [c'') x*] = 0 since
x² = argmin (c'-1)7 and et is independent of c-11, As result,
E
Σ (
Σ min (c' + +c =T zEA2
The latter implies that there exists least one online learning algorithm (Best-Responsel that admits (-T)) alternating regret in the above randomized construction. However the latter is not very informative since there is simple construction at which Responess admits linear alternating regret.
We conclude this section with the formal statement of our results. First, for the case that D is the simplex, we show 1/3) alternating regret (Section 3)
Theorem 2.3. Let
the n--imensional simplex, D = An. There exists an online learning
algorithm A (Algorithm 3) such that for any cost-vector sequence ct,...,c* 11',
_T
+ct) x² min [=1
x² s SO (TT//3. .og (nTT) where x' Ac(c'
1=1
Next, when D is ball of radius p. improve to Ó(1) alternating regret (Section 4
Theorem 2.4. Let DD be ball of radius D = =B(c,, p). There exists an online learning algorithm A
(Algorithm 4) such that for any cost-vector sequence c² ,'....."" c² where ||c|122
1|2 < 1,
I(c'-+ +')
min 20 ED
E(e
Tt O(p (pplog]) where x' Aele)....,eee
,.... ............
Remark 2.5. Using Algorithm nating regret for D
4 we directly get an online learning algorithm with Olog T) alter-
A2.
2.2 Alternating Game-Play
two-player normal form game (A, )) is defined by the payoff matrix A E [-1,1]nxm denoting the payoff of Alice and the matrix B E [-1, 1|,11mmx denoting the payoff of Bob. Once the Alice selects a mixed strategy x E An (prob. distr. over [n]) and Bob selects a mixed strategy y E Am (prob. distr. over (n)) Then Alice suffers (expected) cost Ay and Bob y Bx.
In alternating game-play, Alice updates her mixed strategy in the even rounds while Bob updates in the odd rounds. As result, sequence of alternating play for 2K rounds (resp. for T 2K 1) admits the form (x y²2, (x3, ,"),.... (x2k+11 22²²,, (-=2++1 y 2 (22K -1 22)), Thus, the regret of Alice in the above sequence of play equals the difference between her overall cost and the cost of the best-fixed action,
T/2-1
T/2-1
(T) = (x1) T
(A)TAA Ay
Σ k=l
(k+T A(y2* 3k + y2k+2)
min #EAn
Ay
Σ R=1
x A(y 2k + 22++2
Alice's cost
cost action
5

---

If Alice selects x 2² := A Ay" ........... Ayah-2
: .Ay2k) for l E [K - 1] and 21 A1(+) then
by the definition of alternating regret in Equation 2
we get that
(x')T Ay
(
Ayy
min rtAn
Ay
Σ x (Ay 2y S R (K)
which establishes Corollary
1.1
The proof for T = 2K + is the same by considering Ay 0.
3 The Simplex case
Before presenting our algorithm for the n-dimensional simplex, we present Algorithm 2 that admits
(log2/3 T. TT/33) alternating regret for the 2-simplex and the basis of our algorithm for An. Definition 3.1 (Log-Barrier Regularization), Let the function R A2 + Rzo where R(x) =
log œ log z2.
Algorithm 2 Online Learning Algorithm for 2D-Simplex
1: Input: e0 < (0.0)
2: for rounds f 1= 1,...., do
3: The learner selects x' == min 12(c-11)xx + 1c (c=+ +c--1) a R(x)/1l.
4: The adversary selects cost vector c¹ E [0, 1jm
5: The learner suffers cost (c' + 1(-1)T=+
6: end for
In order to analyze Algorithm 2 we will compare its performance with the performance of the Be the Regularized Leader algorithm with log barrier regularization that is ensured to achieve Oloo T/y) alternating regret
[23 The latter is formally stated and established in Lemma 3.2.
Lemma 3.2. lety'..... I² E A2 where y² == minzed, [ct + d' x + | (c + c Tx + R(x)/7}
Then, ETn (c' + T) - minke(n) Ein(d + cf S log + 2.
In Lemma 3.3 provide closed formula capturing the difference between the output z' E A of Algorithm and the output y² E A2 of Be the Regularized Leader algorithm defined in Lemma 3.2
Lemma 3.3. Let x² = (x1, E A2 as in Algorithm 2 and y² = (vi. v/) E D2 as in Lemma 3.2
Then,
a - 3ं = A ( vi) ((c) - -c)) - (G-'
with A(11,31) == (4191) 1 + (1 x - (1 -n and |A- (a- vi) - (x ,t S 0(7).
Up next use Lemma 3.2 and Lemma 3.3 establish that Algorithm 2 admits Ologg 2/3 T T1/3) alternating regret.
Theorem 3.4. Let x² ."....,," E A2 the sequence produced by Algorithm 2 for the cost sequence
cl,...,c" cT E [- with 7 o (log") 1/g TT. TT/133 then Ralt (T) = O logg 2/3 T..... 13
1/3
Proof. By Lemma 3.2 then Ederr (c' + c'-1)Tx² x² min m) E Eiery (c) cf < O (log T T/7) +
Exerry(c + d'11) y²) where y² A2 as in Lemma 3.2 Using Lemma 3.3 we get that
(c (c+ccl)T((++ (x' - -²² Σ ((c) - +5)
- (af - vi)
Σ
(cc - (2) (c) 1) A - (xf.v)) ((c) cb) -(t-1 c)-
7
= < Σ \- ((c) - 2z²² ( (1--- - - ))
T
= 7 >> (c) cb2² (xt - A (aftt ))) s 0()2T)
t=1
Hence Rutt (T) 5 0 (log T /7 + (T) 50 (log2/33 2/3 T. T1/3) for 7 = o
6

---

3.1 The n- n--Dimensional Simplex
In this section we extend Algorithm to the case the n-dimensional simplex. Our extension is motivated and builds upon the CFR algorithm develloped in the context of EFGs [44]
Without loss of generality
2" We consider a complete binary tree T(V, E) of height H = log n where the leaves I S V corresponds to the n actions, |7]] = n. Each node E V admits exactly two children with {(s), r((s) respectively denoting the left and right child. Moreover, [evel(h) S V denotes the nodes lying at depth h from the root [eevel
assume that
(root) and
Level(log n) L). Up next we present the notion of policy on the nodes of TV,, E).
Definition 3.5. * A policy over the nodes V + AS encodes the probability of selecting the left/right child at node s E V. Specifically x (s) = (I(((s)) s), (r((s)|s) where (({(s)
[r(())s)) = and x {s) is the probability of selecting {(s) (resp. for r(s)).
Pr(s, i, T) denotes the probability of reaching leaf E L starting from node E V and following π(-) each step.
x= A. denotes the probability distribution over the leaves/actions induced by x²-). Formally, we have x. := Pr(root, i, T) for each leaf E L. Definition 3.6. Given
vector e [-1, for the leaves/actions, the virtual cost of node E V under policy (-)), denoted as Q(s, πT, c), equals
{ Co
s L
((..TTC): = { Lier. Pr(s,i,)) 8 L
The virtual cost vector of V under (T-) is defined as g(s, n, c) == (Q(e(s), n, c), Q(((s)))())))))))))(()))))))QQ x, e)).
We remark that (s,, π, c) is the expected cost of the random walk starting from V and following policy (-) until a leaf E L is reached in which case cost e occurred.
Our online learning algorithm for the n-dimensional simplex is illustrated in Algorithm
Algorithm 3 An Online Learning Algorithm for the n--Dimensional Simplex
1: Input: A sequence of cost vectors c',....,'' E []
2: The learner constructs a complete binary tree T), with L A.
3: for each round = 1....,2 do
4: for each h log to 1 do
5: for every node s Lev do
6: The learner computes & (8, a = (.))))),, sets
and
>'(s)= = arg min zEA,
2'(8, dd Σ (a(3, -5 c- a(8 ,()) x + R(x)/7
7:
end for
8:
end for
9:
The learner selects x' := =²" E An (induced by policy ne Definition 3.5
10: The adversary selects cost vector ct E 10,1]
11: The learner suffers cost (c' + cct-1)
end for
We remark that at each round f, the learner computes policy 7-)- as an intermediate step (Step 6) that then uses select the probability distribution x² ,. A. (Step 9). Notice that the computation of policy (-)) is performed in Steps (4)-(8). Since nodes are processed in decreasing order (with respect to their level), during Step 6 r'(() (-) has already been determined for nodes f(s), r(s)
and thus Q (f(s), n², d=1)). Q (r(s), cl-1) !) well-defined.
Up next we present the main steps for establishing Theorem 2.3 key notion in the analysis of Algorithm 3 is that of local alternating regret of node E V presented in Definition 3.7 As established Lemma 3.8 the overall alternating regret of Algorithm can be upper bounded by the sum of the local alternating regrets of the nodes lying in the path of the best fixed leaffaction.
7

---

Definition 3.7. For any sequence c'.....,,'' E...,,,e1111, [-1,,1] the alternating local regret of node 8 E V,
denoted as Roc (s), is defined as
Rooo( (5) = Σ (a(s, ( c') + ((, d) ('()) ,(8,x',''')))
Σ LE(T]
(Q(a, T + Q(a, (', c)
min (E(()))r())
(E[T]
Lemma 3.8. Let leaflaction E L and consider the path p (root $1..... 8H 1) from the root to the leaf i E L. Then, Ei=i(e' +c-11) - c - Et (se)
Up to this point, it is evident that in order to bound the overall alternating regret of Algorithm 3 we just need to bound the local alternating regret any node 8 V. Using Theorem 3.4 we can bound the local regret of leaves i L for which q(i, x", c this approach does apply for nodes $ E V since the local regret does not have the alternating
q(i, x' ,'- However
structure, q(s, n², ct 2 # g(s, x'-| ") To overcome the latter in Lemma 3.9 we establish that ((,,, T
4(8, T², c.- ,²,ct=+),
1 are in distance O (7) which permits us to bound (8) for E V/L
by tweaking the proof of Theorem 3.4
Lemma 3.9. Let π.
xT the policies produced by Algorithm then for any node s E V, (s)]l I 48y and ii) [19(s; n², c -(s, T
Il S 48y log n.
Using Lemma 3.9 we can establish an upper bound on the local regret of any actions s E V. The proof of Lemma 3.10 lies Appendix B and follows similar structure with the proof of Theorem 3.4
Lemma 3.10. Let 7 = o
(log" log" 1/3 /3 /TT/3/ ht/////1o"///// log'/² n))
in Algorithm then Ri
1/3 n T1/3) for all V. O (log 2/3 T. T.o
Theorem directly follows by combining Lemma 3.10 Lemma 3.8 and H llog
4 The Ball case
In Algorithm we present an online learning algorithm with O (log 7) for D = (B, 1) and 122 < 1. Then through the transformation â, := + px with x' E B(0, 1), Algorithm 4 can be transformed to a O (plog, log -aalternating regret algorithm for BCc,p).
Algorithm 4 may seem complicated the first sight however it is composed by two basic algorithmic primitives. At Step 4 A computtsse computes the output w; E B(0, 1) of the Follow the Regularized Leader (FTRI) with Fuclidean regularization and adaptive step-size ro: (Step 3 of Algorithm At Step 5. it mixes the output E B(0, 1) of FTRL with the unnormalized best-response ((0, 1). The selection of the mixing coefficient Pt is adaptively updated at Step 7.
4.1 Proof of Theorem 2.4
In this section we present the main steps of the proof of Theorem 2.4 In Lemma first upper bound on the alternating regret of Adaptive FTRLL
4.1 we provide a
Lemma 4.1. Let w,...., WT E BB,, 1) the sequence produced by Adaptive FTRL (Step 4 of Algo- rithm 4 given as input the cost-vector sequence c², ....., 6. E &B(O, 1). Let I denote the maximum lime-nddx such that Ei= (c + (0-1)T We 2 - -' l|e + c 111/44 Then,
Ede + 21 Te, t=1
min (E
(d
< 4
1
1+ Σ
le + ct 1 + (logT)
Lemma 4.1 guarantees that Adaptive FTRL admits only o(VT) alternating regret in case f1 = o (T). Using Lemma 4.1 establish Lemma 4.2) which is the comerstone of our algorithm and guarantees that once Adaptive FTRL is appropriately mixed with unormalized best-response (-c--1), then the resulting algorithm always admits Olog T') regret.
Lemma 4.2. Let Wi...., E B 1) be produced by Adaptive FTRL given as input c¹ ...., .....cT E (5, 1) and t be the maximum round such that ('= + 1 T 2 -' ||c* + 1
8

---

Algorithm 4 Online Learning Algorithm for Unit Ball
1: P1 0, Dj < [0, 1] and c (0, ()).....).
2: for each round = 1,"
do
3: The learner computes the coefficient ro & 1 Dam |ce + c-
4: The learner computes the output of FTRL,
We f- argmin
|
E
(ce + 10-1)
r0:t-1
2
||01
# Adaptive FTRL
5: The learner selects the action x' +- (1 pe) + p -pe(-c'11)
# Mixing Adaptive FTRL
with Unormalized Best-Respp best-Response
6: The adversary selects cost et with ||e| 122 S and the learner suffers cost (c--1 + c
7: The learner updates the interval D, [0, 1] as follows,
1, (1,
20
Dr +
0, min
V 1 E. 1|e + c
and then updates the coefficient Pt E [0, 1] as follows,
20(c + cc-1)T +
Pc+1 f
Pt +
1 Σ | + t 11
8: end for
Let p = 20/ / + Eti ||el + cl and let y: = (1 p)wt pc- for t S t and ==
fort 2 1 1. Then Etm (ct + d y1 min E (ee + dT x s 0 (log T").
Lemma 4.2 establishes that in case at Step Algorithm mixed the output wi of Adaptive FTRL with the unormalized best-response (-c--1 E B(0 1)) as tollows.
20T (1 S 41]
= (1 qt) we + qt (-c--1) with q =
400 + >t= l|ct + ct
then it would admit (loo 7') alternating regret. Obviously, Algorithm 4 does not know a-priori
neither nor Ee ||e_ + cL-11 However by using the recent result of (5) for Online Gradient Descent in Shrinking Domains, we can establish that the mixing coefficients pt E [0, 1] selected by Algorithm 4 Step admit the exact same result selecting Gt [0, described in Equation The latter is formalized in Lemma
Lemma 4.3. Let the sequences Wi, WT E [B(0, 1) and Pi...., pr E (0,1) produced by Algorithm given input c² ct....,c'' "... Bi0, 1). Additionally let t denote the maximum time such that Et=i(c" + c-1))Tu, W. 2 - ||e* + -- c²-111// and consider the sequence
q: = St) (20/
/0///400 400 E/h ||et + c Then,
Σ cd) tc-l)).. .q- Σ (c'l +c) +c-l)) (d-1).p .pppp.. S O AE[T]
TE
Conclusion
In this paper we introduced a variant of the Online Linear Optimization that we call Alternating Online Linear Optimization for which we developed the first online learning algoithms with of VT) regret guarantees. Our work is motivated by the popular setting of alternating play in two-player games and raises some interesting open questions. The most natural ones is understanding whether

---

(1) regret guarantees can be established the n-dimensional simplex well as establishing o( VT) for general convex losses.
Limitations:
The current work is limited to the linear losses setting. Notice that the classic reduction from convex to linear losses in Standard OLM no longer holds in Alternating OLM. Therefore the generalization to general convex losses seems to require new techniques. We defer this study for future work.
Acknowledgements
This work supported by the Swiss National Science Foundation (SNSF) under grant number 100021_205011 by Hasler Foundation Program: Hasler Responsible AI (project number 21043) and Innovation project supported by Innosuisse (contract agreement 100.960 IP-ICT). Luca Viano is funded through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. This research also supported in part by the National Research Foundation, Singapore and DSO National Laboratorics under its AI Singapore Program (AISG Award No: AISG2- RP RP-2020-016) grant HEESG-AA-22220 AME Programmatic Fund (Grant No.A20H60015)) from A*STAR and Provost's Chair Professorship grant RGEPPV2101.
References
[1] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736-749. ACM, 2022.
[2] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wee Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(log T) swap regret in multiplayer games. CORR, abs/2204. 1417, 2022.
[3] James P. Bailcy, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 391-407 PMLR, 2020.
[4] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 822 831. PMLR, 2020.
[5] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, pages 22222,, 2021.
[6] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Power of hints for online learning with movement costs. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, volume 130 of Proceedings of Machine Learning Research, pages 2818 2826. PMLR, 2021.
[7] Nicolo Cesa-Biande and Gâbor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[8] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis., 40(1)):20-145, 2011.
[9] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett,
10

---

editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages
2019.
[10] Tatjana Chavdarova, Matteo Pagliardini, Sebastian U. Stich, François Fleuret, and Martin Jaggi. Taming gans with lookahead-minmax, In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021.
[11] Steve Chien and Alistair Sinclair. Convergence approximate nash equilibria in congestion games. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIC SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, Jamuary 7-9, 2007, pages 169-178. SIAM, 2007.
[12] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493-1529. PMLR, 2018.
[13] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 235-254. SIAM, 2011.
[14] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 27604-27616, 2021.
[15] Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with hint. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 5299-5308, 2017.
[16] John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT 2010- The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pages 257-269. Omnipress, 2010.
[17] Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour, Regret mini- mization and convergence to equilibria in general-sum markov games. CoRR, abs/2200..1421, 2022.
[18] Gabriele Farina and Tuomas Sandholm. Model-free online learning in unknown sequential decision making problems and games. In Thhrtty Fiitt AAAI Conference on Artificial Intelligence, AAAI 2021.
[19] Gabriele Farina, Robin Schmucker, and Tuomas Sandholm. Bandit linear optimization for sequential decision making and extensive-form games. In Thirty- -hitt AAAI Conference Artificial Intelligence, AAAI 2021.
[20] Yoav Freund and Robert E. Schapire. A theision- generalization of on-line learning and an application to boosting. J. Compus. Syst. Sci., 55(1): (111))11991113) 139, 1997.
[21] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective generative adversarial networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[22] Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Robust no-regret learning in min-max stackelberg games. In 21st International Conference on Autonomous Agents and Multiagens Systems, AAMAS 2022.
[23] Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(3-4):157-225, 2016.
11

---

[24] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: regret bounded by variation costs. Mach. Learn.. 80(2-3):165-188, 2010.
[25] Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In Nader H. Bshouty and Claudio Gentile, editors, Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, volume 4539 of Lecture Notes in Computer Science, pages 499-513. Springer, 2007.
[26] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 2388-2421 PMLR, 2021.
[27] Niklas Lauffer. Mahsa Ghasemi, Abolfazl Hashemi. Yagiz Savas, and Ufuk Topeu. No-regret learning in dynamic stackelberg games. CoRR, abs/2202.04786, 2022.
[28] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. 108(2), 1994.
[29] Haipeng Luo and Robert Schapire. Achieving all with no parameters: Adanormalhedge. In Conference Learning Theory, pages 1286-1304. PMLR, 2015.
[30] Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 18(1):31173116, 2017.
[31] H. Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. J. Mach. Learn, Res., 18:90:1-90:50, 2017.
[32] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007.
[33] Peter Park, Martin Nowak, and Christian Hilbe. Cooperation in alternating interactions with memory constraints. Nature Communications, 13:737, 02 2022.
[34] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 The 26th Annual Conference Learning Theory, volume 30 of JMLR Workshop and Conference Proceedings, pages 993- JMLR.org, 2013.
[35] Mehmet Fatih Sahin, Armin Eftekhari, Ahmet Alacaoglu, Fabian Latorre Gómez, and Volkan Cevher. An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 13943-13955 2019.
[36] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Gamett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 20 pages 2989-2997, 2015.
[37] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold' em. In Qiang Yang and Michael J. Wooldridge, editors. Proceedings of the Twenty-Fourts International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 645-652, AAAI Press, 2015.
[38] Tim Van Erven and Wouter M Koolen. Metagrad: Multiple learning rates in online learning. Advances in Neural Information Processing Systems, 29, 2016.
[39] Chen-Ye Yu Wei, Haipeng Luo, and Alekh Agarwal. Taking a hint: How to leverage loss predictors in contextual bandits? In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event |Graz, Austria), volume 125 of Proceedings of Machine Learning Research, pages 3583-3634 PMLR, 2020.
[40] Andre Wibisono, Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. In NeurlPS, 2022.
12

---

[41] Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B. Grosse. Near-optimal local convergence of alternating gradient descent- ascent for minimax optimization. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, volume 151 of Proceedings of Machine Learning Research, pages 7659-7679. PMLR, 2022.
[42] Guojun Zhang and Yaoliang Yu. Convergence of gradient methods bilinear zero-sum games. In 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
[43] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Tom Fawcett and Nina Mishra, editors, Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 2 21-24, 2003, Washington, DC, USA, pages 928-936 AAAI Press, 2003.
[44] Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Pro- cessing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, NIPS 2007, pages 1729-1736. Curran Associates, Inc., 2007.
13

---

A Omitted Proofs of Section
A.1 Auxilliary Lemmas
Lemma A.1. The log-barrier function R(x) = loog x -log(1 x) is 1-strongly convex in [0, 11.
More precisely, for all 2, [0,1]
R(v) 2 + R ( (y) x) + - y1
Proof. Let f(z) ;= log then f'(x) - and fx)x) प.. Since S 1 we get that f"(x) 2 and thus
f()) 2 f(x) (x) x) ク (s y)²
At the same time the function f(z) = log(1 x)) convex in [0, 1]. This concludes the proof.
Lemma A.2. Let argmin hnc R(z) and y argmin hrè R(2)] where R(-) is 1-strongly convex function in R. Then,
I yl S 2 |c -
Proof. By the strong convexity of the function we get that
yc + R(2) and first order optimality conditions for
1 l y/²
qc y + R(y)
7C' x R(x) +
As result, get that
2 x y
1 7c (y - 2) + R(y) R(x)
7d (y - x) + 7(c 2) (y x) + R(y) - R(x)
s 7(0 6) (y z) z)
which implies that [x: yl < 2 lc - al.
A.2 Proof of Lemma 3.2
Lemma 3.2, Lety' .....y"" 8 E Ag where y/ = min [ + d' x Di=l +c- +(())//
Then, ELn (c' + c'-1)Ta² min Σt (c) + d 2log T +
Proof. We start by rewrite the regret minimization problem over A equivalent one over [0, 1]. that is
T
T
(d
(c' + (c' + (x'- Σ
1=1
where e =c cb. Moreover notice that
E(er + + log + log(1 p)
vi arg min
(4)
pE[0,1] Lrl
?
By the "Follow the Leader/Be the Leader" Lemma
Lemma 3.1], , we have that
T
log + loog(1 - vi)
T
logp + log(1 1 p)
Σ (6 + ot D
min pE[o.1]
Σ
(at + ct-1)
That implies
T
log log(1 p)
Σ (2' ct o
< min
Σ
(c + 201)
pE
14

---

Now let = arg pe((o.. Ei= (c' + c'-1)p and let us subtract Ei= (ce + +z=1)z² from both sides
Σ (C' + +)= logp log( p)
Σ e + (e1 -vi-
x²)
min pE(O.1]
Σ
(e' + v)
7
In case x= we upper bound the minimum the right hand side with the same expression evaluated at = 1/T. As a result,
1 (c' + ct 1
log(7) + log(1 - +
de' + 1 - -0) 5 t=1 Σ 1=1
7
log (T) + log(
T
2log T
2
T-1
22
(5)
In case x² 1, we upper bound the minimum on the right hand side by the expression evaluated at p = 1 - 1/T. As result,
log( + + logg( +)
cc 8- Mot 1)
Σ (c' 1
(1-7)
Σ (c
2'-1)
log(T) + looo( T
2 2 T
2
2
(6)
Therefore putting together Equation (5) and Equation 6). we can conclude that Et= (ce (c!-
minge(2] Ei (c) ot 1 log T/7 + 2.
A.3 Proof of Lemma 3.3
Before presenting the formal proof of Lemma 3.3 we present Lemma A.3 A.3 and Lemma A.4 that are necessary for its proof.
Lemma A.3. Let x' as in Algorithm 2 and vf be the BTRL update as in Lemma 3.2 with R(x) =
log x log(1 I)) and x be the update in Algorithm 3 Then the following hold.
o vil S 8
of - x S 16y
vf w < 87
Proof. Notice that for any y E A2 and cost vector c (2) E TR?, we have that
(x v) ei (a1 vi) c2 v2) = cI v1) c2(-x) v1) (x1 - v1) - -02).
This means that
reduce the bidimensional update in Algorithm 2 as
cg 1) log + log - p)
#1 arg min pE[0,1]
2 1
Σ (
At this point, using strong convexity of the log barrier function (Lemma A.1 the form of the updates in Equation (4) and Equation 77). we can invoke Lemma A.2 using x
o and = yi. this gives
| - ví < 2> | 20 ci cf + c +
< 8y
where we used that the cost sequence is in [-1, 1]. For the second fact, invoke again Lemma A.2 but with = of and a and we obtain
| - < 27 22 20 of - oj-1 + ch + oog
26 20/ < 167
For the third fact, we use Lemma A.2 but with x = y and = yit and we obtain
++ 27 |ett1 ot ct + cs 8
15

---

Lemma A.4. Let (x. v) E 10. and (x', v/) E [0, 1]2 such that |x yl - B, |r 38 s B.
Io' - B and xz' 3/1 - with 3 8 then
AA (r, (-' 192/ r' 192/y - s'1
where A(x,0) v)
(ry))))(ry--yy1111 x1 - yy-
Proof. To simplify notation we denote 2₁ := + t)a² and yt := ty + (1 t)y/ Then
(x, A (x' / (VA (2,,
(2,, Be). (z, v) - (x', v')) öt
< max [E[0.1]
( 800 11 y) (æ', 1')l11
(8)
Let us focus bounding
V A (art, y/ )
po- Notice that
0A -A- (x'z, 3/
3
(9)
dr
((1 21) y1) x,ya))
Now, notice that (at, Mel I f|r - yl + (1
1)(=' 5/1 S B. Using the latter we can lower bound
the denominator of Equation 9 More precisely,
(1 x1) y6) + zttl = 2 (1 zx)² 2 + (2xg () xz)
1
12xz - 11 1/2 x1
4
2
B
4
So for B < \ we obtain
0A 0A 1 (Its 311
8 = 192.
dr
By symmetricity, we can bound with analogous steps the partial derivative wrt to y and hence we get
|AAA-' Be 192.
Plugging this bound back in Equation concludes the proof.
Lemma 3.3 Let xt
(zf z5) Ag as in Algorithm and y' = (yi, 1²2 A2 in Lemma 3.2
Then,
o - vं - (af vi) ((c) c5)) (c - ---11--1) 1)-
with A(x1.31) = (I1v1) + - (1-z1) (1 (1- and | (xf. vi) A A-' (-f b < 0()).
Proof. In order to prove this Lemma 3.3 we use the equivalent one-dimensional description provided in Equation I0
V (cf og + c c log p log(1 p)
2 arg min 2(c ol- )p
(10)
pE(o.1]
?
Similarly the update of BTRL in Lemma 3.2 can be equivalently descirbed as,
- +e -65- 15-1) log + log(1 p)
v arg min pE
(11)
?
1==1
Since lim 10.11 R(p) both of ví [0, 1] \ 00, 1]. Therefore, the first order optimality for
Equation requires that
-1-1
+
Σ
c + -c8
1 0
1
(12)
2
16

---

Using the same reasoning for the BTRL updates in Equation 4
1
<c c5) + +
-
-
+
0.
(13)
y
Vi
Now, subtracting Equation
12 to Equation
13
we obtain
1
1
>(c c2 ci + c
1
that implies
( -c) 7
{zf
vi)
+
(1 vi (1 x
A(afa1)
Therefore, can express the difference between the updates as a function of the costs according the following formula
of ví = 7 vf) ((c) cb)) (c) 1)-
(14)
We conclude the proof by establishing that
A 'a'
(21. v/) A 2-'aeeea (aft) bbtt)| s 0(7).
By Lemma A.3 we are ensured that
o vil S BY
o x1+1| < 16y
vi yi* | $ 8y
In case 7 - 1/(16 8) we are ensured that the conditions of Lemma A.4 are satisfied (B S 1/8) and thus
| A A (a / 192( [z] 2
+ lf 1/t11)
Combining the latter with the guarantees of Lemma A.4 we get that
( vf) A (x s1 )+))| s -
17

---

B
Omitted proofs for the n dimensional case.
B.1 Auxiliary Lemmas
Corollary B.1. i) Q(8, = (((8, i0) Q(root,
=
Proof. For fact i) for any E Level(h), have that
Q(s, = Σ i,(s,
iEL
Σ ((((()))))P((((()..) + Σ (((()))))PP(((())....))))
iEL
SEL
= =(({))]ss) HEL
ir( + Σ &r(
IEL
= + (
c) (s)
where the second last equality uses the fact that 8 Level(h) = r(s) Level(h + 1). Finally, fact ii) follows trivially from the definition of x². Indeed, we have that
(i)
Σ
Pr(root, i, T)c; Qroott, C.
ieL
ieL
B.2 Proof of Lemma 3.8
Lemma 3.8
Let leaf node L and let p (root 81...... i) denotes the path from the root to Then the following holds,
dd +
S
Rioc
1=1
acEp
Proof. By Item 2 of Corollary
B.1 and the fact that c = 0, we get
T
T
Σ 1=1
(c + c
2
(Q(root, c²) + Qrroo, n", -,,")))-(((,,,,))-((- c(-
1=1
1=1
(Q(se, ( - Q(94410'1
((s
Σ
(Q(se, n,, ,,,, + x1,s,x"',c=111
min aE(((e)))(e)))
(Q(a, + Q(a,
(u(s,,"', c') + g(se, x c(1)) (sr))
T
min
Σ 10 + Q(a, d'11))
Corollary B.I
(((((s)))(s)))
(se)
2pEp
18

---

B.3
Proof of Lemma 3.9
Lemma 3.9
Let T ..... T the policies produced by Algorithm
3 then for any state s E V.
(T n (s)l S 48y and ti) [lq TT, c/= q(s T c S 48y logn.
--1
Proof. We first establish that (s) n' (s)]l I 48%.
Let ((s, n, c) == Q(((s), c) - Q(((s), the following one dimensional form,
( q. c) then policy update in Step 6 of Algorithm 3 admits
(E(s)ss) arg min z=|o.11
27(Q(s, Q(s x , c)- +7 Σ (Qs,,TT Ü(, ( + R(x))
Similarly for the policy --
1-2
x' (E())ss = arg min
(' , cl-1)) + Q(s, nt_1 ( 2) + Σ Q(, + ((s, + R(x)
Using Lemma A.2 we get that,
(e((sss)s) x²- ( s 27 20( (',, + +2 n', (-- + Q(s, x'~ ,--1,'--) Q ((s,x"=1,d'
10,,x-111-11 -2Q(2, / c'- s 2247
where the last inequality comes from the fact that -1 -1 - Q(... < and thus [0 x)) $ 2. Up next establish that
lqq(s, n 11 ( 1 I 1ogn.
To simplify notation we let ho denote the depth of state so E V. Up next we prove that [1q n²,, c1-1 ((50. m c 11 < 48ylog
In order to prove the latter we deploy a coupling argument by considering two correlated random walks (8o, so); (81, s1 (i,,.... ..., (sn, s'H) where both walks are initialized at (80,80) while at each level E (lo...., H 1]. the first walk marginally follows policy π E 22 while the second walk marginally follows n' A2.
More precisely, let (sh, sf,) the pair of nodes visited respectively by the first and the second walk at level h E {ho.... !l 11. Then the next pair of nodes (sh, s%,) follow the following joint probability distribution.
In case s/1 A sn: The next pair of nodes (Sh+1, 1/+1) are independent random variables respectively following x(s)) E A2 and n' (ss))) E Az. More precisely,
sh+1 ={
((s)) w.p. [{{(s))(sN)
((s))) w.p. <(((<())s()
and s =
r(s)) w.p. 1 - ((((s)) (sx)
r(sh) w.p. 1- 1- (1(s)))))
In case 8h. s/, and (({())]s) < x ((((s))ss) Then the next pair of nodes (s5, sh fol- lows the joint probability distribution,
(((s),{(s) w.p. ({{())ss) (r(s),((s)) w.p. (((()))a) (r(s),
w.p. 1 1()(((())ss))
In case S). = -/ = and lows the joint probability distribution,
and (({())ss) 2 ({(ss)ss Then the next pair of nodes (s), sy,) fol-
(e(s), w.p. {{(s))ss) (e(s).r(s) w.p. =({(s)ss)- - ({(ss)ss (r(s),r(s) w.p. ([(ss(s)
(sh+1, shett)=
19

---

The above joint random walk, guarantees that the first random walk (resp. the second) follows policy (resp. n' for the second coordinate). More precisely,
Pr[sa+1 - ((s) sh s] ({{())]s)) and Pr [5/+1 = E(s) s/ s) = ({{s)))
As result,
Eie cr = (su n, c) Qs50, rc)
where (i,1') E L L denotes the pair of leaves reached by the joint random walk initialized at 80 V/L.
1Q(so, x. Q(50, T², , = |E - cpll E ||q - -rrl
E [[c crl |1/+11 # S/+1. 8n = P [s # s441, 5h =
h= (Eeeve(())
2
P Plsh+i # sht1, =86 =s]
1= sELevel(h)
Σ
P P # s/41l6h = 8h s P 8h. =s
k= sELevel(h)
H-1
2
([((()]ss) ( Plsh, sh
k=hp sETevel(A)
where in the second equality we used the fact that {6/+11 + 5/ = Shh = =8} = SEVhhe[ are disjoint events.
By setting n' = n². and π = rt-1
we get that
H-1
1Q50. .', -((o,, -- .c)l 2
Σ
Σ
((((s))ss) - (e(ss(()) P(s/, 8% =s]
h by sELevel(h)
< 487 Σ
Σ
P(sh 8h. =)
sELevel(h)
H
48y
Σ
1 48y log
Finally,
[[a(so, n², (c-1)) q(S0, -' --)
1Qa, Q(a, x--1, 1-1,c(-1) 48y log n.
max at ((()
B.4 Proof of Lemma 3.10
Lemma 3.10 Let y = O [1og2/3 / T/ /3 (22/)))))))))))))))) in Algorithm then RT
(T (s)
o log 2/ 2/3 T -
1/3 T1/3) for all V.
t Let also introduce
1 (og(T)
Proof. Let the step-size 0 of Algorithm 3 defined as y= 32.8 [Toggn the BTRL. update for state that is
# 7'(s) = arg min ZEAg
(q(s, + + x R(x)/7
(15)
20

---

We can bound two separate sources of regret, according to the decomposition
T
(8)
a(0,"'=' ((. ,d)) (+)))
min
T + Q(a, x(a,x*=1,,)))
(((())))()
Term
((s,)) (8)
(16)
Temm
First, we recognize that Term I is the BTRL local regret, therefore applying Lemma 3.2 we have
Term S O log T
Then, it remains to bound the term that quantifies the closeness between o and 5f, that is
(g(s, x.) + (09,x"1,,c)) - -s
Let (= ((r(s),( x, then by using Corollary B.1 we get that
(g(s, d') x'= x(,,x"=,,c)) (TT' #*))) Σ (m - *'([(s)|s)
(17)
At the same time by Lemma 3.3 get that
x ({(s)ss) ({(ss)ss =y @', c²) Q(..
(18)
#((s))
Hence combining Equation 17 with Equation
18 obtain
T
(s n', - dd-
+ ((s Σ (() ,()) (T'()) - #()) =7
({()))s) ((())))
At this point, notice that unfortunately (s T², cl-1) that depends on both indices t and - To go around this issue, we add and subtract (G. 1
not rearrange the sum easily because of the term
the term A( (15)))))))))))
(s c')
(q(s, n' d') + g(s, x11 (1))) (T7(() #'(s))
1=1
('s d-l) Q'
A(T (((
(19)
Now we bound the first term. Notice that the assumption of Lemma A.4 are satisfied with B =32- and that (8 (8-32)-1 ensures B < }., Therefore, rearranging the sum and invoking Lemma A.4
21

---

I -
= = 3/ = x-+1, we get
T @'ss ((,,,='-1,--111) = (117(())))))
T-1
A(F)((()))s), (1 ({{s){s)
((s)s)
# (({(((())ss))
('(s,
1
((s))) *+1((()1s))) ('((.
((T(((())))
('(s,TT,c))
(())))) ((()))))
Lemma A.4
1927
7 e)) ([=(((())))) -
# (c())))))
+ (,, (F'((())))) +(+)))))
Lemma A.3
1927
(s, (24 47) + 70 T.. A
491 28-2 + 327
where in the last inequality we used (s, n", e²) S 4 Vt and A(" A(*² s). x ((()))s)) 1
Then, for the second term in Equation 19 we use the second fact Lemma 3.9 In more details, we have that
2 @-( ((8,1) - ('(,,
(())) 8), ((({))()))
(Q(s,T (1s,, + (s, ((,, ((,,,)=-,,--))--- -(,, (',-1" c(-1)
A( A( ({())){))
(', 1 1) + Q(s n., dt 1) [(s, /' ,-,, - ((s, x d (T' (a) (
$
1=1
< 32
Q x ( - (s,
Lemma
32 4 log n.
Therefore
Term S 4- 192 28- + 32 -88 log n + 32% Therefore, neglecting constants, and plugging in the bounds Equation (16), we obtain
log T
RIc (s) S O
+ 2 logn
Therefore by our selection of 7 = O (log1/8 1/3 TT11/3 log 1/3
log m)) we get R.T (8) s 0 (1lo((T)} (log (log))))
B.5
Proof of Therem 2.3
Theorem
Let D be the n-dimensional simplex, D AAA.. There exists online learning algorithm A (A AIgorithm 3 such that for any cost-vector sequence Cı,... CI....,cy Cr E 1|'
2.3
(d TC)
min
6 + 5 (T\/3, log 4/3 (niT)
N' ED
22

---

where x' = -.(cc,....,c"*)))
Proof. By Lemma 3.8 we obtain that (T) & m (s)
Then, recalling that by construction = log n and using the bound on R% (8) in Lemma 3. 10 gives
Ra (T) z nlogn)- O (llog(T) (log ( .r
o (logg(T) (log n)
(llgg)337 88
C Omitted Proof of Section 4
In this section we present the omitted proof' of Section
C.1 Proof of Lemma
To simplify notation we denote é == cf 4 for / 2 1 where co = (0,....0) 0). Moreover we denote
with |-Il the euclidean norm |1-112. Adaptive FTRL (Algorithm admits the following equivalent form.
Algorithm 5 Adaptive FTRL
1: for round ,,...,T T do
2: The learner computes To:--
Σx=1 ||a,||
3: The learner plays w, argmin
|
--1 Σ
x=1 Ci
Tor-1 |
4: The adversary selects cost è with | la I 2 and the learner receives cost é. x
5: end for
Lemma C.1 (55) Let wi,-.., WT B(, 1) the sequence of points produced by Adaptive FTRL
given as inpul the cost-vector sequence êı,... êr and x² == argmin Σ CJ Then
for any index S E [T].
T
(Ws+1 - x²)++ +
Σ
& (wr - x²) = ro:S (1I=1| 112 (|05+1113)
1=$+1
Σ
(1 113]
aj (w+ wet1) Σ
2
1=1+1
1=5+1
where Fi = Toat T0:-- 1or 1.
Proof.
Let [x(x) = aî + マ ||| 12 where ro and 0. Let us also define fo.(xx
E' fe()). Since ên = we get that fua(r) = E. C. x + ro ||=]|| and thus w1+1 == (ngmin,e3(0.1)0dddl Then,
fo.r(x)) 2 Jor(WT+1)
(W(T++1) + fo:T-I
2 fr(WT+1) + (O.T-1(WT)
Σ fe(we+1) + (o:s(ws+1)
t=9+1
As result we get that,
Σ cJ xz + 2 (11)))))
Σ
i W ? (1oott11)) + Σ
c wus++++ + " (Ilwstall))
t=0
S+1
23

---

By rearranging the terms and using the fact that ćo and ro we get that,
T
(ws+1 - xx)++ +
&e (we - x²) $
ru:s
(1I=112 -110s+111))
2
+=
2 (11*1||- (1/++1199)
Σ of (w, w
S=1+1
1=S+1
Lemma C.2 (6)). , Let wi,..., WT E B(, 1) the sequence of points produced by Adaptive FTRL
given as input the cost-vector sequence .i,..., er and x² == argmin E Ej x Then,
T
T
r
Wi
x v 4.5
1 + Σ
|10
1
Proof. Applying Lemma C.1
with S = 0 we get that,
T
T
T Ft (1 1|2 |104t1122) + Σ
Σ
c
ut - x²) S
(we we+1)
(wr
(20)
T
To:T
27 (wi - wet1)
(21)
2
tml
0.5,
1
Σ
|
Σ c (we W2+1)
(22)
Up next we bound the second term. Let f((x)((===)))))))))) = E x + By Lemma 7 in [3 for fi == fo- and
f2 = foxt- Since f1 is 1-strongly convex with respect to the norm ra=-a||z|| and f2 - fi is convex and 2liesit-ipsschtzz Then since wy (0 (z) and w141 (2 Lemma 7 in [31] implies that
2|1sel|
&
[w W S
T0:-1
V 1 + Σ1-
||2,122
As result, get that
2112,
211a ||
os (we - wx+1) S [2.11] - wr+1ll S
5
V 1 + Σ 112,11
/
1
Σi=
1|
Summing from = 1 to T, we get that
Σ a (w, wx+1)
S 4
1+
Σ
|21112
Lemma C.3. Let Wi...., WT B(0, 1) the sequence of points produced by Adaptive FTRL given as input the cost-vector sequence Ci,..., Cr- Let any round t" E (T) such that for all 2 t" + 1,
Σ cal 1lc.11
and Σ 12 17
Then ||w:]| = for all t 2 t + and additionally,
cT (wi - we+1) S log + T).
24

---

Proof. To simplify notation we denote oz =
1| Moreover we denote E1. = E C, and
δ1.- E'==1 Gz By the definition of to E [T] know that for all t t' +
1 VI+ Tle
Ō1 21
4v1+ 1 ō1
where the last inequality follows by the fact that d1:t 2 17. Since we B((,, 1) the latter implies that |w,|| = for all & t* and thus,
Wr = 1010-111
and
w+11 =
|aal
61
61:1
|w w1+1l
||
11122111 ||
||2
C1:11
Č1:c-1
C1a-1 1
č1.t
+
11:2-11
|
| ||
|
||aall
| all
181:0-11 |1
||1:ell
|
-
11110-111
||&/1|
+
c1.1
[
|
s 2
&aall
where the last inequality follows by the triangle inequality, ||:rr|| S || |&ell. As result,
2|| 8||&&ll
we wi+1l - [ ||
<
T1:
where the last inequality follows by the fact that 2 t" + 1 and thus ||c 2 for... Finally get that,
Σ t=14
(w. wr+1) 5
| [w: wr+1ll
t=
8|
1 ō
t=
86
f=t+1
< log
1+
Σ Ōz
(=t+1
K log (1 + TT)
We conclude the section with the proof of Lemma 4.1 with the notation of the section.
We restate the theorem to be consistent
Lemma 4.1
Let wi,..., WT E B(0, 1) the sequence of points produced by Adaptive FTRL given as input the cost-vector sequence cI,..., Cr. Let i denote the maximum index such that
c Wi
E=1
Then the followig holds,
T
T Σ
T
min 1)
c
x
< 4
1+ Σ
1 2 +
O (logT)
t=
t=1
1=1
25

---

Proof. Let t2 denotes the maximum index such that Σ C w. I =|( and E3 the maximum index such that 0 S 17 (as in the proof of Lemma We consider the following 3 mutually exclusive case,
22 fax
Due to the fact that t2 2 t we have that for any t 2 t2 + 1,
-Ilcaall S
c wa S t
a=1
where the first inequality follows by the definition of l2 while the second by the definition
of 4, E._ E W. I - for all 2 t + Since to 2 ts we additionally get that
G1 2 17 for all 2 l2 + 1. As result,
||a=|l ll 2 dn and 01 2 17
for all t 2 f2 1
Meaning that the conditions of Lemma C.3 are satisfied for all ( 2 l2 + 1 and thus
T
aJ (w: (w--w--) S log (1 T) and ||w/l| = -1 for all t 2 12 + 1
(23)
1= Up next we analyze the regret of Adaptive FTRL,
cl (wi- x²)
c (w: x²) +
Σ
(we x²)
(24)
t=
1=
to
(w) Itz 1) +
(1ig+] - xx))
T
+
Σ
& (wi xx)
(25)
1mtz+1
12
12
-1122:211
Σ
cJ Dtat1
c (Itz+1 - =x")
1=1
2 (wi - x²¹)
(26)
1=
(1b++1 - xx")
Σ
oe (wr x¹)
(27)
t=1
(=1++1
Tod2
([|0*| |2=1|uta+11]
T
T
Pt. (11==112 - -| (1we+1l?)) +
Σ
a7 (w: wet1) (28)
2
1=
1=
T0:12
(||0*112 -1) (|
Σ
Tt
(1|=0 112
2
1=b+1
T
Σ c. (wi - w2++1)
(29)
t=t++1
T
Σ
c (w: w(+1) S log (1+T)
(30)
1=t++1
where Inequality (9) follows by the definition of to i.e. D/= cT x' < -1 I|- Inequal-
ity (10) follows by the fact that Eiz èπ Ftg+1 2 - Inequality (11) follows by applying Lemma C.I for S == f2. Equality (12) and Incquality (13) follow by Equation 23
26

---

t 2 max(t2, ts): By using the exact same arguments as above we can establish that
Σ
c (a'- I log (1 T)
and || for all 1 4 +1
(31)
1=
Using the exact same arguments as above we conclude that
(we x²)
c (wr x²)
Σ
& (we - xx)
t=1
t=1++
T
Σ ci (we wh++1)
ce (Wi++1 - -x")+
Σ
& (wi - x²)
b1++1
4.5v 1 01hh +
E (Wi,+1 x²)
Σ
(wre x²)
#=
4.5 1+ 014 + 1og(1+1) T)
where the first inequality follows by applying Lemma C.2 for T = i and the second by repeating Inequalities (11) - (15).
t2 2 max(ti, t3): By the exact same arguments in the previous case,
Σ c (w x²) s 4 + log (1 + T) - 4.5v + log (1 + T)
where the last inequality follows by the fact that diita I 17 (definition of (z).
As result, we have established that in any case,
Σ a [w) - x²) < 4.5, 1+ Σ | + log (1 + T) + 4.5v
C.2 Proof of Lemma 4.3
To simplify notation we summarize the Step 7 of Algorithm 4 in Algorithm 6
Algorithm 6 OGD with Shrinking Domain
P1 0, D1 + [0, 1]
2: for 1... do
3: The learner plays Pt D.
4: The adversary selects 2, and de S 1.
5: The learner updates the interval D, S [0, 1] as follows.
D2 +
0, min
1. (t
Ei (
A
and its actions P++1 [0, as follows
Pe+1 x- [pe 17 22lp.
6: end for
Remark C.4. We remark that Algorithm corresponds to Step 7 of Algorithm $ once
:= 20, z := (c' + c 1 (wi + d' and or ||c + c 1
27

---

Definition C.5. A sequence 9.....: E [0. 1] is valid in hindsight if and only if there exists round E [T] and a [0, 1] such that the following hold,
1. 4 = 8 I[ S ti] (4: = 5 for all s t" and = 0 for all t 2 t" + 1).
2. At the switching point t* E [2],
8² v
+ Σi
In Theorem C.6 we present the payoff guarantees of Algorithm 6 with respect any sequence ςt that is valid in hindsight.
Theorem C.6 ((5)). Let p Pr E [0, 1] a sequence of points produced by Algorithm 6 given as input the sequence (21, (1,,01)..... (2T: oT). In case of < 40, for all rounds E [T] then for any valid in hindsight sequence 91....,T7 E [0,1] (Definition
C.5) the following holds,
(pi 9)) s x (1 11 3
T
)
1
Σ E=1
01
We conclude the section with the proof of Lemma
Lemma 4.3 Let the sequence of cost-vector ct, ....., c² given Algorithm and the produced sequences ,,.
x' E An and PI.....PT (0, 1). Additionally let t denote the maximum time
such that
Σ (c + 1 w. 2 - Σ
l|ee c
1
and consider the sequence = 1/13540 H 41 holds,
220\/400 /400 + Ei= ||et + c-
20/
Then the following
[d) +wi+ c' - - +c)) (wo +c-l) (--1)-p1 Dr O(logT)
Proof. The sequence is valid sequence with switching point 1" = (1 and
20
6 =
400 + Σd1 ||el ct c
Now the sequence Pt produced by Algorithm Algorithm 6 with of the input sequence 2, Since
in Steps 7 and Steps 8 can be viewed as the output of
(ct + cl 1 T (w: dd-1) and o, ||e* c/-
X
1 + Σi=1 Øt
Lemma
follows by Theorem C.6
28


Reviews:
[{"review_id": "kD9LH1f2Nu", "reviewer": "Reviewer_EHgn", "summary": "The paper introduces a variant of the usual online learning model with linear losses, whereby the environment is constrained to produce losses of a specific form. Such a form appears naturally when studying alternating no-regret dynamics in games. The authors establish that this restriction weakens the environment, in that the decision maker is now able (at least in certain domains) to attain unconditionally a regret bound of T^1/3, breaking the typical T^1/2 lower bound of regular regret minimization.", "questions": "Could you please comment on my reservation above?\n\nAlso, I was curious to hear any thoughts you'd like to share about generalizing the algorithm to general convex and compact domains.", "limitations": "No negative societal impact concerns ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe this is a technically solid paper. While I have some reservations about the relevance of the model per se (that is, assuming adversarial losses of the specific form studied in the paper, which is justified by alternation), I think that taking the model as a given the result are interesting. The paper is also well organized and it is easy to follow the flow with a good understanding of the preliminaries on FTRL and online optimization.", "weaknesses": "My only reservation about the paper is about the specific assumption on the losses in general adversarial settings. While the motivation of alternation is clear in two-player games using self-play, I would be curious if the authors could make shed light on what situations their model can model.\n\nThe reason why I think the two-player alternation connection is not super satisfying is that in two-player zero-sum games, optimistic (non-alternating) learning dynamics attain constant regret per player. Similarly, in multiplayer general sum games optimistic dynamics guarantee polylogarithmic regret per player when used in self-play. Given that optimism does not come at a computational cost, it is not obvious why, in practice, one would like to focus on alternation but not optimism.\n\nThat being said, I have a positive opinion of the technical ideas used in the paper.\n\nMinor comments:\nThe paper would benefit from a pass of proofreading, as it contains a few typos. A few examples:\n- L294: I assume there is a \"beyond\" missing in the sentence?\n- Display after L170: the dots should probably be removed for consistency\n- L189: the symbol \\mapsto should arguably be a \\to in this case, at least according to what I consider standard notation (see also https://math.stackexchange.com/questions/473247/difference-of-mapsto-and-right-arrow).\n- Algorithm 3 italicizes keywords such as \"select\", while Algorithms 1 and 2 bold them.\n- L10: I believe it should be \"regardless _of_ the strategies\", but please double check with a native speaker ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your work and your positive feedback. Thank you also for spotting the typos. Up next, we answer your main points that we will also incorporate in our revision. \n\n1. *My only reservation...used in the paper* \\\n\\\nAlternating self-play has proven a valuable optimization tool in several real-life equilibrium computation problems, such as poker as well as generative AI problems, such as GANs [1,2]. From this perspective our work contributes to theoretically understanding the merits of alternation.\\\n\\\nThat being said, the main contribution of our work lies on the game-theoretic perspective. A recent line of works tries to go beyond the o(\\sqrt{T}) regret guarantees by either restricting the power of adversary (e.g., small updates [3]) or by using external information of the adversary’s behavior (e.g., hints [4]). \\\n\\\nOur work reveals that simple alternation between the agents, leads to O(T^{1/3}) (or even O(log T) for 2 actions) regret guarantees no matter the power of the adversary. The latter reveals a sharp phase transition between alternating and simultaneous game play at which  \\Omega(T^{1/2}) regret is tight.\\\n\\\nFinally we would like to remark that various aspects of alternation game-play have been previously considered in the game theory literature [5-10]. For example [9] studies the effect of alternating game-play in cooperative two-player games while it presents several interesting examples at which alternation naturally arises in the games related to animal and social behavior.\n\n$$ $$\n\n2. *Also, I was curious to...and compact domains.* \\\n\\\nWe believe that Algorithm 2 can be extended to general convex sets - by considering a log-barrier function capturing the convex set of interest. The main challenge in establishing the O(T^{1/3}) alternating regret guarantee for this algorithm is generalizing Lemma 3.3, which quantifies the differences between the output of Algorithm 2 and the output of FTRL, to general convex sets.\n\n$$ $$\n\n1] Solving Large Imperfect Information Games Using CFR+, Tamelin et al. 2014\n\n[2] Superhuman AI for heads-up no-limit poker: Libratus beats top professionals, Brown et al. 2018\n\n[3] Online Learning: Stochastic, Constrained, and Smoothed Adversaries,  Rakhlin et al. 2013\n\n[4] Online learning with imperfect hints, Bhaskara et al. 2021\n\n[5] Intrinsic robustness of the price of anarchy, Roughgarden et al. 2015\n\n[6] Convergence to approximate nash equilibria in congestion games, Chien et al. 2007\n\n[7] Finite regret and cycles with fixed 309 step-size via alternating gradient descent-ascent, Bailey et al. 2020\n\n[8] Alternating mirror descent for constrained min-max games, Wibisono et al. 2022\n\n[9] Cooperation in alternating interactions with memory constraints, Park et al. 2022 \n\n[10] Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization, Zhang et al. 2022\n\n"}, {"review_id": "feFkkZiWAj", "reviewer": "Reviewer_5x6H", "summary": "The paper considers online linear optimization where losses are given by $x_t^{\\top} (c_t + c_{t-1})$, where $c_t$ is the adversary’s choice at each round. The authors show that the standard $\\Omega(\\sqrt{T})$ lower bound no long holds, and give a $O(T^{1/3})$ regret algorithm over the simplex as well as a $O(\\rho \\log T)$ regret algorithm over a radius-$\\rho$ ball.", "questions": "- What are the barriers to proving fast-rate results for general convex bodies (e.g. in terms of ratio of inner/outer ball)?\n- Why is there such a gap between the ball and the simplex? \n- If log(T) regret is possible over the ball, it seems natural to expect it’d be possible over any convex body, which would then remove the need for a slower result on the simplex. \n- What is the intuition behind the tree design in the simplex algorithm?\n- Are there notable technical connections to fast-rates results for optimistic learning dynamics?", "limitations": "The connection to concept of “alternation” in games isn’t particularly convincing, and seems like it should be generalizable to broader settings (e.g. movement-bounded adversaries). \n\nWhy only the simplex/ball and not convex sets? \n\nThroughout, there are a number of key omissions of important related work, as well as too much emphasis on restating well-known prior results.\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper introduces a new setting for online learning with constrained adversaries, and gives two algorithms with new, non-trivial regret bounds. \nThe paper is somewhat easy to follow, albeit with some space allocation and presentation issues, and results appear largely correct (although the second algorithm is more difficult to evaluate due to reliance on prior work).", "weaknesses": "On the whole, this strikes me as a paper whose core ideas have the potential to be quite compelling if sufficiently extended and contextualized, but which leaves many relevant questions underdiscussed and is not yet ready for publication. \n\nTo start, the connection between the costs $x_t^{\\top} (c_t + c_{t-1})$ and “alternating gameplay“ could be better motivated; in such turn-based games, why should we think of players as experiencing costs in each round regardless of whose turn it is? Why we should consider this as our cost model for such a game rather than those enabled by e.g. extensive-form games or Stackelberg games? Both of the latter are well-studied from a regret minimization perspective and should be discussed in related work. The formulation given seems more natural as perhaps an example of a more general framework (e.g. when the adversary’s movements are bounded each round) rather than a primary focus in its own right without further contextualization within the broader game theory literature. For example, Remark 1.2 regarding convergence to NE/CCE should probably be omitted unless there is further discussion as to why these solution concepts are appropriate targets for the “alternating” setup (vs. something like Stackelberg equilibria).\n\nTheorem 2.2 is well-known and does not need to be proved in the body; you could maybe state it as a proposition and discuss more informally, but in general, it is not particularly surprising that a specific construction for one setting fails in a more restricted setting, particularly when there are many other known settings where faster rates are obtainable against constrained adversaries (e.g. strongly convex losses).\n\nThe alternating setup considered by [WTP22] is a feature of the algorithmic setup and not directly comparable here. It might be more natural to discuss relations to the long line of work on fast convergence rates (e.g. https://arxiv.org/abs/1507.00407). Perhaps there is a deeper connection between fast rates and bounds on the per-round movement of the adversary, which appears in these works as well.\n\nFurther, the results are only given for special cases (simplex, ball), and no lower bounds are shown. It seems initially a bit strange that the rates for the simplex and the ball differ so dramatically. Why are the algorithm designs for each so different? The intuition behind the algorithms should be highlighted further, possibly in exchange for moving some proof details to the appendix. Is O(T^1/3) optimal for the simplex? Also, it is difficult to sanity-check the $O(\\log T)$ result over the ball for correctness; this result indeed seems surprising for such flexible adversaries, and the technical results should be explained more clearly in the body in order to highlight the primary difficulties and innovations.\n\nThroughout, there are also a number of typos and broken sentences (ex. the statement of “Q2”).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your work and valuable comments. Up next we answer the main points raised in the weakness part. We hope that the following discussion (that we will incorporate in our revision) will help reconsidering your suggestion.\n\n1. *To start...turn it is?:* We remark that alternating game play at which agents update their strategies at a round robin scheme but all experience cost at each round, is a very natural dynamic in game theory and that is aligned with previous works [5-10] (refs in Rev EHgn). For example, best-response dynamics always allow only a single player to update their strategy. Nevertheless, in [5] the performance of no-regret as well as best-response dynamics is considered and in both cases the social cost on each day is the sum of all agents’ cost (not just the ones who moved) showcasing that all agents experience costs every day. Furthermore, intuitively, consider the case of two competing companies which alternatingly adjust to each other's strategies. Clearly, the update of the first company’s policy affects the second’s profits which in turn triggers a further update from the second company and so on.\n2. *Why we should...related work.:* \nStackelberg games inherently put one of the two players at a disadvantage. In contrast, in the context of the two company competition alternating game-play captures the competition between two symmetric companies. Alternating game-play can be extended to extensive form games - two poker players alternatingly adjust to each other's strategies over time (a strategy in EFGs is a collection of prob. distr. over the information sets). Extending our results to EFGs is a very interesting question that however remains outside the scope of this work. In the revised version of the paper we will thoroughly discuss the previous works in the above settings.\n3. *The formulation...“alternating” setup:*  Your suggested framework where the adversary’s movements are bounded within each round *is not* a generalization of our framework. Critically, when our the opponent updates their behavior (i.e. every other time-step) the updates can be *arbitrary*. More precisely, in the Alternating OLO, $||(c_t + c_{t-1}) - (c_{t-1} + c_{t-2})|| = ||c_t - c_{t-2}||$ which can be $\\Theta(1)$. We finally remark that NE/CCE are seminal equilibrium concepts in normal-form games regardless of the game-play (simultaneous or alternating). \n4. *Theorem 2.2...adversaries:* We will rephrase to proposition.\n5. *The alternating...as well.:* In the current write-up we have briefly discussed the long line of research of learning in games (including the suggested paper) - line 129. However we will include further discussion to better illustrate the differences.\nThe major difference with our work consists in the fact that in all the mentioned works the improved regret-guarantees hold *only if all* agents use the exact same algorithm (an optimistic method) which further implies small updates from the opponent. Our improved regret guarantees in the context of alternating game play hold no matter the choices of the adversary (that can be arbitrary away from their previous play). Totally distinct techniques are thus needed for our improved regret bounds.\n6. *Further...innovations.:* Extending our results to general convex sets is an interesting research direction that remains outside the scope of this work. We are not aware of any lower bound on the alternating regret.\nThe unit ball case admits a “simpler” structure compared to simplex permitting a more fine-grained analysis. At an intuitive level the cornerstone difference is that best response in unit ball with respect to $c_{t-1}$ is simply $-c\n_{t-1}/||c_{t-1}||$ while in simplex there might be a whole continuum of optimal points. In the revised version of our work we will discuss in detail the intuition behind our algorithmic design. \n\n*Questions*\n\n1. *Q1*: (As in Reviewer EHgn)   \n2. *Q2*: As mentioned above, the main reason for this discrepancy comes from the fact that a linear function always admits a unique minimizer in unit ball while it may admit a continuum of optimal points in the case of simplex. This “uniqueness property” of the unit ball permits an interpolation between the output of Adaptive FTRL and the greedy best-response (Step 5 of Alg 4). We remark that extending Alg 4 to simplex is very challenging since there might be not a unique best response with respect to $c_{t-1}$ while all the intermediate technical claims of the analysis of Alg 4 crucially use the simple structure of the unit ball (e.g. projecting a vector $c$ in unit call is just $c/||c||$).\\\nThat being said, we believe that the provided $O(T^{1/3})$ bound on the alternating regret  for the case of simplex could be improved to $O(\\log T)$ or even $O(1)$. However the latter requires new ideas and techniques and remains outside the scope of this work. \n3. *Q3:*  Yes however it is not clear how an O(log T) alternating regret algorithm for general sets looks like\n4. *Q4*: The tree decomposition enables us to reduce the problem in the $n$-dimensional simplex to the *easier* 2-dimensional simplex. The reason that in Alg $3$ we use Alg $2$ and not Alg $4$, is that two consecutive outputs of Alg $2$ are always in distance $\\gamma$ which is not the case of Alg 4 - see also our response to Reviewer waxV.   \nIn the revised version of our paper we will discuss in detail the merits of tree decomposition.\n5. *Q5:* Not really. As mentioned above, the improved regret bounds of  optimistic learning dynamics crucially rely on each agent using a specific algorithm permitting an end-to-end description of the overall system (the key idea is bounded-adversarial movements).  On the opposite front, our improved regret bounds for the alternating setting hold no matter the behavior of the adversary meaning that no modeling on the adversary’s behavior is possible. The latter creates several technical challenges and requires a set of novel ideas and techniques.\n\n"}, {"review_id": "OTV7xymSWn", "reviewer": "Reviewer_gHiT", "summary": "This paper consider an online linear optimization (OLO) problem motivated by alternating game play in two-player games. Specifically, after the learner chooses $x^t$ and the adversary selects loss vector $c^t$, the learner suffers loss $(c^t + c^{t-1})x^t$ in the alternating OLO instead of $c^t x^t$ in the standard OLO model. The adversary in the alternating OLO model is weaker than that in the standard OLO model and the main results show that $o(\\sqrt{T})$ regret is possible for the following two cases: (1) $\\mathcal{O}( (\\log n)^{4/3} T^{1/3})$ regret for the $n$-dimensional simplex; (2) $O(\\log T)$ regret for a $\\ell_2$ ball constraints (and when the agent has only 2 actions).  ", "questions": "The results of the paper holds in the adversarial setting. In the game setting, the two players use the same algorithm and are not necessarily adversary to each other. I would like to ask whether better regret guarantees can be achieved in the game setting when the two players use the same algorithm e.g., Algorithm 2 in the paper. Such a result would lead to faster convergence to CCE in two-player games.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The proposed alternating OLO model is interesting and has implication for game-play in two-player games. \n2. Although privous works show $o(\\sqrt{T})$ regret in some restricted cases such as unconstrained domain or when two players use the same algorithm, the main results in this paper hold for the n-dimensional simplex and against an adversary, which is stronger than privous works. The proofs of the main results are non-trivial. \n3. The paper is fairly well-written. The authors provided helpful intuition and high-level ideas in the main body, which makes the paper easy to follow. ", "weaknesses": "1. The $o(\\sqrt{T})$ results for the alternating OLO model only hold for n-dimensional simplex and the ball constraints, but not general convex sets. \n2. As the authors pointed out, the current analysis is limited to the linear loss setting, and does not directly extend to general convex losses. \n3. There is no lower bound results. \n\nHowever, I would like to remark that the current results are still very interesting and are important first steps towars solving these open questions. \n\nSome minor comments:\n\n1. Line 108: \"...OGD with admits...\"\n2. ALG2-Line 3: check \"2\\gamma (c^{t-1})...\"\n3. Line 195: $x^t$ should be $y^t$?\n4. Check line 529-530\n5. Check the last inequality on page 22\n6. Missing squares in the inequality on line 609\n7. The references of inequalities on line 637-639, 643 are broken.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your effort and your positive feedback. We will incorporate the minor typos that you pointed to in the revised version of our paper.\n\n*Questions*\n\n*The results of the paper...in two-player games.:* We believe that once both agents use the same algorithm (e.g. Algorithm~2) better bounds to CCE than the current O(T^{-2/3}) can be achieved. This question remained outside the scope of this work since we focused on the adversarial case however it is a very interesting research question."}, {"review_id": "PV9U42SiYx", "reviewer": "Reviewer_waxV", "summary": "The authors discuss a model of no-regret learning that simulates the use of *alternating* regret updates in a two-player game. In this model, the authors show that the classical lower bound of $\\Theta(\\sqrt{T})$ regret does not hold, and in fact, it is possible to achieve $\\tilde O(T^{1/3})$ regret.", "questions": "1. Maybe some typos?\n    * Remark 2.5: should that refer to Alg 4 instead of Alg 2? The stated bound for Alg 2 on $\\Delta^2$ is $\\tilde O(T^{1/3})$. \n    * Algorithm 3, line 6 ($\\pi^t(s) = \\dots$): should there be a factor of $\\gamma$ on the first $2q(s, \\pi^t, c^{t-1})^\\top x$, to match it with Alg 2, Line 3? If not, ignore my Q2 below, as this is no longer an analogue of CFR, but in that case I would appreciate some intuition as to why $\\gamma$ is suddenly gone from that term.\n1. I think your algorithm for the n-dimensional simplex looks a lot like a version of CFR ([1]; see [2] for a more modern exposition) applied on the binary tree $T$ with Algorithm 2 as the local regret minimizer. This algorithm, then, generalizes immediately to extensive-form games. Does the analysis also generalize? If so, that'd be nice to state.\n1. It is quite surprising to me that there is a gap in the power of $T$ between the $\\ell_2$ ball and the simplex. Such a gap certainly doesn't exist in usual models of no-regret learning. Is there any intuition for this gap? Do you believe it to be fundamental/do you have a lower bound against achieving $\\tilde O(1)$ regret in the simplex case? For example, what happens if you use Alg 4 as your building-block regret minimizer on $\\Delta^2$ within Alg 3?\n\n\n[1] Martin Zinkevich, Michael Johanson, Michael Bowling, Carmelo Piccione. \"Regret Minimization in Games with Incomplete Information\", NeurIPS 2007.  \n[2] Gabriele Farina, Christian Kroer, Tuomas Sandholm. \"Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games\", AAAI 2019", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I enjoyed reading this paper. It addresses a gap that has been observed empirically many times (the fact that alternating regret updates improves practical performance), and does so in a theoretically very nice way. The paper is also well written and easy to understand. I vote to accept.", "weaknesses": "I see no major issues, and I have only a few relatively minor questions; see the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the work and the valuable comments. We will incorporate your comments/suggestions in the revised version of our work.\n\n1. Thanks for spotting the typos! -Yes Remark 2.5 refers to Algorithm 4 - $\\gamma$ is not missing from line 6 of Algorithm 6 (since we have $R(x)/\\gamma$). The typo lies in line 3 of Algorithm 2 since again we have $R(x)/\\gamma$ and thus $\\gamma$ should be removed from $2c_{t-1}^\\top x$\n\n2. Thank you very much for the suggestion. Yes, our algorithm is very similar with the decomposition used in the CFR algorithm and generalizes for EFGs. We are confident that our analysis may carry over with some possible tweaks. We will include this discussion in the camera ready version.\n\n3. We also agree that having different alternating regrets for different convex sets is not very intuitive (at least it is not the case in standard OLO). O(1) regret may be achievable for general convex sets, however this might require totally novel techniques. Using Algorithm 4 in Algorithm 3 is a very reasonable idea that we have in fact tried. Unfortunately the analysis of Alg. 3 does not carry over once Alg 4 replaces Alg. 2. The reason is that the outputs of Alg 2 are always in distance $\\gamma$ at each step which is not the case for Alg 4.\n"}]

Author rebuttal:

Meta-review: This paper proposes a very interesting input model. While the model is not well-motivated in the traditional online learning sense, it is nicely motivated by the practical success of alternation in solving large-scale games and other saddle-point problems. I was somewhat surprised that a result like this holds, actually, since the related work on alternation with mirror descent using a Legendre regularizer explicitly uses the primal-dual dynamics, whereas the present paper gives a worst-case input guarantee under a model that seems to capture inputs generated by alternating no-regret algorithms.
Decision: Accept (spotlight)