0
$\begingroup$

I am facing some confusion regarding the calculation of the values for the states in a grid world.

My Grid World Example

Given that this is my grid world, where the there is a reward for going to F of +1, and no other rewards for other transitions, with the discount factor of .7, would I need to calculate the state value of F, that is, $V_{i+1}(F)$?

There is no indication that it is a goal state. I have calculated the state values of all other states with $V(F)$ being calculated and it not being calculated, where the calculations results are different. However, I am unsure which is the right calculation to use.

Also, I noticed that there are 2 different equations associated with the VI update

$$ V_{i+1}(s) = R(s) + \gamma \cdot \max_{a} [V_i(s')] $$

$$ V_{i+1}(s) = \max_{a} [R(s, a) + \gamma \cdot V_i(s')] $$

From what I understand, one is a reward associated with an action, but the other with a state. However, other than that, I don't understand when to use which.

$\endgroup$
1
  • $\begingroup$ It's not clear to me why you think you may not need to calculate $V(F)$. It's also even unclearer why you think there's no indication $F$ is the goal state, while you described it as the goal state based on the reward function. Maybe I'm misinterpreting your doubts or statements. Could you please clarify this and also change the title to be your specific question? Thanks $\endgroup$
    – nbro
    Commented Apr 27 at 12:53

1 Answer 1

0
$\begingroup$

The expected immediate reward functions $R(s)$ and $R(s,a)$ are convenient structures for the more fundamental $R(s,a,s')$ (expected reward for starting in state $s$, taking action $a$ and arriving in state $s'$) or $p(r,s'|s,a)$ (probability of observing immediate reward $r$ and next state $s'$ given starting in state $s$ and taking action $a$).

Which one to use depends if and how you can take advantage of the structure of the MDP's reward system.

To use $R(s)$ you need the next expected reward to depend solely on the starting state. That isn't the case for your environment, because the reward is gained when arriving in state $s'$.

To use $R(s,a)$ you need the next expected reward to depend on the starting state and action. Technically this is always true, even if the environment is stochastic (and the agent might not end up in the same next state $s'$ each time), because you can always calculate the expected next reward from the fundamental features of the environment.

So in your case, you should use $R(s,a)$ because that will define which state the agent arrives in, and enable you to figure out the immediate reward.

There are other formulations of the update rule which use other building blocks. For example:

$$V_{t+1}(s) = \text{max}_a [\sum_{r,s'} p(r,s'|s,a)(r + \gamma \cdot V_t(s'))]$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .