Reinforcement Learning Fundamentals

SupervisedSupervised learning is taught a correct answer for every example it sees. Reinforcement learning is taught nothing of the kind — an agent takes actions in an environment, receives a reward signal that only ever says "that was worth this much," and has to work out for itself which actions, in which situations, tend to lead to good rewards later. The canonical formal treatment of the field is Sutton and Barto's textbook, and the framing below follows it closely¹.

The Markov Decision Process

TheThe environment is modelled as a Markov Decision Process (MDP): a set of states S, a set of actions A, a transition function giving the probability of moving from one state to another given an action, and a reward received on each transition. "Markov" is doing real work in that name — it's the assumption that the next state depends only on the current state and action, not on the history that led there. The agent's job is to learn a policy, written π(s), a mapping from states to actions, that maximises the total reward it can expect to accumulate over time.

"Total reward" has to account for the future being worth less certainty than the present, so it's usually written as a discounted sum: reward now, plus γ times reward next step, plus γ² times the reward after that, and so on, where γ (gamma) is a number between 0 and 1. A γ close to 0 makes the agent short-sighted, caring almost only about the immediate reward; a γ close to 1 makes it plan for the long run. This single number is one of the most consequential design choices in setting up an RL problem, and it's worth treating as a real decision rather than a default left at 0.9.

Exploration versus Exploitation

AnAn agent that always takes the action it currently believes is best will never discover that a different action might actually be better — it exploits what it knows and never explores what it doesn't. An agent that always tries something new never settles down to use what it has already learned. Balancing the two is not a minor implementation detail; it is one of the central unsolved-in-general problems of the field. The simplest practical answer is ε-greedy: take the currently-best-known action most of the time, but with small probability ε, take a random action instead, purely to keep gathering information about alternatives.

Q-Learning

RatherRather than learning a policy directly, Q-learning learns a value function: Q(s, a), an estimate of the total future reward available from taking action a in state s and then acting optimally afterwards. Once Q is known accurately, the optimal policy falls straight out of it — in any state, take whichever action has the highest Q-value. Watkins and Dayan's original algorithm updates its estimate of Q(s, a) after every single step, using the reward just received plus its own current best guess about the value of wherever it ended up²:

Q(s, a) ← Q(s, a) + α · [ r + γ · max_a' Q(s', a') − Q(s, a) ]

α (alpha) is the learning rate — how much to trust this one new piece of evidence versus everything already believed. The term in brackets is the interesting part: it's the difference between "what I now think this was actually worth" (the reward just received, plus the discounted value of the best action available from the new state) and "what I previously believed it was worth." That difference is called the temporal-difference error, and Q-learning is, at its core, nothing more than nudging an estimate a little closer to a slightly-more-informed estimate, over and over, until the two converge.

Walk it through on a minimal example: a 1×4 corridor of cells [0, 1, 2, 3], the agent starts at cell 0, can move left or right, and reaches +10 reward for reaching cell 3 (which ends the episode) and 0 reward everywhere else. Every Q(s, a) starts at 0. On the agent's first-ever successful run, every step except the last updates Q toward 0 (nothing informative has propagated back yet); the step that finally moves from cell 2 into cell 3 updates Q(2, right) upward, because r = 10 on that transition. On the next episode, the step that moves from cell 1 into cell 2 now has a non-zero max_a' Q(s', a') to bootstrap from (Q(2, right) is no longer 0), so Q(1, right) increases too — the "this leads somewhere good" signal is propagating backward through the corridor one episode at a time, purely from the bracketed correction term, with no map of the corridor given to the agent in advance.

Beyond Value Tables: Policy Methods

Q-learningQ-learning as described above needs a table entry for every (state, action) pair, which is fine for a four-cell corridor and completely infeasible for, say, every possible configuration of a video-game screen. Modern deep reinforcement learning replaces the table with a neural network that approximates Q(s, a) (or learns a policy directly), trading an exact small table for an approximate function that generalises across similar states it has never exactly seen before — the same architectures covered on Neural Network Architectures are the ones doing the approximating.

References