Abstract
This paper analyzes the complexity of on-line reinforcement learning algorithms, namely asynchronous realtime versions of Q-learning and value-iteration, applied to the problem of reaching a goal state in deterministic domains. Previous work had concluded that, in many cases, tabula rasa reinforcement learning was exponential for such problems, or was tractable only if the learning algorithm was augmented. We show that, to the contrary, the algorithms are tractable with only a simple change in the task representation or initialization. We provide tight bounds on the worst-case complexity, and show how the complexity is even smaller if the reinforcement learning algorithms have initial knowledge of the topology of the state space or the domain has certain special properties. We also present a novel bidirectional Q-learning algorithm to find optimal paths from all states to a goal state and show that it is no more complex than the other algorithms.
Introduction
In their 1993 paper, Sven Koenig and Reid G. Simmons challenged the prevailing wisdom regarding the efficiency of Reinforcement Learning (RL). At the time, many researchers believed that "tabula rasa" (starting from scratch) RL was fundamentally too slow for real-world path planning, often requiring an exponential number of actions to find a goal. Koenig and Simmons proved that with a simple shift in task representation, RL becomes surprisingly tractable, moving from exponential to polynomial complexity.
The On-line Path Planning Problem
The paper addresses the "on-line path planning" problem: an agent is dropped into an unknown environment and must find its way to a goal. Because the environment is unknown, the agent must learn by doing—interleaving exploration with action.
The major hurdle identified by previous studies was a "complexity wall," suggesting that reaching a goal using standard RL could take a number of steps that grew exponentially with the size of the state space. This led researchers to add complex augmentations to RL, such as directed exploration mechanisms. Koenig and Simmons asked whether the problem lay with the RL algorithms themselves or simply with how the goal was described to the agent.
Methods and Task Representation
The authors analyzed two classic algorithms and introduced a novel third:
- 1-step Q-learning: Learns the value of specific actions in specific states.
- 1-step Value-Iteration: Assumes the agent can see the immediate results of all possible actions in its current state.
- Bi-directional Q-learning: A new algorithm that interleaves forward and backward searches to efficiently determine the optimal path from every possible state to the goal.
The key innovation investigated is Task Representation. Instead of a "Goal-Reward" setup where the agent only receives a reward upon finishing, they utilize an "Action-Penalty" setup where every move costs -1. This creates a dense reward structure that forces the agent to learn from every step taken.
Complexity Bounds
The paper mathematically demonstrates that changing the task representation reduces the complexity of reaching a goal from exponential to polynomial. Specifically, they proved that "admissible" Q-learning using action penalties has a tight worst-case complexity of $O(en)$ or $O(n^3)$, where $n$ is the number of states and $e$ is the number of possible actions. Value-iteration is even faster, achieving a complexity of $O(n^2)$.
Experimental Results
The authors evaluated these theories using simulated deterministic environments, including "Reset State Spaces" where actions can send the agent back to the start, and One-Dimensional Gridworlds.
As shown in the experimental data for Reset State Spaces, random walks are disastrously inefficient as the state space grows. In contrast, Q-learning and value-iteration using action-penalty representations scale predictably and stay well within polynomial bounds. Value-iteration consistently outperforms Q-learning because it utilizes more information about successor states.
Conclusion and Future Work
Koenig and Simmons' work shows that representation is everything. The "exponential explosion" of RL was not a flaw in the algorithms, but a result of sparse rewards. By penalizing every move, the agent immediately begins mapping the topology of the space. While this study focused on deterministic domains, it provides a foundational framework for understanding complexity in more complex, stochastic environments. Future work may explore how partial initial knowledge of a map can further reduce these complexity bounds.
Summary updated