A Markov decision process is the mathematical object behind fully observed reinforcement learning. It separates the environment dynamics from the agent's policy and makes sequential optimization a problem about controlled Markov chains.
Controlled Markov models
The Markov property says that the present state and action contain all information needed to predict the next transition.
Definition. A discounted Markov decision process is a tuple \((\mathcal S,\mathcal A,P,r,\gamma,\mu)\), where \(\mathcal S\) is the state space, \(\mathcal A\) is the action space, \(P(\cdot\mid s,a)\) is a Markov kernel, \(r(s,a)=\mathbb E(R_{t+1}\mid S_t=s,A_t=a)\), \(0\le\gamma<1\), and \(\mu\) is an initial distribution. A policy \(\pi(\cdot\mid s)\) is a Markov kernel from states to actions.
Proposition. For a fixed policy \(\pi\), the state process is a Markov chain with transition kernel \[ P_\pi(B\mid s)=\int_{\mathcal A}P(B\mid s,a)\pi(\mathrm{d}a\mid s). \]
Proof. Condition on the present state \(S_t=s\). The action is sampled from \(\pi(\cdot\mid s)\), and the next state is sampled from \(P(\cdot\mid s,A_t)\). Integrating over the action gives the displayed kernel. No earlier state or action enters the conditional law once \(S_t\) is fixed.
Discounted return
Discounting makes infinite-horizon value finite and gives Bellman operators contraction geometry.
Definition. The discounted return from time \(t\) is \[ G_t=\sum_{k=0}^\infty \gamma^k R_{t+k+1}. \] When rewards are bounded by \(M\), \(|G_t|\le M/(1-\gamma)\).
Proposition. If \(|r(s,a)|\le M\), then every policy value satisfies \(\|v_\pi\|_\infty\le M/(1-\gamma)\).
Proof. Take absolute values inside the discounted sum: \[ |v_\pi(s)|=\left|\mathbb E_\pi\sum_{k\ge0}\gamma^kR_{k+1}\mid S_0=s\right| \le \sum_{k\ge0}\gamma^kM=\frac{M}{1-\gamma}. \]
Finite and measurable cases
Finite MDPs can be written in matrices; general spaces require kernels and measurability.
Remark. In finite state-action spaces, \(P_\pi\) is a stochastic matrix and value functions are vectors. In Borel spaces, existence of optimal stationary policies requires compactness, continuity, or measurable-selection hypotheses; the formal Bellman equations remain the organizing principle, but measurability is not automatic.
Model-free and model-based viewpoints
Reinforcement learning algorithms differ in whether they estimate the transition model or estimate value and policy objects directly.
Definition. A model-based method estimates or uses \(P\) and \(r\). A model-free method estimates \(v_\pi\), \(q_\pi\), \(v_*\), \(q_*\), or policy gradients without explicitly constructing a transition model.
Remark. The distinction is algorithmic, not mathematical: both approaches are approximating consequences of the same MDP law.
Canonical path-space construction
A discounted Markov decision process is a tuple \[ (\mathsf S,\mathcal S,\mathsf A,\mathcal A, P,r,\rho,\gamma), \] where \(P(\mathrm{d}s'\mid s,a)\) is a Markov kernel, \(\rho\) is the initial law, \(r:\mathsf S\times\mathsf A\to\mathbb R\) is measurable, and \(0\le\gamma<1\). A history-dependent randomized policy is a sequence of kernels \[ \pi_t(\mathrm{d}a_t\mid s_0,a_0,\ldots,s_t). \] The Ionescu--Tulcea theorem then determines a unique law on trajectories by \[ \rho(\mathrm{d}s_0) \prod_{t\ge0}\pi_t(\mathrm{d}a_t\mid h_t) P(\mathrm{d}s_{t+1}\mid s_t,a_t). \]
Definition. If rewards are bounded by \(|r|\le R_{\max}\), the discounted return and performance are \[ G=\sum_{t=0}^{\infty}\gamma^t r(S_t,A_t), \qquad J_\rho(\pi)=E_\rho^\pi G. \] They are well defined and \(|J_\rho(\pi)|\le R_{\max}/(1-\gamma)\).
Markovization
Theorem (Markovization). For any history-dependent policy \(\pi\), define, whenever regular conditional laws exist, \[ \bar\pi_t(\mathrm{d}a\mid s) =\mathbb P^\pi(A_t\in\mathrm{d}a\mid S_t=s). \] The time-inhomogeneous Markov policy \(\bar\pi\) has the same marginal law of \((S_t,A_t)\) at every \(t\), and hence the same expected additive return.
Proof. Induct on \(t\). The state law at \(t=0\) is \(\rho\). If the state laws agree at \(t\), then the definition of \(\bar\pi_t\) makes the joint state-action laws agree. Integrating the common joint law against \(P(\mathrm{d}s'\mid s,a)\) gives equal next-state laws. The expected reward at each time is therefore equal, and bounded convergence justifies summing discounted expectations.
Discounted occupancy measures
Definition. The normalized discounted state-action occupancy measure is \[ d_\rho^\pi(B) =(1-\gamma)\sum_{t=0}^{\infty}\gamma^t \mathbb P_\rho^\pi\{(S_t,A_t)\in B\}. \] It is a probability measure, and \[ J_\rho(\pi) =\frac1{1-\gamma}\int r(s,a)\,d_\rho^\pi(\mathrm{d}s,\mathrm{d}a). \]
Proposition (flow equation). Its state marginal \(d_{\rho,S}^\pi\) satisfies \[ d_{\rho,S}^\pi(\mathrm{d}s) =(1-\gamma)\rho(\mathrm{d}s) +\gamma\int P(\mathrm{d}s\mid x,a) d_\rho^\pi(\mathrm{d}x,\mathrm{d}a), \] and, for a stationary Markov policy, \(d_\rho^\pi(\mathrm{d}s,\mathrm{d}a) =d_{\rho,S}^\pi(\mathrm{d}s)\pi(\mathrm{d}a\mid s)\).
Proof. Separate the \(t=0\) term in the discounted state marginal and shift the remaining sum by one. The Markov transition formula gives the integral term. The factorization follows from the conditional action law under a stationary policy.
Finite, continuous, and average-reward models
For finite \(\mathsf S,\mathsf A\), bounded rewards and discounting ensure existence of an optimal stationary deterministic policy. On Borel spaces, one typically assumes compact action sets, upper semicontinuous rewards, and weakly continuous transition kernels to obtain measurable maximizers. Without such selection hypotheses, Bellman suprema need not be attained.
The average-reward objective \[ \liminf_{T\to\infty}\frac1T E^\pi\sum_{t=0}^{T-1}r(S_t,A_t) \] is not obtained by simply setting \(\gamma=1\): contraction disappears and results require recurrence or unichain conditions. Finite-horizon problems instead augment the state by time and use backward, time-dependent Bellman recursions.
Example (inventory control). With stock \(S_t\), order \(A_t\ge0\), demand \(D_{t+1}\), and \(S_{t+1}=S_t+A_t-D_{t+1}\), a reward combining sales, order cost, and holding cost yields an MDP. The transition kernel is induced by the demand law. State constraints, action-dependent support, and convex costs make this a useful continuous-state example where measurable-selection assumptions matter.