1 Introduction↩︎

We study KL-regularized contextual bandits and episodic RL under general function approximation with model misspecification. Such formulations arise in modern RLHF and LLM post-training pipelines, where policy updates are regularized by a KL penalty relative to a reference policy [1]–[6]. Beyond their practical relevance, KL-regularized objectives provide a principled abstraction of stability–performance trade-offs induced by information-theoretic regularization.

Informally, model misspecification means that the learner uses a model class that is too simple to exactly represent the environment. For example, the learner may fit rewards or value targets using a linear, low-rank, or otherwise restricted class, while the true reward depends on nonlinear features or interactions outside that class. In that case, even with unlimited data and no statistical noise, the best predictor inside the chosen class can still have a nonzero approximation bias. This is the failure of realizability studied in misspecified bandits and RL [7]–[11].

Our analysis builds on the literature on contextual bandits and RL with general function approximation, which develops oracle-based and regression-based algorithms together with strong regret guarantees under structural assumptions [12]–[19]. Subsequent work has further expanded this framework to include policy-optimization-oriented analyses and more general oracle-efficient formulations [20]–[22]. A separate recent line extends these ideas to KL-regularized bandit and RL settings, establishing provably efficient guarantees for soft-policy formulations [4]–[6], [23]–[26]. However, these analyses rely on realizability, requiring the ground-truth reward or value functions to lie within the chosen function class. When this assumption fails, the resulting misspecified setting can fundamentally alter achievable regret guarantees.

Recent work on misspecified bandits and RL shows that achievable guarantees depend critically on the chosen misspecification model [7]–[11], [27]. In KL-regularized problems, this dependence is further complicated by structural differences from standard reward-regret formulations. First, the relevant performance criterion is KL regret with respect to a KL-optimal Gibbs policy, rather than reward regret relative to a deterministic benchmark. Second, the KL regularization changes both the optimization geometry and the Bellman targets appearing in the analysis, so misspecification conditions from standard bandit/RL formulations do not transfer directly. Existing misspecification models do not explicitly account for these KL-specific features, leaving the theoretical treatment of misspecification in KL-regularized bandits and RL incomplete.

This raises the question of whether one can obtain provably efficient KL-regret guarantees under misspecification using approximation conditions aligned with the KL-regularized objective. We address this question for KL-regularized contextual bandits and episodic RL. For RL, our main theorem is stated under explicitly assumed confidence and uncertainty conditions, and the algorithmic guarantees use bonuses calibrated to a known misspecification level. The main contributions are as follows:

• We introduce KL misspecification formulations for contextual bandits and episodic RL. For contextual bandits, we use a pointwise misspecification formulation adapted to the KL-regularized objective. For episodic RL, we introduce a stagewise misspecification condition aligned with KL-regularized Bellman targets.

• The main technical contribution is an analysis that combines a Gibbs quadratic self-bounding inequality for KL gaps with a reduction that converts squared on-policy Q-gaps into squared Bellman residual terms. This isolates the KL-specific terms that are not present in standard misspecified reward-regret analyses.

• We establish high-probability KL-regret guarantees with explicit misspecification terms and eluder-dimension-style complexity dependence. For contextual bandits, we give a direct regret theorem under the KL pointwise misspecification model. For episodic RL, we prove a high-probability regret theorem under assumed confidence and uncertainty conditions, with explicit dependence on misspecification and a bound on the sum of squared bonuses. We further show how our framework recovers standard realizable KL-regularized settings as special cases.

2 Related Work↩︎

2.0.0.1 General function approximation in contextual bandits and RL.

Our work builds on the literature on contextual bandits and RL with general function approximation, including reduction-based, oracle-based, and regression-based approaches [13]–[15], [28]. This literature also develops structural complexity measures and complexity-sensitive analyses that are central to modern online learning theory over rich hypothesis classes [12], [16]–[18]. Related work further studies how structural conditions, such as coverage, affect exploration efficiency in online RL [19], and recent works continue to extend oracle-efficient and policy-optimization-oriented analyses for contextual bandits with rich function classes [20]–[22].

2.0.0.2 KL-regularized bandits, RL, and RLHF-related theory.

A line of work studies KL-regularized, or relative-entropy-regularized, bandit and RL formulations. Related theoretical developments in preference-based RL and RLHF include finite-time analyses, trajectory-preference formulations, randomized exploration schemes, and comparisons between RLHF and standard RL [29]–[32]. More recent results analyze KL-regularized RLHF formulations directly, including iterative preference learning under KL constraints, exploration-aware preference optimization, online and offline settings, and sharp guarantees for KL-regularized contextual bandits and RL [4]–[6], [23], [24]. Additional work studies general-preference and Nash-style RLHF as well as regularized variants beyond the standard Bradley–Terry model [25], [26], [33], [34].

2.0.0.3 Misspecification in bandits and RL.

