from $s$. The *diameter* of a CRMDP $\mu$ is $
  D_\mu:=\max_{s,s'}\min_{\pi:\S\to\A}\EE[{\it time}(s'\mid s,\pi)]
  $, and the diameter of a class $\M$ of CRMDPs is $D_\M=\sup_{\mu\in\M}D_\mu$. A CRMDP (class) with finite diameter is called *communicating*.

\[as:easy\] A CRMDP class $\M$ is *easy* if

\[as:communicate\] it is communicating,

\[as:stay\] in each state $s$ there is an action $\astay_s\in\A$ such that $T(s\mid s,\astay_s)=1$, and

\[as:high-ut\] for every $\delta\in[0,1]$, at most $\delta|\Srisky|$ states have reward less than $\delta$, where $\Srisky= \S\setminus\Ssafe$.

means that the agent can never get stuck in a trap, and \[as:stay\] ensures that the agent has enough control to stay in a state if it wants to. Except in bandits and toy problems, it is typically not satisfied in practice. We introduce it because it is theoretically convenient, makes the negative results stronger, and enables a simple explanation of quantilisation (\[sec:quant\]). says that, for example, at least half the risky states need to have true reward at least $1/2$. Many other formalisations of this assumption would have been possible. While rewards in practice are often sparse, there are usually numerous ways of getting reward. Some weaker version of \[as:high-ut\] may therefore be satisfied in many practical situations. Note that we do 