RL From Scratch Lab

A reinforcement learning library gives you an agent in a few lines. That is convenient until the agent learns nothing, or learns the wrong thing, and no error says why. This lab has eight exercises. Each is a short function you write yourself in numpy, then check with hidden tests that run in your browser. Each one starts with a plain-words setup and a trace by hand, so you know the right number before you type a line.

Recap of earlier lessons. RL Foundations covers return, discount and the Bellman idea. Exploration vs Exploitation covers epsilon-greedy. Your First Q-Table and Q-Learning cover the Q-update and SARSA. Dynamic Programming covers policy evaluation and value iteration. Policy Gradient Methods covers REINFORCE. Actor-Critic Methods covers GAE. This lab does not teach those ideas again. It makes you build them.

Learning Objectives

After this lesson, you will be able to:

Write the discounted return of an episode, and the return from every step onward, working backwards
Write an epsilon-greedy choice that uses a seeded random generator, and a running-average update for a bandit arm
Write the Q-learning update and the SARSA update, and say which line makes one off-policy and the other on-policy
Write policy evaluation and value iteration as sweeps over a small grid, and read a greedy policy off the values
Write the REINFORCE gradient for a softmax policy and prove it right with a numerical gradient check
Write Generalized Advantage Estimation, and name the traps that break these functions

Prerequisites

Before You Start

Review

#How This Lab Works

Every exercise has the same shape. First comes a short setup in plain words. Then a hand trace: one small calculation done on paper, with the answer your code should give. Then a card with the goal, a ladder of hints, and a code editor. The editor holds a starter with TODO marks. It has a Run button and a Check my work button, and under it sits a Show solution button. The hints appear one at a time, so you can take the smallest nudge that gets you moving.

Check my work runs your code, then runs a list of hidden tests, one at a time. It tells you how many passed and shows the message of the first one that failed. The starter is built to fail on purpose, so a fresh cell always says some checks failed. When you finish the TODO lines, all of them pass.

Three things about the tests are worth knowing before you start.

They are tolerance based. A result close enough to the right answer passes, so a harmless rounding difference never fails you.
They are deterministic. Any random numbers come from a fixed seed, so a test that fails today fails the same way tomorrow.
They check more than the one example in the hand trace. Some compare your answer with a second route to the same number, such as a slow loop version, an exact solution of a small linear system, or a slope found by nudging a number a tiny bit each way. If your code only matches the trace, it will still fail those.

The cells use numpy only. The browser has no gym or torch, so none of this needs a simulator or a graphics card, and each cell runs in a moment.

Words you need8 terms

The total reward from a step onward, with later rewards counted for less by the discount.

A number from 0 to 1. A reward k steps away is multiplied by gamma to the power k, so nearer rewards count more.

Exploit means take the move that looks best now. Explore means try something else to learn more.

The number an estimate is being moved toward. In Q-learning it is the reward plus gamma times the value of what comes next.

An on-policy method learns about the behaviour the agent really has. An off-policy method learns about a different one, usually the greedy choice.

One pass that updates the value of every state, all from the old values.

A state where the episode ends. Nothing more can be earned, so its value is 0.

How much better a step went than the critic expected: the reward plus the discounted next value, minus this value.

#The Conventions Used Here

Many mistakes in this area are not about maths. They are about which of two conventions a sentence uses. Fix them before writing code. This table is the single source for the whole lab, and the tests assume it.

