Bandit Algorithms

Motivation

In the multi-armed bandit problem a learner repeatedly chooses one of $K$ actions and observes only the loss of the action it chose. Two models of the environment dominate the literature. In the stochastic model the losses of each arm are drawn i.i.d. from a fixed distribution, and the optimal pseudo-regret grows like $\sum_{i\ne i^*}\log(T)/\Delta_i$, where $\Delta_i$ is the gap between the mean loss of arm $i$ and that of the best arm $i^*$ (Lai and Robbins, 1985). In the adversarial model the losses are arbitrary and the optimal rate is $\Theta(\sqrt{KT})$ (Audibert and Bubeck, 2010). Algorithms that are near-optimal in both models without knowing which one they face are called best of both worlds.

Timeline:

• Bubeck and Slivkins (2012) gave the first best-of-both-worlds algorithm and asked whether one algorithm could be optimal in both regimes.
• Seldin and Slivkins (2014) and Auer and Chiang (2016) obtained $\log^2 T$ or $\log^3 T$ stochastic rates with $\sqrt{KT}$-type adversarial guarantees.
• Wei and Luo (2018) introduced the stochastically constrained adversarial regime and the log-barrier algorithm BROAD.
• Zimmert and Seldin (2021) showed that online mirror descent with the $\tfrac12$-Tsallis entropy (Tsallis-INF) is optimal in both regimes up to constants. Their Theorem 4, the subject of this mission, studies the whole family of $\alpha$-Tsallis regularizers with gap-dependent tuning in the stochastically constrained regime.

Setting

There are $K\ge2$ arms and rounds $t=1,2,\dots$. In round $t$ the learner draws an arm $I_t$ from a probability vector $w_t$ in the simplex $\Delta^{K-1}$, the environment fixes losses $\ell_t\in[0,1]^K$, and only $\ell_{t,I_t}$ is observed. The environment may adapt to the past actions $I_1,\dots,I_{t-1}$ and use its own randomization, modelled by a seed $\omega$ drawn once from a probability measure $\mu$. The pseudo-regret is

$$\overline{Reg}_T=\mathbb E\Big[\sum_{t=1}^T\ell_{t,I_t}\Big]-\min_i\mathbb E\Big[\sum_{t=1}^T\ell_{t,i}\Big],$$

with the expectation over the seed and the learner's draws; a minimizing arm is a best arm in hindsight $i^*_T$.

α-Tsallis-INF is online mirror descent on the simplex. With $\alpha\in(0,1)$, regularization parameters $\xi_i>0$ and learning rates $\eta_t>0$, set

$$\Psi(w)=-\sum_i\frac{w_i^\alpha-\alpha w_i}{\alpha(1-\alpha)\xi_i},\qquad\Psi_t=\Psi/\eta_t .$$

The learner keeps importance-weighted loss estimates $\hat\ell_{t,i}=\mathbb 1(I_t=i)\ell_{t,i}/w_{t,i}$, their sums $\hat L_t$, and plays $w_t=\arg\max_{w\in\Delta^{K-1}}\langle w,-\hat L_{t-1}\rangle-\Psi_t(w)$. The potential $\Phi_t(Y)=\max_{w\in\Delta^{K-1}}\langle w,Y\rangle-\Psi_t(w)$ splits the regret into a stability term $\mathbb E[\sum_t\ell_{t,I_t}+\Phi_t(-\hat L_t)-\Phi_t(-\hat L_{t-1})]$ and a penalty term $\mathbb E[\sum_t\Phi_t(-\hat L_{t-1})-\Phi_t(-\hat L_t)-\ell_{t,i^*_T}]$.

In the stochastically constrained regime the loss differences have fixed means, $\mathbb E[\ell_{t,i}-\ell_{t,i^*}]=\Delta_i$, with a unique best arm $i^*$ ($\Delta_i>0$ for $i\ne i^*$). Then $\overline{Reg}_T=\mathbb E[\sum_t\sum_{i\ne i^*}w_{t,i}\Delta_i]$ and $i^*_T=i^*$. Write $\Delta_{\min}=\min_{i\ne i^*}\Delta_i$. Theorem 4 uses

$$\eta_t=\frac{16^\alpha}{4}\,\frac{1-\bar t^{-1+\alpha}}{(1-\alpha)t^\alpha},\quad\bar t=\max\{e,t\},\qquad\xi_i=\Delta_i^{1-2\alpha}\ (i\ne i^*),\quad\xi_{i^*}=\Delta_{\min}^{1-2\alpha}.$$

Formalization targets

Goal: Theorem 4 (p. 12)

With $T_0=\frac{16}{\Delta_{\min}^2}\log^2\frac{16}{\Delta_{\min}^2}$, for every $T\ge1$,

$$\overline{Reg}_T\le\sum_{i\ne i^*}\frac{\big(8\min\{\frac1{1-\alpha},\log T\}+64\big)(\log T+1)}{\Delta_i}+\frac{16\log^4(T_0)}{\Delta_{\min}}+4 .$$

Milestones

Lemma 17 (Hessian control along a mirror step); Lemma 11, cases 1 and 4 (instantaneous stability); Lemma 20 and Lemma 12, part 2 (penalty); Lemmas 14 and 16 (scalar inequalities for the learning-rate factors); displays (26) and (30) of Appendix D, the stability and penalty bounds under the parameters of Theorem 4.

Lemmas 20 and 12 cover any causal unbiased loss estimator satisfying the bandit feedback assumptions; the other bandit bounds use the importance-weighted estimator.

Significance

The theorem shows that the logarithmic stochastic rate is not special to the $\tfrac12$-Tsallis entropy: for every $\alpha\in(0,1)$, tuning the regularizer to the gaps gives pseudo-regret of order $\sum_{i\ne i^*}\min\{\frac1{1-\alpha},\log T\}\log T/\Delta_i$ in stochastically constrained environments. This places the log-barrier ($\alpha\to0$) and entropic ($\alpha\to1$) regularizers of earlier algorithms in one family, and isolates the role of asymmetric regularization. Unlike Theorem 1, it needs the gaps to tune $\xi$, so it is a statement about the reach of the method rather than a practical algorithm.

The result is proved in the paper; no part of it has a machine-checked proof. Formalizing it produces a complete verified analysis of an online-mirror-descent bandit algorithm with time-varying, non-monotone learning rates, including the stability–penalty decomposition, the Hessian control of Lemma 17 and the explicit constant chase of Appendix D. The analysis also checks two points the paper leaves open: the printed bound has $\log T$ where its proof gives $\log T+1$, and Appendix D applies Lemma 12, which assumes non-increasing learning rates, to a rate that increases for a few early rounds when $\alpha$ is small.

Difficulty

The obvious argument bounds each round's stability by $\sum_i\frac{\eta_t\xi_i}2\mathbb E[w_{t,i}]^{1-\alpha}$ (Lemma 11, case 1) and sums. That bound contains the best arm, whose weight tends to one, so it grows polynomially in $T$ and cannot give a logarithmic rate. The arm $i^*$ has to be removed from the stability, which needs a shifted second-order expansion where losses become slightly negative, and that is only controlled once $\eta_t\xi_i\le\frac14$ (Lemma 17). The early rounds before $T_0$ must be paid for separately, and the asymmetric $\xi$ and the learning rate interact through constants that must be tracked exactly for the self-bounding step to close.

Formalization scope

