A novel heuristic Q-learning algorithm for solving stochastic games
Jianwei Li, Weiyi Liu · 2008
We solve Nash equilibrium of stochastic games using heuristic Q-learning method based on “heuristic learning” + “ Q-learning” under the framework of noncooperative general-sum games. Determining whether a strategy Nash equilibrium exists in a stochastic game is NP-hard even if the game is finite. Therefore normal Q-learning method based on iterative learning can’t solve stochastic games with larger scale. We attempt to make heuristic evaluations for the rewards of each stage game encountered during learning and improve continually the relevant heuristic Q-values in order to approach the optimal learning. Based on such thought, we proposed Multi-agent Heuristic Q-Learning(MHQL)method and proved that its correctness, convergence and acceptable solving time complexity. The experimentation shows that our method can drastically decrease inefficient and repetitive learning thus speed up convergence than iterative Q-learning. Our method can be regarded as a basic framework for general heuristic Q-learning to design better heuristic learning rules.