We introduce a value-based RL agent, which we 64 call BBF, that achieves super-human performance in the Atari 100K benchmark. BBF relies on scaling 16 the neural networks used for value estimation, as well as a number of other design choices that 4 enable this scaling in a sample-efficient manner. We conduct extensive analyses of these design 1 choices and provide insights for future work. We 2015 2017 2019 2021 2023 end with a discussion about updating the goalposts for sample-efficient RL research on the ALE. Figure 1: Environment samples to reach human-level performance, We make our code and data publicly available.

Kernel matrices are popular in machine learning and scientific computing, but they are limited by their quadratic complexity in both construction and storage. It is well-known that as one varies the kernel parameter, e.g., the width parameter in radial basis function kernels, the kernel matrix changes from a smooth low-rank kernel to a diagonally-dominant and then fully-diagonal kernel. Low-rank approximation methods have been widely-studied, mostly in the first case, to reduce the memory storage and the cost of computing matrix-vector products. Here, we use ideas from scientific computing to propose an extension of these methods to situations where the matrix is not well-approximated by a low-rank matrix. In particular, we construct an efficient block low-rank approximation method---which we call the Block Basis Factorization---and we show that it has $\mathcal{O}(n)$ complexity in both time and memory. Our method works for a wide range of kernel parameters, extending the domain of applicability of low-rank approximation methods, and our empirical results demonstrate the stability (small standard deviation in error) and superiority over current state-of-art kernel approximation algorithms.