Simple Algorithm
Artificial Intelligence · Input Layer · 17 min

Reinforcement Learning & Agents

Learning to act from trial, error and reward.

AlphaGo Zero never saw a human game of Go, and the DQN network that learned Atari games was never told their rules. Both learned from a single number, the reward, by trial and error. This lesson shows how an agent turns a stream of rewards into good decisions.

What you’ll learn

  • Describe the agent–environment loop: states, actions, rewards, policies and returns.
  • Explain the exploration–exploitation tradeoff and compare simple bandit strategies.
  • Explain how discounting and the Bellman equation define the value of a state.
  • Describe how Q-learning learns from experience, and where deep RL and reward design fit in.

Learning from a score

How do you teach a machine a skill you cannot demonstrate, like balancing a robot or finding a winning strategy nobody knows? You let it try, and you score the results.

In reinforcement learning, an agent observes the state of its environment, takes an action, and receives a new state and a reward. Its rule for choosing actions is its policy, and its goal is to maximize the total reward collected over time, the return. Nobody says which action was right; the reward only scores what happened, and often much later.

AspectSupervised learningReinforcement learning
FeedbackThe correct answer for each exampleA reward: how good the outcome was
TimingImmediateOften delayed (a game is won only at the end)
DataA fixed datasetGenerated by the agent's own actions
Delayed rewards create the credit assignment problem: which of many earlier actions deserves the credit?

Explore or exploit?

Five slot machines pay out at different, unknown rates. On each pull, do you play the machine that has paid best so far, or try another that might be better? This is the multi-armed bandit, RL with a single state, and it isolates the exploration–exploitation tradeoff.

A greedy strategy always plays the best average so far. ε-greedy explores a random arm a fraction ε\varepsilon of the time. UCB is optimistic: it adds a bonus to arms it is unsure about. Thompson sampling plays each arm with the probability that it is the best. All are scored by regret: the reward lost compared with always pulling the best arm.

Check your understanding

UCB picks the arm with the largest μ^a+cln⁡t/na\hat\mu_a + c\sqrt{\ln t / n_a}, where μ^a\hat\mu_a is the arm's average so far and nan_a its number of pulls. Which arm gets the biggest bonus?

  1. The arm with the highest average
  2. The arm pulled the fewest times so far
  3. The arm pulled most recently
  4. Every arm gets the same bonus
Show the answer

B. The arm pulled the fewest times so far

The bonus shrinks as nan_a grows. Rarely tried arms get a big bonus, so UCB keeps trying them until it is confident they are worse: optimism in the face of uncertainty. Its regret grows only logarithmically with time, while greedy can lock onto a bad arm and lose a little on every pull forever.

What a state is worth

Most problems have many states, and actions have consequences later. A reward now is usually worth more than the same reward later, so the return discounts each step by a discount factor γ\gamma between 0 and 1: G=r1+γr2+γ2r3+⋯G = r_1 + \gamma r_2 + \gamma^2 r_3 + \cdots

Predict before you look

With γ=0.9\gamma = 0.9, a reward of 1 that arrives 10 steps from now is worth how much today?

Show the answer

0.35

0.910≈0.350.9^{10} \approx 0.35. Discounting makes the return finite and prefers sooner rewards. With γ=0.99\gamma = 0.99 the same reward would still be worth about 0.900.90: a far-sighted agent.

The value of a state is the expected return from it when acting well. Values obey a consistency condition, the Bellman equation: a state is worth the best you can do by choosing one action now, its expected reward plus the discounted value of wherever you land.

