Delightful Exploration
Ian Osband · 2026
Read Delightful Exploration by Ian Osband (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13287.txt.
Introduction
Osband introduces delight gated exploration, a rule for spending exploratory actions only when they promise enough. Broad search wastes budget when action spaces are too large to resolve, and random overrides spend blindly. Delight, defined as expected gain times surprise, prices each override against a gate value, recovering Pandora's reservation rule for costly search. Across bandit and tabular tests, the same settings transfer without retuning and regret grows far more slowly than rivals.
Catalog record
| CREATOR | Ian Osband |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58446 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13287
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Delightful Exploration Ian Osband Abstract Most exploration algorithms search broadly until uncertainty is resolved. When the action space is too large to resolve within budget, practitioners default to ε \varepsilon -greedy, which bounds disruption but spends its override blindly. We introduce Delight-gated exploration (DE), a host–override rule that spends exploratory actions only when their prospective delight (expected improvement times surprisal) exceeds a gate price. This practical heuristic recovers a classical result: Pandora’s reservation-value rule for costly search, with surprisal setting the effective inspection cost. Resolved arms exit the gate, fresh arms shut off above a prior-determined threshold, and selected linear-bandit overrides consume finite information budget. Across Bernoulli bandits, linear bandits, and tabular MDPs, the same hyperparameters transfer without retuning, and DE shows much weaker regret growth than Thompson Sampling and ε \varepsilon -greedy in the tested unresolved regimes. Delight improves acting for the same reason it improves learning: it prices scarce resources by the product of upside and surprisal. 1 Introduction Most exploration theory studies the long-run regime, where the agent has enough interaction to resolve the optimal policy. Optimism, posterior sampling, information-directed sampling, and Bayes-optimal planning all search broadly until uncertainty is resolved [ 9 , 18 ] . That broad search pays off when the budget is large enough to amortize it. We target the unresolved regime: action spaces or horizons large enough that broad search cannot be amortized within the available budget. In this regime, large-scale systems default to \varepsilon -greedy. The reasons are practical: \varepsilon -greedy is additive, posterior-free, and simple to implement. It follows a production policy most of the time and only overrides with probability \varepsilon , so the worst-case disruption is bounded. The problem is not the override rate, but how the override is spent. \varepsilon -greedy spends it blindly, often on actions whose posterior upside is already negligible. We propose Delight-gated exploration (DE), which keeps the same additive host-override structure but replaces the blind override with a targeted one. DE uses posterior information to filter candidates. On override rounds, it selects only actions whose prospective delight (the product of expected improvement and surprisal) exceeds a gate price. Actions without enough upside do not pass the gate. A fixed gate price therefore implements satisficing search. The agent explores while posterior upside exceeds the price of deviation, not until all uncertainty is resolved. Like \varepsilon -greedy, DE is a mixture of host and override. The difference is that the override is targeted rather than blind. This paper transposes the Delightful Policy Gradient [ 16 ] from learning to acting. There, delight gates which updates to apply; here, prospective delight gates which actions to try. The distinction is AND versus OR. Standard optimism keeps actions exploration-eligible when uncertainty remains high. DE requires both posterior upside and surprisal. When the environment cannot be fully resolved, this difference becomes decisive. The optimistic set remains broad because many actions are still uncertain, while the delight-gated set shrinks as the host improves. The same gate is also a reservation-value rule. In Weitzman’s Pandora problem, inspecting an action costs c and reveals its latent value. The optimal policy inspects only while the current best value is below a reservation threshold [ 22 ] . DE recovers the same eligibility condition, with the gate price and surprisal jointly setting the effective inspection cost. For fresh \mathrm{Beta}(1,1) Bernoulli arms, this gives a shutoff threshold above which no untried arm passes the gate. DE explores not because an action is uncertain, but because resolving that uncertainty is worth its price. We make four contributions. First, we introduce DE and show strong empirical scaling across Bernoulli bandits, linear bandits, and tabular MDPs, with the same hyperparameters transferred across all three (Section 3 ). Second, we connect DE to optimal search theory: the gate is Pandora eligibility, and horizon-priced reservation search achieves the optimal prior-tail rate in a revealed-value discovery model (Sections 2.2 and 4.4 ). Third, we give structural analysis explaining the observed scaling: resolved arms exit the gate, fresh arms shut off at a reservation threshold, and selected linear-bandit overrides consume finite information budget (Section 4 ). Fourth, we state the limits clearly: fixed-price DE is a finite-budget heuristic, and a full regret bound for the greedy-host noisy-bandit version remains open (Section 5 ). 2 Algorithm Delight-gated exploration augments a greedy host with a sparse exploratory override. With probability 1-\varepsilon_{t} the agent follows the host. With probability \varepsilon_{t} it draws from the override. The only question is how to score candidate exploratory actions. Our answer mirrors the Delightful Policy Gradient: use the product of upside and novelty. For exploration, upside is measured by expected improvement and novelty by surprisal under the host policy. 2.1 Definition Consider a finite action set \mathcal{A} with unknown expected rewards f(a) . Let m_{a}(t)=\mathbb{E}[f(a)\mid\mathcal{H}_{t}] be the posterior mean reward given history \mathcal{H}_{t} . The host baseline is v_{t}=\max_{a}m_{a}(t) . We write \pi_{t}^{\mathrm{host}} for the host policy. The analysis below studies the greedy limit ( \pi_{t}^{\mathrm{host}} plays \argmax_{a}m_{a}(t) ), while experiments use a near-greedy Boltzmann host. We measure upside by expected improvement over the host, \mathrm{EI}_{t}(a)=\mathbb{E}[(f(a)-v_{t})^{+}\mid\mathcal{H}_{t}] . Novelty is measured by a capped relative surprisal \ell_{t}(a)=\min\{[-\log\pi_{t}^{\mathrm{host}}(a)-\ell_{\min,t}]_{+},\,L\} , where \ell_{\min,t}=\min_{b}\{-\log\pi_{t}^{\mathrm{host}}(b)\} . This makes the host’s preferred action have zero surprisal. For a greedy host, non-host actions saturate at L , and DE reduces to a thresholded EI rule. Prospective delight is the product \tilde{\chi}_{t}(a)=\mathrm{EI}_{t}(a)\ell_{t}(a) . This transposes the principle of the Delightful Policy Gradient family [ 16 , 17 ] from learning to acting. Prospective delight must exceed \lambda for an exploratory override to fire. The gated set collects actions with \tilde{\chi}_{t}(a)\geq\lambda . If non-empty, the override samples q_{t}^{\lambda}(a)\propto\tilde{\chi}_{t}(a)\mathbf{1}\{a\in\mathcal{G}_{t}\} ; otherwise it defaults to the host. The final acting policy is \pi_{t}^{\mathrm{act}}=(1-\varepsilon_{t})\pi_{t}^{\mathrm{host}}+\varepsilon_{t}q_{t}^{\lambda}, (1) where \varepsilon_{t}=M/(M+t) is annealed with half-life M . The gate price \lambda is measured in reward units times surprisal; across tasks we use rewards or value estimates on comparable unit scales. 2.2 A Reservation-Value View The delight gate has a classical search interpretation. Consider a revealed-value search problem. Each action a has a latent value X_{a} drawn from a known prior. Inspecting a reveals X_{a} and costs c_{a} , and the decision maker keeps the best revealed value. Pandora’s rule assigns each action a reservation value. When the reservation equation has a unique solution, this value z_{a} satisfies \mathbb{E}[(X_{a}-z_{a})^{+}]=c_{a}. (2) When the solution is not unique, the generalized inverse below gives the same stopping rule. Pandora opens actions in decreasing order of reservation value and stops once the current best value exceeds every unopened reservation value [ 22 ] . DE has the same reservation structure. For an action with host-relative surprisal \ell_{a}>0 , define the effective inspection cost c_{a}:=\lambda/\ell_{a} . When \ell_{a}=0 , we interpret the effective inspection cost as infinite: such actions are handled by the host rather than the exploratory override. Then action a passes the delight gate at baseline v iff \ell_{a}\mathbb{E}[(X_{a}-v)^{+}]\geq\lambda\quad\Longleftrightarrow\quad\mathbb{E}[(X_{a}-v)^{+}]\geq c_{a}. Define the delight reservation index z_{a}^{\lambda}:=\sup\left\{z:\ell_{a}\,\mathbb{E}[(X_{a}-z)^{+}]\geq\lambda\right\}. (3) Proposition 1 (The DE gate is Pandora eligibility) . In the revealed-value search model with fixed \ell_{a}>0 , let \mathcal{G}(v) denote the DE gated set at baseline v . Then \mathcal{G}(v)=\{a:\ell_{a}\mathbb{E}[(X_{a}-v)^{+}]\geq\lambda\}=\{a:z_{a}^{\lambda}\geq v\}. In the unthrottled revealed-value search model, if the override always selects