\clearpage
\begin{center}
{\bf \LARGE Supplementary material for \\[7pt]
``Adaptation to the Range in $K$--Armed Bandits''} \\[15pt]
{\Large by H{\'e}di Hadiji and Gilles Stoltz}
\end{center}

\vspace{2cm} \

\section{Adaptation to the Range for Linear Bandits}
\label{sec:linear-app}

To illustrate the generality of the techniques discussed in this paper, we quickly describe how these
can be used to obtain range adaptive algorithms for linear bandits. This section is meant for illustration
and not for completeness. In particular, we focus on the case of (oblivious) adversarial linear bandits:
we refer the reader to \citet[Chapter~27]{lattimore_szepesvari_2020}, which we follow closely, for a more
thorough description of the setting; we do not describe the application of our techniques to stochastic linear bandits.

\paragraph{Learning protocol.}
A finite action set $\cA \subset \R^d$, of cardinality $K$, is given. (The setting of vanilla $K$--armed bandits considered in
the rest of the article corresponds to $\cA$ formed by the vertices of the probability simplex of $\R^K$.)
The environment selects beforehand a sequence $(y_t)_{t \geq 1}$ of vectors in $\R^d$ satisfying a boundedness assumption:
there exists an interval $[m,M]$ such that
\begin{equation}
\label{eq:bounded-linearbandits}
\forall t \geq 1, \ \
\forall x \in \cA, \qquad
\dotptr{x}{y_t} \in [m,M]\,.
\end{equation}
We assume that the player does not know in advance $m$ nor $M$.
To simplify the exposition, we also assume that $m \leq 0 \leq M $.

At every time step, the player chooses an action $X_t \in \mathcal A$ and receives and only observes the payoff $\dotptr{X_t}{y_t}$.
It does not observe $y_t$ nor the payoffs $\dotptr{x}{y_t}$ associated with choices $x \ne X_t$. The action
$X_t$ is chosen independently at random according to a distribution over $\cA$ denoted by $p_t = \bigl( p_t(a) \bigr)_{a \in \cA}$.

The expected regret is defined as
\[
R_T(y_{1:T}) = \max_{x \in \mathcal A} \sum_{t = 1}^T \dotptr{x}{y_t} - \E \! \left[ \sum_{t = 1}^T \dotptr{X_t}{y_t} \right].
\]

\paragraph{Estimating the unobserved payoffs.}
As in the case of vanilla $K$--armed bandits, the key is to estimate unobserved payoffs.
We may actually build an estimate $\what y_t$ of the vectors $y_t$, from which we form
the estimates $\dotptr{x}{\what{y}_t}$. This estimate takes advantage of the linear structure
of the problem.

Fix a distribution $\pi$ such that the non-negative symmetric matrix
\[
M(\pi) \eqdef \sum_{x \in \mathcal A} \pi(x) \, x x^{\!\top}
\]
is invertible: such a distribution exists whenever $\cA$ spans $\R^d$,
which we may assume with no loss of generality; see Lemma~\ref{lem:lin_extra_expl}
below. This distribution $\pi$ will be used to explore the arms; it is in general not uniform
over the arms.
For all distributions $q$ over $\cA$ and
all $\gamma \in (0,1]$, the distribution $p = (1 - \gamma) q + \gamma \pi$
is such that the non-negative symmetric matrix $M(p)$ is invertible as well
(as it is larger than $\gamma\,M(\pi)$, in the sense of the partial inequality $\succcurlyeq$
over non-negative symmetric matrices). We only use distributions $p_t$ of this form.
We may then define
\begin{equation}
\label{eq:lin_est_formula}
\what y_t = M(p_t)^{-1} \, X_t \dotptr{X_t}{y_t}
\end{equation}
and note that
\begin{equation}
\label{eq:ylin-unbiased}
\E\bigl[ \what y_t \,\big|\, p_t \bigr]
=  M(p_t)^{-1} \Biggl( \underbrace{\sum_{x \in \mathcal A} p_t(x) \, x x^{\!\top}}_{= M(p_t)} y_t \Biggr) = y_t\,;
\end{equation}
indeed, conditioning on $p_t$ amounts to integrating over the random choice of $X_t$ according to $p_t$.

\paragraph{An algorithm adaptive to the unknown range.}
When the range is given, a well-known strategy is to use plain exponential weights over actions in $\mathcal A$
with the estimates $\dotptr{x}{\what{y}_t}$ to obtain distributions $q_t$ that are then mixed with $\pi$
to form the final distributions $p_t$.
When the range is unknown, we suggest to simply replace plain exponential weights
with AdaHedge (the difference lies in the tuning of the rates $\eta_t$), which leads to Algorithm~\ref{algo:adahedge_lin}.
In this algorithm, we refer to rates $\gamma_t$ as exploration rates (and not as extra-exploration rates as in
Algorithm~\ref{algo:adahedge}) and similarly, to $\pi$ as the exploration distribution. This is because
for adversarial linear bandits, exploration was always required even to get expected results (unlike
for $K$--armed bandits, see the introduction of Section~\ref{sec:mainadahedge}).

\begin{figure}[t]
	\renewcommand\footnoterule{}
	\begin{algorithm}[H]
		\begin{algorithmic}[1]
			\caption{\label{algo:adahedge_lin} AdaHedge for adversarial linear bandits}
			\STATE \textbf{Input:} an exploration distribution $\pi$ over $\mathcal A$ and exploration rates $(\gamma_t)_{t \geq 1}$ in $[0,1]$
			\STATE \textbf{Initialization:} $\eta_1 = +\infty$ and $q_{1}$ is the uniform distribution over $\cA$
			\FOR{rounds $t = 1,  \dots$}
			\STATE Define $p_t$ by mixing $q_t$ with $\pi$ according to \vspace{-.25cm} \\
			\[
			p_t = (1 - \gamma_t) q_t + \gamma_t \pi
			\vspace{-.3cm}
			\]
			\STATE Draw an arm $X_t \sim p_t$ (independently at random according to the distribution $p_t$)
			\STATE Get and observe the payoff $\dotptr{X_t}{y_t}$
			\STATE Compute estimates $\dotptr{x}{\what{y}_t}$ of all payoffs according to~\eqref{eq:lin_est_formula}
			\STATE Compute the mixability gap $\delta_t$ based on the distribution $q_t$ and on these estimates:
			\[
			\delta_t =\left\{
			\begin{split}
			& - \sum_{x \in \mathcal A} q_t(x)\,\dotptr{x}{\what{y}_t} +
                \frac{1}{\eta_t} \log \Biggl( \sum_{x \in \mathcal A} q_t(x) \e^{\eta_t \dotptr{x}{\what{y}_t}} \Biggr)
			\quad & \text{if } \eta_t < + \infty \\
			& - \sum_{x \in \mathcal A} q_t(x)\, \dotptr{x}{\what{y}_t} + \max_{x \in \mathcal A} \dotptr{x}{\what{y}_t} \quad & \text{if } \eta_t = + \infty
			\end{split}\right.
			\]
			\STATE Compute the learning rate $\displaystyle{\eta_{t+1} = \Biggl( \sum_{s = 1}^t \delta_s \Biggr)^{-1}} \ln K$
			\STATE Define $q_{t+1}$ component-wise as \vspace{-.3cm}
			\[
			~ \hspace{2.5cm} q_{t+1}(a) = \exp \! \left( \eta_{t+1} \sum_{s =1}^{t} \dotptr{a}{\what{y}_s} \right)
			\Bigg/ \sum_{x \in \mathcal A} \exp \! \left( \eta_{t+1} \sum_{s = 1}^{t} \dotptr{x}{\what{y}_s} \right) \vspace{-.3cm}
			\]
			\ENDFOR
		\end{algorithmic}
	\end{algorithm}
\end{figure}

The analysis of this algorithm relies on the same ingredients as the ones already encountered
in Section~\ref{sec:adahedge-distrfree}, with the addition of the following lemma, that quantifies
the quality of the exploration.
This lemma requires that $\mathcal A$ spans $\R^d$, which we may assume with no loss
of generality (otherwise, we just replace $\R^d$ by the vector space generated by $\cA$).

\begin{lemma}[{\citealp[Theorem 21.1]{lattimore_szepesvari_2020}}]
\label{lem:lin_extra_expl}
There exists a distribution $\pi$ over $\mathcal A$ such that
\[
M(\pi) = \sum_{x \in \mathcal A} \pi(x) \, x x^{\!\top} \;  \mbox{is invertible} \qquad  \mbox{and} \qquad
\max_{x \in \mathcal A}  x^\top M(\pi)^{-1} x  = d\,.
\]
\end{lemma}

We are now ready to state the main result of this section. It is the counterpart of Theorem~\ref{th:adv_talpha_bound};
for the sake of simplicity, we only state it for the value $\alpha = 1/2$.

\begin{theorem}
AdaHedge for adversarial linear bandits (Algorithm~\ref{algo:adahedge_lin})
with the extra-exploration
\[
\gamma_t = \min \Bigl\{1/2, \, \sqrt{2.5 \,  d (\log K) t^{-1/2}} \Bigr\}
\]
ensures that for all bounded ranges $[m,M]$ containing~$0$, for all oblivious individual
sequences $y_1,\,y_2,\ldots$ satisfying the boundedness condition~\eqref{eq:bounded-linearbandits},
\[
R_T(y_{1:T}) \leq 12(M-m) \sqrt{d T \ln K} + 18(M-m) d \log K\,.
\]
\end{theorem}

The proof starts by following closely the one of Theorem~\ref{th:adv_talpha_bound}
(provided in Appendix~\ref{sec:proof:thUBadv});
the differences are underlined and dealt with in the second part of the proof.

\bp
By Reminder~\ref{rem:adahedge}, since the player plays the AdaHedge strategy over the payoff estimates $\dotptr{x}{\what{y}_t}$,
the pre-regret satisfies
\[
\max_{x \in \mathcal A} \sum_{t = 1}^T  \dotptr{x}{\what{y}_t} - \sum_{t = 1}^T \sum_{a \in \mathcal A} q_t(a) \, \dotptr{a}{\what{y}_t}
\leq 2 \sqrt{V_T \log K} +  M_T \left(2 + \frac{4}{3} \log K \right)
\]
with $\displaystyle{V_T = \sum_{t = 1}^T \sum_{x \in \mathcal A} q_t(x) \, \bigl( \dotptr{x}{\what{y}_t} \bigr)^2}$
and
\[
M_T = \max \bigl\{ \dotptr{x}{\what{y}_t} : t \leq T \ \mbox{and} \ x \in \cA \bigr\}
- \min \bigl\{ \dotptr{x}{\what{y}_t} : t \leq T \ \mbox{and} \ x \in \cA \bigr\}\,.
\]
Since $\gamma_t \leq 1/2$, we have
$q_t(x) \leq 2 \, p_t(x)$ for all $x \in \cA$. We therefore define
\[
V'_T = \sum_{t = 1}^T \sum_{x \in \mathcal A} p_t(x) \, \bigl( \dotptr{x}{\what{y}_t} \bigr)^2
\]
and have $V_t \leq 2 V'_T$.
By the tower rule, based on the equality~\eqref{eq:ylin-unbiased},
and given that the expectation of a maximum is larger than the maximum of the
expectations (for the first inequality),
and by the definition of the $p_t$ (for the second inequality), we have
proved so far that
\begin{align*}
R_T(y_{1:T})
& \leq \E\! \left[ \max_{x \in \mathcal A} \sum_{t = 1}^T  \dotptr{x}{\what{y}_t}
- \sum_{t = 1}^T \sum_{a \in \mathcal A} p_t(a) \, \dotptr{a}{\what{y}_t} \right] \\
& \leq \E\! \left[ \max_{x \in \mathcal A} \sum_{t = 1}^T  \dotptr{x}{\what{y}_t}
- \sum_{t = 1}^T \sum_{a \in \mathcal A} q_t(a) \, \dotptr{a}{\what{y}_t} \right]
+ \E \! \left[ \sum_{t = 1}^T \gamma_t \sum_{a \in \mathcal A} \bigl( \pi(a) - q_t(a) \bigr) \, \dotptr{a}{\what{y}_t} \right] \\
& \leq \E\Bigg[2\sqrt{2 V'_T \log K} + M_T \left(2 + \frac{4}{3} \log K \right) \Bigg]
+ \sum_{t = 1}^T \gamma_t \underbrace{\sum_{a \in \mathcal A} \bigl( \pi(a) - q_t(a) \bigr) \, \dotptr{a}{y_t}}_{ \leq (M-m)} \,.
\end{align*}
Hence by Jensen's inequality
and by the bounds $\E[V'_T] \leq (M-m)^2 d T$ and $M_T \leq 2(M-m)d/\gamma_T$
proved below, we finally get
\begin{align*}
R_T(y_{1:t})
& \leq 2 \sqrt{2 \, \E[V'_T] \log K} + \E[M_T] \left(2 + \frac{4}{3} \log K \right)
+ (M-m) \sum_{t = 1}^T \gamma_t \\
&\leq 2\sqrt{2} (M-m) \sqrt{d T \ln K} + \left(2 + \frac{4}{3} \ln K \right) \frac{2(M-m)d}{\gamma_T} + (M-m) \sum_{t = 1}^T \gamma_t \\
& \leq 3(M-m) \sqrt{d T \ln K} + 9(M-m) \frac{d\ln K}{\gamma_T} + (M-m) \sum_{t = 1}^T \gamma_t\,.
\end{align*}
Replacing the $\gamma_t$ by their values and using the same bounds as at
the beginning of Appendix~\ref{sec:proof:thUBadv} yields the claimed result;
the factor $12$ in the bound comes from
\[
3 + \sqrt{10} + 9 \sqrt{\frac{2}{5}} \leq 12\,.
\]
We only need to prove the two claimed bounds to complete the proof;
they can be extracted from the proof of Theorem 27.1 by \citet{lattimore_szepesvari_2020}
but we provide derivations for the sake of completeness. \smallskip

\noindent \emph{Proof of $M_T \leq 2(M-m)d/\gamma_T$.}
We fix $x \in \cA$ and $t \leq T$. We recall that
$M(p_t)$ and thus $M(p_t)^{-1}$ are positive definite symmetric matrices.
By the Cauchy-Schwarz inequality applied with the norm induced by
the positive $M(p_t)^{-1}$,
\[
\bigl| x^{\!\top} M(p_t)^{-1} X_t \bigr|
\leq \sqrt{x^{\!\top} M(p_t)^{-1} x} \,\, \sqrt{X_t^{\!\top} M(p_t)^{-1} X_t}
\leq \max_{x \in \mathcal A} \Big\{ x^{\!\top} M(p_t)^{-1} x \Big\}\,.
\]
As indicated right before~\eqref{eq:lin_est_formula},
we have $M(p_t) \succcurlyeq \gamma_t \, M(\pi)$ and therefore
$M(p_t)^{-1} \curlyeqprec M(\pi)^{-1}/\gamma_t$. This entails
\[
\bigl| x^{\!\top} M(p_t)^{-1} X_t \bigr|
\leq \frac{1}{\gamma_t} \max_{x \in \mathcal A} \Big\{ x^{\!\top} M(\pi)^{-1} x \Big\}
= \frac{d}{\gamma_t}
\leq \frac{d}{\gamma_T}\,,
\]
where the equality follows from Lemma~\ref{lem:lin_extra_expl}
and where we used $\gamma_T \leq \gamma_t$ for the second inequality.
Finally, keeping in mind that we assumed $m \leq 0 \leq M$,
\[
x^{\!\top} \what{y}_t =
\underbrace{x^{\!\top} M(p_t)^{-1} \, X_t}_{\in [-d/\gamma_t,d/\gamma_t]} \underbrace{\dotptr{X_t}{y_t}}_{\in [m,M]}
\in \left[ - \frac{d \max\{-m,M\}}{\gamma_T}, \, \frac{d \max\{-m,M\}}{\gamma_T} \right],
\]
from which the bound
\[
M_t = 2 \, \frac{d \max\{-m,M\}}{\gamma_T} \leq \frac{2 d (M-m)}{\gamma_T}
\]
follows, as desired. \smallskip

\noindent
\emph{Proof of $\E[V'_T] \leq (M-m)^2 d T$.}
Since $\bigl| \dotptr{X_t}{y_t} \bigr| \leq \max\{-m,M\} \leq M-m$,
the definition~\eqref{eq:lin_est_formula} leads to
\begin{align*}
\bigl( \dotptr{x}{\what{y}_t} \bigr)^2
= \Bigl( x^{\!\top} M(p_t)^{-1} \, X_t \dotptr{X_t}{y_t} \Bigr)^2
& \leq (M-m)^2 \, \Bigl( x^{\!\top} M(p_t)^{-1} \, X_t \Bigr)^2 \\
& = (M-m)^2 \, \dotptr{X_t}{M(p_t)^{-1} x} \dotptr{x}{M(p_t)^{-1} X_t}\,.
\end{align*}
Therefore, summing over $x \in \cA$ and using the very definition of $M(p_t)$, we get
\begin{align*}
\sum_{x \in \cA} p_t(x) \, \bigl( \dotptr{x}{\what{y}_t} \bigr)^2
& \leq (M-m)^2 \, X_t^{\!\top} M(p_t)^{-1} \left( \sum_{x \in \cA} p_t(x) \, x x^{\!\top} \right) M(p_t)^{-1} X_t \\
& = (M-m)^2 \, X_t^{\!\top} M(p_t)^{-1} X_t
= (M-m)^2  \Tr \Bigl( M(p_t)^{-1} X_t X_t^\top \Bigr)\,.
\end{align*}
Now, by the linearity of the trace,
\[
\E \biggl[ \Tr \Bigl( M(p_t)^{-1} X_t X_t^\top \Bigr) \biggr]
= \E\! \left[ \sum_{x \in \mathcal A} p_t(x) \Tr \Bigl( M(p_t)^{-1} x x^\top \Bigr) \right]
= \E \bigl[ \Tr(I_d) \bigr] = d\,,
\]
where $I_d$ is the $d$--dimensional identity matrix.
Collecting all bounds together and summing over $t$
yields the claimed inequality $\E[V'_T] \leq (M-m)^2 d T$.
\end{proof}


\section{Bandits with Losses (i.e., Known Upper End $M$ on the Range)}
\label{sec:bandits-gains-losses}

In this section, we provide details on the various claims and results
hinted at in the paragraph ``Known upper end $M$ on the payoff range''
of Section~\ref{sec:bdgainslosses}.

We will only discuss distribution-free and distribution-dependent upper bounds
on the regret, as well as distribution-dependent lower bounds on the regret. This is
because the $\smash{(M-m)\sqrt{KT}}$ distribution-free regret lower bound of~\citet{AuCBFrSc02}
holds even in the case when both ends $m$ and $M$ of the range are known.

When the upper end~$M$ of the payoff range is known,
$\ln T$ distribution-dependent regret rates are possible
and there exists an algorithm achieving the optimal problem-dependent constant (Section~\ref{sec:HTlnT}).
Also, $\sqrt{KT}$ scale-free distribution-free regret upper bounds may be achieved
(Section~\ref{sec:TsallisKTpossible}), which exactly match the distribution-free lower bound.
We could not exhibit a strategy that would simultaneously achieve both optimal distribution-dependent
and distribution-free regret bounds, unlike what is known in the case of a known payoff range (the KL-UCB-switch
strategy by~\citealp{garivier2018kl}) and unlike
what we achieved in the main body of the article when adapting to the unknown range or unknown
upper end $M$ on the range. We however conjecture that this should be possible and that, at least, no trade-off exists
between the two bounds (i.e., we conjecture that Theorem~\ref{thm:adaptive_lower_bound} should not hold).

More precisely,
the case considered in this section corresponds to the models $\Dmod_{-,M}$,
for $M \in \R$, defined as
\[
\Dmod_{-,M} = \bigcup_{\substack{m \in \R, \\ m < M}} \Dmod_{m, M}\,.
\]
We may adapt Definitions~\ref{def:free} and~\ref{def:dep} to define
the concepts of distribution-free and distribution-dependent rates for adaptation to the
lower end of the range by considering the model $\Dmod_{-,M}$ therein
(just as we did in Remark~\ref{rk:th1OKDm+} for the models $\Dmod_{m,+}$).

\subsection{Known~$M$ but Unknown~$m$, Part~1: Distribution-Dependent Bounds}
\label{sec:HTlnT}

The results of this section actually also hold more generally for semi-bounded payoffs,
which correspond to the models $\Dmod_{-\infty,M}$, for $M \in \R$, defined as
the sets of probability distributions with a first moment supported on $(-\infty,M]$.
Note that we have the strict inclusion $\Dmod_{-,M} \subset \Dmod_{-\infty, M}$
as distributions in $\Dmod_{-\infty, M}$ are not bounded in general.

The DMED strategy of~\citet{honda15anon-asymptotic} does achieve a $\ln T$ distribution-dependent
rate for adaptation to the lower end of the range and is even competitive against all bandit problems
in~$\Dmod_{-\infty,M}$. The achieved upper bound is asymptotically optimal
as indicated by Reminder~\ref{rem:LRBK}.

\begin{reminder}[\citealp{honda15anon-asymptotic}, main theorem]
\label{rem:DMED}
The regret of the DMED strategy is bounded, for all bandit problems $\nup$ in $\Dmod_{-\infty, M}$, by
\[
\limsup_{T\to \infty}\frac{R_T( \nup)}{\ln T} \leq \sum_{a = 1}^K \frac{\Delta_a}{\Kinf( \nu_a, \mu^\star, \Dmod_{-\infty,  M})}\,.
\]
\end{reminder}

The nice and deep result of Reminder~\ref{rem:DMED} implies that from the distribution-dependent point of view,
adaptation to the lower end $m$ of the range is automatic (if such a lower end exists: result holds
also when there is no lower bound on the payoffs).
Our intuition and understanding for this situation is the following. When the model is $\Dmod_{m,M}$ for known
ends $m$ and $M$, the optimal constant for the $\ln T$ regret on a bandit problem $\nup$ in $\Dmod_{m,M}$ is given
(see again Reminder~\ref{rem:LRBK}) by
\[
C(\nup,m,M) = \sum_{a = 1}^K \frac{\Delta_a}{\Kinf( \nu_a, \mu^\star,\Dmod_{m,M})}\,.
\]
But it actually turns out, as indicated by Proposition~\ref{prop:Dmod-m} below,
that $C(\nup,m,M)$ is independent of $m$ and equals $C(\nup,-\infty,M)$.

\begin{proposition}
\label{prop:Dmod-m}
Fix $M \in \R$.
For all $m \leq M$, for all $\nu \in \Dmod_{m, M}$ and all $\mu > \Ed(\nu)$,
\[
\Kinf\big( \nu, \mu, \Dmod_{m, M} \big)
= \Kinf\big( \nu, \mu, \Dmod_{-\infty, M} \big)\,.
\]
\end{proposition}

\bp
The inequality $\geq$ is immediate, as the right-hand side of the equality is an infimum over the larger set $\Dmod_{-\infty, M}$.
For the inequality $\leq$, we may assume with no loss of generality that $\mu < M$, as otherwise,
there is no distribution $\nu'$ neither in $\Dmod_{m, M}$ nor in $\Dmod_{-\infty, M}$ with
$\Ed(\nu') > \mu \geq M$, so that both $\Kinf$ quantities equal $+\infty$.

We fix $M$, $m$, $\nu$ and $\mu$ as in the statement of the proposition.
It suffices to show that in the case $\mu < M$, for all $\nu' \in \mathcal \Dmod_{- \infty, M}$ with $\Ed(\nu')> \mu$
and $\nu \ll \nu'$, there exists $\nu'' \in \mathcal \Dmod_{m, M}$ with $\Ed(\nu'')> \mu$ and $\KL(\nu, \nu'') \leq \KL(\nu, \nu')$.
(If $\nu$ is not absolutely continuous with respect to $\nu'$, then $\KL(\nu, \nu') = +\infty$ and taking $\nu''$ as
the Dirac mass $\delta_M$ at $M$ is a suitable choice.)
To do so, given such a distribution $\nu'$, we first note that $\nu \ll \nu'$ and $\nu \in \Dmod_{m, M}$, i.e., $\nu([m,M]) = 1$,
entail that $\nu'([m,M]) > 0$, so that we may define the restriction $\nu'' = \nu'_{[m,M]}$ of $\nu'$ to $[m, M]$; its density
with respect to $\nu'$ is given by
\[
\frac{\dint \nu''}{\dint \nu'}(x)  = \nu'\bigl( [m,M] \bigr)^{-1} \,  \1{x \in [m,M]} \qquad \nu'\text{--a.s. for all $x \in \R$.}
\]
We have the absolute-continuity chain $\nu \ll \nu'' \ll \nu'$, and the Radon-Nykodym derivatives thus defined satisfy
\begin{equation}
\label{eq:chainruledensity}
\frac{\dint \nu}{\dint \nu'}(x) = \frac{\dint \nu}{\dint \nu''}(x) \frac{\dint \nu''}{\dint \nu'}(x) =
\nu'\bigl( [m,M] \bigr)^{-1} \, \frac{\dint \nu}{\dint \nu''}(x) \,  \1{x \in [m,M]} \qquad \nu'\text{--a.s. for all $x \in \R$.}
\end{equation}
Moreover $\Ed(\nu'') \geq \Ed(\nu')$, and thus $\Ed(\nu'') > \mu$, as
\begin{align*}
\Ed(\nu') & = \int_{(-\infty,m)} x \dint \nu'(x) + \int_{[m,M]} x \dint \nu'(x) \\
& \leq \Big( 1 - \nu'\big( [m,M] \bigr) \Big) m + \nu'\big( [m,M] \bigr) \, \Ed(\nu'')
\leq \Ed(\nu'')\,.
\end{align*}
Finally, by~\eqref{eq:chainruledensity}, which also holds $\nu$--almost surely,
and the definition of Kullback-Leibler divergences,
\begin{align*}
\KL(\nu, \nu')
= \int_{(-\infty,M]} \ln \! \left( \frac{\dint \nu}{\dint \nu'} \right) \! \dint \nu
& = - \ln \nu'\bigl( [m,M] \bigr) + \int_{[m,M]} \ln \! \left( \frac{\dint \nu}{\dint \nu''} \right) \! \dint \nu \\
& = - \ln \nu'\bigl( [m,M] \bigr) + \KL(\nu, \nu'') \geq \KL(\nu, \nu'')\,.
\end{align*}
This concludes the proof.
\end{proof}

\subsection{Known~$M$ but Unknown~$m$, Part~2: Distribution-Free Bounds}
\label{sec:TsallisKTpossible}

A first observation is that (as in the case of a fully known payoff range)
AdaHedge does not require any extra-exploration (i.e., any mixing with the uniform
distribution) to achieve a scale-free distribution-free regret bound of order
$\smash{(M-m)\sqrt{KT \ln K}}$. This is formally detailed in Appendix~\ref{app:proofs_exp3}.

Both this result and the one described next rely on the AdaFTRL methodology of~\citet{orabona2018scale},
which we recall in Appendix~\ref{sec:AdaFTRL-full}. AdaFTRL stands for adaptive follow-the-regularized-leader
and it was partially built on and inspired the analysis for AdaHedge, which is a special case of AdaFTRL with entropic
regularizer (see \citealp{de2014follow} for AdaHedge, as well as the earlier analysis by \citealp{cesa2007improved}).
\citet{koolen_2016} actually proposes an alternative analysis of AdaFTRL, closer to the AdaHedge formulation,
namely, using directly some mixability gaps instead of upper bounds thereon; this is the analysis we recall
in Section~\ref{sec:AdaFTRL-full}.

The INF strategy of \citet{audibert2009Minimax} can be seen as an instance of FTRL
with $1/2$--Tsallis entropy, as essentially noted by~\citet{audibert2014regret}.
The INF strategy provides a distribution-free regret bound of order $\sqrt{KT}$
in case of a known payoff range. Up to some technical issues, which we could solve,
it may be extended to provide a similar scale-free distribution regret bound, which is optimal
as it does not contain any superfluous $\sqrt{\ln K}$ factor.
The exact statement to be proved in Appendix~\ref{app:proofs_tsallis}
is the following: AdaFTRL with $1/2$--Tsallis entropy relying on an upper bound $M$ on the payoffs
ensures that for all $m \in \R$ with $m \leq M$,
for all oblivious individual sequences $y_1,y_2,\ldots$ in $[m,M]^K$,
for all $T \geq 1$,
\[
R_T(y_{1:T}) \leq 4 (M-m)\sqrt{KT} + 2(M-m)\,.
\]
We now give a high-level idea of the technical issues that were solved to obtain the bound above.
We consider estimates $\what{y}_{t, a}$ obtained from~\eqref{eq:estscheme} by replacing the constant $C$ therein by the
known upper end~$M$. We however could not simply derive the regret bound from
some generic full-information regret guarantee for AdaFTRL with $1/2$--Tsallis entropy, as
to the best of our knowledge, there are no meaningful full-information regret bounds for Tsallis entropy
in the first place, and as these would anyway scale with the effective range of the estimates.
We instead provide a more careful analysis exploiting special properties of the estimates:
$\what{y}_{t, a} = M$ for all $a \ne A_t$ and $\what{y}_{t, A_t} \leq M$.

We however were unable so far to provide a non-trivial distribution-dependent regret
bound for our strategy AdaFTRL with $1/2$--Tsallis entropy. Note that there exist
$\mathcal{O}(\ln T)$ bounds for FTRL with $1/2$--Tsallis entropy, i.e.,
with a different tuning of the learning rates (namely, $\eta_t$ of order $1/\sqrt t$, but then, the scale-free distribution-free
guarantees are lost); see \citet{zimmert2018optimal}.
We would have liked to prove such a $\mathcal{O}(\ln T)$ scale-free distribution-dependent regret
bound for AdaFTRL with $1/2$--Tsallis entropy (or even achieve a more modest aim like a poly-logarithmic bound),
as this seems possible and would have shown with certainty that the trade-off imposed
by~Theorem~\ref{thm:adaptive_lower_bound} does not hold anymore when the upper end~$M$ on the payoff range
is known.
The techniques of \citet{seldin2017improved}, which consist in a precise tuning of the extra-exploration in their
variant of the Exp3 algorithm of~\citet{AuCBFrSc02} together with a gap estimation scheme, or
the ones of \citet{zimmert2018optimal} might be helpful to that end. We leave this problem
for future research.

\subsubsection{AdaFTRL for Full Information (Reminder of Known Results)}
\label{sec:AdaFTRL-full}

To avoid confusion with the notation used in the main body of the paper,
we first describe the considered setting of prediction of oblivious individual sequences with full information.

\paragraph{Full-information setting.}
The game between the player and the environment is actually the same as the one described in Section~\ref{sec:setting-oblivious},
except that the player observes at each step the entire payoff vector, not just the obtained payoff.
More formally (and with a different piece of notation $z$ instead of $y$, to better distinguish the two settings),
the environment first picks a sequence of payoff vectors $z_t \in \R^K$, for all $t \geq 1$.
Then, in a sequential manner, at every time step $t$, the player picks an action $A_t$,
distributed according to a probability $p_t$ over the action set $[K]$,
obtains the payoff $z_{t, A_t}$, and observes the entire vector $z_t$ (i.e., also
the payoffs $z_{t,a}$ corresponding to the actions $a \neq A_t$).

In the sequel, we denote by $\cS$ the simplex of probability distributions over $[K]$
and we use the short-hand notation, for $p \in \cS$ and $z \in \R^K$,
\[
\dotp{p}{z} = \sum_{a \in [K]} p_a z_a\,.
\]

\paragraph{FTRL (follow-the-regularized-leader).}
The FTRL method consists in choosing $p_t$ according to
\[
p_t \in \argmin_{p \in \mathcal S : F(p) < +\infty} \left\{\frac{F(p)}{\eta_t} - \sum_{s =1}^{t-1} \dotp{p}{z_s} \right\},
\]
where $F : \R^K \to \R \cup \{+ \infty\}$ is a convex function, called the regularizer,
and $\eta_t$ is a non-negative learning rate in $(0, + \infty]$, which may depend on past observations.
The condition $F(p) < +\infty$ will always be satisfied for some $p \in \cS$ by the considered regularizers (see below)
and is only meant to avoid the undefined $+\infty/+\infty$ in the case $\eta_t = +\infty$. For the sake of concision
we will however omit it in the sequel.

Let us give a succint account of the convex analysis results we use here,
following the exposition of \citet[Chapter 26]{lattimore_szepesvari_2020}. Using their terminology,
the domain $\dom L$ of a convex function $L : \R^K \to \R \cup \{+ \infty\}$
is the set $\{ x \in \R^K : L(x) < +\infty \}$ of those points where it takes finite values.
A convex function $L : \R^K \to \R \cup \{+ \infty\}$ is said to be Legendre if the interior of its domain $\interior( \dom L)$ is non-empty,
if $L$ is strictly convex and differentiable on $\interior( \dom L)$, and if its gradient $\nabla L$
blows up on the boundary of $\dom L$. The minimizers of
Legendre functions may be seen to satisfy the following properties.

\begin{proposition}[Special case of {\citealp[Proposition~26.14]{lattimore_szepesvari_2020}}]
\label{prop:opt_condition}
Let $L$ be a Legendre function and $A \subseteq \R^d$ be a convex set that intersects $\interior(\dom L)$.
Then $L$ possesses a unique minimizer $x^\star$ over $A$, which belongs to $\interior (\dom L )$,
therefore ensuring that $L$ is differentiable at $x^\star$. Furthermore,
\[
\forall x \in A \cap \dom L, \qquad \dotp{\nabla L(x^\star)}{x-x^\star} \geq 0\,.
\]
\end{proposition}
\smallskip

Finally, for $x, y \in \R^d$, if $F : \R^K \to \R \cup \{+ \infty\}$ is differentiable at $y$,
we define the Bregman divergence between $x$ and $y$ as
\begin{equation}
B_F(x, y) = F(x) - F(y) - \dotp{\nabla F(y)}{x- y}\,;
\end{equation}
when $F$ is convex, we have $B_F(x, y) \geq 0$ for all $x \in \R^d$.

We are now ready to state our first reminder, which is a classical
regret bound for FTRL (see, e.g., \citealp[Chapter~28, Exercise 28.12]{lattimore_szepesvari_2020}
for references, and \citealp{mcmahan2017survey} for more general versions). It involves
the diameter $D_F$ of the action set (the $K$--dimensional simplex $\cS$ in our case):
\[
D_F = \max_{p, q \in \mathcal S} \big\{ F(p) - F(q) \big\}\,.
\]

\begin{reminder}[Generic full-information FTRL bound over the simplex]
\label{rem:ftrl}
The FTRL method with a Legendre regularizer $F$ (of finite diameter $D_F$) and
with any rule for picking the learning rates so that they form a non-increasing sequence
satisfies the following guarantee:
for all sequences $z_1,\,z_2,\ldots$ of vector payoffs in $\R^K$,
the regret is bounded by
\begin{align}
\nonumber
\max_{a \in [K]} \sum_{t = 1}^T z_{t, a} - \sum_{t = 1}^T \dotp{p_t}{z_t}
\leq \frac{D_F}{\eta_T}
& + \sum_{t = 1}^{T-1} \left(\dotp{p_t - p_{t+1}}{ - z_t}  - \frac{B_{F}(p_{t+1}, p_t)}{\eta_t}\right) \\
\label{eq:ftrl_generic_bound}
& + \left(\dotp{p_T - p^\star}{ - z_T}  - \frac{B_{F}(p^\star, p_T)}{\eta_T}\right), \\
\nonumber
\mbox{where} \qquad p^\star \in \argmax_{p \in \mathcal S} \sum_{t=1}^T \dotp{p}{z_t} &
\end{align}
and where the regret bound is well defined, thanks to the following observations and conventions:
for rounds $t \geq 1$ where $\eta_t < +\infty$, the function $F$ is indeed differentiable at $p_t$
so that $B_{F}(p_{t+1}, p_t)$ is well defined;
for rounds $t \geq 1$ where $\eta_t = +\infty$, we set $B_{F}(p_{t+1}, p_t)/\eta_t = 0$
irrespectively of the fact whether $F$ is differentiable at $p_t$.
\end{reminder}

\bpc{Proof of Reminder~\ref{rem:ftrl}}
Denote by $S_t$ the cumulative vector payoff up to time $t \geq 1$.
Fix $T \geq 1$.
For the sake of concision of the equations, we define $p_{T+1} = p^\star$,
which is a Dirac mass at some arm (that is, $p_{T+1}$ is not given by FTRL).
The regret can therefore be rewritten as
\begin{align*}
\max_{a \in [K]} \sum_{t = 1}^T z_{t, a} - \sum_{t = 1}^T \dotp{p_t}{z_t}
& = \max_{p \in \mathcal S} \sum_{t = 1}^T \dotp{p}{z_{t}}
- \sum_{t = 1}^T \dotp{p_t}{z_t} \\
& = \sum_{t = 1}^T \dotp{p_{T+1}}{z_{t}}
- \sum_{t = 1}^T \dotp{p_t}{z_t}
= \sum_{t = 1}^T \dotp{p_t - p_{T+1}}{-z_t}\,.
\end{align*}
By summation by parts,
\begin{align}
\nonumber
\MoveEqLeft \sum_{t = 1}^T \dotp{p_t - p_{T+1}}{-z_t} \\
\nonumber
& = \sum_{t = 1}^T \sum_{s = t}^T \dotp{p_s - p_{s+1}}{-z_t}
= \sum_{s = 1}^T \sum_{t= 1}^s \dotp{p_s - p_{s+1}}{-z_t}
= \sum_{s = 1}^T \dotp{p_s - p_{s+1}}{-S_s} \\
\label{eq:decregFTRL}
& = \sum_{t = 1}^T \dotp{p_t - p_{t+1}}{-z_t} + \sum_{t = 1}^T \dotp{p_t - p_{t+1}}{-S_{t-1}}\,.
\end{align}
If $\eta_t < + \infty$, then by the optimality condition from Proposition~\ref{prop:opt_condition} applied
to the Legendre function $L : x \mapsto \eta_t^{-1} F(x) - \dotp{S_{t-1}}{x} $, we know that $L$ thus $F$ are differentiable at $p_t$ and that
\begin{align*}
& \dotp{\eta_t^{-1}\nabla F(p_t) - S_{t-1}}{p_{t+1}-p_t} \geq 0\,, \\
\mbox{that is,} \qquad
& \dotp{p_t -p_{t+1}}{- S_{t-1}} \leq \dotp{\eta_t^{-1}\nabla F(p_t)}{p_{t+1} - p_t} \, .
\end{align*}
If $\eta_t = + \infty$, the previous inequality holds too,
as by definition of $p_t$, we have $\dotp{p_t - p_{t+1}}{-S_{t-1}} \leq 0$
and as we set by convention $\eta_t^{-1} \nabla F(p_t) = 0$ regardless of whether $F$ is differentiable at $p_t$ or not.
Substituting in~\eqref{eq:decregFTRL}, we proved so far
\begin{equation}
\sum_{t = 1}^T \dotp{p_t - p_{T+1}}{-z_t}
\leq \sum_{t = 1}^T \dotp{p_t - p_{t+1}}{-z_t}
+ \dotp{\eta_t^{-1}\nabla F(p_t)}{p_{t+1} - p_t}\,.
\end{equation}
This inequality can be rewritten in terms of Bregman divergences:
\[
\sum_{t = 1}^T \dotp{p_t - p^\star}{-z_t}
\leq \sum_{t = 1}^T \left( \dotp{p_t - p_{t+1}}{-z_t} - \frac{B_{F}(p_{t+1}, p_t)}{\eta_t} \right)
+ \sum_{t = 1}^T\frac{F(p_{t+1}) - F(p_{t})}{\eta_{t}}
\]
We now upper bound the second sum in the right-hand side:
again by summation by parts, with the convention $\eta_0 = +\infty$ and $1/\eta_0 = 0$:
\begin{align*}
& \sum_{t = 1}^T\frac{F(p_{t+1}) - F(p_{t})}{\eta_{t}}  = \sum_{t = 1}^T\big(F(p_{t+1}) - F(p_{t})\big) \sum_{s = 1}^{t} \left( \frac{1}{\eta_{s}}  - \frac{1}{\eta_{s-1}} \right) \\
= & \sum_{s=1}^{T} \sum_{t = s}^T \big(F(p_{t+1}) - F(p_{t})\big) \left( \frac{1}{\eta_{s}}  - \frac{1}{\eta_{s-1}} \right) = \sum_{s=1}^T
\big(\underbrace{F(p_{T+1}) - F(p_s)}_{\leq D_F} \big)
\biggl( \underbrace{\frac{1}{\eta_{s}}  - \frac{1}{\eta_{s-1}}}_{\geq 0} \biggr)
\leq \frac{D_F}{\eta_T}\,,
\end{align*}
where the final equality is obtained by a telescoping sum,
using that the sequence of learning rates is non-increasing.
\end{proof}

\paragraph{AdaFTRL, an adaptive version of FTRL.}
The AdaFTRL approach consists in tuning the learning rate in a way that scales with the observed data.
More precisely, it relies on a quantity called the (generalized) mixability gap, which naturally appears
as an upper bound on the summands in the FTRL bound of Reminder~\ref{rem:ftrl}:
\begin{equation}
\label{eq:def_gen_mix_gap}
\delta^{F}_t \eqdef \max_{p \in \mathcal S} \left\{ \dotp{p_t - p}{ - z_t } - \frac{B_F(p, p_t)}{\eta_t} \right\} \geq 0\,.
\end{equation}
That mixability gaps are always nonnegative can be seen by taking
$p = p_t$ in the definition.
We may further upper bound \eqref{eq:ftrl_generic_bound} when it holds by using this mixability gap:
\begin{equation}
\label{eq:ada_ftrl_intermediate}
\max_{a \in [K]} \sum_{t = 1}^T z_{t, a} - \sum_{t = 1}^T \dotp{p_t}{z_t} \leq \frac{D_F}{\eta_T} + \sum_{t = 1}^T \delta_T^F\,.
\end{equation}
The AdaFTRL learning rate balances the two terms in the above regret bound by taking
\begin{equation}
\label{eq:adaftrl-rates}
\eta_t = D_F \Bigg/  \, \sum_{s = 1}^{t-1} \delta_s^F  \quad \in (0,  + \infty]
\end{equation}
Note that this rule for picking learning rates indeed leads to non-increasing sequences thereof, as the mixability gaps are non-negative.
We summarize the discussion above in the theorem stated next,
from which subsequent (closed-from) regret bounds will be derived by
using the specific properties of the regularizer $F$ at hand to upper bound the mixability gaps.

\begin{theorem}[AdaFTRL tool box]\label{thm:adaftrl_toolbox}
Under the assumptions of Reminder~\ref{rem:ftrl} and with its conventions,
the regret of the FTRL method based on the learning rates~\eqref{eq:adaftrl-rates}
satisfies
\begin{equation}\label{eq:gen_ftrl_mixsum}
\max_{a \in [K]} \sum_{t = 1}^T z_{t, a} - \sum_{t = 1}^T \dotp{p_t}{z_t}
\leq 2 \sum_{t = 1}^T \delta_t^F
\end{equation}
where, moreover,
\begin{equation}\label{eq:gen_sq_mix_gaps}
\left( \sum_{t = 1}^T \delta_t^F \right)^{\!\! 2}
= 2 D_F \sum_{t = 1}^T \frac{\delta_t^F}{\eta_t} +   \sum_{t = 1}^T \bigl( \delta_t^F \bigr)^2\,.
\end{equation}
\end{theorem}

\bp
Inequality~\eqref{eq:gen_ftrl_mixsum} follows
from~\eqref{eq:ada_ftrl_intermediate} and~\eqref{eq:adaftrl-rates}.
The equality~\eqref{eq:gen_sq_mix_gaps} is obtained by expanding the squared sum,
\[
\left( \sum_{t = 1}^T \delta_t^F \right)^{\!\! 2} = \sum_{t = 1}^T \bigl( \delta_t^F \bigr)^2
+ 2 \sum_{t = 1}^T \sum_{s = 1}^{t-1} \delta_t^F \delta_s^{F} = \sum_{t = 1}^T (\delta_t^F)^2 + 2 \sum_{t =1}^T \delta_t^F \frac{D_F}{\eta_t}
\]
where the final equality is obtained by substituting the definition~\eqref{eq:adaftrl-rates} of $\eta_t$.
\end{proof}

\subsubsection{AdaHedge for Full Information (Reminder of Known Results)}
\label{app:ada_hedge_proof}

The content of this section is extracted from various sources, out of which the most important is~\citet{koolen_2016}.
We claim no novelty. This section recalls how the bound for AdaHedge (Reminder~\ref{rem:adahedge},
for which a direct proof was provided by~\citet{de2014follow}) can also be seen as a special case of the results of
Section~\ref{sec:AdaFTRL-full}.

It is well-known (see \citealp{FSSW97,KW99,Aud09}),
and can be found again by a simple optimization under a linear constraint,
that the Hedge weight update corresponds to FTRL with the negentropy as a regularizer:
\[
H_{\negent}(p) = \sum_{a = 1}^K p_a \log p_a\,,
\]
with value $+\infty$ whenever $p_a = 0$ for some $a \in [K]$. That is,
\begin{multline}
\label{eq:defadahedgefullinfo}
\argmin_{p \in \mathcal S} \left\{\frac{H_{\negent}(p)}{\eta_t} - \sum_{s =1}^{t-1} \dotp{p}{z_s} \right\} = \{ p_t \} \\
\mbox{with} \qquad
p_{t,a} = \exp \! \left( \eta_{t} \sum_{s = 1}^{t-1} z_{a,s} \right)
\Bigg/ \sum_{k=1}^K \exp \! \left( \eta_{t} \sum_{s = 1}^{t-1} z_{k,s} \right).
\end{multline}
Straightforward calculation show that the regularizer $H_{\negent}$ is indeed Legendre
(see~\citealp{lattimore_szepesvari_2020}, Example 26.11)
and the $H_{\negent}$--diameter of the simplex equals $D_{H_{\negent}} = \log K$. Reminder~\ref{rem:ftrl}
and Theorem~\ref{thm:adaftrl_toolbox} can therefore be applied.

AdaHedge is exactly AdaFTRL with $H_{\negent}$ as a regularizer. Indeed,
the mixability gap~\eqref{eq:def_gen_mix_gap} can be computed in closed form (as noted
by~\citealp[Lemma 5]{reid15generalized}) and reads in this case:
\begin{equation}
\label{eq:def_delta_t}
\delta^{\negent}_t =\left\{
\begin{split}
& - \dotp{p_t}{z_t} + \eta_t^{-1} \log \!\left( \sum_{  a =1}^K p_{t, a} \e^{\eta_t z_{t,a}} \right) \quad & \text{if } \eta_t < + \infty,  \\
& - \dotp{p_t}{z_t} +  \max_{a \in [K]} z_{t,a} \quad & \text{if } \eta_t = + \infty.
\end{split}\right.
\end{equation}

\bpc{Proof of the rewriting~\eqref{eq:def_delta_t}}
When $\eta_t = +\infty$, the mixability gap equals, by definition,
\[
\delta^{F}_t = \max_{p \in \mathcal S} \bigl\{ \dotp{p_t - p}{ - z_t } \bigr\}
= - \dotp{p_t}{z_t} +  \max_{p \in \mathcal S} \dotp{p}{z_t }
= - \dotp{p_t}{z_t} +  \max_{a \in [K]} z_{t,a}\,.
\]
For the case $\eta_t < +\infty$,
the following formula, which is at the heart of the closed-form formula for the Hedge updates~\eqref{eq:defadahedgefullinfo},
will be useful: for any $S \in \R^d$,
\begin{equation}\label{eq:negent_dual}
\min_{p \in \mathcal S} \Big\{  H_{\negent}(p)  -\dotp{p}{S}  \Big\}
= \sum_{i = 1}^K \frac{\e^{S_i}}{\sum_{j = 1}^K \e^{S_j}} \left(\ln \Bigg( \frac{\e^{S_i}}{\sum_{j = 1}^K \e^{S_j}  } \Bigg) - S_i \right)
= - \ln \Bigg( \sum_{i = 1}^K \e^{S_i} \Bigg)\,.
\end{equation}
When $\eta_t < +\infty$, Equation~\eqref{eq:defadahedgefullinfo} shows that $p_t$
lies in the interior $\interior(\cS)$ of $\cS$.
The Bregman divergence at hand in the definition~\eqref{eq:def_gen_mix_gap} of the mixability gaps
may be simplified into
\[
B_F(p, p_t)
= H_{\negent}(p) - H_{\negent}(p_t) - \dotp{\nabla H_{\negent}(p_t)}{p - p_t}
= H_{\negent}(p) - \dotp{\nabla H_{\negent}(p_t)}{p} + 1\,,
\]
where the second inequality holds by
taking into account the fact that $H_{\negent}$ is twice differentiable at any $p \in \interior(\cS)$, with
\[
\nabla H_{\negent}(p) = \big(1 + \ln p_i\big)_{i \in [K]}
\qquad \mbox{so that} \qquad
\dotp{\nabla H_{\negent}(p)}{p} = 1+ \sum_{i = 1}^K p_i \log p_i = 1 + H_{\negent}(p)\,.
\]
The mixability gaps can therefore be rewritten
\begin{align*}
\delta^{F}_t & = \max_{p \in \mathcal S} \left\{ \dotp{p_t - p}{ - z_t } - \frac{B_F(p, p_t)}{\eta_t} \right\} \\
& = - \dotp{p_t}{z_t} - \frac{1}{\eta_t} + \frac{1}{\eta_t} \max_{p \in \mathcal S} \bigl\{ \eta_t \dotp{p}{z_t} -
H_{\negent}(p) + \dotp{\nabla H_{\negent}(p_t)}{p} \bigr\} \\
& = - \dotp{p_t}{z_t} - \frac{1}{\eta_t} - \frac{1}{\eta_t} \min_{p \in \mathcal S} \Bigl\{ H_{\negent}(p) -
\dotpb{p}{\eta_t z_t + \nabla H_{\negent}(p_t)} \Bigr\}
\end{align*}
Now by \eqref{eq:negent_dual}, specialized with $S = \eta_t z_t + \nabla H_{\negent}(p_t)$,
we can compute the value of the minimum:
\[
\min_{p \in \mathcal S} \Bigl\{ H_{\negent}(p) -
\dotpb{p}{\eta_t z_t + \nabla H_{\negent}(p_t)} \Bigr\}
= - \ln \left( \sum_{ i =1}^K \e^{\eta_t z_i + 1 + \ln p_{i}} \right)
= -1 - \ln \left( \sum_{ i =1}^K p_{i} \e^{\eta_t z_i} \right).
\]
Collecting all equalities together concludes the proof.
\end{proof}

Reminder~\ref{rem:adahedge} is thus a special case of the following bound.

\begin{theorem}[See Lemma~3 and Theorem~6 of~\citealp{de2014follow}]
\label{thm:adahedge}
For all sequences of payoffs $z_{t,a}$ lying in some bounded real-valued interval,
denoted by $[b,B]$, for all $T \geq 1$, the regret of the AdaHedge algorithm with full information,
as defined by~\eqref{eq:defadahedgefullinfo} and~\eqref{eq:def_delta_t}, satisfies
\begin{multline*}
\max_{k \in [K]} \sum_{t=1}^T z_{t,k} -
\sum_{t=1}^T \sum_{a=1}^K p_{t,a} \, z_{t,a} \leq 2 \sum_{t=1}^T \delta^{\negent}_t \\
\mbox{where} \qquad \sum_{t=1}^T \delta^{\negent}_t
\leq \sqrt{\sum_{t=1}^T \sum_{a=1}^K p_{t,a} \! \left( z_{t,a} - \sum_{k \in [K]} q_{t,k} \, z_{t,k} \right)^{\!\! 2} \ln K}
+ (B-b) \left( 1 + \frac{2}{3}\ln K \right),
\end{multline*}
and AdaHedge does not require the knowledge of $[b,B]$ to achieve this bound.
\end{theorem}

The quantities
\[
v_t \eqdef \sum_{a=1}^K p_{t,a} \! \left( z_{t,a} - \sum_{k \in [K]} q_{t,k} \, z_{t,k} \right)^{\!\! 2}
\]
in the bound correspond to the variance of the random variables taking values $z_{t,a}$ with probability $p_{t,a}$;
the variational formula for variances indicates that
\[
\sum_{a=1}^K p_{t,a} \! \left( z_{t,a} - \sum_{k \in [K]} q_{t,k} \, z_{t,k} \right)^{\!\! 2}
= \min_{c \in \R} \sum_{a=1}^K p_{t,a} \bigl( z_{t,a} - c \bigr)^2\,,
\]
which entails the final bound given as a note in the statement of Reminder~\ref{rem:adahedge}.

The following formulation of Bernstein's inequality will be useful in the proof of Theorem~\ref{thm:adahedge}.

\begin{lemma}[Bernstein's inequality tailored to our needs]
\label{lm:Bern-Hedi}
Let $X$ be a random variable in $[0, 1]$, with variance denoting by $\Var(X)$.
Then for all $\eta > 0$,
\[
\frac{\log \Bigl( \E \bigl[ \e^{\eta (X - \E[X]) } \bigr] \Bigr)}{\eta^2}
\leq \frac{1}{2} \Var(X) +
\frac{1}{3} \, \frac{\log \Bigl( \E \bigl[ \e^{\eta (X - \E[X]) } \bigr] \Bigr)}{\eta}\,.
\]
\end{lemma}

\bp
Denote by $ \psi_X(\eta) = \log \bigl( \E \bigl[ \e^{\eta (X - \E[X]) } \bigr]$ the log-moment generating function of $X$.
A version of Bernstein's inequality with an appropriate control of the moments
(as stated by \citealp[Section~2.2.3]{Mas03} and applied to $X$ with $c = 1/3$) indicates that for all $\eta \in (0, 3)$,
\[
\Big( 1 - \frac{\eta}{3} \Big) \psi_X(\eta) \leq \frac{\eta^2}{2} \Var(X)\,.
\]
Actually, this inequality also holds for $\eta \geq 3$ as its left-hand side is non-positive while its right-hand side is nonnegative.
The claimed result is derived by rearraging the terms
\[
\psi_X(\eta) \leq \frac{\eta^2}{2} \Var(X) + \frac{\eta}{3} \psi_X(\eta)
\]
and by dividing both sides by $\eta^2$.
\end{proof}

\bpc{Proof of Theorem~\ref{thm:adahedge}}
We apply Theorem~\ref{thm:adaftrl_toolbox}.
To that end, we first bound the mixability gaps. The rewriting~\eqref{eq:def_delta_t}
(and Jensen's inequality) directly shows that $0 \leq \delta_t^{\negent} \leq B-b$.
We may also prove the bound
\begin{equation}
\label{eq:BernGap}
\frac{\delta_t^{\negent}}{\eta_t} \leq  \frac{v_t}{2} + \frac{1}{3}(B-b)\delta_t^{\negent}\,.
\end{equation}
It suffices to do so for $\eta_t < +\infty$.
Consider the random variable $X$ taking values
$(z_{t,a} - b)/(B-b)$ with probability $p_{t,a}$, for $a \in \{1,\ldots,K\}$.
The mixability gap can be rewritten as
\[
\delta_t^{\negent} = \frac{1}{\eta_t} \psi_X\bigl( \eta_t(B-b)\bigr)
\]
with the notation of the proof of Lemma~\ref{lm:Bern-Hedi}.
The variance of $X$ equals $v_t/(B-b)^2$.
Lemma~\ref{lm:Bern-Hedi} with $\eta = \eta_t(B-b)$ yields
\[
\frac{\delta_t^{\negent}}{\eta_t (B-b)^2} \leq \frac{v_t}{2(B-b)^2} + \frac{\delta_t^{\negent}}{3(B-b)}\,.
\]
from which we obtain~\eqref{eq:BernGap} by rearranging.

From~\eqref{eq:gen_sq_mix_gaps} and~\eqref{eq:BernGap}, we deduce, together with
the bound $(\delta_t^{\negent})^2 \leq (B-b)\delta_t^{\negent}$, that
\[
\left(\sum_{t = 1}^T \delta_t^{\negent} \right)^{\!\! 2}
\leq (\log K) \sum_{t = 1}^T v_t + (B-b)\left( \frac{2}{3} \log K + 1  \right) \sum_{t = 1}^T \delta_t^{\negent}\,.
\]
Therefore, using the fact that $x^2 \leq a + bx$ implies $x \leq \sqrt{a} + b$ for all $a, b, x \geq 0$,
\[
\sum_{t = 1}^T \delta_t^{\negent} \leq \sqrt{\ln K \sum_{t = 1}^T v_t} + (B-b)\left( \frac{2}{3} \log K + 1  \right),
\]
which thanks to~\eqref{eq:gen_ftrl_mixsum} concludes the proof of Theorem~\ref{thm:adahedge}.
\end{proof}

\subsubsection{AdaHedge with Known Payoff Upper Bound $M$ (Application of Section~\ref{app:ada_hedge_proof})}
\label{app:proofs_exp3}

We show how to obtain a scale-free distribution-free regret bound of order $(M-m)\sqrt{K T \ln K}$
with no extra-exploration (including no initial exploration)
when an upper bound $M$ on the payoffs is given to the player.
We consider Algorithm~\ref{algo:adahedgeM}, where no mixing takes place (unlike
in Algorithm~\ref{algo:adahedge}) and where the probability distributions $p_t$
are directly computed via an AdaHedge update (no need for intermediate
probabilities $q_t$). Note also that we use the estimates~\eqref{eq:estscheme}
with the choice $C_t = M$, that is,
\begin{equation}
\label{eq:loss_estimates_known_M}
\what{y}_{t, a} = \frac{y_{t, a}-M}{p_{t, a}} \1{A_t = a} + M\,.
\end{equation}
The following observation is key in the analysis below:
$\what{y}_{t, a} = M$ for all $a \ne A_t$ and $\what{y}_{t, A_t} \leq M$.
We will also use, as in the proof of Theorem~\ref{th:adv_talpha_bound},
\[
\sum_{a=1}^K p_{t,a}\,\wh{y}_{t,a} = y_{t, A_t}\,.
\]

\begin{figure}[h]
\renewcommand\footnoterule{}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\caption{\label{algo:adahedgeM} AdaHedge for $K$--armed bandits, when an upper bound on the payoffs is given}
\label{alg:exp3_adahedgeM}
\STATE \textbf{Input:} an upper bound $M$ on the payoffs
\STATE \textbf{AdaHedge initialization:} $\eta_{1} = +\infty$ and $p_{1} = (1/K,\ldots,1/K)$
\FOR{rounds $t = 1,\,2,\, \dots$}
\STATE Draw an arm $A_t \sim p_t$ (independently at random according to the distribution $p_t$)
\STATE Get and observe the payoff $y_{t, A_t}$
\STATE Compute the estimates of all payoffs
\[
\what y_{t, a} = \frac{y_{t, a}-M}{p_{t, a}} \1{A_t = a} + M
\]
\STATE Compute the mixability gap $\delta_t$ based on the distribution $p_t$ and on these estimates:
\[
\delta_t =\left\{
\begin{split}
& - \sum_{a=1}^K p_{t,a}\,\wh{y}_{t,a} + \frac{1}{\eta_t} \log \Biggl( \sum_{a =1}^K p_{t, a} \e^{\eta_t \wh{y}_{t,a}} \Biggr)
\quad & \text{if } \eta_t < + \infty \\
& - \sum_{a=1}^K p_{t,a}\,\wh{y}_{t,a} + \max_{a \in [K]} \wh{y}_{t,a} \quad & \text{if } \eta_t = + \infty
\end{split}\right.
\]
\STATE Compute the learning rate $\displaystyle{\eta_{t+1} = \Biggl( \sum_{s = 1}^t \delta_s \Biggr)^{-1}} \ln K$
\STATE Define $p_{t+1}$ component-wise as \vspace{-.3cm}
\[
~ \hspace{2.5cm} p_{t+1,a} = \exp \! \left( \eta_{t+1} \sum_{s = 1}^{t} \wh{y}_{a,s} \right)
\Bigg/ \sum_{k=1}^K \exp \! \left( \eta_{t+1} \sum_{s = 1}^{t} \wh{y}_{k,s} \right) \vspace{-.3cm}
\]
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{figure}

The performance bound for this simpler algorithm is stated next.

\begin{theorem}
\label{thm:adv_any_exploration--simpler}
AdaHedge for $K$--armed bandits relying on an upper bound $M$
on the payoffs (Algorithm~\ref{algo:adahedgeM})
ensures that for all $m \in \R$ with $m \leq M$,
for all oblivious individual sequences $y_1,y_2,\ldots$ in $[m,M]^K$,
for all $T \geq 1$,
\[
R_T(y_{1:T}) \leq 2 (M-m)\sqrt{KT \log K} + 2(M-m)\,.
\]
\end{theorem}

The main technical difference with respect to the analysis of Algorithm~\ref{algo:adahedge}
is that the mixability gaps are directly bounded by the range $M-m$.
We no longer need to artificially control the size of the estimates (which we did via extra-exploration) to
get, in turn, a control of the mixability gaps.

\begin{lemma}[Improved mixability gap bound]
\label{lem:adahedge_up_bound_mix_gap}
The mixability gaps of AdaHedge for $K$--armed bandits relying on an upper bound $M$
on the payoffs (Algorithm~\ref{algo:adahedgeM})
are bounded, for all $m \in \R$ with $m \leq M$,
for all oblivious individual sequences $y_1,y_2,\ldots$ in $[m,M]^K$,
for all $t \geq 1$, by
\[
0 \leq \delta_t \leq  M-m  \qquad \mbox{and} \qquad \frac{\delta_t}{\eta_t} \leq \frac{1}{2} \,  p_{t, A_t}^{-1}(M - y_{t,A_t})^2  .
\]
\end{lemma}

\bp
The fact that $\delta_t  \geq 0$ holds by definition of the gaps and Jensen's inequality.
For $\delta_t \leq M-m$,
the observations after~\eqref{eq:loss_estimates_known_M} indicate that when $\eta_t = +\infty$,
\[
\delta_t = - \sum_{a=1}^K p_{t,a}\,\wh{y}_{t,a} + \max_{a \in [K]} \wh{y}_{t,a}
= M - \wh{y}_{t,A_t}\,,
\]
while for $\eta_t < +\infty$,
\begin{align*}
\delta_t & = - y_{t, A_t} + \frac{1}{\eta_t} \log \left( (1 - p_{t, A_t}) \e^{\eta_t M}
+ p_{t, A_t} \e^{\eta_t M} \e^{\eta_t (y_{t, A_t}-M) / p_{t, A_t}}\right) \\
& \leq M - y_{t, A_t} + \frac{1}{\eta_t} \log \Bigl( (1 - p_{t, A_t})
+ p_{t, A_t} \underbrace{\e^{\eta_t (y_{t, A_t}-M) / p_{t, A_t}}}_{\leq 1} \Bigr)\,,
\end{align*}
which entails $\delta_t \leq M - y_{t, A_t} \leq M-m$.

Furthermore, in the case $\eta_t < +\infty$,
using the inequality $\e^{-x} \leq  1 - x +  x^2/2$ valid for $x \geq 0$, followed by the inequality
$\log(1 + u) \leq u$, valid for all $u > -1$, we get
\[
\delta_t
\leq M - \what y_{t, A_t}  + \frac{1}{\eta_t} \log \! \biggl(
\underbrace{1 - p_{A_t, t,} + p_{A_t, t}}_{=1} \underbrace{- \eta_t (M -  y_{t, A_t} ) + \eta_t^2 \frac{ (M -  y_{t, A_t} )^2}{2 p_{A_t, t}}}_{= u} \biggr)
\leq \eta_t \frac{(M -  y_{t, A_t} )^2}{2 p_{t, A_t}}\,.
\]
The second inequality is trivial in case $\eta_t = +\infty$, as $\delta_t/\eta_t = 0$.
\end{proof}

We are now ready to prove Theorem~\ref{thm:adv_any_exploration--simpler}.

\bpc{Proof of Theorem~\ref{thm:adv_any_exploration--simpler}}
As indicated in Section~\ref{app:ada_hedge_proof}, AdaHedge is a special case of AdaFTRL
and the bound of Theorem~\ref{thm:adaftrl_toolbox} is applicable.

Equation~\eqref{eq:gen_sq_mix_gaps} and Lemma~\ref{lem:adahedge_up_bound_mix_gap},
which entails in particular that $\delta_t^2 \leq (M-m) \delta_t$,
yield
\[
\bigg(\sum_{t = 1}^T \delta_t \bigg)^{\!\! 2} = 2 (\ln K) \sum_{t = 1}^T \frac{\delta_t}{\eta_t}
+ \sum_{t = 1}^T (\delta_t)^2 \leq (\ln K)  \sum_{t = 1}^T p_{t, A_t}^{-1} (M- y_{t, A_t})^2+ (M-m) \sum_{t=1}^T \delta_t\,,
\]
which, through the fact that $x^2 \leq a + bx$ implies $x \leq \sqrt{a} + b$ for all $a, b, x \geq 0$,
leads in turn to
\[
\sum_{t = 1}^T \delta_t \leq \sqrt{\sum_{t=1}^T p_{t,A_t}^{-1} \! \left( M - \wh{y}_{t,A_t} \right)^{ 2} \ln K} + (M-m)\,.
\]
Therefore, Equation~\eqref{eq:gen_ftrl_mixsum} guarantees that
\begin{equation}\label{eq:almostfin}
\max_{k \in [K]} \sum_{t=1}^T \wh{y}_{t,k} -
\sum_{t=1}^T \underbrace{\sum_{a=1}^K p_{t,a} \, \wh{y}_{t,a}}_{= y_{t,A_t}}
\leq
2\sqrt{\sum_{t=1}^T p_{t,A_t}^{-1} \! \left( M - \wh{y}_{t,A_t} \right)^{ 2} \ln K}
+ 2(M-m)\,.
\end{equation}
We conclude the proof by integrating the inequality above
and using Jensen's inequality, exactly as in the proof of Theorem~\ref{th:adv_talpha_bound}.
Indeed, Equation~\eqref{eq:exp-regret-max} therein indicates that
\[
R_T(y_{1:T})
= \max_{k \in [K]} \sum_{t=1}^T y_{t,k} - \E \! \left[ \sum_{t=1}^T  y_{t,A_t}  \right]
\leq \E \! \left[ \max_{k \in [K]} \sum_{t=1}^T \wh{y}_{t,k} - \sum_{t=1}^T y_{t,A_t} \right]
\]
and, by the same manipulations as in~\eqref{eq:Jensen-mainproofUB} and in the equation
that follows it,
\begin{align*}
	\E \! \left[ \sqrt{\sum_{t=1}^T p_{t,A_t}^{-1} \! \left( M - \wh{y}_{t,A_t} \right)^{ 2} \ln K} \right]
	& \leq \sqrt{ \E \! \left[ \sum_{t=1}^T p_{t,A_t}^{-1} \! \left( M - y_{t,A_t} \right)^{ 2} \ln K \right]} \\
	& = \sqrt{ \E \! \left[ \sum_{t=1}^T \sum_{a=1}^K \! \left( M - y_{t,a} \right)^{ 2} \ln K \right]}
	\leq (M-m)\sqrt{KT \ln K}
\end{align*}
The claimed result is obtained by collecting all bounds together.
\end{proof}

\subsubsection{AdaFTRL with Tsallis Entropy in the Case of a Known Payoff Upper Bound $M$}
\label{app:proofs_tsallis}

In this section we describe how the AdaHedge learning rate scheme can be used in the
FTRL framework with a different regularizer, namely Tsallis entropy, to improve the scale-free distribution-free regret bound into a bound of optimal order $(M-m)\sqrt{KT}$, i.e.,
without any superfluous $\sqrt{\ln K}$ factor.

\paragraph{Tsallis entropy.}
We focus on the (rescaled) $1/2$--Tsallis entropy, which is defined by
\[
H_{1/2}(p) = -\sum_{a = 1}^K 2 \sqrt{p_a}\,.
\]
This regularizer is Legendre over the domain $[0, +\infty)^K$ (see \citealp[Example~26.10]{lattimore_szepesvari_2020}).
Its diameter equals
\begin{equation}
	D_{H_{1/2}} = \max_{p \in \mathcal S} H_{1/2}(p) -  \min_{q \in \mathcal S} H_{1/2}(q)  =  -2 - \bigl( -2 \sqrt K \bigr) = 2 \bigl( \sqrt K -1 \bigr)\,,
\end{equation}
as for all $p \in \mathcal S$, we have (by concavity of the square root for the right-most inequality)
\[
1 \leq \sum_{ a = 1}^K  p_a \leq \sum_{ a = 1}^K \sqrt{p_a} \leq \sqrt K\,,
\]
where $1$ is achieved with $p = (1, 0, \dots, 0)$ and $\sqrt{K}$ with the uniform distribution.

The function $H_{1/2}$ is differentiable at all $q \in (0, +\infty)^K$, with $\nabla H_{1/2}(q) = \big(- 1 / \sqrt{q_a} \big)_{a \in [K]}$ .
The Bregman divergence associated with $H_{1/2}$ equals, for $p, q \in \mathcal S$ such that $q_{a} > 0$ for all $a$:
\begin{multline*}
	B_{H_{1/2}}(p, q)
	= -2 \sum_{ a = 1}^K \sqrt{p_a} + 2 \sum_{ a = 1}^K \sqrt{q_a} + \sum_{ a = 1}^K \frac{1}{\sqrt{q_a}} (p_a - q_a)  \\
	= -2 \sum_{a = 1}^K \frac{ \sqrt{p_a} - \sqrt{q_a}}{2 \sqrt{q_a}}  \Big( 2 \sqrt q_a - (\sqrt{p_a} + \sqrt{q_a}) \Big)
	= \sum_{  a =1}^K \frac{(\sqrt{p_a} - \sqrt{q_a})^2}{\sqrt {q_a}}\,.
\end{multline*}

\paragraph{AdaFTRL with $1/2$--Tsallis entropy.}
We consider FTRL with the $1/2$--Tsallis entropy on the estimated losses~\eqref{eq:loss_estimates_known_M}:
\[
p_t \in
\argmin_{p \in \mathcal S} \left\{\frac{H_{1/2}(p)}{\eta_t} - \sum_{s =1}^{t-1} \dotp{p}{\what y_{s}} \right\}
= \argmin_{p \in \mathcal S}  \left\{ - \frac{1}{\eta_t} \sum_{a = 1}^K 2\sqrt{p_a}
- \sum_{a = 1}^K p_{a} \sum_{s =1}^{t-1} \what y_{s, a} \right\}.
\]

FTRL with the $1/2$--Tsallis entropy was essentially introduced by~\citet{audibert2009Minimax} to
get rid of a $\sqrt{\ln K }$ factor in the distribution-free regret bound of $K$--armed adversarial bandits
(with known payoff range). It was later noted by~\citet{audibert2014regret} that it actually is an instance of
mirror descent with Tsallis entropy as a regularizer.
More recently, \citet{zimmert2018optimal} showed that this regularizer can obtain quasi-optimal regret bounds
for both stochastic and adversarial rewards.

We more precisely consider AdaFTRL with the $1/2$--Tsallis,
that is, we compute the learning rates $\eta_t$ based on the mixability
gaps~\eqref{eq:def_gen_mix_gap}; see Algorithm~\ref{alg:tsallis_ftrl}.
We denote by $\delta_t^{\ts}$ the mixability gaps~\eqref{eq:def_gen_mix_gap}.

\paragraph{On the implementation.}
For Tsallis entropy, the optimization problems involved in the computation of the updates $p_t$ and
of the mixability gaps~$\delta_t^{\ts}$ admit a (semi-)explicit formula.
Indeed, $p_t$ can be computed thanks to the formula, for all $z \in \R^K$,
\begin{equation}\label{eq:opt_pb}
\argmin_{p \in \mathcal S} \bigl\{  H_{1/2}(p) - \dotp{p}{z} \bigr\}
= \argmax_{p \in \mathcal S} \left\{  \dotp{p}{z} + \sum_{a = 1}^K 2 \sqrt{p_a} \right\}
= \left(\frac{1}{\bigl( c(z) - z_a \bigr)^2}\right)_{a \in K}\,,
\end{equation}
where $c(z)$ is an implicit normalization constant, such that the vector lies in the simplex~$\cS$ and $c(z) > z_a$ for all $a \in [K]$.
This constant $c(z)$ is in fact the Lagrange multiplier associated with the constraint $ p_1 + \ldots + p_K = 1$.
See \citet{zimmert2018optimal} for more details on how to compute $c(z)$ efficiently, see also \citet{audibert2014regret}.
To compute the mixabity gap, rewrite
\begin{align}
\nonumber
\delta^{\ts}_t & =
\max_{p \in \mathcal S} \left\{ \dotp{p_t - p}{ - \what y_t } - \frac{H_{1/2}(p) - H_{1/2}(p_t) - \dotp{\nabla H_{1/2}(p_t)}{p - p_t}}{\eta_t} \right\} \\
\label{eq:computeBHgap}
& = \dotp{p_t}{- \what y_t} +  \frac{H_{1/2}(p_t) }{\eta_t}- \frac{\dotp{\nabla H_{1/2} (p_t)}{p_t}}{\eta_t}
+ \frac{1}{\eta_t} \max_{p \in \mathcal S} \Big\{ \dotp{p}{\nabla H_{1/2}(p_t) + \eta_t \what y_t} - H_{1/2}(p) \Big\}\,,
\end{align}
where the maximum in the left-most side of these equalities
can be computed efficiently, thanks to~\eqref{eq:opt_pb}.

\begin{figure}[t]
	\renewcommand\footnoterule{}
	\begin{algorithm}[H]
		\begin{algorithmic}[1]
			\caption{\label{algo:tsallis_ftrlM} AdaFTRL with Tsallis entropy for $K$--armed bandits, when an upper bound on the payoffs is given}
			\label{alg:tsallis_ftrl}
			\STATE \textbf{Input:} an upper bound $M$ on the payoffs
			\STATE \textbf{Initialization:} $\eta_{1} = +\infty$ and $p_{1} = (1/K,\ldots,1/K)$
			\FOR{rounds $t = 1,\,2,\, \dots$}
			\STATE Draw an arm $A_t \sim p_t$ (independently at random according to the distribution $p_t$)
			\STATE Get and observe the payoff $y_{t, A_t}$
			\STATE Compute the estimates of all payoffs
			\[
			\what y_{t, a} = \frac{y_{t, a}-M}{p_{t, a}} \1{A_t = a} + M
			\]
			\STATE Compute the mixability gap $\delta^{\ts}_t$ based on the distribution $p_t$ and on these estimates, e.g., using the
efficient implementation stated around~\eqref{eq:computeBHgap}:
			\[
				\delta^{\ts}_t = \max_{p \in \mathcal S} \left\{ \dotp{p_t - p}{ - \what y_t } - \frac{B_{H_{1/2}}(p, p_t)}{\eta_t} \right\}
			\]
			\STATE Compute the learning rate $\displaystyle{\eta_{t+1} = 2 \Biggl( \sum_{s = 1}^t \delta^{\ts}_s \Biggr)^{-1}} \bigl( \sqrt K -1 \bigr)$
			\STATE Define $p_{t+1}$ as
			\[
			p_{t+1} \in \argmin_{p \in \mathcal S}  \left\{ - \sum_{a = 1}^K p_{a} \sum_{s =1}^{t} \what y_{s, a}
- \frac{1}{\eta_{t+1}} \sum_{a = 1}^K 2\sqrt{p_a} \, \right\},
			\]
where an efficient implementation is provided by, e.g., \eqref{eq:opt_pb}
			\ENDFOR
		\end{algorithmic}
	\end{algorithm}
\end{figure}

\paragraph{Analysis of the algorithm.} We provide the following performance bound.

\begin{theorem}
\label{thm:tsallis}
AdaFTRL with $1/2$--Tsallis entropy for $K$--armed bandits relying on an upper bound $M$
on the payoffs (Algorithm~\ref{alg:tsallis_ftrl})
ensures that for all $m \in \R$ with $m \leq M$,
for all oblivious individual sequences $y_1,y_2,\ldots$ in $[m,M]^K$,
for all $T \geq 1$,
\[
R_T(y_{1:T}) \leq 4 (M-m)\sqrt{KT} + 2(M-m)\,.
\]
\end{theorem}

As in Section~\ref{app:proofs_exp3}, the proof scheme is a combination of the AdaFTRL bound
of Theorem~\ref{thm:adaftrl_toolbox} (which is indeed applicable), together with an improved bound on
the mixability gap that exploits the specific shape of the estimates. This bound is stated in the
next lemma, which is much similar to Lemma~\ref{lem:adahedge_up_bound_mix_gap}.

\begin{lemma}\label{eq:tsall_mix_gap_bound}
The mixability gaps of AdaFTRL with Tsallis entropy for $K$--armed bandits relying on an upper bound $M$
on the payoffs (Algorithm~\ref{alg:tsallis_ftrl})
are bounded, for all $m \in \R$ with $m \leq M$,
for all oblivious individual sequences $y_1,y_2,\ldots$ in $[m,M]^K$,
for all $t \geq 1$, by
\[
0 \leq \delta^{\ts}_t \leq M - m \qquad \mbox{and} \qquad \frac{\delta^{\ts}_t}{\eta_t} \leq  p_{t, A_t}^{-1/2} (M- y_{t, A_t})^2\,.
\]
\end{lemma}

The proof of Lemma~\ref{eq:tsall_mix_gap_bound} is postponed to the end of this section
and we now proceed with the proof of Theorem~\ref{thm:tsallis}.

\bpc{Proof of Theorem~\ref{thm:tsallis}}
The structure of the proof is much similar to the one of Theorem~\ref{thm:adv_any_exploration--simpler},
which is why we only sketch our arguments.
The bound of Theorem~\ref{thm:adaftrl_toolbox} is applicable.
We use Lemma~\ref{eq:tsall_mix_gap_bound} with~\eqref{eq:gen_sq_mix_gaps} to see that
\begin{equation}
\bigg(\sum_{t = 1}^T \delta_t^{\ts} \bigg)^2
\leq  2 D_{H_{1/2}} \sum_{t = 1}^T p_{t, A_t}^{-1/2} (M- y_{t, A_t})^2 + (M-m)\sum_{t = 1}^T \delta_t^{\ts}\,.
\end{equation}
Again, using the fact that for all $a, b, x \geq 0$, the inequality  $x^2 \leq a + bx$ implies $x \leq \sqrt a + b$ :
\begin{equation}\label{eq:mix_sum_tsal}
\sum_{t = 1}^T \delta_t^{\ts} \leq \sqrt{2D_{H_{1/2}} \sum_{t = 1}^T p_{t, A_t}^{-1/2} (M - y_{t, A_t})^2} + (M-m)
\end{equation}
By~\eqref{eq:gen_ftrl_mixsum}, by taking expectations, and by Jensen's inequality:
\begin{equation}
R_T(y_{1:T})
\leq 2 \E \big[ \sum_{t = 1}^T \delta_t^{\ts} \big]
\leq 2\sqrt{2D_{H_{1/2}} \sum_{t = 1}^T \E \Bigl[ p_{t, A_t}^{-1/2} (M- y_{t, A_t})^2 \Bigr]} + 2(M-m)\,.
\end{equation}
We conclude by observing that for all $t$, by definition of the payoff estimates,
\begin{align*}
\E \! \left[ p_{t, A_t}^{-1/2}  \big(M- y_{t, A_t}\big)^2\right]
= \E \! \left[ \sum_{a = 1}^K p_{t, a} \, p_{t, a}^{-1/2}  \big(M- y_{t, a}\big)^2\right]
& \leq (M-m)^2 \, \E \!\left[ \sum_{a =1}^K \sqrt{p_{a, t}} \right] \\
& \leq (M-m)^2 \sqrt{K}\,,
\end{align*}
where the last inequality follows from the concavity of the square root.
The final claim is obtained by bounding the diameter $D_{H_{1/2}}$ by $2 \sqrt K$.
\end{proof}

We conclude this section by providing a proof of Lemma~\ref{eq:tsall_mix_gap_bound}.

\bpc{Proof of Lemma~\ref{eq:tsall_mix_gap_bound}}
The fact that $\delta^{\ts}_t \geq 0$ holds actually for all regularizers
and can be seen from the definition \eqref{eq:def_gen_mix_gap} with $p = p_t$. For the inequality $\delta^{\ts}_t \leq M-m$,
we start with elementary manipulations of the definition of the mixability gap~\eqref{eq:def_gen_mix_gap}.
Denoting by $\vec M$ the vector with coordinates $(M, \dots, M)$
and noting that $\dotp{p_t-q}{\vec M} = 0$ for all $q \in \mathcal S$, we have
\begin{equation}
\label{eq:Lm3rewrdeltats}
\delta^{\ts}_t
= \max_{q \in \mathcal S} \left\{ \dotp{p_t - q}{- \what y_t } - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t} \right\}
=\max_{q \in \mathcal S} \left\{ \dotp{p_t - q}{\vec M- \what y_t } - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t} \right\}.
\end{equation}
Since all the coordinates of $\vec M - \what y_{t}$ are non-negative and by non-negativity of the Bregman divergence, this implies that
\[
\delta^{\ts}_t
\leq \dotp{p_t}{\vec M - \what y_t}
= M - y_{A_t, t} \leq M -m\,.
\]

We now prove the second inequality; we may assume that $\eta_t < + \infty$, as the bound holds trivially otherwise.
By Proposition~\ref{prop:opt_condition} (and by calculations similar to the ones performed in the proof of
Reminder~\ref{rem:ftrl}) the maximum in the rewriting~\eqref{eq:Lm3rewrdeltats}
of $\delta^{\ts}_t$ is achieved on the interior of the domain of $H_{1/2}$, which equals~$(0, + \infty)^K$,
thus in the interior of $\cS$. We therefore only need to prove that
\begin{equation}
\label{lm:AppA4Lemma3-needtoprove}
\forall q \in \interior(\cS), \qquad
\dotp{p_t - q}{\vec M- \what y_t } - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t} \leq
\eta_t \, p_{t, A_t}^{-1/2} (M- y_{t, A_t})^2\,.
\end{equation}
We fix such a $q \in \interior(\cS)$, i.e., such that $q_a > 0$ for all $a$. We consider two cases.
First, if $q_{A_t} \geq p_{t, A_t}$, then, given the observations made after~\eqref{eq:loss_estimates_known_M},
\[
\dotp{p_t - q}{ \vec M- \what y_t }  - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t}
= \underbrace{\left(  \frac{M - y_{t, A_t}}{p_{t, A_t}}\right)}_{\geq 0} \underbrace{\big( p_{t, A_t} - q_{A_t}  \big)}_{\leq 0}
- \frac{B_{H_{1/2}}(q, p_t)}{\eta_t} \leq 0\,.
\]

Otherwise, when $q_{A_t} < p_{t, A_t}$, a standard way of bounding the mixability gap, detailed below,
indicates that
\begin{equation}
\label{eq:lm3--stdbdmixgap}
\dotp{p_t - q}{ M- \what y_t } - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t}
\leq \frac{\eta_t}{2}  \dotpB{\vec M- \what y_t}{ \nabla^2 H_{1/2}(z)^{-1} \, \bigl( \vec M- \what y_t \bigr)}\,,
\end{equation}
where $z$ is some probability distribution of the open segment $\segm(q, p_t)$ between $q$ and $p_t$, and
where $\nabla^2 H_{1/2}(z)^{-1}$ denotes the inverse of the positive definite Hessian of
$H_{1/2}$ at $z$. Since at $w \in (0, + \infty)^K$, the function $H_{1/2}$ is indeed twice differentiable, with
\[
\nabla H_{1/2}(w) = \bigl( -w_a^{-1/2} \bigr)_{a \in[K]}
\qquad {\mbox{and}} \qquad
\nabla^2 H_{1/2}(w) = \mathrm {Diag}\big( w_a^{-3/2} /2\big)_{a \in [K]}\,,
\]
we have $\nabla^2 H_{1/2}(z)^{-1} = \mathrm {Diag}\big( 2 z_a^{3/2} \big)_{a \in [K]}$.
We substitute this value into~\eqref{eq:lm3--stdbdmixgap}
and recall that the vector $\vec M - \what y_t$ has null coordinates except for its $A_t$--th coordinate:
\[
\frac{\eta_t}{2}  \dotpB{\vec M- \what y_t}{ \nabla^2 H_{1/2}(z)^{-1} \, \bigl( \vec M- \what y_t \bigr)}
= \eta_t \,  z_{A_t}^{3/2} \bigl( M- \what y_{t, A_t} \bigr)^2\,.
\]
Finally, remember that $z$ lies in the open segment $\segm(q, p_t)$
and that we assumed  $q_{A_t} < p_{t, A_t}$; we thus also have $z_{A_t} < p_{t, A_t}$.
As a consequence, using the very definition of $\what y_{t, A_t}$,
\[
\eta_t \,  z_{A_t}^{3/2} \bigl( M- \what y_{t, A_t} \bigr)^2
\leq
\eta_t\,  p_{t, A_t}^{3/2} \bigl( M- \what y_{t, A_t} \bigr)^2
= \eta_t\,  p_{t, A_t}^{-1/2}(M- y_{t, A_t})^2\,.
\]
Therefore, in all cases, that is, whether $q_{A_t} \geq p_{t, A_t}$ or $q_{A_t} < p_{t, A_t}$,
the bound~\eqref{lm:AppA4Lemma3-needtoprove} is obtained. It only remains to prove
the standard inequality~\eqref{eq:lm3--stdbdmixgap}.

This inequality is essentially stated as Therorem~26.13 in \citet{lattimore_szepesvari_2020} but we provide a proof
for the sake of completeness.
As we assumed that $\eta_t < + \infty$, we have (as above, by Proposition~\ref{prop:opt_condition})
that $p_t$ lies in the interior of $\cS$. In particular, as both $p_t$ and $q$ are in the interior of $\cS$,
the function $H_{1/2}$ is $\mathcal C^2$ over the closed segment $\overline \segm(q, p_t)$
between $q$ and $p_t$. Therefore, by the mean-value theorem, there exists $z$ in the open segment $\segm(q, p_t)$ such that
\[
\underbrace{H_{1/2}(q) - H_{1/2}(p_t) - \dotp{\nabla H_{1/2}(p_t)}{q-p_t}}_{=B_{H_{1/2}}(q, p_t)}
= \frac{1}{2}\dotpB{q - p_t}{ \nabla^2 H_{1/2}(z) \, (q-p_t)}\,.
\]
It is useful to introduce the standard notation from convex analysis for the local norm
(which is indeed a norm because the Hessian is positive definite):
\[
\lVert q-p_t \rVert_{\nabla^2 H_{1/2}(z)}^2 \eqdef \dotpB{q - p_t}{ \nabla^2 H_{1/2}(z) \, (q-p_t)}\,.
\]
We therefore have so far the rewriting:
\[
- \frac{B_{H_{1/2}}(q, p_t)}{\eta_t} = - \frac{1}{2\eta_t} \dotpB{q - p_t}{ \nabla^2 H_{1/2}(z) \, (q-p_t)}\,.
\]
Now, by the Cauchy-Schwarz inequality,
\begin{align*}
\dotp{p_t - q}{ \vec M- \what y_t }
&= 	\dotpB{\nabla^2 H_{1/2}(z)^{1/2} \, (p_t - q)}{ \nabla^2 H_{1/2}(z)^{-1/2} \, \big(\vec M- \what y_t \big)} \\
&\leq \lVert p_t - q \rVert_{\nabla^2 H_{1/2}(z)} \,\, \lVert \vec M- \what y_t \rVert_{\nabla^2 H_{1/2}(z)^{-1}}\,.
\end{align*}
Combining the rewriting and the bound above, we get
\begin{align*}
\lefteqn{\dotp{p_t - q}{ M- \what y_t } - \frac{B_{H_{1/2}}(q, p_t)}{\eta_t}} \\
&\leq \lVert p_t - q \rVert_{\nabla^2 H_{1/2}(z)}  \lVert \vec M- \what y_t \rVert_{\nabla^2 H_{1/2}(z)^{-1}} - \frac{1}{2\eta_t} \lVert q-p_t \rVert_{\nabla^2 H_{1/2}(z)}^2 \\
&\leq \frac{\eta_t}{2}  \lVert \vec M- \what y_t \rVert_{\nabla^2 H_{1/2}(z)^{-1}}^2\,,
\end{align*}
where we used $ab - b^2 / 2\leq a^2 / 2$ to get the second inequality.
This is exactly~\eqref{eq:lm3--stdbdmixgap}.
\end{proof}
{"config": "arxiv", "file": "2006.03378/Hadiji-Stoltz--Range-2020--Supplementary.tex"}