PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Constrained Control of Storage Systems via Simplex Disturbance-Action Policies

Kamiar Asgari, Michael J. Neely

arXiv:2609.07690v1eess.SYcs.SY

TL;DR

Online storage control must respect actions constrained by current resource while choosing before adversarial arrivals and costs are revealed. The paper introduces SDAC, a feasible-by-construction policy class, and an online controller with regret guarantees against fixed SDAC benchmarks. It also gives an infinite-memory benchmark result and a minimax lower bound that is tight in its dependence on T.

  • Problem

    The controller must manage a state-dependent action constraint under adversarial arrivals and costs revealed only after acting.

    Source: A. Motivation and Problem Setting · p. 1

  • Method

    SDAC restricts policy parameters to a subprobability simplex, and the online controller updates them while preserving feasibility along the changing trajectory.

    Source: A. Motivation and Problem Setting · p. 1, §VIII · p. 7

  • Results

    The paper establishes regret guarantees against fixed SDAC and infinite-memory SDAC policies, alongside a minimax lower bound tight in its dependence on T.

    Source: §V · p. 5, §VIII · p. 7

  • Takeaways & Limitations

    Infinite-memory SDAC includes feasible fixed-fraction policies, and the framework applies to energy-harvesting battery management and related storage-constrained systems.

    Source: §VIII · p. 7

Abstract

from arXiv · show

We study online control of a scalar storage system with nonnegative adversarial resource arrivals and state-dependent action constraints. The adversarial, time-varying cost depends on both state and action. At each time, the controller selects a feasible action before the current resource arrival and cost are revealed. To handle the coupling between feasibility and online learning, we introduce Simplex Disturbance-Action Control (SDAC), whose policies have $H$ nonnegative parameters summing to at most one. Every fixed SDAC policy is feasible by construction. Our online SDAC controller updates these parameters using entropic online mirror descent while preserving feasibility along the time-varying trajectory. We prove a regret bound of $O\!\left(\sqrt{T\log(H+1)}\right)$ relative to the best fixed SDAC policy and a minimax lower bound showing that the dependence on $T$ is tight. We also introduce infinite-memory SDAC policies, which include every feasible fixed-fraction policy. SDAC policies approximate this class with an error that decreases geometrically with $H$. For a suitable choice $H=\Theta(\log T)$, the resulting regret against infinite-memory SDAC policies is $O\!\left(\sqrt{T\log\log T}\right)$. The framework applies to energy-harvesting batteries and other storage-constrained resource systems.

I. INTRODUCTION

The introduction frames online storage control as balancing current and future resource use while respecting a state-dependent action constraint. It presents SDAC as a feasible-by-construction policy class and develops online regret guarantees for adversarial arrivals and costs.

A. Motivation and Problem Setting

  • Storage controllers must trade off lowering current cost against preserving resource for future decisions while meeting the action constraint at every time.The scalar model uses adversarial arrivals and costs, with the controller choosing before the current arrival and cost are revealed.Source: A. Motivation and Problem Setting · p. 1
  • Unrestricted disturbance-action filters can produce negative actions or actions exceeding available resource, so the storage constraint requires a tailored policy class.Source: A. Motivation and Problem Setting · p. 1

C. Contributions

  • SDAC uses nonnegative filter parameters on a subprobability simplex, with retention-coefficient powers, making every fixed policy feasible and its state and action affine in the parameter.Convex state–action costs are therefore convex in the policy parameter, permitting online convex optimization.Source: A. Motivation and Problem Setting · p. 1
  • The online controller updates SDAC parameters with entropic online mirror descent and achieves regret against fixed SDAC and infinite-memory benchmarks; the latter class includes feasible fixed-fraction policies and admits geometrically decreasing truncation error.For H = Θ(log T), the stated regret bound also holds against the best fixed-fraction policy.Source: C. Contributions · p. 2
  • A minimax lower bound scales as Ω((1−α)^−1√T) near α = 1, while the upper and lower bounds differ by (1−α)^−1/2 in their dependence on 1−α.Closing this gap is left for future work.Source: C. Contributions · p. 2

D. Related Work √

  • Unlike simplex-structured DAC and affine-constraint approaches,, SDAC fixed policies satisfy an action constraint coupled to the current storage state.The introduction also distinguishes its adversarial, state-and-action-dependent costs and pre-arrival decisions from related energy-harvesting settings.Source: D. Related Work √ · p. 2

II. MODEL AND REGRET BENCHMARK