V(s)=max⁡a∑s′P(s′∣s,a) [R(s,a,s′)+γV(s′)]V(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\big[R(s,a,s') + \gamma V(s')\big]

Value iteration applies this update to every state, over and over, until nothing changes.

Learning values from experience

Value iteration needs the map: every transition probability and reward. An agent in the real world rarely has one. It can only act and see what happens.

Q-learning (Watkins, 1989) learns a Q-value for every state–action pair straight from experience. After taking action aa in state ss, receiving reward rr and landing in s′s', it nudges its estimate toward one real reward plus the discounted value of the best next action:

Q(s,a)←Q(s,a)+α [ r+γmax⁡a′Q(s′,a′)−Q(s,a) ]Q(s,a) \leftarrow Q(s,a) + \alpha\,\big[\,r + \gamma \max_{a'} Q(s',a') - Q(s,a)\,\big]
α\alpha is the learning rate. Updating a guess toward a better guess is temporal-difference learning.
Check your understanding

What must a Q-learning agent know about the grid before it starts?

  1. The probability of every move's outcome
  2. Where the +1+1 and −1-1 exits are
  3. The optimal values, to have something to learn toward
  4. Nothing about the dynamics: it learns from the transitions it experiences
Show the answer

D. Nothing about the dynamics: it learns from the transitions it experiences

Q-learning is model-free: it needs only the states, actions and rewards it observes. The price is experience: it must try actions, sometimes badly (here with ε\varepsilon-greedy exploration), to learn what they do.

Scaling up, and agents in the world

A table with one entry per state is hopeless for Go, which has more legal positions than there are atoms in the observable universe. Deep Q-networks (Mnih et al., 2015) replaced the table with a neural network reading raw screen pixels, stabilized by experience replay, and learned 49 Atari games from pixels and score alone, reaching human level on many of them.

Policy-gradient methods skip values and adjust a policy network directly, making actions that led to high return more likely. Actor–critic methods add a learned value estimate to reduce the noise, and PPO (2017) became a workhorse, including for fine-tuning language models from human feedback.

In the Hidden Layer you'll study RL Foundations (rewards, returns, value functions and exploration), Temporal-Difference Learning & Q-Learning, Policy Gradients & Actor–Critic, and Agents in the World: many agents learning together, where Nash equilibria replace single optima, robots trained in simulation, and language models acting as agents that plan and use tools.

Key takeaways

  • An RL agent acts, receives a reward and a new state, and learns a policy that maximizes its long-term return.
  • Exploration versus exploitation: greedy strategies can lock onto a bad choice, while ε-greedy, UCB and Thompson sampling keep learning.
  • Discounting makes later rewards count less; values obey the Bellman equation, which value iteration solves when the model is known.
  • Q-learning learns action values from experience alone, nudging each estimate toward reward plus the discounted best next value.
  • Deep RL scales these ideas with neural networks (DQN, policy gradients, AlphaZero), but reward design and sample efficiency remain hard.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What most distinguishes reinforcement learning from supervised learning?

  1. RL uses neural networks and supervised learning does not
  2. RL does not need any data
  3. RL gets a reward that scores its actions, often delayed, instead of being told the correct action
  4. RL only works in games
Show the answer

C. RL gets a reward that scores its actions, often delayed, instead of being told the correct action

The feedback is evaluative, not instructive: a reward says how well things went, not what should have been done, and the agent's own actions decide what data it sees.

Question 2

A bandit strategy always pulls the arm with the best average so far. After a lucky start, arm 2 looks best, although arm 4 is truly better. What tends to happen?

  1. It keeps pulling arm 2 and may never learn that arm 4 is better
  2. It soon switches to arm 4, because averages always converge to the truth
  3. It cycles through all the arms equally
  4. It stops pulling arms
Show the answer

A. It keeps pulling arm 2 and may never learn that arm 4 is better

Greedy revisits arm 4 only if arm 2's average happens to sink below arm 4's unlucky estimate, so the mistake can persist indefinitely and regret grows with every pull. Exploration (ε-greedy, UCB, Thompson sampling) exists to prevent exactly this.

Question 3

What does a discount factor γ\gamma close to 0 make an agent do?

  1. Plan far ahead, valuing distant rewards almost as much as immediate ones
  2. Explore more
  3. Ignore negative rewards
  4. Care almost only about the next reward, ignoring long-term consequences
Show the answer

D. Care almost only about the next reward, ignoring long-term consequences

A reward kk steps ahead is weighted by γk\gamma^k. With γ\gamma near 0 the weights vanish after a step or two, so the agent is short-sighted; near 1 it is far-sighted.

Question 4

Q-learning updates Q(s,a)Q(s,a) toward r+γmax⁡a′Q(s′,a′)r + \gamma\max_{a'}Q(s',a'). What is this target?

  1. The true value of (s,a)(s,a), known in advance
  2. The reward just received plus the discounted value of the best next action, by current estimates
  3. The average reward over all past episodes
  4. The value of a random action in s′s'
Show the answer

B. The reward just received plus the discounted value of the best next action, by current estimates

It is a bootstrapped target: one real reward plus the current guess of what follows. Repeated updates spread reward information backward, and with enough exploration and suitably shrinking step sizes, tabular Q-learning converges to the optimal Q-values (Watkins & Dayan, 1992).

Further reading

  • R. S. Sutton & A. G. Barto, Reinforcement Learning: An Introduction, ch. 1–6 (MIT Press, 2nd ed., 2018).
  • V. Mnih et al., "Human-level control through deep reinforcement learning", Nature (2015).