Pairwise Weights for Temporal Credit Assignment

Zeyu Zheng, Risto Vuorio, Richard L. Lewis, Satinder Singh

Introduction

Temporal Credit Assignment (TCA) is a fundamental challenge in Reinforcement Learning (RL), involving the identification of which past actions are responsible for current rewards. Traditional methods like TD($\lambda$) rely on a recency heuristic, where credit decays exponentially over time. While effective for short-term dependencies, this approach fails in environments with long delays or intervening "noisy" rewards that are irrelevant to the primary goal. This paper proposes a novel framework that replaces fixed temporal decay with learned pairwise weight functions.

Methodology: Pairwise Weighted Advantage Estimators

The authors introduce two new advantage estimators that generalize standard RL approaches:

  1. Meta-PWTD (Pairwise Weighted TD-error): A generalization of the TD($\lambda$) approach.
  2. Meta-PWR (Pairwise Weighted Reward): A generalization of the Monte-Carlo approach.

The core innovation is the pairwise weight function $f_\eta(S_t, S_k, k-t)$, which determines the credit assigned between an action at time $t$ and a signal (reward or TD-error) at time $k$. Unlike $\lambda$, which only considers the time interval $k-t$, this function is conditioned on the specific states $S_t$ and $S_k$.

To optimize these weights, a metagradient approach is employed. An inner loop trains the agent's policy using the current weights, while an outer loop updates the weight parameters $\eta$ based on the agent's overall performance. This allows the system to discover optimal credit assignment strategies autonomously.

Experimental Evaluation

The proposed methods were tested across several benchmarks:

  • Key-to-Door (KtD): A task requiring the agent to pick up a key, navigate a distraction phase (collecting apples), and finally open a door for a reward.
  • bsuite: A set of diagnostic tasks for RL agents.
  • Atari 2600: Testing scalability on 49 high-dimensional games.

Key Results and Discussion

The learned pairwise weights demonstrated a remarkable ability to "teleport" credit across long sequences of irrelevant states. In the Key-to-Door environment, the metagradient successfully learned to ignore the "apple" rewards and link the initial key-pickup action directly to the final door reward.

Key-to-Door environment and learned pairwise weight matrices showing credit 'teleportation' from key to door.

As shown in the performance analysis, Meta-PWTD and Meta-PWR scale significantly better than fixed $\lambda$ baselines as the depth (delay) of the task increases. In the DAG environments, the proposed methods required fewer episodes to reach a 95% score compared to the standard TD(1.0) approach.

Performance comparison showing that Meta-PWTD and Meta-PWR maintain efficiency as task depth increases.

On the Atari benchmark, Meta-PWTD outperformed the A2C baseline in 30 out of 49 games. This suggests that adaptive credit assignment is beneficial even in general environments where long-term dependencies might not be the primary bottleneck.

Conclusion

By moving from fixed temporal decay to state-aware pairwise weights, this work provides a more flexible and powerful mechanism for credit assignment. While the metagradient approach introduces additional computational overhead, the resulting gains in sample efficiency and the ability to solve long-horizon tasks represent a significant step forward for RL agents operating in complex, noisy environments.

Summary updated

BibTeX
@inproceedings{zheng2022pairwise,
  author = {Zeyu Zheng and Risto Vuorio and Richard L. Lewis and Satinder Singh},
  title = {{Pairwise Weights for Temporal Credit Assignment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i8.20909},
}
Figure