$\overline{\varphi}\in\mathcal{M}$. This limit point must have the property
that $u_{L}(\overline{\varphi})\geq v+{\varepsilon}$. But since
$\overline{\varphi}$ is also the limit of extreme points of $\mathcal{M}$ in
directions converging to $u_{O}$, it must be an extreme point of $u_{O}$. But
this contradicts the fact that $V_{L}(\mathcal{M},u_{O})=v$ (since
$V_{L}(\mathcal{M},u_{O})$ is the maximum of $u_{L}(\varphi)$ over all
maximizers $\varphi$ of $u_{O}$, of which $\overline{\varphi}$ is one). The
conclusion follows. ∎

In the second lemma, we show that we can find an open set of optimizer payoffs
$u$ where $V_{L}(\mathcal{M},u)$ is never too much larger than
$V_{L}(\mathcal{M},u_{O})$. Note that since we define
$V_{L}(\mathcal{M},u_{O})$ to be the _largest_ value of $u_{L}(\varphi)$ over
all $\varphi\in\mathcal{M}$ maximizing $u_{O}(\varphi)$, this is not quite
symmetric with Lemma C.4. In fact, we will prove a weaker condition (instead
of an open neighborhood of $u_{O}$, a sufficiently nearby open set of
payoffs), and it is here that we will use Lemmas C.1 and C.3.

######  Lemma C.5.

Let $\mathcal{M}$ be an asymptotic menu and $u_{O}$ an optimizer payoff where
$V_{L}(\mathcal{M},u_{O})=v$. Then, for any ${\varepsilon}>0$, there exists an
open set of optimizer payoffs $U$ such that
$V_{L}(\mathcal{M},u^{\prime}_{O})\geq v-{\varepsilon}$ for any $u^{\prime}\in
U$, and such that there exists a $u^{\prime}\in U$ with
$|u^{\prime}-u_{O}|<{\varepsilon}$.

###### Proof.

Since $V_{L}(\mathcal{M},u_{O})=v$, there must be a $\varphi\in\mathcal{M}$
which is an extreme point in the direction $u_{O}$, and for which
$u_{L}(\varphi)=v$. By Lemma C.1, this means there exists a payoff
$u^{\prime}_{O}$ for which $|u^{\prime}_{O}-u_{O}|\leq{\varepsilon}$ and for
which $\varphi$ is the unique optimizer of $u^{\prime}_{O}$. Then, by Lemma
C.3, there exists an open neighborhood $U$ of $u^{\prime}_{O}$ such that for
any payoff $u\in U$, the optimizer in $\mathcal{M}$ of $u$ has distance at
most ${\varepsilon}$ from $\varphi$ (we pick $X$ to be the open ball of radius
${\varepsilon}$ around $\varphi$ in this application of Lemma C.3). This set
$U$ has our desired properties. ∎

With Lemmas C.4 and C.5, we can now prove the main result of this section.

######  Theorem C.6.

Let $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ be two menus such that there
exists a $u_{O}$ where
$V_{L}(\mathcal{M}_{1},u_{O})>V_{L}(\mathcal{M}_{2},u_{O})$. Then there exists
a positive measure set $U$ of optimizer payoffs where
$V_{L}(\mathcal{M}_{1},u)>V_{L}(\mathcal{M}_{2},u)$ for any $u\in U$.

###### Proof.

Pick an
${\varepsilon}<(V_{L}(\mathcal{M}_{1},u_{O})-V_{L}(\mathcal{M}_{2},u_{O}))/10$.
By Lemma C.4, there exists an open neighborhood $U_{2}$ of optimizer payoffs
around $u_{O}$ such that $V_{L}(\mathcal{M}_{2},u)\leq
V_{L}(\mathcal{M}_{2},u_{O})+{\varepsilon}$ for all $u\in U_{2}$. This open
set $U_{2}$ must contain a ball of some radius $r$; set
${\varepsilon}^{\prime}=\min(r,{\varepsilon})$.

Then, by Lemma C.5, there exists an open set $U_{1}$ of optimizer payoffs such
that $V_{L}(\mathcal{M}_{1},u)\geq
V_{L}(\mathcal{M}_{1},u_{O})-{\varepsilon}^{\prime}$ for all $u\in U_{1}$ and
such that there exists a $u\in U_{1}$ such that
$|u-u_{0}|<{\varepsilon}^{\prime}$.

This means that the sets $U_{1}$ and $U_{2}$ have non-empty intersection. Let
$U=U_{1}\cap U_{2}$; since $U$ is a non-empty open set, it has positive
measure. But now note that for any $u\in U$, $V_{L}(\mathcal{M}_{1},u)\geq
V_{L}(\mathcal{M}_{1},u_{O})-{\varepsilon}^{\prime}>V_{L}(\mathcal{M}_{2},u_{O})+{\varepsilon}\geq
v_{L}(\mathcal{M}_{2},u)$, as desired. ∎

##  Appendix D Inconsistent learning algorithms

In the majority of this paper, we restrict our attentions to consistent
learning algorithms – learning algorithms $\mathcal{A}$ with a unique
asymptotic menu $\mathcal{M}(\mathcal{A})$ such that if you play against
$\mathcal{A}$ for a sufficiently large time horizon, you can implement any CSP
$\varphi\in\mathcal{M}(\mathcal{A})$ arbitrarily closely.

Not all learning algorithms are consistent. A simple example is an algorithm
$\mathcal{A}$ that always plays action $1$ on odd rounds and always plays
action $2$ on even rounds. Nonetheless, it is still possible to extend much of
our analysis to the setting of inconsistent learning algorithms. The main
caveat is that instead of each learning algorithm being associated with a
single asymptotic menu, it will be associated with a collection of asymptotic
menus, each corresponding to a limit point of the sequence of menus for each
time horizon $T$.

######  Theorem D.1.

For any (not necessarily consistent) learning algorithm $\mathcal{A}$, the
sequence $\mathcal{M}(A^{1}),\mathcal{M}(A^{2}),\dots$ has at least one limit
point under the Hausdorff metric. Moreover, all such limit points are valid
asymptotic menus.

###### Proof.

Since the space of convex subsets of a bounded set is sequentially compact
under the Hausdorff metric (see [22]), it follows that the sequence
$\mathcal{M}(A^{1}),\mathcal{M}(A^{2}),\dots$ has at least one limit point.

To prove the second part: consider a limit point $\mathcal{M}$ of the above
sequence. This means that there is a subsequence
$\mathcal{M}(A^{T_{1}}),\mathcal{M}(A^{T_{2}}),\dots$ of the above sequence
that converges to $\mathcal{M}$ under the Hausdorff metric. We will construct
a learning algorithm $\mathcal{A}^{*}$ whose asymptotic menu is $\mathcal{M}$.

The algorithm $\mathcal{A}^{*}$ will work as follows. To run $\mathcal{A}^{*}$
for a time horizon of length $T$, choose the largest $i$ such that $T_{i}\leq
T$. Run $A^{T_{i}}$ for the first $T_{i}$ rounds of the game. Then recursively
run $\mathcal{A}^{*}$ for the remaining $T-T_{i}$ rounds (i.e., finding the
next largest $i^{\prime}$ s.t. $T_{i^{\prime}}\leq T-T_{i}$, and so on).

We will now prove that sequence of menus corresponding to $\mathcal{A}^{*}$
converges to $\mathcal{M}$ under the Hausdorff metric. Fix an
${\varepsilon}>0$. Since the subsequence $M(A^{T_{i}})$ converges to
$\mathcal{M}$, there must be a threshold $n_{\varepsilon}$ such that for any
$n\geq n_{{\varepsilon}}$, the Hausdorff distance
$d_{H}(\mathcal{M}(A^{T_{n}}),\mathcal{M})<{\varepsilon}/100$. On the other
hand, in any execution of $A^{*}$, at most $T_{n+1}$ rounds are spent playing
one of the first $n$ sub-algorithms $A^{T_{1}},A^{T_{2}},\dots,A^{T_{n}}$.
Therefore, if we pick $T\geq 100T_{n_{{\varepsilon}}}/{\varepsilon}$, we can
write any CSP $\varphi$ reached when playing against $(A^{*})^{T}$ in the
form:

$\varphi=\frac{{\varepsilon}}{100}\varphi_{\mathrm{pre}}+\left(1-\frac{{\varepsilon}}{100}\right)\varphi_{\mathrm{post}},$

where $\varphi_{\mathrm{pre}}$ is the CSP induced by the first
${\varepsilon}/100$ fraction of rounds, and $\varphi_{\mathrm{post}}$ is the
CSP induced by the remainder of the rounds. Since $\varphi_{\mathrm{post}}$ is
a convex combination of CSPs belonging to the sets $\mathcal{M}(A^{T_{n}})$
for $n\geq n_{{\varepsilon}}$, we must have
$d(\varphi_{\mathrm{post}},\mathcal{M})\leq{\varepsilon}/100$. Since the
maximum norm of an element in $\Delta_{mn}$ is bounded by $1$, this implies
(via the triangle inequality) that
$d(\varphi,\mathcal{M})<\frac{{\varepsilon}}{100}+\frac{{\varepsilon}}{100}<{\varepsilon}$.
It follows that every point in $\mathcal{M}((A^{*})^{T})$ is within
${\varepsilon}$ of an element of $\mathcal{M}$. But also, for any target
$\varphi^{*}\in\mathcal{M}$, we can pick $\varphi_{\mathrm{post}}$ to be the
convex combination of the closest element to $\varphi^{*}$ in each of the
relevant menus $\mathcal{M}(A^{T_{n}})$ – this also guarantees
$d(\varphi_{\mathrm{post}},\varphi^{*})\leq{\varepsilon}/100$ and thus that
$d(\varphi,\varphi^{*})<{\varepsilon}$ and so every point in $\mathcal{M}$ is
within ${\varepsilon}$ of an element of $\mathcal{M}((A^{*})^{T})$. It follows
that $\mathcal{M}(A^{*})=\mathcal{M}$. ∎

The fact that no-regret and no-swap-regret algorithms induce no-regret and no-
swap-regret menus (Theorem 3.6) extends easily to the case of inconsistent
algorithms.

######  Lemma D.2.

If a $\mathcal{M}$ is an asymptotic menu of the (inconsistent) no-regret
learning algorithm $\mathcal{A}$, then
$\mathcal{M}(\mathcal{A})\subseteq\mathcal{M}_{NR}$. If a $\mathcal{M}$ is an
asymptotic menu of the (inconsistent) no-swap-regret learning algorithm
$\mathcal{A}$, then $\mathcal{M}(\mathcal{A})\subseteq\mathcal{M}_{NSR}$.

###### Proof.

Follows identically to the proof of Theorem 3.6, but applied to the
subsequence of menus converging to $\mathcal{M}$. ∎

As a result of Theorem D.1 and Lemma D.2, we immediately obtain a stronger
version of Theorem 3.9: not only do all consistent no-swap-regret algorithms
share the same asymptotic menu, but in fact every no-swap-regret algorithm
shares the sasme asymptotic menu (and is in fact, consistent).

######  Corollary D.3.

Any no-swap-regret algorithm is consistent (and therefore by Theorem 3.9 has a
unique asymptotic menu of $\mathcal{M}_{NSR}$).

###### Proof.

Let $\mathcal{A}$ be a no-swap-regret algorithm. By Theorem D.1 and Lemma D.2,
any asymptotic menu $\mathcal{M}$ of $\mathcal{A}$ must be the asymptotic menu
of a consistent no-swap-regret algorithm. By Theorem 3.9, this implies
$\mathcal{M}=\mathcal{M}_{NSR}$. This means the sequence
$\mathcal{M}(A^{1}),\mathcal{M}(A^{2}),\dots$ has a unique limit point
$\mathcal{M}_{NSR}$ and therefore converges, so the original algorithm
$\mathcal{A}$ was consistent. ∎

It is an interesting question whether standard (mean-based) no-regret learning
algorithms such as multiplicative weights or FTRL are consistent learning
algorithms. Although intuitively it seems like this should be the case (due to
the simple form such algorithms take), it is surprisingly difficult to show
this formally. In particular, given a CSP $\varphi$ reached by e.g.
multiplicative weights for some large finite time horizon $T$, it is not
obvious how to reach a nearby CSP $\varphi^{\prime}$ for larger time horizons
$T^{\prime}$ (it is not sufficient to just “scale up” the sequence of
adversary actions). We leave this as an interesting open question.
Nonetheless, the results of this section imply that we can still say
meaningful things about asymptotic menus of such algorithms (and we prove in
Section 5.3 that these algorithms are in fact consistent for some payoffs
$u_{L}$).

##  Appendix E Additional Results and Proofs from Section 5

This appendix section continues the discussion in Section 5, discusses
additional results about $\mathcal{M}_{\mathrm{MB}}$, extends the set of
learner payoffs (1) for which we prove the Pareto-domination of FTRL
algorithms and presents the complete proof of Theorem 5.13.

###  E.1 Additional Results about $\mathcal{M}_{\mathrm{MB}}$

Lemma 5.2 showed that $\mathcal{M}_{\mathrm{MB}}$ is contained within the menu
of every mean-based algorithm. Since mean-based no-regret algorithms are known
to exist; we immediately obtain the following corollary (additionally using
Theorem 3.6, which tells us that the asymptotic menu of every no-regret
algorithm is contained within $\mathcal{M}_{NR}$).

######  Corollary E.1.

$\mathcal{M}_{\mathrm{MB}}\subseteq\mathcal{M}_{NR}$.

One way to interpret this is that in the CSP
$\operatorname{\mathsf{Prof}}(\tau)$ associated with any valid trajectory
$\tau$, the learner can never benefit by unilaterally deviating: they always
do at least as well as playing a best response to the optimizer’s marginal
distribution. Interestingly, we can show that mean-based algorithms also have
the property that they can never do much better than this – no profile can end
up with negative regret. This property is useful in generalizing a result in
Section 5.

######  Lemma E.2.

For any valid trajectory $\tau$, the value of the learner in the CSP
$\operatorname{\mathsf{Prof}}(\tau)$ exactly equals the value obtained by
best-responding to the optimizer’s marginal distribution.

This result implies that all extreme points of $\mathcal{M}_{\mathrm{MB}}$
have exactly zero regret, however, interior points might still have negative
regret, since a regret lower bound is not preserved by convex combinations of
CSPs.

###### Proof.

Consider any continuous time-formulation trajectory
$\tau=\\{(x_{1},t_{1},b_{1}),(x_{2},t_{2},b_{2}),\dots,(x_{k},t_{k},b_{k})\\}$;
let $\alpha_{O}$ be the marginal distribution of the optimizer in the CSP
$\operatorname{\mathsf{Prof}}(\tau)$. We show that
$\mu_{L}(\operatorname{\mathsf{Prof}}(\tau))=\max_{a\in[n]}\mu_{L}(\alpha_{O}\otimes
a)$. The proof proceeds via induction on $k$, the length of the transcript.
Let $\tau_{i}$ represent the prefix of the first $i$-triples of $\tau$ (this
is also a valid trajectory). Recall that
$\overline{x}_{i}=\sum_{j=1}^{i}(x_{j}t_{j})/\sum_{j=1}^{i}t_{j}$ (with
$\overline{x}_{0}=0$) is the time-weighted average strategy of the optimizer
over the first $i$ triples. The base case is $k=1$, for which the induction
hypothesis is satisfied, since the validity condition guarantees that
$b_{1}\in BR_{L}(x_{1})$. Assuming the induction hypothesis for $i$, that is
equivalent to stating that
$\mu_{L}(\tau_{i})=\max_{a\in[n]}\mu_{L}(a\otimes\overline{x}_{i})$.

However, the validity condition guarantees that
$b_{i+1}\in\operatorname*{arg\,max}_{a\in[n]}\mu_{L}(a\otimes\overline{x}_{i})$
implying that $\mu_{L}(\tau_{i})=\mu_{L}(b_{i+1}\otimes\overline{x}_{i})$.
However, the CSP $\tau_{i+1}$ is generated from $\tau_{i}$ by playing
$b_{i+1}$ against $x_{i+1}$ and reweighting accordingly, this leads to
$\mu_{L}(\tau_{i+1})=\mu_{L}(b_{i+1}\otimes\overline{x}_{i+1})$. The validity
condition also tells us that
$b_{i+1}\in\operatorname*{arg\,max}_{a\in[n]}\mu_{L}(a\otimes\overline{x}_{i+1})$,
which implies that
$\mu_{L}(\tau_{i+1})=\max_{a\in[n]}\mu_{L}(a\otimes\overline{x}_{i+1})$,
extending the induction hypothesis and completing the proof. ∎

###  E.2 Extending the Learner Payoffs

In Section 5, we showed a learner payoff (4) under which FTRL algorithms are
Pareto-dominated, through a sequence of results about the menus of such
algorithms showing that they fit our characterization of Pareto-dominated no-
regret algorithms. The same sequence of results can be shown to be true for a
positive measure set of learner payoffs obtained by perturbing (4).

The learner payoffs we consider are of the following form, where all
$\epsilon_{1}...\epsilon_{6}$ are between $0$ and
$\varepsilon<=\frac{1}{100}$, and $\epsilon_{1}>\epsilon_{2}$:

$\mu_{\mathcal{L}}=\begin{bmatrix}&\text{N}&\text{Y}\\\
\text{A}&\epsilon_{1}&\epsilon_{2}\\\
\text{B}&-1/6+\epsilon_{3}&1/3+\epsilon_{4}\\\
\text{C}&-1/2+\epsilon_{5}&1/2+\epsilon_{6}\\\ \end{bmatrix}$ (5)

######  Theorem E.3.

For any choice of $u_{L}$ in (5),
$\mathcal{M}_{\mathrm{MB}}^{-}\not\subseteq\mathcal{M}_{NSR}^{-}$.

The proof of this result is along the same lines as that of Theorem 5.3, with
some additional accounting to adjust for the perturbation, and can be found in
Appendix E.3.

######  Theorem E.4.

The mean-based menu $\mathcal{M}_{\mathrm{MB}}$ of any learner payoff of the
form (5) is a polytope.

The proof of Theorem 5.11 works as is for (5).

######  Theorem E.5.

For any $u_{L}$ defined in (5), if $\mathcal{A}$ is a FTRL algorithm, then
$\mathcal{M}(\mathcal{A})=\mathcal{M}_{\mathrm{MB}}$.

The proof of this result is exactly the same as that of Theorem 5.13, for
which we provided a proof sketch in Section 5. A full version of this proof is
given below in Appendix E.4.

######  Corollary E.6.

For every $u_{L}$ defined in (5), all FTRL algorithms are Pareto-dominated.

The proof of this corollary is exactly the same as that of Corollary 5.14,
with the referenced results in Section 5 swapped out for the corresponding
ones in this Appendix E.

###  E.3 Proof of Theorem E.3

Fix any fixed learner payoff $u_{L}\in\eqref{eq:perturbed_game}$. We prove
this result by showing a point in $\mathcal{M}_{\mathrm{MB}}$ for which the
learner obtains their maximin value and has positive swap regret (and is hence
not in $\mathcal{M}_{NSR}$). More atomically, we come up with a valid
trajectory $\tau$ in the continuous formulation mentioned in Section 5. Based
on Lemma E.2, we know that for $u_{L}(\operatorname{\mathsf{Prof}}(\tau))$ to
be the maximin value of the learner, the optimizer’s marginal distribution in
$\operatorname{\mathsf{Prof}}(\tau)$ must be equal to the minimax distribution
– this informs our construction of $\tau$. The first step in our proof is
therefore (approximately) identifying the minimax distribution for the learner
payoff.

######  Claim E.7.

There is a unique, minimax strategy $M$ against the learner payoff $u_{L}$
where $M$ picks action $X$ with probability $p^{*}=2/3\pm O(\varepsilon)$.

###### Proof.

First, we claim that the minmax strategy must cause the learner to be
indifferent between at least two of their actions. To see this, assume for
contradiction the following cases:

  * •

The minimax strategy $s$ strictly incentivizes $A$ over $B$ and $C$ by
$\delta$. Then the optimizer can define a new strategy
$(1-\frac{\delta^{\prime}}{2})s+\frac{\delta^{\prime}}{2}Y$ for any
$\delta^{\prime}\leq\delta$, which still incentivizes $A$ but gives the
learner strictly lower payoff. The only way this would not decrease payoff is
if the strategy was already the pure strategy $Y$, but this cannot incentivize
$A$. So this derives a contradiction.

  * •

The minimax strategy $s$ strictly incentivizes $B$ over $A$ and $C$ by
$\delta$. Then the optimizer can define a new strategy
$(1-\frac{\delta^{\prime}}{2})s+\frac{\delta^{\prime}}{2}N$ for any
$\delta^{\prime}\leq\delta$, which still incentivizes $B$ but gives the
learner strictly lower payoff. The only way this would not decrease payoff is
if the strategy was already the pure strategy $N$, but this cannot incentivize
$B$. So this derives a contradiction.

  * •

The minimax strategy $s$ strictly incentivizes $C$ over $A$ and $B$ by
$\delta$. Then the optimizer can define a new strategy
$(1-\frac{\delta^{\prime}}{2})s+\frac{\delta^{\prime}}{2}N$ for any
$\delta^{\prime}\leq\delta$, which still incentivizes $B$ but gives the
learner strictly lower payoff. The only way this would not decrease payoff is
if the strategy was already the pure strategy $N$, but this cannot incentivize
$C$. So this derives a contradiction.

Next, note that $A$ and $C$ are equal when $P(N)=p$ for some $p=\frac{1}{2}\pm
O(\epsilon)$. Furthermore, when $P(N)=\frac{1}{2}\pm O(\epsilon)$, $B$ is
better than both $A$ and $C$. So there cannot be a minimax strategy when $A$
and $C$ are tied best repsonses. Furthermore, note that $B$ and $C$ are equal
when $P(N)=q$ for some $q=\frac{1}{3}\pm O(\epsilon)$. Against this
distribution, the learner can play $C$ and get payoff
$\frac{1}{2}.\frac{2}{3}-\frac{1}{2}.\left(\frac{1}{3}\pm
O(\epsilon)\right)=\frac{1}{6}\pm O(\epsilon)$. This cannot be the minimax
strategy, as if the optimizer just plays $N$, the learner will get payoff at
most $\epsilon_{1}<\frac{1}{6}\pm O(\epsilon)$.

Therefore, the only remaining possibility is that the minimax distribution is
when $A$ and $B$ are equal. This is a unique distribution, and will be of the
form $P(N)=p^{*}$ for some $p^{*}=\frac{2}{3}\pm O(\epsilon)$

∎

Using a similar analysis, there is a unique distribution for the optimizer for
which the learner’s best response is tied between actions $B$ and $C$, this
distribution plays action $N$ with probability $q^{*}=\frac{1}{3}\pm
O(\varepsilon)$. Consider the continuous time trajectory $\tau=\\{(q^{*}\cdot
N+(1-q^{*})\cdot Y,t_{1},C),(N,t_{2},B)\\}$ where $t_{1}+t_{2}=1$,
$t_{1},t_{2}\geq 0$; and $t_{1}$ and $t_{2}$ are chosen so that
$t_{1}q+t_{2}=p^{*}$. A feasible solution exists with
$t_{1},t_{2}=\frac{1}{2}\pm O(\varepsilon)$ because $q$ is very close to
$1/2$, and $p^{*}$ is very close to $2/3$. By construction, this is indeed a
valid trajectory: we can check that $\overline{x}_{1}=q^{*}\cdot
N+(1-q^{*})\cdot Y$, $\overline{x}_{2}=p^{*}\cdot N+(1-p^{*})Y$,
$\operatorname{\mathsf{BR}}_{L}(q^{*}\cdot N+(1-q^{*})\cdot Y)=\\{B,C\\}$, and
that $\operatorname{\mathsf{BR}}_{L}(p^{*}\cdot N+(1-p^{*})Y)=\\{A,B\\}$. For
this trajectory, $\operatorname{\mathsf{Prof}}(\tau)=t_{1}q^{*}(N\otimes
C)+t_{1}(1-q^{*})(Y\otimes C)+t_{2}(N\otimes B)$. The swap regret of
$\operatorname{\mathsf{Prof}}(\tau)$ is positive, since by swapping all weight
on $B$ to $A$ increases the learner’s average utility by
$\frac{t_{2}}{6}\geq\frac{1}{24}$ (since $t_{2}\geq\frac{1}{4}$), so
$\operatorname{\mathsf{Prof}}(\tau)\not\in\mathcal{M}_{NSR}$. However, by
construction the marginal distribution of the optimizer in
$\operatorname{\mathsf{Prof}}(\tau)$ is exactly the minimax distribution of
the optimizer, implying that the learner gets the minimax value, completing
the proof.

###  E.4 Proof of Theorem 5.13/Theorem E.5

As a consequence of Lemma 5.12, the FTRL algorithm $\mathcal{A}$ is
$\gamma$-mean based with $\gamma(t)\cdot t$ being a sublinear and monotone
function of $t$. Let $\mathcal{M}_{MI}$ denote the intersection of the menu of
all mean-based algorithms. A restatement of Lemma 5.2 is that
$\mathcal{M}_{\mathrm{MB}}\subseteq\mathcal{M}_{MI}$. However, by definition –
$\mathcal{M}_{MI}\subseteq\mathcal{M}(\mathcal{A})$ implying that
$\mathcal{M}_{\mathrm{MB}}\subseteq\mathcal{M}(\mathcal{A})$. To complete the
proof of the lemma only, we only need to show that the menu
$\mathcal{M}=\mathcal{M}(\mathcal{A})$ of a given FTRL algorithm is contained
in $\mathcal{M}_{\mathrm{MB}}$.

To this end, we pick up each extreme point of $\mathcal{M}$ and show its
containment in $\mathcal{M}_{\mathrm{MB}}$. For each such CSP, we demonstrate
a sequence of points in $\mathcal{M}_{\mathrm{MB}}$ converging to this CSP;
which, when combined with the closed and bounded property of
$\mathcal{M}_{\mathrm{MB}}$ (a polytope, see Theorem 5.11), implies that the
limit point is in $\mathcal{M}_{\mathrm{MB}}$.

As our proof sketch indicated, this sequence of points is generated by
observing the finite time menus of the algorithm $\mathcal{A}$. For each point
$P$ in $\mathcal{M}$, there is a a sequence of CSPs $P_{1},P_{2},\dots$ in the
finite time menus that converge to $P$. Our proof shows a sequence of points
$Q_{1},Q_{2},\dots,Q_{T},\ldots\in\mathcal{M}_{\mathrm{MB}}$ satisfying the
property that $d(P_{T},Q_{T})=o(1)~{}$999Here, as everywhere else in this
section, $o(1)$ refers to a sub-constant dependence on $T$. Directly using the
triangle inequality then guarantees that the sequence $\\{Q_{T}\\}$ converges
to $P$.

For ease of writing, we introduce $f(T)=\max\\{\gamma(T)\cdot
T,\operatorname{\rho}(T),\operatorname{\zeta}(T)\\}$. $\rho(T)$ is the regret
bound guaranteed by Lemma 5.12; while $\operatorname{\zeta}(T)$ is the
sublinear function associated with $\mathcal{A}$ from the last clause of Lemma
5.12, and is roughly the upper bound in the difference in the strategy chosen
by the original algorithm and that chosen by the same algorithm restricted to
two actions when the third action is sufficiently far from being a historical
best action. This function $f$, being a max of sublinear functions, is itself
sublinear. There exists a positive constant $K$ such that the magnitude of the
regret of the algorithm is upper bounded by $Kf(T)$. For ease of writing, we
consider $K=1$, although our proof will work for any constant $K>0$. Even
though, Lemma 5.12 guarantees that the regret is contained in
$[0,\operatorname{\rho}(T)]$; we work with a weaker bound of regret being
contained in $[-\operatorname{\rho}(T),\operatorname{\rho}(T)]$

The rest of the proof focuses mostly on proving the existence of $Q_{T}$ given
$P_{T}$. Without loss of generality, we restrict our attention to the simpler
case where $P_{T}$ is an extreme point of the menu
$\mathcal{M}(\mathcal{A})_{T}$; and find a corresponding $Q_{T}$. The same
idea can be extended to arbitrary menu points by rewriting $P_{T}$ as a convex
combination of $mn+1$ extreme points (invoking Caratheodory’s theorem).

We introduce some notation to aid with our proofs, and formalize the notions
of boundaries and finite time trajectories. We track the (partial) state of
learning algorithms by measuring the cumulative payoffs of the three actions
$A,B,C$ after $t-1$ moves, denoted by
$\sigma^{A}_{t},\sigma^{B}_{t},\sigma^{C}_{t}$. Since FTRL algorithms only
care about the relative differences in the payoffs of the actions, we track
these differences $u_{t}:=\sigma^{A}_{t}-\sigma^{C}_{t}$ and
$v_{t}:=\sigma^{B}_{t}-\sigma^{C}_{t}$, and refer to
$(u_{t},v_{t})\in\mathbb{R}^{2}$ as the state of the learner. The move $x_{t}$
of the optimizer takes the learner’s state from $(u_{t},v_{t})$ to
$(u_{t+1},v_{t+1})$. Recall that a CSP is an extreme point in the menu of an
algorithm only if there exists an ordered sequence of optimizer moves combined
with the algorithm’s responses, that induces this point. $P_{T}$ can thus be
thought of as being generated by a sequence of optimizer actions
$x_{1},x_{2},\cdots,x_{T}$, in conjunction with the responses of the FTRL
algorithm $\mathcal{A}$.

This sequence of optimizer actions induces a corresponding sequence of learner
states $(u_{1},v_{1}),(u_{2},v_{2}),\dots,(u_{T},v_{T})$. We refer to the
curve generated by joining consecutive states with line segments as the
finite-time trajectory associated with the point $P_{T}$ (for convenience, we
will drop the “finite-time” identifier and simply call these trajectories,
until otherwise specified). The part of the trajectory associated with a
contiguous subsequence of time steps is referred to a sub-trajectory. It is
useful to keep in mind that the finite-time trajectory is entirely a function
of the optimizer’s actions and the learner’s payoff function, and that
different learner algorithms can potentially induce significantly different
CSPs for the same trajectory.

We divide our state space $\mathbb{R}^{2}$ into multiple zones, based on the
historical best response and its corresponding advantage in these zones. These
zones are demarcated by the following lines:

  * •

$H_{AB}$ is the set of all points $(u,v)$ where $u=v$ and $u,v\geq 0$.

  * •

$H_{BC}$ is the set of all points $(u,v)$ where $v=0$ and $u<0$.

  * •

$H_{AC}$ is the set of all points $(u,v)$ where $u=0$ and $v<0$.

  * •

$S_{AB}$ is the set of all points $(u,v)$ where $v-u=f(T)$ and $u,v\geq 0$.

  * •

$\overline{S}_{AB}$ is the set of all points $(u,v)$ where $u-v=f(T)$ and
$u,v\geq 0$.

  * •

$S_{BC}$ is the set of all points $(u,v)$ where $v=f(T)$ and $u<0$.

  * •

$\overline{S}_{BC}$ is the set of all points $(u,v)$ where $v=-f(T)$ and
$u<0$.

  * •

$S_{AC}$ is the set of all points $(u,v)$ where $u=f(T)$ and $v<0$.

  * •

$\overline{S}_{AC}$ is the set of all points $(u,v)$ where $u=-f(T)$ and
$v<0$.

We refer to $H_{AB},H_{BC},H_{AC}$ as the “hard” boundaries separating the
three actions, and refer to
$S_{AB},S_{BC},S_{AC},\overline{S}_{AB},\overline{S}_{BC},\overline{S}_{AC}$
as the “soft” boundaries. The separation of $f(T)$ between the corresponding
hard and soft boundaries is interpreted an upper bound on the regret of
algorithm $\mathcal{A}$ and the separation in cumulative payoff corresponding
to the mean-based condition of $\mathcal{A}$. While we have defined all
possible hard and soft boundaries, some of them are not explicitly used in our
subsequent analysis. This is due to an asymmetry in the learner payoffs that
prevents certain states from being reached, such as points on $H_{AC}$ that
are far from the origin 101010This asymmetry is exploited later to prove Lemma
E.12, a crucial result showing that the state of the algorithm is always
moving away from the origin.

The learner is said to have a “clear” historical best response action at the
start of a given round if the action with the largest cumulative payoff has an
advantage of at least $f(T)$ over the other actions. In other words, at state
$(u,v)$; $A$ is a clear historical best response when $u>f(T)$ and $u-v>f(T)$,
$B$ is a clear historical best response when $v>f(T)$ and $v-u>f(T)$ and $C$
is a clear historical best response when $u<-f(T)$ and $v<-f(T)$. The
significance of this definition can be seen by recalling that a $\gamma$-mean
based learner plays a clear historical best response at round $t$ with
probability at least $1-2\gamma(t)$ and plays the other actions with
probability at most $\gamma(t)$. In words, a clear historical best response at
round $t$ is practically guaranteed to be played by $\mathcal{A}$, with some
$o(1)$ probability mass for other actions.

Figure 5 shows a picture of the state space, with separations for the soft and
hard boundaries.

Figure 5: The state space with hard and soft boundaries, in black and purple
respectively.

Consider the original point $P$ that we begin with. For $t_{1}<t_{2}$, we call
the part of a trajectory from $(u_{t_{1}},v_{t_{1}})$ to
$(u_{t_{2}},v_{t_{2}})$ a segment. We break up its trajectory into the
following segments:

  * •

(I) An initial segment starting at $(0,0)$ and continuing until the first
point where either $S_{AB}$ or $S_{BC}$ is crossed.

  * •

(NC1) A maximal segment that starts within a move of crossing $S_{AB}$ and
returns to a point within a move of $S_{AB}$ without ever crossing $S_{BC}$.

  * •

(NC2) A maximal segment that starts within a move of crossing $S_{BC}$ and
returns to a point within a move of $S_{BC}$ without ever crossing $S_{AB}$.

  * •

(C1) A minimal segment that starts within a move of crossing $S_{AB}$ and
crosses $S_{BC}$ with its last line segment.

  * •

(C2) A segment that starts within a move of crossing $S_{BC}$ and crosses
$S_{AB}$ with its last line segment.

  * •

(F) The final segment is broken up into a maximal C1 or C2 segment followed by
a segment starting at one of the soft boundaries and staying in the zone with
a unique clear historical best response.

The different types of segments for a trajectory are depicted in Figure 6.

Figure 6: A trajectory is shown with different types of segments having
different colors. In order, it contains: an I segment (in green), a C2 segment
(in blue), an NC1 segment (in red), a C1 segment (in blue), and a final F
segment (in green).

The careful reader might ponder about the problem created by these segments
not ending exactly at the boundaries, but overshooting by one time step. This
is indeed connected to a deeper problem, connected to trajectories that
oscillate back and forth across these boundaries a significant number of
times. We address this issue in detail later by proving (using Lemma E.13)
that the number of segments is sublinear; and thus for sake of convenience, we
can assume these segments exactly end on the corresponding boundaries.

######  Observation E.8.

The trajectory of states cannot intersect with $H_{AC}$ after $t=0$.

###### Proof.

For this event to happen, the historical average optimizer action
(corresponding to the point of intersection, possibly for a fractional time
step) must induce a tie in best-responses between actions $A$ and $C$ \- no
such optimizer distribution exists for these learner payoffs, ruling out the
possibility. ∎

Armed with this observation, it is straightforward to see that this
decomposition of trajectories is uniquely defined and can be constructed
directly by splitting a trajectory into an initial segment (I) followed by
alternating non-crossing (NC) and crossing (C) segments and finishing with a
final (F) segment. Since the trajectory never crosses $H_{AC}$; the only way
crossing segments move across from $S_{AB}$ to $S_{BC}$ is by going through
the region where $B$ is a clear historical best response. The alternating
nature of non-crossing and crossing segments implies that the number of non-
crossing segments is at most the number of crossing segments plus 1.

The main constructive step involved in the proof is in showing how to
transform the trajectory corresponding to point $P_{T}$ into another
trajectory which spends only sublinear time within the soft boundaries and
induces, together with algorithm $\mathcal{A}$, a CSP $P^{\prime}_{T}$ that is
a sub-constant distance to $P_{T}$.

######  Lemma E.9.

Given any trajectory inducing a CSP $P_{T}$ when played against $\mathcal{A}$
with time horizon $T$, there exists a trajectory that spends all but $o(T)$
time outside the soft boundary and induces a CSP $P^{\prime}_{T}$ such that
$d(P_{T},P^{\prime}_{T})=o(1)$ .

The proof is presented later in this section. Armed with such a trajectory, we
then show how to construct a point $Q_{T}\in\mathcal{M}_{\mathrm{MB}}$ that is
$o(1)$ close to $P^{\prime}_{T}$, and hence close to $P_{T}$. Based on the
finite-time trajectory inducing $P^{\prime}_{T}$, we can construct a valid
trajectory $\tau_{T}$ in the continuous-time formulation referred to in
Section 5. We do this by taking the trajectory inducing $P^{\prime}_{T}$,
breaking it up whenever it crosses a hard boundary separating two learner
actions, and replacing each segment by the time average action repeated for
the length of the trajectory. We also attach the corresponding learner best
response action to each segment of this trajectory to complete the triple.
Since $P^{\prime}_{T}$ spends only sublinear time within the soft boundaries,
it is easy to see that the CSP $Q_{T}:=\operatorname{\mathsf{Prof}}(\tau_{T})$
is sublinearly close to $P^{\prime}_{T}$ and hence to $P_{T}$. Thus, we have a
sequence of valid trajectories $\\{\tau_{T}\\}$ whose images under the
continuous function $\operatorname{\mathsf{Prof}}$ are converging to $P$.
Since $\mathcal{M}_{\mathrm{MB}}$ is a closed and bounded set (by virtue of
being a polytope, see Theorem 5.11), the point $P$ is contained in
$\mathcal{M}_{\mathrm{MB}}$, completing the proof.

####  E.4.1 Proof of Lemma E.9

We outline this transformation of the trajectory below, through a sequence of
lemmas that prove some critical properties about this class of games and give
procedures to transform the different types of segments in the target
trajectory.

Based on the learner utilities, we observe that any single move of the
optimizer shifts the state of the learner by some constant distance (in say,
the $\ell_{1}$ norm).

######  Observation E.10.

Starting at state $(u,v)$ and playing optimizer distribution $\alpha(N)$ for
one step changes the state to $(u+\xi_{1},v+\xi_{2})$ with

  * •

$\xi_{1}=1/2\pm 2\varepsilon$ and $\xi_{2}=1/3\pm 2\varepsilon$ when
$\alpha(N)=1$.

  * •

$\xi_{1}=-1/2\pm 2\varepsilon$ and $\xi_{2}=-1/6\pm 2\varepsilon$ when
$\alpha(N)=0$ .

where $\xi=a\pm b$ is equivalent to stating $\xi\in[a-b,a+b]$.

Next, we observe that the optimizer’s action space in the stage game can be
partitioned into contiguous intervals corresponding to which action of the
learner is a best response to it. We note that the breakpoints are close to
$1/3$ and $2/3$, where the optimizer action is parametrized by the probability
with which action $N$ is played.

######  Observation E.11.

For an optimizer distribution $\alpha(N)$; there are numbers $q=1/3\pm
O(\varepsilon)$ and $p=2/3\pm O(\varepsilon)$ such that :

  * •

If $\alpha(N)\in[0,p)$, $C$ is a unique best response.

  * •

If $\alpha(N)\in(p,q)$, $B$ is a unique best response.

  * •

If $\alpha(N)\in(q,1]$, $A$ is a unique best response.

These observations lead to an important result – that the state of the
algorithm drifts away from the origin, in the $\ell_{1}$ distance, by
$\theta(t)$ after $t$ time steps.

######  Lemma E.12.

There exists constants $C_{1},C_{2}>0$ such that every sub-trajectory of
length $L$ corresponds to somewhere between $C_{1}\cdot L$ and $C_{2}\cdot L$
moves, and a constant $B>0$ such that after $t$ time steps, the trajectory is
at least $B\cdot t$-far from the origin in the $\ell_{1}$ distance.

###### Proof.

