Answers.Body: <p>I will try to give a broad answer, if it's not helpful I'll remove it. </p>
  
  <p>When we talk about sampling we are actually talking about the number of interaction required to an agent to learn a good model of the environment.
  In general I would say that there are two issues related to sample efficiency:
  1 the size of the 'action'+'environment states' space 2 the exploration strategy used.</p>
  
  <p>Regarding the first point, in reinforcement learning is really easy to encounter situations in which the number of combinations of possible actions and possible environment states explode, becoming intractable. Lets for example consider the Atari game from the Rainbow paper you linked: the environment in which the agent operate in this case is composed of rgb images of size (210, 160, 3). This means that the agent 'see' a vector of size 100800. The actions that an agent can take are simply modifications of this vector, e.g. I can move to the left a character, slightly changing the whole picture. Despite the fact that in lot of games the number of possible actions is rather small, we must keep in mind that there are also other objects in the environment which change position as well. What other object/enemies do obviously influence the choice of the best action to perform in the next time step. To a high number of possible combinations between actions and environment states is associated a high number of observations/interaction required to learn a good model of the environment. Up to now, what people usually do is to compress the information of the environment (for example by resizing and converting the pictures to grayscale), to reduce the total number of possible states to observe. DQL itself is based on the idea of using neural networks to compress the information gathered from the environment in a dense representation of fixed size. </p>
  
  <p>For what concern the exploration strategy, we can again divide the issue in subcategories: 1 how do we explore the environment 2 how much information do we get from each exploration. Exploration is usually tuned  through the <em>greedy</em> hyper-parameter. Once in a while we let the agent perform a random action, to avoid to get stuck in suboptimal policies (like not moving at all to avoid to fall into a trap, eventually thanks to a greedy action the agent will try to jump and learn that it gives a higher reward). Exploration comes with the cost of more simulations to perform, so people quickly realise that we can't rely only on more exploration to train better policies. One way to boost performance is to leverage not only the present iteration but also past interactions as well, this approach is called <em>experience replay</em>. The underline idea is to update the q-values depending also on weighted past rewards, stored in a memory buffer. Other approaches point to computation efficiency rather than decreasing the amount of simulations. An old proposed technique that follow this direction is <em>prioritised sweeping</em> <a href="https://people.eecs.berkeley.edu/~pabbeel/cs287-fa19/optreadings/MooreAtkeson-1993-prioritized-sweeping.pdf" rel="nofollow noreferrer">Moore et al. 1993</a>, in which big changes in q values are prioritised, i.e. q-values that are stable over iterations are basically ignored (this is a really crude way to put it, I have to admit that I still have to grasp this concept properly). Both this techniques were actually applied in the Rainbow paper. </p>
  
  <p>On a more personal level (just pure opinions of mine from here) I would say that the problem between RL agents and humans is the fact that we (humans) have lot of common sense knowledge we can leverage, and somehow we are able, through cognitive heuristics and shortcuts, to pay attention to what is relevant without even being aware of it. RL agents learn to interact with an environment without any prior knowledge, they just learn some probability distribution through trial and errors, and if something completely new happens they have no ability at all to pick up an action based on external knowledge. 
  One interesting future direction in my opinion is reward modelling, described in this video: <a href="https://youtu.be/PYylPRX6z4Q" rel="nofollow noreferrer">https://youtu.be/PYylPRX6z4Q</a> </p>
  
  <p>I particularly like the emphasis on the fact that the only true thing that human are good at is judging. We don't know how to design proper reward functions, because again, most of the actions we perform in real life are driven by reward of which we are not aware, but we are able in a glimpse to say if an agent is performing a task in a proper way or not. Combining this 'judging power' into RL exploration seems to be a really powerful way to increase sample efficiency in RL.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-14T22:06:15.573Z
Answers.LastActivityDate: 2020-04-10T01:05:50.180Z
Answers.LastEditDate: 2020-04-10T01:05:50.180Z
Answers.UserDisplayName: Edoardo Guerriero
Answers.Body: <p>This is mostly because humans already have information when they start learning the game (priors) that makes them learn it more quickly. We already know to jump on monsters or avoid them or to get gold looking object. </p>
  
  <p>When you remove these priors you can see a human is worse at learning these games. (<a href="https://arxiv.org/pdf/1802.10217.pdf" rel="nofollow noreferrer">link</a>)</p>
  
  <p>Some experiments they tried in the study to remove these priors where replacing all notable objects with colored squares, reversing and scrambling controls, changing gravity, and generally replacing all sprites with random pixels. All these experiments made human learning much harder, and increased death rate, time needed and states visited in the game.</p>
  
  <p>If we want the reinforcement learning algorithm to perform as good as a human, we will have to somehow include these priors we have as a human before training the network. This of course is not yet done (as far as I know)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-16T09:49:22.143Z
Answers.LastActivityDate: 2020-03-16T10:54:00.087Z
Answers.LastEditDate: 2020-03-16T10:54:00.087Z
Answers.UserDisplayName: Lustwelpintje
Body: <p>Reinforcement learning methods are considered to be extremely sample inefficient.</p>
  <p>For example, in a recent DeepMind <a href="https://arxiv.org/abs/1710.02298" rel="nofollow noreferrer">paper</a> by Hessel et al., they showed that in order to reach human-level performance on an Atari game running at 60 frames per second they needed to run 18 million frames, which corresponds to 83 hours of play experience. For an Atari game that most humans pick up within a few minutes, this is a lot of time.</p>
  <p>What makes DQN, DDPG, and others, so sample inefficient?</p>
  
