be formed with elements of a set $X$. The policy $\pi$ specifies how the agent will learn and react to any possible experience. Two concrete definitions of agents are given in \[sec:rl-agents\] below.

When an agent $\pi$ interacts with a CRMDP $\mu$, the result can be described by a (possibly non-Markov) stochastic process $P^\pi_\mu$ over $X=(s,a,\ir,\dr)$, formally defined as: $$\label{eq:mupi}
  P_\mu^\pi(h_n) = P_\mu^\pi(s_0\ir_0\dr_0a_1s_1\ir_1\dr_1\dots a_ns_n\ir_n\dr_n) :=
  \prod_{i=1}^{n}P(\pi(\oh_{i-1})=a_{i})T(s_{i}\mid s_{i-1},a_{i})P(\irf(s_i)=\ir_i,\orf(s_{i})=\dr_{i}).$$ Let $\EE^\pi_\mu$ denote the expectation with respect to $P_\mu^\pi$.

#### Regret

A standard way of measuring the performance of an agent is *regret* [@Berry1985]. Essentially, the regret of an agent $\pi$ is how much less true reward $\pi$ gets compared to an optimal agent that knows which $\mu\in\M$ it is interacting with.

\[def:regret\] For a CRMDP $\mu$, let $\iG_t(\mu,\pi,s_0)\! =\!\EE^\pi_\mu\left[\!\sum_{k=0}^t\irf(s_k)\!\right]$ be the *expected cumulative true reward* until time $t$ of a policy $\pi$ starting in $s_0$. The *regret* of $\pi$ is $$\Reg(\mu, \pi, s_0, t) =
    \max_{\pi'}
    \left[
      \iG_t(\mu,\pi',s_0) - \iG_t(\mu,\pi,s_0)
    \right],$$ and the *worst-case regret* for a class $\M$ is $\Reg(\M,\pi,s_0,t) = \max_{\mu\in\M}\Reg(\mu,\pi,s_0,t)$, i.e. the difference in expected cumulative true reward between $\pi$ and an optimal (in hindsight) policy that knows $\mu$.

The Corrupt Reward Problem {#sec:problem}
==========================

In this section, the 