\documentclass[10pt,a4paper]{article}
\usepackage{amsmath,amsthm}
\newtheorem{thm}{Theorem}
\begin{document}

We consider the following game between Mathematician and Adversary.
A natural $n\ge 2$ is a parameter of the game.
A game position is $n+1$ positive real numbers 
$L$, $L_1,\ldots,L_n$.
Denote by $L(t)$, $L_1(t),\ldots,L_n(t)$ their values after step $t$.

Before the game (at step $0$) all these numbers are equal to zero.

At step $t$, Mathematician announces real numbers 
$p_1,\ldots,p_n\in[0,1]$ such that $\sum_i p_i=1$.
Then Adversary announces numbers $l_1,\ldots,l_n\in[0,1]$
(not necessarily summing up to $1$).
And then the position is updated:
\begin{align*}
L_i(t)&=L_i(t-1)+l_i, \quad i=1,\ldots,n\,,\\
L(t)&=L(t-1)+p_1l_1+\dots+p_nl_n\,.
\end{align*}

The value $L(t)-\min_i L_i(t)$ is the loss of Mathematician
(who tries to make it smaller) and the gain of Adversary.

\begin{thm}
For $n=2$, for any $T$,
Adversary has a polynomially computable strategy such that 
at each step either $l_1=1$, $l_2=0$ or $l_1=0$, $l_2=1$,
and this strategy guarantees that
$$
L(T)-\min_i L_i(T)\ge c\sqrt{T}\,,
$$
where $c$ is a constant.
\end{thm}

This strategy can be considered as a strategy against Learner
in the absolute loss game or randomized simple prediction game
(cf.~\cite{howto}).

\begin{proof}
Let $\alpha<1$ be a positive constant that will be specified later.

For each $i=1,2$, the strategy stores 
the number $g_i(t)=\sqrt{T}-L(t)+L_i(t)$.

At step $t<T$ the strategy does the following.
If $g_i(t)<\sqrt{\alpha T}$ for one of $i$,
then the strategy takes $l_i=0$.
Otherwise, the strategy computes 
$g_1(t+1)g_2(t+1)$
for both possible moves of Adversary
(the move $(p,1-p)$ of Mathematician is known at the moment),
and chooses the move that minimizes this product.
In other words,
the move of Adversary is $l_1=0$, $l_2=1$ if
$p(g_1(t)+g_2(t))-g_2(t)<0$,
and $l_1=1$, $l_2=0$ otherwise.

If $g_i(t)<\sqrt{\alpha T}$, the strategy's move 
guarantees that $g_i(t+1)\le g_i(t)$, thus
$g_i(T)<\sqrt{\alpha T}$ and 
$L(t)-L_i(t)>(1-\sqrt{\alpha})\sqrt{T}$.

Let us prove that it will happen at some step $t\le T$
that $g_i(t)<\sqrt{\alpha T}$ for one of $i$.
It suffices to prove that $g_1(T)g_2(T)<\alpha T$.

Let us estimate the change of $g_1(t)g_2(t)$ at one step
assuming that $g_i(t)\ge\sqrt{\alpha T}$ for $i=1,2$.
Let the move of Mathematician be $(p,1-p)$.
Then $g_1(t+1)g_2(t+1)$ can be
$(g_1(t)-(1-p))(g_2(t)+p)$ or $(g_1(t)+(1-p))(g_2(t)-p)$
depending on the move of Adversary.
The minimum of these two values is 
$g_1(t)g_2(t)-|pg_1(t)-(1-p)g_2(t)|-p(1-p)$.
It is easy to see that the minimum of 
$p(1-p)+|p(g_1(t)+g_2(t))-g_2(t)|$ over $p$
is attained at $p=g_2(t)/(g_1(t)+g_2(t))$
(we assume here that $g_1(t)+g_2(t)\ge 1$,
which holds if $2\sqrt{\alpha T}\ge 1$),
thus the strategy guarantees that
$$
g_1(t+1)g_2(t+1)\le g_1(t)g_2(t)-g_1(t)g_2(t)/(g_1(t)+g_2(t))^2
$$
independent of the move of Mathematician.

Let us bound $g_1(t)+g_2(t)$ from above.
We see that $g_1(t)g_2(t)$ does not increase, therefore
$g_1(t)g_2(t)\le g_1(0)g_2(0)=T$
and $g_1(t)+g_2(t)\le g_1(t)+T/g_1(t)$.
Without loss of generality, assume that $g_1(t)\le g_2(t)$,
then $g_1(t)\le\sqrt{T}$, and the maximal 
(over $g_1(t)\ge \sqrt{\alpha T}$)
value of $g_1(t)+T/g_1(t)$ is attained at 
$g_1(t) = \sqrt{\alpha T}$.
Therefore, we get $g_1(t)+g_2(t)\le
\sqrt{T}(\sqrt{\alpha}+1/\sqrt{\alpha})$,
and thus
$$
g_1(t+1)g_2(t+1)\le 
  g_1(t)g_2(t)\left(1-\frac{\alpha}{(1+\alpha)^2 T}\right)\,.
$$


We have
$$
g_1(T)g_2(T)\le
  T\left(1-\frac{\alpha}{(1+\alpha)^2 T}\right)^T\le
  T\mathrm{e}^{-\frac{\alpha}{(1+\alpha)^2}}\,,
$$
%(the last inequality holds if $T>\frac{\alpha}{(1+\alpha)^2}$),
and it suffices to choose $\alpha$ such that 
$$
 \mathrm{e}^{-\frac{\alpha}{(1+\alpha)^2}} <\alpha\,.
$$
It is easy to check that $\alpha=\mathrm{e}^{-0.16}$ works,
and then $c=1-\sqrt{\alpha}$ is between $0.07$ and $0.08$.
(This value of $\alpha$ is not optimal, but in any case
$\alpha>\mathrm{e}^{-0.25}$.)
\end{proof}

\begin{thebibliography}{0}
\bibitem{howto} N.~Cesa-Bianchi, Y.~Freund, D.~Haussler, D.~Helmbold,
R.~Shapire, M.~Warmuth.
How to Use Expert Advice.
\emph{JACM}, 44(3):427--485, 1997.
\end{thebibliography}

\end{document}


































