Markov Decision Processes

The formal mathematical framework for modeling sequential decision making under uncertainty.

🟡 intermediate4 min readrlfundamentals

A Markov Decision Process (MDP) is the mathematical foundation of Reinforcement Learning. An MDP is defined as a 5-tuple (S, A, P, R, γ): States S, Actions A, Transition Probability P(s'|s,a), Reward function R(s,a,s'), and Discount factor γ ∈ [0, 1). The core assumption is the Markov Property: future state s_{t+1} depends ONLY on current state s_t and action a_t, independent of past history.

The 5-Tuple Definition $(S, A, P, R, \gamma)$

                       REINFORCE ENVIRONMENT LOOP
                         ┌──────────────────┐
                 Action  │                  │  State s_{t+1}
               ┌─────────┤   ENVIRONMENT    ├─────────┐
               │ a_t     │                  │ reward r_{t+1}
               ▼         └──────────────────┘         ▼
       ┌─────────┴────────┐                  ┌────────┴─────────┐
       │     AGENT        │                  │     AGENT        │
       │ Policy π(a|s)    │                  │ Value V(s)       │
       └──────────────────┘                  └──────────────────┘

State Space $S$ : Set of all valid environment states.
Action Space $A$ : Set of all valid agent actions.
Transition Dynamics $P(s' \mid s, a)$ : $P(S_{t+1} = s' \mid S_t = s, A_t = a)$ .
Reward Function $R(s, a, s')$ : Scalar feedback signal $R_{t+1} \in \mathbb{R}$ .
Discount Factor $\gamma \in [0, 1)$ : Weighs future rewards relative to immediate rewards.

Cumulative Discounted Return $G_t$

The goal of the agent is to maximize expected cumulative discounted return $G_t$ :

G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots

$\gamma = 0$ : Myopic agent (cares only about immediate next reward $R_{t+1}$ ).
$\gamma \to 1$ : Far-sighted agent (weighs long-term future rewards heavily).

Say this out loud

"An MDP is a 5-tuple (S, A, P, R, γ) defining sequential decision making under the Markov property: future state s_{t+1} depends strictly on current state s_t and action a_t. The agent optimizes policy π(a|s) to maximize expected cumulative discounted return G_t = ∑ γ^k R_{t+k+1}."

Follow-ups to expect

What is a Partially Observable MDP (POMDP)? An MDP extension where the agent does not observe true state $s_t$ directly, but receives noisy observation $o_t \sim O(o|s)$ , maintaining a probability belief state $b(s)$ over hidden states.
What is the difference between State-Value V(s) and Action-Value Q(s,a)? $V^\pi(s)$ is expected return starting from state $s$ following policy $\pi$ . $Q^\pi(s,a)$ is expected return starting from state $s$ , taking explicit action $a$ , and thereafter following policy $\pi$ .

Check yourself

Question 1 of 3

What does the Markov Property state regarding state transitions in a Markov Decision Process?

More in Reinforcement Learning

See all →

Value-Based vs Policy-Based Methods5 min Multi-Armed Bandits4 min Proximal Policy Optimization5 min