Operations Research

Two-stage decisions under an ambiguous distribution

Two-stage stochastic linear programs model decisions taken in two steps: a first-stage decision $x$ is fixed before an uncertain parameter $\xi$ is observed, and a second-stage (recourse) decision $y$ adapts to $\xi$ afterwards. They underlie capacity planning, inventory and network design. In practice the distribution of $\xi$ is known only through samples $\hat\xi_1,\dots,\hat\xi_I$. Distributionally robust optimization replaces the unknown distribution by the worst case over an ambiguity set; a popular choice is a Wasserstein ball around the empirical distribution, because it contains the true distribution with high probability and yields out-of-sample guarantees (Mohajerin Esfahani and Kuhn, 2018).

Hanasusanto and Kuhn (arXiv:1609.07505, Operations Research 66(3), 2018) study when the resulting two-stage problem can be solved exactly. Section 3 of their paper gives a copositive reformulation for the 2-Wasserstein ball (the subject of a companion mission). Section 4, the subject of this mission, shows that when the uncertainty enters only the constraints of the recourse problem and the ball is a 1-Wasserstein ball with a polyhedral reference distance, the whole problem is a linear program.

Setting

Let $c\in\mathbb R^{N_1}$ and $\mathcal X\subseteq\mathbb R^{N_1}$ be the first-stage cost and feasible set, $q\in\mathbb R^{N_2}$ the second-stage cost, $W\in\mathbb R^{M\times N_2}$ the recourse matrix, and $T(x)\in\mathbb R^{M\times K}$, $h(x)\in\mathbb R^M$ affine functions of $x$. The recourse value at $\xi\in\mathbb R^K$ is

$$Z(x,\xi)=\inf\{\,q^\top y : y\in\mathbb R^{N_2},\ T(x)\xi+h(x)\le Wy\,\}\in[-\infty,+\infty].$$

The uncertainty affects only the constraints (in the paper's notation, $Q=0$), and there is no support constraint: $\Xi=\mathbb R^K$. The problem has sufficiently expensive recourse if some $p\ge 0$ satisfies $W^\top p=q$.

For scaling parameters $w_+,w_->0$ the reference distance is $d(\xi,\xi')=\|\xi-\xi'\|$ with

$$\|\xi\|=\sum_{k\in[K]}\max\{w_+\xi_k,\,-w_-\xi_k\}. \qquad (31)$$

Moving a unit of mass in the positive direction of coordinate $k$ costs $w_+$, in the negative direction $w_-$. The 1-Wasserstein ball $\mathcal B^1_\epsilon(\hat{\mathbb P}_I)$ consists of the probability measures $\mathbb P$ on $\mathbb R^K$ whose optimal transport cost to $\hat{\mathbb P}_I=\frac1I\sum_i\delta_{\hat\xi_i}$ under $d$ is at most $\epsilon$. The worst-case expectation and the two-stage problem (1) are

$$\mathcal Z(x)=\sup_{\mathbb P\in\mathcal B^1_\epsilon(\hat{\mathbb P}_I)}\mathbb E_{\mathbb P}[Z(x,\tilde\xi)],\qquad \inf_{x\in\mathcal X}\ c^\top x+\mathcal Z(x).$$

The dual norm of (31) is $\|z\|_*=\sup\{z^\top\xi:\|\xi\|\le 1\}$.

Formalization targets

Goal: Theorem 6

For $\epsilon>0$ and every $x\in\mathcal X$, $\mathcal Z(x)$ equals the optimal value of the linear program

$$\begin{aligned}\min\ \ &\epsilon\lambda+\frac1I\sum_{i\in[I]}q^\top y_i\\ \text{s.t.}\ \ &\lambda\ge 0,\quad T(x)\hat\xi_i+h(x)\le Wy_i\ \ \forall i\in[I],\\ &q^\top\phi_k\le\lambda,\ q^\top\psi_k\le\lambda,\ T(x)e_k/w_+\le W\phi_k,\ -T(x)e_k/w_-\le W\psi_k\ \ \forall k\in[K],\end{aligned}\qquad(32)$$

and consequently problem (1) has the optimal value of (32) minimized jointly over $x\in\mathcal X$ and the other variables with $c^\top x$ added to the objective.

Milestones, in the order of the paper's proof

1. Theorem 1 in this instance ($r=1$, gauge cost, $\Xi=\mathbb R^K$): $\mathcal Z(x)$ equals the moment problem (5) and, for $\epsilon>0$, the dual

$$\mathcal Z(x)=\inf_{\lambda\ge 0}\ \epsilon\lambda+\frac1I\sum_{i}\sup_{\xi\in\mathbb R^K}\big[Z(x,\xi)-\lambda\|\xi-\hat\xi_i\|\big].$$

2. Display (33): $\mathcal Z(x)=\inf\{\epsilon\lambda+\frac1I\sum_i\sup_{p\ge0,\,W^\top p=q}\,h(x)^\top p+(T(x)^\top p)^\top\hat\xi_i\ :\ \lambda\ge0,\ \|T(x)^\top p\|_*\le\lambda\ \forall p\ge0,\,W^\top p=q\}$.
3. The dual norm of (31): $\|z\|_*=\max_{k}\max\{z_k/w_+,\,-z_k/w_-\}$.
4. The constraint decomposition: the semi-infinite constraint of (33) holds if and only if, for each $k$, there are $\phi_k,\psi_k$ satisfying the four linear inequalities of (32).

Significance

Theorem 6 shows that the two-stage distributionally robust linear program over a 1-Wasserstein ball, which is a priori an optimization over infinitely many distributions, has a linear-programming reformulation with $O(I+K)$ blocks of variables and constraints. It covers distributionally robust least-absolute-deviation regression (Example 2 of the paper), where the reformulation becomes the empirical loss plus a dual-norm regularizer, and it contrasts with the paper's Theorem 7, which shows that for $p$-norm reference distances with $p>1$ the same problem is NP-hard.

The result is proved in the paper; there is no machine-checked proof. A formalization adds a verified chain from the measure-theoretic worst-case expectation to a finite linear program, including the conventions the paper leaves implicit: the extended-real values ($\mathcal Z(x)$ may be $+\infty$, and (32) may then be infeasible), the restriction $\epsilon>0$, and the first-stage cost in the objective.

Difficulty

Each step of the proof is classical, but the chain crosses several regimes. Theorem 1 is a Wasserstein strong duality result, and here it is applied to a loss $Z(x,\cdot)$ that is convex, possibly $+\infty$ on part of $\mathbb R^K$, and not upper semicontinuous, with a cost that is not symmetric; the standard published duality theorems assume an upper semicontinuous real-valued loss or a metric. The passage to (33) interchanges a supremum over $\xi$ with an infimum over the dual-norm ball and must handle the case where the dual recourse polyhedron is unbounded. Finally, every equivalence must hold in the extended reals: an argument that tacitly assumes finiteness proves a statement that fails exactly when the dual polyhedron has a recession direction.

Formalization scope

Vectors are Fin n → ℝ, samples are ξhat : Fin I → (Fin K → ℝ) with $I\ge1$, and $\mathbb R^K$ carries its product (Borel) σ-algebra. $T$ and $h$ are affine maps. The transport cost is the platform definition RWPI.SqrtLasso.transportCost (couplings with first marginal $\mathbb P$, second $\hat{\mathbb P}_I$), the empirical distribution is WassersteinDRO.Duality.empiricalDistribution, and expectations of the extended-real recourse value use WassersteinDRO.Duality.erealExpectation (value $+\infty$ whenever the positive part has infinite integral). Every optimal value is an extended-real infimum or supremum over its feasible set; no Bochner integral and no real-valued sInf/sSup is used.

Conventions made explicit, with reasons:

• $\epsilon>0$. The paper does not restrict $\epsilon$ in Theorem 6, but its proof starts from the dual (6), stated only for $\epsilon>0$, and the identity is false at $\epsilon=0$ when the dual recourse polyhedron has a recession direction $r$ with $T(x)^\top r\ne0$: then (32) is infeasible while $\mathcal Z(x)$ is the finite sample average.
• $c^\top x$ in (32). The printed objective of (32) omits the first-stage cost. The proof establishes the pointwise identity $\mathcal Z(x)=$ value of (32) at $x$, which is the goal's first part; the problem-level equivalence restores $c^\top x$.
• Asymmetric gauge. For $w_+\ne w_-$, (31) is not a norm, and Theorem 1 of the paper is stated for a metric. The paper applies it to (31) anyway; the milestone states that application, with the gauge cost in the orientation $d(\xi,\hat\xi_i)=\|\xi-\hat\xi_i\|$. The case $w_+=w_-$ is not imposed.
• Finite first moment. Membership in $\mathcal M^1(\mathbb R^K)$ is implied by finite transport cost to $\hat{\mathbb P}_I$ and is not repeated.
• The two "$1/N$" factors in the paper's proof are misprints for $1/I$.

A formalization in which $\mathcal Z$ is defined by (6), (33) or (32), in which the gauge is secretly symmetric, or in which expectations are Bochner integrals (zero for non-integrable functions) would make the goal trivial or different; the definitions here exclude each of these.

A complete development needs Wasserstein strong duality for a lower semicontinuous loss and cost (with a disintegration of couplings to pass to the moment problem (5)), LP strong duality and Farkas' lemma in the extended-real form, and a minimax interchange over a compact dual-norm ball. Wasserstein duality for general costs and extended-real LP duality are reusable well beyond this mission; contributions of either are welcome.

Selected references

• G. A. Hanasusanto, D. Kuhn, Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls, Operations Research 66(3), 2018. Pinned version: arXiv:1609.07505v3. DOI 10.1287/opre.2017.1698.
• P. Mohajerin Esfahani, D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations, Mathematical Programming 171, 2018. doi:10.1007/s10107-017-1172-1
• J. Blanchet, K. Murthy, Quantifying distributional model risk via optimal transport, Mathematics of Operations Research 44(2), 2019. doi:10.1287/moor.2018.0936
• R. Gao, A. Kleywegt, Distributionally robust stochastic optimization with Wasserstein distance, Mathematics of Operations Research 48(2), 2023. doi:10.1287/moor.2022.1275
• D. P. Bertsekas, Convex Optimization Theory, Athena Scientific, 2009 (Proposition 5.5.4, the minimax theorem used in the proof).

Motivation

An online retailer that serves many kinds of customers must decide, for each arriving customer, which handful of products to display. Showing too many items is impossible (screen space, shelf space), and which items sell depends on who is looking. The retailer does not know the customers' preferences in advance and learns them only from the choices customers make among the items shown. This is dynamic assortment personalization: an online learning problem in which every display both earns revenue and produces data.

Kallus and Udell (arXiv:1610.05604) study the regime in which the number of customer types $m$ and the number of items $n$ are both large, so that learning each type's preferences separately would take on the order of $mn$ interactions. Their premise is that preferences across types are governed by a few latent features, which makes the matrix of preference parameters approximately low rank. The non-contextual problem — one customer type, multinomial-logit choice — was studied by Rusmevichientong, Shen and Shmoys (2010) and Sauré and Zeevi (2013); the paper extends it to many types and proposes an explore-then-exploit policy whose estimates come from nuclear-norm regularized maximum likelihood, the standard convex surrogate for low rank used in matrix completion.

Setting

There are $m$ customer types and $n$ items. Each type $i$ has a revenue vector $W_i\in\mathbb R^n$ (row $i$ of $W\in\mathbb R^{m\times n}$; $W_{ij}$ is the expected revenue when type $i$ buys item $j$) and a preference vector $\Theta^\star_i$ (row $i$ of the unknown matrix $\Theta^\star\in\mathbb R^{m\times n}$). Types arrive independently from an unknown distribution $\mu^\star$ in the simplex $\Delta^m$.

For an assortment $S\subseteq\{1,\dots,n\}$ and a parameter vector $\theta\in\mathbb R^n$, the multinomial-logit (MNL) choice probability of item $j\in S$ is

$$p_j(S;\theta)=\frac{e^{\theta_j}}{1+\sum_{j'\in S}e^{\theta_{j'}}},$$

and the customer buys nothing with probability $1/(1+\sum_{j'\in S}e^{\theta_{j'}})$. The expected revenue of $S$ is $F(S;w,\theta)=\sum_{j\in S}p_j(S;\theta)w_j$, and $S^\star(w,\theta;K)$ is the set of maximizers of $F(\cdot;w,\theta)$ over $|S|\le K$. The revenue gap $\delta(w,\theta;K)$ is the optimal revenue minus the best revenue of a non-optimal assortment.

