= \d^-_s(\irf^-(s))$, and therefore induce the same measure $P_\mu^\pi = P_{\mu^-}^\pi$ over histories (see Eq. \[eq:mupi\]). This gives that for any $\mu, \pi, s_0, t$, $$\label{eq:sumt}
    G_t(\mu,\pi,s_0) + G_t(\mu^-,\pi,s_0) = t$$ since $$\begin{aligned}
    G_t(\mu, \pi,s_0)&= \EE_{\mu}^\pi\left[\sum_{k=1}^t\irf(s_k)\right]
    = \EE_{\mu}^\pi\left[\sum_{k=1}^t1-\irf^-(s_k)\right]\\
    &= t-\EE_{\mu}^\pi\left[\sum_{k=1}^t\irf^-(s_k)\right]
    = t- G_t(\mu^-,\pi,s_0).
  \end{aligned}$$

Let $M_\mu=\max_\pi G_t(\mu, \pi, s_0)$ and $m_\mu=\min_\pi G_t(\mu, \pi, s_0)$ be the maximum and minimum cumulative reward in $\mu$. The maximum regret of any policy $\pi$ in $\mu$ is $$\label{eq:max-regret}
    \max_\pi \Reg(\mu, \pi, s_0, t)
    = \max_{\pi',\pi} (G_t(\mu, \pi', s_0) - G_t(\mu, \pi, s_0))
    = \max_{\pi'} G_t(\mu, \pi', s_0) - \min_{\pi}G_t(\mu, \pi, s_0)
    = M_\mu - m_\mu.$$ By \[eq:sumt\], we can relate the maximum reward in $\mu^-$ with the minimum reward in $\mu$: $$\label{eq:M-to-m}
    M_{\mu^-}
    = \max_\pi G_t(\mu^-, \pi, s_0)
    = \max_\pi(t - G_t(\mu, \pi, s_0))
    = t - \min_\pi G_t(\mu, \pi, s_0)
    = t - m_\mu.$$ Let $\mu_*$ be an environment that maximises possible regret $M_\mu-m_\mu$.

Using the $M_\mu$-notation for optimal reward, the worst-case regret of any policy $\pi$ can be expressed as: $$\begin{aligned}
    \Reg(\M,\pi,s_0, t)
        & = \max_{\mu} (M_\mu - G_t(\mu,\pi,s_0)) \\
        & \geq \max \{
      M_{\mu_*} - G_t(\mu_*, \pi, s_0),
      M_{\mu_*^-} - G_t(\mu_*^{-}, \pi, s_0)
      \}
    & \text{restrict max operation} \\
        & \geq 