Bellman lower bound against every online evader and escape rule
ProvedKServer.chunk_bellman_lowerLet X be a finite metric space and Ω a finite outcome space. Let Pω ≥ 0 be arbitrary, not necessarily normalized weights, and let σ(ω) be request sequences of length at most n whose requested sets are nonempty. Fix any real escape price p, any preceding history h, any deterministic online evader E, and any online bailout predicate b. The finite-horizon Bellman lower value satisfies
At each step V takes the minimum of escaping before the next request is revealed and continuing, branching on the next requested set and minimizing over the serving position within it. Empty remaining sequences contribute zero even when the bailout predicate is true. After branching, outcome weights are restricted without renormalization.
The bound certifies online conditional cost lower bounds for random chunks. Using unnormalized weights makes it applicable directly to filtration atoms, including outcomes given weight zero. The statement is a lower bound and does not claim an optimal policy is attained.
import Definitions.Def_KServer_chunk_bellman open KServer
theorem KServer.chunk_bellman_lower {X : Type*} [MetricSpace X] [Fintype X]
{Ω : Type*} [Fintype Ω] (p : ℝ) (n : ℕ) (P : Ω → ℝ)
(σ : Ω → List (Set X)) (hP : ∀ ω, 0 ≤ P ω)
(hlen : ∀ ω, (σ ω).length ≤ n)
(hne : ∀ ω, ∀ S ∈ σ ω, S.Nonempty)
(E : EvaderAlgorithm X) (b : List (Set X) → Bool) (h : List (Set X)) :
chunkBellman p n P σ (E.pos h) ≤ ∑ ω, P ω * E.bailCost b h (σ ω) p := by sorry