# Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash
Dynamics††thanks: Previous versions: July 2012, February 2015, March 2017.
Research of the second author was partially supported by a European Research
Council (ERC) Advanced Investigator grant. The authors thank Yakov Babichenko
for useful comments, and the editor, associate editor, and referees for their
very careful reading and helpful suggestions.

Dean P. Foster Amazon Inc, New York City, and University of Pennsylvania,
Philadelphia. _e-mail_<EMAIL_ADDRESS>_web page_ : http://deanfoster.net/
Sergiu Hart Institute of Mathematics, Department of Economics, and Center for
the Study of Rationality, The Hebrew University of Jerusalem. _e-mail_ :
<EMAIL_ADDRESS>_web page_ : http://www.ma.huji.ac.il/hart

(January 12, 2018)

###### Abstract

We propose to smooth out the calibration score, which measures how good a
forecaster is, by combining nearby forecasts. While regular calibration can be
guaranteed only by randomized forecasting procedures, we show that _smooth
calibration_ can be guaranteed by _deterministic_ procedures. As a
consequence, it does not matter if the forecasts are _leaked_ , i.e., made
known in advance: smooth calibration can nevertheless be guaranteed (while
regular calibration cannot). Moreover, our procedure has finite recall, is
stationary, and all forecasts lie on a finite grid. To construct the
procedure, we deal also with the related setups of online linear regression
and weak calibration. Finally, we show that smooth calibration yields
uncoupled finite-memory _dynamics_ in $n$-person games—“smooth calibrated
learning”—in which the players play approximate _Nash equilibria_ in almost
all periods (by contrast, calibrated learning, which uses regular calibration,
yields only that the time-averages of play are approximate correlated
equilibria).

###### Contents

  1. 1 Introduction
    1. 1.1 Literature
  2. 2 Calibration: Model and Result
    1. 2.1 The Calibration Game
    2. 2.2 Smooth Calibration
    3. 2.3 Leaky Forecasts
    4. 2.4 Result
  3. 3 Online Linear Regression
    1. 3.1 Forward Algorithm
    2. 3.2 Discounted Forward Algorithm
    3. 3.3 Windowed Discounted Forward Algorithm
  4. 4 Weak Calibration
  5. 5 Smooth Calibration
  6. 6 Nash Equilibrium Dynamics
  7. A Appendix

##  1 Introduction

How good is a forecaster? Assume for concreteness that every day the
forecaster issues a forecast of the type “the chance of rain tomorrow is
$30\%.$” A simple test one may conduct is to calculate the proportion of rainy
days out of those days for which the forecast was $30\%,$ and compare it to
$30\%;$ and do the same for all other forecasts. A forecaster is said to be
_calibrated_ if, in the long run, the differences between the actual
proportions of rainy days and the forecasts are small—no matter what the
weather really was (see Dawid 1982).

What if rain is replaced by an event that is under the control of another
agent? If the forecasts are made public before the agent decides on his
action—we refer to this setup as _“leaky forecasts”_ —then calibration
_cannot_ be guaranteed; for example, the agent can make the event happen if
and only if the forecast is less than $50\%$, and so the forecasting error
(that is, the “calibration score”) is always at least $50\%.$ However, if in
each period the forecast and the agent’s decision are made
“simultaneously”—which means that neither one knows the other’s decision
before making his own—then calibration _can_ be guaranteed; see Foster and
Vohra (1998). The procedure that yields calibration no matter what the agent’s
decisions are requires the use of _randomizations_ (e.g., with probability
$1/2$ the forecaster announces $30\%,$ and with probability $1/2$ he announces
$60\%).$ Indeed, as the discussion at the beginning of this paragraph
suggests, one cannot have a deterministic procedure that is calibrated (see
Dawid 1985 and Oakes 1985).

Now the standard calibration score is overly fastidious: the days when the
forecast was, say, $30.01\%$ are considered separately from the days when the
forecast was $29.99\%$ (formally, the calibration score is a highly
discontinuous function of the data, i.e., the forecasts and the actions). This
suggests that one first combines all days when the forecast was _close to_
$30\%,$ and only then compares the $30\%$ with the proportion of rainy days.
If, say, there were $200$ days with a forecast of $30.01\%,$ out of which $10$
were rainy, and another $100$ days with a forecast of $29.99\%$, out of which
$80$ were rainy, then the forecaster is very far from being calibrated;
however, he is smoothly calibrated, as his forecasts were all close to $30\%,$
and there were $90/300=30\%$ rainy days. Undershooting at $29.99\%$ and
overshooting at $30.01\%$ is now balanced out. Formally, what this amounts to
is applying a so-called “smoothing” operation to the forecasting errors (which
makes smooth calibration easier to obtain than calibration).111Corollary 12 in
Section 4 will formally show that regular calibration implies smooth
calibration.

Perhaps surprisingly, once we consider smooth calibration, there is no longer
a need for randomization when making the forecasts: we will show that there
exist _deterministic_ procedures that guarantee smooth calibration, no matter
what the agent does. In particular, it follows that it does not matter if the
forecasts are made known to the agent before his decision, and so smooth
calibration can be guaranteed even when forecasts may be leaked.222When the
forecasting procedure is deterministic it can be simulated by the agent, and
so it is irrelevant whether the agent _observes_ the forecasts, or just
_computes_ them by himself, before taking his action. This may come as a
surprise, because, as pointed out above, an agent who knows the forecast
_before_ deciding on the weather will choose rain when the forecast is less
than $50\%$ and no rain otherwise, giving a calibration error of $50\%$ or
more, no matter what the forecaster does. However, against such an agent one
can easily be _smoothly_ calibrated, by forecasting $50.01\%$ on odd days and
$49.99\%$ on even days (the resulting weather will then alternate between rain
and no rain, and so half the days will be rainy days—and all the forecasts are
indeed close to $50\%$). What this proves is only that one can be smoothly
calibrated against this specific strategy of the agent (this is the strategy
that shows that it is impossible to have calibration with deterministic leaky
procedures); our result shows that one can in fact _guarantee_ smooth
calibration with a deterministic strategy, against _any_ strategy of the
agent.

The forecasting procedure that we construct and that guarantees smooth
calibration has moreover finite recall (i.e., only the forecasts and actions
of the last $R$ periods are taken into account, for some fixed finite $R$),
and is stationary (i.e., independent of “calendar time”: the forecast is the
same any time that the “window” of the past $R\ $periods is the
same).333Another, seemingly less elegant, way to obtain this is by restarting
the procedure once in a while; see, e.g., Lehrer and Solan (2009). Finally, we
can have all the forecasts lie on some finite fixed grid.

The construction starts with the “online linear regression” problem,
introduced by Foster (1991), where one wants to generate every period a good
linear estimator based only on the data up to that point. We provide a finite-
recall stationary algorithm for this problem; see Section 3. We then use this
algorithm, together with a fixed-point argument, to obtain “weak calibration,”
a concept introduced by Kakade and Foster (2004) and Foster and Kakade (2006);
see Section 4. Section 5 shows that weak and smooth calibration are
essentially equivalent, which yields the existence of smoothly calibrated
procedures. Finally, these procedures are used to obtain dynamics (“smoothly
calibrated learning”) that are uncoupled, have finite memory, and are close to
Nash equilibria most of the time (while the similar dynamics that are based on
regular calibration yield only the time average becoming close to correlated
equilibria; see Foster and Vohra 1997).

###  1.1 Literature

The _calibration problem_ has been extensively studied, starting with Dawid
(1982), Oakes (1985), and Foster and Vohra (1998); see Olszewski (2015) for a
comprehensive survey of the literature. Kakade and Foster (2004) and Foster
and Kakade (2006) introduced the notion of _weak calibration_ , which shares
many properties with smooth calibration. In particular, both can be guaranteed
by deterministic procedures, and both are of the “general fixed point”
variety: they can find fixed points of arbitrary continuous functions (see for
instance the last paragraph in Section 2.3).444They are thus more “powerful”
than the standard calibration procedures (such as those based on Blackwell’s
approachability), which find _linear_ fixed points (such as eigenvectors and
invariant probabilities). However, while weak calibration may be at times
technically more convenient to work with, smooth calibration is the more
natural concept, easier to interpret and understand; it is, after all, just a
standard smoothing of regular calibration.

The _online regression problem_ —see Section 3 for details—was introduced by
Foster (1991); for further improvements, see J. Foster (1999), Vovk (2001),
Azoury and Warmuth (2001), and the book of Cesa-Bianchi and Lugosi (2006).

##  2 Calibration: Model and Result

In this section we present the calibration game in its standard and “leaky”
versions, introduce the notion of smooth calibration, and state our main
results.

###  2.1 The Calibration Game

Let555We denote by $\mathbb{R}^{m}$ the $m$-dimensional Euclidean space, with
the usual $\ell_{2}$-norm $||\cdot||$. $C\subseteq\mathbb{R}^{m}$ be a compact
convex set, and let $A\subseteq C$ (for example, $C$ could be the set of
probability distributions $\Delta(A)$ over a finite set $A,$ which is
identified with the set of unit vectors in $C,$ or a product of such sets).
The _calibration game_ has two players: the “action” player—the “A-player” for
short—and the “conjecture” (or “calibrating”) player—the “C-player” for short.
At each time period $t=1,2,...,$ the C-player chooses $c_{t}\in C$ and the
A-player chooses $a_{t}\in A.$ There is full monitoring and perfect recall: at
time $t$ both players know the realized history
$h_{t-1}=(c_{1},a_{1},...,c_{t-1},a_{t-1})\in(C\times A)^{t-1}.$

In the _standard_ calibration game, $c_{t}$ and $a_{t}$ are chosen
simultaneously (perhaps in a mixed, i.e., randomized, way). In the _leaky_
calibration game, $a_{t}$ is chosen after $c_{t}$ has been chosen and
revealed; thus, $c_{t}$ is a function of $h_{t-1},$ whereas $a_{t}$ is a
function of $h_{t-1}$ _and_ $c_{t}.$ Formally, a pure strategy of the C-player
is $\sigma:\cup_{t\geq 1}(C\times A)^{t-1}\rightarrow C,$ and a pure strategy
of the A-player is $\tau:\cup_{t\geq 1}(C\times A)^{t-1}\rightarrow A$ in the
standard game, and $\tau:\cup_{t\geq 1}(C\times A)^{t-1}\times C\rightarrow A$
in the leaky game. A pure strategy of the C-player will also be referred to as
_deterministic._

The calibration score—which the C-player wants to minimize—is defined __ at
time $T\geq 1$ as follows. For every forecast $c$ in $C$ let $n(c)\equiv
n_{T}(c):=|\\{1\leq t\leq T:c_{t}=c\\}$ be the number of times that it has
been used, and let

$\bar{a}(c)\equiv\bar{a}_{T}(c):=\frac{1}{n(c)}\sum_{s=1}^{T}\mathbf{1}_{c_{s}=c}\,a_{s}$

be the average of the actions in the periods when the forecast was $c,$ where
we write $\mathbf{1}_{x=y}$ for the indicator that $x=y$ (i.e.,
$\mathbf{1}_{x=y}=1$ when $x=y$ and $\mathbf{1}_{x=y}=0$ otherwise);
$\bar{a}(c)$ is defined only when $c$ appears in the sequence
$c_{1},...,c_{T},$ i.e., $n(c)>0$. The _calibration score_ at time $T$ is then
defined as666The summation is over all $c$ with $n(c)>0,$ and we use the
Euclidean norm (the squared distance $||\bar{a}(c)-c||^{2}$ may well be used
instead, in line with standard statistics usage).

$K_{T}:=\sum_{c\in C}\frac{n(c)}{T}||\bar{a}(c)-c||.$

Thus $K_{T}$ is the mean distance between the forecast $c$ and the average
$\bar{a}(c)$ of the actions $a$ in those periods where the forecast was $c,$
weighted proportionately to how often each forecast $c$ has been used in those
$T$ periods. An alternative formulation is easily seen to be

$K_{T}=\frac{1}{T}\sum_{t=1}^{T}||\bar{a}_{t}-c_{t}||,$ (1)

where $\bar{a}_{t}:=\bar{a}(c_{t}),$ i.e.,

$\bar{a}_{t}:=\frac{\sum_{s=1}^{T}\mathbf{1}_{c_{s}=c_{t}}\,a_{s}}{\sum_{s=1}^{T}\mathbf{1}_{c_{s}=c_{t}}};$

indeed, for each $c$ there are $n(c)$ identical terms in (1) that each equal
$||\bar{a}(c)-c||.$

###  2.2 Smooth Calibration

We introduce the notion of “smooth calibration.” A _smoothing function_ is a
function $\Lambda:C\times C\rightarrow\mathbb{[}0,1]$ with $\Lambda(c,c)=1$
for every $c.$ Its interpretation is that $\Lambda(c^{\prime},c)$ gives the
weight that we assign to $c^{\prime}$ when we are at $c.$ We will use
$\Lambda(c^{\prime},c)$ instead of the indicator $\mathbf{1}_{c^{\prime}=c}$
to “smooth” out the forecasts and the average actions. Specifically, put

$\bar{a}_{t}^{\Lambda}:=\frac{\sum_{s=1}^{T}\Lambda(c_{s},c_{t})\,a_{s}}{\sum_{s=1}^{T}\Lambda(c_{s},c_{t})}\text{
\ \ and\ \ \
}c_{t}^{\Lambda}:=\frac{\sum_{s=1}^{T}\Lambda(c_{s},c_{t})\,c_{s}}{\sum_{s=1}^{T}\Lambda(c_{s},c_{t})}.$

The $\Lambda$_-smoothed calibration score_ at time $T$ is then defined as

$K_{T}^{\Lambda}=\frac{1}{T}\sum_{t=1}^{T}||\bar{a}_{t}^{\Lambda}-c_{t}^{\Lambda}||.$
(2)

A standard (and useful) assumption is a Lipschitz condition: there exists
$L<\infty$ such that
$|$$\Lambda(c^{\prime},c)-\Lambda(c^{\prime\prime},c)|\leq
L||c^{\prime}-c^{\prime\prime}||$ for all $c,c^{\prime},c^{\prime\prime}\in
C.$ Thus, the functions $\Lambda(\cdot,c)$ are uniformly Lipschitz:
$\mathcal{L}(\Lambda(\cdot,c))\leq L$ for every $c\in C,$ where
$\mathcal{L}(f):=\sup\\{\left\|f(x)-f(y)\right\|/\left\|x-y\right\|:x,y\in
X,~{}x\neq y\\}$ denotes the _Lipschitz constant_ of the function $f$ (if $f$
is not a Lipschitz function then $\mathcal{L}(f)=+\infty;$ when
$\mathcal{L}(f)\leq L$ we say that $f$ is $L$_-Lipschitz_).

Two classic examples of Lipschitz smoothing functions are: (i) the so-called
_tent function_ $\Lambda(c^{\prime},c)=[1-||c^{\prime}-c||/\delta]_{+}$ for
$\delta>0$, where $[z]_{+}:=\max\\{z,0\\}$; thus, only points $c^{\prime}$
within distance $\delta$ of $c$ are considered, and their weight is
proportional to the distance from $c$

(4,0.8)(4,1.2) $c$$c^{\prime}$$1$(-0.1,5.6)(0.1,5.6) (4,0.8)(4,1.2)
$c$$c^{\prime}$$1$(-0.1,5.6)(0.1,5.6) (0,1)(2,1)(4,5.6)(6,1)(9.5,1)
(2,0.8)(2,1.2) (6,0.8)(6,1.2) $c-\delta$$c+\delta$ Figure 1: _Left_ : The
indicator function $\textbf{1}_{x=c}$. _Right_ : The $\delta$-tent smoothing
function $\Lambda(x,c)=[1-||x-c||/\delta]_{+}$ with Lipschitz bound
$L=1/\delta$.

(see Figure 1 _Right_ for this function $\Lambda,$ and compare it with the
indicator function in Figure 1 _Left_); and (ii) the so-called _Guassian_ (or
_normal_) smoothing function
$\Lambda(c^{\prime},c)=\exp(-||c^{\prime}-c||^{2}/(2\sigma^{2}))$.

Remarks. _(a)_ The original calibration score $K_{T}$ is obtained when
$\Lambda$ is the indicator function, i.e.,
$\Lambda(c^{\prime},c)=\mathbf{1}_{c^{\prime}=c}$ for all $c,c^{\prime}\in C.$

_(b)_ The normalization $\Lambda(c,c)=1$ pins down the Lipschitz constant
(otherwise one could replace $\Lambda$ with $\alpha\Lambda$ for small
$\alpha>0,$ and so lower the Lipschitz constant without affecting the score).

_(c)_ Smoothing both $\bar{a}_{t}$ and $c_{t}$ and then taking the difference
is the same as smoothing the difference:
$\bar{a}_{t}^{\Lambda}-c_{t}^{\Lambda}=(\bar{a}_{t}-c_{t})^{\Lambda}.$
Moreover, smoothing $a_{t}$ is the same as smoothing $\bar{a}_{t},$ i.e.,
$\bar{a}_{t}^{\Lambda}=a_{t}^{\Lambda}.$

_(d)_ An alternative score smoothes only the average action $\bar{a}_{t}$, but
not the forecast $c_{t}$:

$\tilde{K}_{T}^{\Lambda}=\frac{1}{T}\sum_{t=1}^{T}||\bar{a}_{t}^{\Lambda}-c_{t}||.$