A substantial body of work studies misspecified contextual bandits and RL, establishing forms of graceful degradation beyond realizability and highlighting the sensitivity of guarantees to the chosen misspecification model [7]–[11]. These developments include oracle-efficient contextual bandit methods, misspecified linear contextual bandits, and misspecified RL analyses spanning linear MDPs to more general function approximation settings [8]–[11]. Our bandit misspecification condition adopts a pointwise approximation viewpoint extending to the ideas of the misspecification formulations used by [7], but adapts the formulation to KL-regularized objectives and extends the pointwise viewpoint to KL-regularized Bellman targets in episodic RL. Related work on misspecified regression under covariate shift provides complementary analytical tools for learning with approximation error and distribution shift [27].

3 Preliminaries↩︎

3.1 KL-Regularized Contextual Bandits↩︎

Suppose there are a total of \(T\) rounds. At each round \(t \in [T]\), a context \(x_t \in \mathcal{X}\) is drawn from an unknown distribution \(d\), where \(\mathcal{X}\) denotes the context space. At round \(t\), the learning algorithm observes \(x_t\) and selects a policy \(\pi_t:\mathcal{X}\to\Delta(\mathcal{A})\), where \(\Delta(\mathcal{A})\) denotes the set of distributions over \(\mathcal{A}\). An action is sampled according to \(a_t \sim \pi_t(\cdot \mid x_t)\). The learner subsequently receives a reward \[r_t = R^\star(x_t, a_t) + \epsilon_t, \label{eq:bandit95reward95model}\tag{1}\] where \(R^\star:\mathcal{X}\times\mathcal{A}\to[0,1]\) is an unknown ground-truth reward function, and \(\epsilon_t\) is conditionally zero-mean and \(1\)-sub-Gaussian. We assume the learner is given a reference policy \(\pi_{\mathrm{ref}}(\cdot \mid x)\) and a finite function class \(\mathcal{R}\subseteq[0,1]^{\mathcal{X}\times\mathcal{A}}\) with cardinality \(N_{\mathcal{R}}:=|\mathcal{R}|\).

3.1.0.1 Learning objective

We aim to design a learning algorithm that minimizes the regret, which is defined as follows: \[\mathrm{Reg}(T) = \sum_{t \in [T]} \big( J(\pi^*) - J(\pi_t) \big), \label{eq:bandit95regret95obj}\tag{2}\] where \(J(\pi)\) denotes the KL-regularized objective used here (as in [35]): \[\begin{align} J(\pi) &:= \mathbb{E}_{x \sim d}\,\mathbb{E}_{a \sim \pi(\cdot \mid x)} \left[ R^\star(x, a) - \eta^{-1} \mathrm{KL}\!\left( \pi(\cdot \mid x) \,\|\, \pi_{\mathrm{ref}}(\cdot \mid x) \right) \right] \notag\\ &= \mathbb{E}_{x \sim d}\,\mathbb{E}_{a \sim \pi(\cdot \mid x)} \left[ R^\star(x, a) - \eta^{-1} \log \frac{\pi(a \mid x)}{\pi_{\mathrm{ref}}(a \mid x)} \right], \label{eq:bandit95obj95def} \end{align}\tag{3}\] where \(\eta > 0\) is the regularization parameter. Here \(\pi(a \mid x): \mathcal{X}\times \mathcal{A}\to [0,1]\) denotes the conditional probability of selecting \(a\) given context \(x\). We define the optimal policy \(\pi^* = \arg\max_{\pi} J(\pi)\), and \(\pi_t\) to denote the stochastic policy adopted by the learning algorithm at round \(t\).

Throughout this subsection, policy optimization is taken over all stochastic policies \(\pi\). We use the standard convention that \(\mathrm{KL}\!\left(\pi(\cdot\mid x)\,\|\,\pi_{\mathrm{ref}}(\cdot\mid x)\right)=+\infty\) whenever \(\pi(\cdot\mid x)\) is not absolutely continuous with respect to \(\pi_{\mathrm{ref}}(\cdot\mid x)\). Thus, only policies that are absolutely continuous with respect to \(\pi_{\mathrm{ref}}(\cdot\mid x)\) have finite KL-regularized objective values.

Using Lemma 1 and 3 , the KL-optimal policy is \(\pi^*=\pi_{R^\star}.\) Importantly, this characterization does not require realizability; in our misspecified setting, \(\mathcal{R}\) only specifies the learner’s approximation class, while the benchmark policy is defined by the ground-truth reward \(R^\star\).

This is the KL-regularized extension of the pointwise misspecification formulation in [7]: the benchmark and regret notion are KL-regularized, while the approximation error is quantified in the same pointwise style.

3.2 KL-Regularized RL↩︎

