Concepts / Greedy and Nongreedy Actions

Greedy and Nongreedy Actions

Exploitation uses the action that currently has the greatest estimated value.

  • Machine Learning

The Choice Behind Every Action

At each time step, an action-selection method must decide what to do next. It can select the action that currently appears best, or it can select another action to learn more about that action's value. These choices are called exploitation and exploration. The tension between them is the exploration-exploitation trade-off.

Action estimatescurrent valuesAction choiceExploitationgreatest expected rewardnowExplorationimproved knowledgeinformchoose current bestchoose another
At a single decision point, how does the selected action commit the agent either to using current knowledge or to gathering information?

Greedy and Nongreedy Choices

A greedy action is the action that currently has the greatest estimated value. Choosing it is exploitation: the agent uses what it currently believes and expects to receive the greatest reward on this step. A nongreedy action is an action that is not currently estimated to be the best. Choosing it is exploration when the purpose is to improve knowledge about that action's value.

Greedy actionhighest current estimateImmediate rewardgreatest expected rewardNongreedy actionnot highest currentestimateAction knowledgeimproved value estimateexploitexplore
How does choosing the action with the highest current estimated value differ from choosing another action to learn more?
Worked example

Reading the current estimates

Suppose an agent currently estimates that Action A has a greater value than Action B.

  1. 1
    Identify the greedy action

    Action A is greedy because it currently has the greatest estimated value.

  2. 2
    Identify exploitation

    Choosing Action A exploits current knowledge and aims for the greatest expected reward on this step.

  3. 3
    Identify exploration

    Choosing Action B is nongreedy. If the purpose is to improve knowledge about Action B's value, that choice is exploration.

Result

The same action-selection situation supports two different purposes: choose Action A to exploit, or choose Action B to explore.

Immediate and Long-Run Rewards

Exploitation is appropriate when the goal is to maximize expected reward on the one current step. However, the action that currently looks best may not truly be the best action. Exploration accepts a lower reward in the short run when it may improve knowledge about another action. If that investigation reveals a better action, the newly identified action can be exploited repeatedly, producing greater total reward over many time steps.

Current stepnongreedy actionNew informationvalue estimate improvesLater stepsbetter action exploitedGreater total rewardpossible long-run resultinvestigateidentify better choicerepeat exploitation
How can an action with lower immediate expected reward lead to greater total reward over many time steps?
Worked example

Comparing two objectives

An agent believes Action A is best right now, but Action B has not been investigated enough to know whether it might be better.

  1. 1
    One-step objective

    If the agent only wants the greatest expected reward on the current step, it chooses the currently best-looking action, Action A.

  2. 2
    Long-run objective

    If the agent values total reward over many steps, it may choose Action B to improve its estimate, even if this creates a lower reward in the short run.

  3. 3
    Possible later benefit

    If investigating Action B reveals that it is better than Action A, the agent can exploit Action B repeatedly on later steps.

Result

The best choice for one immediate reward and the best choice for total reward over many steps can differ.

Uncertainty Changes the Trade-Off

An estimated value is not a guarantee that an action is truly best. The currently highest estimate may be wrong because the agent's knowledge is incomplete. This possibility makes a nongreedy action worth considering: trying it can improve the estimate and reveal information that is not available from repeatedly choosing the current favorite.

Action Ahighest current estimateAction A knowledgealready favoredAction Blower current estimateAction B knowledgecould improve throughexplorationexploitexplore
How can uncertainty in estimated action values make a nongreedy action worth trying even when its current estimate is not the highest?

Common Reasoning Mistakes

  • Common mistake

    Treating the greedy action as certainly the best action

    What it looks like

    The action with the greatest current estimated value is chosen repeatedly as if its estimate could not be wrong.

    Why it fails

    The action that currently looks best may not truly be the best action.

    Do this instead

    Remember that exploration can improve knowledge about a nongreedy action and may reveal a better choice.

  • Common mistake

    Calling every nongreedy choice exploration

    What it looks like

    An agent chooses an action with a lower estimate, but there is no purpose of improving knowledge about that action.

    Why it fails

    Exploration specifically involves choosing a nongreedy action to improve knowledge about its value.

    Do this instead

    Use the term exploration when the nongreedy choice is intended to investigate or improve the value estimate.

  • Common mistake

    Assuming the action with the best immediate reward must produce the best total reward

    What it looks like

    The agent always selects the current favorite because it wants the highest reward on every individual step.

    Why it fails

    Immediate reward and long-run total reward can favor different choices.

    Do this instead

    Separate the one-step objective from the possibility that exploration can lead to greater reward across many later steps.

  • Common mistake

    Claiming that one action can explore and exploit at the same time

    What it looks like

    The agent selects the currently best-looking action and describes that same selection as simultaneously investigating another action.

    Why it fails

    A single action selection cannot both choose the current best option and choose another option to improve its estimate.

    Do this instead

    At each decision point, identify whether the selected action is being used for exploitation or for exploration.

Practice the Decision

EASY

An agent currently estimates that Action A has the greatest value. It chooses Action B because it wants to learn whether Action B may be better over many future steps. Identify the action-selection purpose, explain whether the chosen action is greedy or nongreedy, and state why the choice may still improve total reward.

Hints
  • Compare the chosen action with the action that currently has the greatest estimated value.
  • Ask whether the choice is using current knowledge or improving knowledge.
  • Distinguish the reward on this step from reward accumulated over many steps.

What do you think happens?

If Action A currently has the greatest estimated value and the agent chooses Action B specifically to improve knowledge about B, is the decision exploitation or exploration?

  • Exploitation

  • Exploration

  • Both at the same time

Reveal answer
Answer:

Exploration

Action B is nongreedy because it is not currently estimated to be the best, and choosing it to improve knowledge about its value is exploration. One action selection cannot simultaneously explore and exploit.

Key Takeaways

  1. 1
    Exploitation chooses the greedy action: the action with the greatest current estimated value.
  2. 2
    Exploration chooses a nongreedy action to improve knowledge about its value.
  3. 3
    A single action selection cannot simultaneously exploit the current best-looking action and explore another action.
  4. 4
    Exploitation can maximize expected reward on the current step, while exploration may support greater total reward over many steps.
  5. 5
    Uncertainty matters because the current favorite may not truly be the best action.

At a glance

  • A greedy action has the greatest current estimated value, so choosing it is exploitation.
  • A nongreedy action can be chosen for exploration when the goal is to improve knowledge about its value.
  • Immediate expected reward and long-run total reward can favor different actions.
  • Exploration can be worthwhile when current estimates are uncertain and learning may reveal a better action.
  • At one decision point, the agent must choose between exploiting current knowledge and exploring another action.

Related Topics

Related concepts

More concepts starting with G