Introduction

The first article briefly introduced exploration and exploitation through a choice of lunch.

• Exploitation: Visit the favorite restaurant that has been best so far.
• Exploration: Try a new restaurant we do not know well yet.

We also used an $\epsilon$-greedy policy in SARSA and Q-Learning, but did not examine in detail why exploration is necessary.

Choosing the action with the largest Q-value seems reasonable. The problem is that a Q-value during training is not the true action value. It is an estimate constructed from the experience collected so far.

An action that happened to produce a high reward in the first two trials can appear to be the best. If the agent keeps choosing only the greedy action, it may never try the alternatives and may never discover that a better choice exists.

Exploration gives up part of the immediate reward to purchase information. Because that information can lead to better decisions later, it may be valuable in the long run.

We begin with the multi-armed bandit, the simplest environment, which has no state transitions.

The Multi-Armed Bandit

The bandit takes its name from a slot machine with several handles. Selecting an action, or arm, produces one reward from an associated probability distribution.

$$\text{Bandit} = \langle \mathcal{A}, \mathcal{R} \rangle$$

• $\mathcal{A}$: the set of available actions
• $\mathcal{R}^a$: the unknown reward distribution produced by action $a$

Unlike an MDP, a bandit has no next state. We can think of the current state as remaining unchanged at every step. The agent repeatedly chooses one action and observes one reward.

The true value of action $a$ is its mean reward.

$$Q(a) = \mathbb{E}[R \mid A=a]$$

Because the reward distribution is unknown, we estimate the value with samples obtained by actually choosing the action.

$$\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{i=1}^{N_t(a)} R_i(a)$$

$N_t(a)$ is the number of times action $a$ has been selected by time $t$.

In the figure, A has an estimated value of $4.8$, while B has $4.2$. A greedy choice selects A. But C has been tried only once, so its value is highly uncertain. Its true mean could be $8$.

Exploration means trying C to reduce this uncertainty.

When Greedy Gets Trapped by a First Impression

Suppose the true mean rewards of two actions are

$$Q(A)=5, \qquad Q(B)=7.$$

Now suppose the first samples happen to be

$$R(A)=8, \qquad R(B)=2.$$

The current estimates are $8$ for A and $2$ for B, so a greedy policy keeps selecting A. Repeated samples bring A's estimate closer to its true mean of $5$, but B is never selected again and remains at $2$.

The agent never discovers that B is actually better. A greedy action is optimal only under the current estimate; it is not guaranteed to be optimal under the still-unknown reward distributions.

Regret Is the Cost of a Missed Opportunity

In a bandit problem, we can compare exploration methods by cumulative reward. The same idea is often expressed through regret.

The value of the best action is

$$V_* = \max_{a \in \mathcal{A}} Q(a).$$

The expected reward missed by choosing $A_t$ at time $t$ can be viewed as instantaneous regret.

$$\ell_t = V_* - Q(A_t)$$

Total regret is its sum over time.

$$L_T = \sum_{t=1}^{T} \ell_t$$

If we knew the best action, regret would be zero. In reality, we do not know which action is best. Choosing a low-reward action for exploration creates regret immediately. But if we never explore, we may remain trapped in a bad action and accumulate regret for a long time.

A good exploration algorithm balances the cost of acquiring information against the cost of repeatedly making the wrong choice.

ε-Greedy: Occasionally Try Something at Random

$\epsilon$-greedy is one of the simplest and most widely used exploration methods.

• With probability $1-\epsilon$, select the current greedy action.
• With probability $\epsilon$, select one of all actions at random.

If there are $m$ actions, the final probability of choosing the greedy action is

$$1-\epsilon+\frac{\epsilon}{m},$$

while the probability of each other action is

$$\frac{\epsilon}{m}.$$

This is because the random choice can select the greedy action again.

For example, with four actions and $\epsilon=0.1$,

$$P(\text{greedy}) = 0.9+\frac{0.1}{4} = 0.925.$$

Each other action has probability

$$\frac{0.1}{4}=0.025.$$

The current best action is therefore chosen $92.5\%$ of the time, and each of the remaining three actions is selected with probability $2.5\%$.

Should ε Remain Constant?

With a fixed $\epsilon$, the agent continues to choose random actions at the same rate even after training has run for a long time. Exploration never stops, even when every action is already well understood.

We can instead use a decaying $\epsilon$: explore broadly with a large value at the beginning and gradually reduce it.

$$\epsilon_1 > \epsilon_2 > \cdots$$

If it decays too quickly, the agent may settle on the wrong action before exploring enough. If it decays too slowly, it continues unnecessary exploration long after finding a good action.

