Theorem 11.15: RepeatedHE with and initial samples of arm 1 is BIC as long as ,
ProvedIntroBandits.repeatedHE_bicTheorem 11.15. RepeatedHE with exploration probability and initial samples of arm 1 is BIC as long as , where .
Formally: a prior (a probability measure on mean vectors) supported on the finite with ; any reward family with finitely many reward values; any bandit algorithm ; ; with
the posterior gap given the initial samples of arm 1. Then, for every horizon , RepeatedHE (Algorithm 11.2, run with , , ) is Bayesian incentive-compatible in the sense of Definition 11.4: for every round and every two distinct arms such that under the law of the compliant run,
Reading. The event of (11.1) is the sure event of the compliant law. The initial rounds recommend arm 1, so for them the condition reads ; every later round is a HiddenExploration with signal (Lemma 11.10), and is nondecreasing in because determines . Nothing is assumed about ; when no qualifies (Remark 11.16).
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace IntroBandits
theorem repeatedHE_bic (P : Measure (Fin 2 → ℝ)) [IsProbabilityMeasure P]
(F : Finset (Fin 2 → ℝ)) (hF : P (↑F)ᶜ = 0)
(hunit : ∀ μ ∈ F, ∀ a, μ a ∈ Set.Icc (0 : ℝ) 1) (fam : RewardFamily)
(hprior : priorMean P F 1 ≤ priorMean P F 0) (A : BanditPolicy 2) (N₀ : ℕ) {ε : ℝ}
(hε : 0 < ε) (hε3 : ε < initialGapPlus P F fam N₀ / 3) (T : ℕ) :
IsBIC F (repeatedHELaw P F fam A N₀ ε T) recHE := by sorry
end IntroBandits
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.