1
$\begingroup$

This is a follow-up on this question: In reinforcement learning, what is the formal definition of the symbols $S_t$ and $A_t$?

I want to understand the construction and/or definition of the random variables $S_t$ (resembling the state at time $t$) and $A_t$ (action that we take at time $t$) in Reinforcement Learning. For example:

Why can we evaluate $p(s_{t+1}|s_t, a_t)$ to the transition matrix that was given as input?

Attempt:

1) Just assume that there are random variables $S_t, A_t$ and that they satisfy some relations. For example, assume that $p(s_{t+1}|s_t, a_t)$ actually does not depend on $t$, i.e. for $t' \neq t$, $p(s_{t+1}|s_t, a_t) = p(s_{t'+1}|s_{t'}, a_{t'})$ and all those expressions become the input state transition matrix. This is a little unsatisfactory because there is a more "natural" way to do it (see below).

2) Follow the natural description of MDPs (plus a policy): We generate the random variables $A_t, S_t$ by tracing the policy.

Input: A finite set of states $S = \{s_1, ..., s_n\}$ and a finite set of actions $A = \{a_1, ..., a_m\}$ and two functions \begin{align*} \Delta^d : S \times A \times S &\to [0,1] \\ \pi^d : S \times A & \to [0,1] \end{align*} such that $$\forall a, s ~~ \sum_{s' \in S} \Delta^d(s, a, s') = 1$$ (i.e. given a concrete state current $s$ and action $a$, $\Delta^d$ must give a probability distribution on the potential states $s'$ to go to) and $$\forall s ~~~ \sum_{a \in A} \pi^d(s, a) = 1$$ (i.e. given a concrete state, $\pi^d$ must give a probability distribution on possible actions to take). I call them $\Delta^d$ and $\pi^d$ because these are just completely deterministic input numbers, NOT random variables. We assume that there are corresponding random variables \begin{align*} \Delta : S \times A \times \Omega &\to S \\ \pi : S \times \Omega & \to A \end{align*} such that for all $a,s,s'$ \begin{align*} P[\Delta(s,a,\cdot) = s'] &= \Delta^d(s,a,s')\\ P[\pi(s,\cdot)=a] &= \pi^d(s,a) \end{align*} i.e. $\pi$ and $\Delta$ follow the distributions given by $\pi^d$ and $\Delta^d$. Now the definition of the random variables $S_t, A_t$ is recursive but straightforward: \begin{align*} S_t(\omega) &= \Delta(S_{t-1}(\omega), A_{t-1}(\omega), \omega) \\ A_t(\omega) &= \pi(S_{t-1}(\omega), \omega) \end{align*} This is what I mean by natural: The next state is sampled according to the random variable $\Delta$ depending on the currently sampled state and the currently sampled action. The next action is sampled as described by the policy random variable. This is what everybody "describes" informal (not formal though) in their notes on MDPs and/or RL.

Question: Why is $P[S_t=s_t|S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}] = \Delta^d(s_{s-t}, a_{t-1}, a_t)$ for all values $s_t, s_{t-1}, a_{t-1}$?

All I get is \begin{align*} P[S_t=s_t|S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}] &= \frac{P[S_t=s_t,S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}]}{P[S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}]} \\ &= \frac{P[\Delta(s_{t-1}, a_{t-1}, \omega)=s_t,S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}]}{P[S_{t-1}=s_{t-1},A_{t-1}=a_{t-1}]} \end{align*}

and then I am stuck. We should also expect that $P[A_t=a_t|S_t=s_t] = \pi^d(s_t, a_t)$ but I am equally unable to prove this...

Can somebody clear this mess up?

$\endgroup$
  • $\begingroup$ In the question near the end of your post, I assume you mean $\Delta^d(s_{t-1}, a_{t-1}, s_t)$? Instead of $\Delta^d(s_{s-t}, a_{t-1}, a_t)$, which doesn't really seem to be correct? Either way, I'd argue that that equation which you're trying to prove doesn't necessarily follow from any of the previous statements. That equation which you're asking to prove should actually be at the top of your post, and it's one of the "assumptions" we start with, that equation holds by definition, it's the definition of the transition function $\Delta^d$ (it appears to be undefined to me in your post) $\endgroup$ – Dennis Soemers Jan 27 '18 at 11:34
  • $\begingroup$ @Dennis Soemers: Oops, of course you are right, I’ll edit asap. Conserning your comment: if you take this as an assumption then you take road #1 and you should then explain why we should trust in a model that makes soo many assumptions when it is possible to construct these variables that naturally resemble what was described informally beforehand... don’t you agree? $\endgroup$ – Fabian Werner Jan 27 '18 at 22:21
  • $\begingroup$ Well, they're certainly not uncommon assumptions. It's just assuming the Markov property holds, and assuming the state-transition function is stationary (doesn't change by itself over time). In practice, RL is still gonna work fine if these assumptions are slightly violated (probably not if they're ''heavily violated''). In theory, you need them if you want to be able to prove just about anything for RL though (like, convergence proofs for tabular RL algorithms). $\endgroup$ – Dennis Soemers Jan 28 '18 at 9:52
  • $\begingroup$ Also, keep in mind that they're not as restrictive as they might appear at first glance, since there are basically no limitations on what your state representation has to look like. If the current time $t$ is really really important, you could simply include it as an additional variable in your state representation (which is obviously going to lead to a significantly more complex learning problem in practice, but doesn't change anything in theory other than the size of your state space) $\endgroup$ – Dennis Soemers Jan 28 '18 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.