MDPs, States, Actions & Rewards

#The Problem

You are writing a chess bot. Or an inventory planner. Or a trading agent. Or the PPO loop that trains a reasoning model. Four different domains, one surprising fact: all four collapse to the same mathematical object.

Supervised learning gives you (x, y) pairs and asks you to fit a function. Reinforcement learning gives you no labels — only a stream of states, the actions you took, and a scalar reward. Did the move win the game? Did the restock decision save money? Did the trade make a profit? Did the token the LLM just produced lead to a higher reward from the judge?

You cannot learn from this stream until you formalize it. "What I saw," "what I did," "what happened next," "how good that was" — each has to become an object you can reason about. That formalization is a Markov Decision Process. Every RL algorithm in this phase, including the RLHF and GRPO loops at the end, optimizes over this shape.

#The Concept

Markov decision process: states, actions, transitions, rewards, discount

The five objects.

• States S. Everything the agent needs to decide. In GridWorld, the cell. In chess, the board. In an LLM, the context window plus any memory.
• Actions A. The choices. Move up/down/left/right. Play a move. Emit a token.
• Transitions P(s' | s, a). Given state s and action a, the distribution over next state. Deterministic in chess, stochastic in inventory, almost-deterministic in LLM decoding.
• Rewards R(s, a, s'). The scalar signal. Win = +1, loss = -1. Revenue minus cost. The log-likelihood ratio term in GRPO.
• Discount γ ∈ [0, 1). How much future reward counts vs present. γ = 0.99 buys a horizon of ~100 steps; γ = 0.9 buys ~10.

The Markov property P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_0, a_0, …, s_t, a_t). The future depends only on the present state. If it does not, the state representation is incomplete — not a failure of the method, a failure of the state.

Policies and returns. A policy π(a | s) maps states to action distributions. The return G_t = r_t + γ r_{t+1} + γ² r_{t+2} + … is the discounted sum of future rewards. The value V^π(s) = E[G_t | s_t = s] is the expected return starting from s under policy π. The Q-value Q^π(s, a) = E[G_t | s_t = s, a_t = a] is the expected return starting with a specific action. Every RL algorithm estimates one of these two, then improves π accordingly.

The Bellman equations. The fixed-point equations that everything in this phase uses:

V^π(s) = Σ_a π(a|s) Σ_{s', r} P(s', r | s, a) [r + γ V^π(s')] Q^π(s, a) = Σ_{s', r} P(s', r | s, a) [r + γ Σ_{a'} π(a'|s') Q^π(s', a')]

These split expected return into "this step's reward" plus "discounted value of where you land." Recursive. Every algorithm in Phase 9 either iterates this equation to convergence (dynamic programming), samples from it (Monte Carlo), or bootstraps it one step (temporal difference).

discount-horizon

#Build It

#Step 1: a tiny deterministic MDP

A 4×4 GridWorld. Agent starts top-left, terminal at bottom-right, reward of -1 per step, actions {up, down, left, right}. See code/main.py.

GRID = 4
TERMINAL = (3, 3)
ACTIONS = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}

def step(state, action):
    if state == TERMINAL:
        return state, 0.0, True
    dr, dc = ACTIONS[action]
    r, c = state
    nr = min(max(r + dr, 0), GRID - 1)
    nc = min(max(c + dc, 0), GRID - 1)
    return (nr, nc), -1.0, (nr, nc) == TERMINAL

Five lines. That is the entire environment. Deterministic transitions, constant step penalty, absorbing terminal state.

#Step 2: roll out a policy

A policy is a function from state to action distribution. The simplest: uniform random.

def uniform_policy(state):
    return {a: 0.25 for a in ACTIONS}

def rollout(policy, max_steps=200):
    s, total, steps = (0, 0), 0.0, 0
    for _ in range(max_steps):
        a = sample(policy(s))
        s, r, done = step(s, a)
        total += r
        steps += 1
        if done:
            break
    return total, steps

Run the random policy 1000 times. Average return is around -60 to -80 for this 4×4 board. The optimal return is -6 (straight-line path down-right). Closing that gap is everything in Phase 9.

#Step 3: compute V^π exactly via the Bellman equation

