Proof of Theorem 3, p. 1029 — : switching to Gittins after time never lowers the value
ProvedWeberGittins.IndexGap.switch_to_gittins_after_t_optimalConsider the discounted -armed Markov bandit with state space (a standard Borel space), transition kernel , measurable mean reward that is nonnegative and uniformly bounded, and discount factor . For a policy and initial state vector write
for its expected total-discounted reward, as in (1).
Let be any policy, , and let be a policy that is identical to through time (the same selection rule in every round ) and is a Gittins index policy in every round (it plays, almost surely, an arm of greatest current fair charge, ties broken arbitrarily). Then
Weber uses this with and : "since and are identical through time and is optimal thereafter, ". It is the step that lets the bounds (8) for consecutive telescope into Theorem 3. For replaced by the start of play it is the optimality of the Gittins index policy (Theorem 1 of the paper, already on Prove2Me as BanditAlgorithm.gittins_index_theorem).
Formalization Note The statement is the general form of the sentence (" is optimal thereafter"): is arbitrary, not only . The hypothesis on is IsSwitchToGittinsAt P r β σ (t + 1) σ'. Weber's bandits with their own state spaces are encoded as chains on one state space with one kernel and one reward (take the disjoint union); is the conditional mean of the random reward . The value is the series of discounted round expectations, the published convention. The standing assumptions of Section 1 (bounded nonnegative rewards, ) are hypotheses; measurability of and the standard Borel structure of are regularity hypotheses the paper leaves implicit.
import Definitions.Def_GittinsIndex import Definitions.Def_WeberGittins_IndexGap_SwitchPolicies open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace WeberGittins.IndexGap
theorem switch_to_gittins_after_t_optimal {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)
(σ σ' : MarkovBanditPolicy k S) (t : ℕ) (hσ' : IsSwitchToGittinsAt P r β σ (t + 1) σ')
(x : Fin k → S) :
markovBanditDiscountedValue P r β σ x ≤ markovBanditDiscountedValue P r β σ' x := by sorry
end WeberGittins.IndexGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.