# Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods

arXiv: https://arxiv.org/abs/2402.07108 · HTML: https://mlsanity.com/paper/2402.07108/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 11 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management](https://mlsanity.com/paper/2011.06327/) (2020)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)
- [Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-dependent Competitive Ratios](https://mlsanity.com/paper/1905.04770/) (2019)
- [Solving Linear Programs with Fast Online Learning Algorithms](https://mlsanity.com/paper/2107.03570/) (2021)

## Built on by (most cited first, 3 of 3)

- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Online Linear Programming with Batching](https://mlsanity.com/paper/2408.00310/) (2024)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)

## Abstract (arXiv)

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 O(√T), which is suboptimal compared to the 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 O(√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 O(T1/3) with this new framework.