Answers.Body: <p>The Bellman equation in RL is usually defined <span class="math-container">$$v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)\left[r + v_\pi(s')\right] = \mathbb{E}_{s' \sim p, a \sim \pi}\left[r(s, a) + v_\pi(s')\right] \; .$$</span>
  The way you have written it is correct, but I just thought I would point this out. Regardless, your intuition is correct in that it expresses a recursive relationship such that the value of your current state <span class="math-container">$s$</span> is equal to the sum of the expected reward from this state plus the expected value of the state you transition into.</p>
  <p>You do, in fact, implement the Q-learning update in Deep Q-Learning. The loss function that you minimise in DQN is
  <span class="math-container">$$ L(\theta) = \mathbb{E}_{(s,a,r,s')\sim U(D)}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta^-) - Q(s, a; \theta)\right)^2 \right]\;$$</span>
  where <span class="math-container">$U(D)$</span> denotes uniformly at random from replay buffer <span class="math-container">$D$</span> and <span class="math-container">$\theta$</span> are your network parameters (the network parameterises the Q-function), and <span class="math-container">$\theta^-$</span> are a previous iteration of the parameters that are updated every <span class="math-container">$c$</span> episodes to help with convergence of the network.</p>
  <p>As you can see, the loss function is minimising the 'Bellman error' error from your equation 2. Lets think about why this is.</p>
  <p>The TD update you provide is gradually shifting the Q value for <span class="math-container">$(s, a)$</span> towards <span class="math-container">$r + \max_a Q(s', a)$</span> - this is what we want after all since it eventually converges to the optimal Q-function.</p>
  <p>Now lets think about the Deep Q-learning case. We want our network to approximate <span class="math-container">$Q(s, a)$</span> and so if we train the network, using the MSE loss, with <span class="math-container">$r + \max_a Q(s', a)$</span> as our target then our network will gradually be shifted towards predicting <span class="math-container">$r + \max_aQ(s', a)$</span> (which again would give us optimal Q-values for state-action pairs), just like with the TD update.</p>
  <p>This is assuming that you know how training of neural networks works so if you don't then I would recommend asking/searching for a relevant question that explains this.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-10T10:23:05.470Z
Answers.Text: Yes, can you please explain why minimization of the MSE is equivalent to the TD update
Answers.UserDisplayName: Yves Boutellier
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-10T10:36:53.793Z
Answers.Text: When people mention the bellman equation in the context of RL I typically think of it in terms of the value function rather than the state-value function. It also looks neater than OP’s. I can add an explanation about why minimising MSE is equivalent to the TD update.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-10T01:08:42.280Z
Answers.Text: I'm not sure why you're saying that the actual Bellman equation is an equation that is a function of the state only. There are different Bellman equations in the context of RL. You also have the Bellman equation in terms of a state-action function, for instance. In general, when someone mentions the "Bellman equation", that means we're talking about a recursive equation. This pops up a lot in many CS contexts, such as all those dynamic programming algorithms in the CLRS book.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-10T01:08:44.373Z
Answers.Text: The second thing that you're not explaining is: why the minimization of the MSE is equivalent to the TD update, if that's what you're saying.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-10T00:28:09.697Z
Answers.LastActivityDate: 2020-12-10T10:48:43.857Z
Answers.LastEditDate: 2020-12-10T10:48:43.857Z
Answers.UserDisplayName: David
Body: <p>I'm doing a project on Reinforcement Learning. I programmed an agent that uses DDQN. There are a lot of tutorials on that, so the code implementation was not that hard.</p>
  <p>However, I have problems understanding how one should come up with this kind of algorithms by starting from the Bellman equation, and I don't find a good understandable explanation addressing this derivation/path of reasoning.</p>
  <p>So, my questions are:</p>
  <ol>
  <li>How is the loss to train the DQN derived from (or theoretically motivated by) the Bellman equation?</li>
  <li>How is it related to the usual Q-learning update?</li>
  </ol>
  <p>According to my current notes, the Bellman equation looks like this</p>
  <p><span class="math-container">$$Q_{\pi} (s,a) = \sum_{s'} P_{ss'}^a (r_{s,a} + \gamma \sum_{a'} \pi(a'|s') Q_{\pi} (s',a')) \label{1}\tag{1} $$</span></p>
  <p>which, to my understanding, is a recursive expression that says:
  The state-action pair gives a reward that is equal to the sum over all possible states <span class="math-container">$s'$</span> with the probability of getting to this state after taking action <span class="math-container">$a$</span> (denoted as <span class="math-container">$P_{ss'}^a$</span>, which means the environment acts on the agent) times the reward the agent got from taking action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> + discounted sum of the probability of the different possible actions <span class="math-container">$a'$</span> times the reward of the state, action pair <span class="math-container">$s',a'$</span>.</p>
  <p>The Q-Learning iteration (intermediate step) is often denoted as:</p>
  <p><span class="math-container">$$Q^{new}(s,a) \leftarrow  Q(s,a) + \alpha (r + \gamma \max_a Q(s',a') - Q(s,a)) \label{2}\tag{2}$$</span></p>
  <p>which means that the new state, action reward is the old Q value + learning rate, <span class="math-container">$\alpha$</span>, times the temporal difference, <span class="math-container">$(r + \gamma \max_a Q(s',a') - Q(s,a))$</span>, which consists of the actual reward the agent received + a discount factor times the Q function of this new state-action pair minus the old Q function.</p>
  <p>The Bellman equation can be converted into an update rule because an algorithm that uses that update rule converges, as <a href="https://ai.stackexchange.com/a/20163/2444">this answer</a> states.</p>
  <p>In the case of (D)DQN, <span class="math-container">$Q(s,a)$</span> is estimated by our NN that leads to an action <span class="math-container">$a$</span> and we receive <span class="math-container">$r$</span> and <span class="math-container">$s'$</span>.</p>
  <p>Then we feed in <span class="math-container">$s$</span> as well as <span class="math-container">$s'$</span> into our NN (with Double DQN we feed them into different NNs). The <span class="math-container">$\max_a Q(s',a')$</span> is performed on the output of our target network. This q-value is then multiplied with <span class="math-container">$\gamma$</span> and <span class="math-container">$r$</span> is added to the product. Then this sum replaces the q-value from the other NN. Since this basic NN outputted <span class="math-container">$Q(s,a)$</span> but should have outputted <span class="math-container">$r + \gamma \max_a Q(s',a')$</span> we train the basic NN to change the weights, so that it would output closer to this temporal target difference.</p>
  
Tags: <reinforcement-learning><q-learning><dqn><objective-functions><bellman-equations>
Title: How is the DQN loss derived from (or theoretically motivated by) the Bellman equation, and how is it related to the Q-learning update?
UserDisplayName: Yves Boutellier
ThreadText: # How is the DQN loss derived from (or theoretically motivated by) the Bellman equation, and how is it related to the Q-learning update?
  
  (Asked by: username_0 on 2020-12-09)
  
  I'm doing a project on Reinforcement Learning. I programmed an agent that uses DDQN. There are a lot of tutorials on that, so the code implementation was not that hard.
  
  However, I have problems understanding how one should come up with this kind of algorithms by starting from the Bellman equation, and I don't find a good understandable explanation addressing this derivation/path of reasoning.
  
  So, my questions are:
  
  1. How is the loss to train the DQN derived from (or theoretically motivated by) the Bellman equation?
  2. How is it related to the usual Q-learning update?
  
  According to my current notes, the Bellman equation looks like this
  
  $$Q\_{\pi} (s,a) = \sum\_{s'} P\_{ss'}^a (r\_{s,a} + \gamma \sum\_{a'} \pi(a'|s') Q\_{\pi} (s',a')) \label{1}\tag{1} $$
  
  which, to my understanding, is a recursive expression that says:
  The state-action pair gives a reward that is equal to the sum over all possible states $s'$ with the probability of getting to this state after taking action $a$ (denoted as $P\_{ss'}^a$, which means the environment acts on the agent) times the reward the agent got from taking action $a$ in state $s$ + discounted sum of the probability of the different possible actions $a'$ times the reward of the state, action pair $s',a'$.
  
  The Q-Learning iteration (intermediate step) is often denoted as:
  
  $$Q^{new}(s,a) \leftarrow Q(s,a) + \alpha (r + \gamma \max\_a Q(s',a') - Q(s,a)) \label{2}\tag{2}$$
  
  which means that the new state, action reward is the old Q value + learning rate, $\alpha$, times the temporal difference, $(r + \gamma \max\_a Q(s',a') - Q(s,a))$, which consists of the actual reward the agent received + a discount factor times the Q function of this new state-action pair minus the old Q function.
  
  The Bellman equation can be converted into an update rule because an algorithm that uses that update rule converges, as [this answer](https://ai.stackexchange.com/a/20163/2444) states.
  
  In the case of (D)DQN, $Q(s,a)$ is estimated by our NN that leads to an action $a$ and we receive $r$ and $s'$.
  
  Then we feed in $s$ as well as $s'$ into our NN (with Double DQN we feed them into different NNs). The $\max\_a Q(s',a')$ is performed on the output of our target network. This q-value is then multiplied with $\gamma$ and $r$ is added to the product. Then this sum replaces the q-value from the other NN. Since this basic NN outputted $Q(s,a)$ but should have outputted $r + \gamma \max\_a Q(s',a')$ we train the basic NN to change the weights, so that it would output closer to this temporal target difference.
  
  **Tags:** reinforcement-learning, q-learning, dqn, objective-functions, bellman-equations
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-10. Score: 2 | Accepted answer
  
  The Bellman equation in RL is usually defined $$v\_\pi(s) = \sum\_a \pi(a|s) \sum\_{s', r} p(s', r|s, a)\left[r + v\_\pi(s')\right] = \mathbb{E}\_{s' \sim p, a \sim \pi}\left[r(s, a) + v\_\pi(s')\right] \; .$$
  The way you have written it is correct, but I just thought I would point this out. Regardless, your intuition is correct in that it expresses a recursive relationship such that the value of your current state $s$ is equal to the sum of the expected reward from this state plus the expected value of the state you transition into.
  
  You do, in fact, implement the Q-learning update in Deep Q-Learning. The loss function that you minimise in DQN is
  $$ L(\theta) = \mathbb{E}\_{(s,a,r,s')\sim U(D)}\left[\left( r + \gamma \max\_{a'}Q(s', a'; \theta^-) - Q(s, a; \theta)\right)^2 \right]\;$$
  where $U(D)$ denotes uniformly at random from replay buffer $D$ and $\theta$ are your network parameters (the network parameterises the Q-function), and $\theta^-$ are a previous iteration of the parameters that are updated every $c$ episodes to help with convergence of the network.
  
  As you can see, the loss function is minimising the 'Bellman error' error from your equation 2. Lets think about why this is.
  
  The TD update you provide is gradually shifting the Q value for $(s, a)$ towards $r + \max\_a Q(s', a)$ - this is what we want after all since it eventually converges to the optimal Q-function.
  
  Now lets think about the Deep Q-learning case. We want our network to approximate $Q(s, a)$ and so if we train the network, using the MSE loss, with $r + \max\_a Q(s', a)$ as our target then our network will gradually be shifted towards predicting $r + \max\_aQ(s', a)$ (which again would give us optimal Q-values for state-action pairs), just like with the TD update.
  
  This is assuming that you know how training of neural networks works so if you don't then I would recommend asking/searching for a relevant question that explains this.
  
  > **Comments:**
  > **username_2**: I'm not sure why you're saying that the actual Bellman equation is an equation that is a function of the state only. There are different Bellman equations in the context of RL. You also have the Bellman equation in terms of a state-action function, for instance. In general, when someone mentions the "Bellman equation", that means we're talking about a recursive equation. This pops up a lot in many CS contexts, such as all those dynamic programming algorithms in the CLRS book.  
  > **username_2**: The second thing that you're not explaining is: why the minimization of the MSE is equivalent to the TD update, if that's what you're saying.  
  > **username_0**: Yes, can you please explain why minimization of the MSE is equivalent to the TD update  
  > **username_1**: When people mention the bellman equation in the context of RL I typically think of it in terms of the value function rather than the state-value function. It also looks neater than OP’s. I can add an explanation about why minimising MSE is equivalent to the TD update.  
  
  ---
  
  