<p>It is proved that the Bellman update is a contraction (1).</p>
<p><strong>Here is the Bellman update that is used for Q-Learning:</strong></p>
<p><span class="math-container">$$Q_{t+1}(s, a) = Q_{t}(s, a) + \alpha*(r(s, a, s') + \gamma  \max_{a^*} (Q_{t}(s',
   a^*)) - Q_t(s,a)) \tag{1} \label{1}$$</span></p>
<p>The proof of (\ref{1}) being contraction comes from one of the facts (the relevant one for the question) that max operation is non expansive; that is:</p>
<p><span class="math-container">$$\lvert \max_a f(a)- \max_a g(a) \rvert \leq \max_a \lvert f(a) -  g(a) \rvert \tag{2}\label{2}$$</span></p>
<p>This is also proved in a lot of places and it is pretty intuitive.</p>
<p><strong>Consider the following Bellman update:</strong></p>
<p><span class="math-container">$$ Q_{t+1}(s, a) = Q_{t}(s, a) + \alpha*(r(s, a, s') + \gamma  SAMPLE_{a^*} (Q_{t}(s', a^*)) - Q_t(s,a)) \tag{3}\label{3}$$</span></p>
<p>where <span class="math-container">$SAMPLE_a(Q(s, a))$</span> samples an action with respect to the Q values (weighted by their Q values) of each action in that state.</p>
<p><strong>Is this new Bellman operation still a contraction?</strong></p>
<p>Is the SAMPLE operation non-expansive? It is, of course, possible to generate samples that will not satisfy equation (\ref{2}). I ask <strong>is it non-expansive in expectation?</strong></p>
<p>My approach is:</p>
<p><span class="math-container">$$\lvert\,\mathbb{E}_{a \sim Q}[f(a)] - \mathbb{E}_{a \sim Q}[g(a)]\, \rvert \leq \,\,\mathbb{E}_{a \sim Q}\lvert\,\,[f(a) - g(a)]\,\,\rvert \tag{4} \label{4} $$</span></p>
<p>Equivalently:</p>
<p><span class="math-container">$$\lvert\,\mathbb{E}_{a \sim Q}[f(a) - g(a)] \, \rvert \leq \,\,\mathbb{E}_{a \sim Q}\lvert\,\,[f(a) - g(a)]\,\,\rvert$$</span></p>
<p>(\ref{4}) is true since:</p>
<p><span class="math-container">$$\lvert\,\mathbb{E}[X] \, \rvert \leq \,\,\mathbb{E} \,\,\lvert\,\,[X]\,\,\rvert $$</span></p>
<p><strong>But, I am not sure if proving (\ref{4}) proves the theorem. Do you think that this is a legit proof that (\ref{3}) is a contraction.</strong></p>
<p>(If so; this would mean that stochastic policy q learning theoretically converges and we can have stochastic policies with regular q learning; and this is why I am interested.)</p>
<p>Both intuitive answers and mathematical proofs are welcome.</p>

CC BY-SA 4.0
2020-07-24T11:29:55.557Z
(1) is a bellman update; it is a copy paste error that rhs has t+1 (sorry about that) thanks for noticing; I fixed the error now.
sirfroggy
<reinforcement-learning><q-learning><proofs><convergence><bellman-equations>
Is the Bellman equation that uses sampling weighted by the Q values (instead of max) a contraction?
sirfroggy
# Is the Bellman equation that uses sampling weighted by the Q values (instead of max) a contraction?

(Asked by: username_0 on 2020-07-23)

It is proved that the Bellman update is a contraction (1).

**Here is the Bellman update that is used for Q-Learning:**

$$Q\_{t+1}(s, a) = Q\_{t}(s, a) + \alpha\*(r(s, a, s') + \gamma \max\_{a^\*} (Q\_{t}(s',
a^\*)) - Q\_t(s,a)) \tag{1} \label{1}$$

The proof of (\ref{1}) being contraction comes from one of the facts (the relevant one for the question) that max operation is non expansive; that is:

$$\lvert \max\_a f(a)- \max\_a g(a) \rvert \leq \max\_a \lvert f(a) - g(a) \rvert \tag{2}\label{2}$$

This is also proved in a lot of places and it is pretty intuitive.

**Consider the following Bellman update:**

$$ Q\_{t+1}(s, a) = Q\_{t}(s, a) + \alpha\*(r(s, a, s') + \gamma SAMPLE\_{a^\*} (Q\_{t}(s', a^\*)) - Q\_t(s,a)) \tag{3}\label{3}$$

where $SAMPLE\_a(Q(s, a))$ samples an action with respect to the Q values (weighted by their Q values) of each action in that state.

**Is this new Bellman operation still a contraction?**

Is the SAMPLE operation non-expansive? It is, of course, possible to generate samples that will not satisfy equation (\ref{2}). I ask **is it non-expansive in expectation?**

My approach is:

$$\lvert\,\mathbb{E}\_{a \sim Q}[f(a)] - \mathbb{E}\_{a \sim Q}[g(a)]\, \rvert \leq \,\,\mathbb{E}\_{a \sim Q}\lvert\,\,[f(a) - g(a)]\,\,\rvert \tag{4} \label{4} $$

Equivalently:

$$\lvert\,\mathbb{E}\_{a \sim Q}[f(a) - g(a)] \, \rvert \leq \,\,\mathbb{E}\_{a \sim Q}\lvert\,\,[f(a) - g(a)]\,\,\rvert$$

(\ref{4}) is true since:

$$\lvert\,\mathbb{E}[X] \, \rvert \leq \,\,\mathbb{E} \,\,\lvert\,\,[X]\,\,\rvert $$

**But, I am not sure if proving (\ref{4}) proves the theorem. Do you think that this is a legit proof that (\ref{3}) is a contraction.**

(If so; this would mean that stochastic policy q learning theoretically converges and we can have stochastic policies with regular q learning; and this is why I am interested.)

Both intuitive answers and mathematical proofs are welcome.

**Tags:** reinforcement-learning, q-learning, proofs, convergence, bellman-equations

> **Comments:**
> **username_0**: (1) is a bellman update; it is a copy paste error that rhs has t+1 (sorry about that) thanks for noticing; I fixed the error now.  

---

## 0 answers

