  High-dimensional observations and complex real-world dynamics present major
challenges in reinforcement learning for both function approximation and
exploration. We address both of these challenges with two complementary
techniques: First, we develop a gradient-boosting style, non-parametric
function approximator for learning on $Q$-function residuals. And second, we
propose an exploration strategy inspired by the principles of state abstraction
and information acquisition under uncertainty. We demonstrate the empirical
effectiveness of these techniques, first, as a preliminary check, on two
standard tasks (Blackjack and $n$-Chain), and then on two much larger and more
realistic tasks with high-dimensional observation spaces. Specifically, we
introduce two benchmarks built within the game Minecraft where the observations
are pixel arrays of the agent's visual field. A combination of our two
algorithmic techniques performs competitively on the standard
reinforcement-learning tasks while consistently and substantially outperforming
baselines on the two tasks with high-dimensional observation spaces. The new
function approximator, exploration strategy, and evaluation benchmarks are each
of independent interest in the pursuit of reinforcement-learning methods that
scale to real-world domains.
