Bandit Algorithms

Why price without knowing demand

A seller with a fixed stock of a single product and a finite selling season has to set prices without knowing how demand responds to them. This is the standard situation in revenue management: airline seats, hotel rooms, fashion goods and event tickets. The classical theory of dynamic pricing (Gallego and van Ryzin, 1994) assumes that the demand function $\lambda(p)$, the rate of purchase requests at price $p$, is known. In practice it has to be learned from sales, while the season runs and the stock is consumed.

Besbes and Zeevi (2009) asked how much revenue is lost for not knowing $\lambda$. They answered it with explicit policies and matching-order bounds. Their setting differs from the multi-armed bandit literature it borrows from in three ways:

• the problem is constrained by an initial inventory;
• the set of prices is a continuum;
• the set of possible demand functions is a nonparametric class.

This mission formalizes their first main result, Proposition 1: a simple learn-then-price policy has worst-case relative regret of order $(\log n)^{1/2}n^{-1/4}$ in a market of size $n$.

Setting

Prices. Fix $0<\underline p<\overline p<\infty$ and an off price $p_\infty>0$ outside $[\underline p,\overline p]$. The seller may charge any price in $[\underline p,\overline p]\cup\{p_\infty\}$; charging $p_\infty$ stops demand.

Demand. Requests arrive as a Poisson process whose intensity at time $t$ is $\lambda(p(t))$. Let $N$ be a unit-rate Poisson process. By the time change (1), the cumulative requests up to time $t$ under a price path $p(\cdot)$ are $N\big(\int_0^t\lambda(p(s))\,ds\big)$. The seller starts with inventory $x$ and sells until either the horizon $T$ ends or the stock runs out. The expected revenue of a policy $\pi$ is $J^\pi(x,T;\lambda)$.

Demand class. $\mathcal L=\mathcal L(M,\underline K,\overline K,m)$ is the set of regular demand functions satisfying Assumption 1. Regular means:

• $\lambda\ge0$ and $\lambda(p_\infty)=0$;
• $\lambda$ is non-increasing on $[\underline p,\overline p]$, with inverse $\gamma$;
• the revenue rate $r(l)=l\gamma(l)$ is concave.

Assumption 1 requires:

• (i) $\lambda\le M$ on $[\underline p,\overline p]$;
• (ii) $\lambda$ is $\overline K$-Lipschitz and $\gamma$ is $\underline K^{-1}$-Lipschitz;
• (iii) $\max_p p\lambda(p)\ge m$.

Benchmark. The deterministic relaxation (5) replaces the random demand by its mean:

$$J^D(x,T\mid\lambda)=\sup\Big\{\int_0^T p(s)\lambda(p(s))\,ds:\int_0^T\lambda(p(s))\,ds\le x\Big\}.$$

The regret of a policy is $\mathcal R^\pi=1-J^\pi/J^D$.

Scaling. In a market of size $n$ the inventory is $nx$ and the demand function is $n\lambda$, as in (11). The corresponding quantities are $J^\pi_n$, $J^D_n=nJ^D$ and $\mathcal R^\pi_n$.

Algorithm 1, $\pi(\tau,\kappa)$. The policy has three phases.

1. Learning. On $[0,\tau]$ it tests $\kappa$ equally spaced prices $p_i=\underline p+(i-1)(\overline p-\underline p)/\kappa$, each for $\Delta=\tau/\kappa$ time units. It estimates $\lambda(p_i)$ by the normalized request counts $\hat\lambda(p_i)$.
2. Optimization. It chooses $\hat p^u=\arg\max_i p_i\hat\lambda(p_i)$ and $\hat p^c=\arg\min_i|\hat\lambda(p_i)-x/T|$, and sets $\hat p=\max\{\hat p^u,\hat p^c\}$.
3. Pricing. It charges $\hat p$ on $(\tau,T]$ until the stock runs out.

Formalization targets

Goal: Proposition 1

Let $\tau_n\asymp n^{-1/4}$ and $\kappa_n\asymp n^{1/4}$, and let $\pi_n=\pi(\tau_n,\kappa_n)$. Then there is a finite constant $C$, independent of $\lambda$ and $n$, such that

$$\sup_{\lambda\in\mathcal L}\mathcal R^{\pi}_n(x,T;\lambda)\le\frac{C(\log n)^{1/2}}{n^{1/4}}\qquad(n\ge2).$$

The constant is left unspecified, as in the paper. Its dependence on the class parameters, $x$ and $T$ is "somewhat complex" (p. 12), and the order $(\log n)^{1/2}n^{-1/4}$ is the content of the result.

Milestones

The milestones follow the proof in the appendix, in order:

• the scaling $J^D_n=nJ^D$ (p. 12);
• Fact 1, $J^D\ge m\min\{T,x/M\}$ on $\mathcal L$;
• Lemma 1, the solution of (5): charge $p^D=\max\{p^u,p^c\}$ until the stock runs out;
• Lemma 2, a Poisson deviation bound;
• the revenue lower bound (A-2);
• Lemma 3, the learned price is near $p^D$ with high probability;
• Lemma 4 and the Case 1 bound (A-11), for $\lambda(\overline p)\le x/T$;
• Lemma 5 and the Case 2 bound (A-15), for $\lambda(\overline p)>x/T$;
• the Step 4 bound $\mathcal R^\pi_n\le C_{12}(u_n+\tau_n)$, where $u_n=(\log n)^{1/2}\max\{1/\kappa_n,(n\Delta_n)^{-1/2}\}$.