Tags: <reinforcement-learning><dqn><papers><ddpg><sample-efficiency>
Title: Why are reinforcement learning methods sample inefficient?
UserDisplayName: rrz0
ThreadText: # Why are reinforcement learning methods sample inefficient?
  
  (Asked by: username_0 on 2020-03-14)
  
  Reinforcement learning methods are considered to be extremely sample inefficient.
  
  For example, in a recent DeepMind [paper](https://arxiv.org/abs/1710.02298) by Hessel et al., they showed that in order to reach human-level performance on an Atari game running at 60 frames per second they needed to run 18 million frames, which corresponds to 83 hours of play experience. For an Atari game that most humans pick up within a few minutes, this is a lot of time.
  
  What makes DQN, DDPG, and others, so sample inefficient?
  
  **Tags:** reinforcement-learning, dqn, papers, ddpg, sample-efficiency
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-03-14. Score: 5
  
  I will try to give a broad answer, if it's not helpful I'll remove it.
  
  When we talk about sampling we are actually talking about the number of interaction required to an agent to learn a good model of the environment.
  In general I would say that there are two issues related to sample efficiency:
  1 the size of the 'action'+'environment states' space 2 the exploration strategy used.
  
  Regarding the first point, in reinforcement learning is really easy to encounter situations in which the number of combinations of possible actions and possible environment states explode, becoming intractable. Lets for example consider the Atari game from the Rainbow paper you linked: the environment in which the agent operate in this case is composed of rgb images of size (210, 160, 3). This means that the agent 'see' a vector of size 100800. The actions that an agent can take are simply modifications of this vector, e.g. I can move to the left a character, slightly changing the whole picture. Despite the fact that in lot of games the number of possible actions is rather small, we must keep in mind that there are also other objects in the environment which change position as well. What other object/enemies do obviously influence the choice of the best action to perform in the next time step. To a high number of possible combinations between actions and environment states is associated a high number of observations/interaction required to learn a good model of the environment. Up to now, what people usually do is to compress the information of the environment (for example by resizing and converting the pictures to grayscale), to reduce the total number of possible states to observe. DQL itself is based on the idea of using neural networks to compress the information gathered from the environment in a dense representation of fixed size.
  
  For what concern the exploration strategy, we can again divide the issue in subcategories: 1 how do we explore the environment 2 how much information do we get from each exploration. Exploration is usually tuned through the *greedy* hyper-parameter. Once in a while we let the agent perform a random action, to avoid to get stuck in suboptimal policies (like not moving at all to avoid to fall into a trap, eventually thanks to a greedy action the agent will try to jump and learn that it gives a higher reward). Exploration comes with the cost of more simulations to perform, so people quickly realise that we can't rely only on more exploration to train better policies. One way to boost performance is to leverage not only the present iteration but also past interactions as well, this approach is called *experience replay*. The underline idea is to update the q-values depending also on weighted past rewards, stored in a memory buffer. Other approaches point to computation efficiency rather than decreasing the amount of simulations. An old proposed technique that follow this direction is *prioritised sweeping* [Moore et al. 1993](https://people.eecs.berkeley.edu/~pabbeel/cs287-fa19/optreadings/MooreAtkeson-1993-prioritized-sweeping.pdf), in which big changes in q values are prioritised, i.e. q-values that are stable over iterations are basically ignored (this is a really crude way to put it, I have to admit that I still have to grasp this concept properly). Both this techniques were actually applied in the Rainbow paper.
  
  On a more personal level (just pure opinions of mine from here) I would say that the problem between RL agents and humans is the fact that we (humans) have lot of common sense knowledge we can leverage, and somehow we are able, through cognitive heuristics and shortcuts, to pay attention to what is relevant without even being aware of it. RL agents learn to interact with an environment without any prior knowledge, they just learn some probability distribution through trial and errors, and if something completely new happens they have no ability at all to pick up an action based on external knowledge.
  One interesting future direction in my opinion is reward modelling, described in this video: <https://youtu.be/PYylPRX6z4Q>
  
  I particularly like the emphasis on the fact that the only true thing that human are good at is judging. We don't know how to design proper reward functions, because again, most of the actions we perform in real life are driven by reward of which we are not aware, but we are able in a glimpse to say if an agent is performing a task in a proper way or not. Combining this 'judging power' into RL exploration seems to be a really powerful way to increase sample efficiency in RL.
  
  
  ---
  
  ### Answer by username_2 on 2020-03-16. Score: 4
  
  This is mostly because humans already have information when they start learning the game (priors) that makes them learn it more quickly. We already know to jump on monsters or avoid them or to get gold looking object.
  
  When you remove these priors you can see a human is worse at learning these games. ([link](https://arxiv.org/pdf/1802.10217.pdf))
  
  Some experiments they tried in the study to remove these priors where replacing all notable objects with colored squares, reversing and scrambling controls, changing gravity, and generally replacing all sprites with random pixels. All these experiments made human learning much harder, and increased death rate, time needed and states visited in the game.
  
  If we want the reinforcement learning algorithm to perform as good as a human, we will have to somehow include these priors we have as a human before training the network. This of course is not yet done (as far as I know)
  
  
  ---
  
  