Answers.Body: <p><em>TL;DR: It is Q learning. However Q learning is basically sample-based value iteration, so not surprising you see a similarity.</em></p>
  
  <p>Q learning* and value iteration are very strongly related. When considering action values, both approaches use the same Bellman equation for optimal policy, <span class="math-container">$q^*(s,a) = \sum_{r,s'}p(r,s'|s,a)(r+\gamma \text{max}_{a'} q^*(s', a'))$</span> as the basis for update steps. The differences are:</p>
  
  <ul>
  <li><p>Value iteration makes updates using a model of the environment, Q learning works from samples from the environment made by an active agent.</p>
  
  <ul>
  <li>By working from a simulated environment rather than a real one, it may not be clear when an agent is model-free or model-based (or planning rather than acting). However, the way that the simulated environment in the PyTorch example is used is consistent with a model-free method.</li>
  </ul></li>
  <li><p>Value iteration loops through all possible states and actions for updates independently of any action an agent might take (in fact the agent need not exist). Q learning works with whichever states the agent experienced.</p>
  
  <ul>
  <li>By adding experience replay memory in DQN, Q learning becomes a little bit closer to value iteration, as you can frame the memory as a learned model, plus consider it to be a type of planning (or a "sweep" through states). This is how it is described for instance in DynaQ which is an almost identical algorithm to experience replay as used in DQN when both are used in the simplest versions - see Sutton &amp; Barto chapter 8.</li>
  </ul></li>
  <li><p>Value iteration value update steps are over an <em>expectation</em> of next states and rewards - it processes the weighted sum <span class="math-container">$\sum_{r,s'}p(r,s'|s,a)$</span>. Q learning update steps are over <em>sampled</em> next states and rewards - it ends up approximating the same expectation over many separate updates.</p>
  
  <ul>
  <li>Even using large amounts of experience replay memory does not get Q learning the same as value iteration on this issue, samples are not guaranteed perfect. However, in a deterministic environment, this difference is not meaningful. So if you have a deterministic environment, Q learning and value iteration may also be considered a little closer in nature.</li>
  </ul></li>
  </ul>
  
  <hr>
  
  <p>* Technically this applies to single-step Q-learning. n-step Q-learning and Q(<span class="math-container">$\lambda$</span>) use different estimates of future expected return, that are related but not the same as the single-step version shown here.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T08:55:02.327Z
Answers.Text: but according to Q-learning formula that code is incorrect, they use value iteration update rather than Q-learning.
Answers.UserDisplayName: dato nefaridze
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T08:56:14.927Z
Answers.Text: @datonefaridze: I cannot see that. Can you give me the line of code reference wheer you think the update is using value iteration? As far as I can see, the TD target is calculated and used as I would expect for Q learning - i.e. from samples of agent behaviour, and not abstractly from a distribution model.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T17:41:15.993Z
Answers.Text: I think you should emphasize that saying that the use of the experience replay in DQN makes DQN model-based is a little bit of a stretch. It's true that ER is a dataset from which you sample and that contains samples from the environment, but it doesn't provide you the probabilities that a model of the environment would give you (and that you need in value iteration), although you can estimate these probabilities from the ER. Maybe there's some research work that formally shows something similar to what you are saying, but I am currently not aware of it.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T18:06:59.040Z
Answers.Text: @nbro: Yes, there is some support for ER being a model. There is very little difference indeed between ER as used in DQN and the background model-based planning from DynaQ, they are exactly the same algorithm (until you add options like n-step). In DynaQ the memory is explicitly considered a learned sampling model. Sutton & Barto presents it this way in the chapter on planning. It is correct however, that ER cannot be a distributional model (which you would need for value iteration).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T18:13:20.670Z
Answers.Text: Maybe you can provide a reference to the paper/book that shows that. Anyway, I am not saying that the ER cannot represent a distribution. It can, but it's just an approximative model.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T18:16:53.990Z
Answers.Text: @nbro: I added that to the answer - my reference for this is Sutton & Barto chapter 8.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-24T08:50:26.437Z
Answers.LastActivityDate: 2020-05-24T18:19:24.283Z
Answers.LastEditDate: 2020-05-24T18:19:24.283Z
Answers.UserDisplayName: Neil Slater
Body: <p>I read Q-learning algorithm and also I know value iteration (when you update action values).  I think the PyTorch example is value iteration rather than Q-learning.</p>
  
  <p>Here is the link:
  <a href="https://pytorch.org/tutorials/intermediate/reinforcement_q_learning.html" rel="nofollow noreferrer">https://pytorch.org/tutorials/intermediate/reinforcement_q_learning.html</a></p>
  
Tags: <q-learning><value-iteration>
Title: Is the PyTorch official tutorial really about Q-learning?
UserDisplayName: dato nefaridze
ThreadText: # Is the PyTorch official tutorial really about Q-learning?
  
  (Asked by: username_0 on 2020-05-24)
  
  I read Q-learning algorithm and also I know value iteration (when you update action values). I think the PyTorch example is value iteration rather than Q-learning.
  
  Here is the link:
  <https://pytorch.org/tutorials/intermediate/reinforcement_q_learning.html>
  
  **Tags:** q-learning, value-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-24. Score: 4
  
  *TL;DR: It is Q learning. However Q learning is basically sample-based value iteration, so not surprising you see a similarity.*
  
  Q learning\* and value iteration are very strongly related. When considering action values, both approaches use the same Bellman equation for optimal policy, $q^\*(s,a) = \sum\_{r,s'}p(r,s'|s,a)(r+\gamma \text{max}\_{a'} q^\*(s', a'))$ as the basis for update steps. The differences are:
  
  * Value iteration makes updates using a model of the environment, Q learning works from samples from the environment made by an active agent.
  
    + By working from a simulated environment rather than a real one, it may not be clear when an agent is model-free or model-based (or planning rather than acting). However, the way that the simulated environment in the PyTorch example is used is consistent with a model-free method.
  * Value iteration loops through all possible states and actions for updates independently of any action an agent might take (in fact the agent need not exist). Q learning works with whichever states the agent experienced.
  
    + By adding experience replay memory in DQN, Q learning becomes a little bit closer to value iteration, as you can frame the memory as a learned model, plus consider it to be a type of planning (or a "sweep" through states). This is how it is described for instance in DynaQ which is an almost identical algorithm to experience replay as used in DQN when both are used in the simplest versions - see Sutton & Barto chapter 8.
  * Value iteration value update steps are over an *expectation* of next states and rewards - it processes the weighted sum $\sum\_{r,s'}p(r,s'|s,a)$. Q learning update steps are over *sampled* next states and rewards - it ends up approximating the same expectation over many separate updates.
  
    + Even using large amounts of experience replay memory does not get Q learning the same as value iteration on this issue, samples are not guaranteed perfect. However, in a deterministic environment, this difference is not meaningful. So if you have a deterministic environment, Q learning and value iteration may also be considered a little closer in nature.
  
  ---
  
  \* Technically this applies to single-step Q-learning. n-step Q-learning and Q($\lambda$) use different estimates of future expected return, that are related but not the same as the single-step version shown here.
  
  > **Comments:**
  > **username_0**: but according to Q-learning formula that code is incorrect, they use value iteration update rather than Q-learning.  
  > **username_1**: @username_0: I cannot see that. Can you give me the line of code reference wheer you think the update is using value iteration? As far as I can see, the TD target is calculated and used as I would expect for Q learning - i.e. from samples of agent behaviour, and not abstractly from a distribution model.  
  > **username_2**: I think you should emphasize that saying that the use of the experience replay in DQN makes DQN model-based is a little bit of a stretch. It's true that ER is a dataset from which you sample and that contains samples from the environment, but it doesn't provide you the probabilities that a model of the environment would give you (and that you need in value iteration), although you can estimate these probabilities from the ER. Maybe there's some research work that formally shows something similar to what you are saying, but I am currently not aware of it.  
  > **username_1**: @username_2: Yes, there is some support for ER being a model. There is very little difference indeed between ER as used in DQN and the background model-based planning from DynaQ, they are exactly the same algorithm (until you add options like n-step). In DynaQ the memory is explicitly considered a learned sampling model. Sutton & Barto presents it this way in the chapter on planning. It is correct however, that ER cannot be a distributional model (which you would need for value iteration).  
  > **username_2**: Maybe you can provide a reference to the paper/book that shows that. Anyway, I am not saying that the ER cannot represent a distribution. It can, but it's just an approximative model.  
  > **username_1**: @username_2: I added that to the answer - my reference for this is Sutton & Barto chapter 8.  
  
  ---
  
  