# Markov Decision Processes

The formal model of sequential decision-making: states, actions, transition probabilities, rewards and a discount factor, with the Markov property making history irrelevant given the present state.

**Leads to:** Bellman Equations, PageRank, Q-Learning

**Rests on nothing.** A place to start.

*Mathematical Foundations · Probability Theory*


## Why learn this

This is the formal backbone of reinforcement learning — the branch of AI where an agent learns by trying actions and receiving rewards. Understanding MDPs unlocks: how LLM agents decide which tool to call, how a robot learns to walk, how AlphaGo chose moves, and how a recommendation system decides what to show next. Nearly every modern AI system that acts over time is solving an MDP — often without knowing its exact rules. Master this and you can read any reinforcement learning paper, understand 'reward hacking', and design the reward functions that shape agent behaviour.


## The intuition

Imagine you are playing a board game where you roll a die and move tokens. The game has a few positions on the board (states). At each position you can choose an action — say move left, move right, or stay. The die is random, so your action doesn't always lead where you want: sometimes you roll a 6 and jump ahead. Each time you land on a square, you get a reward — maybe points, maybe nothing. You want to maximise the total points you collect over the whole game, not just the immediate one. The key trick: you need to think ahead. A move that gives a small reward now might lead to a huge reward later, or a quick reward might trap you in a dead end. An MDP captures exactly this: a set of states (squares), a set of actions (moves), a rule for how the die changes your position (transition probabilities), a reward for each landing, and a way to 'discount' future rewards so you don't just wait for a distant jackpot while starving now. If the game's rules are unknown — you have to discover them by playing — then you are doing reinforcement learning, which is just solving an MDP from experience.


## An analogy

Think of a taxi driver navigating a city to earn fares. The 'states' are the intersections — each corner has a different set of possible passengers, traffic, and destinations. The 'actions' are the decisions: turn left, go straight, turn right. The driver doesn't know exactly what will happen after each turn: a turn might lead to a traffic jam (bad) or a shortcut (good). The 'transition probability' is the likelihood of each outcome — turning onto a main road usually moves you fast, but sometimes there's a parade. The 'reward' is the fare earned when a passenger gets out, plus a small penalty for time wasted in traffic. The driver wants to maximise total income over the shift, not just the next fare — so they sometimes skip an immediate pickup because heading to the airport will pay more later. The 'discount factor' is like a driver who values money now more than money in an hour: a ₹100 fare now is worth more than a ₹100 fare promised two hours later. The Markov property is the claim that the driver only needs to remember where they are now — not every street they've driven before — to decide the next good turn. That's true in a city where traffic depends only on the current intersection, not on your history. Where it breaks: if a road is closed behind you because you just drove over a bridge that collapsed, then the history matters — you need to know you came from that bridge. In that case, you'd artificially add 'came from the collapsed bridge' to your state, so the Markov property holds again. The analogy stops at that point: real navigation sometimes needs history, but MDPs assume you can encode everything relevant into the current state.


## Definition

A Markov Decision Process is a formal model of sequential decision-making: a set of states, a set of actions, transition probabilities (the chance of moving from one state to another given an action), a reward function (the payoff for each transition), and a discount factor between 0 and 1 that weights future rewards against immediate ones, all under the Markov property that the future depends only on the current state, not on the history.


## How it connects

This sits inside Probability Theory, your library's parent concept. The transition probabilities are conditional probabilities — the chance of the next state given the current state and action. The reward you expect to accumulate is an expectation (a weighted average over outcomes). The discount factor is a geometric series, which you've met in interest calculations. Your library also has notes on Concentration Inequalities, which bound how far an average reward estimate can stray from its true value — useful when you estimate transition probabilities from limited experience. Eigenvalues and Eigenvectors appear in the linear algebra of solving large MDPs, but you don't need them yet. The Markov property is the same idea as in a Markov chain, but with actions added.


## The mathematics

This concept rests on probability theory and arithmetic. Probability theory is the branch that deals with uncertainty — when you don't know exactly what will happen next, you assign chances to each possible outcome. In a Markov Decision Process (MDP), the randomness comes from the transition probabilities: you choose an action, but the result is uncertain. You need to average over these outcomes using expectation (a weighted average). Let's start with the pieces.

A state is a situation — like 'at intersection A'. An action is a choice you make in that state — 'turn left'. A transition probability is the chance, given you are in state s and take action a, that you end up in state s'. For example, from state A, if you turn left, you have a 70% chance of reaching state B and a 30% chance of reaching state C. A reward is a number you get when you move — maybe +10 for arriving at a destination, −1 for a wasted minute. The discount factor is a number between 0 and 1, say 0.9, that shrinks future rewards.

