Q-learning: one update rule, repeated

The previous post ended with a promise: if the learner had the action values, the values of doing each action in each state, acting would be one line long, take the largest. It also ended with the hard part, filling those values in from experience, when the environment hands over one reward at a time and never says what the value was. Q-learning 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 rate does.

The table

The Q-table 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).

Here is a tiny one, two states and two actions, with starting guesses I made up, in percent of the position:

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 probability and not a next state. The greedy 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 $\key{\alpha}$ 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, $\good{-0.42\%}$, and lands in state long. With $\key{\gamma} = \key{0.9}$ the best entry in the long row is 0.80, so the target is $-0.42 + 0.9 \times 0.80 = \good{0.30}$. The old guess in the cash, go long cell was 0.50, so the error is $0.30 - 0.50 = \risk{-0.20}$: the day went worse than the table expected, and the cell has to come down. How far down is the learning rate’s decision:

The same arithmetic can be written as a blend, $(1 - \alpha) \times$ old $+\ \alpha \times$ target: $0.8 \times 0.50 + 0.2 \times 0.30 = 0.46$. Same number, and the blend form makes plain that $\key{\alpha} = 1$ keeps nothing of the old guess and $\key{\alpha} = 0$ keeps all of it. Mitchell’s first version of the rule has no learning rate at all (equation 13.7, the $\key{\alpha} = 1$ 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 $(1 - \key{\alpha})^n$. At $\key{\alpha} = \key{0.2}$ ten updates leave $\risk{10.7\%}$ of the gap; at $\key{0.5}$ they leave a tenth of a percent; at $\key{0.9}$ the second update is already within one percent. If the target never moved, a large learning rate would simply be faster.

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 episode with the day’s reward as its reward and the rest of the table held still (so the “best next” term stays at $0.9 \times 0.80 = 0.72$ and only the learning rate is at work). The ten targets, reward plus 0.72, run from $\bad{-0.42}$ on day 3 to $\good{3.01}$ on day 4, and their average is 1.12:

At $\key{0.2}$ the estimate drifts towards the average of the targets and ends near it, at $\key{1.07}$. At $\key{0.9}$ it is almost a copy of the latest target, swinging from $\bad{-0.24}$ to $\good{2.69}$ in a day, and it ends at $\key{0.59}$ only because the last day was poor. It has not settled, and it never will while the rewards keep varying.

Sutton and Barto give the mechanism (section 2.5). With a constant learning rate the estimate is a weighted average of every target it has ever seen, with the weight on a target seen k updates ago equal to $\key{\alpha}(1 - \key{\alpha})^k$: the most recent target gets $\key{\alpha}$, the one before it a factor $(1 - \key{\alpha})$ less, and so on, an exponentially fading memory. At $\key{\alpha} = \key{0.2}$ the target from five updates ago still carries a weight of 0.066; at $\key{0.9}$ 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-policy: the behaviour that generates experience and the policy 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-policy 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 exploring 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 agent 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 factor 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 $\key{\gamma}$; 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 $\key{\gamma}$ 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).

Traps

The code

The snippet reproduces the one update of the worked example at three learning rates. Variables:

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: 0.50 + 0.2 × (−0.20) = 0.46, 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.

Summary

References

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition (MIT Press, 2018). Section 6.1 for the TD(0) update, bootstrapping 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 ε-greedy policies; section 3.4 for the Q-matrix initialised to zero or to prior information and the update rule with its step-size parameter.