Does this notation in the context of reinforcement learning have an unambiguous measure-theoretic interpretation? In the context of reinforcement learning, I have seen the formula
$$V^\pi(s)=\mathbb E_{\tau \sim \pi}[R(\tau)|s_0=s]$$
and
$$V^\pi(s)=\mathbb E_{a\sim \pi}[Q^\pi(s,a)]$$
Does this notation have an exact meaning in the context of the Kolmogorov formalization of probability theory? (where we have a probability space $(\Omega,\sigma,\mathbb P)$, and where variables like $a$, $s$, and $\tau$ would be "random variables", i.e. functions from $\Omega$ to some space).
The reason it conflicts somewhat with what I'm used to, is that it assumes a "distribution" $\pi$, rather than an underlying probability space.
EDIT: after some answers: I can see how either onr of these equations can be seen wjthin the context of a probability space: in the first, take $\tau$ to be an element of $\Omega$, and in the second, take $a$. I can't see how a single probability space can simultaneously make sense of both of them.
 A: So, this is my answer on the clean description of Reinforcement Learning. There is no 'interpretation' only variations of this clean, mathematical description (because 'interpretation' creates ambiguity and we actually want to speak about the same thing when we say 'reward', 'state', ... but many applied people do not seem to agree with me on that point and seem to prefer just skipping questions like ''What do you mean by $v^\pi(s)$ if $p(s)=0$?'' :-))
Theorem 1 Assume we are given any index set $T$, a set of sets with sigma algebras $(\mathcal{X}_t, \mathcal{C}_t)$ and a set of measurable density functions $(h_t)_{t \in T}$, i.e. $h_t : \mathcal{X}_t \to \mathbb{R}$ is such that $h_t(x) \geq 0$ for all $x$ and $\int_{\mathcal{X}_t} h_t(x) d\mu_t(x) = 1$ with respect to some fixed, natural measure $\mu_t$. Then we can construct a single probability space $(\Omega, \mathcal{A}, P)$ and a set of independent random variables $(X_t)_{t \in T}$ such that $X_t$ maps from $\Omega$ into $\mathcal{X}_t$ and such that $X_t$ has density $h_t$.
Usually there are only two cases, either $\mu_t$ is the Lebesgue measure, $\mathcal{X}_t$ is an interval $(a,b)$ or all all of $\mathbb{R}$ and $X_t$ is a continuous random variable (for example, normally distributed, beta distributed, ...) or $\mu_t$ is the counting measure and $\mathcal{X}_t$ is discrete, i.e. can be understood as either $\mathbb{N}_0$ or a finite subset thereof.
Now in order to come up with the random variables and their description we need Markov Decision Autotmata (MDA) and Markov Decision Processes (MDP) and their relation. Imagine it like this: an MDA describes the problem (i.e. the environment the agent moves in, the transition probabilities, ...) and each MDP describes a single solution with respect to one policy.
Definition 2: A Markov Decision Automata is a touple $(S,A,\mathcal{R},\Delta,\text{rew})$ consisting of sets $S,A, \mathcal{R}$ ($S$ = set of states, $A$ = set of actions, $\mathcal{R}$=set from which the rewards come from) and two functions $\Delta : S \times S \times A \mapsto [0,1]$ and $\text{rew} : \mathcal{R} \times S \times A \times A \mapsto [0,1]$ such that


*

*For each $s,a$, the function $s' \mapsto \Delta(s';s,a)$ is a density

*For each $s',a,s$ the function $r \mapsto \text{rew}(r;s',a,s)$ is a density


We call this an automata because we imagine each state $s \in S$ as a node and attached to each pair of nodes $s, s'$ there are multiple adges leading from $s$ to $s'$ and each edge carries an action $a \in A$ and the number $\Delta(s';s,a)$ and the function $\text{rew}(\cdot;s',a,s)$.
$\Delta$ gives the probability of going from state $s$ to state $s'$ using the action $a$. $\text{rew}(\cdot;s',a,s)$ gives the received reward when moving from $s$ to $s'$ using action $a$.
The MDA for playing the game Tic Tac Toe could look like this for example:

So we start at the empty playing field and then we could select 'TopLeft' (TL) as an action to put our sign 'x'. The other player has a 'choose arbitrarily' playing strategy so the other player reacts with putting his character 'o' to each possible field with an equal probability of $1/8$.
This already tells us why we actually need to model the 'next state' in a probabilistic way: We need this to model the other players behaviour (which we cannot forsee). There are other examples like 'icy lake' (the agent moves on the surface of an icy lake and once chosen right, it goes right with a small probability even if it selects another direction to go to [since the surface is slippy]).
Definition 3: A Markov Decision Process is a sequence of random variables $(R_t, A_t, S_t)_{t \in \mathbb{N}_0}$ such that ...


*

*for each $t$, the finite touple $(S_{t+1}, (R_v, A_v, S_v)_{v=0,...,t})$ has a common density

*the densities $f_{S_{t+1}|A_t,S_t}$, $f_{R_t|S_{t+1},A_t,S_t}$ and $f_{A_t|S_t}$ do not depend on $t$, i.e. if $q \in \mathbb{N}_0$ then 


*

*$f_{S_{t+1}|A_t,S_t}(s'|a,s) = f_{S_{q+1}|A_q,S_q}(s'|a,s)$

