Elden: Exploration via Local Dependencies

Zizhao Wang*

Jiaheng Hu*

Roberto Martin-Martin*

Peter Stone

* External authors

NeurIPS 2023

2023

Abstract

Tasks with large state space and sparse reward present a longstanding challenge to reinforcement learning. In these tasks, an agent needs to explore the state space efficiently until it finds reward: the hard exploration problem. 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 state of one factor that, in order, may affect the state of another factor. This is natural in human environments such as homes where the agent's actions can change the state of one object/factor (switch on/off a stove), which influences the state of another object/factor (heat a pan above the stove). 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. Then the uncertainty of the predicted dependencies is used as an intrinsic reward to encourage exploration toward new interactions. We evaluate the performance of ELDEN on three different domains with complex dependencies, ranging from 2D grid worlds to 3D robotic tasks. In all domains, ELDEN is able to correctly recover local dependencies and learn successful policies, significantly outperforming previous state-of-the-art exploration methods.