GLIE, a condition that often appears in convergence results for tabular control, requires two properties together.

• Every state-action pair is explored infinitely often.
• In the limit, the policy becomes greedy.

It is difficult to apply an asymptotic condition literally to finite training, but it gives us the right direction: provide enough opportunities to explore, while eventually choosing good actions more often.

Optimistic Initialization

Another approach is to initialize Q-values higher than their likely true values.

Suppose the true mean of every action is expected to lie roughly between $0$ and $5$, but we begin with

$$\hat{Q}_0(a)=10.$$

When one action produces reward $3$, that action's estimate falls. Unselected actions remain at $10$, so even a greedy policy naturally tries them next.

The optimistic initial estimate says, “this action might be extremely good,” and thereby encourages exploration.

It is easy to implement, but it has limitations.

• We must decide how optimistic the initial value should be.
• The exploration effect weakens after every action has been tried once.
• If the environment changes later, the initial optimism does not return.

UCB: Value an Action Because We Do Not Know It Well

Random exploration in $\epsilon$-greedy does not distinguish a bad action tried many times from an action tried only a few times. During an exploration step, both are random candidates.

Upper Confidence Bound, or UCB, adds an uncertainty bonus to each action's estimate.

$$A_t = \arg\max_a \left[ \hat{Q}_t(a) + c \sqrt{ \frac{\ln t}{N_t(a)} } \right]$$

The first term represents exploitation.

$$\hat{Q}_t(a)$$

The second is the exploration bonus.

$$c \sqrt{ \frac{\ln t}{N_t(a)} }$$

• If $N_t(a)$ is small, the bonus is large.
• As an action is chosen more often and $N_t(a)$ grows, the bonus shrinks.
• A larger $c$ places more importance on uncertainty.

Consider the following two actions.

A has the higher mean estimate, but B has rarely been tried and therefore has a large bonus. UCB selects B. Once B is observed, its uncertainty and bonus decrease.

This principle is called optimism in the face of uncertainty. We optimistically account for the possibility that an unknown choice may be good, then automatically reduce that optimism as experience accumulates.

Returning from Bandits to MDPs

A bandit has no state transitions, but the same exploration principles extend to MDPs.

In $\epsilon$-greedy Q-Learning, the agent uses the Q-values in each state $s$ and occasionally tries a random action.

$$\pi(a \mid s) = \begin{cases} 1-\epsilon+\epsilon/m, & a=\arg\max_{a'}Q(s,a') \\ \epsilon/m, & \text{otherwise} \end{cases}$$

A UCB-like method can choose actions by adding a visit-count or uncertainty bonus to each state-action value.

Exploration in an MDP is harder than in a bandit, however. An action changes the immediate reward, the states the agent will visit, and the data it will collect later. In some environments, the agent must open a door before it can explore the new states behind it.

This is why sparse-reward environments, where random actions are not enough, use more structured methods such as count-based exploration, curiosity, and intrinsic rewards. We will revisit these ideas when we discuss practical reinforcement learning.

More Exploration Is Not Always Better

Exploration is not free.

• A bad action can be dangerous in medical or robotic environments.
• In a recommendation service, users may leave while the system shows poor items.
• In offline RL, the agent cannot actually try new actions.

“Sufficient exploration” therefore does not mean choosing as many random actions as possible. We must consider both the value of information that reduces uncertainty and the cost of the trial itself.

At an introductory stage, the following questions are useful checks.

1. Is every action being experienced at least occasionally?
2. Is $\epsilon$ becoming small too quickly?
3. Is exploration noise still active during evaluation?
4. Are there dangerous actions that the training environment cannot permit?
5. Has a change in the rewards made the old Q-values stale?

What to Remember

The central idea of this article is

Exploration trades part of the immediate reward for information that can reveal better actions in the long run.

More specifically:

1. A greedy policy can remain trapped forever by a wrong early estimate.
2. $\epsilon$-greedy usually chooses the greedy action and explores randomly with a small probability.
3. A fixed $\epsilon$ keeps exploring even after training is complete.
4. Optimistic initialization encourages unvisited actions through high initial values.
5. UCB adds an uncertainty bonus to the estimated value.
6. Exploration is more difficult in an MDP because an action also changes the states the agent will visit later.

The next article returns to the temporal length of the update target. TD(0) looks ahead one step, while Monte Carlo looks all the way to a terminal state. We will examine the 2-step and 3-step returns between them, TD($\lambda$), which blends every length, and eligibility traces.

References

• David Silver, Lecture 5: Model-Free Control
• David Silver, Lecture 9: Exploration and Exploitation
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition