# Optimal online Learning using potential functions

Yoav Freund

###### Abstract

We study regret-minimizing online algorithms based on potential functions.
First, we show that any algorithm with a regret bound that holds for any
$\epsilon$ is equivalent to a potential minimizing algorithm and vice versa.
Second we should a min-max learning algorithm for known horizon. We show a
regret bound that is close to optimal when the horizon is not known. Finally
we give an algorithm with second order bounds that characterize easy
sequences.

##  1 Introduction

Online prediction with expert advise has been studied extensively over the
years and the number of publications in the area is vast (see e.g. [20, 10,
16, 4, 6].

Here we focus on a simple variant of online prediction with expert advice
called the decision-theoretic online learning game (DTOL) [12]. DTOL (Figure
1) is a repeated zero sum game between a learner and an adversary. The
adversary controls the losses of $N$ actions, while the learner controls a
distribution over the actions.

For $i=1,\ldots,T$ 1. The learner chooses a weight function $P(i,j)$ over the
actions $j\in\\{1,\ldots,N\\}$
such that $\sum_{j=1}^{N}P(i,j)=1$ 2. The adversary chooses an instantaneous
loss for each of the $N$ actions:
$l_{j}^{i}\in[-1,+1]$ for $j\in\\{1,\ldots,N\\}$. 3. The cumulative loss of
action $j$ is $L^{i}_{j}=\sum_{s=1}^{i}l_{j}^{s}$. 4. The learner incurs an
instantaneous average loss defined as $\ell^{i}=\sum_{j=1}^{N}P(i,j)l_{j}^{i}$
5. The cumulative loss of the learner is $L_{\ell}^{i}=\sum_{s=1}^{i}\ell^{s}$
6. The cumulative regret of the learner with respect to action $j$ is
$R_{j}^{i}=L_{\ell}^{i}-L_{j}^{i}$.

Figure 1: Decision theoretic online learning

The goal of the learner (in the percentile version of the game) is to perform
almost as well as $k$ best actions. Specifically, we sort the regrets in
decreasing order $R_{1}^{i}\geq R_{2}^{i}\geq\cdots\geq R_{k}^{i}\geq\cdots$
and define $R_{k}^{i}$ to as the regret relative to the $\epsilon=k/M$ top
percentile, denote $R_{\epsilon}^{i}$. Our goal is to find algorithms that
guarantee small upper bounds on $R_{\epsilon}^{T}$. Known bounds have the form
$c\sqrt{T\ln{1/\epsilon}}$, but the algorithm has to be tuned based on prior
knowledge of $\epsilon$. We seek algorithms with regret bounds that hold
simultaneously for all values of $\epsilon$. In other words algorithms that do
not need to know $\epsilon$ ahead of time. The following definition formalizes
the concept of simultaneous bounds:

######  Definition 1 (Simultaneous regret bound (SRB)).

Let $G:\mathbb{R}\to[0,1]$ be a non-increasing function which maps regret
bounds to probabilities. A distribution over regrets ${\bf\Psi}$ is
simultaneously bound by $G$ if

$\forall R\in\mathbb{R}\;\;{\bf P}_{\rho\sim{\bf\Psi}}\left[\rho\geq
R\right]\leq G(R)$

A potential function is an increasing function $\phi:\mathbb{R}\to\mathbb{R}$.
Online learning algorithms based on potential functions control the regret by
upper bounding the average potential ${\bf
E}_{R\sim{\bf\Psi}}\left[\phi(R)\right]$.

######  Definition 2 (Average potential bound (APB)).

A distribution over he reals ${\bf\Psi}$ satisfies the average potential
function $\phi$ if

$\Phi\doteq{\bf E}_{R\sim{\bf\Psi}}\left[\phi(R)\right]\leq 1$

Where $\phi:\mathbb{R}\to\mathbb{R}^{+}$ is a non decreasing function. The
score $\Phi$ is as defined.

Potential functions have long been used to design and analyze online learning
algorithms. However, the choice of the potential function has been somewhat ad
hoc. Here we show a strong one to one relationship between SBR functions and
potential functions:

######  Theorem 1.

A distribution ${\bf\Psi}$ is simultaneously bounded by $B$ if and only if it
satisfies the average potential bound with $\phi(R)=B(R)^{-1}$

The proof of the theorem is in Appendix A.

Theorem 1 justifies our focus on potential functions and our quest to find the
“best” potential function.

We start with the bounded horizon case. Fixing a potential function at the end
of the game $\phi(T,R)$ and the strategies used by the learner and the
adversary, we define potential functions $\phi(i,R)$ for iterations
$i=T-1,T-2,\ldots,0$ such that the score $\Phi(t)$ is guaranteed to be equal
for all of the iterations.

$\Phi(T)=\Phi(T-1)=\cdots=\Phi(0)$

This allows us to analyze the game one iteration at a time and construct good
strategies for both sides. We name this potential based game the Integer Time
Game, the analysis of this game is given in Section 5. The analysis assumes
only that the final potential $\phi(T,R)$ is strictly positive and has
strictly positive first and second derivatives (We denote the set of functions
that have $0,\ldots,k$ strictly positive derivatives by ${\cal P}^{k}$, the
formal definition is given in Section 4)

The strategies yielded by the analysis guarantee bounds on the final score.
The adversarial strategy guarantees $\Phi^{\uparrow}\leq\Phi(T)$, while the
learner’s strategy guarantees $\Phi(T)\leq\Phi^{\downarrow}$. Unfortunately,
these bounds don’t match, i.e. $\Phi^{\uparrow}<\Phi^{\downarrow}$. In other
words our proposed strategies are not min-max optimal. The question of whether
there exist min/max strategies for the integer time game is open.

To find min/max strategies we expand the game. We call the expanded game the
discrete time game. The expansion involves giving the more options to the
adversary, but not to the learner. As a result, any upper bound
$\Phi^{\downarrow}$ that holds for a learner strategy in the discrete time
game also holds in the integer time game.

The added option for the adversary is to declare, at the beginning of each
iteration, the range of values of the instantanous losses. In the integer time
game this range is set to $[-1,+1]$. In the discrete time game the range is
chosen by the adversary on iteration $i$ to be $[-s_{i},+s_{i}]$ for $1\geq
s_{i}>0$. To keep the game balanced between the adversary and the learner we
replace the iteration number $i$ with real valued time parameter and let
$t_{i+1}=t_{i}+s_{i}^{2}$. this and another necessary adjustment are described
in Section 6. Section 6.1 describes strategies used for the discrete game
which are scaled versions of the strategies for the integer time game.

We fix the potential at the end of the game
$\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{4}$ and consider a sequence of
adversarial and learner strategies indexed by $k$: $Q_{D(k)},P_{D(k)}$, where
$\forall i,\;s^{k}_{i}=\frac{\sqrt{\mathcal{T}}}{2^{k}}$ for some constant
$\mathcal{T}$. We prove two facts regarding the limit $k\to\infty$. The first
(Thm. 9) is that
$\lim_{k\to\infty}\phi_{P_{D(k)}}^{\downarrow}-\phi_{Q_{D(k)}}^{\uparrow}\to
0$. The second (Thm. 10) is that, if $\phi(T,R)$

$\forall k,\forall 0\leq i\leq 2^{2k},t_{i}=i2^{-2k}\mathcal{T},\;\forall
R,\;\;\;,\phi_{Q_{D(k+1)}}^{\uparrow}\left(t_{i},R\right)>\phi_{Q_{D(k)}}^{\uparrow}\left(t_{i},R\right)$

Taken together these facts imply that, if the fixed potential function for the
end of the game $\boldsymbol{\phi}_{\mathcal{T}}$ is in ${\cal P}^{4}$, then
there exists a potential function $\phi(t,R)$. The adversarial strategy
corresponding to this potential function corresponds to Brownian motion. The
backwards recursion used to computer the potential for $t\leq\mathcal{T}$ is a
partial differential equation known as the Kolmogorov Backward equation.

The main result of this paper is that a single adversarial strategy, i.e.
Brownian motion, is optimal for any sufficiently convex potential functions.

The discrete time game presents the adversary with a dilemma. On the one hand,
The adversary has to declare, on each iteration, an upper bound on the range
of the losses $[-s_{i},s_{i}]$ where $s_{i}>0$. On the other hand, it wants to
set $s_{i}$ as small as possible. 111The situation is similar to a folklore
game in which each player writes down a number on a piece of paper and the
player with the largest number wins.

We introduce a variant of the game called the continuous time game to
alleviate this dilemma. In this came the adversary does not announce the step
size and the learner behaves as if the step size is infinitesimally small. In
this case time is advanced according to the variance of the actual losses.
This much more natural algorithm yields a regret bound that depends on the
cumulative variance and is smaller for easy, low variance sequences.

Until this point our theory holds for any final potential function in ${\cal
P}^{4}$. We conclude by analyzing two specific potentials.

  1. 1.

We derive a potential function and a corresponding learning algorithm that is
min/max optimal for a given time horizon $\mathcal{T}$. The optimality is in
the sense that the simultanous regret bound for time $\mathcal{T}$ has a
matching simultanous lower bound.

  2. 2.

By finding solutions to the Kolmogorov Backward equation that hold for all
$t>0$ we eliminate the need to define a final potential. As a result we get an
“anytime” learning algorithm that can be stopped at any time. The specific
potential we analyze is Normal-Hedge . NormalHedge is not min/max otimal for
any time, but it is almost optimal for all times.

##  2 related work

Most of the papers on potential based online algorithms consider one or a few
potential functions. Most common is the exponential potential, but others have
been considered [6]. A natural question is what is the difference between
potential functions and whether some potential function is “best”.

In this paper we consider a large set of potential functions, specifically,
potential functions that are strictly positive and have strictly positive
derivatives of orders up to four. The exponential potential and the
NormalHedge potential [8, 17] are member of this set.

To analyze these potential functions we define a different game, which we call
the “potential game”. In this game the primary goal of the learner is not to
minimize regret, rather, it is to minimize the final score $\Phi^{T}$. To do
so we define potential functions for intermediate steps: $0\leq t<T$.222The
analysis described here builds on a long line of work. Including the Binomial
Weights algorithm and it’s variants [5, 1, 2] as well as drifting games [19,
11].

Zero-order bounds on the regret [14] depend only on $N$ and $T$ and typically
have the form

$\max_{j}R_{j}^{T}<CE\sqrt{T\ln N}$ (1)

for some small constant $C$ (typically smaller than 2). These bounds can be
extended to infinite sets of actions by defining the $\epsilon$-regret of the
algorithm as the regret with respect to the best (smallest-loss)
$\epsilon$-percentile of the set of actions.

this replaces the bound (1) with

$\max_{j}R_{j}^{T}<CE\sqrt{T\ln\frac{1}{\epsilon}}$ (2)

Lower bounds have been proven that match these upper bounds up to a constant.
These lower bounds typically rely on constructions in which the losses
$l_{j}^{i}$ are chosen independently at random to be either $+1$ or $-1$ with
equal probabilities.

Several algorithms with refined upper bounds on the regret have been studied.
Of those, the most relevant to our work is a paper by Cesa-Bianchi, Mansour
and Stoltz [7] on second-order regret bounds. The bound given in Theorem 5 of
[7] can be written, in our notation, as:

$\max_{j}R_{j}^{T}\leq 4\sqrt{V_{T}\ln N}+2\ln N+1/2$ (3)

Where

$\mbox{Var}_{i}=\sum_{j=1}^{N}P^{i}_{j}(l_{j}^{i})^{2}-\left(\sum_{j=1}^{N}P^{i}_{j}l_{j}^{i}\right)^{2}\mbox{
and }V_{T}=\sum_{i=1}^{T}\mbox{Var}_{i}$

A few things are worth noting. First, as $|l_{j}^{i}|\leq 1$,
$\mbox{Var}_{j}\leq 1$ and therefor $V_{T}\leq T$. However $V_{T}/T$ can be
arbitrarily small, in which case inequality 3 provides a tighter bound than 1.
Intuitively, we can say that $V_{T}$ replaces $T$ in the regret bound. This
paper provides additional support for replacing $T$ with $V_{T}$ and provides
lower and upper bounds on the regret involving $V_{T}$.

##  3 Main Results

  1. 1.

Uniform regret bound There exists an online learning algorithm such that for
any $\nu>0$ (set in advance) and any $t,\epsilon$ (holds uniformly) the
following regret bound holds.

$R_{\epsilon}\leq\sqrt{(t+\nu)\left(\ln(t+\nu)+2\ln\frac{1}{\epsilon}\right)}$
(4)

  2. 2.

Second order bound

  3. 3.

optimality of Brownian motion For any potential function in ${\cal P}^{4}$ the
min/max value of any state $(t,R)$ is attained by Brownian motion on the part
of the adversary for any $s\geq t$.

##  4 Preliminaries

We define some terms and notationthat will be used in the rest of the paper.

Positivity We require that potential functions have positive derivatives for a
range of degree. To that end we use the following definition:

######  Definition 3 (Strict Positivity of degree $k$).

A function $f:\mathbb{R}\to\mathbb{R}$ is strictly positive of degree $k$,
denoted $f\in{\cal P}^{k}$ if the derivatives of orders 0 to $k$:
$f(x),\frac{d}{dx}f(x),\ldots,\frac{d^{k}}{dx^{k}}f(x)$ exist and are strictly
positive.

The following useful lemma states that ${\cal P}^{k}$ is closed under positive
conbinations.

######  Lemma 2.

Suppose that for $i=1,\ldots,n$, $f_{i}\in{\cal P}^{k}$ and $\alpha_{i}>0$,
Then $\sum_{i=1}^{k}\alpha_{i}f_{i}\in{\cal P}^{k}$

Divisibility: To reach optimality we need the set of actions to be arbitrarily
divisible. Intuitively, We replace the finite set of actions with a continuous
mass, so that each set of actions can be partitioned into two parts of equal
weight. Formally, we define the set of actions to be a probability space
$(\Omega,\sigma,\mu)$ such that $\omega\in\Omega$ is a particular action. We
require that the space is arbitrarily divisible, which means that for any
$s\in\sigma$ , there exist a partition $u,v\in\sigma$ such that $u\cup
v=s,u\cap v=\emptyset$, and ${\bf P}\left[u\right]={\bf
P}\left[v\right]=\frac{1}{2}{\bf P}\left[s\right]$.

State: The state of a game at iteration $i$, denoted ${\bf\Psi}(i)$, is a
random variable that maps each action $\omega\in\Omega$ to the cumulative
regret of $\omega$ at time $i$: $R_{\omega}^{i}$. The sequence of cumulative
regrets corresponding to action $\omega$ is the path of $\omega$:

$S_{\omega}=(R_{\omega}^{1},R_{\omega}^{2},\ldots,R_{\omega}^{N})$ (5)

Generalized binomial distribution We denote by $\mathbb{B}(n,s)$ the
distribution over the reals defined by $\sum_{i=1}^{n}X_{i}$ where $X_{i}$ are
iid binary random variables which attain the values $-s,+s$ with equal
probabilities.

Expected value shorthand: Suppose $P$ is a distribution over the reals, and
$f:\mathbb{R}\to\mathbb{R}$, we use the following short-hand notation for the
expected value of $f$ under the distribution $P$:

$P\odot f\doteq{\bf E}_{x\sim P}\left[f(x)\right]$

We define the score at iteration $i$ as the average potential with respect to
the state:

$\Phi(i)={\bf\Psi}(i)\odot\phi(i)\doteq{\bf
E}_{R\sim{\bf\Psi}(i)}\left[\phi(i,R)\right]$

Note that in this short-hand notation we suppress the variable with respect to
which the integration is defined, which will always be $R$.

Convolution: Let $A,B$ be two independent random variables. We define the
convolution $A\oplus B$ to be the distribution of $x+y$. A constant $a$
corresponds to the point mass distribution concentrated at $a$. For
convenience we define $A\ominus B=A\oplus(-B)$

##  5 Integer time game

The integer time game is described in Figure 2. The integer time game
generalizes the decision theoretic online learning problem [13] in the
following ways:

  1. 1.

The goal of the learner in DTOL is to guarantee an upper bounds on the regret.
The learner’s goal in the integer time game is to minimize the final score.
From theorem 1 we know that if we set the final potential as
$\boldsymbol{\phi}_{T}(R)=\frac{1}{G(R)}$ then the two conditions are
equivalent, allowing us to focus on the score.

  2. 2.

The number of iterations $T$ is given as input, as is the potential function
at the end: $\boldsymbol{\phi}_{T}(R)$.

  3. 3.

The actions are assumed to be divisible. For our purposes it is enough to
assume that any action can be split into two equal weight parts.

The key to the potential based analysis is that using the predefined final
potential we can define potential functions and scores for all iterations
$1,\ldots,T-1$. This is explained in the next subsection.

Initialization: • input: $T$ : The number of iterations. • Final iteration
potential function: $\boldsymbol{\phi}_{T}\in{\cal P}^{2}$ •
${\bf\Psi}(1)=\delta(0)$ is the initial state of the game which is a point
mass distribution at 0. For $i=1,2,\ldots,T$: 1. The learner chooses a non-
negative random variable over $\Omega$ that is the weight function $P(i,R)$
such that ${\bf\Psi}(i)\odot P(i)=1$ 2. The adversary chooses a function
$Q(i,R)$ that maps $i,R$ to a distribution over $[-1,+1]$. This random
variable corresponds to the instantaneous loss of each action at time $t$. 3.
We define the bias at $(i,R)$ to be $B(i,R)\doteq{\bf E}_{l\sim
Q(i,R)}\left[l\right]$ (6) 4. the average loss is
$\ell(i)={\bf\Psi}(i,R)\odot{{\left({P(i,R)B(i,R)}\right)}}$ (7) 5. The state
is updated. ${\bf\Psi}(i+1)={\bf E}_{R\sim{\bf\Psi}(i)}\left[R\oplus
Q(i,R)\right]\oplus-\ell(i)$ (8) Where $Q(i,R)$ is the distribution of the
losses of actions with respect to which the regret is $R$ after iteration
$i-1$. $\oplus$ denotes the convolution as defined above. The final score is
calculated: $\Phi(T)={\bf\Psi}(T)\odot\boldsymbol{\phi}_{T}$. The goal of the
learner is to minimize this score, the goal of the adversary is to maximize
it.

Figure 2: The integer time game

###  5.1 Defining potential Functions for all iterations

The potential game defines the final potential function
$\boldsymbol{\phi}_{T}$, at the end of the game. We will now show, that we can
extend the definition of a potential function to all iterations of the game.

A single action defines a path $S_{\omega}$ (as defined in (5)). Fixing the
strategies of the learner and the adversary determines a distribution ${\cal
D}$ over paths. We describe two equivalent ways to define $\phi_{P,Q}(i,R)$
for $i<T$

  1. 1.

Using conditional expectation We can define the potential on iteration $i$
based on the fixed potential at iteration $T$.

$\forall i=1,\ldots,T,\;\forall R\;\;\;\phi_{P,Q}(i,R)={\bf
E}_{\omega\sim{\cal D}|R_{\omega}^{i}=R}\left[\phi(T,R_{\omega}^{T})\right]$
(9)

  2. 2.

Using backward induction It is sometimes convenient to compute the the
potential for time $i$ from the potential at time $i+1$:

$\forall i=1,\ldots,T-1,R\;\;\;\phi_{P,Q}(i,R)={\bf E}_{\omega\sim{\cal
D}|M_{\omega}^{i}=R}\left[\phi_{P,Q}(i+1,R_{\omega}^{i+1})\right]$ (10)

by using backwards induction: $i=T-1,T-2,\ldots,1$ we can compute the
potential for all iterations.

We use Equations (6,7) and marginalizing over $R$ to express Equation (10) in
terms of the single step strategies:

$\forall i=1,\ldots,T-1,R\;\;\;\phi_{P,Q}(i,R)\doteq{\bf
E}_{r\sim[(R-\ell(i))\oplus Q(i,R)]}\left[\phi_{P,Q}(i+1,r)\right]$ (11)

The score at iteration $i$ is defined as $\Phi(i)={\bf\Psi}(i)\odot\phi(i)$.
The scores are all different expressions for calculating the expected final
potential for the fixed strategies $Q,P$. Therefor the scores are all equal,
as expressed in the following theorem:

######  Theorem 3.

Assuming $P(i,R),Q(i,R)$ are fixed for all $i=1,\ldots,T-1$, then

${\bf\Psi}(T)\odot\phi(T)=\Phi(T)=\Phi(T-1)=\cdots=\Phi(1)=\phi_{P,Q}(0,0)$

A few things worth noting:

  1. 1.

$\phi_{P,Q}(i,R)$ is the the final expected potential given that the paths
starts at $(i,R)$ and that the strategies used by both players in iterations
$i,\ldots,T$ are fixed. Note also that which strategies were used in
iterations $1,\ldots,i-1$ is of no consequence. The effect of past choices is
captured by the state ${\bf\Psi}(i)$.

  2. 2.

The final expected potential is equal to $\phi(0,0)$ which is the potential at
the common starting point: $i=1$, $R=0$.

###  5.2 Upper and Lower potentials

Next,we vary the strategies of one side or the other to define upper and lower
potentials.

$\exists P,\;\;\;\forall Q,\;\;\forall 1\leq i\leq T,\;\;\forall
R\in\mathbb{R},\;\;\phi_{P}^{\downarrow}(i,R)\geq\phi_{P,Q}(i,R)$ (12)
$\exists Q,\;\;\;\forall P,\;\;\;\;\forall 1\leq i\leq T,\;\;\forall
R\in\mathbb{R},\;\;\phi_{Q}^{\uparrow}(i,R)\leq\phi_{P,Q}(i,R)$ (13)

In words, $\phi_{P}^{\downarrow}$ is an upper bound on the potential that is
guaranteed by the learner strategy $P$ while $\phi_{Q_{D}}^{\uparrow}$ is a
lower bound that is guaranteed by the adversarial strategy $Q$.

Following the same argument as the one leading to Theorem 3. We define upper
and lower scores $\Phi_{P}^{\downarrow}(i),\Phi_{Q}^{\uparrow}(i)$ such that

${\bf\Psi}_{P}(T)\odot\boldsymbol{\phi}_{T}=\Phi_{P}^{\downarrow}(T)=\Phi_{P}^{\downarrow}(T-1)=\cdots=\Phi_{P}^{\downarrow}(0)=\phi_{P}^{\downarrow}(0,0)$
(14)

and

${\bf\Psi}_{Q}(T)\odot\boldsymbol{\phi}_{T}=\Phi_{Q}^{\uparrow}(T)=\Phi_{Q}^{\uparrow}(T-1)=\cdots=\Phi_{Q}^{\uparrow}(0)=\phi_{Q}^{\uparrow}(0,0)$
(15)

Our ultimate goal is to find strategies $P$ and $Q$ such that

$\forall i,R,\;\;\;\phi_{Q}^{\uparrow}(i,R)=\phi_{P}^{\downarrow}(i,R)$ (16)

in particular,
$\Phi_{Q}^{\uparrow}(0)=\phi_{Q}^{\uparrow}(0,0)=\phi_{P}^{\downarrow}(0,0)=\Phi_{P}^{\downarrow}(0)$.
This means that $Q,P$ are a min/max pair of strategies and that
$\Phi_{Q}^{\uparrow}(0)=\Phi_{P}^{\downarrow}(0)$ define the min/max value of
the game.

We do not achieve this for the integer game described in the next section. To
achieve min/max optimality we extend the integer time game to the discrete
time game (section 6) and to the continuous time game (7).

###  5.3 Strategies for the integer time game

We assume that $\boldsymbol{\phi}_{T}\in{\cal P}^{2}$, in other words, the
final potential is positive, increasing and convex. $\boldsymbol{\phi}_{T}$
defines the upper and lower potentials at time $T$:

$\phi_{Q_{I}}^{\uparrow}(T,R)=\phi_{P_{I}}^{\downarrow}(T,R)=\boldsymbol{\phi}_{T}(R)$

We define a backwards recursion for the lower potential:

$\phi_{Q_{I}}^{\uparrow}(i-1,R)=\frac{\phi_{Q_{I}}^{\uparrow}(i,R+1)+\phi_{Q_{I}}^{\uparrow}(i,R-1)}{2}$
(17)

and a backwards recursion for the upper potential:

$\phi_{P_{I}}^{\downarrow}(i-1,R)=\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)+\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}$
(18)

