Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Example 11.4 — two MRPs with the same data distribution have different BE at w = 0

Proved
SuttonBartoRL.OffPolicy.bellman_error_not_learnable

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

counterexamplep2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning

Take the two Markov reward processes of Example 11.4 with their features, and any discount γ∈[0,1]\gamma\in[0,1]γ∈[0,1]. At w=0\mathbf w = \mathbf 0w=0:

  1. in the left MRP the Bellman error vector is zero, so BE(0)=0\mathrm{BE}(\mathbf 0) = 0BE(0)=0 for every state weighting μ\muμ;
  2. hence in the left MRP w=0\mathbf w=\mathbf 0w=0 minimizes the BE for every nonnegative μ\muμ;
  3. in the right MRP, with μ(s)=13\mu(s) = \tfrac13μ(s)=31​,
BE(0)=μ(B)⋅1+μ(B′)⋅1=23.\mathrm{BE}(\mathbf 0) = \mu(\mathsf B)\cdot 1 + \mu(\mathsf B')\cdot 1 = \tfrac23 .BE(0)=μ(B)⋅1+μ(B′)⋅1=32​.
  1. μ(s)=13\mu(s) = \tfrac13μ(s)=31​ is a stationary distribution of the right MRP, and μ1=(13,23)\mu_1 = (\tfrac13, \tfrac23)μ1​=(31​,32​) one of the left MRP;
  2. the two MRPs, each started from its stationary distribution, generate the same observable data distribution: for every nnn, every initial observation o0o_0o0​ and all rewards and observations (r1,o1),…,(rn,on)(r_1, o_1), \dots, (r_n, o_n)(r1​,o1​),…,(rn​,on​), the probability of observing x(S0)=o0,R1=r1,x(S1)=o1,…,Rn=rn,x(Sn)=on\mathbf x(S_0) = o_0, R_1 = r_1, \mathbf x(S_1) = o_1, \dots, R_n = r_n, \mathbf x(S_n) = o_nx(S0​)=o0​,R1​=r1​,x(S1​)=o1​,…,Rn​=rn​,x(Sn​)=on​ is the same in both.

Since the two MRPs generate the same data distribution, the BE is not a function of the data: it is not learnable.

Formalization Note The MRPs are the ones of the definition item, transcribed from the figure on p. 276. The book does not give μ\muμ for the left MRP; claims 1–2 hold for every μ\muμ. The data distribution is described by all finite prefixes of the observed stream (feature vectors and rewards), with each process started from its stationary distribution. The book's further remark on the BE minimizer of the right MRP as γ→1\gamma\to1γ→1 is not formalized.

Preamble
import Mathlib
import Definitions.Def_SuttonBartoRL_OffPolicy_LinearGeometry
import Definitions.Def_SuttonBartoRL_OffPolicy_BELearnabilityExample
Formal statement
namespace SuttonBartoRL.OffPolicy

/-- Sutton & Barto (2018), Example 11.4, p. 276. For every discount `γ ∈ [0, 1]`, at `w = 0`:
1. in the left MRP the Bellman error vector is zero, so `BE(0) = 0` for every state weighting `µ`;
2. hence in the left MRP `w = 0` minimizes the BE (for every nonnegative `µ`);
3. in the right MRP with `µ(s) = 1/3`, `BE(0) = µ(B)·1 + µ(B′)·1 = 2/3`;
4. `µ(s) = 1/3` is stationary for the right MRP, and `(1/3, 2/3)` for the left one;
5. the two MRPs, each started from its stationary distribution, generate the same observable data
   distribution: every finite sequence of observed feature vectors and rewards has the same
   probability in both. -/
theorem bellman_error_not_learnable (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ ≤ 1) :
    (bellmanError beMRP1 (mrpPolicy (Fin 2)) γ beFeatures1 0 = 0 ∧
      ∀ μ : Fin 2 → ℝ, BE beMRP1 (mrpPolicy (Fin 2)) γ μ beFeatures1 0 = 0) ∧
    (∀ μ : Fin 2 → ℝ, (∀ s, 0 ≤ μ s) → ∀ w : Fin 2 → ℝ,
      BE beMRP1 (mrpPolicy (Fin 2)) γ μ beFeatures1 0
        ≤ BE beMRP1 (mrpPolicy (Fin 2)) γ μ beFeatures1 w) ∧
    BE beMRP2 (mrpPolicy (Fin 3)) γ beMu2 beFeatures2 0 = 2 / 3 ∧
    (∀ s' : Fin 3, ∑ s, beMu2 s * beMRP2.trans s () s' = beMu2 s') ∧
    (∀ s' : Fin 2, ∑ s, beMu1 s * beMRP1.trans s () s' = beMu1 s') ∧
    ∀ (o₀ : Fin 2 → ℝ) (l : List (ℝ × (Fin 2 → ℝ))),
      obsProb beMRP1 beMu1 beFeatures1 o₀ l = obsProb beMRP2 beMu2 beFeatures2 o₀ l := by sorry

end SuttonBartoRL.OffPolicy
Source
Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press (2018), ISBN 9780262039246, Example 11.4, p. 276
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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