The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

Santiago Balseiro; Haihao Lu; Vahab Mirrokni

Source-linked AI summary

The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

Santiago Balseiro, Haihao Lu, Vahab Mirrokni

arXiv:2011.10124v3Nov 18, 2020cs.DScs.LGmath.OC

TL;DR

The paper addresses online allocation of requests and develops algorithms for settings where the input model is unknown. The algorithms attain O(T^1/2) regret for an unknown distribution, while their competitive ratio is not optimal when the problem has more structure.

Problem
Online allocation of requests is a central problem in revenue management and online advertising.
Source: §1 · p. 1
Method
The paper designs fast, robust algorithms for generic online allocation inputs without requiring knowledge of the input model.
Source: §1 · p. 2
Results
The algorithms attain O(T^1/2) regret for an unknown distribution and a fixed competitive ratio.
Source: §1.1 · pp. 3–4
Takeaways & Limitations
A single algorithmic approach is designed to perform well across input models without knowing which model applies.
Source: §1 · p. 2
The competitive ratio is not optimal when the problem has more structure.
Source: §6.1 · p. 26

Abstract

from arXiv · show

Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various non-stationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover the dual sub-gradient descent and dual multiplicative weights update algorithm. The resulting algorithms are simple, fast, and do not require convexity in the revenue function, consumption function and action space, in contrast to existing methods for online allocation problems. We discuss applications to network revenue management, online bidding in repeated auctions with budget constraints, online proportional matching with high entropy, and personalized assortment optimization with limited inventory.

1 Introduction

The paper studies finite-horizon online allocation with resource constraints when request rewards and resource consumption are generated by an unknown input model. It develops simple dual-space algorithms for potentially non-convex settings, with guarantees for stochastic and adversarial inputs.

1.1 Main Contributions

The framework maintains per-resource dual multipliers via online mirror descent; suitable reference functions recover dual sub-gradient descent and dual multiplicative weights.Actions use estimated dual variables as proxies for the opportunity cost of resource consumption.Source: §1.1 · pp. 2–3
The framework supports non-concave rewards, nonlinear consumption, and integral actions, while tolerating noise and corruptions in observations.It requires that the single-period Lagrangian problem be efficiently solvable.Source: §1.1 · p. 3
For unknown i.i.d. inputs, the algorithms achieve O(T^1/2) regret, the optimal order under the paper’s minimal assumptions.The paper pairs this upper bound with an Ω(T^1/2) lower bound.Source: §1.1 · pp. 3–4
Against adversarial requests, the algorithms attain a fixed competitive ratio, and no algorithm can improve it without further assumptions.The paper states that the ratio is tight.Source: §1.1 · p. 4
For non-stationary inputs, the algorithms achieve ˜O(T^1/2) regret when inputs are ergodic, O(T^1/2) under seasonality, and vanishing regret with o(T) corruptions.Source: §1.1 · p. 4
A self-correcting update prevents early resource depletion on every sample path, regardless of the input model.The algorithms target constant resource consumption per period so resources last through the horizon.Source: §1.1 · p. 4
The paper applies the algorithms to online linear programming, budgeted repeated-auction bidding, high-entropy online matching, and personalized assortment with limited inventory.It reports new results or simpler, more efficient implementations in these applications.Source: §1.1 · p. 4

1.2 Related Work

Early stochastic-input work focused on linear rewards and consumption, including the random permutation model; Devanur and Hayes (2009) study AdWords.Source: §1.2 · p. 5
The proposed class handles potentially non-convex reward and resource-consumption functions, with similar regret guarantees and simpler updates that need neither large linear programs nor benchmark-value estimates.The algorithms are presented as extending prior dual-based work to general online allocation problems.Source: §1.2 · p. 5
Each iteration can be computed in linear time, without solving large convex optimization problems.The passage places the proposed algorithms in the line of work seeking simple algorithms that avoid large programs.Source: §1.2 · p. 6
For adversarial inputs, the algorithms provide parametric competitive ratios without free disposal, and their bounds are asymptotically optimal for the general allocation setting studied.The competitive ratio depends on resource scarcity; the bounds need not be tight for the special-case AdWords problem.Source: §1.2 · pp. 6–7
For stochastic inputs, the algorithms are asymptotically optimal, while their adversarial competitive ratio is data-dependent and relies on the consumption-budget ratio.This data dependence distinguishes the guarantee from a constant competitive ratio independent of model data.Source: §1.2 · p. 7
The algorithms are asymptotically optimal for ergodic processes and do not rely on forecasting.The passage contrasts this scope with prior work on processes with drift and forecast-based algorithms.Source: §1.2 · p. 7

