Lemma 4.3, p. 14 — (1 + Σ_{j∈S_ℓ} v_j)(R̃_ℓ(S_ℓ) − R(S_ℓ, v)) ≤ Σᵢ [C₁√(vᵢ log(√Nℓ+1)/Tᵢ(ℓ)) + C₂ log(√Nℓ+1)/Tᵢ(ℓ)] w.p. ≥ 1 − 13/ℓ
ProvedMNLBandit.WellSeparated.lemma_4_3Consider the MNL-Bandit problem under Assumption 4.1 (, a feasible family of the form (2.3) closed under subsets), with revenues , and run Algorithm 1 with any tie-breaking rule. After epoch , the algorithm computes the upper confidence bounds and offers in the next epoch
Let and . For every epoch , with probability at least ,
This is the per-epoch convergence rate of the optimistic revenue estimate to the true revenue of the offered assortment. Lemma 6.1 starts from it.
Formalization Note Three readings are disclosed:
- The printed right-hand side has a free index ; its proof ((A.11)–(A.12), p. 36) gives the sum over , which is stated.
- The printed statement writes together with and . Algorithm 1 builds from the bounds of epoch . The statement uses the consistent reading: the estimate built at the end of epoch , which selects .
- The event is restricted to for every , where the right-hand side is defined.
The probability is that of epoch being completed within the first customers with the inequality failing, for every horizon . The constants are the values from the proof of Lemma 4.1 (p. 35). The same statement appears in the companion mission on Theorem 1.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_WellSeparated_Setting
namespace MNLBandit.WellSeparated
open ChoiceCDLP.MNL
/-- Lemma 4.3, p. 14, for Algorithm 1 under Assumption 4.1 and `r_i ∈ [0, 1]`: with `S = S_{ℓ+1}`
the assortment chosen from the UCBs computed at the end of epoch `ℓ ≥ 1`,
`(1 + ∑_{j∈S} v_j)(R̃_{ℓ+1}(S) − R(S, v)) ≤ ∑_{i∈S} [C₁ √(v_i log(√Nℓ+1)/T_i(ℓ)) + C₂ log(√Nℓ+1)/T_i(ℓ)]`
fails, on the event that epoch `ℓ` is completed within `T` customers and every `i ∈ S` has
`T_i(ℓ) ≥ 1`, with probability at most `13/ℓ`, for every `T`. -/
theorem lemma_4_3 (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N)))
(sel : (Finset (Fin N) → ℝ) → Finset (Fin N))
(hTU : MNLBandit.UCB.IsTU 𝒮) (hdown : MNLBandit.UCB.DownClosed 𝒮) (hv : ∀ i, 0 ≤ v i ∧ v i ≤ 1)
(hr : ∀ i, r i ∈ Set.Icc (0 : ℝ) 1) (hsel : MNLBandit.UCB.IsArgmaxSel 𝒮 sel)
(T ℓ : ℕ) (hℓ : 1 ≤ ℓ) :
probT v (alg1 r sel) T
(fun h => ℓ ≤ epochsDone r sel h ∧
(∀ i ∈ epochSet r sel h (ℓ + 1), 1 ≤ Tcount r sel h i ℓ) ∧
∑ i ∈ epochSet r sel h (ℓ + 1),
(C₁ * Real.sqrt (v i * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
+ C₂ * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
< (1 + ∑ j ∈ epochSet r sel h (ℓ + 1), v j) *
(mnlObjective (fun j => vUCB r sel h j ℓ) r 1 (epochSet r sel h (ℓ + 1))
- revenue v r (epochSet r sel h (ℓ + 1))))
≤ 13 / (ℓ : ℝ) := by sorry
end MNLBandit.WellSeparated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.