If the smoothing function puts positive weight only in small neighborhoods,
i.e., there is $\delta>0$ such that $\Lambda(c^{\prime},c)>0$ only when
$||c^{\prime}-c||\leq\delta,$ then the difference between $K_{T}^{\Lambda}$
and $\tilde{K}_{T}^{\Lambda}$ is at most $\delta$ (because in this case
$||c_{t}^{\Lambda}-c_{t}||\leq\delta$ for every $t).$ More generally,
$|K_{T}^{\Lambda}-\tilde{K}_{T}^{\Lambda}|\leq\delta$ when
$(1/T)\sum_{t=1}^{T}||c_{t}^{\Lambda}-c_{t}||\leq\delta$ for any collection of
points $c_{1},...,c_{T}\in C,$ which is indeed the case, for instance, for the
Gaussian smoothing with small enough $\sigma^{2}.$ The reason that we prefer
to use $K^{\Lambda}$ rather than $\tilde{K}^{\Lambda}$ is that $K^{\Lambda}$
vanishes when there is perfect calibration (i.e., $\bar{a}_{t}=c_{t}$ for all
$t),$ whereas $\tilde{K}^{\Lambda}$ remains positive; clean statements such as
$K_{T}^{\Lambda}\leq\varepsilon$ become
$\tilde{K}_{T}^{\Lambda}\leq\varepsilon+\delta.$

Finally, given $\varepsilon>0$ and $L<\infty$, we will say that a strategy of
the C-player—which is also called a “procedure”—is $(\varepsilon,L)$_-smoothly
calibrated_ if there is $T_{0}\equiv T_{0}(\varepsilon,L)$ such that

$K_{T}^{\Lambda}=\frac{1}{T}\sum_{t=1}^{T}\left\|\bar{a}_{t}^{\Lambda}-c_{t}^{\Lambda}\right\|\leq\varepsilon$
(3)

holds almost surely, for every strategy of the A-player, every $T>T_{0},$ and
every smoothing function $\Lambda:C\times C\rightarrow[0,1]$ that is
$L$-Lipschitz in the first coordinate. Unlike standard calibration, which can
be guaranteed only with high probability, smooth calibration may be obtained
by deterministic procedures—as will be shown below—in which case we may well
require (3) to always hold (rather than just almost surely).

###  2.3 Leaky Forecasts

We will say that a procedure (i.e., a strategy of the C-player) is
_leaky_(smoothly) calibrated if it is (smoothly) calibrated also in the leaky
setup, that is, against an A-player who may choose his action $a_{t}$ at time
$t$ depending on the forecast $c_{t}$ made by the C-player at time $t$ (i.e.,
the A-player moves after the C-player). While, as we saw in the Introduction,
there are no leaky calibrated procedures, we will show that there are _leaky
smoothly calibrated_ procedures.

Deterministic procedures (i.e., pure strategies of the C-player) are clearly
leaky: the A-player can use the procedure at each period $t$ to compute
$c_{t}$ as a function of the history $h_{t-1},$ and only then determine his
action $a_{t}.$ Thus, in particular, there cannot be deterministic calibrated
procedures (because there are no leaky calibrated procedures); see Dawid
(1985) and Oakes (1985).

In the case of smooth calibration, the procedure that we construct is
deterministic, and thus leaky smoothly calibrated. However, there are also
randomized leaky smooothly calibrated procedures. One example is the simple
calibrated procedure of D. Foster (1999) in the one-dimensional case (where
$A=\\{$“rain” , “no rain”$\\}$ and $C=[0,1]$): the forecast there is “almost
deterministic,” in the sense that the randomization is only between two very
close forecasts (such as $29.99\%$ and $30.01\%)$, and so can be shown to be
leaky smoothly calibrated. For another example, see footnote 22 in Section 4
below.

A particular instance of the leaky setup is one where the A-player uses a
fixed reaction function $g:C\rightarrow A$ that is a continuous mapping of
forecasts to actions; thus, $a_{t}=g(c_{t})$ (independently of time $t$ and
history $h_{t-1}$). In this case, leaky smooth calibration implies that most
of the forecasts that are used must be approximate fixed points of $g;$
indeed, in every period in which the forecast is $c$ the action is the same,
namely, $g(c),$ and so the average of the actions in all the periods where the
forecast is (close to) $c$ is (close to) $g(c)$ (use the continuity of $g$
here); formally, see the arguments in part (iv) of the proof of Theorem 15 in
Section 6). Thus, leaky procedures find (approximate) fixed points for
arbitrary continuous functions $g$, and so must in general be more complex
than the procedures that yield calibration (such as those obtained by
Blackwell’s approachability); cf. the complexity class PPAD (Papadimitriou
1994) in the computer science literature (see also Hazan and Kakade 2012 for
the connection to calibration).

###  2.4 Result

A strategy $\sigma$ has _finite recall_ and is _stationary_ if there exists a
finite integer $R\geq 1$ and a function $\tilde{\sigma}:(C\times
A)^{R}\rightarrow C$ such that

$\sigma(h_{T-1})=\tilde{\sigma}(c_{T-R},a_{T-R},c_{T-R+1},a_{T-R+1},...,c_{T-1},a_{T-1})$

for every $T>R$ and history $h_{T-1}=(c_{t},a_{t})_{1\leq t\leq T-1}.$ Thus,
only the “window” consisting of the last $R$ periods matters; the rest of the
history, as well as the calendar time $T,$ do not. Finally, a finite set
$D\subseteq C$ is a $\delta$_-grid_ for $C$ if for every $c\in C$ there is
$d\equiv d(c)\in D$ such that $||d-c||\leq\delta.$

Our result is:

###### Theorem 1

For every $\varepsilon>0$ and $L<\infty$ there is an
$(\varepsilon,L)$-smoothly calibrated procedure. Moreover, the procedure may
be taken to be:

  * •

deterministic;

  * •

leaky;

  * •

with finite recall and stationary; and

  * •

with all the forecasts lying on a finite grid.777The sizes $R$ of the recall
and $\delta$ of the grid depend on $\varepsilon$, $L,$ the dimension $m,$ and
the bound on the compact set $C.$

The proof will proceed as follows. First, we construct deterministic finite-
recall algorithms for the _online linear regression_ problem (cf. Foster 1991,
Azoury and Warmuth 2001); see Theorem 2 in Section 3. Next, we use these
algorithms to get deterministic finite-recall _weakly calibrated_ procedures
(cf. Foster and Kakade 2004, 2006); see Theorem 10 in Section 4. Finally, we
obtain smooth calibration from weak calibration; see Section 5.

##  3 Online Linear Regression

Classical linear regression tries to predict a variable $y$ from a vector $x$
of $d$ variables (and so $y\in\mathbb{R}$ and $x\in\mathbb{R}^{d}).$ There are
observations $(x_{t},y_{t})_{t},$ and one typically assumes that888Vectors are
viewed as column vectors, and $\theta^{\prime}$ denotes the transpose of
$\theta$ (thus $\theta^{\prime}x$ is the scalar product $\theta\cdot x$ of
$\theta$ and $x).$ $y_{t}=\theta^{\prime}x_{t}+\epsilon_{t},$ where
$\epsilon_{t}$ are (zero-mean normally distributed) error terms. The optimal
estimator for $\theta$ is then given by the least squares method; i.e.,
$\theta$ minimizes $(1/T)\sum_{t=1}^{T}\psi_{t}(\theta)$ with

$\psi_{t}(\theta):=(y_{t}-\theta^{\prime}x_{t})^{2}$

for every $t.$

In the _online linear regression_ problem (Foster 1991; see Section 1.1), the
observations arrive sequentially, and at each time period $t$ we want to
determine $\theta_{t}$ given the information at that time, namely,
$(x_{1},y_{1}),...,(x_{t-1},y_{t-1})$ and $x_{t}$ only. The goal is to bound
the difference between the mean square errors in the online case and the
offline case (i.e., “in hindsight”); namely,

$\frac{1}{T}\sum_{t=1}^{T}\psi_{t}(\theta_{t})-\frac{1}{T}\sum_{t=1}^{T}\psi_{t}(\theta).$

Thus, an online linear-regression _algorithm_ takes as input a sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ and gives as
output a sequence $(\theta_{t})_{t\geq 1}$ in $\mathbb{R}^{d},$ such that
$\theta_{t}$ is a function only of $x_{1},y_{1},...,x_{t-1},y_{t-1},x_{t},$
for each $t.$

Our result is:

###### Theorem 2

Let $X,Y$ be positive reals, and $\varepsilon>0.$ Then there exists a positive
integer $R_{0}\equiv R_{0}(\varepsilon,X,Y,d)$ such that for every $R>R_{0}$
there is an $R$-recall stationary deterministic algorithm that gives
$(\theta_{t})_{t\geq 1}$ , such that

$\displaystyle\frac{1}{R}\sum_{t=T-R+1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]$
$\displaystyle\leq$
$\displaystyle\varepsilon(1+\left\|\theta\right\|^{2})\text{\ \ and}$ (4)
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]$
$\displaystyle\leq$ $\displaystyle\varepsilon(1+\left\|\theta\right\|^{2})$
(5)

hold for every $T\geq R,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ with
$\left\|x_{t}\right\|\leq X$ and $\left|y_{t}\right|\leq Y$ for all $t.$

When in addition $\theta$ is bounded,999For example, $\theta$ lies in the unit
simplex of $\mathbb{R}^{d}.$ say, $\left\|\theta\right\|\leq M,$ the mean
square error of our online algorithm is guaranteed not to exceed the optimal
offline mean square error by more than $\varepsilon(1+M^{2}).$

The proof of Theorem 2 in the remainder of this section proceeds as follows.

_(i) Forward algorithm_ (Section 3.1). We start with the “forward algorithm”
of Azoury and Warmouth (2001) and the resulting bound on the sum of regrets
$\psi_{t}(\theta_{t})-\psi_{t}(\theta)$ (Theorem 3).

_(ii) Discounted forward algorithm_(Section 3.2).__ We modify the procedure by
introducing a $\lambda$-discount factor, which gives bounds on the discounted
sum of regrets (Propositions 4 and 5).

_(iii) Windowed discounted forward algorithm_ (Section 3.3). We further modify
the procedure by restricting the history to a window consisting only of the
last $R$ periods, which gives bounds on the sum of regrets over that window
(Proposition 8).

_(iv) Conclusion_ (Section 3.3).__ One of the useful properties of discounting
is that the weight of the initial segment from $1$ up to $T-R$ is small
relative to the whole sum from $1$ to $T,$ and so dropping that initial
segment has little effect on the procedure and the resulting estimates. We can
thus choose an appropriate discount factor $\lambda$ and a window size $R$
yielding the desired bounds on the windowed sum of regrets, and thus also on
the time average of the regrets (Proposition 9, which yields Theorem 2).

###  3.1 Forward Algorithm

The starting point is the following algorithm of Azoury and Warmuth (2001,
Section 5.4). For each $a>0,$ the $a$_-forward algorithm_
gives101010$Z_{t}^{-1}$ is the inverse of the $d\times d$ matrix $Z_{t}$
(which is invertible because $a>0),$ and $I$ denotes the identity matrix.
$\theta_{t}=Z_{t}^{-1}v_{t},$ where

$Z_{t}=aI+\sum_{q=1}^{t}x_{q}x_{q}^{\prime}\;\;\;\;\text{and\ \ \ \
}v_{t}=\sum_{q=1}^{t-1}y_{q}x_{q}.$ (6)

######  Theorem 3 (Azoury and Warmuth 2001)

For every $a>0,$ the $a$-forward algorithm yields

$\sum_{t=1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq
a\left\|\theta\right\|^{2}+\sum_{t=1}^{T}y_{t}^{2}\left(1-\frac{\det(Z_{t-1})}{\det(Z_{t})}\right)$
(7)

for every $T\geq 1,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}.$

Proof. Theorem 5.6 and Lemma A.1 in Azoury and Warmuth (2001), where $Z_{t}$
denotes their $\eta_{t}^{-1}$ matrix; the second term in their formula (5.17)
is nonnegative since $\eta_{t}$ is a positive definite matrix.111111Our
statement is different from theirs because $\psi_{t}$ equals twice $L_{t},$
and there is a misprinted sign in the first line of their formula (5.17).
$\square$

###  3.2 Discounted Forward Algorithm

Let $a>0$ and $0<\lambda<1.$ The $\lambda$_-discounted_ $a$-_forward
algorithm_ gives $\theta_{t}=Z_{t}^{-1}v_{t},$ where

$Z_{t}=aI+\sum_{q=1}^{t}\lambda^{t-q}x_{q}x_{q}^{\prime}\;\;\;\;\text{and\ \ \
\ }v_{t}=\sum_{q=1}^{t-1}\lambda^{t-q}y_{q}x_{q}.$ (8)

###### Proposition 4

For every $a>0$ and $0<\lambda<1,$ the $\lambda$-discounted $a$-forward
algorithm yields

$\sum_{t=1}^{T}\lambda^{T-t}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq
a\left\|\theta\right\|^{2}+\sum_{t=1}^{T}\lambda^{T-t}y_{t}^{2}\left(1-\lambda^{d}\frac{\det(Z_{t-1})}{\det(Z_{t})}\right)$
(9)

for every $T\geq 1,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}\ $in $\mathbb{R}^{d}\times\mathbb{R}.$

Proof. Let $b:=\sqrt{a(1-\lambda)}$. From the sequence $(x_{t},y_{t})_{t\geq
1}$ we construct a sequence $(\tilde{x}_{s},\tilde{y}_{s})_{s\geq 1}$ in
blocks as follows. For every $t\geq 1,$ the $t$-th block $B_{t}$ is of size
$d+1$ and consists of
$(\lambda^{-t/2}be^{(1)},0),...,(\lambda^{-t/2}be^{(d)},0),(\lambda^{-t/2}x_{t},\lambda^{-t/2}y_{t}),$
where $e^{(i)}$ is the $i$-th unit vector in $\mathbb{R}^{d}.$ The $a$-forward
algorithm applied to $(\tilde{x}_{s},\tilde{y}_{s})_{s\geq 1}$ yields the
following.

For $s=(d+1)t,$ i.e., at the end of the $B_{t}$ block, we have121212The
notation $\tilde{Z}_{s},$ $\tilde{\psi}_{s},...$ pertains to the
$(\tilde{x}_{s},\tilde{y}_{s})_{s\geq 1}$ problem. $\sum_{s\in
B_{t}}\tilde{x}_{s}\tilde{x}_{s}^{\prime}=b^{2}\lambda^{-t}\sum_{i=1}^{d}e^{(i)}\left(e^{(i)}\right)^{\prime}+\lambda^{-t}x_{t}x_{t}^{\prime}=\lambda^{-t}(b^{2}I+x_{t}x_{t}^{\prime});$
thus

$\displaystyle\tilde{Z}_{(d+1)t}$ $\displaystyle=$ $\displaystyle
aI+\sum_{q=1}^{t}\sum_{s\in
B_{t}}\tilde{x}_{s}\tilde{x}_{s}^{\prime}=aI+\sum_{q=1}^{t}\lambda^{-q}(b^{2}I+x_{q}x_{q}^{\prime})$
$\displaystyle=$
$\displaystyle\lambda^{-t}\left(aI+\sum_{q=1}^{t}\lambda^{t-q}x_{q}x_{q}^{\prime}\right)=\lambda^{-t}Z_{t}$

(since $\sum_{i=1}^{d}e^{(i)}\left(e^{(i)}\right)^{\prime}=I$ and
$b^{2}=(1-\lambda)a;$ recall (8)). Together with
$\tilde{v}_{(d+1)t}=\sum_{q=1}^{t}\sum_{s\in
B_{t}}\tilde{y}_{s}\tilde{x}_{s}=\sum_{q=1}^{t}\lambda^{-q}y_{q}x_{q}=\lambda^{-t}v_{t}$
(only the first entry in each block has a nonzero $\tilde{y}),$ it follows
that $\tilde{\theta}_{(d+1)t}$ indeed equals $\theta_{t}=Z_{t}^{-1}v_{t}$ as
given by (8).

Next, for every $t$ we have $\sum_{s\in
B_{t}}\tilde{\psi}_{s}(\tilde{\theta}_{s})\geq\lambda^{-t}\psi_{t}(\theta_{t})$
(all terms in the sum are nonnegative, and we drop all except the last one).
Also, for every $\theta\in\mathbb{R}^{d},$

$\sum_{s\in
B_{t}}\tilde{\psi}_{s}(\theta)=\lambda^{-t}\left(b^{2}\sum_{i=1}^{d}(\theta^{\prime}e^{(i)})^{2}+\psi_{t}(\theta)\right)=\lambda^{-t}\left(b^{2}\left\|\theta\right\|^{2}+\psi_{t}(\theta)\right).$

Thus the left-hand side of (7) evaluated at the end of the $T$-th block
$B_{T}$ satisfies

$\displaystyle LHS$ $\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}\lambda^{-t}\psi_{t}(\theta_{t})-a\left\|\theta\right\|^{2}-b^{2}\left\|\theta\right\|^{2}\sum_{t=1}^{T}\lambda^{-t}-\sum_{t=1}^{T}\lambda^{-t}\psi_{t}(\theta)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\lambda^{-t}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]-\lambda^{-T}a\left\|\theta\right\|^{2}.$

On the right-hand side we get

