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

Markov Decision Processes (Puterman) II: Markov Policies Preserve Reward CriteriaTextbook

A controller making repeated decisions can remember every state visited and every action taken. The resulting policy class is much larger than the class of rules that use only the current state and time. In applications modeled by Markov decision processes, understanding whether that extra memory changes achievable expected rewards determines which policy…

6 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Demand Shaping Through Bundling and Product Configuration: A Dynamic Multiproduct Inventory-Pricing Model: Under Bundle-to-Stock, the Optimal Policy Is Dictated by a No-Order SetResearch Paper

Firms that sell configurable products — computers, cable and phone packages, meal combos — decide not only how much to stock but also which bundles of components to offer and at what prices. Bundling decisions interact with inventory: offering a bundle draws on several items at once, and an overstocked item is a reason to push the bundles that use it. Song…

8 thms2 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

Analytical Solution to a Discrete-Time Model for Dynamic Learning and Decision Making: the two-action frontier difference equations have a unique closed-form solution with explicit det YResearch Paper

Many sequential decisions trade off immediate reward against information: a firm prices without knowing which demand regime it faces, a clinician treats without knowing a patient's type, a bandit player pulls a risky arm to learn its mean. Formally these are partially observed Markov decision problems (POMDPs) with a hidden but fixed state. Their value…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

On the Learning Benefits of Resource Flexibility: At the Break-Even Cost of Flexibility, the Flexible System Is More Profitable Below a Profit-Margin Threshold and Less Profitable Above ItResearch Paper

A firm that sells several products must decide, before demand is known, how much capacity to build. It can build dedicated capacity, one resource per product, or a single flexible resource that can serve any product but costs more per unit. The classical argument for flexibility is risk pooling: one pooled resource absorbs the fluctuations of several…

10 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Sequential Product Development and Introduction by Cash-Constrained Start-Ups: the Startup's Optimal Launch and Development Strategy Below the Established Firm's Deferral ThresholdResearch Paper

Firms that develop technology in generations face a recurring choice: sell the product they already have, or hold it back while the next generation is developed. Selling it earns revenue now, but once the advanced product arrives, the earlier product cannibalizes part of its market. An established firm makes this choice by weighing development risk against…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems: The Dynamic Program over Great-Looking States Finds a Testing Scheme Within Factor 1 + O(ε) of OptimalResearch Paper

A series system works only if every one of its components works. Deciding whether it works by inspecting components one at a time, in the order that minimizes the expected inspection cost, is the classic sequential testing problem for series systems (Mitten 1960; Butterworth 1972; Simon & Kadane 1975). It is solved by sorting the components by the ratio …

16 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Increasing Biomanufacturing Yield with Bleed–Feed: Optimal Policies and Insights: Optimal Bleed–Feed Policies Have a Three-Way Control-Limit StructureResearch Paper

Biopharmaceuticals such as vaccines and therapeutic proteins are produced by living cells grown in a bioreactor. In a batch fermentation the cells multiply until the medium is depleted and the culture enters a stationary phase, after which the batch is harvested. A bleed–feed operation removes part of the culture and replaces it with fresh medium,…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Dynamic Appointment Scheduling of Base and Surge Capacity: The First-Available Policy Is Optimal When Surge Capacity Is Cheap Relative to the Discounted Cost of Delaying an AppointmentResearch Paper

Many service providers are paid under a contract that makes them responsible for a customer's costly failures over a fixed window: a hospital penalized for heart-failure readmissions within 30 days, or a maintenance contractor responsible for engine replacements. A preventative appointment lowers the chance of such a failure, and the sooner it takes place…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Managing Operations of a Hog Farm Facing Volatile Markets: Optimality of the Price-Dependent Multi-Threshold Hold-Fulfill-Sell Sales Allocation PolicyResearch Paper

A hog producer selling to both a meatpacker and an open market faces a weekly allocation choice. The meatpacker contracts for a fixed quantity, pays different rates for underweight and regular-weight hogs, and charges for any shortfall. The open market has separate prices for the two weight classes. Holding an underweight hog costs money now but makes it…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Profit or Growth? Dynamic Order Allocation in a Hybrid Workforce: The Variance of the Cross-Network Effect Decides Whether Market Thickness Benefits or Costs the SystemResearch Paper

