RobotGuide
Foundations/MDP and Return: Writing 'What To Do' as Something Computable

Foundations 02 / 11 · Modeling

MDP and Return: Writing 'What To Do' as Something Computable

States, actions, transitions, rewards, discount. Once these are pinned down the problem has no ambiguity left - all algorithms are solving the same problem

45 minFoundational6 derivation steps4 self-test questions

One-line conclusion

Reinforcement learning does not solve 'what the world is'; it solves 'given your state representation, how to pick the most profitable action'. If the state is defined wrong, no algorithm can save you - this is the number one cause of failure in real-robot RL, and it matters far more than hyperparameters.

Many people skip this article and go straight to the algorithms, then discover on the real robot that 'it learns in simulation but freezes on hardware'. The root cause is almost always here: the Markov property fails, the reward is written to fire every step, or the discount factor crushes the horizon too hard.

Symbol table

SymbolMeaning
S / AState set / action set
P(s'|s,a)Transition probability; the environment decides it, you cannot learn it and do not need to
rReward. Note whether it is r(s,a) or r(s,a,s') - the two conventions differ by a bias
γDiscount factor, between 0 and 1 (must be below 1 for continuing tasks)
G_tThe discounted return from time t onward - 'how much you can collect in total from here'
π(a|s)The policy, the thing you are learning

Derivation

  1. The five-tuple, and what the Markov property actually demands
  2. Return: folding 'the future' into a single number today
  3. Value functions: V is 'averaged over the policy', Q is 'pin the action down first'
  4. The Bellman expectation equation: one application of the tower property
  5. Another reason for γ<1: it hands you an upper bound on scale
  6. Two kinds of 'optimal': fix the policy then optimize, or optimize the value directly

1. The five-tuple, and what the Markov property actually demands

M=(S, A, P, R, γ). The Markov property says: given the current state s, the future is independent of the past. This does not describe the world; it demands that your state representation be sufficient.

P(st+1 | s_t, a_t) = P(st+1 | s_0,a_0,...,s_t,a_t)

Why this holdsThe most common violation on robots: the state contains joint positions but not joint velocities. Then the 'current state' cannot determine the next step - your policy is effectively dealing with a partially observable environment, and what it learns will jitter. The fix is not a new algorithm; it is putting velocities (or a few frames of history) into the observation.

2. Return: folding 'the future' into a single number today

The return is the discounted sum of rewards. Discounting is not mathematical decoration; it decides how far ahead the algorithm 'sees'.

G_t = rt+1 + γ rt+2 + γ² rt+3 + … = ∑k=0∞ γ^k rt+k+1

Why this holdsThe effective horizon is about 1/(1-γ): γ=0.99 → 100 steps, γ=0.9 → 10 steps. So a small γ is not 'more conservative', it is 'more short-sighted'. In a grasping task with γ=0.9 where one grasp takes 80 steps, the policy never sees a success signal, and the symptom is 'giving up right before reaching the goal'.

3. Value functions: V is 'averaged over the policy', Q is 'pin the action down first'

The two value functions differ in exactly one way: V weights actions by the policy, Q fixes one action in place.

V^π(s) = E_π[G_t | S_t=s], Q^π(s,a) = E_π[G_t | S_t=s, A_t=a], V^π(s) = ∑_a π(a|s)·Q^π(s,a)

Why this holdsThat last equality matters: it means once you have Q you automatically have V (just a weighted average), but not the other way around. The answer to 'why nearly every algorithm learns Q instead of V' lives here.

4. The Bellman expectation equation: one application of the tower property

Split the return into 'this step's reward' plus 'the rest', take the expectation of the rest via the tower property from article 2, and you have the Bellman equation.

V^π(s) = ∑_a π(a|s) ∑s' P(s'|s,a)[ r(s,a,s') + γ V^π(s') ]

Why this holdsWhen you write code, always confirm where the reward sits: inside the bracket means r depends on s' (most simulators work this way); outside the bracket means it depends only on (s,a). Getting this wrong raises no error; it just shifts the whole value function by a constant, and the symptom is 'the critic loss never reaches 0'.

5. Another reason for γ<1: it hands you an upper bound on scale

When rewards are bounded, the discounted return is bounded too. This bound is not theoretical fastidiousness; it directly tells you how large the critic output should be and what learning rate to use.

|G_t| ≤ R_max / (1-γ)

Why this holdsR_max=1 and γ=0.99 → return capped at 100. So the critic output should live between 0 and 100; if you see Q values reach 1e4, first check whether you gave +1 reward every step (you should only give it at termination).

6. Two kinds of 'optimal': fix the policy then optimize, or optimize the value directly

The policy iteration route (value → policy) and the policy gradient route (policy → value) look opposed, but they are solving the same optimality equation. The only difference is which half you choose to treat as the object being optimized.

V*(s) = max_a ∑s' P(s'|s,a)[ r + γ V*(s') ]

Why this holdsNote that max here replaces ∑_a π. This step turns a linear equation into a nonlinear one; it is the ultimate root of 'you cannot invert a matrix, you must approximate', expanded in article 3.

Work it by hand

An MDP with only two states: in A there is a 90% chance of staying in A and scoring 1, and a 10% chance of moving to B; B is a terminal state. γ=0.9. Find V(A).

  1. Set up the equation: V(A) = 1 + 0.9 × (0.9·V(A) + 0.1·V(B))
  2. B is terminal → V(B) = 0; substitute: V(A) = 1 + 0.81·V(A)
  3. Rearrange: V(A)·(1-0.81) = 1 → V(A) = 1/0.19
  4. V(A) = 5.263
Answer

V(A)=5.263. The number looks far bigger than '1 point each time' because A keeps paying out (90% self-loop): a geometric series summing to 1/(1-0.81). Value iteration in practice converges after 300 rounds to 5.26315789, matching the analytic solution to the last digit. This is also the fastest way to check whether your Bellman implementation is right: build an MDP you can compute by hand first.

Run it

A 4×4 grid, -1 per step, start at the top-left, terminal at the bottom-right. Value iteration in 20 lines, printing the V matrix and optimal actions. The value of this code: you can watch the shape of V 'grow' out of the rewards and transitions.

python · numpy only
import numpy as np
N, G = 4, 0.99
V = np.zeros((N, N))
moves = [(-1,0),(1,0),(0,-1),(0,1)]   # up down left right
for _ in range(500):
    Vn = V.copy()
    for i in range(N):
        for j in range(N):
            if (i, j) == (N-1, N-1):
                continue
            q = []
            for di, dj in moves:
                ni, nj = min(max(i+di,0),N-1), min(max(j+dj,0),N-1)
                r = 0.0 if (ni,nj)==(N-1,N-1) else -1.0
                q.append(r + G * V[ni, nj])
            Vn[i, j] = max(q)
    if np.abs(Vn - V).max() < 1e-9:
        V = Vn; break
    V = Vn
np.set_printoptions(precision=1, suppress=True)
print(V)
print('top-left V =', round(V[0,0], 2), ' theory: about -1/(1-0.99) in scale, decaying with distance')

You pass when you see this

V decreases monotonically from the bottom-right toward the top-left (farther is more negative); the top-left lands between about -33 and -40. If V is all 0 or all -1, your termination condition or reward sign is wrong.

Self-test · 4 questions

Answer first, then expand. Each question traces back to a specific derivation section.

01What happens if joint velocities are missing from the state? Does a bigger network fix it?

The Markov property breaks: the same observation no longer has a unique optimal action, the policy oscillates between two actions, and what it learns jitters. A bigger network only makes it jitter more confidently. The fix is to put velocities, torques, or a few frames of history into the observation.

02With γ=0.99, how much weight does a reward at step 150 still carry in the return?

0.99^150 ≈ 0.22. So rewards beyond 100 steps already have very weak influence - that is what 'effective horizon' means: not truncated, but crushed by exponential decay.

03Why do almost all algorithms learn Q rather than V?

Because V is only the policy-weighted average of Q: knowing Q gives you V for free, while the reverse requires knowing the policy to recover it. And a control problem ultimately has to pick an action; Q directly ranks every action.

04The reward is +1 only at termination, γ=0.99 - what range should the critic output normally fall in?

Between 0 and 1/(1-0.99)=100. If you see magnitudes like 1e4, you are almost certainly rewarding every step, or Q is self-amplifying without target synchronization.

Keep reading

Previous: the four math toolsNext: the Bellman equationReinforcement learning knowledge page
PreviousThe Only Four Math Tools You Need NextThe Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge

The whole series · 11 articles

01The Only Four Math Tools You Need40 min02MDP and Return: Writing 'What To Do' as Something Computable45 min03The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge60 min04Model-Free: The Bias-Variance Ledger of MC vs TD60 min05Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'55 min06Policy gradient: deriving REINFORCE line by line70 min07Actor–critic and GAE: turning the variance knob to λ60 min08PPO: what does clip actually clip70 min09SAC: entropy, reparameterization, double Q - three parts, each solving one problem75 min10HER: why goal relabeling is mathematically legitimate50 min11How to debug non-convergence: map symptoms back to formulas45 min