How is that possible that a reward function depends both on the next state and an action from current state?

Question

There's the concept of "expected value of the next reward", often denoted as $\mathcal{R}^a_{ss'}$, and defined as

$$ \mathcal{R}^a_{ss'} = \mathbb{E}\left(r_{t+1} \mid s_t = s, a_t = a, s_{t+1} = s' \right) $$

which is the value we expect for the reward at the next time step, that is at time step $t+1$, given that action $a$ from state $s$ brings us to state $s'$.

But the italicized definition does not seem to be "consistent" with the Bellman equation for the value function, which is

\begin{align} V^\pi(s) &= \sum_{a \in \mathcal{A}(s)} \pi(s, a) \sum_{s' \in \mathcal{S^+}} \mathcal{P}^a_{ss'} \left( \mathcal{R}_{ss'}^a + \gamma V^\pi(s') \right) \end{align}

Why do I say this?

$\mathcal{R}_{ss'}^a$ depends on $s$, $a$ and $s'$, but in the Bellman equation above, specifically in the inner sum $\sum_{s' \in \mathcal{S^+}} \mathcal{P}^a_{ss'} \left( \mathcal{R}_{ss'}^a + \gamma V^\pi(s') \right)$, we are essentially iterating over all possible next states, $s'$, of $s$. But, if that's the case, then what's the purpose of making $\mathcal{R}_{ss'}^a$ depend on the action $a$? That is, if we already have the next state $s'$, then the action is useless, given that we are already taking into consideration the possible next states, indeed. In other words, $a$ and $s'$ may not be compatible.

For example, suppose we are in a certain state $s$, and we take action $a$ from there, and we end up in a state, say, $x$, which must be different to all next states $s'$ (in the inner summation), apart at most from one.

I hope you can see my point and my doubts, and I hope you can clarify them.

Furthermore, given this doubt, I am unable to implement a reward function. Also, I have seen an implementation of the reward function, that is

def reward(state, next_state, action):
    if GRID[state] != GOAL and GRID[next_state] == GOAL:
        return 10.0
    else:
        return 0

which actually does not use the action, but I don't understand why. Why should we use next_state and not the next state of state according to action (or vice-versa)? How could (and why would) we use both next_state and action, if they may be "incompatible" in the sense I described above?

Answer 1

The equations you have given are consistent with each other. The outer sum over $a$ provides the value of $a$. The "link" between $s, a$ and $s'$ that gives the correct associations is the transition function $\mathcal{P}^a_{ss'}$ which will be zero for any state/action/next-state triplet that does not make sense for the MDP. By "not make sense", I mean not allowed by the dynamics of the problem - such as an action that would successfully move too many spaces or through a wall for a maze problem.

It is normal for the reward to not actually depend on $a$, but only on the successor state. This might happen in e.g. a dynamic or adversarial environment where the desired goal is to achieve a specific end state. However, it is also possible for the reward to depend on action taken in a given state, such as activating some object in a particular location. It depends on how you have set up the MDP. Another example of where $a$ might be important is if there is a cost associated with each action that varies, for example an energy requirement, so that the total reward might be separate contribution from $s'$ (for reaching a goal) and $a$ (for spending energy to reach any next state).

Using an expected reward $\mathcal{R}_{ss'}^a$ that depends on all three terms $s, a, s'$ gives you a generic version of the Bellman equation that can be applied to the widest range of MDP designs. It doesn't matter if, in a specific case, the only thing you care about is $s'$ which is what the example reward function shows. Once you decide that the expected reward is dependent on $s'$, then the Bellman equation has to have that expected reward term inside the inner sum (the only place where $s'$ is defined), and there is no additional structure in the equation needed to have this term dependent on $s$ and $a$ as well.

You could legitimately use a variant $\mathcal{R}_{s'}$ in a Bellman equation that is otherwise identical to the equation you give in the question, to describe the value function for a MDP where reward only depends on the state transitioned to. However, you will not find that in the literature because it is less generic.

One common variant that you will see is $\mathcal{R}_{s}^{a}$ i.e. the expected reward for taking action $a$ in state $s$. You might use this for cost-based systems, where the goal is to complete a task efficiently and taking actions expends some resource such as time. Using your notation, the Bellman equation for that design looks like this:

\begin{align} V^\pi(s) &= \sum_{a \in \mathcal{A}(s)} \pi(s, a)( \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S^+}} \mathcal{P}^a_{ss'} V^\pi(s')) \end{align}

Answer 2

I answer a similar question here https://stats.stackexchange.com/a/548006/226796

Hope that it helps you to understand the essence better. Below is my answer.

The two forms of rewards are equivalent in the following sense. Now suppose you have an offline dataset consist of s1,s2,..,sk with reward r1,r2,...,rk. Based on the data, you can estimate the MDP model with transition probability T(s,a,s') and R(s,a,s'). You can also estimate the MDP model to be T(s,a,s') and R(s,a). Solve these two MDP models theoretically, you should obtain the same results of policy and value.

The above is model-based learning. You can also use the Q-learning method by using the offline dataset in an online fashion (assume that you observe sk,rk sequentially). Obviously, the estimated Q-matrix Q^t(s,a) would be different during the learning as the two forms of reward are different. However, you should obtain the same results of Q(s,a) when it converges.