Theorem 3 — for (f₁ + ϵ)n ≤ k ≤ (1 − fₘ − ϵ)n, every non-adaptive policy has regret at least M√n
ProvedMultiSecretary.NonAdaptive.sqrt_regret_lower_boundLet and . There is a constant such that for all masses summing to one with and all with ,
When the budget is a fraction of bounded away from and from , even the best non-adaptive policy loses order against the offline optimum, while adaptive policies (the Budget-Ratio policy of the same paper) achieve regret bounded uniformly in and .
Formalization Note Lean index is the paper's index , so a 0 is the largest value , f 0 is and f (Fin.rev 0) is . The constant is chosen after , , and before , , , and it is required to be strictly positive (with the claim would reduce to ). The statement holds for all in the range, as printed, with no threshold on . The range is empty unless , so the statement has content only for .
import Mathlib import Definitions.Def_MultiSecretary_NonAdaptive_Model import Definitions.Def_MultiSecretary_NonAdaptive_Policy
namespace MultiSecretary.NonAdaptive
open Finset
/-- Theorem 3 (p. 25): for `ϵ = ½ min f_j` and `(f_1 + ϵ) n ≤ k ≤ (1 - f_m - ϵ) n` there is a constant
`M ≡ M(ϵ, m, a_1, …, a_m) > 0` with `M√n ≤ V*_off(n, k) - V*_na(n, k)`. -/
theorem sqrt_regret_lower_bound (ε : ℝ) (hε : 0 < ε) (m : ℕ) [NeZero m] (a : Fin m → ℝ)
(ha : IsValues a) :
∃ M : ℝ, 0 < M ∧ ∀ f : Fin m → ℝ, IsMasses f → eps f = ε → ∀ n k : ℕ,
(f 0 + ε) * n ≤ k → (k : ℝ) ≤ (1 - f (Fin.rev 0) - ε) * n →
M * Real.sqrt n ≤ Voff a f n k - VstarNa a f n k := by sorry
end MultiSecretary.NonAdaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.