Optimally Pacing Budget Spending and Learning

1 Introduction

• Budget depletion forces the learner to stop, while switching among individually feasible experts can violate the budget; the paper asks how to tightly characterize regret under this coupling.In online resource allocation, current rewards and costs are known before the decision, but future opportunities remain unknown.Source: §1 · pp. 1–2

1.1 A Toy Example: Alternating Online Knapsack

• For alternating red and blue balls, the paper gives a constant-regret algorithm by controlling reward regret and spending discrepancy against the same expert mixture.For alternating blocks of D balls, the stated ORA regret is O(D), improving on the cited EMD-based O(T) bound when D = o(T).Source: §1.1 · pp. 2–3

1.2 Our Results

• The Kolmogorov distance measures the largest cumulative-spending difference over any prefix; against D-pacing experts, the paper gives O(D√log F) regret in ORA.The paper reports that its guarantees are optimal up to constant factors, with matching lower bounds in ORA and OLRC.Source: §1.2 · pp. 3–4

Online Resource Allocation (ORA) & Online Learning with Resource Constraints (OLRC)

• The approach jointly optimizes primal and dual variables, unlike the cited alternating primal-dual template, and the paper distinguishes hard-budget feasibility from long-term constraint-violation objectives.The guarantees are extended to sampled play, subpacing experts, and multiple resources.Source: Online Resource Allocation (ORA) &… · pp. 4–5, §1.2 · p. 4

1.4 Comparisons with Prior Work

• For full information, the paper reports O(D√log F + √T log F) regret at Kolmogorov radius D, potentially smaller when maximum cumulative-spending deviation is much smaller than EMD.It states that the guarantee recovers the prior EMD dependence up to a √log F factor.Source: §1.4 · p. 5
• The benchmark allows dynamic strategies whose spending approximates a plan in Kolmogorov distance, rather than requiring strict per-round adherence as in the compared work.The paper notes that even-round spending can remain Kolmogorov-close to uniform pacing despite constant overspending across Ω(T) rounds.Source: §1.4 · pp. 5–6

2.1 Problem Setup

• In ORA, the learner sees current reward and cost vectors before choosing; in OLRC, it chooses before seeing them, with full-information and bandit variants.The setup includes multiple resources, bounded rewards and costs, expert advice, and hard budget constraints.Source: §2.1 · p. 6
• Fractional play gives deterministic rewards and costs for a distribution over actions, while sampled play draws an action and incurs its realized reward and costs.The main analysis focuses on fractional play and full-information feedback; sampled play is also considered.Source: §2.1 · p. 6

2.2 Subpacing Experts and New Regret Benchmark

• The benchmark restricts comparison to experts whose spending patterns are D-subpacing relative to a prespecified baseline.The paper defines the benchmark using the set F(D, b) of such experts.Source: §2.2 · p. 7
• Kolmogorov distance measures the largest absolute difference between two cumulative spending patterns over any prefix of the horizon.The paper uses this distance to define pacing relative to a baseline.Source: §2.2 · p. 7

3.2 An Optimal Algorithm for the Alternating Red and Blue Balls Problem

• Queueing the j-th ball of each monochromatic block into its own subproblem reduces the D-block instance to D unit-block problems.A constant regret and pacing guarantee for each queue yields the O(D) guarantees for the original instance.Source: §3.2 · p. 8, end · p. 11
• The learner observes the current ball’s reward before choosing its fraction, but has no information about future rewards; this feedback suffices for constant regret and pacing in the unit-block setting.The learner has budget T/2 and competes with experts that select all red or all blue balls.Source: §3.2 · pp. 8–9, §3.1 · p. 8
• The algorithm aligns regret and spending deviation to the same expert mixture, so choosing that mixture’s prescribed spending makes both terms vanish simultaneously.Dual variables price the objectives in a minmax game, and the resource-deviation term is measured against the mixture’s cumulative spending.Source: §3.2 · p. 9
• The per-round minmax algorithm is horizon-agnostic, and its regret and pacing guarantees do not depend on T.The warm-up presents a pre-decision-feedback setting with two experts, two actions, one resource, fractional play, and a perfectly pacing baseline.Source: §3 · p. 8, §3.2 · p. 10

end

• O(D) regret and O(D)-pacing are achieved for alternating D-length color blocks, matching the lower-bound scale because the experts’ spending patterns are Θ(D) apart.For D=1, the theorem gives constant regret and constant pacing; exact budget feasibility can be obtained by truncation with only an additional O(1) in each guarantee.Source: §3.2 · p. 8, end · pp. 10–11

4.1 Notation

• The setup extends the algorithm to finite expert classes and multiple resources, initially assuming deterministic fractional play and deferring sampled actions to Section 5.3.The learner selects a distribution over actions and receives deterministic reward and costs under this assumption.Source: §4 · p. 11
• A controller selects a distribution over experts, which induces the action distribution; its resource penalty measures spending deviation from an expert mixture.The potential combines shifted entropy regularizers over expert and resource distributions with this resource penalty.Source: §4.1 · p. 12

4.2 Key Curvature Lemma

• With appropriately chosen regularization, the potential is jointly concave in the expert and resource distributions, a curvature result that relies on experts’ pacing property.The analysis uses shifted entropies for strong concavity, while pacing controls the nonlinear reward and resource-penalty term.Source: §4.2 · p. 13

4.3 Core Algorithms

• ORA chooses an expert mixture minimizing the worst-case potential using current rewards and costs; OLRC lacks that feedback and instead uses FTRL, with stability controlling potential increments.The ORA decision rule is justified by the potential’s affine dependence on the mixture and its joint concavity in the expert and resource distributions.Source: §4.3 · pp. 14–15

4.4 Completing the Analysis

• Regret is bounded by ρx log F + ρv log(m + 1) plus a tail term with pre-decision feedback, and adds T(1 + λmax)^2 without it.Both algorithms are fractionally budget feasible and the bounds hold simultaneously for every D-pacing expert.Source: §4.3 · p. 14, §4.4 · p. 17
• When a resource triggers a hard stop, the analysis bounds regret by the prefix stability and regularization terms plus a suffix residual Tail.The resulting bound is Stabτ + ρx log F + ρv log(m + 1) + Tail.Source: §4.4 · p. 18
• With pre-decision feedback, both algorithms are budget feasible via fractional play, and for every expert f simultaneously the bound is T ≤ ρx log F + ρv log(m + 1) + Tail.Source: §4.4 · p. 18

Optimizing the regularization parameters gives

• The parameter optimization uses ρv = 4D²η,∞/ρx and minimizes the resulting expressions separately for pre-decision and no-pre-decision feedback.The supplied passages do not include the complete optimized expressions.Source: Optimizing the regularization… · p. 18

5 Extensions

• A spending path is D-subpacing exactly when it overspends the baseline by at most D on any prefix and by at most 2D on any interval; the class is downward closed.These bounds enable converting a subpacing path into a pacing path by raising spending when it underspends too far.Source: §5 · p. 19

5.1 Extension 1: Subpacing Experts

• Artificially raising subpacing experts’ costs yields paced instances, allowing the core algorithms to retain fractional budget feasibility and regret guarantees against those experts.The theorem also preserves subpacing guarantees relative to the original costs when the algorithms are subpacing with respect to artificial costs.Source: §5.1 · pp. 20–21

5.2 Extension 2: Subpacing Algorithm

• The learner is made subpacing by playing the null action on unsafe rounds and lowering the baseline when underspending threatens a later interval overspend.A hard stop also makes the learner play the null action forever once activated.Source: §5.2 · p. 22, end · p. 23

end

• With paced experts, the fractional cost path satisfies every hard budget and is Wi-subpacing in each resource, while both feedback regimes provide regret guarantees against every expert.The theorem specifies separate regret bounds for pre-decision and without pre-decision feedback; the supplied excerpts do not expose the complete formulas.Source: end · pp. 23–24
• The actual fractional cost path is Wi-subpacing, and the hard stop ensures fractional budget feasibility.Source: end · p. 25
• Raised-cost accounting preserves feasibility and Wi-subpacing guarantees for true fractional costs by dominating them and transferring the subpacing guarantee.Source: end · p. 30

