Answers.Body: <p>I tried to sketch a mathematical justification of the equality. So we have:</p>
  
  <p><span class="math-container">$$J(\tau) = E_{\tau\sim p_\theta(\tau)}[r(\tau)]$$</span> where <span class="math-container">$p_\theta(\tau) = p(s_1)\prod_{t = 1}^T \pi_{\theta}(a_t, s_t)p(s_{t+1}|s_t, a_t))$</span>.  </p>
  
  <p>Now, <span class="math-container">$p_\theta(\tau)$</span> can be re-written in terms of the Markov Chain transition probabilities, namely: 
  <span class="math-container">$p_\theta(\tau)= \prod_{t = 1}^T \pi_{\theta}(a_t, s_t)p(s_{t}|s_{t-1}, a_{t-1})) = \prod_{t = 1}^T p(s_{t}, a_{t})$</span>.</p>
  
  <p>Here we focus on T = 2 (I guess it is not difficult to prove with a general T, maybe by induction over T). The following holds:
  <span class="math-container">$$J(\tau) = E_{\tau\sim p_\theta(\tau)}[r(\tau)] = E_{(s_1, a_1, s_2, a_2)\sim p(s_1,a_1)p(s_2,a_2)}[r(s_1,a_1) + r(s_2,a_2)] \\ 
  = \int_{(s_1,a_1)} \int_{(s_2,a_2)} (r(s_1,a_1) + r(s_2,a_2))p(s_1,a_1)p(s_2,a_2) d(s_1,a_1)d(s_2, a_2) \\
  = \int_{(s_1,a_1)} \left( \int_{(s_2,a_2)} (r(s_1,a_1)  + r(s_2,a_2))p(s_2,a_2) d(s_2,a_2)\right)p(s_1,a_1)d(s_1, a_1) \\ 
  = E_{(s_1, a_1)\sim p(s_1,a_1)}\left[E_{(s_2, a_2)\sim p(s_2,a_2)}[r(s_1,a_1) + r(s_2,a_2)]\right] \\
  = E_{(s_1, a_1)\sim p(s_1,a_1)} \left[E_{(s_2, a_2)\sim p(s_2,a_2)}[r(s_1,a_1)] + E_{(s_2, a_2)\sim p(s_2,a_2)}[r(s_2,a_2)] \right] \\
  = E_{(s_1, a_1)\sim p(s_1,a_1)} \left[ r(s_1,a_1) + E_{(s_2, a_2)\sim p(s_2,a_2)}[r(s_2,a_2)] \right] $$</span></p>
  
  <p>where the second line is due to the definition of the expectation, in the third line we just changed the order of the terms, in the fourth we used the definition of expectation, in the fifth we used the linearity property of the expectation and the last line is because <span class="math-container">$r(s_1, a_1)$</span> is constant with respect to the integration over <span class="math-container">$(s_2, a_2)$</span>. I preferred to move to the integral form of the expectation in line two and three because it was not clear to me how exactly the expectation could factorise.</p>
  
  <p>To conclude the justification, note that we defined <span class="math-container">$p(s_t, a_t) = \pi_{\theta}(a_t, s_t)p(s_{t}|s_{t-1}, a_{t-1})$</span>, so we have another product here which can be factorised in the same way we did in line two and three of the set of equations above. This brings us the to conditional expectation form of the objective. </p>
  
  <p>In general, every term we have in the original trajectory distribution <span class="math-container">$p_\theta(\tau)$</span> corresponds to an expectation and every reward can be moved up to the first outer expectation which it depends on.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-04T12:06:59.353Z
