Learning to Act: Qualitative Learning of Deterministic Action Models

Thomas Bolander*, Nina Gierasimczuk

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

191 Downloads (Pure)

Abstract

In this article we study learnability of fully observable, universally applicable action models of dynamic epistemic logic. We introduce a framework for actions seen as sets of transitions between propositional states and we relate them to their dynamic epistemic logic representations as action models. We introduce and discuss a wide range of properties of actions and action models and relate them via correspondence results. We check two basic learnability criteria for action models: finite identifiability (conclusively inferring the appropriate action model in finite time) and identifiability in the limit (inconclusive convergence to the right action model). We show that deterministic actions are finitely identifiable, while arbitrary (non-deterministic) actions require more learning power—they are identifiable in the limit. We then move on to a particular learning method, i.e. learning via update, which proceeds via restriction of a space of events within a learning-specific action model. We show how this method can be adapted to learn conditional and unconditional deterministic action models. We propose update learning mechanisms for the afore mentioned classes of actions and analyse their computational complexity. Finally, we study a parametrized learning method which makes use of the upper bound on the number of propositions relevant for a given learning scenario. We conclude with describing related work and numerous directions of further work.
Original languageEnglish
JournalJournal of Logic and Computation
Volume28
Issue number2
Pages (from-to)337-365
ISSN0955-792X
DOIs
Publication statusPublished - 2017

Keywords

  • Action model learning
  • Dynamic epistemic logic
  • Action types
  • Formal learning theory
  • Computational complexity

Fingerprint Dive into the research topics of 'Learning to Act: Qualitative Learning of Deterministic Action Models'. Together they form a unique fingerprint.

Cite this