Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Bandit Algorithms

212 missions · 116 completed

Missions

Open96Completed116All212
🏆Completed
Machine 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
Machine 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
Algorithmic Game TheoryMachine Learning·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price MechanismResearch Paper

A broker stands between a seller and a buyer who hold private valuations. It posts a price to each side, and trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their valuations: they are simple, strategy-proof, and individually rational. When the same kind of trade repeats, the broker must…

28 thms8 active usersReviewed
🏆Completed
Information TheoryMachine LearningOperations Research·Captain: mikedeng1

Phase Transitions in Bandits with Switching Constraints: every policy with at most S switches has regret at least the phase-dependent rate up to a logarithmic factorResearch Paper

In many sequential decision problems, changing the action is costly or administratively limited: a retailer can revise a posted price only a few times per season, a clinical trial can change its treatment allocation only a few times, and a firm can reconfigure its production line only so often. The multi-armed bandit with switching constraints (BwSC)…

31 thms7 active usersReviewed
🏆Completed
Machine 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
Machine 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
Machine 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
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Dynamic Pricing with Unknown Non-Parametric Demand and Limited Price Changes: The SLPE Policy Has Regret O(√T log T log log T) on Its Concentration Event and Makes O(log log T) Price ChangesResearch Paper

A retailer selling one product over TTT periods must choose a price each period without knowing how demand responds to price. Charging different prices reveals the demand curve but costs revenue, and in practice every price change has its own cost: relabelling, customer goodwill, contractual limits on repricing. Dynamic pricing with learning asks for policies…

10 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 2: Regret Lower Bound for Periodic Multi-Armed Bandits with Known PeriodsResearch Paper

Demand, prices and click-through rates often follow seasonal cycles: weekly, monthly, yearly. A decision maker who repeatedly chooses among options whose expected payoffs repeat in time faces a non-stationary multi-armed bandit. Chen, Wang and Wang (arXiv:2005.08088v4, Operations Research, 2025) study the model in which each arm's mean reward is periodic…

15 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Distribution-Free Contextual Dynamic Pricing 1: The DIP Policy Has Expected Regret at Most C T^(2/3) log T Plus 4 p_max L Times the Episode-Weighted ℓ₁ Estimation ErrorsResearch Paper

In contextual dynamic pricing a seller posts a price for each arriving customer, observes only whether the customer buys, and must learn the demand from these binary responses while selling. The problem arises in e-commerce, insurance and consumer lending, where every customer comes with features (product attributes, customer characteristics) that shift the…

18 thms6 active usersReviewed
🏆Completed
Machine LearningProbabilityReinforcement Learning·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 2: LSVI-UCB Has Regret O(√(d³H³Tι²) + ζdHT√ι) on ζ-Approximately Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces relies on function approximation: value functions are represented as functions of a ddd-dimensional feature map instead of tables indexed by states. Before 2019, regret guarantees for exploration with function approximation either needed strong assumptions (deterministic dynamics, a generative…

17 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems V: Symmetric Monotonic Strategies Draw the Suboptimal Arms Collectively a Linear Number of TimesResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of KKK arms and receives a random reward drawn from the chosen arm's unknown distribution. The classical lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996) describe the regret of good strategies when the horizon TTT tends to infinity: it grows like ln⁡T\ln TlnT, with a constant…

15 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems VI: Uniformly Super-Fast Convergent Strategies Draw Each Suboptimal Arm ln T / K_inf Times up to Explicit Lower-Order TermsResearch Paper

In a stochastic multi-armed bandit, a decision maker repeatedly chooses one of several unknown reward sources. Sampling an arm reveals its reward but uses a round that could have been spent on a better arm. A good strategy must therefore reduce sampling of inferior arms, yet it cannot stop sampling them too early: it must still distinguish the current…

14 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems IV: Under Pairwise Symmetry a Suboptimal Arm Is Drawn T/K Times or Almost as Often as an Optimal ArmResearch Paper

Lower bounds for stochastic multi-armed bandits are usually stated for a large horizon: Lai and Robbins (1985) and Burnetas and Katehakis (1996) show that a consistent strategy pulls a suboptimal arm at least about ln⁡T/Kinf⁡\ln T / \mathcal{K}_{\inf}lnT/Kinf​ times. These bounds say nothing about the small-horizon regime, the first rounds in which a strategy has not yet had…

11 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems II: Uniformly Fast Convergent Strategies Draw Every Suboptimal Arm at Least ln T / K_inf Times AsymptoticallyResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of finitely many arms and sees only the reward from the chosen arm. To earn a high reward, the player must favor arms that appear best. Yet an arm that currently appears inferior might be best under another plausible reward law. That uncertainty forces any strategy with uniformly strong…

11 thms6 active usersReviewed
🏆Completed
Information TheoryMachine LearningStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems I: Expected Draws Weighted by Arm Divergences Dominate the Binary Divergence of the Means of Any [0,1]-Valued StatisticResearch Paper

Lower bounds on the regret of stochastic multi-armed bandit strategies say how often any reasonable strategy must sample an arm that is not the best one. They are the benchmark against which upper bounds for UCB, KL-UCB and Thompson sampling are judged optimal. The classical bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996) were proved by…

