---
author:
\textbf{Lilian Besson} \newline
\and Émilie Kaufmann
smallauthor: Lilian Besson
title: What Doubling Tricks Can and Can’t Do for Multi-Armed Bandits
subtitle: About a well-known and under-studied technique for online reinforcement learning
institute:
PhD Student \newline
Team SCEE, IETR, CentraleSupélec, Rennes \newline
\& Team SequeL, CRIStAL, Inria, Lille
smallinstitute: CentraleSupélec \& Inria
date: IETR Seminar - 15th June 2018
smalldate: 15/06/18
lang: en-US
babel-lang: english
handout: false
numbersections: true
section-titles: false
fontsize: 12pt
toc: false
include-before:
\section*{\hfill{}CentraleSupélec Rennes \& Inria Lille\hfill{}}
\subsection*{\hfill{}Équipes {:} SCEE @ IETR \& SequeL @ CRIStAL\hfill{}}
---
\section{\hfill{}0. Introduction and motivation\hfill{}}
\subsection{\hfill{}0.1. Title\hfill{}}
### **« What Doubling Tricks Can and Can’t Do for Multi-Armed Bandits »**
- *Date* : $15$th of June $2018$
- *Who:* [Lilian Besson](https://GitHub.com/Naereen/slides/) , PhD Student in France, co-advised by
| *Christophe Moy*
@ CentraleSupélec
& IETR, Rennes | *Émilie Kaufmann*
@ Inria, Lille |
|:---:|:---:|
| ![7%](../common/LogoCS.png) ![14%](../common/LogoIETR.png) | ![12%](../common/LogoInria.jpg) |
> See our paper [`HAL.Inria.fr/hal-01736357`](https://hal.inria.fr/hal-01736357)
---
# "Doubling trick" : rapide présentation
## Horizon $T$ : mieux de ne pas la connaître !
- En apprentissage séquentiel, expériences de $t=1$ à $t=T$,
- Pour des applications réelles, les algorithmes ne doivent pas connaître l'horizon... (ex : essais cliniques, pubs en ligne, radio intelligente etc).
- Mais beaucoup sont développés avec "la théorie en tête", et dépendent de la valeur de $T$ !
. . .
## But ?
- $\hookrightarrow$ Peut-on transformer un algorithme $\mathcal{A}$ dépendant de $T$ et le rendre \alert{indépendant de l'horizon} $\mathcal{A}'$ ?
- $\implies$ **Oui !**
- Une technique classique : "doubling trick" !
---
# Algorithme du "Doubling trick"
\begin{algorithm}[H]
% XXX Options
\LinesNumbered % XXX Option to number the line
\DontPrintSemicolon
% \RestyleAlgo{boxed}
% XXX Input, data and output
\KwIn{Algorithme de bandit $\mathcal{A}$, et une suite $(T_i)_{i\in\mathbb{N}}$.}
% \KwData{Données}
% \KwResult{Résultat}
\BlankLine
% XXX Algorithme
Soit $i = 0$, et initialise l'algorithme $\mathcal{A}^{(0)} = \mathcal{A}_{T_0}$.\;
\For{$t = 1, \dots, T-1$}{
\If(\tcp*[f]{Horizon suivante $T_{i+1}$ dans la suite}){
$t > T_i$
}{
Horizon suivante : $i = i + 1$\;
Initialise $\mathcal{A}^{(i)} = \mathcal{A}_{T_i - T_{i-1}}$
\tcp*[f]{Départ à vide}
}
Joue selon $\mathcal{A}^{(i)}$ : choisit le bras $A'(t) := A^{(i)}(t - T_{i-1})$\;
Observe la récompense $r(t) = Y_{A'(t), t}$\;
Lui donner cette observation.
}
\caption{$\mathcal{A}' = \mathrm{DT}(\mathcal{A}, (T_i)_{i\in\mathbb{N}})$.}
\label{algo:DTr}
\end{algorithm}
---
# Deux "doubling" : géométrique et exponentiel
- $T_0 \in \mathbb{N}$, $(T_i)_{i\in\mathbb{N}}$ croissante et divergente
- "Indice du dernier terme" : $L_T := \min\{ i \in\mathbb{N} : T_i > T\}$.
## Géométrique
- Pour un paramètre $b > 1$,
- $T_i := \lfloor T_0 b^i\rfloor$,
- $L_T = \lceil \log_b\left( \frac{T}{T_0} \right) \rceil = \mathcal{O}( \log(T) )$.
## Exponentiel
- Pour deux paramètres $a, b > 1$,
- $T_i := \lfloor \frac{T_0}{a} a^{b^i}\rfloor$,
- $L_T = \lceil \log_b\left( \log_a\left( \frac{T}{T_0/a} \right) \right) \rceil = \mathcal{O}( \log(\log(T)) )$.
---
# Regret et but
## Regret ?
- $R_T(\mathcal{A}_T)$ mesure la performance moyenne de l'algorithme $\mathcal{A}$ (qui peut connaître $T$), sur une expérience d'horizon $T$.
- $R_T(\mathcal{A}) := \sum_{t=1}^T \mu^* - \mathbb{E}[\mu_{A(t)}]$ pour un problème à $K$ bras de moyennes $\mu_1,\dots,\mu_K$, de meilleur bras $\mu^* := \arg\max_k \mu_k$ et si $A(t)$ est le choix de l'algorithme à l'instant $t$.
. . .
## But : *conserver* des bornes de regret !
- Si $\mathcal{A}$ vérifie une borne de regret, *e.g.*, $R_T(\mathcal{A}_T) \leq f(T)$
- Alors la version indépendante de $T$, $\mathrm{DT}(\mathcal{A})$, vérifie une borne similaire, avec une perte constante $\ell$, \alert{ou non} :
+ $R_T(\mathrm{DT}(\mathcal{A})) \leq \ell(\text{paramètres pb}) \times f(T)$ : bien !
+ $R_T(\mathrm{DT}(\mathcal{A})) \leq \ell(\text{paramètres pb}) \times g(T)$ : \alert{moins bien} ! (pour $g(T) \gg f(T)$).
---
# Types de bornes
> $c > 0$ est une constante dépendant des paramètres $\mu_1,\dots,\mu_K$ du problème, mais **pas** de $T$.
1. Regret indépendant des paramètres ("adversarial bandits")
$$R_T(\mathcal{A}_T) \leq c \; \sqrt{T}$$
2. Regret dépendant des paramètres ("stochastic bandits")
$$R_T(\mathcal{A}_T) \leq c \; \log(T)$$
## Forme générique
- \alert{$R_T(\mathcal{A}_T) \leq c \; (\log T)^{\delta} T^{\gamma}$}
+ $\delta=0,\gamma>0$ (adverse),
+ ou $\delta>0,\gamma=0$ (stochastique),
+ ou $\delta>0,\gamma>0$ (hybride !). E.g. : $\sqrt{T \log(T)}$.
---
# Résultats avec un "doubling" géométrique
> Avec des horizons $T_i := \lfloor T_0 b^i\rfloor$.
## Conserve bien $R_T \leq \sqrt{T}$ \hfill\Smiley
- Perte constante $\ell(b,\gamma) = \frac{b^{\gamma}(b-1)^{\gamma}}{b^{\gamma}-1} > 1$,
- $\hookrightarrow$ en connaissant $\gamma$, on choisit $b^*$ pour minimiser la perte.
## Conserve pas bien $R_T \leq \log(T)$ \hfill\Sadey
- \alert{On sait que ça ne peut pas marcher !}
- On a une borne inférieure : transforme ${(\log T)}^{\delta}$ en ${(\log T)}^{\delta\alert{+1}}$.
---
# Résultats avec un "doubling" exponentiel
> Avec des horizons $T_i := \lfloor \frac{T_0}{a} a^{b^i}\rfloor$.
## Conserve *peut-être* $R_T \leq \sqrt{T}$ \hfill\Sey
- \alert{Pas encore de borne sup ou inf convaincante},
- Transforme $\leq T^{\gamma}$ en $T^{\alert{b} \gamma}$, pas génial ($b > 1$)...
- Borne inf a la forme inverse, $\geq T^{\gamma}$ en $T^{\frac{\gamma}{\alert{b}}}$...
## Conserve bien $R_T \leq \log(T)$ \hfill\Smiley
- Perte constante $\ell(\delta, b) = \frac{b^{2\delta}}{b^{\delta}-1} > 1$ (*e.g.*, $\geq 4$ pour $\delta=1$),
- $\hookrightarrow$ en connaissant $\delta$, on choisit $b^*$ pour minimiser la perte.
---
# Illustration
![](images/main____env1-1_1217677871459230631.pdf){width=105%}
---
# Questions encore ouvertes
- Un schéma ($(T_i)_{i\in\mathbb{N}}$) intermédiaire qui conviendrait pour les trois types de bornes ?
- Une autre approche "plus intelligente" qui permettrait d'obtenir des meilleures garanties ?
- Empiriquement : choisir des paramètres ($T_0, b$ ou $T_0,a,b$) n'est pas simple, comment bien les choisir ?
## Question bonus
- \alert{Où publier cet article (refusé à COLT $2018$) ?}\newline
$\hookrightarrow$ une revue ? (*e.g.*, JMLR)
---
# Applications de ce travail I
- Très générique !
- Donne une meilleure compréhension théorique de cette technique très utilisée depuis $\sim$ 20 ans (au moins).
- Justifie quelques articles qui utilisent le "doubling trick" sans justifier plus qu'une note de bas de page disant "on ne perd rien qu'une constante multiplicative dans le regret"...
- Donne une méthode simple pour choisir les valeurs de $T_0,b$ ou $T_0,a,b$ ($\hookrightarrow$ minimiser la perte constante $\ell$ !).
---
# Applications de ce travail II
## En radio intelligente ? Oui aussi !
1. Si on utilise un algorithme $\mathcal{A}_T$ très efficace dans son contexte, mais qui dépend de $T$ (*e.g.*, *Approximated Finite-Horizons Gittins Index*, $\mathrm{kl}$-$\mathrm{UCB}^{++}$, en bandits mono-joueur, *Musical Chair* en bandits multi-joueurs, etc),
2. Si on sait quel genre de garantie on espère (contexte stochastique, ou adverse, ou hybride),\pause
3. $\implies$ Alors on peut savoir quel "doubling trick" utiliser pour rendre son algorithme indépendant de $T$ le plus efficacement possible (on connaît $\delta,\gamma$ alors on choisit $T_0,b$ ou $T_0,a,b$ pour minimiser la perte constante $\ell$...).
---
# Une remarque qui m'intrigue
![](images/sad_paragraph_about_doubling_trick.png){width=90%}
\hfill{}\small{\textcolor{gray}{[\href{https://arxiv.org/abs/1805.05071}{Garivier et al, 2018, arXiv:1805.05071}]}}
\vspace*{10pt}
Surprenant : rien n'est prouvé ni justifié dans ce genre d'affirmations, et aucune référence n'est citée.\newline
Et les auteurs connaissent notre article...
---
\section{\hfill{}6. Conclusion\hfill{}}
\subsection{\hfill{}6.1. Summary\hfill{}}
# Conclusion (1/2)
- Online learning can be a powerful tool for Cognitive Radio, and many other real-world applications
- Many formulation exist, a simple one is the Multi-Armed Bandit
- Many algorithms exist, to tackle different situations
- It's hard to know before hand which algorithm is efficient for a certain problem…
- Online learning can also be used to select *on the run*
which algorithm to prefer, for a specific situation!
---
\subsection{\hfill{}6.2. Summary \& Thanks\hfill{}}
# Conclusion (2/2)
- TODO
- TODO
### See our paper
[`HAL.Inria.fr/hal-01736357`](https://hal.inria.fr/hal-01736357)
### See our code for experimenting with bandit algorithms
Python library, open source at [`SMPyBandits.GitHub.io`](https://SMPyBandits.GitHub.io)
\begin{center}\begin{Huge} \Fontify{Thanks for listening ! :-)} \end{Huge}\end{center}