Probability

Motivation

Distribution systems often move stock in two stages. A depot orders from an outside supplier and ships to a retail outlet, where customer demand arrives and unmet demand is backordered. Stock held anywhere costs money, a shortage at the outlet costs more, and each order carries a fixed charge. The basic question is what ordering and shipping rule minimizes total cost.

Clark and Scarf (Management Science 6, 1960) showed that over a finite planning horizon this two-echelon problem decomposes. The outlet solves its own single-location problem, and the depot solves a second single-location problem in which the outlet's shortfall is charged through an induced penalty cost. Federgruen and Zipkin (Operations Research 32(4), 1984) carried the decomposition to the infinite horizon. In the infinite-horizon problems the induced penalty becomes stationary and explicit, which makes the system computable with single-location tools. This mission covers the discounted-cost half of that paper (§§1–2).

Timeline:

• 1960: Clark and Scarf, finite-horizon decomposition, with a nonstationary penalty $\hat P_n$ built from the outlet's optimal cost functions.
• 1963: Iglehart (Management Science 9) proved, for the single-location discounted problem, that the finite-horizon value functions converge uniformly and that an $(s,S)$ policy is optimal.
• 1984: Federgruen and Zipkin combine the two results and prove that a stationary policy built from the decomposition is optimal for the infinite-horizon discounted and average-cost problems.

Setting

Time is discrete. The cost data are a fixed order cost $K$, an order cost rate $c^d$, a shipment cost rate $c^r$, a holding cost rate $h^d$ on all system stock, an extra holding cost rate $h^r$ at the outlet, and a backorder penalty rate $p^r$; all are positive. The discount factor $\alpha$ satisfies $0 \le \alpha < 1$, shipments take $l$ periods and orders take $L$ periods. One-period demands are independent copies of a nonnegative continuous random variable $u$ with mean $\mu < \infty$, and $u^{(i)}$ denotes the sum of $i$ copies.

The state is $(\hat y, v^d, x^r)$:

• $\hat y = (y^1, \dots, y^L)$ lists the outstanding orders, $y^i$ placed $i$ periods ago;
• $v^d$ is the depot's echelon inventory (its own stock plus $x^r$);
• $x^r$ is the outlet's stock plus shipments in transit.

An action is an order $y \ge 0$ and a shipment $z \ge 0$ with $x^r + z \le v^d + y^L$. With demand $u$, the next state is $((y, y^1, \dots, y^{L-1}), v^d + y^L - u, x^r + z - u)$. The one-period cost is

$$c^d(y) + h^d(v^d + y^L) + c^r z + R(x^r + z),$$

where $c^d(y) = K + c^d y$ for $y > 0$, $c^d(0) = 0$, and

$$R(x) = \alpha^l\{-h^d(x - l\mu) + p^r E[u^{(l+1)} - x]^+ + (h^d + h^r)E[x - u^{(l+1)}]^+\}.$$

$B^\alpha(s \mid \pi)$ is the expected total discounted cost of a policy $\pi$ from state $s$.

The critical number $x^{r*}$ minimizes $(1-\alpha)c^r x + R(x)$. The stationary induced penalty is $P(x) = 0$ for $x \ge x^{r*}$ and $P(x) = (1-\alpha)c^r(x - x^{r*}) + R(x) - R(x^{r*})$ otherwise. The depot problem $IH^d_\alpha$ has state $(\hat y, v^d)$, action $y \ge 0$ and one-period cost $c^d(y) + h^d(v^d + y^L) + P(v^d + y^L)$. The policy $\pi_\alpha^*$ orders by an optimal stationary policy $\sigma^d$ of $IH^d_\alpha$ and ships $z = \max\{0, \min\{x^{r*}, v^d + y^L\} - x^r\}$: up to the critical number when the depot has the stock, otherwise as much as it has.

Formalization targets

Goal: Theorem 1 (p. 827)

Assume $\alpha^l p^r \ge (1-\alpha^l)h^d$. For every state with $\hat y \ge 0$ and $x^r \le v^d$, and every admissible policy $\pi$,

$$B^\alpha(\hat y, v^d, x^r \mid \pi_\alpha^*) \le B^\alpha(\hat y, v^d, x^r \mid \pi).$$

The goal leaves the form of $\sigma^d$ open: any optimal stationary depot policy will do, and no $(s,S)$ structure is assumed.

Milestones

The milestones follow the paper's own route. Write $\hat g_n$, $g_n^r$, $\hat g_n^d$, $g_n^d$ for the $n$-period optimal costs of the system, of the outlet, of the depot with penalties $\hat P_n$, and of the depot with penalty $P$.

• Eq. (4): $\hat g_n = \hat g_n^d + g_n^r$.
• Property (e): $g_n^r \to g^r = B^{r\alpha}$.
• §2 claim (Iglehart): $g_n^r \to g^r$ uniformly on $(-\infty, x^{r*}]$.
• Lemma 1: $\hat P_n \to P$ uniformly on $\mathbb R$.
• Lemma 2: $\hat g_n^d - g_n^d \to 0$ uniformly.
• Lemma 3: $\hat g_n \to g^d + g^r$.
• Lemma 4: $g$ satisfies the optimality equation (8), and $\pi_\alpha^*$ attains it.

Significance

The theorem shows that, under discounting, the infinite-horizon two-echelon problem is solved by two single-location problems, with a penalty $P$ that is written in terms of $R$ alone. Computing $P$ does not require the outlet's optimal cost functions. The rest of the paper relies on this: its computational sections evaluate $P$ in closed form for normal demand, and they treat several outlets by relaxation. A machine-checked version also gives an infinite-horizon decomposition theorem against which future multi-echelon formalizations can be checked.

The result was proved in 1984 and is not open. It has not been formalized. The paper's proof is short only because it cites Iglehart's convergence results and Propositions 9.12 and 9.16 of Bertsekas and Shreve (1978) for its last step, so a formal proof must also supply these.

Difficulty

The obvious argument passes to the limit in the finite-horizon decomposition (4). That fails as stated, because the depot program (3) has nonstationary penalties $\hat P_n$, built from the outlet's optimal costs $g_{n-1}^r$, and its value functions are not those of any stationary problem. The comparison of $\hat P_n$ with $P$ needs uniform control over the whole real line. The first few $\hat P_n - P$ are in fact unbounded, since $g_0^r = 0$ has the wrong slope. The uniform control therefore holds only for large $n$, and the error has to be propagated through the depot recursion.

