Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — Both instance-dependent and instance-independent signed bounds for OLD and OLT

Disproved
ZhangJasinPricing.Cyclic.theorem_1

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

There exist positive constants Ψ₁ and Ψ₂, independent of the horizon and every model parameter, such that for every customer model satisfying Assumption 1, and every prescribed initialization and measurable maximizing tie choice for OLD and OLT, the minimum positive gaps Δᴰᵉᶜ and Δᵀᴿ over the full respective cyclic policy classes exist. For every integer T≥2,

RTDec≤Ψ1ΔDeclog⁡TT,RTTR≤Ψ1ΔTRlog⁡TT,R_T^{Dec}\le\frac{\Psi_1}{\Delta^{Dec}}\frac{\log T}{T},\qquad R_T^{TR}\le\frac{\Psi_1}{\Delta^{TR}}\frac{\log T}{T},RTDec​≤ΔDecΨ1​​TlogT​,RTTR​≤ΔTRΨ1​​TlogT​, RTDec≤Ψ2log⁡TT,RTTR≤Ψ2log⁡TT.R_T^{Dec}\le\Psi_2\sqrt{\frac{\log T}{T}},\qquad R_T^{TR}\le\Psi_2\sqrt{\frac{\log T}{T}}.RTDec​≤Ψ2​TlogT​​,RTTR​≤Ψ2​TlogT​​.

Here R is expected achieved revenue divided by T minus the corresponding full-class benchmark, as printed. Revenue includes initialization, clearing, and the actual final prefix. The independent bounds are separate conjuncts for every instance; they are not conditional on an assumed gap witness.

Differences from the source:

  • encoding: finite ordered prices, nonnegative cohort amounts, and a general probability law → zero-based natural-number indices with explicit bounds, real cohort amounts, and a measurable probability space; reason: the same instances are represented; real amounts also include the uniform demands used on p. 28
  • reading: Definition 1 mixes a strict maximum set with a non-strict empty-set test → the maximum and fallback use the displayed strict set; reason: the printed cases leave repeated thresholds undefined; this releases a threshold once reached and retains the larger class (I4)
  • reading: the p. 9 transition display omits the last waiting cohort → transition experiments follow equation (1), including all previous still-patient cohorts through period ℓ; reason: this is the operational definition on p. 8 and resolves the explicit indexing typo (I3)
  • reading: Assumption 1 overloads r as a mean and a realization → the ψ₂ bound one applies to revenue realizations and centered errors have finite ψ₂ norm; reason: the text says norm of all r; the informal tail display is not a separate MGF normalization
  • reading: initialization tests every parameter, with a suggested reset/high/drop procedure → any finite covering list of prescribed test blocks, with incidental high-price samples, reset observations retained as revenue, and a final reset; reason: this specifies the underdetermined testing and first-episode clearing conventions without favorable estimates or idle delays
  • reading: the constants are independent of T and all other problem parameters {rᵢ} and {rᵢⱼℓ} → the same two constants precede the model, M, K, initialization, and tie rules; reason: this is the non-narrowing reading of all other problem parameters required by the brief
  • reading: Δ is called the minimum positive gap and occurs in denominators → existence of actual least positive gaps is an explicit conclusion, with independent bounds as separate conjuncts; reason: the minimum may not exist, including on ordinary instances (I5); assuming it or replacing it by an infimum would discard source instances
  • generalization: OLT initialization tests each parameter once (p. 20); OLD says at least once (p. 13) → OLT also permits repeated targeted tests in the finite covering list; reason: choosing each parameter once recovers the printed OLT testing prescription under the declared block/reset reading; no source instance in that prescription is excluded
  • reading: the drop maximum in (2) includes j=i although drop parameters are defined only for j<i → the j=i case is its separately displayed r_i branch; reason: the p. 10 explanation separates equality from the strict-drop case; no undefined diagonal drop parameter is introduced
Preamble
import Definitions.Def_ZhangJasinPricing_Cyclic_Model
import Definitions.Def_ZhangJasinPricing_Cyclic_Policies
import Definitions.Def_ZhangJasinPricing_Cyclic_DynamicPrograms
import Definitions.Def_ZhangJasinPricing_Cyclic_Learning
import Definitions.Def_ZhangJasinPricing_Cyclic_Analysis
open MeasureTheory
open scoped BigOperators ENNReal
noncomputable section
Formal statement
namespace ZhangJasinPricing.Cyclic
theorem theorem_1 :
    ∃ Ψ₁ Ψ₂ : ℝ, 0 < Ψ₁ ∧ 0 < Ψ₂ ∧
      ∀ (Ω : Type) [MeasurableSpace Ω] (D : Model Ω) (_hA : Assumption1 D),
      ∀ (initD initT : Initialization D.M D.K) (tieD tieT : TieRule),
        (∃ ΔD ΔT : ℝ, IsLeast (positiveGaps D .decreasing) ΔD ∧
          IsLeast (positiveGaps D .threshold) ΔT ∧
          ∀ T : ℕ, 2 ≤ T →
            signedRegret D .decreasing initD tieD T ≤ Ψ₁ / ΔD * Real.log T / T ∧
            signedRegret D .threshold initT tieT T ≤ Ψ₁ / ΔT * Real.log T / T) ∧
        (∀ T : ℕ, 2 ≤ T →
          signedRegret D .decreasing initD tieD T ≤ Ψ₂ * Real.sqrt (Real.log T / T) ∧
          signedRegret D .threshold initT tieT T ≤ Ψ₂ * Real.sqrt (Real.log T / T)) := by sorry
end ZhangJasinPricing.Cyclic
Source
Zhang and Jasin (2021), DOI 10.1287/msom.2021.0979, supplied 34-page artifact, Theorem 1, pp. 22–23 (PDF pp. 22–23)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

There are universal real constants Ψ1>0\Psi_1>0Ψ1​>0 and Ψ2>0\Psi_2>0Ψ2​>0 such that the following holds. They are chosen before everything else, so they do not depend on the sample space, the numbers of prices MMM or patience levels KKK, the prices, the cohort distributions, the initialization schedules, the tie-breaking rules or the horizon TTT. The claim is: for every type Ω\OmegaΩ with a σ-algebra, every model DDD on Ω\OmegaΩ satisfying "Assumption 1", every two initializations ιD,ιT\iota_D,\iota_TιD​,ιT​ and every two tie rules τD,τT\tau_D,\tau_TτD​,τT​, both (I) and (II) below hold.

(I) Gap-dependent bound. There exist reals ΔD,ΔT\Delta_D,\Delta_TΔD​,ΔT​ such that:

  • ΔD\Delta_DΔD​ is the least element of the set of positive gaps for the decreasing class;
  • ΔT\Delta_TΔT​ is the least element of the set of positive gaps for the threshold class;
  • for every integer T≥2T\ge 2T≥2,
SRdec(T)≤Ψ1ΔD⋅log⁡TT,SRthr(T)≤Ψ1ΔT⋅log⁡TT.\mathrm{SR}_{\mathrm{dec}}(T)\le \frac{\Psi_1}{\Delta_D}\cdot\frac{\log T}{T},\qquad \mathrm{SR}_{\mathrm{thr}}(T)\le \frac{\Psi_1}{\Delta_T}\cdot\frac{\log T}{T}.SRdec​(T)≤ΔD​Ψ1​​⋅TlogT​,SRthr​(T)≤ΔT​Ψ1​​⋅TlogT​.

(II) Gap-free bound. For every integer T≥2T\ge 2T≥2,

SRdec(T)≤Ψ2log⁡TT,SRthr(T)≤Ψ2log⁡TT.\mathrm{SR}_{\mathrm{dec}}(T)\le \Psi_2\sqrt{\frac{\log T}{T}},\qquad \mathrm{SR}_{\mathrm{thr}}(T)\le \Psi_2\sqrt{\frac{\log T}{T}}.SRdec​(T)≤Ψ2​TlogT​​,SRthr​(T)≤Ψ2​TlogT​​.

Here log⁡\loglog is the natural logarithm. SRdec(T)\mathrm{SR}_{\mathrm{dec}}(T)SRdec​(T) is the "signed regret" of the decreasing-mode algorithm run with (ιD,τD)(\iota_D,\tau_D)(ιD​,τD​), and SRthr(T)\mathrm{SR}_{\mathrm{thr}}(T)SRthr​(T) is that of the threshold-mode algorithm run with (ιT,τT)(\iota_T,\tau_T)(ιT​,τT​). Both are defined below.

The existence of ΔD,ΔT\Delta_D,\Delta_TΔD​,ΔT​ is part of the conclusion, not a hypothesis. The statement therefore asserts, for every admissible model, that both positive-gap sets are nonempty and attain their infimum.

Every bound is an upper bound on

(expected average revenue)−(benchmark).\text{(expected average revenue)}-\text{(benchmark)}.(expected average revenue)−(benchmark).