11 thms6 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

On the Gittins Index for Multiarmed Bandits 2: A Policy Falls Short of the Gittins Policy by at Most Its Expected Discounted Gap Between the Greatest Gittins Index and That of the Bandit It PlaysResearch Paper

The multiarmed bandit problem asks how to allocate a single resource, one play at a time, among several alternative projects whose states evolve only when they are worked on. It models the scheduling of jobs on a single machine, the design of sequential clinical trials and many problems of research planning. Gittins and Jones showed that it is optimal to…

11 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Improved Algorithms for Linear Stochastic Bandits I: High-Probability Regret Bound for the OFUL AlgorithmResearch Paper

In a linear stochastic bandit, a learner repeatedly chooses an action from a set of vectors and receives a noisy reward whose mean is linear in the action. The model underlies contextual recommendation, adaptive routing and dynamic pricing, where each option is described by features and the payoff of a feature vector must be learned while it is exploited.…

15 thms6 active usersReviewed
🏆Completed
Machine 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
Machine 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
Graph TheoryMachine Learning·Captain: iris

The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback GraphsResearch Paper

Online learning algorithms randomize to hedge against an adversary, and independent resampling makes them change action often. When changing a route, a deployed model or a treatment has a cost of its own, the right benchmark charges one unit per change. With full information this charge leaves the minimax regret at order Tlog⁡K\sqrt{T\log K}TlogK​ (Kalai and Vempala,…

39 thms5 active usersReviewed
Algorithmic Game TheoryConvex Optimization·Captain: iris

Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback: Barrier Bandit Mirror Descent Reaches the Nash Equilibrium at Last-Iterate Rate O~(nT−1/2)\tilde O(nT^{-1/2})O~(nT−1/2)Research Paper

In many operations problems several decision makers act repeatedly on a shared system and see only the payoff they receive: firms setting quantities in a Cournot market observe the market price, sellers in a pricing game observe their revenue, bidders in a Kelly auction observe their allocation. None of them knows the reward functions or their gradients. Ban…

18 thms5 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XIII: Lipschitz Bandits Have Decision-Estimation Coefficient ≲ γ^(−1/(d+1))Textbook

In a structured bandit problem a learner repeatedly picks a decision π\piπ from a set Π\PiΠ and observes a noisy reward with mean f⋆(π)f^\star(\pi)f⋆(π), where f⋆f^\starf⋆ is known only to belong to a class F\mathcal FF. Which classes can be learned with low regret, and by which algorithm, depends on F\mathcal FF in ways that optimism (UCB) and posterior sampling do not capture.…

17 thms5 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning IX: Posterior Sampling Has Bayesian Regret at Most ATlog⁡A\sqrt{AT\log A}ATlogA​Textbook

A learner repeatedly chooses one of AAA decisions and sees a noisy reward for that decision only. In the Bayesian version of this multi-armed bandit problem, the unknown reward distributions are drawn from a known prior. Posterior sampling, also called Thompson sampling or probability matching, plays each decision with the probability that it is optimal given…

20 thms5 active usersReviewed
🏆Completed
Operations Research·Captain: Shuze Chen

Linear Program-Based Policies for Restless Bandits: Necessary and Sufficient Conditions for (Exponentially Fast) Asymptotic Optimality: Exponential convergence of locally affine policiesResearch Paper

A decision maker often manages many similar systems while being able to intervene in only a fraction of them at once. Each system changes over time even when it receives no intervention. A restless bandit describes this situation by treating each system as an arm with its own state and two available actions. The finite-horizon problem is to coordinate those…

13 thms5 active usersReviewed
PreviousPage 1 of 9Next

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