Q-Learning

Q-learning is a reinforcement-learning algorithm that learns the value of taking an action in a state from experience. Each transition updates one Q-table entry using an observed reward and the largest estimated value at the next state. Repeated visits let delayed rewards influence earlier choices without requiring the agent to know the environment's transition model.

Think of a signpost at each junction. Its arrows carry estimates of what you could earn by taking each direction. Reaching a rewarding exit changes the estimate on the arrow that led into it. On a later visit, the junction before that one can learn from the improved signpost. The reward does not rewrite the whole route at once.

The choice here is between +1 on the next move and +5 three moves away. You can see both exits on the map; the updater learns only from the moves the agent tries. Tabular Q-learning fits small, discrete state and action spaces where you can collect repeated experience without knowing the transition model.

How Q-Learning Works: One Experience Changes One Estimate

A state describes where the agent is. An action selects a legal move. The environment returns an immediate reward and a next state. Q(s,a) estimates the discounted return from taking action a in state s and then following an optimal policy. Early in training, that estimate can be wrong. A larger Q value means a more promising action; Q is not an action probability. An episode is one attempt from the start until an exit. Starting a new episode resets the position and keeps the learned table.

The target combines a reward with an estimate

The target is the reward from this move plus the discounted best estimate at the next state. You already observed the reward; the future part is still an estimate. The learning rate alpha controls how far the old Q value moves toward this target. Here alpha = 0.5, so the old estimate and target meet halfway.

For one observed transition (s, a, r, s'), Q-learning forms a target:

future = max over legal a' of Q(s', a')
target = r + gamma * future
Q(s, a) <- Q(s, a) + alpha * (target - Q(s, a))

At a terminal state, future is zero: the episode has ended and there is no next action. The exit reward is already included in r. Every other table entry stays unchanged. The quantity target - Q(s,a) is the temporal-difference error: how far this new target lies from the old estimate. With alpha = 0.5, the update moves halfway toward it; a lower target can also pull Q downward.

Discounting changes which reward is worth pursuing

The discount factor gamma applies once per transition. A reward of 5 received on the third move contributes gamma² × 5 to the return from the start. At gamma = 0.9 that is 4.05; a reward of 1 on the first move contributes 1. At gamma = 0, only the immediate reward counts. Changing gamma changes the objective, not just the speed of learning.

Exploration collects experience; the target uses the maximum

The agent must also decide which experiences to collect. An epsilon-greedy behavior policy draws a uniformly random legal action with probability epsilon; otherwise it chooses an action with the largest current Q value. A random draw can select that same maximizing action. "Explore" describes how the action was sampled, not a promise that the action is worse.

Q-learning is off-policy: its target uses the maximum next-state estimate, even when the behavior policy subsequently samples a different action. SARSA's on-policy target instead uses the next action actually sampled. Both are meaningful learning rules; they answer different policy questions.

Q-Learning Step by Step

The default world has two rows and three columns:

You can move between adjacent open cells. At S, legal actions are Up and Right; at A, Right and Left; at B, Up and Left. Entering either exit gives its reward and ends the episode. All other moves give zero. The wall and map boundary make an action unavailable, represented by a dash rather than a zero estimate.

The run starts with all legal Q values at zero, alpha = 0.5, epsilon = 0.35, gamma = 0.9, and eight episodes. Each episode starts at S and preserves the table. A fixed random seed of 947 makes the demonstration repeatable. Greedy ties follow the legal-action orders above, so the first greedy choice at S is Up. A safety cutoff limits an episode to eight transitions; the longest default episode uses five, so the cutoff does not affect this trace.

Episode 1: learn the nearby exit. The agent takes Up from S and receives 1. The next state is terminal, so the target is 1 + 0.9 × 0 = 1. Q(S,Up) becomes 0 + 0.5 × (1 - 0) = 0.5. Q(S,Right) stays zero.

Episode 2: discover the goal. An exploration draw takes Right to A. Reward and A's estimates are zero, so Q(S,Right) remains zero. Right from A reaches B; its target is also zero. Finally, Up from B reaches the goal. Reward 5 and terminal future zero give target 5, so Q(B,Up) becomes 2.5. The earlier two entries remain zero: those updates already happened before the reward arrived.

Episode 3: move the value one junction backward. Another exploration draw takes S to A. The start's target is still zero. The subsequent A-to-B move now reads Q(B,Up) = 2.5. Its target is 0 + 0.9 × 2.5 = 2.25, and Q(A,Right) becomes 1.125. Reaching the goal again raises Q(B,Up) from 2.5 to 3.75.

Episode 4: change the start's preferred action. Exploration again takes Right from S. A's best estimate is now 1.125, giving target 1.0125. Q(S,Right) becomes 0.50625, just above Q(S,Up) = 0.5. The start's greedy arrow turns Right. The agent finishes the route through B to the goal.

These end-of-episode estimates show why reaching the goal once is not enough:

Each signpost improves when its own action is tried again. In episode 2, S and A had already been updated using zeros before B encountered +5. They cannot use B's new estimate until a later visit.

Episode 5: separate the target from behavior. The agent follows S → A → B → A → B → goal. On the first A-to-B transition, Q(B,Up) = 4.375 and Q(B,Left) = 0. Q-learning uses target 3.9375 and updates Q(A,Right) from 2.25 to 3.09375. The next exploration draw then chooses Left at B. The target used the best estimated continuation even though behavior took a detour. Substituting that sampled Left action would have produced target zero and an updated Q(A,Right) of 1.125 on this same prefix.

Episodes 6 through 8 repeat the direct route and strengthen its estimates. At the end, Q(S,Right) is approximately 3.27480 and Q(S,Up) remains 0.5. Training has improved the choice without making every estimate exact.

The final rollout freezes the table and removes exploration. It follows S → A → B → goal, collecting discounted return 4.05. That observed return and the learned estimate 3.27480 are different quantities. This finite run demonstrates value propagation; it does not prove convergence.

When the Q Table Is a Useful Choice

Use a table when states and legal actions can be enumerated and revisited. The update needs a sampled (state, action, reward, next state) transition, not a labeled correct action. If the transition model and rewards are already known, planning can use them directly. Compare that planning cost with the cost of collecting more experience to improve the Q estimates.

Separate the two control decisions. Epsilon changes which experience you collect. Gamma changes how much delayed rewards count toward your objective. Lowering gamma to force a quicker-looking result solves a different reward problem. Evaluate the frozen greedy policy separately from exploratory training so that a random detour does not masquerade as its preferred action.

Time and Space Complexity

For S states and at most A legal actions per state, tabular Q-learning uses O(SA) memory. A greedy choice or next-state maximum takes O(A) time with a linear scan; committing one table entry takes O(1). Over T sampled transitions, the time complexity is O(TA). This map has three nonterminal states and two legal actions at each, so each transition costs constant work.

The number of experiences needed for a useful policy is a separate question from the cost of one update. Discovering rewards can take far longer than updating a table. Storing every animation snapshot also costs extra memory; that is a playback requirement, not part of the learning algorithm. With many or continuous states, a separate value for every state-action pair becomes impractical and many entries receive little experience. Function approximation shares information across inputs, but adds training challenges that this small table does not model.

Edge Cases

• No exploration. Set epsilon to 0 while keeping gamma at 0.9. Under this world's zero initialization and tie rule, all eight episodes take the nearby exit. Q(S,Up) reaches approximately 0.99609; Q(S,Right) stays zero. No update can extract evidence from an action the agent never tries.
• Immediate reward only. Set gamma to 0 with epsilon 0.35. The agent still encounters the goal, but Q(A,Right) and Q(S,Right) remain zero. The final start estimates are 0.9375 for Up and 0 for Right. Preferring Up is appropriate for the immediate-reward objective.
• Always exploring. Epsilon 1 samples every behavior action randomly; it still uses a maximizing target. The final evaluation remains greedy. Eight episodes do not guarantee that all useful experiences have been collected.
• Terminal versus cutoff. An exit makes future value zero. Reaching this player's eight-transition cutoff does not make the environment state terminal: the last transition still uses a nonterminal bootstrap. A repeated state during the frozen deterministic rollout is reported as a policy cycle.
• Ties. Equal estimates use a fixed action order here. Random tie-breaking would produce different experiences; the deterministic rule is disclosed so the default experiment can be reproduced.

Common Mistakes

• Treating Q as the last immediate reward. Its target includes the discounted estimate of what can happen after the move.
• Updating every earlier state when a reward arrives. One-step Q-learning changes only the experienced state-action pair; earlier entries need later visits to use the improved next-state values.
• Putting the exit reward into the target twice. It appears once as r; the terminal bootstrap is zero.
• Maximizing over unavailable moves. A dash has no action value and cannot win an argmax, even when every legal action has a negative estimate.
• Calling the exploratory trajectory the learned greedy policy. Evaluation uses the frozen table and makes its own sequence of choices.
• Assuming eight successful episodes prove optimality. The classical tabular theorem requires sufficient repeated sampling and suitable learning-rate conditions; fixed alpha over this short run establishes neither. See Watkins and Dayan's original Q-learning paper.

A Note on Simplification

This explainer uses a deterministic grid, state-dependent legal actions, a tabular estimate, fixed alpha, a curated random seed, and a short episode budget. It is not a substitute for formal reinforcement-learning study. Stochastic transitions and large state spaces complicate the problem; deep Q-learning adds function approximation and commonly uses replay buffers and target networks. Those mechanisms are omitted here. The viewer sees the map, but the learning rule uses sampled transitions rather than planning with a known world model.