0
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ as far as I can tell from your notation the two are actually equivalent, but as $P$ is deterministic you can omit writing this as it is simply 1 for the transition that happens and 0 otherwise. $\endgroup$ Apr 14 at 19:44

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for this incredibly detailed reply! If the agent comes across a state with a reward value, it can choose to collect the reward and enter a terminal state or to just move to the state and not collect the reward, thus not entering terminal state. Given this, we would then be introducing a possible transition probability of $T(s, exit, numberedState) = 1$ and $T(s, move, s') = 1$? For which we would then apply Equation 1? $\endgroup$
    – Krellex
    Apr 15 at 20:25
  • $\begingroup$ @Krellex I'm not sure I understand what you mean. Why do you say that the agent can choose or not to collect the reward? The reward should always be collected. Maybe you mean that the reward function is stochastic (i.e. $R(s, a)$ does not always return the same number but with a certain probability returns some number)? I also don't understand why you mention the "terminal state". Do you know what a terminal state is? What do you mean by "numberedState"? Maybe the "numberedState" refers to the terminal state in your notation? $\endgroup$
    – nbro
    Apr 16 at 8:34
  • $\begingroup$ Anyway, I think you're asking whether you would apply or not the 1st equation for different actions. I don't think I can answer this question definitely because, as I said, the equations you're showing us are just the definitions of the Bellman optimality equation. In fact, we're taking a max with respect to $a$, so you cannot really "choose" with these equations. If you tell me which specific algorithm you're using to solve your problem, I might be able to address your doubts. $\endgroup$
    – nbro
    Apr 16 at 8:35
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .