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
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
Operations ResearchOptimization·Captain: Shuze Chen

Online Learning and Optimization for Revenue Management Problems with Add-on Discounts: Regret bound for UCB-Add-OnResearch Paper

Retailers sometimes offer a discount on a game only after a customer buys a console. Such add-on discounts let the customer choose individual additional products while the retailer controls both the original prices and the conditional offers. A retailer with limited transaction history must learn purchase probabilities while choosing these prices. Offering…

9 thms2 active usersReviewed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Robust Dynamic Assortment Optimization in the Presence of Outlier Customers: Active Elimination Has TOTE Regret O(ε̄K²T log T + (K²√ε̄ + √K)√(NT log³T) + K²N log²T) Under ε-ContaminationResearch Paper

A retailer that learns customer preferences online, for example an e-commerce platform choosing which products to display, observes purchases that are not all generated by the population it is trying to learn. Some arrivals are bots, fraudulent accounts or atypical buyers, and their choices can be arbitrary or deliberately misleading. Standard learning…

10 thms2 active usersReviewed
Machine LearningOperations Research·Captain: mikedeng1

Hedging the Drift: Learning to Optimize under Non-Stationarity: the Bandit-over-Bandit algorithm has dynamic regret Õ(d^{2/3}B_T^{1/3}T^{2/3} + d^{1/2}T^{3/4}) without knowing B_TResearch Paper

Many sequential decision problems in operations research are learned online while the environment changes: demand responds to prices differently from week to week, click-through rates drift, and the value of an action in a recommendation or auto-loan pricing system decays as conditions move. The stochastic linear bandit is the standard model for such…

10 thms2 active usersReviewed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Optimal Search and Discovery: Always Taking the Action with the Largest Purchase, Search or Discovery Value Is an Optimal PolicyResearch Paper

In the standard model of costly sequential search, a consumer knows from the start which products exist and pays to learn how much each is worth. Weitzman (Econometrica 1979) solved this problem with a single number per product, the reservation value: inspect in decreasing order of reservation values, and stop as soon as the best product found is worth more…

9 thms2 active usersReviewed
Linear algebraMachine LearningProbability·Captain: mikedeng1

The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Sampling: For Any Prior and Noise, E[Σ Aₜᵀ Γₜ Aₜ] ≤ 2 max(σ², 1) log det(I + T Γ₁)Research Paper

In a linear bandit problem, a learner chooses a vector and observes a noisy scalar response that carries information about an unknown parameter. Regret analyses often need to control the sum of the learner's uncertainty in the directions it chooses. The familiar elliptical potential lemma does this when uncertainty is represented by the inverse of a…

7 thms2 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: Shuze Chen

Multi-armed Bandit Allocation Indices VIII: Index Theorems for Non-Preemptive Jobs under Precedence Constraints and Out-ForestsTextbook

Scheduling jobs on a single machine under precedence constraints ("job iii must be completed before job jjj may be started") is one of the oldest problems of operations research, and with random service times and discounted rewards it is a family of alternative bandit processes that is not simple: the set of jobs that may be served changes as jobs are…

7 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Balancing Optimal Large Deviations in Ranking and Selection: The BOLD Allocation Learns the Large Deviations Optimality Conditions With Probability OneResearch Paper

Ranking and selection asks which of MMM simulated alternatives has the largest mean, when each simulation run returns one noisy sample and the simulation budget is limited. A large literature allocates the budget using the large-deviations analysis of Glynn and Juneja (2004): for a static allocation in which alternative xxx receives a fixed fraction αx\alpha_xαx​ of…

10 thms2 active usersReviewed
Machine LearningOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 4: Arm Elimination with Graph Feedback and Cross Learning Has Regret Õ(T ∧ √(αMT) ∧ √(KT)) with High ProbabilityResearch Paper

In many sequential decision problems, playing one action reveals the outcome of other actions too. A bidder in a first-price auction who bids bbb and sees the winning price learns whether every bid at or above that price would have won. A recommender that shows one item learns something about related items. Two kinds of side information recur. Graph feedback a…

8 thms2 active usersReviewed
Harmonic AnalysisMachine LearningOperations Research+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 1: Regret Upper Bound for the Two-Stage Period-Estimation and Confidence-Bound PolicyResearch Paper

Many demand, traffic and click-through series are seasonal: their mean repeats after a fixed number of periods (a week of days, a year of months), while the length of that cycle is not known in advance. A retailer choosing among KKK promotions, or a platform choosing among KKK recommendations, then faces a multi-armed bandit whose arms have time-varying but…

17 thms2 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data: The G-MCP-Bandit Algorithm Has Expected Cumulative Regret at Most Rmax(T0 + |K|) + C log(T + 1)Research Paper

Personalized decisions — which drug to prescribe, which product to recommend, which price to quote — are made one user at a time, from user features observed on arrival, and the effect of each decision is learned only from the users it was applied to. This is the contextual (covariate) bandit. In electronic records and online platforms the feature vector is…

10 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Learning Unknown Service Rates in Queues 2: Q-UCB Has Queue-Regret at Most 6K v_u(t) log² t / t + (24.004 + UK)/(6t²) in the Late StageResearch Paper