The second obstacle is that the one-period costs are unbounded in both directions: $h^d v$ is negative for negative $v$. Contraction arguments for bounded costs therefore do not apply. Lower boundedness on the feasible set needs the cost relation $\alpha^l p^r \ge (1-\alpha^l)h^d$, and passing from the optimality equation to optimality of a policy needs the theory of models with costs bounded below.

Formalization scope

Everything lives in the namespace FZEchelon.Discounted.

• Model. The data form a structure Model. The pipeline $\hat y$ is a vector indexed by $\{0, \dots, L-1\}$, whose index $k$ is the paper's $y^{k+1}$. For $L = 0$ the current order arrives at once.
• Policies and cost. Time runs forward with weight $\alpha^k$; the paper counts periods remaining. Policies are measurable, non-anticipative, deterministic and history dependent, and they must be feasible along every demand path. $B^\alpha$ is an extended real: the expectation of the positive part of the discounted cost sum minus that of the negative part, under the product law of the demands.
• Finite-horizon programs. These are real infima over the feasible actions.
• Hypotheses. Statements quantify over the physical states $\hat y \ge 0$, $x^r \le v^d$. The standing assumptions of §1 are bundled in StandingAssumptions: positive costs, $0 \le \alpha \le 1$, demand nonnegative, atomless and of finite mean. The §2 statements add $\alpha < 1$ and the cost relation, which the paper names in the proof of Theorem 1. The critical numbers $x^{r*}$ and $x_n^{r*}$ enter as minimizers. The depot policy $\sigma^d$ enters as a measurable, nonnegative stationary policy that is optimal for $IH_\alpha^d$; that is the paper's definition of $\pi_\alpha^*$, and its existence is Iglehart's.
• Ruled out. Comparing $\pi_\alpha^*$ only against stationary policies, or reading $B^\alpha$ as a bare series or a truncated sum, would trivialize or change the theorem. The comparison class is all admissible history-dependent policies.
• Corrections. Where the paper says "bounded" for every $n$ (§2 claim, Lemmas 1 and 2), the statements claim boundedness only where it holds: $n \ge 1$, $n \ge 2$, and eventually, respectively. The moderation notes give the counterexample at $n = 1$. Lemma 2 also carries the standing assumption of p. 821 that never ordering is not optimal. The statement is false without it.
• Infrastructure. A complete development needs the convexity theory of the single-location newsvendor function $R$, value iteration for discounted models with costs bounded below, and the Markov property for the product measure on demand sequences. The control-system file is reusable for other inventory and queueing missions. Formalizations of Iglehart's theorem and of Bertsekas–Shreve Propositions 9.12 and 9.16 are welcome.

Selected references

• A. Federgruen, P. Zipkin, Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model, Operations Research 32(4):818–836, 1984. https://doi.org/10.1287/opre.32.4.818
• A. J. Clark, H. Scarf, Optimal Policies for a Multi-Echelon Inventory Problem, Management Science 6(4):475–490, 1960. https://doi.org/10.1287/mnsc.6.4.475
• D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2):259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259
• D. P. Bertsekas, S. E. Shreve, Stochastic Optimal Control: The Discrete-Time Case, Academic Press, 1978. https://web.mit.edu/dimitrib/www/soc.html

Motivation

Many supply chains move stock through a central warehouse to the retail locations that face customer demand. Deciding how much the warehouse should order from outside, and how much it should ship to each retailer and when, is a stochastic dynamic program whose state contains every stock level and every outstanding order. Exact solution is out of reach except for the smallest systems, so structural results that reduce such a problem to single-location problems matter in practice.

Timeline.

• Clark and Scarf (Management Science 1960) showed that the finite-horizon, discounted problem of a serial system decomposes: an optimal policy is obtained by solving the most downstream location alone, charging its shortfalls to the upstream location through an induced penalty cost, and then solving the upstream location as a single-location problem with that penalty.
• Iglehart (Management Science 1963, and a 1963 chapter in Multistage Inventory Models and Techniques) established the infinite-horizon theory of the single-location problem with a fixed order cost: optimality of stationary $(s,S)$ policies under discounted and average costs, and the convergence of value iteration.
• Federgruen and Zipkin (Operations Research 1984) carried the decomposition to the infinite horizon for a depot and one retail outlet, under discounted costs (Theorem 1) and under the average-cost criterion (Theorem 2). This mission is about the average-cost case, §3 of that paper.

Setting

Time is divided into periods. A depot orders from an outside supplier with lead time $L \ge 0$ and supplies a retail outlet with shipment lead time $l \ge 0$. The demand $u$ in each period is a nonnegative random variable with law $\nu$ and finite mean $\mu$; demands in different periods are independent and identically distributed. Unmet demand at the outlet is backordered.

The state is $(\tilde y, v^d, x^r)$:

• $\tilde y = (y^1,\dots,y^L)$ lists the orders placed $1,\dots,L$ periods ago;
• $v^d$ is the depot's echelon inventory, its own stock plus the outlet's inventory position;
• $x^r$ is the outlet's inventory position, its stock plus shipments in transit.

In each period the decision is an order $y \ge 0$ and a shipment $z \ge 0$ with $x^r + z \le v^d + y^L$, where $y^L$ is the order arriving now. The state then moves to $((y, y^1,\dots,y^{L-1}),\, v^d + y^L - u,\, x^r + z - u)$.

Costs are a fixed order cost $K$, proportional order and shipment rates $c^d$ and $c^r$, a holding rate $h^d$ on system inventory, an extra holding rate $h^r$ at the outlet and a backorder penalty rate $p^r$. After the paper's accounting transformation, the one-period cost is

$$c^d(y) + D(v^d + y^L) + c^r z + R(x^r + z),$$

with $c^d(y) = K + c^d y$ for $y > 0$ and $c^d(0) = 0$, $D(v) = h^d v$, and, at $\alpha = 1$,

$$R(x) = -h^d(x - l\mu) + p^r E[u^{(l+1)} - x]^+ + (h^d + h^r) E[x - u^{(l+1)}]^+ ,$$

where $u^{(l+1)}$ is the demand over $l + 1$ periods. The critical number $x^{r*}$ is a minimizer of $R$. The stationary induced penalty is $P(x) = R(x) - R(x^{r*})$ for $x < x^{r*}$ and $0$ otherwise.

