Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis

An agent acting under uncertainty regarding how it should complete the task assigned to it by its human user can learn more about how it should behave by posing queries to its human user, provided its user is capable of responding to them. Asking too many, however, may risk requiring undue attentional demand of the user, and so the agent should prioritize asking the most valuable queries. For decision-making agents, the value of a query is measured by its Expected Value of Information (EVOI), and so given a set of queries the agent can ask, the agent should ask the query that is expected to maximally improve its performance by selecting the query with highest EVOI in its set. Unfortunately, to compute the EVOI of a query, the agent must consider how each possible response would influence its future behavior, which makes query selection particularly challenging in settings where planning the agent's behavior would be expensive even without the added complication of considering queries to ask, especially when there are many potential queries the agent should consider. The focus of this dissertation is on developing query selection algorithms that can be feasibly applied to such settings.

The main novel approach studied, Decision Query Projection (DQP), is based on the intuition that the agent should consider which query to ask on the basis of obtaining knowledge that would help it resolve a particular dilemma that it "wishes' could be resolved, as opposed to blindly searching its entire query set in hopes of finding one that would give it valuable knowledge. In implementing DQP, this dissertation contributes algorithms that are founded upon the following novel result: for myopic settings, when the agent can ask any query as long as the query has no more than some set number of possible responses, the best query takes the form of asking the user to choose from a specified subset of ways for the agent to behave. Through empirical comparisons in a housing recommendation problem and theoretical analysis, DQP is shown to select queries with near-optimal EVOI when the agent's query set is (1) rich in terms the highest contained query EVOI; and (2) balanced in terms of the obtainable information about which decisions are best.