Theorem 6.5: if ψ is strictly increasing the vigour bandit is indexable, and if W**(x) is strictly increasing its Whittle index is W**(x)
ProvedAllocationIndices.vigour_bandit_indexableindexabilityrestless-banditswhittle-index
Theorem 6.5 (p. 159). (i) If is increasing, the bandit is indexable. (ii) If additionally is increasing over , then the bandit has Whittle index , .
Formally, for the vigour bandit (active: down at rate earning ; passive: up at rate earning nothing; rates in , ; increasing and nonnegative): if is strictly increasing over the thresholds (with , ), the bandit is indexable; and if moreover is strictly increasing over the states, for every state . "Increasing" is read as strictly increasing, as in Theorem 6.4.
Preamble
import Definitions.Def_AllocationIndices_Restless open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **Theorem 6.5** (p. 159). For the vigour bandit (active: down at rate `ν(x)` earning `r(x)`;
passive: up at rate `ρ(x)` earning nothing; `ν(1) = ρ(k) = 0`; `r` increasing and nonnegative):
(i) if `ψ(y) = ν(y)/(ν(y) + ρ(y−1))` is (strictly) increasing over the thresholds, the bandit is
indexable; (ii) if additionally `W**(x) = (r(x)(1−ψ(x)) − r(x+1)(1−ψ(x+1)))/(ψ(x+1) − ψ(x))` is
(strictly) increasing over the states, the bandit has Whittle index `W(x) = W**(x)`. -/
theorem vigour_bandit_indexable {k : ℕ} (nu rho r : Fin k → ℝ)
(hnu : ∀ x, nu x ∈ Set.Icc (0 : ℝ) 1) (hrho : ∀ x, rho x ∈ Set.Icc (0 : ℝ) 1)
(hnu_bot : ∀ x : Fin k, x.val = 0 → nu x = 0)
(hrho_top : ∀ x : Fin k, x.val + 1 = k → rho x = 0)
(hr : Monotone r) (hr0 : ∀ x, 0 ≤ r x)
(hpsi : StrictMonoOn (vigourShare nu rho) (Set.Iic k)) :
Indexable (vigourBandit nu rho r hnu hrho) ∧
(StrictMono (vigourIndex nu rho r) →
∀ x, whittleIndex (vigourBandit nu rho r hnu hrho) x = vigourIndex nu rho r x) := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §6.5 pp. 158-159, Theorem 6.5 (the bandit of Example 6.1; proof 'similar to the above', i.e. to Theorem 6.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.