  Conventional reinforcement learning (RL) algorithms exhibit broad generality
in their theoretical formulation and high performance on several challenging
domains when combined with powerful function approximation. However, developing
RL algorithms that perform well across problems with unstructured observations
at scale remains challenging because most function approximation methods rely
on externally provisioned knowledge about the structure of the input for good
performance (e.g. convolutional networks, graph neural networks, tile-coding).
A common practice in RL is to evaluate algorithms on a single problem, or on
problems with limited variation in the observation scale. RL practitioners lack
a systematic way to study how well a single RL algorithm performs when
instantiated across a range of problem scales, and they lack function
approximation techniques that scale well with unstructured observations.
  We address these limitations by providing environments and algorithms to
study scaling for unstructured observation vectors and flat action spaces. We
introduce a family of combinatorial RL problems with an exponentially large
state space and high-dimensional dynamics but where linear computation is
sufficient to learn a (nonlinear) value function estimate for performant
control. We provide an algorithm that constructs reward-relevant general value
function (GVF) questions to find and exploit predictive structure directly from
the experience stream. In an empirical evaluation of the approach on synthetic
problems, we observe a sample complexity that scales linearly with the
observation size. The proposed algorithm reliably outperforms a conventional
deep RL algorithm on these scaling problems, and they exhibit several desirable
auxiliary properties. These results suggest new algorithmic mechanisms by which
algorithms can learn at scale from unstructured data.
