Bandit Algorithms

Motivation

A retailer who sells several products from shared, non-replenishable inventory over a finite season must set prices without knowing how demand responds to them. Every price posted is both a sale and an experiment. This is the network revenue management problem with demand learning, and it sits between two literatures: dynamic pricing with inventory, where demand is known and the fluid linear program of Gallego and van Ryzin (1997) is the standard benchmark, and multi-armed bandits, where learning is the whole problem but there are no resource constraints.

Ferreira, Simchi-Levi and Wang (Oper. Res. 2018) combine Thompson sampling with a linear-programming step: sample a demand model from the posterior, solve the fluid LP for that model, and randomize prices according to its solution. The same paper extends the scheme to continuous price sets, contextual pricing and bandits with knapsacks.

Timeline of the relevant results:

• 1997: Gallego and van Ryzin introduce the fluid LP upper bound for network revenue management with known demand.
• 2012: Besbes and Zeevi give a non-Bayesian network pricing algorithm with worst-case regret $O(K^{5/3}T^{2/3}\sqrt{\log T})$.
• 2013: Badanidiyuru, Kleinberg and Slivkins (bandits with knapsacks) give worst-case regret $O(\sqrt{KT\log T})$.
• 2013–2014: Bubeck and Liu and Russo and Van Roy give prior-free Bayesian regret bounds for Thompson sampling in unconstrained bandits.
• 2018: Ferreira, Simchi-Levi and Wang prove the $O(\sqrt{TK\log K})$ Bayesian regret bound for TS-fixed (Theorem 1), the target of this mission.

Setting

There are $N$ products and $M$ resources. One unit of product $i$ consumes $a_{ij}\ge0$ units of resource $j$, and resource $j$ starts with inventory $I_j\ge0$ that is never replenished. The season has $T$ periods. In each period the retailer posts one of $K$ price vectors $p_k=(p_{1k},\dots,p_{Nk})$ or a shut-off price $p_\infty$ under which demand is zero.

Given the posted price $p_k$, the demand vector $D(t)\in\mathbb R^N_+$ has law $F(\cdot\,;p_k,\theta)$, where $\theta\in\Theta$ is unknown and drawn from a known, arbitrary prior $\mu_0$. Demand is independent of the past given the posted price and $\theta$, and is bounded: $D_i(t)\in[0,\bar d_i]$. Write $d_{ik}(\rho)$ for the mean demand of product $i$ under $p_k$ and parameter $\rho$, and $d=d(\theta)$.

When inventory covers all demand, all demand is sold. Otherwise the satisfied demand $\tilde D(t)$ satisfies $0\le\tilde D_i(t)\le D_i(t)$, leaves every inventory nonnegative, and leaves at least one resource at zero; no other rule is imposed. Revenue is $\mathrm{Rev}(T)=\sum_t\sum_i\tilde D_i(t)P_i(t)$.

For a mean-demand matrix $d$ and capacities $c_j=I_j/T$, the linear program $\mathrm{LP}(d)$ is

$$\max_{x\ge0}\ \sum_{k=1}^K\Bigl(\sum_{i=1}^N p_{ik}d_{ik}\Bigr)x_k\quad\text{s.t.}\quad\sum_{k=1}^K\Bigl(\sum_{i=1}^N a_{ij}d_{ik}\Bigr)x_k\le c_j\ \ \forall j,\qquad\sum_{k=1}^K x_k\le1,$$

with optimal value $\mathrm{OPT}(d)$.

TS-fixed (Algorithm 1): in each period, sample $\theta(t)$ from the posterior of $\theta$ given the history of posted prices and observed demands; let $x(t)$ be an optimal solution of $\mathrm{LP}(d(\theta(t)))$; post $p_k$ with probability $x_k(t)$ and $p_\infty$ with the remaining probability; observe demand and update the posterior.

Finally $p_{\max}=\max_k\sum_ip_{ik}\bar d_i$ and $p^j_{\max}=\max_{i:a_{ij}\neq0,\,k}p_{ik}/a_{ij}$.

Formalization targets

Goal: Theorem 1 against the LP benchmark

For $K\ge2$, $T\ge1$, every prior, every bounded demand family, every admissible fulfilment rule and every run of TS-fixed,

$$\mathbb E\bigl[\mathrm{OPT}(d)\bigr]\cdot T-\mathbb E\bigl[\mathrm{Rev}(T)\bigr]\ \le\ \Bigl(18\,p_{\max}+37\sum_{i=1}^N\sum_{j=1}^M p^j_{\max}a_{ij}\bar d_i\Bigr)\sqrt{TK\log K}.$$

The paper prints this bound for $\mathrm{BayesRegret}(T)=\mathbb E[\mathrm{Rev}^*(T)]-\mathbb E[\mathrm{Rev}(T)]$, where $\mathrm{Rev}^*$ is the revenue of the optimal policy that knows $\theta$; see Formalization scope for why the LP benchmark is stated instead.

Milestones

The article states Theorem 1 and says that its proof is in the online appendix (Supplemental Material at the DOI). The article itself contains no numbered lemma. The milestone list is therefore empty; the appendix's lemmas will be added as milestones once the appendix is held.

Significance

The bound is prior-free and has explicit constants that depend only on prices, consumption rates and demand bounds. Its dependence on $T$ matches the $\Omega(\sqrt{KT})$ lower bound for Bayesian regret in unconstrained bandits with rewards in $[0,1]$, a special case of the model with no inventory constraints (Bubeck and Cesa-Bianchi 2012, Theorem 3.5). It shows that the posterior-sampling principle survives the addition of resource constraints, lost sales and randomized LP-based pricing, and it is the template for the paper's later results (TS-update, contextual pricing, bandits with knapsacks).