Significance

Proposition 1 shows that a seller who knows only a nonparametric class of demand functions can approach the full-information revenue uniformly over the class. Learning costs a vanishing fraction of revenue, and the policy needs no parametric model. Together with the paper's lower bound of order $n^{-1/2}$ for every admissible policy (Proposition 2, not in this mission), it brackets the minimax regret of nonparametric pricing under an inventory constraint. The result is a reference point for the learning-and-earning literature in operations management that followed it.

The result is proved in the paper; to our knowledge, it has no machine-checked proof. Formalizing it requires:

• a working theory of policies driven by a time-changed Poisson process, with sales capped by an inventory;
• the deterministic relaxation of Gallego and van Ryzin for a continuum of prices with an off price;
• uniform (over the class) Poisson concentration bounds.

The mission produces Lean statements of all of these. A proof would also check every constant chain of the appendix, where the argument uses some displays in a form slightly different from their printed statement (see the scope section).

Difficulty

The obvious argument controls the estimation error at the tested prices and concludes that $\hat p$ is close to the optimal price. It breaks in two places.

First, $p^D$ is the larger of two prices, the revenue maximizer and the price that sells the inventory exactly. Near the boundary between these regimes, the revenue rate at $\hat p$ is not controlled by the error in $\hat p$ alone: it needs the concavity of the revenue rate and the inverse Lipschitz bound on $\gamma$.

Second, when demand at the highest price exceeds the inventory rate ($\lambda(\overline p)>x/T$), the revenue is limited by stock-outs rather than by the price. The bound must then show that nearly all of the inventory is sold during the pricing phase, uniformly over the class.

Throughout, every constant must be independent of the demand function, so the estimates have to hold uniformly over an infinite-dimensional class.

Formalization scope

• Poisson process. The demand is driven by IsPoissonProcess N 1 on a probability space $(\Omega,\mathbb P)$, a published platform definition: ℕ-valued, $N(0)=0$, monotone paths, independent Poisson increments. The time change (1) is rendered by evaluating $N$ at cumulative intensities.
• Inventory. The inventory of the market of size $n$ is $\lfloor nx\rfloor$ units, and sales are $\min\{N(\cdot),\lfloor nx\rfloor\}$. The cap is never dropped.
• Revenue. $J^\pi_n$ is the Bochner expectation of a bounded, finitely-valued revenue, so it is a genuine integral.
• Demand functions. A demand function is a map $\mathbb R\to\mathbb R$, nonnegative, with $\lambda(p_\infty)=0$. Regularity and Assumption 1 are imposed on $[\underline p,\overline p]$, and the inverse $\gamma$ is Function.invFunOn.
• Benchmark. $J^D$ is a supremum over measurable price paths with integrable demand rate. The supremum is genuine: the set of path revenues is nonempty and bounded.
• Algorithm. The grid excludes $\overline p$, as in the paper. Ties in the grid argmax and argmin go to the smallest index. The estimates compare $\hat\lambda(p_i)$ with $x/T$.
• Tuning. $\tau_n\asymp n^{-1/4}$ and $\kappa_n\asymp n^{1/4}$ are encoded with explicit constants $0<c\le c'$, with $\tau_n\in(0,T]$ and $\kappa_n\ge1$. Constants may depend on $c,c'$, the class parameters, the prices, $x$ and $T$, but never on $\lambda$ or $n$.
• Range of $n$. Bounds whose right side vanishes at $n=1$ because $\log1=0$ are stated for $n\ge2$: the goal and (A-15).
• Typo correction. Lemma 5's event uses $nx-C_9nu_n$, as in its proof, not the printed $nx-C_9u_n$.
• Ruled out. A specific demand curve, a fixed $n$, deterministic demand, a finite price set, a known $\lambda$, constants depending on $\lambda$, or dropping the inventory cap would each make the statement a different and easier theorem. None is used.
• Not included. The lower bound of Proposition 2 and the second assertion of Lemma 1 ($J^\pi\le J^D$ for all admissible policies) are not included.

Contributions are welcome at any level: proofs of the milestones (Fact 1, Lemma 1 and Lemma 2 are self-contained), measurability and integrability lemmas for the revenue functional, and a reusable Poisson concentration library built on Mathlib's poissonMeasure.

Selected references

• O. Besbes and A. Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6):1407–1420, 2009. https://doi.org/10.1287/opre.1080.0640
• G. Gallego and G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8):999–1020, 1994. https://doi.org/10.1287/mnsc.40.8.999
• K. Talluri and G. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2005. https://doi.org/10.1007/b139000

Motivation

Thompson Sampling is the oldest heuristic for the multi-armed bandit problem: proposed by Thompson in 1933, it plays each arm with the posterior probability that the arm is the best one. It is simple to implement, performs well empirically (Chapelle and Li, NIPS 2011), and has been used in production systems such as click-through-rate prediction for search advertising. For a long time, however, no finite-time regret guarantee was known for it: the analyses available before 2012 gave only $o(T)$ regret.

