F ast Planning in Sto c hastic Games.pdfVIP

Fast Planning in Sto chastic Games Michael Kearns Yishay Mansour Satinder Singh ATT Labs Tel Aviv University ATT Labs Florham Park, New Jersey Tel Aviv, Israel Florham Park, New Jersey mkearns@ mansour@math.tau.ac.il baveja@ Abstract vide b oth algorithms and mathematical foundations for agents in complex, distributed environments. Sto chastic games generalize Markov decision Given the detailed theoretical and practical under- pro cesses (MDPs) to a multiagent setting standing of single-agent planning and learning in by allowing the state transitions to dep end Markov decision pro cesses (MDPs) that has b een built join tly on all player actions, and having over the last decade, one natural line of research is the rewards determined by multiplayer matrix extension of these algorithms and analyses to a multi- games at each state. We consider the prob- agent setting (Boutilier, Goldszmidt, and Sabata 1999; lem of computing Nash equilibria in sto chas- Brafman and Tennenholtz 1999; Hu and Wellman tic games, the analogue of planning in MDPs. 1998). The work presented here is a contribution to We b egin by providing a generalization of this line. We consider the problem of computing Nash nite-horizon value iteration that computes equilibria in sto chastic games. Sto chastic games gen- a Nash strategy for eac