TL;DR
This paper introduces a formal method to define "useful skills" for AI agents using betweenness centrality—a graph theory measure that identifies "bottleneck" states. By targeting states that lie on many shortest paths between other regions, agents can autonomously discover high-level behaviors (like moving through a doorway or setting up a fork in Tic-Tac-Toe) that dramatically accelerate learning in complex environments.
The Challenge of Skill Discovery
In Reinforcement Learning (RL), agents often start with only "primitive" actions, such as "move north" or "turn left." To solve complex, multi-step problems efficiently, they need to develop "skills" or "subgoals"—high-level behaviors like "pick up the keys" or "navigate to the kitchen."
The core challenge is: How does an agent autonomously determine which subgoals are worth learning?
While researchers have long relied on the "bottleneck" intuition—the idea that states connecting different areas (like a doorway between rooms) make excellent subgoals—defining this formally across diverse tasks has been difficult. Previous methods often relied on task-specific heuristics or required the agent to have already solved the task multiple times. This paper seeks a domain-independent, structural characterization of what makes a skill broadly useful.
Defining Skills with Betweenness Centrality
The authors represent an agent's environment as an interaction graph, where vertices are states and edges are possible transitions. They then apply betweenness centrality to this graph to identify subgoals.
- Betweenness Centrality: This measure calculates the fraction of all shortest paths in a graph that pass through a specific vertex. A state with high betweenness acts as a "pivotal" point for navigation.
- Subgoal Definition: The authors define subgoals as local maxima of betweenness. Instead of searching for the single most central state in the entire world, they look for states that are more central than their immediate neighbors.
- Incremental Discovery: Calculating betweenness for a massive global graph is computationally expensive ($O(nm)$ for unweighted graphs). To solve this, the authors propose an incremental algorithm. The agent builds small subgraphs from short, local trajectories and identifies local maxima within those samples. If a state consistently appears as a local maximum across many subgraphs, it is promoted to a formal subgoal.
Key Insights
- Beyond Physical Navigation: Betweenness isn't limited to physical maps. In Tic-Tac-Toe, the state with the highest betweenness corresponds to "setting up a fork"—a strategic move that creates two simultaneous ways to win. This demonstrates that the measure captures strategic bottlenecks, not just spatial ones.
- The Power of Local Maxima: You don't need to find the "most important" state in the entire environment; you only need the state that connects its immediate neighborhood to the rest of the world. This makes the search for subgoals computationally tractable.
- Betweenness vs. Graph Partitioning: Many existing algorithms attempt to "cluster" the graph and find edges between clusters. The authors argue that betweenness is a more fundamental metric; it identifies "bridges" even in graphs where clear clusters don't exist (such as the game tree of Tic-Tac-Toe).
- Reward Integration: By weighting paths based on the reward function, betweenness can be tuned to find subgoals that are specifically useful for a given task, rather than just general exploration.
Experimental Results
The authors evaluated their approach across several RL benchmarks, including Gridworlds (Rooms & Shortcut), the Taxi Domain, Playroom, and Tic-Tac-Toe.
- Faster Learning: In the Rooms, Shortcut, and Playroom domains, agents using betweenness-based skills reached their goals significantly faster than agents using only primitive actions or randomly selected subgoals.
- Intuitive Discovery: In the Taxi domain, the algorithm automatically identified "picking up the passenger" and "navigational bottlenecks" as the top subgoals—perfectly matching the hand-coded skills human engineers typically design for this task.
- Feasibility of Incremental Search: The incremental algorithm successfully identified doorways in a six-room gridworld using only local, sampled data. This proves that agents do not need a "god's eye view" of the entire environment to discover highly effective skills.
Limitations and Future Work
- Computational Complexity: Even with the incremental approach, calculating betweenness on large subgraphs can be computationally heavy. More efficient approximation methods are needed for massive state spaces.
- Passive vs. Active Discovery: The current incremental algorithm "passively" mines data from random walks. Transitioning to "active exploration"—where the agent specifically seeks out states that might be local maxima—is a promising next step.
- State Representation: The method relies on a discrete state-transition graph. Extending this framework to continuous state spaces, which are common in robotics, remains an open challenge.
Summary updated