Agrawal and Goyal (arXiv:1111.1797, COLT 2012) gave the first logarithmic bounds on the expected regret of Thompson Sampling. This mission formalizes their bound for the general case of $N$ arms (their Theorem 2). A companion mission of the same series formalizes their two-armed bound (Theorem 1), whose proof is independent.

Timeline. Lai and Robbins (1985) proved that every consistent algorithm has regret at least of order $\sum_i \frac{\Delta_i}{D(\mu_i\|\mu_1)}\ln T$. Auer, Cesa-Bianchi and Fischer (2002) showed that UCB1 achieves $O(\sum_i \ln T/\Delta_i)$ in finite time. Agrawal and Goyal (2012) proved $O((\sum_a 1/\Delta_a^2)^2\ln T)$ for Thompson Sampling with $N$ arms; Kaufmann, Korda and Munos (2012) and Agrawal and Goyal (2013) later proved the asymptotically optimal constant for Bernoulli rewards.

Setting

A stochastic $N$-armed bandit has arms $1,\dots,N$. Arm $i$, when played, yields a random reward drawn from a fixed distribution $\nu_i$ supported in $[0,1]$, with mean $\mu_i$; rewards of an arm are i.i.d. and independent of the other arms. Arm $1$ is assumed to be the unique optimal arm, $\mu_1>\mu_i$ for $i\ne1$, and $\Delta_i=\mu_1-\mu_i>0$ is the gap of arm $i$.

Thompson Sampling for general stochastic bandits (Algorithm 2 of the paper) keeps, for each arm $i$, a count $S_i$ of successes and $F_i$ of failures, both starting at $0$. In each round $t$ it draws $\theta_i(t)\sim\mathrm{Beta}(S_i+1,F_i+1)$ independently for every arm, plays $i(t)=\arg\max_i\theta_i(t)$, observes a reward $\tilde r_t\sim\nu_{i(t)}$, performs a Bernoulli trial with success probability $\tilde r_t$, and increments $S_{i(t)}$ on success and $F_{i(t)}$ on failure.

The expected regret in time $T$ is

$$\mathbb E[\mathcal R(T)]=\mathbb E\Big[\sum_{t=1}^T(\mu^*-\mu_{i(t)})\Big],\qquad \mu^*=\max_i\mu_i,$$

the expectation being over the rewards, the Bernoulli trials and the posterior samples.

The proof works with the reward stacks $Z_{i,m}$: the outcome of the $m$-th Bernoulli trial of arm $i$, all independent. Then $s(j)=\sum_{m\le j}Z_{1,m}$, the number of successes in the first $j$ plays of arm $1$, is a $\mathrm{Binomial}(j,\mu_1)$ random variable. The other objects of the proof are the threshold $L_i=24\ln T/\Delta_i^2$, the saturated set $C(t)$ of suboptimal arms with at least $L_i$ plays before round $t$, the intervals $I_j$ between the $j$-th and $(j+1)$-th plays of arm $1$, and the counts $\gamma_j$ and $V_j^{\ell,a}$ defined in §4.

Formalization targets

Goal: Theorem 2

There is an absolute constant $C>0$ such that for every $N\ge2$, every instance as above and every horizon $T\ge2$,

$$\mathbb E[\mathcal R(T)]\le C\Big(\sum_{a=2}^N\frac{1}{\Delta_a^2}\Big)^2\ln T .$$

$C$ does not depend on $N$, on the reward distributions or on $T$.

Milestones

1. Lemma 4: with $E(t)$ the event that every saturated arm's sample lies within $\Delta_i/2$ of its mean, $\Pr(E(t))\ge1-4(N-1)/T^2$, also conditionally on $s(j)=s$.
2. Lemma 5 (Eq. (7)): the expected regret from saturated arms inside $I_j$ is at most $\mathbb E\big[\mathbb E[\gamma_j+1\mid s(j)]\sum_a\Delta_a\mathbb E[\min\{X(j,s(j),\mu_a+\Delta_a/2),T\}\mid s(j)]\big]$.
3. Lemma 1: $\mathbb E[X(j,s,y)]=1/F^B_{j+1,y}(s)-1$, where $X(j,s,y)$ counts the trials before an independent $\mathrm{Beta}(s+1,j-s+1)$ sample exceeds $y$.
4. Lemma 3: a three-case bound on $\mathbb E[\mathbb E[\min\{X(j,s(j),y),T\}\mid s(j)]]$ in terms of the Bernoulli KL divergence $D$ between $y$ and $\mu_1$.

Significance

The result. Theorem 2 shows that Thompson Sampling, a randomized Bayesian heuristic, achieves regret logarithmic in the horizon for any number of arms with bounded rewards, matching the order in $T$ of the Lai–Robbins lower bound. Its dependence on the gaps, $(\sum_a\Delta_a^{-2})^2$, is worse than UCB1's; the paper's own Remark 1 and later work improve it. The proof introduced the device of bounding the waiting time between plays of the optimal arm through geometric variables with Beta-cdf parameters (Lemmas 1 and 3), which reappears in later analyses of Thompson Sampling.

Formalizing it. The theorem is proved on paper; it has not been machine-checked. Bandit theory in Lean (bandit environments, regret, UCB-type analyses) is still young, and no Beta–Bernoulli Thompson Sampling result is formalized. The mission produces a Lean model of Algorithm 2 for general $[0,1]$ rewards with the paper's stack coupling, the §4 bookkeeping of saturated arms and intervals, and the paper's lemmas as separate targets.