Quantity	Meaning in this lab
Episode	A list of rewards, one per step t = 0, 1, 2, and so on. The reward at step t is the one received after acting at step t.
Discount	gamma is between 0 and 1. A reward k steps later is multiplied by gamma to the power k. With gamma = 1 nothing is discounted.
Q-table	Q has shape (n_states, n_actions). States and actions are whole numbers. An update function returns a NEW table and leaves the one it was given alone.
done	True when the move ended the episode. There is no next state, so the target is just the reward r.
Ties	When two actions have the same value, np.argmax picks the lowest index.
Random numbers	The caller passes in a numpy generator, and you never create one inside a function. A call draws one number with rng.random(), and only if it explores does it draw one more, rng.integers(k).
Grid world	next_state[s, a] is where you land, reward[s, a] is the reward for the move, terminal[s] marks a finished state, and a terminal state is worth 0. Moves are deterministic.
Sweep	All new values are computed from the OLD values, then swapped in together. A state's new value never feeds another state in the same sweep.
Policy gradient	The policy gives the chance of action a in state s as softmax(theta[s])[a]. The gradient points uphill on the return, so a step is theta + lr * grad. Each term uses G_t, the return from step t onward. The textbook form has an extra gamma to the power t in front of each term. Many implementations leave it out, and this lab does too.
GAE	values[t] is the critic's value of the state at step t. last_value is its value of the state after the last step, or 0.0 if the episode really ended. The advantage after the last step is 0.

When a convention differs from the book you learned from, the tests follow this table. Neither is wrong, and a small change of convention gives different numbers, so name yours before you compare results.

#Exercise 1: Discounted Return

In plain words. An agent gets a reward at each step, and the total it cares about is the return. Rewards that come later count for less, because a prize now is surer than a prize later. The discount gamma, a number from 0 to 1, sets how much less: a reward k steps away is multiplied by gamma to the power k. Almost everything else in this lab uses this idea in some form, so we start here. You write two functions. One gives the return of a whole episode. The other gives the return from every step onward, which is what policy gradients and advantages need.

Hand trace. Rewards 1, 0, 2 with gamma 0.5. The return is 1 + 0.5 x 0 + 0.25 x 2 = 1.5. Working backwards is easier. The last step's return is 2. The step before it adds 0 + 0.5 x 2 = 1. The first step adds 1 + 0.5 x 1 = 1.5. So the returns from each step are 1.5, 1 and 2.

Mini project

Discounted return

~5 min

Write discounted_return(rewards, gamma) for one episode, and returns_to_go(rewards, gamma) for the return from every step onward. Press Check my work to run the hidden tests.

Your codeEdits save in this browser

pythonrunnable cell

The test that catches most wrong answers compares your array with a slow double loop that adds up gamma to the power k times the reward k steps ahead, for every start step. A second one passes in a numpy array and checks that it comes back unchanged, which catches code that adds into the input while it works backwards.

#Exercise 2: An Epsilon-Greedy Bandit Step

In plain words. A bandit is a row of slot machines, called arms. You do not know which pays best, so you keep an estimate for each arm: the average of the rewards it has paid so far. Epsilon-greedy is the simplest rule for choosing. Most of the time, pull the arm with the best estimate (exploit). With a small chance epsilon, pull any arm at random (explore), so a good arm that looked bad early gets another look. After each pull, fold the reward into that arm's average. You do not need to store every reward: moving the estimate by 1 / n of the gap to the new reward gives exactly the plain average of n rewards.

Randomness works the same way in every function of this lab. The caller passes in a numpy generator, and you never create one inside. A call draws one number, u = rng.random(). If u is below epsilon, it draws one more number, rng.integers(len(q)), to pick an arm. Because the order is fixed, a test with a fixed seed knows exactly which arm you should pick.

Hand trace. Three arms, all estimates 0, all counts 0. Arm 1 pays 4. The count becomes 1 and the estimate moves 1 / 1 of the gap: 0 + (4 - 0) / 1 = 4. Arm 1 pays 2. The count becomes 2 and the estimate moves half the gap: 4 + (2 - 4) / 2 = 3, the average of 4 and 2. For the choice, with epsilon 0.1 a random number u below 0.1 means explore. Anything else means take the arm with the best estimate.

Mini project

An epsilon-greedy bandit step

~6 min

Write epsilon_greedy(q, epsilon, rng) to choose an arm, and update_estimate(q, n, action, reward) to fold one reward into that arm's running average. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

