and $q$ a small fraction of $|\Srisky|$. Both parts of \[as:lim-cor\] can be made vacuous by choosing $\Ssafe=\emptyset$ or $q=|\S|$. Conversely, they completely rule out reward corruption with $\Ssafe=\S$ or $q=0$. But as illustrated by the examples in the introduction, no reward corruption is often not a valid assumption.

; ; coordinates [(1,0) (3,0) (10,1)]{}; ;

An alternative simplifying assumption would have been that the true reward differs by at most $\eps>0$ from the observed reward. However, while seemingly natural, this assumption is violated in all the examples given in the introduction. Corrupt states may have high observed reward and 0 or small true reward.

#### Easy environments

To be able to establish stronger negative results, we also add the following assumption on the agent’s manoeuvrability in the environment and the prevalence of high reward states. The assumption makes the task easier because it prevents *needle-in-a-haystack* problems where all reachable states have true and observed reward 0, except one state that has high true reward but is impossible to find because it is corrupt and has observed reward 0.

\[def:communicating\] Let ${\it time}(s'\mid s,\pi)$ be a random variable for the time it takes a stationary policy $\pi:\S\to\A$ to reach $s'$ 