2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ but according to Q-learning formula that code is incorrect, they use value iteration update rather than Q-learning. $\endgroup$ May 24 '20 at 8:55
  • $\begingroup$ @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. $\endgroup$ May 24 '20 at 8:56
  • $\begingroup$ 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. $\endgroup$
    – nbro
    May 24 '20 at 17:41
  • $\begingroup$ @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). $\endgroup$ May 24 '20 at 18:06
  • 1
    $\begingroup$ @nbro: I added that to the answer - my reference for this is Sutton & Barto chapter 8. $\endgroup$ May 24 '20 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.