When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?

Xuanfei Ren; Tengyang Xie

Source-linked AI summary

When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?

Xuanfei Ren, Tengyang Xie

arXiv:2606.18531v1Jun 16, 2026stat.MLcs.LG

TL;DR

Outcome-level supervision raises questions about when offline reinforcement learning remains statistically tractable. This paper develops OPAC and a theory spanning scalar outcomes, preferences, and nonlinear trajectory objectives, proving sharp rates in tractable settings and exponential barriers in general.

Problem
The paper asks when trajectory-level supervision supports offline policy optimization and whether difficulty arises from distribution shift, latent-reward recovery, or the trajectory-level objective itself.
Method
OPAC jointly learns latent per-step rewards and values using trajectory-level regression, Bellman-error constraints, and pessimistic policy updates.
Results
OPAC attains a sharp eO(H^2√(C_sa(π⋆)/n)) rate with matching bounds, while nonlinear objectives can require Ω(2^H) samples but admit polynomial complexity under κ_μ(σ) and χ_μ(σ).
Takeaways & Limitations
Outcome-level supervision permits efficient offline control for cumulative rewards and structured aggregations, but missing process rewards can make general nonlinear objectives statistically restrictive.
Takeaways & Limitations
The generalized framework assumes a known aggregation rule with Bellman-style structure and does not fully characterize which trajectory-level objectives are learnable and practically meaningful.

Abstract

from arXiv · show

Offline reinforcement learning is typically analyzed under process-level reward supervision, yet many sequential decision datasets record only trajectory-level outcomes. We develop a statistical theory for offline policy optimization from such outcome-level supervision. We first study the canonical setting where the target remains the expected cumulative reward, but each offline trajectory provides only a scalar label whose conditional mean is the cumulative return. We propose OPAC, a pessimistic actor-critic algorithm that learns a latent reward model and optimizes a policy from trajectory-level labels. We prove a high-probability guarantee of order $\widetilde O(H^2\sqrt{C_{sa}(π^\star)/n})$ and a matching lower bound, characterizing the sharp statistical cost of replacing process-level rewards with one trajectory-level label. We then extend the principle to preference-based feedback, preserving the leading horizon and concentrability dependence up to preference-model constants. Finally, we study generalized outcome-based offline RL, where both the supervision and the objective are trajectory-level quantities induced by a nonlinear aggregation of latent per-step rewards. This problem is not learnable in general: for all-success objectives, any offline learner may require $Ω(2^H)$ trajectories even with deterministic transitions and constant concentrability. We then identify a tractable regime through two structural coefficients, $κ_μ(σ)$ and $χ_μ(σ)$, capturing information loss in outcome aggregation and generalized Bellman updates, under which generalized OPAC achieves polynomial sample complexity. Together, our results delineate when outcome-level supervision enables sample-efficient offline control and when missing process-level rewards create fundamental statistical barriers.

1 Introduction

The paper develops a theory of offline policy optimization from trajectory-level supervision, separating difficulties from distribution shift, latent-reward recovery, and trajectory-level objectives. It establishes efficient learning for standard cumulative-return objectives under scalar outcomes or preferences, but identifies exponential barriers for generalized objectives and polynomial guarantees under structural information-preservation conditions.

Scalar outcomes: OPAC jointly learns latent per-step rewards and values, using trajectory-level regression, plug-in Bellman constraints, and pessimistic policy updates for offline distribution shift.The method operates under standard realizability and completeness assumptions with bounded rewards and outcomes.
Scalar outcomes: Ω(H4/ε2) trajectories are necessary at constant state-action concentrability, even with deterministic transitions and two actions.The lower bound attributes the extra difficulty to compressing reward information into one scalar outcome rather than exploration or transition estimation.
Trajectory preferences: H2pCsa(π⋆)/n dependence is preserved for Bradley–Terry–Luce preferences, up to preference-model constants.Logistic preference regression replaces squared trajectory-return regression while retaining the cumulative-return optimization target.
Generalized objectives: Ω(2H) trajectories may be required for nontrivial performance on the all-success objective, despite deterministic transitions and constant state-action concentrability.The objective assigns value one only when every stage succeeds.
Generalized objectives: κµ(σ) and χµ(σ) quantify information loss from outcome aggregation and generalized Bellman targets, enabling polynomial rates in tractable regimes.The outcome-based formulation uses the observed trajectory outcome as both supervision signal and optimization target.

2 Preliminary

The paper studies finite-horizon offline reinforcement learning in MDPs where process-level rewards are unobserved and trajectories instead receive outcome-level supervision. It formalizes policy values, function classes, behavior-data coverage, and notation for subsequent guarantees.

MDP model: A finite-horizon MDP comprises layered state and action spaces, transition kernels, bounded process rewards, a fixed initial state, and Markov policies.The horizon is H, and trajectories contain states and actions from each stage.
Outcome supervision: Process-level rewards define the optimization objective, but offline data omit them and provide trajectory-level outcomes whose conditional mean equals cumulative reward.The dataset consists of n i.i.d. trajectories sampled from behavior policy µ, each paired with an outcome Y satisfying E[Y | τ] = R⋆(τ).
Coverage: Offline learning assumes coverage through all-step state–action concentrability of candidate policies relative to the fixed behavior policy µ.The paper notes that this standard density-ratio condition could be replaced by function-class-dependent coverage, but retains it to focus on reward-supervision granularity.
Objectives and classes: Policy value is J(π) := Eπ[R⋆(τ)], with π⋆ chosen as the in-class maximizer over a fixed policy class Π.The framework also specifies per-step value-function and mean process-reward classes, F and R.
Asymptotic notation: The notation uses O, Ω, and Θ for standard asymptotic bounds, while eO, eΩ, and eΘ additionally hide polylogarithmic problem-parameter factors.The relation a ≲ b denotes an inequality up to a universal constant, with a ≳ b defined analogously.

3 Sample-Efficient Offline RL with Outcome Reward

With only one unbiased cumulative-outcome label per trajectory, OPAC learns a latent reward while enforcing Bellman consistency and achieves a sharp outcome-supervised offline-RL rate. The unavoidable extra horizon factor is purely statistical, arising from compressing H per-step rewards into one label.

OPAC: OPAC alternates pessimistic evaluation with layer-wise exponential-weights policy updates, fitting a latent process reward to trajectory outcomes while enforcing Bellman consistency.Its criteria combine policy mismatch, candidate-reward Bellman error, and regression to scalar outcomes, with double-sampling correcting transition-noise variance.
Assumptions and guarantee: Under reward realizability, approximate value realizability, and Bellman completeness, OPAC returns a high-probability near-optimal policy with statistical error governed by coverage, iteration count, and approximation errors.Completeness is required uniformly over candidate rewards because OPAC estimates rewards from outcome labels and evaluates Bellman backups under them.
Upper bound: n = eO(H4Csa(π⋆)/ε2) trajectories suffice for ε-optimality when εF = εF,F = 0 and K ≥ n.Compared with process-level supervision, outcome supervision incurs one additional factor of H in the horizon dependence.
Lower bound: Ω(H4/ε2) trajectories may be necessary even with deterministic transitions and Csa(π⋆) ≤ 2, establishing a matching lower bound.The lower bound holds for sufficiently large H and n ≥ 64H2, with no transition-learning difficulty.
Tightness: eO(H2√Csa(π⋆)/n) is statistically optimal up to logarithmic factors among algorithms observing bounded unbiased outcome labels.The matching result covers the H2 horizon factor, 1/n statistical rate, and dependence on Csa(π⋆).
Comparison with process supervision: The extra factor of H over process-level supervision persists with constant coverage and deterministic dynamics, reflecting only compression of H per-step rewards into one trajectory-level label.Process-level supervision has an information-theoretic lower bound of Ω(H3/ε2), whereas outcome supervision has eΘ(H4/ε2) sample complexity.

4 Offline RL from Trajectory-Level Preferences

Preference-based offline RL replaces scalar trajectory outcomes with noisy pairwise comparisons while retaining cumulative return as the optimization target. Preference-based OPAC changes only reward fitting, and its guarantee preserves the leading coverage and horizon dependence up to comparison-model constants.

