Lemma 1 — F(x, M) is non-decreasing and convex in M, equal to Φ(x) for M ≤ k and to M for M ≥ K
ProvedWhittleGittins.Retirement.lemma1_monotone_convexConsider Whittle's -project bandit process () with rewards bounded as in (1), , and discount . Let be the value of the continuing process, the bounded solution of (2), and let be the value of the -process, in which one may also retire at any time for the reward : for each , is the bounded solution of (4).
Then for every state , is a non-decreasing convex function of with
Moreover, for the optimal policies of the -process and the continuing process are identical: retirement is never optimal (), and every project has the same one-step value in both processes, .
Lemma 1 says that the -process interpolates between the continuing process (small ) and immediate retirement (large ); its convexity is what makes meaningful in the identity (12).
Formalization Note and 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 , retirement is strictly worse than continuing and the maximised quantities and coincide for every , so the same projects are optimal in both processes.
import Mathlib import Definitions.Def_WhittleGittins_Retirement_BanditProcess
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.