A Modified Q-Learning Algorithm in Games
Yatao Wang · TSpace (University of Toronto) · 2014
This thesis presents a modified Q-learning algorithm and provides conditions for convergence to a pure Nash equilibrium in potential games. In general Q-learning schemes, convergence to a Nash equilibrium may require decreasing step-sizes and long learning time. In this thesis, we consider a modified Q-learning algorithm based on constant step-sizes, inspired by Joint Strategy Fictitious Play (JSFP). When compared to JSFP, the Q-learning with constant step-sizes requires less information aggregation, but only reaches an approximation of a Nash equilibrium. We show that by appropriately choosing frequency dependent step-sizes, sufficient exploration of all actions is ensured and the estimated equilibrium approaches a Nash equilibrium.