Theorem 11.19: absent Property (11.12), any BIC algorithm (ties to arm 1) never plays arm 2
ProvedIntroBandits.bic_never_explores_without_propertybayesian-incentive-compatibilityimpossibilityincentivized-exploration
Theorem 11.19. Suppose ties in Definition 11.4 are always resolved in favor of arm 1 (i.e., imply ). Absent (11.12), any BIC algorithm never plays arm 2.
Formally: a prior supported on the finite , any reward family; suppose Property (11.12) fails, i.e. for every and every tuple of samples of arm 1, (so for every ). Let be a bandit policy over rounds that is BIC with the tie convention: BIC, and whenever , (arm 2 is recommended only when strictly better). Then for every round , under the joint law of the compliant run. "Never plays" is "with probability zero", which is what the induction of the proof establishes.
Preamble
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace IntroBandits
theorem bic_never_explores_without_property (P : Measure (Fin 2 → ℝ)) [IsProbabilityMeasure P]
(F : Finset (Fin 2 → ℝ)) (hF : P (↑F)ᶜ = 0)
(hunit : ∀ μ ∈ F, ∀ a, μ a ∈ Set.Icc (0 : ℝ) 1) (fam : RewardFamily)
(hno : ¬ PriorAllowsExploration P F fam) {T : ℕ} {π : BanditPolicy 2}
(hπ : IsStrictlyBIC F (jointMeasure P F fam π T) (fun h t ↦ (h t).1)) :
∀ t : Fin T, jointMeasure P F fam π T (Set.univ ×ˢ {h | (h t).1 = 1}) = 0 := by sorry
end IntroBandits
Source
Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272 (FnT ML 12, 2019), §11.5 p. 153, Theorem 11.19 with its proof by induction
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.