Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits
Authors: Qingyue Zhao
Kaixuan Ji
Heyang Zhao
Tong Zhang
Quanquan Gu
Venue: ICLR 2026 Poster (2026)
Keywords: contextual bandits
policy optimization
$f$-divergence
regularization
Primary area: learning theory
TL;DR: We show the first near-optimal sample complexity for offline policy optimization with respect to two important classes of  $f$-divergence-regularized objectives with provably weakest data coverage requirements.

Abstract: Many offline reinforcement learning algorithms are underpinned by $f$-divergence regularization, but their sample complexity *defined with respect to regularized objectives* still lacks tight analyses, especially in terms of concrete data coverage conditions. 
In this paper, we study the exact concentrability requirements to achieve the $\tilde{\Theta}(\epsilon^{-1})$ sample complexity for offline $f$-divergence-regularized contextual bandits. For reverse Kullback–Leibler (KL) divergence, arguably the most commonly used one, we achieve an $\tilde{O}(\epsilon^{-1})$ sample complexity under single-policy concentrability for the first time via a novel pessimism-based analysis, surpassing existing $\tilde{O}(\epsilon^{-1})$ bound under all-policy concentrability and $\tilde{O}(\epsilon^{-2})$ bound under single-policy concentrability. We also propose a near-matching lower bound, demonstrating that a multiplicative dependency on single-policy concentrability is necessary to maximally exploit the curvature property of reverse KL. 
Moreover, for $f$-divergences with strongly convex $f$, to which reverse KL *does not* belong, we show that the sharp sample complexity $\tilde{\Theta}(\epsilon^{-1})$ is achievable even without pessimistic estimation or single-policy concentrability.
We further corroborate our theoretical insights with numerical experiments and extend our analysis to contextual dueling bandits. We believe these results take a significant step towards a comprehensive understanding of objectives with $f$-divergence regularization.

