Q-Learning in a Grid World: How an Agent Learns a Policy
A concrete walkthrough of how a reinforcement learning agent uses trial, error and the Bellman equation to discover an optimal path through a simple grid environment.
Why a grid world is the classic first example
Reinforcement learning (RL) is the branch of machine learning concerned with sequential decision-making: an agent takes actions inside an environment, receives rewards, and gradually learns which actions lead to good long-term outcomes. Unlike supervised learning, nobody hands the agent a labelled dataset of correct answers; it has to discover good behaviour purely through trial and error, guided only by the numeric reward signal it receives after each action.
Because real environments like a physical robot or a stock market are complicated and slow to experiment in, RL research and teaching almost always starts with a grid world: a small rectangular grid, one cell of which contains the agent, one or more cells contain a goal with a positive reward, and some cells might be obstacles or hazards with a negative reward. At each time step the agent is in some cell (its state) and chooses to move up, down, left or right (an action); the environment responds by moving the agent (or blocking the move if it hits a wall) and returning a reward, often a small negative number for every ordinary step (to encourage efficiency) and a large positive number for reaching the goal. It is deliberately simple enough to compute exactly and visualize completely, which is exactly why it remains the standard first example: every core RL concept can be shown on a grid small enough to fit on a screen, with every state, action and value visible at once.
States, actions, rewards, and the Markov property
Formally, a grid world (and RL problems generally) is modelled as a Markov Decision Process, or MDP, defined by a set of states S, a set of actions A, a transition function describing the probability of ending up in each next state given a current state and action, a reward function, and a discount factor gamma between 0 and 1. The Markov property, which gives the framework its name, is the assumption that the future depends only on the current state and action, not on the full history of how the agent got there — knowing the agent's current grid cell is enough to predict what happens next, so the agent does not need to remember its entire path.
The discount factor gamma controls how much the agent cares about future rewards relative to immediate ones. A reward received several steps from now is worth gamma raised to that many steps, multiplied by its face value, so a gamma close to 1 (like 0.99) makes the agent very patient and willing to take a long efficient route to a big reward, while a gamma closer to 0 makes it myopic, favouring whatever gives the quickest payoff even if a better long-term option exists. In a grid world, the choice of gamma visibly changes the paths the agent prefers to learn: too low, and it may settle for a nearby mediocre reward rather than travelling further for a better one.
Q-values: the expected value of a state-action pair
The central quantity in Q-learning is the Q-value, written Q(s, a): the expected total future reward (discounted by gamma) of taking action a while in state s, and then continuing to act optimally from then on. If every Q-value were known exactly, the agent's job would be trivial — in any state, just pick the action with the highest Q-value. The entire challenge of Q-learning is that these values are not known in advance and must be estimated purely from the agent's own experience of taking actions and observing what happens.
The agent maintains a table of Q-value estimates, one entry for every combination of grid cell and possible move — for a 5×5 grid with 4 actions, that is 100 numbers, usually all initialised to zero. Every time the agent takes an action and observes the resulting reward and next state, it nudges the relevant table entry toward a better estimate using the Q-learning update rule: Q(s,a) ← Q(s,a) + α [ r + γ maxa' Q(s',a') − Q(s,a) ]
Here alpha is the learning rate, controlling how large a step is taken toward the new estimate each time; r is the reward just received; and the term max Q(s', a') is the agent's current best estimate of how good the next state s' is, found by checking the Q-values of every action available from there. This update is a direct application of the Bellman equation, which expresses the idea that the value of a state-action pair should equal the immediate reward plus the discounted value of the best thing you can do next.
Exploration versus exploitation
Early in training, the Q-table is all zeros or random noise, so always picking the action with the highest current Q-value (exploitation) means the agent commits to essentially arbitrary behaviour before it has learned anything useful, and may never discover a better route it simply never tried. The standard fix is epsilon-greedy action selection: with probability epsilon the agent picks a completely random action (exploration), and with probability 1 minus epsilon it picks whatever action currently has the highest estimated Q-value (exploitation). Epsilon typically starts high, close to 1, so the agent explores broadly at first, and is gradually decreased over training so the agent increasingly exploits what it has learned once its estimates become trustworthy.
In a grid world this tradeoff is easy to see directly: with epsilon too low from the start, an agent that stumbles onto a mediocre path to the goal early on may keep repeating it forever, never trying the cells that would reveal a shorter route, and its Q-values for the unvisited cells stay at zero, uninformative. With epsilon too high for too long, the agent wanders almost randomly and takes far longer to converge on a stable policy, wasting time revisiting cells whose value it already understands reasonably well. Watching an agent's path and its evolving Q-value table side by side, episode after episode, makes the exploration-exploitation tradeoff far more intuitive than the equations alone: you can literally see early episodes as erratic wandering, and later episodes converging to a consistent, purposeful route as the underlying Q-values stabilise.
From a tabular Q-table to a learned policy
After enough episodes — enough full runs from a starting cell to the goal — the Q-values converge (under standard theoretical conditions, they are guaranteed to converge to the true optimal Q-values, provided every state-action pair is visited infinitely often and the learning rate decreases appropriately). Once converged, the agent's policy, its rule for choosing actions, becomes simple: in every state, choose whichever action currently has the highest Q-value. Tracing this greedy path through the grid, cell by cell, reveals the optimal route the agent has discovered from any starting position to the goal, automatically avoiding hazards and taking the shortest or most rewarding path given the reward structure it was trained on.
This exact tabular approach only scales to problems where the number of distinct states is small enough to store explicitly in a table, which is why grid worlds are used for teaching but real applications like Atari games or robotic control need a different approach: Deep Q-Networks (DQN) replace the table with a neural network that takes a state as input and outputs estimated Q-values for every action, letting the same underlying Bellman update rule scale to problems with millions or billions of possible states, such as raw pixel images, that could never be stored as an explicit table. The grid world remains the clearest lens for understanding what that neural network is ultimately approximating.
Frequently Asked Questions
Is Q-learning guaranteed to find the optimal path?
In the tabular setting used for a grid world, yes, under standard theoretical conditions: every state-action pair must be visited infinitely often (which epsilon-greedy exploration with a slowly decaying epsilon satisfies in the limit) and the learning rate must decrease appropriately over time. In practice, with a finite number of training episodes, the agent's Q-values are only an approximation, but they typically converge close enough to optimal that the greedy policy derived from them finds the best or near-best path well before training would formally guarantee convergence.
What is the difference between Q-learning and SARSA?
Both update Q-values using a very similar rule, but Q-learning is off-policy: its update always uses the maximum Q-value available from the next state, regardless of which action the agent actually takes next. SARSA is on-policy: its update uses the Q-value of the action the agent actually did take next, following its current (possibly exploratory) policy. This makes SARSA more conservative, since it accounts for the possibility of taking a risky exploratory action, which matters in environments with hazards where Q-learning's optimistic assumption could lead the agent to walk closer to danger than SARSA would.
Why does the reward function usually include a small negative reward for every step?
A small per-step penalty (for example -1 for every move, with a large positive reward only at the goal) encourages the agent to reach the goal efficiently rather than wandering indefinitely. Without any per-step cost, an agent that eventually reaches the goal receives the same total reward whether it took the shortest path or a much longer meandering one, so there is no pressure toward efficiency. Reward design like this, called reward shaping, has a large effect on the behaviour the agent ultimately learns.
How does the discount factor gamma change the learned behaviour in a grid world with two different-sized rewards?
If a grid world has a small nearby reward and a larger reward further away, a high gamma close to 1 makes the agent value future rewards almost as much as immediate ones, so it is willing to walk the extra distance for the bigger payoff. A low gamma heavily discounts rewards that are many steps away, so the agent may settle for the smaller, closer reward even though the larger one would have produced more total value, because from its perspective the distant reward is worth much less once discounted.