2
$\begingroup$

In Sutton and Barto's book, they talk about how state value functions can be estimated iteratively. First, we initialize the values of all states to arbitrary values. Then, we improve our estimations by applying the Bellman's equation multiple times.

My question is: if the dynamics of an MDP are known, why cant we work backwards to find the exact value functions? In other words, why can't we start from the terminal states and go to the starting states. Since we know that the value of the terminal states is zero, the value of the states preceding the terminal states would only depend on the immediate reward, which is known.

$\endgroup$

1 Answer 1

1
$\begingroup$

Since we know that the value of the terminal states is zero, the value of the states preceding the terminal states would only depend on the immediate reward, which is known.

Not quite. Just because you can go from some state $s$ to a terminal state doesn't mean that you must go from $s$ to a terminal state. For example, consider a game with two states: from $A$, you can go to terminal state $B$ with 10 reward, or you can return to state $A$ with 1 reward. So state $A$ preceeds a terminal state, but it's not trivial to decide on $V(A)$. If the discount $\gamma$ is 0.95, then the value is 20. If the discount is 0.8, then the value is 10.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.