In this section, we introduce the episodic KL-regularized MDP formulation. An episodic MDP is defined by a tuple \((\mathcal{S}, \mathcal{A}, H, T, \mathbb{P}, d, r)\), where \(\mathcal{S}\) denotes the state space, \(\mathcal{A}\) denotes the action space, \(H\) denotes the episode length, and \(T\) denotes the total number of episodes. The transition kernel is given by \(\mathbb{P}=\{\mathbb{P}_h\}_{h=1}^H\), where \(\mathbb{P}_h(s_{h+1} \mid s_h, a_h)\) denotes the probability of transitioning from the current state-action pair \((s_h, a_h)\) to the next state \(s_{h+1}\) at step \(h\). The initial state \(s_1^t\) is drawn from an unknown distribution \(d\), and the reward function is defined as \(r=\{r_h:\mathcal{S}\times\mathcal{A}\to[0,1]\}_{h=1}^H\). For each round \(t \in [T]\) and each step \(h \in [H]\), the learning algorithm observes the current state \(s_h^t\), takes action \(a_h^t\), receives the reward \(r_h^t(s_h^t,a_h^t)\), and transitions to the next state \(s_{h+1}^t\) according to the transition kernel \(\mathbb{P}_h(\cdot \mid s_h^t, a_h^t)\). In the value-function definitions and Bellman-operator definitions below, \(r_h(s, a)\) denotes the underlying stage-\(h\) reward function in the MDP model, while \(r_h^t(s_h^t,a_h^t)\) denotes the reward observed in episode \(t\).

We use stagewise reference policies \(\{\pi_{\mathrm{ref},h}\}_{h=1}^H\). As in the bandit case, policy optimization is taken over all stochastic policies, with the standard convention that \(\mathrm{KL}\!\left(\pi_h(\cdot\mid s)\,\|\,\pi_{\mathrm{ref},h}(\cdot\mid s)\right)=+\infty\) whenever \(\pi_h(\cdot\mid s)\) is not absolutely continuous with respect to \(\pi_{\mathrm{ref},h}(\cdot\mid s)\). Thus, only policies that are absolutely continuous with respect to the stagewise reference policies have finite KL-regularized values.

We define the value function and Q-function as follows: \[\begin{align} V_h^\pi (s_h) &= \sum_{j = h}^H \mathbb{E}^\pi \left[ r_j(s_j, a_j) - \eta^{-1}\mathrm{KL}\!\left( \pi_j(\cdot \mid s_j) \,\|\, \pi_{\mathrm{ref}, j}(\cdot \mid s_j) \right) \Big| s_h \right], \notag\\ Q_h^\pi (s_h, a_h) &= r_h(s_h, a_h) + \sum_{j = h+1}^H \mathbb{E}^\pi \left[ r_j(s_j, a_j) - \eta^{-1}\mathrm{KL}\!\left( \pi_j(\cdot \mid s_j) \,\|\, \pi_{\mathrm{ref}, j}(\cdot \mid s_j) \right) \Big| s_h, a_h \right]. \label{eq:V95and95Q} \end{align}\tag{4}\] Here \(\pi := \{\pi_h\}_{h=1}^H\) denotes the policy sequence, and \(\mathbb{E}^\pi\) denotes the expectation over the trajectory induced by \(\pi\). We can also define the value function and Q-function recursively as follows. We set the terminal value as \(V_{H+1}^\pi(s_{H+1}) = 0\), and for each step \(h \in [H]\), we define \[\begin{align} V_h^\pi(s_h) &= \mathbb{E}_{a_h \sim \pi_h(\cdot \mid s_h)} \left[ Q_h^\pi(s_h, a_h) - \eta^{-1}\mathrm{KL}\!\left( \pi_h(\cdot \mid s_h) \,\|\, \pi_{\mathrm{ref},h}(\cdot \mid s_h) \right) \right],\\ Q_h^\pi(s_h, a_h) &= r_h(s_h, a_h) + \mathbb{E}_{s_{h+1} \sim \mathbb{P}_h(\cdot \mid s_h, a_h)} \left[ V_{h+1}^\pi(s_{h+1}) \right]. \end{align}\] The optimal value function and Q-function are defined as \[V_h^*(s_h) = \max_{\pi}V_h^\pi(s_h), \qquad Q_h^*(s_h,a_h) = \max_{\pi}Q_h^\pi(s_h,a_h). \label{eq:optimal95V95and95Q}\tag{5}\] Assume the optimal policy is achieved at \(\pi^*\). Using Lemma 1 and a backward iteration starting from \(V^*_{H+1}(s_{H+1}) = 0\), we have the following proposition.

The Gibbs policy characterization and the log-partition recursion above are the KL-regularized dynamic-programming counterparts of Lemma 1, and are standard in KL-regularized RL formulations. We use this reference-policy form because it makes the KL-regularized geometry explicit and aligns with the Gibbs-policy benchmark used in our analysis.

