Introduction
The Multi-Armed Bandit (MAB) problem represents the fundamental exploration-exploitation trade-off. While standard algorithms like Upper Confidence Bound (UCB) and Thompson Sampling are theoretically robust, they often fail to leverage structured priors—domain knowledge about the relationships between different options. For instance, in pricing experiments, one can reasonably assume that a higher discount will yield a higher conversion rate than a lower one. Standard independent-arm models discard this information.
This paper introduces ELSV (Exploration via Linearly Separable Value Functions), a framework that bridges the gap between simple index policies and complex lookahead planning. By transforming bandit indices into value functions, ELSV enables efficient lookahead search that incorporates complex constraints, significantly improving short-term performance.
Methodology: From Indices to Value Functions
The core of ELSV is the decomposition of a global value function into linearly separable components.
1. Index-to-Value Translation
The authors demonstrate that the "exploration bonus" in policies like UCB or the Gittins Index can be mapped to a value function. An arm's value is defined as the sum of its expected immediate reward and the expected increase in the value of the knowledge state (information gain).
2. Lookahead Search and Decomposition
Instead of navigating an exponentially growing state space, ELSV decomposes the value function into a sum of individual functions for each arm. This allows for a lookahead search of limited depth. When the search reaches its horizon, the ELSV value function estimates the remaining reward.
3. Incorporating Constraints
To handle structured priors (e.g., $\mu_1 \ge \mu_2$), ELSV employs rejection sampling during lookahead. By only considering future scenarios that satisfy known constraints, the agent can update its knowledge of multiple arms from a single observation, effectively "pruning" suboptimal paths.
Evaluation and Results
The framework was evaluated using Bernoulli bandit simulations, including a "Constrained Bernoulli Bandit" scenario designed to mimic personalized discount offers.
Key Performance Metrics
The primary metric for evaluation is Bayesian Regret. The results indicate that while lookahead depth provides marginal gains in simple independent settings, it is transformative when arms are correlated.
In constrained tasks, ELSV-Gittins significantly outperformed standard benchmarks like Bayes-UCB and Thompson Sampling. By leveraging the structured prior, the agent quickly identified and discarded arms that were logically inferior based on the outcomes of related arms.
Insights and Future Directions
A key insight from this work is that the exploration bonus is essentially a proxy for value change. While standard indices are highly optimized for independent arms, their performance plateaus. The "killer app" for lookahead search is the presence of structure; it allows the agent to reason that failure in one arm implies failure in another, more restrictive arm.
Limitations: - Computational Complexity: Although $O(t^3)$ is efficient, deeper lookahead remains expensive. - Heuristics: Rejection sampling for constraints currently lacks formal regret bounds. - Generalization: Future work will explore extending ELSV to contextual bandits and more complex reward distributions beyond the Bernoulli case.
Summary updated