Technical Summary: Delight-gated Exploration (DE)

Problem Statement

The paper addresses the challenge of exploration in unresolved regimes, where the action space or time horizon is too large to allow an agent to resolve all uncertainty within a given budget. In such settings, standard exploration algorithms (e.g., Optimism, Thompson Sampling, Information-Directed Sampling) that search broadly until uncertainty is resolved become infeasible. Consequently, practitioners often default to $\epsilon$-greedy.

While $\epsilon$-greedy is simple and bounds disruption by following a host policy most of the time, its primary flaw is that the exploratory override is blind. It spends its override budget uniformly, often selecting actions whose posterior upside (expected improvement) is already negligible. The paper argues that in unresolved regimes, uncertainty alone is insufficient justification for exploration; exploration should be priced by the product of upside and surprisal.

Methodology: Delight-gated Exploration (DE)

DE introduces a host–override architecture that retains the additive structure of $\epsilon$-greedy but replaces the blind override with a targeted, priced override.

Core Mechanism

1. Host Policy ($\pi_{host}$): A baseline policy (typically greedy or near-greedy) that selects the action with the highest posterior mean reward, $v_t = \max_a m_a(t)$.
2. Exploratory Override: With probability $\epsilon_t$ (annealed over time), the agent considers an override.
3. Prospective Delight ($\tilde{\chi}_t(a)$): The agent calculates a score for candidate actions defined as the product of:
   • Expected Improvement (Up-side): $EIt(a) = E[(f(a) - v_t)^+ | H_t]$.
   • Surprisal (Novelty): $\ell_t(a) = \min\{[-\log \pi_{host}(a) - \ell_{min}]^+, L\}$, capped at $L$. This measures how surprising an action is relative to the host's preference.
4. The Gate: An action $a$ is eligible for the override only if its prospective delight exceeds a fixed gate price $\lambda$:
   $$\tilde{\chi}_t(a) = EIt(a) \cdot \ell_t(a) \ge \lambda$$
5. Selection: If the gated set $G_t$ is non-empty, the override samples from actions in $G_t$ proportional to their delight scores. If $G_t$ is empty, the agent defaults to the host policy.

Theoretical Connection: Pandora's Rule

The paper establishes that the DE gate is mathematically equivalent to Weitzman's Pandora's reservation-value rule for costly search.

• In Pandora's problem, inspecting an arm costs $c$. The optimal policy inspects only if the current best value is below a reservation threshold.
• In DE, the effective inspection cost for an action is $c_a = \lambda / \ell_a$.
• The gate condition $\ell_a E[(X_a - v)^+] \ge \lambda$ is equivalent to $E[(X_a - v)^+] \ge c_a$.
• This implies that DE implements a satisficing search: it explores only when the resolution of uncertainty is worth the "price" of deviation, rather than exploring until all uncertainty is resolved.

Key Contributions

1. Algorithmic Proposal: Introduction of DE, a practical heuristic that uses prospective delight to filter exploratory candidates, recovering Pandora's reservation-value rule in the process.
2. Empirical Scaling: Demonstration that DE scales gracefully across Bernoulli bandits, linear bandits, and tabular MDPs (DeepSea). Crucially, the same hyperparameters ($M=100, \lambda=0.1, L=10$) transfer across these distinct domains without retuning.
3. Structural Analysis:
   • Resolved Arms Exit: Once a suboptimal arm is sufficiently resolved (separated from the optimal arm), its expected improvement decays, causing it to fall below the gate price and exit the exploration set.
   • Fresh Arms Shut Off: In large action spaces, if the host baseline $v_t$ exceeds a reservation threshold $v_{off}$, no untried (fresh) arm can satisfy the gate condition, effectively pruning the search space.
   • Finite Information Budget: In linear bandits, the number of selected overrides is bounded by the information gain (elliptical potential), independent of the number of arms $K$.
4. Regret Behavior: DE exhibits significantly weaker regret growth than Thompson Sampling and $\epsilon$-greedy in unresolved regimes (where $K \gg T$), while matching their performance in small, resolvable environments.

Experimental Results

• Bernoulli Bandits: As the number of arms $K$ increases, the regret of Thompson Sampling and $\epsilon$-greedy degrades linearly or worse. DE's regret remains nearly flat because it stops exploring arms once the host baseline exceeds the shutoff threshold.
• Linear Bandits: DE outperforms baselines across varying dimensions $D$ and noise levels $\sigma$ without hyperparameter tuning, indicating the mechanism captures a structural property of exploration rather than overfitting to specific posteriors.
• DeepSea (Tabular MDPs): In a deep exploration task requiring a specific sequence of $H$ actions, DE matches or outperforms Posterior Sampling Reinforcement Learning (PSRL) and significantly outperforms $\epsilon$-greedy, which degrades rapidly as $H$ increases.

Significance and Claims

The paper claims that DE offers a principled alternative to "blind" exploration in large-scale systems. Its significance lies in:

• Pricing Scarcity: It prices scarce exploration resources by the product of upside and surprisal, rather than relying on uncertainty alone.
• Satisficing vs. Optimizing: It shifts the goal from resolving all uncertainty (which is impossible in unresolved regimes) to finding a "good enough" policy within budget.
• Transferability: The ability to transfer hyperparameters across independent bandits, linear structures, and sequential MDPs suggests the "delight" metric is a robust, domain-agnostic signal for exploration.

The authors explicitly state limitations:

• A full worst-case regret bound for the greedy-host variant remains an open problem.
• The equivalence to Pandora's rule is exact only in revealed-value search; in noisy bandits, expected improvement serves as a proxy for the value of information.
• The fixed-price DE is a finite-budget heuristic; while it achieves optimal prior-tail rates in specific theoretical models, the experimental schedule is not asymptotically optimal in the same sense.

In conclusion, the paper posits that in unresolved regimes, uncertainty with priced upside is the correct driver for exploration, replacing the traditional "uncertainty alone" paradigm.