p.17 — is the backward recursion
ProvedFreeOrderEPTAS.value_eq_recursionapproximation-schemep2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
For every permutation :
- ;
- the rule "stop at iff " attains this value;
- the program
recursionPreturns at a counted cost of at most .
This is the sentence of p.17 that "can be computed in poly(n) time via dynamic programming".
Differences from the source:
- reading: , "the expected value obtained by an algorithm that utilizes the optimal stopping rule" → the supremum over measurable stopping rules; reason: the operational meaning of the phrase
- encoding: poly(n) time → at most counted units, with the oracle as one unit each; reason: the cost model of the mission
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_V import Definitions.Def_FreeOrderEPTAS_thresholdRule import Definitions.Def_FreeOrderEPTAS_freeOrder open MeasureTheory
Formal statement
namespace FreeOrderEPTAS
/-- p.17 (arXiv:2007.13121v3): the value of the optimal stopping rule on `σ` is the backward
recursion, `V(σ) = R_1`, the threshold rule "stop at `t` iff `X_{σ(t)} ≥ R_{t+1}`" attains it, and
the program `recursionP` computes it at a counted cost of at most `3n`. -/
theorem value_eq_recursion {n : ℕ} (I : Instance n) (σ : Equiv.Perm (Fin n)) :
V I σ = R I σ 0 ∧
∫ x, reward (thresholdRule I σ) σ x ∂(Measure.pi I.μ) = R I σ 0 ∧
∀ r ∈ ((recursionP (orc I) σ).run 0).support, r.1 = R I σ 0 ∧ r.2.total ≤ 3 * n := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, §3.1, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.