Difficulty

Two difficulties are specific to the $N$-armed analysis. First, the arm that competes with arm $1$ changes over time: the set of saturated arms grows, and which saturated arm is "best" depends on the history, so the waiting time between plays of arm $1$ cannot be compared with a single geometric variable as in the two-armed case. Second, the number $\gamma_j$ of rounds at which arm $1$'s sample is large but arm $1$ is not played is not independent of the counts $V_j^{\ell,a}$: both depend on the same posterior samples, and Lemma 5 needs a careful conditioning on the history to separate them. The obvious union bound over arms, treating each suboptimal arm as in the two-armed proof, fails because it ignores the interruptions by unsaturated arms, whose number is the source of the squared sum in the bound.

Formalization scope

• Probability space. Algorithm 2 is realized on a product of three independent i.i.d. tables: Beta draws indexed by (arm, round, successes, failures), rewards indexed by (arm, round) and uniform variables indexed by (arm, round); the Bernoulli trial of a round succeeds when the played arm's uniform variable is below its reward. The law of the run is that of Algorithm 2, which runs for every round $t=1,2,\dots$. $s(j)$ is the number of successful trials among the first $j$ plays of arm $1$ in this infinite run (possibly after the horizon $T$), so it is a $\mathrm{Binomial}(j,\mu_1)$ random variable for every $j$, as the paper's independent $Z_{1,m}$ make it. Ties in the arg max (probability $0$) go to the smallest index.
• Indexing. Arms are Fin N, and Lean arm 0 is the paper's arm $1$. Rounds are $0,\dots,T-1$; Lean round $t$ is the paper's round $t+1$. Sums over $a=2,\dots,N$ are sums over $a\ne0$.
• Expectations are lower Lebesgue integrals in $[0,\infty]$, which has no junk value for non-integrable functions. Conditional expectations given $s(j)$ are written as finite sums over the values of $s(j)$.
• The $O(\cdot)$. The paper writes $O(\cdot)$ in the sense of its footnote 1 ($f(n)\le c\,g(n)$ for $n\ge n_0$). The goal states it with one universal constant $C$, quantified before $N$, the instance and $T$, for every $T\ge2$. The explicit constants printed in App. D are not formalized: expanding the paper's Eq. (21) gives terms $288(N-1)(\ln T)\sum_a\Delta_a^{-2}$ and $48(N-1)^2$ where the paper prints $288(\ln T)\sum_i\Delta_i^{-2}$, and Eq. (22) drops a factor $\ln T$ in its $192/\Delta_a^2$ term. The $O(\cdot)$ claim does not depend on these slips; a statement pinned to the printed numerals might be false.
• Ruled out. A constant depending on $N$, on the means or on $T$; a fixed number of arms; Bernoulli rewards only; or any algorithm other than Algorithm 2 would each make the goal a different and weaker theorem. The statement quantifies over all $N\ge2$ and all reward distributions on $[0,1]$.
• Not included. Eq. (8), the bound $\sum_{j}\mathbb E[\gamma_j\mid s(j)]\le\sum_uL_u+4(N-1)$ "for all instantiations", is not a milestone: each term is conditioned on a different $s(j)$, and the pointwise reading does not follow from the argument given. Remark 1 (an alternate bound) and App. A (several optimal arms) are not part of this mission.
• Contributions welcome: Beta–Binomial identities, geometric waiting times, Hoeffding bounds for binomial cdfs, and the stopping-time arguments behind Lemma 5. Lemma 1 and Lemma 3 are shared with the two-armed mission of this series.

Selected references

• S. Agrawal and N. Goyal, Analysis of Thompson Sampling for the Multi-armed Bandit Problem, COLT 2012; arXiv:1111.1797v3, 2012. https://arxiv.org/abs/1111.1797
• W. R. Thompson, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika 25, 1933. https://doi.org/10.1093/biomet/25.3-4.285
• T. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics 6, 1985. https://doi.org/10.1016/0196-8858(85)90002-8
• P. Auer, N. Cesa-Bianchi and P. Fischer, Finite-time analysis of the multiarmed bandit problem, Machine Learning 47, 2002. https://doi.org/10.1023/A:1013689704352
• O. Chapelle and L. Li, An empirical evaluation of Thompson Sampling, NIPS 2011. https://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
• E. Kaufmann, N. Korda and R. Munos, Thompson Sampling: an asymptotically optimal finite-time analysis, ALT 2012. https://arxiv.org/abs/1205.4217
• S. Agrawal and N. Goyal, Further optimal regret bounds for Thompson Sampling, AISTATS 2013. https://arxiv.org/abs/1209.3353

Motivation

In many sequential decision problems the learner sees side information before acting. A news site chooses an article for a visitor whose history and location it knows; an ad server chooses an advertisement for a query. Only the reward of the chosen action is observed. These are contextual bandit problems, and Chapter 4 of Bubeck and Cesa-Bianchi's monograph Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (arXiv:1204.5721v2) surveys several of their formal versions. In a contextual problem the learner is compared with the best policy, a map from contexts to arms, rather than with the best single arm.

