Learning to Take Actions

Roni KhardonAAAI 1996 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

We formalize a model for supervised learning of action strategies in dynamic stochastic domains and show that PAC-learning results on Occam algorithms hold in this model as well. We then identify a class of rule-based action strategies for which polynomial time learning is possible. The representation of strategies is a generalization of decision listss strategies include rules with existentially quantified conditions, simple recursive predicates, and small internal state, but are syntactically restricted. We also study the learnability of hierarchically composed strategies where a subroutine already acquired can be used as a basic action in a higher level strategy. We prove some positive results in this setting, but also show that in some cases the hierarchical learning problem is computationally hard.
BibTeX
@inproceedings{khardon1996learning,
  author = {Roni Khardon},
  title = {{Learning to Take Actions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=S1bZsAldZH},
}
Figure