5.3 Extension 3: sampled play with pathwise budgets and high-probability guarantees

• For sampled play, martingale concentration yields high-probability regret guarantees, and composing with Extension 2 also gives high-probability subpacing.Source: §5.3 · p. 30
• A realized hard stop truncates sampled play when realized costs approach a budget, without changing the fractional controller’s proposal or state.Source: §5.3 · p. 30
• Lemma 5.6 states that, with probability at least 1 −δ, its guarantee holds simultaneously for every prefix s ≤T and every resource i ∈[m].Source: §5.3 · p. 31
• Every hard budget is satisfied on every realization, and with probability at least 1 − δ regret guarantees hold simultaneously for every expert.The theorem states this for the chosen deterministic fractional regret bound.Source: §5.3 · p. 32
• With Extension 2, the realized resource-i cost path is (Wi + Γi(δ))-subpacing for every resource i.This guarantee holds on the same event as the simultaneous regret guarantee.Source: §5.3 · p. 33
• Sampling increases the fractional regret bound by at most Γr(δ) + maxi∈[m] ηiΓi(δ).The bound applies with probability at least 1 − δ when composing the extensions.Source: §5.3 · p. 33
• The composition raises each Di-subpacing expert to a virtual Di-paced expert, applies Extension 2, then samples with a realized hard stop.Extension 1 does not change parameters entering the regret bound; downward closure transfers budget feasibility and learner subpacing to the true fractional path.Source: §5.3 · p. 33

6 Lower Bounds

• The spending-pattern lower bound applies regardless of pre-decision feedback, including in online resource allocation.The section states that regret must depend on Kolmogorov distance even when current rewards and costs are visible.Source: §6 · p. 33
• A spending-pattern gap of Kolmogorov distance D forces Ω(D) regret, and a constructed D-pacing instance forces Ω(D√log F) regret for F experts.The first bound uses two experts and arbitrary spending patterns; the second uses a specific baseline and holds even with current-round feedback.Source: §6 · pp. 33–34
• Across log F windows of length 2D, the construction repeats a spend-or-save dilemma; with rewards following an unbiased random walk of step size ε = 1/√log F, any algorithm’s regret is Ω(D√log F).Experts choose one of two actions in each window and are D-pacing against the uniform pacing spending pattern. With step size ε = Θ(1/√log F), the walk does not terminate after 2 log F steps with constant probability.Source: §6 · pp. 34–35
• Ω(max{D, T^1/2} · √log F) regret is unavoidable for budget-feasible fractional-play learners when T ≥ 2D log F.The bound holds for some budget, baseline spending pattern, D-pacing expert set, and reward-cost sequence.Source: §6 · p. 35

• The one-resource guarantees assume fixed constants α and V, with D ≥1, F ≥2, and T ≥1.B denotes the budget.Source: A Summary of Guarantees for One Resource · p. 37
• The notation eOT suppresses only polylogarithmic factors in T, so dependence on F remains explicit.Source: A Summary of Guarantees for One Resource · p. 37

Fractional play, D-pacing/subpacing experts

• Fractional play by Algorithms 2 and 3 satisfies fractional budget feasibility and gives simultaneous guarantees for every pacing or subpacing expert, with and without pre-decision feedback.The same rates are stated for D-pacing and D-subpacing experts.Source: A Summary of Guarantees for One Resource · p. 37

Fractional play, subpacing learning algorithm

• Algorithms 2 and 3 with Extension 2 satisfy fractional budget feasibility for the subpacing learning algorithm, under both pre-decision and without pre-decision feedback.The fractional spending path can be made W-subpacing.Source: A Summary of Guarantees for One Resource · p. 37

Sampled play under full-information feedback

• Sampled play under full-information feedback satisfies the budget constraint and, with probability at least 1 −δ, adds at most the stated deviation to fractional regret bounds.When the fractional path is W-subpacing, the sampled path has the same W plus a deviation of this order.Source: A Summary of Guarantees for One Resource · p. 38