# What is the immediate reward in value iteration?

Suppose you're given an MDP where rewards are attributed for reaching a state, independently of the action. Then when doing value iteration:

$$V_{i+1} = \max_a \sum_{s'} P_a(s,s') (R_a(s,s') + \gamma V_i(s'))$$

what is $$R_a(s,s')$$ ?

The problem I'm having is that terminal states have, by default, $$V(s_T) = R(s_T)$$ (some terminal reward). Then when I'm trying to implement value iteration, if I set $$R_a(s,s')$$ to be $$R(s')$$ (which is wha I thought), I get that states neighboring a terminal state have a higher value than the terminal state itself, since

$$P_a(s,s_T) ( R_a(s,s_T) + \gamma V_i(s_T) )$$

can easily be greater than $$V_i(s_T)$$, which in practice makes no sense. So the only conclusion I seem to be able to get is that in my case, $$R_a(s,s') = R(s)$$.. is this correct?

what is $$R_a(s,s')$$ ?

In this case, it appears to represent the expected immediate reward received when taking action $$a$$ and transitioning from state $$s$$ to state $$s'$$. It is written this way so it could be implemented as a series of square matrices, one for each action. Those matrices might of course be very sparse if only a few transitions are possible, but it's a nice generic form for describing MDPs.

Notation varies between different RL tutorials, so do take care when looking at other sources.

The problem I'm having is that terminal states have, by default, $$V(s_T) = R(s_T)$$ (some terminal reward).

No, $$V(s_T) = 0$$ by definition. The value of a state, is the expected discounted sum of future rewards. A terminal state has no future rewards, thus its value is always $$0$$.

The "terminal reward" in your system occurs on the transition $$s \rightarrow s_T$$, so its expected value should be represented by $$R_a(s,s_T)$$

If the terminal state is some goal state, or a bad exit from an episode, and it doesn't matter how you arrive there, then in the formulation you have given, you still represent it as $$R_a(s,s_T)$$, just that the values of $$a$$ and $$s$$ don't matter for your case. In general they might matter, for other MDPs.

So the only conclusion I seem to be able to get is that in my case, $$R_a(s,s') = R(s)$$.. is this correct?

Not in general. However, in some problems this might be a reasonable simplification. If you make that simplification, then you should take care when having a value associated with a single state to be consistent about whether the reward is for entering a particular state, or exiting it. There cannot be a reward for "being in a state", the closest you can get to that is granting a consistent reward when entering a state (ignoring the previous state and action that caused the transition).

It appears here that you have suggested here that you want a reward for exiting a particular state - ignoring which action is taken in it, or what the next state is. I don't know the details of your MDP, so cannot say whether this would work for you. Maybe not, given the rest of your question.

If you are asking in general, then you have the answer $$R_a(s,s') \ne R(s)$$

If you are asking in order to work on a specific MDP, I suggest take another look at your original problem, with the extra information in this answer.

• "No, V(sT)=0 by definition. The value of a state, is the expected discounted sum of future rewards. A terminal state has no future rewards, thus its value is always 0." That's the one, didn't realise it.. thanks! Oct 9 '18 at 7:07