Each time step moves the state only by a constant amount in the $\ell_{1}$
metric (follows directly from Observation E.10). Thus, a segment of some
length $L$ must correspond to a contiguous subsequence of at least $C_{1}\cdot
L$ time steps for some constant $C_{1}>0$. Showing the second half of the
lemma statement will imply a similar upper bound on the number of time steps.
To do so, we look at the offsets to the state generated by the two actions $N$
and $Y$, which are $V_{1}=(1/2\pm 2\varepsilon,1/3\pm 2\varepsilon)$ and
$V_{2}=(-1/2\pm 2\varepsilon,-1/6\pm 2\varepsilon)$. The average offset caused
by the action of the optimizer over any number of time steps must therefore be
some convex combination of $V_{1}$ and $V_{2}$ (we use linearity to rewrite
the average offset of the actions as the offset generated by the historical
average optimizer action). Ignoring the $\varepsilon$ terms for the moment,
the line between the points $V_{1}$ and $V_{2}$ is $y=x/2-1/12$. The
$\ell_{2}$ distance from the origin $(0,0)$ to this line is
$\frac{1}{6\sqrt{5}}$, implying that every point on the line is at least
$\frac{1}{6\sqrt{10}}$ far from the origin. With the $\varepsilon$ terms
included, it is easy to see that this statement is still true for the distance
$\frac{1}{6\sqrt{10}}\pm O(\varepsilon)$. Thus, after $T$ time steps, the
state has $\ell_{1}$ distance at least $\frac{T}{24}$ from the origin,
completing the proof. ∎

The above lemma implies a bound on the number of non-crossing segments in any
trajectory.

######  Lemma E.13.

The number of different segments between rounds $t=\phi$ and $t=T$ is at most
$O\left(\frac{T}{\phi}\right)$.

###### Proof.

An upper bound the number of crossing segments after $\phi$ time steps implies
the same asymptotic upper bound for the number of non-crossing segments. We
assume, without loss of generality, that $\phi>f(T)$ since the first crossing
segment can only appear after $\Omega(f(T))$ time steps (which is the minimum
length of the initial segment). Using Lemma E.12, we see that any crossing
segment is the largest side of an obtuse angled triangle whose two smallest
sides have length $\Omega(\phi)$. Thus, each non-crossing segment has length
$\Omega(\phi)$, and must consequently correspond to $\Omega(\phi)$ time steps
(since each time step’s line segment has constant length). This directly
implies the desired result. ∎

The critical part of our proof is a method to transform non-crossing segments
into a segment with identical start and end points, but one that only spends
$O(f(T))$ (i.e sublinear) number of time steps within the soft boundaries; and
induces almost the same CSP. For a clean exposition that accounts for
different non-crossing segments having different length, we unnormalize the
CSP stick to this convention for the proof. By this, we mean that the CSP is
redefined to be $\sum_{t=1}^{T}x_{t}\otimes y_{t}$ rather than
$\frac{1}{T}\sum_{t=1}^{T}x_{t}\otimes y_{t}$. A visual version of this
transformation is shown in Figure 7.

Figure 7: The NC segment (in red) is replaced by a segment (in green) that
spends minimal time inside the soft boundary.

######  Lemma E.14.

Every non-crossing segment can be replaced with a segment beginning and ending
in the same place, running for the same number of time steps and spending
$O(f(T))$ time within the soft boundaries, with the property that the
resulting trajectory induces a CSP which differs by $O(f(T))$ from the
starting CSP.

###### Proof.

We will prove this for the soft boundary $S_{AB}$. A similar proof works for
$S_{BC}$.

Let $s=x_{t_{1}:t_{2}}$ be the segment of play by the optimizer starting at
$S_{AB}$ and ending somewhere within the soft boundary of $BC$. It has a
resulting CSP of $c$ (the average joint distribution over action pairs
measured over this sequence).

Instead of analyzing algorithm $\mathcal{A}$’s induced CSP $c$ on the segment
$s$; we analyze the (unnormalized) CSP $c^{\prime}$ generated by the action of
$\mathcal{A}_{2}$, a learning algorithm which is equivalent to $\mathcal{A}$
except that it only considers actions $A$ and $B$, on the same segment.The
last clause of Lemma 5.12 shows that the algorithms $\mathcal{A}$ and
$\mathcal{A}_{2}$ pick almost identical distributions in each round (separated
by at most $\frac{\operatorname{\zeta}(T)}{T}$) – thus the CSPs $c$ and
$c^{\prime}$ are sublinearly close, i.e., $||c-c^{\prime}||_{1}=O(f(T))$.
Further, this alternative algorithm is also an instance of FTRL, guaranteeing
the same properties, at least with respect to the actions $A$ and $B$.

Now, we will describe a new trajectory that approximates $c^{\prime}$. Recall
that $x_{t}$ is the distribution played by the optimizer at round $t$. Let
$(\alpha_{A}^{t},\alpha_{B}^{t})$ be the distribution played by the learning
algorithm $\mathcal{A}_{2}$ at round $t$. Define
$D_{A}:=\frac{1}{\alpha_{A}}\sum_{t=t_{1}}^{t_{2}}\alpha_{A}^{t}x_{t}$ and
$D_{B}:=\frac{1}{\alpha_{B}}\sum_{t=t_{1}}^{t_{2}}\alpha_{B}^{t}x_{t}$ where
$\alpha_{A}:=\sum_{t=t_{1}}^{t_{2}}\alpha_{A}^{t}$ and
$\alpha_{B}:=\sum_{t=t_{1}}^{t_{2}}\alpha_{B}^{t}$. In other words, $D_{A}$
and $D_{B}$ are the average distributions of the optimizer conditioned upon
the learner playing $A$ and $B$ respectively, while $\alpha_{A}$ and
$\alpha_{B}$ are the sum of the probabilities (over all the rounds in this
segment) with which the optimizer plays $A$ and $B$ respectively.

Since the segment $s$ starts and ends at the soft boundary $S_{AB}$, we know
that $A$ and $B$ are both within a cumulative value of $O(f(T))$ to a best
response to the distribution
$d^{\prime}=\frac{\alpha_{A}D_{A}+\alpha_{B}D_{B}}{\alpha_{A}+\alpha_{B}}$,
i.e the average distribution of the optimizer over the segment of interest,
played $\alpha_{A}+\alpha_{B}$ times.

We argue that algorithm $\mathcal{A}_{2}$ has an upper bound of $O(f(T))$ on
the magnitude of regret in this segment. To see this, we imagine a prefix to
this segment that starts at the hard boundary $H_{AB}$ and moves to the soft
boundary $S_{AB}$ by playing $K^{\prime}f(T)$ steps of $Y$ for some constant
$K^{\prime}$ 111111We employ this argument since regret upper lower bounds are
typically only guarantees for sequences starting at time $t=0$.. Now, since
this extended sequence begins at the hard boundary, it is as if we started
running $\mathcal{A}_{2}$ at $t=0$ at the start of this sequence (by adding a
constant offset to the cumulative payoffs of $A$ and $B$, a legal action, by
Lemma 5.12). Thus, we get the regret guaranteed to be in the interval
$[-O(f(T)),O(f(T))]$ for the extended sequence (from the properties of FTRL
algorithms ), and observe that the regret for the “true” segment is therefore
guaranteed to be in $[-Hf(T),Hf(T)]$ for some constant $H>0$.

First, we observe that the no-regret property with two actions implies no-swap
regret. Quantitatively, we have:

$\alpha_{B}(\mu_{\mathcal{L}}(D_{B},A)-\mu_{\mathcal{L}}(D_{B},B))\leq
Hf(T)\qquad\text{(based on regret bounds against $A$)}$
$\alpha_{A}(\mu_{\mathcal{L}}(D_{B},B)-\mu_{\mathcal{L}}(D_{B},A))\leq-
Hf(T)\qquad\text{(based on regret bounds against $B$)}$

We show the stronger property that $A$ and $B$ are both close to a best
response to both $D_{A}$ and $D_{B}$ (the observation above only shows that
$A$ is a near best response to $D_{A}$ and $B$ is a near best response to
$D_{B}$). Assume for contradiction that
$\alpha_{A}(\mu_{\mathcal{L}}(D_{B},A)-\mu_{\mathcal{L}}(D_{B},B))>2Hf(T)$.

$\displaystyle\mu_{\mathcal{L}}(c^{\prime})$
$\displaystyle=\alpha_{A}\mu_{\mathcal{L}}(D_{A},A)+\alpha_{B}\mu_{\mathcal{L}}(D_{B},B)$
$\displaystyle>\alpha_{A}\mu_{\mathcal{L}}(D_{A},B)+\alpha_{B}\mu_{\mathcal{L}}(D_{B},B)+2Hf(T)\qquad\text{(by
assumption)}$
$\displaystyle=(\alpha_{A}+\alpha_{B})\mu_{\mathcal{L}}(d^{\prime},B)+2Hf(T)\qquad\text{(using
linearity of the payoffs)}$
$\displaystyle\geq\max_{S\in\\{A,B\\}}(\alpha_{A}+\alpha_{B})\mu_{\mathcal{L}}(d^{\prime},s)-Hf(T)+2Hf(T)\text{(by
the fact that $B$ is close to a best response to $d^{\prime}$)}$

This is a contradiction for sufficiently large $T$, as $\mathcal{A}_{2}$ has
an average regret lower bound of $-Hf(T)$. A similar argument can be made with
$A$ and $B$ exchanged. Thus, we have :

$\alpha_{A}(\mu_{\mathcal{L}}(D_{B},A)-\mu_{\mathcal{L}}(D_{B},B))\leq 2Hf(T)$
$\alpha_{B}(\mu_{\mathcal{L}}(D_{A},B)-\mu_{\mathcal{L}}(D_{A},A))\leq 2Hf(T)$

These inequalities are key to constructing our transformation. We split our
analysis into four cases, depending on whether or not actions $A$ and $B$ are
both played for a significant amount of time in this segment.

We start by assuming that $\alpha_{A}\geq 8K_{1}f(T)$, $\alpha_{B}\geq
8K_{2}f(T)$ for some positive constants $K_{1}$ and $K_{2}$ which will be
defined shortly. This is the most important case in the analysis, and the
other cases (where this assumption is not true) simply follow by exploiting
sublinear differences in the construction.

The new sequence is as follows: from the hard boundary, play $N$ until
$u_{t}-v_{t}=3Hf(T)$. By Observation E.11, this will take $Kf(T)$ rounds for
some constant $K>0$. Then, play $D_{A}$ for $\alpha_{A}-8Kf(T)$ rounds. Then,
play $Y$ until $u_{t}-v_{t}=-3Hf(T)$. We claim that takes only $K_{2}f(T)$
rounds for some constant $K_{2}>0$ \- this is so because the cumulative effect
of playing $D_{A}$ for $\alpha_{A}$ rounds causes a difference of at most
$2Hf(T)$ in the payoffs of actions $A$ and $B$ over these rounds. Therefore,
at the time step $t$ at the end of playing $D_{A}$, $u_{t}-v_{t}\leq 5Hf(T)$.
Then, play $D_{B}$ for $\alpha_{B}-8K_{2}f(T)$ rounds.

Let $D_{A}(Y)$ be the fraction of the time that $Y$ is played in $D_{A}$, and
define $D_{A}(N)$, $D_{B}(Y)$, and $D_{B}(N)$ accordingly. Then, let us
consider the number obtained by adding up the probability of playing $N$ in
all the rounds described so far. This number $n_{N}$ is upper bounded by
$D_{A}(N)(\alpha_{A}-8Kf(T))+D_{B}(N)(\alpha_{B}-8K_{2}f(T))+Kf(T)$. Likewise,
the number of times $n_{Y}$ we have played $y$ so far is upper bounded by
$D_{A}(Y)(\alpha_{A}-8Kf(T))+D_{B}(Y)(\alpha_{B}-8K_{2}f(T))+K_{2}f(T)$.

To finish our sequence, we will play $N$ for
$n^{\prime}_{N}:=d^{\prime}(N)(\alpha_{A}+\alpha_{B})-n_{N}$ times, which is
lower bounded by
$d^{\prime}(N)(\alpha_{A}+\alpha_{B})-(D_{A}(N)(\alpha_{A}-8Kf(T))+D_{B}(N)(\alpha_{B}-8K_{2}f(T))+Kf(T))$
and then play $Y$ for
$n^{\prime}_{Y}:=d^{\prime}(Y)(\alpha_{A}+\alpha_{B})-n_{Y}$ rounds, which is
lower bounded by
$d^{\prime}(Y)(\alpha_{A}+\alpha_{B})-(D_{A}(Y)(\alpha_{A}-8Kf(T))+D_{B}(Y)(\alpha_{B}-8K_{2}f(T))+K_{2}f(T))$
rounds. We show that this is a legal operation by proving that
$n^{\prime}_{N},n^{\prime}_{Y}\geq 0$. It suffices to show their lower bounds
are non-negative.

Note that by the fact that $A$ and $B$ are near best responses for both
$D_{A}$ and $D_{B}$ and using Observation E.11,
$D_{A}(N),D_{B}(N),D_{A}(Y),D_{B}(Y)>\frac{1}{4}$.

$\displaystyle n^{\prime}_{N}$
$\displaystyle=D_{A}(N)\alpha_{A}+D_{B}(N)\alpha_{B}-D_{A}(N)(\alpha_{A}-8Kf(T))-D_{B}(N)(\alpha_{B}-8K_{2}f(T))-Kf(T)$
$\displaystyle=D_{A}(N)8Kf(T)+D_{B}(N)8K_{2}f(T)-Kf(T)$ $\displaystyle\geq
2Kf(T)+2K_{2}f(T)-Kf(T)$ $\displaystyle=Kf(T)+2K_{2}f(T)>0$

