Learning control, from rules to deep Q-networks

Learning from consequences

Reinforcement learning studies how an agent should act inside an environment it does not fully control. At each step it sees the current situation, chooses an action, and receives a reward and a new situation. Nobody supplies the correct action; the agent sees only the reward that followed, and from that alone must work out which choices pay off over time. The hard part is delay: a move that looks good now can lead somewhere bad, and a small early sacrifice can set up a much larger gain later.

This project gathers seven course tasks as one progression, from behavior written by hand to behavior learned from experience. A card game and a car on a hill set the baseline for what fixed or random behavior can do. A server network writes an environment’s rules down explicitly. A frozen lake is the first task that learns, by averaging the outcomes of complete games; tic-tac-toe learns after every move instead. A small regression network then checks whether a neural network can replace a lookup table at all, before a racetrack task combines everything into a deep value function. Each step adds one idea and exposes one new way to fail.

Underneath every task is the same accounting. Write the situation at step $t$ as the state $S_t$, the action as $A_t$, and the reward that follows as $R_{t+1}$. The agent maximizes not the next reward but the discounted return

\[ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots, \]

the whole stream of future rewards, each multiplied by the discount factor $\gamma$ raised to a higher power the further away it lies. The discount sits between 0 and 1 and sets how far ahead the agent looks: at $\gamma=0$ only the immediate reward matters, while near 1 a distant reward counts almost as much as one now. Keeping $\gamma$ below 1 also keeps the sum finite. This single quantity connects a hand of cards to a car on a hill to a board game.^[01]01Sutton and Barto (2018), Reinforcement Learning: An Introduction, second edition.

Following a fixed rulebook · Blackjack

Blackjack is a familiar place to start because most readers already know the goal: draw cards to get as close to 21 as possible without going over, and beat the dealer. The only decision is whether to take another card (hit) or stop (stick), based on what can be seen: the player’s current total, the dealer’s face-up card, and whether the player holds an ace that may count as either 1 or 11.

This first task does no learning at all. It runs a fixed rulebook that maps each visible situation to hit or stick. The rule is cautious when the dealer looks weak and more willing to draw when the dealer shows an ace or a high card. With a usable ace the player can afford more risk, because that ace can drop from 11 to 1 to avoid going bust. The grid below is the entire rule.

With the rule fixed, the only question left is how good it is. The value of a fixed policy is measured by Monte Carlo policy evaluation: play many independent games and average the outcomes, the same averaging the later tasks turn into a learning rule. Across three seeds of 10,000 games each, the heuristic wins $43.4\%$ of games with a mean return near zero ($-0.041$ chips), while random hit-or-stick play wins only $28.1\%$ and returns $-0.397$. A rule that simply reads the state is far better than no rule, yet it never improves, because it ignores the outcomes it sees. Every task after this one adds exactly that missing ingredient: learning from experience.

When random moves are not enough · Mountain-car

Blackjack showed a fixed rule that at least reads the state; this task shows what happens when behavior ignores the state entirely. An underpowered car sits in a valley and has to reach a flag on the right-hand hill. Its engine is too weak to climb straight up, so the only way out is to rock back and forth, building momentum by first driving away from the goal and then reversing at the right moment.

The policy here is random: at each step it picks an acceleration with no regard for what came before. A successful escape is a carefully timed sequence, but random actions have no memory, so each push tends to undo the last. The reward makes this worse: the car is penalized on every step until it reaches the flag, which it almost never does, so it almost never sees the one outcome that shows what good behavior looks like. This is the credit-assignment problem at its starkest: when reward is delayed and rare, trial and error leaves nothing to learn from.

The outcome is the same across the whole evaluation: zero successes in 300 episodes, every episode running to its 999-step limit, and a return near $-33$. Failure is the useful result. It shows that exploration cannot mean uniformly random flailing; it has to produce coordinated experience a learning rule can latch onto.

Writing the rules of the world down · Server network

The earlier tasks came from ready-made simulators; this one is defined from scratch, which makes every rule of the environment visible. Six servers form a small network. Each is either running or crashed, and crashes are contagious: a server is more likely to go down when more of its neighbors are already down. An administrator can maintain one server per step, which forces that server back online. Two servers are neighbors when a link joins them, and only a server’s own neighbors raise its crash risk.

This is a Markov decision process written out in full. The state is which servers are up or down, a list of six on-or-off values; the action is which single server to maintain; the transition rule is the crash model; and the reward is the negative fraction of crashed servers, so a reward closer to zero means a healthier network. Because a crash spreads through neighbors, the probability that server $i$ goes down on a step is

\[ p_i(\text{crash}) = \varepsilon {}+ \alpha\frac{\text{crashed neighbors of }i}{\deg(i)}, \qquad \varepsilon=0.1,\quad \alpha=0.5. \]

Here $\varepsilon$ is a small baseline chance that any server fails on its own, $\alpha$ scales how strongly neighbors drag each other down, and the fraction is the share of server $i$’s neighbors, out of its total count $\deg(i)$, that are currently crashed. Raising $\varepsilon$ makes failures more random; raising $\alpha$ makes them more infectious.

