Greedy and ε-Greedy Action Selection

The Immediate-Reward Trap

Suppose an agent has ten possible actions and must choose one. The natural strategy is to select the action with the highest estimated value. That strategy is called greedy action selection. It has an immediate advantage: the agent uses its current knowledge to pursue the best expected reward for the next step. However, an early reward can be misleading. If the agent treats an unlucky early observation as strong evidence, it may repeatedly choose the wrong action and stop collecting evidence about better actions.

Greedy Actions and Current Estimates

The 10-Armed Testbed

The 10-armed testbed is not one single bandit problem. It is a collection of 2000 independently generated problems. Each problem has ten possible actions. Every action has a true action value, written as q∗(a). These true values are selected from a normal distribution with mean 0 and variance 1. When an action is chosen, its reward is random: the reward distribution has a mean equal to that action's true value and variance 1.

A method interacts with one problem for 1000 steps. The experiment is repeated across all 2000 problems, and the results are averaged. Averaging is important because one run can be strongly affected by chance rewards. The resulting curves describe average behavior across many different tasks rather than the outcome of one unusually lucky or unlucky problem.

Updating Estimates by Sample Average

The compared methods estimate each action's value with the sample-average technique. For a particular action, the learner collects the rewards observed after selecting that action and averages those observations. That average becomes the current estimate used by the action-selection rule.

Why Pure Greed Fails

The greedy method always selects the action with the highest current estimate. Its first results can therefore look promising because it immediately exploits what it currently believes is best. The problem is that an early sample may be disappointing even when the action is actually optimal, or unusually rewarding even when another action is better. Once a misleading estimate becomes the highest estimate, a purely greedy method may keep returning to that action and fail to revisit actions that received disappointing early samples.

In the reported comparison, the greedy method's average reward levels off at about 1 per step, while the best possible average reward on this testbed is about 1.55. The greedy method found the optimal action in only approximately one-third of the problems. These results show why fast initial improvement does not guarantee strong long-run behavior.

Adding ε-Greedy Exploration

An ε-greedy method separates action selection into two possibilities. With probability 1 − ε, it selects the action with the highest current estimated value. With probability ε, it selects a random action. The random choice is not intended to maximize the immediate reward. Its purpose is to give the learner opportunities to collect evidence about actions that may currently be undervalued.

Choosing the greedy action is exploitation. Choosing a nongreedy action is exploration. Exploitation uses current knowledge to pursue the best expected one-step reward. Exploration may produce a lower immediate reward, but it can reveal a better action and improve later choices when many future selections remain.

Comparing the Three Methods

The comparison demonstrates a timing trade-off rather than a universal winner at every moment. More exploration can help the learner discover the optimal action earlier. Less exploration leaves more selections available for exploiting current estimates and can produce better eventual performance in the reported comparison. The best interpretation of ε is therefore about the balance between learning speed and the cost of exploratory selections.

Mistakes in Reasoning

• Assuming that the action with the highest estimate is always the true best action.

  Estimates are based on observed rewards, and early rewards can be misleading.

  Fix: Recognize that ε-greedy exploration creates opportunities to gather more evidence about actions that currently look worse.

• Calling every random action a mistake.

  That random selection is the exploration part of the method, not an accidental failure.

  Fix: Distinguish immediate reward seeking from information gathering.

• Assuming that ε = 0.1 must outperform ε = 0.01 at every stage.

  The source reports that ε = 0.01 eventually outperforms ε = 0.1 on both reward and optimal-action measures.

  Fix: Separate early learning speed from long-run performance.

• Treating the testbed results as the behavior of one single bandit problem.

  The testbed contains 2000 independently generated problems, each with ten actions.

  Fix: Interpret the reported curves as averages across many tasks and many chance outcomes.

Reasoning Practice

Key Takeaways

1. A greedy action has the greatest current estimated value, and selecting it is exploitation.
2. Exploration selects a nongreedy action to gather evidence that may improve future decisions.
3. The 10-armed testbed averages results from 2000 independent ten-action problems, each run for 1000 interaction steps.
4. All three compared methods use sample averages to estimate action values; they differ mainly in whether and how often they explore.
5. Greedy selection can look good early but become trapped by misleading rewards, while ε = 0.1 usually discovers the optimal action earlier and ε = 0.01 eventually performs better in the reported comparison.