In reinforcement learning, what is the correct definition of “value function”?

Question

This is a follow up to: In reinforcement learning, what is the correct mathematical definition of the discounted reward?

I discovered that there seems to exist an extremely large and disparate definition of the value function in reinforcement learning. Here is a brief sample platter:

1. Andrew Ng Notes, page 130

The value function is,

$$V^\pi(s) = \mathbb{E}[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) ... | s_0 = s, \pi], \gamma \in [0,1)$$

This is also the same one as given on Wikipedia: https://en.wikipedia.org/wiki/Reinforcement_learning

2. David Silver Notes

The value function is,

$$V(s) = \mathbb{E}[G_t| S_t = s]$$ where $G_t = R_{t+1} + \gamma R_{t+2} + \ldots, \gamma \in [0, 1]$

Note that this definition loses the conditioning on $\pi$ and is also not starting from $s_0$.

Note that this definition agrees with Richard Sutton (except that Sutton does condition on $\pi$) and Szespevari

3. Van Der Schaar notes, pg 8

The value function is,

$$V^\pi(s) = R(s, \pi(s)) + \mathbb{E}[\sum_{t=1}^\infty \gamma^t R(s_t, \pi(s_t))]$$

This is yet another definition that is different from the above ones.

4. Zico Kolter Notes, pg 12 The value function is,

$$V^\pi(s) = \mathbb{E}[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) ... | s_0 = s, s_{t+1}, a_t = \pi(s_t)], \gamma \in [0,1)$$

This definition is similar to Andrew Ng's one, but is conditioning on a lot more things than Andrew Ng's definition. This is different from David Silver, Richard Sutton and Var Der Schaar.

5. Notes from the University of Toronto, p. 15

$$V^\pi(s_t) = \mathbb{E}[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \ldots], \gamma \in [0,1)$$

This definition is different than all of the above given the lack of conditioning, but also it takes $R_t$ (the current reward) as part of the expectation, whereas say David Silver one starts from $R_{t+1}$.

Which one is correct and why is there such a seemingly large amount of definitions?

Again my concern is that, different definitions translate into different objectives of the problem, so people are solving different problems and calling all of them reinforcement learning.

Answer 1

Which one is correct and why is there such a seemingly large amount of definitions?

Let me answer the second question first: Why is there such a (seemingly) large amount of definitions?

I would guess that there are two different reasons for that:

1. (probably prominently) Lack of knowledge of many mathematical things: What is a random variable actually? What is a Markov process actually mathematically? What are sigma algebras and measures? Further, people do often not know that we must assume or show that random variables have densities, that the word 'density' itself does not make sense but it always has to be a density with respect to a 'natural', alternative measure on the target space, etc etc (could continue here for a while because I have seen all sorts of wild stuff out there, Suttons book is an example of this: My attempt to really understand the 'proof' of the Bellman equation in that book amounted to my answer here: Deriving Bellman's Equation in Reinforcement Learning)
2. Different setups in which one can do Markov Processes / Reinforcement Learning. For example: do we only allow deterministic policies. Given a current state $s$, do we regard the policy as a function $\pi(s)$ that returns one single action or do we rather regard the policy as something indeterministic that gives rise to a probability distribution over the actions?

Now let's look at the 'one true' definition of the value function. Let me first comment why (in my personal perspective) all of the ones that you name are 'flawed'/make special assumptions:

1. does mathematically not make sense. An expected condition looks either like $E[X|Y]$ where $X, Y$ are both random variables and it itself is then a new random variable or like $E[X|Y=\cdot]$ and is actually a function in $y=\cdot$. Hence, 1. is not defined. Ng is introducing a new notion here which is (mathematically speaking) simply not defined (also not by him I guess). Apart from that: What exactly is $R(s_t)$? In the Markovian process thare are random variables $R_t, S_t, A_t$ but the symbol $R(s_t)$ is just not yet defined (and probably will never be).

2. is mathematically senseful but makes certain assumptions on the Markovian process: stationarity (i.e. that the whole setup does not depend on the time). However, one can also view the whole process when policies depend on the time (i.e. you do not have $\pi$ but potentially infinitely many $\pi_t$). But in general, this seems to be the 'correct one' (see below).

3. Is a perfect example of the 'law of equal amount of work'. Let's say you have a complicated theorem that states that $A=B$ and you are a lecturer of a course and you do not want to go into the details of the proof of $A=B$. Since you are a really clever guy, you simply define $A:=B$, then the proof that $A=B$ is easy, right? It is true by definition. Unfortunately, this universe is a mean one. In 100% of the observed cases (again, just personal observation) you will need some property of $A$ that is only valid when it is defined as original $A$ and not as $B$. No matter which way you go, you cannot get around the work of understanding the proof of $A=B$! For example: Why is this thing in 4. even called value function? It is supposed to give the value of a certain policy given that we start at a certain state... how are these things related? Why is it nevertheless the same as the other things (up to all the things that make mathematically no sense)? Because of the Bellman equation. But this Bellman equation is a complicated proof that you cannot avoid :-)

4. seems to assume that the policy is a deterministic function. However, in many mathematical constructions (for example, finding the best policy using value iteration) one needs the policies to be probabilistic and not deterministic.

5. Is just very weird. The left hand side depends on $s_t$ (also unclear what influence $t$ has on the whole thing...) but the right hand side does not... ?

What is the true, most general definition? With regards to all the questions in the area of the foundations of RL and Markov Processes, etc I can only recommend one single source of mathematical truth: Puterman, Markov Decision Processes.

First some basic rules: A Markov process is a touple of random variables $(R_t, S_t, A_t)$ that satisfy certain properties. Let us assume that we look only at stationary processes (that is some additional condition that assure that the time $t$ is irrelevant). How does the policy go in here? Well, that is related to the difference between Markov Automata and Markov Processes. What we fix is the transitions $p(s_{t+1}|s_t, a_t)$ and the rewards $p(r_t|s_{t+1}, a_t, s_t)$ as functions independently of time. However, a Markov process is only uniquely defined if we also specify $p(s_0)$ and $p(a_t|s_t)$. On the other hand, given those two further ingredients, we can actually give rise to this unique Markov Process using a somewhat involved but straightforward construction similar to here.

Summarized: Fix some $\gamma \in (0,1)$. Given the transition probabilities and the rewards that only defines a Markov automata (that is something completely different than random variables). For each choice of probability distributions for the initial state $s_0$ and a policy we can give rise to a Markov process (i.e. now, secretly, implicitly all the random variables $R_t, A_t, S_t$ depend on $\pi$ and the distribution of $s_0$ but if we referred to this all the time then our notation would become really clumsy, that's why we leave it blank and only remind ourselves that the variables itself depend on $\pi$ when we write $V^\pi$ instead of just $V$). Then $$R_t + \gamma R_{t+1} + \gamma^2 R_{t+1} + ...$$ converges almost everywhere and $$V^{t, \pi}(s) = E[R_t + \gamma R_{t+1} + \gamma^2 R_{t+1} + ... | S_t=s]$$ is actually independent of $t$. With this value function one can show many nice things. For example, if certain conditions on the state and action set are met then there is a provably best, deterministic policy (see Thm. 6.2.9 in the book of Puterman). In particular, these conditions are met when the state and action space are finite. That means that all common board games are actually boring because somewhere out in this universe, there is a best strategy to play this game and both players should actually just follow this strategy to maximize their (discounted) reward.