We let \(\mathcal{R}:= \{\mathcal{R}_h\}_{h=1}^H\) denote the finite stagewise function classes used by the algorithm, where \(\mathcal{R}_h \subseteq [0,B_h]^{\mathcal{S}\times \mathcal{A}}\), and denote their cardinalities by \(N_{\mathcal{R}_h} := |\mathcal{R}_h| < \infty\).

For any bounded measurable continuation reward function \(f_{h+1}:\mathcal{S}\times\mathcal{A}\to[0,B_{h+1}]\), define the stagewise log-partition operator and the KL-regularized Bellman operator by \[V_{h+1}(f_{h+1};s_{h+1}) := \eta^{-1}\log \mathbb{E}_{a \sim \pi_{\mathrm{ref},h+1}(\cdot\mid s_{h+1})} \left[\exp\!\left(\eta f_{h+1}(s_{h+1},a)\right)\right]. \label{eq:rl95log95partition95operator}\tag{6}\] \[\begin{align} (\mathcal{T}_{\eta,h}f_{h+1})(s_h,a_h) &:= r_h(s_h,a_h) + \mathbb{E}_{s_{h+1} \sim \mathbb{P}_h(\cdot \mid s_h, a_h)} \left[ V_{h+1}(f_{h+1};s_{h+1}) \right]. \label{eq:soft95bellman95operator} \end{align}\tag{7}\]

3.2.0.1 Learning objective

We aim to design a learning algorithm that minimizes the regret. The objective function is defined as \[J(\pi) = \mathbb{E}_{s_1 \sim d} \left[ V_1^\pi(s_1) \right], \label{eq:rl95obj95def}\tag{8}\] and the regret is defined by \[\mathrm{Reg}(T) = \sum_{t\in[T]} \big( J(\pi^*) - J(\pi_t) \big). \label{eq:rl95regret95obj}\tag{9}\] Using Proposition 1, the KL-optimal policy is the Gibbs policy characterized by \(\{Q_h^*\}_{h=1}^H\). We next introduce a stagewise misspecification condition stated along a possibly data-dependent KL Bellman-backup path.

To state the misspecification condition in a pathwise form, let \(\widetilde{Q}_{t,h+1}\) denote the stage-\((h+1)\) continuation \(Q\)-function used in the episode-\(t\), stage-\(h\) KL Bellman backup, with the terminal convention \(\widetilde{Q}_{t,H+1}\equiv 0\).

This is a KL-regularized, stagewise pointwise misspecification condition along a Bellman-backup path. It extends the pointwise misspecification viewpoint of [7] from bandits to KL-regularized Bellman targets, while being weaker than requiring pointwise approximation uniformly for all continuation functions. Compared with locally bounded misspecification formulations in RL that control approximation error on policy-relevant state-action distributions (e.g., [11]), ?? is a stagewise pointwise condition along a KL Bellman-backup path, and it plays the same structural role in RL as ?? does in contextual bandits.

4 Algorithms↩︎

Our algorithms follow the standard regression-based optimistic template for value-based methods under general function approximation, and are compatible with recent KL-regularized analyses at the level of the Gibbs policy-improvement step. The main difference here is that we allow model misspecification and track it explicitly through additive misspecification terms in the optimism bonuses.

Throughout this section, we work in an oracle-based computational model with ERM oracles and uncertainty-bonus routines. Our guarantees are statistical under this oracle model. We present the known-misspecification versions of the algorithms, where \(\zeta_{\mathrm{Bandit}}\) and \(\zeta_{\mathrm{RL}}\) are treated as known inputs and inserted directly into the bonuses.

To separate regression from uncertainty computation, we maintain two histories: the observed-data history and the state–action history. For bandits, \[\widetilde{D}^{\mathrm{Bandit}}_{t-1}:=\{(x_i,a_i,r_i)\}_{i=1}^{t-1}, \qquad \bar D^{\mathrm{Bandit}}_{t-1}:=\{(x_i,a_i)\}_{i=1}^{t-1},\] and for episodic RL, for each \(h\in[H]\), \[\widetilde{D}^{\mathrm{RL}}_{h,t-1}:=\{(s_{\tau,h},a_{\tau,h},r_{\tau,h},s_{\tau,h+1})\}_{\tau=1}^{t-1}, \qquad \bar D^{\mathrm{RL}}_{h,t-1}:=\{(s_{\tau,h},a_{\tau,h})\}_{\tau=1}^{t-1}.\]

For the RL analysis with recomputed regression labels, we also use a finite continuation-value class \(\mathcal{V}_{h+1}\) containing all continuation values \(\widetilde{V}_{t,h+1}\) generated by Algorithm 2 at stage \(h+1\), with \(N_{\mathcal{V}_{h+1}}:=|\mathcal{V}_{h+1}|\) and \(\mathcal{V}_{H+1}=\{0\}\). This convention is used only to make the frozen-target concentration step uniform over the data-dependent continuation values.