None is an upper bound on benchmark minus revenue. The statement gives no lower bound on the algorithm's revenue.

The model DDD. DDD consists of the following data:

  • Integers M≥2M\ge 2M≥2 and K≥1K\ge 1K≥1.
  • A price function p:N→Rp:\mathbb N\to\mathbb Rp:N→R with pi≥0p_i\ge 0pi​≥0 for i<Mi<Mi<M, strictly decreasing on indices 0,…,M−10,\dots,M-10,…,M−1:
p0>p1>⋯>pM−1≥0.p_0>p_1>\dots>p_{M-1}\ge 0.p0​>p1​>⋯>pM−1​≥0.

The values pip_ipi​ for i≥Mi\ge Mi≥M are unconstrained.

  • A probability measure P\mathbb PP on Ω\OmegaΩ.
  • Random variables Xt(i,k)(ω)∈RX_t(i,k)(\omega)\in\mathbb RXt​(i,k)(ω)∈R ("cohort of arrival time ttt, valuation bin iii, patience kkk").
  • Reals μ(i,k)\mu(i,k)μ(i,k).

For all ttt, all i≤Mi\le Mi≤M and all k≤Kk\le Kk≤K:

  • Xt(i,k)≥0X_t(i,k)\ge 0Xt​(i,k)≥0 pointwise;
  • Xt(i,k)X_t(i,k)Xt​(i,k) is measurable and integrable;
  • E[Xt(i,k)]=μ(i,k)\mathbb E[X_t(i,k)]=\mu(i,k)E[Xt​(i,k)]=μ(i,k), the same for every ttt;
  • (Xt(i,k)−μ(i,k))2(X_t(i,k)-\mu(i,k))^2(Xt​(i,k)−μ(i,k))2 is integrable.

Nothing is said about independence across ttt, iii or kkk.

Demand. Take a cohort array C(s,a,k)C(s,a,k)C(s,a,k) and a price-index sequence π:N→N\pi:\mathbb N\to\mathbb Nπ:N→N. Write (x)+(x)^+(x)+ for truncated natural-number subtraction. The demand at period ttt is

dt(C,π)=∑k=0K ∑s=(t−k)+t ∑a=0M−11[a≤πt and pa<pπu ∀u∈{s,…,t−1}] C(s,a,k).d_t(C,\pi)=\sum_{k=0}^{K}\ \sum_{s=(t-k)^+}^{t}\ \sum_{a=0}^{M-1}\mathbf 1\Big[a\le \pi_t\ \text{and}\ p_a<p_{\pi_u}\ \forall u\in\{s,\dots,t-1\}\Big]\,C(s,a,k).dt​(C,π)=k=0∑K​ s=(t−k)+∑t​ a=0∑M−1​1[a≤πt​ and pa​<pπu​​ ∀u∈{s,…,t−1}]C(s,a,k).
  • The comparison a≤πta\le\pi_ta≤πt​ is between indices.
  • Bin MMM never enters the sum.
  • Only cohorts arriving at times s≥0s\ge 0s≥0 count.

Parameters. The parameter set is

A={(i,i,0):i<M}∪{(i,j,l):i<j<M, 1≤l≤K}.\mathcal A=\{(i,i,0):i<M\}\cup\{(i,j,l):i<j<M,\ 1\le l\le K\}.A={(i,i,0):i<M}∪{(i,j,l):i<j<M, 1≤l≤K}.

The "experiment" Ea(s)E_a^{(s)}Ea(s)​ for a parameter aaa and start time sss is defined case by case:

  • For a=(i,i,0)a=(i,i,0)a=(i,i,0):
Ea(s)=pi∑i′=0i∑k=0KXs(i′,k).E_a^{(s)}=p_i\sum_{i'=0}^{i}\sum_{k=0}^{K}X_s(i',k).Ea(s)​=pi​i′=0∑i​k=0∑K​Xs​(i′,k).
  • For a=(i,j,l)a=(i,j,l)a=(i,j,l) with i≠ji\ne ji=j:
Ea(s)=pj[∑k=1K∑s′=(l−k)+l−1∑i′=i+1jXs+s′(i′,k)+∑i′=0j∑k=0KXs+l(i′,k)].E_a^{(s)}=p_j\Big[\sum_{k=1}^{K}\sum_{s'=(l-k)^+}^{l-1}\sum_{i'=i+1}^{j}X_{s+s'}(i',k)+\sum_{i'=0}^{j}\sum_{k=0}^{K}X_{s+l}(i',k)\Big].Ea(s)​=pj​[k=1∑K​s′=(l−k)+∑l−1​i′=i+1∑j​Xs+s′​(i′,k)+i′=0∑j​k=0∑K​Xs+l​(i′,k)].

