Two different value functions formulations, how can I reconcile them?

Question

I've been studying Reinforcement learning for the past months, and using different sources, I've been seeing different formulations for the same thing. Specifically for value iteration:

My question is this: imagine that I'm in a scenario where the reward is only dependent on the state, meaning that the reward is for example -1 for all states, with one exception, where it is 1.

For the first formulation the summation will be the:

$V(s)\leftarrow \max _{a}\sum_{_{s'}}p(s'|s, a)[r_{s'} + \gamma V(s')]$, where $r_{s'}$ is the reward for reaching s'

With the second formulation :

$V(s)\leftarrow r_{s}+\max _{a}\sum_{_{s'}}p(s'|s, a)[ \gamma V(s')]$, where $r_s$ is the reward of state s

I'm having trouble reconciling why they are different, shouldn't they produce the same result? I tried them with a very simple RL example where the rewards follow the logic explained above. They produced different policies.

Thank you for the help!

Answer 1

They are the same, but the first formula is more general and allows stochastic rewards.

Remarks

1. $$p(s', r \mid s, a)$$ implies that the reward $r$ is dependent on both a state $s$ and an action $a$.

2. In the first image:$$\sum_{s', r}(\cdot) \overset{\underset{\mathrm{def}}{}}{=} \sum_{s' \in S}\sum_{r \in \mathbb{R}}(\cdot)$$.

3. In the second image, $R(s)$ implies that the reward $r$ is solely dependent on a state $s$. This means: $$p(r \mid s, a) = p(r \mid s)$$ for any $s \in S$, $a \in A$, and $r \in \mathbb{R}$.

   1. $p(r | s)$ is $1$ if $R(s) = r$ and $0$ otherwise.

4. In the second image, $P_{sa}(s')$ implies that the state $s'$ is solely dependent on a state $s$ and an action $a$. This means that: $$p(s' \mid s, a, r) = p(s' \mid s, a)$$ since $r$ is dependent on $s$.

With this knowledge, it is possible to derive the second formula from the first.

Reconciliation

$\begin{align} V(s) &\leftarrow \max_{a \in A}\sum_{s', r}p(s', r \mid s, a) \cdot [r + \gamma V(s')] \\ &\leftarrow \max_{a \in A}\sum_{s' \in S}\sum_{r \in \mathbb{R}}p(s', r \mid s, a) \cdot [r + \gamma V(s')] & \text{(Remark #2)}\\ &\leftarrow \max_{a \in A}\sum_{s' \in S}\sum_{r \in \mathbb{R}}p(s' \mid s, a, r) \cdot p(r \mid s, a) \cdot [r + \gamma V(s')] & \text{(Bayes Theorem)} \\ &\leftarrow \max_{a \in A}\sum_{s' \in S}\sum_{r \in \mathbb{R}}p(s' \mid s, a, r) \cdot p(r \mid s) \cdot [r + \gamma V(s')] & \text{(Remark #3)} \\ &\leftarrow \max_{a \in A}\sum_{s' \in S}\sum_{r \in \mathbb{R}}p(s' \mid s, a) \cdot p(r \mid s) \cdot [r + \gamma V(s')] & \text{(Remark #4)} \\ &\leftarrow \max_{a \in A}\sum_{s' \in S}p(s' \mid s, a) \cdot [R(s) + \gamma V(s')] & \text{(Remark #3.1)} \\ &\leftarrow \max_{a \in A} \left[ \sum_{s' \in S}p(s' \mid s, a) \cdot R(s) + \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s')\right] & \text{(law of distribution)} \\ &\leftarrow \max_{a \in A} \left[ R(s) \cdot \sum_{s' \in S} p(s' \mid s, a) + \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s')\right] & \text{(Pull out } R(s) \text{)} \\ &\leftarrow \max_{a \in A} \left[ R(s) \cdot (1) + \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s')\right] & \text{(A law of probabilities)} \\ &\leftarrow \max_{a \in A} \left[ R(s) + \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s')\right] & \text{(Simplification)} \\ &\leftarrow \max_{a \in A} R(s) + \max_{a \in A} \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s') & \text{(max{a + b} = max{a} + max{b})} \\ &\leftarrow R(s) + \max_{a \in A} \sum_{s' \in S}p(s' \mid s, a) \cdot \gamma V(s') & \text{(}R(s) \text{ is not dependent on } a \text{)}\\ V(s) &\leftarrow R(s) + \max_{a \in A} \gamma \sum_{s' \in S}p(s' \mid s, a) \cdot V(s') & \text{(Pull out } \gamma \text{)}\\ \end{align}$

which is the second formula.