I am studying Sutton&Barto's book Reinforcement Learning: An introduction, available for free. On page 80 is given an algorithm called Policy Iteration, this algorithm has a step called Policy Improvement. My understanding is that the policy is assumed to be deterministic; that is, for every feasible $s$ there exists an $a$ such that $\mathbb{P}(A_t = a\mid S_t =s) = 1$. In the step Policy Improvement one has to determine $$ \text{arg max}_a \sum_{s',r} p(s',r\mid s,a)\cdot (r + \gamma \cdot V(s')), $$ where the expression $p(s',r\mid s,a)$ is equivalent to $\mathbb{P}(S_t =s',R_t=r\mid S_{t-1} = s, A_{t-1} = a )$. However, the latter expression can be re-expressed as follows \begin{align} \mathbb{P}(S_t =s',R_t=r\mid S_{t-1} = s, A_{t-1} = a )&=\frac{\mathbb{P}(S_t =s',R_t=r, S_{t-1} = s, A_{t-1} = a)}{\mathbb{P}(S_{t-1} = s, A_{t-1} = a)}\\[1em] &=\frac{\mathbb{P}(S_t =s',R_t=r, S_{t-1} = s, A_{t-1} = a)}{\mathbb{P}(A_{t-1} = a\mid S_{t-1} = s)\cdot \mathbb{P}(S_{t-1} = s)} \end{align} The probability $\mathbb{P}(A_t = a\mid S_t =s)$ appears in the denominator, hence $p(\cdot,\cdot\mid s,a)$ is well-defined for a single pair $(s,a) = (s,\pi(s))$? This means that the argmax should return $\pi(a)$? What am I missing?


1 Answer 1


What am I missing?

When $S_{t-1} = s, A_{t-1} = a$ is a condition as in $\mathbb{P}(X|S_{t-1} = s, A_{t-1}=a)$, it does not mean that there are any expectations or rules regarding distributions $S_{t-1}$ or $A_{t-1}$. By supplying them as a conditional in the expression, you are removing considerations of what is driving them.

Inserting $\mathbb{P}(S_{t-1} = s, A_{t-1} = a)$ into your analysis of $p(s', r|s,a)$ is making an assumption that these random variables are drawn from a distribution that you care about. You then end up constructing a circular argument, because you have implictly decided that you are drawing the distribution of $A_{t-1}$ based on the policy.

However, the update rule does not refer to how the current policy affects the initial state or action. There is no implied distribution of $S_{t-1}$ or $A_{t-1}$, they are just set arbitrarily to each state and action in the whole space as required to resolve the argmax. In the policy evaluation and policy update steps of policy iteration, the state and action being evaluated are not random variables, the notation used is partially hiding that.

In some calculations you may care about the distribution of $S_{t-1}$ and $A_{t-1}$, but it is common in RL to not make use of the distribution of these terms when they are set to fixed values in order to calculate a specific value update.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.