Let μˉa=E[Ea(0)]\bar\mu_a=\mathbb E[E_a^{(0)}]μˉ​a​=E[Ea(0)​].

Assumption 1 requires, for every a∈Aa\in\mathcal Aa∈A and every s∈Ns\in\mathbb Ns∈N:

  • the sub-Gaussian norm of the uncentred variable Ea(s)E_a^{(s)}Ea(s)​ is at most 111;
  • the sub-Gaussian norm of Ea(s)−μˉaE_a^{(s)}-\bar\mu_aEa(s)​−μˉ​a​ is finite.

The norm is the imported subgaussianNorm with respect to P\mathbb PP, an extended-valued quantity whose definition is not shown here. The centring uses the start-000 mean μˉa\bar\mu_aμˉ​a​ for every sss.

Words and the two policy classes. A word is a finite list w=(w0,…,wn−1)w=(w_0,\dots,w_{n-1})w=(w0​,…,wn−1​) of natural numbers. It is valid if n≥1n\ge1n≥1 and every wm<Mw_m<Mwm​<M. Its periodic extension is wt mod nw_{t\bmod n}wtmodn​. Two classes are used:

  • Decreasing class. Valid words with w0≤w1≤⋯≤wn−1w_0\le w_1\le\dots\le w_{n-1}w0​≤w1​≤⋯≤wn−1​. The indices are nondecreasing, so prices are nonincreasing.
  • Threshold class. Valid words in which every entry is at most the last entry wn−1w_{n-1}wn−1​ (an index comparison), and which satisfy a threshold condition defined next.

For the threshold condition, use one-based prices

q0=0,qt=pwt−1 for 1≤t≤n,qt=p0 for t>n.q_0=0,\qquad q_t=p_{w_{t-1}}\ \text{for } 1\le t\le n,\qquad q_t=p_0\ \text{for } t>n.q0​=0,qt​=pwt−1​​ for 1≤t≤n,qt​=p0​ for t>n.

Define θ(t)\theta(t)θ(t) as follows:

  • if q(t−1)+<qtq_{(t-1)^+}<q_tq(t−1)+​<qt​, then θ(t)=(t−1)+\theta(t)=(t-1)^+θ(t)=(t−1)+;
  • otherwise θ(t)\theta(t)θ(t) is the largest k∈{1,…,(t−2)+}k\in\{1,\dots,(t-2)^+\}k∈{1,…,(t−2)+} with qk<qk+1q_k<q_{k+1}qk​<qk+1​ and qk<q(t−1)+q_k<q_{(t-1)^+}qk​<q(t−1)+​, or 000 if there is no such kkk.

The condition is qθ(t)≤qtq_{\theta(t)}\le q_tqθ(t)​≤qt​ for all 1≤t≤n1\le t\le n1≤t≤n.

Revenue of a word and the benchmark. The mean-cycle revenue of www is

R(w)=∑t=0n−1pwt mod n dt(μ, u↦wu mod n),R(w)=\sum_{t=0}^{n-1}p_{w_{t\bmod n}}\ d_t\big(\mu,\ u\mapsto w_{u\bmod n}\big),R(w)=t=0∑n−1​pwtmodn​​ dt​(μ, u↦wumodn​),

where the cohort array is C(s,a,k)=μ(a,k)C(s,a,k)=\mu(a,k)C(s,a,k)=μ(a,k) for every sss. This is an "empty start": no cohorts exist before time 000. The average revenue is Rˉ(w)=R(w)/n\bar R(w)=R(w)/nRˉ(w)=R(w)/n.

The benchmark of a class is

V=sup⁡{Rˉ(w):w in the class},V=\sup\{\bar R(w): w \text{ in the class}\},V=sup{Rˉ(w):w in the class},

