Theorem 5.10: for a GCL(2) system the achievable region is P'(F, f), its extreme points are permutation performances, and AG(F, c) gives a cost-minimizing index policy
ProvedAllocationIndices.gcl2_index_policy_optimalachievable-regionadaptive-greedy-algorithmconservation-lawslinear-programming
Theorem 5.10. If a system satisfies GCL(2) with performance , base function and matrix , then the achievable region is the convex polytope , whose extreme points are the performances of permutation policies. Further, is achieved by a Gittins index policy determined by the indices emerging from the adaptive greedy algorithm .
Formally: for a GCL2System whose achievable region is convex (the class of policies is closed under randomization, as the book's argument on convex combinations of extreme points requires) and any cost vector : ; every extreme point of is for some permutation policy ; has an output; and for every output and every policy , .
Preamble
import Definitions.Def_AllocationIndices_Achievable open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **Theorem 5.10** (p. 130). For a system satisfying GCL(2) with performance `xᵖ`, base
function `f` and matrix `F`, whose class of policies is closed under randomization, the
achievable region is the polytope `P'(F, f)`, its extreme points are performances of permutation
policies, and for every cost vector `c` the optimal cost `C^{opt} = min_π ∑ cᵢ xᵢᵖ` is achieved
by a Gittins index policy determined by the adaptive greedy algorithm `AG(F, c)`. -/
theorem gcl2_index_policy_optimal {N : ℕ} {Pol : Type*} (D : GCL2System N Pol)
(hconv : Convex ℝ (Set.range D.perf)) (c : Fin N → ℝ) :
Set.range D.perf = achievablePolytope' D.F D.f ∧
(∀ x ∈ Set.extremePoints ℝ (achievablePolytope' D.F D.f),
∃ σ : Equiv.Perm (Fin N), x = D.perf (D.permPolicy σ)) ∧
(∃ (σ : Equiv.Perm (Fin N)) (y : Fin N → ℝ), IsAdaptiveGreedy D.F c σ y) ∧
(∀ (σ : Equiv.Perm (Fin N)) (y : Fin N → ℝ), IsAdaptiveGreedy D.F c σ y →
∀ π, linearObjective c (D.perf (D.permPolicy σ)) ≤ linearObjective c (D.perf π)) := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §5.4 p. 130, Theorem 5.10 (Bertsimas and Niño-Mora 1996)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.