Answers.Body: <p>You're correct, that's the definition of the Bellman equation in the deterministic case.</p>
  <p>You can refer to the <a href="https://en.wikipedia.org/wiki/Bellman_equation#:%7E:text=further%20explanation%20needed%5D-,The%20Bellman%20equation,-%5Bedit%5D" rel="nofollow noreferrer">Wikipedia article of the Bellman equation</a> where <span class="math-container">$F(x, a)$</span> is the reward function, with <span class="math-container">$x$</span> the state, <span class="math-container">$T(x,a) = x'$</span>, the transition function, and <span class="math-container">$\beta$</span> the discount factor.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T15:07:05.723Z
Answers.LastActivityDate: 2022-04-15T15:24:06.073Z
Answers.LastEditDate: 2022-04-15T15:24:06.073Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Answers.Body: <p>Your 2nd equation is the Bellman <em>optimality</em> equation (BOE) for <span class="math-container">$V$</span>. So, to emphasise that, you could write it as follows</p>
  <p><span class="math-container">$$
  V^\color{red}{*}(s)
  =
  \max_a(R(s,a) + \gamma\sum_{s'} P(s,a,s') V^\color{red}{*}(s')) 
  \tag{1}\label{1}
  $$</span></p>
  <p>If you let</p>
  <ul>
  <li><span class="math-container">$P(s, a, s') = \mathcal{P}_{ss'}^a = Pr(s_{t+1} = s' \mid s_t = s, a_t = a)$</span>,</li>
  <li><span class="math-container">$R(s,a) = \mathcal{R}_s^a = \mathbb{E}\left[R_{t+1} \mid s_t = s, a_t= a\right]$</span>, where <span class="math-container">$R_{t+1}$</span> is a random variable that represents the reward at time step <span class="math-container">$t+1$</span>,</li>
  <li><span class="math-container">$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]$</span>, and</li>
  <li><span class="math-container">$R(s,a) = \sum_{s'} \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a$</span> (by the law of total expectation)</li>
  </ul>
  <p>then we can rewrite \ref{1} as follows</p>
  <p><span class="math-container">\begin{align}
  V^\color{red}{*}(s)
  &amp;=
  \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) \\
  &amp;=
  \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}</span></p>
  <p>which exactly the same equation as equation 4.1 in Sutton &amp; Barto's book, 1st edition, whose online version you can find <a href="http://incompleteideas.net/book/first/ebook/node40.html" rel="nofollow noreferrer">here</a>. In the 2nd edition, they use a different but equivalent notation.</p>
  <p>Knowing the definition of <span class="math-container">$V^\color{red}{*}(s)$</span> 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 <a href="http://incompleteideas.net/book/first/ebook/node40.html" rel="nofollow noreferrer">this chapter</a>. Anyway, you can use e.g. policy iteration or value iteration.</p>
  <p>Now, back to your actual question. If your environment is deterministic, then</p>
  <p><span class="math-container">$$
  P(s,a,s')
  =
  \begin{cases}
  1, \text{if } f(s, a) = s'\\
  0, \text{otherwise}
  \end{cases}
  $$</span>
  where <span class="math-container">$f$</span> is the (deterministic) transition function.</p>
  <p>This implies that only one summand in <span class="math-container">$\sum_{s'} P(s,a,s') V^\color{red}{*}(s')$</span> might be non-zero. That summand is specifically <span class="math-container">$V^\color{red}{*}(s')$</span>, when <span class="math-container">$f(s, a) = s'$</span>, because, in that case, <span class="math-container">$P(s,a,s') = 1$</span>, and <span class="math-container">$1$</span> times <span class="math-container">$x$</span> is <span class="math-container">$x$</span>.</p>
  <p>So, the BOE simplifies to</p>
  <p><span class="math-container">\begin{align}
  V^\color{red}{*}(s)
  =
  \max_a(R(s,a) + \gamma V^\color{red}{*}(f(s, a))) 
  \end{align}</span></p>
  <p>So, you're correct.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T20:25:54.640Z
Answers.Text: 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?
Answers.UserDisplayName: Krellex
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T08:34:07.807Z
Answers.Text: @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?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T08:35:52.893Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T12:04:16.097Z
Answers.LastActivityDate: 2022-04-15T12:04:16.097Z
Answers.UserDisplayName: nbro
Body: <p>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:</p>
  <p><span class="math-container">$$V(s)=\max_a(R(s,a)+\gamma V(s'))$$</span></p>
  <p>and not</p>
  <p><span class="math-container">$$V(s)=\max_a(R(s,a)+\gamma\sum_{s'}P(s,a,s')V(s'))$$</span></p>
  <p>which would be used for non-deterministic grids?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-14T19:44:40.640Z
Comments.Text: 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.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><game-ai><environment><bellman-equations>
Title: What is the Bellman equation for V(s) in the case of a deterministic environment?
UserDisplayName: Krellex
ThreadText: # What is the Bellman equation for V(s) in the case of a deterministic environment?
  
  (Asked by: username_0 on 2022-04-14)
  
  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?
  
  **Tags:** reinforcement-learning, game-ai, environment, bellman-equations
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2022-04-15. Score: 3 | Accepted answer
  
  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](http://incompleteideas.net/book/first/ebook/node40.html). 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](http://incompleteideas.net/book/first/ebook/node40.html). 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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_3**: @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?  
  > **username_3**: 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.  
  
  ---
  
  ### Answer by username_2 on 2022-04-15. Score: 3
  
  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](https://en.wikipedia.org/wiki/Bellman_equation#:%7E:text=further%20explanation%20needed%5D-,The%20Bellman%20equation,-%5Bedit%5D) where $F(x, a)$ is the reward function, with $x$ the state, $T(x,a) = x'$, the transition function, and $\beta$ the discount factor.
  
  
  ---
  
  