no connection between observed reward $\orf$ and true reward $\irf$. The result therefore encourages us to make precise in which way the observed reward is related to the true reward, and to investigate how agents might handle possible differences between true and observed reward.

Simplifying Assumptions
-----------------------

shows that general classes of CRMDPs are not learnable. We therefore suggest some natural simplifying assumptions, illustrated in \[fig:simplifying-assumptions\].

#### Limited reward corruption

The following assumption will be the basis for all positive results in this paper. The first part says that there may be some set of states that the designers have ensured to be non-corrupt. The second part puts an upper bound on how many of the other states can be corrupt.

\[as:lim-cor\] A CRMDP class $\M$ has *reward corruption limited by $\Ssafe\subseteq\S$ and $q\in\SetN$* if for all $\mu\in\M$

all states s in $\Ssafe$ are non-corrupt, and \[as:safe-state\]

at most $q$ of the non-safe states $\Srisky=\S\setminus\Ssafe$ are corrupt. \[as:lim-del\]

Formally, $\d_s:r\mapsto r$ for all $s\in\Ssafe$ and for at least $|\Srisky|-q$ states $s\in\Srisky$ for all $\d\in\D$.

For example, $\Ssafe$ may be states where the agent is back in the lab where it has been made (virtually) certain that no reward corruption occurs, 