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
Operations ResearchStatistics·Captain: mikedeng1

Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies IV: Sufficient Conditions for Logarithmic Regret with a Known Incumbent PriceResearch Paper

A seller who does not know how demand responds to price must learn the demand curve from its own sales while also earning revenue. This is the learn-and-earn problem of dynamic pricing. Every price it charges both earns and informs, and a policy that only earns can stop learning. Keskin and Zeevi (Operations Research 62(5), 2014) study the problem for a…

11 thms3 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Optimal Dynamic Assortment Planning with Demand Learning: The Separation-Based Policy Has Regret at Most κ₁⌈N/C⌉ log T + K̄₁Research Paper

A retailer who can display only a limited number of products must decide which assortment to show each arriving customer, without knowing how attractive each product is. Offering a product reveals how often it is bought, but offering a poor product costs revenue. This exploration–exploitation trade-off arises in fast fashion, where the selling season is…

13 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits I: The Regret Bound of ILOVETOCONBANDITSResearch Paper

In a contextual bandit problem a learner repeatedly observes a context (a user, a patient, a query), chooses one of KKK actions, and observes the reward of the chosen action only. It competes with the best policy of a fixed class Π\PiΠ of maps from contexts to actions. This is the standard model for news and advertisement recommendation, adaptive clinical…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: naimengye

Multi-armed Bandit Allocation Indices VI: Bandit Sampling Processes, Favourable Priors and Invariance of the IndexTextbook

The bandit processes that motivated the index theorem are sampling processes: an arm is a population from which one draws i.i.d. observations whose distribution has an unknown parameter, and each draw both earns something and teaches something. Chapter 7 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/97804709800…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: naimengye

Multi-armed Bandit Allocation Indices V: Restless Bandits, Indexability and Whittle Indices for Monotone ModelsTextbook

Every proof of the index theorem in Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), uses the fact that a bandit not being processed is frozen. Chapter 6 drops that: Whittle's restless bandits evolve under the passive action too, by a different law, and mmm of nnn must be active at every time. The…

7 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: naimengye

Multi-armed Bandit Allocation Indices IV: The Achievable Region, Generalized Conservation Laws and the Adaptive Greedy AlgorithmTextbook

Chapter 5 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), presents the achievable region methodology of Tsoucas, Bertsimas and Niño-Mora, Glazebrook and Garbe, and Dacre, Glazebrook and Niño-Mora: instead of arguing about policies, one argues about the set of performance vectors they can produce.…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningOperations Research+1·Captain: naimengye

Introduction to Multi-Armed Bandits XI: Bandits and Agents, Incentivized Exploration via Hidden ExplorationTextbook

A recommendation system learns from the users it serves: the diner who tries a restaurant produces the review the next diner reads. Each user would rather exploit what is already known than explore for the benefit of those who come later, so a population of self-interested agents under-explores, and an alternative that looks bad on sparse early evidence may…

10 thms3 active usersReviewed
🏆Completed
Machine 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
Complexity TheoryQuantum Information·Captain: iris

Gap-Agnostic Ground-State Preparation via Quantum BanditsResearch Paper

Preparing the ground state (the lowest-energy eigenvector) of a Hamiltonian HHH is a basic task in quantum simulation, quantum chemistry and condensed-matter physics. In full generality it is hard: deciding the ground energy of local Hamiltonians to inverse-polynomial precision is QMA-complete (Kitaev–Shen–Vyalyi 2002). Efficient algorithms therefore assume…

52 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningProbability·Captain: iris

Calibeating Bandit AdviceResearch Paper

Many sequential decision systems already run a recommendation algorithm: a pricing heuristic, a statistical model trained on private data, a Q-learning agent. A downstream learner who receives its advice in each round may want two things at once. First, the learner should never regret having followed the advice blindly: whatever consistent re-mapping of the…

33 thms2 active usersReviewed
ProbabilityStatistics·Captain: iris

Minimum-Mean Testing under Metric Constraints:Shared Information, Certificates, and AdaptivityResearch Paper

