Q-learning: one update rule, repeated
On this page
The previous post ended with a promise: if the learner had the action valuesThe expected return from taking a given action in a state and following a given policy after that.Reinforcement Learning · §3.5, p. 58, the values of doing each actionOne of the set of things the agent can do; at each step it senses the state, chooses an action and performs it.Machine Learning · §13.2, p. 370 in each stateA signal telling the agent how the environment is at a given moment; the input its policy and value estimates use.Reinforcement Learning · §1.4, p. 7, acting would be one line long, take the largest. It also ended with the hard part, filling those values in from experience, when the environmentEverything outside the agent that it interacts with.Reinforcement Learning · §3.1, p. 47 hands over one rewardThe single number the environment sends the agent at each step; the agent aims to maximise the total over the long run.Reinforcement Learning · §1.3, p. 6 at a time and never says what the value was. Q-learningA method that learns each action's value in each state, aiming straight at the best values whatever policy the agent is following.Reinforcement Learning · §6.5, p. 131 is the standard answer. It is a table and one update rule, and this post goes through both on the same ten days of SPY from January 2023, working one update by hand and then repeating it to see what the learning rateThe number that sets how big each update step is.Deep Learning · §7.2.2, p. 214 does.
The table
The Q-tableA table with one entry for each state-action pair, holding the learner's current estimate of that pair's Q value.Machine Learning · §13.3.2, p. 375 has one row per state and one column per action. Each cell holds the learner’s current estimate of the action value from the previous post: the return it expects if it takes that action in that state and acts well afterwards. Mitchell writes the estimate with a hat, Q̂, to stress that the table is the learner’s hypothesis about the real values, not the values themselves (section 13.3.2). Sutton and Barto initialise it arbitrarily, except that any terminal state’s row is zero (section 6.5); Ritter’s trading version starts it at zero or at prior information if there is any (section 3.4).
Table 1 is a tiny one, two states and two actions, with starting guesses I made up, in percent of the position:
| State | go long | go cash |
|---|---|---|
| cash | 0.50 | 0.00 |
| long | 0.80 | 0.10 |
Read it by row. In state cash the table currently prefers “go long” (0.50 beats 0.00); in state long it prefers “go long” too, which here means stay long (0.80 beats 0.10). A cell is an estimate of a return, so it is in the units of the reward, not a probabilityHow often an event happens if you could repeat a trial without end: the share of trials where it happens.Deep Learning · Ch. 2 introduction, p. 24 and not a next state. The greedyAn action whose estimated value is currently the highest.Reinforcement Learning · §2.1, p. 26 choice compares cells within one row; the number 0.50 is not good or bad on its own, it is only better than 0.00.
The update rule
After one step the learner knows four things: the state it was in, the action it took, the reward it got, and the state it landed in. Q-learning uses them to change exactly one cell, the one for the state and action it just experienced (Sutton and Barto, equation 6.8):
Q, the cell being updated; α, the learning rate; γ, the discount factorR, the reward just received; S′, the state landed in
The square bracket is the whole idea. The first two terms inside it are a target: the reward you actually got, plus the discounted best value the table currently claims for where you landed. That is the recursion from the previous post, value now equals reward now plus discounted value next, with the actual reward standing in for the expected one and the table’s own entry standing in for the true value next. Subtracting the old estimate gives the error, how far the old guess was from the target; Sutton and Barto call it the temporal difference error (section 6.1). Multiplying by the learning rate and adding it back moves the old guess that fraction of the way towards the target. Nothing else in the table moves.
Worked on the morning of 2023-01-03. The learner is in state cash, takes “go long”, receives day 1’s return as its reward, , and lands in state long. With the best entry in the long row is 0.80, so the target is . The old guess in the cash, go long cell was 0.50, so the error is : the day went worse than the table expected, and the cell has to come down. How far down is the learning rate’s decision (Table 2):
| Learning rate | New estimate = old + error | In words |
|---|---|---|
| 0.2 | a fifth of the way to the target | |
| 0.9 | nearly all the way | |
| 1.0 | the target replaces the old guess |
The same arithmetic can be written as a blend, old target: . Same number, and the blend form makes plain that keeps nothing of the old guess and keeps all of it. Mitchell’s first version of the rule has no learning rate at all (equation 13.7, the row), because he starts with a world where the same action in the same state always gives the same reward and the same next state, so there is nothing to average. In a market there is, which is why the fraction matters.
One step, one cell, one fraction of the way. The target is reward now plus discounted best next; the learning rate decides how much of the gap one experience is allowed to close.
What the learning rate does over many updates
A single update is a fraction of the way. Repeated updates of the same cell towards the same target close the gap geometrically: after n updates the share of the original gap still open is . At ten updates leave of the gap; at they leave a tenth of a percent; at the second update is already within one percent. If the target never moved, a large learning rate would simply be faster (Figure 1, first panel).
Targets move. Each day’s reward is one draw from whatever the market does, so the target the rule builds is different every day even when the state is the same. To see what the learning rate does with that, take the long row’s “go long” cell, starting at 0.80, and feed it one update per day of the episodeOne natural run of interaction, such as one play of a game, ending in a terminal state before a reset.Reinforcement Learning · §3.3, p. 54 with the day’s reward as its reward and the rest of the table held still (so the “best next” term stays at and only the learning rate is at work). The ten targets, reward plus 0.72, run from on day 3 to on day 4, and their average is 1.12. Table 3 follows the cell at two learning rates:
| Learning rate | Estimate after each day, days 1 to 10 | Biggest day-to-day move |
|---|---|---|
| 0.2 | 0.70, 0.86, 0.60, 1.08, 1.00, 1.08, 1.26, 1.23, 1.20, 1.07 | 0.48 |
| 0.9 | 0.35, 1.38, −0.24, 2.69, 0.87, 1.37, 1.92, 1.17, 1.11, 0.59 | 2.93 |
At the estimate drifts towards the average of the targets and ends near it, at . At it is almost a copy of the latest target, swinging from to in a day, and it ends at only because the last day was poor. It has not settled, and it never will while the rewards keep varying (second panel).
Sutton and Barto give the mechanism (section 2.5). With a constant learning rate the estimate is a weighted averageAn average in which each value counts in proportion to its weight, instead of every value counting the same. of every target it has ever seen, with the weight on a target seen k updates ago equal to : the most recent target gets , the one before it a factor less, and so on, an exponentially fading memory. At the target from five updates ago still carries a weight of 0.066; at it carries nothing to three decimal places. A constant learning rate therefore never converges in the strict sense; the estimate keeps responding to the latest rewards, which the book notes is what you want when the true values drift, as a market’s do. The alternative is a learning rate that shrinks with each visit to the cell; if it shrinks slowly enough to overcome any starting value but fast enough to settle (their conditions 2.7), the estimate converges. The sample average, one over the number of visits, is the classic choice.
Off-policy: learning greedy while behaving otherwise
Look at the target once more. It uses the best entry in the next state’s row, whatever the learner goes on to do there. The learner’s own next action may be exploratory, a random choice made to see what happens; the target ignores it and asks what the greedy action would be worth. That is what makes Q-learning off-policyA method that evaluates or improves a policy different from the one that produced the data.Reinforcement Learning · §5.4, p. 100: the behaviour that generates experience and the policyThe agent's way of behaving: a mapping from the states it sees to the actions it takes in them.Reinforcement Learning · §1.3, p. 6 whose values are being learned are different policies. Sutton and Barto put it as the learned table “directly approximates” the optimal action values “independent of the policy being followed” (section 6.5). The behaviour policy still matters, but only in one way: it decides which cells get visited, and therefore which cells get updated.
The on-policyA method that evaluates or improves the same policy it uses to make decisions.Reinforcement Learning · §5.4, p. 100 cousin is Sarsa, whose target uses the next action the learner actually takes (equation 6.7). The two differ only in that one term, and the difference shows up where exploringChoosing a non-greedy action so you can improve your estimate of its value.Reinforcement Learning · §2.1, p. 26 is dangerous. In the book’s cliff-walking example (6.6), Q-learning learns the values of the shortest path along the cliff edge, because that is the greedy path, and then falls off it now and then while exploring; Sarsa, which counts its own exploratory stumbles in its targets, learns the longer, safer path and scores better while learning. Which is right depends on whether the agentThe learner and decision maker: the part that chooses actions.Reinforcement Learning · §3.1, p. 47 will keep exploring once deployed. For a trading agent that explores in a simulator and acts greedily on real capital, the Q-learning target is the one that matches.
When the table is right
Mitchell’s convergence theorem (13.1) says what it takes for the table to end up at the true values, in his deterministic world: rewards are bounded, the discount factorA setting that decides how much rewards further in the future are worth now, compared with a reward received right away.Reinforcement Learning · §3.3, p. 55 is below 1, and every state–action pair is visited infinitely often. Sutton and Barto’s statement for the random case adds the shrinking-learning-rate condition above (section 6.5). The visiting condition is the one to carry. The update touches one cell per step, so a cell the behaviour policy never reaches keeps its starting value forever, however long the learner runs. That is absence of evidence, not convergence, and a table can look stable because nothing is being updated rather than because the estimates are right. It is also why a learner that only ever takes the greedy action is in trouble: the cells it believes are worse are the ones it will never check, and Mitchell’s remark (section 13.3.5) is that convergence requires the agent to keep trying every action with some probability. Exploration: when to try something worse on purpose is about that choice.
Mitchell also gives the intuition behind convergence (section 13.3.4). Each update’s new value depends only partly on other error-prone estimates, the max over the next row, and that part is multiplied by ; the rest is the observed reward, which carries no estimation error. So the largest error in the table shrinks by at least a factor of each time every cell has been updated once. Values propagate backwards from wherever reward appears, one step per visit, which is why in his grid world a table of zeros changes nothing until the agent first reaches the goal, and then one more cell per episode (section 13.3.3).
Notation in other books
Sutton and Barto write the update on the time-indexed pair with reward and next state , and call the step-size parameterA small positive fraction in an update rule that controls how fast learning happens.Reinforcement Learning · §1.5, p. 10. Mitchell writes the same pair as with and , the estimate as , and, in his first treatment, assigns the target directly with no step size (his table 13.1). Ritter follows Sutton and Barto’s symbols and calls the step-size parameter too; in that paper it is restricted to the open interval between 0 and 1. The quantity in the bracket is the TD errorThe gap between a state's current value estimate and a better estimate built from the next reward and the next state's value.Reinforcement Learning · §6.1, p. 121, , in Sutton and Barto’s equation 6.5; some texts write the target as and the update as the blend .
Traps
Table 4 lists the usual misreadings.
| People think | Actually |
|---|---|
| A cell holds a probability | it holds an estimated return, in the reward’s units; rows are compared, not read as odds |
| The reward is discounted in the target | only the next state’s value is; the reward just received counts in full |
| A learning rate of 0 wipes the estimate | it freezes it; 1 replaces it with the target |
| Q-learning learns the value of what the agent does | it learns the value of acting greedily, whatever the agent does; that is the off-policy point |
| The update refreshes the whole table | one cell per step; unvisited cells keep their starting values |
| A table that has stopped changing has converged | it may just have stopped being visited, or be fed a learning rate too small to move |
| Taking the max is harmless | the max over noisy estimates is biased upwards (Sutton and Barto, section 6.7); double Q-learning is one fix |
The code
The snippet reproduces Table 2, the one update of the worked example at three learning rates. Its variables are in Table 5:
| Variable | Holds |
|---|---|
Q | the starting table: rows cash and long, columns go long and go cash, in percent |
reward | SPY’s return on 2023-01-03, the reward for going long that morning |
target | reward plus 0.9 times the best entry in the long row |
import pandas as pd
url = "https://raw.githubusercontent.com/ankurtrapasiya/examples/main/data/prices.csv"
px = pd.read_csv(url, index_col="date", parse_dates=True)["SPY"]
r = (px / px.shift(1) - 1).dropna()
reward = 100 * r[pd.Timestamp("2023-01-03")] # day 1's return, in percent
Q = pd.DataFrame({"go long": [0.50, 0.80], "go cash": [0.00, 0.10]}, index=["cash", "long"])
old = Q.loc["cash", "go long"] # the cell for what the learner just did
target = reward + 0.9 * Q.loc["long"].max() # reward now + gamma * best entry in the next row
for alpha in (0.2, 0.9, 1.0):
print(f"alpha {alpha}: {old:.2f} + {alpha} x ({target - old:+.2f}) = {old + alpha * (target - old):.2f}")
It prints three lines: , then 0.32 at 0.9, then 0.30 at 1.0. The
.loc["long"] picks a row of the table by its label and .max() takes the largest entry in it,
which is the max over actions in the formula.
The script behind the real numbers
The tables and the chart come from
examples/q-learning-one-update-rule/q_update.py,
which runs on the blog’s five tickers. To run it yourself, clone the examples repo: its README has a three-command Docker setup, or run uv run q-learning-one-update-rule/q_update.py.
Summary
Table 6 is the post in one line per idea.
| Idea | In one line | On the January 2023 episode |
|---|---|---|
| Q-table | one cell per state and action, holding an estimated return | cash, go long starts at 0.50 |
| Target | reward now plus times the best entry in the next row | |
| Error | target minus the old estimate | 0.30 − 0.50 = −0.20 |
| Learning rate | the fraction of the error applied | 0.46 at 0.2, 0.32 at 0.9, 0.30 at 1 |
| Constant α | an exponentially fading average of past targets | 0.2 ends near the mean target, 0.9 copies the last one |
| Off-policy | the target uses the greedy next action, not the one taken | Sarsa would use the action actually taken |
| Convergence | every pair visited again and again, with a shrinking α | an unvisited cell stays at its starting value |
References
- Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition (MIT Press, 2018). Section 6.1 for the TD(0) update, bootstrappingUpdating value estimates from other value estimates, such as those of the states that come next.Reinforcement Learning · §4.8, p. 89 and the TD error (equations 6.2 and 6.5); section 6.4 for Sarsa and its on-policy target (equation 6.7); section 6.5 for the Q-learning update (equation 6.8), the off-policy property, the convergence conditions and the procedural algorithm; Example 6.6 for cliff walking; section 6.7 for maximisation bias and double learning; section 2.5 for the constant step size as an exponential recency-weighted average (equation 2.6) and the stochastic approximation conditions (2.7); Example 6.2 for estimates that keep fluctuating under a constant step size.
- Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997). Section 13.3.1 for the Q function; section 13.3.2 for the table of estimates and the deterministic training rule (equation 13.7, table 13.1); section 13.3.3 for the worked single update and the backward propagation of values; section 13.3.4 for the convergence theorem (13.1) and the error shrinking by γ; section 13.3.5 for why every action must keep being tried.
- Gordon Ritter, Machine Learning for Trading (2017, SSRN 3015609). Section 3.3 for the greedy and ε-greedyA near-greedy rule: usually take the best-looking action, but sometimes pick among all actions at random with equal chance.Reinforcement Learning · §2.2, p. 28 policies; section 3.4 for the Q-matrix initialised to zero or to prior information and the update rule with its step-size parameter.