Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Bandit Algorithms

215 missions · 122 completed

Missions

Open93Completed122All215
🏆Completed
Machine LearningProbability·Captain: mikedeng1

A Modern Introduction to Online Learning VIII: Tsallis-INF Has Adversarial Regret 32L∞√((d − 1)T) and Stochastic Pseudo-Regret 256L∞² Σ_i (1 + ln T)/Δ_iTextbook

In online learning with bandit feedback, the learner chooses one action and sees only that action's loss. This is the information pattern of sequential trials in which testing one option does not reveal the outcomes of the others. The learner must keep its cumulative loss close to that of a good fixed action while learning which actions are good. A…

6 thms4 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

Regret in Online Combinatorial Optimization I: For Every Learning Rate the Exponentially Weighted Forecaster EXP2 Has Full-Information Regret at Least 0.01 d^{3/2}√n on Some Action SetResearch Paper

Online combinatorial optimization is a repeated game in which a learner selects, round after round, a structured object (a subset of fixed size, a path, a matching, a spanning tree) encoded as a 0/1 vector, and an adversary assigns a cost to every coordinate. It models routing, ranking, scheduling and many other sequential decision problems in operations…

7 thms4 active users
🏆Completed
Machine LearningProbability·Captain: mikedeng1

A Tutorial on Thompson Sampling II: Under Thompson Sampling, Per-Period Expected Regret Splits into a Pessimism Term and a Width Term for Any History-Determined U_tResearch Paper

An online decision maker repeatedly chooses an action, observes an outcome, and receives a reward. In a Bayesian model, an unknown parameter controls the outcomes, and the decision maker begins with a prior distribution for that parameter. Thompson sampling acts by drawing a parameter from its current posterior distribution and choosing an action that would…

7 thms4 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Some Aspects of the Sequential Design of Experiments II: Staying on Heads and Switching on Tails Loses at Most 3 − 2√2 per Toss in the Long RunResearch Paper

In 1952 Herbert Robbins asked how a statistician should draw a sample sequentially from two populations when the goal is the largest possible expected total, not a test or an estimate after the fact (Robbins 1952). This is the problem now called the two-armed bandit, and Robbins' paper is the usual starting point of the multi-armed bandit literature that…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms I: The Nonparametric Learn-then-Price Policy Has Regret at Most C(log n)^{1/2}/n^{1/4}Research Paper

A seller with a fixed stock of a single product and a finite selling season has to set prices without knowing how demand responds to them. This is the standard situation in revenue management: airline seats, hotel rooms, fashion goods and event tickets. The classical theory of dynamic pricing (Gallego and van Ryzin, 1994) assumes that the demand function …

15 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Analysis of Thompson Sampling for the Multi-armed Bandit Problem 2: Logarithmic Regret for N ArmsResearch Paper

Thompson Sampling is the oldest heuristic for the multi-armed bandit problem: proposed by Thompson in 1933, it plays each arm with the posterior probability that the arm is the best one. It is simple to implement, performs well empirically (Chapelle and Li, NIPS 2011), and has been used in production systems such as click-through-rate prediction for search…

11 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Optimal Best Arm Identification with Fixed Confidence III: δ-PAC Guarantee of Chernoff's Stopping Rule for Bernoulli BanditsResearch Paper

