# Solving optimization problems with Blackwell approachability

Julien Grand-Clément
ISOM Department
HEC Paris
<EMAIL_ADDRESS>
&Christian Kroer
IEOR Department
Columbia University
<EMAIL_ADDRESS>

###### Abstract

We introduce the Conic Blackwell Algorithm+ (CBA+) regret minimizer, a new
parameter- and scale-free regret minimizer for general convex sets. CBA+ is
based on Blackwell approachability and attains $O(\sqrt{T})$ regret. We show
how to efficiently instantiate CBA+ for many decision sets of interest,
including the simplex, $\ell_{p}$ norm balls, and ellipsoidal confidence
regions in the simplex. Based on CBA+ we introduce SP-CBA+ a new parameter-
free algorithm for solving convex-concave saddle-point problems, which
achieves a $O(1/\sqrt{T})$ ergodic rate of convergence. In our simulations, we
demonstrate the wide applicability of SP-CBA+ on several standard saddle-point
problems, including matrix games, extensive-form games, distributionally
robust logistic regression, and Markov decision processes. In each setting,
SP-CBA+ achieves state-of-the-art numerical performance, and outperforms
classical methods, without the need for any choice of step sizes or other
algorithmic parameters.

##  1 Introduction

In this paper111A preliminary version of this paper has appeared as a
conference paper by the same authors (Grand-Clément and Kroer, 2021b)., we
develop new algorithms for solving the following convex-concave _saddle-point
problems_ (SPPs):

$\displaystyle\min_{\bm{x}\in\mathcal{X}}\max_{\bm{y}\in\mathcal{Y}}F(\bm{x},\bm{y}),$
(1)

where $\mathcal{X}\subset\mathbb{R}^{n},\mathcal{Y}\subset\mathbb{R}^{m}$ are
convex, compact sets, and
$F:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ is a subdifferentiable
convex-concave function. The optimization problem (1) arises in a number of
practical problems. For example, the problem of computing a Nash equilibrium
of a zero-sum game can be formulated as a convex-concave SPP, and this is the
foundation of most methods for solving sequential zero-sum games (von Stengel,
1996; Zinkevich et al., 2007; Tammelin et al., 2015; Kroer et al., 2020).
Other instances include imaging (Chambolle and Pock, 2011),
$\ell_{\infty}$-regression (Sidford and Tian, 2018), Markov Decision Processes
(MDPs) and robust MDPs (Iyengar, 2005; Wiesemann et al., 2013; Sidford and
Tian, 2018), market equilibrium (Kroer et al., 2021) and distributionally
robust logistic regression, where the $\max$ term represents the
distributional uncertainty (Namkoong and Duchi, 2016; Ben-Tal et al., 2015).
We introduce efficient algorithms for solving (1), focusing on parameter-free
algorithms that do not require choosing, learning or tuning any step sizes.

#### Repeated game framework

One way to solve convex-concave SPPs is by viewing the SPP as a repeated game
between two players: at each iteration $t$, one player chooses
$\bm{x}_{t}\in\mathcal{X}$, the other player chooses
$\bm{y}_{t}\in\mathcal{Y}$, and then the players observe the payoff
$F(\bm{x}_{t},\bm{y}_{t})$. If each player employs a regret-minimization
algorithm, then a well-known theorem says that the uniform average of the
decisions generated by the players converge to a solution to the SPP (see
Theorem 2.1 in Section 2). We will call this the “repeated game framework”.
There are already well-known algorithms for instantiating the above repeated
game framework for (1). For example, one can employ the _online mirror
descent_ (OMD) algorithm (Nemirovski and Yudin, 1983), which generates
iterates as follows for the first player (and similarly for the second
player):

$\displaystyle\bm{x}_{t+1}=\operatorname*{arg\,min}_{\bm{x}\in\mathcal{X}}\langle\eta\bm{f}_{t},\bm{x}\rangle+D(\bm{x},\bm{x}_{t}),$
(2)

where $\bm{f}_{t}\in\partial_{\bm{x}}F(\bm{x}_{t},\bm{y}_{t})$
($\partial_{\bm{x}}$ denotes the set of subgradients as regards the variable
$\bm{x}$), $\eta>0$ is an appropriate step size, and $D$ is a _Bregman
divergence_ which measures distance between points. Another example of a
regret minimizer is Follow-The-Regularized-Leader (FTRL) (Abernethy et al.,
2009), which generates updates as follows:

$\displaystyle\bm{x}_{t+1}=\operatorname*{arg\,min}_{\bm{x}\in\mathcal{X}}\langle\eta\sum_{\tau=1}^{t}\bm{f}_{\tau},\bm{x}\rangle+D(\bm{x},\bm{x}_{t}).$
(3)

The updates (2) and (3) can be computed efficiently for many decision sets
$\mathcal{X}$ and one can achieve an average regret on the order of
$O(1/\sqrt{T})$ after $T$ iterations. This regret can be achieved by choosing
a fixed step size $\eta=\sqrt{2}\Omega/L\sqrt{T}$, where $L$ is an upper bound
on the $\ell_{2}$-norms of the subgradients $\left(\bm{f}_{t}\right)_{t\geq
0}$ and
$\Omega=\max\\{\|\bm{x}-\bm{x}^{\prime}\|_{2}\;|\;\bm{x},\bm{x}^{\prime}\in\mathcal{X}\\}.$
Choosing the step size $\eta$ is problematic, as it requires choosing in
advance the number of iterations $T$ and to know the upper bound $L$, which
may be hard to obtain in many applications or too conservative in practice.
Alternatively, it is possible to choose changing step sizes
$\eta_{t}=\alpha/\sqrt{t}$, for $\alpha>0$. Still, adequately tuning the
parameter $\alpha$ can be time- and resource-consuming. This is not just a
theoretical issue, as we highlight in our numerical experiments (Section 5)
and in the appendices (Appendices F).

These issues can be addressed by employing adaptive step sizes, which estimate
the parameters through the observed subgradients, e.g., AdaHedge for the
simplex setting (De Rooij et al., 2014) or AdaFTRL for general compact convex
decisions sets (Orabona and Pál, 2015). These adaptive variants have not seen
practical adoption in large-scale game-solving, where variants based on
Blackwell approachability are preferred (see the next paragraph). As we show
in our experiments, adaptive variants of OMD and FTRL perform much worse than
our proposed algorithms. While these adaptive algorithms are referred to as
_parameter-free_ , this is only true in the sense that they are able to learn
the necessary parameters. Our algorithm is parameter-free in the stronger
sense that there are no parameters that even require learning.

#### Blackwell approachability

In this paper, we use the framework of Blackwell approachability (Blackwell,
1956) to develop novel parameter-free algorithms for solving the convex-
concave saddle-point problem (1). In principle, Blackwell approachability
arises in the framework of repeated two-player games with vector-valued
payoff: the goal of the first-player is to choose a sequence of decisions
$\bm{x}_{1},\bm{x}_{2},...,$ such that the average of the visited payoff
converges to a known target set $\mathcal{S}$, while the second-player is
typically playing adversarially. Blackwell’s celebrated theorem (Blackwell,
1956) provides an algorithm for constructing such a sequence of decisions
$\bm{x}_{1},\bm{x}_{2},...,$ in the case where the target set $\mathcal{S}$ is
half-space forceable (see details in Section 2).

Blackwell approachability is a very general framework and the applications are
numerous, ranging from stochastic games (Milman, 2006), revenue management,
market design, and submodular maximization (Niazadeh et al., 2020),
calibration (Perchet, 2010), learning in games (Aumann et al., 1995), and fair
online learning (Chzhen et al., 2021). In particular, Blackwell
approachability can be used as a regret minimizer (Abernethy et al., 2011),
and provides a no-regret algorithm, with a average regret of
$O\left(1/\sqrt{T}\right)$ after $T$ iterations. Crucially, when applied to
online regret minimization, Blackwell approachability can be instantiated
without evaluating any of the smoothness or convexity parameters of the
objective function $F$, and the resulting no-regret algorithm does not use any
step sizes: this is in contrast to classical regret minimizers such as OMD (2)
and FTRL (3), which require choosing step sizes.

Despite its appealing properties from a theoretical standpoint, in practice
Blackwell approachability is not widely used to solve classical optimization
problems. In fact, to the best of our knowledge, the only practical
implementation of Blackwell approachability for solving (1) is for the case of
bilinear games on the simplex, where
$F(\bm{x},\bm{y})=\langle\bm{x},\bm{Ay}\rangle$ for
$\bm{A}\in\mathbb{R}^{n\times m}$, and $\mathcal{X},\mathcal{Y}$ are
simplices. This simplex instantiation is also used for Extensive-Form Games
(EFGs), via the aforementioned CFR decomposition (Zinkevich et al., 2007;
Farina et al., 2019a). In the simplex setting, a particular application of
Blackwell approachability yields a no-regret algorithm called regret matching
(RM) (Hart and Mas-Colell, 2000). Combining RM with specific weighting,
thresholding, and alternating schemes yields an algorithm called _regret
matching +_ (RM+) (Tammelin et al., 2015). RM+ has been used in _every_ case
of solving extremely large-scale EFGs in practice, and in particular it was
used in recent poker AI milestones, where poker AIs beat human poker players
(Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018,
2019b). In fact, RM+ routinely outperforms theoretically-superior methods,
such as optimistic variants of OMD and FTRL (Rakhlin and Sridharan, 2013;
Chiang et al., 2012), which achieve $O\left(1/T\right)$ convergence rates in
the repeated game framework. Despite its very strong empirical performances,
RM+ is only defined when the decision set is the simplex. However, many
problems of the form (1) have convex sets $\mathcal{X},\mathcal{Y}$ that are
not simplexes, e.g., box constraints or norm-balls for distributionally robust
optimization (Ben-Tal et al., 2015). Encouraged by the very strong empirical
performance of RM+ and CFR+, we will construct parameter-free algorithms based
on Blackwell approachability for solving more general instances of the saddle-
point problem (1).

###  1.1 Our Contributions

Our main contributions are as follows.

  * •

Conic Blackwell Algorithm+ (CBA+). We start from the general reduction between
regret minimization over general convex compact sets and Blackwell
approachability (Abernethy et al., 2011). This yields a regret minimizer which
we will refer to as the _conic Blackwell algorithm_ (CBA). Motivated by the
practical performance of RM+ on simplexes, we construct a variant of CBA which
uses a thresholding operation analogous to the one employed by RM+. We call
this regret minimizer CBA+ (Algorithm 1). We show that CBA+ achieves
$O(1/\sqrt{T})$ average regret in the worst-case. A major selling point of
CBA+ is that it does not require any step size choices. Instead, CBA+
implicitly adjusts to the structure of the domains and losses by being
instantiations of a Blackwell approachability algorithm, which is itself
parameter-free.

  * •

Impacts of weights and alternation. As regret minimizers, we show that both
CBA and CBA+ are compatible with increasing weighting schemes, that put more
weights on more recent decisions and payoffs (Theorem 3.1 and Theorem 3.3),
where CBA+ is compatible with different weighting schemes for the decisions
and the payoffs. We then introduce a new algorithm for solving convex-concave
saddle-point problems by using CBA+ in a repeated game framework with linear
weights on the sequence of decisions and uniform weights on the payoffs (this
is known as _linear averaging_ in other algorithms (Tammelin et al., 2015; Gao
et al., 2021)), as well as an alternating payoff scheme. We call this
algorithm SP-CBA+. We quantify the benefits of alternation for solving (1)
(Theorem 3.6), and show the first strict improvement guarantee for using
alternation; note that prior results only showed that it does not slow the
convergence (Burch et al., 2019).

  * •

Efficient implementation of CBA+. We show how to implement CBA and CBA+ when
$\mathcal{X}$ and $\mathcal{Y}$ are simplexes, $\ell_{p}$ balls, and
intersections of the $\ell_{2}$ ball with a simplex, which arises naturally as
a confidence region. More generally, CBA and CBA+ can be implemented when we
can efficiently compute orthogonal projections onto the set $\mathcal{X}$ and
$\mathcal{Y}$. Note that the general reduction of regret minimization and
Blackwell approachability from Abernethy et al. (2011) yields CBA, but does
not yield a practically-implementable algorithm, as the authors do not
consider which decision sets allow for efficient projections.

  * •

Practical performance of SP-CBA+. We highlight the practical efficacy of our
algorithmic framework on several domains. First, we apply SP-CBA+ to two-
player zero-sum matrix games, where the objective function is bilinear, and we
compare with RM+, as well as with AdaHedge and AdaFTRL, two adaptive first-
order algorithms. We then apply SP-CBA+ to extensive-form games (EFGs), where
the RM+ regret minimizer combined with linear averaging, alternation, and a
counterfactual regret (CFR+) minimization scheme, leads to state-of-the-art
practical algorithms (Tammelin et al., 2015; Kroer et al., 2020; Gao et al.,
2021). For EFGs, we find that SP-CBA+ leads to comparable performance in terms
of the iteration complexity, and for some games it slightly outperforms CFR+.
In the simplex setting we also find that SP-CBA+ outperforms both AdaHedge and
AdaFTRL. These results show that SP-CBA+ recovers the strong practical
performance of RM+ and CFR+ in the only setting where these two methods apply.
Second, and more importantly, we show that SP-CBA+ leads to strong practical
performance in settings where RM+ and CFR+ do not apply. We consider instances
of distributionally robust logistic regression and Markov decision processes
(MDPs). For these two instances of saddle-point problems, we find that SP-CBA+
performs orders of magnitude better than online mirror descent and follow-the-
regularized leader, as well as their optimistic variants, when using their
theoretically-correct fixed step sizes. Even when considering tuned step sizes
for the other algorithms, SP-CBA+ performs better, with only a few cases of
comparable performance (at step sizes that lead to divergence for some of the
other non-parameter-free methods). The fast practical performance of our
algorithm, combined with its simplicity and the total lack of step sizes or
parameters tuning, suggests that it should be seriously considered as a
practical approach for solving convex-concave optimization instances in
various settings.

We conclude our introduction with a brief discussion on the average regret
achieved by other methods, and resulting convergence to a saddle point. Our
algorithm SP-CBA+ has a rate of convergence towards a saddle point of
$O(1/\sqrt{T})$, similar to OMD and FTRL. In theory, it is possible to obtain
a faster $O\left(1/T\right)$ rate of convergence when $F$ is differentiable
with Lipschitz gradients, for example via mirror prox (Nemirovski, 2004) or
other primal-dual algorithms (Chambolle and Pock, 2016). However, our
experimental results show that SP-CBA+ is faster than optimistic variants of
FTRL and OMD (Syrgkanis et al., 2015), the latter being almost identical to
the mirror prox algorithm, and both achieving $O(1/T)$ rate of convergence. A
similar conclusion has been drawn in the context of sequential game solving,
where the RM+-based algorithms have better practical performance than the
theoretically-superior $O\left(1/T\right)$-rate methods (Kroer et al., 2020,
2018). In a similar vein, using _error-bound conditions_ , it is possible to
achieve a linear rate, e.g., when solving bilinear saddle-point problems over
polyhedral decision sets, by using the extragradient method (Tseng, 1995) or
optimistic gradient descent-ascent (Wei et al., 2020). However, these linear
rates rely on unknown constants, and may not be indicative of practical
performance.

##  2 Repeated game framework and Blackwell approachability

We will solve (1) using a repeated game framework. There are $T$ iterations
with indices $t=1,\ldots,T$. In this framework, each iteration $t$ consists of
the following steps:

  1. 1.

Each player chooses strategies
$\bm{x}_{t}\in\mathcal{X},\bm{y}_{t}\in\mathcal{Y}$.

  2. 2.

The first player observes
$\bm{f_{t}}\in\partial_{\bm{x}}F(\bm{x}_{t},\bm{y}_{t})$ and uses $\bm{f}_{t}$
when computing the next strategy.

  3. 3.

The second player observes
$\bm{g_{t}}\in\partial_{\bm{y}}F(\bm{x}_{t},\bm{y}_{t})$ and uses $\bm{g}_{t}$
when computing the next strategy.

In the repeated game framework described above, the first player chooses
strategies from $\mathcal{X}$ to minimize the sequence of payoffs in the
repeated game, while the second player chooses strategies from $\mathcal{Y}$
in order to maximize payoffs. The goal of each player is to minimize their
regret $R_{T,\bm{x}},R_{T,\bm{y}}$ across the $T$ iterations:

$\displaystyle
R_{T,\bm{x}}=\sum_{t=1}^{T}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\langle\bm{f}_{t},\bm{x}\rangle,\quad
R_{T,\bm{y}}=\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\langle\bm{g}_{t},\bm{y}\rangle-\sum_{t=1}^{T}\langle\bm{g}_{t},\bm{y}_{t}\rangle.$

The reason this repeated game framework leads to a solution to the SPP problem
(1) is the following well-known theorem (e.g., Theorem 1, Kroer (2020)).
Relying on $F$ being convex-concave and subdifferentiable, it connects the
regret incurred by each player to the duality gap in (1).

######  Theorem 2.1.

Let
$\left(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T}\right)=\dfrac{1}{T}\sum_{t=1}^{T}\left(\bm{x}_{t},\bm{y}_{t}\right)$
for any $\left(\bm{x}_{t}\right)_{t\geq 1},\left(\bm{y}_{t}\right)_{t\geq 1}$.
Then

$\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})\leq(R_{T,\bm{x}}+R_{T,\bm{y}})/T.$

Therefore, when each player uses a regret minimizer that guarantees regret on
the order of $O(\sqrt{T})$,
$\left(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T}\right)_{T\geq 0}$ converges to a
solution to (1) at a rate of $O\left(1/\sqrt{T}\right)$. Later we will show a
generalization of Theorem 2.1 that will allow us to incorporate increasing
averaging schemes that put additional weight on the later iterates. Given the
repeated game framework, the next question becomes which algorithms to employ
in order to minimize regret for each player. As mentioned in Section 1, for
matrix games and EFGs, variants of Blackwell approachability are used in
practice (via the CFR decomposition for EFGs).

#### Blackwell Approachability

