Example 7.6: the normal target process with known variance has index ν(x̄, n) = r(x̄, n) = Φ(x̄ (1 + 1/n)^(-1/2)) when x̄ ≥ 0
ProvedAllocationIndices.normal_target_indexgittins-indexnormal-banditstarget-processes
Example 7.6. Normal target process, known variance , , conjugate prior : the predictive density is , (7.6), and if the state is favourable, so that .
Formally: for , and , the Gittins index of the normal target process (next observation , ; target reached if it is , else the state becomes ) in the state equals , which is .
Preamble
import Definitions.Def_AllocationIndices_Sampling open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices
/-- **Example 7.6** (p. 183), the normal target process with known variance `1`, target `0` and
conjugate prior `N(x̄, 1/n)`: if `x̄ ≥ 0` the state `(x̄, n)` is favourable, since sampling values
below the target can only lower the posterior mean, and hence
`ν(x̄, n) = r(x̄, n) = Φ(x̄ (1 + n⁻¹)^{-1/2})` (7.6), here written as the probability that
`x̄ + √(1 + 1/n) Z ≥ 0` for `Z ~ N(0, 1)`. -/
theorem normal_target_index {xb n : ℝ} (hxb : 0 ≤ xb) (hn : 0 < n) {a : ℝ} (ha0 : 0 < a)
(ha1 : a < 1) :
gittinsIndex normalTargetChain normalTargetReward a (Sum.inl (xb, n)) =
((gaussianReal 0 1) {z | 0 ≤ xb + Real.sqrt (1 + 1 / n) * z}).toReal := by sorry
end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §7.3 pp. 182-183, Example 7.6 and Eq. (7.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.