Scale-free Adversarial Reinforcement Learning
Mingyu Chen Xuezhou Zhang
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, \underline{S}cale
\underline{C}lipping \underline{B}ound (\texttt{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
\cite{hadiji2023adaptation}. On adversarial MDPs, our framework also give birth
to the first scale-free RL algorithm with a $\tilde{\mathcal{O}}(\sqrt{T})$
high-probability regret guarantee.