In Blackwell approachability, a decision maker repeatedly takes decisions
$\bm{x}_{t}$ from some convex decision set $\mathcal{X}$ (this set plays the
same role as $\mathcal{X}$ or $\mathcal{Y}$ in (1)). After taking decision
$\bm{x}_{t}$ the player observes a vector-valued affine payoff function
$\bm{u}_{t}(\bm{x})\in\mathbb{R}^{n}$. The goal for the decision maker is to
force the average payoff $\frac{1}{T}\sum_{t=1}^{T}\bm{u}_{t}(\bm{x}_{t})$ to
approach some convex target set $\mathcal{S}$. Blackwell proved that a convex
target set $\mathcal{S}$ can be approached if and only if for every halfspace
$\mathcal{H}\supseteq\mathcal{S}$, there exists $\bm{x}\in\mathcal{X}$ such
that for every possible payoff function $\bm{u}(\cdot)$, $\bm{u}(\bm{x})$ is
guaranteed to lie in $\mathcal{H}$. The action $\bm{x}$ is said to _force_
$\mathcal{H}$. Blackwell’s proof is via an algorithm: at iteration $t$, his
algorithm projects the average payoff
$\bar{\bm{u}}_{t}=\frac{1}{t-1}\sum_{\tau=1}^{t-1}\bm{u}_{\tau}(\bm{x}_{\tau})$
onto $\mathcal{S}$, and then the decision maker chooses an action $\bm{x}_{t}$
that forces the tangent halfspace to $\mathcal{S}$ generated by the normal
vector $\bar{\bm{u}}_{t}-\pi_{\mathcal{S}}(\bar{\bm{u}}_{t})$, where
$\pi_{\mathcal{S}}(\bar{\bm{u}}_{t})$ is the orthogonal projection of
$\bar{\bm{u}}_{t}$ onto $\mathcal{S}$. We call this algorithm _Blackwell’s
algorithm_ ; it approaches $\mathcal{S}$ at a rate of $O(1/\sqrt{T})$
(Blackwell, 1956). In particular, for $d(\bar{\bm{u}}_{T},\mathcal{S})$
defined as
$d(\bar{\bm{u}}_{T},\mathcal{S})=\min\\{\|\bar{\bm{u}}_{T}-\bm{z}\|_{2}\;|\bm{z}\in\mathcal{S}\\},$
we have $d(\bar{\bm{u}}_{T},\mathcal{S})=O\left(1/\sqrt{T}\right)$.
Blackwell’s algorithm is really a meta-algorithm, rather than a concrete
algorithm. Even within the context of the Blackwell approachability problem,
one needs to devise a way to compute the forcing actions needed at each
iteration, i.e., to compute $\pi_{\mathcal{S}}(\bar{\bm{u}})$. To the best of
our knowledge, prior to this paper, the only practical implementation of
Blackwell approachability for solving (1) is on the simplex for solving
bilinear saddle-point problems and extensive-form games, which leads to RM and
RM+.

#### Details on Regret Matching

Let $\Delta(n)$ be the $n$-dimensional probability simplex. Regret Matching
(RM) arises by instantiating Blackwell approachability with the decision space
$\mathcal{X}$ equal to $\Delta(n)$, the target set $\mathcal{S}$ equal to the
nonpositive orthant $\mathbb{R}_{-}^{n}$, and the vector-valued payoff
function
$\bm{u}_{t}(\bm{x}_{t})=\bm{f}_{t}-\langle\bm{f}_{t},\bm{x}_{t}\rangle\bm{e}$
equal to the regret associated to each of the $n$ actions (which correspond to
the corners of $\Delta(n)$). Here $\bm{e}\in\mathbb{R}^{n}$ is the all one
vector. Hart and Mas-Colell (2000) showed that with this setup, playing each
action with probability proportional to its positive regret up to time $t$
satisfies the forcing condition needed in Blackwell’s algorithm. Formally,
regret matching (RM) keeps a running sum
$\bm{r}_{t}=\sum_{\tau=1}^{t}\left(\bm{f}_{\tau}-\langle\bm{f}_{\tau},\bm{x}_{\tau}\rangle\bm{e}\right)$,
and then action $i$ is played with probability
$\bm{x}_{t+1,i}=[\bm{r}_{t,i}]^{+}/\sum_{i=1}^{n}[\bm{r}_{t,i}]^{+}$, where
$[\cdot]^{+}$ denotes thresholding at zero. By Blackwell’s approachability
theorem, this algorithm converges to zero average regret at a rate of
$O(1/\sqrt{T})$. In zero-sum game-solving, it was discovered that a variant of
regret matching leads to extremely strong practical performance (but the same
theoretical rate of convergence). In regret matching+ (RM+), the running sum
is thresholded at zero at every iteration:
$\bm{r}_{t}=[\bm{r}_{t-1}+\bm{f}_{t}-\langle\bm{f}_{t},\bm{x}_{t}\rangle\bm{e}]^{+}$,
and then actions are again played proportional to $\bm{r}_{t}$. In the next
section, we describe a framework by Abernethy et al. (2011) for using
Blackwell’s algorithm to construct regret minimizers for more general convex
sets $\mathcal{X}$; this will lead to the CBA algorithm, from which we will
construct CBA+. While we use the framework of Abernethy et al. (2011), we note
that the _Lagrangian Hedging_ framework of Gordon (2007) could also be used as
the basis for developed a general class of Blackwell-approachability-style
algorithms. It would be interesting to construct a CBA+-like algorithm and
efficient projection approaches for such a framework as well.

##  3 Conic Blackwell Algorithm

###  3.1 Our algorithm

In this section we introduce our main regret minimizer, Conic Blackwell
Algorithm Plus (CBA+), which uses a variation of Blackwell’s approachability
procedure (Blackwell, 1956) to perform regret minimization on a general convex
compact decision set $\mathcal{X}$. We will assume that losses are coming from
a bounded set; this occurs, for example, if there exists $L_{x},L_{y}$ (that
we do not need to know), such that

$\|\bm{f}\|\leq L_{x},\|\bm{g}\|\leq
L_{y},\;\forall\;\bm{x}\in\mathcal{X},\bm{y}\in\mathcal{Y},\forall\;\bm{f}\in\partial_{\bm{x}}F(\bm{x},\bm{y}),\forall\;\bm{g}\in\partial_{\bm{y}}F(\bm{x},\bm{y}).$
(4)

We will simply write $L$ for $L_{x}$ or $L_{y}$ when we focus on the regret of
a single player. We will also use the notation
$\kappa=\max_{\bm{x}\in\mathcal{X}}\|\bm{x}\|_{2}$ (recall that $\mathcal{X}$
is compact). CBA+ is best understood as a combination of two steps. The first
is the basic CBA algorithm, derived from Blackwell’s algorithm, which we
describe next. To convert Blackwell’s algorithm to a regret minimizer on
$\mathcal{X}$, we use the reduction from (Abernethy et al., 2011), which
considers the conic hull
$\mathcal{C}=\textrm{cone}(\\{\kappa\\}\times\mathcal{X})\subset\mathbb{R}^{n+1}$.
The Blackwell approachability problem is then instantiated with $\mathcal{X}$
as the decision set, the target set equal to the polar
$\mathcal{C}^{\circ}=\\{\bm{z}:\langle\bm{z},\bm{\hat{z}}\rangle\leq
0,\forall\bm{\hat{z}}\in\mathcal{C}\\}$ of $\mathcal{C}$, and payoff vectors
$(\langle\bm{f},\bm{x}\rangle,-\bm{f})\in\mathbb{R}^{n+1}$. The conic
Blackwell algorithm (CBA) is implemented by computing the projection
$\pi_{\mathcal{C}}(\bm{u})$ of the average payoff vector $\bm{u}$ onto
$\mathcal{C}$, noting that the projection can be written as
$\alpha(\kappa,\bm{x})$ where $\alpha\geq 0$ is a scalar, and playing the
action $\bm{x}$. The second step in CBA+ is to replace the average payoff
vector $\bm{u}$ with a running projected aggregation of the payoffs, where we
always add the newest payoff to the aggregate, and then project the aggregate
onto $\mathcal{C}$.

More concretely, pseudocode for CBA+ is given in Algorithm 1. This pseudocode
relies on two functions: ${\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}:\mathbb{R}^{n+1}\rightarrow\mathbb{R}^{n}$, which
maps the aggregate payoff vector $\bm{u}_{t}$ to a decision in $\mathcal{X}$,
and ${\sf UPDATEPAYOFF}_{{\sf CBA\textsuperscript{+}}}$ which controls how we
aggregate payoffs. Given an aggregate payoff vector
$\bm{u}=(\tilde{u},\hat{\bm{u}})\in\mathbb{R}\times\mathbb{R}^{n}$, we have

${\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}(\bm{u})=(\kappa/\tilde{u})\hat{\bm{u}}.$

If $\tilde{u}=0$, we just let ${\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}(\bm{u})=\bm{x}_{0}$ for some arbitrary
$\bm{x}_{0}\in\mathcal{X}$. The function ${\sf UPDATEPAYOFF}_{{\sf
CBA\textsuperscript{+}}}$ is implemented by adding the most recent payoff to
the aggregate payoffs, and then projecting onto $\mathcal{C}$. More formally,
it is defined as

${\sf UPDATEPAYOFF}_{{\sf
CBA\textsuperscript{+}}}(\bm{u},\bm{x},\bm{f},\omega)=\pi_{\mathcal{C}}\left(\bm{u}+\omega\left(\langle\bm{f},\bm{x}\rangle/\kappa,-\bm{f}\right)\right),$

where $\omega$ is the weight assigned to the most recent payoff. Because of
the projection step in ${\sf UPDATEPAYOFF}_{{\sf CBA\textsuperscript{+}}}$, we
always have $\bm{u}\in\mathcal{C}$, which in turn guarantees that ${\sf
CHOOSEDECISION}_{{\sf CBA\textsuperscript{+}}}(\bm{u})\in\mathcal{X}$, since
$\mathcal{C}=\textrm{cone}(\\{\kappa\\}\times\mathcal{X})$.

Algorithm 1 Conic Blackwell Algorithm Plus (CBA+)

1:Input A convex, compact set $\mathcal{X}\subset\mathbb{R}^{n}$,
$\kappa=\max\\{\|\bm{x}\|_{2}\;|\;\bm{x}\in\mathcal{X}\\}$.

2:Algorithm parameters Weights $\left(\omega_{\tau}\right)_{\tau\geq
1}\in\mathbb{R}^{\mathbb{N}}$.

3:Initialization $t=1$, $\bm{x}_{1}\in\mathcal{X}$.

4:Observe $\bm{f}_{1}$ then set
$\bm{u}_{1}=\omega_{1}\left(\langle\bm{f}_{1},\bm{x}_{1}\rangle/\kappa,-\bm{f}_{1}\right)\in\mathbb{R}\times\mathbb{R}^{n}$.

5:for $t\geq 1$ do

6: Choose $\bm{x}_{t+1}={\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}(\bm{u}_{t})$.

7: Observe the loss $\bm{f}_{t+1}\in\mathbb{R}^{n}$.

8: Update $\bm{u}_{t+1}={\sf UPDATEPAYOFF}_{{\sf
CBA\textsuperscript{+}}}(\bm{u}_{t},\bm{x}_{t+1},\bm{f}_{t+1},\omega_{t+1}).$

9: Increment $t\leftarrow t+1.$

Let us give some intuition on the effect of projection onto $\mathcal{C}$. For
a geometric intuition, it is easier to visualize the dynamics in
$\mathbb{R}^{2}$. Figure 1 illustrates the projection step
$\pi_{\mathcal{C}}(\cdot)$ of ${\sf CBA\textsuperscript{+}}$. At a high level,
from $\bm{u}_{t}$ to $\bm{u}_{t+1}$, an _instantaneous payoff vector_

$\bm{v}_{t+1}=\omega_{t+1}\left(\langle\bm{f}_{t+1},\bm{x}_{t+1}\rangle/\kappa,-\bm{f}_{t+1}\right)$

is first added to $\bm{u}_{t}$, and then the resulting vector
$\bm{u}^{+}_{t}=\bm{u}_{t}+\bm{v}_{t+1}$ is projected onto $\mathcal{C}$. The
projection $\pi_{\mathcal{C}}(\cdot)$ moves the vector $\bm{u}^{+}_{t}$ along
the edges of the cone $\mathcal{C}^{\circ}$, preserving the (orthogonal)
distance $d$ to $\mathcal{C}^{\circ}$. Intuitively, from a game-theoretic
perspective in the usual case where $\mathcal{C}=\mathbb{R}^{2}_{+}$, the
projection eliminates the negative components of the payoffs, meaning that we
do not remember “negative regrets.”

Figure 1: Illustration of $\pi_{\mathcal{C}}(\cdot)$ for
$\mathcal{C}=\mathbb{R}_{+}^{2}$ (left-hand side) and $\mathcal{C}$ any cone
in $\mathbb{R}^{2}$ (right-hand side).

Let us also note the difference between CBA+ and the algorithm introduced in
Abernethy et al. (2011), which we have called CBA. CBA uses different
UPDATEPAYOFF and CHOOSEDECISION functions. In CBA the payoff update is defined
as

${\sf UPDATEPAYOFF}_{{\sf
CBA}}(\bm{u},\bm{x},\bm{f},\omega)=\bm{u}+\omega\left(\langle\bm{f},\bm{x}\rangle/\kappa,-\bm{f}\right).$

Note in particular the lack of projection as compared to CBA+, this is
analogous to the difference between RM and RM+. The ${\sf
CHOOSEDECISION}_{{\sf CBA}}$ function then requires a projection onto
$\mathcal{C}$:

${\sf CHOOSEDECISION}_{{\sf CBA}}(\bm{u})={\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}\left(\pi_{\mathcal{C}}(\bm{u})\right).$

Based upon the analysis in Blackwell (1956), Abernethy et al. (2011) show that
CBA with uniform weights (both on payoffs and decisions) guarantees
$O(1/\sqrt{T})$ average regret.

###  3.2 Regret bounds for CBA and CBA+

In this section we investigate the theoretical performance guarantees of CBA
and CBA+ when we vary the weights on decisions and payoffs. This is motivated
by practical performance, where it has been observed in several other settings
that increasing weights usually perform better (Gao et al., 2021; Tammelin et
al., 2015; Brown and Sandholm, 2019a), and that _alternating_ update schemes
are helpful (Tammelin et al., 2015; Kroer, 2020). First, we show that CBA and
CBA+ are both compatible with varying weights $\left(\omega_{t}\right)_{t\geq
1}$, when those weights are used on both decisions and payoffs. Second, we
show that CBA+ is compatible with different weights
$\left(\omega_{t}\right)_{t\geq 1}$ on payoffs and weights
$\left(\theta{t}\right)_{t\geq 1}$ on decisions.

We start with the following theorem, which shows that CBA with weights on both
decisions and payoffs is a no-regret algorithm. This generalizes the result of
(Abernethy et al., 2011), which shows that CBA works for uniform weights.

######  Theorem 3.1.

Let $\left(\bm{x}_{t}\right)_{t\geq 1}$ be the sequence of decisions generated
by CBA with payoff weights $\left(\omega_{t}\right)_{t\geq 1}$ and let
$S_{t}=\sum_{\tau=1}^{t}\omega_{\tau}$ for any $t\geq 1$. Then

$\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle=O\left(\kappa\cdot
d(\bm{u}_{T},\mathcal{C}^{\circ})\right).$

Additionally,

$d(\bm{u}_{T},\mathcal{C}^{\circ})=O\left(L\cdot\sqrt{\sum_{t=1}^{T}\omega_{t}^{2}}\right).$

Overall, the average regret is such that

$\dfrac{\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle}{S_{T}}\leq\sqrt{2}\kappa
L\frac{\sqrt{\sum_{t=1}^{T}\omega_{t}^{2}}}{\sum_{t=1}^{T}\omega_{t}}.$

The proof of Theorem 3.1 uses the following facts from conic optimization.
Several of these are direct consequences of Moreau’s decomposition theorem. We
provide proofs of all statements in Lemma 3.2 in Appendix A.

######  Lemma 3.2.

Let $\mathcal{C}\subset\mathbb{R}^{n+1}$ be a closed convex cone and
$\mathcal{C}^{\circ}$ its polar.

  1. 1.

If $\bm{u}\in\mathbb{R}^{n+1}$, then
$\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})=\pi_{\mathcal{C}}(\bm{u})$,
$\langle\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u}),\pi_{\mathcal{C}^{\circ}}(\bm{u})\rangle=0,$
and $\|\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})\|_{2}\leq\|\bm{u}\|_{2}$.

  2. 2.

If $\bm{u}\in\mathbb{R}^{n+1}$ then

$d(\bm{u},\mathcal{C})=\max_{\bm{w}\in\mathcal{C}^{\circ}\cap
B_{2}(1)}\langle\bm{u},\bm{w}\rangle,$

where $B_{2}(1)=\\{\bm{w}\in\mathbb{R}^{n+1}\;|\;\|\bm{w}\|_{2}\leq 1\\}$.

  3. 3.

If $\bm{u}\in\mathcal{C}$, then
$d(\bm{u},\mathcal{C}^{\circ})=\|\bm{u}\|_{2}$.

  4. 4.

Assume that $\mathcal{C}=\textrm{cone}(\\{\kappa\\}\times\mathcal{X})$ with
$\mathcal{X}\subset\mathbb{R}^{n}$ convex compact and
$\kappa=\max_{\bm{x}\in\mathcal{X}}\|\bm{x}\|_{2}$. Then $\mathcal{C}^{\circ}$
is a closed convex cone. Additionally, if $\bm{u}\in\mathcal{C}$ we have
$-\bm{u}\in\mathcal{C}^{\circ}$.

  5. 5.

Let us write $\leq_{\mathcal{C}^{\circ}}$ for the ordering induced by
$\mathcal{C}^{\circ}:\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y}\iff\bm{y}-\bm{x}\in\mathcal{C}^{\circ}$.
Then

$\displaystyle\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y},\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}^{\prime}$
$\displaystyle\Rightarrow\bm{x}+\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}+\bm{y}^{\prime},$
$\displaystyle\forall\;\bm{x},\bm{x}^{\prime},\bm{y},\bm{y}^{\prime}\in\mathbb{R}^{n+1},$
(5) $\displaystyle\bm{x}+\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}$
$\displaystyle\Rightarrow\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y},$
$\displaystyle\forall\;\bm{x},\bm{y}\in\mathbb{R}^{n+1},\forall\;\bm{x}^{\prime}\in\mathcal{C}^{\circ},$
(6)

  6. 6.

Assume that $\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y}$ for
$\bm{x},\bm{y}\in\mathbb{R}^{n+1}$. Then
$d(\bm{y},\mathcal{C}^{\circ})\leq\|\bm{x}\|_{2}$.

We are now ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

The proof proceeds in two steps. We start by proving

$\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle=O\left(\kappa\cdot
d(\bm{u}_{T},\mathcal{C}^{\circ})\right).$

We have

$\displaystyle d(\bm{u}_{T},\mathcal{C}^{\circ})$
$\displaystyle=\max_{\bm{w}\in\textrm{cone}(\\{\kappa\\}\times\mathcal{X})\bigcap
B_{2}(1)}\langle\sum_{t=1}^{T}\omega_{t}\bm{v}_{t},\bm{w}\rangle$ (7)
$\displaystyle\geq\max_{\bm{x}\in\mathcal{X}}\langle\sum_{t=1}^{T}\omega_{t}\bm{v}_{t},\dfrac{(\kappa,\bm{x})}{\|(\kappa,\bm{x})\|_{2}}\rangle$
$\displaystyle\geq\max_{\bm{x}\in\mathcal{X}}\dfrac{\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle}{\|(\kappa,\bm{x})\|_{2}},$
(8)