We define strategies that correspond to these potentials. A strategy for the
adversary:

$Q_{I}(i,R)=\begin{cases}+1&\mbox{ w.p. }\frac{1}{2}\\\ -1&\mbox{ w.p.
}\frac{1}{2}\\\ \end{cases}$ (19)

and a strategy for the learner:

$P_{I}(i,R)=\frac{1}{Z}\frac{\phi(i,R+2)-\phi(i,R-2)}{2}$ (20)

Where $Z$ is a normalization factor

$Z={\bf E}_{R\sim{\bf\Psi}(i)}\left[\frac{\phi(i,R+2)-\phi(i,R-2)}{2}\right]$

The following lemma states that these strategies guarantee the corresponding
potentials.

######  Lemma 4.

Let $i$ be an integer between $1$ and $T$

If $\phi_{Q_{I}}^{\uparrow}(i,R)\in{\cal P}^{2}$

  1. 1.

Positivity: $\phi_{Q_{I}}^{\uparrow}(i-1,R)\in{\cal P}^{2}$

  2. 2.

Adversary: The adversarial strategy (19) guarantees the recursion given in Eq.
(17)

If $\phi_{P_{I}}^{\downarrow}(i,R)\in{\cal P}^{2}$

  1. 1.

Positivity: $\phi_{P_{I}}^{\downarrow}(i-1,R)\in{\cal P}^{2}$

  2. 2.

