Eqs. (6.9)-(6.10): the monotone policy (y) earns Wϕ(y) + R(y) from every state and g(W) is the maximum of these over the thresholds
ProvedAllocationIndices.spinning_plates_optimal_avgaverage-rewardmonotone-policiesrestless-bandits
Eqs. (6.9)–(6.10) (p. 157). As a consequence of the fact that there always exists a member of which achieves , , where is the return rate generated by the asset under monotone policy .
Formally: for the spinning plates asset on states with rates in , , below the top state and above the bottom state, and every subsidy : every monotone policy , , has average reward from every initial state, and the optimal average reward over deterministic stationary Markov policies and initial states equals .
Preamble
import Definitions.Def_AllocationIndices_Restless open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **Eqs. (6.9)–(6.10)** (p. 157). In the spinning plates model with positive interior rates
(`λ(x) > 0` below the top state, `μ(x) > 0` above the bottom state) and `λ(k) = μ(1) = 0`, the
monotone policy `(y)` earns the average reward `Wϕ(y) + R(y)` from every initial state, and the
optimal average reward under passive subsidy `W` is
`g(W) = max_{1 ≤ y ≤ k+1} [Wϕ(y) + R(y)]` (thresholds `0, …, k` here), because there is always a
monotone policy achieving `g(W)`. -/
theorem spinning_plates_optimal_avg {k : ℕ} (hk : 0 < 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)
(hlam_pos : ∀ x : Fin k, x.val + 1 < k → 0 < lam x)
(hmu_pos : ∀ x : Fin k, 0 < x.val → 0 < mu x) (W : ℝ) :
(∀ y ≤ k, ∀ x, avgReward (spinningPlates lam mu r hlam hmu) W (plateThreshold y) x =
W * plateShare lam mu y + plateReturn lam mu r y) ∧
optimalAvg (spinningPlates lam mu r hlam hmu) W = plateEnvelope lam mu r W := 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-157, the reduction to the monotone class A and Eqs. (6.9)-(6.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.