The model is a finite-horizon scalar storage system with bounded nonnegative arrivals, storage loss, and an action limit tied to the current state. The objective is sublinear regret against a fixed policy benchmark while maintaining feasibility at every time.

  • The system starts empty, has retention coefficient α ∈ (0, 1), and receives resource arrivals w_t ∈ [0, 1] as its state evolves.The fraction 1−α of stored resource is lost each period.Source: §II · p. 3
  • At each time the controller chooses a nonnegative action before observing the current arrival or cost, and must satisfy 0 ≤ u_t ≤ αx_t.The arrival and entire cost function are revealed after the action is selected.Source: §II · p. 3
  • The revealed costs are convex in state and action and satisfy Lipschitz and bounded-subgradient assumptions on the feasible domain.These assumptions support the online cost and regret analysis.Source: §II · p. 3
  • The performance objective is sublinear regret against the best fixed SDAC policy chosen in hindsight, with fixed-fraction policies included as a stated comparison class.Source: §II · p. 3

III. SIMPLEX DISTURBANCE-ACTION CONTROL (SDAC)

SDAC replaces unrestricted disturbance-action filters with simplex-constrained policies tailored to storage feasibility. A state decomposition establishes feasibility and convexity properties that support online optimization.

A. From Disturbance-Action Control to SDAC

B. Policies and Structural Properties

C. Approximation of Infinite-Memory SDAC Policies

Infinite-memory SDAC includes feasible fixed-fraction policies, and truncating its parameter sequence yields a horizon-H SDAC policy. The online controller preserves trajectory feasibility while updating its parameters.

C. Approximation of Infinite-Memory SDAC Policies

IV. ONLINE SDAC CONTROLLER

  • The online trajectory is feasible by induction from x_1=0, since 0≤u_t≤αx_t implies x_{t+1}≥w_t≥0.Source: §IV · p. 5

V. REGRET UPPER BOUNDS

The paper establishes regret bounds against fixed SDAC benchmarks and extends the no-regret guarantee to infinite-memory SDAC and fixed-fraction policies. It also gives a minimax lower bound for causal feasible controllers, with a stated mixing-time condition and a gap in the dependence on 1−α.

V. REGRET UPPER BOUNDS

  • Theorem 1 bounds regret against the best fixed SDAC policy under the stated cost assumptions.Source: §V · p. 5
  • The online controller has o(T) regret against the best fixed infinite-memory SDAC policy, with the same bound against the best fixed-fraction policy.Source: §V · p. 5

VI. MINIMAX REGRET LOWER BOUND

  • For every causal feasible controller, a deterministic oblivious arrival-and-cost sequence satisfying the model assumptions gives the minimax lower bound stated in Theorem 2.Source: §VI · p. 5
  • The lower-bound scaling requires T to grow with t_mix(α), and the upper bound's dependence on 1−α is larger by a factor of (1−α)^−1/2.Source: §VI · p. 6

VII. DISCUSSION AND EXTENSIONS

The discussion extends SDAC to retention factors at least one, vector actions, and multiple storage states with diagonal dynamics, while noting boundaries on the resulting policy classes. The conclusion reports regret guarantees and applicability to storage-management settings.

a) Retention α ≥ 1

  • For retention α ≥ 1, the extension writes u_t = kx_t + v_t and filters v_t using powers of α−k, where α−k lies in (0, 1).For fixed k, the comparator is restricted to actions satisfying u_t ≥ kx_t; choosing k in advance or online is left for future work.Source: §VII · p. 6

b) Vector actions and multi-task allocation

  • For vector actions, proportional scaling restores a nominal action whose entries exceed αx_t, and OMD runs over a matrix subprobability simplex.The correction size equals the excess total action under an ℓ1 action-Lipschitz bound.Source: §VII · p. 6

c) Multiple storage states with diagonal dynamics

  • With diagonal multi-storage dynamics, assigning SDAC parameters by storage state yields decoupled constraints and a product of subprobability simplices; cross-coupled systems require further analysis.The online controller clips each nominal action to α_s x_{t,s}; OMD separates by storage state with a sum of negentropy regularizers.Source: §VII · p. 6

VIII. CONCLUSION

  • The conclusion reports a remaining gap between the upper and lower bounds in their dependence on 1−α.The stated conclusion also gives a minimax lower bound and an online-controller upper bound.Source: §VIII · p. 7
  • With H = Θ(log T), the regret guarantee covers the best fixed infinite-memory SDAC policy; the model also applies to energy-harvesting battery management and related storage-constrained settings.The infinite-memory class includes feasible fixed-fraction policies.Source: §VIII · p. 7

APPENDIX A PROOFS FOR SIMPLEX DISTURBANCE-ACTION CONTROL

These proofs establish properties of fixed and infinite-memory SDAC policies, including feasibility, approximation, and convexity of the surrogate cost. They use trajectory recursions and the affine dependence of state-action pairs on policy parameters.

