Body: <p>When reading the following paper(page 4): <a href="https://arxiv.org/pdf/1911.03728.pdf" rel="nofollow noreferrer">An Approximate Dynamic Programming Approach
  for Dual Stochastic Model Predictive Control</a></p>
  <p>I could see that they were able to unnest the minimization's in the bellmans equations due to sampling of the expected values. It would be cumbersome to write down their whole setup so i thought i might understand why with another example:</p>
  <p>Consider the value function below:</p>
  <p><span class="math-container">\begin{align}
  V^{*}(s_0) &amp;= \min_{a_0 \in A_{s_0}}[r(s_0, a_0) + \sum_{s_1}p(s_1|s_0, a_0)V^{*}(s_1)] \\
             &amp;= \min_{a_0 \in A_{s_0}}[r(s_0, a_0) + \sum_{s_1}p(s_1|s_0, a_0)]\min_{a_1 \in A_{s_1}}[r(s_1, a_1) + \sum_{s_2}p(s_2|s_1, a_1)V^{*}(s_2)] \\
             &amp;(?\neq, = ?) \min_{a_0 \in A_{s_0}, a_1 \in A_{s_1}}[r(s_0, a_0) + \sum_{s_1}p(s_1|s_0, a_0)][r(s_1, a_1) + \sum_{s_2}p(s_2|s_1, a_1)V^{*}(s_2)]
  \end{align}</span>
  when should it be an <span class="math-container">$\neq$</span> or an <span class="math-container">$=$</span> in the third equation and why, i.e how can sampling break the recursion and allow us to unnest the minimizations?</p>
  <p>(in the paper, they argue that since they use samples to approximate the expected value of the cost-to-go/next state value function they are allowed to unnest the minimizations)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-01T17:07:13.540Z
Comments.Text: Crossposted (duplicate) at OR.SE: [When can we unnest the minimizations/recursions in value functions(bellman optimality)?](https://or.stackexchange.com/q/11320/491)
Comments.UserDisplayName: SecretAgentMan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-01T22:04:33.820Z
Comments.Text: @SecretAgentMan This question is perfectly fine for this site. There's arguably no better site to ask this question than AI SE.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-03T07:32:20.520Z
Comments.Text: removed the question on operations research
Comments.UserDisplayName: richard baws
Tags: <reinforcement-learning><optimization><markov-decision-process><value-functions><bellman-equations>
Title: When can we unnest the minimizations/recursions in an value function(bellman optimality equation)?
UserDisplayName: richard baws
ThreadText: # When can we unnest the minimizations/recursions in an value function(bellman optimality equation)?
  
  (Asked by: username_0 on 2023-11-28)
  
  When reading the following paper(page 4): [An Approximate Dynamic Programming Approach
  for Dual Stochastic Model Predictive Control](https://arxiv.org/pdf/1911.03728.pdf)
  
  I could see that they were able to unnest the minimization's in the bellmans equations due to sampling of the expected values. It would be cumbersome to write down their whole setup so i thought i might understand why with another example:
  
  Consider the value function below:
  
  \begin{align}
  V^{\*}(s\_0) &= \min\_{a\_0 \in A\_{s\_0}}[r(s\_0, a\_0) + \sum\_{s\_1}p(s\_1|s\_0, a\_0)V^{\*}(s\_1)] \\
  &= \min\_{a\_0 \in A\_{s\_0}}[r(s\_0, a\_0) + \sum\_{s\_1}p(s\_1|s\_0, a\_0)]\min\_{a\_1 \in A\_{s\_1}}[r(s\_1, a\_1) + \sum\_{s\_2}p(s\_2|s\_1, a\_1)V^{\*}(s\_2)] \\
  &(?\neq, = ?) \min\_{a\_0 \in A\_{s\_0}, a\_1 \in A\_{s\_1}}[r(s\_0, a\_0) + \sum\_{s\_1}p(s\_1|s\_0, a\_0)][r(s\_1, a\_1) + \sum\_{s\_2}p(s\_2|s\_1, a\_1)V^{\*}(s\_2)]
  \end{align}
  when should it be an $\neq$ or an $=$ in the third equation and why, i.e how can sampling break the recursion and allow us to unnest the minimizations?
  
  (in the paper, they argue that since they use samples to approximate the expected value of the cost-to-go/next state value function they are allowed to unnest the minimizations)
  
  **Tags:** reinforcement-learning, optimization, markov-decision-process, value-functions, bellman-equations
  > **Comments:**
  > **username_1**: Crossposted (duplicate) at OR.SE: [When can we unnest the minimizations/recursions in value functions(bellman optimality)?](https://or.stackexchange.com/q/11320/491)  
  > **username_2**: @SecretAgentMan This question is perfectly fine for this site. There's arguably no better site to ask this question than AI SE.  
  > **username_0**: removed the question on operations research  
  
  ---
  
  ## 0 answers
  
  