1
$\begingroup$

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)$?

$\endgroup$
2
  • $\begingroup$ You should have asked these two questions in separate posts, given that they are not very related. $\endgroup$
    – nbro
    Feb 12, 2019 at 11:51
  • $\begingroup$ The one answer should be accepted, in my opinion. It completely and correctly answers the questions. $\endgroup$ Mar 17, 2019 at 18:13

1 Answer 1

1
$\begingroup$

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.

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .