Lemma 5.1: a SFABP satisfies the conservation laws (5.5)-(5.6), with equality for policies giving priority to states outside S
ProvedAllocationIndices.sfabp_conservation_lawsachievable-regionconservation-lawsmarkov-bandits
Lemma 5.1. There exist positive (), having the interpretation (5.3), such that for any scheduling policy , for all (5.5), (5.6), and such that equality holds in (5.5) if is a policy that gives priority to bandits whose states are not in over any bandits whose states are in .
Formally: for identical bandit processes on with kernel , discount factor , initial state-vector , every policy of the Bandit Algorithms model and every : for ; ; (which is (5.6), as and ); and if gives priority to bandits whose states are not in , then . Here , the minimal cost identified on p. 120 (the printed formula has a sum in place of the product).
Preamble
import Definitions.Def_AllocationIndices_Achievable open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **Lemma 5.1** (p. 120). For a SFABP of `n` identical bandits on the finite state space
`E = Fin N` with discount factor `a ∈ (0, 1)`, started from the state-vector `k`, the
coefficients `Aᵢ^S` of (5.3) are positive for `i ∈ S`, and for every scheduling policy `π`,
`∑_{i∈S} Aᵢ^S xᵢᵖ ≥ b(S)` for every `S ⊆ E` (5.5), `∑_{i∈E} Aᵢ^E xᵢᵖ = b(E) = 1/(1−a)` (5.6),
and equality holds in (5.5) whenever `π` gives priority to bandits whose states are not in `S`
over any bandits whose states are in `S`. -/
theorem sfabp_conservation_laws {N n : ℕ} (P : Kernel (Fin N) (Fin N)) [IsMarkovKernel P]
{a : ℝ} (ha0 : 0 < a) (ha1 : a < 1) (k : Fin n → Fin N) (π : MarkovBanditPolicy n (Fin N))
(S : Finset (Fin N)) :
(∀ i ∈ S, 0 < conservationCoeff P a S i) ∧
conservationBase P a k S ≤ ∑ i ∈ S, conservationCoeff P a S i * performance P π a k i ∧
∑ i, performance P π a k i = (1 - a)⁻¹ ∧
(GivesPriority S π →
∑ i ∈ S, conservationCoeff P a S i * performance P π a k i = conservationBase P a k S) := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §5.3 pp. 120-121, Lemma 5.1 with the argument preceding it ((5.3), the cost problem and its value)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.