2 Problem Formulation and Algorithm

This section formulates online allocation with potentially nonconvex rewards, consumptions, and action sets, and introduces a dual mirror descent algorithm whose dual updates price scarce resources while primal decisions remain feasible. It specifies reference-function choices that recover familiar dual updates and states assumptions allowing non-concave rewards, non-convex consumption functions, and non-convex or integral feasible sets.

2 Problem Formulation and Algorithm

The finite-horizon allocation problem allows non-concave rewards, nonlinear resource consumption, and potentially non-convex or integral action sets.Each request offers an action that earns reward and consumes resources, subject to cumulative resource constraints.Source: §2 · p. 8
The paper also states that its results extend to stochastic rewards and resource consumption given an action, and discusses incorporating stochastic horizons.Source: §2 · p. 8
The algorithm is designed to perform well across input models without knowing in advance which model generates requests.The stated goal is to satisfy resource constraints while achieving good performance under different input models.Source: §2 · p. 9
The framework distinguishes unknown i.i.d. inputs, arbitrary adversarial inputs, and non-stationary stochastic inputs, including ergodic, periodic, and adversarially corrupted i.i.d. processes.For i.i.d. inputs, performance is measured by regret; for adversarial inputs, it is measured by an asymptotic competitive ratio.Source: §2 · pp. 9–10

2.1 The Dual Problem

The Lagrangian dual function upper-bounds the offline optimum by weak duality, but strong duality may fail because rewards, consumptions, or action sets can be non-convex.The passage notes that the primal-dual gap of the offline separable non-convex problem is bounded independently of the number of requests.Source: §2.1 · p. 10

2.2 Algorithm

At each request, the algorithm selects an opportunity-cost-adjusted reward-maximizing action, takes it if feasible or otherwise takes a void action, then updates dual variables by mirror descent.The update uses a dual subgradient derived from resource consumption and the per-period resource allowance.Source: §2.2 · pp. 11–12
The mirror descent step penalizes movement from the incumbent dual solution using Bregman divergence, with dual variables serving as resource prices for primal decisions.The update takes a step using a chosen step-size and reference function.Source: §2.2 · p. 12
The analysis extends to other online linear optimization updates, and approximate primal solutions suffice with their error added to the regret bound.The algorithm is efficiently implementable when the primal problem is simple to solve; the passage notes many applications admit closed-form or linear-time solutions.Source: §2.2 · p. 12
Selecting the reference function recovers multiplicative weights or online sub-gradient descent; an entropy-type choice gives the former.The section also gives a projection-based update for the latter.Source: §2.2 · p. 12

2.3 General Assumptions

The analysis uses the ℓ∞ norm for primal resource constraints and the ℓ1 norm for the dual space, making its parameters dimension independent.The same dependence on the number of resources is available with primal ℓp and dual ℓq norms when 1/p + 1/q = 1 and p ∈ [2, ∞].Source: §2.3 · p. 13
The setup requires 0 ∈ X, nonnegative bounded resource consumption, and an optimal solution to (3), while approximately optimal solutions also preserve the results.The assumptions on requests include upper bounds on reward and resource consumption, which appear in performance bounds but are not needed to run the algorithm.Source: §2.3 · p. 13
The assumptions allow non-concave rewards, non-convex resource consumption functions, and feasible sets that are non-convex or even integral.This contrasts with prior literature, according to the passage.Source: §2.3 · p. 13
The reference function must be differentiable or essentially smooth and σ-strongly convex in the ℓ1 norm; the stated assumptions ensure the projection step admits a solution.Strong convexity is identified as a standard assumption for mirror descent analysis.Source: §2.3 · pp. 13–14

3 Stochastic I.I.D. Input Model

Under an unknown i.i.d. request distribution, the section analyzes Algorithm 1's regret and shows an O(T^1/2) bound when the horizon and initial resources scale together. This regret order is optimal under the paper's minimal modeling assumptions.

3 Stochastic I.I.D. Input Model

