Theorem 3 —
ProvedWeberGittins.IndexGap.theorem3_index_gap_boundConsider bandit processes, each a Markov chain on a standard Borel state space with transition kernel . In each round a gambler plays one bandit , collects a reward with mean , and only the played bandit changes state. Rewards are nonnegative and uniformly bounded, is measurable, and the discount factor satisfies . The value of a policy from the initial state vector is
Let be the fair charge of state (the supremum over stopping times of expected discounted reward over expected discounted time) and the Gittins index.
Theorem 3. Let be a Gittins index policy (one that always plays a bandit of greatest Gittins index, ties broken arbitrarily), and let be any policy. Then
The suboptimality of an arbitrary policy is thus bounded by the expected discounted sum, along its own trajectory, of the amounts by which the index of the bandit it plays falls short of the greatest index. A policy that plays a bandit within of the greatest index in every round therefore loses at most .
Formalization Note " is the optimal (Gittins) policy" is read as: is any policy with IsGittinsIndexPolicy P r β πstar, as in the published Theorem 1. The expectation of the series is written as the series of round expectations, , the convention of the published value; under bounded rewards the two agree. The index is Weber's (weberIndex), not the fair charge (gittinsIndex); with the bound would be false by the factor . The hypothesis that is measurable is added so that the expectation is a genuine integral. The standing assumptions of Section 1 and the regularity hypotheses (measurable , standard Borel ) are binders; Weber's bandits with separate state spaces are encoded on one state space (disjoint union).
import Definitions.Def_GittinsIndex import Definitions.Def_WeberGittins_IndexGap_SwitchPolicies open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace WeberGittins.IndexGap
theorem theorem3_index_gap_bound {k : ℕ} {S : Type*} [MeasurableSpace S]
[StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r) (hrb : WeberGittins.Suboptimality.RewardsNonnegBounded r)
{β : ℝ} (hβ0 : 0 < β) (hβ1 : β < 1) (hγ : Measurable (gittinsIndex P r β))
(πstar : MarkovBanditPolicy k S) (hπstar : IsGittinsIndexPolicy P r β πstar)
(π : MarkovBanditPolicy k S) (x : Fin k → S) :
markovBanditDiscountedValue P r β πstar x - markovBanditDiscountedValue P r β π x ≤
∑' t : ℕ, β ^ t * WeberGittins.Suboptimality.roundExpectation P π x t (fun h j =>
(⨆ i : Fin k, WeberGittins.Suboptimality.weberIndex P r β (h.2 i)) - WeberGittins.Suboptimality.weberIndex P r β (h.2 j)) := by sorry
end WeberGittins.IndexGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.