Interactive companion · Chapter 12 · Reinforcement learning

Reinforcement Learning Lab

A reinforcement learning agent is never told the right answer: it acts, collects rewards or penalties, and learns a policy that maximizes the cumulative reward.

Q Q-learning A2C CartPole clip PPO UCB Bandits CMAB Truck selection

Based on Chapter 12, “Reinforcement learning,” in Alaa Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning Publications, 2024 (ISBN 978-1633438835).

A Q-learning agent learning its way to the treasure.

Part 1 · Section 12.1

Reinforcement learning

An agent observes a state, takes an action from its policy π, collects a reward and moves on, learning by trial and error. In Markov decision processes (MDPs) actions change future states; in multi-armed bandits the agent only chooses among actions.

Section 12.1 explains the agent-environment loop (Figure 12.3) and maps the RL algorithm families in Figure 12.1.

Part 2 · Sections 12.1.1 and 12.1.2

Markov decision processes

Real commutes are uncertain, so the next state follows probabilities: an MDP. Switch between the deterministic and nondeterministic models, pick a mode of transport and take trips.

Section 12.1.1 contrasts the two commute models of Figure 12.2 and defines the expected return and discount factor γ.

Take the commute (Figure 12.2)

Blue: routes your choice can take. Red italics: transition probabilities. Gold: the current trip; edges thicken with use.

Reach the Treasure (Figure 12.4)

A stochastic policy moves the agent left or right between a fire pit (−10), the treasure (+10) and the exit (+4); its expected return weights each reward by its probability:

Play episodes or drag the policy sliders.

Section 12.1.2 computes this expected return by hand (Figure 12.4) and solves the game with value iteration.

Walk the policy tree

🔥 fire pit (−10, ends) · 💎 treasure (+10) · 🤖 agent · 🏁 exit (+4, ends). Each card is a state the agent can reach; p is the probability of reaching it under the current policy. obs = [cell, treasure collected]; policies are [left, right] probabilities.

Learning by trial and error: Q-learning

Q-learning learns the return Q(s, a) of each action by trial and error, with no model. Press Learn and watch the arrows settle; click cells to cycle empty, wall and fire pit.

Section 12.1.2 derives the Q-learning update and explains why it is off-policy.

A gridworld

Each move −0.1; treasure +10; fire pit −10

Part 3 · Sections 12.1.2 to 12.1.4

Values, policies and actor-critic

Policy gradient methods make actions with a positive advantage  = Q(s, a) − V(s) more likely; in actor-critic methods such as A2C, a critic network estimates V(s) for the actor.

Sections 12.1.2 to 12.1.4 build up equations 12.1 to 12.4, compare model-based, model-free, on-policy and off-policy methods (Tables 12.1 and 12.2), and draw A2C in Figure 12.5.

Part 4 · Section 12.3, Listing 12.2

Balancing CartPole with an actor-critic

Keep the pole upright (+1 per step). Play manually, then train an A2C agent and watch the return per episode climb.

Section 12.3 details CartPole’s states and stopping rules; Listings 12.2 and 12.3 train A2C and PPO with Stable-Baselines3.

CartPole

Keyboard in manual mode: ← and →

Part 5 · Section 12.1.5

Proximal policy optimization

PPO keeps each policy update close to the old policy. PPO-clip caps how far the probability ratio r(θ) = πθ(a|s) / πold(a|s) can move from 1:

LCLIP(θ) = Ê[min(r(θ) Â, clip(r(θ), 1 − ε, 1 + ε) Â)]

Drag r(θ) on the plots, or sweep it, to see where the objective goes flat.

Section 12.1.5 explains why big updates are risky and compares PPO-penalty (equation 12.5) with PPO-clip (Figure 12.6).

The clipped objective

 > 0
 < 0

Solid: LCLIP. Dashed gray: unclipped r(θ)Â. Gold arrow: the direction the update pushes r(θ) (none on a flat part).

The KL divergence measures how different two distributions are; it is not symmetric. Move the sliders to see it change.

Section 12.1.5 defines it and shows its role in PPO.

KL divergence between two Gaussians

Part 6 · Section 12.1.6, Listing 12.1

Multi-armed bandits

Three slot machines, unknown payoffs, 90 pulls (Figure 12.7). Pick a strategy, press Play, then compare strategies over 2,000 runs by their regret.

Section 12.1.6 works out each strategy’s regret, shows the greedy trap and derives UCB (equation 12.7); Listing 12.1 codes all four.

Play 90 pulls

Curves: true payoffs (hidden from the player). Ticks: payoffs so far. Dashed gold: the estimate Q. Bars: share of the 90 pulls.

Part 7 · Section 12.5, Listing 12.5

Contextual bandits: choosing a delivery truck

Each truck is an arm, and the route type is the context that changes which arm is best. Press Learn to watch an ε-greedy learner pick a truck per route.

Section 12.5 builds this reward model and solves it with Vowpal Wabbit (Listing 12.5).

Learn a truck per route

Part 8 · Sections 12.2 and 12.4

Reinforcement learning for optimization

Framed as an MDP, a combinatorial problem can be solved by a learned policy.

Sections 12.2 and 12.4 survey routing, dispatch and traffic applications, and Listing 12.4 coordinates a mobile network with PPO.

Part 9 · Code

Python in Google Colab

Open the book’s Chapter 12 notebooks in Colab, or the companion notebook with the from-scratch code below (Python and NumPy only).

Notebooks

All examplesReinforcement Learning Lab companion notebookThe from-scratch code below, ready to run Chapter 12Listing 12.1Multi-armed bandit strategies Chapter 12Listing 12.2A2C on CartPole Chapter 12Listing 12.3PPO on CartPole Chapter 12Listing 12.4Mobile network coordination with PPO Chapter 12Listing 12.5Contextual bandit for truck selection

From-scratch implementations

Open all in Colab
# MDPs, value iteration and Q-learning (Sections 12.1.1 and 12.1.2)
import random

# 1. The commute of Figure 12.2: expected travel time in minutes under uncertainty
alternative = 180                       # assumed time if the train never comes and you look for another way
car = 0.3 * 50 + 0.5 * 67 + 0.2 * 120
train = 0.6 * 108 + 0.4 * (0.9 * 145 + 0.1 * alternative)
bike = 196
print(f"expected minutes: car {car:.1f}, train {train:.1f}, bike {bike}")

# 2. Reach the Treasure (Figure 12.4): the expected return of the book's single trajectory tree
R = 0.4 * 10 + 0.6 * 4 + 0.4 * 0.2 * -10 + 0.4 * 0.8 * 0 + 0.4 * 0.8 * 0.9 * 0 + 0.4 * 0.8 * 0.1 * 4
print(f"expected return of the trajectory tree: {R:.3f}")          # 5.728

# 3. The same game as an MDP. Cells 0 (fire pit, -10, terminal), 1 (treasure, +10 once), 2 (start), 3 (exit, +4, terminal).
#    A state is (cell, treasure still there?). Actions: 0 = left, 1 = right.
def step(state, action):
    cell, treasure = state
    cell += -1 if action == 0 else 1
    if cell == 0:
        return (cell, treasure), -10, True
    if cell == 3:
        return (cell, treasure), 4, True
    if cell == 1 and treasure:
        return (cell, False), 10, False
    return (cell, treasure), 0, False


STATES = [(c, t) for c in (1, 2) for t in (True, False)]


def value_iteration(gamma=0.9, tol=1e-9):
    V = {s: 0.0 for s in STATES}
    while True:
        delta = 0
        for s in STATES:
            q = []
            for a in (0, 1):
                s2, r, done = step(s, a)
                q.append(r + (0 if done else gamma * V[s2]))
            delta = max(delta, abs(max(q) - V[s])); V[s] = max(q)
        if delta < tol:
            return V


def q_learning(episodes=2000, alpha=0.1, gamma=0.9, eps=0.2, seed=0):
    rng = random.Random(seed)
    Q = {(s, a): 0.0 for s in STATES for a in (0, 1)}
    for _ in range(episodes):
        s, done = (2, True), False
        while not done:
            a = rng.randrange(2) if rng.random() < eps else max((0, 1), key=lambda b: Q[(s, b)])
            s2, r, done = step(s, a)
            target = r if done else r + gamma * max(Q[(s2, 0)], Q[(s2, 1)])
            Q[(s, a)] += alpha * (target - Q[(s, a)])               # temporal-difference update
            s = s2
    return Q