The regret bound is independent of |X|, including settings where action sets may be exponentially large.Source: §3 · p. 17
O(T^1/2) regret is attained with η ∼ T^-1/2 when the horizon and initial resources are scaled together.The bound also implies regret divided by T tends to zero.Source: §3 · p. 17
O(m^1/2 T^1/2) regret follows when the reference function and initialization recover dual online sub-gradient descent.Source: §3 · p. 17
O((m log m)^1/2 T^1/2) regret is obtained for multiplicative weights by bounding the dual variables and restricting the reference function to a box.The entropy reference function is not strongly convex over the full non-negative orthant.Source: §3 · p. 17
The general resource-count dependence is polynomial rather than optimal, but a benchmark upper bound and simplex-constrained duals yield O(log^1/2(m)T^1/2) regret.Source: §3 · pp. 17–18
The Θ(T^1/2) order is tight: some distributions force Ω(T^1/2) regret even with known distribution, while Algorithm 1 attains matching O(T^1/2).The worst-case regret bound does not depend on the distribution's probability mass function.Source: §3 · p. 18

4 Adversarial Input

For adversarial requests, Algorithm 1 achieves an asymptotically optimal fixed competitive ratio under the stated assumptions. Its resource use is controlled so that depletion is not too early, although a nonseparable reference function can make the projection step hard to solve.

4 Adversarial Input

α* is the maximum of 1 and the largest resource's maximum possible consumption divided by its average per-period availability.The theorem gives α* = max{sup(f,b,X)∈S sup_j∈[m],x∈X b_j(x)/ρ_j, 1}.Source: §4 · pp. 18–19
With η ∼ T^-1/2, Algorithm 1 is α*-competitive and matches a lower bound, making its competitive ratio optimal under the stated assumptions.The guarantee means it obtains at least a 1/α* fraction of the best performance in hindsight as T grows.Source: §4 · p. 19
A nonseparable reference function can make projection step (4) hard to solve; the stated assumption requires coordinate-wise separability.The paper notes that most mirror-descent examples use coordinate-wise separable reference functions.Source: §4 · p. 19
For η ∼ T^-1/2, the stopping time leaves T − τA = O(T^1/2) periods, and resources are not depleted too early.The algorithm does not violate resource constraints before τA.Source: §4 · pp. 19–20
Bounded dual variables limit excess resource consumption, so resources are depleted smoothly over time.This is the stated mechanism for avoiding early depletion.Source: §4 · p. 20

5 Non-stationary Input

This section analyzes non-stationary stochastic inputs, including independent non-identical requests, ergodic Markov inputs, and periodic inputs, with guarantees that account for distributional drift and temporal dependence. For Markov inputs, Algorithm 1 attains regret matching the i.i.d. lower bound up to a logarithmic term, while for periodic inputs its regret depends on cycle length and step-size and vanishes when cycles are o(T) under optimal tuning.

5.1 Independent Inputs and Robustness to Adversarial Corruptions

With step-size η ∼ T^-1/2, Algorithm 1 has regret O(T^1/2 + δ), interpolating between i.i.d. regret O(T^1/2) and adversarial-scale regret O(T) as mean deviation grows.Here δ measures mean deviation from the average distribution; the stated adversarial case has δ ∼ T.Source: §5.1 · p. 21
When at most r requests corrupt an otherwise i.i.d. input, regret is O(max{T^1/2, r}); up to O(T^1/2) corruptions preserve O(T^1/2) regret.The paper states that Algorithm 1’s performance degrades linearly with the amount of corruption.Source: §5.1 · p. 21
A lower bound shows linear degradation is necessary, and even a constant variation budget can permit Ω(T) regret when distributions change once.Thus, the variation budget is not an appropriate metric for this setting.Source: §5.1 · p. 22

5.2 Ergodic Input and Markov Processes

For ergodic inputs, which allow nearby requests to be correlated, Theorem 5 bounds Algorithm 1’s regret using k-step distance from stationarity; i.i.d. inputs recover Theorem 1’s bound.The k-step distance measures how far the process’s k-step conditional distribution is from its stationary distribution.Source: §5.2 · pp. 23–24
For a uniformly ergodic general state-space chain with α ∈ (0, 1), setting η ∼ T^−1/2 and k = −log T/(2 log α) yields regret O(T^1/2 log T), matching the i.i.d. lower bound up to a logarithmic term.Source: §5.2 · p. 24

5.3 Periodic Input

With η ∼ (qT)^−1/2, regret is O((qT)^1/2), which vanishes when cycle length q=o(T).The periodic model permits arbitrary correlations within each length-q cycle, while cycles are i.i.d.Source: §5.3 · pp. 24–25
With η ∼ T^−1/2, regret is O(qT^1/2); the bound transitions from O(T^1/2) at q=1 to O(T) at q=T.The passage identifies these endpoints as i.i.d. requests when q=1 and adversarially chosen requests when q=T.Source: §5.3 · p. 25

