Conference proceeding
Contextual Linear Bandits with Delay as Payoff
Proceedings of Machine Learning Research - International Conference on Machine Learning, ICML 2025, Vol.267, pp.76246-76272
2025
Abstract
A recent work by Schlisselberg et al. (2025) studies a delay-as-payoff model for stochastic multiarmed bandits, where the payoff (either loss or reward) is delayed for a period that is proportional to the payoff itself. While this captures many real-world applications, the simple multiarmed bandit setting limits the practicality of their results. In this paper, we address this limitation by studying the delay-as-payoff model for contextual linear bandits. Specifically, we start from the case with a fixed action set and propose an efficient algorithm whose regret overhead compared to the standard no-delay case is at most D∆max log T, where T is the total horizon, D is the maximum delay, and ∆max is the maximum suboptimality gap. When payoff is loss, we also show further improvement of the bound, demonstrating a separation between reward and loss similar to Schlisselberg et al. (2025). Contrary to standard linear bandit algorithms that construct least squares estimator and confidence ellipsoid, the main novelty of our algorithm is to apply a phased arm elimination procedure by only picking actions in a volumetric spanner of the action set, which addresses challenges arising from both payoff-dependent delays and large action sets. We further extend our results to the case with varying action sets by adopting the reduction from Hanna et al. (2023). Finally, we implement our algorithm and showcase its effectiveness and superior performance in experiments
Details
- Title: Subtitle
- Contextual Linear Bandits with Delay as Payoff
- Creators
- Mengxiao Zhang - University of Iowa, United StatesYingfei Wang - University of WashingtonHaipeng Luo - University of Southern California
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research - International Conference on Machine Learning, ICML 2025, Vol.267, pp.76246-76272
- ISSN
- 2640-3498
- eISSN
- 2640-3498
- Grant note
- National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001) IIS-1943607 / National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001)
- Language
- English
- Date published
- 2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9985091807602771
Metrics
3 Record Views