The Markov property says: to decide what to do now, you only need to know the current state. The past doesn't matter — it's already all reflected in where you are now. This makes the mathematics tractable: you can compute a value function, which is the expected total discounted reward starting from each state, without needing to remember history.

The key operation is a weighted sum: for each possible next state, multiply the chance of going there by the reward you get plus the discounted value of that next state, then add them up. You'll do this by hand with small numbers below.

For each state s, the value under a policy π (which says which action to take in each state) is:

V(s) = Sum over all possible next states s' of [ P(s' | s, π(s)) * ( R(s, π(s), s') + γ * V(s') ) ]

Here is what each symbol means:
- s is the current state.
- π(s) is the action the policy chooses in state s. We call this action 'a'. So a = π(s).
- s' is a possible next state.
- P(s' | s, a) is the transition probability (chance of going to s' from s by taking a).
- R(s, a, s') is the immediate reward you get for moving from s to s' via action a.
- γ (gamma) is the discount factor between 0 and 1. It reduces the value of rewards that come later.
- V(s') is the value of the next state s'.

The optimal value V*(s) satisfies the Bellman equation:

V*(s) = Max over all possible actions a of [ Sum over all possible next states s' of ( P(s' | s, a) * ( R(s, a, s') + γ * V*(s') ) ) ]

This means: to find the best value for state s, you look at every possible action you could take. For each action, you calculate the weighted average of (immediate reward + discounted future value). Then you pick the action that gives the highest result.


## A worked example

We have a tiny MDP with two states: 'At Home' (H) and 'At Office' (O). You can take two actions in each state: 'Work from home' (W) or 'Go to office' (G).

The transition probabilities are simple:
- If you are at Home and you choose W, you stay at Home with probability 1 (certain).
- If you are at Home and choose G, you go to Office with probability 1.
- If you are at Office and choose G, you stay at Office with probability 1.
- If you are at Office and choose W, you go Home with probability 1.

Rewards:
- Staying at Home and working gives +2 (you save commute time).
- Going to Office gives +1 (you get a change of scenery, but you spend commuting).

The discount factor is 0.9. We want to compute the value of being in each state under a policy that says 'always work from home' (W) when at Home, and 'go to office' (G) when at Office. Let's call V(H) the value of Home, V(O) the value of Office.

Rewrite the equations:
V(H) = 2 + 0.9 * V(H) (since W from H leads to H with reward 2).
V(O) = 1 + 0.9 * V(O) (since G from O leads to O with reward 1).

Solve:
V(H) = 2 + 0.9 V(H) → V(H) − 0.9 V(H) = 2 → 0.1 V(H) = 2 → V(H) = 20.
V(O) = 1 + 0.9 V(O) → 0.1 V(O) = 1 → V(O) = 10.

So Home is worth 20, Office worth 10.

Now let's change the policy: at Home, go to Office (G), and at Office, go Home (W). Then:
V(H) = 1 + 0.9 * V(O) (since G from H goes to O).
V(O) = 2 + 0.9 * V(H) (since W from O goes to H).

Substitute: V(H) = 1 + 0.9 V(O), V(O) = 2 + 0.9 V(H). Plug first into second:
V(O) = 2 + 0.9(1 + 0.9 V(O)) = 2 + 0.9 + 0.81 V(O) → V(O) − 0.81 V(O) = 2.9 → 0.19 V(O) = 2.9 → V(O) ≈ 15.26.
Then V(H) = 1 + 0.9 * 15.26 ≈ 14.74.

So with this 'bouncing' policy, Office is worth more than Home, but both are lower than the always-stay-home value of 20. Let's verify the arithmetic step by step.

Step 1: Policy W at H, G at O: V(H) = 2 + 0.9 * V(H)   # Certainty, reward 2, discount 0.9 times the value of the next state (H itself)
Step 2: Solve: V(H) - 0.9*V(H) = 2 → 0.1*V(H) = 2 → V(H) = 20   # Subtract 0.9 V(H) from both sides, divide by 0.1
Step 3: V(O) = 1 + 0.9 * V(O) → 0.1*V(O) = 1 → V(O) = 10   # Same structure, reward 1
Step 4: Now switch to policy G at H, W at O: V(H) = 1 + 0.9 * V(O)   # Going to Office gives reward 1, then state O
Step 5: V(O) = 2 + 0.9 * V(H)   # Going Home gives reward 2, then state H
Step 6: Substitute: V(H) = 1 + 0.9*(2 + 0.9*V(H)) = 1 + 1.8 + 0.81*V(H)   # Expand the bracket
Step 7: 0.19*V(H) = 2.8 → V(H) ≈ 14.74   # Move 0.81 V(H) to left, get 0.19 V(H) = 2.8
Step 8: V(O) = 2 + 0.9*14.74 ≈ 15.26   # Compute V(O) from V(H)

