Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite discounted greedy charge-stack interleaving

Proved
BanditAlgorithm.discounted_charge_stack_interleaving_le_greedy_prefix

by Harry_Xu · Aug 1, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsgittins-indexprobability

Let Hi(0),Hi(1),…H_i(0),H_i(1),\ldotsHi​(0),Hi​(1),… be a nonincreasing real-valued charge stack for each of kkk arms. An interleaving chooses one stack at each round and receives its next unused charge. Suppose the interleaving a∗a^*a∗ is greedy through round N−1N-1N−1: at every n<Nn<Nn<N, its selected next charge is at least the currently available next charge of every arm. For any other interleaving aaa and any discount factor 0≤α≤10\leq\alpha\leq10≤α≤1,

∑n=0N−1αnHan ⁣(Tan(n))  ≤  ∑n=0N−1αnHan∗ ⁣(Tan∗∗(n)),\sum_{n=0}^{N-1}\alpha^n H_{a_n}\!\left(T_{a_n}(n)\right) \;\leq\; \sum_{n=0}^{N-1}\alpha^n H_{a_n^*}\!\left(T^*_{a_n^*}(n)\right),n=0∑N−1​αnHan​​(Tan​​(n))≤n=0∑N−1​αnHan∗​​(Tan∗​∗​(n)),

where Ti(n)T_i(n)Ti​(n) is the number of entries already taken from stack iii before round nnn under the relevant interleaving.

This finite-horizon greedy-interleaving inequality isolates the deterministic rearrangement step used in the Gittins-index proof and is reusable independently of the stochastic bandit coupling.

Preamble
import Definitions.Def_GittinsChargeInterleaving
Formal statement
namespace BanditAlgorithm

theorem discounted_charge_stack_interleaving_le_greedy_prefix
    {k N : ℕ} {H : Fin k → ℕ → ℝ} {astar : ℕ → Fin k}
    (hH : ∀ i, Antitone (H i))
    (hastar : ∀ n, n < N → ∀ i,
      H i (stackPullCountBefore astar i n) ≤
        H (astar n) (stackPullCountBefore astar (astar n) n))
    {α : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
    (a : ℕ → Fin k) :
    (∑ n ∈ Finset.range N,
        α ^ n * chargeStackInterleaving H a n) ≤
      ∑ n ∈ Finset.range N,
        α ^ n * chargeStackInterleaving H astar n := by
  sorry

end BanditAlgorithm
Source
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §35.4, proof of Lemma 35.10, printed pp. 452–453 (free PDF pp. 460–461), https://tor-lattimore.com/downloads/book/book.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me