Theorem 5.5: for a GCL(1) system the achievable region is the polytope P(A, b), its extreme points are permutation performances, and AG(A, r) gives an optimal index policy
ProvedAllocationIndices.achievable_region_theoremTheorem 5.5. If a system satisfies GCL(1) 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 adaptive greedy algorithm .
Formally: for a GCL1System whose achievable region is convex (the class of policies is closed under randomization, which the book's argument on convex combinations of extreme points uses and without which fails already for two job types) and any reward vector : ; every extreme point of is for some permutation policy ; has an output; and for every output of and every policy , . The last clause is the index theorem in this generality: the permutation policy listing the job types in the order found by , the Gittins index policy, is optimal for the linear objective.
import Definitions.Def_AllocationIndices_Achievable open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
namespace AllocationIndices
/-- **Theorem 5.5** (p. 127). For a system satisfying GCL(1) with performance `xᵖ`, base function
`b` and matrix `A`, whose class of policies is closed under randomization (the achievable region
is convex, as for past-measurable policies that may randomize; this is what the argument of
§5.2 on convex combinations of extreme points uses), the achievable region is the polytope
`P(A, b)`, its extreme points are performances of permutation policies, and for every reward
vector `r` the optimal return `R^{opt} = max_π ∑ rᵢ xᵢᵖ` is achieved by a Gittins index policy
determined by the adaptive greedy algorithm `AG(A, r)`: an output exists, and every output's
permutation policy attains the maximum. -/
theorem achievable_region_theorem {N : ℕ} {Pol : Type*} (D : GCL1System N Pol)
(hconv : Convex ℝ (Set.range D.perf)) (r : Fin N → ℝ) :
Set.range D.perf = achievablePolytope D.A D.b ∧
(∀ x ∈ Set.extremePoints ℝ (achievablePolytope D.A D.b),
∃ σ : Equiv.Perm (Fin N), x = D.perf (D.permPolicy σ)) ∧
(∃ (σ : Equiv.Perm (Fin N)) (y : Fin N → ℝ), IsAdaptiveGreedy D.A r σ y) ∧
(∀ (σ : Equiv.Perm (Fin N)) (y : Fin N → ℝ), IsAdaptiveGreedy D.A r σ y →
∀ π, linearObjective r (D.perf π) ≤ linearObjective r (D.perf (D.permPolicy σ))) := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.