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

102 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

Cite this

@article{af04b771a9924edfbbefa043519e17fc,
title = "Learning to Act: Qualitative Learning of Deterministic Action Models",
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.",
keywords = "Action model learning, Dynamic epistemic logic, Action types, Formal learning theory, Computational complexity",
author = "Thomas Bolander and Nina Gierasimczuk",
year = "2017",
doi = "10.1093/logcom/exx036",
language = "English",
volume = "28",
pages = "337--365",
journal = "Journal of Logic and Computation",
issn = "0955-792X",
publisher = "Oxford University Press",
number = "2",

}

Learning to Act: Qualitative Learning of Deterministic Action Models. / Bolander, Thomas; Gierasimczuk, Nina.

In: Journal of Logic and Computation, Vol. 28, No. 2, 2017, p. 337-365.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Learning to Act: Qualitative Learning of Deterministic Action Models

AU - Bolander, Thomas

AU - Gierasimczuk, Nina

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Action model learning

KW - Dynamic epistemic logic

KW - Action types

KW - Formal learning theory

KW - Computational complexity

U2 - 10.1093/logcom/exx036

DO - 10.1093/logcom/exx036

M3 - Journal article

VL - 28

SP - 337

EP - 365

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

SN - 0955-792X

IS - 2

ER -