3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ You explained a few things I was not taking into consideration, but, nevertheless, there are still a few things you didn't explain which still look inconsistent to me. For example, the action $a$ from $s$ may not lead to $s'$, so $a$ and $s'$ are "incompatible". It seems you want to say that, not taking into consideration $a$ seems to because we assume that actions are "equivalent" (either in terms of the next state they bring us to and in terms of e.g. performance/time) to take us to next states. Why this assumption? The Bellman equation I described in my question seems inconsistent. $\endgroup$ – nbro Dec 16 '17 at 13:17
  • $\begingroup$ @nbro: The transition matrix $\mathcal{P}_{ss'}^{a}$ deals with making correct associations and weightings for $a$ with $s'$ so that keeps things consistent. If a particular transition does not occur then the formula gives it a weighting of 0. In practice you would code the summations to avoid even including zero-probability transitions, but that depends on what is possible, whilst the maths formula again gives the general view. $\endgroup$ – Neil Slater Dec 16 '17 at 13:35
  • $\begingroup$ First of all, shouldn't $\mathcal{P}^a_{ss'}$ be an element of a cube (and not a matrix), given that it contains the transition probabilities to move to $s'$ (and there may be more than one) and there multiple combinations of previous states $s$ and $a$? In fact, it needs to be indexed by three elements. Unless that is a matrix for a single $a$, or a single $s$, or a single $s'$. In that case, which one, and why? $\endgroup$ – nbro Dec 16 '17 at 13:55
  • $\begingroup$ @nbro: Technically as per the notation, $\mathcal{P}^a_{ss'}$ is set of $|\mathcal{A}|$ matrices, each $|\mathcal{S}| \times |\mathcal{S}^+|$. But you can treat that as a 3D tensor, yes. Either way my previous comment stands - the inclusion of this transition function is what maintains the correct weighting for $s, a, s'$ in the inner expression - typically it will be sparse (although there is no rule that forces it to be sparse). $\endgroup$ – Neil Slater Dec 16 '17 at 14:03
  • $\begingroup$ Do you know of any article/book where the vector/matrix notation is used to describe RL? $\endgroup$ – nbro Dec 16 '17 at 14:06

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.