Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

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 O(C cov H 3 /ε 2 ) sample complexity, where C 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 perstep 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.

Policies, value functions, and the Bellman operator. A (randomized) policy π is specified as π h : S → ∆(A), and it induces a distribution P π of trajectory τ = (s 1 , a 1 , • • • , s H , a H ) by s 1 ∼ ρ, and for each h ∈ [H], a h ∼ π h (s h ), s h+1 ∼ T h (s h , a h ). We let E π [•] to be the corresponding expectation.

The expected cumulative reward of a policy π is given by J(π) := E π H h=1 R h (s h , a h ) . The value function and Q-function of π is defined as

Let π ⋆ denote an optimal policy (i.e., π ⋆ ∈ argmax π J(π)), and let V ⋆ and Q ⋆ be the corresponding value function and Q-function. It is well-known that (V ⋆ , Q ⋆ ) satisfies the following Bellman equation for each s ∈ S, a ∈ A, h ∈ [H]:

with the convention that V ⋆ H+1 = 0. Therefore, we define the Bellman operator T h as follows: for any f :

Then, it is straightforward to verify that the Bellman equation reduces to

. Complexity measure of the MDP. Coverability is a natural notion for measuring the difficulty of learning in the underlying MDP (Xie et al., 2022).

Definition 1 (Coverability). For a given MDP M and a policy class Π, the coverability C cov is defined as

where 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 C cov (Π) := C cov (Π; M ⋆ ) for succinctness.

Function approximation. In this paper, we work with (model-free) function approximation, where the learner have access to a value function class

The function class F and R consist of candidate functions to approximate Q ⋆ and the ground-truth reward function R ⋆ . 4 In the literature of RL with general function approximation, it is typically assumed that the function classes are realizable, i.e., Q ⋆ ∈ F and R ⋆ ∈ R. In this paper, we adopt the following relaxed realizability condition with a fixed approximation error ε app ≥ 0.

There exists Q ♯ ∈ F and R ♯ ∈ R such that max h∈

For each value function f ∈ F, it induces a greedy policy π f given by π f,h (s) := argmax a∈A f (s, a). Therefore, the value function class F induces a policy class Π F := π f : f ∈ F, and we take our policy class Π = Π F 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 ⊆ (X → R) and parameter α ≥ 0, an α-covering of H (with respect to the sup norm) is a subset H ′ ⊆ H such that for any f ∈ H, there exists f ′ ∈ H ′ with sup x∈X |f (x) -f ′ (x)| ≤ α. We define the α-covering number of H as N (H, α) := min|H ′ | : H ′ is a α-covering of H.