Paper Review: Exploring the Limit of Outcome Reward for Learning Mathematical Reasoning

Lyu et al. (2025)—ArXiv

TLDR

New RL framework (OREAL) for training Binary Outcome Based Reasoning models. Prove that BC (Behavioral Cloning, i.e., SFT) on positive trajectories from BoN (Best-of-N) sampling is sufficient to learn the KL-regularized optimal policy in binary feedback environments. They also apply a token-level RM to sample important tokens in reasoning traces for learning.

Interesting Bits

Lemma 2.1 (Learning from Positive Samples): Let $\pi(\theta, s)$ be a distribution over parameters $\theta$ and trajectory $s$, where each $s$ is associated with a binary reward $R(s) \in \{0, 1\}$. Define $p \triangleq \mathbb{E}_{s \sim \pi(\theta, \cdot)}[R(s) = 1] > 0$. Consider the BoN sampling: $n = n_0 \rightarrow \infty$ and sample $\{s_1, s_2, \ldots, s_n\}$ i.i.d. from $\pi_\theta$. BoN selects $s^*$ uniformly from the subset with $R(s_i) = 1$. We have that, The probability of selecting $s^*$ is converge to $\frac{\pi(\theta, s)}{p}$, which is independent of $n$.

Breakdown:

• “Let $\pi(\theta, s)$ be a distribution over parameters $\theta$ and trajectory $s$…”

  • $\pi(\theta, s)$: This represents a policy (the LLM), parameterized by $\theta$, that defines a probability distribution over trajectories $s$. $\pi(\theta, s)$ gives the probability of observing the trajectory $s$ when following the policy parameterized by $\theta$.
  • $s$: A trajectory (in this case, a reasoning trace for a query) generated by the policy.

• “… where each $s$ is associated with a binary reward $R(s) \in \{0, 1\}$.”

  • $R(s) \in \{0, 1\}$: The reward function $R$ is binary (as now common with ORMs). It assigns a reward of 1 if the trajectory $s$ attains the correct solution, and 0 otherwise.

