Quantile MDP Theorem 3 — forward execution on the augmented state attains the backward value
ProvedQuantileMDP.theorem_3For a finite MDP and horizon , there are action and level-update maps and . At each and , the action is admissible and maximizes the fixed-action backward value. The allocation attains that fixed-action value:
Here is computed by the backward recursion. With , feasibility means and or .
Starting at any time and initial quantile level , at each step use and set after observing the next state. The induced history-dependent policy is admissible and attains the backward value for the cumulative reward from . The time-zero case is Theorem 3 of Li, Zhong and Brandeau. The statement uses the corrected budget of the existing finite-horizon formalization, including levels zero and one.
Preamble
import Definitions.Def_QuantileMDP_augmentedPolicy import Definitions.Def_QuantileMDP_dpValue import Definitions.Def_QuantileMDP_quantile open MeasureTheory
Formal statement
theorem QuantileMDP.theorem_3 {S A : Type*} [Fintype S] [Fintype A] (M : QuantileMDP.Model S A) (T : ℕ) :
∃ (act : ℕ → S → ℝ → A) (next : ℕ → S → ℝ → S → ℝ),
(∀ t s τ, τ ∈ Set.Icc (0 : ℝ) 1 → act t s τ ∈ M.adm t s) ∧
(∀ t < T, ∀ s τ, τ ∈ Set.Icc (0 : ℝ) 1 →
let a := act t s τ
let q := next t s τ
let p := fun i => (M.P t s a i).toReal
let g := fun i u => QuantileMDP.dpValue M T (t + 1) i u + (M.r t s a i : EReal)
q ∈ QuantileMDP.Feasible p τ ∧
(⨅ i, ⨅ (_ : q i ≠ 1), g i (q i)) = QuantileMDP.opt p g τ ∧
QuantileMDP.opt p g τ = QuantileMDP.dpValue M T t s τ) ∧
∀ t s τ, τ ∈ Set.Icc (0 : ℝ) 1 →
(M.shift t).Admissible (QuantileMDP.augmentedPolicy act next t τ) ∧
QuantileMDP.quantile (QuantileMDP.rewardLaw (M.shift t) (T - t) (QuantileMDP.augmentedPolicy act next t τ) s) τ =
QuantileMDP.dpValue M T t s τ := by sorrySource
Li, Zhong and Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.3, Theorem 3, pp. 13–14. https://arxiv.org/abs/1711.05788v5