Theorem 1, p. 11 — Algorithm 1 has regret at most C₁√(NT log NT) + C₂N log² NT
ProvedMNLBandit.UCB.theorem_1Performance bound for Algorithm 1. There are absolute constants and with the following property. Consider any instance of the MNL-Bandit problem:
- products with revenues ;
- MNL parameters (Assumption 4.1.1);
- a nonempty feasible family of the form (2.3), with totally unimodular and integral, closed under taking subsets (Assumption 4.1.2).
Let be Algorithm 1 run with any argmax tie-breaking rule. Then for every horizon ,
The algorithm does not know : it uses only the revenues, the feasible family and the observed choices. The bound holds without any separation between the optimal and the suboptimal assortments.
Formalization Note. The constants are quantified before every other object (number of products, horizon, parameters, revenues, family and tie-breaking rule), so they are uniform as the page says. is the natural logarithm. At the right side is , and so is the regret (with one product and one customer the first assortment is already optimal). The nonemptiness of is presupposed by the paper's .
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_UCB_Setting import Definitions.Def_MNLBandit_UCB_Algorithm1
namespace MNLBandit.UCB
open ChoiceCDLP.MNL
theorem theorem_1 :
∃ C₁ C₂ : ℝ, ∀ (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N)))
(hne : 𝒮.Nonempty) (sel : (Finset (Fin N) → ℝ) → Finset (Fin N)) (T : ℕ),
IsTU 𝒮 → DownClosed 𝒮 → IsArgmaxSel 𝒮 sel →
(∀ i, 0 ≤ v i) → (∀ i, v i ≤ 1) → (∀ i, r i ∈ Set.Icc (0 : ℝ) 1) →
regret v r 𝒮 hne (alg1 r sel) T ≤
C₁ * Real.sqrt (N * T * Real.log (N * T)) + C₂ * N * Real.log (N * T) ^ 2 := by sorry
end MNLBandit.UCB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.