I believe this is a very silly question or I am overlooking something fairly simple but I cannot make sense of the factorization of the conditional expectation in a very concrete application:

I am looking at a Markov Decision Process (MDP), i.e. a collection of random variables $(R_t, A_t, S_t)_{t \in \mathbb{N}_0}$ where $S_t$ represents the state at time $t$, $A_t$ represents the action at time t and $R_t$ represents the reward at time $t$. We imagine an 'agent' moving through some state space $S$ and being in some state $s_t \in S$ by choosing some action $a_t$ in the action space $A$ and receiving a reward $r_t$ depending on $a_t, s_t$. The goal is to find a policy $p(a_t|s_t)$ (i.e. an instruction for preferring specific actions over others given the current state) such that the following quantity gets maximized: Put $G_t = \sum_{k=0}^\infty \gamma^k R_{t+k}$ then we want to maximize $$v^\pi(s) := E^\pi[G_t|S_t=s]$$ where $E^\pi$ means that we setup the MDP with $\pi$ as the probability distributions for $p(a_t|s_t)$. What people now do is to define $$v^*(s) := \sup_{\pi} v^\pi(s)$$ and I am confused at two points concerning these definitions.

  1. The mere expression $E[X|Y=\cdot]$ refers to a $P_Y$-almost everywhere equivalence class and not to a concrete function (by the mere definition of the factorization of the conditional expectation). Even worse: Given one particular $y$, it might be that for every real number $r$, there exists a representative $f_{y,r}$ of $E[X|Y=\cdot]$ such that $f_{y,r}(y) = r$. This due to the fact that if $Y$ maps to some part of the reals endowed with the Lebesgue measure and has a density w.r.t. this measure then $P_Y(\{y\}) = \int_{\{y\}} f_Y(y) dy = 0$! So is it like $$v^\pi(s) = \sup_{\pi, f \in E^\pi[G_t|S_t=\cdot]} f(s)$$? I hardly doubt that because then $v^\pi(s) = \infty$ for all $s$ is a pretty boring function...

  2. Let us assume that $p(a_t|s_t)$ actually do not depend on $t$, i.e. $f_{A_t|S_t}(a|s) = f_{A_q|S_q}(a|s)$ for all $t,q$ and all $a,s$. Then many authors use the fact that $v^\pi$ is independent of $t$, i.e. by definition, $v^\pi$ depends on some $t$ in $G_t$. However, it is only natural to say 'well, given the starting state it does not really matter how I got there, $v^\pi(s)$ expresses the 'average' reward when I start from there and follow $\pi$'. So let us prove a simplified version: We want to show that $E[R_t|S_t=s] = E[R_q|S_q=s]$. One can show that $p(r_t|s_t) = p(r_q|s_q)$ if $r_t=r_q$ and $s_t=s_q$ so that \begin{align*} v^\pi(s_t) &= \int_{r_t} r_t p(r_t|s_t) dr_t \\ &= \int_{r_q} r_q p(r_q|s_q) dr_q \\ &= v^\pi(s_q) \end{align*} However, the first equation only holds $P_{S_t}$-almost everywhere and the second one only holds $P_{S_q}$-almost everywhere. The measures $P_{S_t}$ and $P_{S_q}$ do absolutely not coincide (for example, if we play Tic-Tac-Toe then there is a designated start state $s_0$ that contains the empty playing field and $P_{S_0}(\{s_0\}) = 1$, however, whenever one player has made any move we can never return so that $P_{S_t}(\{s_0\}) = 0$ for all $t$!).

--> Q1: How are $v^\pi, v^*$ actually defined given that representatives of $v^\pi$ can vary?

--> Q2: How can we show that $v^\pi$ actually does not depend on $t$ when the measures $P_{S_t}$ and $P_{S_q}$ are so brutally different?

The thing is that usually, we are only interested in "aggregated properties" of the factorization $E[X|Y=y]$ that are independent of the chosen representative, i.e. we only consider integrals over it or something similar. We never taste the forbidden fruit of actually evaluating it on one particular point! This is what confuses me very much and any help to clarify what is meant is extremely appreciated :-)




Oh, I completely overlooked that many reliable sources (i.e. not Sutton and Barto but Puterman, Markov Decision Processes) have this little assumption in the beginning of the respective chapter that the state space is discrete... Then, at least on $\{s \in S : P[S_t=s] \neq 0\}$, $E[X|S_t=s]$ is uniquely determined, namely $$E[X|S_t=s] = \int_{\mathbb{R}} x p(x|s_t) dx$$

The second question is now easier because '$P_{S_t}$-almost everywhere' is just everywhere on $M_t = \{s \in S : P[S_t = s] > 0\}$ and '$P_{S_q}$-almost everywhere' is just $M_q = \{s \in S : P[S_q=s] > 0\}$ i.e. we have a unified way of talking about them. However, it might totally be true that $M_t \cap M_q = \emptyset$, for example, in the situation adressed above with the starting state. In that case, $v^\pi(s_0)$ can only be defined as $v^\pi(s_0; 0)$ because for any other $t$, $v^\pi(s_0;t)$ is simply undefined.


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.