Proposition 2.8: if ν(x(t)) > ν(x) for all t ≥ 1 almost surely, the supremum in (2.6) is attained at τ = ∞ and ν(x) > r(x)
ProvedAllocationIndices.index_attained_at_infinity_of_index_increasinggittins-indexmonotone-indices
Proposition 2.8. If , the supremum in (2.6) is attained when , and .
Formally: for a bandit process on a countable state space with bounded reward and , and a state such that, under , almost surely for every : the never-stopping time attains the supremum, , and . This includes the case when is almost surely increasing.
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem index_attained_at_infinity_of_index_increasing {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) (x : S)
(h : markovChainMeasure P x
{ω | ∀ t : ℕ, 1 ≤ t → gittinsIndex P r a x < gittinsIndex P r a (ω t)} = 1) :
stoppedRatio P r a (fun _ ↦ ⊤) x = gittinsIndex P r a x ∧ r x < gittinsIndex P r a x := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §2.11.1 p. 45, Proposition 2.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.