5
$\begingroup$

In both the reinforcement learning course given by David Silver and the latest draft of Richard S. Sutton's RL book what is the formal definition of the symbols $S_t$ and $A_t$?

Do these definitions depend on the policy being used until time-step $t$?


Some context for the question:

I realize that this question might seem trivial, since the authors explicitly define these variables in their textbook/lecture. However, I'm currently trying to make sense of their definitions, but no interpretation I think of seems to yield a coherent/consistent notation. What follows is my line of thought, showing which interpretations I tried and why they seem to be inconsistent.

These authors seem to define the following symbols like so:

$$S_t\triangleq\text{The state we visit at time-step }t.$$ $$A_t\triangleq\text{The action we take at time-step }t.$$

Where both $S_t$ and $A_t$ are commonly treated as random variables.

However, what confuses me is that in order to properly define $S_t$ for $t>0$ it seems necessary to first define all the $S_i,A_i$, for $0\leq i <t$. Hence, it seems that the definition of $S_t$ only makes sense if we specify with which policy we're choosing our actions at all the time-steps before we reached time-step $t$.

This is already ambiguous, and personally confusing, since the symbol $S_t$ has no mention whatsoever to which policy was used to sample the actions until that point. For example, the same symbol $S_5$ can represent completely different random variables, if they're specified in different contexts with different policies being used (or different starting states).

This ambiguity didn't strike me as very impairing, since I thought one could always use, say, a superscript to indicate the policy being used at all the previous time-steps, e.g. $S_5^\pi$. Also, for most of the discussions it was very clear which policy was being used (and almost as clear what was the starting state), so it seemed harmless to drop the extra notation.

However, I later encountered definitions like, for instance, the action-value function of a state action pair: $$ Q_\pi(s,a)=\mathbb E_\pi[G_t | S_t=s, A_t=a] $$

This is supposed to be defined for all legal actions $a$ in state $s$. However, if I interpret $S_t$ as $S_t^\pi$ and $A_t$ as $A_t^\pi$, respectively, this definition seems to break down when $a$ is an action that policy $\pi$ would never choose, or $s$ is an unreachable state given policy $\pi$ and some starting state $s_0$ (since we'll be conditioning the expectation on an impossible event). So it seems that these authors are not simply dropping the superscript I mentioned before, and instead $S_t$ and $A_t$ have some other definition.

$\endgroup$
3
$\begingroup$

In the summary of notation (page xvi) of Sutton and Barto's book, they define $S_t$ as:

state at time $t$, typically due, stochastically, to $S_{t-1}$ and $A_{t-1}$

This is similar to what you observed:

However, what confuses me is that in order to properly define $S_t$ for $t>0$ it seems necessary to first define all the $S_i, A_i$, for $0≤i<t$.

The main difference between the book's definition and your observation is that they only take $i = t-1$, not $0 \leq i < t$. Only that single prior step is sufficient due to the Markov property which is basically assumed to hold throughout the entire book, we're almost always talking about Markov Decision Processes.

Another difference is that $S_t$ does not require $S_{t-1}$ and $A_{t-1}$ to be well-defined necessarily, those values only happen to typically explain how we ended up where we are now ($S_t$). The obvious exception is the initial state $S_0$, which we simply end up in... out of the blue kind of.

Hence, it seems that the definition of $S_t$ only makes sense if we specify with which policy we're choosing our actions at all the time-steps before we reached time-step $t$.

This is not necessary. An agent could theoretically change their policies during an episode too. In fact, as a random variable, $S_t$ doesn't even really represent just a single value. It's a symbol that we use to denote the state that we happen to be in during some episode at time $t$, without caring about what we did before that or plan to do after it. See the wikipedia page on random variables.


\begin{equation} Q_\pi (s,a) = \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right] \end{equation}

This equation simply says that the value of $Q_\pi$ is equal to the returns that we expect to obtain if:

  1. we start following policy $\pi$ from now on (it doesn't matter which policy we've been following up until now)
  2. we happen to currently be in state $s$ (this is a specific value, this is no longer a random variable), and we happen to have chosen to select action $a$.

