Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds
Yunbei Xu1 Yuzhe Yuan1 Ruohan Zhan2 National University of Singapore 2 University College London [email protected] [email protected] [email protected]
arXiv:2605.12316v1 [cs.LG] 12 May 2026
1
Abstract We study the fundamental and timely problem of learning long sequences in autoregressive modeling and next-token prediction under model misspecification, measured by the joint Kullback–Leibler (KL) divergence. Our goal is to characterize how the sequence horizon H affects both approximation and estimation errors in this joint-distribution, sequence-level regime. By establishing matching upper and lower bounds, we provide, to our knowledge, the first complete characterization of long-horizon error behavior under the natural joint KL objective, with improved rates and optimality justification relative to existing work. On the approximation side, we show that joint KL admits a horizon-free approximation factor, in sharp contrast to Hellinger-based analyses that exhibit an Ω(H) dependence for computationally efficient methods; this isolates the choice of divergence as the source of approximation amplification. On the estimation side, we prove a fundamental information-theoretic lower bound of order Ω(H) that holds for both decomposable e policy classes and fully shared policies, matching the O(H) upper bounds achieved by computationally efficient algorithms. Our analysis clarifies the landscape of recent autoregressive learning results by aligning the log-loss training objective, the sequence-level evaluation metric, and the approximation metric through a sharp joint-KL oracle theory. We further show that these joint-KL guarantees imply policy learning regret bounds at rates matching prior imitation learning literature.
1
Introduction
Learning distributions over long sequences is a central problem in modern AI and in applications of large language models. Autoregressive (AR) modeling addresses this challenge by predicting the next token given the history and repeating this step to generate a full sequence. It does so by factorizing the joint distribution through conditional next-step laws, enabling likelihood-based training and principled probabilistic evaluation. This formulation has become the dominant template for sequence modeling, powering large-scale language models (Bengio et al., 2000) and naturally extending to multimodal generation (van den Oord et al., 2016), sequential density estimation (Larochelle and Murray, 2011), and model-based forecasting (Salinas et al., 2020). We formalize AR modeling as learning a policy that induces a joint distribution over length-H sequences under the maximum-likelihood objective. Here we adopt the useful dynamical-systems lens (Rohatgi et al., 2025; Hazan et al., 2025), to regard the history as a state, the next token as an ⋆ action or output, and data-generating mechanism as a policy. Formally, let π ⋆ = (π1⋆ , . . . , πH ) denote the data-generating policy for a length-H sequence S = (u1 , . . . , uH ), where πh⋆ (· | u<h ) is the ⋆ conditional law of the h-th token given its history u<h . Let P π be the induced joint distribution over S. For any candidate policy π = (π1 , . . . , πH ) ∈ Π, denote by P π the induced joint distribution. AR Preprint.
modeling exploits the sequential structure through the autoregressive factorization P π (u1:H ) =
H Y
πh (uh | u<h ) ,
u<h = (u1 , . . . , uh−1 ).
(1)
h=1
The population maximum-likelihood (equivalently, cross-entropy) objective (Goodfellow et al., 2016, §20), used explicitly in autoregressive language modeling since GPT-1 (Radford et al., 2018), aims to ⋆ minimize the expected negative log-likelihood under P π and is therefore equivalent to minimizing the joint Kullback–Leibler (KL) divergence: " H # ⋆ X min ES∼P π⋆ − log πh (uh |u<h ) ⇐⇒ min KL P π ∥ P π . (2) π∈Π
π∈Π
h=1
Accordingly, the joint-KL objective (2) is the natural target in generative modeling and sequence prediction practice; we refer to learning under this objective as autoregressive learning. Despite its practical importance, autoregressive learning is not a standard i.i.d. statistical learning problem. The joint-KL objective is a trajectory-level criterion: later prefixes are generated by earlier tokens, so the covariate distribution evolves with the horizon rather than being fixed exogenously. This endogenous sequential structure is the source of the price of long horizons studied in this paper. In this work, we study the generalization properties of autoregressive learning under misspecification, where the true policy π ⋆ may not belong to the specified policy class Π. A standard decomposition of the generalization risk of an estimator π̂ takes the form ⋆
⋆
d(P π , P π̂ ) ≤ Capx · min d(P π , P π ) + Cest · π∈Π {z } | | approximation error error
H log(|Π|/δ) + Õ( ), n {z n}
estimation error with fast rate
where n denotes the number of i.i.d. trajectory samples. Throughout, we evaluate models by their joint KL to the data-generating process as in (2), which means d(P, Q) = KL(P ∥Q) and is exactly the population objective of log-loss training. Unlike standard in-sample conditional density estimation, (2) places autoregressive learning in a distinct joint-distribution regime: the learned conditional factors are judged by the full sequence law they induce, so estimation error and misspecification accumulate through the autoregressive factorization. This raises a basic question: under joint sequence-level metrics, which horizon dependencies in approximation and estimation are intrinsic, and which are artifacts of the analysis or the metric choices? This timely question connects to recent theory on autoregressive learning, next-token prediction, and in-context learning. Motivated by the maximum-likelihood objective used in GPTs (Radford et al., 2018), early studies (Xie et al., 2022; Wies et al., 2023; Wang et al., 2023; Jiang, 2023) developed Bayesian or latent-variable interpretations of in-context learning. These works explain how autoregressive models can perform implicit inference from context, but they do not provide a misspecified joint-KL oracle theory. Building on this line, Zhang et al. (2023) formulate next-token prediction as autoregressive density estimation under joint metrics and misspecification, with their main result stated in joint total variation distance. Although joint-KL-type quantities appear in their proofs and in-context-learning consequences, their results do not yield a sharp estimation– approximation decomposition for joint KL metric. Relatedly, Yüksel and Flammarion (2025) obtain KL-type guarantees for log-loss training of autoregressive processes, but their approximation term is measured by a worst-case total-variation criterion rather than by the joint KL metric used for evaluation. None of these works develops lower bounds or an optimality theory that distinguishes how horizon dependence changes across different structural restrictions on the policy class. A second line studies autoregressive and imitation learning under squared Hellinger distance through the minimax-optimality lens. Foster et al. (2024a) analyze log-loss training for general behavior cloning and obtain finite-sample guarantees that imply multi-step control under Hellinger-type evaluation, with autoregressive learning as a special case. Rohatgi et al. (2025) focus more directly on misspecified autoregressive learning and show that, under squared Hellinger evaluation, computationally tractable algorithms can suffer an Ω(H) amplification of approximation error. These lower bounds are highly informative, but these results also suggest that the horizon behavior of autoregressive learning is metric-dependent. Squared Hellinger does not coincide with the population objective induced by log-loss training, and its pseudo-chain-rule behavior leads to a different approximation 2
Approximation error KL divergence (our results)
Θ(1)
Squared Hellinger distance (Rohatgi et al. (2025))
Θ(H)
Estimation error Decomposable class H log H|Π| O n H log |Π| Θ n
Fully-shared class |Π| Θ H log n Θ logn|Π|
Table 1.1: Summary of scaling behaviors in sequence horizon H and sample size n
story from the exact KL chain-rule decomposition studied here. Our work gives a sharp joint-KL analysis in a general autoregressive learning setting. Both the evaluation risk and the approximation error are measured in the same joint-KL metric, so the result directly characterizes the population objective corresponding to next-token log-loss training. We provide upper and lower bounds for both approximation and estimation, and treat both fully-shared and decomposable policy classes. Our work provides a unified answer by developing a sharp horizon scaling map for misspecified autoregressive learning under log-loss. At a high level, Table 1.1 summarizes the canonical behaviors of approximation and estimation under joint KL versus squared Hellinger, and clarifies how sharing across steps affects the statistical term. With this picture in place, we can state the main contributions. 1.1
Main Results and Takeaways
We summarize our main results and takeaways below; proofs and extensions are deferred to the appendix. • Clarifying the KL formulation in the joint-distribution-level regime. We study the new joint-distribution-level regime of autoregressive learning and organize how prior work has approached this paradigm under TV-, Hellinger-, and KL-type analyses. By disentangling the training objective, sequence-level evaluation metric, and approximation metric, we further clarify the relationships among existing results and identify joint KL as the metric-aligned formulation for log-loss training. • Misspecified guarantees under joint KL (and what drives horizon effects). We establish a sharp misspecified generalization guarantee for log-loss, showing that the approximation ratio satisfies Capx = O(1) under the joint KL objective. In particular, in contrast to the Ω(H) barrier under squared Hellinger distance (Rohatgi et al., 2025), this shows that horizon growth in Capx is a divergence-induced phenomenon rather than an inherent limitation of autoregressive factorization (see Theorem 3.1). • Algorithmic upper bounds under joint KL. We analyze ERM and Bayesian posterior learners and derive joint-KL generalization bounds with estimation ratio Cest = Õ(H). The bounds make explicit the tradeoff between approximation and estimation across two canonical policy-class regimes (decomposable versus fully shared), and we extend the analysis to a broad family of dependent policy classes that capture cross-step coupling common in practice (see Section 3.2). The bounds further imply rollout-level policy learning guarantees to be highlighted below (see also Section 5). • Information-theoretic lower bounds (unavoidable linear horizon dependence). Using a Fano-type construction, we prove that Cest must scale at least as Ω(H) under joint KL (see Theorem 4.2), even for structured classes, showing that the linear horizon dependence in our upper bounds is unavoidable up to logarithmic factors. This refines the interpretation of “error amplification”: under log-loss, the fundamental obstruction is statistical rather than approximation-driven. Two points are worth highlighting in more details: Advantages of KL over Hellinger in our setting. Our analysis and accompanying insights point to two reasons to favor KL over the squared Hellinger distance adopted in Rohatgi et al. (2025). First, since estimation error can be significantly reduced with larger sample size n, it is preferable for any horizon dependence H to appear in the estimation term rather than the approximation term; comparing the first two rows of Table 1.1 shows that our KL-based formulation yields the more favorable rate in 3
this regime. Second, joint KL aligns with the canonical objective in modern generative modeling and large language model training (Ermon, 2023; Radford et al., 2018). Policy learning guarantee. Our joint-KL bounds translate directly into rollout-level policy learning guarantees: by Pinsker’s √ inequality, they control the worst-case return gap over bounded trajectory rewards at the usual · order. Hence joint KL matches the rollout control order obtained from squared Hellinger distance, while preserving our estimation–approximation separation.
2
Problem Setting ⋆
∗ Let π ∗ = (π1∗ , . . . , πH ) denote the data-generating model and P π be the induced joint distribution ⋆ over length-H token sequences. Given n i.i.d. samples (S1 , · · · , Sn ), where each sequence Si ∼ P π consists of tokens {ui1 , · · · , uiH }, our goal is to learn a model π from a pre-specified class Π that best approximates π ∗ in KL divergence: ⋆ min KL P π ∥ P π . (2) π∈Π
In particular, we allow for model misspecification π ∗ ∈ / Π. Our objective is therefore to characterize both the approximation error induced by restricting to Π and the estimation error arising from finite-sample statistical learning. Denote by sh = u<h the length-(h − 1) prefix, and write π = (π1 , ..., πH ) for a sequence model. We adopt a widely used assumption of bounded log density (Xie et al., 2022; Rohatgi et al., 2025). Assumption 1 (Boundedness of log density). π ∗ (xh |sh ) ≤ G. sup sup sup log h πh (xh |sh ) π∈Π h∈[H] sh We distinguish between two structural regimes for the policy class Π. Decomposable policy classes (no parameter sharing). In the decomposable regime, often called no parameter sharing in prior work (e.g., Foster et al., 2024a; Rohatgi et al., 2025) and motivated by horizon-specific parameterizations practice (e.g., Sabbaghi et al., 2024), the model class factorizes across time, so each step admits its own independent conditional component. Concretely, the class factorizes across the horizon as Π = Π1 × · · · × ΠH , where Πh denotes the set of admissible conditional distributions at step h. For ease of presentation, we focus on the homogeneous setting in which the per-step classes coincide, Π1 = · · · = ΠH =: Π0 , so that Π = ΠH . Note that heterogeneous per-step classes (Πh )H 0 h=1 can always be reduced to this SH homogeneous form by taking the lifted base class Π0 := h=1 Πh . More generally, one may consider policy classes that do not decompose across steps, i.e., classes satisfying only Π ⊆ ΠH 0 . We defer the analysis of such dependent (non-decomposable) classes to Section 3.2. Fully-shared policy classes (parameter sharing). A second regime of primary interest is the fully shared (or consistent) policy class, obtained by tying the same policy component across all horizons. This restriction is analytically cleaner and is adopted in prior joint-metric analyses (Zhang et al., 2023; Yüksel and Flammarion, 2025). Formally, this class is given by Πcons := π = (π0 , . . . , π0 ) ∈ ΠH 0 : π0 ∈ Π0 , so that πh ≡ π0 for all h ∈ [H] and Πcons ⊆ ΠH 0 . This regime captures the canonical parametersharing structure in autoregressive model training (e.g., the original Transformer), while still allowing the induced joint distribution P π to exhibit long-range dependence through the evolving history u<h .
3
Upper Bounds of Autoregressive Learning in Joint KL
3.1
Joint-KL Guarantees: Constant Approximation and an Estimation Barrier
Two canonical log-loss-aligned learners: ERM and Bayesian posterior. We begin by studying two classical learners for next-token prediction under the log-loss, both directly aligned with the joint 4
KL objective in (2). The first is empirical risk minimization (ERM), which outputs any minimizer of the empirical negative log-likelihood: n
H
1 XX π̂ ∈ arg min − log πh (uih | ui<h ). π∈Π n i=1
(3)
h=1
This is the canonical training paradigm for modern language models: Transformer pretraining is precisely maximum-likelihood learning over large text corpora. As a complementary baseline, we also consider a Bayesian posterior (exponential-weights) learner, which aggregates hypotheses according to their empirical log-likelihood. Concretely, starting from a prior over Πh , the per-step posterior after observing n trajectories yields a mixture predictor X π̂h (· | sh ) ∝ qh (πh ) πh (· | sh ), (4) πh ∈Πh n Q
where qh is the posterior weight updated from the prior by the empirical likelihood
i=1
πh (uih |ui<h ).
This learner is also natural under log-loss, in light of the classical mixability viewpoint in online conditional density estimation. We next show that both learners admit oracle-type guarantees under joint KL in the misspecified regime, with horizon-free approximation and horizon-dependent estimation terms. Throughout this paper, we use the notation f ≲ g to mean that there exists an absolute constant c > 0 such that f ≤ c · g. iid
⋆
Theorem 3.1 (ERM and Bayesian Posterior under joint KL). Let S1 , . . . , Sn ∼ P π with π ⋆ ∈ / Π, where Π is a finite decomposable model class. Under Assumption 1, ERM algorithm (3) and Bayesian Posterior algorithm (4) guarantees that for any δ ∈ (0, 1) and any ε > 0, with probability at least 1 − δ, ⋆ ⋆ (1 + ε)2 (HG + 1) log(H|Π0 |δ −1 ) KL(P π ∥P π̂ ) ≲ (1 + ε) min KL(P π ∥P π ) + . π∈Π ε {z n } | {z } |
(5)
estimation error
approximation error
For fully shared model class Πcons , the result would be ⋆ ⋆ (1 + ε)2 (HG + 1) log(|Π0 |δ −1 ) KL(P π ∥P π̂ ) ≲ (1 + ε) min KL(P π ∥P π ) + . π∈Πcons ε {z n } {z } | |
(6)
estimation error
approximation error
The two regimes trade off approximation and estimation: since Πcons ⊂ Π, the decomposable class can only reduce the approximation term, while its estimation term differs from the shared case only by an additional log H factor. The first terms in (5) and (6) show that the approximation error do not amplify with the horizon (i.e., ⋆ sequence length): the approximation ratio Capx on min KL(P π ∥P π ) is (1 + ε), independent of H. π∈Π
Comparison and technical distinction relative to Hellinger analyses Rohatgi et al. (2025). The reason why joint KL can achieve horizon independent approximation ratio comes from the exact chain rule for KL, which decomposes the joint KL into a sum of conditional KLs along the sequence: H ⋆ X h i KL P π , P π̂ = Esh ∼P π⋆ (u<h ) KL πh⋆ (· | sh ), π̂h (· | sh ) . h=1
By contrast, the squared Hellinger distance satisfies only a pseudo chain rule. A convenient form is H hX i ⋆ 1 2 π⋆ π̂ 2 2 DH P , P ≤ Esh ∼dπ⋆ (u<h ) DH πh⋆ (· | sh ), π̂h (· | sh ) ≤ H DH P π , P π̂ , h 7 h=1
see, e.g. (Foster et al., 2024b). Consequently, stepwise Hellinger analyses incur a linear in H factor, explaining the Ω(H) dependence reported in prior work Rohatgi et al. (2025), whereas the KL chain rule prevents such amplification. This clarifies that the Ω(H) growth is a metric-induced artifact. 5
The proof techniques are also distinct. Their analysis exploits a sequence-level log-loss–Hellinger relation, together with boundedness and the triangle inequality, which simplifies dependence analysis but is specific to Hellinger and leads to the decomposable/shared-class gap reported in Table 1.1; see the discussion around (10). Our joint-KL analysis must instead track prefixes and union-bound across horizons explicitly. Theorem 3.1 shows that, even under this sharper metric, decomposable classes incur only H log H, rather than the naive H 2 , horizon dependence. Improvements over TV and KL analyses Zhang et al. (2023); Yüksel and Flammarion (2025). Zhang et al. (2023) state their main guarantee in joint total variation. Since Pinsker converts KL to TV only at square-root scale, a TV guarantee derived from log-loss complexity naturally yields an n−1/2 -type rate, whereas direct joint-KL analysis can retain the n−1 -type oracle rate under standard bounded log-loss conditions. It is also useful to compare Theorem 3.1 with Yüksel and Flammarion (2025). Their Theorems 3.4 and 3.5 correspond closely to Step 1 and Step 2 in our proof sketch, but their approximation term is measured in worst-case total variation, which is not a joint metric: Eapp ≲ G · inf
π∈Π
H X h=1
sup TV (πh⋆ (·|sh ), πh (·|sh )) sh
Even strengthening their analysis to sequence-level TV would not give a sharp oracle bound in the evaluation metric we use, namely joint KL. By basic inequalities, under Assumption 1 we have "H # X p ⋆ π ⋆ KL(P ∥P ) ≲ G · EP π⋆ TV(πh (·|sh ), πh (·|sh )) ≲ G HKL(P ⋆ ∥P π ), h=1
showing that even a sequence-level TV approximation would yield horizon dependence in worst case. Moreover, applying the bounds of Zhang et al. (2023); Yüksel and Flammarion (2025) to decomposable classes leads to a naive H 2 -level estimation term. Our ERM and posterior bounds instead scale linearly in H, again up to logarithms. This advantage is relevant for horizon- or position-dependent parameterizations used in practice (Sabbaghi et al., 2024). Core proof ideas. The argument first proves a prefix-conditioned oracle inequality for the one-step log-loss at each fixed step h and prefix sh . For ERM this uses a Bernstein-type concentration argument, while for the Bayesian posterior it follows from the mixability of log-loss. We then average these local inequalities over the random prefixes generated by the data; a Freedman-type martingale bound controls the deviation between this empirical prefix average and its population counterpart. The exact KL chain rule then converts the stepwise control into the desired joint-KL bound. In particular, for decomposable classes, the stepwise argument requires uniform control only over the coordinate-wise index set {(h, πh ) : h ∈ [H], πh ∈ Π0 }, yielding the log(H|Π0 |) factor instead of the complexity of the full product class, improving the naive H 2 -horizon dependence to H log H. On the impossibility of Capx = 1 high-probability bounds. It is natural to ask whether the Bayesian posterior can satisfy a high-probability oracle inequality under joint KL with leading constant 1 on the misspecification term and only a complexity-dependent remainder. While mixability of log-loss can deliver such sharpness at the prefix-conditioned level (Step 1), it does not extend through the averaging-over-prefixes step needed to control the joint objective (Step 2). As a result, sharp highprobability bounds under joint KL cannot generally be achieved. The following theorem formalizes this impossibility in the misspecified regime, for any learner. Theorem 3.2 (No Capx = 1 high-probability oracle bound under joint KL). There exist absolute constants c > 0 and δ0 ∈ (0, 1) such that the following holds. For any H, n ∈ N, one can construct a misspecified data-generating policy π ⋆ and a base class Π0 satisfying Assumption 1 such that for n o Π ∈ ΠH , Π := {(π , . . . , π ) : π ∈ Π } , cons 0 0 0 0 0 every (possibly randomized) learner outputting π̂ ∈ Π from n i.i.d. trajectories satisfies ⋆ ⋆ H Pr KL P π P π̂ ≥ inf KL P π P π + c √ ≥ δ0 . (7) π∈Π n In particular, a sharp high-probability oracle inequality with leading constant 1 and only a e O(H log |Π0 |/n) remainder is impossible in the misspecified regime. 6
3.2
Improper Learning via Lifting the Policy Space
We now turn to the more general dependent regime, where the feasible set of stepwise conditionals is coupled across the horizon: Π ⊆ Π1 × · · · × ΠH . Without loss of generality, we take each Πh to be the minimal induced marginal class Πh := {πh : π ∈ Π}, so Πh is exactly the collection of step-h conditionals realizable by some π ∈ Π. Such dependencies naturally arise from parameter sharing, nonconvex architectural constraints, or combinatorial structures, and they prevent choosing (π1 , . . . , πH ) independently. Here in our discussion, “computational efficiency” is used in the specific sense of avoiding the horizon-dependent planning inefficiency highlighted in Section 3 of Rohatgi et al. (2025). Proper learning: coupled search and an H 2 statistical barrier. A proper learner must output a single hypothesis π̂ ∈ Π. When Π is dependent, this requirement couples all H components, so even evaluating or optimizing the empirical log-loss over Π becomes a global structured selection problem over exponentially many joint configurations, which is computationally inefficient in general. Even if one ignores computation and allows an arbitrary proper selector over Π, the joint log-loss aggregates along the trajectory and its effective range and dependence structure can scale with the horizon. As a consequence, proper learning in dependent classes can suffer an intrinsic estimation barrier of order Ω(H 2 ) under joint KL (see Corollary 1 in Appendix), reflecting that long-horizon coupling amplifies statistical uncertainty at the trajectory level. Lifting: tractable stepwise learning with linear horizon scaling. We therefore relax properness SH by lifting the search space to the stepwise product class Π̃ := ΠH 0 where Π0 := h=1 Πh is the marginal union class. Learning in the lifted space Π̃ enables stepwise ERM or Bayesian posterior updates, which are computationally tractable, and yields an O(H)-type estimation term of order Õ(H log |Π0 |/n). The following lemma relates the sizes of Π and Π0 , allowing a direct comparison between the lifted and proper regimes. SH Lemma 1. For any Π ⊂ Π1 × · · · × ΠH where Πh := {πh : π ∈ Π}, writing Π0 := h=1 Πh , we have that: log |Π0 | ≤ log |Π| + log H log |Π| ≤ H log |Π0 | Therefore, the estimation-error gain from using the lifted class is sandwiched asf H2 ≳
H 2 log |Π| H log |Π| ≳ , H log |Π0 | log |Π| + log H
so the gain is on the order of a factor ranging from H to H 2 in the horizon (modulo logarithms), at the cost of learning in the lifted space. We summarize the computational and statistical gain by lifting as the following theorem. Theorem 3.3. With Π̃ = ΠH 0 as above, stepwise ERM or Bayesian posterior updates are computationally tractable and achieve only Õ(H log |Π0 |/n) estimation, while any proper learner over a dependent class Π can incur Ω(H 2 log |Π|/n) estimation under joint KL. By Lemma 1, optimizing over the lifted space corresponds to an H-to-H 2 (up to a log term) gap in horizon dependence.
4
Lower Bounds of Autoregressive Learning in Joint KL
In this section we discuss error amplification from both the approximation and estimation perspectives. To facilitate a clean comparison across metrics, we still assume that the candidate policy space is identical across steps and focus on two representative cases: decomposable classes and fully shared classes. In particular, Theorem 4.2 provides the paper’s main lower bound. This is a central contribution, as it identifies the intrinsic horizon-dependent statistical cost of autoregressive learning and clarifies the fundamental limits of earlier upper-bound analyses. Approximation-side error amplification. As discussed earlier, squared-Hellinger analyses imply that any computationally efficient procedure may suffer an approximation ratio scaling as Capx = 7
Ω(H) in long-horizon AR modeling. Here we interpret this phenomenon through the lens of error ⋆ amplification. The best-in-class misspecification level inf π∈Π d(P π , P π ) typically grows with H simply because matching a length-H joint distribution becomes progressively harder. An Ω(H) inflation in Capx therefore amplifies this horizon-growing approximation gap into a much larger sequence-level error, echoing the classical compounding-error intuition from imitation learning. Our results show that this approximation-side amplification can be metric-induced: switching to joint KL removes the Ω(H) blow-up in the approximation ratio, so the amplification is not an inherent feature of sequential prediction but a consequence of the evaluation criterion. Estimation-side error amplification on KL divergence. We now focus on the statistical term and make the dependence on the policy class structure explicit. For squared Hellinger distance, there is a standard guarantee for its estimation error. Here we list the result in the realizable case, same results of estimation error also applied to misspecified case. Theorem 4.1 (Foster et al. (2024a) Proposition 2.1). Fix any expert π ⋆ ∈ Π. Let π̂ be the output of the ERM algorithm (3). Then for any δ ∈ (0, 1), with probability at least 1 − δ, log |Π| δ −1 ⋆ 2 DH P π̂ , P π ≤ 2 . (8) n This result is particularly informative in our setting because log |Π| faithfully reflects whether the class shares parameters across steps. Indeed, if Π = ΠH 0 , which represent the no parameter sharing case, then log |Π| = H log |Π0 | and 8 yields an estimation rate of order H log |Π0 |/n. If instead Π is fully shared, then |Π| = |Π0 | and the rate improves to log |Π0 |/n. In this sense, squared Hellinger can distinguish whether we are effectively selecting H independent hypotheses or reusing a single hypothesis throughout the horizon. However, this structural “discount” from sharing does not persist in the misspecified regime under KL. The main reason is captured by the following lower bound result. Theorem 4.2. There exist absolute constants c, c0 > 0 such that for any |Π| ≥ 4, any n ≥ c0 log |Π|, any horizon H ∈ N, and any G ∈ (0, 1], one can construct a finite decomposible policy class Π and associated distributions {P π }π∈Π on a finite sample space such that for every selector iid
⋆
π̂ = π̂(S1:n ) ∈ Π based on S1 , . . . , Sn ∼ P π where π ⋆ ∈ Π, h ⋆ i H G2 log |Π| inf sup EP π⋆ KL P π P π̂ ≥ c . π̂∈Π π ⋆ ∈Π n
(9)
In particular, although Theorem 4.2 is stated under realizability, its implication for misspecification is immediate. For the decomposable regime, enlarging the oracle family can only enlarge the supremum, hence the minimax risk (and the lower bound) cannot decrease. Moreover, passing to a fully-shared subclass only restricts the learner (shrinks the set in the infimum) and does not constrain the oracle; under misspecification it is natural that π ⋆ lies in the enlarged decomposable family while violating sharing. Therefore, under misspecification, KL necessarily retains an H-linear estimation dependence in both decomposable and fully-shared cases: even with full sharing, the statistical term scales as H log |Π0 |/n. The lower bound also explains a key difference between the joint-KL setting and the squared-Hellinger setting summarized in Table 1.1. The distinction is most visible for fully-shared model classes. A central reason is that the estimation term for a fully-shared class can be horizon-free because the proof exploits a special log-loss/Hellinger relationship(Rohatgi et al., 2025). Roughly, exponential-tail control of the log-likelihood ratio can be combined with the triangle inequality ⋆ ⋆ ⋆ 4 log(|Π|/δ −1 ) 2 2 2 2 DH (P π̂ , P π ) ≤ 2DH (P π̂ , P π̄ ) + 2DH (P π̄ , P π ) ≤ + L̂(P π̄ ) − L̂(P π ) . n n (10) b denotes the empirical trajectory-level log-loss. Since this comparison is made at the level Here L of the induced joint distributions, the resulting complexity term depends on the shared policy class as a whole, rather than on a uniform control over horizon-indexed conditional components. This is exactly why their analysis exhibits the striking statistical gap between decomposable and fully shared classes; see Table 1.1 of our paper. 8
However, this horizon-free behavior is specific to the log-loss/squared-Hellinger analysis and does not carry over to joint KL. Under joint KL, the risk itself decomposes along the autoregressive sequence, so horizon-wise statistical accumulation cannot be avoided simply by imposing a fully-shared policy class. Our lower bound makes this point precise: even in the fully-shared regime, the estimation error must scale linearly with H. Thus the H-dependence in our joint-KL bounds reflects an intrinsic statistical difficulty of autoregressive learning, rather than an artifact of using decomposable classes or of a loose horizon-wise union bound. Summary of error amplification under Hellinger and KL analyses. To summary, Hellinger and KL exhibit different error amplification behaviors: Hellinger amplifies primarily through the approximation side, while KL shifts the horizon dependence to the estimation side. Since estimation error can be diluted by increasing the sample size n, this makes KL a particularly meaningful and practice-aligned metric despite its H-linear statistical accumulation.
5
From Joint KL Guarantees to Policy Learning Regret Bounds
Autoregressive generation can also be viewed as a policy-learning problem: a policy maps each prefix sh to a distribution over the next token, and hence induces a distribution P π over entire rollouts. This is the same object that appears in imitation learning (more details may refer to (Foster et al., 2024a)), where one compares the rollout distribution of a learned policy with that of an expert policy. To make this connection explicit, let J(π; r) := Eτ ∼P π [r(τ )] denote the expected return of policy π under a trajectory-level reward function r. We call r R-bounded if |r(τ )| ≤ R for all trajectories τ , and for simplicity take R = 1. For the standard imitation-learning formulation, the worst-case, sequence-level regret can be bounded by joint TV as the following: sup
⋆
{J(π ⋆ ; r) − J(b π ; r)} = DTV (P π , P πb ).
r: 1-bounded
Thus controlling the trajectory-level total variation distance is exactly equivalent to controlling the worst-case return gap over bounded rewards. Our joint-KL guarantee fits directly into this policy-learning objective. Indeed, Pinsker’s inequality immediately yields a rollout-control guarantee for the corresponding imitation-learning problem: r 1 ⋆ sup {J(π ; r) − J(b π ; r)} ≤ KL(P π⋆ ∥P πb ). 2 r: 1-bounded Thus our bound provides a direct rollout-control√guarantee for the corresponding policy-learning problem. At this level, joint KL yields the same ·-order guarantee as squared Hellinger distance, since trajectory-level Hellinger control is also converted to total variation through a square-root comparison (See Theorem 3.1, (Foster et al., 2024a)). This perspective clarifies that the joint-KL objective is not merely a next-token prediction surrogate: it is strong enough to control the rollout distribution induced by the learned policy. It also preserves the main estimation–approximation message of our analysis: approximation does not amplify with the horizon, while the linear horizon dependence in estimation is intrinsic under misspecification.
6
Conclusion
We studied misspecified autoregressive learning through the lens of joint KL divergence. We show that joint KL admits a horizon-free approximation, which implies that the Ω(H) approximation blowup under squared Hellinger can be metric-induced. At the same time, our analysis reveals a genuine Ω(H) estimation barrier for proper learners for joint KL, and show that using horizon-dependent decomposable parameterization would not increase the horizon dependence despite logarithms. We further propose an improper Bayesian posterior learner over a lifted policy space that is computationally tractable. Finally, we extend the autoregressive density estimation results to rollout-level policy learning guarantees. A natural direction for future work is to use this framework to study LLM-specific settings, including pre-training, in-context learning, and alignment, and to extend our results to transformer architectures and more realistic policy classes. 9
References Bengio, Y., Ducharme, R., and Vincent, P. (2000). A neural probabilistic language model. In Leen, T., Dietterich, T., and Tresp, V., editors, Advances in Neural Information Processing Systems, volume 13. MIT Press. Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Gordon, G., Dunson, D., and Dudík, M., editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 19–26, Fort Lauderdale, FL, USA. PMLR. Ermon, S. (2023). Course notes in cs https://deepgenerativemodels.github.io/syllabus.html.
236
deep
generative
modeling.
Foster, D. J., Block, A., and Misra, D. (2024a). Is behavior cloning all you need? understanding horizon in imitation learning. Advances in Neural Information Processing Systems, 37:120602– 120666. Foster, D. J., Han, Y., Qian, J., and Rakhlin, A. (2024b). Online estimation via offline estimation: An information-theoretic framework. Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487. Goodfellow, I., Bengio, Y., Courville, A., and Bengio, Y. (2016). Deep learning, volume 1. MIT press Cambridge. Hazan, E., Shwartz, S. S., and Srebro, N. (2025). Research program: Theory of learning in dynamical systems. Jiang, H. (2023). A latent space theory for emergent abilities in large language models. arXiv preprint arXiv:2304.09960. Larochelle, H. and Murray, I. (2011). The neural autoregressive distribution estimator. In Gordon, G., Dunson, D., and Dudík, M., editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 29–37, Fort Lauderdale, FL, USA. PMLR. Mehta, N. (2017). Fast rates with high probability in exp-concave statistical learning. In Singh, A. and Zhu, J., editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1085–1093. PMLR. Radford, A., Narasimhan, K., Salimans, T., Sutskever, I., et al. (2018). Improving language understanding by generative pre-training. OpenAI blog. Rohatgi, D., Block, A., Huang, A., Krishnamurthy, A., and Foster, D. J. (2025). Computationalstatistical tradeoffs at the next-token prediction barrier: Autoregressive and imitation learning under misspecification. Sabbaghi, M., Pappas, G., Hassani, H., and Goel, S. (2024). Explicitly encoding structural symmetry is key to length generalization in arithmetic tasks. arXiv preprint arXiv:2406.01895. Salinas, D., Flunkert, V., Gasthaus, J., and Januschowski, T. (2020). Deepar: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting, 36(3):1181–1191. van den Oord, A., Kalchbrenner, N., and Kavukcuoglu, K. (2016). Pixel recurrent neural networks. In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1747–1756, New York, New York, USA. PMLR. Wang, X., Zhu, W., Saxon, M., Steyvers, M., and Wang, W. Y. (2023). Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning. Advances in Neural Information Processing Systems, 36:15614–15638. 10
Wies, N., Levine, Y., and Shashua, A. (2023). The learnability of in-context learning. Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2022). An explanation of in-context learning as implicit bayesian inference. Yüksel, O. K. and Flammarion, N. (2025). Generalization bounds for autoregressive processes and in-context learning. In EurIPS 2025 Workshop on Principles of Generative Modeling (PriGM). Zhang, Y., Zhang, F., Yang, Z., and Wang, Z. (2023). What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization. arXiv preprint arXiv:2305.19420.
11
Contents 1
Introduction
1
1.1
3
Main Results and Takeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Problem Setting
4
3
Upper Bounds of Autoregressive Learning in Joint KL
4
3.1
Joint-KL Guarantees: Constant Approximation and an Estimation Barrier . . . . .
4
3.2
Improper Learning via Lifting the Policy Space . . . . . . . . . . . . . . . . . . .
7
4
Lower Bounds of Autoregressive Learning in Joint KL
7
5
From Joint KL Guarantees to Policy Learning Regret Bounds
9
6
Conclusion
9
A Proofs of Theorem 3.1 (Main Upper Bound)
12
A.1 Proofs for step 1: prefix-conditioned control . . . . . . . . . . . . . . . . . . . . .
13
A.2 Proofs for step 2: averaging over random prefixes . . . . . . . . . . . . . . . . . .
15
A.3 Proofs of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
B Proof of Theorem 4.2 (Main Lower Bound)
18
C Missing proofs in Section 3
21
D Technical Tools
22
E Impact Statement and Limitations
23
A
E.1 Broader Impacts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
E.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
Proofs of Theorem 3.1 (Main Upper Bound)
We prove a generalization of Theorem 3.1 that allows for an infinite policy class via a log-ratio covering argument. The finite-class case is recovered by setting r = 0. Definition A.1 (Log-ratio cover). Fix a policy class Π0 . For r > 0, we say that Π′ ⊂ Π0 is an r-cover of Π0 if for each π ∈ Π0 , there is some π ′ ∈ Π′ with log(π(xh |uh )/π ′ (xh |uh )) ≤ r for any xh and uh . We write Nlog (Π0 , r) to denote the cardinality of the smallest r-cover of Π0 . The definition here is standard and widely used (Foster et al., 2021; Rohatgi et al., 2025). The proof consists of two ingredients. The first is a prefix-conditioned control. Fix a step h and consider the random prefixes {sih }ni=1 induced by the trajectories. The goal is to bound the empirical conditional KL of the learner in terms of any conditional comparator π̄h within the class (up to a complexity term), namely to control n n 1X 1X ⋆ i i KL πh (· | sh ) ∥ π̂h (· | sh ) − (1 + ε) KL πh⋆ (· | sih ) ∥ π̄h (· | sih ) . n i=1 n i=1 12
For ERM, this bound is proved in Lemma 2. For the Bayesian posterior learner, the analogous prefix-conditioned bound is proved in Lemma 3. The second ingredient is an averaging over random prefixes bound, which connects the empirical average over visited prefixes to the population quantity in the chain rule. Concretely, the goal is to control the deviation n H H h X i 1 XX Esh ∼P π⋆ KL πh⋆ (· | sh ) ∥ πh (· | sh ) − (1 + ε) KL πh⋆ (· | sih ) ∥ πh (· | sih ) , n i=1 h=1
h=1
uniformly over π in the policy class. This step is shared by both ERM and the Bayesian posterior and is proved in Lemma 4. Combining the two ingredients and, moreover, using a Freedman-type deviation bound (Lemma 7) to control the empirical-to-population gap n 1X KL πh⋆ (· | sih ) ∥ π̄h (· | sih ) − (1 + ε)ES∼P π⋆ KL πh⋆ (· | sh ) ∥ π̄h (· | sh ) , n i=1 yields Theorem 3.1. A.1
Proofs for step 1: prefix-conditioned control iid
⋆
Lemma 2 (prefix-conditioned control for ERM). Let S1 , . . . , Sn ∼ P π with π ⋆ ∈ / Π = ΠH 0 or Πcons , where Π0 has a finite log-ratio cover. Under assumption 1, ERM algorithm guarantees that for any δ ∈ (0, 1) and any ε > 0, with probability at least 1 − δ, for all π̄h : n H n H 1 XX 1 XX KL πh⋆ (· | si1:h−1 ) ∥ π̂h (· | si1:h−1 ) ≤ (1 + ε) KL πh⋆ (· | si1:h−1 ) ∥ π̄h (· | si1:h−1 ) n i=1 n i=1 h=1 h=1 log Nlog (Π0 , r) δ −1 C + C ′ Hr, + H(G + 1) ε n for universal constants C, C ′ .
Proof of Lemma 2: Fix r > 0 and let Πr ⊂ Π be an r-cover in the sense of Definition A.1. For each π ∈ Π, pick a representative π r ∈ Πr such that for every length-h trajectory (uh , s1:h−1 ), log
π(uh | s1:h−1 ) ≤ r. π r (uh | s1:h−1 )
(11)
We prove the result for a single step and then sum up them. For any π ∈ Π0 , define H
π ⋆ (· | s1:h−1 ) 1 X log h , H π(· | s1:h−1 ) h=1 µ(π; s1:h−1 ) := Euh ∼πh⋆ (·|s1:h−1 ) Y (π; s1:h−1 ) = KL πh⋆ (· | s1:h−1 ) ∥ π(· | s1:h−1 ) ,
Y (π; s1:h−1 ) :=
n
µ̂(π; s1:h−1 ) :=
1X Yi (π; s1:h−1 ). n i=1
For notational convenience, write µπ for µ(π; s1:h−1 ) and define µ̂π analogously. Let π̄ be any fixed policy in the class, and denote by π̄ r ∈ Πr its representative. We use Lemma 5 to obtain the Bernstein condition. From EP π⋆ [e−Y ] = 1 and |Y | ≤ G, we have Var(Y ) ≤ V (G) µ with V (G) = 4 + 4G. Hence, by the two-sided Bernstein inequality, for any δg ∈ (0, 1), with probability at least 1 − δg , r 2V (G) µ log(1/δg ) 4G log(1/δg ) |µ − µ̂| ≤ + . (12) n 3 n Apply (12) simultaneously to all π ′ ∈ Πr and to π̂r ∈ arg min µ̂π′ . ′ π ∈Πr
13
By a union bound with δg = δ/|Πr |, with probability at least 1 − δ the following holds for all π ′ ∈ Πr : b r (π ′ ) + ar √µπ′ + √µπ̄r + 2br , ∆r (π ′ ) ≤ ∆ (13) where ∆r (π ′ ) := µπ′ − µπ̄r ,
b r (π ′ ) := µ̂π′ − µ̂π̄r , ∆
and r ar :=
2V (G) log(|Πr |δ −1 ) , n
br :=
4G log(|Πr |δ −1 ) . 3 n
By (11), we have |Y (π) − Y (π r )| ≤ r ⇒ |µπ − µπr | ≤ r, |µ̂π − µ̂πr | ≤ r. Since π̂ is an ERM over Π0 and Πr ⊂ Π0 , (14) implies min µ̂π′ ≥ min µ̂π − r = µ̂π̂ − r, µ̂π̂r ≤ µ̂π̂ + r, ′ π ∈Πr
(14)
π∈Π
and therefore b r (π̂ r ) = µ̂π̂r − µ̂π̄r ≤ 2r. ∆
(15)
√ √ √ Applying (13) with π ′ = π̂ r and using µπ̂r = ∆r (π̂ r ) + µπ̄r together with x + y ≤ x + y, we obtain p √ ∆r (π̂ r ) ≤ ar ∆r (π̂ r ) + 2 µπ̄r + 2br + 2r. (16) √ √ Solving x ≤ ar x + 2ar µπ̄r + 2br + 2r yields √ ∆r (π̂ r ) ≤ 2a2r + 4ar µπ̄r + 4br + 4r. By (14) and Πr ⊂ Π0 , we have µπ̄ ≤ µπ̄r ≤ µπ̄ + r. Moreover, ∆(π̂) := µπ̂ − µπ̄ ≤ µπ̂r − µπ̄r + 2r = ∆r (π̂ r ) + 2r. Combining the previous display with |Πr | = Nlog (Π0 , r) gives s √ V (G) µπ̄r log Nlog (Π0 , r) δ −1 V (G) log Nlog (Π0 , r) δ −1 +4 2 ∆(π̂) ≤ 4 n n −1 log N (Π , r) δ 16 log 0 + G + 6r. 3 n √ Finally, apply 2 xy ≤ εx + yε to the square-root term with x = µπ̄r and y 8V (G)
=
log(Nlog (Π0 ,r)δ −1 ) , and use µπ̄r ≤ µπ̄ + r. Thus for any ε > 0, n
n n 1 X 1 X KL π ⋆ (· | si1:h−1 ) ∥ π̂(· | si1:h−1 ) = µπ̄ + ∆(π̂) ≤ (1 + ε) KL π ⋆ (· | si1:h−1 ) ∥ π̄(· | si1:h−1 ) nH i=1 nH i=1 log Nlog (Π0 , r) δ −1 C + (G + 1) + C ′ r, ε n □ iid
⋆
Lemma 3 (prefix-conditioned control for Bayesian Posterior). Let S1 , . . . , Sn ∼ P π with π ⋆ ∈ / Π = ΠH 0 or Πcons , where Π0 has a finite log-ratio cover. Under assumption 1, Bayesian Posterior algorithm guarantees that for any ε > 0, we have that, n H n H 1 XX 1 XX KL(πh⋆ (· | si1:h−1 )∥π̂h (· | si1:h−1 ) ≤ KL(πh⋆ (· | si1:h−1 )∥π̄h (· | si1:h−1 )) n i=1 n i=1 h=1
h=1
+ Hr + 14
H log Nlog (Π0 , r) . n
⋆
Proof. Let Si = (si1 , ui1 , . . . , siH , uiH ) be i.i.d. trajectories from P π for i = 1, . . . , n. Fix r > 0. Let Πh,r ⊂ Πh be an r-cover under the log-ratio metric, i.e., for every πh ∈ Πh there exists πhr ∈ Πh,r such that for all (u, s1:h−1 ), πh (u | s1:h−1 ) ≤ r. πhr (u | s1:h−1 )
log
Define the per-step Bayesian (exponential-weights) posterior predictor on Πh,r with a uniform prior by
π̂h (· | s1:h−1 ) =
X
qh (πhr ) πhr (· | s1:h−1 ),
P π̂ (S) =
r ∈Π πh h,r
H Y
π̂h (uh | s1:h−1 ).
h=1
By log-loss mixability, for any fixed data S1:n and any πhr ∈ Πh,r , n n X X − log π̂h (uih | si1:h−1 ) ≤ − log πhr (uih | si1:h−1 ) + log Nlog (Πh , r). i=1
(17)
i=1
Summing (17) over h = 1, . . . , H and adding
⋆ i i i,h log πh (uh | s1:h−1 ) to both sides gives
P
n H n H H π ⋆ (ui | si ) πh⋆ (uih | si1:h−1 ) 1 XX 1 XX 1X log h hi 1:h−1 ≤ log + log Nlog (Πh , r). n i=1 n i=1 n π̂h (uh | si1:h−1 ) πhr (uih | si1:h−1 ) h=1
h=1
(18)
h=1
For any π ∈ Π choose its cover representatives {πhr }H h=1 ⊂ Πh,r . By the cover property, n H ) πh (ui | si 1 XX log r hi 1:h−1 n i=1 πh (uh | si1:h−1 )
≤ Hr.
h=1
Since (18) works for any possible sequence, averaging both sides yields n H n H 1 XX 1 XX KL(πh⋆ (· | si1:h−1 )∥π̂h (· | si1:h−1 ) ≤ KL(πh⋆ (· | si1:h−1 )∥π̄h (· | si1:h−1 )) n i=1 n i=1 h=1
h=1
+ Hr +
H log Nlog (Π0 , r) . n
(19) □
A.2
Proofs for step 2: averaging over random prefixes
i i Lemma 4. Let Π0 be an arbitrary class and let Π = ΠH 0 . Let Si = (u1 , . . . , uH ) be i.i.d. trajectories ⋆ drawn from P π . For any π ∈ Π and trajectory S = (u1 , . . . , uH ), define ⋆
∆π (S) := KL(P π , P π ) − (1 + ε)
H X
KL πh⋆ (· | sh ) ∥ πh (· | sh ) ,
sh = (u1 , . . . , uh−1 ).
h=1
(20) Fix any r > 0, and let Π0,r ⊂ Π0 be an r-cover in the sense of Definition A.1, namely for each π0 ∈ Π0 there exists π0r ∈ Π0,r such that for all (u, s), log
π0 (u | s) ≤ r. π0r (u | s)
Write Nlog (Π0 , r) := |Π0,r |. Then for any δ ∈ (0, 1), with probability at least 1 − δ, simultaneously for all π ∈ Π, n 1X (1 + ε)2 HG 2H Nlog (Π0 , r) ∆π (Si ) ≤ log + (1 + ε)Hr. (21) n i=1 εn δ 15
For fully shared class Πcons , we have that for any δ ∈ (0, 1), with probability at least 1 − δ, simultaneously for all π ∈ Πcons , n 1X (1 + ε)2 HG 2 Nlog (Π0 , r) + (1 + ε)Hr. (22) ∆π (Si ) ≤ log n i=1 εn δ In particular, the same bound holds for any data-dependent π̂ ∈ Π. Proof of Lemma 4: We first prove the result for decomposable class. Fix h ∈ {1, . . . , H} and πh ∈ Π0 . For i = 1, . . . , n define Yh,i (πh ) := KL πh⋆ (· | Shi ) ∥ πh (· | Shi ) , Shi = (ui1 , . . . , uih−1 ). By Assumption 1, 0 ≤ Yh,i (πh ) ≤ G almost surely. Let Fi be the natural filtration of (S1 , . . . , Si ). Then Yh,i (πh ) is Fi -measurable, and by independence together with the chain rule for KL, Ei−1 Yh,i (πh ) = ESh KL πh⋆ (· | Sh ) ∥ πh (· | Sh ) , ⋆
where Sh denotes a generic prefix distributed according to P π . Apply Lemma 7 to the sequence Xi := Yh,i (πh ) ∈ [0, G]. With probability at least 1 − δh,πh , n n X X (1 + ε)2 G 2 Ei−1 [Yh,i (πh )] ≤ (1 + ε) Yh,i (πh ) + log , ε δh,πh i=1 i=1 and hence after dividing by n and rearranging, n (1 + ε)2 G 2 1 X Ei−1 [Yh,i (πh )] − (1 + ε)Yh,i (πh ) ≤ log . n i=1 εn δh,πh
(23)
Now apply (23) to all h ∈ [H] and all representatives πhr ∈ Π0,r , and take a union bound with δh,πhr = δ/(HNlog (Π0 , r)). With probability at least 1 − δ, for all h and all πhr ∈ Π0,r , n (1 + ε)2 G 2HN (Π , r) 1 X log 0 Ei−1 [Yh,i (πhr )] − (1 + ε)Yh,i (πhr ) ≤ log . (24) n i=1 εn δ e and let π r = (π r , . . . , π r ) be its coordinatewise representatives in Fix any π = (π1 , . . . , πH ) ∈ Π 1 H Π0,r . By the log-cover property, for every prefix s, π r (u | s) KL πh⋆ (· | s) ∥ πh (· | s) − KL πh⋆ (· | s) ∥ πhr (· | s) = Eu∼πh⋆ (·|s) log h ≤ r. πh (u | s) Consequently, for each trajectory S, H X
KL πh⋆ (· | sh ) ∥ πh (· | sh )
h=1
−
H X
KL πh⋆ (· | sh ) ∥ πhr (· | sh ) ≤ Hr.
h=1
The same argument applies to the chain-rule expression of the joint KL: ⋆
KL(P π , P π ) =
H X
ESh KL πh⋆ (· | Sh ) ∥ πh (· | Sh ) ,
h=1
hence ⋆
⋆
r
KL(P π , P π ) − KL(P π , P π ) ≤ Hr. Combining the two displays with the definition (20) yields ∆π (S) ≤ ∆πr (S) + (1 + ε)Hr for all trajectories S.
(25)
PH Pn ⋆ r Finally, sum (24) over h = 1, . . . , H and use h=1 i=1 Ei−1 [Yh,i (πhr )] = n KL(P π , P π ) (chain rule) to obtain n 1X (1 + ε)2 HG 2HNlog (Π0 , r) ∆πr (Si ) ≤ log n i=1 ε δ 16
e it also holds for Together with (25), this proves (21). Since the bound holds uniformly over π ∈ Π, e any data-dependent π̂ ∈ Π. For fully shared class, just take δh,πhr = δ/(Nlog (Π0 , r)) and the result follows the same steps. A.3
□
Proofs of Theorem 3.1 iid
⋆
Proposition 1 (Theorem 3.1, generalization to infinite classes). Let S1 , . . . , Sn ∼ P π with π ⋆ ∈ / Π, where Π is a finite decomposable model class. Under Assumption 1, ERM algorithm (3) and Bayesian Posterior algorithm (4) guarantees that for any δ ∈ (0, 1) and any ε > 0, with probability at least 1 − δ, ⋆ ⋆ (1 + ε)4/3 (HG + 1) log(HNlog (Π0 , r)δ −1 ) KL(P π ∥P π̂ ) ≲ (1 + ε) min KL(P π ∥P π ) + + (1 + ε)Hr . π∈Π ε n{z } | {z } |
estimation error
approximation error
(26) For fully shared model class Πcons , the result would be ⋆ ⋆ (1 + ε)4/3 (HG + 1) log(Nlog (Π0 , r)δ −1 ) + (1 + ε)Hr . KL(P π ∥P π̂ ) ≲ (1 + ε) min KL(P π ∥P π ) + π∈Πcons ε n{z | } | {z }
estimation error
approximation error
(27) Proof of Proposition 1: We focus on ERM algorithm under decomposable class, and the proof for the Bayesian posterior or fully shared class are similar. Having had Lemma 2 and Lemma 4, the only term we need to control is n 1X KL πh⋆ (· | sih ) ∥ π̄h (· | sih ) − (1 + ε)ES∼P π⋆ KL πh⋆ (· | sh ) ∥ π̄h (· | sh ) , (28) n i=1 Fix h ∈ [H] and r > 0, and let Π0,r ⊂ Π0 be an r-log-ratio cover . Pick π̃h ∈ Π0 such that Esh ∼P π⋆ KL πh⋆ (· | sh ) ∥ π̃h (· | sh ) ≤ inf Esh ∼P π⋆ KL πh⋆ (· | sh ) ∥ πh (· | sh ) + r, πh ∈Π0
which exists by the definition of the infimum. By the cover property, there is π̃hr ∈ Π0,r such that for all (u, s), log(π̃h (u | s)/π̃hr (u | s)) ≤ r, and hence for every prefix s, π̃ r (u | s) KL πh⋆ (· | s) ∥ π̃h (· | s) − KL πh⋆ (· | s) ∥ π̃hr (· | s) = Eu∼πh⋆ (·|s) log h ≤ r. π̃h (u | s) In particular, Esh ∼P π⋆ KL πh⋆ (· | sh ) ∥ π̃hr (· | sh ) ≤ inf Esh ∼P π⋆ KL πh⋆ (· | sh ) ∥ πh (· | sh ) + 2r. πh ∈Π0 ⋆ i r i Define Yi := KL πh (· | sh ) ∥ π̄h (· | sh ) and Fi := σ(S1 , . . . , Si ). ByAssumption 1, 0 ≤ Yi ≤ G a.s., and Ei−1 [Yi ] = Esh ∼P π⋆ Y where Y = KL πh⋆ (· | sh ) ∥ π̄hr (· | sh ) . Applying Lemma 7 yields, with probability at least 1 − δ, n 1X G Yi − (1 + ε)Esh ∼P π⋆ Y ≤ log(δ −1 ). n i=1 εn Combining with the choice of π̄hr gives (28) with the comparator term written as inf πh ∈Π0 Esh ∼P π⋆ KL(πh⋆ ∥πh ), up to an additional r-approximation term. Combining Lemma 2, Lemma 4 and 28, we have that ⋆ ⋆ (1 + ε)2 (HG + 1) log(HNlog (Π0 , r)δ −1 ) KL(P π ∥P π̂ ) ≲ (1 + ε)3 min KL(P π ∥P π ) + + (1 + ε)3 Hr. π∈Π ε n (29) Now the preceding bound is of the form (1 + ε)3 A +
(1 + ε)2 B + (1 + ε)3 Hr, ε 17
⋆
(HG+1) log(HN
(Π ,r)δ −1 )
0 log where A = minπ∈Π KL(P π ∥P π ) and B = . To rewrite the leading n 1/3 3 factor on A as (1 + ε), set ε̃ := (1 + ε) − 1 so that (1 + ε̃) = 1 + ε. Substituting ε̃ for ε preserves the 1/ε order in the estimation term since
(1 + ε̃)2 (1 + ε)2/3 (1 + ε)4/3 = , ≲ 1/3 ε̃ ε (1 + ε) − 1 up to universal constants. Consequently, we obtain the equivalent (up to constants) decomposition ⋆ ⋆ (1 + ε)4/3 (HG + 1) log(HNlog (Π0 , r)δ −1 ) + (1 + ε)Hr . KL(P π ∥P π̂ ) ≲ (1 + ε) min KL(P π ∥P π ) + π∈Π ε n{z } {z } | |
estimation error
approximation error
Following the same proof procedure, the same bound can be stated with an (1 + ε) prefactor in the estimation term for the Bayesian posterior, i.e., replacing (1 + ε)4/3 by (1 + ε) (up to universal constants). In the main paper, we state the bounds for both ERM and the Bayesian posterior with the enlarged coefficient (1 + ε)2 , since for practical choices of ε this is just a numerical constant and not a key ingredient of the theorem. □
B
Proof of Theorem 4.2 (Main Lower Bound)
Now we turn to the proof overview for Theorem 4.2. We establish the lower bound by an information–theoretic packing argument combined with Fano’s inequality. We build a small family of policies that are well separated yet individually close to the class average, so the data reveal only limited information about which one is true. Under proper learning the estimator must pick a single policy; when the information is too small, Fano forces a constant chance of picking the wrong one, which yields the desired lower bound combining with the separation. The proof below instantiates this outline. Proof of Theorem 4.2: Let the sample space be S = {1, . . . , d} with d ≥ |Π0 |. Choose |Π0 | vectors v (1) , . . . , v (|Π0 |) ∈ {±1}d that are pairwise orthogonal and balanced (e.g., columns of a Hadamard matrix, padded if needed). For ε > 0, define exp(εvs ) eεvs P πv (s) = Pd (s ∈ S). = d cosh ε k=1 exp(εvk ) Then, for any v, w and any s, log
P πv (s) = ε (vs − ws ) ∈ {−2ε, 0, 2ε}. P πw (s)
(⋆)
Taking ε ≤ G/2 gives the required two–sided ratio bound. Let the average (uniform) distribution be P̄ (s) =
1 X πv 1 P (s) = . |Π0 | v d
A direct calculation using orthogonality yields, for v ̸= w, KL(P πv ∥ P πw ) = ε tanh ε, KL P πv ∥ P̄ = ε tanh ε − log cosh ε. Using tanh x ≥ x/2 and log cosh x ≤ x2 /2 for x ∈ (0, 1], we have KL P πv ∥ P̄ ≤ 12 ε2 . KL(P πv ∥ P πw ) ≥ 12 ε2 ,
(30)
Now we construct a hard finite class of H-step product policies and apply a per-coordinate Fano argument. Define the H-step policy class n o Π := ΠH 0 = π = (π1 , . . . , πH ) : πh ∈ Π0 ∀h ∈ [H] , where each Π0 is the same single-step class indexed by {v (1) , . . . , v (|Π0 |) }. For any index vector θ = (θ1 , . . . , θH ) ∈ {1, . . . , |Π0 |}H , 18
let π θ ∈ Π denote the H-step policy with πhθ = πv(θh ) , and define the induced distribution on an H-step trajectory S = (S1 , . . . , SH ) ∈ S H by the product form P θ (S) =
H Y
P πv(θh ) (Sh ).
(31)
h=1
We observe n i.i.d. trajectories S 1 , . . . , S n ∼ P θ and write S1:n := (S 1 , . . . , S n ). By the chain rule for KL and the product structure (31), for any θ, θ′ , H X ε2 π ′ θ θ′ KL P ∥ P = KL P πv(θh ) ∥ P v(θh ) ≥ dH (θ, θ′ ), 2
(32)
h=1
where dH (θ, θ′ ) := |{h : θh ̸= θh′ }|. Let Θ be uniform on {1, . . . , |Π0 |}H . Consider any estimator Θ̂ = Θ̂(S1:n ) ∈ {1, . . . , |Π0 |}H . Fix any coordinate h ∈ [H]. Conditional on Θ−h := (Θ1 , . . . , Θh−1 , Θh+1 , . . . , ΘH ), the data in coordinates ̸= h are independent of Θh and do not carry information about Θh under the product model (31). Therefore, I(Θh ; S1:n | Θ−h ) = I(Θh ; S1:n,h ), where S1:n,h := (Sh1 , . . . , Shn ) are the step-h observations across the n trajectories. Applying Fano’s inequality to the |Π0 |-ary hypothesis test for Θh yields, for any estimator Θ̂h , Pr(Θ̂h ̸= Θh ) ≥ 1 −
I(Θh ; S1:n,h ) + log 2 . log |Π0 |
Moreover, by the standard mutual information bound via the uniform mixture P̄ and (30), n X n I(Θh ; S1:n,h ) ≤ max KL P πv ∥ P̄ ≤ ε2 . v 2 i=1
(33)
(34)
Choose r G log |Π0 | ε := , 4 n and assume n ≥ c0 log |Π0 | with c0 large enough so that ε ≤ min{G/2, 1}. Then (33)–(34) imply, for |Π0 | large enough, 1 Pr(Θ̂h ̸= Θh ) ≥ for all h ∈ [H]. (35) 2 Summing (35) over h gives H X H E dH (Θ, Θ̂) = Pr(Θ̂h ̸= Θh ) ≥ . 2
(36)
h=1
Hence then, using (32) and (36), we have that h i ε2 H 2 E KL P Θ ∥ P Θ̂ ≥ E dH (Θ, Θ̂) ≥ ε . 2 4 Finally, since Θ is uniform on {1, . . . , |Π0 |}H , h i h i sup EP θ KL P θ ∥ P Θ̂ ≥ E KL P Θ ∥ P Θ̂ ,
(37)
θ∈{1,...,|Π0 |}H 2
log |Π0 | and combining with (37) and ε2 = G yields 16 n h i H G2 log |Π0 | 1 H G2 log |Π0 | sup EP θ KL P θ ∥ P Θ̂ ≥ · · = . 4 16 n 64 n θ∈{1,...,|Π0 |}H
This proves the claim with c = 1/64.
□
Corollary 1. There exist absolute constants c, c0 > 0 such that for any |Π| ≥ 4, any n ≥ c0 log |Π|, any horizon H ∈ N, and any G ∈ (0, 1], one can construct a finite general dependent policy 19
class Π and associated distributions {P π }π∈Π on a finite sample space such that for every selector iid
⋆
π̂ = π̂(S1:n ) ∈ Π based on S1 , . . . , Sn ∼ P π where π ⋆ ∈ Π, h ⋆ i H 2 G2 log |Π| inf sup EP π⋆ KL P π P π̂ ≥ c . π̂∈Π π ⋆ ∈Π n
(38)
Proof of Corollary 1: The proof mirrors Theorem 4.2, but the key change is that under a dependent class the trajectory law no longer decomposes across steps. Hence the (⋆) likelihood-ratio bound must be applied to the joint policy (rather than stepwise), which forces the corresponding choice of ε at the HG scale. With this joint control in place, we apply Fano’s inequality directly to the |Π|-ary testing problem and do not need a per-coordinate Fano argument. Let the sample space be S = {1, . . . , d} with d ≥ |Π|. Choose |Π| vectors v (1) , . . . , v (|Π|) ∈ {±1}d that are pairwise orthogonal and balanced (e.g., columns of a Hadamard matrix, padded if needed). For ε > 0, define exp(εvs ) eεvs (s ∈ S). P πv (s) = Pd = d cosh ε k=1 exp(εvk ) Then, for any v, w and any s, log
P πv (s) = ε (vs − ws ) ∈ {−2ε, 0, 2ε}. P πw (s)
Taking ε ≤ HG/2 gives the required two–sided ratio bound. Let the average (uniform) distribution be P̄ (s) =
1 X πv 1 P (s) = . |Π| v d
A direct calculation using orthogonality yields, for v ̸= w, KL(P πv ∥ P πw ) = ε tanh ε, KL P πv ∥ P̄ = ε tanh ε − log cosh ε. Using tanh x ≥ x/2 and log cosh x ≤ x2 /2 for x ∈ (0, 1], we have KL P πv ∥ P̄ ≤ 12 ε2 . KL(P πv ∥ P πw ) ≥ 12 ε2 ,
(39)
We use Fano’s information inequality here. Let π be uniform on {1, . . . , |Π|} and observe S1:n ∼ (P π )⊗n . For any estimator π̂, Fano’s inequality gives that Pr(π̂ ̸= π) ≥ 1 −
I(π; S1:n ) + log 2 . log |Π|
(40)
By the chain rule and (39), I(π; S1:n ) ≤
n X
n max KL P πv ∥ P̄ ≤ ε2 . v 2 i=1
(41)
Choose r HG log |Π| ε := , 4 n and assume n ≥ c0 log |Π| so that ε ≤ min{HG/2, 1}. Then (40)–(41) imply, for |Π| large enough, Pr(π̂ ̸= π) ≥ 1 −
H 2 G2 log 2 1 − ≥ . 32 log |Π| 2
(42)
Notice that whenever π̂ ̸= π, by (39), KL(P π ∥ P ππ̂ ) ≥ 21 ε2 . Therefore, h ⋆ i 1 H 2 G2 log |Π| ε2 (42) 1 1 2 sup EP π⋆ KL P π ∥ P π̂ ≥ · ε = , ≥ Pr(π̂ ̸= π) · 2 4 2 64 n π ⋆ ∈Π which proves the claim with c = 1/64.
□ 20
C
Missing proofs in Section 3
Proof of Theorem 3.2 It suffices to prove the claim for the special case H = 1. Indeed, the general H statement follows by taking a product construction across steps so that the joint KL adds over h and the lower bound scales linearly in H. Let the token space be X = {0, 1}. Fix a constant a ∈ (0, 1/4), and for each n ≥ 1 set 1 b := √ . 10 n Consider a base class Π0 = {π (+) , π (−) } consisting of two (history-independent) conditional models, 1 1 π (+) (1) := + a, π (−) (1) := − a, π (+) (0) := 1 − π (+) (1), π (−) (0) := 1 − π (−) (1). 2 2 For the data-generating policy, define π ⋆ ∈ / Π0 by 1 π ⋆ (1) := + b, π ⋆ (0) := 1 − π ⋆ (1). 2 ⋆ Then P π is the induced distribution on u ∈ X with Pr(u = 1) = 21 + b, and for any π ∈ Π0 , P π is the induced distribution with Pr(u = 1) = 12 ± a. Since b ̸= a, we have π ⋆ ∈ / Π0 , i.e. the model is misspecified. Moreover, Assumption 1 holds with absolute constants because all Bernoulli parameters lie in [ 12 − a, 12 + a] ⊂ [1/4, 3/4], so the log-loss range is uniformly bounded. When H = 1, both choices in the theorem reduce to the same class Π = Π0 (since ΠH 0 = Π0 and Πcons = Π0 ). A direct computation yields ⋆
KL P π ∥P π
(−)
⋆
− KL P π ∥P π
(+)
1
+a . 2 −a
= (2b) log 21
Choosing a = 1/4 gives the explicit gap 2b log 3. In particular, n o ⋆ ⋆ (+) ⋆ (−) inf KL P π ∥P π = min KL P π ∥P π , KL P π ∥P π , π∈Π0
and selecting the “wrong” element of Π0 increases the KL by exactly 2b log 3. Let π̂ be any (possibly randomized) learner that outputs π̂ ∈ Π0 from n i.i.d. samples u1 , . . . , un ∼ ⋆ P π . Consider the associated test φ := 1{π̂ = π (+) }. If instead the data-generating policy is 1 1 ⋆ ⋆ or π− (1) = − b, π+ (1) = + b 2 2 then Le Cam’s inequality gives ⋆ ⋆ Pr⋆ (π̂ = π (−) ) + Pr⋆ (π̂ = π (+) ) ≥ 1 − TV (P π+ )⊗n , (P π− )⊗n . P
π
+
P
π
−
By Pinsker’s inequality and tensorization, r r ⋆ ⋆ 1 n ⋆ ⋆ ⋆ ⋆ KL (P π+ )⊗n ∥(P π− )⊗n = KL P π+ ∥P π− . TV (P π+ )⊗n , (P π− )⊗n ≤ 2 2 For Bernoulli parameters 12 ± b, one has the standard bound ⋆ ⋆ KL P π+ ∥P π− ≤
(2b)2 ≤ 16b2 , ( 12 − b)( 21 + b)
which implies TV (P
⋆ π+ ⊗n
)
, (P
⋆ π− ⊗n
)
r
≤
√ n 8 1 · 16b2 = < . 2 10 3
Therefore, Pr⋆ (π̂ = π (−) ) + Pr⋆ (π̂ = π (+) ) ≥ P
π
+
P
π
−
so for at least one choice of sign σ ∈ {+, −} we have Pr⋆ (π̂ ̸= π (σ) ) ≥
P πσ
21
1 . 3
2 , 3
Fix such a sign and take the corresponding data-generating policy π ⋆ := πσ⋆ . Now we can conclude the lower bound. On the event {π̂ ̸= π (σ) }, the excess joint KL over the oracle in Π0 is exactly 2b log 3. Hence, with probability at least δ0 := 1/3, ⋆ ⋆ ⋆ 1 KL P π ∥P π̂ ≥ inf KL P π ∥P π + 2b log 3 = inf KL P π ∥P π + c · √ , π∈Π0 π∈Π n √ log 3 where c := 5 since b = 1/(10 n). This proves Theorem 3.2 for H = 1. As noted at the beginning, the general H statement follows by taking the product construction across √ h ∈ [H], in which case the excess KL accumulates additively, yielding the term cH/ n while the same constant-probability event persists. □ Proof of Lemma 1:
SH
By definition, Π0 =
h=1 Πh , hence
|Π0 | ≤
H X
|Πh |.
h=1
For each h, the coordinate projection map projh : Π → Πh given by projh (π) = πh is surjective by definition of Πh , and therefore |Πh | ≤ |Π|. Combining these two bounds yields |Π0 | ≤
H X
H X
|Πh | ≤
h=1
|Π| = H|Π|.
h=1
Taking logarithms gives the first inequality. We next prove the second one. Since Πh ⊆ Π0 for all h, we have Π ⊆ Π1 × · · · × ΠH ⊆ ΠH 0 . H H Therefore |Π| ≤ |Π0 | = |Π0 | . Taking logarithms gives the result.
D
□
Technical Tools
Lemma 5 (Central to Bernstein (Mehta, 2017)). Let X be a random variable taking values in [−B, B]. Assume that E e−ηX ≤ 1, then 1 2 E[X ] ≤ 4 + B E[X]. η Lemma 6 (Freedman’s inequality (Beygelzimer et al., 2011)). Let (Xt )t≤T be a real-valued martingale difference sequence adapted to a filtration (Ft )t≤T . If |Xt | ≤ R almost surely, then for any η ∈ (0, 1/R), with probability at least 1 − δ, T X
Xt ≤ η
t=1
T X
log(δ −1 ) Et−1 Xt2 + . η t=1
(43)
The following result is a consequence of Lemma 6. Lemma 7. Let (Xt )t≤T be a sequence of random variables adapted to a filtration (Ft )t≤T . If 0 ≤ Xt ≤ R almost surely, then with probability at least 1 − δ, T X
Xt ≤ (1 + ε)
t=1
T X
R log(δ −1 ), ε
(44)
(1 + ε)2 R log(δ −1 ). ε
(45)
Et−1 [Xt ] +
t=1
and also with probability at least 1 − δ, T X t=1
Proof of Lemma 7:
Et−1 [Xt ] ≤ (1 + ε)
T X
Xt +
t=1
Define the martingale difference sequence Zt := Xt − Et−1 [Xt ], t = 1, . . . , T. 22
Since 0 ≤ Xt ≤ R, we have |Zt | ≤ R almost surely. Moreover, Et−1 [Zt2 ] = Vart−1 (Xt ) ≤ Et−1 [Xt2 ] ≤ R Et−1 [Xt ], where the last inequality uses Xt2 ≤ RXt for Xt ∈ [0, R]. We apply Freedman’s inequality (Lemma 6) to (Zt )t≤T . For any η ∈ (0, 1/R), with probability at least 1 − δ, T X
Zt ≤ η
t=1
T X
Et−1 [Zt2 ] +
t=1
≤ ηR
T X
Et−1 [Xt ] +
t=1
Recalling
PT
t=1 Zt =
PT
t=1 Xt − T X
log(δ −1 ) η log(δ −1 ) . η
PT
t=1 Et−1 [Xt ], we obtain
Xt ≤ (1 + ηR)
t=1
T X
Et−1 [Xt ] +
t=1
log(δ −1 ) . η
Choosing η = ε/R (which is valid since ε ∈ (0, 1)) yields (44). For (45), apply Freedman’s inequality to the martingale difference sequence −Zt . Equivalently, with probability at least 1 − δ, −
T X
Zt ≤ η
t=1
Since −
PT
t=1 Zt =
T X
Et−1 [Zt2 ] +
t=1
PT
t=1 Et−1 [Xt ] −
(1 − ηR)
T X
T X log(δ −1 ) log(δ −1 ) ≤ ηR Et−1 [Xt ] + . η η t=1
PT
t=1 Xt , this implies
Et−1 [Xt ] ≤
t=1
T X t=1
Xt +
log(δ −1 ) . η
ε Choose η = (1+ε)R ∈ (0, 1/R), so that (1 − ηR)−1 = 1 + ε. Then T X
Et−1 [Xt ] ≤ (1 + ε)
t=1
T X t=1
Xt + (1 + ε)
T X log(δ −1 ) (1 + ε)2 R = (1 + ε) Xt + log(δ −1 ), η ε t=1
□
which is (45).
E
Impact Statement and Limitations
E.1
Broader Impacts
This paper is primarily theoretical: it studies autoregressive learning under joint KL evaluation and clarifies how log-loss training, misspecification, and horizon dependence interact at the sequencedistribution level. Its potential positive impact is methodological reliability. Many sequential prediction and decision systems are used through the full trajectories they induce, so evaluating only conditional accuracy can obscure long-horizon error accumulation. By aligning the training objective, evaluation metric, and approximation metric in joint KL, our results provide sharper tools for auditing autoregressive models and for understanding when full-sequence behavior is controlled. At the same time, these results should not be interpreted as deployment guarantees by themselves: joint-KL control on the training distribution does not ensure validity under unsupported interventions, distribution shift, hidden confounding, or misaligned objectives. If sequential data encode historical bias, strategic behavior, or missing variables, sharper sequence modeling may amplify rather than remove such risks. Responsible use therefore requires support/identification checks, robustness analysis, constraint and fairness auditing, and appropriate human oversight in high-stakes applications. E.2
Limitations
This paper is primarily theoretical. We develop a joint-KL framework for autoregressive learning, characterize horizon dependence, and connect sequence-level statistical guarantees to downstream 23
decision control. The present work does not provide large-scale empirical validation or domainspecific deployment studies. In particular, applying the theory to prediction and decision systems requires problem-specific modeling choices, sufficient support for the relevant history-action pairs, and careful treatment of distribution shift and identification. We view applications to language modeling, dynamical systems, and decision-making as important follow-up directions, and are actively developing empirical and domain-driven extensions of the framework.
24