Distributed algorithms based on fictitious play for near optimal sequential decision making
Esra Sisikoglu · Deep Blue (University of Michigan) · 2009
We develop stochastic search algorithms to find optimal or close to optimal solutions for sequential decision making problems. We specifically consider two problem classes: 1. Large-scale, discrete, deterministic, finite horizon dynamic programming problems: We use a Sampled Fictitious Play (SFP) algorithm for solving large-scale, finite horizon, discrete dynamic programming (DP) problems. We model the DP problem as an identical interest game between multiple players. We show that the SFP algorithm converges to the equilibrium strategies of this game. In addition, we present two new algorithms, namely Repeated SFP and SFP Based Local Search, that find globally optimal solutions using SFP as a base algorithm. We present the performance of the algorithms on dynamic lot sizing problems and the Traveling Salesman Problem (TSP). Numerical experiments show that our algorithms find close to optimal solutions very quickly. We also present small modifications that improve the performance of the algorithms. 2. Stochastic, discounted, infinite horizon Markov Decision Problems: Using Sampled Fictitious Play (SFP) concepts, we develop an online learning algorithm, referred to as SFP based Learning (SFPL), for solving a discounted homogeneous Markov Decision Problem (MDP) where the transition probabilities are unknown. In SFPL, we estimate and update the unknown transition probabilities, the optimal value, and the optimal action of each state, simultaneously. We prove the convergence of SFPL to the optimal solution. We compare the performance of SFPL with SARSA and Q-Learning on dynamic location and windy gridworld problems.