Hardness in Markov Decision Processes: Theory and Practice
Authors: Michelangelo Conserva
Paulo Rauber
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Hardness
Benchmarking

Abstract: 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 $\texttt{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 $\texttt{Colosseum}$ environments, obtaining results that demonstrate the generality of tabular hardness measures.

Hardness in Markov Decision Processes:
Theory and Practice
Michelangelo Conserva
Paulo Rauber
Queen Mary University of London London, United Kingdom
Queen Mary University of London London, United Kingdom p rauber@qmul. ac. uk
conserva@quul ac.uk uk
Abstract
Meticulously analysing the empirical strengths and weaknesses reinforcement learning methods in hard (challenging) environments essential inspire innova- tions and assess progress in the field. In tabular reinforcement learning, there is well-established standard selection of environments 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 to unlock the practical usefulness of this theory through four main contributions. First, we present sys- tematic survey of the theory of hardness, which also identifies promising research directions. Second, we introduce Colosseum, 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 bench- mark. While advancing the theoretical understanding of hardness non-tabular reinforcement learning remains essential, 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.
Introduction
Reinforcement learning studies a setting where an agent interacts with an environment by observing states, receiving rewards, and selecting actions with the objective of optimizing reward-based crite- rion. The field has attracted significant interest in recent years after striking performances obtained in board games [1] and video games [2, 3]. Solving these grand challenges constitutes pivotal milestone in the field. However, the corresponding agents require efficient simulators due to their high sample complexity, i.e.. the number of observations that they require optimize a reward-based criterion in an unknown environment. Outside of games, many important applications in healthcare, robotics, logistics, finance, and advertising can also be naturally formulated reinforcement learning problems. However, simulators for these scenarios may not be available, reliable, or efficient.
The development of reinforcement learning methods that explore efficiently has long been considered one of the most crucial efforts to reduce sample complexity. Meticulously evaluating the strengths and weaknesses of such methods is essential to assess progress and inspire new developments in the field. Such empirical evaluations are performed through benchmarks composed of a selection of environments and evaluation criteria. Ideally, this selection should be based on theoretically principled reasoning that considers the hardness of the environments and the soundness of the evaluation criteria.
In non-tabular reinforcement learning, where the number of states is large (and potentially infinite), there is no theory of hardness except for a few restricted settings. Consequently, the selection of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

environments in current benchmarks [4, 5] relies solely on the experience of their authors. Although such benchmarks are certainly valuable, there is no guarantee that they contain a sufficiently diverse range of environments and that they are effectively able to quantify agent capabilities. In contrast, in tabular reinforcement learning, where the number of states and actions is finite, a rich theory of hardness of environments is available. Perhaps surprisingly, a principled benchmark based on this theory has so far been absent. There are at least two reasons for this absence. First, these hardness measures have been developed to provide theoretical guarantees for reinforcement learning methods, and not considered as directly useful for practical purposes, Second, the lack of a unifying presentation and critical comparison between different measures has limited their potential impact.
The goal of this paper is to establish the importance of hardness measures outside the context of theoretical reinforcement learning and unlock their practical usefulness with four main contributions. In Section 2, we present systematic survey of the theory of hardness for Markov decision processes. This survey serves as an introduction, tutorial, and, equally importantly, identifies gaps in the current theoretical landscape that suggest promising directions for future work. In Section 3.1, we introduce Colosseum, a pioneering Python package that enables the empirical investigation of hardness and implements a principled benchmark for the four most widely studied tabular reinforcement learning settings. The selected environments aim to maximize diversity with respect to two important measures of hardness, thus providing a varied set of challenges for which a precise characterization of hardness is available. In Section 3.2, we present an empirical comparison between three theoretical, yet efficiently computable. measures of hardness. Our analysis provides insights into which aspects of hardness are best captured by each of the measures and identifies desirable qualities for future measures. Finally, in Section 3.3, we report the results of five agents with theoretical guarantees in our novel (principled) benchmark, which allows to empirically validate the quality of the selection methodology by demonstrating that harder environments effectively lead to worse performances.
Although this paper is concerned with the tabular setting, for which principled measures of hardness are available, we intend our contributions as milestones towards the future development of theoretical and empirical measures of hardness for non-tabular reinforcement learning. Accordingly, Section 3.1 shows how tabular hardness measures can be used in a widespread class of environments that includes non-tabular versions of the environments in the Colosseum benchmark, which enables studying how these measures relate to the performance of four agents from the non-tabe non-tabular bsuite benchmark [4].
2 Hardness in Theory
Section 2.1 introduces our notation and important definitions. Section 2.2 presents our survey of the theoretical landscape of measures of hardness, which includes novel categorization of existing measures. Section 2.2.3 highlights the weaknesses of existing measures and introduces the concept of complete measure of hardness, which we believe should be the focus of future developments.
2.1 Preliminaries
Let A ((X)) denote the set of probability distributions over a set X. A finite Markov decision process (MDP) is tuple M (8, A, P, Pu, R). where S is the finite set of states, A is the finite set of actions, P: S x A + ASS) is the transition kernel, Po E A(S) is the initial state distribution, and R: S x A + A ((O, 1J) is the reward kernel [6]. Given an optimization horizon T, a reinforcement learning agent aims to find a (possibly stochastic) policy π : S + A(A) that optimizes a reward- based criterion. The MDP M is unknown the agent but can be learned through experience. The interaction between the agent and the environment starts when the initial state 80 ~ Po is drawn. For any < t < T, the agent samples an action 0r (T:(s) from its current policy Tr, and the environment draws the next state St+1 P(st, az) and reward rt+1 ~ R(st, az). An MDP is episodic with time horizon H when the state 5t+1 is drawn from the initial state distribution whenever t ++1 O (mod H) and continuous otherwise. In the continuous setting, a factor y E (0, 1) is used to discount future rewards in the discounted setting, and future rewards are averaged across time in the undiscounted setting. For policy π,, an MDP M induces Markov chain [7] with transition probabilities P. (M) Eee T(u P(s' 8, a) whose stationary distribution is denoted by n²t MDPs can be classified into three communication classes [8]. An MDP is ergodic if the Markov chain induced by any deterministie policy is ergodie. An MDP communicating if, for every two
states s' e S. there is deterministic policy that induces a Markov chain where is accessible
2

---

from s' and vice versa, An MDP is weakly communicating when there is partition (C, S \ C) of the set of states such that, for every two states s, E C, there is deterministic policy that induces a Markov chain where is accessible from s' and vice versa, and every state E S \ C is transient in every Markov chain induced by any deterministic policy. Every ergodic MDP is communicating. and every communicating MDP is weakly communicating.
The episodic state-action value function is given by Qi (8,0):= : Ei=h+1 81 = 8, on =
and the episodic state value function is given by ep, (s) ;= E. (a 8) ST. (s. The dis-
counted state-action value function is given by (5 a) := E [2 7 rz 1800 0,00 - a). and the discounted state value function is given by (s) == E. T(a [ Q) (8, a). These expectations are taken w.r.t. the policy æ,, the transition kernel P. and the reward kernel R. In the undiscounted setting, the value of every state(-action) is the same, since rewards are averaged across infinite time
steps. In that case, we define the expected average reward as pm == limm T Σ E [re]. which also given by '² = (yx", RT), where R is vector such that R.- = E Bawn(s) (0, a) is the expected reward obtained when following from state 8. An optimal policy x' obtains maximum value for every state. We assume with little loss of generality that the optimal policy is unique. We drop the subscripts when the setting is clear from the context, and write to denote 'T" in superscripts.
The most widely studied performance criteria are the expected cumulative regret, which yields the regret minimization setting [9], and the sample efficiency of exploration, which yields the Probably Approximately Correct Reinforcement Learning (PAC-RL) setting [10]. In simple terms, the regret measures the loss in reward due to the execution of a sub-optimal policy. In contrast, the sample efficiency measures how many interactions the agent requires to approximately learn s* with high probability. The main difference between the two criteria is that the rewards obtained during the interactions with the MDP are not considered in PAC-RI., whereas all rewards contribute to the cumulative regret. Therefore, PAC-RL agents can generally afford more aggressive exploration.
2.2 Characterization of hardness
We distinguish the hardness of MDPs into two kinds of complexity, the visitation complexity and the estimation complexity. The visitation complexity relates to the difficulty of visiting all the states, and the estimation complexity relates to the discrepancy between the optimal policy and the best policy an agent can derive from given estimate of the transition and reward kernels. The two complexities are complementary in the sense that the former quantifies the hardness of gathering samples from the state space while the latter quantifies the hardness of producing highly rewarding policy given the samples. In the literature, we identify two approaches that aim to capture the mentioned complexities. The first approach, which we call Markov chain-based, considers that an MDP is an extension of a Markov chain where transition probabilities can be changed based on direct interventions by an agent [1]]. This approach is well suited to capture the hardness that comes from the visitation complexity since considers the properties of transition kernels. The second approach, which we call value-based, considers the discrepancy between the optimal policy and the best policy an agent can derive from a value function point estimate. Note that the information contained in such point estimate is lower than the one in kernels estimate and that the difficulty of obtaining an accurate estimate of the value function is not considered in this approach. Therefore, the based approach is only able to partially capture the estimation complexity. A striking fact that highlights this shortcoming is that almost every value-based measure of hardness is independent of the variability of the reward kernel. Therefore, given an MDP M' that is obtained by increasing the reward kernel variability of an MDP M, value- based measures of hardness assign the same level of hardness to M and M'.
Markov chain properties and value functions depend on fixed policy, which presents two natural choices to derive measures of hardness. The first choice considers the optimal policy, which typically leads measure that considers best-case scenario. The second choice considers policy that maximizes a criterion that characterizes a worst-case scenario. For instance, a policy that maximizes such criterion may spend its time in a region of the state space that is not relevant for learning x².
3

---

2.2.1 Markov thain-based measures of hardness
Mixing time. The mixing time of a Markov chain with stationary distribution is defined as
4 == (n sup drv (P' ()) S 0.25]:
.ES
where drv is the total variation distance between distributions and the vector p" represents the distribution over states after n steps starting from state s. The value 0.25 is conventionally established in the Markov chain literature for the definition of the mixing time. For ergodic and aperiodic Markov chains, lit P. μ for every state 8, so the mixing time is the number of steps a Markov chain takes to produce samples that are close to being distributed according to the stationary distribution μ..
For instance, a Markov chain with non-negligible probability of transitioning from every state to every state is quickly mixing. In contrast, the mixing time can be very long in chains where the state space has several distinct regions each of which is well connected but where transitions between regions have low probability [12]. Kearns and Singh [13] propose an extension of the mixing time to MDPs that considers the maximum mixing time across policies t == sup= Efr in the undiscounted setting. Although the mixing time plays an important role in that setting, since the average reward obtained by policy is given by p (n" RR), ), it is not generally good measure of hardness. First, does not capture the visitation complexity, since it neglects the fact that the agent may direct its exploration through choice of policy. Second, it does not capture any significant aspect of optimal policy estimation, which does not require stationary distribution samples from every policy.
Diameter.
The diameter is fundamentally related to the number of time steps required to transition between states. In the continuous setting, the diameter is most commonly defined as
D sup in,
$1
where T - is the expected number of time steps required to reach state 82 from state 81 when following policy æ [14]. Intuitively, D is the worst-case expected number of time steps required to transition between two states when following the best policy for that purpose. Related definitions
Dworst := sup sup T =--- and Dop == inf sup T - which imply D S Dop S Dwoest [15].
π #1
#1 #
In the episodic setting, we define the diameter by augmenting each state s with the current in-episode time step h and considering the diameter of this augmented MDP in the continuous setting. Note that Tū,, (1 can be larger than the episode length H. which means that (on average) more than one episode may be required to transition from state (s1, h1) to state (s2, h2). This happens whenever /12 < h,, which may be undesirable the intent is to focus on the expected number of time steps required to transition between states from the same episode. The diameter is always infinite in makly-coommniicatin MDPs if the supremum is not restricted to states in the recurrent class C and is always finite in the episodic setting (where every state is reachable within an episode). A large diameter can be caused by high stochasticity. The diameter is very apt at measuring visitation complexity, since it captures the effort required to deliberately move between states. However, it neglects the reward kernel, and so has limited capacity to measure the estimation complexity.
Distribution mismatch coefficient. The distribution mismatch coefficient (DMC) has been defined for the continuous undiscounted [16] and continuous discounted [17] cases respectively as
d'
DMC : sup Σ
and DMC = sup SES Pa(#))
where d", (s) (1 77) Σe PPr(s s
| so) is the discounted state visitation distribution of the optimal policy given an initial state sg. Note that the DMC is guaranteed to be finite only for ergodic MDPs In communicating MDPs, there is at least one policy я whose stationary distribution assigns probability zero to some states. MDPs whose optimal stationary distribution μ² has its probability mass concentrated on few states tend to have a large DMC. In contrast, when μ²" is closer to being uniformly distributed across states, the DMC tends to be small. For small values of DMC, as every n1 is close to 1²", the agent will gather samples from the optimal stationary distribution regardless of its current policy, which may enable quick learning. contrast, for large values of DMC, the agent needs to actively seek policy that gathers such samples. The DMC is not well suited to quantify

---

the visitation complexity, since it fails to capture the difficulty of visiting all states. The DMC also does not capture the estimation complexity, since it does not account for the stochasticity of the environment, which is related to the number of samples required to make accurate estimations.
2.2.2 Value-based measures of hardness
Action-gap regularity. Given an estimate Q* of the optimal state-action value function Q", the greedy policy with respect to Q" always chooses an action associated with the highest state-action value. Whether or not such a policy is optimal depends exclusively on the ordering of the estimates for given state rather than their accuracy. For instance, assuming that a" is the optimal action for every state greedy agent would act optimally if ((saa)) (ss, a') for every action a' + a", even if [Q* (s, a) (s.. a)l >> for every action The action-gap regularity is measure of hardness that leverages this principle through the theory of hardness for classification algorithms [18]. However, this measure is only defined for two actions, and has exceptionally limited applicability.
Environmental value norm.
The (discounted) environmental value norm C7 is defined as
C7 = sup Var (5" (s,a) P(m,())))
This quantity can be similarly defined in the undiscounted setting [19]. In words, the environmental value norm captures the one-step variance of the value function V for a given policy т. In the episodic setting, closely related measure called maximum per-step conditional variance Cf [20] is defined as
C#
== sup (s,a.))
Vaar (Var R(s,a)
Var s'mP(s,a)
V 18))
Alternatively, as with the diameter, it is also possible to define this quantity by augmenting each state with the current in-episode time step h and considering the environmental value norm of this augmented MDP in the continuous setting. For every policy, the environmental value norm is equal zero when the transition kernel is deterministic. However, a highly stochastic MDP may still have small environmental value norm, since this norm captures the variance of the state value function rather than the stochasticity the transition kernel. Maillard et al. [19] suggest using the environmental value norm of the optimal policy x² as measure of hardness. The main strength of such measure is that the variability of the optimal value function captures an important aspect of the estimation complexity. However, this measure of hardness neglects the visitation complexity.
Sub-optimality gap. The sub-optimality gap is defined in the continuous and episodic settings as
Ass, a) = (s) (s, and (s == V7 (T,,a)..
respectively. Since V7 = max, (* a) for every state the sub-optimality gap A(s a) mea- sures the difference expected return between selecting the optimal action for state s and selecting the action Intuitively, identifying suboptimal action a' in given state s is easier if the gap A(s, a') large. Simchowitz and Jamieson [21] identifies the sum of the reciprocals of the sub-optimality gaps (ss A(s,aJ measure of hardness. They also demonstrate the importance of the sub-optimality gaps by showing that recent optimistic algorithms necessarily incur in cumulative regret proportional to the smallest nonzero sub-optimality gap in the episodic setting. However, note that approximating the optimal value function (and identifying near-optimal policy) is particularly easy when every sub-optimality gap is small. Consequently, the (PAC-RL) sample complexity is likely decrease when the sum of the reciprocals of the sub-optimality gaps increases. Furthermore. this measure does not explicitly capture visitation complexity and is prone to severe numerical issues.
Table 1: Computational complexity of generally applicable measures up to logarithmic factors.
Markov chain-based measures
Value-based measures
Mixing time
Diameter
Distribution mismatch coefficient
Environmental value norm
Sub-optimality gaps
((
O([S) -)
Ö(SF)AA(1 - -)
5

---

2.2.3 Future directions
Current hardness measures suffer from three principal issues. They are not designed to be efficiently computable (see Table and Appendix B), they are limited in their ability to simultaneously capture visitation complexity and estimation complexity, and they are oblivious to the distinct challenges presented by different performance criteria. For instance, while regret minimizing agents must be cautious not to incur in large regret during learning (for example, by not revisiting lowly rewarding states that are not followed by highly rewarding states), PAC-RL agents have the flexibility to incur in large regret long as they end up with a near-optimal policy. Therefore, the visitation complexity should differ across settings. The fact that current measures disregard this distinction is concerning, since they should account for the specific difficulty of the optimization task. These issues not discussed in previous work, since measures of hardness have not been considered relevant outside the context of deriving theoretical performance guarantees for reinforcement learning agents.
In order to address these issues, we believe that future work should focus on developing efficiently computable (non-trivial) hardness measures that (approximately) meet the following novel definition.
Definition 2.1 (Complete measure of hardness) A measure 0 .M- - R- is complete for an MDP class M and criterion eb (sample complexity or cumulative regret) if, for every pair M1, M2 E M and near-optimal agent A that achieves the criterion lower bound of class M up to logarithmic factors! (M1) > ((2)) implies (M1 A+) (M2, A"), where v hides logarithmic factors.
Combining existing measures that capture visitation complexity and estimation complexity is a viable first step in that direction. Recently, Wagenmaker et al. [23] have pioneered this approach in the episodic setting by proposing the gap-visitation complexity,
GVP(E) = Σ inf inf
H
1
(x)
(3)
W (s, a) (s)
"
1=0
where as, == (sh 5,00 a) is the probability of visiting state-action pairs (s,a) a) at in-episode time step h when following policy `, (s) == sup, P= (s,, = s) is the maximum reachability of state output policy in the PAC-RL setting. The strength of this measure is that it weights the sub-optimality action gaps with measures of visitation complexity, Wß. and Wn. This captures the difficulty induced by the critical states that are both hard to reach and for which it is hard to estimate the best action. However, the gap-visitation complexity fails to be a generally applicable hardness measure. It depends on the PAC-RI. setting-specifer parameter 6, it is restricted to the finite horizon setting (and can not be extended to the continuous setting), and not efficiently computable.
in-episode time step h, and is parameter related to the optimality of the
3 Hardness in Practice
3.1 Colosseum
This section briefly introduces Colosseum, a pioneering Python package that bridges theory and practice in tabular reinforcement learning while also being applicable in the non-tabular setting. More details about the package can be found in Appendix A and in the project website.?
As a hardness analysis tool, Colosseum identifies the communication class of MDPs, assembles insightful visualizations and logs of interactions between agents and MDPs, computes three measures of hardness (environmental value norm, sum of the reciprocals of the sub-optimality gaps, and diameter, whose computation requires novel solution described in App. A.4). Eight MDP families are available for experimentation. Some are traditional families "RiverSwin im [24], Taxi [25], and FrozenLake) while others are more recent (MiniGid environments [26]). Additionally, DeepSea [27] was included as a hard exploration family of problems, and the SimpleCr id family is composed of simplified versions of the MG- HG--mmpyy environment. By controlling the parameters of MDPs from each family (further detailed in App. A.3), it is easy to create an MDP with any desired hardness.
As benchmarking tool, Colosseum is unique in its strong connection with theory. For instance, in contrast to non-tabular benchmarks, Colosseum computes theoretical evaluation criteria such
I For example, the [( 2) sample complexity bound for the episodic communicating setting [22].
Available at htttp:::/michhhlaage.leaa wtw.ooooooore....iaiiooeeeeeeeee Colooossm

---

as the expected cumulative regret and the expected average future reward, which can be used to exactly evaluate the performance criterion of regret minimizing agents. The benchmark covers the most commonly studied reinforcement learning settings: episodic ergodic, episodic communicating, continuous ergodic, and continuous communicating. For each setting, we have selected twenty MDPs that are diverse with respect to their diameters and environmental value norms as proxies for different combinations of visitation complexity and estimation complexity. Figure 17 in Appendix shows how each of these MDPs varies according to these measures, and Section 3.3 empirically validates this selection by showing that harder MDPs correspond to worse agent performance. Notably, the theoretically backed selection of MDPs and the rigorous evaluation criteria make the Colosseum benchmark the most exhaustive in tabular reinforcement learning, since previous evaluations were conducted empirically in a few MDPs (such as Taxi or RiverSwim).
Col osseumm also allows testing of non-tabular agents by leveraging the BlockMDDP model [28]. BlockMDPss equip tabular MDPs with an emission map that is (possibly stochastic) mapping q S - (O) from the finite state space S to a (possibly infinite) observation space O. Agents interacting with BlockMDPs are only provided with observations, non-tabular methods are generally required. Many commonly used non-tabular MDPs (such as Minecraft [29]) can be straightforwardly encoded as BlockMDPs using the Colosseum MDP families. Colosseum implements diverse set of deterministic emission maps and allows combining them with different sources of noise. Appendix A.2 further details BlockMDPs and the available emission maps.
3.2 Empirical analysis of hardness measures
For brevity, this section only presents results of hardness measures in the MiniGrid family of environments in the episodic setting. Appendix D presents the full outcome of the empirical analysis.
A MiniGridEmpty MDP is a grid world where an agent has three available actions: moving forward, rotating left, and rotating right. An agent is rewarded for being in a few specific states and receives no reward in every other state. Appendix A.3.4 provides more details about this family of environments.
In our investigation, we consider four scenarios that highlight the different aspects of MDP hardness.
Scenario 1. We vary the probability p_rand that an MDP executes a random action instead of the action selected by an agent. As p_rand approaches one, value estimation becomes easier, since outcomes depend less on agent choices. However, intentionally visiting states becomes harder.
Scenario 2. We vary the probability p_lazy that an MDP stays in the same state instead of executing the action selected by an agent. Contrary increasing p p_rand, increasing p_ p_lazy never benefits exploration. Increasing p_lazy decreases estimation complexity and increases visitation complexity.
Scenario 3 and 4. We vary the number of states across MDPs from the same family. In scenario 4, we also let p_raadd= = 0.1 to study the impact of stochasticity. these scenarios, increasing the number of states simultaneously increases the estimation complexity and the visitation complexity.
In every scenario, hardness measures are compared with the cumulative regret of a near-optimal agent tuned for each specific MDP (see App. D). This regret serves as an optimistic measure of hardness. Appendix C describes how these measures are normalized. Note that, due to normalization, the plots should only be compared in terms of trends (growth rates) rather than absolute values.
Analysis. Figure/ presents the empirical results for the episodic MiniGridEmptyy family in the four scenarios with 95% bootstrapped confidence intervals over twelve random seeds.
The experiments confirm our claim that the diameter captures visitation rather than estimation complexity. This measure of hardness grows superlincarly with both p_rand and p_lazy (Figures la and lb) since deliberate movement between states requires an exponentially increasing number of time steps. Although the diameter highlights the sharply increasing visitation complexity, its trend overestimates the increase in cumulative regret of the tuned near-optimal agent, which is explained by the unaccounted decrease in estimation complexity. The diameter also increases almost linearly with the number of states (Figures le and Id). For the small p_ rand (scenario 4), the relation is still approximately linear. This linear trend underestimates the evident non-linear growth in hardness in the regret of the tuned near-optimal agent but is in line with the mild increase in visitation complexity.
The empirical evidence indicates that the environmental value norm can only capture estimation complexity. It decreases p p_lazy and p_rand increase (Figures la and 1b) because the optimal
7

---

Diameter
Envionmental
Sum of the reciprorals of the sin-optirallyy gaps
Cumulative of tuned reasapimal agent
0.8
Nomatzed
0.6
0.4
0.0
0.4
0.4
100
200
100
Probability random action
Probability Iazy action
Number states
of states
(a) Scenario
(b) Scenario
Scenario
Scenario
Figure I: The Colosseum hardness analysis for the episodic MiniGrid (Empty family.
value of neighboring states becomes closer, which decreases the per-step variability of the optimal value function. When the number of states increases but the transition and reward structures remain the same (Figures Ic and ld), the small increase in this variability only generates a sublinear growth.
We empirically observe that the sum of the reciprocals of the sub-optimality gaps is not particularly apt at capturing estimation complexity, due to its exclusive focus on optimal policy identification, and it also underestimates the increase in hardness induced by an increase in visitation complexity. This measure increases weakly superlinearly in scenarios and 2 (Figures la and lb). The probability of executing the action selected by the agent decreases when p_ p_lazy and p p_rand increase, so the difference between the state and the state-action optimal value functions decreases sharply. The measure increases almost linearly with the number of states (Figures Ic and 1d). This is explained by the fact that the average value of the additional terms in the summation is often similar to the average value of the existing terms when MDPs have the same structure of reward and transition kernels.
3.3 Colosseum benchmarking
In this section, we benchmark five tabular agents with theoretical guarantees and four non- non-tabular agents. Besides being valuable on their own, these results help to empirically validate our benchmark.
Agents. The tabular agents posterior sampling for reinforcement learning (PSRL) for the episodic and continuous settings [30, 31]. Q-learning with UCB exploration for the episodic setting [32], Q-learning with optimism for the continuous setting [16]. and UCRL2 for the continuous setting [14]. The non-tabular agents (from bsuite) are ActorCritic, ActorCriticRNN, BootDQN, and DQN.
Experimental procedure. We set the total number of time steps to 500 000 with maximum training time of 10 minutes for the tabular setting and 40 minutes for the non-tabular setting. If an agent does not reach the maximum number of time steps before this time limit, learning interrupted, and the agent continues interacting using its last best policy. This guarantees a fair comparison between agents with different computational costs. The performance indicators are computed every 100 time steps. Each interaction between an agent and an MDP is repeated for 20 seeds. The agents' hyperparameters have been chosen by random search to minimize the average regret across MDPs with randomly sampled parameters (see Appendix E). We use a deterministic emission map that assigns uniquely identifying vector to each state (for example, gridworld coordinate) to derive the non-tabular benchmark MDPs. In Table 2, we report the per-step normalized cumulative regrets divided by the total number of time steps (defined in Appendix C), which allows comparisons across different MDPs We summarize the main findings here and refer to Appendix E. for further details.
Analysis. Table 2 often shows high variability in the performance of the same agent across MDPs of the same family. Therefore, maximising the diversity across diameters and value norms effectively produces diverse challenges even for MDPs with similar transition and reward structures. For example, in the continuous communicating case (Table 2d). Q-learning performs well only in some MDPs of the MiniGri MiniGridEmpty dEmpty family. This also happens for UCRL2 for the SimpleGrin id family.
The average normalized cumulative regret is lower in ergodic environments compared to commu- nicating environments. This indicates that the ergodic setting is generally slightly easier than the communicating settings. Notably, in the continuous setting, the ergodic setting is more challenging than the communicating setting for Q-leaming (Tables 2c and 2d). Designing naturally ergodic
8

---

Table 2: Normalized cumulative regrets of selected agents on the Colosseun benchmark. (a) Episodic ergodic. (b) Episodic communicating. (c) Continuous ergodic. (d) Continuous communicating.
(a)
(b)
(c)
(d)
Q-hommng
QHamminn
Q-koming
Quiraming
MDP
MDP
MDP Desphiaa
Docphen
B8:22 (N]
DeepSica
-00 =:
Dosphes
36 (1]
J00 1. 201
225-2.10 .6b
T8. 2. (8)
78 2.65
.002
25.1
FroessLake
.01
(1)
J99
MG Erett
FooesLake
1.00 10)
28 .15
300 Errpty
ProuedLake
.90 207
19:11 20
.09 2.6
24
MG-Eirptt
-88 112
06.22
35. 104
31: 033
J03 .16
Faocstaake
54 0 (14
-77 -M4
011 6:
04::t /06
.01
Mc-Rioppy
100
1.00 200
.11
180
00
002 60
1:01 (9)
44 112
1400 /20
101
18
-9- /00
-5. -35
000 180
00: -30
231 40
= 114
14: 05
M0-Btom
-21
18
03:-4 A01
-27- -58
-10 21
.55 0: 17
1,00 4.00
1.00
.01 :00
MG-Rooors
591:
1.00 200
.63
-50
MG-Roomr
390
118.4 220
MG--Roem
111 01
1.00 1.0
.75:2 40
100 00:--P0 ())
34% -5
51. 11:+-00
(11 D0
16:11
1.00 /00
072:1
356
01: 8: 011
1:00 /00
/2: 01
=:
RiveSkin
.00
(12 177
1:00 /00
46-4.
RiverSwin
.00
RiverSwite
366-
.00 00
SimpkGond
Strepeetivd
20.1 -00
75.
55
20
15
-14 221
J01 .00
192:1.
101 101
SimploGGrd
-54.5 114
11 (1
0:60
102
011
SipplGGnd
.70
Tao
-6:22 11.
08 011
Taxi
34:2.00
.09
-0
.43 200
.00
0012 (1)
32: 0:00
.8. 24
31.
.96
Tax
.09.
.66 (00
81.
23.4.25
.65
.56
317
07
.86
MDP is not straightforward. In fact, the majority of MDPs in the literature communicating. In Colosseum, ergodicity is induced by setting p_rand > in otherwise communicating MDPs. Model-free agents struggle with the resulting increase in variability of the state-action value function.
In the episodic settings (Tables 2a and 2b), PSRL obtains excellent performances with low variability. Q-laariig instead performs well in a few MDPs. This often happens since, when the action selected by the agent is randomly substituted (due to p_rand > 0) with one with a large sub-optimality gap, the resulting Q-value update introduces a critical error that requires many samples to be corrected.
In the continuous settings (Tables 2c and 2d), UCRL2 performs best in the ergodic cases when Q-learning suffers from the issue caused by p_rand > 0 but is only slightly better than Q-learning in the communicating ones. PSRL instead struggles with most MDPs. The reason for its weak performance in this setting is the computationally expensive optimistic sampling procedure required for its worst-case theoretical guarantees. It often breaks the time limit before reaching the first quarter of available time steps, meaning that it lacks sufficient samples to estimate the optimal policy.
Figure 2 places the regret of the agents in the continuous ergodic setting (Table 2c) on position corresponding to the diameter and value norm of the benchmark environments. PSRL and Q-learning (Figures 2a and 2b), appear be impacted more by the value norm than the diameter. This is in line with the lack of sufficient samples for PSRL and the aforementioned issue related to high q estimates variability for Q-learning, which exacerbated when the estimation complexity is higher. In the case of UCRL2 (Figure 2c), which provides more reliable evidence since it performs well across the MDPs, higher regret effectively corresponds higher diameter and value norm.
YC Spors (5)
NG Aoorm 100
NG Roamr 121
2.0
Empoy
MO Enteyy 211
MO Emetyy 21 MS Eniooy L00
MG Fr
1.2
Fooaro
MG Plvaro 21A
Rosmo 13)
ND Emary
MG Emply 131
Enrety
Emary
HiS Eneelt (2)
T brick
9e Emottyy IR
MiG vic.trptyii (2)
Sueetwi
Evees
of
Reirdwim 12
SoverSadm O
SimpraCns
IN: Smovy (T)
Saverdaim
orggy
Starrdalm 13)
mi lede di 291
MG (msty:
0.8
simpttcie
Sgro 101
Singleorid 12:
0.5
Frower
Tax 19
Prezenkaao 121
Ted 10
Too (0)
Din
Diameter
(2) PSRL
(b) Q O-leaming
[c UCRL2
Figure 2: Average cumulative regret obtained by the tabular agents with guarantees in the continuous ergodic setting placed according to the diameter and the value norm associated to the MDPs

---

Non-tabular benchmarking. The performance of the agents is in line with the results reported by Osband al. [4]. with the exception of BootDQN. Being the most computationally intensive. this agent often breaks the time limit, which consequently worsens its overall performance. Figure 3 places the regret of the agents in the continuous ergodic setting on position corresponding to the diameter and value norm of the benchmark environments. Interestingly, and similarly to the tabular case (Figure 2), while the best performing agent (DQN) is evidently impacted more by the diameter, the opposite holds for the other agents. Regardless of the visitation complexity, this suggests that an agent that fails to handle the estimation complexity of an environment is bound to perform badly both in the tabular and con-tabular settings.
2.00
1.73
1.00
0.25
Of
aeroese Si al tleerttt
altrevitee
3.50
9.25
20
40
60
100
20
40
CD
ED
100
22
62
82
100
20
00
200
Dumelerr
Charsstor
Diaradtr
Dirrster (6) DON
(A) ActorCritic
(6) ActovErRicRMN
(c) ReaDDON
Figure 3: Average cumulative regret obtained by the non non-tabular baseline agents in the continuous ergodic setting placed according to the diameter and the value norm associated to the MDPs.
4 Conclusion
We established the usefulness of the theory of hardness in empirical reinforcement learning. Prior to our work, hardness measures were limited to providing theoretical guarantees for agents. In order to promote a wider understanding of these measures, we presented a systematic survey that newly identified two major approaches for characterizing hardness: Markov chain-basel and value- based. These approaches aim to capture complementary aspects of hardness: visitation complexity and estimation complexity. Our survey also exposed relative lack of measures that capture both aspects, which motivates our definition of complete measures of hardness. Their development is important theoretically, elucidating what makes a problem hard for a specific performance criterion, and empirically, allowing the creation of principled benchmarks for a specific performance criterion.
We presented the first empirical study of (efficiently computable) hardness measures. This study revealed which aspects of hardness current measures capture and clarified their relationship with the behavior of near-optimal agents. Based these results, we proposed a benchmark for the most widely studied tabular reinforcement learning settings that contains environments that maximize diversity with respect to two highly distinet measures. Such a principled benchmark is valuable to gauge progress in the field. The new benchmark allowed conducting the most exhaustive empirical comparison between theoretically principled tabular reinforcement learning agents to date, which revealed undocumented weaknesses of these agents and further validated our choices of environments.
As first step towards principled non-tabular benchmarking, we argued that many commonly used environments can be encoded as BlockMDPs, which are non-tabular versions of tabular MDPs for which partial characterization of hardness is already possible. We observed a clear empirical relation between two tabular hardness measures and the performance of four non-tabular agents. BlockMDPs represent a promising starting point for the future development of non-tabular hardness measures while already being useful to provide relevant insights into the performance of non-tabulat agents.
Our work has led to the development of Colosseum, a pioneering tool for empirical but theoretically principled study of tabular reinforcement learning with experimental non-tabular benchmarking capabilities. Besides implementing the aforementioned tabular benchmark, Colosseum provides valuable analysis tools: regret and hardness computations, communication class identification, logging, and visualizations. Colosseum can also be easily extended and integrated with new agents and environments, for which we will actively seek contributions from the community. We strongly believe that Colosseum has the potential to become a fundamental tool in reinforeement learning.
10

---

Acknowledgments and Disclosure of Funding
This research was financially supported by the Intelligent Games and Games Intelligence CDT (IGGI; EP/S022325/1) and used Queen Mary University of London Apocrita HPC facility. The authors would like to thank Sjoerd van Steenkiste and Tabish Rashid for their valuable feedback.
References
[1] David Silver, Thomas Hubert, Julian Schrittwisser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018.
[2] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 2019.
[3] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1912. 2019.
[4] Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020.
[5] Raghu Rajan, Jessica Lizeth Borja Diaz, Suresh Guttikonda, Fabio Ferreira, André Biedenkapp. Jan Ole von Hartz, and Frank Hutter. MDP playground: A design and debug testbed for reinforcement learning. arXiv preprint arXiv: 190v00990.007700. 2019.
[6] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[7] David A Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Soc., 2017.
[8] LCM Kallenberg. Classification problems MDPs. In Markov processes and controlled Markov chains. Springer, 2002.
[9] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in Neural Information Processing Systems, 2006.
[10] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[11] Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, 1957.
[12] D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. Adaptive Computation and Machine Learning series. MIT Press, 2009.
[13] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 2002.
[14] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 2010.
[15] Peter Bartlett and Ambuj Tewari. REGAL: a regularization based algorithm for reinforcement learning weakly communicating MDPs. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference. AUAI Press, 2009.
[16] Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward Markov decision processes. In International Conference on Machine Learning. PMLR, 2020.

---

[17] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research, 2021.
[18] Amir Massoud Farahmand. Action-gap phenomenon in reinforcement learning. Advances in Neural Information Processing Systems, 2011.
[19] Odalric-Ambrym Maillard, Timothy A Mann, and Shie Mannor. How hard is my MDP? The distribution-nnrm to the rescue". Advances in Neural Information Processing Systems, 2014.
[20] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning. PMLR, 2019.
[21] Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. Advances in Neural Information Processing Systems, 2019.
[22] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- ned-hhoizonn reinforce- ment learning. Advances in Neural Information Processing Systems, 2015.
[23] Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference Learning Theory, pages 358-418.
PMLR, 2022.
[24] Alexander L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences, 2008
[25] Thomas G Dietterich. Hicrarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 2000.
[26] Maxime Chevalier-Boiswe Lucas Willems, and Suman Pal. Minimalistic Gridworld environ- ment for OpenAl gym.
com/maximeclb /gyb//ggmm-mmy minigrid, 2018.
[27] Ian Osband, Benjamin Van Roy, Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. Journal of Machine Learning Research, 2019.
[28] Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference Machine Learning, pages 1675-1674. PMLR, 2019.
[29] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International Conference on Machine Learning, pages
PMLR, 2020.
[30] Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) Efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 2013.
[31] Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 2017.
[32] Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? Advances in Neural Information Processing Systems, 2018.
[33] Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic Markov chains. In Proceedings of the Thirty-Second Conference on Learning Theory, Proceedings of Machine Learning Research, 2019.
[34] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o(agr()) iterations and faster algorithms for maximum flow. arXiv preprint 1rXiv:1312.6677, 2013.
[35] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, 2018
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] In the introduction, explain where each contribution is described in the text. The same contributions are mentioned in the abstract. In the conclusion, we also present concrete list of contributions.
(b) Did you describe the limitations of your work? [Yes] We describe the assumptions behind every theoretical measure of hardness. The results of our empirical investigation are naturally limited the environments, measures, and agents that we considered. Nevertheless, we believe that the experimental protocol described in Appendices D and is very robust. The remaining limitations are discussed as potential future works.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not envision potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We explicitly mention the full set of assumptions involved in theoretical results and report relevant references when appropriate.
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We include We describe the experimental procedures for the
a link to the code in Section empirical evaluation of the measures of hardness in Section 3.2 and for the Colosseum benchmark evaluation Section 3.3. We refer to the corresponding appendices (Apps. D and E) for additional details.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] The details for the empirical evaluation of the measures of hardness and the Colosseum benchmark evaluation are provided in Appendices D and
E.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report 95% bootstraped confidence intervals in the plots and standard deviations in the tables.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] These details are provided in Appendices D and E.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We describe all the dependencies of Coloaseus in Appendix A.
(b) Did you mention the license of the assets? [No] However, all these assets are open-
source and freely available.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] The code of our newly proposed Python package (Colosseum) is included in link in Section 3.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
13

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14

---

A Colosseum
Colosseum is a pioneering Python package that creates a bridge between theory and practice in labular reinforcement learning with an eye on the non-tabular setting. It allows to empirically, and efficiently, investigate the hardness of MDPs, and it implements the first principled benchmark for tabular reinforcement learning algorithms. In the following sections, we report some additional details on the capabilities of Colosseum. However, we invite the reader to check the latest online documentation along with the tutorials that cover in detail every aspect of the package.
A.1 Expected performance indicators
Each agent in Colosseum is required to implement function that returns its current best policy estimate #. for any time step t. Using an efficient implementation of the policy evaluation algorithm, Colosseum can compute the corresponding expected regret and expected average reward, which, summed across time steps, amounts to the expected cumulative reward and expected cumulative regret. Although it is possible to perform this operation every time step of the agent/MDP interaction, we leave the option to approximate the expected cumulative regret by calculating the expected regret every n time steps and assuming that the policy of the agent the previous n 1 time steps would have yielded a similar expected regret. For instance, for n = 100, the expected cumulative regret at time step T 500 would be approximated as the sum of the expected regrets calculated at time steps t = 100, 200, 500 multiplied by 100.
A.2 Non-tabular capabilities
Colosseum is primarily aimed at the tabular reinforcement learning setting. However, as ultimate goal is to develop principled non-tabular benchmarks, we offer a way to test non-tabular reinforcement learning algorithms on the Colosseum benchmark. Although our benchmark defines challenge that is well characterized for tabular agents, we believe that it can provide valuable insights into the performance of non-tabular algorithms. In order do so, we adopt the BlockMD)P formalism proposed by Du et al. [28]. A BlockMDP is a tuple (S, A, P. Po. R, O q). where O and S + AOO) are respectively the non-tabular observation space that the agent observes and the (possibly stochastic) emission map that associates a distribution over the observation space to each state in the MDP. Note that the agent not provided with any information on the state space S. Colosseum implements six deterministic emission maps with different properties and four kinds of noise to make the emission maps stochastic, which we describe below. Examples of the emission maps with distinguishable characteristics for each MDP family will be presented in the corresponding sections.
Emission maps:
One-hot encoding. This emission map assigns to each state a feature vector that is filled with zeros with the exception of an index that uniquely corresponds to the state.
Linear optimal value. This emission map assigns to each state a feature vector Φ(s) that enables linear representation of the optimal value function. In other words, there is 6 such that (s) = ((s).
Linear random value. This emission map assigns to each state a feature vector ((s) that enables linear representation of the value function of the randomly acting policy. In other words, there is a such that VT (s) = 6T d(s). where π is the randomly acting policy.
State information. This emission map assigns each state a feature vector that contains uniquely identifying information about the state (c.g., coordinates for the DeepSea family).
Image encoding. This emission map assigns to each state a feature matrix that encodes the visual representation of the MDP as grayscale image.
Tensor encoding. This emission map assigns to each state tensor composed of the concatenation of matrices that one-hot encode the presence of a symbol in the corresponding indices. For example, for the DeepSea family, the tensor is composed of a matrix that encodes the position of the agent and matrix that encodes the positions of white spaces.
Noise:
Available attttpsr//ssceellaggoooooorrrrr github. 1o/ooosseemm
15


Reviews:
[{"review_id": "xhVf2q_wc8", "reviewer": "Reviewer_XzpS", "summary": "This work provides a unifying review of hardness measures for MDPs that have appeared in previous RL theory bounds in tabular settings. The authors have also developed a benchmark with easily estimable values for these hardness measures to be used for empirical investigation of RL theory. Performance of four standard algorithms are measured in the environments.", "questions": "How were environments selected from the literature? Was any attempt made to construct novel MDPs with particular relationships between hardness measures? What limited this process if so?", "limitations": "As suggested above, the insight here is mainly unifying, with little specific novel contributions, either in terms of environment or in terms of analysis. New measures of hardness, or previously unseen environments with useful properties would make the paper very strong.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Originality:*\nThe work provides a unifying perspective on what has thus far been seen as disparate notions of hardness, with qualitative comparison of the strengths and weaknesses of each. I think that, while no new notion of hardness is investigated here, which would make this a very strong paper, the perspective offered is novel and worthwhile. The development of a standard tabular benchmark for RL theory is again a work of synthesis from previous papers. While valuable for RL theory practitioners, there is less novel insight here, as these environments are well known.\n\n*Quality:*\nThe paper is clearly well-thought through and well constructed, with unifying insight provided. I think if the environments weren't chosen from the literature, but instead chosen such that the different aspects of hardness described in the paper were easier to control independently with respect to the different policy and environment parameters described in the paper, the benchmark would lead to even more meaningful insight.\n\n*Clarity:*\nThe paper is easy to follow, and plots and charts are easy to read. The visualisations of the environments give good intuition as to their structure, and the experiments give good characterisation of their hardness.\n\n*Significance:*\nThe paper is significant, and well-poised to enable future work in unified hardness and empirical evaluation of RL theory results.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fVyzK749QP-", "reviewer": "Reviewer_cqd5", "summary": "This paper reviews and categorizes some hardness measures on tabular MDPs, and proposes a new tabular RL benchmark named \"Colosseum\" that enables exact computation of these measures in empirical evaluations. Extensive experiments are conducted to assess the performance of existing tabular RL methods on the proposed benchmark that spans diverse environments focusing on different hardness measures.", "questions": "1. The authors wrote in the paper \"we believe our contributions are important milestones towards the future development of theoretical and empirical measures of hardness for non-tabular reinforcement learning\". However, it is not clear how the measures presented in the paper can be extended to non-tabular settings (while still being computationally feasible). Adding more discussion on this point can be helpful.\n2. The paper surveys existing hardness measures by dividing them into two categories, namely \"Markov chain-based\" which focuses on the state visitation complexity, and \"value-based\" which focuses on the estimation complexity of value functions. It seems like this taxonomy is closely relevant to the well-known \"exploitation-exploration\" dilemma with state visitation complexity capturing the difficulty in exploration, and estimation complexity capturing the difficulty in exploitation. The authors are encouraged to discuss this relation in more detail.\n3. The message conveyed by Definition 2.1 is somewhat vague: it is not clear to me how this \"complete measure\" connects to the intuition or other theoretical arguments that capture the \"hardness\" of learning a near-optimal policy on an MDP, e.g., the PAC learnability. In other words, is there any conceptual/theoretical evidence implying that this hardness measure is _sufficient_ in the sense of some criteria? Also, while I can understand that existing measures may be insufficient in measuring all aspects of hardness since they either focus on the state visitation complexity or the estimation complexity, can we use Definition 2.1 to certify this?", "limitations": "No concern.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The paper suggests an interesting viewpoint of connecting the theory and practice of tabular RL by taking into account the hardness measures that are typically used only in theoretical analysis when evaluating and comparing tabular RL algorithms.\n2. The \"Colosseum\" benchmark is of high quality, flexible, and with sufficient docs and tutorials.\n3. The empirical evaluations are thorough.\n4. The paper is well organized and presented. \n\n### Weaknesses\n1. The benchmark and the hardness measures only apply to tabular RL. In contrast, most of the current empirical work in RL is devoted to the non-tabular setting, and there is also an increasing number of theoretical work that explores non-tabular RL.\n2. The theoretical claims made by this paper are somewhat vague (see the following for details).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UtpuGDcSVHT", "reviewer": "Reviewer_QBF7", "summary": "This paper first presents a survey of existing hardness measures and results from the MDP literature. Their main contribution is the introduction of `Colosseum`, which is a benchmark for empirically validating hardness results, which they use to compare various existing hardness measures.", "questions": "1. Is all of section 2 just a review of existing literature? It seems like this is the case, but just wanted to confirm.\n2. In line 72 it says \"Given an optimization horizon $T$\". What is this exactly? Is it related to episodic horizon?\n3. In lines 99-100 it says there is an assumption of the existence of an optimal policy $\\pi^*$ that \"obtains maximum value for every state\", but this policy will necessarily be dependent on time as well as state, no?\n4. Why do you use the value of $0.25$ in equation (1)? This is not justified in the text.\n5. Below line 186, $\\gamma$ is a subscript of $C$ on the left-hand side, but it does not appear in the right hand side. Should it? Or should it be removed from $C$?\n6. In lines 206-208 it says \"approximating the value function ... is particularly easy when every sub-optimality gap is small.\" This is not necessarily the case in RL: sub-optimality gap is with respect to the optimal policy, but in RL we don't start from the optimal policy.\n7. In lines 374-375 you say your empirical investigations \"revealed previously undocumented weaknesses of these agents and further validated our choices of environments.\". What does this say about existing empirical work evaluating these algorithms?", "limitations": "Some limitations are provided (mostly related to future work). It would be nice to have some discussion regarding the significance/impact (or lack thereof) of this work, in line with some of the comments I made above regarding significance.\n\nNo discussion of potential negative societal impact was provided.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\nIt seems to me that section 2 (Hardness in Theory) is a review of existing literature, so the original contributions of this paper would be limited to the `Colosseum` package and the empirical investigations provided. For these, the work is original as far as I can tell, although some of the claims seem to be a bit inflated (e.g. \"a pioneering Python package\", \"the most exhaustive in tabular reinforcement learning\", \"invaluable analysis tools\", etc.).\n\n# Quality\nThe authors have done a reasonably thorough survey of hardness literature and evaluated these measures using the various environments in their package. There are a few issues regarding clarity and correctness that I include in the questions below.\nThe code for `Colosseum` seems to be well-written and well-documented, which I consider to be a core part of this paper's contribution.\n\n# Clarity\nThe paper is very well written and motivated reasonably well. Some of the plots and tables are hard to digest; specifically, it's often not clear _what_ is being said with them. There's a lot going on in Figure 1 (and even more in Table 1), and even though the main takeaways do seem to be discussed in the text, they're mostly lost in the paragraphs in page 7 (it seems that the last sentence is the main takeaway for each hardness measure). I would suggest highlighting these in a more streamlined manner (to draw the reader's attention directly to the takeaways) and leave the descriptive text until after.\nTable 1 is a bit overwhelming, it's not clear what we're supposed to be looking for. I would also suggest rewriting this section so there are clear takeaways and insights for the readers; currently it reads just as a verbal description of the (many) numbers in the table.\n\nAlthough it is claimed that in Figure 2 \"there is generally a positive relationship between both of these hardness measures and the average cumulative regret\", it seems almost like points uniformly spread on the plane (i.e. I don't see a clear relationship at all).\n\nThere are a few other issues I mention in the questions below.\n\n# Significance\nThis, to me, is the weakest point of the paper. Although I appreciate the authors' effort to produce a nice package for benchmarking theoretical results, it's not clear how significant this will be. Empirical evaluations on toy environments (for theoretical results) are typically meant to highlight characteristics or subtleties of the theory introduced, but are not the end goal in itself. In particular, whether the empirical results suggest sub-linear or linear growth, say, does not in any way change the theoretical results. Thus, it is not clear what the added value would be to have a \"theory benchmark\".\nSomething that I think could make this package more impactful is to try to go beyond tabular. One suggestion would be to look at bsuite (which the authors do cite), as they include both tabular and continuous environments. In particular, it would be interesting to evaluate both as they may allow one to empirically investigate how the hardness measures vary when moving from tabular to larger systems. I acknowledge that in non-tabular systems it may not be possible to compute all of them in closed form, but there may be approximations; alternatively, continuous variants of the tabular systems considered could provide a nice middle ground (e.g. by \"smoothing out\" each tabular state).\nAnother aspect that could increase the significance of this work is to evaluate non-tabular methods, for instance with linear function approximators. A lot of RL theory does exist for linear approximators (and tabular, of course), so it would be interesting to evaluate how the dynamics of the empirical evaluations change (or not) when moving from tabular to non-tabular methods.\n\nAlong these lines, in line 366 it says \"The development of such measures is theoretically and empirically important.\". It would be nice to provide some concrete examples, such as a theoretical bound dependent on one of these hardness measures, or something like that. Otherwise it's not clear why these hardness measures are important.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OvjOS8S_1A9", "reviewer": "Reviewer_XAUr", "summary": "The paper introduces Colosseum, a Python package that allows empirical investigation of MDP hardness along estimation complexity and visitation complexity for tabular reinforcement learning. It surveys various existing harndess measures and argues why many of these do not capture the above mentioned complexities properly. The ones which come closest to capturing these are Environmental value norm for estimation complexity and Diameter for visitation complexity as I understand from the paper. It also implements agents and implements a benchmark for what the authors claim are the four most widely studied tabular reinforcement learning settings - which I believe are: (a) Episodic ergodic. (b) Episodic communicating. (c) Continuous ergodic. (d) Continuous communicating. They also perform experiments examining the hardness measures under various changes to the MPDs (Fig. 1) as also with the agents in the mentioned settings (Tab. 1 and fig. 2).\n", "questions": ">For instance, consider an MDP where a set of lowly rewarding states stands between an agent and a set of highly rewarding states. A regret minimization agent is heavily discouraged from visiting the lowly rewarding states, in contrast to a PAC-RL agent. Therefore, the state visitation complexity should differ across settings.\n\nI do not quite think this is the best argument here because if, let's say, the only way to the high-rewarding states is through the lowly rewarding states, then regret would still be minised by going through them and so the agent would not be discouraged.\n\n\n>The fact that current measures disregard this distinction is concerning, since they should quantify the difficulty of a specific optimization task.\n\nWhat is \"this distinction\" here?\n\nWhat is \"the criterion lower bound of class M up to logarithmic factors\"?\n\nIn line no. 274: \"the probability p_lazy that an MDP stays in the same state instead of executing the action selected by an agent\"\n\nHow can the MDP remain in the same state if an action was taken? Is there a \"no-op\" action as well in the action space? I saw only 3 actions in the action space and no no-op.\n\n\"which solely allows comparing trends\"\n\nwhy is solely italicised here?\n\nHow did the authors choose twelve and five random seeds for the experiments?\n\nThe paper mentions both cumulative regret and sample efficiency for exploration as possible performance criteria/metrics but then only experiments with cumulative regret agents are shown. Is there a reason sample efficiency for exploration was not considered for the experiments?\n\n", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe they motivate the approach well and the benchmark is more comprehensive than existing benhcmark for tabular RL. The quality of the woek also seems high. They provide code and collect it in a single package which should be of great significance to the community, esp. but not just the tabular RL communtiy. I assume the code quality is also good based on a quick walk through the Jupyter notebook: Colosseum_main_tutorial.ipynb. The analysis plots also look good. However, in respect to the clarity, I feel like the paper would be much more suited to the journal format. I feel like many of the questions I ask below are probably clarified in the Appendix (which I only glanced through), however, I feel like some of these rather belong in the main paper.\n\nThe motivations for the different MDP families was not described in the main paper\n\nThere were some statements such as:\n>The ergodic settings seem generally slightly easier than the communicating settings.\n\nBut the evidence was not explicitly pointed out. I felt like this in many places and it feels this was done to save space.\n\nBecause of such space-saving measures, I feel the paper is better suited to a journal.\n\n\nIn various places the clarity can be improved, e.g.:\n\n>The diameter also increases almost linearly with the number of states. When p_rand is relatively small, an approximately linear relationship can still be observed.\n\nThis was a little confusing because sub-figures being referenced are not mentioned. esp. for the 2nd sentence, I can't see the linear relationship when  p is \"small\" in Fig. 1a because it's not zoomed in enough. What values of p were meant \"small\"?\n\n\n>\"Sum of the reciprocals of the sub-optimality gaps\": This measure of hardness is not particularly apt at capturing estimation complexity, since it focuses solely on optimal policy identification. It also underestimates the increase in hardness induced by an increase in visitation complexity.\n\nI understand the arguments. However, in Fig. 1a-1d, tbh, \"Sum of the reciprocals of the sub-optimality gaps\" actually seems the closest to the cumulative regret of the tuned near-optimal agent. Could the authors please add some reasoning as to why this measure ends up being seemingly the closet to the cumulative regret of the tuned near-optimal agent even though it is not suited either for visitation complexity or estimation complexity.\n\n\n>For Q-learning and PSRL (Figs. 2b and 2c), the diameter seems to have a generally smaller influence on the average cumulative regret\n\nI cant quite see this in the figures.\n\n>(efficiently computable) hardness measures\n\nAdding a table with computational complexity of calculating the measures would be highly appreciated.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept