PaperlayerView exact revision on arXiv

Source-linked AI summary

A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

Menglong Li, Jiawei Zhang

arXiv:2609.05895v1cs.LG

TL;DR

Finite-horizon resource allocation with unknown request probabilities raises the question of whether constant regret requires solving a fluid LP or assuming nondegeneracy. The paper uses a primal first-order policy that updates the current request type’s action coordinates, and proves O(1) expected additive regret against the exact hindsight optimum.

  • Problem

    The paper asks whether online resource allocation can achieve low regret without relying on fluid-LP nondegeneracy, which may fail under ties, redundant resources, or nonunique shadow prices.

    Source: §1 · pp. 1–2

  • Method

    A primal policy learns unknown arrival probabilities and performs one gradient ascent update per period on the current request type’s action coordinates, without solving a fluid LP.

    Source: §1 · p. 1

  • Results

    O(1) expected additive regret is achieved relative to the exact hindsight optimum under i.i.d. arrivals with unknown probabilities.

    Source: §1 · p. 3, §6 · p. 22

  • Takeaways & Limitations

    The guarantee needs neither a linear-program solve nor a nondegeneracy assumption on the fluid LP.

    Source: §6 · p. 22

    The regret constant is horizon-independent but may depend on problem dimensions, rewards, resource consumptions, the penalty parameter, and minimum arrival probability.

    Source: §1 · p. 3

Abstract

from arXiv · show

We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. The arrival types are independent and identically distributed, but their probabilities are unknown. 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. The policy achieves $O(1)$ expected additive regret relative to the hindsight optimum, with a bound independent of the horizon $T$. It does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.

1 Introduction

The paper studies finite-horizon resource allocation with unknown i.i.d. request probabilities and asks whether constant regret can be achieved without solving a fluid linear program. It introduces a primal first-order policy with horizon-independent expected regret, even when the fluid LP is degenerate.

1 Introduction

  • Nondegeneracy may fail with ties, redundant resources, or nonunique shadow prices, and small capacity or demand changes can change the optimal basis.The introduction motivates regret bounds that do not deteriorate near degeneracy.Source: §1 · p. 2
  • Constant-regret approaches described in the introduction still solve fluid LPs, while this paper asks whether first-order updates can eliminate that optimization step.The passage notes that repeated LP solves can be costly in time-sensitive applications.Source: §1 · p. 2
  • One gradient ascent update per period changes only the action coordinates for the observed request type, using matrix-vector operations and simplex projections.The update belongs to a primal first-order learning policy for finite-action online resource allocation.Source: §1 · pp. 2–3
  • O(1) expected additive regret relative to the exact hindsight optimum holds without a nondegeneracy assumption, including when action ties or changes of optimal basis occur.The guarantee applies when arrival probabilities are unknown; the penalty parameter can be selected using observed arrivals.Source: §1 · p. 3
  • A high-probability bound controls one-period loss by a constant multiple of squared distance to that period’s penalized optimal solution set.Updating only the current type’s coordinates suffices for bounded total expected loss even as the penalized problem changes over time.Source: §1 · p. 3
  • The guarantee is horizon-independent, not dimension-free: its constant may depend on resources, types, actions, rewards, consumptions, the penalty parameter, and minimum arrival probability.The paper notes that worst-case regret can be exponential in the number of resources.Source: §1 · p. 3

2 Model and problem formulation

The model has finite request types and type-dependent action menus, with resource capacities growing proportionally to the horizon. It evaluates online policies against a hindsight optimum and uses fluid LP relaxations to represent feasible allocations.

2 Model and problem formulation

  • The initial capacity is B_T = Tb, and each period brings an i.i.d. request type from a finite set with unknown probabilities.The type-dependent action menu includes rejection, which earns zero reward and consumes no resources.Source: §2 · p. 3
  • Each chosen action earns a reward and consumes a resource vector; decisions must satisfy capacity constraints on every sample path.The decision maker observes the current type and remaining capacity before acting.Source: §2 · pp. 3–4
  • Expected additive regret compares a policy’s expected reward with the expected reward of the hindsight optimum, which observes the full arrival sequence.For each realized sequence, the hindsight optimum selects an optimal feasible allocation.Source: §2 · p. 4
  • Replacing realized type demands with their expectations yields a fluid relaxation, normalized by dividing capacities, demands, and allocation variables by T.In the normalized relaxation, x_ja represents the fraction of periods in which type j is assigned to action a.Source: §2 · pp. 4–5

3 Algorithm and main result

The policy uses one type-specific gradient update per period on a quadratically penalized fluid relaxation, and achieves constant regret without solving a fluid LP. Its guarantees include a fixed-parameter version requiring a positive lower bound on p_min and an adaptive version that does not.