V = value_iteration()
Q = q_learning()
print("state (cell, treasure)   V*      Q(left)  Q(right)  greedy action")
for s in STATES:
    if s == (1, True):
        continue                        # unreachable: stepping onto cell 1 collects the treasure
    print(f"{str(s):24s} {V[s]:6.2f}   {Q[(s, 0)]:6.2f}   {Q[(s, 1)]:6.2f}    {'left' if Q[(s, 0)] > Q[(s, 1)] else 'right'}")
# optimal plan: left to the treasure (+10), then right twice to the exit (+4): 10 + 0.9 * 0 + 0.81 * 4 = 13.24

# 4. Q-learning in a gridworld: reach the treasure (+10), avoid the fire pits (-10); every move costs 0.1
GRID = ["....#T",
        ".F.#..",
        "...#F.",
        ".#....",
        ".F.F#.",
        "S....."]
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]                      # up, right, down, left


def grid_step(pos, a):
    r, c = pos[0] + MOVES[a][0], pos[1] + MOVES[a][1]
    if not (0 <= r < 6 and 0 <= c < 6) or GRID[r][c] == "#":
        r, c = pos                                              # bump into the edge or a wall: stay put
    cell = GRID[r][c]
    if cell == "T":
        return (r, c), 10, True
    if cell == "F":
        return (r, c), -10, True
    return (r, c), -0.1, False


def grid_q_learning(episodes=500, alpha=0.5, gamma=0.95, eps=0.1, seed=0):
    rng = random.Random(seed)
    Q = {}
    lengths = []
    for _ in range(episodes):
        s, done, steps = (5, 0), False, 0
        while not done and steps < 200:
            q = [Q.get((s, a), 0.0) for a in range(4)]
            a = rng.randrange(4) if rng.random() < eps else max(range(4), key=lambda b: (q[b], rng.random()))
            s2, r, done = grid_step(s, a)
            target = r if done else r + gamma * max(Q.get((s2, b), 0.0) for b in range(4))
            Q[(s, a)] = q[a] + alpha * (target - q[a])
            s, steps = s2, steps + 1
        lengths.append(steps)
    return Q, lengths


Q, lengths = grid_q_learning()
print("gridworld: steps in the first 5 episodes", lengths[:5], "and the last 5", lengths[-5:])
arrows = "^>v<"
for r in range(6):
    print("   " + " ".join(GRID[r][c] if GRID[r][c] in "#TF" else arrows[max(range(4), key=lambda a: Q.get(((r, c), a), 0.0))] for c in range(6)))
Part 10 · Summary

What to remember

MDPs and bandits

MDP actions change future states; bandits only trade off exploration and exploitation.

Values and advantages

The advantage tells a policy gradient which actions to reinforce.

Stable updates

PPO clips the probability ratio to keep updates small.

RL for optimization

Routing, dispatch and network coordination can be learned as policies.

References: R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., 2018. J. Schulman et al., “Proximal policy optimization algorithms,” 2017. V. Mnih et al., “Asynchronous methods for deep reinforcement learning,” 2016. A. G. Barto, R. S. Sutton and C. W. Anderson, “Neuronlike adaptive elements that can solve difficult learning control problems” (CartPole), 1983. S. Schneider et al., “mobile-env: an open platform for reinforcement learning in wireless mobile networks,” 2022. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 12.

Part 11 · Quiz

Check your understanding

Two quick questions on Chapter 12. Pick an answer to check it.

Q1. In PPO-clip, the advantage  of an action is positive and the probability ratio r(θ) has already risen above 1 + ε. What does the clipped objective LCLIP do?

Q2. Why can the purely greedy (exploit-only) bandit strategy get stuck on a worse slot machine, while UCB does not?

For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms. The coding solutions are also on GitHub (Chapter 12).