The DAI Theorem, "only if" half — an optimal policy almost surely continues a process of maximal index at every stage
OpenGittinsDAI.IndexTheorem.dai_theorem_only_ifConsider a simple family of alternative bandit processes. Each process is a Markov chain on a common standard Borel state space with transition kernel and measurable reward function . At each stage a policy observes the history so far (the past state vectors and the processes chosen) and the current state vector , and selects one process, possibly at random; the selected process earns and moves according to , while the other processes are frozen. Policies may be randomized and history-dependent. The discount factor satisfies , and for every state
Write for the total expected discounted reward of a policy from the initial state vector , and for the dynamic allocation index (Eq. (2)) of a process in state , assumed to be a measurable function of the state (as the paper asserts on p. 151).
The DAI Theorem, "only if" half. Let be a policy and an initial state vector with
Then at every stage , for almost every history of the first stages under the law of play of from , the process selected by is, with probability one, one of those whose index in its current state is maximal:
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 ; "at each stage … almost always" is read per stage, almost surely under the policy's own finite-horizon law from .
import Mathlib import Definitions.Def_GittinsIndex import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
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