Theorem 3 — logarithmic lower bound on worst-case regret with a known incumbent price
ProvedKeskinZeevi.IncumbentLowerBound.regret_lower_bound_logConsider the incumbent price model of §3.4. Prices lie in with . The seller knows an incumbent price and the incumbent demand at that price, so that (the incumbent price relation (18)). The unknown slope lies in with , and the optimal price is interior to for every . Demand in period is , where and the shocks are i.i.d. with .
Theorem 3. There exists a finite positive constant such that for every pricing policy and every horizon ,
Here is the worst-case regret (22), and is the natural logarithm.
Knowing the demand at one price lets the seller learn "for free" whenever it charges any other price, and the attainable regret drops from order (Theorem 1) to order . This theorem shows that cannot be beaten. Theorem 4 shows that it is achieved.
Formalization Note. The constant is chosen before the probability space, the noise, the policy and the horizon, so it depends only on the model . Policies are deterministic and non-anticipating, and their price process is generated from the noise by the recursion of the policy definition. The hypotheses and are fields of the model; they are implicit on the page, and without the theorem is false.
import Mathlib import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Model import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Policy import Definitions.Def_RobustBooking_Shared_GaussianNoise import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Regret open RobustBooking.Shared open MeasureTheory
namespace KeskinZeevi.IncumbentLowerBound
/-- Theorem 3 (Lower Bound on Regret), p. 1149: under the incumbent price relation (18) there
is a finite positive constant `c`, depending only on the model `M` (price interval, incumbent
price and demand, slope interval, noise level), such that `Δ^π(T) ≥ c log T` for every pricing
policy `π` and every horizon `T ≥ 3`; `Δ^π(T)` is the worst-case regret (22) over
`{β ∈ 𝔅 : ψ(β) ≠ 0}`. -/
theorem regret_lower_bound_log (M : Model) :
∃ c : ℝ, 0 < c ∧
∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
∀ (π : Policy M.l M.u) (T : ℕ), 3 ≤ T →
c * Real.log T ≤ worstRegret M P ε π T := by sorry
end KeskinZeevi.IncumbentLowerBound
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix a model , an object of the bundle's type Model. The statement uses four named parts of :
- , a noise parameter;
- and , two parameters that index the policy class;
- itself, which is passed whole to the regret functional.
The type Model is defined in the imported file Def_KeskinZeevi_IncumbentLowerBound_Model, whose code is not shown here. Nothing in this statement constrains further. In particular, it imposes no relation between and and no sign condition on , beyond whatever the definition of Model itself enforces.
The statement asserts that there is a real number with
such that the following holds. The number is chosen after and before everything below, so it may depend on only.
For every measurable space , every probability measure on , and every real-valued process
suppose the hypothesis holds. This predicate comes from the imported file Def_RobustBooking_Shared_GaussianNoise, whose code is not shown here. The statement uses it only as an assumption relating , and the sequence . No measurability, independence or distributional property of is assumed beyond what that predicate contains.
Then, for every policy and every natural number with ,
where:
- ranges over the bundle's type , defined in
Def_KeskinZeevi_IncumbentLowerBound_Policy; - is the natural logarithm of , viewed as a real number;
- is the real number
worstRegret M P ε π T, defined inDef_KeskinZeevi_IncumbentLowerBound_Regret.
The definitions of and are not shown, so what this real number measures cannot be read off from the code given. The accompanying doc comment describes as a worst-case regret over a parameter set and as depending on specific model quantities, but that comment is not part of the formal assertion.
The constant is uniform across three things:
- every probability space and every noise process satisfying the hypothesis;
- every policy;
- every horizon .
The statement does not claim that is finite in any sense beyond being a real number, nor that it is computable or given by any formula.
Degenerate cases.
- Probability space. Because is a probability measure, must be nonempty. A one-point is allowed whenever can hold there.
- Unsatisfiable noise hypothesis. If can never hold for this , for example because of a degenerate , the inner claim is vacuous. The whole statement then holds with any .
- Empty policy type. If is empty, for instance for some relation between and , the claim is likewise vacuous.
- Small horizons. The horizons are excluded. For we have , so the left side is strictly positive. The statement therefore forces for every admitted .
- Junk values in the regret. Suppose is internally a supremum over an empty or unbounded set, where the real-valued supremum returns the default . Or suppose it is an expectation of a non-integrable function, where the integral returns . In either case the statement would require , which is impossible. So the theorem can only hold if, for every admitted case, is a genuine value bounded below by .
Whether such junk values can arise depends on definitions not visible here.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.