Preference observation model: Pairwise preferences are generated by a fixed Bradley–Terry–Luce model from latent trajectory returns, so learners observe only noisy binary comparisons.The true per-step reward and trajectory return are not directly observed.
Preference loss and algorithm: Preference-based OPAC retains the pessimistic actor–critic and exponential-weights updates, changing reward fitting from squared regression to logistic regression.The output remains a mixture policy over iterates.
Sample complexity: Theorem 3 gives a high-probability policy guarantee for preference-based OPAC under Assumptions 1–3 and suitable parameters η and β.The guarantee holds with probability at least 1 −δ.
Sample complexity: The rate preserves the leading H2p Csa(π⋆)/n dependence, with αC and cC adding comparison-model constants over returns in [0, H].The special case εF = εF,F = 0 and K ≥n is identified separately in the theorem statement.

5 Outcome-Based RL with Generalized Objective

This section studies offline RL where the trajectory-level outcome is both the supervision and the objective, potentially through a nonlinear aggregation of latent per-step rewards. It shows that learning can be exponentially hard without structure, while two coefficients characterize tractable generalized objectives.

Generalized objective: Generalized RL optimizes the expected trajectory outcome induced by a known stage-wise aggregation rule σ, with cumulative reward recovered when σ is summation.Nonlinear aggregations define objectives distinct from noisy proxies for latent cumulative rewards.
All-success example: The all-success aggregation sets σ to the product of binary per-step rewards, making the objective the probability that every stage succeeds.This is a nonlinear trajectory criterion rather than a cumulative-reward proxy.
Impossibility result: Ω(2^H) trajectories are required to achieve expected suboptimality below 1/8 under all-success aggregation, even with deterministic transitions and C_sa(π⋆) ≤ 2.The outcome label is informative on only an exponentially small set of trajectories.
Structural coefficients: κ_μ(σ) measures information loss when recovering latent per-step rewards from outcomes, while χ_μ(σ) measures compression during generalized Bellman propagation.Generalized OPAC must address both inverse problems, which are independent and cannot generally be merged.
Tractable regime: Under Assumptions 1–4, generalized OPAC provides a high-probability policy guarantee for Bellman-learnable aggregations controlled by κ_μ(σ) and χ_μ(σ).The structured subclass includes cumulative returns and all-success objectives through stage-wise aggregation maps satisfying the stated regularity conditions.

6 Conclusion … B.3 Approximation and Comparator Lemmas

The paper concludes that trajectory-level supervision can support efficient offline policy optimization for cumulative and structured objectives, but generalized outcome objectives may impose exponential barriers. Its appendices establish the concentration, approximation, comparator, and optimization tools underlying these guarantees, while noting limitations of the generalized framework.

6 Conclusion: OPAC attains a sharp eO(H^2√(C_sa(π⋆)/n)) rate for cumulative-reward objectives, quantifying the cost of compressing H process-level rewards into one trajectory label.The same theoretical template extends to trajectory preferences.
6 Conclusion: Generalized outcome objectives exhibit an exponential barrier in general, while structured aggregations controlled by κ_μ(σ) and χ_μ(σ) admit polynomial sample complexity.The framework assumes a known aggregation rule with Bellman-style structure and does not fully characterize statistically learnable, practically meaningful objectives.
A Related Work: The related-work discussion positions this contribution at the intersection of pessimistic offline RL, preference learning, outcome-based feedback, and generalized trajectory objectives.It emphasizes offline learning under partial single-policy coverage and identifies κ_μ(σ) and χ_μ(σ) as complexity measures for tractable generalized objectives.
B Technical Lemmas for Outcome-based Offline RL: The technical appendix defines the population loss notation and develops auxiliary lemmas supporting outcome-based offline RL analysis.These tools include trajectory-measure change, layer-wise no-regret optimization, concentration, and Bellman-error control.
B.1 Change-of-Measure and Optimization Tools: The change-of-measure and optimization tools control distribution-shift terms and the policy-optimization component of the upper-bound proof.The subsection uses a trajectory-measure lemma and a specialized exponential-weights no-regret bound.
B.2 Concentration Lemmas: The concentration lemmas transfer population losses to empirical counterparts through uniform policy-loss, reward-model, and Bellman-error estimates.The bounds rely on Hoeffding- and Bernstein-style concentration under bounded rewards, critics, finite classes, and approximate Bellman completeness.
B.3 Approximation and Comparator Lemmas: The approximation and comparator lemmas bound the pessimism-step comparator, performance differences, and regret decomposition using critic realizability and Bellman residual arguments.Lemma 12 provides a high-probability inequality uniformly over policies, while later lemmas express policy-performance gaps through fake rewards and residuals.

