Floyd-Warshall Reinforcement Learning Learning from Past Experiences to Reach New Goals

Vikas Dhiman, Shurjo Banerjee, Jeffrey Mark Siskind, Jason J. CorsoarXiv 2018 · arXiv

Introduction

In the field of robotics and autonomous navigation, agents often operate in static environments where the physical layout remains constant while specific objectives change frequently. For instance, a domestic robot may need to find keys one moment and a remote control the next within the same house. Traditional Reinforcement Learning (RL) approaches often struggle with this goal-conditioned flexibility. Model-free methods like Q-learning typically treat each new goal as a novel problem, necessitating extensive re-exploration. Conversely, model-based RL attempts to learn environment dynamics but is prone to compounding errors that degrade long-term planning.

Floyd-Warshall Reinforcement Learning (FWRL) proposes a middle ground. By adapting the classic Floyd-Warshall "all-pairs shortest path" algorithm to RL, it enables agents to "stitch together" past trajectories to find optimal paths to new goals with high sample efficiency.

Methodology: The Floyd-Warshall Function

The core innovation of FWRL is the Floyd-Warshall (FW) function, denoted as $F(s' | s, a)$. This function represents the expected cumulative reward of starting at state $s$, executing action $a$, and eventually reaching a target goal state $s'$.

To ensure the agent learns the global structure of the environment rather than just specific goal-oriented paths, the authors enforce a triangle-inequality constraint during training: $$F^*(s_j | s_i, a_i) \geq F^*(s_k | s_i, a_i) + \max_{a_k} F^*(s_j | s_k, a_k)$$

Conceptual diagram of trajectory stitching in FWRL. By visiting an intermediate state $s_i$, the agent can infer paths between previously unconnected start and goal states.

This constraint dictates that the value of an optimal path from $s_i$ to $s_j$ must be at least as high as the value of a path that passes through an intermediate state $s_k$. By optimizing for this property, the agent learns the relationships between all visited state pairs. If an agent has traveled from $s_1$ to $s_i$ in one instance and from $s_i$ to $g_1$ in another, it can immediately synthesize a path from $s_1$ to $g_1$ without further exploration.

Experimental Setup

The effectiveness of FWRL was evaluated in two simulated tabular grid-world environments:

  1. Four-room grid world: A standard benchmark featuring rooms connected by narrow doorways, which serves as a test for navigating bottlenecks.
  2. Windy four-room grid world: An extension that introduces stochasticity via "wind" effects, testing the algorithm's robustness to complex dynamics.

These environments allow for a clear comparison of how different algorithms handle spatial reachability and transitivity.

Results and Analysis

FWRL demonstrated superior performance across multiple metrics compared to baselines such as standard Q-learning (QL), Q-learning with goal concatenation (QLCAT), and Model-Based RL (MBRL).

Performance comparison across different RL algorithms. FWRL demonstrates significantly lower distance inefficiency and higher rewards per episode compared to baselines.

Sample Efficiency and Reward

In both standard and windy grid worlds, FWRL's learning curves showed significantly faster convergence. The agent achieved peak performance in a fraction of the episodes required by standard Q-learning. Quantitatively, FWRL reached approximately twice the median reward of the next best baseline.

Zero-Shot Pathfinding

Qualitative analysis in an "H-Maze" configuration highlighted FWRL's unique capabilities. After observing two distinct trajectories that intersected at a central point, the FWRL agent could immediately identify the shortest path for a start-goal pair it had never explicitly practiced. In contrast, standard Q-learning agents often failed, becoming stuck against obstacles because they lacked the "stitching" logic inherent in the FW function.

Discussion and Future Work

While FWRL offers a powerful framework for goal-conditioned RL, it currently faces limitations related to scalability. The tabular nature of the current implementation involves an $O(|S|^3)$ complexity, which is computationally prohibitive for high-dimensional or continuous state spaces. Additionally, the method assumes a static environment layout; dynamic changes to the environment could invalidate the learned "stitching" logic.

Future research will focus on integrating triangle-inequality constraints into Deep RL architectures. By using neural networks as function approximators, the principles of FWRL could potentially be scaled to complex, real-world robotic tasks where state spaces are vast and continuous.

Summary updated

Abstract

Consider mutli-goal tasks that involve static environments and dynamic goals. Examples of such tasks, such as goal-directed navigation and pick-and-place in robotics, abound. Two types of Reinforcement Learning (RL) algorithms are used for such tasks: model-free or model-based. Each of these approaches has limitations. Model-free RL struggles to transfer learned information when the goal location changes, but achieves high asymptotic accuracy in single goal tasks. Model-based RL can transfer learned information to new goal locations by retaining the explicitly learned state-dynamics, but is limited by the fact that small errors in modelling these dynamics accumulate over long-term planning. In this work, we improve upon the limitations of model-free RL in multi-goal domains. We do this by adapting the Floyd-Warshall algorithm for RL and call the adaptation Floyd-Warshall RL (FWRL). The proposed algorithm learns a goal-conditioned action-value function by constraining the value of the optimal path between any two states to be greater than or equal to the value of paths via intermediary states. Experimentally, we show that FWRL is more sample-efficient and learns higher reward strategies in multi-goal tasks as compared to Q-learning, model-based RL and other relevant baselines in a tabular domain.
BibTeX
@misc{dhiman2018floyd,
  author = {Vikas Dhiman and Shurjo Banerjee and Jeffrey Mark Siskind and Jason J. Corso},
  title = {{Floyd-Warshall Reinforcement Learning Learning from Past Experiences to Reach New Goals}},
  year = {2018},
  eprint = {1809.09318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.09318},
}
Figure