Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Dynamic Programming

347 missions · 248 completed

Missions

Open99Completed248All347
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper

An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock)…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper

Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0C_0C0​ units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…

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

On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper

In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an (s,S)(s,S)(s,S) policy is optimal in every period of a finite-horizon problem: order up to SSS when the stock falls below sss,…

17 thms3 active users
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 3: Stationary Policies Suffice and the Stationary/Time-Varying Uncertainty Gap Vanishes GeometricallyResearch Paper

A Markov decision process (MDP) is controlled with transition probabilities estimated from data, and optimal policies computed for the estimated model can perform badly when the estimates are off. Robust MDPs replace the single transition model by a set of models and optimize the worst case over that set. Two readings of "the set" are possible. In the statio…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTopology·Captain: mikedeng1

The Structure of Dynamic Programing Models: A Solution of the Principle of Optimality with Vanishing Tail Is the Optimal ReturnResearch Paper

Dynamic programming, as introduced by Bellman in the early 1950s, solves sequential decision problems through a functional equation: the value of a problem started in a given state equals the best one-stage return plus the value of the problem started in the state that decision leads to. In practice the argument usually runs backwards. One writes down the…

8 thms3 active users
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

The Steiner Problem in Graphs: Algorithm A Computes the Length of the Steiner TreeResearch Paper

The Steiner problem in graphs asks for the cheapest way to connect a prescribed set of nodes of a network, where intermediate nodes may be used freely. It is the network version of the classical Euclidean Steiner tree problem surveyed by Gilbert and Pollak (SIAM J. Appl. Math. 16, 1968), and it arises wherever a few sites must be joined through an existing…

10 thms3 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Monotone Mappings with Application in Dynamic Programming II: Convergence of the DP Algorithm under Uniform DecreaseResearch Paper

Infinite-horizon sequential decision problems (deterministic optimal control, Markov decision processes, minimax control) share one computational question: does the dynamic programming (DP) algorithm, which starts from a terminal cost and repeatedly applies the Bellman operator, converge to the optimal cost? For discounted problems with bounded costs the…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Asymptotic Optimality of Tailored Base-Surge Policies in Dual-Sourcing Inventory Systems: Asymptotic Optimality of the Best TBS Policy for Long Lead TimesResearch Paper

