Hardness in Markov Decision Processes: Theory and Practice
This work addresses the problem of benchmarking reinforcement learning methods for researchers, providing a principled benchmark to assess progress, though it is incremental in advancing from tabular to non-tabular settings.
The paper tackles the lack of standardized environments for analyzing reinforcement learning methods in hard settings by introducing Colosseum, a package for empirical hardness analysis, and benchmarks five tabular agents, showing that tabular hardness measures generalize to non-tabular versions.
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.