We describe a class of stateful games, which we call ‘medium-access games’, as a model for human and machine communication and demonstrate how to use the Nash equilibria of those games as played by pairs of agents with stationary policies to predict turn-taking behaviour in Q-learning agents based on the agents’ reward function. We identify which fixed policies exhibit turn-taking behaviour in medium-access games and show how to compute the Nash equilibria of such games by using Markov chain methods to calculate the agents’ expected rewards for different stationary policies. We present simulation results for an extensive range of reward functions for pairs of Q-learners playing medium-access games and we use our analysis for stationary agents to develop predictors for the emergence of turn-taking. We explain how to use our predictors to design reward functions for pairs of Q-learning agents that are conducive (or prohibitive) to the emergence of turn-taking in medium-access games. We focus on designing multi-agent reinforcement learning systems that deliberately produce coordinated turn-taking but we also intend our results to be useful for analysing emergent turn-taking behaviour. Based on our turn-taking related results, we suggest ways to use our methodology to designs rewards for quantifiable behaviours besides turn-taking.
BowlingM.VelosoM. (2002). Multiagent learning using a variable learning rate. Artificial Intelligence, 136(2): 215–250.
2.
BusoniuL.BabuskaR.De SchutterB. (2008). A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 38(2): 156–172.
3.
ChaoC.ThomazA. L. (2010). Turn taking for human-robot interaction. In AAAI fall symposium on dialog with robots, Arlington, USA, 11–13 November 2010, pp. 132–134. Palo Alto, CA: AAAI Press.
4.
ChenL.LowS. H.DoyleJ. C. (2010). Random access game and medium-access control design. IEEE/ACM Transactions on Networking, 18(4): 1303–1316.
CrandallJ. W.GoodrichM. A. (2010). Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning. Machine Learning, 82(3): 281–314.
7.
Di PaoloE. A. (2000). Behavioral coordination, structural congruence and entrainment in a simulation of acoustically coupled agents. Adaptive Behavior, 8(1): 27–48.
8.
FawcettT. (2006). An introduction to ROC analysis. Pattern Recognition Letters, 27(8): 861–874.
9.
FlamS. (2002). Equilibrium, evolutionary stability and gradient dynamics. International Game Theory Review, 4(4): 357–370.
10.
FloodM. M. (1958). Some experimental games. Management Science, 5(1): 5–26.
11.
GoldmanC.AllenM.ZilbersteinS. (2007). Learning to communicate in a decentralized environment. Autonomous Agents and Multi-Agent Systems, 15(1): 47–90.
12.
GordonG. J. (2007). Agendas for multi-agent learning. Artificial Intelligence, 171(7): 392–401.
13.
GreenwaldA.HallK.SerranoR. (2003). Correlated Q-learning. In 20th International Conference on Machine Learning, Washington DC, USA, 242.
14.
HäggströmO. (2002). Finite Markov chains and algorithmic applications. Cambridge, UK: Cambridge University Press.
15.
HarcourtJ.SweetmanG.ManicaA.JohnstoneR. (2010). Pairs of fish resolve conflicts over coordinated movement by taking turns. Current Biology, 20(2): 156–160.
16.
HardinG. (1968). The tragedy of the commons. Science, 162(3859): 1243–1248.
17.
HelbingD.SchoenhofM.StarkH.HolystJ. (2005). How individuals learn to take turns: Emergence of alternating cooperation in a congestion game and the prisoner’s dilemma. Advances in Complex Systems, 8: 87–116.
18.
HuJ.WellmanM. P. (2003). Nash Q-learning for general-sum stochastic games. The Journal of Machine Learning Research, 4: 1039–1069.
19.
IizukaH.IkegamiT. (2004). Adaptability and diversity in simulated turn-taking behavior. Artificial Life, 10(4): 361–378.
20.
KitanoH.AsadaM.KuniyoshiY.NodaI.OsawaE. (1997). RoboCup: the robot world cup initiative. In 1st international conference on autonomous agents, Marina del Rey, USA, 5–8 February 1997, pp. 340–347. New York, NY: ACM Press.
21.
Kose-BagciH.DautenhahnK.NehanivC. (2008). Emergent dynamics of turn-taking interaction in drumming games with a humanoid robot. In 17th IEEE international symposium on robot and human interactive communication, Munich, Germany, 1–3 August 2008, pp. 346–353. Piscataway, NJ: IEEE Press.
22.
LarssonE. G.JorswieckE.LindblomJ.MochaourabR. (2009). Game theory and the flat fading Gaussian interference channel. IEEE Signal Processing Magazine, 26(5): 18–27.
23.
LeshemA.ZehaviE. (2009). Game theory and the frequency selective interference channel. IEEE Signal Processing Magazine, 26(5): 28–40.
24.
MansonJ. H.NavarreteC. D.SilkJ. B.PerryS. (2004). Time-matched grooming in female primates? New analyses from two species. Animal Behaviour, 67(3): 493–500.
25.
NashJ. F. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1): 48–49.
26.
NeillD. B. (2001). Optimality under noise: Higher memory strategies for the alternating prisoner’s dilemma. Journal of Theoretical Biology, 211(2): 159–180.
27.
NeillD. B. (2003). Cooperation and coordination in the turn-taking dilemma. In 9th conference on theoretical aspects of rationality and knowledge (Ed. TennenholtzM.), Los Angeles, USA, 5–7 November 2003, pp. 231–244, New York, NY: ACM Press.
28.
NolfiS. (2005). Emergence of communication in embodied agents: co-adapting communicative and non-communicative behaviours. Connection Science, 17(3): 231–248.
29.
PutermanM. L. (1994). Markov decision processes: discrete stochastic dynamic programming. New York, NY: John Wiley & Sons.
30.
QuinnM. (2001). Evolving communication without dedicated communication channels. In 6th european conference on advances in artificial life (Eds. KelemenJ.SosikP.), Prague, Czech Republic, 10–14 September 2001, vol. 2159, pp. 357–366. Berlin, Germany: Springer.
31.
RaffenspergerP. A.WebbR. Y.BonesP. J.McInnesA. I. (2012). A simple metric for turn-taking in emergent communication. Adaptive Behavior, 20(2): 104–116.
32.
RasaO. A. E. (1989). The costs and effectiveness of vigilance behaviour in the dwarf mongoose: implications for fitness and optimal group size. Ethology Ecology & Evolution, 1(3): 265–282.
33.
RauxA.EskenaziM. (2008). Optimizing endpointing thresholds using dialogue features in a spoken dialogue system. In 9th SIGdial workshop on discourse and dialogue (Eds. SchlangenD.HockeyB. A.), Columbus, USA, 19–20 June 2008, pp. 1–10. Morristown, NJ: Association for Computational Linguistics.
34.
SacksH.SchegloffE. A.JeffersonG. (1974). A simplest systematics for the organization of turn-taking for conversation. Language, 50(4): 696–735.
35.
StiversT.EnfieldN. J.BrownP.EnglertC.HayashiM.HeinemannT.. . . LevinsonS. C. (2009). Universals and cultural variation in turn-taking in conversation. Proceedings of the National Academy of Sciences of the United States of America, 106(26): 10587–10592.
36.
SuttonR. S.BartoA. G. (1998). Reinforcement Learning. Cambridge, MA: MIT Press.
37.
TanenbaumA. S. (2002). Computer Networks. Upper Saddle River, NJ: Prentice Hall.
38.
TrivelpieceW.TrivelpieceS.VolkmanN. (1987). Ecological segregation of adelie, gentoo, and chinstrap penguins at King George Island, Antarctica. Ecology, 68(2): 351–361.
39.
TurunenM.HakulinenJ.KainulainenA. (2006). Evaluation of a spoken dialogue system with usability tests and long-term pilot studies: similarities and differences. In 9th international conference on spoken language processing, Pittsburgh, USA, 17–21 September 2006, pp. 1057–1060. Baixas, France: International Speech Communication Association.
40.
Von StengelB. (2007). Equilibrium computation for two-player games in strategic and extensive form. In NisanN.RoughgardenT.TardosE.VaziraniV. V. (Eds.) Algorithmic game theory, (pp. 53–78). Cambridge, UK: Cambridge University Press.
41.
WagnerK.ReggiaJ. A.UriagerekaJ.WilkinsonG. S. (2003). Progress in the simulation of emergent communication and language. Adaptive Behavior, 11(1): 37–69.
42.
WaltmanL.KaymakU. (2007). A theoretical analysis of cooperative behavior in multi-agent Q-learning. In IEEE international symposium on approximate dynamic programming and reinforcement learning, Honolulu, USA, 1–5 April 2007, pp. 84–91. Piscataway, NJ: IEEE Press.
WeinbergG.BlosserB. (2009). A leader-follower turn-taking model incorporating beat detection in musical human-robot interaction. In 4th ACM/IEEE international conference on human-robot interaction, San Diego, USA, 11–13 March 2009, pp. 227–228. New York, NY: ACM Press.
45.
YangJ.KleinA. G.BrownD. R. (2009). Natural cooperation in wireless networks. IEEE Signal Processing Magazine, 26(5): 98–106.
46.
ZinkevichM.GreenwaldA.LittmanM. (2006). Cyclic equilibria in Markov games. In WeissY.SchölkopfB.PlattJ. (Eds.), Advances in Neural Information Processing Systems, vol. 18, pp. 1641–1648. Cambridge, MA: MIT Press
