Reinforcement Learning - What's the formula for the value function

Question

I'm trying to implement a value-iteration algorithm to solve a grid-world problem (I'm new to the field). The usual formula that I encounter about the value function V(s) is: $$V(s) = R(s) + max_{a \in A} \sum_{s' \in S} T(s, a, s') V(s')$$ where $S$ is the set of states, $A$ the set of actions, $T$ the transition model

$$T(s, a, s') = P(s_{t+1} = s' | s_t = s, a_t = a)$$ and $R$ the reward function.

Since I'm working on a model-based problem, $T$ and $R$ should be known; the problem is that I don't know how to define (or compute knowing the details of the problem) $R$. If I'm in a state $s$ and take an action $a$ that would make the agent hit a boundary of the grid world, the new state $s'$ will be $s$, and the reward, as defined by the problem, is -5.

On the other hand, if I had arrived in state $s$ through another state, the reward will be -1. So basically, $R(s)$ depends on the previous state and the previous action. How do I represent that in the $V(s)$ formula?

Answer 1

The formula you have quoted is a bit unwieldy, precisely because the R function as defined needs to "look ahead" to all possible outcomes and their probabilities, but how to do that is not included explicitly.

There are actually a few variants of the Bellman equation that express more or less detail. A good place to start for a truly generic version is Sutton & Barto (2nd Edition):

$$v^*(s) = \text{max}_{a \in \mathcal{A}}[\sum_{r,s'}p(r,s'|s,a)(r + v^*(s')]$$

Where $\sum_{r,s'}$ is over all possible reward and next state pairs.

The above equation changes your transition function that only handles next state, to a similar function that handles successor state and reward:

$$p(r,s'|s,a) = Pr\{ R_{t+1} = r, S_{t+1} = s' | S_{t} = s, A_{t} = a \}$$

Usually this does not increase the number of items to sum over, or add much complexity, because reward will most often associated with the transition.

The benefit is that this approach removes the need for a reward function that works with expected reward, and just works with specific rewards. Other variants are possible too, such as an expected reward function based on $(s,a)$ or $(s,a,s')$ - the difference is just a little bit of juggling with the expression so that it remains effectively the same given the subtle differences in definition for $r$.