Logarithmic Regret for Online KL-Regularized Reinforcement Learning

• URL: http://arxiv.org/abs/2502.07460v2
• Date: Tue, 18 Feb 2025 13:55:04 GMT
• Title: Logarithmic Regret for Online KL-Regularized Reinforcement Learning
• Authors: Heyang Zhao, Chenlu Ye, Wei Xiong, Quanquan Gu, Tong Zhang,
• Abstract summary: KL-regularization plays a pivotal role in improving efficiency of RL fine-tuning for large language models. Despite its empirical advantage, the theoretical difference between KL-regularized RL and standard RL remains largely under-explored. We propose an optimistic-based KL-regularized online contextual bandit algorithm, and provide a novel analysis of its regret.
• Score: 51.113248212150964
• License:
• Abstract: Recent advances in Reinforcement Learning from Human Feedback (RLHF) have shown that KL-regularization 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 KL-regularized objective in decision making \citep{xiong2024iterative, xie2024exploratory,zhao2024sharp}, these analyses either reduce to the traditional RL setting or rely on strong coverage assumptions. In this paper, we propose an optimism-based 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 $\mathcal{O}\big(\eta\log (N_{\mathcal R} T)\cdot d_{\mathcal R}\big)$ logarithmic regret bound, where $\eta, N_{\mathcal R},T,d_{\mathcal R}$ denote the KL-regularization 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.

Related papers

• Sharp Analysis for KL-Regularized Contextual Bandits and RLHF [52.519416266840814]
  Reverse-Kullback-Leibler (KL) regularization has emerged to be a predominant technique used to enhance policy optimization in reinforcement learning. We show that a simple two-stage mixed sampling strategy can achieve a sample complexity with only an additive dependence on the coverage coefficient. Our results provide a comprehensive understanding of the roles of KL-regularization and data coverage in RLHF, shedding light on the design of more efficient RLHF algorithms.
  arXiv  Detail & Related papers  (2024-11-07T11:22:46Z)
• Demonstration-Regularized RL [39.96273388393764]
  Using expert demonstrations, we identify an optimal policy at a sample complexity of order $widetildeO(mathrmPoly(S,A,H)/(varepsilon2 NmathrmE)$ in finite and $widetildeO(mathrmPoly(d,H)/(varepsilon2 NmathrmE)$ in linear Markov decision processes. We establish that demonstration-regularized methods are provably efficient for reinforcement learning from human feedback.
  arXiv  Detail & Related papers  (2023-10-26T10:54:47Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL) We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.
  arXiv  Detail & Related papers  (2023-05-29T17:11:28Z)
• Rényi Divergence Deep Mutual Learning [3.682680183777648]
  This paper revisits Deep Learning Mutual (DML) as a simple yet effective computing paradigm. We propose using R'enyi divergence instead of the KL divergence, which is more flexible and limited. Our empirical results demonstrate the advantage combining DML and R'enyi divergence, leading to further improvement in model generalization.
  arXiv  Detail & Related papers  (2022-09-13T04:58:35Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  We study human-in-the-loop reinforcement learning (RL) with trajectory preferences. Instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. We propose the first optimistic model-based algorithm for PbRL with general function approximation.
  arXiv  Detail & Related papers  (2022-05-23T09:03:24Z)
• Towards Tractable Optimism in Model-Based Reinforcement Learning [37.51073590932658]
  To be successful, an optimistic RL algorithm must over-estimate the true value function (optimism) but not by so much that it is inaccurate (estimation error) We re-interpret these scalable optimistic model-based algorithms as solving a tractable noise augmented MDP. We show that if this error is reduced, optimistic model-based RL algorithms can match state-of-the-art performance in continuous control problems.
  arXiv  Detail & Related papers  (2020-06-21T20:53:19Z)
• Leverage the Average: an Analysis of KL Regularization in RL [44.01222241795292]
  We show that Kullback-Leibler (KL) regularization implicitly averages q-values. We provide a very strong performance bound, the very first to combine two desirable aspects. Some of our assumptions do not hold with neural networks, so we complement this theoretical analysis with an extensive empirical study.
  arXiv  Detail & Related papers  (2020-03-31T10:55:06Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.