Learner: The learner strategy (20) guarantees the recursion given in Eq. (18)

###### Proof.

We prove each claim in turn

  1. 1.

Positivity: Follows from Lemma 2.

  2. 2.

Adversary: By symmetry adversarial strategy (19) guarantees that the aggregate
loss (7) is zero regardless of the choice of the learner: $\ell(i)=0$.
Therefor the state update (8) is equivalent to the symmetric random walk:

${\bf\Psi}(i)=\frac{1}{2}{{\left({({\bf\Psi}(i)\oplus 1)+({\bf\Psi}(i)\ominus
1)}\right)}}$

Which in turn implies that if the adversary plays $Q^{*}$ and the learner
plays an arbitrary strategy $P$

$\phi_{Q_{I}}^{\uparrow}(i-1,R)=\frac{\phi_{Q_{I}}^{\uparrow}(i,R-1)+\phi_{Q_{I}}^{\uparrow}(i,R+1)}{2}$
(21)

As this adversarial strategy is oblivious to the learner’s strategy, it
guarantees that the average value at iteration $i$ is equal to the average of
the lower value at iteration $i$.

  3. 3.

Learner: Plugging learner’s strategy (20) into equation (7) we find that

$\ell(i)=\frac{1}{Z_{i}}{\bf
E}_{R\sim{\bf\Psi}(i)}\left[{{\left({\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}\right)}}B(i,R)\right]$
(22)

Consider the score at iteration $i$ when the learner’s strategy is $P^{*}$ and
the adversarial strategy $Q$ is arbitrary

$\Phi_{P^{*},Q}(i,R)={\bf E}_{R\sim{\bf\Psi}(i)}\left[{\bf E}_{y\sim
Q(i)(R)}\left[\phi(i,R+y-\ell(i))\right]\right]$ (23)

As $\phi(i,\cdot)$ is convex and as $y-\ell(i)\in[-2,2]$,

$\phi_{P_{I}}^{\downarrow}(i-1,R+y)\leq\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)+\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}+(y-\ell(i))\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}$
(24)

Combining the equations (22) and (23) we find that

$\displaystyle\Phi_{P^{*},Q}(i,R)$ $\displaystyle=$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}(i)}\left[{\bf E}_{y\sim
Q(i)(R)}\left[\phi_{P_{I}}^{\downarrow}(i,R+y-\ell(i))\right]\right]$ (25)
$\displaystyle\leq$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}(i)}\left[\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)+\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}\right]$
(26) $\displaystyle+$ $\displaystyle{\bf E}_{R\sim{\bf\Psi}(i)}\left[{\bf
E}_{y\sim
Q(i)(R)}\left[(y-\ell(i))\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}\right]\right]$
(27)

The final step is to show that the term (27) is equal to zero. As $\ell(i)$ is
a constant with respect to $R$ and $y$ the term (27) can be written as:

$\displaystyle{\bf E}_{R\sim{\bf\Psi}(i)}\left[{\bf E}_{y\sim
Q(i)(R)}\left[(y-\ell(i))\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}\right]\right]$
(28) $\displaystyle=$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}(i)}\left[B(i,R)\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}\right]$
(29) $\displaystyle-$ $\displaystyle\ell(i){\bf
E}_{R\sim{\bf\Psi}(i)}\left[\frac{\phi_{P_{I}}^{\downarrow}(i,R+2)-\phi_{P_{I}}^{\downarrow}(i,R-2)}{2}\right]$
(30) $\displaystyle=$ $\displaystyle 0$ (31)

∎

Repeating the induction steps of Lemma 4 from $i=T$ to $i=1$ yields the
following theorem.

######  Theorem 5.

Let $\boldsymbol{\phi}_{T}\in{\cal P}^{2}$, for any iteration $0\leq i\leq T$
and regret $R_{0}\in\mathbb{R}$

  * •

The lower potential guaranteed by $Q_{I}$ is

$\phi_{Q_{I}}^{\uparrow}(i,R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}(T-i,1)}\left[\boldsymbol{\phi}_{T}(R)\right]$

  * •

The upper potential guaranteed by $P_{I}$ is

$\phi_{P_{I}}^{\downarrow}(i,R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}(T-i,2)}\left[\boldsymbol{\phi}_{T}(R)\right]$

Plugging in $i=0$,$R=0$ we get the following Corrolary:

######  Corollary 6.

if the learner plays $P_{I}$ on every iteration it guarantees that the final
score satisfies

${\bf\Psi}(T)\odot\boldsymbol{\phi}_{T}\leq\mathbb{B}(T,2)\odot\boldsymbol{\phi}_{T}$

If the Adversary plays $Q_{I}$ on every iteration it guarantees that:

${\bf\Psi}(T)\odot\boldsymbol{\phi}_{T}=\mathbb{B}(T,1)\odot\boldsymbol{\phi}_{T}$

##  6 From integer to discrete time

The upper and lower bound on the final score given in Theorem 5 do not match.
If $\boldsymbol{\phi}_{T}\in{\cal P}^{2}$ then
$\mathbb{B}(T,1)\odot\boldsymbol{\phi}_{T}<\mathbb{B}(T,2)\odot\boldsymbol{\phi}_{T}$
In other words, the strategies (19,20) are not a min/max pair.333There might
be other (pure) strategies for the integer game that are a min/max pair, we
conjecture that is not the case, and seek a extension of the game that would
yield min/max strategies.

To close this gap we extend the integer time game into a new game we call the
discrete time game (Fig. 3). The discrete time game increases the options
available to the adversary, but not to the learner. As the integer step game
is a special case of the new game, any upper potential that can be guaranteed
by the learner in the discrete time game is also an upper potential for the
discrete time game.

In the integer time game the loss of each action is in the range $[-1,+1]$, in
the discrete time game the adversary chooses, on iteration $i$ a step size
$0<s_{i}\leq 1$ which restricts the losses to the range $[-s_{i},+s_{i}]$.
Note that by always choosing $s_{i}=1$, the adversary can choose to play the
integer time game.

