Lemma 2.4: with ν(B₁) > ν(B₂) and τ attaining ν(B₁), continuing B₁ for τ then B₂ for σ beats the reverse order
ProvedAllocationIndices.interchange_portionsgittins-indexinterchange-argument
Lemma 2.4. If bandit processes and have indices and with , and is a stopping time for such that , while is an arbitrary stopping time for , then the expected reward from selecting for time , and then for time , is greater than from reversing the order of selection.
Formally: bandit processes on countable state spaces with bounded rewards, the same discount factor , initial states with ; a positive stopping time of with ; any positive stopping time of . Then
the two sides being the expected rewards of the two orders, since the processes are independent.
Preamble
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
theorem interchange_portions {S₁ S₂ : Type*} [MeasurableSpace S₁] [Countable S₁]
[MeasurableSingletonClass S₁] [MeasurableSpace S₂] [Countable S₂] [MeasurableSingletonClass S₂]
(P₁ : Kernel S₁ S₁) [IsMarkovKernel P₁] {r₁ : S₁ → ℝ} (hr₁ : BoundedReward r₁)
(P₂ : Kernel S₂ S₂) [IsMarkovKernel P₂] {r₂ : S₂ → ℝ} (hr₂ : BoundedReward r₂)
{a : ℝ} (ha0 : 0 < a) (ha1 : a < 1) {x₁ : S₁} {x₂ : S₂}
(hν : gittinsIndex P₂ r₂ a x₂ < gittinsIndex P₁ r₁ a x₁)
{τ : (ℕ → S₁) → ℕ∞} (hτ : IsPositiveStoppingTime τ)
(hτν : stoppedRatio P₁ r₁ a τ x₁ = gittinsIndex P₁ r₁ a x₁)
{σ : (ℕ → S₂) → ℕ∞} (hσ : IsPositiveStoppingTime σ) :
interchangeValue P₂ r₂ P₁ r₁ a σ τ x₂ x₁ < interchangeValue P₁ r₁ P₂ r₂ a τ σ x₁ x₂ := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §2.7 p. 34, Lemma 2.4 with its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.