What Reward Structure Enables Efficient Sparse-Reward RL? A Proof-of-Concept with Policy-Aware Matrix Completion

Sparse-reward reinforcement learning typically focuses on exploration, but we ask: can structural assumptions about reward functions themselves accelerate learning? We introduce Policy-Aware Matrix Completion (PAMC), which exploits low-rank structure in reward matrices while correcting for policy-induced sampling bias. PAMC combines three key components: a low-rank plus sparse reward model, inverse propensity weighting to handle Missing-Not-At-Random (MNAR) data, and confidence-gated abstention that falls back to intrinsic exploration when uncertain. We provide finite-sample theory showing that completion error scales as $O(\sigma\sqrt{r(|\mathcal{S}|+|\mathcal{A}|)/\text{ESS}})$ where ESS is the effective sample size under policy overlap $\kappa$. PAMC achieves strong empirical results at 10M steps (a sample-efficiency comparison): 4100$\pm$250 return vs. 200$\pm$50 for DrQ-v2 on Montezuma's Revenge, 78\% vs. 65\% success rate on MetaWorld-50, and 15\% improvement over CQL on D4RL datasets. The method maintains 8\% computational overhead while providing calibrated confidence intervals (95\% empirical coverage). When structural assumptions are violated, PAMC gracefully degrades through increased abstention rather than catastrophic failure. Our approach demonstrates that reward structure exploitation can complement traditional exploration methods in sparse-reward domains.

When an AI agent learns by trial and error, it usually needs frequent feedback to figure out which actions are good. But in many realistic settings, like a game where you only score points after finding a hidden key, or a robot that only succeeds after a long sequence of correct moves, feedback is extremely rare. Most existing methods try to solve this by pushing the agent to explore more, but they treat the underlying rewards as a complete mystery, ignoring the fact that rewards usually have hidden patterns. For example, in a classic exploration game, keys unlock doors in predictable ways across many rooms. We built a method called Policy Aware Matrix Completion that views the table of possible rewards like a partially filled spreadsheet and predicts the blanks by exploiting these hidden patterns. It also corrects for the fact that the agent tends to revisit the same places, which biases what it sees, and it refuses to use its guesses whenever it is not confident enough, falling back to ordinary exploration. Across a wide range of tasks, our approach learns dramatically faster than strong baselines, including a roughly twenty fold improvement on a notoriously hard exploration game, while adding only about eight percent extra computation. Just as importantly, when the hidden patterns are not really there, the method automatically recognizes this and steps aside rather than confidently making things worse, which matters in safety sensitive settings.