Answers.Body: <p>This is a big question. I'm not going to try to cover the state-of-the-art, but I'll try to cover some of the main ideas. </p>
  
  <p><strong>Function Approximation</strong> [1]<br>
  An essential strategy for scaling up RL algorithms is to reduce the effective size of your state and/or action space through function approximation. For example, you could parameterize your value function using fewer parameters than there are states. Optimization would then take place in the much smaller parameter space, which can be substantially faster. Note that using function approximation almost always loses you any convergence guarantees you would have had otherwise in the tabular setting. It has been very successful in practice, though.</p>
  
  <p><strong>Sampling</strong>[2]<br>
  Value iteration and other dynamic programming algorithms sweep through the entire state space when computing value functions. Sample-based approaches instead update value functions for states as they are visited. These include Monte Carlo and Temporal Difference methods. Sampling allows us to focus on a subset of the states, freeing us from the computation required to get accurate value estimates of potentially irrelevant states. This is essential in real-world settings, where almost all possible states of the world are irrelevant or even impossible to reach.</p>
  
  <p><strong>Sample Efficiency/Experience Replay</strong><br>
  All else equal, a sample efficient agent is one that learns more with the same experience. Doing this reduces learning time, especially if the time bottleneck is in interacting with the environment. One basic way of improving sample efficiency is to store and reuse experience with something like the experience replay buffer popularized in the <a href="https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf" rel="nofollow noreferrer">DQN paper</a>. Another, more recent, algorithm called <a href="https://arxiv.org/pdf/1707.01495.pdf" rel="nofollow noreferrer">Hindsight Experience Replay</a> improves sample efficiency by allowing the agent to learn more from its failures (trajectories with no reward).</p>
  
  <p><strong>Model-Based Methods</strong>[3]<br>
  While technically also about sample efficiency (maybe all of these points are?), model-based methods are important enough to warrant their own section. Usually, the MDP dynamics aren't known to the agent beforehand. Learning and maintaining an estimate of the MDP is therefore often a good idea. If an agent can use its internal model of the world to simulate experience, it can then learn from that simulated experience (called <em>planning</em>) in addition to learning from actual experience. Because simulated experience is much cheaper to gather than actual experience, this can reduce the time needed to learn.</p>
  
  <p><strong>Search</strong>[4]<br>
  If our value estimates were perfect, then behaving optimally would only be a matter of moving to the neighboring state with the highest value. This is hardly ever the case, though, so we would like to make decisions more intelligently. One way, called <em>forward search</em>, is to use a model to consider many possible trajectories starting from the current state. The most popular and successful example of forward search is Monte Carlo Tree Search (MCTS), which was famously used in <a href="http://discovery.ucl.ac.uk/10045895/1/agz_unformatted_nature.pdf" rel="nofollow noreferrer">AlphaGo Zero</a>. Because search allows us to make better decisions given imperfect value estimates, we can focus on more promising trajectories, saving time and computation.</p>
  
  <p><strong>Exploration</strong><br>
  Only ever taking what we think is the "best" action in a given state is usually not a very good idea. When sampling trajectories through large state and/or action spaces, this strategy can completely fail. Taking exploratory actions can help ensure that high-value states are discovered at all. Deciding when to explore and which actions to take is active area of research. In general, though, exploratory actions are ones that reduce an agent's uncertainty of the environment.</p>
  
  <p><strong>Injecting Human Knowledge</strong><br>
  Finally, and maybe obviously, reducing the time complexity of an RL algorithm can be accomplished by giving the agent more information about the world. This can be done in many ways. If using linear function approximation, for example, an agent could be given useful information through the features it uses. If it makes use of a model, the model could be initialized with reasonable priors for the reward and transition probability distributions. "Reward shaping", the practice of manually engineering a (dense) reward function to facilitate learning a specific task, is a more general approach. An agent could also learn directly from human demonstrations with <a href="https://www.academia.edu/160777/Algorithms_for_inverse_reinforcement_learning" rel="nofollow noreferrer">inverse reinforcement learning</a> or <a href="https://www.cs.cmu.edu/~mmv/papers/09ras-survey.pdf" rel="nofollow noreferrer">imitation learning</a>.</p>
  
  <hr>
  
  <p><strong>References</strong><br>
  All references not already linked to are chapters out of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton and Barto's RL book</a>.<br>
  [1] Linear function approximation is discussed in depth in Chapter 9.<br>
  [2] Monte Carlo and Temporal Difference methods are discussed in Chapters 5 and 6.<br>
  [3] Model-based methods are discussed in the first part of Chapter 8.<br>
  [4] MCTS and search in general are discussed in the second half of Chapter 8.  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-15T09:38:04.050Z
Answers.Text: I think this a nice post, but maybe you should also list a few concrete algorithms (if there are any) that actually scale well to large problems, given that this is the actual question. Right now, yours is an answer to the question "What are the techniques that can be used to scale RL algorithms to large problems"?.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-15T12:04:57.130Z
Answers.Text: @nbro I don't know of any implemented agents that use all of these techniques. But many of the papers I linked to (DQN, HER, AlphaGo Zero) give full specifications of agents that scale well in large problems.
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-06T00:05:16.147Z
Answers.Text: I've just come across this answer again. I think that I should also note that _bandits_ (in particular, _contextual bandits_) are used by Netflix and Microsoft to recommend covers of movies and other stuff.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-15T05:53:19.907Z
Answers.LastActivityDate: 2019-04-19T01:55:44.767Z
Answers.LastEditDate: 2019-04-19T01:55:44.767Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>Given a large problem, value iteration and other table based approaches seem to require too many iterations before they start to converge. Are there other reinforcement learning approaches that better scale to large problems and minimize the amount of iterations in general?</p>
  
