Fine-tuning Behavioral Cloning Policies with Preference‑Based Reinforcement Learning
Authors: Mael Macuglia
Paul Friedrich
Giorgia Ramponi
Venue: ICLR 2026 Poster (2026)
Keywords: Behavioral Cloning
Preference-Based Reinforcement Learning
Reinforcement Learning
Primary area: reinforcement learning
TL;DR: We show theoretical guarantees & experiments for a novel two-stage reinforcement learning method that first learns an optimal policy estimate from an offline, expert dataset, and then refines the estimate via online preference-based human feedback.

Abstract: Deploying reinforcement learning (RL) in robotics, industry, and health care is blocked by two obstacles: the difficulty of specifying accurate rewards and the risk of unsafe, data-hungry exploration. We address this by proposing a two-stage framework that first learns a safe initial policy from a reward-free dataset of expert demonstrations, then fine-tunes it online using preference-based human feedback. We provide the first principled analysis of this offline-to-online approach and introduce BRIDGE, a unified algorithm that integrates both signals via an uncertainty-weighted objective. We derive regret bounds that shrink with the number of offline demonstrations, explicitly connecting the quantity of offline data to online sample efficiency. We validate BRIDGE in discrete and continuous control MuJoCo environments, showing it achieves lower regret than both standalone behavioral cloning and online preference-based RL. Our work establishes a theoretical foundation for designing more sample-efficient interactive agents.

Published as a conference paper at ICLR 2026
FINE- BEHAVIORAL CLONING POLICIES WITH PREFERENCE-BASER REINFORCEMENT LEARNING
Maël Macuglia' Paul Friedrich 1,2 Giorgia Ramponi'
1 Department of Informatics, University of Zurich, Switzerland
2 ETH AI Center, Zurich, Switzerland mael www.aacllli... ialllllld@iiouu com, {paul friedirriddrch, gaorgia.ramponi
ABSTRACT
Deploying reinforcement learning (RL) in robotics, industry, and health care is blocked by two obstacles: the difficulty of specifying accurate rewards and the risk of unsafe, data-hungry exploration. We address this by proposing a two- stage framework that first learns safe initial policy from reward-free dataset of expert demonstrations, then fine-tunes online using preference-based human feedback. We provide the first principled analysis of this offline-to-online ap- proach and introduce BRIDGE, a unified algorithm that integrates both signals via uncertainty-we weighted objective. We derive regret bounds that shrink with the number of offline demonstrations, explicitly connecting the quantity of offline data online sample efficiency. We validate BRIDGE in discrete and continuous control MuJoCo environments, showing it achieves lower regret than both stan- dalone behavioral cloning and online preference-based RL. Our work establishes a theoretical foundation for designing more sample-e efficient interactive agents.
INTRODUCTION
Deploying reinforcement learning (RL) (Sutton & Barto 2018) physical robots, industrial processes, or healthcare remains notoriously difficult for two reasons. First, exploration is both risky and data-hungry (Dulac-Arnodd al.] (019): A policy that begins from seratch can damage hardware, or user trust, long before gathering enough experience to learn. Second, reward mis-specification: even experienced domain experts often find it hard translate informal task goals into a correct and safe numerical reward signal (Leike et al. 2018).
A promising solution addresses both challenges simultaneously: It combines reward-free expert demonstrations with online preference- brasee feedback, allowing practitioners to leverage safe im- itation learning while enabling corrective refinement through simple comparative judgments. This hybrid approach has achieved remarkable empirical success across domains. It is the core technique behind modern dialogue agents like ChatGPT, which is first trained to imitate curated demonstra- tions of desirable responses and then fine-tuned via RL from human feedback (RLHF) (Ouyang) jet al., 2022). Similar approaches have achieved near-expert performance complex games like Atari and control tasks like MuJoCo (Christiano al. 2017) and enabled safe weal-world robot ma- nipulation by ranking tele-operated clips before on-hardware fine-tuning (Brown et al., 2020). Our reward-free setting is distinct from related line of successful work that also pre- poe-trains offline but
assumes access to ground-truth reward signal for online fine-tuning (Nair et al. 2020 Kostrikov
al. 2022 Tang et al. 2025 Park al. 2024 Tirinzoni et al.) 2025).
However, despite its widespread practical success, the theoretical foundations of rifline-to-online
preference learning remain unexplored. Existing theory analyzes either imitation leaming or preference-based RL in isolation. This leaves fundamental questions unanswered: How exactly do offline demonstrations improve online preference learning? What are the precise trade-offs between the quantity of offline data and the number of online queries? When is this combination provably better than either approach alone? This theoretical gap prevents a principled understanding of the method's ''s limits and leaves practitioners without formal guidance for designing such systems.
Code available wwt.ttp::/// httpiiheehhtteee/ttttoo..oo/////

---

