Claim 11.12: if the single-round BIC property holds when arm 2 is recommended, it holds when arm 1 is
ProvedIntroBandits.bic_arm_two_sufficesbayesian-incentive-compatibilityincentivized-exploration
Claim 11.12. Assume (11.5) holds for arm . Then it also holds for .
Formally, for any recommendation rule that depends on the signal only: finite, a probability law of with -marginal supported on the finite , , a distribution over the two arms for each . If implies , then the rule is single-round BIC: also implies . The proof is the identity and .
Preamble
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace IntroBandits
theorem bic_arm_two_suffices {Ω : Type} [Fintype Ω] [DecidableEq Ω] [MeasurableSpace Ω]
[MeasurableSingletonClass Ω] (Q : Measure ((Fin 2 → ℝ) × Ω)) [IsProbabilityMeasure Q]
(F : Finset (Fin 2 → ℝ)) (hF : Q ((↑F)ᶜ ×ˢ Set.univ) = 0)
(hprior : priorMean Q.fst F 1 ≤ priorMean Q.fst F 0)
(rule : Ω → Fin 2 → ℝ) (hrule : ∀ S, rule S ∈ stdSimplex ℝ (Fin 2))
(h2 : 0 < ∑ S, (sigProb Q S).toReal * rule S 1 →
0 ≤ ∑ μ ∈ F, ∑ S, (Q {(μ, S)}).toReal * (μ 1 - μ 0) * rule S 1) :
IsSingleRoundBIC Q F rule := by sorry
end IntroBandits
Source
Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272 (FnT ML 12, 2019), §11.3 p. 149, Claim 11.12 with its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.