Initialization: $t_{0}=0$
On iteration $i=1,2,\ldots$ 1. If $t_{i}=\mathcal{T}$ the game terminates. 2.
The adversary chooses a step size $0<s_{i}\leq\min(\sqrt{1-t_{i}},1)$, which
advances time by $t_{i}=t_{i-1}+s_{i}^{2}$ 3. Given $s_{i}$, the learner
chooses a distribution $P(i)$ over $\mathbb{R}$. 4. The adversary chooses a
mapping from $\mathbb{R}$ to distributions over
$[-s_{i},+s_{i}]:\;Q(t,\cdot):\mathbb{R}\to\Delta^{[-s_{i},+s_{i}]}$ 5. The
aggregate loss is calculated: $\ell(t_{i})={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[P(t_{i},R)B(t_{i},R)\right]\mbox{ where
}B(t_{i},R)\doteq{\bf E}_{y\sim Q(t_{i},R)}\left[y\right]$ (32) Such that
$|\ell(t_{i})|\leq s_{i}^{2}$ 6. The state is updated. ${\bf\Psi}(t_{i})={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[Q(t_{i},R)\oplus(R-\ell(t_{i}))\right]$ Where
$\oplus$ is a convolution as defined in the preliminaries. Upon termination,
the final value is calculated:
$\Phi(\mathcal{T})={\bf\Psi}(\mathcal{T})\odot\phi(\mathcal{T})$

Figure 3: The discrete time game

We make two additional alterations to the integer time game in order to keep
the game fair. An unfair game is one where one side always wins. We list the
alterations and then justify them.

  1. 1.

real-valued time In the integer time game we use an integer to indicate the
iteration number: $i=1,2,\ldots,T$. In the discrete time game we use an
positive real value, which we call “time” and use the update rule
$t_{i+1}=t_{i}+s_{i}^{2}$, and define the final time, which is used in the
regret bound, to be $\mathcal{T}=\sum_{i=0}^{T}s_{i}^{2}$

  2. 2.

Bounded average loss We restrict the average loss to a range much smaller than
$[-s_{i},+s_{i}]$, specifically: $|\ell(i)|\leq s_{i}^{2}$

Note that both of these conditions hold trivially when $s_{i}=1$

  1. 1.

Justification of real-valued time To justify these choices we consider the
following adversarial strategy for the discrete time game:

$Q_{D}{{\left[{s,p}\right]}}{{\left({t,R}\right)}}=\begin{cases}+s&\mbox{ w.p.
}p\\\ -s&\mbox{ w.p. }1-p\\\ \end{cases}$ (33)

From Equation (15) we get that the initial score,

$\Phi_{Q_{D}}^{\uparrow}(0)=\Phi_{Q_{D}}^{\uparrow}(T)={\bf\Psi}_{Q_{D}}(T)\odot\phi(T)$

On the other hand, we know that ${\bf\Psi}_{Q_{D}}(T)=\mathbb{B}(T,s)$.
Suppose $T$ is large enough that the normal approximation for the binomial can
be used. Let ${\cal N}(\mu,\sigma^{2})$ be the normal distribution with mean
$\mu$ and variance $\sigma^{2}$.

$\lim_{T\to\infty}\Phi_{Q_{D}}^{\uparrow}(0)={\cal N}(0,Ts^{2})\odot\phi(T)$
(34)

Recall that $\phi(T)$ is a fixed strictly convex function. It is not hard to
see that if $Ts^{2}\to 0$ minimizes $\Phi_{Q_{D}}^{\uparrow}(0)$ and makes it
equal to to $\phi(T,0)$, which means that the learner wins, while if
$Ts^{2}\to\infty$, $\Phi_{Q_{D}}^{\uparrow}(0)\to\infty$ which means that the
adversary wins. In order to keep the game balanced keep $Ts^{2}$ constant as
we let $s\to 0$. We achieve that by defining the real-valued discrete time as
$t_{j}=\sum_{i=0}^{j-1}s_{i}^{2}$.

  2. 2.

Justification of bounding average loss Suppose the game is played for $T$
iterations and that the adversary uses the strategy
$Q_{D}{{\left[{s,\frac{1}{2}+\epsilon}\right]}}{{\left({t,R}\right)}}$ and
that $s=\frac{1}{\sqrt{T}}$. In this case the loss of the learner in iteration
$i$ is $\ell(i)=2s\epsilon$ and the total loss is

$L_{\ell}^{T}=\sum_{i=0}^{T-1}\ell(i)=T2\epsilon s=\frac{2\epsilon}{s}$

.

If $\epsilon$ is kept constant as $s\to 0$ then
$\lim_{T\to\infty}L_{\ell}^{T}=\infty$, biasing the game towards the
adversary. On the other hand, if $\epsilon=s^{\alpha}$ for $\alpha<1$ then
$L_{\ell}^{T}\to 0$, biasing the game towards the learner. To keep the game
balanced we have to set $\epsilon=cs$ for some constant $c$. Without loss of
generality we set $c=1$.

Generalizing this to the game where the adversary can choose a different
$s_{i}$ in each iteration we get the constraint $|\ell(i)|\leq s_{i}^{2}$

###  6.1 Strategies for discrete time

We fix a real number $\mathcal{T}$ as the real length of the game.

We define a sequence of adversarial strategies, indexed by $k$, where the step
size of $Q_{D(k)}$ is $s_{k}=2^{-2k}\sqrt{\mathcal{T}}$.

We define a sequence of adversarial strategies $Q_{D(k)}$ and matching learner
strategies $P_{D(k)}$ for $k=0,1,2,\ldots$. The adversarial strategies are
designed so that the upper and lower potentials converge to a limit as
$k\to\infty$.

We set the time points $t_{i}=is_{k}^{2}$ for $i=0,1,\ldots,2^{2k}$. We call
the resulting games $k$-discrete and denote them as $D(k)$.

For a given $k$ we define upper and lower potentials for each $t_{i}$. This is
done by induction starting with the final potential function
$\boldsymbol{\phi}_{\mathcal{T}}(R)=\phi_{Q_{D(k)}}^{\uparrow}(\mathcal{T},R)=\phi_{P_{D(k)}}^{\downarrow}(\mathcal{T},R)$
and iterating backwards for $i=T,T-1,\ldots,0$, $t_{i}=is_{k}^{2}$

$\phi_{Q_{D(k)}}^{\uparrow}(t_{i-1},R)=\frac{\phi_{Q_{D(k)}}^{\uparrow}(t_{i},R+s_{k})+\phi_{Q_{D(k)}}^{\uparrow}(t_{i},R-s_{k})}{2}$
(35)

$\phi_{P_{D(k)}}^{\downarrow}(t_{i-1},R)=\frac{\phi_{P_{D(k)}}^{\downarrow}(t_{i},R+s_{k}(1+s_{k}))+\phi_{P_{D(k)}}^{\downarrow}(t_{i},R-s_{k}(1+s_{k}))}{2}$
(36)

These upper and lower potentials correspond to strategies for the adversary
and the learner. The adversarial strategy is

$Q_{D(k)}=\begin{cases}+s_{k}&\mbox{ w.p. }\frac{1}{2}\\\ -s_{k}&\mbox{ w.p.
}\frac{1}{2}\\\ \end{cases}$ (37)

The learner’s strategy is:

$\displaystyle
P_{D(k)}(t_{i},R)=\frac{1}{Z}\frac{\phi_{P_{D(k)}}^{\downarrow}(t_{i+1},R+s_{k}(1+s_{k}))-\phi_{P_{D(k)}}^{\downarrow}(t_{i+1},R-s_{k}(1+s_{k}))}{2}$
(38) $\displaystyle\mbox{ where }Z={\bf
E}_{R\sim{\bf\Psi}(t_{i+1})}\left[\frac{\phi_{P_{D(k)}}^{\downarrow}(t_{i+1},R+s_{k}(1+s_{k}))-\phi_{P_{D(k)}}^{\downarrow}(t_{i+1},R-s_{k}(1+s_{k})}{2}\right]$

The potentials and strategies defined above are scaled versions of the integer
time potential recursions defined in Equations (17,18) and the strategies
defined in Equations (19,20). Specifically, the games operate on lattices that
we will now describe.

The adversarial strategy $Q_{I}$ defines the following lattice over $i$ and
$R$:

$\boldsymbol{I}_{T}=\left\\{(i,2j-i)\left|0\leq i\leq T,0\leq j\leq
i\right.\right\\}$

The $k$’th adversarial strategy $Q_{D(k)}$ uses step size
$s_{k}=\sqrt{\mathcal{T}}2^{-k}$ and time increments
$s_{k}^{2}=\mathcal{T}2^{-2k}$. We define the game lattice for $k$ as the set
of $(t,R)$ pairs that are reached by $Q_{D(k)}$.

$\boldsymbol{K}_{{\mathcal{T},k}}=\left\\{(t,R)\left|t=is_{k}^{2},0\leq i\leq
2^{2k},R=(2j-i)s_{k},0\leq j\leq i\right.\right\\}$

$\boldsymbol{I}_{T}$ is a special case of $\boldsymbol{K}_{\mathcal{T},k}$
because setting $\mathcal{T}=T=2^{2k}$ we get that $s_{k}=s_{k}^{2}=1$ and
$\boldsymbol{K}_{\mathcal{T},k}=\boldsymbol{I}_{T}$.

It is not hard to show that the lattices get finer with $k$, i.e. if $j\leq
k$, $\boldsymbol{K}_{\mathcal{T},j}\subseteq\boldsymbol{K}_{\mathcal{T},k}$.

The following Lemma parallels Lemma 4 for the integer time game.

######  Lemma 7.

Let $i$ be an integer between $1$ and $T$

If $\phi_{Q_{D(k)}}^{\uparrow}(t_{i},R)\in{\cal P}^{2}$

  1. 1.

$\phi_{Q_{D(k)}}^{\uparrow}(t_{i-1},R)\in{\cal P}^{2}$

  2. 2.

The adversarial strategy (37) guarantees the recursion given in Eq. (35)

If $\phi_{P_{D(k)}}^{\downarrow}(t_{i},R)\in{\cal P}^{2}$

  1. 1.

$\phi_{P_{D(k)}}^{\downarrow}(t_{i-1},R)\in{\cal P}^{2}$

  2. 2.

The learner strategy (38) guarantees the recursion given in Eq. (36)

###### Proof.

The statement of the Lemma and the proof are scaled versions of Lemma 4 and
its proof. The iteration step is $s_{k}^{2}$ instead of $1$ while the
loss/gain of an action in a single step is $[-s_{k},s_{k}]$ instead of
$[-1,+1]$.

One change worth noting is at the step from Equation (23) and Equation (24),
where the bound $y-\ell(i)\in[-2,2]$ is replace by
$y-\ell(i)\in[-s_{k}-s_{k}^{2},s_{k}+s_{k}^{2}]$. This follows from the bound
$|\ell(i)|\leq s_{k}^{2}$ which is discussed in Section 6. ∎

######  Theorem 8.

Let $\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{2}$ be the final potential in
the discrete time game. Fix $k$ and the step size
$s_{k}=\sqrt{\mathcal{T}}2^{-k}$, and let $t_{i}=is_{k}^{2}$ for
$i=0,1,\ldots,2^{2k}$ and let $R_{0}$ be a real value, then

  * •

The lower potential guaranteed by $Q_{D(k)}$ is

$\phi_{Q_{D(k)}}^{\uparrow}(t_{i},R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}{{\left({2^{2k}-i,s_{k}}\right)}}}\left[\boldsymbol{\phi}_{\mathcal{T}}(R)\right]$
(39)

  * •

The upper potential guaranteed by $P_{D(k)}$ is

$\phi_{P_{D(k)}}^{\downarrow}(t_{i},R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}{{\left({2^{2k}-i,s_{k}(1+s_{k})}\right)}}}\left[\boldsymbol{\phi}_{\mathcal{T}}(R)\right]$
(40)

Using Theorem 8 we can show that, as $k\to\infty$, the upper lower potential
converge to the same limit.

######  Theorem 9.

Fix $\mathcal{T}$ and assume $\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{2}$.
Consider the sequence of upper and lower potentials
$\phi_{P_{D(k)}}^{\downarrow},\phi_{Q_{D(k)}}^{\uparrow}$ for
$k=0,1,2,\ldots$.

Then for any $0<t\leq\mathcal{T}$ and any $R_{0}$:

$\lim_{k\to\infty}\phi_{P_{D(k)}}^{\downarrow}(t,R_{0})=\lim_{k\to\infty}\phi_{Q_{D(k)}}^{\uparrow}(t,R_{0})={\cal
N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$ (41)

###### Proof.

We first assume that $(t,R_{0})\in\boldsymbol{K}_{j,\mathcal{T}}$ and that
$k\geq j$. We later expand to any $0<t\leq\mathcal{T}$ and any
$R_{0}\in\mathbb{R}$. Consider Equation 40 for $P_{D(k)}$ and $P_{D(j)}$,
keeping $t$ and $j$ constant and letting $k\to\infty$.

$\phi_{P_{D(j)}}^{\downarrow}(t,R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}{{\left({2^{2j}-i_{j},s_{j}(1+s_{j})}\right)}}}\left[\boldsymbol{\phi}_{\mathcal{T}}(R)\right]$
(42)

$\phi_{P_{D(k)}}^{\downarrow}(t,R_{0})={\bf E}_{R\sim
R_{0}\oplus\mathbb{B}{{\left({2^{2k}-i_{k},s_{k}(1+s_{k})}\right)}}}\left[\boldsymbol{\phi}_{\mathcal{T}}(R)\right]$
(43)

We rewrite the binomial factor in Eq (43)

$\mathbb{B}{{\left({2^{2k}-i_{k},s_{k}(1+s_{k})}\right)}}=\mathbb{B}{{\left({2^{2(k-j)}{{\left({2^{2j}-i_{j}}\right)}},2^{j-k}s_{j}(1+2^{j-k}s_{j})}\right)}}$

As $j$ is constant, $s_{j}$ is constant and so is $a_{j}\doteq 2^{2j}-i_{j}$.
Multiplying the number of steps by the variance per step we get

$Var(\mathbb{B}_{k})=2^{2(k-j)}a_{j}{{\left({2^{j-k}s_{j}(1+(2^{j-k}s_{j})}\right)}}^{2}=a_{j}s_{j}^{2}(1+(2^{j-k}s_{j}))^{2}$

As $s_{j},a_{j}$ are constants we get that
$\lim_{k\to\infty}Var(\mathbb{B}_{k})=a_{j}s_{j}$. From the central limit
theorem we get that for any $(t,R_{0})\in\boldsymbol{K}_{j,\mathcal{T}}$

$\lim_{k\to\infty}\phi_{P_{D(k)}}^{\downarrow}(t,R_{0})\odot\boldsymbol{\phi}_{\mathcal{T}}={\cal
N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$ (44)

Our argument hold for all
$(t,R_{0})\in\bigcup_{k=0}^{\infty}\boldsymbol{K}_{k,\mathcal{T}}$ which is
dense in the set $0<t\leq\mathcal{T},R_{0}\in\mathbb{R}$. On the other hand,
$\phi_{P_{D(k)}}^{\downarrow}(t,R)\odot\boldsymbol{\phi}_{\mathcal{T}}$ is
continuous in both $t$ and $R$, therefor Equation (44) holds for all $t$ and
$R$.

As similar (slightly simpler) argsument holds for the lower potential limit
$\lim_{k\to\infty}\phi_{Q_{D(k)}}^{\uparrow}(t,R_{0})$

∎

We have shown that in the limit $s\to 0$ the learner and the adversary
converge to the same potential function. In the next section we show that this
limit is the min/max solution by describing conditions under which the
adversary prefers using ever smaller steps size.

###  6.2 The adversary prefers smaller steps

Theorem 44 characterizes the limits of the upper and lower potentials, as
$k\to\infty$ are equal to each other and to ${\cal
N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$ To show that this
limit corresponds to the min/max slolution of the game we need to show that
the adversary perfers smaller steps. In other words, that for any $t,R$,
$\phi_{Q_{D(k)}}^{\uparrow}(t,R)$ increases with $k$.

To prove this claim we strengther the condition
$\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{2}$ used above to
$\boldsymbol{\phi}_{\mathcal{T}}\in^{4}$. In words, we assume that the
function $\boldsymbol{\phi}_{\mathcal{T}}(R)$ is continuous and strictly
positive and it’s first four derivatives are continuous and strictly positive.

We use the sequence of discrete adversarial strategies $Q_{D(k)},k=1,2,\ldots$
defined in Section 6.1.

######  Theorem 10.

If $\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{4}$, and $\mathcal{T}>0$ then
for any $k>0$, any $t\in[0,\mathcal{T}]$ and any $R$

$\phi_{Q_{D(k+1)}}^{\uparrow}(t,R)>\phi_{Q_{D(k)}}^{\uparrow}(t,R)$

The proof of the theorem relies on a reduction to a simpler case: dividing a
single time step of duration $\tau$ into four time steps of duration $\tau/4$

######  Lemma 11.

If $\boldsymbol{\phi}_{\tau}\in{\cal P}^{4}$, and $\tau>0$ then for any $R$

$\phi_{Q_{D(1)}}^{\uparrow}(0,R)>\phi_{Q_{D(0)}}^{\uparrow}(0,R)$

###### Proof.

The step size is $s_{k}=2^{-k}\sqrt{\tau}$, therefor
$s_{0}=\sqrt{\tau},s_{1}=\frac{\sqrt{\tau}}{2}$. The time icrement is $\Delta
t_{k}=s_{k}^{2}$, therefor $\Delta t_{0}=\tau,\Delta t_{1}=\frac{\tau}{4}$. In
other words, $k=0$ corresponds to a single step of size , while $k=1$
corresponds to four steps of size $\frac{1}{2}$.

By definition
$\boldsymbol{\phi}_{\tau}(R)=\phi_{Q_{D(0)}}^{\uparrow}(\tau,R)=\phi_{Q_{D(1)}}^{\uparrow}(\tau,R)$

For $k=0$ we we get the recursion

$\phi_{Q_{D(0)}}^{\uparrow}(0,R)=\frac{\phi_{Q_{D(0)}}^{\uparrow}(\tau,R-\sqrt{\tau})+\phi_{Q_{D(0)}}^{\uparrow}(\tau,R+\sqrt{\tau})}{2}=\frac{\boldsymbol{\phi}_{\tau}(R-\sqrt{\tau})+\boldsymbol{\phi}_{\tau}(R+\sqrt{\tau})}{2}$
(45)

For $k=1$ we we have for $i=0,1,2,3$:

$\phi_{Q_{D(0)}}^{\uparrow}{{\left({\frac{i}{4}\tau,R}\right)}}=\frac{\phi_{Q_{D(0)}}^{\uparrow}{{\left({\frac{i+1}{4}\tau,R-\frac{1}{2}\sqrt{\tau}}\right)}}+\phi_{Q_{D(0)}}^{\uparrow}{{\left({\frac{i+1}{4}\tau,R+\frac{1}{2}\sqrt{\tau}}\right)}}}{2}$
(46)

Combining Equation (46) for $k=0,1,2,3$ we get

$\displaystyle\phi_{Q_{D(1)}}^{\uparrow}(0,R)$ $\displaystyle=$
$\displaystyle\frac{1}{16}\left[\phi_{Q_{D(1)}}^{\uparrow}{{\left({\tau,R{-2}\sqrt{\tau}}\right)}}+4\phi_{Q_{D(1)}}^{\uparrow}{{\left({\tau,R{-}\sqrt{\tau}}\right)}}\right.$
$\displaystyle+\left.6\phi_{Q_{D(1)}}^{\uparrow}{{\left({\tau,R}\right)}}+4\phi_{Q_{D(1)}}^{\uparrow}{{\left({\tau,R{+}\sqrt{\tau}}\right)}}+\phi_{Q_{D(1)}}^{\uparrow}{{\left({\tau,R{+2}\sqrt{\tau}}\right)}}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{16}\left[\boldsymbol{\phi}_{\tau}{{\left({R{-2}\sqrt{\tau}}\right)}}+4\boldsymbol{\phi}_{\tau}{{\left({R{-}\sqrt{\tau}}\right)}}+6\boldsymbol{\phi}_{\tau}{{\left({R}\right)}}+4\boldsymbol{\phi}_{\tau}{{\left({R{+}\sqrt{\tau}}\right)}}+\boldsymbol{\phi}_{\tau}{{\left({R{+2}\sqrt{\tau}}\right)}}\right]$

the difference between Equations (6.2) and (45) is

$\displaystyle\phi_{Q_{D(1)}}^{\uparrow}(0,R)-\phi_{Q_{D(0)}}^{\uparrow}(0,R)$
$\displaystyle=$
$\displaystyle\frac{1}{16}\left[\boldsymbol{\phi}_{\tau}{{\left({R{-2}\sqrt{\tau}}\right)}}-4\boldsymbol{\phi}_{\tau}{{\left({R{-}\sqrt{\tau}}\right)}}+6\boldsymbol{\phi}_{\tau}{{\left({R}\right)}}-4\boldsymbol{\phi}_{\tau}{{\left({R{+}\sqrt{\tau}}\right)}}+\boldsymbol{\phi}_{\tau}{{\left({R{+2}\sqrt{\tau}}\right)}}\right]$

Our goal is to show that the LHS of Eqn. 6.2 is positive. This is equivalent
to proving positivity of

$\displaystyle g_{a}(R)$ $\displaystyle=$
$\displaystyle\frac{2}{3a^{2}}{{\left({\phi_{Q_{D(1)}}^{\uparrow}(0,R)-\phi_{Q_{D(0)}}^{\uparrow}(0,R)}\right)}}$
(49) $\displaystyle=$
$\displaystyle\frac{1}{24a^{4}}\left[\boldsymbol{\phi}_{\tau}{{\left({R{-2}a}\right)}}-4\boldsymbol{\phi}_{\tau}{{\left({R{-}a}\right)}}+6\boldsymbol{\phi}_{\tau}{{\left({R}\right)}}-4\boldsymbol{\phi}_{\tau}{{\left({R{+}a}\right)}}+\boldsymbol{\phi}_{\tau}{{\left({R{+2}a}\right)}}\right]$

where $a=2s_{1}=\sqrt{\tau}$

The function $g_{a}(R)$ has a special form called “divided differences”. The
proof of the following lemma uses this fact to show that Eqn (49) is strictly
postive.

######  Lemma 12.

If $\boldsymbol{\phi}_{\tau}\in{\cal P}^{4}$ and $\tau>0$, then $\forall
R,g_{s}(R)>0$

The proof of Lemma 12 is given in appendix B

###### Proof.

of Theorem 10
The proof is by double induction over $k$ and over $t_{i}$. For $k=1,2,\ldots$
we consider the the loss step $s=2^{-k-1}\sqrt{\mathcal{T}}$ and the time step
$\Delta t=s^{2}=2^{-2k-2}\mathcal{T}$. For each game iteration
$i=0,\ldots,2^{2k}-1$ we fix the potential at time
$t_{1}=(i+1)2^{-2k}\mathcal{T}$ and We consider the difference between the
potential at $t_{0}=(i+1)2^{-2k}\mathcal{T}$

we take a finite backward induction over $t=T-2^{-2k},T-2\times
2^{-2k},T-3\times 2^{-2k},\cdots,0$. Our inductive claims are that
$\phi_{k+1}(t,R)>\phi_{k}(t,R)$ and $\phi_{k+1}(t,R)$,$\phi_{k}(t,R)$ are
continuous, strongly convex and have a strongly positive fourth derivative.
That these claims carry over from $t=T-i\times 2^{-2k}$ to $t=T-(i+1)\times
2^{-2k}$ follows directly from Lemma LABEL:lemma:n-strictly-convex.

The theorem follows by forward induction on $k$.

∎

Theorem 9 characterizes the limit

$\lim_{k\to\infty}\phi_{P_{D(k)}}^{\downarrow}(t,R_{0})=\lim_{k\to\infty}\phi_{Q_{D(k)}}^{\uparrow}(t,R_{0})={\cal
N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$ (50)

Theorem 10 states that increasing $k$ is always advantageous to the adversary.

Together these theorems show that the the min/max optimal potential function
is ${\cal N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$.

##  7 Brownian motion

There seems to be a paradox: the adversary prefers to set $s_{i}>0$ as small
as possible. On the other hand, there is no minimal strictly positive number,
so whatever the adversary chooses has to be suboptimal. In other words, time
is not continuous, it increases in discrete steps. As that is the case, why is
brownian motion still the correct way to compute the potential?

One can use the following argument: the learner knows the range
$[-s_{i},+s_{i}]$ for the next instantanous losses before it has to choose the
weights he places on the actions. On the other hand, it does not know the
range of the following losses, but he knows that the adversary always prefers
small ranges. The safe thing for the learner to do is to assume that the
following steps will be infinitesmaly small, i.e. that the future losses form
a brownian process

It is well known that the limit of random walks where $s\to 0$ and $\Delta
t=s^{2}$ is the the Brownian or Wiener process (see [15]).

An alternative characterization of Brownian Process is

${\bf P}\left[X_{t+\Delta
t}=x_{1}|X_{t}=x_{0}\right]=e^{-\frac{(x_{1}-x_{0})^{2}}{2\Delta t}}$

The backwards recursion that defines the value function is the celebrated
Backwards Kolmogorov Equation with no drift and unit variance

$\frac{\partial}{\partial t}\phi(t,R)+\frac{1}{2}\frac{\partial^{2}}{\partial
R^{2}}\phi(t,R)=0$ (51)

Given a final value function with a strictly positive fourth derivative we can
use Equation (51) to compute the value function for all $0\leq t\leq T$. We
will do so in he next section.

##  8 The continuous time game and bounds for easy sequences

In Section 6 we have shown that the integer time game has a natural extension
to a setting where $\Delta t_{i}=s_{i}^{2}$. We also demonstrated sequences of
adversarial strategies $S_{1},S_{2},\ldots$ such that
$\sup_{k\to\infty}{\phi_{Q}^{\uparrow}}_{k}(0,R)=$

We characterized the optimal adversarial strategy for the discrete time game
(Section LABEL:sec:discrete-Time-Game), which corresponds to the adversary
choosing the loss to be $s_{i}$ or $-s_{i}$ with equal probabilities. A
natural question at this point is to characterize the regret when the
adversary is not optimal, or the sequences are “easy”.

To see that such an improvement is possible, consider the following constant
adversary. This adversary associates the same loss to all actions on iteration
$i$, formally, $Q(i,R)=l$. In this case the average loss is also equal to $l$,
$\ell(i)=l$ which means that all of the instantaneous regrets are
$r=l-\ell(t_{i})=0$, which, in turn, implies that
${\bf\Psi}(i)={\bf\Psi}(i+1)$. As the state did not change, it makes sense to
set $t_{i+1}=t_{i}$, rather than $t_{i+1}=t_{i}+s_{i}^{2}$.

We observe two extremes for the adversarial behavior. The constant adversary
described above for which $t_{i+1}=t_{i}$, and the random walk adversary
described earlier, in which each action is split into two, one half with loss
$-s_{i}$ and the other with loss $+s_{i}$. In which case
$t_{i+1}=t_{i}+s_{i}^{2}$ which is the maximal increase in $t$ that the
adversary can guarantee. The analysis below shows that these are two extremes
on a spectrum and that intermediate cases can be characterized using a
variance-like quantity.

We define a variant of the discrete time game (LABEL:sec:discrete-Time-Game)
For concreteness we include the learner’s strategy, which is the limit of the
strategy in the discrete game when $s_{i}\to 0$.

Set $t_{1}=0$ Fix maximal step $0<s<1$ On iteration $i=1,2,\ldots$ 1. If
$t_{i}=T$ the game terminates. 2. Given $t_{i}$, the learner chooses a
distribution $P(i)$ over $\mathbb{R}$:
$P^{cc}(t,R)=\frac{1}{Z^{cc}}\left.\frac{\partial}{\partial
r}\right|_{r=R}\phi(t,r)\mbox{ where }Z^{cc}={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[\left.\frac{\partial}{\partial
r}\right|_{r=R}\phi(t,r)\right]$ (52) 3. The adversary chooses a step size
$0<s_{i}\leq s$ and a mapping from $\mathbb{R}$ to distributions over
$[-s_{i},+s_{i}]$: $Q(t):\mathbb{R}\to\Delta^{[-s_{i},+s_{i}]}$ 4. The
aggregate loss is calculated: $\ell(t_{i})={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[P^{cc}(t_{i},R)B(t_{i},R)\right],\;\mbox{
where }B(t_{i},R)\doteq{\bf E}_{y\sim Q(t_{i},R)}\left[y\right]$ (53) the
aggregate loss is restricted to $|\ell(t_{i})|\leq cs_{i}^{2}$. 5. Increment
$t_{i+1}=t_{i}+\Delta t_{i}$ where $\Delta t_{i}={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[H(t_{i},R)\;\;{\bf E}_{y\sim
Q(t_{i},R)}\left[(y-\ell(t_{i}))^{2}\right]\right]$ (54) Where
$H(t_{i},R)=\frac{1}{Z^{H}}\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{r=R}\phi(t_{i},r)\mbox{ and }Z^{H}={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{r=R}\phi(t_{i},r)\right]$ (55) 6. The state is updated.
${\bf\Psi}(t_{i+1})={\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[Q(t_{i})(R)\oplus(R-\ell(t_{i}))\right]$

Figure 4: The continuous time game and learner strategy

Our characterization applies to the limit where the $s_{i}$ are small.
Formally, we define

######  Definition 4.

We say that an instance of the discrete time game is $(n,s,\tau)$-bounded if
it consists of $n$ iterations and $\forall\;\;0<i\leq n,\;\;s_{i}<s$ and
$\sum_{j=1}^{n}s_{j}^{2}=\tau$

Note that $\tau>t_{n}$ and that $\tau$ depends only on the ranges $s_{i}$
while $t_{n}$ depends on the variance. $t_{n}=T$ is the dominant term in the
regret bound, while $\tau$ controls the error term.

######  Theorem 13.

Let $\phi\in{\cal P}^{\infty}$ be a potential function that satisfies the
Kolmogorov backward equation (51). Fix the total time $\tau$ and let $G_{n}$
be an $(n,\sqrt{\frac{\tau}{n}},\tau)$-bounded game. Let $n\to\infty$.

Then

$\Phi({\bf\Psi}(\tau))\leq\Phi({\bf\Psi}(0))+O{{\left({\frac{1}{\sqrt{n}}}\right)}}$

The proof is given in appendix C

If we define

$V_{n}=t_{n}=\sum_{i=1}^{n}\Delta t_{i}=\sum_{i=1}^{n}{\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf E}_{y\sim
Q(t_{i},R)}\left[H(t_{i},R)((y-\ell(t_{i}))^{2})\right]\right]$ (56)

We can use $V_{n}$ instead of $T$ giving us a variance based bound.

##  9 Anytime potential functions

The results up to this point hold for any potential function in ${\cal
P}^{4}$. Given a final potential function
$\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{4}$ we can compute the potential
for any $0\leq t\leq\mathcal{T}$ and any $R$ using the equation

$\phi(t,R)={\cal N}(R_{0},\mathcal{T}-t)\odot\boldsymbol{\phi}_{\mathcal{T}}$
(57)

By using uses the $R$-derivative of this potential function to define the
weights the learner guarantees that the final average score is at most
$\phi(0,0)$.

A major limition of this result is that the horizon $\mathcal{T}$ is set in
advance. It is desirable that the potential is defined without knowledge of
the horizon. In what follows we show that Hedge and NormalHedge can both be
used in such “anytime” algorithms.

Our solution is based on the observation that a potential function satisfies
Eqn (57) if and only if it satisfies the Kolmogorov backwards PDE (51):

$\frac{\partial}{\partial t}\phi(t,R)+\frac{1}{2}\frac{\partial^{2}}{\partial
r^{2}}\phi(t,R)=0$ (58)

The potential $\boldsymbol{\phi}_{\mathcal{T}}\in{\cal P}^{4}$ defines a
boundary condition of the PDE.

We derive our anytime algorithm by finding solutions to the Kolmogorov PDE
that are not restricted in time, and that have a fixed parametric form. In
other words, the evolution of the potential with time is defined by changing
the parameter values, without changing the form.

We consider two solutions to the PDE, the exponential potential and the
NormalHedge potential. We give the form of the potential function that
satisfies Kolmogorov Equation 51, and derive the regret bound corresponding to
it.

The exponential potential function which corresponds to exponential weights
algorithm corresponds to the following equation

$\phi_{\mbox{\tiny exp}}(R,t)=e^{\sqrt{2}\eta R-\eta^{2}t}$

Where $\eta>0$ is the learning rate parameter.

Given $\epsilon$ we choose $\eta=\sqrt{\frac{\ln(1/\epsilon)}{t}}$ we get the
regret bound that holds for any $t>0$

$R_{\epsilon}\leq\sqrt{2t\ln\frac{1}{\epsilon}}$ (59)

Note that the algorithm depends on the choice of $\epsilon$, in other words,
the bound does not hold for all values of $\epsilon$ at the same time.

The NormalHedge value is

$\phi_{\mbox{\tiny
NH}}(R,t)=\begin{cases}\frac{1}{\sqrt{t+1}}\exp\left(\frac{R^{2}}{2(t+1)}\right)&\mbox{if
}R\geq 0\\\ \frac{1}{\sqrt{t+1}}&\mbox{if }R<0\end{cases}$ (60)

The function $\phi_{\mbox{NH}}(R,t)$, restricted to $R\geq 0$ is in ${\cal
P}^{4}$ and is a constant for $R\leq 0$.

The regret bound we get is:

$R_{\epsilon}\leq\sqrt{(t+1)\left(2\ln\frac{1}{2\epsilon}+\ln(t+1)\right)}$
(61)

This bound is slightly larger than the bound for exponential weights, however,
the NormalHedge bound holds simultaneously for all $\epsilon>0$ and the
algorithm requires no tuning.

## References

  * [1] Jacob Abernethy, John Langford, and Manfred K Warmuth.  Continuous experts and the binning algorithm.  In International Conference on Computational Learning Theory, pages 544–558. Springer, 2006.
  * [2] Jacob Abernethy, Manfred K Warmuth, and Joel Yellin.  Optimal strategies from random walks.  In Proceedings of The 21st Annual Conference on Learning Theory, pages 437–446. Citeseer, 2008.
  * [3] Saad Ihsan Butt, Josip Pečarić, and Ana Vukelić.  Generalization of popoviciu-type inequalities via fink’s identity.  Mediterranean journal of mathematics, 13(4):1495–1511, 2016.
  * [4] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth.  How to use expert advice.  Journal of the ACM (JACM), 44(3):427–485, 1997.
  * [5] Nicolo Cesa-Bianchi, Yoav Freund, David P Helmbold, and Manfred K Warmuth.  On-line prediction and conversion strategies.  Machine Learning, 25(1):71–110, 1996.
  * [6] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * [7] Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz.  Improved second-order bounds for prediction with expert advice.  Machine Learning, 66(2):321–352, 2007.
  * [8] Kamalika Chaudhuri, Yoav Freund, and Daniel J Hsu.  A parameter-free hedging algorithm.  Advances in neural information processing systems, 22, 2009.
  * [9] Carl de Boor.  Divided differences.  arXiv preprint math/0502036, 2005.
  * [10] Meir Feder, Neri Merhav, and Michael Gutman.  Universal prediction of individual sequences.  IEEE transactions on Information Theory, 38(4):1258–1270, 1992\.
  * [11] Yoav Freund and Manfred Opper.  Drifting games and brownian motion.  Journal of Computer and System Sciences, 64(1):113–132, 2002.
  * [12] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [13] Yoav Freund and Robert E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of Computer and System Sciences, 55(1):119–139, August 1997\.
  * [14] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * [15] Mark Kac.  Random walk and the theory of brownian motion.  The American Mathematical Monthly, 54(7P1):369–391, 1947.
  * [16] Nick Littlestone and Manfred K Warmuth.  The weighted majority algorithm.  Information and computation, 108(2):212–261, 1994.
  * [17] Haipeng Luo and Robert E Schapire.  Achieving all with no parameters: Adanormalhedge.  In Conference on Learning Theory, pages 1286–1304. PMLR, 2015.
  * [18] Tiberiu Popoviciu.  Sur certaines inégalités qui caractérisent les fonctions convexes.  Analele Stiintifice Univ.“Al. I. Cuza”, Iasi, Sectia Mat, 11:155–164, 1965.
  * [19] Robert E Schapire.  Drifting games.  Machine Learning, 43(3):265–291, 2001.
  * [20] Volodimir G Vovk.  Aggregating strategies.  Proc. of Computational Learning Theory, 1990, 1990.

##  Appendix A Proof of Theorem 1

###### Proof.

  * •

${\bf\Psi}$ satisfies a simultaneous bound for $B$ if it satisfies an average
potential bound for $\phi=B^{-1}$
Assume by contradiction that ${\bf\Psi}$ does not satisfy the simultaneous
bound. In other words there exists $a\in\mathbb{R}$ such that ${\bf
P}_{R\sim{\bf\Psi}}\left[R>a\right]>B(a)$. From Markov inequality and the fact
that $\phi$ is non decreasing we get

${\bf E}_{R\sim{\bf\Psi}}\left[\phi(R)\right]\geq\phi(a){\bf
P}_{R\sim{\bf\Psi}}\left[R>a\right]>\phi(a)B(a)=\frac{B(a)}{B(a)}=1$

but ${\bf E}_{R\sim{\bf\Psi}}\left[\phi(R)\right]>1$ contradicts the average
potential assumption for the potential $\phi(R)=B(R)^{-1}$

  * •

${\bf\Psi}$ satisfies an average potential bound for $\phi=B^{-1}$ if it
satisfies a simultaneous bound for $B$
As $\phi$ is a non-decreasing function, and assuming $R,R^{\prime}$ are drawn
independently at random according to ${\bf\Psi}$:

$\displaystyle{\bf E}_{R\sim{\bf\Psi}}\left[\phi(R)\right]$ $\displaystyle=$
$\displaystyle{\bf E}_{R\sim{\bf\Psi}}\left[\phi(R){\bf
P}_{R^{\prime}\sim{\bf\Psi}}\left[\phi(R^{\prime})\geq\phi(R)\right]\right]$
(62) $\displaystyle\leq$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}}\left[\phi(R){\bf
P}_{R^{\prime}\sim{\bf\Psi}}\left[R^{\prime}\geq R\right]\right]$ (63)
$\displaystyle<$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}}\left[\phi(R)B(R)\right]$ (64) $\displaystyle=$
$\displaystyle{\bf E}_{R\sim{\bf\Psi}}\left[\frac{B(R)}{B(R)}\right]={\bf
E}_{R\sim{\bf\Psi}}\left[1\right]=1$ (65)

∎

##  Appendix B Divided differences of a function

The function $g_{s}(R)$ has a special form called “divided difference” that
has been extensively studied [18, 3, 9]. and is closely related to to
derivatives of different orders. Using this connection and the fact that
$\phi(\cdot,R)\in{\cal P}^{4}$ we prove the following lemma:

We conclude that if $\phi(t^{\prime},R)$ has a strictly positive fourth
derivative then $\phi_{k+1}(t,R)>\phi_{k}(t,R)$ for all $R$, proving the first
part of the lemma.

The second part of the lemma follows from the fact that both $\phi_{k+1}(t,R)$
and $\phi_{k}(t,R)$ are convex combinations of $\phi(t,R)$ and therefor retain
their continuity and convexity properties.

A function $\boldsymbol{\phi}$ that satisfies inequality
LABEL:eqn:4thOrderConvex is said to be 4’th order convex (see details in in
[3]).

Following[3] we give a brief review of divided differences and of
$n$-convexity.

Let $f:[a,b]\to\mathbb{R}$ be a function from the segment $[a,b]$ to the
reals.

######  Definition 5 ($n$’th order divided difference of a function).

The $n$’th order divided different of a function $f:[a,b]\to\mathbb{R}$ at
mutually distinct and ordered points $a\leq x_{0}<x_{1}<\cdots<x_{n}\leq b$
defined recursively by

$[x_{i};f]=f(x_{i}),\;i\in 0,\ldots n,$
$[x_{0},\ldots,x_{n};f]=\frac{[x_{1},\ldots,x_{n};f]-[x_{0},\ldots,x_{n-1};f]}{x_{n}-x_{0}}$

######  Definition 6 ($n$-convexity).

A function $f:[a,b]\to\mathbb{R}$ is said to be $n$-convex $n\geq 0$ if and
only if for all choices of $n+1$ distinct points: $a\leq
x_{0}<x_{1}<\cdots<x_{n}\leq b$, $[x_{0},\ldots,x_{n};f]\geq 0$ holds.

$n$-convexity is has a close connection to the sign of $f^{(n)}$ \- the $n$’th
derivative of $f$, this connection was proved in 1965 by popoviciu [18].

######  Theorem 14.

If $f^{(n)}$ exists then f is $n$-convex if and only if $f^{(n)}\geq 0$.

The next lemma states that the function $g(R)>0$ as defined in Equation
(LABEL:eqn:divdiff).

###### Proof.

of Lemma (12)

Fix $t$ and define $f(x)=\phi(t,x)$. Let
$(x_{0},x_{1},x_{2},x_{3},x_{4})=(R-2s,R-s,R,R+s,R+2s)$

Using this notation we can rewrite $g(R)$ in the form

$h(x_{0},x_{1},x_{2},x_{3},x_{4})=\frac{1}{24s^{4}}{{\left({f(x_{4})-4f(x_{3})+6f(x_{2})-4f(x_{1})+f(x_{0})}\right)}}$
(66)

Is the 4-th order divided difference of $\phi(t,\cdot)$

  1. 1.

$[x_{i};f]=f(x_{i})$

  2. 2.

$[x_{i},x_{i+1};f]=\frac{f(x_{i+1})-f(x_{i})}{s}$

  3. 3.

$[x_{i},x_{i+1},x_{i+2};f]=\frac{\frac{f(x_{i+2})-f(x_{i+1})}{s}-\frac{f(x_{i+1})-f(x_{i})}{s}}{2s}=\frac{f(x_{i+2})-2f(x_{i+1})+f(x_{i})}{2s^{2}}$

  4. 4.

$\displaystyle[x_{i},x_{i+1},x_{i+2},x_{i+3};f]$ $\displaystyle=$
$\displaystyle\frac{\frac{f(x_{i+3})-2f(x_{i+2})+f(x_{i+1})}{2s^{2}}-\frac{f(x_{i+2})-2f(x_{i+1})+f(x_{i})}{2s^{2}}}{3s}$
$\displaystyle=$
$\displaystyle\frac{f(x_{i+3})-3f(x_{i+2})+3f(x_{i+1})-f(x_{i})}{6s^{3}}$

  5. 5.

$\displaystyle[x_{i},x_{i+1},x_{i+2},x_{i+3},x_{i+4};f]$ $\displaystyle=$
$\displaystyle\frac{\frac{f(x_{i+4})-3f(x_{i+3})+3f(x_{i+2})-f(x_{i+1})}{6s^{3}}-\frac{f(x_{i+3})-3f(x_{i+2})+3f(x_{i+1})-f(x_{i})}{6s^{3}}}{4s}$
$\displaystyle=$
$\displaystyle\frac{f(x_{i+4})-4f(x_{i+3})+6f(x_{i+2})-4f(x_{i+1})+f(x_{i})}{24s^{4}}$

∎

##  Appendix C Proof of Theorem 13

We start with two technical lemmas

######  Lemma 15.

Let $f(x)\in{\cal P}^{2}$, i.e. $f(x),f^{\prime}(x),f^{\prime\prime}(x)>0$ for
all $x\in\mathbb{R}$, let $h(x)$ be a uniformly bounded function: $\forall
x,\;\;|h(x)|<1$. Let ${\bf\Psi}$ be a distribution over $\mathbb{R}$. If ${\bf
E}_{x\sim{\bf\Psi}}\left[f(x)\right]$ is well-defined (and finite) , then
${\bf E}_{x\sim{\bf\Psi}}\left[h(x)f^{\prime}(x)\right]$ is well defined (and
finite) as well.

###### Proof.

Assume by contradiction that ${\bf
E}_{x\sim{\bf\Psi}}\left[h(x)f^{\prime}(x)\right]$ is undefined. Define
$h^{+}(x)=\max(0,h(x))$. As $f^{\prime}(x)>0$, this implies that either ${\bf
E}_{x\sim{\bf\Psi}}\left[h^{+}(x)f^{\prime}(x)\right]=\infty$ or ${\bf
E}_{x\sim{\bf\Psi}}\left[(-h)^{+}(x)f^{\prime}(x)\right]=\infty$ (or both).

Assume wlog that ${\bf
E}_{x\sim{\bf\Psi}}\left[h^{+}(x)f^{\prime}(x)\right]=\infty$. As
$f^{\prime}(x)>0$ and $0\leq h^{+}(x)\leq 1$ we get that ${\bf
E}_{x\sim{\bf\Psi}}\left[f^{\prime}(x)\right]=\infty$. As $f(x+1)\geq
f^{\prime}(x)$ we get that ${\bf E}_{x\sim{\bf\Psi}}\left[f(x)\right]=\infty$
which is a contradiction. ∎

######  Lemma 16.

Let $f(x,y)$ be a differentiable function with continuous derivatives up to
degree three. Then

$\displaystyle f(x_{0}+\Delta x,y_{0}+\Delta
y)=f(x_{0},y_{0})+\left\\{\left.\frac{\partial}{\partial
x}\right|_{\tiny\begin{matrix}x,y=\\\
x_{0},y_{0}\end{matrix}}f(x,y)\right\\}\Delta
x+\left\\{\left.\frac{\partial}{\partial y}\right|_{\tiny\begin{matrix}x,y=\\\
x_{0},y_{0}\end{matrix}}f(x,y)\right\\}\Delta y$ (67) $\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{2}}{\partial
x^{2}}\right|_{\tiny\begin{matrix}x,y=\\\
x_{0},y_{0}\end{matrix}}f(x,y)\right\\}\Delta
x^{2}+\left\\{\left.\frac{\partial^{2}}{\partial x\partial
y}\right|_{\tiny\begin{matrix}x,y=\\\
x_{0},y_{0}\end{matrix}}f(x,y)\right\\}\Delta x\Delta
y+\frac{1}{2}\left\\{\left.\frac{\partial^{2}}{\partial
y^{2}}\right|_{\tiny\begin{matrix}x,y=\\\
x_{0},y_{0}\end{matrix}}f(x,y)\right\\}\Delta y^{2}$ (68) $\displaystyle+$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial
x^{3}}\right|_{\tiny\begin{matrix}x,y=\\\ x_{0}+t\Delta x,y_{0}+t\Delta
y\end{matrix}}f(x,y)\right\\}\Delta
x^{3}+\frac{1}{2}\left\\{\left.\frac{\partial^{3}}{\partial x^{2}\partial
y}\right|_{\tiny\begin{matrix}x,y=\\\ x_{0}+t\Delta x,y_{0}+t\Delta
y\end{matrix}}f(x,y)\right\\}\Delta x^{2}\Delta y$ (70)
$\displaystyle+\frac{1}{2}\left\\{\left.\frac{\partial^{3}}{\partial x\partial
y^{2}}\right|_{\tiny\begin{matrix}x,y=\\\ x_{0}+t\Delta x,y_{0}+t\Delta
y\end{matrix}}f(x,y)\right\\}\Delta x\Delta
y^{2}+\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial
y^{3}}\right|_{\tiny\begin{matrix}x,y=\\\ x_{0}+t\Delta x,y_{0}+t\Delta
y\end{matrix}}f(x,y)\right\\}\Delta y^{3}$