where (7) follows from Statement 2 in Lemma 3.2, and (8) follows from CBA
maintaining

$\bm{u}_{t}=\left(\sum_{\tau=1}^{t}\omega_{\tau}\frac{\langle\bm{f}_{\tau},\bm{x}_{\tau}\rangle}{\kappa},-\sum_{\tau=1}^{t}\omega_{\tau}\bm{f}_{\tau}\right),\forall\;t\geq
1.$

Since $\|(\kappa,\bm{x})\|_{2}\leq\sqrt{2}\kappa$, we can conclude that

$\sqrt{2}\kappa
d(\bm{u}_{T},\mathcal{C}^{\circ})\geq\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle.$

We now prove that

$d(\bm{u}_{T},\mathcal{C}^{\circ})\leq
L\sqrt{\sum_{\tau=1}^{T}\omega_{\tau}^{2}}.$

We have

$\displaystyle d(\bm{u}_{t+1},\mathcal{C}^{\circ})^{2}$
$\displaystyle=\min_{\bm{z}\in\mathcal{C}^{\circ}}\|\bm{u}_{t+1}-\bm{z}\|_{2}^{2}$
$\displaystyle\leq\|\bm{u}_{t+1}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t})\|_{2}^{2}$
$\displaystyle\leq\|\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t})\|_{2}^{2}$
$\displaystyle\leq\|\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t})\|_{2}^{2}+\omega_{t+1}^{2}\|\bm{v}_{t+1}\|_{2}^{2}$
$\displaystyle+2\omega_{t+1}\langle\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t}),\bm{v}_{t+1}\rangle$
$\displaystyle\leq\|\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t})\|_{2}^{2}+\omega_{t+1}^{2}\|\bm{v}_{t+1}\|_{2}^{2},$
(9)

where (9) follows from

$\langle\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t}),\bm{v}_{t+1}\rangle=0.$
(10)

This is one of the crucial components of Blackwell’s approachability
framework: the current decision is chosen to force the next payoff to lie in
the hyperplane generated by projecting the aggregate payoffs onto the target
set. To see this, first note that
$\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u})=\pi_{\mathcal{C}}(\bm{u}_{t})$.
Let us write
$\bm{\pi}=\left(\tilde{\pi},\hat{\bm{\pi}}\right)=\pi_{\mathcal{C}}(\bm{u}_{t})$.
Note that by definition, $\bm{x}_{t+1}=(\kappa/\tilde{\pi})\hat{\bm{\pi}}$,
and
$\bm{v}_{t+1}=\left(\langle\bm{f}_{t+1},\bm{x}_{t+1}\rangle/\kappa,-\bm{f}_{t+1}\right)$.
Therefore,

$\displaystyle\langle\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t}),\bm{v}_{t+1}\rangle$
$\displaystyle=\langle\bm{\pi},\bm{v}_{t+1}\rangle$
$\displaystyle=\langle\left(\tilde{\pi},\hat{\bm{\pi}}\right),\left(\langle\bm{f}_{t+1},\bm{x}_{t+1}\rangle/\kappa,-\bm{f}_{t+1}\right)\rangle$
$\displaystyle=\langle\left(\tilde{\pi},\hat{\bm{\pi}}\right),\left(\langle\bm{f}_{t+1},(\kappa/\tilde{\pi})\hat{\bm{\pi}}\rangle/\kappa,-\bm{f}_{t+1}\right)\rangle$
$\displaystyle=\langle\hat{\bm{\pi}},\bm{f}_{t+1}\rangle-\langle\hat{\bm{\pi}},\bm{f}_{t+1}\rangle$
$\displaystyle=0.$

Next, recall that
$d(\bm{u}_{t},\mathcal{C}^{\circ})^{2}=\|\bm{u}_{t}-\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t})\|_{2}^{2}$.
Applying (9) inductively we obtain

$d(\bm{u}_{t},\mathcal{C}^{\circ})^{2}\leq\sum_{\tau=1}^{t}\omega_{\tau}^{2}\|\bm{v}_{\tau}\|_{2}^{2}\leq
L^{2}\cdot\sum_{\tau=1}^{t}\omega_{\tau}^{2},$

where the last inequality follows from the definition of $\bm{v}_{t}$ and $L$.
∎

In the next theorem, we show a result that may seem surprising: CBA+ allows us
to use two separate and different weighting schemes for the decisions in the
regret definition and the aggregate payoffs. This result is analogous to the
fact that for the simplex case, RM+ is compatible with polynomial averaging
schemes on the decision while using constant weights on the aggregate payoffs
(Tammelin et al., 2015; Brown and Sandholm, 2019a).

######  Theorem 3.3.

Consider $\left(\bm{x}_{t}\right)_{t\geq 1}$ generated by CBA+ with aggregate
payoff weights $\left(\omega_{t}\right)_{t\geq 1}$, when regret is measured
using decision weights $\left(\theta_{t}\right)_{t\geq 1}$, and
$S_{T}=\sum_{t=1}^{T}\theta_{t}$. Assume that
$\frac{\theta_{t+1}}{\theta_{t}}\geq\frac{\omega_{t+1}}{\omega_{t}},\forall\;t\geq
1$. Then

$\dfrac{\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}\rangle}{S_{T}}\leq\sqrt{2}\kappa
L\frac{\theta_{T}}{\omega_{T}}\frac{\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}}{\sum_{t=1}^{T}\theta_{t}}.$

Our proof heavily relies on the sequence of payoffs belonging to the cone
$\mathcal{C}$ at every iteration ($\bm{u}_{t}\in\mathcal{C},\forall\;t\geq
1$), and for this reason it does not extend to CBA. We also note that the use
of conic optimization somewhat simplifies the argument compared to the proof
that RM+ is compatible with polynomial averaging on decisions and uniform
weights on payoffs.

###### Proof of Theorem 3.3.

Recall that
$\bm{v}_{t}=\left(\langle\bm{f}_{t},\bm{x}_{t}\rangle/\kappa,-\bm{f}_{t}\rangle\right)$.
By construction and following the same argument as for the proof of Theorem
3.1, we have

$\displaystyle\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}\rangle\leq\sqrt{2}\kappa\cdot
d\left(\sum_{t=1}^{T}\theta_{t}\bm{v}_{t},\mathcal{C}^{\circ}\right).$ (11)

Additionally, we always have

$\omega_{t+1}\bm{v}_{t+1}\geq_{\mathcal{C}^{\circ}}\bm{u}_{t+1}-\bm{u}_{t}.$
(12)

This is because

$\displaystyle\omega_{t+1}\bm{v}_{t+1}-\bm{u}_{t+1}+\bm{u}_{t}$
$\displaystyle=\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}-\bm{u}_{t+1}$
$\displaystyle=\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}-\pi_{\mathcal{C}}\left(\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\right)$
$\displaystyle=\pi_{\mathcal{C}^{\circ}}\left(\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\right)\in\mathcal{C}^{\circ}.$

Therefore, multiplying (12) by $\theta_{t+1}$ and dividing by $\omega_{t+1}$,
we obtain

$\theta_{t+1}\bm{v}_{t+1}\geq_{\mathcal{C}^{\circ}}\frac{\theta_{t+1}}{\omega_{t+1}}(\bm{u}_{t+1}-\bm{u}_{t}).$

Reformulating the right-hand side we obtain

$\theta_{t+1}\bm{v}_{t+1}\geq_{\mathcal{C}^{\circ}}\frac{\theta_{t+1}}{\omega_{t+1}}\bm{u}_{t+1}-\frac{\theta_{t}}{\omega_{t}}\bm{u}_{t}-\left(\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\right)\bm{u}_{t}.$

Summing up the previous inequalities from $t=1$ to $t=T-1$ and using
$\bm{u}_{1}=\bm{v}_{1}$ we obtain

$\sum_{t=1}^{T}\theta_{t}\bm{v}_{t}\geq_{\mathcal{C}^{\circ}}\frac{\theta_{T}}{\omega_{T}}\bm{u}_{T}-\sum_{t=1}^{T-1}\left(\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\right)\bm{u}_{t}.$

Note that
$\sum_{t=1}^{T-1}\left(\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\right)\bm{u}_{t}\in\mathcal{C}$,
because $\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\geq
0$. Therefore, Statement 4 in Lemma 3.2 shows that
$-\sum_{t=1}^{T-1}\left(\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\right)\bm{u}_{t}\in\mathcal{C}^{\circ}$.
Now, by applying (6) in Statement 5 of Lemma 3.2, we have

$\sum_{t=1}^{T}\theta_{t}\bm{v}_{t}\geq_{\mathcal{C}^{\circ}}\frac{\theta_{T}}{\omega_{T}}\bm{u}_{T}-\sum_{t=1}^{T-1}\left(\frac{\theta_{t+1}}{\omega_{t+1}}-\frac{\theta_{t}}{\omega_{t}}\right)\bm{u}_{t}\Rightarrow\sum_{t=1}^{T}\theta_{t}\bm{v}_{t}\geq_{\mathcal{C}^{\circ}}\frac{\theta_{T}}{\omega_{T}}\bm{u}_{T}.$

Since $\frac{\theta_{T}}{\omega_{T}}\bm{u}_{T}\in\mathcal{C}$, Statement 6
shows that

$\displaystyle
d\left(\sum_{t=1}^{T}\theta_{t}\bm{v}_{t},\mathcal{C}^{\circ}\right)\leq\bigg{\|}\frac{\theta_{T}}{\omega_{T}}\bm{u}_{T}\bigg{\|}_{2}.$
(13)

By construction $\bm{u}_{T}$ is the sequence of aggregated payoffs generated
by CBA+ with weights $\left(\omega_{t}\right)_{t\geq 1}$. We now show that
$d(\bm{u}_{T},\mathcal{C}^{\circ})=\|\bm{u}_{T}\|_{2}=O\left(L\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}\right)$.
We have

$\displaystyle\|\bm{u}_{t+1}\|_{2}^{2}$
$\displaystyle=\|\pi_{\mathcal{C}}\left(\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\right)\|_{2}^{2}$
$\displaystyle\leq\|\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\|_{2}^{2}$ (14)

where (14) follows from Statement 1 in Lemma 3.2. Therefore,

$\displaystyle\|\bm{u}_{t+1}\|_{2}^{2}$
$\displaystyle\leq\|\bm{u}_{t}\|^{2}_{2}+\omega_{t+1}^{2}\|\bm{v}_{t+1}\|^{2}_{2}+2\omega_{t+1}\langle\bm{u}_{t},\bm{v}_{t+1}\rangle.$

By construction and for the same reason as for (10),
$\langle\bm{u}_{t},\bm{v}_{t+1}\rangle=0$. Therefore, we have the recursion

$\|\bm{u}_{t+1}\|_{2}^{2}\leq\|\bm{u}_{t}\|^{2}_{2}+\omega_{t+1}^{2}\|\bm{v}_{t+1}\|^{2}_{2}.$

By telescoping the inequality above we obtain

$\|\bm{u}_{t}\|_{2}^{2}\leq\sum_{\tau=1}^{t}\omega_{\tau}^{2}\|\bm{v}_{\tau}\|^{2}_{2}.$

By definition of $L$, we conclude that

$\|\bm{u}_{T}\|_{2}\leq L\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}.$

Therefore, by (13),
$d(\sum_{t=1}^{T}\theta_{t}\bm{v}_{t},\mathcal{C}^{\circ})\leq
L\frac{\theta_{T}}{\omega_{T}}\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}.$ This shows
that

$\dfrac{\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t}\langle\bm{f}_{t},\bm{x}\rangle}{S_{T}}\leq\sqrt{2}\kappa
L\frac{\theta_{T}}{\omega_{T}}\frac{\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}}{\sum_{t=1}^{T}\theta_{t}}.$

∎

###  3.3 Convergence bounds for saddle-point problems

In this section, we show how the regret bounds from the previous section
translate into convergence rates for solving convex-concave saddle-point
problems in the repeated game framework. In particular, the following theorem
gives the convergence rate of CBA+ and CBA for solving saddle-point problems
of the form (1), based on our bounds on the regret of each player under
various weighting schemes. The proof is in Appendix B.

######  Theorem 3.4.

Let $L=\max\\{L_{x},L_{y}\\}$ defined in (4) and
$\kappa=\max\\{\max\\{\|\bm{x}\|_{2},\|\bm{y}\|_{2}\\}\;|\;\bm{x}\in\mathcal{X},\bm{y}\in\mathcal{Y}\\}$.

  1. 1.

Let
$\left(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T}\right)=\sum_{t=1}^{T}\omega_{t}\left(\bm{x}_{t},\bm{y}_{t}\right)/S_{T},$
where $\left(\bm{x}_{t}\right)_{t\geq 1},\left(\bm{y}_{t}\right)_{t\geq 1}$
are generated by the repeated game framework with CBA with weights
$\left(\omega_{\tau}\right)_{t\geq 1}$ on both decisions and payoffs and
$S_{T}=\sum_{t=1}^{T}\omega_{t}$. Assume that $\omega_{t}=t^{p},\forall t\geq
1$. Then

$\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})=O\left(\frac{\kappa
L\sqrt{p+1}}{\sqrt{T}}\right).$

  2. 2.

Let $p,q\in\mathbb{N}$ with $q\geq p$. Let
$\left(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T}\right)=\sum_{t=1}^{T}\theta_{t}\left(\bm{x}_{t},\bm{y}_{t}\right)/S_{T},$
where $\left(\bm{x}_{t}\right)_{t\geq 1},\left(\bm{y}_{t}\right)_{t\geq 1}$
are generated by the repeated game framework with CBA+ with aggregate payoff
weights $\left(\omega_{t}\right)_{t\geq 1}$, and decision weights
$\left(\theta_{t}\right)_{t\geq 1}$ and $S_{T}=\sum_{t=1}^{T}\theta_{t}$.
Assume that $\theta_{t}=t^{q},\omega_{t}=t^{p},\forall t\geq 1$. Then

$\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})=O\left(\frac{\kappa
L(q+1)}{\sqrt{p+1}\sqrt{T}}\right).$

We note that larger weights lead to slightly worse worst-case convergence
guarantees. In contrast to this, we will see in our numerical simulations that
the strongest empirical performances for CBA+ are obtained for $q=1,p=0$,
i.e., linear weights on the decisions and uniform weights on the payoffs.

Let us compare our bounds with the regret bounds of classical first-order
methods. We consider $p,q=0$. CBA and CBA+ achieve $O\left(\kappa
L/\sqrt{T}\right)$ average regret, whereas online mirror descent (OMD)
(Nemirovski and Yudin, 1983; Ben-Tal and Nemirovski, 2001) and follow-the-
regularized-leader (FTRL) (Abernethy et al., 2009; McMahan, 2011) achieve
$O\left(\Omega L/\sqrt{T}\right)$ average regret, where
$\Omega=\max\\{\|\bm{x}-\bm{x}^{\prime}\|_{2}\rvert\bm{x},\bm{x}^{\prime}\in\mathcal{X}\\}.$
We can always recenter $\mathcal{X}$ to contain $\bm{0}$, in which case the
bounds for OMD/FTRL and CBA+ are equivalent since $\kappa\leq\Omega\leq
2\kappa$. The bound on the average regret for _optimistic_ OMD (OOMD, Chiang
et al. (2012)) and _optimistic_ FTRL (OFTRL, Rakhlin and Sridharan (2013)) is
$O\left(\Omega^{2}L/T\right)$ in the repeated game framework, a priori better
than the bound for CBA+ as regards the number of iterations $T$. Nonetheless,
we will see in Section 5 that the empirical performance of CBA+ is better than
that of $O(1/T)$ methods. A similar situation occurs for RM+ compared to OOMD
and OFTRL for solving extensive-form games such as poker (Farina et al.,
2019b; Kroer et al., 2020).

###  3.4 Improved convergence bounds using alternation

Alternation is a simple variation of the repeated game framework from Section
2. Alternation is known to lead to significant speedup for RM+ (Tammelin et
al., 2015), and we will observe in our simulations (Section 5) that this holds
for CBA+ as well. In the repeated game framework with alternation, at
iteration $t$, the second player is provided with the decision $\bm{x}_{t}$ of
the first player for iteration $t$. Because alternation is defined the same
way for both CBA and CBA+, we omit the subscripts in CHOOSEDECISION and
UPDATEPAYOFF. In particular, at iteration $t$ of the repeated game framework
with alternation, the players choose $\bm{x}_{t}$ and $\bm{y}_{t}$ as follows:

  1. 1.

Both players start with aggregate payoffs $\bm{u}^{x}_{t-1},\bm{u}^{y}_{t-1}$.

  2. 2.

The first player chooses a decision $\bm{x}_{t}$ based on $\bm{u}^{x}_{t-1}$:

$\bm{x}_{t}={\sf CHOOSEDECISION}(\bm{u}^{x}_{t-1}).$

  3. 3.

For $\bm{g}_{t-1}=\partial_{y}F(\bm{x}_{t},\bm{y}_{t-1})$, the second player
updates its aggregate payoff:

$\bm{u}^{y}_{t}={\sf
UPDATEPAYOFF}\left(\bm{u}_{t-1}^{y},\bm{y}_{t-1},\bm{g}_{t-1},\omega_{t}\right).$

  4. 4.

The second player chooses a decision $\bm{y}_{t}$ based on $\bm{u}^{y}_{t}$:

$\bm{y}_{t}={\sf CHOOSEDECISION}(\bm{u}^{y}_{t}).$

  5. 5.

For $\bm{f}_{t}=\partial_{x}F(\bm{x}_{t},\bm{y}_{t})$, the first player
updates its aggregate payoff:

$\bm{u}^{x}_{t}={\sf
UPDATEPAYOFF}\left(\bm{u}_{t-1}^{x},\bm{x}_{t},\bm{f}_{t},\omega_{t}\right).$

Recall that we use the repeated game framework to solve (1) because we can
bound the duality gap by the sum of the average regrets of each player using
Theorem 2.1. It is known that in the repeated game framework with alternation,
it is possible to construct decisions such that Theorem 2.1 fails to hold,
because of the mismatch in the sequences of decisions of the players (Farina
et al., 2019a). That said, it was later shown that a modified version of
Theorem 2.1 holds (Burch et al., 2019). Here we state a more general version
of that result, which was first shown in a set of lecture notes (Kroer, 2020).
In particular, the following bound holds on the duality gap. For the sake of
completeness, we provide the proof in Appendix C.

######  Theorem 3.5.

Consider some weights $\left(\theta_{t}\right)_{t\geq 1}$ and
$S_{T}=\sum_{t=1}^{T}\theta_{t+1}$. Let
$\left(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T}\right)=\sum_{t=1}^{T}\theta_{t+1}\left(\bm{x}_{t+1},\bm{y}_{t}\right)/S_{T},$
where $\left(\bm{x}_{t}\right)_{t\geq 1},\left(\bm{y}_{t}\right)_{t\geq 1}$
are generated by the repeated game framework with alternation. Then

