Planning VS Reinforcement Learning for Large State Spaces

Question

Does knowing everything about your environment yield any major shortcuts to finding the optimal policy, in a Markov Decision Process with a very large (finite) number of states?

Mere planning clearly requires less effort than reinforcement learning for smaller state spaces; in many cases we can just calculate the policy or value function from the transition diagram using backward induction (dynamic programming). However, when the state space becomes too large to solve, or perhaps even to represent, are we stuck with the trial-and-error methods of reinforcement learning anyhow, or are there easier algorithms to implement for large scale planning?

Answer 1

However, when the state space becomes too large to solve, or perhaps even to represent, are we stuck with the trial-and-error methods of reinforcement learning anyhow, or are there easier algorithms to implement for large-scale planning?

One approach a full model of the environment enables that best fits your criteria is Monte Carlo Tree Search (MCTS). At decision-time, MCTS runs simulations starting from the current state to estimate action-values on the fly.

The effectiveness of MCTS depends on the MDP (mostly the branching factor and number of timesteps per episode) and the time and computational budgets at each timestep. However, you can start with an agent who performs much better than random.

MCTS is used in the wild, for example, in Tesla's Autopilot software.

DeepMind used a variant of MCTS in AlphaGo and, more interestingly AlphaGo Zero. In AlphaGo Zero, they used a neural network to approximate both a policy used to guide the search and a value function to evaluate leaf nodes in the tree. By training the policy network using supervised learning to imitate the policy output by MCTS, they were able to get a richer training signal than normal RL.

The use of the neural network means the tree is expanded towards more likely moves and evaluated much faster, meaning it does far better than standard MCTS.

I wrote a tutorial explaining the pro's and con's of MCTS compared with other planning methods for a course here if you'd like to learn more.

Answer 2

How human beings make daily decisions, which usually involve huge search spaces? We do abstraction, we think hierarchically, we divide and conquer, we search for a solution guided by heuristics that allow us to focus our search in directions that appear most promising.

I believe to deal with huge search spaces, the planning algorithms should have the same mechanisms mentioned above.

Reinforcement learning is nothing but dynamic programming (sth very basic to planning guys) plus function approximation. If anyone thinks DP+function fitting means strong intelligence that is going to solve complex planning problems, good luck!