Offline reinforcement learning is typically analyzed under process-level reward supervision, yet many sequential decision datasets record only trajectory-level outcomes. We develop a statistical theory for offline policy optimization from such outcome-level supervision. We first study the canonical setting where the target remains the expected cumulative reward, but each offline trajectory provides only a scalar label whose conditional mean is the cumulative return. We propose OPAC, a pessimistic actor-critic algorithm that learns a latent reward model and optimizes a policy from trajectory-level labels. We prove a high-probability guarantee of order $\widetilde O(H^2\sqrt{C_{sa}(π^\star)/n})$ and a matching lower bound, characterizing the sharp statistical cost of replacing process-level rewards with one trajectory-level label. We then extend the principle to preference-based feedback, preserving the leading horizon and concentrability dependence up to preference-model constants. Finally, we study generalized outcome-based offline RL, where both the supervision and the objective are trajectory-level quantities induced by a nonlinear aggregation of latent per-step rewards. This problem is not learnable in general: for all-success objectives, any offline learner may require $Ω(2^H)$ trajectories even with deterministic transitions and constant concentrability. We then identify a tractable regime through two structural coefficients, $κ_μ(σ)$ and $χ_μ(σ)$, capturing information loss in outcome aggregation and generalized Bellman updates, under which generalized OPAC achieves polynomial sample complexity. Together, our results delineate when outcome-level supervision enables sample-efficient offline control and when missing process-level rewards create fundamental statistical barriers.
Alex: Welcome to another episode of ResearchPod. Today, we're looking at a fundamental challenge in artificial intelligence: how do you teach a system to perform well when you only ever see the final result?
Sam: That's the core puzzle. In most AI training, a system gets a small signal after every single action—a nudge that says "good move" or "bad move." But in many real-world situations, you only find out at the very end whether the whole sequence worked.
Alex: So this paper is basically asking how we can learn from the "what"—the final outcome—without having the "how"—the step-by-step feedback?
Sam: Exactly. And it's a harder problem than it might sound. Think about learning to cook a meal. If someone only tells you "this tastes great" or "this is awful" after you've finished, you have no idea whether you oversalted the pasta, undercooked the chicken, or got the timing wrong. You have to work backward from one piece of information to figure out dozens of decisions. This research provides a mathematical blueprint for doing exactly that—identifying when it's possible and where the fundamental limits lie.
Alex: So if I'm training a robot to assemble a circuit board, I might only know if the board works at the end. I don't know which specific solder joint caused the failure. That's the kind of problem we're talking about?
Sam: That's a precise analogy. The system has to work backward from that single "pass" or "fail" signal and guess which actions along the way were helpful. The authors propose a specific approach to solve this, which they call OPAC—short for "Outcome-based Pessimistic Actor-Critic."
Alex: Let's take that apart. Why would a robot need to be "pessimistic"?
Sam: Here's the issue. This research is about what's called "offline" learning—the system trains on a fixed collection of past data, like a library of recorded attempts, rather than going out and trying things live. The danger is that the system might see a particular action that looks promising in the data, but there are only one or two examples of it. With so little evidence, it might wildly overestimate how good that action is. Being "pessimistic" is the solution: the system deliberately underestimates any action it doesn't have solid evidence for. It's a built-in caution that says, "If I haven't seen enough proof that this works, I'll treat it as risky."
Alex: So it's protecting itself from being overconfident about things it hasn't really tested. That makes sense. But how does it actually figure out which individual steps were good or bad, if all it has is that one final signal?
Sam: Think of it like a detective reconstructing a crime from a single piece of evidence. The system takes that final "success" or "failure" label and works through the sequence mathematically, estimating how much each step likely contributed to that outcome. It's building a theory of what probably happened, even though it never directly observed the value of each step. The paper calls these estimated values "latent rewards"—hidden signals that the system infers rather than measures directly.
Alex: And how well does this actually work? Is it as efficient as just having step-by-step feedback from the start?
Sam: Not quite, and the paper is honest about that. There's a genuine statistical cost to working from a single outcome rather than continuous feedback. The system needs more data to reach the same level of confidence. And here's the key insight: the difficulty scales with what the researchers call the "horizon"—essentially, the length of the task. The more steps between the first action and the final result, the harder it becomes to work out what mattered.
Alex: So a ten-step task is meaningfully harder than a three-step task, and a hundred-step task might be a different problem entirely?
Sam: That's the pattern. The paper proves that for most practical tasks, this added difficulty is manageable—it grows, but not catastrophically. However, there's a specific category of task where things become much harder: situations where every single step must be executed correctly for the outcome to succeed. If one mistake anywhere in the sequence means total failure, the system has almost no way to tell which step was the problem. The difficulty in those cases grows exponentially with the length of the sequence.
Alex: So there's a real boundary here. Some tasks are learnable from outcome-only feedback, and some effectively aren't—at least not without an enormous amount of data.
Sam: That's precisely what the paper establishes. And that distinction is useful in itself. Before this work, it wasn't clear where those limits sat. Now there's a formal framework that tells you, for a given task, whether outcome-based learning is feasible and roughly how much data you'd need. That's the kind of result that shapes how researchers design AI systems going forward—knowing in advance whether a particular approach will run into a wall.
Alex: Is there any way to make the harder cases more tractable? Or is this just a fundamental ceiling?
Sam: The paper points to two properties of a task that determine how hard it is. One is how much information gets lost when you compress a whole sequence into a single label. The other is how well the system can mathematically "undo" that compression—reverse-engineer the individual steps from the final signal. If both of those are well-behaved, learning works. If either one breaks down, you're in trouble. So the practical implication is that task design matters. If you can structure a problem so that the outcome is more informative—or break a long task into shorter checkpoints—you can move it from the "very hard" category into the "manageable" one.
Alex: So it's not just about the algorithm. It's also about how you set the problem up in the first place.
Sam: Exactly. And I think that's the deeper takeaway from this research. It's not just "here's a new algorithm." It's a clearer map of the terrain—showing which problems are tractable, which are not, and what properties of a task determine which side of that line you're on. For anyone building AI systems that operate in the real world, where step-by-step feedback is often impossible to get, that map is genuinely useful.
Alex: It's a more principled way of asking the question before you even start building. Thanks for walking us through it, Sam.
Sam: Thanks for listening to ResearchPod.