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
Algorithmic Game TheoryMarkov ChainOperations Research·Captain: mikedeng1

Markovian Decision Processes with Uncertain Transition Probabilities I: The Max-Min Policy-Iteration Algorithm Terminates at a Max-Min Optimal Pure Stationary PolicyResearch Paper

Howard's finite Markovian decision process (MDP) models a controller who, at each instant, observes the state of a system, chooses a decision, collects a reward and moves to a random next state with known transition probabilities. Howard's policy-iteration algorithm computes an optimal policy, and the model has been applied to inventory control, equipment…

12 thms4 active usersReviewed
🏆Completed
Control TheoryOperations ResearchProbability·Captain: Shuze Chen

Dynamic Programming and Optimal Control V: LQG and Certainty EquivalenceTextbook

The separation theorem — certainty equivalence for linear-quadratic control with imperfect state information — is one of the celebrated structural results of stochastic control: the optimal controller splits into a least-squares estimator and the deterministic LQR actuator, designed independently. It underlies every LQG autopilot and Kalman-filter-based…

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

Markov Decision Processes with Applications to Finance VI: With Proportional Transaction Costs the Optimal Portfolio Has Buy, Hold and Sell Regions Given by ConesTextbook

In frictionless discrete-time portfolio models the investor rebalances freely, and with a homogeneous utility the optimal policy keeps a constant fraction of wealth in the stock. Real trading is costly: every purchase or sale of stock pays a fee proportional to the traded amount. A constant-fraction policy then trades every period and pays the fee every…

34 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Markov Decision Processes with Applications to Finance II: In Convex Markov Decision Models the Convex Functions in Bb+\mathbb{B}_b^+Bb+​ Satisfy the Structure AssumptionTextbook

In a finite-horizon Markov decision problem the value functions VnV_nVn​ are computed backwards by the Bellman equation Vn=TnVn+1V_n = T_nV_{n+1}Vn​=Tn​Vn+1​. Bäuerle and Rieder (Springer 2011) organize the general theory around one hypothesis, the Structure Assumption (SAN)(\mathrm{SA}_N)(SAN​): if a class of functions IMn\mathbb{IM}_nIMn​ is stable under the maximal reward operator TnT_nTn​ and every…

15 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationReinforcement Learning·Captain: iris

On the Convex Formulations of Robust Markov Decision Processes: The Fixed Point of the Entropy-Regularized Robust Bellman Operator Is log_b of the Unique Optimum of a Convex ProgramResearch Paper

