Bandit Algorithms

Motivation

In the adversarial (non-stochastic) multi-armed bandit problem a forecaster repeatedly chooses one of $K$ actions while an opponent sets the rewards, and only the reward of the chosen action is revealed. The model was proposed as a way of playing an unknown repeated game: Baños (1968) studied the repeated game in which the player observes only its own payoff, which is exactly the bandit problem against an opponent who reacts to the player's past moves. It is the basic model of online decision making under partial feedback without statistical assumptions, and it underlies regret minimization in games, adversarial routing and online advertising. Chapter 3 of Bubeck and Cesa-Bianchi's monograph (arXiv:1204.5721v2) collects its fundamental results: the Exp3 forecaster of Auer, Cesa-Bianchi, Freund and Schapire (SIAM J. Comput. 2002), its high-probability variant Exp3.P, and the $\sqrt{nK}$ minimax lower bound.

Setting

There are $K \ge 2$ arms and rounds $t = 1, 2, \dots, n$. At each round an adversary assigns a gain $g_{i,t} \in [0,1]$ to every arm $i$; the forecaster picks an arm $I_t$, possibly at random, and observes only $g_{I_t,t}$. The adversary may be non-oblivious (adaptive): $g_{i,t} = g_{i,t}(I_1,\dots,I_{t-1})$ may depend on the forecaster's past actions. A forecaster rule maps the past actions to a probability vector $p_t$ on the arms, and a run is a sequence of random arms with $I_t \sim p_t$ given the past. The regret is the random variable

$$R_n = \max_{i=1,\dots,K}\sum_{t=1}^n g_{i,t} - \sum_{t=1}^n g_{I_t,t},$$

and, in the loss version $\ell_{i,t} \in [0,1]$, the pseudo-regret is $\overline R_n = \mathbb E\sum_t \ell_{I_t,t} - \min_i \mathbb E\sum_t \ell_{i,t}$. Since the maximum sits inside the expectation, $\overline R_n \le \mathbb E R_n$ in the gain version, and against an adaptive adversary the two can differ.

Exp3 draws $I_t$ from exponential weights $p_{i,t+1} \propto \exp(-\eta_t \tilde L_{i,t})$ of importance-weighted cumulative loss estimates $\tilde L_{i,t} = \sum_{s \le t} \ell_{i,s}\mathbb 1_{I_s = i}/p_{i,s}$. Exp3.P uses biased gain estimates $\tilde g_{i,t} = (g_{i,t}\mathbb 1_{I_t=i} + \beta)/p_{i,t}$ and mixes in the uniform distribution:

$$p_{i,t+1} = (1-\gamma)\frac{\exp(\eta\tilde G_{i,t})}{\sum_k \exp(\eta \tilde G_{k,t})} + \frac{\gamma}{K}, \qquad \tilde G_{i,t} = \sum_{s=1}^t \tilde g_{i,s}.$$

Formalization targets

Goal: Theorem 3.3 (expected regret of Exp3.P)

With $\beta = \sqrt{\ln K/(nK)}$, $\eta = 0.95\sqrt{\ln K/(nK)}$, $\gamma = 1.05\sqrt{K\ln K/n}$, against every adaptive adversary,

$$\mathbb E R_n \le 5.15\sqrt{nK\ln K} + \sqrt{\frac{nK}{\ln K}}.$$

Milestones

• Lemma 3.1: for $\beta \in (0,1]$ and a fixed arm $i$, with probability at least $1-\delta$, $\sum_t g_{i,t} \le \sum_t \tilde g_{i,t} + \ln(\delta^{-1})/\beta$.
• Eq. (3.12): if $\gamma \le 1/2$ and $(1+\beta)K\eta \le \gamma$, then with probability at least $1-\delta$,

$$R_n \le \beta nK + \gamma n + (1+\beta)\eta Kn + \frac{\ln(K\delta^{-1})}{\beta} + \frac{\ln K}{\eta}.$$

• Theorem 3.2: with $\beta = \sqrt{\ln(K\delta^{-1})/(nK)}$, $R_n \le 5.15\sqrt{nK\ln(K\delta^{-1})}$ (3.10); with $\beta = \sqrt{\ln K/(nK)}$, $R_n \le \sqrt{nK/\ln K}\,\ln(\delta^{-1}) + 5.15\sqrt{nK\ln K}$ (3.11), each with probability at least $1-\delta$.
• Theorem 3.1: Exp3 with $\eta = \sqrt{2\ln K/(nK)}$ has $\overline R_n \le \sqrt{2nK\ln K}$ (3.2); with $\eta_t = \sqrt{\ln K/(tK)}$, $\overline R_n \le 2\sqrt{nK\ln K}$ (3.3).
• Lemma 3.2 and Theorem 3.4: for $n \ge K \ge 2$ and every forecaster there is a Bernoulli instance with $\max_i \mathbb E\sum_t Y_{i,t} - \mathbb E\sum_t Y_{I_t,t} \ge \sqrt{nK}/20$.

Significance

