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
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

On the Optimal Dividend Problem for a Spectrally Negative Lévy Process I: Optimality of the Barrier Strategy at c* in the Classical Dividend ProblemResearch Paper

An insurance company's surplus grows with premiums and falls with claims. In the Cramér–Lundberg model with a positive safety loading, the surplus drifts to +∞+\infty+∞ with probability one. De Finetti (1957) objected that a company does not accumulate capital indefinitely: surplus above some level is paid out to shareholders. He proposed choosing the payout…

2,308 thms12 active usersReviewed
🏆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
Linear OptimizationOperations Research·Captain: iris

On the Strength of Relaxations of Weakly Coupled Stochastic Dynamic Programs: State-Independent, Totally Unimodular Linking Constraints Make the Lagrangian and ALP Upper Bounds EqualResearch Paper

Many sequential decision problems in operations research consist of a large number of otherwise independent subproblems that interact only through a few resource constraints in each period: arms of a restless bandit sharing a budget of activations, legs of an airline network sharing seat inventories, servers sharing a matching budget. These are weakly…

18 thms6 active usersReviewed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs: A Variable-Rate Queue Has an Average Cost Optimal Stationary Policy Whenever λ < max aβResearch Paper

Controlled queues are the standard testing ground for Markov decision processes with infinitely many states: the state is a queue length, which is unbounded, and the holding cost grows with it. The classical theory of the average cost criterion (Ross, Applied Probability Models with Optimization Applications, 1970) produces an optimal stationary policy only…

27 thms6 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
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance IX: Multiperiod Indifference Prices under Exponential Utility Are Given by a Backward RecursionTextbook

In a complete market every contingent claim has one arbitrage-free price, the cost of replicating it. When part of the risk sits in an asset that cannot be traded, replication fails and arbitrage arguments leave an interval of prices. Indifference pricing selects a price from the seller's preferences: the price at which an investor with a given utility…

31 thms5 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance I: Under the Structure Assumption the Value Functions Solve the Bellman Equation and Every Sequence of Maximizers Is an Optimal PolicyTextbook

Sequential decisions under uncertainty appear in inventory control, portfolio choice, consumption planning and optimal stopping. The common model is the Markov Decision Model: a controller observes a state, picks an action, collects a reward, and the system moves at random to a new state. The standard solution method, backward induction, goes back to…

29 thms5 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
Control TheoryMarkov ChainStochastic Systems·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 3: Discrete-Time Equilibria Exist on an Infinite Horizon for Closed Convex Admissible Transition RowsResearch Paper

In many dynamic decision problems the criterion an agent uses today is not the one it will use tomorrow. The standard example is non-exponential discounting: if a payoff received ttt periods from now is weighted by δ(t)\delta(t)δ(t) and δ\deltaδ is not geometric, then the plan that is optimal from today's point of view will be abandoned by the agent's future selves.…

11 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
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Bandit Processes and Dynamic Allocation Indices: A Policy Is Optimal If and Only If It Almost Surely Continues a Bandit Process of Maximal Dynamic Allocation IndexResearch Paper

The multi-armed bandit problem asks how to share effort sequentially among several independent projects, each of which evolves only while it is worked on. It models the scheduling of jobs on a single machine, the order in which to explore candidate sites, sequential clinical trials and the allocation of research effort among competing projects. Before 1972…

8 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
PreviousPage 1 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