A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

• URL: http://arxiv.org/abs/2603.14673v1
• Date: Sun, 15 Mar 2026 23:59:30 GMT
• Title: A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
• Abstract summary: We study nonstationary Online Linear Programming (OLP)<n>In OLP, $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors.<n>We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments.
• Score: 29.531157410826825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonstationary Online Linear Programming (OLP), where $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors. At the beginning of the planning horizon, the decision-maker is provided with a resource endowment that is sufficient to fulfill a significant portion of the requests. The decision-maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to this resource endowment. We focus on the challenging single-sample setting, where only one sample from each of the $n$ distributions is available at the start of the planning horizon. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of orders, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

Related papers

• A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret [6.929167893040819]
  We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon.<n>We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with the current request type.
  arXiv  Detail & Related papers  (2026-09-05T05:30:29Z)
• ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping [79.1905186547363]
  ResiSpec is a framework that strategically reforms the proposal distribution during verification.<n>It prevents candidate obsolescence and achieves up to 1.92$times$ speedup over state-of-the-art multi-candidate methods.
  arXiv  Detail & Related papers  (2026-08-25T11:25:55Z)
• Adaptive Multi-Round Allocation with Stochastic Arrivals [26.102812388131813]
  We study a sequential resource allocation problem motivated by adaptive network recruitment.<n>We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities.<n>In the multi-round setting, the resulting Bellman recursion is intractable due to the high-dimensional evolution of the frontier.
  arXiv  Detail & Related papers  (2026-05-12T13:29:06Z)
• Non-Stationary Online Resource Allocation: Learning from a Single Sample [5.81028169940199]
  We study online resource allocation under non-stationary demand with a minimum offline data requirement.<n>We propose a novel type-dependent quantile-based meta-policy that decouples the problem into modular components.
  arXiv  Detail & Related papers  (2026-02-20T10:07:35Z)
• Online Linear Programming with Replenishment [9.214452378957697]
  We study an online linear programming (OLP) model in which inventory is not provided upfront but instead arrives gradually through a replenishment process.<n>The introduction of dispersed, uncertain replenishment fundamentally alters the structure of classical OLPs.<n>We develop new algorithms and regret analyses for three major distributional regimes studied in the OLP literature.
  arXiv  Detail & Related papers  (2026-01-21T04:09:29Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  We propose a novel regularization scheme for linear decision rules (LDR) based on the AdaSO (adaptive least absolute shrinkage and selection operator) Experiments show that the overfit threat is non-negligible when using the classical non-regularized LDR to solve MSLP. For the LHDP problem, our analysis highlights the following benefits of the proposed framework in comparison to the non-regularized benchmark.
  arXiv  Detail & Related papers  (2021-10-07T02:36:14Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  We consider a general online optimization problem with multiple budget constraints over a horizon of finite time periods. The objective of the decision maker is to maximize the cumulative reward subject to the budget constraints. This formulation captures a wide range of applications including online linear programming and network revenue management.
  arXiv  Detail & Related papers  (2020-12-13T04:47:37Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  We consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model unknown to the decision maker. We design general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent.
  arXiv  Detail & Related papers  (2020-11-18T18:39:17Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.