Abstract
Sample collection is a critical bottleneck in reinforcement learning (RL), particularly in real-world domains like robotics and healthcare where environment interaction is costly. We propose a confidence-based sampling strategy derived from the Optimal Computing Budget Allocation (OCBA) algorithm. By utilizing ensembles to estimate predictive uncertainty, our method intelligently allocates exploration effort toward actions that maximize the probability of identifying the optimal policy. This strategy is integrated into Q-learning, DQN, and SAC, demonstrating significant improvements in sample efficiency and stability across various benchmarks, including synthetic MDPs and MuJoCo continuous control tasks.
Introduction
The "Achilles' heel" of modern reinforcement learning is its low sample efficiency. While agents can achieve superhuman performance in simulation, the requirement for millions of interactions makes deployment in physical systems—such as autonomous vehicles or medical diagnostics—prohibitively expensive. Traditional exploration strategies like $\epsilon$-greedy or Upper Confidence Bound (UCB) often fail to account for the model's own predictive uncertainty, leading to "extravagantly expensive" sampling of sub-optimal or already well-understood actions.
This work bridges the gap between simulation-based optimization and sequential decision-making by adapting the OCBA algorithm for RL. By focusing on the most promising actions rather than exploring all high-potential options optimistically, we significantly reduce the total interactions required to reach peak performance.
The OCBA-Based Sampling Strategy
Our approach introduces a plug-and-play sampling layer for off-policy RL algorithms, consisting of three core pillars:
- Ensemble-based Uncertainty Estimation: The agent maintains an ensemble of $M$ independent models (typically $M=5$). The variance in their predictions provides a robust proxy for epistemic uncertainty without the computational overhead of complex Bayesian neural networks.
- OCBA Allocation: We adapt the "Ranking and Selection" (R&S) framework to RL. The goal is to maximize the Probability of Correct Selection (PCS)—the likelihood that the chosen action is truly the best. Unlike UCB, which is purely optimistic, OCBA focuses on the gap between the best-estimated action and its competitors.
- Confidence-Triggered Exploration: We calculate an Approximate PCS (APCS). If confidence is high, the agent exploits; if low, it samples actions according to an OCBA-derived distribution designed to improve certainty where it matters most.
Experimental Evaluation
We evaluated the OCBA-integrated algorithms across a spectrum of environments, from synthetic tabular MDPs to high-dimensional continuous control tasks in MuJoCo.
Key Results and Insights
- Faster Convergence: In tabular settings, OCBA-Q-learning reaches optimal performance significantly faster than UCB or vanilla Q-learning. As shown in the figures below, the performance gap is maintained across varying state ($|\mathcal{S}|$) and action ($|\mathcal{A}|$) space sizes.
- Superior Performance in Continuous Control: In the MuJoCo HalfCheetah task, OCBA-SAC achieved a score of 8115.8, nearly doubling the performance of the state-of-the-art ensemble baseline, SUNRISE (4403.7).
- Enhanced Stability: The OCBA-based methods exhibit much lower variance during training. This stability suggests that the agent is less prone to "unlearning" or diverging, a common issue in deep RL.
Discussion and Future Work
By focusing exploration on the most informative actions, OCBA creates a "virtuous cycle": higher-quality data leads to a better policy, which further refines the efficiency of future data collection. While the ensemble approach adds a per-step computational cost, the massive reduction in required environment interactions makes it a net gain for real-world applications.
Future research will focus on extending this framework to on-policy algorithms (like PPO) and addressing the unique challenges of predictive uncertainty in decentralized multi-agent systems.
Summary updated