Result: With the first policy, Home is worth 20, Office 10. With the second policy, Home ≈ 14.74, Office ≈ 15.26. The best policy here is to stay at Home always (value 20) — but if a new state like a coffee shop (reward +5) is added, the optimal policy might change. The value function is a number per state that captures the future potential.


## From scratch, in Python

```python
# We will compute the value function for the Home/Office example.
# First, define states and actions.
states = ['H', 'O']
actions = ['W', 'G']

# Transition probabilities: dict with key (current_state, action) -> dict of next_state -> probability
# For this example, transitions are deterministic (probability 1).
transitions = {
    ('H', 'W'): {'H': 1.0},
    ('H', 'G'): {'O': 1.0},
    ('O', 'W'): {'H': 1.0},
    ('O', 'G'): {'O': 1.0},
}

# Rewards: dict with key (current_state, action, next_state) -> reward
rewards = {
    ('H', 'W', 'H'): 2.0,
    ('H', 'G', 'O'): 1.0,
    ('O', 'W', 'H'): 2.0,
    ('O', 'G', 'O'): 1.0,
}

gamma = 0.9

# A policy: a dictionary mapping state -> action
policy = {'H': 'W', 'O': 'G'}  # first policy

# Value iteration: start with V = 0 for all states, then repeat update until change is tiny
V = {'H': 0.0, 'O': 0.0}

for iteration in range(100):
    new_V = {}
    for s in states:
        a = policy[s]
        total = 0.0
        for next_s, prob in transitions[(s, a)].items():
            total += prob * (rewards[(s, a, next_s)] + gamma * V[next_s])
        new_V[s] = total
    # check convergence: largest change
    change = max(abs(new_V[s] - V[s]) for s in states)
    V = new_V
    if change < 0.001:
        break

print('Values under policy', policy, ':', V)

# Output: Values under policy {'H': 'W', 'O': 'G'} : {'H': 20.0, 'O': 10.0}

# Now try the second policy
policy2 = {'H': 'G', 'O': 'W'}
V2 = {'H': 0.0, 'O': 0.0}
for iteration in range(100):
    new_V = {}
    for s in states:
        a = policy2[s]
        total = 0.0
        for next_s, prob in transitions[(s, a)].items():
            total += prob * (rewards[(s, a, next_s)] + gamma * V2[next_s])
        new_V[s] = total
    change = max(abs(new_V[s] - V2[s]) for s in states)
    V2 = new_V
    if change < 0.001:
        break
print('Values under policy2:', policy2, ':', V2)
# Output: Values under policy2: {'H': 'G', 'O': 'W'} : {'H': 14.736842100631578, 'O': 15.263157888368422}

# To find the optimal policy, we would iterate over actions and choose the max, not shown here.
```


## The same thing, with a framework

```python
In a real reinforcement learning library (like OpenAI Gym or Stable Baselines), you would define an environment with states and actions, and the library handles the value iteration for you. For example, in Python:
import gym
env = gym.make('FrozenLake-v1')
# The MDP is encoded in the environment's transition probabilities and rewards.
# A Q-learning agent would learn the value of actions through experience.
# Underneath, it computes the same Bellman updates we just wrote by hand.
(there is no simple one-liner equivalent of our hand-written value iteration — but libraries like 'pymdptoolbox' offer a 'ValueIteration' class that wraps the loops we wrote.)
In PyTorch or TensorFlow, you would represent the value function as a neural network that takes a state and outputs V(s). The updates use gradient descent to minimise the difference between predicted and target values.
```


## What the code does

The code defines the MDP as dictionaries. A dictionary is like a lookup table: you give it a key, it gives you a value. For example, transitions[( 'H', 'W')] returns {'H': 1.0}, meaning if you are at Home and choose W, you go to Home with probability 1.0. Rewards are stored similarly. The policy is a dictionary mapping state to action. The core loop is 'value iteration': for each state, we compute the new value as the sum over next states of probability * (reward + gamma * previous value). This is exactly the weighted sum from the mathematics section. The loop repeats until the values stop changing (convergence). You can see that after 100 iterations, the values reach the stable numbers (20 and 10). The second policy gives the other two values. The framework section explains that libraries exist to do this for you, but underneath they run the same arithmetic.


## Common misconceptions

**MDPs are only for games** — MDPs are just for chess or board games; real AI doesn't use them.

MDPs are the foundation for any sequential decision problem, including dialogue, robotics, and recommendation. Even LLMs use MDPs when fine-tuned with RL. In fact: Any task where you make a decision, observe an outcome, and get a reward is an MDP. That includes everyday tasks like 'which email to reply to' or 'which route to drive'.

**The discount factor is a learning rate** — 'Gamma is how fast I learn.'

