Theorem 1 — expected regret of adaptive binning and exploration
DisprovedChenGallegoPricing.ABE.theorem_1Fix a positive integer and positive constants . There is a constant such that for every measurable demand , every Borel probability covariate law , and every bin-law version satisfying the model's conditioning convention, if satisfies all clauses of Assumptions 2–3 with those constants, then for every positive integer horizon and every admissible measurable ABE tie rule and split-price completion,
The policy is the concrete Algorithm 1 recursion with the exact §3.4 tuning, and regret compares to the continuous-price optimum. The covariates and fresh purchase noise have the stated independent/conditional Bernoulli laws. The constant is independent of the demand, covariate law, horizon, and choices of ties or missing prices after and the four regularity constants are fixed. The false Lemma 2 is not assumed or imported. No lower horizon threshold is imposed: in particular the assertion includes . Insight I3 records its counterexample there; insight I2 records the algorithmic omission.
Differences from the source:
- generalization: C is positive and independent of T → for fixed positive d and M₁,M₂,M₃,M₄ one C works for every admissible demand, covariate law, bin-law version, horizon and measurable ABE completion; reason: the minimax formulation and constants on pp. 31–33 support uniformity; fixing an instance recovers the printed claim
- reading: conditional bin revenue on every rectangle, including singletons → all supported probability-law versions on null rectangles, normalized restriction on positive-mass rectangles, and Dirac laws on singletons; reason: conditioning on a null event has no canonical law; this retains arbitrary covariate laws and the stated singleton revenues
- reading: Algorithm 1 lines 15–22 assign no price on a splitting round → every measurable history/current-covariate-based price in [0,1] is allowed there, its usual feedback is observed but discarded from bin statistics, and exactly one split consumes the round; reason: retain every completion of the printed transition relation rather than selecting a favorable omitted action
- encoding: grids and thresholds are displayed even for terminal bins → only active exploration or splitting branches evaluate them; terminal bins charge their midpoint, including T=1 and T=2; reason: inactive singular metadata have no effect on any action or observation
- encoding: prices, covariates, revenue observations and expectations are described probabilistically → Euclidean cube and closed-unit-price subtypes, finite histories, independent covariate/uniform draws, revenue p times a threshold-generated purchase bit, and an integral of the finite sum of gaps; reason: this realizes the stated conditional Bernoulli law and equals the sum of expectations; the source’s measurability convention is explicit
- encoding: dyadic bins store grid spacing and empirical statistics → cells have level/integer-coordinate addresses, spacing is computed from endpoints, and histories are replayed to reconstruct the state; clipping to [0,1] only totalizes off-domain metadata; reason: reachable valid states have a unique active cell, in-range grid prices and the same counters, means and decisions
- reading: the ceiling glyph in §3.4 and the conflicting verbal ceiling description in the p. 26 notation table → the conventional ceiling, the smallest integer not less than its argument; reason: the formula glyph is unambiguous and the table’s smallest integer not exceeding x does not exist; insight I5 records the typo
import Mathlib import Definitions.Def_ChenGallegoPricing_ABE_Geometry import Definitions.Def_ChenGallegoPricing_ABE_Model import Definitions.Def_ChenGallegoPricing_ABE_Algorithm import Definitions.Def_ChenGallegoPricing_ABE_Process open MeasureTheory
namespace ChenGallegoPricing.ABE
theorem theorem_1 (d : ℕ)
(hd : 0 < d)
(M₁ M₂ M₃ M₄ : ℝ)
(hM₁ : 0 < M₁) (hM₂ : 0 < M₂) (hM₃ : 0 < M₃) (hM₄ : 0 < M₄) :
∃ C : ℝ, 0 < C ∧ ∀ (D : Demand d), Measurable D →
∀ (μ : Measure (Ctx d)) [IsProbabilityMeasure μ]
(ν : Set (Ctx d) → Measure (Ctx d)),
IsBinLaw μ ν → Assumption2 D M₁ → Assumption3 D ν M₂ M₃ M₄ →
∀ T : ℕ, 0 < T → ∀ (tie : TieRule d) (completion : Policy d),
IsAdmissibleABE T M₂ tie completion →
regret D μ (abePolicy T M₂ tie completion) T ≤
C * (T : ℝ) ^ (((d : ℝ) + 2) / ((d : ℝ) + 4)) * (Real.log T) ^ 2 := by sorry
end ChenGallegoPricing.ABE
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix an integer and four real constants . The statement asserts that there is a constant , depending only on , such that the regret bound
holds simultaneously for every demand function , context law , family of bin laws , horizon , tie rule and completion policy satisfying the hypotheses below. Here is the natural logarithm and the power is a real power.
Spaces.
- A context is a point . This is the half-open unit cube in Euclidean space , with the Euclidean norm and the Borel structure inherited from .
- A price is a point , which is closed.
Quantified objects and hypotheses.
- Demand. is any jointly measurable function. plays the role of a purchase probability. Write for the expected revenue.
- For each , let be some fixed (choice-selected) maximizer of over if a maximizer exists, and otherwise.
- Let .
- Context law. is any probability measure on . No density or other regularity is assumed.
- Bin laws. assigns a measure on to every subset . A rectangle is a nonempty measurable set of the form with each an interval. Degenerate intervals (single points) are allowed, so singletons, segments and faces count as rectangles. must satisfy:
- For every rectangle :
- is a probability measure with ;
- if , then .
- If , is otherwise unconstrained.
- For every : , the point mass at .
- On non-rectangles is unconstrained.
- For every rectangle :
- Lipschitz assumption with constant . For all and :
The second clause makes continuous on , so a maximizer exists and is a genuine maximizer. 5. Bin-level assumption with constants . For a rectangle , let be the bin revenue curve (a Bochner integral). Let be a choice-selected maximizer of on , or if none exists. For every rectangle (not only dyadic cells):
- (a) has exactly one maximizer on , so is that unique maximizer.
- (b) For every :
- (c) .
- (d) , where is the Euclidean diameter in .
Since is nonempty and takes values in , these infima and suprema are ordinary finite ones. Because singletons are rectangles with , clauses (a)–(b) apply pointwise: for every , has a unique maximizer, and
Applying (d) to the box spanned by two points gives . 6. Horizon. is any natural number with . 7. Tie rule and completion. and are arbitrary functions of a history (a finite list of observations ) and a context . They must be admissible:
- For each length , the maps , and are measurable on .
- Whenever the algorithm's current cell for (defined below) has level below and its visit count satisfies , then and for all . Here are that cell's stored averages. In words: on such rounds, returns an index of a maximal stored average among .
The policy .
Parameters:
Here and are natural numbers obtained by truncating at .
Dyadic cells:
- The level- cell with integer indices is .
- Its children are the level- cells with indices , .
- The root is the level- cell, equal to all of .
State:
- The state is a finite set of active cells together with, for every cell, a record consisting of:
- a visit count ;
- an interval ;
- per-index counts ;
- per-index averages .
- Initially only the root is active, and every cell's record is , , all .
- The active cells always cover , since they start at the root and a split replaces a cell by its children. Each context is assigned to some active cell containing it, selected by choice; the root is a fallback that is never reached.
Grid prices are , and prices are clamped to when quoted.
Given a history , the state is obtained by replaying from the initial state. Each observation updates the state using , and the prefix of before it; the recorded price itself is ignored. The policy then quotes for a new context as follows. Let be its cell, with level and record .
- Exploration — if and :
- Quote .
- On update, increases by , increases by and becomes the running mean , where .
- Split round — if and :
- Quote .
- On update, the observed is discarded. is removed from the active set and its children are added.
- Each child gets a fresh record with , all , and interval , where is the grid price at index .
- 's own record only has incremented.
- Exploitation — if :
- Quote .
- On update only is incremented, and is discarded.
Regret.
- Draw i.i.d. pairs , , with and independent and uniform on . The joint law is the -fold product of .
- Round posts , where is the history of earlier rounds.
- It records if and otherwise, and appends to the history.
- The regret is
It is measured against the per-context optimal price over the continuum , using expected revenue rather than the realized . It is a Bochner integral, so it equals by convention if the integrand fails to be integrable (e.g. is not measurable).
Degenerate cases.
- and . The case is excluded, and is required.
- Small horizons, . Then . The root, of level , is never below , so the policy posts the constant price in every round. and are never consulted, the admissibility condition on is vacuous, and , , play no role. The regret is then , subject to the integrability convention.
- . We have , so the right-hand side is exactly and the statement asserts for every admissible instance. In that case , , and the division by yields , so ; none of these values is used.
- . , so the grid spacing divides by , which gives ; all grid prices equal , but again they are unused since .
- When grid quantities matter. Whenever (i.e. ), we have and , so no division-by-zero defaults occur in the grid.
- . Clause (b) applied to any rectangle (e.g. ) with any requires . So if , the hypotheses can never be satisfied and the statement holds vacuously for any .
- Null rectangles. For rectangles with , may be any probability measure on , and the bin-level assumption must still hold for it.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.