A similar analysis for $Y$ shows that

$\displaystyle n^{\prime}_{Y}$
$\displaystyle=D_{A}(Y)\alpha_{A}+D_{B}(Y)\alpha_{B}-D_{A}(Y)(\alpha_{A}-8Kf(T))-D_{B}(Y)(\alpha_{B}-8K_{2}f(T))-K_{2}f(T)$
$\displaystyle=D_{A}(Y)8Kf(T)+D_{B}(Y)8K_{2}f(T)+8K_{2}-K_{2}f(T)$
$\displaystyle\geq 2Kf(T)+2K_{2}f(T)-K_{2}f(T)$
$\displaystyle=2Kf(T)+K_{2}f(T)>0$

A similar analysis can also be used to upper bound $n^{\prime}_{X}$ and
$n^{\prime}_{Y}$ by $8(K_{1}+K_{2})f(T)$. Since
$n^{\prime}_{X},n^{\prime}_{Y}\geq 0$, our construction is valid, and we have
played $N$ and $Y$ the same total frequency across the rounds as compared to
the original segment. Therefore the endpoint of the new segment will be
exactly the same 121212The state at the end of $t$ rounds only depends on the
average marginal distribution of the optimizer and is invariant to reordering
of the optimizer’s play. and the number of rounds will be as well. Further, we
argue that the CSP of this segment is very close to the CSP of the original
segment. In the new segment, because we have moved $3Hf(T)$ away from the hard
boundary and because we can only move back by $2Hf(T)$ as we play $D_{A}$, the
learner will play $A$ the whole time against this (except for a sublinear
fraction of the rounds), since we are in the clear historical best response
zone for action $A$ 131313Here, we use the fact that $f$ is monotone
increasing.. For the same reason, the learner plays $B$ against $D_{B}$ when
we play it (except for a sublinear fraction of the rounds). The other drivers
of change in the CSP are the $Kf(T)$ rounds of $\alpha_{A}$ that we do not
play $D_{A}$ (similar for $D_{B}$), the $K_{2}f(T)$ rounds of playing $Y$ that
are required to go from the region where $A$ is the clear historical best
response to where $B$ is the clear historical best response and the
$8(K_{1}+K_{2})(f(T))$ rounds of play at the end to reach the same end point
as the original segment. Even if all these changes go in the same direction,
the net effect on the CSP is at most $O(f(T))$ deviation in the $\ell_{1}$
distance since each round can only effect a change of $O(1)$ (the constants do
not depend on $T$ and are entirely determined by the learner values in the
game).

Although we have assumed that $\alpha_{A}\geq 8K_{1}f(T)$, $\alpha_{B}\geq
8K_{2}f(T)$, the same analysis can still be done if this assumption is not
true. We simply do not play $D_{A}$/$D_{B}$ in the construction if the
corresponding frequency $\alpha_{A}$/ $\alpha_{B}$ is very small. With minor
modifications, the same guarantees can be achieved without this assumption.

∎

Armed with these tools, we focus now on generating $P^{\prime}_{T}$ from
$P_{T}$ for a finite time horizon $T$. The procedure starts by decomposing the
trajectory of the point $P_{T}$ in the state space defined above into
I,C1,C2,NC1,NC2 and F segments. Each segment is then replaced with another
segment (by a suitable modification of the optimizer actions) with the same
start and end point so that the new trajectory has the property that only
sublinear time is spent outside the regions with a clear historical best
response. We maintain the invariant that the unnormalized CSP induced by this
new sequence/ trajectory against algorithm $\mathcal{A}$ is only sublinearly
different (i.e $o(T)$ distant in the $\ell_{1}$ metric) from $P_{T}$.

Dealing with the Crossing segments of the type C1 or C2 is the easiest part of
the transformation - these segments already spend their entire duration in a
region with a single clear historical best response, so we can leave them
untouched. To deal with non-crossing segments (C1/C2); we make use of Lemma
E.14 to replace them one by one with a segment that has the same start and end
point, operates for exactly the same time duration and results in a trajectory
that spends time at most $O(f(T))$ outside the clear historical best response
region and generates a CSP shifted by only $O(f(T))$ from the starting
trajectory’s CSP. A concern with this sequence of transformations is that
sufficiently large number of crossing segments can result in linear drift from
the original CSP/ linear time spent outside the clear historical best response
zone. To address this issue, we split the analysis into two parts. Set
$g(T)=\sqrt{f(T)\cdot T}$, since $f(T)$ is asymptotically sublinear, so is
$g(T)$. We split the time horizon $T$ into the first $g(T)$ time steps and the
remaining time steps. The play in the first part can only affect the CSP by
$O(g(T))$, further the total time spent outside the clear historical best
response zone in the first part is also upper bounded by $g(T)$. Using Lemma
E.13, there are at most
$O\left(\frac{T}{g(T)}\right)=O\left(\sqrt{\frac{T}{f(T)}}\right)$ crossing
segments in the second half. Therefore, the total drift (in $\ell_{1}$
distance) from the original CSP is upper bounded by
$O\left(f(T)\cdot\sqrt{\frac{T}{f(T)}}\right)=O(g(T))=o(T)$. Similarly, in the
time steps corresponding to the crossing segments, the final trajectory spend
time at most $o(T)$ away from the boundary.

A similar analysis can be done for the initial (I) and final (F) segment, by
only replacing the non-crossing part of their trajectories using Lemma E.14
and contributing an additional $o(T)$ drift away from the original CSP, and
$o(T)$ additional time spent away from the clear historical best response
zone.

##  Appendix F Omitted proofs

###  F.1 Proof of Lemma 3.1

###### Proof of Lemma 3.1.

We will first show that $V_{L}(\mathcal{M}(\mathcal{A}),u_{O})\leq
V_{L}(\mathcal{A},u_{O})$. To see this, let $\varphi^{*}$ be the CSP in
$\mathcal{M}(\mathcal{A})$ achieving the value $V_{L}(M(\mathcal{A}),u_{O})$.
There exists a sequence $\varphi^{1},\varphi^{2},\dots$ with
$\varphi^{T}\in\mathcal{M}(\mathcal{A}^{T})$ which converges to $\varphi^{*}$.
For any menu $\mathcal{M}$ and CSP $\varphi\in\mathcal{M}$, let
${\varepsilon}_{O}(\mathcal{M},\varphi)=(\max_{\varphi^{\prime}\in\mathcal{M}}u_{O}(\varphi^{\prime}))-u_{O}(\varphi)$
denote how far $\varphi$ is from optimal (for the optimizer) in $\mathcal{M}$.
Since $u_{O}$ is continuous in $\varphi$, the function ${\varepsilon}_{O}$ is
continuous, and therefore the sequence
${\varepsilon}_{O}(\mathcal{M}(\mathcal{A}^{T}),\varphi^{T})$ converges to
${\varepsilon}_{O}(\mathcal{M}(\mathcal{A}),\varphi^{*})=0$. This means that
for any ${\varepsilon}$ there exists a $T({\varepsilon})$ such that
${\varepsilon}_{O}(\mathcal{M}(\mathcal{A}^{T}),\varphi^{T})<{\varepsilon}$
for any $T\geq T({\varepsilon})$. But this implies there is a transcript in
$\mathcal{X}(\mathcal{A},u_{O},T,{\varepsilon})$ that induces $\varphi^{T}$,
and in particular, that $V_{L}(\mathcal{A},u_{O},T,{\varepsilon})\geq
u_{L}(\varphi^{T})$. In particular, for any ${\varepsilon}>0$,
$\liminf_{T\rightarrow\infty}V_{L}(\mathcal{A},u_{O},T,{\varepsilon})\geq\liminf_{T\rightarrow\infty}u_{L}(\varphi^{T})=u_{L}(\varphi^{*})=V_{L}(\mathcal{M}(\mathcal{A}),u_{O})$.
By taking ${\varepsilon}$ to $0$, it follows that
$V_{L}(\mathcal{M}(\mathcal{A}),u_{O})\leq V_{L}(\mathcal{A},u_{O})$.

We now must show $V_{L}(\mathcal{A},u_{O})\leq
V_{L}(\mathcal{M}(\mathcal{A}),u_{O})$. Let $V=V_{L}(\mathcal{A},u_{O})$; by
the definition (1) of $V_{L}(\mathcal{A},u_{O})$, there must exist a sequence
$(T_{1},{\varepsilon}_{1}),(T_{2},{\varepsilon}_{2}),\dots$ of strictly
increasing $T_{i}$ and strictly decreasing ${\varepsilon}_{i}$ where
$V_{L}(\mathcal{A},u_{O},T_{i},{\varepsilon}_{i})$ converges to $V$. For each
$(T_{i},{\varepsilon}_{i})$, let
$\varphi_{i}\in\mathcal{M}(\mathcal{A}^{T_{i}})$ be the CSP induced by a
${\varepsilon}_{i}$-optimal point in
$\mathcal{X}(\mathcal{A},u_{O},T_{i},{\varepsilon}_{i})$, i.e., one where
$u_{L}(\varphi_{i})\geq
V_{L}(\mathcal{A},u_{O},T_{i},{\varepsilon}_{i})-{\varepsilon}_{i}$. Since the
$\varphi_{i}$ all belong to the bounded closed set $\Delta_{mn}$, there must
be a convergent subsequence of these CSPs that converge to a
$\varphi^{\prime}\in\mathcal{M}(\mathcal{A})$ with the property that
$u_{L}(\varphi^{\prime})=V$. It follows that $V=V_{L}(\mathcal{A},u_{O})\leq
V_{L}(\mathcal{M}(\mathcal{A}),u_{O})$. ∎

###  F.2 Proof of Lemma 3.5

###### Proof of Lemma 3.5.

To prove that some convex set $\mathcal{M}^{\prime}$ is an asymptotic menu, it
is sufficient to prove there exists a consistent learning algorithm
$\mathcal{A}^{\prime}$ that has the asymptotic menu
$\mathcal{M}(\mathcal{A}^{\prime})=\mathcal{M}^{\prime}$. The learning
algorithm $\mathcal{A}^{\prime}$ is as follows: let $C$ be the smallest
integer that is larger than $\sqrt{T}$. Note that this grows asymptotically
with $\sqrt{T}$. The learner now construct the set $S$ of at most $O(C^{mn})$
CSPs in $\Delta_{mn}$ containing all CSPs whose coordinates are all integer
multiples of $\frac{1}{C}$, and that are within $\ell_{\infty}$-distance
$\frac{1}{C}$ of $\mathcal{M}$. Note that every CSP $\varphi$ in $\mathcal{M}$
is within $\ell_{\infty}$-distance $\frac{1}{C}$ of some CSP of this form.

We can now assign each $\varphi^{\prime}\in S$ a unique sequence of moves
which the optimizer can play in order to communicate this CSP to the learner.
As there are $C^{mn}$ points and the optimizer can play any of $m$ actions,
the optimizer can communicate this in at most $\log(C^{mn})=mn\log(C)$ rounds,
using constant number of bits each round. For the first $mn\log(C)$ rounds of
the game, the learner will play their first move, and the optimizer will
communicate their preferred $\varphi^{\prime}$.

After this, the learner will identify the $\varphi^{\prime}\in S$ associated
with this sequence, and ascribe a joint cycle of moves they can play with the
optimizer $(P(x),P(y))$ that will result in $\varphi^{\prime}$ being played in
the limit as the time horizon $T$ goes to infinity. In particular, for some
CSP $\varphi^{\prime}$, the sequence will play out in cycles of length $C$,
and in each cycle, the learner and optimizer will jointly play the move pair
$(i,j)$ for $C\cdot\varphi(i,j)$ rounds (recall that this is an integer);
iterating over move pairs in lexicographical order. If the opponent ever fails
to follow $P(j)$, the optimizer will immediately begin playing the algorithm
that converges to $\mathcal{M}$, ignoring the history of play that happened
before this failure occurred.

First we will show that
$\mathcal{M}_{A^{\prime}}\subseteq\mathcal{M}^{\prime}$. Consider, for a game
of length $T$, any sequence that the optimizer could play against $A$. During
the first $mn\log(C)$ rounds the learner and optimizer will agree on some
$\varphi^{\prime}_{\mathcal{M}^{\prime}}\in\Delta_{mn}$ and associated
sequence $(P(x),P(y))$ s.t.
$\lim_{T\rightarrow\infty}(\sum_{t=1}^{T}P(x)_{t}\otimes
P(y)_{t})=\varphi^{\prime}_{\mathcal{M}^{\prime}}$. Then let $t^{\prime}\geq
mn\log(C)$ be the first time that the follower does not play according this
sequence. Then, the resulting CSP is of the form

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}x_{t}\otimes y_{t}$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{mn\log(C)}x_{t}\otimes
y_{t}+\frac{1}{T}\sum_{i=1}^{t^{\prime}-mn\log(C)-1}P(x)_{i}\otimes
P(y)_{i}+\frac{1}{T}x_{t^{\prime}}\otimes
y_{t^{\prime}}+\frac{1}{T}\sum_{t=t^{\prime}+1}^{T}x_{t}\otimes y_{t}$ (By the
fact that the players coordinate from $mn\log(C)+1$ to $t^{\prime}-1$)
$\displaystyle=\frac{1}{T}\sum_{t=1}^{mn\log(C)}x_{t}\otimes
y_{t}+\frac{1}{T}\sum_{i=1}^{t^{\prime}-mn\log(C)-1}P(x)_{i}\otimes
P(y)_{i}+\frac{1}{T}x_{t^{\prime}}\otimes
y_{t^{\prime}}+\frac{1}{T}\sum_{t=t^{\prime}+1}^{T}A^{T-t^{\prime}}(x_{t},...x_{t^{\prime}+1})\otimes
x_{t}$ (By the fact that $A^{\prime}$ defects to playing $A$ after round
$t^{\prime}$)

