Theorem 3.6 (Blackwell): the optimal policies for the search problem are exactly those conforming to the index p_i q_i / c_i
ProvedAllocationIndices.search_index_optimalTheorem 3.6. Optimal policies for Problem 3 are those conforming to the index .
Formally: boxes, prior probabilities with , detection probabilities and search costs . With the convention that the change by Bayes' theorem, so that after unsuccessful searches of box the current probability is proportional to , a search policy (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 is maximal.
The expected cost is in . 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.
import Definitions.Def_AllocationIndices_Jobs open MeasureTheory ProbabilityTheory BanditAlgorithm
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.