Answers.Body: <blockquote>
    <p><strong>Question 1</strong>. Are the states <span class="math-container">$s'$</span> drawn from a from a joint probability distribution <span class="math-container">$P_{sa}$</span>? In other words, if you are in an
    initial state <span class="math-container">$s$</span>, take an action <span class="math-container">$\pi(s)$</span>, then <span class="math-container">$s'$</span> is the random
    state you would end up in according to the probability distribution
    <span class="math-container">$P_{sa}$</span>?</p>
  </blockquote>
  
  <p>This is tricky, because you don't show a definition of <span class="math-container">$P_{sa}$</span>. My first thought was that you meant the transition matrix <span class="math-container">$P_{ss'}^a$</span>, but that doesn't fit with the phrase <em>joint probability distribution</em>.</p>
  
  <p>If you really mean <em>joint probability distribution</em> then the answer is generally "no", because <span class="math-container">$P_{sa}$</span> should be the probability of observing state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span> when taking a random sampled time step:</p>
  
  <p><span class="math-container">$$P_{sa} = \pi(a|s)\rho_{\pi}(s)$$</span></p>
  
  <p>where <span class="math-container">$\rho_{\pi}(s)$</span> is the distribution of states under policy <span class="math-container">$\pi$</span>. Note this makes no reference to <span class="math-container">$s'$</span> at all.</p>
  
  <p>However, there are ways that this could relate to the distribution of <span class="math-container">$s'$</span>. Probably the most direct relationship would be when there is a deterministic environment, thus knowing <span class="math-container">$s$</span> and <span class="math-container">$a$</span> would determine <span class="math-container">$s'$</span>. If, in addition to that, each <span class="math-container">$s'$</span> could <em>only</em> be reached from a single <span class="math-container">$(s,a)$</span> combination, then knowing <span class="math-container">$P_{sa}$</span> would also give you knowledge of <span class="math-container">$P_{s'}$</span> - this is not the same thing as the question is asking though.</p>
  
  <p>If you <em>did</em> mean the transition matrix <span class="math-container">$P_{ss'}^a$</span> instead in the question, then the answer is yes, because</p>
  
  <p><span class="math-container">$$P_{ss'}^a = \sum_r p(r,s'|s,a)$$</span></p>
  
  <blockquote>
    <p><strong>Question 2.</strong> What are the advantages of looking at <span class="math-container">$q_{\pi}(s,a)$</span> versus <span class="math-container">$v_{\pi}(s)$</span>?</p>
  </blockquote>
  
  <p>The main advantage is that you can derive a policy more easily from <span class="math-container">$q_{\pi}$</span>:</p>
  
  <p><span class="math-container">$$\pi'(s) = \text{argmax}_a q_{\pi}(s,a)$$</span></p>
  
  <p>Compare with deriving a policy using <span class="math-container">$v_{\pi}$</span>:</p>
  
  <p><span class="math-container">$$\pi'(s) = \text{argmax}_a \sum_{s',r} p(r, s'|s,a)(r + \gamma v_{\pi}(s'))$$</span></p>
  
  <p>Note that these policies are not necessarily the same as <span class="math-container">$\pi$</span> on which the <span class="math-container">$q$</span> or <span class="math-container">$v$</span> values are evaluated. In fact this is a common situation whilst searching for an optimal policy, and it is possible to show that <span class="math-container">$\pi'(s)$</span> will result in same or higher returns as <span class="math-container">$\pi(s)$</span> across all states . . . the proof of this is called the <a href="http://www.incompleteideas.net/book/ebook/node42.html" rel="nofollow noreferrer">policy improvement theorem</a>.</p>
  
  <p>The important thing about the first equation using <span class="math-container">$q$</span> is that it does not involve using the MDP model <span class="math-container">$p(r, s'|s,a)$</span> directly. This is the basis of model-free RL. Whilst the version using <span class="math-container">$v$</span> is more complex (taking more computation) and requires that you know <span class="math-container">$p(r,s'|s,a)$</span>.</p>
  
  <p>The main disadvantage of looking at <span class="math-container">$q_{\pi}(s,a)$</span> is that it has a larger dimension, it maps <span class="math-container">$S \times A \rightarrow \mathbb{R}$</span>, as opposed to using <span class="math-container">$v_{\pi}(s)$</span> which maps <span class="math-container">$S \rightarrow \mathbb{R}$</span>. So it can take longer to get good approximations of <span class="math-container">$q$</span> compared to <span class="math-container">$v$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-12T07:54:51.020Z
