Learning to Generalize from Sparse and Underspecified Rewards

Rishabh Agarwal, Chen Liang, Dale Schuurmans, Mohammad Norouzi

Abstract

We consider the problem of learning from sparse and underspecified rewards, where an agent receives a complex input, such as a natural language instruction, and needs to generate a complex response, such as an action sequence, while only receiving binary success-failure feedback. Such success-failure rewards are often underspecified: they do not distinguish between purposeful and accidental success. Generalization from underspecified rewards hinges on discounting spurious trajectories that attain accidental success, while learning from sparse feedback requires effective exploration. We address exploration by using a mode covering direction of KL divergence to collect a diverse set of successful trajectories, followed by a mode seeking KL divergence to train a robust policy. We propose Meta Reward Learning (MeRL) to construct an auxiliary reward function that provides more refined feedback for learning. The parameters of the auxiliary reward function are optimized with respect to the validation performance of a trained policy. The MeRL approach outperforms our alternative reward learning technique based on Bayesian Optimization, and achieves the state-of-the-art on weakly-supervised semantic parsing. It improves previous work by 1.2% and 2.4% on WikiTableQuestions and WikiSQL datasets respectively.

The Challenge: Sparse and Underspecified Rewards

In many real-world AI tasks, such as semantic parsing (translating natural language into SQL queries), agents often operate under binary feedback: a 1 for success and a 0 for failure. While simple to implement, this reward structure presents two significant challenges:

  1. Sparse Rewards: In vast action spaces, finding any sequence that yields a reward is extremely difficult—a "needle in a haystack" problem.
  2. Underspecified Rewards: Binary rewards often fail to distinguish between "purposeful" success and "accidental" success. For instance, an agent might generate a query that happens to return the correct answer from a table for the wrong reasons (a "spurious" trajectory). Learning from these accidental successes prevents the agent from generalizing to new, unseen data.
An illustration of underspecified rewards in a maze task where multiple trajectories (a1, a2, a3) result in the same binary success reward despite varying in efficiency and correctness relative to the instruction.

Methodology: MAPOX and MeRL

To address these hurdles, the authors propose a two-pronged approach focusing on diverse exploration and refined reward signals.

Mode-Covering Exploration (MAPOX)

Standard Reinforcement Learning (RL) objectives are typically "mode-seeking," meaning they converge on a single optimal path. However, for effective exploration in sparse environments, a "mode-covering" strategy is required to discover all possible successful paths. The authors utilize Iterative Maximum Likelihood (IML) to populate a memory buffer with a diverse set of successful trajectories. Once a diverse buffer is established, the system switches to Maximum Across Polar Outcomes (MAPO), a more robust policy optimization method, to refine the agent's behavior.

Meta Reward Learning (MeRL)

Since binary rewards are insufficient for distinguishing quality, the authors introduce an auxiliary reward function. The core innovation is Meta Reward Learning (MeRL), which uses a gradient-based meta-learning loop.

The MeRL framework combines mode-covering exploration to find successful trajectories with a meta-learning loop that optimizes auxiliary rewards based on validation performance.

In this framework, the agent is trained on the training set using an auxiliary reward. The parameters of this reward function are then optimized based on the policy's performance on a separate validation set. The intuition is that generalization serves as a proxy for reward quality: if a reward encourages trajectories that help the agent perform well on unseen data, it is likely a "correct" reward rather than one that encourages "reward hacking."

Experimental Results

The MeRL approach was evaluated on three distinct benchmarks:

  • WikiTableQuestions: A complex dataset requiring multi-step reasoning over Wikipedia tables. MeRL achieved 44.1% accuracy, a 1.2% improvement over the previous state-of-the-art.
  • WikiSQL: A large-scale dataset for mapping questions to SQL. MeRL reached 74.8% accuracy under weak supervision, a 2.4% improvement.
  • Instruction Following Maze: A synthetic task used to test the handling of spurious paths. MeRL significantly closed the gap between agents trained on underspecified rewards and those trained with an "Oracle" (perfect) reward.

Conclusion

The research demonstrates that generalization performance on a validation set can be effectively used to refine reward signals in sparse environments. Key insights include the effectiveness of IML for initial discovery and the utility of trajectory features (like program length or entity matches) in identifying non-spurious paths. Future work may involve moving beyond linear reward models to more complex neural network-based rewards and exploring non-terminal rewards that provide feedback throughout an action sequence.

Summary updated

Abstract

We consider the problem of learning from sparse and underspecified rewards, where an agent receives a complex input, such as a natural language instruction, and needs to generate a complex response, such as an action sequence, while only receiving binary success-failure feedback. Such success-failure rewards are often underspecified: they do not distinguish between purposeful and accidental success. Generalization from underspecified rewards hinges on discounting spurious trajectories that attain accidental success, while learning from sparse feedback requires effective exploration. We address exploration by using a mode covering direction of KL divergence to collect a diverse set of successful trajectories, followed by a mode seeking KL divergence to train a robust policy. We propose Meta Reward Learning (MeRL) to construct an auxiliary reward function that provides more refined feedback for learning. The parameters of the auxiliary reward function are optimized with respect to the validation performance of a trained policy. The MeRL approach outperforms our alternative reward learning technique based on Bayesian Optimization, and achieves the state-of-the-art on weakly-supervised semantic parsing. It improves previous work by 1.2% and 2.4% on WikiTableQuestions and WikiSQL datasets respectively.
BibTeX
@inproceedings{agarwal2019learning,
  author = {Rishabh Agarwal and Chen Liang and Dale Schuurmans and Mohammad Norouzi},
  title = {{Learning to Generalize from Sparse and Underspecified Rewards}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=ryEzYjZO-S},
}
Figure