  We present the OMG-CMDP! algorithm for regret minimization in adversarial
Contextual MDPs. The algorithm operates under the minimal assumptions of
realizable function class and access to online least squares and log loss
regression oracles. Our algorithm is efficient (assuming efficient online
regression oracles), simple and robust to approximation errors. It enjoys an
$\widetilde{O}(H^{2.5} \sqrt{ T|S||A| ( \mathcal{R}(\mathcal{O}) + H
\log(\delta^{-1}) )})$ regret guarantee, with $T$ being the number of episodes,
$S$ the state space, $A$ the action space, $H$ the horizon and
$\mathcal{R}(\mathcal{O}) = \mathcal{R}(\mathcal{O}_{\mathrm{sq}}^\mathcal{F})
+ \mathcal{R}(\mathcal{O}_{\mathrm{log}}^\mathcal{P})$ is the sum of the
regression oracles' regret, used to approximate the context-dependent rewards
and dynamics, respectively. To the best of our knowledge, our algorithm is the
first efficient rate optimal regret minimization algorithm for adversarial
CMDPs that operates under the minimal standard assumption of online function
approximation.
