Corollary 11.14: RepeatedHE is BIC if for each time
ProvedIntroBandits.repeatedHE_bic_of_gapsbayesian-incentive-compatibilityhidden-explorationincentivized-exploration
Corollary 11.14. RepeatedHE is BIC if for each time , where is the posterior gap given the exploration data .
Formally: a prior supported on the finite with , any reward family, any bandit algorithm , initial rounds, and a horizon . If for every round of the run after the initial ones (record lengths with ) , where is the posterior gap given the exploration rounds of the first rounds and the expectation is under the law of the first rounds of RepeatedHE, then RepeatedHE is BIC (Definition 11.4) over the rounds: for every round and every two distinct arms with , under the law of the compliant run.
Preamble
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace IntroBandits
theorem repeatedHE_bic_of_gaps (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 < ε) {T : ℕ}
(hgap : ∀ n, N₀ ≤ n → n < T →
ε < heExpect P F fam A N₀ ε n (fun h ↦ max 0 (explGap P F fam h)) / 3) :
IsBIC F (repeatedHELaw P F fam A N₀ ε T) recHE := by sorry
end IntroBandits
Source
Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272 (FnT ML 12, 2019), §11.4 p. 151, Corollary 11.14 (Lemma 11.10 applied round by round with signal S_t)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.