Epsilon-Greedy Action Selection

On the 10-armed testbed, UCB generally performs better than epsilon-greedy action selection.

Programming

The Choice Behind Every Action

Whenever an agent chooses an action, it faces a tension. It can use its current estimates to select the action that appears best, or it can choose a different action to gather information. The first choice is exploitation. The second is exploration. Epsilon-greedy action selection is understood through this decision between using current knowledge and learning more.

Tracing a Greedy Decision

Definition

A greedy action is an action with the greatest current estimated value. Choosing a greedy action is exploitation: the agent relies on what it currently believes in order to seek the best expected one-step reward.

Worked example

Comparing current estimates

An agent has current estimated values for three actions: action A, action B, and action C. Action B has the greatest estimate.

1
Compare
The agent compares the current estimated values of the available actions.
2
Identify
The action with the greatest current estimated value is action B, so action B is greedy.
3
Interpret
Choosing action B is exploitation because the agent is using its current knowledge to pursue the best expected immediate reward.

Result

Action B is the greedy action, and choosing it is exploitation.

How does an agent use epsilon to decide whether to choose the greedy action or a nongreedy action?

The diagram shows the conceptual role of the epsilon-greedy choice: the agent begins with its current estimates, then selects either the greedy action for exploitation or a nongreedy action for exploration. The greedy action is defined by the estimates; the nongreedy choice is valuable because it can provide information that changes later estimates.

Immediate Reward versus Future Knowledge

Exploitation is aimed at the best expected one-step reward. If the current estimates are accurate enough, selecting the greedy action is the strongest immediate choice. Exploration can appear worse in the short term because it selects a nongreedy action instead of the action that currently looks best. However, exploration may reveal that another action is better than its current estimate suggests. When many future selections remain, that improved knowledge can produce greater total reward.

Why can exploiting the current best estimate maximize immediate reward while exploring can produce greater long-term reward?

Key point

Neither exploration nor exploitation is always the better choice. They optimize different horizons: exploitation pursues immediate reward, while exploration may improve the choices available later.

UCB as a Comparison Point

The 10-armed testbed provides a compact way to compare action-selection strategies. In this setting, UCB generally performs better than epsilon-greedy action selection. The result does not mean that UCB eliminates exploration. UCB still investigates actions whose values are uncertain. Its advantage in the testbed is that this approach is generally more effective than epsilon-greedy selection there.

How do the action-selection strategies differ across trials, and why does UCB generally achieve better average reward than epsilon-greedy?

UCB's Startup and Limitations

UCB has a special startup period. During the initial k steps, it selects randomly among actions that have not yet been tried. This behavior gives each untried action an initial opportunity to be investigated. After that startup period, the broader UCB approach continues to consider uncertainty rather than simply removing exploration.

What happens next when UCB evaluates actions that have not yet been tried, and why does it select each untried action?

UCB also becomes harder to use when the problem changes. In a nonstationary problem, the underlying probability distributions change over time. Evidence collected earlier may then be less useful for judging what an action is like now. UCB's accumulated estimates can therefore become misleading when past behavior no longer represents the current distribution.

What changes when the reward distributions move over time, and why can UCB's reliance on accumulated estimates become misleading?

A further limitation appears beyond bandits. Large state spaces make UCB difficult to extend to general reinforcement learning, especially when function approximation is used. The source identifies these advanced settings as a major difficulty and notes that there is currently no known practical way to use the idea of UCB action selection there.

Common Reasoning Errors

Common mistake
Treating the greedy action as the action that is guaranteed to produce the highest reward.
What it looks like
An action is greedy because it has the greatest current estimated value.
Why it fails
Greedy describes the present estimate, not a guarantee about the actual reward.
Do this instead
Describe the greedy action as the action currently estimated to be best.
Common mistake
Assuming that exploitation is always the correct choice.
What it looks like
The agent always selects the action with the greatest current estimate.
Why it fails
Exploration can reveal a better action and may produce greater total reward when future selections remain.
Do this instead
Separate immediate reward from longer-term information and reward.
Common mistake
Assuming that UCB's better testbed performance means it solves general reinforcement learning.
What it looks like
UCB performs well on the 10-armed testbed, so it should be easy to use with large state spaces.
Why it fails
Large state spaces and function approximation make UCB difficult to extend beyond bandits.
Do this instead
Treat the testbed result as a setting-specific comparison, not a universal guarantee.
Common mistake
Forgetting UCB's startup behavior.
What it looks like
Describing UCB as immediately ranking every action using a mature history.
Why it fails
During the initial k steps, UCB selects randomly among actions that have not yet been tried.
Do this instead
Account for the special startup period before discussing later uncertainty-based selection.
Common mistake
Assuming accumulated evidence is always current evidence.
What it looks like
Using old action observations as though the action's probability distribution could not have changed.
Why it fails
In nonstationary problems, the underlying probability distributions change over time.
Do this instead
Ask whether earlier evidence still represents the current action-reward behavior.

Practice the Decision

MEDIUM

An agent has one action with the greatest current estimated value. Explain what it means to choose that action, what it means to choose a nongreedy action instead, and why the nongreedy choice might be useful when future selections remain. Then explain one reason not to assume that UCB will transfer directly to a large-state-space reinforcement-learning problem.

Hints

Use the terms greedy action, exploitation, and exploration.
Distinguish immediate reward from improved knowledge for later choices.
Mention changing probability distributions or the difficulty of function approximation.

Your attempt (not saved)

What do you think happens?

During UCB's initial k steps, what happens if several actions have not yet been tried?

UCB permanently ignores the untried actions.
UCB selects randomly among the actions that have not yet been tried.
UCB always selects the action with the greatest current estimated value.

Reveal answer

Answer:

UCB selects randomly among the actions that have not yet been tried.

The initial k steps are a special startup period in which UCB gives untried actions an opportunity to be selected.

What to Remember

1
A greedy action has the greatest current estimated value.
2
Choosing the greedy action is exploitation and targets the best expected one-step reward.
3
Choosing a nongreedy action is exploration and can improve later decisions by providing information.
4
On the 10-armed testbed, UCB generally performs better than epsilon-greedy action selection, while still investigating uncertain actions.
5
UCB has a special startup period involving random selection among untried actions, and its use becomes difficult with changing distributions, large state spaces, and function approximation.

At a glance

The greedy action is the action with the greatest current estimated value.
Exploitation uses current knowledge for immediate reward, while exploration gathers information that may improve long-term reward.
UCB generally outperforms epsilon-greedy selection on the 10-armed testbed, but it begins by selecting randomly among untried actions during its initial k steps.
Changing probability distributions can make accumulated estimates misleading.
Large state spaces and function approximation make UCB difficult to apply practically in general reinforcement learning.

Related concepts

More concepts starting with E