$RHS=\sum_{t=1}^{T}\sum_{s\in
B_{t}}\tilde{y}_{s}^{2}\left(1-\frac{\det(\tilde{Z}_{s-1})}{\det(\tilde{Z}_{s})}\right)=\sum_{t=1}^{T}\lambda^{-t}y_{t}^{2}\left(1-\frac{\det(\tilde{Z}_{(d+1)t-1})}{\det(\tilde{Z}_{(d+1)t})}\right)$

(again, only the last term in each block has nonzero $\tilde{y}_{s}).$ We have
seen above that $\tilde{Z}_{(d+1)t}=\lambda^{-t}Z_{t};$ thus
$\tilde{Z}_{(d+1)t-1}=\tilde{Z}_{(d+1)t}-\lambda^{-t}x_{t}x_{t}^{\prime}=\lambda^{-t}(Z_{t}-x_{t}x_{t}^{\prime})=\lambda^{-t+1}Z_{t-1}+(\lambda^{-t}-\lambda^{-t+1})aI.$
Therefore $\det(\tilde{Z}_{(d+1)t-1})\geq\det(\lambda^{-t+1}Z_{t-1})$ (indeed,
if $B$ is a positive definite matrix and $\beta>0$ then131313Let
$\beta_{1},...,\beta_{d}>0$ be the eigenvalues of $B;$ then the eigenvalues of
$B+cI$ are $\beta_{1}+c,...,\beta_{d}+c,$ and so
$\det(B+cI)=\prod_{i}(\beta_{i}+c)>\prod_{i}\beta_{i}=\det(B).$ $\det(B+\beta
I)>\det(B)).$ Therefore we obtain

$\displaystyle RHS$ $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\lambda^{-t}y_{t}^{2}\left(1-\frac{\det(\lambda^{-t+1}Z_{t-1})}{\det(\lambda^{-t}Z_{t})}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\lambda^{-t}y_{t}^{2}\left(1-\lambda^{d}\frac{\det(Z_{t-1})}{\det(Z_{t})}\right)$

(the matrices $Z_{t}$ are of size $d\times d,$ and so
$\det(cZ_{t})=c^{d}\det(Z_{t})).$ Recalling that $LHS\leq RHS$ by (7) and
multiplying by $\lambda^{T}$ yields the result. $\square$

Remark. From now on it will be convenient to assume that
$\left\|x_{t}\right\|\leq 1$ and $\left|y_{t}\right|\leq 1$ (i.e., $X=Y=1);$
for general $X$ and $Y,$ multiply $x_{t},y_{t},\theta_{t},\psi_{t},a$ by
$X,Y,Y/X,Y^{2},X^{2},$ respectively, in the appropriate formulas.

###### Proposition 5

For every $a>0$ and $1/4\leq\lambda<1$ there exists a constant $D_{1}\equiv
D_{1}(a,\lambda,d)$ such that the $\lambda$-discounted $a$-forward algorithm
yields

$\sum_{t=1}^{T}\lambda^{T-t}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq
a\left\|\theta\right\|^{2}+D_{1},$ (10)

for every $T\geq 1,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ with
$\left\|x_{t}\right\|\leq 1$ and $|y_{t}|\leq 1$ for all $t.$

Proof. Let $K\geq 1$ be an integer such that $1/4\leq\lambda^{K}\leq 1/2.$
Given $T\geq 1,$ let the integer $m\geq 1$ satisfy $(m-1)K<T\leq mK.$ Writing
$\zeta_{t}$ for $\det(Z_{t}),$ we have

$\displaystyle\sum_{t=1}^{T}\lambda^{T-t}\left(1-\lambda^{d}\frac{\zeta_{t-1}}{\zeta_{t}}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{mK}\lambda^{T-t}\left(1-\lambda^{d}\frac{\zeta_{t-1}}{\zeta_{t}}\right)$
(11) $\displaystyle=$
$\displaystyle\lambda^{T}\sum_{j=1}^{m-1}\sum_{t=jK+1}^{(j+1)K}\lambda^{-t}\ln\left(\lambda^{-d}\frac{\zeta_{t}}{\zeta_{t-1}}\right)$
$\displaystyle\leq$
$\displaystyle\lambda^{T}\sum_{j=1}^{m-1}\lambda^{-(j+1)K}\sum_{t=jK+1}^{(j+1)K}\ln\left(\lambda^{-d}\frac{\zeta_{t}}{\zeta_{t-1}}\right)$
$\displaystyle\leq$
$\displaystyle\lambda^{T}\sum_{j=1}^{m-1}\lambda^{-(j+1)K}\ln\left(\lambda^{-dK}\frac{\zeta_{(j+1)K}}{\zeta_{jK}}\right)$

(in the second line we have used $1-1/u\leq\ln u$ for $0<u\leq 1$, as in
(4.21) in Azoury and Warmuth 2001; in the third line,
$\lambda^{-t}\leq\lambda^{-(j+1)K}$ since $t\leq(j+1)K$ and $\lambda<1$).

Let $B=(b_{ij})$ be a $d\times d$ symmetric positive definite matrix with
$\left|b_{ij}\right|\leq\beta$ for all $i,j,$ and let $a>0.$ Then
$a^{d}\leq\det(aI+B)\leq d!(a+\beta)^{d}.$ Indeed, the second inequality
follows easily since the determinant is the sum of $d!$ products of $d$
elements each. For the first inequality, let $\beta_{1},...,\beta_{d}>0$ be
the eigenvalues of $B;$ then the eigenvalues of $aI+B$ are
$a+\beta_{1},...,a+\beta_{d},$ and so
$\det(aI+B)=\Pi_{i=1}^{d}(a+\beta_{i})>a^{d}$. Applying this to $Z_{t}$ (using
(8), $|x_{t,i}x_{t,j}|\leq\left\|x_{t}\right\|^{2}\leq 1,$ and
$\sum_{t=1}^{T}\lambda^{T-t}<1/(1-\lambda)$) yields

$a^{d}\leq\zeta_{t}\equiv\det(Z_{t})\leq
d!\left(a+\frac{1}{1-\lambda}\right)^{d}.$

Therefore, since $\lambda^{-K}\leq 4,$ we get

$\lambda^{-dK}\frac{\zeta_{(j+1)K}}{\zeta_{jK}}\leq
4^{d}d!\left(1+\frac{1}{a(1-\lambda)}\right)^{d}=:D,$

and so (11) is

$\displaystyle\leq$
$\displaystyle\lambda^{T}\sum_{j=1}^{m-1}\left(\lambda^{-K}\right)^{j+1}\ln
D\leq\lambda^{T}\frac{\lambda^{-K(m+1)}-\lambda^{-2K}}{\lambda^{-K}-1}\ln D$
$\displaystyle\leq$
$\displaystyle\lambda^{T}\frac{\lambda^{-T}\lambda^{-K}-0}{2-1}\ln D=4\ln D$

(since $2\leq\lambda^{-K}\leq 4$ and $K(m+1)<T+K$). Substituting this in (9)
and putting

$D_{1}:=4\left(\ln d!+d\ln 4+d\ln\left(1+\frac{1}{a(1-\lambda)}\right)\right)$
(12)

completes the proof. $\square$

###  3.3 Windowed Discounted Forward Algorithm

From now on it is convenient to put $(x_{t},y_{t},\theta_{t})=(0,0,0)$ for all
$t\leq 0.$

Let $a>0,~{}0<\lambda<1,$ and integer $R\geq 1$. The $R$_-windowed_
$\lambda$-_discounted_ $a$-_forward algorithm_ gives
$\theta_{t}=Z_{t}^{-1}v_{t},$ where141414The sums below effectively start at
$\min\\{t-R+1,1\\}$ (because we put $x_{q}=0$ for $q\leq 0$).

$Z_{t}=aI+\sum_{q=t-R+1}^{t}\lambda^{t-q}x_{q}x_{q}^{\prime}\;\;\;\;\text{and\
\ \ }v_{t}=\sum_{q=t-R+1}^{t-1}\lambda^{R-q}y_{q}x_{q}.$ (13)

###### Lemma 6

For every $a>0$ and $0<\lambda<1$ there exists a constant $D_{2}\equiv
D_{2}(a,\lambda,d)$ such that if $(\tilde{\theta}_{t})_{t\geq 1}$ is given by
the $\lambda$-discounted $a$-forward algorithm, and $(\theta_{t})_{t\geq 1}$
is given by the $R$-windowed $\lambda$-discounted $a$-forward algorithm for
some integer $R\geq 1,$ then

$\left|\psi_{t}(\tilde{\theta}_{t})-\psi_{t}(\theta_{t})\right|\leq
D_{2}\lambda^{R}$ (14)

for every151515For $t\leq R$ we have $\tilde{\theta}_{t}=\theta_{t}$ since
they are given by the same formula. $t\geq 1$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ with
$\left\|x_{t}\right\|\leq 1$ and $|y_{t}|\leq 1$ for all $t$.

To prove this lemma we use the following basic result. The norm of a matrix
$A$ is $\left\|A\right\|:=\max{}_{z\neq 0}\left\|Az\right\|/\left\|z\right\|.$

###### Lemma 7

For $k=1,2,$ let $c_{k}=A_{k}^{-1}b_{k},$ where $A_{k}$ is a $d\times d$
symmetric matrix whose eigenvalues are all greater than or equal to some
$\alpha>0,$ and $\left\|b_{k}\right\|\leq M.$ Then $\left\|c_{k}\right\|\leq
M/\alpha$ and

$\left\|c_{1}-c_{2}\right\|\leq\frac{1}{\alpha}\left\|b_{1}-b_{2}\right\|+\frac{M}{\alpha^{2}}\left\|A_{1}-A_{2}\right\|.$

Proof. First,
$\left\|c_{k}\right\|\leq\left\|A_{k}^{-1}\right\|\left\|b_{k}\right\|\leq(1/\alpha)M$
since $\left\|A_{k}^{-1}\right\|$ equals the maximal eigenvalue of
$A_{k}^{-1},$ which is the reciprocal of the minimal eigenvalue of $A_{k},$
and so $\left\|A_{k}^{-1}\right\|\leq 1/\alpha.$

Second, express $c_{1}-c_{2}$ as
$A_{1}^{-1}(b_{1}-b_{2})+A_{1}^{-1}(A_{2}-A_{1})A_{2}^{-1}b_{2},$ to get

$\left\|c_{1}-c_{2}\right\|\leq\left\|A_{1}^{-1}\right\|\left\|b_{1}-b_{2}\right\|+\left\|A_{1}^{-1}\right\|\left\|A_{2}-A_{1}\right\|\left\|A_{2}^{-1}\right\|\left\|b_{2}\right\|$

and the proof is complete. $\square$

Proof of Lemma 6. For $t\leq R$ we have $\tilde{\theta}_{t}\equiv\theta_{t},$
and so consider $t>R.$ We have161616Notation: $\tilde{v}_{t}$ and
$\tilde{Z}_{t}$ pertain to the sequence $\tilde{\theta}_{t}$ given by the
$\lambda$-discounted $a$-forward algorithm, whereas $v_{t}$ and $Z_{t}$
pertain to the sequence $\theta_{t}$ given by the $R$-windowed
$\lambda$-discounted $a$-forward algorithm.
$\left\|\tilde{v}_{t}\right\|,\left\|v_{t}\right\|\leq\sum_{q=1}^{\infty}\lambda^{q}=1/(1-\lambda)$.
The matrices $\tilde{Z}_{t}$ and $Z_{t}$ are the sum of $aI$ and a positive-
definite matrix, and so their eigenvalues are $\geq a.$ Next,

$\left\|\tilde{v}_{t}-v_{t}\right\|=\left\|\sum_{q=1}^{t-R}\lambda^{t-q}y_{q}x_{q}\right\|\leq\frac{\lambda^{R}}{1-\lambda};$

similarly, for each each element $(\tilde{Z}_{t}-Z_{t})_{ij}$ of
$\tilde{Z}_{t}-Z_{t}$ we have

$\left|(\tilde{Z}_{t}-Z_{t})_{ij}\right|=\left|\sum_{q=1}^{t-R}\lambda^{t-q}x_{q,i}x_{q,j}\right|\leq\frac{\lambda^{R}}{1-\lambda},$

and so171717Because $\left\|A\right\|\leq d\max_{i,j}|a_{ij}|$ for any
$d\times d$ matrix $A.$ $\left\|\tilde{Z}_{t}-Z_{t}\right\|\leq
d\lambda^{R}/(\lambda-1).$ Using Lemma 7 yields

$\left\|\tilde{\theta}_{t}-\theta_{t}\right\|\leq\frac{1}{a}\frac{\lambda^{R}}{1-\lambda}+\frac{1}{a^{2}}\frac{d\lambda^{R}}{1-\lambda}=\frac{\lambda^{R}(a+d)}{(1-\lambda)a^{2}}.$

Hence

$\displaystyle\left|\psi_{t}(\tilde{\theta}_{t})-\psi_{t}(\theta_{t})\right|$
$\displaystyle=$
$\displaystyle\left|(y_{t}-\tilde{\theta}_{t}^{\prime}x_{t})^{2}-(y_{t}-\theta_{t}^{\prime}x_{t})^{2}\right|$
$\displaystyle=$
$\displaystyle\left|(\tilde{\theta}_{t}^{\prime}-\theta_{t}^{\prime})x_{t}\cdot\left(2y_{t}-(\tilde{\theta}_{t}^{\prime}+\theta_{t}^{\prime})x_{t}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left\|\tilde{\theta}_{t}-\theta_{t}\right\|\left(2+\left\|\tilde{\theta}_{t}\right\|+\left\|\theta_{t}\right\|\right)$
$\displaystyle\leq$
$\displaystyle\frac{\lambda^{R}(a+d)}{(1-\lambda)a^{2}}\left(2+\frac{2}{(1-\lambda)a}\right)=D_{2}\lambda^{R},$

where

$D_{2}:=\frac{2\left(a+d\right)(a(1-\lambda)+1)}{a^{3}(1-\lambda)^{2}};$ (15)

this completes the proof. $\square$

###### Proposition 8

For every $a>0$ and $1/4\leq\lambda<1$ there exist constants $D_{1}\equiv
D_{1}(a,\lambda,d)$ and $D_{2}\equiv D_{2}(a,\lambda,d)$ such that for every
integer $R\geq 1$ the $R$-windowed $\lambda$-discounted $a$-forward algorithm
yields

$\displaystyle\frac{1}{R}\sum_{t=T-R+1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]$
$\displaystyle\leq$
$\displaystyle(a\left\|\theta\right\|^{2}+D_{1})\left(1-\lambda+\frac{\lambda}{R}\right)$
$\displaystyle+\frac{(\left\|\theta\right\|+1)^{2}}{R(1-\lambda)}+D_{2}\lambda^{R}$

for every $T\geq 1,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ with
$\left\|x_{t}\right\|\leq 1$ and $\left|y_{t}\right|\leq 1$ for all $t.$

Proof. Let $\tilde{\theta}_{t}$ be given by the $\lambda$-discounted
$a$-forward algorithm. Put $g_{t}:=\psi_{t}(\theta_{t})-\psi_{t}(\theta)$
(where $\theta_{t}$ is given by the $R$-windowed $\lambda$-discounted
$a$-forward algorithm) and
$\tilde{g}_{t}:=\psi_{t}(\tilde{\theta}_{t})-\psi_{t}(\theta).$ Apply (10) at
$T,$ and also at each one of $T-R+1,T-R+2,...,T-1;$ multiply those by
$1-\lambda$ and add them all up, to get

$\displaystyle\sum_{t=1}^{T}\lambda^{T-t}\tilde{g}_{t}+(1-\lambda)\sum_{r=1}^{R-1}\sum_{t=1}^{T-r}\lambda^{T-r-t}\tilde{g}_{t}$
$\displaystyle\leq$
$\displaystyle(a\left\|\theta\right\|^{2}+D_{1})(1+(R-1)(1-\lambda))$
$\displaystyle=$
$\displaystyle(a\left\|\theta\right\|^{2}+D_{1})(R-R\lambda+\lambda).$

For $t\leq T-R,$ the total coefficient of $\tilde{g}_{t}$ on the left-hand
side above is
$\lambda^{T-t}+(1-\lambda)\sum_{r=1}^{R-1}\lambda^{T-r-t}=\lambda^{T-R+1-t};$
for $T-R+1\leq t\leq T,$ it is
$\lambda^{T-t}+(1-\lambda)\sum_{r=1}^{T-t}\lambda^{T-r-t}=1.$ Therefore

$\sum_{t=1}^{T-R}\lambda^{T-R+1-t}\tilde{g}_{t}+\sum_{t=T-R+1}^{T}\tilde{g}_{t}\leq(a\left\|\theta\right\|^{2}+D_{1})(R-R\lambda+\lambda).$

Now
$\tilde{g}_{t}\geq-\psi_{t}(\theta)\geq-(\left\|\theta\right\|\left\|x_{t}\right\|+\left|y_{t}\right|)^{2}\geq-(\left\|\theta\right\|+1)^{2},$
and so

$\displaystyle\sum_{t=T-R+1}^{T}\tilde{g}_{t}$ $\displaystyle\leq$
$\displaystyle(a\left\|\theta\right\|^{2}+D_{1})(R-R\lambda+\lambda)+(\left\|\theta\right\|+1)^{2}\sum_{t=1}^{T-R}\lambda^{T-R+1-t}$
$\displaystyle\leq$
$\displaystyle(a\left\|\theta\right\|^{2}+D_{1})(R-R\lambda+\lambda)+\frac{(\left\|\theta\right\|+1)^{2}}{1-\lambda}.$

Divide by $R$ and use $g_{t}\leq\tilde{g}_{t}+D_{2}\lambda^{R}$ (by
Proposition 6). $\square$

Choosing appropriate $\lambda$ and $R$ allows us to bound the right-hand side
of (8).

###### Proposition 9

For every $\varepsilon>0$ and $a>0$ there is
$\lambda_{0}\equiv\lambda_{0}(\varepsilon,a,d)<1$ such that for every
$\lambda_{0}<\lambda<1$ there is $R_{0}\equiv
R_{0}(\varepsilon,a,d,\lambda)\geq 1$ such that for every $R\geq R_{0}$ the
$R$-windowed $\lambda$-discounted $a$-forward algorithm yields

$\displaystyle\frac{1}{R}\sum_{t=T-R+1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]$
$\displaystyle\leq$ $\displaystyle\varepsilon(1+\left\|\theta\right\|^{2}),$
(17)
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]$
$\displaystyle\leq$ $\displaystyle\varepsilon(1+\left\|\theta\right\|^{2}),$
(18)

for every $T\geq R,$ every $\theta\in\mathbb{R}^{d},$ and every sequence
$(x_{t},y_{t})_{t\geq 1}$ in $\mathbb{R}^{d}\times\mathbb{R}$ with
$\left\|x_{t}\right\|\leq 1$ and $\left|y_{t}\right|\leq 1$ for all $t.$

Proof. The right-hand side of (8) is

$\leq\left(D_{1}(1-\lambda)+\frac{D_{1}}{R}+\frac{2}{R(1-\lambda)}+D_{2}\lambda^{R}\right)+\left\|\theta\right\|^{2}\left(a(1-\lambda)+\frac{a}{R}+\frac{2}{R(1-\lambda)}\right)$

(use $\lambda/R\leq 1/R$ and $(\left\|\theta\right\|+1)^{2}\leq
2\left\|\theta\right\|^{2}+2).$ First, take $1/4\leq\lambda_{0}<1$ close
enough to $1$ so that $a(1-\lambda_{0})\leq\varepsilon/4$ and
$D_{1}(a,\lambda_{0},d)\cdot(1-\lambda_{0})\leq\varepsilon/4$ (recall formula
(12) for $D_{1}$ and use $\lim_{x\rightarrow 0^{+}}x\ln x=0).$ Then, given
$\lambda\in[\lambda_{0},1),$ take $R_{0}\geq 1\ $large enough so that
$a/R_{0}\leq\varepsilon/4,$ $D_{1}(a,\lambda,d)/R_{0}\leq\varepsilon/4,$
$2/(R_{0}(1-\lambda))\leq\varepsilon/4,$ and
$D_{2}(a,\lambda,d)\lambda^{R_{0}}\leq\varepsilon/4.$ This shows (17) for
every $T\geq 1.$

In particular, for $T^{\prime}<R$ we get
$(1/R)\sum_{t=1}^{T^{\prime}}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq\varepsilon(1+\left\|\theta\right\|^{2})$
(because $(x_{t},y_{t},\theta_{t})=(0,0,0)$ for all $t\leq 0).$ For $T\geq R,$
add up the inequalities (17) for the disjoint blocks of size $R$ that end at
$t=T,$ together with the above inequality for the initial smaller block of
size $T^{\prime}<R$ when $T$ is not a multiple of $R,$ to get
$(1/R)\sum_{t=1}^{T}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq\lceil
T/R\rceil\varepsilon(1+\left\|\theta\right\|^{2})\leq
2(T/R)\varepsilon(1+\left\|\theta\right\|^{2}).$ Replacing $\varepsilon$ with
$\varepsilon/2$ yields (18). $\square$

Remark. Similar arguments show that, for $\lambda_{0}\leq\lambda<1,$ the
discounted average is also small:

$\frac{1-\lambda}{1-\lambda^{T}}\sum_{t=1}^{T}\lambda^{T-t}\left[\psi_{t}(\theta_{t})-\psi_{t}(\theta)\right]\leq\varepsilon(1+\left\|\theta\right\|^{2}).$

Proposition 9 yields the main result of this section, Theorem 2.

Proof of Theorem 2. Use Proposition 9 (with, say, $a=1),$ and rescale
everything by $X$ and $Y$ appropriately (see the Remark before Proposition 5).
$\square$

##  4 Weak Calibration

The notion of “weak calibration” was introduced by Kakade and Foster (2004)
and Foster and Kakade (2006). The idea is as follows. Given a “test” function
$w:C\rightarrow\\{0,1\\}$ that indicates which forecasts $c$ to consider, let
the corresponding score be181818The $S_{T}$ scores are norms of averages,
rather than averages of norms like the $K_{T}$ scores. “Windowed” versions of
the scores may also be considered (with the average taken over the last $R$
periods only; cf. (4)).
$S_{T}^{w}:=||(1/T)\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})||.$ It can be shown
that if $S_{T}^{w}$ is small for every such $w,$ then the calibration score
$K_{T}$ is also small.191919Specifically, if $S_{T}^{w}\leq\varepsilon$ for
all $w:C\rightarrow\\{0,1\\}$ then $K_{T}\leq 2m\varepsilon.$ Indeed, for each
coordinate $i=1,...,m,$ let $C_{+}^{i}$ be the set of all $c_{t}$ such that
$\bar{a}_{t,i}>c_{t,i},$ and $C_{-}^{i}$ the set of all $c_{t}$ such that
$\bar{a}_{t,i}<c_{t,i}.$ Taking $w$ to be the indicator of $C_{+}^{i}$ yields
$S_{T}^{w}=(1/T)\sum_{t}[\bar{a}_{t,i}-c_{t,i}]_{+}\leq\varepsilon$ (where
$[z]_{+}:=\max\\{z,0\\});$ similarly, the indicator of $C_{-}^{i}$ yields
$(1/T)\sum_{t}[\bar{a}_{t,i}-c_{t,i}]_{-}\leq\varepsilon.$ Adding the two
inequalities gives $(1/T)\sum_{t}|\bar{a}_{t,i}-c_{t,i}|\leq 2\varepsilon.$
Since this holds for each one of the $m$ coordinates, it follows that
$K_{T}\leq 2m\varepsilon.$

