A near-optimal polynomial time algorithm for learning in certain classes of stochastic games

A near-optimal polynomial time algorithm for learning in certain classes of stochastic games

0.00 Avg rating0 Votes
Article ID: iaor2002353
Country: United States
Volume: 121
Issue: 1/2
Start Page Number: 31
End Page Number: 47
Publication Date: Aug 2000
Journal: Artificial Intelligence
Authors: ,
Abstract:

We present a new algorithm for polynomial time learning of optimal behavior in single-controller stochastic games. This algorithm incorporates and integrates important recent results of Kearns and Singh in repeated games. In stochastic games, the agent must cope with the existence of an adversary whose actions can be arbitrary. In particular, this adversary can withhold information about the game matrix by refraining from (or rarely) performing certain actions. This forces upon us an exploration versus exploitation dilemma more complex than in Markov decision processes in which, given information about particular parts of a game matrix, the agent must decide how much effort to invest in learning the unknown parts of the matrix. We present a polynomial time algorithm that addresses these issues in the context of the class of single controller stochastic games, providing the agent with near-optimal return.

Reviews

Required fields are marked *. Your email address will not be published.