Reinforcement learning
Comparison of tabular methods
Q-learning, SARSA, Monte Carlo and Dyna-Q: study the learning of a strategy. Compare exploration and planning across nine game environments.
For each route, a new difficulty
- IThe environments
LineWorld, GridWorld, Monty Hall with 3 then 5 doors, rock-paper-scissors in 2 rounds, SecretEnv0 to SecretEnv3. - IIThe ten models
Monte Carlo and its variants, SARSA, Q-learning, Expected SARSA, Value Iteration, Policy Iteration, Dyna-Q and Dyna-Q+. - IIIAll models, game by game
Go back to each environment, compare the decisions and results, then explain the behaviours.
The reading plan
From rules to models, then to behaviours
How does an agent learn to play from the rewards of its actions? This project implements ten tabular methods and puts them to the test in LineWorld, GridWorld, Monty Hall with three then five doors, rock-paper-scissors in two towers and four secret environments.
Why separate the three stages?
We first discover the rules and objective of each game. We then explain the ten methods, from returning an episode to planning Dyna-Q+. Finally, we return to each environment to compare all the methods: their decisions, their performances and the reasons for their behaviour. The same diagrams then link the observations to the mechanisms already presented.
A gain at the end of the road
0 and 7 end the game. The numbers are the states; left and right are the actions. Workshop scale.
1 / 3 · Understanding environments
LineWorld: take the right exit
The agent starts from box 4 on a line numbered 0 to 7. He can go left or right. In the workshop, the right output yields +1, the left output −1; intermediate steps earn 0. Reaching an endpoint ends the game.
Why start with this game?
There are no obstacles or hazards in traveling. We can read a strategy directly from the route arrows. The reference is simple: 4 → 5 → 6 → 7, or +1 in three steps. After studying the models, we will compare the ten methods on this same line, not just Monte Carlo.
Four trips to the exit
−0,1 − 0,1 − 0,1 + 10 = 9,7
The start in the center is surrounded. The path squares are connected by the decisions above. Any action against an edge or any detour can change the score.
1 / 3 · Understanding environments
GridWorld: reaching an exit with few detours
The grid contains 25 squares and four possible directions. The agent starts from the center; top left and bottom right exits earn +10. An ordinary move costs −0.1, hitting the edge −0.5, and returning to the center −1.
Why add the number of steps to the score?
Several paths reach an exit. A direct journey of four actions yields 9.7: three small costs, then +10 upon arrival. An agent who succeeds in six steps has found an exit, but keeps a detour. We will therefore seek to distinguish success, efficiency of the journey and behaviour during learning.
Three gain positions, two reasons to change
| Hidden gain | Keep A | Change |
|---|---|---|
| Door A | Win | Lose |
| Door B | Lose | Win |
| Door C | Lose | Win |
The initial choice is A in all three cases. The presenter always opens a losing door different from the agent's choice.
1 / 3 · Understanding environments
Monty Hall: keep a door or change?
One of the three doors hides a gain. The agent chooses a door; the presenter, who knows the answer, opens another losing door. The agent can keep his choice or take the last closed door. The game pays 1 if it reveals the gain, 0 otherwise.
Why can a good decision lose?
Change wins two times out of three in the long run; keep wins one time out of three. But no decision guarantees the outcome of a game. The table shows the three possible positions of the gain for an initial choice A. The comparison of the models must therefore focus on several parts and on their tendency to keep or change.
Keep A, then change to the last choice
Example where the gain is in B. The winning door remains hidden from the agent. Keeping A during the three openings maintains its initial probability of 1/5; the other remaining door is 4/5.
1 / 3 · Understanding environments
Five doors: follow several successive choices
This variant starts with five doors. Three choices and three losing door openings precede the final decision between keeping and switching. At each step, the agent observes its current door and the doors already open; the position of the gain remains hidden.
Why does the sequence of choices matter?
Keeping your first door during all openings, then changing at the end, gives a theoretical reference of 80%. This probability does not automatically describe a strategy that changes in the meantime. To understand a model, you will have to look at its entire sequence of decisions, and not just its last choice.
The state must retain first choice
- 1You play rock. The opponent plays at random.
- 2It copies your first choice: rock.
- →The answer is paper.
Remembering does not predict a random draw. Here, memory is useful because the second round rule depends on the first.
1 / 3 · Understanding environments
Two turns: anticipate the copy of the first choice
In the first round of rock, paper, scissors, the opponent plays at random. In the second, he replays the agent's first choice. If the agent started with stone, the opponent will therefore play stone: leaf becomes the correct answer. Each round earns +1, 0 or −1 depending on its outcome.
Why keep the first choice in observation?
The “second round” information is not enough to decide: you also need to know what the agent had played. The workshop keeps these two pieces of information. We will measure the victories in the second round and the score of the two rounds separately: even with a perfectly played second round, the first remains random.
How many situations should we explore?
Length of bars in logarithmic scale (base 2). Three actions per state are declared by the engines; not all situations are necessarily encountered in a session.
1 / 3 · Understanding environments
Four environments with hidden rules
SecretEnv0 through SecretEnv3 are provided as compiled engines. The agent reads a state identifier and authorized actions, takes action, and then observes the score variation. The declared spaces range from 8,192 to 2,097,152 states, with three possible actions in total.
Why treat them separately from the five known games?
Their states and scores are observable, but we cannot explain their rules like those of a grid or Monty Hall. It is also necessary to distinguish measured behaviours from interface errors. The comparative part will specify, for each method, what the archives really allow us to conclude. The workshop allows you to try Q-learning on the original engines.
Same situation, two choices to evaluate
| State | Left | Right |
|---|---|---|
| Box 4 | Q(4, ←) | Q(4, →) |
Q estimates a return for each action. V estimates the return of a state. Policy turns these estimates into choices. The update mechanism changes from one model to another.
2 / 3 · Understanding models
What all models try to estimate
The games are now defined. A policy associates an action with each situation. A Q table estimates the expected return of an action in this situation; a V table estimates the value of a state. The return adds up future rewards, with a factor γ which gradually reduces their weight.
Why might methods produce different choices?
They do not use the same target to correct their estimates. Monte Carlo awaits a full return; TD methods use an estimate of the next step; dynamic programming exploits rules; Dyna builds a model from the experiments. The following diagrams explain these calculations. We reserve their performances for the third part.
Return to a completed episode
The numbers shown at the end are the returns for that episode. Q approaches these returns; it does not instantly become accurate.
2 / 3 · Understanding models
Monte Carlo on-policy: learn after the game
The agent follows a policy that sometimes explores, then waits until the end of the game. It goes back along the path to calculate the return of each choice and bring Q closer to this return. In the workshop, only the first visit of a state–action pair in the episode is retained; the update step is α = 0.15.
Why do we have to repeat the parts?
This variant learns the consequences of the policy that produced the episodes, including exploration. Repeating games stabilizes the estimates, but returns can vary and come late in a long game. The diagram uses a LineWorld path to read the calculation; it illustrates the mechanism, before any performance comparison.
Explore from the starting point
The ES variant can start in another non-terminal square of the grid and try another first action. The other choices follow the policy; updates wait until the episode ends.
In the door games and the two towers, only the first choice is randomized by the workshop.
2 / 3 · Understanding models
Monte Carlo ES: vary the first tests
Monte Carlo can miss actions if policy never tries them. Exploring Starts changes the start: on the workshop grids, the agent starts in a non-terminal box drawn at random and chooses its first action at random. It then tracks the best-evaluated actions and waits until the end to update Q.
Why might starting somewhere else help?
This gives access to state–action pairs rarely visited since the usual start. The exploration is concentrated at the beginning of the episode. This mechanism assumes being able to choose the starting point. In Monty Hall and Rock-Paper-Scissors, the workshop only randomizes the first choice: this version therefore does not cover all states through exploratory departures.
Correct the weight of a trajectory
- bThe collection policy chooses an action with probability 0.2.
- πThe target policy chooses this action with probability 1.
- ×5The ratio for this choice is 1 / 0.2 = 5.
Example of weighting, not measured performance. High weights can amplify variability. In the workshop, if an action no longer corresponds to the deterministic target policy, the previous steps stop receiving the contribution of this trajectory.
2 / 3 · Understanding models
Monte Carlo off-policy: learning another policy
The collection policy b explores, while the target policy π chooses the best estimated actions. Off-policy Monte Carlo uses the collected feedback to learn this target policy. To correct the difference between the two, it weights the episodes with the probability ratios π(a|s) / b(a|s).
Why can these weights make learning irregular?
A rare action in the data may be given a high weight. Conversely, a trajectory that deviates from a deterministic target policy ceases to contribute to earlier stages in implementation. The workshop uses a persistent weighted average. This separation between followed policy and learned policy will reappear in Q-learning, with another form of update.
One step on the grid, one value to correct
Illustrative values of the four actions in the next box. The action actually taken is ↓.
= 1.88
Q before: 3. Q after: 3 + 0.15 × (1.88 − 3) = 2.83.
SARSA retains 2: the value of the next real choice.
2 / 3 · Understanding models
SARSA: learning with the next real choice
On the grid, the agent moves from a box s to a box s′, then chooses its next action a′. SARSA adjusts Q(s,a) towards r + γ Q(s′,a′). It does not wait for the output: the value already associated with the next action serves as a relay. At the end, the future is worth zero since the game is over.
Why does exploration influence what SARSA learns?
If the next choice is an exploratory detour, SARSA uses the value of this detour. He therefore learns of the return of the policy actually followed, exploration included. The slider opposite shows how a single transition modifies Q. Q-learning will keep this immediate update, but replace the next actual choice with the best estimated choice.
One step on the grid, one value to correct
Illustrative values of the four actions in the next box. The action actually taken is ↓.
= 7.82
Q before: 3. Q after: 3 + 0.15 × (7.82 − 3) = 3.72.
Q-learning retains 8: the best value, even if the next choice is ↓.
2 / 3 · Understanding models
Q-learning: learn the best estimated sequence
Same square, same movement, same reward. What changes is the target: r + γ max Q(s′,a). Even if the agent then explores a detour, Q-learning uses the best action estimated in the next box. The collection policy can explore; the target assumes a greedy continuation.
Why doesn't this guarantee better performance?
The maximum concerns estimates, which can still be bad. You have to visit the actions to correct them. With little experience, an overly optimistic value may attract the agent. On this small grid, several methods end up finding the same path: the interest of the comparison also lies in their learning speed and their variability.
One step on the grid, one value to correct
Illustrative values of the four actions in the next box. The action actually taken is ↓.
= 7.23
Q before: 3. Q after: 3 + 0.15 × (7.23 − 3) = 3.63.
Expected SARSA weights the four values. With ε = 0, its target matches that of Q-learning.
2 / 3 · Understanding models
Expected SARSA: weighting all possible outcomes
SARSA uses a randomly drawn next choice; Q-learning uses the best. Expected SARSA calculates the average of the values of the next actions, weighted by the policy. With four actions and ε = 20%, a single leading action receives 85% probability; each of the other three, 5%.
Why take a weighted average?
This removes the randomness associated with drawing a single next action from the target. The chance of the game and that of the experiments remain present. When ε is zero, this expectation reaches the maximum. Vary ε: you will see exactly what changes in the target, then compare this calculation to those of SARSA and Q-learning.
The value of the outputs propagates
Synchronous sweeps: Each box uses the values from the previous sweep. Terminals display their entry reward, +10; their future value is zero.
2 / 3 · Understanding models
Value Iteration: calculate paths without traversing them
Until now, the agent had to play to learn. On a grid where all the rules are known, we can calculate the consequences of each action. Value Iteration replaces the value of one box with the best immediate reward plus the discounted value of the next one. A succession of sweeps spreads interest from the exits towards the center.
Why does this require more information?
The calculation also examines transitions that the agent has never experienced. It needs a reliable model of rewards and movements. The cursor shows this propagation on the workshop grid, starting from zero values. Incorrect rules produce a policy optimized for the wrong game; more calculation does not repair this discrepancy.
Correct the arrows of policy
An initial policy that always chooses the right ends up stuck against the edge. His assessment reveals the cost of this repetition.
Evaluate choices → improve arrows → start again.
2 / 3 · Understanding models
Policy Iteration: Evaluate a plan, then correct it
Value Iteration improves values directly. Policy Iteration starts with a policy, for example the arrows drawn on the grid. It calculates the return of that policy, then replaces each arrow with a better action. She starts again until the choices stabilize.
Why don't fewer iterations mean less computation?
A Policy Iteration contains a policy evaluation, which may require multiple scans. Value Iteration directly improves values with each scan. Comparing only their numbers of iterations would be misleading: it is necessary to take into account the work carried out and verify that both calculate from the same transitions and rewards.
A real experience, five replayed memories
After the actual arrival, Q(19, ↓) goes from 0 to 1.5. Move the cursor forward: the memories of the path transmit this information to the other squares, without further movement.
Illustrative repeat order: 14, 13, 12, 19, 14. In the workshop, memories are drawn at random. The values start from zero, except that of the actual arrival.
2 / 3 · Understanding models
Dyna-Q: a real movement, several mental repetitions
Dyna-Q starts with a Q-learning update after a real step. He then memorizes: “from this box, this action gave this reward and this next box”. Then it pulls memories and redoes updates without replaying in the engine. In the workshop, five repetitions accompany each real interaction.
Why can this mixture help and then become misleading?
On a deterministic grid, the memory describes a reliable transition: the gain can propagate without new paths. In Monty Hall, the workshop only memorizes the last observed outcome. Replaying it can amplify a lucky or unlucky sample. Replaying an outcome does not create a new independent observation. We will check the consequences of this approximation in the comparisons by game.
Seniority becomes a planning bonus
= 0
During a new real test, the age of this action starts again from zero. The bonus remains internal to simulated updates.
2 / 3 · Understanding models
Dyna-Q+: give a reason to revisit forgotten actions
Dyna-Q reuses what it knows. Dyna-Q+ adds, during planning, a bonus κ√τ: τ counts the time since the last real attempt of an action. An action ignored for a long time becomes more attractive, which encourages you to return to check what it allows. Untried actions from visited states can also enter the model.
Why doesn't this bonus replace an actual reward?
It serves to guide exploration; it is not added to the displayed game score. The cursor shows its growth. This idea is particularly useful when the rules change, but the games known to the workshop remain fixed: our measurements therefore do not demonstrate an adaptation to a change of rules. This is the most composite method of the course: Q-learning, model, planning and seniority.
Read each comparison in the same order
- 1The table: the ten methods on the same game.
- 2The chosen model: its mechanism and the reasons for the observed behaviour.
- 3The diagram: its policy and a recorded part, action by action.
Budgets 0, 50, 100 and 300 also allow you to see the start of learning. α = 0.15; γ = 0.99; ε = 0.15 during learning, cut during evaluation. DP calculates from the rules; the calculation times and the number of updates are not equalized.
Download CSV measurements3 / 3 · Compare models in each environment
The same game, all the methods, the same measures
The mechanisms are in place. We now return to each environment, in the same order. Each comparison presents the ten methods, then allows you to inspect the decisions of a method and relate its behaviour to its operation. An unevaluated method is flagged explicitly, without assigning it a zero score.
Why separate a trajectory from an average result?
A trajectory helps to understand a choice; it does not summarize a performance. The scores come from eight independent training sessions, each evaluated over 300 games without exploration. Policy patterns and registered parties come from a single seed fixed in advance. Historical Python results remain accessible in the respective game comparison.
All models on LineWorld
Choose a method from the table to examine its behaviour in the diagram below.
| Method | Success | Score | Not |
|---|---|---|---|
| Chance | 57.7 % | 0.15 | 11.9 |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 | |
| 100 % | 1 | 3 |
Averages of 8 seeds × 300 games without exploration. * Policy calculated from rules, independent of budget. — Not evaluated in this protocol.
Monte Carlo on-policy : link the mechanism to the behaviour
An exit to the right gives positive feedback to the choices of the entire journey. On this short line, a few episodes can already inform all the useful choices from the start. The final policy of this essay joins the exit in three steps.
Review the operation of Monte Carlo on-policy
One policy and part registered
Next action: →. Reward observed after this action: 0.
The arrows show the maximum value actions; several arrows indicate a tie. The point locates the agent, the marked boxes show his passage.
See the values that guide this choice
Observed state: 4. An action of maximum value is chosen; ties are broken at random.
| Action | Estimated value |
|---|---|
| ← | 0.9596 |
| → | 0.9743 |
Illustration: training seed 1101, evaluation seed 51101. Policy after 1000 episodes. This single part does not summarize the eight workouts.
Dispersion between workouts
Average success: 100 %; standard deviation between the eight seeds: 0 points. Minimum 100 %, maximum 100 %.
The averages describe the eight workouts; the illustrated policy only comes from seed 1101. The explanations link the mechanism to what is observed, without experimentally isolating all the causes of the deviations.
Complete comparison with Python archives
Two behaviours in Python archives
+3 in 3 steps
+500 in 1000 steps
The step limit ends the loop evaluation. The cumulative gain is high, but the terminal is not reached. Historical Python scale, different from the workshop.
3 / 3 · Compare models in each environment
LineWorld: ten methods, one output
After 1,000 episodes, all eight methods that learn by interaction reach the right output in three steps in this protocol. Value Iteration and Policy Iteration also calculate this path from the rules. The ten methods are presented together; select one to see its policy arrows and saved trip.
Why do different mechanisms achieve the same result?
The line is short, the movements are deterministic and only one exit is favorable. Monte Carlo can pass the gain all the way after the episode; SARSA, Q-learning and Expected SARSA propagate it step by step; dynamic programming calculates the consequences; Dyna reuses transitions. The final result is therefore not enough to decide between them: also observe the beginning of the learning.
All models on GridWorld
Choose a method from the table to examine its behaviour in the diagram below.
| Method | Success | Score | Not |
|---|---|---|---|
| Chance | 93.9 % | 2.06 | 35.7 |
| 100 % | 9.7 | 4 | |
| 100 % | 9.68 | 4.3 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 | |
| 100 % | 9.7 | 4 |
Averages of 8 seeds × 300 games without exploration. * Policy calculated from rules, independent of budget. — Not evaluated in this protocol.
Monte Carlo on-policy : link the mechanism to the behaviour
The return of an episode adds up the costs of the detours before the final gain. Shorter journeys thus receive better returns. The map allows you to check how this information was transformed into local choices, once the episodes were over.
Review the operation of Monte Carlo on-policy
One policy and part registered
Next action: ↑. Reward observed after this action: -0.1.
The arrows show the maximum value actions; several arrows indicate a tie. The point locates the agent, the marked boxes show his passage.
See the values that guide this choice
Observed state: 12. An action of maximum value is chosen; ties are broken at random.
| Action | Estimated value |
|---|---|
| ← | 9.0458 |
| → | 8.1804 |
| ↑ | 9.2106 |
| ↓ | 7.9 |
Illustration: training seed 1101, evaluation seed 51101. Policy after 1000 episodes. This single part does not summarize the eight workouts.
Dispersion between workouts
Average success: 100 %; standard deviation between the eight seeds: 0 points. Minimum 100 %, maximum 100 %.
The averages describe the eight workouts; the illustrated policy only comes from seed 1101. The explanations link the mechanism to what is observed, without experimentally isolating all the causes of the deviations.
Complete comparison with Python archives
Q-learning · Python test, 500 episodes
Training reward, average in blocks of 10 episodes.
Read the curve values
| End of block | Average reward |
|---|---|
| 10 | 7.58 |
| 20 | 9.64 |
| 30 | 9.66 |
| 40 | 9.7 |
| 50 | 9.59 |
| 60 | 9.65 |
| 70 | 9.68 |
| 80 | 9.48 |
| 90 | 9.7 |
| 100 | 9.68 |
| 110 | 9.59 |
| 120 | 9.64 |
| 130 | 9.63 |
| 140 | 9.61 |
| 150 | 9.64 |
| 160 | 9.52 |
| 170 | 9.52 |
| 180 | 9.7 |
| 190 | 9.68 |
| 200 | 9.66 |
| 210 | 9.61 |
| 220 | 9.63 |
| 230 | 9.61 |
| 240 | 9.66 |
| 250 | 9.64 |
| 260 | 9.68 |
| 270 | 9.7 |
| 280 | 9.68 |
| 290 | 9.7 |
| 300 | 9.59 |
| 310 | 9.66 |
| 320 | 9.7 |
| 330 | 9.7 |
| 340 | 9.66 |
| 350 | 9.68 |
| 360 | 9.48 |
| 370 | 9.65 |
| 380 | 9.66 |
| 390 | 9.65 |
| 400 | 9.59 |
| 410 | 9.65 |
| 420 | 9.7 |
| 430 | 9.65 |
| 440 | 9.7 |
| 450 | 9.7 |
| 460 | 9.7 |
| 470 | 9.68 |
| 480 | 9.65 |
| 490 | 9.7 |
| 500 | 9.7 |
3 / 3 · Compare models in each environment
GridWorld: success is not enough to avoid detours
On this grid, all tested methods reach an output after the final budget. Most get 9.7 in four steps; Monte Carlo ES gives 4.25 steps on average across the eight seeds. The map shows a policy's choices, and the recorded path indicates the actions actually taken in a game.
Why can a method be successful with a longer route?
Exploring Starts visits various departures; a finite budget does not guarantee that each policy obtained is optimal from the center. TD methods correct values locally, while Dyna's memories are reliable on this deterministic grid. Two different paths can also be equally short: compare the steps and the score, rather than just judging the direction of the arrows.
All models on Monty Hall · 3 doors
Choose a method from the table to examine its behaviour in the diagram below.
| Method | Success | Score | Not |
|---|---|---|---|
| Chance | 49.7 % | 0.5 | 2 |
| 68 % | 0.68 | 2 | |
| 58.5 % | 0.58 | 2 | |
| 67.7 % | 0.68 | 2 | |
| 67.7 % | 0.68 | 2 | |
| 65.3 % | 0.65 | 2 | |
| 68 % | 0.68 | 2 | |
| — | — | — | |
| — | — | — | |
| 58.5 % | 0.59 | 2 | |
| 62.2 % | 0.62 | 2 |
Averages of 8 seeds × 300 games without exploration. * Policy calculated from rules, independent of budget. — Not evaluated in this protocol.
Monte Carlo on-policy : link the mechanism to the behaviour
The final return is worth 0 or 1. Repeating games brings Q closer to the observed gains to keep or change. The counter indicates the preference of this policy; an isolated defeat remains compatible with the right decision to change.
Review the operation of Monte Carlo on-policy
One policy and part registered
Next action: Door C. Reward observed after this action: 0.
Of the 300 parts of this seed: 0 final “keep” decisions and 300 “change”. The winning door never enters the pattern observation.
See the values that guide this choice
Observed state: 0:-1:. An action of maximum value is chosen; ties are broken at random.
| Action | Estimated value |
|---|---|
| Door A | 0.4518 |
| Door B | 0.5556 |
| Door C | 0.7347 |
Illustration: training seed 1101, evaluation seed 51101. Policy after 1000 episodes. This single part does not summarize the eight workouts.
Dispersion between workouts
Average success: 68 %; standard deviation between the eight seeds: 2.6 points. Minimum 63 %, maximum 72.3 %.
The averages describe the eight workouts; the illustrated policy only comes from seed 1101. The explanations link the mechanism to what is observed, without experimentally isolating all the causes of the deviations.
Complete comparison with Python archives
Tests, with their fluctuations
100 training episodes, 100 evaluation games per trial. Theoretical reference for change: 66.7%.
Test settings
Test 1 : α 0.1, γ 0.99, initial ε 0.1.
Test 2 : α 0.1, γ 0.99, initial ε 0.1.
Test 3 : α 0.1, γ 0.99, initial ε 0.1.
Test 4 : α 0.1, γ 0.9, initial ε 0.1.
Test 5 : α 0.1, γ 0.9, initial ε 0.1.
Test 6 : α 0.1, γ 0.98, initial ε 0.1.
Test 7 : α 0.1, γ 0.99, initial ε 0.1.
Test 8 : α 0.11, γ 0.98, initial ε 0.1.
3 / 3 · Compare models in each environment
Three doors: what methods teach to change?
The eight methods evaluated win approximately 58-68% of games after 1,000 episodes. The table compares them all and reports the two dynamic programming methods not evaluated here. The diagram shows a recorded game; The counter indicates how many final decisions keep or change the gate in the 300 parts of the seed shown.
Why isn't replaying a memory always worth playing again?
Monte Carlo aggregates returns, TD methods gradually correct their estimates. Here Dyna replays the last memorized outcome: in a random game, this can amplify a particular observation. Expected SARSA reduces the chance of the next choice in its target, but does not eliminate the chance of winning. Explanations by method make it possible to find these distinctions in the observations.
All models on Monty Hall · 5 doors
Choose a method from the table to examine its behaviour in the diagram below.
| Method | Success | Score | Not |
|---|---|---|---|
| Chance | 49.6 % | 0.5 | 4 |
| 64.2 % | 0.64 | 4 | |
| 55.5 % | 0.56 | 4 | |
| 64.3 % | 0.64 | 4 | |
| 67.3 % | 0.67 | 4 | |
| 66.6 % | 0.67 | 4 | |
| 66.6 % | 0.67 | 4 | |
| — | — | — | |
| — | — | — | |
| 62 % | 0.62 | 4 | |
| 64.8 % | 0.65 | 4 |
Averages of 8 seeds × 300 games without exploration. * Policy calculated from rules, independent of budget. — Not evaluated in this protocol.
Monte Carlo on-policy : link the mechanism to the behaviour
The final return corrects the entire sequence of choices. It therefore also depends on intermediate changes, which makes the attribution of the gain to each decision less direct. The diagram allows you to follow a complete sequence, while the average score describes the many other parts.
Review the operation of Monte Carlo on-policy
One policy and part registered
Next action: Door C. Reward observed after this action: 0.
Of the 300 parts of this seed: 105 final “keep” decisions and 195 “change”. The winning door never enters the pattern observation.
See the values that guide this choice
Observed state: 0:-1:. An action of maximum value is chosen; ties are broken at random.
| Action | Estimated value |
|---|---|
| Door A | 0.4439 |
| Door B | 0.5618 |
| Door C | 0.9358 |
| Door D | 0.4505 |
| Door E | 0.3117 |
Illustration: training seed 1101, evaluation seed 51101. Policy after 1000 episodes. This single part does not summarize the eight workouts.
Dispersion between workouts
Average success: 64.2 %; standard deviation between the eight seeds: 5.6 points. Minimum 54.3 %, maximum 72 %.
The averages describe the eight workouts; the illustrated policy only comes from seed 1101. The explanations link the mechanism to what is observed, without experimentally isolating all the causes of the deviations.
3 / 3 · Compare models in each environment
Five doors: comparing the sequences of decisions
With the same budget, the eight methods evaluated achieve around 55 to 67% savings. Their final decision is not enough to explain this score: the intermediate changes modify the situations visited. Advance through the recorded game to see the open doors, the current choice, and the values that guide each decision.
Why do the same algorithms require more experience?
Successive choices multiply the possible observations: each line of Q is visited less often. Partial exploratory departures cover this space imperfectly; Monte Carlo returns depend on the entire sequence; TD uses interim estimates; Dyna only memorizes one outcome per observed couple. A comparison of a few points alone does not prove general superiority.
All models on Rock, paper, scissors · 2 rounds
Choose a method from the table to examine its behaviour in the diagram below.
| Method | 2nd round won | Score | Not |
|---|---|---|---|
| Chance | 33.5 % | 0 | 2 |
| 100 % | 1 | 2 | |
| 100 % | 0.98 | 2 | |
| 100 % | 1.02 | 2 | |
| 100 % | 1 | 2 | |
| 100 % | 1 | 2 | |
| 100 % | 1 | 2 | |
| — | — | — | |
| — | — | — | |
| 100 % | 1.01 | 2 | |
| 100 % | 0.99 | 2 |
Averages of 8 seeds × 300 games without exploration. * Policy calculated from rules, independent of budget. — Not evaluated in this protocol.
Monte Carlo on-policy : link the mechanism to the behaviour
The full return contains the result of the second round. The state memorizes the first choice: episodes can thus associate each copy of the opponent with the response that beats it. The first round remains random even if the second is always won.
Review the operation of Monte Carlo on-policy
One policy and part registered
Next action: Paper. Reward observed after this action: -1.
For this seed: 300 second round wins over 300. The total score also includes the first random round.
See the values that guide this choice
Observed state: 0:-1. An action of maximum value is chosen; ties are broken at random.
| Action | Estimated value |
|---|---|
| Rock | 0.2649 |
| Paper | 0.7714 |
| Scissors | 0.2929 |
Illustration: training seed 1101, evaluation seed 51101. Policy after 1000 episodes. This single part does not summarize the eight workouts.
Dispersion between workouts
Average success: 100 %; standard deviation between the eight seeds: 0 points. Minimum 100 %, maximum 100 %.
The averages describe the eight workouts; the illustrated policy only comes from seed 1101. The explanations link the mechanism to what is observed, without experimentally isolating all the causes of the deviations.
3 / 3 · Compare models in each environment
Two rounds: eight methods use the same memory
After 1,000 episodes, all evaluated methods win the second round in our protocol. The diagram shows the agent's first choice, its copy by the adversary and the model's response. The scores for both rounds remain close to +1, with variations due to the random first round.
Why does changing model do little for this game?
The state preserves exactly the information that makes the runoff predictable. The complete Monte Carlo return, the TD targets and the transitions memorized by Dyna then all allow the first choice to be associated with the correct answer. This convergence illustrates the role of state representation: useful information can count more than a more complex learning mechanism.
Each method, on each of the four engines
| Method | State of the evidence |
|---|---|
| Unvalidated measurements | |
| Unvalidated measurements | |
| Unvalidated measurements | |
| Unvalidated measurements | |
| Unvalidated measurements | |
| Unvalidated measurements | |
| Interface error | |
| Interface error | |
| Unvalidated measurements | |
| Unvalidated measurements |
Q-Learning on SecretEnv0
The archive shows an average score of 0 and 100 steps, in a campaign whose interface has documented issues. This does not explain behaviour specific to Q-Learning, nor to classify this method.
↓ real action
New state + score variation
Q-learning can be tested on the native engine in the final workshop. The measurements of this new session are distinct from those of the archive.
Review the operation of Q-Learning3 / 3 · Compare models in each environment
SecretEnv0 to SecretEnv3: what we can really compare
All ten methods now have a known mechanism. On secret environments, however, old results contain interface errors and fallback measures. The table therefore distinguishes, for each engine and each method, an exploitable measurement of a result which does not allow a conclusion.
Why not attribute these failures to the algorithms?
An error in the adapter can prevent Monte Carlo from receiving an episode or distort the transitions used by TD, DP and Dyna. A zero recorded under these conditions is not proof of a bad strategy. The current workshop offers Q-learning on native engines; the other methods require a validated protocol before being able to compare their behaviour and performance.
An experience to explore in this chapter.
Put into practice · Reproduce the comparisons
Find the mechanisms by making the agents play
Choose a game and a method, train the agent, then observe its decisions. The journey gave you hypotheses: a reward that spreads, an exploratory detour, an uncertain door choice or a useful memory. The workshop now allows them to confront a game.
What you can do
Changing the game or method resets the table. Training again adds 1,000 episodes; Replaying retains what has been learned. Measurements for this session may vary with samples.
From the line to the grid
- Start with Monte Carlo, then SARSA and Q-learning. Increase exploration: the average during training can drop while the strategy evaluated remains good.
- On GridWorld, count the four steps of a direct path. Then compare with a policy calculated by Value Iteration or Policy Iteration.
Doors, memory and planning
- In Monty Hall, observe several games: an isolated defeat does not allow you to judge the strategy. With five doors, also follow the intermediate choices.
- In two turns of rock, paper, scissors, check that the agent responds to the first choice memorized. Compare Dyna-Q on the grid then on the doors: does replaying a memory have the same value in both games?
Measure without confusion
- The Evaluate button plays 300 games without exploration and displays score, success and length. Compare these measurements to the training average.
- In secret environments, train the Q table on the original engine and observe the score variations; the number displayed describes your local test.