Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

Bandit Algorithms

Lattimore and Szepesvári's Bandit Algorithms: regret bounds for explore-then-commit, UCB, Thompson sampling, and adversarial bandits.

16 completed missions

Missions

1–16 of 16
Open0Completed16All16
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms III: Asymptotic and Minimax Optimality of UCBTextbook

The basic UCB regret bound of Mission II is logarithmic but not tight: its leading constant 16/Δi16/\Delta_i16/Δi​ is eight times the information-theoretic limit, and its worst-case rate carries a spurious log⁡n\sqrt{\log n}logn​. Chapters 8–9 of Lattimore–Szepesvári close both gaps. A refined confidence schedule f(t)=1+tlog⁡2tf(t) = 1 + t\log^2 tf(t)=1+tlog2t yields the asymptotically optimal …

25 thms10 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms II: Stochastic Bandits and the UCB AlgorithmTextbook

A learner repeatedly chooses one of kkk slot machines, observes only the reward of the chosen arm, and wants to earn almost as much as the best arm in hindsight. This is the stochastic multi-armed bandit, the canonical model of the exploration–exploitation dilemma. This mission formalizes the model (environments, policies, regret, and the regret decomposition …

27 thms9 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XIV: Bayesian Bandits, the Gittins Index and Thompson SamplingTextbook

The oldest bandit algorithm (Thompson, 1933) is also the most modern: sample a parameter from the posterior and act greedily. Chapters 34–36 of Lattimore–Szepesvári develop the Bayesian view in two crowning results. The Gittins index theorem: for infinite-horizon discounted Markov bandits, the seemingly intractable dynamic program is solved exactly by an…

89 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XI: Lower Bounds for Stochastic Linear BanditsTextbook

Is the dnd\sqrt{n}dn​ regret of LinUCB (Mission X) an artifact of the algorithm or a law of nature? Chapters 24–25 of Lattimore–Szepesvári prove it is essentially unimprovable. On the unit ball there is a parameter θ\thetaθ with ∥θ∥22=d2/(48n)\|\theta\|_2^2 = d^2/(48n)∥θ∥22​=d2/(48n) forcing Rn≥dn163R_n \ge \frac{d\sqrt{n}}{16\sqrt{3}}Rn​≥163​dn​​ — the goal theorem — and the hypercube gives the same …

14 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms V: Adversarial Bandits and Exp3Textbook

What if the rewards are not random at all, but chosen by an adversary who knows your algorithm? Remarkably, a randomized learner can still compete with the best fixed arm in hindsight. Chapters 11–12 of Lattimore–Szepesvári develop the adversarial kkk-armed bandit: rewards xti∈[0,1]x_{ti} \in [0,1]xti​∈[0,1] are an arbitrary fixed matrix, the learner samples At∼PtA_t \sim P_tAt​∼Pt​, and…

12 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XVI: Markov Decision Processes and UCRL2Textbook

The final step from bandits to reinforcement learning: actions now change the state of the world. Chapter 38 of Lattimore–Szepesvári studies online learning in an unknown Markov decision process with SSS states, AAA actions and rewards in [0,1][0,1][0,1]. The optimism principle of Mission II scales up: UCRL2 maintains confidence sets over transition kernels, solves an ext…

35 thms6 active users
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms VII: Lower Bounds for Finite-Armed BanditsTextbook

How well can any algorithm possibly do? Chapters 13–17 of Lattimore–Szepesvári answer with three matching impossibility results. The divergence decomposition identifies the information a policy collects: D(Pνπ,Pν′π)=∑iE[Ti(n)]D(Pi,Pi′)D(\mathbb{P}_{\nu\pi}, \mathbb{P}_{\nu'\pi}) = \sum_i \mathbb{E}[T_i(n)] D(P_i, P_i')D(Pνπ​,Pν′π​)=∑i​E[Ti​(n)]D(Pi​,Pi′​). Feeding it into the Bretagnolle–Huber inequality of Mission VI…

13 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XIII: Pure Exploration and Best-Arm IdentificationTextbook

Sometimes reward during learning is irrelevant — a pharmaceutical company running phase-II trials only cares about identifying the best treatment, as quickly and as reliably as possible. Chapter 33 of Lattimore–Szepesvári formalizes fixed-confidence best-arm identification: a policy together with a stopping time τ\tauτ and a recommendation must be sound (wrong…

50 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms IV: Bernoulli Bandits and KL-UCBTextbook

When rewards are binary — a click or no click, a cure or no cure — the subgaussian machinery of Missions I–III is not tight: the variance of a Bernoulli arm degrades near the boundary of [0,1][0,1][0,1], and the correct exponential rate is governed by the binary relative entropy d(p,q)=plog⁡pq+(1−p)log⁡1−p1−qd(p,q) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}d(p,q)=plogqp​+(1−p)log1−q1−p​ rather than a squared distance.…

28 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms VI: Information-Theoretic FoundationsTextbook

Every lower bound in bandit theory rests on one question: how hard is it to tell two probability measures apart from a sample? The answer is quantified by the relative entropy D(P,Q)D(P,Q)D(P,Q), and the sharpest elementary tool is the Bretagnolle–Huber inequality: for any event AAA, P(A)+Q(Ac)≥12exp⁡(−D(P,Q))P(A) + Q(A^c) \ge \frac{1}{2}\exp(-D(P,Q))P(A)+Q(Ac)≥21​exp(−D(P,Q)) — no test can distinguish PPP from QQQ with total…

5 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XV: Partial MonitoringTextbook

Bandit feedback is only one point on a spectrum: a learner might see more than its own loss (full information) or less (a spam filter never learns what happened to mail it deleted). Chapter 37 of Lattimore–Szepesvári studies finite adversarial games G=(L,Φ)G = (\mathcal{L}, \Phi)G=(L,Φ) where the loss matrix and the feedback matrix are decoupled. The goal theorem is the…

16 thms4 active users
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms X: Stochastic Linear Bandits and LinUCBTextbook

When actions are feature vectors and the mean reward is linear — Xt=⟨θ∗,At⟩+ηtX_t = \langle \theta_*, A_t\rangle + \eta_tXt​=⟨θ∗​,At​⟩+ηt​ — a bandit can generalize across arms: pulling one arm reveals information about all of them. Chapter 19 of Lattimore–Szepesvári carries the optimism principle into this setting: LinUCB (a.k.a. OFUL) plays the action maximizing …

8 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms IX: Self-Normalized Concentration and Optimal DesignTextbook

Least-squares estimation from adaptively collected data is the statistical heart of linear bandits: the actions AtA_tAt​ depend on past noise, so classical fixed-design theory does not apply. Chapter 20 of Lattimore–Szepesvári resolves this with the method of mixtures: the process Mt(x)=exp⁡(⟨x,St⟩−12∥x∥Vt(λ)2)M_t(x) = \exp(\langle x, S_t\rangle - \frac{1}{2}\|x\|^2_{V_t(\lambda)})Mt​(x)=exp(⟨x,St​⟩−21​∥x∥Vt​(λ)2​) is a…

9 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms I: Concentration of MeasureTextbook

How quickly does the empirical mean of independent random variables concentrate around the true mean? This question is the analytic engine of the entire theory of stochastic bandits: every optimistic algorithm (Explore-Then-Commit, UCB and its relatives) is calibrated by a tail bound on the sample mean. This mission formalizes the subgaussian framework of…

2 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XII: Follow-the-Regularised-Leader and Mirror DescentTextbook

Beneath Exp3, Exp4 and their relatives lies one algorithm: minimize past losses plus a convex regularizer. Chapters 26–28 of Lattimore–Szepesvári develop this unifying view. For a Legendre potential FFF with Bregman divergence DFD_FDF​, both mirror descent and follow-the-regularised-leader satisfy the master bound …

5 thms2 active users
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms VIII: Contextual Bandits and Exp4Textbook

Real decisions come with context: a news site chooses an article for a particular user. Competing with the single best arm is then meaningless; the right benchmark is the best mapping from contexts to arms, or more generally the best of MMM expert policies. Chapter 18 of Lattimore–Szepesvári formalizes this via Exp4 — exponential weighting over experts, fed…

9 thms2 active usersReviewed

Top contributors

RankContributorAccepted solutionsSubmitted problems
1HXHarry_Xu144141
2GRGrace6368
3RYryanshin170
4MKMKPynnic1612
5JIjianglsbz103
6NINickrobbins9580
7ANann56
7ZJZehao Jin55
9APAphrodite41
9HPHartmann_Psi43

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me