A near-optimal polynomial time algorithm for learning in certain classes of stochastic games
type: Item
instance of: scholarly article
title: A near-optimal polynomial time algorithm for learning in certain classes of stochastic games
zbMATH Open document ID: 0951.68119
DOI: 10.1016/S0004-3702(00)00039-4
published in: Artificial Intelligence
publication date: 2000-10-26T00:00:00Z
review text: 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 \textit{Kearns} and \textit{Singh} [Proc. ICML-98 (1998)] in reinforcement learning and of \textit{Monderer} and \textit{M. Tennenholtz} [J. Artif. Intell. Res. 7, 231 (1997)] 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.
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 1521720
zbMATH Keywords: stochastic games
zbMATH Keywords: polynomial time learning in hostile environments
zbMATH Keywords: exploration versus exploitation in multi-agent systems
author: Ronen Brafman
author: Moshe Tennenholtz
MaRDI profile type: Publication
cites work: Q4004078
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Q3912508
cites work: Near-optimal reinforcement learning in polynomial time
cites work: An orderfield property for stochastic games when one player controls transition probabilities
cites work: Stochastic Games
cites work: Linear programming and undiscounted stochastic games in which one player controls transitions
Wikidata QID: Q126657516
description: scientific article; zbMATH DE number 1521720