In 1996, Roni Khardon introduced a framework that bridged a long-standing divide in Artificial Intelligence: the gap between symbolic, logic-based planning and reactive, reinforcement-based learning. This paper formalizes how an agent can learn complex, rule-based strategies by observing a teacher, even within stochastic and partially observable environments.
The Problem: Planning vs. Reinforcement Learning
At the time of this research, AI was largely split into two paradigms. Planning utilized formal logic to find optimal action sequences, but it was often computationally prohibitive and struggled in "noisy" or dynamic worlds. Conversely, Reinforcement Learning (RL) handled noise and dynamic environments well but lacked symbolic structure, often requiring the agent to memorize actions for every possible state—a task that scales exponentially with complexity.
Khardon identifies a middle ground, asking: Can we learn a "reactive" strategy that utilizes symbolic representations? Specifically, how can an agent learn a strategy that succeeds "most of the time" in a stochastic world without performing exhaustive logical reasoning at every step?
The "Learning to Act" Framework
The paper proposes a formal model for supervised learning of action strategies. The key components include:
- The World Model: The environment is treated as a Partially Observable Markov Decision Process (POMDP). Crucially, the learner does not need to know the internal structure of this process; they only need to observe the results of actions.
- Production Rule Systems (PRS): Strategies are represented as a priority list of "if-then" rules (e.g., if the block is clear and the goal is to move it, then move it). This allows for symbolic reasoning that is fast to execute.
- Supervised Learning (The Oracle): Instead of trial-and-error exploration, the agent observes a "teacher" (an oracle) and attempts to find a strategy consistent with the teacher's successful runs.
- The Learn-PRS Algorithm: This greedy algorithm searches for a concise set of rules. It handles "predicate invention"—creating internal definitions for concepts like "is this block part of a tower?"—and reconstructs the teacher's internal state by testing small state-machine configurations.
Key Insights and Theoretical Results
Occam’s Razor for Actions
The paper proves a version of the "Occam's Razor" theorem for action strategies. If an agent finds a simple strategy consistent with a sufficient number of a teacher's successful runs, that strategy is guaranteed (with high probability) to perform nearly as well as the teacher on new problems. This provides a formal proof of PAC (Probably Approximately Correct) learnability in this domain.
Predicate Invention and Hidden State
One of the most powerful aspects of the Learn-PRS algorithm is its ability to "invent" recursive predicates. For example, it can learn the concept of "above" (block A is above block B, even with intermediate blocks) by searching a restricted space of recursive definitions. Furthermore, even if a strategy requires memory (hidden state), the algorithm can learn this by testing different small state-machine configurations until it matches the teacher's behavior.
The Complexity of Hierarchies
The paper also explores hierarchically composed strategies, where subroutines are used as basic actions. Khardon demonstrates that hierarchical learning is computationally efficient if the teacher "labels" the subroutines. However, if the learner must discover the hierarchy autonomously, the problem becomes NP-Hard.
Case Study: Blocks World
The paper utilizes the Blocks World domain—a classic AI benchmark—to illustrate these concepts. While finding optimal solutions in Blocks World is NP-complete, Khardon shows that a PRS can implement a near-optimal strategy and, more importantly, that this strategy can be efficiently learned from examples.
Conclusion and Limitations
Khardon’s work successfully demonstrates that symbolic logic and reactive behavior are not mutually exclusive. By representing a policy as a symbolic PRS, an agent can achieve fast, reactive performance while maintaining an interpretable structure.
However, the model relies heavily on the availability of a competent teacher. If the only successful strategy for a task is incredibly complex, the algorithm may struggle to find a concise representation. Despite these limitations, the paper remains a foundational text for understanding how symbolic strategies can be acquired through observation in complex, stochastic worlds.
Summary updated