Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — F(x, M) is non-decreasing and convex in M, equal to Φ(x) for M ≤ k and to M for M ≥ K

Proved
WhittleGittins.Retirement.lemma1_monotone_convex

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsdynamic-programminggittins-indexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider Whittle's NNN-project bandit process (N≥1N \ge 1N≥1) with rewards bounded as in (1), k(1−β)≤Ri(xi)≤K(1−β)k(1-\beta)\le R_i(x_i)\le K(1-\beta)k(1−β)≤Ri​(xi​)≤K(1−β), and discount 0≤β<10\le\beta<10≤β<1. Let Φ\PhiΦ be the value of the continuing process, the bounded solution of Φ=max⁡iLiΦ\Phi = \max_i L_i\PhiΦ=maxi​Li​Φ (2), and let F(x,M)F(x, M)F(x,M) be the value of the MMM-process, in which one may also retire at any time for the reward MMM: for each MMM, F(⋅,M)F(\cdot, M)F(⋅,M) is the bounded solution of F=max⁡(M,max⁡iLiF)F = \max(M, \max_i L_i F)F=max(M,maxi​Li​F) (4).

Then for every state xxx, F(x,M)F(x, M)F(x,M) is a non-decreasing convex function of MMM with

F(x,M)={Φ(x),M≤k,M,M≥K.(5)F(x, M) = \begin{cases}\Phi(x), & M \le k,\\ M, & M \ge K.\end{cases} \qquad (5)F(x,M)={Φ(x),M,​M≤k,M≥K.​(5)

Moreover, for M<kM < kM<k the optimal policies of the MMM-process and the continuing process are identical: retirement is never optimal (F(x,M)>MF(x, M) > MF(x,M)>M), and every project has the same one-step value in both processes, LiF(⋅,M)(x)=LiΦ(x)L_iF(\cdot, M)(x) = L_i\Phi(x)Li​F(⋅,M)(x)=Li​Φ(x).

Lemma 1 says that the MMM-process interpolates between the continuing process (small MMM) and immediate retirement (large MMM); its convexity is what makes ∂F/∂M\partial F/\partial M∂F/∂M meaningful in the identity (12).

Formalization Note Φ\PhiΦ and FFF are taken as any bounded measurable solutions of (2) and (4) (IsContinuingValue, IsMProcessValue). Projects are indexed by Fin N with [NeZero N]. The last sentence of the Lemma, which speaks of optimal policies, is rendered without a policy layer: for M<kM < kM<k, retirement is strictly worse than continuing and the maximised quantities LiF(⋅,M)(x)L_i F(\cdot,M)(x)Li​F(⋅,M)(x) and LiΦ(x)L_i\Phi(x)Li​Φ(x) coincide for every iii, so the same projects are optimal in both processes.

Preamble
import Mathlib
import Definitions.Def_WhittleGittins_Retirement_BanditProcess
Formal statement
namespace WhittleGittins.Retirement

open MeasureTheory ProbabilityTheory

/-- Lemma 1 (p. 144): `F(x, M)` is non-decreasing and convex in `M`, equals `Φ(x)` for `M ≤ k` and
`M` for `M ≥ K`; for `M < k` retirement is never optimal and the one-step values `Lᵢ F` and
`Lᵢ Φ` coincide, so the optimal policies of the two processes are identical. -/
theorem lemma1_monotone_convex {N : ℕ} [NeZero N] {X : Fin N → Type*}
    [∀ i, MeasurableSpace (X i)] (B : BanditProcess N X)
    (F : (∀ j, X j) → ℝ → ℝ) (Φ : (∀ j, X j) → ℝ)
    (hF : IsMProcessValue B F) (hΦ : IsContinuingValue B Φ) (x : ∀ j, X j) :
    Monotone (F x) ∧ ConvexOn ℝ Set.univ (F x) ∧
      (∀ M, M ≤ B.k → F x M = Φ x) ∧ (∀ M, B.K ≤ M → F x M = M) ∧
      (∀ M, M < B.k → M < F x M ∧ ∀ i, Lop B i (fun z => F z M) x = Lop B i Φ x) := by sorry

end WhittleGittins.Retirement
Source
Whittle, Multi-armed Bandits and the Gittins Index, J. R. Statist. Soc. B 42 (1980), p. 144 (PDF 2), Lemma 1, (5)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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