A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
Haoran Xu, Owen Shen, Peter Glynn, Yinyu Ye, Patrick Jaillet · 2026
Read A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming by Haoran Xu, Owen Shen, Peter Glynn, Yinyu Ye, Patrick Jaillet (2026) 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-2603-14673.txt.
Description
Xu and co-authors bound regret for nonstationary online linear programming from a single sample. Orders arrive one by one with shifting reward and resource profiles. Each call to accept or reject is final. Only one sample from each order distribution is known up front. Their re-solving algorithm blends dynamic programming with dual methods from the stationary case. With resources scaling in the order count, regret grows as the square of log n. Strong drift and thin data still allow polylog regret, they prove.
Catalog record
| CREATOR | Haoran Xu, Owen Shen, Peter Glynn, Yinyu Ye, Patrick Jaillet |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116368 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14673