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
Markov ChainOperations Research·Captain: mikedeng1

Analysis and Algorithms for Service Parts Supply Chains II: The Single-Unit Single-Customer DecompositionTextbook

A base-stock (order-up-to) policy orders, in every period, exactly enough to bring the inventory position (stock on hand plus stock on order minus backorders) up to a target level. It is the policy used in practice for repairable and consumable service parts, and the analysis of every later chapter of Muckstadt's book assumes it. Its optimality is therefore…

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

Analysis and Algorithms for Service Parts Supply Chains I: Optimality of Order-Up-To Policies by Dynamic ProgrammingTextbook

A stocking point that reviews its inventory once per period and must decide how much to order is the basic unit of every service parts supply chain: each warehouse, each repair depot and each forward location in the networks studied later in Muckstadt's Analysis and Algorithms for Service Parts Supply Chains (Springer 2005, DOI 10.1007/b138879) faces this…

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

Computing Optimal (s, S) Inventory Policies III: Selecting an (s, S) Policy That Is Optimal for Every Starting StockResearch Paper

The periodic-review inventory model with a fixed ordering cost is one of the basic models of operations research. When every order incurs a set-up cost KKK in addition to holding and shortage costs, the optimal replenishment rule over an infinite horizon is, under standard convexity assumptions, a stationary (s,S)(s, S)(s,S) policy: whenever the stock falls below the…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies II: Bounds on the Optimal s and S of the n-Period Model from the One-Period CostResearch Paper

The (s,S)(s, S)(s,S) policy is the standard ordering rule for a single stocked item with a fixed charge per order: when the stock position falls below a reorder point sss, order up to a level SSS; otherwise order nothing. Scarf (1960) proved that when the expected one-period cost is convex, some (s,S)(s, S)(s,S) policy is optimal in every period of a finite-horizon model with…

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

Markov Decision Processes XIX: Theory of Optimal Stopping ProblemsTextbook

A gambler watching a sequence unfold has to decide, at each moment and knowing only the past, whether to take what is on the table or wait for something better. That is the whole of optimal stopping, and it is one of the few problems in stochastic control with a clean and completely general answer: the value of the problem is the smallest superharmonic…

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

Markov Decision Processes XV: Optimal Play in Red-and-Black and the Gittins IndexTextbook

Chapter 7's abstract machinery — contracting Markov Decision Models, the Structure Theorem, value iteration with an explicit convergence rate — earns its keep by solving concrete problems. Section 7.6 works through four kinds of application: a return to the classical cash-balance inventory problem, now over an infinite horizon; the "red-and-black" gambling…

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

Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook

Real investors do not merely accumulate wealth for a single terminal payoff; they consume along the way, and the market they invest in is rarely a single fixed statistical regime for years at a time — bull and bear markets, business cycles, and volatility regimes shift the distribution of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…

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

Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook

The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem 2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence of function classes IMn\mathrm{IM}_nIMn​ and decision-rule classes Δn\Delta_nΔn​ closed…

14 thms3 active usersReviewed
🏆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
🏆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
🏆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
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) I: Backward Induction and Optimal PoliciesTextbook

Inventory replenishment, equipment replacement, and resource allocation require decisions whose consequences continue beyond the current period. A choice can earn an immediate reward and change the distribution of future opportunities. Comparing only immediate rewards therefore does not generally identify a good policy. A finite-horizon Markov decision…

8 thms2 active usersReviewed
PreviousPage 6 of 10Next

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