Logarithmic Regret for Single-Sample Nonstationary Online Linear Programming

We study nonstationary online linear programming when learning data are exceptionally sparse: before the horizon, the decision-maker receives one independent sample from each period's unknown distribution, while online reward--consumption pairs are independent but non-identically distributed. We prove that the single-sample dual re-solving policy of Xu et al. attains $O(\log n)$ regret in the large-resource regime. This improves the previous $O((\log n)^2)$ guarantee for the same policy and matches the logarithmic order already unavoidable in stationary continuous-valuation OLP. The decisive step is a non-i.i.d. empirical-process inequality for the vector threshold class $p\mapsto a\mathbf 1\{u>a^\top p\}$: every suffix of length $N$ has uniform second moment $O(1/N)$. Local strong convexity converts this estimate into $O(1/N)$ mean-square dual convergence. A delta-path argument then controls the remaining-resource process, and a stopped threshold-loss decomposition turns squared price error into harmonic cumulative regret. Thus one heterogeneous forecast sample per future period suffices for an order-optimal logarithmic rate under smooth local dual geometry.