Firms that can buy the same item from two suppliers, a cheap slow one and a fast expensive one, face the dual-sourcing inventory problem: how much to order from each source in every period when demand is random and unmet demand is backlogged. Global sourcing (offshore regular supply plus a near-shore express supply) is the standard example (Allon and Van…

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

Markovian Decision Processes with Uncertain Transition Probabilities II: Max-Max and Max-Min Optimal Returns Bound the Bayesian Optimal ReturnResearch Paper

A Markovian decision process (Howard, 1960) models a controller who, in each of finitely many states, picks a decision, earns a reward and moves to a random next state according to known transition probabilities. In applications (inventory control, equipment replacement, quality control) those probabilities are estimated, not known. Satia and Lave (Operation…

7 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Markov-Renewal Programming. I: Formulation, Finite Return Models: Policy Iteration Finds an Optimal Stationary Policy for the Discounted Infinite-Horizon Markov-Renewal ProgramResearch Paper

Many operational systems move between a finite number of states at random times: a machine alternates between working and repair, a queue between occupancy levels, an inventory between stock positions. When the time spent in a state is not exponential and not a fixed period, neither discrete-time Markov decision processes nor continuous-time Markov chains…

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

Coherent Multiperiod Risk Adjusted Values and Bellman's Principle: Stability of the Test Probabilities Is Equivalent to Bellman's PrincipleResearch Paper

A coherent risk measure assigns to a future financial position the smallest amount of capital that makes it acceptable to a supervisor. Artzner, Delbaen, Eber and Heath characterised the one-period version: every coherent risk measure has the form π(X)=inf⁡Q∈PEQ[X]\pi(X)=\inf_{\mathbb Q\in\mathcal P}\mathbb E_{\mathbb Q}[X]π(X)=infQ∈P​EQ​[X] for a set P\mathcal PP of test probabilities (ADEH…

12 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations 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
Operations ResearchProbability·Captain: naimengye

Markov Decision Processes III: The Average Reward Optimality Equation for Unichain ModelsTextbook

When a system is controlled indefinitely and decisions are frequent — a router admitting packets, a queue accepting jobs, a machine being maintained — discounting future rewards is often unjustified, and what matters is the long-run average reward per period. Puterman's Chapter 8 (doi:10.1002/9780470316887) develops the theory of this criterion, and its…

5 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Dynamic Programming and Optimal Control VII: Infinite Horizon ProblemsTextbook

Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic…

8 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with kkk-SUM in 2DResearch Paper

In ddd-Knapsack (the vector or multidimensional knapsack problem) every item has a profit and a ddd-dimensional weight vector, and one must choose a set of items of maximum total profit whose total weight stays within a capacity in every coordinate. It models any selection problem with several budgets at once (money, time, space, staff) and is the simplest…

21 thms2 active usersReviewed
Complexity TheoryOperations ResearchOptimization·Captain: iris

Multi-Selection Pandora's Box with Nonobligatory Inspection: A PTAS and a Structural SeparationResearch Paper

Pandora's box is a basic model of costly search. Weitzman (1979) showed that a simple index policy is optimal when a box must be opened before its prize can be selected. In many settings a searcher may select an option without inspecting it: a firm may hire a candidate on their record alone. This gives Pandora's box with nonobligatory inspection (PNOI). The…

107 thms2 active usersReviewed
Control TheoryProbabilityStochastic Systems·Captain: iris

Markov Decision Processes with Applications to Finance XIII: Piecewise Deterministic Markov Decision Processes Have Optimal Nonrelaxed Markov PoliciesTextbook

Many controlled systems move deterministically between random shocks: an insurer's reserve between claims, a portfolio between market jumps, a production line between breakdowns. Piecewise Deterministic Markov Processes, introduced by Davis (Piecewise-deterministic Markov processes, JRSS B, 1984), are the general class of such non-diffusions. Their control…

21 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms2 active usersReviewed
Linear OptimizationOperations Research·Captain: iris

Self-Adapting Network Relaxations for Weakly Coupled Markov Decision Processes: Every Feasibility Network Relaxation Bound Lies Between the Optimal Value and the Lagrangian BoundResearch Paper

Many sequential decision problems in operations research consist of a number of independent subsystems that interact only through shared resources: assortment and inventory decisions under a common budget, multi-armed bandits with a cap on the number of arms pulled, scheduling with capacity limits. Such problems are modelled as weakly coupled Markov…

14 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: iris

Technical Note—Revenue Management with Calendar-Aware and Dependent Demands: Asymptotically Tight Fluid Approximations: The Fluid-LP Policy Is 1/(4L)-Approximate and Asymptotically OptimalResearch Paper

Revenue management systems forecast demand over canonical intervals of time, such as a week, often with a general distribution for each week, and the demand of one week is a signal for the next. The prevalent demand model, a discrete-time approximation to a Poisson process, cannot reproduce this. With one arrival per period, arrival probabilities λt\lambda_tλt​ a…

22 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Pricing for the Stars: Dynamic Pricing in the Presence of Rating Systems: rating sensitivity raises long-run profits and ratings, and raises prices and lowers consumer surplus exactly when κ < 1/2Research Paper

Online marketplaces such as Amazon and Steam show each product's aggregate rating, a summary of past reviews, next to its current price. Reviews are left by buyers, and who buys depends on the price, so a seller who changes the price today changes the reviews that tomorrow's rating is made of. Platforms also choose how the rating is computed; in recent…

8 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMarkov 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
Linear OptimizationOperations ResearchProbability·Captain: iris

Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations: The Optimal Online Policy's Expected Regret Grows at Least Logarithmically in the HorizonResearch Paper

In an online linear program, customers arrive one at a time and a firm must accept or reject each one at once, spending a shared inventory of mmm resources. The model covers network revenue management, ad allocation and order fulfilment (Li and Ye, 2022). Its central performance measure is the regret: the gap between what an omniscient planner collects and…

25 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: iris

Robust Online Selection with Uncertain Offer Acceptance: The Best Robust Ratio Equals the Value of an Explicit Linear Program, and Its Optimal Solutions Give Optimal PoliciesResearch Paper

In the classical secretary problem a decision maker sees candidates in random order, learns only how each compares with those already seen, and must decide irrevocably whether to hire. Many real selection processes add one more source of uncertainty: the chosen candidate may refuse. Job offers are declined, customers ignore promotions, admitted students…

14 thms2 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Minimization Fractional Prophet Inequalities for Sequential Procurement: With In-House Production the Competitive Ratio Is Exactly (1 + (n−1)/ℓ^{1/(p−1)})^{p−1}Research Paper

A firm that must buy a fixed quantity of a commodity often faces suppliers one at a time: a quote arrives, the firm decides how much to buy at that price, and the decision cannot be revisited. Electricity procurement, cloud capacity and spot markets for raw materials all have this shape. When the marginal cost of buying grows with the amount bought from one…

10 thms2 active usersReviewed
PreviousPage 8 of 14Next

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