Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.6 (Blackwell): the optimal policies for the search problem are exactly those conforming to the index p_i q_i / c_i

Proved
AllocationIndices.search_index_optimal

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

bayesian-updatingindex-policysearch-theory

Theorem 3.6. Optimal policies for Problem 3 are those conforming to the index piqi/cip_i q_i / c_ipi​qi​/ci​.

Formally: nnn boxes, prior probabilities pi≥0p_i \ge 0pi​≥0 with ∑ipi=1\sum_i p_i = 1∑i​pi​=1, detection probabilities 0<qi≤10 < q_i \le 10<qi​≤1 and search costs ci>0c_i > 0ci​>0. With the convention that the pip_ipi​ change by Bayes' theorem, so that after NiN_iNi​ unsuccessful searches of box iii the current probability is proportional to pi(1−qi)Nip_i(1-q_i)^{N_i}pi​(1−qi​)Ni​, a search policy σ\sigmaσ (a sequence of boxes) is optimal, in the sense that no policy has a smaller expected cost of finding the object, if and only if at every step it searches a box whose current index pi′qi/cip'_i q_i / c_ipi′​qi​/ci​ is maximal.

The expected cost is ∑kcσkPr⁡[not found by the first k searches]\sum_k c_{\sigma_k} \Pr[\text{not found by the first } k \text{ searches}]∑k​cσk​​Pr[not found by the first k searches] in [0,∞][0, \infty][0,∞]. The "only if" direction is part of the printed statement ("optimal policies are those …"): a policy that ever searches a box of strictly smaller index can be strictly improved by an interchange, and a policy that neglects a box of positive probability has infinite cost. Checked numerically: on random instances every single-step deviation from the index rule increased the cost.

Preamble
import Definitions.Def_AllocationIndices_Jobs

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace AllocationIndices

theorem search_index_optimal {n : ℕ} (p q c : Fin n → ℝ) (hp : ∀ i, 0 ≤ p i) (hp1 : ∑ i, p i = 1)
    (hq0 : ∀ i, 0 < q i) (hq1 : ∀ i, q i ≤ 1) (hc : ∀ i, 0 < c i) (σ : ℕ → Fin n) :
    IsOptimalSearch p q c σ ↔ ConformsToSearchIndex p q c σ := by sorry

end AllocationIndices
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §3.5.4 pp. 71-73, Problem 3, Problem 3A, (3.10)-(3.11) and Theorem 3.6 (Blackwell, reported by Matula 1964; also Exercise 3.6)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

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

  • Endorsed by mikedeng1 · Oct 22, 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