Now instead of the discontinuous indicator functions, _weak calibration_
requires that $S_{T}^{w}$ be small for Lipschitz continuous “weight” functions
$w:C\rightarrow[0,1]$. Specifically, let $\varepsilon>0$ and $L<\infty.$ A
procedure (i.e., a strategy of the C-player in the calibration game) is
$(\varepsilon,L)$-_weakly calibrated_ if there is $T_{0}\equiv
T_{0}(\varepsilon,L)$ such that

$S_{T}^{w}=\left\|\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})\right\|\leq\varepsilon$
(19)

holds for every strategy of the A-player, every $T>T_{0},$ and every weight
function $w:C\rightarrow[0,1]$ that is $L$-Lipschitz (i.e.,
$\mathcal{L}(w)\leq L).$

The importance of weak calibration is that, unlike regular calibration, it can
be guaranteed by deterministic procedures (which are thus leaky): Kakade and
Foster (2004) and Foster and Kakade (2006) have proven the existence of
deterministic $(\varepsilon,L)$-weakly calibrated procedures. Moreover, as we
will show in the next section, weak calibration is essentially equivalent to
smooth calibration.

We now provide a deterministic $(\varepsilon,L)$-weakly calibrated procedure
that in addition has finite recall and is stationary.

###### Theorem 10

For every $\varepsilon>0$ and $L<\infty$ there exists an
$(\varepsilon,L)$-weakly calibrated deterministic procedure that has finite
recall and is stationary; moreover, all its forecasts may be taken to lie on a
finite grid.

The proof uses the result of Theorem 2. The basic idea is to use the forecast
itself as part of the input to the forecast—which adds a fixed-point construct
to the regression. Assume for starters that $a$ and $c$ are one-dimensional,
and also that we have only a single weight function $w$. Consider the online
linear regression problem with $x_{t}=(c_{t},w(c_{t}))$ and $y_{t}=a_{t}.$
Given the history $h_{t-1}$ up to and including time $t-1,$ if we knew the
value of $c_{t}$ then we would get a forecast
$\hat{a}_{t}:=\theta_{t}^{\prime}x_{t}$ for which, by equation (5), the regret
is small. But we do not know $c_{t},$ as it is going in fact to be our
forecast: that is, we want to choose $c_{t}$ so that the resulting
$\hat{a}_{t}$ satisfies $\hat{a}_{t}=c_{t}.$ This requires solving a fixed-
point problem (which is possible since the mapping $H$ from $c_{t}$ to
$\hat{a}_{t}$ is continuous), and indeed yields the desired $c_{t}.$ Now
equation (5) yields, for an appropriate $\varepsilon>0,$

$\frac{1}{T}\sum_{t=1}^{T}(a_{t}-\hat{a}_{t})^{2}\leq\frac{1}{T}\sum_{t=1}^{T}(a_{t}-\theta^{\prime}x_{t})^{2}+\varepsilon$

for all $\theta$. But $\hat{a}_{t}=c_{t}$, and so taking
$\theta=(1,\sqrt{\varepsilon})$ gives

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}(a_{t}-c_{t})^{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}(a_{t}-c_{t}-\sqrt{\varepsilon}w(c_{t}))^{2}+\varepsilon$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}(a_{t}-c_{t})^{2}-2\sqrt{\varepsilon}\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})+\varepsilon+\varepsilon$

(in the second line we have used $w(c_{t})\in[0,1]).$ Therefore

$\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})\leq\sqrt{\varepsilon};$

together with the similar computation for $\theta=(1,-\sqrt{\varepsilon})$ we
get

$S_{T}^{w}=\left|\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})\right|\leq\sqrt{\varepsilon},$

as desired. To deal with $m$-dimensional $a$ and $c$ we use $m$ separate
online regressions, one for each coordinate; to deal with all the
$L$-Lipschitz weight functions $w,$ we take an appropriate finite grid.

Proof. _(i) Preliminaries._ Without loss of generality assume that $A\subseteq
C\subseteq[0,1]^{m}$ (one can always translate the sets $A$ and $C$—which does
not affect (19)—and rescale them—which just rescales the Lipschitz constant);
assume also that $L\geq 1$ (as $L$ increases there are more Lipschitz
functions) and $\varepsilon\leq 1$.

For every $b\in\mathbb{R}^{m}$ let $\gamma(b):=\arg\min_{c\in
C}\left\|c-b\right\|$ be the closest point to $b$ in $C$ (it is well defined
and unique since $C$ is a convex compact set); then

$\left\|c-b\right\|\geq\left\|c-\gamma(b)\right\|$ (20)

for every $c\in C$ (because

$\left\|c-b\right\|^{2}=\left\|c-\gamma(b)\right\|^{2}+\left\|b-\gamma(b)\right\|^{2}-2(b-\gamma(b))\cdot(c-\gamma(b))$

and the third term is $\leq 0);$ moreover, $\gamma(b)=b$ when $b\in C.$

Let $\varepsilon_{1}:=\varepsilon/(2\sqrt{m}).$ Denote by $W_{L}$ the set of
weight functions $w:C\rightarrow[0,1]$ with $\mathcal{L}(w)\leq L.$ By Lemma
18 in the Appendix, there exist $d$ functions $f_{1},...,f_{d}$ in $W_{L}$
such that for every $w\in W_{L}$ there is a vector
$\varpi\equiv\varpi_{w}\in[0,1]^{d}$ with202020Since $W_{L}$ is compact in the
$\sup$ norm, there are $f_{1},...,f_{d}\in W_{L}$ such that for every $w\in
W_{L}$ there is $1\leq i\leq d$ with $\max_{c\in
C}|w(c)-f_{i}(c)|\leq\varepsilon_{1}.$ Lemma 18 improves on this, in getting a
much smaller $d$ by using linear combinations with bounded coefficients.

$\max_{c\in
C}\left|w(c)-\sum_{i=1}^{d}\varpi_{i}f_{i}(c)\right|\leq\varepsilon_{1}.$ (21)

Denote $F(c):=(f_{1}(c),...,f_{d}(c))\in[0,1]^{d};$ thus
$\left\|F(c)\right\|\leq\sqrt{d}.$ Without loss of generality we assume that
the set $\\{f_{1},...,f_{d}\\}$ includes the “$j$-th coordinate function,”
which maps each $c\in C$ to its $j$-th coordinate $c_{j};$ say,
$f_{j}(c)=c_{j}$ for $j=1,...,m$ (thus $d>m;$ in fact $d$ is much larger than
$m).$

Let $\varepsilon_{2}:=\varepsilon/(m+m(1+d)^{2}+d^{2})$ (where $d$ is given by
Lemma 18 in the Appendix, and depends on $\varepsilon,m,$ and $L)$ and
$\varepsilon_{3}:=(\varepsilon_{2})^{2}.$

_(ii) The function_ H _._ Let $\lambda$ and $R$ be given by Theorem 2 and
Proposition 9 for $a=1,$ $X=\sqrt{d},$ $Y=1,$ and
$\varepsilon=\varepsilon_{3}$. For each $j=1,...,m$ consider the sequence
$(x_{t},y_{t}^{(j)})_{t\geq 1}=(F(c_{t}),a_{t,j})_{t\geq 1}$ in
$\mathbb{R}^{d}\times\mathbb{R},$ where $a_{t}\in A$ is determined by the
A-player, and $c_{t}\in C$ is constructed inductively as follows.

Let the history be $h_{t-1}=(c_{1},a_{1},...,c_{t-1},a_{t-1}).$ For each
$c\in\mathbb{R}^{m}$, let212121A subscript $j$ stands for the $j$-th
coordinate (e.g., $a_{t,j}$ is the $j$-th coordinate of $a_{t})$, whereas a
superscript $j$ refers to the $j$-th procedure (e.g., $v_{t}^{(j)}$).

$\displaystyle Z_{t}(c)$ $\displaystyle=$ $\displaystyle
I+\sum_{q=1}^{R-1}\lambda^{R-q}x_{q}x_{q}^{\prime}+F(c)F(c)^{\prime}\in\mathbb{R}^{d\times
d},$ $\displaystyle v_{t}^{(j)}$ $\displaystyle=$
$\displaystyle\sum_{q=1}^{R-1}\lambda^{R-q}a_{q,j}x_{q}\in\mathbb{R}^{d},$
$\displaystyle H_{t,j}(c)$ $\displaystyle=$
$\displaystyle\left(Z_{t}(c)^{-1}v_{t}^{(j)}\right)^{\prime}F(c)\in\mathbb{R},$
$\displaystyle H_{t}(c)$ $\displaystyle=$
$\displaystyle(H_{t,1}(c),...,H_{t,m}(c))\in\mathbb{R}^{m}$

(where $x_{q}=F(c_{q})$ for $q<t).$ Finally, we extend the function $H_{t}$ to
all of $\mathbb{R}^{m}$ by putting $H_{t}(b):=H_{t}(\gamma(b))$ for every
$b\in\mathbb{R}^{m}$; i.e., we project $b$ to its closest point $\gamma(b)$ in
$C,$ and then apply $H_{t}$ to it.

_(iii) Fixed point of_ $H.$ For every $c\in C$ we have
$\left\|v_{t}^{(j)}\right\|\leq\sqrt{d}\lambda/(1-\lambda)$ (since
$\left|a_{q,j}\right|\leq 1$ and
$\left\|x_{q}\right\|=\left\|F(c_{q})\right\|\leq\sqrt{d}),$ and so
$\left\|Z_{t}(c)^{-1}v_{t}^{(j)}\right\|\leq\sqrt{d}\lambda/(1-\lambda)$ by
Lemma 7 ($Z_{t}(c)$ is positive definite and its eigenvalues are $\geq 1),$
which finally implies that
$\left|H_{t,j}(c)\right|\leq\sqrt{d}\lambda/(1-\lambda)\cdot\sqrt{d}=d\lambda/(1-\lambda)=:K.$
Therefore the restriction of $H_{t}$ to the compact and convex set
$[-K,K]^{m},$ which is clearly a continuous function (since, again, $Z_{t}(c)$
is positive definite and its eigenvalues are $\geq 1),$ has a fixed point (by
Brouwer’s fixed-point theorem), which we denote $b_{t}$ (any fixed point will
do);222222There may be more than one fixed point here, in which case we may
choose the fixed point at random, and obtain a _randomized_ procedure that
satisfies everything the deterministic procedure does. Using it yields in
Theorem 1 a randomized procedure that is _leaky_ smoothly calibrated (cf.
Section 2.3). put $c_{t}:=\gamma(b_{t})\in C.$ Thus

$c_{t}=\gamma(b_{t})\text{ \ and\ \ }b_{t}=H_{t}(b_{t})=H_{t}(c_{t}).$

Define $x_{t}:=F(\gamma(b_{t}))=F(c_{t})$ and
$\theta_{t}^{(j)}:=Z_{t}(c_{t})^{-1}v_{t}^{(j)}\in\mathbb{R}^{d}.$ Then
$Z_{t}(c_{t})=I+\sum_{q=1}^{R}\lambda^{R-q}x_{q}x_{q}^{\prime},$ and thus it
corresponds to the $R$-windowed $\lambda$-discounted $1$-forward algorithm
(see (13)). Therefore, for every $j=1,...,m$ and every
$\theta^{(j)}\in\mathbb{R}^{d}$ we have by (5)

$\frac{1}{T}\sum_{t=1}^{T}\left[\psi_{t}^{(j)}(\theta_{t}^{(j)})-\psi_{t}^{(j)}(\theta^{(j)})\right]\leq\varepsilon_{3}\left(1+\left\|\theta^{(j)}\right\|^{2}\right)$
(22)