Arms are Fin K with $K\ge2$ and the paper's arm $i$ is i - 1. Rounds start at 1; an action sequence is h : ℕ → Fin K with h 0 unused. The adversary is the published RegretBandits.Adversarial.Adversary (losses in $[0,1]$ depending on past actions only) composed with a seed drawn from a probability measure, with losses measurable in the seed. Expectations are explicit: an integral over the seed of a finite sum over action paths weighted by $\prod_t w_{t,I_t}$. The algorithm is an argmax predicate on the weight function, never a choice function. $\Phi_t$ is a real supremum over the simplex. Logarithms are natural, and real powers are Real.rpow with nonnegative bases.

The goal takes $\alpha\in(0,1)$; the endpoints $\alpha\in\{0,1\}$, where the paper's learning rate and regularizer are limits, are not stated. The regime "stochastically constrained with a unique best arm" is replaced by the two consequences the proof uses: the self-bounding inequality $\overline{Reg}_T\ge\mathbb E[\sum_t\sum_{i\ne i^*}w_{t,i}\Delta_i]$ and $i^*_T=i^*$. Every such regime satisfies both, so the formal statement is at least as strong as the printed one. The constant $\log T+1$ in the first term is the one the proof reaches. A trivial formalization is ruled out: the expectation is a genuine probability law, the gaps are tied to the losses through the self-bounding hypothesis, and the weights are determined by the algorithm, so the bound cannot hold vacuously.

A complete development needs the explicit law of a bandit run with an adaptive randomized adversary, unbiasedness of the IW estimator, convex conjugates and Bregman divergences on the simplex, and elementary real analysis for Lemmas 14 and 16. The run-law and the stability–penalty decomposition are reusable for any mirror-descent bandit algorithm. Proofs of any milestone, and of the scalar Lemmas 14 and 16 in particular, are welcome independently.

Selected references

• J. Zimmert and Y. Seldin, Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits, Journal of Machine Learning Research 22(28), 2021. https://arxiv.org/abs/1807.07623 (v6)
• S. Bubeck and A. Slivkins, The best of both worlds: stochastic and adversarial bandits, COLT 2012. https://arxiv.org/abs/1202.4473
• C.-Y. Wei and H. Luo, More adaptive algorithms for adversarial bandits, COLT 2018. https://arxiv.org/abs/1801.03265
• J. Abernethy, C. Lee and A. Tewari, Fighting bandits with a new kind of smoothness, NeurIPS 2015. https://arxiv.org/abs/1512.04152
• T. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics 6(1), 1985. https://doi.org/10.1016/0196-8858(85)90002-8
• J.-Y. Audibert and S. Bubeck, Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research 11, 2010. https://jmlr.org/papers/v11/audibert10a.html

Motivation

In the adversarial multi-armed bandit problem a learner repeatedly picks one of $K$ arms and observes only the loss of the arm it picked, while an adversary chooses the losses, possibly reacting to the learner's past choices. The minimax pseudo-regret of this problem is of order $\sqrt{KT}$ after $T$ rounds, and the classical algorithm Exp3 achieves only $\sqrt{KT\log K}$ (Auer et al., 2002). Online mirror descent with a Tsallis-entropy regularizer interpolates between Exp3 (negative Shannon entropy) and the log-barrier, and the choice of the Tsallis parameter $\alpha$ decides which logarithmic factor appears in the bound.

Timeline:

• 2002: Auer, Cesa-Bianchi, Freund and Schapire, Exp3, pseudo-regret $O(\sqrt{KT\log K})$.
• 2009: Audibert and Bubeck, the Poly-INF algorithm, the first $O(\sqrt{KT})$ adversarial bound (COLT 2009).
• 2015: Abernethy, Lee and Tewari analyse gradient-based prediction with Tsallis regularization for $\alpha\in(0,1]$ with a horizon-dependent learning rate (NeurIPS 2015).
• 2017: Agarwal, Luo, Neyshabur and Schapire analyse the log-barrier ($\alpha=0$) (COLT 2017).
• 2019/2021: Zimmert and Seldin give a single anytime analysis covering every $\alpha\in[0,1]$, Theorem 3 of arXiv:1807.07623v6 (JMLR 22(28), 2021).

Setting

There are $K\ge1$ arms and rounds $t=1,2,\dots$. At round $t$ the learner draws an arm $I_t$ from a probability vector $w_t$ in the simplex $\Delta^{K-1}$, the adversary fixes a loss vector $\ell_t\in[0,1]^K$, which may depend on $I_1,\dots,I_{t-1}$ and on the adversary's internal randomization, and the learner observes $\ell_{t,I_t}$. The pseudo-regret is

$$\overline{Reg}_T=\mathbb E\Big[\sum_{t=1}^T\ell_{t,I_t}\Big]-\min_i\mathbb E\Big[\sum_{t=1}^T\ell_{t,i}\Big],$$

with the expectation over both sources of randomness.

The importance-weighted (IW) estimator is $\hat\ell_{t,i}=\mathbb 1(I_t=i)\,\ell_{t,i}/w_{t,i}$ and $\hat L_{t}=\sum_{s\le t}\hat\ell_s$. For $\alpha\in(0,1)$ and $\xi_i>0$ the α-Tsallis regularizer is

$$\Psi(w)=-\sum_i\frac{w_i^\alpha-\alpha w_i}{\alpha(1-\alpha)\xi_i},\qquad\Psi_t=\Psi/\eta_t ,$$

with symmetric regularization $\xi_i=1$. α-Tsallis-INF is online mirror descent:

$$w_t=\arg\max_{w\in\Delta^{K-1}}\ \langle w,-\hat L_{t-1}\rangle-\Psi_t(w),$$

and the potential is $\Phi_t(Y)=\max_{w\in\Delta^{K-1}}\langle w,Y\rangle-\Psi_t(w)$. The pseudo-regret splits into a stability term $\mathbb E[\sum_t\ell_{t,I_t}+\Phi_t(-\hat L_t)-\Phi_t(-\hat L_{t-1})]$ and a penalty term $\mathbb E[\sum_t\Phi_t(-\hat L_{t-1})-\Phi_t(-\hat L_t)-\ell_{t,i^*_T}]$, where $i^*_T$ is a best arm in expectation in hindsight. Theorem 3 uses the learning rate

$$\eta_t=\sqrt{\frac{K^{1-2\alpha}-K^{-\alpha}}{1-\alpha}\cdot\frac{1-t^{-\alpha}}{\alpha t}} .$$

Formalization targets

Goal: Theorem 3, $\alpha\in(0,1)$

$$\overline{Reg}_T\le2\sqrt{\min\Big\{\frac{1}{\alpha-\alpha^2},\frac{\log K}{\alpha},\frac{\log T}{1-\alpha}\Big\}KT}+1\qquad\text{for every }T\ge1 .$$

The goal fixes the constants of the paper; it holds against every randomized adaptive adversary.

Milestones

1. Lemma 11 part 1: the per-round stability is at most $\min\{\sum_i\frac{\eta_t\xi_i}{2}\mathbb E[w_{t,i}]^{1-\alpha},1\}$.
2. The maximum of $\sum_i z_i^{1-\alpha}$ over the simplex is $K^\alpha$.
3. Lemma 20: the penalty is bounded by increments of the inverse learning rate times differences of $\Psi$, plus $\langle u-e_{i^*_T},L_T\rangle$.
4. Lemma 12 part 1: for non-increasing positive learning rates the penalty is at most $\frac{(K^{1-\alpha}-1)(1-T^{-\alpha})}{(1-\alpha)\alpha\eta_T}+1$.
5. Lemma 14: $(1-y^{-x})/x$ is non-increasing on $x>0$, tends to $\log y$, and is at most $\min\{x^{-1},\log y\}$.

