Scale-free Adversarial Reinforcement Learning

This paper initiates the study of scale-free learning in Markov Decision Processes (MDPs), where the scale of rewards/losses is unknown to the learner. We design a generic algorithmic framework, {S}cale {C}lipping {B}ound (SCB), and instantiate this framework in both the adversarial Multi-armed Bandit (MAB) setting and the adversarial MDP setting. Through this framework, we achieve the first minimax optimal expected regret bound and the first high-probability regret bound in scale-free adversarial MABs, resolving an open problem raised in {hadiji2023adaptation}. On adversarial MDPs, our framework also give birth to the first scale-free RL algorithm with a Õ(√T) high-probability regret guarantee.