We will now show that, for any ${\varepsilon}>0$, for sufficiently large $T$
the above CSP is within $\ell_{\infty}$-distance ${\varepsilon}$ of a point in
$\mathcal{M}^{\prime}$. It then follows that
$\mathcal{M}_{A^{\prime}}\subseteq\mathcal{M}^{\prime}$.

To do so, first note that if we take $T$ large enough s.t.
${\varepsilon}T>10mn\log(C)$, then (simply by modifying $2mn\log(C)$ terms of
magnitude at most $1/T$) the above CSP is within distance ${\varepsilon}/5$ of
the CSP

$\tilde{\varphi}=\frac{1}{T}\sum_{i=1}^{t^{\prime}}P(x)_{i}\otimes
P(y)_{i}+\frac{1}{T}\sum_{t=t^{\prime}+1}^{T}A^{T-t^{\prime}}(x_{t},...x_{t^{\prime}+1})\otimes
x_{t}.$

We will also define

$\tilde{\varphi}_{\mathcal{M}^{\prime}}=\frac{1}{t^{\prime}}\sum_{i=1}^{t^{\prime}}P(x)_{i}$
(6)

and

$\tilde{\varphi}_{\mathcal{M}}=\frac{1}{T-t^{\prime}}\sum_{t=t^{\prime}+1}^{T}A^{T-t^{\prime}}(x_{t},...x_{t^{\prime}+1})\otimes
x_{t}.$ (7)

By doing so we can write
$\tilde{\varphi}=\frac{t^{\prime}}{T}\varphi_{\mathcal{M}}+(1-\frac{t^{\prime}}{T})\varphi_{\mathcal{M}^{\prime}}$.
We will now show that there exist $\varphi_{\mathcal{M}}\in\mathcal{M}$ and
$\varphi_{\mathcal{M}^{\prime}}\in\mathcal{M}^{\prime}$ such that, for
sufficient large $T$,

$\displaystyle\frac{t^{\prime}}{T}||\tilde{\varphi}_{\mathcal{M}^{\prime}}-\varphi_{\mathcal{M}}||_{\infty}$
$\displaystyle\leq{\varepsilon}/5,$ (8)
$\displaystyle\frac{T-t^{\prime}}{T}||\tilde{\varphi}_{\mathcal{M}}-\varphi_{\mathcal{M}^{\prime}}||_{\infty}$
$\displaystyle\leq{\varepsilon}/5.$ (9)

Together, these two statements imply that $\tilde{\varphi}$ is within distance
$2{\varepsilon}/5$ from a convex combination of two CSPs in
$\mathcal{M}^{\prime}$, and therefore itself within distance
$2{\varepsilon}/5$ from $\mathcal{M}^{\prime}$.

To prove (8), note that whenever $t^{\prime}$ is a multiple of $C$,
$\tilde{\varphi}_{\mathcal{M}}$ is equal to our selected point
$\varphi^{\prime}\in S$. If $t^{\prime}>10C/{\varepsilon}$, then by splitting
the sum in (6) at the largest multiple of $C$, we have that
$||\tilde{\varphi}_{\mathcal{M}^{\prime}}-\varphi^{\prime}||\leq{\varepsilon}/10$.
Since $\varphi^{\prime}$ is in turn within distance $1/C$ of a CSP in
$\mathcal{M}^{\prime}$, it follows that
$||\tilde{\varphi}_{\mathcal{M}^{\prime}}-\varphi_{\mathcal{M}^{\prime}}||_{\infty}\leq{\varepsilon}/10+1/C$
for this CSP $\varphi_{\mathcal{M}^{\prime}}$; for sufficiently large $T$,
$C\leq 10/{\varepsilon}$ and we have established (6). On the other hand, if
$t^{\prime}\leq 10C/{\varepsilon}$, then $t^{\prime}/T\leq
10C/({\varepsilon}T)$, which again is at most ${\varepsilon}/5$ for
sufficiently large $T$ (in particular, some $T=\Omega({\varepsilon}^{-4})$
suffices).

Similarly, to prove (9), note that $\tilde{\varphi}_{\mathcal{M}}$ belongs to
the finite-time menu $\mathcal{M}(A^{T-t^{\prime}})$. Let $d(t)$ equal the
Hausdorff distance between $\mathcal{M}(A^{t})$ and $\mathcal{M}$; since the
sequence $\mathcal{M}(A^{t})$ converges in the Hausdorff to $\mathcal{M}$,
$d(t)=o(1)$ is sub-constant in $t$. In particular, for sufficiently large $T$,
we have that $d(\sqrt{T})\leq{\varepsilon}/10$. This directly implies that if
$T-t^{\prime}\geq\sqrt{T}$, then (9) holds. But if $T-t^{\prime}<\sqrt{T}$,
then the LHS of (9) is at most $1/\sqrt{T}$, which is also at most
${\varepsilon}/10$ for sufficiently large $T$. This concludes the proof that
$\mathcal{M}(\mathcal{A}^{\prime})\subseteq\mathcal{M}^{\prime}$.

Now we will prove that
$\mathcal{M}^{\prime}\subseteq\mathcal{M}(\mathcal{A}^{\prime})$. To see this,
consider any point $\varphi\in\mathcal{M}^{\prime}$. We will show that it is
possible to achieve this point in the limit against $A^{\prime}$. The way that
the Optimizer will achieve this point is by picking the CSP
$\varphi^{\prime}_{net(T)}$ in the $\frac{1}{C}$-net $S$ which is closest in
distance to their desired point in $\mathcal{M}^{\prime}$ and communicating
with the Learner that this is what they want to achieve. This defines a limit
cycle sequence $(P(x),P(y))$ which the two players will play together. Then,
as long as the Optimizer doesn’t defect from this sequence, the CSP of the
final point is

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}x_{t}\otimes
y_{t}=\frac{1}{T}\sum_{t=1}^{mn\log(C)}x_{t}\otimes
y_{t}+\frac{1}{T}\sum_{i=1}^{T-mn\log(C)}P(x)_{i}\otimes P(y)_{i}$

Taking the limit:

$\displaystyle\lim_{T\rightarrow\infty}\left(\frac{1}{T}\sum_{t=1}^{mn\log(C)}x_{t}\otimes
y_{t}+\frac{1}{T}\sum_{i=1}^{T-mn\log(C)}P(x)_{i}\otimes P(y)_{i}\right)$
$\displaystyle=\lim_{T\rightarrow\infty}\left(\frac{1}{T}\sum_{i=1}^{T-mn\log(C)}P(x)_{i}\otimes
P(y)_{i}\right)$
$\displaystyle=\lim_{T\rightarrow\infty}\left(\frac{1}{T}\sum_{i=1}^{T}P(x)_{i}\otimes
P(y)_{i}\right)=\lim_{T\rightarrow\infty}\varphi^{\prime}_{net(T)}$
$\displaystyle=\varphi^{*}$

Recall that $\varphi^{*}$ was our desired point in $\mathcal{M}^{\prime}$.
Therefore $\mathcal{M}^{\prime}\subseteq\mathcal{M}_{A^{\prime}}$, completing
our proof. ∎

###  F.3 Proof of Theorem 3.6

###### Proof of Theorem 3.6.

Fix some $u_{L}$. Let $\mathcal{M}_{NR}(\varepsilon)$ denote the relaxation of
the set $\mathcal{M}_{NR}$ where the no-regret constraint is relaxed to:

$\sum_{i\in[m]}\sum_{j\in[n]}\varphi_{ij}u_{L}(i,j)\geq\max_{j^{*}\in[n]}\sum_{i\in[m]}\sum_{j\in[n]}\varphi_{ij}u_{L}(i,j^{*})-\varepsilon.$

Let $\mathcal{A}$ be a no-regret algorithm. Then, for all $(u_{L},u_{O})$, its
average total regret over $T$ rounds is upper bounded by some function $f(T)$
such that $\lim_{T\rightarrow\infty}\frac{f(T)}{T}=0$. For each time horizon
$T$, define the set $S_{T}:=M_{NR}\left(\varepsilon_{T}\right)$ where
${\varepsilon}_{T}=\min\left({\varepsilon}_{T-1},\frac{f(T,n)}{T}\right)$ (so
that the sequence ${\varepsilon}_{T}$ is non-increasing). It follows that
$S_{1}\supseteq S_{2}\supseteq\cdots$ with
$\lim_{T\rightarrow\infty}S_{T}=\mathcal{M}_{NR}$ (since
$\lim_{T\rightarrow\infty}\varepsilon_{T}=0$). But it also follows from the
no-regret constraint that $\mathcal{M}(A^{T})\subseteq S_{T}$ for each $T$,
and thus, $\mathcal{M}(\mathcal{A})\subseteq\mathcal{M}_{NR}$.

A similar argument works for no-swap-regret through the use of the
corresponding relaxation. ∎

###  F.4 Proof of Lemma 3.8

###### Proof of Lemma 3.8.

We will show that every CSP of the form $x\otimes y$ with $x\in\Delta_{m}$ and
$y\in\operatorname{\mathsf{BR}}_{L}(x)$ belongs to $\mathcal{M}(\mathcal{A})$.
By Lemma 3.7, this implies that
$\mathcal{M}_{NSR}\subseteq\mathcal{M}(\mathcal{A})$.

First, consider the case where $y$ is the unique best response to $x$, i.e.,
$\operatorname{\mathsf{BR}}_{L}(x)=\\{y\\}$. By Theorem 3.3, the asymptotic
menu $\mathcal{M}(\mathcal{A})$ must contain a point of the form $x\otimes
y^{\prime}$ for some $y^{\prime}\in\Delta_{n}$. If
$y^{\prime}\not\in\operatorname{\mathsf{BR}}_{L}(x)$, then this CSP has high
regret (it violates (2)) and contradicts the fact that $\mathcal{A}$ is no-
regret. It follows that we must have $y^{\prime}=y$.

If $y$ is not a unique best-response to $x$, then we will find a point
$x^{\prime}$ close to $x$ such that $y$ is a unique best response to
$x^{\prime}$. To prove we can do this, note that since $y$ is neither weakly
dominated (by assumption) nor strictly dominated (since it is a best-
response), there must exist a strategy $x^{*}\in\Delta^{m}$ for the optimizer
which uniquely incentivizes $y$. Thus, for sufficiently small $\delta>0$, the
optimizer strategy $x(\delta)=(1-\delta)x+\delta x^{*}$ uniquely incentivizes
$y$ as a best response, and thus $x(\delta)\otimes
y\in\mathcal{M}(\mathcal{A})$. Since $\mathcal{M}(\mathcal{A})$ is closed,
taking the limit as $\delta\rightarrow 0$ implies that $x\otimes
y\in\mathcal{M}(\mathcal{A})$, as desired. ∎

###  F.5 Characterization of $\mathcal{M}_{NR}$

In Lemma 3.7, we show that the no-swap-regret menu can be alternatively
characterized as the convex hull of all “best response” CSPs, of the form
$x\otimes y$ with $x\in\Delta_{m}$ and
$y\in\operatorname{\mathsf{BR}}_{L}(x)$. In this subsection, we prove a
similar characterization of the extreme points of $\mathcal{M}_{NR}$: namely,
$\mathcal{M}_{NR}$ is the convex hull of all CSPs with exactly zero regret.

Specifically, for a CSP $\varphi$ define

$\operatorname{\mathsf{Reg}}(\varphi)=\max_{j^{*}\in[n]}\sum_{i\in[m]}\sum_{j\in[n]}\varphi_{ij}u_{L}(i,j^{*})-\sum_{i\in[m]}\sum_{j\in[n]}\varphi_{ij}u_{L}(i,j).$

We have the following lemma.

######  Lemma F.1.

$\mathcal{M}_{NR}$ is the convex hull of all CSPs $\varphi$ with
$\operatorname{\mathsf{Reg}}(\varphi)=0$.

###### Proof.

We can define $\mathcal{M}_{NR}$ as the intersection of the simplex
$\Delta_{mn}$ and the set $S$ of points $x\in\mathbb{R}^{mn}$ where
$\operatorname{\mathsf{Reg}}(x)\leq 0$ (note that we can extend the definition
of $\operatorname{\mathsf{Reg}}(\varphi)$ above to a convex function for all
$x\in\mathbb{R}^{mn}$). By definition, all CSPs $\varphi$ with
$\operatorname{\mathsf{Reg}}(\varphi)=0$ are contained in $\mathcal{M}_{NR}$.
All extreme points $\varphi$ of $\mathcal{M}_{NR}$ must lie either on the
boundary of $S$ (where it is guaranteed that
$\operatorname{\mathsf{Reg}}(\varphi)=0$), or must themselves be an extreme
point of $\Delta_{mn}$. But the extreme points of $\Delta_{mn}$ correspond to
pure strategies of the form $\varphi=i\otimes j$. If such a strategy has
$\operatorname{\mathsf{Reg}}(\varphi)\leq 0$, it must also have
$\operatorname{\mathsf{Reg}}(\varphi)=0$ (since replacing $j^{*}=j$ leaves the
learner’s utility unchanged).

