(C.5), p. 48 โ Reg_ฯ(T, v) โค ๐ผ_ฯ ฮฃ_{โ=1}^L (1 + V(S_โ))(R(S*, v) โ R(S_โ, v))
ProvedMNLBandit.WellSeparated.display_C_5Consider the MNL-Bandit problem under Assumption 4.1 with revenues , and run Algorithm 1 with any tie-breaking rule. Let be the number of epochs started within the first customers, the assortment of epoch , and . Then
Given its assortment, the length of an epoch is geometric with mean . The display rewrites the per-customer regret as a per-epoch regret, the form in which the epoch-wise bounds of Lemmas 4.3, 6.2 and Corollary C.1 apply.
Formalization Note The paper writes "". With a finite horizon the last epoch is cut at time , so it contributes at most its expected full length. Only "" holds, and this is all the proof of Theorem 3 uses. The expectation is over histories of length , a finite sum.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_WellSeparated_Setting
namespace MNLBandit.WellSeparated
open ChoiceCDLP.MNL
/-- Display (C.5), p. 48 (the epoch rewriting of the regret, as an inequality), for Algorithm 1
under Assumption 4.1 and `r_i โ [0, 1]`:
`Reg_ฯ(T, v) โค ๐ผ_ฯ โ_{โ=1}^{L} (1 + V(S_โ))(R(S*, v) โ R(S_โ, v))`, `V(S) = โ_{jโS} v_j`, where `L`
is the number of epochs started within the first `T` customers. -/
theorem display_C_5 (N : โ) (v r : Fin N โ โ) (๐ฎ : Finset (Finset (Fin N))) (h๐ฎ : ๐ฎ.Nonempty)
(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 : โ) :
MNLBandit.UCB.regret v r ๐ฎ h๐ฎ (alg1 r sel) T โค
โ h : Fin T โ Option (Fin N), histProb v (alg1 r sel) T h *
โ โ โ Finset.Icc 1 (epochsStarted r sel h),
(1 + โ j โ epochSet r sel h โ, v j) *
(MNLBandit.UCB.optRevenue v r ๐ฎ h๐ฎ - revenue v r (epochSet r sel h โ)) := by sorry
end MNLBandit.WellSeparated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.