Proof of Theorem 4, eq. (10) —
ProvedWeberGittins.Submodular.eq10_partial_sums_submodularLet , , be sequences of real numbers that are nonincreasing () and nonnegative. For a set of bandits and , let be the sum of the first terms of the interleaving of the sequences , , into nonincreasing order (). Then for all sets and all ,
This is inequality (10) in the proof of Weber's Theorem 4, stated for one fixed realisation of the bandits' state sequences, where are the prevailing charges. It is a purely deterministic statement about sums of largest terms; summed against and averaged over realisations it yields the submodularity of the optimal value.
Formalization Note is partialInterleavedSum H I t, the largest sum of initial segments of total length (equal to the interleaving sum for nonincreasing sequences). Nonnegativity of the sequences is Weber's standing assumption of nonnegative rewards (p. 1024), which makes the fair charges nonnegative; it is needed when (for , , and , the left side is and the right side ).
import Definitions.Def_WeberGittins_Submodular_PartialInterleavedSum
namespace WeberGittins.Submodular
/-- Weber (1992), proof of Theorem 4, eq. (10), p. 1030: for nonincreasing, nonnegative
prevailing-charge sequences `H j`, the partial interleaved sums are submodular in the set of
bandits: `U_t(I ∩ J) + U_t(I ∪ J) ≤ U_t(I) + U_t(J)` for all `t ≥ 0`. -/
theorem eq10_partial_sums_submodular {n : ℕ} (H : Fin n → ℕ → ℝ)
(hanti : ∀ j, Antitone (H j)) (hnonneg : ∀ j k, 0 ≤ H j k)
(I J : Finset (Fin n)) (t : ℕ) :
partialInterleavedSum H (I ∩ J) t + partialInterleavedSum H (I ∪ J) t ≤
partialInterleavedSum H I t + partialInterleavedSum H J t := by sorry
end WeberGittins.Submodular
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.