Theorem 2.3: the discrete-time Gittins index ν(B, x, a) is nondecreasing in the discount factor a
ProvedAllocationIndices.index_mono_discountdiscount-factorgittins-indexmonotonicity
Theorem 2.3. The (discrete-time) Gittins index, , is nondecreasing in the discount factor .
Formally: for a bandit process on a countable state space with bounded reward, every state and discount factors , , the index being (2.6) computed with the respective discount factor. (The proof in the text kills a -discounted stopping time with an independent geometric clock of ratio , which requires ; the displayed inequality there has its letters swapped.)
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem index_mono_discount {S : Type*} [MeasurableSpace S] [Countable S]
[MeasurableSingletonClass S] (P : Kernel S S) [IsMarkovKernel P] {r : S → ℝ}
(hr : BoundedReward r) {a b : ℝ} (hb0 : 0 < b) (hba : b ≤ a) (ha1 : a < 1) (x : S) :
gittinsIndex P r b 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.6.5 p. 32, Theorem 2.3 with its proof (randomized stopping times with a geometric kill)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.