Answers.LastActivityDate: 2019-02-12T09:46:10.613Z
Answers.LastEditDate: 2019-02-12T09:46:10.613Z
Answers.UserDisplayName: Neil Slater
Body: <p>Suppose <span class="math-container">$G_t$</span>, the discounted return at time <span class="math-container">$t$</span> is defined as: <span class="math-container">$$ G_t \triangleq R_t+\gamma R_{t+1}+\gamma^{2}R_{t+2} + \cdots = \sum_{j=1}^{\infty} \gamma^{k}R_{t+k}$$</span></p>
  
  <p>where <span class="math-container">$R_t$</span> is the reward at time <span class="math-container">$t$</span> and <span class="math-container">$0 &lt; \gamma &lt; 1$</span> is a discount factor. Let the state-value function <span class="math-container">$v(s)$</span> be defined as: <span class="math-container">$$v_{\pi}(s) \triangleq \mathbb{E}[G_t|S_{t}=s]$$</span></p>
  
  <p>In other words, it is the expected discounted return given that we start in state <span class="math-container">$s$</span> with some policy <span class="math-container">$\pi$</span>. Then  <span class="math-container">$$v_{\pi}(s) = \mathbb{E}_{\pi}[R_t+\gamma G_{t+1}|S_{t}=s]$$</span></p>
  
  <p><span class="math-container">$$ = \sum_{a} \pi(a|s) \sum_{s',r} p(r,s'|s,a)[r+\ \gamma v_{\pi}(s')]$$</span></p>
  
  <blockquote>
    <p><strong>Question 1</strong>. Are the states <span class="math-container">$s'$</span> drawn from a from a joint probability distribution <span class="math-container">$P_{sa}$</span>? In other words, if you are in an
    initial state <span class="math-container">$s$</span>, take an action <span class="math-container">$\pi(s)$</span>, then <span class="math-container">$s'$</span> is the random
    state you would end up in according to the probability distribution
    <span class="math-container">$P_{sa}$</span>?</p>
  </blockquote>
  
  <p>Also let <span class="math-container">$q_{\pi}(s,a)$</span>, the action-value function be defined as: <span class="math-container">$$q_{\pi}(s,a) \triangleq \mathbb{E}_{\pi}[G_t|S_t = s, A_t = a]$$</span> </p>
  
  <p><span class="math-container">$$=\sum_{s',r} p(r,s'|s,a)[r+\ \gamma v_{\pi}(s')]$$</span></p>
  
  <blockquote>
    <p><strong>Question 2.</strong> What are the advantages of looking at <span class="math-container">$q_{\pi}(s,a)$</span> versus <span class="math-container">$v_{\pi}(s)$</span>?</p>
  </blockquote>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-17T18:13:50.170Z
Comments.Text: The one answer should be accepted, in my opinion. It completely and correctly answers the questions.
Comments.UserDisplayName: Philip Raeisghasem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-12T11:51:45.553Z
Comments.Text: You should have asked these two questions in separate posts, given that they are not very related.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><math><markov-decision-process>
Title: Is the next state drawn from the joint distribution of the previous state and action?
UserDisplayName: reinforcemenguy12
ThreadText: # Is the next state drawn from the joint distribution of the previous state and action?
  
  (Asked by: username_0 on 2019-02-12)
  
  Suppose $G\_t$, the discounted return at time $t$ is defined as: $$ G\_t \triangleq R\_t+\gamma R\_{t+1}+\gamma^{2}R\_{t+2} + \cdots = \sum\_{j=1}^{\infty} \gamma^{k}R\_{t+k}$$
  
  where $R\_t$ is the reward at time $t$ and $0 < \gamma < 1$ is a discount factor. Let the state-value function $v(s)$ be defined as: $$v\_{\pi}(s) \triangleq \mathbb{E}[G\_t|S\_{t}=s]$$
  
  In other words, it is the expected discounted return given that we start in state $s$ with some policy $\pi$. Then $$v\_{\pi}(s) = \mathbb{E}\_{\pi}[R\_t+\gamma G\_{t+1}|S\_{t}=s]$$
  
  $$ = \sum\_{a} \pi(a|s) \sum\_{s',r} p(r,s'|s,a)[r+\ \gamma v\_{\pi}(s')]$$
  
  > **Question 1**. Are the states $s'$ drawn from a from a joint probability distribution $P\_{sa}$? In other words, if you are in an
  > initial state $s$, take an action $\pi(s)$, then $s'$ is the random
  > state you would end up in according to the probability distribution
  > $P\_{sa}$?
  
  Also let $q\_{\pi}(s,a)$, the action-value function be defined as: $$q\_{\pi}(s,a) \triangleq \mathbb{E}\_{\pi}[G\_t|S\_t = s, A\_t = a]$$
  
  $$=\sum\_{s',r} p(r,s'|s,a)[r+\ \gamma v\_{\pi}(s')]$$
  
  > **Question 2.** What are the advantages of looking at $q\_{\pi}(s,a)$ versus $v\_{\pi}(s)$?
  
  **Tags:** reinforcement-learning, math, markov-decision-process
  > **Comments:**
  > **username_2**: You should have asked these two questions in separate posts, given that they are not very related.  
  > **username_1**: The one answer should be accepted, in my opinion. It completely and correctly answers the questions.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2019-02-12. Score: 2
  
  > **Question 1**. Are the states $s'$ drawn from a from a joint probability distribution $P\_{sa}$? In other words, if you are in an
  > initial state $s$, take an action $\pi(s)$, then $s'$ is the random
  > state you would end up in according to the probability distribution
  > $P\_{sa}$?
  
  This is tricky, because you don't show a definition of $P\_{sa}$. My first thought was that you meant the transition matrix $P\_{ss'}^a$, but that doesn't fit with the phrase *joint probability distribution*.
  
  If you really mean *joint probability distribution* then the answer is generally "no", because $P\_{sa}$ should be the probability of observing state $s$ and action $a$ when taking a random sampled time step:
  
  $$P\_{sa} = \pi(a|s)\rho\_{\pi}(s)$$
  
  where $\rho\_{\pi}(s)$ is the distribution of states under policy $\pi$. Note this makes no reference to $s'$ at all.
  
  However, there are ways that this could relate to the distribution of $s'$. Probably the most direct relationship would be when there is a deterministic environment, thus knowing $s$ and $a$ would determine $s'$. If, in addition to that, each $s'$ could *only* be reached from a single $(s,a)$ combination, then knowing $P\_{sa}$ would also give you knowledge of $P\_{s'}$ - this is not the same thing as the question is asking though.
  
  If you *did* mean the transition matrix $P\_{ss'}^a$ instead in the question, then the answer is yes, because
  
  $$P\_{ss'}^a = \sum\_r p(r,s'|s,a)$$
  
  > **Question 2.** What are the advantages of looking at $q\_{\pi}(s,a)$ versus $v\_{\pi}(s)$?
  
  The main advantage is that you can derive a policy more easily from $q\_{\pi}$:
  
  $$\pi'(s) = \text{argmax}\_a q\_{\pi}(s,a)$$
  
  Compare with deriving a policy using $v\_{\pi}$:
  
  $$\pi'(s) = \text{argmax}\_a \sum\_{s',r} p(r, s'|s,a)(r + \gamma v\_{\pi}(s'))$$
  
  Note that these policies are not necessarily the same as $\pi$ on which the $q$ or $v$ values are evaluated. In fact this is a common situation whilst searching for an optimal policy, and it is possible to show that $\pi'(s)$ will result in same or higher returns as $\pi(s)$ across all states . . . the proof of this is called the [policy improvement theorem](http://www.incompleteideas.net/book/ebook/node42.html).
  
  The important thing about the first equation using $q$ is that it does not involve using the MDP model $p(r, s'|s,a)$ directly. This is the basis of model-free RL. Whilst the version using $v$ is more complex (taking more computation) and requires that you know $p(r,s'|s,a)$.
  
  The main disadvantage of looking at $q\_{\pi}(s,a)$ is that it has a larger dimension, it maps $S \times A \rightarrow \mathbb{R}$, as opposed to using $v\_{\pi}(s)$ which maps $S \rightarrow \mathbb{R}$. So it can take longer to get good approximations of $q$ compared to $v$.
  
  
  ---
  
  