Published as a conference paper at ICLR 2026
TOWARDS A SHARP ANALYSIS OF OFFLINE POLICY LEARNING FOR J-DIVERGENCE-REGULAAIZDD CON- TEXTUAL BANDITS
Qingyue Zhao">, Kaixuan Ji Heyang Zhao'r, Tong Zhang', Quanquan Gu
University of California, Los Angeles
University of Illinois Urbana-Champaige (kaixuanji, z4 hyzhao &cc ucla. edu tozhange: liniiis.i..i....iimiiiiiimiiii.i edu, qguêcs ucla.edu
ABSTRACT
Many offline reinforcement learning algorithms underpinned by f-divergence regularization, but their sample complexity defined with respect to regularized objectives still lacks tight analyses, especially in terms of concrete data cover- age conditions. In this paper, we study the exact concentrability requirements to achieve the ((c-)) sample complexity for offline /-divergenne-regulliiiee con- textual bandits. For reverse Kullback -Libller (KL) divergence, arguably the most commonly used one, we achieve an Ö(c-l) sample complexity under single- policy concentrability for the first time via novel pessimism-based analysis, surpassing existing Ō(E-1) bound under all-policy concentrability and Ö(E 2) bound under single-policy concentrability. also propose a near-matcho wear-matching lower bound, demonstrating that a multiplicative dependency on single-policy concen- trability is necessary to maximally exploit the curvature property of reverse KL. Moreover, for f-divergences with strongly convex f. to which reverse KL does not belong, we show that the sharp sample complexity θ(e-1) ) achievable even without pessimistic estimation single-policy concentrability. We further cor- roborate our theoretical insights with numerical experiments and extend our anal- ysis to contextual dueling bandits. We believe these results take a significant step towards comprehensive understanding of objectives with f-divergence regular- ization.
INTRODUCTION
Due to the data-hungry and instable nature of reinforcement learning (RL), divergences that are straightforward to estimate via Monte Carlo or amenable to constrained optimization stand out from numerous candidates (Rényi 1961 Csiszár 1967; Müller 1997: Basseville] 2013) as regularizers;
expectation, for which empirical average is a good proxy (Levine 2018 Levine et al. 2020); and the latter class subsumes those with nice positive curvatures (e.g., Bregman divergence (Bregman) 1967) induced by strongly convex functions). In particular, Kullback-Leibler (KI.) divergence is the only one at the intersection of f-divergence and Bregman divergence (Jiao al., [2014] Theorem 5), indicating its theoretical advantage among common choices from both computational and statistical aspects. Also, the KL-regularized RL objective is arguably the most popular one in practice:
the former family is typically f-divergence (Rényi 1961 because any of them
((T) = Ex [r] - 17 KKL (ef).
(1.1)
where is the reward, re is reference policy, (L(T|l the reverse KL divergence, and the inverse temperature. When ाe is uniform, 1.1 reduces to the entropy- regooop--rullrizeedd objec- tive that encourages diverse actions and enhances robustness (Williams) 1992 Ziebart et al. 2008
Levine & Koltun 2013] Levine et al.) 2016), Haarnoja et af.) 2018 Richemond et al. 2024 Liu et al. 2024). KL regularization has also been widely used in the RL fine-tuning of large language models
"Equal Contribution

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of sample complexity bounds for finding e-optimal policy for offline contextual bandits with KL- and (strongly convex) f f-divergence regularization. Constants and polylog factors are omitted here except the metric entropy log N. "Reverse KLL" stands for KL-regularized contex- tual bandits and "f-divergence w/ s.c., f for the counterpart with a-strongly convex f. The two existing upper bounds are adapted from the implicit form in Xiong et al. (2024) Theorem 3.1) and Zhao et al. (2024) Theorem 3.3 and Theorem 4.4), of which the detailed adaptions are deferred to Appendix A
The relationship between D2 and C**
is detailed in Section
2.1
Regularizer
Xiong et al. (2024)
Zhao et al. 2024
This work
Upper
de-2
n log.V n/c log
n - log N
Reverse KI.
Lower
n c- log N
f-divergence w/ s.c. f
Upper
a nc log N ne log.N
Lower
Ouyang et al. 2022 Rafailov et al.
2023), where n- is the base model. Given its widespread
use, there has been surge of interest in understanding the role of KL regularization in RL by both empirical studies (Ahmed et al.] 2019; Liu et al., (0199 and theoretical analysis (Geist et al.) [019]] Kozuno et 2022). There are also lines of research on KL. regularization in online learning (Cai et al. 2020 He et al., 2022; jJ et al., (023) and convex optimization (Neu et al.) 2017]. However, most of these works still study the unregularized reward maximization objective, against which the sample complexity is at least S((E 2)
Vieillard et aT., |
Several recent papers (Xiong et al. 2024, Xie et al. 2024; Zhao et al. 2024 Foster et al. 2025
Aminian et al. 2025) switched the focus analyzing the sub-optimality defined via the regularizer objective [1.]p. under which an (2 sample complexity is possible (Zhao et al. 2024 Theo- rem 3.6). However, even restricted to the pure i..d. setting, existing analyses in this vein either result in still Ō(E-2) bounds (Xiong al. 2024; Xie et al. 2024 has stringent (local) all-policy concentrability dependencies in their upper bounds (Zhao et al. 2024 Aminian et al. 22225] Thus, there are by far no tight bounds in terms of both the dependency of and data coverage conditions for KL-regularized offline decision making. In addition, all analyses above set KL as the right target by default; but reverse KL is the f-divergence with (xx) = x log x, which merely convex. There- fore, it is also unknown whether /-divergence regularizers with even nicer (e.g.. strongly convex) f. whose performance against the reward maximization objective are provably promising (Zhan et al.) 2022 Gabbianelli et al. 2024:] Huang al.) (225b)), can enjoy better coverage dependency in their sample complexity when the corresponding regularized objectives serve as the performance metric. Because data coverage (i.e., concentrability) conditions captures the crucial distributional shift issue in offline RL (eeinne et al. 2020), the aforementioned perspectives motivate a pivotal open problem:
What is the weakest coverage condition required for offline learning to be near-optimal with respect to dedivergence-egullriaze objectives?
We attack this problem by showing near-optimal sample complexity with matching concentrability dependencies for two representative subclasses of f f-divergence. First, for contextual bandits with KL regularization, we achieve a near-optimal sample complexity guarantee with linear dependence on single-policy coverage ratio. Our novel lower bound further indicates that this multiplicative dependency on single-policy concentrability is necessary. Surprisingly, for f-divergence with a- strongly-convex f. we prove nearly matching sample complexity bounds of @(a-1 ing the dependence on coverage for the first time. For the ease of comparison, we adapt existing counterparts under our notation to the offline setting and summarize them in Table [
eliminat-
1.1 CONTRIBUTIONS
For KL regularization, we propose pessimism-based algorithm achieving the tight sample com- plexity under single-policy concentrability. We also obtain lower bound that linearly scale with the density-ratio-basee single-policy concentrability. Both results strictly improves upon previous
SSee Appendix A.1 for detailed reasons.
"See Section 2. for details on coverage conditions.
2

---

Published as a conference paper at ICLR 2026
works (Zhao et al. 2024 Foster al. 2025 in the offline setting, showing that single-policy concentrability is both sufficient and necessary achieve the @(c-t) sample complexity.
Technically speaking, our analysis exploits the strong convexity of KL and pessimism of the re- ward estimator, to refine a mean-value-type risk upper bound (Lemma 2.14 to its, which in turn leads to a novel moment-based analysis, effectively bypassing the need for uniform control over the discrepancy between any two functions in the function class. To the best of our knowledge, this machinery has not been used in the standard analysis of existing offline RL algorithms and may be of independent interest.
objectives with strongly convex S. we design truly lightweight algorithm free of pessimism- basedd gadgets and still obtain the @(c=1) sample complexity certified by a matching lower bound without coverage conditions.
For /-divergence--eggulaiiizz
We verify the statistical rates above numerical experiments, and demonstrate the versatility of all algorithmic and constructive proof ideas above by extending them to F-divergence-regullaiieg contextual dueling bandits (CDBs), achieving similar O(e sample complexity bounds. More- over, all algorithms are applicable for reward function classes with small metric entropy.
1.2 KEY RELATED WORK
We review two key lines of theoretical progress that are relevant to our algorithm design and analysis. Pessimism in offiine RL. The principle of pessimism has been underpinning offline RL for both the tabular (Rashidinejad et al., (02T) and function approximation (Tin et al.) 2021) settings under the name of lower confidence bound (LCB). For contextual bandits, it is behind the adaptively optimal sample complexity analysis (Li et al. 2022). Shi et al. (2022) proposed a LCB-based model-free algorithm for tabular RL with oettmol guarantee. Uin et al. (2021): Xiong et al. (2022) Di al. (2024) utilized LCB in conjunction with the classic least-square value iteration paradigm to derive O sample complexity results for model-free RL with function approximation. The line of work from Rashidinejad al. (202I); : Xie al. (2021b) Li al. (2024) settled the sample complexity of tabular model-based RL via pessimistic estimators exploiting the variance information. It is also possible to leverage the idea of pessimism to design model-based algorithms under general function approximation that are at least statistically efficient (Xie et al., 202 (eeaaa & Sun [202] Wang et al. 2024). The principle of pessimism has also been applied counterfactual empirical risk minimization (Swaminathan & Joachims 2015 London & Sandler (019) and offline policy learning (Sakhi et al.] 2023; 2024). which are orthogonal to our contributions.
However, in terms of risk decomposition, to the best of our knowledge, none of these pessimism- based analyses really goes beyond the performance difference lemma (Foster & Rakhlin 2023 Lemma 13) simulation lemma (Foster & Rakhlin, 2023 Lemma 23); both of which are not able to capture the strong concavity of KL-regularized objectives even in the bandit setting. The
algorithmic idea of using pessimistic least-square estimators under general function approximation in Jnjin et al. (2021): ): Di et al. (2024) is similar to ours, but their sub-optimality gap is bounded by the sum of bonuses, which cannot directly lead to the desired sample complexity of our objective.
Offinee CDBs. CDBs (Dudik et al. 2015) is the contextual extension of dueling bandits in the classic
literature of online learning from pairwise comparisons (Yue al. 2012 Zoghi et al.] 2014). Since the empirical breakthrough of preference-
RL fine-tuning of LLMs Ouuyan et al.) 2022). the
theory of offline CDBs has received more attention under linear function approximation (Zhu al.
2023 Xiong et al. (2024) and general function approximation (Zhan et al. 2022; Zhao et al. 2024 Song et al. 2024] Huang et al. 20255). Preference models without stochastic transitivity (Munos et al. 2023 Ye et al. 2024 Wu et al. 20244] ZZhng et al. (2024) are beyond the scope of this work, namely, our preference labels are assumed to follow the Bradley-Terry Model (Bradley & Terry) 1952).
The sets S and A are assumed to be countable throughout the paper. For nonnegative sequences } and {yn]. we write In = O(y,)) if lim sup,-toc /n/ yn < co, Yn = 2(xx))
Notation.
In = O(y,), and yn = (zx,) ) if In = O(y,) and Hn = M(y.). We further employ ((-). and θ to hide polylog factors. For countable X' and V, denote the family of probability kernels from X to y by A()(x). For g X' + R, its infinity norm is denoted by || = supzex [=
For pair of probability measures P E Q the same space and function f R2 - R, their
3

---

Published as a conference paper at ICLR 2026
f f-divergence is Dy PorePlllo = ( ((PP dQ) dQ. Specifically, when f(z) x log olgg.. z, 1-divergence becomes KI. divergence denoted as KL (P = f log( dP/ /Q) dP, and when f(x) = 1 11/2,
it becomes the total variation
(TV) distance, which is denoted as (PII)) - 0.5 f f - dQ)- We use supp(P) ()) to denote the support set of P.
COTTEXTUAL BANDITS
KL-REGULARIZEH STL-EGUULRRIAA CONTEXTUAL
2
In this section, we introduce pessimism-based algorithm, PCB-KL, for offline KL CL-reguuln contextual bandits. We then showcase our novel analysis techniques for PCB-KL, which couples the algorithmic pessimism with the curvature property of KL-regularized objectives.
2.1 PROBLEM SETUP
We consider contextual bandit, which is denoted by a tuple (S,A, r, x "d Specifically, S is the context space, A is the action space and r : S x A -> [0. 1] is the reward function. In the offline setting, the agent only has access to an i.i.d. dataset D = {(s,, (4; r:)] Here s/s are states sampled from p E (SS), a, E A is the action taken from behavior policy, and r is the observed reward given by F; = r(s;, a. + Ss, where E, is L-sub-Gaussian (Lattimore & Szepesvári 2020 , W
Definition 5.2). In this work, we consider the KL-regularized objective
(x) = Bi ((..))xp ((s,,)= - 17 1--
-1-lo log
T(ass)
(2.1)
n (a|s)
where :e is known reference policy and the "inverse temperature" 17 controls the intensity of reg- ularization. For simplicity, we assume that ne is also the behavior policy that generates the dataset D, which is similar to the type of "behavior regularization" studied in /han et al. (2022). The unique optimal policy m. == -
(E J (T) is given by (See, e.g.. Zhang 2023 Proposition 7
x (-1s) of (+1s) exp
(1 (o-r((s))) 1), Vs ES
(2.2)
A policy ı is said to be c-optimal if SubOptRKI (T) = J(TT J(x) S and the goal of the agent is to find one such policy using D. Note that SubOptRKI. (.) is defined through (2.1) and thus depends on 17. To ensure that c-optimality is achievable, we assume that lies in known function d
class class& G C (S A + [o, 1)), from which the agent obtains an estimator F. More specifically, we work with general function approximation under realizability, which is as follows.
Assumption 2.1. For this known function class g c (S A + [0, 1). 3g* G with g" =T.
We also employ the standard notion of covering number (Wainwright 2019 Definition 5.1) as the complexity measure of the reward function class G.
Definition 2.2 (c-net and covering number). Given a function class G c (S x A +
IR), a finite set G(c) C is c-net of G w.r.t. || lloo. if for any g E G, there exists g' E g(() such that lgg - l' 10 S e. The e-covering number is the smallest cardinality Ng(e)) of such G(e).
A Assumption 2.3. For any c, > 0, the -oooerinng number (umberN(((e)) of G is p))y(=.
Assumpee 2.3 allowing log.N (c) to be roughly negligible is arguably mild. For example, when is the class of linear functions of dimension d and radius R. the covering number is Ng((e)
O((1+ + Re 11y) (Jin et al. 2020 Lemma D.6), which satisfies A 2.3
yd)
Concentrability. birettraabblty.. The data quality of D collected by - is typically characterized by concentrabil- ity in offline RI. (Farahmand et al. 2010 Chen & Jiang 2019 Jiang & Xiel (024), which quantifies the ability of the behavioral policy to generate diverse actions. We first define the density- matsstt-raaio-baseee concentrabiliy abilitzaabilii as follows.
rDeissty-ratio-baseed concentrability), For policy class II, refer- poorabliii C. is O
Definition 2.4 ence policy re the density-ration rettitty-rtioo-basee batio- all pollco concentrabiltty sup suPrEn..ES..C. re (als), whose single-policy poliee comterpant under the optimal policy T" is CT C == S.REESEAA (((d))))
=
(als). (als)) (
'We suppress J, into J and n. into =" when they are clear in context in the following presentation.
4

---

Published as a conference paper at ICLR 2026
In the definition above, small all-policy concentrability intuitively corresponds to supp(r""f) cover- ing all possible inputs. On the other hand, small single-policy concentrability means that supp(=""*) only subsumes supp( ). In this paper, in addition density-ratio-busee concentrability, also adopt the following Dd-based concentrabilites to better capturing the nature of function class G. In detail, we start with the Di-divergence follows.
Definition 2.5. Given a function class g C (S x x divergence D2 ((s, a); as
and a fixed policy т, define the D R)
(g(s, a) - h(s. a))
sup A (s (/xpx d') h a'))²]
The "eluder timension"-ryin Definition 2.5 is directly inspired by Di et al. (2024); Zhao et al. 2024), the intuition behind which is that given (s,a) E S x A, a small Di-divergence indicates that for two functions 9 and h, if they are close under the behavior policy я, then they will also be close such pair a). Therefore, the DD-divergence quantifies how well the estimation dataset collected by the behavior policy π can be generalized to a specific state-action pair.
Remark 2.6. For the tabular setting, direct computation yields (s,,, which can be estimated by the visitation frequency empirically. Under linear function approxima- tion, it is well known that (s, a) [| ()]s,,)]] [) under mild conditions of the parameter space, where == E ((,, ())(s, a) is the covariance matrix, which can be estimated by empirical covariance matrices in practice, potentially with ridge regularization. For more general function classes like neural networks, the D can also be efficiently approximated by heuristics as discussed in Xiong et al. (2024): Gupta et al. 2024); Xu et al. (2025).
(als)=
We are now ready to define the two notions concentrability conditions. Assumption 2.7 (All-policy concentrability). Given reference policy -t,, there exists D < do such that D SU (C, a); r
Assumption 2.7 indicates that the errors on any state-action pairs can be bounded by the error on the samples from π up to a factor D, whose relaxed counterpart under the same zfe is as follows.
Assumption 2.8 (Single-policy concentrability). D = [(, Dg((s, a): zef) < c0.
Assumption 2.8 indicates that the errors on the distributions of state-action pairs p X x² can be bounded by the error on the samples from p X re up to some constant. For both types, the single- policy concentrability assumption is strictly weaker than the all-policy concentrability assumption. However, in general, the two quantities characterizing single-policy concentrability C and D2 cannot be bounded by each other up to constant factors. In particular, we have D S |S||A|C** indicating that C** subsumes D when |S| and |A| can be seen as constants. We refer the reader to Appendix B for further discussion on the relation between C*" and D2..
2.2 ALGORITHM
In this subsection, we present offline bandit algorithm, KL-PCB, for KL-regularized contextual bandits in Algorithm [ KL-PPB first leverages least-square estimator to find a function I E G that minimizes its risk on the offline dataset. In Zhao et al.] (2024), such ğ is directly applied to construct the estimated policy. In contrast, we construct a pessimistic estimator of g" following the well-known pessimism principle in offline RL (Jin al. 202T). Specifically, we define the bonus
/ /128 log (2Ng(e)/0)/33 We then obtain our pessimistic estimation ğ by setting ğ ğ - In. which is less than g" with high probability. Formally, let the event {() given > 0 defined as
term I n through the confidence radius
18e as
(s, a) 3Dg ((s, a), Tt V(s,a) E S A.
(2.3)
{()) == sup (u [|o 96و r (s,a) s z0)
(2.4)
on which the least square estimation I obtained in Line of Algorithm does not deviate too much from the true function g and therefore 9 is a pessimistic estimation of g" We have the following lemma indicating that this event holds with high probability.
5

---

Published as a conference paper at ICLR 2026
Algorithm Offline KL-Regularized Pessimistic Contextual Bandits (KL-PCB)
Require: regularization 7, reference policy -e" offfine dataset D, function class G
1: Least square estimation of reward function E argmin gEg E(s,,, (g(8;, a;) rz)
2: Let 9 f- I. where In is the bonus term in (2.3
Ensure: {() x x (a|s) exp (1 ((s,a)
Lemma 2.9. For all 5 > 0, E()) holds with probability at least 1 6. 8.
After obtaining the pessimistic estimation, KL-PCB output the policy म, which maximizes the esti- mated objective
((s,a) -17 -n- log {(ass) x (als)
J(T) (x.a))=xx
the maximizer of which is the counterpart of [2.2 i.e.,
i(als)
ref (als) exp (n g(s,a))
2.3 THEORETICAL RESULTS
The sample complexity for KL-regularized contextual bandits is settled in this subsection. We first give the upper bound of KL-PCB.
Theorem 2.10. Under Assumption
2.8 for sufficiently small (0, 1), if we set r, in 2.3
then n = Ö(nD2. Log.N((e) suffices to guarantee the output policy स of Algorithm to be e-optimal with probability at least - 6.
Previously, Zhao al. 2024 achieved Ö(c-!) sample complexity under Assumption 2.7 As
comparison, KL-PCB achieves the same Ō sample complexity but only requiring Assump- tion 2.8 which is weaker than Assumption 2.7 We also provide the sample complexity lower bound of regguullrrze contextual bandits in the following theorem, which, together with Theorem 10 demonstrates that single-policy concentrability is both necessary and sufficient for near-optimal of- fline learning evaluated by KL-regularized objectives.
Theorem 2.11. For VS 2 1, 7 > log C* E (2, exp(//444 and any algorithm Alg. there is a KL-regularized contextual bandit with C < C such that Alg requires O minn -1 "² log (o)))( samples to find an e-optimal policy for sufficiently small
Previously, Zhao et al. 22024) provided sample complexity lower bound [(1)) log (e)))/e) under KL regularization. Foster al. (2025) also provided lower bound of 12(C=") for KL-regularized objective to show the necessity of coverage. Compared to their results, our result shows that the multiplicative dependency on C is necessary for the first time.
Remark 2.12. Theorem 2.11 shows that when is sufficiently small, any algorithm for offline KL-regularized contextual bandits requires at least Q(nC* )e- log logNN((c) samples to output an c-optimal policy. The presence of exp(poly (7)) in the range of C* is inevitable, since we always have C** I <ex((n) in reverse KI. regularized bandits with bounded rewards.
Remark 2.13. As discussed before, we might have some easy instances with D2 S C=,, where KL-PCB outperforms the lower bound. This does not volates Theorem 2.11 since Theo- rem 2.11 only guarantees that there exist some hard instances that all algorithms require at least Ω ((min CC* log Ng((cc)) samples.
2.4 PROOF OVERVIEW OF THEOREM 2.10
In this section, we summarize the novel techniques in the proof of Theorem 2.10 which is de- ferred Appendix D.4 At high level, we consider the regularized objective (1.1) multi-arm
bandits, then P + KL (P(()) is 1-strongly convex w.r.t. TV (-ll)) (Polyanskiy & Wu 2025 Exer- cise I.37), and thus J(x)) is strongly concave. Therefore, J(x²) (T7) is possible to be of the order [TV [2] x Ö( pretending that n is the unconstrained maximizer. In detail, we follow the regret decomposition in Zhao et al. 2004)) which is encompassed by the following lemma.

---

Published as a conference paper at ICLR 2026
Lemma 2.14. Let g S A + R be any reward function, then there exist some y [0, 1] such that the sub-optimality gap of Tg (-1s) nTe (x1s)exp (19(s,)) can be bounded as
J( (Ta) (x.)))x) [9 (s)"
where 9, == 19 (1 7)'** and (+1s) nd (:|s) exp (ng,(s..))
In Zhao et al. (2024), because the g Lemma 2.14 is substituted with only the least-square estimator
9 with no extra structures, the reliance on the "middpoii policy ny can only be controlled all poolcyy
á of g" in Algorithm and thus the concentrability. However, our is the pessimistic estimator g
presence of my can be eliminated for free: let G(7) = Bpx=., (ō g') a)
(s.
and (s, =
( -ー-9" (8, < O, then direct computation (detailed in the proof of Lemma D.3) yields
G7(7) = n, Er, (A) a)] - E [s, a) Br,, [ a)]
- 0.
(2.5)
This gives J(x²) (( S pxx= (s a)] which can be bounded with single-policy
concentrability while still achieves the sharp dependency c-1 on Here, 2.5) holds due moment-based machinery in Lemma 2.15
Lemma 2.15. I( 2 0) and 3 < oc, then [[X3] E [[ < 0.
The intuition behind Lemma is natural: X and X cannot be positively correlated. Moreover, to the best of our knowledge, we are the first unveil this moment- structure our standaad aessimism-based analysis, from which the sharp upper bound follows. While pessimism is widely adopted to derive near-optimal statistical rates under single-policy concentrability in offline RI. with reward maximization as the goal (See, c.g.. Jin et al.] (2021): Xiong et al. (2022)) the standard pessimism-bas based pipeline is not sharp enough for bounding the SubOpt (x) defined through regularized objectives, the reason of which is detailed in the last paragraph of Appendix A.1
-DIVEEGENNE--RGGULANN
CONTEXTUAL BANDITS
As discussed in Section 2 the fast rate implied by Theorems 2.10 and 2.11 is primarily achieved due the strong convexity of + (L(T][>'"*) However, KL just an instance of f-divergence with f(x) = log which is only locally strongly convex but not strongly convex. Motivated by this observation, we further examine f-divergence regularization with strongly convex ʃ. which may introduce more favorable curvature in the performance metric of offline learning in principle.
3.1 PROBLEM SETUP
We study a contextual bandit setting similar to that in Section 2.1 In this section, we consider the following f-divergence regularized objective
Jn L.Dy(1)) (T) -E (r(8, a]] - 'E
(3.1)
where y is the regularization intensity and (y(p)) Eang (p((a)/((a)) is the f-divergence. Let the optimal policy be Tr,,,, == argmax,EE(AIs) Jn and we re-denine the learning objec- tive as searching for a policy π with SubOpt (a00pptaa((a)) (T) = J(mT) ((T) < We consider those functions : (0, +o0) + R with nice positive curvature condition in Assumption 3.1
Assumption 3.1. f is a-strongly convex, twice continuously differentiable, and f(1) = 0.
Many elementary functions like quadratic polynomials naturally satisfy Assumption 3.1 For in- stance, the I-strongly convex (x:) (xr 1)2/2 induces D = (PIQ). which is the x²_ divergence recently considered in RL literature (see e.g., Zhan et al. 2022); Huang et al. (2025b); Amortila et al. (2024)). This regularization exhibits promising theoretical potential for relaxing the data coverage requirement for efficient offline policy learning (Huang et al. (025b) and to be ef- fective in preventing reward hacking (Laidlaw et al.) 2025) against unregularized objectives. These favorable benefits are primary due to the observation that strongly convex f's impose a stronger penalization actions out of the coverage of ref
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 Offline f-divergence Regularized Contextual Bandits (f-CB)
Require:
regularization 7/, reference policy nee,, function class g, offline dataset D 1: Least square estimation 9 E argmin geG (ss, (g(s;, (a) - rT))
2:
Compute the optimal policy under the least-square reward estimator 9 for E S as
*(-ls) f argmax (T(+)s), -n "D)((((()))
((()))AA(A)
Ensure: π
3.2 ALGORITIIM AND MAIN RESULTS
In this subsection, we present an offline learning algorithm for f-divergence regularized bandit, f-CB, in Algorithm 2 Algorithm first leverages least-square estimator to find a function g E g that minimizes its risk the offline dataset. The algorithm then uses the least squares estimation to construct the output policy म. Compared to Algorithm [ f-CB does not require any procedure to construct pessimistic reward estimation, whose sample complexity upper bound is given as follows.
Theorem 3.2. Under Assumption 3.1 for sufficiently small E (0, 1), with probability at least is sufficient to guarantee the output policy म of f-CB to be
1 6, n log <-optimal.
Theorem 3.2 shows that the sample complexity of Algorithm@geet rid of the dependency any data coverage conditions when f is strongly convex. Intuitively, this is because the f-divergence regularization in this case is much stronger, so that both x² and से are close enough to x-
Remark 3.3. Compared to the D.. dependency in Theorem 2.10
The following hardness result justify the near-optimality of Theorem 3.2 for f-divergence- regularized contextual bandits.
Theorem 3.4. For any e (0, 0, 0, 32/3- log 2. sufficiently small e, and algorithm Alg, there is an a-strongly-convex function f and an f-divergence-regullaize contextual bandit instance such that Alg requires at least (2(aaaape- loog (c)) samples to return an e-optimal policy.
3.3 PROOF OVERVIEW OF THEOREM 3.2
Unlike KL- regularization, the x² under f-divergence might not have closed form. This means that the proof of Lemma which relies on the closed form of π², cannot be directly adopted. Therefore, we ad- dress this from dual-Bregman perspective, inspired by AAbernethy et al. (2015). For the simplicity of presentation, we consider multi-armed bandits here and omit the subscript for context s.
We provide an overview of key analysis techniques for proving Theorem 3.2
We consider the function (T)) 1) -n-1Dy(mTp (= which is the regularizer in the objective. Then its convex conjugate is given by (r)(r) = supxes= ((, r) - H (T)]. which is exactly the expected reward obtained by the optimal policy given reward function r. One observation that when f is strongly convex, the induced f-divergence, and therefore the function H are also strongly convex. Therefore, let म,, = argmax,
((TT)) ((T ((T given some reward function r, the strong convexity of (TT) gives that (H* = of our key observations:
This leads to the following regret decomposition, which is one
J(TT) - (T) = Eaan- (a)] - Em-= a (a)] - (D [=
=H* (g) (",g" -g)
-1"
(V (g),9"
which is the Bregman divergence of the dual function H' and therefore can be bounded by (g" g) V (") g) for some ÿ. By Proposition 3.2 in Penot 1994), when H is strongly convex,
we can bound 2 H (g) as follows
V'H ((T))) 1 a (f ( (a(A)))
We again suppress J Jr.,, (-) into J(.) and Ri into when there confusion.
8

---

Published as a conference paper at ICLR 2026
which enables to bound (g- is not related to π², the upper bound is independent of any notion of concentrability.
by a albbbyynaaaaaaa by -(9) Since E, (g) ( "
Empirical Rate Verification Subtipt
Empirical Rate Verification Subditt aa-1
Empirical Scaling SiB- liy w.r.t.g
nd - 11/2, 1/2
n² =112 1/21
nx a 2
Iited rate: -0 98
fitted rate: -0.98
9/10)
fitted 9/10]
fited
2.4
21
2:43
2:14
20
210
25
240
(a) Empirical rate for KL.
(b) LHS: Empirical rate for x²: RHS: Empirical scaling a.
Figure 1:
The empirical relation between log, n and log, SubOpt. The fitted rate means the slope of log, n ~ log, SubOpt estimated via linear regression. Here n is the sample size. Every point is the average over 100 independent trials.
4 EXPERIMENTS
Simulation on multi-armed bandits. We first empirically check the correctness of our matching
bounds for KL and f-divergence on the simplest testbed: two-armed bandits, i.e., A = {0, 13. We use one hard instance constructed in the proof of Theorem ( (Appendix D.5) for the simulation under KL and one hard instance constructed in the proof of Theorem 3.4 (Appendix [E.2] for the simulation under f-divergence with f(r) = a(x - /)²/2. Recall that the dependency on e in all sample complexity bounds above is ((c-l), and thus both SubOptRKL and SubOpt fdiv should be roughly proportional to n1 function of the sample size n, which can be verified from the linear regression between log, n and log, SubOpt; i.e., the estimated slope should be approximately -1. Therefore, the two fitted rates in Figure[[()) [())]ndicates that KL-PCB indeed achieves the near-optimal statistical rate n- under different T ss and the counterparts in the LHS of Figure (b) indicates the near-optimality of f-CB empirically. The contrast between Figure ((a) and the LHS of Figure [(b) also corroborates that the sample complexity against the KL-regularized objective positively depend on the concentrability, while that against the sedivergence-regulaiizeee objective does not vary with the coverage condition of re Moreover, top of the hard instance for f-divergence, we further set a = 2 /n to numerically examine the scaling of SubOpt w.r.t. the strong convexity modulus a. As shown on the RHS of Figure I(b) SubOpt fdiy remains stable as goes up given na = 2 therefore, Figure ((b) also empirically verified that SubOpt is inversely proportional to a.
C=
0-22000
C-47, 2"22203
C-41, p"2233
S.l- Spt-epttnallto Cap
Gutp-pppimalloo Cap
Sample
(a) Empirical rate for KL.
(b) Empirical rate for x
Figure 2: The empirical relation between log, and log, SubOpt for linear bandits. In the legend, denote C (resp. Dz-) by C (resp. D 2)..
9

---

Published as a conference paper at ICLR 2026
Simulation on linear bandits. We then simulate linear bandit as follows. The constructions of the feature map o, ground-truth parameter O" and the induced reward are detailed in Appendix C.1 The behavior policy is constructed as n' = 33nif(
(1 3))nnf(A=)) where A₁ A be the subset such that A consists of the k arms with the lowest expected reward. We consider three different behavior policies. (3, k) E {(1, -), (0.1, (0.05, 20) which induces various C and D so as to demonstrate the influence of coverage under different regularization. The results are compiled in Figure 2 Specifically, for the KL-regularized cases depicted in Figure [[aa]] we see that as the coverage coefficients C** and D², vary, there is a consistent sub-optimality gap margin between these instances. In contrast, Figure 2(b)shows that the sub-optimality gaps under different instances (with distinct coverage coefficient) are very close for sufficiently large sample sizes. These results corroborate theoretical finding that the sample complexity w.r.t. KL-regularized objectives is concentabilit-ddeeedden but that w.r.t f-divergence ones is not (for strongly convex f).
Unioom Tyley
Un loy
Saky Palcy
S.t-opt Geo
24
Sample
Sample Size
(a) Empirical rate for KL
(b) Empirical rate for x
Figure 3: The empirical relation between log, n and log2 SubOpt on MNIST dataset.
Real-world experiments. We further verify our theory on a vision dataset, MNIST (LeCun) 1998)
The construction of the feature map is detailed in Appendix C.2 We consider two reference polices, a uniform policy (nif(.A) and a spiky policy (.) + D.5Dirac((O)) to obtain instances with different concentrability coefficients. Figure exhibits the SubOpt curves, which show that under Kl-rregularvzation when sample size is not large enough, there exists a considerable gap between instances with different behavior policy, but the gap is vanishing as the sample size increases. On the other hand, as for >dddivergence regularization, such a gap vanishes quickly when the sample size becomes moderately large and the sub-optimal gap remains similar for larger sample sizes. These results are consistent with the simulation in Section and our theoretical findings.
5 CONCLUSION AND FUTURE WORK
In this work, we take the first step towards fully understanding the statistical efficiency with respect to
objectives of offline policy learning by sharp analyses for two empir- ically relevant subclasses. (1) We are the first to show that single-policy concentrability is nearly the right coverage condition for reverse KL to achieve the fast é(c=!) sample complexity. The novel techniques in algorithm analysis leverages the curvature of KL-regularized objectives and in- tegrates pessimism with a newly identified moment-basee observation, enabling a neat refinement of irean-value-type argument to the extreme; which decoupled from tricky algorithmic tweaks, and thus might be of independent interest. (2) If strong convexity is further imposed on f. our fast Ô(c-)) sample complexity is provably free of any coverage dependency. Unlike those for KL, the upper bound arguments for strongly convex f do not rely on specific closed-form solutions of the regularized objective maximizer.
All techniques in this work can be generalized beyond vanilla absolute reward feedback, as certified by CDBs, which is detailed in Appendix G under slightly different notion of D2 tailored for pairwise comparison feedback. However, for reverse-KL regularization, the DŻ. in the upper bound and the C"" in the lower bound still does not perfectly match. Also, for general f-divergence other than reverse-KL. our analyses require f to be twice-continuously differentiable and strongly convex. Fully closing the gap under reverse-Ke KL regularization and extending the analysis to general f-divergences interesting directions for future work.
10

---

Published as a conference paper at ICLR 2026
THE USE OF LARGE LANGUAGE MODELS (LLMs)
We use LLMs as a tool to refine our writing and correct grammatical errors.
ACKNOWLEDGMENT
We thank the anonymous reviewers and area chair for their helpful comments. QZ, KJ, HZ and QG are supported in part by the National Science Foundation DMS-2323113 and IIS-2403400. HZ is also supported in part by 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.
REFERENCES
Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smooth- ness. Advances Neural Information Processing Systems, 28, 2015.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy policy optimization. In International conference machine learning, pp- 151-160. PMLR, 2019.
Gholamali Aminian, Amir R Asadi, Idan Shenfeld, and Youssef Mroueh. Theoretical analysis of kl-regularized rihf with multiple reference models. arXiv preprint arXiv:2502.01203. 2025.
Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy, Scalable online exploration via cov- erability. In Proceedings of the 41st International Conference on Machine Learning, pp. 1392- 1455, 2024.
Michéle Basseville. Divergence measures for statistical data processing annotated bibliography. Signal Processing, 93(4):621-63) 2013.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Fan Chen, Dylan Foster, Yanjun Han, Jian Qian, Alexander Rakhlin, and Yunbei Xu. Assouad, fano, and le cam with interaction: A unifying lower bound framework and characterization for bandit learnability, Advances in Nearal Information Processing Systems, 37:75585-75641 2024.
Jinglin Chen and Nan Jiang. Information-theoreeie considerations in batch reinforcement learning.
In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Imre Csiszár. On information-type measure of difference of probability distributions and indirect observations. Studia Sci. Math. Hungar. 2:299-318, 1967.
Qiwei Di, Heyang Zhao, Jiafan He, and Quanquan Gu. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Con- textual dueling bandits. In Conference Learning Theory, pp. 563-587. PMLR, 2015.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances in neural information processing systems, 23, 2010.
Dylan Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive deci- sion making. arXiv preprint 12X::22312.16730 2023.

---

Published as a conference paper at ICLR 2026
Dylan Foster, Zakaria Mhammedi, and Dhruv Rohatgi. Is a good foundation necessary for efficient reinforcement learning? the computational role of the base model in exploration. arXiv preprint arXiv:2503.07453, 2025.
Germano Gabbianelli, Gergely Neu, and Matteo Papini. Importance-weighted offline learning done right. In International Conference on Algorithmic Learning Theory, pp. 614-634. PMLR, 2024.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pp. 2160-2169 PMLR, 2019.
Edgar N Gilbert. A comparison of signalling alphabets. The Bell system technical journal, (1): 504-522, 1952.
Dhawal Gupta, Christoph Dann, and Alekh Agarwal. P3o: Pessimistic preference-based policy optimization for robust alignment from preferences. In Adaptive Foundation Models: Evolving Al for Personalized and Efficient Learning, 2024.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics, pp. 4259-4280. PMLR, 2022.
Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J Foster. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. In Forty-second International Conference on Machine Learning, 2025a
Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason D Lee, Wen Sun, Akshay Krishnamurthy, and Dylan J Foster. Correcting the mythos of Kl-regularization: Direct alignment without overopti- mization via chi-squared preference optimization. In The Thirteenth International Conference on Learning Representations, 2025b.
Kaixuan Ji, Qingyue Zhao, Jiafan He, Weitong Zhang, and Quanquan Gu. Horizon-free reinforce- ment learning in adversarial linear mixture mdps. arXiv preprint arX.v:2305.08359, 2023.
Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. Statistical Science, 2024.
Jiantao Jiao, Thomas A Courtade, Albert No, Kartik Venkat, and Tsachy Weissman. Information measures: the curious case of the binary alphabet. IEEE Transactions on Information Theory, 60 (12):7616-7626. 2014.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMIR, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
Tadashi Kozuno, Wenhao Yang, Nino Vieillard, Toshinori Kitamura, Yunhao Tang, Jincheng Mei, Pierre Ménard, Mohammad Gheshlaghi Azar, Michal Valko, Rémi Munos, al. Kl-entropy- regularized rl with a generative model is minimax optimal. arXiv preprint arXiv:2205. 2022.
Cassidy Laidlaw, Shivam Singhal, and Anca Dragan. Correlated proxies: new definition and improved mitigation for reward hacking. In The Thirteenth International Conference on Learning Representations, 2025.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statis- fies, pp. 38-5 53, 1973.
12

---

Published as a conference paper at ICLR 2026
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. con/exdb/nmist// 1998.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 0000100000000,0. 2018.
Sergey Levine and Vladlen Koltun. Guided policy search. International conference on machine learning, pp. 1-9. PMLR, 2013.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. Journal of Machine Learning Research, 17(39):1-40, 2016.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233-260, 2024.
Gene Li, Cong Ma, and Nati Srebro. Pessimism for offline linear contextual bandits using l, confi- dence sets. Advances in Nearal Information Processing Systems, 35:20974-20987, 2022.
Guanlin Liu, Kaixuan Ji, Renjie Zheng, Zheng Wu, Chen Dun, Quanquan Gu, and Lin Yan. En- hancing multi-step reasoming abilities of language models through direct q-function optimization. arXiv preprint arXiv:2410.09302, 2024.
Zhuang Liu, Xuanlin Li, Bingyi Kang, and Trevor Darrell. Regularization matters in policy opti- mization. arXiv preprint
2019.
Ben London and Ted Sandler. Bayesian counterfactual risk minimization. In International Confer- ence on Machine Learning. pp. 4125-4133, PMLR, 2019.
Alfred Müller. Integral probability metries and their generating classes of functions. Advances in applied probability, 29(2):429-443. 1997.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:23 (tt::23/2.00880 2023.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. unified view of entropy- markov decision processes. arXiv preprint arXiv:1705.07798. 2017.
Long Ouyang. Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 2022.
Jean-Paul Penot. Sub-hessians, super-hessians and conjugation. Nonlinear Analysis: ods & Applications, 23(6):689-702, 1994.
Theory, Meth-
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge univer- sity press, 2025.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2023.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716 2021.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics, volume 4, pp. 547-562. University of California Press, 1961.
13

---

Published as a conference paper at ICLR 2026
Pierre Harvey Richemond, Yunhao Tang, Daniel Guo, Daniele Calandriello, Mohammad Gheshlaghi Azar, Rafael Rafailov, Bernardo Avila Pires, Eugene Tarassov, Lucas Spangher, Will Ellsworth, et al. Offline regularised reinforcement learning for large language models alignment. arXiv preprint arXiv:2405. 19107, 2024.
Otmane Sakhi, Pierre Alquier, and Nicolas Chopin. Pac-bayesian offline contextual bandits with guarantees. In International Conference Machine Learning, pp- 29777-29799 PMLR, 2023.
Otmane Sakhi, Imad Aouali, Pierre Alquier, and Nicolas Chopin. Logarithmic smoothing for pes- simistic oft-policy evaluation, selection and learning. Advances in Neural Information Processing Systems, 37:80706-80755, 2024.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International conference on machine learning, pp. 19967-20025. PMLR, 2022.
Yuda Song, Gokul Swamy, Aarti Singh, Drew Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. International conference on machine learning, pp. 814 823. PMLR, 2015.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021.
Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957.
Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pictquin, Rémi Munos, and Matthieu Geist. Leverage the average: analysis of kl regularization in reinforcement learning. Advances in Neural Information Processing Systems, 33:12163-12174, 2020.
Martin Wainwright. High- diigs-dimessoonl statistics: A non-asymptotic viewpoint, volume 48. Cam bridge university press, 2019.
Zhiyong Wang, Dongruo Zhou, John Lui, and Wen Sun. Model-based rl as minimalist approach to horizon-free and second-order bounds. arXiv preprint arXiv:2408. 08994, 2024.
Ronald J Williams. Simple statistical
algorithms for connectionist reinforcement
learning. Machine learning, 8:229-25 22699226,1111 1992.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint 4rXiv:2405.00675. 2024.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021a.
Tengyang Xie, Nan Jiang. Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407. 2021b.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q -ppappooxnnttion for sample-efficiett rlhf. arXiv preprint arXiv:2405.2 1046, 2024.
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly mini- max optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205. 200o:2205.5552... 2022.
14

---

Published as a conference paper at ICLR 2026
Wei Xiong, Hanze Dong. Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning. 2024.
Yinglun Xu, Hangoo Kang, Tarun Suresh, Yuxuan Wan, and Gagandeep Singh. Learning a pes- simistic reward model in rlhf. arXiv preprint arXiv:2505.205::: 2025.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.073344 2024.
Bin Yu. Assouad, fano, and cam. In Festschrift for Lucien Cam: research papers in probability and statistics, pp. 423 435. Springer, 1997.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed ducling bandits problem. Journal of Computer and System Sciences, 78(5):158--155, 2012.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference Learning Theory, pp. 2730-2775. PMLR, 2022.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline preference-based reinforcement learning, arXiv preprint arXiv:2305.1483 2023.
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023. doi: 10.1017/978 11019998880099977
Yifan Zhang, Ge Zhang, Yue Wu, Kangping Xu, and Quanquan Gu. General preference modeling with preference representations for aligning language models. arXiv preprint arXiv:2410.02197, 2024.
Heyang Zhao, Chenlu Ye, Quanquan Gu, and Tong Zhang. Sharp analysis for kl-regularized con- textual bandits and rlhf. arXiv preprint arXiv:241 1..46225 2024.
Heyang Zhao, Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang. Logarithmic regret for online kl-regularized reinforcement learning, arXiv preprint arXiv:2502.074460 2025.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb- ucb-based exploration. In International conference on machine learning, pp. 1 1492-1 1502. PMLR, 2020.
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. arXiv preprint arXiv: 06573, 2018
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feed- back from pairwise k-wise comparisons. In International Conference on Machine Learning, pp. 43037-43061 PMLR, 2023.
Brian D Ziebart, Andrew I. Maas, J Andrew Bagnell, Anind K Dey, al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433-1438. Chicago, II., USA, 2008
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International conference on machine learning, pp. 10-18. PMLR, 2014.
CONTENTS
1
Introduction
Contributions
1.2
Key Related Work
15

---

Published as a conference paper at ICLR 2026
2
KL-reuularized Contextual Bandits
2.1
Problem Setup
2.2
Algorithm
Theoretical Results
2.4
Proof Overview of Theorem 2.
3
rddvergence-regnlariied Contextual Bandits
3.1
Problem Setup
3.2
Algorithm and Main Results
3.3
Proof Overview of Theorem 3.2
Experiments
5
Conclusion and Future Work
10
Additional Review of Existing Results
17
A.I Previous Attempts Understanding KL-regularized RL
17
Additional Discussion of Relation between Coverage Measures
18
Experimental Details
19
Linear Bandits
19
C22 Real-Wolf Wold Experiments
19
Missing Proofs from Section
19
D.I Proof of Lemma 2.9
19
D22 Proof of Lemma 2.14
20
D.3 Proof of Lemma 2.15
21
Proof of Theorem 20
D.5 Proof of Theorem 2.
22
E
Missing Proof from Section
24
Proof of Theorem 3.2
E.2 Proof of Theorem 3,4
26
Generalization to contextual dueling bandits
27
Problem setup
28
Algorithms and Results
28
F2.1
Algorithms for KL-regularized contextual dueling bandits
28
F2.22
Algorithm and Results for /ddivergence Regularized CDBs
29
Missing proof from Appendix
30
16

---

Published as a conference paper at ICLR 2026
G.
1
Proof of Theorem F.4
30
2 Proof of Theorem F
32
3 Proof of Theorem
33
Proof of Theorem
34
H Auxiliary Lemmas
35
A ADDITIONAL REVIEW OF EXISTING RESULTS
Additional notations. Besides the notation introduced in Section 1 we will use the following notations in Appendix. We denote [N] := fI. .N} for any positive integer N. Boldfaced lower case (resp. upper case) letters are reserved for vectors (resp. matrices). Given positive definite E E Radd and x E RR, we denote the vector's Euclidean norm by | and define ||x|| > = vx Ex. We use Ber to denote Bernoulli distribution with expectation and Uni for the uniform distribution on finite set X. For & E R!AI, we denote || = Eoea (sa). We also denote In = M(mn by In Z On in Appendix. We use du for Hamming distance.
A.1 PREVIOUS ATTEMPTS ON UNDERSTANDING KL-REGULLARIZE RL.
There has been a surge of interest in understanding the principle behind KI.-regularized RI.. RI.. Ahhee al. (2019); Liu et al. (2019) studied by ablation the effect of entropy regularization on the stability of policy improvement in policy optimization, the regret of which has been rigorously settled under the classic online mirror descent framework (Cai et al.) 2020 He et al.) 2022 Ji al., 2023). Neu iet al. (2017) unified popular KL-regularized policy optimization algorithms under a convex opti- mization framework, but the interplay with the data was left untouched. A series of work (Geist et al. 2019 Vieillard et al., 2020 Kozuno et al. 2022) then analyzed the sample complexity of algorithms using KI./entropy-tyi -typ proximal terms with respect the previous iteration or/and en- tropy regularizer with improved dependence on the effective horizon in discounted Markov decision processes. However, the performance metric in these studies is still the unregularized reward max- imization objective, under which the sample complexity for finding an c-optimal policy is at least equal the statistical limit (2(c-)).
Convergence under regularized objectives. Several recent studies (Xie et al. 2024 Xiong al.) 2024 Zhao et al. 2024: 2025 Foster et al. 2025) switched the focus to analyzing the sub-optimality guarantee with respect to the regularized objective (..I). In particular, Xie et al. (2024) stud- ied token-level Markov decision processes (MDPs) and proposed a KL-regularized RL algorithm named XPO, which achieves Ō(e-2) sample complexity under their notion of all-policy concentra- bility. [iing et al. (2024) proposed an Offline GSHF algorithm via the principle of pessimism in the
face of uncertainry, and proved ((c-2) sample complexity under single-policy concentrability (See Section 2action2.1]for detailed definitions of concentrability). On the other hand, the sharp analysis in Zhao
ct al. (204 vields the optimal sample complexity Ö(E-)). but requires all-policy concentrability
(Zhao et al. 2024, Definition 2.6), i.e., the behavior policy ref is required cover the entire func- tion class for all possible policies. ZZhao et al. (2025) considered the online episodic MDP setting, which inherently does need any notion of data coverage and thus their results not directly adaptable to our offline setting. Foster et al. (2025) considered an interesting hybrid setting in which the n state-action pairs are still from the offline dataset but ?(n) online reward queries and policy switches are allowed; in contrast, in our setting, all reward signals are obtained in a purely offline manner.
Previous analyses and results in detail. Here, we briefly discuss the direct adaptation of previous sample complexity analysis and results (with respect to KL-regularized objectives) to our setting and demonstrate the reason why theirs cannot imply an Ö(e=1) sample complexity without all all-policy concentrability. In previous analysis of pessimism for unregularized objectives (Jin et al., 2021 Xiong al. 2022), the sub-optimality gap is decomposed via the performance difference lemma as
17

---

Published as a conference paper at ICLR 2026
follows
-
= Eawr (a)] - Ba 0 (a) 1 (L 11 + KL (e
x B (a)) R [(a]] -1 "KL(" || + KL( |T
Ea (a)] Baw, [aa)] 77 'KLK" [| +1 TKLLLLL ( ||
Fa 19" (a) - {(a)]:
where the first inequality holds due to pessimism and last inequality holds due म is optimal for G. Notably, the KL-regularization term is canceled out in the analysis, leading to loose sample complexity (( since the curvature of KI-divergence is not exploited. Specifically, under linear function approximation, this performance gap, obtained by [ioog et al. (2024) becomes
J(m²) J(m) - | (oxxTr(((ss))))
(Ø(s, a]] 1/
x RHS,
where is the reference vector, Φ(s,a) E Rd is the feature map, and Eaft Ei= (8;; a;) ((),);;;()) az) is the sample covariance matrix. However, we can show that RHS can be bounded from below by
[[((aa))pxx- vil Amin (2nth) = || [b(s, a)] 1/ Ammax (oir) 1/2
[((a)) [0(s, a)] -/|tr(Zoot))1 1/22
-1/2
|[(e [0(8 a)] - 1/1l
Σ [1 (
-Qn =//11112,
where Amin and Amax is the minimum and maximum eigenvalue of a matrix. the first inequality
holds due to the fact that T
Σx 2 ||x||2>min and the second inequality holds due to Amax ()) S
tr(E). Zhao et al. 2024 proposed a two-stage learning algorithm and obtained an Ö(c-)) sample complexity for online Kl-rregulariee bandits. The algorithm can be adopted offline learning by removing the second stage and treat the samples from first stage as the offline dataset. An analogous
analysis gives sample complexity of Ō(D² where D2 is the all- all-policy concentrability.
B ADDITIONAL DISCUSSION OF RELATION BETWEEN COVERAGE MEASURES
In this section, we provide more illustrations on the relation between two coverage measures, D and C In particular, we provide two cases under linear function approximation, on one of which D2 O(dC*) and on the other we have D < C where is the dimension of the function class. We summarized them as two propositions.
Proposition B.1. There exist a KL-regularized linear bandit instance, such that D (ddC*))
Proof. We construct the instance as follows. Let d = 24 + be some odd number and consider an 2. 1-armed bandit, such that the feature vector of the i-th arm, ((a,) = e, Rd which has on its i-th entry and 0 on all other entries. The reference policy - (a:) (2AC) for E [2A] and re (a2A-1) (C 1)/C, where 2C
e". The ground truth reward function 0* Σ Eisa e
and the function class is given by all ||0|,c < 1. By construction, we know that π *a,,) 2 π (a.)
and only if E [A] and its closed form given by
e
1
t' T'a))
Ae 20-11 2A'
which gives C"" C.. Now we compute the D2_ of this instance. For all E [A], we know that
e
D²((,)) sup
2CA e(C))
||0] 52 End e,)
Thii he done by setting the in their paper
18

---

Published as a conference paper at ICLR 2026
where the second equation holds with 0 C₁. Taking expectation over x², we have
D
(a,;)) e(C* d),
iE[A]
which concludes the proof.
The following proposition provides another instance on which D C Proposition B.2. For any C 2 2, there exists a KL-regularized linear bandit instance, such that C = C/2 and D = (1))
Proof. We consider the function class of 0 E R and ||||| S 2.2 The instance consists of three arms,
where (}a)) = (1, 0), ((22) = (0, 1), and ((ag) = (1, The ground truth parameter 0 (1,
The reference policy is given by (a;()
x' (a2) = 1/2 1/2C and x (a1) 1/C, where
C' - 111 =... A direct computation yields that
e"
C
π (0z)
C= =
C
en +-
e
+ - 2
On the other hand, we know that for i 1,2, we have (a:):) S (a:) 4. As for ds since have (0, d(a)))) that (ag) S (a)) + 2D s 16. Therefore, taking expectation over π,",, we know that D S 12 which is a constant.
(0, p(a)) o(a2)) 2 (0, o(a1)) 2 ((2))()))) which gives
C EXPERIMENTAL DETAILS
C.I LINEAR BANDITS
The linear bandit instance used for Figure 2 has d 20 and |A| 100. For each arm a A,
we randomly generate its feature vector ((a) Rd such that [| = 1. We then randomly sample the model parameter 0* E IRd such that || = and the expected reward obtained via r(a)= " ((a)).
C.2 REAL-WOL EXPERIMENTS
MNIST consists of 60000 figures, each which of x 28 pixels and consists of handwritten digit in {0...., 9}. context. To obtain the feature (bs,, a), we first use the hidden representation of a classifier to embed each image as a vector in IR We then follow the approach in Zhou et al. (2020) to obtain the feature of each context-ace acction pair by having Φ(s, a) = x @ Cat1 image encoder and @ stands for tensor product.
Here, we consider each image context and A {0, {...... 9} for each
where x is the output of R 1000
D MISSING PROOFS FROM SECTION 2
D.1 PROOF OF LEMMA 2.9
We first provide the following lemmas of concentration.
Lemma D.1 ZZhao et al. 2024 Lemma C.I), For any policy x and state-action pairs {(s,, mm
generated i..dd from p X n. and E. < with probability at least 8, for any 91 and 92 we have
Exxx (91 (2(5, ((ss,)))
3
2 Σ (gi(s;, a:) - a:))
log(2Ng(c.)/8) + 10cz. 3n
32
n
where No((e) is the c.vveriin number of G.
Lemma D.2 (Zhao et al. 2024. Lemma C.2). For arbitrary policy æ and dataset {(s ag, r:) )m generated i.i.d., from the product of p and the Bradley-Terry Model; let be the least square estimator of g", then for any < & < 1 and > 0, with probability at least 8 we have
(ō(si, a;) (",, a:))² 16log(aVg(c.)/0) + 4nca-
19

---

Published as a conference paper at ICLR 2026
Now are ready to prove Lemma 2.9
Proof of Lemma 2.9 We have the following inequality
(0(s.a) a) 5" (8, a))²
(ō(s,a) 96 (s(),a))²
E (((())))
Byg [(((s, a) 9- a))
sup ( 92
01 Baddd ((9 92 a)) 2 Exrr
a))²
D8 a), n'd " E (0(ss g" (s,
(D.1)
where the inequality holds by taking supremum to 91.92 G. Now we have
2 (g(s) 9" as)
32
Exd [[g(s, a) - g" (s, a)s
+ (og(2N)(ee)/0)) + 10ec
n
3n
2
32
[66 ())))) + 4nec] + log log(2Ng(e.)/O)) + 10c
3n
128
log (og + 18c.:
(D.2)
3m
where the first inequality holds due to Lemma D.1 and second holds due to Lemma D.2
Plug-
ging D.2) into D.I) and setting E, = O(n -1 complete the proof.
D.2 PROOF OF LEMMA 2.14
This proof is extracted from the proof of Zhao et (2024) Theorem 3.3) and we present here for completeness. By definition of our objective in (2.1) we have
J(x") -(Tg)
T" (als)
- log Ty (a(s)
1
((x (s, 17 log gee (alss)
E (x
(s(
11 राट (als)
1) B(esa))px log (als) cxp(119 (s,, (s, a))
B log TT exp n1 (s, a))
T' (a|s)
[a(((8)
17 Expup llog Zg (s)] Egup log (x)] - Bamp
Σ
Ta(as)) (0( ((s,
aEd
where for all g we detine (-) follows,
(z(.) = Σ
π rof (al.) (a))) exp (ng(:,a)).
aEA
We further denote A(s, a) = g(8, a) 9" (s, a) and (g) log (g(s) E.EA To(als) A(s, a).
It worth noticing that 17 E2 gg (H (1 H2( J(T) (TTg). Now we take derivative of H with respect to ass
(H,
a
log (g()) -1 17 Σ (als)) s(s.a))
0 a)
( a)
aEA
(g(s) re (als) exp(n a)) -7-11
17 (a(()s)
172 A(s,a) (als) exp(1 g(8,a))
+ 122 -(s (als) exp(n a))
(s(s)
[s)
nh (a'lx) exp(1 g(s, a')) 17 A(s,d') J (als) exp(1 g(s.a))
+
(s)
(g(s)
e'EA'(a)
(ag)) + {Tg(s))) A(s + t2²
Σ (g(d)))),,(ls))Asssd)
d'EAl(o)
20

---

Published as a conference paper at ICLR 2026
Therefore, by mean value theorem, there exists
[0, and 9, 79 + (1 ~)0" such that
H.(g) H²(g") = -1² Σ
Tah (als) mm Σ Σ
Th (12l=)
aEA
- By (00(s,a)-g(s.(l)) g(s.a)))].
- a)s 9 + yn (Baws [(0'(s. -((,)))
2 -
where the inequality holds by omitting the second term and 7 S 1. Now taking expectation over p. we have
J(TT) - ((Tg) = 1i (BoNo(H.(O") - H.(g))
S (BB(a,))ppo (8, {) g(s,
which concludes the proof.
D.3 PROOF OF LEMMA 2.15
Proof of Lemma 2.15 and y2 is
We define Y = -X Then it suffices to show that the covariance between Y
Cov(Y, y2) -E -
(
-
20,
where both inequalities follow from Jensen's inequality.
D.4 PROOF OF THEBREM 2.10
To start with, we first define the following quantities. For all y E [0, 1]. we define 9, = =9 + 7)g* and denote
(-Is) x Te (+|s) exp (ng, ,), Vs S; G(7) = Epx,, (Ø ( -ū-g")² (s,)
The key to our analysis is the monotonicity of the function G(y) y, which formally stated in the following lemma.
Lemma D.3. On event E, 0 E argmax,e(o.1) G(7).
Proof. For simplicity, we use A(s, a) to denote (g (s), a) this proof. Then we know that L(s, a) < 0 for all as e S on event E. The most direct way to prove is take derivative of G with respect to y, which corresponds to the policy gradient (Sutton et al. 1999) of R., and thus implying favorable structure. A direct calculation yields that
Epxa, V.
a) - Ed' [D(s,
= -EE En, (s, - Ex, [A a) Ex., (sss a)]
00,
where IE, the shorthand of E Egr.ps E,,, is the shorthand of Eg the first equation is derived from standard policy gradient and the inequality holds conditioned on the event (() due to Lemma 2.15 and Lemma 2.15
Now ready to prove Theorem 2.10
21

---

Published as a conference paper at ICLR 2026
Proof of Theorem 2.10
Following the proof of Zhao et al. 22024 Theorem 3.3), we know that there
exists 7 E [0,1] such that
J(x)) - J(a) n)(()) n)(())
(D.33
where the first inequality holds due to Lemma 2.14 and the second inequality holds due to the event and Lemma D.3 The term G(O) can be further bounded with the D²-based concentrability as
follows
G( 1) (e.))) (o- (0-9")((s,a)
(s.) (s.a))
An (e [ (() x);
O(n logg (oggge.) (s.)),
(D.4)
where the second inequality holds conditioned on {6) because of Lemma D.3 and the last inequal- ity follows from the definition of E()) together with Line 2 By Lemma 2.9 know that event & holds with probability at least - 6, which finishes the proof.
D.5 PROOF OF THBOREM 2.11
Proof of Theorem 2.17
We consider the family of contextual bandits with S == [S], A= |A| < oo
and reward function in some function class G composed of function S A + [0, 1] follows.
CBg
re m)) G,P E A(S), Te A(A[S)).
(D.5)
Our goal is to prove the following statement. Fixing any $ 2 1, > 4lgg 2 and C E (2, cxp(n/ [4)], then for any estimator D + म A(A(S), for any n 2 16SC", there exist some function class g, such that E inst (S, p, re n) CBg with single-policy concentrability C" < C regularization coefficient |S| = S = Ollog (G). and
SubOpIRKL (f; inst) 2
(D.6)
Since log [9] 2 Log.N((e) for any e E (0, 1). equation (D6 yields the desired bound.
We set S = [S] [+1), p Unif and the reference policy to be
Vs E re (- 1--,,---= rd (+1(s)
C-1;
where C > is parameter to be specified later. We construct 2 Bernoulli reward functions, in particular, Vr E {+1}5, the mean function F; of the reward (indexed by r) is defined as
Tr (s, 1) 0.5 T,,, (s, +1) = 0.5
for any state E S, where E (0, 1/2) and E (0. 1/4] will be specified later. We omit the RKL subscript in the following argument when is clear in context. By (2.2). the optimal policy गे under r, is
exp (n(a + r26))
C-1 exp (1(a+ T,6)) +C-1
Vs E S, (-11s_ exp (n(a + T-6)) + + 77 (+1|s)
(D.7)
Since C* < exp(n/4), we assign C = C* and = 17 log C-1 =ex=xxx(1o)) which gives
(-1ss
exp(n(a + T,O))
exp(1TT0)
Vs S, (-1
< C - + + T,5)) C. + exp(177.0) C²;
Vs S, (+11|s
C
1
+1 SC= CC=²:
(+1ls)
C C-1
where the last inequality is due to the assumption C* 2 2. Therefore, we obtain
max = C".
(D.8)
r
22

---

Published as a conference paper at ICLR 2026
We will abuse the notation SubOpt(f;;7 == SubOpt(f;;r.) Since p US)
$
SubOpI(T;:)) - Σ Sub)pt,(R;T))
(D.9)
where
rr (x) - -11 log (1(ss
xp (-1s) - (-11s), - -noll (11(s) x- (115)
SubOpt, (R:T) =
(als) exp (nr-
" Banx
log
t (a|s)
7 (als) exp (177 (s,a))
Biaa(11s))
log
i(als)
Bawx)((11))
log
rof (b|s) exp
17
DEA
J (als)
exp (s,
Bawa(-1as)
log
{(ass)
1 (-12(-1e) ())
x
(als) exp (W (8, a))
(als) exp (11,(s, (s)
log
log
17
(a(s))
{(ass)
17 KL (+ (+]])T))
(D.10)
We write
~ 7' if T' E {=1 differ in only the s-th coordinate and 7 ~ 7' 3s E S, ~r ~.
By D.10
Vs S, VT, 7' {=1} with T ~ T'.
SubOpt, (T: 7) + SubOpt, (R:T')
"KL (T] + + "KL
KL ( +++
((a(s)
=217 Σ i(a|s) log
V (= ((aaassT (a|s)
aEA
2n) KL (f(-18)]| (-16) 211 Ea-7(-1o) log
Σ beA
V T (=(6)))
2 -2 1 logg Σ V (b1s)
DEA
(exp(nō) + ()(exp( +
= log
(D.11)
4
v m² (-)))))) EseA V (b)s) (b|s) for every s E S, the inequality is due to the non-negativity of KL divergence, and the last equality follows from (D.7 together with the design choice C - exp(na).
where म (-1s)
Case n76 < 2. Recall that Vx E R, (e te = x2 2k=0
22 (2k+2)
2 x²/2, which implics
1
log 1 1 n6 16
1)) log (1+
17262
1 17282/4
D.II
n702/8 /8.
17
2
4
1
(D.12)
Here, the last inequality is due to 7/ < 1 and Vz E [0, 1), log(1 + x) 2 x/2.
Case n78 > 2.
We have -17 10 22ogg 2 > -5 log 2, which implies the following bound.
exp(no) 1 11ō 2 log 2 5 11 112-2 log 2 (1 log 2)5 2 35/10. (D.13)
D.11
log
In summary, D.12 and D.13 imply that Vs E S, VT, E {+ with F ~ 7'.
> 1182 ^
36
SubOpt,(f;r))
(D.14)
10
23

---

Published as a conference paper at ICLR 2026
Let P. be the distribution of (s, a. where p.a (-1s), and Bern(r-(s,a)). Then dr E EV,,,'' E {=1}$ with T ~x T',
KL (P+
Σ ref 3,
5
C
KL (B)m (ern)rrrr -1))
5
45
166²
(D.15)
S0.00 82)
3SC
where we use the requirement 1/4 and KL (Bern(p)] (er)(()) I (p q) (q(1 9)) Then
let PD, be the distribution of 'D given the mean reward function Tr, we employ (.15)) to get
16nd
KL (PD.IIPp,)) nKL (P.1Pp) <
(D.16)
3SC
Since 16SC 16SC by design, we can set d /SC/n (which ensures 5 S 1/4) to obtain
sup MubbOpt(f;instt > inst
sup SubOpt(7;7) rE(+1}
1
1782
30
5
Λ
min exp (- KL TNUT'
(Po,1IP'.) IIPr..,)
5
8
10
S1
3v S*
2 DSCC
SC
exp - 16/3)
32n
40
where the 5 in the second inequality comes from D.9 the second inequality is by substituting D.14) into Assouad's Lemma (Lemma H.3 and the last mequality due (D.16).
E MISSING PROOF FROM SECTION 3
E. PROOF OF THEOREM 3.2
Before coming to the proof, we first introduce some useful properties. The following properties characterize the convexity of f-divergence when f is (strongly) convex.
The strong-convexity of f implies that the corresponding f-divergence, Dy(-1]=/e) is also strongly convex with respect to all æ S > ((A) supported by re.
Proposition E.1. Given context 8, Dy (T (T(+s) (-Iss) strict convex with respect to क if f is strictly convex.
Proposition E.2. Given context 8, a(-1s) + (z) 4a-strong convex with respect to the metric TV if is a-strongly convex.
Proof of Proposition E.2
We first show the gradient of D, with respect to æ.
aD / (T
refy m ((a)
π (b)
T(a) ree (a)
(b)f
=f
OT(a
(b)
PEA
24

---

Published as a conference paper at ICLR 2026
Now consider IT, 72 E ((A) supported by nr
Dj 1 - " (
n2, VD (T2(1211="1)
Σ (m) - =2(aa) 1
Ti (a)
TT((a)
tal m2(a)
(())
(a)
preer (a)
(
(a)
T m2(a)
T. (((((() -  (a)
T Ti(a)
T2
Σ BEA
(a)
/
(. (a)
T (a)
( (a)
(a) ) (TI(a) T²(a))²
(1)
Tz(a)
ref (a)
2 aEA
π
(a)
1
g (a)
aEA
ti (a) - m
2
where the first inequality holds due to f's strong convexity and the second holds due to Cauchy-Schwarz. The proof finishes since | - Telli = 2TV (mllTT))
We first introduce some notation and important properties concerning the convex conju- gate of functions. Given some context 8, we denote the regularization term as H.(x)) y ( (-1s)). We use (r) to denote the convex conjugate of H. which is deñned
H) = sup ((t()ss) - -H((T))
rES-A
We have the following properties for the convex conjugate. The first property gives the gradient of convex conjugate (see, e.g., Zhou 2018 Lemma 5).
Proposition E.3. Given context 8, and convex f. let a (TT()))) r(s. HH,(T) for some r, then the gradient of H; is given by (r) (-1s).
We also need some properties of F2 the Hessian matrix of the convex conjugate function. We first give the Hessian matrix of the original function H3 as follows.
f" x(ails) x (ai 8)
f" [() (ajA
(²H -ddag
x
(E.1)
re (ails)
ref (a/a)l8)
Furthermore, when f is a-strongly convex, we have
VHH am - ddag nd (ails)=1,,-.
_ (s) 1s)
The following lemma, which gives estimate of V H3 is the pivot of the proof. Lemma E.4. For any reward r S x A + [0, 1], we have
(r); = a -'ddiag - (a ss), T ( Is)).
Proof of Lemma E.4 Given reward function 8 A + [0. 1]. we consider
Tr E argmax ((T()))) H.(r)).
rES-AIAi
From F.1 we know that 2 H. (T..) is invertible. Therefore, by Penot 1994 Proposition 3.2, we have (r) 1 H. Since f is a-strongly convex, we have
H = a addiiggaa ( (s), ... - (a [s))
which finishes the proof.
25

---

Published as a conference paper at ICLR 2026
Now are ready to prove Theorem 3.2
Proof of Theorem 3.2 tion 9¹, we know that
Consider our estimation which approximates the ground truth reward func-
argmax (E(ssa)--x==((ssaa) (m) *ES-
We have the following sub-optimality decomposition
J(x)) J(ī) Beup Eawa Pg (s, - Eu~# (s, -7 (1= (f)(((
Bguup (g") (g) ( 9)
Eaupl (g") (g) (VH g)
Esspp (g - g) V V2H, (g) - g)..
where 3 =9 + (1 7)g and 7 E [0, and the last equation holds due to Taylor's expansion. Now, for any 8 E (0, and ca > 0, with probability at least 1
J( - (
E Esmpl ووا" g) v "1' - 3)]
S - BBu (g" 9)
... "" ("= -3]
1 (aa)~-x= (g (g"(8,
(8, a)s
128
a
log (cg(2N)(c.))0)) 18c
3n
where the first inequality holds due to Lemma E.4 and last inequality holds due to equation D.2 compleessseeess
Setting & O(n-)) completes the proof.
E.2 PROOF OF THEOREM 3.4
We first provide the following lemma that gives the close form of optimal policy under x2 diveeggee regularization.
Lemma E.S (Huang et al. 2205a Lemma G.2)). Let xt be the optimal policy of x2 diverreee regularized objective with reward function r, then क² has the closed form
x ref (.) max (0, (0()((()) >))} where Σ (a) 1.
aEA
By Proposition E.2 fdiv argmax Jaaiv (T) is unique. The sub-optimality gap for f- divergence is consequently defined as
SubOpt yaiv (av( (.) = SubOpt As, =
=J J - J.aiv()..
(E.2)
Now we are ready to prove Theorem 3.4
We still consider the family of contextual bandits CBg given by (D.)). We, still, aim to prove the following statement. Fixing any S > 32 2, 1 > log and a, we set f() : a(æ 1)2/2 /2, then for any estimator D के A(A[S), for any sufficiently large, there exist some function class g, such that 3 inst (S, A.r, m)) e CBg with [S] =
Proof of Theorem 3.4
(log [G]), and
SubOpt (M: inst)
2 a -n-
(E.3)
Since log [ 2 (g() for any c (0, 1), equation
E.3 yields the desired bound.
We again omit subscripts fdiv when is clear in context. We set S = |S], A = +1), and P Uni For all S, re Unif(AA). We further consider the following reward function
class. We leverage Lemma H.4 and obtain a set E {-1, +1 such that (1) |V] 2 exp(S/8)
and (2) for any v, vf E V,v o' one has ||e ||1 S/2. We construct the following reward
26

---

Published as a conference paper at ICLR 2026
function class where the reward follows Bernuuli distribution and the mean functions given by the function class
g (r. -1) -/2 1 u +1) 1/2+ o.8, As Slu V),
where 8 1) is to be specified later. Fix some context and * v2 different at entry and corresponding reward r and 12. Without loss of generality, we assume ri (8, :) = (1/2 6, 1/2 6) and (2 (1/2 1/2 + 6). Then direct calculation implies that
n0, (-18) = max no no (s, ))} = 0.5ma 0 A),
2
m5 m-10) = max (0, na
(12(0,)) (0,700 -)} =0.5ma (12(s,,) A),
where À 0.5 - ' Note that 2x (ulle) +1= Eusalu(a))/vvo)) and x² Dy. we obtain
that A f,
BubOpt,(f(.(b)). Subop(,((((b)))
(E.4)
20
= (r + (72 (-1ss)
T (;(s)) (ri(s, :) + +rr A.(ss) + 2n 2mx (f (-1s)
- (- (-|s)
a ( (1)((
> 2(rr(s,))))) ), क (-))) - 1 2n 1 (T)sss (+|s)
1 2900 a
762 no2
(E.5)
a
Now take expectation over all possible contexts and recall that -lu-vllll S/2 for + v', know that for any rı # r2 G
n62
(R; + SubOpt(#;rr)) 2
2a
Given any mean reward function r E G, let P, be the distribution of (s, a, r) when s ~ Ps a ~ re (-Is), and r Bern(r(s, a)). Suppose PD. is the distribution of the dataset given mean reward function then KL (Po., (PP..) nKL (Pr, Pr.)) for any pair of r1,72 E G. Now we invoke Fano's inequality (Lemma H.2) to obtain
7182
max KL (Po,, [PD,,) ) log
inf sup (u;Opt(F;inntt ins
1
4a
log [
1/82
64n82 + 8 1llog2
1
4x
where the second inequality holds due to KL(Bern(p) (Bern(())))) S (p 2)2 -))] Let 8
16 16-1vSm then we obtain that for all π we have
sup SubOpt inst) 2 n EnB
an
which finishes the proof in that log, |g| = S.
F GENERALIZATION TO CONTEXTUAL DUELING BANDITS
In this section, we extend our algorithm to the problems of regularized contextual dueling bandits, where the learner receives preference comparison instead of absolute signals. Our setup largely follows Zhu et al. (2023); Zhan et al. (2023) and the notion sub-optimality follows Xiong et al. 2024) Zhao al. 2024
27

---

Published as a conference paper at ICLR 2026
Algorithm 3 Offline KL-Regularized Pessimistic Contextual Dueling Bandit (KL-PCDB)
Require: regularization 7/ reference policy n- function class g, offline dataset D
((8;, a a D:)}
1: Compute the maximum likelihood estimator of the reward function
ys log (19(5), at) g(5,, -(5),,))) + (1 -v: o ( a²) g(s), a])l]]
g argmin gEg
2: Let O(s. a) = ((s (s a). where (n a) is the bonus term in F.1
Ensure: T(als) re (als) exp (1 a))
F.1 PROBLEM SETUP
We still consider contextual bandits (S.A, r, π ref) where S is the state space, A is the action space and r x A -> [0. 1] is the reward function But only relative preference feedback is available, viz., we have an i.i.d. offline dataset 'D = {ss, of af. ys ) where s; E S is generated from distribution P and a._ af ~ T The binary preference label = 1 indicates a, is preferred over of (denoted by
-²) and 0 for 2 > al given context s. In this work we consider the Bradley- -erry Model, where Ply = 1|s.a', aa²] link function. The objective here identical to (2.1) for KL-regularization and (3.1) for f-divergence
ar((s;, a.) r(s;, r();,,))), where (xx) = (1 + e->)- is the
regularization. Our goal is still to find an e-optimal policy. To control the complexity of the function class G, we assume that Assumption 2.1 still holds here.
Concentrability. Analogous to Section we need our estimation from offline dataset generaliz- able to the state-action pairs visited by our obtained policy. While density-ratio-base rasdo-beedd concentrabil- ity can be directly adapted to dueling bandit, we need a slightly different notion of D2 -iveergeenc.. This is because in dueling bandit, we cannot observe the absolute reward and best estimation we can achieve that for any state 8 and actions a at,a², our estimated g(s, a²) g(s, a²) R r(s, a r(s,a" a²). This implies that there exists some mapping b S + [-1, such that g(s, a) b(s) = r(s, a) on the offline data, which leads to the following definition.
Definition F.I. Given a class of functions G (S A + R) and some policy म, let B (S []) be the function class, define the Di-divergence ((s,
(o(s.a) - h(s a) b(s))² b(s))
sup inf g. DEB Egeu Vara 0 a') h(s' a')]
A similar definition has been introduced in Zhao et al. 2024 Definition 2.6), which underpins the following two assumptions that characterize the coverage ability of , similarly as in Section 2
Given a reference policy -e we define two coverage notions for contextual dueling bandits. Assumption F.2 (All-policy concentrability). D == SSP D8 a); ref) < oc.
Assumption F.3 (Single-policy concentrability). D := ((x,)))xx DD' ((s, a); md) < oo.
Similar
concentrability assumptions have appeared in previous work in offline contex- tual dueling bandits (Huang et al.) (025b]] (Song et al. (0244) and similar notions has also appeared in the analysis of model-based RL (Uehara & Sun 2021 Wang et al.) 2024). Still, while Assump- tion F3 is strictly weaker than Assumption R2 in general cases, the two quantities, CF and D2
cannot be bounded by each other.
F.2 ALGORITHMS AND RESULTS
F.2.1 ALGORITIMMS FOR KL-REGULARIZED CONTEXTUAL DUELING BANDITS
We elucidate KL-PCDB for offline Regregulard contextual dueling bandits, whose pseudocode is summarized in Algorithm 3 KL-PCDB first estimate the ground truth function g" on offline dataset
We overload some notations in Section by their dueling counterparts for notational simplicity.
28

---

Published as a conference paper at ICLR 2026
Algorithm 4 Offline f-Divergence Regularized Contextual Dueling Bandits (S-CDB)
Require: regularization 7/ reference policy n- function class g, offline dataset D {(s;, a a 3t) 1: Compute the maximum likelihood estimator of the reward function
ys log a (lo(s;,a)) at)) g(st, a2)l) (1 v:) a [g((s, (
g(s), at))]
g argmin geg
2: Compute the optimal policy with respect reward g
7--1s) +
argmax Σ
(alss){(s,a) + (((()())
(())))EA(A) aEA
Ensure: i(als)
with maximum likelihood estimator (MLE) to estimate function 9 E G. After that, analogous to Algorithm[] [I] we adopt the principle of pessimism in the face of uncertainty. Specifically, we define the penalty term
(n B.
3 D)((s,
(F.1)
where
B² = 128 log (2.()))))))) + 18E, = Ō(n
(F2)
and then subtract it from the MLE 9 to obtain a pessimistic estimator g. KL-PCB then output the policy म, maximizing the estimated objective
π (a|s)
[(T) = B(s.a)~pxx a) - log
re (a
the maximizer of which is in closed form the counterpart of (2.2)
(als) re (als) exp (n as)
We provide the following theoretical guarantees for Algorithm
Theorem F.4. Under Assumption F3 if we set H, according to then for sufficiently small
e E (0, 1). with probability at least 1 6, n = ( A C is sufficient to guarantee the output policy 2 of Algorithm 3 to be e-optimal.
Remark F.5. Zhao al.
2024) achieved an Ö(e-1) sample complexity under Assumption F.2
Comparing to Zhao et al.
2024), KL-PCDB achieves the same ((e sample complexity but only
requiring Assumption
which is weaker than Assumption F2
The following theorem provides the sample complexity lower bound for KL-regularized dueling contextual bandits.
Theorem F.6. For any sufficiently small (0, 1), 0, 1.15 C* S exp(n/2)/2, and any algo- rithm Alg, there a KL-regularized contextual dueling bandit instance with single-policy concentra- bility C < C such that Alg requires at least 2 min(n]C* log Ng((N)) log No (222)))))) samples to return e-optimal policy.
Remark F.7. Theorem F.6 shows that when is sufficiently small, any algorithm for offline KL- regularized contextual dueling bandits requires at least 2(1 log Nog.Ng(e (e)e (c)6-11)) samples to output an e-optimal policy, which matches the sample complexity upper bound in Theorem F.4 indicating that KL-PCB is nearly optimal.
F.2.2 ALGORITHM AND RESULTS FOR F Í-DIVERGENCE REGULARIZED CDBS
We present an offline learning algorithm for f-divergence regularized contextual dueling bandit, J-CDB, in Algorithm 4 J-CDB first leverages maximum likelihood estimator to find function
29

---

Published as a conference paper at ICLR 2026
E G that minimizes its risk on the offline dataset. Then the algorithm constructs the output policy that maximizes the f-divergence regularized objective induced by g. Similar to Algorithm do not require any pessimism in f-CDB. The following theorem provides upper bound of Algorithm 4
Theorem F.8. For any sufficiently small e (0,1). and 17, a O, with probability at least 1 6, n = 1n ((())) sufficient to guarantee that the output policy मे Algorithm is c-optimal.
The following theorem provides a lower bound for offline f-divergence regularized contextual du- eling bandit with strongly convex f.
Theorem F99. For any E 1), a, > O, and offline RL algorithm Alg, there is an a-strongly convex f and f-divergence regularized contextual dueling bandit instance such that Alg requires at samples to return e-optimal policy.
least a
Remark F.10. Theorem F.9 indicates that, when e is sufficiently small, to produce an e-optimal policy, any algorithm for offine f-regularized contextual bandits with strongly convex f requires at least a(a (aae"mne))) samples. This lower bound matches the sample-complexity upper bound in
Theorem F88 indicating that Algorithm 4 is nearly optimal.
G MISSING PROOF FROM APPENDIX
G. PROOF OF THEOREM
The proof follows the proof in Section
At the beginning, we first define the event E(5) given
5 > 0 as
{()) =
S ((s,s, b(s) (s. S sTa(s,a))
(G.1)
Here, In is defined in F.1 We abuse the notation and define b(-)
argmin
sup B (x.))ESxA
$b(5, a) rn (s.
(G.2)
where (b(s, a) (0(s.a) - b(s) (s.aa) a) and when E holds, for all (s. a) 8 x A, we have $5(8, () < (s, a) This indicates that the least square estimation ğ obtained in Line 1 of Algo- rithm 3 after adjusted by some bias function 6, is close to the true function g". The following lemma shows that this event holds with high probability.
Lemma G.1. For any > 0, ())) 2 8.
Proof. From Lemma H.I we have that with probability at least 1 8, holds that
Egtrop Var. ( [ø(s', a') g5'(s' s o Log(No(E.)/O)++e +ea).
(G.3)
further holds true that for some b
((,, a), n r) Baep Var Vara- (+1s) [T( g" (s) 2 (g(s. a) - b(s) 00 (),) (G.4)
Substituting (G.3) into G..). we have
inf (ā(s, a) b(s) g" (s, as)
(G.5)
(ō(s, b(s) 9" as)
inf Egaup Var (181) g0ss' a') - ge (s', d') Esino Varaw [g((s'a')) (s',
< <D}((s, a), ग Tf Eggr (g((s bb(s) - (s, (s)
(G.6)
< n - 0 Log(Ng(e.)))) + Ec
(G.7)
where the first inequality holds due to the definition of D3((s, (, a), Teff and the last inequality holds due to Lemma
H.T
30

---

Published as a conference paper at ICLR 2026
We overload the following quantities. For any y [0, and (s, a) E 8 x A, we define gy a) == > - b(s)) + (1-10 (1-7)g" (s,a),
Furthermore, we introduce the following quantities
7 To, (+1+) x n (-I) exp (ngg( (s-)), G( = Epxn, [@ a) - b(s) g" (s, (s.a))
where b(-) is defined in G.2p. We still have the monotomicity of the function G(y), which is char- acterized by the following lemma.
Lemma G.2. On event (()), 0 E arjm G(7).
Proof. For simplicity, we use A(s, a) to denote ((s.a) b(8) (* a) in this proof. Then on event E()), we know that (ss, a) I 0 for all (s,a) E S x A. Taking derivatives of G w.r.,, ? directly, we conclude that for all y E [0, 1].
G7(n) = nEE (s ( - E (ss
T =n En, (s, - Ex, ( a) En,, ((),a))
< 0,
where E, is the shorthand of Expp E,, is the shorthand of Eawn, and the inequality holds condi- tioned on the event {6) due Lemma 2.15
Finally, we have the proposition that adding some bias term b - does not affect the resulting policy.
Proposition G.3. Let b S - R be some bias function, then for all E G we have J(Fg) J(ng-b), where (g ())s, a) = =g( b(s).
Proof. For any fixed state E S, we have for any a E A that,
(als) (ng(s,
Tg Tg(a|s)
ExEE ot (a'ls) exp (ng(ss, (n)))
(als) exp (ng a)) exp (-nb(s))
Enee reef (a'ls) exp (1gg 8, a')) exp (-njb())
(als) exp (vig(s, a) b(s))
Eves ntef (a'ls) exp (nlg(s, b(s))
{s-s(a
which indicates that my Fg b- This immediately leads to J J (T
Now we are ready to prove Theorem
Proof of Theorem F4 We proceed the proof under the event E()). By Proposition G.3 we know
that
J(m")- - J(x") J (mrg)
= =J("") - J ( b).
Consequently, there exist some 7 E [0, 1] and b: S + [-1, such that
J(TT) - ((T) = J(x") - J(Tggbb
I nYxx, [ a) b(s) g" as)
-
(G.8)
31

---

Published as a conference paper at ICLR 2026
1 where the inequality holds due to Lemma 2.14 Under event E(6), we know that ((s a) b(s) g" a). Together with Lemma G.2 we obtain G(y) I G(O). Therefore, we know that
[(x)) - J()) - G(
(G.9)
= pxF (0(s,a) - b(s) g((,,a))²
4n Exxx- [T)(s, a c Exxr [[[(s, a) - b(s) - b(s)-((s())))) -s,,a)))))
= Anl Bpxx ()((s n C Bpx= [@(ss a) - b(s) g (s, a))²1) "
(n log (((c)m
(G.10)
where the incquality holds due to the definition of (6). Plugging G.10 into (G.8). we know that
J(x") ( has upper bound Ö(D.. ))). By Lemma G.1 event & with probability at least 1 - 8, which concludes the proof.
G.2 PROOF OF THEOREM F.6
Proof of Theorem F.6 The proof is similar the proof of Theorem 2.11
Consider the following
family of contextual dueling bandit instances with S = |S) = A oc and reward in some
function class G.
CDB = A(S,
A(A
(G.11)
Fixing any $ 1, 4 log? 2 and C E (2, exp( aim prove that, for any estimator D + मे E ((ASS), for any n 2 16SC*, there exist some function class G, such that 3 inst = (S, A. p, ",,,,,,,er,, 11 E CDB with single-policy concentrability C C", regularizzation coefficient
n, S| = S 6(log (9), and
inf
SubOptRKI. (2; inst) 2 min(nSC"n (SC"))
(G.12)
instECDB
Since log [9] 2 Ng() for any e E (0, 1). the above bound yields the desired result.
We construct the same reward function class in the proof of Theorem 2.11 In particular, we set = [S], A = [+1], p = Unif(S), and the reference policy to be
Vs S, / (-1|s) C- π (+1ls) =1 =1-
where C = C**
Then the total sub-optimality of any π E A(A[S) given any reward function
S:S x A A
1 Σ SubOpt (T(1)))))))
SubOpt (T;T) = 5
(G.13)
We further let = 1o & C exp(naa). We construct 2 Bernoulli reward functions, in particular, Vr E {+1] the mean function r, the reward (indexed by T) is defined
(s, -1) = 0.5 + (,,, +1) 0.5
Then, following the derivation (.12) and D.13 we know that Vs e S, VT, e {+1} with ~
35
(a:0pt,(f:7)) SubOpt,
^
(G.14)
10"
Let P. be the distribution of (s, a a,.aaaa,u, .y2 for ~ a. a² i.d.
(-|s) and (e))
r(s, a² a))).. Now we set 8 = /S/n and conclude that for 7 ~ 7' with -
KL (P., IP.r,))
(C- (C-
Σ
KL KL (Bem(((((=(())))) - r(s', ((s'sa²)))))
SC
"'aa'.a?
2(C -1)
[K (Ber((a + Bern(rrf 8))) V KL (Bern(o 6)) Bern(o + +d)))
S
32

---

Published as a conference paper at ICLR 2026
Since a, 8 (0.1/2), by the fact KL(PIIQ) x 2Q TV (PIIQ)² (see e.g., Polyanskiy & Wu 2025 Section 7.6)), we know that
KL (Pr, 1P,t)) - 2(C-11 11
SC 1+ expla + 6) 1 expla -) 1 1t explp(a + +8)
exp(2a)(exp(0) (d) exp((-0))²
$ 3SC
(1+ explap -8))
4e
(exp(6) exp(-x))
3SC
3 365 C-
(G.15)
where the second and third inequality hold due a, - 1/2, and last inequality follows from exp(=)-exp(-2)) I 3x for I [0. 1/2]. Now we set SSC/n 1/4. We substitute (G.14)
into Assouad's ss Lemma (Lemma H.3 and obtain that
1
n82
38
min exp ( - KL (Pp,1lPp.) Tut
inf inBtECDB
SubOptRkL (i; inst)
S
5
8
10
162
nKL (Prr (lrrop
exp
4
8
10
exp(-36)
min min(n Cs
32
where the 1/S comes from the denominator of G.13 and second inequality follows from (.15
G.3 PROOF OF THEOREM F.8
Proof of Theorem E.8
The proof similar to the proof of Theorem 3.2 Recall that b(+) defined
in G.2
we know that
म argmax ((ss))-xx(((ss.0 a)] 1170)--17111 " [' (T)(
argmax ((x.,))xxx (o(s.)) b(s)] - ' DD (T][ REAM
We have the following sub-optimality decomposition
-(x²) - J(T)
Eguu Bane (s,, Ba ( (g" (s) - 17 [T)(T")| Dy 1
E Egupl (g'"") H (7.g" - g b)
Exupl Hg'g") Hī b) - (VH: b).g - + b)
= Ee [gg g b) V' b+b]].
1 (s) a) g(s, a) b(s) and the last equation holds due to Taylor's expansion. Now, for any E (0 and e. 0. with probability at least 1 -
where ÿ = 7 + (1 7) and 7 E [0, 1). (g
J(TT) J ( = Esppl(g 6) v v - + b)]
< nEnp (g" ( b) diag ( (a1 [s),
x. - (aals)) ++b) b)]
I (1 of [00
g(, a) + b(s))
128
< a in
log 2Ng (2)g(cc) + 18c,)
3n
where the first inequality holds due to Lemma E.4 and last inequality holds due to equation G.3 Setting 6, O(n-1) completes the proof.
33

---

Published as a conference paper at ICLR 2026
G.4 PROOF OF THEOREM F.9
Proof of Theorem P. We still consider the contextual dueling bandit instance class defined in [G.II. We show that given any positive a, for any 2 S. max 17² 2), there exists
f: R such that f a-strongly convex, log |g] (S) and
sup SubOptzaiv (f; inst) 2 n a RE insE
inf
(G.16)
an
where D = {(8,, at af. from which ((AA)) is denoted by [I(D). Since S (llo [+]) Z log.Ng(E.) for all 6, (0, we can conclude the theorem.
J= is the offline preference dataset, all (possibly randomized) maps
Let S [S]. A {+1}, p Unif(S) and nhd (-Is) (nif(A) for any S. Then the total sub-optimality of any π E ((A[S) given any reward function r S x IR is
1 Σ S
SubOpt (T;))
SubOpt ( (T(-1s):r(s.)))
(G.17)
We still consider the reward function class indexed by {=1}8. For all {+1} the reward instance "shaped" by r is
(s + aT,
(G.18)
where at, = +1 because E A {=1}. We thereby refer t ~ T' to any pair in {=1}$ that differs only in one coordinate. VT, {+1]s if T', then suppose Ta -T we have
n
SubOpt jav (
au (T(
(G.19)
an
where the inequality follows from exactly the same calculation in equation
E.5 by setting f(x)
Let Pr be the distribution of (s, a², y)) for P. a a² y (ern(a a') r(s,a?))) Then we denote 5 v S/n and conclude that for I' with
(I 1)3/2 /2
iid.
x (-1s) and
Ts T.
KL (Pr. (Pr,,)
Σ (L r(s'r (1 r(s',a²))
SA²
s',a'.
KL (Bern(a (er(()))))) + KL (Ber((((-26)) (ern)) (22)))
45
1
< (exp(-20) (25) 1) (exp(25) 1)²)
45
3682 18
< 25
(exp(20) - -1)² < 25
(G.20)
where the last inequality follows from exp(x) assumption. Therefore, we substitute (G.19 into Assouad's Lemma (Lemmal H.3) to obtain
3r for 0.,) and 5 /S/n 0.25 by
LHS of G.16)
min exp S am rap!
1
S S
(-KL KL (Po, (Po.))
0.25
S
exp (-nKL nKL (
(Pr.IIPro,,) ))
an exp( >
S
S an
(G.21)
an
where the 1/S comes from the denominator of G.17 and the second inequality follows from G.20
Recaal that in this Dy x², where (xllv) Encalu(a)3//(o))
34

---

Published as a conference paper at ICLR 2026
H AUXILIARY LEMMAS
Lemma H.1 (hhoo et al. 2024 Lemma D.4). Consider offline dataset {(s;, a3, at vi)) gener- ated from the product of the context distribution p E (S)), policy a E A(A[S), and the Bradley- Terry Model defined in Appendix F.1 Suppose 9 is the result of MLE estimation of Algorithm 3 and we further define b(s) have
-9" Ba s) g(s,a) - g" (s. a)]. then with probability at least 1 26, we
E xa [[] a) g0 b(s)) 0o
Nog((o(
n2
Lemmas H.2 and H.3
standard reductions (Le Cam 1973 Yu
1997
Polyanskiy & Wu
2025).
See, e.g..
Chen et al. (2024, Section 3) for a general proof.
Lemma H.2 (Fano's inequality). Fix any R = {ri, rss and policy class II. let L R Ry be some loss function. Suppose there exist some constant >> 0 such that the following condition holds:
min min [[T + L(x,r,) 2c. *g xell
Then we have
+ KL(Pr, (P,,) log
inf sup RupD,, (x)(),,)) xell PeR
log 5
where the trajectory distribution of æ interacting with instance r E R. denoted by P,. Lemma H.3 (Assouad's Lemma). Let R be the of instances, IT be the of estimators, 2 {=1} for some S > 0, and {4ك} be S functions from II x R to R,. Suppose {re Jeee C R and the loss function is
S L(T,)) = Σ v(T El 5=1
We denote m 6' they differ only in the j-th coordinate. Further assume that
ari 0' inf Lo( [T( 2
(H.1)
mell
for some then
inf sup ED L xell FER
min exp (- KL (Pro IPro.)) 35:0~,0
where the trajectory distribution of æ interacting with instance r R is denoted by P..
The following Lemma H.4 is due to Gilbert 1952 coding theory.
Varshamov 1957). which is a classical result in
Lemma H.4. Suppose a set of characters with |Σ| = q where q 2 2 prime power and N is some natural number. Then there exists subset 1 of V such that (1) for any o' E V, # ey one has d (v, v') 2 N/2 and (2) log, |V| 2 (1/))) = @(1), where d the Hamming distance and the entropy function H is given by
H (x) = log(q - 1) log x - (1 x))
log - x)
logq
logq
log
For example, when g 2, this means that there exists a subset V of 11,, 1]$ such that (1) |V] exp(S/8) and (2) for any v, o V.,0 + bj one has ||v - w'|l1 | 2 5/2.
35


Reviews:
[{"review_id": "M7hWy2gXwW", "reviewer": "Reviewer_3Ln2", "summary": "The paper studies the sample complexity of regularized policy optimization with general $f$-divergence regularizations in contextual bandits. For the special case of KL-divergence regularization, the authors derive an $\\mathcal{O}(\\epsilon^{-1})$ upper bound when the reference policy provides sufficient coverage of the optimal regularized policy. They further present a matching lower bound, up to a coverage parameter, that depends on a weaker density-ratio coverage of the optimal regularized policy, indicating that some coverage assumption is necessary for efficient learning. Finally, for $\\alpha$-strongly convex function divergences, they establish a minimax-optimal sample complexity that does not depend on any coverage parameters.", "questions": "1. The coverage term of lowerbound is bounded by $ \\min( C^{\\pi^\\*}, \\mathcal{O}(\\exp(\\eta) )) $ in Theorem 2.11. Similarly, the coverage term of sample complexity of Algorithm 1 can be bounded by $ \\min( D^2_{\\pi^\\*}, \\mathcal{O}(|S||A|\\exp(\\eta) )) $. Can this be improved to $ \\min( D^2_{\\pi^\\*}, \\mathcal{O}(\\exp(\\eta) )) $?\n2. Have the authors tried to show similar upper bound for $f$-divergence-regularized CB when $f$ is only locally strongly-convex by adding an appropriate bonus term similar to Algorithm 1?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Relaxation from all policy coverage to optimal policy coverage assumption with clever use of pessimistic bonus term\n2. The lower bound of Theorem 2.11 has a multiplicative coverage term, showing some coverage assumption is needed for any efficient algorithm\n3. The work shows that for $f$-divergence-regularized objectives, if $f$ is strongly convex, then no coverage assumption on the reference policy is necessary.", "weaknesses": "1. The worst-case gap between $C^{\\pi^\\*}$ and $D^2_{\\pi^\\*}$ scales as $|S||A|$. This linear dependence on the size of the state space can render Algorithm 1 inefficient, even when $C^{\\pi^\\*}$ is a constant. A more detailed discussion or empirical illustration of how these two coverage measures relate in practice would strengthen the paper.\n2. Theorem 3.4 constructs only a specific instance of an $\\alpha$-strongly convex $f$ (a scaled $\\chi^2$ divergence) that matches the upper bound, rather than establishing a general $f$-dependent lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "JtQbqmN3fJ", "reviewer": "Reviewer_8QC9", "summary": "The paper investigates the theoretical offline reinforcement learning with general function approximation. They provide sharper lower and upper bounds with a proposed KL-divergence-regularized simple algorithm, where they also prove single-policy concentrability is efficient and necessary. Also, they investigate the f-divergence-regularized algorithm, which can converge normally without coverage assumptions. The results are very novel in this area. A few experiments are conducted to corroborate their theoretical results.", "questions": "1. Could you provide more intuition for Lemma 2.14? It appears central to your KL-regularized algorithm. Also, this technique seems to originate in prior work—can you clarify the differences in proofs between this one and the previous one? \n2. For the f-divergence regularized algorithm, is my understanding in the weakness correct? If no, please justify it. If yes, please elaborate a little more about what is the potential impact or benefit of it.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written. The story is clear and consistent.\n2. The contributions should be solid. a) The f-divergence could provide another way to understand the requirement for offline learning. b) The refined mean-value-type risk upper bound has some technical improvements.", "weaknesses": "1. The results in the f-divergence algorithm are not compared with the global optimal policy, which is not the same as the KL-divergence. In other words, it seems to replace the coverage assumption with another assumption that the global optimal policy is the optimal policy they defined in 3.1. It is still an important contribution, but it may be overstated.\n2. The numerical experiments are very simple, more like a sanity check rather than a validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Sq2nqOICeO", "reviewer": "Reviewer_8Rei", "summary": "This paper provides a tight statistical analysis of offline contextual bandits with f-divergence regularization, focusing on the widely used reverse KL and on general strongly convex f-divergences. The authors establish the $O(1/\\epsilon)$ sample-complexity results under single-policy concentrability for reverse-KL-regularized objectives, A novel pessimism-based proof technique is used by leveraging the curvature of the reverse-KL objective and a moment-based lemma. For strongly convex f-divergences, the authors further show that the same rate can be achieved without any coverage assumptions, supported by a matching lower bound and simple empirical verification.", "questions": "The paper mentioned that for strongly convex f-divergence, we do not need the data coverage assumption. I am wondering if we use the local convex f-divergence, can KL analysis be applied for this case? Or there is a fundamental challenge here.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper established a near-optimal sample complexity for offline regularized bandits.\n2. The moment-based argument and integration of pessimism with curvature properties seem novel in offline bandits.\n3. The extension to strongly convex f-divergences provides a unified theoretical view.", "weaknesses": "1. Experiments are limited. Only toy two-armed-bandit cases are shown, perhaps including some real dataset would strengthen the arguments.\n2. The paper seems to put more effort on introducing the analysis for KL-divergence regularized Bandits, while the title suggest general f-divergence. Perhaps including discussions on how to handle general f-divergence regularized bandits would make the main body match with the title.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Gwf9OhVkfp", "reviewer": "Reviewer_gwK9", "summary": "This paper provides a sharp theoretical analysis of offline contextual bandits under f-divergence regularization, a class of objectives underlying many modern offline RL and RLHF algorithms. The key contribution is a refined characterization of the sample complexity required to find an ε-optimal policy with respect to the regularized objective, rather than the unregularized reward.\n\nFor the reverse KL divergence, the authors prove an Ō(ε⁻¹) sample complexity under single-policy concentrability—strictly improving those requiring stronger all-policy coverage assumptions. They also provide a matching lower bound showing that the dependency on the single-policy concentrability coefficient is necessary.\n\nFor general f-divergences with strongly convex f, they establish that the same fast rate Θ̃(ε⁻¹) is achievable without any coverage dependence, supported by both upper and lower bounds. The analysis leverages a novel moment-based argument that couples pessimism with the curvature of the regularized objective, providing a new proof technique beyond the standard performance-difference or simulation-lemma analyses.\n\nEmpirical results on two-armed synthetic bandits corroborate the theoretical rates and demonstrate distinct scaling behaviors between KL and strongly convex f-divergences.", "questions": "- $\\pi_{\\gamma}$ in the LHF of the equation in Lemma 2.14? \n- I don't understand Lemma 2.14, does the lemma hold for every $\\lambda$, for for some $\\lambda$ ($\\exists \\lambda$)? \n- How critical is the assumption that the behavior policy equals π_ref? Would the same rates hold when π_ref differs from the logging policy?\n- For the χ²-regularized case, could you provide intuition or experiments showing the trade-off between strong convexity (α) and the bias introduced by over-regularization?\n- Could your analysis provide insights into why KL regularization remains dominant in practice despite its stronger coverage requirements?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Sharp and rigorous theoretical results: The paper achieves the first tight sample complexity bounds for offline f-divergence-regularized bandits, closing important gaps in the literature. The improvements—from stronger coverage assumptions to Ō(ε⁻¹) under single-policy coverage—are both technically and conceptually relevant.\n\n- Broader generality beyond KL: Extending the framework to strongly convex f-divergences (e.g., χ²) and proving that fast rates can be achieved without any concentrability assumptions is conceptually strong. It clarifies how curvature of the regularizer directly impacts coverage requirements.\n\n- Balanced theoretical and empirical validation: Although simple, the experiments convincingly verify the predicted n⁻¹ scaling and the absence of coverage dependence for strongly convex f. The theoretical lower bounds are also near-matching, strengthening the claims.\n\n- Relevance and timeliness: The results have clear implications for RLHF, offline RL with KL or χ² regularization, and policy optimization under limited coverage, making the work both theoretically rigorous and practically relevant.", "weaknesses": "- The experiments only involve two-armed synthetic bandits. Although sufficient to verify scaling, a richer empirical study (e.g., linear contextual or synthetic high-dimensional bandits) would strengthen the practical credibility.\n- Som part of the writting is unclear (see questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)