Nonstationary k-armed Bandit Task

If the task is not always the same, an action that worked well a moment ago may no longer be the best choice.

Programming

A Moving Target

Suppose a learner repeatedly chooses among several actions and receives an immediate reward after each choice. If the task is not always the same, an action that worked well a moment ago may no longer be the best choice. The learner is facing a moving target: the true action values can change randomly from step to step.

How do changing true action values make an old estimate misleading?

Associative Search

Associative search combines two jobs. First, the learner must discover which actions tend to produce good outcomes. Second, the learner must connect those actions to the situations in which they work. The connection is learned through trial and error rather than being supplied in advance.

A situation clue changes what the learner can remember and use. Without a clue, rewards from different tasks may look as though they came from one undifferentiated changing task. With a clue, the learner can distinguish the current situation and use experience from that situation when it appears again.

How does a situation clue map the learner to an action that has worked in that situation?

Worked example

Separating Two Situations

Imagine that one bandit task is signaled by a red clue and another is signaled by a green clue. The clues identify the current situation but do not reveal the action values.

1
Without clues
The learner receives outcomes from both tasks but has no information identifying which task is active. The observations therefore look like evidence from one changing task.
2
With clues
The learner can keep the red-situation experience conceptually separate from the green-situation experience and connect each recognized situation with an action that has worked there.
3
What the clue does not do
The clue identifies the situation; it does not reveal which action has the highest value. That action still has to be discovered through trial and error.

Result

The clue makes it possible to learn a situation-dependent policy rather than treating every changing reward as coming from one undifferentiated task.

From Feedback to Choice

The learning cycle is feedback-driven. The learner observes the current situation, selects an action, receives an immediate reward, and uses that outcome to improve its action-value information for future choices. When a situation clue is available, the relevant experience is tied to that situation instead of being pooled with every other situation.

How does immediate reward feedback influence later action choices?

Three Learning Problems

Problem type	Situation information	Effect of an action	Main learning requirement
Basic k-armed bandit	No distinguishing situation clue in the described task	Affects only the immediate reward	Discover which action currently gives better rewards
Associative search	A clue identifies the current situation	Affects only the immediate reward in the described version	Discover good actions and associate them with the situations where they work
Full reinforcement learning	Situations are part of the problem	Actions also determine the next situation	Learn action choices while accounting for how actions affect later situations and consequences

The distinctions are based on whether the learner conditions choices on situations and whether actions influence what situation comes next.

Associative search sits between the other two cases. It goes beyond a basic k-armed bandit because the learner must condition its action on the current situation. It remains simpler than full reinforcement learning because, in the version described here, an action affects only the immediate reward and does not also determine the next situation.

What differs among a bandit with no situations, associative search with situation-action mappings, and full reinforcement learning?

Why Fast Change Hurts

A nonstationary method is not automatically effective at every rate of change. If the true action values change rapidly, an estimate based on earlier feedback can become misleading before the learner has enough time to use it. The learner is then trying to learn from evidence about a target that has already moved.

Worked example

An Estimate That Ages Quickly

Consider a learner that has repeatedly found Action A useful. The true action values then change rapidly, and Action B becomes better.

1
Past experience
The learner's experience supports Action A because that action worked well earlier.
2
The task changes
The true action values change, so Action A is no longer necessarily the best choice.
3
The old estimate misleads
If the learner relies too heavily on earlier observations, it may continue favoring Action A even though the current situation favors another action.

Result

Rapid nonstationarity makes learning difficult because useful past evidence becomes outdated quickly.

Common mistake
Assuming that a situation clue reveals the best action.
What it looks like
Treating a red clue as if it directly announced which arm has the highest value.
Why it fails
The clue identifies the current situation but does not reveal the action values.
Do this instead
Use the clue to select the relevant situation-specific experience, then continue discovering effective actions through trial and error.
Common mistake
Treating associative search as an ordinary stationary bandit.
What it looks like
Keeping one undifferentiated view of action quality even when different situations are signaled.
Why it fails
The learner should connect actions with the situations where they work.
Do this instead
Condition the action choice on the recognized situation.
Common mistake
Calling every changing bandit problem full reinforcement learning.
What it looks like
Assuming that changing rewards alone mean actions control future situations.
Why it fails
In the described associative version, actions affect only immediate rewards and not the next situation.
Do this instead
Reserve the full reinforcement learning comparison for problems in which actions also determine the next situation.
Common mistake
Assuming that handling nonstationarity guarantees good performance under rapid change.
What it looks like
Expecting a method designed for changing values to remain accurate when the values change extremely quickly.
Why it fails
Rapid change can make learned estimates outdated before they are useful.
Do this instead
Treat the rate of change as a separate difficulty from identifying the current situation.

Check Your Model

MEDIUM

A learner receives a distinctive clue for each currently active bandit task. The clue identifies the task, but the action values can still change rapidly. Explain what problem the clue solves, what problem remains, and why this task is associative search rather than full reinforcement learning.

Hints

Separate identifying the current situation from estimating action values.
Ask whether an action changes only the immediate reward or also the next situation.
Mention the role of trial and error in learning the situation-action association.

Your attempt (not saved)

What do you think happens?

If two different bandit tasks produce changing rewards but no clue identifies which task is active, should the learner treat their observations as separate situation-specific experiences?

Yes, because the learner can always infer the task from the reward
No, the observations look like one undifferentiated changing task
Yes, because changing rewards automatically identify the situation

Reveal answer

Answer:

No, the observations look like one undifferentiated changing task.

Without a distinguishing clue, the learner has no information that separates the tasks. With a clue, it can associate experience with the recognized situation.

Key Takeaways

1
Associative search requires discovering effective actions and linking them to the situations where they work.
2
A distinguishing clue lets the learner separate experience from different bandit tasks and learn a situation-dependent policy.
3
The described task remains bandit-like because actions affect only immediate rewards, unlike full reinforcement learning where actions also determine the next situation.
4
Rapid changes in true action values can make earlier estimates misleading.
5
A situation clue addresses task identification; it does not by itself solve rapid nonstationarity.

At a glance

Associative search combines trial-and-error action discovery with situation-action association.
Situation clues prevent experience from different tasks from being treated as one undifferentiated changing task.
Associative search is more structured than a basic k-armed bandit but simpler than full reinforcement learning.
Rapidly changing action values make old estimates unreliable, even when a learner is designed for nonstationary tasks.

Related concepts

Full reinforcement learning

More concepts starting with N