$\displaystyle\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})$
$\displaystyle\leq\frac{1}{S_{T}}\left(\max_{\bm{y}\in\mathcal{Y}}\theta_{t+1}\sum_{t=1}^{T}\langle\bm{g}_{t},\bm{y}\rangle-\sum_{t=1}^{T}\theta_{t+1}\langle\bm{g}_{t},\bm{y}_{t}\rangle\right)$
$\displaystyle+\frac{1}{S_{T}}\left(\sum_{t=1}^{T}\theta_{t+1}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}\langle\bm{f}_{t},\bm{x}\rangle\right)$
$\displaystyle+\frac{1}{S_{T}}\left(\sum_{t=1}^{T}\theta_{t+1}\left(F(\bm{x}_{t+1},\bm{y}_{t})-F(\bm{x}_{t},\bm{y}_{t})\right)\right).$

From Theorem 3.5, we see that alternation guarantees convergence to a solution
of (1), if

$\sum_{t=1}^{t+1}\theta_{t+1}\left(F(\bm{x}_{t+1},\bm{y}_{t})-F(\bm{x}_{t},\bm{y}_{t})\right)\leq
0.$ (15)

In the framework of RM and RM+, we have
$\mathcal{X}=\Delta(n),\mathcal{Y}=\Delta(m)$ and the objective function is
bilinear. In this case, it is shown in Burch et al. (2019) that (15) holds. In
particular, for any $t\in[T]$, it holds that
$F(\bm{x}_{t+1},\bm{y}_{t})-F(\bm{x}_{t},\bm{y}_{t})\leq 0$. We provide the
following stronger result for CBA+ in the case of an objective function $F$
that is linear in one of the two variables, with any convex compact decision
sets $\mathcal{X}$ and $\mathcal{Y}$. The proof is presented in Appendix D.

######  Theorem 3.6.

Assume that $\left(\bm{x},\bm{y}\right)\mapsto F\left(\bm{x},\bm{y}\right)$ is
linear in $\bm{x}$.

  1. 1.

In the framework of Theorem 3.5, suppose that $\left(\bm{x}_{t}\right)_{t\geq
1},\left(\bm{y}_{t}\right)_{t\geq 1}$ are generated by CBA+ with weights
$\left(\omega_{t}\right)_{t\geq 1}$ on the payoffs. We have, for $t\geq 1$,

$F(\bm{x}_{t+1},\bm{y}_{t})-F(\bm{x}_{t},\bm{y}_{t})\leq-\frac{\kappa}{\omega_{t}\cdot\|\bm{u}_{t}^{x}\|_{\infty}}\|\bm{u}_{t}^{x}-\bm{u}_{t-1}^{x}\|_{2}^{2}.$

  2. 2.

In the framework of Theorem 3.5, suppose that $\left(\bm{x}_{t}\right)_{t\geq
1},\left(\bm{y}_{t}\right)_{t\geq 1}$ are generated by CBA with weights
$\left(\omega_{t}\right)_{t\geq 1}$ on the payoffs. We have, for $t\geq 1$,

$F(\bm{x}_{t+1},\bm{y}_{t})-F(\bm{x}_{t},\bm{y}_{t})\leq-\frac{\kappa}{\omega_{t}\cdot\|\pi_{\mathcal{C}}\left(\bm{u}_{t}^{x}\right)\|_{\infty}}\|\pi_{\mathcal{C}}\left(\bm{u}_{t}^{x}\right)-\pi_{\mathcal{C}}\left(\bm{u}_{t-1}^{x}\right)\|_{2}^{2}.$

Note that our results in Theorem 3.6 for CBA and CBA+ improve upon the
analogous results for RM and RM+ (Burch et al., 2019), because Theorem 3.6
guarantees a strict improvement from alternation, where (Burch et al., 2019)
only show that it does not hurt. Secondly, their result is for the case of a
bilinear objective function, whereas we only require linearity in one of the
variables. Our assumption that the objective function is linear in one of the
decision variable is satisfied for many important decision problems, e.g.,
markov decision processes, distributionally robust logistic regression, and
matrix games, as we will see in our simulations in Section 5.

##  4 Efficient implementations of CBA

We now turn to efficiently implementing CBA and CBA+. The main bottleneck of
both CBA+ and CBA is to efficiently compute $\pi_{\mathcal{C}}(\bm{u})$, the
orthogonal projection of a vector $\bm{u}$ on the cone
$\mathcal{C}=\textrm{cone}(\\{\kappa\\}\times\mathcal{X})$:

$\pi_{\mathcal{C}}(\bm{u})\in\arg\min_{\bm{y}\in\mathcal{C}}\|\bm{y}-\bm{u}\|_{2}^{2}.$
(16)

Note that this issue is not discussed in Abernethy et al. (2011), which do not
provide an efficient implementation of CBA. In this section, we show how to
efficiently solve (16) for many important decision sets $\mathcal{X}$. One of
the critical components of our proofs is Moreau’s Decomposition Theorem
(Combettes and Reyes, 2013) (Statement 1 in Lemma 3.2), which states that
$\pi_{\mathcal{C}}(\bm{u})$ can be recovered from
$\pi_{\mathcal{C}^{\circ}}(\bm{u})$ and vice versa, because for any convex
cone $\mathcal{C}$, we have
$\pi_{\mathcal{C}}(\bm{u})+\pi_{\mathcal{C}^{\circ}}(\bm{u})=\bm{u}.$ All the
proofs for this section are presented in Appendices E.

###  4.1 Simplex

Assume that $\mathcal{X}=\Delta(n)$. This setting is standard for matrix
games. It is also used for extensive-form games, because CFR decomposes regret
minimization over the tree-like decision space into a set of local regret
minimizations over simplexes (Zinkevich et al., 2007). In the game setting,
$n$ is the number of actions of a player and $\bm{x}\in\Delta(n)$ represents a
randomized strategy. When $\mathcal{X}=\Delta(n)$, we show that
$\pi_{\mathcal{C}^{\circ}}(\bm{u})$ can be computed in $O(n\log(n))$ using a
sorting trick similar to that for the standard simplex projection, and
therefore $\pi_{\mathcal{C}}(\bm{u})$ can be computed in
$O\left(n\log(n)\right)$ using Moreau’s decomposition. In particular, we
provide the following closed-form expression for the polar cone
$\mathcal{C}^{\circ}$.

######  Lemma 4.1.

Let $\mathcal{C}=\textrm{cone}\left(\\{1\\}\times\Delta(n)\right)$. Then
$\mathcal{C}^{\circ}=\\{\left(\tilde{y},\hat{\bm{y}}\right)\in\mathbb{R}^{n+1}\;|\;\max_{i\in[n]}\hat{y}_{i}\leq-\tilde{y}\\}.$

Therefore, computing $\pi_{\mathcal{C}^{\circ}}(\bm{u})$ is equivalent to
solving

$\min\\{(\tilde{y}-\tilde{u})^{2}+\|\hat{\bm{y}}-\hat{\bm{u}}\|_{2}^{2}\;|\;(\tilde{y},\hat{\bm{y}})\in\mathbb{R}^{n+1},\max_{i\in[n]}\hat{y}_{i}\leq-\tilde{y}\\}.$
(17)

We prove the following proposition in Appendix E.

######  Proposition 4.2.

Let $\mathcal{X}=\Delta(n)$. An optimal solution
$\pi_{\mathcal{C}^{\circ}}(\bm{u})$ to (17) can be computed in $O(n\log(n))$
arithmetic operations. Therefore, $\pi_{\mathcal{C}}(\bm{u})$ can be computed
in $O\left(n\log(n)\right)$ arithmetic operations.

###  4.2 $\ell_{p}$ balls

For $p\geq 1$ and $p=\infty$, we consider the $\ell_{p}$ balls
$\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}\|_{p}\leq 1\\}$. This
type of decision set appears in many problems in optimization, including
robust optimization (Ben-Tal et al., 2015), distributionally robust logistic
regression (Namkoong and Duchi, 2016), $\ell_{\infty}$ regression (Sidford and
Tian, 2018) and saddle-point reformulation of Markov Decision Processes (Jin
and Sidford, 2020). We first reformulate the cones $\mathcal{C}$ and
$\mathcal{C}^{\circ}$. Recall that
$\kappa=\max\\{\|\bm{x}\|_{2}\;|\;\bm{x}\in\mathcal{X}\\}$.

######  Lemma 4.3.

Let $\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}\|_{p}\leq 1\\},$ with
$p\geq 1$ or $p=\infty$. Let $q\in\mathbb{R}\bigcup\\{+\infty\\}$ be such that
$1/p+1/q=1$. Then

$\displaystyle\mathcal{C}$
$\displaystyle=\\{(\tilde{y},\bm{y})\in\mathbb{R}\times\mathbb{R}^{n}\;|\;\|\bm{y}\|_{p}\leq\tilde{y}/\kappa\\},$
$\displaystyle\mathcal{C}^{\circ}$
$\displaystyle=\\{(\tilde{y},\bm{y})\in\mathbb{R}\times\mathbb{R}^{n}\;|\;\|\bm{y}\|_{q}\leq-\kappa\tilde{y}\\}.$

Based on Lemma 4.3, we can prove the following propositions.

######  Proposition 4.4.

Let $\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}\|_{p}\leq 1\\}$ for
$p\in\\{1,\infty\\}$. Then $\pi_{\mathcal{C}}(\bm{u})$ can be computed in
$O\left(n\log(n)\right)$ operations.

######  Proposition 4.5.

Let $\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}\|_{2}\leq 1\\}.$ Then
$\pi_{\mathcal{C}}(\bm{u})$ can be computed in $O\left(n\right)$ operations.

###  4.3 Ellipsoidal confidence region in the simplex

Here, $\mathcal{X}$ is an ellipsoidal subregion of the simplex, defined as
$\mathcal{X}=\\{\bm{x}\in\Delta(n)\;|\;\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}\\}$.
This type of decision set is widely used because it is associated with
confidence regions when estimating a probability distribution from observed
data (Iyengar, 2005; Bertsimas et al., 2019). It can also be used in the
Bellman update for robust Markov Decision Processes (Iyengar, 2005; Wiesemann
et al., 2013; Goyal and Grand-Clément, 2018). We also assume that the
confidence region is “entirely contained in the simplex”:
$\\{\bm{x}\in\mathbb{R}^{n}|\bm{x}^{\top}\bm{e}=1\\}\bigcap\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}\\}\subseteq\Delta(n)$,
to avoid degenerate components. In this case, using a change of basis we show
that it is possible to compute $\pi_{\mathcal{C}}(\bm{u})$ in closed-form,
i.e., in $O(n)$ arithmetic operations.

######  Proposition 4.6.

Let
$\mathcal{X}=\\{\bm{x}\in\Delta(n)\;|\;\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}\\}$
and assume that
$\\{\bm{x}\in\mathbb{R}^{n}|\bm{x}^{\top}\bm{e}=1\\}\bigcap\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}\\}\subseteq\Delta(n)$.
Then $\pi_{\mathcal{C}}(\bm{u})$ can be computed in $O\left(n\right)$
arithmetic operations.

###  4.4 Other decision sets via bisection

In the case where we can not find an exact solution of
$\pi_{\mathcal{C}}(\bm{u})$ or $\pi_{\mathcal{C}^{\circ}}(\bm{u})$, it is
possible to resort to bisection to obtain an approximate solutions. In
particular, $\pi_{\mathcal{C}}(\bm{u})$ is the solution to the following
optimization program:

$\min\\{(\alpha\kappa-\tilde{u})^{2}+\|\alpha\bm{x}-\hat{\bm{u}}\|_{2}^{2}\;|\;\alpha\geq
0,\bm{x}\in\mathcal{X}\\}.$ (18)

If we fix $\alpha>0$, then an optimal $\bm{x}(\alpha)$ is a solution to

$\min\\{\|\bm{x}-\hat{\bm{u}}/\alpha\|_{2}^{2}\;|\;\bm{x}\in\mathcal{X}\\}.$
(19)

Therefore, if we can efficiently compute orthogonal projections on the set
$\mathcal{X}$, it is possible to perform bisection on $\alpha$ to compute an
$\epsilon$-approximation of $\pi_{\mathcal{C}}(\bm{u})$ in
$O\left(\log(\epsilon^{-1})\right)$ iterations, i.e., solving (19) only
$O\left(\log(\epsilon^{-1})\right)$ times.

##  5 Numerical experiments

In this section we compare the performances of SP-CBA+ on real and synthetic
instances of classical saddle-point problems. We focus on bilinear matrix
games, extensive-form games, distributionally robust logistic regression, and
Markov decision processes (MDPs). Recall that we have defined SP-CBA+ by
combining the repeated game framework from Section 2 with CBA+ as a regret
minimizer, along with uniform weights on the payoffs, linear weights on the
decisions and the alternating updates from Section 3.4. We start by examining
the performance of SP-CBA+ on matrix and extensive-form games; for these games
the RM+ algorithm is already known to perform extremely well empirically, and
the goal of these experiments is to see whether SP-CBA+ retains that very
strong empirical performance. The experiments on distributionally robust
logistic regression and MDPs then show the performance on new domains where no
Blackwell-based algorithms were known prior to this paper.

###  5.1 Matrix games

Matrix games are saddle-point problems with a bilinear objective function and
simplexes as decision sets:

$\min_{\bm{x}\in\Delta(n)}\max_{\bm{y}\in\Delta(m)}\langle\bm{x},\bm{Ay}\rangle$
(20)

where $\bm{A}\in\mathbb{R}^{n\times m}$ is the matrix of payoffs of the game.
We can view (20) as a zero-sum game between the first player and the second
player, where the coefficient $A_{ij}\in\mathbb{R}$ represents payoff obtained
by the second player when the first player chooses action $i$ and the second
player chooses action $j$.

#### Experimental setup

We generate 100 synthetic matrices $\bm{A}$ of size $\mathbb{R}^{n\times m}$
with $(n,m)=(100,50)$. Similarly as in Chambolle and Pock (2016); Nesterov
(2005), for the coefficients of $\bm{A}$ we consider a uniform distribution in
$[0,1]$ or a normal distribution of mean $0$ and variance $1$. We compare SP-
CBA+ with RM+, which is known to achieve the best empirical performance
compared to a wide range of algorithms, including Hedge and other first-order
methods (Kroer, 2020; Kroer et al., 2018; Farina et al., 2019b). We also
compare with two other scale-free and parameter-free no-regret algorithms,
AdaHedge (De Rooij et al., 2014) and AdaFTRL (Orabona and Pál, 2015), with the
$\ell_{2}$ norm as the Bregman divergence. Similarly as for SP-CBA+, for RM+
we use the repeated game framework with alternation, along with linear
averaging on the decisions and uniform averaging on the payoffs. In Figures
2-3, we compare the performance of the four algorithms (SP-CBA+, RM+, AdaHedge
and AdaFTRL) for solving (20). In Figure 2(a) and Figure 2(b), we let the four
algorithms run for $T=1000$ iterations, and we show the duality gap of the
current running average as a function of the number of iterations. This shows
the progress made by the algorithms toward solving (20) at each iteration. In
Figure 3(a) and Figure 3(b), we run the four algorithms for time-max = 10
seconds, and we show the duality gap as a function of the time of computation.
We average all the results over 50 randomly generated instances. Note that
both axis are in logarithmic scale.

#### Results and discussion

When we compare the duality gap as a function of the number of iterations
(Figure 2(a) and Figure 2(b)), we note that SP-CBA+ performs on par with RM+,
and both algorithms vastly outperform AdaHedge and AdaFTRL. However, each
iteration of SP-CBA+ on the simplex requires solving $O\left(n\log(n)\right)$
arithmetic operations (see Section 4.1), whereas each iteration of RM+ can be
performed in $O(n)$ operations. Therefore, when we compare the duality gap as
a function of the computation time (Figure 3(a) and Figure 3(b)), we note that
RM+ outperforms SP-CBA+, even though after roughly ten seconds of computation,
the performances of SP-CBA+ and RM+ are equivalent.

(a) Uniform

(b) Normal

Figure 2: Comparison of SP-CBA+, RM+, AdaHedge and AdaFTRL on instances of
matrix games, with respect to the number of iterations. The payoffs are chosen
randomly, with uniform distribution in Figure 2(a) and normal distribution in
Figures 2(b).

(a) Uniform

(b) Normal

Figure 3: Comparison of SP-CBA+, RM+, AdaHedge and AdaFTRL on instances of
matrix games, with respect to computation time. The payoffs are chosen
randomly, with uniform distribution in Figure 3(a), and normal distribution in
Figure 3(b).

###  5.2 Extensive-form games

Extensive-form games (EFGs, (von Stengel, 1996; Zinkevich et al., 2007)) are
used to model sequential games with imperfect information. For example, they
were used for superhuman poker AIs in games such as Texas hold’em (Tammelin et
al., 2015; Brown and Sandholm, 2018, 2019b; Moravčík et al., 2017). EFGs can
be written as saddle-point problems, with a bilinear objective functions and
polytopes $\mathcal{X},\mathcal{Y}$ encoding the players’ decision spaces (von
Stengel, 1996). Based on the counterfactual regret minimization (CFR)
framework (Zinkevich et al., 2007), EFGs can be solved via decomposition into
a set of simplex-based regret minimization problems. We point the reader to
(Farina et al., 2019a, c) for more details.

#### Experimental setup

For solving EFGs, we combine the CFR decomposition with CBA+ as a regret
minimizer on the simplex. For the sake of simplicity, we will still call the
resulting algorithm SP-CBA+ (since we use alternation and linear averaging on
the decisions), even though the algorithm relies on the CFR decomposition for
EFGs (which is not necessary for solving the other saddle-point instances from
Section 5.1, Section 5.3 and Section 5.4). We compare SP-CBA+ with CFR+
(Bowling et al., 2015), the algorithm with the strongest empirical performance
for solving EFGs. Note that both SP-CBA+ and CFR+ guarantee a $O(1/\sqrt{T})$
rate of convergence to a Nash equilibrium. We compare SP-CBA+ and CFR+ on
several Leduc poker benchmark instances, a search game, and sheriff; we refer
to (Farina et al., 2021) for details about the instances. Similarly as in
Section 5.1, we compare the progress of SP-CBA+ and CFR+ both as a function of
computation time and number of iterations in the repeated game framework. We
run the algorithms for time-max = 100 seconds and $T=1500$ iterations; note
that we choose time-max and $T$ larger for EFGs than for matrix games because
the EFG instances are way larger than the matrix games from Section 5.1.

#### Results and discussion

