Theorem 1 — (corrected: strict quantile budget in OPT)
ProvedQuantileMDP.theorem_1dynamic-programmingmarkov-decision-processp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantile
Let be a model with finite state set and finite action set, a horizon, , a state, an admissible action and . Let be the optimal value function (5) at time and the intermediate value function. Then
the supremum being over with or , where . The supremum is attained by some such , and the maximum defining is attained by an admissible policy with .
Together with (6) this is the dynamic-programming step of the quantile MDP: the time- value function is computed from the time- value function as a function of both the state and the quantile level.
Differences from the source:
- correction: budget → or ; reason: the printed statement is false — , one action, , , , , , : gives , while the only policy's reward is or with probability each and .
- reading: "max" and the admissible actions → hypothesis ; reason: for a non-admissible no policy has , and the paper's maximum ranges over admissible actions (p.8).
- generalization: admissible set → , depending on the state; reason: the paper's case is .
- encoding: , , of Assumption 1 → kernels and rewards ; reason: every model of Assumption 1 induces such a pair with the same joint law, 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.
- encoding: and real values → the finite type as index set, values in the extended reals; reason: same instances.
- encoding: the process from time → the model shifted by , started at its time , with a fresh policy; reason: the paper's histories begin with (p.10).
- 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 in OPT and over policies in → suprema in the extended reals together with clauses saying each is attained; reason: that is what the maxima assert.
Preamble
import Mathlib import Definitions.Def_QuantileMDP_quantile import Definitions.Def_QuantileMDP_opt import Definitions.Def_QuantileMDP_Model import Definitions.Def_QuantileMDP_optValue
Formal statement
namespace QuantileMDP
/-- Theorem 1 (Value Function Dynamic Programming), corrected budget: for `t < T` and an
admissible action `a`, `ṽ_t(s, τ, a) = OPT(s, τ, a, v_{t+1}(·,·))`, where
`OPT = max_q min_{i : q_i ≠ 1} [v_{t+1}(s_i, q_i) + r_t(s, a, l_t(s, a, s_i))]` with
`p_i = P(S_{t+1} = s_i | S_t = s, a_t = a)` and `v_{t+1}` the optimal value function (5). Both
maxima are attained: the one over `q` in `OPT` and the one over policies in `ṽ_t`.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.2, Theorem 1 (8),
p.11.
**Formalization Note** `OPT` is `opt` with the corrected budget `∑ p_i q_i < τ ∨ ∑ p_i q_i = 0`
(the printed `≤ τ` fails at `τ = 1/2` for one step to two equally likely states with rewards
`0` and `10`). The state space is indexed by the type `S` itself. The maximum over actions in the
paper ranges over admissible actions, so `a ∈ adm t s` is assumed. -/
theorem theorem_1 {S A : Type*} [Fintype S] [Fintype A] (M : Model S A) (T t : ℕ) (ht : t < T)
(s : S) (a : A) (ha : a ∈ M.adm t s) (τ : ℝ) (hτ : τ ∈ Set.Icc (0 : ℝ) 1) :
optValueAct M T t s τ a =
opt (fun s' => (M.P t s a s').toReal)
(fun s' q => optValue M T (t + 1) s' q + ((M.r t s a s' : ℝ) : EReal)) τ ∧
OptAttained (fun s' => (M.P t s a s').toReal)
(fun s' q => optValue M T (t + 1) s' q + ((M.r t s a s' : ℝ) : EReal)) τ ∧
∃ π : Policy S A, (M.shift t).Admissible π ∧ π 0 (fun _ => s) = a ∧
quantile (rewardLaw (M.shift t) (T - t) π s) τ = optValueAct M T t s τ a := by sorry
end QuantileMDP
Source
Li, Zhong, Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.2, Theorem 1 (8), p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.