In round $t=1,2,\dots$ a customer of type $i_t\sim\mu^\star$ arrives, the retailer offers $S_t$ with $|S_t|\le K$, and the customer chooses $j_t$ from the MNL law with parameters $\Theta^\star_{i_t}$. The regret (Definition 1) of a policy after $T$ rounds is the expected revenue of the $\Theta^\star$-greedy policy, which always offers an element of $S^\star(W_{i_t},\Theta^\star_{i_t};K)$, minus the expected revenue of the policy.

Algorithm 2, $\pi_{\text{nuc-norm}}(C,\lambda)$, keeps a sample $\mathcal O$ of exploration observations. At round $t$, if $|\mathcal O|\le Cr(m+n)\log t$ it explores: it offers a uniformly random subset of size exactly $K$ and records $(i_t,j_t,S_t)$. Otherwise it exploits: it offers an element of $S^\star(W_{i_t},\widehat\Theta_{i_t};K)$, where $\widehat\Theta$ is a solution of

$$\min_{\Theta}\ L(\Theta)+\lambda\|\Theta\|_*\quad\text{s.t.}\quad\|\Theta\|_\infty\le\alpha/\sqrt{mn},\tag{5}$$

with $L$ the average negative log-likelihood (4) of the sample, $\|\cdot\|_*$ the nuclear norm and $\|\Theta\|_\infty$ the largest absolute entry.

Formalization targets

Goal: Theorem 6

Let $r\ge\operatorname{rank}\Theta^\star$, $1/\rho\le m\mu^\star_i\le\rho$ for all $i$, $\|\Theta^\star\|_\infty\le\alpha/\sqrt{mn}$, $\min_i\delta(W_i,\Theta^\star_i;K)\ge\delta>0$ and $0\le W$, $\max_{ij}|W_{ij}|\le\omega$. With

$$C=\frac{4194304\,K^6\rho^3\omega^2\alpha^2e^{16\alpha}}{\delta^2},\qquad\lambda=8\sqrt{\frac{\rho K}{Crmn}},\tag{12}$$

for every selection of $\widehat\Theta$ from the solutions of (5) and of the exploited assortment,

$$\mathrm{Regret}(T;\pi_{\text{nuc-norm}}(C,\lambda))\le\big((Cr(m+n)+3)\log T+1\big)\,\omega\qquad\text{for }1\le T\le(m+n)^{mn/(Cr(m+n))}.$$

Milestones

