  Methods for learning optimal policies in autonomous agents often assume that
the way the domain is conceptualised---its possible states and actions and
their causal structure---is known in advance and does not change during
learning. This is an unrealistic assumption in many scenarios, because new
evidence can reveal important information about what is possible, possibilities
that the agent was not aware existed prior to learning. We present a model of
an agent which both discovers and learns to exploit unforeseen possibilities
using two sources of evidence: direct interaction with the world and
communication with a domain expert. We use a combination of probabilistic and
symbolic reasoning to estimate all components of the decision problem,
including its set of random variables and their causal dependencies. Agent
simulations show that the agent converges on optimal polices even when it
starts out unaware of factors that are critical to behaving optimally.
