Answers.Body: <p>For a Markov Decision Process <span class="math-container">$(\mathcal{S}, \mathcal{A}, P, R)$</span> (here <span class="math-container">$P(s, s') = \mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a))$</span>;, let us define the value of being in a certain state. That is,
  <span class="math-container">$$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) | S_t =s\right].$$</span>
  That is, the value of being in state <span class="math-container">$s$</span> at time <span class="math-container">$t$</span> is equal to the expected value of the discounted sum of future rewards, where the expectation is taken with respect to <span class="math-container">$\pi(\cdot | s)$</span> the action policy and the environment dynamics <span class="math-container">$P$</span>.</p>
  <p>We will now define
  <span class="math-container">$$\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) = G_t$$</span></p>
  <p>Now, we can rewrite this as
  <span class="math-container">$$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] =  \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma G_{t+1} | S_t =s\right].$$</span>
  The RHS is now in a nicer format and we can express it as
  <span class="math-container">$$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right],$$</span>
  where <span class="math-container">$s'$</span> is the state that we transition into at time <span class="math-container">$t+1$</span>. Note that <span class="math-container">$s'$</span> is a random variable and we are taking the expectation over this according to the action policy and the environment dynamics -- this is because the state we transition into depends first on the action we select and then the environment dynamics <span class="math-container">$P$</span>.</p>
  <p>You can see that we now have
  <span class="math-container">$$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right].$$</span>
  This is the Bellman equation (at least a form of it) and it expresses a recursive relationship between the values of states. That is, the value of being in state <span class="math-container">$s$</span> is equal to the expected immediate reward from being in this state plus the value of being in the state that we transition into. This relationship is useful in Reinforcement Learning as many algorithms use this equation to form update rules to approximate the value/state-action value function of the MDP, such as the  SARSA algorithm, so it is more than just a philosophy, it is the driving force behind many of the RL algorithms.</p>
  <p>Now, when I say at least a form of it, that is because in RL it is also common to see a Bellman equation for the state action value function
  <span class="math-container">$$q_\pi(s, a) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ G_t | S_t = s, A_t = a\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + v_\pi(s') | S_t = s, A_t = a\right];$$</span>
  noting that the value function <span class="math-container">$v$</span> is the expectation of <span class="math-container">$q$</span> over the action space, i.e. we marginalise out the action we condition on -- thus there is the recursive relationship.</p>
  <p>As pointed out in the comments for this question, it is also worth noting that Bellman equations originated in Dynamic Programming, which exist to solve planning problems such as the knapsack problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T01:17:40.993Z
Answers.Text: This answer provides a nice/concise derivation of how one can get to one Bellman equation, but, especially because the OP was confused about _different_ definitions of the "Bellman equation", I think it is worth emphasing that when people say "Bellman equation" in RL they typically mean **any** of the recursive equations that involves some value function, not just the state value function, but what they specifically refer to may probably depend on the context. For example, Barto & Sutton sometimes refer to Q as also a Bellman equation.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T01:19:54.563Z
Answers.Text: So, first, it may also be worth saying that the Bellman equations are actually very important in RL, and they are not just "philosophy" (as the OP thinks). Moreover, you may also say that "Bellman equations" typically arise in dynamic programming (basically invented by Richard Bellman, hence the name) and that dynamic programming solutions exist to solve planning problems (i.e. value/policy iteration, which require the "model"), but DP is not just used in the context of MDPs, but used to solve traditional CS problems (the knacksack problem and so on).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-20T23:41:09.880Z
Answers.LastActivityDate: 2020-12-21T10:35:44.857Z
Answers.LastEditDate: 2020-12-21T10:35:44.857Z
Answers.UserDisplayName: David
Answers.Body: <p>Just to add to the previous answer some more background and intuition. The background of Bellman equation comes from optimal control theory of dynamic systems of form (in discrete time case)
  <span class="math-container">\begin{equation}
  s_{k+1} = f_d(s_k, a_k) \tag{1}
  \end{equation}</span>
  where <span class="math-container">$s_k$</span> represents state at time <span class="math-container">$k$</span> and <span class="math-container">$a_k$</span> action at time <span class="math-container">$k$</span>. The goal is to optimize multistage objective function of form
  <span class="math-container">\begin{equation}
  V_N(s_0) = \sum_{k=0}^N J(s_k, a_k)
  \end{equation}</span>
  while satisfying dynamic constraints <span class="math-container">$(1)$</span> where <span class="math-container">$J(\cdot)$</span> is a stage cost at time <span class="math-container">$k$</span>. The product of this optimization are optimal control policies <span class="math-container">$a_k = \pi_k(s_k)$</span> which provide optimal value for the multistage objective function. Bellman's principle of optimality states that, for the multistage optimization problems, the objective function value at timestep <span class="math-container">$k$</span> should satisfy
  <span class="math-container">\begin{align}
  V^*_{k}(s_k) &amp;= \min_{a_k}[J(s_k, a_k) + V^*_{k-1}(s_{k+1})]\\
  &amp;= \min_{a_k}[J(s_k, a_k) + V^*_{k-1}(f_d(s_k, a_k))]
  \end{align}</span>
  This can be of course proven, you can find the proof in any optimal control/dynamic programming book.</p>
  <p>This also makes intuitive sense. Consider that you are at timestep <span class="math-container">$N$</span> (end of trajectory you want to optimize). You only need to consider 1 action <span class="math-container">$a_N$</span>. You would now go through all possible states <span class="math-container">$s_N$</span> and pick action <span class="math-container">$a_N$</span> which minimizes your stage cost <span class="math-container">$J(s_N, a_N)$</span> for all those states separately. After you did that, you would go one step backwards in time and find optimal action <span class="math-container">$a_{N-1}$</span> for all states <span class="math-container">$s_{N-1}$</span>. According to the Bellman optimality principle, you only need to consider action <span class="math-container">$a_{N-1}$</span> in your optimization, because you already know action <span class="math-container">$a_N$</span> (calculated previously) which would minimize <span class="math-container">$J(s_N, a_N)$</span> for any possible future state <span class="math-container">$s_N$</span>. Then you would keep going backwards in time until <span class="math-container">$k=0$</span>. This is very useful because you don't need to consider all <span class="math-container">$N$</span> timesteps at once, you only consider one timestep at a time which prevents combinatorial explosion for large <span class="math-container">$N$</span>. Bellman optimality principle has been adapted to many different applications, including RL and stochastic systems.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T11:38:29.070Z
Answers.LastActivityDate: 2020-12-21T11:48:20.073Z
Answers.LastEditDate: 2020-12-21T11:48:20.073Z
Answers.UserDisplayName: Brale
Body: <p>What does the Bellman equation actually say? And are there many flavours of that?</p>
  <p>I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is. And I think the Bellman Equation is just basic philosophy and you can do whatever you want with that.</p>
  <p>The interpretations that I have seen so far:</p>
  <p>Let's consider this grid world.</p>
  <pre><code>+--------------+
  | S6 | S7 | S8 |
  +----+----+----+
  | S3 | S4 | S5 |
  +----+----+----+
  | S0 | S1 | S2 |
  +----+----+----+
  </code></pre>
  <ul>
  <li>Rewards: S1:10; S3:10</li>
  <li>Starting Point: S0</li>
  <li>Horizon: 2</li>
  <li>Actions: Up, Down, Left, Right (If an action is not valid because there is no space, you remain in your position)</li>
  </ul>
  <p><strong>The V-Function/Value:</strong></p>
  <p>It tells you how good is it to be in a certain state.</p>
  <p>With a horizon of 2, one can reach:</p>
  <pre><code>S0==&gt;S3 (Up)   (R 5)
  S0==&gt;S0 (Down) (R 0)
  S0==&gt;S1 (Right)(R10)
  S0==&gt;S0 (Left) (R 0)
  </code></pre>
  <p>From that onwards</p>
  <pre><code>S0==&gt;S3 (Up)   (R 5)
  S0==&gt;S0 (Down) (R 0)
  S0==&gt;S1 (Right)(R10)
  S0==&gt;S0 (Left) (R 0)
  
  S1==&gt;S4 (Up)   (R 0)
  S1==&gt;S1 (Down) (R10)
  S1==&gt;S2 (Right)(R 0)
  S1==&gt;S0 (Left) (R 0)
  
  S3==&gt;S6 (Up)   (R 0)
  S3==&gt;S0 (Down) (R 0)
  S3==&gt;S3 (Right)(R 5)
  S3==&gt;S2 (Left) (R10)
  </code></pre>
  <p>Considering no discount, this would mean that it is R=45 good to be in S0, because these are the options. Of course, you can't grab every reward, because you have to decide. Do I need to consider the best next state yet, because this would obviously reduce my expected total reward, but as I can only make two steps it would tell me what is really possible. Not what the overall Reward R(s) in that range is.</p>
  <p><strong>The Q-Function/Value</strong></p>
  <p>This function takes a state and an action, but I am not sure. If that means that I have a reward function that just considers my actions as well to give me a reward. Because in the previous example I just have to land on a state (It doesn't really matter how I get there). But this time I get a reward, when I choose a certain action. R(s,a)
  But otherwise I do not rate the best action and select that next state to calculate the next state. I choose every next step and from that I choose the 2nd next.</p>
  <p><strong>Optimization V-function or Q-function</strong></p>
  <p>This works the same as V-Function or Q-Function, but it just considers the next best award. Some sort of greedy approach:</p>
  <p>First step:</p>
  <pre><code>S0==&gt;S3 (Up)   (R 5) [x]
  S0==&gt;S0 (Down) (R 0) [x]
  S0==&gt;S1 (Right)(R10)
  S0==&gt;S0 (Left) (R 0) [x]
  </code></pre>
  <p>Second Step:</p>
  <pre><code>S1==&gt;S4 (Up)   (R 0) [x]
  S1==&gt;S1 (Down) (R10) 
  S1==&gt;S2 (Right)(R 0) [x]
  S1==&gt;S0 (Left) (R 0)
  </code></pre>
  <p>So, this would say that is the best I can do in two steps. I know that there is a problem, because when I just follow a greedy approach I risk that I won't get the best result, if I would have had a reward of 1000 on S2 later.</p>
  <p>But still, I just want to know, if I have a correct understanding. I know there might be many flavours and interpretations but at least I want to know that is the correct name of these approaches.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-21T17:13:58.527Z
Comments.Text: Your main questions seem to be 1. "What is the Bellman equation telling us?" and 2. "Are there different variants of the BE?". **These are already 2 distinct questions that should be asked in their own separate post, so this post is already too broad and I could close it as such**. In addition to that, you're also talking about value functions and there are some details/calculations that I don't think are really relevant to answer your 2 main questions. So, I suggest that you remove all the details that are not really necessary to answer your 2 main questions because this post is already long.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-21T17:17:41.343Z
Comments.Text: The answers below seem to address what are the Bellman equations and what they are telling us. They do not seem to address any of the details or calculations that you're performing. If you're interested in specific details, I suggest that you ask another question specifically asking about something that you don't understand about those calculations or value functions. Alternatively, instead of removing all the details, you could leave just a simplified version of your calculations that is relevant to your 2 main questions.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-21T17:22:54.267Z
Comments.Text: Moreover, you start by asking "What does the Bellman equation actually telling? And are there many flavours of that?", but you're not even specifying which Bellman equation are you referring to. Then you say "I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is", which people? Can you provide a link? That's what a good question should include (links and the context). This post is just too broad and brings up too many topics that are difficult to address in a single answer.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-21T17:23:42.850Z
Comments.Text: So, as I said, simplify this post as much as possible, but keep the relevant context and information. More importantly, now that there are already 2 answers (both of them seem to be good), try to leave the questions that those answers address. If you have more questions, ask them in another post, as I already said.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-22T17:43:22.693Z
Comments.Text: @nbro I will do that. Just give me a little time.
Comments.UserDisplayName: Johnny
Tags: <reinforcement-learning><definitions><value-functions><bellman-equations>
Title: What is the Bellman Equation actually telling?
UserDisplayName: Johnny
ThreadText: # What is the Bellman Equation actually telling?
  
  (Asked by: username_0 on 2020-12-20)
  
  What does the Bellman equation actually say? And are there many flavours of that?
  
  I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is. And I think the Bellman Equation is just basic philosophy and you can do whatever you want with that.
  
  The interpretations that I have seen so far:
  
  Let's consider this grid world.
  
  ```
  +--------------+
  | S6 | S7 | S8 |
  +----+----+----+
  | S3 | S4 | S5 |
  +----+----+----+
  | S0 | S1 | S2 |
  +----+----+----+
  
  ```
  
  * Rewards: S1:10; S3:10
  * Starting Point: S0
  * Horizon: 2
  * Actions: Up, Down, Left, Right (If an action is not valid because there is no space, you remain in your position)
  
  **The V-Function/Value:**
  
  It tells you how good is it to be in a certain state.
  
  With a horizon of 2, one can reach:
  
  ```
  S0==>S3 (Up)   (R 5)
  S0==>S0 (Down) (R 0)
  S0==>S1 (Right)(R10)
  S0==>S0 (Left) (R 0)
  
  ```
  
  From that onwards
  
  ```
  S0==>S3 (Up)   (R 5)
  S0==>S0 (Down) (R 0)
  S0==>S1 (Right)(R10)
  S0==>S0 (Left) (R 0)
  
  S1==>S4 (Up)   (R 0)
  S1==>S1 (Down) (R10)
  S1==>S2 (Right)(R 0)
  S1==>S0 (Left) (R 0)
  
  S3==>S6 (Up)   (R 0)
  S3==>S0 (Down) (R 0)
  S3==>S3 (Right)(R 5)
  S3==>S2 (Left) (R10)
  
  ```
  
  Considering no discount, this would mean that it is R=45 good to be in S0, because these are the options. Of course, you can't grab every reward, because you have to decide. Do I need to consider the best next state yet, because this would obviously reduce my expected total reward, but as I can only make two steps it would tell me what is really possible. Not what the overall Reward R(s) in that range is.
  
  **The Q-Function/Value**
  
  This function takes a state and an action, but I am not sure. If that means that I have a reward function that just considers my actions as well to give me a reward. Because in the previous example I just have to land on a state (It doesn't really matter how I get there). But this time I get a reward, when I choose a certain action. R(s,a)
  But otherwise I do not rate the best action and select that next state to calculate the next state. I choose every next step and from that I choose the 2nd next.
  
  **Optimization V-function or Q-function**
  
  This works the same as V-Function or Q-Function, but it just considers the next best award. Some sort of greedy approach:
  
  First step:
  
  ```
  S0==>S3 (Up)   (R 5) [x]
  S0==>S0 (Down) (R 0) [x]
  S0==>S1 (Right)(R10)
  S0==>S0 (Left) (R 0) [x]
  
  ```
  
  Second Step:
  
  ```
  S1==>S4 (Up)   (R 0) [x]
  S1==>S1 (Down) (R10) 
  S1==>S2 (Right)(R 0) [x]
  S1==>S0 (Left) (R 0)
  
  ```
  
  So, this would say that is the best I can do in two steps. I know that there is a problem, because when I just follow a greedy approach I risk that I won't get the best result, if I would have had a reward of 1000 on S2 later.
  
  But still, I just want to know, if I have a correct understanding. I know there might be many flavours and interpretations but at least I want to know that is the correct name of these approaches.
  
  **Tags:** reinforcement-learning, definitions, value-functions, bellman-equations
  
  > **Comments:**
  > **username_1**: Your main questions seem to be 1. "What is the Bellman equation telling us?" and 2. "Are there different variants of the BE?". **These are already 2 distinct questions that should be asked in their own separate post, so this post is already too broad and I could close it as such**. In addition to that, you're also talking about value functions and there are some details/calculations that I don't think are really relevant to answer your 2 main questions. So, I suggest that you remove all the details that are not really necessary to answer your 2 main questions because this post is already long.  
  > **username_1**: The answers below seem to address what are the Bellman equations and what they are telling us. They do not seem to address any of the details or calculations that you're performing. If you're interested in specific details, I suggest that you ask another question specifically asking about something that you don't understand about those calculations or value functions. Alternatively, instead of removing all the details, you could leave just a simplified version of your calculations that is relevant to your 2 main questions.  
  > **username_1**: Moreover, you start by asking "What does the Bellman equation actually telling? And are there many flavours of that?", but you're not even specifying which Bellman equation are you referring to. Then you say "I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is", which people? Can you provide a link? That's what a good question should include (links and the context). This post is just too broad and brings up too many topics that are difficult to address in a single answer.  
  > **username_1**: So, as I said, simplify this post as much as possible, but keep the relevant context and information. More importantly, now that there are already 2 answers (both of them seem to be good), try to leave the questions that those answers address. If you have more questions, ask them in another post, as I already said.  
  > **username_0**: @username_1 I will do that. Just give me a little time.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-12-20. Score: 2
  
  For a Markov Decision Process $(\mathcal{S}, \mathcal{A}, P, R)$ (here $P(s, s') = \mathbb{P}(S\_{t+1} = s' | S\_t = s, A\_t = a))$;, let us define the value of being in a certain state. That is,
  $$v\_\pi(s) = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[\sum\_{i=0}^\infty \gamma^{i+t}r(s\_{t+i}, a\_{i+t}) | S\_t =s\right].$$
  That is, the value of being in state $s$ at time $t$ is equal to the expected value of the discounted sum of future rewards, where the expectation is taken with respect to $\pi(\cdot | s)$ the action policy and the environment dynamics $P$.
  
  We will now define
  $$\sum\_{i=0}^\infty \gamma^{i+t}r(s\_{t+i}, a\_{i+t}) = G\_t$$
  
  Now, we can rewrite this as
  $$\mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[G\_t | S\_t =s\right] = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[ r(s\_t, a\_t) + \gamma G\_{t+1} | S\_t =s\right].$$
  The RHS is now in a nicer format and we can express it as
  $$\mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[G\_t | S\_t =s\right] = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[ r(s\_t, a\_t) + \gamma v\_\pi(s') | S\_t =s\right],$$
  where $s'$ is the state that we transition into at time $t+1$. Note that $s'$ is a random variable and we are taking the expectation over this according to the action policy and the environment dynamics -- this is because the state we transition into depends first on the action we select and then the environment dynamics $P$.
  
  You can see that we now have
  $$v\_\pi(s) = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[ r(s\_t, a\_t) + \gamma v\_\pi(s') | S\_t =s\right].$$
  This is the Bellman equation (at least a form of it) and it expresses a recursive relationship between the values of states. That is, the value of being in state $s$ is equal to the expected immediate reward from being in this state plus the value of being in the state that we transition into. This relationship is useful in Reinforcement Learning as many algorithms use this equation to form update rules to approximate the value/state-action value function of the MDP, such as the SARSA algorithm, so it is more than just a philosophy, it is the driving force behind many of the RL algorithms.
  
  Now, when I say at least a form of it, that is because in RL it is also common to see a Bellman equation for the state action value function
  $$q\_\pi(s, a) = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[ G\_t | S\_t = s, A\_t = a\right] = \mathbb{E}\_{a\_i \sim \pi, s\_i \sim P}\left[ r(s\_t, a\_t) + v\_\pi(s') | S\_t = s, A\_t = a\right];$$
  noting that the value function $v$ is the expectation of $q$ over the action space, i.e. we marginalise out the action we condition on -- thus there is the recursive relationship.
  
  As pointed out in the comments for this question, it is also worth noting that Bellman equations originated in Dynamic Programming, which exist to solve planning problems such as the knapsack problem.
  
  > **Comments:**
  > **username_1**: This answer provides a nice/concise derivation of how one can get to one Bellman equation, but, especially because the OP was confused about _different_ definitions of the "Bellman equation", I think it is worth emphasing that when people say "Bellman equation" in RL they typically mean **any** of the recursive equations that involves some value function, not just the state value function, but what they specifically refer to may probably depend on the context. For example, Barto & Sutton sometimes refer to Q as also a Bellman equation.  
  > **username_1**: So, first, it may also be worth saying that the Bellman equations are actually very important in RL, and they are not just "philosophy" (as the OP thinks). Moreover, you may also say that "Bellman equations" typically arise in dynamic programming (basically invented by Richard Bellman, hence the name) and that dynamic programming solutions exist to solve planning problems (i.e. value/policy iteration, which require the "model"), but DP is not just used in the context of MDPs, but used to solve traditional CS problems (the knacksack problem and so on).  
  
  ---
  
  ### Answer by username_3 on 2020-12-21. Score: 1
  
  Just to add to the previous answer some more background and intuition. The background of Bellman equation comes from optimal control theory of dynamic systems of form (in discrete time case)
  \begin{equation}
  s\_{k+1} = f\_d(s\_k, a\_k) \tag{1}
  \end{equation}
  where $s\_k$ represents state at time $k$ and $a\_k$ action at time $k$. The goal is to optimize multistage objective function of form
  \begin{equation}
  V\_N(s\_0) = \sum\_{k=0}^N J(s\_k, a\_k)
  \end{equation}
  while satisfying dynamic constraints $(1)$ where $J(\cdot)$ is a stage cost at time $k$. The product of this optimization are optimal control policies $a\_k = \pi\_k(s\_k)$ which provide optimal value for the multistage objective function. Bellman's principle of optimality states that, for the multistage optimization problems, the objective function value at timestep $k$ should satisfy
  \begin{align}
  V^\*\_{k}(s\_k) &= \min\_{a\_k}[J(s\_k, a\_k) + V^\*\_{k-1}(s\_{k+1})]\\
  &= \min\_{a\_k}[J(s\_k, a\_k) + V^\*\_{k-1}(f\_d(s\_k, a\_k))]
  \end{align}
  This can be of course proven, you can find the proof in any optimal control/dynamic programming book.
  
  This also makes intuitive sense. Consider that you are at timestep $N$ (end of trajectory you want to optimize). You only need to consider 1 action $a\_N$. You would now go through all possible states $s\_N$ and pick action $a\_N$ which minimizes your stage cost $J(s\_N, a\_N)$ for all those states separately. After you did that, you would go one step backwards in time and find optimal action $a\_{N-1}$ for all states $s\_{N-1}$. According to the Bellman optimality principle, you only need to consider action $a\_{N-1}$ in your optimization, because you already know action $a\_N$ (calculated previously) which would minimize $J(s\_N, a\_N)$ for any possible future state $s\_N$. Then you would keep going backwards in time until $k=0$. This is very useful because you don't need to consider all $N$ timesteps at once, you only consider one timestep at a time which prevents combinatorial explosion for large $N$. Bellman optimality principle has been adapted to many different applications, including RL and stochastic systems.
  
  
  ---
  
  