If we only consider the duality gap as a function of the number of iterations
(Figure 5), SP-CBA+ performs on par with CFR+, and significantly outperforms
CFR+ on some EFGs instances (Figure 4(a) and Figure 4(b)). However, when we
consider the progress made by each algorithm during time-max = 100 seconds
(Figure 5), CFR+ enjoys better numerical performances than SP-CBA+. This is
because the updates are closed-form in CFR+, whereas each update of SP-CBA+
requires to solve an equation, a situation similar as for matrix games over
the simplex (Section 5.2). It is interesting to note that for EFGs, the
difference in per-iteration computation time has a bigger impact than for
matrix games; it is possible that this is due to our python-based
implementation of SP-CBA+. Better implementations of SP-CBA+ for EFGs could
potentially lead to better results. To conclude this section, we note that
CFR+ enjoys the best empirical performances for solving EFGs, and it is not
concerning that SP-CBA+ can not outperform CFR+ on EFGs (in terms of
computation time). Instead, we will see in the next section how SP-CBA+
carries over these very strong empirical results to saddle-point instances
where CFR+ does not apply and where SP-CBA+ can be implemented more
efficiently.

(a) Search game (4 turns)

(b) Battleship (3 turns)

(c) Leduc, 2pl. 3 ranks

(d) Leduc, 2pl. 5 ranks

Figure 4: Comparison of SP-CBA+ and CFR+ for solving extensive-form games, as
regards the number of iterations.

(a) Search game (4 turns)

(b) Battleship (3 turns)

(c) Leduc, 2pl. 3 ranks

(d) Leduc, 2pl. 5 ranks

Figure 5: Comparison of SP-CBA+ and CFR+ for solving extensive-form games,
based on the computation time.

###  5.3 Distributionally robust logistic regression

Distributionally robust optimization exploits knowledge of the statistical
properties of the model parameters to obtain risk-averse optimal solutions
(Rahimian and Mehrotra, 2019). We focus on the following instance of
distributionally robust logistic regression (Namkoong and Duchi, 2016; Ben-Tal
et al., 2015). There are $m$ observed feature-label pairs
$\left(\bm{a}_{i},b_{i}\right)\in\mathbb{R}^{n}\times\\{-1,1\\}$, and we want
to solve

$\min_{\bm{x}\in\mathbb{R}^{n},\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}}\max_{\bm{y}\in\Delta(m),\|\bm{y}-\bm{y}_{0}\|_{2}\leq\epsilon_{y}}\sum_{i=1}^{m}y_{i}\ell_{i}(\bm{x})+\frac{\mu}{2}\|\bm{x}\|_{2}^{2}$
(21)

where $\ell_{i}(\bm{x})=\log(1+\exp(-b_{i}\bm{a}^{\top}_{i}\bm{x}))$ and
$\mu\geq 0$. The formulation (21) takes a worst-case approach to put more
weight on misclassified observations and provides some statistical guarantees,
e.g., it can be seen as a convex regularization of standard empirical risk
minimization instances (Duchi et al., 2021).

#### Experimental setup

We compare SP-CBA+ with four classical first-order methods (FOMs): Online
Mirror Descent (OMD), Optimistic OMD (O-OMD), Follow-The-Regularized-Leader
(FTRL) and Optimistic FTRL (O-FTRL). We provide a detailed presentation of our
implementations of these algorithms and our experimental setting in Appendix
F; we use the $\ell_{2}$ norm as the Bregman divergence. We compare the
performances of these algorithms with SP-CBA+ on two synthetic datasets and
two real data sets. We use parameters
$\bm{x}_{0}=\left(1,...,1\right)/n,\epsilon_{x}=10,\bm{y}_{0}=\left(1,...,1\right)/m,\epsilon_{y}=1/2m,\mu=0.1$
in (21), and we initialize all algorithms at $\bm{x}_{0},\bm{y}_{0}$. For the
synthetic classification instances, we generate a vector
$\bm{x}^{*}\in\mathbb{R}^{n}$, we sample some vectors
$\bm{a}_{i}\in\mathbb{R}^{n}$ at random for $i\in\\{1,...,m\\}$, set labels
$b_{i}=\text{sign}(\bm{a}^{\top}_{i}\bm{x}^{*})$, and then we flip $10\%$ of
the labels. We consider two types of synthetic instances: one where $a_{ij}$
is sampled from a uniform distribution in $[0,1]$, and one where $a_{ij}$ is
sampled from a normal distribution with mean $0$ and variance $1$. For the
real classification instances, we use the following datasets from the libsvm
website222https://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets/: adult
and splice.

One of the main motivations for SP-CBA+ is to obtain a parameter-free
algorithm. In contrast, the other FOMs considered in this section require
choosing step sizes $\eta_{t}$ at every iteration $t$. This is a major
limitation in practice: if the step sizes are too small, the iterates may be
very conservative, while the algorithms may diverge with very large step
sizes. We will compare the performances of the FOMs for both the fixed,
theoretically-correct step sizes, and for tuned step sizes. The computation of
the theoretically-correct step sizes is presented in Appendix F.3. To tune the
FOMs, we run them for the first $10$ iterations, with step sizes
$\eta_{t}=\alpha/\sqrt{t+1}$ for OMD and FTRL and step size $\eta_{t}=\alpha$
for O-OMD and O-FTRL, and we search for the best
$\alpha\in\\{0.01,0.1,1,10,100\\}$. We then choose the value of $\alpha$ that
lead to the smallest duality gap after $10$ iterations, and use this value for
the remaining $T=1000$ iterations. Note that the tuning time and iterations
(where the first $10$ iterations are repeated with various values of $\alpha$)
are counted in the total computation time and number of iterations of the
FOMs. We acknowledge that this tuning method is only one possibility and that
the multiplicative factor $\alpha$ could be chosen in many different ways.
However, any other tuning framework would still be resource-demanding and
uncertain. In contrast, SP-CBA+ does not require any tuning, and, as we will
see, outperforms even the tuned FOMs. Finally, on the $y$-axis we only report
the worst-case loss of the current average $\bar{\bm{x}}_{T}$; in particular,
we do not compute the duality gap at every iteration, because for a fixed
value of $\bm{y}$, computing the optimal $\bm{x}$ requires solving a
(regularized) nominal logistic regression, which would be computationally
intensive to do at every iteration.

#### Proximal updates for the first-order methods

Note that in (21), SP-CBA+ is instantiated on an $\ell_{2}$ ball (for the
first player) and the intersection of an $\ell_{2}$ ball and the simplex (for
the second player). As shown in Section 4.2 and Section 4.3, this leads to
closed-form updates for SP-CBA+ at every iteration. In contrast, OMD, FTRL,
O-OMD, and O-FTRL require binary searches for the decision of the second
player at each iteration, see Appendix F. The functions used in the binary
searches themselves require solving an optimization program (an orthogonal
projection onto the simplex) at each evaluation. Even though computing the
orthogonal projection of a vector onto the simplex of size $m$ can be done in
$O(m\log(m))$, this results in slower overall running time, compared to SP-
CBA+ with closed-form updates at each iteration. The situation is even worse
for O-OMD, which requires two proximal updates at each iteration.

#### Results and discussion

In Figure 6, we show the progress of all algorithms toward solving (21) as a
function of the number of iterations, when the theoretical step sizes are used
for the FOMs. We notice that all FOMs are progressing very slowly toward an
optimal solution. This is because the theoretical step sizes are very small,
relying on upper bounds on the Lipschitz constants of the objective function
of (21). In contrast, SP-CBA+ quickly converges to an optimal solution, even
though we see in Figure 6(a) that during the first few iterations, SP-CBA+ may
increase the objective function. In Figure 7, we tune the FOMs for the first
$10$ iterations, before running them (with the tuned step sizes). We note that
depending on the datasets, the tuned FOMs may perform very well (e.g., OMD in
Figure 7(a), all FOMS in Figure 7(b), O-OMD in Figure 7(c)), but may also fail
to converge to an optimal solution, even after very good performances during
the first iterations (e.g., O-FTRL in Figure 7(c)). This is because the
convergence guarantees of the FOMs may fail to hold, for large choices of the
multiplicative factor $\alpha$. In Figure 8 and Figure 9, we present the same
experiments but where we record the computation time on the $x$-axis. Recall
that the per-iteration computation time of SP-CBA+ is shorter than for the
FOMs, because SP-CBA+ has closed-form updates in this setting. Therefore, we
still observe in Figures 8-9 that SP-CBA+ outperforms the classical FOMs.

(a) Uniform

(b) Normal

(c) Australian

(d) Splice

Figure 6: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a solution
to the distributionally robust logistic regression problem (21), based on the
number of iterations. The theoretical choices of step sizes are used in the
first-order methods.

(a) Uniform

(b) Normal

(c) Australian

(d) Splice

Figure 7: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a solution
to the distributionally robust logistic regression problem (21), based on the
number of iterations. The tuned step sizes are used in the first-order
methods.

(a) Uniform

(b) Normal

(c) Australian

(d) Splice

Figure 8: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a solution
to the distributionally robust logistic regression problem (21), based on the
computation time. The theoretical choices of step sizes are used in the first-
order methods.

(a) Uniform

(b) Normal

(c) Australian

(d) Splice

Figure 9: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a solution
to the distributionally robust logistic regression problem (21), based on the
computation time. The tuned step sizes are used in the first-order methods.

###  5.4 Markov decision processes

Markov Decision Processes (MDPs) are used as a modeling tool for sequential
decision-making problems (Puterman, 1994), and have found applications in game
learning (Mnih et al., 2013) and healthcare (Grand-Clément et al., 2020;
Alagoz et al., 2010; Steimle and Denton, 2017). In a finite MDP, the set of
states is $[n]$ and there are $A$ actions. For each state-action pair $(s,a)$,
there is an associated instantaneous reward $r_{sa}$ as well as a distribution
$\bm{P}_{sa}\in\Delta(n)$ over the possible next states in $[n]$. We write
$r_{\infty}=\max_{s,a}r_{sa}$ and we assume, without loss of generality, that
$r_{sa}\geq 0,\forall\;(s,a)\in[n]\times[A]$. Given a discount factor
$\lambda\in(0,1)$ and an initial probability distribution
$\bm{p}_{0}\in\Delta(n)$, the goal of the decision-making is to maximize the
infinite-horizon discounted cumulated reward. This leads to the following
linear programming formulation (Puterman, 1994):

$\min\\{(1-\lambda)\bm{p}_{0}^{\top}\bm{v}\;|\;v_{s}\geq
r_{sa}+\lambda\bm{P}_{sa}^{\top}\bm{v},\forall\;(s,a)\in[n]\times[A]\\}$

which can be rewritten as a saddle-point problem (Jin and Sidford, 2020):

$\min_{\bm{v}\in\mathbb{R}^{n},\|\bm{v}\|_{2}\leq\sqrt{n}r_{\infty}/(1-\lambda)}\max_{\mu\in\Delta(n\times
A)}\;(1-\lambda)\bm{p}_{0}^{\top}\bm{v}+\sum_{s=1}^{n}\sum_{a=1}^{A}\mu_{sa}\left(r_{sa}+\lambda\bm{P}_{sa}^{\top}\bm{v}-v_{s}\right),$
(22)

where we add the constraint $\|\bm{v}\|_{2}\leq\sqrt{n}r_{\infty}/(1-\lambda)$
because CBA+ requires a bounded decision set $\mathcal{X}$; this is a valid
constraint for the optimal solution $\bm{v}^{*}\in\mathbb{R}^{n}$ to the MDP
problem, because $\bm{v}^{*}$ satisfies $0\leq v^{*}_{s}\leq
r_{\infty}/(1-\lambda),\forall\;s\in[n]$.

#### Experimental setup

We test the performances of SP-CBA+ for solving (22) on random Garnet MDPs
(Generalized Average Reward Non-stationary Environment Test-bench, (Archibald
et al., 1995; Bhatnagar et al., 2007)), a class of random MDP instances widely
used for benchmarking sequential decision-making algorithms. Garnet MDPs are
parametrized by a branching factor $n_{b}$, which represents the proportion of
reachable next states from each state-action pair $(s,a)$. We choose
$S=100,A=50,n_{b}=50\%,\lambda=0.95$. We average the performances of our
algorithm over 10 random instances of Garnet MDPs, where the reward parameters
are drawn at random uniformly in $[0,10]$. We compare SP-CBA+ with the same
first-order methods as in the previous section: OMD, FTRL, and their
optimistic variants, with the same tuning method. The computation of the upper
bounds $L_{v}$ and $L_{\mu}$ are detailed in Appendix G. We acknowledge that
at the scale of the instances considered in this paper, MDPs can be solved
efficiently using policy iteration. This algorithm is specialized to solving
MDPs and differs greatly from SP-CBA+ which is based on the repeated game
framework; for this reason, we compare SP-CBA+ with first-order methods that
are widely applicable and that have been developed for larger MDP instances,
e.g. online mirror descent for MDPs (Jin and Sidford, 2020).

#### Results and discussion

Similarly as in the two previous section, we note that SP-CBA+ outperforms
OMD, FTRL, as well as the optimistic variants, even after they are tuned. We
note that in our tuning method, choosing the best step sizes after observing
the first 10 iterations may lead to algorithms that choose step sizes that are
too large and algorithms that fail to converge, such as O-OMD in Figures
11(a)-11(b). Also, we note in Figure 11(b) that tuning the FOMs may require a
lot of computation time. In contrast, SP-CBA+ does not need to be tuned and
all the computation time in SP-CBA+ is used to make progress toward solving
(22).

(a) Number of iterations

(b) Computation time

Figure 10: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a
solution to the MDP problem (22). The theoretical choices of step sizes are
used in the first-order methods.

(a) Number of iterations

(b) Computation time

Figure 11: Comparisons of CBA+, OMD, FTRL, OOMD and OFTRL to compute a
solution to the MDP problem (22). The tuned step sizes are used in the first-
order methods.

##  6 Conclusion

We have proposed SP-CBA+, an algorithm based on Blackwell approachability for
solving classical instances of saddle-point optimization. Our algorithm is 1)
simple to implement for many practical decision sets, 2) completely parameter-
free and does not attempt to learn any step sizes, and 3) competitive with, or
even better than, state-of-the-art approaches with both theoretical and tuned
parameters. Interesting future directions of research include designing
efficient implementations for other widespread decision sets (e.g., based on
Kullback-Leibler divergence or $\phi$-divergence), extending SP-CBA+ to
unbounded decision sets, and developing novel accelerated versions based on
strong convex-concavity or optimism.

