Taking average reward is not optimal when estimating state value in MDP? In policy evaluation process in MDPs, the state value function is calculated as $V(s) = E(r+V(s'))$.
Now suppose there are 7 states in an MDP, where state 1 is the start state and state 7 is the terminal state. Some transitions and their rewards according to some policy are shown in the follows:
start -> end, reward

1 -> 2, 0
1 -> 3, 10
1 -> 4, 25
2 -> 5, 0
3 -> 5, 0
3 -> 6, 0
4 -> 6, 40
4 -> 6, 20
5 -> 7, 20
5 -> 7, 30
6 -> 7, 10
6 -> 7, 20

According to the policy evaluation formula, we can calculate the state value for each state:42, 25, 20, 45, 25, 15, 0 respecively for state 1-7.
However, I don't think the state values is a good fit for the transitions. If we define loss as
$Loss = (V(s) - (V(s')+r))^2$
which is the loss used when we adopt function approximators for value functions,we will find that such set of state values gives a loss of 1567. However, by simply multiplying each state value by 0.9, it can give a better loss of about 1472. It is reasonable because there are lots of zero rewards in the transitions.
So my question is: what is the objective function that taking the expectation of rewards optimizes? Is there anything wrong in my reasoning above? If we use a function approximator, it will definately underestimate the state values, what is the root cause for this?
 A: You are calculating V(s) and your loss function using the data in slightly different ways. Most importantly your loss function sums loss once per sample transition, whilst V(s) is using the transitions in more complex ratios.
By using the sample transitions to build an MDP and resolve V(s), you will on average have trajectories visiting state 1 always, state 2 $\frac{1}{3}$ of the time, and state 5 $\frac{1}{2}$ of the time. These ratios need to form part of your loss calculation, because if this were a sampled supervised learning dataset, then they would occur with that frequency - if you do this you should find that the values you calculate do indeed minimise a weighted MSE.
More concretely, for a fair comparison between your loss calculation from samples and the state values you have estimated, you should define total loss as:
$$L = \sum_{i=i}^{N} \frac{\rho_{MDP}(s_i)}{\rho_{N}(s_i)} (V(s_i) - (V(s'_i)+r_i))^2$$
Where $\rho_{MDP}(s_i)$ is the expected frequency of steps that start in state $S$ resulting from your MDP reconstruction to calculate $V(s_i)$, and $\rho_{N}(s_i)$ is the observed frequency of that start state in the sample set.
This formula will tend towards the MSE loss that you were expecting to see, as you take larger, more representative sample sizes.
