p. 123: the indices computed by the adaptive greedy algorithm AG(A, r) for a SFABP are nondecreasing along its order and equal the Gittins indices
ProvedAllocationIndices.adaptive_greedy_indices_eq_gittinsachievable-regionadaptive-greedy-algorithmgittins-index
p. 123. The algorithm calculates s, with . These are in fact the Gittins indices.
Formally: for a bandit process on with kernel , rewards and discount factor , let be the coefficients (5.3). For every output of the adaptive greedy algorithm (any tie-breaking), the indices satisfy , and , the Gittins index of state , for every state . (That is immediate from and is not restated.)
Preamble
import Definitions.Def_AllocationIndices_Achievable open MeasureTheory ProbabilityTheory BanditAlgorithm Finset
Formal statement
namespace AllocationIndices
/-- **The adaptive greedy indices are the Gittins indices** (p. 123, Eqs. (5.13)–(5.14)). For a
bandit process on the finite state space `E = Fin N` with transition kernel `P`, rewards `r` and
discount factor `a ∈ (0, 1)`, let `A` be the matrix (5.3) of expected discounted return times.
Every output `(σ, y)` of the adaptive greedy algorithm `AG(A, r)` lists the states in
nondecreasing order of its indices, `ν_{i_1} ≤ ν_{i_2} ≤ ⋯ ≤ ν_{i_N}`, and these indices are
the Gittins indices: `ν_i = ν(B, i)` for every state `i`. -/
theorem adaptive_greedy_indices_eq_gittins {N : ℕ} (P : Kernel (Fin N) (Fin N))
[IsMarkovKernel P] (r : Fin N → ℝ) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1)
(σ : Equiv.Perm (Fin N)) (y : Fin N → ℝ) (h : IsAdaptiveGreedy (conservationCoeff P a) r σ y) :
(∀ j k : Fin N, j ≤ k → greedyIndex σ y (σ j) ≤ greedyIndex σ y (σ k)) ∧
∀ i, greedyIndex σ y i = gittinsIndex P r a i := 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. 122-123, the adaptive greedy algorithm AG(A, r) and the identification (5.13)-(5.14) of its output with the Gittins indices
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.