for all $T\geq T_{0}\equiv R,$ where
$\psi_{t}^{(j)}(\theta)=(a_{t,j}-\theta^{\prime}x_{t})^{2},$ and thus
$\psi_{t}^{(j)}(\theta_{t}^{(j)})=(a_{t,j}-b_{t,j})^{2}$ (recall that
$b_{t,j}=H_{t,j}(b_{t})=\left(\theta_{t}^{(j)}\right)^{\prime}F(\gamma(b_{t}))=\left(\theta_{t}^{(j)}\right)^{\prime}x_{t}).$
Summing over $j$ yields

$\frac{1}{T}\sum_{t=1}^{T}\sum_{j=1}^{m}\left[\psi_{t}^{(j)}(\theta_{t}^{(j)})-\psi_{t}^{(j)}(\theta^{(j)})\right]\leq\varepsilon_{3}\left(m+\sum_{j=1}^{m}\left\|\theta^{(j)}\right\|^{2}\right).$

Now
$\sum_{j=1}^{m}\psi_{t}^{(j)}(\theta_{t}^{(j)})=\sum_{j=1}^{m}(a_{t,j}-b_{t,j})^{2}=\left\|a_{t}-b_{t}\right\|^{2}\geq\left\|a_{t}-\gamma(b_{t})\right\|^{2}=\left\|a_{t}-c_{t}\right\|^{2}=\sum_{j=1}^{m}$
$(a_{t,j}-c_{t,j})^{2}$ (by the definition of $\gamma(b_{t})$ and (20), since
$a_{t}\in A\subseteq C),$ and therefore

$\frac{1}{T}\sum_{t=1}^{T}\sum_{j=1}^{m}\left[(a_{t,j}-c_{t,j})^{2}-\psi_{t}^{(j)}(\theta^{(j)})\right]\leq\varepsilon_{3}\left(m+\sum_{j=1}^{m}\left\|\theta^{(j)}\right\|^{2}\right).$
(23)

_(iv) Estimating_ $S_{T}^{w}.$ Given a weight function $w\in W_{L},$ let the
vector $\varpi\equiv\varpi_{w}\in[0,1]^{d}$ satisfy (21), i.e.,
$\left|w(c)-\varpi^{\prime}F(c)\right|\leq\varepsilon_{1}$ for all $c\in C.$
Take $u=(u_{j})_{j=1,...,m}\in\mathbb{R}^{m}$ with $\left\|u\right\|=1.$ For
every $j=1,...,m,$ take
$\theta^{(j)}=e^{(j)}+\varepsilon_{2}u_{j}\varpi\in\mathbb{R}^{d},$ where
$e^{(j)}\in\mathbb{R}^{d}$ is the $j$-th unit vector; thus
$\left\|\theta^{(j)}\right\|\leq 1+\varepsilon_{2}d\leq 1+d$ (since
$\varepsilon_{2}\leq\varepsilon\leq 1).$ We have

$(\theta^{(j)})^{\prime}x_{t}=(\theta^{(j)})^{\prime}F(c_{t})=c_{t,j}+\varepsilon_{2}\left(\varpi^{\prime}F(c_{t})\right)u_{j}$

(since $f_{j}(c)=c_{j}$ for $j\leq m),$ and hence

$\displaystyle(a_{t,j}-c_{t,j})^{2}-\psi_{t}^{(j)}(\theta^{(j)})$
$\displaystyle=$
$\displaystyle(a_{t,j}-c_{t,j})^{2}-(a_{t,j}-c_{t,j}-\varepsilon_{2}\left(\varpi^{\prime}F(c_{t})\right)u_{j})^{2}$
$\displaystyle=$ $\displaystyle
2\varepsilon_{2}\left(\varpi^{\prime}F(c_{t})\right)u_{j}(a_{t,j}-c_{t,j})-(\varepsilon_{2}\varpi^{\prime}F(c_{t}))^{2}u_{j}^{2}.$

Summing over $j=1,...,m$ yields

$\displaystyle\sum_{j=1}^{m}\left[(a_{t,j}-c_{t,j})^{2}-\psi_{t}^{(j)}(\theta^{(j)})\right]$
$\displaystyle=$ $\displaystyle
2\varepsilon_{2}\left(\varpi^{\prime}F(c_{t})\right)u^{\prime}(a_{t}-c_{t})-(\varepsilon_{2}\varpi^{\prime}F(c_{t})^{2}\left\|u\right\|^{2}$
$\displaystyle\geq$ $\displaystyle
2\varepsilon_{2}\left(\varpi^{\prime}F(c_{t})\right)u^{\prime}(a_{t}-c_{t})-(\varepsilon_{2})^{2}d^{2}$
$\displaystyle\geq$ $\displaystyle
2\varepsilon_{2}w(c_{t})u^{\prime}(a_{t}-c_{t})-\varepsilon_{1}\cdot
2\varepsilon_{2}\left\|u\right\|\left\|a_{t}-c_{t}\right\|-(\varepsilon_{2})^{2}d^{2}$
$\displaystyle\geq$ $\displaystyle
2\varepsilon_{2}w(c_{t})u^{\prime}(a_{t}-c_{t})-2\varepsilon_{1}\varepsilon_{2}\sqrt{m}-(\varepsilon_{2})^{2}d^{2}$

(since: $\left\|u\right\|=1,$ $|\varpi^{\prime}F(c)|\leq d$ [the coordinates
of $\varpi$ are between $-1$ and $1$ and those of $F(c)$ between $0$ and $1$],
$\left\|a_{t}-c_{t}\right\|\leq\sqrt{m}$ (since $a_{t},c_{t}\in[0,1]^{m},$ and
recall (21)).

Together with (23) we get (recall that $\varepsilon_{3}=(\varepsilon_{2})^{2}$
and $\varepsilon_{1}=\varepsilon/(2\sqrt{m})$):

$2\varepsilon_{2}\cdot\frac{1}{T}\sum_{t=1}^{T}w(c_{t})u^{\prime}(a_{t}-c_{t})\leq(\varepsilon_{2})^{2}(m+m(1+d)^{2}+d^{2})+\varepsilon\varepsilon_{2};$

hence, dividing by $2\varepsilon_{2}$ and recalling that
$\varepsilon_{2}=\varepsilon/(m+m(1+d)^{2}+d^{2})$):

$u\cdot\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon.$

Since $u\in\mathbb{R}^{m}$ with $\left\|u\right\|=1$ was arbitrary, the proof
of (19) is complete.

_(v) Grid._ For the “moreover” statement, let
$\varepsilon_{4}:=\varepsilon/(L\sqrt{m}+1),$ and take $D\subseteq C$ to be a
finite $\varepsilon_{4}$-grid in $C$; i.e., for every $c\in C$ there is
$d(c)\in D$ with $||d(c)-c||\leq\varepsilon_{4}.$ Replace the forecast $c_{T}$
obtained above with $\tilde{c}_{T}:=d(c_{T});$ then, for every $a_{T}\in A,$
we have

$||w(c_{T})(a_{T}-c_{T})-w(\tilde{c}_{T})(a_{T}-\tilde{c}_{T})||\leq
L\varepsilon_{4}\sqrt{m}+\varepsilon_{4}=\varepsilon.$

Therefore the score $S_{T}^{w}$ changes by at most $\varepsilon$, and so it is
at most $2\varepsilon.$ $\square$

##  5 Smooth Calibration

In this section we show (Propositions 13 and 14) that weak calibration and
smooth calibration are essentially equivalent (albeit with different constants
$\varepsilon,L$). The existence of weakly calibrated procedures (Theorem 10,
proved in the previous section) then implies the existence of smoothly
calibrated procedures, which proves Theorem 1.

We first show how to go from weak to smooth calibration. When comparing the
two scores, we see that the smooth calibration score uses weighted averages
rather than sums: $\sum_{s=1}^{T}\Lambda(c_{s},c_{t})(a_{s}-c_{s})$ is divided
by $\sum_{s=1}^{T}\Lambda(c_{s},c_{t}).$ The following useful lemma shows how
to bound the latter using the former.

###### Lemma 11

There exists a constant $0<\gamma\equiv\gamma_{C}<\infty$ that depends only on
the dimension $m$ and the diameter $\alpha$ of $C$ such that for any
$L$-smoothing weight function $\Lambda,$ any $c_{1},...,c_{T}\in C,$ and
any232323The set $C-C$ consists of all $b=b^{\prime}-b^{\prime\prime}$ with
$b^{\prime},b^{\prime\prime}\in C.$ $b_{1},...,b_{T}\in C-C,$ putting

$B_{t}:=\sum_{s=1}^{T}\Lambda(c_{s},c_{t})b_{s}\text{\ \ \ and\ \ \
}W_{t}:=\sum_{s=1}^{T}\Lambda(c_{s},c_{t})$

for all $1\leq t\leq T,$ we have

$\frac{1}{T}\sum_{t=1}^{T}\frac{||B_{t}||}{W_{t}}\leq\gamma
L^{m/2}\left(\frac{1}{T}\max_{1\leq t\leq T}||B_{t}||\right)^{1/2}.$

Proof. Let $D\subset\mathbb{R}^{m}$ be an $m$-dimensional cube with sides of
length $\alpha$ that contains $C$ (such a cube exists because the diameter of
$C$ is $\alpha).$ Let $D_{1},...,D_{M}$ be a partition of $D$ into disjoint
cubes with sides of length $1/(2L\sqrt{m});$ the diameter of each such cube is
thus $1/(2L)$, and the number of cubes is $M=\left\lceil 2\alpha
L\sqrt{m}\right\rceil^{m}.$

Put $\kappa:=(1/T)\max_{1\leq t\leq T}||B_{t}||$ and
$\bar{b}_{t}\equiv\bar{b}_{t}^{\Lambda}:=B_{t}/W_{t}.$ When $W_{t}$ is large,
the inequality $||B_{t}||/W_{t}\leq\kappa T/W_{t}$ provides a good bound; we
will show that, for a large proportion of indices $t,$ this is indeed the
case.

Given $\eta>0$ (which will be specified later), call a cube $D_{j}$ _good_ if
it contains at least $\eta T$ elements of the sequence $c_{1},...,c_{T}$
(i.e., $|\\{t\leq T:c_{t}\in D_{j}\\}|\geq\eta T),$ and bad otherwise; call an
index $t\leq T$ _good_ if __ $c_{t}$ belongs to some good cube $D_{i},$ and
_bad_ otherwise.

If $c_{t}$ and $c_{s}$ belong to the same cube $D_{j}$ then
$||c_{s}-c_{t}||\leq\mathrm{diam}(D_{j})=1/(2L),$ and so
$1-\Lambda(c_{s},c_{t})=\Lambda(c_{t},c_{t})-\Lambda(c_{s},c_{t})\leq
L||c_{s}-c_{t}||\leq 1/2,$ which implies that $\Lambda(c_{s},c_{t})\geq 1/2.$
Therefore for every good $t$ we have $W_{t}=\sum_{s\leq
T}\Lambda(c_{s},c_{t})\geq(1/2)\eta T,$ and thus
$\left\|\bar{b}_{t}\right\|\leq 2T\kappa/(\eta T)=2\kappa/\eta,$ which then
gives

$\frac{1}{T}\sum_{good\text{ }t\leq
T}||\bar{b}_{t}||\leq\frac{2\kappa}{\eta}.$

The number of bad $t$ is less than $M\cdot\eta T$ (because each bad cube
contains less than $\eta T$ elements of $c_{1},...,c_{T},$ and there are $M$
cubes). For every $s$ we have $||b_{s}||\leq\mathrm{diam}(C)=\alpha,$ and so
$\bar{b}_{t},$ which is a weighted average of the $b_{s},$ satisfies
$||\bar{b}_{t}||\leq\alpha$ as well. Thus

$\frac{1}{T}\sum_{bad\text{ }t\leq T}||\bar{b}_{t}||\leq\frac{1}{T}M\cdot\eta
T\cdot\alpha=\alpha\eta M.$

Adding the last two displayed inequalities and choosing
$\eta=\sqrt{(2\kappa)/(\alpha M)}$ yields

$\frac{1}{T}\sum_{t\leq T}||\bar{b}_{t}||\leq 2\sqrt{2\kappa\alpha M};$

recalling that $M=\left\lceil 2\alpha L\sqrt{m}\right\rceil^{m}$ gives the
result, with $\gamma$ essentially equal to $2^{(m+3)/2}\alpha^{m/2}m^{m/4}.$
$\square$

An immediate consequence is that smooth calibration is a weaker requirement
than calibration.

###### Corollary 12

Calibration implies smooth calibration.

Proof. We will show that242424The notations $f(x)=\mathrm{O}(g(x))$,
$f(x)=\Omega(g(x)),$ and $f(x)=\Theta(g(x))$ mean, as usual, that there are
constants $C<\infty$ and $c>0$ such that for all $x$ we have, respectively,
$f(x)\leq Cg(x),$ $f(x)\geq cg(x),$ and $cg(x)\leq f(x)\leq Cg(x).$ In our
case $x$ stands for $(\varepsilon,L)$; the dimension $m$ is assumed fixed.
$K_{T}^{\Lambda}=\mathrm{O}\left(\sqrt{K_{T}}\right)$ for each fixed $L$
(where $K_{T}^{\Lambda}$ is the $\Lambda$-smoothly calibrated score for any
$L$-Lipschitz $\Lambda,$ and $K_{T}$ is the regular calibration score).
Indeed, for every $c_{t}\in C$ we have (use $0\leq\Lambda(\cdot,\cdot)\leq 1)$

$\displaystyle\frac{1}{T}\left\|\sum_{s=1}^{T}\Lambda(c_{s},c_{t})(a_{s}-c_{s})\right\|$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{s=1}^{T}\Lambda(c_{s},c_{t})||(a_{s}-c_{s})||$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{s=1}^{T}||a_{s}-c_{s}||=K_{T}.$

Now apply Lemma 11 with $b_{s}=a_{s}-c_{s}$ for all $s.$ $\square$

Returning to our proof, we can finally obtain smoothly calibrated procedures
with the desired properties, proving Theorem1.

###### Proposition 13

An $(\varepsilon,L)$-weakly calibrated procedure is
$(\varepsilon^{\prime},L)$-smoothly calibrated for
$\varepsilon^{\prime}=\gamma L^{m/2}\varepsilon^{1/2}$ (with the constant
$\gamma\equiv\gamma_{C}$ given by Lemma 11).

Proof. For any $L$-Lipschitz smoothing function $\Lambda,$ Lemma 11 with
$b_{s}=a_{s}-c_{s}$ for all $s$ yields

$K_{T}^{\Lambda}\leq\gamma L^{m/2}\left(\sup_{w\in
W_{L}}S_{T}^{w}\right)^{1/2}$

(because $\Lambda(\cdot,c_{t})\in W_{L}$ for all $c_{t}$; recall the
definition (19) of $S_{T}^{w}$ in Section 4). Therefore $\sup_{w\in
W_{L}}S_{T}^{w}\leq\varepsilon$ implies $K_{T}^{\Lambda}\leq\gamma
L^{m/2}\varepsilon^{1/2}=\varepsilon^{\prime}$ $\square$

Proof of Theorem 1. Apply Theorem 10 and Proposition 13, and recall (Section
2.3) that for deterministic procedures leaks do not matter. $\square$

As an aside, we now show how to go from smooth to weak calibration.

###### Proposition 14

An $(\varepsilon,L)$-smoothly calibrated procedure is
$(\varepsilon^{\prime},L^{\prime})$-weakly calibrated, where252525We have not
tried to optimize the estimates for $\varepsilon^{\prime}$ and $L^{\prime}.$
$\varepsilon^{\prime}=\Omega\left(\varepsilon^{1/2}L^{m/2}\right)$ and
$L^{\prime}=\mathrm{O}\left(\varepsilon^{1/2}L^{(m+2)/2}\right).$

Proof. Let $(D_{j})_{j=1,...,M}$ be a partition of $[0,1]^{m}\supseteq C$ into
disjoint cubes with sides $\delta:=1/(L\sqrt{m});$ the diameter of each cube
is thus $\delta\sqrt{m}=1/L$, and the number of cubes is
$M=\delta^{-m}=L^{m}m^{m/2}.$ Let $\varepsilon_{1}:=\sqrt{\varepsilon L^{m}}$
and $\varepsilon_{2}:=\varepsilon_{1}m^{m/2}/M=\sqrt{\varepsilon/L^{m}}.$ Take
$L^{\prime}:=L\varepsilon_{1}/2=\sqrt{\varepsilon L^{m+2}}/2$ and
$\varepsilon^{\prime}=\varepsilon_{1}(1+\sqrt{m}+\sqrt{m^{m+1}})=\sqrt{\varepsilon
L^{m}}(1+\sqrt{m}+\sqrt{m^{m+1}}).$

Fix $a_{t},c_{t}\in C\subseteq[0,1]^{m}$ for $t=1,...,T,$ and a weight
function $w$ in $W_{L^{\prime}}.$ Assume that $K_{T}^{\Lambda}\leq\varepsilon$
holds for every smoothing function $\Lambda$ that is $L$-Lipschitz in the
first coordinate; we will show that $S_{T}^{w}\leq\varepsilon^{\prime}$ (where
$K_{T}^{\Lambda}$ and $S_{T}^{w}$ are given by (2) and (19), respectively).

Let $V\subseteq\\{1,...,T\\}$ be the set of indices $t$ such that the cube
$D_{j}$ that contains $c_{t}$ includes at least a fraction $\varepsilon_{2}$
of $c_{1},...,c_{T},$ i.e., $|\\{s\leq T:c_{s}\in
D_{j}\\}|\geq\varepsilon_{2}T.$ Then

$T-|V|=|\\{t\leq T:t\notin V\\}|<M\cdot\varepsilon_{2}T=\varepsilon_{2}MT,$
(24)

because there are at most $M$ cubes containing less than $\varepsilon_{2}T$
points each.

We distinguish two cases.

_Case 1_ : $\max_{t\in V}w(c_{t})<\varepsilon_{1}.$ Since
$||a_{t}-c_{t}||\leq\sqrt{m},$ we have $||\sum_{t\in
V}w(c_{t})(a_{t}-c_{t})||\leq|V|\cdot\varepsilon_{1}\cdot\sqrt{m}\leq\varepsilon_{1}\sqrt{m}T$
(use $|V|\leq T),$ and $||\sum_{t\notin
V}w(c_{t})(a_{t}-c_{t})||\leq(T-|V|)\cdot
1\cdot\sqrt{m}=\varepsilon_{2}M\sqrt{m}T$ (use (24)). Adding and dividing by
$T$ yields

$S_{T}^{w}\leq(\varepsilon_{1}+\varepsilon_{2}M)\sqrt{m}=\varepsilon_{1}\sqrt{m}(1+m^{m/2})<K\varepsilon_{1}=\varepsilon^{\prime}.$

_Case 2_ : $\max_{t\in V}w(c_{t})\geq\varepsilon_{1}.$ Let $s\in V$ be such
that $w(c_{s})=\max_{t\in V}w(c_{t})\geq\varepsilon_{1},$ and let $R\subseteq
V$ be the set of indices $r$ such that $c_{r}$ lies in the same cube $D_{j}$
as $c_{s}.$

For each $r$ in $R,$ proceed as follows. First, we have
$|w(c_{s})-w(c_{r})|\leq L^{\prime}||c_{s}-c_{r}||\leq
L^{\prime}\cdot\delta\sqrt{m}=L\varepsilon_{1}/2\cdot(1/L)=\varepsilon_{1}/2,$
and so

$w(c_{r})\geq
w(c_{s})-\frac{\varepsilon_{1}}{2}\geq\varepsilon_{1}-\frac{\varepsilon_{1}}{2}=\frac{\varepsilon_{1}}{2}.$
(25)

Next, put $w^{r}(c):=\min\\{w(c),w(c_{r})\\}$ and
$\Lambda(c,c_{r}):=w^{r}(c)/w(c_{r})$ for $r\in R$ (and, for $t\notin R,$ put,
say, $\Lambda(c,c_{t})=1$ for all $c)$; then
$\mathcal{L}(\Lambda(\cdot,c_{r}))\leq\mathcal{L}(w)/w(c_{r})\leq
L^{\prime}/(\varepsilon_{1}/2)=L,$ and so, by our assumption

$\frac{1}{T}\sum_{r\in
R}||\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda}||\leq\frac{1}{T}\sum_{t\leq
T}||\bar{a}_{t}^{\Lambda}-c_{t}^{\Lambda}||\leq
K_{T}^{\Lambda}\leq\varepsilon.$ (26)