6 Applications

The section develops applications to online linear programming, budgeted auction bidding, and high-entropy proportional matching. For the matching application, it addresses feasibility under randomized assignments when the hindsight resource constraint is expressed in expected allocations.

6.1 Online Linear Programming

Under i.i.d. inputs, the algorithm achieves optimal O(T^1/2) regret without solving auxiliary linear programs.Source: §6.1 · p. 26
For arbitrary adversarial revenue vectors and consumption matrices, it achieves the optimal asymptotic competitive ratio, tight at 1/rho in the single-leg case.Source: §6.1 · p. 26
The adversarial guarantee is not optimal for more structured problems, including AdWords, where vanishing stochastic regret precludes a fixed ratio independent of rho.Source: §6.1 · pp. 26–27

6.2 Bidding in Repeated Auctions with Budgets

For budgeted repeated auctions, the algorithm needs only observed payments—not competitors’ highest bids—and applies to any ex-post incentive-compatible auction.Source: §6.2 · pp. 27–28
Compared with Balseiro and Gur (2019), the method obtains similar regret bounds without their restrictive stochastic-input assumptions, while remaining optimal adversarially.Source: §6.2 · p. 28

6.3 Proportional Matching with High Entropy

High-entropy proportional matching seeks reward-maximizing impression-to-advertiser assignments while preserving high entropy; the formulation offers fairness and diversity with nonlinear concave rewards.Source: §6.3 · pp. 28–29
Each arriving impression has a revenue vector and is assigned to advertiser j with probability (x_t)_j, or left unassigned with probability 1 − Σ_j(x_t)_j.The reward includes an entropy regularizer on assignment probabilities.Source: §6.3 · p. 29
Because matching decisions are randomized, the constraints must account for the realized assignment, represented by the random variable v_t.The hindsight problem states its resource constraint in terms of expected allocation x_t.Source: §6.3 · p. 29

Appendix F.1, this problem is a valid upper bound on the performance of every online algorithm.

The appendix discusses an online counterpart to prior proportional-matching work, while Section 6.4 formulates personalized assortment optimization as an online allocation problem. Under i.i.d. inputs, the algorithms improve on a cited competitive ratio without auxiliary linear programs, but their adversarial ratio is not always sharper.

Appendix F.1, this problem is a valid upper bound on the performance of every online algorithm.

For proportional matching, the algorithm provides a simple online counterpart to Agrawal et al. (2018) with similar regret and complexity bounds.The algorithm does not require knowing the benchmark value or solving a convex optimization problem.Source: Appendix F.1 · p. 30

6.4 Personalized Assortment Optimization with Limited Inventories

Personalized assortment optimization fits the online allocation framework, with binary assortment decisions and choice probabilities representing expected product consumption.The choice model is assumed known to the retailer, though it can be learned separately; inventory updates use realized consumption.Source: §6.4 · pp. 30–31
Under stochastic i.i.d. inputs, Golrezaei et al. (2014)’s algorithm yields a 4-competitive ratio, while our algorithms attain a (1 + ε)-competitive ratio because their regret vanishes.A different algorithm from Golrezaei et al. (2014) obtains O(T^1/2) regret but requires solving at least one large linear program with 2m variables or constraints.Source: §6.4 · p. 32
Under adversarial inputs, Golrezaei et al. (2014) has a sharper competitive ratio, using shared revenues and reward linearity in consumption.The paper conjectures no algorithm can attain vanishing stochastic regret and fixed adversarial competitive ratios for assortment optimization.Source: §6.4 · p. 32

7 Extensions and Numerical Experiments

The extensions broaden the framework to alternative online optimization updates, unknown horizons, stochastic realized rewards and consumption, and approximate primal solves. The paper reports that its algorithms retain their guarantees in these settings, and concludes that they are optimal across several input models.

7.1 Beyond Mirror Descent

Algorithm 1 acts as a meta-algorithm that can use online linear optimization as a black box, extending beyond mirror descent.The paper notes extensions to regularized follow-the-leader, Adagrad, and Adam; ergodic and periodic inputs require stable dual variables.Source: §7.1 · pp. 32–33

7.2 Unknown Length of Horizon

