Logarithmic Regret for Online KL-Regularized Reinforcement Learning

Recent advances in Reinforcement Learning from Human Feedback (RLHF) have shown that KLregularization plays a pivotal role in improving the efficiency of RL fine-tuning for large language models (LLMs). Despite its empirical advantage, the theoretical difference between KL-regularized RL and standard RL remains largely under-explored. While there is a recent line of work on the theoretical analysis of KLregularized objective in decision making (Xiong et al., 2024a; Xie et al., 2024; Zhao et al., 2024) , these analyses either reduce to the traditional RL setting or rely on strong coverage assumptions. In this paper, we propose an optimismbased KL-regularized online contextual bandit algorithm, and provide a novel analysis of its regret. By carefully leveraging the benign optimization landscape induced by the KL-regularization and the optimistic reward estimation, our algorithm achieves an O η log(N R T ) • d R logarithmic regret bound, where η, N R , T, d R denote the KLregularization parameter, the cardinality of the reward function class, number of rounds, and the complexity of the reward function class. Furthermore, we extend our algorithm and analysis to reinforcement learning by developing a novel decomposition over transition steps and also obtain a similar logarithmic regret bound.