Abstract
Traditional multi-armed bandit models assume that items can be recommended repeatedly. However, many real-world recommendation scenarios, such as personalized styling or dating apps, involve "disposable" items that can only be shown once. This paper formalizes the Disposable Linear Bandit problem and introduces the Generalized UCB (UCBG) algorithm. By incorporating a "look-ahead" strategy and an efficient alternating heuristic, the proposed method manages the inventory of available items to optimize long-term rewards. Experimental results on synthetic datasets show significant regret reduction compared to standard bandit algorithms.
Introduction
In recommendation systems, the goal is often to learn user preferences while maximizing immediate satisfaction. Standard linear bandit algorithms like LinUCB excel at this by repeatedly recommending the "best" items. However, in "one-and-done" scenarios—like Stitch Fix's personalized boxes or dating app profiles—an item is removed from the pool once it is recommended. This constraint, known as disposability, creates a unique challenge: a greedy algorithm might exhaust high-potential items early for exploration, leaving only low-quality options for the future.
Methodology
The authors propose shifting the objective from selecting the single best arm to selecting the best remaining subset of arms for the entire time horizon.
Generalized UCB (UCBG)
The UCBG algorithm selects a subset of arms that maximizes the total potential reward over the remaining time horizon. This "look-ahead" approach ensures the algorithm doesn't prematurely exhaust its best options, effectively managing the inventory of available items.
Alternating Heuristic and Initialization
Since finding the optimal subset is a computationally hard combinatorial problem, the authors developed a fast alternating heuristic. This heuristic iteratively switches between optimizing the user preference estimate and selecting the best set of arms. To ensure high-quality convergence, they utilize a Similarity-Based Initialization. This strategy prioritizes arms with many similar neighbors in the feature space, treating them as safer to "spend" for exploration because similar alternatives exist for future exploitation.
Theoretical Insights
The paper establishes a new minimax lower bound for the disposable setting: $\Omega(\phi d \sqrt{T})$. The term $\phi$ represents the "spread" of the optimal arms. Interestingly, this suggests that disposability can sometimes lead to lower regret than standard settings because the algorithm is forced to explore a broader range of high-quality items rather than converging on a single point.
Experimental Results
The proposed methods were evaluated using synthetic datasets with 5,000 arms and users in a 15-dimensional space. The experiments covered both Bernoulli and Gaussian reward distributions across various time horizons ($T$).
The results demonstrate that the UCBG variants, particularly UCBG3, consistently outperform standard benchmarks like LinUCB and Greedy selection. In synthetic experiments, the proposed alternating heuristic achieved up to 10% lower regret than competing benchmarks.
Conclusion and Future Work
This work highlights the fundamental differences between standard and disposable bandits. While the proposed alternating heuristic offers significant performance gains, its computational complexity remains higher than simple greedy methods. Future research will focus on scaling these methods for real-time systems with millions of items and validating the approach on real-world user interaction logs.
Summary updated