Proof of Theorem 3 — worst-case regret bounded below by a harmonic sum
ProvedKeskinZeevi.IncumbentLowerBound.regret_lower_bound_harmonicConsider the incumbent price model with i.i.d. demand shocks. There exist positive constants and , depending only on the model, with the following property. For every pricing policy and every horizon ,
In the paper, and , where and are the constants of Lemma 4.
This is the second display of the proof of Theorem 3. Since the harmonic sum is at least , it gives the logarithmic lower bound.
Formalization Note. The sums over are Lean sums over . and are chosen before the probability space, the noise, the policy and the horizon. The statement asserts the existence of such constants rather than fixing and , because Lemma 4's constants are themselves existential.
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
/-- Proof of Theorem 3, second display on p. 1159: with `K₁ = |b_max| c₀/(u − l)²` and
`K₂ = c₁/(u − l)²`, `Δ^π(T) ≥ K₁ Σ_{t=1}^{T−1} 1/(K₂ + t) ≥ c Σ_{t=1}^{T−1} 1/t` where
`c = K₁/(1 + K₂)`. The sums over `t = 1, …, T − 1` are over `Finset.Ico 1 T`. The constants
depend only on the model `M`. -/
theorem regret_lower_bound_harmonic (M : Model) :
∃ K₁ : ℝ, 0 < K₁ ∧ ∃ K₂ : ℝ, 0 < K₂ ∧
∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
∀ (π : Policy M.l M.u) (T : ℕ),
K₁ / (1 + K₂) * ∑ t ∈ Finset.Ico 1 T, 1 / (t : ℝ)
≤ K₁ * ∑ t ∈ Finset.Ico 1 T, 1 / (K₂ + (t : ℝ)) ∧
K₁ * ∑ t ∈ Finset.Ico 1 T, 1 / (K₂ + (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
Let be any model, with fields . The statement asserts that there exist constants and , depending on alone, with the following property. Take:
- any measurable space (fixed but arbitrary universe) and any probability measure on it;
- any real functions on satisfying the imported predicate "Gaussian noise with parameter under ", whose definition is not part of this code;
- any policy on ;
- any .
Then both inequalities hold:
Here is the real supremum, equal to if unbounded above, of the regrets
The ingredients are:
- and ;
- , where is the price generated by under slope and shocks , with periods from ;
- ;
- the expectation is a Bochner integral, which is if not integrable.
The first inequality involves only , and , and none of . The statement does not relate to any other constant. In the sums , so no division by zero occurs. The same must work for every .
Degenerate cases: for and all sums are empty. The first inequality reads , and the second asserts only that the worst-case regret is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.