simulation lemma

Suppose you have learned a model of the world that is slightly wrong — its transition probabilities and rewards are close to reality but not exact. If you plan a great policy inside this imperfect simulator, how good will that policy be in the real environment? The simulation lemma gives the clean answer: the error in the value you compute is controlled by the error in your model, so a good-enough model yields a good-enough policy.

The lemma bounds the difference between a policy's value in the true MDP and its value in the estimated MDP by the model's reward and transition errors, each scaled by the effective horizon 1/(1−γ). Because the bound depends only on model accuracy and the horizon, it lets you reduce the whole problem of learning a good policy to the cleaner statistical problem of learning an accurate model — exactly the strategy behind model-based RL and behind regret proofs like UCRL.

The horizon factor again warns that small model errors are magnified over long horizons, and uniform model accuracy across all states can be expensive to obtain; refined versions weight the error by how often the policy actually visits each state, tightening the bound where it matters.