In high-dimensional reinforcement learning settings with sparse rewards, performing
 effective exploration to even obtain any reward signal is an open challenge.
 While model-based approaches hold promise of better exploration via planning, it
 is extremely difficult to learn a reliable enough Markov Decision Process (MDP)
 in high dimensions (e.g., over 10^100 states). In this paper, we propose learning
 an abstract MDP over a much smaller number of states (e.g., 10^5), which we can
 plan over for effective exploration. We assume we have an abstraction function
 that maps concrete states (e.g., raw pixels) to abstract states (e.g., agent position,
 ignoring other objects). In our approach, a manager maintains an abstract
 MDP over a subset of the abstract states, which grows monotonically through targeted
 exploration (possible due to the abstract MDP). Concurrently, we learn a
 worker policy to travel between abstract states; the worker deals with the messiness
 of concrete states and presents a clean abstraction to the manager. On three of
 the hardest games from the Arcade Learning Environment (Montezuma's,
 Pitfall!, and Private Eye), our approach outperforms the previous
 state-of-the-art by over a factor of 2 in each game. In Pitfall!, our approach is
 the first to achieve superhuman performance without demonstrations. Exploration is a key bottleneck in high-dimensional, sparse-reward reinforcement learning tasks. Random exploration (e.g., via epsilon-greedy) suffices when rewards are abundant BID24 , but when rewards are sparse, it can be difficult for an agent starting out to even find any positive reward needed to bootstrap learning. For example, the infamously difficult game MON-TEZUMA'S REVENGE from the Arcade Learning Environment (ALE) BID6 contains over 10 100 states and requires the agent to go thousands of timesteps without receiving reward. Performing effective exploration in this setting is thus an open problem; without demonstrations, even state-of-the-art intrinsically-motivated RL agents BID5 BID44 achieve only about one-tenth the score of an expert human .In this paper, we investigate model-based reinforcement learning BID17 as a potential solution to the exploration problem. The hope is that with a model of the state transitions and rewards, one can perform planning under the model to obtain a more informed exploration strategy. However , as the model being learned is imperfect, errors in the model compound BID42 BID43 when planning over many time steps. Furthermore , even if a perfect model were known, in high-dimensional state spaces (e.g. over 10 100 states), planning-computing the optimal policy (e.g. via value iteration)-is intractable. As a result , model-based RL has had limited success in high-dimensional settings BID42 . To address this, some prior work has focused on learning more accurate models by using more expressive function approximators BID25 , and learning local models BID21 BID50 . Others have attempted to robustly use imperfect models by conditioning on, instead of directly following, model-based rollouts BID49 , frequently replanning, and combining model-based with model-free approaches BID0 BID40 . However, none of these techniques offer a fundamental solution.Instead of directly learning a model over the concrete state space, we propose an approach inspired by hierarchical reinforcement learning (HRL) BID41 BID46 Figure 1 : (a) Illustration of the abstract MDP on MONTEZUMA'S REVENGE. We have superimposed a white grid on top of the original game. At any given time, the agent is in one of the grid cellseach grid cell is an abstract state. In this example, the agent starts at the top of a ladder (yellow dot). The worker then navigates transitions between abstract states (green arrows) to follow a plan made by the manager (red dots). (b) Circles represent abstract states. Shaded circles represent states within the known set. The manager navigates the agent to the fringe of the known set (s 3 ), then randomly explores with π d to discover new transitions near s 3 (dotted box). (c) The worker extends the abstract MDP by learning to navigate to the newly discovered abstract states (dotted arrows). 2017), and learn a model over a much smaller abstract state space. Specifically, we assume we have a state abstraction function BID22 BID36 BID9 , which maps a highdimensional concrete state (e.g. all pixels on the screen) to a low-dimensional abstract state (e.g. the position of the agent). We then aim to learn an (abstract) Markov Decision Process (MDP) over this abstract state space as follows: A manager maintains an (abstract) MDP over a subset of all possible abstract states which we call the known set, which is grown over time. The crucial property we enforce is that this abstract MDP is highly accurate and near deterministic on the known set, so we can perform planning without suffering from compounding errors, and do it efficiently since we are working with a much smaller number of abstract states. Concurrently, we learn a worker policy that the manager uses to transition between abstract states. The worker policy has access to the concrete states; its goal is to hide the messy details of the real world from the manager (e.g., jumping over monsters) so that the manager has a much simpler planning problem (e.g., traversing between two locations). In our implementation, the worker keeps an inventory of skills (i.e., options BID41 ), each of which is driven by a deep neural network; the worker assigns an appropriate skill for each transition between abstract states. In this way, the worker does not "forget" BID20 , and we ensure monotonic progress in learning the abstract MDP. This abstract MDP, which enables us to efficiently explore via planning, is a key difference between our work and previous HRL work (e.g., BID4 BID46 ), which also learn skills and operate on latent abstract state spaces but without forming an MDP.We evaluate our approach on three of the most challenging games from the ALE BID6 : MONTEZUMA'S REVENGE, PITFALL!, and PRIVATE EYE. In all three domains, our approach achieves more than 2x the reward of prior non-demonstration state-of-the-art approaches. In PITFALL!, we are the first to achieve superhuman performance without demonstrations, surpassing the prior state-of-the-art by over 100x. Additionally, since our approach is model-based, we can generalize to new rewards without re-training, as long as the reward function is a function of the abstract states. When evaluated on a new reward function never seen during training , our approach achieves over 3x the reward of prior state-of-the-art methods explicitly trained on the new rewards. This work presents a framework for tackling long-horizon, sparse-reward, high-dimensional tasks by using abstraction to decrease the dimensionality of the state space and to address compounding model errors. Empirically, this framework performs well in hard exploration tasks, and theoretically guarantees near-optimality. However, this work has limitations as well. First, our approach relies on some prior knowledge in the state abstraction function, although we compare against state-ofthe-art methods using a similar amount of prior knowledge in our experiments. This information is readily available in the ALE, which exposes the RAM, and in many robotics tasks, which expose the underlying state (e.g., joint angles and object positions). Still, future work could attempt to automatically learn the state abstraction or extract the abstraction directly from the visible pixels. One potential method might be to start with a coarse represention, and iteratively refine the representation by splitting abstract states whenever reward is discovered. Another limitation of our work is that our simple theoretical guarantees require relatively strong assumptions. Fortunately, even when these assumptions are not satisfied, our approach can still perform well, as in our experiments. A EXPERIMENT DETAILS Following Mnih et al. (2015) , the pixel concrete states are downsampled and cropped to 84 by 84 and then are converted to grayscale. To capture velocity information, the worker receives as input the past four frames stacked together. Every action is repeated 4 times.In addition, MONTEZUMA'S REVENGE and PITFALL! are deterministic by default. As a result, the manager deterministically navigates to the fringes of the known set by calling on the worker's deterministic, saved skills. To minimize wallclock training time, we save the states at the fringes of the known set and enable the worker to teleport to those states, instead of repeatedly re-simulating the entire trajectory. When the worker teleports, we count all the frames it would have had to simulate as part of the training frames. Importantly, this only affects wallclock time, and does not benefit or change the agent in any way. Notably, this does not apply to PRIVATE EYE, where the initial state is stochastically chosen from two similar possible states.A.1 HYPERPARAMETERS All of our hyperparameters are only tuned on MONTEZUMA'S REVENGE. Our skills are trained with the Adam optimizer BID19 with the default hyperparameters. TAB5 describes all hyperparameters and the values used during experiments (bolded), as well as other values that we tuned over (non-bolded). Most of our hyperparameters were selected once and never tuned.
We automatically construct and explore a small abstract Markov Decision Process, enabling us to achieve state-of-the-art results on Montezuma's Revenge, Pitfall!, and Private Eye by a significant margin.
{"src": "scitldr-AIC_train", "paper_id": "ryxLG2RcYX"}