For a policy $\pi$ and initial state $s$, $B_n(s \mid \pi)$ is the expected cost of the first $n$ periods and $B(s \mid \pi) = \limsup_n B_n(s \mid \pi)/n$ is the average cost. Problem IH asks for a policy minimizing $B(s\mid\cdot)$ from every state. The depot problem IH$^d$ has states $(\tilde y, v^d)$, orders $y \ge 0$ and one-period cost $c^d(y) + D(v^d + y^L) + P(v^d + y^L)$. Its minimal average cost is $a^d$. The outlet problem has states $x^r$, shipments $z \ge 0$ and one-period cost $c^r z + R(x^r + z)$. The policy $\pi^*$ orders by an optimal stationary policy of IH$^d$ and ships $z = \max(0, \min(x^{r*}, v^d + y^L) - x^r)$: up to the critical number if the depot has the stock, otherwise as much as it has.

Formalization targets

Goal: Theorem 2 (p. 828)

With $\alpha = 1$ and $c^d = c^r = 0$, the policy $\pi^*$ is measurable and feasible from every physical state, and for every such state $s$ and every measurable feasible policy $\pi$,

$$B(s \mid \pi^*) \le B(s \mid \pi).$$

Milestones

• Property (f) (p. 824): $g^r_n(x)/n \to B^r(x) = c^r\mu + R(x^{r*})$ for the outlet program $g^r_n$.
• Eq. (4) (p. 823), for $0 \le \alpha \le 1$: $\hat g_n(\tilde y, v^d, x^r) = \hat g^d_n(\tilde y, v^d) + g^r_n(x^r)$.
• §3 claims (p. 828): with $c^r = 0$, $x^{r*}$ is the critical number of every period, $g^r_n(x) = nR(x^{r*})$ for $x \le x^{r*}$, $\hat P_n = P$, $\hat g^d_n = g^d_n$ and $\hat g_n = g_n$.
• §3 display (p. 828): $\hat g_n(\tilde y, v^d, x^r)/n \to a = a^d + R(x^{r*})$.
• Lemma 5 (p. 828): $B(s \mid \pi^*) = a$.
• Proof of Theorem 2 (p. 828): $\hat g_n(s) \le B_n(s \mid \pi)$ for every measurable feasible $\pi$.

Significance

The result. Theorem 2 reduces an average-cost problem with a multidimensional state to two problems with smaller states: a single-location $(s,S)$-type problem for the depot with a known convex penalty $P$, and a myopic critical-number rule for the outlet. The optimal system cost is the sum $a^d + a^r$ of their optimal costs. The paper uses this to compute optimal policies with standard single-location software, and its §5 builds heuristics for several outlets on the same decomposition.

Formalizing it. The result is proved in the paper; nothing here is open. To our knowledge none of it has been machine-checked. A formal proof has to make precise what the paper leaves to "standard arguments":

• the class of measurable history-dependent policies;
• the expected costs of policies with unbounded one-period costs;
• the passage from history-dependent to Markov policies;
• the transient of $\pi^*$ when the outlet starts above its critical number.

Difficulty

The obvious argument would identify the average-cost optimal value through an average-cost optimality equation on the full state space and verify that $\pi^*$ attains it. No such equation is available here. The state space is unbounded, the one-period costs are unbounded both above and below in the state, and the depot's fixed cost makes its value functions $K$-convex rather than convex.

The paper's route avoids that equation but needs three separate facts:

• value iteration for the whole system, divided by $n$, converges to $a^d + a^r$, which rests on Iglehart's convergence for the depot and on the stationarity of the penalties when $c^r = 0$;
• the finite-horizon value bounds the cost of every history-dependent policy, not only of Markov ones;
• $\pi^*$ achieves $a$ from every state, including states with $x^r > x^{r*}$, where it does not ship at all until demand has brought the outlet below its critical number.

Formalization scope

