Reinforcement learning fundamentals

Small experiments to learn the basics of reinforcement learning, following Reinforcement Learning: An Introduction (Sutton and Barto, 2nd edition). The algorithms are written in Python with NumPy, the environments come from Gymnasium: an ε-greedy agent on a 10-armed bandit and tabular Q-learning on Frozen Lake.

What reinforcement learning is

Sutton and Barto describe reinforcement learning as “learning what to do—how to map situations to actions”, so as to maximize a numerical reward. A learner, the agent, interacts with its environment: it senses the situation it is in, takes an action and receives a reward, a number that says how good the outcome was. Unlike in supervised learning, nobody tells it which action would have been right. It has to discover which actions pay off by trying them. In the harder cases an action also changes the next situation and, through it, all later rewards. These two features, trial-and-error search and delayed reward, are what set reinforcement learning apart. The book’s own picture is an infant at play: no teacher, only the consequences of its own movements.

The book also separates the problem from the solution method: the problem describes what the agent faces, the method how it learns from experience. The same problem can be solved with different methods. Each experiment here pairs one problem with one method, and the two problems follow the split above: the bandit only has trial-and-error search, Frozen Lake adds delayed reward.

Term	Meaning	Bandit	Frozen Lake
Agent	The learner that makes decisions	The player	The figure on the ice
Environment	Everything the agent acts on	Ten slot machines	The frozen lake
State	The situation the agent is in	(only one)	The tile it stands on
Action	What the agent can do	Pull one of ten arms	Step left, down, right or up
Reward	Feedback after an action	Payout of the arm	1 at the goal, otherwise 0
Policy	The agent’s rule for choosing actions	Which arm to pull	Which direction to step on each tile
Method	How the agent learns from experience	ε-greedy with sample averages	Tabular Q-learning

Multi-armed bandit

There are ten slot machines (“arms”, after the one-armed bandit), each with an unknown mean reward. There are no states and no consequences: every pull is the same situation, and the only thing to learn is which arm is best.

What makes this hard is the kind of feedback. A pull returns a reward for the arm that was chosen, but says nothing about which arm would have been best. Supervised learning gets the correct answer no matter what the model predicted. Here the agent only learns about the arms it actually tries. At every step it has to choose between exploitation, pulling the arm that currently looks best, and exploration, pulling another arm to improve its estimate. Exploiting earns more now, exploring can find a better arm and earn more later.

Action values

The value of an arm is its expected reward:

$$q_*(a) = \mathbb{E}\left[R_t \mid A_t = a\right]$$

The index $t$ only ties the reward to the action taken in the same step. The machines do not change over time, so $q_*(a)$ does not depend on $t$. If the agent knew these values the problem would be trivial. It only sees noisy rewards, so it keeps an estimate $Q_t(a)$, the average of the rewards the arm has paid so far:

$$Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbf{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbf{1}_{A_i = a}}$$

The indicator $\mathbf{1}_{A_i = a}$ is 1 when arm $a$ was pulled in step $i$ and 0 otherwise, so it filters the history down to that arm. By the law of large numbers $Q_t(a)$ converges to $q_*(a)$, but only for arms that keep being pulled. Written incrementally, the same average becomes

$$Q_{n+1} = Q_n + \frac{1}{n}\,\big(R_n - Q_n\big)$$

This is the update shape that comes back in every method below, with the observed reward as target and step size $1/n$. There is no next state, so there is nothing to bootstrap from.

Implementation

The testbed follows section 2.3: each $q_*(a)$ is drawn from $\mathcal{N}(0, 1)$, and pulling arm $a$ returns a reward drawn from $\mathcal{N}(q_*(a), 1)$. Environment and agent are kept apart: only pull knows q_star, the agent only ever sees r.

import numpy as np

rng = np.random.default_rng(0)

# Environment: only these two functions know the true values q*(a)
def create_bandit(k=10):
    return rng.normal(0, 1, k)              # one true value per arm

def pull(q_star, a):
    return rng.normal(q_star[a], 1)         # noisy reward around q*(a)

# Agent: sees nothing but its own estimates Q and the rewards it gets
def select_action(Q, epsilon):
    if rng.uniform(0, 1) < epsilon:
        return rng.integers(0, len(Q))      # explore: random arm
    return rng.choice(np.flatnonzero(Q == Q.max()))   # exploit: best arm, ties broken randomly

