0
$\begingroup$

Suppose you have a markov process that can generate bounded random walks such that you have two terminal states... The left most state and the right most state. If the sequence ends in the leftmost state you get 0 reward and if your sequence ends in the right most state you get a reward of 1.

Estimating the value function v(s) for each state provides you with the probability of ending in the right most state given you are in state s. Why is this the case? What is the intuitive explanation that confirms this is a probability?

$\endgroup$
1
  • $\begingroup$ How do you estimate the value function? $\endgroup$
    – gunes
    Feb 15 '20 at 9:54
1
$\begingroup$

I think a more explicit answer can be given by looking at the value function definition. For a random walk (with no actions, a markov reward process), and no discounting, the value function for all states that do not transition into the success terminal state $s_{\text{uccess}}$ is given by

$$V(s) = \underbrace{P(s_\text{failure})(0 + V(s_{\text{failure}}))}_{=0} + \sum_{s' \not = \text{terminal}} P(s'| s) V(s').$$

This is because there is only a reward of $1$ at the "success" terminal state. For any terminal state, the value is $0$. Now, the value for a state that can transition into the success terminal state is

$$V(s) = P(s_\text{ucecss})\underbrace{(1 + V(s_{\text{uccess}}))}_{=1} + \sum_{s' \not = \text{terminal}} P(s'| s) V(s').$$

The value function for all states that do not transition into $s_{\text{uccess}}$ can be expanded recursively as

$$V(s) = \sum_{s' \not = \text{terminal}} P(s' | s) \sum_{s''} P(s'' | s')V(s'').$$

Continuing with this, you can see that the value for any state is the sum over all paths to the terminal state $s_{\text{uccess}}$. This is because the paths that end in the failure terminal state get multiplied by $0$ in the end. Furthermore, each term in the sum is the product of probabilities of that path occuring. In otherwords,

$$V(s) = \sum_{\text{Path}_i: s \rightarrow s_{\text{uccess}}} P(\text{Path}_i).$$ where $P(\text{Path}_i) = \prod_{s \in \text{Path}_i} P(s' | s)$.

$\endgroup$
1
  • $\begingroup$ Ah, this is exactly it. Because it reduces to the sum of products of transitions for in a path over all possible paths, the result is a probability itself. Thank you! $\endgroup$ Feb 29 '20 at 23:54
1
$\begingroup$

This is simply from the fact that the reward of one of the final states is 1 and all other rewards are 0. Value of a state is estimated as expected return from that state. Consider a simple case where you only have 3 states. Far left state is terminal with reward 0 and far right is terminal with reward 1. If you spawn in far left state you immediately end so value of that state is 0. If you spawn in right state you immediately end with reward 1 so value of that state is 1. For the middle state expected value (value of that state) would be \begin{equation} V = 0.5 \cdot 0 + 0.5 \cdot 1 = 0.5 \end{equation} because in random walk you have $0.5$ probability of ending in left state with reward 0 and same probability of ending in right state with reward 1. So you can see that value of the state is basically a probability that you end up in far right terminal state. The same analysis would be done for $n$ states but it would be a bit more complicated since you would have to count in how many different ways you can come from some specific state to a right terminal state. So for general case it would be \begin{equation} V = \sum_{n=0}^{\infty} x_n0.5^n\cdot 1 \end{equation} where $n$ represents number of taken steps, and $x_n$ is number of different ways you can reach right terminal state in $n$ steps. Note that for some number of steps $n$, $x_n$ can be $0$ meaning you cant reach right terminal state in $n$ steps exactly. This sum converges since $0.5 < 1$ and it will be $\leq 1$.

$\endgroup$
1
  • $\begingroup$ For your second equation, I can see how everything up to the multiplication by 1 can be interpreted as a probability, but having a hard time accepting that evaluating the whole expression warrants that it be considered a probability. Are we calling it a probability because as you mentioned the result is bounded between 0 and 1 and that is sufficient? $\endgroup$ Feb 15 '20 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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