A Markov decision process (MDP) models sequential decisions under uncertainty: in each state an agent picks an action, collects a reward and moves to a random next state. Its optimal value function is the fixed point of the Bellman operator, and since the 1960s it has also been the optimum of a linear program over value functions (Puterman, Markov Decision…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Distributionally Robust Markov Decision Processes: S-robust strategies are distributionally optimal and admit a saddle pointResearch Paper

A planner who controls a stochastic system often knows more than a range of possible transition probabilities, but less than a complete probability distribution for those probabilities. For example, a small confidence region may contain a parameter with probability at least 90%, while a larger region contains it with certainty. Optimizing against every…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Revenue Management with Repeated Customer Interactions: the myopic policy earns at least a (1 − γ) fraction of the optimal revenue under bang-per-buck heterogeneity γResearch Paper

Network revenue management studies how a platform with limited supply should allocate products to customers at given prices. Most of the literature treats each interaction as one-shot: a request arrives, is served or rejected, and leaves. Examples are the fluid models of Gallego and van Ryzin (1997) and the bid-price controls of Talluri and van Ryzin (1998).…

13 thms3 active usersReviewed
🏆Completed
Control TheoryOperations Research·Captain: mikedeng1

Driving Supply to Marketplaces: Optimal Platform Pricing When Suppliers Share Inventory: The Supplier Shares Its n-th Unit Exactly When the Time-to-Go Is at Most a Threshold tₙResearch Paper

Online marketplaces such as Zalando, Amazon or Farfetch let brands sell through the platform's storefront in addition to their own stores. One common arrangement is inventory sharing: the brand keeps ownership of its stock, but makes it visible to the platform's customers, and pays the platform a commission on every unit the platform sells. For a supplier…

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

Time Consistency of the Mean-Risk Problem: The Upper Images of the Dynamic Mean-Risk Problem Satisfy a Set-Valued Bellman RecursionResearch Paper

Markowitz's mean-variance problem trades off the expected terminal wealth of a portfolio against its risk. Over several periods the scalarized form of this problem is time inconsistent: a strategy that is optimal today for a fixed risk-aversion parameter is generally no longer optimal tomorrow for the same parameter, so the investor would deviate from her…

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

On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand I: The Approximation APT Bounds the Expected Cost-to-Go from Below and Above and Is Exact in the Last PeriodResearch Paper

Retailers and restaurants increasingly deliver orders from their own stores within an hour or less. Orders arrive throughout the day, a fixed pool of drivers is based at the store, and in each dispatch wave the operator must decide how many drivers to send out now and along which routes. Sending many drivers now gives short delivery times for the current…

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

Multi-Product Dynamic Pricing with Reference Effects Under Logit Demand 1: Without Gain-Seeking Products the Myopic Price Path Converges to a Steady State; with One the Myopic Policy Has NoneResearch Paper

Consumers judge a price against a reference price, an internal benchmark formed from the prices they have seen before. A price above the reference is perceived as a loss and depresses demand; a price below it is perceived as a gain and stimulates it. Because today's prices shape tomorrow's reference prices, a seller facing reference effects solves a dynamic…

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

Coordinating Inventory Control and Pricing Strategies for Perishable Products 2: With Zero Lead Time and Minimal Disposal, Two Myopic Solutions Bound the Optimal Order-Up-To LevelResearch Paper

Food, blood products, pharmaceuticals and many retail goods are perishable: a unit is usable for a fixed number of periods and is then discarded. A seller of such a product decides every period how much to order, what price to charge, and how much stock to deplete or dispose of. Because units of different ages coexist, the state of the system is a vector of…

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

The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation: Error Bound for Least-Squares Policy Iteration with LookaheadResearch Paper

Approximate policy iteration is the template behind most practical reinforcement-learning systems for large state spaces: alternate between choosing a policy that looks good under the current value estimate and estimating the value of that policy, with errors in both steps. Game-playing systems such as AlphaZero add two ingredients to this template: a…

19 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Markov Decision Processes with Observation Costs: Framework and Computation with a Penalty Scheme: The Quasi-Variational Inequality with Inspection Operator Has a Unique Bounded SolutionResearch Paper

In many sequential decision problems the state of a system is not observed for free. A controller monitoring a machine, a patient or an inventory must pay to inspect it, and between inspections it acts on a belief rather than on the state. The observation cost model (OCM) makes this precise for a finite Markov chain: at each time the controller either pays…

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

Coordinating Inventory Control and Pricing Strategies for Perishable Products 1: With Backlogging, the Profit-to-Go Is L♮-Concave and the Optimal Policy Is Monotone with Bounded SensitivityResearch Paper

Food, blood and pharmaceuticals are perishable: a unit not sold within its lifetime is thrown away. A seller decides each period how much to order, which price to charge, and whether to dispose of stock early. A large stock of old units argues for a lower price and a smaller order.

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs 2: Under τ-Admissible Random Node Selection, Cuts Become Exact Almost Surely at Every Tree NodeResearch Paper

Stochastic dual dynamic programming (SDDP) and its relatives are the standard algorithms for multistage stochastic programs: hydro-thermal scheduling, energy storage and long-horizon capacity planning are solved with them in industry. They approximate each future cost function from below by a maximum of affine cuts, compute new cuts only at a few randomly…

16 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On Solving Multistage Stochastic Programs with Coherent Risk Measures: The Inner-Approximation Policy's Nested Risk-Adjusted Cost Is at Most the Upper Bound yResearch Paper

Multistage stochastic linear programs model decisions taken over time under uncertainty: reservoir releases in hydro-thermal scheduling, production and inventory plans, capacity expansion. Their standard solution method, stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991), approximates each stage's cost-to-go function from below by cutting…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs 1: Deterministic Cutting-Plane Bellman Approximations Become Exact Along the Generated TrajectoriesResearch Paper

