Paper deep dive
Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectives
Qiwei Di, Xuheng Li, Kaixuan Ji, Chenggong Zhang, Heyang Zhao, Quanquan Gu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/4/2026, 2:44:38 AM
Summary
This paper investigates the theoretical differences between off-policy and on-policy distillation (OPD) in the context of sequential knowledge distillation from multiple teachers. It establishes that off-policy distillation corresponds to minimizing forward Kullback-Leibler (KL) divergence, resulting in a weighted arithmetic mixture of teacher distributions, while on-policy distillation corresponds to minimizing reverse KL divergence, resulting in a normalized weighted geometric aggregate. The authors derive algorithms for both settings, prove logarithmic regret bounds in tabular and function approximation settings, and analyze the mechanisms behind OPD's benefits (retaining confident expert preferences) and fragility (sensitivity to low-probability correct responses and incorrect prefix favoring over long horizons).
Entities (8)
Relation Signals (7)
On-Policy Distillation → correspondsto → Reverse Kullback-Leibler divergence
confidence 95% · We connect off- and on-policy distillation to forward- and reverse-Kullback–Leibler (KL) objectives, respectively.
Off-policy Distillation → correspondsto → Forward Kullback-Leibler divergence
confidence 95% · We connect off- and on-policy distillation to forward- and reverse-Kullback–Leibler (KL) objectives, respectively.
Reverse Kullback-Leibler divergence → yields → Weighted geometric aggregate
confidence 93% · reverse KL yields a normalized weighted geometric aggregate.
Forward Kullback-Leibler divergence → yields → Weighted arithmetic mixture
confidence 93% · Forward Kullback--Leibler (KL) divergence yields a weighted arithmetic mixture
Reverse Kullback-Leibler divergence → issensitiveto → Teachers assigning low probabilities to correct responses
confidence 88% · but is more sensitive to teachers that assign very low probabilities to correct responses.
Reverse Kullback-Leibler divergence → retains → Confident expert's preferences
confidence 88% · Relative to forward KL, reverse KL can better retain a confident expert's preferences under uninformative feedback
Reverse Kullback-Leibler divergence → favors → Incorrect prefixes over long horizons
confidence 85% · Its token-level conditionals also reveal a dependence on continuation distributions that can favor incorrect prefixes over long horizons.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:On-policy distillation (OPD) learns from teacher feedback on student-generated responses and has shown promise in reducing forgetting relative to supervised fine-tuning (SFT). However, its benefits and fragility remain incompletely understood. We study sequential distillation from multiple teachers, where the student minimizes its average divergence from the teachers. Forward Kullback--Leibler (KL) divergence yields a weighted arithmetic mixture, while reverse KL yields a normalized weighted geometric aggregate. We develop algorithms that learn these targets under off-policy and on-policy feedback, respectively, establishing logarithmic regret bounds in the tabular setting and extending the analysis to function approximation. By analyzing these aggregation targets, we identify mechanisms that help explain both the benefits and fragility of OPD. Relative to forward KL, reverse KL can better retain a confident expert's preferences under uninformative feedback, but is more sensitive to teachers that assign very low probabilities to correct responses. Its token-level conditionals also reveal a dependence on continuation distributions that can favor incorrect prefixes over long horizons.
Tags
Links
- Source: https://arxiv.org/abs/2609.38666v1
- Canonical: https://arxiv.org/abs/2609.38666v1
Trouble viewing inline? Open PDF directly →
Full Text
198,078 characters extracted from source content.
Expand or collapse full text
Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training ObjectivesThanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: hyzhao@cs.ucla.eduThanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: qgu@cs.ucla.edu Qiwei Di Xuheng Li Kaixuan Ji Chenggong Zhang †thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: qiwei2000@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: xuheng.li@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: kaixuanji@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: chenggong61@g.ucla.edu Affiliation: Heyang Zhao Quanquan Gu Abstract On-policy distillation (OPD) learns from teacher feedback on student-generated responses and has shown promise in reducing forgetting relative to supervised fine-tuning (SFT). However, its benefits and fragility remain incompletely understood. We study sequential distillation from multiple teachers, where the student minimizes its average divergence from the teachers. Forward Kullback–Leibler (KL) divergence yields a weighted arithmetic mixture, while reverse KL yields a normalized weighted geometric aggregate. We develop algorithms that learn these targets under off-policy and on-policy feedback, respectively, establishing logarithmic regret bounds in the tabular setting and extending the analysis to function approximation. By analyzing these aggregation targets, we identify mechanisms that help explain both the benefits and fragility of OPD. Relative to forward KL, reverse KL can better retain a confident expert’s preferences under uninformative feedback, but is more sensitive to teachers that assign very low probabilities to correct responses. Its token-level conditionals also reveal a dependence on continuation distributions that can favor incorrect prefixes over long horizons. 1 Introduction Knowledge distillation transfers capabilities from teacher models to a student language model. A conventional approach is supervised fine-tuning (SFT) on teacher-generated responses, where the student learns to predict tokens along trajectories supplied by the teacher. On-policy distillation (OPD) (Agarwal et al., 2024; Lu and Lab, 2025) instead samples responses from the current student and obtains teacher logits along the resulting trajectories. This allows the student to learn from teacher feedback on its own behavior, an approach that has been adopted in the post-training of large language models (Yang et al., 2025; Xiao et al., 2026; Zeng et al., 2026). Related studies show that on-policy reinforcement learning can reduce forgetting relative to SFT (Shenfeld et al., 2026b; Chen et al., 2025) and, in some settings, recover capabilities lost during SFT (Jin et al., 2025). Despite these advantages, OPD can also be fragile. It may fail under teacher–student mismatch and suffer from training instability over long generation horizons (Li et al., 2026). However, a theoretical understanding of when OPD offers advantages over off-policy methods such as SFT and what limits those advantages remains to be established. Recent work has begun to clarify the conditions under which these advantages arise. For example, Sriraman et al. (2026) show that in a noisy-expert model, matching the clean expert’s return can require exponentially many offline samples in the horizon, whereas an on-policy algorithm achieves polynomial dependence when the corruption is known. Viano et al. (2026) show that on-policy value-based imitation can efficiently match the expert’s return under realizability of its action-value function, without requiring policy realizability. Together, these works establish conditions under which on-policy interaction offers advantages over offline learning. However, they do not directly explain the fragility observed in practical OPD, leaving a gap in our understanding of when and why it succeeds or fails. This naturally raises a question: What are the pros and cons caused by the distinction between off-policy and on-policy feedback in knowledge distillation? As a first step toward answering this question, we consider the setting where the student distills sequential data from multiple teachers, and the goal of the student is to minimize its average divergence from all teachers. Within this framework, we connect off- and on-policy distillation to forward- and reverse-Kullback–Leibler (KL) objectives, respectively. We then derive closed-form solutions for both objectives, offering a new perspective on the differences between SFT and OPD through the aggregation targets they induce. Our main contributions are listed as follows: • We propose a sequential distillation framework in which the student minimizes its average divergence from all teachers, and characterize the resulting aggregation targets under forward and reverse KL divergence. Specifically, forward KL yields a weighted arithmetic mixture of the teacher distributions, while reverse KL yields a normalized weighted geometric mean. We also derive the token-level conditionals of both targets for autoregressive generation. • We develop algorithms that learn the forward-KL target from off-policy data collection and the reverse-KL target from teacher logits on student-generated responses. In the tabular setting, we establish O~(logT) O( T) regret bounds for both protocols, with regret defined as the cumulative divergence between the student’s policy at each round and the corresponding aggregation target. We further extend the logarithmic regret to the setting with general function approximation. As a result, these guarantees connect off-policy distillation to the forward-KL aggregation objective and on-policy distillation to the reverse-KL aggregation objective. • We compare the two targets to examine the benefits and fragility of reverse-KL aggregation relative to forward-KL aggregation. First, we consider a setting with one confident expert teacher and several uninformative teachers and show that reverse-KL aggregation can retain a higher probability of the correct response than forward-KL aggregation. We also show that a misleading teacher can suppress correct responses under reverse KL, whereas forward KL preserves the expert’s weighted contribution. Finally, by examining the token-level conditionals, we show that over long horizons, reverse-KL aggregation can favor an incorrect prefix even while preserving the expert’s ranking of complete responses. These results offer possible explanations for the benefits and fragility of OPD observed in practice. Notation. For a positive integer n, let [n]:=1,…,n[n]:=\1,…,n\. For a finite set S, let Δ() (S) denote the set of probability distributions on S. We write (E) (E) for the indicator of an event E, and use E, ℙP, and Var for expectation, probability, and variance, respectively. For distributions p,q∈Δ()p,q∈ (S), the Kullback–Leibler divergence is KL(p∥q):=∑z∈p(z)log[p(z)/q(z)]KL(p\|q):= _z p(z) [p(z)/q(z)], where terms with p(z)=0p(z)=0 are zero, and KL(p∥q)=+∞KL(p\|q)=+∞ if p(z)>0=q(z)p(z)>0=q(z) for some z. We use O(⋅)O(·) for asymptotic upper bounds and O~(⋅) O(·) to hide logarithmic factors except logT T. The notation a≲ba b means a≤Cba≤ Cb for a universal constant C>0C>0. 2 Related Work Variants of on-policy distillation. On-policy distillation trains a language model by having it generate responses and using a teacher’s next-token distributions to supervise those responses (Agarwal et al., 2024; Gu et al., 2024). Following the empirical success of OPD, subsequent work has explored improvements to its training objectives, the use of teacher feedback, and the construction of teachers. To improve the training objective, existing methods introduce skew KL or contrastive losses (Ko et al., 2024; Ko et al., 2025), combine forward and reverse KL using hybrid objectives or teacher–student agreement (Zhu et al., 2026; Jin et al., 2026; Xing et al., 2026), or construct intermediate distributions between the teacher and student as training targets (Jang et al., 2026; Xie et al., 2026). To make better use of teacher feedback, other methods use response outcomes to weight or calibrate supervision (Zheng et al., 2026; Hou et al., 2026), reduce variance or reshape distillation rewards (Oh et al., 2026; Zhao et al., 2026a), and stabilize training through policy constraints and mixed rollout sources (Luo et al., 2026). Data collection is also adapted through selective teacher intervention during student generation (Xu et al., 2025) and early termination of student rollouts to reduce generation costs and avoid unreliable teacher feedback (Ziheng et al., 2026; Xin et al., 2026; Zhang et al., 2026). Beyond these changes to objectives and training, the source of supervision has expanded from a separate teacher model to self-teachers conditioned on reasoning traces, demonstrations, additional context, or environmental feedback (Zhao et al., 2026e; Shenfeld et al., 2026a; Ye et al., 2026; Hübotter et al., 2026; Liu et al., 2026). Multiple teachers can also supervise a shared student, whether they are independently trained domain experts (Ma et al., 2026a) or constructed through task-specific soft prompts (Ma et al., 2026b). These extensions motivate studying how distillation combines knowledge from different teachers. We refer readers to Song and Zheng (2026) for a comprehensive survey of OPD methods. Understanding on-policy distillation. Recent studies examine both the advantages and the failure modes of on-policy distillation. For capability retention during RL fine-tuning, Shenfeld et al. (2026b) relate reduced forgetting to an implicit bias toward solutions close to the initial policy in KL divergence, while Chen et al. (2025) emphasize on-policy data and mode-seeking behavior. Empirical studies also show that stronger teachers and denser supervision do not necessarily yield better distillation. Li et al. (2026) find that OPD gains depend on compatible reasoning patterns and the teacher offering capabilities beyond those already acquired by the student. They further observe that teacher guidance becomes less effective on longer student-generated prefixes, with training instability emerging at later tokens and spreading to earlier positions. Wang et al. (2026) identify settings where teacher–student mismatch causes incorrect responses to receive higher average token-level rewards than correct ones. Fu et al. (2026) identify three sources of instability in sampled-token OPD: predominantly negative token-level rewards that make learning sensitive to a small set of positively rewarded tokens; unreliable teacher feedback that can reinforce repetitive or meaningless continuations on student-generated prefixes; and tokenizer or special-token mismatches that penalize semantically valid outputs. The theoretical understanding of OPD is relatively limited. Sriraman et al. (2026) establish an exponential separation in horizon dependence between offline learning and an on-policy algorithm with known expert corruption, and Viano et al. (2026) obtain efficient imitation under expert action-value realizability without policy realizability. Our contribution is to characterize their distinct optimal targets when aggregating multiple teachers and connect those targets to learning guarantees. We then analyze how teacher confidence, misleading feedback, and autoregressive continuations affect the expert’s preferences at these targets, providing possible mechanisms for both capability retention and fragility. Relevant RL theory. To turn our perspective on distinct aggregation objectives into formal learning guarantees, we rely on the established RL theory, including supervised learning, KL-regularized bandits, and reinforcement learning with function approximation. Our analysis of the off-policy distillation protocol builds on the classical theory of behavior cloning, which aims to learn a policy from expert demonstrations. Classical analyses characterize how prediction errors compound under distribution shift (Syed and Schapire, 2010; Ross and Bagnell, 2010). DAgger addresses this issue by collecting expert feedback on learner-visited states, reducing imitation learning to no-regret online learning (Ross et al., 2011). Subsequent work further characterizes the statistical limits of imitation learning and the benefits of interaction (Rajaraman et al., 2020; Rajaraman et al., 2021). More recently, Foster et al. (2024) establish guarantees for behavior cloning with logarithmic loss under realizability, highlighting the importance of the loss function and policy-class complexity. Our forward-KL guarantees draw on log-loss prediction methods, combining smoothed probability estimation in the tabular setting and exponentially weighted policy aggregation under function approximation with a new one-sided bounded martingale concentration inequality. For on-policy distillation, our analysis draws on prior work establishing logarithmic regret for KL-regularized bandits and reinforcement learning. Zhao et al. (2026b) establish O(1/ϵ)O(1/ε) sample complexity in a sufficiently small-error regime under reference-policy coverage, and later Zhao et al. (2025) extend the results to obtain logarithmic regret in online contextual bandits and RL. For multi-armed bandits, Ji et al. (2026b) sharpen the dependence on the number of arms and regularization strength through nearly matching regret upper and lower bounds. Similar fast-rate guarantees have also been established in the offline setting for multi-armed bandits (Ji et al., 2026a), or with sufficient coverage conditions under KL and more general divergences (Zhao et al., 2026d; Zhao et al., 2026c). This line of work has since been extended to multiple reference models (Aminian et al., 2026), general preference models (Wu et al., 2026), game-theoretic settings (Nayak et al., 2025), differential privacy (Wu et al., 2025), and misspecified models (Hong et al., 2026). We adapt these techniques to sequential distillation by treating teacher log-probability ratios as rewards and accounting for dependence among rollouts from the same sampled teacher. This yields logarithmic regret guarantees for learning the reverse-KL aggregation target from on-policy teacher feedback. While we have established the connection between off- and on-policy distillation and their respective aggregation targets in the tabular setting, we seek to extend this connection to more general settings, drawing inspiration from prior work on general function approximation. In contextual bandits, Russo and Van Roy (2013) introduce eluder dimension to quantify how past observations constrain predictions at unobserved actions. Subsequent work extends eluder-based analyses to model estimation through value-targeted regression (Ayoub et al., 2020) and general value-function approximation (Wang et al., 2020). We use a generalized notion of eluder dimension developed in later work (Agarwal et al., 2023; Zhao et al., 2024; Di et al., 2024) and adapt it to the autoregressive setting. 3 Preliminaries We study sequential distillation, in which a single student learns from multiple teachers over successive training rounds with the goal of aggregating their knowledge. Let X be a finite context space of size S:=||S:=|X|, A a finite token space of size A:=||A:=|A|, and H the generation horizon. We write :=HY:=A^H for the response space. Each response y=(a1,…,aH)∈y=(a_1,…,a_H) is generated autoregressively, and we denote its length-(h−1)(h-1) prefix by y<h:=(a1,…,ah−1)y_<h:=(a_1,…,a_h-1). We consider a sequential distillation setting with a finite collection of teacher models indexed by ℐI, where |ℐ|=I|I|=I. For each i∈ℐi , let ρi∈Δ() _i∈ (X) be its context distribution and let pip_i be an autoregressive teacher policy such that for any h∈[H]h∈[H], the token conditionals are written as pi(⋅∣x,y<h)∈Δ().p_i(· x,y_<h)∈ (A). The induced sequence-level policy is pi(y∣x)=∏h=1Hpi(ah∣x,y<h).p_i(y x)= _h=1^Hp_i(a_h x,y_<h). At round t, the student policy πt _t is determined by the observations from previous rounds. A latent teacher index iti_t is then drawn uniformly from ℐI, independently of previous rounds. Conditional on iti_t, we draw m contexts independently from ρit _i_t. The entire batch shares this teacher: teacher responses and feedback are generated according to pitp_i_t. We consider two distillation protocols: • (Off-policy Distillation) We sample m contexts xt,j∼ρit\x_t,j\ _i_t and full teacher rollouts yt,j∼pit(⋅|xt,j)y_t,j p_i_t(·|x_t,j). If we further have access to the teacher logits, at each teacher-generated prefix yt,j,<hy_t,j,<h, we additionally observe the full logit vector Zt,j,h∈ℝZ_t,j,h ^A. The corresponding token log-probabilities are obtained by applying log-softmax: logpit(a∣xt,j,yt,j,<h) p_i_t(a x_t,j,y_t,j,<h) =Zt,j,h(a)−log∑b∈eZt,j,h(b),a∈. =Z_t,j,h(a)- _b e^Z_t,j,h(b), a . • (On-policy Distillation) We sample m contexts xt,j∼ρit\x_t,j\ _i_t, use the current student policy πt _t to roll out with yt,j∼πt(⋅|xt,j)y_t,j _t(·|x_t,j) token by token, and receive the per-token teacher log-probabilities lt,j,h=logpit(at,j,h|xt,j,yt,j,<h),h∈[H]. l_t,j,h= p_i_t(a_t,j,h\,|\,x_t,j,\,y_t,j,<h), h∈[H]. Rather than matching any single teacher selected in the current round, our goal is to learn a single autoregressive student policy that aggregates the behavior of all teacher models. This objective is designed to avoid catastrophic forgetting: sequentially adapting the student to the current teacher may reduce its loss on the corresponding task while degrading its performance on teachers encountered previously. To formalize the desired aggregate policy, let D:Δ()×Δ()→ℝ≥0∪+∞D: (Y)× (Y) _≥ 0∪\+∞\ be a divergence between distributions. Given the collection of teacher models (ρi,pi)i∈ℐ\( _i,p_i)\_i , we define the target policy by π∗∈argminπ:→Δ()∑i∈ℐx∼ρi[D(π(⋅∣x)∥pi(⋅∣x))]. π^*∈ argmin_π:X→ (Y) _i E_x _i [D (π(· x)\, \|\,p_i(· x) ) ]. (3.1) Here, π(⋅∣x)π(· x) and pi(⋅∣x)p_i(· x) denote the induced distributions over complete responses in =HY=A^H. Remark 3.1. The initial student policy can also serve as a reference during training. In reinforcement learning from human feedback (RLHF), for example, the updated policy is often regularized toward its initial policy to limit how far it departs from that reference. To capture this role in our framework, we regard the reference policy as an additional teacher and include it in the teacher set as a modeling simplification. Under this interpretation, even distillation from a single external teacher can be viewed as learning from both that teacher and the initial student. Specifically, when D is the reverse KL or forward KL divergence, the objective can be decomposed into a sum of token-level divergences using the chain rule. In this work, we will mainly focus on the cases of forward KL (D(p∥q)=KL(q∥p))(D(p\|q)=KL(q\|p)) and reverse KL (D(p∥q)=KL(p∥q))(D(p\|q)=KL(p\|q)). Regret. Since teacher indices are sampled uniformly, the marginal context distribution is the uniform mixture of the teacher context distributions: ρ¯(x):=1I∑i∈ℐρi(x). ρ(x):= 1I _i _i(x). For each choice of D, let π∗π^* denote the corresponding minimizer of (3.1). We define regret as the cumulative divergence of the student policies πtt=1T\ _t\_t=1^T from this target, averaged over the marginal context distribution: Regret(T):=∑t=1Tx∼ρ¯[D(πt(⋅∣x)∥π∗(⋅∣x))]. (T):= _t=1^TE_x ρ [D ( _t(· x)\, \|\,π^*(· x) ) ]. (3.2) SFT has a well-known forward-KL interpretation, while reverse KL is commonly used in OPD. Motivated by these connections, we take D(p∥q)=KL(q∥p)D(p\|q)=KL(q\|p) for off-policy distillation and D(p∥q)=KL(p∥q)D(p\|q)=KL(p\|q) for on-policy distillation. 4 Off-policy Distillation & Forward KL In this section, we study how off-policy feedback can be used to learn the forward-KL aggregate. We first characterize this target, then construct a tabular algorithm using teacher-generated responses, with or without full teacher logits, and establish logarithmic regret bounds. As the first step, the following theorem gives the target distribution and its token conditionals. Theorem 4.1 (Forward KL). If D(p∥q)=KL(q∥p)D(p\|q)=KL(q\|p), a minimizer of (3.1) is given at the sequence level, for each x with ρ¯(x)>0 ρ(x)>0, by πF∗(y|x)=∑i∈ℐwi(x)pi(y|x), _F^*(y|x)= _i w_i(x)p_i(y|x), (4.1) where wi(x)=ρi(x)/[∑j∈ℐρj(x)]w_i(x)= _i(x)/[ _j _j(x)]. Moreover, for any h∈[H]h∈[H], supposing ∑j∈ℐρj(x)pj(y<h∣x)>0 _j _j(x)p_j(y_<h x)>0, the token-level distributions are given by πF∗(a|x,y<h)=∑i∈ℐwi(x,y<h)pi(a|x,y<h),wi(x,y<h):=ρi(x)pi(y<h|x)∑j∈ℐρj(x)pj(y<h|x). _F^*(a|x,y_<h)= _i w_i(x,y_<h)\,p_i(a|x,y_<h), w_i(x,y_<h):= _i(x)\,p_i(y_<h|x) _j _j(x)\,p_j(y_<h|x). (4.2) Remark 4.2. The prefix-dependent weights admit a Bayesian interpretation. Under the off-policy sampling protocol, the teacher index is first sampled uniformly, the context is drawn from ρit _i_t, and the response is generated by pitp_i_t. Therefore, for every prefix satisfying ∑j∈ℐρj(x)pj(y<h∣x)>0 _j _j(x)p_j(y_<h x)>0, Bayes’ rule gives wi(x,y<h)=ℙ(it=i|xt,j=x,yt,j,<h=y<h). w_i(x,y_<h)=P (i_t=i |x_t,j=x,y_t,j,<h=y_<h ). Thus, wi(x,y<h)w_i(x,y_<h) is the posterior probability that teacher i generated the observed context and prefix. Consequently, teachers that better explain the observed prefix receive greater weight in the target policy’s next-token distribution. 4.1 Algorithm Design The posterior weights above also determine the next-token distribution in teacher-generated data. For a teacher-generated rollout (xt,j,yt,j)(x_t,j,y_t,j), let u∈h−1u ^h-1 denote a prefix. Conditioning on (xt,j,yt,j,<h)=(x,u)(x_t,j,y_t,j,<h)=(x,u) gives teacher weights wi(x,u)w_i(x,u). Hence, the next-token distribution is ℙ(at,j,h=a∣xt,j=x,yt,j,<h=u) (a_t,j,h=a x_t,j=x,\,y_t,j,<h=u ) =∑i∈ℐwi(x,u)pi(a|x,u)=πF∗(a|x,u). = _i w_i(x,u)p_i(a|x,u)= _F^*(a|x,u). Thus, at every visited prefix, the observed next token is a sample from the corresponding token conditional of the forward-KL target, which suggests estimating each target conditional from the token frequencies observed at the corresponding context–prefix pair. When full logits are available, each sampled token can instead be replaced by the teacher’s conditional probability vector. To express both updates in a common form, define qt,j,h(a):=(at,j,h=a)w/ologit,exp(Zt,j,h(a))∑b∈exp(Zt,j,h(b)),w/logit. q_t,j,h(a):= cases (a_t,j,h=a)&w/o\ logit,\\ (Z_t,j,h(a)) _b (Z_t,j,h(b)),&w/\ logit. cases We then define the per-round normalized counts as ct(x,u,a):=1m∑j=1m(xt,j=x,yt,j,<h=u)qt,j,h(a). c_t(x,u,a):= 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u)\,q_t,j,h(a). (4.3) Here, the token position h=|u|+1h=|u|+1 is determined by the prefix u and is hidden from the notation ct(x,u,a)c_t(x,u,a). The algorithm accumulates these counts after each round according to Wt(x,u,a) W_t(x,u,a) :=∑s=1tcs(x,u,a),Wt(x,u):=∑a∈Wt(x,u,a), := _s=1^tc_s(x,u,a),\ W_t(x,u):= _a W_t(x,u,a), and outputs the conditional policy π^t+1(a|x,u):=Wt(x,u,a)+1/2Wt(x,u)+A/2. π_t+1(a|x,u):= W_t(x,u,a)+1/2W_t(x,u)+A/2. (4.4) Here we add a (1/2)(1/2)-smoothing to each accumulated weight, following the spirit of the classical Krichevsky–Trofimov estimator (Krichevsky and Trofimov, 1981), which prevents zero predicted probabilities and assigns the uniform distribution to unvisited states. Algorithm 1 Per-Prefix Forward KL 1: Input: Context set X, token set A, horizon H. 2: Initialize W0(x,u,a)=0W_0(x,u,a)=0; equivalently, π^1(a|x,u)=1/A π_1(a|x,u)=1/A at every active prefix. 3: for t=1,…,Tt=1,…,T do 4: Observe the batch of teacher rollouts (xt,j,yt,j)j=1m\(x_t,j,y_t,j)\_j=1^m and, when available, the teacher logits Zt,j,hj,h\Z_t,j,h\_j,h. 5: For every level-h state (x,u)(x,u) and token a, set ct(x,u,a)c_t(x,u,a) as in (4.3). 6: Update the weight Wt(x,u,a)=Wt−1(x,u,a)+ct(x,u,a)W_t(x,u,a)=W_t-1(x,u,a)+c_t(x,u,a) and Wt(x,u)=∑aWt(x,u,a)W_t(x,u)= _aW_t(x,u,a). 7: Let π^t+1(a|x,u) π_t+1(a|x,u) be as defined in (4.4). 8: end for 9: Output π^tt=1T\ π_t\_t=1^T. 4.2 Theoretical Guarantees We now bound the cumulative forward-KL divergence from the target πF∗ _F^* to the policies produced by Algorithm 1. The following theorem gives logarithmic regret bounds under both feedback protocols, with expectation and probability taken over the teachers and rollouts sampled during training. Theorem 4.3. Let T≥2T≥ 2, and define the regret in (3.2) with D(p∥q)=KL(q∥p)D(p\|q)=KL(q\|p). Under the off-policy distillation protocol, both with and without access to full teacher logits, Algorithm 1 satisfies [Regret(T)] [Regret(T) ] ≤4SAHlogT. ≤ 4SA^H T. Moreover, for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, Algorithm 1 satisfies Regret(T)≤8SAHlogT+4H(1+log(2T+A))log1δ. (T)≤ 8SA^H T+4H (1+ (2T+A) ) 1δ. For fixed S, A, and H, Theorem 4.3 implies that the forward-KL divergence from πF∗ _F^* to π^t π_t, averaged over contexts and training rounds, decays as O(logT/T)O( T/T) in expectation and with high probability. Thus, off-policy feedback allows the student to learn the forward-KL aggregate in this average-divergence sense. The factor SAHSA^H reflects the size of the effective state–action space: at step h, each context–prefix pair (x,u)∈×h−1(x,u) ×A^h-1 acts as a distinct state, yielding SAhSA^h state–action pairs. The exponential dependence on H comes from the growth of the effective state space itself and the bound scales linearly with the total number of state–action pairs across all steps. 5 On-policy Distillation & Reverse KL In this section, we study how on-policy feedback can be used to learn the reverse-KL aggregate. With the same structure as the last section, we first characterize this target, then construct a tabular algorithm using teacher log-probabilities evaluated along student-generated responses. The following theorem gives the target distribution and its token conditionals. Theorem 5.1 (Reverse KL). Let wi(x)=ρi(x)/[∑j∈ℐρj(x)]w_i(x)= _i(x)/[ _j _j(x)]. Define the unnormalized token-level geometric mean gh(a|x,y<h) g_h(a|x,y_<h) :=∏i∈ℐpi(a|x,y<h)wi(x). := _i p_i(a|x,y_<h)^w_i(x). We define the value function iteratively backward as follows: for any x∈x , y∈Hy ^H, VH+1(x,y):=1,Vh(x,y<h) V_H+1(x,y):=1, V_h(x,y_<h) :=∑a∈gh(a|x,y<h)Vh+1(x,(y<h,a)),h=H,…,1. := _a g_h(a|x,y_<h)\,V_h+1 (x,(y_<h,a) ), h=H,…,1. Then the sequence-level reverse-KL minimizer is unique and is given by πR∗(y|x)=∏i∈ℐpi(y|x)wi(x)/V1(x). _R^*(y|x)= _i p_i(y|x)^w_i(x)/V_1(x). (5.1) Moreover, we assume that at every prefix y<hy_<h, Vh(x,y<h)>0V_h(x,y_<h)>0. Then, the token-level distribution is unique, i.e., πR∗(a|x,y<h)=gh(a|x,y<h)⋅Vh+1(x,(y<h,a))/Vh(x,y<h). _R^*(a|x,y_<h)=g_h(a|x,y_<h)· V_h+1 (x,(y_<h,a) )/V_h(x,y_<h). (5.2) Remark 5.2. In contrast with the last section, the teacher weights wi(x)w_i(x) depend only on the context. However, the token conditional is not obtained by normalizing ghg_h alone: each token score is also multiplied by Vh+1V_h+1, which sums the products of subsequent scores over all possible continuations. To summarize, the target accounts for both the current token and the continuations that follow it. 5.1 Algorithm Design To control the estimation error of teacher feedback, we assume that teacher token log-probabilities differ from those of a fixed reference policy by a bounded amount. Assumption 5.3. Let B>0B>0. There exists a fixed full-support reference policy πref _ref such that, for every i∈ℐi , h∈[H]h∈[H], and (x,u,a)∈×h−1×(x,u,a) ×A^h-1×A, |log[pi(a|x,u)/πref(a|x,u)]|≤B. | [p_i(a|x,u)/ _ref(a|x,u)] |≤ B. No such assumption is required for our forward-KL analysis, since the feedback consists of token indicators or teacher probabilities, both bounded in [0,1][0,1]. Here, we instead estimate teacher log-probabilities, which can be unbounded below. Assumption 5.3 imposes a two-sided bound on the token-level probability ratios between each teacher and the reference policy. Let ℱtF_t denote the observations available before round t, so that πt _t is ℱtF_t-measurable. For a student-generated rollout (xt,j,yt,j)(x_t,j,y_t,j), let u∈h−1u ^h-1 denote a prefix. At any visited context–prefix–token triple (x,u,a)(x,u,a), Bayes’ rule gives ℙ(it=i∣ℱt,xt,j=x,yt,j,<h=u,at,j,h=a)=ρi(x)πt(u|x)πt(a|x,u)∑k∈ℐρk(x)πt(u|x)πt(a|x,u)=wi(x). (i_t=i _t,\,x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a )= _i(x) _t(u|x) _t(a|x,u) _k _k(x) _t(u|x) _t(a|x,u)=w_i(x). Given the context and past observations, the prefix and token are generated by the student policy, which is shared across teacher indices. Their probabilities therefore cancel, leaving the teacher weights unchanged. Recall that the observed feedback is lt,j,h=logpit(a|x,u)l_t,j,h= p_i_t(a|x,u). Its conditional mean satisfies [lt,j,h|ℱt,xt,j=x,yt,j,<h=u,at,j,h=a] [l_t,j,h\, |\,F_t,\,x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a ] =∑i∈ℐwi(x)logpi(a|x,u)=loggh(a|x,u). = _i w_i(x) p_i(a|x,u)= g_h(a|x,u). Visits to (x,u,a)(x,u,a) thus provide unbiased observations of the log-geometric score loggh(a|x,u) g_h(a|x,u). Motivated by this, we estimate this score by averaging the feedback collected at the same triple. Define the cumulative visit count NtN_t, the cumulative feedback StS_t, and the empirical mean l¯t l_t as Nt(x,u,a) N_t(x,u,a) :=∑s=1t∑j=1m(xs,j=x,ys,j,<h=u,as,j,h=a), := _s=1^t _j=1^m (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a ), St(x,u,a) S_t(x,u,a) :=∑s=1t∑j=1mls,j,h(xs,j=x,ys,j,<h=u,as,j,h=a), := _s=1^t _j=1^ml_s,j,h (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a ), l¯t(x,u,a) l_t(x,u,a) :=St(x,u,a)/(Nt(x,u,a)∨1). :=S_t(x,u,a)/ (N_t(x,u,a) 1 ). (5.3) To account for uncertainty in these empirical means, we construct optimistic estimates of the log-geometric scores. The following lemma bounds the estimation error at visited triples. Lemma 5.4. Under Assumption 5.3, fix any δ∈(0,1)δ∈(0,1). With probability at least 1−2δ1-2δ, the following inequality holds for every t∈[T]t∈[T] and every (x,u,a)(x,u,a) with Nt(x,u,a)≥1N_t(x,u,a)≥ 1 simultaneously, |l¯t(x,u,a)−loggh(a|x,u)| | l_t(x,u,a)- g_h(a|x,u) | ≤βt(x,u,a), ≤ _t(x,u,a), where βt(x,u,a):=O~(BmH/(Nt(x,u,a)∨1)+BmH/(Nt(x,u,a)∨1)) _t(x,u,a):= O (B mH/(N_t(x,u,a) 1)+BmH/(N_t(x,u,a) 1) ). As a result, we can define the optimistic estimate l^t(x,u,a):=l¯t(x,u,a)+minβt(x,u,a),2BNt(x,u,a)≥1,logπref(a|x,u)+BNt(x,u,a)=0. l_t(x,u,a):= cases l_t(x,u,a)+ \ _t(x,u,a),2B \&N_t(x,u,a)≥ 1,\\ _ref(a|x,u)+B&N_t(x,u,a)=0. cases (5.4) At visited triples, Lemma 5.4 ensures that l^t(x,u,a)≥loggh(a|x,u) l_t(x,u,a)≥ g_h(a|x,u) on the confidence event. At unvisited triples, this inequality follows directly from Assumption 5.3. We then substitute these optimistic scores into the backward recursion defining the reverse-KL target in (5.2): g^t,h(a|x,u) g_t,h(a|x,u) :=exp(l^t(x,u,a)),V^t,H+1(x,y):=1, := ( l_t(x,u,a) ),\ V_t,H+1(x,y):=1, V^t,h(x,u) V_t,h(x,u) :=∑a∈g^t,h(a|x,u)V^t,h+1(x,(u,a)),h=H,…,1. := _a g_t,h(a|x,u) V_t,h+1 (x,(u,a) ), h=H,…,1. Therefore, for any h, any context x and prefix y<h=uy_<h=u, the output policy for the next token is defined as π^t+1(a|x,u):=g^t,h(a|x,u)V^t,h+1(x,(u,a))/V^t,h(x,u). π_t+1(a|x,u):= g_t,h(a|x,u) V_t,h+1 (x,(u,a) )/ V_t,h(x,u). (5.5) The algorithm is outlined in Algorithm 2. Algorithm 2 Per-Prefix Reverse KL 1: Input: Context set X, token set A, H, B, δ, and T. 2: Initialize π^1(a|x,u)=1/A π_1(a|x,u)=1/A for any (x,u,a)(x,u,a). 3: for t=1,…,Tt=1,…,T do 4: Observe the contexts xt,jj=1m\x_t,j\_j=1^m generated from ρit _i_t. 5: For each j, generate yt,j∼π^t(⋅|xt,j)y_t,j π_t(·|x_t,j) and observe lt,j,hh=1H\l_t,j,h\_h=1^H. 6: For each triple (x,u,a)(x,u,a), update Nt(x,u,a)N_t(x,u,a), St(x,u,a)S_t(x,u,a), and l¯t(x,u,a) l_t(x,u,a) as in (5.3). 7: Construct the optimistic estimate l^t l_t according to (5.4). 8: Define π^t+1 π_t+1 according to (5.5). 9: end for 10: Output π^tt=1T\ π_t\_t=1^T. 5.2 Theoretical Guarantees We now bound the regret induced by Algorithm 2. Theorem 5.5. Let T≥2T≥ 2, and define the regret in (3.2) with D(p∥q)=KL(p∥q)D(p\|q)=KL(p\|q). Under the on-policy distillation protocol and Assumption 5.3, for any δ∈(0,1/3)δ∈(0,1/3), with probability at least 1−3δ1-3δ, Algorithm 2 satisfies Regret(T) (T) ≤O~(B2H2SAHlogT). ≤ O (B^2H^2SA^H T ). For fixed S, A, H, B, and δ, Theorem 5.5 implies that the reverse-KL divergence from π^t π_t to πR∗ _R^*, averaged over contexts and training rounds, decays as O~(logT/T) O( T/T) with high probability. Thus, on-policy feedback allows the student to learn the reverse-KL aggregate in this average-divergence sense. As in the off-policy setting, the factor SAHSA^H reflects the size of the effective state–action space. For the detailed proof, see Appendix C. 6 Comparison of Distinct Aggregation Objectives The preceding sections establish learning guarantees that connect off-policy distillation to forward-KL aggregation and on-policy distillation to reverse-KL aggregation. We now examine the differences between these two forms of aggregation and their implications for combining the capabilities of multiple teachers in a single policy. 6.1 Uninformative Teachers Consider a context x that falls within teacher k’s area of expertise but is unfamiliar to the remaining teachers. We represent this difference in coverage by assuming that ρk(x) _k(x) is large relative to ∑i≠kρi(x) _i≠ k _i(x). The expert therefore receives a large aggregation weight α:=wk(x)∈(0,1)α:=w_k(x)∈(0,1). Write p(⋅|x):=pk(⋅|x)p(·|x):=p_k(·|x) and N:=||≥2N:=|Y|≥ 2, and let q:=p(y⋆|x)q:=p(y |x) denote the expert’s probability of a desirable response y⋆y . A value of q close to one means that the expert already produces the correct response with high probability. We ask whether the aggregate can maintain this high probability when the other teachers are uninformative. To represent the remaining teachers’ lack of information at x, we model their response distributions as uniform: pi(y|x)=1/Np_i(y|x)=1/N for every i≠ki≠ k and y∈y . These teachers have total weight 1−α1-α and are equivalent, under either objective, to a single uniform teacher with this weight. The two aggregation targets are therefore πF∗(y|x) _F^*(y|x) =αp(y|x)+1−αN,πR∗(y|x)=p(y|x)α∑z∈p(z|x)α. =α p(y|x)+ 1-αN, _R^*(y|x)= p(y|x)^α _z p(z|x)^α. For a concrete comparison, suppose y⋆y is the only correct response and q∈(1/N,1)q∈(1/N,1), with the expert assigning uniform probability to each incorrect response. The following proposition shows that, for fixed teacher weights and response space, the comparison is determined by a confidence threshold. Proposition 6.1. Fix N≥2N≥ 2 and α∈(0,1)α∈(0,1), and consider the teacher distributions above. If N≥3N≥ 3, there exists a unique qc=qc(N,α)∈(1/N,1)q_c=q_c(N,α)∈(1/N,1) such that, for every q∈(1/N,1)q∈(1/N,1), πR∗(y⋆|x)>πF∗(y⋆|x)⟺q>qc. _R^*(y |x)> _F^*(y |x) q>q_c. The proof is given in Appendix E. Figure 1(a) plots the two correct-response probabilities for q>0.5q>0.5, with N=10N=10 and α=0.9α=0.9 fixed. Figure 1: Forward- and reverse-KL aggregation with expert weight α=0.9α=0.9. Panels (a,b) use N=10N=10 responses, with each teacher distributing its remaining probability uniformly over incorrect responses. (a) The other teachers are uniform, and expert confidence q varies above 0.50.5; the targets cross at qc≈0.7617q_c≈ 0.7617. (b) The expert’s probability is fixed at q=0.99q=0.99, while the other teacher’s correct-response probability ε varies on a logarithmic axis. (c) For binary responses, the horizon H varies while all token probabilities remain fixed. The expert chooses the correct first token a with probability 0.990.99; subsequent tokens have probabilities (0.99,0.01)(0.99,0.01) after a and (1/2,1/2)(1/2,1/2) after b. The other teacher is uniform at every prefix. Remark 6.2. This setting illustrates how forgetting can arise when a student, after acquiring an expert teacher’s capability, continues learning from other teachers that are uninformative on the same context. Proposition 6.1 identifies when this reduction is smaller under reverse aggregation than under forward aggregation, offering a possible explanation for empirical findings that OPD is less susceptible to forgetting than SFT. For example, Shenfeld et al. (2026a) show in both single-task and sequential continual-learning experiments that OPD preserves general and previously acquired capabilities while learning new tasks, whereas SFT leads to substantial performance regression. Similar observations are reported by Hübotter et al. (2026) and Ma et al. (2026b), and have also been made in the field of vision language action model (Zhong et al., 2026). 6.2 Misleading Teachers The preceding examples model teachers that are unfamiliar with a context as uniform. In this section, we consider another scenario where teachers may be misleading. As the small aggregation weights of some teachers reflect their limited coverage of the context, their predictions on such unfamiliar contexts may be highly inaccurate. Thus, they may assign extremely low probability to the correct response. We show that forward aggregation preserves a high probability of the correct response when the expert is highly confident and receives most of the weight. Under reverse aggregation, however, even a teacher with a small weight can drive this probability arbitrarily close to zero by assigning sufficiently low probability to the correct response. Figure 1(b) illustrates this effect by varying only the misleading teacher’s correct-response probability ε , while fixing the expert’s probability at q=0.99q=0.99 and the teacher weights at 0.90.9 and 0.10.1. As ε decreases toward zero, the reverse target approaches zero, whereas the forward target remains bounded below by the expert’s weighted contribution. The following proposition extends this comparison to a set of correct responses. Proposition 6.3. Let ∅≠E⊊ ≠ E be a set of correct responses. For any teacher k, the forward target satisfies πF∗(E|x)≥wkpk(E|x). _F^*(E|x)≥ w_kp_k(E|x). In contrast, for any α,q,η∈(0,1)α,q,η∈(0,1), there exist two teachers with weights w1=αw_1=α and w2=1−αw_2=1-α, each assigning positive probability to every response, such that p1(E|x)=q,πR∗(E|x)<η.p_1(E|x)=q, _R^*(E|x)<η. Intuitively, forward aggregation is a weighted sum of nonnegative probabilities, so other teachers cannot cancel the expert’s contribution to correct responses. Reverse aggregation instead averages log-probabilities, which can be arbitrarily negative. Consequently, a teacher that assigns sufficiently low probability to correct responses relative to incorrect ones can override the expert’s preference, even with a small aggregation weight. Remark 6.4. The sensitivity identified by Proposition 6.3 offers a possible explanation for some empirical failures of OPD under teacher–student mismatch. Such failures can occur even with a stronger teacher: Ma et al. (2026a) find that a stronger but distributionally different teacher produces predominantly negative feedback on student rollouts and degrades student performance. Related empirical remedies address either extreme feedback or the initial mismatch. Wang et al. (2026) show that clipping or compressing extreme token-level log-ratios can improve training stability, while Li et al. (2026) find that an SFT cold start on teacher-generated responses reduces the initial pattern mismatch and improves subsequent OPD. 6.3 Long Horizons The preceding comparisons focus on the probabilities of complete responses. During autoregressive generation, however, reverse aggregation can favor a prefix that the expert considers less likely, even while preserving the expert’s ranking of complete responses. This can steer generation toward an incorrect trajectory. Consider an expert teacher p1p_1 with weight α∈(0,1)α∈(0,1) and a uniform teacher p2p_2 with weight β=1−αβ=1-α. Since p2(y|x)=A−Hp_2(y|x)=A^-H is the same for every complete response, its contribution to the geometric aggregate cancels upon normalization, leaving πR∗(y|x)=p1(y|x)α/[∑z∈p1(z|x)α]. _R^*(y|x)=p_1(y|x)^α/ [ _z p_1(z|x)^α ]. Raising probabilities to the power α<1α<1 preserves the ranking of complete responses while increasing the relative weight of less likely responses. Token-level probabilities, however, also depend on a sum over possible continuations, as shown by (5.2). For a prefix u of length h−1h-1 and a candidate token c, πR∗(c|x,u)∝p1(c|x,u)α∑v∈H−hp1(v|x,u,c)α. _R^*(c|x,u) p_1(c|x,u)^α _v ^H-hp_1(v|x,u,c)^α. Since α<1α<1, spreading probability mass more evenly across continuations increases this sum. The continuation factor can therefore favor tokens with more diffuse continuations over those whose continuations are concentrated on a few responses. To further illustrate this effect, consider responses of length H over =a,bA=\a,b\, where a is the correct first token. The expert p1p_1 has weight α=0.9α=0.9 and selects a at the first step with probability r=0.99r=0.99. The other teacher p2p_2 has weight β=0.1β=0.1 and assigns probability 1/21/2 to each token at every prefix. At each of the remaining H−1H-1 positions, the expert’s token distribution depends only on the first token. After an initial a, it assigns probability 0.990.99 to a and 0.010.01 to b, regardless of the intervening tokens. After an initial b, it assigns probability 1/21/2 to each token. Thus, the expert’s continuations are concentrated after a and uniform after b, while all token probabilities remain strictly positive. Under forward aggregation, the probability of choosing a at the first step is the weighted average of the teachers’ corresponding probabilities and is therefore independent of the continuation distributions and the horizon. Figure 1(c) plots the probability of choosing the correct first token a as H varies from 11 to 4040, keeping the teacher weights and token-level probabilities fixed. More generally, the following proposition shows that this reversal can occur even when the uniform teacher receives an arbitrarily small weight. Proposition 6.5. Fix β∈(0,1/2)β∈(0,1/2) and r∈(1/2,1)r∈(1/2,1). For every sufficiently large horizon H, there exist two teacher policies p1p_1 and p2p_2 on =a,bHY=\a,b\^H, each assigning positive probability to every response, such that p1(a|x)=rp_1(a|x)=r and p2p_2 is uniform at every prefix. With aggregation weights w1(x)=1−βw_1(x)=1-β and w2(x)=βw_2(x)=β, their forward and reverse targets satisfy πF∗(a|x)>πF∗(b|x),πR∗(a|x)<πR∗(b|x). _F^*(a|x)> _F^*(b|x), _R^*(a|x)< _R^*(b|x). Remark 6.6. The reversal in Proposition 6.5 illustrates a potential difficulty for OPD on long responses: increasing the horizon can change the reverse aggregation target’s preferred prefix while the expert’s preference remains fixed. Empirically, Li et al. (2026) find that longer rollouts can exhibit late-stage collapse, with instability emerging at later tokens and spreading toward earlier positions. Ziheng et al. (2026) find that teachers are less able to recover correct answers from longer student-generated prefixes and that stopping rollouts early can improve training stability. 7 Conclusion We studied off- and on-policy distillation in a sequential multi-teacher framework. By characterizing the forward- and reverse-KL targets and establishing learning guarantees, we connected the two feedback protocols to distinct aggregation objectives. Our comparisons show that reverse-KL aggregation can better preserve a confident expert’s preference in the presence of uniform teachers, but can suppress correct responses under misleading feedback or favor incorrect prefixes over long horizons. These results offer possible explanations for the benefits and fragility of OPD relative to SFT, and provide a perspective on the difference between SFT and OPD through the lens of distinct aggregation objectives. AI use statement This work builds on the authors’ research intuition and ideas. We used AI models, including GPT 5.6 Sol, GPT 6 Astra, Claude Fable 5, and Grok 4.6, to help articulate and summarize these ideas and to draft and polish the manuscript. These models also assisted in proving several key technical lemmas and developing proof strategies. The authors verified the proofs and reviewed the AI-assisted writing, and take full responsibility for the correctness and final content of the paper. Appendix A Proof of the KL Aggregation Theorems In this section, we prove Theorems 4.1 and 5.1. We first reduce the objective to a separate optimization problem at each context. Recall that ρ¯(x):=1I∑i∈ℐρi(x),wi(x):=ρi(x)∑j∈ℐρj(x) ρ(x):= 1I _i _i(x), w_i(x):= _i(x) _j _j(x) for every x with ρ¯(x)>0 ρ(x)>0. Define ℐx+ _x^+ :=i∈ℐ:wi(x)>0,LD,x(π):=∑i∈ℐx+wi(x)D(π(⋅∣x)∥pi(⋅∣x)). :=\i :w_i(x)>0\,\ L_D,x(π):= _i _x^+w_i(x)D (π(· x)\, \|\,p_i(· x) ). Using ρi(x)=Iρ¯(x)wi(x) _i(x)=I ρ(x)w_i(x), we obtain ∑i∈ℐx∼ρi[D(π(⋅∣x)∥pi(⋅∣x))]=I∑x:ρ¯(x)>0ρ¯(x)LD,x(π). _i E_x _i [D (π(· x)\, \|\,p_i(· x) ) ]=I _x: ρ(x)>0 ρ(x)L_D,x(π). (A.1) The optimization domain in (3.1) allows a separate distribution in Δ() (Y) at every context. Therefore, it suffices to minimize LD,xL_D,x at each context with ρ¯(x)>0 ρ(x)>0. Contexts with ρ¯(x)=0 ρ(x)=0 do not affect the objective, and their policies may be chosen arbitrarily. Throughout the proofs, zero-weight teachers are omitted from geometric products. We use the conventions 0log(0/q)=00 (0/q)=0 for q≥0q≥ 0 and plog(p/0)=+∞p (p/0)=+∞ for p>0p>0. A.1 Proof of Theorem 4.1 Proof of Theorem 4.1. Fix a context x with ρ¯(x)>0 ρ(x)>0. For forward KL, the contextwise objective in (A.1) is LF,x(π):=∑i∈ℐx+wi(x)KL(pi(⋅∣x)∥π(⋅∣x)). L_F,x(π):= _i _x^+w_i(x)KL (p_i(· x)\, \|\,π(· x) ). We first identify its minimizing sequence distribution, and then derive the corresponding token conditionals. Sequence-level minimizer. Define the candidate distribution qF(y∣x):=∑i∈ℐx+wi(x)pi(y∣x),y∈. q_F(y x):= _i _x^+w_i(x)p_i(y x), y . Since the weights are nonnegative and sum to one, qF(⋅∣x)∈Δ()q_F(· x)∈ (Y). Let F(x) _F(x) :=y∈:qF(y∣x)>0, :=\y :q_F(y x)>0\, CF(x) C_F(x) :=∑i∈ℐx+wi(x)KL(pi(⋅∣x)∥qF(⋅∣x)). := _i _x^+w_i(x)KL (p_i(· x)\, \|\,q_F(· x) ). For every i∈ℐx+i _x^+, we have qF(y∣x)≥wi(x)pi(y∣x)q_F(y x)≥ w_i(x)p_i(y x). Consequently, CF(x)C_F(x) is finite and does not depend on π. For a policy that is positive on F(x)S_F(x), expanding the KL divergences gives LF,x(π)−CF(x) L_F,x(π)-C_F(x) =∑i∈ℐx+wi(x)∑y∈F(x)pi(y∣x)logqF(y∣x)π(y∣x) = _i _x^+w_i(x) _y _F(x)p_i(y x) q_F(y x)π(y x) =∑y∈F(x)qF(y∣x)logqF(y∣x)π(y∣x) = _y _F(x)q_F(y x) q_F(y x)π(y x) =KL(qF(⋅∣x)∥π(⋅∣x)), =KL (q_F(· x)\, \|\,π(· x) ), (A.2) where the second equality uses the definition of qFq_F. If π assigns zero probability to some y∈F(x)y _F(x), at least one positive-weight teacher assigns positive probability to that response. In that case, both sides of (A.2) are +∞+∞, so the identity remains valid in the extended-real sense. By nonnegativity of KL divergence, the right-hand side of (A.2) is minimized at zero, with equality if and only if π(⋅∣x)=qF(⋅∣x)π(· x)=q_F(· x). Thus, the minimizing sequence distribution is unique at this context and satisfies πF∗(y∣x)=qF(y∣x)=∑i∈ℐwi(x)pi(y∣x), _F^*(y x)=q_F(y x)= _i w_i(x)p_i(y x), which proves (4.1). Token-level conditionals. Fix h∈[H]h∈[H] and u∈h−1u ^h-1. Marginalizing the sequence distribution over all continuations gives πF∗(u∣x) _F^*(u x) =∑i∈ℐwi(x)pi(u∣x), = _i w_i(x)p_i(u x), πF∗((u,a)∣x) _F^*((u,a) x) =∑i∈ℐwi(x)pi(u∣x)pi(a∣x,u). = _i w_i(x)p_i(u x)p_i(a x,u). (A.3) The first equality follows from linearity of marginalization; the second additionally uses the autoregressive factorization of each teacher. Suppose that ∑iρi(x)pi(u∣x)>0 _i _i(x)p_i(u x)>0. Then πF∗(u∣x)>0 _F^*(u x)>0, and taking the ratio of the two prefix probabilities yields πF∗(a∣x,u) _F^*(a x,u) =πF∗((u,a)∣x)πF∗(u∣x) = _F^*((u,a) x) _F^*(u x) =∑i∈ℐwi(x)pi(u∣x)pi(a∣x,u)∑j∈ℐwj(x)pj(u∣x) = _i w_i(x)p_i(u x)p_i(a x,u) _j w_j(x)p_j(u x) =∑i∈ℐρi(x)pi(u∣x)∑j∈ℐρj(x)pj(u∣x)pi(a∣x,u), = _i _i(x)p_i(u x) _j _j(x)p_j(u x)p_i(a x,u), (A.4) where the last equality substitutes the definition of wi(x)w_i(x) and cancels its common normalization factor. This is exactly (4.2). At a prefix with πF∗(u∣x)=0 _F^*(u x)=0, the conditional may be chosen arbitrarily without changing the sequence distribution. Since x was arbitrary, combining the contextwise minimizers using (A.1) completes the proof. ∎ A.2 Proof of Theorem 5.1 Proof of Theorem 5.1. Fix a context x with ρ¯(x)>0 ρ(x)>0. The contextwise reverse-KL objective is LR,x(π):=∑i∈ℐx+wi(x)KL(π(⋅∣x)∥pi(⋅∣x)). L_R,x(π):= _i _x^+w_i(x)KL (π(· x)\, \|\,p_i(· x) ). Define the unnormalized sequence score and its total mass by Gx(y):=∏i∈ℐx+pi(y∣x)wi(x),Zx:=∑y∈Gx(y). G_x(y):= _i _x^+p_i(y x)^w_i(x), Z_x:= _y G_x(y). We first show that Zx=V1(x)Z_x=V_1(x), then identify the minimizing sequence distribution and its token conditionals. Backward recursion and normalization. By the autoregressive factorization of the teachers, Gx(y) G_x(y) =∏i∈ℐx+(∏h=1Hpi(ah∣x,y<h))wi(x) = _i _x^+ ( _h=1^Hp_i(a_h x,y_<h) )^w_i(x) =∏h=1H∏i∈ℐx+pi(ah∣x,y<h)wi(x) = _h=1^H _i _x^+p_i(a_h x,y_<h)^w_i(x) =∏h=1Hgh(ah∣x,y<h). = _h=1^Hg_h(a_h x,y_<h). (A.5) For every h∈[H+1]h∈[H+1] and u∈h−1u ^h-1, we claim that Vh(x,u)=∑ah,…,aH∈∏k=hHgk(ak∣x,y<k),y=(u,ah,…,aH). V_h(x,u)= _a_h,…,a_H _k=h^Hg_k(a_k x,y_<k), y=(u,a_h,…,a_H). (A.6) At h=H+1h=H+1, the sum contains one empty continuation and its empty product is one, so the identity agrees with VH+1(x,y)=1V_H+1(x,y)=1. Suppose that it holds at level h+1h+1. Using the defining recursion for VhV_h, we obtain Vh(x,u) V_h(x,u) =∑ah∈gh(ah∣x,u)Vh+1(x,(u,ah)) = _a_h g_h(a_h x,u)V_h+1(x,(u,a_h)) =∑ah∈gh(ah∣x,u)∑ah+1,…,aH∈∏k=h+1Hgk(ak∣x,y<k) = _a_h g_h(a_h x,u) _a_h+1,…,a_H _k=h+1^Hg_k(a_k x,y_<k) =∑ah,…,aH∈∏k=hHgk(ak∣x,y<k), = _a_h,…,a_H _k=h^Hg_k(a_k x,y_<k), where the second equality uses the induction hypothesis. This proves (A.6) by backward induction. At the empty prefix, it gives V1(x)=∑y∈Gx(y)=Zx. V_1(x)= _y G_x(y)=Z_x. (A.7) In particular, the positivity condition V1(x)>0V_1(x)>0 implies Zx>0Z_x>0. Sequence-level minimizer. Define qR(y∣x):=Gx(y)Zx,R(x):=y∈:Gx(y)>0. q_R(y x):= G_x(y)Z_x, _R(x):=\y :G_x(y)>0\. By (A.7), qR(⋅∣x)q_R(· x) is a probability distribution. The set R(x)S_R(x) is the common support of all positive-weight teachers. Any policy assigning positive mass outside this set has infinite reverse KL to at least one such teacher, and therefore incurs infinite objective value. For a policy supported on R(x)S_R(x), we have LR,x(π) L_R,x(π) =∑y∈R(x)π(y∣x)[logπ(y∣x)−∑i∈ℐx+wi(x)logpi(y∣x)] = _y _R(x)π(y x) [ π(y x)- _i _x^+w_i(x) p_i(y x) ] =∑y∈R(x)π(y∣x)logπ(y∣x)Gx(y) = _y _R(x)π(y x) π(y x)G_x(y) =∑y∈R(x)π(y∣x)logπ(y∣x)qR(y∣x)−logZx = _y _R(x)π(y x) π(y x)q_R(y x)- Z_x =KL(π(⋅∣x)∥qR(⋅∣x))−logV1(x). =KL (π(· x)\, \|\,q_R(· x) )- V_1(x). (A.8) Here, the second equality uses the definition of GxG_x, the third uses Gx=ZxqRG_x=Z_xq_R and ∑yπ(y∣x)=1 _yπ(y x)=1, and the last uses (A.7). The same identity holds in the extended-real sense when π puts positive mass outside R(x)S_R(x), since both sides are then infinite. Since −logV1(x)- V_1(x) does not depend on π, nonnegativity of KL divergence shows that the unique minimizing sequence distribution is πR∗(y∣x)=qR(y∣x)=∏i∈ℐx+pi(y∣x)wi(x)V1(x), _R^*(y x)=q_R(y x)= _i _x^+p_i(y x)^w_i(x)V_1(x), which proves (5.1). Token-level conditionals. Fix h∈[H]h∈[H] and a prefix u=(u1,…,uh−1)u=(u_1,…,u_h-1), and let G<h(x,u):=∏k=1h−1gk(uk∣x,u<k), G_<h(x,u):= _k=1^h-1g_k(u_k x,u_<k), where the empty product is one. Combining (A.5) and (A.6), and summing over all continuations, gives πR∗(u∣x) _R^*(u x) =G<h(x,u)Vh(x,u)V1(x), = G_<h(x,u)V_h(x,u)V_1(x), πR∗((u,a)∣x) _R^*((u,a) x) =G<h(x,u)gh(a∣x,u)Vh+1(x,(u,a))V1(x). = G_<h(x,u)g_h(a x,u)V_h+1(x,(u,a))V_1(x). (A.9) If πR∗(u∣x)>0 _R^*(u x)>0, then both G<h(x,u)G_<h(x,u) and Vh(x,u)V_h(x,u) are positive. Taking the ratio of the two prefix probabilities yields πR∗(a∣x,u) _R^*(a x,u) =πR∗((u,a)∣x)πR∗(u∣x) = _R^*((u,a) x) _R^*(u x) =gh(a∣x,u)Vh+1(x,(u,a))Vh(x,u), = g_h(a x,u)V_h+1(x,(u,a))V_h(x,u), (A.10) which is (5.2). These conditionals are uniquely determined at every positive-probability prefix. At a null prefix with Vh(x,u)>0V_h(x,u)>0, the right-hand side of (A.10) still defines a valid conditional, because its numerator sums to Vh(x,u)V_h(x,u). When Vh(x,u)=0V_h(x,u)=0, choose an arbitrary conditional instead. To verify that these choices induce the minimizing sequence law, take any y∈R(x)y _R(x). All factors and continuation values along this response are positive, so the selected conditionals telescope: ∏h=1Hgh(ah∣x,y<h)Vh+1(x,y≤h)Vh(x,y<h) _h=1^H g_h(a_h x,y_<h)V_h+1(x,y_≤ h)V_h(x,y_<h) =∏h=1Hgh(ah∣x,y<h)V1(x) = _h=1^Hg_h(a_h x,y_<h)V_1(x) =Gx(y)Zx=πR∗(y∣x), = G_x(y)Z_x= _R^*(y x), where y≤h:=(a1,…,ah)y_≤ h:=(a_1,…,a_h) and the first equality uses VH+1(x,y)=1V_H+1(x,y)=1. These probabilities already sum to one over R(x)S_R(x). Since every selected token conditional is normalized, the induced autoregressive law assigns zero mass to all other responses and equals πR∗(⋅∣x) _R^*(· x). Thus, uniqueness concerns the sequence distribution and its conditionals at positive-probability prefixes, not arbitrary conditionals at null prefixes. Applying (A.1) across contexts completes the proof. ∎ Appendix B Proof of Theorem 4.3 Proof. In this section, we prove Theorem 4.3. Let ℱt:=σ(xs,j,ys,j,qs,j,h(a):1≤s<t,j∈[m],h∈[H],a∈)F_t:=σ (\x_s,j,\,y_s,j,\,q_s,j,h(a):1≤ s<t,\,j∈[m],\,h∈[H],\,a \ ). Then, π^t π_t is ℱtF_t-measurable. Fix a level h, a state (x,u)∈×h−1(x,u) ×A^h-1, and a token a∈a . Under either feedback model, [qt,j,h(a)|ℱt,it=i,xt,j=x,yt,j,<h=u]=pi(a|x,u). [q_t,j,h(a)\, |\,F_t,\,i_t=i,\,x_t,j=x,\,y_t,j,<h=u ]=p_i(a|x,u). (B.1) Indeed, without logits, qt,j,h(a)=(at,j,h=a)q_t,j,h(a)= (a_t,j,h=a), whose conditional mean is pi(a|x,u)p_i(a|x,u). With logits, qt,j,h(a)=pi(a|x,u)q_t,j,h(a)=p_i(a|x,u) is observed directly. Conditioned on it=i_t=i, using the independence of samples between each round, we have ℙ(xt,j=x,yt,j,<h=u|it=i,ℱt)=ρi(x)pi(u|x). (x_t,j=x,\,y_t,j,<h=u|i_t=i,F_t )= _i(x)p_i(u|x). (B.2) Combining (B.1) and (B.2), and using that iti_t is uniform over ℐI, we have [(xt,j=x,yt,j,<h=u)qt,j,h(a)|ℱt] [ (x_t,j=x,\,y_t,j,<h=u)q_t,j,h(a)\, |\,F_t ] =∑i∈ℐℙ(it=i∣ℱt)[(xt,j=x,yt,j,<h=u)qt,j,h(a)|ℱt,it=i] = _i P(i_t=i _t)\,E [ (x_t,j=x,\,y_t,j,<h=u)q_t,j,h(a)\, |\,F_t,i_t=i ] =1I∑i∈ℐℙ(xt,j=x,yt,j,<h=u|ℱt,it=i) = 1I _i P (x_t,j=x,\,y_t,j,<h=u |F_t,i_t=i ) ⋅[qt,j,h(a)|ℱt,it=i,xt,j=x,yt,j,<h=u] ·E [q_t,j,h(a) |F_t,i_t=i,\,x_t,j=x,\,y_t,j,<h=u ] =1I∑i∈ℐρi(x)pi(u|x)pi(a|x,u). = 1I _i _i(x)p_i(u|x)p_i(a|x,u). (B.3) The right-hand side is precisely the joint prefix–token probability under the forward target (4.2). More explicitly, 1I∑i∈ℐρi(x)pi(u|x)pi(a|x,u)=ρ¯(x)πF∗(u|x)πF∗(a|x,u). 1I _i _i(x)p_i(u|x)p_i(a|x,u)= ρ(x) _F^*(u|x) _F^*(a|x,u). (B.4) To see this identity, first note that ρ¯(x)πF∗(u|x) ρ(x) _F^*(u|x) =(1I∑k∈ℐρk(x))(∑i∈ℐρi(x)∑k∈ℐρk(x)pi(u|x)) = ( 1I _k _k(x) ) ( _i _i(x) _k _k(x)p_i(u|x) ) =1I∑i∈ℐρi(x)pi(u|x). = 1I _i _i(x)p_i(u|x). (B.5) Moreover, conditioned on the prefix (x,u)(x,u), the posterior weight of teacher i is wi(x,u)=ρi(x)pi(u|x)∑k∈ℐρk(x)pk(u|x). w_i(x,u)= _i(x)p_i(u|x) _k _k(x)p_k(u|x). Therefore, πF∗(a|x,u) _F^*(a|x,u) =∑i∈ℐwi(x,u)pi(a|x,u) = _i w_i(x,u)p_i(a|x,u) =∑i∈ℐρi(x)pi(u|x)pi(a|x,u)∑k∈ℐρk(x)pk(u|x). = _i _i(x)p_i(u|x)p_i(a|x,u) _k _k(x)p_k(u|x). (B.6) Multiplying (B.5) and (B.6), the prefix normalizing factor cancels, giving ρ¯(x)πF∗(u|x)πF∗(a|x,u)=1I∑i∈ℐρi(x)pi(u|x)pi(a|x,u). ρ(x) _F^*(u|x) _F^*(a|x,u)= 1I _i _i(x)p_i(u|x)p_i(a|x,u). Recall that ct(x,u,a):=1m∑j=1m(xt,j=x,yt,j,<h=u)qt,j,h(a). c_t(x,u,a):= 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u)\,q_t,j,h(a). Averaging (B.3) over the m rollouts therefore yields [ct(x,u,a)|ℱt]=ρ¯(x)πF∗(u|x)πF∗(a|x,u). [c_t(x,u,a)\, |\,F_t ]= ρ(x) _F^*(u|x) _F^*(a|x,u). (B.7) Only linearity of expectation is used here. In particular, the m rollouts need not be independent after marginalizing over their shared teacher index iti_t. For any autoregressive policy π, define its round-t empirical loss by ℓt(π):=−∑h=1H∑x∈∑u∈h−1∑a∈ct(x,u,a)logπ(a|x,u). _t(π):=- _h=1^H _x _u ^h-1 _a c_t(x,u,a) π(a|x,u). (B.8) Define L(π):=x∼ρ¯,y∼πF∗(⋅|x)[−logπ(y|x)]L(π):=E_x ρ,y _F^*(·|x) [- π(y|x) ]. Using the autoregressive representation of π, we have −logπ(y|x)=−∑h=1Hlogπ(ah|x,y<h). - π(y|x)=- _h=1^H π(a_h|x,y_<h). Consequently, using the linearity of expectation, L(π)L(π) can be expressed as L(π)=−∑h=1H∑x,u,aρ¯(x)πF∗(u|x)πF∗(a|x,u)logπ(a|x,u). L(π)=- _h=1^H _x,u,a ρ(x) _F^*(u|x) _F^*(a|x,u) π(a|x,u). Substituting (B.7) into (B.8) now gives, for every ℱtF_t-measurable policy π, [ℓt(π)|ℱt]=L(π). [ _t(π)\, |\,F_t ]=L(π). (B.9) Moreover, we have L(π)−L(πF∗) L(π)-L( _F^*) =x∼ρ¯,y∼πF∗(⋅|x)[logπF∗(y|x)π(y|x)] =E_x ρ,y _F^*(·|x) [ _F^*(y|x)π(y|x) ] =x∼ρ¯KL[πF∗(⋅|x)∥π(⋅|x)]. =E_x ρKL [ _F^*(·|x)\|π(·|x) ]. (B.10) Applying (B.9) and (B.10) to π^t π_t and πF∗ _F^* and the tower property, we have [Regret(T)] [Regret(T) ] =[∑t=1T[L(π^t)−L(πF∗)]] =E [ _t=1^T [L( π_t)-L( _F^*) ] ] =[∑t=1T[ℓt(π^t)−ℓt(πF∗)]]. =E [ _t=1^T [ _t( π_t)- _t( _F^*) ] ]. (B.11) Fix h∈[H]h∈[H], define ℓt,h(π):=−∑x∈∑u∈h−1∑a∈ct(x,u,a)logπ(a|x,u). _t,h(π):=- _x _u ^h-1 _a c_t(x,u,a) π(a|x,u). Then, ℓt(π)=∑hℓt,h(π) _t(π)= _h _t,h(π). We consider ∑t=1T[ℓt,h(π^t)−ℓt,h(πF∗)] _t=1^T [ _t,h( π_t)- _t,h( _F^*) ]. Recall that Wt(x,u,a)=∑i=1tci(x,u,a)W_t(x,u,a)= _i=1^tc_i(x,u,a), Wt(x,u)=∑aWt(x,u,a)W_t(x,u)= _aW_t(x,u,a). For a fixed state (x,u)(x,u), we omit (x,u)(x,u) and use the shorthand notation Wt(a)W_t(a) and WtW_t when it will not cause any confusion. Similarly, we write ct(a)=ct(x,u,a)c_t(a)=c_t(x,u,a) and define ct:=∑act(a)c_t:= _ac_t(a). Thus, Wt=∑i=1tciW_t= _i=1^tc_i. Using the definition of ct(x,u,a)c_t(x,u,a) in (4.3), we have ct=1m∑j=1m(xt,j=x,yt,j,<h=u)∑aqt,j,h(a). c_t= 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u)\, _aq_t,j,h(a). Note that in both cases, ∑aqt,j,h(a)=1 _aq_t,j,h(a)=1. Thus, we have ct c_t =1m∑j=1m(xt,j=x,yt,j,<h=u)≤1. = 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u)≤ 1. In Algorithm 1, the policy at context (x,u)(x,u) is defined as π^t(a|x,u)=Wt−1(a)+1/2Wt−1+A/2. π_t(a|x,u)= W_t-1(a)+1/2W_t-1+A/2. For simplicity, we write the action set as =1,2,…,AA=\1,2,…,A\. Let tQ_t be a random A-dim probability vector with Dirichlet distribution t∼Dir(Wt−1(1)+12,…,Wt−1(A)+12). _t (W_t-1(1)+ 12,…,W_t-1(A)+ 12 ). The goal of this construction is the following fact: the mean of tQ_t is exactly the output policy: q∼t[q(a)]=Wt−1(a)+1/2Wt−1+A/2=π^t(a|x,u). _q _t[q(a)]= W_t-1(a)+1/2W_t-1+A/2= π_t(a|x,u). For a positive vector v=(v1,…,vA)v=(v_1,…,v_A), define the multivariate beta function by B(v):=∏a=1AΓ(va)Γ(∑a=1Ava), (v):= _a=1^A (v_a) ( _a=1^Av_a), (B.12) where Γ is the gamma function. The beta function is the normalizing constant of the Dirichlet distribution. Indeed, for every positive vector v, the density of the Dirichlet distribution vQ_v on the simplex ΔA:=q∈ℝ+A:∑aq(a)=1 _A:=\q _+^A: _aq(a)=1\ is fv(q)=1B(v)∏a=1Aq(a)va−1,q∈ΔA. f_v(q)= 1B(v) _a=1^Aq(a)^v_a-1, q∈ _A. Equivalently, ∫ΔA∏a=1Aq(a)va−1q=B(v). _ _A _a=1^Aq(a)^v_a-1\,dq=B(v). More generally, for every nonnegative vector c∈ℝ+Ac _+^A, q∼v[∏a=1Aq(a)ca] _q _v [ _a=1^Aq(a)^c_a ] =1B(v)∫ΔA∏a=1Aq(a)ca+va−1q = 1B(v) _ _A _a=1^Aq(a)^c_a+v_a-1dq =B(v+c)B(v). = B(v+c)B(v). Therefore, we have q∼t[∏a∈q(a)ct(a)] _q _t [ _a q(a)^c_t(a) ] =B(Wt−1(1)+ct(1)+12,…,Wt−1(A)+ct(A)+12)B(Wt−1(1)+12,…,Wt−1(A)+12) = B (W_t-1(1)+c_t(1)+ 12,…,W_t-1(A)+c_t(A)+ 12 )B (W_t-1(1)+ 12,…,W_t-1(A)+ 12 ) =B(Wt(1)+12,…,Wt(A)+12)B(Wt−1(1)+12,…,Wt−1(A)+12), = B (W_t(1)+ 12,…,W_t(A)+ 12 )B (W_t-1(1)+ 12,…,W_t-1(A)+ 12 ), (B.13) where we use Wt(a)=Wt−1(a)+ct(a)W_t(a)=W_t-1(a)+c_t(a). Let αt:=∑a∈ct(a)≤1,t+:=a∈:ct(a)>0. _t:= _a c_t(a)≤ 1, _t^+:=\a :c_t(a)>0\. For every a∈t+a _t^+, define the Hölder exponent ra:=1/ct(a)r_a:=1/c_t(a). If αt<1 _t<1, introduce one additional exponent r0:=1/(1−αt)r_0:=1/(1- _t). These exponents satisfy 1r0+∑a∈t+1ra=(1−αt)+∑a∈t+ct(a)=1. 1r_0+ _a _t^+ 1r_a=(1- _t)+ _a _t^+c_t(a)=1. Using the generalized Hölder’s inequality, we have q∼t[∏a∈q(a)ct(a)] _q _t [ _a q(a)^c_t(a) ] ≤[1r0]1r0∏a∈t+q∼t[[q(a)ct(a)]ra]1ra [1^r_0] 1r_0 _a _t^+E_q _t [ [q(a)^c_t(a) ]^r_a ] 1r_a =∏a∈t+q∼t[q(a)]ct(a)=∏a∈π^t(a|x,u)ct(a), = _a _t^+E_q _t [q(a) ]^c_t(a)= _a π_t(a|x,u)^c_t(a), (B.14) where we used q∼t[q(a)]=π^t(a|x,u)E_q _t[q(a)]= π_t(a|x,u). If αt=1 _t=1, we can skip r0r_0 and use the same generalized Hölder’s inequality. Combining (B.13) and (B.14), multiplying over t, and using the telescoping argument, we have ∏t=1T∏a∈π^t(a|x,u)ct(a) _t=1^T _a π_t(a|x,u)^c_t(a) ≥∏t=1TB(Wt(⋅)+12)B(Wt−1(⋅)+12) ≥ _t=1^T B (W_t(·)+ 121 )B (W_t-1(·)+ 121 ) =B(WT(⋅)+12)B(12). = B (W_T(·)+ 121 )B ( 121 ). Taking the negative logarithm, we have −∑t=1T∑a∈ct(a)logπ^t(a|x,u)≤logB(12)B(WT(⋅)+12). - _t=1^T _a c_t(a) π_t(a|x,u)≤ B( 121)B (W_T(·)+ 121 ). (B.15) Next, we consider an arbitrary policy π(⋅|x,u)π(·|x,u). First suppose WT>0W_T>0. By the nonnegativity of KL divergence, ∑a∈WT(a)logπ(a|x,u) _a W_T(a) π(a|x,u) =∑a∈WT(a)logWT(a)WT−WT∑a∈WT(a)WTlogWT(a)WT⋅π(a|x,u) = _a W_T(a) W_T(a)W_T-W_T _a W_T(a)W_T W_T(a)W_T·π(a|x,u) =∑a∈WT(a)logWT(a)WT−WTKL(WT(⋅)WT∥π(⋅|x,u)) = _a W_T(a) W_T(a)W_T-W_TKL ( W_T(·)W_T \|π(·|x,u) ) ≤∑a∈WT(a)logWT(a)WT, ≤ _a W_T(a) W_T(a)W_T, (B.16) where we set 0log0:=00 0:=0. Summing (B.15) and (B.16), we have ∑t=1T∑a∈ct(a)logπ(a|z)π^t(a|z) _t=1^T _a c_t(a) π(a|z) π_t(a|z) ≤logB(12)B(WT(⋅)+12)+∑a∈WT(a)logWT(a)WT=:ℛ(WT(⋅)). ≤ B( 121)B(W_T(·)+ 121)+ _a W_T(a) W_T(a)W_T=:R (W_T(·) ). When WT=0W_T=0, let ℛ(WT(⋅))=0R (W_T(·) )=0. The following lemma bounds ℛ(WT(⋅))R (W_T(·) ) using Stirling’s formula. Lemma B.1. Let WT(a)≥0W_T(a)≥ 0 for every a∈a , and let WT:=∑a∈WT(a). W_T:= _a W_T(a). Then, ℛ(WT(⋅))R (W_T(·) ) satisfies ℛ(WT(⋅))≤Alog(WT+1)+3A. (W_T(·) )≤ A (W_T+1)+3A. We defer the proof of Lemma B.1 to Appendix D. Choose π=πF∗π= _F^*. For any (x,u)∈×h−1(x,u) ×A^h-1, we have ∑t=1T∑a∈ct(x,u,a)logπF∗(a|x,u)π^t(a|x,u)≤Alog(WT(x,u)+1)+3A. _t=1^T _a c_t(x,u,a) _F^*(a|x,u) π_t(a|x,u)≤ A (W_T(x,u)+1 )+3A. Therefore, we have ∑t=1T[ℓt,h(π^t)−ℓt,h(πF∗)] _t=1^T [ _t,h( π_t)- _t,h( _F^*) ] =∑x∈∑u∈h−1∑t=1T∑a∈ct(x,u,a)logπF∗(a|x,u)π^t(a|x,u) = _x _u ^h-1 _t=1^T _a c_t(x,u,a) _F^*(a|x,u) π_t(a|x,u) ≤∑(x,u)∈×h−1[Alog(WT(x,u)+1)+3A]. ≤ _(x,u) ×A^h-1 [A (W_T(x,u)+1 )+3A ]. For every fixed level h and round t, it is easy to check that ∑(x,u)∈×h−1∑a∈ct(x,u,a)=1. _(x,u) ×A^h-1 _a c_t(x,u,a)=1. Consequently, ∑(x,u)∈×h−1WT(x,u)=T, _(x,u) ×A^h-1W_T(x,u)=T, and hence WT(x,u)≤TW_T(x,u)≤ T for any (x,u)(x,u). This leads to ∑t=1T[ℓt,h(π^t)−ℓt,h(πF∗)] _t=1^T [ _t,h( π_t)- _t,h( _F^*) ] ≤2SAhlogT. ≤ 2SA^h T. (B.17) Finally, summing (B.17) over h∈[H]h∈[H], we have ∑t=1T[ℓt(π^t)−ℓt(πF∗)] _t=1^T [ _t( π_t)- _t( _F^*) ] ≤2SlogT∑h=1HAh ≤ 2S T _h=1^HA^h =2S⋅logTA(AH−1)A−1 =2S· T A(A^H-1)A-1 ≤4SAHlogT. ≤ 4SA^H T. (B.18) Using (B.11), we obtain [Regret(T)] [Regret(T) ] ≤4SAHlogT. ≤ 4SA^H T. We next consider the high-probability regret bound. Define Xt X_t :=ℓt(πF∗)−ℓt(π^t), := _t( _F^*)- _t( π_t), rt r_t :=−[Xt∣ℱt]=x∼ρ¯KL(πF∗(⋅|x)∥π^t(⋅|x)). :=-E[X_t _t]=E_x ρKL ( _F^*(·|x)\| π_t(·|x) ). Thus, Regret(T)=∑t=1TrtRegret(T)= _t=1^Tr_t. Define M0=0M_0=0, and Mt:=∑s=1t(Xs+rs),t∈[T]. M_t:= _s=1^t(X_s+r_s), t∈[T]. Since rt=−[Xt∣ℱt]r_t=-E[X_t _t], we have [Mt−Mt−1|ℱt]=0E[M_t-M_t-1|F_t]=0. Thus, Mtt=0T\M_t\_t=0^T is a martingale with respect to ℱt+1t=0T\F_t+1\_t=0^T. Our goal is to control MTM_T. Using the definition of ℓt _t, Xt X_t =∑h=1H∑(x,u,a)ct(x,u,a)logπ^t(a|x,u)πF∗(a|x,u). = _h=1^H _(x,u,a)c_t(x,u,a) π_t(a|x,u) _F^*(a|x,u). First note that in Algorithm 1, π^t(a|x,u) π_t(a|x,u) =Wt−1(x,u,a)+1/2Wt−1(x,u)+A/2 = W_t-1(x,u,a)+1/2W_t-1(x,u)+A/2 ≥12(t−1)+A≥12T+A. ≥ 12(t-1)+A≥ 12T+A. Since πF∗(a|x,u)≤1 _F^*(a|x,u)≤ 1, it follows that XtH≥−LT,LT:=log(2T+A). X_tH≥-L_T, L_T:= (2T+A). (B.19) Here we use the following equation ∑(x,u,a)ct(x,u,a)=1. _(x,u,a)c_t(x,u,a)=1. Moreover, we can see ∑h=1H∑(x,u,a)ct(x,u,a)H=1. _h=1^H _(x,u,a) c_t(x,u,a)H=1. Using the AM-GM inequality, we have exp(XtH) ( X_tH ) =∏h=1H∏(x,u,a)(π^t(a|x,u)πF∗(a|x,u))ct(x,u,a)/H = _h=1^H _(x,u,a) ( π_t(a|x,u) _F^*(a|x,u) )^c_t(x,u,a)/H ≤1H∑h=1H∑(x,u,a)ct(x,u,a)π^t(a|x,u)πF∗(a|x,u). ≤ 1H _h=1^H _(x,u,a)c_t(x,u,a) π_t(a|x,u) _F^*(a|x,u). Taking conditional expectation over ℱtF_t and using [ct(x,u,a)∣ℱt]=ρ¯(x)πF∗(u|x)πF∗(a|x,u), [c_t(x,u,a) _t]= ρ(x) _F^*(u|x) _F^*(a|x,u), we obtain [exp(XtH)|ℱt] [ ( X_tH ) |F_t ] ≤1H∑h=1H∑(x,u,a)ρ¯(x)πF∗(u|x)πF∗(a|x,u)π^t(a|x,u)πF∗(a|x,u) ≤ 1H _h=1^H _(x,u,a) ρ(x) _F^*(u|x) _F^*(a|x,u) π_t(a|x,u) _F^*(a|x,u) =1H∑h=1H∑(x,u)ρ¯(x)πF∗(u|x)∑aπ^t(a|x,u) = 1H _h=1^H _(x,u) ρ(x) _F^*(u|x) _a π_t(a|x,u) ≤1H∑h=1H∑x∈ρ¯(x)∑u∈h−1πF∗(u|x) ≤ 1H _h=1^H _x ρ(x) _u ^h-1 _F^*(u|x) =1. =1. (B.20) The following lemma shows that a one-sided lower bound and an exponential central condition provide exponential control of deviations from the conditional mean. Lemma B.2. Let ℱF be a σ-algebra, and let Y be a random variable satisfying, almost surely, Y≥−L,[eY∣ℱ]≤1, Y≥-L, [e^Y ]≤ 1, for some L≥0L≥ 0. Define μ:=−[Y∣ℱ]μ:=-E[Y ]. Then μ∈[0,L]μ∈[0,L], and, for every θ∈[0,1]θ∈[0,1], log[eθ(Y+μ)|ℱ]≤(1+L)θ2μ. [e^θ(Y+μ) |F ]≤(1+L)θ^2μ. Applying Lemma B.2 to Y=Xt/HY=X_t/H, L=LTL=L_T, we have for every λ∈[0,1/H]λ∈[0,1/H] log[eλ(Xt+rt)|ℱt]≤H(1+LT)λ2rt. [e^λ(X_t+r_t)\, |\,F_t ]≤ H(1+L_T)λ^2r_t. (B.21) Define ℰt(λ):=exp(λ∑s=1t(Xs+rs)−H(1+LT)λ2∑s=1trs). _t(λ):= (λ _s=1^t(X_s+r_s)-H(1+L_T)λ^2 _s=1^tr_s ). Then, (B.21) implies that ℰs(λ)s=0T\E_s(λ)\_s=0^T is a nonnegative supermartingale with ℰ0(λ)=1E_0(λ)=1. As a result, [ℰT(λ)]≤[ℰ0(λ)]=1E[E_T(λ)] [E_0(λ)]=1. Moreover, we have ℰT(λ)=exp(λMT−H(1+LT)λ2Regret(T)). _T(λ)= (λ M_T-H(1+L_T)λ^2Regret(T) ). Therefore, for any C>0C>0, by Markov’s inequality, we have ℙ[λMT−H(1+LT)λ2Regret(T)≥C]≤[ℰT(λ)]eC≤1eC. [λ M_T-H(1+L_T)λ^2Regret(T)≥ C ]≤ E[E_T(λ)]e^C≤ 1e^C. Set C=log(1/δ)C= (1/δ). Now we obtain with probability at least 1−δ1-δ, MT=∑t=1T(Xt+rt)≤H(1+LT)λRegret(T)+log(1/δ)λ. M_T= _t=1^T(X_t+r_t)≤ H(1+L_T) (T)+ (1/δ)λ. (B.22) On the other hand, (B.18) gives −∑t=1TXt=∑t=1T[ℓt(π^t)−ℓt(πF∗)]≤4SAHlogT. - _t=1^TX_t= _t=1^T [ _t( π_t)- _t( _F^*) ]≤ 4SA^H T. Moreover, we have Regret(T)=−∑t=1TXt+∑t=1T(Xt+rt). (T)=- _t=1^TX_t+ _t=1^T(X_t+r_t). Therefore, with probability at least 1−δ1-δ, the following inequality holds: Regret(T)≤4SAHlogT+H(1+LT)λRegret(T)+log(1/δ)λ. (T)≤ 4SA^H T+H(1+L_T) (T)+ (1/δ)λ. (B.23) Choose λ=12H(1+log(2T+A))≤1H. λ= 12H(1+ (2T+A))≤ 1H. We have H(1+LT)λ=1/2H(1+L_T)λ=1/2. Rearranging (B.23) yields Regret(T)≤8SAHlogT+4H(1+log(2T+A))log1δ. (T)≤ 8SA^H T+4H (1+ (2T+A) ) 1δ. ∎ Appendix C Proof of Theorem 5.5 Proof of Theorem 5.5. We first control the error of the optimistic token-score estimates. Let ℱtF_t denote the history before round t. In this way, both l^t−1 l_t-1 and π^t π_t are ℱtF_t-measurable. Let ℰE be the event in Lemma 5.4, which satisfies ℙ(ℰ)≥1−2δP(E)≥ 1-2δ. On this event, simultaneously for every round s and every visited triple (x,u,a)(x,u,a), |l¯s(x,u,a)−loggh(a|x,u)|≤βs(x,u,a). | l_s(x,u,a)- g_h(a|x,u) |≤ _s(x,u,a). (C.1) Moreover, Assumption 5.3 and the definition of ghg_h imply that for every teacher i, |logpi(a|x,u)−loggh(a|x,u)| | p_i(a|x,u)- g_h(a|x,u) | =|logpi(a|x,u)πref(a|x,u)−∑k∈ℐwk(x)logpk(a|x,u)πref(a|x,u)|≤2B. = | p_i(a|x,u) _ref(a|x,u)- _k w_k(x) p_k(a|x,u) _ref(a|x,u) |≤ 2B. Since l¯s(x,u,a) l_s(x,u,a) is an average of the observed teacher log-probabilities at this triple, it follows that |l¯s(x,u,a)−loggh(a|x,u)|≤2B. | l_s(x,u,a)- g_h(a|x,u) |≤ 2B. (C.2) Combining (C.1) and (C.2), we obtain |l¯s(x,u,a)−loggh(a|x,u)|≤minβs(x,u,a),2B. | l_s(x,u,a)- g_h(a|x,u) |≤ \ _s(x,u,a),2B \. Consequently, on the event ℰE, the optimistic estimate l^s=l¯s+minβs,2B l_s= l_s+ \ _s,2B\ satisfies 0≤l^s(x,u,a)−loggh(a|x,u)≤min2βs(x,u,a),4B. 0≤ l_s(x,u,a)- g_h(a|x,u)≤ \2 _s(x,u,a),4B \. For an unvisited triple, the algorithm sets l^s(x,u,a)=logπref(a|x,u)+B. l_s(x,u,a)= _ref(a|x,u)+B. Assumption 5.3 implies −B≤loggh(a|x,u)−logπref(a|x,u)≤B. -B≤ g_h(a|x,u)- _ref(a|x,u)≤ B. Therefore, 0≤l^s(x,u,a)−loggh(a|x,u)≤2B. 0≤ l_s(x,u,a)- g_h(a|x,u)≤ 2B. We next consider the output policy. Multiplying the token conditionals defined by the backward recursion gives π^t(y|x) π_t(y|x) =∏h=1Hexp(l^t−1(x,y<h,ah))V^t−1,h+1(x,y≤h)V^t−1,h(x,y<h) = _h=1^H ( l_t-1(x,y_<h,a_h) ) V_t-1,h+1(x,y_≤ h) V_t-1,h(x,y_<h) =exp(∑h=1Hl^t−1(x,y<h,ah))V^t−1,1(x), = ( _h=1^H l_t-1(x,y_<h,a_h) ) V_t-1,1(x), (C.3) where the second equation holds by canceling out the telescoping terms and V^t−1,H+1=1 V_t-1,H+1=1. Comparing this expression with the reverse target in (5.1), we obtain logπ^t(y|x)πR∗(y|x) π_t(y|x) _R^*(y|x) =∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]+logV1(x)V^t−1,1(x). = _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ]+ V_1(x) V_t-1,1(x). (C.4) Moreover, the ratio of the normalizing constants can be expressed as an expectation under π^t π_t. To see this, first expand the expectation: y∼π^t(⋅|x)exp(−∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]) _y π_t(·|x) (- _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ] ) =∑y∈π^t(y|x)exp(−∑h=1Hl^t−1(x,y<h,ah)+∑h=1Hloggh(ah|x,y<h)). = _y π_t(y|x) (- _h=1^H l_t-1(x,y_<h,a_h)+ _h=1^H g_h(a_h|x,y_<h) ). (C.5) Substituting (C.3) into (C.5), the right-hand side becomes ∑y∈exp(∑h=1Hl^t−1(x,y<h,ah))V^t−1,1(x)exp(−∑h=1Hl^t−1(x,y<h,ah)+∑h=1Hloggh(ah|x,y<h)) _y ( _h=1^H l_t-1(x,y_<h,a_h) ) V_t-1,1(x) (- _h=1^H l_t-1(x,y_<h,a_h)+ _h=1^H g_h(a_h|x,y_<h) ) =1V^t−1,1(x)∑y∈exp(∑h=1Hloggh(ah|x,y<h)) = 1 V_t-1,1(x) _y ( _h=1^H g_h(a_h|x,y_<h) ) =1V^t−1,1(x)∑y∈∏h=1Hgh(ah|x,y<h). = 1 V_t-1,1(x) _y _h=1^Hg_h(a_h|x,y_<h). Finally, recall that in Theorem 5.1, we have seen V1(x)=∑y∈∏h=1Hgh(ah|x,y<h). V_1(x)= _y _h=1^Hg_h(a_h|x,y_<h). Consequently, y∼π^t(⋅|x)exp(−∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)])=V1(x)V^t−1,1(x). _y π_t(·|x) (- _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ] )= V_1(x) V_t-1,1(x). (C.6) Taking expectation over π^t(⋅|x) π_t(·|x) and substituting (C.6) into (C.4) yields KL(π^t(⋅|x)∥πR∗(⋅|x))=y∼π^t(⋅|x)[∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]] ( π_t(·|x)\, \|\, _R^*(·|x) )=E_y π_t(·|x) [ _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ] ] +logy∼π^t(⋅|x)exp(−∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]). + _y π_t(·|x) (- _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ] ). (C.7) On the event ℰE, l^t−1(x,y<h,ah)≥loggh(ah|x,y<h) l_t-1(x,y_<h,a_h)≥ g_h(a_h|x,y_<h) for any t,ht,h. We can therefore apply the basic inequality e−v≤1−v+v2/2e^-v≤ 1-v+v^2/2 for v≥0v≥ 0. Let V=∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]V= _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ]. The right-hand side can be bounded as [V]+logexp(−V) [V]+ (-V) ≤[V]+log(1−[V]+[V2]/2) [V]+ (1-E[V]+E[V^2]/2 ) ≤[V]−[V]+12[V2] [V]-E[V]+ 12E[V^2] =12[V2], = 12E[V^2], where we use logx≤x−1 x≤ x-1 for any x>0x>0. As a result, we have KL(π^t(⋅|x)∥πR∗(⋅|x)) ( π_t(·|x)\, \|\, _R^*(·|x) ) ≤12y∼π^t(⋅|x)[(∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)])2] ≤ 12E_y π_t(·|x) [ ( _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ] )^2 ] ≤H2y∼π^t(⋅|x)[∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]2], ≤ H2E_y π_t(·|x) [ _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ]^2 ], (C.8) where the last inequality holds due to the Cauchy–Schwarz inequality. We next relate the expected squared errors in (C.8) to those evaluated on the observed rollouts. Define Xt:=H2m∑j=1m∑h=1H[l^t−1(xt,j,yt,j,<h,at,j,h)−loggh(at,j,h|xt,j,yt,j,<h)]2. X_t:= H2m _j=1^m _h=1^H [ l_t-1(x_t,j,y_t,j,<h,a_t,j,h)- g_h(a_t,j,h|x_t,j,y_t,j,<h) ]^2. Conditionally on ℱtF_t, each rollout has joint distribution ℙ(xt,j=x,yt,j=y∣ℱt) (x_t,j=x,y_t,j=y _t) =1I∑i∈ℐρi(x)π^t(y|x) = 1I _i _i(x) π_t(y|x) =ρ¯(x)π^t(y|x). = ρ(x) π_t(y|x). Since l^t−1 l_t-1 and π^t π_t are ℱtF_t-measurable, linearity of conditional expectation therefore gives [Xt∣ℱt] [X_t _t] =H2m∑j=1mx∼ρ¯y∼π^t(⋅|x)[∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]2] = H2m _j=1^mE_x ρE_y π_t(·|x) [ _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ]^2 ] =H2x∼ρ¯y∼π^t(⋅|x)[∑h=1H[l^t−1(x,y<h,ah)−loggh(ah|x,y<h)]2]. = H2E_x ρE_y π_t(·|x) [ _h=1^H [ l_t-1(x,y_<h,a_h)- g_h(a_h|x,y_<h) ]^2 ]. (C.9) Note that this does not require independence among the rollouts within a round. On the event ℰE, combining (C.9) with (C.8), we have Regret(T) (T) =∑t=1Tx∼ρ¯KL(π^t(⋅|x)∥πR∗(⋅|x))≤∑t=1T[Xt∣ℱt]. = _t=1^TE_x ρKL ( π_t(·|x)\, \|\, _R^*(·|x) )≤ _t=1^TE[X_t _t]. (C.10) To apply Lemma I.6, we need a bound on XtX_t. At every previously visited triple, (C.2) and the definition of l^t−1 l_t-1 give |l^t−1(x,u,a)−loggh(a|x,u)| | l_t-1(x,u,a)- g_h(a|x,u) | ≤|l¯t−1(x,u,a)−loggh(a|x,u)|+minβt−1(x,u,a),2B ≤ | l_t-1(x,u,a)- g_h(a|x,u) |+ \ _t-1(x,u,a),2B\ ≤4B. ≤ 4B. At an unvisited triple, l^t−1(x,u,a)=logπref(a|x,u)+B l_t-1(x,u,a)= _ref(a|x,u)+B indicates |l^t−1(x,u,a)−loggh(a|x,u)|∈[0,2B] | l_t-1(x,u,a)- g_h(a|x,u) |∈[0,2B]. Consequently, in both cases, 0≤Xt≤H2m⋅mH⋅(4B)2=8H2B2. 0≤ X_t≤ H2m· mH·(4B)^2=8H^2B^2. Moreover, XtX_t is ℱt+1F_t+1-measurable. Applying Lemma I.6, with probability at least 1−δ1-δ, the following inequality holds ∑t=1T[Xt∣ℱt]≤2∑t=1TXt+64H2B2log2δ. _t=1^TE[X_t _t]≤ 2 _t=1^TX_t+64H^2B^2 2δ. (C.11) Substituting (C.11) into (C.10) and taking a union bound, we conclude that, with probability at least 1−3δ1-3δ, Regret(T) (T) ≤Hm∑t=1T∑j=1m∑h=1H[l^t−1(xt,j,yt,j,<h,at,j,h)−loggh(at,j,h|xt,j,yt,j,<h)]2⏟I ≤ Hm _t=1^T _j=1^m _h=1^H [ l_t-1(x_t,j,y_t,j,<h,a_t,j,h)- g_h(a_t,j,h|x_t,j,y_t,j,<h) ]^2_I +64H2B2log2δ. +64H^2B^2 2δ. (C.12) It remains to bound I for every data trajectory on ℰE. Regrouping the observations by their corresponding triples gives I=∑h=1H∑(x,u,a)∑t=1T[Nt(x,u,a)−Nt−1(x,u,a)][l^t−1(x,u,a)−loggh(a|x,u)]2. I= _h=1^H _(x,u,a) _t=1^T [N_t(x,u,a)-N_t-1(x,u,a) ] [ l_t-1(x,u,a)- g_h(a|x,u) ]^2. Here Nt(x,u,a)−Nt−1(x,u,a)N_t(x,u,a)-N_t-1(x,u,a) counts the visits to this triple in round t, each of which contributes the same squared error. Since there are m samples per round, 0≤Nt(x,u,a)−Nt−1(x,u,a)≤m,NT(x,u,a)≤mT. 0≤ N_t(x,u,a)-N_t-1(x,u,a)≤ m, N_T(x,u,a)≤ mT. For each fixed triple (x,u,a)(x,u,a), we split the inner sum according to whether Nt−1(x,u,a)=0N_t-1(x,u,a)=0 or Nt−1(x,u,a)≥1N_t-1(x,u,a)≥ 1. In the former case, only the first round that visits this triple can contribute, with at most m visits. Hence, ∑t∈[T]:Nt−1(x,u,a)=0[Nt(x,u,a)−Nt−1(x,u,a)][l^t−1(x,u,a)−loggh(a|x,u)]2≤4mB2. _ subarrayct∈[T]:\\ N_t-1(x,u,a)=0 subarray [N_t(x,u,a)-N_t-1(x,u,a) ] [ l_t-1(x,u,a)- g_h(a|x,u) ]^2≤ 4mB^2. Summing this bound over all K:=S∑h=1HAhK:=S _h=1^HA^h triples and applying Lemma 5.4 gives I≤4mB2K I≤ 4mB^2K +∑h=1H∑(x,u,a)∑t∈[T]:Nt−1(x,u,a)≥1[Nt(x,u,a)−Nt−1(x,u,a)]⋅min16B2, 4βt−1(x,u,a)2. + _h=1^H _(x,u,a) _ subarrayct∈[T]:\\ N_t-1(x,u,a)≥ 1 subarray [N_t(x,u,a)-N_t-1(x,u,a) ]· \16B^2,\,4 _t-1(x,u,a)^2 \. (C.13) Recall that βt(x,u,a)=O~(BmHNt(x,u,a)+BmHNt(x,u,a)). _t(x,u,a)= O (B mHN_t(x,u,a)+ BmHN_t(x,u,a) ). For Nt−1(x,u,a)≥1N_t-1(x,u,a)≥ 1, squaring the confidence radius gives 4βt−1(x,u,a)2≤O~(B2mHNt−1(x,u,a)+B2m2H2Nt−1(x,u,a)2), 4 _t-1(x,u,a)^2≤ O ( B^2mHN_t-1(x,u,a)+ B^2m^2H^2N_t-1(x,u,a)^2 ), where we used (v+w)2≤2v2+2w2(v+w)^2≤ 2v^2+2w^2. Combining this with the constant bound 16B216B^2, we obtain min16B2, 4βt−1(x,u,a)2 \16B^2,\,4 _t-1(x,u,a)^2 \ ≤O~(B2min1,mHNt−1(x,u,a)+m2H2Nt−1(x,u,a)2) ≤ O (B^2 \1,\, mHN_t-1(x,u,a)+ m^2H^2N_t-1(x,u,a)^2 \ ) ≤O~(B2min1,mHNt−1(x,u,a)), ≤ O (B^2 \1, mHN_t-1(x,u,a) \ ), where we use min1,v+v2≤2min1,v \1,v+v^2\≤ 2 \1,v\ since v2≤v^2≤ v when 0≤v≤10≤ v≤ 1. Fix a triple (x,u,a)(x,u,a) with NT(x,u,a)≥1N_T(x,u,a)≥ 1. Order its visits chronologically, breaking ties within each round arbitrarily. If its k-th visit occurs in round t, then k≤Nt−1(x,u,a)+m≤Nt−1(x,u,a)+mH, k≤ N_t-1(x,u,a)+m≤ N_t-1(x,u,a)+mH, because at most m visits occur in that round and H≥1H≥ 1. For each visit included in the remaining sum, Nt−1(x,u,a)≥1N_t-1(x,u,a)≥ 1, and hence min1,mHNt−1(x,u,a) \1, mHN_t-1(x,u,a) \ ≤2mHNt−1(x,u,a)+mH ≤ 2mHN_t-1(x,u,a)+mH ≤2mHk. ≤ 2mHk. The first inequality uses min1,v≤2v/(1+v) \1,v\≤ 2v/(1+v) for v≥0v≥ 0. Since Nt(x,u,a)−Nt−1(x,u,a)N_t(x,u,a)-N_t-1(x,u,a) counts the visits in round t, the following summation counts all the visits to (x,u,a)(x,u,a) and thus can be indexed by k, leading to ∑t∈[T]:Nt−1(x,u,a)≥1[Nt(x,u,a)−Nt−1(x,u,a)]min1,mHNt−1(x,u,a) _ subarrayct∈[T]:\\ N_t-1(x,u,a)≥ 1 subarray [N_t(x,u,a)-N_t-1(x,u,a) ] \1, mHN_t-1(x,u,a) \ ≤2mH∑k=1NT(x,u,a)1k ≤ 2mH _k=1^N_T(x,u,a) 1k ≤2mH[1+logNT(x,u,a)] ≤ 2mH [1+ N_T(x,u,a) ] ≤2mHlog(emT), ≤ 2mH (emT), (C.14) where we use ∑k=1T1/k≤1+logT _k=1^T1/k≤ 1+ T and NT(x,u,a)≤mTN_T(x,u,a)≤ mT. Substituting (C.14) into (C.13) and summing over all (x,u,a)(x,u,a) triples, we have I I ≤4mB2K+O~(B2mHKlog(emT))=O~(B2mHKlogT)=O~(B2mSHAHlogT). ≤ 4mB^2K+ O (B^2mHK (emT) )= O (B^2mHK T )= O (B^2mSHA^H T ). In conclusion, (C.12) gives that with probability at least 1−3δ1-3δ, the following inequality holds: Regret(T) (T) ≤HmI+O~(B2H2) ≤ HmI+ O(B^2H^2) ≤O~(B2H2SAHlogT). ≤ O (B^2H^2SA^H T ). This completes the proof of Theorem 5.5. ∎ Appendix D Proof of Lemmas Used in Appendices B and C D.1 Proof of Lemma B.1 Proof of Lemma B.1. When WT=0W_T=0, the inequality holds naturally. We therefore assume throughout the rest of the proof that WT>0W_T>0. If A=1A=1, then B(v)=Γ(v)Γ(v)=1B(v)= (v) (v)=1 for every v>0v>0, and WT(1)logWT(1)WT=0. W_T(1) W_T(1)W_T=0. Thus, ℛ(WT(⋅))=0R(W_T(·))=0. It remains to consider A≥2A≥ 2. By the definition of the beta function (B.12), we have −logB(WT(⋅)+12) - (W_T(·)+ 121 ) =logΓ(WT+A2)−∑a∈logΓ(WT(a)+12). = (W_T+ A2 )- _a (W_T(a)+ 12 ). (D.1) Using Lemma I.8 with s=WT+A/2s=W_T+A/2, we have logΓ(WT+A2) (W_T+ A2 ) ≤(WT+A−12)log(WT+A2)−(WT+A2) ≤ (W_T+ A-12 ) (W_T+ A2 )- (W_T+ A2 ) +12log(2π)+112(WT+A/2). + 12 (2π)+ 112(W_T+A/2). (D.2) For every a∈a , applying Lemma I.8 with s=WT(a)+1/2s=W_T(a)+1/2, we have logΓ(WT(a)+12) (W_T(a)+ 12 ) ≥WT(a)log(WT(a)+12)−(WT(a)+12)+12log(2π). ≥ W_T(a) (W_T(a)+ 12 )- (W_T(a)+ 12 )+ 12 (2π). (D.3) Substituting (D.2) and (D.3) into (D.1), we obtain −logB(WT(⋅)+12)≤−∑a∈WT(a)log(WT(a)+12) - (W_T(·)+ 121 )≤- _a W_T(a) (W_T(a)+ 12 ) +(WT+A−12)log(WT+A2)−A−12log(2π)+112(WT+A/2), + (W_T+ A-12 ) (W_T+ A2 )- A-12 (2π)+ 112(W_T+A/2), where we use ∑a∈WT(a)=WT _a W_T(a)=W_T. Recall that ℛ(WT(⋅)) (W_T(·) ) =logB(12)−logB(WT(⋅)+12)+∑a∈WT(a)logWT(a)WT. = ( 121 )- (W_T(·)+ 121 )+ _a W_T(a) W_T(a)W_T. Therefore, we have ℛ(WT(⋅))≤logB(12)+∑a∈WT(a)logWT(a)WT(a)+1/2⏟I1 (W_T(·) )≤ ( 121 )+ _a W_T(a) W_T(a)W_T(a)+1/2_I_1 +WTlogWT+A/2WT⏟I2+A−12log(WT+A2)⏟I3−A−12log(2π)+112(WT+A/2). + W_T W_T+A/2W_T_I_2+ A-12 (W_T+ A2 )_I_3- A-12 (2π)+ 112(W_T+A/2). (D.4) Since 0≤WT(a)/[WT(a)+1/2]≤10≤W_T(a)/[W_T(a)+1/2]≤ 1, I1≤0I_1≤ 0. For I2I_2, using log(1+s)≤s (1+s)≤ s for every s≥0s≥ 0, we have I2 I_2 =WTlog(1+A2WT)≤A2. =W_T (1+ A2W_T )≤ A2. For I3I_3, we have WT+A2≤(WT+1)(1+A/2)W_T+ A2≤(W_T+1) (1+A/2 ). Thus, WT+A2≤(WT+1)(1+A2), W_T+ A2≤(W_T+1) (1+ A2 ), and hence I3≤(A−1)log(WT+1)/2+(A−1)log(1+A/2)/2I_3≤(A-1) (W_T+1)/2+(A-1) (1+A/2)/2. As a result, (D.4) indicates ℛ(WT(⋅)) (W_T(·) ) ≤A−12log(WT+1)+logB(12)+A2+A−12log(1+A2)+112. ≤ A-12 (W_T+1)+ ( 121 )+ A2+ A-12 (1+ A2 )+ 112. (D.5) Finally, by definition, logB(12)=A2logπ−logΓ(A2). ( 121 )= A2 π- ( A2 ). Applying Lemma I.8 with s=A/2s=A/2, we have logΓ(A2) ( A2 ) ≥A−12logA2−A2+12log(2π). ≥ A-12 A2- A2+ 12 (2π). Since A≥2A≥ 2, we have logB(12)≤A2(logπ+1)−A−12logA2. ( 121 )≤ A2( π+1)- A-12 A2. (D.6) Substituting (D.6) into (D.5), we have ℛ(WT(⋅)) (W_T(·) ) ≤A−12log(WT+1)+A2+A−12log(1+A2)+112 ≤ A-12 (W_T+1)+ A2+ A-12 (1+ A2 )+ 112 +A2(logπ+1)−A−12logA2 + A2( π+1)- A-12 A2 ≤Alog(WT+1)+3A, ≤ A (W_T+1)+3A, where we use log(1+A/2)−log(A/2)≤2/A (1+A/2)- (A/2)≤ 2/A. This completes the proof of Lemma B.1. ∎ D.2 Proof of Lemma B.2 Proof of Lemma B.2. By conditional Jensen’s inequality, exp([Y∣ℱ])≤[eY∣ℱ]≤1. (E[Y ] ) [e^Y ]≤ 1. Therefore, [Y∣ℱ]≤0E[Y ]≤ 0 and hence μ≥0μ≥ 0. Moreover, Y≥−LY≥-L implies [Y∣ℱ]≥−LE[Y ]≥-L, so μ≤Lμ≤ L. We first show that, for every y≥−Ly≥-L and θ∈[0,1]θ∈[0,1], eθy−1−θy≤(1+L)θ2(ey−1−y). e^θ y-1-θ y≤(1+L)θ^2(e^y-1-y). (D.7) First, suppose that y≥0y≥ 0. Expanding the exponential using Taylor’s series gives eθy−1−θy e^θ y-1-θ y =∑k=2∞θkykk! = _k=2^∞ θ^ky^kk! ≤θ2∑k=2∞ykk! ≤θ^2 _k=2^∞ y^kk! =θ2(ey−1−y), =θ^2(e^y-1-y), where we used θk≤θ2θ^k≤θ^2 for every k≥2k≥ 2. It remains to show (D.7) when −L≤y≤0-L≤ y≤ 0. Let y=−sy=-s for some s∈[0,L]s∈[0,L]. Then, on the one hand, the left-hand side of (D.7) satisfies e−θs−1+θs≤θ2s22. e^-θ s-1+θ s≤ θ^2s^22. On the other hand, the right-hand side of (D.7) satisfies: (1+L)θ2(e−s−1+s) (1+L)θ^2(e^-s-1+s) =(1+L)θ2∫0s(1−e−v)v =(1+L)θ^2 _0^s(1-e^-v)\,dv ≥(1+L)θ2∫0sv1+vv ≥(1+L)θ^2 _0^s v1+v\,dv ≥(1+L)θ2∫0sv1+Lv ≥(1+L)θ^2 _0^s v1+L\,dv =θ2s22, = θ^2s^22, where the first inequality holds due to ex≥1+xe^x≥ 1+x, and thus e−x≤1/(1+x)e^-x≤ 1/(1+x) whenever x≥0x≥ 0. The second inequality holds due to v≤s≤Lv≤ s≤ L. Therefore, we have proved (D.7) for y∈[−L,0]y∈[-L,0]. Using (D.7), we obtain [eθY∣ℱ] [e^θ Y ] =1+θ[Y∣ℱ]+[eθY−1−θY∣ℱ] =1+ [Y ]+E[e^θ Y-1-θ Y ] ≤1−θμ+(1+L)θ2[eY−1−Y∣ℱ]. ≤ 1-θμ+(1+L)θ^2E[e^Y-1-Y ]. (D.8) Using [eY∣ℱ]≤1E[e^Y ]≤ 1, we have [eY−1−Y∣ℱ] [e^Y-1-Y ] =[eY∣ℱ]−1−[Y∣ℱ] =E[e^Y ]-1-E[Y ] ≤−[Y∣ℱ] ≤-E[Y ] =μ. =μ. Therefore, (D.8) gives [eθY∣ℱ]≤1−θμ+(1+L)θ2μ. [e^θ Y ]≤ 1-θμ+(1+L)θ^2μ. Consequently, log[eθ(Y+μ)|ℱ] [e^θ(Y+μ)\, |\,F ] =θμ+log[eθY∣ℱ] =θμ+ [e^θ Y ] ≤θμ+log(1−θμ+(1+L)θ2μ) ≤θμ+ (1-θμ+(1+L)θ^2μ ) ≤θμ−θμ+(1+L)θ2μ ≤θμ-θμ+(1+L)θ^2μ =(1+L)θ2μ, =(1+L)θ^2μ, where the last inequality uses log(1+s)≤s (1+s)≤ s. This completes the proof of Lemma B.2. ∎ D.3 Proof of Lemma 5.4 Proof. Fix a level h and a triple z=(x,u,a)z=(x,u,a). Let ℱtF_t denote the history before round t. Define Yt(z):=1m∑j=1m(xt,j=x,yt,j,<h=u,at,j,h=a)[lt,j,h−loggh(a|x,u)]. Y_t(z):= 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a ) [l_t,j,h- g_h(a|x,u) ]. By the definitions of StS_t and NtN_t, we have ∑s=1tYs(z)=St(x,u,a)−Nt(x,u,a)loggh(a|x,u)m. _s=1^tY_s(z)= S_t(x,u,a)-N_t(x,u,a) g_h(a|x,u)m. (D.9) Under the on-policy protocol, conditionally on ℱtF_t, the teacher index is uniform over ℐI, the context follows ρit _i_t, and the response is generated by π^t π_t. Therefore, [Yt(z)∣ℱt] [Y_t(z) _t] =1m∑j=1m1I∑i∈ℐρi(x)π^t(u|x)π^t(a|x,u)[logpi(a|x,u)−loggh(a|x,u)] = 1m _j=1^m 1I _i _i(x) π_t(u|x) π_t(a|x,u) [ p_i(a|x,u)- g_h(a|x,u) ] =ρ¯(x)π^t(u|x)π^t(a|x,u)∑i∈ℐwi(x)[logpi(a|x,u)−loggh(a|x,u)] = ρ(x) π_t(u|x) π_t(a|x,u) _i w_i(x) [ p_i(a|x,u)- g_h(a|x,u) ] =0, =0, where the second equality uses ρi(x)/I=ρ¯(x)wi(x) _i(x)/I= ρ(x)w_i(x). The last equality holds due to ∑iwi(x)=1 _iw_i(x)=1 and loggh(a|x,u)=∑iwi(x)logpi(a|x,u) g_h(a|x,u)= _iw_i(x) p_i(a|x,u). Using Assumption 5.3, for every teacher i, |logpi(a|x,u)−loggh(a|x,u)| | p_i(a|x,u)- g_h(a|x,u) | =|logpi(a|x,u)πref(a|x,u)−∑k∈ℐwk(x)logpk(a|x,u)πref(a|x,u)| = | p_i(a|x,u) _ref(a|x,u)- _k w_k(x) p_k(a|x,u) _ref(a|x,u) | ≤B+∑k∈ℐwk(x)B=2B. ≤ B+ _k w_k(x)B=2B. When (xt,j=x,yt,j,<h=u,at,j,h=a)≠0 (x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a )≠ 0, lt,j,h=logpi(a|x,u)l_t,j,h= p_i(a|x,u) for some i∈ℐi . Thus, |lt,j,h−loggh(a|x,u)|≤2B. |l_t,j,h- g_h(a|x,u) |≤ 2B. In the definition of Yt(z)Y_t(z), at most m summands can be nonzero. Thus, |Yt(z)|≤2Bm/m=2B|Y_t(z)|≤ 2Bm/m=2B. Moreover, Jensen’s inequality gives Yt(z)2 Y_t(z)^2 ≤1m∑j=1m(xt,j=x,yt,j,<h=u,at,j,h=a)[lt,j,h−loggh(a|x,u)]2 ≤ 1m _j=1^m (x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a ) [l_t,j,h- g_h(a|x,u) ]^2 ≤4B2m∑j=1m(xt,j=x,yt,j,<h=u,at,j,h=a). ≤ 4B^2m _j=1^m (x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a ). Taking the conditional expectation, we obtain Var(Yt(z)∣ℱt) (Y_t(z) _t) =[Yt(z)2∣ℱt] =E[Y_t(z)^2 _t] ≤4B2m[∑j=1m(xt,j=x,yt,j,<h=u,at,j,h=a)|ℱt]. ≤ 4B^2mE [ _j=1^m (x_t,j=x,\,y_t,j,<h=u,\,a_t,j,h=a ) |\,F_t ]. (D.10) Define Vt(z):=∑s=1tVar(Ys(z)∣ℱs)V_t(z):= _s=1^t (Y_s(z) _s). Since [Ys(z)∣ℱs]=0E[Y_s(z) _s]=0 and |Ys(z)|≤2B|Y_s(z)|≤ 2B, Lemma I.4 implies that both (∑s=1tYs(z),Vt(z))and(−∑s=1tYs(z),Vt(z)) ( _s=1^tY_s(z),\,V_t(z) ) (- _s=1^tY_s(z),\,V_t(z) ) are sub-gamma processes with parameter 2B/32B/3. Let K:=S∑h=1HAhK:=S _h=1^HA^h. Then, applying Lemma I.5 with ρ=2Bρ=2B, with probability at least 1−δ/(2K)1-δ/(2K), we have ∑s=1tYs(z)≤4Vt(z)log(2HtK/δ)+883Blog(2HtK/δ), _s=1^tY_s(z)≤ 4 V_t(z) (2H_tK/δ)+ 883B (2H_tK/δ), (D.11) where we can choose Ht=e+log(1+T)H_t=e+ (1+T) since Vt(z)≤4B2TV_t(z)≤ 4B^2T. Applying the same inequality to −Ys(z)-Y_s(z), and taking the union bound, we obtain that with probability at least 1−δ1-δ, the following inequality holds for any h and any z=(x,u,a)z=(x,u,a): |∑s=1tYs(z)|≤4Vt(z)log(2HtK/δ)+883Blog(2HtK/δ). | _s=1^tY_s(z) |≤ 4 V_t(z) (2H_tK/δ)+ 883B (2H_tK/δ). Since 1m∑j=1m(xs,j=x,ys,j,<h=u,as,j,h=a)∈[0,1], 1m _j=1^m (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a )∈[0,1], we can apply Lemma I.6 and obtain that for any h and z=(x,u,a)z=(x,u,a), with probability at least 1−δ/K1-δ/K, the following inequality holds simultaneously for all t∈[T]t∈[T]: ∑s=1t[1m∑j=1m(xs,j=x,ys,j,<h=u,as,j,h=a)|ℱs] _s=1^tE [ 1m _j=1^m (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a )\, |\,F_s ] ≤2∑s=1t1m∑j=1m(xs,j=x,ys,j,<h=u,as,j,h=a)+8log(2K/δ). ≤ 2 _s=1^t 1m _j=1^m (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a )+8 (2K/δ). (D.12) Taking a union bound over h and (x,u,a)(x,u,a), the inequality holds for all h and (x,u,a)(x,u,a) simultaneously. Combining (D.10) and (D.12), we have Vt(z) V_t(z) ≤8B2m∑s=1t∑j=1m(xs,j=x,ys,j,<h=u,as,j,h=a)+32B2log(2K/δ) ≤ 8B^2m _s=1^t _j=1^m (x_s,j=x,\,y_s,j,<h=u,\,a_s,j,h=a )+32B^2 (2K/δ) =8B2Nt(x,u,a)m+32B2log(2K/δ). = 8B^2N_t(x,u,a)m+32B^2 (2K/δ). (D.13) Substituting (D.13) into (D.11), we have, with probability at least 1−2δ1-2δ, simultaneously for every t∈[T]t∈[T], h, and z=(x,u,a)z=(x,u,a), the following inequality holds |∑s=1tYs(z)| | _s=1^tY_s(z) | ≤4(8B2Nt(x,u,a)m+32B2log2Kδ)log2HtKδ+883Blog2HtKδ ≤ 4 ( 8B^2N_t(x,u,a)m+32B^2 2Kδ ) 2H_tKδ+ 883B 2H_tKδ ≲BNt(x,u,a)mlog2HtKδ+Blog2HtKδ, B N_t(x,u,a)m 2H_tKδ+B 2H_tKδ, where we use v+w≤v+w v+w≤ v+ w and log(2K/δ)≤log(2HtK/δ) (2K/δ)≤ (2H_tK/δ). For every triple with Nt(x,u,a)≥1N_t(x,u,a)≥ 1, (D.9) gives |l¯t(x,u,a)−loggh(a|x,u)| | l_t(x,u,a)- g_h(a|x,u) | =mNt(x,u,a)|∑s=1tYs(z)| = mN_t(x,u,a) | _s=1^tY_s(z) | ≲BmNt(x,u,a)log2HtKδ+BmNt(x,u,a)log2HtKδ. B mN_t(x,u,a) 2H_tKδ+ BmN_t(x,u,a) 2H_tKδ. Finally, since K≤SHAHK≤ SHA^H and Ht=e+log(1+T)H_t=e+ (1+T), log2HtKδ≤HlogA+log[2SH(e+log(1+T))δ]. 2H_tKδ≤ H A+ [ 2SH (e+ (1+T) )δ ]. Hiding the logarithmic factors, we can define βt(x,u,a)=O~(BmHNt(x,u,a)+BmHNt(x,u,a)), _t(x,u,a)= O (B mHN_t(x,u,a)+ BmHN_t(x,u,a) ), and conclude that |l¯t(x,u,a)−loggh(a|x,u)|≤βt(x,u,a). | l_t(x,u,a)- g_h(a|x,u) |≤ _t(x,u,a). This completes the proof of Lemma 5.4. ∎ Appendix E Missing Proof in Section 6 Proof of Proposition 6.1. Fix N≥2N≥ 2 and α∈(0,1)α∈(0,1), and let b:=1/Nb:=1/N. For q∈(b,1)q∈(b,1), write the correct-response probabilities as F(q) F(q) :=πF∗(y⋆|x)=αq+(1−α)b, := _F^*(y |x)=α q+(1-α)b, R(q) R(q) :=πR∗(y⋆|x)=qαqα+(N−1)1−α(1−q)α. := _R^*(y |x)= q^αq^α+(N-1)^1-α(1-q)^α. Both probabilities lie in (0,1)(0,1). Since the log-odds function is strictly increasing, F(q)−R(q)F(q)-R(q) has the same sign as G(q) G(q) :=logF(q)1−F(q)−logR(q)1−R(q) := F(q)1-F(q)- R(q)1-R(q) =logF(q)1−F(q)−αlogq1−q+(1−α)log(N−1). = F(q)1-F(q)-α q1-q+(1-α) (N-1). The function G extends continuously to q=bq=b, with G(b)=0G(b)=0. Differentiating gives G′(q) G (q) =αF(q)(1−F(q))−αq(1−q) = αF(q)(1-F(q))- αq(1-q) =α(q−F(q))(1−q−F(q))F(q)(1−F(q))q(1−q). = α(q-F(q))(1-q-F(q))F(q)(1-F(q))q(1-q). For q>bq>b, we have q−F(q)=(1−α)(q−b)>0q-F(q)=(1-α)(q-b)>0. Thus, the sign of G′(q)G (q) is the sign of 1−q−F(q)=1−(1+α)q−(1−α)b,1-q-F(q)=1-(1+α)q-(1-α)b, which vanishes at qm:=[1−(1−α)b]/(1+α)q_m:=[1-(1-α)b]/(1+α). If N≥3N≥ 3, then b<qm<1b<q_m<1, so G is strictly increasing on (b,qm)(b,q_m) and strictly decreasing on (qm,1)(q_m,1). In particular, G(qm)>0G(q_m)>0. Moreover, F(q)→α+(1−α)b∈(0,1)F(q)→α+(1-α)b∈(0,1) as q↑1q 1, and hence G(q)→−∞G(q)→-∞. The intermediate value theorem and strict decrease on (qm,1)(q_m,1) imply that there is exactly one zero qc∈(qm,1)q_c∈(q_m,1). We have G(q)>0G(q)>0 for b<q<qcb<q<q_c and G(q)<0G(q)<0 for qc<q<1q_c<q<1, giving the claimed ordering. If N=2N=2, then qm=b=1/2q_m=b=1/2, so G′(q)<0G (q)<0 throughout (1/2,1)(1/2,1). Since G(b)=0G(b)=0, this gives G(q)<0G(q)<0 and therefore R(q)>F(q)R(q)>F(q) on that interval. Finally, both targets are below the expert probability for q>bq>b: we have F(q)<qF(q)<q, and R(q)1−R(q)=q1−q(1−q(N−1)q)1−α<q1−q, R(q)1-R(q)= q1-q ( 1-q(N-1)q )^1-α< q1-q, which implies R(q)<qR(q)<q. ∎ Proof of Proposition 6.3. Fix a context x and suppress its dependence in the notation. Since the forward target is the weighted arithmetic mixture of the teachers, summing over E gives πF∗(E)=∑iwipi(E)≥wkpk(E), _F^*(E)= _iw_ip_i(E)≥ w_kp_k(E), where the inequality follows from the nonnegativity of every summand. For the reverse target, fix α,q,η∈(0,1)α,q,η∈(0,1) and write m:=|E|m:=|E| and n:=|∖E|n:=|Y E|. Both m and n are positive. For ε∈(0,1) ∈(0,1), define two teachers by p1(y)=q/m,y∈E,(1−q)/n,y∉E,p2(y)=ε/m,y∈E,(1−ε)/n,y∉E.p_1(y)= casesq/m,&y∈ E,\\ (1-q)/n,&y∉ E, cases p_2(y)= cases /m,&y∈ E,\\ (1- )/n,&y∉ E. cases These distributions have full support, and p1(E)=qp_1(E)=q. With weights α and 1−α1-α, the unnormalized geometric masses on the two sets are ∑y∈Ep1(y)αp2(y)1−α _y∈ Ep_1(y)^αp_2(y)^1-α =qαε1−α, =q^α ^1-α, ∑y∉Ep1(y)αp2(y)1−α _y∉ Ep_1(y)^αp_2(y)^1-α =(1−q)α(1−ε)1−α. =(1-q)^α(1- )^1-α. Consequently, πR∗(E)=qαε1−αqαε1−α+(1−q)α(1−ε)1−α. _R^*(E)= q^α ^1-αq^α ^1-α+(1-q)^α(1- )^1-α. As ε↓0 0, the numerator tends to zero and the denominator tends to (1−q)α>0(1-q)^α>0. Hence πR∗(E)→0 _R^*(E)→ 0, and a sufficiently small positive ε ensures πR∗(E)<η _R^*(E)<η. This choice retains full support for both teachers and proves the claim. ∎ Proof of Proposition 6.5. Fix β∈(0,1/2)β∈(0,1/2) and r∈(1/2,1)r∈(1/2,1), and set α:=1−βα:=1-β. We construct the expert using token probabilities that do not depend on the horizon. Fix δ∈(0,1/2)δ∈(0,1/2), let p1(a|x)=rp_1(a|x)=r, and, at every subsequent position, set p1(a|x,u)=1−δ,if the first token of u is a,1/2,if the first token of u is b.p_1(a|x,u)= cases1-δ,&if the first token of $u$ is $a$,\\ 1/2,&if the first token of $u$ is $b$. cases The probability of b is the complementary probability at every prefix. Let p2p_2 assign probability 1/21/2 to each token at every prefix. Both teachers assign positive probability to every response in a,bH\a,b\^H for every finite H. Marginalizing the forward mixture over the last H−1H-1 tokens yields πF∗(a|x)=αr+β2=12+α(r−12)>12. _F^*(a|x)=α r+ β2= 12+α (r- 12 )> 12. Thus πF∗(a|x)>πF∗(b|x) _F^*(a|x)> _F^*(b|x) for every H. For the reverse target, the uniform teacher contributes the same factor 2−βH2^-β H to every complete response, so πR∗(y|x)=p1(y|x)α∑z∈a,bHp1(z|x)α. _R^*(y|x)= p_1(y|x)^α _z∈\a,b\^Hp_1(z|x)^α. Define Cα:=(1−δ)α+δαC_α:=(1-δ)^α+δ^α and Dα:=21−αD_α:=2^1-α. Summing the powered expert probabilities over continuations gives ∑v∈a,bH−1p1(av|x)α _v∈\a,b\^H-1p_1(av|x)^α =rαCαH−1, =r^αC_α^H-1, ∑v∈a,bH−1p1(bv|x)α _v∈\a,b\^H-1p_1(bv|x)^α =(1−r)αDαH−1. =(1-r)^αD_α^H-1. Since 0<α<10<α<1, the function t↦tαt t^α is strictly concave. As δ≠1/2δ≠ 1/2, strict concavity implies Cα=(1−δ)α+δα<2(12)α=Dα.C_α=(1-δ)^α+δ^α<2 ( 12 )^α=D_α. The reverse target’s first-token odds therefore satisfy πR∗(a|x)πR∗(b|x)=(r1−r)α(CαDα)H−1. _R^*(a|x) _R^*(b|x)= ( r1-r )^α ( C_αD_α )^H-1. In particular, these odds are strictly less than one whenever H>1+αlog(r/(1−r))log(Dα/Cα).H>1+ α (r/(1-r)) (D_α/C_α). The denominator is strictly positive, so this bound is finite for every fixed β and r in the stated ranges. The same construction thus satisfies πR∗(a|x)<πR∗(b|x) _R^*(a|x)< _R^*(b|x) for every sufficiently large integer H, completing the proof. ∎ Appendix F Parameter Sensitivity of Aggregation Targets We extend the examples in Section 6 by varying the teacher weights, expert confidence, response-space size, and continuation distributions. All curves are deterministic evaluations of the closed-form targets, rather than results of training a student. Each comparison holds the other parameters fixed. The vertical axes show the full probability range, and dashed lines indicate the expert’s probability. Uninformative teachers. The expert has weight α, assigns probability q to the correct response, and distributes its remaining mass uniformly over the N−1N-1 incorrect responses. The other teachers are uniform and have total weight 1−α1-α. Writing F(q):=πF∗(y⋆|x)F(q):= _F^*(y |x) and R(q):=πR∗(y⋆|x)R(q):= _R^*(y |x), we evaluate F(q)=αq+1−αN,R(q)=qαqα+(N−1)1−α(1−q)α.F(q)=α q+ 1-αN, R(q)= q^αq^α+(N-1)^1-α(1-q)^α. Here N counts responses; splitting the uniform teachers’ total weight among more identical teachers leaves both targets unchanged. Figure 2: Sensitivity to expert weight and response-space size with uninformative teachers. Panels (a–c) vary α∈0.5,0.9,0.99α∈\0.5,0.9,0.99\ at N=10N=10. Panels (d–f), together with (b), compare N∈2,10,100,1000N∈\2,10,100,1000\ at α=0.9α=0.9. Each curve varies q from 1/N1/N toward 11. Dotted vertical lines mark the interior crossing when it exists. Figure 2 shows that the region in which reverse aggregation retains more correct-response probability depends on both parameters. For the weights shown at N=10N=10, increasing α lowers the confidence threshold, although the targets become close as both approach the expert. At α=0.9α=0.9, increasing N from 1010 to 10001000 raises the threshold, narrowing the range of q with a reverse advantage. The binary case differs: reverse aggregation is larger throughout q∈(1/2,1)q∈(1/2,1), with no interior crossing. Misleading teachers. We fix N=10N=10 and replace the uniform teacher by a teacher of weight 1−α1-α that assigns probability ε to the correct response. Both teachers distribute their remaining probability uniformly over the incorrect responses. The targets are F(ε)=αq+(1−α)ε,R(ε)=qαε1−αqαε1−α+(1−q)α(1−ε)1−α.F( )=α q+(1-α) , R( )= q^α ^1-αq^α ^1-α+(1-q)^α(1- )^1-α. Figure 3 varies the expert weight at fixed q=0.99q=0.99, and its confidence at fixed α=0.9α=0.9. The horizontal coordinate is log10ε _10 ; we evaluate the reverse target in the log domain to retain accuracy for extremely small probabilities. Figure 3: Sensitivity to expert weight and confidence with misleading teachers. Panels (a–c) fix q=0.99q=0.99 and vary α. Panels (d–f), together with (b), fix α=0.9α=0.9 and compare q∈0.6,0.9,0.99,0.999q∈\0.6,0.9,0.99,0.999\. Horizontal ranges differ: log10ε∈[−10,−1] _10 ∈[-10,-1] in (a), [−600,−1][-600,-1] in (c), and [−60,−1][-60,-1] otherwise. Moving left makes the other teacher more misleading. Higher expert weight or confidence shifts the decline in reverse probability to smaller values of ε . This protection can be substantial: at q=0.99q=0.99, the reverse probability equals 1/21/2 at approximately ε=10−18 =10^-18 for α=0.9α=0.9, compared with 10−19810^-198 for α=0.99α=0.99. Nevertheless, every fixed α<1α<1 permits suppression as ε↓0 0, whereas forward aggregation remains above αqα q. The extreme ranges illustrate the absence of a uniform positive lower bound for reverse aggregation; they do not estimate how often such predictions arise in practice. Long horizons. The expert selects the correct first token a with probability r. At every subsequent position, its probabilities for (a,b)(a,b) are (1−δ,δ)(1-δ,δ) after an initial a and (1/2,1/2)(1/2,1/2) after an initial b. The other teacher is uniform at every prefix. With expert weight α, let Cα=(1−δ)α+δαC_α=(1-δ)^α+δ^α and Dα=21−αD_α=2^1-α. The first-token probabilities are FH=αr+1−α2,RH=[1+(1−r)α(DαCα)H−1]−1.F_H=α r+ 1-α2, R_H= [1+ ( 1-rr )^α ( D_αC_α )^H-1 ]^-1. Figure 4 varies α, r, and δ separately around (α,r,δ)=(0.9,0.99,0.01)(α,r,δ)=(0.9,0.99,0.01), evaluating every integer H from 11 to 10001000. Figure 4: Sensitivity of first-token probabilities to the horizon. Top row: vary α with r=0.99r=0.99 and δ=0.01δ=0.01. Middle row: vary r with α=0.9α=0.9 and δ=0.01δ=0.01. Bottom row: vary δ∈0.01,0.1,0.3δ∈\0.01,0.1,0.3\ with α=0.9α=0.9 and r=0.99r=0.99. The baseline is repeated in (b), (f), and (g). The horizontal axis is logarithmic; curves connect values computed at integer horizons. Increasing the expert’s weight or first-token confidence delays the reversal in the displayed settings. At r=0.99r=0.99 and δ=0.01δ=0.01, the first horizon with RH<1/2R_H<1/2 is 1010, 6868, or 717717 for α=0.5α=0.5, 0.90.9, or 0.990.99, respectively. Making the continuations after a more diffuse also delays reversal. For δ=0.3δ=0.3, the reverse probability first falls below 1/21/2 at H=555H=555, compared with H=68H=68 at δ=0.01δ=0.01. Forward aggregation is independent of H in every panel. Thus, in this construction, the deterioration arises from the difference between the continuation distributions, while expert confidence and weight determine how long the initial preference persists. Appendix G Forward KL with Function Approximation The tabular estimator learns a separate conditional distribution at each prefix. Function approximation allows these conditionals to share a common representation. Let Π=πθ:θ∈Θ =\ _θ:θ∈ \ be a finite class of autoregressive policies, where πθ(y|x)=∏h=1Hπθ(ah|x,y<h). _θ(y|x)= _h=1^H _θ(a_h|x,y_<h). We make the standard realizability assumption for the function class. Assumption G.1. There exists θ∗∈Θθ^*∈ such that, for every context x and every response y∈y , πθ∗(y|x)=πF∗(y|x). _θ^*(y|x)= _F^*(y|x). G.1 Algorithm Design We aggregate the candidate policies at the token level, using sampled tokens when logits are unavailable and full teacher probabilities otherwise. Recall the token feedback qt,j,h(a)q_t,j,h(a) defined in Section 4: qt,j,h(a):=(at,j,h=a)w/ologit,exp(Zt,j,h(a))∑b∈exp(Zt,j,h(b)),w/logit. q_t,j,h(a):= cases (a_t,j,h=a)&w/o\ logit,\\ (Z_t,j,h(a)) _b (Z_t,j,h(b)),&w/\ logit. cases For each θ∈Θθ∈ , define its empirical loss in round t by ℓt(πθ):=−1m∑j=1m∑h=1H∑a∈qt,j,h(a)logπθ(a|xt,j,yt,j,<h). _t( _θ):=- 1m _j=1^m _h=1^H _a q_t,j,h(a) _θ(a|x_t,j,y_t,j,<h). (G.1) The main idea of the algorithm is to maintain a distribution pt(θ)p_t(θ) over the parameter space Θ . More specifically, choose a prior distribution p0p_0 on Θ with p0(θ)>0p_0(θ)>0 for every θ∈Θθ∈ , and initialize L0(θ)=0L_0(θ)=0. At the beginning of round t, for any prefix (x,u)(x,u), the learner uses π^t(a|x,u):=∑θ∈Θpt−1(θ)πθ(a|x,u). π_t(a|x,u):= _θ∈ p_t-1(θ) _θ(a|x,u). (G.2) After observing the feedback, the learner updates pt(θ) p_t(θ) :=pt−1(θ)exp(−ℓt(πθ)/H)∑θ′∈Θpt−1(θ′)exp(−ℓt(πθ′)/H). := p_t-1(θ) (- _t( _θ)/H ) _θ ∈ p_t-1(θ ) (- _t( _θ )/H ). (G.3) The factor 1/H1/H normalizes the sum of the H token losses in each rollout. Intuitively, the update favors candidates with smaller cumulative empirical losses, relative to their prior weights. Algorithm 3 Forward KL with Function Approximation 1: Input: Finite policy class Π=πθ:θ∈Θ =\ _θ:θ∈ \, prior p0p_0 with p0(θ)>0p_0(θ)>0 for every θ, number of rounds T. 2: for t=1,…,Tt=1,…,T do 3: For any prefix (x,u)(x,u), construct the policy π^t(a|x,u) π_t(a|x,u) as in (G.2). 4: Observe the batch of teacher-generated rollouts (xt,j,yt,j)j=1m\(x_t,j,y_t,j)\_j=1^m and, when available, the teacher logits Zt,j,hj,h\Z_t,j,h\_j,h. 5: For every θ∈Θθ∈ , compute ℓt(πθ) _t( _θ) as in (G.1) 6: For every θ∈Θθ∈ , update the mixture weights pt(θ)p_t(θ) as in (G.3) 7: end for 8: Output: π^tt=1T\ π_t\_t=1^T. This exponential reweighting resembles the posterior updates used in Thompson sampling. Unlike Thompson sampling, however, our algorithm predicts with a mixture of the candidate policies rather than a single sampled candidate. Evaluating this mixture at each decoding step introduces large computational cost, which is a key limitation of our forward-KL algorithm with function approximation. G.2 Theoretical Guarantee In this section, we first work on a finite function class Θ . We will apply the results to the setting with finite covering number later. The following theorem bounds the regret by the prior weight of a good candidate and its approximation error. Under realizability, the approximation term vanishes. Theorem G.2. Let T≥2T≥ 2. Suppose the regret in (3.2) is defined with D(p∥q)=KL(q∥p)D(p\|q)=KL(q\|p). Under off-policy distillation protocol and the function approximation setting, both with and without access to teacher logits, Algorithm 3 satisfies [Regret(T)] [Regret(T) ] ≤infθ∈ΘHlog1p0(θ)+Tx∼ρ¯KL(πF∗(⋅|x)∥πθ(⋅|x)), ≤ _θ∈ \H 1p_0(θ)+TE_x ρKL ( _F^*(·|x)\, \|\, _θ(·|x) ) \, provided the right-hand side is finite. In particular, under Assumption G.1, for the optimal parameter θ∗θ^*, Algorithm 3 satisfies [Regret(T)]≤Hlog1p0(θ∗). [Regret(T) ]≤ H 1p_0(θ^*). Moreover, for any δ>0δ>0, under Assumption G.1, the following inequality holds with probability at least 1−δ1-δ: Regret(T)≤2Hlog1p0(θ∗)+4H(1+log2δp0(θ∗))log2δ. (T)≤ 2H 1p_0(θ^*)+4H (1+ 2δ p_0(θ^*) ) 2δ. Proof. Let ℱtF_t be the σ-algebra generated by all rollouts and feedback observed before round t: ℱt:=σ((xs,j,ys,j),qs,j,h(a):s<t,j∈[m],h∈[H],a∈). _t:=σ ((x_s,j,y_s,j),q_s,j,h(a):s<t,\ j∈[m],\ h∈[H],\ a ). Thus, both pt−1p_t-1 and π^t π_t are ℱtF_t-measurable. Recall the feedback counts ct(x,u,a)c_t(x,u,a) defined in (4.3). For any policy π, (G.1) can be rewritten as ℓt(π)=−∑h=1H∑(x,u,a)ct(x,u,a)logπ(a|x,u). _t(π)=- _h=1^H _(x,u,a)c_t(x,u,a) π(a|x,u). (G.4) Easy to see, the following equation holds ∑(x,u,a)ct(x,u,a)=1 _(x,u,a)c_t(x,u,a)=1 Therefore, we have ∑h=1H∑(x,u,a)ct(x,u,a)H=1. _h=1^H _(x,u,a) c_t(x,u,a)H=1. (G.5) For any t≥1t≥ 1, define the normalizing constant Ct:=∑θ∈Θp0(θ)exp(−1H∑s=1tℓs(πθ)), C_t:= _θ∈ p_0(θ) (- 1H _s=1^t _s( _θ) ), and C0=1C_0=1. Direct iteration of (G.3) gives pt(θ)=p0(θ)exp(−H−1∑s=1tℓs(πθ))Ct. p_t(θ)= p_0(θ) (-H^-1 _s=1^t _s( _θ) )C_t. Moreover, we have CtCt−1 C_tC_t-1 =1Ct−1∑θ′∈Θp0(θ′)exp(−1H∑s=1t−1ℓs(πθ′)−ℓt(πθ′)H) = 1C_t-1 _θ ∈ p_0(θ ) (- 1H _s=1^t-1 _s( _θ )- _t( _θ )H ) =∑θ′∈Θp0(θ′)exp(−H−1∑s=1t−1ℓs(πθ′))Ct−1⏟=pt−1(θ′)exp(−ℓt(πθ′)/H) = _θ ∈ p_0(θ ) (-H^-1 _s=1^t-1 _s( _θ ) )C_t-1_=\,p_t-1(θ ) (- _t( _θ )/H ) =∑θ′∈Θpt−1(θ′)exp(−ℓt(πθ′)/H). = _θ ∈ p_t-1(θ ) (- _t( _θ )/H ). (G.6) The definition of ℓt _t in (G.4) gives exp(−ℓt(πθ′)/H) (- _t( _θ )/H ) =exp(∑h=1H∑(x,u,a)ct(x,u,a)Hlogπθ′(a|x,u)) = ( _h=1^H _(x,u,a) c_t(x,u,a)H _θ (a|x,u) ) =∏h=1H∏(x,u,a)πθ′(a|x,u)ct(x,u,a)/H. = _h=1^H _(x,u,a) _θ (a|x,u)^c_t(x,u,a)/H. (G.7) Substituting (G.7) into (G.6), we have CtCt−1=∑θ′∈Θpt−1(θ′)∏h=1H∏(x,u,a)πθ′(a|x,u)ct(x,u,a)/H. C_tC_t-1= _θ ∈ p_t-1(θ ) _h=1^H _(x,u,a) _θ (a|x,u)^c_t(x,u,a)/H. (G.8) Using the generalized Hölder’s inequality, we have CtCt−1 C_tC_t-1 ≤∏h=1H∏(x,u,a)(∑θ′∈Θpt−1(θ′)πθ′(a|x,u))ct(x,u,a)/H ≤ _h=1^H _(x,u,a) ( _θ ∈ p_t-1(θ ) _θ (a|x,u) )^c_t(x,u,a)/H =∏h=1H∏(x,u,a)π^t(a|x,u)ct(x,u,a)/H = _h=1^H _(x,u,a) π_t(a|x,u)^c_t(x,u,a)/H =exp(−ℓt(π^t)/H), = (- _t( π_t)/H ), where the last equation holds using (G.4). Taking the negative logarithm, and summing over t∈[T]t∈[T] yields ∑t=1Tℓt(π^t) _t=1^T _t( π_t) ≤−H∑t=1TlogCtCt−1=−HlogCT, ≤-H _t=1^T C_tC_t-1=-H C_T, (G.9) where the equality uses C0=1C_0=1. Now fix any comparator policy πθ _θ such that θ∈Θθ∈ . Easy to see CT C_T =∑θ′p0(θ′)exp(−1H∑t=1Tℓt(πθ′)) = _θ p_0(θ ) (- 1H _t=1^T _t( _θ ) ) ≥p0(θ)exp(−1H∑t=1Tℓt(πθ)). ≥ p_0(θ) (- 1H _t=1^T _t( _θ) ). Therefore, we have −∑t=1Tℓt(πθ)≤HlogCT+Hlog1p0(θ). - _t=1^T _t( _θ)≤ H C_T+H 1p_0(θ). (G.10) Summing up (G.9) and (G.10), we have ∑t=1T[ℓt(π^t)−ℓt(πθ)]≤Hlog1p0(θ). _t=1^T [ _t( π_t)- _t( _θ) ]≤ H 1p_0(θ). (G.11) As a result, ∑t=1T[ℓt(π^t)−ℓt(πF∗)] _t=1^T [ _t( π_t)- _t( _F^*) ] =∑t=1T[ℓt(π^t)−ℓt(πθ)]+∑t=1T[ℓt(πθ)−ℓt(πF∗)] = _t=1^T [ _t( π_t)- _t( _θ) ]+ _t=1^T [ _t( _θ)- _t( _F^*) ] ≤Hlog1p0(θ)+∑t=1T[ℓt(πθ)−ℓt(πF∗)]. ≤ H 1p_0(θ)+ _t=1^T [ _t( _θ)- _t( _F^*) ]. (G.12) Using the same argument as in Appendix B, we have [ct(x,u,a)∣ℱt] [c_t(x,u,a) _t] =1I∑i∈ℐρi(x)pi(u|x)pi(a|x,u) = 1I _i _i(x)p_i(u|x)p_i(a|x,u) =ρ¯(x)πF∗(u|x)πF∗(a|x,u). = ρ(x) _F^*(u|x) _F^*(a|x,u). Consequently, using (G.4), for any ℱtF_t-measurable policy π with finite loss, [ℓt(π)−ℓt(πF∗)∣ℱt] [ _t(π)- _t( _F^*) _t ] =∑h=1H∑(x,u,a)[ct(x,u,a)∣ℱt]logπF∗(a|x,u)π(a|x,u) = _h=1^H _(x,u,a)E[c_t(x,u,a) _t] _F^*(a|x,u)π(a|x,u) =∑h=1H∑(x,u)ρ¯(x)πF∗(u|x)KL(πF∗(⋅|x,u)∥π(⋅|x,u)) = _h=1^H _(x,u) ρ(x) _F^*(u|x)KL ( _F^*(·|x,u)\, \|\,π(·|x,u) ) =x∼ρ¯KL(πF∗(⋅|x)∥π(⋅|x)). =E_x ρKL ( _F^*(·|x)\, \|\,π(·|x) ). (G.13) The last equality follows from the chain rule for KL divergence. Taking expectations in (G.12) and applying (G.13) to both π^t π_t and πθ _θ, we conclude that [Regret(T)] [Regret(T)] ≤Hlog1p0(θ)+∑t=1Tx∼ρ¯KL(πF∗(⋅|x)∥πθ(⋅|x)) ≤ H 1p_0(θ)+ _t=1^TE_x ρKL ( _F^*(·|x)\, \|\, _θ(·|x) ) =Hlog1p0(θ)+Tx∼ρ¯KL(πF∗(⋅|x)∥πθ(⋅|x)). =H 1p_0(θ)+TE_x ρKL ( _F^*(·|x)\, \|\, _θ(·|x) ). Since the inequality holds for every fixed θ, taking the infimum gives [Regret(T)]≤infθ∈ΘHlog1p0(θ)+Tx∼ρ¯KL(πF∗(⋅|x)∥πθ(⋅|x)). [Regret(T)]≤ _θ∈ \H 1p_0(θ)+TE_x ρKL ( _F^*(·|x)\, \|\, _θ(·|x) ) \. (G.14) High-probability bound under realizability. Suppose πθ∗=πF∗ _θ^*= _F^* for some θ∗∈Θθ^*∈ . As in Appendix B, define Xt X_t :=ℓt(πF∗)−ℓt(π^t), := _t( _F^*)- _t( π_t), rt r_t :=−[Xt∣ℱt]. :=-E[X_t _t]. By (G.13), Regret(T)=∑t=1TrtRegret(T)= _t=1^Tr_t. The argument establishing (B.20) applies to any ℱtF_t-measurable policy π, since it only uses policy normalization and the conditional mean of the feedback counts. Therefore, [exp(XtH)|ℱt]=[exp(ℓt(πF∗)−ℓt(π^t)H)|ℱt]≤1. [ ( X_tH ) |F_t ]=E [ ( _t( _F^*)- _t( π_t)H )\, |\,F_t ]≤ 1. (G.15) To replace the lower bound provided by KT smoothing in the tabular proof, we control the mixture weight of θ∗θ^*. Define W0=1W_0=1 and Wt W_t :=Ctexp(1H∑s=1tℓs(πF∗))=p0(θ∗)pt(θ∗). :=C_t ( 1H _s=1^t _s( _F^*) )= p_0(θ^*)p_t(θ^*). The equality follows from the formula for pt(θ∗)p_t(θ^*) and realizability. By (G.6), WtWt−1 W_tW_t-1 =CtCt−1exp(ℓt(πF∗)/H) = C_tC_t-1 ( _t( _F^*)/H ) =∑θ∈Θpt−1(θ)exp(ℓt(πF∗)−ℓt(πθ)H), = _θ∈ p_t-1(θ) ( _t( _F^*)- _t( _θ)H ), where we apply (G.6). Since Wt−1W_t-1 and pt−1p_t-1 are ℱtF_t-measurable, (G.15) implies [Wt∣ℱt] [W_t _t] =Wt−1∑θ∈Θpt−1(θ)[exp(ℓt(πF∗)−ℓt(πθ)H)|ℱt] =W_t-1 _θ∈ p_t-1(θ)E [ ( _t( _F^*)- _t( _θ)H )\, |\,F_t ] ≤Wt−1, ≤ W_t-1, where the last inequality holds due to (G.15). Thus, WtW_t is a nonnegative supermartingale with respect to ℱt+1t=0T\F_t+1\_t=0^T. Using Ville’s inequality (Lemma I.9), we have ℙ(max0≤t≤TWt≤2δ)≥1−δ2. ( _0≤ t≤ TW_t≤ 2δ )≥ 1- δ2. (G.16) Define Jt J_t :=(max0≤s<tWs≤2δ),L:=log2δp0(θ∗). := ( _0≤ s<tW_s≤ 2δ ), L:= 2δ p_0(θ^*). Whenever Jt=1J_t=1, the token-level mixture satisfies π^t(a|x,u)πF∗(a|x,u)≥pt−1(θ∗)=p0(θ∗)Wt−1≥e−L, π_t(a|x,u) _F^*(a|x,u)≥ p_t-1(θ^*)= p_0(θ^*)W_t-1≥ e^-L, where the first inequality holds due to π^t(a|x,u):=∑θpt−1(θ)πθ(a|x,u)≥pt−1(θ∗)πF∗(a|x,u) π_t(a|x,u):= _θp_t-1(θ) _θ(a|x,u)≥ p_t-1(θ^*) _F^*(a|x,u). The second inequality holds due to (G.16). Thus, logπ^t(a|x,u)πF∗(a|x,u)≥−L π_t(a|x,u) _F^*(a|x,u)≥-L for every (x,u,a)(x,u,a). Using the definition of XtX_t and the loss representation, we obtain XtH X_tH =ℓt(πF∗)−ℓt(π^t)H = _t( _F^*)- _t( π_t)H =∑h=1H∑(x,u,a)ct(x,u,a)Hlogπ^t(a|x,u)πF∗(a|x,u) = _h=1^H _(x,u,a) c_t(x,u,a)H π_t(a|x,u) _F^*(a|x,u) ≥−L∑h=1H∑(x,u,a)ct(x,u,a)H ≥-L _h=1^H _(x,u,a) c_t(x,u,a)H =−L. =-L. The inequality uses ct(x,u,a)≥0c_t(x,u,a)≥ 0, and the last equality follows from (G.5). When Jt=0J_t=0, we instead have JtXt/H=0≥−LJ_tX_t/H=0≥-L, since L≥0L≥ 0. Combining the two cases gives JtXtH≥−L. J_tX_tH≥-L. Moreover, since JtJ_t is ℱtF_t-measurable, [eJtXt/H∣ℱt] [e^J_tX_t/H _t] =1∗(Jt=0)+(Jt=1)[eXt/H∣ℱt] =1* (J_t=0)+ (J_t=1)E[e^X_t/H _t] =1−Jt+Jt[eXt/H∣ℱt] =1-J_t+J_tE[e^X_t/H _t] ≤1, ≤ 1, where the last inequality holds due to (G.15). Hence, Lemma B.2 and the argument leading to (B.22) apply to JtXtJ_tX_t, whose conditional means are −Jtrt-J_tr_t. Replacing LTL_T by L and the failure probability by δ/2δ/2, we obtain, for any fixed λ∈(0,1/H]λ∈(0,1/H], with probability at least 1−δ/21-δ/2, ∑t=1TJt(Xt+rt)≤H(1+L)λ∑t=1TJtrt+log(2/δ)λ. _t=1^TJ_t(X_t+r_t)≤ H(1+L)λ _t=1^TJ_tr_t+ (2/δ)λ. Choose λ=[2H(1+L)]−1λ=[2H(1+L)]^-1. Conditioned on the event in (G.16), and taking a union bound, we conclude that, with probability at least 1−δ1-δ, Regret(T)≤−∑t=1TXt+12Regret(T)+2H(1+L)log2δ. (T)≤- _t=1^TX_t+ 12Regret(T)+2H(1+L) 2δ. Finally, (G.11) with θ=θ∗θ=θ^* gives −∑t=1TXt≤Hlog1p0(θ∗). - _t=1^TX_t≤ H 1p_0(θ^*). Substituting this bound and rearranging yields Regret(T)≤2Hlog1p0(θ∗)+4H(1+log2δp0(θ∗))log2δ. (T)≤ 2H 1p_0(θ^*)+4H (1+ 2δ p_0(θ^*) ) 2δ. ∎ G.3 Function Class with Finite Covering Number Let Π=πθ:θ∈Θ =\ _θ:θ∈ \ be a class of autoregressive policies containing πF∗ _F^*. For ε>0 >0, we define the ε -covering number of the token log-probability class logΠ as follows. Definition G.3 (Covering number). The covering number (ε,logΠ,∥⋅∥∞)N( , ,\|·\|_∞) is the smallest cardinality of a finite subset Πε⊆Π _ such that, for every π∈Ππ∈ , there exists π~∈Πε π∈ _ satisfying ‖logπ−logπ~‖∞ \| π- π\|_∞ :=suph∈[H],x∈u∈h−1,a∈|logπ(a|x,u)−logπ~(a|x,u)|≤ε. := _ subarraych∈[H],\,x \\ u ^h-1,\,a subarray | π(a|x,u)- π(a|x,u) |≤ . When the function class Π has finite covering number Nε:=(ε,logΠ,∥⋅∥∞)<∞N_ :=N( , ,\|·\|_∞)<∞, we can choose an ε -cover Πε⊆Π _ of cardinality NεN_ , and run Algorithm 3 on Πε _ with a prior distribution p0p_0. Then, we have the following regret guarantee: Theorem G.4. Let Π be a class of autoregressive policies containing πF∗ _F^*. Fix ε>0 >0 such that Nε:=(ε,logΠ,∥⋅∥∞)<∞. N_ :=N( , ,\|·\|_∞)<∞. Let the algorithm be described as above and p0p_0 be the uniform prior. Under off-policy feedback, both with and without teacher logits, the expected regret can be bounded by [Regret(T)]≤HlogNε+THε. [Regret(T)]≤ H N_ +TH . Moreover, for every δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, Regret(T) (T) ≤2H(logNε+Tε)+4H(1+logNε+Tε+log2δ)log2δ. ≤ 2H ( N_ +T )+4H (1+ N_ +T + 2δ ) 2δ. Proof. Since πF∗∈Π _F^*∈ , the definition of the ε -cover ensures that there exists πθ¯∈Πε _ θ∈ _ such that ‖logπF∗−logπθ¯‖∞≤ε. \| _F^*- _ θ\|_∞≤ . (G.17) In particular, for every prefix–token triple (x,u,a)(x,u,a), logπF∗(a|x,u)πθ¯(a|x,u)≤ε. _F^*(a|x,u) _ θ(a|x,u)≤ . Using the autoregressive factorization, for every complete response y=(a1,…,aH)y=(a_1,…,a_H), we obtain logπF∗(y|x)πθ¯(y|x) _F^*(y|x) _ θ(y|x) =∑h=1HlogπF∗(ah|x,y<h)πθ¯(ah|x,y<h) = _h=1^H _F^*(a_h|x,y_<h) _ θ(a_h|x,y_<h) ≤Hε. ≤ H . Taking expectations over x∼ρ¯x ρ and y∼πF∗(⋅|x)y _F^*(·|x) therefore gives x∼ρ¯KL(πF∗(⋅|x)∥πθ¯(⋅|x))≤Hε. _x ρKL ( _F^*(·|x)\, \|\, _ θ(·|x) )≤ H . (G.18) The uniform prior on the cover assigns p0(θ¯)=1/Nεp_0( θ)=1/N_ . Applying Theorem G.2, we have [Regret(T)] [Regret(T)] ≤Hlog1p0(θ¯)+Tx∼ρ¯KL(πF∗(⋅|x)∥πθ¯(⋅|x)) ≤ H 1p_0( θ)+TE_x ρKL ( _F^*(·|x)\, \|\, _ θ(·|x) ) ≤HlogNε+THε, ≤ H N_ +TH , where we use that p0p_0 is uniform and (G.18). This has proved the expected regret bound. For the high-probability bound, let Θε _ index the NεN_ policies in Πε _ , with p0(θ)=1/Nεp_0(θ)=1/N_ for every θ∈Θεθ∈ _ . We use the same filtration ℱtF_t as in the finite-class analysis and define Xt X_t :=ℓt(πF∗)−ℓt(π^t), := _t( _F^*)- _t( π_t), rt r_t :=−[Xt∣ℱt]. :=-E[X_t _t]. By (G.13), Regret(T)=∑t=1TrtRegret(T)= _t=1^Tr_t. For the policy πθ¯ _ θ in (G.17), ℓt(πθ¯)−ℓt(πF∗) _t( _ θ)- _t( _F^*) =∑h=1H∑(x,u,a)ct(x,u,a)logπF∗(a|x,u)πθ¯(a|x,u) = _h=1^H _(x,u,a)c_t(x,u,a) _F^*(a|x,u) _ θ(a|x,u) ≤ε∑h=1H∑(x,u,a)ct(x,u,a)=Hε. ≤ _h=1^H _(x,u,a)c_t(x,u,a)=H . (G.19) Combining (G.19) with (G.11) gives −∑t=1TXt - _t=1^TX_t =∑t=1T[ℓt(π^t)−ℓt(πF∗)] = _t=1^T[ _t( π_t)- _t( _F^*)] =∑t=1T[ℓt(π^t)−ℓt(πθ¯)]+∑t=1T[ℓt(πθ¯)−ℓt(πF∗)] = _t=1^T[ _t( π_t)- _t( _ θ)]+ _t=1^T[ _t( _ θ)- _t( _F^*)] ≤HlogNε+∑t=1T[ℓt(πθ¯)−ℓt(πF∗)] ≤ H N_ + _t=1^T[ _t( _ θ)- _t( _F^*)] ≤HlogNε+THε. ≤ H N_ +TH . (G.20) Define CtC_t and WtW_t the same as in the last section, that is, Ct C_t :=∑θ∈Θεp0(θ)exp(−1H∑s=1tℓs(πθ))=1Nε∑θ∈Θεexp(−1H∑s=1tℓs(πθ)), := _θ∈ _ p_0(θ) (- 1H _s=1^t _s( _θ) )= 1N_ _θ∈ _ (- 1H _s=1^t _s( _θ) ), Wt W_t :=Ctexp(1H∑s=1tℓs(πF∗)), :=C_t ( 1H _s=1^t _s( _F^*) ), with C0=W0=1C_0=W_0=1. With a similar argument to (B.20), we have [exp(ℓt(πF∗)−ℓt(π^t)H)|ℱt]≤1. [ ( _t( _F^*)- _t( π_t)H )\, |\,F_t ]≤ 1. (G.21) Using the normalizer-ratio identity (G.6), we have WtWt−1 W_tW_t-1 =CtCt−1exp(ℓt(πF∗)/H) = C_tC_t-1 ( _t( _F^*)/H ) =∑θ∈Θεpt−1(θ)exp(ℓt(πF∗)−ℓt(πθ)H), = _θ∈ _ p_t-1(θ) ( _t( _F^*)- _t( _θ)H ), where the last equality holds due to the same argument as in (G.6). We also have pt(θ¯) p_t( θ) =Nε−1exp(−H−1∑s=1tℓs(πθ¯))Ct = N_ ^-1 (-H^-1 _s=1^t _s( _ θ) )C_t =1NεWtexp(−1H∑s=1t[ℓs(πθ¯)−ℓs(πF∗)]) = 1N_ W_t (- 1H _s=1^t[ _s( _ θ)- _s( _F^*)] ) ≥e−tεNεWt, ≥ e^-t N_ W_t, where the inequality uses (G.19). Furthermore, (G.17) implies πθ¯(a|x,u)≥e−επF∗(a|x,u) _ θ(a|x,u)≥ e^- _F^*(a|x,u). Therefore, the token-level mixture satisfies π^t(a|x,u)πF∗(a|x,u) π_t(a|x,u) _F^*(a|x,u) ≥pt−1(θ¯)πθ¯(a|x,u)πF∗(a|x,u) ≥ p_t-1( θ) _ θ(a|x,u) _F^*(a|x,u) ≥e−tεNεWt−1. ≥ e^-t N_ W_t-1. Using the same concentration argument as in the last section, we can consider the high-probability event max0≤s<tWs≤2δ. \ _0≤ s<tW_s≤ 2δ \. On this event, we have π^t(a|x,u)πF∗(a|x,u)≥δe−Tε2Nε=e−L, π_t(a|x,u) _F^*(a|x,u)≥ δ e^-T 2N_ =e^-L, where we define L:=log(2Nε/δ)+TεL:= (2N_ /δ)+T . Repeating the stopped-process argument from the proof of Theorem G.2, we obtain, with probability at least 1−δ1-δ, Regret(T) (T) ≤2H(logNε+Tε)+4H(1+logNε+Tε+log2δ)log2δ. ≤ 2H ( N_ +T )+4H (1+ N_ +T + 2δ ) 2δ. This proves Theorem G.4. ∎ Example G.5. Suppose Θ⊆ℝd ^d is a nonempty compact set contained in a Euclidean ball of radius R, where d≥1d≥ 1. Assume that πθ∗=πF∗ _θ^*= _F^* for some θ∗∈Θθ^*∈ . Moreover, suppose that, for some L0>0L_0>0, |logπθ(a|x,u)−logπθ′(a|x,u)|≤L0‖θ−θ′‖2 | _θ(a|x,u)- _θ (a|x,u) |≤ L_0\|θ-θ \|_2 for every θ,θ′∈Θθ,θ ∈ , h∈[H]h∈[H], and (x,u,a)∈×h−1×(x,u,a) ×A^h-1×A. Then, a standard Euclidean covering argument gives (ε,logΠ,∥⋅∥∞)≤(1+2RL0ε)d. ( , ,\|·\|_∞)≤ (1+ 2RL_0 )^d. For every T≥2T≥ 2, choose such a cover with ε=1/T =1/T. By Theorem G.4, the expected regret satisfies [Regret(T)]≤H[dlog(1+2RL0T)+1]. [Regret(T) ]≤ H [d (1+2RL_0T )+1 ]. Moreover, with probability at least 1−δ1-δ, we have Regret(T)≤O~(dHlogT). (T)≤ O(dH T). Appendix H Reverse KL with Function Approximation We now study on-policy distillation with function approximation. Fix any h∈[H]h∈[H]. For any prefix x∈x , u∈h−1u ^h-1, a∈a , following the notation in Theorem 5.1, we define the target as f∗(h,x,u,a):=loggh(a|x,u)=∑i∈ℐwi(x)logpi(a|x,u). f^*(h,x,u,a):= g_h(a|x,u)= _i w_i(x) p_i(a|x,u). Specifically, we define :=⋃h=1H(h×h−1×), := _h=1^H (\h\×X×A^h-1×A ), and write zt,j,h:=(h,xt,j,yt,j,<h,at,j,h)z_t,j,h:=(h,x_t,j,y_t,j,<h,a_t,j,h) for the query associated with the h-th token of rollout j in round t. Throughout this section, we retain Assumption 5.3, with reference policy πref _ref and bound B>0B>0. Moreover, let ℱF be a finite class of functions f:→ℝf:Z . We further impose the following realizability assumption. Assumption H.1. f∗∈ℱf^* . To measure how past observations constrain predictions at a new query, we introduce a new version of generalized Eluder dimension adapted to autoregressive trajectory batches. The underlying uncertainty compares the disagreement between two candidate score functions at the current query with their cumulative squared disagreement on previously observed data. Since the estimator is updated only after each round, this comparison uses observations from completed rounds, without incorporating feedback from the current batch. Definition H.2. Fix λ>0λ>0. For a sequence of trajectory batches, write Zt:=(zt,j,h)j∈[m],h∈[H],Z<t:=(Z1,…,Zt−1). Z_t:=(z_t,j,h)_j∈[m],\,h∈[H], Z_<t:=(Z_1,…,Z_t-1). For any query z∈z , define Dℱ2(z,Z<t):=supf1,f2∈ℱ(f1(z)−f2(z))2λ+∑s=1t−11mH∑j=1m∑h=1H(f1(zs,j,h)−f2(zs,j,h))2. D_F^2(z;Z_<t):= _f_1,f_2 (f_1(z)-f_2(z) )^2λ+ _s=1^t-1 1mH _j=1^m _h=1^H (f_1(z_s,j,h)-f_2(z_s,j,h) )^2. (H.1) The batched generalized Eluder dimension is dimT(ℱ;λ):=supZ1:T∑t=1T1mH∑j=1m∑h=1Hmin1,Dℱ2(zt,j,h;Z<t), _T(F;λ):= _Z_1:T _t=1^T 1mH _j=1^m _h=1^H \1,\,D_F^2(z_t,j,h;Z_<t) \, (H.2) where the supremum is over all sequences of T trajectory batches, each containing m rollouts of horizon H. H.1 Algorithm Design Recall that, for every visited query zt,j,h=(h,x,u,a)z_t,j,h=(h,x,u,a), [lt,j,h|ℱt,zt,j,h=(h,x,u,a)] [l_t,j,h\, |\,F_t,\,z_t,j,h=(h,x,u,a) ] =∑i∈ℐwi(x)logpi(a|x,u) = _i w_i(x) p_i(a|x,u) =loggh(a|x,u)=f∗(h,x,u,a), = g_h(a|x,u)=f^*(h,x,u,a), (H.3) where ℱtF_t denotes the history before round t. This identity motivates estimating f∗f^* by least squares. For each f∈ℱf , define ℓt(f) _t(f) :=1mH∑j=1m∑h=1H(f(zt,j,h)−lt,j,h)2. := 1mH _j=1^m _h=1^H (f(z_t,j,h)-l_t,j,h )^2. (H.4) Moreover, we define Lt(f) L_t(f) :=∑s=1tℓs(f),L0(f):=0. := _s=1^t _s(f), L_0(f):=0. At the beginning of round t, the learner computes f¯t−1∈argminf∈ℱLt−1(f). f_t-1∈ argmin_f L_t-1(f). (H.5) Using the principle of optimism for online reinforcement learning, we therefore define a bonus using the batched generalized Eluder dimension, i.e., for any z∈z , the bonus function is defined as bt−1(z):=(4β+λ)Dℱ2(z,Z<t), b_t-1(z):= (4β+λ)D_F^2(z;Z_<t), (H.6) where λ>0λ>0 and β>0β>0 are parameters to be specified later. Given the reference policy πref _ref and the bound B from Assumption 5.3, as it implies |f∗(h,x,u,a)−logπref(a|x,u)|≤B, |f^*(h,x,u,a)- _ref(a|x,u) |≤ B, we define the optimistic score by f^t−1(h,x,u,a):=minf¯t−1(h,x,u,a)+bt−1(h,x,u,a),logπref(a|x,u)+B. f_t-1(h,x,u,a):= \ f_t-1(h,x,u,a)+b_t-1(h,x,u,a),\, _ref(a|x,u)+B \. (H.7) The following lemma establishes pointwise optimism and bounds the error of the optimistic score. Lemma H.3. Under Assumptions 5.3 and H.1, fix δ∈(0,1)δ∈(0,1) and choose β=32B2log|ℱ|δ,λ>0. β=32B^2 |F|δ, λ>0. Then, with probability at least 1−δ1-δ, simultaneously for every t∈[T]t∈[T] and z∈z , |f¯t−1(z)−f∗(z)| | f_t-1(z)-f^*(z) | ≤bt−1(z). ≤ b_t-1(z). Furthermore, the following inequality holds 0≤f^t−1(z)−f∗(z) 0≤ f_t-1(z)-f^*(z) ≤min2bt−1(z),2B. ≤ \2b_t-1(z),2B \. To construct the output policy, we apply the backward propagation as in the tabular setting to the estimated scores f^t f_t. More specifically, set V^t−1,H+1(x,y)=1 V_t-1,H+1(x,y)=1 and recursively define V^t−1,h(x,u) V_t-1,h(x,u) :=∑a∈exp(f^t−1(h,x,u,a))V^t−1,h+1(x,(u,a)), := _a ( f_t-1(h,x,u,a) ) V_t-1,h+1(x,(u,a)), (H.8) for h=H,…,1h=H,…,1. We then output π^t(a|x,u):=exp(f^t−1(h,x,u,a))V^t−1,h+1(x,(u,a))V^t−1,h(x,u). π_t(a|x,u):= ( f_t-1(h,x,u,a) ) V_t-1,h+1(x,(u,a)) V_t-1,h(x,u). (H.9) This procedure is described in Algorithm 4. Algorithm 4 Optimistic Reverse KL with Function Approximation 1: Input: Function class ℱF, reference policy πref _ref, bound B, horizon H, batch size m, number of rounds T, and parameters λ,β>0λ,β>0. 2: Initialize L0(f)=0L_0(f)=0 for every f∈ℱf . 3: for t=1,…,Tt=1,…,T do 4: Compute the regression estimate f¯t−1 f_t-1 using (H.5). 5: Compute bt−1b_t-1 and f^t−1 f_t-1 using (H.6) and (H.7). 6: Set V^t−1,H+1(x,y)=1 V_t-1,H+1(x,y)=1 and compute the backward recursion (H.8). 7: Construct π^t π_t using (H.9). 8: Receive contexts xt,jj=1m\x_t,j\_j=1^m according to the on-policy protocol and generate yt,j∼π^t(⋅|xt,j)y_t,j π_t(·|x_t,j). 9: Observe teacher feedback lt,j,hj∈[m],h∈[H]\l_t,j,h\_j∈[m],\,h∈[H]. 10: Compute ℓt(f) _t(f) using (H.4) and update Lt(f)=Lt−1(f)+ℓt(f)L_t(f)=L_t-1(f)+ _t(f) for every f∈ℱf . 11: end for 12: Output: π^tt=1T\ π_t\_t=1^T. H.2 Theoretical Guarantee Given Lemma H.3, we have the following guarantee on the regret of Algorithm 4. Theorem H.4. Under Assumptions 5.3 and H.1, fix δ∈(0,1)δ∈(0,1) and choose λ>0λ>0 and β≥32B2log2|ℱ|δ β≥ 32B^2 2|F|δ Then, with probability at least 1−δ1-δ, Algorithm 4 satisfies Regret(T) (T) :=∑t=1Tx∼ρ¯KL(π^t(⋅|x)∥πR∗(⋅|x)) := _t=1^TE_x ρKL ( π_t(·|x)\, \|\, _R^*(·|x) ) ≤4H2(4β+λ)dimT(ℱ;λ)+16H2B2log4δ. ≤ 4H^2(4β+λ) _T(F;λ)+16H^2B^2 4δ. In particular, if we choose λ=B2λ=B^2 and β=32B2log(2|ℱ|/δ)β=32B^2 (2|F|/δ), we have Regret(T)≤O(B2H2dimT(ℱ;B2)log2|ℱ|δ). (T)≤ O (B^2H^2 _T(F;B^2) 2|F|δ ). Proof. Let ℱtF_t denote the history before round t. In particular, f¯t−1 f_t-1, bt−1b_t-1, and π^t π_t are ℱtF_t-measurable. Applying Lemma H.3, we have with probability at least 1−δ/21-δ/2, the following inequality holds simultaneously for every t∈[T]t∈[T] and z∈z 0≤f^t−1(z)−f∗(z)≤min2bt−1(z),2B, 0≤ f_t-1(z)-f^*(z)≤ \2b_t-1(z),2B\, (H.10) when β≥32B2log(2|ℱ|/δ)β≥ 32B^2 (2|F|/δ). Let ℰE be this high-probability event. For every t and z, define ψt(z) _t(z) :=min4bt−1(z)2,4B2. := \4b_t-1(z)^2,4B^2\. (H.11) Then we have 0≤ψt(z)≤4B20≤ _t(z)≤ 4B^2. On ℰE, (H.10) further gives [f^t−1(z)−f∗(z)]2≤ψt(z). [ f_t-1(z)-f^*(z) ]^2≤ _t(z). (H.12) Fix a context x and a response y. Write vt(x,y):=∑h=1H[f^t−1(h,x,y<h,ah)−f∗(h,x,y<h,ah)]. v_t(x,y):= _h=1^H [ f_t-1(h,x,y_<h,a_h)-f^*(h,x,y_<h,a_h) ]. On ℰE, every summand is nonnegative, so vt(x,y)≥0v_t(x,y)≥ 0. Recall that for y=(a1,…,aH)y=(a_1,…,a_H), the backward propagation gives π^t(y|x) π_t(y|x) =∏h=1Hef^t−1(h,x,y<h,ah)V^t−1,h+1(x,y≤h)V^t−1,h(x,y<h) = _h=1^H e f_t-1(h,x,y_<h,a_h) V_t-1,h+1(x,y_≤ h) V_t-1,h(x,y_<h) =exp(∑h=1Hf^t−1(h,x,y<h,ah))V^t−1,1(x), = ( _h=1^H f_t-1(h,x,y_<h,a_h) ) V_t-1,1(x), where we used V^t−1,H+1(x,y)=1 V_t-1,H+1(x,y)=1. Similarly, the reverse target satisfies πR∗(y|x)=exp(∑h=1Hf∗(h,x,y<h,ah))V1(x), _R^*(y|x)= ( _h=1^Hf^*(h,x,y_<h,a_h) )V_1(x), where V1(x)=∑yexp(∑h=1Hf∗(h,x,y<h,ah))V_1(x)= _y ( _h=1^Hf^*(h,x,y_<h,a_h) ). Taking the logarithm of their ratio therefore yields logπ^t(y|x)πR∗(y|x) π_t(y|x) _R^*(y|x) =∑h=1H[f^t−1(h,x,y<h,ah)−f∗(h,x,y<h,ah)] = _h=1^H [ f_t-1(h,x,y_<h,a_h)-f^*(h,x,y_<h,a_h) ] +logV1(x)−logV^t−1,1(x) + V_1(x)- V_t-1,1(x) =vt(x,y)+logV1(x)V^t−1,1(x). =v_t(x,y)+ V_1(x) V_t-1,1(x). (H.13) To express the ratio of normalizing constants as an expectation, expand the expectation over complete responses: y∼π^t(⋅|x)[e−vt(x,y)] _y π_t(·|x) [e^-v_t(x,y) ] =∑y∈π^t(y|x)e−vt(x,y) = _y π_t(y|x)e^-v_t(x,y) =∑y∈exp(∑h=1Hf^t−1(h,x,y<h,ah))V^t−1,1(x)exp(∑h=1H[f∗(h,x,y<h,ah)−f^t−1(h,x,y<h,ah)]) = _y ( _h=1^H f_t-1(h,x,y_<h,a_h) ) V_t-1,1(x) ( _h=1^H [f^*(h,x,y_<h,a_h)- f_t-1(h,x,y_<h,a_h) ] ) =1V^t−1,1(x)∑y∈exp(∑h=1Hf∗(h,x,y<h,ah)) = 1 V_t-1,1(x) _y ( _h=1^Hf^*(h,x,y_<h,a_h) ) =V1(x)V^t−1,1(x). = V_1(x) V_t-1,1(x). (H.14) The third equality follows by cancellation of the f^t−1 f_t-1 terms in the exponent. The last equality uses the definition of V1(x)V_1(x). Taking expectation over π^t(⋅|x) π_t(·|x) in (H.13) and considering (H.14), we have KL(π^t(⋅|x)∥πR∗(⋅|x)) ( π_t(·|x)\, \|\, _R^*(·|x) ) =π^t[vt(x,y)]+logπ^t[e−vt(x,y)] =E_ π_t[v_t(x,y)]+ _ π_t[e^-v_t(x,y)] ≤π^t[vt(x,y)]+π^t[e−vt(x,y)]−1 _ π_t[v_t(x,y)]+E_ π_t[e^-v_t(x,y)]-1 ≤12π^t[vt(x,y)2]. ≤ 12E_ π_t[v_t(x,y)^2]. (H.15) Here the first inequality uses logu≤u−1 u≤ u-1 for u>0u>0, and the second uses e−v≤1−v+v2/2e^-v≤ 1-v+v^2/2 for v≥0v≥ 0. All expectations in this display are conditional on x. By the Cauchy–Schwarz inequality and (H.12), vt(x,y)2 v_t(x,y)^2 ≤H∑h=1H[f^t−1(h,x,y<h,ah)−f∗(h,x,y<h,ah)]2 ≤ H _h=1^H [ f_t-1(h,x,y_<h,a_h)-f^*(h,x,y_<h,a_h) ]^2 ≤H∑h=1Hψt(h,x,y<h,ah). ≤ H _h=1^H _t(h,x,y_<h,a_h). Consequently, on ℰE, Regret(T) (T) ≤H2∑t=1Tx∼ρ¯,y∼π^t(⋅|x)[∑h=1Hψt(h,x,y<h,ah)]. ≤ H2 _t=1^TE_x ρ,\,y π_t(·|x) [ _h=1^H _t(h,x,y_<h,a_h) ]. (H.16) Define Xt:=1mH∑j=1m∑h=1Hψt(zt,j,h). X_t:= 1mH _j=1^m _h=1^H _t(z_t,j,h). Then XtX_t is ℱt+1F_t+1-measurable and satisfies 0≤Xt≤4B20≤ X_t≤ 4B^2 almost surely. Under the on-policy protocol, each rollout has conditional marginal distribution ℙ(xt,j=x,yt,j=y∣ℱt) (x_t,j=x,\,y_t,j=y _t ) =1I∑i∈ℐρi(x)π^t(y|x) = 1I _i _i(x) π_t(y|x) =ρ¯(x)π^t(y|x). = ρ(x) π_t(y|x). Since ψt _t is determined before round t, this implies [Xt∣ℱt]=1Hx∼ρ¯,y∼π^t(⋅|x)[∑h=1Hψt(h,x,y<h,ah)]. [X_t _t]= 1HE_x ρ,\,y π_t(·|x) [ _h=1^H _t(h,x,y_<h,a_h) ]. (H.17) This identity uses only the marginal law of each rollout, not independence within the batch. Combining (H.16) and (H.17), we obtain, on ℰE, Regret(T)≤H22∑t=1T[Xt∣ℱt]. (T)≤ H^22 _t=1^TE[X_t _t]. (H.18) Apply Lemma I.6 to Xtt=1T\X_t\_t=1^T, with range bound 4B24B^2 and failure probability δ/2δ/2. With probability at least 1−δ/21-δ/2, ∑t=1T[Xt∣ℱt]≤2∑t=1TXt+32B2log4δ. _t=1^TE[X_t _t]≤ 2 _t=1^TX_t+32B^2 4δ. (H.19) Taking a union bound, we conclude that, with probability at least 1−δ1-δ, Regret(T)≤H2∑t=1TXt+16H2B2log4δ. (T)≤ H^2 _t=1^TX_t+16H^2B^2 4δ. (H.20) Finally, by the definition of the bonus function, we have ψt(z)=4min(4β+λ)Dℱ2(z,Z<t),B2. _t(z)=4 \(4β+λ)D_F^2(z;Z_<t),B^2 \. Our choice of β ensures 4β+λ≥B24β+λ≥ B^2. Therefore, ψt(z)≤4(4β+λ)min1,Dℱ2(z,Z<t). _t(z)≤ 4(4β+λ) \1,D_F^2(z;Z_<t) \. (H.21) Indeed, when Dℱ2(z,Z<t)≤1D_F^2(z;Z_<t)≤ 1, we use the first term in the minimum defining ψt _t. Otherwise, we use ψt(z)≤4B2≤4(4β+λ) _t(z)≤ 4B^2≤ 4(4β+λ). Summing (H.21) over the observed queries gives ∑t=1TXt _t=1^TX_t =∑t=1T1mH∑j=1m∑h=1Hψt(zt,j,h) = _t=1^T 1mH _j=1^m _h=1^H _t(z_t,j,h) ≤4(4β+λ)∑t=1T1mH∑j=1m∑h=1Hmin1,Dℱ2(zt,j,h,Z<t) ≤ 4(4β+λ) _t=1^T 1mH _j=1^m _h=1^H \1,D_F^2(z_t,j,h;Z_<t) \ ≤4(4β+λ)dimT(ℱ;λ). ≤ 4(4β+λ) _T(F;λ). The last inequality follows from the definition of the generalized Eluder dimension, since the observed batches form a valid sequence of autoregressive trajectories. Substituting this inequality into (H.20) completes the proof of Theorem H.4. ∎ H.3 Proof of Lemma H.3 Proof. Let ℱtF_t denote the history before round t. Fix f∈ℱf , and define Δt,j,h(f) _t,j,h(f) :=f(zt,j,h)−f∗(zt,j,h), :=f(z_t,j,h)-f^*(z_t,j,h), ξt,j,h _t,j,h :=lt,j,h−f∗(zt,j,h). :=l_t,j,h-f^*(z_t,j,h). The conditional-mean identity gives [ξt,j,h∣ℱt,zt,j,h]=0. [ _t,j,h _t,z_t,j,h]=0. (H.22) Moreover, conditioned on zt,j,h=z=(h,x,u,a)z_t,j,h=z=(h,x,u,a), Assumption 5.3 implies ξt,j,h∈[logπref(a|x,u)−B−f∗(z),logπref(a|x,u)+B−f∗(z)]. _t,j,h∈ [ _ref(a|x,u)-B-f^*(z),\, _ref(a|x,u)+B-f^*(z) ]. We use the abbreviation Δ:=Δt,j,h(f),ξ:=ξt,j,h := _t,j,h(f),ξ:= _t,j,h. Then, applying Assumption 5.3 to f∗f^* and observing that it is an average over all the teachers, we have [ξ∣ℱt,zt,j,h]=0,|ξ|≤2B. [ξ _t,z_t,j,h]=0, |ξ|≤ 2B. Set η=1/(32B2)η=1/(32B^2). We claim that [eη(2Δξ−Δ2/2)∣ℱt,zt,j,h]≤1. [e^η(2 ξ- ^2/2) _t,z_t,j,h ]≤ 1. (H.23) In fact, if |Δ|≥8B| |≥ 8B, then 2Δξ−Δ22≤4B|Δ|−Δ22≤0. 2 ξ- ^22≤ 4B| |- ^22≤ 0. Thus, (H.23) holds in this case. Otherwise, if |Δ|<8B| |<8B, then |2ηΔξ|≤2η⋅8B⋅2B=1. |2η ξ|≤ 2η· 8B· 2B=1. Using eu≤1+u+u2e^u≤ 1+u+u^2 for |u|≤1|u|≤ 1, we obtain [e2ηΔξ∣ℱt,zt,j,h] [e^2η ξ _t,z_t,j,h] ≤1+2ηΔ[ξ∣ℱt,zt,j,h]+4η2Δ2[ξ2∣ℱt,zt,j,h] ≤ 1+2η [ξ _t,z_t,j,h]+4η^2 ^2E[ξ^2 _t,z_t,j,h] ≤1+16η2B2Δ2 ≤ 1+16η^2B^2 ^2 ≤exp(16η2B2Δ2) ≤ (16η^2B^2 ^2) =exp(ηΔ2/2). = (η ^2/2). The second inequality uses the zero conditional mean and ξ2≤4B2ξ^2≤ 4B^2. The third uses 1+v≤ev1+v≤ e^v, and the last equality follows from our choice of η. Multiplying both sides by e−ηΔ2/2e^-η ^2/2 proves (H.23). To handle the dependence within a round, apply Jensen’s inequality to the exponential function: exp(ηmH∑j=1m∑h=1H[2Δt,j,h(f)ξt,j,h−12Δt,j,h(f)2]) ( ηmH _j=1^m _h=1^H [2 _t,j,h(f) _t,j,h- 12 _t,j,h(f)^2 ] ) ≤1mH∑j=1m∑h=1Hexp(η[2Δt,j,h(f)ξt,j,h−12Δt,j,h(f)2]). ≤ 1mH _j=1^m _h=1^H (η [2 _t,j,h(f) _t,j,h- 12 _t,j,h(f)^2 ] ). Taking conditional expectations given ℱtF_t and applying (H.23) to each summand gives [exp(ηmH∑j=1m∑h=1H[2Δt,j,h(f)ξt,j,h−12Δt,j,h(f)2])|ℱt]≤1. [ ( ηmH _j=1^m _h=1^H [2 _t,j,h(f) _t,j,h- 12 _t,j,h(f)^2 ] )\, |\,F_t ]≤ 1. (H.24) We do not condition on the entire batch or assume independence among its observations. Define M0(f)=1M_0(f)=1 and Mt(f):=exp(η∑s=1t1mH∑j=1m∑h=1H[2Δs,j,h(f)ξs,j,h−12Δs,j,h(f)2]). M_t(f):= (η _s=1^t 1mH _j=1^m _h=1^H [2 _s,j,h(f) _s,j,h- 12 _s,j,h(f)^2 ] ). Equation (H.24) implies [Mt(f)∣ℱt]≤Mt−1(f). [M_t(f) _t]≤ M_t-1(f). Thus, Mt(f)t=0T\M_t(f)\_t=0^T is a nonnegative supermartingale. By Ville’s inequality (Lemma I.9), ℙ(max0≤t≤TMt(f)>|ℱ|δ)≤δ|ℱ|. ( _0≤ t≤ TM_t(f)> |F|δ )≤ δ|F|. Taking a union bound over f∈ℱf , we obtain an event ℰE with ℙ(ℰ)≥1−δP(E)≥ 1-δ on which, simultaneously for every f∈ℱf and t∈0,…,Tt∈\0,…,T\, ∑s=1t1mH∑j=1m∑h=1H[2Δs,j,h(f)ξs,j,h−12Δs,j,h(f)2] _s=1^t 1mH _j=1^m _h=1^H [2 _s,j,h(f) _s,j,h- 12 _s,j,h(f)^2 ] ≤1ηlog|ℱ|δ ≤ 1η |F|δ =32B2log|ℱ|δ =32B^2 |F|δ ≤β. ≤β. (H.25) Expanding the difference of squared losses gives (f(zs,j,h)−ls,j,h)2−(f∗(zs,j,h)−ls,j,h)2=Δs,j,h(f)2−2Δs,j,h(f)ξs,j,h. (f(z_s,j,h)-l_s,j,h)^2-(f^*(z_s,j,h)-l_s,j,h)^2= _s,j,h(f)^2-2 _s,j,h(f) _s,j,h. Therefore, on ℰE, Lt(f)−Lt(f∗) L_t(f)-L_t(f^*) =12∑s=1t1mH∑j=1m∑h=1HΔs,j,h(f)2 = 12 _s=1^t 1mH _j=1^m _h=1^H _s,j,h(f)^2 −∑s=1t1mH∑j=1m∑h=1H[2Δs,j,h(f)ξs,j,h−12Δs,j,h(f)2] - _s=1^t 1mH _j=1^m _h=1^H [2 _s,j,h(f) _s,j,h- 12 _s,j,h(f)^2 ] ≥12∑s=1t1mH∑j=1m∑h=1HΔs,j,h(f)2−β, ≥ 12 _s=1^t 1mH _j=1^m _h=1^H _s,j,h(f)^2-β, (H.26) where the last inequality holds due to (H.25). It holds for any f∈ℱf , so it also applies to f¯t−1 f_t-1. Moreover, by (H.5) and the realizability assumption, we have Lt−1(f¯t−1)≤Lt−1(f∗). L_t-1( f_t-1)≤ L_t-1(f^*). Applying (H.26) at time t−1t-1 consequently gives ∑s<t1mH∑j=1m∑h=1H[f¯t−1(zs,j,h)−f∗(zs,j,h)]2≤2β. _s<t 1mH _j=1^m _h=1^H [ f_t-1(z_s,j,h)-f^*(z_s,j,h) ]^2≤ 2β. (H.27) Since both f¯t−1 f_t-1 and f∗f^* belong to ℱF, the definition of Dℱ2D_F^2 implies, for every z∈z , |f¯t−1(z)−f∗(z)|2 | f_t-1(z)-f^*(z) |^2 ≤Dℱ2(z,Z<t)(λ+∑s<t1mH∑j=1m∑h=1H[f¯t−1(zs,j,h)−f∗(zs,j,h)]2) ≤ D_F^2(z;Z_<t) (λ+ _s<t 1mH _j=1^m _h=1^H [ f_t-1(z_s,j,h)-f^*(z_s,j,h) ]^2 ) ≤(λ+2β)Dℱ2(z,Z<t) ≤(λ+2β)D_F^2(z;Z_<t) ≤bt−1(z)2. ≤ b_t-1(z)^2. Taking square roots proves the pointwise confidence bound. Finally, for z=(h,x,u,a)z=(h,x,u,a), Assumption 5.3 and the definition of f∗f^* give logπref(a|x,u)−B≤f∗(z)≤logπref(a|x,u)+B. _ref(a|x,u)-B≤ f^*(z)≤ _ref(a|x,u)+B. On ℰE, the confidence bound also gives f¯t−1(z)+bt−1(z)≥f∗(z). f_t-1(z)+b_t-1(z)≥ f^*(z). Therefore, f^t−1(z)≥f∗(z) f_t-1(z)≥ f^*(z), which proves optimism. Moreover, f^t−1(z)−f∗(z) f_t-1(z)-f^*(z) =minf¯t−1(z)−f∗(z)+bt−1(z),logπref(a|x,u)+B−f∗(z) = \ f_t-1(z)-f^*(z)+b_t-1(z),\, _ref(a|x,u)+B-f^*(z) \ ≤min2bt−1(z),2B. ≤ \2b_t-1(z),2B\. This completes the proof of Lemma H.3. ∎ Appendix I Auxiliary Lemmas I.1 Uniform Bernstein Concentration in Bakhtiari et al. (2026) First, we list several key results from Bakhtiari et al. (2026) that are used in our analysis. To start with, we present several definitions. Definition I.1 (CGF-like, Definition 4 Bakhtiari et al. 2026). A twice differentiable function ψ:[0,λmax)→ℝ+ψ:[0, _ ) _+ is called CGF-like if it is convex, non-negative, and satisfies ψ(0)=ψ′(0)=0ψ(0)=ψ (0)=0. Definition I.2 (sub-ψ process, Definition 5 Bakhtiari et al. 2026). Let ℱtt∈[T]\F_t\_t∈[T] be a filtration, ψ:[0,λmax)→ℝ+ψ:[0, _ ) _+ be a CGF-like function. Let Stt∈[T]\S_t\_t∈[T] be a real-valued stochastic process adapted to ℱt\F_t\, Vtt∈[T]\V_t\_t∈[T] be another process adapted to ℱt\F_t\ taking values in ℝ+R_+. We say that (St,Vt)t∈[T]\(S_t,V_t)\_t∈[T] is a sub-ψ process if for all t∈[T]t∈[T] and λ∈[0,λmax)λ∈[0, _ ), there exists an ℱF-adapted supermartingale Lt(λ)t∈[T]\L_t(λ)\_t∈[T] such that Mt(λ):=exp(λSt−∑s=1tψ(λ)Vs)≤Lt(λ),a.s. M_t(λ):= (λ S_t- _s=1^tψ(λ)V_s )≤ L_t(λ), .s. Definition I.3 (Definition 6 Bakhtiari et al. 2026). A random process (St,Vt)t∈[T]\(S_t,V_t)\_t∈[T] is sub-gamma with parameter v>0v>0 if it is sub-ψ with the CGF-like function ψ(λ)=λ22(1−vλ)ψ(λ)= λ^22(1-vλ) for some v>0v>0. Lemma I.4 (Proposition 11 Bakhtiari et al. 2026). Let ℱtt∈[T]\F_t\_t∈[T] be a filtration and let (Xt)t∈[T](X_t)_t∈[T] be a real-valued stochastic process adapted to ℱF. Assume that there exists a constant b>0b>0 such that for all t∈[T]t∈[T], Xt≤[Xt|ℱt−1]+ba.s. X_t [X_t|F_t-1]+b\ a.s. Then, for St=∑s=1t(Xs−[Xs|ℱs−1]),Vt=∑s=1tVar(Xs|ℱs−1), S_t= _s=1^t(X_s-E[X_s|F_s-1]), V_t= _s=1^t (X_s|F_s-1), the process (St,Vt)t∈[T]\(S_t,V_t)\_t∈[T] is sub-gamma with parameter b/3b/3. Lemma I.5 (Theorem 10 Bakhtiari et al. 2026). For any sub-gamma process (St,Vt)t∈[T]\(S_t,V_t)\_t∈[T] with parameter v>0v>0, and any ρ>0ρ>0, δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, we have for all t∈[T]t∈[T], St≤4Vtlog(Ht/δ)+11(v+ρ)log(Ht/δ), S_t≤ 4 V_t (H_t/δ)+11(v+ρ) (H_t/δ), where Ht=log(1+Vt/ρ2)+eH_t= (1+V_t/ρ^2)+e. I.2 Other Auxiliary Lemmas Lemma I.6 (Lemma B.3, Foster et al. 2024). Let tt∈[T]\ X_t\_t∈[T] be a sequence of non-negative random variables adapted to a filtration ℱtt∈[T]\F_t\_t∈[T]. Assume that 0≤t≤R0≤ X_t≤ R almost surely for all t∈[T]t∈[T] and some constant R>0R>0. Then, for any δ∈(0,1)δ∈(0,1) and all T′≤T ≤ T, with probability at least 1−δ1-δ, we have ∑t=1T′[t|ℱt−1] _t=1^T E[ X_t|F_t-1] ≤2∑t=1T′t+8Rlog(2/δ), ≤ 2 _t=1^T X_t+8R (2/δ), ∑t=1T′t _t=1^T X_t ≤32∑t=1T′[t|ℱt−1]+4Rlog(2/δ). ≤ 32 _t=1^T E[ X_t|F_t-1]+4R (2/δ). Lemma I.7. Let μf(⋅)∝exp(f(⋅)) _f(·) (f(·)), μg(⋅)∝exp(g(⋅)) _g(·) (g(·)) be two probability distributions. Then, KL(μf∥μg)=μf[f−g]+log[μf[exp(g−f)]]. ( _f\| _g)=E_ _f[f-g]+ [E_ _f[ (g-f)] ]. Proof. Let Zf=∑xexp(f(x))Z_f= _x (f(x)), Zg=∑xexp(g(x))Z_g= _x (g(x)) be the normalization constants. Then, μf(x)=exp(f(x))Zf,μg(x)=exp(g(x))Zg. _f(x)= (f(x))Z_f,\ _g(x)= (g(x))Z_g. The KL-divergence is equal to KL(μf∥μg) ( _f\| _g) =∑xμf(x)logμf(x)μg(x) = _x _f(x) _f(x) _g(x) =∑xμf(x)[f(x)−g(x)+log(Zg/Zf)] = _x _f(x) [f(x)-g(x)+ (Z_g/Z_f) ] =μf[f−g]+log(Zg/Zf). =E_ _f[f-g]+ (Z_g/Z_f). Moreover, Zg/Zf Z_g/Z_f =∑xexp(g(x))∑xexp(f(x)) = _x (g(x)) _x (f(x)) =∑xexp(f(x))∑yexp(f(y))⋅exp(g(x)−f(x)) = _x (f(x)) _y (f(y))· (g(x)-f(x)) =μf[exp(g−f)]. =E_ _f[ (g-f)]. Thus, we complete the proof. ∎ Lemma I.8 (Stirling’s inequality). Let Γ(⋅) (·) be the gamma function. For any s>0s>0, the following inequality holds (s−12)logs−s+12log(2π) (s- 12 ) s-s+ 12 (2π) ≤logΓ(s) ≤ (s) ≤(s−12)logs−s+12log(2π)+112s. ≤ (s- 12 ) s-s+ 12 (2π)+ 112s. Lemma I.9 (Ville’s inequality). Let Xtt=0T\X_t\_t=0^T be a non-negative supermartingale. Then, for any v>0v>0, ℙ[max0≤t≤TXt≥v]≤[X0]v. [ _0≤ t≤ TX_t≥ v ]≤ E[X_0]v. Proof. Please refer to Durrett (2019). ∎ References Agarwal et al. (2023) A. Agarwal, Y. Jin, and T. Zhang VO Q l: towards optimal regret in model-free rl with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, p. 987–1063. Cited by: §2. Agarwal et al. (2024) R. Agarwal, N. Vieillard, Y. Zhou, P. Stanczyk, S. Ramos Garea, M. Geist, and O. Bachem On-policy distillation of language models: learning from self-generated mistakes. In International Conference on Learning Representations, Vol. 2024, p. 21246–21263. Cited by: §1, §2. Aminian et al. (2026) G. Aminian, A. R. Asadi, I. Shenfeld, and Y. Mroueh Kl-regularized rlhf with multiple reference models: exact solutions and sample complexity. Advances in Neural Information Processing Systems 38, p. 101117–101151. Cited by: §2. Ayoub et al. (2020) A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, p. 463–474. Cited by: §2. Bakhtiari et al. (2026) A. Bakhtiari, A. Ayoub, S. Robertson, D. Janz, and C. Szepesvári Eluder dimension: localise it!. arXiv preprint arXiv:2601.09825. Cited by: §I.1, §I.1, Definition I.1, Definition I.2, Definition I.3, Lemma I.4, Lemma I.5. Chen et al. (2025) H. Chen, N. Razin, K. Narasimhan, and D. Chen Retaining by doing: the role of on-policy data in mitigating forgetting. arXiv preprint arXiv:2510.18874. Cited by: §1, §2. Di et al. (2024) Q. Di, H. Zhao, J. He, and Q. Gu Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. In International Conference on Learning Representations, Vol. 2024, p. 4377–4410. Cited by: §2. Durrett (2019) R. Durrett Probability: theory and examples. Vol. 49, Cambridge university press. Cited by: §I.2. Foster et al. (2024) D. J. Foster, A. Block, and D. Misra Is behavior cloning all you need? understanding horizon in imitation learning. Advances in Neural Information Processing Systems 37, p. 120602–120666. Cited by: Lemma I.6, §2. Fu et al. (2026) Y. Fu, H. Huang, K. Jiang, J. Liu, Z. Jiang, Y. Zhu, and D. Zhao Revisiting on-policy distillation: empirical failure modes and simple fixes. arXiv preprint arXiv:2603.25562. Cited by: §2. Gu et al. (2024) Y. Gu, L. Dong, F. Wei, and M. Huang Minillm: knowledge distillation of large language models. In International Conference on Learning Representations, Vol. 2024, p. 32694–32717. Cited by: §2. Hong et al. (2026) H. Hong, Z. Wang, Q. Gu, and H. Wang Online kl-regularized reinforcement learning with function approximation under misspecification. arXiv preprint arXiv:2606.06053. Cited by: §2. Hou et al. (2026) W. Hou, S. Peng, W. Wang, Z. Ruan, Y. Zhang, Z. Zhou, M. Gao, Y. Chen, K. Wang, H. Yang, et al. Uni-opd: unifying on-policy distillation with a dual-perspective recipe. arXiv preprint arXiv:2605.03677. Cited by: §2. Hübotter et al. (2026) J. Hübotter, F. Lübeck, L. Behric, A. Baumann, M. Bagatella, D. Marta, I. Hakimi, I. Shenfeld, T. K. Buening, C. Guestrin, et al. Reinforcement learning via self-distillation. arXiv preprint arXiv:2601.20802. Cited by: §2, Remark 6.2. Jang et al. (2026) I. Jang, J. Yeom, J. Yeo, H. Lim, and T. Kim Stable on-policy distillation through adaptive target reformulation. In Findings of the Association for Computational Linguistics: ACL 2026, p. 42217–42227. Cited by: §2. Ji et al. (2026a) K. Ji, Q. Di, H. Zhao, Q. Zhao, and Q. Gu On the optimal sample complexity of offline multi-armed bandits with kl regularization. arXiv preprint arXiv:2605.02141. Cited by: §2. Ji et al. (2026b) K. Ji, Q. Zhao, H. Zhao, Q. Di, and Q. Gu Near-optimal regret for kl-regularized multi-armed bandits. arXiv preprint arXiv:2603.02155. Cited by: §2. Jin et al. (2025) H. Jin, S. Luan, T. Ni, S. Lyu, G. Rabusseau, R. Rabbany, D. Precup, and M. Hamdaqa Rl fine-tuning heals ood forgetting in sft. arXiv preprint arXiv:2509.12235. Cited by: §1. Jin et al. (2026) W. Jin, T. Min, Y. Yang, D. Wei, Y. Zhou, S. R. Kadhe, N. Baracaldo, and K. Lee Entropy-aware on-policy distillation of language models. arXiv preprint arXiv:2603.07079. Cited by: §2. Ko et al. (2025) J. Ko, T. Chen, S. Kim, T. Ding, L. Liang, I. Zharkov, and S. Yun Distillm-2: a contrastive approach boosts the distillation of llms. arXiv preprint arXiv:2503.07067. Cited by: §2. Ko et al. (2024) J. Ko, S. Kim, T. Chen, and S. Yun Distillm: towards streamlined distillation for large language models. arXiv preprint arXiv:2402.03898. Cited by: §2. Krichevsky and Trofimov (1981) R. Krichevsky and V. Trofimov The performance of universal encoding. IEEE Transactions on Information Theory 27 (2), p. 199–207. Cited by: §4.1. Li et al. (2026) Y. Li, Y. Zuo, B. He, J. Zhang, C. Xiao, C. Qian, T. Yu, H. Gao, W. Yang, Z. Liu, et al. Rethinking on-policy distillation of large language models: phenomenology, mechanism, and recipe. arXiv preprint arXiv:2604.13016. Cited by: §1, §2, Remark 6.4, Remark 6.6. Liu et al. (2026) Y. Liu, S. Zhang, Y. Zhang, and Q. Gu Self-distilled policy gradient. arXiv preprint arXiv:2606.04036. Cited by: §2. Lu and Lab (2025) K. Lu and T. M. Lab On-policy distillation. Thinking Machines Lab: Connectionism. Note: https://thinkingmachines.ai/blog/on-policy-distillation External Links: Document Cited by: §1. Luo et al. (2026) F. Luo, Y. Chuang, G. Wang, Z. Xu, X. Han, T. Zhang, and V. Braverman Demystifying opd: length inflation and stabilization strategies for large language models. arXiv preprint arXiv:2604.08527. Cited by: §2. Ma et al. (2026a) W. Ma, J. Wei, L. Zhao, H. Zhang, B. Xiao, L. Li, Q. Yang, B. Gao, Y. Wang, R. Li, et al. Mopd: multi-teacher on-policy distillation for capability integration in llm post-training. arXiv preprint arXiv:2606.30406. Cited by: §2, Remark 6.4. Ma et al. (2026b) Y. Ma, Z. Zhu, M. Jiang, and C. Xiao One student, many teachers: multi-task on-policy distillation via soft-prompt privileged context. arXiv preprint arXiv:2607.18293. Cited by: §2, Remark 6.2. Nayak et al. (2025) A. Nayak, T. Yang, O. Yagan, G. Joshi, and Y. Chi Achieving logarithmic regret in kl-regularized zero-sum markov games. arXiv preprint arXiv:2510.13060. Cited by: §2. Oh et al. (2026) M. Oh, S. Song, G. Choi, Y. Choi, and Y. Jo KL for a kl: on-policy distillation with control variate baseline. arXiv preprint arXiv:2605.07865. Cited by: §2. Rajaraman et al. (2021) N. Rajaraman, Y. Han, L. Yang, J. Liu, J. Jiao, and K. Ramchandran On the value of interaction and function approximation in imitation learning. Advances in Neural Information Processing Systems 34, p. 1325–1336. Cited by: §2. Rajaraman et al. (2020) N. Rajaraman, L. Yang, J. Jiao, and K. Ramchandran Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems 33, p. 2914–2924. Cited by: §2. Ross and Bagnell (2010) S. Ross and D. Bagnell Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, p. 661–668. Cited by: §2. Ross et al. (2011) S. Ross, G. Gordon, and D. Bagnell A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, p. 627–635. Cited by: §2. Russo and Van Roy (2013) D. Russo and B. Van Roy Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems 26. Cited by: §2. Shenfeld et al. (2026a) I. Shenfeld, M. Damani, J. Hübotter, and P. Agrawal Self-distillation enables continual learning. arXiv preprint arXiv:2601.19897. Cited by: §2, Remark 6.2. Shenfeld et al. (2026b) I. Shenfeld, J. Pari, and P. Agrawal Rl’s razor: why online reinforcement learning forgets less. In International Conference on Learning Representations, Vol. 2026, p. 59839–59864. Cited by: §1, §2. Song and Zheng (2026) M. Song and M. Zheng A survey of on-policy distillation for large language models. arXiv preprint arXiv:2604.00626. Cited by: §2. Sriraman et al. (2026) V. Sriraman, P. Liu, D. Hsu, and A. Block Behavior cloning is not all you need: the optimality of on-policy distillation for noisy expert feedback. arXiv preprint arXiv:2606.30923. Cited by: §1, §2. Syed and Schapire (2010) U. Syed and R. Schapire A reduction from apprenticeship learning to classification. Advances in neural information processing systems 23. Cited by: §2. Viano et al. (2026) L. Viano, A. Moulin, A. Huang, V. Cevher, P. Amortila, and D. J. Foster When does on-policy interaction help? representational tradeoffs in value-based imitation learning. arXiv preprint arXiv:2607.29617. Cited by: §1, §2. Wang et al. (2026) R. Wang, H. Wang, Y. Chen, B. Xue, T. Fang, W. Yu, and K. Wong Demystifying on-policy distillation: roles, pathologies, and regulations. arXiv preprint arXiv:2607.13399. Cited by: §2, Remark 6.4. Wang et al. (2020) R. Wang, R. R. Salakhutdinov, and L. Yang Reinforcement learning with general value function approximation: provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33, p. 6123–6135. Cited by: §2. Wu et al. (2026) D. Wu, C. Shi, J. Yang, and C. Shen Greedy sampling is provably efficient for rlhf. Advances in Neural Information Processing Systems 38, p. 108198–108232. Cited by: §2. Wu et al. (2025) Y. Wu, R. Thareja, P. Vepakomma, and F. Orabona Offline and online kl-regularized rlhf under differential privacy. arXiv preprint arXiv:2510.13512. Cited by: §2. Xiao et al. (2026) B. Xiao, B. Xia, B. Yang, B. Gao, B. Shen, C. Zhang, C. He, C. Lou, F. Luo, G. Wang, et al. Mimo-v2-flash technical report. arXiv preprint arXiv:2601.02780. Cited by: §1. Xie et al. (2026) Z. Xie, L. L. Zhang, Z. Xie, and M. Yang Trust region policy distillation. arXiv preprint arXiv:2607.04751. Cited by: §2. Xin et al. (2026) H. Xin, A. Zhao, Y. Sun, J. Li, X. Shen, and H. Xiong Escaping the kl agreement trap in on-policy distillation. arXiv preprint arXiv:2606.09471. Cited by: §2. Xing et al. (2026) X. Xing, H. Wang, B. Gao, Z. Li, and Y. Tang Trust region on-policy distillation. arXiv preprint arXiv:2606.01249. Cited by: §2. Xu et al. (2025) W. Xu, R. Han, Z. Wang, L. Le, D. Madeka, L. Li, W. Wang, R. Agarwal, C. Lee, and T. Pfister Speculative knowledge distillation: bridging the teacher-student gap through interleaved sampling. In International Conference on Learning Representations, Vol. 2025, p. 64616–64646. Cited by: §2. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §1. Ye et al. (2026) T. Ye, L. Dong, X. Wu, S. Huang, and F. Wei On-policy context distillation for language models. arXiv preprint arXiv:2602.12275. Cited by: §2. Zeng et al. (2026) A. Zeng, X. Lv, Z. Hou, Z. Du, Q. Zheng, B. Chen, D. Yin, C. Ge, C. Huang, C. Xie, et al. Glm-5: from vibe coding to agentic engineering. arXiv preprint arXiv:2602.15763. Cited by: §1. Zhang et al. (2026) D. Zhang, Z. Yang, S. Janghorbani, J. Han, A. Ressler I, Q. Qian, G. D. Lyng, S. S. Batra, and R. E. Tillman Fast and effective on-policy distillation from reasoning prefixes. In Findings of the Association for Computational Linguistics: ACL 2026, p. 25553–25569. Cited by: §2. Zhao et al. (2026a) A. Zhao, J. Tong, Y. Fan, P. Nie, W. Li, and X. Shen PowerOPD: stabilizing on-policy distillation with bounded power transformation. arXiv preprint arXiv:2606.17199. Cited by: §2. Zhao et al. (2024) H. Zhao, J. He, and Q. Gu A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. Advances in Neural Information Processing Systems 37, p. 94684–94735. Cited by: §2. Zhao et al. (2026b) H. Zhao, C. Ye, Q. Gu, and T. Zhang Sharp analysis for kl-regularized contextual bandits and rlhf. Advances in Neural Information Processing Systems 38, p. 107964–108002. Cited by: §2. Zhao et al. (2025) H. Zhao, C. Ye, W. Xiong, Q. Gu, and T. Zhang Logarithmic regret for online kl-regularized reinforcement learning. arXiv preprint arXiv:2502.07460. Cited by: §2. Zhao et al. (2026c) Q. Zhao, K. Ji, H. Zhao, and Q. Gu Fast rates for offline contextual bandits with forward-kl regularization under single-policy concentrability. arXiv preprint arXiv:2605.09214. Cited by: §2. Zhao et al. (2026d) Q. Zhao, K. Ji, H. Zhao, T. Zhang, and Q. Gu Towards a sharp analysis of offline policy learning for f-divergence-regularized contextual bandits. In International Conference on Learning Representations, Vol. 2026, p. 117176–117210. Cited by: §2. Zhao et al. (2026e) S. Zhao, Z. Xie, M. Liu, J. Huang, G. Pang, F. Chen, and A. Grover Self-distilled reasoner: on-policy self-distillation for large language models. arXiv preprint arXiv:2601.18734. Cited by: §2. Zheng et al. (2026) B. Zheng, X. Ma, Y. Liang, J. Ruan, X. Fu, K. Lin, B. Zhu, K. Zeng, and X. Cai Scope: signal-calibrated on-policy distillation enhancement with dual-path adaptive weighting. arXiv preprint arXiv:2604.10688. Cited by: §2. Zhong et al. (2026) Z. Zhong, H. Yan, J. Li, J. He, T. Zhang, and H. Li Vla-opd: bridging offline sft and online rl for vision-language-action models via on-policy distillation. arXiv preprint arXiv:2603.26666. Cited by: Remark 6.2. Zhu et al. (2026) W. Zhu, R. Xie, R. Wang, and P. Liu Hybrid policy distillation for llms. arXiv preprint arXiv:2604.20244. Cited by: §2. Ziheng et al. (2026) Z. Ziheng, J. Li, H. Tang, Y. N. Wu, and D. Terzopoulos Less is more: early stopping rollout for on-policy distillation. arXiv preprint arXiv:2605.27028. Cited by: §2, Remark 6.6.