Many verification tasks ask whether every one of kkk noisy quantities clears a threshold: a batch passes inspection only if every component meets its specification, and an update is deployed only if every task benefits. When the quantities are known to be related, one observation carries evidence about several possible failures at once. Chaomeng Chen and…

85 thms2 active usersReviewed
Machine Learning·Captain: iris

Online Learning with Ordered Experts (via Two-point Feedback)Research Paper

Many online decisions choose a point on an ordered scale: a posted price, a threshold, an inventory level. When a class of experts recommends such points, the learner would like to compete with the best expert while paying for only a few loss evaluations per round. Zuo (Online Learning with Ordered Experts (via Two-point Feedback), STOC 2027 submission)…

40 thms2 active usersReviewed
Machine LearningOperations Research·Captain: iris

Decoupling Corruption and Horizon in Robust Contextual PricingResearch Paper

In dynamic pricing a seller repeatedly posts a price to an arriving buyer and learns only whether the buyer bought. In the contextual version, each buyer comes with an observable feature vector, and the buyer's valuation is a fixed but unknown linear function of it. The seller must learn that linear function from yes/no answers while losing as little…

15 thms2 active usersReviewed
Machine LearningOperations Research·Captain: iris

Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared RandomnessResearch Paper

Consider mmm devices sharing KKK wireless channels. In each time slot every device transmits on one channel, two devices on the same channel both fail, channel qualities change arbitrarily, and a device learns only what it transmitted itself. A device that transmitted nothing cannot tell a bad channel from a collision. This is the multiplayer bandit problem…

43 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: iris

Relaxed Indexability and Index Policy for Partially Observable Restless Bandits: Relaxed Indexability Is Equivalent to a Passive-Time Inequality, and the Approximate Whittle Index Has a Closed FormResearch Paper

A restless multi-armed bandit has NNN arms, each a Markov chain that keeps evolving whether or not it is used; in every slot a decision maker activates some of the arms and collects rewards from them. Channel selection in wireless networks, machine maintenance, target tracking and patient monitoring are of this form. Finding an optimal policy is PSPACE-hard…

14 thms2 active usersReviewed
Operations ResearchStochastic Systems·Captain: iris

Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems: Under DAM.FE the Time-Averaged Weighted Queue Length Is O(K²(log N + K)L_check/ε³ + K·min(T,T₀)²/(εT))Research Paper

Many service systems match a set of agents with work to a set of servers in every time slot: devices sharing radio channels in cognitive radio, workers and tasks on an online service platform, customers and providers in a marketplace. When the matching is computed centrally and the service rates are known, the MaxWeight policy, which in every slot serves a…

22 thms2 active usersReviewed
Operations ResearchProbabilityRevenue Management and Pricing·Captain: iris

Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information: The Stochastic Approximation Policy SAP(α, β) Has Worst-Case Regret O(log T)Research Paper

A retailer choosing which products to display, a platform choosing which items to recommend, and a broadcaster choosing which content to stream all face an assortment problem: offer a set of products, observe what customers buy, and earn the revenue of the purchased item. The standard demand model is the multinomial logit (MNL) model, under which the…

17 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

Weak Signal Asymptotics for Sequentially Randomized Experiments: Sample Paths of Lipschitz Sequentially Randomized Markov Experiments Converge Weakly to the Unique Diffusion Limit (3.1)Research Paper

Sequential experiments choose which treatment to try next from the outcomes seen so far. Multi-armed bandit algorithms such as Thompson sampling, tempered greedy rules and Luce's rule are the standard examples, and they are used in clinical trials, online platforms and adaptive A/B testing. Their behaviour is usually studied either in the large-signal…

14 thms2 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: iris

A Simple and Optimal Policy Design with Safety Against Heavy-Tailed Risk for Stochastic Bandits: SE and UCB Have O(KTln⁡T)O(\sqrt{KT\ln T})O(KTlnT​) Regret and an e−Ω(x/KT)e^{-\Omega(x/\sqrt{KT})}e−Ω(x/KT​) Regret TailResearch Paper

Stochastic multi-armed bandit policies are judged almost always by their expected regret. In operations settings such as dynamic pricing, assortment testing or clinical allocation, a decision maker also cares about the probability of a bad outcome: a policy whose regret is small on average can still incur regret linear in the horizon TTT with non-negligible…

