Multi-View Decision Processes: The Helper-AI Problem ������������������������������� �����������������������
We consider a two-player sequential game in which agents have the same reward function but may disagree on the transition probabilities of an underlying Markovian model of the world. By committing to play a specific policy, the agent with the correct model can steer the behavior of the other agent, and seek to improve utility. We model this setting as a multi-view decision process, which we use to formally analyze the positive effect of steering policies. Furthermore, we develop an algorithm for computing the agents' achievable joint policy, and we experimentally show that it can lead to a large utility increase when the agents' models diverge.
1 Introduction.
In the past decade, we have been witnessing the fulfillment of Licklider's profound vision on AI [Licklider, 1960]:
Man-computer symbiosis is an expected development in cooperative interaction between men and electronic computers.
Needless to say, such a collaboration, between humans and AIs, is natural in many real-world AI problems. As a motivating example, consider the case of autonomous vehicles, where a human driver can override the AI driver if needed. With advances in AI, the human will benefit most if she allows the AI agent to assume control and drive optimally. However, this might not be achievable-due to human behavioral biases, such as over-weighting the importance of rare events, the human might incorrectly override the AI. In the way, the misaligned models of the two drivers can lead to a decrease in utility. In general, this problem may occur whenever two agents disagree on their view of reality, even if they cooperate to achieve a common goal.
Formalizing this setting leads to a class of sequential multi-agent decision problems that extend stochastic games. While in a stochastic game there is an underlying transition kernel to which all agents (players) agree, the same is not necessarily true in the described scenario. Each agent may have a different transition model. We focus on a leader-follower setting in which the leader commits to a policy that the follower then best responds to, according to the follower's model. Mapped to our motivating example, this would mean that the AI driver is aware of human behavioral biases and takes them into account when deciding how to drive.
To incorporate both sequential and stochastic aspects, we model this as a multi-view decision process. Our multi-view decision process is based on an MDP model, with two, possibly different, transition kernels. One of the agents, hereafter denoted as P 1 , is assumed to have the correct transition kernel and is chosen to be the leader of the Stackelberg game-it commits to a policy that the second agent (P 2 ) best-responds to according to its own model. The agents have the same reward function, and are in this sense cooperative. In an application setting, while the human (P 2 ) may not be a planner, we motivate our set-up as modeling the endpoint of an adaptive process that leads P 2 to adopt a best-response to the policy of P 1 .
Using the multi-view decision process, we analyze the effect of P 2 's imperfect model on the achieved utility. We place an upper bound on the utility loss due to this, and also provide a lower bound on how much P 1 gains by knowing P 2 's model. One of our main analysis tools is the amount of influence an agent has, i.e. how much its actions affect the transition probabilities, both according to its own model, and according to the model of the other agent. We also develop an algorithm, extending backwards induction for simultaneous-move sequential games [c.f. Bošanskỳ et al., 2016], to compute a pair of policies that constitute a subgame perfect equilibrium.
In our experiments, we introduce intervention games as a way to construct example scenarios. In an intervention game, an AI and a human share control of a process, and the human can intervene to override the AI's actions but suffers some cost in doing so. This allows us to derive a multi-view process from any single-agent MDP. We consider two domains: first, the intervention game variant of the shelter-food game introduced by Guo et al. [2013], as well as an autonomous driving problem that we introduce here. Our results show that the proposed approach provides a large increase in utility in each domain, thus overcoming the deficiencies of P 2 's model, when the latter model is known to the AI.
The paper introduces multi-view decision processes (MVDP) as a cooperative game between two agents, where one agent may have an imperfect model of the transition probabilities of the other agent.
Generally, the work is motivated well, the problem is interesting and clearly relevant to AI and the NIPS community. The theoretical results are nicely complemented by experiments. Presentation is mostly smooth: the main goals are consistent with the narrative throughout the paper, but the some details from the experiments seem less clear (seem points below.)
Some points are confusing and need further clarification:
1. In the second footnote on page 3, what is a "worst-case best response"? This is not defined, seems like they should all share the property that they attain the maximum value against some policy.
2. The authors talk about solving using backward induction and make reference to Bozansky et al 2016 and Littman 1994, but those works treat exclsively the zero-sum case. MVDP is a cooperative game that can be at least as hard as general-sum games (by Lemma 1), and backward induction generally cannot solve these due to equilibrium selection problems leading to non-unique values for subgames, also shown in Zinkevich et al 2005. How is it possible to apply backward induction by propagating single Q and V values here then? The authors claim to find an approximate joint optimal policy, which is stronger than a Nash equilibrium, and it seems by Zinkevich et al 2005 this should at least require cyclic (nonstationary) strategies.
3. From the start the authors talked about stochastic policies, but this is a cooperative identical payoff game. It's not clear later (seeing the proof of Lemma 1) that mixed strategies are necessary due to the different views leading to an effectively general-sum game. How then could a the determinstic version of the algorithm that computes a pure stationary policy be approximately optimal? Even in the Stackelberg case, mixing could be necessary.
Minor:
The role of c in the c-inervention games is not clear. On page 6, the authors write a cost c(s) is subtracted from the reward r_t when P2 takes an action other. But then in Remark 1 gives the equation rho(s, a) = [rho(s) + cI{a_{t,2} != a^0}] / (1+c) does not subtract c. This can be easily fixed by rewording the text at bottom of page 6.