Lemma 11.10: HiddenExploration is BIC for any target function as long as
ProvedIntroBandits.hidden_exploration_bicLemma 11.10. Algorithm 11.1 is BIC, for any target function , as long as , where is the posterior gap.
Formally: a finite signal space and a probability law of whose -marginal is supported on the finite with (the standing assumption of the chapter's Preliminaries); any randomized target, a distribution over the two arms for each signal; . Then the recommendation rule of HiddenExploration, , satisfies the single-round BIC property (11.5): for both orderings of the two arms, implies .
The bound is the printed one (non-strict); the book's proof ends with the strict because it proves the strict inequality (11.6), and at equality the same computation gives , which is what (11.5) asks.
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace IntroBandits
theorem hidden_exploration_bic {Ω : Type} [Fintype Ω] [DecidableEq Ω] [MeasurableSpace Ω]
[MeasurableSingletonClass Ω] (Q : Measure ((Fin 2 → ℝ) × Ω)) [IsProbabilityMeasure Q]
(F : Finset (Fin 2 → ℝ)) (hF : Q ((↑F)ᶜ ×ˢ Set.univ) = 0)
(hunit : ∀ μ ∈ F, ∀ a, μ a ∈ Set.Icc (0 : ℝ) 1)
(hprior : priorMean Q.fst F 1 ≤ priorMean Q.fst F 0)
(trg : Ω → Fin 2 → ℝ) (htrg : ∀ S, trg S ∈ stdSimplex ℝ (Fin 2))
{ε : ℝ} (hε : 0 < ε) (hε3 : ε ≤ sigGapPlus Q F / 3) :
IsSingleRoundBIC Q F (hiddenExploration ε trg Q F) := by sorry
end IntroBandits
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.