Eq. (2.5): the Gittins index is the greatest prevailing charge under which continuing for one or more periods is not a loss
ProvedAllocationIndices.fair_charge_characterizationfair-chargegittins-indexoptimal-stopping
Eq. (2.5). : the index is the greatest rent one would be willing to pay per period for ownership of the rewards arising from the bandit while it is continued for one or more periods.
Formally: for a bandit process on a countable state space with bounded reward and , for every state ,
where the inner supremum is over all stopping times and is the index (2.6) of the Bandit Algorithms model. The set on the right is nonempty ( works with ) and bounded above by , so the real supremum is genuine.
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem fair_charge_characterization {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) :
gittinsIndex P r a x = sSup {lam : ℝ | 0 ≤ fairChargeProfit P r a x lam} := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §2.5 p. 25, Eq. (2.5), and the fair-charge interpretation in the proof of Theorem 2.1 (p. 27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.