Companions

Theorem 3 at the boundaries: $\alpha=1$ (negative-entropy regularizer, rate $\lim_{\alpha\to1}\eta_t=\sqrt{\log(K)(1-t^{-1})/(Kt)}$, bound $2\sqrt{\log(K)KT}+1$) and $\alpha=0$ (log-barrier, rate $\sqrt{(K-1)\log(t)/t}$, bound $2\sqrt{\log(T)KT}+1$).

Significance

Theorem 3 gives one anytime bound for the whole Tsallis family. At $\alpha=\tfrac12$ it is $O(\sqrt{KT})$, the minimax rate, without knowledge of $T$; at $\alpha\to1$ it recovers the Exp3 rate and at $\alpha\to0$ the log-barrier rate, with constants matching Abernethy et al. without tuning the learning rate to the horizon. It is the adversarial half of the paper's study of α-Tsallis-INF, whose stochastic half (Theorem 4) shows why $\alpha=\tfrac12$ is the only value that is optimal in both regimes.

The result is proved in the paper. As far as is known, no machine-checked proof of any Tsallis-INF or Poly-INF regret bound exists. The mission produces a formal model of randomized adaptive adversaries together with online mirror descent for bandits, and formal stability and penalty lemmas for the Tsallis family, which are the standard building blocks of later best-of-both-worlds analyses.

Difficulty

The obvious route, bounding the regret of each fixed seed and action sequence and averaging, fails: the IW estimates have second moments of order $1/w_{t,i}$, which are unbounded, and only their expectation under the learner's own sampling is controlled. The stability term therefore has to be bounded in expectation, for a regularizer whose convex conjugate has no closed form for general $\alpha$. The penalty term involves a learning rate that changes every round, so the potentials of consecutive rounds are not directly comparable. The expectation of the run is over a law that couples the adversary's seed with the learner's random actions, so every step that the paper writes as "take expectations" has to be carried out over that law.

Two features of the printed proof need care. Theorem 3's learning rate is $0$ at $t=1$, where $\Psi_1=\Psi/\eta_1$ is undefined, and for small $\alpha$ it increases between $t=2$ and $t=3$, while Lemma 12 part 1 assumes a non-increasing sequence of positive learning rates. A complete proof of the goal has to handle these first rounds.

Formalization scope

Arms are Fin K with $K\ge1$; action sequences are maps $h:\mathbb N\to$ Fin K with $h(t)=I_t$ and $h(0)$ unused. The adversary is a seed $\omega$ drawn from a probability measure $\mu$ together with one published RegretBandits.Adversarial.Adversary K per seed (losses in $[0,1]$, depending on past actions only), with losses measurable in the seed. The expectation of a quantity at horizon $T$ is $\int\sum_{a}(\prod_{t\le T}w_{t,a_t})F\,d\mu$. The learner's weights are an argmax predicate on a weight function: for every round, the objective $\eta_t\langle w,-\hat L_{t-1}\rangle-\Psi(w)$ is maximized over the simplex. This is the paper's rule whenever $\eta_t>0$, and at $\eta_1=0$ it makes $w_1$ the minimizer of $\Psi$, the uniform vector, which is the initialisation of online mirror descent. No hypothesis on the weights is added beyond this rule. $\Phi_t$ is a real supremum over the simplex, attained because the simplex is compact and nonempty. Powers are real powers; $\log$ is the natural logarithm.

The goal and the milestones take $\alpha\in(0,1)$ (the page: $\alpha\in[0,1]$); the boundary values are separate companion theorems, with the limiting regularizers of §3.2 and the limiting learning rates of p. 12, and the log-barrier companion restricts the weights to the open simplex. Lemmas 12 and 20 are stated, as on the page, for any loss estimator that is conditionally unbiased given the seed and the past, depends on the actions through its own round only, and is measurable and integrable under the run law. The page prints the $\alpha\to1$ limit of the learning rate as $\sqrt{\log(K)(1-t^{-1})/t}$; the true limit carries an extra factor $1/K$ under the root, and the $\alpha=1$ companion uses the true limit. In Lemma 20 the term $\langle u-e_{i^*_T},L_T\rangle$ sits inside the expectation, since $L_T$ is random under an adaptive adversary.

A trivializing formalization is ruled out: the weights are not chosen by a choice function, and an algorithm whose weights are arbitrary at $\eta_1=0$ is excluded because the predicate pins $w_1$.

A complete development needs: convex conjugates of separable regularizers on the simplex, the stability argument via a second-order bound, telescoping of potentials, unbiasedness of IW estimators under the run law, and elementary real-analysis estimates (Lemma 14, the simplex maximum). The run law, the IW estimator and the potential are reusable in the companion missions on Theorem 1 and Theorem 4. Contributions to any milestone, and to reusable lemmas about the run law, are welcome.

Selected references

• J. Zimmert, Y. Seldin, Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits, J. Mach. Learn. Res. 22(28), 2021; arXiv:1807.07623v6. https://arxiv.org/abs/1807.07623
• J. Abernethy, C. Lee, A. Tewari, Fighting Bandits with a New Kind of Smoothness, NeurIPS 2015. https://arxiv.org/abs/1505.00340
• A. Agarwal, H. Luo, B. Neyshabur, R. E. Schapire, Corralling a Band of Bandit Algorithms, COLT 2017. https://arxiv.org/abs/1612.06246
• J.-Y. Audibert, S. Bubeck, Minimax Policies for Adversarial and Stochastic Bandits, COLT 2009. https://www.learningtheory.org/colt2009/papers/024.pdf
• P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM J. Comput. 32(1), 2002. https://doi.org/10.1137/S0097539701398375

Motivation

A multi-armed bandit learner repeatedly chooses one of several actions, observes only the loss of the chosen action, and tries to perform nearly as well as a single fixed action selected in hindsight. Two common loss models make different demands on the learner. In a stochastic model, each arm has a stable mean loss and the learner can gradually distinguish the best arm. In an adversarial model, losses may change with time and even respond to previous choices. A useful bandit algorithm should handle both without first being told which model generated the losses.

Zimmert and Seldin's Tsallis-INF paper analyzes one algorithm in both regimes. Its Theorem 1 gives a square-root guarantee against arbitrary adversarial losses and a logarithmic guarantee when the regret satisfies a self-bounding constraint. The latter condition includes the usual stochastic case with a unique best arm and also permits some adversarial deviations. This mission formalizes the reduced-variance (RV) estimator part of that theorem and six supporting statements from its analysis.

Setting

There are $K\ge1$ arms and rounds $t=1,2,\ldots$. At round $t$, the environment supplies a loss $\ell_{t,i}\in[0,1]$ for each arm $i$. The learner draws an arm $I_t$ from a probability vector $w_t$ and observes only $\ell_{t,I_t}$. The environment can base its current losses on the actions from earlier rounds. It may also randomize: a seed $\omega$ records its internal random choices, while its response to a history remains adaptive. The learner's random actions are then drawn successively from its history-dependent weight vectors. Expectations below average over both sources of randomness.

The pseudo-regret at horizon $T$ compares the learner's expected total loss with the lowest expected total loss of a fixed arm:

$$\operatorname{Reg}_T =\mathbb E\!\left[\sum_{t=1}^{T}\ell_{t,I_t}\right] -\min_i\mathbb E\!\left[\sum_{t=1}^{T}\ell_{t,i}\right].$$

For the algorithm studied here, $\widehat L_{t-1}$ is the vector of estimated losses accumulated before round $t$. The symmetric half-Tsallis regularizer is

