Average expected reward vs expected reward for start-state

Question

Suppose we are given a MDP and a policy $\pi$, where for simplicity we have exactly one possible start state $s_0$. Let $V^\pi(s)$ denote the expected return when being in a state s. Moreover, denote by $d^\pi(s)$ the occupancy frequency or on-policy distribution (see for instance http://incompleteideas.net/book/bookdraft2017nov5.pdf on page 163). My question is now: Does the following hold:

$V^\pi(s_0) = \sum_s d^\pi(s) \cdot V^\pi(s)$

where the sum runs over all possible states s. I assume there are just finitely many here. I cannot prove it somehow and I think it does not hold but I do not know of any example. Do you have a proof for that or give some counterexample? Any help appreciated!

Answer 1

For sure the formula that you state does not hold. Assume that the rewards are all positive and that there exists a state $s$ such that $V^\pi(s) > 0$ then

$$\text{RHS} = V^\pi(s_0) + V^\pi(s) + ... \geq V^\pi(s_0) + V^\pi(s) > V^\pi(s_0) = \text{LHS}$$

What you might mean is that

$$V^\pi(s) = \sum_{a} \pi(a|s) Q^\pi(s,a)$$

where $Q^\pi(s,a) = \left(E^\pi[R|S_t=s,A_t=a]\right)$ [here, $R = \sum_{t=0}^\infty \gamma^t R_t$ is the reward variable] which is easily proved:

Assume that $X:\Omega \to \mathcal{X}, Y:\Omega \to \mathcal{Y}, Z : \Omega \to \mathcal{Z}$ are random variables and have a common density $p(x,y,z)$ and furthermore assume that $p(y)>0$ for all $y$, then one can show that $$E[X|Y=y] = \int_{\mathcal{X}} x \cdot p(x|y) dx$$ and $$E[X|Y=y,Z=z] = \int_{\mathcal{X}} x \cdot p(x|y,z) dx$$

(see https://math.stackexchange.com/questions/496608/formal-definition-of-conditional-probability/498338#498338).

Then \begin{align*} E[X|Y=y] &= \int_{\mathcal{X}} x \cdot p(x|y) dx \\ &= \int_{\mathcal{X}} x \cdot \frac{p(x,y)}{p(y)} dx \\ &= \int_{\mathcal{X}} x \cdot \frac{\int_{\mathcal{Z}} p(x,y,z) dz}{p(y)} dx \\ &= \int_{\mathcal{Z}} \int_{\mathcal{X}} x \cdot \frac{ p(x,y,z)p(y,z)}{p(y,z)p(y)} dx dz \\ &= \int_{\mathcal{Z}} \frac{p(z,y)}{p(y)} \int_{\mathcal{X}} x \cdot p(x|y,z) dx dz \\ &= \int_{\mathcal{Z}} p(z|y) E[X|Y=y,Z=z] dz \end{align*}

Applied to the situation above we have $X=R, Y=S_0, Z=A_0$ and $$V^\pi(s) = E[R|S_0=s] = E[X|Y=y] = \sum_{z \in A} p(z|y) E[X|Y=y,Z=z] = \sum_{a \in A} p(a|s) Q^\pi(s,a)$$