Proposition 2.7: if r(x(t)) ≤ r(x) for all t ≥ 1 almost surely, the supremum in (2.6) is attained at τ = 1 and ν(x) = r(x)
ProvedAllocationIndices.index_eq_reward_of_reward_nonincreasinggittins-indexmonotone-indicesmyopic-policy
Proposition 2.7. 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 : and .
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem index_eq_reward_of_reward_nonincreasing {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 → r (ω t) ≤ r x} = 1) :
stoppedRatio P r a (fun _ ↦ 1) x = gittinsIndex P r a x ∧ gittinsIndex P r a x = r 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.7 with the preceding computation
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.