Are there reinforcement learning algorithms that scale to large problems?

Question

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?

Answer 1

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. Another, more recent, algorithm called Hindsight Experience Replay 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. 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 or imitation learning.

---

References
All references not already linked to are chapters out of Sutton and Barto's RL book.
[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.