In supervised learning every example comes with the right answer. In reinforcement learning (RL) an agent lives in an environment: at each step it sees a state, picks an action, and gets a reward and a new state. Nobody says which action was right. The agent only learns, by trial and error, which sequences of actions pile up the most reward. The lecture covers the vocabulary (policy, reward, discounted return), then two ways to learn. Q-learning learns a table of "how good is action in state ". Deep Q-networks replace that table with a neural network, so the same idea scales to raw game pixels. Policy gradients skip the table and adjust a policy network directly. It ends with AlphaGo Zero and the open problems of using RL on real robots and cars. This was the last lecture of the course; nothing in it was flagged for homework or the exam.
After this you canTeaching by experience
The course has covered supervised, unsupervised and semi-supervised learning. Reinforcement learning is the fourth kind. Slide 3 points out that all of them are "supervised" by something: someone has to say what's good and what's bad. What changes is the form that judgment takes.
| Supervised learning | Reinforcement learning | |
|---|---|---|
| Slogan (slide 4) | "Teach by example": here are examples, learn the pattern | "Teach by experience": here is a world, learn by exploring it |
| Feedback | The correct label for every input | A reward, often delayed, for a whole sequence of actions |
| Output | A prediction (class, number) | A policy: which action to take in each state |
| Data | A fixed dataset | Generated by the agent's own actions |
The professor's example (03:04): teaching a baby to walk to the couch. If the baby falls halfway, that attempt gets a negative reward; if it makes it, a positive one. Nobody tells the baby which muscle to move at which instant. Rewarding whole attempts is enough to steer it toward the action sequences that work.
Deep RL = RL + neural networks (slide 2). Slides 7–14 build this up as a perception–action pipeline. Deep learning (weeks 13–15) handles the front half: turning raw sensor data into useful features and making one decision, like "this image is a duck". RL adds the back half: reasoning and planning over a sequence of decisions, where each action changes what the agent sees next.
A toddler learns to walk from a handful of falls; an RL agent may need millions of trials. Slide 6 offers three guesses: our "hardware" carries 230 million years of evolution of walking on two legs, we imitate other people, and the brain's learning algorithm is probably better than backpropagation and SGD. The professor stresses that nobody really knows. RL is an attempt to copy that kind of learning.
The agent–environment loop
At every time step the agent does three things (slide 15): it executes an action , observes the new state , and receives a reward . Then it repeats. One run from a start state to a terminal state is an episode, and the record of it is a trajectory:
Slide 17 lists what an agent may learn, directly or indirectly:
- Policy : the agent's behavior, a map from state to action. It can be deterministic, , or stochastic, = probability of action in state .
- Value function: how good each state () or each state–action pair () is, measured as expected future reward.
- Model: the agent's own picture of the environment, meaning what state and reward each action will lead to.
| Task (slides 19–21) | State | Actions | Reward |
|---|---|---|---|
| Cart-pole: balance a pole on a moving cart | Pole angle, angular speed, cart position, cart velocity | Horizontal force on the cart | +1 for every step the pole stays upright |
| Doom: eliminate all opponents | Raw game pixels | Up, down, left, right, shoot, … | Positive for eliminating an opponent, negative when the agent is eliminated |
| Robot grasping: pick up objects of different shapes | Raw camera pixels | Move arm, grasp | Positive when the pickup succeeds |
Environments differ along several axes (slide 16), and each one changes which methods work: fully vs partially observable (chess vs poker), single vs multi-agent (Atari vs traffic), deterministic vs stochastic (cart-pole vs traffic), static vs dynamic, and discrete vs continuous (chess moves vs cart-pole forces). Slide 22's takeaway: the algorithms are the fun part. The hard part is defining a useful state space, action space and reward, and the hardest part is getting meaningful data for that formalization.
The professor says several times that, given and , the next reward and state "will be deterministic", so you "can easily know" them. That holds only in deterministic environments like cart-pole. Slide 16 itself lists stochastic environments, and in general the next state is random: . More importantly, a model-free learner like Q-learning does not know and in advance. It finds them out by taking the action and observing what the environment returns (Géron, "Temporal Difference Learning"; Mitchell §13.3).
In cart-pole, what is the agent's policy, and what does the reward encourage?
The policy maps the 4-number state (angle, angular speed, position, velocity) to a force on the cart. Since every upright step earns +1, total reward is the number of steps survived, so the reward encourages keeping the pole up as long as possible.
Return and discounting
"Meaning of life for an RL agent: maximize reward" (slide 18). But not the reward of one step: the total of all rewards from now on, called the return (the slides call it "future reward"). Rewards far in the future are worth less, so each one is multiplied by a discount factor per step of delay:
- discounted return from time ("discounted future reward")
- reward of a single step
- discount factor, ; typical values 0.9 to 0.99
- last step of the episode (can be )
The return obeys a one-step recursion, which is the seed of everything in Sections 4–8:
Why discount at all? Slide 18 gives two reasons, and the professor spends most of his time on the first:
- A math trick for convergence. If every reward satisfies , the discounted sum can never blow up, even over an infinite episode. That bound is what makes convergence proofs possible:
- Uncertainty. The environment is random, partly hidden, and "life can end at any moment". One way to read : at each step there's a chance the episode stops, so a reward steps away only arrives with probability .
An episode pays : three steps that each cost 1, then the goal. Compute the return backward with :
Check forward: . Without discounting the return would be . The goal's +10 shrinks to 7.29 because it is three steps away. Géron's version: rewards with give .
Slide 17 numbers the reward that follows action as , and so do slide 26 and Géron. Slide 18 starts the return at , which is Mitchell's convention (reward for the step taken at time ). Both are fine as long as the first reward counts with weight . Also, at 16:18 the lecture calls the return "a linear combination of different states". It's a weighted sum of rewards, with weights
Credit assignment. Rewards are often sparse and delayed. When the pole finally falls after 100 steps, which of the 100 actions was to blame? Scoring each action by the discounted return that follows it is the standard answer (Géron's "credit assignment problem"). That idea comes back in policy gradients (Section 10).
All rewards lie in and . What is the largest possible return?
, reached by getting reward 1 at every step forever.
MDPs and the Bellman equation
The lecture mentions the "Bellman optimality equation" on slide 26 but says "I don't want to go in deep". It's the foundation of Q-learning, so here it is from the textbook. The standard model of an RL environment is a Markov decision process (MDP):
- a set of states and, in each state, a set of allowed actions;
- transition probabilities = probability of landing in after taking in ;
- rewards for each transition;
- a discount factor .
"Markov" means the next state depends only on the current state and action, not on the history before it. The current state contains everything the agent needs.
The optimal state value is the expected discounted return from if the agent acts optimally from then on. Bellman showed it satisfies a recursive equation: the value of a state equals the best action's expected immediate reward plus the discounted value of where you land.
The same idea for state–action pairs gives the optimal Q-value : the expected return if you take in now and act optimally afterward.
- how good state is under optimal play
- how good action is in state (then optimal play)
- "from the next state on, take the best action"
- optimal policy: in each state, the action with the largest
The last line is why Q-values are so useful. With in hand, acting optimally needs no lookahead and no model: just pick the row maximum. With only , you'd also need and to know which action leads to the good states (Mitchell §13.3).
Value iteration turns the Bellman equation into an algorithm: start with all values at 0 and apply the right-hand side repeatedly. The estimates are guaranteed to converge to the optimal values. Q-value iteration does the same with Q. Both are dynamic programming, which the professor mentions at 31:30: break a big problem into a recursion and fill in a table.
Start with every Q at 0. One round gives each Q its expected immediate reward:
, , , all others 0.
Round two adds discounted future value. For example:
Run it to convergence (about 50 rounds) and you get:
| State | a0 | a1 | a2 | Best |
|---|---|---|---|---|
| s0 | 18.92 | 17.03 | 13.62 | a0 |
| s1 | 0 | n/a | −4.88 | a0 (stay) |
| s2 | n/a | 50.13 | n/a | a1 |
With , the −50 fire isn't worth it: stay in s1. With the agent values the later +40s more and , so the policy flips to "go through the fire". (These match Géron's printed values; computed in Python.)
Why can't an agent use value iteration in a game it has never played?
Value iteration needs and for every transition. A new agent doesn't know them. It has to learn from experience, which is what Q-learning (Section 7) does.
Value iteration on a grid world
Mitchell's grid world is the classic small example. Six cells; the agent can move up, down, left or right to a neighboring cell. Every move earns 0 except a move into the goal G, which earns +100. G is absorbing: once there, the episode is over. Moves are deterministic, so for the cell you move to, and the Bellman update simplifies to
where is the cell that action leads to.
| Iteration k | s1 | s2 | s4 | s5 | s6 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 100 | 0 | 0 | 100 |
| 2 | 90 | 100 | 0 | 90 | 100 |
| 3 | 90 | 100 | 81 | 90 | 100 |
| 4 | 90 | 100 | 81 | 90 | 100 |
- k = 1: only the two cells next to G (s2 and s6) can earn anything in one step: .
- k = 2: s1 can move right into s2: . Same for s5 (up to s2 or right to s6).
- k = 3: s4 is three moves from G: .
- k = 4: nothing changes, so the values have converged: the table's last row. Each value is .
From you also get every Q-value: . For s1, "right" gives and "down" gives . The 72.9 matches Mitchell's Figure 13.3.
Slide 28 says value iteration is impractical for Atari Breakout because the state is 4 grayscale frames of pixels with 256 levels each: rows in the table. The slide's "" is off. Since , the row count is , and its base-10 exponent is
so the count is about . The point stands: it dwarfs the atoms in the universe.
If γ were 0.5 instead of 0.9, what would V*(s4) be? Would the policy change?
s4 is 3 moves from G: (and s1 = s5 = 50, s2 = s6 = 100). The policy doesn't change: with all-zero step rewards, any prefers the shortest path.
Three families of RL methods
The professor sorts RL methods by sample efficiency: how much experience they need before they behave well.
- Model-based (slide 23): learn a model of the world, then plan with it; update the model and re-plan often. The professor's analogy is a map: once you have it, the planning is cheap.
- Value-based: learn or , then act by choosing the best action in each state. Because the greedy choice is deterministic, the agent will never try anything new unless you add exploration on purpose (Section 8). Q-learning and DQN live here.
- Policy-based: learn a stochastic policy directly and act by sampling from it. Exploration is "baked in", because a stochastic policy tries different actions by itself. REINFORCE lives here.
Slide 24's taxonomy (from OpenAI Spinning Up) splits the field first into model-free (policy optimization: policy gradient, A2C/A3C, PPO, TRPO; Q-learning: DQN, C51, QR-DQN, HER; and hybrids DDPG, TD3, SAC) and model-based (learn the model: World Models, I2A, MBMF, MBVE; or be given the model: AlphaZero). The lecture covers one example from each model-free branch, DQN and REINFORCE, and touches AlphaZero.
Introducing policy gradients, the professor says that for the value-based method "you have the data, you have the model together". Q-learning and DQN are model-free: slide 24 puts them under "Model-Free RL", and they never learn or . They learn values, which sit between learning a full model and learning a policy outright.
Why does a value-based method need exploration "added on" while a policy-based method has it built in?
A value-based agent acts by , which always picks the same action in a given state, so without extra randomness it never tests the alternatives. A policy-based agent samples from , which gives every action some probability until it learns otherwise.
Q-learning
Value iteration needs the transition probabilities and rewards. Q-learning doesn't. It keeps a table with one row per state and one column per action, plays the game, and after each step nudges one cell toward what it just saw. The definition (slide 26): is the expected return when starting in , performing , and following policy afterward. Q-learning aims straight at , the optimal one.
- the state the agent was in and the action it took
- the reward and next state the environment actually returned
- learning rate,
- discount factor
- value of the best action in the next state, read from the current table
- bracket
- the TD error : how much the new evidence disagrees with the old estimate
Read it as "move the old estimate a fraction of the way toward the target". The target is a one-sample estimate of the Bellman right-hand side: the reward you just got plus the discounted value of where you landed. The professor compares it to gradient descent (28:27): the bracket plays the role of a gradient and a step size. When the bracket is zero everywhere, nothing changes, and the Bellman equation holds. With and deterministic moves it becomes Mitchell's simpler rule .
The algorithm on slide 27:
- Initialize arbitrarily (zeros are common). Observe the initial state .
- Select and carry out an action (for example ε-greedy, Section 8).
- Observe the reward and the new state .
- Update the one cell you just used:To get the max, scan row of the table (31:28).
- Set and repeat until the episode terminates; then start another episode.
All Q-values start at 0. Every episode the agent starts in s4 and walks s4 → right → s5 → right → s6 → up → G. Since G is terminal, .
| Episode | Q(s4, right) | Q(s5, right) | Q(s6, up) |
|---|---|---|---|
| 1 | 0 + .5(0 + .9·0 − 0) = 0 | 0 + .5(0 + .9·0 − 0) = 0 | 0 + .5(100 + 0 − 0) = 50 |
| 2 | 0 + .5(0 + .9·0 − 0) = 0 | 0 + .5(0 + .9·50 − 0) = 22.5 | 50 + .5(100 − 50) = 75 |
| 3 | 0 + .5(0 + .9·22.5 − 0) = 10.125 | 22.5 + .5(.9·75 − 22.5) = 45 | 75 + .5(100 − 75) = 87.5 |
| 40 | 81.0 | 90.0 | 100.0 |
The reward is discovered only at the goal, and then it propagates backward one step per episode, exactly as Mitchell describes. After many episodes the values reach , the numbers from the value-iteration table, without the agent ever being told the rules of the grid. (In this example every step is the same, so only the max over the next state's row matters. In s5, for instance, is just because s6's other actions are still 0.)
Off-policy. The target uses , the action the optimal policy would take next, not the action the agent will actually take. So Q-learning learns no matter how the agent behaves while collecting data (slide 26: "use any policy", "independent of the policy being followed"). The only requirement is that every pair keeps getting updated. Géron: Q-learning can learn the optimal policy just by watching an agent act at random, "imagine learning to play golf when your teacher is a drunk monkey". For the guarantee to hold strictly, also has to shrink over time, as in SGD.
The callouts under the update rule say "New State" under and "Old State" under . Both are the same state–action pair . What's new and old is the Q-value estimate: is the updated value, the value before the update. The new state is , which only appears inside the max. Also, is the immediate one-step reward . The lecture calls it "the future reward" at 28:27, but the future part is .
They're different algorithms. Value iteration (Section 4) sweeps over all states using known and : it's planning with a model. Q-learning updates one visited pair at a time from observed transitions, with no model. Géron describes Q-learning as "an adaptation of the Q-Value Iteration algorithm to the situation where the transition probabilities and the rewards are initially unknown". Both share the same Bellman target, which is probably why the slide links them.
, the agent receives , and the best Q-value in is 6. With , , what is the new ?
Target . TD error . New value .
Exploration vs exploitation
Q-learning only learns about actions it actually tries. An agent that always takes the current best action (exploitation) can get stuck: if it once got a lucky reward from a mediocre action, it may never discover a better one. Trying other actions to gather information is exploration. Slide 23 calls exploration "a necessary add-on" for value-based methods, and the same trade-off reappears in AlphaGo's tree search (slide 44: "going deep on promising positions or exploring new underplayed positions").
The standard add-on is the ε-greedy policy: with probability take a uniformly random action, otherwise take .
A common schedule starts with (pure exploration, since the Q-table is meaningless at first) and decays it toward about 0.05 as the estimates improve. DeepMind's Atari DQN went from 1 to 0.1 over the first million steps. Géron also mentions a smarter alternative: add a curiosity bonus to rarely tried actions, e.g. where counts how often the action was tried.
Choosing a restaurant. Exploit: go to your favorite. Explore: try somewhere new, which might be worse tonight but could become your new favorite. Someone who never explores can't find out their favorite isn't the best, and someone who always explores never gets to enjoy what they've found.
With 5 actions and , what's the probability of the greedy action? Of one specific other action?
Greedy: . Each other action: . Check: .
Deep Q-networks (DQN)
A Q-table needs one row per state. That's fine for six grid cells and hopeless for Breakout, where a state is four frames (slide 28: about possible states). A table that size can't be stored, and it couldn't generalize anyway: every screen the agent hasn't seen exactly would have an untrained row.
The fix is the week 13–15 idea: use a neural network as a function approximator. A network with weights takes the state and outputs Q-values, so similar screens get similar values, and a few million weights stand in for an impossible table.
Slide 30 shows two designs. One feeds in and gets one Q-value out. The other, which DQN uses, feeds only in and gets one output per action. Then a single forward pass scores every action, which is exactly what the max in the target and the greedy choice need (Géron calls this "much more efficient"). At inference time (36:24), feed in the state and take the action with the largest output. For Atari (slide 31), the input is the stack of game frames, a CNN extracts features, and there's one output per joystick action.
Training. Turn the Q-learning target into a regression label and minimize the squared error by gradient descent (week 3), exactly like supervised learning (slide 32):
- weights of the online network, trained every step
- weights of the target network, a periodically refreshed copy of
- the target; treated as a fixed label (no gradient flows through it)
Naively training this is unstable (39:04). The network chases its own outputs: every update changes the targets too, "a dog chasing its own tail" in Géron's words. And consecutive frames are nearly identical, so a minibatch of them is highly correlated, unlike the i.i.d. samples SGD assumes. Slide 33's two tricks fix this:
- Experience replay. Store every transition in a large buffer (DeepMind used 1 million). Each training step samples a random minibatch from it. That breaks the correlations and reuses each experience many times.
- Fixed target network. Compute targets with a frozen copy and only copy every steps (slide 33: every 1,000 steps; DeepMind's Atari run: 10,000). The professor's description (40:02): train one branch many times, then sync the other branch to it, and repeat. The targets now hold still between syncs.
A sampled transition has , . For the next state and three actions, the target network outputs . The online network's prediction for the action taken is .
- DQN target: the max is 3.5, so .
- Loss for this sample: . Gradient descent raises toward 4.15.
- Double DQN: the online network picks the next action, the target network scores it. If the online net gives , it picks the third action, and the target net values that at 1.0: .
The two networks disagree about which action is best, so the Double DQN target is much lower. That's the point: taking the max of noisy estimates is biased upward (the max picks whichever estimate happens to be too high). Using two networks lowers that overestimation.
Slide 32 says "DQN: same network for both Q; Double DQN: separate network for each Q". That clashes with slide 33, whose fixed target network is a separate network, and it's part of DQN as DeepMind published it. Géron's account: DQN with fixed targets computes , so the target net both chooses and scores . Double DQN changes only who chooses:
The bias it reduces is the max's overestimation of Q-values, not just early-training inaccuracy.
Experience replay is described as "widely used in so-called active learning". It comes from reinforcement learning itself (Lin, 1992, then DeepMind's DQN). Its purpose is the one above: decorrelate training samples and reuse past experience.
Results (slides 34–35). Slide 34 shows stills of DQN playing Breakout after 10, 120 and 240 minutes of training. In DeepMind's video they come from, the agent barely returns the ball at first, plays well by 120 minutes, and by 240 minutes has found the trick of digging a tunnel through the side of the wall so the ball bounces along the top. Across the Atari suite it matched or beat human players on many games from raw pixels alone, with one network architecture and one set of hyperparameters.
What two problems does experience replay solve that plain online Q-learning with a network would have?
(1) Consecutive transitions are highly correlated, which breaks SGD's assumption of independent samples; random sampling from a big buffer decorrelates them. (2) Each experience would be used once and thrown away; replay reuses it many times, which improves sample efficiency.
Policy gradients and REINFORCE
DQN learns values and derives a policy from them. A policy gradient (PG) method skips the values: a policy network with weights takes the state and outputs action probabilities (slide 37: Pong pixels in, "probability of moving UP" out). Training does gradient ascent on the expected return. Slide 38 quotes Karpathy's summary: "Run a policy for a while. See what actions led to high rewards. Increase their probability."
| DQN | Policy gradient | |
|---|---|---|
| Learns | , then acts by | directly |
| Policy type | Off-policy: can learn from data any policy collected (e.g. old replay data) | On-policy: learns from episodes played by the current policy |
The REINFORCE gradient (slide 38, Williams 1992), written the way the professor rewrites it at 45:30:
- probability the policy gave to the action it actually took (slide 38 writes )
- the direction in weight space that makes that action more likely (the "score function")
- the discounted return that followed: a big positive pushes hard toward the action, a negative one pushes away
Why the log? The log-derivative trick, which the professor derives by hand on slide 38 (44:44–49:12). We want the gradient of an expectation, but the expectation's weights depend on , so we can't just sample. Since :
The right side is an expectation under the policy again, so you can estimate it by playing episodes and averaging . It also needs no derivative of the reward or the environment, which may not even be differentiable. The professor's side note: if then and the log removes the exponential, which is why the log form is easier for softmax policies.
A Pong policy has two actions with a softmax over two scores, both starting at 0: , so . For a softmax, .
- The agent pressed UP. is minus , which is .
- The episode was won, . With step size 0.1:
- New probability: . UP got a little more likely.
- Had the episode been lost (), the same step in reverse gives .
In practice (Géron's version) you play several episodes, compute each action's discounted return, normalize the returns across episodes (subtract the mean, divide by the standard deviation) to get each action's advantage, and weight each gradient by its advantage. Normalizing means "better than average" pushes up and "worse than average" pushes down, even if every raw reward is positive.
| Policy gradient vs DQN (slide 39) | |
|---|---|
| Pros | Works even when Q is too complex to learn ("messy world"); can learn stochastic policies (DQN can't); handles continuous actions easily (just output a distribution); slide claims faster convergence |
| Cons | Sample inefficient (needs more data); less stable in training; poor credit assignment for delayed rewards |
The professor reads slide 39 as "for the DQN, some positive and negative parts". The slide lists the pros and cons of policy gradients compared with DQN. "Stochastic policies: DQN can't" makes this clear. So: PG handles stochastic policies and continuous actions; DQN is the more sample-efficient one. Take "faster convergence" loosely. Géron calls simple PG "highly sample inefficient", and it's the reason more advanced methods (actor-critic, PPO) exist.
The problem with REINFORCE (slide 39, 52:10): since every action in an episode is scaled by the same total return, an episode with a few bad moves but a high total counts all of its moves as good. The professor's example: a sequence like "good, bad, good" can get the same average credit as "good, good, good". Only averaging over many episodes separates the good moves from the bad ones, which is why it needs so much data.
Why is REINFORCE on-policy while Q-learning is off-policy?
REINFORCE's gradient is an expectation over trajectories from the current ; episodes from an older policy have the wrong distribution, so it must keep generating fresh episodes with the policy being trained. Q-learning's target uses , the optimal next action, regardless of which policy collected the transition, so any data works.
AlphaGo Zero and the real world
Go (slides 41–43) has far too many positions for any table or brute-force search. AlphaGo (2016) beat the top human players; AlphaGo Zero (2017) beat AlphaGo, learning only from self-play with no human games. AlphaZero then did the same for chess and shogi (slides 46–48). Its approach (slides 44–45):
- Monte Carlo tree search (MCTS) from the current position, which balances exploitation (going deep on promising moves) against exploration (trying under-explored moves), the same trade-off as Section 8.
- A neural network as "intuition" for which positions to expand, so the search doesn't have to cover the huge tree (55:16).
- MCTS look-ahead, rather than human games, to improve the value estimates it trains on.
- A "two-headed" network with a shared body (multi-task learning): one head outputs move probabilities (a policy), the other the probability of winning (a value).
- A residual network (ResNet) architecture.
In slide 24's taxonomy AlphaZero is model-based, given the model: the rules of Go tell it exactly what each move does, so it can plan by search.
The real world. Slides 49–52: most successful real-world robots don't use deep RL yet, but that's slowly changing (learned control dynamics; Waymo's "learning to drive beyond pure imitation"). Slide 53 names the open challenge: real-world trial and error is slow, expensive and dangerous. There are two ways out, and the professor calls them "the two biggest problems" (56:42):
- Learn from real-world observation plus very few trials, which needs much more data-efficient algorithms.
- Train in realistic simulation, then transfer to the real world ("sim-to-real"), which needs better simulators and better transfer learning.
The professor closes the course with its map: supervised learning (classification and regression), unsupervised learning (clustering and dimensionality reduction), semi-supervised learning, deep learning (MLPs, CNNs, RNNs), and now reinforcement learning. The goal was a big picture of what machine learning can solve rather than depth on each algorithm. He invites students to message him later if they want suggestions on applying ML to their own problems.
What are AlphaGo Zero's network's two outputs, and which RL family does each echo?
Move probabilities, which is a policy (policy-based), and the probability of winning, which is a value estimate (value-based). MCTS adds planning with a known model (model-based), so it combines all three families.
Cheat sheet
| Loop | state → action → reward , next state |
| Agent learns | policy , value / , and/or model |
| Return | ; |
| γ | 0.9–0.99; reward steps ahead weighted ; small γ = short-sighted |
| Bellman (V) | |
| Bellman (Q) | ; |
| Value iteration | apply the Bellman update to all states until nothing changes; needs |
| Q-learning | ; model-free, off-policy |
| ε-greedy | random action w.p. ε, else argmax; greedy gets |
| DQN | network, one output per action; loss |
| DQN tricks | experience replay (decorrelate, reuse); target net copied every C steps (stable targets) |
| Double DQN | online net picks , target net scores it; reduces overestimation |
| REINFORCE | ; on-policy |
| Log trick | |
| PG vs DQN | PG: stochastic + continuous actions, less sample-efficient, less stable, weak credit assignment |
| Sample efficiency | model-based > value-based > policy-based |
Practice
Q1What most distinguishes reinforcement learning from supervised learning?
Q2An episode gives rewards and . What is the return from the first step?
Q3Why does a discount factor help the theory of RL?
Q4In slide 27's Q-table, row S3 is for A1–A4. Which action does the greedy policy take in S3?
Q5, reward , , , . New ?
Q6Why is Q-learning called off-policy?
Q7ε-greedy with and 4 actions. Probability of taking the greedy action?
Q8What problem does DQN's fixed target network solve?
Q9Which algorithm requires knowing the transition probabilities and rewards in advance?
Q10Which is an advantage of policy gradients over DQN (slide 39)?
Problem 1: For Géron's MDP (Section 4) with γ = 0.9, run two rounds of Q-value iteration starting from all zeros. Give Q₁ and Q₂ for every allowed (state, action), and the greedy policy after round 2.
Round 1 (, so only immediate expected rewards count):
; ; ; ; ; .
So , , .
Round 2:
Greedy policy: s0 → a0, s1 → a0 (stay), s2 → a1. It already matches the converged policy for γ = 0.9 (Q* = 18.92 / 17.03 / 13.62 in s0; 0 vs −4.88 in s1; 50.13 in s2).
Checked in Python against Géron's Q-value iteration code; round-2 values match exactly.
Problem 2: Using slide 27's Q-table, the agent is in S1 and acts ε-greedily. (a) With ε = 0.1, what's the probability it takes A3? (b) It takes A3, receives r = +1 and lands in S2. With α = 0.1, γ = 0.9, update Q(S1, A3). (c) Does S1's greedy action change? (d) If this were DQN with a target network that outputs (2, 0, 1, −2) for S2 and an online prediction of −1 for (S1, A3), what is the squared loss for this sample?
(a) A3 isn't greedy in S1 (A2 is, with +2), so it is only chosen by exploring: .
(b) . Target . TD error . New value .
(c) No. S1's row becomes , and A2 is still the max. One step with a small moves the estimate only 10% of the way toward the target. A3 would need several more good outcomes to overtake A2.
(d) The target is the same . Loss . Its gradient pushes the online network's output for (S1, A3) up toward 2.8, which is the DQN version of step (b).
Note the max in the target is over the next state's row (S2), not the current one, and the reward is the immediate one-step reward.