Algorithms 1 and 2 take \((\beta,\lambda)\) as explicit inputs for modularity. In the theorem statements, these parameters are instantiated using localized-eluder calibrations at the usual logarithmic scale, with additional \(T\zeta^2\)-type misspecification terms.

For convenience, we define clipping as \(\Pi_{[0,n]}(x):=\min\{n,\max\{0,x\}\}\).

4.1 Contextual bandits: MR-KL-UCB↩︎

We adapt the standard upper confidence bound (UCB) method to the KL-regularized setting and propose Misspecification-Robust KL-UCB (MR-KL-UCB) in Algorithm 1. The algorithm performs optimism at the reward-function level and then samples from the induced Gibbs policy. Concretely, at round \(t\), after observing \(x_t\), the learner fits an ERM predictor on \(\widetilde{D}^{\mathrm{Bandit}}_{t-1}\), computes an uncertainty bonus using \(U_{\mathcal{R}}\) and \(\bar D^{\mathrm{Bandit}}_{t-1}\) as in Definition 1, forms an optimistic clipped reward estimate, and samples from the Gibbs policy induced by that optimistic estimate. All update formulas are given once in Algorithm 1 and are not repeated in the prose. For the theoretical guarantee in Theorem 4, we use \(\beta=\Theta\!\Big(\sqrt{\log(N_\mathcal{R}T/\delta)}\Big)\) and defer the exact formulas to 11 .

Relative to optimistic contextual bandit methods with greedy action selection, MR-KL-UCB performs optimism at the reward-function level and then samples from the corresponding Gibbs policy.

4.2 Episodic RL: MR-KL-LSVI↩︎

We adapt LSVI [36] to the KL-regularized setting and propose Misspecification-Robust KL-LSVI (MR-KL-LSVI) in Algorithm 2. The algorithm is a KL-regularized extension of backward fitted-\(Q\) planning with optimism. Each episode has two phases: a backward planning pass based on previous-episode data, followed by one rollout of the resulting nonstationary Gibbs policy.

Let \(B_h:=H-h+1\). In the backward pass, at each stage \(h\), the learner recomputes regression labels using the current continuation value, fits a stagewise ERM predictor on \(\widetilde{D}^{\mathrm{RL}}_{h,t-1}\), computes a stagewise uncertainty bonus from \(\bar D^{\mathrm{RL}}_{h,t-1}\) using \(U_{\mathcal{R}_h}\) (Definition 1), forms an optimistic clipped \(Q\)-estimate, and then performs Gibbs policy improvement relative to \(\pi_{\mathrm{ref},h}\). The soft value update uses the stagewise log-partition operator \(V_h(\cdot\,;s)\) already defined in 3. All update formulas are given once in Algorithm 2, and are not repeated in the prose. For the RL guarantee in Corollary 1, we use \(\beta=\Theta(\sqrt{\Lambda_{\mathrm{RL}}})\), where \(\Lambda_{\mathrm{RL}}\) includes the finite stagewise function classes and the finite continuation-value classes used in the frozen-target concentration step. The order-level calibration is stated in Corollary 1, and the constant-level version is given in Appendix 8.

Algorithm 2 uses labels recomputed within the current backward pass and inserts the known misspecification level \(\zeta_{\mathrm{RL}}\) directly into the stagewise bonus. Relative to classical LSVI-UCB-style methods, the key differences are the KL-regularized soft continuation value and Gibbs policy improvement.

5 Analysis↩︎

5.1 KL-Regularized Contextual Bandits↩︎

5.1.0.1 Proof sketch.

The proof is an optimistic regression analysis adapted to the KL-regularized objective, following the standard second-order-bonus route with KL geometry made explicit via the Gibbs variational identity.

The starting point is an exact Gibbs representation of the round-\(t\) KL regret gap. Under optimism, this gap is upper bounded by \(\eta\) times a squared score residual under the learner policy. Hence, the regret analysis reduces to controlling a second-order quantity, namely a predictable sum of squared bonuses.

To establish optimism under misspecification, we compare the ERM estimator to a comparator \(R^\circ\in\mathcal{R}\) satisfying \(\sup_{x\in\mathcal{X}}\sup_{a\in\mathcal{A}}|R^\circ(x,a)-R^\star(x,a)|\le \zeta_{\mathrm{Bandit}}.\) The ERM localization step controls \(\widehat R_{t-1}-R^\circ\), while ?? controls \(R^\circ-R^\star\). After adding the bonus and clipping, these combine into a pointwise residual bound \(0\le \widetilde{R}_{t-1}(x,a)-R^\star(x,a)\lesssim b_{t-1}(x,a)\).

