Querying to Find a Safe Policy under Uncertain Safety Constraints in Markov Decision Processes

• DOI: 10.1609/aaai.v34i03.5638
• Publication Date: 2020-06-29T19:50:56Z
• Authors: Shun Zhang; Edmund Durfee; Satinder Singh
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; 10. No inequality; 3. Good health

An autonomous agent acting on behalf of a human user has the potential of causing side-effects that surprise the user in unsafe ways. When the agent cannot formulate a policy with only side-effects it knows are safe, it needs to selectively query the user about whether other useful side-effects are safe. Our goal is an algorithm that queries about as few potential side-effects as possible to find a safe policy, or to prove that none exists. We extend prior work on irreducible infeasible sets to also handle our problem's complication that a constraint to avoid a side-effect cannot be relaxed without user permission. By proving that our objectives are also adaptive submodular, we devise a querying algorithm that we empirically show finds nearly-optimal queries with much less computation than a guaranteed-optimal approach, and outperforms competing approximate approaches.