Multistage stochastic programs model sequential decisions under uncertainty: hydro-thermal scheduling, inventory and capacity planning, portfolio management. The dominant solution methods, Stochastic Dual Dynamic Programming (SDDP, Pereira and Pinto 1991) and its relatives CUPPS and DOASA, never compute the Bellman (future-cost) functions of the problem.…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

The Bayesian Prophet: A Low-Regret Framework for Online Decision Making: Constant Regret of the Fluid Bayes Selector for the Multi-Secretary ProblemResearch Paper

In online allocation, requests arrive one at a time and each must be accepted or rejected on arrival, using a limited budget of resources. Revenue management, ad allocation and hiring all fit this pattern. A natural benchmark for an online policy is the prophet, or Offline: the decision maker who sees the whole arrival sequence in advance and acts optimally…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Robust Markov Decision Processes 2: The Affine Reward-to-Go Semidefinite Program Is Exact for One Quadratic Constraint and Conservative for SeveralResearch Paper

A Markov decision process (MDP) evaluates a policy by its expected discounted reward, which requires the transition probabilities. In practice these are estimated from data, and the optimal policy of the estimated model can perform badly under the true kernel. Robust MDPs replace the kernel by an ambiguity set of kernels and judge a policy by its worst-case…

17 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Dynamic Type Matching: Under the Modified Monge Condition There Is an Optimal Matching Policy That Respects the Priority Relation ≻MsResearch Paper

Many platforms match two sides of a market over time: ride-hailing platforms match riders with drivers, blood banks match donated units with patients, organ allocation matches donors with recipients, and retailers pool inventory across fulfilment centres to serve orders from several regions. Demand and supply arrive in several types (locations, blood…

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

Dynamic Pricing with Loss-Averse Consumers and Peak-End Anchoring: Every Optimal Price Path Converges Monotonically to a Steady State Set by the Initial Minimum PriceResearch Paper

Firms that change prices over time face customers who remember past prices. A large empirical literature in marketing documents reference price effects: demand depends not only on the current price but on how that price compares with a price the customer expects, and losses (prices above the reference) weigh more than gains of the same size, the loss…

14 thms3 active usersReviewed
🏆Completed
OptimizationReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 2: Under Closure, a (c, µ)-Gradient-Dominated Policy Iteration Objective Makes ℓ (κc/(1−γ), κµ/(1−γ))-Gradient DominatedResearch Paper

Policy gradient methods optimize a parameterized control policy by gradient descent on its long-run cost. They underlie much of modern reinforcement learning, from REINFORCE and actor-critic methods to trust-region and proximal policy optimization, and they are used in operations problems such as inventory control and optimal stopping. Their objective is…

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

On the Sample Complexity of Reinforcement Learning III: Non-Stationary Approximate Policy Iteration Is Within 2T Times the Regression Error Averaged over Any Competitor's State-Time DistributionTextbook

Approximate dynamic programming replaces the exact value functions of a Markov decision process by approximations, typically produced by a regression algorithm. The classical guarantees for the resulting policies are stated in the max norm: if every state-action value is estimated to within ε\varepsilonε uniformly over the state space, the greedy policy loses…

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

On the Sample Complexity of Reinforcement Learning V: Exact Conservative Policy Iteration Improves at Every Update and Halts within 8H²/ε² Updates with Future Advantages at Most ε/HTextbook

Policy iteration replaces the current policy by the greedy policy with respect to its state-action values. With exact values this improves the policy at every state. When the improvement step is only approximate, or is restricted to a class of policies, a greedy replacement can make the policy worse, and the resulting error bounds are stated in max norm…

18 thms3 active usersReviewed
PreviousPage 3 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