Section 5, p. 1028 — on a fixed realisation, any policy's greatest prevailing charge is at least the Gittins policy's
ProvedWeberGittins.Suboptimality.greatest_prevailing_charge_ge_gittinsFix a realisation of the states through which each of bandits evolves. Along it, the prevailing charge of bandit after it has been played times is a number , and is nonincreasing (it is a running minimum of fair charges). A policy, on this realisation, is a sequence of arms ; write
for the number of plays of bandit before time , so that is the prevailing charge of bandit at time . The Gittins policy plays, at every time, a bandit whose current prevailing charge is greatest: is a sequence with for all and .
Then for every sequence and every time ,
In words: if one follows a policy that differs from the Gittins policy, the greatest prevailing charge at time is at least as great as it would have been under the Gittins policy. Combined with (5), this gives the suboptimality bound of Theorem 2.
Formalization Note The statement is deterministic. The paper's "fixed realisation" is encoded by arbitrary nonincreasing sequences (the prevailing-charge stacks, which along a realisation are ), and "the Gittins policy" by any greedy interleaving of these stacks (the published IsGreedyChargeStackInterleaving, ties broken arbitrarily). The statement is proved for all nonincreasing stacks, which include the running-minimum stacks. The play counts are the published stackPullCountBefore. Bandits are indexed by ; at both maxima are the empty supremum .
import Definitions.Def_GittinsChargeInterleaving open BanditAlgorithm
namespace WeberGittins.Suboptimality
theorem greatest_prevailing_charge_ge_gittins {k : ℕ} (H : Fin k → ℕ → ℝ)
(hH : ∀ i, Antitone (H i)) (astar : ℕ → Fin k)
(hastar : IsGreedyChargeStackInterleaving H astar) (a : ℕ → Fin k) (t : ℕ) :
(⨆ i : Fin k, H i (stackPullCountBefore astar i t)) ≤
⨆ i : Fin k, H i (stackPullCountBefore a i t) := by sorry
end WeberGittins.Suboptimality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.