Scale-free Adversarial Reinforcement Learning
<|reference_start|>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, \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.<|reference_end|>
@article{chen2024scale-free,
    title={Scale-free Adversarial Reinforcement Learning},
    author={Mingyu Chen, Xuezhou Zhang},
    journal={arXiv preprint arXiv:2403.00930},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.00930},
    primaryClass={cs.LG cs.AI}
}