Markov Decision Process Model¶
Formal model — instantiates Sequential Policy Optimization
Writes a repeated decision as a formal tuple of states, actions, transition probabilities, rewards, and horizon — the shared scaffold every solver, simulator, and learner reads from.
Before anyone can compute, simulate, or learn a policy, the repeated decision has to be written down as a single explicit object. The Markov Decision Process Model is that object: a tuple of a state set, the actions available in each state, a transition model giving the probability of each next state, a reward/cost function scoring each move, and a horizon over which consequences count. Its whole job is representation, not solution — it makes the problem writable so that any optimizer, simulator, or learner can operate on a shared, inspectable structure instead of on someone's mental model. Its one defining commitment is the Markov property: the state must summarize enough that the next transition depends only on the current state and action, never on the full history.[n1] Getting that right is the entire art of the model; everything downstream inherits it.
Example¶
A regional distributor of bottled water wants to formalize its weekly warehouse restocking so the analytics and operations teams stop arguing from different pictures. They build an MDP. The state is on-hand inventory, bucketed into bands (0–200 units, 200–500, and so on), plus units already in transit. The actions are the order sizes they can place: nothing, 50, 100, or 200 pallets. The transition model is next week's stock given this week's stock, the order, and demand — demand is a probability distribution estimated from two years of sales, so a given order lands the warehouse in different next-states with different odds. The reward is negative cost: holding charges, stockout penalties, and ordering fees summed. The horizon is a rolling multi-week window that captures the lead-time lag.
The crucial moment is when they discover that plain on-hand inventory violates the Markov property — because a shipment already en route changes next week's stock regardless of today's order. So they fold "units in transit" into the state until the next transition depends only on the current state and action. The output is not a decision; it is a clean, shared model that the analytics team's solver and the ops team's simulator can both read.
How it works¶
The model is assembled, not computed:
- Define the state set. Choose variables that actually change future options, risks, or rewards, and bucket continuous quantities to a resolution the data can support.
- Enumerate the action set per state. List the legitimate moves available in each state; they need not be the same everywhere.
- Specify the transition model. Give
P(next | state, action)as a probability table, a factored form, or a generative sampler, from data, expert judgment, or physics. - Attach the reward/cost function. Score each transition in units the decision cares about.
- Set the horizon. Finite, infinite, or rolling — how far ahead consequences are allowed to count.
- Audit the Markov property. Where the next state depends on history, augment the state until it does not.
It produces an artifact, never an action. A separate solver, simulator, or learner turns it into a policy.
Tuning parameters¶
- State granularity — finer buckets fit reality more closely but explode the state count and starve each cell of data; coarser buckets are estimable but blur decisions.
- Action granularity — more actions give finer control at the cost of a larger search and thinner evidence per action.
- Transition representation — a full table is exact but huge; a factored or generative form scales but hides structure.
- Horizon type — longer or infinite horizons capture delayed effects but raise uncertainty and computational load.
- Markov augmentation — how much history to fold into the state: enough to satisfy the property, not so much that the space blows up.
When it helps, and when it misleads¶
Its strength is giving everyone one shared, inspectable object: state definitions, transition assumptions, and reward criteria are all forced into the open where they can be argued and audited, rather than buried in an algorithm. It also forces the Markov question, which is where most sequential-decision reasoning quietly goes wrong.
Its failure modes are representational, and they are silent. State misspecification — a state that omits a variable driving transitions — leaves every downstream solver confidently optimal for the wrong problem. The state space is also prone to blowing up: adding one variable multiplies the states, the curse of dimensionality[n2] that makes many honest models intractable. The classic misuse is treating the tidy tuple as validated truth — mistaking the map for the territory and never checking the estimated transitions against reality. The guarding discipline is to validate the Markov assumption and the transition estimates on held-out data, and to keep the model revisable rather than frozen.
How it implements the components¶
The MDP Model supplies the representational scaffold — the problem, not its solution:
state_set— defines the recurring situations, bucketed to a resolution the data supports and augmented until Markov.action_set— enumerates the legitimate moves available in each state.transition_model— specifiesP(next | state, action)as a table, factored form, or sampler.reward_cost_function— scores each transition in the decision's own units.decision_horizon— sets how far consequences are allowed to count.
It does not solve or evaluate: it produces no policy_rule and no policy_evaluation_rule. Turning this model into an optimal action map is Dynamic Programming / Value Iteration and Policy Iteration; the MDP only supplies the board they play on.
Related¶
- Instantiates: Sequential Policy Optimization — the MDP is the formal representation the archetype's solvers, simulators, and learners all consume.
- Sibling mechanisms: Dynamic Programming / Value Iteration · Policy Iteration · Simulation Rollout Evaluation · Reinforcement Learning Policy Learning · Threshold Policy Rule · Adaptive Policy Review Cycle · Off-Policy or Historical Replay Evaluation
Editorial Notes¶
Form Classification¶
Form family: Representation, Specification & Plan
Rationale: The mechanism assembles and publishes the state, action, transition, reward, and horizon tuple that solvers consume, so the operative form is a formal specification rather than the computation performed with it.
Nearest alternative: Analysis, Modeling & Optimization — A solver or simulator computes from the tuple; this mechanism supplies the non-executable model specification on which those computations depend.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Universal
Rationale: Markov decision processes were formalized in postwar operations research through dynamic programming and sequential control.
Related originating lineages:
- Computer Science & Software Engineering — Artificial intelligence and reinforcement learning materially expanded algorithmic solution methods.
- Mathematics — Probability theory supplies the state-transition foundation.
Review resolution: Both independent reviews place the primary provenance in operations_research. The queued differences (domain_reach_disagreement) concern secondary metadata, not primary lineage. The final retains computer_science, mathematics only where a reviewer supplied a formative-lineage rationale; downstream use or broad applicability by itself is not treated as origin. origin_mode=cross_disciplinary_synthesis because the supplied rationales identify formative contributions that are composed in the mechanism's present form. domain_reach=universal records established application breadth separately from provenance. confidence=high preserves the more cautious evidence assessment. encyclopedia_synthesis=false records whether either reviewer identified deliberate corpus-level composition.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The MDP model is a mechanism, not the archetype. A textbook MDP diagram with no governed reward criteria, safety constraints, or review triggers is not Sequential Policy Optimization — it is only the scaffold. The archetype is the discipline of governing what goes into this tuple and when it gets revised.
[n1] The Markov property holds when the future is conditionally independent of the past given the present state — the next state depends only on the current state and action. It is the assumption that makes the whole apparatus tractable, and the one most often violated by an under-specified state. ↩
[n2] The curse of dimensionality is the exponential growth of the state space as variables are added, so that a faithful model quickly becomes too large to store or solve exactly — the standing reason to bucket states coarsely or use factored and sampled representations. ↩