• Representation. A state is a triple in $(\mathrm{Fin}\,L \to \mathbb R) \times \mathbb R \times \mathbb R$. For $L = 0$ the order placed now arrives at once. Time runs forward in Lean; the paper numbers periods backward. Finite-horizon value functions keep the paper's index $n$ (periods remaining). Each "min" of programs (1), (2), (3), (5) is a real infimum over the constraint set.
• Policies and costs. Policies are deterministic, history-dependent and measurable, and they must be feasible along every demand realization. $B_n$ is an extended real (expected positive part minus expected negative part of each period's cost). $B$ is a $\limsup$ in the extended reals, and the optimal average costs are infima in the extended reals.
• Standing assumptions (p. 821):
  • $K, h^d, h^r, p^r > 0$;
  • demands i.i.d., nonnegative, without atoms ("for convenience we shall assume $u$ is continuous") and with finite mean.
• Added hypotheses.
  • States are restricted to the physical ones, $\tilde y \ge 0$ and $x^r \le v^d$.
  • $c^d = c^r = 0$. The paper reduces to this case "without loss of generality", on the grounds that average proportional costs equal $c^d\mu$ and $c^r\mu$ "under all interesting policies" (p. 827). That class is never specified, and the proofs are written for $c^d = c^r = 0$. The general-cost version is the paper's informal reduction and is not part of the goal.
  • Eq. (4) is stated for $0 \le \alpha \le 1$ with $K, h^d, h^r, p^r > 0$ and $c^d, c^r \ge 0$ (so that it covers §3's case $c^d = c^r = 0$), and with the relation $\alpha^l p^r \ge (1 - \alpha^l)h^d$, which the paper names on p. 827; it holds automatically at $\alpha = 1$.
• Ruling out trivial readings.
  • $\pi^*$ is built from a depot rule $\sigma^d$ assumed optimal for IH$^d$ from every depot state. Its existence is Iglehart's theorem, cited and not formalized; no $(s,S)$ form is required.
  • The goal quantifies over all measurable feasible policies, and $\pi^*$'s own feasibility is a conclusion, so a vacuous policy class cannot satisfy it.
  • A sorry-free check in the workspace exhibits an instance (exponential demand) meeting every standing hypothesis other than the optimality of $\sigma^d$, including the existence of $x^{r*}$.
• Reusable infrastructure. The definitions of history-dependent policies and of extended-real expected and average costs for controlled processes driven by i.i.d. real noise are generic, and could be reused for other inventory and queueing models. Contributions are welcome on any milestone, and especially on a formal version of the Markov reduction (Dynkin–Yushkevich III.1) for this setting and on Iglehart's convergence of $g^d_n/n$.

Selected references

• A. Federgruen and P. Zipkin, Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model, Operations Research 32(4):818–836, 1984. https://doi.org/10.1287/opre.32.4.818
• A. J. Clark and H. Scarf, Optimal Policies for a Multi-Echelon Inventory Problem, Management Science 6(4):475–490, 1960. https://doi.org/10.1287/mnsc.6.4.475
• D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2):259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259
• D. L. Iglehart, Dynamic Programming and Stationary Analyses of Inventory Problems, Chapter 1 in H. Scarf, D. Gilford and M. Shelly (eds.), Multistage Inventory Models and Techniques, Stanford University Press, 1963.
• E. B. Dynkin and A. A. Yushkevich, Controlled Markov Processes, Springer, 1979.
• D. P. Bertsekas and S. E. Shreve, Stochastic Optimal Control: The Discrete-Time Case, Academic Press, 1978.

Motivation

Least-squares regression fitted by stochastic gradient descent — the least-mean-square (LMS) algorithm — is the basic large-scale learning procedure: each observation is touched once, at a cost linear in the dimension. Classical analyses of stochastic approximation give the rate $O(1/\sqrt n)$ for non-strongly-convex objectives, and $O(1/(\mu n))$ when the objective is $\mu$-strongly convex. For least squares, $\mu$ is the smallest eigenvalue of the input covariance, which in high-dimensional problems is close to zero, so the strongly convex rate is often worse than the non-strongly-convex one.

F. Bach and E. Moulines (arXiv:1306.2119, NeurIPS 2013) showed that for the square loss this dichotomy disappears: averaged LMS with a constant step size reaches the rate $O(1/n)$ with no strong-convexity assumption, and with a constant that does not involve the smallest eigenvalue. Averaging of stochastic approximation iterates goes back to Polyak and Juditsky (SIAM J. Control Optim. 1992), whose guarantees are asymptotic and use decreasing step sizes. The proof technique for the expansion of the noise process is adapted from Aguech, Moulines and Priouret (SIAM J. Control Optim. 2000). This mission formalizes the non-asymptotic bound in expectation (Theorem 1 of the paper) and the chain of lemmas of its Appendix A.

Setting

Let $\mathcal H=\mathbb R^d$ with $d\ge1$, inner product $\langle\cdot,\cdot\rangle$ and norm $\|\cdot\|$. For $a\in\mathcal H$, $a\otimes a$ is the operator $b\mapsto\langle a,b\rangle a$. For self-adjoint operators, $A\preccurlyeq B$ means that $B-A$ is positive semi-definite.

The data are independent and identically distributed pairs $(x_n,z_n)\in\mathcal H\times\mathcal H$, $n\ge1$, with finite second moments. The covariance operator is $H=\mathbb E[x_n\otimes x_n]$, assumed invertible (its eigenvalues may be arbitrarily small). The least-squares objective

$$f(\theta)=\tfrac12\,\mathbb E\big[\langle\theta,x_n\rangle^2-2\langle\theta,z_n\rangle\big]$$

attains its global minimum at $\theta^*$, and $\xi_n=z_n-\langle\theta^*,x_n\rangle x_n$ is the residual. The model need not be well specified: $\mathbb E[\xi_n\mid x_n]$ need not vanish. Two constants $R,\sigma>0$ satisfy

$$\mathbb E[\xi_n\otimes\xi_n]\preccurlyeq\sigma^2H,\qquad \mathbb E\big[\|x_n\|^2x_n\otimes x_n\big]\preccurlyeq R^2H .$$

These are assumptions (A1)–(A6) of §2.1. The LMS recursion with constant step size $\gamma$, started at $\theta_0\in\mathcal H$, is

$$\theta_n=\theta_{n-1}-\gamma\big(\langle\theta_{n-1},x_n\rangle x_n-z_n\big)=(I-\gamma x_n\otimes x_n)\theta_{n-1}+\gamma z_n ,$$

and its average is $\bar\theta_{n-1}=n^{-1}\sum_{k=0}^{n-1}\theta_k$.

Formalization targets

Goal: Theorem 1, Eq. (2)

For every step size $0<\gamma<1/R^2$ and every $n\ge1$,

$$\mathbb E\big[f(\bar\theta_{n-1})-f(\theta^*)\big]\le\frac{1}{2n}\left[\frac{\sigma\sqrt d}{1-\sqrt{\gamma R^2}}+R\|\theta_0-\theta^*\|\frac{1}{\sqrt{\gamma R^2}}\right]^2 .$$

The constants are the paper's. A companion item states the case $\gamma=1/(4R^2)$, where the bound reads $\frac2n\big[\sigma\sqrt d+R\|\theta_0-\theta^*\|\big]^2$.

Milestones (Appendix A)

1. The excess risk is a quadratic form: $f(\theta)-f(\theta^*)=\tfrac12\langle\theta-\theta^*,H(\theta-\theta^*)\rangle$.
2. Consequences of (A6): $\mathbb E\|x_n\|^2\le R^2$, $\operatorname{tr}H\le R^2$, $H\preccurlyeq R^2I$, and $\gamma H\preccurlyeq I$ for $\gamma\le1/R^2$.
3. Lemma 1: for a recursion $\alpha_n=(I-\gamma x_n\otimes x_n)\alpha_{n-1}+\gamma\xi_n$ with martingale-difference noise and $\gamma R^2\le1$,

$$(1-\gamma R^2)\,\mathbb E\langle\bar\alpha_{n-1},H\bar\alpha_{n-1}\rangle+\tfrac{1}{2n\gamma}\mathbb E\|\alpha_n\|^2\le\tfrac{1}{2n\gamma}\|\alpha_0\|^2+\tfrac{\gamma}{n}\textstyle\sum_{k=1}^{n}\mathbb E\|\xi_k\|^2 .$$

4. Lemma 3: $(1-(1-u)^n)^2\le nu$ for $u\in[0,1]$ and $n>0$.
5. Lemma 2: for $\alpha_n=(I-\gamma H)\alpha_{n-1}+\gamma\xi_n$ with $\mathbb E[\xi_n\otimes\xi_n]\preccurlyeq C$, the second-moment bound (13) and

$$\mathbb E\langle\bar\alpha_{n-1},H\bar\alpha_{n-1}\rangle\le\tfrac{1}{n\gamma}\|\alpha_0\|^2+\tfrac1n\operatorname{tr}(CH^{-1}).$$

6. The pathwise decomposition $\theta_n-\theta^*=M^n_1(\theta_0-\theta^*)+\gamma\sum_{k=1}^nM^n_{k+1}\xi_k$ (A.2).
7. The initial-condition bound $\mathbb E\langle\bar\eta_{n-1},H\bar\eta_{n-1}\rangle\le\|\eta_0\|^2/(n\gamma)$ for the noise-free process (A.3).
8. The expansion of the noise process (A.4): the remainder recursion (16), the covariance bound (17) $\mathbb E[\eta^r_{n-1}\otimes\eta^r_{n-1}]\preccurlyeq\gamma^{r+1}R^{2r}\sigma^2I$, the order-$r$ bound $\frac1n\gamma^rR^{2r}d\sigma^2$, the remainder bound $\frac{\gamma^{r+2}\sigma^2R^{2r+4}}{1-\gamma R^2}$, and the noise bound

$$\big(\mathbb E\langle\bar\eta_{n-1},H\bar\eta_{n-1}\rangle\big)^{1/2}\le\frac{\sigma\sqrt d}{\sqrt n}\cdot\frac{1}{1-\sqrt{\gamma R^2}}\quad(\eta_0=0,\ \gamma R^2<1).$$

Significance

The result. Theorem 1 gives a finite-sample, dimension-explicit bound with two terms: a variance term $\sigma^2d/n$, which matches the minimax rate for least-squares regression, and a bias term $R^2\|\theta_0-\theta^*\|^2/(\gamma n)$. Neither involves the smallest eigenvalue of $H$, so the guarantee survives ill-conditioning, which is the regime of high-dimensional learning. The bound is the basis for the paper's later results: the high-probability bound (Theorem 2) and the constant-step algorithm for logistic regression (Theorem 3), whose analysis invokes Theorem 1 for the quadratic approximations.

Formalizing it. The result is proved in the paper; nothing here is open. To our knowledge no part of it has been machine-checked. A formalization yields a reusable layer for linear stochastic approximation in finite dimension: martingale-difference noise in $\mathbb R^d$, second-moment bounds for linear recursions driven by random operators, Loewner-order arguments, and averaging. The lemmas are stated for an abstract filtration and an abstract operator $H$, so they apply beyond this model. The mission also records the corrections the appendix needs (an "$=$" that should be "$\preccurlyeq$" in (13), an index in (16), and the exponent of $\|\eta_0\|$ in A.5).

Difficulty

Two steps resist the naive approach. First, the obvious one-step analysis — expand $\|\theta_n-\theta^*\|^2$ and take expectations — yields the bias part and Lemma 1, but on the noise it gives only $\gamma\sum_k\mathbb E\|\xi_k\|^2/n$, which does not decrease with $n$. The $\sigma^2d/n$ rate requires averaging to cancel the noise, and this cancellation is visible only for the recursion with $x_n\otimes x_n$ replaced by its mean $H$. The random recursion is therefore expanded in powers of $\gamma$ around the mean recursion, and each term $\eta^r$ needs its own covariance bound, by induction on $r$, using the independence of $x_n$ from $\eta^{r}_{n-1}$. Second, the induction relies on Loewner-order bookkeeping: sums of $(I-\gamma H)^{2k}H$ must be bounded uniformly in $n$ without dividing by small eigenvalues.

Formalization scope

The space $\mathcal H$ is EuclideanSpace ℝ (Fin d). Operators are continuous linear maps, and $H^{-1}$ is an explicit two-sided inverse. Observations are indexed from $1$. Averages are $\bar p_{n-1}=n^{-1}\sum_{k=0}^{n-1}p_k$, with $n\ge1$ in every statement that uses them. The covariance operator is defined by its bilinear form, $\langle v,Hw\rangle=\mathbb E[\langle x_1,v\rangle\langle x_1,w\rangle]$. Every Loewner inequality whose sides are expectations is an inequality of quadratic forms (for example $\mathbb E\langle\xi_1,v\rangle^2\le\sigma^2\langle v,Hv\rangle$ for all $v$), which is the same order for self-adjoint operators.

Lean's Bochner integral is $0$ on non-integrable functions, so every moment assumption carries the integrability of its integrand, and every bounded expectation in a conclusion is paired with an integrability conjunct. Without these, a heavy-tailed $x_n$ would satisfy (A6) vacuously and a conclusion could hold through the value $0$; neither formalization is acceptable. Independence is of the pairs $(x_n,z_n)$, not of $x_n$ and $z_n$ separately. (A4) is attainment of the minimum, not a gradient condition.

The following hypotheses are added to the page and disclosed in each item:

• $\gamma>0$ (a step size, and $\sqrt{\gamma R^2}$ is a denominator);
• $n\ge1$;
• the positivity and self-adjointness of $H$ in Lemma 2;
• $\gamma R^2<1$ instead of $\le1$ in the remainder bound, which divides by $1-\gamma R^2$.

A complete development needs:

• conditional expectations of $\mathbb R^d$-valued martingale differences, and the orthogonality of their sums;
• independence of a fresh observation from the past iterates;
• spectral calculus for $(I-\gamma H)^k$;
• Minkowski's inequality in $L^2$.

All of these are reusable for other stochastic-approximation missions. Proofs of any milestone are welcome, as are alternative arguments for the noise bound that avoid the expansion.

Selected references

• F. Bach and E. Moulines, Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n), Advances in Neural Information Processing Systems 26, 2013. https://arxiv.org/abs/1306.2119
• B. T. Polyak and A. B. Juditsky, Acceleration of stochastic approximation by averaging, SIAM Journal on Control and Optimization 30(4), 1992. https://doi.org/10.1137/0330046
• R. Aguech, E. Moulines and P. Priouret, On a perturbation approach for the analysis of stochastic tracking algorithms, SIAM Journal on Control and Optimization 39(3), 2000. https://doi.org/10.1137/S0363012997331639
• F. Bach and E. Moulines, Non-asymptotic analysis of stochastic approximation algorithms for machine learning, Advances in Neural Information Processing Systems 24, 2011. https://hal.science/hal-00608041