for some $0\leq t\leq 1$.

###### Proof.

of Lemma 16 Let $F:[0,1]\to\mathbb{R}$ be defined as $F(t)=f(x(t),y(t))$ where
$x(t)=x_{0}+t\Delta x$ and $y(t)=y_{0}+t\Delta y$. Then $F(0)=f(x_{0},y_{0})$
and $F(1)=f(x_{0}+\Delta x,y_{0}+\Delta y)$. It is easy to verify that

$\frac{d}{dt}F(t)=\frac{\partial}{\partial x}f(x(t),y(t))\Delta
x+\frac{\partial}{\partial y}f(x(t),y(t))\Delta y$

and that in general:

$\frac{d^{n}}{dt^{n}}F(t)=\sum_{m=1}^{n}{n\choose
m}\frac{\partial^{n}}{\partial x^{m}\partial y^{n-m}}f(x_{0}+t\Delta
x,y_{0}+t\Delta y)\Delta x^{m}\Delta y^{n-m}$ (71)

As $f$ has partial derivatives up to degree 3, so does $F$. Using the Taylor
expansion of $F$ and the intermediate point theorem we get that

$f(x_{0}+\Delta x,y_{0}+\Delta
y)=F(1)=F(0)+\frac{d}{dt}F(0)+\frac{1}{2}\frac{d^{2}}{dt^{2}}F(0)+\frac{1}{6}\frac{d^{3}}{dt^{3}}F(t^{\prime})$
(72)

