Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The DAI Theorem, "only if" half — an optimal policy almost surely continues a process of maximal index at every stage

Open
GittinsDAI.IndexTheorem.dai_theorem_only_if

by tianyipeng · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-processesdynamic-programminggittins-indexmulti-armed-bandit

Consider a simple family of kkk alternative bandit processes. Each process is a Markov chain on a common standard Borel state space Θ\ThetaΘ with transition kernel PPP and measurable reward function RRR. At each stage n=0,1,2,…n=0,1,2,\dotsn=0,1,2,… a policy observes the history so far (the past state vectors and the processes chosen) and the current state vector (x1,…,xk)(x_1,\dots,x_k)(x1​,…,xk​), and selects one process, possibly at random; the selected process iii earns anR(xi)a^n R(x_i)anR(xi​) and moves according to PPP, while the other processes are frozen. Policies may be randomized and history-dependent. The discount factor satisfies 0<a<10<a<10<a<1, and for every state xxx

E{∑t=0∞at∣R(x(t))∣ ∣ x(0)=x}<∞.E\Big\{\sum_{t=0}^{\infty} a^t |R(x(t))| \,\Big|\, x(0)=x\Big\}<\infty .E{t=0∑∞​at∣R(x(t))∣​x(0)=x}<∞.

Write Vπ(x)V_\pi(x)Vπ​(x) for the total expected discounted reward of a policy π\piπ from the initial state vector xxx, and ν(y)\nu(y)ν(y) for the dynamic allocation index (Eq. (2)) of a process in state yyy, assumed to be a measurable function of the state (as the paper asserts on p. 151).

The DAI Theorem, "only if" half. Let π\piπ be a policy and xxx an initial state vector with

Vπ(x)=sup⁡π′Vπ′(x).V_\pi(x) = \sup_{\pi'} V_{\pi'}(x).Vπ​(x)=π′sup​Vπ′​(x).

Then at every stage nnn, for almost every history of the first nnn stages under the law of play of π\piπ from xxx, the process selected by π\piπ is, with probability one, one of those whose index in its current state is maximal:

πn({i:ν(xi(n))=max⁡jν(xj(n))} ∣ history)=1.\pi_n\big(\{i : \nu(x_i(n)) = \max_j \nu(x_j(n))\} \,\big|\, \text{history}\big) = 1 .πn​({i:ν(xi​(n))=jmax​ν(xj​(n))}​history)=1.

This is the necessity half of Gittins' DAI Theorem ("a policy is optimal if and only if at each stage the bandit process selected for continuation is almost always one of those whose dynamic allocation index is then maximal"): every optimal policy is, almost surely along its own trajectory, an index policy. The sufficiency half (an index policy is optimal) is the Gittins index theorem.

Formalization Note Same model and hypotheses as the full DAI theorem GittinsDAI.IndexTheorem.dai_theorem (MarkovBanditPolicy, markovBanditMeasure, markovBanditDiscountedValue, gittinsIndex). "Optimal" means attaining the (real) supremum over all policies from the given initial state vector xxx; "at each stage … almost always" is read per stage, almost surely under the policy's own finite-horizon law from xxx.

Preamble
import Mathlib
import Definitions.Def_GittinsIndex
import Definitions.Def_AllocationIndices_Index
open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace GittinsDAI.IndexTheorem

/-- **The DAI Theorem, "only if" half** (Gittins 1979, Section 3, p. 154): for a simple family of
alternative bandit processes, an optimal policy almost surely continues, at every stage, a bandit
process whose dynamic allocation index is then maximal. -/
theorem dai_theorem_only_if {k : ℕ} {S : Type*} [MeasurableSpace S] [StandardBorelSpace S]
    (P : Kernel S S) [IsMarkovKernel P] {r : S → ℝ} (hr : Measurable r) {α : ℝ}
    (hα0 : 0 < α) (hα1 : α < 1) (hint : DiscountedRewardIntegrable P r α)
    (hg : Measurable (gittinsIndex P r α))
    (π : MarkovBanditPolicy k S) (x : Fin k → S)
    (hopt : markovBanditDiscountedValue P r α π x =
        ⨆ π' : MarkovBanditPolicy k S, markovBanditDiscountedValue P r α π' x) :
    ∀ n : ℕ, ∀ᵐ h ∂(markovBanditMeasure P π x n),
        (π.select n) h {a | ∀ j, gittinsIndex P r α (h.2 j) ≤ gittinsIndex P r α (h.2 a)} = 1 := by sorry

end GittinsDAI.IndexTheorem
Source
Gittins, Bandit Processes and Dynamic Allocation Indices, J. R. Statist. Soc. B 41 (1979), p. 154, The DAI Theorem (Section 3), "only if" direction

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