Greedy and Epsilon-Greedy Action Selection

Choosing with Incomplete Knowledge

An agent often must choose an action using estimates rather than complete knowledge of what will happen. It can inspect possible actions, consider the rewards and estimated future values associated with the resulting states, and compare the actions. The action with the greatest current estimated value is called the greedy action.

Comparing Estimated Actions

To identify a greedy action, compare the current estimated values of the available actions. The action with the greatest estimate is greedy. This comparison does not require the estimate to be perfect; it only describes which action currently appears best according to the agent's approximate knowledge.

Looking Ahead with Heuristic Search

Heuristic search applies the same general choice idea beyond a single immediate comparison. It begins with an approximate value function and looks ahead from each possible action to possible next states. During that look-ahead, it combines immediate rewards with estimated future values. The resulting backed-up values allow the agent to compare the candidate actions and select the most promising one.

The numbers in the diagram are illustrative rather than a prescribed calculation rule. The important process is the one described by the source: inspect possible actions, look ahead to possible states, back up rewards and estimated values, and use the resulting values to compare the actions.

Temporary Search Results

Conventional heuristic search uses backed-up values to make the current choice. The search calculation can guide the agent toward the most promising action, but the backed-up values are used temporarily rather than being used to update the approximate value function. In this approach, the search result helps with the decision that is happening now.

Learning from Search

Search results can also be retained as information for later decisions. When the backed-up values contribute to improving the value function, later choices can use a changed approximate value function instead of relying only on the original estimates. This creates a distinction between calculating values for one decision and using those calculations to improve future decision-making.

Exploitation and Exploration

Choosing the greedy action is exploitation: the agent uses its current knowledge to seek the best expected one-step reward. Choosing a nongreedy action is exploration: the agent chooses an action that is not currently estimated to be best in order to gather information that may improve later estimates.

The choice is a conflict because one action selection cannot serve both purposes at the same time. Selecting the greedy action uses current knowledge to pursue immediate reward. Selecting a nongreedy action instead creates an opportunity to learn more about that action. Exploration may sacrifice some short-term reward while improving knowledge that can support better choices when many future selections remain.

Reasoning Before Selection

1. Identify the actions currently available.
2. Use the current estimates to identify the action with the greatest estimated value.
3. Recognize that this greatest-estimate action is greedy.
4. Choose the greedy action when the immediate expected reward is the priority.
5. Consider a nongreedy action when gathering information may improve later estimates and future choices.
6. Remember that exploitation and exploration optimize different horizons: immediate reward versus possible long-term improvement.

Common Selection Mistakes

• Treating the greedy action as the action that is guaranteed to be best.

  A greedy action is defined by having the greatest current estimated value. The estimate is the agent's current knowledge, not a guarantee about the outcome.

  Fix: Say that the greedy action appears best according to the current estimates.

• Calling every heuristic-search result a permanent improvement to the value function.

  Conventional heuristic search can use backed-up values temporarily without updating the approximate value function.

  Fix: Ask whether the backed-up values are being used only for the current choice or are being retained to improve future estimates.

• Treating exploration as automatically better than exploitation.

  Exploration may reveal a better action, but it can sacrifice short-term reward. Exploitation and exploration serve different horizons.

  Fix: Describe exploitation as targeting immediate expected reward and exploration as gathering information that may improve later choices.

• Describing greedy action selection and heuristic search as completely unrelated.

  Both use value information to compare possible actions. Heuristic search extends the idea by looking ahead to possible next states and backing up rewards and estimated values.

  Fix: Explain the shared comparison idea and then identify the broader look-ahead performed by heuristic search.

Practice the Trade-off

1. Greedy action selection chooses the action with the greatest current estimated value. It is exploitation because it uses current knowledge to pursue the best expected one-step reward. A nongreedy choice is exploration because it gathers information that may improve later estimates. Heuristic search extends value-based action comparison by looking ahead to possible states and backing up rewards and estimated values. Those backed-up values may be used temporarily for one decision, or they may contribute to improving the value function so that future decisions use changed estimates.