Online Learning with Probing for Sequential User-Centric Selection
Tianyi Xu, Yiting Chen, Henger Li, Zheyong Bian, Emiliano Dall’Anese, Zizhan Zheng · 2025
Read Online Learning with Probing for Sequential User-Centric Selection by Tianyi Xu, Yiting Chen, Henger Li, Zheyong Bian, Emiliano Dall’Anese, Zizhan Zheng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20112.txt.
Introduction
Tianyi Xu and five co-authors formalize decisions where peeking costs time and money. Their 2025 paper frames probing-augmented user-centric selection. A learner first probes some options to learn their state, then assigns plays. Ridesharing, wireless scheduling, and recommendations all share this shape.
For known odds, a greedy probing rule comes with a constant-factor promise. For unknown odds, their OLPA algorithm learns while probing. Its regret grows with the square root of time, plus small extra terms. A matching lower bound shows that rate is nearly the best possible. Tests on real data backed the math. Probing wisely beats both blind guessing and endless checking.
Catalog record
| CREATOR | Tianyi Xu, Yiting Chen, Henger Li, Zheyong Bian, Emiliano Dall’Anese, Zizhan Zheng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20112
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Learning with Probing for Sequential User-Centric Selection Tianyi Xu, Yiting Chen, Henger Li, Zheyong Bian, Emiliano Dall’Anese, Zizhan Zheng Abstract We formalise 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 K plays to M M arms. PUCS encompasses practical scenarios such as ridesharing, wireless scheduling, and content recommendation, in which both resources and payoffs are initially unknown and probing incurs cost. For the offline setting (known distributions) we present a greedy probing algorithm with a constant‑factor approximation guarantee of ζ = ( e − 1 ) / ( 2 e − 1 ) \zeta=(e-1)/(2e-1) . For the online setting (unknown distributions) we introduce OLPA , a stochastic combinatorial bandit algorithm that achieves a regret bound of 𝒪 ( T + ln 2 T ) \mathcal{O}\!\bigl(\sqrt{T}+\ln^{2}\!T\bigr) . We also prove an Ω ( T ) \Omega(\sqrt{T}) lower bound, showing that the upper bound is tight up to logarithmic factors. Numerical results using the dataset collected from the real world demonstrate the effectiveness of our solutions. † † paperid: 8214 1 Introduction Stochastic multi‑armed bandits (MAB) [ 16 ] and Multi‑player MABs (MP‑MAB) [ 1 ] have been extensively studied as general frameworks for sequential decision making, where the goal is to maximize the cumulative reward by sequentially choosing from a set of options, or “arms” [ 16 , 2 ] . These models have been applied in a variety of domains, including personalized recommendation [ 19 ] , financial portfolio management [ 14 ] , and dynamic resource allocation [ 1 ] . To cope with complex real‑world scenarios, the user‑centric selection problem has recently been introduced as an extension of MP‑MABs [ 7 ] . Consider context recommendation as an example. The decision‑maker recommends multiple pieces of content (mapped to arms in MP‑MABs) and selects a subset of slots (plays) to allocate to these arms (assignment decision). Unlike traditional MP‑MABs, the user‑centric selection problem allows each arm to be associated with stochastic units of resources, and multiple plays can pull the same arm. Applications of the user‑centric selection problem are vast and include personalized content delivery [ 19 ] and resource allocation in ridesharing platforms [ 7 ] . As another example, consider the user‑centric selection problem in ridesharing [ 7 ] . Pickup locations correspond to arms, and drivers can be modeled as plays. There is a moving cost to a pickup location that is related to the reward. Multiple drivers can drive to the same location, but there is a limit on the maximum number of requests (resources) that can be hosted together at any location. This example clearly illustrates the user‑centric selection problem, but in practice, some information is unknown. For instance, in this example, the distribution of passenger requests in a certain area is unknown. The real‑time road conditions are also unknown. These unknown factors can significantly impact the accuracy of decision‑making. The classic MAB framework relies purely on instantaneous feedback received after each decision round to obtain a desired exploration vs. exploitation trade‑off. In such an uncertain environment, probing is a promising approach for acquiring additional information when searching for the best alternative under uncertainty. It was initially studied in economics [ 27 ] and has found applications in database query optimisation [ 23 , 10 , 20 ] . Recently, it has been used to obtain real–time road traffic conditions (subject to a cost) before making vehicle‑routing decisions [ 3 ] , and for collecting link‑quality information for scheduling in wireless access points [ 28 , 29 ] . In this work, we propose a unified framework that integrates probing strategies with assignment decisions in the context of user‑centric selection. We term this abstraction the Probing‑augmented User‑Centric Selection (PUCS) framework. PUCS explicitly couples the probing decision with the subsequent play‑to‑arm assignment, enabling us to quantify both the value and the cost of information acquisition. Concretely, in every round the decision maker first probes a budget‑limited subset of arms to observe their resources and rewards, and then assigns the K plays to the M arms accordingly. In the offline case where the reward and resource distributions are known a priori, we derive a greedy probing algorithm that achieves a constant approximation factor by exploiting the submodularity of the objective function. For the more challenging online setting, we develop a combinatorial bandit algorithm and prove a regret bound of \mathcal{O}\!\bigl(\sqrt{T}+\ln^{2}\!T\bigr) . We remark that [ 31 ] also considers probing in a similar multi‑player MAB setting. However, they do not consider multiple resources for arms and assume that two or more plays assigned to the same arm can lead to a collision. In addition, they assume the rewards follow a Bernoulli distribution, while we consider general distributions. Further, they do not consider a given probing budget as we do. Contributions. The primary contributions of this work are as follows: • We introduce the PUCS framework for jointly choosing which arms to probe and how to assign plays in user‑centric selection problems. • For the offline setting with known distributions, we design a greedy probing algorithm that admits a constant‑factor approximation guarantee \zeta=(e-1)/(2e-1) . • For the online setting with unknown distributions, we propose a two‑phase stochastic combinatorial bandit algorithm ( OLPA ) and establish a regret bound \mathcal{O}\!\bigl(\sqrt{T}+\ln^{2}T\bigr) together with an \Omega(\sqrt{T}) lower bound. • Extensive experiments on real‑world datasets demonstrate the empirical effectiveness of our approach over strong baselines. 2 Related Work Sequential decision-making and online learning have been extensively studied in various contexts. Classical approaches such as multi-armed bandits [ 2 , 4 ] provide foundational strategies for balancing exploration and exploitation. Recent advancements have extended these models to more complex scenarios, including combinatorial bandits [ 8 ] , and multi-player MAB [ 15 ] which are more relevant to our sequential user-centric selection problems. Sequential user-centric selection problems can be viewed as a variant and extension of the multi-player multi-armed bandit (MP-MAB) framework. MP-MAB models are designed to handle situations where multiple players compete for shared arms, requiring strategies that account for both coordination and competition among players [ 30 , 22 ] . These models are particularly effective in scenarios like recommendation systems or resource allocation tasks, where multiple users interact with a common set of options. Unlike traditional MP-MABs, the user-centric selection problem allows each arm to be associated with stochastic units of resources and multiple plays can pull the same arm [ 7 ] . A ridesharing example is considered in [ 7 ] about the sequential user-centric selection problem. In this scenario, pickup locations can be mapped to arms, and drivers can be modeled as plays. The cost of moving to a pickup location is related to the reward, and the ride requests arriving at each arm can be modeled as the resource. Multiple drivers can choose to drive to the same location. However, this approach overlooks the unknown information of the real world, such as real-time traffic information, which can significantly impact decision-making. To address these unknown factors in real‑world systems, one can actively probe the environment and