We will now show that $S_{T}^{w}$ is close to an appropriate multiple of
$||\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda}||,$ for each $r$ in $R.$ For $t$ in
$V$ we have $w(c_{t})\leq w(c_{s}),$ and so $0\leq w(c_{t})-w^{r}(c_{t})\leq
w(c_{s})-w(c_{r})\leq\varepsilon_{1}/2$ (recall (25)), which gives

$\left\|\sum_{t\in
V}\left(w(c_{t})-w^{r}(c_{t})\right)(a_{t}-c_{t})\right\|\leq|V|\cdot\frac{\varepsilon_{1}}{2}\cdot\sqrt{m}\leq\frac{1}{2}\varepsilon_{1}\sqrt{m}T.$

For $t\notin V$ we have $0\leq w(c_{t})-w^{r}(c_{t})\leq 1,$ and so (recall
(24))

$\left\|\sum_{t\notin
V}\left(w(c_{t})-w^{r}(c_{t})\right)(a_{t}-c_{t})\right\|\leq(T-|V|)\cdot
1\cdot\sqrt{m}\leq\varepsilon_{2}M\sqrt{m}T.$

Adding the two inequalities and dividing by $T$ yields

$\displaystyle S_{T}^{w}$ $\displaystyle=$
$\displaystyle\left\|\frac{1}{T}\sum_{t=1}^{T}w(c_{t})(a_{t}-c_{t})\right\|\leq\left\|\frac{1}{T}\sum_{t=1}^{T}w^{r}(c_{t})(a_{t}-c_{t})\right\|+\sqrt{m}\left(\frac{\varepsilon_{1}}{2}+\varepsilon_{2}M\right)$
$\displaystyle\leq$
$\displaystyle||\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda}||+\sqrt{m}\left(\frac{\varepsilon_{1}}{2}+\varepsilon_{2}M\right),$

because $\sum_{t\leq T}w^{r}(c_{t})(a_{t}-c_{t})=\left(\sum_{t\leq
T}w^{r}(c_{t})\right)(\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda})$ and $\sum_{t\leq
T}w^{r}(c_{t})\leq T.$ The set $R$ contains at least $\varepsilon_{2}T$ points
(these are all the points in the same cube as $c_{s}),$ i.e.,
$|R|\geq\varepsilon_{2}T;$ averaging over all $r$ in the set $R$ and then
recalling (26) finally gives