$$\Psi_t(w)=-4\eta_t^{-1}\sum_{i=1}^{K}\left(\sqrt{w_i}-\tfrac12w_i\right), \qquad \eta_t=\frac4{\sqrt t}.$$

The vector $w_t$ maximizes $\langle w,-\widehat L_{t-1}\rangle-\Psi_t(w)$ over the probability simplex. With the RV loss estimator, arm $i$ has baseline $B_t(i)=\tfrac12\mathbf 1\{w_{t,i}\ge\eta_t^2\}$ and estimate $\widehat\ell_{t,i}=\mathbf 1\{I_t=i\}(\ell_{t,i}-B_t(i))/w_{t,i}+B_t(i)$. This is an estimator based on the one observed loss, even though its update is a vector.

The self-bounding condition chooses gaps $\Delta_i\in[0,1]$ with exactly one zero, at $i^*$, and a constant $C\ge0$, as defined in Section 2. It requires

$$\operatorname{Reg}_T\ge \mathbb E\!\left[\sum_{t=1}^{T}\sum_{i\ne i^*}w_{t,i}\Delta_i\right]-C.$$

The gaps measure how costly it is to place weight on each non-best arm. In a stochastic bandit with a unique best arm, the usual expected-loss gaps give this relation with $C=0$ Zimmert and Seldin, §2 and §4.1.

Formalization targets

Adversarial guarantee

The first target is an upper bound for every bounded, randomized adaptive adversary and every $T\ge1$:

$$\operatorname{Reg}_T\le 2\sqrt{KT}+14K\log T+16.$$

The paper prints $10K\log T$ in Theorem 1's display. Its proof yields $14K\log T$, the coefficient formalized here; the difference is recorded in the moderation notes. The theorem's other displayed bounds retain their printed constants.

Self-bounding guarantee

For $K\ge2$, set $\Delta_{\min}=\min_{i\ne i^*}\Delta_i$ and

$$X=\sum_{i\ne i^*}\frac{\log T+3}{\Delta_i}+\frac2{\Delta_{\min}}.$$

Under the self-bounding condition, the same algorithm must satisfy

$$\operatorname{Reg}_T\le X+28K\log T+\tfrac32\sqrt K+32+C.$$

When $C>X$, it must also satisfy $\operatorname{Reg}_T\le2\sqrt{XC}+28K\log T+\tfrac32\sqrt K+32$. The goal states both clauses together with the adversarial guarantee. Its six milestones give a pathwise stability bound from Lemma 19, two per-round stability bounds from Lemma 11, two accumulated penalty bounds from Lemma 12, and a finite tail-sum estimate from Lemma 15.

Significance

The adversarial clause limits the cost of learning even when no arm has a persistent advantage. The self-bounding clause gives gap-sensitive logarithmic growth when the learner receives enough information to identify a unique best arm, while allowing the additive deviation $C$. The two guarantees apply to the same weight rule and the same RV estimator Zimmert and Seldin, Theorem 1.

The paper proves its RV claims in prose and equations. A complete Lean proof would make the algorithm's randomized adaptive loss model, its path law, the estimator and the exact constants explicit in machine-checked form. The local theorem statements and definitions in this proposal compile with placeholder theorem proofs; the mission's mathematical results are therefore targets for formalization, not results already machine checked here. The setting definitions may also support formal analyses of other bandit algorithms with adaptive randomized losses.

Difficulty

The learner sees only one loss at each round, so the weight vector depends on estimates whose individual coordinates can be much larger than the observed losses. Bounding the change in the regularized potential by a simple worst-case estimate loses the dependence on the arm weights that the gap-sensitive result needs. The RV estimator reduces this difficulty but can take negative values, which changes the stability calculation. The self-bounding guarantee also compares the theorem's zero-gap arm with a best arm chosen in expectation at horizon $T$; for $C>0$ these need not coincide. That comparator issue is documented for audit.

Formalization scope

The arms are Fin K, with the paper's first arm represented by Lean index zero. Histories are functions on natural-number rounds; entry zero is unused. A referenced published adversarial protocol supplies bounded losses and dependence on past actions. A probability measure on adversary seeds and a finite sum over action paths define the run law. The algorithm is an argmax predicate whose estimates are computed from its own weights and the observed loss. The real-valued simplex supremum defines $\Phi_t$; $K\ge1$ makes that simplex nonempty, and its compactness bounds the objective. The goal requires measurable seeded losses, a probability measure, $T\ge1$, $C\ge0$ in the self-bounding regime, and $K\ge2$ where $\Delta_{\min}$ is used. The penalty milestones take conditionally unbiased estimators that depend only on actions through their own round, are measurable, and have finite expected absolute size, as required for a sequential run and genuine expectations. Positive, non-increasing learning rates are explicit.

The argmax is taken over every simplex weight vector, and the run law includes every action path with its product probability. These choices rule out an arbitrary weight rule or a zero-valued integral masquerading as the algorithm. The development needs reusable facts about the simplex, measurability and integrability of the finite-path law, positivity of Tsallis-INF weights, and bounds on the real potential. Contributions that establish those facts or close the six milestone theorems fit this mission.

Selected references

• Julian Zimmert and Yevgeny Seldin, Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits, Journal of Machine Learning Research 22(28), 2021; formalization follows arXiv:1807.07623v6, pp. 5–10, 18–21.

Motivation

Thompson sampling (TS) chooses each action with the posterior probability that it is optimal. Its practical success in online advertising, recommendation and experimentation raised the question of why it works and when it does not. The tutorial of Russo, Van Roy, Kazerouni, Osband and Wen (Found. Trends Mach. Learn. 11(1), 2018) answers part of that question in §8.1 with an information-theoretic regret bound due to Russo and Van Roy (JMLR 17, 2016). The bound applies to every algorithm, not only TS. It reduces the analysis of a particular algorithm to one quantity, the information ratio: the squared expected regret of a period divided by the information the period yields about the optimal action.

Timeline:

• 2016: Russo and Van Roy, An information-theoretic analysis of Thompson sampling (JMLR 17), introduce the information ratio with the regret and the mutual information both conditioned on a realised history, and prove the regret bound and bounds on the ratio for TS (for example $|\mathcal X|/2$ for $|\mathcal X|$-armed bandits and $d/2$ for linear bandits).
• 2018: Russo and Van Roy, Learning to optimize via information-directed sampling (Oper. Res. 66), design algorithms that minimise the information ratio directly.
• 2018: Russo and Van Roy, Satisficing in time-sensitive bandit learning (arXiv:1803.02855), observe that the same bounds hold with the information ratio averaged over histories. This is the form (8.7) the tutorial uses (footnote 1, p. 75).
• 2018: the tutorial gives the bound as (8.8), with a three-line proof on p. 76 whose last step is cited from the 2016 paper.

Setting

An agent acts in periods $t=1,2,\dots$. In each period it selects an action $x_t$ from a finite set $\mathcal X$ and observes an outcome $y_t$ from a finite set $\mathcal Y$. An unknown parameter $\theta$, taking values in a measurable space $\Theta$, has a prior distribution $P$. Given $\theta$ and the action $x$, the outcome is drawn from a probability vector $q_\theta(\cdot\mid x)$ that depends measurably on $\theta$. The agent receives the reward $r(y_t)$ for a known function $r$. The mean reward of action $x$ is

$$\mu(x,\theta)=\sum_{y}q_\theta(y\mid x)\,r(y),$$

and the optimal action $x^*=x^*(\theta)$ is a measurable selector of $\arg\max_x\mu(x,\theta)$. Ties may be broken in any measurable way, and every result holds for every selector.

