# Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

## Built on by (most cited first, 30 of 32)

- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Online Learning for Traffic Routing under Unknown Preferences](https://mlsanity.com/paper/2203.17150/) (2022)
- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Trading-off price for data quality to achieve fair online allocation](https://mlsanity.com/paper/2306.13440/) (2023)
- [Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness](https://mlsanity.com/paper/2511.07604/) (2025)
- [Cross-Epoch Adaptive Rollout Optimization for RL Post-Training](https://mlsanity.com/paper/2606.05606/) (2026)
- [An Online Algorithm for Chance Constrained Resource Allocation](https://mlsanity.com/paper/2303.03254/) (2023)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Online Allocation Problem with Two-sided Resource Constraints](https://mlsanity.com/paper/2112.13964/) (2021)
- [Online Regenerative Learning](https://mlsanity.com/paper/2209.08657/) (2022)
- [Adaptive Resolving Methods for Markov Decision Processes with Function Approximations](https://mlsanity.com/paper/2505.12037/) (2025)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Online Linear Programming for Multi-Objective Routing in LLM Serving](https://mlsanity.com/paper/2607.03948/) (2026)
- [Differentiating Through Dual Prices: End-to-End Policy Learning Under Capacity Constraints](https://mlsanity.com/paper/2608.04669/) (2026)
- [Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand](https://mlsanity.com/paper/2608.14096/) (2026)
- [LLM-Powered Predictive Decision-Making for Sustainable Data Center Operations](https://mlsanity.com/paper/2608.18503/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)

## Abstract (arXiv)

We study an online linear programming (OLP) problem under a random input model in which the columns of the constraint matrix along with the corresponding coefficients in the objective function are generated i.i.d. from an unknown distribution and revealed sequentially over time. Virtually all pre-existing online algorithms were based on learning the dual optimal solutions/prices of the linear programs (LP), and their analyses were focused on the aggregate objective value and solving the packing LP where all coefficients in the constraint matrix and objective are nonnegative. However, two major open questions were: (i) Does the set of LP optimal dual prices learned in the pre-existing algorithms converge to those of the "offline" LP, and (ii) Could the results be extended to general LP problems where the coefficients can be either positive or negative. We resolve these two questions by establishing convergence results for the dual prices under moderate regularity conditions for general LP problems. Specifically, we identify an equivalent form of the dual problem which relates the dual LP with a sample average approximation to a stochastic program. Furthermore, we propose a new type of OLP algorithm, Action-History-Dependent Learning Algorithm, which improves the previous algorithm performances by taking into account the past input data as well as decisions/actions already made. We derive an O(log n log log n) regret bound (under a locally strong convexity and smoothness condition) for the proposed algorithm, against the O(√n) bound for typical dual-price learning algorithms, where n is the number of decision variables. Numerical experiments demonstrate the effectiveness of the proposed algorithm and the action-history-dependent design.