Preporato
Reinforcement Learning Basics: Q-Learning and Reward Shaping on a Gridworld
Hands-on lab · IDE in your browser

Reinforcement Learning Basics: Q-Learning and Reward Shaping on a Gridworld

Learn reinforcement learning by building it. Balance exploration and exploitation with epsilon-greedy action selection, write the temporal-difference update at the heart of Q-learning, train an agent to navigate a gridworld from sparse end-of-episode rewards, roll out the greedy policy to see what it learned, and add potential-based reward shaping that speeds learning without changing the optimal path.

Time
55 min
Checked steps
5
Level
Intermediate
Setup
None
Read step 1

Hands-on labs require Pro · $29.99/mo · cancel anytime

The job

An agent starts in the corner of a gridworld and has to find its way to the goal, avoiding a pit, guided only by a reward it receives at the end of each attempt. You build the Q-learning agent that solves it from scratch, then make it learn faster with reward shaping.

5 steps, each checked when you finish it

A check runs your work at the end of every step. Hints and the full solution are there if you get stuck.

  1. 1

    Choose an action

    Reinforcement learning has no labelled answers.

  2. 2

    The temporal-difference update

    This one line is how the agent learns.

  3. 3

    Train the agent

    Now run the episodes.

  4. 4

    Roll out the policy

    Training mixes in random exploration, so the episode returns are noisy.

  5. 5

    Reward shaping

    On this grid the only rewards are at the very end: +10 at the goal, -10 in the pit.

Step 1 as it appears in the lab

The lab’s own text. The hint and the solution stay inside the lab.

Step 1: Choose an action

Choose an action

Reinforcement learning has no labelled answers. The agent learns by acting, seeing the reward, and adjusting. It faces a constant trade-off: try something new (explore) or take the best action it knows (exploit). Epsilon-greedy is the simplest way to balance the two.

gridworld.py gives you the environment: GridWorld() with reset(), functional step(s, a) returning (next_state, reward, done), states() and manhattan(s). Actions are 0=up, 1=down, 2=left, 3=right. You write the agent in agent.py, where new_Q() gives a table mapping each state to four action-values.

Write epsilon_greedy(Q, s, eps, rng): with probability eps return a uniformly random action using rng; otherwise return the highest-valued action for s, breaking ties toward the lower index.

agent.py, the file you edit61 lines
"""Tabular Q-learning. You choose actions, apply the temporal-difference update, train over episodes,
roll out the greedy policy, and finally shape the reward so learning speeds up."""
import random
from collections import defaultdict

import gridworld as G


def new_Q():
    """A table mapping each state to four action-values, all starting at 0."""
    return defaultdict(lambda: [0.0, 0.0, 0.0, 0.0])


# ---------- Step 1: choose an action ----------

def epsilon_greedy(Q, s, eps, rng):
    """With probability eps pick a uniformly random action (explore); otherwise pick the highest-valued
    action for s (exploit), breaking ties toward the lower action index."""
    # TODO (Step 1): with prob eps return rng.randrange(4); else the argmax of Q[s],
    # ties to the lower index.
    raise NotImplementedError("Step 1: write epsilon_greedy()")


# ---------- Step 2: the temporal-difference update ----------

def td_update(Q, s, a, r, s2, done, alpha, gamma):
    """Move Q[s][a] toward the observed target. The target is r at a terminal step, otherwise r plus gamma
    times the best value available in s2. Update in place."""
    raise NotImplementedError("td_update() arrives in Step 2")


# ---------- Step 3: train ----------

def train(env, episodes=400, alpha=0.5, gamma=0.95, eps0=1.0, eps_min=0.05, seed=0,
          max_steps=200, reward_fn=None, decay_episodes=250):
    """Run Q-learning for a number of episodes with epsilon decaying linearly from eps0 to eps_min. Return
    (Q, returns) where returns[i] is the TRUE (unshaped) total reward of episode i. reward_fn, if given,
    transforms the reward used for the update only: reward_fn(env, r, s, s2)."""
    raise NotImplementedError("train() arrives in Step 3")


# ---------- Step 4: run the greedy policy ----------

def rollout(env, Q, max_steps=100):
    """Follow the greedy policy from the start with no exploration. Return
    {"reached_goal", "steps", "total_reward"}."""
    raise NotImplementedError("rollout() arrives in Step 4")


# ---------- Step 5: shape the reward ----------

def shaped_reward(env, r, s, s2, gamma=0.95):
    """Potential-based shaping: add gamma * phi(s2) - phi(s) to r, with phi(s) = -manhattan distance to the
    goal. This gives a per-step gradient toward the goal without changing which policy is optimal."""
    raise NotImplementedError("shaped_reward() arrives in Step 5")


def first_solved(env, episodes=400, **kw):
    """Train and return the first episode index after which the greedy policy reaches the goal, or None."""
    Q, _ = train(env, episodes=episodes, **kw)
    return rollout(env, Q)["reached_goal"]
Provided for you:gridworld.pytry_it.py

Frequently asked questions

What is the exploration-exploitation trade-off?

An agent must both try unfamiliar actions to discover their value (explore) and take the best action it currently knows to earn reward (exploit). Epsilon-greedy handles it by acting randomly a fraction epsilon of the time and greedily otherwise, usually decaying epsilon as the agent learns.

What does the Q-learning temporal-difference update do?

It moves the value of the action just taken toward the reward received plus the discounted value of the best action available in the next state. Repeated over many steps, this propagates the reward at the goal back through the states that lead to it, so the agent learns a path.

What is potential-based reward shaping?

Adding a shaping term gamma*phi(next) - phi(state) to the reward, where phi is a potential function such as the negative distance to the goal. It gives the agent a helpful per-step gradient and, because it is a potential difference, provably leaves the optimal policy unchanged.

Learning reinforcement learning with Q-learning

Reinforcement learning has no labelled data: an agent learns by acting, observing rewards, and updating its estimates of what each action is worth. Q-learning is the classic tabular algorithm, and a gridworld is the classic place to understand it. In this lab you build a Q-learning agent end to end. You write epsilon-greedy action selection, the temporal-difference update, the training loop, and a greedy rollout, then add potential-based reward shaping and measure how much faster the agent learns when every step points it toward the goal.