The history $\mathbb H_t$ is the list $(x_1,y_1),\dots,(x_t,y_t)$. An algorithm $\pi$ assigns to every history a probability vector over $\mathcal X$, from which the next action is drawn. The joint law of $(\theta,\mathbb H_t)$ is $P(d\theta)\prod_{s\le t}\pi(x_s\mid\mathbb H_{s-1})\,q_\theta(y_s\mid x_s)$, and every expectation below is taken under it. The expected cumulative regret, or Bayesian regret, is

$$\mathbb E[\mathrm{Regret}(T)]=\mathbb E\Big[\sum_{t=1}^T\big(\mu(x^*,\theta)-\mu(x_t,\theta)\big)\Big].$$

The entropy of the prior distribution of $x^*$ is $H(x^*)=-\sum_a\mathbb P(x^*=a)\log\mathbb P(x^*=a)$. The conditional mutual information $I(x^*;(x_t,y_t)\mid\mathbb H_{t-1})$ is the expected information that the period-$t$ observation carries about $x^*$ given the past, averaged over the past. The information ratio of period $t$ is (8.7):

$$\Gamma_t=\frac{\big(\mathbb E[\mu(x^*,\theta)-\mu(x_t,\theta)]\big)^2}{I(x^*;(x_t,y_t)\mid\mathbb H_{t-1})}.$$

Formalization targets

Goal: (8.8)

For every model and every algorithm, every horizon $T$ and every $\bar\Gamma\ge0$ with $\big(\mathbb E[\mu(x^*,\theta)-\mu(x_t,\theta)]\big)^2\le\bar\Gamma\,I(x^*;(x_t,y_t)\mid\mathbb H_{t-1})$ for $t=1,\dots,T$,

$$\mathbb E[\mathrm{Regret}(T)]\le\sqrt{\bar\Gamma\,H(x^*)\,T}.$$

When every mutual information is positive, the least such $\bar\Gamma$ is $\max_{t\le T}\Gamma_t$, which is the tutorial's $\bar\Gamma$. A companion theorem states that literal form under the positivity hypothesis.

Milestones, in the order of the p. 76 proof

1. Regret is additive over periods:

$$\mathbb E[\mathrm{Regret}(T)]=\sum_{t=1}^T\mathbb E[\mu(x^*,\theta)-\mu(x_t,\theta)].$$

2. The Jensen (Cauchy–Schwarz) step: if $\delta_t^2\le\bar\Gamma I_t$ for every $t$ and $\sum_tI_t\le H$, then $\sum_t\delta_t\le\sqrt{T\bar\Gamma H}$. This milestone is the published, proved theorem BanditAlgorithm.information_ratio_cumulative_bound_signed. It states the step in the form the proof uses, with the entropy budget as a hypothesis.
3. The entropy budget:

$$\sum_{t=1}^T I\big(x^*;(x_t,y_t)\mid\mathbb H_{t-1}\big)\le H(x^*).$$

Significance

The result. (8.8) separates the regret analysis of an algorithm into two independent problems. One is a per-period bound on the information ratio, which depends on the structure of the problem and the algorithm. The other is the entropy of the optimal action, which depends only on the prior. Combined with the bound $\bar\Gamma\le|\mathcal X|/2$ that Russo and Van Roy (2016) prove for TS on $|\mathcal X|$-armed bandits, and with $H(x^*)\le\log|\mathcal X|$, it gives $\sqrt{|\mathcal X|\,T\log|\mathcal X|/2}$. On the shortest-path problem of p. 76, $\bar\Gamma\le d/2$ makes the regret depend on the number $d$ of edges and on $H(x^*)$, not on the exponentially large number of paths. The same inequality is the design criterion of information-directed sampling, which chooses actions to minimise the ratio.

Formalizing it. The bound and its proof are known. The work here is to make the probabilistic model explicit, with a general parameter space, an outcome kernel and randomized algorithms; to formalize the per-period decomposition of the regret and the chain-rule argument behind the entropy budget, which the tutorial cites rather than proves; and to obtain (8.8) for every algorithm in one statement. The Proved platform results for Lattimore and Szepesvári's Bayesian adversarial bandit (Theorem 36.5 and its chain-rule lemmas) are about a different model: one algorithm (TS), the best arm in hindsight of a reward matrix, and the budget $\log k$. To our knowledge, (8.8) itself has not been formalized.

Difficulty

The Cauchy–Schwarz step is elementary and already proved on the platform. Milestone 1 is bookkeeping: the cumulative regret integrates over histories of length $T$, while the period-$t$ term integrates over histories of length $t$, and later periods must be integrated out.

The substance is the entropy budget. The obvious attempt bounds each period's information by $H(x^*)$, which loses a factor $T$. The bound is uniform in $T$ only because the per-period informations telescope: their sum is the information that the whole history carries about $x^*$, which is at most the entropy of $x^*$. Each step requires conditional distributions of $x^*$ given histories, where $\theta$ lives in a general measurable space and is integrated against the prior. Zero-probability histories must also be handled consistently with the convention $0\log0=0$.

Formalization scope

