In reinforcement learning, what is the formal definition of the symbols $S_t$ and $A_t$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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