A formal model for sequential decision problems in which an agent observes a state from a state space, chooses an action from an action set, and the system transitions to a next state according to transition probabilities that depend only on the current state and action (the Markov property); a reward function assigns immediate payoffs and the objective is to maximize expected cumulative reward over a horizon (discounted or finite).

Principle

Optimal control is characterized by Bellman optimality: the value function satisfies a recursive equation equating the value of a state to the best expected immediate reward plus the discounted value of successor states; solving these equations (value iteration, policy iteration, or linear programming) yields an optimal policy when state/action spaces and model probabilities are known and tractable.

Demonstration

Illustrative scenario — Inventory replenishment: Situation — state = current inventory level, action = order quantity, demand is stochastic with known distribution. Recognition — define transition probabilities P(s'|s,a) from demand model and immediate cost/reward (holding, shortage, ordering). Action — apply value iteration: initialize value, iterate Bellman update until convergence, extract policy mapping inventory states to optimal order amounts. Consequence — derived policy minimizes expected long‑run cost under the assumed model and discounting horizon, subject to model accuracy and computational limits.

Misapplication

Modeling a partially observable or history‑dependent problem as an MDP without augmenting the state to capture necessary information, or treating the learned policy as optimal when transition probabilities or reward functions are misspecified; the semantic error is assuming the Markov property or model knowledge where it does not hold.

Consequence

When correctly specified, an MDP yields prescriptive optimal policies and value bounds and supports algorithmic solution techniques; misapplication produces policies that perform poorly or are unsafe in deployment because unmodeled dependencies or model uncertainty invalidate optimality claims.

Reversal

If the agent cannot observe the full state, the problem is a POMDP and requires belief‑state augmentation; if transition probabilities or rewards are unknown, reinforcement learning or robust MDP formulations are needed; continuous or very large state/action spaces demand function approximation, hierarchical decomposition or approximative algorithms that forfeit exact Bellman solutions.

Boundary

Clearly within — finite discrete state/action problems with known transition probabilities and rewards amenable to dynamic programming. Boundary case — large or continuous state/action spaces where exact DP is infeasible and approximation is needed. Clearly outside — adversarial settings without stochastic transition models (game‑theoretic formulations) or one‑shot decision problems without sequential structure.

Semantic Tension

Tradeoff between model fidelity and computational tractability: representing all relevant information in the state ensures Markovian structure but increases dimensionality and computational cost; simplifying the state can make computation feasible but violates Markov assumptions and degrades policy quality.

Synthesis

MDPs formalize the structure of sequential stochastic decision making and identify Bellman recursion as the central computational principle; their practical success depends on the adequacy of the state representation and whether transition/reward models can be known or learned within available computational resources.