# Observe Before Play: Multi-armed Bandit with Pre-observations

arXiv: https://arxiv.org/abs/1911.09458 · HTML: https://mlsanity.com/paper/1911.09458/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

## Built on by (most cited first, 5 of 5)

- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2506.14988/) (2025)
- [Exploiting Side Information for Improved Online Learning Algorithms in Wireless Networks](https://mlsanity.com/paper/2202.11699/) (2022)
- [Online Learning with Probing for Sequential User-Centric Selection](https://mlsanity.com/paper/2507.20112/) (2025)

## Abstract (arXiv)

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(K2log 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(fracK4M2log 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.