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
OptimizationReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 6: In the KL-Regularized Finite MDP, a Regularized-Optimal Policy Is Within λ(1 + log(1 + c/λ)) of OptimalResearch Paper

Policy gradient methods for Markov decision processes are frequently run on a regularized objective rather than on the cost of interest: a convex penalty on the action distribution is added to every single-period cost. Regularization smooths the problem, makes optimal policies strictly stochastic, and keeps iterates away from the boundary of the probability…

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

Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model 3: Robust Dynamic Assortments Grow with Remaining Capacity and over TimeResearch Paper

Single-leg capacity allocation under customer choice is the basic dynamic problem of revenue management: a firm holds a fixed stock of a perishable resource (seats on a flight leg, rooms on a night), and in every period of a finite selling horizon it decides which products (fare classes) to offer to the arriving customer. Talluri and van Ryzin (Management…

17 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Robust Dynamic Programming 2: The Discounted Robust Value Function Is the Unique Fixed Point of the Robust Bellman OperatorResearch Paper

Markov decision processes model sequential decisions under uncertainty, and their optimal policies are computed from transition probabilities that in practice are estimated from data. Optimal policies can be sensitive to estimation error in those probabilities. Robust dynamic programming replaces each transition law by a set of plausible laws and evaluates…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Robust Dynamic Programming 1: The Robust Bellman Recursion and Optimality of Deterministic Markov Policies in Finite HorizonResearch Paper

Markov decision processes assume that the transition law is known exactly. In practice it is estimated from data, and the optimal policy computed for the point estimate can perform badly when the true law differs. Robust dynamic programming replaces each transition law by a set of plausible laws and evaluates a policy by its worst-case expected reward over…

7 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityReinforcement Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning VI: In a Deterministic MDP an Algorithm Acts T-Step Optimally at All but NAT TimestepsTextbook

A reinforcement-learning agent that does not know its environment has to act and learn at once. Each step spent gathering information about unfamiliar states is a step not spent collecting reward, and an agent that only exploits what it already knows may never find better behaviour. Chapter 8 of Kakade's thesis (Kakade 2003) turns this trade-off into a…

14 thms2 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning IV: Advantages at Most ε/T under μ Make a Policy ε + T‖d_{π′,s₀} − μ‖₁ Close to Every Policy of the ClassTextbook

Planning in a Markov decision process with a large or infinite state space cannot visit every state. The trajectory tree method of Kearns, Mansour and Ng (2000) finds a near-best policy in a class Π\PiΠ with a number of generative-model calls independent of the state space, but exponential in the horizon TTT. Chapter 6 of S. M. Kakade's PhD thesis, On the…

10 thms2 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning II: The Gradient of the Normalized Discounted Value Is the Sum over Actions of ∇π·Q under the Discounted Future State DistributionTextbook

Policy gradient methods search a parameterized family of stochastic policies π(a∣s,θ)\pi(a\mid s,\theta)π(a∣s,θ), θ∈Rk\theta\in\mathbb R^kθ∈Rk, by following the gradient of the policy's performance. They are the standard tool when the state space is too large for tabular dynamic programming and when a compact policy class (a neural network, a linear softmax) is easier to represent…

9 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning I: Approximate Policy Iteration with Max-Norm Evaluation Error ε Is Eventually Within 2ε/(1−γ)² of OptimalTextbook

Most practical reinforcement-learning methods do not compute value functions exactly. They alternate between estimating a value function from data, usually with a parametric approximator, and acting greedily with respect to that estimate. Approximate value iteration and approximate policy iteration are the two classical schemes of this kind, and their error…

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

Algorithms for Scheduling Runway Operations Under Constrained Position Shifting 1: Dynamic Programming on the CPS Network Gives the Minimum MakespanResearch Paper

A busy runway is the bottleneck of an airport, and the order in which arriving or departing aircraft use it determines how many operations fit into an hour. Consecutive aircraft must be spaced by minimum separations that depend on both aircraft (a light aircraft behind a heavy one needs a long gap because of wake turbulence), so reordering the…

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

Algorithms for Scheduling Runway Operations Under Constrained Position Shifting 2: The Minimum Total Delay Is a Shortest Source-Sink Path in the CPS NetworkResearch Paper

Runway capacity is the binding constraint at many busy airports. An aircraft landing or taking off behind another must wait a minimum separation time that depends on the two aircraft's weight classes, because of wake vortices; the US Federal Aviation Administration publishes these spacing requirements. Reordering aircraft changes the sum of the separations…

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

Bounded-parameter Markov Decision Processes 1: The Optimistic and Pessimistic Optimal Interval Value Functions Satisfy Bellman-like EquationsResearch Paper

A Markov decision process is specified by numbers: transition probabilities and rewards. In practice these numbers are estimated from data, elicited from experts, or produced by aggregating the states of a larger model, and in each case what is actually known is a range for each parameter rather than its value. Givan, Leach and Dean (Artificial…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

On the Structure of Lost-Sales Inventory Models 3: If Demand Increases in the Convex Order, the Optimal Lost-Sales Cost f̄_t(v; φ) Is Nondecreasing in φResearch Paper

In the periodic-review inventory model with lost sales, demand that cannot be met from stock is lost rather than backordered. With a positive order lead time LLL the state of the system is a vector of length LLL: on-hand stock plus the L−1L-1L−1 orders still in the pipeline. This model is standard in retail, where a customer facing an empty shelf buys elsewhere. Its…

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

Old and New Methods for Lost-Sales Inventory Systems 1: Under Any Policy in Z(s) the State Enters X(s) and Never Leaves, So Every State Outside X(s) Is TransientResearch Paper

The lost-sales inventory system with a positive lead time is one of the basic models of inventory theory. Demand that cannot be met from stock is lost rather than backlogged, and orders arrive a fixed number LLL of periods after they are placed. Unlike the backlog system, where the inventory position is a sufficient one-dimensional state and a base-stock…

5 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

On the Structure of Lost-Sales Inventory Models 1: In the Transformed State v = J⁻¹x, the Optimal Cost Functions f̄_t(v) and ḡ_t(v, ζ) Are L♮-ConvexResearch Paper

The lost-sales inventory system is the inventory model in which demand that cannot be met from stock is lost, not backlogged. It is the natural model for retail and for any setting where a customer who finds the shelf empty buys elsewhere. With a positive order lead time it is also one of the classical hard problems of inventory theory. In the backorder…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete Dynamic Programming with Sensitive Discount Optimality Criteria 2: No Improvement of Order n+1 Implies n-Discount Optimality, Which Rules Out Improvement of Order nResearch Paper

A finite Markov decision process is usually solved under one of two criteria: the expected total discounted reward, for a fixed interest rate, or the long-run average reward. Neither is satisfactory when the interest rate is small and not known precisely. Blackwell (Blackwell 1962) showed that some stationary policy is optimal for every discount factor…

17 thms2 active usersReviewed
Machine LearningMarkov ChainProbability+1·Captain: mikedeng1

An Analysis of Temporal-Difference Learning with Function Approximation 1: Linear TD(λ) Converges with Probability 1 to the Fixed Point of ΠT^(λ), with Error ≤ ‖ΠJ* − J*‖_D/(1 − α(1−λ)/(1−αλ))Research Paper

Temporal-difference learning, TD(λ\lambdaλ), is the basic algorithm of reinforcement learning for estimating the expected discounted cost of a Markov chain from observed transitions (Sutton, 1988). On large or infinite state spaces it is run with a linear function approximator: the cost-to-go is represented as a weighted sum of KKK fixed basis functions, and…

13 thms2 active usersReviewed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

Inventory Control in a Fluctuating Demand Environment II: With a Fixed Order Cost, a World-Dependent (r, S) Policy Is Optimal and Lies within Veinott-Type BoundsResearch Paper

Demand for many products is not stationary: it rises and falls with the economy, the season, a product's life cycle or a customer's state. Song and Zipkin (1993) (DOI 10.1287/opre.41.2.351) model this by a world-driven demand process: an exogenous Markov chain AAA (the "state of the world") whose current state sets the rate of a Poisson demand stream. The…

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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 3: Dynamic Program DP3 Minimizes the Number of Tardy Equal-Length Jobs on a Batch Machine with Agreeable Release and Due DatesResearch Paper

Semiconductor burn-in tests hold several jobs in an oven at once. A production planner must decide which jobs share each oven run and in what order those runs take place. A job may become available only after earlier manufacturing steps, and a due date marks when its test should finish. The planning objective here is to minimize how many jobs finish after…

9 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case 2: The Greedy Forward Dual Solution Is Optimal and Its Value Is the Lot-Sizing CostResearch Paper

Economic lot sizing asks when to produce goods across a finite planning horizon when demand in each period is known. Producing in a period incurs a fixed setup charge and a marginal cost per unit, while goods may be produced before the period in which they are needed. Such a decision has to balance paying another setup charge against producing more units…

7 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Multi-armed Bandits and the Gittins Index: With Per-Project Horizons the Maximal M-Process Reward Is K − ∫_M^K ∏ᵢ ∂φᵢ/∂m dm and the Gittins Index Rule Attains ItResearch Paper

The multi-armed bandit problem asks how to allocate effort sequentially among NNN independent projects, only one of which can be worked on at a time, so as to maximise expected total discounted reward. It is the model behind research planning, clinical-trial allocation and job scheduling, and it is the prototypical example of a Markov decision problem whose…

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

Optimal Inventory Policies for Assembly Systems Under Random Demands 1: In Long-Run Balance, an Assembly System Has the Optimal Policies of an Equivalent Series SystemResearch Paper

An assembly system must coordinate the production of components that meet at a common downstream item. A shortage of any required component can delay the finished product, while producing a component too early incurs holding cost. In Rosling's 1989 study, the central question is whether optimal decisions for such a tree can be understood using the simpler…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete Dynamic Programming with Sensitive Discount Optimality Criteria 1: If Every Stationary Policy Is Transient, Some Stationary Policy Maximizes the Expected Total Reward over All PoliciesResearch Paper

A finite dynamic program with total reward is the basic model of sequential decision making without discounting: a system moves among finitely many states, a decision maker picks an action in each state, collects a reward, and the system moves on or stops. The quantity of interest is the expected total reward of a policy, summed over the whole (possibly…

12 thms2 active usersReviewed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Inventory Control in a Fluctuating Demand Environment III: Under Stochastic Monotonicity, the Myopic and Optimal Basestock Levels Are Nondecreasing in the World StateResearch Paper

Demand for many products does not arrive at a constant rate. It moves with an underlying environment: the economy, the season, a product's life-cycle stage, the state of a customer's own operations. Song and Zipkin (Oper. Res. 41(2):351–370, 1993) modelled this environment as a continuous-time Markov chain, the world, whose current state sets the Poisson…

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

Quality Control under Markovian Deterioration 1: A Discounted-Optimal Policy Produces, Inspects, Produces Again and Revises on Successive Intervals of the BeliefResearch Paper

A production process deteriorates over time, and the state it is in cannot be observed directly. Each period the operator chooses among three actions: produce without looking, produce and inspect the item (which reveals the current state at a cost), or revise the process back to its good state. This is one of the earliest partially observed Markov decision…

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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 1: Dynamic Program DP1 Finds a Minimum-Makespan On-Time Batch Schedule of Equal-Length Jobs with Agreeable Release and Due DatesResearch Paper

Burn-in is the final testing stage of semiconductor manufacturing: finished integrated circuits are loaded on boards and held in an oven at high temperature for a prescribed minimum time, so that weak devices fail before shipment. An oven holds many boards at once, a load cannot be interrupted, and a board may stay in the oven longer than its specified time…

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