For an unknown stochastic horizon that is a stopping time, the regret bound gains an extra term bounded by f̄ · Var(T)^1/2.This yields sublinear regret in the expected number of time periods; adversarially choosing the number of requests precludes vanishing regret even with stochastic input.Source: §7.2 · p. 33

7.3 Stochastic Reward and Resource Consumption

When rewards and resource consumption are stochastic after an action, the analysis extends by making decisions using expected reward and consumption.The theorems continue to hold after taking expectation over the stochastic realization; the i.i.d. case is proved explicitly.Source: §7.3 · p. 34

7.4 Approximately Solving the Sub-Problem (3)

For additive per-round solve errors ϵ_t, the regret bound gains their sum; if the cumulative error is O(T^1/2), then Regret(A) remains O(T^1/2).Source: §7.4 · p. 34

7.5 Numerical Experiments

Numerical experiments report that regret grows as T^1/2 across tested step sizes, and the algorithms’ running times are independent of primal decision dimension.The experiments also report ˜O(√(mT)) regret for online gradient descent and multiplicative weights, versus ˜O(√T) for projected multiplicative weights.Source: §7.5 · p. 35

8 Conclusion and Future Directions

The algorithms attain vanishing regret under stochastic i.i.d. and non-stationary inputs and fixed competitive ratios under adversarial inputs, with optimal performance across models.They apply to nonlinear rewards and consumption and potentially integral decisions, without knowing the input model in advance.Source: §8 · p. 35

A Proofs in Section 2

These proofs connect the online allocation guarantee to the dual benchmark and work out regret bounds for example mirror-descent reference functions. The examples show how the choice of reference function affects dependence on the number of resources.

A.1 Proof of Proposition 1

Relaxing the total-consumption constraint and choosing a nonnegative dual multiplier yields an upper bound on every online algorithm’s performance.The appendix also describes the proportional-matching algorithm as a simple online counterpart to Agrawal et al. (2018), with similar regret and complexity bounds.Source: §A.1 · p. 41

B.1 Online Gradient Descent

For online gradient descent, the squared Euclidean reference function gives a regret bound whose C1 and C3 constants are independent of the number of resources.A squared weighted-ℓ2 reference function can account for different resource-constraint scales by normalizing consumption.Source: §B.1 · pp. 41–42

B.2 Multiplicative Weights Algorithm

For multiplicative weights, the negative-entropy reference function yields a regret bound with dependence on m and log(f̄/ρ̄).The analysis bounds dual variables in a box, with a sufficiently small step size for sufficiently long horizons.Source: §B.2 · p. 42

C Optimal Dependence on the Number of Resources

Restricting dual variables to a scaled simplex lets the multiplicative-weights analysis attain optimal dependence on the resource count. The adversarial proof adapts the stochastic argument and substitutes the online mirror-descent regret bound.

C Optimal Dependence on the Number of Resources

Restricting dual variables to D yields an optimal log^1/2(m) dependence on the number of resources for multiplicative weights.The negative-entropy reference function and simplex restriction support the stronger regret guarantee.Source: C Optimal Dependence on the Number of… · p. 43

D.1 Proof of Theorem 2

The adversarial proof applies primal-performance and complementary-slackness steps, then substitutes the online mirror-descent regret bound.It selects a resource-specific dual pivot when the algorithm stops before the horizon.Source: §D.1 · pp. 44–45

D.2 Proof of Proposition 2

The proof bounds every dual multiplier by μmax when the step size is sufficiently small. For time-dependent request distributions, it adapts the earlier theorem proof using their time-averaged distribution and mean-deviation bound.

D.2 Proof of Proposition 2

If μ ≤ μmax and η ≤ σ²/ b̄, the next dual multiplier also satisfies μ+ ≤ μmax.The proof applies this one-step bound to keep all iterates below μmax.Source: §D.2 · p. 46
The proof first establishes that each dual multiplier is at most μmax, then uses the stopping-time definition to finish Proposition 2.The one-step bound in Lemma 3 supplies the multiplier bound for every period.Source: §D.2 · p. 46

E.1 Proof of Theorem 3

For time-dependent request distributions, the proof adapts Theorem 1 using the time-averaged distribution and the condition MD(P⃗) ≤ δ.It reuses Theorem 1's arguments and bounds the Bregman-divergence term as in that proof.Source: §E.1 · pp. 47–48

E.2 Proof of Theorem 4

The proof lower-bounds performance under corruption by reducing to a stochastic input case and constructing two hard input sequences. Yao’s lemma turns the resulting deterministic-algorithm bound into a lower bound for randomized algorithms.

