What is the Bellman equation for V(s) in the case of a deterministic environment?

Question

I am currently trying to practice reinforcement learning for an agent on a grid. The grid is deterministic. Since the grid is deterministic, to calculate the value for each grid square from the reward and next state, we could simply apply the following Bellman equation:

$$V(s)=\max_a(R(s,a)+\gamma V(s'))$$

and not

$$V(s)=\max_a(R(s,a)+\gamma\sum_{s'}P(s,a,s')V(s'))$$

which would be used for non-deterministic grids?

Answer 1

Your 2nd equation is the Bellman optimality equation (BOE) for $V$. So, to emphasise that, you could write it as follows

$$ V^\color{red}{*}(s) = \max_a(R(s,a) + \gamma\sum_{s'} P(s,a,s') V^\color{red}{*}(s')) \tag{1}\label{1} $$

If you let

• $P(s, a, s') = \mathcal{P}_{ss'}^a = Pr(s_{t+1} = s' \mid s_t = s, a_t = a)$,
• $R(s,a) = \mathcal{R}_s^a = \mathbb{E}\left[R_{t+1} \mid s_t = s, a_t= a\right]$, where $R_{t+1}$ is a random variable that represents the reward at time step $t+1$,
• $R(s, a, s') = \mathcal{R}_{ss'}^a = \mathbb{E}\left[R_{t+1} \mid s_t = s, a_t= a, s_{t+1} = s'\right]$, and
• $R(s,a) = \sum_{s'} \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a$ (by the law of total expectation)

then we can rewrite \ref{1} as follows

\begin{align} V^\color{red}{*}(s) &= \max_a \left(\sum_{s'} \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a + \gamma\sum_{s'} \mathcal{P}_{ss'}^a V^\color{red}{*}(s') \right) \\ &= \max_a \sum_{s'} \mathcal{P}_{ss'}^a \left( \mathcal{R}_{ss'}^a + \gamma V^\color{red}{*}(s') \right) \tag{2}\label{2} \end{align}

which exactly the same equation as equation 4.1 in Sutton & Barto's book, 1st edition, whose online version you can find here. In the 2nd edition, they use a different but equivalent notation.

Knowing the definition of $V^\color{red}{*}(s)$ is not sufficient to find it. You need an algorithm. If you are not familiar with dynamic programming algorithms applied to MPDs, then take a look at this chapter. Anyway, you can use e.g. policy iteration or value iteration.

Now, back to your actual question. If your environment is deterministic, then

$$ P(s,a,s') = \begin{cases} 1, \text{if } f(s, a) = s'\\ 0, \text{otherwise} \end{cases} $$ where $f$ is the (deterministic) transition function.

This implies that only one summand in $\sum_{s'} P(s,a,s') V^\color{red}{*}(s')$ might be non-zero. That summand is specifically $V^\color{red}{*}(s')$, when $f(s, a) = s'$, because, in that case, $P(s,a,s') = 1$, and $1$ times $x$ is $x$.

So, the BOE simplifies to

\begin{align} V^\color{red}{*}(s) = \max_a(R(s,a) + \gamma V^\color{red}{*}(f(s, a))) \end{align}

So, you're correct.

Answer 2

You're correct, that's the definition of the Bellman equation in the deterministic case.

You can refer to the Wikipedia article of the Bellman equation where $F(x, a)$ is the reward function, with $x$ the state, $T(x,a) = x'$, the transition function, and $\beta$ the discount factor.