$\displaystyle S_{T}^{w}$ $\displaystyle\leq$
$\displaystyle\frac{1}{|R|}\sum_{r\in
R}||\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda}||+\sqrt{m}\left(\frac{\varepsilon_{1}}{2}+\varepsilon_{2}M\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{\varepsilon_{2}}\frac{1}{T}\sum_{r\in
R}||\bar{a}_{r}^{\Lambda}-c_{r}^{\Lambda}||+\sqrt{m}\left(\frac{\varepsilon_{1}}{2}+\varepsilon_{2}M\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{\varepsilon_{2}}\varepsilon+\sqrt{m}\left(\frac{\varepsilon_{1}}{2}+\varepsilon_{2}M\right)=\frac{\varepsilon\sqrt{L^{m}}}{\sqrt{\varepsilon}}+\varepsilon_{1}\left(\frac{\sqrt{m}}{2}+m^{(m+1)/2}\right)$
$\displaystyle=$
$\displaystyle\varepsilon_{1}\left(1+\frac{\sqrt{m}}{2}+m^{(m+1)/2}\right)<K\varepsilon_{1}=\varepsilon^{\prime},$

completing the proof. $\square$

##  6 Nash Equilibrium Dynamics

In this section we use our results on smooth calibration to obtain dynamics in
$n$-person games that are in the long run close to Nash equilibria most of the
time.

A (finite) _game_ is given by a finite set of players $N$, and, for each
player $i\in N,$ a finite set of actions262626We refer to one-shot choices as
“actions” rather than “strategies,” the latter term being reserved for
repeated interactions. $A^{i}$ and a payoff function
$u^{i}:A\rightarrow\mathbb{R},$ where $A:=\prod_{i\in N}A^{i}$ denotes the set
of action combinations of all players. Let $n:=|N|$ be the number of players,
$m^{i}:=|A^{i}|$ the number of pure actions of player $i,$ and $m:=\sum_{i\in
N}m^{i}$; also, let $U$ be a bound on payoffs, i.e., $|u^{i}(a)|\leq U$ for
all $a\in A$ and $i\in N.$ The set of mixed actions of player $i$ is
$X^{i}:=\Delta(A^{i}),$ the unit simplex (i.e., the set of probability
distributions) on $A^{i}$; we identify the pure actions in $A^{i}$ with the
unit vectors of $X^{i},$ and so $A^{i}\subseteq X^{i}.$ Put $C\equiv
X:=\prod_{i\in N}X^{i}$ for the set of mixed-action combinations. The payoff
functions $u^{i}$ are multilinearly extended to $X,$ and thus
$u^{i}:X\rightarrow\mathbb{R}.$

For each player $i$, a combination of mixed actions of the other players
$x^{-i}=(x^{j})_{j\neq i}\in\prod_{j\neq i}X^{j}=:X^{-i},$ and
$\varepsilon\geq 0,$ let $\mathrm{BR}_{\varepsilon}^{i}(x^{-i}):=\\{x^{i}\in
X^{i}:u^{i}(x^{i},x^{-i})\geq\max_{y^{i}\in
X^{i}}u^{i}(y^{i},x^{-i})-\varepsilon\\}$ denote the set of
$\varepsilon$_-best replies_ of $i$ to $x^{-i}.$ A (mixed) action combination
$x\in X$ is a _Nash_ $\varepsilon$_-equilibrium_ if
$x^{i}\in\mathrm{BR}_{\varepsilon}^{i}(x^{-i})$ for every $i\in N;$ let
NE$(\varepsilon)\subseteq X$ denote the set of Nash $\varepsilon$-equilibria
of the game.

A (discrete-time) _dynamic_ consists of each player $i\in N$ playing a pure
action $a_{t}^{i}\in A^{i}$ at each time period $t=1,2,...;$ put
$a_{t}=(a_{t}^{i})_{i\in N}\in A.$ There is perfect monitoring: at the end of
period $t$ all players observe $a_{t}$. The dynamic is _uncoupled_(Hart and
Mas-Colell 2003, 2006, 2013) if the play of every player $i$ may depend only
on player $i$’s payoff function $u^{i}$ (and not on the other players’ payoff
functions). Formally, such a dynamic is given by a mapping for each player $i$
from the history $h_{t-1}=(a_{1},...,a_{t-1})$ and his own payoff function
$u^{i}$ into $X^{i}=\Delta(A^{i})$ (player $i$’s choice may be random); we
will call such mappings _uncoupled._ Let $x_{t}^{i}\in X^{i}$ denote the mixed
action that player $i$ plays at time $t,$ and put $x_{t}=(x_{t}^{i})_{i\in
N}\in X.$

The dynamics we consider are smooth variants of the “calibrated learning”
introduced by Foster and Vohra (1997). _Calibrated learning_ consists of each
player best-replying to calibrated forecasts on the other players’ actions; it
results in the joint distribution of play converging in the long run to the
set of correlated equilibria of the game. Kakade and Foster (2004) defined
_publicly calibrated learning_ , where each player approximately best-replies
to a public weakly calibrated forecast on the joint actions of all players,
and proved that most of the time the play is an approximate Nash equilibrium.
We consider instead _smooth calibrated learning_ , where weak calibration is
replaced with the more natural smooth calibration; it amounts to taking
calibrated learning and smoothing out both the forecasts and the best replies.
Moreover, our forecasts are $n$-tuples of mixed strategies (in
$\prod_{i}\Delta(A^{i})$), rather than correlated mixtures (in
$\Delta(\prod_{i}A^{i})$).

Formally, a _smooth calibrated learning_ dynamic is given by:

  1. (D1)

An $(\varepsilon_{c},L_{c})$-smoothly calibrated deterministic procedure,
which yields at time $t$ a forecast $c_{t}\in X$ on the distribution of
actions of each player.

  2. (D2)

For each player $i\in N$ an $L_{g}$-Lipschitz $\varepsilon_{g}$-approximate
best-reply mapping $g^{i}:X\rightarrow X^{i};$ i.e.,
$g^{i}(x)\in\mathrm{BR}_{\varepsilon_{g}}^{i}(x^{-i})$ for every $x^{-i}\in
X^{-i}.$

  3. (D3)

Each player runs the procedure in (D1), generating at time $t$ a forecast
$c_{t}\in X;$ then each player $i$ plays at period $t$ the mixed
action272727Thus $\mathbb{P}\left[a_{t}=a~{}|~{}h_{t-1}\right]=\prod_{i\in
N}x_{t}^{i}(a^{i})$ for every $a=(a^{i})_{i\in N}\in A,$ where $h_{t-1}$ is
the history and $x_{t}^{i}(a^{i})$ is the probability that
$x_{t}^{i}\in\Delta(A^{i})$ assigns to the pure action $a^{i}\in A^{i}.$
$x_{t}^{i}:=g^{i}(c_{t})\in X^{i},$ where $g^{i}$ is given by (D2). All
players observe the action combination $a_{t}=(a_{t}^{i})_{i\in N}\in A$ that
has actually been played, and remember it.

The existence of a deterministic smoothly calibrated procedure in (D1) is
given by Theorem 1. For each player $i,$ the payoff function $u^{i}$ is linear
in $x^{i},$ and
$|u^{i}(x^{i},x^{-i})-u^{i}(y^{i},x^{-i})|\leq\sqrt{m^{i}}U||x^{i}-y^{i}||,$
and so $\mathcal{L}(u^{i})\leq\sqrt{m^{i}}U\leq\sqrt{m}U;$ the existence of
Lipschitz approximate best-reply mappings in (D2) is then given by Lemma 19 in
the Appendix (in particular, for $\varepsilon_{g}$ and $L_{g}$ such that
$L_{g}\geq\nu_{m}(\sqrt{m}U/\varepsilon_{g})^{m+1}).$

Since for each player $i$ the approximate best reply condition in (D2) makes
use _only_ of player $i$’s payoff function $u^{i},$ we can without loss of
generality choose $g^{i}$ so as to depend only on $u^{i},$ which makes the
dynamic _uncoupled_ (see above).

Our result is:

###### Theorem 15

Fix the finite set of players $N,$ the finite action spaces $A^{i}$ for all
$i\in N,$ and the payoff bound $U<\infty.$ For every $\varepsilon>0,$ any
smooth calibrated learning dynamic with appropriate parameters282828Such as
those given in (33). is an uncoupled dynamic that satisfies

$\liminf_{T\rightarrow\infty}\frac{1}{T}\left|\\{t\leq
T:x_{t}\in\mathrm{NE}(\varepsilon)\\}\right|\geq 1-\varepsilon\text{\hskip
14.45377pt}\mathrm{(a.s.)}$

for every finite game with payoff functions $(u^{i})_{i\in N}$ that are
bounded by $U$ (i.e., $|u^{i}(a)|\leq U$ for all $i\in N$ and $a\in A).$

The idea of the proof is as follows. First, assume that the forecasts $c_{t}$
are in fact calibrated (rather than just smoothly calibrated) and, moreover,
that they are calibrated with respect to the mixed plays $x_{t}$ (rather than
with respect to the actual plays $a_{t}).$ Because $x_{t}$ is given by a fixed
function of $c_{t},$ namely, $x_{t}=g(c_{t})\equiv(g^{i}(c_{t}))_{i\in N},$
the sequence of mixed plays in those periods when the forecast was a certain
$c$ is the constant sequence $g(c),...,g(c),$ whose average is $g(c),$ and
calibration then implies that $g(c)$ must be close to $c$ (most of the time,
i.e., for forecasts that appear with positive frequency). But we have only
smooth calibration; however, because $g$ is a continuous function, if $c$ and
$g(c)$ are far from one another then so are $c^{\prime}$ and $g(c^{\prime})$
for any $c^{\prime}$ close to $c,$ and so the average of such $g(c^{\prime})$
is also far from $c,$ contradicting smooth calibration. Thus, most of the time
$g(c_{t})$ is close to $c_{t},$ and hence $g(g(c_{t}))$ is close to $g(c_{t})$
(because $g$ is continuous)—which says that $g(c_{t})$ is close to an
approximate best reply to itself, i.e., $g(c_{t})$ is an approximate Nash
equilibrium. Finally, an appropriate use of a strong law of large numbers
shows that if the actual plays $a_{t}$ are (smoothly) calibrated then so are
their expectations, i.e., the mixed plays $x_{t}.$ Two crucial features of our
dynamic—which are needed to get Nash equilibria, and cannot be obtained with
standard, probabilistic, calibration—are, first, that all players always have
the same forecast, and second, that (smooth) calibration is preserved despite
the fact that the actions depend on the forecasts (leakyness).

Proof. This proof goes along similar lines to the proof of Kakade and Foster
(2004) for publicly calibrated dynamics (which is the only other calibration-
based Nash dynamic to date292929Recall footnote 4.).

Recall that $m^{i}:=|A^{i}|$ and $m:=\sum_{i\in N}m^{i},$ and so
$X\subset[0,1]^{m}.$ Put $g(c):=(g^{i}(c))_{i\in N}$ for every $c\in X;$ thus
$g:X\rightarrow X$ is a Lipschitz function with $\mathcal{L}(g)\leq nL_{g}$
(because $\mathcal{L}(g^{i})\leq L_{g}$ for each $i).$

Take $\Lambda$ to be the $L_{c}$-tent smoothing function:
$\Lambda(c^{\prime},c)=[1-L_{c}||c^{\prime}-c||]_{+}$ for all $c,c^{\prime}\in
X.$

For each period $t,$ let $c_{t}\in X$ be the _forecast_ , $x_{t}=g(c_{t})\in
X$ the _behavior_ (i.e., mixed actions), and $a_{t}\in A$ the realized pure
_actions_ ($c_{t},x_{t},$ and $a_{t}$ all depend on the history). We divide
the proof into the following steps: (i) smoothed average actions
$\bar{a}_{t}^{\Lambda}$ and forecasts $\bar{c}_{t}^{\Lambda}$ are close (by
smooth calibration); (ii) smoothed average actions $\bar{a}_{t}^{\Lambda}$ and
behaviors $\bar{x}_{t}^{\Lambda}$ are close (by the law of large numbers);
(iii) forecasts $c_{t}$ and behaviors $x_{t}$ are close (because smoothing had
little effect there); (iv) behaviors $x_{t}$ are close to Nash equilibria.
Finally, (v) shows how to tweak the parameters to get the desired result.

_(i) Smoothed average actions and smoothed forecasts are close._

Let $T_{0}$ be such that the smooth calibration score
$K_{T}^{\Lambda}\leq\varepsilon_{c}$ for all $T>T_{0},$ i.e.,

$\frac{1}{T}\sum_{t=1}^{T}||\bar{a}_{t}^{\Lambda}-c_{t}^{\Lambda}||\leq\varepsilon_{c}$
(27)

for all $T>T_{0}.$

_(ii) Smoothed average actions and smoothed average behaviors are close._

Let $D\subset X$ be a finite $\varepsilon_{1}$-grid of $X.$ For each $d\in D$
we have
$\mathbb{E}\left[\Lambda(c_{s},d)a_{s}~{}|~{}h_{s-1}\right]=\Lambda(c_{s},d)x_{s}$
(given $h_{s-1},$ only $a_{s}$ is random, and its conditional expectation is
$\mathbb{E}\left[a_{s}~{}|~{}h_{s-1}\right]=g(c_{s})=x_{s}$). By the Strong
Law of Large Numbers for Dependent Random Variables (see Loève 1978, Theorem
32.1.E:
$(1/T)\sum_{s=1}^{T}(X_{s}-\mathbb{E}\left[X_{s}|h_{s-1}\right])\rightarrow 0$
as $T\rightarrow\infty$ a.s., for random variables $X_{s}$ that are, in
particular, uniformly bounded; note that there are finitely many $d\in D$) we
get

$\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{s=1}^{T}\Lambda(c_{s},d)(a_{s}-x_{s})=0\text{\
\ for all }d\in D\text{\hskip 14.45377pt{(a.s.)}}.$ (28)

Thus, for each one of the (almost all) infinite histories $h_{\infty}$ where
(28) holds, there is a finite $T_{1}\equiv T_{1}(h_{\infty})$ such that
$(1/T)\left\|\sum_{t=1}^{T}\Lambda(c_{s},d)(a_{s}-x_{s})\right\|\leq\varepsilon_{1}$
for all $T>T_{1}$ and all $d\in D.$ Now for every $c\in X$ there is $d\in D$
with $||d-x||\leq\varepsilon_{1},$ and so
$|\Lambda(c_{s},d)-\Lambda(c_{s},c)|\leq L_{c}||c-d||\leq
L_{c}\varepsilon_{1};$ together with303030Because $a_{s},x_{s}\in[0,1]^{m}$.
$||a_{s}-x_{s}||\leq\sqrt{m}$ it follows that

$\frac{1}{T}\left\|\sum_{s=1}^{T}\Lambda(c_{s},c)(a_{s}-x_{s})\right\|\leq(1+\sqrt{m}L_{c})\varepsilon_{1}\text{\
\ for all }T>T_{1}\text{ and all }c\in X.$

Taking in particular $c=c_{t}$ for all $t\leq T,$ and then applying Lemma 11
to the set $[0,1]^{m}$ and $b_{s}=a_{s}-x_{s},$ yields

$\frac{1}{T}\sum_{t=1}^{T}||\bar{a}_{t}^{\Lambda}-\bar{x}_{t}^{\Lambda}||\leq\gamma_{m}L_{c}^{m/2}\sqrt{(1+\sqrt{m}L_{c})\varepsilon_{1}}=:\varepsilon_{2},$
(29)

where the constant $\gamma_{m}$ depends only on $m.$

_(iii) Behaviors and forecasts are close._

Because $\Lambda(c_{s},c_{t})>0$ only when $||c_{s}-c_{t}||<1/L_{c},$ it
follows that $c_{t}^{\Lambda},$ as a weighted average of such $c_{s},$
satisfies $||c_{t}^{\Lambda}-c_{t}||<1/L_{c}.$ Moreover,
$||x_{s}-x_{t}||=||g(c_{s})-g(c_{t})||\leq nL_{g}/L_{c},$ and so
$||\bar{x}_{t}^{\Lambda}-x_{t}||\leq nL_{g}/L_{c},$ which together with (27)
and (29) gives

$\frac{1}{T}\sum_{t=1}^{T}||x_{t}-c_{t}||\leq\varepsilon_{c}+\varepsilon_{2}+\frac{1}{L_{c}}+\frac{nL_{g}}{L_{c}}=:\varepsilon_{3}$
(30)

for almost every infinite history $h_{\infty}$ and for every
$T>\max\\{T_{0},T_{1}(h_{\infty})\\}.$

_(iv) Behaviors are close to Nash equilibria._ From (30) it immediately
follows that, for every $\varepsilon_{4}>0,$

$\frac{1}{T}\left|\left\\{t\leq
T:\left\|g(c_{t})-c_{t}\right\|>\varepsilon_{4}\right\\}\right|\leq\frac{1}{\varepsilon_{4}}\frac{1}{T}\sum_{t=1}^{T}\left\|(g(c_{t})-c_{t})\right\|\leq\frac{\varepsilon_{3}}{\varepsilon_{4}}.$
(31)

If $\left\|g(c_{t})-c_{t}\right\|\leq\varepsilon_{4}$ then

$\left\|g^{i}(x_{t})-x_{t}^{i}\right\|=\left\|g^{i}(g(c_{t}))-g^{i}(c_{t})\right\|\leq
L_{g}\varepsilon_{4},$

and so

$\displaystyle u^{i}(x_{t})$ $\displaystyle\geq$ $\displaystyle
u^{i}(g^{i}(x_{t}),x_{t}^{-i})-\sqrt{m^{i}}U\left\|g^{i}(x_{t})-x_{t}^{i}\right\|$
$\displaystyle\geq$
$\displaystyle\max_{y^{i}\in\Delta(A^{i})}u^{i}(y^{i},x_{t}^{-i})-\varepsilon_{g}-\sqrt{m^{i}}UL_{g}\varepsilon_{4}$

(for the second inequality we have used
$g^{i}(x)\in\mathrm{BR}_{\varepsilon_{g}}^{i}(x^{-i})$). Therefore
$\left\|g(c_{t})-c_{t}\right\|\nolinebreak\leq\nolinebreak\varepsilon_{4}$
implies that $x_{t}\in\mathrm{NE}(\varepsilon_{5}),$ where

$\varepsilon_{5}:=\varepsilon_{g}+\sqrt{m}UL_{g}\varepsilon_{4}$ (32)

(recall that $m=\sum_{i}m^{i}\geq m^{i}),$ and so, from (30) and (31) we get

$\frac{1}{T}\left|\left\\{t\leq
T:x_{t}\notin\mathrm{NE}(\varepsilon_{5})\right\\}\right|\leq\frac{\varepsilon_{3}}{\varepsilon_{4}}$

for all large enough $T$, for almost every infinite history.

_(v) Tweaking the parameters._ To bound both $\varepsilon_{3}/\varepsilon_{4}$
and $\varepsilon_{5}$ by, say, $3\varepsilon,$ one may take, for instance (see
(29)–(32) and recall Lemma 19 in the Appendix),

$\displaystyle\varepsilon_{g}$ $\displaystyle=$
$\displaystyle\varepsilon,\;\;L_{g}=\nu_{m}\left(\frac{\sqrt{m}U}{\varepsilon}\right)^{m+1},$
(33) $\displaystyle\varepsilon_{4}$ $\displaystyle=$
$\displaystyle\frac{2\varepsilon}{\sqrt{m}UL_{g}},$
$\displaystyle\varepsilon_{c}$ $\displaystyle=$
$\displaystyle\varepsilon\varepsilon_{4},\;\;L_{c}=\frac{1+nL_{g}}{\varepsilon\varepsilon_{4}},$
$\displaystyle\varepsilon_{2}$ $\displaystyle=$
$\displaystyle\varepsilon\varepsilon_{4},\;\;\varepsilon_{1}=\frac{\varepsilon_{2}^{2}}{\gamma_{m}^{2}L_{c}^{m}(1+\sqrt{m}L_{c})},$

because we then get $\varepsilon_{5}=\varepsilon+2\varepsilon=3\varepsilon$
and
$\varepsilon_{3}=\varepsilon\varepsilon_{4}+\varepsilon\varepsilon_{4}+\varepsilon\varepsilon_{4}=3\varepsilon\varepsilon_{4}.$
$\square$

Remarks. _(a) Nash dynamics._ Uncoupled dynamics where Nash
$\varepsilon$-equilibria are played $1-\varepsilon$ of the time were first
proposed by Foster and Young (2003), followed by Kakade and Foster (2004),
Foster and Young (2006), Hart and Mas-Colell (2006), Germano and Lugosi
(2007), Young (2009), Babichenko (2012), and others (see also Remark (h)
below).

_(b) Coordination._ All players need to coordinate before playing the game on
the smoothly calibrated procedure that they will run; thus, at every period
$t$ they all generate the same forecast $t.$ By contrast, in the original
calibrated learning dynamic of Foster and Vohra (1997)—which leads to
correlated equilibria—every player may use his own calibrated procedure.

This fits the so-called _Conservation Coordination Law_ for game dynamics,
which says that some form of “coordination” must be present, either in the
limit static equilibrium concept (such as correlated equilibrium) or in the
dynamic leading to it (such as Nash equilibrium dynamics). See Hart and Mas-
Colell (2003, footnote 19) and Hart (2005, footnote 19).

_(c)_ _Deterministic calibration._ In order for all the players to generate
the same forecasts, it is not enough that they all use the same procedure; in
addition, the forecasts must be deterministic (otherwise the randomizations,
which are carried out independently by the players, may lead to different
actual forecasts). This is the reason that we use smoothly calibrated
procedures rather than fully calibrated ones (cf. Oakes 1985 and Foster and
Vohra 1998).

_(d) Leaky calibration_. One may use a common _randomized_ smoothly calibrated
procedure, provided that the randomizations are carried out publicly (i.e.,
they must be leaked!). Alternatively, a “central bureau of statistics” may be
used each period to provide the forecast to all the players.

_(e) Finite memory._ In (D1) one may use a smoothly calibrated procedure that
has finite recall and is stationary (see Theorem 1). However, while in the
calibration game of Section 5 both the actions $a_{t}$ and the forecasts
$c_{t}$ are monitored and thus become part of the recall window, in the
$n$-person game only $a_{t}$ is monitored (while the forecast $c_{t}$ is
computed by each player separately, but is _not_ played). Therefore, in order
to run the calibrated procedure, in the $n$-person game each player needs to
remember at time $T$, in addition to the last $R$ action combinations
$a_{T-R},...,a_{T-1},$ also the last $R$ forecasts $c_{T-R},...,c_{T-1}.$
“Finite recall” of size $R$ in the calibration procedure therefore becomes
“finite memory” of size $2R$ in the game dynamic: the memory contains $R$
elements of $A$ and $R$ elements of313131For a similar transition from finite
recall to finite memory, see Theorem 7 in Hart and Mas-Colell (2006). $C.$

Alternatively, to get finite recall rather than finite memory one may
introduce an artificial player, say, player $0,$ with action set $A^{0}:=X$
and constant payoff function $u^{0}\equiv 0,$ who plays at each period $t$ the
forecast $c_{t},$ i.e., $a_{t}^{0}=c_{t};$ this way the forecasts become part
of the recall of all players.

_(f) Forecasting joint play._ In (D1) one may use a procedure that forecasts
the joint play: the forecasts $c_{t}$ lie in $\Delta(A),$ rather than in
$\prod_{i}\Delta(A^{i}))$ (the dimension is then larger, $\prod_{i}m^{i}$
instead of $\sum_{i}m^{i}).$ The approximate best reply functions $g^{i}$ can
then be defined over $\Delta(A),$ and the proof carries through essentially
without change. Thus most of the time the play is close to Nash equilibrium,
despite the fact that the forecasts are allowed to be correlated; in fact, the
forecasts turn out to be close to being independent (because $g(c_{t})\in X$
is independent, and $c_{t}$ is close to $g(c_{t})).$

_(g) Separate forecasts._ One cannot simplify (D1) by replacing the
forecasting procedure that yields $c_{t}=(c_{t}^{i})_{i\in N}\in X$ with $n$
separate forecasting procedures that yield $c_{t}^{i}\in X^{i}$ for each $i\in
N,$ because then behaviors $x_{t}$ and forecasts $c_{t}$ need no longer be
close (in part (iii) of the proof, when $c_{s}^{i}$ is now close to
$c_{t}^{i}$ for some $i,$ it does not follow that $c_{s}^{j}$ and $c_{t}^{j}$
for $j\neq i$ are also close, and so neither are $g(c_{s})$ and $g(c_{t})$).

_(h) Continuous approximate best reply_. In (D2) one may take the functions
$g^{i}$ to be continuous rather than Lipschitz and carry the proof with the
modulus of continuity instead of the Lipschitz bound (for uncoupledness one
would need to require uniform equicontinuity).

_(i) Exhaustive search._ Dynamics that perform exhaustive search can also be
used to get the result of Theorem323232We thank Yakov Babichenko for
suggesting this. 15. Take for instance a finite grid on $X$, say,
$D=\\{d_{1},...,d_{M}\\}\subset X,$ that is fine enough so that there always
is a pure Nash $\varepsilon$-equilibrium on the grid. Let the dynamic go over
the points $d_{1},d_{2},...$ in sequence until the first time that
$d_{T}^{i}\in\mathrm{BR}_{\varepsilon}^{i}(d_{T}^{-i})$ for all $i,$ following
which $d_{T}$ is played forever. This is implemented by having for every
player $i$ a distinct action $a_{0}^{i}\in A^{i}$ that is played at time $t$
only when $d_{t}^{i}\in\mathrm{BR}_{\varepsilon}^{i}(d_{t}^{-i})$ (otherwise a
different action is played); once the action combination
$a_{0}=(a_{0}^{i})_{i\in N}\in A$ is played, say, at time $T,$ each player $i$
plays $d_{T}^{i}$ at all $t>T.$ This dynamic is uncoupled (each player only
considers $\mathrm{BR}_{\varepsilon}^{i})$ and has memory of size $2$ (i.e.,
$2$ elements of $X)$: for $t\leq T,$ it consists of $d_{t-1}$ and $a_{t-1}$
(the last checked point and the last played action combination); for $t>T,$ it
consists of $d_{T}$ and $a_{0}$. Of course, all players need to coordinate
before playing the game on the sequence $d_{1},d_{2},...,d_{M}$ and the action
combination $a_{0}.$

_(j) Continuous action spaces._ The result of Theorem 15 easily extends to
continuous action spaces and approximate _pure_ Nash equilibria. Assume that
for each player $i\in N$ the set of actions $A^{i}$ is a convex compact subset
of some Euclidean space (such games arise, for instance, from exchange
economies where the actions are net trades; see, e.g., Hart and Mas-Colell
2015). Thus $A=\prod{}_{i\in N}A^{i}$ is a compact convex set in some
Euclidean space, say, $\mathbb{R}^{m}.$

For every $\varepsilon\geq 0,$ the set of pure $\varepsilon$_-best replies_ of
player $i$ to $a^{-i}\in a^{-i}$ is
$\mathrm{PBR}_{\varepsilon}^{i}(a^{-i}):=\\{a^{i}\in
A^{i}:u^{i}(a^{i},a^{-i})\geq\max_{b^{i}\in
A^{i}}u^{i}(b^{i},a^{-i})-\varepsilon\\}.$ An action combination $a\in A$ is a
_pure_ _Nash_ $\varepsilon$_-equilibrium_ if
$a^{i}\in\mathrm{PBR}_{\varepsilon}^{i}(a^{-i})$ for every $i\in N;$ let
PNE$(\varepsilon)\subseteq A$ denote the set of pure Nash
$\varepsilon$-equilibria.

Smooth calibrated learning is defined as above, except that now the
approximate best replies are pure actions (the play is $a_{t}=g(c_{t}),$ and
it is monitored by all players). Our result here is:

###### Theorem 16

Fix the finite set of players $N,$ the convex compact action spaces $A^{i}$
for all $i\in N,$ and the Lipschitz bound $L<\infty.$ For every
$\varepsilon>0,$ and any smooth calibrated learning dynamic with appropriate
parameters, there is $T_{0}\equiv T_{0}(\varepsilon,L)$ such that for every
$T\geq T_{0},$

$\frac{1}{T}\left|\\{t\leq T:a_{t}\in\mathrm{PNE}(\varepsilon)\\}\right|\geq
1-\varepsilon$

for every game with payoff functions $(u^{i})_{i\in N}$ that are $L$-Lipschitz
(i.e., $\mathcal{L}(u^{i})\leq L)$ and quasi-concave in one’s own action
(i.e., $u^{i}(a^{i},a^{-i})$ is quasi-concave in $a^{i}\in A^{i}$ for every
$a^{-i}\in A^{-i}),$ for all $i\in N.$

Proof. We now have $A^{i}=X^{i}$ and $a_{t}=x_{t}=g(c_{t}),$ and everything is
deterministic. Proceed as in the proof of Theorem 15, skipping part (ii) (the
use of the Law of Large Numbers) and taking $\varepsilon_{1}=0$ and $T_{1}=0.$
$\square$

_(k) Reaction function and fixed points._ The proof of Theorem 15 shows that
in the leaky calibration game, if the A-player uses a stationary strategy
given by a Lipschitz “reaction” function $g$ (i.e., he plays $g(c_{t})$ at
time $t)$, then smooth calibration implies that the forecasts $c_{t}$ are
close to fixed points of $g$ most of the time.

## References

  * [1] Azoury, K. S. and M. K. Warmuth (2001), “Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions,” _Machine Learning_ 43, 211–246.
  * [2] Babichenko, Y. (2012), “Completely Uncoupled Dynamics and Nash Equilibria,” _Games and Economic Behavior_ 76, 1–14.
  * [3] Cesa-Bianchi, N. and G. Lugosi (2006), _Prediction, Learning, and Games_ , Cambridge University Press.
  * [4] Dawid, A. P. (1982), “The Well-Calibrated Bayesian,” _Journal of the American Statistical Association_ 77, 605–613.
  * [5] Dawid, A. P. (1985), “Self-Calibrating Priors Do Not Exist: Comment,” _Journal of the American Statistical Association_ 80, 340–341.
  * [6] Foster, D. P. (1991), “Prediction in the Worst Case,” _The Annals of Statistics_ 19, 1084–1090.
  * [7] Foster, D. P. (1999), “A Proof of Calibration via Blackwell’s Approachability Theorem,” _Games and Economic Behavior_ 29, 73–78.
  * [8] Foster, D. P. and S. M. Kakade (2006), “Calibration via Regression,”  _IEEE Information Theory Workshop 2006._
  * [9] Foster, D. P. and R. V. Vohra (1997), “Calibrated Learning and Correlated Equilibrium,” _Games and Economic Behavior_ 21, 40–55.
  * [10] Foster, D. P. and R. V. Vohra (1998), “Asymptotic Calibration,” _Biometrika_ 85, 379–390.
  * [11] Foster, D. P. and R. V. Vohra (1999), “Regret in the On-Line Decision Problem,” _Games and Economic Behavior_ 29, 7–35.
  * [12] Foster, D. P. and H. P. Young (2003), “Learning, Hypothesis Testing, and Nash Equilibrium,” _Games and Economic Behavior_ 45, 73–96.
  * [13] Foster, D. P. and H. P. Young (2006), “Regret Testing: Learning to Play Nash Equilibrium without Knowing You Have an Opponent,” _Theoretical Economics_ 1, 341–367.
  * [14] Foster, J. (1999), “On Relative Loss Bounds in Generalized Linear Regression,” in _12th International Symposium on Fundamentals of Computation Theory (FCT ’99)_ , 269–280.
  * [15] Germano, F. and G. Lugosi (2007), “Global Nash Convergence of Foster and Young’s Regret Testing,” _Games and Economic Behavior_ 60, 135–154.
  * [16] Hart, S. (2005), “Adaptive Heuristics,” _Econometrica_ 73, 1401–1430; Chapter 11 of Hart and Mas-Colell (2013).
  * [17] Hart, S. and A. Mas-Colell (2000), “A Simple Adaptive Procedure Leading to Correlated Equilibrium,” _Econometrica_ 68, 1127–1150; Chapter 2 of Hart and Mas-Colell (2013).
  * [18] Hart, S. and A. Mas-Colell (2001), “A General Class of Adaptive Strategies,” _Journal of Economic Theory_ 98, 26–54; Chapter 3 of Hart and Mas-Colell (2013).
  * [19] Hart, S. and A. Mas-Colell (2003), “Uncoupled Dynamics Do Not Lead to Nash Equilibrium,” _American Economic Review_ 93, 1830–1836; Chapter 7 of Hart and Mas-Colell (2013).
  * [20] Hart, S. and A. Mas-Colell (2006), “Stochastic Uncoupled Dynamics and Nash Equilibrium,” _Games and Economic Behavior_ 57, 286–303; Chapter 8 of Hart and Mas-Colell (2013).
  * [21] Hart, S. and A. Mas-Colell (2013), _Simple Adaptive Strategies: From Regret-Matching to Uncoupled Dynamics_ , World Scientific, 2013\.
  * [22] Hart, S. and A. Mas-Colell (2015), “Markets, Correlation, and Regret-Matching,” _Games and Economic Behavior_ 93, 42–54.
  * [23] Hazan, E. and S. Kakade (2012), “(Weak) Calibration is Computationally Hard,” _25th Annual Conference on Learning Theory (COLT ’12); JMLR: Workshop and Conference Proceedings_ 23 (2012), 3.1–3.10.
  * [24] Kakade, S. M. and D. P. Foster (2004), “Deterministic Calibration and Nash Equilibrium,” in _17th Annual Conference on Learning Theory (COLT ’04)_ ; _Journal of Computer and System Sciences_ 74 (2008), 115–130.
  * [25] Lehrer, E. and E. Solan (2009), “Approachability with Bounded Memory,” _Games and Economic Behavior_ 66, 995–1004.
  * [26] Loève, M. (1978), _Probability Theory, Vol. II_ , 4th edition, Springer.
  * [27] Oakes, D. (1985), “Self-calibrating Priors Do Not Exist,” _Journal of the American Statistical Association_ 80, 339.
  * [28] Olszewski, W. (2015), “Calibration and Expert Testing,” in _Handbook of Game Theory, Vol. 4_ , H. P. Young and S. Zamir (editors), Springer, 949–984.
  * [29] Papadimitriou, C. (1994). “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence,” _Journal of Computer and System Sciences_ 48, 498–532.
  * [30] Vovk, V. (2001), “Competitive On-Line Statistics,” _International Statistical Review_ 69, 213–248.
  * [31] Young, H. P. (2009), “Learning by Trial and Error,” _Games and Economic Behavior_ 65, 626–643.

##  Appendix A Appendix

Let $C$ be a compact subset of $\mathbb{R}^{m}$ and let $\varepsilon>0.$ A
_maximal_ $2\varepsilon$_-net_ in $C$ is a maximal collection of points
$z_{1},...,z_{K}\in C$ such that $\left\|z_{k}-z_{j}\right\|\geq 2\varepsilon$
for all $k\neq j;$ maximality implies
$\cup_{k=1}^{K}B(z_{k},2\varepsilon)\supseteq C.$ Let
$\alpha_{k}(x):=[3\varepsilon-\left\|x-z_{k}\right\|]_{+},$ and put
$\bar{\alpha}(x):=\sum_{k=1}^{K}\alpha_{k}(x).$ For every $x\in C$ we have
$0\leq\alpha_{k}(x)\leq 3\varepsilon$ and $\bar{\alpha}(x)\geq\varepsilon$
(since $\alpha_{k}(x)\geq\varepsilon$ when $x\in B(z_{k},2\varepsilon),$ and
the union of these balls covers $C).$ Finally, define
$\beta_{k}(x):=\alpha_{k}(x)/\bar{\alpha}(x).$

###### Lemma 17

The functions $(\beta_{k})_{1\leq k\leq K}$ satisfy the following properties:

(i)

$\beta_{k}(x)\geq 0$ for all $x\in C\ $and all $k.$

(ii)

$\sum_{k=1}^{K}\beta_{k}(x)=1$ for all $x\in C.$

(iii)

$\beta_{k}(x)=0$ for all $x\notin B(z_{k},3\varepsilon).$

(iv)

For each $x\in C$ there are at most333333We have not tried to get the best
bounds in (iv) and (v); indeed, they may be easily reduced. $4^{m}$ indices
$k$ such that $\beta_{k}(x)>0.$

(v)

$\mathcal{L}(\beta_{k})\leq 4^{m+2}/\varepsilon$ for every $k.$

Proof. (i) and (ii) are immediate. For (iii), we have $\beta_{k}(x)>0$ iff
$\alpha_{k}(x)>0$ iff $\left\|x-z_{k}\right\|<3\varepsilon.$ This implies that
$B(z_{k},\varepsilon)\subseteq B(x,4\varepsilon).$ The open balls of radius
$\varepsilon$ with centers at $z_{k}$ are disjoint (because
$\left\|z_{k}-z_{j}\right\|\geq 2\varepsilon$ for $k\neq j),$ and so there can
be at most $4^{m}$ such balls included in $B(x,4\varepsilon)$ whose volume is
$4^{m}$ times larger; this proves (iv). For every $x,y\in C$:

$\displaystyle\left|\beta_{k}(x)-\beta_{k}(y)\right|$ $\displaystyle\leq$
$\displaystyle\left|\frac{\alpha_{k}(x)}{\bar{\alpha}(x)}-\frac{\alpha_{k}(y)}{\bar{\alpha}(x)}\right|+\left|\frac{\alpha_{k}(y)}{\bar{\alpha}(x)}-\frac{\alpha_{k}(y)}{\bar{\alpha}(y)}\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{\bar{\alpha}(x)}\left|\alpha_{k}(x)-\alpha_{k}(y)\right|+\frac{\alpha_{k}(y)}{\bar{\alpha}(x)\bar{\alpha}(y)}\sum_{j=1}^{K}\left|\alpha_{j}(x)-\alpha_{j}(y)\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{\varepsilon}\left\|x-y\right\|+\frac{3\varepsilon}{\varepsilon\cdot\varepsilon}2\cdot
4^{m}\left\|x-y\right\|\leq\frac{4^{m+2}}{\varepsilon}\left\|x-y\right\|$

(since $\bar{\alpha}(x)\geq\varepsilon$, $\alpha_{k}(x)\leq 3\varepsilon,$ and
there are at most $2\cdot 4^{m}$ indices $j$ where neither $\alpha_{j}(x)$ nor
$\alpha_{j}(y)$ vanishes); this proves (v). $\square$

Thus, the functions $(\beta_{k})_{1\leq k\leq K}$ constitute a _Lipschitz
partition of unity_ that is subordinate to the maximal $2\varepsilon$-net
$z_{1},...,z_{K}$. Next, we obtain a basis for the Lipschitz functions on $C.$

###### Lemma 18

Let $W_{L}$ be the set of functions $w:C\rightarrow[0,1]$ with
$\mathcal{L}(w)\leq L.$ Then for every $\varepsilon>0$ there exist $d$
functions $f_{1},...,f_{d}\in W_{L}$ such that for every $w\in W_{L}$ there is
a vector $\varpi\equiv\varpi_{w}\in[0,1]^{d}$ satisfying

$\max_{x\in C}\left|w(x)-\sum_{i=1}^{d}\varpi_{i}f_{i}(x)\right|<\varepsilon.$

Moreover, one can take $d=\mathrm{O}(L^{m}/\varepsilon^{m+1}).$

Proof. Put $\varepsilon_{1}:=\varepsilon/(3L).$ Let $z_{1},...,z_{K}$ be a
maximal $2\varepsilon_{1}$-net on $C,$ and let $\beta_{1},...,\beta_{K}$ be
the corresponding Lipschitz partition of unity given by Lemma 17 (for
$\varepsilon_{1}).$

Given $w\in W_{L},$ let $v(x):=\sum_{k=1}^{N}w(z_{k})\beta_{k}(x);$ then
$w(z_{k})\in[0,1]$ and we have

$\displaystyle\left|w(x)-v(x)\right|$ $\displaystyle=$
$\displaystyle\left|\sum_{k=1}^{N}\left(w(x)-w(z_{k})\right)\beta_{k}(x)\right|\leq\sum_{k:\beta_{k}(x)>0}\beta_{k}(x)\left|w(x)-w(z_{k})\right|$
$\displaystyle\leq$
$\displaystyle\sum_{k:\beta_{k}(x)>0}\beta_{k}(x)3\varepsilon_{1}L=3\varepsilon_{1}L,$

since $\beta_{k}(x)>0$ implies $\left\|x-z_{k}\right\|<3\varepsilon_{1}$ and
thus $|w(x)-w(z_{k})|\leq L\left\|x-z_{k}\right\|\leq L\cdot 3\varepsilon_{1}$
(because $\mathcal{L(}w)\leq L).$

Now $\mathcal{L}(\beta_{k})\leq 4^{m+2}/\varepsilon_{1}$ by (v) of Lemma 17;
we thus replace each $\beta_{k}$ by the sum of $Q=\left\lceil
4^{m+2}/(\varepsilon_{1}L)\right\rceil$ identical copies of
$(1/Q)\beta_{k}$—denote them $f_{k,1},...,f_{k,Q}$—which thus satisfy
$\mathcal{L}(f_{k,q})=(1/Q)\mathcal{L}(\beta_{k})\leq L,$ and so

$\left|w(x)-\sum_{k=1}^{K}\sum_{q=1}^{Q}w(z_{k})f_{k,q}(x)\right|=\left|w(x)-v(x)\right|\leq
3\varepsilon_{1}L=\varepsilon.$

The $d=KQ$ functions $(f_{k,q})_{1\leq k\leq K,1\leq q\leq Q}$ yield our
result.

Finally, $K=\mathrm{O}(\varepsilon_{1}^{-m})$ (because $C$ contains the $K$
disjoint open balls of radius $\varepsilon_{1}$ centered at the $z_{k})$ and
$Q\leq 4^{m+2}/(\varepsilon_{1}L)+1,$ and so
$d=KQ=\mathrm{O}(\varepsilon_{1}^{-m-1}L^{-1})=\mathrm{O}(\varepsilon^{-m-1}L^{m})$.
$\square$

In the game setup we construct $\varepsilon$-best reply functions that are
Lipschitz. The following lemma applies when the action spaces are finite (as
in Theorem 15), and also when they are continuous (as in Theorem 16). In the
former $C=X=\prod_{i\in N}X^{i}$ where $X^{i}=\Delta(A^{i}),$ and in the
latter $C=X=A=\prod_{i\in N}A^{i},$ and the set $\Delta(A^{i})$ is identified
with $A^{i}$; also, $\mathrm{BR}_{\varepsilon}^{i}$ stands for
$\mathrm{PBR}_{\varepsilon}^{i},$ the set of _pure_ $\varepsilon$-best
replies.

###### Lemma 19

Assume that for each player $i\in N$ the function
$u^{i}:X\rightarrow\mathbb{R}$ is a Lipschitz function with
$\mathcal{L}(u^{i})\leq L,$ and $u^{i}(\cdot,c^{-i})$ is quasi-concave on
$X^{i}$ for every fixed $c^{-i}\in X^{-i}.$ Then for every $\varepsilon>0$
there is a Lipschitz function $g^{i}:X\rightarrow X^{i}$ such that
$g^{i}(c)\in\mathrm{BR}_{\varepsilon}^{i}(c^{-i})$ for all $c\in X,$ and
$\mathcal{L}(g^{i})\leq\nu_{m}(L/\varepsilon)^{m+1}$ where the constant
$\nu_{m}$ depends only on the dimension $m.$

Proof. Put $\varepsilon_{1}:=\varepsilon/(6L).$ Let $z_{1},...,z_{K}\in C$ be
a maximal $2\varepsilon_{1}$-net on $C$, and let $\beta_{1},...,\beta_{K}$ be
the subordinated Lipschitz partition of unity given by Lemma 17. For each
$i\in N$ and $1\leq k\leq K$ take
$x_{k}^{i}\in\mathrm{BR}_{0}^{i}(z_{k}^{-i}),$ and define
$g^{i}(c):=\sum_{k=1}^{K}\beta_{k}(c)x_{k}^{i}.$ Because $\beta_{k}(c)>0$ if
and only if $\left\|c-z_{k}\right\|<3\varepsilon_{1},$ it follows that
$x_{k}^{i}\in\mathrm{BR}_{\varepsilon}^{i}(c^{-i})$ (indeed, for every
$y^{i}\in\Delta(A^{i})$ we have
$u^{i}(x_{k}^{i},c^{-i})>u^{i}(x_{k}^{i},z_{k}^{-i})-3L\varepsilon_{1}\geq
u^{i}(y^{i},z_{k}^{-i})-3L\varepsilon_{1}>u^{i}(y^{i},c^{-i})-6L\varepsilon_{1}=\varepsilon,$
where we have used $\mathcal{L}(u^{i})\leq L$ twice, and
$x_{k}^{i}\in\mathrm{BR}_{0}^{i}(z_{k}^{-i})).$ The set
$\mathrm{BR}_{\varepsilon}^{i}(c^{-i})$ is convex by the quasi-concavity
assumption, and so $g^{i}(c),$ as an average of such $x_{k}^{i},$ belongs to
$\mathrm{BR}_{\varepsilon}^{i}(c^{-i}).$

Now $\max_{c\in C}||c||\leq\sqrt{m}$ (because $C\subseteq[0,1]^{m}),$ and so
$\left\|x_{k}\right\|\leq\sqrt{m}$ (where $x_{k}=(x_{k}^{i})_{i\in N})$ for
all $k,$ and $K\leq(\sqrt{m}/\varepsilon_{1})^{m}$ (because $C\subseteq
B(0,\sqrt{m})$ contains the $K$ disjoint open balls of radius
$\varepsilon_{1}$ centered at the points $z_{k}).$ Therefore the Lipschitz
constant of $g(c)=\sum_{k=1}^{K}\beta_{k}(c)x_{k}$ satisfies, by Lemma 17 (v),
$\mathcal{L}(g)\leq\sum_{k=1}^{K}\left\|x_{k}\right\|\mathcal{L(}\beta_{k})\leq(\sqrt{m}/\varepsilon_{1})^{m}\,\sqrt{m}\,4^{m+2}/\varepsilon_{1}=\nu_{m}\varepsilon^{-m-1}L^{m+1}$
for $\nu_{m}=\sqrt{m}^{m+1}4^{m+2}6^{m+1}$. $\square$