# Online Learning with Probing for Sequential User-Centric Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 27 Jul 2025.

## Builds on (most cited first, 8 of 8)

- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Neural Approximate Dynamic Programming for On-Demand Ride-Pooling](https://mlsanity.com/paper/1911.08842/) (2019)
- [Budget-Constrained Multi-Armed Bandits with Multiple Plays](https://mlsanity.com/paper/1711.05928/) (2017)
- [Observe Before Play: Multi-armed Bandit with Pre-observations](https://mlsanity.com/paper/1911.09458/) (2019)
- [Joint AP Probing and Scheduling: A Contextual Bandit Approach](https://mlsanity.com/paper/2108.03297/) (2021)
- [Online Learning for Adaptive Probing and Scheduling in Dense WLANs](https://mlsanity.com/paper/2212.13585/) (2022)
- [Understanding human mobility patterns in Chicago: an analysis of taxi data using clustering techniques](https://mlsanity.com/paper/2306.12094/) (2023)

## Abstract (arXiv)

We formalize sequential decision-making with information acquisition as the probing-augmented user-centric selection (PUCS) framework, where a learner first probes a subset of arms to obtain side information on resources and rewards, and then assigns K plays to M arms. PUCS covers applications such as ridesharing, wireless scheduling, and content recommendation, in which both resources and payoffs are initially unknown and probing is costly. For the offline setting with known distributions, we present a greedy probing algorithm with a constant-factor approximation guarantee zeta = (e-1)/(2e-1). For the online setting with unknown distributions, we introduce OLPA, a stochastic combinatorial bandit algorithm that achieves a regret bound O(√T + ln2 T). We also prove a lower bound Omega(√T), showing that the upper bound is tight up to logarithmic factors. Experiments on real-world data demonstrate the effectiveness of our solutions.