as evidence about a true signal are not fail-safe solutions to the reward corruption problem.

Let $\Srisky = \{s_1,\dots,s_n\}$ for some $n\geq 2$, and let $\S=\Ssafe\dunion\Srisky$ for arbitrary $\Ssafe$ disjoint from $\Srisky$. Let $\A=\{a_1,\dots,a_n\}$ with the transition function $T(s_i\mid s_j,a_k)=1$ if $i=k$ and 0 otherwise, for $1\leq i,j,k\leq n$. Thus \[as:communicate,as:stay\] are satisfied.

Let $\R=\{\r_1,\dots,\r_n\}\subset[0,1]$ be uniformly distributed between [^4] $\r_{\min}=1/|\Srisky|=\r_1<\dots<\r_n=1$. Let $\iRf$ be the class of functions $\S\to\iR$ that satisfy \[as:high-ut\] and are constant and equal to $\ir_{\min}$ on $\Ssafe$. Let $\D$ be the class of corruption functions that corrupt at most two states ($q=2$).

Let $\M$ be the class of CRMDPs induced by $\Tf=\{T\}$, $\iRf$, and $\D$ with the following constraints. The observed reward function $\orf$ should satisfy \[as:high-ut\]: For all $\delta\in[0,1]$, $|\{s\in\Srisky:\orf(s)>\delta\}| \geq (1-\delta)|\Srisky|$. Further, $\orf(s')=\r_{\min}$ for some state $s'\in\Srisky$.

Let us start with the CR agent $\pidb$. Assume $\mu\in\M$ is an element where there is a single preferred state $s^*$ after all states have been explored. For sufficiently large $t$, $\pidb$ will then always choose $a^*$ to go to $s^*$ after some initial exploration. If another element $\mu'\in\M$ has the same observed reward function as $\mu$, then $\pidb$ will take the same actions in $\mu'$ as 