Most tests replay the same seeded generator on the side and demand the same picks, so the order of the random draws matters. Another test runs 4000 picks and checks that the share of non-best arms is near epsilon x (k - 1) / k, because a random pick can land on the best arm too. A third makes calls at epsilon 0 and demands that the random stream still moves, one draw per call.

#Exercise 3: The Q-Learning Update

In plain words. A Q-table holds a number for each (state, action) pair: how good that move is, counting the future. After every step the agent has a reward r and has landed in a new state. The target for the move it just made is r plus gamma times the best Q-value in the new state. The update moves the old number a fraction alpha of the way toward that target. If the episode just ended there is no new state, so the target is only r. Q-learning is called off-policy because its target uses the best next move, whatever the agent really does next.

Hand trace. A table with 3 states and 2 actions, all 0 except the row for state 2, which is [0.5, 2.0]. The agent is in state 0, takes action 1, gets reward 1 and lands in state 2. The target is 1 + 0.9 x 2.0 = 2.8. With alpha 0.1 the entry moves a tenth of the way from 0 to 2.8, so Q[0, 1] becomes 0.28. If the episode had ended there, the target would be 1 and the entry would become 0.1.

Mini project

The Q-learning update

~5 min

Write q_learning_update(Q, s, a, r, s_next, done, alpha, gamma) so that it returns a new table in which only Q[s, a] has moved toward the target. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

One test repeats the same update 60 times and expects the entry to arrive at its target. Others hide a huge value in the next state and set done to True, which must be ignored, and use negative Q-values, which catch a max that quietly includes 0.

#Exercise 4: The SARSA Update

In plain words. SARSA is the same update with one change. Q-learning looks at the best move in the next state. SARSA looks at the move the agent really takes there, because that is the move it will carry out. So SARSA learns the value of the way the agent actually behaves, exploring included, and is called on-policy. The name lists what the update uses: state, action, reward, next state, next action.

Hand trace. The same table and step as exercise 3: state 0, action 1, reward 1, next state 2 whose row is [0.5, 2.0]. This time the agent took action 0 in state 2. The target is 1 + 0.9 x 0.5 = 1.45, so with alpha 0.1 the entry Q[0, 1] becomes 0.145. Q-learning gave 0.28. If the agent had taken action 1, the better one, SARSA would also give 0.28.

Mini project

The SARSA update

~5 min

Write sarsa_update(Q, s, a, r, s_next, a_next, done, alpha, gamma). It differs from exercise 3 in one place, the target. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

The strongest test runs 30 random transitions and checks two things: the exact formula, and the fact that a SARSA entry can never end above the Q-learning entry for the same transition, since the action taken is never better than the best action.

#Exercise 5: Policy Evaluation on a Grid

In plain words. Suppose the agent follows a fixed policy and you know the rules of the world. How good is each state? Its value is what the agent can expect to collect from there on. The Bellman equation says a state's value is the policy-weighted average, over actions, of the reward plus gamma times the value of where you land. You do not solve that in one go. You start every value at 0 and apply it again and again, one sweep over all states at a time, until the numbers stop changing.

The world is a small grid given as arrays: next_state[s, a], reward[s, a] and terminal[s]. The four actions are 0 up, 1 down, 2 left and 3 right. A move into a wall leaves you where you are. A move into the goal pays 1 and ends the episode. The cell includes a make_grid helper that builds these arrays, so you only write the sweep.

Hand trace. A 2 x 2 grid. States 0 and 1 are the top row, 2 and 3 the bottom row, and state 3 is the goal. The policy is random: each of the 4 actions has chance 0.25. gamma is 0.9. After sweep 1, state 1 is worth 0.25, because one of its four actions (down) lands in the goal and pays 1. State 2 is the same (right). State 0 has no move into the goal, so it is still 0. After sweep 2, state 0 is worth (0.9 x 0.25 + 0.9 x 0.25) / 4 = 0.1125, from its moves right and down. State 1 is worth (0.225 + 1 + 0 + 0.225) / 4 = 0.3625.

Mini project

Policy evaluation on a grid

~7 min