Surrogate-cost properties

  • Affine state-action pairs in the SDAC parameter make the surrogate cost convex, while the coefficient and Lipschitz bounds support a bound on its variation across parameters.The proof invokes the fixed-policy state-action domain D_α and Hölder’s inequality.Source: Appendix A · p. 7

Feasibility and approximation

  • Truncating an infinite-memory SDAC policy preserves its state trajectory over the horizon, allowing the finite-memory feasibility result to establish feasibility of the original policy.The proof sets past arrivals to zero and compares the policy with its truncation.Source: Appendix A · pp. 7–8
  • The approximation proof subtracts the two state recursions, iterates the resulting relation, and applies the Lipschitz condition to bound cost differences.Both policies' state-action pairs lie in D_α.Source: Appendix A · p. 8

APPENDIX B PROOFS FOR THE ONLINE SDAC CONTROLLER

The appendix supports the online controller’s update and clipping steps with properties of negentropy and Bregman projection. It also establishes a closed-form OMD update and positivity of its iterates.

Negentropy properties

  • Negentropy is 1-strongly convex on the subprobability simplex, supporting the OMD analysis.The proof establishes the bound first for positive coordinates and extends it by continuity.Source: Appendix B · pp. 8–9

Action clipping

  • The appendix characterizes action clipping as a Bregman projection onto the parameters compatible with the current state.The projection is defined for each time t.Source: Appendix B · p. 9
  • The compatible-parameter set is compact and convex, and the Bregman projection onto it exists uniquely.The proof uses strict convexity of the divergence and the feasible zero parameter.Source: Appendix B · p. 9

OMD update

  • The OMD update has a closed-form solution obtained from the exponentiated coordinates and normalization by their ℓ1 norm when needed.The update’s iterates remain strictly positive from the stated initialization.Source: Appendix B · p. 9

APPENDIX C PROOFS FOR THE REGRET UPPER BOUNDS

The regret proofs combine OMD bounds on surrogate costs with stability bounds for the changing online trajectory. They then extend the guarantee to infinite-memory and fixed-fraction comparators using truncation and approximation.

Regret against fixed SDAC policies

  • The OMD regret bound for surrogate costs is combined with trajectory stability to obtain the regret bound against fixed SDAC policies.The proof bounds the initial divergence and selects a step size before taking the maximum over comparator parameters.Source: Appendix C · pp. 10–11

Stability of the online trajectory

  • The stability proof bounds state deviation using the one-step OMD movement bound, then bounds action deviation through clipping and cost deviation through Lipschitz continuity.The action deviation is at most α times the state deviation.Source: Appendix C · pp. 10–11

Regret against infinite-memory SDAC

  • For infinite-memory comparators, the proof truncates the parameter sequence, combines the finite-memory regret and approximation bounds, and chooses H_T proportional to log T.The resulting bound is O(log log T) in the proof’s stated asymptotic expression for fixed α, L_x, and L_u.Source: Appendix C · p. 11

Regret against fixed-fraction policies

  • Because every fixed-fraction policy belongs to the infinite-memory class, the infinite-memory guarantee also yields a fixed-fraction regret bound.The proof uses m(k) ∈ M∞ for every k ∈ [0, α].Source: Appendix C · p. 11

APPENDIX D PROOFS FOR THE MINIMAX REGRET LOWER BOUND

The proof establishes a minimax regret lower bound by randomizing signed costs against any causal feasible controller, then fixing a deterministic oblivious sequence. It uses two fixed SDAC policies and applies the lower-bound argument when enough rounds remain after the mixing horizon.

APPENDIX D PROOFS FOR THE MINIMAX REGRET LOWER BOUND

  • Rademacher-signed affine costs are convex, satisfy the required subgradient bounds, and produce an admissible sequence in every realization.The cost is c_t(x,u)=ξ_t(L_x x−L_u u), with gradient ξ_t(L_x,−L_u).Source: Appendix D · p. 12
  • The proof compares fixed SDAC parameters m(0)=0 and m(1)=e1; from t≥2, m(1) has action α and state 1.The m(1) state remains 1 under the stated dynamics.Source: Appendix D · p. 12
  • Averaging over randomized signs yields a deterministic oblivious sequence with expected regret at least the derived lower bound.The expectation is over the controller’s randomization.Source: Appendix D · p. 12
  • When T≥2t_mix(α)+2, at least T/2 indices remain for applying Theorem 2 in the corollary proof.The counted indices run from t_mix(α)+2 through T.Source: Appendix D · p. 12
Loading 2609.07690v1…