This mission covers three of the chapter's models. The first marks each round with a context from a finite set. In the second, $N$ experts give advice, as in prediction with expert advice. The third is the bandit multiclass problem: a linear classifier predicts one of $K$ labels and then learns only whether its prediction was right. The goal is the mistake bound of the Banditron (Kakade, Shalev-Shwartz and Tewari, ICML 2008). The bound shows that one bit of feedback per round suffices to compete with every linear classifier, at regret $O(n^{2/3})$.

Setting

There are $K \ge 2$ arms (or labels) $\{1,\dots,K\}$ and rounds $t = 1, \dots, n$.

Adversarial losses. At round $t$ an adversary assigns losses $\ell_{i,t} \in [0,1]$ to the arms and may adapt to the forecaster's past plays $I_1, \dots, I_{t-1}$. The forecaster draws $I_t$ at random from a distribution $p_t$ that depends on what it has observed, and it observes only $\ell_{I_t,t}$. Expectations $\mathbb E$ are over the forecaster's draws.

Side information. Each round carries a context $s_t$ from a finite set $\mathcal S$, and the sequence $s_1, s_2, \dots$ is fixed in advance. The pseudo-regret against context-to-arm maps is

$$\overline R^{\mathcal S}_n = \max_{g:\mathcal S\to\{1,\dots,K\}} \mathbb E\Big[\sum_{t=1}^n \ell_{I_t,t} - \sum_{t=1}^n \ell_{g(s_t),t}\Big].$$

The S-Exp3 forecaster runs one instance of Exp3 (Section 3.1 of the book) on each context.

Expert advice. At each round each of $N$ experts $j$ proposes a distribution $\xi^j_t$ over arms, which may depend on the forecaster's past plays. The contextual pseudo-regret is

$$\overline R^{\mathrm{ctx}}_n = \max_{k=1,\dots,N}\mathbb E\Big[\sum_{t=1}^n \ell_{I_t,t} - \sum_{t=1}^n \mathbb E_{i\sim\xi^k_t}\ell_{i,t}\Big].$$

Exp4 (Fig. 4.1) runs exponential weights over the experts with importance-weighted loss estimates.

Bandit multiclass. The examples $(x_t, y_t) \in \mathbb R^d \times \{1,\dots,K\}$ are fixed in advance, with $\|x_t\| = 1$ (Euclidean). A $K\times d$ matrix $U$ classifies $x$ by $\arg\max_i (Ux)_i$. Its multiclass hinge loss on round $t$ is $\ell_t(U) = [1 - (Ux_t)_{y_t} + \max_{i\neq y_t}(Ux_t)_i]_+$. Write $L_n(U) = \sum_{t\le n}\ell_t(U)$ for the cumulative hinge loss, $\bar L_n(U) = L_n(U)/n$ for its average, and $\|U\|$ for the Frobenius norm. The multiclass Perceptron predicts $\hat y_t = \arg\max_i (W_tx_t)_i$ and, after seeing $y_t$, adds $x_t$ to row $y_t$ and subtracts it from row $\hat y_t$. The Banditron (p. 58) predicts $Y_t$ from $p_{i,t} = (1-\gamma)\mathbb 1_{\hat y_t = i} + \gamma/K$. It observes only $\mathbb 1_{Y_t = y_t}$ and updates $W_{t+1} = W_t + \widetilde X_t$, where $(\widetilde X_t)_{i,j} = x_{t,j}\big(\mathbb 1_{Y_t=y_t}\mathbb 1_{Y_t=i}/p_{i,t} - \mathbb 1_{\hat y_t=i}\big)$. Its number of mistakes is $M_n = \sum_{t\le n}\mathbb 1_{Y_t\neq y_t}$.

Formalization targets

Goal: Theorem 4.7 (Banditron)

For $n \ge 8K$, $\gamma = (K/n)^{1/3}$, every example sequence as above and every $K\times d$ matrix $U$,

$$\mathbb E\,M_n \le L_n(U) + \Big(1 + \|U\|\sqrt{2\bar L_n(U)}\Big)K^{1/3}n^{2/3} + 2\|U\|^2K^{2/3}n^{1/3} + \sqrt2\,\|U\|K^{1/6}n^{1/3}.$$

Milestones

1. Multiclass Perceptron bound (Section 4.4, p. 57). For every $n \ge 1$ and $U$, $\sum_{t\le n}\mathbb 1_{\hat y_t\ne y_t} \le L_n(U) + 2\|U\|^2 + \|U\|\sqrt{2n\bar L_n(U)}$.
2. Theorem 4.1 (p. 44). S-Exp3 satisfies $\overline R^{\mathcal S}_n \le \sqrt{2n|\mathcal S|K\ln K}$.
3. Theorem 4.2 (p. 46), with corrected constants. Exp4 without mixing satisfies $\overline R^{\mathrm{ctx}}_n \le \sqrt{2nK\ln N}$ for $\eta_t = \sqrt{2\ln N/(nK)}$, and $\overline R^{\mathrm{ctx}}_n \le 2\sqrt{nK\ln N}$ for $\eta_t = \sqrt{\ln N/(tK)}$.
4. Theorem 4.3 (p. 50), with corrected learning rate. Let the plays be drawn from distributions $q_t$ with $q_{i,t}\ge\varepsilon > 0$, and let Exp3 run on the estimates $\ell_{i,t}\mathbb 1_{I_t=i}/q_{i,t}$ with $\eta = \sqrt{2\varepsilon\ln K/n}$. Then $\max_k \mathbb E\big[\sum_t \mathbb E_{i\sim p_t}\ell_{i,t} - \sum_t\ell_{k,t}\big] \le \sqrt{(2n/\varepsilon)\ln K}$.