## References

  * Abernethy et al. [2011] Jacob Abernethy, Peter L Bartlett, and Elad Hazan.  Blackwell approachability and no-regret learning are equivalent.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pages 27–46. JMLR Workshop and Conference Proceedings, 2011.
  * Abernethy et al. [2009] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin.  Competing in the dark: An efficient algorithm for bandit linear optimization.  2009\.
  * Alagoz et al. [2010] Oguzhan Alagoz, Heather Hsu, Andrew J Schaefer, and Mark S Roberts.  Markov decision processes: a tool for sequential decision making under uncertainty.  _Medical Decision Making_ , 30(4):474–483, 2010\.
  * Archibald et al. [1995] TW Archibald, KIM McKinnon, and LC Thomas.  On the generation of Markov decision processes.  _Journal of the Operational Research Society_ , 46(3):354–361, 1995.
  * Aumann et al. [1995] Robert J Aumann, Michael Maschler, and Richard E Stearns.  _Repeated games with incomplete information_.  MIT press, 1995.
  * Beck and Teboulle [2003] Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3):167–175, 2003.
  * Ben-Tal and Nemirovski [2001] Aharon Ben-Tal and Arkadi Nemirovski.  _Lectures on modern convex optimization: analysis, algorithms, and engineering applications_ , volume 2.  Siam, 2001.
  * Ben-Tal et al. [2015] Aharon Ben-Tal, Elad Hazan, Tomer Koren, and Shie Mannor.  Oracle-based robust optimization via online learning.  _Operations Research_ , 63(3):628–638, 2015.
  * Bertsimas et al. [2019] Dimitris Bertsimas, Dick den Hertog, and Jean Pauphilet.  Probabilistic guarantees in robust optimization.  2019\.
  * Bhatnagar et al. [2007] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee.  Naturalgradient actor-critic algorithms.  _Automatica_ , 2007.
  * Blackwell [1956] David Blackwell.  An analog of the minimax theorem for vector payoffs.  _Pacific Journal of Mathematics_ , 6(1):1–8, 1956\.
  * Bowling et al. [2015] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin.  Heads-up limit hold’em poker is solved.  _Science_ , 347(6218):145–149, 2015.
  * Brown and Sandholm [2018] Noam Brown and Tuomas Sandholm.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374):418–424, 2018.
  * Brown and Sandholm [2019a] Noam Brown and Tuomas Sandholm.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1829–1836, 2019a.
  * Brown and Sandholm [2019b] Noam Brown and Tuomas Sandholm.  Superhuman AI for multiplayer poker.  _Science_ , 365(6456):885–890, 2019b.
  * Burch et al. [2019] Neil Burch, Matej Moravčík, and Martin Schmid.  Revisiting CFR+ and alternating updates.  _Journal of Artificial Intelligence Research_ , 64:429–443, 2019.
  * Chambolle and Pock [2011] Antonin Chambolle and Thomas Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  _Journal of mathematical imaging and vision_ , 40(1):120–145, 2011.
  * Chambolle and Pock [2016] Antonin Chambolle and Thomas Pock.  On the ergodic convergence rates of a first-order primal–dual algorithm.  _Mathematical Programming_ , 159(1-2):253–287, 2016.
  * Chiang et al. [2012] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu.  Online optimization with gradual variations.  In _Conference on Learning Theory_ , pages 6–1. JMLR Workshop and Conference Proceedings, 2012.
  * Chzhen et al. [2021] Evgenii Chzhen, Christophe Giraud, and Gilles Stoltz.  A unified approach to fair online learning via Blackwell approachability.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Combettes and Reyes [2013] Patrick L Combettes and Noli N Reyes.  Moreau’s decomposition in Banach spaces.  _Mathematical Programming_ , 139(1):103–114, 2013\.
  * De Rooij et al. [2014] Steven De Rooij, Tim Van Erven, Peter D Grünwald, and Wouter M Koolen.  Follow the leader if you can, hedge if you must.  _The Journal of Machine Learning Research_ , 15(1):1281–1316, 2014.
  * Duchi et al. [2008] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra.  Efficient projections onto the $\ell_{1}$ ball for learning in high dimensions.  In _Proceedings of the 25th international conference on Machine learning_ , pages 272–279, 2008.
  * Duchi et al. [2021] John C Duchi, Peter W Glynn, and Hongseok Namkoong.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 2021.
  * Egozcue et al. [2003] Juan José Egozcue, Vera Pawlowsky-Glahn, Glòria Mateu-Figueras, and Carles Barcelo-Vidal.  Isometric logratio transformations for compositional data analysis.  _Mathematical Geology_ , 35(3):279–300, 2003\.
  * Farina et al. [2019a] Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Online convex optimization for sequential decision processes and extensive-form games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1917–1925, 2019a.
  * Farina et al. [2019b] Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Optimistic regret minimization for extensive-form games via dilated distance-generating functions.  In _Advances in Neural Information Processing Systems_ , pages 5222–5232, 2019b.
  * Farina et al. [2019c] Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Regret circuits: Composability of regret minimizers.  In _International Conference on Machine Learning_ , pages 1863–1872, 2019c.
  * Farina et al. [2021] Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent.  In _Proceedings of the AAAI Conference on Artificial Intelligence_. AAAI, 2021.
  * Gao et al. [2021] Yuan Gao, Christian Kroer, and Donald Goldfarb.  Increasing iterate averaging for solving saddle-point problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7537–7544, 2021.
  * Gordon [2007] Geoffrey J Gordon.  No-regret algorithms for online convex programs.  In _Advances in Neural Information Processing Systems_ , pages 489–496. Citeseer, 2007.
  * Goyal and Grand-Clément [2018] Vineet Goyal and Julien Grand-Clément.  Robust Markov decision process: Beyond rectangularity.  _arXiv preprint arXiv:1811.00215_ , 2018.
  * Grand-Clément and Kroer [2020] Julien Grand-Clément and Christian Kroer.  First-order methods for Wasserstein distributionally robust MDP.  _arXiv preprint arXiv:2009.06790_ , 2020.
  * Grand-Clément and Kroer [2021a] Julien Grand-Clément and Christian Kroer.  Scalable first-order methods for robust MDPs.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(13):12086–12094, May 2021a.
  * Grand-Clément and Kroer [2021b] Julien Grand-Clément and Christian Kroer.  Conic Blackwell Algorithm: Parameter-free convex-concave saddle-point solving.  _Advances in Neural Information Processing Systems_ , 34, 2021b.
  * Grand-Clément et al. [2020] Julien Grand-Clément, Carri W Chan, Vineet Goyal, and Gabriel Escobar.  Robust policies for proactive ICU transfers.  _arXiv preprint arXiv:2002.06247_ , 2020.
  * Hart and Mas-Colell [2000] Sergiu Hart and Andreu Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Iyengar [2005] Garud Iyengar.  Robust dynamic programming.  _Mathematics of Operations Research_ , 30(2):257–280, 2005.
  * Jin and Sidford [2020] Yujia Jin and Aaron Sidford.  Efficiently solving MDPs with stochastic mirror descent.  In _International Conference on Machine Learning_ , pages 4890–4900. PMLR, 2020.
  * Kroer [2020] Christian Kroer.  IEOR8100: Economics, AI, and optimization lecture note 5: Computing Nash equilibrium via regret minimization.  2020\.
  * Kroer et al. [2018] Christian Kroer, Gabriele Farina, and Tuomas Sandholm.  Solving large sequential games with the excessive gap technique.  In _Advances in Neural Information Processing Systems_ , pages 864–874, 2018.
  * Kroer et al. [2020] Christian Kroer, Kevin Waugh, Fatma Kılınç-Karzan, and Tuomas Sandholm.  Faster algorithms for extensive-form game solving via improved smoothing functions.  _Mathematical Programming_ , pages 1–33, 2020.
  * Kroer et al. [2021] Christian Kroer, Alexander Peysakhovich, Eric Sodomka, and Nicolas E Stier-Moses.  Computing large market equilibria using abstractions.  _Operations Research_ , 2021.
  * McMahan [2011] Brendan McMahan.  Follow-the-regularized-leader and mirror descent: Equivalence theorems and $l_{1}$ regularization.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 525–533. JMLR Workshop and Conference Proceedings, 2011.
  * Milman [2006] Emanuel Milman.  Approachable sets of vector payoffs in stochastic games.  _Games and Economic Behavior_ , 56(1):135–147, 2006.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Moravčík et al. [2017] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  _Science_ , 356(6337):508–513, 2017.
  * Namkoong and Duchi [2016] Hongseok Namkoong and John C Duchi.  Stochastic gradient methods for distributionally robust optimization with f-divergences.  In _NIPS_ , volume 29, pages 2208–2216, 2016.
  * Nemirovski [2004] Arkadi Nemirovski.  Prox-method with rate of convergence ${O}(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  _SIAM Journal on Optimization_ , 15(1):229–251, 2004.
  * Nemirovski and Yudin [1983] Arkadi Nemirovski and David Yudin.  _Problem complexity and method efficiency in optimization._ 1983\.
  * Nesterov [2005] Yu Nesterov.  Smooth minimization of non-smooth functions.  _Mathematical programming_ , 103(1):127–152, 2005\.
  * Niazadeh et al. [2020] Rad Niazadeh, Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru.  Online learning via offline greedy: Applications in market design and optimization.  2020\.
  * Orabona and Pál [2015] Francesco Orabona and Dávid Pál.  Scale-free algorithms for online linear optimization.  In _International Conference on Algorithmic Learning Theory_ , pages 287–301. Springer, 2015.
  * Perchet [2010] Vianney Perchet.  _Approachability, Calibration and Regret in Games with Partial Observations_.  PhD thesis, PhD thesis, Université Pierre et Marie Curie, 2010.
  * Puterman [1994] M.L. Puterman.  _Markov Decision Processes : Discrete Stochastic Dynamic Programming_.  John Wiley and Sons, 1994.
  * Rahimian and Mehrotra [2019] Hamed Rahimian and Sanjay Mehrotra.  Distributionally robust optimization: A review.  _arXiv preprint arXiv:1908.05659_ , 2019.
  * Rakhlin and Sridharan [2013] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In _Conference on Learning Theory_ , pages 993–1019. PMLR, 2013.
  * Sidford and Tian [2018] Aaron Sidford and Kevin Tian.  Coordinate methods for accelerating $l_{\infty}$ regression and faster approximate maximum flow.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 922–933. IEEE, 2018.
  * Steimle and Denton [2017] Lauren N Steimle and Brian T Denton.  Markov decision processes for screening and treatment of chronic diseases.  In _Markov Decision Processes in Practice_ , pages 189–222. Springer, 2017.
  * Syrgkanis et al. [2015] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire.  Fast convergence of regularized learning in games.  28, 2015.
  * Tammelin et al. [2015] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling.  Solving heads-up limit Texas hold’em.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * Tseng [1995] Paul Tseng.  On linear convergence of iterative methods for the variational inequality problem.  _Journal of Computational and Applied Mathematics_ , 60(1-2):237–252, 1995.
  * von Stengel [1996] Bernhard von Stengel.  Efficient computation of behavior strategies.  _Games and Economic Behavior_ , 14(2):220–246, 1996.
  * Wei et al. [2020] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo.  Linear last-iterate convergence in constrained saddle-point optimization.  In _International Conference on Learning Representations_ , 2020.
  * Wiesemann et al. [2013] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem.  Robust markov decision processes.  _Mathematics of Operations Research_ , 38(1):153–183, 2013.
  * Zinkevich et al. [2007] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.  Regret minimization in games with incomplete information.  In _Advances in neural information processing systems_ , pages 1729–1736, 2007.

##  Appendix A Proof of Lemma 3.2

###### Proof of Lemma 3.2.

  1. 1.

The fact that
$\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})=\pi_{\mathcal{C}}(\bm{u})\in\mathcal{C}$,$\langle\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u}),\pi_{\mathcal{C}^{\circ}}(\bm{u})\rangle=0$
follows from Moreau’s Decomposition Theorem (Combettes and Reyes, 2013). The
fact that $\|\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})\|_{2}\leq\|\bm{u}\|_{2}$
is a straightforward consequence of
$\langle\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u}),\pi_{\mathcal{C}^{\circ}}(\bm{u})\rangle=0$.

  2. 2.

For any $\bm{w}\in\mathcal{C}^{\circ}\cap B_{2}(1)$ we have

$\langle\bm{u},\bm{w}\rangle\leq\langle\bm{u}-\pi_{\mathcal{C}}(\bm{u}),\bm{w}\rangle\leq\|\bm{w}\|_{2}\|\bm{u}-\pi_{\mathcal{C}}(\bm{u})\|_{2}\leq\|\bm{u}-\pi_{\mathcal{C}}(\bm{u})\|_{2}.$

Conversely, since
$\left(\bm{u}-\pi_{\mathcal{C}}(\bm{u})\right)/\|\bm{u}-\pi_{\mathcal{C}}(\bm{u})\|_{2}\in\mathcal{C}^{\circ}$,
we have

$\max_{\bm{w}\in\mathcal{C}^{\circ}\cap
B_{2}(1)}\langle\bm{u},\bm{w}\rangle\geq\|\bm{u}-\pi_{\mathcal{C}}(\bm{u})\|_{2}.$

This shows that

$\max_{\bm{w}\in\mathcal{C}^{\circ}\cap
B_{2}(1)}\langle\bm{u},\bm{w}\rangle=\|\bm{u}-\pi_{\mathcal{C}}(\bm{u})\|_{2}=d(\bm{u},\mathcal{C}).$

  3. 3.

For any $\bm{u}\in\mathbb{R}^{n+1}$, by definition we have
$d(\bm{u},\mathcal{C}^{\circ})=\|\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})\|_{2}$.
Now if $\bm{u}\in\mathcal{C}$ we have $\pi_{\mathcal{C}^{\circ}}(\bm{u})=0$ so
$d(\bm{u},\mathcal{C}^{\circ})=\|\bm{u}\|_{2}$.

  4. 4.

Let $\bm{u}\in\mathcal{C}$. Then $\bm{u}=\alpha(\kappa,\bm{x})$ for
$\alpha\geq 0,\bm{x}\in\mathcal{X}$. We will show that
$-\bm{u}\in\mathcal{C}^{\circ}$. We have

$\displaystyle-\bm{u}\in\mathcal{C}^{\circ}$
$\displaystyle\iff\langle-\bm{u},\bm{u}^{\prime}\rangle\leq
0,\forall\;\bm{u}^{\prime}\in\mathcal{C}$
$\displaystyle\iff\langle-\alpha(\kappa,\bm{x}),\alpha^{\prime}(\kappa,\bm{x}^{\prime})\rangle\leq
0,\forall\;\alpha^{\prime}\geq 0,\forall\;\bm{x}^{\prime}\in\mathcal{X}$
$\displaystyle\iff\kappa^{2}+\langle\bm{x},\bm{x}^{\prime}\rangle\geq 0$
$\displaystyle\iff-\langle\bm{x},\bm{x}^{\prime}\rangle\leq\kappa^{2},$

and $-\langle\bm{x},\bm{x}^{\prime}\rangle\leq\kappa^{2}$ is true by Cauchy-
Schwartz and the definition of
$\kappa=\max_{\bm{x}\in\mathcal{X}}\|\bm{x}\|_{2}$.

  5. 5.

We start by proving (5). Let
$\bm{x},\bm{x}^{\prime},\bm{y},\bm{y}^{\prime}\in\mathbb{R}^{n+1},$ and assume
that
$\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y},\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}^{\prime}$.
Then
$\bm{y}-\bm{x}\in\mathcal{C}^{\circ},\bm{y}^{\prime}-\bm{x}^{\prime}\in\mathcal{C}^{\circ}$.
Because $\mathcal{C}^{\circ}$ is a convex set, and a cone, we have
$2\cdot\left(\dfrac{\bm{y}-\bm{x}}{2}+\dfrac{\bm{y}^{\prime}-\bm{x}^{\prime}}{2}\right)\in\mathcal{C}^{\circ}$.
Therefore,
$\bm{y}+\bm{y}^{\prime}-\bm{x}-\bm{x}^{\prime}\in\mathcal{C}^{\circ}$, i.e.,
$\bm{x}+\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}+\bm{y}^{\prime}$.

We now prove (6). Let
$\;\bm{x},\bm{y}\in\mathbb{R}^{n+1},\bm{x}^{\prime}\in\mathcal{C}^{\circ}$ and
assume that $\bm{x}+\bm{x}^{\prime}\leq_{\mathcal{C}^{\circ}}\bm{y}$. Then by
definition $\bm{y}-\bm{x}-\bm{x}^{\prime}\in\mathcal{C}^{\circ}$.
Additionally, $\bm{x}^{\prime}\in\mathcal{C}^{\circ}$ by assumption. Since
$\mathcal{C}^{\circ}$ is convex, and is a cone,
$2\cdot\left(\dfrac{\bm{y}-\bm{x}-\bm{x}^{\prime}}{2}+\dfrac{\bm{x}^{\prime}}{2}\right)\in\mathcal{C}^{\circ}$,
i.e., $\bm{y}-\bm{x}\in\mathcal{C}^{\circ}$. Therefore,
$\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y}.$

  6. 6.

Let $\bm{x},\bm{y}\in\mathbb{R}^{n+1}$ such that
$\bm{x}\leq_{\mathcal{C}^{\circ}}\bm{y}$. Then
$\bm{y}-\bm{x}\in\mathcal{C}^{\circ}$. We have
$d(\bm{y},\mathcal{C}^{\circ})=\min_{\bm{z}\in\mathcal{C}^{\circ}}\|\bm{y}-\bm{z}\|_{2}\leq\|\bm{y}-(\bm{y}-\bm{x})\|_{2}=\|\bm{x}\|_{2}.$

∎

##  Appendix B Proof of Theorem 3.4

###### Proof of Theorem 3.4.

We prove the theorem for each part separately.

  1. 1.

Let

$\bar{\bm{x}}_{T}=\frac{1}{S_{T}}\sum_{t=1}^{T}\omega_{t}\bm{x}_{t},\bar{\bm{y}}_{T}=\frac{1}{S_{T}}\sum_{t=1}^{T}\omega_{t}\bm{y}_{t}.$

Since $F$ is convex-concave, we first have

$\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})\leq\frac{1}{S_{T}}\left(\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}F(\bm{x},\bm{y}_{t})\right).$

Now,

$\displaystyle\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}F(\bm{x},\bm{y}_{t})$
$\displaystyle=\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y})-\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y}_{t})$
$\displaystyle+\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y}_{t})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}F(\bm{x},\bm{y}_{t}).$

Now since $F$ is convex-concave, we can upper bound each pair of terms using
the subgradient inequality:

$\displaystyle\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y})-\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y}_{t})$
$\displaystyle\leq\max_{\bm{y}\in\mathcal{Y}}\omega_{t}\sum_{t=1}^{T}\langle\bm{g}_{t},\bm{y}\rangle-\sum_{t=1}^{T}\omega_{t}\langle\bm{g}_{t},\bm{y}_{t}\rangle,$
$\displaystyle\sum_{t=1}^{T}\omega_{t}F(\bm{x}_{t},\bm{y}_{t})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}F(\bm{x},\bm{y}_{t})$
$\displaystyle\leq\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle,$

where
$\bm{f}_{t}\in\partial_{\bm{x}}F(\bm{x}_{t},\bm{y}_{t}),\bm{g}_{t}\in\partial_{\bm{y}}F(\bm{x}_{t},\bm{y}_{t})$
(recall the repeated game framework presented at the beginning of Section 2).
We recognize the right-hand side as the regrets in the repeated game
framework. For CBA with weights on both payoffs and decisions (Theorem 3.1),
we have shown that

$\displaystyle\frac{1}{S_{T}}\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\omega_{t}\langle\bm{g}_{t},\bm{y}\rangle-\sum_{t=1}^{T}\langle\omega_{t}\bm{g}_{t},\bm{y}_{t}\rangle$
$\displaystyle=O\left(\kappa
L\frac{\sqrt{\sum_{t=1}^{T}\omega_{t}^{2}}}{\sum_{t=1}^{T}\omega_{t}}\right),$
$\displaystyle\frac{1}{S_{T}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle$
$\displaystyle=O\left(\kappa
L\frac{\sqrt{\sum_{t=1}^{T}\omega_{t}^{2}}}{\sum_{t=1}^{T}\omega_{t}}\right).$

Recall that $\omega_{t}=t^{p}$. Since $t\mapsto t^{p}$ is an increasing
function, we have

$\int_{0}^{k}t^{p}dt\leq\sum_{t=1}^{k}t^{p}\leq\int_{0}^{k+1}t^{p}dt.$

Therefore, we can conclude that

$\displaystyle\sum_{t=1}^{T}\omega_{t}^{2}$
$\displaystyle=O\left(\frac{1}{p+1}T^{2p+1}\right),$
$\displaystyle\frac{1}{p+1}T^{p+1}$
$\displaystyle\leq\sum_{t=1}^{T}\omega_{t}.$

Overall, we obtain that

$O\left(\kappa
L\frac{\sqrt{\sum_{t=1}^{T}\omega_{t}^{2}}}{\sum_{t=1}^{T}\omega_{t}}\right)=O\left(\frac{\kappa
L\sqrt{p+1}}{\sqrt{T}}\right).$

  2. 2.

This proof is mostly similar to the first part. We have

$\displaystyle\theta_{T}$ $\displaystyle=T^{q},$
$\displaystyle\frac{T^{q+1}}{q+1}$
$\displaystyle\leq\sum_{t=1}^{T}\theta_{t},$
$\displaystyle\sqrt{\sum_{t=1}^{T}\omega^{2}_{t}}$
$\displaystyle=O\left(\frac{1}{\sqrt{p+1}}T^{p+1/2}\right),$
$\displaystyle\omega_{T}$ $\displaystyle=T^{p}.$

Combining all this we obtain that an upper bound of

$O\left(\kappa
L\frac{(q+1)T^{q}}{T^{q+1}}\frac{T^{p+1/2}}{\sqrt{p+1}T^{p}}\right)$

which is equal to $O\left(\frac{\kappa L(q+1)}{\sqrt{p+1}\sqrt{T}}\right).$

∎

##  Appendix C Proof for Theorem 3.5

###### Proof of Theorem 3.5.

The proof of Theorem 3.5 is similar to the proof of Theorem 3.4 presented in
Appendix B. Let

$\bar{\bm{x}}_{T}=\frac{1}{S_{T}}\sum_{t=1}^{T}\theta_{t+1}\bm{x}_{t+1},\bar{\bm{y}}_{T}=\frac{1}{S_{T}}\sum_{t=1}^{T}\theta_{t+1}\bm{y}_{t}.$

Since $F$ is convex-concave, we first have

$\max_{\bm{y}\in\mathcal{Y}}F(\bar{\bm{x}}_{T},\bm{y})-\min_{\bm{x}\in\mathcal{X}}F(\bm{x},\bar{\bm{y}}_{T})\leq\frac{1}{S_{T}}\left(\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x},\bm{y}_{t})\right).$

Now we can rewrite

$\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x},\bm{y}_{t})$

as

$\displaystyle\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y})-\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y}_{t})$
$\displaystyle+\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y}_{t})-\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t},\bm{y}_{t})$
$\displaystyle+\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t},\bm{y}_{t})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x},\bm{y}_{t}).$

Now since $F$ is convex-concave, we can use the following upper bound:

