The Reinforcement Learning Framework
Chapter Seventy-Eight
Syllabus topic Module 2, "Reinforcement learning framework"
Pages 495 to 504 of 591
In one line
An agent acts, the world answers with a number, and the agent must work out for itself which of its past actions earned it.
This is the third setting in the syllabus, after supervised and unsupervised learning, and it is different from both in a way worth being precise about.
The vocabulary
Every one of these will be used in the next three chapters.
| Term | Meaning |
|---|---|
| Agent | the thing that chooses |
| Environment | everything else |
| State | what the agent observes at a step |
| Action | what it may do |
| Reward | a single number the environment returns |
| Policy | a rule giving an action for each state, written as a mapping |
| Return | the total reward from a step onwards, usually discounted |
| Value | the expected return from a state under a policy |
| Episode | one run from a start state to a terminal state |
Keep reward and value apart. A reward is what arrives at one step; a value is the whole future expected from a state. A state with reward 0 can have a high value, because of what follows it.
Three ways it differs from supervised learning
A paper asking "how does reinforcement learning differ" wants these three, not one.
1. The feedback is evaluative, not instructive. Supervised learning is told the correct label. A reinforcement learner is told how good its action was and never what it should have done.
2. The reward is delayed. The move that lost the game may be the tenth before the end, and the agent must work out which of its past actions to credit or blame. This is the credit assignment problem, and it is the central difficulty.
3. The agent generates its own data. What the agent sees depends on what it did, so a poor policy collects a poor data set and may never observe the states where it would have learned better. Nothing in supervised learning has this property, and it is the reason for the whole exploration question below.
The measurement
# The reinforcement learning setting, measured: what a reward is, why a discount
# changes the answer rather than only the arithmetic, and why an agent that
# always takes the best known action can be permanently wrong.
def lcg(seed):
x = seed
while True:
x = (1664525 * x + 1013904223) % (2 ** 32)
yield x / 2 ** 32
gen = lcg(4242)
rnd = lambda: next(gen) # noqa: E731
print("THE SETTING. an AGENT acts in an ENVIRONMENT. at each step it observes a")
print("STATE, chooses an ACTION, receives a REWARD and lands in a new state. it")
print("is told NOTHING about which action was right; only the reward arrives.")
print()
print(" policy : a rule giving the action to take in each state")
print(" return : the total reward from a step onwards, usually DISCOUNTED")
print(" value : the expected return from a state under a policy")
print(" episode : one run from a start state to a terminal state")
print()
print("WHAT MAKES IT DIFFERENT FROM SUPERVISED LEARNING")
print(" the feedback is a REWARD, not a correct answer: the agent is told how")
print(" good its action was, never what it should have done.")
print(" the reward is DELAYED: the move that lost the game may be the tenth")
print(" before the end. this is the CREDIT ASSIGNMENT problem.")
print(" the data is not given: the agent's own actions decide what it sees,")
print(" so a bad policy collects a bad data set.")
print()
print("A CORRIDOR, to show what the discount actually does.")
print(" five rooms in a line. from the start the agent may go LEFT and collect")
print(" 5 after one step, or go RIGHT and collect 20 after four steps.")
print(" which is better is NOT a fact about the corridor. it depends on the")
print(" discount factor, and the discount factor is part of the problem.")
print()
print(" gamma | left: 5 after 1 step | right: 20 after 4 steps | choose")
for g in (0.5, 0.7, 0.8, 0.9, 0.95, 1.0):
left = g ** 1 * 5
right = g ** 4 * 20
print(" %5.2f | %20.4f | %23.4f | %s"
% (g, left, right, "LEFT" if left > right else "RIGHT"))
print()
print(" the switch happens where gamma**1 * 5 = gamma**4 * 20, that is where")
print(" gamma**3 = 0.25, at gamma = %.4f. BELOW it the agent is short sighted"
% (0.25 ** (1.0 / 3)))
print(" and takes the near reward; above it, patient.")
print()
print(" AND WHY DISCOUNT AT ALL, since it changes the answer?")
print(" 1. a reward now is worth more than the same reward later, which is")
print(" true of money, of marks and of most things.")
print(" 2. without it, a task that never ends has an INFINITE return and")
print(" every policy is equally good. with gamma below 1 the sum")
print(" converges: a reward of 1 for ever is worth 1/(1-gamma) =")
print(" %.1f at gamma = 0.9, not infinity." % (1 / (1 - 0.9)))
print(" 3. it expresses uncertainty about the future continuing at all.")
print()
print("EXPLORATION AGAINST EXPLOITATION, which is the other thing that makes")
print("reinforcement learning hard. three actions with unknown payoffs:")
ARMS = [("A", 0.30), ("B", 0.55), ("C", 0.50)]
print(" action | true probability of a reward of 1")
for name, p in ARMS:
print(" %6s | %.2f" % (name, p))
print(" the agent is NOT told these. it must find the best by trying.")
print()
def pull(i):
return 1.0 if rnd() < ARMS[i][1] else 0.0
def run(epsilon, steps, seed):
"""Try each action ONCE, then act. Ties are broken by the lowest index, so
the first pulls matter: that is the whole point of the measurement."""
global gen, rnd
gen = lcg(seed)
rnd = lambda: next(gen) # noqa: E731
total = [0.0] * len(ARMS)
tries = [0] * len(ARMS)
reward = 0.0
for i in range(len(ARMS)):
r = pull(i)
total[i] += r
tries[i] += 1
reward += r
for _ in range(steps - len(ARMS)):
means = [total[i] / tries[i] for i in range(len(ARMS))]
if rnd() < epsilon:
i = min(int(rnd() * len(ARMS)), len(ARMS) - 1)
else:
i = max(range(len(ARMS)), key=lambda j: means[j])
r = pull(i)
total[i] += r
tries[i] += 1
reward += r
means = [total[i] / tries[i] for i in range(len(ARMS))]
believes = ARMS[max(range(len(ARMS)), key=lambda j: means[j])][0]
return reward, tries, believes
print(" PURE EXPLOITATION, epsilon = 0: try each action once, then always take")
print(" the one with the best average so far. ten runs of 500 steps:")
print(" run | reward | times each action was taken | believes best")
wrong = 0
for s in range(10):
reward, tries, believes = run(0.0, 500, 1000 + s * 7919)
if believes != "B":
wrong += 1
print(" %3d | %6.0f | %-27s | %s" % (s + 1, reward, str(tries), believes))
print(" %d of 10 runs ended believing the wrong action was best, and in every" % wrong)
print(" one of those the agent had stopped trying the others ENTIRELY. a greedy")
print(" agent whose first pull of the best action happens to pay nothing will")
print(" never pull it again, because pulling it is not the best action")
print(" according to what it knows. the mistake is permanent.")
print()
print(" EPSILON-GREEDY, epsilon = 0.10: take a random action one time in ten.")
print(" run | reward | times each action was taken | believes best")
wrong2 = 0
for s in range(10):
reward, tries, believes = run(0.10, 500, 1000 + s * 7919)
if believes != "B":
wrong2 += 1
print(" %3d | %6.0f | %-27s | %s" % (s + 1, reward, str(tries), believes))
print(" %d of 10 runs ended on the wrong action, and every action is still" % wrong2)
print(" being sampled, so a wrong belief can still be corrected.")
print()
print(" AND THE COST OF EXPLORING, over 2000 steps:")
print(" epsilon | mean reward over 10 runs | runs believing the best action")
for eps in (0.0, 0.01, 0.05, 0.10, 0.30, 1.0):
tot, right = 0.0, 0
for s in range(10):
reward, tries, believes = run(eps, 2000, 1000 + s * 7919)
tot += reward
if believes == "B":
right += 1
print(" %7.2f | %24.1f | %d of 10" % (eps, tot / 10, right))
print()
print(" READ THE TWO COLUMNS TOGETHER, because neither alone is the answer.")
print(" epsilon = 0 is the cheapest policy and the least reliable. epsilon = 1")
print(" never stops exploring: it identifies the best action most often and")
print(" collects the AVERAGE payoff of the three, because it never uses what")
print(" it has learnt. the useful values are in between, and the whole subject")
print(" of reinforcement learning is spent between them.")
print()
print(" IN PRACTICE epsilon is DECAYED: explore heavily at first and less as")
print(" the estimates settle, which buys the identification without paying for")
print(" it for ever.")The Reinforcement Learning Framework
THE SETTING. an AGENT acts in an ENVIRONMENT. at each step it observes a
STATE, chooses an ACTION, receives a REWARD and lands in a new state. it
is told NOTHING about which action was right; only the reward arrives.
policy : a rule giving the action to take in each state
return : the total reward from a step onwards, usually DISCOUNTED
value : the expected return from a state under a policy
episode : one run from a start state to a terminal state
WHAT MAKES IT DIFFERENT FROM SUPERVISED LEARNING
the feedback is a REWARD, not a correct answer: the agent is told how
good its action was, never what it should have done.
the reward is DELAYED: the move that lost the game may be the tenth
before the end. this is the CREDIT ASSIGNMENT problem.
the data is not given: the agent's own actions decide what it sees,
so a bad policy collects a bad data set.
A CORRIDOR, to show what the discount actually does.
five rooms in a line. from the start the agent may go LEFT and collect
5 after one step, or go RIGHT and collect 20 after four steps.
which is better is NOT a fact about the corridor. it depends on the
discount factor, and the discount factor is part of the problem.
gamma | left: 5 after 1 step | right: 20 after 4 steps | choose
0.50 | 2.5000 | 1.2500 | LEFT
0.70 | 3.5000 | 4.8020 | RIGHT
0.80 | 4.0000 | 8.1920 | RIGHT
0.90 | 4.5000 | 13.1220 | RIGHT
0.95 | 4.7500 | 16.2901 | RIGHT
1.00 | 5.0000 | 20.0000 | RIGHT
the switch happens where gamma**1 * 5 = gamma**4 * 20, that is where
gamma**3 = 0.25, at gamma = 0.6300. BELOW it the agent is short sighted
and takes the near reward; above it, patient.
AND WHY DISCOUNT AT ALL, since it changes the answer?
1. a reward now is worth more than the same reward later, which is
true of money, of marks and of most things.
2. without it, a task that never ends has an INFINITE return and
every policy is equally good. with gamma below 1 the sum
converges: a reward of 1 for ever is worth 1/(1-gamma) =
10.0 at gamma = 0.9, not infinity.
3. it expresses uncertainty about the future continuing at all.
EXPLORATION AGAINST EXPLOITATION, which is the other thing that makes
reinforcement learning hard. three actions with unknown payoffs:
action | true probability of a reward of 1
A | 0.30
B | 0.55
C | 0.50
the agent is NOT told these. it must find the best by trying.
PURE EXPLOITATION, epsilon = 0: try each action once, then always take
the one with the best average so far. ten runs of 500 steps:
run | reward | times each action was taken | believes best
1 | 152 | [498, 1, 1] | A
2 | 275 | [1, 498, 1] | B
3 | 281 | [1, 498, 1] | B
4 | 249 | [1, 1, 498] | C
5 | 282 | [1, 496, 3] | B
6 | 296 | [1, 498, 1] | B
7 | 150 | [498, 1, 1] | A
8 | 139 | [498, 1, 1] | A
9 | 270 | [3, 495, 2] | B
10 | 268 | [5, 493, 2] | B
4 of 10 runs ended believing the wrong action was best, and in every
one of those the agent had stopped trying the others ENTIRELY. a greedy
agent whose first pull of the best action happens to pay nothing will
never pull it again, because pulling it is not the best action
according to what it knows. the mistake is permanent.
EPSILON-GREEDY, epsilon = 0.10: take a random action one time in ten.
run | reward | times each action was taken | believes best
1 | 269 | [25, 456, 19] | B
2 | 271 | [17, 461, 22] | B
3 | 266 | [18, 466, 16] | B
4 | 259 | [13, 29, 458] | C
5 | 260 | [22, 104, 374] | B
6 | 292 | [22, 459, 19] | B
7 | 261 | [17, 465, 18] | B
8 | 235 | [44, 26, 430] | C
9 | 262 | [18, 458, 24] | B
10 | 279 | [19, 461, 20] | B
2 of 10 runs ended on the wrong action, and every action is still
being sampled, so a wrong belief can still be corrected.
AND THE COST OF EXPLORING, over 2000 steps:
epsilon | mean reward over 10 runs | runs believing the best action
0.00 | 949.7 | 6 of 10
0.01 | 1044.1 | 8 of 10
0.05 | 1075.9 | 8 of 10
0.10 | 1075.4 | 10 of 10
0.30 | 1034.5 | 9 of 10
1.00 | 911.5 | 10 of 10
READ THE TWO COLUMNS TOGETHER, because neither alone is the answer.
epsilon = 0 is the cheapest policy and the least reliable. epsilon = 1
never stops exploring: it identifies the best action most often and
collects the AVERAGE payoff of the three, because it never uses what
it has learnt. the useful values are in between, and the whole subject
of reinforcement learning is spent between them.
IN PRACTICE epsilon is DECAYED: explore heavily at first and less as
the estimates settle, which buys the identification without paying for
it for ever.The Reinforcement Learning Framework
The discount factor changes the answer
Five rooms in a line. From the start, going left collects 5 after one step; going right collects 20 after four steps. Which is better?
The Reinforcement Learning Framework
| gamma | Left, 5 after 1 step | Right, 20 after 4 steps | Choose |
|---|---|---|---|
| 0.50 | 2.5000 | 1.2500 | LEFT |
| 0.70 | 3.5000 | 4.8020 | RIGHT |
| 0.90 | 4.5000 | 13.1220 | RIGHT |
| 1.00 | 5.0000 | 20.0000 | RIGHT |
The Reinforcement Learning Framework
The question has no answer until gamma is fixed. The switch is where gamma1 5 = gamma4 20, that is gamma3 = 0.25, at gamma = 0.6300**. Below it the agent is short-sighted and takes the near reward; above it, patient.
The Reinforcement Learning Framework
So the discount factor is part of the problem, not a setting of the solver. A paper that treats gamma as a tuning knob like a learning rate has misunderstood it: changing gamma changes which policy is optimal.
And why discount at all, given that it changes the answer. Three reasons, all worth giving:
| 1 | A reward now is worth more than the same reward later, which is true of money, of marks, and of most things. |
| 2 | Without it, a task that never ends has an infinite return and every policy is equally good. With gamma below 1 the sum converges: a reward of 1 for ever is worth 1/(1 - gamma), which is 10.0 at gamma = 0.9, not infinity. |
| 3 | It expresses uncertainty about whether the future will arrive at all. |
Episodic tasks, which end, can use gamma = 1 safely. Continuing tasks, which do not, cannot.
Exploration against exploitation
The second difficulty, and the one that has no clean solution. Three actions, with unknown payoff probabilities of 0.30, 0.55 and 0.50. The agent must find the best by trying.
The Reinforcement Learning Framework
Pure exploitation, epsilon = 0: try each action once, then always take the one with the best average.
| Run | Reward | Times each action taken | Believes best |
|---|---|---|---|
| 1 | 152 | 498, 1, 1 | A, the worst |
| 2 | 275 | 1, 498, 1 | B |
| 4 | 249 | 1, 1, 498 | C |
The agent commits to whichever action happened to pay on its single first trial, and in run 1 that was the worst of the three, pulled 498 times out of 500. Four of ten runs ended believing the wrong action was best, and in every one of them the other actions had stopped being tried at all.
The trap stated plainly: an agent whose first trial of the best action pays nothing will never try it again, because trying it is not the best action according to what it knows. The mistake is self-sealing and permanent.
Epsilon-greedy is the standard repair: with probability epsilon, take a random action; otherwise take the best known one. At epsilon = 0.10, two of ten runs ended on the wrong action, and every action was still being sampled, so a wrong belief could still be corrected.
The cost of exploring, measured
epsilon | Mean reward over 2000 steps | Runs believing the best action |
|---|---|---|
| 0.00 | 949.7 | 6 of 10 |
| 0.01 | 1044.1 | 8 of 10 |
| 0.05 | 1075.9 | 8 of 10 |
| 0.10 | 1075.4 | 10 of 10 |
| 0.30 | 1034.5 | 9 of 10 |
| 1.00 | 911.5 | 10 of 10 |
Read both columns together, because neither alone is the answer.
epsilon = 0 collects the least and is the least reliable. epsilon = 1 identifies the best action every time and collects the least but one, because it never uses what it has learned: it earns the average payoff of the three actions for ever. The best total is around 0.05 to 0.10, which explores enough to be sure and then spends most of its steps on the answer.
In practice epsilon is decayed: explore heavily at first and less as the estimates settle, which buys the identification without paying for it for ever. Optimistic initial values are the other standard trick: start every action's estimate too high, so that any action not yet tried looks attractive and gets tried once by a purely greedy agent.
Designing the reward
The reward is not given by nature; somebody writes it, and a badly written one is the commonest cause of a strange policy.
| Danger | What happens |
|---|---|
| Reward hacking | the agent finds a way to earn the number without doing the intended task |
| Rewarding the method rather than the goal | the agent does the method and not the goal; reward the outcome |
| Sparse rewards | nothing but a win at the end gives almost no signal to learn from |
| Shaping | intermediate rewards help, and can change the optimal policy if added carelessly |
The Reinforcement Learning Framework
The reward hypothesis is the assumption the whole field rests on: that every goal can be expressed as the maximisation of the expected value of a single scalar reward. It is an assumption, and Ethical Issues in AI Systems returns to what happens when a real objective does not fit in one number.
Where it is used
| Field | The reward |
|---|---|
| Board and video games | winning |
| Robot control | staying upright, reaching a target |
| Recommendation | a click, a purchase, time spent |
| Scheduling and routing | throughput, delay avoided |
| Tuning a large language model | a human preference between two answers |
The third row is worth pausing over: a system rewarded for time spent will learn to hold attention, which is not the same as being useful, and that is reward hacking in production rather than in a laboratory.
Distinctions
| Supervised | Reinforcement | |
|---|---|---|
| Feedback | the correct answer | a number |
| When | immediately | delayed |
| Data | given | the agent's own actions decide it |
| Difficulty | generalisation | credit assignment, exploration |
| Reward | Value | |
|---|---|---|
| Covers | one step | the whole future |
| Given by | the environment | estimated by the agent |
| A state with reward 0 | is worth nothing now | may be worth a great deal |
epsilon = 0 | epsilon = 1 | |
|---|---|---|
| Explores | never | always |
| Reward here | 949.7 | 911.5 |
| Found the best | 6 of 10 | 10 of 10 |
| Fails by | committing to a mistake | never using what it knows |
What it does not mean
Reinforcement learning is not supervised learning with delayed labels. There is no label at any point; only a number saying how good the action was.
The discount factor is not a tuning parameter. It changes which policy is optimal, here at gamma 0.6300.
Gamma below 1 is not always required. Episodic tasks can use 1; continuing tasks cannot, or the return is infinite.
A greedy agent does not converge on the best action. Here it committed to the worst action in one run of ten and never revisited it.
More exploration is not better. epsilon = 1 identified the best action every time and earned less than epsilon = 0.05.
A high reward is not evidence of the intended behaviour. That is reward hacking.
Quick revision
- Agent, environment, state, action, reward, policy, return, value, episode. A reward is one step; a value is the expected return from a state.
- Three differences from supervised learning: feedback is evaluative, not instructive; the reward is delayed, giving the credit assignment problem; the agent's actions generate its own data.
- The discount changes the answer. 5 after one step against 20 after four: LEFT below
gamma = 0.6300, RIGHT above, since the switch is atgamma**3 = 0.25. - Why discount: a reward now is worth more; a continuing task would otherwise have infinite return, whereas
1/(1-gamma)is 10.0 atgamma = 0.9; and the future may not arrive. Episodic tasks may usegamma = 1, continuing ones may not. - Greedy fails permanently. Three actions at 0.30, 0.55, 0.50: a purely greedy agent commits to whichever paid on its single first trial, took the worst action 498 times in one run, and ended wrong in 4 of 10.
- Epsilon-greedy at 0.10: wrong in 2 of 10, and still sampling everything.
- Cost of exploring over 2000 steps:
0.00gives 949.7 and 6 of 10;0.05gives 1075.9;0.10gives1075.4and 10 of 10;1.00gives 911.5 and 10 of 10. The best totals are in between. - Practice: decay epsilon, or use optimistic initial values.
- Reward design: beware reward hacking, rewarding the method instead of the goal, and sparse rewards; shaping helps and can change the optimal policy. The reward hypothesis is that any goal can be written as one scalar to maximise.
The Reinforcement Learning Framework
Test yourself
1. Give three ways reinforcement learning differs from supervised learning. The feedback is a reward saying how good the action was rather than the correct answer; the reward is delayed, so the agent must decide which earlier action to credit, which is the credit assignment problem; and the agent's own choices determine what data it sees, so a poor policy can collect data that never reveals a better one.
2. Distinguish a reward from a value. A reward is the single number the environment returns at one step. A value is the expected total discounted reward from a state onwards under a policy, so a state paying nothing immediately can still have a high value because of what follows it.
3. Show that the discount factor can change which policy is optimal. Take 5 available after one step against 20 after four. The first is worth gamma 5 and the second gamma4 20, which are equal when gamma3 = 0.25, at gamma about 0.6300. Below that value the nearer reward is preferred and above it the larger one, so the optimal policy depends on gamma and gamma is part of the problem statement.
4. Give three reasons for discounting. A reward received now is worth more than the same reward later. Without discounting a task that never terminates has infinite return and every policy is equally good, whereas with gamma below one the sum converges, a unit reward for ever being worth 1/(1-gamma), or 10 at gamma 0.9. And discounting expresses uncertainty about whether the future will arrive at all.
The Reinforcement Learning Framework
5. Why can a purely greedy agent be permanently wrong? Because its estimate of an action can only improve if it takes that action, and it will not take an action its current estimate says is inferior. If the best action happens to pay nothing on its first trial, its estimate stays low for ever and it is never tried again. In the measurement, four runs in ten ended believing a worse action was best, one of them having taken the worst of three actions 498 times out of 500.
6. What does the measurement show about the value of exploring? That both extremes are poor. With no exploration the agent earned 949.7 over 2000 steps and found the best action in only six runs of ten. With continuous exploration it found the best action every time and earned 911.5, because it never used what it knew. Values around 0.05 to 0.10 earned about 1075 and identified the best action reliably.
7. What is reward hacking, and how does the reward hypothesis relate to it? Reward hacking is the agent finding a way to earn the reward without performing the intended task, such as a recommender rewarded for time spent learning to hold attention rather than to be useful. The reward hypothesis, that every goal can be expressed as maximising a single scalar reward, is what makes the problem tractable, and reward hacking is what happens when the scalar chosen is not in fact the goal.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.