Optimism in the Face of Uncertainty: UCB Methods

While simple exploration methods like $\epsilon$-greedy ensure that all actions are eventually tried, they explore randomly without considering how much is known about each action. Randomly stumbling upon good strategies can be inefficient for complex problems. We need smarter ways to direct exploration towards promising but uncertain options. The principle of "optimism in the face of uncertainty" provides a formal approach: act as if everything is as good as plausibly possible given the current knowledge. Upper Confidence Bound (UCB) algorithms embody this principle.

The Multi-Armed Bandit Analogy

UCB methods originated in the simpler setting of multi-armed bandits (MABs). Imagine facing several slot machines ("arms"), each providing a reward drawn from an unknown probability distribution. Your goal is to maximize your total reward over a sequence of pulls. Should you keep pulling the arm that has given the best average reward so far (exploit), or try other arms that might be better but haven't been explored enough (explore)?

UCB provides a criterion for selecting an arm $a$ at each timestep $t$. It relies on two components:

1. Estimated Value ($Q_t(a)$): The average reward received from arm $a$ up to time $t$. This represents the current exploitation value.
2. Uncertainty Bonus: A term that quantifies how uncertain we are about the true value of arm $a$. This term is higher for arms that have been pulled fewer times.

A popular UCB algorithm, UCB1, selects the action that maximizes the sum of these two terms:

$$A_t = \underset{a}{\mathrm{argmax}} \left[ Q_t(a) + c \sqrt{\frac{\ln N_t}{N_t(a)}} \right]$$

Where:

• $A_t$ is the action selected at time $t$.
• $Q_t(a)$ is the estimated value (average reward) of action $a$ after $t$ rounds.
• $N_t$ is the total number of pulls across all arms up to time $t$.
• $N_t(a)$ is the number of times action $a$ has been pulled up to time $t$.
• $c$ is a constant ($c > 0$) that controls the degree of exploration. Higher $c$ encourages more exploration.

The term $\sqrt{\frac{\ln N_t}{N_t(a)}}$ acts as the uncertainty measure. It grows logarithmically with the total number of plays ($N_t$) and decreases as a specific arm is played more often ($N_t(a)$ increases). This ensures that actions which haven't been tried often, or whose estimates are potentially inaccurate, receive a bonus, making them more likely to be selected. If $N_t(a) = 0$, the bonus is considered infinite, ensuring each action is tried at least once (assuming appropriate initialization).

This "optimistic" approach effectively balances exploration and exploitation. Actions with high estimated values are favored, but actions with high uncertainty also get a chance, especially early on or if their potential upper bound is competitive.

Applying UCB in Reinforcement Learning

Extending UCB from the stateless bandit setting to sequential decision-making in Markov Decision Processes (MDPs) presents challenges but follows the same core principle. The state adds complexity because the value of an action depends on the state it's taken in.

A common way to adapt UCB is to apply it to the action selection within each state $s$. The selection rule becomes:

$$A_t = \underset{a}{\mathrm{argmax}} \left[ Q(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$

Here:

• $Q(s, a)$ is the estimated value of taking action $a$ in state $s$.
• $N(s)$ is the count of how many times state $s$ has been visited.
• $N(s, a)$ is the count of how many times action $a$ has been taken in state $s$.

This requires maintaining estimates for Q-values (e.g., using Q-learning or SARSA updates) and also keeping track of state-visit counts $N(s)$ and state-action counts $N(s, a)$.

Evolution of Q-values, uncertainty bonuses, and resulting UCB scores for two actions (A and B) with true means 0.6 and 0.7 respectively. Action B eventually surpasses A in UCB score as its higher potential is explored.

Challenges and Adaptations

The direct application described above works well in tabular settings or environments with discrete, manageable state spaces. However, it faces significant hurdles in environments with large or continuous state and action spaces:

1. Tracking Counts: Maintaining exact counts $N(s)$ and $N(s, a)$ becomes impossible when states are continuous or the state space immense. Function approximation techniques are needed to estimate these counts or density models. Pseudo-counts, derived from density models or hashing functions, are often used as approximations (discussed later in this chapter).
2. Function Approximation: When using deep neural networks or other function approximators for $Q(s, a)$, the interaction between the function approximator and the UCB bonus needs careful consideration. Simply adding the bonus to the approximated Q-value might not be statistically sound or stable.
3. Exploration Constant: The parameter $c$ balances exploration and exploitation. Its optimal value can be problem-dependent and may require careful tuning. Theoretical values derived for bandits might not directly apply.
4. Non-Stationarity: Standard UCB assumes stationary reward distributions. In RL, the effective distribution of rewards for a state-action pair can change as the policy evolves and different subsequent states are reached.

Despite these challenges, the core principle of UCB influences many advanced exploration techniques. For instance, in model-based RL, UCB is often used within planning algorithms like Monte Carlo Tree Search (MCTS) to guide the simulation process towards uncertain but potentially rewarding sequences of actions (as seen in Chapter 5). Modifications incorporating function approximation and dealing with large state spaces have also been developed, often combining UCB ideas with other approaches like bootstrapping or intrinsic motivation.

Summary

UCB methods provide a principled way to manage the exploration-exploitation trade-off by explicitly modeling uncertainty. By adding an uncertainty bonus to estimated action values, UCB encourages exploration of actions that are not well understood but might yield high rewards. While direct application in large-scale RL requires adaptations to handle extensive state spaces and function approximation, the idea of "optimism in the face of uncertainty" remains significant in designing exploration strategies for complex sequential decision-making problems. It represents a step toward more directed and potentially more efficient discovery of optimal policies.