A Near-Optimal Poly-Time Algorithm for Learning a class of Stochastic Games
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 734-738.
Abstract
We present a new algorithm for polynomial time learning of near optimal behavior in stochastic games. This algorithm incorporates and integrates important recent results of Keams and Singh [ 1998] in reinforcement learning and of Monderer and Tennenholtz [1997] in repeated games. In stochastic games we face an exploration vs. exploitation dilemma more complex than in Markov decision processes. Namely, given information about particular parts of a game matrix, how much effort should the agent invest in learning its unknown parts. We explain and address these issues within the class of single controller stochastic games. This solution can be extended to stochastic games in general.
@inproceedings{ijcai1999p105,
title = {A Near-Optimal Poly-Time Algorithm for Learning a class of Stochastic Games},
author = {Brafman, Ronen I. and Tennenholtz, Moshe},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {734--738},
year = {1999},
note = {Machine Learning},
url = {https://ijcai.org/proceedings/1999/105},
}
TY - CPAPER TI - A Near-Optimal Poly-Time Algorithm for Learning a class of Stochastic Games AU - Brafman, Ronen I. AU - Tennenholtz, Moshe T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 734 EP - 738 UR - https://ijcai.org/proceedings/1999/105 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
