Abstract
In the multi-armed bandit (MAB) framework, the feedback mechanism significantly dictates the achievable regret. This paper investigates the "one-sided full-information" setting, a variant where selecting an action reveals the rewards of all higher-indexed actions. We present the Elimination-based algorithm (ELIM), which leverages this asymmetric feedback structure to achieve a near-optimal distribution-independent regret bound of $O(\sqrt{T \log(TK)})$. Through theoretical analysis and numerical simulations, we demonstrate that ELIM provides a robust, provably efficient solution for applications such as online reserve price auctions, where information flow is inherently directional.
Introduction
In a standard Multi-Armed Bandit (MAB) problem, an agent faces a fundamental trade-off between exploration and exploitation: they only observe the reward for the specific arm they choose. Conversely, in a "full-information" setting, the agent observes the rewards for all possible arms regardless of their choice. This paper explores a middle ground known as the one-sided full-information setting.
This structure is particularly relevant to online reserve price auctions. Consider an auctioneer setting a reserve price. If a low price is set, the auctioneer observes all bids that exceeded that price, effectively revealing what the outcome would have been for any higher reserve price. However, if a high price is set and no bids are received, the auctioneer gains no information regarding potential outcomes at lower price points. The challenge lies in balancing the need to play lower-indexed arms (which provide more information) against the desire to play the arm with the highest expected reward.
The ELIM Algorithm
The authors propose ELIM (Elimination-based algorithm), a strategy designed to exploit the asymmetric feedback of the one-sided setting. The algorithm operates through four primary mechanisms:
- Active Set Management: ELIM maintains a set of "active" arms ($S_t$) that have not yet been statistically ruled out as suboptimal.
- Optimistic Information Gathering: In each round, the algorithm selects the arm with the smallest index within the active set. Since playing arm $i$ reveals rewards for all arms $j \ge i$, choosing the smallest index maximizes the feedback received for all remaining candidates.
- Statistical Pruning: The algorithm tracks empirical mean rewards for all arms. If an arm’s performance falls significantly below the current best-performing arm—specifically, beyond a calculated confidence radius $\rho_t$—it is eliminated from the active set.
- The Doubling Trick: To handle scenarios where the total time horizon $T$ is unknown, the authors utilize a standard doubling trick, executing the algorithm in epochs of increasing length.
Theoretical Contributions
The core theoretical achievement of this work is the establishment of a distribution-independent regret bound of $O(\sqrt{T \log(TK)})$. This represents a significant improvement over previous theoretical guarantees for directed feedback graphs.
To prove this bound, the authors employed a "bubble-sort" argument. They demonstrated that the worst-case regret occurs when the arms are ordered such that the optimal arm has a high index. This configuration forces the algorithm to repeatedly play suboptimal, lower-indexed arms to gather sufficient information to eliminate them. Furthermore, the authors established a lower bound of $\Omega(\sqrt{T \log K})$, proving that ELIM is optimal up to small logarithmic factors.
Empirical Results
The paper evaluates ELIM using numerical experiments on synthetic data, primarily utilizing Bernoulli reward distributions across two main scenarios:
- Uniform-mean: All suboptimal arms share the same mean, allowing the authors to test the impact of the reward gap ($\Delta$) and the position of the optimal arm.
- Random-mean: Suboptimal arm means are drawn uniformly at random to simulate noisier, more realistic environments.
ELIM was compared against EXP3-RTB (an adversarial bandit baseline) and UCB-N (a variant of the Upper Confidence Bound algorithm that incorporates side information). The results showed that ELIM significantly outperformed EXP3-RTB. Interestingly, while UCB-N often exhibited superior empirical performance in plots, it currently lacks the tight theoretical guarantees provided for ELIM in this specific one-sided setting.
Conclusion and Future Work
This research successfully closes the gap between upper and lower bounds for the one-sided full-information bandit problem. While ELIM stands as the current "gold standard" for provable performance, the empirical success of UCB-N suggests a promising avenue for future work: developing a tighter theoretical analysis for UCB-style algorithms in asymmetric feedback environments. Additionally, extending these insights to more complex or dynamic graph feedback structures could further broaden the applicability of these algorithms in industrial contexts.
Summary updated