Abstract
We analyze the complexity of on-line reinforcement-learning algorithms applied to goal-directed exploration tasks. Previous work had concluded that, even in deterministic state spaces, initially uninformed reinforcement learning was at least exponential for such problems, or that it was of polynomial worst-case time-complexity only if the learning methods were augmented. We prove that, to the contrary, the algorithms are tractable with only a simple change in the reward structure (e.g., action penalties) or initialization (e.g., optimistic values).
Introduction
In the early 1990s, a significant gap existed between the empirical success of reinforcement learning (RL) and theoretical complexity bounds. While RL worked well in practice, theorists like Whitehead (1991) had proven that "uninformed" RL could take exponential time to find a goal, even in simple deterministic environments. This intractability arises because, until the agent reaches the goal, it receives no feedback, effectively performing a random walk. Koenig and Simmons (1996) address this by determining the specific conditions that make goal-directed exploration tractable versus intractable.
Reinforcement Learning Framework
The authors analyze two primary 1-step RL algorithms:
- Watkins’ Q-learning: A standard risk-neutral approach that averages expected rewards.
- Heger’s $\hat{Q}$-learning: A risk-averse variant using a minimax approach, suitable for guaranteeing results in non-deterministic environments.
The study focuses on "on-line" algorithms, where the agent learns while moving, and measures complexity by the number of actions taken to reach the goal for the first time.
Experimental Environments
To prove complexity bounds, the authors utilize synthetic state-space topologies rather than empirical datasets:
- Reset State Spaces: A "hard" environment where a single incorrect move returns the agent to the start state.
- Gridworlds: Standard rectangular environments used to evaluate how complexity scales with the diameter (distance) of the space.
- Safely Explorable Spaces: Environments where no state is a "dead end," ensuring the goal is always reachable.
Theoretical Analysis: Representation and Knowledge
The paper identifies two critical factors in RL efficiency:
- Reward Representation: In a Goal-Reward setup (reward of 1 at goal, 0 elsewhere) with zero initialization, the agent lacks a gradient to follow until it accidentally hits the goal. In contrast, an Action-Penalty representation (penalty of -1 for every action) provides immediate feedback. The agent "remembers" visited states as having lower values, effectively pushing it toward unexplored territory.
- Initialization: Initializing a Goal-Reward system with optimistic values (e.g., all 1s) acts similarly to an action penalty. As the agent fails to find the goal, these values decrease, creating a frontier of high-value unexplored states that guides exploration.
Additionally, the authors introduce $Q_{map}$-learning, a DYNA-style architecture that learns an internal world model to plan shorter paths to unexplored areas.
Complexity Results
The authors provide formal proofs for the following:
- Intractability: Zero-initialized Goal-Reward RL is indeed exponential, requiring an average of $3 \times 2^{n-2} - 2$ actions in a reset space of size $n$.
- Tractability: With Action-Penalty or Optimistic Initialization, complexity is reduced to $O(ed)$, where $e$ is the number of state-action pairs and $d$ is the diameter of the state space. In a typical 2D gridworld, this translates to efficient polynomial scaling (roughly $O(n^{1.5})$ or $O(n^2)$).
- Model-Based Efficiency: $Q_{map}$-learning can further reduce complexity by at least a factor of $n$ in certain hard spaces by allowing the agent to plan paths to the knowledge frontier.
Discussion and Limitations
While the paper proves RL can be tractable, it relies on the "safely explorable" assumption; in environments with permanent traps or dead ends, these guarantees do not hold. Furthermore, the focus is on initial exploration (reaching the goal once) rather than the complexity of converging to an optimal policy. While $Q_{map}$-learning reduces physical actions, it introduces significant computational overhead for model planning. Finally, while these $O(ed)$ bounds are polynomial in the number of states, applying them to modern deep RL with continuous or massive state spaces remains a challenge.
Summary updated