Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 8.6.3 — canonical bias update identity

Proved
PutermanMDP.Unichain.bias_update

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

average-rewardmarkov-decision-processesp2o-gran-per-chapterp2o-plan-bookp2o-v1policy-iterationunichain

In a finite unichain model let (g,h)(g,h)(g,h) be any evaluation solution for the current admissible rule ddd, and let d′d'd′ be the rule selected by the improvement step. With the canonical biases hd∞=Hdrdh^{d^\infty}=H_dr_dhd∞=Hd​rd​ and h(d′)∞=Hd′rd′h^{(d')^\infty}=H_{d'}r_{d'}h(d′)∞=Hd′​rd′​,

h(d′)∞=hd∞−Pd′∗hd∞+Hd′B(g,h).h^{(d')^\infty}=h^{d^\infty}-P_{d'}^*h^{d^\infty}+H_{d'}B(g,h).h(d′)∞=hd∞−Pd′∗​hd∞+Hd′​B(g,h).

The evaluated vector hhh may carry any additive constant; the biases appearing outside BBB have their canonical normalization. The identity describes the transient part of a policy update.

Differences from the source:

  • encoding: finite nonempty state set and finite nonempty state-dependent action sets → finite types S and A, Nonempty S, and nonempty admissible finsets; reason: the union of finitely many finite action sets is finite; irrelevant action entries can be extended by zero rewards and any stochastic row
  • encoding: standing finite unichain model of §8.6 with bounded rewards → IsUnichain M and a finite stationary MDP; reason: finiteness makes the reward bound automatic; no irreducibility or aperiodicity is added
  • encoding: decision rules d_n and d_{n+1} and their evaluation solutions → admissible-rule subtypes d and d′, with explicit evaluation equations; reason: these are the algorithm variables and equations (8.6.1), not assumptions of improvement or termination
  • encoding: P* is the Cesàro limit and H = (I − P + P*)⁻¹(I − P*) → published Cesàro limit and equivalent deviation matrix (I − P + P*)⁻¹ − P*; reason: for finite stochastic P, (I − P + P*)⁻¹P* = P*, so these are the same matrices, including periodic chains
  • reading: the introductory sentence says d_n is determined in the improvement step → d_{n+1} is the rule determined in that step; reason: (8.6.2), (8.6.10) and the proof on p. 381 identify the improved rule as d_{n+1}; this index typo is recorded in INSIGHTS.yaml
Preamble
import Mathlib
import Definitions.Def_PutermanMDP_Unichain_Iteration
open MarkovDecisionProcesses Matrix
Formal statement
namespace PutermanMDP.Unichain

/-- Proposition 8.6.3, (8.6.10). The printed `d_n` in the introductory sentence
is read as `d_{n+1}`, as required by (8.6.2) and the proof's residual identity. -/
theorem bias_update {S A : Type*} [Fintype S] [Fintype A]
    [DecidableEq S] [Nonempty S] (M : StationaryMDP S A) (hM : IsUnichain M)
    (d d' : Rule M) (g : ℝ) (h : S → ℝ)
    (heval : Evaluates M d g h) (himp : Improves M d d' h) :
    policyBias M d' = policyBias M d - (policyLimit M d').mulVec (policyBias M d) +
      (policyDeviation M d').mulVec (optimalityResidual M g h) := by sorry

end PutermanMDP.Unichain
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 380 (PDF 396), Proposition 8.6.3, (8.6.10); proof p. 381 (PDF 397)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. SSS and AAA are finite types, SSS is nonempty and has decidable equality, and MMM is a StationaryMDP with IsUnichain(M)\mathrm{IsUnichain}(M)IsUnichain(M), an imported predicate not shown.

Data. d,d′d, d'd,d′ are rules (functions S→AS\to AS→A choosing admissible actions), g∈Rg\in\mathbb{R}g∈R, and h∈RSh\in\mathbb{R}^Sh∈RS.

Hypotheses.

  • Evaluation: for all sss,
g+h(s)=r(s,d(s))+∑jp(j∣s,d(s)) h(j).g + h(s) = r(s,d(s)) + \sum_j p(j\mid s,d(s))\,h(j).g+h(s)=r(s,d(s))+j∑​p(j∣s,d(s))h(j).
  • Improvement: Improves(M,d,d′,h)\mathrm{Improves}(M,d,d',h)Improves(M,d,d′,h) holds. That is, IsImproving(M,h,d′)\mathrm{IsImproving}(M,h,d')IsImproving(M,h,d′) holds, and if IsImproving(M,h,d)\mathrm{IsImproving}(M,h,d)IsImproving(M,h,d) holds then d′=dd' = dd′=d as whole rules. IsImproving is imported and not shown.

Notation.

  • For a rule eee: Pe=transMatrix(M,e)P_e = \mathrm{transMatrix}(M,e)Pe​=transMatrix(M,e), Pe∗=limitMatrix(Pe)P^*_e = \mathrm{limitMatrix}(P_e)Pe∗​=limitMatrix(Pe​), and He=deviationMatrix(Pe)H_e = \mathrm{deviationMatrix}(P_e)He​=deviationMatrix(Pe​). All three are imported.
  • The bias of eee is he:=He reh_e := H_e\, r_ehe​:=He​re​, where re(s)=r(s,e(s))r_e(s) = r(s,e(s))re​(s)=r(s,e(s)).
  • ψ:=optimalityResidual(M,g,h)\psi := \mathrm{optimalityResidual}(M,g,h)ψ:=optimalityResidual(M,g,h), an imported function not shown.

Conclusion. The vectors in RS\mathbb{R}^SRS satisfy

hd′=hd−Pd′∗ hd+Hd′ ψ.h_{d'} = h_d - P^*_{d'}\, h_d + H_{d'}\,\psi .hd′​=hd​−Pd′∗​hd​+Hd′​ψ.

This identity involves two different vectors:

  • the defined biases hdh_dhd​ and hd′h_{d'}hd′​;
  • the arbitrary evaluation solution hhh, which enters only through ψ\psiψ.

The statement does not require h=hdh = h_dh=hd​.

Degenerate cases. S=∅S = \emptysetS=∅ is excluded. The statement is vacuous in each of the following cases:

  • no rule exists;
  • no pair (g,h)(g,h)(g,h) solves the evaluation equations for ddd;
  • no d′d'd′ satisfies Improves(M,d,d′,h)\mathrm{Improves}(M,d,d',h)Improves(M,d,d′,h), for instance if no rule is improving for hhh;
  • IsUnichain(M)\mathrm{IsUnichain}(M)IsUnichain(M) is unsatisfiable.

If d′=dd' = dd′=d, the identity reads hd=hd−Pd∗hd+Hdψh_d = h_d - P^*_d h_d + H_d \psihd​=hd​−Pd∗​hd​+Hd​ψ.

Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me