Introduction
Algorithmic Teaching (AT) explores the theoretical limits of instruction by identifying the smallest, most informative set of examples required for a learner to acquire a target concept. While AT has seen significant success in simple classification tasks, its application to sequential decision-making—where behavior is demonstrated over time—remains a complex challenge. This paper extends AT to the domain of sequential tasks, developing a framework to help robots and humans alike become more effective teachers through Inverse Reinforcement Learning (IRL).
Methodology: Optimal Teaching for IRL
In the IRL framework, a learner observes a teacher's actions and attempts to infer the underlying reward function (the weights assigned to various environmental features) that the teacher is optimizing. The authors' core contribution is an algorithm designed to select demonstrations that most efficiently resolve ambiguity in these reward weights.
Uncertainty Modeling and Greedy Selection
The algorithm maintains a "hypothesis space" of all possible reward weights. It utilizes a Monte Carlo sampling approach to estimate the volume of this space, representing the learner's uncertainty. To select the most informative demonstrations, the authors employ a greedy selection strategy. Rather than solving a hard combinatorial problem to find the absolute best set of trajectories, the algorithm iteratively picks the starting location that results in a trajectory that most drastically shrinks the hypothesis space.
Theoretical Guarantees
A key theoretical insight of the paper is the proof that the uncertainty reduction function is "submodular." This property ensures that the simple greedy approach is mathematically guaranteed to be within a specific factor $(1 - 1/e)$ of the true optimal solution, providing a rigorous foundation for the proposed method.
Experimental Evaluation
The authors evaluated their approach using two custom-designed navigation grid-worlds, Map A and Map B, which serve as controlled benchmarks for reward inference.
As illustrated in the figure above, Map A focuses on preferences between different terrain types (e.g., light vs. dark tiles), while Map B tests preferences between two distinct targets (the "Star" vs. the "Diamond"). These environments allow the researchers to isolate how specific demonstrations resolve ambiguity in reward weights $w_0, w_1, w_2$.
Key Insights: The Power of Decision Points
The algorithm's effectiveness stems from its ability to identify "critical points" in the state space. An informative demonstration is not merely a successful one; it is one that occurs where different choices lead to divergent outcomes, forcing the underlying reward structure to be revealed.
In Figure 2, we see how the algorithm selects different starting points for Task 3 and Task 4 to disambiguate the teacher's intent. By starting the agent in positions where it must choose between paths, the teacher provides much higher information gain than a standard "shortest path" demonstration from a random corner.
Results and Human Teaching
The results of this study are two-fold:
- Efficiency Gains: In simulations, optimally selected demonstrations allowed the learner to reach peak performance 8 to 16 times faster than demonstrations starting from random locations.
- Human Guidance: A user study with 80 participants showed that while humans are naturally sub-optimal teachers—often providing redundant information—they can be significantly improved with algorithmic guidance. Participants who were given simple hints based on the algorithm's logic produced demonstrations that resulted in much lower reward uncertainty.
Conclusion and Future Work
This research demonstrates that algorithmic principles can drastically improve the efficiency of teaching sequential tasks. While currently limited to discrete grid-worlds, the submodular nature of the problem provides a promising path toward scaling these methods to high-dimensional robotic tasks. Future work will explore interactive "Active Learning" scenarios where agents can specifically request demonstrations at the most informative decision points.
Summary updated