The remainder separates concentration from complexity control. A Freedman step relates the predictable squared-bonus sum to the squared-bonus sum along sampled actions, and eluder dimension summability bounds \(\sum_{t=1}^T b_{t-1}(x_t,a_t)^2\) by \(\beta^2 d(\mathcal{R},\lambda,T)\). Finally, the additive misspecification term in the bonus contributes \(T\zeta_{\mathrm{Bandit}}^2\).

5.2 KL-Regularized RL↩︎

For episodic RL, the proof follows the same high-level route as in the bandit case, but the stagewise regression problem uses recomputed targets. The guarantee below is for the known-misspecification setting used by Algorithm 2. For the frozen-target confidence step, let \(\mathcal{V}_{h+1}\) denote a finite class containing the continuation values \(\widetilde{V}_{t,h+1}\) generated by the algorithm. This class is used only for the proof of the frozen-target concentration event and is not an additional algorithmic input.

We first state a modular regret theorem that separates the KL-RL regret reduction from the statistical verification of confidence and uncertainty conditions. The concrete guarantee for Algorithm 2 is then obtained as a corollary by verifying these conditions in Appendix 8.

5.2.0.1 Proof sketch.

Theorem 6 gives the regret reduction once confidence, residual control, uncertainty-summability, and alignment are available. Appendix 8 verifies these conditions for Algorithm 2; in particular, the frozen-target confidence step is proved uniformly over \(V\in\mathcal{V}_{h+1}\), which allows us to instantiate it with the data-dependent continuation value \(\widetilde{V}_{t,h+1}\).

At a high level, fix an episode and condition on the start-of-episode filtration so that the planning outputs and recomputed targets are fixed. Under optimism, each stagewise Gibbs KL term is controlled by a squared \(Q\)-gap under the learner policy. A multi-step reduction propagates these stagewise terms through the episode and upper bounds the total by an \(H^2\)-weighted sum of squared Bellman residuals, which is the source of the leading \(H^2\) factor.

Next, the Bellman residuals are controlled by the bonus. The frozen-target confidence step controls the estimation error around a stagewise comparator, while ?? controls the comparator-to-target gap. After adding the optimistic bonus and clipping, these yield a residual bound of the form \(e_{t,h}(s,a)^2 \lesssim b_{t,h}(s,a)^2\), hence conditional regret reduces to a second-order bonus sum.

Finally, uncertainty-squared summability yields the leading complexity term \(\eta H^2 \beta^2 d_{\mathrm{RL}}(\lambda,T)\), plus the explicit misspecification contribution \(\eta H^3T\zeta_{\mathrm{RL}}^2\). The logarithmic factors hidden in \(\widetilde{O}(\cdot)\) include the finite-class union bound over \(\mathcal{R}_h\), the continuation-value classes \(\mathcal{V}_{h+1}\), and the Freedman alignment steps.

6 Conclusion↩︎

We study KL-regularized contextual bandits and episodic reinforcement learning under general function approximation with model misspecification. We formulate KL-aligned misspecification conditions and analyze optimistic regression-based algorithms that act via reference-relative Gibbs policies. For contextual bandits, we prove high-probability KL-regret bounds with explicit dependence on misspecification and localized eluder-dimension complexity. For episodic RL, we establish a high-probability regret guarantee for our KL-regularized LSVI-style algorithm, where the leading term is governed by an explicit confidence/uncertainty interface and the bound again separates statistical complexity from misspecification. Both results recover the corresponding realizable KL-regularized guarantees as special cases. Technically, the analysis combines Gibbs variational identities, optimism-based KL self-bounding, and summability of squared bonus terms, leading to logarithmic-in-\(T\) high-probability factors.

Our misspecification model is pointwise and paired with light-tailed noise assumptions. Recent RLHF studies suggest that KL regularization alone may not ensure robustness under broader forms of reward misspecification, and can fail in particular under heavy-tailed reward errors. Extending KL-regret guarantees to on-policy misspecification measures and heavy-tailed settings remains an important direction for future work. Another open question is whether the horizon dependence in the RL guarantee can be improved, ideally with matching lower bounds under KL-adapted misspecification. More broadly, a natural future direction is to extend the framework beyond reward-based learning to richer feedback models, including preference-based formulations.

Acknowledgements↩︎

We thank the anonymous reviewers and area chair for their helpful comments. QG is supported in part by the National Science Foundation DMS-2323113 and IIS-2403400. HH and HW are supported in part by National Science Foundation IIS-2403401. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

7 Notation↩︎

8 Proofs↩︎

8.1 KL-Regularized Contextual Bandits↩︎

