The importance-sampling ratio corrects the returns: (5.4)
ProvedSuttonBartoRL.ImportanceSampling.ordinary_importance_sampling_unbiasedimportance-samplingmonte-carlop2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning
Let cover , let , and assume that under every episode started at terminates within steps with probability one. Then the return of an episode generated by , weighted by its importance-sampling ratio, has expectation equal to the value of under the target policy:
This is why the first-visit ordinary importance-sampling estimator (5.5) is unbiased.
Formalization Note Time is shifted to . is the expected return of an episode generated by from (not a Bellman fixed point). The book leaves termination implicit; the bounded-horizon hypothesis is a restriction relative to the book, which Example 5.5 (unbounded episodes) shows is not necessary in general.
Preamble
import Mathlib import Definitions.Def_SuttonBartoRL_ImportanceSampling_Episodes
Formal statement
namespace SuttonBartoRL.ImportanceSampling
/-- Sutton & Barto (2018), §5.5, p. 104, Eq. (5.4): `E_b[ρ_{t:T-1} G_t | S_t = s] = v_π(s)`.
Episodes start at `S_0 = s` and follow the behaviour policy `b`, which covers the target policy
`π`; under `b` every episode from `s` terminates within `H` steps with probability one; the
discount rate is `γ ∈ [0, 1]`. -/
theorem ordinary_importance_sampling_unbiased {S A : Type} [Fintype S] [DecidableEq S] [Fintype A]
(M : MDP S A) (term : Finset S) (π b : SuttonBartoRL.FiniteMDP.Policy S A) (hcov : Coverage π b)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ ≤ 1) (s : S) (H : ℕ)
(hH : ∑ n ∈ Finset.range (H + 1), ∑ e : Episode M n, episodeProb M term b s e = 1) :
expectation M term b s (fun n e => e.isRatio π b n * e.ret γ) = value M term π γ s := by sorry
end SuttonBartoRL.ImportanceSampling
Source
Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press (2018), ISBN 9780262039246, Eq. (5.4), p. 104
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.