[null, {"document_url": "https://link.springer.com/article/10.1007/s10458-016-9352-6", "unformatted_src": "https://media.springernature.com/w306/springer-static/cover/journal/10458/31/4.jpg", "src": "https://media.springernature.com/w306/springer-static/cover/journal/10458/31/4.jpg"}, null]


Autonomous Agents and Multi-Agent Systems 
July 2017, Volume 31, Issue 4, pp 767–789 | Cite as

Efficiently detecting switches against non-stationary opponents



Interactions in multiagent systems are generally more complicated than single agent ones. Game theory provides solutions on how to act in multiagent scenarios; however, it assumes that all agents will act rationally. Moreover, some works also assume the opponent will use a stationary strategy. These assumptions usually do not hold in real world scenarios where agents have limited capacities and may deviate from a perfect rational response. Our goal is still to act optimally in these cases by learning the appropriate response and without any prior policies on how to act. Thus, we focus on the problem when another agent in the environment uses different stationary strategies over time. This will turn the problem into learning in a non-stationary environment, posing a problem for most learning algorithms. This paper introduces DriftER, an algorithm that (1) learns a model of the opponent, (2) uses that to obtain an optimal policy and then (3) determines when it must re-learn due to an opponent strategy change. We provide theoretical results showing that DriftER guarantees to detect switches with high probability. Also, we provide empirical results showing that our approach outperforms state of the art algorithms, in normal form games such as prisoner’s dilemma and then in a more realistic scenario, the Power TAC simulator.


Learning Non-stationary environments Switching strategies Repeated games

Most of this work was performed while the first author was a graduate student at INAOE.



This research was supported partially by project CB-2012-01-183684 and scholarship 335245/234507 granted by Consejo Nacional de Ciencia y Tecnologia (CONACyT) Mexico. This research has taken place in part at the Intelligent Robot Learning (IRL) Lab, Washington State University. IRL research is supported in part by grants NSF IIS-1149917, NSF IIS-1319412, USDA 2014-67021-22174, and a Google Research Award.







Hernandez-Leal, P., Zhan, Y., Taylor, M.E. et al. Auton Agent Multi-Agent Syst (2017) 31: 767. https://doi.org/10.1007/s10458-016-9352-6



