A mathematical model for sequential decision-making under uncertainty defined by a tuple (S, A, P, R, γ): state space S, action set A, transition kernel P(s'|s,a), reward function R(s,a), and discount factor γ; decisions (policies) map states to actions or distributions over actions.

Principle

Decisions are optimized to maximize expected cumulative (discounted or finite-horizon) reward given the Markov property that the next state distribution depends only on the current state and chosen action.

Demonstration

In a finite MDP representing a grid-world, S is the set of grid cells, A is {up,down,left,right}, P encodes stochastic motion, R gives rewards at goal/obstacle cells, and optimal policies solve Bellman equations to maximize discounted return.

Misapplication

Modeling a problem with hidden relevant history as an MDP without augmenting the state breaks the Markov assumption; learning or planning under this flawed model produces suboptimal or inconsistent policies.

Consequence

For finite, discounted MDPs there exist optimal stationary (memoryless) deterministic policies; dynamic programming and value-iteration algorithms converge to optimal value functions under standard conditions.

Reversal

If the process is non‑Markovian or partially observable, the MDP formalism fails: optimal control requires history-dependent strategies or the richer POMDP framework rather than ordinary MDP solutions.

Boundary

Applies to discrete-time, fully observable decision processes (finite or countable or continuous state/action with measurable structure); it excludes problems with partial observability unless the state is suitably extended, and continuous-time control unless reformulated.

Semantic Tension

Often conflated with reinforcement learning: MDP is the formal model (environment plus rewards), while reinforcement learning comprises algorithms to discover policies when P or R are unknown.

Synthesis

A Markov decision process is the formal state-action-transition-reward framework for sequential stochastic control where the Markov property enables recursive optimization of expected cumulative reward via Bellman relations.