def run(epsilon, steps=1000, k=10):
    q_star = create_bandit(k)
    best = np.argmax(q_star)                # only used for the statistics

    Q = np.zeros(k)                         # estimated value per arm
    sums = np.zeros(k)                      # total reward per arm
    counts = np.zeros(k)                    # number of pulls per arm
    rewards = np.zeros(steps)
    optimal = np.zeros(steps)

    for t in range(steps):
        a = select_action(Q, epsilon)
        r = pull(q_star, a)
        sums[a] += r
        counts[a] += 1
        Q[a] = sums[a] / counts[a]          # sample average
        rewards[t] = r
        optimal[t] = a == best
    return rewards, optimal

One detail turned out to matter: random tie-breaking. All estimates start at 0, and np.argmax returns the first maximum. A greedy agent then tries the arms in index order and stops at the first one whose first reward is positive. Breaking ties randomly removes this bias towards low indices, but it does not stop the agent from locking in. Only exploration does that.

Why greedy gets stuck

An arm whose estimate is too high gets pulled, pays less than expected and is corrected. An arm whose estimate is too low is never pulled again, so the mistake stays. One unlucky first reward is enough to write off the best arm for good. ε-greedy keeps pulling every arm with probability $\varepsilon / k$, so underestimates get corrected too.

Interactive demo

Press Step to run the loop above one line at a time and watch a single reward turn into a new estimate, or Pull for a whole iteration. With ε = 0 the agent usually commits to one arm within the first few pulls. Try a few bandits with New bandit to see how often that arm is the wrong one. Initial Q 5 makes the greedy agent try every arm once before it commits.

ε stays constant here, it is never reduced over time. Even once the agent knows the best arm, it still pulls a random one in a fraction ε of the steps, so the share of optimal actions stays below 100 %. In practice ε is often lowered during learning for exactly this reason.

Results

Averaged over 2000 random bandits with 1000 pulls each, measured over the last 100 pulls:

Agent	Average reward	Optimal arm chosen
Greedy (ε = 0)	1.03	34 %
ε = 0.01	1.32	61 %
ε = 0.1	1.36	79 %
Greedy, initial Q = 5	1.42	69 %

Always pulling the best arm would give about 1.54, the expected maximum of ten standard normal values.

• Greedy settles on the best arm in only about a third of the runs and never improves after that.
• ε = 0.1 finds the best arm fastest but keeps paying for exploration. Even with perfect estimates it picks the best arm at most $1 - \varepsilon + \varepsilon/k = 91\,\%$ of the time.
• ε = 0.01 learns more slowly and is only at 61 % after 1000 pulls, but its ceiling is 99.1 %, so in the long run it overtakes ε = 0.1.
• Optimistic initial values make even a greedy agent try every arm once, because an untried arm at 5 looks better than any tried one. With sample averages the initial value is forgotten after the first pull, so this only buys one sample per arm. That is enough for the highest average reward here, but the agent still locks onto the wrong arm in about a third of the runs.

Frozen Lake

Picture having to cross a frozen lake to reach a flag on the other side. Some spots have holes in the ice, and you have no map: you only find a hole by falling into it, and then you start over at the shore. On slippery ice a step does not always go where you aimed. And you only find out whether you did well at the very end, when you reach the flag.

This adds what the bandit left out. Where you stand now depends on every earlier step, so a decision matters long after it was made. The only reward comes at the end of a long chain of steps, and the agent has to work out which of them deserve the credit. The exploration problem stays the same. The sections below build up the ideas needed for this: the return and the discount factor for rewards that arrive late, values per state and action, and bootstrapping to pass the reward back step by step.

In the experiment the lake is a 4×4 grid. The agent starts top left (S) and has to reach the goal (G) without falling into a hole (H). The only reward is 1 at the goal. Walking into the edge of the grid is not fatal: the agent stays on its tile, gets a reward of 0 and has only lost a step, which the discount factor turns into a slightly lower value. On slippery ice the agent only moves in the intended direction one third of the time. The agent learns with tabular Q-learning.

Return and discount factor

The agent maximizes the return, the sum of all future rewards, where each step into the future is weighted by the discount factor $\gamma \in [0, 1]$:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

$\gamma$ is part of the problem definition, not of the algorithm. A reward $k$ steps away is worth only $\gamma^k$ of its value today, so with a single reward at the goal a shorter path is worth more. The agent looks roughly $1/(1-\gamma)$ steps ahead, about 100 steps for $\gamma = 0.99$.

State values and action values

The state value $v_\pi(s)$ is the expected return when starting in state $s$ and following the policy $\pi$. The action value $q_\pi(s, a)$ fixes the first action:

$$v_\pi(s) = \mathbb{E}_\pi\left[G_t \mid S_t = s\right], \qquad q_\pi(s, a) = \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right]$$