taken as a real supremum (Lean's convention gives 000 if the set is empty or unbounded above). Both classes contain every one-letter word (i)(i)(i) with i<Mi<Mi<M, so they are nonempty.

The positive-gap set of a class is

{d>0: d=V−Rˉ(w) for some w in the class}.\{d>0:\ d=V-\bar R(w)\ \text{for some } w \text{ in the class}\}.{d>0: d=V−Rˉ(w) for some w in the class}.

The algorithm. The state holds:

  • the observation list of triples (price index, sales, revenue);
  • for each parameter, a list of revenue samples;
  • the current word and an offset;
  • flags "boundary" (initially true) and "after clearing" (initially false);
  • an episode list;
  • a cycle counter ccc (initially 111).

Write NaN_aNa​ for the number of samples of parameter aaa. The sample mean is

μ^a=∑(samples of a)Na,\hat\mu_a=\frac{\sum(\text{samples of }a)}{N_a},μ^​a​=Na​∑(samples of a)​,

which is 000 when Na=0N_a=0Na​=0. The optimistic index is

Ua=μ^a+8log⁡cNa,U_a=\hat\mu_a+\sqrt{\frac{8\log c}{N_a}},Ua​=μ^​a​+Na​8logc​​,

whose square-root term is 000 when Na=0N_a=0Na​=0.

Observing price index iii with optional label aaa at time ttt (the number of observations so far) proceeds as follows:

  1. Sales are dt(X(ω),π)d_t(X(\omega),\pi)dt​(X(ω),π), where π\piπ is the past observed indices followed by iii from time ttt on.
  2. Revenue is r=pi⋅r=p_i\cdotr=pi​⋅ sales.
  3. The triple is appended to the observation list.
  4. If a label aaa is given, rrr is appended to aaa's samples.

Initialization schedule. An initialization ι\iotaι is a list of tests. Each test lies in A\mathcal AA, every element of A\mathcal AA occurs at least once, and repeats are allowed. Each test aaa contributes one block:

  • first (M−1,no label)(M-1,\text{no label})(M−1,no label);
  • then, if a=(i,i,0)a=(i,i,0)a=(i,i,0): one period (i,(i,i,0))(i,(i,i,0))(i,(i,i,0));
  • otherwise, for a=(i,j,l)a=(i,j,l)a=(i,j,l): lll periods (i,(i,i,0))(i,(i,i,0))(i,(i,i,0)) followed by (j,a)(j,a)(j,a).

The schedule is these blocks in order, followed by a final (M−1,no label)(M-1,\text{no label})(M−1,no label).

The plan options. The dynamic program dp(t,i)\mathrm{dp}(t,i)dp(t,i) returns all maximum-value pairs (word of length ttt, total value), keeping every tie:

  • For t=1t=1t=1 it is {((i),U(i,i,0))}\{((i),U_{(i,i,0)})\}{((i),U(i,i,0)​)}.
  • For t≥2t\ge2t≥2 it maximizes over two kinds of candidate:
    • "drops": a word from dp(t−1,j)\mathrm{dp}(t-1,j)dp(t−1,j) for some j<ij<ij<i, extended by iii, with value increased by U(j,i,min⁡(t−1,K))U_{(j,i,\min(t-1,K))}U(j,i,min(t−1,K))​;
    • "same":
      • in decreasing mode, a word from dp(t−1,i)\mathrm{dp}(t-1,i)dp(t−1,i) extended by iii, with value increased by U(i,i,0)U_{(i,i,0)}U(i,i,0)​;
      • in threshold mode, the concatenation of a word from dp(k+1,i)\mathrm{dp}(k+1,i)dp(k+1,i) and one from dp(t−k−1,i)\mathrm{dp}(t-k-1,i)dp(t−k−1,i), for 0≤k≤t−20\le k\le t-20≤k≤t−2, with values added.

The option list collects, for lengths 1≤t≤B1\le t\le B1≤t≤B and end indices i<Mi<Mi<M, all of dp(t,i)\mathrm{dp}(t,i)dp(t,i) with value divided by ttt. The bound is B=K+M−1B=K+M-1B=K+M−1 in decreasing mode and B=2K+M−2B=2K+M-2B=2K+M−2 in threshold mode.

Tie rule. A tie rule τ\tauτ is any function choosing, from a candidate count n>0n>0n>0, a numerical history vector hhh and candidate values vvv, an index in {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} that maximizes vvv. For each fixed nnn it must be measurable in (h,v)(h,v)(h,v).

The history vector hhh is:

  • h0h_0h0​ is the number of observations;
  • for m≥1m\ge1m≥1, hmh_mhm​ is coordinate (m−1) mod 3(m-1)\bmod 3(m−1)mod3 of observation ⌊(m−1)/3⌋\lfloor(m-1)/3\rfloor⌊(m−1)/3⌋;
  • hm=0h_m=0hm​=0 beyond the recorded observations.

The selected plan is the option at the chosen index.

Label of a word position. For the current word www at zero-based position mmm, let i=wmi=w_mi=wm​ and j=w(m−1)+j=w_{(m-1)^+}j=w(m−1)+​. The label is:

  • (i,i,0)(i,i,0)(i,i,0) if m=0m=0m=0 or pj≤pip_j\le p_ipj​≤pi​;
  • otherwise (j,i,min⁡(ℓ,K))(j,i,\min(\ell,K))(j,i,min(ℓ,K)), where ℓ=m\ell=mℓ=m in decreasing mode and ℓ=(m−θ(m+1))+\ell=(m-\theta(m+1))^+ℓ=(m−θ(m+1))+ in threshold mode.

Playing a position proceeds as follows:

  1. Observe woffsetw_{\text{offset}}woffset​ with its label.
  2. If the cycle is not finished, advance the offset.
  3. If the cycle is finished:
    • reset the offset to 000;
    • increase ccc by 111;
    • set "boundary" to true iff some label bbb used by www has 2 Nbepisode start≤Nb2\,N_b^{\text{episode start}}\le N_b2Nbepisode start​≤Nb​, where Nbepisode startN_b^{\text{episode start}}Nbepisode start​ is the count recorded at the start of the last episode, or 000 if there is none.

Starting an episode records the start time, the current counts, the current sample means and ccc, sets the word, and clears both flags.

Each period does exactly one of the following:

  • During initialization: observe the next schedule entry, with its label.
  • Else, if "after clearing" is set: start an episode with the current word and play a position.
  • Else, if "boundary" is set: select a new word w′w'w′.
    • If there was a previous word www and plast(w′)<plast(w)p_{\text{last}(w')}<p_{\text{last}(w)}plast(w′)​<plast(w)​, run one clearing period. It observes last(w′)\text{last}(w')last(w′) with label (last(w),last(w′),min⁡(∣w∣,K))(\text{last}(w),\text{last}(w'),\min(|w|,K))(last(w),last(w′),min(∣w∣,K)), adopts w′w'w′ and sets "after clearing".
    • Otherwise, start an episode with w′w'w′ and play a position.
  • Otherwise: play a position.

Exactly one observation is added per period. The run lasts exactly TTT periods, counting initialization and clearing periods.

Signed regret. Let RevT(ω)\mathrm{Rev}_T(\omega)RevT​(ω) be the sum of the revenue coordinates of the TTT observations. Then

SR(T)=E[RevT]T−V,\mathrm{SR}(T)=\frac{\mathbb E[\mathrm{Rev}_T]}{T}-V,SR(T)=TE[RevT​]​−V,

where VVV is the benchmark of the class matching the mode.

Degenerate and default-value cases.

  • Since P\mathbb PP is a probability measure, Ω\OmegaΩ is nonempty.
  • M≥2M\ge 2M≥2, K≥1K\ge 1K≥1 and T≥2T\ge 2T≥2 exclude zero counts and zero horizons, and log⁡T>0\log T>0logT>0.
  • TTT may be shorter than the initialization schedule, and the bounds are still asserted for such TTT.
  • If RevT\mathrm{Rev}_TRevT​ fails to be integrable (including failing to be measurable), its expectation is taken as 000. In that case SR(T)=−V\mathrm{SR}(T)=-VSR(T)=−V.
  • If a class's average revenues were unbounded above, VVV would be 000 by convention.
  • If a positive-gap set is empty, for example when every word in the class attains VVV, or if it has no least element because gaps accumulate at 000, then part (I) is false for that model. The theorem therefore includes the assertion that neither happens for any model satisfying Assumption 1. This holds for both classes simultaneously.
  • With no samples, μ^a=0\hat\mu_a=0μ^​a​=0 and the bonus is 000. With c=1c=1c=1, log⁡c=0\log c=0logc=0 and every bonus is 000.
  • With no prior episode, the recorded counts are 000, so the "boundary" test is automatically true.
  • All (x)+(x)^+(x)+ subtractions truncate at 000: in t−kt-kt−k, l−kl-kl−k, t−1t-1t−1, t−2t-2t−2, m−1m-1m−1 and m−θ(m+1)m-\theta(m+1)m−θ(m+1).
  • A missing maximum in θ\thetaθ is 000.
  • Out-of-range word positions read index 000, hence price p0p_0p0​.
  • Prices at indices ≥M\ge M≥M are unconstrained.
  • Assumption 1 bounds the sub-Gaussian norm of the uncentred experiments by 111, and requires only finiteness for the centred ones.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me