Learning Process Rewards via Success Visitation Matching for Efficient RL

Source: arXiv:2606.23640 · Published 2026-06-22 · By Raymond Tsao, Andrew Wagenmaker, Sergey Levine

TL;DR

This paper addresses the challenge of sparse outcome rewards in reinforcement learning (RL), where reward is only given upon task completion, causing difficult credit assignment and slow learning progress. The authors propose Success Visitation Matching (SVM), a method that transforms sparse outcome rewards into dense process rewards by training a discriminator to distinguish state-action visitations from successful versus unsuccessful episodes. The resulting reward encourages policies to match visitations of successful trajectories while avoiding unsuccessful ones, providing dense feedback throughout the episode instead of only at completion.

Theoretical analysis proves that in deterministic environments, policies maximizing the SVM reward also maximize the original sparse reward, thus preserving optimality. The method scales by estimating visitation ratios via classification rather than explicit density estimation. Experiments in robotic finetuning tasks on several benchmarks including LIBERO-90, RoboCasa, and real-world WidowX robot scenarios show SVM grants roughly 2x faster convergence and higher final success rates compared to baselines that use only sparse outcome rewards or prior reward shaping methods. The technique also improves finetuning pretrained vision-language-action policies and shows comparable results when applied to RL from demonstrations.

Overall, the paper introduces a theoretically grounded and practical approach to obtaining dense, automated process rewards from sparse outcomes using visitation-based discrimination, substantially improving sample efficiency and learning stability in challenging robotic manipulation tasks.

Key findings

• SVM process reward leads to roughly 2× faster RL finetuning convergence on LIBERO-90 tasks compared to outcome-only reward (Fig 3 and 7).
• On RoboCasa tasks, SVM enables over 90% success rate while baselines fail to learn meaningful improvement (Fig 4).
• In real-world WidowX robotic finetuning, SVM reaches >80% success with substantially fewer environment steps than outcome reward alone (Fig 6).
• Theorem 4.1 proves that in deterministic MDPs, optimizing SVM reward preserves the optimality of maximizing the original sparse outcome reward.
• SVM outperforms prior reward shaping baselines like SORS, SASR, GAIL-Reward, RND, and GVL in sample efficiency and final performance.
• Ablations show that using the log-ratio form for the discriminator output and updating discriminators with both successful and failed episodes online improves RL performance (Figs 10-12).
• SVM applied to RL from demonstrations matches GAIL performance and significantly improves over outcome-only rewards (Fig 8).
• Training a single discriminator over all timesteps rather than per timestep maintains strong performance while simplifying training.

Threat model

The adversary is the learning agent seeking to maximize rewards in an environment where task success is only sparsely signaled. The method assumes the agent can collect episodes labeled as successful or unsuccessful. The agent cannot manipulate the labeling process or corrupt stored episodes but tries to learn efficiently from sparse signals. There is no explicit adversarial threat in terms of malicious attackers modifying policies or rewards beyond the RL optimization challenge.

Methodology — deep read

1. Threat Model & Assumptions: The adversary in this context is essentially the RL agent trying to learn a policy to maximize a sparse outcome reward signal. The environment is modeled as a Markov Decision Process (MDP) with deterministic transitions (for the theorem) but the approach is empirically validated on stochastic environments as well. The learner has access only to the sparse outcome reward (0 everywhere except +1 at success) and past trajectories (labeled successful or unsuccessful). The goal is to efficiently learn a policy that maximizes success probability despite sparse reward signals.

2. Data: Provenance & Labels: The dataset D consists of past episodes collected during RL. Episodes with outcome reward 1 are labeled as successful (D+) and those with outcome 0 are unsuccessful (D−). Initially, this might include rollouts from a pretrained policy or demonstrations. The data is represented as state-action pairs indexed by timestep h within episodes. For large state spaces, explicit counts are infeasible; instead, state-action pairs with labels (successful or unsuccessful) are used to train a discriminator classifier.

3. Architecture / Algorithm: The core novelty is defining a dense process reward r_svm at each timestep h for state-action pair (s,a) as: r_svm_h(s,a) = rout(s) + λ * clip_beta [log (b_w+_h(s,a) / b_w-_h(s,a))], where b_w+_h and b_w-_h approximate visitation densities from D+ and D− respectively, λ and β are hyperparameters, and clip_beta clips the log-ratio to stabilize training.

Since explicit densities are hard to estimate, they train a discriminator b_f_h for each step that predicts probability a (s,a) came from D+, optimizing cross-entropy loss on labeled successful/unsuccessful samples. The visitation density ratio is then estimated by b_f_h(s,a) / (1 - b_f_h(s,a)). The final reward is used as the reward function for standard RL policy optimization.

4. Training Regime: Algorithm 1 alternates between policy update and discriminator update steps. Starting from a pretrained policy π_0 and initial rollouts, the discriminator is trained on D+ and D− episodes. The policy is improved by RL maximizing r_svm, which combines original sparse reward and visitation-based reward. After each episode, new episodes are added to D+ or D− depending on outcome reward and discriminator re-trained. They implement this with different RL algorithms: DSRL for diffusion policies, Residual RL for residual action learning, and RLPD for learning from demonstrations. Experiments use 3 random seeds for simulated tasks, averaging results.

5. Evaluation Protocol: Metrics: Success rate as fraction of episodes achieving outcome reward. Baselines include outcome reward alone, SORS, SASR, variants of GAIL, RND, and GVL. They evaluate on simulation benchmarks LIBERO-90 (16 tasks across 3 scenes), RoboCasa (3 tasks), and real-world WidowX robot manipulation tasks (3 tasks), along with RL finetuning pretrained VLAs and RL from demonstrations. Sample efficiency (training steps to reach target success) and final success rates are reported. Experiments include ablations on discriminator functional forms, policy extraction methods, and ratio clipping hyperparameter.

