Decoupling Learning and Decision-Making: Breaking the $\mathcalO(\sqrtT)$ Barrier in Online Resource Allocation with First-Order Methods
<|reference_start|>Decoupling Learning and Decision-Making: Breaking the $\mathcalO(\sqrtT)$ Barrier in Online Resource Allocation with First-Order Methods: Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical success of first-order methods, they typically achieve a regret no better than $\mathcal{O}(\sqrt{T})$, which is suboptimal compared to the $\mathcal{O}(\log T)$ bound guaranteed by the state-of-the-art linear programming (LP)-based online algorithms. This paper establishes several important facts about online linear programming, which unveils the challenge for first-order-method-based online algorithms to achieve beyond $\mathcal{O}(\sqrt{T})$ regret. To address the challenge, we introduce a new algorithmic framework that decouples learning from decision-making. For the first time, we show that first-order methods can attain regret $\mathcal{O}(T^{1/3})$ with this new framework.<|reference_end|>
@article{gao2024decoupling,
    title={Decoupling Learning and Decision-Making: Breaking the
  $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with
  First-Order Methods},
    author={Wenzhi Gao, Chunlin Sun, Chenyu Xue, Dongdong Ge, Yinyu Ye},
    journal={arXiv preprint arXiv:2402.07108},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07108},
    primaryClass={cs.LG math.OC}
}