Significance

Theorem 4.7 shows that, on any sequence of examples, the bandit version of online multiclass classification costs at most $O(K^{1/3}n^{2/3})$ mistakes beyond the hinge loss of the best linear classifier. The full-information Perceptron, by comparison, pays $O(\sqrt n)$. The bound has no stochastic assumption and has explicit constants. Theorems 4.1–4.3 are the basic regret guarantees for side information and expert advice. Theorem 4.3 in particular lets learning algorithms serve as experts inside Exp4, which is the construction behind Theorem 4.5.

The mission produces machine-checked statements, and eventually proofs, of these results with fully explicit constants and an explicit model of adaptive adversaries and adaptive advice. To the curators' knowledge none of the Banditron, the multiclass Perceptron bound, S-Exp3 or Theorem 4.3 is formalized anywhere. The platform's Bandit Algorithms series has a proved Exp4 bound, but only for advice and rewards fixed in advance. The book proves all four milestones and the goal; two printed statements (4.2 and 4.3) contain misprints that this mission corrects.

Difficulty

The Banditron bound concerns a randomized process whose weight matrix depends on all earlier random predictions. The Perceptron argument tracks $\langle U, W_{n+1}\rangle$ and $\|W_{n+1}\|^2$. It carries over only in conditional expectation, and the second moment of the importance-weighted update is of order $K/\gamma$ on rounds where $\hat y_t \neq y_t$ and of order $\gamma$ otherwise. Combining these into one inequality for $\sum_t\mathbb P(\hat y_t\neq y_t)$ and then for $\mathbb E M_n$ requires solving a quadratic inequality in the presence of expectations, and the constants must come out as printed. For the Exp3/Exp4 results, the obstacle is that losses and advice adapt to past plays. The standard potential argument has to be run conditionally on the history, and a version that fixes the losses in advance proves a weaker theorem.

Formalization scope

• Rounds and laws. Rounds are numbered from $0$ in Lean (Lean round $t$ is the book's round $t+1$). Every forecaster is a sampling rule from past plays to weights on Fin K. The law of the first $n$ plays is the product $\prod_t p_t(\omega_t\mid\omega_{<t})$ over sequences $\omega : \mathrm{Fin}\,n\to\mathrm{Fin}\,K$, and expectations are finite sums against it. The adversary and the experts are deterministic functions of past plays; an independent randomized adversary is a mixture of these. The examples of the Banditron are fixed.
• Argmax. $\hat y_t$ uses any argmax selector; all tie-breaking rules are covered.
• Norms. $\|x_t\| = 1$ is the Euclidean condition $\sum_j x_{t,j}^2 = 1$; $\|U\|$ is the Frobenius norm written out explicitly.
• Infima and maxima. Each "$\inf_U$" and "$\max_k$" of the book is stated as "for every $U$" or "for every $k$", which is equivalent.
• Explicit constants. Every bound is the one printed or, for the corrected items, the one the proof yields. No $O(\cdot)$ appears.
• Corrected misprints. Theorem 4.7 prints the examples in $\mathbb R^d\times\{-1,+1\}$; labels are in $\{1,\dots,K\}$. Theorem 4.2 prints $\sqrt{2nN\ln K}$ and $2\sqrt{nN\ln K}$; the proof gives $\sqrt{2nK\ln N}$ and $2\sqrt{nK\ln N}$. Theorem 4.3 prints $\eta = \sqrt{2\ln K/(nK)}$; (4.7) follows from the proof with $\eta = \sqrt{2\varepsilon\ln K/n}$.
• Parameter range. At $n = 8K$ the Banditron's $\gamma$ equals $1/2$, outside the box's open interval $(0,1/2)$. The proof uses only $\gamma\le 1/2$, so $n = 8K$ is included.
• Ruling out trivial forms. Theorem 4.1 is stated for the explicit S-Exp3 forecaster, not as an existence claim, so no forecaster tuned to the losses can witness it. The losses and the advice are allowed to adapt, so a proof for oblivious sequences does not suffice.
• Left out. Theorem 4.4 (Exp4 with mixing) is proved in the book only by reference. The argument that reference suggests yields $\tfrac32\gamma n + K\ln N/\gamma$, not the printed $\gamma n/2 + K\ln N/\gamma$. Theorem 4.5 is stated with $O(\cdot)$, Theorem 4.6 "for some constant $c$", and Eq. (4.8) is left to the reader.

Useful reusable infrastructure: the path-law expectation for history-dependent sampling, the exponential-weights potential argument under adaptive losses, and Perceptron-type inner-product arguments for matrices. Proofs of any milestone and of the goal are welcome.

Selected references

• S. Bubeck, N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends in Machine Learning 5(1), 2012. arXiv:1204.5721v2. https://arxiv.org/abs/1204.5721 ; https://doi.org/10.1561/2200000024
• S. M. Kakade, S. Shalev-Shwartz, A. Tewari, Efficient Bandit Algorithms for Online Multiclass Prediction, ICML 2008. https://doi.org/10.1145/1390156.1390212
• P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing 32(1), 2002. https://doi.org/10.1137/S0097539701398375
• O.-A. Maillard, R. Munos, Adaptive Bandits: Towards the Best History-Dependent Strategy, AISTATS 2011. https://proceedings.mlr.press/v15/maillard11a.html

Motivation

In bandit convex optimization a forecaster repeatedly picks a point $x_t$ of a convex set $\mathcal K\subseteq\mathbb R^d$, and an adversary picks a convex loss $\ell_t$. The forecaster pays $\ell_t(x_t)$ and observes only that number: it never sees the function, its gradient, or its value elsewhere. This is the model of online optimization with only function-value access, as in tuning a system online from measured costs, dynamic pricing with an unknown convex demand-cost curve, or routing with path costs observed only on the route taken. The question is how fast the forecaster can approach the best fixed point in hindsight.

Chapter 6 of Bubeck and Cesa-Bianchi's monograph (arXiv:1204.5721v2, Foundations and Trends in Machine Learning 5(1), 2012) treats the problem through spherical gradient estimates fed to projected gradient descent. The one-point method is due to Flaxman, Kalai and McMahan (SODA 2005, arXiv:cs/0408007), who obtained an $\mathcal O(n^{3/4})$ regret bound. Agarwal, Dekel and Xiao (COLT 2010) showed that two function evaluations per round allow $\mathcal O(\sqrt n)$. Whether one-point feedback admits $\sqrt n$ regret was open when the monograph was written (p. 94); Bubeck, Eldan and Lee (STOC 2017, arXiv:1607.03084) later obtained $\sqrt n$ regret up to logarithmic and polynomial-in-$d$ factors for convex losses, with a different and much more involved algorithm.

Setting

Let $\mathbb B=\{x\in\mathbb R^d:\|x\|\le1\}$ be the closed Euclidean unit ball and $\mathbb S=\{x:\|x\|=1\}$ the unit sphere, with unnormalized spherical measure $\sigma$, so that $\sigma(\mathbb S)=d\,\mathrm{Vol}(\mathbb B)$. Fix $\delta>0$. For a loss $\ell$, the smoothed loss is $\widetilde\ell(x)=\mathbb E\,\ell(x+\delta B)$ with $B$ uniform on $\mathbb B$.

The set $\mathcal K$ is closed and convex with $r\mathbb B\subseteq\mathcal K\subseteq R\mathbb B$. The losses $\ell_1,\ell_2,\dots:\mathbb R^d\to\mathbb R$ are $G$-Lipschitz, differentiable and convex, and are fixed before the game (an oblivious adversary).

OSGD (Online Stochastic Gradient Descent) on a set $\mathcal K'$ with learning rate $\eta$ starts at $x_1=0$ and sets $x_{t+1}=\operatorname{argmin}_{y\in\mathcal K'}\|y-(x_t-\eta\widetilde g_t(x_t))\|$, where $\widetilde g_t$ is a gradient estimate. With $S_1,S_2,\dots$ independent and uniform on $\mathbb S$:

