  Meticulously analysing the empirical strengths and weaknesses of
reinforcement learning methods in hard (challenging) environments is essential
to inspire innovations and assess progress in the field. In tabular
reinforcement learning, there is no well-established standard selection of
environments to conduct such analysis, which is partially due to the lack of a
widespread understanding of the rich theory of hardness of environments. The
goal of this paper is to unlock the practical usefulness of this theory through
four main contributions. First, we present a systematic survey of the theory of
hardness, which also identifies promising research directions. Second, we
introduce Colosseum, a pioneering package that enables empirical hardness
analysis and implements a principled benchmark composed of environments that
are diverse with respect to different measures of hardness. Third, we present
an empirical analysis that provides new insights into computable measures.
Finally, we benchmark five tabular agents in our newly proposed benchmark.
While advancing the theoretical understanding of hardness in non-tabular
reinforcement learning remains essential, our contributions in the tabular
setting are intended as solid steps towards a principled non-tabular benchmark.
Accordingly, we benchmark four agents in non-tabular versions of Colosseum
environments, obtaining results that demonstrate the generality of tabular
hardness measures.
