Answers.Body: <p>Both your notation and terminology are quite confusing. For example, I'm not sure what is an &quot;optimal&quot; Bellman operator is. <a href="https://ai.stackexchange.com/a/11133/20538">Here's a good clarification</a> on definition of a Bellman operator. Likewise, your description of the DQN algorithm completely ignores the averaging over states/actions/rewards sampled from the replay memory.</p>
  <p>Trying to savage your notation, I'll introduce a Bellman operator <span class="math-container">$B$</span> that acts on any state-value function <span class="math-container">$Q$</span> as:</p>
  <p><span class="math-container">$$B[Q(s,a)] = \mathbb{E}_{s'}\left[r(s,a,s') + \gamma \max_{a'} Q(s',a')  \right]$$</span></p>
  <p>And optimal Q function <span class="math-container">$Q^*$</span> satisfies the Bellman equation:</p>
  <p><span class="math-container">$$B[Q^*(s,a)] = Q^*(s,a)$$</span></p>
  <p>The <em>value-iteration</em> algorithm iteratively applies the Bellman operator:
  <span class="math-container">$$Q^{n+1}(s,a) = B[Q^n(s,a)]$$</span>
  And is proven to converge to the optimal Q function:
  <span class="math-container">$$Q^*(s,a) = \lim_{n\to\infty}Q^{n}(s,a)$$</span></p>
  <p>Now, in the DQN algorithm we are approximating Q functions with DNNs with parameters <span class="math-container">$\theta$</span>: <span class="math-container">$Q(s,a; \theta)$</span>. Then we approximate the value-iteration algorithm by minimizing the norm</p>
  <p><span class="math-container">$$\mathbb{E}_{s,a} \left\|B[Q(s,a; \theta_{i-1})] - Q(s,a; \theta_i)\right\|$$</span></p>
  <p>The minimization is performed over parameters <span class="math-container">$\theta_i$</span> with previous parameters <span class="math-container">$\theta_{i-1}$</span> held fixed.</p>
  <p>The averages <span class="math-container">$\mathbb{E}_{s,a}$</span> and <span class="math-container">$\mathbb{E}_{s'}$</span> are approximated by sampling a minibatch <span class="math-container">$MB$</span> of <span class="math-container">$(s,a,r,s')$</span> tuples from the replay memory.</p>
  <p>I suppose that is the closest I can get to the crux of your question. You are claiming that the average in the bellman operator application is approximated by a single point:
  <span class="math-container">$$B[Q(s,a)] \simeq r(s,a,s') + \gamma \max_{a'} Q(s',a')$$</span>
  While, in fact it is approximated by
  <span class="math-container">$$B[Q(s,a)] \simeq \mathbb{E}_{s'\in MB} \left[ r(s,a,s') + \gamma \max_{a'} Q(s',a')\right]$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-09T14:23:00.197Z
Answers.LastActivityDate: 2021-04-09T14:23:00.197Z
Answers.UserDisplayName: Kostya
Body: <p>I am currently studying reinforcement learning, especially DQN.
  In DQN, learning proceeds in such a way as to minimize the norm (least-squares, Huber, etc.) of the optimal Bellman equation and the approximate Q-function as follows (roughly):
  <span class="math-container">$$
  \min\|B^*Q^*-\hat{Q}\|.
  $$</span>
  Here <span class="math-container">$\hat{Q}$</span> is an estimator of Q function, <span class="math-container">$Q^*$</span> is the optimal Q function, and <span class="math-container">$B^*$</span> is the optimal Bellman operator.
  <span class="math-container">$$
  B^*Q^*(s,a)=\sum_{s'}p_T(s'|s,a)[r(s,a,s')+\gamma \max_{a'}Q^*(s',a')],
  $$</span>
  where <span class="math-container">$p_T$</span> is a transition probability, <span class="math-container">$r$</span> is an immediate reward, and <span class="math-container">$\gamma$</span> is a discount factor.
  As I understand it, in the DQN algorithm, the optimal Bellman equation is approximated by a single point, and the optimal Q function <span class="math-container">$Q^*$</span> is further approximated by an estimator different from <span class="math-container">$\hat{Q}$</span>, say <span class="math-container">$\tilde{Q}$</span>.
  <span class="math-container">\begin{equation}\label{question}
  B^*Q^*(s,a)\approx r(s,a,s')+\gamma\max_{a'}Q^*(s',a')\approx r(s,a,s')+\gamma\max_{a'}\tilde{Q}(s',a'),\tag{*}
  \end{equation}</span>
  therefore the problem becomes as follows:
  <span class="math-container">$$
  \min\|r(s,a,s')+\gamma\max_{a'}\tilde{Q}(s',a')-\hat{Q}(s,a)\|.
  $$</span></p>
  <p><strong>What I want to ask：</strong>
  I would like to know the mathematical or theoretical background of the approximation of \eqref{question}, especially why the first approximation is possible. It looks like a very rough approximation. Can the right-hand side be defined as an &quot;approximate Bellman equation&quot;?　I have looked at various literature and online resources, but none of them mention exact derivation, so I would be very grateful if you could tell me about reference as well.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-09T13:12:02.160Z
Comments.Text: Hi. Can you please edit your post to include a link to the research paper or book where you took these equations from, in order to provide some context?
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><dqn><math><function-approximation><bellman-equations>
Title: Why the optimal Bellman operator of a Q-function can be approximated by a single point
UserDisplayName: user
ThreadText: # Why the optimal Bellman operator of a Q-function can be approximated by a single point
  
  (Asked by: username_0 on 2021-04-08)
  
  I am currently studying reinforcement learning, especially DQN.
  In DQN, learning proceeds in such a way as to minimize the norm (least-squares, Huber, etc.) of the optimal Bellman equation and the approximate Q-function as follows (roughly):
  $$
  \min\|B^\*Q^\*-\hat{Q}\|.
  $$
  Here $\hat{Q}$ is an estimator of Q function, $Q^\*$ is the optimal Q function, and $B^\*$ is the optimal Bellman operator.
  $$
  B^\*Q^\*(s,a)=\sum\_{s'}p\_T(s'|s,a)[r(s,a,s')+\gamma \max\_{a'}Q^\*(s',a')],
  $$
  where $p\_T$ is a transition probability, $r$ is an immediate reward, and $\gamma$ is a discount factor.
  As I understand it, in the DQN algorithm, the optimal Bellman equation is approximated by a single point, and the optimal Q function $Q^\*$ is further approximated by an estimator different from $\hat{Q}$, say $\tilde{Q}$.
  \begin{equation}\label{question}
  B^\*Q^\*(s,a)\approx r(s,a,s')+\gamma\max\_{a'}Q^\*(s',a')\approx r(s,a,s')+\gamma\max\_{a'}\tilde{Q}(s',a'),\tag{\*}
  \end{equation}
  therefore the problem becomes as follows:
  $$
  \min\|r(s,a,s')+\gamma\max\_{a'}\tilde{Q}(s',a')-\hat{Q}(s,a)\|.
  $$
  
  **What I want to ask：**
  I would like to know the mathematical or theoretical background of the approximation of \eqref{question}, especially why the first approximation is possible. It looks like a very rough approximation. Can the right-hand side be defined as an "approximate Bellman equation"?　I have looked at various literature and online resources, but none of them mention exact derivation, so I would be very grateful if you could tell me about reference as well.
  
  **Tags:** reinforcement-learning, dqn, math, function-approximation, bellman-equations
  
  > **Comments:**
  > **username_1**: Hi. Can you please edit your post to include a link to the research paper or book where you took these equations from, in order to provide some context?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-04-09. Score: 0
  
  Both your notation and terminology are quite confusing. For example, I'm not sure what is an "optimal" Bellman operator is. [Here's a good clarification](https://ai.stackexchange.com/a/11133/20538) on definition of a Bellman operator. Likewise, your description of the DQN algorithm completely ignores the averaging over states/actions/rewards sampled from the replay memory.
  
  Trying to savage your notation, I'll introduce a Bellman operator $B$ that acts on any state-value function $Q$ as:
  
  $$B[Q(s,a)] = \mathbb{E}\_{s'}\left[r(s,a,s') + \gamma \max\_{a'} Q(s',a') \right]$$
  
  And optimal Q function $Q^\*$ satisfies the Bellman equation:
  
  $$B[Q^\*(s,a)] = Q^\*(s,a)$$
  
  The *value-iteration* algorithm iteratively applies the Bellman operator:
  $$Q^{n+1}(s,a) = B[Q^n(s,a)]$$
  And is proven to converge to the optimal Q function:
  $$Q^\*(s,a) = \lim\_{n\to\infty}Q^{n}(s,a)$$
  
  Now, in the DQN algorithm we are approximating Q functions with DNNs with parameters $\theta$: $Q(s,a; \theta)$. Then we approximate the value-iteration algorithm by minimizing the norm
  
  $$\mathbb{E}\_{s,a} \left\|B[Q(s,a; \theta\_{i-1})] - Q(s,a; \theta\_i)\right\|$$
  
  The minimization is performed over parameters $\theta\_i$ with previous parameters $\theta\_{i-1}$ held fixed.
  
  The averages $\mathbb{E}\_{s,a}$ and $\mathbb{E}\_{s'}$ are approximated by sampling a minibatch $MB$ of $(s,a,r,s')$ tuples from the replay memory.
  
  I suppose that is the closest I can get to the crux of your question. You are claiming that the average in the bellman operator application is approximated by a single point:
  $$B[Q(s,a)] \simeq r(s,a,s') + \gamma \max\_{a'} Q(s',a')$$
  While, in fact it is approximated by
  $$B[Q(s,a)] \simeq \mathbb{E}\_{s'\in MB} \left[ r(s,a,s') + \gamma \max\_{a'} Q(s',a')\right]$$
  
  
  ---
  
  