Learning Without a Map

An agent begins at a coordinate it has seen before but does not yet understand. It can move north, east, south, or west. Somewhere on the field is a destination; elsewhere, a costly route. There is no map of either one.

The agent receives only consequences. A move costs a little. A mistake may cost more. Reaching the destination pays well. From those local signals it has to form an answer to a global question: what should I do here?

Q-learning gives that question a remarkably concrete representation. It stores one number for every state and action. Deep Q-learning replaces the table with a neural network. That substitution makes larger worlds possible, but it changes more than storage. It changes what the learner can generalize, what we can inspect, and what we can promise about the result.

A world with delayed consequences

The usual mathematical frame is a Markov decision process:

$\mathcal{S}$ is the set of states, $\mathcal{A}$ the available actions, $P$ the transition dynamics, and $R$ the reward signal. The discount factor $\gamma \in [0,1)$ controls how much later rewards matter now.

The Markov assumption says that the current state contains the information needed to predict the next transition. It does not say that the world is deterministic. The same action in the same state may still lead somewhere different; the probability of each outcome is represented by $P$.

Starting at time $t$, the return is the discounted sum of future rewards:

An immediate reward is only one observation. The return is what the agent is ultimately trying to improve.

For a policy $\pi$, the action-value function asks what return to expect after taking action $a$ in state $s$, then following $\pi$:

A Q-table simply assigns a cell to each of those questions. For a single state $s=(r,c)$, one row looks like this:

The table is not a model of the terrain. It does not say why a wall exists or predict every consequence in advance. It records how promising each available decision has become through experience. This is why Q-learning is called model-free: it can learn action values without first estimating $P$ and $R$ as an explicit model.

A recursive target

The optimal action-value function satisfies a Bellman optimality equation:

