On the Learnability of Causal Domains: Inferring Temporal Reality from Appearances
Loizos Michael · 2007
We examine the feasibility of learning causal domains by ob-serving transitions between states as a result of taking certain actions. We take the approach that the observed transitions are only a macro-level manifestation of the underlying micro-level dynamics of the environment, which an agent does not directly observe. In this setting, we ask that domains learned through macro-level state transitions are accompanied by for-mal guarantees on their predictive power on future instances. We show that even if the underlying dynamics of the envi-ronment are signicantly restricted, and even if the learnabil-ity requirements are severely relaxed, it is still intractable for an agent to learn a model of its environment. Our negative results are universal in that they apply independently of the syntax and semantics of the framework the agent utilizes as its modelling tool. We close with a discussion of what a com-plete theory for domain learning should take into account, and how existing work can be utilized to this effect.