Posterior Sampling Lemma was introduced in the (More) Efficient RL via Posterior Sampling and looks like this.
$M^*$ here is the true MDP while $M_k$ is the MDP sampled from the posterior in episode $k$. $H_{t_k}$ is the history before the start of episode $k$.
I was trying to understand why this lemma holds true, but I am not sure I understand.
- I don't understand what the expectations are with respect to on both sides.
- Maybe a naive question, but if $g$ is $\sigma(H_{t_k})$ measurable, then why does it need the MDP ($M^*$ or $M_k$)? If I understand correctly, $\sigma(H_{t_k})$ measurable means it should be computable using just $H_{t_k}$.
- And where does $f$ come in the definition? Is that hidden in left expectation because $M^*$ is sampled from $f$?
Any insights would be extremely helpful. Thank you.