Write policy_evaluation(next_state, reward, terminal, policy, gamma) that sweeps until the values stop changing. The grid builder is given. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

import numpy as np

def policy_evaluation(next_state, reward, terminal, policy, gamma, tol=1e-10, max_sweeps=10000):
  """Value of every state when the agent follows the policy.

next_state[s, a] is the state you land in, reward[s, a] is the reward for that move.
  terminal[s] is True for a state where the episode has ended: its value is 0.
  policy[s, a] is the chance of taking action a in state s (each row adds up to 1).
  One sweep updates every state at once from the OLD values, then swaps in the new ones.
  """
  V = np.zeros(len(next_state))
  for sweep in range(max_sweeps):
      V_new = V.copy()
      # TODO: q = reward + gamma * V[next_state]   (an array the same shape as reward)
      # TODO: V_new = the policy-weighted sum of q over the actions (axis=1), then V_new[terminal] = 0
      change = np.max(np.abs(V_new - V))
      V = V_new
      if change < tol:
          break
  return V

def make_grid(rows, cols, goal):
  """A grid world. State s = row * cols + col. Actions: 0 up, 1 down, 2 left, 3 right.
  A move into a wall leaves you where you are. Moving into the goal pays 1 and ends the episode."""
  n = rows * cols
  next_state = np.zeros((n, 4), dtype=int)
  reward = np.zeros((n, 4))
  for s in range(n):
      row, col = divmod(s, cols)
      moves = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
      for a, (rr, cc) in enumerate(moves):
          if rr < 0 or rr >= rows or cc < 0 or cc >= cols:
              rr, cc = row, col
          s2 = rr * cols + cc
          next_state[s, a] = s2
          reward[s, a] = 1.0 if (s2 == goal and s != goal) else 0.0
  terminal = np.zeros(n, dtype=bool)
  terminal[goal] = True
  return next_state, reward, terminal

next_state, reward, terminal = make_grid(2, 2, goal=3)
policy = np.full((4, 4), 0.25)
print("after 1 sweep :", policy_evaluation(next_state, reward, terminal, policy, 0.9, max_sweeps=1))
print("converged     :", np.round(policy_evaluation(next_state, reward, terminal, policy, 0.9), 4))

The tests compare your converged answer with the exact one, found by solving a small linear system, on a 2 x 2 grid and on a 3 x 3 grid with a random policy. They also check one and two sweeps against the hand numbers, which catches an update that reads values already changed in the same sweep. A policy that always goes up must give all zeros, which catches code that ignores the policy.

#Exercise 6: Value Iteration

In plain words. Policy evaluation scores a policy someone gave you. Value iteration finds the best one. The change is a single word: instead of averaging over the actions with the policy's weights, take the best action. Sweep until the values stop changing, and you have the best value each state can have. The best way to act is then read off: in each state, pick the action with the highest reward plus gamma times the value of where it lands. That is the greedy policy for those values.

Hand trace. Three states. In state 0, action 0 pays 1 and ends the episode, and action 1 pays 0 and moves to state 1. In state 1, action 0 pays 5 and ends, and action 1 pays 0 and ends. State 2 is where every episode ends. With gamma 0.9, state 1 is worth 5. State 0 is worth the better of 1 and 0 + 0.9 x 5 = 4.5, so 4.5, and its best action is 1, the one that pays nothing now. A rule that only looks at the next reward would pick action 0.

Mini project

Value iteration

~7 min

Write value_iteration(next_state, reward, terminal, gamma) that returns the best values and the greedy policy as whole numbers. The trap example from the hand trace is in the cell. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

import numpy as np

