Logarithmic Regret for Online KL-Regularized Reinforcement Learning
Authors: Heyang Zhao
Chenlu Ye
Wei Xiong
Quanquan Gu
Tong Zhang
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
regularization
Primary area: theory->reinforcement_learning_and_planning

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 (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 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.

Logarithmic Regret for Online KL-Regularized Reinforcement Learning
Heyang Zhao Chenlu Ye" 22 Wei Xiong? Quanquan Gu
Tong Zhang? ?
Abstract
large language models (LLMs), which is commonly referred to the Reinforcement Learning from Human Feedback (RLHF) (Bai et al., 2022; Ouyang et al., 2022). The RLHF learning paradigm has been used to make powerful chatbot by aligning the L.Ms with human preference, making the model generation helpful, honest, and harmless (Bai et al., 2022). Notable examples include the OpenAl's Chat-GPT (OpenAI, 2023), Anthropic's Claude (Bai et al., 2022), and Google's Gemini (Team et al., 2023). More recently, the KL- regularized RL framework has also been applied to enhance multi-turn pulli-tturnaa reasoning capabilities, resulting in powerful rea- soning models such as GPT4-ol and DeepSeek-RL
Recent advances in Reinforcement Learning from Human Feedback (RLHF) have shown that KL- regularization plays a pivotal role in improv- ing the efficiency of RL fine-tuning for large language models (LLMs). Despite its empiri- cal 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 (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 assump- tions. In this paper, we propose an optimism- based Kl--regularized online contextual bandit al- gorithm, 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 (1) log( (N - dx.) logarithmic re- gret bound, where 77, NR. T, dR denote the KL- regularization parameter, the cardinality of the reward function class, number of rounds, and the complexity of the reward function class. Further- more, extend our algorithm and analysis to reinforcement learning by developing novel de- composition over transition steps and also obtain a similar logarithmic regret bound.
However, the RLHF process also faces challenges. It often causes decline in certain abilities acquired during pre- training and supervised fine-tuning (SFT), a phenomenon commonly known as "alignment tax" (Askell et al., 2021; Lin et al., 2023). For instance, contrastive learning without regularization, as observed in Meng et al. (2024), can de- grade performance on standard reasoning benchmarks like MATH (Hendrycks et al., 2021) and GSM8K (Cobbe et al., 2021). Additionally, unregularized RL training presents sig- nificant challenges on computational efficiency and training stability (Casper et al., 2023). To address these issues, prac- titioners often optimize a KL-rreularrzed objective (defined formally in Section 4) to balance reward optimization and mitigate alignment tax.
Morcover, these KL-regularized frameworks often demon- strate superior sample efficiency compared standard deep RL tasks. For example, models with 52B parameters (Claude (Bai et al., 2022)) and 671B parameters (DeepSeek- RI (DeepSeek-Al et al., 2025)) achieve substantial policy improvement with only tens of thousands of samples or thou- sands of training steps. Similar observations apply to direct preference alignment algorithms (Rafailov et al., 2023; Tun- stall et al., 2023; Chen al., 2024; Dong et al., 2024), which develop state-of-the-a open-source chatbots using fewer than 100K samples. These results highlight the superior sample efficiency of KL-regularized RL, surpassing tradi- tional deep RL applications (Silver et al., 2016) and their analyses in the RL theory literature.
1. Introduction
We study the KL-regularized contextual bandit (Langford & Zhang, 2007; Xiong et al., 2024a) and Markov decision processes (MDPs) (Sutton, 2018) in this paper. These two frameworks have received significant attention due to their tremendous successes in the post-training stage of modern
'Equal contribution Unnivessity of California, Los Angeles, CA 90095, USA Uniierrsity of Illinois Urbana-Chan Champaagn,,,,,,, IL 61801, USA. Correspondence to: Quanquan Gu <qgu uew.u......uu.. Tong Zhang Sttnnghhng@toongghaatt @wwtggtanggmlll.... mlloog.>.
However, despite the empirical success, a fundamental con- nection between KL regularization and learning efficiency has not been established so far theoretically. While some
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
recent studies have attempted analyze these frameworks, they often rely on standard analysis techniques, yielding regret guarantees similar to those of standard RL (Xiong et al., 2024a; Xie et al., 2024; Xiong et al., 2024b; Cen et al., 2024), or they depend on strong coverage assump- tions and restricted to the bandit settings (Zhao et al., 2024).
novel policy decomposition technique through multi- steps. These techniques may be of independent interest and have the potential to inspire future research on KL-regularized decision-making problems.
2. Related Work
notable exception is the approach of Tiapkin et al. (2023; 2024), which achieves ((Hddnn) e) sample complexity for KL-regularized linear MDPs, and O(H' An/c) sample complexity for tabular MDPs. However, their analysis fo- cuses on the pure exploration or best policy identification setting, where the goal is to find near-optimal policies using the least possible amount of interactions with the environ- ment, rather than the online setting where the agent needs to trade off between exploration and exploitation. Therefore, the following pivotal question remains open:
RLHE. Reinforcement Learning from Human Feedback (RLHF) has achieved tremendous successes in the modern large language model post training (OpenAI, 2023; Bai et al., 2022; Ouyang et al., 2022; Team et al., 2023). The dominant approach in the area is based on the reward training and policy optimization with the PPO algorithm (Schulman et al., 2017). However, applying PPO effectively in the context of LLMS presents significant challenges (Choshen et al., 2019). However, getting the PPO work is challenging in the context of LLMs (Choshen et al., 2019). In view of this, researchers have spent great efforts in proposing alternative approaches to the PPO algorithm.
Is KL-regularized RL more efficient than standard RL in the online setting without additional coverage assumption?
In this work, we address this question by designing provably efficient algorithms based on the optimism in the face of uncertainty (OFU) principle and develop refined policy sub- optimimality decomposition for both contextual bandits and MDPs.
One line of research revisits REINFORCE- -ased variants such as ReMAX and GRPO (Li et al., 2023a; Shao et al., 2024), with the KL-regularized objective. Another approach focuses on direct preference learning (Zhao al., 2023b; Rafailov et al., 2023; Azar et al., 2023), which bypasses the reward modeling stage and directly optimizes the policy using the preference dataset in a supervised manner. A no- table example is the Direct Preference Optimization (DPO) algorithm (Rafailov et al., 2023), which has gained great attention in both the open-source community (Tunstall et al., 2023; Lambert al., 2024) and industrial applications such as Llama (Dubey al., 2024). All approaches mentioned above are derived under the KL-regularized framework stud- ied in this paper. An exception to this trend is best-of-n (BoN) sampling and rejection sampling fine-tuning (Bai et al., 2022; Dong et al., 2023; Touvron et al., 2023), where a reward model is used to filter samples for final output or select training samples. However, recent works show that the success of BoN sampling may essentially result from the fact that it is optimal in terms of the KL-reward trade-off (Gui et al., 2024; Yang et al., 2024).
We establish the theoretical guarantees for the algorithms and demonstrate their statistical advantages over standard RL scenarios. We summarize our contributions as follows.
For KL-regularized contextual bandits, we establish the first O (oglog (og dæ)) regret bound that scales logarithmically with time steps T in the standard on- line RL setting, where 7) is the KL-regularization pa- rameter, NR. dr denote the cardinality of the reward function class R, and its eluder dimension. This re- sult significantly improves upon the previous ((TT) bound (Xiong et al., 2024a) and eliminates the strong coverage condition in prior work (Zhao et al., 2024).
Distinct from the previous analyses that solely rely the learned policy maximizing the KL-regularized ob- jective, we take a novel approach by expressing the suboptimality gap in terms of a functional gap with respect to the policy TR induced by proxy reward function R. With a tine-grained analysis for the deriva- tive of the gap, we then establish the monotonicity in the sub-optimality gap via the optimistic reward estima- tion. This allows us to obtain the uncertainty induced by the policy at the current time step so that the sum of squared uncertainty can be bounded by the eluder dimension.
Theory of RLHE The theoretical foundation of RLHF traces back to dueling bandits (e.g.. Yue et al., 2012; Saha, 2021; Bengs et al., 2021), which studied preference feed- back in non-regularized settings. This was later extended to online reinforcement learning with finite state spaces
Xiong et al. (2024a) studies relative- preeeie- feedback, so their sample complexity additionally depends on c". Since our work focuses on absolute rewards, we omit this dependence.
'Xiong et al. (2024b) considers the trajectory- -evell level reward and learns the reward in R and transition probability P separately, so the dependence on dR, Ni and d, P, Np are separete.
We extend these techniques to KL-regularized MDPs and establish the first Olog regret bound in the literature. The key to this improved regret bound is a
"Xie et al. (2024) considers the deterministiie-ransttoon setting and optimizes the policy directly.
2

---

Logarithmic Regret for Online KL.-Regularied Reinforcement Learning
Table 1. Comparison of online -l.-regularized algorithms in handits and MDPs, where e is the sub-optimality gap, T is the number of rounds, d is the vector dimension for linear models, constant 1) > 0 is the KL-regularized parameter, CCL. is the global coverage condition, dæ and de are the complexity measure for general function class R and F. O omits the logarithmic order for and l/c. The notations N, NR, Nr@B, Nn represent the cardinality or covering number for the reward, value and bonus function classes. The fourth column represents the number samples needed to achieve an e-suboplimality, and the last column shows whether they require the coverage condition. We convert the regret bounds of our algorithms sample complexity by Lemma D.2. We remark that the results of Xiong et al. (2024a); Xie et al. (2024); Xiong et al. (2024b) are based on preference feedback. When comparing with them, we mainly focus on the order of dependency T. See Remark 3.1 for further discussion the extension to preference feedback.
Setting
Algorithm
Regret
Sample Complexity
Coverage
Online Iterative GSHF'
Ö((((())
x
(Xiong et al., 2024a)
Bandits
Two-Stage Mixed-Policy Sampling
Ó + 1//c)log NR)
(Zhao et al., 2024)
KL-UUB (Theorem 4.1)
(ndy log T. log(NRz)
Ō Óndd (ogg(RR))
Online Iterative M-GSHF
Ö( ((dxz log NR.
Ö(dR log Nx/e
(Xiong et al., 2024bb
+ +dd log
Hdd log Np//)
x
MDPs
XPO (Xie et al., 2024)²
Ō log \
x
KL-LSVI-UCB (Theorem 5.1)
OnHH'dxlog log Neg8))
On log N=gB)/c)
X
(tabular settings) and function approximation (Xu et al., 2020; Novoseller et al., 2020; Pacchiano al., 2021; Chen et al., 2022). More recently, Zhan et al. (2023b); Wu & Sun (2023) developed reward-free learning algorithms and sampling-based methods for online RLHE, For the offline learning. Zhu et al. (2023); Zhan et al. (2023a); Li et al. (2023b); Zhong et al. (2024); Huang et al. (2024) propose sample-efficient algorithms under suitable coverage condi- tions. These works mainly develop techniques to estimate the underlying reward model associated with the Bradley- Terry model from querying the preference oracle (human) and achieve similar order regret with the standard reward learning. However, since they only consider reward maxi- mization, the results deviate from the practical applications of RLHF. For example, reward maximization frameworks often assume deterministic optimal policy, which is un- suitable for generative models.
the KL-regularized problem and develop new techniques and algorithms that achieve superior theoretical guarantees compared to prior studies.
The most closely related work to our project is Zhao et al. (2024), which considers the KL-regularized RL in the bandit setting. They propose a two-stage mixed-poligy sampling al- gorithm and provide a regret bound which enjoys an (11cc) sample complexity. However, their results rely on rela- tively strong coverage assumption, which is not compatible with the practical applications of RLHF In contrast, our work provides a novel algorithm and analysis that achieves a logarithmic regret bound without the coverage assumption. We summarize the comparison of our work with the existing literature Table 1.
Notation. For finite function class F, we use Nr to represent its cardinality. We use Ô to omit the logarith- mic orders. We use the convention [n] = any vector x and matrix Σ, let ||=r||>: = vx Ea. For a function R : X' x A + R, parameter > and the reference policy Tref, let the normalization constant xx)) = Ea exp(r)((x,a))
After these works, the recent project Xiong et al. (2024a) provides the first provably efficient algorithm of RI.FF un- der the KL-regularized contextual bandit formulation. The result is further refined in (Xie et al., 2024) and Xie et al. (2024); Liu et al. (2024): Cen al. (2024) propose provably efficient algorithms with optimistically biased optimization targets, which originate from the feel-good sampling (Zhang, 2022). In parallel, Wang et al. (2023); Ye et al. (2024) extend the techniques of preference learning to the general prefer- ence setting under the Markov game formulation. However, their techniques simply discard the KL divergence in the target, and use the standard techniques to get results that are similar the non-regularized problems, which are es- sentially sub-optimal for the KL-regularized framework. In contrast, in this work, we aim to leverage the structure of
For
3. Background
3.1. AL-Regularized Contextual Bandits
The contextual bandit problem with KL-regularized objec- tive is defined as follows.
At each round t 2 1, the learner observes a context x, E X, and chooses an action at E A, where X' is the context space and the action space. The learner then receives a
3

---

Logarithmic Regret for Online KL.- KI.-Regularized Reinforcement Learning
reward rt E IR which characterizes the gain of the learner from choosing action 0f under context sy, We assume that the reward It is generated by
the eluder coefficient can be simplified as
((0) 02) T (12
sup 0, 02ERK
v / + ZiE (0: 02) TT a.))
Tt = Tt= ( ac) te,,
1((0) 02) [2 al)l 1 || a))x,""
sup 02.0
where I2 (Iz, is the unknown reward function and é, is an independent
v(1 -2) (0, 02)
zero-mean random noise. In practice, the context can be a prompt, and the action is the response generated by the LLMs. The reward signal is a sentence reward that commonly used (Ouyang et al., 2022; Bai et al., 2022; Touvron et al., 2023).
where the inequality uses the Cauchy- SShwarz inequality. Hence, the uncertainty reflects how much a direction in the feature space has been explored. Further, the eluder dimension represents how many times the model can be "surprised" by the out-of-sample data over ' rounds. One can show that this definition is more general than the original one in (Russo & Van Roy, 2013) as we further take the magnitude of violation into consideration while the original eluder dimension only counts the frequency (Zhang, 2023; Xie et al., 2022).
Remark 3.1. We do not consider the preference feedback here since the more recent applications in building reason- ing models (DeepSeek-Al et al., 2025) and improving LLM safety (Guan et al., 2024) assume the existence of the ab- solute reward value (e.g. the binary reward indicator of the correctness). The results presented in this work can be readily extended to the preference feedback using the techniques developed in dueling bandit or RL (Yue et al., 2012; Pacchiano et al., 2021; Xiong et al., 2024a; Li al., 2024).
We consider a KL-regularized objective follows:
log <(a|z))
((r): : Ea R2 az.
") Teat (a|z))
1 KL
=Eandd Eewrt [R" (x, a)]
Assumption 3.2 (Reward function rcalizability). Assume that there exists a reward function class R. X + 1] such that R (1, a) E R.
where Tyof is the reference policy known to the learner, and r >> 0 is the regularization parameter. This formulation is adopted in nearly all RLHF practice for LLM alignment (Bai et al., 2022; Ouyang et al., 2022: Touvron et al., 2023), and there is closed- forem solution for this optimization, also known as Gibbs distribution.
Without loss of generality, we assume that the function class has finite cardinality [R], and we can generalize the analy- sis to an infinite function class by considering a covering number (Zhang, 2023).
Lemma 3.4 (Solution of KI-rregllaried Optimization (Proposition 7.16 and Theorem 15.3 of Zhang (2023)). For any fixed x E X and reward function R, we have
Definition 3.3 (Uncertainty and eluder dimension). For any sequence D = {<x,, a,) N=l we define the uncertainty of (ar, a) with respect to R as:
max Eawx(+ls) [R(z, a) -1) (
1 log Bammaa((1)) exp (1F((z))))
UR a1-11)
71
RR, a)- Ra(x, a)l
sup RyRR
where Zz(z) is the normalization constant and the mini- mizer of the loss functional is
V++ (Ri (x), Ra(xz)))))
Then, the eluder dimension is given by d(R, X, sup a1:r Et= min (1, (UR(), oe; 11-))
=
T <H(axx) ZR(I)) Teef (a/x) exp (n)((z,a))
1
3.2. Re-Rlaallr Reinforcement Learning
The uncertainty (R, xr a; D:) measures how much dif- ference the new-coming data x, a has with the history data D., and is widely adopted in RL literature with general function approximation (Zhang, 2023; Ye et al., 2023; Agar- wal et al., 2023; Zhao et al., 2023a). To illustrate it bet- ter, we use the linear function as special case, where the function class R can be embedded into a linear mapping R = {0T (.:.)) E Rd, 1101|2 < B). Let the covariance matrix E,- = Eim p(a, ())(())))))))))) az) + A/B T. Then,
In this section, we introduce the KL-regularized MDP prob- lem. A Markov Decision Process (MDP) is defined by a tuple M (S, H.P. do.r), where S is the state space, A is the action space, H is the time horizon, transition proba- bility P = {1P,, ! denotes the probability (( ax) of transition from the current (S), an) to the next state $1++1 at each step h, dg is the initial state distribution, and r r= (rh : S
IR. H
h=1 the reward function.
4

---

Logarithmic Regret for Online KL.- KI.-Regularized Reinforcement Learning
A policy и is a sequence of function {T with Th S A - [0, 1] for all h E [H]] The objective is to find policy that maximizes the following KL-regularized value:
Without loss of generality, we assume that (sh an)
[0, 1] for any (St: @h) E S x A!. From (1), we know that (sA) E [0, 1] for any 8n E A.
Function approximation We approximate the value func- tion {Q7 hetaa by function class F = Fi x .... X FH where Fn S x A - [0. Similarly, we can define re- lated optimal policies policies and value functions with the estimated Q- Q-function Qn. E Fv, and V-function Vn.
H J(m) =E" Σ (Bh, an) 77 Σ log
Th (anlasa)) Toef, (anlss)
where EE" denotes the expectation ((A, On,, (n, rn)] 11 of the reward and the trajectory induced by policy π from the initial state 81 ~ dg-
Then, we define the KL-regularized Bellman operator T, space F: for any fn+1 E Fh+t1,
We can define the value functions as the expected future return with KL-regularization:
T/t f on) = ra(s,, an) + 1 Ena (shtl)
(8a)
E=T
(sw, anr)
where
Vit (Sn+1)
17 log Eag 1 (1) exp (nff+1 (114))()))))
KL KI(TTT (-|s ) Ie a [a)
17
To ensure efficient learning, we suppose that the true Q- value function belongs to the considered function class and the one-step backward of the value function also remains in the considered function class, which are known as realizabil- ity and Bellman completeness assumptions, respectively. Assumption 3.6 (Realizabilitty. each h E [H]. we have O E Fi.
(r, an) + 13"
(sw
-
1 KL(TT (-1ow) Te az sn, an
17
We can also iteratively define the regularized value function as follows:
= 0, and
Assumption 3.7 (Bellman completeness). each h E [H] and any fh+1 E Fr+1, we have T fh+1 E Fj.
Vi (sa) = Eo (a an)
1
(11w]]]]
These two assumptions are standard and normal in RL lit- erature with general function approximation (Wang et al., 2020; Jin et al., 2021; Zhang, 2023).
"
Qh an) (sh. an) + Ea -r (l
Vi (#N+1)
We further define the optimal value function {Vi heemm and the optimal action-value function 1Q7 he
4. KL-Regularized Contextual Bandits
Vir (sx) max Vg (#n); (% an) max Q% (5h, ax)-
4.1. The Proposed Algorithm and Result
We develop the KL-regularized Upper Confidence Bound (KL-UCB) algorithm in Algorithm 1. In each round E [T]. after observing context Ie ~ do. taking action 0g ~ Te (-1xz), and receiving the reward r. = R (1e, oz) + c, we compute the estimator Rg by solving the least square regression. Then, we perform optimism by adding the fol- lowing bonus term to the reward estimator:
Assume optimal policy is achieved at n", using Lemma 3.4 and a backward iteration starting from the Vi+4(S1H+ ($1+1)= = 0, we have the following proposition.
Proposition 3.5. The optimal policy is a layer-wise Gibbs distribution of the Q"
T (axlsn)) = Z (kn) Tee (an exp (nQ7 an)),
be(a, a) min { {1,0r UR, UR.
(3)
exp (1127 (sh, an)) is the normalization constant. Also, the V value is the maximum value of the single-step KL-regularized optimization prob- lem:
where (sh)) ==
where UR, is the uncertainty in Definition 3.3, D,-1 {(x,, heeee(t- and we define the confidence set itera- tively:
1 7)
VA (8A) = log Eay--reer (-lea) exp (11Q (sh, an). (1)
R₂ = (RER: E(R(e, - Re( (,),, + + S
We also have the following connection between the Q' and V*:
'This is for the simplicity of analysis. By multiplying the results by H, our analysis can he applicd to the cases where Pa [0. 1] for E [M.)
(Sn: an) = (5n, (nn++))))))) Tenny Vh411
(8h+1). (2)
5

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
Algorithm 1 KL-Reeullarieed UCB
the definition of the bonus, the subtraction of the last two terms is upper bounded by since T7 is the maximizer of the KL-regularized reward according to Algorithm 1. Essentially, deserting the last two terms is where they loosen and reduce to the traditional analysis. As a result, their regret is upper bounded by the first-order summation of bonuses Σ Ea be (2t, me) and finally get an ((vT) regret.
1: Input: 7). 6, Rrof. R. for t= 1=
3: Sample context 2e ~ do and action de me(-(
4: Observe reward
R² (2 at) + 6e, where 6, is the
random noise.
Compute the least square estimate of the reward function based on Dj = {(rx, us, r=)
Rs + argmin RER
Σ (R(ai,))) rrs)"
Our Analysis. We provide the proof sketch of Theo- rem 4.1 here. The details are provided in Appendix A. Our analysis is divided into the following four parts.
6: Apply the planning oracle to compute (T+1++++) x (--r(-1-) exp (n (Re(t.)) + be(:-))], where is the ex- ploration bonus term defined (3).
Part I: Single-Step Regret Decomposition. For all 2 1, with Rº (z. a) 1 log exp (1/2²* (zz a)) and the closed- form solution of л- and from Lemma 3.4, have the following equality for the suboptimality gap:
7: end for
Theorem 4.1. Under Assumption 3.2, for any 8 > by taking 3T lo with probability at least 8, the output of Algorithm satisfies
log <a(ax)
B
R ('
Teet (e)
1 log (e(ar) nea (a(z)
Eai 18" (x,
Regret(T)) = 0
(4)
1 log Zx. (x)
1
=
log Z +da- (x)
Remark 4.2. Theorem 4.1 establishes that the regret of Al- gorithm scales logarithmically with T, rather than at the typical (vT)) rate, thereby improving upon the previous analysis in Xiong al. (2024a) under the standard online RL setting. To the best of our knowledge, this is the first analysis of KL-regularized contextual bandit that achieves this logarithmic regret bound.
"
"
Bis [Re-1 (2r, a) R' (z, a) (x, a)),
where ( is the normalization term for the policy with respect to reward function Rt We defer the detailed deriva- tion of (4) to Appendix A.
Remark 4.3. Compared to previous work (Xiong et al., 2024a; Xie et al., 2024; Ye et al., 2024) that neglect the KL term and reduce to the traditional RL analysis, the upper bound in (4) is more refined and involves the gap of the normalization term Zz(x), which is crucial for the analysis of the KL-regularized objective.
4.2. Proof Outline of Theorem 4.1
We first explain where the previous methods loosen and then highlight our methods to get the sharp bound.
Review of Analysis in Previous Work Previous anal- ysis (Xiong et al., 2024a; Ye al., 2024; Song et al., 2024) neglects the pivotal role of KL-regularization in the suboptimality decomposition and reduce to the tradi- tional bandit analysis. Specifically, using the short-hand notation R(x, T) = (aws(-ja) R(x, a) and KL(T[[+²) = they derive that
Part II: Shape of Regularized Suboptimality Gap. To further analyze (4), we define function
1
A R) log ZR(x) Erg [M(xa a) R² (s, a)]. (5)
and write (4) as the function gap:
R" (a, x) KL(T" [[ (R" me) (L(Te((=aa)
Ezwdo (A Ro + bb-1) - A(x, R")]
(6)
-[(a n") Ri (x,)) (x(,)²')
To analyze the behavior of (6), we have the following lemma, which reveals the gradient of A(r, R) with respect to R.
< (By Optimism)
+ (x m.) R² Rx (x) + be(x, Te)
Lemma 4.4. Let ZR(z) = EaEA (a)r(a) (xx exp((n a)) ) = Tree (alz) R(x, (n))) We have the following partial gradient result:
and nHH (alxz) (7((a)r)
< 2be m()
+ (R, x") b.( x") KL(T" (1==)]] (I, mi) (,(
0A(r, sr, R)
0R(2, a) (=)((lx) (R(x, a) R (x,
(((a)))=<(((ll (((d))))) (((,,a''R(((oooo))) 77)
where on the right-hand side of the last equality, the first two terms follow from the optimistic reward estimator and
Σ
(R(z,
d'EA
6

---

Logarithmic Regret for Online KL. KL.-Regularized Reinforcement Learning
The proof of this lemma deferred Appendix A. With the gradient information above, we can apply the mean value theorem to show that there exists fx = X- ---RR---bb-i)e (1 X) R. for some À E (0, 1) such that
5. KL--Regularized RL
5.1. The Proposed Algorithm and Result
A Algorithm 2 KL-reeglaarzed LSVI with UCB
Bn (2, R + b (z, R*)
Input: 1/, 6, Tyef. F.
2: for episode t= == I,..., T do
E Exnda
Σ
nm7 (a|z) (fa(e, Ht (x,a))
3: Receive the intial state si.
aEA
4: for stage h H...., do
3y1 (a|z) n (d'xz) (fa(z,a') R (x,,d))
5: Set fh + argmin Jaen E (fa ah) - r
11
V (8h+1))
d'EA
(Ri-1 (2, a) + b 1 a) - R (z, a))]
6:
Construct bonus (:,-) defined in (9). 7: Set (s,sa) t- (1((sa)) + by a) for any (v,a) E
S X A.
Part III: Benefits of Optimism. The bonus used in Algo- rithm ensures that with high probability, the true reward function is upper bounded by the optimistic reward function, which is formally stated in the following lemma.
8:
Set (s(s) + max, Ba (8.0) n
(L(T(-1s), Krot (-|s)]]-
9:
end for
10: for stage h ===1... I..., H do
11:
Observe s/.-
Lemma 4.5. Under Algorithmm I and Assumption 3.2 and the condition that the noises at are conditional 1-sub- Gaussian, we have with probability at least - 5 for all 1. E [T], the uniform optimism event that Eppt (Re(z,a) a) + be(xx (x, a) 2 O, a(z,a) xX holds true.
12: Follow (-1+)+) x expp(()))xpppp (.-))
13: Choose action aj ~ (+(s)s)).
14:
end for
15:
end for
We adapt the Kl-regularizztion to the Least Square Value Iteration with UCB framework (Zhang, 2022; Wang et al., 2020) to propose the KL-LSVI-UCB algorithm in Algorithm 2. which establishes the optimistic Q-value function estima- tions Qi backward from step H to step 1, with QH+11 0. In each step h E [H], we first learn the estimator f) to minimize the Bellman backward error:
Hence, conditioning on E we have Ax a') R' (xx a') 2 0, V(r,a) E X x A, which is substituted back into (8) to get
Exndo (2(x, R + b1-1) A(x, R*)]
Bddo E 1 (z) R² (x)
L-1 Σ (fh(sh aht - rh.
aEd
R = argmin E.FFF
(f)(z,a) - 1² (u, T/A (a|x)]
(8)
U(a.a)
Then, under the principle of optimism, we construct the confidence set iteratively
S HaandoBaaajl - Bar (1m] ([x]
(Re-1(z,)) a) + b (x, - R² a))
F(
{ fh Fr:
where the last inequality holds since by taking the derivative of U(I,0 a) with respect to X, we can show that a(I,a) reaches the maximum when À = 1.
Eus(h - + +xs +x)))))
and the bonus:
Part IV: Regret Bound. Conditioning on high-prroyybiliyy event Uppe we derive the regret bound from (8):
by (s, min {1,8h Uh. , (N),, (9)
T
where ftt is the uncertainty formulated in Definition 3.3, and D (sh oi rh, 1 Hence, we add the bonus to the value function estimation to get the optimistic estimation Q1 (x) (s, + 0/ (8, a) and
(Tgret(T) S
> Bay Beywang Ear
(Re-1 ar) + b be-1 az) Rd (x+, (
< 4n Bee
1
(x())) = log E exp (n (s) 77
Thus, according to the definition of bonus b, in (3), we can follow standard analyses for general function approximation under the finite eluder dimension to obtain the desired result.
For the analysis, we follow Ye et al. (2023); Wang et al. (2020) and assume that there exists a bonus function class
7

---

Logarithmic Regret for Online KL.- KI.-Regularized Reinforcement Learning
BN with cardinality NE, that accommodates bonus fune- tions b/, Ye al. (2023); Wang al. (2020) have used examples and algorithms to show that this type of bonus can be approximately calculated under suitable conditions.
For each term I4+1, since T(M) and +(++1) only differs a step h + 1, and they are both ni for h = h + 2, ..... H, we use the notation (L mT,)) == (L (-IsA) |TT (-1ss)) for short and can reduce the step-wise gap back into the bandit gap:
Theorem 5.1. Under Algorithm 2 and Assumptions 3.6 and 3.7 with $ = @ (loo((N,TH/5)) we have with probability at least 1 -6 8,
Esn 1 ddi 1 { ( mh+1) - 77 (
(5 -1 -Kkhh))))--------- (L mood nT 1(Q4
(T) = (n
log(NN (N
(5441,
where d(F,).T) = Σn a(Fn,,,T) and No = max, Ny. NNrtt NB
where the inequality holds by applying (8) with R - Qh+1 and Re+b, = Qn+1. Therefore, we can obtain the following bound for each (I++1).
5.2. Proof Outline of Theorem 5.1
Lemma 5.2. We use the notation E² for the expectation of trajectories generated by do x it. Conditioning on the uniform optimism event that Eapt = ={Q(8hs an))
We defer the detailed proof in Appendix B and highlight the crucial part of the proof in the sequel.
The crucial part of the analysis for the MDP setting lies in decomposing the regret into the errors of Bellman backup in each step. For conciseness, timators when there is no confusion. We denote the Bellman eгror as (5%, aA)) = Q as) - T 1 (8h, an).
Q7 (Thh,,a an) 2 0, V(Kn; un) ES A, h E [H]] holds,
H1
omit the superseript t for es-
I++1 S 11441 [CE
Σ 5mh41
c((s):;)))
The proof is shown in Appendix B.1. Therefore, we can decompose the regret as follows:
Review of Standard Policy Loss Decomposition. We first recall the standard decomposition without KL- regularization (Zhang, 2023):
H-1
((-))-((F) S n
Σ
[(
EeEeen f-h+11
esار aj)))
Vi" (61) - Vf s - - I F. (1), 01) ('1)
H
S <
[
(en(onn a.))
+ 01) -T' -V'22 [1))
(10)
where the second inequality is the Cauchy-Sehwar inequal- ity. Since the summation over H steps is inside the square, we can only pay an additional order of H.
S... Σ (s). - T,j
where E denotes the expectation of trajectories generated by do x 7, and T denotes the Bellman operator without KL- regularization. Thus, following the standard decomposition results in the polynomial dependence on T for the previous works (Xiong et al., 2024a; Xie et al., 2024).
Then, following the standard analysis of MDP literature (Zhang, 2023), we can demonstrate that the optimism Eapt holds with a high probability and obtain the desired bound.
6. Conclusion
Our Analysis. In this work, to avoid the direct summation of Bellman errors in (10), we develop novel decompo- sition to obtain the square of the Bellman errors. To realize this goal, instead of decomposing the value functions, we decompose the policies.
In this paper, we study KL-regularized contextual bandits and MDPs in the standard online RL setting. While these frameworks have been widely applied in the empirical post- training of modern foundation generative models, their theo- retical properties are substantially less explored. We propose two provably efficient algorithms: KL-regularized UCB and KL-regularized LSVI with UCB, based on the standard op- timism principle and show that they achieve regret bounds that scale logarithmically with T, significantly improving over the typical ((VT)) rate. To the best of our knowledge, this is the first theoretical analysis of KL-regularized RL to establish such logarithmic regret bounds in the standard online setting, aligning well with the empirically observed
For each h, let ((h) := #1sh @ Th+1H be the concatenated policy of and n" at time step h. Then, x² can be denoted as # and V/- = v= Then the suboptimality gap for के can be decomposed as follows:
#-1
Σ Eng (1
(s1) 12 12)
J(m")~ ((+)
(s1)
0=
1n+1
8

---

Logarithmic Regret for Online KI. KL.-Regularized Reinforcement Learning
superior sample efficiency of KL-regularized RL (Bai al., 2022; DeepSeek-Al et al., 2025). An expense of this log- arithmic bound for MDPs is that the bound has additional dependence on the horizon H, which can be left as future work.
dueling bandits: A survey, The Journal of Machine Learn- ing Research, 22(1):278-335 2021.
Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J., Rando, J., Freedman, R., Korbak, T., Lindner, D., Freire, P., et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:230..15217, 2023.
The key to this improvement lies in a refined value decom- position for the bandit setting and a novel policy decomposi- tion technique for MDPs, both of which may be of indepen- dent interest. We hope our study inspires further theoretical investigations into the learning dynamics of KL-regularized RL.
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., Schuurmans, D., Chi, Y., and Dai, B. Value-incentivized preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:24055 19320, 2024.
Impact Statement
Chen, X., Zhong, H., Yang, Z., Wang, Z. and Wang, L. Human inetaan-intther in-the-loop: Provably efficient preference- bassed reinforcement learning with general function approxima- tion. In International Conference on Machine Learning, pp. 3773-3793, PMLR, 2022.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Chen, Z., Deng, Y., Yuan, H., Ji, K., and Gu, Q. Self-play fine- miee-tuning converts weak language models to strong lan- guage models. arXiv preprint arXiv:2401.01335. 2024.
Acknowledgements
We thank the anonymous reviewers for their helpful com-
Choshen, L.,, Fox, L.,, Aizenbud, Z., and Abend, O. On the weaknesses of reinforcement learning for neural machine translation, arXiv preprint arXiv:190..01755 2019.
ments. HZ and QG are supported in part by the National Science Foundation DMS-23231 13 and IIS-2403400. HZ is also partially supported by the Amazon PhD fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
References
DeepSeck-AI, Guo, D., Yang, D., Zhang, H., Song. J., Zhang, R., Xu, R., Zhu, Q., Ma, s., Wang, P., Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, 7.,, Gao, Z., Liu, A., Xue, B., Wang, B., Wu, B., Feng, B.. Lu, C., Zhao, C., Deng, C., Zhang, C.,, Ruan, C., Dai, D., Chen, D., Ji, D., Li, E., Lin, F., Dai, F., Luo, F. Hao, G., Chen, G., Li, G., Zhang, H., Bao, H., Xu, H., Wang, H., Ding, H., Xin, H., Gao. H., Qu, H., Li, H., Guo, J., Li, J., Wang. J., Chen, J., Yuan, J., Qiu, J., Li, J., Cai, L.,, Ni, J.. Liang, J., Chen, J., Dong, K., Hu, K., Gao, K., Guan, K., Huang, K., Yu, K., Wang. L.. Zhang, L., Zhao, L., Wang, L., Zhang, L., Xu, L., Xia, L., Zhang, M., Zhang, M., Tang, M., Li, M., Wang, M., Li, M., Tian, N., Huang, P., Zhang, P., Wang, Q.. Chen, Q., Du, Q. Ge, R., Zhang, R., Pan, R., Wang, R., Chen, R. J., Jin, R. L., Chen, R., Lu, S., Zhou, S., Chen, S., Ye, S., Wang, S., Yu. S., Zhou, S., Pan. S., Li, S. S., Zhou, S. Wu, S., Ye, S., Yun, T., Pei, T., Sun, T., Wang, T., Zeng, W., Zhao, W., Liu, W., Liang, W., Gao, W., Yu, W., Zhang, W., Xiao, W. L., An, W., Liu, X., Wang, X., Chen, X., Nic, X., Cheng, X., Liu, X., Xie, X., Liu, X., Yang, X., Li, X., Su, X., Lin, X., Li, X. Q., Jin, X., Shen, X., Chen, X., Sun, X., Wang, X., Song, X., Zhou, X., Wang, X., Shan, X., Li, Y. K., Wang, Y. Q. Wei, Y. X., Zhang,
Agarwal, A., Jin, Y., and Zhang, T. Vo q I: Towards optimal regret in model-free with nonlinear function approxima- tion. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
Askell, A., Bai, Y., Chen, A., Drain, D., Ganguli, D., Henighan, T., Jones, A., Joseph, N., Mann, B., DasSarma, N., et al. A general language assistant as a laboratory for alignment. arXiv preprint arXiv:2 arXiv:2112.0086/1 2021.
Azar, M. G., Rowland, M., Piot, B., Guo, D., Calandriello, D., Valko, M., and Munos, R. A general theoretical paradigm to understand learning from human preferences. arXiv preprint arXiv:2310.1 12036, 2023.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training helpful and harmless assistant with rein- forcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022.
Bengs, V., Busa-Fekete R., El Mesaoudi-Pare Paull A., and Hüllermeier, F. Preference- based online learning with
9

---

Logarithmic Regret for Online KL. Kl.-Regularized Reinforcement Learning
Y, Xu, Y., Li, Y., Zhao, Y., Sun, Y., Wang, Y., Yu, Y., Zhang, Y., Shi, Y., Xiong, Y., He, Y., Piao, Y., Wang, Y. Tan, Y., Ma, Y., Liu, Y., Guo, Y., Ou, Y., Wang, Y., Gong,
Lambert, N., Morrison, J., Pyatkin, V., Huang, S., Ivison, H., Brahman, F., Miranda, J. V., Liu, A., Dziri, N., Lyu, S., et al. Tę" ulu 3: Pushing frontiers in open language model post-training. arXiv preprint arXiv:2411.1512 2024.
Y., Zou, Y., He, Y., Xiong, Y., Luo, Y., You. Y., Liu, Y., Zhou, Y., Zhu, Y. X., Xu, Y., Huang, Y., Li, Y., Zheng,
Y. Zhu, Y., Ma, Y., Tang. Y., Zha, Y., Yan, Y., Ren, Z. Z., Ren, Z., Sha, Z., Fu, Z., Xu, Z., Xie, Z., Zhang, Z., Hao,
Langford, J. and Zhang, T. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Z. Ma. Z.. Yan, Z., Wu, Z., Gu, Z., Zhu. Z., Liu, Z., Li, Z., Xie, Z., Song, Z., Pan, Z.,, Huang, Z., Xu, Z.,, Zhang, Z. and Zhang, Z. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL ht https: httpxxiivv..oo////a//aaa hts///bs/2200000 12948.
Li, X., Zhao, H., and Gu, Q. Feel-good thompson sam- pling for contextual dueling bandits. arXiv preprint arXiv:2404.06011 2024.
Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang, T. Raft: Re- ward ranked finetuning for generative foundation model alignment. arXiv preprint NXi622304.06767, 2023.
Li, Z., Xu, T., Zhang. Y., Yu, Y., Sun, R., and Luo. Z.- Q. Remax: A simple, effective, and efficient reinforce- ment learning method for aligning large language models. arXiv e-prints, pp. arXiv-2310, 2023a.
Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., Jiang, N., Sahoo, D., Xiong, C., and Zhang, T. Rlhf workflow: From reward modeling online rlhf. arXiv preprint wxXiv2205.07766. 2024.
Li, Z.,, Yang. Z.,, and Wang. M. Reinforcement learning with human feedback: Learning dynamic choices via pessimism. arXiv preprint arXiv:2305. 18438, 2023b.
Lin, Y. Tan, L., Lin, H., Zheng, Z., Pi, R., Zhang. J., Diao, S., Wang, H., Zhao, H., Yao, Y., al. Speciality vs generality: An empirical study on catastrophic forget- ting in fine-tuning foundation models. arXiv preprint arXiv:2309.0mm 06225,, 2023.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A. et al. The Ilama herd of models. arXiv preprint arXiv:2407.2178. 2024.
Foster, J. and Rakhlin, A. Foundations of reinforcement learning and interactive decision making, arXiv preprint arXiv:2312.167310 2023.
Liu, Z., Lu, M.. Zhang, S., Liu, B., Guo, H., Yang, Y., Blanchet, J., and Wang, Z. Provably mitigating overopti- mization in rlhf: Your sft loss is implicitly an adversarial regularizer. arXiv preprint arXiv:2405. 16436, 2024.
Guan, M. Y., Joglekar, M., Wallace, E., Jain, S., Barak, B., Heylar, A., Dias, R., Vallone, A., Ren, H., Wei, J., et al. Deliberative aligmment: Reasoning enables safer lan- guage models. arXiv preprint 2rXiv:2412.16339 2024.
Meng. Y., Xia, M., and Chen, Simpo: Simple preference optimization with reference-free reward. arXiv preprint arXiv:2405.477:: 2024.
Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J. Dueling posterior sampling for preference-based rein- forcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 1029-1038. PMLR, 2020.
Gui, L., Gârbacea, C., and Veitch, V. Bonbon alignment for large language models and the sweetness of best-of-n sampling. arXiv preprint 20X1::2406.00832. 2024.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Mcasuring math- ematical problem solving with the math dataset. arXiv preprint arXiv:2103.03877, 2021.
OpenAL. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023.
Ouyang, L.,, Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744 2022.
Huang, A., Zhan, W., Xie, T., Lee, J. Sun, W., Krishna- murthy, A., and Foster, D. J. Correcting the mythos of kl-regularization: Direct alignment without overparame- terization via chi-squared preference optimization. arXiv e-prints, pp. arXiv-2407, 2024.
Pacchiano, A., Saha, A., and Lee, Dueling rl: reinforce- ment learning with trajectory preferences. arXiv preprint 1 1..04500, 2021.
Jin, C., Liu, Q., and Miryoosefi. S. Bellman eluder di- mension: New rich classes of problems, and sample- efficient algorithms. Advances in neural information processing systems, 14:13406-1341 2021.
Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, D., and Finn, C. Direct preference optimization: Your
10

---

Logarithmic Regret for Online KL.- KL.-Regularized Reinforcement Learning
language model is secretly a reward model. arXiv preprint arXiv:2305.18221 2023.
Tunstall, L.,, Beeching, E., Lambert, N., Rajani, N., Ra- sul, K., Belkada, Y., Huang, S., von Werra, L., Fourrier, C., Habib, N., et al. Zephyr: Direct distillation of Im alignment. arXiv preprint arXiv:2310.
Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
2023.
Wang. R., Salakhutdinov, R. R., and Yang, L. Reinforce- ment learning with general value function approximation: Provably efficient approach via bounded eluder dimen- sion. Advances in Neural Information Processing Sys- tems, 33:6123-61333 2020.
Saha, A. Optimal algorithms for stochastic contextual prefer- ence bandits. Advances in Neural Information Processing Systems, 34:30050-30000 2021.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. 2017.
Wang, Y., Liu, Q. and Jin, C. Is rlhf more difficult than standard rI? arXiv preprint arXiv:2306.141111 2023.
arXiv preprint
Wu, R. and Sun, W. Making with preference-bane feedback efficient via randomization. arXiv preprint SKGV:23310.45552 2023.
Shao, Z., Wang, P. Zhu, Q., Xu, R., Song, J., Zhang, M., Li, Y., Wu, Y., and Guo, D. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
Xie, T., Foster, J., Bai, Y., Jiang, N., and Kakade, S. M.
The role of coverage in online reinforcement learning. arXiv preprint arxiv:2210.041557 2022.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panncershelvam, V., Lanctot, M., al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Xie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadal- lah, A., and Rakhlin, A. Exploratory preference optimiza- Harnessing implicit q"-approximation for sample- efficient rlhf. arXiv preprint arXiv:2405. 2024.
tion:
Song, Y., Swamy, G., Singh, A., Bagnell, D., and Sun, W. The importance of online data: Understanding prefer- ence fine-tuning via coverage. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists, 2024.
Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Con- ference on Machine Learning, 2024a.
Sutton, R. S. Reinforcement learning: An introduction. A Bradford Book, 2018
Xiong, W., Shi, C., Shen, J., Rosenberg, A., Qin, Z., Ca- landriello, D., Khalman, M., Joshi, R., Piot, B., Saleh, M., et al. Building math agents with multi-turn iterative preference learning. arXiv preprint arXiv:2409.02255 2024b.
Team, G., Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.-B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M.. Hauth, A., et al. Gemini: a family of highly capable multimodal models. arXiv preprint 2r /880, 2023.
Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. Preference- reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-188777 18794, 2020.
Tiapkin, D., Belomestny, D., Calandriello, D.,, Moulines, E., Munos, R., Naumov, A., Perrault, P., Tang, Y., Valko, M.. and Menard, P. Fast rates for maximum entropy exploration. In International Conference on Machine Learning, pp. 34161-34221. PMLR, 2023.
Yang, J. Q., Salamatian, S., Sun, Z., Suresh, A. T., and Beirami, A. Asymptotics of language model alignment. arXiv preprint arXiv:2404.00 0/0440 2024.
Tiapkin, D., Belomestny, D., Calandriello, D., Moulines, E., Naumov, A., Perrault, P., Valko, M., and Menard, P. Regularized rl. In The Twelfth International Conference on Learning Representations, 2024.
Ye, C., Xiong, W., Gu, Q. and Zhang, T. Corruption- robust algorithms with uncertainty weighting for nonlin- ear contextual bandits and markov decision processes. International Conference on Machine Learning, pp. PMLR, 2023.
Touvron, H., Martin, I.., Stone, K., Albert, P., Almahairi, A., Babaci, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint Xxiv:2307.00928, 2023.
Ye, C.,, Xiong. W., Zhang, Y., Jiang, N., and Zhang, T. A the- oretical analysis of nash learning from human feedback under general re-ruullrd preference. arXiv preprint arXiv:2402.07314 2024.

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences,
2012.
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. /48/6, 2023a.
Zhan, W., Uehara, M., Sun, W., and Lee, D. How to query human feedback efficiently in rl? arXiv preprint arXiv:2305.18505. 2023b.
Zhang, T. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857 2022.
Zhang, T. Mathematical analysis of machine learning algo- rithms. Cambridge University Press, 2023.
Zhao, H., He, J., and Gu, Q A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. arXiv preprint arXiv:2311.15238 2023a.
Zhao, H., Ye, C., Gu, Q., and Zhang, T. Sharp analysis for kl-regularized contextual bandits and rlhf. arXiv preprint arXiv:24/1.04022 2024.
Zhao, Q.. Ji, K., Zhao, H., Zhang. T., and Gu, Q. Nearly optimal sample complexity of offline kl-regularized con- textual bandits under single-policy concentrability. arXiv preprint 20Xiv:2502.0660 2025.
Zhao, Joshi, R., Liu, T., Khalman, M., Saleh, M., and I Liu, Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint 2005 2023b.
Zhong, H., Feng, G., Xiong, W., Zhao, L.., He, D., Bian, J. and Wang, L. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint 41X192200.11822,, 2024.
Zhu, B., Jiao, J., and Jordan, M. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXhv:2301.11270 2023.
12

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
A. Proofs for KL- Reggaauua Contextual Bandits
Lemma A.1 (Objective Decomposition). For any E [T], conditioning on the uniform optimism event that Eot {Re(2, a) + (x Rt (z, a) 0, ((x, E X A3 holds, we have
R2' J(x') ( S nB [Re, (xx, + -
Proof. For all t 2 I, with Ht (zz a) 1 log exp (n (2 a)) and the closed-form solution of n² and ι from Lemma 3.4, have the following equality for the suboptimality gap:
log (a(a))
1 <<(a/x))
E,
R (2)
E,,,
R (I,
log
7 (a)((
" Tre((alz))
Tref (a (z) exp(11( (I,
1
log [ror(a|z) exp(1 (x, a))
E
log
Biz
1)
(a/z))
17
(a(z)
log Tref (a/o)) exp(nR aI)
1
Em. log [ar((a/)) exp(n( R R a) + b 1 a)))
- Enr
(a(px)
Te. (1(()))
11
+ Es. (2,1(2,,))
R² (z, a) + +b (Ix
log n--(x) "1
log 1 +b (x) + Ex, (2, - R (z, a) (1, a)),
(11)
17
where Zn(x)= = EnEd (a)(( exp(nR(2, a)) is the normalization term for the policy with respect to reward function
R.
define Aax, R) as the following quantity for a reward function R: X -
Teet (a|x) exp(n)(xx.a)) Za(x)
(xx, R)
log Zn(xx)
Σ
(R(x,a) (*
(12)
1
log (R(I)
E [R(I, R2 (2,
With the definition of ((r, a), the gap in (11) can be written as Ez [Ax Re-1 + -1,, R)) To analyze the
behavior of Egwd, (r. R b(-1) A (Ix, R*) we now study the gradient of A(r, R). We are interested in the gradient of A (x, R) with respect to Rxx, a) for each E A.
Then, by invoking Lemma A.2 to simplify the computation, we can write the gradient as follows:
(A(r, R)
0[ 1 log ZR (z) + E [[xx,a] a) - R² (I, a]]
aR(I,a)
0K(I,0 a)
1 1 (Z)(2)
OR(2,a) (a/())) (R(x,a) (x, a))
17 Zz(x) 2R(r, a)
Σ
(d'=)) (R(x,a')- (*,aa)))
aR(r, a)
a'za
(Ta((az) (R(z,a')- - - (x,x)))))
= + [
0
(d'lz (R(z, a) - H² (I,
0R(z,a)
- (R(z,a) Rd (x, - E n=b((l=) =/(('(=) (R(z, (x, (x,
a'$a
-=)((/x>) (R(x,
a) (()((a)))(R((,,))) R (x, - n Σ (a(a))
(2(((()) (R(z, a') R (x,aa))
a'EA
where the third equality uses (14) and the fourth equality uses (15) and (16), the second equality and the last equality simply use the linearity of 0 and summation.
13

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
Since (A(,.R) uniformly bounded when R uniformly bounded, by the Mean Value Theorem, there exists fx 3M(2,0)
A (Rr-1 + 1) + (1 2) R2 for some À E [o, 1] such that
Byrdoo [ (r, Ro- + bb-1) - (xx R*)]
0D(a', fx)
Eo'nda Σ
(R a) + b,)) 18 (pxx,))) a))
@R(x,a)
aEA
= Eg'nndo
(1777 (a/z) (fx(2, - (x, Σ
J (alz) <d -((t)) (
aEA
a' EA
(Re-1(I, a) b (1, a) R (2)
S Be
(Ri-1(x,a) + az, - R (x, (fx(x, - (x, n.H (a/x)]
(13)
aEA
U(2,a)
where the last inequality holds since conditioning Spp have
fa a') Rt (x, a') = A(Ro-1(z, a) + (f((,)))) 20, Exx
We use the notation 5, = RR + by R.. Let
U(A) Σ (2, To(a|z) exp (2)
for A E 10.
Exo exp (2) 18 (z
aEA
We take the derivative as follows:
(U())
6--1 a) TT,, 10,-1 (To(a(x) exp
1700 1101-1(2,0)
Σ
02
ETD exp (1(A6)- + R (x, a)))
mo(a|z) exp (T(A6)_1(2, + (x, a))) Em, 16. cop
exp
(x,
(x)
Em exp
+ a))))
5 1 51 6 (2, x/² 101-1 1T (666-1 -
= E [5,-1
a) +
{ Buz, (x, a)
Eny [ (2,, .Ry, (2,
20,
where the inequality holds since for random variable X 2 0 have
-[ -[X] = E[(X² - (Xx - E[X]]
E[((2 +
- [[X])] +
= (x E(X))
E[(( E[X]) - E[X]) +0
0,
which follows from Lemma 2. in (Zhao al., 2025). Therefore, since (1x S R2-1(1, a) + 1e-1(1, a) for any (x, X x A, we can obtain that
U(A) < U(1) = Σ 6,- (x, R R (alz))
aEA
We further have the following bound for RHS of (13):
J(x²) - J(TT) =R A(x, P + b.-1)
A(x, R*))
14

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
So B Bawni Ry_, 18-1 (1w) (Rt + ( (x, a)) J.
Lemma A.2. Let (z(z) = EaEA (ref(a exp(n](a, a)) and (2((/))) [ree(a exp((((x,))) have the following Zx(z)
partial gradient results:
0Zn(2) m exp (1 a)),
(14)
OR(x,a)
0Tz(a/z) dR(r,a) = -
(15)
For d' # have
0= (d'lz) aR(r,a)
(16)
Proof. The proof is deferred to Appendix C.
Lemma A.3. Under Algorithm and Assumption 3.2 and the condition that the noises Et are conditional 1-sub- Gaussian, we have with probability at least 1 6 for all E [T], the uniform optimism event that Eops 0, v(x,a) X A} holds true.
R (z, Z
Proof. By invoking Lemma C.I with F = R. X A and 1.we have for all [2'] with probability least 1- 8.
Σ (a(2,,))) - Rt a:)) 8log((NN = 2
1 B9.
(17)
Hence, we deduce that for any (
R1 a) R2(2, a)
Rd (2,
(2) 5 sup RoER
A
Σ
RR (R - Re(x;, a:))
A++ Ei=1 i== (Ri()))))) Ro(x,, a2))
1
S 2x, V /A+ 2 2
- (A, a; D:) $r,
where the second inequality follows from the definition of UR and (17), and the last inequality uses S 1.07 and the choice of bonus by. Besides, since R (x. a) Re(x, a) S 1, we have
R2 (x, (2 < (()
Therefore, we get
(,(x, + (z, (x, 20. O.
Proof of Theorem 4.1. Let
Ri at) R2(we, ar)
U, = sup
Ru R.ER
Σ (B) (Ri, a4) a2))
We know from Lemma A.3 that Userr Eppt holds with probability at least Thus, conditioning on Uter we invoke Lemma A.l to get
T Regret
(J(TT) -((e)
mm1
15

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
E Exi Baiwnr [Rr
1 ar) + b ax) - R (1x; ax))
t=1
4n
Begg Ba (1),)
de Bayw min {I, (UR, (2,33, Dt)))=)))
4npT
- (7 d (R,,,T)).
where the second inequality uses the condition -, the second equality uses the definition of bonus b, in (3), and the last inequality follows from the value of 3r and the cluder dimension in Definition 3.3.
B. Proofs for KL-Regularized RL
B.1. Regret Decomposition
Lemma B.1. We use the short-hand notation E for the expectation trajettriis generated by do â, and
en(sn, an) Qu(sn, an) Tit V ( an) = (1 an)
Irn + (
Conditioning on the uniform optimism event that Eopt holds, we have
(sh, ah)
(7, ah) 20, V(sh an) E E A, h E [A]
H
-(a")-J(TT) I TE
Σ h=l
([ee(())))))
jmh
Proof. For each h, let *(h) := Tish 2 1h+1 be the concatenated policy of गे and π at time step h. Then, n² can be denoted as 7(0) and V/' = V= Then the suboptimality gap for can be decomposed as follows:
n Σ
VT (s1) V((
Es [Viath) (s1) - Vi 1ith (s1)]
1n41
For each term I4+1, we deduce that
(A) h+1 (snt1) v (su+1)]
E en
E sn E [0 (8h41, -1 - (14
Ex (aahhti) (5n+1,an41) (1
E rod 1i { EErpy, [Q
01+1) - (
Ex,1 aa Q (S641, ax41) - - (100 (44
where the second equality follows from the fact that 2/(h = # (h+1) = ग for = h + 2,.., H.
Then, we can follow the analysis of Lemma A.I for each step h + 1 with do di R² Q x" Thtt and 7h derive that
TA S <R (( - (1+)))))
Further, conditioning on Eapt. deduce that
2 1h+ (8h+1, Qu+ (S1+1, (x41)
16

---

Logarithmic Regret for Online KI.-Regularized Reinforcement Learning
ee (1++((0)2)) (
B/e 11/111190 1.th 11 log ot
en+ (sh+1sh ap+1)
B. 104+1
(Q an+2)
Q0+2( 0 (($2+1,
N.
IV
Σ eg)s
J2h+1
where second inequality holds due to the Jensen's inequality. Taking this back to Ja+1 leads to
1++1 S 1
Σ es(s,,))))
a))
12h-1
S
B Jent anti
I(
Σ f=h+1
cg(s), aو) e
where the second inequality uses the Jensen's inequality. Therefore, we get
S
Σ B
{<E Σ
c)(s,,
h=o
1=h+1
Lemma B.2 (Confidence Sets for Value Function). Let fh. be the estimator as defined in Algorithm 2 and
p = =//og(ANN,TH/0)
where define N₂ Nyr, NN NB (A)- Then, with probability at least 6, we have for all & [T] and h (H).
(s) TT, 1 a)) S 8h UAA (s, a; D/ ((s,a)E8xx
(sn, an) Q7 (St, an) 0,
where D denotes the history data { hiett-1)
Proof. For k E [K]. h E [M] let St be the o-algebra generated by the random variables representing the state-action pairs up to and including those that appear stage h of episode k. That is, St is generated by
st, a Sh 0 $ a...... ......
H a
2
sn a ..... i 0
2
2
$1. of.
s aj
Let Qi+1, V4+1 be the set of possible value functions, i.c.
2x+1 {g S x A 3/h+1 E 11+11.441 E BR41 8.1. g = sh+1 + bnt1),
V4+1 = {g: : S + Qu+1 E Q1+1 s.t. g(.) = max (1+i(:,0)) a
The proof is based on the standard concentration inequality for the least square estimator (Zhang, 2023).
For simplicity, denote by ef, the noise term in the least square estimator with respect to arbitrary value function Va+1 E Vis1.c..
c) = rh Vn+i ( -T, T, Vn+i at))
17

---

Logarithmic Regret for Online Kl.-Regularized Reinforcement Learning
By definition,
S = 0, le S 1.
Hence, by invoking Lemma C.1 and using a union bound over V4+1. we have for all & [7] and h [H], with probability least 1 6,
1
[Rithh, ah) - Vh at,]] S (8og(4NN,HH/5) S (
(3())
(18)
where the first inequality follows from the definition of N₂ and [V++1l N NN using union bound over all t 2 1.
Then can complete the proof
Therefore, for any (s, a) E E x A, we have
L-1
(()s - -T Di (8, a)) S U' (8, (s,;;
A+
ah) - -T,- (th
$ (8 U (s, a; 1)
(19)
where the first inequality holds by using the completeness of the Bellman operator T Vt h+1 E Fn and the definition of uncertainty U and the last inequality applies (18) and X S 2
Morcover, we will prove Q (sh, an) - 27 (sh, an) 2 A [H] by induction. At step H + 1, we know that Q7 = Q = 0.
Assume that at step + 1, we have
(8+1,,01) (86+1,041)) 0.
Then, at step h, we obtain that
Qh(sn. an) - Q7 (sh, an)
= Ph (sh, an) + +/i an) Vi
Th Vitt (sh,an) an) (37)) UA, (8, a; DL_1) + (8%)) UA (s,a; D/_1) TT Vitta ash,an)
E 10 log Ban 11 exp
- 11+1 (0+++((+++11
w NV
0.
where the first inequality uses (19) and the definition of bonus b9, in (3), the second inequality follows from the derivation of the value function in (1), and the last inequality is due to the induction hypothesis at step h + 1.
Proof of Theorem 5.1. From Lemma B.2 we know that Eaps holds at all time step t [T] with probability least 1 8. Hence, by applying Lemma 5.2 for each & E [T]. we have
H
H
J( - J(**) s πET
Σ
(IO))()))))
- ( a;)l)) "
hm1
jmh
- (3) 2
qHE**
h=1s=h
Σ
(oh
-T,, 1
- (sh. an) )
where the second inequality applies the Jensen's 's inequality.
Then, by Lemma B.2, with probability at least. 6. we have for all & E [7] and E [H].
Q (Sh, a+) - -Tih Dr 1 (sh, an) = by (Sh. an) + Rh (8h, an) - T,i 1 an)
18

---

Logarithmic Regret for Online KL.- Kl.-Regularized Reinforcement Learning
(y ah) +B% -U3, (0h, ani D(-1)
= =33 U3, (5h. Ani 1)-
where the last equality uses the definition of bonus b
Therefore, we have
Regret (T)
> (
T H
S 4n
Σ
F
do &. [U,, (sh, ax: (0::D_1)) 1)-1))
= = -((HH'dFFFAT)) Ollgg(
where d(F,A,T) Em=
hh=1 d,T).
C. Proof of Technical Lemmas Proof of Lemma A.2. For the first equation, we notice that
(Zn(v)
E''' Fe (x) exp (n)((r,
@R(z,a)
0R(2,0 a)
no (a|z) exp (nR(x,,)) a))
ŌR(a, a) = TT (a/r) exp (gR(x,a)) a)).
For the second equation, with the derivation rule of [
((a))())) (0(2))
we have
9(=)
0 (a|a)
o Troe (a exp
(1)
aR(z,a)
dR(r,a)
(T exp (n 0.) Rx(x) - 0Zn(z)) Trel exp (n a))
ZR(z)²
-mb(( - (a)=))
where the first equation in the last step. Finally, for the last equation, we have
0x7 Teer (a'l<) exp (1)((z, (Z))/((z))
aR(r,a)
aR(r, a)
(re (x) exp (n) d/)) (Z)(())
ZR(Z)²
= =-n=x(a(>) (a'
We follow Theorem 13.15 from Zhang (2023) and Ye et al. (2023) to derive the in-sample error for the function.
Lemma C.I. Consider a function space F Z + R and a filtered sequence (zt, E Z x R so that e, is conditional zero-mean ---ub-Gauud Gaussian noise. Suppose that is a finite space with cardinality Ny For fa(-) + R. suppose that f=(, a.) + Et. If ft is an ERM solution:
fe = =aagmiin
Σ (f(2)))911)
JEF
19

---

Logarithmic Regret for Online KL--Regularieed Reinforcement Learning
with probability at least 1 have for all E [
E(f(()) fa(2))² ( log@PoogNNNT
Proof. For f E F, define
o(f xz) -a [ff(2) - 11)² - (f((z) y1
-a (f((z) - fx(2) - =e)² ei
20([(zz) - -f(())) 6 alf(zz) {z()))
where = =1/ 2/4 Since e is yysub-Gasusse conditional S = 12/ G. 11 we get
log E. exp + f+(z)))
4a
(f(z)) - fa(z)))²
2
8r72
which means that
(((=)) -
((=))-(<ss)) (=()))
(f(z)) fa(z)))
log Ey exp (o(f.2))))
2
8112
41/2
8172
Then, by Lemma D.I with À = 1, we have for all f E F and t E [7]. with probability at least
6,
off 21) S log Fy, Exp (Ø(f. 1og(N+///)
S (f(z)) - fz + 1og(N)111))
8r7
Additionally, since fo is the ERM solution, have
Σ sfPe 21) = - - -1) - -0(()) 2 o.
1=1
1=1
Combining the results above leads
(f((z)) fa(z))² 5an (
D. Auxliary Lemmas
Lemma D.1 (Russo & Van Roy 2013). Consider a sequence of random variables {Ze JeN adapted the filtration { and a function f F. For any X 0, with probability at least 1 for all t 1, have
(S,1) log(1/0)
f(Z.) log Ele -r(Z)))
X
Proof. For a detailed proof, see Theorem 13.2 of Zhang (2023) or Lemma 34 of Foster Rakhlin (2023).
Lemma D.2 (Online-to-bane -btth conversion). If an algorithm has a sublinear regret of ct llg T, then the algorithm finds an e-optimal policy with at most (cc//c samples, where θ omit logarithmic terms of ct /e. Here ct is a problem-dependen constant.
20

---

Logarithmic Regret for Online KL.-Regularized Reinforcement Learning
Proof. We denote the policy sequence (m";"". n²). Then, by definition of regret, know
(T) TT (V Σ Vi (x1)
Sc¹ log T.
We consider the uniform policy मे Uniform(r 1. x²) It follows that
T
log T T
V(()))
Σ
vr (21) sel.
It suffices to prove that which is equivalent solving
c². log c,
T
T S exp(T c/c)).
By using the Lambert W function', we can prove that
T W(1)e²
where ((1) 2 log(1/e) log (1/e).
httress//..withppeiierr////////e wtw.canttrrrt_ffftioooooooo function
21


Reviews:
[{"review_id": "1vlvfH4fpr", "reviewer": "Reviewer_b9cv", "summary": "The paper presents new high-probability regret bounds for entropy-regularized contextual bandits and finite-horizon reinforcement learning. Concretely, the authors show that the regret bound is logarithmic in the time horizon, which improves asymptotically on existing bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer b9cv\n\nThank you for your positive feedback! We answer your questions point-by-point.\n\n**Q1** After defining the eluder dimension and providing an example, the authors do not discuss it further. However, the overall regret bound is only logarithmic in $T$ if the eluder dimension is logarithmic in $T$. I understand that there are function classes for which this is true, but the authors need to discuss the implications of this, especially since they promote entropy-regularization for large-scale RLHF.\n\n**A1** Thank you for the insightful comment! Eluder dimension plays an important role in our analysis for the regret bound. Here we provide a discussion of the eluder dimension as follows. The concept of eluder dimension is first introduced in [1], which serves as an important complexity measure for studying reinforcement learning with general function classes. It has been shown that for a (generalized) linear function class, the eluder dimension is $\\sim d\\log T$ where $d$ is the dimension of the function class [2]. Our logarithmic-in-$T$ regret bound holds when the eluder dimension grows at most logarithmically with $T$. We will add the detailed discussion and the clarification in our revision.\n\n---\n\n**Q2** In finite-horizon reinforcement learning it is usually assumed that the value function is bounded by $H$ rather than 1. The authors do not make it clear what the exact dependence on $H$ is if we change this assumption?\n\n**A2** Thank you for your insightful question! If the value function is assumed to be bounded by $H$, then $e_j$ in Lemma 5.2 (on page 8) will be $O(H)$ times larger, which further yields an $O(\\eta H^4\\cdot d \\log \\mathcal{N})$ regret bound after applying Lemma 5.2. The additional dependence can be removed via variance weighting and the Bernstein inequality, which is, however, not the focus of our work. We will add this disscussion in the revision.\n\n\n[1] Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. NeurIPS 2013\n\n[2] Wang, Ruosong, Russ R. Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. NeurIPS 2020.", "claims_and_evidence": "The main claim is in the form of high-probability regret bounds, and the evidence is in the form of a theoretical analysis that supports the claim.", "methods_and_evaluation_criteria": "Entropy-regularization is often used in reinforcement learning applications, but this paper is purely theoretical.", "theoretical_claims": "I did check the proof outline, and to the best of my knowledge the theoretical claims are correct, though I did not check the proof of each individual lemma in detail.\n\nAfter defining the eluder dimension and providing an example, the authors do not discuss it further. However, the overall regret bound is only logarithmic in T if the eluder dimension is logarithmic in T. I understand that there are function classes for which this is true, but the authors need to discuss the implications of this, especially since they promote entropy-regularization for large-scale RLHF.\n\nIn finite-horizon reinforcement learning it is usually assumed that the value function is bounded by H rather than 1. The authors do not make it clear what the exact dependence on H is if we change this assumption (H^2?)", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The theoretical results of the paper shed light on why entropy regularization is commonly used in successful applications of reinforcement learning.", "essential_references_not_discussed": "I am not aware of any.", "other_strengths_and_weaknesses": "In terms of strengths, the analysis depends on novel regret decompositions which may be of interest in other areas. In particular, I had never seen the regret decomposition that changes the policy for one time step at a time, which allows bounding the local regret as the expected square difference in value functions at that time step.\n\nIn terms of weaknesses, I miss a discussion of the eluder dimension as mentioned above.", "other_comments_or_suggestions": "The name KL-UCB already exists in the literature, and I would strongly advice the authors to change the name of their novel algorithms.\n\nI think the introduction makes excessive references to RLHF. Though LLMs have provided a successful application domain for reinforcement learning in recent years, entropy regularization is commonly used with reinforcement learning in a wide range of domains, and there is nothing specific to RLHF in the proposed algorithms.\n\nIn the first paragraph of related work, there are two almost identical sentences about PPO for LLMs.", "questions_for_authors": "What is the exact dependence on the horizon H?\n\nAre there known results regarding the eluder dimension for the class of neural networks used to train LLMs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ePlFNLmMrR", "reviewer": "Reviewer_SUKH", "summary": "The authors noted that the theoretical differences between KL-regularized reinforcement learning (RL) and standard RL have not been thoroughly explored. Recent studies analyzing KL-regularized objectives in decision-making either revert to traditional RL settings or depend on strong coverage assumptions. In the KL-regularized contextual bandits and Markov Decision Processes (MDPs) within the online RL framework, the authors proposed KL-regularized UCB and KL-regularized LSVI with UCB. These two algorithms are based on the standard optimism principle and demonstrate that they achieve regret bounds that scale logarithmically with the number of rounds, T.\n\n## update after rebuttal\nThanks to the authors' efforts in providing feedback. For the simulated experiments conducted by the authors, it is recommended that they include detailed information about the experimental settings related to the controllable synthetic environment. This information should be provided in the supplementary material for clarity and transparency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer SUKH\n\nThank you for your insightful comments! We address your questions as follows.\n\n**Q1** The two proposed algorithms are said to achieve regret bounds that scale logarithmically with the number of rounds, T. To support these claims, empirical validations should be conducted in real-world Reinforcement Learning from Human Feedback (RLHF) experiments to provide valuable insights. It is curious whether any empirical validations related could be provided.\n\n**A1**: Thanks for the point. We would like to clarify that the main focus of this project is to understand the statistical limit of the online decision making under the KL-regularized objective. Past experience suggests these understandings can be effectively connected to the downstream real-world algorithmic designs in principle, though with certain heuristic approximation to overcome the gap between the theoretical side and the empirical side. Even in the RLHF literature, we notice that the theoretical advantage of iterative RLHF/DPO was first established in [1] and then its empirical recipe is presented in [2, 3] and became standard practice in the past year. The idea of pessimism was established in [4], and empirical community construct reward model with uncertainty penalization to mitigate the reward hacking issue [5].\n\nWe hope that the insights from this work can motivate a comprehensive study with real-world experiments for future work, which is beyond the scope of this work. Meanwhile, a direct validation of the faster rate with real-world experiments is also not feasible since we have no access to the groud-truth reward. \n\nHowever, we agree that empirical study can help to make the study complete. Therefore, we conduct some simulated experiments under controllable synthetic environment. Specifically, we run simulations for our algorithm under a multi-armed linear contextual bandit and different values of KL-regularization parameter $\\eta$. The result provided at this anonymous link https://anonymous.4open.science/r/Simulation_KL_RLHF-C092/KL_reg_MDPs.pdf validates that the regret scale logarithmically with rounds $T$.\n\n---\n\n**Q2** Both algorithms include bonus terms, specifically a constant value of 1 found in equations (3) and (9). How does the constant affect the uncertainty associated with this bonus and the reward function? Additionally, is it possible to explore other potential bonus terms that could be utilized within these two algorithms?\n\n**A2**: Thanks for the questions. The central idea here is that we should use an optimistically biased objective to facilitate exploration of the underlying space, where adding an uncertainty bonus is one of the most common approach in the literature. The upper bound of the bonus may be very large compared to the range of the reward, so we usually truncate the bonus by $1$.\n\nFrom the theoretical perspective, which is also the main focus of our paper, such as bonus should ensure the estimator is an upper bound of the true parameter with high probability and is constructed mostly by the concentration inequality tool from the high-dimensional statistics, where the constants are determined accordingly to satisfy this goal. Meanwhile, any potential bonus that satisfies this condition is valid but we usually take the sharpest estimation for a better theoretical results.\n\nWhen we move to the practical side, we typically resort to heuristic approximation of the bonus and apply the theoretical insights in principle. For instance, a common way is to use the ensemble method to incorporate the uncertainty into empirical experiments [5]. There are also alternative ways that can be used as \"potential bonus\" like using a optimistically biased loss function [6, 7]. Nevertheless, the empirical results in these works consistently show that taking uncertainty into consideration can largely improve the real-world performance of the algorithms. \n\n[1] Xiong, W, et al. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. ICML, 2024.\n\n[2] Guo, S, et al. Direct Language Model Alignment from Online AI Feedback. 2024.\n\n[3] Dong, H, et al. RLHF Workflow: From Reward Modeling to Online RLHF. TMLR, 2024.\n\n[4] Jin, Y, et al. Is pessimism provably efficient for offline rl? ICML, 2021.\n\n[5] Coste, T, et al. Reward model ensembles help mitigate overoptimization. ICLR, 2024.\n\n[6] Xie, T, et al. Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF. 2024.\n\n[7] Liu, Z, et al. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adversarial regularizer. NIPS, 2024.", "claims_and_evidence": "The proposed algorithms, KL-regularized UCB and KL-regularized LSVI with UCB, are based on theoretical analyses and have yet to undergo empirical validation.", "methods_and_evaluation_criteria": "This work did not include any practical experiments for the evaluation of the algorithms.", "theoretical_claims": "The theoretical analysis outlined in the main paper seems to be well-structured and thorough at first glance.", "experimental_designs_or_analyses": "No related experimental designs or analyses.", "relation_to_broader_scientific_literature": "The authors provide two provably efficient algorithms: KL-regularized UCB and KL-regularized LSVI with UCB. Both algorithms theoretically achieve the logarithmic regret bound.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "1. The two proposed algorithms are said to achieve regret bounds that scale logarithmically with the number of rounds, T. To support these claims, empirical validations should be conducted in real-world Reinforcement Learning from Human Feedback (RLHF) experiments to provide valuable insights. It is curious whether any empirical validations related could be provided.\n2. Both algorithms include bonus terms, specifically a constant value of 1 found in equations (3) and (9). How does the constant affect the uncertainty associated with this bonus and the reward function? Additionally, is it possible to explore other potential bonus terms that could be utilized within these two algorithms?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DNkRd4w9OJ", "reviewer": "Reviewer_TRX2", "summary": "This paper considers the problem of online KL-regularized contextual bandits and MDPs and proposes two provably efficient algorithms with logarithmic regret bounds, improving over the typical $O(\\sqrt{T})$ regret bounds.\n\nThe key idea is a refined value/policy decomposition technique for the bandits/MDPs with KL-regularization.\n\n## update after rebuttal\n\nI maintain my positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer TRX2\n\nThank you for your strong support!\n\n**Q1** In page 4, it is stated that \"Without loss of generality, we assume that the function class has finite cardinality\" with a reference to a ~500 page book. How should the proof be modified to handle the infinite case? In order to make the claim that there is no loss in generality, I suggest adding an appendix section to at least state the exact regret bound in the infinite case and include a brief overview of how it could be obtained, with more detailed references.\n\n**A1** Thank you for your helpful suggestion! For the infinite case, we will assume that the function class has finite covering number. For each function $f\\in\\mathcal R$, there exists a cover function $f'$ belongs to the cover such that $f$ and $f'$ are close enough so that we can transform this problem into a finite class and take the uniform bound. Then, in the final regret bound, we just need to replace the class cardinality with the covering number. This analysis is standard in previous literature [1,2] and Chapter 4.6 of Zhang, 2023. We will provide the details in the revision.\n\n\n[1] Zhao H, et al. Sharp analysis for kl-regularized contextual bandits and rlhf.\n\n[2] Ye C, et al. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. ICML, 2023.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I didn't check all the details, but as far as I have checked, the proofs are correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The related works section is comprehensive and covers the relation to the broader literature.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "Strengths: \nI believe this is a strong result and the ideas used here may also be of independent interest for other works.\n\nWeakness:\nThere are no experiments to demonstrate the effectiveness of the proposed algorithms in practice.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "In page 4, it is stated that \"Without loss of generality, we assume that the function class has finite cardinality\" with a reference to a ~500 page book. How should the proof be modified to handle the infinite case?  \nIn order to make the claim that there is no loss in generality, I suggest adding an appendix section to at least state the exact regret bound in the infinite case and include a brief overview of how it could be obtained, with more detailed references.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8JCsx4G8ww", "reviewer": "Reviewer_yuSc", "summary": "Short summary: the authors propose a KL-regularized contextual bandit algorithm, and show it achieves logarithmic regret using a fine-grained analysis of the sub-optimality gap. They then extend this analysis to KL-regularized Reinforcement Learning by reducing to the bandit setting. The resulting KL-regularized least squares value iteration algorithm achieves a regret logarithmic in the number of rounds and polynomial in the horizon.\n\nMore detailed summary of bandit section: \n- The proposed algorithm consists of using a least-squares fit of received rewards, and using as a policy a Gibbs reweighting of the reference policy according to the reward approximation plus an exploration bonus (i.e. $\\pi(a|x) \\propto \\pi_{ref}(a|x) e^{\\eta(\\hat{R}(x,a) + b(x,a)}$).\n- The exploration bonus is a monotonic function of reward uncertainty (Def. 3.3).\n- Contrary to prior works, which apply a classical suboptimality gap decomposition in the KL-regularized setting, the authors propose a fine-grained analysis of the KL-regularized suboptimality gap. This analysis directly considers the normalization term for the policy ($Z_R(x) = \\sum_a \\pi_{ref}(a|x) e^{\\eta R(x, a)}$).\n- They can then bound the regret by the sum of squared bonuses, from which they claim their regret bound follows\n\nMore detailed summary of RL section:\n- The proposed bandit algorithm is modified by replacing the least-squares fit of the reward by least-squares value iteration (i.e. learning a Q-function estimator $\\hat{f}$ to minimize the square Bellman backward error $|| \\hat{f}(s, a) - r_h - \\hat{V}^{\\hat{f}}(s)||^2$), still using an exploration bonus.\n- To reduce to the bandit setting, the authors consider couplings of the learned policy $\\hat{\\pi}$ and the optimal policy $\\pi^*$. A coupled policy $\\hat{\\pi}^{(h)}$ acts according to $\\hat{\\pi}$ until episode timestep $h$, and subsequently according to $\\pi^*$.\n- Since $\\hat{\\pi}^{(0)} = \\pi^*$ and $\\hat{\\pi}^{(H)} = \\hat{\\pi}$ (where $H$ is the episode horizon), the suboptimality gap can be decomposed as a telescoping sum of $\\mathbb{E}[V^{\\hat{\\pi}^{(h)}}(s) - V^{\\hat{\\pi}^{(h+1)}}(s)]$.\n- Since each term in the telescoping sum depends only on one timestep of the environment, the analysis from the bandit case (i.e. $H=1$) applies. This yields a bound of the suboptimality gap by $H^2$ times the sum of squared approximate Bellman errors (i.e. according to the algorithm’s estimates $\\hat{f}, \\hat{Q}, \\hat{V}$). \n- Since the proposed algorithm minimizes squared approximate Bellman errors, standard function approximation generalization bounds imply the regret is logarithmic in the number of episodes.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer yuSc\n\nThank you very much for your strong support!\n\n**Q1** It would have been interesting to see computational resource considerations in the analysis of KL-LSVI. For example, in RLHF applications, reward models can be large-scale neural networks. In this case, optimizing a reward model at every episode could be very costly.\n\n**A1** Our work focuses on providing a general and standard online framework enjoying logarithmic regret bounds. The computational efficiency is indeed very important for larges-scale models. Hence, to improve efficiency in RLHF applications, it has been shown that low switching techniques [1,2,3] can solve this problem both emprirically and theoretically. Following the batch framework in [1], we can obtain the same sample complexity with $\\Theta(d_{\\mathcal R})$ number of batches.\n\n---\n\n**Q2** It would be interesting to see generalizations of KL-LSVI to the setting where \n is a neural network, e.g. optimized via gradient descent during training. I would imagine Line 5 might be replaced e.g. by a stochastic gradient update. I wonder if there are any standard techniques that could be used to generalize this paper’s analysis to such an online SGD setting.\n \n**A2** In practice, a promising direction is Thompson Sampling (TS)-based exploration, which can be implemented using Stochastic Gradient Langevin Dynamics (SGLD) to introduce randomness into SGD for regression. SGLD enables implicit posterior sampling during training, potentially improving the balance between exploration and exploitation in the KL-regularized setting.\n\nTo extend the current theoretical analysis of KL-LSVI, one could explore whether existing regret bounds for Langevin-based exploration methods apply in this context. Notably, [4] shows that TS with a \"feel-good\" term achieves an optimal sample complexity bound comparable to UCB in contextual bandits with function approximation. Furthermore, [5] provides a comprehensive empirical study demonstrating the efficiency of TS in RL and the effectiveness of SGLD in approximating TS. We believe investigating sampling-based methods for KL-regularized objectives in RL is an interesting direction for future work.\n\n---\n\n**Q3** I believe it would have been helpful if, when referencing “standard techniques” (e.g. lines 368-369), the authors would have provided specific citations or references to pin down which techniques exactly they have in mind.\n\n**A3** Thanks for the helpful suggestion! We will explain the standard techniques detailedly in the revision.\n\n \n[1] Xiong W, et al. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. ICML, 2023.\n\n[2] Bai, Y., et al. Training a helpful and harmless assistant with reinforcement learning from human feedback.\n\n[3] Touvron, H., et al. Llama 2: Open foundation and fine-tuned chat models.\n\n[4] Zhang, T. Feel-good thompson sampling for contextual bandits and reinforcement learning. \n\n[5] Ishfaq, H., et al. Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo", "claims_and_evidence": "The authors give a clear and comprehensible explanation of their proposed algorithms and proofs. I believe it would have been helpful if, when referencing “standard techniques” (e.g. lines 368-369), the authors would have provided specific citations or references to pin down which techniques exactly they have in mind. But, besides this, I found the core technical claims to be well explained and justified.", "methods_and_evaluation_criteria": "This is a theory paper proving a regret bound, and so experimental evaluations are not of major relevance in this case.", "theoretical_claims": "I reviewed the elements of the proof presented in the main paper, but did not go into the ones in the supplementary materials in detail.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Given that the prior state-of-the-art regret bound for KL-regularized RL was $O(\\sqrt{T})$, and that the authors prove a logarithmic bound, the result seems to be of major theoretical significance. In addition, as highlighted in Table 1, the author’s proposed algorithm achieves $O(1/\\epsilon)$ sample complexity, while prior art achieves only $O(1/\\epsilon^2)$.\n\nFurther, the “policy decomposition” technique used in line 422 to reduce the RL setting to the bandit setting seems fairly general, and might be applicable in other analyses of regret in MDPs.", "essential_references_not_discussed": "I am not aware of missing essential references, but will revisit this during the discussion period in case any are pointed out by other reviewers.", "other_strengths_and_weaknesses": "Other strengths:\n- Clarity: the proof outline in the main paper clearly conveys the main techniques introduced, and is comprehensible to non-experts in relevant preceding works.\n\nOther weaknesses (or, rather, interesting further directions I would have been interested in seeing in this paper, but can each perfectly well be left for future work):\n- It would have been interesting to see computational resource considerations in the analysis of KL-LSVI. For example, in RLHF applications, reward models can be large-scale neural networks. In this case, optimizing a reward model at every episode could be very costly. \n- In the same direction as the above, it would be interesting to see generalizations of KL-LSVI to the setting where $\\hat{f}$ is a neural network, e.g. optimized via gradient descent during training. I would imagine Line 5 might be replaced e.g. by a  stochastic gradient update. I wonder if there are any standard techniques that could be used to generalize this paper’s analysis to such an online SGD setting.", "other_comments_or_suggestions": "- There is a large whitespace in Line 231, second column. It might be best to not leave the corresponding equation as an inline expression.\n- It would be helpful if the authors could also reference the rationale behind the inequality in Line 365.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HxXFuZKHbv", "reviewer": "Reviewer_cCx6", "summary": "This paper studied online RL with KL regularization, and proposed an optimism-based algorithm for contextual bandits and RL. The paper showed that the regret scales logarithmic with the number of iterations, demonstrating the superiority of KL regularization used in RL. Particularly, the paper developed a new technique in the analysis of the regret, where it performs a refined analysis of the normalization term used in policy updating, and helps to show a reduced regret.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer cCx6\n \nThank you for your strong support!\n\n**Q1** In the claim of achieving logarithm regret (e.g. remark 4.2), it is better to explain it is because the optimal policy is the one that maximizes the KL-regularized objective, rather than standard objective (cumulative return)\n\n**A1** Thanks for reminding this point! We will add this to the revision and state that now our objective is the reward subtracted by the KL-regualrization and is different from the original RL objective. We focus on this objective because as stated in Lines 21-34 right, for post-training in large-sacle models, the trained policy should not move too far from the strong base policy. Otherwise, the \"sloignment tax\" arises.\n\n---\n\n**Q2** Lack some (at least) simple experiments to demonstrate the proposed algorithm and validate the results.\n\n**A2** Since large scale experiments are beyond the scope of this theoretical work, we run simulations for our algorithm under a multi-armed linear contextual bandit. We use different values of KL-regularization parameter $\\eta$ and arm number $K$. The results are provided at this anonymous link https://anonymous.4open.science/r/Simulation_KL_RLHF-C092/KL_reg_MDPs.pdf. Since the x-axis has logarithmic scale, the almost linear curve in the figures validates that the regret scales logarithmically with rounds $T$.", "claims_and_evidence": "Yes. The paper provided detailed theoretical analysis to support their claims and theorems.", "methods_and_evaluation_criteria": "Yes. This is a theoretical paper and theoretical analysis is provided.", "theoretical_claims": "I briefly checked the proofs, particularly the analysis of the normalization term, and they seem correct to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: the logarithm regret result seems promising and interesting. the technique for analyzing the normalization term is novel.\n\nWeakness: Lack some (at least) simple experiments to demonstrate the proposed algorithm and validate the results.", "other_comments_or_suggestions": "In the claim of achieving logarithm regret (e.g. remark 4.2), it is better to explain it is because the optimal policy is the one that maximizes the KL-regularized objective, rather than standard objective (cumulative return). Since the lower bound of standard online RL is $\\Omega(\\sqrt{T})$. This could help to improve the clarity.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers online learning using a KL-regularized objective in the settings of contextual bandits and reinforcement learning. It establishes, for the first time, regret bounds that scale logarithmically with the number of time steps $T$. Previous bounds scaled with $\sqrt{T}$ and relied on strong coverage assumptions.

All five reviewers agreed that this is a good paper with novel contributions and recommended acceptance. While some expressed concerns about the lack of experimental evaluation, I believe the theoretical contribution is strong and significant in its own right. Moreover, the decomposition introduced in one of the sections may be of independent interest. Based on this, I recommend acceptance.

The authors should address the following points in the revised version, in order of priority:

- To avoid confusion, consider resolving the algorithm naming conflict: the same name KL-UCB was already used in [1].
- Explicitly clarify the conditions required on the growth of the eluder dimension for the regret bounds to hold.  
- Include the brief discussion on how to remove the additional dependence on the horizon $H$, which is currently left for future work but outlined in the rebuttal.  
- Provide detailed information about the simple experiment that was shared during the author-reviewer discussion.

[1] *The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond*, A. Garivier and O. Cappé, ALT 2011.
Decision: Accept (poster)