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

Discrete Dynamic Programming 2: A Stationary Policy Is Nearly Optimal as the Discount Factor Tends to 1 Exactly When It Maximizes x(g) and, Among Those, y(g)Research Paper

A finite Markov decision problem with discounting is solved by Howard's policy improvement routine: start from a stationary policy, switch to actions that do better against its value, repeat. When the discount factor β\betaβ tends to 111 the total discounted income typically diverges, and the natural targets become the long-run average income and, among…

11 thms3 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete Dynamic Programming 1: Every Finite Markov Decision Problem Has a Stationary Policy That Is Optimal for All Discount Factors Sufficiently Near 1Research Paper

A Markov decision problem models a system that is observed once per period and controlled by choosing an action: the action earns an immediate income and determines the probabilities of the next state. Inventory control, machine replacement, queue admission and many reinforcement-learning benchmarks are of this form. With future income discounted by a…

11 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction IX: Average Reward and the Futility of Discounting in Continuing ProblemsTextbook

Reinforcement learning formulates control as maximizing reward accumulated over time. For continuing tasks, where interaction never terminates, the standard textbook objective is the discounted return with a discount rate γ<1\gamma < 1γ<1. Chapter 10 of Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018), argues that once values…

11 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion: With Finite Storage a Modified Base-Stock Policy Is Strongly Average-Cost OptimalResearch Paper

A manufacturer that makes one product to stock faces random demand, can produce at most bbb units per period, and can store at most UUU units. The classical result without the production limit is that a base-stock policy is optimal: raise inventory to a fixed level yˉ\bar yyˉ​ each period. With a production limit, the natural modification is to produce up to yˉ\bar yyˉ​ w…

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

Reinforcement Learning: An Introduction IV: Policy Iteration for ε-Soft PoliciesTextbook

Policy iteration alternates two steps: evaluate the current policy, then replace it by a policy that is greedy with respect to the evaluated action values. The policy improvement theorem guarantees that each greedy step does not make the policy worse, and that the process stops only at an optimal policy. When the action values are estimated from experience…

11 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction III: The Policy Improvement Theorem and Policy IterationTextbook

Reinforcement learning methods search for good behaviour by alternating two activities: estimating how good the current behaviour is, and changing the behaviour in the direction those estimates suggest. Sutton and Barto call this pattern generalized policy iteration and use it as the organizing idea of their textbook (Sutton & Barto 2018, §4.6). Its…

9 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction II: The Bellman Optimality Equation and the Existence of an Optimal PolicyTextbook

Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) is the standard introductory text of the field. Its Chapter 3 sets up the model that the rest of Part I works in: the finite Markov decision process (MDP), the value functions of a policy, and the Bellman equations that relate the value of a state to the values of its…

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

An Analysis of Bid-Price Controls for Network Revenue Management II: Bid-Price Controls Are Not Optimal in GeneralResearch Paper

Airlines, hotels and other capacity-constrained sellers decide, request by request, whether to sell a unit of a perishable resource now or hold it for a more valuable request later. In an airline network an itinerary uses seats on several flight legs at once, so the decision couples the legs. Bid-price controls are a widely used practical answer: each leg…

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

An Analysis of Bid-Price Controls for Network Revenue Management I: The Fixed-Bid-Price Heuristic Is Asymptotically OptimalResearch Paper

Airlines, hotels and rental-car firms sell a fixed, perishable capacity to customers who arrive over time and pay different prices. In an airline network, one ticket for an origin–destination itinerary consumes seats on several flight legs at once, so accepting a cheap connecting passenger today can displace a more valuable request tomorrow on any of those…

12 thms3 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Dynamic Pricing Strategies with Reference Effects II: A Myopic Firm Underprices and Its Prices Converge MonotonicallyResearch Paper

Consumers judge a price against a reference price, an internal expectation formed from the prices they have seen before. A price below the reference feels like a gain and raises demand, a price above it feels like a loss and lowers demand. Because today's price moves tomorrow's reference price, a firm facing such consumers solves a dynamic problem even when…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Bellman's Dynamic Programming VIII: Multi-Stage Games, Games of Survival and the Extended Min-Max TheoremTextbook

Chapter X of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) carries the functional-equation method of the earlier chapters from one-player decision processes to two-player zero-sum games that are played over many stages. At each stage the two players make simultaneous…

9 thms3 active usersReviewed
🏆Completed
Calculus of VariationsControl TheoryNumerical Analysis+2·Captain: mikedeng1

Bellman's Dynamic Programming VII: Convergence of Discrete Approximations in the Calculus of VariationsTextbook

Chapter IX of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) recasts problems of the calculus of variations with constraints as dynamic programming processes. A variational problem with an inequality constraint on the control, such as 0≤y≤x0 \le y \le x0≤y≤x, is awkward for the…

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

Stochastic Dynamic Programming and the Control of Queueing Systems X: Average Cost Optimization of Continuous Time Markov Decision ChainsTextbook

Many queueing systems evolve in continuous time: customers arrive according to a Poisson process, services take exponentially distributed times, and a controller may change the service rate, admit or reject customers, or route them whenever the state changes. Minimizing the long-run average cost of such a system is a standard problem in the control of…

11 thms3 active users
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems VIII: Computing Average Cost Optimal Policies by Approximating SequencesTextbook

Control problems for queueing systems (admission control, service rate control, routing to parallel servers) are naturally modelled as Markov decision chains whose state is a vector of queue lengths. The state space is therefore denumerably infinite, and the performance measure of interest is usually the long-run average cost per slot. For such models the…

14 thms3 active users
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems IV: Average Cost Optimal Stationary Policies Exist for Finite State SpacesTextbook

Controlled queues, inventories and communication links are run for a long time, and the quantity an operator usually cares about is the long-run average cost per period rather than a discounted total. The average cost criterion is harder to work with than the discounted one: its value is a lim sup⁡\limsuplimsup of Cesàro means, it is not given by a contraction, and for…

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

Stochastic Dynamic Programming and the Control of Queueing Systems II: The Discount Optimality EquationTextbook

Control problems for queueing systems (admission control, routing, service rate selection, inventory replenishment) are naturally modelled as Markov decision chains with a countable state space, such as the number of customers in a buffer, and with costs that grow without bound in the state, such as holding costs proportional to queue length. The expected…

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

Stochastic Dynamic Programming and the Control of Queueing Systems I: Finite Horizon Optimality and Approximating SequencesTextbook

Controlled queueing systems (admission control, routing, service-rate selection) are naturally modelled as Markov decision chains whose state is a buffer content and therefore ranges over a countably infinite set. Linn Sennott's Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, DOI 10.1002/9780470317037) develops the dynamic…

14 thms3 active usersReviewed
🏆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
PreviousPage 7 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