# Infrequent Resolving Algorithm for Online Linear Programming arXiv: https://arxiv.org/abs/2408.00465 · HTML: https://mlsanity.com/paper/2408.00465/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 62 references that are in the map. - First posted on arXiv 1 Aug 2024. ## Builds on (most cited first, 24 of 24) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019) - [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020) - [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020) - [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020) - [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020) - [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019) - [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020) - [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020) - [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020) - [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017) - [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018) - [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013) - [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019) - [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019) - [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) - [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019) - [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022) - [Greedy Algorithm for Multiway Matching with Bounded Regret](https://mlsanity.com/paper/2112.04622/) (2021) - [Solving Linear Programs with Fast Online Learning Algorithms](https://mlsanity.com/paper/2107.03570/) (2021) - [Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances](https://mlsanity.com/paper/2205.09078/) (2022) - [Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent](https://mlsanity.com/paper/2202.06152/) (2022) ## Built on by (most cited first, 8 of 8) - [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025) - [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024) - [Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy](https://mlsanity.com/paper/2607.02196/) (2026) - [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026) - [Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand](https://mlsanity.com/paper/2608.14096/) (2026) - [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026) - [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026) - [Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More](https://mlsanity.com/paper/2610.09577/) (2026) ## Abstract (arXiv) Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only O(loglog T) times over the time horizon T. Moreover, when we are allowed to solve LPs only M times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly Oleft(T^(1/2)M-1right) regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. The code is available at https://github.com/guokai-li/infrequentresolvingolp.