Self-Punishment and Reward Backfill for Deep Q-Learning

Mohammad Reza Bonyadi, Rui Wang, Maryam ZiaeiIEEE TNNLS 2020 · DOI

Abstract

Reinforcement Learning (RL) agents often struggle with the "credit assignment problem"—the difficulty of determining which specific action in a long sequence led to a final reward or failure. This paper proposes two simple yet powerful strategies inspired by behavioral psychology to bridge this gap: Self-Punishment (SP) and Reward Backfill (RB). These bio-inspired reward shaping strategies tackle the credit assignment problem in Deep Q-Learning by providing intrinsic signals for failures and "bridging" rewards back to previous actions. Evaluated on 30 Atari games, these methods improved performance in over 65% of environments, with some seeing gains of over 25x.

Introduction: The Credit Assignment Problem

In many RL environments, rewards are "sparse." An agent might take hundreds of actions before receiving a single point or losing a life. Standard algorithms like Deep Q-Networks (DQN) often struggle because they primarily learn from immediate feedback. If an agent loses a life but the environment provides a reward of zero, the agent cannot easily distinguish that "bad" terminal state from a "neutral" state where it just hasn't scored yet. This ambiguity slows down learning significantly. While increasing the "look-ahead" ($n$-step TD updates) can help, it is computationally expensive and difficult to implement in deep learning architectures.

Proposed Bio-Inspired Methods

The authors propose two lightweight strategies that can be integrated into any value-based RL algorithm:

  1. Self-Punishment (SP): Inspired by operant conditioning, this strategy forces the agent to "punish" itself. If an action leads to a terminal state (like losing a life) and the environment doesn't provide a negative reward, the agent intrinsically subtracts a constant value $p$ from its reward. This makes the distinction between "neutral" and "undesirable" states clear.
  2. Reward Backfill (RB): Inspired by "clicker training" used in animal behavior modification, this strategy backpropagates a fraction of a non-zero reward to the preceding zero-reward actions. It uses a decay function ($f(i) = \lambda^i$) so that actions closer to the reward get more "credit" than those further back.

The authors mathematically prove that both strategies are Policy Independent Reshaping Functions (PIRF). This ensures that adding these intrinsic rewards does not change the optimal solution of the game; it simply accelerates the agent's path to finding it.

Key Insights: The Role of Sparsity

A critical finding of the research is the relationship between reward frequency and the effectiveness of Reward Backfill. The authors define "sparsity length" as the number of frames between non-zero rewards.

Mean sparsity length across 30 Atari environments, highlighting the threshold where Reward Backfill becomes most effective.

As shown in the figure above, environments vary significantly in their reward density. The researchers found that RB is most effective when the sparsity length is at least 25 frames. In games with very frequent rewards (low sparsity), RB can introduce noise that may hinder learning.

Performance Evaluation

The researchers evaluated their methods on 30 Atari 2600 games, comparing them against standard baselines like Double DQN (D2QN) and Dueling Double DQN (D3QN).

Logarithmic improvement of the proposed methods over standard DQN/D3QN baselines and other reward-shaping techniques across the Atari suite.

The results demonstrate broad success:

  • Broad Success: The proposed strategies improved performance in over 65% of the tested games.
  • Massive Gains: In some environments, the improvement was staggering—up to 2,800% (28x) compared to the baseline.
  • Computational Efficiency: Unlike other methods for solving credit assignment (like prioritized replay or curiosity-driven exploration), RB and SP are $O(1)$ operations, requiring negligible extra CPU/GPU power.

Limitations and Future Work

While highly effective, these strategies are not universal. In games with very complex terminal states or extremely frequent rewards, performance occasionally dropped. Furthermore, the current implementation uses static parameters for $p$ and $\lambda$. Future research could explore adaptive strategies where the agent tunes its own punishment and backfill levels based on the real-time sparsity length of the environment. Combining these methods with other exploration techniques, such as Noisy DQN, also remains a promising direction.

Summary updated

BibTeX
@article{bonyadi2020self,
  author = {Mohammad Reza Bonyadi and Rui Wang and Maryam Ziaei},
  title = {{Self-Punishment and Reward Backfill for Deep Q-Learning}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2020},
  doi = {10.1109/tnnls.2021.3140042},
}
Figure