In best arm identification with fixed confidence, a learner samples KKK unknown distributions ("arms") one at a time, and must eventually stop and name the arm with the largest mean, with an error probability at most a prescribed risk δ\deltaδ, while using as few samples as possible. The problem goes back to the sequential design of experiments (Chernoff, 1959;…

10 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: naimengye

Multi-armed Bandit Allocation Indices I: The Gittins Index, Optimal Stopping and MonotonicityTextbook

A decision-maker has nnn projects, each a Markov reward process, and at every decision time may advance exactly one of them; the others stay frozen. Which project to advance so as to maximize the expected total discounted reward? Posed as a dynamic program the problem has a state space that is the product of the nnn state spaces, and the size of that product…

12 thms4 active usersReviewed
🏆Completed
Machine 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
Machine 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
Machine 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
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

The Fragility of Optimized Bandit Algorithms: Optimized Bandit Algorithms Have Truncated Cauchy Regret TailsResearch Paper

The stochastic multi-armed bandit is the basic model of sequential decision-making under uncertainty: in each round an algorithm chooses one of KKK arms, observes a random reward from that arm's distribution, and tries to play the best arm as often as possible. Since Lai and Robbins (1985) the standard of quality has been the expected regret, and an algorithm…

14 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Contextual Bandits with Cross-Learning: UCB1.CL Has Expected Regret O(Kκ̄ log T/Δ*) and O(√(κ̄KT log T)) with Stochastic Rewards and Adversarial ContextsResearch Paper

In a contextual bandit a learner plays TTT rounds; in round ttt it observes a context ctc_tct​, pulls one of KKK arms and receives the reward of that arm in that context. In many applications the learner also learns what the pulled arm would have paid in other contexts. The motivating example of Balseiro, Golrezaei, Mahdian, Mirrokni and Schneider (arXiv:1809.09582)…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Robust Learning of Consumer Preferences: the Myopic Tracking Policy is worst-case asymptotically optimal for identifying the top-ranked productResearch Paper

A company that is about to launch a product often has several candidate versions of it (designs, packagings, feature bundles) and wants to know which one consumers like best. A common way to find out is to ask: show an arriving consumer a few versions and record which one they pick. Each such query costs time and money, and consumer answers are noisy, so…

22 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents: The Gaussian Gittins Index Equals the Posterior γ-Quantile μ + Φ⁻¹(γ)σ up to o(1) as γ → 1Research Paper

A Gittins index assigns a number to an uncertain arm in a discounted bandit problem. The index converts a sequential choice, where an agent may keep gathering information or retire, into a tax threshold for playing the arm. Computing it generally requires an optimal stopping calculation. A Bayesian upper confidence bound, by comparison, is a quantile of the…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 2: The ML-IS-UCB Bidding Policy Achieves Expected Regret at Most C√T log³ T for Every Oblivious Private-Value SequenceResearch Paper

Display advertising has been moving from second-price to first-price auctions: several exchanges began rolling them out in 2017, and Google Ad Manager completed its move at the end of 2019 (Davies 2019). In a second-price auction bidding one's value is a dominant strategy; in a first-price auction the optimal bid depends on the distribution of the competing…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 1: With IID Private Values a Bidding Policy Achieves Expected Regret at Most C√T log^2.5 TResearch Paper

Most display advertising is sold in first-price auctions: the highest bidder wins and pays its own bid. Since the industry's move away from second-price formats around 2019, a bidder can no longer bid its value and must instead learn how much to shade its bid, from data about how the other bidders behave. A demand-side platform faces this problem millions…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection 4: The Greedy-Phase Budget of the Explore-First Greedy Procedure Decays Exponentially in n0Research Paper

Ranking and selection (R&S) asks which of kkk simulated alternatives has the largest mean when each observation is noisy and the simulation budget is fixed. Large-scale problems, with thousands or millions of alternatives, arise in simulation optimization run on parallel computers, and for them the relevant question is how the total budget BBB must grow with kkk.…

5 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Thompson Sampling with Information Relaxation Penalties II: The IRS Performance Bounds Are Monotone, W^TS ≥ W^IRS.FH ≥ W^IRS.V-Zero and W^TS ≥ W^IRS.V-EMaxResearch Paper

In a Bayesian multi-armed bandit a decision maker pulls one of KKK arms in each of TTT periods, observes the reward, and updates a prior belief about each arm's unknown parameter. The best achievable expected total reward, V∗(T,y)V^*(T, y)V∗(T,y), is the value of a dynamic program over beliefs, and for all but the smallest instances it cannot be computed. Upper bounds on V∗V^*V∗…

9 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Corruption-Robust Exploration in Episodic Reinforcement Learning II: Uniformly Action-Eliminating Algorithms Suffer Expected Regret at Least K/8 for K ≤ A^H/4Research Paper

In stochastic multi-armed bandits, a robust way to explore is action elimination: keep confidence intervals for every arm, discard an arm once its upper confidence bound falls below another arm's lower confidence bound, and sample uniformly among the arms that survive. Uniform sampling is what makes the first corruption-robust bandit algorithm work (Lykouris…

10 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Distribution-Free Contextual Dynamic Pricing 2: Every Algorithm Has Expected Regret at Least C₀ C_p T₀ on Some Perturbed Linear Bandit with Perturbation C_pResearch Paper

Dynamic pricing asks a seller to post prices to a stream of customers and learn demand from purchase decisions alone. Luo, Sun and Liu study the contextual version in which a customer's valuation is linear in a covariate vector plus noise with an unknown distribution (arXiv:2109.07340v2; Mathematics of Operations Research, 2024). Their DIP policy estimates…

5 thms3 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making VII: Policy-Cover Inverse Gap Weighting Certifies dec_γ ≤ 95H³SA/γ for Tabular Reinforcement LearningResearch Paper

In episodic reinforcement learning, an agent learns the rewards and dynamics of a system while choosing actions that determine which states it observes. A bound on the number of states and actions alone does not prescribe how to explore: a policy can be valuable because it earns reward, because it visits an uncertain state-action pair, or both. Foster,…

16 thms3 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making VI: Posterior Sampling Bounds the Dual DEC of Tabular Reinforcement Learning by 26H²SA/γResearch Paper

In episodic reinforcement learning, an agent acts repeatedly in an unknown system and must learn which policy earns the largest expected reward. Even when states and actions are finite, the agent's choices change which data it observes. Foster, Kakade, Qian, and Rakhlin use the decision-estimation coefficient (DEC) to connect this information constraint to…

12 thms3 active usersReviewed
🏆Completed
Information TheoryMachine LearningOperations Research·Captain: mikedeng1

Regret in Online Combinatorial Optimization II: Under Bandit Feedback Every Strategy Has Minimax Regret at Least 0.02 m√(dn) on Some Set of Actions with m OnesResearch Paper

An online player repeatedly chooses a subset of coordinates and pays the sum of their losses. In many applications the player sees only that sum, not the losses of the selected coordinates. This bandit feedback makes it harder to identify which coordinate within each chosen subset is responsible for a favorable or unfavorable outcome. Audibert, Bubeck and…

13 thms3 active usersReviewed
🏆Completed
Information TheoryOperations ResearchProbability·Captain: mikedeng1

Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 2: Any Policy with at Most m Price Changes Has Regret at Least KT^(1/(m+1)) on a Bernoulli InstanceResearch Paper

A seller learning a demand curve normally adjusts prices as new observations arrive. A price-change limit prevents that continual adjustment: a price may have to be chosen before the seller knows which demand curve it faces, then held through a block of sales. This matters when repricing is operationally costly, constrained by contracts, or visible to…

10 thms3 active usersReviewed
PreviousPage 3 of 5Next

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