will use the knowledge to optimise true reward. For example, if the CR agent has learned that a high reward state $s$ is likely corrupt with low true reward, then it will not try to reach that state. One might therefore expect that at least the CR agent will do well under the simplifying assumptions \[as:lim-cor,as:easy\]. below shows that this is *not* the case.

In most practical settings it is often computationally infeasible to compute $\pirl$ and $\pidb$ exactly. However, many practical algorithms converge to the optimal policy in the limit, at least in simple settings. For example, tabular Q-learning converges to $\pirl$ in the limit [@Jaakkola1994]. The more recently proposed CIRL framework may be seen as an approach to build CR agents [@Hadfield-menell2016cirl; @Hadfield-menell2016osg]. The CR and RL agents thus provide useful idealisations of more practical algorithms.

\[th:rl-imp1\] For any $|\Srisky|\geq q>1$ there exists a CRMDP class $\M$ that satisfies \[as:lim-cor,as:easy\] such that $\pirl$ and $\pidb$ suffer near worst possible time-averaged regret $$\apl(\M, \pirl, s_0, t)=\apl(\M, \pidb, s_0, t)=1-1/|\Srisky|.$$ For $\pidb$, the prior $b$ must be such that for some $\mu\in\M$ and $s\in\S$, $\EE_b[\irf(s) \mid  h_\mu]>\EE_b[\irf(s') \mid  h_\mu]$ for all $s'$, where $\EE_b$ is the expectation with respect to 