Equation (7) — the reward-to-go splits by the next state into a mixture of shifted continuation laws
ProvedQuantileMDP.eq_7dynamic-programmingmarkov-decision-processp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantile
Let be a model with finite state and action sets, a horizon, , a state and an action. For an admissible policy started at time in state with first action , the law of the reward-to-go given is
where the continuation after follows the tail policy after the history . Consequently, as in (7),
for every , the mixture inside being the right-hand side of the first display.
This is the step that turns the time- problem into a quantile of a mixture over next states, to which Lemma 2 applies.
Differences from the source:
- generalization: (7), an identity of quantile maxima → the identity of laws (first conjunct) together with (7) (second conjunct); reason: applying and the maximum to the identity of laws gives the printed (7).
- encoding: the sum of indicator-weighted conditional reward-to-go variables → the mixture (law of the continuation shifted by ); reason: the law of that random variable.
- encoding: the process from time and the continuation from time → the models shifted by and , the continuation policy being the policy's tail after ; reason: the paper's histories begin with (p.10).
- encoding: the range of in the recursion () → hypothesis ; reason: same times.
- 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.
- generalization: admissible set → , depending on the state; reason: the paper's case is .
- 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.
Preamble
import Mathlib import Definitions.Def_QuantileMDP_quantile import Definitions.Def_QuantileMDP_Model import Definitions.Def_QuantileMDP_optValue open MeasureTheory
Formal statement
namespace QuantileMDP
/-- Equation (7): conditioning on the next state. For `t < T`, a policy started at time `t` in
state `s` whose first action is `a` has reward-to-go law
`∑_{s'} P_t(s' | s, a) · Law(r_t(s, a, s') + ∑_{k=t+1}^{T-1} r_k | S_{t+1} = s')`, the continuation
being the policy's tail after `s`; hence `ṽ_t(s, τ, a)` is the maximum of `Q_τ` of this mixture.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.2, (7), p.10
(and the display following it, p.11).
**Formalization Note** The first conjunct is the identity of laws behind (7); the second is (7)
at the level of quantiles. The time-`t` process is `M.shift t`, and the process after
`S_{t+1} = s'` is `M.shift (t+1)` under the policy `π.tail s`. -/
theorem eq_7 {S A : Type*} [Fintype S] [Fintype A] (M : Model S A) (T t : ℕ) (ht : t < T) (s : S)
(a : A) :
(∀ π : Policy S A, (M.shift t).Admissible π → π 0 (fun _ => s) = a →
rewardLaw (M.shift t) (T - t) π s =
∑ s' : S, M.P t s a s' •
(rewardLaw (M.shift (t + 1)) (T - (t + 1)) (π.tail s) s').map
(fun x => x + M.r t s a s')) ∧
(∀ τ : ℝ, optValueAct M T t s τ a =
⨆ (π : Policy S A) (_ : (M.shift t).Admissible π) (_ : π 0 (fun _ => s) = a),
quantile (∑ s' : S, M.P t s a s' •
(rewardLaw (M.shift (t + 1)) (T - (t + 1)) (π.tail s) s').map
(fun x => x + M.r t s a s')) τ) := by sorry
end QuantileMDP
Source
Li, Zhong, Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.2, (7), p.10, and the display following it, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.