def value_iteration(next_state, reward, terminal, gamma, tol=1e-10, max_sweeps=10000):
  """Best achievable value of every state, and the greedy policy for it.

next_state[s, a] is the state you land in, reward[s, a] is the reward for that move.
  terminal[s] is True for a state where the episode has ended: its value is 0.
  Return (V, policy): V has one value per state, policy[s] is the best action in s
  (the lowest index if two actions tie). One sweep updates every state from the OLD values.
  """
  V = np.zeros(len(next_state))
  for sweep in range(max_sweeps):
      V_new = V.copy()
      # TODO: q = reward + gamma * V[next_state]
      # TODO: V_new = the BEST q in each row (axis=1), then V_new[terminal] = 0
      change = np.max(np.abs(V_new - V))
      V = V_new
      if change < tol:
          break
  # TODO: q from the final V again, and policy = the best action in each row (np.argmax, axis=1)
  policy = np.zeros(len(next_state), dtype=int)
  return V, policy

# A small trap. In state 0, action 0 pays 1 right away and ends. Action 1 pays 0 but leads to state 1,
# where action 0 pays 5. Greedy-for-one-step picks action 0. The best plan is action 1.
next_state = np.array([[2, 1], [2, 2], [2, 2]])
reward = np.array([[1.0, 0.0], [5.0, 0.0], [0.0, 0.0]])
terminal = np.array([False, False, True])
V, policy = value_iteration(next_state, reward, terminal, 0.9)
print("V      :", V)
print("policy :", policy)

The tests check the trap above, exact values on a corridor and on a 3 x 3 grid, where a state d moves from the goal is worth gamma to the power d - 1, and the Bellman optimality equation at the answer. They also check that the policy picks an action whose value really is the highest, that the policy is an integer array, and that the best values are at least the values of the random policy.

#Exercise 7: The REINFORCE Gradient

In plain words. So far the agent learned values and then acted on them. Policy gradient methods change the policy directly. Here the policy is a table of scores theta[s, a], turned into probabilities by a softmax in each state. REINFORCE plays an episode, then for every step nudges the scores so that the action taken becomes more likely if the return that followed was high, and less likely if it was low. The nudge for step t is the return G_t times the slope of log pi(a_t | s_t) with respect to the scores. For a softmax that slope is simple: one_hot(a_t) minus the probabilities. It is added to the row of state s_t. The cell gives you a safe softmax_rows, so you write only the gradient.

Hand trace. Two states, two actions, theta all zeros, so every probability is 0.5. An episode: step 0 is in state 0, takes action 1 and gets reward 1. Step 1 is in state 1, takes action 0 and gets reward 2. gamma is 1, so the returns are 3 and 2. Row 0 gets 3 x ([0, 1] - [0.5, 0.5]) = [-1.5, 1.5]. Row 1 gets 2 x ([1, 0] - [0.5, 0.5]) = [1, -1].

Mini project

The REINFORCE gradient

~7 min

Write reinforce_gradient(theta, states, actions, rewards, gamma) for a softmax table policy. softmax_rows is given. Press Check my work, which tests it against a numerical gradient.

Your codeEdits save in this browser

pythonrunnable cell

import numpy as np

def softmax_rows(theta):
  """Turn each row of scores into probabilities (given to you, already safe from overflow)."""
  z = theta - theta.max(axis=1, keepdims=True)
  e = np.exp(z)
  return e / e.sum(axis=1, keepdims=True)

def reinforce_gradient(theta, states, actions, rewards, gamma):
  """REINFORCE gradient estimate for a table policy pi(a | s) = softmax(theta[s]).

theta is (n_states, n_actions). states, actions, rewards are the three lists of one episode.
  Each step t adds G_t * (one_hot(actions[t]) - pi[states[t]]) to row states[t] of the answer,
  where G_t is the discounted return from step t onward. Return an array shaped like theta.
  """
  theta = np.asarray(theta, dtype=float)
  pi = softmax_rows(theta)
  grad = np.zeros_like(theta)
  # TODO: G = the discounted return from each step onward (walk backwards, as in exercise 1)
  # TODO: for each step t, add G[t] * (one_hot(actions[t]) - pi[states[t]]) to grad[states[t]]
  return grad

theta = np.zeros((2, 2))
g = reinforce_gradient(theta, [0, 1], [1, 0], [1.0, 2.0], 1.0)
print(g)

