\section{Introduction}

The notion of approachability introduced by \cite{Blackwell1956} can
be viewed as an extension of von Neumann's minimax theorem
\citep{vonNeumann1928} to the case of vectorial
payoffs. \citeauthor{Blackwell1956} gave a simple example showing that
the straightforward analog of von Neumann's minimax theorem does not
hold for vectorial payoffs. However, in contrast with this negative
result for one-shot games, he proved that, in repeated games, a player
admits an adaptive strategy guaranteeing that their average payoff
\emph{approaches} a closed convex set in the limit, provided that the
set satisfies a natural separability condition.

The theory of Blackwell approachability is intimately connected with
the field of online learning for the reason that the problem of
\textit{regret minimization} can be viewed as an approachability
problem: in particular, the learner would like their vector of regrets
(with respect to each competing benchmark) to converge to a
non-positive vector.  In this vein, \cite{AbernethyBartlettHazan2011}
demonstrated how to use algorithms for approachability to solve a
general class of regret minimization problems (and conversely, how to
use regret minimization to construct approachability
algorithms). However, applying their reduction sometimes leads to
suboptimal regret guarantees -- for example, for the specific case of
minimizing external regret over $T$ rounds with $K$ actions, their
reduction results in an algorithm with $O(\sqrt{TK})$ regret (instead
of the optimal $O(\sqrt{T\log K})$ regret bound achievable by
e.g. multiplicative weights).

One reason for this suboptimality is the choice of distance used to
define approachability. Both \citeauthor{Blackwell1956} and
\citeauthor{AbernethyBartlettHazan2011}\! consider approachability
algorithms that minimize the Euclidean ($\ell_2$) distance between
their average payoff and the desired set. We argue that, for
applications to regret minimization, it is often more useful to study
approachability under other distance metrics, most commonly
approachability under the \textit{$\ell_{\infty}$ metric} to the
\textit{non-positive orthant}, which is well suited to capture the
fact that regret is a \textit{maximum} over various competing
benchmarks. This has been observed in the past in several recent
publications \citep{Perchet2015,Shimkin2016,Kwon2021}.  In particular,
by constructing algorithms for $\ell_{\infty}$ approachability, it is
possible to naturally recover a $O(\sqrt{T\log K})$ external regret
learning algorithm (and algorithms with optimal regret guarantees for
many other problems of interest).

However, there is still one significant problem with developing regret
minimization algorithms via $\ell_{\infty}$ approachability (or any of
the forms of approachability previously mentioned): the time and space
complexity of these algorithms depends polynomially on the dimension
$d$ of the space of vectorial payoffs, which in turn equals the number
of benchmarks we compete against in our regret minimization
problem. In some regret minimization settings, this can be
prohibitively expensive. For example, in the setting of swap regret
(where the benchmarks are parameterized by the $d = K^K$ swap
functions mapping $[K]$ to $[K]$), this results in algorithms with
complexity exponential in $K$. On the other hand, there exist
algorithms, e.g.\ \citep{BlumMansour2007}, which are both efficient
($\poly(K)$ time and space) and obtain optimal regret guarantees.

\subsection{Main results}

In this paper, we present a framework for converting
\textit{high-dimensional} $\ell_{\infty}$ approachability problems to
\textit{low-dimensional} ``pseudonorm'' approachability problems, in
turn resolving many of these issues. To be precise, recall that the
setting of approachability can be thought of as a $T$-round repeated
game, where in round $t$ the learner chooses an action $p_t$ from some
convex ``action'' set ${\mathscr P} \subseteq \mathbb{R}^n$, the adversary
simultaneously chooses an action $\ell_t$ from some convex ``loss''
set ${\mathscr L} \subseteq \mathbb{R}^m$, and the learner receives a vector-valued
payoff $u(p_t, \ell_t)$, where $u\colon {\mathscr P} \times {\mathscr L} \rightarrow
\mathbb{R}^{d}$ is a $d$-dimensional bilinear function. The learner would
like the $\ell_{\infty}$ distance between their average payoff
$\frac{1}{T}\sum u(p_t, \ell_t)$ and some convex set\footnote{For
simplicity, throughout this paper we assume ${\mathscr S}$ to be the negative
orthant $(-\infty, 0]^d$, as this is the case most relevant to regret
minimization. However, much of our results extend straightforwardly
to arbitrary convex sets.} ${\mathscr S}$ to be as small as possible.

