Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
Authors: Fan Chen
Zeyu Jia
Alexander Rakhlin
Tengyang Xie
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning theory
online exploration
outcome-based RL
sample efficient RL
Primary area: theory

Abstract: Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop a provably sample-efficient algorithm achieving $\widetilde{O}({C_{\rm cov} H^3}/{\varepsilon^2})$ sample complexity, where $C_{\rm cov}$ is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large or infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome-based feedback is statistically separated from per-step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assumption, dramatically simplifying the algorithm. We further extend our approach to preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute a theoretical foundation for understanding the statistical properties of outcome-based reinforcement learning.

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
Fan Chen"
Zeyu Jia" zyjia@mi t.ddu
Alexander Rakhlin' rakhlin@mit.ecm
Tengyang Xie txêcs. wisc.edu
fanchen@mit, ttt.uuiiiiituuuuuuu....
Abstract
Reinforcement learning with sarromme-based feedback faces a fundamental chal- lenge: when rewards only observed trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop provably sample-efficiet algorithm achieving OCC.ov H /62) sample complexity, where Ccov is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome- based feedback is statistically separated from per- step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assump- tion, dramatically simplifying the algorithm. We further extend our approach preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute theoretical foundation for understanding the statistical properties of outcome-basee reinforcement learning.
Introduction
Reinforcement learning with outcome-based feedback is fundamental paradigm where agents receive rewards only at the end of complete trajectories rather than at individual steps. This feedback model naturally arises in many applications, from large language model training (Ouyang al., 2022: Bai et al., 2022; Jacch et al., 2024), where human preferences are provided for entire outputs rather than individual tokens, to clinical trials, where patient outcomes are only observable after complete treatment regimen. Despite the prevalence of such settings, the statistical implications of outcome-basee feedback for online exploration remain poorly understood.
In traditional reinforcement learning (Sutton et al., 1998), agents observe rewards immediately after each action, providing granular signal that directly links actions their consequences. In contrast, outcome-based feedback presents a fundamental challenge: when rewards are only observed at the trajectory deterniinnn which specific actions contributed the final outcome becomes significantly more difficult, This credit assignment problem particularly acute sequential maniinnn-maiiggg tasks with long horizons, where many different action combinations could lead to the observed outcome.
While recent work (Jia et al., 2025) has shown that sascome-based feedback is sufficient for offline reinforcement learning under certain conditions, the feasibility of efficient online exploration with only trajectory-leve feedback remains open question. Online learning caaning-where where agent actively explores to gather new data- essential for adaptive systems that must learn in dynamic environments without pre-collected datasets. This leads our central question:
When is online exploration with outcome-based based reward statistically tractable?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This question has been studied in the setting where the reward function is assumed to be well- structured (Efroni al.. 2021: Pacchiano et al., 2021; Chatterji et al., 2021; Cassel et al., 2024; Lancewicki and Mansour, 2025), with primary focus on the linear reward functions. Similar reliance on the well-behaved reward structure" also appears in the recent work on Reinforcement Learning from Human Feedback (RLHF) (Chen et al., 2022b,a; Wu and Sun, 2023; Wang et al., 2023), where only preference feedback is available. However, well-behaved reward structure is dedicated and might fail to capture many weal-world scenarios with general function approximation. In this paper, we address this question by providing a comprehensive theoretical analysis of outcome-basee online reinforcement learning with general function approximation. We investigate when efficient exploration is possible with only trajectory-Iever feedback and characterize the fundamental statistical limits of learning in this setting. Our main results are as follows:
(1) We present model-free algorithm for outcome-based online RL with general function approxi- mation (Algorithm 1) that relies solely on trajectory-level reward feedback rather than per-step feedback. Our algorithm achieves a complexity bound of Ô(Cenv ((C /E²) under standard realiz- ability and completeness assumptions, where Crov is the coverability coefficient that measures an intrinsic complexity of the underlying MDP. This bound applies in the general function approxi- mation setting where state spaces may be large or infinite, requiring only that value functions can be represented by an appropriate function class with bounded statistical complexity.
(2) For the special case of deterministic MDPs, present simpler algorithm based on Bellman residual minimization (Algorithm 2) that achieves similar theoretical guarantees with improved computational efficiency.
(3) As extension, we generalize our approach to preference-based reinforcement learning (Section 4), where feedback comes in the form of binary preferences between trajectory pairs under the Tradley-Terry-Lutt model. This extension bridges the gap practical reinforcement learning from human feedback (RLHF) scenarios, where even outcome reward feedback is rare.
(4) We also identify fundamental separation between outcome- and per-step feedback (Sec- tion 5). Specifically, there exists a MDP with known transition dynamics and horizon H 2, and the reward being a d-dimensional generalized linear function, while in this problem ef(d) samples are necessary to learn near-optimal policy with only outcome reward. However, such problem is known to easy with per-step reward feedback, in the sense that existing algorithms can return an e-optimal within Odd rounds with per-step feedback. This separation demonstrates that delicate analysis based well- bellveh reward structure can fail catastrophically when only outcome reward feedback is available.
Our results provide a theoretical foundation for understanding when outcome-based exploration is tractable and when it presents insurmountable statistical barriers. By characterizing these fundamental limits, we offer guidance for the development of efficient algorithms for learning from trajectory-leve feedback in online settings and highlight the precise conditions under which outcome-based feedback is statistically equivalent to per-step feedback.
2 Preliminaries
Markov Decision Process. An MDP M is specified by a tuple p,,,,TT,,RRRA with state space A(S)) initial state
S, action space A, horizon H, transition kernel = (T, : S x distribution م E (S)). and the mean reward function R (R, : S A + [0, 1)) At the start of each episode, the environment randomly draws an initial state 81 p, and then at each step h E [+] after the agent takes action (a,, the environment generates the next state 8h+1 ~ T(-ss,, ).). The episode terminates immediately after aæ is taken, and, for notational simplicity, we denote sH+1 to be the deterministic terminal state. We denote
41, 8H ag) to be the trajectory, and throughout this paper we always assume the reward function is normalized, i... R(F)= D Ri, an) E [0, 1] almost surely.
In addition to the states, the learner may also observe the reward feedhack after the episode terminates. In the process reward feedback setting, the learner receives a random reward vector (r1, ,"H) E
MMore specifically, most of the recent work either assume the reward class is linear or admits low eluder dimension (as a function of the trajectory).
2

---

[0, 1_" such that B[ra/T] = (sk: an) for each h E [H]. In the outcome reward setting, the learner only receives single reward value [H] such that E[[[r] Σ (s,, 0h).
Policies, value functions, and the Bellman operator A (randomized) policy x is specified as {TH S + ((A)), and it induces distribution P" of trajectory (81, ",,'.. 8r,, a by p. and for each h E [H]. an T((88) 8h+1 ~ Ta(sn, on). We let ["[.] to be the corresponding expectation.
The expected cumulative reward of a policy is given by J(T) = 18 E Ru(sh; an) The value function and Q-function of defined as
H
(s) =
Σ
Re(se, E=h
8h =
(T( = E
Σ
Re Re(se, at) 8/ 0, 1=h
Let π¹ denote optimal policy (i.c., x² argmax, (T))., and let V* and Q be the corresponding value function and Q-function. It is well-known that (V*,²*) satisfies the following Bellman equation for each E S, A, E [M]:
V (+) = max (7 a),
(x( = (s, a) + BewTT (i+z(''),
(I)
aεA
with the convention that + O. Therefore, we define the Bellman operator Th as follows: for any f x A R. Tu. defined as
[T,.f a) == (s, a) + (1 max f(s', a'), a'EAA
(2)
Then, is straightforward verify that the Bellman equation reduces to Q
Th for [4]] Complexity measure of the MDP. Coverability is natural notion for measuring the difficulty of learning in the underlying MDP (Xie et al., 2022).
Definition 1 (Coverability). For given MDP M and a policy class II, the coverability Ceov defined as
d
Ccov (II: M) =
min M1. ()
max MEI
where
4x
maE, H4 (s,a)
(s,a,))
The coverability coefficient of an MDP is an inherent measure of the diversity of the state-action distributions. Our main upper bounds scale with the coverability of the underlying MDP M and in this case we abbreviate Ceov((I) == Ceov (TI; M*) for succinetness.
Function approximation. In this paper, work with (model-free) function approximation, where the learner have access to a value function class F = Fi x ... FH and a reward function class RH with each Fr, Rr (S x A [0,10]]
R = R,
The function class J and R consist candidate functions to approximate Q* and the ground-truth reward function R In the literature of RL with general function approximation, it is typically assumed that the function classes are realizable, i.c., Q* F and R E R. In this paper, we adopt the following relaxed realizability condition with a fixed approximation error Eapp 0.
Assumption 1 (Realizability). There exists Q E F and R E such that max 11 -% z
Eapp. maX | R loc I Eapp-
For each value function f E F. induces greedy policy y given by (s) argmax f(s. a). Therefore, the value function class induces a policy class II := { : f FJ. and we take our policy class II = II for the remaining part of this paper.
The complexity of the function class is measured by the covering number.
Definition 2 (Covering number). For a function class H C (X - R) and parameter a 2 0, an a-covering of H (with respect to the sup norm) is subset Ht' C H. such that for any f E H. there exists f e H' with supsex (f()) (x)) < a. We define the a-covering number of H as N a) == min H' is a-covering of H}.
In the following, always write H² for the true reward function avoid confusion.

---

Bellman operator. A reward function R = (R1, ... RR) E R induces a Bellman operator as [TRA/](s, a) = (8, a) + Ey' (-le,)) max I (8', ,'), YS = (,,,-" .SH) E
a'EAA
where we also adopt the notation fH+1 0 for any F.. Most literature on RL with general
function approximation also makes use of a richer comparator function class g = x ..... x GH that
satisfies the following Bellman completeness (Jin et al., 2021a; Xie al., 2021, 2022. etc.).
Assumption 2 (Bellman completeness). For each [H). Fk S 9h. For any f E F and R, holds g.... I|TR,ff - gull I Cupp for h E [H].
Miscellaneous notation. For any p E [0, 1], we define Bern(p) to be the Bernoulli distribution with P(X = 1) p. For functions f and g 2 0, we use f = O(g) to denote that there exists a universal constant C' such that f S C. g.
3
Sample-Efficient Online RL with Outcome Reward
In this section, we present model-free RI. algorithm with outcome reward, which achieves sample complexity guarantee scaling with the coverability coefficient and the log-covering number of the function classes.
3.1 Main Result
We present Algorithm 1, which is based on the principle of optimism. For simplicity of presentation, assume that the initial state 8, is fixed.
The crux of the proposed algorithm outcome reward, in contrast to most existing RL algorithms (with general function approximation) that make use the process reward (ri. .TH) to fit the Q-function for each step (Du et al., 2021; Jin al., 202 la, etc.). A natural first idea is to fit, given dataset D {(T, r)} consisting of previously observed (trajectory, outcome reward) pairs, a reward model from the reward function class R by optimizing the following reward model loss:
new method for performing Fitted-Q Iteration with only
H
2
RM (R) (R)
Σ (T.))ED
Σ A==
Rs (8h. (sh.an) an)
-
As discussed below in Remark 1, directly fitting estimated reward model based CBM can lead to bad performance. Instead, our algorithm jointly optimizes over the value functions and reward models, detailed below.
For any proxy reward model R E R and value function f E F,F we define the Bellman error at step h [ as
Conl == Σ
(fa(s): an) - RR on) max fa+ ( (4)
(T.))D
a measure of violation of the Bellman equation (1) with the proxy reward model R. Then, we introduce the Bellman loss defined as
H1
H inf gEG A=1
C (f: R) = Σ (fnn hml
Σ Ep fh R),
(5)
where we subtract the infimum of E 9 over the helper function class G, a common approach to overcoming the double- sambligg problem (Antos et al., 2008; Zanette al., 2020; Jin et al., 2021a; Liu et al., 2023b).
Algorithm. First fix arbitrary policy nee (can be the policy which takes arbitrary action on al states). The proposed algorithm takes in a value function class F, reward function class R and comparator function class G. and performs the following two steps for each iteration = 1,2, ... .T:
(Optimism) Compute optimistic estimates of (Q", R*) through solving the following joint maxi- mization problem with the datasct D consisting of all previously observed (trajectory, outcome reward) pairs:
(())
=
max REJ,RER
Af((s)) C (f; Rt) - (1)).
(6)

---

Algorithm Outcome-Based Exploration with Optimism
input: Q-function class F, reward function class R, comparator class 9, parameter À reference
policy ref--
initialize: + 0.
for 1....... do
2:
Compute the optimistic estimates:
( (R)
max A1((81) LD (J: R) LD (IR)
JEF,RER.
3:
Select policy T/ <- y(t)
4: for 1,2, H do
5: Execute Th on, Tref for one episode and obtain (T(NA), p((r)))
6: Update dataset: 'D
(TTSs) }.
7: end for
8:
end for
9:
Output मे Uni((
where for any f E F we denote fi())) == A (1111.00 a) to be the value of f at the initial
state. Therefore, the optimization problem (6) enforces optimism by balancing the estimated
value (1()) and the estimation error L (f: R) + LBM(R (R) though
À 2 0.
(Data collection) Based on the optimism estimate f the algorithm selects π == - To collect data, the algorithm then executes the exploration policies π on 'ref for each E [H] where for any policy æ and Tref, let и о₁ Tzet be the policy that executes for the first h steps, and then executes Tref starting at the (h + 1)-th step.
Theoretical analysis. For Algorithm which scales with the coverability Crov = Caov (IIx), where ΙT = {my E F} is the policy class induced by F. To simplify the presentation, denote log Nr infa20 (log N N(a) Ta), where ((a)) is defined as
provide the following sample complexity guarantee,
N(a) = max (N(F,, N(R,, NN, a.).
ke(ff
With the function classes being parametric, is clear that log Nr S log(T))
Theorem 1. Let 8 E (0, Suppose that Assumption I and Assumption hold, and the parameters are chosen as
H log(NTHH//)
T Coov 122 1f log(T))
X = max
T THEppp
log(NTrra/0)
(7)
x2
where co, > O are absolute constants. Then with probability at least 1 - 8, the output policy स of Algorithm 1 satisfies V*(si) V$ 5 O log(T") -App))
The proof of Theorem is deferred to Appendix C. Particularly, we note that when the function classes satisfy log Ny < (dd and app = 0, Algorithm outputs an e-optimal policy with sample complexity
TH S SŌ CooudH2
Notably, the coverability Coov measures the inherent complexity of the underlying MDP M (Xie et al., 2022) and it is independent of the reward function class. As our result only depends on the coverability Ccov and the statistical complexity of the function classes, does not rely on the structure of reward functions, while previous works assume the reward functions are either linear (Efroni et al., 2021; Cassel et al., 2024) or admit low trajectory eluder dimension (Chen al., 2022b,a).
Remark 1. In Algorithm the reward functions B and Q-functions f are jointly optimized (see Eg. (6)). A natural question is whether these can be optimized separately first learning fated reward model and then applying optimism to the Q-functions based on the learned reward model. We
5

---

Algorithm 2 Outcome-Based Exploration with Optimism for Determinsitic MDP
input: Function class F, parameter À > O. initialize: + 0. initial estimate for E I: for = 1, ........ . do
2: Receive s(t) and compute the optimistic estimates:
f max (f1(s LBB (n). feJ
3: Select policy g( f- " y(o)
4: Execute (1) to obtain a trajectory 7( = ,d a1) (0)
H aH)
with outcome reward p(t)
5: Update dataset: D < D u {(rl), r(t))].
6: end for
7: Output म (1:))
show that this decoupled approach can lead to failures: due to reward model mismatch, the algorithm may become 'trapped' in regions where the exploratory policy fails gather informative data. As result, the sample complexity can become infinite in the worst case. See Section F.1 in the appendix for details.
3.2 A Simpler Algorithm for Deterministic MDPs
A disadvantage of Algorithm is that it requires solving max-min optimization problem (6), as the Bellman loss C involves a minimization problem over G. While such computationally inefficient optimization problems are the common subroutines of existing function approximation RL algorithms (Jin et al., 2021a; Foster al., 2021, 2022; Chen et al., 2022a, etc.), turns out that Algorithm I can be significantly simplified when the transition dynamics in underlying MDP are deterministic.
Assumption 3. The transition kernel T is deterministic, for any [H] and sh S, ap A. there is unique state Sh+1 E S such that Tr(s4++ Sh, 44)) =
Note that in this setting, the initial state 81 and the outcome reward r can still be random. This setting also referred as Deterministic Contextual MDP in Xie et al. (2024).
Value difference as reward model. A key observation that, when the underlying MDP M is deterministie, the Bellman equation (1) trivially reduces to the following equality
(i an) R (sh, an)) + V
which holds almost surely. Hence, for any trajectory T, it holds that
Rd (*(T) Σ R (sh, a+) = Σ [Qi an) Vh (86+1)]
Therefore, any value function f E induces an outcome reward model R (SxA)) IR defined as
RÉ RT(T)) [n(s,, an) In
where we adopt the notation fa(s) = max.EA (a(s,a) for E [H]. This observation motivates the following Bellman Residual loss:
H
2
(BR(F) = Σ
Σ
(sn - (n+t()))))
(8)
(T.))DD
where D ((TTT)) is any dataset consisting of (trajectory, outcome reward) pairs.

---

Bellman Residual Minimization (BRM) with Optimism. For deterministic MDP, we propose Algorithm 2 as simplification of our main algorithm. Similar Algorithm the proposed algorithm takes in the value function class F and alternates between the following two steps for each round t -,,,,..,,7
1. (Optimism) Compute optimistic estimates of Q* through solving the following maximization problem with the dataset ID consisting of all previously observed (trajectory, outcome reward) pairs:
n
max Af((s)) - ())))) fEF
enforcing optimism by balancing the estimated value (31) and the Bellman residual loss C (f).
2. (Data collection) Based on the optimistic estimate f selects T6 == yos and collect a trajectory
7(1 (sf) ................................ H (H) with outcome reward p(())
Compared to Algorithm 1, Algorithm 2 has the several advantages. First, it does not rely on the reward function class R and the comparator function class G, and the Bellman residual loss LB is much simpler than the Bellman loss CB thanks to the deterministic nature of the underlying MDP. Therefore, Algorithm is more amenable to computationally efficient implementation, as replaces the max-min optimization problem (6) in Algorithm with much simpler maximization problem (9). Further, for every round t, the algorithm only needs to collect one episode from the greedy policy x(
Theoretical analysis. We present the upper bound of Algorithm 2 in terms of the following notion of coverability.
Cevv (II) == Cov (11; M,,),
where MM is the underlying MDP, M the MDP with deterministic initial state 8 and the same transition dynamics M and II II is the policy class induced by F. In general, C (II) is always an upper bound on the coverability Coov (II), and the guarantee of Algorithm 2 scales with Co (II) as it avoids the layer-wiss wise exploration strategy of Algorithm 1. We also denote
log NET == inf max N aF,,
a) hE[H]
a20
Theorem 2. Let E (0, 1). Suppose that Assumption I holds, and the parameters are chosen as
H log (og(N5,1/8) ,Teapp J: T2 Cooo H)H 1og(Nz,,7/), (10)
X Co
E²
where Co, > 0 are absolute constants. Then with probability at least 1 - ō, Algorithm achieves
T
Σ (
- (o1)) $E+ (I)) log(T) Eapp).
The above upper bound provides the PAC guarantee through the standard online-to-batee conversion,
and its proof deferred to Appendix D. It is worth noting that Theorem only relies on realizability assumption on the Q-function class F, significantly relaxing the assumptions of realizablity (As- sumption 1) and completeness (Assumption 2) Theorem As remark, we note that Theorem implies that Algorithm in fact achieves regret bound of order /T.
Preference-based Reinforcement Learning
The goal of preference- basedd based learning is find a near-optimal policy only through interacting with the environment that provides preference feedback. As an extension of our results presented in Section in this section we present similar algorithm for preferecc-bbssed RL with the same sample complexity guarantee.
*The (expected) regret of the algorithm can be defined as Reg(T) = ET (V*)) - V= (x("((("))) (s("))
7

---

Preference-basse learning in MDP. In preference-based RL, the interaction protocol of the learner with the environment specified as follows. For each round .....
The learner selects policy zf1.1) and T'
The learner receives trajectories 7(t+) x 2(01) -(t,) xt",), and preference feedbback y
Bern(C(r (((-)) where C. is comparison function.
Intuitively, for any trajectory pair (r+, the comparison function C(r+,T~) P(r+ measures the probability that 7+ is more preferred. In this paper, we mainly focus on the Bradley- Terry-Luce (BTR) model (Bradley and Terry, 1952), which is widely used on RLHF literature. We expect that our algorithm and analysis techniques apply to broader class of preference models.
Definition 3 (BTR model). The comparison function is specified
exp (T
, exp (3R + exp Exp(3R (T))
where Re is the ground-truth reward function, 3 > 0 is a parameter.
Under BTR model, the preference feedback fact contains information the outcome rewards. Hence, in this sense, preference-based RL can be regarded as extension of outcome-based RL with weaker feedback.
Algorithm for preference- RL. To extend Algorithm 1, we need to modify the reward model loss CRM (defined in (3)) incorporate preference feedback. For any dataset D (T consisting of (trajectories, preference) pair, we introduce the following preference-based reward model loss CPBRM.
CD
PbRM (R)
=
Σ L(B(T*) (r+,r WEDD
(1I)
where L(w,y) := -Bwy log(1 + cBw)) is the logistic loss. It is well-known that under BTR model (Definition 3), the ground-truth reward R is the population minimizer of CPRRM, and any approximate minimizer of CPPRM can serve proxy for R'. Therefore, with the loss function CPbRM we propose the following algorithm (Algorithm 3, detailed description in Appendix E), which generalizes Algorithm 1 to handle preference feedback: For each iteration 1.2.- the algorithm performs the following two steps.
(Optimism) Compute optimistic estimates of (Q", R²) through solving the following joint maxi- mization problem with the dataset DD consisting of all previously observed (urajectories, feedback) pairs:
R())=
> {[1(s))
Szef D.R
CB R)
CPRRM (P)RM(R). (R),
(12)
JEF,RER
where the Bellman loss CB is defined in (5), Diref is the estimated value function of Tre defined D.R R
as
Free = D.R
Σ R(T
(13)
D
(r
MlED
The term (11) - Pref
D.ft can be regarded as estimate of the advantage of F over under (f, R). It is introduced to avoid over-estimating the optimal value, the preference feedback only provide information between the difference between two trajectories.
2. (Data collection) The algorithm selects the greedy policy ( := T() For each h E [H], the algorithm sets ((GA,)) 1) = π On Tref and ((.... = Tref. executes (t.611,) ((.., ?) to collects trajectories (T(6.,)) ylu., 1) and the preference feedhack (t.
We provide the following sample complexity guarantee of the algorithm above.

---

Theorem 3. Let 5 E (0,1), 1). Suppose that Assumption I and Assumption 2 hold, and the parameters of Algorithm are chosen as
H Moogg(Nrr NTH/ Sapp
T o Coov (o
X = Co max
(14)
where co is an absolute constant, and O.) omits moly-logarithmic factors and constant depending
on B. Then, with probability at least 1 - 8, the output policy मे of Algorithm 3 satisfies
(*(s)) - (s)) 5
The proof of Theorem is deferred to Section E.
Lower Bounds
As shown by Theorem 1, with bounded coverability of the MDP and appropriate assumptions on the function classes, finding near-optimal policy within a polynomial number of episodes with outcome rewards is possible. In this setting, our sample complexity bounds match the sample complexity of Algorithm GOLF (Jin et al., 2021a; Xie et al., 2022), up to factor of O(H). This indicates that, under bounded coverability, learning with outcome-based rewards is almost statistically equivalent to learning with process rewards.
Additionally, in the setting of offline reinforcement learning with bounded uniform concentrabillty, the results of Jia et al. (2025) indicate that there is also statistical equivalence between learning with outcome rewards and learning with process rewards. Therefore, it is natural ask the following question:
Is learning with outcome rewards always statistically equivalent to learning with process rewards in RL?
However, it turns out that the answer is negative if the statistical complexity is measured with respect to the structure of the value (reward) function classes.
More specifically, we construct a class of MDPs with horizon H = 2, known transition T, and d-dimensional generalized linear reward models (Appendix F.2). With process reward feedback, such problem is known to be easy as it admits low (Bellman) eluder dimension (Russo and Van Roy, 2013; Jin al., 2021a, etc.), and existing algorithms can learn an e-optimal policy using (dl /E²) episodes with process rewards. However, given only access to outcome rewards, we show that this problem is as hard as learning ReLU linear bandits (Dong et al., 2021; Li et al., 2022), and hence it requires least e((d) episodes to learn. Hence, in this setting, there is exponential separation between learning with process rewards and learning with outcome-basee rewards.
Theorem 4. For any positive integer d 2 1, there exists a class M of two-layer MDPs with a fixed transition kernel T. and initial state 8t, such that the following holds:
(a) There exists an algorithm that, for any MDP M E M and any E E (0, given access to process reward feedback, returns an e-optimal policy with high probability using ((e (e2) episodes.
(b) Suppose that there exists an algorithm that, for any MDP M E M, given only access to outcome reward, returns a 0.1-optimal policy with probability at least & using T episodes. Then it must hold that T = ((e where e₁ is an absolute constant.
This exponential separation demonstrates that the delicate analysis based on well-behaved Bellman errors (Jiang et al., 2017; Jin et al., 2021a; Du et al., 2021, etc.) crucially relies on the process reward feedback, and the resulting guarantees might not be preserved in the setting where only outcome reward feedback is available.
'We note that under this construction, it straightforward to construct function classes F and R such that both Assumption 1 and Assumption hold, but the coverability scales Ccor A(d)

---

6 Conclusion
In this work, we develop model-free, sample-efficient algorithm for outcome-based reinforcement learning that relies solely on trajectory-level rewards and achieves theoretical guarantees bounded by coverability under function approximation. From the lower bound side, we show that joint optimization reward and value functions is essential, and establish a fundamental exponential gap between outcome-based and per-step feedback. For deterministic MDPs, we propose a simpler, feedback, demonstrating that
more efficient variant, and extend our approach to preference- it preserves the same statistical efficiency. In the current work, only studied the case where the outcome-basee reward is the sum of all intermediate rewards. We leave the development of efficient algorithms for other types of aitcome-based rewards future work.
Acknowledgements
We acknowledge support of the Simons Foundation and the NSF through awards DMS-2031883 and PHY-2019786, ARO through award W91 19F-21111--- and the DARPA AIQ award.
References
Philip Amortila, Dylan J Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning. arXiv preprini arXiv:2401.0966 2024a.
Philip Amortila, Dylan Foster, and Akshay Krishnamurthy. Scalable online exploration via coverability. arXiv preprint arXiv:2403.0657/ 2024b.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71:89-129, 2008
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0586. 2022.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
Mohak Bhardwaj, Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning. Advances Neural Information Processing Systems, 36, 2023.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-34) 345, 1952.
Asaf Cassel, Haipeng Luo, Aviv Rosenberg, and Dmitry Sotnikov. Near-optimal regret in linear mdps with aggregate bandit feedback. arXiv preprint arXiv:2405.0760 2024.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivizee preference optimization: A unified approach online and offline rlhf. arXiv preprint 2tt.:::2205.19920.. 2024.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with mece-pe--episode feedback. Advances in Neural Information Processing Systems, 34: 3401-3412, 2021.
Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimation coefficients: pac, reward-free, preference-basee learning, and beyond. arXiv preprint arXiv:2209. 2022a.
Fan Chen, Constantinos Daskalakis, Noah Golowich, and Alexander Rakhlin. Near-optimal learning and planning in separated latent mdps. In The Thirty Seventh Annual Conference on Learning Theory, pages 995-1067. PMLR, 2024.
Jinglin Chen and Nan Jiang. Eiformation-thoorete considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
10

---

Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-ing in-the-loopp Provably efficient preference- reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022b.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In st Annual Conference on Learning Theory, number 101, pages 355-366, 2008.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rlhf via active preference optimization. arXiv preprint arXiv:2402. 10500, 2024.
Kefan Dong. Jiaqi Yang, and Tengyu Ma. Provable model-basee based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34:26168 001666688261888 26182, 2021.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Leurning, pages 2826-2836. PMLR, 2021.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference artificial intelligence, volume 35, pages 7288-7295, 2021.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances in neural information processing systems, 23, 2010.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13487, 2021.
Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35:35404 35417, 2022.
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Camney, et al. Openai ol system card. arXiv preprint arXiv:2412.16670, 2024.
Zeyu Jia, Alexander Rakhlin, and Tengyang Xie. Do we need to verify step by step? rethinking process supervision from a theoretical perspective. arXiv preprint arXiv:2502.10581, 2025.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34:13406-13418 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021b.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pages 267-274, 2002.
Tal Lancewicki and Yishay Mansour. Near-optimal regret using policy optimization in online mdps with aggregate bandit feedback. arXiv preprint arXiv:2502. 24000005502.00004, 2025.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Gene Li, Pritish Kamath, Dylan Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 01-23737-23750) 2022.
Fanghui Liu, Luca Viano, and Volkan Cevher. What can online reinforcement learning with function approximation benefit from general coverage conditions? In International Conference on Machine Learning, pages 22063-22091. PMLR, 2023a.
Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. Maximize explore: One objective function fusing estimation, planning, and exploration. Advances in Neural Information Processing Systems, 36, 2023b.
11

---

Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567. Citeseer, 2003.
Gergely Neu and Gábor Bartók. An efficient algorithm for learning with semi-bandit feedback. In International Conference on Algorithmic Learning Theory, pages 234-248. Springer, 2013.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncerlainty in Artificial Intelligence, pages 1029-1038, PMLR, 2020.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, volume 27, pages
2014.
Long Ouyang. Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jomathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2 11.0110.0 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, volume 26, pages 2256-2264, 2013.
Wen Sun. Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rl? arXiv preprint arXiv:2306. 2423.
Runzhe Wu and Wen Sun. Making with preference-basee feedback efficient via randomization. arXiv preprint arXiv:2310. 1.0.24440..44 2023.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 11404-11413, PMLR, 2021.
Tengyang Xie. Ching- An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint 17X1v22210004157, 2022.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit qt-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21044 2024.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18894 2020.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314, 2024.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pages 10978-10989, PMLR, 2020.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason Lee, and Wen Sun. Provable offline preference-based reinforcement learning. arXiv preprint 2305:23005.4816 2023.
12

---

Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang, Shuohang Wang. Hany Hassan, and Zhaoran Wang. Sell-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405.1933. 2024.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning. pages 43037-43067. PMLR, 2023.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] provided a proper justification is given (e.g., "error hars expensive" " or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims made in the abstract and introduction accurately reflect this paper's contributions and scope. More supporting details are included in the main text.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
This paper discussed the limitations in the main body below each theorem.
14

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: This paper provides the full set of assumptions in the main body and complete (and correct) proof in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co for more details.
blic/gut guides/Codeeeee staide/s/coeuunnissiioooiii.o..
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: Sooeee////ooeeeiieeceeeeee swi.mmolsooooooooooooooo for more details.
/ //nips. cctpsccccpblll/
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps: httpp/cc//bbccccctcccccuuieeee
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: performed.
This is pure theoretical paper. There is no societal impact of the work
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
18

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ee-ackaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
19

---

Justification:
for This paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Please refer to our LLM policy peattp::/neuripstt //tperrpp.ccccoofeeeeeee//////// what should or should not be described.
20

---

A More Related Works
We review more related works this section.
The coverability coefficient has recently gained attention in the theory of online reinforcement learning (Xie et al., 2022; Liu et al., 2023a; Amortila et al., 20)4a.b). This condition is in the same spirit as the widely used concentrability coefficient (Munos, 2003; Antos et al., 2008; Farahmand al., 2010; Chen and Jiang, 2019; Jin et al., 2021b; Xie and Jiang, 2021; Xie al., 2021; Bhardwaj et al., 2023), a concept frequently employed in the theory of offline (or batch) reinforcement learning. well-known duality suggests that the coverability coefficient can be interpreted as the optimal concentrability coefficient attainable by any offline data distribution. For further discussion, see Xie et al. (2022).
A related body of theoretical work explores reinforcement learning with frejectoryfeedback (Neu and Bartók, 2013; Efroni et al., 2021; Chatterji al., 2021; Cassel et al., 2024; Lancewicki and Mansour, 2025), where the learner receives only episode-level feedback at the end of each trajectory. This category also encompasses preference-based reinforcement learning (Pacchiano et al., 2021; Chen et al., 2022b; Zhu et al., 2023; Wu and Sun, 2023; Zhan et al., 2023), which relies on pairwise comparisons between trajectories. While most prior work focuses on tabular or linear MDP settings, we take a step further by studying learning with function approximation, and bound the complexity by the coverability coefficient.
In the context of Online Reinforcement Learning, numerous prior works have investigated the complexity of exploration and policy optimization, introducing various complexity measures such as Bellman rank (Jiang et al., 2017), Eluder dimension (Russo and Van Roy, 2013; Osband and Van Roy, 2014), witness rank (Sun et al., 2019), Bellman-Eluder dimension (Jin al., 2021a), the bilinear class (Du et al., 2021), and decision-estimation coefficients (Foster et al., 2021). These complexity notions characterize properties of the function model class but are generally not instance-dependent. In contrast, Xie et al. (2022) introduces the pestance-dependee provide complexity bounds in online reinforcement learning. For further discussion on instance- dependent complexity measures, we refer the reader to the discussions therein.
notion of coverability coefficients to
We further review some literatures on online preference-based learning online RLHF. Xu et al. (2020); Novoseller et al. (2020); Pacchiano et al. (2021); Wu and Sun (2023); Zhan et al. (2023); Das et al. (2024) provides theoretical guarantees for tabular MDPs and linear MDPs. Ye et al. (2024) studies RLHF with general function approximation for contextual bandits, which is equivalent to the case where // = 1. Chen et al. (2022b); Wang al. (2023) use the Eluder dimension type complexity measures to characterize the sample complexity of online RLHF, which sometimes can be too pessimistic. Xie et al. (2024); Cen al. (2024); Zhang et al. (2024) proposed algorithms for online RLHF with function approximation, but their complexity depends on the trajectory coverability instead of the state coverability
B Technical tools
B.1 Uniform convergence with square loss
To prove the uniform convergence results with square loss, we frequently use the following version Freedman's inequality (see e.g., Beygelzimer et al., 2011).
Lemma 5 (Freedman's 's inequality). Suppose that 7 _0..... .... is a martingale difference sequence
that is adapted to the filtration (8 and Z < C almost surely for all t E (T). Then for any A E [0, t) with probability at least 1 - ö, for all n S T,
D + log(1/6)
Σ
E (Z
X
1=1
Lemma 6. Suppose that (x yy()) ).... (x (T) is sequence of random variable in X x (0, C
that is adapted to the filtration (E= such that there exists a function F= : X + [0, 1 with F* (x = (/ (ztt"), "0' almost surely. Then for any function F X + [0, C). it holds that with probability at least 1 1-6 for all n E [T]
2
n
(F( - 2
Σ (F ) 2
E (F(x - (=(011)) gu-1]] - 100 log(1/6).
2
21

---

Conversely, it holds that with probability at least 8, for all n E [T',
(F(x!)) - y00
Σ
8r 1 gu + 50 log (1/8). (F" - y002² - 2 B -
1=1
1=1
Proof of Lemma 6. Denote
W == (F(x!0)) - -00 (F* (x(1)) y/o)2
(F(z!")) - F* (x² 2(F(x - Fr - )0))
Note that
E || 8 81-1 E (F(x10) F (2:01)) gu-11
and
2 = W - E [ S / < C².
Therefore, using Freedman's 's incquality (Lemma 5), for any fixed X E 10, cta we have with probabil- ity at least 0,
(1/0)
Σ t=1
700
+ A (Z (
Vn E [7].
1=1
Note that
(2w)² 8--10
S 1E (1
= F (F(x)") - F )) 4 + 4(F(x()) - (F((")))((((( - / gie 2r
<50 (F(x - F" (x)0))) g g(m1))
Therefore, by setting X = .ल we get the desired upper bound.
Similarly, for the lower bound, we can apply Freedman's inequality with (-20) to show that for 10C2, with probability at least 1 - 8,
(2 8 21 + log(1/8) E
7
A
A
1=1
(F(2)0)- - (z(211)) gup ('((00)))/88-11)
+ 100 log(1/0), Vn E [Z'].
Proposition 7. Fix a parameter a 2 O. Under the assumption of Lemma 6, suppose that H C (X - [0, CT) is a fixed function class, and Få E H satisfies || 12 S Eapp. Define
n
Cx(F) = ] (F(x "0
Ex(F) = Σ E -((""))F"((""")) 8(-1))1
Let 15C (2,, 0)8) + 3Cna + 4nc2 2pp Then the following holds simultaneously with probability at least 6:
(1) For each E [T].
inf FEEH
C. S k.
(2) For each n E [T], for all F E H.
1
(F) < Ln(F) - inf C, (I") + R.
2
PER
22

---

:= Proof of Proposition 7. Denote := a), Let Ha be a minimal a-covering of H. Then applying Lemma and the union bound, we have with probability least 1 6, the following holds simultaneously for n E [7]:
(1) For all F' Ha. it holds that
(n((F) & (F(FF) - (n(FF) + 10C² 1002 log(2N/6).
2
(2) It holds that
(FA) - Ln( S (F + 5C log(2/6).
In the following, condition on the above success event.
By definition, (,,t) S ne? app and hence
L. (F*) Ln (FH)) 4ne 5C log(2//).
(15)
Furthermore, for any E H. there exists F' Ho with ||F - F' S a, which implies
[F,(P) Ln (F") S 20na, Therefore, under the success event, we have
(En(F) - - 2Cna.
2 E. (F) - (F) - (F") + 100 10C log(2N/0) + 3Cna.
holds for arbitrary F F. Hence, by (15), we have
{n (F) L. (F+t) 15C log(2N/0) 3Cna 4ne
Noting that L, (F 2 inf FE Lu (F') completes the proof of (2). Furthermore, using En 2 0. we also have
C. (F+) <
inf FeEH
L (F") + log(2/00) + 3Cna + 4ns
This completes the proof of (1).
B.2 Uniform convergence with log-loss
We prove the following result, which is direct extension of the standard MLE guarantee (Zhang, 2002).
Proposition 8. Suppose that {Po(yl=))oEe C (X AQU)) is class of condition densities parametrized by an abstract parameter class O. Without loss of generality. we assume y is discrete.
A a-covering of θ is subset O' θ such that for any 0 θ, there exists 0' O' such that llog Po(u|æ) log Po (ylx)) S a for all x E X. y E y. We define the covering number of θ under log-loss
(0. ax) = min miin((e)) O'| O' is axcovering 0).
Suppose that (x ". ... (x m) is a sequence of random variables adapted to the filtration (3 such that there exists 0+ E O so that IP(yit)) (1 F(1-1) Pa. (y ()) almost surely for E [T]. Then it holds that for all n E [Tr, all 0 e.
E ( Po. (( 80-1] <
Σ Dog Po (o log Pa. (x00))))))
+ log Niog (0,a) + 2na.
Proof Proposition 8. For each 0 E O, we consider
Let e' C be a minimal a-covering, and let N == |0'| = -Ning (0, a).
L (0) == log (2() log Pa- (2.0).
23

---

Then it holds that
E
exp
- (0)
z 20) Fe f
y (-1000))
Po- (y)
Po(yl=:9)
Σ yEY
V Po ((1)) Pa. (ulzio)
D Po Po (-1xx())) Pa- (+1211))-
Therefore, applying Lemma 9 and using union bound over 0 E O', we have the following bound: with probability at least 8, for any E e [T].
L (8)
1
log
exp
L 1 (0') log(
2
In the following, we condition on the above event. Fix any 0 E 9. Then, there exists 0' E O' such that [log Po(y|z) - log (o)(y)z) I a for all E N, E V. and hence (0) - (0') I a almost surely. Therefore, combining the results above and using log w ffo 0, we have
[10( Frem
[D Ps. Po.(-12/0)) D
log
exp
2
log
exp
Fu-
S na
(000') + log(N1/8)
2 t=1
n (0) + log(
2na
By the arbitrariness of 0 O the proof is completed.
Lemma 9 (Foster et al. (2021, Lemma A.4)). For any sequence of real-valued random variables
X ( adapted to filtration (8'9) t== it holds that with probability at least - 5. for all
E [T].
log [exp(-XX Fü 1 I
x + +log (1/8).
1=1
C Missing Proofs in Section 3.1
C.1 Proof of Theorem
We first present more detailed statement of the upper bound of Theorem 1, follows.
Theorem 10. Let E (0, 1), E [0. 1), and we denote Geov = Ceov ( (mr)), where IT = { : I E F} the policy class induced by F. Suppose that Assumption and Assumption hold. Then with probability at least 1 - 8, the output policy ãt of Algorithm satisfies
T
(*())) - (31) -
1
Σ
(V*(s)) ( -V))
T
t=1
[og(((()/00 + +TH pppp)
ACeov log(?) (T)
< O(H)
T
Therefore, for any E (0, 1), with the optimally-tuned parameter X, it holds that V (81) - -
E + OVToo H²2 H22 )pp) long
H2
H2 -log ( ((ee/((Coov((11)
T δ
24

---

Recall that we let Qi E 2 E R be such that
max ke
0
0%
S Supp:
max h
R
Rh
S
Capp
For each E [T]. we write D to be the dataset maintained by Algorithm the end of the tth iteration, i.c.,
D = ((T(Km)) p(anh)) )
We summarize the uniform concentration results for the loss L and LRM, follows. We note that these concentration bounds are fairly standard (see e.g. Jin et al. (2021a)), and for completeness, we present the proof in Appendix C.3.
Proposition 11. Let å E 10, 2 O. Suppose that Assumption I and Assumption 2 holds. Then with probability at least 6, for all t [T). E , E R. holds that
H
E
(2) ON Teat (R(T) - 12 (T))² <
RM D(t) (R)
RRM Die (T-) + H
A-1 h=1
H
ET
(8)
(Ja(sn; an) -
an)))² C (J:R) C (E); + Hs,
kith=1
where
Clog + log(H/8) ( (sapp + p)),
and C 0 an absolute constant.
Performance difference decomposition. Denote (+(1)) == max.e (81, Then it is clear that (s1) - (s1) < Eapp- Therefore, for any t E [2]. by optimism (the definition of (fw) R D,, holds that
(s1) Eapp ($1)
CBE D(- (Q', I8F) + CRM
CD (R+)
- (Qt,R") PP--1 (12*)
=VE(8i)-
X
CB Dit- (f R + CRM Dit-)) (R
BE DD-1) (Q=,, R²) + CRM
Di (R+)
(11 (())
A
Furthermore, by the standard performance difference lemma (Kakade and Langford, 2002), it holds that
11
1 (11, - V*(*) (81) = Σ
(sh, an) - [Th Siu (ss,, an)] [112 ET
(16)
h=1
Based on (16), the existing approaches (with per-step reward feedback) bound the expectation of the Bellman error ef (sh, ax) = f (sh, an) - [T 1] ax) through various arguments (e.g.. eluder argument (Jin et al., 2021a) and coverability argument (Xie et al., 2022)). However, in outcome
reward model, is possible that (* [ (sn, an) [Tr, fn+1](s an)] is large even when the sub- optimality of ( is small, because the outcome reward is invariant under shifting of the ground-truth reward function R
Therefore, we consider the following refined decomposition:
(s1) vol0 (s1)
E
[1 (sh. an) [TR: T
(17)
(e) (1)
Σ R (Sh, an)
Σ R an)
25

---

Coverability argument. Following the coverability argument of Xie et al. (2022), we have the following upper bound on the expected Bellman errors.
Proposition 12. Denote eh2 = - hh Th Jn+1. Then, for each E [H], it holds that
1 (s an)l S 2Coor log (1- CcorI")
27 +
(T(h)
eh (Sh, an)a
Following the ideas of Jia al. (2025), we prove the following upper bound on the reward errors.
Proposition 13. It holds that
HHo log (1+ Coer
H E ( (T) -
HTw +
Σ
IskCEST
h=1
Based on the results above, we finalize the proof of Theorem 1.
Proof of Theorem 1. By optimism and the decomposition (17), it holds that for t E [T],
H
CBE (f R (fo,, Dipe- (QF, R²)
V*(s1) -V00) (81) -app
Σ
Baio
(sh,
an)
hm
CRM D(t-1) (R -CRM Die-1) (1T)
ET
(T) (7))
Then, under the success event of Proposition 11, we have
(*1) vT (81) - Eapp A
2H
H
B=(1) |0/ (sh. as))
Σ (1)
2 (s))
ch
2A
(18)
Aml
+
E [ (T) -T)
E
(R)
RR*
2A
R.C
h=1
Applying Proposition and Cauchy inequality gives for all E (
Σ
T
E
g=(0)
(s),
an) ACcov log (1+
Cevv T
2T +
Σ 1SkeEST
BT(h) ch
ci (sh, az)2
2A
and similarly, applying Proposition 13 and Cauchy inequality gives
T
E
(T) - RT))
< 4ey log
1+ Ganv T
+ 2x
HTK +
E
H
E
(80 ow (R) - (T))
k
IShEtsT
A=1
Therefore, we take summation of (18) over / E [T), and combining the inequalities above gives
Σ ((((s))- --
((((s))~<'(((0) (si) < Teapp
4THK X
+ 5AHCoov log (1 Coov T
This is the desired upper bound.
26

---

C.2 Proof of Proposition 12 and Proposition 13
The following proposition is an generalized version of the results in Xie et al. (2022, Appendix D). For proof, e-g. Chen al. (2024).
Proposition 14 (Xie et al. (2022)). Let 2 be parameter. Suppose that p p) is sequence of distributions over X, and there exists μ E A(X) such that p (z)(x)/((() S C for all
X. t [T]. Then for any sequence wi .... ( of functions X' [0, 1] and constant B 2 1, it holds that
T
CT B
Σ
E Pa (x) -
2o 1
2TB +
Σ RxC
B Expit 1500 (x))
As warm-up. we prove Proposition 12 by directly invoking Proposition 14.
Proof Proposition 12. Fix h E [H]. To apply Proposition 14, we consider A, and define
p p (1)
((sh.an)= =)) A(S x A),
:= = A [0.
By the definition of coverability (Definition 1), for C Ceov (II), there exists μ ASS A) such that (s, ///puss a) < for all (s, a) E S A. Therefore, applying Proposition 14 with B = 2 1 gives the desired upper bound.
Next, we proceed to prove Proposition 13. Our key proof technique summarized in the following proposition, which is inspired by the (rather sophisticated) analysis of Jia et al. (2025).
Proposition 15. Recall that for any D = (D S A R), we denote
D(T) = Da(sh, ah);
VT = (81, (11, 01 ... ,H, E (8 A)
h=1
Fix a Markov policy Weef, we denote Di(s) DH+1(s) 0, and
Da(s) = Beat
Σ De(s,,
sh =s A1 H.
Emm
Then for any policy n, holds that
H
H <
Σ E (Da(sn, + Dn+1(sn+1) - Dn(s)))
E Reof D
h=1
h=1
The proof of Proposition 15 is deferred to the end of this subsection. With Proposition 15, prove Proposition 13 as follows.
Proof of Proposition 13. To apply Proposition 15, for each t E [T', we consider
E To
Σ R (30, ar)
Σ
Rt az) sh =
Vh ...... ,H,
t=h
Then, by Proposition 15, it holds that for any policy x.
R
(Sh, an)
(sh, an) + (0) (8h+1114)) (sn))
(19)
H
4
E B Need (T)
h
27

---

Furthermore,
E R - E"
R2 (sh: an.) - (sh an) + A h+1 - [sW]]
(20)
E R (sh, an. R2 (sh, ap) 1 (8h+1) A (sn)
Therefore, to apply Proposition 14, we consider the space X S x x S, and for each [H]. we define
Ph pm ((sh) ah. 8h+1) = E A 8),
4 (s. a, 5') R (s, R (s, A 1 (8) (s)
Note that for any h, we have w/th x A x S + [0. 1]. Further, let Pa E A(S x A) be the distribution such that |[dg/unll al < Coor for any policy т. Then we can consider the distribution Fy E (SS x A x S) given by (n,
(s' a). Then it holds that
Ph
Ph (s,a,8)) sup 8,0,s' P. (8,00 s.a."'
& (8, (T,
sup
I Cen-
a (n(s
14
Therefore, for [A], applying Proposition 14 on the sequence (p ... :hh and (1th .' gives
2Coov log 1 Ceav Ki
E muppl (2) 2/ (x) _
2T'
Σ
E xxpph 2/ (x)²
To conclude, we combine the inequalities above and bound
(T) - (T)))
b E | (sh, an) 177 (sh, an) A -
H
H T
xmpp (1) 1/ (x)
(0) 1// (2))
=
Souph
1=1 1=1
h=1
1+ CoarT'
2Coov log
2TR +
amppl (0 (x))2
h=
t=1 Ret
1 Coor
2HCoov log
2THR+
E
(k) 1h (z))
A=1 t=1 ket
Cooy
8HCcov log
11
HTR+ Σ
E
(M) no (T) RR
ISECISTIN hml
where the first inequality follows from (20), the second last line follows from Cauchy inequality, and last inequality follows from the definition of (p).) (01)) and (19).
Proof of Proposition 15. For T (s1, as. SH, aH) (S A) we denote Ti
($1, a1.-.. Oh, S1+1) to be the prefix sequence of for each E [H]. Then, we note that
Tre [(()) Σ De(se, az) Foot
Σ 1=
De(se, Th
28

---

Delse, ae) + Dh+1(5h+1),
because the policy on Tref executes the Markov policy Neef starting at the (h (h-t) step. it holds that
step. Therefore,
B n
Σ De(s + DD+1 (he
E EE T ( (ero ( [D(T) mnl)²
S EEnNToRned ((T) Bxo D(T)²
where the first equality follows from the fact that the policy π on Trer executes π for the first h steps. Therefore, for h >> holds that
E (Di (sh, an) + Dn+i(Sa+1) Dn(s)))²
Bra Σ De(se, Datt(SN41)
De(se, Du((n))
De(se, az) + (att((0t1))
E -
Σ
De(se, ae) (sn)
S To The D(T)2 + 1 D(T)²
For 1, because Di(s) O, we already have
E (Di(s1, 01) + (82) (s1)) = E (Di(s1, D2(
Tol D(T)?.
Taking summation over [f] completes the proof.
C.3 Proof of Proposition 11
We prove Proposition 11 in Lemma 16 and Lemma 17 separately. Recall again that under Assumption the function Q* F, R E satisfy
max WE
| Qi
S
Eapp
max hE[H]
RD.
Rt
S
Eapp-
Lemma 16. Under Assumption 1, with probability least 1 - 6, for any t [T), all R E R, holds that
B
on Roet
< C (R) - CB (I2²)
kghh=1
15H log (p) 15(2/8)+ 2T Sapp + 47 HT
Proof of Lemma 16. To apply Proposition 7, we consider the whole history {(T(t.)) p(t.))) )E((T))EE)))
generated by executing Algorithm 1, and recall that DD = {(T(t1n), y(t..))) is the history up to the t-th iteration. Note that (7(t.)), p((c.)), ... (T(1..1, p(t)0) are pairwise independent given Dit-1), with
(1.0) ~ n on Traf
(aM) D) -umn] = Rd (1.N))
Also note that r E 10, almost surely, and we regard S ((S A)" + [0. 1)), and R R satisfies (T) Rd
(T) < Heapp for all J E (S x A)
Therefore, applying Proposition
on the function class R and the sequence ((7(1)) p(l.)) hejo.) gives that with probability at least 1 - 6, for all R E R, 1 E (T). it holds that
E (1) Min (R(T) RT)+))²
R (F(k:10)) D (R(
k=1h=1
29

---

CRM (R)
CRM D(t) (R²) + 15 Hp) + 2T sapp + 4TH2Pp
Finally, note that log (R, H)) upper bound.
H Io= (Rn. - Hog N ((). This gives the desired
Similarly, we prove Proposition 11 (2) as follows, following Jin et al. (2021a).
Lemma 17. Fix h E [H] and å (0, 1), p 2 O. Suppose that Assumption I and Assumption holds.
Then with probability at least 1 - the following holds:
(1) For each E [T].
& (Qh Q1t1:R)
inf EDIO Oh+1i R2) & O(THeapp + THp (og(N())/))) ghEgn
(2) For each E for all Jn E Fr, Jn+1 E Fu4I and Ra E Rr.
E (fi(sh, an) (TR,fh++1l(s, an))
S Doo (fhi fh+t1; RA))
inf E (9h. fa+1: 1: RA) + + (o)()())
9h Sh.
where we use O() to hide absolute constant for simplicity.
Proof of Lemma 17. Fix h E [H] and denote N == Np). We let Fa++ be minimal p-covering of Fa+1, and let R2 be a minimal p-covering of Rr, By definition, |F S N, I N.
In the following, we adopt the notation of the proof of Lemma 16. Recall that conditional on D(t-),
(1.4) (1.0) ~ x. og Trefs (t.6) (sf (4.0 (6.4) .... , .a
and ((ta)) .... 20..0 are independent conditional on Dit-t), For simplicity, we denote ((t.0) (5h aa ahil).
Fix f141 E Fhet U and Ra E R2 U (R we consider
= fnta(((4))) + Rx(s (..)).
and it holds that
E D 1n0
Then, for any on Gh. it holds that
ED (gh, Ja+1; Rτ.) = ΣΣ
(gn(x 3
k=1 t=1
and we also have
H
H1
E Togtet (sh, an.) [TR, ( an))²
E
(9n (2) - [T fn fnttt( D
k=
Then, applying Proposition 7 with the function class H Gn yields that with probability at least
1 2N, the following holds:
(a) For each
[T], for any gh Gi.
(M) (gh(sn, on) [Tnnf-ul((s,aa)))
<EpCo n (gh, Rm)
inf Exco, fat1: RA) ((lgg(N/6) + THE + THp).
s Eb,
(b) When fat1 Q and R = R the function Q Fr. S Gr satisfies the inequality 110 The 5 app and thus
( 0 127,) < inf (gn, of (2, + Oloog((/))))))) + THe + THH)) grESn
30

---

Therefore, taking the union bound, we know that the inequalities (a) and (b) above hold simultaneously with probability at least 1 - ò for all fh+11 E F h+1 U U(Qh+13 and R₁ E R2 U { In particular, we have completed the proof of (1).
To prove (2), we only need to note that Gr S Fh. and for any fh+1 E F1+1, RA E Rr, there exists fh+11 E F Ry R2 such that [lf - fh+ille S p. [R, Rl I p. Therefore, by the standard covering argument and the fact that m²*) oи Fref mTh),, we have also shown (2).
D Proof of Theorem 2
In this section, we provide the proof of Theorem 2, which is a direct adaption of the proof of Theorem Appendix C. We first present more detailed statement of the upper bound (with any parameter À > 0).
Theorem 18. Suppose that Assumption / holds. Then with probability at least 1 5, Algorithm 2 achieves
prll S Eapp + O(1) 1 log(No, + T== app
XHC (LI)
T ('(o)9)-->')
X
We also work with a slightly relaxed version of Assumption 3.
Assumption 4. Under any policy for each h E [H), it holds that almost surely (5,, an) (sh an) + Vi
Further, to simply the notation, for each f E F, we recall that the induced reward model R! is defined as R2 (8, == (i) Re (8, a) = (, [n),), which implies
"1
R¹
Σ h=1
Ja(sn, an) (8n=11)))).
Uniform convergence. For each & E [Z]. we define Dit-1) == ((T(t),,((t)))))))))))))))) p(tt)) the data collected before 'th iteration. We also recall that by definition (8), we have
CBR
Σ [fnoh (al fh+ ( (s pilt)
R (T (1(tt)-)((s)
Therefore, a direct instantiation of Proposition on the class R = {K fEEF yields the following proposition.
Proposition 19. Let å (0,1), 0. Suppose that Assumption I and Assumption 4 holds. Then with probability at least 1 1 for all t [T]. E F, it holds that
E
(R')))
< CBR (ʃ) L (Qt) + K.
2
where
K k= C log(NN (a) TH T T)
C> 0 is absolute constant, and denote N=(a): == maxne(H] N(Fr, a)) for any 2 0. Performance difference decomposition. In this setting,
rewrite the decomposition (16) as
H
1 (81) - (z(*) (81) = Σ
E
(5)
[ (8h, an) - (sn, an) - - (8)+1)]
h=1
E =0)
H
[1t) (s)) ((041)) - Σ
(t,, an)
(21)
hml
hm1
E"
(R - R (T)].
where we denote R = ((())
which is a reward model given by
R (s, a) (s)
(s, fi (s. (
31

---

Optimism.
Similar to Appendix C.I, we use the fact that from (9),
f = max Af((s(")
-D) (f),
CBR
fEF
and hence
1 (3 -
- 1 (f)) AV
pit- (f(t),
Using
- ())(s I Eapp. (21) and Proposition 19, we now deduce that
CBR Dut
1) 1,(
(QF)
(*(+)) (((()))V~+(((0 (s()) I app E R R*)[]]]
Die
t-1
+ K + BTl (T) - (T)
E
S Capp
x
2A
k=1
(22)
Therefore, it remains to prove an analogue to Proposition 13.
Coverability argument. We strength Proposition 13 using the deterministic nature of the underlying MDP. For each E S and E [H], we define
Sy II) == {(5', a) 3r E II, under и and it holds that s', an = a).
and (s; IT) (s;
Proposition 20. Let B 1. For any initial state 81 E S, any sequence of reward functions R ,.. R and any sequence of policies T .... , it holds that
E (-(")
(T)
(r))
4TH 1+
< (8) log
2TB +
Σ 1SkCIST
ET(M)
(R)) - (T)) $1
B
where N(8)) = EH (s1 II), and the conditional distribution E. [-] 81] taken over the expectation generated by executing policy æ starting with the initial state 81.
The proof of Proposition 20 is deferred to the end of this section.
Finalizing the proof. With the above preparation, we now finalize the proof of Theorem Taking summation of (22) over t = 1,2, T. we have
(s(")) (T(0) (3
< Teapp + TK
T
R (T) RT((T)
E (K)
(R - RT)))))
X
2X
ISkCIST
TTaapp + TK
Egioo
Σ 8T [R RR))) - Σ
1
(T(
(R R (R)
X
2X
IsketST
2Tw X
Esip N(ss)Alog (1 1 TH
<Teapp
where the last inequality follows from Proposition 20 and Cauchy inequality. This is the desired upper bound.
32

---

Proof of Proposition 20. In the following proof, we assume E S is fixed. Consider
I = {(,, [M], (8, a) (a(s S [H] 8 x A.
Note that [Z]
Σ |= (s; = ((1).. By definition, for any policy 9, there unique (11, such that under and starting from 81, we have sn. 8% ag aj
pair (5% ( deterministically.
For each & [T], we consider the following vectors indexed by Z:
git = [Rg (s, a.) -1 (8, a) (h,e,0) E R
H
6 = [ (sh an = als1) (MiS,a)EI
sop (0 E R.
(h "0
h=1
With this definition, holds that for any k, E (T'.
E (K) [R - Σ (sT o ( R* .ap [o7"))
(dra), 2b(1)).
Therefore, we apply the elliptical potential argument (Lattimore and Szepesvári, 2020). Let V == Exer ( BI. Then it holds that
Σ
1000, b S
min (il 13 max max{]l llv, 1}
T
T max{ 13.
min 1 1,13
Note that
max 1100001
2
1 <
+ B 11 + Σ (0ln)) 15l09²
1/
k=1
T(1 + 4BZ)
Σ B=(h)) (RR
R (T))) $1
ISKEIT
and by Lattimore and Szepesvári (2020), we have
T
min Σ
11 2|Z|log
TH 1+
[
Combining the inequalities above and rescale B <
B 4
completes the proof.
E Proofs from Section 4
We present the full description of our algorithm or preference-based RL as follows.
E.1 Proof of Theorem 3
For each E (T). we write Dio to be the dataset maintained by Algorithm the end of the ith iteration, i.e.,
D ((r(tittt) pitini-), yg kSt.
Note that for each t [T], h [H]. have (((Ai-)) Tref- Therefore, for each R R, define Viell = Tot (R(T) and recall that
Dref D.R
Σ
R(T
D
(rt. WEED
The following lemma follows from the standard uniform convergence rate with Hoeffding's 's inequality and the union bound.
33

---

Algorithm 3 Outcome-Based Exploration for Preference-based RL
input: Function class F, parameter À > 0, reference policy Tref- initialize: + 0. I: fort= = 1, .,, T' do
2: Compute the optimistic estimates through (12):
(f R,,
max SEF,
[f((s1)
Dise D.R
-CD CD (f: CPDRM (H),
3:
Select policy T y(1)
4: for = 1... do
5: Execute (0) on Fref for two episode and obtain trajectories (rllihet), gelcee 1) and
preference feedback y(uhh)
6:
7: Update dataset: D DU ((T(tattt, x(lnn1)) ( ((t))))
8: end for
9:
end for
Output Un)
Lemma 21. Let (0,1), O. Suppose that Assumption I and Assumption 2 holds. Then with probability at least - for all t E [T], RE E R, holds that
log ( + Hp.
Vref D R
Vrref
t
We summarize the uniform concentration results for the loss LB and LPDRM follows. The proof analogous to Proposition 11 and is provided in Appendix F.2.
Proposition 22. Let å e (0, 1).1).p 2 Suppose that Assumption I and Assumption 2 holds. Then with probability at least 1 - 5, for all t e [T. f E F,R E R, it holds that
roe D
R
V
tH
ET (init) (A,A.)
([H(Tt)-R() [R*(T)) H (T))))
Co [CCMMM (R) CPPRM +CaHi,
Eett h=1
ΣΣ (M (1) ksth=1
(fr(sh, an) - az)) < 2 (f: CBF, (QA:R5) HR.
where Cg = g2
28
K == Clog (()) (o + +)((Eap + +)).
and an absolute constant.
In the following, condition the success event of Proposition 22. Note that ((t.h.-) Trefs and hence Proposition 22 implies that for all R R, E [T].
H
OA Tead R [vrel
-vnet)) < C9 [C[CPRRM (R) - CPRRM (PA) + CgHH.. (PRM
k h=
Therefore, for any reward function R, we define R as Rí (s, a)
Viel and R (2(ssa) a) R (s, a) for h > Then it is clear that R(T) = R(T) - Vget and for all R E R, t E [T]. we have
H
1 (M) Fret [R(T) Re (T)) C' D(o (R) CPBRM (1+)) + Callk. (23)
1.S 1=1
34

---

Performance difference decomposition.
In this setting, we re-write (17) as follows:
Vall (81)
(81)
E (0
[ (shr and
[TRRC: S S (shh an)
H
11
+ B
Σ
R (sh and
Σ
R (3h. an)
H1
E B=(())
( ch (sh, an) + (T(()))
(T) (T)
V/te
R(
1=1
where we recall that we denote
(1) c/
= S/ Tnt Therefore, we re-organize the equality as
H
(11) - V/rof Rio
(81) Vgd
(T) - [T) = E=
+
Σ TT(
(Sh, an)-
(24)
With the above preparation, we present the proof of Theorem 3, which closely follows the proof of Theorem in Appendix C.I.
Proof of Theorem 3.
By definition, for each E [T].
(f R()) = max A {fi((s) - Droe 1) 1)
CBE Dit- (f: R) - [PRRM (R).
RER
Therefore, using Q? F,R R, we have
(( - Prof (D(--1),n(11) - [i(()) Dree
Di
LBE Du- (1 (f(1) R!)) - -LD (QF;
CPRM Dic
(R.0)
LPGRM (RF) DiC
À
Using the decomposition (24), Proposition 22, and the fact that (i((1) vi((s1) I Eapp. (K((T) 12" (T) 5 HēEpp, we have
2HR
Vi*(s)) -* (s1) s (H 1)sapp + Vref -Vref
12,12(1)
+
Vielf
Viel 11
A
11
ET (2)
(sn, an)]
(T(()))
eh (sh, ax)²
(sh)
1=1
let
+ 1x (1) [P'0 -
[T)
b=th=1
(25)
Taking summation over ( 1,2,.... and apply Proposition 12, Proposition 13, and Lemma 21 yields
E V - (61) S 0(1) H(Eapp + + VTR+ THE
+ CCgAHCenn log 1 Coov I K
X
This is the desired upper bound.
E.2 Proof of Proposition 22
The inequality involving CBE, is implied by Proposition 11 and proven in Appendix C.3. In the following, we only need to prove the inequality involving CPRR) by invoking Proposition
Consider the class θ R U (R*) X (S x A) (S H. and y {0. 1). For any E O, exp (3P((7
we define
exp (x3((((++
Pm([]=t,77)
Pr(OT+,7=)
exp (3R((++))) + exp (BR(T-))
exp(3 + exp (3R(T-))
35

---

following Definition 3.
Recall that D { ,( y( } heet is the history up the t-th iteration. For
simplicity, we denote 2((h1) = (Tiliitt, , p(1h-))). Note that (alti)) y( (x yb.)). Then it is clear that for all t E [ E [H],,
Pyy (z(1))) DE 1) Pr- (1) (2tth)))))))))
and it also holds that
Vy {0,1). Further, noting that Mog (0, Bp) I N(R, + Therefore, applying Proposition 8 gives the following result: with probability at least 1 5. for any RET R,tE [7].
)))) = log Pn( L(R(T=) ((((T))-R(T>)>)))
"
(P , PR. (+17 (3. +) (0.0
k=11=1
Σ
[L(R(T+) R(T ((R R (T))))
(r iT :t))
+ log (RR, H)) + 1) (2/8) T
1
D(O (Rt - (1E*) + HK,
2
where the second inequality uses the fact that [R( - (0r)-R((11) (T) I Heapp- Finally, note that Di (Bern(p), Bern( 2 {p - q)² and
B
w'l, Vw, E [--1,]]
2e
Therefore, using the definition of PR completes the proof.
F Proofs of Lower Bounds
F1 Hard Case of Learning with Fitted Reward Models
As mentioned in Section 3.1, in Algorithm 1 the learner has to optimize over the reward class and value function class jointly. In the following,
argue that if the learner first learns fitted reward model in the reward class, then optimizes the value function with the fitted rewards, the output policies each iteration never converge to the optimal policy.
In detail, we consider algorithms in the form of Algorithm 4, where the learner fits the reward model 8 at iteration / first, then the learner calls algorithm alg. which takes per-step rewards data as input and outputs a policy म, at each iteration. align with the structure of Algorithm 1, we take alg to be single iteration of the GOLF algorithm in Jin et al. (2021a), i.c. T yT()) where f(o) jrgmax f (x1 T (x1)) Here the confidence set F is defined as
F
J : (J; $
CBE
with CB defined in Eq. (5).
Then we have the following proposition, which shows that this approach outputs suboptimal policies at every iteration in some special hard cases.
Proposition 23, Consider Algorithm with alg single iteration of the GOLF algorithm. After running iterations, the learner averages over all policies to output a policy. There exists an MDP class that realizes the ground truth MDP, such that the above algorithu outpus policy which is at least su01-subap..mal.
Proof of Proposition 23. We consider the following class of two-layer MDP, where S {s1}. Sy = {s2]. and the action space to be A = {a1, az). The transition models T are identical across the class, and have the following form:
T(s2 $1, a.) 1, Vi {1,2}.
36

---

Algorithm 4 RL with fitted reward models
input: Algorithm alg, reward regression oracle O.
1: Initialize ( 0 for every h E [M]
2: for (= 1, 2, ...... 7 do
3: Feed D to alg and receive (7()) from alg
4: Execute rT and receive (r(*), (r(),)()) where 7( = (sf". "a"".......
( (9)
5: Receive the fitted reward function from O:
R
min Σ (R(711)) - - RER k=
6:
Let P/. = RR (5% 0 (0)) for each E [H].
7: Let Di:: = D) 1) {(s) ai 810 1
30
H 4 (1))
8: end for
The reward class is defined as R {R', R²), where
= R (s1, a2) = 0.20, R (1)),1) = 0.20, R 02) = 0.19,
and (s1, = ($1, a2) 0.00,
18 (1) = 0.38, R² 02) = 0.39.
The Q-function class Q is defined as Q 10',00"0 Q², Q2 (*, which takes value in Table 1 respec- tively. Notice that in all possible reward models and Q-functions, the values at (81, 01) and at (81, 02)
Table I: Value of Q' Qa, Q3, Q4
(81,
(81,02)
(82, 01)
(82, (2)
Q
0.40
0.40
0.20
0.19
Q2
0.20
0.20
0.20
0.19
Q
0.59
0.59
0.38
0.39
0.39
0.39
0.38
0.39
the same. In the following, when without ambiguity simply R(s1) denote R(s1, a1) and R(s1, a2), and use ((s1) to denote Q(s1, a1) and Q(s2, 02).
We further suppose the ground truth model reward satisfies R = RR, then we can verify that the optimal Q-function is Q. easy to verify that sets Q and R satisfy the completeness assumption. Hence, sets Q and R satisfy the realizability assumption Assumption and the completeness assumption Assumption 2 with =.
To see why this is hard-case for GOLF type algorithms, we first notice that for any trajectory (81, āi, 82, ū2) with outcome reward R2 (s), + R² (82, ā2) collected by the algorithm, we always have
(s1 (²2,,, āz)-
Hence as long as 'D does not contain state-action pair (82, 01), when fitting the reward function using the following ERM oracle:
Σ (r(7) -))
argmin
RER
(T.))E
the reward model R² always achieves the minimum. In the worst case, we assume the fitted reward models encountered by the learner at such rounds are always R².
In the following, we verify that by running the GOLF algorithm, the learner will not encounter the state-action pair (82,a) a1) at any round. We notice that the optimal policies of Q3 and Q* all take d2 at state 82, and also that
(² 2 (s1) and Q² 2 (s1).
Hence, verify that the algorithm never chooses on at state 82, we only need to verify that either Q² or Q² belongs to the confidence set, then Q3 also belongs the confidence set.
37

---

When the leamer collects new trajectory, two new pieces of data will be added to the dataset D. If the trajectory does not pass through the state-action pair (1).01) these two pieces of data will be in the following form:
(51, 01, R² (s1)), (82, 02, 18 a2)) or (51, 02, R (s1)), (52, 02, R2 (#2, a2)).
No matter which one of these two, have the following inequality for the sum of squared Bellman error across these two pieces of data
+(Q)))+&((0)) + 0.01 0.28 0.20² =E(("")+
0.20 + 0.20 0.20 =
According to the construction the confidence set, if either Q' or Q² belongs to the confidence set, then Q* belongs to the confidence set as well.
Therefore, no matter how many rounds the algorithm runs, the optimistic policy always takes action 42 at state 82. Hence the average policy से also takes 02 at 82, which implies that
J(x²) ( 2 0.01.
F22 Proof Theorem
d/2 Then, by the standard packing argument over sphere Fix a parameter& E (0, and N 1 2:
(see e.g., Li et al., 2022), there exists set θ = {0,,,.. 10,,"",,NN' S gd-1 such that
,0N]
|10 0 2 22,
Vi j j.
This implies (0,,0) < - for any + j.
Construction. In the following, we set
E, and construct state space S as
S = S US,
S = {s1}.
S₂ O
and let action space A = θ The initial state is always $1, and we define the transition T as i.e., taking action
T(s2
$1, a 0) 1, E
0 at transits to 0 deterministically.
Reward functions. For any v E O, we define the reward model R" as follows:
(8, a) = ReL.U((a, v) b) + (a, + 1] [0,
Va E O
(8 a) 31l - (8, u) E [0, 1].
Vs E O.
Note that can write 91 (x) [ReLU(z b) + 11,92(z) 3 and then 92 is linear function, and
3 r s ge(i) (
31 x 21
VI
Hence, I1 and O2 are (well-conditioned) generalized linear functions, and hence R2 and Ry are both (well-conditioned) d-dimensional generalized linear functions.
We let MM" be the MDP with transition T and mean reward function R" and M (M" Q) be the corresponding class of MDPs. We next show that M can be learned with polynomial process- based samples, but cannot be learned with polynomial outcome-based samples.
Exponential Lower Bound for Outcome-Based Setting. When executing a policy in MDP M we have a₃ = Ti (81), $2 = a1, and d2 = 72 (82), and the data (To.or, R) observed are in the following form of trajectory together outcome-basee based rewards:
2 ReLU v) - -b) 3
(81, 01, 82, az):
R|T ~ Bern
38

---

where Tn is deterministic function of и. In the following, we denote an TI (s1), and then E[ π Re u) b) + Further, under M
2 J(x) + 1a
and in particular, J(m))= = Therefore, for any policy π,, it is (s/3)-optimal under M only when d, = v. Hence, we can apply the standard lower bound argument for multi-arm bandits (see e.g., Lattimore and Szepesvári, 2020) to show that: If there any T-runnd algorithm that returns an (e/3)-optimal policy with probability least 1 for any MDP M E M, then it must hold that 2 N. (where c 0 is an absolute constant). Setting Cgz bound.
completes the proof of the lower
Polynomial Upper Bound with Process-Based Samples. M M, we have
Notice that for fixed E θ under
J(TT) - J(T) = 51 - f( = =b}l = 3 (1, u) - ((.m u)]-
Thus, for any 8 E O, we define TO as лक (s) (s) 0 for Vs S. Then it holds that under M",
E
R2
v).
Therefore, given access to process reward feedback, linear bandits. Hence, for any a > with process reward feedback, there are algorithms that returns an a-optimal policy with high probability, using T S O(P//a) episodes with process rewards (see e.g., Dani et al., 2008).
reduce learning M to learning class of
39


Reviews:
[{"review_id": "JnOWv9VAku", "reviewer": "Reviewer_R6NT", "summary": "The paper proposes an algorithm with sample complexity bound for outcome-based online RL. The algorithm can handle general function classes for approximation. The algorithmic framework is further simplified for deterministic MDPs and extended to preference-based RL to demonstrate the generic nature of the approach. Finally, lower bounds are derived for both the per-step reward-based and outcome-based RL settings. This shows exponential deviation among hardness of these two frameworks in some well-crafted MDPs.", "questions": "1. Can you provide some examples of $N(\\alpha)$ and $N_T$ for some function classes? Present description in line 175 is vague to me.\n2. The lower bounds are interesting for future research but no detail or intuition on the \"hard\" MDP construction is provided. Can you summarise why the specific two-layer MDP constructed exposes this gap? What is the bottleneck?\n3. How does the covering number scales with dimensions and structures of policy class? It can go exponential in problem parameters, no? Where can we get a better polynomial type bounds on MDP parameters using this complexity measure? Also do we have to take the min over all base measures $\\mu$? If yes, explain the intuition?\n4. The formal proof for Theorem 3 of preference based optimization passes through proposition 22 and thus, proposition 8, which tries to control the Hellinger distance between the Bernoulli distributions over trajectories induced by different reward models. Why it has to be the Hellinger distance between them? Why not TV or any other metric? Can you explain this choice?\n5. Please address the issues in weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The problem setup is interesting and timely.\n2. The algorithm extends the well-studied fitted Q-iteration to this setting, which is nice approach to bridge the per-step reward and outcome-based RL setups.\n3. The analysis of preference-based RL provides a motivating instantiation of the outcome-based RL in the context of modern RLHF applications.\n4. The lower bounds demonstrating the different between per-step and outcome-based RL are insightful for future research.\n\nWeakness:\n1. Limitations of the analysis or the framework are not discussed.\n2. Regret is never introduced in the paper. Also the notation $R$ is confusing with reward (e.g. Eq. 11, 13 etc.).\n3. The description of the comparator class is almost non-existent. I understand that the idea comes from another work but explaining how to choose it exactly, specially in preference-based setting, is necessary for clarity.\n4. The proposed lower bound on T to satisfy the error bounds in Eq 7, 10 and 14 seems intangible to me as both sides depend on T, and I do not see how the left side scales with T for some useful function classes. Can you explain this?", "was_revised": true, "final_justification": "The paper addresses an interesting problem of outcome-based online RL. The discussions addresses most of my questions. I would really recommending adding the discussions to the paper. Also, discussing limitations like intractability of the algorithm should be discussed in detail to pave way for future works. Thus, I recommend a borderline accept .", "rebuttal": "We thank the reviewer for the review. Below, we address the concerns raised in the review:\n\n> Limitations of the analysis or the framework are not discussed.\n\nThank you for pointing out the omission regarding the limitations of our analysis/framework. We will update them accordingly in the future version of our paper.\n\n---\n\n> Regret is never introduced in the paper. Also the notation $R$ is confusing with reward (e.g. Eq. 11, 13 etc.).\n\nThanks for mentioning this issue. We will add the following definition in our revision:\n“The regret across $T$ steps is defined as $\\sum_{t=1}^T (V^\\star - V^{\\pi_t})$, where $V^\\star$ is the optimal value function and $V^{\\pi_t}$ is the value function of the policy chosen at time $t$.”\nWe will also clarify the notation $R$. \n\n---\n\n> The description of the comparator class is almost non-existent. I understand that the idea comes from another work but explaining how to choose it exactly, specially in preference-based setting, is necessary for clarity.\n\nThe comparator class $\\mathcal{G}$ for the Bellman completeness is indeed commonly considered in the literature of model-free RL. Typically, it can be chosen to be the value function class $\\mathcal{F}$, as long as the class $\\mathcal{F}$ is rich enough (so that it is close under the Bellman operator). When the class $\\mathcal{F}$ consists of neural networks, we may expect the Bellman completeness holds with small error, as guaranteed by the approximation theory of neural networks.\n\n---\n\n> Can you provide some examples of $N(\\alpha)$ and $N_T$ for some function classes? Present description in line 175 is vague to me.\n\nFor example, when $F$ is a parametric class of dimension $d$, e.g. $d$-dimensional linear function, we have $\\log N(F, \\alpha)\\asymp d\\log(1/\\alpha)$. When $F$ is some non-parametric class, e.g. Lipschitz functions in dimension $d$, we have $\\log N(F, \\alpha)\\asymp \\alpha^{-d}$.\n\n---\n\n> The proposed lower bound on T to satisfy the error bounds in Eq 7, 10 and 14 seems intangible to me as both sides depend on T, and I do not see how the left side scales with T for some useful function classes. Can you explain this?\n\nAs discussed, for parametric function class, we have $N_T\\asymp d\\cdot \\log T$, where $d$ is (roughly) the number of parameters. For such classes, all of these conditions in Eq 7, 10 and 14 with both sides depending on $T$ hold when $T\\ge M * \\log T^2$ for some parameter $M$ possibly depending on $\\epsilon, \\delta, H$ and $C_{\\rm cov}$. Therefore, this condition is automatically satisfied when $T \\ge M \\cdot \\log^2 M$. This condition can be used as a surrogate condition in Eq 7, 10 and 14. We will clarify this in the revision.\n\n---\n\n> The lower bounds are interesting for future research but no detail or intuition on the \"hard\" MDP construction is provided. Can you summarise why the specific two-layer MDP constructed exposes this gap? What is the bottleneck?\n\nThe main intuition of Theorem 4 (the lower bound) is that, without bounded coverability, the outcome reward may not be well-behaved even when the per-step (process) rewards are generalized linear functions. Technical, the lower bound follows from the following two facts:\n\n- ReLU bandit setting is exponentially hard to learn\n\n- In linear bandit setting, there are algorithms with $O(d\\sqrt{T})$ regret\n\nSo in our two-layered MDP construction, we let the full problem to be a ReLU bandit, meanwhile we encode a linear reward structure in the first layer. Hence with the per-step reward model, the learner has access to the linear structure in the first layer, hence can achieve sublinear regret, while with the outcome reward model, the learner must deal with the ReLU bandit, which is exponentially hard.\n\n---\n\n> How does the covering number scales with dimensions and structures of policy class? It can go exponential in problem parameters, no? Where can we get a better polynomial type bounds on MDP parameters using this complexity measure? Also do we have to take the min over all base measures $\\mu$? If yes, explain the intuition?\n\n$C_{\\mathrm{cov}}(\\Pi)$ is the denotes the coverability of the policy class, i.e. the coverage of policies in $\\Pi$ among all possible offline distributions $\\mu$, hence in the formulation we have to take min over all base measures. This notion is very natural for measuring the complexity of $\\Pi$, as it notes the minimal efforts for learning under the covariant shift of all policies in $\\Pi$. When the state space and action space are discrete, this notion has another formulation that might be more intuitive:\n\n$C_{\\mathrm{cov}}(\\Pi) = \\max_{h} \\sum_{s_h\\in S_h, a_h\\in A}\\sup_{\\pi\\in \\Pi} d^\\pi(s_h, a_h).$\n\nHere we briefly some common MDPs with bounded coverability guarantee:\n\n- Tabular MDPs: $C_{\\mathrm{cov}}(\\Pi) \\leq |S||A|$\n\n- Block MDPs: $C_{\\mathrm{cov}}(\\Pi) \\leq |S||A|$, where $S$ is the latent state space\n\n- Linear/low-rank MDPs: $C_{\\mathrm{cov}}(\\Pi) \\leq d|A|$, where $d$ is the feature dimension\n\n- Sparse low-rank MDPs: $C_{\\mathrm{cov}}(\\Pi) \\leq k|A|$, where $k$ is the sparsity level.\n\nAs shown by the above examples, the coverability coefficient scales polynomially with relevant problem parameters, instead of exponentially.\n\n---\n\n> The formal proof for Theorem 3 of preference based optimization passes through proposition 22 and thus, proposition 8, which tries to control the Hellinger distance between the Bernoulli distributions over trajectories induced by different reward models. Why it has to be the Hellinger distance between them? Why not TV or any other metric? Can you explain this choice?\n\nThe main purpose of Proposition 8 is to provide non-asymptotic guarantees for maximum likelihood estimates (MLE). We choose the Hellinger distance primarily to facilitate the analysis, as it offers technical convenience in theoretical derivations. As the TV distance can be upper bounded by the Hellinger distance, Proposition 8 still holds if the Hellinger distance is replaced by TV distance. Our choice of formulation aims to maintain generality, extending the applicability of the results beyond the immediate scope of this paper."}, {"review_id": "7kc2u0BT9a", "reviewer": "Reviewer_T9uz", "summary": "The authors tackle reinforcement learning with outcome-based feedback in the case of general function approximation. Under the assumptions of coverability and completeness, they show that an optimistic algorithm that models the unknown reward function and balances the estimated value of the Q-function, the TD error, and the reward model error can achieve a sample complexity of $T \\geq O(C_{\\text{cov}} N(1/T) H^2/\\epsilon^2)$ episodes. A simplified algorithm is presented in the case of deterministic MDPs that only requires realizability instead of completeness. They extend the first algorithm to preference-based RL, and conclude by providing a hard instance, showing that learning from outcome-based feedback can be exponentially harder than process reward feedback when coverability is not satisfied but the low Bellman eluder dimension assumption is.", "questions": "1. If the assumption that the outcome-based feedback is given by the sum of rewards is relaxed, how do you think the results would change?\n2. How does your paper compare to Kausik et al. (2024)?\n\nI was going to award this paper a score of 5 (Accept), before noticing the concerns outlined above that affect the significance and originality of the paper. I will be very happy to increase my score if my concerns are addressed.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n1. **Strong theoretical contribution in a highly salient setting**.\n- The paper addresses a highly salient setting with a thorough mathematical analysis, providing trajectory-only feedback theory with matching lower bounds for general function approximation. The proofs appear to be sound.\n- The contributions are varied and thorough, consisting of a statistically efficient model-free algorithm, a simplified algorithm for deterministic MDPs, extension to preference-based feedback, and a lower bound that completes the picture -- while coverability is sufficient for RL with outcome-based feedback consisting of the sum of rewards, the low Bellman eluder dimension assumption is not. \n2. **Original algorithms**.\n- The authors provide two original algorithms for RL theory with general function approximation, that very refreshingly are not derivatives of GOLF. The authors also show that joint optimization of the reward model and Bellman loss is necessary as well.\n- In particular, it is very nice that the authors adopt the MEX approach, instead of maintaining per-step confidence sets as in GOLF, to achieve sufficient optimism in Algorithm 1. \n3. **Clear writing and presentation**.\n- The paper is well-written and very easy to understand. \n\n## Weaknesses\n1. **Claim of first comprehensive analysis of outcome-based feedback in online RL with general function approximation**.\n- Relevant work exists that the authors do not cite or compare their results to. Kausik et al. (2024) view cardinal (good/bad) and dueling (preferential) feedback in RLHF as partially-observed reward states, and provide guarantees for model-based (in the tabular setting) and model-free (a GOLF derivative in the general function approximation setting) RL. The latter uses a history-aware analogue of the Bellman-eluder dimension. In my opinion, the setting is highly similar, even though the approach may be different, and it may not be appropriate to say that this is the first comprehensive analysis of the problem in online RL with general function approximation.\n2. **Outcome model structure**. \n- Further, the claim that this gives a comprehensive analysis of RL with outcome-based feedback may not be appropriate as well. In my view, the contribution is not as broad as the paper claims for the below reason. \n- The authors assume that the outcome-based feedback observed is given by the sum of the rewards in the trajectory. This is not necessarily the case in practice (for instance, one can easily imagine a threshold outcome that yields 1 if the sum of rewards is high enough and 0 otherwise), and is an assumption that other prior work (see Kausik et al. (2024) for an example) does not make.\n- In my view, it is quite possible that this assumption is the reason why this paper achieves stronger results than Kausik et al. (2024) in the case where no intermediate feedback is observed in their setting. To be more specific, the fact that the outcome-based feedback is assumed to be the sum of the rewards in this paper may be the very reason why the credit assignment problem is solvable in this setting (under coverability) but not that of Kausik et al. (2024). \n- However, this is not stated as an assumption, but is presented as part of the setting itself. I do not think this is good practice. I am of the opinion that this should be highlighted and presented as an assumption, due to the above remarks. \n- This ultimately limits the scope of the paper, and one can conclude that this paper therefore may only tackle a special case of outcome-based feedback where the outcome is the sum of the rewards. \n\n## References\n1. Cheng et al. (2022), Adversarially Trained Actor Critic for Offline Reinforcement Learning\n2. Kausik et al. (2024), A Theoretical Framework for Partially Observed Reward-States in RLHF", "was_revised": true, "final_justification": "The author's rebuttal has satisfactorily addressed my concern previously highlighted at the end of the questions section. As promised, I have increased my score.", "rebuttal": "We thank the reviewer for bringing the work of Kausik et al. (2024) to our attention. To facilitate a clear comparison, we outline the key distinctions between the two settings:\n\n- Our setting (A): The outcome feedback is (a noisy observation of) the sum $R_1(s_1,a_1)+\\cdots+R_H(s_H,a_H)$\n\n- Setting of Kausik et al. (2024) (B): The outcome feedback is a (possibly sparse) vector $(R_h(s_h,u_h,a_h))_{h\\in \\mathcal{H}}$, where $u_h$ is the *unobserved* reward state that can depend on the history up to step $h$ in an arbitrary way.\n\nWe would like to note that setting (A) represents the most commonly studied outcome-reward model in recent theoretical works (Efroni et al., 2021; Pacchiano et al., 2021; Chatterji et al., 2021; Wu and Sun, 2023; Wang et al., 2023; Cassel et al., 2024; Lancewicki and Mansour, 2025). When we refer to providing a \"comprehensive theoretical analysis of outcome-based online RL,\" we are specifically addressing this well-established setting (A).\n\nWe acknowledge that setting (B) presents greater learning challenges, as the reward structure may depend on the entire history. However, we would like to discuss some limitations when directly applying the results of Kausik et al. (2024) to our outcome feedback setting (A):\n\n- Trajectory space complexity: The upper bounds in Kausik et al. (2024) scale with variants of the eluder dimension over the trajectory space, which must be $\\Omega(|\\mathcal{A}|^H)$ in worst-case scenarios (e.g., combination locks). The conditions under which trajectory eluder dimension can be bounded by other relevant problem parameters remain largely unexplored. Notably, it cannot be bounded by the per-step eluder dimension, as demonstrated by our lower bound. While such dependence on trajectory eluder dimension may be unavoidable under the fully general setting (B) due to combination locks falling into this category, we believe there is value in exploring more refined analyses for specific subclasses.\n\n- One of our objectives is to avoid dependence on eluder dimension over trajectory space—an approach that aligns with recent advances in partially observable RL, which typically leverage specific structural properties (observability, decodability, stability, etc.) other than trajectory eluder dimension to obtain clearer bounds. We identify a broad and practically relevant class of MDPs that are learnable under setting (A), with upper bounds scaling with the coverability of the underlying MDP—a relatively intuitive and well-understood complexity measure. \n\n- Importantly, coverability serves as an intrinsic complexity measure of the MDP structure and remains bounded even when the eluder dimension of the value function class becomes unbounded (as with neural networks).\n\nWhile we recognize that setting (B) is indeed more general than (A), setting (A) remains significantly more challenging than learning with per-step (process) reward feedback. Previous works addressing setting (A) have primarily focused on linear rewards or functions with manageable trajectory eluder dimension. In this context, we believe our upper bounds using state-action coverability represent a meaningful theoretical contribution that involves several novel analytical techniques.\n\nWe are grateful for the reviewer's observation that the phrase \"comprehensive theoretical analysis of outcome-based online RL\" could be clearer. In our revision, we will explicitly highlight that: (1) this work specifically addresses \"sum of rewards\" outcome feedback, and (2) we will provide appropriate context regarding other more general outcome feedback models considered in related literature.\n\n---\n\n> If the assumption that the outcome-based feedback is given by the sum of rewards is relaxed, how do you think the results would change?\n\nWhen the outcome feedback takes the form of a general, non-linear function $R(s_1,a_1,\\cdots,s_H,a_H)$, our upper bounds would indeed hold, but with coverability measured over the trajectory space rather than state-action space. However, trajectory coverability is typically much larger than standard coverability and, in worst-case scenarios, grows exponentially with the horizon—a highly undesirable property.\n\nThis exponential dependence appears to be fundamental rather than an artifact of our analysis. For example, for the threshold outcome model (which outputs 1 if the sum of rewards exceeds a fixed threshold and 0 otherwise), it is possible to embed any H-step combination lock into an H-step MDP with a single state (as demonstrated by Kausik et al., (2024)). This construction shows that any algorithm operating with only threshold feedback must incur an exponential sample complexity $\\Omega(|\\mathcal{A}|^H)$ in the worst case.\n\nWe hope this clarification helps position our work appropriately within the broader outcome-based RL literature, and we thank the reviewer again for this valuable feedback."}, {"review_id": "8rTkJE1kCi", "reviewer": "Reviewer_EJnZ", "summary": "This paper studies online reinforcement learning with trajectory-wise reward feedback. While previous works have focused on structured rewards such as linear functions, this paper considers general function approximation. Under standard realizability and completeness assumptions, the authors propose an algorithm and establish an $\\tilde{O}(H^3/\\epsilon^2)$ sample complexity guarantee. They also provide theoretical analysis in the setting of preference-based learning. Finally, the authors present an example MDP in which all outcome-based reinforcement learning algorithms incur exponential sample complexity.", "questions": "1. Could the authors clarify whether the algorithm collects $H$ trajectories per iteration by executing the policy $\\pi \\circ h\\,\\pi_{ref}$?\n2. In offline learning, $\\mu$ usually refers to the data distribution. In the online setting, however, data is generated interactively over time. Could the authors clarify what $\\mu$ specifically represents in online RL?\n3. In the lower bound proof, the ReLU bandit example (Section 6.1.4) demonstrates a linear sample complexity in $T$. Is this because the example violates Assumption 1 and Assumption 2? Clarification on whether the lower bound arises from the failure of these assumptions would be appreciated.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths: \n 1. This work is the first to provide a theoretical analysis of online reinforcement learning with outcome-based reward feedback under general function approximation.\n 2. The authors present a counterexample MDP in which per-step reward RL algorithms are sample-efficient, whereas outcome-based algorithms suffer from exponential sample complexity. This highlights a fundamental difference between outcome-based MDPs and standard MDPs.\n\n### Weakness\n1. In the loop between steps 4 and 7 of the Algorithm 1, the policy $\\pi \\circ h\\,\\pi_{ref}$ is executed once per iteration to collect a trajectory. This means that each iteration yields $H$ trajectories in total, and the entire algorithm generates $TH$ trajectories over $T$ iterations. This differs from standard online RL algorithms, which usually collect only one trajectory per iteration. I haven't carefully checked the proof details, so it's unclear whether a typo error exists at this point. However, it seems that the theoretical guarantees rely on collecting $H$ times more trajectory data. If those additional trajectories were omitted, the sample complexity of the algorithm could increase accordingly.\n\n2. Some notations are not explained, such as $d_h^{\\pi}$ and $\\mu_h$, although they are standard notations in offline learning.\n\n3. In the definition of Bellman completeness, the Bellman operator is applied to vector-valued functions $f$ ($f_1,...,f_H$), whereas in Assumption 2, it is applied to scalar-valued functions $f_{h+1}$.", "was_revised": true, "final_justification": "My concerns have been addressed in the rebuttal phase.", "rebuttal": "We thank the reviewer for the detailed review. Below, we address the concerns raised in the review:\n\n> In the loop between steps 4 and 7 of the Algorithm 1, the policy $\\pi\\circ_h \\pi_{\\rm ref}$ is executed once per iteration to collect a trajectory. This means that each iteration yields $H$ trajectories in total, and the entire algorithm generates $TH$ trajectories over $T$ iterations. This differs from standard online RL algorithms, which usually collect only one trajectory per iteration.\n\nIndeed, our algorithm collects $H$ trajectories per iteration by executing the policy $\\pi\\circ_h \\pi_{\\rm ref}$ for each $h$. This strategy makes the algorithm actively explore the environment. While it is not a standard one in the literature of online RL, such a “per-step” exploration is commonly adopted in the literature on partially observable RL, where active exploration is crucial for sample efficiency guarantee.\n\nAs a remark, our algorithm can also be modified so that it only collects one trajectory per iteration, by uniformly sampling a step h and executing $\\pi\\circ_h \\pi_{\\rm ref}$. Our analysis can similarly be adopted with such a modified algorithm. However, to keep the presentation as simple as possible, we chose to present the current version of the algorithm. \n\n---\n\n> Some notations are not explained, such as $d^\\pi_h$ and $\\mu_h$, although they are standard notations in offline learning. …In offline learning, $\\mu_h$ usually refers to the data distribution. In the online setting, however, data is generated interactively over time. Could the authors clarify what  specifically represents in online RL?\n\nWe thank the reviewer for bringing up this subtle point. $d^\\pi_h$ is defined to be the occupancy measure at layer $h$. More specifically, for any state $s\\_h\\in \\mathcal{S}\\_h$ and action $a_h$, $d^\\pi\\_h = \\mathbf{Pr}\\_{\\tau\\sim \\pi}[(s_h, a_h)\\in \\tau]$, where $\\tau$ is a trajectory sampled according to policy $\\pi$. Additionally, $\\mu_h$ appears in the definition of the coverability coefficient in online learning. The coverability coefficient is defined as \n$$\nC\\_{\\rm cov}=\\min\\_{\\mu_1,\\cdots,\\mu_H}\\max_{h\\in [H],\\pi\\in\\Pi}\\left\\|\\left\\|{\\frac{d^\\pi_h}{\\mu_h}}\\right\\|\\right\\|\\_{\\infty},\n$$\nwhere there is an infimum over *all* distributions $\\mu_1,\\cdots,\\mu_H$ over $\\mathcal{S}\\times\\mathcal{A}$. By contrast, in offline RL, the sample complexity guarantees typically scale with the *concentrability coefficient*:\n$$\nC\\_{\\rm conc}=\\max_{h\\in [H],\\pi\\in\\Pi}\\left\\|\\left\\|{\\frac{d^\\pi_h}{\\mu_h}}\\right\\|\\right\\|\\_{\\infty},\n$$\nwhere $\\mu\\_1,\\cdots,\\mu\\_H$ are the *fixed* offline data distribution. Therefore, the coverability coefficient equals the smallest possible concentrability among all possible offline data distributions. The above relation between the coverability coefficient and the concentrability coefficient provides a bridge between offline RL and online RL, and the coverability coefficient has been identified as a natural and intrinsic complexity of online RL (see e.g., (Xie et al., 2023), and also [A] and [B]).\n\n---\n\n> In the definition of Bellman completeness, the Bellman operator is applied to vector-valued functions $f (f\\_1,...,f\\_H)$, whereas in Assumption 2, it is applied to scalar-valued functions $f_{h+1}$.\n\nThank you for pointing out this typo. We will update the definitions in the revision, so that Bellman operator is defined on the vector-valued function and consistent with the existing work.\n\n---\n\n> In the lower bound proof, the ReLU bandit example (Section 6.1.4) demonstrates a linear sample complexity in $T$. Is this because the example violates Assumption 1 and Assumption 2?\n\nIn the ReLU bandit example, both Assumption 1 and 2 are satisfied, but the coverability $C_{\\rm cov}=\\exp(\\Omega(d))$, as the set of all (possibly optimal) actions is exponentially large. We will clarify this in the revision.\n\nReferences:\n\n[A] The Power of Resets in Online Reinforcement Learning. Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin.\n\n[B] Scalable online exploration via coverability. Philip Amortila, Dylan J Foster, Akshay Krishnamurthy."}, {"review_id": "g3f3gmSX2R", "reviewer": "Reviewer_mCk3", "summary": "The paper studies outcome based (aka trajectory feedback, or aggregate feedback) RL in the general function approximation setup, subject to the standard coverability, realizability and completeness assumptions typically required for sample efficient learning with general function approximation.\n\nIn more detail, the algorithms in the paper receive as input a class of reward functions $\\mathcal R$ and a class of Q functions $\\mathcal F$, and output an $\\epsilon$-optimal policy after roughly $C_{\\rm cov}N/\\epsilon^2$ interaction episodes, where $C_{\\rm cov}$ denotes the coverability coefficient and $N$ the covering number of $\\mathcal R$ and $\\mathcal F$.\nAn additional error term scales linearly with the violation of the Bellman completeness and realizability assumptions. \n\nThe algorithms presented include:\n1. The fundamental trajectory feedback setup, which is computationally inefficient in general.\n2. A simplified algorithm for the case of deterministic dynamics, which is efficient assuming oracle access to $\\mathcal F$.\n3. An extension of the fundamental setup algorithm to the case of preference feedback.\n\nFinally, a lower bound is established that demonstrates standard semi bandit feedback is easier than trajectory feedback in the general function approximation setup (in the sense that the former admits sample efficient algorithms, while the latter does not).", "questions": "* What is the reason for employing the reference policy in the exploration phase of Alg1 (similarly Alg3)? As you explained, you make no assumption regarding the distribution of actions it chooses. If this is the case, why not just stick with $\\pi^{(t)}$ for the entire episode, in favor of simplicity?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* This work is the first to study trajectory feedback in the general function approximation setup. Prior works only study the tabular and linear setups.\n* Three algorithms of independent interest are studied.\n* The paper is well written with clear presentation, and is easy to follow.\n\n### Weaknesses\n* Nothing stands out.\n\n### Minor comments\n- Line 39: \"where the reward function is assumed to be well structured\" --- some of the works mention consider the tabular setup, and do not make any particular assumptions on the reward shape. What exactly do you mean by \"well structured\" or \"well behaved\"? If I understand correctly the distinguishing feature of the present paper is that it obtains rates independent of $S$. But, this does not relate to well behavedness of the reward function. Works that study the linear setup such as Cassel et al. 24 consider linear MDPs, which is a much stronger assumption than just linear reward.\n- Line 126: \"Bellman operator\" might be a better heading?\n- Line 175: What is $d$?\n- Line 256: \"which is widely used on RLHF literature\" (on $\\to$ in)\n- Line 300: \"Is outcome-based samples are statistically equivalent\"", "was_revised": true, "final_justification": "I have decided to maintain my original rating favoring acceptance. Following additional discussions, it appears computational efficiency, while being a weakness of the proposed method, is not by any means a major one or very specific to this work.\n\nAs noted by the authors and in the AC / reviewers discussions, the issue of computational intractability is common in many algorithms in RL with general function approximation.", "rebuttal": "We thank the reviewer for the detailed review. Below, we address the concerns raised in the review:\n\n> **Line 39 Meaning of \"well structured\" or “well behaved” reward functions**\n\nWe use this adjective to describe that the reward function is either linear with respect some features of state-action pairs, or slightly more generally, admitting bounded *trajectory* eluder dimension. Assumptions on well-behaved reward function is very common in previous work, including in tabular MDP (where the reward function is automatically linear with respect to the $|\\mathcal{S}|\\times |\\mathcal{A}|$-dimensional feature) and linear MDP (where the linear reward function is part of the linearity structure).\n\nWe will clarify this in the revision.\n\n---\n\n> **Line 126 Bellman operator as the heading?**\n\nThanks for the suggestions. We will update it in our revision.\n\n---\n\n> **Line 175 what’s $d$?** \n\nIn the setting where the function classes are parametric, $d$ is the dimension of the parametric model, i.e.. the number of “free parameters”. For example, when the function classes are linear with respect to a feature map, $d$ is the dimension of the feature.\n\n---\n\n> **Line 256 and Line 300**\n\nThanks for pointing out the typo, we will fix them in the version.\n\n---\n\n> **Reason and choice of reference policy in Alg1 and Alg3**\n\nThe point of adopting the policy $\\pi\\circ_h \\pi_{\\mathrm{ref}}$ is to make the algorithm more exploratory. The fixed reference policy serves as a comparator for the policy $\\pi^{(t)}$, and it has to be the same across different iterations. Based on this reasoning (and our theoretical analysis), we cannot choose $\\pi_{\\mathrm{ref}}$ to be $\\pi^{(t)}$, which changes over time."}, {"review_id": "NFmbLfA9Ec", "reviewer": "Reviewer_YCwT", "summary": "This paper presents a comprehensive analysis of outcome-based online reinforcement learning, addressing the fundamental credit assignment challenge when rewards are observed only at the end of a trajectory. The authors develop a provably sample-efficient algorithm (Algorithm 1) for settings with general function approximation, achieving a sample complexity of $\\tilde{O}(C_{cov}H^{3}/\\epsilon^{2})$. A key contribution is the identification of a fundamental exponential separation, revealing that for certain MDPs, outcome-based feedback is unavoidably less efficient than per-step rewards. For the special case of deterministic MDPs, the paper also proposes a significantly simpler and more computationally efficient variant (Algorithm 2) that eliminates the strong completeness assumption required by the primary algorithm. Finally, the framework is extended to preference-based feedback settings, demonstrating that similar statistical efficiency can be achieved.", "questions": "On the Computational Feasibility of Algorithm 1: Beyond the special case of deterministic MDPs, could you elaborate on potential pathways to make this optimization computationally feasible, even if it requires approximations? For example, are there specific structural assumptions on the function classes $\\mathcal{F,R,G}$ (beyond determinism) or approximation techniques (e.g., alternating optimization, gradient-based methods for the outer loop) that you believe could make Algorithm 1 practical?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- strengths:\n\t- Foundational and General Theoretical Framework: This paper provides what appears to be the first comprehensive theoretical analysis for online RL with outcome-based feedback under the challenging general function approximation setting. By developing a provably sample-efficient algorithm, the authors establish a rigorous and foundational contribution that is applicable to complex environments where tabular methods are insufficient.\n\t- Insight on Fundamental Limits: A key strength is the paper's lower bound analysis, which establishes a fundamental exponential separation between outcome-based and per-step feedback. It proves that for certain MDPs, outcome-based feedback is inherently less efficient, requiring exponentially more samples to learn a near-optimal policy. This result clearly defines the statistical barriers of the problem and provides crucial context for when outcome-based learning is tractable.\n\t- Practical Relevance and Extensions: The paper's impact is broadened by its thoughtful extensions and methodological insights. The approach is generalized to handle preference-based feedback, directly connecting the theory to practical Reinforcement Learning from Human Feedback (RLHF) scenarios. For deterministic MDPs, the authors provide a much simpler and more computationally efficient algorithm (Algorithm 2) that eliminates the need for a completeness assumption. Finally, the work offers clear guidance by demonstrating that jointly optimizing the reward and value functions is essential, as simpler decoupled approaches can fail. \n\n\n- weaknesses\n\t- The central contribution, Algorithm 1, hinges on solving a joint optimization problem (Eq. 6) to estimate the value and reward functions. While theoretically elegant, this step poses significant practical challenges. The objective function itself involves a Bellman loss term, $L_D^{BE}(f;R)$, which requires computing an infimum over function class $\\mathcal G$. This creates a nested, max-min-like optimization problem. In the general function approximation setting, where $\\mathcal F$ and $\\mathcal R$ are typically non-convex (e.g., neural networks), solving this outer maximization for a global optimum is generally intractable.", "was_revised": true, "final_justification": "I would like to keep my original score since the authors have addressed my concern.", "rebuttal": "We thank the reviewer for the review. Below, we address the concerns raised in the review:\n\n> The central contribution, Algorithm 1, hinges on solving a joint optimization problem (Eq. 6) to estimate the value and reward functions. While theoretically elegant, this step poses significant practical challenges. The objective function itself involves a Bellman loss term, which requires computing an infimum over function class . This creates a nested, max-min-like optimization problem. In the general function approximation setting, where  and  are typically non-convex (e.g., neural networks), solving this outer maximization for a global optimum is generally intractable.\n\nWe admit that to solve the optimization problem in Algorithm 1 can be computationally intractable without proper assumptions. Broadly speaking, in the literature of RL theory, achieving computational efficiency RL with general function approximation has long been an open problem. To the best of our knowledge, it is only partly resolved under restricted problems (e.g., MDPs with linear structure) or stronger access oracle (reset). \n\nWe note that under reset access, the max-min optimization in our algorithm can indeed be replaced by a maximization problem, following the approach of [A]. Achieving computational tractable outcome-based RL beyond the setting of reset access can be an important direction of future work. \n\n---\n\n> On the Computational Feasibility of Algorithm 1: Beyond the special case of deterministic MDPs, could you elaborate on potential pathways to make this optimization computationally feasible, even if it requires approximations? For example, are there specific structural assumptions on the function classes  (beyond determinism) or approximation techniques (e.g., alternating optimization, gradient-based methods for the outer loop) that you believe could make Algorithm 1 practical?\n\nAs mentioned above, with reset access, the algorithm can be modified to avoid the max-min optimization. In addition, gradient-based approximation/alternating optimization can indeed be applied to the max-min optimization problem, assuming that the function classes are parametrized (e.g., class of neural networks). Particularly, under certain regularity conditions, the existing convergence results may be applied, showing that a local minima can be found. We believe analyzing the optimization landscapes of the GOLF-based algorithms is an important future direction for RL theory.\n\n[A] The Power of Resets in Online Reinforcement Learning. Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin."}]

Author rebuttal:

Meta-review: The paper studies the sample complexity of RL problems with outcome/aggregated/trajectory feedback with general function approximation. Assuming realizability and completeness, the authors prove sample complexity bounds of $\tilde{O}(C_{cov}H^3/\epsilon^2)$ (where $C_{cov}$ is the coverability coefficient), via an intractable algorithm. They also suggest a simplified more tractable approach for deterministic MDPs, which only requires realizability, and extend the results to preference-based feedback. Finally, the authors show an exponential separation between per-step feedback and outcome feedback when coverability is not satisfied.

The reviewers agreed that this work is a well-rounded paper with several contributions, including a new statistically-efficient algorithm for RL with trajectory feedback and general function approximation, separation from the per-step feedback model, a simplified algorithm for deterministic MDPs, and more. The only potential weakness that was discussed between the reviewers was the intractability of the general approach. It was agreed upon that, in light of the previous literature in similar settings, this is only a minor weakness. The authors are still encouraged to explore whether the additional coverability assumption could be utilized to design computationally-efficient algorithms.
Decision: Accept (poster)