The decisive test is numerical, as in the deep learning lab. It builds the sum of G_t x log pi(a_t | s_t) with each G_t held fixed, nudges every entry of theta up and down, and the measured slope must equal your gradient. A state that repeats in the episode catches an assignment where an addition belongs. Each row of the gradient must add to 0, and a small step along your gradient with a positive return must make the taken action more likely.

#Exercise 8: Generalized Advantage Estimation

In plain words. REINFORCE multiplies each step by the whole return, which is noisy. An actor-critic method keeps a second model, the critic, that guesses the value of each state. The advantage of a step is how much better it went than the critic expected. The one-step version is delta = reward + gamma x (value of the next state) - (value of this state). Generalized Advantage Estimation, GAE, blends the deltas of several steps ahead with one dial, lambda. With lambda = 0 it is just delta, trusting the critic's next value. With lambda = 1 it is the full return minus the critic's value, trusting only real rewards. The blend is computed backwards: adv[t] = delta[t] + gamma x lambda x adv[t + 1]. The critic's value for the state after the last step is passed in as last_value. Use 0 if the episode really ended.

Hand trace. Rewards 1, 1. Values 0.5, 0.4. last_value 0.2. gamma 0.9, lambda 0.5. The last step has delta = 1 + 0.9 x 0.2 - 0.4 = 0.78 and nothing after it, so its advantage is 0.78. The first step has delta = 1 + 0.9 x 0.4 - 0.5 = 0.86, so its advantage is 0.86 + 0.9 x 0.5 x 0.78 = 1.211.

Mini project

GAE advantage

~6 min

Write gae(rewards, values, last_value, gamma, lam) that returns one advantage per step. Press Check my work.

Your codeEdits save in this browser

pythonrunnable cell

Limits make the best tests. With lambda 0 the answer must be the plain deltas. With lambda 1 it must equal the discounted return plus the discounted last_value, minus values[t]. If the critic is exactly right, meaning its values equal the true returns, every advantage must be 0. A slow double loop over (gamma x lambda) to the power l times delta checks the middle.

#Where the Traps Are

Every exercise has one common wrong answer that looks right. They fall into four families.

Time and index. Returns, advantages and the next-state value all look forward, so they are built by walking backwards. A slip of one place, using values[t] where values[t + 1] belongs, still returns an array of the right shape. Write beside each line which step it refers to, and test with a case where the answer is known, such as lambda = 0 or lambda = 1.

Terminal states. A move that ends the episode has no next state. Skip the done rule and the value past the end of the episode leaks into the target. Forget to force a terminal state to 0, or forget last_value in GAE, and every value near the end is off, with nothing crashing.

Which target. Q-learning uses the best next value, SARSA the value of the action actually taken, policy evaluation the policy-weighted average, value iteration the best action. One word separates each pair, which is why a bug here trains quietly. Also decide whether a sweep reads old values or values already changed. In this lab it reads only the old ones.

Sign and randomness. The REINFORCE gradient points uphill, so the step is plus. A flipped sign trains the policy to do worse. Random choices must come from the generator that was passed in, in a fixed order, and never from a new generator made inside the function, or a seeded run stops being repeatable.

Symptom	Likely cause
Q-values near the end of an episode are too high, or keep growing	The done flag was ignored, so the value of a state that does not exist was added to the target
Q-learning and SARSA give identical tables when they should differ	The SARSA target used the best next value instead of the value of the action taken
The agent grabs the nearest prize and ignores a bigger one later	gamma was left out, or the policy was read from the rewards instead of from reward plus gamma times the value
Policy evaluation gives different answers when the states are numbered differently	Values were updated in place, so some states read new values in the same sweep
The same seeded run gives different results each time	A new generator was made inside a function, or a random draw was skipped on one branch
The policy gets worse as it trains	The gradient step went downhill, a sign slip, or the returns were taken with the wrong sign
The last advantage of an episode is wrong	last_value was ignored, or values[t] was used where the next state's value belongs

#Capstone Checklist

Use this list to check that you are ready to read and write real RL code. Tick each item only if you can do it without looking.