Motivation

A firm that sets prices without knowing how demand responds to them has to learn the demand curve from its own sales. Each price it charges is both a revenue decision and an experiment. The natural policy, certainty equivalent pricing, re-estimates the demand parameters after every period and charges the price that would be optimal if the estimates were exact. den Boer and Zwart show that this policy can fail: with positive probability its prices settle at a suboptimal value, because they converge too fast for the estimates to keep improving (den Boer–Zwart 2014, Proposition 1, the subject of the companion mission). The same phenomenon was found by Lai and Robbins (1982) for a linear control problem.

Their remedy, Controlled Variance Pricing (CVP), keeps certainty equivalent pricing but forces the sample variance of the chosen prices to decay no faster than $t^{\alpha-1}$. The main result is that this small amount of enforced exploration gives regret $O(T^\alpha + T^{1-\alpha}\log T)$, hence $O(T^{1/2+\delta})$ for every $\delta > 0$, for a broad class of demand models that are specified only through their first two moments. Keskin and Zeevi (2014) later placed CVP in a larger family of semi-myopic policies with $\sqrt T\log T$ regret for linear demand.

Setting

A seller chooses in each period $t = 1, 2, \dots$ a price $p_t \in [p_l, p_h]$, with $0 < p_l < p_h$, and then observes demand $d_t$. Demand at price $p$ has mean $h(a_0^{(0)} + a_1^{(0)}p)$ and variance $\sigma^2 v(h(a_0^{(0)} + a_1^{(0)}p))$, where the link $h$ and variance function $v$ are known and $C^2$ on $[0,\infty)$, $\dot h > 0$, and the parameter $a^{(0)} = (a_0^{(0)}, a_1^{(0)})$ with $a_0^{(0)} > 0 > a_1^{(0)}$ is unknown. The noise $e_t = d_t - h(a_0^{(0)} + a_1^{(0)}p_t)$ is a martingale difference with conditional variance $\sigma^2 v(\cdot)$ and a uniformly bounded conditional moment of some order $r > 3$.

The expected revenue is $r(p, a) = p\,h(a_0 + a_1p)$. Near $a^{(0)}$ it has a unique maximizer $p(a)$ in the open interval $(p_l, p_h)$ with $\partial_p^2 r < 0$ there, and $p_{\mathrm{opt}} = p(a^{(0)})$. The regret of a policy is

$$\operatorname{Regret}(T) = \mathbb E\Big[\sum_{t=1}^T r(p_{\mathrm{opt}}, a^{(0)}) - r(p_t, a^{(0)})\Big].$$

The estimate $\hat a_t$ is the maximum quasi-likelihood estimate (MQLE), the root of the quasi-score equation (3), $\sum_{i\le t} \frac{\dot h}{\sigma^2 v(h)}(1, p_i)^\top(d_i - h(\hat a_0 + \hat a_1 p_i)) = 0$. With $\bar p_t$ and $\operatorname{Var}(p)_t$ the sample mean and variance of $p_1,\dots,p_t$, the taboo interval is $\mathrm{TI}(t) = (\bar p_t - w_t, \bar p_t + w_t)$ with $w_t = \sqrt{c[(t+1)^\alpha - t^\alpha](t+1)/t}$. CVP starts from two distinct prices $p_1, p_2$, fixes $\alpha \in (0,1)$ and $0 < c < 2^{-\alpha}(p_1-p_2)^2\min\{1,(3\alpha)^{-1}\}$, and for $t \ge 2$: if $\hat a_t$ does not exist or has the wrong signs, it charges whichever of $p_1, p_2$ is farther from $\bar p_t$; otherwise it charges $p(\hat a_t)$ if that keeps $\operatorname{Var}(p)_{t+1} \ge c(t+1)^{\alpha-1}$, and the best price outside $\mathrm{TI}(t)$ if not.

Formalization targets

Goal: Theorem 1

$$\operatorname{Regret}(T, \mathrm{CVP}) = O\big(T^\alpha + T^{1-\alpha}\log T\big) \qquad (1/2 < \alpha < 1),$$

stated as: there is $K > 0$, depending on the model, $\alpha$, $c$ and the initial prices but not on $T$, with $\operatorname{Regret}(T) \le K(T^\alpha + T^{1-\alpha}\log T)$ for all $T \ge 1$. The constant is left free, so the statement survives any sharpening of the constants.

Milestones

1. Proposition 2: $\operatorname{Var}(p)_t \ge c\,t^{\alpha-1}$ for all $t \ge 2$ along every CVP path.
2. Lemma 1: $\lambda_{\max}(P_t) \le (1+p_h^2)t$ and $t\operatorname{Var}(p)_t \le (1+p_h^2)\lambda_{\min}(P_t)$ for the design matrix $P_t = \sum_{i\le t}(1,p_i)^\top(1,p_i)$.
3. Proposition 3: $\hat a_t$ eventually exists, $\hat a_t \to a^{(0)}$ a.s., and for some $\rho_0$, $\mathbb E[T_{\rho_0}^{1/2}] < \infty$ and $\mathbb E[\|\hat a_t - a^{(0)}\|^2\mathbf 1_{t > T_{\rho_0}}] = O(\log t/t^\alpha)$.
4. Eq. (11): in the normal–linear case, $\mathbb E\|\hat a_t - a^{(0)}\|^2 = O(\log t / t^\alpha)$.
5. Eqs. (17), (18), (20): the quadratic revenue gap, the local Lipschitz bound on $p(a)$, and $|p_{t+1} - p(\hat a_t)| \le |\mathrm{TI}(t)|$ for large $t$.
6. The closing bound $\mathbb E[(p_t - p_{\mathrm{opt}})^2] = O(t^{\alpha-1} + \log t/t^\alpha)$.

Significance

The theorem shows that a policy that is certainty equivalent almost all of the time, with a single interpretable tuning parameter $\alpha$, attains regret $O(T^{1/2+\delta})$ in generalized linear demand models, without distributional assumptions beyond two moments. It explains the role of $\alpha$ precisely: $T^\alpha$ is the cost of exploration and $T^{1-\alpha}\log T$ the cost of estimation error. Proposition 2 and Lemma 1 are reusable for any policy that enforces a variance floor on its actions, and (11) is a self-contained rate for least squares under adaptively chosen designs.

The result is proved in the paper, with Proposition 3 delegated to den Boer and Zwart (2012) for general links. To our knowledge none of it has been machine-checked. A formalization would verify the delegated consistency argument, fix the conditions under which it applies (see Formalization scope), and provide a Lean development of adaptive least squares and quasi-likelihood rates that the related Keskin–Zeevi missions also need.

Difficulty

