Exploration and Exploitation, Made Concrete

In the realm of decision-making and reinforcement learning, agents must grapple with the dilemma of whether to choose the most promising action or to explore options that hold less known potential. This choice is quantified through the concept of regret, defined as the difference between the outcome of the chosen action and the outcome of always selecting the best possible action.

Strategies employing exploration must contend with regret that grows either linearly or sublinearly over time. Pure exploitation, while avoiding regret, commits to mediocre actions if initial estimates are incorrect. Conversely, pure exploration leads to regret that escalates linearly, as the agent continues sampling suboptimal actions.

An effective strategy aims for sublinear regret, meaning the per-decision cost of learning approaches zero, resulting in a total regret that grows more slowly than the number of decisions made. In the context of a bandit problem with a fixed set of arms, the optimal achievable regret growth is logarithmic in the number of pulls, a result established by Lai and Robbins in 1985. This serves as the benchmark against which all other strategies are measured.

Several strategies have been proposed to achieve this logarithmic regret bound. The epsilon-greedy method randomly selects an action with probability epsilon (ε) at each step, otherwise choosing the current best action. While simple, it explores at a fixed rate, wasting resources on arms that have already been ruled out. Decaying epsilon over time mitigates this flaw by gradually reducing exploration as the agent gains confidence in its choices.

Optimistic initialization involves starting value estimates above any achievable return, causing unvisited actions to appear most promising until they are tried and proven disappointing. This approach requires no additional computation or randomness but is only effective as a starting point before learning takes place.

The upper confidence bound (UCB) strategy selects the action with the highest estimated value, augmented by a bonus term that grows with the uncertainty of that estimate. Deterministic in nature, UCB directs exploration towards arms with high uncertainty, rather than uniformly across all arms. This approach is particularly valuable for arithmetic calculations, providing a clear understanding of the trade-off between exploration and exploitation.

Thompson sampling offers an alternative approach by maintaining a posterior distribution over each arm's value and sampling from these distributions to make decisions. Exploration emerges naturally from the overlap of posterior distributions, with similar traffic directed to arms with overlapping distributions and clearly inferior arms fading away quickly. This method is often the preferred default choice for solving bandit problems, with extensive arithmetic analysis available for various scenarios.

The bonus term in UCB1, specifically sqrt(2 * ln(t) / n_i), where t represents the total number of decisions so far, and n_i denotes the number of times arm i has been chosen, plays a crucial role in determining the exploration strategy. Evaluating this bonus at t = 1000 for arms with varying amounts of data reveals that the bonus decreases as the square root of the sample count, meaning that ten times more data reduces the bonus by approximately a factor of three.

This demonstrates that uncertainty about an arm's value diminishes slowly, allowing promising arms to be probed for extended periods before they are discarded.

Interestingly, the bonus also increases logarithmically with total time, meaning that an arm unexplored for a prolonged period may regain attractiveness, even without additional information about it. This property renders UCB robust to slow changes in the environment, although it may waste effort in stationary scenarios.

The constant under the square root in the UCB1 formula, set to 2, assumes rewards bounded between 0 and 1. If the reward scale differs, the constant must be adjusted accordingly, as failure to do so will result in over- or under-exploration of the arms.

Moving beyond the simplicity of bandit problems, multi-armed bandit (MAB) problems present significantly greater challenges when transitioning to more complex environments like Markov Decision Processes (MDPs). In MDPs, reaching an unexplored state may require a specific sequence of actions, making random exploration ineffective.

For instance, in a game requiring a long, specific sequence of actions to obtain a reward, uniform random exploration has an extremely low probability of success, making long-term exploration infeasible. This starkly contrasts with the shallow exploration strategies employed in bandit problems, where a single random action may suffice.

The canonical benchmark for hard exploration problems is Montezuma's Revenge, an Atari game that demands players perform a lengthy, specific action sequence to obtain a reward. Early attempts to train deep reinforcement learning agents in this environment yielded no results, as the agents lacked any prior experience to learn from. This highlights the limitations of shallow exploration methods and the need for more sophisticated exploration strategies in complex environments.

Intrinsic reward generation is another approach to tackle hard exploration problems by providing an additional reward for encountering novel states. Count-based methods introduce a bonus inversely proportional to the frequency of state visits, while prediction-error methods add a bonus for states where a learned model's prediction deviates significantly from the actual outcome.

However, these approaches have their own shortcomings, such as the "noisy TV" problem, where the agent may become overly focused on novel states without necessarily learning valuable information.

In summary, the exploration-exploitation dilemma is a fundamental challenge in reinforcement learning, with various strategies attempting to strike a balance between the two. Logarithmic regret growth, as achieved by the UCB1 strategy, provides a desirable trade-off between exploration and exploitation. However, as environments become more complex, such as in MDPs, the need for more sophisticated exploration methods and intrinsic reward generation becomes increasingly apparent.