Sampled fictitious play is Hannan consistent

DOI10.1016/J.GEB.2018.01.005MaRDI QIDQ1753299zbMATH OpenOpenAlexFDO

Authors Zifan Li, Ambuj Tewari

Publication date 29 May 2018

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01687

zbMATH Keywords

learningrepeated gamesfictitious playHannan consistencyadaptive heuristics

Mathematics Subject Classification ID

Multistage and repeated games (91A20) Rationality and learning in game theory (91A26)

Abstract: Fictitious play is a simple and widely studied adaptive heuristic for playing repeated games. It is well known that fictitious play fails to be Hannan consistent. Several variants of fictitious play including regret matching, generalized regret matching and smooth fictitious play, are known to be Hannan consistent. In this note, we consider sampled fictitious play: at each round, the player samples past times and plays the best response to previous moves of other players at the sampled time points. We show that sampled fictitious play, using Bernoulli sampling, is Hannan consistent. Unlike several existing Hannan consistency proofs that rely on concentration of measure results, ours instead uses anti-concentration results from Littlewood-Offord theory.

Recommendations

• Consistency and cautious fictitious play
• A general class of adaptive strategies
• On the rate of convergence of fictitious play
• On the rate of convergence of fictitious play
• Consistency of vanishingly smooth fictitious play

Cites work

• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 1233801 (Why is no real title available?)
• A Fictitious Play Approach to Large-Scale Optimization
• A Remark on Stirling's Formula
• Efficient algorithms for online decision problems
• From external to internal regret
• Internal regret in on-line portfolio selection
• Learning dynamics in games with stochastic perturbations
• On a lemma of Littlewood and Offord
• Prediction, Learning, and Games
• Simple adaptive strategies. From regret-matching to uncoupled dynamics. With the collaboration of Yakov Babichenko, Amotz Cahn, Yishay Mansour and David Schmeidler

Cited in

(4)

• A general class of adaptive strategies
• Consistency of vanishingly smooth fictitious play
• Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games
• Multi-agent reinforcement learning: a selective overview of theories and algorithms

This page was built for publication: Sampled fictitious play is Hannan consistent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753299)