Theorem 4 — sufficient conditions for logarithmic regret with a known incumbent price
ProvedKeskinZeevi.IncumbentSufficient.regret_log_upper_boundConsider the incumbent price model with light-tailed i.i.d. demand shocks, and a true slope whose optimal deviation from the incumbent price is nonzero, . There is a threshold such that for every , every and every start time there is a finite constant with the following property. If a pricing policy satisfies, almost surely, for all ,
then its regret is logarithmic:
Condition (i) asks the policy to keep accumulating information at a logarithmic rate, and (ii) asks it to stay close to the greedy (certainty-equivalent) deviation . By Theorem 3 of the same paper, is the best possible order, so policies meeting (i)–(ii) are asymptotically optimal.
Formalization Note. This is a corrected form of the printed theorem, which reads "There exist finite positive constants , and such that if … satisfies (i) … (ii) almost surely for all , then …". Read literally, the existential make the statement vacuous (take so large that (i) fails for every policy at ). The proof on pp. 1159–1160 shows that any above a threshold works, that is arbitrary, and that the conditions are used only for large . The Lean statement is that content, which implies the printed statement (take , any , ). The sum in (ii) starts at , because is defined only for greedy ILS; this weakens the hypothesis. uses Lean's when , which under (i) can only happen for . The constant is chosen before the policy and the horizon, as on the page; it may depend on the model, the noise law, , , and . The regret is for the fixed true slope , not the worst case (22).
import Mathlib import Definitions.Def_RobustBooking_Shared_Noise import Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares import Definitions.Def_KeskinZeevi_IncumbentSufficient_Regret open RobustBooking.Shared open MeasureTheory ProbabilityTheory
namespace KeskinZeevi.IncumbentSufficient
/-- Keskin–Zeevi 2014, p. 1150, Theorem 4 (Sufficient Conditions for Asymptotic Optimality), in
the form its proof establishes (the printed "there exist κ₀, κ₁" makes a literal reading
vacuous): for `β ∈ 𝔅` with `ψ(β) ≠ 0` there is a threshold `κ₀' > 0` such that for every
`κ₀ ≥ κ₀'`, every `κ₁ > 0` and every start time `t₀ ≥ 1` there is a finite `C > 0` with the
following property. If a policy `π` satisfies, almost surely for all `t ≥ t₀`,
(i) `Ĵ_t ≥ κ₀ log t` and (ii) `Σ_{s=1}^t (ψ(b_s) - x_{s+1})² ≤ κ₁ log t`, then
`Δ^π_β(T) ≤ C log T` for all `T ≥ 3`. `C` does not depend on `π` or `T`. -/
theorem regret_log_upper_bound (M : Model) {Ω : Type*} [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P] (ε : ℕ → Ω → ℝ) (σ : ℝ)
(hε : LightTailedNoise P ε σ) (β : ℝ) (hβ : β ∈ M.B) (hψ : M.psi β ≠ 0) :
∃ κ₀' : ℝ, 0 < κ₀' ∧ ∀ κ₀ : ℝ, κ₀' ≤ κ₀ → ∀ κ₁ : ℝ, 0 < κ₁ → ∀ t₀ : ℕ, 1 ≤ t₀ →
∃ C : ℝ, 0 < C ∧ ∀ π : Policy M,
(∀ᵐ ω ∂P, ∀ t : ℕ, t₀ ≤ t →
κ₀ * Real.log t ≤ Jhat π β ε t ω ∧
∑ s ∈ Finset.Icc 1 t, (M.psi (truncEst π β ε s ω) - dev π β ε (s + 1) ω) ^ 2 ≤
κ₁ * Real.log t) →
∀ T : ℕ, 3 ≤ T → regret π β ε P T ≤ C * Real.log T := by sorry
end KeskinZeevi.IncumbentSufficient
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Throughout, is a model of type Model. The objects Model, Policy, LightTailedNoise, Jhat, truncEst, dev and regret are defined in the imported files Definitions.Def_RobustBooking_Shared_Noise, Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares and Definitions.Def_KeskinZeevi_IncumbentSufficient_Regret. Those files are not shown, so their contents cannot be unfolded here. What the statement itself shows about them is below. The model has a set of reals and a function . A policy ranges over the type . Given , a parameter , a noise process , a time and an outcome , there are real numbers (Jhat), (truncEst) and (dev). There is also a real number (regret), which additionally depends on the measure . The docstring gives an informal account of the source theorem. It is a comment, not part of what the code asserts.
Data and hypotheses. Fix the following:
- a model ;
- a measurable space with a probability measure ;
- a real-valued process , with ;
- a real number , with no sign or other restriction imposed in this statement;
- a real number .
Assume:
- satisfies
LightTailedNoisewith respect to and parameter (defined in an imported file, not shown); - ;
- .
Conclusion. There is a real number with the following property. For every real , every real and every natural number , there is a real constant such that the following holds for every policy of . Suppose that, for -almost every , the two conditions below hold simultaneously for all natural numbers :
That is, there is a single -null set outside of which both inequalities hold at every . Then for every natural number :
Here is the real natural logarithm applied to the natural number cast to . All of , , and are evaluated with the fixed and .
Order of quantifiers.
- may depend on , , , and .
- may depend on all of those and also on , and .
- is chosen before and , so one serves every policy meeting the hypothesis and every horizon .
- The statement only asserts that some exists. It gives no bound on how large is.
- Raising makes the condition on stronger, so the implication becomes weaker. Suppose that beyond some level no policy can meet almost surely. Then any larger makes the conclusion hold vacuously. Whether that can happen depends on the definition of
Jhat, which is not shown.
Degenerate and edge cases.
- If is empty, or
LightTailedNoisecannot be satisfied, or vanishes on all of , the statement is vacuous. Whether any of these happens depends on the imported definitions. - is nonempty because is a probability measure.
- If is empty, the claim about policies is vacuous.
- Every considered satisfies , so .
- At we have . So if , the hypothesis at requires and . The second condition means almost surely.
- The sum is never empty, since .
- The conclusion says nothing about horizons .
- For we have , so the bound is strictly positive.
- The regret is compared as a real number. Whether it can take a default value, for example from the integral of a non-integrable function or from a supremum over an empty or unbounded set, depends on the
regretdefinition, which is not shown. - Similarly,
Jhat,truncEstanddevmay involve division or truncation that returns a default value, such as division by zero giving . That cannot be seen from this statement.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.