Many firms that run their own delivery or service workforce have started to operate a hybrid workforce: salaried employees serve part of the demand, while a crowd of independent freelancers on a platform owned by the same firm serves the rest. A firm in this position faces a recurring allocation question. Every order sent to the platform pays freelancers…

10 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Asset Selling Under Debt Obligations: Under a Single Debt Payment Due Before the Horizon Ends, the Optimal First Sale Follows a Control Band of Two Critical PricesResearch Paper

Firms that hold a large, divisible asset (a commodity inventory, a block of shares, a stock of natural gas) often financed it with debt and must sell it over time to repay that debt. Without debt, the timing problem is classical: Karlin (1962) showed that a non-divisible asset facing independent prices should be sold the first time the price exceeds a…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Social Responsibility Auditing in Supply Chain Networks: An Optimal Auditing Policy First Audits and Drops Suppliers, Then Rectifies All Remaining Ones or Proceeds to ProductionResearch Paper

A buyer may be liable for social responsibility violations among suppliers that remain in its production network. Auditing can prevent a later penalty, but the buyer must pay for each audit and then choose what to do with a supplier that fails. Dropping a supplier can also remove other firms that depend on it, changing the buyer's eventual production…

4 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Shipping Consolidation Across Two Warehouses with Delivery Deadline and Expedited Options for E-commerce and Omni-channel Retailers: The Single-Warehouse Optimal Policy Is a Slack-Time ThresholdResearch Paper

Online and omni-channel retailers promise delivery within a fixed number of days, and carriers charge less for slower service. A retailer that receives orders over time can therefore wait, collect several orders into one package, and send it by a slower and cheaper service, as long as no order misses its promised date. Waiting saves the fixed cost of a…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Online Allocation and Pricing: Constant Regret via Bellman Inequalities: Regret Is at Most the Information Loss Plus the Bellman LossResearch Paper

An online allocator must commit to an action after each arrival, although later arrivals can change which actions would have been best. Revenue management and online resource allocation use regret to measure the expected reward lost against a benchmark. If the benchmark sees too much future information, this gap can grow with the horizon even when the…

9 thms2 active usersReviewed
🏆Completed
AnalysisControl TheoryOperations Research·Captain: mikedeng1

Wait Time Based Pricing for Queues with Customer-Chosen Service Times: The Delay Differential Optimality Equations Have a Decreasing Concave SolutionResearch Paper

Service systems such as public fast-charging stations for electric vehicles let each customer choose how long to be served. Lin, Shang and Sun (SSRN 3709573, 2020; later in Management Science, doi:10.1287/mnsc.2022.4474) study a firm that announces to every arriving customer the current wait time www (the work already in the queue) and a price rate ppp per unit…

19 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationReinforcement Learning·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 4: Safe Accelerated Value Iteration Converges to v* at Rate O(λ′^s) for Every λ′ ∈ [λ, 1)Research Paper

Value iteration (VI) is the standard method for computing the optimal value function of a discounted Markov decision process (MDP). It applies the Bellman operator repeatedly, and because that operator is a λ\lambdaλ-contraction in the sup norm, the error after sss steps is at most λs\lambda^sλs times the initial error. When the discount factor λ\lambdaλ is close to 111…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationReinforcement Learning·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 3: On the n-State Chain MDP, Every First-Order Method Has ‖v_s − v*‖∞ ≥ λ^s/(1+λ) for s = 1, …, n − 1Research Paper

Value iteration (VI) is the basic algorithm for computing the optimal value function of a discounted Markov decision process (MDP). Its error contracts by the discount factor λ\lambdaλ per step, so it needs on the order of (1−λ)−1log⁡(1/ϵ)(1-\lambda)^{-1}\log(1/\epsilon)(1−λ)−1log(1/ϵ) iterations, which is slow when λ\lambdaλ is close to 111, the regime of interest in long-horizon planning and…