C Proof of the Outcome-Based Offline RL Upper Bound … D.1 Preference Identifiability and Concentration

The proofs establish the outcome-based offline RL upper bound through regret decomposition, policy optimization, pessimistic empirical transfer, and parameter selection. The preference extension uses BTL identifiability, concentration, and a centered change-of-trajectory-measure argument.

C Proof of the Outcome-Based Offline RL Upper Bound: Theorem 1 is proved using the population losses defined in Eq. (18).
C.1 Regret Decomposition: The regret upper bound is decomposed using Lemma 15 for arbitrary learned policies, latent rewards, and function estimates.
C.2 Bounding the Policy-Optimization Term: The policy-optimization term is controlled by the no-regret layer-wise softmax update, with bounded function values enabling Lemma 8.The analysis selects η = η⋆ = Vmax√(K/(8 log |A|)).
C.3 Bounding the Bellman and Reward-Mismatch Terms: Bellman and reward-mismatch terms are bounded using state-action concentrability, change-of-trajectory measure, Cauchy–Schwarz, and AM–GM.The pessimism coefficient is aligned through the β/2 parameter choice and the factor-2 concentration bounds.
C.4 Pessimism and Empirical Transfer: Pessimistic empirical transfer proceeds through four steps: transferring losses, pivoting with fπk, invoking pessimistic optimality, and cancelling the centered reward-model term.The cancellation removes the potentially constant-order LRM_D(r⋆) term from the final bound.
C.5 Final Rate and Parameter Choice: With n trajectories and Vmax = H, concentration terms scale at the trajectory level, while the H factor in Bellman-error terms comes from summing over h.The final parameter choice uses K ≥ n under exact realizability and exact Bellman completeness.
D Proof of the Preference-Based Upper Bound: The preference-based proof follows the scalar-outcome argument, replacing squared reward-model loss with logistic preference loss while using 2n unlabelled trajectories from preference pairs.The fixed BTL constants depend only on γ and H.
D.1 Preference Identifiability and Concentration: Under BTL feedback, preference log loss is identifiable through return-difference error and concentrates uniformly over r via a self-bounded log-likelihood ratio.The constants depend on aC = 1/(1 + eγH), hence on γH, but not on n, δ, or reward-class size outside logarithmic factors.

D.2 Proof of the Preference-based Upper Bound · E Lower Bound for Outcome-based Learning

The preference-based proof preserves the scalar-outcome regret decomposition, adding only a preference-specific reward-mismatch and concentration analysis. Optimizing the preference parameter β and using the BTL constants yields the stated upper bound, while the supplied passages contain no evidence for the merged lower-bound section.

D.2 Proof of the Preference-based Upper Bound: The cumulative-return objective and regret decomposition remain unchanged from the scalar-outcome proof.Terms (I)k, (II)k, and (III)k are controlled exactly as before; only the population reward-mismatch term changes.
D.2 Proof of the Preference-based Upper Bound: Lemma 17 supplies a centered preference concentration bound, while the remaining empirical-loss controls hold on the scalar-outcome proof’s high-probability event.The proof transfers population losses to empirical losses using Eq. (58a), Eq. (58c), and Eq. (58d).
D.2 Proof of the Preference-based Upper Bound: Preference-model optimality and performance-loss transfer combine to bound the empirical terms by preference-specific slack terms.The argument invokes Eqs. (68), (69), and (70), then rewrites βεapx as (β/2) · 2εapx.
D.2 Proof of the Preference-based Upper Bound: εPref = eO(cC/n), and optimizing β minimizes the first two terms in the resulting bound.The constants cC and αC are the BTL preference constants, with β chosen according to the proof’s balancing step.
D.2 Proof of the Preference-based Upper Bound: The optimized choice gives an explicit intermediate bound that can be equivalently expanded using Csa(π) ≥1.The proof expands the square-root product before adding the no-regret contribution for term (II).
D.2 Proof of the Preference-based Upper Bound: Adding the no-regret term and setting Vmax = H yields the final averaged preference-based guarantee, which proves Eq. (11) for π = π⋆.The BTL constants depend on γ and H through the bounded comparison range, but not on n, δ, or |R| beyond log(|R|/δ).

E.1 Proof of Theorem 2: Lower Bound for Sum-Reward Outcomes

The lower bound constructs deterministic finite-horizon MDPs where binary action choices encode an unknown parameter and only a bounded trajectory-level label is observed. A Fano-based estimation reduction shows that recovering the optimal policy incurs loss scaling with the horizon and reward gap, even though C_sa=2.

Hard-instance construction: The hard family uses deterministic transitions, binary actions, and an unknown parameter θ∈{0,1}^H specifying the rewarding action at each stage.The state is the time index, so the learner must identify the correct action independently across H stages.
Hard-instance construction: At each step, the correct action receives (1+∆)/2 and the other receives (1−∆)/2, with ∆∈[0,1].Both rewards lie in [0,1], and the trajectory return is determined by the Hamming distance between the action vector and θ.
Outcome-level observation: The uniform behavior policy yields C_sa=2, while the learner observes only Y(τ)∈{0,H} with E[Y(τ)|τ]=R_θ(τ).Thus the construction satisfies the bounded unbiased trajectory-outcome model used for the upper bound.
Statistical reduction: Fano’s inequality applied to a Varshamov–Gilbert packing reduces policy learning to estimating θ from n i.i.d. trajectory-label samples.The construction uses ∆≤1/2 under the standing condition n≥64H^2 and selects a packing with log M≥H/8.
Policy-learning lower bound: The estimation lower bound gives 2Φ(δ/2)=δ/4≥∆H/32, and policy errors translate into at least ∆/2 reward loss at every incorrectly identified stage.Therefore, guaranteeing suboptimality at most ε requires controlling the corresponding parameter-estimation error.

E.2 Proof of Theorem 5: Exponential Lower Bound for All-Success Aggregation · F Generalized Reinforcement Learning Theory · F.1 Generalized Value Functions and Bellman Recursion

The paper proves an exponential lower bound for all-success aggregation despite constant state–action concentrability, then develops generalized value functions and Bellman recursions for stage-wise affine-in-continuation objectives.

E.2 Proof of Theorem 5: Exponential Lower Bound for All-Success Aggregation: 2^H trajectory concentrability coexists with constant state–action concentrability in the hard deterministic finite-horizon construction.The behavior policy chooses both binary actions uniformly at every step, while the optimal policy concentrates on one trajectory.
E.2 Proof of Theorem 5: Exponential Lower Bound for All-Success Aggregation: The reduction converts policy value suboptimality into zero-one loss for estimating the hidden binary parameter θ.The induced estimator chooses the most likely action at each step under the candidate policy.
E.2 Proof of Theorem 5: Exponential Lower Bound for All-Success Aggregation: The observation laws for distinct parameters are indistinguishable unless sampled trajectories hit one of their two parameter-specific action vectors.The trajectory covariate is uniform and the all-success label equals 1 only for the matching action vector.
E.2 Proof of Theorem 5: Exponential Lower Bound for All-Success Aggregation: n ≤ 2^H−2 implies expected suboptimality at least 1/8, so achieving ε < 1/8 requires exponentially many trajectories.The lower bound applies to all possibly randomized offline learners through a two-point argument.
F Generalized Reinforcement Learning Theory: Generalized reinforcement learning restricts attention to Markov policies and stage-wise affine-in-continuation aggregation with terminal constant g.The generalized objective is defined as the expected recursively aggregated return under a candidate reward, recovering the main objective for the true reward.
F.1 Generalized Value Functions and Bellman Recursion: Affine continuation allows conditional expectations to commute with aggregation, yielding generalized action- and state-value functions.These values are defined under a policy and candidate reward and support the subsequent theory.
F.1 Generalized Value Functions and Bellman Recursion: The generalized value functions satisfy a backward Bellman recursion.The framework also defines state-value surrogates for arbitrary collections of stage-wise state–action functions.