3 Algorithm and main result

  • The policy has constant regret; its fixed-parameter guarantee needs a positive lower bound on p_min, but not the arrival probabilities themselves.The regret-bound constant depends on the action menus, resource-consumption matrix, rewards, and 1/p_min.Source: §3 · pp. 5, 7
  • Each period, the policy applies gradient ascent to a quadratically penalized fluid relaxation and selects the action with the largest updated coordinate for the observed type.Only the current type's action coordinates are updated.Source: §3 · pp. 5, 7
  • As the arrival-probability estimate changes, the policy rescales the preceding solution while keeping each type's action-allocation fractions unchanged.After observing the current type, it updates that type's coordinates and chooses the action with the largest updated coordinate.Source: §3 · p. 6
  • An adaptive choice of penalty parameter and step size also yields a regret bound independent of T without requiring a known positive lower bound on p_min.The bound's constant may still depend on 1/p_min.Source: §3 · p. 8

4 Preliminary analysis

The analysis relates the penalized problem to fluid LPs with expanded capacities, then uses sensitivity bounds for optimal solution sets as capacities and demand change. These bounds do not require nondegeneracy.

4 Preliminary analysis

  • The preliminary analysis represents the penalized problem through a fluid LP with expanded capacity and uses sensitivity bounds to compare optimal solutions.It decomposes the optimization gap between the penalized problem and fluid LPs under different capacity and demand vectors.Source: §4 · p. 8

4.1 The optimization gap

  • The quadratic resource-overuse penalty is analyzed through capacity expansion, with bounds enabling comparison to a fluid LP whose capacity is close to c.The penalty permits consumption above c but charges for the excess.Source: §4.1 · pp. 8–9

4.2 Sensitivity of optimal solutions

  • Sensitivity bounds compare entire optimal-solution sets and remain valid when a solution set is a face or an optimal basis changes as c and η change.The bounds do not require nondegeneracy.Source: §4.2 · p. 10

5 Regret analysis

The regret analysis bounds total regret through expected one-period losses, relating them to distance from the current fluid-LP solution set. It combines quadratic growth, contraction of the coordinate update, and distance, loss, and concentration bounds to establish horizon-independent distance and constant expected regret.

5 Regret analysis

  • The proof reduces regret to expected one-period losses, controlling periods with inaccurate arrival distributions using a uniform loss bound and concentration inequalities.When estimated and remaining-request distributions are close to the true arrivals, the loss is bounded by a constant times squared distance to the current penalized problem’s optimal solution set.Source: §5 · p. 10

5.1 One-period loss

  • One-period losses are fluid-LP value decreases after fixing the current action, net of reward, and their sum gives a sample-path bound on regret.Taking expectations reduces the proof to bounding the sum of these losses.Source: §5.1 · p. 11

5.2 Bounding the one-period loss by distance to the optimal solution set

  • When arrival estimates are close to the true probabilities, one-period loss is zero for sufficiently small distance to the optimal solution set and uniformly bounded otherwise.The analysis applies this loss control on the event that the estimated and remaining-request distributions are close.Source: §5.2 · pp. 12–13

5.3 Bounding the distance to the optimal solution set

  • A quadratic-growth bound and a weighted contraction of the coordinate update control distance to the optimal solution set, even as the resource target and estimated distribution change over time.The resulting sum of expected squared distances is bounded by a constant independent of T; sensitivity bounds control changes in the optimal solution set.Source: §5 · p. 10, §5.3 · pp. 14, 15, 18
  • The cumulative squared distance to the optimal solution set is bounded by a finite constant independent of T.After capping resource-target components at maximum possible consumption, the distance between targets is at most 2 ∥w̄∥2 /(s −1).Source: §5.3 · pp. 18–20

5.4 Proof of Theorem 3.1

  • In completing the proof, the final s̄ periods contribute at most s̄H2(1 + ∥r∥2), giving an explicit upper bound on their total contribution.Source: §5.4 · p. 21
  • The expected regret is bounded by a finite constant C independent of the horizon T.The proof combines per-period loss bounds, concentration bounds for complementary events, and a bound on the contribution of the final periods.Source: §5.4 · p. 21

6 Concluding Remarks

The paper concludes that its first-order policy achieves constant expected regret without solving a linear program or assuming nondegeneracy. It identifies extensions beyond the finite-support model as open questions.