Tags: <reinforcement-learning>
Title: Are there reinforcement learning algorithms that scale to large problems?
UserDisplayName: Jan
ThreadText: # Are there reinforcement learning algorithms that scale to large problems?
  
  (Asked by: username_0 on 2019-04-14)
  
  Given a large problem, value iteration and other table based approaches seem to require too many iterations before they start to converge. Are there other reinforcement learning approaches that better scale to large problems and minimize the amount of iterations in general?
  
  **Tags:** reinforcement-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-04-15. Score: 6 | Accepted answer
  
  This is a big question. I'm not going to try to cover the state-of-the-art, but I'll try to cover some of the main ideas.
  
  **Function Approximation** [1]  
  An essential strategy for scaling up RL algorithms is to reduce the effective size of your state and/or action space through function approximation. For example, you could parameterize your value function using fewer parameters than there are states. Optimization would then take place in the much smaller parameter space, which can be substantially faster. Note that using function approximation almost always loses you any convergence guarantees you would have had otherwise in the tabular setting. It has been very successful in practice, though.
  
  **Sampling**[2]  
  Value iteration and other dynamic programming algorithms sweep through the entire state space when computing value functions. Sample-based approaches instead update value functions for states as they are visited. These include Monte Carlo and Temporal Difference methods. Sampling allows us to focus on a subset of the states, freeing us from the computation required to get accurate value estimates of potentially irrelevant states. This is essential in real-world settings, where almost all possible states of the world are irrelevant or even impossible to reach.
  
  **Sample Efficiency/Experience Replay**  
  All else equal, a sample efficient agent is one that learns more with the same experience. Doing this reduces learning time, especially if the time bottleneck is in interacting with the environment. One basic way of improving sample efficiency is to store and reuse experience with something like the experience replay buffer popularized in the [DQN paper](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf). Another, more recent, algorithm called [Hindsight Experience Replay](https://arxiv.org/pdf/1707.01495.pdf) improves sample efficiency by allowing the agent to learn more from its failures (trajectories with no reward).
  
  **Model-Based Methods**[3]  
  While technically also about sample efficiency (maybe all of these points are?), model-based methods are important enough to warrant their own section. Usually, the MDP dynamics aren't known to the agent beforehand. Learning and maintaining an estimate of the MDP is therefore often a good idea. If an agent can use its internal model of the world to simulate experience, it can then learn from that simulated experience (called *planning*) in addition to learning from actual experience. Because simulated experience is much cheaper to gather than actual experience, this can reduce the time needed to learn.
  
  **Search**[4]  
  If our value estimates were perfect, then behaving optimally would only be a matter of moving to the neighboring state with the highest value. This is hardly ever the case, though, so we would like to make decisions more intelligently. One way, called *forward search*, is to use a model to consider many possible trajectories starting from the current state. The most popular and successful example of forward search is Monte Carlo Tree Search (MCTS), which was famously used in [AlphaGo Zero](http://discovery.ucl.ac.uk/10045895/1/agz_unformatted_nature.pdf). Because search allows us to make better decisions given imperfect value estimates, we can focus on more promising trajectories, saving time and computation.
  
  **Exploration**  
  Only ever taking what we think is the "best" action in a given state is usually not a very good idea. When sampling trajectories through large state and/or action spaces, this strategy can completely fail. Taking exploratory actions can help ensure that high-value states are discovered at all. Deciding when to explore and which actions to take is active area of research. In general, though, exploratory actions are ones that reduce an agent's uncertainty of the environment.
  
  **Injecting Human Knowledge**  
  Finally, and maybe obviously, reducing the time complexity of an RL algorithm can be accomplished by giving the agent more information about the world. This can be done in many ways. If using linear function approximation, for example, an agent could be given useful information through the features it uses. If it makes use of a model, the model could be initialized with reasonable priors for the reward and transition probability distributions. "Reward shaping", the practice of manually engineering a (dense) reward function to facilitate learning a specific task, is a more general approach. An agent could also learn directly from human demonstrations with [inverse reinforcement learning](https://www.academia.edu/160777/Algorithms_for_inverse_reinforcement_learning) or [imitation learning](https://www.cs.cmu.edu/~mmv/papers/09ras-survey.pdf).
  
  ---
  
  **References**  
  All references not already linked to are chapters out of [Sutton and Barto's RL book](http://incompleteideas.net/book/the-book-2nd.html).  
  [1] Linear function approximation is discussed in depth in Chapter 9.  
  [2] Monte Carlo and Temporal Difference methods are discussed in Chapters 5 and 6.  
  [3] Model-based methods are discussed in the first part of Chapter 8.  
  [4] MCTS and search in general are discussed in the second half of Chapter 8.
  
  > **Comments:**
  > **username_2**: I think this a nice post, but maybe you should also list a few concrete algorithms (if there are any) that actually scale well to large problems, given that this is the actual question. Right now, yours is an answer to the question "What are the techniques that can be used to scale RL algorithms to large problems"?.  
  > **username_1**: @username_2 I don't know of any implemented agents that use all of these techniques. But many of the papers I linked to (DQN, HER, AlphaGo Zero) give full specifications of agents that scale well in large problems.  
  > **username_2**: I've just come across this answer again. I think that I should also note that _bandits_ (in particular, _contextual bandits_) are used by Netflix and Microsoft to recommend covers of movies and other stuff.  
  
  ---
  
  