ELDEN: Exploration via Local Dependencies

Zizhao Wang, Jiaheng Hu, Peter Stone, Roberto Martín-Martín

Abstract

Reinforcement learning (RL) in environments with sparse rewards remains a significant challenge. While intrinsic motivation methods like curiosity and empowerment have been proposed, they often struggle with environmental noise or indirect causal chains. We introduce ELDEN (Exploration via Local DepENdencies), a novel exploration method that incentivizes agents to discover interactions between entities. ELDEN utilizes partial derivatives of a learned dynamics model to track local dependencies and rewards the agent based on the uncertainty of these dependencies within an ensemble. Our results across four complex domains—including 2D grid worlds and 3D robotic simulations—show that ELDEN effectively solves long-horizon tasks where traditional methods fail.

Introduction

Reinforcement learning struggles in environments where the agent only receives a reward signal at the end of a long sequence of actions. To address this, researchers employ intrinsic rewards to encourage exploration. However, existing methods have notable limitations. Curiosity-based methods, which reward high prediction error, are often distracted by "noisy TVs"—complex but irrelevant physics. Empowerment-based methods, which reward maximal control, focus on direct influence and may ignore critical indirect interactions, such as a stove heating a pot the agent is not touching.

ELDEN addresses these gaps in environments with factored state spaces and chained dependencies. It shifts the focus from predicting how entities move to discovering whether they interact.

Methodology

ELDEN models the environment as a local causal graph where edges represent dependencies between entities.

Comparison of exploration strategies: Curiosity (prediction error), Empowerment (direct influence), and ELDEN (local dependencies).

The core technical innovation lies in using partial derivatives of a learned dynamics model: $| \frac{\partial \hat{p}(s^j_{t+1})}{\partial s^i_t} |$. A high derivative indicates that a change in entity $i$ at time $t$ significantly impacts entity $j$ at $t+1$, signaling a dependency. ELDEN trains an ensemble of these models and uses the variance of predicted dependencies as an intrinsic reward, encouraging the agent to explore states with uncertain interactions. To ensure focus on meaningful interactions, a sparsity regularization term is included to suppress false positives.

Experimental Setup

We evaluated ELDEN on four diverse environments with complex chained dependencies:

  1. Thawing (Mini-behavior): A 2D grid world task involving a fridge, fish, and sink.
  2. CarWash (Mini-behavior): A long-horizon task with multiple objects (rag, soap, car).
  3. Minecraft 2D: A tech-tree environment requiring specific crafting sequences.
  4. Kitchen (Robosuite): A 3D continuous simulation requiring multi-step cooking tasks.
The Kitchen environment in Robosuite, featuring complex entity interactions like a stove switch, stove, pot, and meatball.

Results and Discussion

ELDEN significantly outperformed state-of-the-art baselines across almost all domains. In the CarWash, Minecraft 2D, and Kitchen environments, ELDEN was frequently the only method to successfully complete the tasks. Beyond task success, ELDEN achieved superior ROC-AUC scores in identifying ground-truth dependencies compared to attention-based models.

The primary insight is that identifying interaction modes is a more robust exploration signal than perfect trajectory prediction. However, ELDEN may be less effective in tasks requiring extreme precision over interaction discovery. Future work will explore learning low-level motor skills and dependencies simultaneously.

Summary updated

Abstract

Tasks with large state space and sparse rewards present a longstanding challenge to reinforcement learning. In these tasks, an agent needs to explore the state space efficiently until it finds a reward. To deal with this problem, the community has proposed to augment the reward function with intrinsic reward, a bonus signal that encourages the agent to visit interesting states. In this work, we propose a new way of defining interesting states for environments with factored state spaces and complex chained dependencies, where an agent's actions may change the value of one entity that, in order, may affect the value of another entity. Our insight is that, in these environments, interesting states for exploration are states where the agent is uncertain whether (as opposed to how) entities such as the agent or objects have some influence on each other. We present ELDEN, Exploration via Local DepENdencies, a novel intrinsic reward that encourages the discovery of new interactions between entities. ELDEN utilizes a novel scheme --- the partial derivative of the learned dynamics to model the local dependencies between entities accurately and computationally efficiently. The uncertainty of the predicted dependencies is then used as an intrinsic reward to encourage exploration toward new interactions. We evaluate the performance of ELDEN on four different domains with complex dependencies, ranging from 2D grid worlds to 3D robotic tasks. In all domains, ELDEN correctly identifies local dependencies and learns successful policies, significantly outperforming previous state-of-the-art exploration methods.
BibTeX
@inproceedings{wang2023elden,
  author = {Zizhao Wang and Jiaheng Hu and Peter Stone and Roberto Martín-Martín},
  title = {{ELDEN: Exploration via Local Dependencies}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=sL4pJBXkxu},
}
Figure