Lemma 2.2: the supremum in (2.6) is attained by the stopping rule with any stopping set Σ₀ between {ν(x) < ν(ξ)} and {ν(x) ≤ ν(ξ)}
ProvedAllocationIndices.optimal_stopping_setgittins-indexoptimal-stoppingstopping-set
Lemma 2.2. The supremum in (2.6) is attained by a stopping time . For , this stopping time has a stopping set, say , which may be chosen to be any set such that
Formally: for a bandit process on a countable state space with bounded reward and , every state and every set of states with the two inclusions above, the stopping rule "stop at the first decision time at which " is a positive stopping time , and . Taking gives the attainment claim. In a countable state space every set is measurable, so no measurability condition on is needed.
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem optimal_stopping_set {S : Type*} [MeasurableSpace S] [Countable S]
[MeasurableSingletonClass S] (P : Kernel S S) [IsMarkovKernel P] {r : S → ℝ}
(hr : BoundedReward r) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1) (ξ : S) (stopSet : Set S)
(h₁ : {x | gittinsIndex P r a x < gittinsIndex P r a ξ} ⊆ stopSet)
(h₂ : stopSet ⊆ {x | gittinsIndex P r a x ≤ gittinsIndex P r a ξ}) :
IsPositiveStoppingTime (hittingTime stopSet) ∧
stoppedRatio P r a (hittingTime stopSet) ξ = gittinsIndex P r a ξ := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §2.6.3 p. 30, Lemma 2.2, with its proof on p. 31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.