Policy optimization methods are popular reinforcement learning algorithms in practice and recent works have build theoretical foundation for them by proving √(T) regret bounds even when the losses are adversarial. Such bounds are tight in the worst case but often overly pessimistic. In this work, we show that by carefully designing the regularizer, bonus terms, and learning rates, one can achieve a more favorable polylog(T) regret bound when the losses are stochastic, without sacrificing the wor…