Answers.Body: <p>In the context of decision theory (and reinforcement learning, which is the trendier name for this field of research nowadays), the Bellman equations are the most important equations because all algorithms used in reinforcement learning are derived from them. Even though they might not seem groundbreaking they are the foundations on which the whole field rests.</p>
  <p>Let's take as an example the policy iteration algorithm. It consists of alternating a policy evaluation and a policy improvement step until convergence.</p>
  <p>If we take the Bellman equation for the value function, we have
  <span class="math-container">$$V^\pi(s) = \mathbb{E}_{a_t \sim \pi(s), s_{t+1} \sim P(.|s, a_t)}[R(s, a_t) + \gamma V^\pi(s_{t+1}) | s_t = s]$$</span>
  where <span class="math-container">$\pi$</span> is the policy, <span class="math-container">$P$</span> the transition probabilities and <span class="math-container">$R$</span> the reward function.</p>
  <p>You can calculate this exactly in the discrete case, if <span class="math-container">$P$</span> and <span class="math-container">$\pi$</span> are known, because it's a system of <span class="math-container">$|S|$</span> (the dimension of the state space) equations with <span class="math-container">$|S|$</span> unknowns (the <span class="math-container">$V^\pi(s)$</span>).</p>
  <p>Once you've evaluated your policy, you perform a policy improvement step which consists in setting (pay attention to where <span class="math-container">$\pi'$</span> and <span class="math-container">$\pi$</span> are used) <span class="math-container">$$V^{\pi'}(s) = \text{argmax}_a Q_\pi(s, a) = \text{argmax}_a \mathbb{E}_{s' \sim P(.|s,a)}[R(s, a) + \gamma V^\pi(s') | S_t=s, A_t=a]$$</span> The fact that the new greedy policy <span class="math-container">$\pi'$</span> is a strict improvement over <span class="math-container">$\pi$</span> can be derived from the Bellman equations (you can refer to the <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Sutton&amp;Barto book</a> section 4.2 for the full proof). It's called greedy because we've assumed that by changing <span class="math-container">$\pi$</span> by only looking at what's better one step ahead we've improved <span class="math-container">$\pi$</span> for all following steps.</p>
  <p>The final piece of the puzzle is that we've designed a sequence of monotically improving policies. We know it converges towards the optimal policy in a finite number of steps because there's only a finite number of policies in the discrete case.</p>
  <p>Hopefully this gives you an idea of why the Bellman equations are so important.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-09T20:41:02.723Z
Answers.Text: This is correct, but, although the OP mentions the "decision theory" and "game theory" contexts, I would also say that 1. dynamic programming is a general approach to solving problems, as long as they satisfy 2 conditions (optimal substructure and overlapping subproblems - refer to the CLRS book), 2. why that is the case in the case of RL, 3. mention the "Bellman optimality principle" and how it relates to what you just said.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-10T20:18:22.010Z
Answers.Text: Just to double check before I amend my answer:
  2. Is it because we are in an MDP setting where P(S_t|S_{t-1}, A_{t-1},S_{t-2},...) = P(S_t|S_{t-1},A_{t-1})?
  3. The principal of optimality is what is used to derive the Bellman equations (e.g. the one I gave for the state value function), is that what you want me to mention?
Answers.UserDisplayName: Raphael Lopez Kaufman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-10T22:19:27.103Z
Answers.Text: I think the Bellman _optimality_ equation (BOE) (a _recurrence relation_, which is a term used in CS in the context of DP) itself describes that an MDP has _optimal substructure_, i.e. the solution to $v(s)$ is a function of $v(s')$ (a subproblem) - if you know $v(s')$, you also know $v(s)$. Regarding the overlapping subproblems, $v(s')$ could be used to define both $v(s_1)$ and $v(s_2)$, so we can reuse $v(s')$ to compute $v(s_1)$ and $v(s_2)$, so they have overlapping subproblems. Note that this is how I've just tried to connect the 2 worlds - CS and RL - so I don't know if this is accurate.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-10T22:20:43.190Z
Answers.Text: So, I am not sure if the Markov property is relevant here. I know we can use it to derive the BE from the definition of the value function (see [here](https://nbro.gitlab.io/blogging/2022/02/16/bellman-equations/)), so maybe the Markov property is somehow related. Regarding the principle of optimality, as stated e.g. in Wikipedia _Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision_, I think that's just the BOE.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-11T19:48:40.437Z
Answers.Text: It all makes sense. I'm wondering if from this you have precise suggestions to make my answer better for OP. These are all valid points, but I'm not sure they explain why the Bellman equations are important.
Answers.UserDisplayName: Raphael Lopez Kaufman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-11T20:40:00.447Z
Answers.Text: The question wasn't just about the Bellman equation but also the "Bellman's Condition of Optimality" (which I assume the OP was referring to the "principle of optimality" I have just quoted from Wikipedia) [so maybe it was a bit too broad anyway]. This reminded me of the 2 conditions I just mentioned for a dynamic programming solution to be applicable. So, these Bellman equations and "principle of optimality" also appear in other areas other than MDPs, so that's another reason why they are important, in my view. You don't have to change your answer, I just wanted to point this out.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-09T19:44:12.253Z
Answers.LastActivityDate: 2022-05-09T19:44:12.253Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Body: <p>In the context of Decision Making and Game Theory, &quot;Bellman's Equations and Bellman's Conditions of Optimality&quot; are said to be some of the most important mathematical principles in this field.</p>
  <p>Reading <a href="https://en.wikipedia.org/wiki/Bellman_equation" rel="nofollow noreferrer">the corresponding Wikipedia page</a>,
  I am trying to understand what is considered so &quot;groundbreaking&quot; about the Bellman's Condition of Optimality.</p>
  <p>As far as I understand, Bellman's Principle of Optimality is saying that - for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered. If I have understood this correctly - isn't this kind of obvious?</p>
  <p>To me, this sounds like a tautology - for something to be blue, the thing must also be blue.</p>
  <p>I think I am obviously not understanding the above statements properly.</p>
  <p><strong>In short, could someone please explain why Bellman's Equations and Bellman's Conditions of Optimality are considered so &quot;important and groundbreaking&quot;?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-09T15:23:57.620Z
Comments.Text: Can you please quote the statement that you're confused about, rather than providing a possible misinterpretation of it? For example, you say "for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered", that doesn't look very accurate. I would prefer to see the original statement.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><bellman-equations>
Title: What is so special about the Bellman Optimality Principle?
UserDisplayName: stats_noob
ThreadText: # What is so special about the Bellman Optimality Principle?
  
  (Asked by: username_0 on 2022-05-09)
  
  In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this field.
  
  Reading [the corresponding Wikipedia page](https://en.wikipedia.org/wiki/Bellman_equation),
  I am trying to understand what is considered so "groundbreaking" about the Bellman's Condition of Optimality.
  
  As far as I understand, Bellman's Principle of Optimality is saying that - for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered. If I have understood this correctly - isn't this kind of obvious?
  
  To me, this sounds like a tautology - for something to be blue, the thing must also be blue.
  
  I think I am obviously not understanding the above statements properly.
  
  **In short, could someone please explain why Bellman's Equations and Bellman's Conditions of Optimality are considered so "important and groundbreaking"?**
  
  **Tags:** reinforcement-learning, bellman-equations
  > **Comments:**
  > **username_1**: Can you please quote the statement that you're confused about, rather than providing a possible misinterpretation of it? For example, you say "for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered", that doesn't look very accurate. I would prefer to see the original statement.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-05-09. Score: 2
  
  In the context of decision theory (and reinforcement learning, which is the trendier name for this field of research nowadays), the Bellman equations are the most important equations because all algorithms used in reinforcement learning are derived from them. Even though they might not seem groundbreaking they are the foundations on which the whole field rests.
  
  Let's take as an example the policy iteration algorithm. It consists of alternating a policy evaluation and a policy improvement step until convergence.
  
  If we take the Bellman equation for the value function, we have
  $$V^\pi(s) = \mathbb{E}\_{a\_t \sim \pi(s), s\_{t+1} \sim P(.|s, a\_t)}[R(s, a\_t) + \gamma V^\pi(s\_{t+1}) | s\_t = s]$$
  where $\pi$ is the policy, $P$ the transition probabilities and $R$ the reward function.
  
  You can calculate this exactly in the discrete case, if $P$ and $\pi$ are known, because it's a system of $|S|$ (the dimension of the state space) equations with $|S|$ unknowns (the $V^\pi(s)$).
  
  Once you've evaluated your policy, you perform a policy improvement step which consists in setting (pay attention to where $\pi'$ and $\pi$ are used) $$V^{\pi'}(s) = \text{argmax}\_a Q\_\pi(s, a) = \text{argmax}\_a \mathbb{E}\_{s' \sim P(.|s,a)}[R(s, a) + \gamma V^\pi(s') | S\_t=s, A\_t=a]$$ The fact that the new greedy policy $\pi'$ is a strict improvement over $\pi$ can be derived from the Bellman equations (you can refer to the [Sutton&Barto book](http://incompleteideas.net/book/RLbook2020.pdf) section 4.2 for the full proof). It's called greedy because we've assumed that by changing $\pi$ by only looking at what's better one step ahead we've improved $\pi$ for all following steps.
  
  The final piece of the puzzle is that we've designed a sequence of monotically improving policies. We know it converges towards the optimal policy in a finite number of steps because there's only a finite number of policies in the discrete case.
  
  Hopefully this gives you an idea of why the Bellman equations are so important.
  
  > **Comments:**
  > **username_1**: This is correct, but, although the OP mentions the "decision theory" and "game theory" contexts, I would also say that 1. dynamic programming is a general approach to solving problems, as long as they satisfy 2 conditions (optimal substructure and overlapping subproblems - refer to the CLRS book), 2. why that is the case in the case of RL, 3. mention the "Bellman optimality principle" and how it relates to what you just said.  
  > **username_2**: Just to double check before I amend my answer: 2. Is it because we are in an MDP setting where P(S_t|S_{t-1}, A_{t-1},S_{t-2},...) = P(S_t|S_{t-1},A_{t-1})? 3. The principal of optimality is what is used to derive the Bellman equations (e.g. the one I gave for the state value function), is that what you want me to mention?  
  > **username_1**: I think the Bellman _optimality_ equation (BOE) (a _recurrence relation_, which is a term used in CS in the context of DP) itself describes that an MDP has _optimal substructure_, i.e. the solution to $v(s)$ is a function of $v(s')$ (a subproblem) - if you know $v(s')$, you also know $v(s)$. Regarding the overlapping subproblems, $v(s')$ could be used to define both $v(s_1)$ and $v(s_2)$, so we can reuse $v(s')$ to compute $v(s_1)$ and $v(s_2)$, so they have overlapping subproblems. Note that this is how I've just tried to connect the 2 worlds - CS and RL - so I don't know if this is accurate.  
  > **username_1**: So, I am not sure if the Markov property is relevant here. I know we can use it to derive the BE from the definition of the value function (see [here](https://nbro.gitlab.io/blogging/2022/02/16/bellman-equations/)), so maybe the Markov property is somehow related. Regarding the principle of optimality, as stated e.g. in Wikipedia _Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision_, I think that's just the BOE.  
  > **username_2**: It all makes sense. I'm wondering if from this you have precise suggestions to make my answer better for OP. These are all valid points, but I'm not sure they explain why the Bellman equations are important.  
  > **username_1**: The question wasn't just about the Bellman equation but also the "Bellman's Condition of Optimality" (which I assume the OP was referring to the "principle of optimality" I have just quoted from Wikipedia) [so maybe it was a bit too broad anyway]. This reminded me of the 2 conditions I just mentioned for a dynamic programming solution to be applicable. So, these Bellman equations and "principle of optimality" also appear in other areas other than MDPs, so that's another reason why they are important, in my view. You don't have to change your answer, I just wanted to point this out.  
  
  ---
  
  