Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming

Shamin Kinathil; Scott Sanner; Nicolás Della Penna

Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming

Shamin Kinathil, Scott Sanner, Nicolás Della Penna

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 nonlinear optimisation, a problem for which closedform solutions are generally unavailable. We present an exact closed-form solution to a subclass 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.

Original language	English
Title of host publication	Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014
Editors	Nevin L. Zhang, Jin Tian
Publisher	AUAI Press
Pages	390-399
Number of pages	10
ISBN (Electronic)	9780974903910
Publication status	Published - 2014
Event	30th Conference on Uncertainty in Artificial Intelligence, UAI 2014 - Quebec City, Canada Duration: 23 Jul 2014 → 27 Jul 2014

Publication series

Name	Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014

Conference

Conference	30th Conference on Uncertainty in Artificial Intelligence, UAI 2014
Country/Territory	Canada
City	Quebec City
Period	23/07/14 → 27/07/14

Cite this

Kinathil, S., Sanner, S., & Penna, N. D. (2014). Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming. In N. L. Zhang, & J. Tian (Eds.), Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014 (pp. 390-399). (Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014). AUAI Press.

Kinathil, Shamin ; Sanner, Scott ; Penna, Nicolás Della. / Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming. Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014. editor / Nevin L. Zhang ; Jin Tian. AUAI Press, 2014. pp. 390-399 (Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014).

@inproceedings{54bb68d2e7fc4d07b818515c12d6e899,

title = "Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming",

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 nonlinear optimisation, a problem for which closedform solutions are generally unavailable. We present an exact closed-form solution to a subclass 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.",

author = "Shamin Kinathil and Scott Sanner and Penna, {Nicol{\'a}s Della}",

year = "2014",

language = "English",

series = "Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014",

publisher = "AUAI Press",

pages = "390--399",

editor = "Zhang, {Nevin L.} and Jin Tian",

booktitle = "Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014",

note = "30th Conference on Uncertainty in Artificial Intelligence, UAI 2014 ; Conference date: 23-07-2014 Through 27-07-2014",

}

Kinathil, S, Sanner, S & Penna, ND 2014, Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming. in NL Zhang & J Tian (eds), Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014. Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014, AUAI Press, pp. 390-399, 30th Conference on Uncertainty in Artificial Intelligence, UAI 2014, Quebec City, Canada, 23/07/14.

Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming. / Kinathil, Shamin; Sanner, Scott; Penna, Nicolás Della.
Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014. ed. / Nevin L. Zhang; Jin Tian. AUAI Press, 2014. p. 390-399 (Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming

AU - Kinathil, Shamin

AU - Sanner, Scott

AU - Penna, Nicolás Della

PY - 2014

Y1 - 2014

N2 - 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 nonlinear optimisation, a problem for which closedform solutions are generally unavailable. We present an exact closed-form solution to a subclass 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.

AB - 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 nonlinear optimisation, a problem for which closedform solutions are generally unavailable. We present an exact closed-form solution to a subclass 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.

UR - http://www.scopus.com/inward/record.url?scp=84923306244&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84923306244

T3 - Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014

SP - 390

EP - 399

BT - Uncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014

A2 - Zhang, Nevin L.

A2 - Tian, Jin

PB - AUAI Press

T2 - 30th Conference on Uncertainty in Artificial Intelligence, UAI 2014

Y2 - 23 July 2014 through 27 July 2014

ER -

Closed-form solutions to a subclass of continuous stochastic games via symbolic dynamic programming

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this