2
$\begingroup$

I am stuck at the proof of the contraction of variance for distributional Bellman operator from the paper, in which it is defined as enter image description here

and the proof is stated as

enter image description here

In its second part, how is the variance of the target distribution equal to the expectation of the variance terms over the next state-action pairs?

$\endgroup$
2
  • $\begingroup$ Do you mean why $\mathbb{V}(P^\pi Z_1(x, a)) - \mathbb{V}(P^\pi Z_2x, a))$ turns into $\mathbb{E}[\mathbb{V}(Z_1(X', A')) - \mathbb{V}(Z_2(X', A'))]$? $\endgroup$
    – nbro
    Jan 30, 2023 at 14:35
  • $\begingroup$ @nbro Yes, exactly. $\endgroup$ Jan 30, 2023 at 15:48

2 Answers 2

0
$\begingroup$

This is a common trick in reinforcement learning literature which uses the law of large numbers to use the sampled variables $X$ and $A$ instead of $x$ and $a$. Let's say we know the probability $p(x)$ with which a continuous $x$ is given, then we can calculate the expectation value of $x$ as: \begin{align} \mathbb{E}_{x \sim p}[x] &= \int p(x)x ~dx \\ &= \lim \limits_{N \to \infty}\frac{1}{N}\sum_{N} X \end{align} In the last line, we did not assume any knowledge of $p(x)$ but we averaged over the samples taken from $p(x)$. This would be the only way to find the expectancy value for an unknown system, e.g. the average speed of a driver, of whom we don't know the exact driving behaviour. We can also use the sampled variables for an expression of the variance \begin{align} \mathbb{V}(x) = \int p(x)(x - \mathbb{E}_{x \sim p}(x))² dx = \lim \limits_{N \to \infty} \frac{1}{N} \sum_{N} (X-\mathbb{E}[X])² \end{align} From here, two things could happen, since the notation in the paper is not quite clear.

  1. Define $\mathbb{V}[X] = (X-\mathbb{E}[X])²$ then \begin{equation} \lim \limits_{N \to \infty} \frac{1}{N} \sum_{N} (X-\mathbb{E}[X])² = \lim \limits_{N \to \infty} \frac{1}{N} \sum_{N} \mathbb{V}[X] = \mathbb{E}[{\mathbb{V}[X]}]. \end{equation} But this would be a rather confusing notation since $(X-\mathbb{E}[X])²$ is only sample whose expecation value is the variance.
  2. Since the variance already is an expectation value (the expected, absolute difference from the mean), we can add an additional expectation value, which basically does not do anything: \begin{equation} \lim \limits_{N \to \infty} \frac{1}{N} \sum_{N} (X-\mathbb{E}[X])² = \mathbb{V}[X] = \mathbb{E}[\mathbb{V}[X]] = \lim \limits_{N \to \infty} \frac{1}{N} \sum_{N} \mathbb{V}[X] = \lim \limits_{N \to \infty} \frac{1}{N} N\mathbb{V}[X] = \mathbb{V}[X]. \end{equation} I lean towards this explanation, but still introducing a useless expectation value is quite strange.

Now, let's use this in order to explain why: \begin{align} \mathbb{V}(P^{\pi}Z_{1}(x, a)) - \mathbb{V}(P^{\pi}Z_{2}(x, a)) \\ = \int \pi(a) p(x)(P^{\pi}Z_{1}(x, a) - \mathbb{E}_{x \sim p, a\sim \pi}[{P^{\pi}Z_{1}(x, a)}])^{2}~dxda - \int \pi(a) p(x)(P^{\pi}Z_{2}(x, a) - \mathbb{E}_{x \sim p, a\sim \pi}[{P^{\pi}Z_{2}(x, a)}])^{2}~dxda \\ = \lim \limits_{N \to \infty} \frac{1}{N} \sum (Z_{1}(X', A') - \mathbb{E}[Z_{1}(X', A')])^{2} - (Z_{2}(X', A') - \mathbb{E}[Z_{2}(X', A')])^{2} \\ = \mathbb{E}[\mathbb{V}(Z_{1}(X', A')) - \mathbb{V}(Z_{2}(X', A'))] \\ \end{align} Where in the last step one can use any of the two possibilities given above. I abbreviated $p(x') = p(x'|x, a)$ and $\pi(a) = \pi(a|x)$.

$\endgroup$
3
  • 1
    $\begingroup$ You are misleading two things, 1) x, a is conditional-ed, no randomness; 2) variance definition is wrong. $\endgroup$ Mar 1, 2023 at 10:22
  • $\begingroup$ Oh, I forgot the squares, you are right. I also just used a short-hand notation and therefore dropped the conditionals. But the randomness comes directly into play when capital letters are used, e.g. see from the paper 1. Introduction > "Bellman’s equation succintly describes this value in terms of the expected reward and ex- pected outcome of the random transition $(x, a) → (X′, A′)$." So, $(x, a)$ is known but due to a random transition we end up in the random $(X', A')$ $\endgroup$ Mar 1, 2023 at 10:43
  • $\begingroup$ I think it is inappropriate to integrate over (x, a), this is the definition of the expectation which variable has randomness. It is crucial to determine how the variance of $P^{\pi}Z(x, a)$ is defined. I will update an answer in a later time. $\endgroup$ Mar 1, 2023 at 12:08
0
$\begingroup$

The confusing part is how the variance is defined in terms of $P^{\pi}Z(x, a)$, which includes three sources of randomness, $X', A', Z$. However, if we define the variance as

\begin{align*} \mathbb{V}(P^{\pi}Z(x, a)) & \triangleq \int P(X' = x', A' = a') \mathbb{V} (Z | x', a')dx'da' \\ & = \mathbb{E}_{X', A'}[\mathbb{V}(Z|X', A')] \end{align*}

Then the result clearly follows as both $P^{\pi}Z_{1}$ and $P^{\pi}Z_{2}$ evolve the same dynamics, that is, on $X', A'$. By linearity of the expectation, the statement concludes.

$\endgroup$
2
  • $\begingroup$ Your notation of the variance is quite strange on the right hand-side. $Z$ is a function with the arguments $(x, a)$, it is not an argument to the probability $\mathbb{V}$, like it looks in your notation. Also you somehow define the variance as the expectation value over exactly the same variance, could you somehow distinguish these obviously different variances from each other? $\endgroup$ Mar 1, 2023 at 13:21
  • $\begingroup$ Firstly, $Z$ is a random variable, whose distribution describes the possible values of the action-value function. And you can think of the expression as that the left-hand side variance is defined as the expected value of conditional variance of $Z$, because it is natural to have distribution of $Z$ after the next state and action are ready. $\endgroup$ Mar 1, 2023 at 13:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .