Importance sampling corrections

Goal: given some function $f$ with random inputs $X$, and a distribution $d^{\prime }$, estimate the expectation of $f(X)$ under a different (target) distribution $d$.

Solution: weight the data by the ratio $d/d^{\prime }$

$$\begin{array}{rl}{\mathbb{E}}_{x\sim d}[f(x)]& =\sum d(x)f(x)\\ & =\sum d^{\prime }(x)\frac{d(x)}{d^{\prime }(x)}f(x)\\ & ={\mathbb{E}}_{x\sim d^{\prime }}\left[\frac{d(x)}{d^{\prime }(x)}f(x)\right]\end{array}$$

This is useful in Off-Policy learning. Ergo, when following policy $\mu$, can use $\frac{\pi (A_t\mid S_t)}{\mu (A_t\mid S_t)}{R}_{t+1}$ as unbiased sample.

For Off-Policy Monto Carlo:

Goal: estimate $v_{\pi }$
Data: trajectory ${\tau }_t=\{S_t,A_t,R_{t+1},S_{t+1},\dots \}$ generated with $\mu$
Solution: use return $G({\tau }_t)=G_t=R_{t+1}+\gamma R_{t+2}+\dots$, and correct:

$$\begin{array}{rl}\frac{p({\tau }_t|\pi )}{p({\tau }_t|\mu )}G({\tau }_t)& =\frac{p(A_t|S_t,\pi )p(R_{t+1},S_{t+1}|S_t,A_t)p(A_{t+1}|S_{t+1},\pi )\cdots }{p(A_t|S_t,\mu )p(R_{t+1},S_{t+1}|S_t,A_t)p(A_{t+1}|S_{t+1},\mu )\cdots }{G}_t\\ & =\frac{\pi (A_t|S_t)\pi (A_{t+1}|S_{t+1})\cdots }{\mu (A_t|S_t)\mu (A_{t+1}|S_{t+1})\cdots }{G}_t\end{array}$$

For TD

$$v(S_t)\leftarrow v(S_t)+\alpha \left(\frac{\pi (A_t\mid S_t)}{\mu (A_t\mid S_t)}(R_{t+1}+\gamma v(S_{t+1}))-v(S_t)\right)$$

For SARSA

This is called Expected SARSA

• No importance sampling is required
• Next action may be chosen using behaviour policy $A_{t+1}\sim \mu (\cdot \mid S_{t+1})$
• But we consider probabilities under $\pi (\cdot \mid S_t)$
• Update $q(S_t,A_t)$ towards value of alternative action

$$q(S_t,A_t)\leftarrow q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma \sum _a\pi (a\mid S_{t+1})q(S_{t+1},a)-q(S_t,A_t)\right)$$

So you can see the expectation there instead of the $\max$ in Q. Actually, Q-learning is a special case with greedy target policy $\pi$.