  Optimal action selection in decision problems characterized by sparse,
delayed rewards is still an open challenge. For these problems, current deep
reinforcement learning methods require enormous amounts of data to learn
controllers that reach human-level performance. In this work, we propose a
method that interleaves planning and learning to address this issue. The
planning step hinges on the Iterated-Width (IW) planner, a state of the art
planner that makes explicit use of the state representation to perform
structured exploration. IW is able to scale up to problems independently of the
size of the state space. From the state-actions visited by IW, the learning
step estimates a compact policy, which in turn is used to guide the planning
step. The type of exploration used by our method is radically different than
the standard random exploration used in RL. We evaluate our method in simple
problems where we show it to have superior performance than the
state-of-the-art reinforcement learning algorithms A2C and Alpha Zero. Finally,
we present preliminary results in a subset of the Atari games suite.
