Markov Decision Processes & the Bellman Equation
Formalizing 'an agent acting in a world'
Reinforcement learning needs a precise mathematical object to describe the problem an agent is solving: an environment with states, actions the agent can take, and rewards it receives. That object is the Markov Decision Process (MDP). Nearly every reinforcement learning algorithm — from tabular Q-learning to the deep RL systems behind game-playing agents and RLHF-tuned language models — is, underneath, solving an MDP.
The four components of an MDP
An MDP is defined by a tuple $(S, A, P, R)$, sometimes with a discount factor $\gamma$:
- States ($S$) — every possible situation the agent could be in. A chess board position, a robot's sensor readings, a game score.
- Actions ($A$) — every move the agent can take from a given state.
- Transition function ($P$) — $P(s'|s, a)$, the probability of landing in state $s'$ after taking action $a$ in state $s$. This can be deterministic or stochastic (the same action might lead to different outcomes due to randomness in the environment).
- Reward function ($R$) — $R(s, a, s')$, the immediate numeric reward received for that transition. This is the only signal that tells the agent what's good or bad — there's no supervised "correct action" label anywhere.
The agent's goal is to learn a policy $\pi(a|s)$ — a strategy for choosing actions — that maximizes the total reward accumulated over time.
The Markov property: the past doesn't matter, only the present
The defining assumption of an MDP is the Markov property: the probability of the next state depends only on the current state and action — not on the entire history of how the agent got there. Formally, $P(s_{t+1}|s_t, a_t) = P(s_{t+1}|s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0)$.
This is a modeling convenience, not always literally true of the real world — but it's extremely powerful when it holds (or approximately holds), because it means the *current state* is a sufficient summary of everything relevant to the future. You don't need to remember the whole trajectory, just where you are right now. This is exactly why state representation design matters so much in RL: if your state doesn't capture enough information to make it Markovian, the agent effectively can't plan correctly.
Value functions: how good is a state (or state-action pair)?
To act well, the agent needs to estimate *how good* a state is — not just immediately, but accounting for everything it can lead to. The state-value function $V^\pi(s)$ is the expected total discounted future reward from state $s$, following policy $\pi$ thereafter: $V^\pi(s) = E\left[\sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s\right]$
The discount factor $\gamma$ (between 0 and 1) controls how much the agent cares about future rewards versus immediate ones — $\gamma$ close to 0 makes the agent myopic, $\gamma$ close to 1 makes it farsighted.
The action-value function (Q-function) $Q^\pi(s, a)$ is similar, but conditions on taking a specific action $a$ first, then following $\pi$ afterward. This is the quantity Q-learning directly learns, because knowing $Q(s,a)$ for every action tells you exactly which action is best without needing a separate model of the environment's dynamics.
The Bellman equation: the recursive heart of RL
The Bellman equation expresses a value function recursively: the value of a state equals the immediate reward, plus the discounted value of whatever state comes next. For the optimal value function:
$V^*(s) = \max_a \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^*(s') \right]$
And the equivalent for the optimal Q-function:
$Q^*(s,a) = \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^*(s', a') \right]$
This recursive structure is why RL algorithms can learn incrementally rather than needing to see complete trajectories: you can update your estimate of $Q(s,a)$ using just the immediate reward plus your *current estimate* of the next state's value, then repeat. This is exactly the update rule behind Q-learning and underlies nearly every value-based RL algorithm, from tabular methods to deep Q-networks.
Epsilon-greedy: balancing exploration and exploitation
Even with a perfect value-update rule, the agent faces a fundamental dilemma: should it take the action it currently believes is best (exploitation), or try something different to see if it's actually better (exploration)? Always exploiting risks getting stuck on a mediocre strategy because you never discover a better one; always exploring wastes reward on actions you already know are bad.
Epsilon-greedy is the simplest practical answer: with probability $\epsilon$, take a random action (explore); otherwise, take the current best-known action (exploit). $\epsilon$ typically starts high (encouraging exploration early, when value estimates are unreliable) and decays over training as the agent's estimates become more trustworthy.
Key RL concepts at a glance
| Concept | What it represents | Where it's used |
|---|---|---|
| State-value V(s) | Expected return from a state under a policy | Policy evaluation, actor-critic baselines |
| Action-value Q(s,a) | Expected return from taking a specific action | Q-learning, DQN, action selection |
| Bellman equation | Recursive relationship linking value to next-state value | Foundation for value iteration and Q-learning updates |
| Epsilon-greedy | Exploration strategy balancing random vs. greedy actions | Nearly every value-based RL algorithm during training |
What's next
This is the mathematical skeleton underneath reinforcement learning; for how these ideas scale up with neural networks as function approximators instead of exact tables, and how real agents are trained in practice, see reinforcement-learning.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.