Where $0\leq t^{\prime}\leq 1$. Using Eq (71) to expand each term in Eq. (72)
completes the proof. ∎

###### Proof.

of Theorem 13
We prove the claim by an upper bound on the increase of potential that holds
for any iteration $1\leq i\leq n$:

$\Phi({\bf\Psi}(t_{i+1}))\leq\Phi({\bf\Psi}(t_{i}))+as_{i}^{3}\mbox{ for some
constant }a>0$ (73)

Summing inequality (73) over all iterations we get that

$\Phi({\bf\Psi}(T))\leq\Phi({\bf\Psi}(0))+c\sum_{i=1}^{n}s_{i}^{3}\leq\Phi({\bf\Psi}(0))+as\sum_{i=1}^{n}s_{i}^{2}=\Phi({\bf\Psi}(0))+asT$
(74)

From which the statement of the theorem follows.

We now prove inequality (73). We use the notation $r=y-\ell(i)$ to denote the
instantaneous regret at iteration $i$.

Applying Lemma 16 to $\phi(t_{i+1},R_{i+1})=\phi(t_{i}+\Delta
t_{i},R_{i}+r_{i})$ we get

$\displaystyle\phi(t_{i}+\Delta t_{i},R_{i}+r_{i})$ $\displaystyle=$
$\displaystyle\phi(t_{i},R_{i})$ (75) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial}{\partial\rho}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}$ (76) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial}{\partial\tau}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\Delta t_{i}$ (77)
$\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{2}}{\partial\rho^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{2}$ (78) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial^{2}}{\partial
r\partial\tau}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}\Delta t_{i}$ (79)
$\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{2}}{\partial\tau^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\Delta t_{i}^{2}$ (80)
$\displaystyle+$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial\rho^{3}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{3}$ (81)
$\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{3}}{\partial\rho^{2}\partial\tau}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{2}\Delta t_{i}$
(82) $\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{3}}{\partial\rho\partial\tau^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}\Delta t_{i}^{2}$
(83) $\displaystyle+$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial\tau^{3}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}\Delta
t_{i}^{3}$ (84)

