Closed-form Solutions to a Subclass of Continuous Stochastic Games via Symbolic Dynamic Programming

Shamin Kinathil, Scott Sanner, Nicolás Della Penna
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:823-832, 2014.

Abstract

Zero-sum stochastic games provide a formalism to study competitive sequential interactions between two agents with diametrically opposing goals and evolving state. A solution to such games with discrete state was presented by Littman (Littman, 1994). The continuous state version of this game remains unsolved. In many instances continuous state solutions require non-linear optimisation, a problem for which closed-form solutions are generally unavailable. We present an exact closed-form solution to a sub-class of zero-sum continuous stochastic games that can be solved as a parameterised linear program by utilising symbolic dynamic programming. This novel technique is applied to calculate exact solutions to a variety of zero-sum continuous state stochastic games.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-kinathil14a, title = {Closed-form Solutions to a Subclass of Continuous Stochastic Games via Symbolic Dynamic Programming}, author = {Kinathil, Shamin and Sanner, Scott and Della Penna, Nicol{\'a}s}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {823--832}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/kinathil14a/kinathil14a.pdf}, url = {https://proceedings.mlr.press/r12/kinathil14a.html}, abstract = {Zero-sum stochastic games provide a formalism to study competitive sequential interactions between two agents with diametrically opposing goals and evolving state. A solution to such games with discrete state was presented by Littman (Littman, 1994). The continuous state version of this game remains unsolved. In many instances continuous state solutions require non-linear optimisation, a problem for which closed-form solutions are generally unavailable. We present an exact closed-form solution to a sub-class of zero-sum continuous stochastic games that can be solved as a parameterised linear program by utilising symbolic dynamic programming. This novel technique is applied to calculate exact solutions to a variety of zero-sum continuous state stochastic games.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Closed-form Solutions to a Subclass of Continuous Stochastic Games via Symbolic Dynamic Programming %A Shamin Kinathil %A Scott Sanner %A Nicolás Della Penna %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-kinathil14a %I PMLR %P 823--832 %U https://proceedings.mlr.press/r12/kinathil14a.html %V R12 %X Zero-sum stochastic games provide a formalism to study competitive sequential interactions between two agents with diametrically opposing goals and evolving state. A solution to such games with discrete state was presented by Littman (Littman, 1994). The continuous state version of this game remains unsolved. In many instances continuous state solutions require non-linear optimisation, a problem for which closed-form solutions are generally unavailable. We present an exact closed-form solution to a sub-class of zero-sum continuous stochastic games that can be solved as a parameterised linear program by utilising symbolic dynamic programming. This novel technique is applied to calculate exact solutions to a variety of zero-sum continuous state stochastic games. %Z Reissued by PMLR on 04 October 2026.
APA
Kinathil, S., Sanner, S. & Della Penna, N.. (2014). Closed-form Solutions to a Subclass of Continuous Stochastic Games via Symbolic Dynamic Programming. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:823-832 Available from https://proceedings.mlr.press/r12/kinathil14a.html. Reissued by PMLR on 04 October 2026.

Related Material