The theorem is proved on paper but, as far as a platform search shows, not formalized anywhere. The platform has a formal proof of the unconstrained Bayesian Thompson sampling bound $\sqrt{kn\log k/2}$ (BanditAlgorithm.thompson_sampling_bayesian_regret, Lattimore–Szepesvári Theorem 36.5) and an open single-product deterministic upper bound in revenue management (RevenueManagement.deterministic_upper_bound). Neither has inventory, an LP subroutine, or lost sales. A formal proof here would supply the first machine-checked analysis of Thompson sampling under resource constraints and would check the paper's constants.

Difficulty

In an unconstrained bandit, Thompson sampling's regret reduces to a sum of per-period gaps between an upper confidence bound and the sampled reward, because the sampled optimal arm and the true optimal arm are identically distributed given the history. Here the action is a randomized mixture $x(t)$ from an LP, the reward is not additive in the prices chosen, and revenue is lost when inventory runs out. Two quantities must be controlled: the revenue the algorithm would collect if all demand could be served, and the revenue lost to stock-outs. The second depends on the random time at which each resource is exhausted under a pricing rule that was optimized for a sampled, not the true, demand, and on an arbitrary fulfilment rule once some resource is empty. Standard bandit arguments do not bound such lost sales, which are a nonlinear function of the whole trajectory.

Formalization scope

Lean representation. Products, resources and price vectors are indexed by Fin N, Fin M, Fin K; the posted price is an Option (Fin K) with none the shut-off price. Periods are 0-based ($t=0,\dots,T-1$ stands for the paper's $1,\dots,T$). $\Theta$ is a standard Borel space with a probability measure $\mu_0$; demand is a Markov kernel $F$ from $\Theta\times$Fin K to $\mathbb R^N$, bounded in $[0,\bar d_i]$ for every parameter. A run of TS-fixed is a family of random variables on a probability space satisfying, almost surely and via conditional expectations: $\theta\sim\mu_0$; the posterior-sampling property of $\theta(t)$ given everything before period $t$; the price draw with probabilities $x(\theta(t))$ for a measurable optimal LP selection $x$; the demand law given the past, $\theta(t)$ and the posted price; and fulfilment rules (a)/(b). The logarithm is natural. Prices, consumption and inventory are nonnegative (implicit in the paper). $\mathrm{OPT}(d)$ is a supremum over a nonempty bounded feasible set, so it has no junk value.

Corrections to the printed statement.

1. $K\ge2$ is added. At $K=1$ the printed right-hand side is $0$, yet on a one-price instance with Bernoulli$(0.8)$ demand, $I=T/2$ and a point-mass prior, TS-fixed loses about $0.2p\sqrt T$ in expectation.
2. The LP benchmark replaces $\mathbb E[\mathrm{Rev}^*(T)]$. Section 3.1.1 bounds $\mathbb E[\mathrm{Rev}^*(T)\mid d]$ by $\mathrm{OPT}(d)\cdot T$, citing Gallego–van Ryzin. Under the paper's fulfilment rule this fails when products use disjoint resources: with two products, $I=(T,1)$, $p_1=(1,0)$, $p_2=(1/2,0)$ and deterministic demand $(1,1)$, the known-$\theta$ policy earns at least $T$ while $\mathrm{OPT}(d)\cdot T=1$. The paper states that its proof bounds the gap to "the LP benchmark defined in Section 3.1.1" (p. 1594), and the last display of Section 3.1.1 bounds $\mathrm{BayesRegret}(T)$ by exactly $\mathbb E[\mathrm{OPT}(d)]\cdot T-\mathbb E[\mathrm{Rev}(T)]$. Wherever the Gallego–van Ryzin bound holds, the corrected goal implies the printed one.

Ruled out. A bound for the "ideal" revenue $\sum_iD_i(t)P_i(t)$ instead of the satisfied revenue, or for an arbitrary policy whose prices are merely close to the LP solution, is not Theorem 1; the goal carries the full TS-fixed run and the lost-sales accounting.

Infrastructure needed. Posterior-sampling identities for general (standard Borel) priors, a Hoeffding/Azuma-type concentration for bounded demand along the price-selection process, LP sensitivity with respect to the mean-demand matrix, and a pathwise bound on lost sales under an arbitrary fulfilment rule. The LP and fluid-benchmark definitions are reusable for later missions on TS-update (Theorem 2), contextual pricing (Theorem 4) and bandits with knapsacks (Theorem 5). Contributions welcome: proofs of the goal, and formal statements of the online appendix's lemmas.

Selected references

• K. J. Ferreira, D. Simchi-Levi, H. Wang, Online Network Revenue Management Using Thompson Sampling, Operations Research 66(6):1586–1602, 2018. https://doi.org/10.1287/opre.2018.1755
• G. Gallego, G. van Ryzin, A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management, Operations Research 45(1):24–41, 1997. https://doi.org/10.1287/opre.45.1.24
• O. Besbes, A. Zeevi, Blind Network Revenue Management, Operations Research 60(6):1537–1550, 2012. https://doi.org/10.1287/opre.1120.1057
• A. Badanidiyuru, R. Kleinberg, A. Slivkins, Bandits with Knapsacks, FOCS 2013. https://arxiv.org/abs/1305.2545
• S. Bubeck, C.-Y. Liu, Prior-free and Prior-dependent Regret Bounds for Thompson Sampling, NeurIPS 2013. https://arxiv.org/abs/1311.0466
• D. Russo, B. Van Roy, Learning to Optimize via Posterior Sampling, Mathematics of Operations Research 39(4):1221–1243, 2014. https://doi.org/10.1287/moor.2014.0650
• S. Bubeck, N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends in Machine Learning 5(1), 2012. https://arxiv.org/abs/1204.5721
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 36. https://doi.org/10.1017/9781108571401