The goal bounds the expected regret, not the pseudo-regret, against an opponent that adapts to the forecaster's randomized past choices. A pseudo-regret bound says nothing about $\mathbb E R_n$ in that setting, and the book obtains the expected-regret bound by first proving a high-probability bound valid at every confidence level, (3.11), and integrating its tail. Together with Theorem 3.4 the chapter shows that $\sqrt{nK}$ is the minimax rate of adversarial bandits up to a $\sqrt{\ln K}$ factor. Lemma 3.1, the concentration of biased importance-weighted estimates, holds for any forecaster rule and is the step that turns exponential weights into a high-probability guarantee.

All results are proved in the book. On the formal side, the platform has the pseudo-regret bound of Exp3 against an oblivious adversary (a fixed reward table, Bandit Algorithms V) and an Exp3-IX high-probability bound; it has no Exp3.P, no regret bound against adaptive adversaries and no Bernoulli $\sqrt{nK}/20$ lower bound. This mission adds an explicit model of adaptive adversaries and randomized forecaster runs, and the chapter's statements with the book's exact constants.

Difficulty

Against an adaptive adversary the gains are random and depend on the forecaster's own past draws, so the argument used for a fixed reward table (take expectations of an inequality that holds for every fixed sequence) does not control $\mathbb E R_n$: the maximum over arms does not commute with the expectation. Unbiased estimates do not help either, because the variance of $\ell_{i,t}/p_{i,t}$ is of order $1/p_{i,t}$, which can be arbitrarily large; even with uniform mixing at rate $n^{-1/2}$ the cumulative variance is of order $n^{3/2}$. The bias $\beta$ and the mixing $\gamma$ have to be tuned jointly so that the estimate concentrates while the exponential-weights analysis survives, and the constants $0.95$, $1.05$ and $5.15$ come out of that tuning. The lower bound needs an information-theoretic comparison of a forecaster's behaviour on $K+1$ Bernoulli instances, against forecasters that may be randomized.

Formalization scope

Arms are Fin K with $K \ge 2$; rounds are numbered $1,\dots,n$; logarithms are natural. Action sequences are functions $\mathbb N \to$ Fin K whose entry $0$ is ignored. An adversary is a structure holding values in $[0,1]$ that may depend on the past actions only (gains for Exp3.P, losses for Exp3); a randomized adversary with independent external randomness reduces to this case by conditioning. A run of a forecaster rule $p$ on a probability space is pinned down by the cylinder identity $\mathbb P(I_1 = h_1,\dots,I_t = h_t) = \mathbb P(I_1=h_1,\dots,I_{t-1}=h_{t-1})\,p_t(h)(h_t)$, which determines the law of $(I_1,\dots,I_n)$. "With probability at least $1-\delta$" is $\mathbb P(\text{event}) \ge 1-\delta$ for $\delta \in (0,1)$, and $\mathbb E R_n$ is the Bochner integral of the bounded, measurable regret. The lower bounds use a stochastic model in which the forecaster sees past actions and the rewards of the played arms, and rewards are i.i.d. product Bernoulli.

Constants and conventions:

• Every constant is the book's exact one: $0.95$, $1.05$, $5.15$, $1/20$. No $O(\cdot)$ is involved.
• Exp3.P with $1.05\sqrt{K\ln K/n} > 1$ is outside the box's range $\gamma \in [0,1]$; its vector can then have negative entries, and if it does on a history of positive probability no run exists. This happens only when $n < 1.11\,K\ln K$, where the printed bounds already follow from $R_n \le n$, so the statements are true there whether or not a run exists.
• Corrected misprints: the Exp3 box's $\tilde\ell_{i,s}$ is $\tilde\ell_{i,t}$; the sign in (3.16) is the box's $\exp(+\eta\tilde G)$; the proof of (3.10) says the bound is trivial "if $n \ge 5.15\sqrt{\cdots}$", which should be $n \le$. The statements carry no lower bound on $n$.
• Added standing hypotheses: $K \ge 2$ everywhere, $n \ge K$ in Theorem 3.4 (from the protocol box, p. 6; Theorem 3.4 is false without it), $\beta > 0$ and $p_{i,t} > 0$ in Lemma 3.1.
• Theorem 3.4 is stated as "for every forecaster there is a Bernoulli instance with regret at least $\sqrt{nK}/20$", which implies the book's $\inf\sup$ (3.18).

A trivializing formalization is ruled out: the forecasters are fixed rules of the observed history drawn with fresh randomness, the adversary is not restricted to a fixed sequence, and the lower bounds quantify over all forecasters and exhibit the instance.

Welcome contributions: a reusable construction of runs (existence of a probability space carrying a run for every rule), the supermartingale form of Lemma 3.1, the exponential-weights potential argument, a tail-integration lemma $\mathbb E W \le \int_0^1 \delta^{-1}\mathbb P(W > \ln\delta^{-1})\,d\delta$, and a KL/Pinsker comparison for bandit runs.

Selected references

• S. Bubeck, N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends in Machine Learning 5(1), 2012. arXiv:1204.5721v2, doi:10.1561/2200000024
• P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The nonstochastic multiarmed bandit problem, SIAM Journal on Computing 32(1), 2002. doi:10.1137/S0097539701398375
• J.-Y. Audibert, S. Bubeck, Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research 11, 2010. jmlr.org/papers/v11/audibert10a
• N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006. doi:10.1017/CBO9780511546921