Define the bandit filtrations \[\mathcal{F}^{-}_{t}:=\sigma\!\big(\{(x_i,a_i,r_i)\}_{i=1}^{t-1},x_t\big),\qquad \mathcal{F}^{a}_{t}:=\sigma(\mathcal{F}^{-}_{t}, a_t),\qquad \mathcal{F}_t:=\sigma(\mathcal{F}^{a}_{t}, r_t).\] For alignment arguments, we view \(X_t-\mathbb{E}[X_t\mid\mathcal{F}^-_t]\) as a martingale difference with respect to the shifted filtration \(\{\mathcal{F}^-_{t}\}_{t\ge 1}\), since \(X_t\) is \(\mathcal{F}^-_{t+1}\)-measurable and \(\mathbb{E}[X_t\mid\mathcal{F}^-_t]\) is predictable.

Using the main-text bandit history notation, let \(z_i:=(x_i,a_i)\). For any \(\bar D^{\mathrm{Bandit}}_{t-1}\), define the localized uncertainty width \[\mathcal{U}_{\mathcal{R}}\!\big(\lambda;(x,a)\mid \bar D^{\mathrm{Bandit}}_{t-1}\big) := \min\left\{1,\; \sup_{\substack{R,R'\in\mathcal{R}:\\ \sum_{i=1}^{t-1}(R(z_i)-R'(z_i))^2\le \lambda}} \bigl|R(x,a)-R'(x,a)\bigr| \right\}. \label{eq:bandit95width95def}\tag{10}\] Fix \(\delta\in(0,1)\) and set \[\beta := \max\Bigl\{1,\;c_0 \sqrt{\log\!\Big(\frac{2T N_{\mathcal{R}}}{\delta}\Big)}\Bigr\}, \qquad \lambda := c_\lambda\Bigl(d(\mathcal{R},\lambda,T)+\log\!\tfrac{2T N_{\mathcal{R}}}{\delta} + T\,\zeta_{\mathrm{Bandit}}^2\Bigr), \label{eq:beta95lambda95bandit95app}\tag{11}\] for sufficiently large universal constants. The corresponding bonus is \[b_{t-1}(x,a) := \min\left\{1,\;\beta\,\mathcal{U}_{\mathcal{R}}\!\big(\lambda;(x,a)\mid \bar D^{\mathrm{Bandit}}_{t-1}\big)+\zeta_{\mathrm{Bandit}}\right\}. \label{eq:bonus95def95app}\tag{12}\]

8.2 KL-Regularized RL↩︎

For episode \(t\) and stage \(h\), let \(\mathcal{F}^-_{t,h}\) be the \(\sigma\)-field generated by the trajectory history up to stage \(h\) (including \(s_{t,h}\)), and let \(\mathcal{F}^a_{t,h}:=\sigma(\mathcal{F}^-_{t,h}, a_{t,h})\). We use \(\bar D^{\mathrm{RL}}_{h,t-1}\) for the stage-\(h\) state–action history. For each stage \(h\), define the KL log-partition operator \[V_h(u;s):=\frac{1}{\eta}\log \mathbb{E}_{a\sim\pi_{\mathrm{ref},h}(\cdot\mid s)}\!\left[e^{\eta u(s,a)}\right]. \label{eq:rl95log95partition95app}\tag{20}\] We assume \(\mathbb{E}[\epsilon_{t,h}\mid \mathcal{F}^{a}_{t,h}]=0\) and \(\epsilon_{t,h}\) is conditionally \(1\)-sub-Gaussian given \(\mathcal{F}^{a}_{t,h}\).

In the RL part below, we will use the conditional quantity \(\bar R_t=\mathbb{E}[R_t\mid \mathcal{F}^-_{t,1}]\) (defined later) as a convenient intermediate. No additional concept beyond this conditionalization is intended.

Assume the pathwise stagewise misspecification condition ?? . In particular, for each algorithm-generated continuation \(\widetilde{Q}_{t,h+1}\), there exists \(f^\dagger_{t,h}\in\mathcal{R}_h\) such that \[\sup_{s\in\mathcal{S}}\sup_{a\in\mathcal{A}} \bigl|f^\dagger_{t,h}(s,a)-(\mathcal{T}_{\eta,h}\widetilde{Q}_{t,h+1})(s,a)\bigr| \le \zeta_{\mathrm{RL}}. \label{eq:rl95comparator95completeness95app}\tag{21}\]

We now define the stagewise uncertainty score directly from localized widths, so that the uncertainty-squared summability statement becomes a deterministic consequence of the width definition.

For each stage \(h\in[H]\), let \(z_{i,h}:=(s_{i,h},a_{i,h})\). For any \(\bar D^{\mathrm{RL}}_{h,t-1}\), define the stagewise localized uncertainty width \[\mathcal{U}_{\mathcal{R}_h}\!\big(\lambda;(s,a)\mid \bar D^{\mathrm{RL}}_{h,t-1}\big) := \min\left\{B_h,\; \sup_{\substack{f,f'\in\mathcal{R}_h:\\ \sum_{i=1}^{t-1}(f(z_{i,h})-f'(z_{i,h}))^2\le \lambda}} \bigl|f(s,a)-f'(s,a)\bigr| \right\}, \label{eq:rl95stagewise95width95def}\tag{22}\] where \(B_h:=H-h+1\).

Define the stagewise uncertainty score by \[\mathrm{unc}_{t,h}(s,a) := \mathcal{U}_{\mathcal{R}_h}\!\big(\lambda;(s,a)\mid \bar D^{\mathrm{RL}}_{h,t-1}\big). \label{eq:rl95unc95def95direct}\tag{23}\]

For the frozen-target concentration argument, take \(\mathcal{V}_{h+1}\subseteq[0,B_{h+1}]^{\mathcal{S}}\) to be a finite deterministic class containing every continuation value \(\widetilde{V}_{t,h+1}\) that can be generated by the algorithm at stage \(h+1\), and set \(N_{\mathcal{V}_{h+1}}:=|\mathcal{V}_{h+1}|\). We use the convention \(B_{H+1}=0\) and \(\mathcal{V}_{H+1}=\{0\}\). For each \(V\in\mathcal{V}_{h+1}\), the stagewise misspecification condition gives a fixed comparator \(f_h^{\dagger,V}\in\mathcal{R}_h\) satisfying \[\sup_{s\in\mathcal{S}}\sup_{a\in\mathcal{A}} \left|f_h^{\dagger,V}(s,a)- \left(r_h^\star(s,a)+\mathbb{E}_{s'\sim P_h(\cdot\mid s,a)}[V(s')]\right)\right| \le \zeta_{\mathrm{RL}}. \label{eq:rl95comparator95fixedV95app}\tag{24}\] For the realized continuation \(V=\widetilde{V}_{t,h+1}\), we write \(f^\dagger_{t,h}:=f_h^{\dagger,\widetilde{V}_{t,h+1}}\), which is consistent with 21 .

Fix \(\delta\in(0,1)\) and define \[\Lambda_{\mathrm{RL}} := \max_{h\in[H]} \log\!\left( \frac{4TH N_{\mathcal{R}_h}N_{\mathcal{V}_{h+1}}}{\delta} \right). \label{eq:Lambda95RL95app}\tag{25}\] Set \[\beta := \max\Bigl\{1,\;c_0 \sqrt{\Lambda_{\mathrm{RL}}}\Bigr\}, \qquad \lambda := \max\Bigl\{ 2H^2,\; c_\lambda\Bigl( \bar\sigma^2\bigl(d_{\mathrm{RL}}(\lambda,T)+\Lambda_{\mathrm{RL}}\bigr) + T\,\zeta_{\mathrm{RL}}^2 \Bigr) \Bigr\}, \label{eq:beta95lambda95rl95app}\tag{26}\] for sufficiently large universal constants, where \(\bar\sigma^2:=c_\sigma(1+H^2)\). The stagewise bonus is \[b_{t,h}(s,a):=\min\{B_h,\;\beta\,\mathrm{unc}_{t,h}(s,a)+\zeta_{\mathrm{RL}}\}. \label{eq:rl95bonus95def95app95fixed}\tag{27}\]

Define the optimistic scores, soft values, and Bellman target means by \[\begin{align} \widetilde{Q}_{t,h}(s,a)&:=\Pi{[0,B_h]}\big(\hat{Q}_{t,h}(s,a)+b_{t,h}(s,a)\big), \tag{28}\\ \widetilde{V}_{t,h}(s)&:=V_h(\widetilde{Q}_{t,h};s), \tag{29}\\ m_{t,h}(s,a) &:= (\mathcal{T}_{\eta,h}\widetilde{Q}_{t,h+1})(s,a) = r_h^\star(s,a)+\mathbb{E}_{s'\sim P_h(\cdot\mid s,a)}\!\big[\widetilde{V}_{t,h+1}(s')\big], \tag{30} \end{align}\] with \(\widetilde{Q}_{t,H+1}\equiv 0\).

For each \(t\in[T]\), stage \(h\in[H]\), and past episode \(i<t\), define the recomputed label \[y^{(t)}_{i,h} := r_{i,h}+\widetilde{V}_{t,h+1}(s_{i,h+1}), \label{eq:rl95recomputed95label95def}\tag{31}\] and the stagewise ERM \[\hat{Q}_{t,h}\in\mathop{\mathrm{arg\,min}}_{f\in\mathcal{R}_h}\sum_{i=1}^{t-1}\bigl(f(z_{i,h})-y^{(t)}_{i,h}\bigr)^2. \label{eq:rl95stagewise95erm95def}\tag{32}\]

The key technical point is that \(\widetilde{V}_{t,h+1}\) is data-dependent. We therefore prove the offset inequality uniformly over \(\mathcal{V}_{h+1}\) and only then instantiate it with \(V=\widetilde{V}_{t,h+1}\).

References↩︎