6. Reproducibility: Code or pretrained weights are not explicitly stated as released, but the method relies on common RL and classification components. Datasets LIBERO, RoboCasa, Robomimic, and BridgeData V2 are public or benchmark datasets. Details for discriminator training and RL hyperparameters are provided in appendices.

Example end-to-end: Starting with pretrained policy π_pre, collect initial episodes N0 to label success/failure. Train discriminator b_f to distinguish successful vs unsuccessful (s,a) pairs. Compute r_svm using discriminator outputs combined with original sparse reward. Use RL to update policy π to maximize r_svm. Collect new episodes using updated π, update D+ and D− sets, retrain discriminator, and repeat. This iterative procedure guides the policy with dense feedback signal towards matching successful visitation distributions, speeding credit assignment and convergence.

Technical innovations

• Introducing a success visitation matching (SVM) process reward that transforms sparse outcome rewards into dense step-level rewards by leveraging visitation density ratio between successful and unsuccessful episodes.
• Using a discriminator trained on labeled episodes (successful vs unsuccessful) to estimate visitation ratios as a classification problem, bypassing explicit density estimation.
• Proving theoretically that in deterministic MDPs, the optimal policy that maximizes the SVM reward is also optimal for the original sparse outcome reward.
• Formulating the SVM reward optimization as a KL-regularized RL objective encouraging closeness to successful visitations and divergence from unsuccessful ones.
• Continuous online updating of the discriminator with new successful and unsuccessful episodes to adapt visitation estimates during training, improving sample efficiency.

Datasets

• LIBERO-90 — 90 tasks in 20 scenes — public benchmark
• RoboCasa — image-based kitchen tasks (e.g., PnPCounterToCab) — public benchmark
• Robomimic — manipulation demonstrations and tasks (Can, Square) — public benchmark
• BridgeData V2 — 60,000+ robot trajectories for multi-task diffusion policy pretraining — public dataset

Baselines vs proposed

• Outcome-only reward: Final success rate ~40-60% on LIBERO tasks vs SVM ~80% after 2×10^5 timesteps (Fig 3,7).
• SORS: slower convergence and lower success rates compared to SVM (Fig 3,4).
• SASR: underperforms SVM in both sample efficiency and final performance (Fig 3,4).
• GAIL-Reward (fixed demonstrator): learns slower and achieves lower final success than SVM with online updates (Fig 3).
• RND intrinsic reward: failed to improve beyond outcome-only baseline (Fig 3).
• GVL (vision-language model reward): lower success rate and slower than SVM, limited by compute budget (Fig 3).
• SVM achieves ~2× fewer environment steps to reach 90% success compared to outcome reward alone on RL finetuning tasks.
• On Robocasa, only SVM enabled learning with ~90% success, baseline methods did not improve (Fig 4).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.23640.

Fig 1: (a) Given trajectories labeled with sparse outcome reward rout, we train a discriminator to

Fig 2: Robomimic,

Fig 3: Aggregated results of RL finetun-

Fig 4: Aggregated results of RL finetuning with

Fig 6: RL finetuning with DSRL and SVM

Fig 7: RL finetun-

Fig 8: RL from demonstra-

Fig 9: Visualization of real-world tasks on

Limitations

• Theoretical guarantees require deterministic transitions and countable state-action spaces; though empirically effective, stochasticity could degrade performance.
• Discriminator training quality depends heavily on having representative success and failure trajectories; sparse successes early on may limit reward accuracy.
• The approach assumes episodic tasks with clear binary success labels, may be less applicable to more complex or continuous reward structures.
• No adversarial robustness analysis was performed; a manipulative agent might exploit discriminator weaknesses or mislabeled episodes.
• Scaling to very high-dimensional observation spaces might require high-capacity classifiers and extensive data, increasing training cost.
• Evaluation focused mainly on robotic manipulation; generalization to other RL domains with sparse rewards remains to be studied.

Open questions / follow-ons

• How does SVM perform in highly stochastic or partially observable environments where visitation estimates are noisier?
• Can the approach be extended to multi-goal or continuous success metrics rather than binary outcome rewards?
• What are the theoretical or empirical trade-offs between discriminator capacity, classifier calibration, and final policy performance?
• How does updating the discriminator online versus fixing it affect long-term policy stability and robustness?

Why it matters for bot defense

Bot-defense and CAPTCHA systems often face challenges of sparse or binary feedback signals indicating success (e.g., solved CAPTCHA or not). This research introduces a theoretically sound and practical method to turn such sparse outcome signals into dense, informative rewards by encouraging matching the visitation distributions of states/actions associated with prior successful completions. Applying a similar success visitation matching approach could help CAPTCHA solvers or anomaly detectors learn more efficiently and robustly from limited success signals, improving adaptation speed and stability.

Moreover, the discriminator-based estimation of visitation ratios aligns with adversarial or classification-based approaches common in bot-detection pipelines. The method’s provable policy optimality preservation and demonstrated empirical sample efficiency gains offer promising techniques to improve reinforcement learning components of bot-defense mechanisms that typically struggle with sparse feedback. However, practical adaptation in security settings would require attention to possible adversarial manipulations and stochasticities inherent in user behavior.

Cite

@article{arxiv2606_23640,
  title={ Learning Process Rewards via Success Visitation Matching for Efficient RL },
  author={ Raymond Tsao and Andrew Wagenmaker and Sergey Levine },
  journal={arXiv preprint arXiv:2606.23640},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.23640}
}

Read the full paper

• arXiv:2606.23640 (abstract)
• arXiv:2606.23640 (PDF)