Theorem 6.4: if ϕ is strictly decreasing the spinning plates asset is indexable, and if W*(x) is strictly decreasing its Whittle index is W*(x)
ProvedAllocationIndices.spinning_plates_indexableindexabilityrestless-banditsspinning-plateswhittle-index
Theorem 6.4 (p. 157). (i) If is strictly decreasing over , the asset is indexable. (ii) If additionally (6.11) is strictly decreasing over , then the asset has Whittle index , .
Formally, for the spinning plates asset on states (rates in with , reward increasing and nonnegative): if is strictly decreasing over the thresholds (with , ), then implies , where is the set of states in which some policy that is average-optimal from every initial state under subsidy takes the passive action; and if moreover is strictly decreasing over the states, for every state .
Preamble
import Definitions.Def_AllocationIndices_Restless open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **Theorem 6.4** (p. 157). For the spinning plates asset (rates `λ, μ` uniformized to
`[0, 1]` with `λ(k) = μ(1) = 0`, reward `r` increasing and nonnegative):
(i) if `ϕ(y) = λ(y−1)/(λ(y−1) + μ(y))` is strictly decreasing over the thresholds
`1 ≤ y ≤ k + 1` (here `0 ≤ y ≤ k`), the asset is indexable;
(ii) if additionally `W*(x) = (R(x+1) − R(x))/(ϕ(x) − ϕ(x+1))` is strictly decreasing over the
states, the asset has Whittle index `W(x) = W*(x)`. -/
theorem spinning_plates_indexable {k : ℕ} (lam mu r : Fin k → ℝ)
(hlam : ∀ x, lam x ∈ Set.Icc (0 : ℝ) 1) (hmu : ∀ x, mu x ∈ Set.Icc (0 : ℝ) 1)
(hlam_top : ∀ x : Fin k, x.val + 1 = k → lam x = 0)
(hmu_bot : ∀ x : Fin k, x.val = 0 → mu x = 0)
(hr : Monotone r) (hr0 : ∀ x, 0 ≤ r x)
(hphi : StrictAntiOn (plateShare lam mu) (Set.Iic k)) :
Indexable (spinningPlates lam mu r hlam hmu) ∧
(StrictAnti (plateIndex lam mu r) →
∀ x, whittleIndex (spinningPlates lam mu r hlam hmu) x = plateIndex lam mu 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. 156-158, Theorem 6.4 with its proof (the upper envelope (6.10) and its hinge points)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.