for some $0\leq g\leq 1$.

By assumption $\phi$ satisfies the Kolmogorov backward equation:

$\frac{\partial}{\partial\tau}\phi(\tau,\rho)=-\frac{1}{2}\frac{\partial^{2}}{\partial
r^{2}}\phi(\tau,\rho)$

Combining this equation with the exchangeability of the order of partial
derivative (Clairiaut’s Theorem) we can substitute all partial derivatives
with respect to $\tau$ with partial derivatives with respect to $\rho$ using
the following equation.

$\frac{\partial^{n+m}}{\partial\rho^{n}\partial\tau^{m}}\phi(\tau,\rho)=(-1)^{m}\frac{\partial^{n+2m}}{\partial\rho^{n+2m}}\phi(\tau,\rho)$

Which yields

$\displaystyle\phi(t_{i}+\Delta t_{i},R_{i}+r_{i})$ $\displaystyle=$
$\displaystyle\phi(t_{i},R_{i})$ (85) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial}{\partial\rho}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}$ (86) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial^{2}}{\partial\rho^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}{{\left({\frac{r_{i}^{2}}{2}-\Delta
t_{i}}\right)}}$ (87) $\displaystyle-$
$\displaystyle\left\\{\left.\frac{\partial^{3}}{\partial\rho^{3}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}\Delta t_{i}$ (88)
$\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{4}}{\partial\rho^{4}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\Delta t_{i}^{2}$ (89)
$\displaystyle+$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial\rho^{3}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{3}$ (90)
$\displaystyle-$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{4}}{\partial\rho^{4}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{2}\Delta t_{i}$
(91) $\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{5}}{\partial\rho^{5}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta
t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}\Delta t_{i}^{2}$
(92) $\displaystyle-$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{6}}{\partial\rho^{6}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i}+g\Delta t_{i},R_{i}+gr_{i}\end{matrix}}\phi(\tau,\rho)\right\\}\Delta
t_{i}^{3}$ (93)

