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

CREATORHaoran Xu, Owen Shen, Peter Glynn, Yinyu Ye, Patrick Jaillet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116368
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14673

Browse the full library · About the Tower of Babel