Writing the dynamics down also pins down what “better” means. The value of a policy $\pi$ from a state is its expected return, $V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$, so comparing two policies is comparing this value. The full task has $2^6 = 64$ states, but a single server tells the story. It is either up or down; maintaining it forces it up next step; and if left alone while up it crashes with probability $p_c = \varepsilon + \alpha\,(\text{crashed neighbors}/\deg)$. The diagram below evaluates the crashed-first idea on one server, leave it while up and maintain it once down, taking $p_c = 0.35$ for a server with half its neighbors down and a discount $\gamma = 0.9$.

Each state’s number is its value under this policy. The numbers come from the Bellman expectation equation, which says a state’s value is the reward earned now plus the discounted value of wherever the policy moves next. Being up is worth slightly more than being down, and both sit near zero because the policy keeps repairing. No learning happens yet; the point is only to score two fixed policies on the same explicit model, one maintaining a random server, the other crashed-first. As in Blackjack, the reported scores estimate these values by averaging returns over many simulated episodes.

Over 1,000 hundred-step episodes per seed, random maintenance scores about $-66$, while repairing a crashed server first scores about $-49$. The replay shows why: fixing a failed node early cuts off a chain of infection before it reaches that node’s neighbors. The crashed-first rule still looks only one step ahead, but it uses the state in a way the random rule does not.

Learning from finished games · Frozen lake

So far nothing has learned. The frozen-lake task is the first that improves from its own experience. The agent has to cross a small grid from a start tile to a goal tile without stepping into a hole, choosing one of four moves at each square.

It learns by first-visit Monte Carlo control, which builds directly on the discounted return $G_t$ from the introduction. The agent plays a full episode, then for each state-action pair it visited, takes the return that followed the first time it chose that action and folds it into a running average:

\[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) {}+ \frac{1}{N(S_t,A_t)}\bigl(G_t-Q(S_t,A_t)\bigr). \]

Reading left to right: $Q(S_t,A_t)$ is the current estimate of how good action $A_t$ is in state $S_t$, measured as the return it expects to earn; $G_t$ is the return actually observed after that pair; and $N(S_t,A_t)$ counts how often the pair has been seen, so $1/N$ shrinks each update as evidence piles up and lets the estimate settle onto its true average. The agent then acts greedily with respect to $Q$, preferring the highest-valued action, while an $\varepsilon$-greedy rule still takes a random action a fraction $\varepsilon$ of the time so every option keeps being tried. The run uses the deterministic $4\times4$ lake, $\gamma=0.9$, 100 episodes per iteration, and $\varepsilon$ decaying from 0.5 to 0.1.

The interesting part is not that a full 50-iteration run solves the lake, but how a reasonable-looking shortcut fails. A naive stopping rule halts as soon as the largest change in $Q$ drops below 0.5. Because early episodes can leave $Q$ briefly unchanged before informative outcomes arrive, that rule stops after only 2 to 4 iterations, and one resulting policy fails all 500 test games. Requiring at least 10 iterations before applying the same tolerance removes that failure here.

The policies below make the difference concrete. The fully trained seed-21 policy reaches the goal in six moves. The prematurely stopped seed-87 policy moves down once, then repeatedly picks an action that cannot change its square, so the video skips from that loop to the 100-step timeout.

Episode SuccessFailure

Learning after every move · Tic-tac-toe

Monte Carlo control had to wait for a whole game to finish, because it needs the full return $G_t$. Q-learning removes that wait: it updates after every move, using its own current estimates to stand in for the rest of the game. That substitution is called bootstrapping.

After each move it adjusts the value of the action it just took toward a one-step target:

