Theorem 11.7: with probability at least , GREEDY never chooses arm 2
ProvedIntroBandits.greedy_never_exploresbayesian-greedyincentivized-explorationmartingale
Theorem 11.7. With probability at least , GREEDY never chooses arm 2.
Formally: for every prior (a probability measure on mean vectors, supported on the finite set , correlated or not), every reward family, every bandit policy that is GREEDY (11.2) and every horizon , under the joint law of of the run,
where is the prior mean. The probability is written as , so the statement is trivial when , as the book's is.
Preamble
import Definitions.Def_IntroBandits_Agents open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace IntroBandits
theorem greedy_never_explores (P : Measure (Fin 2 → ℝ)) [IsProbabilityMeasure P]
(F : Finset (Fin 2 → ℝ)) (hF : P (↑F)ᶜ = 0)
(hunit : ∀ μ ∈ F, ∀ a, μ a ∈ Set.Icc (0 : ℝ) 1) (fam : RewardFamily)
{π : BanditPolicy 2} (hπ : IsGreedy P F fam π) (T : ℕ) :
ENNReal.ofReal (priorMean P F 0 - priorMean P F 1) ≤
jointMeasure P F fam π T (Set.univ ×ˢ {h | ∀ t, (h t).1 = 0}) := by sorry
end IntroBandits
Source
Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272 (FnT ML 12, 2019), §11.2 p. 148, Theorem 11.7, with its proof by optional stopping
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.