Decisions in sequence: states, rewards and value
A Markov decision process on a grid world: discounted return, the value of a state, the Bellman equation, and value iteration to the best policy.
What it covers6
Why it matters
A bandit makes one kind of choice over and over, and each choice stands alone. Most decisions aren't like that. A move in a game changes the position you move from next. A reply in a conversation changes what the other person says. The reward for a good early move may not arrive until many moves later, and some tempting moves lead somewhere bad. To reason about this you need a way to say how good it is to be in a situation, counting everything that can follow from it. That number is called value, and every reinforcement learning method, including the ones that train language models, is a way of estimating it or acting on it.
What you'll be able to do
- Describe a problem as a Markov decision process: states, actions, rewards and what each action leads to
- Work out the return of a sequence of rewards, with later rewards discounted
- Compute the value of every state under a fixed policy by sweeping the Bellman equation
- Find the best policy with value iteration, and say how the discount and uncertainty change it
Show the answer
It depends on how reliably the robot moves and how bad a fall would be
If every move goes exactly where intended, the short path is simply cheaper. If moves sometimes go astray, each step beside the stairs carries a chance of a large loss, and enough of that risk outweighs the battery saved. Value is the tool for weighing these against each other, and by the end of this lesson you'll compute it for both cases.
The idea: states, actions, rewards and value
Purpose. Describe a decision problem with a few numbers, and measure how good it is to be somewhere.
Here is a small world, three rows by four columns. The agent starts bottom-left. Top-right is a goal worth +1, and just below it a pit worth −1. One square is a wall. Each move costs 0.04, which is what makes shorter routes better.
| blank | col 0 | col 1 | col 2 | col 3 |
|---|---|---|---|---|
| row 0 | goal +1 | |||
| row 1 | wall | pit −1 | ||
| row 2 | start |
Four words describe it, and they describe every problem in this track.
- A state is a situation the agent can be in. Here, a square:
(row, column). - An action is something it can do: up, down, left or right.
- A reward is the number it receives after each action.
- The transition is what an action leads to: the next state.
Setup (runs before every cell) · 23 lines
The lesson runs this once, before its first cell, and every cell, drill and example starts with what it defines. A cell that changes a setup object changes it for the cells after it, until the page reloads.
ROWS, COLS, WALL = 3, 4, (1, 1) ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} STATES = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) != WALL] def step(state, action): r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) def worth(s, a, V, gamma): nxt, reward = step(s, a) return reward + gamma * V[nxt] def value_iteration(gamma, sweeps=100): V = {s: 0.0 for s in STATES} for sweep in range(sweeps): V = {s: 0.0 if s in ENDS else max(worth(s, a, V, gamma) for a in MOVES) for s in STATES} return V
ROWS, COLS = 3, 4 WALL, START = (1, 1), (2, 0) # the goal and the pit: reaching either ends the episode ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} def step(state, action): """Where an action leads and the reward for arriving. Walls and edges leave you where you were.""" r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) state, rewards = START, [] for action in ["up", "up", "right", "right", "right"]: state, reward = step(state, action) rewards.append(reward) print(action, "->", state, "| reward", reward) print("total reward:", round(sum(rewards), 2))
One run from the start to an end square is an episode. This one took five moves and collected −0.04 four times and then +1: 0.84 in all.
Notice what step needs to know: the current state and the action. Nothing about how the agent got there. That is the Markov property from the Markov chains lesson, and a world with states, actions, rewards and Markov transitions is a Markov decision process, or MDP. It is a Markov chain in which you get to choose, at every step, which row of the transition table applies.
A rule that says which action to take in each state is a policy. "Up twice, then right" is not quite one: a policy must answer for every state, because the agent may not end up where it planned.
ROWS, COLS, WALL = 3, 4, (1, 1) ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} def step(state, action): r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) print(step((1, 0), "right"), step((1, 2), "right"), step((2, 0), "down"))
Show the answer
((1, 0), -0.04) ((1, 3), -1.0) ((2, 0), -0.04)
Moving right from (1, 0) hits the wall, so the agent stays put and still pays 0.04. Moving right from (1, 2) lands in the pit: −1. Moving down from the bottom row hits the edge: it stays, and pays 0.04.
The return, and why later counts for less
The agent's aim isn't the next reward. It is the total over the whole episode, called the return. One refinement turns out to matter a great deal: a reward that arrives later is counted for a little less.
In plain words: is the return. is the first reward, the second, and so on. (gamma) is the discount factor, a number between 0 and 1. The first reward counts in full, the second is multiplied by , the third by twice, and each later one by one more.
Uses the setup above, 23 lines.
rewards = [-0.04, -0.04, -0.04, -0.04, 1.0] # the five-move route to the goal gamma = 0.9 parts = [round(r * gamma ** k, 4) for k, r in enumerate(rewards)] print(parts) print("return:", round(sum(parts), 4)) print("a reward of 1 on every move, forever:", round(sum(gamma ** k for k in range(1000)), 3))
The +1 at the end arrives four moves late, so it counts as 0.9⁴ ≈ 0.656. The return of this route is 0.5185, not the 0.84 you get by plain adding.
Why discount at all? Three reasons, in rising order of importance.
- Sooner is better. A reward now is worth more than the same reward later, as with money.
- The future is uncertain. The further ahead a reward lies, the more can go wrong before it arrives.
- The sum stays finite. The last line above is the geometric series from the sequences lesson: a reward of 1 forever adds up to 1 ÷ (1 − 0.9) = 10, not infinity. Without that, "collect as much as possible" would have no meaning for a task that never ends.
is a setting you choose, and it says how far ahead the agent cares. Near 0, it grabs whatever is closest. Near 1, it will take many unrewarded steps toward something large.
A reward k moves away is worth gamma to the power k of its face value today.
Show the answer
2
The return is 1 + 0.5 + 0.25 + 0.125 + ..., a geometric series with first term 1 and ratio 0.5. It settles at 1 ÷ (1 − 0.5) = 2.
The return of a list of rewards
Write discounted_return(rewards, gamma): the first reward in full, plus the second times gamma, plus the third times gamma squared, and so on. An empty list has a return of 0.
Uses the setup above, 23 lines.
def discounted_return(rewards, gamma): return sum(rewards) print(round(discounted_return([-0.04, -0.04, -0.04, -0.04, 1.0], 0.9), 4))
The picture. The always-right policy on the grid, swept 1, 2, 3 and 50 times. Each square shows its value. Watch the news of the goal's +1 spread back one square per sweep. The numbers are the ones the sweeping cell in the next part prints.
Write a sentence or two, then compare it with a good answer in the lesson.
In code: sweeping the Bellman equation
Purpose. Let the values settle by sweeping, plot them, and read the best policy from them.
The value of a state
Now the central idea. The value of a state is the return the agent can expect if it starts there and follows its policy. A square next to the goal has a high value. A square whose policy walks into the pit has a low one.
You could find a state's value by playing out the whole episode and adding up. There is a shortcut that needs no playing out. If the policy takes the agent from state to state with reward , then the return from is that reward plus the discounted return from :
In plain words: is the value of state , and ("s prime") is the state that comes next. The value of where you are is the reward for your next move, plus gamma times the value of where that move puts you.
This is the Bellman equation. It ties each state's value to its neighbor's, and that suggests a method: start every value at 0, then apply the equation to every state, again and again. Each pass is a sweep.
Uses the setup above, 23 lines.
ROWS, COLS, WALL = 3, 4, (1, 1) ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} STATES = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) != WALL] def step(state, action): r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) def evaluate(policy, gamma, sweeps): V = {s: 0.0 for s in STATES} for sweep in range(sweeps): V = {s: 0.0 if s in ENDS else step(s, policy[s])[1] + gamma * V[step(s, policy[s])[0]] for s in STATES} return V def show(V): for r in range(ROWS): print(" ".join( " ## " if (r, c) == WALL else " GOAL " if ENDS.get((r, c)) == 1.0 else " PIT " if (r, c) in ENDS else f"{V[(r, c)]:6.3f}" for c in range(COLS))) always_right = {s: "right" for s in STATES} for sweeps in (1, 2, 3, 50): print("after", sweeps, "sweep" if sweeps == 1 else "sweeps") show(evaluate(always_right, 0.9, sweeps))
The policy here is a poor one: go right, always. Watch what the sweeps do.
- After one sweep each state knows only its next reward: +1 beside the goal, −1 beside the pit, −0.04 everywhere else.
- After two, the square two moves from the goal has heard about it: 0.860. Good news travels back one square per sweep.
- After three, the top-left square reads 0.734, and the top row never changes again.
- By fifty, the rest has settled too. The bottom row and the left column sit at −0.398.
That −0.398 is the policy's fault, not the world's. In the bottom row, "right" walks to the corner and then into the edge forever, paying 0.04 a move: the geometric series again, −0.04 ÷ (1 − 0.9) = −0.4. A value is always the value of a state under a policy. Change the policy and the same square is worth something else.
reward, gamma, next_value = -0.04, 0.9, 0.86 print(round(reward + gamma * next_value, 3))
Show the answer
0.734
−0.04 + 0.9 × 0.86 = −0.04 + 0.774 = 0.734. That is the top-left square in the grid above: one move from a square worth 0.860.
Show the answer
A better policy: the square's value depends on what the agent does next
A value is the return expected from a state when following a particular policy. "Always right" walks into the corner and stays there, so the start is worth −0.4. Under a policy that heads for the goal, the same square is worth 0.519, as the next part shows.
Code flow. One sweep, in the smallest world: a square a one move from a square b, which is one move from the goal. Step through three sweeps and watch a hear about the goal one sweep after b does.
The values as a picture. The best policy's values after 1, 2, 5 and 20 sweeps, drawn as shaded squares (lighter is higher). The setup above holds the world and value_iteration:
Uses the setup above, 23 lines.
import matplotlib.pyplot as plt import numpy as np fig, axes = plt.subplots(1, 4, figsize=(11, 2.6)) for ax, sweeps in zip(axes, (1, 2, 5, 20)): V = value_iteration(0.9, sweeps) grid = np.array([[V.get((r, c), 0.0) for c in range(COLS)] for r in range(ROWS)]) ax.imshow(grid, vmin=-1, vmax=1) ax.set_title(f"{sweeps} sweeps") ax.set_xticks([]) ax.set_yticks([]) plt.show()
The bright patch begins beside the goal and spreads down the left side and along the bottom row, one square a sweep. A heat map shows the shape of a value function faster than a grid of numbers does.
The best policy
Evaluating a given policy is half the story. What you want is the best one. One change to the Bellman equation finds it: don't follow a fixed action, take whichever action gives the most.
In plain words: for each action available in state , work out the reward plus gamma times the value of where it leads. The value of the state is the largest of those. means "the largest, over the actions".
Sweeping this equation until nothing changes is value iteration. When it settles, the best policy can be read straight off: in each state, take the action that achieved the maximum.
Uses the setup above, 23 lines.
ROWS, COLS, WALL = 3, 4, (1, 1) ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} STATES = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) != WALL] ARROW = {"up": "^", "down": "v", "left": "<", "right": ">"} def step(state, action): r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) def worth(s, a, V, gamma): nxt, reward = step(s, a) return reward + gamma * V[nxt] def value_iteration(gamma, sweeps=100): V = {s: 0.0 for s in STATES} for sweep in range(sweeps): V = {s: 0.0 if s in ENDS else max(worth(s, a, V, gamma) for a in MOVES) for s in STATES} return V for gamma in (0.9, 0.5): V = value_iteration(gamma) print("gamma", gamma) for r in range(ROWS): values = " ".join( " ## " if (r, c) == WALL else " GOAL " if ENDS.get((r, c)) == 1.0 else " PIT " if (r, c) in ENDS else f"{V[(r, c)]:6.3f}" for c in range(COLS)) arrows = " ".join( "#" if (r, c) == WALL else "G" if ENDS.get((r, c)) == 1.0 else "P" if (r, c) in ENDS else ARROW[max(MOVES, key=lambda a: worth((r, c), a, V, gamma))] for c in range(COLS)) print(values, " | ", arrows)
With gamma 0.9 the start square is worth 0.519: the return of the five-move route you computed by hand, now found by the algorithm without being told any route. The arrows are the best policy, and they cover every square, including ones a sensible agent would never visit. That is what makes it a policy and not a plan.
With gamma 0.5 the arrows are the same but the start is worth −0.013. An agent that discounts this steeply sees the goal's +1 as 0.5⁴ ≈ 0.06 from the start, barely enough to pay for the walk. Lower the goal's reward a little, and it would have no reason to go.
Value iteration is exact, and it has two limits that Q-learning and Policy gradients remove. It needs to know the rules: step is called for every state and action, without ever moving. And it visits every state on every sweep, which is fine for 11 squares and impossible for chess.
gamma = 0.9 left = -0.04 + gamma * 0.62 right = -1.0 + gamma * 0.0 print(round(max(left, right), 3), "left" if left > right else "right")
Show the answer
0.518 left
Left is worth −0.04 + 0.9 × 0.62 = 0.518. Right is worth −1, since the episode ends and nothing follows. The state's value is the larger, 0.518, and the best action is the one that gave it.
The best action from a state
Write best_action(options, V, gamma). options maps each action's name to a tuple (reward, next_state), and V maps each state to its value. Return a tuple: the action whose reward + gamma * V[next_state] is largest, and that largest worth. If two actions tie, return the one listed first. A next state of None means the episode ends there, and nothing is added.
Uses the setup above, 23 lines.
def best_action(options, V, gamma): return None, 0.0 V = {"a": 0.62, "b": 0.86} print( best_action({"left": (-0.04, "a"), "up": (-0.04, "b"), "right": (-1.0, None)}, V, 0.9))
Worked example: when moves can go astray
Back to the opening question. Make the world unreliable: with some chance, the agent's move is replaced by a random one. Now an action has several possible outcomes, and its worth is the average over them, each weighted by its chance.
Uses the setup above, 23 lines.
ROWS, COLS, WALL = 3, 4, (1, 1) ENDS = {(0, 3): 1.0, (1, 3): -1.0} MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)} STATES = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) != WALL] def step(state, action): r, c = state[0] + MOVES[action][0], state[1] + MOVES[action][1] nxt = (r, c) if 0 <= r < ROWS and 0 <= c < COLS and (r, c) != WALL else state return nxt, ENDS.get(nxt, -0.04) def worth(s, a, V, gamma, slip): total = 0.0 # what actually happens: usually a, sometimes anything for b in MOVES: chance = (1 - slip) * (b == a) + slip / 4 nxt, reward = step(s, b) total += chance * (reward + gamma * V[nxt]) return total def value_iteration(gamma, slip, sweeps=200): V = {s: 0.0 for s in STATES} for sweep in range(sweeps): V = {s: 0.0 if s in ENDS else max(worth(s, a, V, gamma, slip) for a in MOVES) for s in STATES} return V for slip in (0.0, 0.2, 0.4): V = value_iteration(0.9, slip) print("slip", slip, "| start", round(V[(2, 0)], 3), "| beside the pit, row 1", round(V[(1, 2)], 3), "| below the pit", round(V[(2, 3)], 3), "| far corner, top-left", round(V[(0, 0)], 3))
The only change from the lesson's value iteration is worth: it now adds up over every move that might happen, each times its chance. That weighted sum is an expected value, and with it the same sweep handles an uncertain world. Read across the rows. As moves get less reliable every square loses value, but not equally: the square below the pit falls from 0.621 to 0.082, far more than the top-left corner, which falls from 0.734 to 0.512. Being near the pit is cheap when you never slip and expensive when you might. That is the staircase from the opening question, in numbers.
Write a sentence or two, then compare it with a good answer in the lesson.
In practice: sweeps as array operations, and planning in an agent
Purpose. See the same sweep as one line of NumPy, and where planning with a known model fits in a real system.
The array version is the same arithmetic, and it is the form that scales: a sweep over a million states is one max over a large array instead of a Python loop. Tables stop being practical when states are not listed but described, such as every position of a chess board, which is why Q-learning is followed by function approximation in neural networks.
Where this turns up in an engineer's week. Planning with a known simulator: routing, inventory and scheduling problems are often MDPs whose rules are written down, and value iteration or its cousins solve them exactly. An agent that picks tools in a loop is an MDP too: the state is the conversation so far, the actions are tool calls, and the reward arrives at the end. Reward design is where it goes wrong: an agent optimizes the reward you wrote, not the one you meant, so a step cost that is too small or too large changes the route it takes, as the discount did here.
On the job: write the reward and the discount down as parameters, and look at the policy they produce on a small example before trusting them on a big one.
Goes deeper in
- Q-learning: the same values, learned from experience without knowing the rules.
- Policy gradients: improve the policy directly.
- RLHF: the language-model case, where the reward comes from human preferences.
Write a sentence or two, then compare it with a good answer in the lesson.
Practice what you just read
- 6 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 11 review cards for spaced repetition
Try a quiz question
What does the value of a state measure?
Before this lesson
Where this lesson leads.
575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.
Phase 3 · about 39 hours of study
Machine learning
Learning from data, and knowing when it worked
50 lessons 1 free
- What machine learning is FreePrograms that learn rules from examples instead of being told them.30 min
- Features and labelsSupervised learning: inputs, targets and predictions.30 min
- Train, validation and test setsHold data back so you can trust your results.38 min
- Preparing dataClean, encode and scale data before a model sees it.40 min
- Linear regressionFit a line, and predict numbers from features.42 min
- Loss functionsOne number that says how wrong the model is.35 min
- Training with gradient descentAdjust weights step by step to reduce the loss.42 min
- Learning rateStep size, convergence and divergence.35 min
- Logistic regressionPredict probabilities for yes/no outcomes.42 min
- Multiclass classificationSoftmax and cross-entropy for more than two classes.42 min
- The same three models in PyTorchA line, logistic regression and softmax regression fitted both ways: the loss, the gradient and the update opened up, with weight decay and mini-batches.35 min
- Precision, recall and F1Accuracy lies; these don't.42 min
- ROC curves and AUCJudge a classifier across every threshold.30 min
- Calibration: can the probability be trusted?Bands of predicted risk against what happened, the Brier score, why naive Bayes is over-confident, and fixing it on rows the model did not fit.30 min
- Overfitting and underfittingMemorizing versus learning.30 min
- RegularizationPenalize complexity so models generalize.40 min
- Bias and varianceThe two ways a model can be wrong.30 min
- Cross-validationReuse limited data for more reliable estimates.42 min
- Imbalanced classes in depthRare classes measured: why rebalancing mostly moves the threshold, correcting inflated probabilities, average precision against AUC, why the count of rare cases matters, and thresholds from costs.45 min
- Naive Bayes: classifying with countsA classifier trained by counting: Bayes' rule over words, the naive assumption, log scores, smoothing for unseen words, why it is overconfident, and when it beats logistic regression.45 min
- Nearest neighborsPredict from the most similar examples.35 min
- Decision treesLearn a flowchart of yes/no questions.42 min
- Random forests and boostingMany weak models voting beat one strong one.42 min
- Gradient boosting in depthBoosting built from scratch: trees fit to the gradient of the loss, depth and interactions, learning rate against number of trees, early stopping, and what XGBoost and LightGBM add.45 min
- Support vector machinesThe widest margin, support vectors, the hinge loss and C, kernels for curved boundaries, and when an SVM fits.40 min
- Recommender systemsShrunk averages, item-to-item collaborative filtering, matrix factorization, and cold start.40 min
- Project: a price modelMultiple regression on log prices, one-hot categories, percentage effects and an extrapolation flag.45 min
- Feature engineeringTurn raw data into signals a model can use.35 min
- The scikit-learn workflowFit, predict and evaluate with the standard ML library.45 min
- Explaining a model: what it uses, and why this predictionPermutation importance on held-back rows, a linear model's contributions for one customer, partial dependence, and what none of them can say.35 min
- Capstone: churn predictionPredict which customers will leave, and measure it properly.45 min
- ClusteringGroup similar items without labels (k-means).35 min
- Clusters of any shape: DBSCAN and hierarchiesWhy k-means needs round clusters, DBSCAN's core points and noise, and hierarchical clustering with its linkages.40 min
- Anomaly detectionMasking, robust scores with the median and MAD, baselines from the past, isolation forests and thresholds from a review budget.40 min
- Dimensionality reductionVisualize and compress high-dimensional data.35 min
- Cleaning messy dataDuplicates, junk rows, text numbers, mixed dates and missing values that mean something.45 min
- Grouping, pivoting and reshapingNamed aggregation, pivot tables, transform, running totals and groups too small to rank.45 min
- Data in pieces: partitions and mergeable summariesSplit, summarize and combine; which statistics merge exactly, merging variances, sketches for the rest, and partitioning well.30 min
- Combining tables with mergeJoin on keys safely, stack tables, and divide by the right denominator.44 min
- Time series with pandasResample, smooth, compare across years, and test whether one series leads another.45 min
- Forecasting: baselines, lag features and backtestsThree baselines, lag features that never see their own future, a walk-forward backtest, and a range around the number.40 min
- Text mining: TF-IDF, search and labelsBag of words and TF-IDF, similarity search and its blind spots, text classifiers and topics, and when LLM labels are worth it.35 min
- Location dataHaversine distances, nearest places, GeoJSON, point in polygon and simple maps.40 min
- Comparing groups: t-testsWelch's t-test, pooled vs average rates, and a control group for before-and-after changes.40 min
- More tests: groups, categories, relationshipsChoose a test, ANOVA by hand, chi-square on counts, Pearson vs Spearman, one-sided tests.40 min
- Project: an exploratory analysis reportFive business questions answered with cleaning, joins, charts and a test, then written up.45 min
- Bandits: explore or exploitLearning from rewards with no labels: a running estimate for each option, why the greedy choice gets stuck, epsilon-greedy and an optimism bonus.35 min
- Decisions in sequence: states, rewards and valueA Markov decision process on a grid world: discounted return, the value of a state, the Bellman equation, and value iteration to the best policy.40 min
- Q-learning: learning values by doingA value for every action, learned from experience with no rules given: the update, a grid world you can watch, and why optimism explores better than chance.40 min
- Policy gradients: learning what to do directlyA policy as probabilities you can nudge: turn up what worked, measure it against a baseline, and see how the same update trains a language model.40 min
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write