• the two-point estimate (6.1) is $\widetilde g_t(x_t)=\frac d{2\delta}\big(\ell_t(X_t^+)-\ell_t(X_t^-)\big)S_t$ with $X_t^\pm=x_t\pm\delta S_t$; the played point is $X_t^+$ or $X_t^-$ by a fair coin;
• the one-point estimate (6.3) is $\widetilde g_t(x_t)=\frac d\delta\,\ell_t(\widetilde X_t)S_t$ with played point $\widetilde X_t=x_t+\delta S_t$.

OSGD runs on the shrunken set $\mathcal K'=(1-\delta/r)\mathcal K$, so that the perturbed points stay in $\mathcal K$. The pseudo-regret is

$$\overline R_n=\mathbb E\sum_{t=1}^n\ell_t(\widetilde X_t)-\min_{x\in\mathcal K}\sum_{t=1}^n\ell_t(x).$$

Formalization targets

Goal: Theorem 6.2, tuned

If in addition $|\ell_t|\le L$ on $\mathcal K$, and $\delta=(2n)^{-1/4}\sqrt{RdL/((3+R/r)G)}$, $\eta=(2n)^{-3/4}\sqrt{R^3/(dL(3+R/r)G)}$, then one-point OSGD satisfies

$$\overline R_n\le 4n^{3/4}\sqrt{RdL\,(3+R/r)\,G}.$$

Milestones

1. Lemma 6.1: $\nabla\int_{\mathbb B}\ell(x+\delta b)\,db=\frac1\delta\int_{\mathbb S}\ell(x+\delta s)s\,d\sigma(s)$.
2. Lemma 6.2: $\frac d\delta\mathbb E[\ell(x+\delta S)S]=\nabla\mathbb E\,\ell(x+\delta B)$.
3. Eq. (6.2): $|\ell(x)-\widetilde\ell(x)|\le\delta G$.
4. Lemma 6.3: the queried points' regret against $x$ is at most the smoothed regret of the iterates against $(1-\xi)x$, plus $3\delta Gn+\xi GRn$.
5. Theorem 6.1: two-point OSGD has $\overline R_n\le R^2/\eta+\eta(Gd)^2n+\delta(3+R/r)Gn$, and $\overline R_n\le 2RGd\sqrt n+\delta(3+R/r)Gn$ for $\eta=R/(Gd\sqrt n)$.
6. Theorem 6.2, first display: one-point OSGD has $\overline R_n\le R^2/\eta+\frac{(dL)^2}{\delta^2}\eta n+\delta(3+R/r)Gn$ for every $0<\delta\le r$ and $\eta>0$.

