TY - JOUR
T1 - Single Sample Fictitious Play
AU - Swenson, Brian
AU - Kar, Soummya
AU - Xavier, Joao
N1 - Funding Information:
Manuscript received June 13, 2015; revised March 14, 2016, October 9, 2016, and February 18, 2017; accepted May 4, 2017. Date of publication May 29, 2017; date of current version October 25, 2017. This work was supported in part by the FCT Project FCT [UID/EEA/50009/2013] through the Carnegie-Mellon/Portugal Program managed by ICTI from FCT and by FCT Grant CMU-PT/SIA/0026/2009, and in part by the NSF Grant ECCS-1306128. Recommended by Associate Editor A. Garcia. (Corresponding author: Soummya Kar.) B. Swenson is with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail: brianswe@andrew.cmu.edu).
Publisher Copyright:
© 2012 IEEE.
PY - 2017/11
Y1 - 2017/11
N2 - This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)-A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples.
AB - This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)-A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples.
UR - http://www.scopus.com/inward/record.url?scp=85036460142&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85036460142&partnerID=8YFLogxK
U2 - 10.1109/TAC.2017.2709548
DO - 10.1109/TAC.2017.2709548
M3 - Article
AN - SCOPUS:85036460142
SN - 0018-9286
VL - 62
SP - 6026
EP - 6031
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 11
M1 - 7935409
ER -