Theorem 4.18: an ε-index policy for a SFABP loses at most εγ⁻¹(1 − e⁻ᵞ)⁻¹ in the book's index units, i.e. ε/(1 − a)² for the discrete-time index
OpenAllocationIndices.eps_index_policy_near_optimalTheorem 4.18. If is an -index policy for an SFABP with the discount parameter , then .
Formally: for a SFABP in the Bandit Algorithms model (a common countable state space, bounded reward, discount factor ), , and a policy that at every decision time almost surely continues a bandit whose Gittins index is within of the maximal index among the current states, for every initial state-vector ,
where is the discounted value of from . At this is the index theorem.
The units of . The book's -bounds of §4.10 are in the continuous-time units of the index, reward per unit time with . Corollary 4.16's bound shows it. For a Markov family with decision times , that index is times the discrete-time index (2.6), whose denominator is . An -index policy for the discrete index is therefore an -index policy in the book's units, and the book's bound becomes . Reading the book's constant with the discrete index, i.e. , gives a false statement for . Two one-state bandits paying and show it: the -index policy that always plays the second loses , which at is . Exact value iteration on 120 random families (up to three bandits with up to three states each) found the worst -index policy within of the bound and never above it, while the other reading was exceeded in 5 families.
import Definitions.Def_AllocationIndices_Superprocess open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace AllocationIndices
theorem eps_index_policy_near_optimal {T : Type*} [MeasurableSpace T] [Countable T]
[MeasurableSingletonClass T] (P : Kernel T T) [IsMarkovKernel P] {r : T → ℝ}
(hr : BoundedReward r) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1) {ε : ℝ} (hε : 0 ≤ ε) {k : ℕ}
{π : MarkovBanditPolicy k T} (hπ : IsEpsIndexPolicy P r a ε π) (x : Fin k → T) :
(⨆ π' : MarkovBanditPolicy k T, markovBanditDiscountedValue P r a π' x) -
ε / (1 - a) ^ 2 ≤
markovBanditDiscountedValue P r a π x := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.