# Online Linear Programming with Batching

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 18 references that are in the map.
- First posted on arXiv 1 Aug 2024.

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

- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [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)
- [Upfront Commitment in Online Resource Allocation with Patient Customers](https://mlsanity.com/paper/2108.03517/) (2021)
- [Batching and Optimal Multi-stage Bipartite Allocations](https://mlsanity.com/paper/2211.16581/) (2022)

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

- [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)

## Abstract (arXiv)

We study Online Linear Programming (OLP) with batching. The planning horizon is cut into K batches, and decisions on orders can be delayed to the end of their associated batch. The ability to delay decisions improves operational performance, as measured by regret. We study two questions: (1) What is a lower bound on the regret as a function of K and the length of the planning horizon? (2) Which algorithms can achieve this regret lower bound? This paper analyzes these questions when the distribution of the reward has a continuous support. We provide an Omega(log K) regret lower bound in the single-resource case, and we provide pricing algorithms having an O(log K) regret in the setting with Poisson arrivals and multiple types of resources. All the algorithms update the prices at most K times and only delay orders of the first and the last batches. All the regret bounds are independent of the length of the planning horizon. Finally, we study a more realistic large support setting where the number of distinct order types is finite but scales with the total number of orders. We prove that our Theta(log K) bounds still hold for the batching operation of a multisecretary problem with discretized uniform rewards in this large support setting, provided the support grows fast enough. This suggests that the continuous support setting that is the paper's focus serves as a useful theoretical surrogate for the more realistic large finite support setting.