Published as a conference paper at ICLR 2026
We provide the first theoretical analysis of this empirically important paradigm. We formalize the "offline imitation + online preference fine-tuning" setting and develop rigorous regret bounds that quantify how offline expert data reduces online learning complexity. We introduce Bounded Regret with Imitation Data and Guided Exploration (BRIDGE) that achieves the predicted theoretical benefits in experiments on discrete and, extending beyond our theory, continuous control tasks. Our key contributions are:
algorithm,
The first theoretical framework for offline-to-online preference learning. We provide the first rigorous regret analysis for this approach. Our framework (Theorem 4.2) uses the Hellinger distance between trajectory distributions to construct confidence sets whose radii, O(1/vn), directly connect the quantity of offline data n to online learning efficiency.
A regret bound showing offline data reduces online regret. We prove that our algorithm, BRIDGE (Algorithm I) achieves an optimal VT regret dependence on the online horizon T, while explicitly showing how offline demonstrations improve online performance (The- orem 4. Our bound formally shows that as the number of offline demonstrations + oo, the online regret approaches zero, theoretically validating that high-quality offline data dra- matically improves preference learning efficiency.
We review related work on the affline-to-onlin paradigm in Section 2 and formalize our problem setting and regret measure in Section 3 We then present algorithm, BRIDGE, along with its
theoretical regret bounds in Section 4 Finally, we validate our theory with experiments on discrete
and continuous control tasks in Section 5
We show detailed experiments in Appendix A and all
proofs in Appendices B F
2 RELATED WORK
Imitation Learning. Behavioral Cloning (BC), pioneered by road-following systems like ALVINN (Pomerleau] 1988). learns policies from expert data via supervised learning. Recent advances in theory e.g. establish horizon-free sample complexity bounds for BC (Foster et al.] 2024). The DAGGER algorithm mitigates covariate shift at deployment time (when facing states outside the training data), with iterative expert corrections, achieving no-regret guarantees (Ross et al.) 2011] However, its reliance on a constantly available expert is often impractical. Our approach inherits BC's simplicity but replaces this online expert with preference-basee refinement.
Hybrid offline-to-online RL. Learning entirely online from a cold start is often sample-inefficient and (initially) unsafe. Our work fits into the hybrid paradigm, which avoids this by using offline data to warm-start a policy before online refinement, with early contributions including model- al- gorithms (Ross& & Bagnell 2012). This area has significant empirical progress (Rajeswaran et al.] 2018) Nair et al., 2018 Vecerik et al. 2017 Lee et al. 2022; Ball et al. 2023 and theoretical advances in statistical approaches to efficiently combine offline and online datasets (Song et al.) 2023) Wagenmaker & Pacchiano| 2023 Tang et al.] [002)). However, this entire line of work is fundamentally different from ours as assumes access
et al.
ground-truth re- ward function functtnnoton during online fine-tuning. For instance, prior theory shows that for non-expert offline data, pre-training offers no statistical improvement in this reward-based setting (Xie et al., [021). I) We show, in contrast, that offline expert data provides a provable statistical advantage when com- bined with reward-free, online preference- BRIDGE with modern preference- based fine-tuning approaches.
feedback. Appendix [A provides comparison of
In summary, prior imitation-only approaches lack robustness outside the demonstration manifold, while existing offline-to-online methods demand ground-truth rewards. Our work bridges these gaps by (i) proving that expert demonstrations plus a modest preference-query budget yield sharper regret bounds, and (ii) showing empirically that cifference-guideed exploration corrects for blind spots with far fewer risky interactions than pure online RL.
3 PROBLEM FORMULATION
We address the challenge of learning optimal policies by combining information from two com- plementary sources: offline expert demonstrations and online preference feedback. In this hybrid
2

---

Published as a conference paper at ICLR 2026
learning paradigm, first leverage dataset of trajectories collected from expert policy to establish strong priors over the policy space. Then, we strategically utilize these priors to guide an online preference-based learning process. where expert provides binary feedback comparing pairs of trajectories. This framework enables us to efficiently narrow the search space using of- fline demonstrations while refining our understanding of the expert's underlying preference model through targeted online queries. We aim to quantify how knowledge from offline demonstrations translates improved regret bounds in the online preference learning phase.
Finite MDP setting freward-free), Consider a finite-horizon Markov Decision Process (MDP) de- fined by the tuple MM- (S. A. P. H). where S is a finite state space. A is a finite action space, H E N is the horizon length, and P = {Pr (eeM represents the time-dependent transition dynam- ics, with Pa (-|s, a) denoting the probability distribution over next states given state-action pair (s, a) step h. A policy π heeth consists of collection of mappings TTA S + ((A), where (AA) is the probability simplex over actions. A trajectory state-action pairs generated by executing a policy π in the environment following dynamics P. We denote the space of all possible trajectories of fixed length H/ as TT We assume the trajectories have a continuous distribution with respect to the counting or Lebesgue measure. We will write 17,, for the density function of the trajectory distribution induced by policy and dynamics P.
{(s); on (n))aa [N is sequence of
Offinne demonstrations. We assume access to an offline dataset D = (Ti consisting of n in- dependent trajectories of length H, where each T; Pp.. This is imitation learning setting where trajectories are generated by an expert policy n² interacting with the true environment dynamics P".
Online preference queries. We formalize preference- based learning through feature embeddings and a probabilistic preference model (Christiano et al., [017]; (ahaa et al.] (023). We assume the existence of trajectory embedding function Φ 7 + IR that known the learner. The offline demonstrations capture raw expert behavior, while the known embedding function & provides the necessary structure for efficient online preference learning. The trajectory embedding function ø serves a critical purpose in our framework by enabling meaningful preference comparisons that would be difficult to perform on raw trajectories. This embedding approach provides a versatile framework that can accommodate various types of trajectory information. The flexibility of this representation allows our method to adapt to different domains and preference structures without changing the underlying learning algorithm. We define the policy embedding as the expected feature representation: of (T) = ET [d())
We adopt two commonly used assumptions, bounded trajectory embeddings (Saha al. 2023 Horker-Holder et al. (2020b) and bounded weight vectors (Filippi et al. 2010: Faury et al. 2020).
Assumption 1. We require (i) bounded features: [|ø(T)]l2 S B for all T E T and some known B < 00, and (ii) bounded weights: w" E E Rd ||u||2 S W) for a known W < co.
We measure the degree of non-linearity of the sigmoid (xx = (1 + + over the parameter space (where o' is the first derivative of σ) with == (0) (0) T=)
We use a Bradley-Tere model for the preference feedback. Given two trajectories 7 and 72, the binary preference outcome 01,2 E {0, }} is modeled as a Bernoulli random variable, indicating with 01,2 that r is preferred over 72, and vice-versa with 01,2 = 0:
P(7' > 72) ( = 1|r = =((_==) - (b(7)) w"))
This corresponds to latent utility model where the inner product (Ø(T), w*) represents the utility of trajectory т. We can extend this to policies, defining P(r'' > x²) = ((((T))) o(T²), w)).. This represents an expected preference over the distribution of trajectories, and captures the average preference when comparing behaviors induced by different policies. From this model, we derive score function for trajectories s(7) = (Ø(T), w*) and extend it to policies as s sP(T) = Er, [s(r))-
Offline estimation quality. For the offline phase, we measure the quality of estimation using dis- tributional distance metrics in the space of trajectory distributions. Specifically, we will construct confidence sets in the form of Hellinger balls around our estimated density policy and dynamics. Notably, the Hellinger distance relates directly to the L' norm between square-root densities, en- abling geometric interpretation of our confidence sets Euclidean balls in the space of density embeddings, with computational advantages over alternative divergences. The precise construction of these confidence sets and their properties is shown in Section 4
3

---

Published as a conference paper at ICLR 2026
Online regret. We quantify our online learning phase's performance through regret measurement. In each round t E [T] of online learning. the agent selects policies T; and n; receives binary preference feedback or {0, 1}, and accumulates regret measured against the optimal policy. We specifically use the pseudo-regret with respect to the policy class IT as in Saha et al. (023
T
22 (T)
(TT
W
2s (x*) - (s (TT) +
RTT
mnxx mell
2
2
All our performance guarantees will be expressed in terms of the MDP parameters (state space size {S] action space size |.A), horizon length H), offline data quantity n, online interaction rounds T, and confidence level 8 of the offline estimation establishing direct connection between offline data quality and online learning efficiency.
where n² arg man STT).
Notation. We denote [ = (1, (I, H3 for H E N. For probability distributions P.Q, (P, is the squared Hellinger distance and TV P, Q) the total variation distance. We denote as (0) = {o E Rd || S R3 the Euclidean ball of radius R, and define z == zr as the outer product.
BRIDGING OFFLINE BEHAVIORAL CLONING AND ONLINE PREFERENCE- BASED FEEDBACK
Our approach BRIDGE uses offine expert demonstrations to improve the efficiency of online pref- erence learning. The core idea to use the offline expert data to construct set in policy space that contains the expert with high confidence, drastically shrinking the search space for the subsequent online learning. This process contains three steps:
1. Offline imitation: We first use the offline dataset to learn an initial policy via Behavioral Cloning (BC), and transition model estimate via maximum likelihood estimation (MLE).
2. Confidence set construction:
Next, we construct a confidence set Noffiine centered on the BC policy in trajectory distribution space. We define the set as a ball the space of trajectory distributions using the Hellinger distance. This provides a clean geometric interpretation, namely a ball defined by single scalar quantity (its radius), and makes the theoretical analysis tractable. We prove that the radius shrinks at rate of ((I/vn) where n is the number of offline expert demonstrations. More offline data directly translates to a tighter ball and smaller, more focused search space for online learning.
3. Constrained online learning: Finally, we perform online preference- based RL, but with exploration constrained to policies that lie within the pre-computed Hellinger ball. This prevents the agent from exploring highly suboptimal or unsafe regions of the policy space.
This framework is illustrated in Figure [ implemented in detail in Algorithm experimentally verified in Section and supported by our main theoretical result. The following theorem formalizes the intuition that more offline data improves online performance by providing regret bound that explicitly depends on n. The full proof is found Theorem E.
gigh-probability
Theorem 4.1 (Main result: Offline data reduces online regret). Let n be the number of offline demonstrations from expert policy satisfying Assumption where Taain O is the minimum nonzero visitation probability under the expert policy's 's distribution. Then, with probability at least 1 - 8, the regret of BRIDGE is bounded by
(
Ry S δ
VT
T
log 1+
+
(1)
Tt
7min
This regret bound represents matches Saha et al. (2023), it now also depends inversely on the number of offline demonstrations n. Crucially, the regret vanishes as n + 3c, for a fixed T. This formally captures our claim that high-quality offline data can arbitrarily reduce the complexity of online preference-based learning.
theoretical contribution. While the regret's scaling in vT
'They show equivalence of the standard preference-based formulation up to constant factors, if B, W S 1.
4

---

Published as a conference paper at ICLR 2026
Algorithm BRIDGE: Bounded Regret with Imitation Data and Guided Exploration
Input: offline dataset TD no. of iterations T
2: Estimate ~, and P via MLE (Eqs. (2) 3 and compute confidence set 1 (Theorem 4.2
3: Initialize model P1 P. data matrix V1 ALa
4: for = 1,...., do
5: Compute w/ via constrained MLE (Equation
4
6: Define policy set 11, based -i and w (Lemma 4.5
7: (T) m t arg 2 {7t 11 (T)) 6e (x²3
B, 2 2W SWB, 5onkine) T8 pu and obtain preference 1(T) > -ř)
BT( 11 2W B, 8 gonkine)
8: Sample trajectories 7/ Ip
P.'
P.
9: Update matrix V(+1 <- V.+ (x)) 0² (m?)) and model P(+1
10: end for
11:
return Best policy from Il using final weight estimate w
proj
The remainder of this section substantiates these claims. We first detail the construction of the Hellinger-based offline confidence Section 4.1 and then describe how we link it the online
preference-leande algorithm that operates within this set in Sections 4.2 and 4.3) Section 4.4 gives
a proof sketch, and Section 4.5 discusses limitations and implications of BRIDGE's assumptions.
Offline Estimation
Online Preference Learning
Distribution Space P(T) (P7) ael
Policy Space II
PEP
polline
[|oflline
R
BC
BC
x
Hellinger ball around 1 P(T) confidence Iooillnne
Expert Preferences
Figure 1: Overview of the BRIDGE framework. Offline estimation derives estimators BC and P using the dataset DH and constructs a confidence set in trajectory distribution space P(7) as Hellinger ball (left). which translates the offline policy confidence set [ooillie in policy space II likely to contain n (middle). The confidence set IIfffline is then used to constrain the online preference learning phase (right), where policies are sampled from within this and presented to the expert for preference feedback.
4.1 STAGE 1: OFFLINE CONFIDENCE SET CONSTRUCTION
The goal of our offline phase is use the expert dataset DD to construct a policy confidence set Noffhine that is guaranteed to contain the expert policy n' with high probability (1 - 5). The key result of this stage is a computable confidence set whose radius shrinks with increasing amounts of offline data, which we formalize in the following theorem. The proofs of both this theorem and Lemma 4.4 are shown in Appendix C.4
Theorem 4.2 (Offline confidence set radius). Define constants a == /4-1S| logglog(())) 2/8) and = / 4- |||.. [A] log(nll 2/0). Under Assumption the policy set
Tolfiine = TT H2
Pa S Radius p.
a confidence set of level containing कt" with probability at least 1 8, where
a
B
(1 1 H (1+
2a
Radius
Vn
Fr
7min
/n
5

---

Published as a conference paper at ICLR 2026
This result provides the fundamental connection between offline data and online learning efficiency: the confidence set radius scales as ( vn) with the offline sample size n. As we collect more expert demonstrations, the confidence set shrinks, constraining the online policy search space more tightly. Since our online regret bounds will directly depend on the size this confidence set, this establishes quantifiable trade-off between offline data collection and online preference query effi- ciency, a key contribution of our work. We now detail the components required to construct this set. Relevant corollaries and their proof's are presented in Appendix C
Policy and model estimation. To construct the confidence set, we first obtain estimators for the policy and transition dynamics from the offline data, assuming realizability. We apply maximum likelihood estimation (MLE) on the expert trajectories D to learn the BC policy estimator n BC and the transition model estimator P.
Assumption 2 (Realizability). The optimal policy and true transition function belong to their spective function classes: π² E 1l and P P.
The BC estimator BC found via log-loss Behavioral Cloning (BC), and the MLE transition esti- mator P found similarly using Maximum Likelihood Estimation (MLE):
Σ
(a (a,, lsh)),
π
arg max well
$E|n] hE[M]
P
Σ iE(m]
Σ
[log(P(s++zlshh
arg max PEP
We provide concentration bounds for these estimators in Appendix C.3 which characterize their error in terms of the Hellinger distance 2
Bounding concentrability. A key challenge in using these estimators is that bounds depend on the unknown true dynamics Pt. To create a computable confidence set, we must eliminate this dependency. We do by bounding the concentrability coefficient, which measures the maximum divergence between the state-action distributions of an estimated policy π and the expert π². Commonly encountered offline RL literature (Chen & Jiang 2019), is defined as:
C (s,
C(xBC
n BC
sup (E(H]
sup (x..) (s.)ss dp. (s,a)
To bound this quantity without requiring broad data coverage, instead make mild assumption on the expert's 's policy structure.
Assumption (Expert policy concentration). The expert policy n" has a minimum visitation prob- ability Ymii > 0 for state state-actions it visits, i.e., min, (s.a.))
2 Vmin-
Intuitively, this assumption characterizes the expert's intrinsic behavior. A smaller Ymin corresponds to a more specialized expert with sharp preferences for certain state-actions, while a larger value implies more uniform visitation pattern. This contrasts standard assumption in offline RL of minimum dataset coverage across all state-actions (Levine al., 2020 Chen & Jiang 2019).
We can now bound the concentrability coefficient using only the Hellinger error R of our policy estimator and the expert's concentration pattern "Juin For the proof, see Appendix C.3.3
Lemma 4.3 (Concentrability coefficient bound). Under Assumption for policy estimator BC satisfying (PT .PT.) < R, the concentration coefficient is bounded by
PC
C( RC 5 2/R
Yiin
We present theoretical results for the standard setting of tabular state and action spaces, and finite policy classes II. While we leave full theoretical extension of our framework to the continuous setting for future work, show experiments and implementation for continuous MDPs Section 3 Appendix

---

Published as a conference paper at ICLR 2026
Final confidence set construction. By combining our concentration results for T and P (Corol- laries C.5 and C.9) with the deterministic bound on concentrability, we can construct the final offline confidence set. The following lemma provides the general form, which uses only quantities com- putable from our offine data and estimators, leading directly to the explicit radius in Theorem (42 Lemma 4.4 (Offline policy confidence set). Let Rí (ō/2) and R2(0/2) be high-probability upper bounds on the Hellinger estimation errors for the policy and transition model, such that with prob- ability at least 5/2 each:
(P PP..) S (1(22) and HPP
p ,P-)) & R2(6/2).
Then, under Assumption the offline confidence policy
(1+ (1
2 2vR Rí
II
T T
Vmin
contains the expert policy nt' with probability at least 1
4.2 STAGE CONSTRAINED ONLINE PREFERENCE LEARNING
In the online stage, goal is to efficiently learn the true preference reward vector w by leveraging the confidence set IIoffline constructed previously. Our approach follows the generalized linear model (GLM) framework for preference-bacee parametric bandits (Filippi et al., 2010; Faury et al. 2020). We first summarize its core components, and then show our novel adaptations. All derivations and proofs provided in Appendix
RI. of Saha al. (003)), who themselves adapt GLMs from
Preference-basse online learning framework. The online algorithm learns a preference vector w by iteratively presenting pairs of trajectories (²) to expert and receiving binary preference. At each step 4, the method computes a regularized maximum likelihood estimate w.LLE' based on past preference queries. Since this initial estimate may not satisfy our boundedness Assumption I it is projected onto a valid set. This projection uses the empirical data matrix
V KAI +
2=1
which captures the information gathered from past queries, and transformation function given by g(w) EE= a ((p(T))) - o(T)), (off)./) w)) (d(T)) - )(T?)) +Aw. The projected estimate w pro is then
found by solving the following optimization problem:
w Pooj
(19:(w) (e (.....E.
MI.E
arg min wEBw(O)
The matrix V, serves a dual role: It defines a confidence ellipsoid around w/ that contains w with high probability, and it guides exploration towards directions highest uncertainty via its Mahalanobis norm. To obtain our distributional guarantees, we need to relate this empirical matrix, built from single trajectory realizations, to its expected counterpart V,, which averages over the sampling randomness of the trajectories: V. RλI, Σ (o (T/) 6 (m?)) Relating these matrices allows our bounds to account for both model uncertainty and sampling variance.
Our work introduces two important modifications to this framework integrate the offline informa- tion and guide online exploration.
1. Offline-online transition model integration. We improve the online transition model estimator's sample efficiency by pooling offline and online data. We initialize it using the offline MLE estimator from Equation (.), which in the tabular setting is a simple count-based estimator. We then update at each step t using the combined counts:
Nor(s' s, N.(s', s,a)
Pi(5' a)
(s, + (s(
Consequently, to account for the uncertainty in the estimator, adapt the exploration bonus from Chatterji et al. (202I) to use these combined counts:
Un
BA( n, ENNaE
min hE(M]
Σ
2n, Ang Noa(Sn, (h,, an) + Ne(Sh, an)
7

---

Published as a conference paper at ICLR 2026
where Un is logarithmic term dependent the state-action space size and the confidence 6 (Lemma E.3 This bonus B, encourages exploring parts of the state-action space where com- bined offine--oline transition model less certain.
2. Constrained and uncertainty-guidde policy selection. We constrain all online exploration to the offline confidence set _ Within this safe set, the algorithm actively seeks to reduce uncer- lainty. At each step (line 7 of Algorithm []. it selects the pair of policies (T) m that maximizes a total exploration objective. This objective combines the uncertainty in the preference model (the || ll- term) with uncertainty in the transition model (the B, bonus). The following lemma formalizes the adaptive online confidence set II; from which we sample, guaranteeing that this ex- ploration strategy remains sound. The confidence radius multiplier 7/ defined in Appendix [D.4 Lemma 4.5 (Online policy confidence set). With probability at least 1 gonline, the optimal policy guntir n² is contained the set II C 1 for all E (T), where 8' 2[ and II, is defined as
11, == { TT 11
V E 11
(Q) - (T))) w: mmm) + n 110 (10P((T) (T) -PP (T)'lVV,
+ Be(T, 2W B, 8') + Be(T', (111,,110 2W B, 8*) 2 } (nh + Lemma D.7
4.3 THE BRIDGE: HOW OFFLINE DATA REDUCES ONLINE REGRET
We now explain the core theoretical mechanism connecting the quality our offline estimate the final online regret (cf. Lemmas B.4 and E.6).
Regret bounds online learning are fundamentally tied to controlling the cumulative exploration variance of queried policy pairs, tr(V.) = Evec [| o u. )13. Standard analyses (Lattimore & Szepesvári 2020) rely on worst-case bounds. Saha et al. (2023), using the bounded feature assumption I obtain a worst-case uniform bound on the feature differences - ll2 S 2B, leading to total variance that scales linearly with the online horizon T.
Our key insight is that by constraining policy selection to π E II (line 7 of Algorithm I we es- tablish tighter, offline data- dependent bound. The properties of our Hellinger- based confieecee set (Lemma 4.4) and the connection between Hellinger distances and feature distances (Appendix [. allow prove that for any pair of policies æ1, 22 E Noofilin.
" 60 (T22)) < 4V2B
1o
Vn
This result directly injects the offline data size into the online variance term at each step. It is the central mechanism by which the offline confidence set's O(1/vn) radius improves our final regret bound (Theorem 4.1]. which formally establishes the trade-off between offline data collection and online query efficiency.
4.4 PROOF SKETCH OF OUR MAIN REGRET BOUND (THEOREM 4.1)
We first derive the offline confidence set Ioffline in Theorem 4.2 Lemma B.1 proving that x* noffline with high probability. For each online iteration 1, in Lemma D.1 we bound the distance between the learned parameter wh and the optimal parameter w under the norm induced by V., in Lemma D.2 we relate the empirical data matrix V, to the expected data matrix V., and combine this Lemma D.3 to bound the distance between w and w" under the norm induced by V.. To handle the uncertainty of our transition estimator, we define and bound bonus terms B in Lemmas D.4 to D.6 Combining these results, we prove Lemma 4.5) which states that with high probability, Vt I....,T:: : E 11, In Lemma D.7 we prove the regret bound as a combination of the three terms of the final bound of Theorem E.I which however still depend on the bonus terms and policy embedding difference under the ||- ll -nom. Finally, in Theorem E. we use auxiliary results to remove that dependence and bound each of these three terms in terms of just the various constants (MDP parameters and assumed embedding & parameter vector bounds), the number of online iterations T, and the number of offline data n..
8

---

Published as a conference paper at ICLR 2026
4.5 LIMITATIONS AND ASSUMPTIONS OF BRIDGE
Here we briefly discuss the implications of our assumptions and resulting limitations of our theory.
Linear preferences and bounded features. The chosen feature embedding & must be sufficiently expressive to capture the expert's 8 preferences. In case the expert preferences are unknown, one has to resort to naïve policy embeddings. These perform worse than informed ones (as seen in Figure but can still work well enough, as main experiments show in Figure 2 Future work could investigate learning embeddings from the offline dataset ! before the online phase begins, using supervupee objectives van den Oord et al. (2018).
Realizability and expert data. We assume the expert policy is realizable, and that the offline data comes from the expert. As a result, the quality of the offline data is key to BRIDGE's performance. If the offline data is noisy or suboptimal, the resulting BC policy will be a poor center for our Hellinger ball and the confidence set may require a larger radius to contain the expert policy or, worse, may not contain at all with useful radii. Our ablation on suboptimal offline data in Appendix A. A. confirms that as data is noisier, the effectiveness of our offline filtering (search space reduction) decreases.
Expert policy concentration. Our assumption Ymin 0 is weaker than comparable ones in the literature that require minimal offline data coverage across all state-action pairs (Rashidinejad et al.) 2021). We only require that the expert's 's policy has a minimum visitation probability for the states it visits. The dependence of regret on the minimum visitation probability Tinin arises naturally from concentrating statistical estimation error on states where expert support exists.
5 EXPERIMENTS
We conduct experiments validate our theoretical claims and demonstrate the empirical effective- ness of BRIDGE. We implement our algorithm for both discrete and continuous MDPs. As base- lines, we implement Foster al. (2024)'s 's offline Behavioral Cloning (BC) and Saha al. (2023) online preference-based RL (PbRL) algorithms, for both of which no implementations are publicly available. BRIDGE outperforms both baselines' cumulative regret in both discrete and con- tinuous control environments. We conduct ablation studies comparing the impact of the radius, expert suboptimality, number of offline trajectories, and embedding functions. We refer to the ap- pendix for details on the ablations (A.]) environments ( embeddings (A.3) and descriptions of the algorithm implementations (A.5).
Discrete and continuous environments. We provide a separate implementation of BRIDGE and PbRL for both types of environments, detailed descriptions are in Appendix A.5 We eval- uate BRIDGE against offline BC and online PbRL baselines in two discrete (StarMDP and Gridworld d) and continuous control (Reacher and Ant) environments. For each algorithm, we measure regret the difference in expected reward between the currently selected "best" policy and the expert policy. As shown in Figure BRIDGE achieves lower cumulative regret than both baselines across all environments. Figure shows that BRIDGE refines its policy search space IT faster than the PbRL baseline.
In the discrete case, the confidence set filtering step (line 6) and optimization step (line 7) require ((11g[llime (2) and ((IL,1²) many computations, respectively. In continuous control, with its in- finitely large policy space, we use a finite approximation of II render these steps tractable (see Appendix A.5.2 With our implementation, we provide a solution to this practical optimization challenge that most algorithms with theoretical guarantees in imitation learning (Foster et al.) 2024) and preference-based RI. (Chen et al. 2022 Drago et al. 2025) do not address explicitly. We view this as an additional contribution.
Ablations. We performed several ablations, with full details found in Appendix A. Our findings show performance is sensitive to the confidence set radius: A large radius less effective as the search space is poorly constrained, while a radius that is too small can break theoretical guarantees by excluding the optimal policy πt (Lemma 4.5). The quantity and quality of offline data also di- rectly impact performance, more high-quality trajectories shrink the confidence set and improve performance, while less-optimal data leads to less shrinkage. The choice of feature embedding ó is critical. Embeddings that are better aligned with the ground-truth expert preferences significantly

---

Published as a conference paper at ICLR 2026
60
Online PaRL
BRIDGE
BRIDGE
Cumulative rogral
60
Oumulstive
20
(a) StarMDP
(b) Gridworld
180
800
BRIDGE
BRIDGE
Cumutattic ragret
10.
Cumulsttie
400
0
170
(c) Reacher
(d) Ant
baselines across four environments. Our method, BRIDGE, achieves lower regret than the offline BC (Foster et al. 2024) and online PbRL (Saha et al. 2023 baselines in both discrete tasks & b) and continuous control tasks (c & d). Dotted lines show BC (green) and expert (red) regret. Mean and 95% CI over 20 seeds. Embeddings used (cf. Appendix A.3): (a) identity-short, (b) state-counts. (c d) average state-action. Num- ber of offline demonstrations: (a) 2, (b) 10, (c) 20, (d) 30.
Figure 2: Cumulative regret
10P
Onlire PuRL
Online FURL
of poticias 11,
Number ol polictes
100
101
10'
10P
25
25
70
70
100
120
100
370
200
Itaration
Ilenation
Figure 3: Policy set size refinement for discrete (StarMDP, left) and continuous (Reacher, right) environments. Our BRIDGE rapidly prunes the policy search space compared to the online PbRL. baseline, which explores more broadly. Mean and 95% CI over 20 seeds.
improve performance for both our method and the baseline. We verify that empirical regret follows the theoretical dependence on expert minimum visitation probability Tmin- As Timin shrinks, perfor- mance degrades. Finally, we show that injecting noise into the oracle feedback delays convergence and increases regret.
CONCLUSION
We introduce BRIDGE, an algorithm that addresses the real-world challenges of learning without specifiable reward functions and risky exploration by fine-tuning imitation policies with online pref- erence feedback. We provide the first theoretical regret bound for this hybrid paradigm, proving that an offline-built confidence set shrinks the online search space to provably reduce regret. Our ex- periments in discrete and continuous control tasks validate this theory, showing BRIDGE achieves lower regret than both offline-only and online-only baselines. Our work opens new directions for developing interactive learning systems that can safely and efficiently improve from human input without explicit reward signals.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This research was generously supported with funding by the Hasler Foundation, under the project title "Unified Feedback Integration Framework for Reinforcement Learning".
REFERENCES
Philip Ball, Laura Smith, Ilya Kostrikov, and Sergey Levine. Efficient online reinforcement learn- ing with offline data. In Proceedings of the International Conference on Machine Learning (ICML). pp. 1577-1594, 2023.
Daniel Brown, Russell Coleman, Ravi Srinivasan, and Scott Niekum. Safe imitation learning via fast Bayesian reward inference from preferences. In Proceedings of the International Conference on Machine Learning (ICML), pp.
2020.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforce- ment learning with once-per-episode feedback. Advances in Neural Information Processing Sys- tems (NeurIPS), pp. 3401-3412 2021.
Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In Proceedings of the International Conference Machine Learning (ICML), pp. 1042-1051, 2019.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in-the loop: Provably efficient preference- based reinforcement learning with general function approximation. In Proceedings of the International Conference on Machine Learning (ICML), pp. 3773-3793, 2022.
Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1300--3383 2017.
Simone Drago, Marco Mussi, and Alberto Maria Metelli. Towards theoretical understanding of se- quential decision making with preference feedback. In Forty-second International Conference on Machine Learming, 2025.
net http://wweeetrrrroooooooooooi/ia
Gabriel Dulac-Arold, Daniel Mankowitz, and Todd Hester. Challenges of woal-world reinforcement learning. arXiv preprint arXiv: 1904. 2019.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In Proceedings of the International Conference on Machine Learning (ICML), pp. 3052-3060, 2020.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems (NeurIPS), 2010.
Dylan Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? Understanding horizon in imitation learning. arXiv preprint arXiv:2407: 2024.
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep Q-learning from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), 2018.
Ilya Kostrikov, Ofir Nachum, Vikas Tomar, and Sergey Levine. Offline reinforcement learning with implicit Q-leariing In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offline-to-onlin reinforcement learning via balanced replay and pessimistic Q-ensemble. Proceedings of the Conference Robot Learning (CoRI.), pp. 1702-1712, 2022.
11

---

Published as a conference paper at ICLR 2026
Jan Leike, David Krueger, Tom Everitt, Miljan Martic, Vishal Maini, and Shane Legg. Scalable agent alignment via reward modeling: a research direction. arXiv preprint arXiv: arX0v:1111.7871, 2018.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXi::2005.016433 2020.
Ashvin Nair, Bob McGrew, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Over- coming exploration in reinforcement learning with demonstrations. In Proceedings of the IEEE International Conference Robotics and Automation (ICRA), pp. 6292-6299 2018.
Ashvin Nair, Gal Dalal, Abhishek Gupta, and Sergey Levine. AWAC: Accelerating online reinforce- ment learning with offline datasets, In Proceedings of the Conference on Robot Learning (CoRL), pp. 102-121, 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. In Advances in Neural Information Processing Systems (NeurIPS), pp. 11730-277444 2022.
Aldo Pacchiano, Jack Parker-Holder Yunhao Tang, Krzysztof Choromanski, Anna Choromanska, and Michael Jordan. Learning to score behaviors for guided policy optimization. In Proceedings of the International Conference on Machine Learning (ICML). pp. 7445-7454, 2020.
Seohong Park, Kevin Frans, Sergey Levine, and Aviral Kumar. Is value learning really the main bottleneck in offline RL? In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Jack Parker-Holdes Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diver- sity in population based reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020a.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), pp. 18050-18062, 2020b.
Dean A Pomerleau. ALVINN: An autonomous land vehicle in a neural network. Advances in Neural Information Processing Systems (NeurIPS), 1988.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model secretly a reward model. arXiv preprint arXiv:2305.18220 18200, 2024.
Antonin
RI baselines3 Z00. basel n z0o, 2020.
Raffin
https::/github.. com RM/
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv: /709. 10087, 2017.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. arXiv preprint arx
2021.
Stéphane Ross and Andrew Bagnell. Agnostic system identification for model-basee reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1905- 1912, 2012.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 627-635, 2011.
12

---

Published as a conference paper at ICLR 2026
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling RL: Reinforcement learning with tra- jectory preferences. Proceedings of the International Conference on Artificial Intelligence and 2023.
Statistics (AISTATS), pp.
Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973-606, 2016.
Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hy- brid RL: Using both offline and online data can make RL efficient. In Proceedings of the Interna- tional Conference on Learning Representations (ICLR), 2023.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen Tang, Ben Abbatematteo, Jiaheng Hu, Rohan Chandra, Roberto Martin-Martin, and Peter Stone. Deep reinforcement learning for robotics: A survey of real-world successes. In Proceed- ings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 28694-28698, 2025.
Dengwang Tang. Rahul Jain, Botao Hao, and Zheng Wen. Efficient online learning with offline datasets for infinite horizon MDPs: A Bayesian approach. arXiv preprint arXiv:2310.1 15331,
2023.
Andrea Tirinzoni, Ahmed Touati, Jesse Farebrother, Mateusz Guzek, Anssi Kanervisto, Yingchen Xu, Alessandro Lazaric, and Matteo Pirotta. Zero-shot whole-body humanoid control via behav- ioral foundation models, 2025.
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.1733, 2024.
Sara A. van de Geer. Applications of empirical process theory, 2000. semant www.tticccccccac.ccoooomoo or..oopuuirr 123051755
URL https://api,
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018
Mel Vecerik. Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pictquin, Bilal Piot, Nico- las Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstra- tions for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv: 2017.
Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pp. 35300-35338, 2023.
Martin J Wainwright. High-dimensional statistics: A non-asymplotic viewpoint, volume 48. Cam- bridge University Press, 2019.
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 (NeurIPS), 34:27395-27407, 2021.
Tong Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. Annals of Statistics, 34:2180-22101 2006.
13

---

Published as a conference paper at ICLR 2026
A EXPERIMENTS AND ADDITIONAL CONTEXT
We compare our algorithm with the log-loss behavioral cloning method of Foster et al. (2024) and the preference-based online learning algorithm of [Saha et al. (2023). We could not find publicly available implementations for either of the two, so we made adaptions to achieve computable im- plementation. Our separate implementations for discrete and continuous environments are described in Appendii/AA.5.11 and respeciivv.....
All discrete experiments were run on an MI Max CPU with 32GB of RAM, with a wall-clock time of roughly 3 seconds per iteration of the online loop for BRIDGE. The main computational bottleneck in the discrete implementation is the simulation of trajectories for approximating the expectation within d(TT), runtime does not vary significantly between the different environments, if normalized for episode length. Steps 6 and 7 of the algorithm, within its online loop, are the most computationally complex. Step 6, filtering IIgmine to obtain II, requires ( (2) many calculations involving the embeddings. Step 7, finding the pair of policies in II, that maximizes uncertainty, requires O[II, (2) many. The smaller the initial IIqiline, the shorter the runtime.
Throughout, we use deterministic, tabular policies, i.c., they are represented by a matrix of size S A, where each row is one-hot vector defining the deterministic action taken in that state. The figures shown display results averaged over 30 seeds, with thick lines representing the average, and shaded areas the results contained within one standard deviation to either side of the average. The continuous control experiments were run on an HPC cluster on variety of nodes with both AMD and Intel server CPUs of mixed generations (32- to 256-core), on 20 parallel seeds each using a separate core, and using less than 2GB of RAM per core. On these more complex environments, simulating rollouts and filtering the online confidence set at each iteration is considerably more expensive, and observed wall-clock experiment runtime for 200 iterations reached up to 8 hours (much faster, at only small performance loss, if forgoing online confidence set filtering). Runtime strongly varies between environments, as e.g. higher dimensional state space and more complex transition dynamics increase memory and computation requirements.
Our main regret and search space size figures contain two types of plots. The first (ef. Figure 2 displays the (sub)optimality of the current best policy chosen by each online algorithm at each iteration. At the end of an iteration, this policy is chosen as the one from the offline confidence set T which maximizes the learned score function s (T)) Ey. [()(T), w. Its expected reward is simulated and compared to the optimal policy's (red dotted line) calculate the regret. The green dotted line is the expected reward of the Behavioral Cloning policy estimated
al. (2024). The second plot (cf. Figure 3 illustrates the speed at which the algorithms pare down the size of the policy confidence set IT, once the set contains only single element, we consider the algorithm converged, as that element the algorithm's 's estimate of the optimal policy x².
A.1 ABLATIONS
Impact of radius on BRIDGE performance. On the Reacher continuous control environment with 20 offline trajectories, vary the radius BRIDGE uses filter the candidates. Figure Shows that higher radii lead to less filtering, and performance that approaches the online PbRL baseline's s. Reducing the radius improves performance up point if reduced by too much, the expert may no longer be contained in the filtered IIfffiie and thus the search space II, leading to worsening regret.
Impact of offline data amount and suboptimality on confidence set size. This ablation validates our central theoretical contributions: increasing the amount and quality of offline data constrains the policy search space, which in turn improves online regret and enables more sample-efficient preference learning. We conduct the ablation on the Gri sworlld environment. We vary the amount of offline expert trajectories in D from ooffinee = 10 to 1000. Additionally, we vary the quality of the data using noise parameter ranging from 0% to 20% that represents the probability that an expert action in the dataset is corrupted to a random action. Results shown are averaged over 100 random seeds.
Table I shows the percentage of policies remaining in the confidence set after Hellinger distance filtering, such that 100% indicates no constraint and filtering, and lower values show tighter
14

---

Published as a conference paper at ICLR 2026
Baseline
100
BRIDGE [n-0.1)
BRIDGE (-+0.8)
BRIDGE
SAN
BRIDOF [r-5.0 0)
Cumusthi rognet
200
Figure 4: BRIDGE performance for different values of the radius used to filter candidate policies and create the offline confidence set. Higher radii lead to less filtering and performance that ap- proaches the online PbRL baseline's, s, while radius too small excludes (near-)optimal candidates, leading to unavoidable regret.
constraints and stronger filtering. We observe that clean data, 100-fold increase in training data leads to 12.4x reduction in search space size (99.9% - 8.0%), roughly a O(1/ (offline) scaling. Our experiment shows that BRIDGE's filtering still works under noisy data, with filtering effectiveness weakening as noise increases.
Confidence Set Size (%)
Nattline
0% Noise
10% Noise 20% Noise
10
99. 99.9+0.3
99.9+0.3
100.0=0.0
20
92.4=8.7
96.2+6.4
99.0=1.8 1.8
40
58.5#16.3
80.4+14.3
95.325.8
28.9+17.1
66.3+16.3
92.047.4
1000
8.024.8
65.6+10.0
95.443.3
Table 1:
Empirical validation of confidence set scaling with offline data size and demonstration noise. Results averaged over 100 statistical runs.
Impact of offline dataset size BRIDGE performance. We run ablation comparing the im- pact of the amount of offline data ! given on BRIDGE's performance. The experiment is again carried out on the Reacher continuous control environment. If given more offline trajectories, the quality of the BC policy BC and thus also BRIDGE's candidate set of policies I[olliie improves. We observe that BRIDGE quickly converges to best policy its candidate set, so more offline data, as expected, leads lower regret.
Impact of choice of embedding & on BRIDGE performance. The choice of embedding has outsized impact both PbRL'ss and BRIDGE's performance. We illustrate this again the Reacher continuous control environment. We show three embeddings: one that approximates the true reward signal in this environment, and the environmentt-gnosticc average stale-action and last state embeddings. See Appendix A.3 for a detailed description of all embeddings used. Figure 6 illustrates how embeddings that more closely approximate the reward signal improve preference- learning performance. The average reward-emulating embedding massively simplifies the learning problem by making it easy distinguish good from bad policies the only downside being that it has to be handcrafted for this specific environment, which is harder the less one knows about the nature the reward signal (but is trivial in a well-specified sim like MuJoCo). The alternative are the two state-agnostic embeddings, which show slower and worse convergence, with the richer BRIDGE. This environ-
average state-action embedding showing slightly better convergence ment's rewards contain components that non-linear in the observations, e.g., the total magnitude of acceleration ||al| to punish harsh movements. These two embeddings cannot represent those components. We cannot expect them fully converge purely from preference signals: their search
15

---

Published as a conference paper at ICLR 2026
BRIDGE (N-12)
BRIDGE (N-20)
BRIDGE (N-30)
Cumusthic rognet
100
Figure 5: BRIDGE performance for different amounts of offline demonstration trajectories given. As the number offline trajectories increases, BRIDGE's regret reduced.
space may contain several potentially optimal policies whose trajectories differ only in those non- linear components and who thus cannot be distinguished using those embeddings and our linear model.
130
200
100
Cumaanta MOT
150
STECE Orllie PAAT
100
72
Iwaatinn
Dematoon
(a) average reward-emulating
(b) average state-action
(c) final state
Figure 6: Ablation showing BRIDGE's performance using three different embeddings in continu- ous environments. Embeddings that are closer to the true reward signal predictably perform better.
Impact of minimum expert visitation Tmin- We run ablation comparing the impact of different values of Ymin between 0.05 and 0.25. As Tmin shrinks, which corresponds to a more specialized expert, theoretical regret bound increases. Figure 7 shows that experimentally, this behavior holds true, and smaller 7min lead to a higher regret.
The environment goal, is described in Appendix A.I allows us to control the expert's Ymin via a parameter in the environment definition.
for this ablation is variation of the StarMDP that has two paths to the
Impact of noisy expert feedback. We run an ablation comparing the impact of different levels of noise in the expert feedback, from 0% 50%. As Figure shows, increased noise leads to longer time until convergence, and higher cumulative regret.
A.2 ENVIRONMENTS
10 StarMDP (custom). illustrate the transition dynamics underlying the StarMDP in Figure
This environment features states and 4 actions do, d1, a22 dg that correspond to rightt feft, up and down respectively. Actions have probability of 0.7 of success, with an agent being moved to a different, random state with probability of 0.3. Taking an "impossible" action such going left in state 84 will result not moving with probability 1. Episodes have length H and start from So- The offline expert's dataset consists of trajectories (re-drawn each seed).
16

---

Published as a conference paper at ICLR 2026
0.08
Nob
0.15
20
Cumuistic regrct
Figure 7: Ablation showing BRIDGE's performance with different levels of minimum expert vis- itation probability Ymin. As "/min shrinks, our regret bounds get looser, and empirical performance deteriorates.
a1
80
01
00
4g
$2
R
+1
40
00
01
84
83
a1
R
100
Figure 8: Environment used for the ablation Ymin. The starting state is so. when taking any action so there a probability equal to Tiai to transported to 83 (dotted line). The only states with nonzero rewards are $2 (R = +1) and $4 (R - 100). The expert will always move along the trajectory ($p, $1, $2). or, if they randomly get transported to $3, along (&p, $3, $2). Thus, the expert's minimum nonzero visitation probability V/nin equal the probability of getting transported.
Gridworld (custom). We illustrate the gridworld environment in Figure 11 consists of a grid with states associated with different rewards, including a negative-reward region the top-right corner, high-reward but unreachable state, and moderate-rewes goal state
The environment
200
0% noise
20% noiie
150
50% noise
Cumuishve ragnos
100
Figure 9: Ablation showing BRIDGE's performance with different levels of noise in the oracle
feedback. At a given level, the oracle has a chance equivalent to the noise to return the wrong preference. With higher noise, convergence slows down, leading higher cumulative regret.
17

---

Published as a conference paper at ICLR 2026
84
R 10
00
80
82
a1
01
S
R 6
83
R =
-
Figure 10: Star MDP. Transition probabilities 0.7 for all solid arrows, otherwise the action takes the agent randomly to one of the other states.
at the bottom right corner. Each episode has length 10 and starts in the top-left corner. Each of the four actions (up, left, down, right) has success probability of 0.8, whereas with probability 0.2 a randomly chosen different action is executed. Action stay remains in the current state with probability 1. Transitions beyond the grid limits through obstacles have probability zero, with the remainder of the probability mass for each action being distributed among other directions equally. The offline dataset consists of 10 expert trajectories (re-drawn each seed).
Start
-1
20
10
Figure 11: Gridworld environment. Rewards at every state are indicated if non-zero. Transition probabilities are 0.9. Thick lines indicate obstacle, through which state transitions have probabil- ity zero.
Reacher (MuJoCo, v5). This environment is part of the MuJoCo continuous control suite, which we use via Gymnasium (Towers et 2024). The agent controls two-jointed robot arm on 2D plane and needs to move its tip to location that is sampled at random at the start of each episode. Rewards are weighted combination of the distance between tip of the arm and the target, and penalty term given as the euclidian norm of the action. The environment features 10-dimensional observation space and 2-dimensional action space (torque at each joint). We train our own expert on this environment, using RL Baselines3 Zoo's s (Raffin 2020) reference implementations. We use it to generate an offline dataset of 20 trajectories (re-drawn each seed), each of length H 50 (the default).
Saable-Bsselines PPO agent with training hyperparameters taken from
Ant (MuJoCo, v5). This is the second of our two continuous control environments, again accessed via Gymnasium. It is more complex as a control task than Reacher, but contains less stochastic elements. The agent is 3D quadruped robot with four legs, that each feature two controllable joints. The aim is to move across a plane, with a slightly randomized initial location and orientation. Rewards are given for achieving maximal distance in direction of the x-axis, with penalties for large action amplitudes and a bonus for survival (not flipping over). Our goal in selecting this environment is that the survival aspect allows behavioral cloning quickly achieve dlose-lo-pptimal policy,
18

---

Published as a conference paper at ICLR 2026
but to have the remaining nonzero probability of sudden catastrophic failure require many more offline trajectories to fully converge. The action space has 8 dimensions. The 105-dimensional observation space is much bigger than in 'Ant'. RL Baselines3 Zoo provides pre-trained experts for many MuJoCo environments, but these are based on -v3 versions of the environments, which in Ant's case features slightly different action space than our -v5 version, thus making the agent incompatible. Just like in the Reacher environment, we used their training hyperparameters to train our own expert to convergence with TD3. The expert used generate an offline dataset of 30 trajectories (re-drawn each seed), each of length 100 (truncating from the default 1000).
A.3
EMBEDDINGS
The choice embedding function & has implications on computational complexity and learning speed. Concretely, both small dimension d and upper bound B for the norm of embedded trajecto- ries are desirable. We present embeddings for both discrete (tabular) and continuous environments. See Pacchiano et (2020) Parker Holder et al. (2020a) for more possible embedding functions and analyses of their performance in different RL tasks.
Our experiments the reward signal model the preferences. general observation we make that confirming intuition, the more closely an embedding approximates the true reward, the easier the learning problem and the faster preference learning (both BRIDGE and the PbRL baseline) converges. If one has information about the nature of the true preferences (in our case, rewards), it seems helpful incorporate those by crafting environment-specifee embeddings, which we have done in the continuous case.
Discrete environments. We considered four options, defined on the space of trajectories. In the experiments shown use two embeddings that strike good balance between dimension, norm bound, and expressiveness. The StarMDP experiments use the identity.sher The Gr wridworld experiments the state.counts embedding. States and actions repre- sented as one-hot vectors.
embedding.
Table 2: Discrete embedding definitions and properties
Name
Definition ((T)
d
B
identity.long identity.short
(50, Σ (15H(1),01)
H(SS)
|Al)
V2H
[S] +
A|
V2H
stant.counts
EisH (8t)
S
H
final.state 8h
[
Continuous environments. We use both aaviromment-agnostin and environment--peecfic embed- dings, as shown in Table 3 Our main experiments for both Reacher and Ant (Section (5) use the average wwarageessaaee. www.stttttttiioo
embedding, which similar to the discrete identity.short embedding. We show the impact of using the env-agnostic final_st lalaltttttee and env-specific reacher. reward embeddings in an ablation in Appendix A.I
Table 3: Continuous embedding definitions and properties
Name
Definition ((T)
d
averageestaate-action
|S]
|A]
VISI +
AA
final.state
8H
[S]
V
reacher reward
1 Ensu (ldisttttt-----aree,, 2?, 11²)
2
2.2
A.4 COMPARING BRIDGE WITH MODERN PREFERENCE-BAE BASED FINE-TUNING ALGORITHMS
We see three main points of comparison to BRIDGE the space of preference based fine-tuning algorithms: Reinforcement Learning from Human Feedback (RLHF) Ouyang et al. (2022). Direct
19

---

Published as a conference paper at ICLR 2026
Preference Optimization (DPO) Rafailov et al. (2024), and online-preferent based RL (PbRL) Saha et al. (003))
RLHF first trains static reward model (RM) from offline dataset of preferences. then runs an RL algorithm (like PPO) against this reward model. This two-stage process can suffer from RM mis-specification or "reward hacking." Furthermore, it typically relies on "soft" KL-divergence penalty to the initial policy as a heuristic for safety or style. BRIDGE differs in two ways: First, avoid static RM by iteratively learning the latent preference vector w within the online loop. Second, we replace the heuristic KL-constraint with a provable one: our online exploration is "hard" constrained the offline Hellinger confidence set - which is guaranteed contain the expert policy x² with high probability.
DPO is a powerful offline method that learns directly from static, pre-collected set of preferences. BRIDGE is designed for a different, online problem setting. Our online stage is an active learning loop that intelligently selects which new queries to make to a live expert to minimize online regret. Moreover, like RLHE, DPO's offline phase requires preferences, whereas BRIDGE's offline phase uses reward-free expert demonstrations.
Online-only PhRL is what BRIDGE'S online component builds on. Our core contribution is adapt- ing into a hybrid framework. BRIDGE improves on the PbRL. baseline in two ways: First, we constrain policy selection to 11p which establishes tighter, data-dependent exploration variance bound that shrinks with number offline demonstrations n, formally connecting offline data to on- line regret. Second, we "pool" both offline and online data create more sample-efficient online transition model estimator.
A.5 PRACTICAL IMPLEMENTATIONS OF BRIDGE
We provide two different implementations of BRIDGE, one for tabular, and the other for continuous environments The discrete implementation aims to implement BRIDGE as close to the theoret- ical description as possible, while the continuous one implements its main ideas, but has to take more liberties in details to stay computable. Appendix A.3. shows the discrete implementation, Appendix A.5.2 the continuous one, and Appendix [A.5.3 presents computationally efficient way to calculate the Hellinger distance in the discrete case, which we use in our discrete implementation.
A.5.1 DISCRETE IMPLEMENTATION
Offline learning For both our testing environments StarMDP and Gridworld, we obtain the (labular) optimal policy π² by solving linear program using cvxopt. We sample trajectories from this policy to create a dataset of offline trajectories D The learned transition models are trained on the offline trajectory dataset. The model for StarMDP is Maximum Likelihood Estimator (MLE) 2-layer MIP with a hidden dimension
based on the state visitation counts, while Gri fcridwordd of 32 and ReI.u activations trained to predict next states with a cross-entropy loss. We estimate the optimal policy on the offline dataset with log-loss Behavioral Cloning (LogLessBC in Foster et al. 2024 using Adam, resulting in ã.
To obtain I we use rejection sampling, although the search space of policies depends on the MDP. In StarMDP, we construct all [T] 1024 deterministic, stationary policies and iterate through each of them, calculating its Hellinger distance to मे and adding it to Mf if the distance is less than R. In larger MDPs this is infeasible as [TI] quickly grows. In Gr Gridworld, we sam- ple 500, 000 random policies, and build 11 by iterating through that sample. This sample is large enough to contain close-to-optimal policies with near certainty while staying computationally feasible to exhaustively check. Larger MDPs may require larger samples.
The purely online baseline PbRL in principle searches the space of all (deterministic, stationary) policies II. This is feasible in atarMDP, but in Gr Gridworld, we have to make a pragmatic adap- tion. We define PbRL's i search space as I1offlne (which is on the order of < 50 policies), augmented by random policies to reach a set of size 1000.
*Code: http:s///ggtttbb../////reeaeeeee
20

---

Published as a conference paper at ICLR 2026
Online, preference-based learning In the online loop, estimate Φ(TT) Er [ó(r)] for any т, we sample 100 trajectories T and average the returned embeddings. To start the online loop, we initialize wo as a vector of random normal values with mean 0 and variance 1. In subsequent iterations t, w is initialized as normalized vector of ones (this does improve convergence compared to random initialization) and trained on all online trajectories observed so far using a regularized binary cross-entropy loss (as in Saha et al. (2023), Section 3.1) and Adam for 10 episodes. After preferences have been collected, we update the learned transition model, obtaining 1 by retraining from scratch the same models and losses described in the offline part on all online trajectories observed so far. At the end of each iteration, we find the policy with the highest predicted score (d(T)) w and calculate its average reward as well as the true optimal policy x''s over 1000 sampled trajectories under the true transitions and compare the two in our suboptimality plots.
A.5.2 CONTINUOUS IMPLEMENTATION
Offline learning. For both environments Reacher and Ant, we train agents using the hyperpa- rameters from RL Baselines3 Zoo. We sample trajectories from this policy to create a dataset of offline trajectories DD Unlike in the discrete implementation, for simplicity, we do not implement a learned transition model (implementation would work exactly the same as the discrete case). We again obtain an estimate BBC of the optimal policy on the offline dataset with log-loss Behav- ioral Cloning using Adam [LogLossBC in Foster et al. (2024)). Policies are modeled as Gaussian policies with 2-layer MLP of 64 (Reacher) or 256 (Ant) neurons per layer.
As the size of the true policy space is infinite and the rejection sampling from random policies (our approach in discrete MDPs) is computationally infeasible, obtain the offline confidence set I constructively. An alternative approach would be to discretise the state- and action space to land back discrete setting, but we show here how to adapt BRIDGE to the fully continuous setting.
We first construct a proxy II to the true policy space II. The learning problem for BRIDGE and PbRL is fundamentally to learn to distinguish between "good" and "bad" policies, in our case in terms of expected reward. Policies with zero or near-zero expected reward are easily distinguishable from the others by both algorithms and regardless of embedding. They also form the overwhelm- ing majority of all policies in the true II or random sample of it. Including them thus simply increases computation time without meaningfully impacting both algorithms' dynamics. Our goal is to construct a proxy for II that is computationally feasible to search and contains policies ranging in performance from near-zero to near-optimal or even optimal in roughly even proportions, skewed toward including more worse policies, but not to the extremely lopsided degree of the true 11. Our solution is to construct a union of two sets:
I BC BBC small noise)
BC + large noise}.
The first set contains policies that close to the BC policy in terms of both reward and distance in trajectory distribution space, and is expected to also contain near-optimal or optimal policies that improve on BBC We obtain it by adding small amount of Gaussian noise to the BC policy's parameters. The second set is meant to represent the rest of the policy space that achieves rewards ranging from zero to decent, but not near-optimal. It is constructed similar to the first, but with much higher levels of noise. By tuning the noise level, this approach results in policies that cover the remaining spectrum of performance (decent near-zero) and distance to BCC (in trajectory distribution space).
We then define BRIDGE's filtered offline confidence set
IIfffiiee : {(T i [[Ø(T)) d(( radius]
using the L.2, (rather than Hellinger) distance in trajectory distribution space for computability.
Online, preference-basee learning. We estimate ((T) = p.-,,--poee [d(T)] by sampling 200 trajec- tories and averaging the returned embeddings. For massively increased performance, we do this
21

---

Published as a conference paper at ICLR 2026
only once at the start of the online loop and then cached versions. The order of operations in the online loop is slightly different than as stated in theory and in the discrete case.
We first filter [[ to obtain the online confidence set,
11. =
Iroffline
Va'
E IIoffline ( 6(x²), wi) - 20]
As we assume a known transition model, there are no bonus terms. The exploration scaling factor can be chosen to increase (smaller 7) or reduce (larger 7) the speed at which the confidence set is pruned.
Then, sample pair of policies from the set, m²) E 11. There are several ways to implement sampling that follow the spirit of the theoretical algorithm. We have tested three:
x = arg (ó(r)) we) and nT2 random, picking a pair of the current estimated optimal policy and a random other,
(,²,+²) ? = arg (ax - <(x3), w.) + -llm(=²)) - ((>>))l spiritually similar to UCB, which picks the pair maximizing 3-weighted combination of the difference in estimated win probabilities and the uncertainty that estimate,
and perhaps closest to the theoretical algorithm, picking pair purely based the the uncertainty, (T ) = arg max|
<(>")|l.""
Although they show similar performance, on our environments and embeddings, the first performed slightly better and is the one we pick throughout.
As in theory, we then sample a trajectory from the pair, receive the oracle preference or I(T T??) (in our case, the higher true trajectory reward), and store the tuple of embedding differences DΦt = p(T²) p(*²) and preference signal (Aér, 0:) in the online preference buffer Doreet To increase convergence speed, we repeat this N rollouts 10 many times for the same policy pair each iteration.
We then learn on the preference buffer Dever using MLE and continual training (rather than starting from scratch every episode) of 100 epochs per iteration.
Finally, we update the data matrix V, = V + (2
A.5.3 AN EFFICIENT CALCULATION OF THE (SQUARED) HELLINGER DISTANCE THE DISCRETE CASE
Here, we demonstrate how under the assumptions of our model there is a computationally tractable method of calculating the Hellinger distances we need that avoids (intractable) iteration over the entire trajectory space.
Reducing Hellinger distance to a recursive scheme. The Hellinger distance between two dis- tributions Ppi, pm p72 is a measure of distance over the space of trajectories. Its square is defined
HP pp:)= =1
Σ
Ppl (P)
trajectorics
1 1I-B
where the term of the sum is called the Bhattacharyya coefficient. Calculating this sum is normally intractable, as the space of trajectories is too large to exhaustively compute anything over. In our case, there is a way to not just calculate this sum (and therefore the Hellinger distance), but do so very efficiently, and we show it here.
In an abuse of notation, we use the fact that we assume stationary, deterministic policies, write (s:)) to refer to the action π chooses with probability at state 8t. We first note that p = do(so) I 1. (arlss) 21,2 18t, at), where do(:) is the initial state distribution.
22

---

Published as a conference paper at ICLR 2026
Our ultimate goal is to efficiently calculate the Bhattacharyya coefficient. Let 7 (Su. ao..... Sr) be a trajectory length that ends in st. Let us write out the square-root term
Ppl (T: (p))PPp(t)))
/dl(0))
II ==
((arlss)P as) do(o0) f=0...-1
II
P2 an)
V
do(s0)
j=0..t-1
Since r² and x² are deterministic, we can simplify it. Whenever x (s) + (s) for any 8 in the trajectory Tr, either x (8) or (s) are zero, which reduces their product to and thus zeroes out the entire term. Thus,
ppl P (T) do(sa)
( (st) (s:))
==0..
We define Xs(s) as the sum of the square root of the product of pt p2 for all partial trajectories Tr of length ending in state 8, i.e:
x1(s) = Σ
(T)
ending
Claim. There a recursive relationship:
X1+1(50-1) Σ ( ((t)) +s))) S,ES
Proof. For t = 0, the trajectories of length 0 are just the initial states, so by definition, Xn(s) = do(s). Note that we can write Xo 1D vector of length (S].
For the induction step, by definition:
X141(86+1)= =
E
du(so) II z=0
v pP' (8541l83, aF) (854111855)
1 ending #cs1
We
can
split the product inside the parentheses into
II-.....-1(....)))
V pp' (8t+1 18;; at) ) (st+1lst, at),
and
split the sum
Σ Ts ending 8y-1
Ex, Ea, Es0.00... by first summing over history up to time:
f-1
X0+1($(11== = Σ
Σ
do(so)
II...
II j=0
V papt (s1t1ls a pP (s441))0)))
8t,0s
$00,00....55-11.00-
First, note that the term in brackets is exactly the definition of Xe(st), so we can substitute it. Second, we can again use the fact that policies are deterministic, and that x (s) is non-zero (= 1) if and only if the two policies agree that state, and thus
/ pppt (8t+1 az) ppp (st+1 |st, at) = / (s 1 (ss)) 7
= =? = J.
Combining these two insights, get exactly the claim.
Using the claim, if we have X((sH) ) for all t O.... H and states E S, we can calculate the Bhattacharyya coefficient:
Σ XH(sH)= ES
Σ Σ
Vipph (TH (PH))P
8n ES ending in
Σ
V (PT
trajectories r of length H
BC((P IPp))
23

---

Published as a conference paper at ICLR 2026
Efficiently computing H². We can the recursive scheme just proved above to efficiently compute (*(H)) for all sH, and thus also the Bhattacharyya coefficient BC(..)) and finally the Hellinger distance (...). First, treat X, vector of length (S], where the th entry is Xx;)).. Then, define a matrix such that
Ms = V (s'
s (()))L(T)() = (s)).
Then, have X1 M Xo. X2 M M M Xo. ... XH M Xo. and Xo is simply the vector of probabilities of the initial state distribution dg. Putting this all together, we get
18 Σ 1=0
H (PP pl, P
M do)
This way, avoid having to do any computations tional cost is merely building the matrix M once at the beginning based on ,,, P_ and p (O((S)2), computing M (O(log H) matrix multiplications of (( each), and calculat- ing Xи M Xo with one final matrix multiplication, for a total computational complexity of Olog H|S logg 3) and memory complexity of O([S)) tractable for moderate-sized MDPs.
the entire trajectory space. Computa-
Intuition in our case of p =P.. Our BRIDGE algorithm computes H² .P.)) with the same underlying transition distribution P. In that case,
H
pat (TH) (TH) (TH) do()))
V (8;)) ((s (()))) =3((s) =at}
j=0
f 1
= dd(())
II
P(5 (z) = (3()) = at}
1=0
P(Tn) and n² agree on }
If a trajectory passes only through states where T² and r²'s actions agree, we can call it agreement trajectory. Then, the squared Hellinger distance a direct interpretation using the total probability mass of agreement trajectories:
H²(PT'' pan =1 - -CC(PP P. poy))
p:
=1 - Σ pP (TH) (TH)
(rggemgeemmett trajectories under P).
The complex interpretation of Hellinger distance thus becomes a simple question:
What is the probability that a trajectory evolves for H steps without ever hitting a state where T and ²² diverge?
B SIMPLIFIED SETUP FOR UNDERSTANDING REGRET ANALYSIS
In this section, we propose an analysis of the regret under a simplified setting, where the underlying dynamics Pa known. We aim to build understanding of how the construction of the confidence set over the policies from the offline learning estimation helps to reduce the number of policies to draw from in the online learning setting. By ignoring the added complexity of the transition estimation, we can highlight which part our methods applies to the policies. The goal to prepare the reader for the proof of our algorithm BRIDGE in Appendix
24

---

Published as a conference paper at ICLR 2026
Offline Estimation
Lemma B.1:
Offline Policy Confi-
dence Set
Defines the set of policies -
Corollary [C.5 =
Contains true
policy nT with probability 1 6
Online Estimation
Lemma B.2
Optimal Policy Con-
tainment
Algorithm 2 BRIDGE (Known Model)
-Ellipsoid CI Lemma D.I
Change of norm Lemma D.2 Conditioned Lemma B.
Starts with offline confidence Computes policy set II, at each round
Ensures 11, for all rounds
Selects maximally informative pol-
Combines offline confidence with online estimation
icy pairs
Regret Analysis
Lemma B,4 Feature Difference
Theorem B.5 Regret Analysis
Bound
Final bound:
Leverage Distributional Dist.
Ö(T / log(1 + n.d
T-IS|
))
Lemma R1
Key Insight:
Algorithm leverages offline data to reduce explo-
ration cost
With sufficient offline data, regret becomes con- stant
Feature dimension d amplifies offline data value
Briddges gap between offline imitation and online preference learning
Figure 12: Proof Overview for BRIDGE Algorithm with Known Dynamics
B.1 SETUP FOR KNOWN DYNAMICS
B.1.1 OFFLINE ESTIMATION WITH KNOWN DYNAMICS
Assume we get the offline data D = (T.eet) The underlying object describing the trajectories finite MDP, reward-free setting in the main paper. Assume that the set of possible policies is
25

---

Published as a conference paper at ICLR 2026
stationary and deterministic. Then assuming the underlying dynamics known, the confidence set from Theorem 4.2 reduces to the following, by direct application Corollary C.5 i.c., setting the radius around the MLE estimate x from Equation (7).
We formalize this into the following Lemma:
Lemma B.1 (Offline policy confidence set under known dynamics), Let BCC be the log-loss BC estimator defined in Equation 7 The policy set
6 8 log [|A 8-11
Ofline
(T: HI,
contains n² with probability at least 8.
Proof. Note that by symmetry
H HPPP., pt, )Pp.)
H H(Pp., PP.)
Then the result follows from Corollary C.5
B.1.2 ONLINE LEARNING WITH KNOWN DYNAMICS
Here, we adapt our algorithm BRIDGE to the setting with known transition dynamics P We adapt the approach from Saha et al. (203) under known dynamics to constrain the set of policies to choose from to our offline confidence set hhe described the previous section.
First, since the transitions known, for this section define:
((T) = Erwep. [o(T)]
We also define the expected data matrix V under the true transition dynamics P as follows (see Appendix D for an overview of results about data matrices):
V.' RAL Σ
( (( ((T)))
Then we define the set of policies II, to draw from during the online iterations as:
(d) = 20BW (d (T)))))) (cf. Lemma D.2
known
4x,3(6) + (a))
I Mi |' Mo
(Ó(T) 6(*',, w. " + 7: known [|(((T)) 6(T')( - 20}.
Lemma B.2 (Optimal policy containment). Conditioned on Ew. n Eyge Eugline where:
Fage is the event defined Lemma D.
Exgn is the event defined in Lemma D.2
EEggine = {a" E &II
then
n"
11,
Vt [T].
Proof. This follows directly from Lemma 2 in Saha et al. (023). We adapt the probability parameter
to account for the additional condition that n E Ommme which holds with probability at least 1 according to Lemma C.13
26

---

Published as a conference paper at ICLR 2026
We now present the adapted version of BRIDGE for the known transition model:
Algorithm 2 BRIDGE (known model): Bounded Regret with Imitation Data and Guided Exploration
1: Input: Offline dataset Dh time horizon T, true dynamics P
2: Compute confidence set 1 using Lemma B.1
3: Initialize V1 t kAIa
> Initialize data matrix
4: fort I,..., do
5: Compute w! via constrained MLE (Equation (4)
6: Define policy set IT, based on T and w! proj
7: (T): mī) - arg ma {l(Ø(=)))))))))))))))){)))) - o ((=²))
8: Sample trajectories T. ~ Pp,, T? ~ Pp- and obtain preference = I(T! x xt) + (Ø(T)) ( d(T)))
9: Update matrix: V V f- V, p
10: end for
11:
return Best policy from Hly using final weight estimate w
B.2 REGRET ANALYSIS: BRIDGE (KNOwN MODEL)
We now present a regret analysis of the BRIDGE algorithm under known transition. We start by stating the following lemma:
Lemma B.3. The regret of BRIDGE under known dynamics is bounded from above by:
Rr S 277
known
Σ
[b(=))) - <(= (((=)))(??">
SE[T]
Proof. Let Aot ((()) (.T)). First, we bound the instantaneous regret, using Lemma D.2 in the last line:
2r (A w") + (Doi w")
< (Aor) pro (A w.!rol + I|w" w
(146 (| + Ae [(v
$ (Aot *1 rro (A 2.2 w.rro + 2
known (1 +1 (
Since chose .. .े arg max A and know that xF II, (Lemma B.2 we get
2r. S (Aoi. w + ( w. + 2-
known ( 1
(
Next, using the fact that म.. m, nt" E II, we have the following constraints:
(A ti w. + T
known A *1
( )- 20 0
i e [1,2}
(i mii
%
known A 12 *
i i (1,2)
which lead to
2r. Σ 9/
known
(I
-1 (v )-1
+
A [1 )-1 + 2 known A [vv
< 7/
known
A 1121 (v. )
hence
Ry = Σ
r: <
2
known
| ((7"")--
EE[T]
[T
27

---

Published as a conference paper at ICLR 2026
The remaining step in analysis is to bound the term:
Σ |((mm)) (( (( EE(TT
Σ =E(T]
T [d(T)] E Tmpp [d(T)]
A simple approach would be to Assumption 1 which states that the feature map is bounded in f2-norm by B. However, our offline confidence set construction in Lemma [B.] provides powerful result: policies in set have distributions that close only Hellinger distance but also in the resulting feature expectations.
provides a more
This precisely why we formulated our confidence set constraint using the square root of the squared Hellinger distance it yields a bound on the L2 norm of distribution differences. Through we can translate bounds on Hellinger distance into bounds on the difference of feature expectations in the f--nom.
Lemma H
We formalize this connection in the following lemma:
Lemma B,4 (Feature difference bound Under offline constraints). For policies nt, xt E -h selected by our algorithm at each round t [T]. the sum feature differences measured in the data matrix norm bounded as:
(((T)) (( V2d log log 1+ 192B2T|S| log([A) 8-1)
n. d
LE[T]
where d the feature dimension, the feature norm bound, [S] and |A] are the state and action space sizes, and n is the number of offline samples.
Proof. Again let A <b o(m(). First, we use Canchy-Schwarz on the vectors
(I)aTT) b (1 1.2 (1))er))) and take square root both sides to bound:
(a, b) = Σ
1.2 lV! )-1 I
T. TE[T]
A 1.2 (VP
=|||||||]]
AE[T]
Then, the inequality
2log[1 + u)
u u21
Add (V."'-) )-1 22 Σ
log( 1 1
1E|T9
Using the definition of V we have
r+1 = A laxa+ + Σ (AA
.E([]
= -.."" + (Ao) 1.2 (A 1.2TT
=VV 1/22 1+ (20)) ) (V."" 12/2.
Using the properties of the deterninant:
det((V (+1) det(VV.") ) det (T + (V -1/2 A (100))) -
det((V ). (1 || 1.212 (v. 1-1
det(Vo)
(1+ + A 1.2
sE((]
28

---

Published as a conference paper at ICLR 2026
Taking the log both sides, this holds iff
det( V (-1) det (V))
log
log(1 + 1 (V )
EEI!
It also holds that:
dV (+1)
II
A 2
<E(d]
Using linearity of trace:
TrVV 6+1) Tr(AT) + Σ (A((2)
sE|t]
= + Σ
=E([]
Applying the corrected bound from Lemma F.1
| 912 - (2v2- B v (P p-
p-: Ppp ))²
8BB2 24 AM. log( Al -
n
192 [S] log( A 5 5-1
Using this tighter bound in our trace calculation:
Tr(V 4+1 S d. A 192Ba|S| log( ((AA 111)
n 5) 8-1) ndd
= dl (1
Hence:
det((V det(Vo)
(ee((V'+)) p (42)
Tr(Vi++)
log
d log
d
192B21|S) log(IA) 8 .5-1) n -- X
dl log
A 11
192B2t log(1AA) 8 8-1) ndd
d log() + d log 1+
Since deo( = Xd, the first logarithmic term cancels out:
det (itta det(Vo)
d -log 1+ 192 log( 8-1)
log
ndd
Therefore:
(e (v++))
A 1.2 1
(V. (V."' 3-1 5 2- log
det(Vo)
192B*T| log( A|] 8-1)
< 2d log
1
ndd
29

---

Published as a conference paper at ICLR 2026
Taking the square root:
192B2r1S log( 8-11)
| (V.")-- )- S 2d log 1+
ndd
Theorem B.5 (Regret Analysis for BRIDGE under Known Model), Let 6 S 1/e and 2 B Then,
with probability at least 1 the expected regret of Algorithm 2 bounded by:
( 114461111 6-1)
Ry - (2k3r(6) + oar(6)) log [1
ndd
In asymptotic notation, this becomes:
RT= = R -
WWBBBB+BB)BB. a (og((T//<6)) log
T|S 1 nd
where the probability parameter 8 accounts for the events
Exe-
Lemmal D.1
4 Lemma D.2
V
Eogline := {TT 11 }
Lemma B.1
Remark B.6. This result demonstrates significant improvement over Saha et al.
2023 's bound
of ① ((WVEB WB) dlog(TB/<á)) The key advantage lies in the term
log(1
T|S
which approaches zero as nd + oc, potentially yielding constant regret.
B.3 PRACTICAL REGRET ANALYSIS WITH FIXED OFFLINE DATA (KNOWN MODEL)
For fixed offline dataset of size n, our regret bound scales with horizon T
R7 - (
1 1188
CTSS) n d
where r VWV -
This bound reveals three distinct regimes:
1. Small T Regime (T|S) < n- nddd: Using log(1 + +z) ~ x for small x::
S n d
= o (r.TT. S//2/2
R =
Vn
2. Transition Regime (T|8) d):
R = O 0 (W W (B)
3. Large 7' Regime (T|S) > d):
RT O (r Vlog(T)
((( These regimes highlight two key insights: (1) with sufficient offline data (n (2( )), regret dra-
matically improves from O (lo((T)) to O(1) the dependence on T: and (2) feature dimension amplifies the value of offline data, allowing the same regret reduction with vdd times less data. This explains why nigh-dimensional problems may benefit more significantly from offline data.
As increases, regret transitions from logarithmic (O(log(T)) to sublinear (O( and even- tually approaches ((1) when n > TiSl, In the limiting case where n - oo, exploration becomes
d
unnecessary, and regret is bounded only by statistical error in the offline estimation.
30

---

Published as a conference paper at ICLR 2026
C OFFLINE ESTIMATION
C.I MAXIMUM LIKELIHOOD FOR DENSITY ESTIMATION
In this section, present Maximum Likelihood Estimation (MLE) for density estimation that forms the foundation of our concentration results. While these results are presented more extensively in Foster al. 2024), include them here for completeness and readability.
The analysis of MLE relies on standard concentration techniques following the well-established work of van de Geer (2000) and Zhang (2006), enhanced by new Freedman-type concentration inequalities developed in Foster et al. (024)) (Appendix B).
The key proof strategy connects MLE analysis information-theorett measures via Rényi diver- gence of order 1/2,, written as D1 (PlI))- Specifically, the approach bounds expressions of the form -n log (By-g- [e log(g(=)/9' (=))),, which equals 3/ (gl2(")l"") This term is bounded ing Freedman-type inequalities for adapted sequences, which provide high-pree bigh-probability bounds of the form Σ (og(EE-1ee--))
S ΣT Xt + log(6-1). When combined with union bounds over e-nets, this yields tight concentration results for the entire function class. The approach also
leverages connections to Hellinger distance through the identity (2,),9") = 1 ((2)g
providing geometrically interpretable guarantees.
To handle infinite classes, we introduce tailored notion of covering number for log-loss:
Definition C.1 Log-Cooerin Number). For class g A(X), the class g' X is cover if for all E G, there exists g' E G" such that V E E
log(g(a)/s (x)) 6 The size of such cover is defined by (9.
Consider the data Dn {æ; he(m] consisting i..d copics of x ~ g" where g" E A(X). We have class G C (X)) that may or may not contain g" The density MLE estimator is defined
arg max
Σ
log(g(z;))
(5)
9E9
KE(M)
Lemma C.2 (Maximum Likelihood Estimator Bound), The maximum likelihood estimator in Equa- 8,
tion has that with probability at least
6 (G, 45 +
H²
inf 2>0
inf log(1 Dxa
n
gEG
In particular, if G is finite, the maximum likelihood estimator satisfies
(² g.) 6log(2(91/6--) + 2 inf log(1 + Dx=(0*11)))
n
gEg
Note that the term geg log(1 + x (gg)) corresponds to the mis-specification error, and is zero if g" E G.
C.2 MLE OBJECTIVE OF DATASET OF INDEPENDENT TRAJECTORIES
Given a data set of reward free trajectories D (7y (ee of trajectories of length // where {Ti} iiLd 7 ~ PP... The distribution Pp- is assumed to continuous w.r.t to the Lebesgue measure. It is characterized by the policy density density P = P where IT, P characterize the policy and transition density spaces. The log-likelihood of the with for policy и and a transition /' reads:
(=, HE(H)) IT and the stationary transition
(T, P)
Σ log [P(st)
(i sf)
II 1615
P(s) of
n iE|m]
The maximum likelihood objective over the density class {PP))e..PE for the dataset W!!
H
max PEI
Σ Σ
Σ
(6)
xE(n] JE[M]
vE(n) ==
31

---

Published as a conference paper at ICLR 2026
C.3 CONCENTRATION BOUNDS
In this section, we provide concentration bounds for the MLE estimators of the policies and the transition model, well for notion of concentrability coefficient. The important takeaway is that the control of the error, i.e., the decay of these concentration bounds depends only on values known the user. This will allow to compute confidence policy sets based on these bounds.
C.3.1 POLICY ESTIMATION
Define the log-loss behavioral cloning estimator for dataset D described in Appendix C.2 as
Σ Σ
π
arg max
Tlll
(E(M) hE(H]
which is from Equation (6) equivalent to performing maximum density estimation over the density
class {PP- well- Similar to Theorem (cf. Foster et al. (2024)) define the following
Definition C.3 (Policy covering number). For class II C {TA S 5 A(A)), say that II' C
{mp S + A(A) is an c-cover if for all ı E there exists n'' E II' such that
(als)
log
Se V(s,a,)) ES Ax
(als)
We denote the size of the smallest such cover as No (II,
We state the following theorem from (Foster et al. 2024 Appendix C):
Theorem C.4 (Generalization bound for log-loss BC, general policies). The log-loss BC estimator
(Equation 7 satisfies with probubility 2 1 -
6 (T))//H6--1) +g
BC PP-) S inf
n
in particular, II is finite,
H2 0C .PT.) S
6. log
|T| 8-1)
Proof. See (Foster et al.
2024 Appendix C).
Corollary C.5 (Generalization bound for log-loss BC, deterministic, stationary tabular policies). Il = i. i.e the set of deterministic tabular policies, for the log-loss BC estimator Equation 7
holds that with probability at least 1 5,
(PP 1P.)) 6- SS| log A --
7
Proof. We have 11 ||[|s].
we have stochastic rather than deterministic policies, we need to determine (1 e)). This can be accomplished using discretisation argument, where we create finite e-net that ap- proximates the continuous space stochastic policies within the desired error tolerance.
C.3.2 TRANSITION MODEL ESTIMATION
Here we can give similar argument as for the policy log loss BC estimator. We define the following estimator
P
arg max PEP
log(P(5)+1ls)..)
(8)
iEIn) 1=0
which is from Eq. equivalent performing maximum density estimation over the density class (IP Trep. Similarly, define the following notion of covering
32

---

Published as a conference paper at ICLR 2026
Definition C.6 (Log covering number for stationary transitions). For class of stationary transition probability functions P C. : x A - A(S)) we define that P c - ((S) an
e-cover if for all P P there exists P' P' such that
(( ('(s'ss.a)
log
SE V(s',8)
We denote the size of the smallest such cover by Werans Assumption (Realisability of transitions). We assume the true transition density to be in the model class ie P
We can now give similar guarantee as for the log loss policy estimate but for the transition estimate Theorem C.7 (Generalisation bound for MLE transition estimator). The MLE for transitions (Eq. satisfies with probability at least 1 -
6 (Tl +
(P p
Pp-)
< inf
Proof. Given valid e-cover of P from definition C.6 we have
Pr
P P(a (n)
log
log
S cc. H.
Pp.
P' ('(s++1 shy an)
This means that we get a valid e H cover for the trajectory density class. The bound follows as direct application of Lemma C.2
Lemma C.8 (Log covering number for stationary, tabular & stochastic transitions). For class of
stationary transition probability functions P C {P: S x A A(S) where |S x Al is finite (tabular
MDP), the 6-cover from Definition C.6 satisfies:
log(Nerame (P,e)) < S| |A| ([S) - 1) log (1+1)
Proof. The proof follows standard geometric discretization argument for a finite class functions (see Chapter 5 Wainwright (2019)) For a given > 0 we construct geometric grid:
G. {5, 5 exp(e/21 /2), exp(e)), ) exp(3e//2 /)). ... exp(ke/2)}
where 5 > 0 is the minimum probability and l is chosen such that the grid represents discretization of the continuous interval [0, 1] i.
2 log((1/0)
8 eke(kke22)
Thus the grid size is at most:
2 log
19.1 <
For each state action pair (s, a) define P(s.|s, a) p. for e [S]. Note that for the first 1,....|111 - there exist di = Pd ('(ss11, a) E G. that satisfies by construction
exp(-e/22
Pt qi
exp(e/2)
For the last state i -= (8), we need to determine disD close enough to P|s)
Let define S, = > 11--1 qi and S, : > 1511
p; we have the constraint
S P
Ss = S -
From the bound on the first 1 - -|S] elements we have
Sy cxpppp < Sp S. cxp(c/2)
33

---

Published as a conference paper at ICLR 2026
For the ratio of the last probability
P|S
1 - Sp
ØssD
S
have the following condition such that we have P1sl
2 (xp(-c)
9151
cxp(-c)
Sq S exp(e/2) exp(-c)
Similarly for the upper bound, we have the condition
exp(e) -
Sq S exp(c) - exp(
Combining both constraints, get
exp(e) -
exp(c) -
Sq min
exp(e) - exp(-epp (e2) exp(e) exp(-e/2)
By Taylor approximation, this boils down to
2
Sq S 3
Hence we select only the combination of points that satisfies
< Sq -
It remains count the number of points in cover, i.e, the first IS 1| that satisfy constraint
(number of grid points) 1S-1| s | $1-1 s ( (og(
18|-1
+
Going across all state action pairs, and taking the logarithm, we get
([2l08(1/0) (1))g
log(Werans (P,c)) < [S]AA[(S 1) log
+ +1).
Choosing Oee) yield the result.
Corollary C.9 (Stochastic, stationary, tabular transition setting). For finite 1S x A) (tabular setting) and assuming the transition density class to be stochastic and stationary we have with probability at least -
H (PPT".PTT" S O (SPLLA1lg(nHH88]
where for the theoretical optimal constant Ctheory
Proof. From our lemma on the covering number of transition functions, we have:
( +
H
log Nirans (P, (/1//1) s |S|AIi 1) log
For large z. we can approximate:
log
+ +1) ~ log
Substituting this into our bound:
61og(2) + 6]5]][A[([[ 1) log (H) + 6 log((-1)
H22 1PP < inf
+
6 (log(2) + 6D log H) - 6D log(s) 6 log(ō-1) + +
inf
520
34

---

Published as a conference paper at ICLR 2026
where D = | 1) for brevity.
To find the optimal E, we differentiate with respect to and set to zero:
d 6 log((2 + 6D log(H) H) 6D log(e) + 6 log(o=1)
6D
+
+ +1=0
de
TLE
6D
6
-
Eopt
n
Substituting this optimal value back:
6 6log(2) 6D (Dlog(H)) (H) 6D log
6D + 6log
6D
H² (TPT (PP ....) ك
π
n
(2) (ollo(HH) 6D (6D) 6D log (n) + log
6D
6 log((2) + 6log(d 6
6- log
nH 6D
+ 6D
n
For large state spaces where |S] 1 Rd |S]. and defining D | this becomes:
6 (og((2) + 6log(8 + 6. log
nHl
+ 6D
(PP....77))
6n
n
For large n and D, the dominant term is get:
6D log(nH))
and we can combine the logarithmic terms to
n
H2 (PT PP-)) = |SI loggAHo
n
Note that the constant 6 appears in the full derivation. This completes the proof.
L
C.3.3 CONCENTRABILITY COFFFICIENT UPPER BOUND
Definition C.10 (Concentrability coefficient). We define the following quantity as the concentra- bility coefficient:
(s, "(..)) dp (s.a)
C( BC xx*
sup [E|H] (s.
sup
measures the maximum ratio between the state-action distributions induced by policies BC and under the true dynamics p*
Assumption (Minimum visitation probability). There exists a constant Tiinn such that for all state-action-time time tuples with non-zero probability under the optimal policy:
min
(s,"(s,a) 2
7min
(d (s.))0
Lemma C.11 (Concentrability coefficient bound), Consider a policy estimator BC satisfying
HP RC (PPP","T")) S.
Then, under Assumption the concentration coefficient is bounded by:
CC BC x- 5 1 2
Ymin
35

---

Published as a conference paper at ICLR 2026
Proof. We will begin by upper bounding the numerator using the condition the Hellinger dis- tance, followed by lower bounding the denominator using concentration.
For the upper bound, note that
sup dd
Recall that the state-action distribution dp. (8, a) is the marginal distribution of the trajectory distri- bution at timestep I. Explictly:
t. (s,
( 0, 0, =a,
where T-L denotes all time steps in the trajectory except for time t. and PPp- (T) is the probability of trajectory r under policy æ and dynamics P*.
It follows that
TV sC a "xpp''= =2 (VP (FP (st = a). PT. (st = s,a, = a))
2 TV TV (ID9 (Pp.,,PT")
2 HP (PT S2
By assumption]
1
we have lower bound on the minimum acttonnction visitation probability:
min (s,a.t):d (s,a)>0
Vmin'
Finally, we combine the upper bound the numerator and the lower bound from assumption to get v(a, s, s.t dp. (a, s) > 0:
= = suPo,s,t 1dp-.- "(s,a) (s, a)l
CC -
inf inf (ppa
2VR.
< + inf an... (8,"
$ 11 2/R R
7min
This completes the proof, giving us a deterministic bound on the concentration coefficient that de- pends the Hellinger distance between trajectory distributions and the minimum visitation proba- bility of the optimal policy.
C.3.4 CONFIDENCE SET CONSTRUCTION
In this section, we will derive a distributional confidence set on the trajectory space in the form of a hellinger ball, accounting for the error of the MI.E density estimates BC and P. We start by presenting the following in between result
Lemma C.12 (Technical results), Assume finite state-action space S x A (tabular setting). VT e I1 where πT" is the true policy and p P are the true and estimated transition models, the following bound holds:
H'PPT PT.) SH H. C(T,T")
HPP,', PP..).
p.
where
d p (3,(
C(T,T")
sup
sup
|E[A] (s.0) Sx "s (s,a)>0 dF. (s,
36

---

Published as a conference paper at ICLR 2026
Proof. We derive the proof in three steps:
Step
PP. S Σ det
H² (P())s))))) P"
8E[H-1
Step 2:
H2 (P(.)s), ar). pe (118
E Be
S CrT, x²) B (ssnaa)mapp H² at)) PM (-1ss,
Step 3:
HP p ,PPT)
1 2
E
(s [H2 (P)
H
Proof Step 1:
(PP, pp..)=1. f (o(s)) II (aa st) st
H-1
St) Psc 1s- a az)dT
= - / pp- (T) mo(5o) I1 x x (sr) / P(ss+1 8x) P* (8t+ 18t, az)
dr
(o(80) I T(a (st) (8241181,
f (T) H-1
P(set1/8e,00) dr.
II
(*1411, Ue)
Next, we define
P(se+1186,0) 0z)
(1($1+1. at, st) = V Pa (S S1, az)
Te(s,, 0z) = [ V (e) $t, as) = / pr ("(((ss,,ai) arld', s1, adds.
Notice that ?/ is a BC coefficient, ie, (0(s,, a:) ())
Using notation above:
H H p: Pp..
E
II (0(ss)))
Using conditional expectation (law of iterated expectation) we change the distribution in the expec- tation from FT. to the so called state-action distribution d'p.. To show this argument, we show it for state action pair (oo, So.81) $1). The rest follows by using the same idea:
H 1 1
H-1
Ey p..
II
St, as)
= Egpran
a so, an))
Ea, Ea, ulls
a (r(s s1 II t=1
t=0
mo(so) TI (1 (o) / (r ao) an(s1, so, s0,
$0.00
H
II
as ( St. ai)
= -/ Hu(so) Ti (T(aulsu)
(o au)
37

---

Published as a conference paper at ICLR 2026
Notice that
/ pp- =: (so ao) Marginal over (so. ao)
po(()) =I(aol50)
Using a recursive argument, it follows that
H-1 II
(TP,, p. 1P7.)
E
(s St, az)
11
t
Using the fact that
II
24 Σ (1 xz)
Vo, E [0.1].
and that 74. E [0, 1jvt, it holds that
2 p. 1.p..).))
5
E Baps (1(((s))))))))))
1=
IP(P((ss,a).
Proof Step 2:
( 0c), a:))] = ds - P()
(s,a) (s,'(),)) (P((((ss)))
(s,a)
(s,() 8,0 (s,a)
Sz. (s, (2) P*
By definition of the concentrability coefficient:
dp. a) dp''' a)
((,,T")= = sup *E[M]
sup
( (s.)))
(s,)20
Therefore:
(p)(s,)) C(a,T") Vt v(s,a) where 'p:'20
20
d (s,a)
(s,
Proof Step 3:
38

---

Published as a conference paper at ICLR 2026
Starting from previous expression:
H-1
H (PP pp. = II t=
1 (m(ss,
We define
F2 = 1011-1460 Vi(s,, a,) (P),, (1ss,,, at)).
Using the fact that (1 x) e x for all 2, it follows:
H
H
I (1 x.) S exp
33
By the second-order Taylor expansion of the exponential function:
H
H
H
1
exp
24
2
1=1
Since 2; for all we know that
Σ Di
S
H, which gives us:
1
H
Tt-
2
Therefore:
H
2
H²
(1 2
Σ
24
Z4
2
1=1
H
Σ
24
2
H
H
2
For the bound 112 p .T.) 2 1 "
Ij hold, need:
H
Σ
1
x
2
H
1=1
1=1
This is satisfied when:
2(H - 2
Σ
H
This condition is typically met for good estimators where Hellinger distances are small. For large H, the bound approaches 2.
Under this condition, we can establish:
H-1
22 p.
P.T))
>
Σ
(H2(((-)s)) a1), (
(" az))].
H
39

---

Published as a conference paper at ICLR 2026
Lemma C.13 (Policy density confidence set). Assume that the following events hold:
}. such that P(E1) 2 81,
F1 = HPppp pp--) S Rí (6)))
Eg HP(Pp'PPl) R2(62)
such that P(E2) 2 82.
where x BC and P are estimators of the policy and the transition dynamics, respectively. Then, under Assumption the policy set
1 S R1 R2 (1+ v(++
2/
C n WT:VHR(P
p. (
(2
H
Tmin
is a confidence set of level 1 ő = 1 (61 + 82), i.e.
P( E 11 2 1 - (81 +
Proof. Define:
HPPP Pi: PP) =: (1, (T2, Pa)ll
where || |
== ||
||
We can then decompose by the triangle inequality: ([))))()))-
[[TT", -
(c BC P)] s |1(==1, ,P) - PP)
+ ||( P²) Bm PT)
+ (1 BC p*) - (7 BC P)]
From event Eg, we can bound the first term:
|1(TT, P)) (TT" ,') S VR2
and from event E,, we can bound the second:
[I(T*, PP) (mBB,,P)) PP))I S / R.
Lastly, using Lemma C.12 we can bound the third term:
[1 P*) - Bc P)] S V C(TBC,
m²) H [1(==,, P) (m", P*)]]
and by Assumption and our concentrability coefficient bound, we can bound it further:
2/R
CC π-" S
Yimin
Then, assuming events E1 n Ey hold jointly, with probability at least 1 - (61 + 52), we have:
[[TT", P) (,BBC))) / Rı + RR2 (1+
7(1+ 2 2/R H
7min
Hence, by construction, the set:
Rr (1 (1+1/ +++(1+++++ 20 Umia
My (TT) IT: [1( P) BC P>]1 / Rí VR2
H
contains x" with probability at least 1 (61 + 62).
40

---

Published as a conference paper at ICLR 2026
C.4 PERFORMANCE GUARANTEES
We apply our method of constructing confidence sets based on distributional guarantees for maxi- mum likelihood density estimation the tabular reinforcement learning setting with state space S and action space A. We consider deterministic stationary tabular policies (II = 115) and stochas- tic stationary tabular transitions, though the method versatile to other settings with appropriate adaptation of the corresponding covering numbers (cf. Theorems
C.3 and C.6p.
Let BC be the log-loss BC estimator (Equation 2 of the true policy π², and P be the MLE esti- mator (Equation (3)) of the true transition model P The concentration bounds for these estimators are, with probability at least 1 - 61 and 82 respectively:
4 |8| log((AA() 0
HP Pp.) < R
(Corollary C.5
HPP pp.) - R2 4. S.S
|A| log( Ho H
(Corollary C.9
T
Additionally, we use Assumption S that the optimal policy has a minimum nonzero visitation prob- ability. Under this assumption, the concentrability coefficient is bounded by:
2 VRi
C(r = 1+
Ymin
Theorem C.14 (Offline policy confidence set). Assume the setting described above and Assumption with d1 = 82 = 8/2 and define
V 4 [S| log A 2/0),
8 = / 4. | | log(nH 2/8).
Then, the policy set
{ T:
(1+
(I+v(1+
2/R2
H2 (P pr
v R1 C R2
HH
Ymia
confidence set of level containing x with probability least 8. The radius of this confidence set is explicitly:
8 Vn Vn
(1+ (1+1/ H 11+ Yiiin
2xx
Radius
/n
Proof. The proof follows directly from Lemma C.13 by applying our bounds on H2 (T H2 (IPT. ..F.), along with bound on the concentrability coefficient from Assumption Setting
PP.. and
81 82 8/2 and substituting the appropriate values gives the result.
D ONLINE ESTIMATION
The underlying setting described in Section 3
D.1 ELLIPTICAL CONFIDENCE SET
For completeness and to make paper self-contained, provide brief overview of the online preference-based learning approach used our method. The formulation presented this section closely follows the work of [ahaa al. (2023) and Faury et al. (2020). with adaptations specific setting. We include this background to help the reader understand the elliptical confidence set construction that forms foundation for our theoretical analysis.
In the logistic model, a natural way of computing an estimator w, of w given trajectory pairs ((r),7 72) and preference feedback values {or 1-11 is via maximum likelihood estimation. At
41

---

Published as a conference paper at ICLR 2026
time the regularized log- likelihood (or negative erosspentropy loss) of a parameter can be written as:
of log(o((0(7))) - w))) w
2
t=1
+(1 log (1- (((((())))) - <(T²), w))).
where À > 0 is regularization parameter. The function L is strictly concave for À 0. The max- imum likelihood estimator WrLLL can be written as w. MLLEE arg mäX 2 (w). Unfortunately, WALLE may not satisfy the boundedness assumption | so instead make use of projected version of w. M.M.F. Following Faury et al. (2020), and recalling assumption we define a data matrix and a transformation of w. given by MTD
V, RAL +
E - -(T1))
8=1
1-1
(e(w)= = Σ ((((T))) - - () (o(+)) p(T))) + Aw
Then, the projected parameter, along with its confidence set, is given by
w proj = arg min
[19x(w) - 96 ( MLE I|v,",
w s.L Wi
C( = (w s.t. |w lll.v. & 2x3r(5))-
We restate a bound by Faury et al. (200 that shows the probability of w. being in (6) for all t 2 can be lower bounded.
where Be(0) VAW + /log(1/0) + log (1+
LB RAd
Lemma D.1 (Confidence set coverage). Let 8 E (0, 1] and define the event that w. is in the confi- dence interval (ō) for all E N:
Eng (Vt w. (O))-
Then P(E
5.
Proof. This follows from Faury et al. (2020) with slight modification account for our bounded feature assumption.
This elliptical confidence set construction, which has its roots in generalized linear bandits (Filippi et al. 22100, Faury et al.) 2020). forms a critical component of our online learning algorithm. By maintaining and updating these confidence sets new preference data is collected, our algorithm can efficiently balance exploration and exploitation to identify the optimal policy. The confidence bounds ensure that with high probability, the true reward parameter lies within our constructed set throughout the learning process, which is essential for the regret guarantees we derive in the following sections.
D.2 NORM RELATION BETWEEN DATA MATRICES
For completeness, restate key results from Saha al. 2023 concerning the relationships be- tween various data matrices that arise in our analysis. These results are included to ensure the appendix is self-contained and to provide context for subsequent analysis. The full proofs of these results can be found in the original paper.
Saha al. 2023) establishes relationships between three key matrices:
42

---

Published as a conference paper at ICLR 2026
Vi The empirical data matrix constructed from observed trajectories
V The expected data matrix under the true transition dynamics P
Ve- The expected data matrix under the estimated transition dynamics P.
These matrices defined as follows:
1 KAIA+
(0())) (++)))
V. = KAIA +
( - - - -
V. = +AL+
(T)) - (m ( ( (
Where (ςτT) represents the expected feature vector under policy и and the true transition dynamics P while 6ºt (xz represents the expected feature vector under policy и and the estimated transition dynamics P..
Saha et al. (2023) introduces precision event that relates the empirical matrix Vr to the expected matrix V VT=
E = (Vr
p" 3 2VT (
Under this event, they establish the following bound: Lemma D.2 (Adapted from Saha et al. (2023) Corollary 1). Under assumption 7 event Eng Erper for any E [T]
conditioned on
|w- - | S aar(())))))
where (6) 20BW /dlog(T(1++2))) 28). Furthermore, if < 1/e, then P(E n Expe) 1 - log, T.
Additionally, Saha et al. 2023 relates norms based on the matrix V with those based on Ve:
Lemma D.3 (Adapted from Saha et al. (023) Lemma 3). Let Eo be the event that for all t E N,
8'
))
1
|w!rl wollv, S v2(l wolly.
Σ 4 B 2W B,
+
where 8' = (1+1W/eja and 1B Then P (Eo) 2 1 8
Note that the bonus function B is defined in Lemma D.4
These norm relations from Saha et al. (2023) are essential in our regret analysis, as they allow us to relate confidence bounds across different probability spaces and bound the regret of our algorithm.
D.3 TRANSITION ESTIMATION AND BONUS TERMS
Note that the offline estimator of the transition probabilities based on the log-loss MLE in Equa- tion 3 when the state-action space is discrete, is equivalent to the following count-based estimator (derivable using simple Lagrange multiplier argument):
Nottne (s' (s'18, (8,a) a)
P Pomine (8' (8'1s, a)
Nottine (s, a)
43

---

Published as a conference paper at ICLR 2026
where
Nofflnne (8,a) = Σ
Σ
11 = s, =a},
iE|m] bE[#]
Notline (s' [s, a) ==
Σ
Σ
11 = s', =3, s, aa.
iEIn be[#]
This equivalence allows us to initialize the online estimation process with the count estimator from the offline data (see line in Algorithm D yielding the combined estimator for the transition model:
P,(5's,a) = Nottine (s' 8, a) + (o(''8,,)
Notline (s, a) (s,
From this estimator, we adapt two key lemmas from Chatterji et al. (2021) that will define our notion of bonus terms.
Lemma D.4 (Moment transition difference error). Consider the transition count estimator Pt from Equation equation g Further, assume the trajectory data follows a martingale structure adapted to the natural filtration of the problem. For any fixed policy E II and any scalar function f : R for all N:
such that [T) < y, with probability at least
Epy. [f(r]] - Epp [f(T) EE BFG
Σ NE(M]
an (1, =: Be((T,
where
H [S] (AA) log
(log(NN Natton .0a))
Ssnas (1, = min
2n, 1n
Ne(sn, an) +
Nattine ( (8h, an)
The term Br 41 serves as bonus term.
Proof. Our combined estimator incorporates both online data (adapted to the natural filtration) and offline data (assumed i...d). We can artificially treat the offline data as though it were adapted the natural filtration as well, by considering it as "past" observations. This allows to directly apply proof methodology from Chatterji et al. (202T) (Lemma B.1) to our combined count estimator.
The key insight is that the martingale structure of the estimation error is preserved when combining offline and online counts, with the benefit of reduced variance due the increased denominator (sh, ag) + Noftiin on)). This directly translates to tighter confidence bounds compared to using only online data.
We present stronger version of the lemma that holds uniformly for all policies Lemma D.5 (Uniform Moment Transition Difference Error). Consider the transition count estima- for Pt. from Equation equation Further assume the trajectory data follows a martingale structure adapted to the natural filrationn of the problem. For any scalar function f TT B. such that If(r)) < and for any > O, with probability at least 1 ō for all E N and all π E II:
[f(rr] - Eez. [f(T)] Epy. Egx Ar
Σ [E[H]
sa, a, (n,
te,
(:B.(7.m.6.c)
where
Esm.an (1, 6, :=
11 log((S)) (AI) + lo ([inH + log
(6 llgg (Nog(Nesssn.a + Nomorr (sk.ah))
min
2n, An7
Ne(sh, an) N Nomine (Sh, ap.
44

---

Published as a conference paper at ICLR 2026
Proof. The proof follows by applying similar techniques in Lemma D.4 but with additional care to ensure uniformity across all policies.
As before, convergence over the policy class II achieved by applying a covering argument and the union bound, following the methodology in Chatterji et al. (2021) (Lemma B.2). The additional term |S] log space.
artificially treat the offline data adapted to the natural filtration. The uniform
[44l1 appears due to this covering, which introduces an e-discretisation of the policy
The combined offline and online counts in the denominator (Ni an) Nottine (8n; an)) provide tighter uniform confidence bounds compared to using online data alone.
To provide further intuition, we elaborate on the meaning and significance of the terms B, and B, introduced in the previous lemmas. reinforcement learning literature, these would referred to as the empirical bonuy and true bonus, respectively. Both terms quantify the concentration of our estimators around their true values.
The empirical bonus (T 7, 6) represents the expected sum of state-action-leve uncertainty terms et Sa,.a, (1), 5) under the estimated transition model P,. Importantly, this term be directly computed from observed data.
In contrast, the true bonus 17, represents the expected sum of uncertainty terms San.as (17, 8, under the true transition model P This term cannot be directly computed as it depends on the unknown true model.
For our regret analysis, we need to relate these two quantities. The following lemma provides crucial connection, showing that the empirical bonus B, can be bounded in terms of the true bonus B, uniformly across all policies æ.
Lemma D.6 (Relationship between empirical and true bonus terms). Let 1), > O. For all policies II simultaneously and for all E N, with probability least 6:
Be( S (T, 2H <) +
Proof. Define the function f:T + R as:
f(T)
et Sa (17, 8). hE[H]
Σ
By construction, B,( n1 8) Epy, [f(T)) Since Sa (1,5)
8) S 2ny for all state-action pairs, we
have (f(r)) s 2nH Applying Lemma D.5 with this f(T) and the bound 2nHH:
Epg [[(]]] - -pp, [S(T)] S E7y.
Σ
E (2n 8,6)
te.
NE(H
By definition, the right-hand side equals BT(TT, 2H,, d, te. Therefore: (M n1, 8) Ery, [](r)
E2p [f(T]]
+e.
From Lemma D.4 we know that:
Epg. [f(T) < Egz [f(r)] + B,( B. B.(m,n,0) = 2B, n)
This gives us:
Be(T, < _2,((2, () B((T, 2H, 8, +e
= B n,0)
+
Bi( B,(m,2Hn, +c.
45

---

Published as a conference paper at ICLR 2026
Therefore, the lemma statement follows.
This lemma is instrumental for regret analysis, it allows to work with instead of Br. The advantage is that B, involves expectations with respect to the true transition model p which makes more amenable theoretical analysis. By establishing this relationship, we effectively account for the transition estimation error and can focus on controlling the difference between empirical and true moments, which a more tractable problem our analytical framework.
D.4 POLICY SET II, AND PROOF OF LEMMA 4.5
Recall that we define the policy set II, to draw from in line 7 of Algorithm 1 as
I1. = { h E I
Va E 119-8
(Ø (TT',, uz ( + 71 110 ( (T) -000-(((0)) (T))V
+ BT(T, 2W W. 5') + B.(m', 2W B, 8') 2 0}:
where 8' -8online /2|_|||S) and 11 is derived in Theorem 4.2
The radius 7/t is defined
86 | ))
8'
2 1
Tt (2(4x8(())+ + (z) +2
Σ
Br T/. 2W B,
+
(1
where 8'
(1+4W/6)2 and 4 Then IP (Eo) 2 6.
gonline
Then Lemma
4.5 states that with high probability, x² E II Vt (T].
Proof of Lemma 4.5 We begin by conditioning on the following events:
Foftine
(x
E [g
from Theorem 4.2
Ew from Lemma
D.2
confidence set for w²)
Eiz from Lemma D 2
(relation for data matrices)
Eo from Lemma D.3
(estimated norm relation)
Eg from Lemma D.4 (bounds on the bonus terms B₂)
By the union bound, these five events hold simultaneously with probability at least 58.
By the optimality of π², we have for any n':
0 s (6(=T)) ((T'), w²) = (Egp. x(T) (ET)) - Enzy, p. Φ(T), w*).
Then, by event Eg and defining f(T) = ((((), w"), we have from Assumption that [f(r)] < 2W B, which yields:
(é(T") ((m'), w²) (TT) -0 ( w²) Be(m" 2W 2, // B. 2W B, (/)
where the probability parameter accounts for any n' E II, which covers the case of the offline confidence set being the whole policy space (i.e., not having enough offline data for learning).
Next, we bound the term:
P (T* の (T'), w²) = (0 Ro (TT) - R² (I'',, w. proj + (T)) - l (TT', w- - wf
(
< (0 (TT" p (Nt w proj + (T²) - ( 1|1 w" "
46

---

Published as a conference paper at ICLR 2026
We can event Eg:
8'
)
2
1
||u, w" w"llv. llv. S (2 wa wallp?- + 2,
Be
9. N.2WB
+
883 A
Using events Ew- n Byp. we get:
||w w" lollv. S v2(4k3r(0) + (.) +2
Σ Be T, 2..WBB B,
+ =:
86 S61AA|SS
Putting these results together yields that n² E II, for E N under the event Fottine-
The probability of this event is at least 1 - 56 by the union bound of all the events we conditioned on. By rescaling 6/5, we obtain the desired result with probability at least
L
D.5 REGRET BOUND
In this section, we provide lemma as an intermediate step toward the full proof the regret analysis of BRIDGE. This lemma separates the upper bound on the regret into three distinct terms, each of which we further analyze in Appendix
Lemma D.7 (Regret analysis (unknown dynamics)). Under the following events:
Euggine
{x*
1-8
from Theorem 4.2
Ex- from Lemmal
D.2
confidence set for w*)
Evgr from Lemma D.2
reeation for data matrices)
from Lemma
D.3
festimated norm relation)
from Lemma D.4
(bounds on the bonus terms B₂)
the regret of BRIDGE Algorithm 7 upper bounded by:
RT 2
TT Torm
T
(T))
68 (
Σ
Σ
Be 4W W.B6).
CE(T
(E(1.2 LE(T)
Term
Term 3
where
Pr V2(4k3r(() (ar(()) + +4 V
Σ
Bi(T), A,, 24TeH2WW
iE(1.2)
and
(.,,(()) 20BW Vdlog(T(1+22))/
Br(6) VAW (og(L/0) 2d (1
TB Rtd
Proof. We start by writing
2r, (Ø(=T) )- - p ) (p(T)) d(m²), w*)
(TT)) (TT)
0 ? 10 (()((T)) (T*) 0 (m/), 2() 6(TT)))))) w'))
(0ft - (
d(m?),,")
47

---

Published as a conference paper at ICLR 2026
Then, by Lemma D.4 we have with probability at least 1 - 6 for each of the following:
2(0(TT) 0² (I"), w²) _ 2B.(= ( AWB,6) B,6)
(T)) o())), w²) B(( 4W . AWB
(m)) p(m)), - B, 4WB,6).
By the union bound, with high probability:
2r S (T*) - ) (T+)) )² + (0") w²) + B. + BW + +2B,(=", N4.,, 6.).
Next, we observe that:
( oft ( ) w²) + (
(T*) @² ( w*)
S (6" (x²) - o ( ) (0 (x*) 10 (m w.
+ +|ww"= - wrrilli, llv. (100 8² (r + 110² (x*) - ( (+t))lv
of
Conditioning on the joint event En n Faw- n Bype we have with high probability:
(of) (TT) (f w²) (0 (T*) 6f (m w²)
(T*) (TT) of (mz ) ( + 10 (x*) - 60 ( ) (गT)
+ (10)) の ( ( の² (क (
Using Lemma D.4 again, the following holds with high probability:
2(0(xT) (TT) w < 2B' . 5,6
( - (b(T)) r - [( AWB,6)
(0 (T+) - (x()))) w < (m 4,,, B,
Putting everything together, it follows that:
2r, S 2%t (IT) (TT @ ( + (T+) - L (T))
2Bc 4W 8) + (T) 4W + 4B, 4W B, 8).
Under the event TT' E 1I, from Lemma 4.5 and using the fact that T.. of E II, we have:
2r, S ( - (
AWB,8) ( 4. (T))l + (B,
Hence, the regret is:
RT Σ 2r:
(E(T]
Σ
(Tello
( -
+ 4B,(T],4WB.B) 4. + 4B.(=,,
(,
<E|2]
S YT
((PP((
of (T))I +
Σ
(E[T]
EE|T]
Note that by Lemma
D.6 with high probability:
(, 2WB,)² < (B, WB.
48

---

Published as a conference paper at ICLR 2026
Plugging this into t yields Vt::
tt v2((nBB(O)) (a)
B1 AHW B,W,B8&,0 c) + (T 8, + 24(t - 1)HWWB.
This completes the proof of the claimed result.
E FULL REGRET ANALYSIS IN THE UNKNOWN TRANSITION CASE: THEOREM E.1
In this section, we present the complete regret analysis of our BRIDGE algorithm. We recommend that readers first review Appendix [ where we analyze a simplified setting in which the dynamics are assumed to be known. This simplified case captures the core idea of our approach: constraining the set of policies considered during online preference learning using a confidence interval derived from offline behavioral cloning estimation (see Figure
The key difference the present analysis that we now incorporate the estimation the transition model. Specifically, first estimate the transition model offline and then this estimate as the starting point for online transition estimation. This approach reduces the error due to transition un- certainty by factor of (()/Vn), which is the same rate of improvement we achieve for the policy estimation through behavioral cloning. As we will show, this allows our algorithm to effectively leverage offline demonstrations to reduce both sources of uncertainty, resulting substantially im- proved regret bounds.
Theorem E.1 (Regret bound with offline-enhanced exploration (unknown dynamics)). Let n be the number of offline demonstrations with minimum visitation probability Yiuin O for state-action pairs. With probability at least ô, the regret of the algorithm is bounded by:
A.S--B2.VAALL Vun-tmn
B2 H 18p2 min { log(T))
Ri 2 Pr
T llg 1
d
Tern I
AATTH
H5/2WBVT
| |A/2/
+ θ HiS
H VT
V/nni
vn Jnin
1/4
Term
where
7 =
1 Volo(T) + HWBBS) min log(T), n. Ymiin
T
HVWB
and we have set to optimize the bound.
From this regret bound we can observe that as n + oo with fixed 7min > O: (i) Term approaches Ō((K + BW) B [ogg(T) + VHW B); (ii) Term 2, the logarithm approaches log(1) (1) = 0: Term all components approach zeto. The overall regret bound exhibits a vT dependence in Saha al.
(2023). However, this results a regret bound that can be made arbitrarily small with sufficiently high-quality offline data, changing the complexity of regret analysis without having access to offline expert dataset. This result helps in closing the gap between empirical results in applying RL. in real-world scenarios and theoretical works.
From Lemma D.7 we analyze the three key terms in our regret bound: the confidence multiplier (Term 1), the logarithmic determinant ratio (Term 2), and the bonus function summation (Term 3).
49

---

Published as a conference paper at ICLR 2026
Each term is examined in detail in the following subsections.
Term 1 = -T- = V2(4K (T( + (.))(())
1
+ 4
Σ AE(1.2) TE[T]
Σ
Be(T AHW 6,)) + 2 B,
T
Term 2 =
T
( 6F (x?))l7
[E[T]
Term 3 =
Σ
Σ
Be(Ti 4WB
(6(1.2 [E[T]
E.
TERM 1: ASYMPTOTIC BOUND
We derive an asymptotic bound for Term I in Theorem E. Lemma E.2 The auxiliary lemmata used in the proof of Lemma E.2 are found in Appendix E.I.1
Lemma E.2. The asymptotic bound on Yr can be expressed as:
- BB BW) Vdl)Vdlo((T)) + BIB)
TT= -
min log(T), Tmin
+ VTeHHWB
Proof. We analyze each term in expression "r separately.
Step Analyze v2(4k (8) + (a))(())
By definition,
(.) 20BW V /doo (
TB² kdd
3r( = VAW + V log(1/6) + 2d 1+
For (6), we have:
(.,T(() = 20BW (T(+ 2T)/0)
= o (20DW logo((12/0)
o BW (WB/ddlo (dlog((()))
For (r) we have:
TB²
3r(0) VAW + log(1/5) + 2d
1 sAd
B2
S VAW log(1/5) + 2d
(for large enough T)
xdd
2B2
V log(1/6) + 2d 2d 2d
xAd
O(VĀW v dlog(T) log (1/5))
Therefore, this term becomes:
V2(4K- (6) + (.)) =OkK- (VXW + /dlog(T) log (1/)) BW /8))
OOEVVW + +x/ + log (1/) BW (dlg((TT))
=O((K + BW) / (tlllllggggttt/lll(oaoll m BW (1)))
50

---

Published as a conference paper at ICLR 2026
For fixed confidence parameter 6, this simplifies to:
v (24k (r(() + (ar(()) O((x BW) (W))dlog(T))
Step Analyze T
This term (+)) and becomes negligible for large T compared to other terms.
Step 3: Analyze 4 (iE(1.2) Ete(T) Br(a), 4HW B, 6) 2
Using the provided lemma on the sum of squared bonus terms, Lemma H.5
Σ Σ
Br( 4HW B,
6,,) 4,
s (4HWB) min log(T),
T
Viuin
(E(1,2)
Ō 16//2 B². 111111 min log(T),
T
n Tmin
Ô B min [og(()), -imia
}):
For the second term inside the square root:
= W
Therefore:
Σ
Σ
BT( 4,) + 24TeH?W
(E(1.2)
T
1
16HH:W2B21S|22 min log(T),
O(TeH2WB)
n Ymin
T
0
16/1 min log(T),
O(ATTHHWWB)
n Timin
T
}
16H min log (T),
+ +O(VTcH&BB
n Ymin
H|WB|S) min log(T)) T
+O(
Ymin
Step Combine all terms
Combining all terms from Steps 1-3, we get:
1
TT = 0 + BW) dlogg(T) +0
+ HFWBSS) min log(T),
T
O((TeHlWWB) B).
Vinin
Expressing this with Ô notation hide logarithmic factors, and canceling O(1/T) O(1):
PT = δ (w+ BW) /dlg((T) + H(S min log(T)), T
VTTHHWB
n 7min
51

---

Published as a conference paper at ICLR 2026
E.1.1 TERM I ASYMPTOTIC BOUND: AUXILIARY LEMMATA FOR LEMMA E.2
Lemma E.3 (Offline-enhance) bonus term bound). Let be the number of offline demonstrations, with a minimum visitation probability Ymin > 0 for gute-action pairs visited by the expert policy n². Then, with probability least 1 28', the sum of squared bonus terms satisfies:
Σ TE|T] A=1
c(t) ( 5)) S 321? (log((()|A(()) [S|
[nnH
+ log
(llg((H))
T
SS log
1+
71 YYin
where Steach the number of state-action pairs with non-zero visitation probability under the expert policy.
Proof. Step 1: Express Modified Bonus Terms with Offline Data. We define modified bonus term to incorporate offline data:
U
e00) (s, n,,) min
2n, /n Not(s, a) + Ne(
where U = H log([8||A[[t) + [S] log
AnH
+ log
6 log(())
Step 2: Express the Sum of Squared Bonus Terms.
Following Saha's structure, but with our modified bonus terms:
c(t) S (c,,,)))
[E[T] 1=1
Nr+1(s,a)
H Hlgg((S]|A(1] + [o] 1nH
+ log
Glog(1)
ΣΣ
min (4n 167
Not a) +
Step 3: Rearrange Account for Offline Data. The key insight: With offline data, we need to adjust the indices of summation. For each state-action pair, we've already observed it Nar(s, a) times the offline dataset. Therefore:
H
Σ
c(t) Saenhare (c,
tEfT' h=1
Na(e NN
H [og([S)|A|(H) + |S| log
in8
log
6 6log(t")
Σ
min 4n2 167
t'
xESaEA
(==Na(
where t' represents the total count (offline + online).
Step 4: Simplify Using Common Term. For clarity and following Saha al. (2023) approach.
let's s define:
6 Glog( (log(HT) HT)
V = H ( log
+ log
8'
52

---

Published as a conference paper at ICLR 2026
For sufficiently large t', the min is dominated by the second term:
Nar(s,a) +N
(s) (ssssss)+)+)rr (Nr+
V 16n V. ΣΣ Σ
Σ
16
(==)a(
N'=Naass.a+11
Step 5: Use the Harmonic Sum Property. We know that Σ Diza+1
I log (:). Therefore:
Na(x,a)- -Nr+1(s;a)
Σ
1 < log
(s + NN44(5,,) log (1+ Nr+1(s,a) Noti(s, a)
Not((s, a)
('=Nar(e,)++1
Step 6: Apply the Minimum Visitation Probability, With our assumption that d "p,"(s, a) for all state-action pairs visited by the expert policy, we have:
7min
Not 2 n. Tminn V(s, a) E Sreach
where Seach is the set of state-action pairs with non-zero visitation probability under the expert policy.
Therefore:
N)) Non(s,
Nr- (1, V(s, a) E Srewch
log (+
s log 1
n
Ymin
Step 7: Apply Jensen's Inequality. We know Ex,a (s, TH (total state-action visits in online learning).
By Jensen's inequality and the concavity of log(1 + x):
Σ log (1+ (1.1(s.a)
Sceachl llgg 1+ E(sa)sS (8,1 a)
H Tmin
Sreachl H "min
(Sou)
Since E(E,)) Nrt1(s,a) ST..
log 1+ NT+ (8, n H Ymin
TH
Sreachil -log 1
Syeach n H Vunin
SSech
Simplifying:
log 1+ (5,)(5,a) n H V/nin
< Srenchl log (1+ Sreach 7
T
Viin
(S.a)
For unreachable states, we can use Saha's original bound, but these contribute negligibly to regret optimal policies don't visit them.
Step 8: Final Bound. Substituting back:
(1) C (E, ()),, s 11nn V. |Seachl .og 1+ 71 Timin
T
(E[2]
53

---

Published as a conference paper at ICLR 2026
Substituting V and accounting for approximation constants:
H
c(0) SaLAiaL (6, ( 0)) - $3212 [Hlg(( + IS|
A4HH + log
(Glog(H))
8'
rE|T] A=1
T
S| log
71 Tmin
This completes our proof, showing explicitly how offline data (through n) and minimum visitation probability 7min reduce the bound on bonus terms, thereby reducing regret.
Squared Bonus Term Bound). Let O and 8 E (0, 1). Let n be the number of offline demonstrations with minimum visitation probability Ymin > 0 for state- action pairs visited by the expert policy. Define Eg((")) be the event that for all t E N and i (1,2):
Lemma E.4
5.2
Σ
< 12n H2
1.41m (2 (max (4n HI, 1))) + + 1 8
(E(1,2) t=1
T
+ 64n/² H Smachh log 11
n Timin
([4n/H) 1)
6 log
llg((H)) (T)
H log( (||[A)))
+ [S] log
+ log
8
Then (()) 21 28'.
Proof. We follow Saha et al. (2023) proof structure, beginning with the martingale analysis and then applying our offline-enhancee bounds.
The bonus terms can be expressed as:
2 Be(T tb )) + (
5
2
H-
( 1)
8
E
(6 7:
st +
(:
Pg
(e, 17, 2
E
of S
(1157)
Pc
Using Jensen's 's inequality (as in the original proof):
T-
of (e, n. 2 =))) HE
sh (c, 1,, = 27
Σ
Σ
(0)
E
stop.T=
(144)
4~ By (115))
Following the martingale analysis of Saha, we define:
カ-1
27
1-1
D = E
Σ
a (37)
Σ
( ())
(0)
si (111)
h=l
Since <.. 1) < 2n. we have |
< 8 and var!")
(oh (e.
s
1 H²
Applying the Uniform Empirical Bernstein Bound (as in the original proof), we get:
D
(9)
1 E
Ø-1
Σ
o ()))) 2
2
(115)
E=1
5.2
+n7 H 1.41n (2 (max (4n/ Ht, 1))) In
8
54

---

Published as a conference paper at ICLR 2026
Therefore, with high probability for i {1,2}:
TH-1
1- 1-11
E
Σ
Sh (c,),))))
2
sh ( (c,77 + 412
ei dimp,rTp
(-18))
1=1
h=1
5.2
+ 67j H
(1.4 In (2 (max (4n Ht, Ht,1))) + In
8'
Combining for both policies, with probability 1 1 -82"
1-1 1111
Σ xE(1,2 t=1
( < 2H
Σ
c(e,)) Senian
())
(E(1.2)
t=1 h=1
5.2 [L4 In (2 (max (4n Ht, 1))) + In 8 +1)
+ 12m2 122
Now, using Lemma E.3 we have:
(-1
Sanian (c, (1,. 6))) S V |reach -log 1
clea))
T
Yuun
f=1 A=1
where [og({$]|A|H)) + |S| log ( Indf 1) + log (log((H)
Substituting this bound and combining terms:
Σ (1
1/ 12 H2 (1.41nin (2 (max (4n Hi, 1))) + In
5.2
+ +1)
T
+ 64n HV 1Sreahh llgg 1+
Timin
Expanding V:
5.2
Σ 8/((1) < 12m² H² [.4In (2 (max (4n Ht, 1))) + In (E(1.) t=1
8' +1)
T
+ 64n² SSeachl log +
Vinin
AnHH]
(log(HH))
(log((()14(AT) + +SS| log
+ log
c
8
Lemma F.5 (Asymptotic bound for offline-enhanced squared bonus terms). With n offline demon- strations and minimun visitation probability Tunin the sum of squared bonus terms is bounded as:
Σ ie (1,2) t=1
so 20(121118) min log(7),
T Yunin
})
(()) hides logarithmic factors in H, [S}, [A], 8-1, and -1, well constant factors.
55

---

Published as a conference paper at ICLR 2026
Proof.
We start from the detailed bound of Lemma E.4
Σ
Be(m), )/EE8)) 12n H²
(141min (2 (max (4n²Ht, 1))) +
5.2
8' + +1)
(e(1.2) 8=1
4nH
+ 64n2 H
H log (IS]|A)H) + |S| log
+ log (6log(H))
T
/trechh log 1
7min
Analyzing each term:
Step First term analysis. The first term is:
12n H
Ht, 1))) 1.4 1.44nnn (2 (max HL,
5.2 In 8'
+1) ) O112 log log( log(
Since log (T) grows extremely slowly, and we 're using Ô notation which hides logarithmic fac- tors, this term is dominated by O
Step Second term analysis. For the second term, we have:
T
C Cf V |Seeach log
n Yiiun
where a constant and V log( ()) + [S] log
([1t An
log (llggHH))
Within the factor V, the dominant term is |S] log 4n asymptotically:
since it scales with |S]. Therefore,
Ö[SS).
Upper bounding Sreachl $ [S] as requested, the second term becomes:
| log
[1
T
T1. Yymin
Step 3: Analysis of log
We need to consider different regimes for this logarithmic
term:
Case 1: Small offline dataset (n Ymin <
T
T "imin
log + n Ymuin
log
n
(Tg(
log(n .mii))
(log(T)))
Case 2: Balanced regime (n 7min T)
log 1 1
log
0())
1 Ymin
Yuun
Case 3: Large offline dataset (n Tmin 7) Here we can use the approximation log(1 + x)) = x for small x:
T
T
T
log
I
Ymin
n Timin
Tmin
Combining these cases, we can express the behavior of this term as:
log
1 7/-in
O min log(T) (T),
Tmmn
56

---

Published as a conference paper at ICLR 2026
Step 4: Combining all terms. The first term H²) is dominated by the second term when |S| and is non-trivial. Therefore, our final asymptotic bound is:
(Be(th <o 20 min Log(()), (E(12) t=1
Σ
T
Tmin })
This bound correctly captures how the offline data affects the regret across different regimes. For small n relative T, recover a bound similar the standard one with log( For large enough n, the bound improves n2 Timin"
showing linear reduction in the bound increases.
E.2 TERM 2: ASYMPTOTIC BOUND
We derive an asymptotic bound for Term 2 in Theorem E. via Lemma E.6 The auxiliary lemma used in the proof of Lemma E.6 is found in Appendix E.2.1
Lemma E.6 (Upper bound Term 2). Term 2 has the following asymptotic result:
T KE(T]
1 (T+)
&P. (*f)ll?
T-88--B2. VAII-
① B2. B2. H- 18 min (2, log()))
Tlog 1+
d
Most importantly, as n + co, ie the offline data set's size goes oc, the asymptotic regret log(1)= = 0.
Proof. We follow standard argument from Lattimore & Szepesvári 2020
We start with the inequality
a < 2 2og(1 +u)
Vu 2 1,
which implies
A 11 2 Σ
log(1 + 12)))
TE(T)
1E(T]
Using the definition of V,, we have
P4+1 A. laxd +
Dot = A0r 21/2 -1 V1/2.
iE
Using properties of the determinant:
(e+1V = del(VV) del (T+ A2,
= det(Vi) (1+ | :)
det(Vo)
II
(1 + [[+1A0011
sE[t]
holds iff:
det((V+11) doo(
log
Σ log(1 + |A .).
57

---

Published as a conference paper at ICLR 2026
We can also use the linearity of the trace
[r(V==1] = [r( +
= d Σ
sE(t]
sE[d]
to write
det(Ve+1)
II
A - ā Tr(Ve+13)
We notice that
Ad 112 (T)) (
[10 (m)) 0 (m)) - (f + (
(T:)
- 21 P: (TT)
o a (m))l + 10 ( 0 po (Ti)
We can also bound
10 ) 8 ( - 4 R B².
From lemma
F.1 linking the Hellinger ball with the constraint moments, together with lemma E.7 for the tabular setting, get
a 3
H (1+ Tmin vn
2a
R = Radius
1 + /
vn
Vn
a
v |S| log( AA| -2/5)
8
4
|S
|A| log(n -2/8).
Now with result Lemma E.
we have
(T) (T))2
0o H 1 CT (FT, 1og((5]1A1/8)
(m+t
t
+
t2
t)2
(n + t)2
Hence in asymptotic notation.
2 2 (TT) (
110 [o (x²)
(m?))
2 22
p (TT.) (
| Po
Po (m
S B 1A H
Ô B² H HSS m(n +t)
vn- Tnnn
We need to sum over i E [T]. Therefore, by using
t T n(n + t) In
T
~
1
n
1E[T
arrive
Σ
- -
(m/r)1) ( - Po
1E|27
s Ô B² B². min { T log(T)) }+ T S. B² VIA H
Tinin
This expression behaves differently depending the relationship between T and
58

---

Published as a conference paper at ICLR 2026
1. When T < n: Using In(1 2) se x for small z, get
T T
2
n(n + t)
LE
-01)
2. When T > n: We have In (1 + : = In (?),
so the sum is dominated by T
unified bound that works across all regimes is:
T log(()) })
Σ
n(n + = min
n
LE[T]
Hence the final bound yields
10 (m/) - - (0?
1E
Ô H..H--188 1.18. min log(())
$ Flo 1+
d
E.2.1 TERM 2 ASYMPTOTIC BOUND: AUXILIARY LEMMA FOR LEMMA E.6
Lemma E.7 (Bound on difference of expected features under estimated transitions). Let Φ T Rd with max, [|ő(T) S B be a feature map, Po be the count-based estimator from n offline trajec- tories following policy x² under dynamics P*, and Pt be the combined estimator after t additional online interactions. Then, with prohability at least 5:
R o (=) (B2 (
t2
(T
(n + 1)
where Cr(Fr σ²) πT) is the concentration coefficient accounting for distribution shift.
Furthermore, when combined with an additional error term of O (t). the overall bound simplifies to O (1) for all practical regimes.
Proof. We divide the proof into several steps:
Step 1: Martingale Structure and Concentration Bounds. Let F, be the o-algebra generated by all information available after interactions. For each triplet of state, action, and next action
(s, as a,,,)) 8'), define:
Xi(s, a, s') = 1[s; = 8, a, = a, 8:41 = - - P" a) Hs, 8, 8,a; = aa.
This forms a martingale difference sequence with respect to filtration {Fi)en Es,,(s,a, 5') -.
The offline estimator be expressed
a) Pd -
Σ
Xi(s,a,8').
Wo
sEoffline
By the Hoeffding Azuma inequality, for any (s.a) a) with Nos (s, a) 0, with probability at least
1 -
2 200(44)521A110)
PP(s' s) P'(s'|s,a)]
Nof Noffisee a)
59

---

Published as a conference paper at ICLR 2026
Similarly, for the online-only estimator Pontine (5)1,,a)
with probability least Ni(s.))
log (4|ST)AA//))
Pontine (s'(s,a) - (*
(s.a)
Step Bounds on Total Variation Distance. By union bound over next states, with probability at least 1 -|
[Po(-|s, -11bs
= Σ Po(s'|ss (s))sss,))
(2 1ogg(4)5(/////0)
S |S| V
Noss
Similarly for the online estimator:
log loo ((9((4))))))/))
pomtinee (-18,) - (1(
s |S| 111
N.(s,a)
Using triangle inequality:
[ontine--|s Pa(-ss;))la s Pontine (-1s, ()(s + 1I
Po(-ss
2 1log(4{{)2)/// + +1S|
2log(4)5(2)A100)
S |S|
Ne(x,a)
(lin
Step Combined Estimator Analysis. The combined estimator can be expressed as:
Pa(s'ls,0) (s, Noffline (s') (s'(s, a) + (s(s)ss,a)
Note (8, a) + Ne(s,a)
Nossline a)
Ne(s. Not Bime (s'ls, + Nof + Nz(s,a)
Ni(s'ss,a)
Noosstin(ss a) + a)(s,a)
Noss a)
Nr(s,a)
= =(1 (1-aree (l-ar(s,a)) (s(5)s) + an( (
Ne(s.a) Where as) Nossiim(s..0+ Thus:
P((s'(s,a)- Poo'))ss (01 a)(s)a) Po(s'Is, a) + (s( (5)ss,) Po('(ss,
a)) (Poontine (5'18,a) Po(s'ss,
Therefore:
[|P((-)s,)) Pol-(s,))ll as) |ontinee (-|s, a) Po
2 log (4|S|21A1/8) + |S] log (4/5))) (s(
Noffline (8, a)
Step 4: Accounting for Visitation Distributions. For precise analysis, we express the counts in
terms of visitation frequencies:
Nofftine a) = flif (s, a) H,
N₂(s,a) = t t p (s, a) H.
Here, 16 fline (8, a) and "n (8, a) are the average state-action visitation frequencies. This gives:
t t (s, a)
(s n. flife (s, a) + t pontine (8, a)
60

---

Published as a conference paper at ICLR 2026
Assuming the states in the support of policy have visitation frequencies lower-bounded by some constant с for both offline and online regimes:
[|P:(-|s, - -alaa))PPPoPls.... a)
c.c
|S|
21og(4/5T(AA10)
1
1
n. n.c.tcc
C.H
Vt
vn
t
2 [ogg({(()|AA(0))
n n+t |S|
+
H-H
Vt
vn
= [8)
log([S||AA[5) at
1
1
H
n+t
VE
Step 5: Feature Expectation Difference. We begin with the telescoping decomposition:
(T) (00)))(((Tll = =| [Ø(T)] Exury [0(T)]l22
(T))l2
S B- -(s,))dd [IP:(1..,)) Po(-
To handle the distribution shift, we use the concentration coefficient:
P. ($,
(T(
1 (o.0))
1 Wif
By Cauchy-Schwarz inequality:
(s [((,,a) CT(FTT / Vlsayyrtirn [[(s a).
Applying this to our bound:
1o
(m) (T)
B. Cr(Fr,T,T') v (B [1|:((1s,,) Po(-ls,a)13
From Step 4, we have:
[| Po(-ls,a)l?? |S| log([S][A|/8)
)
H
11 n++1
V1
log log(1S11A1//5
|s|2.
+
VIn +
H
n n+t
= (1sp2 log({S)|AA10)
2t
H
(n + l)2
(n + t)2 Vtn
(n + 1)2
For large n and f, the middle term is dominated by the other two, So:
(P:(()), - Po(-ls,a)11+ < o (isp.. log([S||A|//)
(n + t)2 ())mm)
12
+
H
(n - t)2
Substituting back:
P of (T) B². H². (F o [||2 log log((S|[AA100)
t²
-
H
(n + t)2
(n + t)2n
-0(B--1 H 1 (|(()))))))) Cr(
x2 (n + 1)2
(n + t)2
Step 6: Analysis for Different Regimes. Let's examine the bound for different regimes:
61

---

Published as a conference paper at ICLR 2026
When >> (dominant offline data):
1 p (T) P (x) S B H |S 1og((S11AA10)) (Fr (F b
n22
When > n (dominant online data):
- o O B² H 1812 log((51141/8) Cr(F,,,,,)))
Step 7: Combined with Additional Error Term. When combined with additional error term of O we analyze the combined bound by comparing the orders:
When (early online learning):
(n + t)²
2
t²
2
(n + 1)3.. 7
71
71
Therefore, O ( dominates.
When (balanced regime):
t
71
0
(12 t)2
4n²
4n
t²
n2²
0
-
1
(n2 1)2
4n
4n
7
Both terms are O (H).
When t >> (predominantly online learning):
(n + 1)2
t
12
1
(n + t)²
n n
Since t >> have 1 < the second term dominates derived expression. When
combined with an additional error O (4), both terms are of the same order, giving an overall bound of O (#)
E.3 TERM 3: ASYMPTOTIC BOUND
We derive asymptotic bound for Term 3 in Theorem E. via Lemma E.8 The auxiliary lemmata used in the proof of Lemma E.8 are found Appendix E.3.1
Lemma E.8 (Asymptotic bound for offline-enhanced bonus terms). Let Eg be the event from Lemma E.9 which occurs with probability at least 26. Then, by setting T the follow- ing asymptotic bound holds:
Σ
+ (B..TT.ASB.B)
8)
(E[T]
ATTH
HORSBBT
+ S1 .T Vlog(T). |S ||//11 |
I ② HISh
n
Tmin
vn
7min
1/4
Proof. Starting with the bound from Eg:
Σ AB. 4SB,0) d) 4B,(7] 4SB,8)
[
S ET +
Σ
8B, SBS (.B.SB SHS,,,,,
[E[2)
62

---

Published as a conference paper at ICLR 2026
From Lemma E.9 have:
Σ
8B.(T) (HSB,,, (BB. 8USB,,,
1E
|ATH
+ SBR H T
|
$ Ō
H
(To
72 VYmin
Vn
Yiin
n//4
We set optimize the bound, which makes eT = 0(1). This constant term is dominated by the other terms for large T'
Additionally, setting + affects the log 32/1 log(32HH T) term inside the bound.
This adds lo'( factor, which is already absorbed in the notation. Therefore, our final asymptotic bound is:
Σ AB. 4SB,6) + 4B.(=Z, 4) (E|7]
ATTH H812SBVT + H T Vlog(T).
| 1/4
$ Ô
H|
+
Tiinn
VR
Ymin
n/4
This bound shows three distinct terms scaling with offline data:
1. The first term scales as Vn and represents the primary benefit of offline data for covered regions
2. The second term also scales as vn and captures the improved martingale concentration
I 3. The third term scales as nt and accounts for the diminishing probability of encountering uncovered regions
For sufficiently large n, the bound improves, but it's important to note that the third term has a direct linear dependence T (modulo logarithmic factors). This term dominates for large T unless scales appropriately with T. Specifically, with n = (T*)), the third term becomes ((1), and with O the overall bound becomes O log))), which is near-optimal.
This demonstrates that with sufficient ligh-quality offline data scaling appropriately with the horizon T. the sum of bonus terms can be made arbitrarily small, fundamentally improving the regret bound.
E.3.1 TERM 3 ASYMPTOTIC BOUND: AUXILIARY LEMMATA FOR LEMMA E.8
Lemma E.9 (Bound for summed offline-enhanced bonus terms). Let Eg from Lemma E.10 be the event that for all T E N:
Σ A AW 8, (z) (E
STT + Σ 8B.( SHWB, B, + (BB( SHW B,
Let be the number of offline demonstrations with minimum visitation probability Yauin state-action pairs visited by the expert policy. Then, invoking Lemma E.10 and Theorem E.1l Eg occurs with probability least 1 25, and:
0 for
63

---

Published as a conference paper at ICLR 2026
Σ
SHW.,8, &WW &HW B,
1E/7]
H-1
Σ
Lail (s 8HW B,
Σ
o (sSHWB. +I,
SE
where incorporates the benefit of offline data
W
/11////11
I=Ō
H VT.
Vmin
Ymin
n²/1
and P(E9) O (TH ( (og(n) represents the probability that at least one state-action pair encountered during online learning lacks good offline coverage. Furthermore, with probability at least 1 - 28;
Σ [E|
8B,(T), SHW,.HWWWBR 6, (8) 8HWB (.
32H2WB
6log(HT)
2048HW BV H log ())AA))))) + |S] log
+ log
SS
5
V n Viin
HVT + H VT.
|
+
Tuain VTl
n//
Using Ô notation to hide logarithmic factors and simplifying:
Σ
SHW (B. 8,
4E[2]
[A|TH
H5/2WBVT H VT. |
HISS
n
Tmin
Vn 7/min
n/4
This bound demonstrates how offline data benefits reinforcement learning through three mecha- nisms:
1. Reducing exploration needs for well-covered regions (first term)
2. Improving martingale concentration for covered state-action pairs (second term)
3. Decreasing the probability of encountering poorly-covered regions (third term)
All terms approach zero as n. co, though at different rates: the first two terms seale as 5/ while the third term scales n,74- This confirms that with sufficient high-quality offline data, the entire bound can be made arbitrarily small, fundamentally improving sample complexity reinforcement learning.
Proof. We follow the structure of the original proof, adapting it to incorporate our offline-enhanced bounds.
Step 1: Set up the martingale difference sequences. quences:
Consider the martingale difference se- H
[ SHW 6,
Σ
(e,8HWB, k.
1=1
64

---

Published as a conference paper at ICLR 2026
and
W-1 [B:( B,,,)
oo (,,
Each has norm upper bound 32// B, since (e 0, s 21j and therefore En (e, 1/
1), S
Step 2: Apply anytime Hoeffding inequality with improved bounds. Consider the martingale difference sequences:
H-1
[B. B, 8,
Σ
(c,8HWB,0)};)
and
H-1 8HWB
Σ
of (H,
By Lemma(E.1 which accounts for both covered and uncovered state-action pairs, with probability at least 1 - ó for all T e N simultancously:
Σ (E[T]
(BWW:,./WBB3..)) SB.(TT SHW SHWB,
H-1 (GSHWB.6) +I.
Σ
(0) S8 Ll
(.8HWB,6) +
Σ
(0)
LE|T
where incorporates our rigorous analysis of martingale concentration with offline data from Lemma E.12
H0/2WBTT
| |///4
I=Ō
+ H VT.
/uinn
n//
The second term accounts for the probability P(E9)= = (TT S|2 log(n) that at least one
state-action pair encountered during online learning lacks good offline coverage, while maintaining the proper VT scaling in the regret bound.
Step 3: Apply our oflline-enhanced bound. Now, to bound the remaining empirical eтror terms, apply Theorem E.1l For each policy Tे. i {1,2]:
h Σ
Σ (E[T] A=1
Laaa (H,8WB, B,8)
32H + log
(6log(HT))
< 64HWB. B H Hog((S)|A))H) - |S] log
SSeachh 2/ Tmin
Step 4: Combine the bounds. Summing both policies:
65

---

Published as a conference paper at ICLR 2026
8 (E(T]
to (e,8HWB.6) + Σ
(6,8HWB,6)
32H2W
log (6log(1[T)
T
8- 64HW B H [og([S]]4)HH)) |8| log
Sreachh
2 Tinin
32 B
Glog HT)
T
W048H B H log( log( (S]AA))) + |S] log
+ log
S
V n Vinn
Step 5: Express the complete bound. Therefore, with probability least 1 26:
SB. 6,6, + (1, 8HW 6)
EE
32 B
(6log(HT)
- 2048HW B H log( (S)[A))) + |S] log
+ log
|Sreach
V
Vuni
+ HVTT
|||/3|A||14
+ H VT.
Vn
Ymin
n/4
Using ① notation to hide logarithmic factors and simplifying:
Σ 8B. 8,6 (B. SHA.TT..WDDDD SHWB, ,,
1E[2
AATH HVBT H VT.
H|ssy
n 7min
7min 7min
n/4
This bound demonstrates several key insights:
Sublinear regret: All terms scale as VT, maintaining the crucial sublinear dependence on horizon. This ensures that our regret doesn't grow linearly with T.
Offline data benefits: All terms decrease as n increases, but at different rates:
The first two terms decrease at rate 1 V and capture the direct benefit of offline data for state-action pairs with good coverage
The third term decreases at the slower rate of 7,77 and accounts for the diminishing prob- ability of encountering poorly-covered state-action pairs
3. Complete dependence offline data: Unlike traditional online-only bounds, analysis shows that all components of the regret can be reduced with sufficient offline data.
With sufficient high-quality offline data (n - with fixed Ymii > 0), all terms approach zero, firming that offline data can fundamentally change the sample complexity of reinforcement learn- ing.
Lemma E.10. Let n,, c > 0. For all n simultaneously and for all t E N, with probability --.
Ba(T, 5 2B, 5, +e.
Proof. Recall that
(TT, n, 0) ESS (1b11)
Σ
San.a (1, 8)
66

---

Published as a conference paper at ICLR 2026
Let :T R be defined as,
H-1
f(7) = Σ
Senion (1))
elo
is easy to see that f(r) E (0, Hn for 7 r. Therefore, direct application of Lemma in Saha et al. (2023) implies that with probability at least 1 - 8 and simultaneously for all x, and t E N,
BI, - (1811)
(116))
Σ C (7,)) B,(TT, 2Hm, 6,) +e.
(1)) Since <.. (e, 17, 2 (n,, 8) for all 0, 0,0 8 A and (,, is monotonic in 7,, conclude that
H
E 92 7
Σ
cll) as (1,
< E Eeppp.r
e(t) Sah (e, 0)
Σ hml
Sa (c, 2H 8)
e(t)
B,, 211,,
Combining these incqualities, the result follows.
Lemma E.11 (Bound for non-squared effline-ehhanced bonus terms). Let n be the number of offline demonstrations with minimum visitation probability "Imin 0 for state-action pairs visited by the expert policy. Then, with probability at least 1 6:
8-1
Σ (ET] A=1
Saca (c,8HSB,
(0)
32H²SB
(6log(H1) (T))
T
64HSB/
H log([S]|AA[A)
+ + log
+ log
11
2
nt Tmin
Proof. We follow the approach shown the provided image, adapting it to incorporate offline data. Starting with our modified definition of bonus terms that incorporate offline data:
U
el0) (e, min 2n, / Notr(s, a) + Ne
where U = H log({S]]A{HH) + log
32 + log (6log())
Rewriting the sum by grouping
state-action pairs:
11
Ny
U
el)) Sa (c. (HS..B - - -2
Σ
min
16HSB,32HSB.
(o +
(E[T] A=1
SEA
For sufficiently large values of NoR(s, a) + 6, the minimum is dominated by the second term:
Nx41(
NT41(8.a)
U
ΣΣ RES
32HSB
32HSBVU
ΣΣ
Non
Non a) +t
BEA
The key adaptation is reindex the sum account for offline visits:
67

---

Published as a conference paper at ICLR 2026
(s.a)
Natt(s.a) Nr++ (s,a)
Σ
a)) +t
#ES aEA
aEA
++1
where l' represents the total count (offline online). Using the property of the sum of inverse square roots and the minimum visitation assumption:
Nanls (anosaa)+Nr++4(0
22 Not(88, + (8+1(8,0) 2/ Na
v
2 Notrls, a) + NT+1(5,a)
Nr+1(8,a)
x //
v N))(s.
Nor(s,a)
NI+1(s,a) (or((s,a) v(s,a) E Sweahh
2 V
H Tmin
Applying Jensen's inequality:
N141(8,0)
E(an)eSma N1+1(s, a)
Σ
2
21
v Non a) 2 1
H Miia
H. Yuin
(m
TH
< 2 Steach
n H. Ymin
T
2 SSeach
n Tmin
Substituting back:
H- 1
Σ
2 SaL. (c,8HSB,0) < 32HSBVU 2 |Sreach
Tmin
[ A=1
6AHSBVU Sreach
V
n Vmin
Expanding U:
Σ TE
elt) Sec,haae, (e, 8HSB88
32H2SBB + log
(llog(HT)
T Ymin |
< 64HSB/ H [|)((S)|AAAA) + [S] log
.21
8
This completes the proof.
Lemma E.12 (Martingale concentration with offline data). Let (Xe)==1 be the martingale differ- ence sequence defined as:
H-1 X, = Be( SHWB,8,C
Σ
(c,8HW 8,8).
of
68

---

Published as a conference paper at ICLR 2026
Let be the number of offline trajectories with minimum visitation probability Vmin fornfor state- actionn pairs visited by the expert policy. Then, with probability at least 6:
T X
H812 WB. VT + HWWB VT.
S n//
SS
Vn.
Ymin
The first term captures the direct benefit of offline data for state-actions pairs with good coverage, and the second term accounts for the diminishing probability P(E)) O TH of encountering state-action pairs with insufficient offline coverage.
L (o)(()
Proof. We introduce novel approach that substantially improves upon standard martingale concen- tration bounds by leveraging offline data. We begin by comparing our approach with the standard method used by Saha.
Saha et al. (023)* 's approach (standard method): each element the martingale difference sequence:
The conventional approach uniformly bounds
X,1 Be(m SHWB,6,C)
Σ
(1) at (c,8HWB,5) 6, $32HWWB.
This bound derived by noting that (c, 17, 07 S 2n, yielding En Ssn.an (c. 17, 5) I 2H and applying triangle inequality. This leads martingale concentration term in the regret bound that O(H2W (VTT) and, crucially, does not improve with offline data.
Our improved approach: We recognize that with offline data, we can obtain substantially tighter bounds by conditioning on appropriate events. This leads to martingale concentration term that explicitly decreases with offline data, approaching zero n + oc.
Step 1: Define data-dependent events and calculate their probabilities.
We define two complementary events:
Event E: "All state-action pairs encountered in all T episodes have good offline coverage" (i.e., (on a) 2 c n "min for some constant c 0)
Event E "At least one state-action pair encountered lacks good offline coverage"
To calculate P(E"), we leverage our MLE concentration bound for transition models (Corollary
H² p pPp') 5
n
The crucial insight is that we can relate this Hellinger distance to the probability of encountering state-action pairs with insufficient offline data. Using the relationship between Hellinger distance, total variation distance, and event probabilities:
1. Hellinger distance bounds total variation: TV(P, Q) < V2- H(,, Q) 2. Total variation bounds event probability differences: PP(A) Q(A) TV(P.Q)
Let A,,a be the event "state-action pair (s, a) has insufficient offline data coverage." Under the true model p and with enough offline data sampled from policy close to nr, the probability P (Az.a) negligible. Therefore:
P (As.a) S Pp- (As,a) + TV(P 1PP)) < .PT""PPP)))
69

---

Published as a conference paper at ICLR 2026
Using our Hellinger distance bound:
50 VV |
P (As,a) (A
Pr-
n
By union bound across all T (H 1) state-action pairs encountered:
1) Pr. =0 TH || log(n)
P(E)) T (H 1)
n
The probability of encountering any state-action pair with insufficient offline cover- age decreases as n increases, rate of approximately v
Key insight 1:
Step 2:
Establish conditional bounds on martingale differences. Case 1: Under event E (good offline coverage). When all actenn pairs have good offline coverage:
e(t) Sa.0 (c. n,,) = min
2n, v
Non(s, + No(s,a)
U
S min
2q. 20..ng
An
Ymin
For sufficiently large n, the second term in the min dominates:
U
2 (), s 1nl
n- Twin
7 V'VH W log( (|| + log 1/0)
=
In Ymin
Therefore, for 17 = SHW B:
X,I E = (T SHWB. 8,
at (c,8HB,.))
H
E
Σ Li=1
(t)
HWB VH log ((AA)) + log (/5)
2 O
Vn Ymin
H2WB. H. log( S||AA) + log(1/8)
00
Vn 7min
M
Case 2: Under event E (at least one poorly covered state-action). Here, we revert to Saha's standard bound:
E 3 M
Key insight 2: Under event E (which occurs with high probability for large n²), the martingale differences are much smaller than Saha's uniform bound, specifically by a factor of yie"mii
Key innovation: By conditioning on events E and E we can precisely quantify how the martingale concentration improves with offline data through two mechanisms:
70

---

Published as a conference paper at ICLR 2026
1. The magnitude of martingale differences under E scales
Viiia
2. The probability of event F decreases as n increases, a rate of approximately /
This conditional analysis is fundamentally different from Saha's approach, which uses a single worst-case bound regardless of offline data. Our approach precisely captures how offline data duces both the magnitude of exploration bonuses and the probability of encountering state-action pairs that require large exploration.
Step 3: Apply Azuma- Hoena--g incquality conditionally. The Azuma-Hoefrding inequality for bounded martingale differences states that for a martingale difference sequence {Xtri=1 with [Xe]] S almost surely:
T Σ
X2
X 2
2exp
- c
Applying this conditionally event E, where
|xal S Mn for all t:
A²
P
Σ
X2
N E S 2exp
T.
M²
1=1
Similarly, conditionally on event E", where |.Kel S M:
X
P
Σ
X
L
< 2exp
2 T
M
Step Apply the law of total probability.
By the law of total probability:
T
T
P
Σ
X
2
A
P
Σ
X₁
> A
E
P(E) P
Σ
Xt
2 \
E
PPE
/=1
t=l
t=1
X²
1²
<
2 exxp
-P(E) + 2exp
-P(E).
2. T.
M2
2 M2
To obtain an overall bound of 6, we bound each term by 5/2.
For the first term:
X
2 exp
P(E) S
2. T.T.
M2
X2
8
exp
2- T M2
2 P(E)
2
2 P(E)
log
2. T M2
2- P(E)
3 A 2 Mn
2. T ..
For the second term:
X²
8
2 exp
P(E)) -
2.T -33
-- 2 M )
X2
+ exp
$
2. P(E))
2 P(E*)
x > M
2. T. .og
71

---

Published as a conference paper at ICLR 2026
Step 5: Derive the combined bound. need:
For the bound hold with probability least 1 6,
2 P(E)
2. (2P((E))
A 2 max Mn 1/2 222TT T..T.B. log
.MM
2- T log
8
2 P(E))
s Mn
1. T ...Tlog Pog
+ M
T .
Substituting our expressions for Mn and M:
H VH log( S|| AI)
(10(1/))
P((E)
A
+0 H
T loo
Mmin
6
Using our bound on P(E)):
HWBB / H log([S] T (1/8)
A5O
vn Vuin
TH
[S A log(nHH
0
HWWB B.
T Pog
Step 6: Analyze the asymptotic behavior.
We start with the second term of our bound,
o (1PWR
S log(n
TH
HwWB.
T log
Step 6.1: Expand the logarithm inside the second term.
TH
S)2 [A] log(nHô-1)
TH
||||||||ogl log(nHō
log
log
+
log
8
n
TH
+ 1
|819| lognnHo
log
log
2
Step 6.2: Extract VT from the square root.
TH log
| log(nH6
H T
log
8
n
TH 8
|S|] log(nHō
H VT
log
log
2
[SPPIAI log(n H16
Step 6.3: Analyze the behavior for large n. For large n, the term log comes negative because n grows faster than the logarithmic term.
be-
72
Therefore:
TH
| log(n(((-1)
log
2 log
TH O0Vlog((
log
This gives us:
H VT (TT.OV(ooTTT S(H-BBBBB)
72

---

Published as a conference paper at ICLR 2026
Step 6.4: Incorporate P(E*) correctly. know that P(E9) = TH All log(n)
To properly account for this probability in the bound, express the term as:
TH H VT- log
P(Ex)
S (|2 log(n)
TH
S S/P|A|| log(n)
n
78
/2 |/
= H VT Ó(1)
n//4
= ö =Ō CO(HAB VT.
1S14/2/A/4 1/4
Step 7: Combine these results for final bound.
We now have two key terms in our bound for martingale concentration:
H VH [og[[[]]A) T log 1//)
AsO
vn
Ymin
H VT.
n/4
Simplifying the first term and using Ô notation to hide logarithmic factors:
H VT + (O(HWWB.. VT
| 1/12/1
A A
Vn Vnn Tmin
n²/
Therefore, with probability least
T
11 WB VT
| n/4
Σ
X S
Ō
+ H2HWBB VT.
Tmin
This bound reveals several key insights:
1. Sublinear regret: Both terms scale as VT, maintaining the crucial sublinear dependence the horizon. This ensures that our regret doesn't 't grow linearly with T.
2. Offline data benefits: Both terms decrease increases, but different rates:
The first term decreases rate t and captures the direct benefit of offline data for state-action pairs with good coverage
The second term decreases at the slower rate of 1 and accounts for the diminishing /º/4 probability of encountering poorly-covered state-action pairs
3. Complete dependence offline data: Unlike Saha et al. (2023)'s 's bound, which has an irreducible term independent of offline data, our bound shows that all components of martingale concentration can be reduced with sufficient offline data.
4. Different decay rates:
The different decay rates (+) vs. , suggest that the second term will eventually dominate for very large n, setting the ultimate rate at which offline data can improve performance.
This confirms that with sufficient high- high-quality offline data (n + oo with fixed 7mi > 0), the entire martingale concentration bound approaches zero, eliminating this component of regret entirely. I1
73

---

Published as a conference paper at ICLR 2026
F AUXILIARY MATHEMATICAL RESULTS
F.1 BRIDGING OFFLINE CONFIDENCE SETS AND ONLINE CONSTRAINTS
Lemma F.1 (Hellinger ball moment constraints: linear embedding). Define random variable on (A,
Assume f A Rd and of <B < oc.
Consider two distributions P. Q with densities that are continuous with respect to Lebesgue measure. Further assume:
HP(I))Q) & R.
Then
[[E](xx) Ees(x)l22 222 B Vd. R
and
[|Covp(((z)) Cova(f d B², v2 R.
Proof. For the squared norm on first moment, the following holds true
Ep EEff = / f())((()) dxx))dx]|2
- / (1(()))2)p(a)) ((x)ddr
s Vd. B. [p(x) (x)))dr.
-PTV(P
Using the classical result Sason & Verdú (2016) together with our constraint
TV(P.Q) (2H²( s V2R
yield the first result.
For the covariance we follow similar approach only for matrices. Define g(x) == f(x)f(x)" then
[Epg(>) EBg(x))lop || f (px)) ((x))()))))))) (xx))o
(ʃ (f -(())) -()))))))) ell
sup lo ||=||==1
/ oJ ((x)s(())o(lll)) ((x))dz sup |||||==1
/ (v. (p(x) 9((x) dr
sup |=l|z=1
(lf())|l- g(x) dr
sup
||
2 d. B² TV(,.Q) 52. B² 1/2 R.
Using definition of covariance matrix we have
[[Covr(J) Covo(/)llop = || ) [ggls Ep/Ep E 1flloo
< [Er[[s [ T "0 M|lop + /Ep/ - EES F
$2. d. B² .2. + |E fp EQ TT 1lop
74

---

Published as a conference paper at ICLR 2026
in order to bound the last term we have
fE - Boo ff 10p = |BpfEpf - - Ep fl - L. o 1 llop
- -E >lo + p[
-
oof) - ld 1lop
< |Bpfll2 |Epf - Eœfll + || |Eppf Eoffl2
2 Vd. B- -- 3-I1Epf Befll2
I <..0 d B² v2. R.
G DISCLAIMER ON LLM USAGE
LLMs were used for light language editing.
75


Reviews:
[{"review_id": "vlutUurqk7", "reviewer": "Reviewer_xVVw", "summary": "The authors provide the first fundamental analysis of the offline-to-online approach and introduce BRIDGE, a unified algorithm that integrates two signals through an uncertainty-weighted objective function. They derive a regret bound that narrows as the number of offline demonstrations increases, thus explicitly linking the amount of offline data to the efficiency of online samples.", "questions": "Have you considered experiments in other cases, or multi-scale scenarios?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The theoretical part is excellent.", "weaknesses": "The experimental section could be more comprehensive.", "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": "7EMYIYFoYO", "reviewer": "Reviewer_LAhg", "summary": "The paper \"fine tuning behavioral cloning policies with preference-based RL\" is a novel piece of work exploring the links between imitation learning and online pereference-based RL. The authors present a unified framework (BRIDGE) which combines these two - aiming to address the potential limitations of RL in domains where a) writing down appropriate reward functions is difficult and/or b) letting your agent perform open exploration would be risky or impractical.\n\nTheir key idea can be summarized as: firstly, one learns a \"safe\" warm-start policy from expert demonstrations only (no rewards), secondly you construct a \"confidence set\" in the space of policies based on this, and lastly the policy is updated using preference-based feedback which takes the form of a binary score between pairs of presented trajectories.\n\nIn Theorem 4.1 the authors provide the main theoretical result of the paper that offline data reduces online regret. They present empirical results on discrete environments (StarMDP and Gridworld) and continuous environments (Reacher and Ant) showing that their method achieves lower regret than two baselines.", "questions": "- Related to the comment about the footnote and the theoretical result applicability, the confidence set construction and theoretical results often rely on the finiteness of S and A (for example, theorem 4.2 explicitly contains |S| and |A| terms. How are these results adapted to the continuous setting?\n- Since the performance heavily depends on the choice of embedding function, have you thought about proposing ways to learn such embeddings from data?\n- Have you considered the sensitivity of your algorithm to a noisy feedback signal?\n- In practise, how should someone choose the confidence set radius or the number of offline trajectories?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The work is highly original and a very interesting idea. The paper's most significant contribution is as the first theoretical framework for studying the interplay from offline to online preference learning. The novel idea centres on using the Hellinger distance between distributions of trajectories to build the above mentioned confidence sets. It is the radii of these sets which the authors demonstrate is reduced with more offline data. They derive a non-trivial regret bound in terms of the amount of offline data and equivalent the radii of these sets.\n\nThe theoretical developments appear technically sound and well-motivated, although the proofs are extensive and largely relegated to the appendices. Due to time constraints I was not able to verify every step in detail.\n\nThe paper's presentation is very clear and well-written, with extensive detail. Each stage is logically introduced with clear figures and empirical data. There are extensive appendices.", "weaknesses": "An important point which is relegated to a footnote on page 6 is the applicability of the theoretical results. Section 3 introduces finite MDP settings before the theoretical results, and the footnote mentions that the results are presented for \"tabular, stationary transitions here\", but that the framework \"readily adapts to other transition model classes\". I think this could be made more clear, either by making this adaption more evident or presenting the scope of the theoretical results as distinct from the empirical ones (which include continuous control environments).\n\nThe embedding functions are clearly an important consideration and are shown to affect performance. The authors briefly touch on the limitations this could impose - a more detailed analysis of this could be insightful. For example, what are the consequences for more practical domains where the appropriate underlying structure may be unknown?\n\nThere are various assumptions made throughout the paper which are mostly introduced as standard to the field, but the implications or limitations of these are not drawn out in detail. Relatedly, a more general discussion of the limitations of the work is missing and would benefit the paper. \n\nThe majority of the theory sections are in the appendix. For accessibility and interest it might be nice to include a high-level proof summary. It could also be interesting to see a discussion comparing BRIDGE to modern RLHF or preference-based fine-tuning algorithms.", "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": "Gyzv0gkOzJ", "reviewer": "Reviewer_UYkF", "summary": "This paper addresses the challenge of applying reinforcement learning (RL) in real-world settings where specifying rewards is difficult and exploration is risky. The authors propose a two-stage framework: first, learn an initial policy using Behavioral Cloning (BC) from reward-free offline expert demonstrations; second, fine-tune this policy online using preference-based feedback. The paper introduces BRIDGE (Bounded Regret with Imitation Data and Guided Exploration), an algorithm designed for this \"offline imitation + online preference fine-tuning\" setting. The main contributions are:\n\n1.  **The first theoretical framework** for analyzing this offline-to-online preference learning paradigm without ground-truth rewards during fine-tunin.\n2.  **Regret bounds** (Theorem 4.1) that explicitly quantify how the amount of offline expert data ($n$) improves online sample efficiency, showing regret approaches zero as $n \\rightarrow \\infty$. The bounds rely on constructing confidence sets using the Hellinger distance between trajectory distributions, with radii shrinking as $O(1/\\sqrt{n})$ (Theorem 4.2).\n3.  **Empirical validation** of BRIDGE in discrete (StarMDP, Gridworld) and continuous control (MuJoCo Reacher, Ant) environments, showing lower cumulative regret compared to standalone BC and online preference-based RL (PbRL) baselines.\n\nThe core idea is to use offline data to construct a Hellinger ball confidence set around the BC policy, constraining the online preference learning phase to this smaller, safer region of the policy space.", "questions": "**Questions**\n\n**Continuous Implementation vs. Theory:** Could you elaborate on the theoretical implications of using the $L_2$ distance proxy in embedding space and the constructive sampling method for $\\Pi^{offline}$ in the continuous experiments, compared to the Hellinger distance over trajectory distributions used in the theory? Does this approximation affect the validity of the regret bounds in the continuous setting?\n\n**Sensitivity to $\\gamma_{min}$:** How sensitive are the theoretical bounds and the practical performance of BRIDGE to the value of $\\gamma_{min}$ (Assumption 3)? What happens if $\\gamma_{min}$ is extremely small, corresponding to a highly specialized expert?\n\n**Offline Data Quality:** The theory assumes offline data comes from an expert policy $\\pi$. The ablation in Appendix A.1 briefly explores noisy data. Could you comment further on how the theoretical guarantees might degrade if the offline data is suboptimal or contains non-expert trajectories? Theorem 4.1 seems robust to some noise via $\\gamma_{min}$ but assumes the *demonstrations* come from $\\pi^*$.\n\n**Computational Cost:** Calculating the Hellinger distance (even with the efficient method in Appendix A.4.3) and optimizing over the policy set $\\Pi_t$ (Line 7, Algorithm 1) seems potentially computationally expensive, especially as the state/action space grows. Could you discuss the scalability of BRIDGE? The appendix mentions runtime but doesn't explicitly compare the overhead vs PbRL.\n\n**Trajectory Embedding $\\phi$:** Given the significant impact of the embedding function shown in the ablations, do you have insights into how one might systematically choose or even learn an effective $\\phi$ in practical scenarios where the underlying reward/preference structure is unknown?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Novel Theoretical Contribution:** Provides the first rigorous theoretical framework and regret analysis for the widely used but previously theoretically unexplored paradigm of offline imitation learning followed by online preference-based fine-tuning.\n\n**Clear Connection Between Offline Data and Online Efficiency:** The derived regret bounds (Theorem 4.1) explicitly and quantitatively show how the amount of offline data ($n$) reduces online regret, formally justifying the approach's sample efficiency benefits. The use of Hellinger distance confidence sets with radii shrinking as $O(1/\\sqrt{n})$ provides a clear mechanism.\n\n**Unified Algorithm (BRIDGE):** Proposes a concrete algorithm that integrates offline BC and online PbRL via uncertainty weighting and constrained exploration within the derived confidence set.", "weaknesses": "**Complexity of Bounds:** While insightful, the final regret bound in Theorem 4.1 and particularly the expanded version in Theorem E.1 are quite complex, making direct interpretation challenging. While the dependence on $n$ is clear, understanding the interplay of all MDP parameters ($S, A, H$), $\\gamma_{min}$, $d$, $B$, $W$, etc., is less straightforward. The simplified analysis in Appendix B is helpful but doesn't cover the full algorithm.\n\n**Computability of Hellinger Confidence Set:** Constructing the Hellinger confidence set $\\Pi_{1-\\delta}^{offline}$ involves estimating the Hellinger distance between the BC policy and candidate policies under the estimated dynamics $\\hat{P}$. While Appendix A.4.3 provides an efficient calculation for the discrete case, the practical implementation for continuous environments resorts to an $L_2$ distance proxy in embedding space and constructive sampling around $\\pi^{BC}$. This discrepancy between the theory (Hellinger distance over trajectory distributions) and continuous implementation requires further justification or analysis regarding its impact on the guarantees.\n\n**Dependence on $\\gamma_{min}$:** The bounds depend on $\\gamma_{min}$, the minimum visitation probability of the expert policy. This value is unknown and hard to estimate. While Assumption 3 is milder than typical offline RL coverage assumptions, the practical implications of a potentially very small $\\gamma_{min}$ (specialized expert) on the bounds could be discussed further.\n\n**Choice of Embedding Function:** The experiments and Appendix A.1 highlight the critical impact of the trajectory embedding function $\\phi$ on performance. The theory assumes $\\phi$ is known, but provides little guidance on choosing or learning a good embedding, which remains a key practical challenge.", "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": "NDaXbzwUjt", "reviewer": "Reviewer_g6Yh", "summary": "This paper proposes a hybrid algorithm, BRIDGE, that combines offline behavioral cloning with online preference-based RL to address data scarcity and unsafe exploration challenges. The method first constructs a confidence set over policies using the Hellinger distance in trajectory distribution space, and then fine-tunes the policy online using preference feedback constrained to this confidence set. Theoretically, the paper establishes a regret bound that converges asymptotically to zero as the number of offline demonstrations increases, formally characterizing the relationship between offline data quantity and online learning efficiency. Empirical results on both discrete and continuous control environments show that BRIDGE outperforms offline BC and online PbRL baselines.", "questions": "- In Figure 2, the number of offline demonstrations used should be specified. Without this, the performance comparison with online PbRL (which starts without offline data) seems incomplete. Also, what policy does the online PbRL baseline start from at iteration 0?\n- In Figure 2, why do the dotted lines (offline BC) lack CI? Is the offline dataset fixed across the 20 runs?\n- In Figure 3, how is the number of policies quantified in continuous environments? Is the state-action space discretized?\n- What motivates the use of the Hellinger distance over other divergence measures? Is it mainly for analytical convenience?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical results clearly support the necessity of the hybrid algorithm. The provided regret bound is sharper and offers meaningful insight into how offline demonstration data improves online sample efficiency. While I did not verify the detailed proofs in the appendix, the proof sketch is mathematically sound and grounded in established theoretical tools.\n- The writing and organization are clear, with a strong logical flow from motivation to theoretical results and experiments.", "weaknesses": "- Some experimental details are deferred to the appendix but are essential for understanding the results (see specific questions below).\n- The computational complexity of the optimization step (line 7 in Algorithm 1) is unclear.", "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)