21 thms2 active usersReviewed
Machine LearningOperations Research·Captain: iris

Shrinking the Upper Confidence Bound: A Dynamic Product Selection Problem for Urban Warehouses: ConsUCB Has Regret at Most K + αK + 10α√(dKT log(KT)) with Probability at Least 1 − δResearch Paper

An online retailer choosing which low-demand products to display, and to stock in its urban warehouses, faces an unusual learning problem. Thousands of products must be chosen at once, the selection can change only a few times per season, and sales data arrive only for the products that were offered. Jin, Simchi-Levi, Wang, Wang and Yang (arXiv:1903.07844v2)…

19 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Offline Planning and Online Learning Under Recovering Rewards: the purely periodic policy of Algorithm 2 earns at least γ_K·UB_R[K]·T − O(N)Research Paper

In many recommendation and promotion settings the reward of showing an item depends on how long it has been since the item was last shown: a promoted product in a live-streaming session, a notification, a piece of content whose appeal recovers while it rests. Bandits with recovering rewards model this. Kleinberg and Immorlica (FOCS 2018) studied recharging…

23 thms2 active usersReviewed
Graph TheoryMachine LearningProbability·Captain: iris

Small-Loss Bounds for Online Learning with Partial Information: Double-Threshold Freezing has ϵ\epsilonϵ-approximate regret ≤300α(A(d,T)+3log⁡d+2δ)/ϵ2\le 300\alpha(A(d,T)+3\log\frac{d+2}{\delta})/\epsilon^2≤300α(A(d,T)+3logδd+2​)/ϵ2 w.p. 1−δ1-\delta1−δResearch Paper

In adversarial online learning a learner chooses one of ddd actions (arms) in each of TTT rounds and suffers a loss in [0,1][0,1][0,1]. Classical regret bounds grow with the horizon, O(Tlog⁡d)O(\sqrt{T\log d})O(Tlogd​). A small-loss bound replaces TTT by the loss L⋆L^\starL⋆ of the best arm, which matters whenever good actions exist: routing traffic, choosing treatments, recommending items.…

12 thms2 active usersReviewed
Information TheoryMachine Learning·Captain: iris

Satisficing in Time-Sensitive Bandit Learning: Every Policy's Discounted Satisficing Regret Is at Most Γ(A~,ψ) I(A~;θ)/(1−α2)\sqrt{\Gamma(\tilde A,\psi)\,I(\tilde A;\theta)/(1-\alpha^2)}Γ(A~,ψ)I(A~;θ)/(1−α2)​Research Paper

Bayesian bandit algorithms such as Thompson sampling are analyzed through the information ratio: the squared expected shortfall of a period divided by the information the period's observation reveals about the optimal action A∗A^*A∗ (Russo & Van Roy 2016). That analysis bounds regret by Γ H(A∗) T\sqrt{\Gamma\, H(A^*)\, T}ΓH(A∗)T​, where H(A∗)H(A^*)H(A∗) is the entropy of the optimal…

18 thms2 active usersReviewed
Machine LearningReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XI: Generalized UCB Has Regret Controlled by the Eluder DimensionTextbook

A structured bandit is a repeated decision problem in which a learner picks a decision πt\pi^tπt from a set Π\PiΠ and observes a noisy reward. The set Π\PiΠ can be large or continuous: a dosage, a price vector, a path in a graph. Treating each decision separately costs regret of order ∣Π∣T\sqrt{|\Pi|T}∣Π∣T​, which is useless when Π\PiΠ is large relative to the horizon TTT. The…

22 thms2 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XV: A Family Embedding the Multi-Armed Bandit Forces the Constrained DEC to Be ≳ αTextbook

In interactive decision making a learner repeatedly picks a decision π\piπ from a decision space Π\PiΠ, receives a reward and an observation drawn from an unknown model M⋆M^\starM⋆, and is judged by its regret against the best decision of M⋆M^\starM⋆. Foster and Rakhlin's lecture notes (arXiv:2312.16730) organize the whole theory around one complexity measure, the Decis…

14 thms2 active usersReviewed
PreviousPage 6 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