Significance

The $n^{3/4}$ bound shows that a single function value per round suffices for sublinear regret against any oblivious sequence of Lipschitz convex losses, with a forecaster whose only operations are a random perturbation and a Euclidean projection. The smoothing identity of Lemmas 6.1–6.2 is the basic tool of zeroth-order (derivative-free) optimization, used well beyond bandits, and Theorem 6.1 is the $\sqrt n$ benchmark for two-point methods.

All results are proved in the source. To the best of current knowledge none is formalized: the related items of the Introduction to Online Convex Optimization series on Prove2Me (Hazan's Lemma 6.7 and Theorem 6.9) were formalized with missing hypotheses and are recorded as disproved. This mission produces machine-checked statements with every hypothesis explicit, and the formal infrastructure (sphere measure calculus, a projected stochastic gradient analysis) for later zeroth-order results.

Difficulty

Two steps resist a direct formal treatment. First, Lemma 6.1 is a divergence-theorem identity on the ball; Mathlib has the sphere measure and polar coordinates, but its divergence theorem covers boxes rather than balls, so differentiating the ball average in $x$ requires either such a theorem or a direct argument about translates of the ball. Second, the regret analysis takes expectations of quantities that depend on the whole past: the iterate $x_t$ is a function of $S_1,\dots,S_{t-1}$, and unbiasedness $\mathbb E[\widetilde g_t\mid x_t]=\nabla\widetilde\ell_t(x_t)$ holds only conditionally, via independence of $S_t$ from the past. A pathwise gradient-descent inequality must be combined with this conditional expectation round by round, with measurability of the projected iterates established along the way. The naive approach of treating the estimate as the true gradient of $\ell_t$ fails: it is a gradient of $\widetilde\ell_t$, and the gap is handled only by Eq. (6.2) and Lemma 6.3.

Formalization scope

Points are in EuclideanSpace ℝ (Fin d) with $d\ge1$; rounds are $t=1,2,\dots$, sums run over Finset.Icc 1 n. $\sigma$ is Mathlib's Measure.toSphere of Lebesgue measure; the uniform laws are normalized restrictions. Randomness lives on an arbitrary probability space; the directions $S_t$ are measurable, mutually independent (iIndepFun) and uniform on $\mathbb S$, and in Theorem 6.1 the pairs $(S_t,C_t)$ are independent with $C_t$ a fair sign independent of $S_t$. A run of OSGD is a predicate (start at $0$, each iterate a Euclidean projection onto $(1-\delta/r)\mathcal K$), which determines the run uniquely, so the forecaster uses only observed values and its own randomness. The losses are Lipschitz, differentiable and convex on all of $\mathbb R^d$; the bound $|\ell_t|\le L$ is on $\mathcal K$, because a convex function bounded on $\mathbb R^d$ is constant. The minimum over $\mathcal K$ is an infimum over the subtype $\mathcal K$, attained in every theorem.

Conventions and corrections, each stated in the item's Formalization Note:

• Lemma 6.1 carries the factor $1/\delta$ that the printed statement omits and the proof contains (corrected misprint).
• Theorem 6.1's second display prints $\eta=R/(GD\sqrt n)$ and a limit "for $\delta\to0$"; the item states $\overline R_n\le 2RGd\sqrt n+\delta(3+R/r)Gn$ for $\eta=R/(Gd\sqrt n)$ and every admissible $\delta$, which implies the limit (corrected misprint).
• Theorems 6.1 and 6.2 add $0<\delta\le r$, which the proofs need for $X_t^\pm,\widetilde X_t\in\mathcal K$; for the tuned $\delta$ of the goal it is a condition on $n$.
• The goal adds $G,L>0$ and $n\ge1$, which its formulas for $\delta,\eta$ need; the constant $4$ is the book's rounding of $2\cdot2^{3/4}$ and is kept, as is the form $R^2/\eta$.

The statements cannot be satisfied trivially: the run is pinned by its recursion, the losses are fixed before the randomness, the expectations are of bounded measurable functions (no zero-valued Bochner integrals), and the minimum is over the nonempty compact $\mathcal K$. Section 6.3 (Lemma 6.4, Theorem 6.3) is not included, because its algorithm box and proof use different stage lengths and its unimodality condition is stated on a smaller set than the proof uses.

Needed infrastructure: calculus of ball averages and sphere integrals, symmetry of the uniform sphere law, nonexpansiveness of projections onto closed convex sets, and conditional-expectation bookkeeping for adapted iterates. Each is reusable for zeroth-order optimization; contributions of any of them as separate lemmas are welcome.

Selected references

• S. Bubeck, N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends in Machine Learning 5(1), 2012. arXiv:1204.5721v2, doi:10.1561/2200000024
• A. Flaxman, A. Kalai, H. B. McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, SODA 2005. arXiv:cs/0408007
• A. Agarwal, O. Dekel, L. Xiao, Optimal algorithms for online convex optimization with multi-point bandit feedback, COLT 2010. link
• S. Bubeck, R. Eldan, Y. T. Lee, Kernel-based methods for bandit convex optimization, STOC 2017. arXiv:1607.03084