They are connected through the model $p(s' \mid s, a)$, the probability of landing in $s'$ after taking $a$ in $s$:

$$q_\pi(s, a) = \sum_{s'} p(s' \mid s, a)\,\big[r + \gamma\, v_\pi(s')\big]$$

A short way to remember it: $V$ rates places, $Q$ rates decisions.

Learning from a target

All methods here share one update. An estimate is moved a step of size $\alpha$ towards a target, a new and slightly better guess of what the value should be:

$$\text{estimate} \leftarrow \text{estimate} + \alpha \,\big(\text{target} - \text{estimate}\big)$$

The methods only differ in what the target is made of:

Method	Target	Bootstraps
Bandit (sample average)	$R$	no
Monte Carlo	$G_t$, the full return of the episode	no
TD(0)	$R_{t+1} + \gamma V(S_{t+1})$	yes
SARSA	$R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$	yes
Q-learning	$R_{t+1} + \gamma \max_a Q(S_{t+1}, a)$	yes

The bandit method is the simplest case of this pattern. With only one state and no next step, the future term disappears, and with $\gamma = 0$ and $\alpha = 1/n$ the Q-learning update turns into the sample average from the bandit:

$$Q(a) \leftarrow Q(a) + \tfrac{1}{n}\,\big(R - Q(a)\big)$$

Q-learning keeps a constant $\alpha$ instead of $1/n$. Its target contains its own estimates, which keep changing while the agent learns, so recent experience should count more than an average over everything seen so far.

Bootstrapping

An update bootstraps when its target contains the agent’s own current estimate, like $V(S_{t+1})$ above, instead of only observed rewards. The name comes from “pulling yourself up by your bootstraps”: estimates are improved using estimates.

• It works because every target still contains a piece of real information, the observed reward and the observed next state.
• It lets the agent learn after every single step instead of waiting for the end of the episode, and it has lower variance than the full return.
• The price is bias: while the estimate of the next state is still wrong, the update learns something partly wrong.
• Information travels backwards one step per update. In the demo below the value of the goal spreads tile by tile towards the start.

$n$-step methods and TD($\lambda$) sit in between: they use $n$ real rewards before bootstrapping, or a weighted mix of all $n$. With $\lambda = 0$ this is TD(0), with $\lambda = 1$ it is Monte Carlo.

Temporal-difference learning

TD learning combines learning from experience with bootstrapping. Its core is the TD error, the difference between two predictions of the same quantity made one step apart:

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t), \qquad V(S_t) \leftarrow V(S_t) + \alpha\, \delta_t$$

This places TD among the other families:

	Bootstrapping	No bootstrapping
Known model (exact expectation)	Dynamic programming	Exhaustive search
No model (samples)	TD learning	Monte Carlo

Model-based and model-free

With a model the agent can compute instead of trying. Without one it only sees what env.step() returns. This is why model-free control learns $Q$ rather than $V$: choosing an action from $V$ needs to know where the action leads, while $\arg\max_a Q(s, a)$ does not.

On slippery ice this matters. Take a tile whose neighbours are worth 0.9 (right), 0.3 (up), 0.3 (left) and 0 (a hole below), and every move goes to the intended direction or to one of the two perpendicular ones with probability 1/3:

$$Q(s, \rightarrow) = \tfrac13 (0.9 + 0.3 + 0) = 0.40, \qquad Q(s, \uparrow) = \tfrac13 (0.3 + 0.3 + 0.9) = 0.50$$

Moving “up” is better even though the best neighbour is to the right, because moving right risks sliding into the hole. Q-learning picks this up from experience without ever knowing the 1/3.

Exploration, on-policy and off-policy

With ε-greedy the agent takes the action with the highest current value, and with probability ε a random one instead. Both SARSA and Q-learning act this way and update after every step. They differ only in the target:

• SARSA is on-policy. It uses the action it will actually take next, random moves included, and learns the value of the ε-greedy policy it follows. Near a cliff it learns to keep a safety margin.
• Q-learning is off-policy. It uses $\max_a Q(S_{t+1}, a)$, as if it played perfectly from the next state on, and learns the optimal policy while still exploring.

Off-policy learning is what later makes replay buffers possible (DQN, SAC): the agent can learn from old experience collected by an earlier version of itself.

Implementation

The Q-learning algorithm from Sutton and Barto (section 6.5), with the Python implementation next to each line:

Pseudocode	Implementation
Initialize $Q(s, a)$, with $Q(\text{terminal}, \cdot) = 0$	np.full((n_states, n_actions), 0.5)
Choose $A$ from $S$ using ε-greedy	select_action(Q, s, epsilon)
Take action $A$, observe $R$, $S'$	env.step(a)
$Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma \max_a Q(S', a) - Q(S, A)]$	q_update(...)

import gymnasium as gym
import numpy as np

rng = np.random.default_rng(0)
env = gym.make("FrozenLake-v1", map_name="4x4", is_slippery=False)

n_states = env.observation_space.n      # 16 tiles
n_actions = env.action_space.n          # 0=left, 1=down, 2=right, 3=up

alpha = 0.1                             # step size
gamma = 0.99                            # discount factor
epsilon = 0.1                           # exploration rate

def select_action(Q, s, epsilon):
    if rng.uniform(0, 1) < epsilon:
        return rng.integers(0, n_actions)            # explore: random action
    return rng.choice(np.flatnonzero(Q[s] == Q[s].max()))   # exploit, ties broken randomly

def q_update(Q, s, a, r, s_next, terminated):
    next_value = 0 if terminated else Q[s_next].max()   # nothing follows a hole or the goal
    target = r + gamma * next_value
    Q[s, a] = Q[s, a] + alpha * (target - Q[s, a])

def run_episode(Q):
    s, _ = env.reset()
    total_reward, done = 0.0, False
    while not done:
        a = select_action(Q, s, epsilon)
        s_next, r, terminated, truncated, _ = env.step(a)
        q_update(Q, s, a, r, s_next, terminated)
        total_reward += r
        s = s_next
        done = terminated or truncated
    return total_reward

Q = np.full((n_states, n_actions), 0.5)  # optimistic start, see results
rewards = [run_episode(Q) for _ in range(1000)]

Two details turned out to matter:

• Terminal states. After a hole or the goal nothing follows, so the next value is 0. Handling this with the terminated flag instead of zeroing table rows keeps the update correct for any initial values and does not require knowing where the holes are. A time-limit stop (truncated) is not terminal and still bootstraps.
• Random tie-breaking. At the start all four values of a tile are equal, whatever the initial value. With a plain np.argmax the agent would always pick “left” and keep walking into the wall.

Interactive demo

Press Step to watch a single Q-learning update with all numbers, or +100 episodes to train. Switch the ice to slippery to see the policy change.

As with the bandit, ε stays constant. The success rate during training includes the random moves, so it stays below 100 % even when the learned policy is already perfect. Run greedy test plays without exploration (ε = 0) and shows what the policy itself achieves.

The Q-table starts at 0.5. With Initial Q 0 every target stays 0 until the agent stumbles into the goal by chance, so for a long time nothing is learned at all. With 0.5 or 1 every action the agent tries loses a little value, so untried actions look better and get explored first, and holes are punished right away. A start at 1 lies above every true value and makes the agent try everything before it settles, while 0.5 lets it commit to a good path sooner.

Results

Solid ice. The learned policy is the shortest path around the holes, and the values along it are exactly powers of $\gamma$, the bootstrapped reward one step further away each time:

Tile, action	Steps to goal	$Q(s, a)$
14, →	1	1.000
10, ↓	2	0.990
9, →	3	0.980
8, →	4	0.970
4, ↓	5	0.961
0, ↓	6	0.951

The success rate during training stays around 87 %. The policy itself is perfect: the remaining failures come from ε-exploration, and a greedy evaluation with ε = 0 reaches 100 %.

Slippery ice. Many arrows now point into walls. On the start tile, pushing left means the agent either stays where it is or slides down, and it can never slide towards the holes. The agent chooses actions by which slips are safe, not by where it wants to go. Even the optimal policy only succeeds in about 74 % of episodes. The learned policy matched the one computed with value iteration from the full model on every tile but one.

Initial values. Starting the table at a value above zero (“optimistic initialization”, section 2.6) makes every tried action look slightly worse than the untried ones, which turns into systematic exploration. Holes are recognized at once, while with zeros they teach nothing until the goal has been found by chance. After 200 episodes on solid ice:

Initial Q	Success during training	max Q(start)	Greedy evaluation
0	5 %	0.000	27 %
0.5	90 %	0.951	100 %
1	92 %	0.952	100 %

Over 30 seeds, 0.5 also stopped bumping into walls much sooner than 1. A value of 1 lies above every true value, so the agent has to wear down the optimism of every action first. A value of 0.5 sits between bad and good actions, so the agent commits to the path it found earlier.

Overestimation. On slippery ice the learned max Q(start) settled at 0.583, above the true optimum of 0.542. Taking the maximum over noisy estimates is biased upwards, the maximization bias that Double Q-learning (section 6.7) addresses.