Exploration: when to try something worse on purpose

Q-learning: one update rule, repeated ended on a condition: the Q-table converges only if every state–action pair keeps being visited. The update rule does not decide which pairs get visited. The learner’s way of choosing actions does, and if that way is “take the action the table rates best”, a cell the table underrates is a cell the learner never checks. This post is about that choice. It uses Sutton and Barto’s simplest setting, a bandit with one state and ten actions, reproduced in a few lines of numpy with made-up rewards, because the problem is the same there as in a full Q-table and far easier to see. No prices are involved; the market only enters at the end, where it adds a complication the bandit does not have.

Greedy gets stuck

Sutton and Barto open their book’s methods with the k-armed bandit: you face the same choice of k actions again and again, each action pays a reward drawn from its own fixed distribution, and you want the largest total reward over, say, a thousand choices (section 2.1). The value of an action is its mean reward. The learner does not know it, so it keeps an estimate: the average of the rewards that action has paid so far (section 2.2, their equation 2.1).

The action whose estimate is currently the largest is the greedy action. Taking it is exploiting what you know; taking any other is exploring, and the point of exploring is that it improves the estimate of an action you might be wrong about. The two cannot happen on the same step, which is the whole conflict: exploiting is right for this step’s reward, exploring may be right for the total.

Their ten-armed testbed shows what pure exploiting costs (section 2.3). Two thousand tasks, each with ten actions whose true values are drawn at random, each reward the true value plus noise. The greedy learner, averaged over the tasks, settled at a reward per step of about 1 when the best action would have paid about 1.54, and it was on the best action in only about a third of the tasks. In the other two thirds the best action’s first rewards happened to be disappointing, its estimate fell below some other action’s, and the learner never went back. One bad draw became a permanent belief.

A greedy learner cannot correct an underestimate. The action it rates too low is exactly the one it stops trying, so no new evidence about it ever arrives.

Epsilon-greedy: a random action, once in a while

The plain fix is to behave greedily most of the time and, with a small probability, pick an action at random from all of them, including the greedy one (section 2.2). The probability is called epsilon, $\key{\varepsilon}$, and the rule epsilon-greedy. The chance that any given step lands on the greedy action is then

ε, the probability of a random stepA, the number of actions

$$P(\text{greedy}) = 1 - \key{\varepsilon} + \frac{\key{\varepsilon}}{\good{|A|}}$$ $$P(\text{each other action}) = \frac{\key{\varepsilon}}{\good{|A|}}$$

The second term is the random branch landing on the greedy action by chance. With $\key{\varepsilon} = \key{0.1}$ and ten actions the greedy action is taken $\key{91\%}$ of the time and each other action $\key{1\%}$, which is why the book notes that the 0.1 learner “never selected that action more than 91% of the time” even once it knew which action was best. With $\key{\varepsilon} = \key{0.2}$ and three actions, the greedy share is $\key{86.7\%}$ and each other action gets $\key{6.7\%}$, not 20%: epsilon is split across the actions, not given to each.

Table 1 is the testbed rerun with 2,000 tasks and three choosers, from the script behind this post:

The best possible reward per step, if every task’s best action were known, is 1.53. The greedy learner stops improving almost at once and stays at $\risk{35\%}$. The learner exploring one step in ten finds the best action fastest and is on it in $\good{80\%}$ of tasks by the end, but it can never go above 91%, because a tenth of its steps are random by design. The learner exploring one step in a hundred climbs slowly and is still climbing at step 1,000; given enough steps it would pass the other, since it wastes only 1% of its steps once it knows. That trade, the first panel of Figure 1, is the shape of the whole subject: exploring more finds good actions sooner, then costs a fixed share of every step; exploring less learns slowly, then exploits better.

Shrinking epsilon

The book’s own suggestion follows from Table 1: reduce epsilon over time to get the fast start of a large value and the clean exploiting of a small one (section 2.3). The usual way is to multiply it by a factor just under 1 after every step or episode, so that after n steps it is

ε, the exploration probability after n stepsd, the factor applied each step

$$\key{\varepsilon_n} = \varepsilon_0 \cdot \good{d}^{\,n}$$

This is the same geometric decay as the discount factor in the MDP post, pointed at a different quantity. Starting from 1 (Table 2, and the second panel of Figure 1):

At $\good{0.9}$ exploration is effectively over after fifty steps, long before a table of any size has been covered; whatever the first fifty random steps happened to find is what the learner keeps. At $\good{0.999}$ it is still exploring more than a third of the time after a thousand steps. The factor is a statement about how long the learner is allowed to be wrong, and the honest way to pick it is to count: how many state–action pairs are there, and how many visits does each need before its estimate means anything? A hundred states with three actions is 300 cells, and a rule that stops exploring after 50 steps has not seen most of them once.

Two things the decay does not do. It never reaches zero, however small it gets, but it does not keep the infinite-visits condition either: the random steps it still allows thin out so fast that their total is finite, and once epsilon is a thousandth a wrong cell is rarely checked again. And a learner whose epsilon has decayed can look finished when it has merely stopped looking: a table that has stopped changing is evidence that nothing is being updated, not that the estimates are right. The Q-learning post made the same point about the learning rate.

Stochastic is not nonstationary

The bandit above is stochastic: each action’s rewards vary from draw to draw, but around a mean that never moves. The learner’s job is to average through the noise, and the sample average does that; by the law of large numbers it converges to the true value (section 2.2). A single good reward from an action is one draw, and acting on it as if it were the value is the mistake that trapped the greedy learner.

A nonstationary problem is different in kind: the true values themselves change over time (section 2.3). Now exploration is needed even if the rewards had no noise at all, because an action that was worse last month may be better this month, and only trying it will show that. Sutton and Barto say this is the case “most commonly encountered in reinforcement learning”, and a market is one: the net value of a trade in a given state depends on conditions that move. The averaging method has to change too. A sample average weights every past reward equally and so, after a year, barely reacts to a new month; a constant step size weights recent rewards more, with the weight on a reward seen k steps ago fading as $(1-\alpha)^k$ (section 2.5, their equation 2.6). That is the exponentially fading memory from the learning-rate section of the Q-learning post, and here is the reason for it: in a world that drifts, forgetting is a feature.

Different samples do not mean the world changed. A stable distribution gives different draws every time; nonstationarity is the distribution itself moving. The first needs averaging, the second needs averaging that forgets, and both need exploring to keep going.

Exploring with real money

A bandit explores for free; a random pull costs nothing but the reward it might have earned. A trading agent that takes a random action is placing a trade it has no reason to place, and paying spread and commission for it. Ritter’s paper, whose update rule the Q-learning post used, handles this by separating two things. The learning uses an epsilon-greedy policy, because that is what guarantees every action keeps being sampled (his section 3.3). The learning does not happen on the market: he proposes fitting a small model of asset returns to real data, simulating a far larger data set from it, and training the agent on the simulation until its table converges (his section 5), noting that the real problem needed a few million training steps, more than most financial histories contain.

The split that follows is the one to carry into the rest of the series. Training behaviour and deployed behaviour are different policies. In training the agent explores, on simulated or historical data, where a bad action costs nothing. Once deployed it acts greedily on the table it learned, taking the random branch out. What remains random is the market, not the agent, and that is where the nonstationarity section bites: a deployed agent that has stopped exploring and stopped learning is a frozen table in a moving world. It will not notice that its best action has stopped being best; the only things that can notice are its logs and the person reading them. Ritter’s own answer to overfitting is the same as his answer to data: the agent is only as good as the simulator it practised in, which is where Dyna: learn a model of the world, then practise in it picks up.

Two other ways to explore

Sutton and Barto give two alternatives to epsilon-greedy in the same chapter. Optimistic initial values (section 2.6): start every estimate far above any plausible reward, say +5 when the true values are around 0, so whichever action is tried first disappoints the learner and it moves on to the next; every action gets tried several times even by a greedy chooser. The book calls it a useful trick on stationary problems and no help on nonstationary ones, because its urge to explore is used up at the start and never renews. Upper confidence bound selection (section 2.7, equation 2.10): add to each estimate a bonus that grows with how rarely the action has been tried, so exploration goes to the uncertain actions rather than to all of them equally. It does well on the testbed and, the book says, is hard to carry beyond bandits to full reinforcement learning with large state spaces.

Traps

Table 3 lists the usual misreadings.

The code

The snippet reruns the ten-armed testbed on 500 tasks and prints how often each chooser is on the best action at the last step. The data is synthetic: each task’s true action values are drawn once, and each reward is that value plus unit noise, which is the book’s construction. Its variables are in Table 4:

import numpy as np

rng = np.random.default_rng(0)
runs, steps, arms = 500, 1000, 10
q_true = rng.normal(size=(runs, arms))          # each task's true value per action, unknown to the learner
best = q_true.argmax(axis=1)
rows = np.arange(runs)

for eps in (0.0, 0.01, 0.1):
    Q, N = np.zeros((runs, arms)), np.zeros((runs, arms))
    for t in range(steps):
        greedy = Q.argmax(axis=1)                                  # the action rated best so far
        explore = rng.random(runs) < eps                           # with probability eps...
        a = np.where(explore, rng.integers(arms, size=runs), greedy)  # ...pick any action at random
        r = rng.normal(q_true[rows, a])                            # reward: true value plus noise
        N[rows, a] += 1
        Q[rows, a] += (r - Q[rows, a]) / N[rows, a]                # running average of the rewards seen
    print(f"epsilon {eps}: best action taken in {100 * (a == best).mean():.0f}% of tasks at step {steps}")

It prints three lines: 37% for epsilon 0, 61% for 0.01, 82% for 0.1. The numbers differ a little from Table 1 because this run uses 500 tasks and breaks ties in the estimates by taking the first action rather than a random one. Q[rows, a] picks one cell per task, the action each task took, and the last line is the incremental average from the book’s equation 2.3: move the estimate towards the new reward by one over the number of times the action has been taken.

The script behind the real numbers

The tables and the chart come from examples/exploration-try-something-worse/exploration.py, which uses made-up bandit rewards rather than 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 exploration-try-something-worse/exploration.py.

Summary

Table 5 is the post in one line per idea.

References

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition (MIT Press, 2018). Section 2.1 for the k-armed bandit, action values, greedy actions, exploiting and exploring; section 2.2 for the sample-average estimate (equation 2.1), greedy selection (2.2) and the epsilon-greedy rule with its infinite-sampling guarantee; section 2.3 for the ten-armed testbed, the greedy learner’s reward of about 1 against a best of about 1.54, its one-third success rate, the 91% ceiling at $\varepsilon = 0.1$, the suggestion to reduce ε over time, and the nonstationary case; section 2.4 for the incremental average (equation 2.3); section 2.5 for the constant step size as a recency-weighted average (equation 2.6); section 2.6 for optimistic initial values; section 2.7 for upper-confidence-bound selection (equation 2.10).
• Gordon Ritter, Machine Learning for Trading (2017, SSRN 3015609). Section 3.3 for the epsilon-greedy policy as the way to keep every action sampled; section 5 for training on a simulated data set built from a small fitted model of returns, the few million steps the real problem needed, and overfitting as a property of the model the agent practised in.