Note how the definition does not depend directly on what policy we've been using in the past. It only depends on the policy we've been using in the past indirectly, in the sense that that explains how we may have ended up in state $S_t = s$. But we do not require knowledge of our past policy to properly define anything in this equation, and that past policy will often not even be the only requirement for a complete explanation of how we ended up where we happen to be now. For example, in nondeterministic environments, we may also require knowledge of a random seed and a Random Number Generator to completely explain why we are where we are now. But the definition of the equation does not rely on the ability to explain this. We just take for granted that, at time $t$, we are in state $S_t = s$, and the equation is well-defined from there.

This equation happens to rely on the future policy $\pi$, but that may be a different policy from our past policy, and this reliance is denoted by the subscript on $Q_\pi$ and $\mathbb{E}_\pi$.

$\endgroup$
  • $\begingroup$ Hey Dennis, thanks for your time! However, I'm having some trouble digesting your answer: - You say "Only that single prior step is sufficient due to the Markov property which is basically assumed to hold throughout the entire book (...)". I don't see how the Markov property plays any role in this. Defining $S_t$ in terms of $S_{t-1}$ and $A_{t-1}$ is ok for me, but then you need to define $S_{t-1}$, which will make you have to define $S_{t-2}$ and $A_{t-2}$, and so forth, until $S_0$. $\endgroup$ – JLagana Jan 25 '18 at 7:06
  • $\begingroup$ - You also say "Another difference is that $S_t$ does not require $S_{t−1}$ and $A_{t−1}$ to be well-defined necessarily". To discuss this, I'd like to give a more concrete example: let's say I give you the full MDP dynamics (the entire tuple that defines it, including transition probabilities, reward function, etc). I argue that with this information only, $S_t$ is not well-defined. Or can you specify its probability distribution using only the information given? I think it's also necessary to completely specify the distribution (or the values) of $S_{t-1}$ and $A_{t-1}$. $\endgroup$ – JLagana Jan 25 '18 at 7:10
  • $\begingroup$ @JLagana $S_t$ is just a random variable, it's not a specific value. It's the variable we always use to denote ''the state we happen to be in at time $t$''. So yes, we don't know the exact value we assign to that state until we've actually reached that point in time, but the variable that will ''contain'' that value is already well-defined, and we can already use it in the definition of various equations (we just can't compute exact numbers yet, since we can't replace the random variables with actual values/numbers $\endgroup$ – Dennis Soemers Jan 25 '18 at 9:17
  • $\begingroup$ The distinction between random variables on one hand, and values on the other, is important $\endgroup$ – Dennis Soemers Jan 25 '18 at 9:18
  • $\begingroup$ Hey again. I think I have the distinction between random variable and values very clear already. When I say that $S_t$ is not well-defined I don't mean we don't know the value that this random variable will actually take when we sample from the MDP. Instead, I mean that the probability distribution function of this random variable is not well-defined. $\endgroup$ – JLagana Jan 25 '18 at 12:27
1
$\begingroup$

I came up with one possible interpretation of these symbols that seem to be consistent with all the material I've seen so far in these courses.

As pointed out in Dennis Soemers' answer, Sutton's book define $S_t$ as:

state at time $t$, typically due, stochastically, to $S_{t−1}$ and $A_{t−1}$

The "typically due" led me to think that perhaps $S_t$ doesn't refer to the same thing in all contexts. Maybe, $S_t$ in one context is actually a random variable, with a distribution that depends on $S_{t-1}$ and $A_{t-1}$. Then, in another context (or in the same context but for other $S_i$, $i\neq j$), it is a deterministic quantity, already specified for us.

Which leads me to interpret $S_t$ as simply a placeholder symbol. With this I mean that the symbol $S_t$ doesn't mean much without a context. The context then specifies if that state is supposed to be random, with a distribution conditioned on the state and action at the previous time step, or if it is a deterministic value. Furthermore, given a context, it's not necessary for all $S_i$ to share the same nature, some can be random and some can be deterministic (although the case where more than one state in the chain is deterministic is probably meaningless$^{[1] }$).

Hence, when we write things like

$$ Q_\pi(s,a)=\mathbb E_\pi[G_t | S_t=s, A_t=a] ~,$$

we mean that $S_t$ and $A_t$ are not random (not even random variables that we have observed their values). Instead, they are simply deterministic values given by us. However, the subscript $\pi$ in the expectation is then the context that defines all the $S_i$ and $A_i$ for $i>t$ to be random, with distributions that depend on the previous state and action, or the policy $\pi$ and the previous state, respectively. Whether or not the subscript $\pi$ also determines the nature of all the $S_i$, $A_i$ for $i<t$ seems irrelevant, since (because of its definition) the quantity $G_t$ won't depend on them (but I would argue it doesn't, otherwise $S_t$ shouldn't be deterministic).

This previous equation is in some sense asking: "What is the expected value of $G_t$, in the context that we start at state $s$, take the action $a$, and from that point onward we sample states and returns from the MDP model we defined somewhere else, and sample actions from our policy $\pi$.

I think it's important to repeat that in that equation $S_t$ and $A_t$ are not (at least according to what I could come up as a sensible interpretation of this notation) random variables! They are not random variables that we have somehow observed their values. Otherwise, this equation would suffer from the problem I described earlier: if policy $\pi$ never chooses action $a$, or never reaches state $s$, then we would be conditioning on impossible events. Instead, they're deterministic quantities. I would even go as far as advocate towards using the notation:

$$ Q_\pi(s,a)=\mathbb E_\pi[G_t] \quad,\quad S_t=s \text{ and } A_t=a$$

instead, to clear up any possible confusion that these variables might be random.

[1]: Note that this is fundamentally different from the case where these states are all random, but we have observed the value of them.

$\endgroup$
  • $\begingroup$ Your interpretation of $S_t$ as a placeholder symbol seems correct, but that's kind of what "random variable" means. It's always a random variable. Random variables can be "deterministic" too, in that it's possible for all the probability mass to be on only a single value, they're still random variables though. See for example the first paragraph here: en.wikipedia.org/wiki/Degenerate_distribution $\endgroup$ – Dennis Soemers Jan 26 '18 at 10:00
  • $\begingroup$ $S_t$ and $A_t$ very much still are random variables in that equation, but in the equation we indeed fix their values to $s$ and $a$. That's because, when we use that equation, we specifically want to ask "what return are we going to get if we choose action $a$, given that we have observed ourselves to be in state $s$ right now?" We will often repeat that question for every action $a$ that is legal in the current state $s$, and then select the action that gives us the highest $Q$-value. So $a$ can very well be an action that would never be picked by policy $\pi$, and that's no problem at all. $\endgroup$ – Dennis Soemers Jan 26 '18 at 10:03
  • $\begingroup$ When, in the equation, we say "$S_t = s$", the symbol $S_t$ is still the random variable as originally defined. However, by adding "$= s$" after it, we specify that we fill in a specific value for the random variable. In the case of $S_t = s$, we fill in that particular value because we have observed it, whereas in the case of $A_t = a$, we fill in that particular value because we want to make a prediction for it, "what would happen if ...?" That last thing will generally be repeated in a loop for all possible $a$, to make predictions for all of them $\endgroup$ – Dennis Soemers Jan 26 '18 at 10:07
  • $\begingroup$ In that equation, if you regard $A_t$ as a random variable, then what is its distribution? Is it $\pi(\cdot | S_t)$? If it is, assume that for this policy $\pi$, $\pi(a_1|s_0)=0$. Then, when defining the value of $Q_\pi(s_0,a_1)$, you'll be forced to take the expected value of $G_t$ conditioned on an impossible event, namely $A_t=a_1$. What would that value be? $\endgroup$ – JLagana Jan 26 '18 at 10:35
  • $\begingroup$ It seems impossible to me to take the expected value of a random variable conditioned on an impossible event. Since conditioning on an impossible event $B$ would give you a new sample space in which all the outcomes are $\in B$, but all of them initially had probability 0. How can you renormalize the distribution to this new sample space? $\endgroup$ – JLagana Jan 26 '18 at 10:37
1
$\begingroup$

I am scratching my head about this as well... In principal what follows is more of a comment than an answer. Everything I say is just guessing because I have neither read a formal description yet.

I think that most applied statisticians have a very deep understanding what they are doing but the do not allow the rest of the world to understand it properly because, as you said: apparently they like it very much to confuse random variables, values, measures, distributions, densities and so on. Nevertheless: in all cases there is a clean, mathematical, unambigous interpretation behind the symbols: We start with a probability space $\Omega$ (with some $\sigma$-algebra and some measure $P$ on it). In Markov processes we have some easy 'input' that we are given and we need to interpret and understand it. The input is a (for now finite) set of possible state values $S = \{s_1, ..., s_n\}$ and a (for now finite) set of actions $A = \{a_1, ..., a_m\}$ and a deterministic transition function $\Delta : S \times A \to S$ that, when evaluated like so $\Delta(s,a)$ giving us a completely fixed description of what happens (of what is the next state) when we are in state $s$ and take action $a$. Nothing probability related so far. The first thing that people seem to have confusion about is the policy (is it random or not?). The input we are given is what they call $\pi : S \times A \to [0,1]$ such that for all $s$ we have $\sum_{a \in A} \pi(s,a) = 1$ The first mistake is to say that $\pi$ is some sort of random or random variable. Up to now we can read that as a matrix of size $|S| \times |A|$ such that the row sums are $1$. Absolutely deterministic. I think what they actually mean is the following: We are given a whole set of random variables $(\alpha_s)_{s \in S} : \Omega \to A$ that are responsible for sampling the action that we take. We will write this as $\alpha(s, \omega) = \alpha_s(\omega)$. Now what their $\pi$ means is nothing else but $$P[\alpha(s, \omega) = a] = \pi(s, a)$$ i.e. their $\pi$ gives the distribution of the variables $\alpha_s$. I think that you are absolutely right in saying that we must define the random variables $S_t$ and $A_t$ now recursively: $$ A_t(\omega) = \alpha(S_t(\omega), \omega) $$ i.e. the action we take at time $t$ is defined by what the policy "randomly" choses when inserting the current state $s_t = S_t(\omega)$ and the general information $\omega$. $S_t$ in turn is defined as $$S_t(\omega) = \Delta(S_{t-1}(\omega), A_{t-1}(\omega))$$ i.e. the state $s_t$ at time $t$ is the one that we get by the transition function $\Delta$ when evaluated at the state $s_{t-1} = S_{t-1}(\omega)$ and the action $a_{t-1} = A_{t-1}(\omega)$ that we took before.

The mere fact that this definition is recursive is not too bad: On the one hand this seems to be the nature of the RL game: take the current state and do something with it in order to get to the next state. In mathematics in general there are many recursive things: the faculty function, the Fibonacci numbers, ...

Now the only question that remains is how to define $S_0$! However, this is something that must come from the input: When considering a Markov process we are usually given a finite state graph. When unflating that and doing probability theory with it we always end up in terms like $$p(s_{t}|s_{t-1}) \cdot ... \cdot p(s_1|s_0) \cdot p(s_0)$$ i.e. that tiny little $p(s_0)$ stays there no matter what you do. I think it is something the user must specify (like a prior in the Bayesian setup). However, as we gain more and more information with many states and the current situation only depends on the very last state and not the thing we did initially, I guess that it is not so important how to define $S_0$ so I think it is fine to start defining $S_0$ to be just some uniformly distributed random variable over the states. Or maybe it is like this: The thing we want to do in the end is to compare policies (in order to get the best one). When comparing them I think that $p(s_0)$ has little influence. For example, if you get some KPI that somehow needs to divide the expressions above for different policies then the $p(s_0)$ cancels out...

Does that make sense?

edit: Now thinking about what you said about the deterministic policy and the "impossible" event in the comments...

$\endgroup$
  • $\begingroup$ Hey Fabian, thank you for your time! Indeed, I think we agree with many things. However, I'm having trouble completely understanding your answer. Can you tell me if you agree with my statement that in the state-action value function definition, $S_t$ and $A_t$ are not random? $\endgroup$ – JLagana Jan 26 '18 at 14:09
  • $\begingroup$ @JLagana: Humm, we can give a 'natural' definition and people write it into expected contionals... that must mean that these are normal random variables... otherwise we could never write these expressions... but as stated: I am unsure how to do it cleanly :-( $\endgroup$ – Fabian Werner Jan 26 '18 at 14:13
  • $\begingroup$ well, just because someone wrote it into expected conditionals doesn't make it random. The person could be abusing notation, for instance. $\endgroup$ – JLagana Jan 26 '18 at 14:20
  • $\begingroup$ @JLagana totally agreed but there is a difference in abusing the notation like this: $P[X=x]$ <-> $p(x)$ and abusing notation in an expected conditional... at least I cannot imagine anything else to write there as a replacement. Also my (little amount of) experience with applied stats is that one has to think hard but this is then rewarded with a deeper understanding because there always is a clean probabilistic model behind it. $\endgroup$ – Fabian Werner Jan 26 '18 at 14:25

Your Answer

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

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