Many service systems must match jobs to servers whose quality is not known in advance: crowdsourcing platforms routing tasks to worker types, wireless schedulers assigning users to channels, and switches in data networks. The scheduler learns server quality only by trying servers, and every poor assignment lets work pile up. The natural performance measure…

12 thms2 active usersReviewed
Machine LearningProbabilityReinforcement Learning·Captain: mikedeng1

(More) Efficient Reinforcement Learning via Posterior Sampling: PSRL Has Bayesian Regret O(τS√(AT log(SAT))) in Episodic Finite MDPsResearch Paper

An agent that interacts repeatedly with an unknown Markov decision process must trade exploration against exploitation. The dominant design principle for provably efficient reinforcement learning has been optimism in the face of uncertainty: UCRL2 (Jaksch, Ortner & Auer, 2010) and REGAL (Bartlett & Tewari, 2009) build confidence sets around the unknown…

14 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability: FALCON+ Has Regret ≤ 14.3·Σₘ√(K𝓔(τₘ₋₁−τₘ₋₂))(τₘ−τₘ₋₁) + τ₁ + √(8T log(2/δ)) w.p. 1−δResearch Paper

A contextual bandit is a sequential decision problem: in each round a learner sees a context (a user's features, a patient's covariates), picks one of KKK actions, and observes the reward of that action only. Applications include recommendation, dynamic pricing and adaptive clinical decisions. The difficulty is statistical and computational at once: the…

14 thms2 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Personalized Dynamic Pricing with Machine Learning: High-Dimensional Features and Heterogeneous Elasticity 2: Under Unknown Sparsity, Lasso-Based ILQX Pricing Has Regret at Most Cs√T(log d + log T)Research Paper

Online sellers of loans, insurance, travel and retail goods observe data about each arriving customer before quoting a price. Using that data to price individually is attractive only if the seller can learn, from its own sales, how demand responds to price for customers with given characteristics. Two features make this hard in practice. The number of…

6 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 1: In the Well-Separated Case, Algorithm-I with m Price Changes Has Regret at Most KT^(1/(m+1))Research Paper

Retailers set prices and stock levels without knowing how demand responds to price. They must learn the demand curve from their own sales while still earning money, which is the exploration–exploitation trade-off of dynamic pricing with learning (den Boer 2015). Two features of practice make the problem harder than the textbook bandit. First, demand is…

10 thms2 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Personalized Dynamic Pricing with Machine Learning: High-Dimensional Features and Heterogeneous Elasticity 1: Under Known Sparsity, ILSX Pricing Has Regret at Most Cs√T log TResearch Paper

A seller who changes prices while learning demand faces two costs: a price experiment may earn less revenue now, while insufficient experimentation leaves later prices poorly calibrated. Customer features make the balance harder because both willingness to buy and sensitivity to price may vary between customers. Ban and Keskin study this problem when the…

6 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

The Multi-Armed Bandit Problem with Covariates I: Successive Elimination Has Expected Regret at Most 392γ²(1 + n/T)(K/Δ)log(TΔ²/18γ²) + nΔ⁻ Under a Random HorizonResearch Paper

In a multi-armed bandit, a decision maker repeatedly chooses an arm, observes a reward, and tries to learn which arm has the highest average reward while losing little reward during learning. A policy that requires the number of future pulls in advance cannot be used unchanged when stopping time is uncertain. Perchet and Rigollet study successive elimination…

10 thms2 active usersReviewed
Machine Learning·Captain: mikedeng1

An Optimal Algorithm for Stochastic and Adversarial Bandits III: α-Tsallis-INF With Gap-Tuned Asymmetric Regularization Has Logarithmic Pseudo-Regret When the Best Arm Is UniqueResearch Paper

In the multi-armed bandit problem a learner repeatedly chooses one of KKK 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 ∑i≠i∗log⁡(T)/Δi\sum_{i\ne i^*}\log(T)/\Delta_i∑i=i∗​log(T)/Δi​, where …

14 thms2 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Linearly Parameterized Bandits 4: For Finitely Many Arms, the Uncertainty Ellipsoid Policy Has Regret at Most a₆|U|‖z‖ + a₇|U| Σᵤ min{log T/Δᵘ(z), TΔᵘ(z)}Research Paper

In a linearly parameterized bandit, the expected rewards of many arms are driven by a small number of unknown parameters. Each arm is a vector u∈Rru \in \mathbb R^ru∈Rr, and its expected reward is the inner product u′Zu'Zu′Z with an unknown parameter vector ZZZ. Problems of this kind arise in marketing and revenue management, where each product is described by rrr features…

12 thms2 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Linearly Parameterized Bandits 1: On the Unit Sphere with a Gaussian Prior, Every Policy Has Bayes Risk at Least 0.006·r√TResearch Paper

In a linearly parameterized bandit, a decision maker repeatedly chooses an arm uuu from a set Ur⊂Rr\mathcal U_r \subset \mathbb R^rUr​⊂Rr and observes a noisy reward whose mean is the inner product u′Zu'Zu′Z with an unknown parameter vector ZZZ. The model covers pricing, assortment and recommendation problems in which arms are described by feature vectors and the number of arms…

7 thms2 active usersReviewed
PreviousPage 3 of 4Next

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