• $\mathcal X$ and $\mathcal Y$ are finite types; $\Theta$ is an arbitrary measurable space with a probability measure $P$. The tutorial allows infinite action sets and general outcomes. The finite specialization makes $H(x^*)$ and every mutual information a finite sum. The kernel $q_\theta(\cdot\mid x)$ of §4 replaces the noise representation $y_t=g(x_t,\theta,w_t)$ of p. 70; both describe the same laws.
• Standing hypotheses: $q_\theta(y\mid x)\ge0$, $\sum_yq_\theta(y\mid x)=1$, measurability of $\theta\mapsto q_\theta(y\mid x)$, measurability of the level sets of $x^*$, and $\mu(x,\theta)\le\mu(x^*(\theta),\theta)$. They make every integrand bounded and measurable, so no integrability hypothesis is added.
• An algorithm is a behavioural policy, giving a probability vector over actions for each history. Under perfect recall this is equivalent to an algorithm with internal randomization. Periods are 0-based in Lean: Lean period $s$ is tutorial period $t=s+1$.
• Logarithms are natural in both $I$ and $H$. The conditional mutual information is defined directly as an average of Kullback–Leibler divergences, with joint probabilities. It is not defined as a difference of unconditional mutual informations: that would make the chain rule true by definition and empty milestone 3. $\Gamma_t$ is never written as a quotient in the goal, so a period with zero information cannot turn the bound into one with $\bar\Gamma=0$.
• Needed infrastructure: marginalisation over later periods of the history law, the chain rule of conditional mutual information for finite variables averaged against a general prior, and $I(x^*;\mathbb H_T)\le H(x^*)$. The Proved platform results InformationTheory.kernel_average_categorical_kl_le_marginal_entropy and its _general variant (average KL to the mixture is at most the mixture's entropy), and the adversarial-bandit lemmas BanditAlgorithm.bayesian_ts_conditional_information_gain_chain_rule and bayesian_history_mutualInformation_endpoint_bound, are related tools. A chain-rule library for this history model would be reusable beyond this mission, for example for information-directed sampling. Proofs of auxiliary lemmas are welcome.

The tutorial's argument is on pp. 75–76. The tutorial cites Russo and Van Roy (2016) for the original results, including the entropy budget.

Selected references

• D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, A Tutorial on Thompson Sampling, Foundations and Trends in Machine Learning 11(1):1–96, 2018. https://doi.org/10.1561/2200000070
• D. Russo, B. Van Roy, An Information-Theoretic Analysis of Thompson Sampling, Journal of Machine Learning Research 17(68):1–30, 2016. https://jmlr.org/papers/v17/14-087.html (arXiv: https://arxiv.org/abs/1403.5341)
• D. Russo, B. Van Roy, Learning to Optimize via Information-Directed Sampling, Operations Research 66(1):230–252, 2018. https://doi.org/10.1287/opre.2017.1663
• D. Russo, B. Van Roy, Satisficing in Time-Sensitive Bandit Learning, arXiv preprint, 2018. https://arxiv.org/abs/1803.02855
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 36. https://doi.org/10.1017/9781108571401

Motivation

Thompson Sampling is the oldest bandit algorithm: Thompson proposed it in 1933 for allocating patients between two treatments (Thompson 1933). It keeps a posterior distribution over the unknown mean reward of every action, draws one sample from each posterior, and plays the action whose sample is largest. It is simple, widely used, and in experiments competitive with index policies designed for optimality. For decades it had no matching theoretical guarantee.

The benchmark for a stochastic bandit algorithm is the lower bound of Lai and Robbins (1985): every consistent policy draws a suboptimal arm $a$ at least $(1-o(1))\ln T/K(\mu_a,\mu^*)$ times in $T$ rounds, where $K$ is the Kullback–Leibler divergence. A policy that attains this rate is called asymptotically optimal.

Timeline.

• 1933: Thompson introduces the algorithm, without analysis.
• 1985: Lai and Robbins prove the lower bound and construct asymptotically optimal (but complex) policies.
• 2011–2012: KL-UCB (Garivier and Cappé 2011) and Bayes-UCB (Kaufmann, Cappé and Garivier 2012) attain the bound for Bernoulli rewards with simpler index rules.
• 2012: Agrawal and Goyal give the first logarithmic regret bound for Thompson Sampling, $O\big((\sum_a 1/\Delta_a^2)^2\ln T\big)$, which does not have the optimal constant.
• 2012: Kaufmann, Korda and Munos (arXiv:1205.4217) prove that Thompson Sampling with uniform priors is asymptotically optimal for Bernoulli rewards, with a finite-time bound. This mission formalizes that result.

Setting

There are $K\ge2$ arms. Arm $a$ yields reward $1$ with probability $\mu_a\in(0,1)$ and $0$ otherwise. Arm $1$ is the unique optimal arm: $\mu^*=\mu_1>\mu_a$ for every $a\neq1$. The gap of arm $a$ is $\Delta_a=\mu^*-\mu_a$, and $\mu_2$ denotes the largest mean among the suboptimal arms.

Thompson Sampling with uniform priors. Let $N_{a,t}$ be the number of times arm $a$ has been drawn before round $t$ and $S_{a,t}$ the number of rewards equal to $1$ among those draws. With a uniform prior, the posterior of $\mu_a$ is $\mathrm{Beta}(S_{a,t}+1,\,N_{a,t}-S_{a,t}+1)$. In round $t$ the algorithm draws, independently, a sample $\theta_{a,t}$ from each posterior, plays $A_t=\arg\max_a\theta_{a,t}$, and observes the reward of $A_t$.

The regret after $T$ rounds is

$$\mathcal R(T)=T\mu^*-\mathbb E\Big[\sum_{t=1}^T R_t\Big]=\sum_a\Delta_a\,\mathbb E[N_{a,T}],$$

where $N_{a,T}$ now counts the draws of $a$ in rounds $1,\dots,T$. The Bernoulli divergence is $K(p,q)=p\ln\frac pq+(1-p)\ln\frac{1-p}{1-q}$.

The analysis compares the Thompson samples with two index rules. For an arm with $S$ successes in $N$ draws, at round $t$ of a horizon $T$, the KL-UCB index is $u=\sup\{x\in[S/N,1):N\,K(S/N,x)\le\ln t+\ln\ln T\}$, and the Bayes-UCB index $q$ is the quantile of order $1-\frac1{t\ln T}$ of the posterior $\mathrm{Beta}(S+1,N-S+1)$.

Formalization targets

Goal: Theorem 1 (p. 3)

For every $\epsilon>0$ there is a constant $C$, depending on $\epsilon$ and the instance, such that for every horizon $T$,

$$\mathcal R(T)\le(1+\epsilon)\sum_{a:\,\mu_a\neq\mu^*}\frac{\Delta_a(\ln T+\ln\ln T)}{K(\mu_a,\mu^*)}+C.$$

Only the existence of $C$ is asserted; its value is not fixed, so improvements of the lower-order terms do not invalidate the goal.

Milestones

1. Eq. (1): $\mathcal R(T)=T\mu^*-\mathbb E[\sum_{t=1}^T R_t]=\sum_a\Delta_a\,\mathbb E[N_{a,T}]$.
2. Theorem 2 (p. 4): for each suboptimal $a$ and $\epsilon>0$, $\mathbb E[N_{a,T}]\le(1+\epsilon)\frac{\ln T+\ln\ln T}{K(\mu_a,\mu_1)}+C$.
3. Proposition 1 (p. 4): there is $b\in(0,1)$ with $\sum_{t\ge1}\mathbb P(N_{1,t}\le t^b)<\infty$.
4. Display (4) (p. 5): $\mathbb E[N_{a,T}]\le A+B+2$, an under-estimation term $A$ for arm $1$ plus a KL-UCB term $B$.
5. Lemma 1 (p. 5): $\sum_t\mathbb P\big(\theta_{1,t}\le\mu_1-\sqrt{6\ln t/N_{1,t}}\big)\le N_0(b)+3+C_b$.
6. Lemma 2 (p. 6): $B\le(1+\epsilon)\frac{\ln T+\ln\ln T}{K(\mu_a,\mu_1)}+D$ for large $T$.
7. Lemma 3 (p. 9), in its analytic form (§3.4): a bound on the probability that the optimal arm's samples stay below $\mu_2+\delta$ for $f$ rounds.
8. Lemma 4 (p. 9): saturated suboptimal arms rarely produce samples above $\mu_a+\delta_a$.
9. §2 (p. 3): the Beta–Binomial identity (referenced) and the comparison $q<u$ of the two indices.

Significance

The result. Theorem 1 shows that the leading constant of Thompson Sampling's regret equals the Lai–Robbins constant, so no consistent policy does asymptotically better on Bernoulli bandits. It settled a question open since 1933 and is the starting point for later optimality proofs of Thompson Sampling for exponential families and Gaussian rewards. Proposition 1, a summable tail bound on the event that the optimal arm is under-sampled, is the reusable core: it is a deviation inequality for the number of draws of the optimal arm, which a bound on its expectation does not imply.

The formalization. The result is proved on paper; no machine-checked proof of an optimal-constant bound for Bernoulli Thompson Sampling exists. The platform already has the Gaussian frequentist analysis of Lattimore and Szepesvári (Theorem 36.3) and the non-optimal Agrawal–Goyal bound. This mission adds the Bernoulli, Beta-posterior case with the KL constant, the KL-UCB and Bayes-UCB indices with the $\ln t+\ln\ln T$ exploration rate, and the optimal-arm tail bound. Corrected statements are part of the output: the explicit constant $D$ printed at the end of Lemma 2's proof is too small, the constant $C_{\lambda,\mu_1,\mu_2}$ printed for Lemma 3 has the wrong sign, and Lemma 3 as printed quantifies over arbitrary random intervals, which its proof does not support.

Difficulty

The standard proof for an optimistic index policy bounds the draws of a suboptimal arm by an under-estimation term $\sum_t\mathbb P(l_{1,t}<\mu_1)$ and a concentration term. For Thompson Sampling the under-estimation term is not small: once the posterior of arm $1$ is concentrated, $\mathbb P(\theta_{1,t}<\mu_1)$ is close to $1/2$ in every round. Comparing $\theta_{1,t}$ with a lower confidence bound $\mu_1-\sqrt{6\ln t/N_{1,t}}$ instead only helps if $N_{1,t}$ is large with overwhelming probability, and a bound on $\mathbb E[N_{1,t}]$ does not give that.

Proposition 1 supplies it, and it carries most of the difficulty. It must control long stretches of rounds in which arm $1$ is never drawn while several suboptimal arms compete, and it needs the samples of arm $1$ conditioned on its successes at a random time while the arm is not played, an optional-skipping step that the paper leaves implicit and that is the main measure-theoretic obstacle in Lean.

Formalization scope

Representation. The algorithm is the published Thompson Sampling run (AgrawalGoyalTS_TwoArmed_ThompsonSampling) on the published Bernoulli bandit (bernoulliRelativeEntropy). That run is Agrawal–Goyal's Algorithm 2, which passes each reward through a Bernoulli trial of success probability equal to the reward; for $\{0,1\}$ rewards the trial returns the reward almost surely, so the posterior is exactly the paper's. Probabilities are values of tsLaw in $[0,\infty]$, expectations of counts and the regret are lower integrals in $[0,\infty]$, and every bound compares with the embedding of a real right-hand side.

Conventions.

• Lean arm $0$ is the paper's arm $1$. Lean round $t$ is the paper's round $t+1$; $N_{a,t}$, $S_{a,t}$ are the counts when $\theta_{a,t}$ is drawn, and the paper's $\ln t$ is $\ln(t+1)$ at Lean round $t$.
• $\sqrt{6\ln t/N_{1,t}}=\infty$ when $N_{1,t}=0$ (p. 4), encoded by cases.
• The KL-UCB supremum ranges over $x<1$, because the real-valued divergence at $q=1$ is a finite junk value; $u=1$ when $N=0$ or $S=N$, cases the page leaves undefined.
• Every constant with a printed dependence list ($C$, $D$, $N$, $b$, $C_b$) is chosen after the instance (and $\epsilon$, the arm) and before $T$.

Added hypotheses and corrections.

• $0<\mu_a<1$ for every arm, and $K\ge2$: not stated in the paper but used by its proof (it divides by $\mu_1(1-\mu_1)$, and $K(\mu_a,1)=\infty$).
• Arm $1$ is the unique optimal arm (the paper's standing assumption of §2; its reduction of several optimal arms to one is cited, not proved).
• Display (4) and the index comparison are stated for $T\ge3$ (the page's $T\ge e$) and rounds $1\le t\le T$.
• Lemma 2 asserts only the existence of $D$; Lemma 3 is formalized as the analytic bound of §3.4 with the sign-corrected constant; Lemma 1's $C_b$ is read with the pre-draw count.

Trivializations ruled out. Thompson Sampling is not characterized by a predicate that an arbitrary policy could satisfy: it is the published run, which fixes the posterior draws, the argmax and the updates. The constant is quantified as $\forall\epsilon\,\exists C\,\forall T$, never $\forall T\,\exists C$, and no real number is extracted from a possibly infinite expectation.

Infrastructure and contributions. A complete development needs Beta–Binomial duality, Chernoff–Hoeffding bounds for binomial tails, optional skipping for the reward stacks of the played arms, and the KL-UCB counting argument. The Beta–Binomial identity is an open milestone shared with the Agrawal–Goyal mission. Proofs of any milestone, in particular Proposition 1, Lemma 4 and the analytic Lemma 3, are welcome; Lemma 3's bound and the index comparison are pure real analysis and reusable beyond bandits.

Selected references

• E. Kaufmann, N. Korda, R. Munos, Thompson Sampling: An Asymptotically Optimal Finite Time Analysis, ALT 2012 (LNCS 7568); arXiv:1205.4217v2. https://arxiv.org/abs/1205.4217
• W. R. Thompson, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika 25, 1933. https://doi.org/10.2307/2332286
• T. L. Lai, H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics 6, 1985. https://doi.org/10.1016/0196-8858(85)90002-8
• S. Agrawal, N. Goyal, Analysis of Thompson Sampling for the multi-armed bandit problem, COLT 2012; arXiv:1111.1797. https://arxiv.org/abs/1111.1797
• A. Garivier, O. Cappé, The KL-UCB algorithm for bounded stochastic bandits and beyond, COLT 2011; arXiv:1102.2490. https://arxiv.org/abs/1102.2490
• E. Kaufmann, O. Cappé, A. Garivier, On Bayesian upper confidence bounds for bandit problems, AISTATS 2012. https://proceedings.mlr.press/v22/kaufmann12.html

Motivation

In a linearly parameterized bandit, a decision maker repeatedly chooses an arm from a possibly infinite set of vectors and receives a noisy reward whose mean is linear in an unknown parameter. Classical bandit policies treat arms as independent and must try each arm, so their regret grows with the number of arms (Lai and Robbins 1985); in applications such as marketing, where similar products are expected to have similar sales, the linear structure lets one observation inform many arms, and the regret can be made independent of the number of arms. Rusmevichientong and Tsitsiklis (arXiv:0812.3465v2, Mathematics of Operations Research 2010) show that when the arms form the unit sphere of $\mathbb R^r$, no policy has Bayes risk below order $r\sqrt T$. This mission concerns their matching upper bound: a simple policy that alternates exploration and greedy exploitation in cycles of growing length attains regret of order $r\sqrt T$ whenever the best arm depends smoothly on the parameter.

The linearly parameterized bandit was studied earlier by Abe and Long (1999), Auer (2002) and, independently of this paper, Dani, Hayes and Kakade (2008), whose policies rely on confidence regions for the parameter. The result here shows that for arm sets with a smooth best arm, such as balls and, by Polovinkin (1996), ellipsoids, a phase-based policy with a single least squares estimate per cycle suffices.

Setting

Let $r \ge 2$ and let $\mathcal U_r \subset \mathbb R^r$ be a compact set of arms. Playing arm $u$ in period $t$ yields the reward

$$X^u_t = u'Z + W^u_t,$$

where $Z \in \mathbb R^r$ is an unknown parameter and the errors $W^u_t$ are independent of each other and of $Z$, identically distributed in $t$ for each arm, with mean zero.

Assumption 1 fixes constants $\sigma_0, \bar u, \lambda_0 > 0$ that do not depend on $r$: (a) every error satisfies $\mathbb E[e^{xW^u_t}] \le e^{x^2\sigma_0^2/2}$ for all $x \in \mathbb R$; (b) every arm has $\|u\| \le \bar u$, and $\mathcal U_r$ contains linearly independent arms $b_1, \dots, b_r$ with $\lambda_{\min}(\sum_k b_kb_k') \ge \lambda_0$.

The smooth best arm response condition SBAR($J$) requires that every $z \ne 0$ have a unique best arm $u^*(z)$, the maximizer of $v'z$ over $\mathcal U_r$, and that $\|u^*(z) - u^*(y)\| \le J\|z - y\|$ for unit vectors $z, y$.

The PEGE policy (Phased Exploration and Greedy Exploitation) runs in cycles $c = 1, 2, \dots$. In cycle $c$ it plays $b_1, \dots, b_r$ once each, computes the ordinary least squares estimate

$$\widehat Z(c) = \frac1c\Big(\sum_{k=1}^r b_kb_k'\Big)^{-1}\sum_{s=1}^c\sum_{k=1}^r b_k X^{b_k}(s)$$

from all exploration rewards so far, and then plays a greedy arm $G(c) \in \arg\max_{v \in \mathcal U_r} v'\widehat Z(c)$ for $c$ periods, ties broken arbitrarily.

The regret given $Z = z$ over $T$ periods is $\mathrm{Regret}(z, T, \mathrm{PEGE}) = \sum_{t=1}^T \mathbb E[\max_{v \in \mathcal U_r} v'z - U_t'z \mid Z = z]$, where $U_t$ is the arm played in period $t$, and the risk is $\mathrm{Risk}(T, \mathrm{PEGE}) = \mathbb E[\mathrm{Regret}(Z, T, \mathrm{PEGE})]$ for a prior on $Z$.

Formalization targets

Goal: Theorem 3.1 (p. 15)

Under Assumption 1 and SBAR($J$), there is $a_1 > 0$ depending only on $\sigma_0, \bar u, \lambda_0, J$ such that for every $r \ge 2$, every $z \ne 0$ and $T \ge r$,

$$\mathrm{Regret}(z, T, \mathrm{PEGE}) \le a_1\Big(\|z\| + \frac1{\|z\|}\Big) r\sqrt T,$$

and, if $\mathbb E\|Z\| \le M$ and $\mathbb E[1/\|Z\|] \le M$ for every $r$, there is $a_2$ depending only on $\sigma_0, \bar u, \lambda_0, J, M$ with

$$\mathrm{Risk}(T, \mathrm{PEGE}) \le a_2\, r\sqrt T.$$

The constants are unspecified; only the order $r\sqrt T$ and its uniformity in $r$ are asserted.

Milestones on the way

• Lemma 3.4 (p. 16): $\mathbb E[\|\widehat Z(c) - z\|^2 \mid Z = z] \le h_1 r/c$.
• Lemma 3.5 (p. 17): $\|w/\|w\| - z/\|z\|\| \le 2\|w - z\|/\max\{\|z\|, \|w\|\}$.
• Lemma 3.6 (p. 17): $\mathbb E[\max_{u} z'(u - G(c)) \mid Z = z] \le r h_2/(c\|z\|)$.
• Sec. 3.1 (p. 18): $\mathrm{Regret}(z, rK + \sum_{c=1}^K c, \mathrm{PEGE}) \le h_3 r\|z\|K + h_4\sum_{c=1}^K r/\|z\|$.

Further results

• Lemma 3.2 (p. 16): a density condition near the origin gives $\mathbb E[1/\|Z\|] \le M$; for $Z \sim N(0, I_r/r)$, $\mathbb E\|Z\| \le 1$ and $\mathbb E[1/\|Z\|] \le \sqrt\pi$.
• The unit ball and the unit sphere satisfy SBAR(1) (pp. 15–16).
• Corollary 3.3 (p. 16): on the unit sphere with standard normal errors, $\mathrm{Regret} \le a_3(\|z\| + 1/\|z\|)r\sqrt T$ and, under the prior $N(0, I_r/r)$, $\mathrm{Risk} \le a_3 r\sqrt T$.

Significance

Theorem 3.1 with the lower bound of Theorem 2.1 of the same paper identifies $r\sqrt T$ as the optimal order of the regret and the Bayes risk on the unit sphere, and Corollary 3.3 makes this precise. The bound is achieved by a policy with no confidence sets and no per-period optimization beyond one linear maximization per cycle. The factor $\|z\| + 1/\|z\|$ shows how the difficulty depends on the size of the parameter; combined with the trivial bound $2\bar u\|z\|T$, the regret does not deteriorate as $\|z\| \to 0$.

The results are proved in the paper; none of them is machine-checked. A formalization yields a verified dimension-explicit regret bound for an explore–exploit policy with a continuum of arms, the least squares error bound under sub-Gaussian noise (Lemma 3.4), and Lipschitz properties of normalization and of the best-arm map on balls, all of which are reusable.

Difficulty

The expected instantaneous regret of a greedy arm computed from a noisy estimate is not obviously small: for a general compact arm set the best arm may jump under a small perturbation of the parameter, and the regret is then of order $\|z\|$ however good the estimate is. The SBAR condition prevents such jumps, but only for unit vectors, so the estimation error must be transferred to the direction of the estimate, which costs a factor $1/\|z\|$. The estimate may also vanish with positive probability when the errors are discrete, where the greedy arm is arbitrary. Finally, the constants must be uniform in the dimension $r$: a bound with an $r$-dependent constant is immediate from $\mathrm{Regret} \le 2\bar u\|z\|T$, so the content of the theorem lies in keeping every constant independent of $r$ and of the arm set.

Formalization scope

Vectors live in EuclideanSpace ℝ (Fin r), so the norm is Euclidean and the inner product is $u'z$. The model's standing assumptions are encoded as follows: $\mathcal U_r$ is compact; the errors of each arm have mean zero and a law $\nu_u$; Assumption 1(a) requires the moment generating function to exist and satisfy the sub-Gaussian bound; Assumption 1(b) writes $\lambda_{\min}(\sum_k b_kb_k') \ge \lambda_0$ as $\lambda_0\|x\|^2 \le \sum_k (b_k'x)^2$. Every constant is quantified before the dimension $r$, the arm set, the error laws, the exploration arms, the tie-breaking rule, the prior, $z$ and $T$; a version with constants depending on $r$ or on the instance is trivial and is excluded by this quantifier order.

PEGE uses exactly the exploration arms $b_k$ of Assumption 1(b), which are an argument of the policy. The greedy rule is any measurable selection of a maximizer; measurability, implicit on the page, is a hypothesis. Since PEGE uses only exploration rewards, the expectation is over an independent table of exploration errors $W^{b_k}(s)$ with laws $\nu_{b_k}$, with the parameter fixed to $z$ ("given $Z = z$"). Regret and risk are lower Lebesgue integrals of nonnegative gaps, valued in $[0, \infty]$, so an upper bound is never satisfied by a default value of an integral. The moment conditions on the prior are lower Lebesgue integrals, so $\mathbb E[1/\|Z\|] = \infty$ if the prior charges the origin.

Two printed statements are adjusted. Lemma 3.6 is printed "for any $z \in \mathbb R^r$", but its bound $r h_2/(c\|z\|)$ is undefined at $z = 0$; it is stated for $z \ne 0$. The p. 18 cycle-sum display is likewise stated for $z \ne 0$. In Corollary 3.3, the exploration arms are those of Assumption 1(b) with $\bar u = \lambda_0 = 1$, as in its proof. Measurability of the density in Lemma 3.2(a) is added.

The source is arXiv:0812.3465v2; its printed page numbers equal the PDF page numbers. Contributions welcome: proofs of the milestones, a sub-Gaussian least squares library, and the Lipschitz analysis of best-arm maps.

Selected references

• P. Rusmevichientong, J. N. Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, 2010; Mathematics of Operations Research 35(2), 2010. https://arxiv.org/abs/0812.3465v2
• V. Dani, T. P. Hayes, S. M. Kakade, Stochastic Linear Optimization under Bandit Feedback, COLT 2008. https://www.learningtheory.org/colt2008/papers/80-Dani.pdf
• P. Auer, Using Confidence Bounds for Exploitation-Exploration Trade-offs, Journal of Machine Learning Research 3, 2002. https://www.jmlr.org/papers/v3/auer02a.html
• E. S. Polovinkin, Strongly convex analysis, Sbornik: Mathematics 187(2), 1996. https://doi.org/10.1070/SM1996v187n02ABEH000111