The deterministic parts are short. The difficulty is Proposition 3. The prices are chosen adaptively from past data, so the regressors are not independent of the noise, and standard rates for (quasi-)likelihood estimates do not apply. The natural argument, bounding $\|\hat a_t - a^{(0)}\|^2$ by $Q_t/\lambda_{\min}(P_t)$ with $Q_t$ a self-normalized martingale quadratic form, needs a bound $\mathbb E[Q_t] = O(\log t)$ that holds in expectation and not only almost surely, as in Lai and Wei (1982). For a non-linear link the MQLE is defined only implicitly, and its existence near $a^{(0)}$ has to be shown first, with a moment bound on the last time it fails. That is the random time $T_\rho$. Turning almost-sure consistency into a rate in expectation is where most of the work lies.

Formalization scope

All declarations live in the namespace CVPricing.Regret. Periods are 1-based. Prices, demands and parameters are real; $a = (a_0, a_1) \in \mathbb R \times \mathbb R$ with the Euclidean norm (euclidNorm), not Mathlib's sup norm. The design matrix, sample mean and $t\operatorname{Var}(p)_t$ are the published Keskin–Zeevi definitions fisherOf, avgPriceOf, infoMetricOf. Every $O(\cdot)$ is "there is $K > 0$ such that for all $t$", with $K$ quantified after the model data. Rates are stated for $t \ge 2$ and the regret for $T \ge 1$. $h$ and $v$ are total functions constrained on $[0,\infty)$. A root of (3) counts only where $\hat a_0 + \hat a_1 p_i \ge 0$ for every observed $p_i$. CVP is a predicate on a realized path that allows every maximizer in (7) and (8).

Disclosed deviations from the page:

• the model requires $a_0^{(0)} + a_1^{(0)}p_h > 0$ (printed: $\ge 0$), because in the boundary case the policy's case (c) fires infinitely often and the proof of Theorem 1 does not cover it;
• (3) is assumed to have at most one root (the page notes roots need not be unique, and the policy cannot select the root nearest $a^{(0)}$);
• the neighbourhood assumption is read as a unique maximizer over $[p_l, p_h]$ lying in $(p_l, p_h)$;
• the demand process is given by its conditional mean, its conditional variance and (2), with integrable noise moments, not by a fixed law $D(p)$;
• the initial prices are deterministic.

Corrected slips: Proposition 2 is stated for $c \le 2^{-\alpha}(p_1-p_2)^2\min\{1/2,(3\alpha)^{-1}\}$, because the printed range fails at $t=2$ ($\operatorname{Var}(p)_2 = (p_1-p_2)^2/4$, not $/2$). Theorem 1 keeps the printed range. Eq. (20) is stated for $p_{t+1}$ and for $t$ beyond an explicit threshold.

The goal does not assume the variance bound, consistency or (20). The policy contains the variance check and the taboo interval, and the regret is the expectation over the actual price process. A statement that assumed any of these, or that dropped the taboo step, would be trivial or false. Contributions are welcome on adaptive least squares (Sherman–Morrison and determinant-ratio bounds), martingale last-time moment bounds, and the implicit-function step (18).

Selected references

• A. V. den Boer, B. Zwart, Simultaneously Learning and Optimizing Using Controlled Variance Pricing, Management Science 60(3):770–783, 2014. https://doi.org/10.1287/mnsc.2013.1788
• A. V. den Boer, B. Zwart, Mean square convergence rates for maximum quasi-likelihood estimators, Stochastic Systems 4(2):375–403, 2014 (cited as 2012 working paper). https://doi.org/10.1214/12-SSY086
• T. L. Lai, C. Z. Wei, Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems, Annals of Statistics 10(1):154–166, 1982. https://doi.org/10.1214/aos/1176345697
• T. L. Lai, H. Robbins, Iterated least squares in multiperiod control, Advances in Applied Mathematics 3(1):50–73, 1982. https://doi.org/10.1016/S0196-8858(82)80005-5
• N. B. Keskin, A. Zeevi, Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies, Operations Research 62(5):1142–1167, 2014. https://doi.org/10.1287/opre.2014.1294

Why myopic pricing is a problem

A seller who does not know how demand responds to price has to learn the demand curve from its own sales while it is selling. The most natural policy is certainty equivalent pricing (also called myopic pricing or passive learning): after every period, estimate the unknown demand parameters from all data collected so far, and charge the price that would be optimal if the estimates were the truth. It is simple, uses all data, and is what a price manager would do without further thought.

den Boer and Zwart (Management Science 60(3):770–783, 2014) show that this policy can fail. In the linear-demand, Gaussian-noise model, the prices it produces fail to converge to the optimal price with positive probability: the policy is not strongly consistent. The result motivates the paper's main contribution, controlled variance pricing, which adds just enough price dispersion to keep learning (treated in the companion mission of this series).

The phenomenon has a history in adaptive control:

• 1976. Anderson and Taylor study the linear system $y_t = a_0 + a_1x_t + \epsilon_t$ controlled by a certainty equivalent rule that steers $y_t$ to a target, and examine by simulation the statistical properties of the least squares estimates it produces (Econometrica 44(6), 1976).
• 1982. Lai and Robbins (Adv. Appl. Math. 3(1), 1982) prove that there are parameter values for which the certainty equivalent controls converge with positive probability to a value different from the optimal control.
• 2014. den Boer and Zwart adapt the argument to revenue maximization with linear demand, without the conditions Lai and Robbins place on the initial inputs and the input bounds: any two different initial prices in $[p_l, p_h]$ give the failure with positive probability.

Setting

A monopolist sells one product in periods $t = 1, 2, \dots$ at prices $p_t$ from an interval $[p_l, p_h]$ with $0 < p_l < p_h$. The demand in period $t$ is

$$d_t = a_0^{(0)} + a_1^{(0)} p_t + e_t ,$$

where $e_1, e_2, \dots$ are independent $N(0, \sigma^2)$ random variables. The parameters are unknown to the seller and satisfy $\sigma > 0$, $a_0^{(0)} > 0$, $a_1^{(0)} < 0$, $a_0^{(0)} + a_1^{(0)}p_h \ge 0$. The expected revenue at price $p$ is $r(p, a_0, a_1) = p(a_0 + a_1p)$, maximized at the optimal price

$$p_{\mathrm{opt}} = -\frac{a_0^{(0)}}{2a_1^{(0)}}, \qquad p_l < p_{\mathrm{opt}} < p_h .$$

Certainty equivalent pricing charges two different initial prices $p_1 \ne p_2$ in $[p_l, p_h]$. After $t \ge 2$ periods it computes the least squares estimates $\hat a_t = (\hat a_{0t}, \hat a_{1t})$, the solution of the normal equations $\sum_{i \le t}(1, p_i)^{\mathsf T}(d_i - \hat a_{0t} - \hat a_{1t}p_i) = 0$, and charges

