A modern approach to AI · Chapter 22

Reinforcement Learning

An agent improves its behavior by acting, observing consequences, and learning which choices lead to long-term reward.

Chapter guide

  1. 22.1 Learning from Rewards — Rewards score outcomes; value estimates expected future return, not just immediate payoff.
  2. 22.2 Passive Reinforcement Learning — With a fixed policy, estimate utilities or transition/reward models from experience.
  3. 22.3 Active Reinforcement Learning — Choose actions while learning; exploration trades short-term reward for information.
  4. 22.4 Generalization in Reinforcement Learning — Function approximation shares learning across similar states, but can introduce errors.
  5. 22.5 Policy Search — Optimize policy parameters directly using sampled returns or policy gradients.
  6. 22.6 Apprenticeship and Inverse Reinforcement Learning — Infer preferences from demonstrations, then learn a policy that reflects them.
  7. 22.7 Applications of Reinforcement Learning — Control, games, scheduling, and resource allocation require careful objectives and safe evaluation.

Interactive: learn a route

Tabular Q-learning on a tiny deterministic grid. Reach the goal (+10); each move costs −1. The agent explores random actions, then increasingly favors its learned values.

Ready. Start at the upper-left; goal is lower-right.

Episode 0 · Total reward 0

How Q-learning updates a route

State is the current cell, action is a legal move, and Q(s,a) estimates the discounted return for taking that move. The exploration rate ε chooses a random legal action with probability ε; otherwise the agent chooses a legal action with a largest current Q-value.

a ← ε-greedy(Q[s, ·])
s′ ← result of a; observe reward r
Q[s,a] ← Q[s,a] + α (r + γ maxₐ′ Q[s′,a′] − Q[s,a])

Here α = 0.35 and γ = 0.9. For example, if Q[s,a]=2, r=−1, and max Q[s′,·]=4, the target is −1+0.9×4=2.6, so the update gives 2+0.35×(2.6−2)=2.21. For terminal transitions the target is just the observed reward; the code takes a maximum only over legal actions at nonterminal next states.

Assumptions and cost

This is a deterministic, fully observed grid with fixed rewards and a tabular Markov state (the current cell is assumed to contain all decision-relevant information). The hazard ends an episode with −5; reaching the goal ends it with +10; other moves cost −1. Random exploration means an episode is not guaranteed to finish in a bounded number of moves.

Complexity. Let S be the number of states and A the maximum legal actions per state. Q-learning's selection/update costs O(A) time per move, with O(A) temporary legal-action storage; the Q-table uses O(SA) auxiliary space. Redrawing all grid cells adds O(S) visualization time and O(S) DOM memory per move, separate from the table. For this fixed 4×4 world with four moves, total work and table memory per step are O(1). There is no finite worst-case total bound per episode because random actions can loop.