For small MDPs the Bellman equation is a linear system. Enumerate states, apply the expectation, iterate until the values stop changing.

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in all_states()}
    while True:
        delta = 0.0
        for s in all_states():
            if s == TERMINAL:
                continue
            v = 0.0
            for a, pi_a in policy(s).items():
                s_next, r, _ = step(s, a)
                v += pi_a * (r + gamma * V[s_next])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

This is iterative policy evaluation. It is the first algorithm in Sutton & Barto and the theoretical foundation of every RL method that follows.

#Step 4: γ is a hyperparameter with physical meaning

Effective horizon is roughly 1 / (1 - γ). γ = 0.9 → 10 steps. γ = 0.99 → 100 steps. γ = 0.999 → 1000 steps.

Too low and the agent acts myopically. Too high and credit assignment becomes noisy, because many early steps share responsibility for far-future reward. LLM RLHF typically uses γ = 1 because episodes are short and bounded. Control tasks use 0.95–0.99. Long-horizon strategy games use 0.999.

#Pitfalls

• Non-Markovian state. If you need the last three observations to decide, the "state" is not just the current observation. Fix: stack frames (DQN on Atari stacks 4) or use a recurrent state (LSTM/GRU over observations).
• Sparse rewards. Win-only rewards make learning nearly impossible in large state spaces. Shape rewards (intermediate signal) or bootstrap with imitation (Phase 9 · 09).
• Reward hacking. Optimizing a proxy reward often produces pathological behavior. OpenAI's boat-racing agent spun in circles collecting powerups forever instead of finishing the race. Always define reward from the target outcome, not the proxy.
• Discount mis-spec. γ = 1 on an infinite-horizon task makes every value infinite. Always cap with either a finite horizon or γ < 1.
• Reward scale. Rewards of {+100, -100} vs {+1, -1} give identical optimal policies but vastly different gradient magnitudes. Normalize to [-1, 1]-ish before plugging into PPO/DQN.

#Use It

The 2026 stack reduces every RL pipeline to an MDP before touching code:

Write the five tuples before writing any training loop. Most "RL does not work" bug reports trace back to an MDP formulation that was broken on paper.

#Ship It

Save as outputs/skill-mdp-modeler.md:

---
name: mdp-modeler
description: Given a task description, produce a Markov Decision Process spec and flag formulation risks before training.
version: 1.0.0
phase: 9
lesson: 1
tags: [rl, mdp, modeling]
---

Given a task (control / game / recommendation / LLM fine-tuning), output:

1. State. Exact feature vector or tensor spec. Justify Markov property.
2. Action. Discrete set or continuous range. Dimensionality.
3. Transition. Deterministic, stochastic-with-known-model, or sample-only.
4. Reward. Function and source. Sparse vs shaped. Terminal vs per-step.
5. Discount. Value and horizon justification.

Refuse to ship any MDP where the state is non-Markovian without explicit mention of frame-stacking or recurrent state. Refuse any reward that was not defined in terms of the target outcome. Flag any `γ ≥ 1.0` on an infinite-horizon task. Flag any reward range >100x the typical step reward as a likely gradient-explosion source.

#Exercises

1. Easy. Implement the 4×4 GridWorld and random-policy rollout in code/main.py. Run 10,000 episodes. Report mean and std of return. Compare to the optimal return (-6).
2. Medium. Run policy_evaluation with γ ∈ {0.5, 0.9, 0.99} for the uniform-random policy. Print V as a 4×4 grid for each. Explain why the state values near the terminal grow faster with larger γ.
3. Hard. Turn the GridWorld stochastic: each action slips to an adjacent direction with probability p = 0.1. Re-evaluate the uniform policy. Does V[start] get better or worse? Why?

#Key Terms

#Further Reading

• Sutton & Barto (2018). Reinforcement Learning: An Introduction, 2nd ed. — the textbook. Ch. 3 covers MDPs and Bellman equations; Ch. 1 motivates the reward hypothesis that underlies every subsequent lesson.
• Bellman (1957). Dynamic Programming — the origin of the Bellman equation.
• OpenAI Spinning Up — Part 1: Key Concepts — concise MDP primer from a deep-RL angle.
• Puterman (2005). Markov Decision Processes — the operations-research reference on MDPs and exact solution methods.
• Littman (1996). Algorithms for Sequential Decision Making (PhD thesis) — the cleanest derivation of MDPs as a dynamic-programming specialization.