Theorem 2 — backward DP computes (corrected: strict quantile budget in OPT)
ProvedQuantileMDP.theorem_2Let be a finite-horizon Markov decision process with finite state set , finite action set , non-stationary transition laws , rewards and nonempty admissible action sets. Let be a horizon. Put for all and , and compute iteratively, for ,
with the problem (8) with the budget or . Then for every start state and every ,
where is the set of all admissible deterministic history-dependent policies and the quantile is that of the cumulative reward from ; the maximum is attained.
This is the main result of the paper: the quantile-optimal value of a finite-horizon MDP is computed by a backward dynamic program over the pair (state, quantile level), even though the optimal policy itself is in general history dependent.
Differences from the source:
- correction: budget in OPT → or ; reason: the printed statement is false — , one action, , , , (Assumption 1 holds with , , ), : the printed recursion gives via , while the only policy's reward is or with probability each, whose -quantile is .
- encoding: , , of Assumption 1 → kernels and rewards ; reason: every model of Assumption 1 induces such a pair with the same joint law of states, actions and rewards, and every kernel model is one (, , ).
- encoding: policies on → deterministic functions of the state history; reason: for deterministic policies past actions are functions of past states.
- generalization: admissible set → , depending on the state; reason: the paper's case is .
- encoding: , → the essential infimum and supremum of footnote 1, valued in the extended reals; reason: footnote 1 gives the precise form.
- encoding: the law of given → a finite sum of Dirac masses over state paths from weighted by their probabilities; reason: it is that law.
- encoding: "" → the value is the greatest element of the set of quantiles attained by admissible policies; reason: that is what the maximum asserts.
- encoding: admissible sets and the data for → nonempty sets and data for every ; reason: an empty leaves no policy and the maximum undefined, and the data at is never used.
- encoding: the maxima over and in the recursion → suprema in the extended reals in the definition of the recursion; reason: same values: only the value of each step enters the recursion.
import Mathlib import Definitions.Def_QuantileMDP_quantile import Definitions.Def_QuantileMDP_Model import Definitions.Def_QuantileMDP_dpValue
namespace QuantileMDP
/-- Theorem 2 (Optimal Value Function), corrected budget: let `v_T(s, τ) = 0` and compute
`v_t(s, τ) = max_a OPT(s, τ, a, v_{t+1}(·,·))` for `t = T-1, …, 0`. Then `v_0(s, τ)` is the maximum,
over all admissible history-dependent policies `π`, of `Q^π_τ[∑_{k=0}^{T-1} r_k(S_k, a_k, w_k)]`
from `S_0 = s`, for every `τ ∈ [0,1]`.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.3, Theorem 2,
p.12.
**Formalization Note** `OPT` is `opt` with the corrected budget `∑ p_i q_i < τ ∨ ∑ p_i q_i = 0`
(the printed `≤ τ` gives `10` instead of `0` at `τ = 1/2` for one step to two equally likely
states with rewards `0` and `10`). "max" is `IsGreatest`: the value is attained by an admissible
policy and no admissible policy does better. Every horizon `T` (including `0`) and every
`τ ∈ [0,1]`, endpoints included. -/
theorem theorem_2 {S A : Type*} [Fintype S] [Fintype A] (M : Model S A) (T : ℕ) (s : S) (τ : ℝ)
(hτ : τ ∈ Set.Icc (0 : ℝ) 1) :
IsGreatest {x : EReal | ∃ π : Policy S A, M.Admissible π ∧
x = quantile (rewardLaw M T π s) τ} (dpValue M T 0 s τ) := by sorry
end QuantileMDP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.