$$p_{t+1} = \arg\max_{p \in [p_l, p_h]} p\,(\hat a_{0t} + \hat a_{1t}p),$$

with $p_{t+1} = p_h$ when the estimated slope $\hat a_{1t}$ is nonnegative.

Formalization targets

Goal: Proposition 1

$$P\big(p_t \not\to p_{\mathrm{opt}}\big) > 0 .$$

The goal states only the failure of convergence, for every admissible parameter and every pair of different initial prices; it does not fix where the prices go.

Stronger: the prices stick at the boundary

$$P\big(p_t = p_h \ \text{for all } t \ge 3\big) > 0 .$$

This is what the paper's argument establishes; since $p_{\mathrm{opt}} < p_h$ it implies the goal.

Milestones

The milestones are the displayed steps of the appendix proof, in attack order: the determinant of the coefficient matrix of the linear system (12); the bound $P(\sup_{t \ge 3}|(t-2)^{-1}\sum_{i=3}^t e_i| > \epsilon) \le 8\sigma^2\epsilon^{-2} < 1$ for $\epsilon > \sqrt 8\,\sigma$; positivity of the probability of an explicit event $A_\delta$ on the noise for large $\delta$; the case $t = 2$ (the first fitted line pushes $p_3$ to $p_h$); the representation $\hat a_t - a^{(0)} = (\bar e_t - \bar p_tC_t/V_t,\ C_t/V_t)$ of the least squares error; recursive and closed forms of $V_t$ and $C_t$; and the deterministic induction that every noise path in $A_\delta$ keeps the price at $p_h$ forever.

Significance

The result is the standard counterexample to certainty equivalence in dynamic pricing. It shows that estimation and optimization cannot be separated naively: a policy that always exploits its current estimate can lock itself into a price at which the data no longer move the estimate enough to correct it. Every later policy in this literature that forces exploration (controlled variance pricing, semi-myopic policies, constrained iterated least squares) is designed against this failure, and its necessity is argued by pointing to results of this kind.

The result is proved in the paper; nothing here is open. To our knowledge it has no machine-checked proof. Formalizing it adds:

• a verified pathwise analysis of the least squares recursion along a price path, reusable for other proofs about adaptive estimation with two parameters;
• a verified maximal bound for running means of i.i.d. Gaussian noise, of the kind used in many consistency proofs;
• a clean probabilistic statement of the failure, against which consistency results for exploration policies can later be contrasted.

Difficulty

The obvious heuristic, "with positive probability the first two observations are so noisy that the fitted slope is wrong", is not enough: one bad estimate is corrected by later data unless the policy stops generating informative data. The proof has to control the whole infinite future. It does so by showing that on a single event, defined through the first two noise values and a uniform bound on all later running means, the price stays at $p_h$ forever, which requires the closed form of the least squares estimate along a price path that is constant from period 3 on. That event involves infinitely many noise variables, so its probability is positive only through a maximal inequality, and independence between $(e_1, e_2)$ and the later noise. A second subtlety is the choice of constants: the size of the band $\delta$ enters the conditions on $(e_1, e_2)$, so the order in which $\delta$ and the set of admissible $(e_1, e_2)$ are chosen matters (the printed proof picks them in a circular order; a non-circular choice exists).

Formalization scope

• Model. CVPricing.CertEquiv.Model bundles $p_l, p_h, a_0^{(0)}, a_1^{(0)}, \sigma$ with the standing assumptions of §2 as fields, including $p_l < p_{\mathrm{opt}} < p_h$ (the paper's neighbourhood assumption specialized to linear demand). The noise is the referenced published definition RobustBooking.Shared.GaussianNoise (measurable, mutually independent, each $N(0, \sigma^2)$); its Lean index $k$ is period $k+1$, so the paper's $e_i$ is ε (i - 1).
• Policy. cePrice is a deterministic recursion on a noise path, so the random price process is obtained by evaluating it at $\omega$. Periods are 1-based. The least squares estimate is the referenced KeskinZeevi.SufficientConditions.lsEstimateOf, the solution of the normal equations (4), unique whenever $p_1 \ne p_2$. The certainty equivalent rule is the projection of $-\hat a_{0t}/(2\hat a_{1t})$ onto $[p_l, p_h]$ when $\hat a_{1t} < 0$, and $p_h$ when $\hat a_{1t} \ge 0$; the latter is the convention the paper's proof adopts for wrong-signed estimates.
• Corrected slips. The definition of the event $A$ is printed with "$\delta|\bar e_t| \le \delta$" (read $|\bar e_t| \le \delta$) and with its second line missing a factor $\delta$ on the term $(2p_h - p_1 - p_2)$; both are restored as in (12) and the last display of the proof. The intercept of the first fitted line is printed without $a_0^{(0)}$; the correct intercept is stated, and the printed condition remains sufficient for $p_3 = p_h$.
• WLOG. The steps of the proof assume $p_1 < p_2$ and are stated under that ordering; the goal and the stronger statement cover $p_1 \ne p_2$.
• No trivialization. The goal is a statement about the Gaussian law of the noise: a theorem that exhibits one bad noise path, or that assumes $P(A) > 0$, does not prove it. The event in the goal is a set of outcomes whose measurability is not asserted.
• Welcome contributions. Kolmogorov's maximal inequality for sums of independent square-integrable variables; least squares identities for two-parameter regression; the independence argument separating $(e_1, e_2)$ from the later noise.

Selected references

• A. V. den Boer, B. Zwart, Simultaneously Learning and Optimizing Using Controlled Variance Pricing, Management Science 60(3):770–783, 2014. https://doi.org/10.1287/mnsc.2013.1788
• T. L. Lai, H. Robbins, Iterated least squares in multiperiod control, Advances in Applied Mathematics 3(1):50–73, 1982. https://doi.org/10.1016/S0196-8858(82)80005-5
• T. W. Anderson, J. B. Taylor, Some experimental results on the statistical properties of least squares estimates in control problems, Econometrica 44(6):1289–1302, 1976. https://doi.org/10.2307/1914261
• Y. S. Chow, H. Teicher, Probability Theory: Independence, Interchangeability, Martingales, 3rd ed., Springer, 2003. https://doi.org/10.1007/978-1-4612-1950-7