It follows that all extreme points of $\mathcal{M}_{NR}$ have zero regret. ∎

Lemma F.1 should not be interpreted as implying that _every_ point in
$\mathcal{M}_{NR}$ has exactly zero regret; indeed, many points in the
interior of $\mathcal{M}_{NR}$ may have negative regret
$\operatorname{\mathsf{Reg}}(\varphi)<0$. In particular,
$\operatorname{\mathsf{Reg}}$ is a convex function of $\varphi$, and it may be
the case that the convex combination of two CSPs may have less regret than
either individual CSP. In contrast, the swap regret function is always non-
negative, so $\mathcal{M}_{NSR}$ does exactly contain the points with zero
swap regret.

###  F.6 Proof of Lemma 5.2

###### Proof of Lemma 5.2.

We will do this in two steps. First, call a segment $(x_{i},t_{i},b_{i})$ of a
trajectory _non-degenerate_ if $b_{i}$ is a strict best response of the
learner throughout the entire segment, i.e.,
$\operatorname{\mathsf{BR}}_{L}(\overline{x}_{i-1})=\operatorname{\mathsf{BR}}_{L}(\overline{x}_{i})=\\{b_{i}\\}$.
We say a trajectory itself is ${\varepsilon}$-non-degenerate if at least a
$1-{\varepsilon}$ fraction of the segments of the trajectory (weighted by
duration $t_{i}$) are non-degenerate. We begin by claiming that for any valid
trajectory $\tau$ and ${\varepsilon}>0$, there exists an ${\varepsilon}$-non-
degenerate trajectory $\tau^{\prime}$ such that
$||\operatorname{\mathsf{Prof}}(\tau)-\operatorname{\mathsf{Prof}}(\tau^{\prime})||_{1}\leq{\varepsilon}$.
In other words, for any CSP induced by $\tau$, we can always approximately
induce it by a trajectory which is almost always non-degenerate.

To prove this, if $\tau=\\{(x_{1},t_{1},b_{1}),\dots,(x_{k},t_{k},b_{k})\\}$,
we will construct a $\tau^{\prime}$ of the form

$\tau^{\prime}=\\{(y_{1},\delta_{1}),(x_{1},t_{1},b_{1}),(y_{2},\delta_{2}),(x_{2},t_{2},b_{2}),\dots,(y_{k},\delta_{k}),(x_{k},t_{k},b_{k})\\},$

where $\tau^{\prime}$ is formed by interleaving $\tau$ with a sequence of
short “perturbation” segments $(y_{i},\delta_{i})$. The goal will be to choose
these segments such that each primary segment of the form
$(x_{i},t_{i},b_{i})$ is non-degenerate, while keeping the duration
$\delta_{i}$ of each perturbation segment small. Note that we haven’t
specified the learner’s response for these perturbation segments – the intent
is that since these segments are small, they will not significantly contribute
to $\operatorname{\mathsf{Prof}}(\tau)$ and we can ignore them (in fact, it is
possible that they will cross best-response boundaries, in which case we can
split them up into smaller valid segments).

Now, let $\overline{x^{\prime}}_{i-}$ and $\overline{x^{\prime}}_{i+}$ be the
time-weighted average strategies of the optimizer right before and right after
segment $(x_{i},t_{i},b_{i})$ in $\tau^{\prime}$, respectively. Let
$\overline{y}_{i}=(\sum_{j=1}^{i}y_{j}\delta_{j})/(\sum_{j=1}^{i}\delta_{j})$
be the time-weighted average strategy of the first $i$ perturbations. Note
that $\overline{x^{\prime}}_{i-}$ is a non-trivial convex combination of
$\overline{x}_{i-1}$ and $\overline{y}_{i}$. Since
$b_{i}\in\operatorname{\mathsf{BR}}_{L}(\overline{x}_{i-1})$, if $b_{i}$ is a
strict best-response to $\overline{y}_{i}$ (i.e.,
$\operatorname{\mathsf{BR}}_{L}(\overline{y}_{i})=\\{b_{i}\\}$), then this
would imply that $b_{i}$ is a strict best-response to
$\overline{x^{\prime}}_{i-}$. Likewise, $\overline{x^{\prime}}_{i+}$ is a non-
trivial convex combination of $\overline{x}_{i}$ and $\overline{y}_{i}$, so
this would also imply that $b_{i}$ is a strict best-response to
$\overline{x^{\prime}}_{i+}$. Altogether, if $\overline{y}_{i}$ strictly
incentivizes action $b_{i}$, then segment $(x_{i},t_{i},b_{i})$ is non-
degenerate.

But note that since no action for the learner is weakly dominated, we can
construct a sequence of perturbations where each $\overline{y}_{i}$ strictly
incentivizes action $b_{i}$ (simply set $y_{i}$ equal to an action which
strictly incentivizes $b_{i}$, and make $\delta_{i}$ big enough compared to
preceding $\delta$). But also, if a given sequence
$\\{(y_{1},\delta_{1}),\dots,(y_{k},\delta_{k})\\}$ of perturbations has this
property, so does any scaling
$\\{(y_{1},\lambda\delta_{1}),\dots,(y_{k},\lambda\delta_{k})\\}$ of this
sequence. So we can scale this sequence so that $\sum_{i=1}^{k}\delta_{i}\leq
0.5\cdot{\varepsilon}\cdot\sum_{i=1}^{k}t_{i}$.

Doing this guarantees that the trajectory is ${\varepsilon}$-non-degenerate.
It also guarantees that
$\operatorname{\mathsf{Prof}}(\tau^{\prime})=(1-{\varepsilon}/2)\operatorname{\mathsf{Prof}}(\tau)+({\varepsilon}/2)\varphi_{\delta}$
for some other CSP $\varphi_{\delta}\in\Delta_{mn}$; from this, we have that
$||\operatorname{\mathsf{Prof}}(\tau)-\operatorname{\mathsf{Prof}}(\tau^{\prime})||_{1}\leq({\varepsilon}/2)(||\operatorname{\mathsf{Prof}}(\tau)||_{1}+||\varphi_{\delta}||_{1})={\varepsilon}$.
Our desired claim follows.

In the second step, we will show that given any ${\varepsilon}$-non-degenerate
trajectory $\tau$, there exists a CSP $\varphi$ in $\mathcal{M}$ with the
property that $||\varphi-\operatorname{\mathsf{Prof}}(\tau)||_{1}\leq
2{\varepsilon}$. Combining this with the previous claim, this implies that for
any valid trajectory $\tau$, there exists a sequence of CSPs in $\mathcal{M}$
converging to $\operatorname{\mathsf{Prof}}(\tau)$, and thus
$\operatorname{\mathsf{Prof}}(\tau)\in\mathcal{M}$ (and
$\mathcal{M}_{MB}\subseteq\mathcal{M}$).

To prove this, we simply play out the trajectory. Without loss of generality,
assume that for $\tau$, the total duration $\sum_{i=1}^{k}t_{i}=1$ (if not,
scale it so that this is true). The adversary will play each action $x_{i}$
for $\lfloor t_{i}T\rfloor$ rounds.

Now, assume $\mathcal{A}$ is a mean-based algorithm with a specific rate
$\gamma(T)$. Assume segment $i$ of $\tau$ is non-degenerate and consider the
action of the learner at round $t=(t_{1}+t_{2}+\dots+t_{i-1}+\lambda t_{i})T$
(for some $0\leq\lambda\leq 1$). At this point in time, for any action
$j\in[n]$ for the learner, we can write

$\frac{1}{t}\sum_{s=1}^{t}u_{L}(x_{t},j)=(1-\lambda)u_{L}(\overline{x}_{i-1},j)+\lambda
u_{L}(\overline{x}_{i},j).$

Since segment $i$ is non-degenerate,
$\operatorname{\mathsf{BR}}_{L}(\overline{x}_{i-1})=\operatorname{\mathsf{BR}}_{L}(\overline{x}_{i})=\\{b_{i}\\}$,
so there exists some constant $g_{i}$ (depending only on $\tau$ and not on
$T$) such that
$u_{L}(\overline{x}_{i-1},b_{i})>u_{L}(\overline{x}_{i-1},b^{\prime})+g_{i}$
and $u_{L}(\overline{x}_{i},b_{i})>u_{L}(\overline{x}_{i},b^{\prime})+g_{i}$
for any $b^{\prime}\neq b_{i}$. It follows that for any $b^{\prime}\neq
b_{i}$,

$\frac{1}{t}\sum_{s=1}^{t}u_{L}(x_{t},b_{i})>g_{i}+\frac{1}{t}\sum_{s=1}^{t}u_{L}(x_{t},b^{\prime}).$

Since $t$ scales with $T$, for large enough $T$, we will have
$g_{i}>\gamma(t)$. The mean-based property then implies that the learner must
put at least $(1-n\gamma(t))=1-o(1)$ weight on action $b_{i}$. It follows that
each non-degenerate segment $(x_{i},t_{i},b_{i})$ contributes a
$t_{i}(x_{i}\otimes b_{i})$ term to the limiting CSP as $T\rightarrow\infty$.
But this is exactly the term this segment contributes to
$\operatorname{\mathsf{Prof}}(\tau)$. Since all but an
${\varepsilon}$-fraction of $\tau$ is comprised of non-degenerate segments,
this means the limiting CSP $\varphi$ in $\mathcal{M}$ has the property that
$||\varphi-\operatorname{\mathsf{Prof}}(\tau)||_{1}\leq 2{\varepsilon}$.

∎

###  F.7 Proof of Lemma 5.12

###### Proof of Lemma 5.12.

We prove these properties in order.

First, for any time horizon $T$, the definition of FTRL ensures that
$\left|\frac{R_{T}(y)}{\eta_{T}}\right|\leq g(T)$ for some monotone sublinear
function $g(T)=o(T)$. At round $t$, consider any action $j$ that is at least
$\sqrt{\frac{2g(T)}{T}}$ worse on average than the historical best action
$j^{\prime}$. Assume, for contradiction, that the distribution $y_{t}$ picked
by the algorithm puts mass at least $\sqrt{\frac{2g(T)}{T}}$ on action $j$,
i.e. $y_{t,j}\geq\sqrt{\frac{2g(T)}{T}}$. An alternative distribution
$y^{\prime}_{t}\in\Delta^{n}$ can thus be constructed from $y_{t}$ by setting
$y^{\prime}_{t,i}=y_{t,i}$ for all $i\notin\\{j,j^{\prime}\\}$,
$y^{\prime}_{t,j}=y_{t,j}-\sqrt{\frac{2g(T)}{T}}$ and
$y^{\prime}_{t,j^{\prime}}=y_{t,j^{\prime}}+\sqrt{\frac{2g(T)}{T}}$. It is
easy to see that $y^{\prime}_{t}$ obtains lower value on the objective
minimized by $y_{t}$, leading to a contradiction. Thus, the finite-time
algorithm is mean-based with $\gamma(T)=\sqrt{\frac{2g(T)}{T}}$.

The regret upper bound follows from standard regret properties of FTRL
algorithms with strongly convex regularizers (see [21]), while the lower bound
is proved for all FTRL algorithms by GM [20].

The third property follows directly from the definition of
$\textsf{FTRL}_{T}(\eta,R)$, for the function $\widetilde{A}_{T}(U)$ given by

$\widetilde{A}_{T}(U)=\arg\max_{y\in\Delta_{n}}\left(\langle
U,y\rangle-\frac{R(y)}{\eta_{T}}\right).$ (10)

Note that since $y\in\Delta_{n}$, adding $\Delta$ to each component of $U$
increases $\langle U,y\rangle$ by a $y$-independent $\Delta$, and therefore
does not affect the argmax.

Finally, to show the last property, we will take

$\widetilde{A}^{\prime}_{T}(U^{\prime})=\arg\max_{y^{\prime}\in\Delta_{n-1}}\left(\langle
U^{\prime},y^{\prime}\rangle-\frac{R^{\prime}(y^{\prime})}{\eta_{T}}\right),$
(11)

where $U^{\prime}\in\mathbb{R}^{n-1}$ and $R^{\prime}(y^{\prime})=R(\pi(y))$
(recall $\pi$ is the embedding from $\Delta_{n-1}$ to $\Delta_{n}$ that
ignores the $j$th coordinate). For a fixed $U$ (and corresponding $U^{\prime}$
obtained by removing coordinate $j$), let $\Phi(y)=\langle
U,y\rangle-R(y)/\eta_{T}$ and $\Phi^{\prime}(y^{\prime})=\langle
U^{\prime},y^{\prime}\rangle-R^{\prime}(y^{\prime})/\eta_{T}$. Let
$y_{\text{opt}}$ and $y^{\prime}_{\text{opt}}$ be the maximizers of $\Phi$ and
$\Phi^{\prime}$ respectively (i.e., the values of $\widetilde{A}_{T}(U)$ and
$\widetilde{A}^{\prime}_{T}(U^{\prime})$). Finally, let $r({\varepsilon})$ be
the maximum value of $R(y_{1})-R(y_{2})$ over all pairs
$(y_{1},y_{2})\in\Delta_{n}\times\Delta_{n}$ with
$||y_{1}-y_{2}||_{1}\leq{\varepsilon}$. Since $R(y)$ is bounded and convex,
$r({\varepsilon})$ must go to zero as ${\varepsilon}$ approaches $0$.

By construction, $R$ is $\alpha$-strongly-convex for some fixed $\alpha>0$.
Then $\Phi(y)$ is $(\alpha/\eta_{T})$-convex, so for any $y\in\Delta_{n}$, if
$||y-y_{\text{opt}}||_{2}\geq\delta$, then
$\Phi(y_{\text{opt}})-\Phi(y)\geq\alpha\delta^{2}/\eta_{T}$.

