Lemma E.2, p. 57 — for t ≤ Nα/(60ϵ²) at least N/3 hiding places j have 𝒫_j(a_t = j) ≤ 1/2
ProvedMNLBandit.LowerBound.lemma_E_2Consider coins (arms): when the biased coin is hidden at position , coin shows with probability and every other coin with probability . A guessing algorithm is an online algorithm on these coins: at each time it chooses (possibly at random) a coin given the coins it chose before and their outputs, and sees the output of . Write for the law of its view when the biased coin is at position .
Let , , with , and let be a time with
Then there is a set with such that
In words: for a short horizon, at least a third of the possible hiding places of the biased coin are not guessed with probability more than . This is the key step of the MAB lower bound (Lemma 5.1).
Formalization Note The time is written , where is the number of rounds observed before is chosen; the hypothesis is . The added hypotheses , and are those of the instance with a small . The printed proof's form of Pinsker's inequality, , is smaller than the true ; with the true inequality and , which holds when , the printed suffices. The algorithm is randomized (behavioural), which includes the deterministic ones.
import Mathlib import Definitions.Def_MNLBandit_LowerBound_BernoulliMAB
namespace MNLBandit.LowerBound
theorem lemma_E_2 (N : ℕ) (hN : 12 ≤ N) (α ϵ : ℝ) (hα : 0 < α) (hϵ : 0 < ϵ)
(hϵ4 : ϵ ≤ 1 / 4) (hαϵ : 2 * α + ϵ ≤ 1)
(A : MABAlg N) (hA : IsMABAlg A) (s : ℕ)
(hs : (s : ℝ) + 1 ≤ (N : ℝ) * α / (60 * ϵ ^ 2)) :
∃ J : Finset (Fin N), (N : ℝ) / 3 ≤ J.card ∧
∀ j ∈ J, armProb A (imabMeans α ϵ j) s j ≤ 1 / 2 := by sorry
end MNLBandit.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.