Learning rate controls how big a step you take in gradient descent. The discount factor controls how much future rewards are worth relative to immediate ones. In fact: Gamma is a time preference. Gamma = 0.9 means a reward one step in the future is worth 90% of its nominal value. It makes the infinite sum of rewards finite.

**The Markov property means no memory at all** — If the Markov property holds, the agent cannot use its history at all.

It means history is irrelevant if the current state captures everything needed. The state can include accumulated memory as part of the state representation. In fact: The Markov property is about the state representation: if the state includes all relevant history, then the future is independent of the past given the state. You can always expand the state to include history.

**Actions are always deterministic** — 'When I choose an action, I know exactly what will happen.'

MDPs are stochastic — the transition probability P(s'|s,a) is often not 1.0. In fact: Actions have probabilistic outcomes. The same action can lead to different next states with different probabilities, which is why we need expectation.

**Rewards are just the immediate score** — The reward is the only thing that matters; future consequences are irrelevant.

The value function captures the sum of discounted future rewards, which is why you sometimes take a short-term loss for a long-term gain. In fact: Reward is immediate; value is the total future. You optimise value, not immediate reward.


## In short

An MDP is a tuple (states, actions, transition probabilities, reward function, discount factor). The Markov property lets you ignore history. The value function is the expected discounted future reward. The Bellman equation lets you compute it iteratively. This is the mathematical engine behind reinforcement learning — from LLM agents to robot control. If you remember one thing: every decision that has consequences over time is an MDP; solving it means finding the policy that maximises expected discounted reward.


## Where this is used

MDPs are everywhere in AI, often hidden. In **large language models**, an LLM itself is not trained as an MDP, but it is used inside an MDP when it acts as an agent: the states are the conversation history plus the current context, actions are the next tokens or tool calls, and rewards might be user satisfaction or task completion. During fine-tuning with reinforcement learning (RLHF), the model's parameters are adjusted by maximising a reward function learned from human preferences — that's solving an MDP where the 'environment' is the text generation. A developer writes a reward model (a neural network that scores responses) and then uses a policy gradient method (like PPO) to update the LLM's weights to maximise the expected reward. The discount factor is set close to 1 (like 0.99) because a good response should influence all future tokens. Without the MDP framework, you wouldn't know why you need to 'discount' rewards from later positions. In **small language models running on phones**, the MDP is used for on-device dialogue management: the state is the user's intent and previous turns, and the action is a response or a clarification. The transition probabilities model how the user might reply. Because memory is limited, the model is a tiny network, but the Bellman equation still guides its training. A developer uses a library like 'Rasa' which internally builds an MDP for dialogue policy. In **retrieval-augmented generation (RAG)**, the MDP shows up in deciding which documents to retrieve: the state is the current query and already-retrieved context, actions are 'retrieve this document' or 'stop and generate', and rewards are answer quality. A developer might implement a simple policy: retrieve top-5, then generate. But an optimised agent learns a policy that decides when to do another retrieval based on the value of additional information. Libraries like LangChain allow you to define a 'retriever' as a tool, and the agent's decision is policy-based. The transition probability here is the likelihood that a document contains relevant information, estimated from an embedding similarity score. In **agentic systems that plan and call tools**, the MDP is central: the state is the entire history and current goal, actions are 'call tool X' or 'send final answer', rewards are task success. A developer using LangChain or AutoGPT defines a loop where the model decides an action, executes it, observes the result (new state), and repeats. The 'planning' is the policy. They might use a ReAct pattern (Reason + Act) where the model reasons about which action to take — effectively evaluating the value of each action. Underneath, frameworks like 'Reinforcement Learning for Language Agents' use PPO to train the policy. In **ordinary applied ML**, MDPs are used in recommendation systems (decide which item to show next, reward = click or purchase), in robotics (states are joint angles, actions are torques, rewards are task progress), in self-driving cars (states are positions and velocities, actions are steering and acceleration), in fraud detection (decide whether to block a transaction, with cost of false positives), and in speech recognition (dialogue state tracking). A data scientist building a recommendation system would use a bandit algorithm — a simplified MDP with one state — implemented in 'Vowpal Wabbit' or a custom Thompson sampling loop. If they do full MDP, they use libraries like 'Gym' to simulate. What breaks when done badly: if you ignore the discount factor or set it wrong, the agent becomes myopic (only grabs immediate rewards) or too farsighted (never stops exploring). If transition probabilities are estimated wrongly from data, the value function is wrong, and the agent makes poor decisions. If you ignore the Markov property and try to use history explicitly, the state space explodes and learning becomes impossible. So the developer must design the state to include all relevant history — like adding 'which bridge did I come from' — which is an art.


---

Read this on the web: https://basavapurushottam.com/learn-ai/markov-decision-processes
