# Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2026.

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

- [Cross-Epoch Adaptive Rollout Optimization for RL Post-Training](https://mlsanity.com/paper/2606.05606/) (2026)

## Abstract (arXiv)

We consider the dynamic resource allocation problem where the decision space is finite-dimensional, yet the solution must satisfy a large or even infinite number of constraints revealed via streaming data or oracle feedback. We model this challenge as an Online Semi-infinite Linear Programming (OSILP) problem and develop a novel LP formulation to solve it approximately. Specifically, we employ function approximation to reduce the number of constraints to a constant q. This addresses a key limitation of traditional online LP algorithms, whose regret bounds typically depend on the number of constraints, leading to poor performance in this setting. We propose a dual-based algorithm to solve our new formulation, which offers broad applicability through the selection of appropriate potential functions. We analyze this algorithm under two classical input models-stochastic input and random permutation-establishing regret bounds of O(q√T) and Oleft(left(q+qlogT)√Tright)right) respectively. Note that both regret bounds are independent of the number of constraints, which demonstrates the potential of our approach to handle a large or infinite number of constraints. Furthermore, we investigate the potential to improve upon the O(q√T) regret and propose a two-stage algorithm, achieving O(qlogT + q/ε) regret under more stringent assumptions. We also extend our algorithms to the general function setting. A series of experiments validates that our algorithms outperform existing methods when confronted with a large number of constraints.