Theorem 2 — V_{π*}(x) − V_π(x) ≤ (1 − β)E_π[Σ_t β^t(max_i min_{s≤t} G_i(x_i(s)) − R_{j(t)}/(1 − β))]
ProvedWeberGittins.Suboptimality.theorem2_suboptimality_boundConsider the discounted -armed Markov bandit with state space (a standard Borel space), Markov kernel , measurable reward that is nonnegative and uniformly bounded, and discount factor . Let be the fair charge and
the Gittins index of Weber's (3). Write for the state of bandit at time , for the bandit played at time , and for the expected total discounted reward (1) of a policy from the initial states .
Suppose is the optimal (Gittins) policy, i.e. a policy that in every round plays, with probability one, an arm of greatest Gittins index. Then for every policy and every initial state vector ,
This is Theorem 2 of the paper, inequality (6), a bound first given by Glazebrook (1990). It measures how far an arbitrary policy falls short of the optimum by the expected discounted excess, along the policy's own trajectory, of the greatest prevailing charge over the reward actually collected.
Formalization Note Since , the bound is equivalent to ; the statement keeps the paper's form, with inside and the factor outside. "The optimal (Gittins) policy" is any policy satisfying the published IsGittinsIndexPolicy (its optimality is the published Theorem 1, BanditAlgorithm.gittins_index_theorem); the statement does not assume one exists. Weber's is written as the series of round expectations, which agrees with it for bounded rewards. At round the integrand is evaluated on the history of the first rounds and the current state vector , so the minimum runs over ; is the mean of Weber's random reward . The hypotheses "rewards nonnegative and uniformly bounded" and are the standing assumptions of Section 1; measurability of and the standard Borel structure on are added regularity. The bandits are indexed by ; when no policy exists, so the statement has content only for .
import Definitions.Def_WeberGittins_Suboptimality_Model open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace WeberGittins.Suboptimality
theorem theorem2_suboptimality_bound {k : ℕ} {S : Type*}
[MeasurableSpace S] [StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r) (hrb : RewardsNonnegBounded r)
{β : ℝ} (hβ0 : 0 < β) (hβ1 : β < 1)
(π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 ≤
(1 - β) * ∑' t : ℕ, β ^ t * roundExpectation P π x t (fun h j =>
(⨆ i : Fin k, currentHistoryPrevailingCharge (weberIndex P r β) t h i) -
r (h.2 j) / (1 - β)) := by sorry
end WeberGittins.Suboptimality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.