On the other hand, consider the $z\in\Delta_{n}$ formed by taking
$y_{\text{opt}}$ and moving all the mass on coordinate $j$ to the coordinate
$j^{*}=\operatorname*{arg\,max}_{j^{*}\in[n]}U_{j^{*}}$. Since we have moved
mass to a better coordinate, we have that $\langle U,z\rangle\geq\langle
U,y_{\text{opt}}\rangle$. But also, since $y_{\text{opt}}$ has at most
$\gamma(T)$ weight on action $j$ (by the mean-based property we established
earlier), $||y_{\text{opt}}-z||_{1}\leq 2\gamma(T)$, and so
$|R(y_{\text{opt}})-R(z)|\leq r(2\gamma(T))$. Together, this shows that
$\Phi(y_{\text{opt}})-\Phi(z)\leq r(2\gamma(T))/\eta$.

But since $z$ has no mass on coordinate $j$, $z=\pi(z^{\prime})$ for some
$z^{\prime}\in\Delta_{n-1}$. From the definition of $\Phi^{\prime}$, we
further have that $\Phi^{\prime}(z^{\prime})=\Phi(z)$. Since
$y^{\prime}_{\text{opt}}$ maximizes $\Phi^{\prime}$, we have that
$\Phi^{\prime}(y^{\prime}_{\text{opt}})\geq\Phi^{\prime}(z^{\prime})$.

It follows that
$\Phi(y_{\text{opt}})-\Phi(\pi(y^{\prime}_{\text{opt}}))=\Phi(y_{\text{opt}})-\Phi^{\prime}(y^{\prime}_{\text{opt}})\geq
r(2\gamma(T))/\eta$. From the earlier statement about the strong convexity of
$\Phi$, this implies that
$||y_{\text{opt}}-\pi(y^{\prime}_{\text{opt}})||_{2}\leq\sqrt{r(2\gamma(T))/\alpha}$.
Since $\gamma(T)=o(1)$ and $r({\varepsilon})$ converges to zero as
${\varepsilon}$ goes to zero, it follows that if we let
$\operatorname{\zeta}(T)=T\sqrt{r(2\gamma(T))/\alpha}$, then
$||y_{\text{opt}}-\pi(y^{\prime}_{\text{opt}})||\leq\operatorname{\zeta}(T)/T$,
and $\operatorname{\zeta}(T)=o(T)$, as desired.

∎

##  Appendix G The mean-based menu and no-regret menu may differ

The mean-based menu contains all CSPs asymptotically reachable against some
mean-based algorithm. Since there are many no-regret mean-based algorithms, it
is natural to wonder if perhaps the mean-based menu $\mathcal{M}_{MB}$ is
simply equal to the no-regret menu $\mathcal{M}_{NR}$: that is, perhaps any
CSP $\varphi$ with no-regret is achievable as the profile
$\operatorname{\mathsf{Prof}}(\tau)$ of a valid trajectory $\tau$.

In this Appendix, we show that this is not the case. In particular, we prove
the stronger statement that for the choice of $u_{L}$ in (4), no mean-based
algorithm has $\mathcal{M}_{NR}$ as its asymptotic menu.

######  Lemma G.1.

For the choice of $u_{L}$ in (4), the asymptotic menu of any mean-based no-
regret algorithm $\mathcal{A}$ is a strict subset of $\mathcal{M}_{NR}$. In
particular, $\mathcal{M}_{MB}\subset\mathcal{M}_{NR}$.

###### Proof.

Consider any mean-based no-regret algorithm $\mathcal{A}$. We must show there
exists a CSP $\varphi$ in $\mathcal{M}_{NR}$ that cannot be in
$\mathcal{M}(\mathcal{A})$. Before doing this, we will prove a useful
intermediary result: any extreme point of $\mathcal{M}(\mathcal{A})$ which
contains both the actions $A$ and $C$ must also contain the action $B$. Assume
for contradiction that this is not the case. Then, there is an extreme point
$p$ which contains $A$ and $C$ but not $B$. Consider some trajectory $\tau$
which achieves $p$ against $\mathcal{A}$ (this must exist because $p$ is an
extreme point). Because both $A$ and $C$ are played a constant fraction of the
time, there is some constant that can be picked such that, after that time,
$A$ and $C$ both must still be played, and therefore there is a switch from
$A$ to $C$ or from $C$ to $A$. But during that time, $B$ needs to be played.

Now we can turn back to our main proof. Let the CSP which we claim is not in
$\mathcal{M}(\mathcal{A})$ be
$\gamma=(\frac{1}{3}(A,X),\frac{1}{3}(A,Y),\frac{1}{3}(C,Y))$. Assume for
contradiction that in fact $\gamma\in\mathcal{M}(\mathcal{A})$. Then $\gamma$
can be decomposed into extreme points of $\mathcal{M}(\mathcal{A})$. But none
of these extreme points can contain both $A$ and $C$, as proven above.
Therefore, one of the extreme points is $CY$, and the remaining extreme points
have $(\frac{1}{2}AX,\frac{1}{2}AY)$ as a convex combination. However,
$(\frac{1}{2}AX,\frac{1}{2}AY)$ has positive regret (the learner would rather
plan $B$). Thus $(\frac{1}{2}AX,\frac{1}{2}AY)$ cannot be within
$\mathcal{M}(\mathcal{A})$, and therefore is not the convex combination of
extreme points of $\mathcal{M}(\mathcal{A})$. This is a contradiction.
Therefore, $\gamma\notin\mathcal{M}(\mathcal{A})$ for any mean-based no-regret
algorithm $\mathcal{A}$, completing our proof. ∎

##  Appendix H Beyond utility-specific learners

###  H.1 Global Learning Algorithms

In all previous sections of this paper, we have assumed that the learner has
access to full information about their own payoffs at the start of the game.
However, we can also think about them as committing to a mapping from learner
utilities $u_{L}$ to learning algorithms. We will refer to this mapping as a
_global_ learning algorithm, and extend our definitions accordingly. When
necessary for clarity, we will refer to the standard learning algorithms
discussed previously in this paper as _utility-specific_ learning algorithms.

######  Definition H.1 (Global Learning Algorithm).

A global learning algorithm $G$ is a mapping from learner utilities $u_{L}$ to
utility-specific learning algorithms $\mathcal{A}$.

######  Definition H.2 (No-Regret Global Algorithm).

A global learning algorithm $G$ is no regret if, for all $u_{L}$, $G(u_{L})$
is a no-regret algorithm.

######  Definition H.3 (No-Swap Regret Global Algorithm).

A global learning algorithm $G$ is no swap regret if, for all $u_{L}$,
$G(u_{L})$ is a no swap regret algorithm.

######  Definition H.4 (Strictly Mean-Based Global Algorithm).

A global learning algorithm $G$ is strictly mean-based if, for all $u_{L}$,
$G(u_{L})$ is strictly mean-based.

While we have previously represented $u_{L}$ implicitly in our notation for
learner payoffs, $u_{L}$ is unknown to our global learning algorithm $G$, and
thus we will instead write $V_{L}(\mathcal{A},u_{L},u_{O})$. We can now define
Pareto-optimality and Pareto-domination over this larger space:

######  Definition H.5 (Asymptotic Pareto-Dominance for Global Learning
Algorithms).

A global learning algorithm $G_{1}$ _asymptotically Pareto-dominates_ another
global learning algorithm $G_{2}$ if, for a positive measure set of $u_{L}$,
there is a positive measure set of $u_{O}$ such that
$V_{L}(G_{1}(u_{L}),u_{L},u_{O})>V_{L}(G_{2}(u_{L}),u_{L},u_{O})$.
Furthermore, for all remaining $u_{L}$ and $u_{O}$,
$V_{L}(G_{1}(u_{L}),u_{L},u_{O})\geq V_{L}(G_{2}(u_{L}),u_{L},u_{O})$. A
global learning algorithm is Pareto-optimal if no global learning algorithm
Pareto-dominates it.

There is a tight relationship between Pareto-domination as we have discussed
it previously and Pareto-domination over the class of global learning
algorithms:

######  Lemma H.6.

A global learning algorithm $G$ is asymptotically Pareto-dominated if and only
if there exists a positive measure set of $u_{L}$ such that for each $u_{L}$,
$G(u_{L})$ is Pareto dominated by some learning algorithm $\mathcal{A}$.

###### Proof.

First, we will prove the forwards direction. Consider some global learning
algorithm $G_{2}$ that is asymptotically Pareto-dominated by some global
learning algorithm $G_{1}$. Then, by definition, $G_{1}$ Pareto-dominates
$G_{2}$ on a positive meausure set of games. Thus for a positive measue set of
$u_{L}$, $G_{2}(u_{L})$ is Pareto dominated by the learning algorithm
$G_{1}(u_{L})$.

Now, we can prove the backwards direction. Consider some global learning
algorithm $G_{2}$ which has some positive measure set of of $u_{L}$ such that
$G_{2}(u_{L})$ is Pareto dominated by some learning algorithm $\mathcal{A}$.
Let $U^{*}$ be the set of learner utilities such that this Pareto domination
occurs, and let $f:U^{*}\rightarrow\mathcal{A}$ be a mapping from these
utilities to the learning algorithm that Pareto-dominates $G_{2}(u_{L})$.

Then, we can define a global algorithm $G_{1}$ that takes as input $u_{L}$ as
follows:

  * •

If $u_{L}\in U^{*}$, behave according to $f(u_{L})$.

  * •

Else, behave according to $G_{2}(u_{L})$.

We claim that $G_{1}$ Pareto-dominates $G_{2}$. To see this, note that $U^{*}$
is a positive measure set, so for a positive measure set of $u_{L}$,
$G_{1}(u_{L})$ Pareto-dominates $G_{2}(u_{L})$. Furthermore, for all
$(u_{L},u_{O})$ pairs, if $u_{L}\notin U^{*}$, the algorithms will behave
exactly the same (and thus their performance will be equivalent). Finally, if
$u_{L}\in U^{*}$, by the promise of Pareto-domination of the utility-specific
learning algorithm $\mathcal{A}$, there is no $(u_{L},u_{O})$ pair such that
$G_{2}(u_{L})$ outperforms $G_{1}(u_{L})$. ∎

Combining Corollary 5 and Lemma H.6, we attain the following corollary:

######  Corollary H.7.

All strictly mean-based global algorithms are Pareto-dominated.

And combining Corollary 5, Theorem 3.9 and Corollary 4.10, we attain the
following corollary:

######  Corollary H.8.

All no swap regret global algorithms are Pareto-optimal.

Thus, our main results extend easily to the global setting. However, restating
the problem in this way allows us to explore an important subset of global
learning algorithms: those which do not directly utilize information about
$u_{L}$.

###  H.2 Game-Agnostic Algorithms

Both the class of strictly mean-based algorithms and the class of no-swap
regret algorithms include many well-known algorithms that do not explicitly
map from $u_{L}$ to a utility-specific learning algorithm. Multiplicative
weights, for example, receives information about $u_{L}$ only in the form of
counterfactual payoffs after each round.

We call algorithms with this level of information about $u_{L}$ _game-
agnostic_ algorithms. We will exploit the freedom of dependence that global
algorithms can have on $u_{L}$ in order to explicitly define these game-
agnostic algorithms as a subclass of global algorithms.

######  Definition H.9 (Game-Agnostic Algorithm).

A game-agnostic algorithm is a global learning algorithm which cannot directly
utilize information about the initial input $u_{L}$, or see the number of
actions of the optimizer. Instead, this algorithm can only change its state
according to the counterfactual payoffs for their actions after each round.

Game-agnostic algorithms utilize the standard informational model of the
online learning setting, in that they only learn about their own utilities
counterfactually on a round-per-round basis. We can now define a weaker
condition for Pareto-optimality, restricted to the comparison class of game-
agnostic algorithms:

######  Definition H.10 (Asymptotic Pareto-dominance over Game-Agnostic
Algorithms).

A game-agnostic learning algorithm $G$ is _asymptotically Pareto-optimal over
Game-Agnostic Algorithms_ if it is not asymptotically Pareto-dominated by any
game-agnostic learning algorithm.

######  Lemma H.11.

If a game-agnostic algorithm $G$ is Pareto-optimal, it is also Pareto-optimal
over game-agnostic algorithms.

###### Proof.

Consider some game-agnostic algorithm $G$ which is Pareto-optimal over all
$u_{L}$. Then, it is not asymptotically Pareto-dominated by any global
learning algorithm. This includes the set of all game-agnostic learning
algorithms. Therefore, $G$ is not Pareto-dominated by any game-agnostic
learning algorithm, completing our proof. ∎

Notably, within the class of no-swap-regret algorithms, which we have proven
to be Pareto-optimal, there are many game-agnostic learning algorithms, such
as Blum-Mansour and TreeSwap [5, 13, 30].

######  Corollary H.12.

All game-agnostic learning algorithms that guarantee sublinear swap regret are
Pareto-optimal over the space of all game-agnostic learning algorithms.

While we are able to extend our Pareto-optimality results to the game-agnostic
setting, we leave as a open question whether FTRL algorithms are still Pareto-
dominated in this general sense. Notably, while many FTRL algroithms are game-
agnostic, the algorithm that we prove Pareto-dominates these algorithms in
Corollary 5.14 is not game-agnostic itself. In particular, the algorithm
crucially uses $u_{L}$ in order to determine which points to “delete” from the
mean-based menu.