F.2 Generalized Bellman Equations and Optimality … G.3 Auxiliary Lemmas

The appendix establishes generalized Bellman characterizations, a multiplicative performance-difference identity, and the proof machinery underlying the generalized outcome-based upper bound. Under contractivity, greedy policies are optimal, while auxiliary constructions control reward and trajectory-return discrepancies.

F.2 Generalized Bellman Equations and Optimality: Under ah(u) ∈[0, 1], the generalized Bellman optimality equation has a unique solution equal to Q⋆,r, and every greedy policy is optimal.The same characterization is summarized by Corollary 23.
F.3 Generalized Performance Difference Lemma: The generalized performance-difference lemma expresses policy-value differences as advantage terms weighted by prefix products of continuation factors.These multiplicative weights replace the additive-return decomposition.
G Proof of the Generalized Outcome-Based Upper Bound: The generalized upper-bound proof replaces per-step reward gaps with Bellman-operator gaps and weights policy occupancies by policy- and reward-dependent trajectory factors.The regret decomposition, concentration transfer, and AM–GM balancing follow the blueprint of the additive-return analysis.
G.1 Setup: The generalized population losses incorporate trajectory weights, generalized Bellman operators, and trajectory returns, while an r-free identity replaces the additive Bellman-error identity.Affine aggregation makes the one-step target unbiased after subtracting the conditional-variance-canceling baseline.
G.2 Generalized Regret Decomposition: The generalized regret decomposition splits performance differences into three terms whose right-hand side is independent of the chosen candidate reward.This independence follows from the r-free identity and the generalized performance-difference lemma at r⋆.
G.3 Auxiliary Lemmas: A measurable fake reward makes a critic Bellman-consistent with a policy, identifying the critic as that policy’s value function in an auxiliary MDP.The fake reward is a proof device, not an object estimated by the algorithm, and the Bellman inverse coefficient controls its discrepancy.
G.3 Auxiliary Lemmas: Under contractivity and Lipschitz assumptions, trajectory-return differences telescope through multiplicative continuation factors, yielding upper and L2 bounds used to control the generalized proof terms.The L2 control combines reward-model error with the fake-reward discrepancy bounded through χµ(σ) and generalized Bellman error.

G.4 Proof of Theorem 6

Theorem 6 is proved by decomposing the generalized policy gap, controlling its components uniformly over policies, rewards, and value functions, and combining the resulting bounds with pessimism and no-regret analysis. Tuning β and applying Young’s inequality yields the theorem’s stated statistical order, with lower-order remainders absorbed under the standard normalization.

Proof setup: Generalized OPAC applies Lemma 26 with comparator π⋆, current policy πk, and the selected pair (rk, fk), then averages the resulting decomposition over k.The averaging occurs on a single high-probability event supporting uniform concentration over Π × R × F.
Concentrability dependence: The generalized analysis introduces κµ(σ) through a change-of-measure step, while a trajectory-level alternative would replace κµCsa(π⋆) with κπ⋆Cτ(π⋆).The state–action concentrability form is retained for consistency with the rest of the paper, although the trajectory-level form can be tighter when µ covers π⋆ trajectories sufficiently.
Concentration bounds: The generalized Bellman, reward-model, and weighted policy-loss terms are controlled using concentration arguments adapted to nonlinear Bellman targets, trajectory returns, and trajectory weights.Bellman-completeness contributes the slack term 4εF,F, while weighted policy-loss summands remain bounded by O(HVmax).
Pessimistic algorithm gap: Pessimism compares the algorithm’s choice against (fbπ, r⋆), and generalized realizability plus Bellman analysis bounds the resulting approximation and model-error terms.The proof combines generalized performance-difference losses with residual bounds under rollout-induced state–action distributions.
Final combination: Choosing β and applying Young’s inequality cancels negative Bellman and reward-model terms; after normalization, lower-order terms are dominated and averaging adds the no-regret contribution to obtain Eq. (17).The aggregate slack is ¯ε := εBE + εRM + 4εF,F + 2εapx.

H Examples of Generalized Objectives · I The Underlying Statistical Problem: σ-Composition Regression · I.1 Regression formulation