From the printed proof of Theorem 6 (pp. 47–48): the Lipschitz bound $|p_j(S;\theta)-p_j(S;\theta')|\le\frac14\sqrt{|S|}\|\theta-\theta'\|_2$; the revenue bound $|F(S;w,\theta)-F(S;w,\theta')|\le\frac14\|w\|_\infty K^{3/2}\|\theta-\theta'\|_2$; the comparison $F(S';w,\theta)\ge F(S;w,\theta)-\frac12\|w\|_\infty K^{3/2}\|\theta-\theta'\|_2$ of optimal sets; the stability of the optimal set; and the count of exploration rounds. From the deterministic part of the recovery analysis (Sec. 8): Lemma 2 (a quadratic lower bound on the Bregman divergence of $L$), Lemma 5 (an upper bound from the regularized objective) and Lemma 6 (the nuclear-norm error is controlled by $\sqrt r$ times the Frobenius error and the spectral tail of $\Theta^\star$).

Significance

Theorem 6 is the paper's guarantee that a policy exploiting low-rank structure pays regret of order $r(m+n)\log T$ rather than the order $mn\log T$ that the paper shows (Theorem 5) for policies treating each type separately. The intermediate results are reusable: the Lipschitz bounds for MNL choice probabilities and revenue apply to any MNL assortment policy that plugs in estimated parameters, and Lemmas 2, 5 and 6 are the deterministic core of nuclear-norm regularized estimation for a likelihood that is not an entrywise loss.

To the best of current knowledge none of these results has a machine-checked proof. The mission produces a formal model of a contextual MNL assortment process with an adaptive policy, its trajectory law and regret, together with formal statements and proofs of the Lipschitz and stability facts that any explore-then-exploit analysis of MNL assortment needs. Several printed statements needed correction (see Formalization scope); machine-checked proofs settle the corrected forms.

Difficulty

The goal is a statement about the law of a $T$-round adaptive process: the offered set at round $t$ depends on the whole past through the exploration test and through an estimate defined only as some minimizer of (5). Any argument must handle this dependence exactly, for every admissible selection of minimizer and of optimal assortment, rather than for one convenient choice.

The constants are explicit and the horizon is restricted, so the inequality has to hold with the paper's normalization exactly as stated, including the box constraint of (5). The printed proof routes through the paper's high-probability recovery bound (Theorem 3), which is believed false as printed and is not part of this mission, so a proof cannot simply cite it. Lemmas 5 and 6 require Hölder's inequality for the spectral/nuclear pairing and a decomposition of the error relative to the singular subspaces of $\Theta^\star$; Lemma 2 requires a curvature estimate for the log-sum-exp function uniformly on the box.

Formalization scope

The source is the arXiv preprint arXiv:1610.05604, an unstamped PDF pinned by sha256 2b010481…216a; its printed page numbers equal the PDF page numbers.

Types and items are Fin m and Fin n, 0-based; the no-purchase option is none. Matrices are MatrixCompletion.RealMatrix m n; the nuclear, spectral and Frobenius norms, the Frobenius inner product and $\|\cdot\|_\infty$ are the published MatrixCompletion definitions, and $F$ is the published ChoiceCDLP.MNL.mnlObjective with weights $e^{\theta_j}$ and no-purchase weight $1$. All probabilities and expectations are finite sums over histories in Fin T → Fin m × Finset (Fin n) × Option (Fin n). Regret is Definition 1 after the tower property: the greedy policy earns $\sum_i\mu^\star_i\max_{|S|\le K}F(S;W_i,\Theta^\star_i)$ per round and Algorithm 2 earns $F(S_t;W_{i_t},\Theta^\star_{i_t})$ in expectation. The gap condition $\delta(w,\theta;K)\ge d$ is stated as "every non-optimal assortment of size at most $K$ earns at most the optimum minus $d$", since $\delta$ itself is undefined when every assortment is optimal.

Added hypotheses and corrections, each disclosed in the item's note:

• Theorem 6 assumes $W\ge0$, $\delta>0$, $1\le K\le n$, $m,n\ge1$ and $T\ge1$. The horizon is read as $T\le(m+n)^{mn/(Cr(m+n))}$ (the page sets $r$ beside the fraction in the exponent); for $r\ge1$ this is the smaller range. If $r=0$, Lean's division by zero gives $\lambda=0$ and horizon $T\le1$.
• The stability of the optimal set (p. 47) is false as printed (an equality of optimal sets) and is stated as the inclusion $S^\star(w,\theta';K)\subseteq S^\star(w,\theta;K)$ under the page's (non-strict) closeness hypothesis, multiplied out.
• The exploration count (p. 48) is stated as $Cr(m+n)\log T+1$, the form the next display uses, instead of the printed $C\log T+1$.
• Lemma 2 is false as printed and carries an extra factor $\frac12$; it assumes $\Theta^\star$ and $\Theta^\star+\Delta$ both feasible for (5).
• Lemmas 5 and 6 carry the standing assumptions of Sec. 8: $\widehat\Theta$ solves (5), $\Theta^\star$ is feasible, $\lambda>0$.

Theorem 3 (static recovery) and Lemma 4 (gradient concentration) are not posed: both are believed false as printed. Lemmas 3 and 7 are not posed either.

A trivializing formalization is ruled out: the estimator is any minimizer of (5) with its box constraint, the exploited set is any optimal assortment for the estimate, and both are quantified universally; exploration draws uniformly from subsets of size exactly $K$; and the benchmark is the $\Theta^\star$-greedy policy under the same arrival law. Fixing the estimator to $\Theta^\star$, dropping the box, or comparing to the best fixed assortment would change the theorem.

Contributions welcome: proofs of the milestones (the Lipschitz lemmas are calculus on the softmax function; Lemmas 5 and 6 are matrix analysis reusable for other nuclear-norm estimators), a proof that the definition of $\nabla L$ is the gradient of $L$, and a proof that the history weights form a probability distribution.

Selected references

• N. Kallus, M. Udell, Dynamic Assortment Personalization in High Dimensions, arXiv preprint, 2016–2017; Operations Research 68(4), 2020. https://arxiv.org/abs/1610.05604
• P. Rusmevichientong, Z.-J. M. Shen, D. B. Shmoys, Dynamic assortment optimization with a multinomial logit choice model and capacity constraint, Operations Research 58(6), 2010. https://doi.org/10.1287/opre.1100.0866
• D. Sauré, A. Zeevi, Optimal dynamic assortment planning with demand learning, Manufacturing & Service Operations Management 15(3), 2013. https://doi.org/10.1287/msom.1120.0412
• B. Recht, M. Fazel, P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review 52(3), 2010. https://doi.org/10.1137/070697835

Motivation

A firm selling a fixed stock of a perishable product over a finite season must set prices without knowing how demand responds to them. Online retail and travel platforms often see a customer's segment before quoting a price, so they can price-discriminate across consumer types. Learning a separate demand curve for each type, however, seems to cost more exploration as the number of types grows. Chen and Gallego (arXiv:1812.09234v3, 2021; Mathematics of Operations Research, 2022) give a learning algorithm whose regret does not depend on the number of types. Their key step is to learn a single scalar first: the shadow price of inventory.

Earlier work on the single-type problem frames the question. Besbes and Zeevi (Operations Research, 2009) defined the regret against the fluid benchmark and showed that no policy can achieve regret decaying faster than $n^{-1/2}$. Wang, Deng and Ye (Operations Research, 2014) gave a single-product algorithm whose regret matches this rate up to logarithmic factors. Chen and Gallego extend the rate to $M$ types with one inventory constraint.

Setting

There are $M\ge1$ consumer types, a season $[0,T]$ and an inventory $c$. When the firm charges price $p$ to type $m$, type-$m$ consumers arrive at rate $d_m(p)$. Prices range over $[0,p_\infty]$, where $p_\infty$ is a choke price with $d_m(p_\infty)=0$. Assumption 1 asks that each $d_m$ be strictly decreasing, bounded and Lipschitz, and that the revenue rate $r_m(\lambda)=\lambda d_m^{-1}(\lambda)$ be Lipschitz and twice differentiable, with $0<M_3\le-r_m''\le M_4$.

The fluid problem (2) maximizes $\sum_m\int_0^Tp_m(t)d_m(p_m(t))\,dt$ subject to $\sum_m\int_0^Td_m(p_m(t))\,dt\le c$. Its optimal value is $J^D(T,c)$. Its dual is one-dimensional. With

$$\mathcal R_m(z)=\max_{p}d_m(p)(p-z),\qquad \mathcal P_m(z)=\operatorname*{argmax}_pd_m(p)(p-z),\qquad g(z)=cz+T\sum_m\mathcal R_m(z),$$

the dual optimum is $z^*=\operatorname{argmin}_{z\ge0}g(z)$, and the optimal fluid prices are the constants $p^*_m=\mathcal P_m(z^*)$.

In the $n$-th system demand and inventory scale together: type $m$ arrives as a Poisson process with rate $n\,d_m(p)$, and the inventory is $nc$. The firm does not know $d_m$. It knows $T$, $c$, $n$, the constants of Assumption 1 and, by Assumption 2, intervals $[\underline p,\overline p]$ and $[0,\overline z]$ that contain every $p^*_m$ and $z^*$. A policy $\pi$ has expected revenue $J^\pi_n(T,c)$, and its regret is

$$R^\pi_n(T,c)=1-\frac{J^\pi_n(T,c)}{J^D_n(T,c)}.$$

Algorithm 1, the primal-dual learning algorithm, runs phases $k=1,\dots,K$ of shrinking lengths $\tau^{(k)}$. In each learning phase it tests a price grid inside the current interval estimators of every $p^*_m$. It then minimizes an empirical dual function on a grid of $z$ and re-centres the interval estimators of $z^*$ and $p^*_m$. In the last phase it either charges a marked-up price (sufficient capacity), or tests two prices and interpolates between them so that total sales end close to $nc$ (insufficient capacity). Its tuning depends on a constant $\epsilon>0$.

Formalization targets

Goal: Theorem 1 (p. 17)

For every $\delta>0$ one can choose $\epsilon>0$ and a constant $C$, independent of $n$, such that

$$R^\pi_n(T,c)\le C(\log n)^{2+\delta}n^{-1/2}\qquad\text{for all }n\ge3.$$

The two capacity regimes (Propositions 2–3)

$$z^*=0:\ R^\pi_n=O\big((\log n)^{2+16\epsilon}n^{-1/2}\big),\qquad z^*>0:\ R^\pi_n=O\big((\log n)^{2+18\epsilon}n^{-1/2}\big).$$

Milestones

• Proposition 1: the fluid problem is solved by the constant prices $p^*$, with complementary slackness; and the monotonicity, convexity and derivative of $\mathcal P_m$ and $\mathcal R_m$.
• Lemmas 9 and 10: a Poisson tail bound decaying faster than any power, and $\mathbb E|X-\lambda|\le\sqrt\lambda$.
• Lemmas 1 and 2: $K\le3\log n+3$, and the learning phases take at most half the season.
• Lemmas 3–5: the interval estimators contain $z^*$, $p^*_m$ and $\mathcal P_m$ on the dual interval, except with probability $O((\log n)^2/n)$.
• Lemmas 6–7: the sales at the start of the last phase are close to the fluid level.
• Lemma 8: when $z^*>0$, $\mathbb E|S(T)-nc|=O((\log n)^\epsilon n^{1/2})$.

Significance

Theorem 1 states that personalized pricing for $M$ types under a shared inventory constraint is learnable at the single-type rate $n^{-1/2}$, up to logarithms, with a constant independent of $n$. Combined with the Besbes–Zeevi lower bound, the algorithm is rate-optimal. Learning the scalar shadow price $z^*$, instead of the joint optimum of an $M$-dimensional problem, is what avoids the curse of dimensionality.

The result is proved in the paper; no machine-checked version exists. A formalization would add to the platform a multi-type Poisson pricing model with stock-outs, the one-dimensional Lagrangian dual of the fluid revenue-management problem, an exactly specified multi-phase learning algorithm, and reusable Poisson deviation lemmas. Lemmas 1, 2, 9 and 10 and Proposition 1 can be proved independently of the probabilistic analysis.

Difficulty

The obvious argument estimates every $p^*_m$ directly and charges the estimate. With interval estimators of width $n^{-1/4}$ this loses revenue of order $n^{-1/4}$ per unit time when the inventory constraint binds ($z^*>0$), because $p^*_m$ is then not the unconstrained maximizer of $p\,d_m(p)$. The paper's (11) and (19) show the loss. The bound $n^{-1/2}$ requires steering the total sales to within $O(n^{1/2})$ of the inventory, which is Lemma 8, and a second-order expansion of the revenue around $p^*$ that uses the first-order condition $r_m'(d_m(p^*_m))=z^*$.

Formally, a further difficulty is the closed loop: the prices of a phase depend on the counts of earlier phases, and the counts are Poisson only conditionally, through the random time change $N_m(n\int_0^td_m(P_m(s))\,ds)$.

Formalization scope

All declarations live in the namespace PrimalDualPricing.Regret. Printed page numbers equal PDF page numbers in the cited preprint.

• Model. Types are Fin M. Each $d_m:\mathbb R\to\mathbb R$ satisfies Assumption 1 on $[0,p_\infty]$ and is otherwise any extension with $0\le d_m\le M_1$; the last-phase prices $\underline p^{(K)}_m-\alpha$ and $\overline p^{(K)}_m+\alpha$ can leave $[0,p_\infty]$. $d_m(p_\infty)=0$ encodes the choke price. $\mathcal P_m$ and $z^*$ are fields carrying their optimality properties.
• Assumption 2 is read with $z^*\in[0,\overline z)$; the page prints $(0,\overline z)$, which would drop the case $z^*=0$ that Proposition 2 and Theorem 1 cover. The price interval is placed in the domain, $0\le\underline p<\overline p\le p_\infty$.
• Remark 2 assumes $M_3\le g''\le M_4$; this is read on $[0,\overline z]$, because globally it is unsatisfiable. Each $\mathcal P_m$ is $M_2$-Lipschitz.
• The fluid value $J^D$ is the supremum of (2) over measurable price paths. The identity $J^D=T\sum_mp^*_md_m(p^*_m)$ is Proposition 1.4, a milestone, and is not built into the definition.
• The algorithm. The grid sizes $N^{(k)}$, $N_z^{(k)}$ are rounded up. Grid spacing is $\Delta_m/N$ for prices and $\Delta_z/(N_z+1)$ for duals: the text and Table 1, respectively the text and line 15, agree on these, and Algorithm 1 line 7 and Table 1 print the other forms. Ties in (8)–(9) go to the smallest index. $\theta$ in (14) is projected onto $[0,1]$, with $\theta=0$ when (14) is degenerate. An empty $p^l$ period in step 4 follows the pseudo-code. The decision rules never take $d_m$, $\mathcal P_m$ or $z^*$ as arguments.
• The system. $M$ independent unit-rate Poisson processes (the published IsPoissonProcess) with right-continuous, jointly measurable paths. The inventory of the $n$-th system is $\lfloor nc\rfloor$ units, and nothing is sold after the stock-out. Lemmas 6–8 use the uncapped sales of the paper's modified system (§4).
• Asymptotics. "$O(f(n))$" is read as $\exists C$, independent of $n$ and the phase index, for all $n\ge3$. "Sufficiently small $\epsilon$" is read as every $\epsilon\in(0,\epsilon_0)$. The algorithm needs $n\ge3$ for $K$ to exist.
• Corrected misprints. Proposition 1.2 prints $\mathcal R_m'=-\sum_md_m(\mathcal P_m)$ with the index reused; the statement is $-d_m(\mathcal P_m(z))$. Proposition 1.3 and the global form of the bound in 1.1 fail at the kinks of $\mathcal P_m$. Part 1's derivative bound is stated as a Lipschitz bound, and part 3 is omitted. Lemmas 3–4 are stated in product form. Propositions 2–3 are stated through their regret conclusions. The printed comparison $\tilde J^\pi_n\le J^\pi_n$ (pp. 13–14) can fail when a last-phase price exceeds $\overline p$, so it is not used.

A formalization that lets the policy read the true demand, measures regret against anything other than $J^D_n$, ignores the stock-out in $J^\pi_n$, or assumes the high-probability events of Lemma 5 would trivialize the goal; none of these is done here.

Contributions to the reusable parts are welcome: Poisson tails, the envelope theorem for $\mathcal R_m$, and the time-change construction of policy-driven Poisson sales.

Selected references

• N. Chen, G. Gallego, A Primal-dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint, arXiv:1812.09234v3, 2021; Mathematics of Operations Research, 2022. https://arxiv.org/abs/1812.09234
• O. Besbes, A. Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6), 2009. https://doi.org/10.1287/opre.1080.0640
• Z. Wang, S. Deng, Y. Ye, Close the Gaps: A Learning-While-Doing Algorithm for Single-Product Revenue Management Problems, Operations Research 62(2), 2014. https://doi.org/10.1287/opre.2013.1249
• G. Gallego, G. van Ryzin, A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management, Operations Research 45(1), 1997. https://doi.org/10.1287/opre.45.1.24

Motivation

The simplex method for linear programming moves from vertex to vertex along the edges of a polyhedron. A lower bound on the number of pivots of any edge-following method is the graph diameter of the feasible polyhedron: the largest number of edges needed to connect two of its vertices. Whether this diameter is bounded by a polynomial in the dimension $d$ and the number $n$ of facets is the polynomial Hirsch conjecture, open since the 1950s. The original Hirsch conjecture, $n-d$, was refuted for unbounded polyhedra by Klee and Walkup (1967) and for bounded ones by Santos (2012) (doi:10.4007/annals.2012.176.1.7).

Timeline.

• 1964–1966. Klee proves that a three-dimensional polyhedron with $n$ facets, bounded or not, has diameter at most $n-3$ (doi:10.4153/CJM-1964-058-3, doi:10.1137/0113061, doi:10.2140/pjm.1966.17.249).
• 1967. Klee and Walkup show that the Hirsch bound fails for unbounded polyhedra in dimension four (doi:10.1007/BF02395039).
• 1992. Kalai and Kleitman prove the first subexponential bound, $n^{\log_2 d+2}$, for all polyhedra (doi:10.1090/S0273-0979-1992-00285-9, arXiv:math/9204233).
• 2010. Eisenbrand, Hähnle, Razborov and Rothvoss show that $n^{\log_2 d+1}$ holds for a broad combinatorial abstraction of polyhedra (doi:10.1287/moor.1100.0470).
• 2014. Todd sharpens the Kalai–Kleitman bound to $(n-d)^{\log_2 d}$ for all polyhedra, bounded or not (arXiv:1402.3579; SIAM J. Discrete Math. 28 (2014), doi:10.1137/140962310). This is the result of this mission.

Setting

A polyhedron $P\subseteq\mathbb R^d$ is the set of solutions of finitely many linear inequalities,

$$P=\operatorname{Hpoly}(a,b)=\{x\in\mathbb R^d:\ \langle a_i,x\rangle\le b_i,\ i=1,\dots,n\}.$$

It need not be bounded. A vertex of $P$ is a point $v$ for which some half-space $H$ satisfies $P\cap H=\{v\}$, equivalently an extreme point of $P$. Two vertices $v\neq w$ are adjacent when $P\cap H=[v,w]$ for some half-space $H$; the segment $[v,w]$ is then an edge. A path of length $k$ is a sequence of vertices $v=v_0,\dots,v_k=w$ with consecutive vertices adjacent, $\rho_P(v,w)$ is the least such $k$, and the diameter is $\delta(P)=\max\rho_P(v,w)$ over pairs of vertices. A $(d,n)$-polyhedron is a $d$-dimensional polyhedron with $n$ facets, and

$$\Delta(d,n)=\max\{\delta(P):\ P \text{ a } (d,n)\text{-polyhedron}\},$$

the maximum taken over bounded and unbounded polyhedra alike. All logarithms are to base 2.

Formalization targets

Goal: Theorem 1

$$\Delta(d,n)\le (n-d)^{\log d}\quad(1\le d\le n),\qquad \Delta(1,1)=0.$$

The goal fixes no constant beyond the paper's own exponent and leaves no case of $d$, $n$ or boundedness open.

Milestones, in the order the proof uses them

1. The identity $(n-d)^{\log d}=d^{\log(n-d)}$ (p. 2).
2. Two vertices on a common facet are at distance at most $\Delta(d-1,n-1)$ (p. 2, in the proof of Lemma 1).
3. Lemma 1 (Kalai–Kleitman): for $2\le d\le\lfloor n/2\rfloor$, $\Delta(d,n)\le\Delta(d-1,n-1)+2\Delta(d,\lfloor n/2\rfloor)+2$.
4. $\Delta(d,d)=0$.
5. $\Delta(1,n)\le 1$.
6. $\Delta(2,n)\le n-2$.
7. $\Delta(3,n)\le n-3$ (Klee), for unbounded polyhedra too.
8. If $n<2d$, then $\Delta(d,n)\le\Delta(d-1,n-1)$.
9. In the ten cases $d=4,\ 8\le n\le 11$; $d=5,\ 10\le n\le 12$; $d=6,\ 12\le n\le 13$; $d=7,\ n=14$, the bound $\lfloor (n-d)^{\log d}\rfloor$ satisfies the recursion of Lemma 1.
10. For $d\ge4$, $n-d\ge8$, $n\ge 2d$: $(d-1)^{\log(n-d)}+2(n/2-d)^{\log d}+2\le d^{\log(n-d)}$. For $n>2d$ this is the displayed inequality; at $n=2d$ the second power is zero, consistent with $\Delta(d,d)=0$.

Significance

The result. The bound $(n-d)^{\log d}$ is never larger than the Kalai–Kleitman bound. It equals the true value $n-d$ in dimensions 1 and 2, and it depends on $n$ only through the Hirsch quantity $n-d$. Since $(n-d)^{\log d}=d^{\log(n-d)}$, it is also symmetric under linear-programming duality, which exchanges the roles of $d$ and $n-d$. For fixed $n-d$ it is polynomial in $d$. It applies to the unbounded feasible regions that arise in practice in linear programming.

Formalizing it. The theorem has been proved since 2014. The platform has a proof of the bounded case only: Hirsch.todd_bound assumes $d\ge3$, a nonempty interior and Bornology.IsBounded. This mission's goal extends it to all polyhedra, bounded or not, and to $d=1,2$. That is the statement the paper proves, and the one an analysis of the simplex method on unbounded feasible regions needs. The unbounded form of Lemma 1 and the common-facet bound are open on the platform as items of the Kalai–Kleitman series and are reused here. Klee's unbounded three-dimensional bound has no formal proof on the platform: the published Hirsch.klee_three_dimensional_bound and Hirsch.dimension_three_bound cover bounded polyhedra only. The bounded recursion Hirsch.kalai_kleitman_recursion and the bounded facet reduction Hirsch.facet_reduction are proved and may serve as models.

Difficulty

Two steps are hard. The first is the unbounded case. Statements proved for polytopes do not transfer directly, because an unbounded polyhedron may have no vertices or a single one, unbounded edges (rays) that are not edges of the graph, and redundant or implicit-equality rows. Each geometric milestone must hold for these. The second is Klee's three-dimensional bound, which the paper cites without proof. Assuming boundedness to apply the published polytope versions is ruled out: Klee and Walkup showed that unbounded and bounded diameters differ from dimension four on, so the unbounded case carries content of its own. The arithmetic milestones are elementary but sensitive to edge values of $\log$ and the real power.

Formalization scope

All statements use the published definitions Hirsch.Hpoly, Hirsch.Adj and Hirsch.DiamLE (Hirsch_model). Vertices are Set.extremePoints ℝ. DiamLE P B says that any two extreme points are joined by a walk of exactly $B$ steps, each step staying put or crossing an edge. So the bound includes connectivity of the vertex–edge graph.

• Inequality reading. "$\Delta(d,n)\le B$" is stated as: for every $a:\mathrm{Fin}\,n\to\mathbb R^d$ and $b$, DiamLE (Hpoly a b) B. This ranges over all polyhedra given by $n$ inequalities in $\mathbb R^d$, including lower-dimensional, empty and redundant ones. It is equivalent to the paper's statement: a lower-dimensional polyhedron of dimension $d'$ with $n'$ facets has $n'-d'\le n-d$.
• No boundedness, nonemptiness or full-dimensionality is assumed anywhere.
• The logarithm is Real.logb 2 and the power is Real.rpow. A distance is at most $(n-d)^{\log d}$ exactly when it is at most the floor $\lfloor (n-d)^{\log d}\rfloor$, abbreviated toddBound d n in the milestone on the ten cases. The clause $\Delta(1,1)=0$ is a separate conjunct, because $0^0=1$ in Real.rpow.
• Disclosed additions: nonzero rows in the $n<2d$ step (as in the referenced Lemma 1 and the $d=2$ bound). In the general step, $n\ge2d$: the paper secures it by treating $n<2d$ first. The second power is written with base $n/2-d$; it equals the printed expression when $n>2d$ and takes the intended value zero when $n=2d$, where the printed logarithm is undefined.
• Natural-number subtraction appears in $n-3$ and $n-2$ (both harmless, since for small $n$ there are no vertices) and in $\mathbb R^{d-1}$ for facets.

Trivializing encodings are excluded: no Bornology.IsBounded hypothesis; no definition of $\Delta$ by sSup over $\mathbb N$, which would be $0$ on unbounded families; no use of Hirsch.gdist, which is $0$ when no walk exists; and no dropping of the $\Delta(1,1)=0$ clause.

Contributions are welcome on every milestone. A complete development needs facial structure of unbounded polyhedra (facets as polyhedra one dimension lower, tight rows at vertices), the relaxation argument of Lemma 1, Klee's three-dimensional argument, and real-power and logarithm estimates. The facet machinery and Klee's bound are reusable for any diameter result on unbounded polyhedra.

Selected references

• M. J. Todd, An improved Kalai–Kleitman bound for the diameter of a polyhedron, SIAM J. Discrete Math. 28 (2014); arXiv:1402.3579v2. arXiv:1402.3579, doi:10.1137/140962310
• G. Kalai and D. J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Amer. Math. Soc. 26 (1992), 315–316. doi:10.1090/S0273-0979-1992-00285-9
• V. Klee, Diameters of polyhedral graphs, Canad. J. Math. 16 (1964), 602–614. doi:10.4153/CJM-1964-058-3
• V. Klee, Paths on polyhedra I, J. SIAM 13 (1965), 946–956. doi:10.1137/0113061
• V. Klee, Paths on polyhedra II, Pacific J. Math. 17 (1966), 249–262. doi:10.2140/pjm.1966.17.249
• V. Klee and D. W. Walkup, The d-step conjecture for polyhedra of dimension d < 6, Acta Math. 117 (1967), 53–78. doi:10.1007/BF02395039
• F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoss, Diameter of polyhedra: limits of abstraction, Math. Oper. Res. 35 (2010), 786–794. doi:10.1287/moor.1100.0470
• F. Santos, A counterexample to the Hirsch conjecture, Ann. of Math. 176 (2012), 383–412. doi:10.4007/annals.2012.176.1.7

Motivation

In a congestion game, each player chooses resources and pays a cost that depends on how many players use each chosen resource. Such games model shared facilities and network use, where independently chosen strategies can cost more in total than a coordinated choice. The price of anarchy measures this inefficiency by comparing the social cost of an equilibrium with the minimum social cost. A familiar way to bound it is to prove a smoothness inequality that applies to every pair of strategy profiles. That inequality has a useful reach: once established, it bounds not only pure Nash equilibria but also broader equilibrium notions. The question in this mission is how much that reach costs in sharpness. Roughgarden (2015) proves that for congestion games it costs nothing at the level of the worst case over any fixed collection of allowed resource cost functions.

For affine resource costs, earlier analyses had already identified a worst-case value of $5/2$, attained by a finite congestion game and matched by a smoothness bound. The 2015 paper asks whether this agreement reflects affine costs or a general property of congestion games. Its Theorem 5.8 gives the latter answer, even when the collection of allowed functions is infinite and has no prescribed formula. The mission treats the theorem at that generality, while giving the finite positive case and the boundary case their own supporting targets. Roughgarden (2015), §§2.3 and 5.

Setting

A finite congestion game has a finite player set, a finite resource set $E$, and for each player $i$ a nonempty set $S_i$ of subsets of $E$ called strategies. Each resource $e$ has a cost function $c_e:\mathbb N\to\mathbb R$. For a strategy profile $A=(A_i)_i$, its load $x_e(A)$ is the number of players whose selected strategy contains $e$. Player $i$ pays $C_i(A)=\sum_{e\in A_i}c_e(x_e(A))$, and the social cost is $C(A)=\sum_i C_i(A)$. A profile is a pure Nash equilibrium when no player can lower its own cost by changing its strategy alone. These are the objects of Example 2.5 in Roughgarden (2015).

Fix a nonempty set $\mathcal C$ of resource cost functions, each nonnegative, nondecreasing, and not identically zero on positive loads. The class $\mathcal G(\mathcal C)$ contains every finite congestion game whose resource functions belong to $\mathcal C$. It permits any finite number of players and resources and any nonempty strategy families. The pure price of anarchy $\rho_{\mathrm{pure}}(G)$ is the largest equilibrium-to-optimum cost ratio in one game, allowing $+\infty$ when an equilibrium costs more than zero but the optimum costs zero.

A game is $(\lambda,\mu)$-smooth if, for every two feasible profiles $A,A^*$, the sum of the player costs after each player individually switches from $A_i$ to $A_i^*$ is at most $\lambda C(A^*)+\mu C(A)$. The set $\mathcal A(\mathcal G(\mathcal C))$ consists of pairs with $\mu<1$ that satisfy this inequality for every game in the class. A related resourcewise set $\mathcal A(\mathcal C)$ asks, for every $c\in\mathcal C$, current load $x\ge0$, and comparison load $x^*\ge1$, that

$$c(x+1)x^*\le\lambda c(x^*)x^*+\mu c(x)x.$$

Its best ratio is $\gamma(\mathcal C)=\inf_{(\lambda,\mu)\in\mathcal A(\mathcal C)}\lambda/(1-\mu)$, with value $+\infty$ if there is no admissible pair. The bounded-load versions $\mathcal A(\mathcal C,n)$ and $\gamma(\mathcal C,n)$ use $0\le x\le n$ and $1\le x^*\le n$. Roughgarden (2015), equations (34)–(36) and (41).

Formalization targets

Tightness of the congestion-game class

Theorem 5.8, in the form of equation (34), is the goal:

$$\sup_{G\in\mathcal G(\mathcal C)}\rho_{\mathrm{pure}}(G) =\inf_{(\lambda,\mu)\in\mathcal A(\mathcal G(\mathcal C))}\frac{\lambda}{1-\mu}.$$

It applies to every nonempty set $\mathcal C$ satisfying the standing cost-function conditions, whether finite, countable, or uncountable. Neither the number of players nor the number of resources is fixed. The equality is stronger than the routine upper bound from smoothness: it says that the best upper bound available from a uniform smoothness argument matches actual worst-case pure-equilibrium inefficiency. Roughgarden (2015), Theorem 5.8 and (34).

Resourcewise characterization

The paper also identifies the common value with $\gamma(\mathcal C)$:

$$\sup_{G\in\mathcal G(\mathcal C)}\rho_{\mathrm{pure}}(G)=\gamma(\mathcal C).$$

The milestone list follows the paper's statements: the general upper bound; nonnegativity of $\mu$; passage from resource constraints to game smoothness; the bound for one game; the two finite optimization lemmas; the finite lower-bound theorem; the infinite-price boundary case; the countable case; and the characterization by $\gamma(\mathcal C)$. The finite lower-bound target uses the one-sided conclusion established in the proof of Theorem 5.6. Roughgarden (2015), §§5.1–5.5.

Significance

The equality rules out a uniform improvement of the worst-case pure price-of-anarchy bound by using features of pure Nash equilibrium that a smoothness argument ignores. In this domain the broader applicability of smoothness does not force a worse class-wide bound. For a chosen cost-function family, the resourcewise characterization expresses that bound through explicit inequalities rather than a search over every possible finite game. Roughgarden (2015), §§2.4 and 5.5.

The result is proved in the paper. The remaining work here is a machine-checked proof of its formal statement and supporting theorems. The published congestion-game model supplies loads, player costs, feasible profiles, and pure Nash equilibria. The definitions of smoothness parameters and prices of anarchy built for this mission can also support later work on other cost-function classes and equilibrium bounds. The goal statement itself is a proof target, not an already verified result.

Difficulty

The smoothness inequality immediately gives an upper bound on equilibrium costs, but it does not by itself show that a game attains or approaches that bound. The difficult direction relates a small family of resourcewise constraints to actual games with inefficient equilibria. For finite positive cost-function sets, the optimum parameter value may be attained or may be approached only at infinity in parameter space; the two cases have different statements in Lemmas 5.3 and 5.5. The general theorem must also cover functions that vanish at a positive load, unbounded worst-case ratios, and sets of functions of arbitrary cardinality. Simply optimizing a bound for one fixed game would miss the supremum over the entire class. Roughgarden (2015), §§5.2–5.4.

Formalization scope

Lean represents players and resources by Fin k and Fin m and quantifies over every $k,m\in\mathbb N$. A strategy is a finite resource subset, a strategy family is finite and nonempty, and all costs are real-valued at each load. The value $c(0)$ is unrestricted because it is unused in a player's cost and is multiplied by zero in (35). The all-zero function is excluded as in §5.1. Nonemptiness of $\mathcal C$, stated at the start of that section, is carried into the finite optimization lemmas because their conclusions select functions from $\mathcal C$. Zero-player and zero-resource games are allowed and do not raise the worst-case supremum.

Prices of anarchy and the values $\gamma$ are extended nonnegative reals. Thus an empty smoothness-parameter set has infimum $+\infty$; a positive equilibrium cost over zero optimum gives $+\infty$; and a game with no equilibrium contributes zero to the supremum. The paper's finite congestion games with nonempty strategy sets do have pure equilibria. The conversion of a real ratio $\lambda/(1-\mu)$ into this type does not truncate admissible class-wide ratios: if some cost function has $c(1)>0$, a one-resource game forces the ratio to be at least one; if none does, the parameter set is empty. Smoothness and optimum quantify over feasible profiles only. These choices prevent the equality from becoming vacuous through an empty real infimum, total division by zero, or a supremum over a fixed small game size.

The complete development needs finite-set sums, function updates, extended nonnegative infima and suprema, and the published congestion-game definitions. Reusable contributions include lemmas about the resourcewise parameter sets and their relation to game smoothness. The paper's uncountable approximation paragraph has a gap for flat cost functions; the theorem remains the stated target, and a formal proof may use a different argument at that stage. Roughgarden (2015), pp. 31–32.

Selected references

• Tim Roughgarden, Intrinsic Robustness of the Price of Anarchy, Journal of the ACM 62(5), Article 32, 2015. DOI. The source used here is the author's final version dated July 14, 2015; the cited page numbers are its printed pages.

Motivation

In a stochastic multi-armed bandit, a player repeatedly chooses one of $K$ arms and receives a random reward drawn from the chosen arm's unknown distribution. The classical lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996) describe the regret of good strategies when the horizon $T$ tends to infinity: it grows like $\ln T$, with a constant determined by Kullback–Leibler divergences. They say nothing about small horizons.

Garivier, Ménard and Stoltz (Math. Oper. Res., 2019; arXiv:1602.07182v3) show that the regret has a definite shape over the whole range of $T$: it is almost linear at first ("explore first"), and only afterwards logarithmic ("exploit next"). Their §3 gives three non-asymptotic lower bounds for the initial phase, each for a natural class of strategies. This mission is the third of them, Theorem 4 (p. 13): a collective lower bound on the total number of pulls of all suboptimal arms. It is the bound that remains informative when many arms are suboptimal, and it is the one illustrated for large $K$ in the paper's §3.4.

Setting

A bandit problem $\underline\nu=(\nu_a)_{a=1,\dots,K}$ is a family of probability distributions on $\mathbb R$, each with an expectation $\mu_a=E(\nu_a)$. A model $\mathcal D$ is a set of such distributions, and $\underline\nu$ is in $\mathcal D$ when every $\nu_a\in\mathcal D$. Put $\mu^\star=\max_a\mu_a$.

At each round $t\ge1$ a strategy $\psi$ chooses an arm $A_t$ from the past rewards (possibly with auxiliary randomization) and observes a reward $Y_t\sim\nu_{A_t}$. The number of pulls of arm $a$ up to round $T$ is $N_{\psi,a}(T)=\sum_{t=1}^T\mathbb 1\{A_t=a\}$, and $\mathbb E_{\underline\nu}$ is the expectation when $\psi$ interacts with $\underline\nu$.

The set of optimal arms is $\mathcal A^\star(\underline\nu)=\{a:\mu_a=\mu^\star\}$, of cardinality $A^\star_{\underline\nu}$, and the set of worst arms is $\mathcal W(\underline\nu)$, the arms of smallest mean. The paper defines a partial order: $\underline\nu'\preccurlyeq\underline\nu$ when $\nu'_a=\nu_a$ for every optimal arm $a$ of $\underline\nu$ and $E(\nu'_a)\le E(\nu_a)$ for every other arm. Two classes of strategies enter the theorem.

1. $\psi$ is pairwise symmetric for optimal arms on $\mathcal D$ (Definition 3, p. 11) if, for every $\underline\nu$ in $\mathcal D$ and every pair of optimal arms $a^\star,a_\star$ with $\nu_{a^\star}=\nu_{a_\star}$, for all $T\ge1$, the pairs $(N_{\psi,a^\star}(T),N_{\psi,a_\star}(T))$ and $(N_{\psi,a_\star}(T),N_{\psi,a^\star}(T))$ have the same distribution.
2. $\psi$ is monotonic on $\mathcal D$ (Definition 4, p. 13) if for all $\underline\nu'\preccurlyeq\underline\nu$ in $\mathcal D$, $\sum_{a^\star\in\mathcal A^\star(\underline\nu')}\mathbb E_{\underline\nu'}[N_{\psi,a^\star}(T)]\ge\sum_{a^\star\in\mathcal A^\star(\underline\nu)}\mathbb E_{\underline\nu}[N_{\psi,a^\star}(T)]$: on an easier problem the optimal arms are pulled at least as often.

With $\mathrm{KL}$ the Kullback–Leibler divergence, the constant of the theorem is

$$\mathcal K^{\max}_{\underline\nu}=\min_{w\in\mathcal W(\underline\nu)}\ \max_{a^\star\in\mathcal A^\star(\underline\nu)}\mathrm{KL}(\nu_w,\nu_{a^\star}).$$

The Bernoulli divergence is $\mathrm{kl}(p,q)=p\ln\frac pq+(1-p)\ln\frac{1-p}{1-q}$, (5).

Formalization targets

Goal: Theorem 4 (main display), p. 13

For every model $\mathcal D$, every strategy $\psi$ pairwise symmetric for optimal arms and monotonic on $\mathcal D$, every bandit problem $\underline\nu$ in $\mathcal D$ and every $T\ge1$,

$$\sum_{a\notin\mathcal A^\star(\underline\nu)}\mathbb E_{\underline\nu}\big[N_{\psi,a}(T)\big]\ \ge\ T\left(1-\frac{A^\star_{\underline\nu}}K-\frac{A^\star_{\underline\nu}\sqrt{2T\mathcal K^{\max}_{\underline\nu}}}K-\frac{2A^\star_{\underline\nu}T\mathcal K^{\max}_{\underline\nu}}K\right).$$

Milestones, in the order of the paper's proof

1. Lemma 2 (p. 14): if $(x-\alpha)^2\le\beta x$ with $\alpha,\beta\ge0$, then $x\le\alpha+\beta+\sqrt{\alpha\beta}$.
2. Lemma 6 (p. 20): for $0\le p<q\le1$, $\mathrm{kl}(p,q)\ge(p-q)^2/(2\max_{x\in[p,q]}x(1-x))\ge(p-q)^2/(2q)$.
3. Monotonicity reduction (p. 13): with $\tilde w$ a worst arm and $\underline{\underline\nu}$ equal to $\underline\nu$ on the optimal arms and to $\nu_{\tilde w}$ elsewhere, $\sum_{a\notin\mathcal A^\star(\underline\nu)}\mathbb E_{\underline\nu}[N_{\psi,a}(T)]\ge\sum_{a\notin\mathcal A^\star(\underline{\underline\nu})}\mathbb E_{\underline{\underline\nu}}[N_{\psi,a}(T)]$.
4. Uniform split (p. 13): if all arms of $\underline{\tilde\nu}$ carry the same distribution, $\mathbb E_{\underline{\tilde\nu}}[N_{\psi,a}(T)]=T/K$ for every arm.
5. The kl display (p. 14): $T A^\star_{\underline\nu}\mathcal K^{\max}_{\underline\nu}/K\ge\mathrm{kl}(A^\star_{\underline\nu}/K,x)$ with $x=\frac1T\sum_{a^\star\in\mathcal A^\star(\underline\nu)}\mathbb E_{\underline{\underline\nu}}[N_{\psi,a^\star}(T)]$.
6. Equation (14) (p. 14): $x\le\frac{A^\star_{\underline\nu}}K\big(1+2T\mathcal K^{\max}_{\underline\nu}+\sqrt{2T\mathcal K^{\max}_{\underline\nu}}\big)$.

Significance

Theorem 4 bounds the regret from below through $R_{\psi,\underline\nu,T}\ge(\min_{a\notin\mathcal A^\star}\Delta_a)\sum_{a\notin\mathcal A^\star}\mathbb E_{\underline\nu}[N_{\psi,a}(T)]$, (13). While $T$ is small compared with $K/(A^\star_{\underline\nu}\mathcal K^{\max}_{\underline\nu})$, the right-hand side of the theorem is of order $T(1-A^\star/K)$, so the regret is linear: a reasonable strategy cannot avoid spending a constant fraction of the first rounds on the suboptimal arms. Unlike the per-arm bounds of Theorems 2 and 3, the bound concerns all suboptimal arms at once and does not degrade as $K$ grows; §3.4 of the paper shows numerically that it gives the stronger regret bound for many arms.

The theorem is proved in the paper; to our knowledge no part of it has been machine-checked. A formal proof would exercise the published canonical bandit model of the platform (StochasticBandit, BanditPolicy, banditMeasure) on a genuine lower-bound argument with two auxiliary bandit problems, together with a local Pinsker inequality for Bernoulli divergences in $[0,+\infty]$ that is reusable in other bandit lower bounds.

Difficulty

The obvious attempt applies the fundamental inequality (6) to $\underline\nu$ and an alternative in which one suboptimal arm becomes optimal, as in Theorem 2. That gives a bound arm by arm, which deteriorates with $K$ and does not see the number $A^\star$ of optimal arms; it also needs a hypothesis of the type "smarter than uniform", which is not assumed here. Nothing is known about how a general $\psi$ behaves on $\underline\nu$ itself, so the two hypotheses on $\psi$ must carry all the information, and both are weak: Definition 3 only constrains pairs of optimal arms with equal laws, and only through the joint distribution of their pull counts under the canonical bandit measure; Definition 4 only compares problems ordered by $\preccurlyeq$. On the analytic side, the classical Pinsker inequality $\mathrm{kl}(p,q)\ge2(p-q)^2$ loses the factor $A^\star/K$ and gives a weaker theorem, so a local refinement is required, and every divergence is valued in $[0,+\infty]$.

Formalization scope

Arms are indexed by Fin K (the paper's arm $a$ is index $a-1$), with $K\ge1$ assumed in the goal. A bandit problem is the published BanditAlgorithm.StochasticBandit K, a strategy is a published BanditPolicy K (a family of Markov kernels from histories to arms; every strategy of the paper with auxiliary uniform randomization induces one with the same law of arms and rewards), and $\mathbb E_{\underline\nu}[N_{\psi,a}(T)]$ is the integral of the pull count against banditMeasure. A model is a Set (Measure ℝ) whose members are probability measures with an integrable identity, the standing assumption of §1.1–§1.2. Definitions 3 and 4 leave $T$ implicit and are read "for all $T\ge1$"; in Definition 3 equality of distributions is equality of the image measures of the pair of counts, not of their expectations. $\mathrm{KL}$, $\mathrm{kl}$ and $\mathcal K^{\max}$ take values in $[0,+\infty]$; the goal assumes $\mathcal K^{\max}_{\underline\nu}<+\infty$, since otherwise the printed bound is $-\infty$ and a real-valued conversion would silently replace $+\infty$ by $0$. The Bernoulli divergence is defined as the divergence between two Bernoulli laws on $\mathbb R$, so it is $+\infty$ where (5) is, rather than a finite junk value. The auxiliary problems of the proof are not constructed; the milestones quantify over them with their defining properties.

The paper's "In particular" clause, $\sum_{a\notin\mathcal A^\star}\mathbb E[N_{\psi,a}(T)]\ge\frac T2(1-A^\star/K)$ for $T\le K/(8A^\star\mathcal K^{\max})$, is not stated: it follows from the main display only when $A^\star/K+\sqrt{A^\star/K}\le1/2$ (at $A^\star/K=1/2$ the main bound is negative), and whether it holds in general is not known here.

A formalization that weakens the strategy classes (full permutation symmetry, or equality of expected counts in Definition 3), drops the requirement that the problems lie in the model, or uses a real Bernoulli divergence with finite values at $q\in\{0,1\}$ does not count.

A complete development needs the fundamental inequality (6) on the canonical bandit model (the subject of mission I of this series; the chain rule for the divergence of bandit measures is already proved on the platform), the symmetry argument on the canonical measure, Lemma 6 and Lemma 2. Contributions of any of these, and of the identity $\sum_a N_{\psi,a}(T)=T$ integrated against banditMeasure, are welcome; Lemma 6 and the symmetry lemma are reusable beyond this mission.

Selected references

• A. Garivier, P. Ménard, G. Stoltz, Explore First, Exploit Next: The True Shape of Regret in Bandit Problems, Mathematics of Operations Research, 2019; arXiv:1602.07182v3. https://arxiv.org/abs/1602.07182, https://doi.org/10.1287/moor.2017.0928
• T. L. Lai, H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 1985. https://doi.org/10.1016/0196-8858(85)90002-8
• A. N. Burnetas, M. N. Katehakis, Optimal adaptive policies for sequential allocation problems, Advances in Applied Mathematics, 1996. https://doi.org/10.1006/aama.1996.0007
• T. Lattimore, Cs. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020. https://doi.org/10.1017/9781108571401