Lemma 4, p. 20 — quantization costs at most (2/M + 1/K)T regret
ProvedFirstPriceLearning.Stochastic.lemma_4first-price-auctionsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantizationregret
Let , let be any CDF on , let be an arbitrary value sequence and its clipping to . Let be bids on the grid : the bids of a policy of the quantized problem, which the induced policy plays in the original problem. Then
where is the regret (3), computed with the maximum over all bids in and the true values.
This is the step that transfers a regret bound for the finite contextual bandit to the continuous auction.
Formalization Note. The statement is pathwise: it holds for every bid sequence on the grid, so it applies to every realization of a randomized .
Preamble
import Mathlib import Definitions.Def_FirstPriceLearning_Stochastic_Auction
Formal statement
namespace FirstPriceLearning.Stochastic
open MeasureTheory
/-- Lemma 4 (p. 20): quantization loses at most `(2/M + 1/K) T`. For any value sequence
`v ∈ [0,1]^T`, any HOB law `G` on `[0, 1]` and any bids `b_t` on the grid `𝒜 = {1/K, …, 1}` (the
bids of a policy `π^Q` of the quantized problem, which the induced policy `π` also plays), the
regret (3) is at most the quantized regret `R̃_T(π^Q, v)`, computed against the clipped values
`ṽ_t = min {x ∈ 𝒞 : x ≥ v_t}`, `𝒞 = {1/M, …, 1}`, plus `(2/M + 1/K) T`. -/
theorem lemma_4 (T M K : ℕ) (hM : 1 ≤ M) (hK : 1 ≤ K) (μG : Measure ℝ) [IsProbabilityMeasure μG]
(hG : μG (Set.Icc (0 : ℝ) 1)ᶜ = 0) (v : Fin T → ℝ) (hv : ∀ t, v t ∈ Set.Icc (0 : ℝ) 1)
(b : Fin T → ℝ) (hb : ∀ t, b t ∈ gridA K) :
regret μG v b ≤
gridRegret μG (gridA K) (fun t => clipValue M (v t)) b + (2 / M + 1 / K) * T := by sorry
end FirstPriceLearning.Stochastic
Source
Han, Zhou, Weissman, Optimal No-regret Learning in Repeated First-price Auctions, arXiv:2003.09795v7, p. 20, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.