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 · 247 completed

Missions

Open100Completed247All347
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 1: For a Reversible Policy Chain, Accelerated Value Computation Converges at Rate 1 − √((1−λ)/(1+λ)) + η for Every η > 0Research Paper

Value iteration is the standard method for solving a discounted Markov decision process (MDP), and its policy-evaluation variant, value computation (VC), computes the value of a fixed policy by iterating an affine contraction. Both converge geometrically at rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to one, as in long-horizon…

18 thms7 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case III: Monotone Increase Models — Accumulation Points of DP-Optimal Controls Give an Optimal Stationary PolicyTextbook

Infinite-horizon dynamic programming with positive (nonnegative) costs and no discounting, or with discount factors that do not make the Bellman operator a contraction, is the setting of Blackwell's and Strauch's positive and negative programming models and of many deterministic control and reachability problems. In this regime the classical contraction…

21 thms6 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance VII: The Multiperiod Mean-Variance Problem Has an Explicit Efficient Frontier and Optimal PortfolioTextbook

Mean-variance portfolio selection, introduced by Markowitz in 1952 (and slightly earlier by de Finetti), measures the risk of a portfolio by the variance of its return: among all portfolios that reach at least a prescribed expected return, choose one of smallest variance. The single-period problem was solved in the 1950s and is still the standard tool of…

12 thms5 active usersReviewed
🏆Completed
Control TheoryOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance III: The Stochastic Linear-Quadratic Problem Has Quadratic Value Functions and Linear Optimal Controls Given by a Riccati RecursionTextbook

A linear-quadratic (LQ) problem asks for a control that keeps a linear stochastic system close to zero at quadratic cost. It is the one model of sequential decision making under uncertainty with general Euclidean state and action spaces whose optimal value and optimal policy are known in closed form, which is why it serves as the reference model of control…

19 thms5 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XIV: UCB-VI Has Regret ≲HSATlog⁡(SAHT/δ)\lesssim HS\sqrt{AT\log(SAHT/\delta)}≲HSATlog(SAHT/δ)​ When All Optimal Values Lie in [0,1][0,1][0,1]Textbook

Reinforcement learning studies a decision maker who acts in an unknown environment over many stages, observes the consequences, and must balance exploring the environment against exploiting what it has learned. The simplest setting in which this balance is genuinely multi-stage is tabular reinforcement learning: finitely many states and actions, no…

13 thms5 active usersReviewed
🏆Completed
EconomicsMarkov ChainOperations Research·Captain: mikedeng1

An Analysis of “Buy X, Get One Free” Reward Programs: Without Transaction Utility, a Redemption Threshold Alone Cannot Raise the Firm's Long-Run Profit Above max{λqv, λ(v − v̄)}Research Paper

"Buy XXX, get one free" (BXGO) programs are among the most common loyalty schemes: coffee shops, car washes, golf courses and hotel chains hand out a free unit after a fixed number of paid purchases. A long empirical literature documents that such programs change behaviour, most visibly through point pressure, the acceleration of purchases as a customer…

19 thms5 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 2: For a Reversible Policy Chain, Momentum Value Computation Converges at Rate (1 − √(1/κ))/(1 + √(1/κ)) + η for Every η > 0Research Paper

Value iteration and its policy-evaluation special case, value computation, are the basic algorithms of dynamic programming for Markov decision processes (MDPs). Both are fixed-point iterations of a λ\lambdaλ-contraction, so they converge at the geometric rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to 111, which is the regime of long effective…

13 thms5 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

Optimality of (s, S) Policies in Inventory Models with Markovian Demand I: With Markov-Modulated Demand and Fixed Ordering Costs, a State-Dependent (s, S) Policy Is Optimal over a Finite HorizonResearch Paper

Single-item inventory theory asks how much stock to order each period when the order carries a fixed cost KKK on top of a per-unit cost and demand is random. With independent, identically distributed demand, Scarf (1960) showed that the optimal finite-horizon policy has the (s,S)(s,S)(s,S) form: when the stock falls below the reorder point sss, order up to the level SSS;…