\[ Q(s,a) \leftarrow Q(s,a) + \alpha \left[r + \gamma\max_{a'}Q(s',a') - Q(s,a)\right]. \]

The bracket is the temporal-difference error: the gap between the current estimate $Q(s,a)$ and a fresh target, $r + \gamma\max_{a'}Q(s',a')$, that combines the immediate reward $r$ with the discounted value of the best action in the next state $s'$. The step size $\alpha$ sets how far each move nudges the estimate: larger learns faster but reacts more to noise, smaller is steadier but slower. Because the target uses $\max_{a'}$, the update always aims at the greedy next action even while an $\varepsilon$-greedy policy explores, which is what makes Q-learning off-policy.^[02]02Watkins and Dayan (1992), “Q-learning,” Machine Learning 8, 279–292.

In tic-tac-toe the state is the full $3\times3$ board, so the table stores one value per reachable board. Occupied squares are masked as illegal, and each step bundles the agent’s move with the fixed opponent’s reply unless the game has ended. Four supplied opponents were trained against separately: 5,000 games of learning, then 100 greedy games to score.

Win rates land between 83% and 88% across the four opponents. Policy 2 has the highest mean, but 100 games per seed are too few to rank them with confidence. The solid result is shared by all four: the same update rule learns a strong policy against different fixed behaviors, and the replay lets you step through its choices one move at a time.

Can a neural network stand in for the table?

Every learning task so far kept one value per state in a table. That works while states are few, but a table cannot generalize: it says nothing about a state it has never visited, and it grows with the number of possible states. The racetrack ahead has far too many, so the plan is to replace the table with a neural network that predicts values from the state directly. Before trusting a network inside the noisy learning loop, this task checks it on its own.

The check is ordinary supervised regression, stripped of everything reinforcement-specific. A small $3\rightarrow5\rightarrow2$ network takes an input $x\in[0,1]^3$ and must reproduce two functions whose answers can be computed exactly:

\[ f_1(x)=\sum_i x_i^2, \qquad f_2(x)=\sum_i x_i. \]

Because the true targets are known for any input, any remaining error must come from the network and its optimizer, not from delayed rewards or shifting data. Across three seeds, 2,000 Adam steps cut the test error from about $2.82$ to $0.02$.

The parity plots make the point: predictions that started scattered end up close to the diagonal, where prediction equals target. This is a clean bill of health for the machinery, gradients, batching, an optimizer, and a held-out test set, before bootstrapped targets are allowed to complicate it.

From a lookup table to a deep network · Racetrack

The racetrack task needs everything at once. A car has to drive from a start line to a finish line along a bent track without hitting a wall. Its state is four numbers, position and velocity in two dimensions $(x,y,v_x,v_y)$, and each action nudges its acceleration. Action noise sometimes overrides the command, hitting a wall ends the episode with reward $-20$, and crossing the finish returns $+100$. A good policy accelerates early, keeps enough speed through the bend, then eases off to slip through the narrow finish.

The tabular agent reuses the exact Q-learning update from tic-tac-toe, but position and velocity are effectively continuous, so a table would need an entry for every combination, far too many to fill. This is where the previous task’s network earns its place. A deep Q-network replaces the table with a two-hidden-layer network that predicts action values from the four state numbers, trained to minimize

\[ \mathcal L(\theta) = \left(Q_\theta(s,a)-y\right)^2, \qquad y=r+\gamma\max_{a'}Q_{\bar\theta}(s',a'). \]

Here $\theta$ are the network’s weights, $Q_\theta(s,a)$ its predicted value, and $y$ the same one-step target as Q-learning, now produced by a network. The catch is that $y$ depends on the network’s own output, so the quantity being predicted moves every time the weights change. Two DQN ingredients tame that moving target in stages. Replay DQN stores past transitions in a 10,000-step buffer and trains on random samples, breaking the strong correlation between consecutive steps. DQN with a target network goes further, computing $y$ from a second, slowly updated copy of the weights $\bar\theta$, so the target holds still long enough for the main network to chase it.^[03]03Mnih et al. (2015), “Human-level control through deep reinforcement learning,” Nature 518, 529–533.

The plain online network fails outright despite more than six million steps per seed, because it chases a target that shifts on every update. Replay alone is not reliably enough: one seed finishes at 98%, another reaches 96% in training then collapses to zero. Adding the slowly moving target network makes all three seeds succeed. It stays noisy, one seed finishes at 73% and evaluations still swing, but consistent failure is no longer the outcome.

The learned behavior is easier to read on the map than in a single success rate. A separate seed-87 run saved the final checkpoint with both a successful and a crashing episode. The selector below replays either one; these are illustrative, while the three-seed chart above remains the evidence.

Trajectory SuccessFailure

What the sequence shows

The seven tasks expose three distinct reasons a decision system can fail, and each one appears exactly where the method changes:

• The behavior cannot learn at all. Random mountain-car actions explore individual controls but never assemble them into a momentum-building sequence.
• The estimate is trusted too early. The frozen-lake shortcut mistakes a small, temporary change in $Q$ for real convergence and stops before the evidence is in.
• The learning target will not hold still. Online DQN bootstraps from the very network it rewrites on every step; replay helps, and a separate target network makes success repeatable.

The successes lean on different kinds of structure. Blackjack builds domain knowledge straight into the rule. The server network exploits a causal feature of the current state. Monte Carlo control averages complete returns. Tabular Q-learning bootstraps while keeping one independent value per observed state. A deep Q-network shares information across states through a neural network, gaining reach but inviting the instability that replay and a target network exist to control.

Limitations

Three seeds expose variance but do not support precise confidence intervals or fine-grained method rankings. The racetrack configurations differ in training budget and learning rate, so their comparison is diagnostic rather than controlled. The frozen-lake experiment is deterministic and small, so its stopping-rule lesson may change under slippery dynamics. Blackjack and the server network compare hand-written policies, not learned optimal ones. Tic-tac-toe uses only 100 evaluation games per seed. Finally, the interactive trajectories are representative episodes, not summaries of every path seen during training.

Conclusion

Rebuilding the exercises as scripts turned a set of disconnected demos into one experimental story. A fixed policy can be strong when useful knowledge is already available. Monte Carlo and tabular temporal-difference learning improve behavior from experience without any model of the world. Neural approximation scales the value function up to states a table could never hold, but replay and a target network are not cosmetic additions: on the racetrack, they are what separate consistent learning from outright failure or seed-dependent collapse.

The result is therefore not just a set of solved environments. It is a record of where each new idea becomes necessary, and of the failures that make that necessity visible.