§4.4.1, p. 115 — Q̂^a_t(b) ≤ Q^a_t(b): the approximation is always an underestimate
ProvedKaelblingPOMDP.Witness.underestimatep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pomdpq-functionwitness-algorithm
Let be a POMDP satisfying the standing hypotheses, and an action. Let be a nonempty finite set of -step trees with root action whose subtrees all lie in , and let . Then for every belief state ,
The witness algorithm grows from below; a belief state where the inequality is strict is a witness that is not yet complete.
Formalization Note is Qfun, the formula of p. 114. Here .
Preamble
import Mathlib import Definitions.Def_KaelblingPOMDP_Witness_Useful
Formal statement
namespace KaelblingPOMDP.Witness
open Finset
universe u
/-- §4.4.1, p. 115 (Kaelbling, Littman, Cassandra, *Planning and acting in partially observable stochastic domains*,
Artificial Intelligence 101:99–134 (1998)): "Note that for all b, Q̂^a_t(b) ⩽ Q^a_t(b); the approximation
is always an underestimate of the true value function." Here `U_a` is any nonempty set of candidate
trees (root `a`, subtrees in `V_{t−1}`), `Q̂^a_t(b) = max_{p ∈ U_a} V_p(b)`, and `t = n + 2`. -/
theorem underestimate {S A Ω : Type u} [Fintype S] [DecidableEq S] [Nonempty S] [Fintype A] [DecidableEq A]
[Nonempty A] [Fintype Ω] [DecidableEq Ω] [Nonempty Ω]
(M : POMDP S A Ω) (hM : M.IsValid) (a : A) (n : ℕ)
(U : Finset (PolicyTree A Ω (n + 1))) (hU : U.Nonempty) (hUC : U ⊆ candidates M a n) :
∀ b ∈ stdSimplex ℝ S, upper M U hU b ≤ Qfun M a n b := by sorry
end KaelblingPOMDP.Witness
Source
Kaelbling, Littman, Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence 101:99–134 (1998), DOI 10.1016/S0004-3702(98)00023-X, p. 115, §4.4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.