in $\mu$. To finish the proof for the $\pidb$ agent, we just need to show that $\M$ contains such a $\mu'$ where $s^*$ has true reward $\r_{\min}$. We construct $\mu'$ as follows.

-   Case 1: If the lowest observed reward is in $s^*$, then let $\irf(s^*)=\r_{\min}$, and the corruption function be the identity function.

-   Case 2: Otherwise, let $s'\not=s^*$ be a state with $\orf(s')=\min_{ s\in\Srisky}\{\orf(s)\}$. Further, let $\irf(s')=1$, and $\irf(s^*)=\r_{\min}$. The corruption function $C$ accounts for differences between true and observed rewards in $s^*$ and $s'$, and is otherwise the identity function.

To verify that $\irf$ and $C$ defines a $\mu'\in\M$, we check that $C$ satisfies \[as:lim-del\] with $q=2$ and that $\irf$ has enough high utility states (\[as:high-ut\]). In Case 1, this is true since $C$ is the identity function and since $\orf$ satisfies \[as:high-ut\]. In Case 2, $C$ only corrupts at most two states. Further, $\irf$ satisfies \[as:high-ut\], since compared to $\orf$, the states $s^*$ and $s'$ have swapped places, and then the reward of $s'$ has been increased to 1.

From this construction it follows that $\pidb$ will suffer maximum asymptotic regret. In the CRMDP $\mu'$ given by $C$ and $\irf$, the $\pidb$ agent will always visit 