# Improving Policy Gradient by Exploring Under-appreciated Rewards

arXiv: https://arxiv.org/abs/1611.09321 · HTML: https://mlsanity.com/paper/1611.09321/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2016.

## Built on by (most cited first, 14 of 14)

- [Motif: Intrinsic Motivation from Artificial Intelligence Feedback](https://mlsanity.com/paper/2310.00166/) (2023)
- [Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification](https://mlsanity.com/paper/2111.11188/) (2021)
- [Cal-DPO: Calibrated Direct Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2412.14516/) (2024)
- [Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences](https://mlsanity.com/paper/2107.08285/) (2021)
- [Co-Adaptation of Algorithmic and Implementational Innovations in Inference-based Deep Reinforcement Learning](https://mlsanity.com/paper/2103.17258/) (2021)
- [OPIRL: Sample Efficient Off-Policy Inverse Reinforcement Learning via Distribution Matching](https://mlsanity.com/paper/2109.04307/) (2021)
- [How to Leverage Demonstration Data in Alignment for Large Language Model? A Self-Imitation Learning Perspective](https://mlsanity.com/paper/2410.10093/) (2024)
- [On a Connection Between Imitation Learning and RLHF](https://mlsanity.com/paper/2503.05079/) (2025)
- [How to Train Your Deep Research Agent? Prompt, Reward, and Policy Optimization in Search-R1](https://mlsanity.com/paper/2602.19526/) (2026)
- [End-to-End Neuro-Symbolic Architecture for Image-to-Image Reasoning Tasks](https://mlsanity.com/paper/2106.03121/) (2021)
- [Policy Gradient Algorithms Implicitly Optimize by Continuation](https://mlsanity.com/paper/2305.06851/) (2023)
- [Bayesian Distributional Policy Gradients](https://mlsanity.com/paper/2103.11265/) (2021)
- [Bidirectional Soft Actor-Critic: Leveraging Forward and Reverse KL Divergence for Efficient Reinforcement Learning](https://mlsanity.com/paper/2506.01639/) (2025)
- [Network Calculus with Flow Prolongation -- A Feedforward FIFO Analysis enabled by ML](https://mlsanity.com/paper/2202.03004/) (2022)

## Abstract (arXiv)

This paper presents a novel form of policy gradient for model-free reinforcement learning (RL) with improved exploration properties. Current policy-based methods use entropy regularization to encourage undirected exploration of the reward landscape, which is ineffective in high dimensional spaces with sparse rewards. We propose a more directed exploration strategy that promotes exploration of under-appreciated reward regions. An action sequence is considered under-appreciated if its log-probability under the current policy under-estimates its resulting reward. The proposed exploration strategy is easy to implement, requiring small modifications to an implementation of the REINFORCE algorithm. We evaluate the approach on a set of algorithmic tasks that have long challenged RL methods. Our approach reduces hyper-parameter sensitivity and demonstrates significant improvements over baseline methods. Our algorithm successfully solves a benchmark multi-digit addition task and generalizes to long sequences. This is, to our knowledge, the first time that a pure RL method has solved addition using only reward feedback.