Observe Before Play: Multi-armed Bandit with Pre-observations
This work addresses the problem of optimizing decision-making under uncertainty with costly information acquisition for researchers in bandit algorithms, offering incremental improvements by extending existing frameworks with pre-observations.
The paper tackles the stochastic multi-armed bandit problem by allowing players to pre-observe arm rewards at a cost, introducing an additional trade-off between observation and exploitation. It proposes algorithms for single-player and multi-player settings, proving regret bounds such as O(K^2 log T) for single-player and O(K^4/M^2 log T) for centralized multi-player, with experiments showing outperformance over baselines.
We consider the stochastic multi-armed bandit (MAB) problem in a setting where a player can pay to pre-observe arm rewards before playing an arm in each round. Apart from the usual trade-off between exploring new arms to find the best one and exploiting the arm believed to offer the highest reward, we encounter an additional dilemma: pre-observing more arms gives a higher chance to play the best one, but incurs a larger cost. For the single-player setting, we design an Observe-Before-Play Upper Confidence Bound (OBP-UCB) algorithm for $K$ arms with Bernoulli rewards, and prove a $T$-round regret upper bound $O(K^2\log T)$. In the multi-player setting, collisions will occur when players select the same arm to play in the same round. We design a centralized algorithm, C-MP-OBP, and prove its $T$-round regret relative to an offline greedy strategy is upper bounded in $O(\frac{K^4}{M^2}\log T)$ for $K$ arms and $M$ players. We also propose distributed versions of the C-MP-OBP policy, called D-MP-OBP and D-MP-Adapt-OBP, achieving logarithmic regret with respect to collision-free target policies. Experiments on synthetic data and wireless channel traces show that C-MP-OBP and D-MP-OBP outperform random heuristics and offline optimal policies that do not allow pre-observations.