From the assumption that the game is $(n,s,T)$-bounded we get that

  1. 1.

$|r_{i}|\leq s_{i}+cs_{i}^{2}\leq 2s_{i}$

  2. 2.

$\Delta t_{i}\leq s_{i}^{2}\leq s^{2}$

given these inequalities we can rewrite the second factor in each term as
follows, where $|h_{i}(\cdot)|\leq 1$

  * •

For (86): $r_{i}=2s_{i}\frac{r_{i}}{2s_{i}}=2s_{i}h_{1}(r_{i})$.

  * •

For (87): $r_{i}^{2}-\frac{1}{2}\Delta
t_{i}=4s_{i}^{2}\frac{r_{i}^{2}-\frac{1}{2}\Delta
t_{i}}{4s_{i}^{2}}=4s_{i}^{2}h_{2}(r_{i},\Delta t_{i})$

  * •

For (88): $r_{i}\Delta t_{i}=2s_{i}^{3}\frac{r_{i}\Delta
t_{i}}{2s_{i}^{3}}=2s_{i}^{3}h_{3}(r_{i},\Delta t_{i})$

  * •

For (89): $\Delta t_{i}^{2}=s_{i}^{4}\frac{\Delta
t_{i}^{2}}{s_{i}^{4}}=s_{i}^{3}h_{4}(\Delta t_{i})$

  * •

For (90):
$r_{i}^{3}=8s_{i}^{3}\frac{r_{i}^{3}}{8s_{i}^{3}}=8s_{i}^{3}h_{5}(r_{i},\Delta
t_{i})$

  * •

For (91): $r_{i}^{2}\Delta t_{i}=4s_{i}^{4}\frac{r_{i}^{2}\Delta
t_{i}}{4s_{i}^{4}}=4s_{i}^{3}h_{6}(r_{i},\Delta t_{i})$

  * •

For (92): $r_{i}\Delta t_{i}^{2}=2s_{i}^{5}\frac{r_{i}\Delta
t_{i}^{2}}{2s_{i}^{5}}$

  * •

For (93): $\Delta t_{i}^{3}=s_{i}^{6}\frac{\Delta t_{i}^{3}}{s_{i}^{6}}$

We therefor get the simplified equation

$\displaystyle\phi(t_{i}+\Delta t_{i},R_{i}+r_{i})$ $\displaystyle=$
$\displaystyle\phi(t,R)+\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r+\left\\{\left.\frac{\partial}{\partial
t}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\Delta t$ $\displaystyle+$
$\displaystyle\frac{1}{2}\left\\{\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r^{2}$ $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial^{2}}{\partial r\partial
t}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}\Delta t_{i}$
$\displaystyle+$
$\displaystyle\frac{1}{6}\left\\{\left.\frac{\partial^{3}}{\partial
r^{3}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r_{i}^{3}+O(s^{4})$

and therefor

$\displaystyle\phi(t_{i}+\Delta t_{i},R+r)$ $\displaystyle=$
$\displaystyle\phi(t_{i},R)+\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}r$ (94) $\displaystyle+$
$\displaystyle\left\\{\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}(r^{2}-\Delta t_{i})+O(s^{3})$

Our next step is to consider the expected value of (94) wrt
$R\sim{\bf\Psi}(t_{i})$, $y\sim Q(t_{i},R)$ for an arbitrary adversarial
strategy $Q$.

We will show that the expected potential does not increase:

${\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf E}_{y\sim
Q(t_{i},R)}\left[\phi(t_{i}+\Delta
t_{i},R+y-\ell(t_{i}))\right]\right]\leq{\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[\phi(t_{i},R)\right]$ (95)

Plugging Eq (94) into the LHS of Eq (95) we get

$\displaystyle{\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf E}_{y\sim
Q(t_{i},R)}\left[\phi(t_{i}+\Delta t_{i},R+y-\ell(t_{i}))\right]\right]$ (96)
$\displaystyle=$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[\phi(t_{i},R)\right]$ (97) $\displaystyle+$
$\displaystyle{\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf E}_{y\sim
Q(t_{i},R)}\left[\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}(y-\ell(t_{i}))\right]\right]$
(98) $\displaystyle+$ $\displaystyle{\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf
E}_{y\sim Q(t_{i},R)}\left[\left\\{\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}((y-\ell(t_{i}))^{2}-\Delta
t_{i})\right]\right]$ (99) $\displaystyle+$ $\displaystyle O(s^{3})$ (100)

Some care is needed here. we need to show that the expected value are all
finite. We assume that the expected potential (Eq (97) is finite. Using Lemma
15 this implies that the expected value of higher derivatives of
$\frac{\partial}{\partial R}\phi(R)$ are also finite.444I need to clean this
up and find an argument that the expected value for mixed derivatives is also
finite.

To prove inequality (73), we need to show that the terms 98 and 99 are smaller
or equal to zero.

Term (98) is equal to zero:
As $\ell(t_{i})$ is a constant relative to $R$ and $y$, and
$\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}$ is a constant with respect to
$y$ we can rewrite (98) as

${\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}{\bf E}_{y\sim
Q(t_{i},R)}\left[y\right]\right]-\ell(t_{i}){\bf
E}_{R\sim{\bf\Psi}(t_{i})}\left[\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\right]$ (101)

Combining the definitions of $\ell(t)$ (32) and and the learner’s strategy
$P^{cc}$ (52) we get that

$\displaystyle\ell(t_{i})$ $\displaystyle=$ $\displaystyle{\bf
E}_{R\sim{\bf\Psi}{t_{i}}}\left[\frac{1}{Z}\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}{\bf E}_{y\sim
Q(i,R)}\left[y\right]\right]\mbox{ where }Z={\bf
E}_{R\sim{\bf\Psi}{t_{i}}}\left[\frac{1}{Z}\left\\{\left.\frac{\partial}{\partial
r}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}\right]$ (102)

Plugging (102) into (101) and recalling the requirement that
$\ell(t_{i})<\infty$ we find that term (98) is equal to zero.

Term (99) is equal to zero:
As $\Delta t_{i}$ is a constant relative to $y$, we can take it outside the
expectation and plug in the definition of $\Delta t_{i}$ (54)

${\bf E}_{R\sim{\bf\Psi}(t_{i})}\left[{\bf E}_{y\sim
Q(t_{i},R)}\left[Q(t_{i},R)\right]{\left\\{\left.\frac{\partial^{2}}{\partial
r^{2}}\right|_{\tiny\begin{matrix}\tau,\rho=\\\
t_{i},R\end{matrix}}\phi(\tau,\rho)\right\\}(y-\ell(t_{i}))^{2}}-\Delta
t_{i}\right]=\Delta t_{i}-\Delta t_{i}=0$ (103)

Where $G(t_{i},R)$ is defined in Equation (LABEL:eqn:SecondOrderDerivative) We
find that (99) is zero.

Finally (100) is negligible relative to the other terms as $s\to 0$. ∎