Optimal Regret for Online Storage Control via Cumulative Policies
Abstract
We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves O(√T) regret against the best fixed infinite-memory policy in this class, using O(log T) memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing τ=(1−α)−1, the minimax expected regret is Θ(√Tmin{T,τ}3/2) for every finite-memory simplex policy class and its infinite-memory extension, when α∈[1/2,1), T≥4, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.
Related
- Regret-Optimal Linear-Quadratic Control under Distributional Drift
- Optimal long-run control of endemic infections: bang-bang threshold policies in a stochastic SIS model
- Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
- Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
- Optimality of Threshold Policies for Heat Storage Optimization and a Policy Gradient Algorithm
BibTeX
@misc{asgari2026optimal,
title = {{Optimal Regret for Online Storage Control via Cumulative Policies}},
author = {Kamiar Asgari and Michael J. Neely},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21262},
eprint = {2609.21262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21262},
}
RIS
TY - UNPB
TI - Optimal Regret for Online Storage Control via Cumulative Policies
AU - Kamiar Asgari
AU - Michael J. Neely
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21262
UR - https://arxiv.org/abs/2609.21262
AB - We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves O(√T) regret against the best fixed infinite-memory policy in this class, using O(log T) memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing τ=(1−α)^−1, the minimax expected regret is Θ(√Tmin{T,τ}^3/2) for every finite-memory simplex policy class and its infinite-memory extension, when α∈[1/2,1), T≥4, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.
ER -