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
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
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
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
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
Operations ResearchProbability·Captain: iris

Markov Decision Processes with Applications to Finance XV: The Perpetual American Put Is the Smallest Superharmonic Majorant of the Payoff and Is Exercised Below a ThresholdTextbook

An American option may be exercised at any time up to its expiry, so its fair price is the value of an optimal stopping problem under the risk-neutral measure, and its optimal exercise rule is an optimal stopping time. Chapter 11 of Bäuerle and Rieder's Markov Decision Processes with Applications to Finance (Springer, 2011) treats this problem as a Markov…

26 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance V: Under Regime Switching Ordered in the Increasing Concave Order the Value Rises and Consumption Falls with the RegimeTextbook

Return distributions of risky assets are not constant over time: they shift with the business cycle, monetary policy, regulation or catastrophes. A standard way to capture this in portfolio theory is a regime-switching (Markov-modulated) market, in which an observable finite-state Markov chain, the environment process, selects the distribution of next…

33 thms4 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Risk Averse Stochastic Programming: Time Consistency and Optimal Stopping: The Nested-Risk Snell Envelope Is the Optimal Stopping Value, Attained by the First Time It Meets the RewardResearch Paper

Optimal stopping asks when to stop a reward process Z0,…,ZTZ_0,\dots,Z_TZ0​,…,ZT​ so as to make the stopped reward ZτZ_\tauZτ​ as large as possible. In its classical form the criterion is the expectation E[Zτ]\mathbb E[Z_\tau]E[Zτ​], and the solution is the Snell envelope: the value process obtained by comparing, at each date, the reward for stopping now with the conditional expectation…

22 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Frontiers in Operations: Optimal Genetic Testing of Families: A Two-Sided Threshold Rule on Untested Members' Carrier Risks Decides When to Stop TestingResearch Paper

Most conditions with reliable genetic tests are autosomal dominant: one pathogenic copy substantially raises disease risk, and a relative's result changes everyone's risk. Clinical guidelines nevertheless decide whom to test one person at a time, and none accounts explicitly for the informational value of a test to the rest of the family (Adelman & Wang 2023…

17 thms4 active usersReviewed
EconomicsMarkov ChainOperations Research·Captain: iris

General Equilibrium in a Heterogeneous-Agent Incomplete-Market Economy with Many Consumption Goods and a Risk-Free Bond: A Competitive Stationary Equilibrium ExistsResearch Paper

Heterogeneous-agent incomplete-market models are the workhorse of quantitative macroeconomics: a continuum of agents faces uninsurable income risk and self-insures by saving in a risk-free bond, and the cross-sectional wealth distribution is an equilibrium object. In the one-good model of Huggett (1993) and Aiyagari (1994) only the interest rate is…

40 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Asymptotically Optimal Lagrangian Policies for Multi-Warehouse, Multi-Store Systems with Lost Sales: the SLaBS policy's expected loss is O(√(min{M,N}·T·N·log(TN)))Research Paper

Retailers with many stores often hold a finite stock of a product in a few distribution centres and ship it to the stores over a selling season, with no replenishment of the centres themselves: seasonal goods, fashion, end-of-life products. Unmet store demand is lost. The decision is how much to send to each store in each period, from which warehouse,…

29 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality: Asymptotic optimality of feasible dynamic fluid policiesResearch Paper

Many sequential allocation problems combine numerous individually small projects with a common capacity constraint. A firm may allocate capital across investments, inventory across locations, or service opportunities across competing activities. Each local decision changes future rewards and local states. At the same time, a common observed signal can…

22 thms4 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VIII: The Infinite-Horizon Borel Models — the Optimality Equation J* = T(J*) under (P), (N), (D)Textbook

Infinite horizon dynamic programming asks for the least expected cost of controlling a stochastic system forever, and for a policy attaining it. On finite or countable state spaces the theory has been classical since Bellman, Blackwell (1965) and Strauch (1966). Many models in operations research, inventory control, queueing and economics have continuous…

23 thms4 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy JobsResearch Paper

A production planner may have many jobs competing for a small number of identical machines. Each job has a processing requirement, a due date and a penalty for missing that date. Minimizing the sum of those penalties is the weighted tardy jobs problem. Its numerical parameters matter for exact optimization: a dynamic program can depend on the largest due…

18 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Get Permanent Results Faster by Counting StarsResearch Paper

The permanent combines the entries of a square matrix by summing one product for each permutation of its columns. For a matrix containing only zeros and ones, it counts perfect matchings in the corresponding bipartite graph. Over other commutative rings, the same expression is an algebraic computation problem. Its arithmetic cost measures how many additions…

22 thms3 active usersReviewed
Operations ResearchStochastic SystemsTheoretical Computer Science·Captain: iris

Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers: A Deterministic Quasi-Polynomial-Time Algorithm Computes a (1−ϵ)(1-\epsilon)(1−ϵ)-Optimal Adaptive Service PolicyResearch Paper

Providing timely service under high capacity utilization is a central issue in stochastic systems, and customer impatience has major economic consequences in data centers, healthcare, ride-hailing and call centers (Wang, Li, Jiang, 2010). Cygan, Englert, Gupta, Mucha and Sankowski (ITCS 2013) introduced one of the structurally simplest models of it: a…

24 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Performance Guarantees for Network Revenue Management with Flexible Products: The Approximate Policy Earns at Least a 1/(1+θL)1/(1 + \theta L)1/(1+θL) Fraction of the Optimal Expected RevenueResearch Paper

Network revenue management sells the limited capacities of resources to demand that arrives over time, in air travel, hospitality, media advertising and cloud computing. A flexible product can be served by several combinations of resources, and the service provider chooses which. Airlines sell discount tickets for an origin-destination pair without fixing…

25 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: iris

On Strategic Measures and Optimality Properties in Discrete-Time Stochastic Control with Universally Measurable Policies: lower semianalytic optimal value and everywhere ε-optimal policiesResearch Paper

A discrete-time stochastic control problem (a Markov decision process, MDP) on general state and action spaces asks for a policy that minimizes some criterion of the random trajectory it generates. Once the state space is uncountable, measurability decides whether the problem is well posed at all. The optimal value may fail to be Borel measurable even when…

22 thms3 active usersReviewed
Operations ResearchProbability·Captain: iris

Distributionally Robust Markov Decision Processes and Their Connection to Risk Measures: Robust Value Iteration and Deterministic Markov Optimal Policies for Both Players on Borel SpacesResearch Paper

A Markov decision process assumes that the law of the random disturbances is known. In inventory, energy and finance models that law is estimated, and a controller who is averse to the estimation error wants a policy that performs well under every law in a set of plausible ones. This is distributionally robust control. Bäuerle and Glauner's paper Distributio…

33 thms3 active usersReviewed
Operations ResearchOptimizationRevenue Management and Pricing·Captain: iris

Dynamic Pricing with Menu Costs: Approximation Schemes and Applications to Grocery Retail: A Budget-Feasible Pricing Strategy Within 1 − ε of Optimal in Time (|I|/ε · ϱmax)^O(T) · ‖U¹‖∞^O(1)Research Paper

Grocery retailers set prices on a weekly calendar, but every price change has a cost: shelf labels must be reprinted and replaced, systems updated, staff scheduled. The economics literature calls these menu costs; for large US supermarket chains they were measured at a sizeable fraction of net margins (Levy, Bergen, Dutta, Venable, 1997), so retailers limit…

21 thms3 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Markov Decision Processes with Applications to Finance XII: The Primal and Dual Linear Programs of a Contracting Markov Decision Problem Have Equal Values and Optimal SolutionsTextbook

A discounted Markov Decision Problem asks for a policy that maximizes the expected discounted sum of rewards of a controlled Markov chain. Besides value iteration and policy iteration, the third classical way to compute such policies is linear programming: the value function is the smallest function satisfying a family of linear inequalities, and the dual…

18 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance XIV: When the One-Step Stopping Set Is Closed the One-Step-Look-Ahead Rule Is OptimalTextbook

Optimal stopping asks when to end a random process so as to maximize the expected reward. It covers house selling, the secretary problem, sequential testing and the exercise of American options. Chapter 10 of N. Bäuerle and U. Rieder, Markov Decision Processes with Applications to Finance (Springer, 2011, doi:10.1007/978-3-642-18324-9) treats these problems…

13 thms3 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: iris

Condition-Based Production for Stochastically Deteriorating Systems: Optimal Policies and Learning: The Optimal Production Rate Decreases in Deterioration, Time to Maintenance and Base RateResearch Paper

Production systems such as wind turbines and assembly equipment can often be run faster or slower, and running faster usually wears them out faster. Between scheduled maintenance visits, an operator can therefore trade revenue now against deterioration later. Condition-based production, a term coined by Uit het Broek et al. (2020), makes this trade-off…

16 thms3 active usersReviewed
PreviousPage 1 of 4Next

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