Answers.LastActivityDate: 2018-12-07T07:32:35.470Z
Answers.LastEditDate: 2018-12-07T07:32:35.470Z
Answers.UserDisplayName: aprospero
Answers.Body: <p>In the <a href="https://www.youtube.com/watch?v=PTbxa6GsTWc&amp;index=3&amp;list=PLkFD6_40KJIznC9CDbVTjAF2oyt8_VAe3" rel="nofollow noreferrer"><em>YouTube depiction of CS294-112 fall 2017 lecture 3 Reinforcement Learning</em>, Levine</a>, the transition of the finite horizon expected reward to a form where each transition is decoupled from the entire Markov chain of state-action marginals is explained between <span class="math-container">$t_{video}$</span> = 44:04 and <span class="math-container">$t_{video}$</span> = 45:22.</p>
  
  <p>At t=44:29, the probabilistic expectation where no actions take place is given as a starting point.  It's a distribution already known, the initial state distribution.</p>
  
  <p>The statement, "Inside that expectation ...," at <span class="math-container">$t_{video}$</span> = 44:39, begins the description of how to build an expectation expression for the first two vertices of the Markov chain.  This is the beginning of a process where expectations <span class="math-container">$E$</span> are factored recursively.  The purpose of the expansions is to decouple the expectation at each vertex from those of other vertices in the Markov chain, clarifying dependencies and exposing the mathematical features of the recursion.</p>
  
  <p>The right-hand factor is the integrated expectation of reward over the achievement of the next state-action marginal, where the action is distributed according to the fixed policy.</p>
  
  <p>How a state and action pair fits into a state-action marginals which can then form a Marcov Chain, provided the policy is fixed and known, was explained at <span class="math-container">$t_{video}$</span> = 21:40 in this same lecture.  Each vertex in the chain is taken to be the aggregation of a state with the proposed action to be applied to it, leading to a reward <span class="math-container">$r(s, a)$</span>.  </p>
  
  <p>Returning to <span class="math-container">$t_{video}$</span> = 44:39, notice the plus sign without the right-hand addend, waiting for another recursion.  When the recursion is expressed later in the process, the right-hand factor becomes the integrated expectation of reward over the achievement of the finite sequence represented by the remainder of the Markov chain.</p>
  
  <p>Multiplication is implied because we are now conditioning on <strong>both</strong> probabilities of the initial state and a transition from it.  Notice also that the second vertex in the Marcov Chain is a state-action marginal.</p>
  
  <p>Notice now that rewards are additive because the goal of learning was defined as a sum of products, which is a simplifying assumption.</p>
  
  <p>Also notice that each expectation distributions of reward after the first one can be expressed as a product of single-vertex expectation distributions.  Each factor is a localized expectation along the sequence of vertices in the Markov chain of state-action marginals.  This is the factoring of expectation distributions.</p>
  
  <p>This factoring is the application of Product distribution, which <a href="https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Product_distribution.html" rel="nofollow noreferrer">can be proven</a> using the "law" of total expectations. </p>
  
  <p>At <span class="math-container">$t_{video}$</span> = 44:51, the pattern recursion is expressed with a single ellipsis.  Recognition of the recursion pattern can be facilitated by re-expressing with a few modifications of mathematical style.</p>
  
  <ul>
  <li>Use of the original variable to represent the value objective</li>
  <li>Extending the equality</li>
  <li>Using two ellipses instead of one clarify the recursion is a continuation of conditions from right to left as well as continuation of rewards from left to right</li>
  <li>Strategically placing line returns</li>
  </ul>
  
  <p><span class="math-container">$$\pi_{\theta}(\tau) = \sum_{t=1}^T \operatorname{E}_{(s_t, a_t)\sim p_\theta(\tau)}[r(s_t, a_t)] \\ = E_{s_1 \sim p(s_1)}[E_{a_1 \sim \pi(a_1|s_1)}[r(s_1, a_1) \\ + E_{s_2 \sim p(s_2|s_1, a_1)}[E_{a_2 \sim \pi(a_2|s_2)}[r(s_2, a_2)] \\ + \; ... \\ ...|s_2]|s_1,a_1]|s_1]]$$</span></p>
  
  <p>Inverting the transformation, recombining the expansion back to its original form may also be illustrative.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-29T15:40:19.817Z
Answers.LastActivityDate: 2018-10-29T16:02:00.557Z
Answers.LastEditDate: 2018-10-29T16:02:00.557Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>In <a href="https://www.youtube.com/watch?v=PTbxa6GsTWc&amp;index=3&amp;list=PLkFD6_40KJIznC9CDbVTjAF2oyt8_VAe3" rel="nofollow noreferrer">one of his lectures</a> Levine describes the objective of reinforcement learning as: <span class="math-container">$$J(\tau) = E_{\tau\sim p_\theta(\tau)}[r(\tau)]$$</span>
  where <span class="math-container">$\tau$</span> refers to a single trajectory and <span class="math-container">$p_\theta(\tau)$</span> is the probability of having taken that trajectory so that <span class="math-container">$p_\theta(\tau) = p(s_1)\prod_{t = I}^T \pi_{\theta}(a_t, s_t)p(s_{t+1}|s_t, a_t))$</span>.</p>
  
  <p>Starting from this definition, he writes the objective as <span class="math-container">$J(\tau) =\sum_{t=1}^T E_{(s_t, a_t)\sim p_\theta(\tau)}[r(s_t, a_t)]$</span> and argues that this sum can be decomposed by using conditional expectations, so that it becomes:</p>
  
  <p><span class="math-container">$$J(\tau) = E_{s_1 \sim p(s_1)}[E_{a_1 \sim \pi(a_1|s_1)}[r(s_1, a_1) + E_{s_2 \sim p(s_2|s_1, a_1)}[E_{a_2 \sim \pi(a_2|s_2)}[r(s_2, a_2)] + ...|s_2]|s_1,a_1]|s_1]]$$</span></p>
  
  <p>Can anyone explain this last step? I guess the <a href="https://en.wikipedia.org/wiki/Law_of_total_expectation" rel="nofollow noreferrer">law of total expectation</a> is involved, but I can not figure out how exactly.</p>
  
