| This work studies decision making in multi-agent systems, such as robotic soccer, poker, Quake. The focus is on designing computationally tractable algorithms that tell one agent (our agent) what to do in the presence of other agents. More precisely, we look at the problem of computing a best-response policy for our agent given a game with a set of opponents, where opponents are not necessarily adversarial, but simply self interested. We categorize the set of games along two axes: known versus unknown structure, and fully versus partially observable states and actions.; In games with known structure, our agent knows the state space, the action space, the probability transition functions, the rewards. Finding best-response in such games is a planning problem. In games with unknown structure, our agent does not know the probability transition functions, the rewards and must explore the game in order to understand the system dynamics. Finding best-response then becomes a learning problem.; Along the second axis, in fully observable games our agent has access to all information relevant for the decision making, including the history of the game play, the current states, actions, and rewards. In partially observable games, on the other hand, some of this information is hidden, and our agent instead receives observations that only partially describe underlying states, actions and rewards.; In this space of games, we look at three quadrants and study three particular instances of problems. We study planning in fully observable games, planning in partially observable games, and learning in fully observable games. In each case computing best-response policy for our agent is intractable. Instead, we provide computationally feasible algorithms for computing approximations to best-response policy-good-response policy, and demonstrate the performance of our algorithms with experimental data. |
