Before revision:  Secondly, our regret bounds are the first of their kind in the reinforcement learning setting to have the number of corruptions show up additively with respect to \sqrt{T, PolicyGapComplexity\} } rather than multiplicatively.
After revision:  Secondly, our regret bounds are the first of their kind in the reinforcement learning setting to have the number of corruptions show up additively with respect to \min\{\sqrt{T, PolicyGapComplexity\} } rather than multiplicatively.