We first demonstrate how to construct a new $d'$-dimensional bilinear
function $\widetilde{u}\colon {\mathscr P} \times {\mathscr L} \rightarrow \mathbb{R}^{d'}$, a new
convex set ${\mathscr S}' \subseteq \mathbb{R}^{d'}$, and a pseudonorm\footnote{In
this paper a \textit{pseudonorm} is a function $f\colon \mathbb{R}^{d'}
\rightarrow \mathbb{R}_{\geq 0}$ which satisfies most of the properties of
a norm (e.g. positive homogeneity, triangle inequality), but may be
asymmetric (there may exist $x$ where $f(x) \neq f(-x)$) and may not
be definite (there may exist $x \neq 0$ where $f(x) = 0$). Just as a
norm $\norm{\cdot}$ defines a distance between $x, y \in \mathbb{R}^{d'}$
via $\norm{x - y}$, a pseudonorm $f$ defines the pseudodistance $f(x -
y)$.} $f$ such that the ``pseudodistance'' between the average
modified payoff $\frac{1}{T}\sum \widetilde{u}(p_t, \ell_t)$ and ${\mathscr S}'$ is
equal to the $\ell_{\infty}$ distance between the original average
payoff and ${\mathscr S}$. Importantly, the new dimension $d'$ is equal to $mn$
and is independent of the original dimension $d$.

We then develop an algorithmic theory of pseudonorm approachability
analogous to that developed in \citep{AbernethyBartlettHazan2011} for
the $\ell_2$ norm and \citep{Shimkin2016, Kwon2021} for other norms,
showing that, in order to perform pseudonorm approachability, it
suffices to be able to perform online linear optimization (OLO) over a
convex set given by the Fenchel dual of the unit pseudonorm ball (and
that the rate of approachability is directly related to the regret
guarantees of this OLO subalgorithm). This has the following
consequences for approachability:

\begin{itemize}
    \item First, by solving this OLO problem with a quadratic
      regularized Follow-The-Regularized-Leader (FTRL) algorithm, we
      show (modulo mild normalization assumptions on the sizes of
      ${\mathscr P}$, ${\mathscr L}$, and $u$) that there exists a pseudonorm
      approachability algorithm (and hence an $\ell_{\infty}$
      approachability algorithm for the original problem) which
      converges at a rate of $O(nm/\sqrt{T})$. We additionally provide
      a stronger bound on the rate which scales as
      $O(D_{u}D_{p}D_{\ell}/\sqrt{T})$ where $D_{p} = \diam {\mathscr P}$,
      $D_{\ell} = \diam {\mathscr L}$, and $D_{u}$ is the maximum $\ell_2$ norm
      of the set of vectors formed by taking the coefficients of
      components of $u$ (Theorem \ref{thm:poly_regret}). In
      comparison, the best-known generic guarantee for
      $\ell_{\infty}$-approachability prior to this work converged at
      a $d$-dependent rate of $O(\sqrt{(\log d)/T})$.
      
    \item \sloppy{Second, we show that as long as we can evaluate the
      original $\ell_{\infty}$-distance between $\frac{1}{T}\sum
      u(p_t, \ell_t)$ and $(-\infty, 0]^d$ efficiently, we can
      implement the above algorithm in $\poly(m, n)$ time per round
      (Theorem \ref{thm:efficient_alg}). This has the following
      natural consequence for the class of regret minimization
      problems that can be written as $\ell_{\infty}$-approachability
      problems: \textit{if it is possible to efficiently compute some
        notion of regret for a sequence of losses and actions, then
        there is an efficient (in the dimensions of the actions and
        losses) learner that minimizes this regret}.}

      \item Finally, in some cases, the $O(\sqrt{(\log d)/T})$
        approachability rate from (inefficient)
        $\ell_{\infty}$-approachability outperforms the rate obtained
        by the quadratic regularized FTRL algorithm. We define a new
        regularizer whose value is given by finding the maximum
        entropy distribution of a subset of distributions of support
        $d$, and show that, by using this regularizer, we recover this
        $O(\sqrt{(\log d)/T})$ rate. In particular, whenever we can
        efficiently compute this maxent regularizer, there is an
        efficient learning algorithm with a $O(\sqrt{(\log d)/T})$
        approachability rate.
\end{itemize}

\noindent
We then apply our framework to various problems in regret minimization:

\begin{itemize}
    \item We show that our framework straightforwardly recovers a
      regret-optimal and efficient algorithm for swap regret
      minimization. Doing so requires computing the above maximum
      entropy regularizer for this specific case, where we show that
      it has a nice closed form. In particular, to our knowledge. this
      is the first approachability-based algorithm for swap regret
      that both is efficient and has the optimal minimax regret.
    
    \item In Section~\ref{sec:bayes_correlated}, we apply our
      framework to develop the first efficient contextual learning
      algorithms with low \textit{Bayesian swap regret}. Such
      algorithms have the property that if learners employ them in a
      repeated Bayesian game, the time-average of their strategies
      will converge to a Bayesian correlated equilibrium, a
      well-studied equilibrium notion in game theory (see
      e.g. \cite{bergemann2016bayes}).
    
    This notion of Bayesian swap regret was recently introduced by
    \cite{mansour2022}, who also provided an algorithm with low
    Bayesian swap regret, albeit one that is not computationally
    efficient. By applying our framework, we easily obtain an
    efficient contextual learning algorithm with $O(CK\sqrt{T})$
    Bayesian swap regret, resolving an open question of
    \cite{mansour2022} (here $C$ is the number of ``contexts'' /
    ``types'' of the learner).

    \item In Section~\ref{sec:rl}, we further analyze the application
      of our general $\ell_\infty$-approachability theory and
      algorithm to the analysis of reinforcement learning (RL) with
      vectorial losses. We point out how our framework can provide a
      general solution in the full information setting with known
      transition probabilities and how we can recover the best known
      solution for standard regret minimization in episodic RL. More
      importantly, we show how our framework and algorithm can lead to
      an algorithm for constrained MDPs with a significantly more
      favorable regret guarantee, logarithmic in the number of
      constraints $k$, in contrast with the $\sqrt{k}$-dependency of
      the results of \citet{MiryoosefiBrantleyDaumeDudikSchapire2019}.

\end{itemize}


\subsection{Related Work}

There is a wide literature dealing with various aspects of Blackwell's
approachability, including its applications to game theory,
regret minimization, reinforcement learning, and multiple extensions.

\citet{HartMasColell2000} described an adaptive procedure for players
in a game based on Blackwell's approachability, which guarantees that
the empirical distributions of the plays converges to the set of a
correlated equilibrium. This procedure is related to internal regret
minimization, for which, as shown by \citet{FosterVohra1999}, the
existence of an algorithm follows the proof of
\citet{HartMasColell2000}.  \citet{HartMasColell2001} further gave a
general class of adaptive strategies based on approachability.
Approachability has been widely used for calibration \citep{Dawid82},
see \cite{FosterHart2017} for a recent work on the topic.
Approachability and partial monitoring were studied in a series of
publications by \citet{Perchet2010,MannorPerchetStoltz2014,
  MannorPerchetStoltz2014Bis,
  PerchetQuincampoix2015,PerchetQuincampoix2018,KwonPerchet2017}. More
recently, approachability has also been used in the analysis of
fairness in machine learning \citep{ChzhenGiraudStoltz2021}.

Approachability has also been extensively used in the context of
reinforcement learning. \citet{MannorShimkin2003} discussed an
extension of regret minimization in competitive Markov decision
processes (MDPs) whose analysis is based on Blackwell's
approachability theory. \citet{MannorShimkin2004} presented a
geometric approach to multiple-criteria reinforcement learning
formulated as approachability conditions.
\citet{KalathiBorkarJain2014} presented strategies for approachability
for MDPs and Stackelberg stochastic games based on
\citeauthor{Blackwell1956}'s approachability theory.  More recently,
\citet{MiryoosefiBrantleyDaumeDudikSchapire2019} used approachability
to derive solutions for reinforcement learning with convex
constraints. 

The notion of approachability was further extended in several studies.
\citet{Vieille1992} used differential games with a fixed duration to
study weak approachability in finite dimensional
spaces. \citet{Spinat2002} formulated a necessary and sufficient
condition for approachability of non-necessary convex sets.
\citet{Lehrer2003Bis} extended \citeauthor{Blackwell1956}'s
approachability theory to infinite-dimensional spaces.

The most closely related work to this paper, which we build upon,
is that of \citet{AbernethyBartlettHazan2011} who showed that,
remarkably, any algorithm for Blackwell's approachability could be
converted into one for online convex optimization and vice-versa.
\citet{BernsteinShimkin2015} also discussed a related response-based
approachability algorithm.

\citet{Perchet2015} presented a specific study of $\ell_\infty$
approachability, for which they gave an exponential weight algorithm.
\citet[][Section~5]{Shimkin2016} studied approachability for an
arbitrary norm and gave a general duality result for an arbitrary norm
using Sion's minmax theorem. The pseudonorm duality theorem we prove,
using Fenchel duality, can be viewed as a generalization.
\citet{Kwon2016,Kwon2021} also presented a duality theorem similar to
that of \citet{Shimkin2016} which they used to derive a FTRL algorithm
for general norm approachability. They further treated the special
case of internal and swap regret. However, unlike the algorithms
derived in this work, the computational complexity of their swap
regret algorithm is in $O(K^K)$. This is also true of the paper of
\citet{Perchet2015} which also analyzes the swap regret problem.



It is known that if all players follow a swap regret minimization
algorithm, then the empirical distribution of their play converges to
a correlated equilibrium \citep{BlumMansour2007}.
\cite{HazanKale2008} showed a result generalizing this property to the
case of $\Phi$-regret and $\Phi$-equilibrium, where the $\Phi$-regret
is the difference between the cumulative expected loss suffered by the
learner and that of the best $\Phi$-modification of the sequence in
hindsight.
\citet{GordonGreenwaldMarks2008} further generalized the results of
\cite{HazanKale2008} to a more general class of $\Phi$-modification
regrets.  The algorithms discussed in \citep{GordonGreenwaldMarks2008}
are distinct from those discussed in this paper (they do not clearly
extend to the general approachability setting, and they require
significantly different computational assumptions than
ours). Nevertheless, they bare some similarity with our work.

\ignore{
\textbf{TODO: add phi regret papers (Hazan / Kale), (Gordon et al.)}
}


\section{Preliminaries}

\paragraph{Notation.} We use $[n]$ as a shorthand for
set $\{1, 2, \dots, n\}$. We write $\Delta_{d} = \{x \in \mathbb{R}^d \mid
x_i \geq 0, \sum x_i = 1 \}$ to denote the simplex over $d$ dimensions
and ${\overline{\Delta}}_{d} = \{x \in \mathbb{R}^d \mid x_i \geq 0, \sum x_i \leq 1
\}$ to denote the convex hull of the $d$-simplex with the origin.
$\conv(S)$ denotes the convex hull of the points in $S$, and
$\cone(S) = \{\alpha x \mid \alpha \geq 0, x \in \conv(S)\}$ the
convex cone generated by the points in $S$.

Some of the more standard proofs have been deferred to Appendix
\ref{app:omitted}.

\subsection{Blackwell approachability and regret minimization}
\label{sec:online_learning}

We begin by illustrating the theory of Blackwell approachability for
the specific case of the $\ell_{\infty}$-distance; this case is both
particularly suited to the application of regret minimization, and
will play an important role in the results (e.g. reductions to
pseudonorm approachability) that follow.

We consider a repeated game setting, where every round $t$ a learner
chooses an action $p_t$ belonging to a bounded\footnote{We bound the
entries of ${\mathscr P}$, ${\mathscr L}$, and $u$ within $[-1, 1]$ for convenience, but
it is generally easy to translate between different boundedness
assumptions (since almost all relevant quantities are linear). We
express the majority of our theorem statements (with the notable
exception of Theorem \ref{thm:poly_regret}) in a way that is
independent of the choice of bounds.} convex set ${\mathscr P} \subseteq [-1,
  1]^{n}$, and an adversary simultaneously chooses a loss $\ell_t$
belonging to a bounded convex set ${\mathscr L} \subseteq [-1, 1]^{m}$. Let
$u\colon {\mathscr P} \times {\mathscr L} \rightarrow [-1, 1]^d$ be a bounded
bilinear\footnote{We briefly note that all our results also hold for
\textit{biaffine} functions $u_i$; in particular, extending the loss
and action sets slightly (by replacing ${\mathscr P}$ and ${\mathscr L}$ with ${\mathscr P}
\times \{1\}$ and ${\mathscr L} \times \{1\}$) allows us to write any biaffine
function over the original sets as a bilinear function over the
extended sets.} vector-valued \textit{payoff function}, and let ${\mathscr S}
\subseteq \mathbb{R}^d$ be a closed convex set with the property that for
every $\ell \in {\mathscr L}$, there exists a $p \in {\mathscr P}$ such that $u(p, \ell)
\in {\mathscr S}$ (we say that such a set is ``separable''). When $d = 1$, the
minimax theorem implies that there exists a single $p \in {\mathscr P}$ such
that for all $\ell$, $u(p, \ell) \in {\mathscr S}$.

This is not true for $d > 1$, but the theory of Blackwell
approachability provides the following algorithmic analogue of this
statement. Define a \textit{learning algorithm} $\mathcal{A}$ to be a
collection of functions $\mathcal{A}_t \colon {\mathscr L}^{t-1} \rightarrow {\mathscr P}$ for
each $t \in [T]$, where $\mathcal{A}_t$ describes how the learner decides
their action $p_t$ as a function of the observed losses $\ell_1,
\ell_2, \dots, \ell_{t-1}$ up until time $t-1$. Blackwell
approachability guarantees that there exists a learning algorithm
$\mathcal{A}$ such that when $\mathcal{A}$ is run on any loss sequence $\bm{\ell}$ the
resulting action sequence $\bm{p}$ has the property that:

\begin{equation}\label{eq:approachability}
  \lim_{T\rightarrow \infty} d_{\infty}
  \left(\frac{1}{T}\sum_{t=1}^{T}u(p_{t}, \ell_t), {\mathscr S}\right) = 0.
\end{equation}

\noindent
(Here for $v, w \in \mathbb{R}^d$, $d_{\infty}(v, w) = \max_{i} |v_i -
w_i|$ represents the $\ell_{\infty}$ distance between $v$ and $w$).

As mentioned, one of the main motivations for studying Blackwell
approachability is its connections to regret minimization. In
particular, for a fixed choice of $u$, define

\begin{equation}\label{eq:regret_def}
  \Reg(\mathbf{p}, \bm{\ell}) = \max\left(\max_{i \in [d]}
  \left(\sum_{t=1}^{T} u_i(p_t, \ell_t)\right), 0\right).
\end{equation}

Note first that this definition of ``regret'' is exactly $T$ times the
$\ell_{\infty}$ approachability distance in the case where ${\mathscr S} =
(\infty, 0]^d$ is the negative orthant; that is,

\begin{equation}\label{eq:regret}
  \Reg(\bm{p}, \bm{\ell}) = T \cdot d_{\infty}
  \left(\frac{1}{T}\sum_{t=1}^{T}u(p_{t}, \ell_t), (-\infty, 0]^d \right).
\end{equation}

But secondly, note that by choosing ${\mathscr P}$, ${\mathscr L}$, and $u$ carefully,
the definition $\eqref{eq:regret_def}$ can capture a wide variety of
forms of regret studied in regret minimization. For example:

\begin{itemize}
    \item When ${\mathscr P} = \Delta_{K}$, ${\mathscr L} = [0, 1]^K$, $d = K$, and
      $u(p, \ell)_i = \langle p, \ell \rangle - \ell_i$, $\Reg(\bm{p},
      \bm{\ell})$ is the \textit{external regret} of playing action
      sequence $\bm{p}$ against loss sequence $\bm{\ell}$; i.e., it
      measures the regret compared to the best single action.

    \item When ${\mathscr P} = \Delta_{K}$, ${\mathscr L} = [0, 1]^K$, $d = K^{K}$, and
      (for each function $\pi \colon [K]\rightarrow[K]$, $u(p, \ell)_\pi =
      \sum_{i=1}^{K}p_{i}(\ell_{i} - \ell_{\pi(i)})$, $\Reg(\bm{p},
      \bm{\ell})$ is the \textit{swap regret} of playing action
      sequence $\bm{p}$ against loss sequence $\bm{\ell}$; i.e., it
      measures the regret compared to the best action sequence
      $\bm{p'}$ obtained by applying a fixed swap function to sequence
      $\bm{p}$.

    \item When ${\mathscr P} \subseteq \mathbb{R}^{n}$ is a convex polytope, ${\mathscr L} =
      [0, 1]^n$, $d = |V({\mathscr P})|$ (where $V({\mathscr P})$ is the set of vertices
      of ${\mathscr P}$), and (for each vertex $v \in V({\mathscr P})$), $u(p, \ell)_{v}
      = \langle p, \ell \rangle - \langle v, \ell\rangle$, this
      captures the (external) regret from performing online linear
      optimization over the polytope ${\mathscr P}$ (see Section
      \ref{sec:olo}).

    \item Finally, to illustrate the power of this framework, we
      present an unusual swap regret minimization that we call
      ``Procrustean swap regret minimization'' (after the orthogonal
      Procrustes problem, see \citep{gower2004procrustes}). Let ${\mathscr P} =
      \{x \in \mathbb{R}^{n} \, \colon ||x||_2 \leq 1\}$ be the unit ball in
      $n$ dimensions, ${\mathscr L} = [-1, 1]^{n}$, and, for each orthogonal
      matrix\footnote{Technically, this leads to an infinite
      dimensional $u$ (since the group of orthogonal matrices is
      infinite), but one can instead take an arbitrarily fine discrete
      approximation of the set. Indeed, one of the advantages of the
      results we present is that they are largely independent of the
      dimension $d$ of $u$.} $Q \in O(n)$, let $u(p, \ell)_{Q} =
      \langle p, \ell \rangle - \langle Qp, \ell \rangle$.
\end{itemize}

When the negative orthant $(-\infty, 0]^d$ is separable with respect
  to $u$, which is true in all of the above examples, the theory of
  Blackwell approachability immediately guarantees the existence of a
  sublinear regret learning algorithm $\mathcal{A}$ for the corresponding
  notion of regret. Specifically, define the regret of a learning
  algorithm $\mathcal{A}$ to be the worst-case regret over all possible loss
  vectors $\bm{\ell} \in {\mathscr L}^{T}$; i.e.,

\begin{equation}\label{eq:regret_def2}
    \Reg(\mathcal{A}) = \max_{\bm{\ell} \in {\mathscr L}^{T}}\, \Reg(\bm{p}, \bm{\ell}),
\end{equation}

\noindent
where $p_t = \mathcal{A}_{t}(\ell_1, \dots, \ell_{t-1})$. Then
\eqref{eq:approachability} implies that the same algorithm $\mathcal{A}$
satisfies $\Reg(\mathcal{A}) = o(T)$. Motivated by this application, we will
restrict our attention for the remainder of this paper to the setting
where ${\mathscr S} = (-\infty, 0]^d$ and will assume (unless otherwise
  specified) that this ${\mathscr S}$ is separable with respect to the bilinear
  function $u$ we consider.

In fact, the theory of $\ell_{\infty}$-approachability is constructive
and allows us to write down explicit algorithms $\mathcal{A}$ along with
explicit (and in many cases, near optimal) regret bounds. However,
before we introduce these algorithms, we will need to introduce the
problem of online linear optimization.


\subsection{Online linear optimization}
\label{sec:olo}

Here we discuss algorithms for \textit{online linear optimization}
(OLO), a special case of online convex optimization where all the loss
functions are linear functions of the learner's action. These will
form an important primitive of our algorithms for approachability.

Let ${\mathscr X}, {\mathscr Y}$ be two bounded convex subsets of $\mathbb{R}^r$ and consider
the following learning problem. Every round $t$ (for $T$ rounds) our
learning algorithm must choose an element $x_t \in {\mathscr X}$ as a function
of $y_1, y_2, \dots, y_{t-1}$. The adversary simultaneously chooses a
loss ``function'' $y_t \in {\mathscr Y}$. This causes the learner to incur a
loss of $\langle x_t, y_t \rangle$ in round $t$. The goal of the
learner is to minimize their regret, defined as the difference between
their total loss and the loss they would have incurred by playing the
best fixed action in hindsight, i.e.,

$$\Reg(\bm{x}, \bm{y}) = \max_{x^* \in {\mathscr X}}\left(\sum_{t=1}^{T} \langle x_t, y_t\rangle - \sum_{t=1}^{T} \langle x^*, y_t\rangle\right).$$

There are many similarities between this problem and the
approachability and regret minimization problems discussed in Section
\ref{sec:online_learning}. For example, if we take ${\mathscr X} = {\mathscr P} =
\Delta_{K}$ and ${\mathscr Y} = {\mathscr L} = [0, 1]^{K}$, then OLO is equivalent to
the problem of external regret minimization. However, not all regret
minimization problems can be written directly as an instance of OLO --
for example, there is no clear way to write swap regret minimization
as an OLO instance. Eventually we will demonstrate how to apply OLO as
a subroutine to solve any regret minimization problem, but this will
involve a reduction to Blackwell approachability and will require
running OLO on different spaces than the action/loss sets ${\mathscr P}$ and
${\mathscr L}$ directly (which is why we distinguish the action/loss sets for
OLO as ${\mathscr X}$ and ${\mathscr Y}$ respectively).

There is an important subclass of algorithms for OLO known as
\textit{Follow the Regularized Leader (FTRL)} algorithms
\citep{ShalevShwartz2007,AbernethyHazanRakhlin2008}. An FTRL algorithm
is completely specified by a strongly convex function $R\colon {\mathscr X}
\rightarrow \mathbb{R}$, and plays the action

\[
x_t = \argmin_{x \in {\mathscr X}}\left(R(x) + \sum_{s=1}^{t-1}\langle x,
y_{s}\rangle \right).
\]

In words, this algorithm plays the action that minimizes the total
loss on the rounds until the present (``following the leader''),
subject to an additional regularization term. It is possible to
characterize the worst-case regret of an FTRL algorithm in terms of
properties of the regularizer $R$ and the sets ${\mathscr X}$ and ${\mathscr Y}$ (see
e.g. Theorem 15 of \cite{hazan2016introduction}). For our purposes, we
will only need the following two results for specific regularizers.

\begin{lemma}[Quadratic regularizer, \citep{Zinkevich2003}]
\label{lem:quadratic_regularizer}
Let $D_x = \diam {\mathscr X}$ and $D_y = \max_{y \in {\mathscr Y}} ||y||_2$. Let $x_0$
be an arbitrary element of ${\mathscr X}$, and let $R(x) = ||x - x_0||^2$. Then,
the FTRL algorithm with regularizer $R$ incurs worst-case regret at
most $O(D_xD_y\sqrt{T})$.
\end{lemma}

\begin{lemma}[Negative entropy regularizer, \citep{KivinenWarmuth1995}]
\label{lem:negent_regularizer}
Let ${\mathscr X} = \Delta_{d}$, ${\mathscr Y} = [0, 1]^d$, and let $R(x) =
\sum_{i=1}^{d} x_i\log x_i$ (where we extend this to the boundary of
${\mathscr X}$ by letting $0\log 0 = 0$). Then, the FTRL algorithm with
regularizer $R$ incurs worst-case regret at most $O(\sqrt{T \log d})$.
\end{lemma}

\subsection{Algorithms for $\ell_{\infty}$-approachability}
\label{sec:approachability}

We can now write down an explicit description of our algorithm for
$\ell_{\infty}$-approachability (in terms of a blackbox OLO algorithm)
and get quantitative bounds on the rate of convergence in the LHS of
\eqref{eq:approachability}. Let $\mathcal{F}$ be an OLO algorithm for the sets
${\mathscr X} = {\overline{\Delta}}_{d}$ and ${\mathscr Y} = [-1, 1]^d$. Then we can describe our
algorithm $\mathcal{A}$ for $\ell_{\infty}$-approachability as
Algorithm~\ref{algo:algorithm-linf-approach}.

\begin{algorithm2e}[ht]
\SetAlgoLined
Initialize $\theta_1$ to an arbitrary point in ${\overline{\Delta}}_d$\;
\BlankLine
\For{$t\leftarrow 1$  \KwTo $T$}{
  Choose $p_t \in {\mathscr P}$ so that for all $\ell \in {\mathscr L}$, $\langle
  \theta_t, u(p_t, \ell)\rangle \leq 0$. Such a $p_t$ is guaranteed to
  exist by the separability condition on $u$, since $\langle \theta, s
  \rangle \leq 0$ for any $\theta \in {\overline{\Delta}}_d$ and $s \in (-\infty,
  0]^d$\;
Play action $p_t$ and receive as feedback $\ell_t \in {\mathscr L}$\;
Set $y_t = -u(p_t, \ell_t)$\;
Set $\theta_{t+1} = \mathcal{F}(y_1, y_2, \dots, y_t)$.
}
\caption{Description of Algorithm $\mathcal{A}$ for $\ell_{\infty}$-approachability}
\label{algo:algorithm-linf-approach}
\end{algorithm2e}

It turns out that we can relate the $\ell_{\infty}$ approachability
distance to $(-\infty, 0]^{d}$ (and hence the regret of this algorithm
  $\mathcal{A}$) to the regret of our OLO algorithm $\mathcal{F}$.

\begin{theorem}\label{thm:linf_approachability}
We have that
$$\Reg(\mathcal{A}) = T \cdot
d_{\infty}\left(\frac{1}{T}\sum_{t=1}^{T}u(p_{t}, \ell_t), (-\infty,
0]^d \right) \leq \Reg(\mathcal{F}).$$
\end{theorem}

If we let $\mathcal{F}$ be the negative entropy FTRL algorithm (Lemma
\ref{lem:negent_regularizer})\footnote{There is a slight technical
difference between the sets $\mathcal{X} = {\overline{\Delta}}_d$ and $\mathcal{Y} = [-1, 1]^d$ in
Algorithm \ref{algo:algorithm-linf-approach} and the sets $\mathcal{X}' =
\Delta_d$ and $\mathcal{Y}' = [0, 1]^d$ in Lemma
\ref{lem:negent_regularizer}. However, note that if we map $x \in \mathcal{X}$
to $(x_1, x_2, \dots, x_n, 1 - \sum x_i) \in \Delta_{d+1}$ and $y \in
[-1, 1]^d$ to $((1+y_1)/2, (1+y_2)/2, \dots, (1+y_d)/2, 0) \in [0,
  1]^{d+1}$, we preserve the inner product of $x$ and $y$ up to an
additive constant, which disappears when computing regret, and a
factor of $1/2$.}, we obtain the following regret guarantee for $\mathcal{A}$.

\begin{corollary}
  \label{cor:linf_regret_minimization}
For any bilinear regret function $u\colon {\mathscr P} \times {\mathscr L} \rightarrow
[-1, 1]^d$, there exists a regret minimization algorithm $\mathcal{A}$ with
worst-case regret $\Reg(\mathcal{A}) = O(\sqrt{T \log d})$.
\end{corollary}

Equivalently, Corollary \ref{cor:linf_regret_minimization} can be
interpreted as saying that there exists an
$\ell_{\infty}$-approachability algorithm which approaches the
negative orthant at an average rate of $O(\sqrt{(\log d)/T})$. In
general, \eqref{eq:regret} lets us straightforwardly convert between
results for approachability and results for regret
minimization. Throughout the remainder of the paper we will primarily
phrase our results in terms of $\Reg(\mathcal{A})$, but switch between
quantities of interest when convenient.


\section{Main Results}
\label{sec:main}

Already Corollary \ref{cor:linf_regret_minimization} leads to a number
of impressive consequences. For example, when applied to the problem
of swap-regret minimization (where $u$ has dimension $d = K^K$), it
leads to a learning algorithm with $O(\sqrt{KT\log K})$ regret,
matching the best known regret bounds for this problem
\citep{BlumMansour2007}. However, the algorithm we obtain in this way
has two unfortunate properties.

First, since $u$ is $d$-dimensional, implementing the algorithm as
written above requires $O(\poly(d))$ time and space complexity (even
storing any specific $y_t$ or $\theta_t$ requires $\Omega(d)$
space). This is fine if $d$ is small, but in many of our applications
$d$ is much (e.g., exponentially) larger than the dimensions $m$ and
$n$ of the loss and action sets. For example, for swap regret we have
$d = K^K$ but $m = n = K$. Although Corollary
\ref{cor:linf_regret_minimization} gives us an optimal $O(\sqrt{KT\log
  K})$ swap regret algorithm, it takes exponential time / space to
implement (in contrast to other known swap regret algorithms, such as
that of \citet{BlumMansour2007}).

Secondly, although Corollary \ref{cor:linf_regret_minimization} has
only a logarithmic dependence on $d$, sometimes even this may be too
large (for example when we want to compete against an uncountable set
of benchmarks). In such cases, we would ideally like a regret bound
that depends on the action and loss sets but not directly on $d$.

In the following subsections, we will demonstrate a framework for
regret minimization that allows us to achieve both of these goals
(under some fairly light computational assumptions on $u$).

\subsection{Approachability for pseudonorms}
\label{sec:pseudonorm_approachability}

In Section \ref{sec:approachability}, we described the theory of
Blackwell approachability for a distance metric defined by the
$\ell_{\infty}$ norm (i.e., $||z||_{\infty} = \max_i |z_i|$). We begin
here by describing a generalization of this approachability theory to
functions we refer to as \emph{pseudonorms} and
\emph{pseudodistances}. A function $f \colon \mathbb{R}^{d} \to \mathbb{R}_{\geq
  0}$ is a pseudonorm if $f(0) = 0$, $f$ is positive homogeneous (for
all $z \in \mathbb{R}^{d}$, $\alpha \in \mathbb{R}_{\geq 0}$, $f(\alpha z) =
\alpha f(z)$), and $f$ satisfies the triangle inequality ($f(z + z')
\leq f(z) + f(z')$ for all $z, z' \in \mathbb{R}^{d}$). Note that unlike
norms, pseudonorms may not satisfy definiteness and are not
necessarily symmetric; it may be the case that $f(z) \neq
f(-z)$. However, all norms are pseudonorms. Note also that by the
positive homogeneity and the triangle inequality, a pseudonorm is a
convex function.  A pseudonorm $f$ defines a \emph{pseudodistance
function} $d_f$ via: $\forall z, z' \in \mathbb{R}^{d}, d_f(z, z') = f(z -
z')$.

In order to effectively work with pseudodistances, it will be useful
to define the dual set ${\mathscr T}^*_f$ associated to $f$ as follows:
${\mathscr T}^*_f = \curl*{\theta \colon \forall z \in \mathbb{R}^{d}, \tri*{\theta,
    z} \leq f(z)}$. This coincides with the traditional notion of
duality in convex analysis; for example, when $f$ is a norm, ${\mathscr T}^*_f$
coincides with the dual ball of radius one: ${\mathscr T}^*_f = \curl*{\theta
  \colon \norm*{\theta}_* \leq 1}$ (e.g., when $f$ is the
$d$-dimensional $\ell_{\infty}$ norm, ${\mathscr T}_{f}^*$ is the
$d$-dimensional $\ell_1$-ball). The following theorem relates the
pseudodistance between $z$ and a convex set ${\mathscr S}$ to a convex
optimization problem over the dual set.


\begin{restatable}{theorem}{GeneralFunction}
\label{th:general-function}
For any closed convex set ${\mathscr S} \subset \mathbb{R}^d$, the following
equality holds for any $z \in \mathbb{R}^d$:
\[
d_f(z, {\mathscr S}) 
= \inf_{s \in {\mathscr S}} f(z - s)
= \sup_{\theta \in {\mathscr T}^*_f} \curl*{\theta \cdot z
  - \sup_{s \in {\mathscr S}} \theta \cdot s}.
\]
\end{restatable}

\begin{proof}
We adopt the standard definition and notation in optimization for an
\emph{indicator function $I_{{\mathscr K}}$} of a set ${\mathscr K}$: for any $x$,
$I_{{\mathscr K}}(x) = 0$ if $x$ is in ${\mathscr K}$, $+\infty$ otherwise.
Define $\widetilde f$ by $\widetilde f(s) = f(z - s)$ for all $s \in \mathbb{R}^d$ and
set $g = I_{\mathscr S}$.

By definition, the conjugate function of $f$ is defined by: $\forall y
\in \mathbb{R}^d, f^*(y) = \sup_{x \in \mathbb{R}^{d}} x \cdot y - f(x)$. Now, if
$y$ is in ${\mathscr T}^*_f$, then we have $f^*(y) \leq f(x) - f(x) = 0$. Thus,
since $f(0) = 0$, the supremum in the definition of $f^*$ is achieved
for $x = 0$ and $f^*(0) = 0$. Otherwise, if $y \not \in {\mathscr T}^*_f$,
there exists $x \in {\mathscr X}$ such that $x \cdot y > f(x)$. 
For that $x$, for any
$t > 0$, by the positive
homogeneity of $f$, we have
$(tx) \cdot y - f(tx) 
= t \paren*{x \cdot y - f(x)} > 0$.
Taking the limit $t \to +\infty$, this shows that $f^*(y) =
+\infty$. Thus, we have $f^*(y) = I_{{\mathscr T}^*_f}$.

By definition, the conjugate function
$\widetilde f^*$ is defined for all $\theta$
by
$\widetilde f^*(\theta) 
= \sup_{x \in {\mathscr X}} x \cdot \theta - f(z - x)
= \sup_{u \in {\mathscr X}} (z - u) 
\cdot \theta - f(u)
= f^*(-\theta) + z \cdot \theta
= I_{{\mathscr T}^*_f}(-\theta) + z \cdot \theta$,
which can also be derived from the conjugate function calculus in Table B.1 of
\citep{MohriRostamizadehTalwalkar2018}.

It is also known that the
conjugate function of the indicator function $g$ is defined by $g^*
\colon \theta \mapsto \sup_{s \in {\mathscr S}} \theta \cdot s$
\citep{BoydVandenberghe2014}.
Since $\dom(\widetilde f) = \mathbb{R}^d$ and $\cont(g) = {\mathscr S}$, we have
$\dom(\widetilde f) \cap
\cont(g) = {\mathscr S} \neq \emptyset$.
Thus, for any convex and bounded set ${\mathscr S}$ in $\mathbb{R}^d$, by Fenchel
duality (Theorem~\ref{th:fenchel-duality},
Appendix~\ref{app:fenchel-duality}), we can write:
\begin{align*}
d_{f}(z, {\mathscr S}) 
& = \inf_{s \in {\mathscr S}} f(z - s)\\
& = \inf_{s \in \mathbb{R}^d} \curl*{f(z - s) + I_{\mathscr S}(s)}
\tag{def. of $I_{\mathscr S}$}\\
& = \sup_{\theta \in \mathbb{R}^d} \curl*{- \paren*{I_{{\mathscr T}^*_f}(-\theta)
    + \theta \cdot z} - \sup_{s \in {\mathscr S}} \curl*{-\theta \cdot s}}
\tag{Fenchel duality theorem}\\
& = \sup_{-\theta \in {\mathscr T}^*_f } \curl*{- \theta \cdot z
  - \sup_{s \in {\mathscr S}} \curl*{-\theta \cdot s}}
\tag{def. of $I_{{\mathscr T}^*_f}$}\\
& = \sup_{\theta \in {\mathscr T}^*_f } \curl*{\theta \cdot z
  - \sup_{s \in {\mathscr S}} \theta \cdot s}.
\tag{change of variable}
\end{align*}
This completes the proof.
\end{proof}

We will primarily be concerned with the case where ${\mathscr S}$ is a convex
cone. A \textit{convex cone} is a set ${\mathscr C}$ such that if $x \in {\mathscr C}$,
$\alpha x \in {\mathscr C}$ for all $\alpha \geq 0$. In this case, Theorem
\ref{th:general-function} can be simplified to write $d_f(z, {\mathscr C})$ as
a \textit{linear} optimization problem over the intersection of
${\mathscr T}^{*}_f$ and the polar cone of ${\mathscr C}$.

\begin{corollary}
\label{cor:quasidistance_olo}
Let ${\mathscr C}$ be a convex cone, and let ${\mathscr C}^{\circ} = \{y\,\mid\,\langle
y, x \rangle \leq 0\, \forall x \in {\mathscr C}\}$ be the polar cone of
${\mathscr C}$. Fix a $d$-dimensional pseudonorm $f$ and let ${\mathscr T}^{{\mathscr C}}_{f} =
{\mathscr T}^{*}_f \cap {\mathscr C}^{\circ}$. Then for any $z \in \mathbb{R}^d$,

$$d_f(z, {\mathscr C}) = \sup_{\theta \in {\mathscr T}^{{\mathscr C}}_{f}} (\theta \cdot z).$$
\end{corollary}



\subsection{From high-dimensional $\ell_{\infty}$
  approachability to low-dimensional pseudonorm approachability}
\label{sec:dimension_reduction}

In Section \ref{sec:approachability}, we expressed the regret for a
general regret minimization problem as the $\ell_{\infty}$ distance

\begin{equation}\label{eq:reg_inf}
\Reg = T \cdot d_{\infty}\left(\frac{1}{T}\sum_{t=1}^{T} u(p_t,
\ell_t), (-\infty, 0]^{d}\right).
\end{equation}

\noindent
In this section, we will demonstrate how to rewrite this in terms of a
lower-dimensional pseudodistance.

Consider the bilinear ``basis map'' $\widetilde{u}: {\mathscr P} \times {\mathscr L} \to
\mathbb{R}^{nm}$ given by $\widetilde{u}(p, \ell)_{i, j} = p_{i}\ell_{j}$. Note
that every bilinear function $b\colon {\mathscr P} \times {\mathscr L} \to
\mathbb{R}$ can be written in the form $b(p, \ell) = \langle \widetilde{u}(p,
\ell), v\rangle$ for some vector $v \in \mathbb{R}^{nm}$ (i.e., the
monomials in $\widetilde{u}$ form a basis for the set of biaffine functions on
${\mathscr P} \times {\mathscr L}$)\footnote{If it is helpful, one can think of $\widetilde{u}$
as the natural map from ${\mathscr P} \times {\mathscr L}$ to the tensor product
${\mathscr P}\,\otimes\,{\mathscr L}$. The vectors $v_i$ can then be thought of as
elements of the dual space, each representing a linear functional on
${\mathscr P}\,\otimes\,{\mathscr L}$.}.

Let $v_i \in \mathbb{R}^{nm}$ be the vector of coefficients
corresponding to the component $u_i$ of $u$ and consider the function
$f(x) = \max(\max_{i \in [d]} \tri{v_i, x}, 0)$. Note that $f$ is a
pseudonorm on $\mathbb{R}^{nm}$; indeed, it's straightforward to see
that $f$ is non-negative and $f(\alpha x) = \alpha f(x)$ for any
$\alpha \geq 0$. In addition, let ${\mathscr C}$ be the convex cone defined by
${\mathscr C} = \{x\,\mid\, \langle x, v_i \rangle \leq 0\, \forall i \in
[d]\}$. We claim that that we can rewrite the $\ell_{\infty}$ distance
in \eqref{eq:reg_inf} in the following way.

\begin{theorem}
  \label{thm:dimension_reduction}
We have that
\begin{equation}
  d_{\infty}\left(\frac{1}{T}
  \sum_{t=1}^{T} u(p_t, \ell_t), (-\infty, 0]^{d}\right)
    = d_{f}\left(\frac{1}{T}\sum_{t=1}^{T} \widetilde{u}(p_t, \ell_t), {\mathscr C}\right).
\end{equation}
\end{theorem}
The dual set ${\mathscr T}^*_{f}$ associated to this pseudonorm is given by:
\[
{\mathscr T}^*_{f} = \curl*{\widetilde{\theta} \in \mathbb{R}^{nm}\colon \forall x \in
  \mathbb{R}^{nm}, \tri{\widetilde{\theta}, x} \leq \max_{i \in [d]} \tri{v_i, x}}.
\]

The following two properties of this dual set will be useful in the
sections that follow. First, we show that we can alternately think of
${\mathscr T}^*_{f}$ as the convex hull of the $v_i$.

\begin{lemma}
\label{lemma:DualSet}
The dual set ${\mathscr T}^*_{f}$ coincides with the convex hull of $v_i$s:
${\mathscr T}^*_{f}
= \conv \curl*{v_1, \ldots, v_d}$.
\end{lemma}


Secondly, we show that the dual set ${\mathscr T}_{f}^*$ is contained within
the polar cone ${\mathscr C}^{\circ}$ of ${\mathscr C}$.

\begin{lemma}
\label{lemma:containment}
We have that ${\mathscr T}_{f}^* \subseteq {\mathscr C}^{\circ}$, where ${\mathscr C}^{\circ} =
\{y\,\mid\, \langle y, x\rangle \leq 0 \, \forall x \in {\mathscr C}\}$.
\end{lemma}
\begin{proof}
By Lemma \ref{lemma:DualSet}, it suffices to show that each $v_i \in
{\mathscr C}^{\circ}$, i.e., for each $v_i$, that $\langle v_i, x \rangle \leq
0$ for all $x \in {\mathscr C}$. However, this immediately follows by the
definition of ${\mathscr C}$, since each $x \in {\mathscr C}$ satisfies $\langle x, v_i
\rangle \leq 0$ for all $i \in [d]$. (An equivalent way of thinking
about this is that ${\mathscr C}$ is already the polar cone of the cone
generated by the $v_i$, so the $v_i$ must lie in the polar to ${\mathscr C}$).
\end{proof}

This allows us to simplify Corollary \ref{cor:quasidistance_olo} even further.

\begin{corollary}
\label{cor:regret_olo}
For this convex cone ${\mathscr C}$ and pseudonorm $f$, we have that for any $z
\in \mathbb{R}^{mn}$,

$$d_{f}(z, {\mathscr C}) = \sup_{\widetilde{\theta} \in {\mathscr T}_{f}^*}
\left\langle \widetilde{\theta}, z \right\rangle.$$
\end{corollary}

Finally, we prove the following ``separability'' conditions for this
approachability problem.

\begin{lemma}\label{lemma:low-dim-separability}
The following two statements are true.

\begin{enumerate}
    \item For any $\ell \in {\mathscr L}$, there exists a $p \in {\mathscr P}$ such that
      $\widetilde{u}(p, \ell) \in {\mathscr C}$.
      
    \item For any $\widetilde{\theta} \in {\mathscr T}_{f}^*$, there exists a $p \in {\mathscr P}$
      such that $\tri{\widetilde{\theta}, \widetilde{u}(p, \ell)} \leq 0$ for all $\ell
      \in {\mathscr L}$.
\end{enumerate}
\end{lemma}

\subsection{Algorithms for pseudonorm approachability}
\label{sec:pseudonorm_alg}

We now present an algorithm for pseudonorm approachability in the
setting of Section \ref{sec:dimension_reduction} (i.e., for the
bilinear function $\widetilde{u}$ and the convex cone ${\mathscr C}$). Just as the
algorithm in Section \ref{sec:approachability} for
$\ell_{\infty}$-approachability required an OLO algorithm for the
simplex, this algorithm will assume we have access to an OLO algorithm
$\widetilde{\cF}$ for the sets ${\mathscr X} = {\mathscr T}_{f}^*$, and ${\mathscr Y} = -\conv(\widetilde{u}({\mathscr P},
{\mathscr L}))$ (recall that $\conv(\widetilde{u}({\mathscr P}, {\mathscr L}))$ denotes the convex hull of
the points $\widetilde{u}(p, \ell) \in \mathbb{R}^{nm}$ for $p \in {\mathscr P}$ and $\ell
\in {\mathscr L}$).



\begin{algorithm2e}
\SetAlgoLined
Initialize $\widetilde{\theta}_1$ to an arbitrary point in ${\mathscr T}_{f}^*$\;
\BlankLine
\For{$t\leftarrow 1$  \KwTo $T$}{
Choose $p_t \in {\mathscr P}$ so that for all $\ell \in {\mathscr L}$, $\langle \widetilde{\theta}_t, \widetilde{u}(p_t, \ell)\rangle \leq 0$ (such a $p_t$ is guaranteed to exist by the second statement in Lemma \ref{lemma:low-dim-separability})\;
Play action $p_t$ and receive as feedback $\ell_t \in {\mathscr L}$\;
Set $y_t = -\widetilde{u}(p_t, \ell_t)$\;
Set $\widetilde{\theta}_{t+1} = \widetilde{\cF}(y_1, y_2, \dots, y_t)$.
}
\caption{Description of Algorithm $\widetilde{\cA}$ for $f$-approachability}
\label{algo:algorithm-pseudonorm-approach}
\end{algorithm2e}

Our algorithm $\widetilde{\cA}$ is summarized above in Algorithm
\ref{algo:algorithm-pseudonorm-approach}. We now have the following
analogue of Theorem \ref{thm:linf_approachability}.

\begin{theorem}
\label{thm:pseudonorm_approachability}
The following guarantee holds for the pseudonorm approachability algorithm
$\widetilde{\cA}$:
$$\Reg(\widetilde{\cA}) = T \cdot d_f\left(\frac{1}{T}\sum_{t=1}^{T}\widetilde{u}(p_{t},
\ell_t), {\mathscr C} \right) \leq \Reg(\widetilde{\cF}).$$
\end{theorem}
\begin{proof}
The first equality follows as a direct consequence of Theorem
\ref{thm:dimension_reduction} (which proves that the $d_f$ distance to
${\mathscr C}$ is equal to the analogous $\ell_{\infty}$ distance to $(-\infty,
0]^d$) and Theorem \ref{thm:linf_approachability} (which shows that
  this $\ell_{\infty}$ distance is equal to the regret of our regret
  minimization problem). It therefore suffices to prove the second
  equality.

Note that
\begin{eqnarray*}
d_f\left(\frac{1}{T}\sum_{t=1}^{T}\widetilde{u}(p_{t}, \ell_t), {\mathscr C} \right) &=& \sup_{\widetilde{\theta} \in {\mathscr T}_{f}^*} \left\langle \widetilde{\theta}, \frac{1}{T}\sum_{t=1}^{T}\widetilde{u}(p_{t}, \ell_t)\right\rangle\\
&=& -\inf_{\widetilde{\theta} \in {\mathscr X}} \left\langle \widetilde{\theta}, \frac{1}{T}\sum_{t=1}^{T}\left(-\widetilde{u}(p_{t}, \ell_t)\right)\right\rangle\\
&=& \frac{1}{T}\Reg(\widetilde{\cF}) - \frac{1}{T}\sum_{t=1}^{T}\left\langle \widetilde{\theta}_t, -\widetilde{u}(p_{t}, \ell_t)\right\rangle \\
&\leq& \frac{1}{T}\Reg(\widetilde{\cF}).
\end{eqnarray*}

Here, the first equality holds as a consequence of Corollary
\ref{cor:regret_olo}, and the last inequality holds since (by choice
of $p_t$ in step 2a) $\langle \widetilde{\theta}_t, \widetilde{u}(p_t, \ell)\rangle \leq
0$ for all $t \in [T]$.
\end{proof}

If we choose $\widetilde{\cF}$ to be FTRL with a quadratic regularizer, Lemma
\ref{lem:quadratic_regularizer} implies the following result.

\begin{theorem}
\label{thm:poly_regret}
Let $u\colon {\mathscr P} \to {\mathscr L}$ be a bilinear regret function. Then
there exists a regret minimization algorithm $\widetilde{\cA}$ for $u$ with
regret

$$\Reg(\widetilde{\cA}) = O(D_{z}(\diam {\mathscr P})(\diam {\mathscr L})\sqrt{T}),$$

\noindent
where $D_{z} = \max_{i \in [d]} ||v_i||$. If we let 

$$\lambda = \max_{i \in [d]} ||v_{i}||_{\infty} = \max_{i \in [d], j \in [m], k \in [n]} \left| \frac{\partial^2 u_i}{\partial p_j \partial \ell_k} \right|,$$

\noindent
then this regret bound further satisfies

$$\Reg(\widetilde{\cA}) = O(\lambda nm \sqrt{T}).$$
\end{theorem}
\begin{proof}
To see the first result, note that
Lemma~\ref{lem:quadratic_regularizer} directly implies a bound of
$O(\diam({\mathscr X})\diam({\mathscr Y})\sqrt{T})$, where ${\mathscr X} = {\mathscr T}_{f}^{*}$ and ${\mathscr Y}
= -\conv(\widetilde{u}({\mathscr P}, {\mathscr L}))$. We'll now proceed by simplifying
$\diam({\mathscr X})$ and $\diam({\mathscr Y})$. First, for ${\mathscr X}$, recall from Lemma
\ref{lemma:DualSet} that ${\mathscr X} = {\mathscr T}_{f}^*$ is the convex hull of the
$d$ vectors $v_i \in \mathbb{R}^{nm}$, so $\diam({\mathscr X}) = O(\max_{i \in [d]}
||v_i||) = O(D_z)$. Second, for ${\mathscr Y}$, note that $\diam({\mathscr Y}) =
O(\max_{y \in {\mathscr Y}} ||y||) = O(\max_{p \in {\mathscr P}, \ell \in {\mathscr L}}||\widetilde{u}(p,
\ell)||)$. But $||\widetilde{u}(p, \ell)|| = ||p|| \cdot ||\ell||$, so
$\diam({\mathscr Y}) = O\left(\max_{p \in {\mathscr P}}||p|| \cdot \max_{\ell \in
  {\mathscr L}}||\ell||\right) = O((\diam{\mathscr P})(\diam {\mathscr L}))$. Combining these, we
obtain the first inequality.

The second result directly follows from the following three facts:
i. $\diam {\mathscr P} = O(\sqrt{n})$ (since ${\mathscr P} \subseteq [-1, 1]^n$,
ii. $\diam {\mathscr L} = O(\sqrt{m})$ (since ${\mathscr L} \subseteq [-1, 1]^m$), and
iii. $D_z \leq \lambda \sqrt{mn}$.
\end{proof}

Theorem \ref{thm:poly_regret} shows that in settings where $\lambda$
is constant (which is true in all the settings we consider), there
exists an algorithm where $\Reg(\widetilde{\cA}) = \poly(n, m) \sqrt{T}$;
notably, $\Reg(\widetilde{\cA})$ does not depend on the dimension $d$, which in
many cases can be thought of as the number of benchmarks of comparison
for our learning algorithm.

In the following two sections, we will show how to strengthen this
result in two different ways. First, we will show that (modulo some
fairly mild computational assumptions) it is possible to efficiently
implement the algorithm of Theorem \ref{thm:poly_regret}. Second, we
will show that by using a different choice of regularizer, we can
recover exactly the regret obtained in Corollary
\ref{cor:linf_regret_minimization}.

\subsection{Efficient algorithms for pseudonorm approachability}

\subsubsection{Computational assumptions}

In this section we will discuss how to transform the algorithm in
Theorem \ref{thm:poly_regret} into a computationally efficient
algorithm. Note that without any constraints on ${\mathscr L}$, ${\mathscr P}$, and $u$
or how they are specified, performing any sort of regret minimization
efficiently is a hopeless task (e.g., consider the case where it is
computationally hard to even determine membership in ${\mathscr P}$). We'll
therefore make the following three structural / computational
assumptions on ${\mathscr L}$, ${\mathscr P}$, and $u$.

First, we will restrict our attention to cases where the loss set
${\mathscr L}$ is ``orthant-generating''. A convex subset $S$ of $\mathbb{R}^d$ is
\textit{orthant-generating} if $S \subseteq [0, \infty)^d$ and for
  each $i \in [d]$, there exists an $\lambda_i > 0$ such that
  $\lambda_ie_i \in S$ (as part of this assumption, we will also
  assume we have access to the values $\lambda_i$). Note that many
  common choices for ${\mathscr L}$ (e.g., $[0, 1]^m$, $\Delta_m$,
  intersections of other $\ell_p$ balls with the positive orthant) are
  all orthant-generating.

Second, we will assume we have an \textit{efficient separation oracle}
for the action set ${\mathscr P}$; that is, an oracle which takes a $p \in
\mathbb{R}^n$ and outputs (in time $\poly(n)$) either that $p \in {\mathscr P}$ or a
separating hyperplane $h \in \mathbb{R}^n$ such that $\langle p, h \rangle
> \max_{p' \in {\mathscr P}} \langle p', h \rangle$.

Finally, we will assume we have access to what we call an
\textit{efficient regret oracle} for $u$. Given a collection of $R$
action/loss pairs $(p_r, \ell_{r}) \in {\mathscr P} \times {\mathscr L}$ and $R$
positive constants $\alpha_r \geq 0$, an efficient regret oracle can
compute (in time $\poly(n, m, R)$) the value of $\max_{i \in [d]}
\sum_{r=1}^{R} \alpha_r u_i(p_r, \ell_r)$. This can be thought of as
evaluating the function $\Reg(\bm{p}, \bm{\ell})$ for a pair of action
and loss sequences that take on the action/loss pair $(p_r, \ell_r)$
an $\alpha_r/\sum_{r'}\alpha_{r'}$ fraction of the time. At a higher
level, having access to an efficient regret oracle means that a
learner can efficiently compute their overall regret at the end of $T$
rounds (it is hard to imagine how one could efficiently minimize
regret without being able to compute it).

\subsubsection{Extending the dual set}

One of the ingredients we will need to implement algorithm $\widetilde{\cA}$ is
a membership oracle for the dual set ${\mathscr T}_{f}^*$ (e.g.\ in order to
perform OLO over this dual set). To check whether $\widetilde{\theta} \in
{\mathscr T}_{f}^*$, it suffices to check whether $\langle \widetilde{\theta}, x\rangle
\leq \max_{i \in [d]} \langle v_{i}, x \rangle$ for all $x \in
\mathbb{R}^{nm}$, so in turn, it will be useful to be able to compute the
function $\max_{i \in [d]} \langle v_i, x \rangle$ for any $x \in
\mathbb{R}^{nm}$.

Computing this maximum is \textit{very similar}\footnote{In fact, in
almost all practical cases where we have an efficient regret oracle,
it is possible by a similar computation to directly compute this
maximum. Here we describe an approach that works in a blackbox way
given only a strict regret oracle -- if you are accept the existence
of an oracle that can optimize linear functions over the $v_i$, you
can skip this subsection.} to what is provided by our regret oracle:
note that by writing $u_i(p_r, \ell_r)$ as $\langle v_i, \widetilde{u}(p_r,
\ell_r)\rangle$, we can think of the regret oracle providing the value
of:

$$\max_{i \in [d]} \left\langle v_i, \sum_{r=1}^{R}\alpha_r \widetilde{u}(p_r,
\ell_r) \right\rangle.$$

If it were possible to write any $x \in \mathbb{R}^{d}$ in the form
$\sum_{r=1}^{R}\alpha_r \widetilde{u}(p_r, \ell_r)$, we would be done. However,
this may not be possible: in particular, $\sum_{r=1}^{R}\alpha_r
\widetilde{u}(p_r, \ell_r)$ must lie in the convex cone $\cone(\widetilde{u}({\mathscr P}, {\mathscr L}))$
generated by all points of the form $\widetilde{u}(p, \ell)$.

We will therefore briefly generalize the theory of Section
\ref{sec:pseudonorm_approachability} to cases where we are only
able to optimize over an extension of the dual set. Given a convex
cone ${\mathscr Z}$, let ${\mathscr T}_{f}^{*}({\mathscr Z}) = \{\theta\,\mid\, \forall z \in
{\mathscr Z}, \tri{\theta, z} \leq f(z)\}$. Note that ${\mathscr T}_{f}^{*} \subseteq
{\mathscr T}_{f}^{*}({\mathscr Z})$ (since in ${\mathscr T}_{f}^*$, $\tri{\theta, z} \leq f(z)$
must hold for all $z$ in the ambient space). The following lemma shows
that if $z$ is in ${\mathscr Z}$, to maximize a linear function over
${\mathscr T}_{f}^*$ it suffices to maximize it over ${\mathscr T}_{f}^*({\mathscr Z})$.

\begin{lemma}
\label{lem:dual_extension}
Let ${\mathscr Z}$ be an arbitrary convex cone. Then if $z \in {\mathscr Z}$, the
following equalities hold:
\[
\sup_{\theta \in {\mathscr T}^{*}_f} \tri{\theta, z}
= \sup_{\theta \in {\mathscr T}^{*}_f({\mathscr Z})} \tri{\theta, z} = f(z).
\]
\end{lemma}

Now, consider the specific convex cone ${\mathscr Z} = \cone(\widetilde{u}({\mathscr P},
{\mathscr L}))$. Given Lemma \ref{lem:dual_extension}, it is straightforward to
check that Theorem \ref{thm:pseudonorm_approachability} continues to
hold even if the domain ${\mathscr X}$ of the OLO algorithm $\widetilde{\cF}$ is set to
${\mathscr T}_{f}^*({\mathscr Z})$ instead of ${\mathscr T}_{f}^*$. In particular, the first
equality in the proof of Theorem \ref{thm:pseudonorm_approachability}
is still true when ${\mathscr T}_{f}^*$ is replaced by ${\mathscr T}_{f}^*({\mathscr Z})$, since
$\frac{1}{T}\sum_{t}\widetilde{u}(p_t, \ell_t) \in {\mathscr Z}$.

There is one other issue we must deal with: it is possible that
${\mathscr T}_{f}^*({\mathscr Z})$ is significantly larger than ${\mathscr T}_{f}^*$, and
therefore an OLO algorithm with domain ${\mathscr T}_{f}^*({\mathscr Z})$ might incur
more regret than that of ${\mathscr T}_{f}^{*}$. In fact, there are cases where
the set ${\mathscr T}_{f}^*({\mathscr Z})$ is unbounded. Nonetheless, the following
lemma shows that for OLO with a quadratic regularizer, we will never
encounter very large values of $\widetilde{\theta}$.

\begin{lemma}
\label{lemma:bound_extension}
Let $R(\widetilde{\theta}) = ||\widetilde{\theta}||^2$, and fix a $z \in {\mathscr Z}$ and $\eta >
0$. Let

$$\widetilde{\theta}_{opt} = \argmin_{\widetilde{\theta} \in {\mathscr T}_{f}^*({\mathscr Z})}\left(\eta
R(\widetilde{\theta}) - \langle \widetilde{\theta}, z \rangle\right).$$

\noindent
Then $||\widetilde{\theta}_{opt}|| \leq \diam({\mathscr T}_{f}^*)$.
\end{lemma}

Lemma \ref{lemma:bound_extension} therefore implies that a
quadratic-regularized OLO algorithm $\widetilde{\cF}$ will only output values of
$\widetilde{\theta}$ with $||\widetilde{\theta}|| \leq \diam({\mathscr T}_{f}^*)$, and therefore we
can safely set ${\mathscr X} = {\mathscr T}_{f}^* \cap \{\theta \mid ||\theta|| \leq
\rho\}$, where $\rho = \Theta(\diam({\mathscr T}_{f}^*))$ is an efficiently
computable upper bound on $\diam({\mathscr T}_{f}^*)$. This guarantees that
$\diam({\mathscr X}) = O(\diam({\mathscr T}_{f}^*))$, and thus the regret guarantees of
Theorem \ref{thm:poly_regret} remain unchanged.

\subsubsection{Constructing a membership oracle}

We will now demonstrate how to use our regret oracle to construct a
membership oracle for the expanded set ${\mathscr X}$ defined in the previous
section. We first show that it is possible to check for membership in
${\mathscr Z}$ (and further, when $z \in {\mathscr Z}$, write $z$ as a convex
combination of the generators of ${\mathscr Z}$).

\begin{lemma}
\label{lem:z_membership}
Given a point $z \in \mathbb{R}^{nm}$, we can efficiently check whether $z
\in {\mathscr Z}$. If $z \in {\mathscr Z}$, we can also efficiently write $z$ in the
form $\sum_{k=1}^{m}\alpha_k \widetilde{u}(p_k, \ell_k)$ (for an explicit
choice of $p_k$, $\ell_k$, and $\alpha_k$).
\end{lemma}

Note that expressing $z$ in the form $\sum_{k=1}^{m}\alpha_k \widetilde{u}(p_k,
\ell_k)$ allows us to directly apply our efficient regret oracle (with
$R = m$). We therefore gain the following optimization oracle as a
corollary.

\begin{corollary}
\label{cor:eval_max}
Given an efficient regret oracle, for any $z \in {\mathscr Z}$ we can efficiently (in time $\poly(n, m)$) compute $\max_{i \in [d]} \langle v_i, z \rangle$.
\end{corollary}

Finally, we will show that given these two results, we can efficiently
construct a membership oracle for our set ${\mathscr X}$. To do this, we will
need the following fact (loosely stated; see Lemma
\ref{lemma:convex-opt} in Appendix \ref{app:fenchel-duality} for an
accurate statement): it is possible to minimize a convex function over
a convex set as long as one has an evaluation oracle for the function
and a membership oracle for the convex set.

\begin{lemma}
\label{lem:x_membership}
Given an efficient regret oracle for $u$, we can construct an efficient membership oracle for the set ${\mathscr X}$.
\end{lemma}

\subsubsection{Implementing regret minimization}

Equipped with this membership oracle, we can now state and prove our main theorem.

\begin{theorem}
\label{thm:efficient_alg}
Assume that:

\begin{enumerate}
    \item The convex set ${\mathscr L}$ is orthant-generating.
   
    \item We have an efficient separation oracle for the convex set ${\mathscr P}$.
    \item We have an efficient regret oracle for the regret function $u$.
\end{enumerate}

\noindent
Then it is possible to implement the algorithm of Theorem \ref{thm:poly_regret} in $\poly(n, m)$ time per round.
\end{theorem}
\begin{proof}
There are two steps of unclear computational complexity in the
description of the algorithm in Section \ref{sec:pseudonorm_alg}: step
2a, where we find a $p_t$ such that $\langle \widetilde{\theta}_t, \widetilde{u}(p_t,
\ell)\rangle \leq 0$ for all $\ell \in {\mathscr L}$, and step 2d, where we
have to run our OLO subalgorithm over ${\mathscr T}_{f}^*$ (which we
specifically instantiate as FTRL with a quadratic regularizer).

We begin by describing how to perform step 2a efficiently. Fix a
$\widetilde{\theta}_t$. Note that since ${\mathscr L}$ is orthant-generating, to check
whether $\langle \widetilde{\theta}_t, \widetilde{u}(p_t, \ell)\rangle \leq 0$ for all
$\ell \in {\mathscr L}$, it suffices to check whether $\widetilde{u}(p_t, e_k) \leq 0$
for each unit vector $e_k \in \mathbb{R}^{m}$. Therefore, to find a valid
$p_t$ we must find a point $p_t \in {\mathscr P}$ that satisfies an additional
$m$ explicit linear constraints. Since we have an efficient separation
oracle for ${\mathscr P}$, this is possible in $\poly(n, m)$ time.

To implement the FTRL algorithm $\mathcal{F}$ over the set ${\mathscr X} = {\mathscr T}_{f}^*$
with a quadratic regularizer, each round we must find the minimizer of
the convex function $g(\widetilde{\theta}) = R(\widetilde{\theta}) + \eta\sum_{s=1}^{t-1}
\langle \widetilde{\theta}, \widetilde{u}(p_s, \ell_s)\rangle$ over the convex set
${\mathscr X}$. To do this, it suffices to exhibit an evaluation oracle for $g$
and a membership oracle for ${\mathscr X}$. To evaluate $g$, note that we
simply need to be able to compute $R(\widetilde{\theta})$ (which is a Euclidean
distance in $\mathbb{R}^{mn}$) and $\sum_{s=1}^{t-1} \langle \widetilde{\theta},
\widetilde{u}(p_s, \ell_s)\rangle$ which we can do in $O(mn)$ time by keeping
track of the cumulative sum $\sum_{s=1}^{t-1} \widetilde{u}(p_s, \ell_s)$ and
computing a single inner product in $\mathbb{R}^{mn}$. A membership oracle
for ${\mathscr X}$ is provided by Lemma \ref{lem:x_membership}.
\end{proof}



\subsection{Recovering $\ell_{\infty}$ regret via maxent regularizers}

One interesting aspect of this reduction to pseudonorm approachability
is that, in some cases, the regret bound of $O(\sqrt{T\log d})$
achievable via $\ell_{\infty}$-approachability (Corollary
\ref{cor:linf_regret_minimization}) sometimes outperforms the regret
bound of $O(\lambda mn\sqrt{T})$ achieved by pseudonorm
approachability (Theorem \ref{thm:poly_regret}), for example when $d =
\poly(m, n)$. Of course, this comparison is not completely fair: in
both cases there is flexibility to specify the underlying OLO
algorithm, and the $O(\sqrt{T\log d})$ bound uses an FTRL algorithm
with a negative entropy regularizer, whereas our pseudonorm
approachability bound uses an FTRL algorithm with a quadratic
regularizer. After all, there are well-known cases (e.g.\ for OLO over
a simplex, as in $\ell_{\infty}$-approachability) where the negative
entropy regularizer leads to exponentially better (in $d$) regret
bounds than the quadratic regularizer.

In this subsection, we will show that there exists a different
regularizer for pseudonorm approachability -- one we call a
\textit{maxent regularizer} -- which recovers the $O(\sqrt{T\log d})$
regret bound of Corollary \ref{cor:linf_regret_minimization}.  In
doing so, we will also better understand the parallels between the
regret minimization algorithm $\mathcal{A}$ (which works via reduction to
$\ell_{\infty}$-approachability in a $d$-dimensional space) and the
regret minimization algorithm $\widetilde{\cA}$ (which works via reduction to
pseudonorm approachability in an $nm$-dimensional space).

Let $V$ be the $d$-by-$nm$ matrix whose $i$th row equals $v_i$. Note
that $V$ allows us to translate between analogous concepts/quantities
for $\mathcal{A}$ and $\widetilde{\cA}$ in the following way.

\begin{lemma}
  \label{lemma:translation}
The following statements are true:

\begin{itemize}

\item For any $p \in {\mathscr P}$ and $\ell \in {\mathscr L}$, $u(p, \ell) = V\widetilde{u}(p, \ell)$.

\item The dual set ${\mathscr T}_{f}^* = V^{T}\Delta_d$ (i.e., $\widetilde{\theta} \in
  {\mathscr T}_{f}^*$ iff there exists a $\theta \in \Delta_d$ such that
  $\widetilde{\theta} = V^{T}\theta$).

\item If $\theta \in \Delta_d$ and $\widetilde{\theta} = V^{T}\theta \in
  {\mathscr T}_{f}^*$, then for any $p \in {\mathscr P}$ and $\ell \in {\mathscr L}$,
  $\tri{\theta, u(p, \ell)} = \tri{\widetilde{\theta}, \widetilde{u}(p, \ell)}$.

\item Fix $\theta_t \in \Delta_d$ and let $\widetilde{\theta} = V^{T}\theta$. If
  $p_t$ satisfies $\tri{\theta_t, u(p_t, \ell)} \leq 0$ for all $\ell
  \in {\mathscr L}$, then $p_t$ also satisfies $\tri{\widetilde{\theta}_t, \widetilde{u}(p_t,
    \ell)} \leq 0$ for all $\ell \in {\mathscr L}$.
\end{itemize}
\end{lemma}
\begin{proof}
The first statement follows from the fact that $V\widetilde{u}(p, \ell)_i =
\langle v_i, \widetilde{u}(p, \ell)\rangle = u(p, \ell)_i$. The second claim
follows as a consequence of Lemma \ref{lemma:DualSet} (that
${\mathscr T}_{f}^*$ is the convex hull of the vectors $v_i$). The third claim
follows from the first claim: $\langle \theta, u(p, \ell)\rangle =
\langle \theta, V\widetilde{u}(p, \ell) \rangle = \langle V^{T}\theta, \widetilde{u}(p,
\ell) \rangle = \langle \widetilde{\theta}, \widetilde{u}(p, \ell) \rangle$. Finally, the
fourth claim follows directly from the third claim.
\end{proof}

Now, fix a regret minimization problem (specified by ${\mathscr P}$, ${\mathscr L}$, and
$u$) and consider the execution of algorithm $\mathcal{A}$ on some specific
loss sequence $\bm{\ell} = (\ell_1, \ell_2, \dots, \ell_{T})$. Each
round $t$, $\mathcal{A}$ runs the entropy-regularized FTRL algorithm $\mathcal{F}$ to
generate a $\theta_t \in \Delta_d$ (as a function of the actions and
losses up until round $t$) and then uses $\theta_t$ to select a $p_t$
that satisfies $\tri{\theta_t, u(p_t, \ell)} \leq 0$ for all $\ell \in
{\mathscr L}$. If we execute algorithm $\widetilde{\cA}$ for the same regret minimization
problem on the same loss sequence, each round $t$, $\widetilde{\cA}$ runs some
(to be determined) FTRL algorithm $\widetilde{\cF}$ to generate a $\widetilde{\theta}_t
\in {\mathscr T}_{f}^*$, and then uses $\widetilde{\theta}_t$ to select a $p_t$ that
satisfies $\tri{\widetilde{\theta}_t, \widetilde{u}(p_t, \ell)}$ for all $\ell \in
{\mathscr L}$. Lemma \ref{lemma:translation} shows that if $\widetilde{\theta}_t =
V^{T}\theta_t$ for each $t$, then both algorithms will generate
\textit{exactly the same} sequence of actions in response to this loss
sequence\footnote{Technically, there may be some leeway in terms of
which $p_t$ to choose that e.g. satisfies $\tri{\theta_t, u(p_t,
  \ell)} \leq 0$ for all $\ell \in {\mathscr L}$, and the two different
procedures could result in different choices of $p_t$. But if we break
ties consistently (e.g. add the additional constraint of choosing the
$p_t$ that maximizes the inner product of $p_t$ with some generic
vector), then both procedures will produce the same value of $p_t$.},
and hence the same regret.

The question then becomes: how do we design an OLO algorithm $\widetilde{\cF}$
that outputs $\widetilde{\theta}_t = V^{T}\theta_t$ each round that $\mathcal{F}$ would
output $\theta_t$? Recall that if $\mathcal{F}$ is an FTRL algorithm with
regularizer $R:\Delta_d \to \mathbb{R}$, then

\[
\theta_t = \argmin_{\theta \in \Delta_d}\left(R(\theta) +
\sum_{s=1}^{t-1}\langle \theta, u(p_t, \ell_t)\rangle\right).
\]
Define $\widetilde{R}:{\mathscr T}_{f}^* \to \mathbb{R}$ via

\begin{equation}
    \widetilde{R}(\widetilde{\theta}) = \min_{\substack{\theta \in \Delta_d\\V^{T}\theta = \widetilde{\theta}}}R(\theta).
\end{equation}

We claim that if we let $\widetilde{\cF}$ be the FTRL algorithm that uses
regularizer $\widetilde{R}$, then $\widetilde{\cF}$ will output our desired sequence of
$\widetilde{\theta}_t$.

\begin{lemma}
The following equality holds for the output $\widetilde{\theta}_t$:
$$\widetilde{\theta}_t = \argmin_{\widetilde{\theta} \in {\mathscr T}_{f}^*}\left(\widetilde{R}(\widetilde{\theta}) +
\sum_{s=1}^{t-1}\langle \widetilde{\theta}, \widetilde{u}(p_t, \ell_t)\rangle\right) =
V^{T}\theta_t.$$
\end{lemma}
\begin{proof}
Note that we can write

\begin{eqnarray*}
\widetilde{\theta}_t &=& \argmin_{\widetilde{\theta} \in {\mathscr T}_{f}^*}\left(\widetilde{R}(\widetilde{\theta}) + \sum_{s=1}^{t-1}\langle \widetilde{\theta}, \widetilde{u}(p_t, \ell_t)\rangle\right)\\
&=& \argmin_{\widetilde{\theta} \in {\mathscr T}_{f}^*}\left(\left(\min_{\substack{\theta \in \Delta_d\\V^{T}\theta = \widetilde{\theta}}}R(\theta)\right) + \sum_{s=1}^{t-1}\langle \widetilde{\theta}, \widetilde{u}(p_t, \ell_t)\rangle\right)\\
&=& \argmin_{\widetilde{\theta} \in {\mathscr T}_{f}^*}\left(\min_{\substack{\theta \in \Delta_d\\V^{T}\theta = \widetilde{\theta}}}\left(R(\theta) + \sum_{s=1}^{t-1}\tri{\theta, u(p_t, \ell_t)}\right)\right) \\
&=& V^{T}\argmin_{\theta \in \Delta_d}\left(R(\theta) + \sum_{s=1}^{t-1}\tri{\theta, u(p_t, \ell_t)}\right) \\
&=& V^{T}\theta_t.
\end{eqnarray*}

\noindent
The third equality follows from the fact that if $\widetilde{\theta} =
V^{T}\theta$, then $\tri{\theta, u(p, \ell)} = \tri{\widetilde{\theta}, \widetilde{u}(p,
  \ell)}$ (by Lemma~\ref{lemma:translation}).
\end{proof}

\begin{corollary}
\label{cor:maxent_regularizer}
Let $\mathcal{F}$ be an FTRL algorithm over $\Delta_{d}$ with regularizer $R$,
and let $\widetilde{\cF}$ be an FTRL algorithm over ${\mathscr T}_{f}^*$ with regularizer
$\widetilde{R}$. Then $\Reg(\mathcal{A}) = \Reg(\widetilde{\cA})$.
\end{corollary}

We now consider the specific case where $R$ is the negentropy
function; i.e., for $\theta \in \Delta_{d}$, $R(\theta) = -H(\theta) =
\sum_{i=1}^{d}\theta_i \log \theta_i$. For this choice of $R$, $\widetilde{R}$
becomes

\begin{equation}\label{eq:maxent_reg}
    \widetilde{R}(\widetilde{\theta}) = -\max_{\substack{\theta \in \Delta_d\\V^{T}\theta = \widetilde{\theta}}}H(\theta).
\end{equation}

In other words, $-\widetilde{R}(\widetilde{\theta})$ is the maximum entropy of any distribution $\theta$ in $\Delta_d$ that satisfies the $nm$ linear constraints imposed by $V^{T}\theta = \widetilde{\theta}$. This is exactly an instance of the Maxent problem studied in
\citep{BergerDellaPietraDellaPietra1996, 
Rosenfeld1996, 
DellaPietraDellaPietraLafferty1997, 
DudikPhillipsSchapire2007} and
\citep{MohriRostamizadehTalwalkar2018}[chapter~12]. 
\ignore{MM: I think it is fine to comment this out.
Unfortunately, it is not clear whether it is possible to efficiently
solve this problem (i.e., compute $\widetilde{R}$); however, there are multiple
things we can say the general solution that may be useful in specific
cases.  }

It is known \citep{DellaPietraDellaPietraLafferty1997,
  DudikPhillipsSchapire2007,MohriRostamizadehTalwalkar2018} that the
entropy maximizing distribution is a \textit{Gibbs distribution}. In
particular, the $\theta$ maximizing the expression in
\eqref{eq:maxent_reg} satisfies (for some real constants
$\lambda_{jk}$ for $j \in [n]$, $k \in [m]$)

\begin{equation}
\label{eq:gibbs}
\theta_i = \frac{\exp\left(\sum_{j=1}^{n}\sum_{k=1}^{m}
  \lambda_{jk}v_{ijk}\right)}{Z(\lambda)},
\end{equation}

\noindent
where $Z(\lambda)$ (the ``partition function'') is defined via 

\begin{equation}
  Z(\lambda) = \sum_{i=1}^{d}\exp\left(\sum_{j=1}^{n}\sum_{k=1}^{m}
  \lambda_{jk}v_{ijk}\right).
\end{equation}
Generally, there is exactly one choice of $\lambda_{jk}$ which results
in $V^{T}\theta = \widetilde{\theta}$ (since there are $mn$ free variables and
$mn$ linear constraints). For this optimal $\lambda$, it is known that
the maximum entropy is given by $\langle \lambda, \widetilde{\theta} \rangle -
\log Z(\lambda)$. If it is possible to solve this system for
$\lambda_{jk}$ and evaluate $Z(\lambda)$ efficiently, we can then
evaluate $\widetilde{R}$ efficiently. In Section \ref{sec:swap} we will see how
to do this for the specific case of swap regret (where we are helped
by the fact that \eqref{eq:gibbs} guarantees that $\theta$ is a
product distribution).

Regardless of how we compute the maxent regularizer $\widetilde{R}$, efficient
computation leads to an efficient $O(\sqrt{T\log d})$ regret
minimization algorithm.

\begin{corollary}
  \label{cor:efficient_entropy}
If there exists an efficient ($\poly(n, m)$ time) algorithm for
computing the maxent regularizer $\widetilde{R}(\widetilde{\theta})$, then there exists a
regret minimization algorithm $\widetilde{\cA}$ for $u$ with regret $O(\sqrt{T
  \log d})$ and that can be implemented in $\poly(n, m)$ time per
round.
\end{corollary}

\section{Applications}

\subsection{Swap regret}
\label{sec:swap}

Recall that in the setting of swap regret, the action set is ${\mathscr P} =
\Delta_K$ (distributions over $K$ actions), the loss set is ${\mathscr L} = [0,
  1]^K$, and the \textit{swap regret} of playing a sequence of actions
$\bm{p}$ on a sequence of losses $\bm{\ell}$ is given by

$$\SwapReg(\bm{p}, \bm{\ell}) = \max_{\pi: [K] \to [K]}
\sum_{t=1}^{T} \sum_{i=1}^{K}(p_{ti}\ell_{ti} -
p_{ti}\ell_{t\pi(i)}).$$

In words, swap regret compares the total loss achieved by this
sequence of actions with the loss achieved by any transformed action
sequence formed by applying an arbitrary ``swap function'' to the
actions (i.e., always playing action $\pi(i)$ instead of action
$i$). Swap regret minimization can be directly written as an
$\ell_{\infty}$-approachability problem for the bilinear function
$u\colon {\mathscr P} \times {\mathscr L} \to \mathbb{R}^{K^K}$ where
\[
u_{\pi}(p, \ell) = \sum_{i=1}^{K}(p_i\ell_i - p_i\ell_{\pi(i)}).
\]

\noindent
(here we index $u$ by the $K^K$ functions $\pi: [K] \to
    [K]$). Note that the negative orthant is indeed separable with
    respect to $u$ since if we let $p^*(\ell) = \argmin_{p \in {\mathscr P}}
    \langle p, \ell\rangle$, $u_{\pi}(p, \ell) \leq 0$ for any swap
    function $\pi$.

We can now apply the theory developed in Section
\ref{sec:main}. First, since $m = n = K$ and the maximum absolute
value of any coefficient in $u$ is $1$, Theorem \ref{thm:poly_regret}
immediately results in a swap regret algorithm with regret
$O(K^2\sqrt{T})$. Moreover, since we can write

$$\max_{\pi: [K] \to [K]} \sum_{t=1}^{T} \sum_{i=1}^{K}
(p_{ti}\ell_{ti} - p_{ti}\ell_{t\pi(i)}) = \sum_{i=1}^{K}
\max_{j \in [K]}\sum_{t=1}^{T} (p_{ti}\ell_{ti} - p_{ti}\ell_{tj}),$$

\noindent
we can compute $\SwapReg$ efficiently. By Theorem
\ref{thm:efficient_alg}, we can therefore implement this
$O(K^2\sqrt{T})$-regret algorithm efficiently (in $\poly(K)$ time per
round). We can improve upon this regret bound by noting that
$\diam({\mathscr P}) = O(1)$, $\diam({\mathscr L}) = O(\sqrt{K})$, and $D_z =
O(\sqrt{K})$ (the coefficient vector $v_{\pi}$ corresponding to
$u_{\pi}(p, \ell)$ contains at most $2K$ coefficients that are $\pm
1$).  It follows that $D_z(\diam {\mathscr P})(\diam {\mathscr L}) = O(K)$, and it
follows from the first part of Theorem \ref{thm:poly_regret} that the
regret of the aforementioned algorithm is actually only
$O(K\sqrt{T})$.

This is still a factor of approximately $O(\sqrt{K})$ larger than the
optimal $O(\sqrt{TK\log K})$ bound. To achieve the optimal regret
bound, we will show how to compute the maxent regularizer for swap
regret (and hence can efficiently implement an $O(\sqrt{T\log d}) =
O(\sqrt{TK\log K})$ algorithm via Corollary
\ref{cor:efficient_entropy}). Recall that the maxent regularizer
$\widetilde{R}(\widetilde{\theta})$ is defined for $\widetilde{\theta} \in V^{T}\Delta_d$ is the
negative of the maximum entropy of a distribution $\theta \in
\Delta_{d}$ that satisfies $\widetilde{\theta} = V^{T}\theta$. For our problem,
$\widetilde{\theta}$ is $(K^2)$-dimensional, and this imposes the following
linear constraints on $\theta$ (which we view as a distribution over
swap functions $\pi$):

\begin{eqnarray*}
\widetilde{\theta}_{ij} &=& - \sum_{\pi \mid \pi(i) = j} \theta_{\pi} \hspace{10mm} \mbox{ for $j \neq i$}\\
\widetilde{\theta}_{ii} &=& 1 - \sum_{\pi \mid \pi(i) = i} \theta_{\pi}.
\end{eqnarray*}

Now, by the characterization presented in \eqref{eq:gibbs}\footnote{In
particular, in the case of swap regret we have that $v_{\pi, i, j} =
\bm{1}(k = j) - \bm{1}(k = \pi(j))$. Since the first term
($\bm{1}(k=j)$) does not depend on $\pi$, we can ignore its
contribution to $\theta_{\pi}$ (it cancels from the numerator and
denominator).}, we know the entropy maximizing $\theta$ satisfies (for
some $K^2$ constants $\lambda_{ij}$)

\begin{eqnarray*}
\theta_{\pi} = 
\frac{\exp\left(\sum_{i=1}^{K}\lambda_{i \pi(i)}\right)}{\sum_{\pi'}\exp\left(\sum_{i=1}^{K}\lambda_{i \pi'(i)}\right)} 
= \frac{\prod_{i=1}^{K}\exp\left(\lambda_{i \pi(i)}\right)}{\sum_{\pi'}\prod_{i=1}^{K}\exp\left(\lambda_{i \pi'(i)}\right)} 
= \prod_{i=1}^{K} \frac{\exp(\lambda_{i\pi(i)})}{\sum_{j=1}^{K}\exp(\lambda_{ij})}.
\end{eqnarray*}

In particular, this shows that the entropy maximizing distribution
$\theta$ is a product distribution over the set of swap functions
$\pi$ where for each $i \in [K]$ the value of $\pi(i)$ is chosen
independently. Moreover, from $\widetilde{\theta}$ we can recover the overall
marginal probability $q_{ij} = \Pr_{\pi \sim \theta}[\pi(i) = j]$ (it
is $-\widetilde{\theta}_{ij}$ if $j \neq i$ and $1 - \widetilde{\theta}_{ii}$ if $j =
i$). The entropy of this product distribution can therefore be written
as:
\[
H(\theta) = \sum_{i=1}^{K} H(\pi (i)) = -\sum_{i=1}^{K} \sum_{j=1}^{K}
q_{ij}\log q_{ij}.
\]
Our regularizer $\widetilde{R}(\widetilde{\theta})$ is simply $-H(\theta)$ and can
clearly be efficiently computed as a function of $\widetilde{\theta}$. It
follows from Corollary \ref{cor:efficient_entropy} that there exists
an efficient ($\poly(K)$ time per round) regret minimization algorithm
for swap regret that incurs $O(\sqrt{T\log d}) = O(\sqrt{TK\log K})$
worst-case regret.

Finally, we briefly remark that the pseudonorm $f$ we construct here
is closely related to the $\ell_{1, \infty}$ \textit{group norm}
defined over $K$-by-$K$ square matrices as the $\ell_{1}$ norm of
vector formed by the $\ell_{\infty}$ norms of the rows (i.e.,
$||M||_{1, \infty} = \sum_{i=1}^{K}\max_{j \in [K]} |M_{ij}|$). This
is not unique to swap regret; in many of our applications, the
relevant pseudonorm can be thought of as a composition of multiple
smaller norms (often $\ell_1$ or $\ell_{\infty}$ norms).

\subsection{Procrustean swap regret}

To illustrate the power of Theorem \ref{thm:efficient_alg}, we present
a toy variant of swap regret where the learner must compete against an
\emph{infinite} set of swap functions (in particular, all orthogonal
linear transformations of their sequence of actions) and yet can do
this efficiently while incurring low (polynomial in the dimension of
their action set) regret.

In this problem, the action set ${\mathscr P} = \{x \in \mathbb{R}^{n} \,;\,
||x||_{2} \leq 1\}$ is the set of unit vectors with norm at most 1 and
the loss set ${\mathscr L} = [-1, 1]^n$. The learner would like to minimize the
following notion of regret:
\begin{equation}
  \label{eq:procrustes}
  \PReg(\bm{p}, \bm{\ell}) = \max_{Q \in O(n)}
  \sum_{t=1}^{T} (\langle p_t, \ell_t \rangle - \langle Qp_t, \ell_t \rangle).
\end{equation}
Here, $O(n)$ is the set of all orthogonal $n$-by-$n$ matrices. We call
this notion of regret \emph{Procrustean swap regret} due to its
similarity with the \emph{orthogonal Procrustes problem} from linear
algebra, which (loosely) asks for the orthogonal matrix which most
closely maps one sequence of points $\bm{x}_1$ onto another sequence
of points $\bm{x}_2$ (in our setting, we intuitively want to map
$\bm{x}$ onto $-\bm{\ell}$ to minimize the loss of our benchmark). See
\cite{gower2004procrustes} for a more detailed discussion of the
Procrustes problem. Regardless, note that we can compute
$\PReg(\bm{p}, \bm{\ell})$ efficiently, since we have an efficient
membership oracle for the convex hull $\conv(O(n))$ of the set of
orthogonal matrices (specifically, an $n$-by-$n$ matrix $M$ belongs to
$\conv(O(n))$ iff all its singular values are at most $1$ in absolute
value).

In our approachability framework, we can capture this notion of regret
with the bilinear function $u(p, \ell)$ with coordinates indexed by $Q
\in O(n)$ with $u(p, \ell)_Q = \langle p, \ell \rangle - \langle Qp,
\ell \rangle$ (which is separable with respect to the negative
orthant, since for $p = -\ell/||\ell||_2$, $u(p, \ell)_Q \leq
0$). Since all the conditions of Theorem \ref{thm:efficient_alg} hold,
there is an efficient learning algorithm which incurs at most
$O(\sqrt{nT})$ Procrustean swap regret (in particular, $\diam {\mathscr P} =
O(1)$, $\diam {\mathscr L} = O(\sqrt{n})$, and $D_z = O(1)$).

\subsection{Converging to Bayesian correlated equilibria}
\label{sec:bayes_correlated}

Swap regret has the nice property that if in a repeated $n$-player
normal-form game, all players run a low-swap regret algorithm to
select their actions, their time-averaged strategy profile will
converge to a correlated equilibrium (indeed, this is one of the major
motivations for studying swap regret).

In repeated Bayesian games (games where each player has private
information drawn independently from some distribution each round) the
analogue of correlated equilibria is \textit{Bayesian correlated
  equilibria}. Playing a repeated Bayesian game requires a contextual
learning algorithm, which can observe the private information of the
player (the ``context'') and select an action based on
this. \cite{mansour2022} show that there is a notion of regret (that
we call $\BSReg$) such that if all learners are playing an algorithm
with low $\BSReg$, then over time they converge on average to a
Bayesian correlated equilibrium. However, while \cite{mansour2022}
provide a low $\BSReg$ algorithm, their algorithm is not provably
efficient (it requires finding the fixed point of a system of
quadratic equations); by applying our framework, we show that it is
possible to obtain a polynomial-time, low-$\BSReg$ algorithm for this
problem.

Formally, we study the following full-information contextual online
learning setting. As before, there are $K$ actions, but there are now
$C$ different contexts (``types''). Every round $t$, the adversary
specifies a loss function $\ell_t \in {\mathscr L} = [0, 1]^{CK}$, where
$\ell_{t, i, c}$ represents the loss from playing action $i$ in
context $c$. Simultaneously, the learner specifies an action $p_t \in
{\mathscr P} = \Delta([K])^C \subset \mathbb{R}^{CK}$ which we view as a function
mapping each context to a distribution over actions. Overall, the
learner receives expected utility $\sum_{c=1}^{C} \Pr_{\mathcal{C}}[c]
\sum_{i=1}^{K} p_{t}(c)_i \ell_{t, i, c}$ this round (the learner's
context is drawn iid from the publicly known distribution $\mathcal{C}$ each
round). In this formulation $\BSReg$ can be written in the form
\begin{equation}
\label{eq:bsreg_main1}
\BSReg
= \max_{\kappa, \pi_{c}}\sum_{t=1}^{T}\sum_{c=1}^{C} \Pr_{\mathcal{C}}[c]
\sum_{i=1}^{K} \left(p_{t}(c)_i\ell_{t, i, c}
- p_{t}(\kappa(c))_{i}\ell_{t, \pi_{c}(i), c}\right),
\end{equation}
where the maximum is over all ``type swap functions'' $\kappa\colon [C]
\to [C]$ and $C$-tuples of ``action-deviation swap functions''
$\pi_{c}\colon [K] \to [K]$. It is straightforward to verify that
$\BSReg$ (as written in \eqref{eq:bsreg_main1}) can be written as an
$\ell_{\infty}$-approachability problem for a bilinear function $u\colon
{\mathscr P} \times {\mathscr L} \to \mathbb{R}^{d}$ for $d = C^C K^{KC}$. The theory
of $\ell_{\infty}$-approachability guarantees the existence of an
algorithm with $O(\sqrt{T\log d}) = O(\sqrt{T(C\log C + KC \log K)})$
regret, but this algorithm has time/space complexity $O(d)$ and is
very inefficient for even moderate values of $C$ or $K$.

Instead, in Appendix \ref{app:bayesian}, we show that $\BSReg$ can be
written in the form

$$\BSReg
= \sum_{c = 1}^{C} \max_{c' \in [C]} \sum_{i = 1}^{K} \max_{j \in [K]}
\sum_{t=1}^{T} \Pr_{\mathcal{C}}[c] \left(p_{t}(c)_i\ell_{t, i, c}
- p_{t}(c')_{i}\ell_{t, j, c}\right).$$

\noindent
This allows us to evaluate $\BSReg$ in $\poly(C, K, T)$ time and apply
our pseudonorm approachability framework. Directly from Theorems
\ref{thm:poly_regret} and \ref{thm:efficient_alg}, we know that there
exists an efficient ($\poly(C, K)$ time per round) learning algorithm
that incurs at most $O(K^2C^2\sqrt{T})$ swap regret. As with swap
regret, we can tighten this bound somewhat by examining the values of
$\diam({\mathscr X})$ and $\diam({\mathscr Y})$ and show that this algorithm actually
incurs at most $O(KC\sqrt{T})$ regret (details left to Appendix
\ref{app:bayesian}).

This is within approximately an $O(\sqrt{KC})$ factor of
optimal. Interestingly, unlike with swap regret, it is unclear if it
is possible to efficiently solve the relevant entropy maximization
problem for Bayesian swap regret (and hence achieve the optimal regret
bound). We pose this as an open question.

\begin{question}
Is it possible to efficiently (in $\poly(K, C)$ time) evaluate the
maximum entropy regularizer $\widetilde{R}(\widetilde{\theta})$ for the problem of
Bayesian swap regret?
\end{question}


\subsection{Reinforcement learning in constrained MDPs}
\label{sec:rl}

We consider episodic reinforcement learning in constrained Markov
decision processes (MDPs). Here, the agent receives a vectorial reward
(loss) in each time step and aims to find a policy that achieves a
certain minimum total reward (maximum total loss) in each dimension.
Approachability has been used to derive reinforcement learning
algorithms for constrained MDPs before
\citep{MiryoosefiBrantleyDaumeDudikSchapire2019, yu2021provably,
  MiryoosefiJin2021}, however, exclusively using $\ell_2$ geometry. As
a result, these methods aim to bound the $\ell_2$ distance to the
feasible set and the bounds scale with the $\ell_2$ norm of the reward
vector. This deviates from the more common, and perhaps more natural,
formulation for constrained MDPs studied in other works
\citep{efroni2020exploration,brantley2020constrained,ding2021provably}. Here,
each component of the loss vector is within a given range (e.g.  $[0,
  1]$) and the goal is to minimize the largest constraint violation
among all components. We will show that $\ell_\infty$-approachability
is the natural approach for this problem and yields algorithms that
avoid the $\sqrt{d}$ factor in the regret, where $d$ is the number of
constraints, that algorithms based on $\ell_2$ approachability suffer.
While the number of constraints $d$ can sometimes be small, there are
many applications where $d$ is large and a $\operatorname{poly}(d)$
dependency in the regret is undesirable, even when a computational
dependency on $d$ is manageable. For example, constraints may arise
from fairness considerations like demographic disparity that ensure
that the policy behaves similarly across all protected groups. This
would require a constraint for each pair of groups which could be very
many.


The formal problem setup is as follows. We consider an MDP $({\mathscr X}, {\mathscr A},
P, \curl*{\ell}_{t \in [T]})$ defined by a state space ${\mathscr X}$, an
action set ${\mathscr A}$, a transition function $P \colon {\mathscr X} \times {\mathscr A}
\times {\mathscr X} \to [0, 1]$, where $P(x' | x, a)$ is the probability of
reaching state $x'$ when choosing action $a$ at state $x$, and
$\ell\colon {\mathscr X} \times {\mathscr A} \to [0, 1]^d$ the loss vector function with
$\ell = (\ell^1, \ldots, \ell^d)$.  We work with losses for
consistency with the other sections but our results also readily apply
to rewards.  To simplify the presentation, we will assume a
\emph{layered MDP} with $L + 1$ layers with ${\mathscr X} = \bigcup_{l = 0}^L
{\mathscr X}_l$, ${\mathscr X}_i \cap {\mathscr X}_j = \emptyset$ for $i \neq j$, and with ${\mathscr X}_0
= \{x_0\}$ and ${\mathscr X}_L = \{x_L\}$.

We define a (stochastic) policy $\pi$ as mapping from ${\mathscr A} \times {\mathscr X}
\to [0, 1]$ where $\pi(a | x)$ represents the probability of action
$a$ in state $x$. Given a policy $\pi$ and the transition probability
$P$, we define the \emph{occupancy measure} ${\mathsf q}^{P, \pi}$ as the
probability of visiting state-action pair $(x, a)$ when following
policy $P$ \citep{Altman1999,NeuGyorgySzepesvari2012}: ${\mathsf q}^{P,
  \pi}(x, a) = \P\bracket*{x, a \mid P, \pi}$.  We will denote by
$\Delta(P)$ the set of all occupancy measures, obtained by varying the
policy $\pi$. It is known that $\Delta(P)$ forms a polytope.


We consider the feasibility problem in CMDPs with stochastic rewards
and unknown dynamics. The loss vector $\ell\colon {\mathscr X} \times {\mathscr A} \to
[0, 1]^d$ is the same in all episodes, ${\mathscr L} = \{ \ell \}$. Our goal is
to learn a policy $\pi \in \Pi$ such that $\langle {\mathsf q}^{P, \pi}, \ell
\rangle \leq {\mathbf c} $ for a given threshold vector ${\mathbf c} \in [0,
  L]^d$. The payoff function $u\colon \Delta(P) \times {\mathscr L} \to
\mathbb{R}^d$ is defined as: $u({\mathsf p}, \ell) = \bracket*{
\begin{smallmatrix}
{\mathsf p} \cdot  \ell^1 - c_1\\
\vdots\\
{\mathsf p} \cdot  \ell^d - c_d
\end{smallmatrix}}$.
The set ${\mathscr S} = (-\infty, 0]^d$ is separable as long as there is a
policy that satisfies all constraints. Although we define the payoff
function $u$ in terms of occupancy measures $\Delta(P)$, they will be
implicit in the algorithm.

To aide the comparison of our approach to existing work in this
setting, we omit the dimensionality reduction with pseudonorms in
this application and directly work in the $d$-dimensional space. We
will analyze Algorithm~\ref{algo:algorithm-linf-approach} for
$\ell_\infty$ approachability, which can be implemented in MDPs by
adopting the following oracles from prior work
\citep{MiryoosefiBrantleyDaumeDudikSchapire2019} on CMDPs:
\begin{itemize}

\item \textbf{\textsc{BestResponse}-Oracle} For a given $\theta \in
  \mathbb{R}^d$, this oracle returns a policy $\pi$ that is
  $\epsilon_0$-optimal with respect to the reward function $(s,a)
  \mapsto -\langle \ell(s,a), \theta\rangle$.
  
\item \textbf{\textsc{Est}-Oracle} For a given policy $\pi$, this
  oracle returns a vector $z \in [0, L]^d$ such that $\|z - \langle
  {\mathsf q}^{P, \pi}, \ell \rangle\|_\infty \leq \epsilon_1$.
\end{itemize}


Consider first the case without approximation errors, $\epsilon_0 =
\epsilon_1 = 0$, for illustration. For a vector $\theta_t \in
\Delta_{d+1}$, let $\theta_t' \in \mathbb{R}^d$ be the vector that contains
only the first $d$ dimensions of $\theta_t$. When we call the
\textsc{BestResponse} oracle with vector $\theta_t'$, it returns a
policy $\pi_t$ such that its occupancy measure satisfies $\langle
{\mathsf q}^{P, \pi_t}, - \theta_t' \cdot \ell \rangle \geq \max_{{\mathsf q}^\star
  \in \Delta(P)} \langle {\mathsf q}^\star, - \theta_t' \cdot \ell \rangle$.
We can use this to show:
\begin{align*}
    \theta_t \cdot [u({\mathsf q}^{P, \pi_t}, \ell), ~0]
    & = \theta_t' \cdot u({\mathsf q}^{P, \pi_t}, \ell)
    = \langle {\mathsf q}^{P, \pi_t}, \theta_t' \cdot \ell \rangle
    - c \leq \langle {\mathsf q}^\star, \theta_t' \cdot \ell \rangle - c \leq 0
\end{align*}
where ${\mathsf q}^\star$ is the occupancy measure of a policy that satisfies
all constraints.

Thus ${\mathsf q}^{P, \pi_t}$ is a valid choice for $p_t$ in Line~3 of
Algorithm~\ref{algo:algorithm-linf-approach}. Passing the policy
$\pi_t$ to the \textsc{Est} yields $\hat z_t = u({\mathsf q}^{P, \pi_t},
\ell) + c$; this is enough to compute
\begin{align*}
    y_t &= - [\hat z_t - c,~ 0] = -  [u(p_t, \ell), ~0]
\end{align*}
in Line~5 of
Algorithm~\ref{algo:algorithm-linf-approach}\footnote{Since FTRL with
negative entropy regularizer operates on the simplex with $\|
\theta_{t}\| = 1$, we pad the inputs with a zero dimension obtain an
OLO algorithm on the interior of $\Delta_{d}$.}. Finally, we obtain
$\theta_{t+1} \in \mathbb R^{d+1}$ by passing $y_1, y_2, \dots, y_t$ to
a negative entropy FTRL algorithm as the OLO algorithm $\mathcal{F}$ (Line~6
of Alg.~\ref{algo:algorithm-linf-approach}).

Using similar steps as for Theorem~\ref{thm:linf_approachability} and
relying on the regret bound for $\mathcal{F}$ in
Lemma~\ref{lem:negent_regularizer}, we can show the following
guarantee:

\begin{restatable}{proposition}{appropoinfty}
\label{prop:constrainedmdp}
Consider a constrained episodic MDP with horizon $L$, fixed loss
vectors $\ell$ with $\ell(s,a) \in [0, 1]^d$ for all state-action
pairs $(s,a) \in {\mathscr X} \times {\mathscr A}$ and a constraint threshold vector $c
\in [0, L]^d$.  Assume that there exists a feasible policy that
satisfies all constraints and let $\bar \pi$ be the mixture policy of
$\pi_1, \dots, \pi_T$ generated by the approach described above. Then
the maximum constraint violation of $\bar \pi$ satisfies
\begin{align*}
    \max_{i \in [d]} \{{\mathsf q}^{P, \bar \pi} \cdot \ell^i - c_i \}
    = d_{\infty}\left(\frac{1}{T}\sum_{t=1}^T u({\mathsf q}^{P, \pi_t}, \ell), {\mathscr S} \right)
    \leq O\left(L \sqrt{\frac{\log(d)}{T}}\right) + \epsilon_0 + 2\epsilon_1.
\end{align*}
\end{restatable}
Applying the results from prior work
\citep{MiryoosefiBrantleyDaumeDudikSchapire2019} based on $\ell_2$
approachability would yield a bound of $(L\sqrt{d} + \epsilon_1)
T^{-1/2} + \epsilon_0 + 2\epsilon_1$ in our setting with an additional
$\sqrt{d}$ and $\epsilon_1$ factor in front of $T^{-1/2}$.  For the
sake of exposition, we illustrated the benefit of $\ell_\infty$
approachability using the oracles adopted by
\citet{MiryoosefiBrantleyDaumeDudikSchapire2019}, but our approach can
also be applied with similar advantages to other works that make
oracle calls explicit \citep{yu2021provably, MiryoosefiJin2021}.

\section{Conclusion}

  We presented a new algorithmic framework for
  $\ell_\infty$-approachability, which we argued is the most suitable
  notion of approachability for a variety of applications such as
  regret minimization. Our algorithms leverage a key dimensionality
  reduction and a reduction to an online linear optimization. These
  ideas can be similarly used to derive useful algorithms for
  approachability with alternative distance metrics. In fact, as
  already pointed out, some of our algorithms can be similarly
  viewed as a reduction to an online linear optimization of an
  equivalent group-norm approachability.


\bibliographystyle{plainnat}