I can write the discounted return and the return from every step onward, and say why it is easiest to walk backwards
I can write an epsilon-greedy choice with a passed-in generator, and a running-average update for an arm
I can write the Q-learning update, with the done rule, and say what makes it off-policy
I can write the SARSA update and say in one sentence how it differs from Q-learning
I can write policy evaluation as sweeps and say why each sweep reads only the old values
I can write value iteration, read the greedy policy off the values, and explain why the greedy policy must come from reward plus gamma times the value
I can write the REINFORCE gradient for a softmax policy and prove it with a numerical gradient check
I can write GAE and say what lambda = 0 and lambda = 1 give
Given an RL loop I have never seen, I can find the index, terminal, target and sign choices in under a minute

If you can tick every line, you can read the training code of an RL library and spot a convention mismatch. If you cannot, go back to the exercise for that line, open the solution, and write the function again without it.

Simple statistical gradient-following algorithms for connectionist reinforcement learning

Ronald Williams (1992)

The REINFORCE gradient from exercise 7.

Q-learning

Christopher Watkins, Peter Dayan (1992)

The update from exercise 3.

High-Dimensional Continuous Control Using Generalized Advantage Estimation

John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, Pieter Abbeel (2015)

The advantage estimate from exercise 8.

Reinforcement Learning: An Introduction

Richard Sutton, Andrew Barto (2018)

Policy evaluation, value iteration, SARSA and policy gradients, in the second edition.

#Key Takeaways

The return is its reward plus gamma times the return of the next step, so it is built by walking backwards. gamma = 1 is the plain sum
Epsilon-greedy draws one number u from the passed-in generator, explores if u is below epsilon, and otherwise takes np.argmax. A step size of 1 / n makes the estimate the plain average
The Q-learning target is r + gamma times the best next value, or just r when done. One entry moves, a fraction alpha of the way
SARSA differs in one place: its target uses the value of the action actually taken next, so it is on-policy and Q-learning is off-policy
Policy evaluation is a policy-weighted average of reward + gamma * V[next_state], swept using only the old values, with terminal states held at 0
Value iteration replaces that average by the best action, and the greedy policy is read from the final values, not from the rewards
The REINFORCE gradient adds G_t * (one-hot - probabilities) to the row of each visited state, with +=, and a numerical gradient check proves it
GAE is adv[t] = delta[t] + gamma * lam * adv[t + 1]. lam = 0 gives the one-step error and lam = 1 gives the full return minus the critic

#Quick Check

Quick Check1 / 4

Q-learning and SARSA both build a target from r plus gamma times a Q-value of the next state. What is the difference?

Where to next. Revisit Policy Gradient Methods and read its REINFORCE equations with your own gradient beside them. To see how a clipped objective keeps policy updates small, continue to Proximal Policy Optimization. To carry these habits into language-model applications, begin the next track with RAG by Hand.

RL From Scratch Lab

Learning Objectives

After this lesson, you will be able to:

Write the discounted return of an episode, and the return from every step onward, working backwards
Write an epsilon-greedy choice that uses a seeded random generator, and a running-average update for a bandit arm
Write the Q-learning update and the SARSA update, and say which line makes one off-policy and the other on-policy
Write policy evaluation and value iteration as sweeps over a small grid, and read a greedy policy off the values
Write the REINFORCE gradient for a softmax policy and prove it right with a numerical gradient check
Write Generalized Advantage Estimation, and name the traps that break these functions

Prerequisites

Before You Start

Review

#How This Lab Works

Three things about the tests are worth knowing before you start.

They are tolerance based. A result close enough to the right answer passes, so a harmless rounding difference never fails you.
They are deterministic. Any random numbers come from a fixed seed, so a test that fails today fails the same way tomorrow.
They check more than the one example in the hand trace. Some compare your answer with a second route to the same number, such as a slow loop version, an exact solution of a small linear system, or a slope found by nudging a number a tiny bit each way. If your code only matches the trace, it will still fail those.