6 Concluding Remarks

  • The fixed-penalty and adaptive policies both achieve O(1) expected additive regret without solving a linear program or assuming fluid-LP nondegeneracy.The regret is relative to the hindsight optimum.Source: §6 · p. 22
  • When each request type has relatively few actions, updating only that type’s coordinates can make each period’s computation much smaller than a full gradient update.The quantities needed for the update can be maintained without computing other coordinates.Source: §6 · p. 22
  • Whether first-order policies can attain constant expected regret without LP solves or nondegeneracy in settings such as nonstationary arrivals and delayed decisions remains open.The paper also lists uncertainty about the horizon and other allocation settings as extensions.Source: §6 · p. 22
  • For continuous-support inputs, the cited regret results require regularity and nondegeneracy conditions or concern particular models; the paper’s model assumes finite-support rewards and resource-consumption vectors.The authors leave open whether comparable bounds in continuous-support models can be achieved using only first-order updates without LP solves.Source: §6 · p. 22

A.1 Proof of Lemma 4.1

The proof relates the penalized allocation problem to a fluid LP with expanded capacities. It establishes that optimal allocations in one formulation correspond to optimal allocations in the other.

A.1 Proof of Lemma 4.1

  • For fixed y, the smallest feasible expansion is [Wy − c]+, while fixing an expansion and optimizing over y gives G_c,η(ξ); maximizing either formulation establishes the stated equivalence.The proof substitutes the smallest feasible expansion into the objective, then maximizes over allocations.Source: §A.1 · p. 23
  • If y is optimal in S(c, η), uniqueness of the maximizing expansion forces ξ_y = ξ*, so y maximizes the fluid LP with capacity c + ξ*.The proof first shows (y, ξ_y) is an optimal pair.Source: §A.1 · p. 23
  • Conversely, if y maximizes the fluid LP with capacity c + ξ*, then the proof establishes that y belongs to S(c, η).It uses ξ_y ≤ ξ* coordinatewise to complete the argument.Source: §A.1 · p. 23

A.2 Proof of Lemma 4.4

The proof uses a dual formulation to relate optimal capacity expansion to fluid-LP solutions. Strong convexity and LP stability then support bounds on changes in the optimal solution set.

A.2 Proof of Lemma 4.4

  • The proof bounds changes in λ*, translates that bound into expansion stability, and applies Lemma 4.2 to fluid LPs with expanded capacities.The optimal sets S(c, η) are identified with fluid-LP optimal sets at those expanded capacities.Source: §A.2 · pp. 24, 26
  • For each type, h_j(λ) is the largest reward of an action after charging resource price λ.Source: §A.2 · p. 24
  • Strong convexity gives Q_c,η a unique minimizer λ*, and minimax equality with LP duality connects Q_c,η to the expansion objective Ψ_c,η.The proof applies Sion’s minimax theorem before using LP duality.Source: §A.2 · pp. 24–25
  • The saddle point has expansion ξ* = κλ*, so the optimal dual price determines the maximizing capacity expansion.For fixed λ, the maximizing expansion is unique.Source: §A.2 · p. 25

B.1 Proof of Lemma 5.2

The proof uses expressions in (5.2) and a comparison of maximizers over perturbed feasible sets to establish the lemma’s parts.

B.1 Proof of Lemma 5.2

  • Lemma 4.2 supplies a maximizer over the perturbed feasible set to compare with the original maximizer.The original maximizer is y0; the comparison solution y1 maximizes over P(c−hwja, η −hej).Source: §B.1 · p. 26
  • Part (i) follows directly from the second expression in (5.2).Source: §B.1 · p. 26
  • The coordinate vector eja is indexed by the action coordinate (j, a).Source: §B.1 · p. 26
  • Part (ii) follows because the normalized loss is nonnegative.The proof obtains this from the second expression in (5.2).Source: §B.1 · p. 26

C Unknown minimum arrival probability

The appendix adapts the regret proof to an unknown minimum arrival probability by choosing a penalty from arrival estimates. It bounds the resulting solution changes and distance accumulation, yielding a regret bound independent of T.

C Unknown minimum arrival probability

  • The penalty and gradient update depend only on past arrivals, allowing the proof to bound solution-set changes as the penalty varies.The argument also accounts for changes in capacity and arrival estimates.Source: C Unknown minimum arrival probability · pp. 26, 29
  • The penalty is chosen from the smallest estimated arrival probability, and accurate estimates keep it in a fixed positive interval.The minimum true arrival probability is used only in the proof; inaccurate estimates are handled using feasible-set diameter bounds and concentration.Source: C Unknown minimum arrival probability · pp. 26–27
  • Arrival-estimation errors become sufficiently unlikely after a number of periods independent of T, with geometric decay thereafter.Source: C Unknown minimum arrival probability · p. 27
  • The contraction argument and rescaling estimates yield a sum of expected squared distances bounded independently of T.The proof conditions on the past when applying the contraction bound.Source: C Unknown minimum arrival probability · pp. 29–30
  • A constant independent of T bounds the regret, including the contribution of the final periods.The proof combines this with the bounded regret terms for the preceding periods.Source: C Unknown minimum arrival probability · p. 30
Loading 2609.05895v1…