Tags: <machine-learning><reinforcement-learning><statistical-ai>
Title: Reinforcement learning objective as conditional expectations
UserDisplayName: aprospero
ThreadText: # Reinforcement learning objective as conditional expectations
  
  (Asked by: username_0 on 2018-10-28)
  
  In [one of his lectures](https://www.youtube.com/watch?v=PTbxa6GsTWc&index=3&list=PLkFD6_40KJIznC9CDbVTjAF2oyt8_VAe3) Levine describes the objective of reinforcement learning as: $$J(\tau) = E\_{\tau\sim p\_\theta(\tau)}[r(\tau)]$$
  where $\tau$ refers to a single trajectory and $p\_\theta(\tau)$ is the probability of having taken that trajectory so that $p\_\theta(\tau) = p(s\_1)\prod\_{t = I}^T \pi\_{\theta}(a\_t, s\_t)p(s\_{t+1}|s\_t, a\_t))$.
  
  Starting from this definition, he writes the objective as $J(\tau) =\sum\_{t=1}^T E\_{(s\_t, a\_t)\sim p\_\theta(\tau)}[r(s\_t, a\_t)]$ and argues that this sum can be decomposed by using conditional expectations, so that it becomes:
  
  $$J(\tau) = E\_{s\_1 \sim p(s\_1)}[E\_{a\_1 \sim \pi(a\_1|s\_1)}[r(s\_1, a\_1) + E\_{s\_2 \sim p(s\_2|s\_1, a\_1)}[E\_{a\_2 \sim \pi(a\_2|s\_2)}[r(s\_2, a\_2)] + ...|s\_2]|s\_1,a\_1]|s\_1]]$$
  
  Can anyone explain this last step? I guess the [law of total expectation](https://en.wikipedia.org/wiki/Law_of_total_expectation) is involved, but I can not figure out how exactly.
  
  **Tags:** machine-learning, reinforcement-learning, statistical-ai
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2018-11-04. Score: 0 | Accepted answer
  
  I tried to sketch a mathematical justification of the equality. So we have:
  
  $$J(\tau) = E\_{\tau\sim p\_\theta(\tau)}[r(\tau)]$$ where $p\_\theta(\tau) = p(s\_1)\prod\_{t = 1}^T \pi\_{\theta}(a\_t, s\_t)p(s\_{t+1}|s\_t, a\_t))$.
  
  Now, $p\_\theta(\tau)$ can be re-written in terms of the Markov Chain transition probabilities, namely:
  $p\_\theta(\tau)= \prod\_{t = 1}^T \pi\_{\theta}(a\_t, s\_t)p(s\_{t}|s\_{t-1}, a\_{t-1})) = \prod\_{t = 1}^T p(s\_{t}, a\_{t})$.
  
  Here we focus on T = 2 (I guess it is not difficult to prove with a general T, maybe by induction over T). The following holds:
  $$J(\tau) = E\_{\tau\sim p\_\theta(\tau)}[r(\tau)] = E\_{(s\_1, a\_1, s\_2, a\_2)\sim p(s\_1,a\_1)p(s\_2,a\_2)}[r(s\_1,a\_1) + r(s\_2,a\_2)] \\
  = \int\_{(s\_1,a\_1)} \int\_{(s\_2,a\_2)} (r(s\_1,a\_1) + r(s\_2,a\_2))p(s\_1,a\_1)p(s\_2,a\_2) d(s\_1,a\_1)d(s\_2, a\_2) \\
  = \int\_{(s\_1,a\_1)} \left( \int\_{(s\_2,a\_2)} (r(s\_1,a\_1) + r(s\_2,a\_2))p(s\_2,a\_2) d(s\_2,a\_2)\right)p(s\_1,a\_1)d(s\_1, a\_1) \\
  = E\_{(s\_1, a\_1)\sim p(s\_1,a\_1)}\left[E\_{(s\_2, a\_2)\sim p(s\_2,a\_2)}[r(s\_1,a\_1) + r(s\_2,a\_2)]\right] \\
  = E\_{(s\_1, a\_1)\sim p(s\_1,a\_1)} \left[E\_{(s\_2, a\_2)\sim p(s\_2,a\_2)}[r(s\_1,a\_1)] + E\_{(s\_2, a\_2)\sim p(s\_2,a\_2)}[r(s\_2,a\_2)] \right] \\
  = E\_{(s\_1, a\_1)\sim p(s\_1,a\_1)} \left[ r(s\_1,a\_1) + E\_{(s\_2, a\_2)\sim p(s\_2,a\_2)}[r(s\_2,a\_2)] \right] $$
  
  where the second line is due to the definition of the expectation, in the third line we just changed the order of the terms, in the fourth we used the definition of expectation, in the fifth we used the linearity property of the expectation and the last line is because $r(s\_1, a\_1)$ is constant with respect to the integration over $(s\_2, a\_2)$. I preferred to move to the integral form of the expectation in line two and three because it was not clear to me how exactly the expectation could factorise.
  
  To conclude the justification, note that we defined $p(s\_t, a\_t) = \pi\_{\theta}(a\_t, s\_t)p(s\_{t}|s\_{t-1}, a\_{t-1})$, so we have another product here which can be factorised in the same way we did in line two and three of the set of equations above. This brings us the to conditional expectation form of the objective.
  
  In general, every term we have in the original trajectory distribution $p\_\theta(\tau)$ corresponds to an expectation and every reward can be moved up to the first outer expectation which it depends on.
  
  
  ---
  
  ### Answer by username_1 on 2018-10-29. Score: 2
  
  In the [*YouTube depiction of CS294-112 fall 2017 lecture 3 Reinforcement Learning*, Levine](https://www.youtube.com/watch?v=PTbxa6GsTWc&index=3&list=PLkFD6_40KJIznC9CDbVTjAF2oyt8_VAe3), the transition of the finite horizon expected reward to a form where each transition is decoupled from the entire Markov chain of state-action marginals is explained between $t\_{video}$ = 44:04 and $t\_{video}$ = 45:22.
  
  At t=44:29, the probabilistic expectation where no actions take place is given as a starting point. It's a distribution already known, the initial state distribution.
  
  The statement, "Inside that expectation ...," at $t\_{video}$ = 44:39, begins the description of how to build an expectation expression for the first two vertices of the Markov chain. This is the beginning of a process where expectations $E$ are factored recursively. The purpose of the expansions is to decouple the expectation at each vertex from those of other vertices in the Markov chain, clarifying dependencies and exposing the mathematical features of the recursion.
  
  The right-hand factor is the integrated expectation of reward over the achievement of the next state-action marginal, where the action is distributed according to the fixed policy.
  
  How a state and action pair fits into a state-action marginals which can then form a Marcov Chain, provided the policy is fixed and known, was explained at $t\_{video}$ = 21:40 in this same lecture. Each vertex in the chain is taken to be the aggregation of a state with the proposed action to be applied to it, leading to a reward $r(s, a)$.
  
  Returning to $t\_{video}$ = 44:39, notice the plus sign without the right-hand addend, waiting for another recursion. When the recursion is expressed later in the process, the right-hand factor becomes the integrated expectation of reward over the achievement of the finite sequence represented by the remainder of the Markov chain.
  
  Multiplication is implied because we are now conditioning on **both** probabilities of the initial state and a transition from it. Notice also that the second vertex in the Marcov Chain is a state-action marginal.
  
  Notice now that rewards are additive because the goal of learning was defined as a sum of products, which is a simplifying assumption.
  
  Also notice that each expectation distributions of reward after the first one can be expressed as a product of single-vertex expectation distributions. Each factor is a localized expectation along the sequence of vertices in the Markov chain of state-action marginals. This is the factoring of expectation distributions.
  
  This factoring is the application of Product distribution, which [can be proven](https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Product_distribution.html) using the "law" of total expectations.
  
  At $t\_{video}$ = 44:51, the pattern recursion is expressed with a single ellipsis. Recognition of the recursion pattern can be facilitated by re-expressing with a few modifications of mathematical style.
  
  * Use of the original variable to represent the value objective
  * Extending the equality
  * Using two ellipses instead of one clarify the recursion is a continuation of conditions from right to left as well as continuation of rewards from left to right
  * Strategically placing line returns
  
  $$\pi\_{\theta}(\tau) = \sum\_{t=1}^T \operatorname{E}\_{(s\_t, a\_t)\sim p\_\theta(\tau)}[r(s\_t, a\_t)] \\ = E\_{s\_1 \sim p(s\_1)}[E\_{a\_1 \sim \pi(a\_1|s\_1)}[r(s\_1, a\_1) \\ + E\_{s\_2 \sim p(s\_2|s\_1, a\_1)}[E\_{a\_2 \sim \pi(a\_2|s\_2)}[r(s\_2, a\_2)] \\ + \; ... \\ ...|s\_2]|s\_1,a\_1]|s\_1]]$$
  
  Inverting the transformation, recombining the expansion back to its original form may also be illustrative.
  
  
  ---
  
  