$\displaystyle\max_{\bm{y}\in\mathcal{Y}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y})-\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t+1},\bm{y}_{t})$
$\displaystyle\leq\max_{\bm{y}\in\mathcal{Y}}\theta_{t+1}\sum_{t=1}^{T}\langle\bm{g}_{t},\bm{y}\rangle-\sum_{t=1}^{T}\theta_{t+1}\langle\bm{g}_{t},\bm{y}_{t}\rangle,$
$\displaystyle\sum_{t=1}^{T}\theta_{t+1}F(\bm{x}_{t},\bm{y}_{t})-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}F(\bm{x},\bm{y}_{t})$
$\displaystyle\leq\sum_{t=1}^{T}\theta_{t+1}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\theta_{t+1}\langle\bm{f}_{t},\bm{x}\rangle,$

where
$\bm{f}_{t}\in\partial_{\bm{x}}F(\bm{x}_{t},\bm{y}_{t}),\bm{g}_{t}\in\partial_{\bm{y}}F(\bm{x}_{t+1},\bm{y}_{t})$.
This concludes the proof of Theorem 3.5. ∎

##  Appendix D Proof of Theorem 3.6

We start with the following lemma. It shows that once a non-degenerate update
has been chosen ($\bm{u}_{t}\neq\bm{0}$ for CBA+ and
$\pi_{\mathcal{C}}(\bm{u}_{t})\neq\bm{0}$ for CBA), all the future updates are
also non-degenerate.

######  Lemma D.1.

  1. 1.

Let $\left(\bm{u}_{t}\right)_{t\geq
1}\in\left(\mathbb{R}^{n+1}\right)^{\mathbb{N}}$ the sequence of payoffs
generated by CBA with weights $\left(\omega_{t}\right)_{t\geq 1}$ on the
payoffs. Let $t\geq 1$. If
$\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)\neq\bm{0}$, then for all
$t^{\prime}\geq t$ we also have
$\pi_{\mathcal{C}}\left(\bm{u}_{t^{\prime}}\right)\neq\bm{0}$.

  2. 2.

Let $\left(\bm{u}_{t}\right)_{t\geq
1}\in\left(\mathbb{R}^{n+1}\right)^{\mathbb{N}}$ the sequence of payoffs
generated by CBA+ with weights $\left(\omega_{t}\right)_{t\geq 1}$ on the
payoffs. Let $t\geq 1$. If $\bm{u}_{t}\neq\bm{0}$, then for all
$t^{\prime}\geq t$ we also have $\bm{u}_{t^{\prime}}\neq\bm{0}$.

###### Proof of Lemma D.1.

  1. 1.

Assume that $\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)\neq\bm{0}$. Let
$\bm{\pi}_{t}=\left(\tilde{\pi}_{t},\hat{\bm{\pi}}_{t}\right)$ such that
$\bm{\pi}_{t}=\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)$. In this case, we can
define $\bm{x}_{t+1}=\left(\kappa/\tilde{\pi}_{t}\right)\hat{\bm{\pi}}_{t}$.
By definition of the updates in CBA, we have

$\bm{u}_{t+1}=\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1},$

for
$\bm{v}_{t+1}=\left(\frac{\langle\bm{f}_{t+1},\bm{x}_{t+1}\rangle}{\kappa},-\bm{f}_{t+1}\right).$
We will show that $\bm{u}_{t+1}\notin\mathcal{C}^{\circ}$. By definition,

$\bm{u}_{t+1}\notin\mathcal{C}^{\circ}\iff\exists\;\bm{z}\in\mathcal{C},\langle\bm{z},\bm{u}_{t+1}\rangle>0.$

If we take $\bm{z}=\bm{\pi}_{t}$, we have

$\langle\bm{\pi}_{t},\bm{u}_{t+1}\rangle=\langle\bm{\pi}_{t},\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\rangle=\langle\bm{\pi}_{t},\bm{u}_{t}\rangle$

since that by definition of $\bm{x}_{t+1}$, we have
$\langle\bm{\pi}_{t},\bm{v}_{t+1}\rangle=0$. Now

$\langle\bm{\pi}_{t},\bm{u}_{t}\rangle=\langle\pi_{\mathcal{C}}\left(\bm{u}_{t}\right),\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)+\pi_{\mathcal{C}^{\circ}}\left(\bm{u}_{t}\right)\rangle=\langle\pi_{\mathcal{C}}\left(\bm{u}_{t}\right),\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)\rangle=\|\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)\|_{2}^{2}>0.$

This shows that $\bm{u}_{t+1}\notin\mathcal{C}^{\circ}$. Since
$\bm{u}_{t+1}=\pi_{\mathcal{C}}(\bm{u}_{t+1})+\pi_{\mathcal{C}^{\circ}}(\bm{u}_{t+1})$,
this also shows that $\pi_{\mathcal{C}}(\bm{u}_{t+1})\neq\bm{0}$. By
induction, we have shown that
$\pi_{\mathcal{C}}\left(\bm{u}_{t}\right)\neq\bm{0}\Rightarrow\pi_{\mathcal{C}}\left(\bm{u}_{t^{\prime}}\right)\neq\bm{0},\forall\;t^{\prime}\geq
t$.

  2. 2.

The proof is very similar to the proof of the first statement. Suppose that
$\bm{u}_{t}\neq\bm{0}$. In this case, we can define
$\bm{x}_{t+1}=\left(\kappa/\tilde{u}_{t}\right)\hat{\bm{u}}_{t}$. Note that by
definition of the updates in CBA+, we have

$\bm{u}_{t+1}=\pi_{\mathcal{C}}\left(\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\right).$

We will show that

$\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\notin\mathcal{C}^{\circ}.$

By definition of $\mathcal{C}^{\circ}$,

$\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\notin\mathcal{C}\iff\exists\;\bm{z}\in\mathcal{C},\langle\bm{z},\bm{u}_{t}+\bm{v}_{t+1}\rangle>0.$

For $\bm{z}=\bm{u}_{t}$, we obtain

$\langle\bm{u}_{t},\bm{u}_{t}+\omega_{t+1}\bm{v}_{t+1}\rangle=\langle\bm{u}_{t},\bm{u}_{t}\rangle=\|\bm{u}_{t}\|_{2}^{2}>0,$

where

$\langle\bm{u}_{t},\bm{v}_{t+1}\rangle=0$

follows from the choice of $\bm{x}_{t+1}$ as in Blackwell approachability
framework (see (10) in the proof of Theorem 3.1 for more details.) Therefore,
for any $t\geq 1$, we have
$\bm{u}_{t}\neq\bm{0}\Rightarrow\bm{u}_{t+1}\neq\bm{0}$. This concludes the
proof of Lemma D.1 by induction.

∎

We are now ready to prove Theorem 3.6.

###### Proof of Theorem 3.6.

Assume that $\left(\bm{x},\bm{y}\right)\mapsto F\left(\bm{x},\bm{y}\right)$ is
linear in $\bm{x}$.

  1. 1.

We want to prove that

$F(\bm{x}_{t},\bm{y}_{t})\geq
F(\bm{x}_{t+1},\bm{y}_{t})+\frac{\kappa}{\omega_{t}\|\bm{u}_{t}\|_{\infty}}\|\bm{u}_{t}-\bm{u}_{t-1}\|_{2}^{2}.$
(23)

Let $t\geq 1$. Recall that

$\displaystyle\bm{x}_{t}$ $\displaystyle={\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}(\bm{u}_{t-1}),$ $\displaystyle\bm{x}_{t+1}$
$\displaystyle={\sf CHOOSEDECISION}_{{\sf
CBA\textsuperscript{+}}}(\bm{u}_{t}).$

We consider the following two cases.

    1. (a)

Case 1: $\bm{u}_{t}=\bm{0}$. From Lemma D.1, we must have
$\bm{u}_{t-1}=\bm{0}$, in which case $\bm{x}_{t+1}=\bm{x}_{t}=\bm{x}_{0}$ (the
default value for the decisions of the first player), so that (23) holds
because every term is $0$, with the convention that $0/0=0$ (in case
$\bm{u}_{t+1}=\bm{0}$).

    2. (b)

Case 2: $\bm{u}_{t}\neq\bm{0}$. We start from

$\bm{u}_{t}=\pi_{\mathcal{C}}\left(\bm{u}_{t-1}+\omega_{t}\bm{v}_{t}\right)$

with
$\bm{v}_{t}=\left(\frac{\langle\bm{f}_{t},\bm{x}_{t}\rangle}{\kappa},-\bm{f}_{t}\right)$.
The optimality condition for the projection on $\mathcal{C}$ shows that

$\langle\bm{u}_{t}-\bm{u}_{t-1}-\omega_{t}\bm{v}_{t},\bm{u}_{t}-\bm{z}\rangle\leq
0,\forall\;\bm{z}\in\mathcal{C}.$

We can apply this with $\bm{z}=\bm{u}_{t-1}$ to obtain

$\langle\bm{u}_{t}-\bm{u}_{t-1}-\omega_{t}\bm{v}_{t},\bm{u}_{t}-\bm{u}_{t-1}\rangle\leq
0.$

This shows that

$\|\bm{u}_{t}-\bm{u}_{t-1}\|_{2}^{2}\leq\langle\omega_{t}\bm{v}_{t},\bm{u}_{t}-\bm{u}_{t-1}\rangle.$

Recall that by definition of $\bm{x}_{t}$ and $\bm{v}_{t}$, we have

$\langle\bm{v}_{t},\bm{u}_{t-1}\rangle=0.$

Recall that $\bm{u}_{t}=\alpha_{t+1}\left(\kappa,\bm{x}_{t+1}\right)$, with
$\alpha_{t+1}>0$ because $\bm{u}_{t}\neq\bm{0}$. This implies that

$\displaystyle\langle\omega_{t}\bm{v}_{t},\bm{u}_{t}-\bm{u}_{t-1}\rangle$
$\displaystyle=\langle\omega_{t}\bm{v}_{t},\bm{u}_{t}\rangle$
$\displaystyle=\omega_{t}\langle\left(\frac{\langle\bm{f}_{t},\bm{x}_{t}\rangle}{\kappa},-\bm{f}_{t}\right),\alpha_{t+1}\left(\kappa,\bm{x}_{t+1}\right)\rangle$
$\displaystyle=\omega_{t}\alpha_{t+1}\left(\langle\bm{f}_{t},\bm{x}_{t}\rangle-\langle\bm{f}_{t},\bm{x}_{t+1}\rangle\right).$

Overall, we have obtained

$\langle\bm{f}_{t},\bm{x}_{t}\rangle\geq\langle\bm{f}_{t},\bm{x}_{t+1}\rangle+\frac{1}{\omega_{t}\alpha_{t+1}}\|\bm{u}_{t}-\bm{u}_{t-1}\|_{2}^{2}.$

Recall that by definition,
$\bm{u}_{t}=\alpha_{t+1}\left(\kappa,\bm{x}_{t+1}\right)$, with
$\kappa=\max\\{\|\bm{x}\|_{2}|\bm{x}\in\mathcal{X}\\}$. Therefore,

$\|\bm{u}_{t}\|_{\infty}=\alpha_{t+1}\max\\{\kappa,\|\bm{x}_{t+1}\|_{\infty}\\}=\alpha_{t+1}\kappa,$

where the last inequality follows from
$\|\bm{x}_{t+1}\|_{\infty}\leq\|\bm{x}_{t+1}\|_{2}\leq\kappa$. Overall, we
have shown that

$\langle\bm{f}_{t},\bm{x}_{t}\rangle\geq\langle\bm{f}_{t},\bm{x}_{t+1}\rangle+\frac{\kappa}{\omega_{t}\|\bm{u}_{t}\|_{\infty}}\|\bm{u}_{t}-\bm{u}_{t-1}\|_{2}^{2}.$

Recall that in the repeated game framework with alternation, we have
$\bm{f}_{t}=\partial_{\bm{x}}F(\bm{x}_{t},\bm{y}_{t})$. For an objective
function that is linear in $\bm{x}$, we obtain

$\displaystyle\langle\bm{f}_{t},\bm{x}_{t+1}\rangle$
$\displaystyle=F(\bm{x}_{t+1},\bm{y}_{t}),$
$\displaystyle\langle\bm{f}_{t},\bm{x}_{t}\rangle$
$\displaystyle=F(\bm{x}_{t},\bm{y}_{t}).$

In this case, we have shown that

$F(\bm{x}_{t},\bm{y}_{t})\geq
F(\bm{x}_{t+1},\bm{y}_{t})+\frac{\kappa}{\omega_{t}\|\bm{u}_{t}\|_{\infty}}\|\bm{u}_{t}-\bm{u}_{t-1}\|_{2}^{2}.$

This concludes the proof of the first statement of Theorem 3.6.

  2. 2.

The proof is identical to the first claim of this theorem. For the sake of
conciseness, we omit it in this paper.

∎

##  Appendix E Proofs for the efficient projections of Section 4

###  E.1 Proofs for the simplex

###### Proof of Lemma 4.1.

For $\mathcal{X}=\Delta(n)$, we can choose
$\kappa=\max\\{\|\bm{x}\|_{2}\;|\;\bm{x}\in\mathcal{X}\\}=1$. Therefore,
$\mathcal{C}=\\{\alpha\left(1,\bm{x}\right)\;|\;\bm{x}\in\Delta(n),\alpha\geq
0\\}$. For $\bm{y}=(\tilde{y},\hat{\bm{y}})\in\mathbb{R}^{n+1}$ we have

$\displaystyle\bm{y}\in\mathcal{C}^{\circ}$
$\displaystyle\iff\langle\bm{y},\bm{z}\rangle\leq
0,\forall\;\bm{z}\in\mathcal{C}$
$\displaystyle\iff\langle(\tilde{y},\hat{\bm{y}}),\alpha(1,\bm{x})\rangle\leq
0,\forall\;\bm{x}\in\Delta(n),\forall\;\alpha\geq 0$
$\displaystyle\iff\tilde{y}+\langle\hat{\bm{y}},\bm{x}\rangle\leq
0,\forall\;\bm{x}\in\Delta(n)$
$\displaystyle\iff\max_{\bm{x}\in\Delta(n)}\langle\hat{\bm{y}},\bm{x}\rangle\leq-\tilde{y}$
$\displaystyle\iff\max_{i=1,...,n}\hat{y}_{i}\leq-\tilde{y}.$

∎

###### Proof of Proposition 4.2.

Let us fix $\tilde{y}\in\mathbb{R}$ and let us first solve

$\displaystyle\min$ $\displaystyle\|\hat{\bm{y}}-\hat{\bm{u}}\|_{2}^{2}$ (24)
$\displaystyle\hat{\bm{y}}\in\mathbb{R}^{n},$
$\displaystyle\max_{i\in[n]}\hat{y}_{i}\leq-\tilde{y}.$

This is essentially the projection of $\hat{\bm{u}}$ on
$(-\infty,-\tilde{y}]^{n}$. So a solution to (24) is
$\hat{y}_{i}(\tilde{y})=\min\\{-\tilde{y},\hat{u}_{i}\\},\forall\;i=1,...,n.$
Note that in this case we have
$\hat{\bm{u}}-\hat{\bm{y}}(\tilde{y})=\left(\hat{\bm{u}}+\tilde{y}\bm{e}\right)^{+}.$
So overall the orthogonal projection on $\mathcal{C}^{\circ}$ boils down to
the optimization of the function $\phi:\mathbb{R}\mapsto\mathbb{R}_{+}$ such
that

$\phi:\tilde{y}\mapsto(\tilde{y}-\tilde{u})^{2}+\|\left(\hat{\bm{u}}+\tilde{y}\bm{e}\right)^{+}\|_{2}^{2}.$
(25)

In principle, we could use binary search with a doubling trick to compute a
$\epsilon$-minimizer of the convex function $\phi$ in
$O\left(\log(\epsilon^{-1})\right)$ calls to $\phi$. However, it is possible
to find a minimizer $\tilde{y}^{*}$ of $\phi$ using the following remark.

By construction, we know that
$\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})\in\mathcal{C}$. Here,
$\mathcal{C}=\textrm{cone}\left(\\{1\\}\times\Delta(n)\right)$, and
$\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})=\left(\tilde{u}-\tilde{y}^{*},\left(\hat{\bm{u}}+\tilde{y}^{*}\bm{e}\right)^{+}\right).$
We first check if $\tilde{u}=\tilde{y}^{*}$. This is the case if and only if
$\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})=\bm{0}$, i.e., if and only if
$\bm{u}\in\mathcal{C}^{\circ}$, which is straightforward to check using Lemma
4.1. Now if $\tilde{u}\neq\tilde{y}^{*}$, we must have
$\tilde{u}>\tilde{y}^{*}$, by definition of $\mathcal{C}$. This also implies
that

$\dfrac{\left(\hat{\bm{u}}+\tilde{y}^{*}\bm{e}\right)^{+}}{\tilde{u}-\tilde{y}^{*}}\in\Delta(n),$

which in turns imply that

$\tilde{y}^{*}+\sum_{i=1}^{n}\max\\{\hat{u}_{i}+\tilde{y}^{*},0\\}=\tilde{u}.$
(26)

We can use (26) to efficiently compute $\tilde{y}^{*}$ without using any
binary search. In particular, we can sort the coefficients of $\hat{\bm{u}}$
in $O\left(n\log(n)\right)$ arithmetic operations, and use (26) to find
$\tilde{y}^{*}$. ∎

###  E.2 Proofs for $\ell_{p}$-balls

###### Proof of Lemma 4.3.

Let us write $B_{p}(1)=\\{\bm{z}\in\mathbb{R}^{n}\;|\;\|\bm{z}\|_{p}\leq
1\\}$. Here we consider $\mathcal{X}=B_{p}(1)$. Recall that
$\kappa=\max\\{\|\bm{x}\|_{2}\;|\;\bm{x}\in\mathcal{X}\\}$. Therefore, by
definition, $\mathcal{C}=\\{\alpha\left(\kappa,\bm{x}\right)\;|\;\bm{x}\in
B_{p}(1),\alpha\geq 0\\}$.

We first provide the reformulation for $\mathcal{C}$. Let
$\bm{y}=(\tilde{y},\hat{\bm{y}})\in\mathcal{C}$. Then
$\tilde{y}=\alpha\kappa,\hat{\bm{y}}=\alpha\bm{x}$ with $\alpha\geq 0$ and
with $\bm{x}$ such that $\|\bm{x}\|_{p}\leq 1$. For $\alpha>0$ we have
$\|\bm{x}\|_{p}\leq
1\iff\|\alpha\bm{x}\|_{p}\leq\alpha\iff\|\hat{\bm{y}}\|_{p}\leq\tilde{y}/\kappa$.

We now provide the reformulation for $\mathcal{C}^{\circ}$. Note that for
$\bm{y}=(\tilde{y},\hat{\bm{y}})\in\mathbb{R}^{n+1}$ we have

$\displaystyle\bm{y}\in\mathcal{C}^{\circ}$
$\displaystyle\iff\langle\bm{y},\bm{z}\rangle\leq
0,\forall\;\bm{z}\in\mathcal{C}$
$\displaystyle\iff\langle(\tilde{y},\hat{\bm{y}}),\alpha(\kappa,\bm{x})\rangle\leq
0,\forall\;\bm{x}\in B_{p}(1),\forall\;\alpha\geq 0$
$\displaystyle\iff\kappa\tilde{y}+\langle\hat{\bm{y}},\bm{x}\rangle\leq
0,\forall\;\bm{x}\in B_{p}(1),$ $\displaystyle\iff\max_{\bm{x}\in
B_{p}(1),}\langle\hat{\bm{y}},\bm{x}\rangle\leq-\kappa\tilde{y}$
$\displaystyle\iff\|\hat{\bm{y}}\|_{q}\leq-\kappa\tilde{y},$

since $\|\cdot\|_{q}$ is the dual norm of $\|\cdot\|_{p}$. ∎

###### Proof of Proposition 4.4.

For $p=1$, we have $\|\cdot\|_{q}=\|\cdot\|_{\infty}$ and we can choose
$\kappa=1$. Let us compute the projection of
$\left(\tilde{u},\hat{\bm{u}}\right)$ on $\mathcal{C}^{\circ}$ using the
reformulation of Lemma 4.3:

$\displaystyle\min$
$\displaystyle\;(\tilde{y}-\tilde{u})^{2}+\|\hat{\bm{y}}-\hat{\bm{u}}\|_{2}^{2}$
(27) $\displaystyle\;\tilde{y}\in\mathbb{R},\hat{\bm{y}}\in\mathbb{R}^{n},$
$\displaystyle\|\hat{\bm{y}}\|_{\infty}\leq-\tilde{y}.$

For a fixed $\tilde{y}\in\mathbb{R}$, we want to compute
$\min\\{\|\hat{\bm{y}}-\hat{\bm{u}}\|_{2}^{2}\;|\;\hat{\bm{y}}\in\mathbb{R}^{n},\|\hat{\bm{y}}\|_{\infty}\leq-\tilde{y}\\}.$
This projection can be computed in closed-form as
$\hat{\bm{y}}^{*}(\tilde{y})=\min\\{-\tilde{y},\max\\{\tilde{y},\hat{\bm{u}}\\}\\}$,
since this is simply the orthogonal projection of $\hat{\bm{u}}$ onto the
$\ell_{\infty}$ ball of radius $-\tilde{y}$. Let us call
$\phi:\mathbb{R}\mapsto\mathbb{R}$ such that

$\phi(\tilde{y})=\left(\tilde{y}-\tilde{u}\right)^{2}+\|\hat{\bm{y}}^{*}(\tilde{y})-\hat{\bm{u}}\|_{2}^{2}.$

Note that
$\hat{\bm{y}}^{*}(\tilde{y})-\hat{\bm{u}}=\left(\hat{\bm{u}}+\tilde{y}\bm{e}\right)^{+}$,
so we have

$\phi:\tilde{y}\mapsto\left(\tilde{y}-\tilde{u}\right)^{2}+\|\left(\hat{\bm{u}}+\tilde{y}\bm{e}\right)^{+}\|_{2}^{2}.$

Assume that we have ordered the coefficients of
$\hat{\bm{u}}\in\mathbb{R}^{n}$ in decreasing order. This can be done in
$O\left(n\log(n)\right)$ arithmetic operations. Then on each of the $n+1$
intervals
$\mathcal{I}_{1}=\left(-\infty,-\hat{u}_{1}\right),\mathcal{I}_{2}=\left(-\hat{u}_{1},-\hat{u}_{2}\right),...,\mathcal{I}_{n+1}=\left(-\hat{u}_{n},+\infty\right)$,
the map $\phi$ is a second order polynomial in $\tilde{y}$, with a non-
negative coefficient in front of $\tilde{y}^{2}$. Therefore, for each
$i\in[n+1]$, we can find a closed-form expression for the minimum
$\phi^{*}_{i}$ of $\phi$ on $\mathcal{I}_{i}$, and the scalar
$\tilde{y}^{*}_{i}$ attaining this minimum. We can then simply search for a
global minimum of $\phi$ among the scalars

$\\{\tilde{y}^{*}_{i}\;|\;i\in[n+1]\\}\bigcup\\{-\hat{u}_{i}\;|\;i\in[n]\\}.$

Once we have found $\tilde{y}^{*}$ the minimizer of $\phi$, we obtain the
solution of $\pi_{\mathcal{C}^{\circ}}(\bm{u})$ as
$\pi_{\mathcal{C}^{\circ}}(\bm{u})=\left(\tilde{y}^{*},\hat{\bm{y}}^{*}(\tilde{y})\right)$,
and we can recover $\pi_{\mathcal{C}}(\bm{u})$ from
$\pi_{\mathcal{C}}(\bm{u})=\bm{u}-\pi_{\mathcal{C}^{\circ}}(\bm{u})$.

Let us now focus on the case $p=\infty$. We know that $\|\cdot\|_{1}$ and
$\|\cdot\|_{\infty}$ are dual norms to each other. Therefore, from Lemma 4.3,
it is as computationally demanding to compute orthogonal projections onto
$\mathcal{C}^{\circ}$ (when $p=1$) and onto $\mathcal{C}$ (when $p=\infty$).
Therefore, the method described in the first part of this proof for computing
$\pi_{\mathcal{C}^{\circ}}(\bm{u})$ for $p=1$ can be applied for computing
$\pi_{\mathcal{C}}(\bm{u})$ in the case $p=\infty$. ∎

###### Proof of Proposition 4.5.

First, we check if $\bm{u}\in\mathcal{C}$, i.e., we check if
$\|\hat{\bm{u}}\|_{2}\leq\tilde{u}$. If this is the case, then
$\pi_{\mathcal{C}}(\bm{u})=\bm{u}$. Second, we check if
$\bm{u}\in\mathcal{C}^{\circ}$, i.e., we check if
$\|\hat{\bm{u}}\|_{2}\leq-\tilde{u}$. If this is the case, then
$\pi_{\mathcal{C}}(\bm{u})=\bm{0}$. Else, we have
$\|\hat{\bm{u}}\|_{2}>|\tilde{u}|$, and we can provide a closed-form solution
to $\pi_{\mathcal{C}}(\bm{u})$. Let us fix $\tilde{y}\in\mathbb{R}$ and define
$\hat{\bm{y}}^{*}(\tilde{y})$ the vector attaining the minimum in
$\min\\{\|\hat{\bm{y}}-\hat{\bm{u}}\|_{2}^{2}\;|\;\hat{\bm{y}}\in\mathbb{R}^{n},\|\hat{\bm{y}}\|_{2}\leq\tilde{y}\\}.$
With this notation, we want to find the minimum of
$\phi:\mathbb{R}\mapsto\mathbb{R}$ defined as

$\phi(\tilde{y})=\left(\tilde{y}-\tilde{u}\right)^{2}+\|\hat{\bm{y}}^{*}(\tilde{y})-\hat{\bm{u}}\|_{2}^{2}.$

If $\tilde{y}\geq\|\hat{\bm{u}}\|_{2}$, then
$\hat{\bm{y}}^{*}(\tilde{y})=\hat{\bm{u}}$. This shows that the minimum of
$\phi$ on $[\|\hat{\bm{u}}\|_{2},+\infty)$ is attained at
$\tilde{y}_{1}=\|\hat{\bm{u}}\|_{2}$, at a value of
$\phi(\tilde{y}_{1}))=\left(\|\hat{\bm{u}}\|_{2}-\tilde{u}\right)^{2}$. When
$\tilde{y}\in[0,\|\hat{\bm{u}}\|_{2}]$, we have
$\hat{\bm{y}}^{*}(\tilde{y})=\left(\tilde{y}/\|\hat{\bm{u}}\|_{2}\right)\hat{\bm{u}}$.
Note that here, $\tilde{y}\mapsto\hat{\bm{y}}^{*}(\tilde{y})$ is
differentiable. Therefore,
$\phi:\tilde{y}\mapsto\left(\tilde{y}-\tilde{u}\right)^{2}+\|\hat{\bm{y}}^{*}(\tilde{y})-\hat{\bm{u}}\|_{2}^{2}$
is also differentiable. The first-order optimality conditions yield a closed-
form solution for the minimum of $\phi$ on $[0,\|\hat{\bm{u}}\|_{2}]$, with
$\tilde{y}_{2}=\dfrac{\tilde{u}+\|\hat{\bm{u}}\|_{2}}{2}$. For this value of
$\tilde{y}_{2}$, we obtain
$\phi(\tilde{y}_{2})=(1/2)\left(\|\hat{\bm{u}}\|_{2}-\tilde{u}\right)^{2}.$
Therefore, the global minimum of $\phi$ on $[0,+\infty)$ is attained at
$\tilde{y}_{2}$, yielding

$\pi_{\mathcal{C}}(\bm{u})=\left(\dfrac{\tilde{u}+\|\hat{\bm{u}}\|_{2}}{2},\dfrac{\tilde{u}+\|\hat{\bm{u}}\|_{2}}{2}\frac{\hat{\bm{u}}}{\|\hat{\bm{u}}\|_{2}}\right).$

∎

###  E.3 Proofs for confidence regions in the simplex

###### Proof of Proposition 4.6.

We can write $\mathcal{X}=\bm{x}_{0}+\epsilon\tilde{B},$ where
$\tilde{B}=\\{\bm{z}\in\mathbb{R}^{n}\;|\;\bm{z}^{\top}\bm{e}=0,\|\bm{z}\|_{2}\leq
1\\}.$

Suppose we made a sequence of decisions $\bm{x}_{1},...,\bm{x}_{T}$, which can
be written as $\bm{x}_{t}=\bm{x}_{0}+\epsilon\bm{z}_{t}$ for
$\bm{z}_{t}\in\tilde{B}.$ Then it is clear that for any sequence of payoffs
$\bm{f}_{1},...,\bm{f}_{T}$, we have

$\displaystyle\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle=\epsilon_{x}\left(\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{z}_{t}\rangle-\min_{\bm{z}\in\tilde{B}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{z}\rangle\right).$
(28)

Therefore, if we run CBA+ on the set $\tilde{B}$ to obtain
$O\left(\sqrt{T}\right)$ growth of the right-hand side of (28), we obtain a
no-regret algorithm for $\mathcal{X}$. We now show how to run CBA+ for the set
$\tilde{B}$. Let
$\mathcal{V}=\\{\bm{v}\in\mathbb{R}^{n}\;|\;\bm{v}^{\top}\bm{e}=0\\}.$ We use
the following orthonormal basis of $\mathcal{V}$: let
$\bm{v}_{1},...,\bm{v}_{n-1}\in\mathbb{R}^{n}$ be the vectors
$\bm{v}_{i}=\sqrt{i/(i+1)}\left(1/i,...,1/i,-1,0,...,0\right),\forall\;i=1,...,n-1,$
where the component $1/i$ is repeated $i$ times. The vectors
$\bm{v}_{1},...,\bm{v}_{n-1}$ are orthonormal and constitute a basis of
$\mathcal{V}$ (Egozcue et al., 2003). Writing
$\bm{V}=\left(\bm{v}_{1},...,\bm{v}_{n-1}\right)\in\mathbb{R}^{n\times(n-1)}$,
and noting that $\bm{V}^{\top}\bm{V}=\bm{I}$, we can write
$\tilde{B}=\\{\bm{Vs}\;|\;\bm{s}\in\mathbb{R}^{n-1},\|\bm{s}\|_{2}\leq 1\\}.$
Now, if $\bm{x}=\bm{x}_{0}+\epsilon_{x}\bm{z}_{t}$ with
$\bm{z}_{t}\in\mathcal{V}$, we have $\bm{z}_{t}=\bm{Vs}_{t}$, for
$\bm{s}_{t}\in\mathbb{R}^{n-1}$ and $\|\bm{s}\|_{2}\leq 1$. Finally,
$\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}_{t}\rangle-\min_{\bm{x}\in\mathcal{X}}\sum_{t=1}^{T}\omega_{t}\langle\bm{f}_{t},\bm{x}\rangle$
is equal to

$\epsilon_{x}\left(\sum_{t=1}^{T}\omega_{t}\langle\bm{V}^{\top}\bm{f}_{t},\bm{s}_{t}\rangle-\min_{\bm{s}\in\mathbb{R}^{n-1},\|\bm{s}\|_{2}\leq
1}\sum_{t=1}^{T}\omega_{t}\langle\bm{V}^{\top}\bm{f}_{t},\bm{s}\rangle\right).$
(29)

Therefore, to obtain a regret minimizer for (29) with observed payoffs
$\left(\bm{f}\right)_{t\geq 1}$, we can run CBA+ on the right-hand side, where
the decision set is an $\ell_{2}$ ball and the sequence of observed payoffs is
$\left(\bm{V}^{\top}\bm{f}_{t}\right)_{t\geq 1}$. In the previous section we
showed how to efficiently instantiate CBA+ in this setting (see Proposition
4.5). ∎

######  Remark E.1.

In this section we have highlighted a sequence of reformulations of the
regret, from (28) to (29). We essentially showed how to instantiate CBA+ for
settings where the decision set $\mathcal{X}$ is the intersection of an
$\ell_{2}$ ball with a hyperplane for which we have an orthonormal basis.

##  Appendix F Details on OMD, FTRL and optimistic variants

###  F.1 Algorithms

For solving our instances of distributionally robust optimization, we compare
SP-CBA+ with the following four state-of-the-art algorithms: at iteration
$t\geq 1$, for a step size $\eta_{t}>0$, the updates are:

  1. 1.

Follow-The-Regularized-Leader (FTRL) (Abernethy et al., 2009; McMahan, 2011):

$\bm{x}_{t+1}\in\arg\min_{\bm{x}\in\mathcal{X}}\;\langle\sum_{\tau=1}^{t}\bm{f}_{\tau},\bm{x}\rangle+\dfrac{1}{\eta_{t}}\|\bm{x}\|_{2}^{2}.$
(FTRL)

Optimistic FTRL (Rakhlin and Sridharan, 2013): given estimation $\bm{m}^{t+1}$
of loss at iteration $t+1$, choose

$\bm{x}_{t+1}\in\arg\min_{\bm{x}\in\mathcal{X}}\;\langle\sum_{\tau=1}^{t}\bm{f}_{\tau}+\bm{m}^{t+1},\bm{x}\rangle+\dfrac{1}{\eta_{t}}\|\bm{x}\|_{2}^{2}.$
(O-FTRL)

  2. 2.

Online Mirror Descent (OMD) (Nemirovski and Yudin, 1983; Beck and Teboulle,
2003):

$\bm{x}_{t+1}\in\min_{\bm{x}\in\mathcal{X}}\langle\bm{f}_{t},\bm{x}\rangle+\dfrac{1}{\eta_{t}}\|\bm{x}-\bm{x}_{t}\|_{2}^{2}.$
(OMD)

Optimistic OMD (Chiang et al., 2012): given estimation $\bm{m}^{t+1}$ of loss
at iteration $t+1$,

$\displaystyle\bm{z}_{t+1}\in\min_{\bm{z}\in\mathcal{X}}\langle\bm{m}_{t+1},\bm{z}\rangle+\dfrac{1}{\eta_{t}}\|\bm{z}-\bm{x}_{t}\|_{2}^{2},$
(O-OMD) $\displaystyle\text{Observe the loss }\bm{f}_{t+1}\text{ related to
}\bm{z}_{t+1},$
$\displaystyle\bm{x}_{t+1}\in\min_{\bm{x}\in\mathcal{X}}\langle\bm{f}_{t+1},\bm{x}\rangle+\dfrac{1}{\eta_{t}}\|\bm{x}-\bm{x}_{t}\|_{2}^{2}.$

Note that these algorithms can be written more generally using Bregman
divergence (e.g., Ben-Tal and Nemirovski (2001)). We choose to work with
$\|\cdot\|_{2}$ instead of Kullback-Leibler divergence as this
$\ell_{2}$-setup is usually associated with faster empirical convergence rates
(Chambolle and Pock, 2016; Gao et al., 2021). Additionally, following Chiang
et al. (2012); Rakhlin and Sridharan (2013), we use the last observed loss as
the predictor for the next loss, i.e., we set $\bm{m}^{t+1}=\bm{f}_{t}$.

###  F.2 Implementations

The proximal updates defined in the previous section need to be resolved for
the decision sets of both players of the distributionally robust optimization
problem (21). We present the details of our implementation here. The results
in the rest of this section are reminiscent to the novel tractable proximal
setups presented in Grand-Clément and Kroer (2020, 2021a).

#### Computing the projection steps for the first player

For
$\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{n}\;|\;\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}\\}$,
$\bm{c},\bm{x}^{\prime}\in\mathbb{R}^{n}$ and a step size $\eta>0$, the prox-
update becomes

$\min_{\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon_{x}}\langle\bm{c},\bm{x}\rangle+\dfrac{1}{2\eta}\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}.$

Using a change of variable, we find that the optimal solution $\bm{x}^{*}$ to
the problem above is

$\bm{x}^{*}=\bm{x}_{0}+\epsilon_{x}\dfrac{\bm{x}^{\prime}-\eta\bm{c}-\bm{x}_{0}}{\max\\{\epsilon_{x},\|\bm{x}^{\prime}-\eta\bm{c}-\bm{x}_{0}\|_{2}\\}}.$

#### Computing the projection steps for the second player

For
$\mathcal{Y}=\\{\bm{y}\in\Delta(m)\;|\;\|\bm{y}-\bm{y}_{0}\|_{2}\leq\epsilon_{y}\\}$,
the proximal update of the second player from a previous point
$\bm{y}^{\prime}$ and a step size of $\eta>0$ becomes

$\min_{\|\bm{y}-\bm{y}_{0}\|_{2}\leq\epsilon_{y},\bm{y}\in\Delta(m)}\langle\bm{c},\bm{y}\rangle+\dfrac{1}{2\eta}\|\bm{y}-\bm{y}^{\prime}\|_{2}^{2}.$
(30)

If we dualize the $\ell_{2}$ constraint with a Lagrangian multiplier $\mu\geq
0$ we obtain the relaxed problem $q(\mu)$ where

$q(\mu)=-(1/2)\epsilon_{y}^{2}\mu+\min_{\bm{y}\in\Delta(m)}\langle\bm{c},\bm{y}\rangle+\dfrac{1}{2\eta}\|\bm{y}-\bm{y}^{\prime}\|_{2}^{2}+\dfrac{\mu}{2}\|\bm{y}-\bm{y}_{0}\|_{2}^{2}.$
(31)

Note that the $\arg\min$ in

$\min_{\bm{y}\in\Delta(m)}\langle\bm{c},\bm{y}\rangle+\dfrac{1}{2\eta}\|\bm{y}-\bm{y}^{\prime}\|_{2}^{2}+\dfrac{\mu}{2}\|\bm{y}-\bm{y}_{0}\|_{2}^{2}$

is the same $\arg\min$ as in