• “Define $p \triangleq \mathbb{E}_{s \sim \pi(\theta, \cdot)}[R(s) = 1] > 0$.”

  • $p \triangleq \mathbb{E}_{s \sim \pi(\theta, \cdot)}[R(s) = 1]$: This defines $p$ as the probability of getting a positive reward when we sample a trajectory $s$ from the policy $\pi(\theta, \cdot)$. The notation $\mathbb{E}_{s \sim \pi(\theta, \cdot)}[\cdot]$ denotes the expectation over trajectories sampled from the policy $\pi(\theta, \cdot)$, that is $\frac{\#\text{Trajectories that attain reward 1}}{\#\text{Total trajctories}}$.
  • $p > 0$: This assumption states that there is a non-zero probability of achieving a positive reward under the policy $\pi(\theta, \cdot)$. This is a necessary condition; otherwise, if $p=0$, we would never get positive samples to learn from (i.e., when sampling enough times, the model can at least once achieve a correct solution).

• “Consider the BoN sampling: $n = n_0 \rightarrow \infty$ and sample $\{s_1, s_2, \ldots, s_n\}$ i.i.d. from $\pi_\theta$.”

  • BoN sampling: Best-of-N sampling. We are generating $n$ trajectories.
  • $n = n_0 \rightarrow \infty$: The number of sampled trajectories $n$ is initially some number $n_0$ and is considered to go to infinity. This is a theoretical consideration to analyze the asymptotic behavior. In practice, $n$ would be a large but finite number.
  • $\{s_1, s_2, \ldots, s_n\}$ i.i.d. from $\pi_\theta$: We sample $n$ trajectories independently and identically distributed (i.i.d.) according to the policy $\pi_\theta = \pi(\theta, \cdot)$.

• “BoN selects $s^*$ uniformly from the subset with $R(s_i) = 1$.”

  • Subset with $R(s_i) = 1$: From the $n$ sampled trajectories $\{s_1, s_2, \ldots, s_n\}$, we consider only those trajectories that received a positive reward (i.e., $R(s_i) = 1$). Let’s call this set of successful trajectories $S^+ = \{s_i \mid R(s_i) = 1, i \in \{1, 2, \ldots, n\}\}$.
  • BoN selects $s^*$ uniformly from $S^+$: If $S^+$ is not empty, BoN sampling selects one trajectory $s^*$ uniformly at random from the set $S^+$.

• “We have that, The probability of selecting $s^*$ is converge to $\frac{\pi(\theta, s)}{p}$, which is independent of $n$.”

  • “The probability of selecting $s^*$ is converge to $\frac{\pi(\theta, s)}{p}$…”: This is the core result of the lemma. It states that as $n \rightarrow \infty$, if we perform BoN sampling as described, the probability distribution of the selected trajectory $s^*$ converges to a distribution that is proportional to $\pi(\theta, s)$ and normalized by $p$.
  • $\frac{\pi(\theta, s)}{p}$: This is a normalized probability distribution. Note that summing $\frac{\pi(\theta, s)}{p}$ over all trajectories $s$ that can have $R(s)=1$ would sum to 1 (if we consider the appropriate domain). Basically, we are conditioning on the event that we obtained a positive reward. We can think of $p = \sum_{s: R(s)=1} \pi(\theta, s)$ (if trajectory space is discrete, or integral if continuous), so $\frac{\pi(\theta, s)}{p} = \frac{\pi(\theta, s)}{\sum_{s': R(s')=1} \pi(\theta, s')}$, which is the conditional probability $\pi(\theta, s | R(s)=1)$.
  • “… which is independent of $n$.”: The limiting distribution $\frac{\pi(\theta, s)}{p}$ does not depend on the number of samples $n$ used in BoN sampling, once $n$ is sufficiently large (theoretically, as $n \rightarrow \infty$). The value of $n$ affects how quickly we approach this limiting distribution, but the distribution itself is determined by the policy $\pi(\theta, s)$ and the probability of positive reward $p$.

Implications

What does this lemma tell us?

In essence, Lemma 2.1 states that when we use BoN sampling and select a trajectory $s^*$ from the successful ones, the distribution of these selected trajectories, in the limit as we sample a very large number of initial trajectories, becomes proportional to the original policy distribution $\pi(\theta, s)$, but conditioned on achieving a positive reward.

Why is this important?

• Focus on Successful Trajectories: BoN sampling naturally focuses on trajectories that are successful (positive reward). In scenarios where positive rewards are sparse but crucial for learning, BoN helps to concentrate learning efforts on these valuable samples.
• Implicit Policy Improvement: By sampling from $\pi_\theta$ and then selecting from the positive reward set, we are effectively biasing our selection towards trajectories that are more likely under $\pi_\theta$ and lead to positive rewards. This can be seen as a form of implicit policy improvement or directed exploration.
• Connection to Importance Sampling: The form $\frac{\pi(\theta, s)}{p}$ is reminiscent of importance sampling. Here, we are implicitly re-weighting trajectories based on the condition of positive reward.
• Theoretical Foundation for BoN in Positive Reward Learning: This lemma provides a theoretical grounding for using BoN sampling in situations where we are primarily interested in learning from positive examples, and rewards are binary indicating success or failure.

Proof:

Lemma 2.1 (Formal Statement): Let $\pi(\theta, s)$ be a probability distribution over trajectories $s$, and let $R(s) \in \{0, 1\}$ be a binary reward associated with each trajectory $s$. Define $p = \mathbb{E}_{s \sim \pi(\theta, \cdot)}[R(s) = 1] > 0$. For a given $n \in \mathbb{N}$, let $\{s_1, s_2, \ldots, s_n\}$ be $n$ independent and identically distributed (i.i.d.) samples from $\pi(\theta, \cdot)$. Let $S^+ = \{s_i \mid R(s_i) = 1, i \in \{1, 2, \ldots, n\}\}$. If $S^+ \neq \emptyset$, let $s^*$ be selected uniformly at random from $S^+$. We want to show that for any trajectory $s$ with $R(s) = 1$, the probability of selecting $s^* = s$ (in a suitable sense as $n \to \infty$) is proportional to $\pi(\theta, s) / p$. More precisely, we will show that for any trajectory $s$ with $R(s) = 1$:

$\lim_{n \to \infty} P(s^* = s \mid S^+ \neq \emptyset) = \frac{\pi(\theta, s)}{p}$

---

Let $s$ be a trajectory such that $R(s) = 1$. We are interested in the probability $P(s^* = s \mid S^+ \neq \emptyset)$. By definition of conditional probability, we have:

$P(s^* = s \mid S^+ \neq \emptyset) = \frac{P((s^* = s) \cap (S^+ \neq \emptyset))}{P(S^+ \neq \emptyset)}$

First, let’s consider the denominator $P(S^+ \neq \emptyset)$. The event $S^+ = \emptyset$ means that for all $i \in \{1, 2, \ldots, n\}$, $R(s_i) = 0$. Since $s_i$ are i.i.d. and $P(R(s_i) = 1) = p$, we have $P(R(s_i) = 0) = 1 - p$. Thus, $P(S^+ = \emptyset) = P(\forall i, R(s_i) = 0) = \prod_{i=1}^n P(R(s_i) = 0) = (1 - p)^n$ Since $p > 0$, as $n \to \infty$, $(1 - p)^n \to 0$. Therefore, $P(S^+ \neq \emptyset) = 1 - P(S^+ = \emptyset) = 1 - (1 - p)^n \to 1$ as $n \to \infty$.

Now let’s consider the numerator $P((s^* = s) \cap (S^+ \neq \emptyset))$. For $s^* = s$ to occur, it must be the case that at least one of the sampled trajectories is $s$ and has a positive reward (which is true since $R(s) = 1$), and when we sample from $S^+$, we select one of the instances of $s$.

Let $N_s(n)$ be the number of times the trajectory $s$ appears in the sample $\{s_1, \ldots, s_n\}$, i.e., $N_s(n) = \sum_{i=1}^n \mathbb{I}(s_i = s)$. Let $N^+(n)$ be the number of trajectories with positive reward in the sample, i.e., $N^+(n) = |S^+| = \sum_{i=1}^n \mathbb{I}(R(s_i) = 1)$.

If $N^+(n) > 0$, BoN selects uniformly from $S^+$. The event $s^* = s$ occurs if and only if at least one of the selected trajectories in $S^+$ is $s$, and when we choose uniformly from $S^+$, we choose one of these instances. Since we are interested in the probability of selecting a trajectory that is equal to $s$, and all instances of $s$ in $S^+$ are indistinguishable in the uniform selection process, the probability of selecting $s^* = s$ given $S^+ \neq \emptyset$ is the ratio of the expected number of instances of $s$ in $S^+$ to the expected size of $S^+$, in the limit.

More formally, consider the number of indices $i$ such that $s_i = s$. Let $I_s = \{i \mid s_i = s, 1 \leq i \leq n\}$. Then $|I_s| = N_s(n)$. Also, let $I^+ = \{i \mid R(s_i) = 1, 1 \leq i \leq n\}$. Then $|I^+| = N^+(n)$. If $I^+ \neq \emptyset$, we select an index $j \in I^+$ uniformly at random. Then $s^* = s_j$. The event $s^* = s$ occurs if the chosen index $j \in I^+$ is also in $I_s$. Since $R(s) = 1$, if $s_i = s$, then $R(s_i) = R(s) = 1$. Thus, $I_s \subseteq I^+$. So, $I_s \cap I^+ = I_s$. Therefore, the number of indices $j \in I^+$ such that $s_j = s$ is $|I_s| = N_s(n)$. And the total number of indices in $I^+$ is $|I^+| = N^+(n)$.

If $N^+(n) > 0$, then the probability of choosing an index $j \in I^+$ such that $s_j = s$ is $\frac{|I_s|}{|I^+|} = \frac{N_s(n)}{N^+(n)}$. Thus, given $S^+ \neq \emptyset$ (which is equivalent to $N^+(n) > 0$), the probability of selecting $s^* = s$ is $\frac{N_s(n)}{N^+(n)}$.

We know that by the Law of Large Numbers, as $n \to \infty$: $\frac{N_s(n)}{n} = \frac{1}{n} \sum_{i=1}^n \mathbb{I}(s_i = s) \xrightarrow{p} \mathbb{E}[\mathbb{I}(s_i = s)] = P(s_i = s) = \pi(\theta, s)$ $\frac{N^+(n)}{n} = \frac{1}{n} \sum_{i=1}^n \mathbb{I}(R(s_i) = 1) \xrightarrow{p} \mathbb{E}[\mathbb{I}(R(s_i) = 1)] = P(R(s_i) = 1) = p$ where $\xrightarrow{p}$ denotes convergence in probability.

By the Continuous Mapping Theorem and the ratio theorem for convergence in probability (since $p>0$), we have: $\frac{N_s(n)}{N^+(n)} = \frac{N_s(n)/n}{N^+(n)/n} \xrightarrow{p} \frac{\pi(\theta, s)}{p}$ This means that for large $n$, $\frac{N_s(n)}{N^+(n)}$ is close to $\frac{\pi(\theta, s)}{p}$ with high probability.

Since $P(s^* = s \mid S^+ \neq \emptyset) = \frac{N_s(n)}{N^+(n)}$ when $N^+(n) > 0$, and we are interested in the limit as $n \to \infty$, we can say that in probability, for large $n$, $P(s^* = s \mid S^+ \neq \emptyset) \approx \frac{\pi(\theta, s)}{p}$.

To make this more rigorous in terms of limit of probabilities, we can use the convergence in probability to convergence in distribution in this case. Since $\frac{N_s(n)}{N^+(n)} \xrightarrow{p} \frac{\pi(\theta, s)}{p}$, it also converges in distribution to a degenerate random variable at $\frac{\pi(\theta, s)}{p}$. Thus, the limit of the probability is indeed $\frac{\pi(\theta, s)}{p}$.

Therefore, $\lim_{n \to \infty} P(s^* = s \mid S^+ \neq \emptyset) = \frac{\pi(\theta, s)}{p}$

This completes the formal proof. The probability of selecting a specific trajectory $s$ (with $R(s) = 1$) using BoN sampling, conditioned on getting at least one positive sample, converges to $\frac{\pi(\theta, s)}{p}$ as the number of initial samples $n$ goes to infinity.