difficulty of the corrupt reward problem is established with two negative results. First, a No Free Lunch theorem shows that in general classes of CRMDPs, the true reward function is unlearnable (\[th:impossibility\]). Second, \[th:rl-imp1\] shows that even under strong simplifying assumptions, Bayesian RL agents trying to compensate for the corrupt reward still fail badly.

No Free Lunch Theorem {#sec:impossibility}
---------------------

Similar to the No Free Lunch theorems for optimisation [@Wolpert1997], the following theorem for CRMDPs says that without some assumption about what the reward corruption can look like, all agents are essentially lost.

\[th:impossibility\] Let $\R=\{\r_1,\dots,\r_n\}\subset[0,1]$ be a uniform discretisation of $[0,1]$, $0=\r_1<\r_2<\cdots<\r_n=1$. If the hypothesis classes $\iRf$ and $\D$ contain all functions $\irf:\S\to \iR$ and $\d:\S\times\iR\to \oR$, then for any $\pi$, $s_0$, $t$, $$\label{eq:regbound}
    \Reg(\M,\pi,s_0, t)\geq \frac{1}{2}\max_{\check\pi}\Reg(\M,\check\pi,s_0, t).$$ That is, the worst-case regret of any policy $\pi$ is at most a factor 2 better than the maximum worst-case regret.

Recall that a policy is a function $\pi:\H\to\A$. For any $\irf,\d$ in $\iRf$ and $\D$, the functions $\irf^-(s) := 1-\irf(s)$ and $\d^-_s(x) := \d_s(1-x)$ are also in $\iRf$ and $\D$. If $\mu=\crmdp$, then let $\mu^-=\crmdpm$. Both $(\irf,\d)$ and $(\irf^-,\d^-)$ induce the same observed reward function $\orf(s) = \d_s(\irf(s)) = \d^-_s(1-\irf(s)) 