10 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

A Dynamic Model for Managing Volunteer Engagement I: The Bellman Equation of the Drift-Rate Control Problem Has a SolutionResearch Paper

Non-profit organizations depend on volunteers whose availability they cannot schedule. They can only influence it, through recruiting drives, reminders and recognition events. Ata, Tongarlak, Lee and Field (arXiv:2312.02920) model a food-recovery non-profit's volunteer pool as a queueing network. Repeat volunteers rest between shifts, one-time volunteers…

17 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchProbability·Captain: mikedeng1

A Dynamic Model for Managing Volunteer Engagement II: The Bellman Solution in Closed Form Between Consecutive Engagement ThresholdsResearch Paper

Non-profit organizations such as food banks run on volunteer labour. Volunteers sign up for shifts, wait on a sign-up list, work, rest, and may or may not return; the organization can spend money on engagement activities (reminders, recognition events, recruitment drives) that raise the rate at which volunteers come back or arrive. Spending too little…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multi-Product Dynamic Pricing with Reference Effects Under Logit Demand 5: When Consumers Ignore Gains (c_i⁻ ≥ c_i⁺ = 0) the Optimal Pricing Policy Admits a Steady StateResearch Paper

Consumers judge a price against a reference price, an internal standard formed from the prices they have seen before. A price above the reference is perceived as a loss and a price below it as a gain. When gains and losses weigh differently, the seller's current price shapes tomorrow's demand, and dynamic pricing becomes a sequential decision problem. A…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multi-Product Dynamic Pricing with Reference Effects Under Logit Demand 2: The Myopic Policy Loses at Most β(1−α)ωp_H/((1−αβ)(1−β)) Against the Optimal Discounted RevenueResearch Paper

Consumers judge a price against a reference price, an internal benchmark formed from the prices they have seen before. A price below the reference is perceived as a gain and raises demand; a price above it is perceived as a loss and lowers demand. Because today's price moves tomorrow's reference price, a seller who maximises the revenue of each period…

6 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

Robust Markov Decision Processes: Beyond Rectangularity 2: With Polyhedral r-Rectangular Factor Sets, One Deterministic Policy and Factor Matrix Stay Robust-Optimal for All Discount Factors Near 1Research Paper

A Markov decision process (MDP) models sequential decisions under uncertainty: in each state a decision maker picks an action, collects a reward, and the system moves to a random next state according to a transition kernel. In applications the kernel is estimated from data, and an optimal policy for the estimated kernel can perform poorly under a slightly…

7 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

Robust Markov Decision Processes: Beyond Rectangularity 1: Under r-Rectangular Factor Uncertainty, Robust Value Iteration Converges to the Optimal Worst-Case Value, Attained by a Deterministic PolicyResearch Paper

A Markov decision process (MDP) is optimized for a transition kernel that, in practice, is estimated from data, and the optimal policy for the estimated kernel can perform poorly under small perturbations of it. The robust MDP approach replaces the single kernel by an uncertainty set of kernels and asks for the policy with the best worst-case expected…

12 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

Robust Markov Decision Processes 1: Over s-Rectangular Ambiguity Sets, Robust Policy Improvement Is Solved by a Stationary Randomized Policy and the Fixed Point of the Robust Bellman MapResearch Paper

A Markov decision process (MDP) is evaluated with a transition kernel that, in practice, is estimated from data. The expected total reward of a policy can be very sensitive to small errors in that estimate (Mannor, Simester, Sun and Tsitsiklis, 2007). Robust MDPs address this by letting the kernel range over an ambiguity set and optimizing the worst-case…

14 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities 2: Setwise-Continuous Observations Do Not Make the Belief Transition Weakly ContinuousResearch Paper

A partially observable Markov decision process describes a controlled system whose state is hidden but whose observations are available to a decision maker. The distribution of the hidden state conditional on the observations is the belief state. Replacing the hidden state by this distribution turns the model into a fully observed decision process, provided…

6 thms2 active usersReviewed
PreviousPage 7 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