20 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Analysis of Stochastic Dual Dynamic Programming Method: SDDP with Independently Subsampled Scenarios Finds an Optimal Policy of the SAA Problem in Finitely Many Iterations Almost SurelyResearch Paper

Multistage stochastic linear programs model sequential decisions under uncertainty: capacity and reservoir planning, hydro-thermal scheduling, inventory and asset–liability management. When the data process is stagewise independent, the problem decomposes by dynamic programming into one linear program per stage, coupled through expected cost-to-go functions.…

14 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Inventory Policies for Assembly Systems Under Random Demands 2: If an Item and Its Predecessors Have Negative Discounted Echelon Holding Cost, the Minimal Cost Is Unbounded BelowResearch Paper

Assembly systems — components purchased from outside, assembled into subassemblies, and those into an end product facing random customer demand — are the standard model of material requirements planning under uncertainty. Rosling's paper (Oper. Res. 37(4), 1989) shows that, under a cost assumption, the optimal policies of such a system are those of an…

17 thms5 active users
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Stable Function Approximation in Dynamic Programming II: In a Nondiscounted MDP with All Policies Proper, Value Iteration Through a Self-Weighted Averager ConvergesResearch Paper

Value iteration solves a Markov decision process by repeatedly applying the Bellman backup to a table of state values. When the state space is too large for a table, the values are stored in a function approximator instead: each backup is followed by a fit, and the fitted function is backed up again. This approximate value iteration is the basis of fitted…

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

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 1: The Optimal Policy Offers Only Nondominated Sets, a Larger One the More Capacity and the Less Time RemainResearch Paper

A seller with one limited inventory pool can choose which fare products to show in each selling period. When customers choose among the displayed products, showing another fare can both add sales and divert buyers from a more expensive fare. A fixed ranking of fares therefore does not by itself tell the seller which products to offer. Talluri and van…

10 thms5 active usersReviewed
🏆Completed
Linear OptimizationMarkov ChainOperations Research·Captain: mikedeng1

Linear Programming and Sequential Decisions: An Optimal Solution of the Equilibrium LP Yields a Stationary Decision Rule of Least Expected Monthly CostResearch Paper

Alan S. Manne's Linear Programming and Sequential Decisions (Management Science 6(3), 1960, pp. 259–267) is the first formulation of an infinite-horizon, average-cost sequential decision problem as a linear program. The illustration is a single-item inventory problem, but the construction, with unknowns indexed by a state and a decision and constraints…

13 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Probabilistic Production and Inventory Problem: The Optimal Discounted Cost Is the Greatest Point of the Constraint Set (9) and the Unique Optimum of the Linear Program (P2)Research Paper

A Markov decision process with finitely many states and actions and a discounted cost criterion can be solved in three classical ways: policy iteration, value iteration, and linear programming. The third goes back to F. d'Epenoux's paper A Probabilistic Production and Inventory Problem (Management Science 10(1), 1963, partly redrafted from a translation of…

10 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 1: Additive Demand: k-Concave Profit-to-Go, Optimal (s, S, p) PolicyResearch Paper

A retailer that sets both its replenishment quantities and its prices over a finite selling season faces a coupled decision: the price shapes the demand that the inventory must serve, and the inventory position shapes which price is worth charging. With a fixed cost per order, the classical inventory answer is the (s, S) policy of Scarf (1960): when the…

11 thms5 active usersReviewed
🏆Completed
Control TheoryLinear algebraMarkov Chain+2·Captain: mikedeng1

Bellman's Dynamic Programming IX: Markovian Decision Processes and the Maximal Perron RootTextbook

Chapter XI of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; DOI 10.2307/j.ctv1nxcw0f) studies decision processes whose state is a vector of nonnegative quantities, for example the probabilities that a system is in each of NNN states, or the stocks of NNN commodities, and whose transitions are linear maps chosen stage by stage by a…

13 thms5 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: Shuze Chen

Dynamic Programming and Optimal Control IV: LQR and the Riccati EquationTextbook

