Proposition 2.6: if ν(x(1)) > ν(x) almost surely, the supremum in (2.6) is attained at some τ > 1 and ν(x) > r(x)
ProvedAllocationIndices.index_gt_reward_of_index_increasing_oncegittins-indexmonotone-indices
Proposition 2.6. 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 : there is a stopping time with everywhere and , and .
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem index_gt_reward_of_index_increasing_once {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 {ω | gittinsIndex P r a x < gittinsIndex P r a (ω 1)} = 1) :
(∃ τ : (ℕ → S) → ℕ∞, IsPositiveStoppingTime τ ∧ (∀ ω, 2 ≤ τ ω) ∧
stoppedRatio P r a τ 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.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.