*$f_{R_t|S_{t+1},A_t,S_t}(r|s',a,s) = f_{R_q|S_{q+1},A_q,S_q}(r|s',a,s)$

*$f_{A_t|S_t}(a|s) = f_{A_q|S_q}(a|s)$


*the Markov property: $f_{S_{t+1},A_t,R_t|*} = f_{S_{t+1},A_t,R_t|S_t}$ where we may replace $*$ by any subcollection of random variables within $(S_t, (R_v,A_v,S_v)_{v=0,...,t-1})$, i.e. the next things that happen (state, action and reward) exclusively depend on the current state and on nothing else in the past history.


The connection between those two is as follows: Given a MDA and a fixed 'initial' distribution $I$ for $S_0$ and a fixed policy $\pi$, i.e. a function $\pi : A \times S \mapsto [0,1]$ such that for every $s \in S$, $\int_A \pi(a;s) da = 1$, we can actually explicitly create an MDP using the following strategy:
We use Thm 1 multiple times to create a common probability space with independent random variables $S_0, P_{t,s} R_{t,s',a,s}, D_{t,a,s}$ for all possible values of $t,s',s,a$ such that


*

*$S_0$ maps to $S$ and $S_0 \sim I$

*$P_{t,s}$ maps to $A$ and $P_{t,s} \sim \pi(\cdot;s)$

*$D_{t,a,s}$ maps to $S$ and $D_{t,a,s} \sim \Delta(\cdot;s,a)$

*$R_{t,s',a,s}$ maps to $\mathcal{R}$ and $R_{t,s',a,s} \sim \text{rew}(\cdot;s',a,s)$
where $X \sim f$ means that the random variable $X$ has density $f$. We define the MDP in the following recursive way: $S_0$ is already defined. Assume that $S_t$ is already defined then
 - $A_t(\omega) := P_{t,S_t(\omega)}(\omega)$
 - $S_{t+1}(\omega) := D_{t,A_t(\omega),S_t(\omega)}(\omega)$
 - $R_{t}(\omega) := R_{t,S_{t+1}(\omega), A_t(\omega),S_t(\omega)}(\omega)$
Although we defined the random variables in this weird way and although we have this 'double $\omega$' thing going on we can actually prove:
Theorem 4: The collection of random variables $(R_t,A_t,S_t)$ as defined above is an MDP.
Proof: Exercise. If you don't see how it works it has been done here for the simpler case of Markov Automata (without the rewards and so on but it works in the same way).
In one sentence: MDA describes the environment / the problem setup and each solution (namely a policy) gives rise to an MDP that we can then use in a clean measure theoretic way in order to define things like $v^\pi(s) = E[\sum \gamma^k R_k | S_0=s]$ and so forth.
In one picture: One MDA gives rise to many MDPs:

Final notes:


*

*To make the connection between MDA and MDP somewhat more visible: Let us write $p(...)$ for the densities, i.e. $p(a_t) = f_{A_t}(a_t)$ and so forth then if we create the random variables as above then $p(a_t|s_t) = \pi(a_t;s_t)$, $p(s_{t+1}|s_t,a_t) = \Delta(s_{t+1};s_t,a_t)$ and of course, $R_t(r|s_{t+1},a_t,s_t) = \text{rew}(r;s_{t+1},a_t,s_t)$, i.e. the random variables that we define have the densities that we started with... Thats why we say that this MDP is an MDP over the MDA that is given initially.

*There are many more issues with what people usually simply claim without thinking about it. For example: $E[X|Y=y]$ is a complicated mathematical object (factorization of conditional expectation). This refers to a whole class of functions, so taking the pointwise supremum $v^*(s) = \text{max}_\pi v^\pi(s)$ does not really make sense... or does it? ;-)

*We can never never never ever define $E[X|Y=y]$ if $p(y)=0$. For example, if the state space is continuous like in the 'balancing the pole'-task we cannot at all attempt to use the original theory with valuation functions! It will fail, because nothing is defined. Worse: Even if the state space is finite (like in Tic Tac Toe) we actually can not define $v^\pi(s) = E[\sum_{k=0}^\infty \gamma^k R_k | S_0=s]$ for *any state other than $s=\text{empty}$!!! (becaue $P[S_0=s] = 0$ if $s$ is not the empty field!) So, for many applications in RL, this ($E[... | S_0=s]$) actually is not (and can never be) the definition of the value function! We need to do it differently...

*There are many generalizations of what I have written above. For example: sometimes, people let the policy $\pi$ depend on the time $t$ and/or even on the past $(r_v, a_v, s_v)_{v=0,...,t}$. However, it turns out that this does not result in better policies because in many cases (discrete state and action space + mild regularity conditions) the best possible policy EVER is a stationary (i.e. does not depent on time) markovian (i.e. does not depend on the past except for $s_t$) and even deterministic (i.e. for every state there exists one 'best' action $a$ such that $\pi(a;s) = 1$ and $\pi(a';s) = 0$ for all $a'\neq a$) one.

A: Yes it does. Given $s$, the sample space $\Omega$ is the set of actions. $\pi$ is $\mathbb{P}$; it assigns a probability to each action. The random variables here is actually $Q(s, a)$.
