Balancing Exploration and Exploitation with Upper-Confidence-Bound Action Selection

The Choice Between Discovery and Reward

A reinforcement learning agent often must choose an action before it knows which action is best. It can exploit an action that has already produced reward, or it can explore an unfamiliar action that might reveal a better opportunity. These competing needs create the exploration-exploitation dilemma.

Neither behavior is sufficient by itself. Exclusive exploration keeps spending decisions on discovery instead of using actions that appear effective. Exclusive exploitation repeatedly uses the current favorite and may never check whether another action is better. An agent therefore needs discovery to gain information and reward-seeking behavior to make use of that information.

How UCB Builds an Action Score

Upper Confidence Bound action selection addresses the weakness of choosing only the action with the highest current estimated value. A high estimate may belong to an action whose value is still uncertain. UCB considers an upper confidence bound for each action and favors the action with the largest combined quantity.

The square-root term is important because it prevents the agent from treating an uncertain estimate as if it were fully reliable. An action can therefore be selected because its estimated value is high, because its uncertainty bonus is high, or because the combination is highest among the available actions.

Tracing Selection Counts Through Time

The uncertainty term changes as selections are made. For action a, the count N_t(a) records how often that action has been selected by time t. When action a is selected, N_t(a) increases. Because this count is in the denominator of the square-root term, the uncertainty estimate for that action decreases.

When a different action is selected, time t increases but N_t(a) does not. The numerator of the uncertainty term increases while action a's denominator remains unchanged, so action a's uncertainty estimate increases. In this way, an action that is skipped becomes more attractive to reconsider, while an action that is repeatedly selected becomes less uncertain.

The Role of the Exploration Parameter

The parameter c is greater than zero. It multiplies the uncertainty term, so it controls how strongly uncertainty affects the quantity being maximized. It also controls the degree of exploration and determines the confidence level of the upper bound.

Why Untried Actions Are Eligible

If N_t(a) equals zero, action a has not been selected before time t. The uncertainty expression would not have a usable previous selection count in its denominator. UCB handles this case by considering the action a maximizing action, which ensures that an untried action is eligible for selection.

Repeated Trials in Uncertain Tasks

A single observed reward does not provide dependable information about an action when the task is stochastic. Repeated selections supply experience about that action. As the agent gathers more information, its estimate can become more reliable, while the uncertainty term reflects how much uncertainty remains.

This is why an agent's preference should develop progressively. Early exploration supplies experience. Later choices can give greater weight to actions that appear effective, while continued exploration remains important whenever the agent still lacks reliable information.

Mistakes in UCB Reasoning

• Choosing only the action with the highest estimated value.

  UCB is designed to consider the uncertainty bonus as well as the estimated value.

  Fix: Compare the combined upper confidence quantities rather than the estimated values alone.

• Assuming uncertainty always decreases over time.

  When another action is selected, time increases while the skipped action's selection count stays unchanged, so its uncertainty estimate increases.

  Fix: Track both time and the action's own selection count.

• Treating c as an action value.

  c controls the influence of the uncertainty term and the confidence level of the upper bound.

  Fix: Keep the estimated value and the exploration-controlling parameter conceptually separate.

• Ignoring an action whose selection count is zero.

  UCB treats an action with zero previous selections as a maximizing action so that it remains eligible for selection.

  Fix: Handle the zero-count case explicitly.

• Using only exploration or only exploitation.

  Exclusive exploration fails to use effective actions, while exclusive exploitation can miss a better action.

  Fix: Allow exploration to supply information and exploitation to use actions that appear effective.

Practice: Predict the Next Preference

What to Remember

1. UCB combines an estimated action value with an uncertainty bonus and selects the action with the largest combined upper confidence quantity.
2. The square-root term represents uncertainty or variance in the action-value estimate.
3. Selecting an action increases its selection count and decreases its uncertainty estimate; selecting other actions increases the uncertainty estimate of an action that was skipped.
4. The parameter c is greater than zero and controls how strongly uncertainty affects the score, along with the exploration degree and confidence level.
5. An action with zero previous selections is treated as a maximizing action so that it remains eligible for discovery.
6. Exploration discovers action effectiveness, while exploitation uses actions already found to be effective; reinforcement learning needs both.