Adaptive Teaching of Temporal Logic Formulas to Learners with Preferences

Zhe Xu, Yuxin Chen, Ufuk TopcuarXiv 2020 · OpenReview

Abstract

Machine teaching is an algorithmic framework for teaching a target hypothesis via a sequence of examples or demonstrations. We investigate machine teaching for temporal logic formulas -- a novel and expressive hypothesis class amenable to time-related task specifications. In the context of teaching temporal logic formulas, an exhaustive search even for a myopic solution takes exponential time (with respect to the time span of the task). We propose an efficient approach for teaching parametric linear temporal logic formulas. Concretely, we derive a necessary condition for the minimal time length of a demonstration to eliminate a set of hypotheses. Utilizing this condition, we propose a myopic teaching algorithm by solving a sequence of integer programming problems. We further show that, under two notions of teaching complexity, the proposed algorithm has near-optimal performance. The results strictly generalize the previous results on teaching preference-based version space learners. We evaluate our algorithm extensively under a variety of learner types (i.e., learners with different preference models) and interactive protocols (e.g., batched and adaptive). The results show that the proposed algorithms can efficiently teach a given target temporal logic formula under various settings, and that there are significant gains of teaching efficacy when the teacher adapts to the learner's current hypotheses or uses oracles.

Introduction

Machine Teaching (MT) aims to find the minimal set of examples—a curriculum—that directs a learning algorithm toward a specific target hypothesis. While MT is well-established for simple concepts like linear classifiers, teaching Temporal Logic presents a significant computational challenge. Temporal logic describes system behavior over time (e.g., "Always stay in the green zone, but eventually visit the blue zone within 5 seconds"), making it ideal for complex task specifications in robotics and AI.

However, teaching these formulas involves two primary hurdles:

  1. Exponential Search Space: Identifying the shortest trajectory to invalidate an incorrect logic formula requires searching through an exponential number of possible time-series sequences.
  2. Learner Biases: Real-world learners often possess internal preferences, such as favoring simpler formulas. Inefficient teaching occurs if these biases are ignored.

Methodology: The TLIP Framework

To address these challenges, we introduce TLIP (Teaching pLTL Formulas with Integer Programming). This framework focuses on a fragment of Parametric Linear Temporal Logic (pLTL), specifically formulas utilizing "Always" ($G$) and "Eventually" ($F$) operators with defined time bounds.

Teaching Demonstrations

The teaching process relies on providing demonstrations, which are trajectories of states over time. These trajectories serve as evidence to prune the learner's hypothesis space by demonstrating what behaviors satisfy or violate specific temporal constraints.

Example of temporal demonstrations (trajectories) used to teach pLTL formulas.

Core Contributions

  • Necessary Conditions: The authors derive mathematical conditions for the minimum trajectory length required to eliminate specific sets of incorrect hypotheses.
  • Integer Programming (IP) Formulation: Instead of brute-force searching, TLIP formulates the selection of the next demonstration as an IP problem. This allows the use of optimized solvers like Gurobi to find near-optimal "myopic" (greedy) solutions efficiently.
  • Preference-Based Learning: The model accounts for learners with specific preferences. The teacher can operate in non-adaptive (fixed batch) or adaptive (interactive) modes, where the teacher reacts to the learner's current guess.
  • Teaching Oracles: For learners stuck in local preference minima, the framework introduces oracles that provide intermediate target hypotheses to guide the learner step-by-step.

Evaluation and Results

The algorithm was evaluated using synthetic pLTL sets (270 formulas) and a simulated 81-cell gridworld robot navigation scenario where the robot must learn movement rules based on color-coded states.

Key Performance Metrics

  • Scalability: While Exhaustive Search (ESMT) timed out after 300 minutes for trajectories of length 10, TLIP solved the same problems in under 8 seconds.
  • Efficiency: TLIP reduced the number of demonstrations by 50% to 80% compared to randomized greedy baselines.
  • Adaptivity and Oracles: Adaptive teaching reduced costs by up to 31.15%, while oracles provided a 75% reduction in the most difficult cases involving local preferences.

Discussion and Conclusion

The results demonstrate that a "greedy" teacher—one that picks the best next example to eliminate the most "preferred" incorrect hypotheses—is near-optimal, staying within a logarithmic factor of the absolute best possible sequence. The study also highlights the trade-off between AN-Cost (number of examples) and AL-Cost (total trajectory length), which is vital for practical robotics where long demonstrations are costly.

While currently limited to the ($F$, $G$) fragment of pLTL, future work aims to incorporate the "Until" ($U$) operator and test these methods against black-box reinforcement learning algorithms in continuous systems.

Summary updated

Abstract

Machine teaching is an algorithmic framework for teaching a target hypothesis via a sequence of examples or demonstrations. We investigate machine teaching for temporal logic formulas -- a novel and expressive hypothesis class amenable to time-related task specifications. In the context of teaching temporal logic formulas, an exhaustive search even for a myopic solution takes exponential time (with respect to the time span of the task). We propose an efficient approach for teaching parametric linear temporal logic formulas. Concretely, we derive a necessary condition for the minimal time length of a demonstration to eliminate a set of hypotheses. Utilizing this condition, we propose a myopic teaching algorithm by solving a sequence of integer programming problems. We further show that, under two notions of teaching complexity, the proposed algorithm has near-optimal performance. The results strictly generalize the previous results on teaching preference-based version space learners. We evaluate our algorithm extensively under a variety of learner types (i.e., learners with different preference models) and interactive protocols (e.g., batched and adaptive). The results show that the proposed algorithms can efficiently teach a given target temporal logic formula under various settings, and that there are significant gains of teaching efficacy when the teacher adapts to the learner's current hypotheses or uses oracles.
BibTeX
@misc{xu2020adaptive,
  author = {Zhe Xu and Yuxin Chen and Ufuk Topcu},
  title = {{Adaptive Teaching of Temporal Logic Formulas to Learners with Preferences}},
  year = {2020},
  eprint = {2001.09956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.09956},
}
Figure