Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20112 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913995070373888 |
|---|---|
| author | Xu, Tianyi Chen, Yiting Li, Henger Bian, Zheyong Dall'Anese, Emiliano Zheng, Zizhan |
| author_facet | Xu, Tianyi Chen, Yiting Li, Henger Bian, Zheyong Dall'Anese, Emiliano Zheng, Zizhan |
| contents | 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 $ζ= (e-1)/(2e-1)$. For the online setting with unknown distributions, we introduce OLPA, a stochastic combinatorial bandit algorithm that achieves a regret bound $\mathcal{O}(\sqrt{T} + \ln^{2} T)$. We also prove a lower bound $Ω(\sqrt{T})$, showing that the upper bound is tight up to logarithmic factors. Experiments on real-world data demonstrate the effectiveness of our solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20112 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Learning with Probing for Sequential User-Centric Selection Xu, Tianyi Chen, Yiting Li, Henger Bian, Zheyong Dall'Anese, Emiliano Zheng, Zizhan Machine Learning Artificial Intelligence Data Structures and Algorithms 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 $ζ= (e-1)/(2e-1)$. For the online setting with unknown distributions, we introduce OLPA, a stochastic combinatorial bandit algorithm that achieves a regret bound $\mathcal{O}(\sqrt{T} + \ln^{2} T)$. We also prove a lower bound $Ω(\sqrt{T})$, showing that the upper bound is tight up to logarithmic factors. Experiments on real-world data demonstrate the effectiveness of our solutions. |
| title | Online Learning with Probing for Sequential User-Centric Selection |
| topic | Machine Learning Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.20112 |