I was following the reinforcement learning lecture notes on CS229. On page 3 they have the equation for the expectation of the total pay-off:
$$ \mathbb{E}[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots] $$
However they do not specify clearly to me, what the expectation is over. i.e. what is the distribution exactly over which the expectation is being evaluated? I am looking for a mathematically precise answer, not for conceptual answer. I literally want to see the factorization of the distribution. Also, it's super important that it's consistent with the Bellman equation on page 3:
$$ V^{\pi}(s) = R(s) + \gamma \sum_{s' \in S} P_{s\pi(s)}(s') V^{\pi}(s') $$
i.e. that the suggested factorization indeed yields that equation (if we wanted it).
I do understand conceptually that is over the visited states (and actions) that our systems goes through. However, what exactly does the distribution for that look like? Is it consistent with Bellman's equation?
Anyway, these are my thoughts so far but I have not really got an answer which I am 100% satisfied.
We know that a way to do reinforcement learning is in the framework of Markov Decision Processes. One of the things in the tuple specifying an MDP is the transition probabilities. In Andrew Ng's notation they are:
$$P_{sa}(s') = Pr[S_{t} = s' \mid S_{t-1} = s, A_{t-1} = a]$$
Which means the transition probability is a distribution over the next time step state $S_t$, depending on which was your previous state $S_{t-1}$ and action at that time step $A_{t-1}$. It's clear that $S_t$ is a r.v. as it's random where to transition by the framework of the problem. The action is actually also a r.v. The reason is because the action, even when we know a specific policy, since it depends on a random quantity (namely the random state) then the actions have to be random according to the states that our system explores.
I don't like Andrew's notation and I want to use the following:
$$P_{s|sa}(s'|s,a) = Pr[S_{t} = s' \mid S_{t-1} = s, A_{t-1} = a]$$
Notice that we can re-write Bellman's equation as:
$$ V^{\pi}(s) = R(s) + \gamma \sum_{s' \in S} P_{s | s \pi(s)}(s' \mid s, \pi(s) ) V^{\pi}(s') $$
One natural question could be, why is it not dependent on all the previous states? And the answer is because we are assuming the Markov property. Due to this reasoning it occurred to me to try to write down a probabilistic graphical model for this. Let me depict to you the local Markov property:
taking into account all states in the process, we get a complete picture of what the correct graphical model:
If indeed that is the distribution of such a process then I conjecture that the distribution should factorizes as follows:
$$Pr[ \vec{S} = \vec{s} , \vec{A} = \vec{a} ] = p_{s}(s_0) \prod^{\infty}_{t=1} p_{s|s,a}(s_t|s_{t-1}, a_{t-1}) \prod^{\infty}_{t=0} p_{a | s} (a_t | s_t)$$
now notice that given a specific policy $\pi(s)$ then $p_{a |s}(a_t | s_t)$ is trivial to specify. Namely it's:
$$ p_{s |a}(a_t | s_t) = \left\{ \begin{array}{lr} 1 & a_t = \pi(s_t)\\ 0 & \text{otherwise} \end{array} \right. $$
i.e. intuitively it's saying, the next action is dictated deterministically by the policy function. If the policy function says that at sate $s_t$ do $\pi(s_t)$, then we do that action exact action $\pi(s_t)$. So given we are at state $s_t$, if the policy function says move north, or whatever $\pi(s_t)$ is for that state, then we do that action.
Now that we finally have some expression for the probability distribution, I believe that's the distribution which the expectation is being taken over. Is that correct? I've been having problems checking if it's indeed consistent with Bellman's equation.
