Multi-step reinforcement learning

The experience and the learning objective do not have to come from the same policy. The behavior policy supplies what happened; the target policy determines how that experience contributes to learning.

Programming

One Experience, Two Policies

A reinforcement-learning agent can learn from experience generated by a policy different from the policy it is trying to learn. The policy that generates behavior is called the behavior policy. The policy being learned is called the target policy. This separation is the central idea of off-policy learning.

How can experience generated by one policy be used to learn a different policy?

Key point

Following the Sampled Path

The n-step tree backup algorithm is an off-policy method. It follows an observed action through its sampled next state, preserving the part of the experience that actually occurred. After reaching that next state, the backup can expand over possible actions instead of waiting for every one of them to be sampled.

What happens as the backup follows sampled transitions for some steps and then expands all possible actions?

Worked example

A short backup trace

Suppose the behavior policy samples an action from state s0 and the environment produces state s1. At s1, the target policy assigns probabilities to three possible actions.

1
Step 1: retain the observation
The backup uses the observed action from s0 and the sampled transition to s1. This is the sample-transition part of the tree backup.
2
Step 2: expand at s1
Rather than using only the action that the behavior policy happened to sample next, the backup considers all actions available at s1.
3
Step 3: weight the branches
Each action branch contributes according to the probability assigned to that action by the target policy.

Result

The backup is neither a purely sampled path nor a full expansion from the beginning. It combines an observed path segment with target-policy-weighted action branches.

Adding Unsampled Actions

A sampled transition tells the algorithm what happened for one action. It does not, by itself, tell the algorithm to ignore the other actions. In a full backup, the other actions enter through their possible contributions, weighted by the probabilities that the target policy assigns to them.

How do actions that were not sampled still contribute to the update?

Stopping the Backup

The n-step tree backup does not expand the tree indefinitely. It stops when the chosen n-step backup depth has been reached. If a terminal state is reached before that depth, there is no later state or action branch to continue backing up, so the remaining part of the return ends there.

What condition causes the backup process to stop, and how does reaching a terminal state change the remaining return?

Three Research Phases

Research on teams of reinforcement-learning agents developed through three broad phases. The phases are best understood as a widening sequence of questions: first, how learning automata could learn in bandit, team, and game problems; second, how learning could use context and connect with artificial neural networks; and third, how learning rules could reflect findings about the brain.

How did research on teams of reinforcement-learning agents develop across three phases?

First phase: research associated with M. L. Tsetlin and later stochastic learning automata studied bandit, team, and game problems.
Second phase: researchers extended learning automata to associative or contextual learning and connected them with single-layer and multi-layer artificial neural networks.
Third phase: research paid greater attention to synaptic plasticity and constraints suggested by neuroscience.

From Non-Associative to Contextual

Approach	What learning uses	Historical role
Non-associative learning automata	Learning behavior in bandit, team, and game problems without an explicitly associative context	Foundation of the first research phase
Associative or contextual reinforcement learning	Context together with reinforcement	Second phase; connected learning automata with artificial neural networks
Associative reward-penalty algorithm	Associative reinforcement learning in learning units and teams	Strengthened connections among learning automata, pattern classification, associative reinforcement learning, and artificial neural networks

The distinction is whether learning is explicitly conditioned on contextual information.

What is the difference between learning from an action's reward alone and learning conditioned on contextual states?

The word non-associative marks the boundary of the first phase: those studies investigated learning behavior but did not address the contextual bandit case. Associative reinforcement learning added an explicit context, so the learner could connect what it perceived with the action and the reinforcement received.

The associative reward-penalty algorithm, introduced by Barto and Anandan in 1985, was important because it connected several lines of work: stochastic learning automata, pattern classification, associative reinforcement learning, and artificial neural networks. Teams of these units were connected into multi-layer neural networks and were reported to learn nonlinear functions, including XOR, while receiving a globally broadcast reinforcement signal. Later mathematical analysis showed that a special case of A R - P is a REINFORCE algorithm.

Neuroscience and the Third Phase

The third phase was influenced by growing neuroscience support for the possibility that this kind of learning occurs in the brain. Researchers therefore paid more attention to synaptic plasticity and to biological constraints, rather than treating the learning rule only as an abstract computational procedure.

STDP
Dopamine
Reward-modulated STDP
Synaptic plasticity
Other biological constraints suggested by neuroscience

Mistakes to Avoid

Common mistake
Treating the behavior policy and target policy as the same thing.
What it looks like
Assuming that the policy that generated an observed action must also determine every branch in the backup.
Why it fails
Off-policy learning separates the policy generating experience from the policy being learned.
Do this instead
Use the behavior policy to identify the observed experience and the target policy to determine the learning update and branch weights.
Common mistake
Following only the sampled action at every step.
What it looks like
Ignoring all actions that were not selected in the observed trajectory.
Why it fails
The n-step tree backup combines sampled transitions with full backups over possible actions.
Do this instead
Follow the observed transition where sampling is used, then include alternative actions through the full backup.
Common mistake
Giving every alternative action equal influence.
What it looks like
Treating all branches in a full backup as equally important.
Why it fails
Target-policy probabilities determine the weights of state-to-action branches.
Do this instead
Weight each branch according to the probability assigned by the target policy.
Common mistake
Calling the first phase associative simply because it involved learning.
What it looks like
Describing every learning automaton study as contextual reinforcement learning.
Why it fails
The first phase did not address the contextual bandit case.
Do this instead
Reserve associative or contextual learning for approaches that explicitly use context.
Common mistake
Reducing the importance of A R - P to a single learning unit.
What it looks like
Missing its connection to neural networks and later REINFORCE analysis.
Why it fails
Its historical importance came from linking several research traditions and supporting teams of units in multi-layer networks.
Do this instead
Remember both its associative learning role and its connections to neural networks and REINFORCE.

Check Your Understanding

MEDIUM

An agent collects a transition using one policy, but the learning algorithm is updating a different target policy. Explain what information comes from the behavior policy, what information comes from the target policy, and why the backup includes actions that were not sampled.

Hints

Start by separating experience generation from policy evaluation or improvement.
Identify the observed transition as the sampled part of the backup.
Explain that alternative actions enter through a full backup weighted by target-policy probabilities.

Your attempt (not saved)

EASY

Place these developments in order and state what each added: non-associative learning automata, associative or contextual reinforcement learning, and neuroscience-informed learning rules.