The value of an action is its immediate reward plus the discounted value of the best decision available afterward. The equation refers back to itself. Q-learning turns that recursion into an update from a sampled transition $(s,a,r,s',d)$, where $d=1$ when the transition ends the episode:

Here, $y_t$ is the one-step target, $\delta_t$ is the temporal-difference error, and $\alpha$ is the learning rate. The terminal mask $(1-d)$ matters: after a true terminal state, there is no future value to bootstrap. The target is just the final reward.

This update moves one table entry toward a better estimate. It does not rewrite the whole map. As the destination is reached repeatedly, useful information travels backward one experienced transition at a time.

Exploration is part of the data

Always selecting the largest current Q-value would exploit what the agent already believes. Early in learning, those beliefs are mostly arbitrary. An $\epsilon$-greedy behaviour policy makes a simple compromise:

Exploration is not noise added after learning. It determines which evidence enters the table at all.

Notice the two policies in the update. The behaviour policy sometimes explores, but the target uses the greedy $\max$ action. Q-learning therefore learns about a greedy target policy while following a different behaviour policy. It is an off-policy method.

Watch a value move

The field lab below keeps the world small enough to inspect. Its purpose is not to make the agent look intelligent. It is to leave the bookkeeping visible.

Start with Step. Select a state, then follow the highlighted transition from the old Q-value through the reward, discounted next-state maximum, target, TD error, and new Q-value. The displayed equation substitutes the actual numbers from that move.

Then use Run episode and Train 25. Watch the policy arrows and value heat spread away from the destination. The episode, success, and exploration counters separate lucky arrival from repeated learning.

Three controls change different parts of the reasoning:

• $\alpha$ changes how strongly one observation revises an estimate.
• $\gamma$ changes how far future reward reaches back through the field.
• $\epsilon$ changes how often the agent gathers evidence outside its current best route.

Switch between deterministic and slippery movement to expose another distinction. In a deterministic field, one action identifies one next state. In a slippery field, a Q-value must summarize a distribution of consequences. The same update still applies, but it now needs repeated samples to estimate the expectation.

Resetting is useful here. A policy can look stable because it has learned, because the environment is forgiving, or because it has not explored enough to discover that its preferred route is fragile.

What the convergence theorem actually promises

Tabular Q-learning has an important convergence result, but “Q-learning converges” is too broad a summary. In the discounted, finite tabular setting, the classic result depends on several conditions:

• Finite representation. The state and action spaces are finite, and each action value has its own table entry.
• Bounded rewards. No transition can contribute an unbounded reward.
• Persistent exploration. Every state-action pair continues to be visited.
• Appropriate learning rates. Updates continue indefinitely while their squared magnitudes remain summable.
• Stationary Markov dynamics. Reward and transition distributions do not change during learning, with $\gamma<1$, or with suitable absorbing episodic conditions.

For every state-action pair, the learning-rate requirement is commonly written as

Under the theorem’s conditions, the table converges to $Q^*$ with probability one. A fixed $\alpha$ slider in a finite demonstration is useful for seeing the update, but it is not itself the theorem’s diminishing learning-rate schedule. Twenty-five episodes are an illustration, not a certificate.

This boundary matters because the table gives each state-action pair an independent place to settle. The proof does not automatically follow when millions of pairs share parameters inside a neural network.

When the table stops fitting

The table is exact and inspectable, but it assumes that states can be enumerated. That becomes untenable quickly. An image is not one state in a compact list; it is a high-dimensional observation. Even a modest collection of continuous sensor readings creates more possible inputs than a table can visit or store.

Function approximation changes the question from “which cell contains this value?” to “which parameters produce a useful estimate?” A Deep Q-Network uses a neural network with parameters $\theta$:

For a discrete action set, one forward pass commonly receives the state and emits an action-value vector with one estimate per action:

The agent selects among these outputs; it does not run a separate network for each action.

This permits generalization. Updating the network for one observation may also change its predictions for similar observations. That shared structure is the reason to use the network—and a source of interference that the table did not have.

Two stabilizers, not two guarantees

The DQN described by Mnih and colleagues joined Q-learning with deep neural representations for Atari observations. Two mechanisms made the learning process substantially more workable.

Replay memory stores transitions $e_t=(s_t,a_t,r_t,s_{t+1},d_{t+1})$. Training samples random minibatches from that memory rather than updating only on the newest transition. Experience can be reused, and adjacent, highly correlated observations are mixed with older ones. Replay does not make the data truly independent or erase the behaviour policy that produced it; it makes the training distribution less tightly coupled to the latest trajectory.

A target network holds parameters $\theta^-$ fixed for a period while the online network $\theta$ is updated. Without that separation, the same parameters would move both the prediction and the target at every gradient step—as if a ruler changed length while it was being used.

environment ──> replay memory ──> sampled transition
                                        │
                    ┌───────────────────┴───────────────────┐
                    ▼                                       ▼
         online network Q(·; θ)                  target network Q(·; θ⁻)
                    │                                       │
                    └──────── prediction / target ──────────┘
                                        │
                                      loss
                                        │
                                 update θ only

                     periodically: copy θ ──> θ⁻

The DQN view in the lab keeps this pipeline inspectable. Compare the table with the network representation, choose a replay sample, and trace its online estimate, target-network values, TD target, error, and loss. A target sync deliberately makes $\theta^-$ catch up; between syncs, the two networks should disagree.

Learning a moving estimate

For a sampled transition, the DQN target is

The online network is trained to reduce a temporal-difference loss such as

where $\mathcal{D}$ is the replay distribution. Practical implementations often use a Huber loss or clip errors to reduce the influence of extreme updates, but the essential structure is the same: a prediction is trained toward another learned prediction plus observed reward.

That is powerful, and it is structurally dangerous. DQN brings together the three elements often called the deadly triad:

1. Function approximation: many estimates share the same parameters.
2. Bootstrapping: the target includes another current value estimate.
3. Off-policy learning: the update’s greedy target differs from the behaviour that generated the replay data.

Together they can produce instability or divergence. Replay memory and a target network are engineering responses to that problem. They do not restore the general tabular convergence guarantee.

The maximum can be optimistically wrong

There is another subtle issue inside $\max_{a'}Q(s',a')$. Suppose several action estimates contain noise. Taking the maximum tends to select not only a good action, but an action whose error happens to be positive. The same estimates choose and evaluate the winner, so overestimation can accumulate.

Double DQN separates those jobs. The online network selects the next action:

and the target network evaluates it:

The method does not claim that either network is unbiased in isolation. It reduces the particular feedback created when one noisy maximum performs both roles.

What changes when a table becomes a network

DQN is foundational, not universal. Its “one output per action” design is naturally suited to discrete action sets of manageable size. It does not directly solve continuous control, and it is extravagant for a grid where a small table is clearer and more reliable. Sparse rewards, partial observability, non-stationarity, and poor exploration do not disappear because the value function is deep.

It is also not an explanation of how modern language-model agents work. Those systems may involve reinforcement learning somewhere in their development, but their language models, tool use, context, planning loops, memory, and training pipelines are not a DQN operating over a grid. Sharing the word agent does not make the mechanisms interchangeable.

The map was the representation

Q-learning begins with a small act of faith: that repeated local corrections can assemble a useful global policy. In the table, we can watch that assembly happen. Each value has an address. Each update has a visible destination. The limits are obvious because the representation itself runs out of room.

DQN removes that boundary by replacing addresses with approximation. A larger world becomes reachable, but the learned map is now distributed through weights, and one correction can redraw several regions at once.

That is the central trade. The network is not merely a bigger table. Scaling the representation also scales the uncertainty around learning. The right question is therefore not whether deep Q-learning is more advanced. It is whether the world is large enough to justify what becomes harder to inspect, stabilize, and guarantee.

Sources

• Watkins, C. J. C. H., and Dayan, P. “Q-learning” (1992). The original detailed convergence result for tabular Q-learning.
• Sutton, R. S., and Barto, A. G. Reinforcement Learning: An Introduction, second edition. The broader treatment of MDPs, value methods, function approximation, and the deadly triad.
• Mnih, V., et al. “Human-level control through deep reinforcement learning” (2015). The Nature DQN paper combining deep value approximation, replay memory, and a target network for Atari.
• van Hasselt, H., Guez, A., and Silver, D. “Deep Reinforcement Learning with Double Q-Learning” (2016). The Double DQN treatment of maximization bias.
• Hessel, M., et al. “Rainbow: Combining Improvements in Deep Reinforcement Learning” (2018). Onward reading on how several extensions to DQN interact.