E.2 Proof of Theorem 4

The stochastic model is a special case of the corruption model with δ = 0, so its lower bound also applies to the corruption model.The proof cites the stochastic-model lower bound, including Lemma 1 from Arlotto and Gurvich 2019.Source: §E.2 · p. 48
Every deterministic mechanism incurs regret of order δ for the constructed distribution over input sequences.The proof uses Yao’s lemma to relate this bound to randomized algorithms.Source: §E.2 · p. 49
The hard instance uses two three-stage input sequences that differ only in Stage 2, which the algorithm cannot identify before that stage.The construction analyzes deterministic algorithms under an equal-probability distribution over the two sequences.Source: §E.2 · pp. 49–50

E.3 Proof of Theorem 5

The proof establishes stability of the dual iterates and adapts Theorem 1 to request processes that deviate from a stationary distribution. Its regret bound incorporates that deviation and the step-size-dependent stability term.

E.3 Proof of Theorem 5

The proof adapts Theorem 1 to an ergodic process whose k-step total-variation deviation from a one-period distribution is at most δ.It uses the process condition TV_k(P, P̄) ≤ δ in bounding the regret.Source: §E.3 · pp. 52, 54
When η ≤ 2σ/(b̄ + ρ̄), consecutive dual multipliers differ in 1-norm by at most Cη.This stability bound is used in the proof's analysis of time-dependent request distributions.Source: §E.3 · pp. 51–52
The displayed regret bound includes a step-size stability term and terms proportional to T·TV_k(P, P̄) and k.The proof derives the bound by combining its intermediate inequalities and substituting the chosen dual variable.Source: §E.3 · p. 54

E.4 Proof of Theorem 6

Theorem 7 treats stochastic request processes through a partition-based variation measure, and Theorem 6 follows as a periodic-process special case. The appendix also extends the analysis to random rewards and consumption, and states a standard online mirror descent result.

E.4 Proof of Theorem 6

Theorem 7 considers an arbitrary stochastic process with a partition and a mean-deviation parameter δ; its proof bounds the benchmark using the partition-based reference distribution.The displayed benchmark inequality relates OPT(P) to the expected dual function and a term involving the partition variation.Source: §E.4 · pp. 54, 56
For requests periodic with cycle length q, choosing cycles as the partition gives ℓ2(Π) ≤ 2qT and TV(P, Π, P̄) = 0, yielding Theorem 6 from Theorem 7.The proof identifies Theorem 6 as a special case of Theorem 7.Source: §E.4 · p. 57

F.1 Proof of Proposition 3

With random rewards and consumption revealed after the action, the adapted algorithm chooses using expected functions but updates resources using realized consumption.The paper states that its performance bounds continue to hold after taking expectation over the randomness.Source: §F.1 · pp. 57–58

G Online Mirror Descent

For convex losses and bounded subgradients, Proposition 5 gives an online mirror descent guarantee when the reference function is strongly convex.The proof obtains the bound by summing the per-period inequalities and telescoping the Bregman divergences.Source: G Online Mirror Descent · pp. 59–60

H.1 Online Linear Programming

Experiments examine online linear programming and proportional matching under i.i.d. and ergodic inputs. They report regret scaling with horizon and resource dimension, and relative reward exceeding 80% within 10,000 samples in some matching settings.

H.1 Online Linear Programming

O(T^1/2) regret growth appeared for OGD, MWU, and MWU-P as T increased.Figure 1 reports average regret over 100 random trials with 95% confidence intervals.Source: Figure 1 · p. 61, §H.1 · p. 62
MWU-P regret grew more slowly with m, consistent with O(log(m)) versus O(m^1/2) for OGD and MWU; none grew with d.The reported dimension trends are consistent with the paper’s theory.Source: §H.1 · p. 62

H.2 Proportional Matching

O(T^1/2) regret growth held for both publishers under i.i.d. and ergodic inputs, while relative reward exceeded 80% within 10,000 samples for i.i.d. and c=0.5.The relative-reward threshold was reached for publisher 2 and publisher 5.Source: §H.2 · p. 63, Figure 2 · p. 64, Figure 3 · p. 64
Regret retained T^1/2 growth across tested step sizes, with publisher 5 more step-size-sensitive than publisher 2.The authors note that tuning the step size may further improve performance.Source: §H.2 · p. 63, Figure 4 · p. 64