The discrete-time Riccati equation is the central object of linear-quadratic optimal control — the design equation behind LQR/LQG controllers in every modern control stack. Proposition 4.4.1 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005, §4.1) packages its asymptotic theory: under controllability and observability the Riccati…

9 thms5 active usersReviewed
🏆Completed
Control TheoryOptimization·Captain: Shuze Chen

Dynamic Programming and Optimal Control III: The Minimum PrincipleTextbook

The Pontryagin Minimum (Maximum) Principle is the fundamental necessary condition of optimal control, in continuous use since 1956 across aerospace guidance, robotics, and mathematical economics. Chapter 3 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops it from the dynamic programming side: the HJB sufficiency theorem…

18 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance VIII: The Binomial Mean-Risk Problem with Average-Value-at-Risk Has an Explicit Value and a Stationary Optimal PolicyTextbook

Markowitz's mean-variance criterion measures the risk of a portfolio by the variance of its terminal wealth. The variance penalizes gains and losses alike, which is one of its drawbacks as a measure of risk. The axiomatic theory of coherent risk measures (Artzner, Delbaen, Eber and Heath, 1999) replaced it in much of risk management by quantities that look…

13 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance XI: Contracting Models Satisfy Value Iteration, Have a Unique Fixed Point and an Optimal Stationary PolicyTextbook

Infinite-horizon Markov Decision Processes with discounted rewards are the standard model for sequential decisions under uncertainty in operations research, economics and finance: inventory and cash management, consumption and investment, dividend payout, replacement and maintenance. Whether the problem has a usable solution depends on two questions. Is the…

12 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchReinforcement Learning·Captain: iris

Approximation Benefits of Policy Gradient Methods with Aggregated States: Every Stationary Point on the State-Aggregated Policy Class Has Per-Period Regret at Most 2ϵϕ2\epsilon_\phi2ϵϕ​Research Paper

Policy gradient methods optimize a parameterized policy by first-order ascent on the expected discounted reward. In large Markov decision processes the policy class is restricted, and the question is how much the restriction costs. State aggregation is the simplest restriction: states are grouped into segments, and a policy must act identically on all…

31 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Cloud Cost Optimization: Model, Bounds, and Asymptotics: The Newsvendor Policy π* Has Optimality Gap at Most √θ Times the Bound (14), So It Is Asymptotically Optimal as Demand Scales by θResearch Paper

Cloud providers sell computing capacity in two ways: reserved resources, paid for every period whether used or not, and on-demand resources, rented one period at a time at a higher price. A firm that runs a stream of computing jobs with deadlines must decide how much capacity to reserve once, how much to rent each period, and which job runs on which…

48 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Markov Decision Processes (Puterman) VIII: Average Optimality for Semi-Markov ModelsTextbook

A controller may make decisions whenever a machine fails, a customer arrives, or a service finishes. The time between two decisions then depends on the state and the chosen action. Counting decisions alone does not measure elapsed operating time: a policy earning a large reward per decision may spend so long between decisions that its reward per unit time…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Assortment Optimization Under Consider-then-Choose Choice Models: the dynamic program's state space has at most min(2^N, N·2^K) subproblemsResearch Paper

Assortment optimization asks a retailer which subset of products to offer so as to maximize expected revenue, given a model of how customers choose among what is offered. A widely used class of choice models in operations management describes customers by ranked preference lists: each customer type buys the highest-ranked product on offer, or nothing (Farias…

12 thms4 active users
🏆Completed
Bandit AlgorithmsLinear OptimizationOperations Research+2·Captain: Shuze Chen

Multi-armed Bandit Allocation Indices IX: Suboptimality Bounds for Branching Bandits and Index Policies on Parallel MachinesTextbook

Gittins index policies are optimal for a single server choosing among alternative bandit processes, and the achievable region method of Bertsimas and Niño-Mora (Math. Oper. Res. 1996) explains why: when the performance vectors of a scheduling system satisfy generalized conservation laws, the region they fill is a polytope whose optimal vertex is an index…

11 thms4 active usersReviewed
PreviousPage 1 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