The paper shows that generalized outcome objectives can be tractable or exponentially hard depending on information loss in scalar aggregation and generalized Bellman updates. It formalizes this issue through κ_μ(σ)-based σ-composition regression and illustrates the resulting guarantees and barriers across several objectives.

H Examples of Generalized Objectives: κ_μ(σ) measures how much scalar trajectory outcomes obscure distinct per-step reward profiles, while χ_μ(σ) measures compression in generalized Bellman targets.Large values of either coefficient can cause sample-complexity blow-ups; generalized OPAC is analyzed under structural conditions controlling them.
H Examples of Generalized Objectives: Under Assumption 4, generalized OPAC achieves the Theorem 6 guarantee with dominant statistical terms governed by κ_μ(σ) and χ_μ(σ).The bound holds up to the no-regret term in K and approximation errors.
H Examples of Generalized Objectives: For cumulative return, the generalized recursion becomes the usual Bellman backup, Assumption 4 holds with L = 1, and χ_μ(σ) = 1.The corresponding κ_μ(σ) bound matches setting κ_μ(σ) = 1 in Eq. (106).
H Examples of Generalized Objectives: Conditional continuation can produce identical scalar outcomes from catastrophically failing and steadily positive reward sequences, despite per-step feedback distinguishing them.Its hard gate is not Lipschitz, placing the exact objective outside Assumption 4.
H Examples of Generalized Objectives: Max-reward recursion is non-affine and therefore outside the generalized Bellman theory; if terminal rewards always dominate, κ_μ(σ) = +∞.Trajectory-level observations then cannot efficiently recover earlier per-step signals or support finite-sample complexity guarantees.
I The Underlying Statistical Problem: σ-Composition Regression · I.1 Regression formulation: σ-composition regression models i.i.d. covariate trajectories x_i, bounded scalar outcomes Y_i, and E[Y_i | x_i] = R(x_i; r⋆), with κ_μ(σ) capturing reward-recovery complexity.The coefficient is the supremum of pair-specific ratios comparing per-step reward differences with composed-outcome differences.

I.2 Minimax Rate for σ-Composition Regression · I.3 Proof of Theorem 31 · I.4 Proof of Theorem 32

The σ-composition regression results establish a high-probability upper bound for empirical risk minimization and a matching lower-bound framework showing that outcome aggregation imposes an additional κ-dependent minimax cost. The accompanying proofs use squared-loss concentration for the upper bound and a two-point Le Cam argument for the lower bound.

I.2 Minimax Rate for σ-Composition Regression: Theorem 31 gives a high-probability upper bound for any empirical risk minimizer under finite R, realizability, and bounded outcomes and predictions.The assumptions include r⋆∈R, |R(x; r)|≤Vmax, and |Yi|≤Vmax almost surely.
I.2 Minimax Rate for σ-Composition Regression: Outcome aggregation compresses per-step differences into R(x; r), causing control of ||r̂−r⋆||2 through outcome residuals to incur an extra factor of order κ.Theorems 31 and 32 together make κ explicit in the minimax rate.
I.2 Minimax Rate for σ-Composition Regression: Theorem 32 constructs hardness from two distinct candidates r and r′ separated by Δ2, with finite κr,r′(σ), under independent Gaussian outcome noise.The lower-bound setup isolates the information loss from compressing per-step structure into one trajectory outcome.
I.3 Proof of Theorem 31: Theorem 31’s proof rewrites the problem as squared prediction-error minimization for gr(x)=R(x; r), with population excess loss defined under µ.It introduces ℓr(x,Y)=(Y−gr(x))2 and an independent sample copy.
I.3 Proof of Theorem 31: The upper-bound proof applies one-sided Bernstein concentration to excess-loss variables, sets η=δ/|R|, and uses a union bound over r∈R.The empirical risk minimizer satisfies ED[Zr̂]≤0, enabling the final population-error bound.
I.4 Proof of Theorem 32: Theorem 32’s proof compares the laws induced by r and r′, which differ conditionally on x only through the mean of a Gaussian with variance Vmax^2.The candidates are Δ-separated, and the two-point Le Cam method yields the lower-bound condition.