Gradient-Descent for Randomized Controllers Under Partial Observability

Linus Heck; Jip Spel; Sebastian Junges; Joshua Moerman; Joost-Pieter Katoen

doi:10.1007/978-3-030-94583-1_7

Gradient-Descent for Randomized Controllers Under Partial Observability

Linus Heck, Jip Spel, Sebastian Junges, Joshua Moerman, Joost-Pieter Katoen

Department of Computer Science

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

Abstract

Randomization is a powerful technique to create robust controllers, in particular in partially observable settings. The degrees of randomization have a significant impact on the system performance, yet they are intricate to get right. The use of synthesis algorithms for parametric Markov chains (pMCs) is a promising direction to support the design process of such controllers. This paper shows how to define and evaluate gradients of pMCs. Furthermore, it investigates varieties of gradient descent techniques from the machine learning community to synthesize the probabilities in a pMC. The resulting method scales to significantly larger pMCs than before and empirically outperforms the state-of-the-art, often by at least one order of magnitude.

Original language	English
Title of host publication	Verification, model Checking, and Abstract Interpretation
Subtitle of host publication	23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings
Editors	Bernd Finkbeiner, Thomas Wies
Publisher	Springer
Pages	127-150
Number of pages	24
Edition	1
ISBN (Electronic)	9783030945831
ISBN (Print)	9783030945824
DOIs	https://doi.org/10.1007/978-3-030-94583-1_7
Publication status	Published - 2022
Event	The 23rd international conference Verification, Model Checking, and Abstract Interpretation - Philadelphia, United States Duration: 16 Jan 2022 → 18 Jan 2022 Conference number: 23 https://popl22.sigplan.org/home/VMCAI-2022 https://link.springer.com/book/10.1007/978-3-030-94583-1

Publication series

Series	Lecture Notes in Computer Science
Volume	13182
ISSN	0302-9743

Series	Theoretical Computer Science and General Issues (LNCS subseries)
Volume	13182

Conference

Conference	The 23rd international conference Verification, Model Checking, and Abstract Interpretation
Abbreviated title	VMCAI 2022
Country/Territory	United States
City	Philadelphia
Period	16/01/22 → 18/01/22
Internet address	https://popl22.sigplan.org/home/VMCAI-2022 https://link.springer.com/book/10.1007/978-3-030-94583-1

Access to Document

10.1007/978-3-030-94583-1_7

Cite this

Heck, L., Spel, J., Junges, S., Moerman, J., & Katoen, J.-P. (2022). Gradient-Descent for Randomized Controllers Under Partial Observability. In B. Finkbeiner, & T. Wies (Eds.), Verification, model Checking, and Abstract Interpretation: 23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings (1 ed., pp. 127-150). Springer. https://doi.org/10.1007/978-3-030-94583-1_7

Heck, Linus ; Spel, Jip ; Junges, Sebastian et al. / Gradient-Descent for Randomized Controllers Under Partial Observability. Verification, model Checking, and Abstract Interpretation: 23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings. editor / Bernd Finkbeiner ; Thomas Wies. 1. ed. Springer, 2022. pp. 127-150 (Lecture Notes in Computer Science, Vol. 13182). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 13182).

@inproceedings{ea797d31e9984cedace8806ea680b42b,

title = "Gradient-Descent for Randomized Controllers Under Partial Observability",

abstract = "Randomization is a powerful technique to create robust controllers, in particular in partially observable settings. The degrees of randomization have a significant impact on the system performance, yet they are intricate to get right. The use of synthesis algorithms for parametric Markov chains (pMCs) is a promising direction to support the design process of such controllers. This paper shows how to define and evaluate gradients of pMCs. Furthermore, it investigates varieties of gradient descent techniques from the machine learning community to synthesize the probabilities in a pMC. The resulting method scales to significantly larger pMCs than before and empirically outperforms the state-of-the-art, often by at least one order of magnitude.",

author = "Linus Heck and Jip Spel and Sebastian Junges and Joshua Moerman and Joost-Pieter Katoen",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; The 23rd international conference Verification, Model Checking, and Abstract Interpretation, VMCAI 2022 ; Conference date: 16-01-2022 Through 18-01-2022",

year = "2022",

doi = "10.1007/978-3-030-94583-1_7",

language = "English",

isbn = "9783030945824",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "127--150",

editor = "Bernd Finkbeiner and Thomas Wies",

booktitle = "Verification, model Checking, and Abstract Interpretation",

edition = "1",

url = "https://popl22.sigplan.org/home/VMCAI-2022, https://link.springer.com/book/10.1007/978-3-030-94583-1",

}

Heck, L, Spel, J, Junges, S, Moerman, J & Katoen, J-P 2022, Gradient-Descent for Randomized Controllers Under Partial Observability. in B Finkbeiner & T Wies (eds), Verification, model Checking, and Abstract Interpretation: 23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings. 1 edn, Springer, Lecture Notes in Computer Science, vol. 13182, Theoretical Computer Science and General Issues (LNCS subseries), vol. 13182, pp. 127-150, The 23rd international conference Verification, Model Checking, and Abstract Interpretation, Philadelphia, Pennsylvania, United States, 16/01/22. https://doi.org/10.1007/978-3-030-94583-1_7

Gradient-Descent for Randomized Controllers Under Partial Observability. / Heck, Linus; Spel, Jip; Junges, Sebastian et al.
Verification, model Checking, and Abstract Interpretation: 23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings. ed. / Bernd Finkbeiner; Thomas Wies. 1. ed. Springer, 2022. p. 127-150 (Lecture Notes in Computer Science, Vol. 13182). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 13182).

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

TY - GEN

T1 - Gradient-Descent for Randomized Controllers Under Partial Observability

AU - Heck, Linus

AU - Spel, Jip

AU - Junges, Sebastian

AU - Moerman, Joshua

AU - Katoen, Joost-Pieter

N1 - Conference code: 23

PY - 2022

Y1 - 2022

N2 - Randomization is a powerful technique to create robust controllers, in particular in partially observable settings. The degrees of randomization have a significant impact on the system performance, yet they are intricate to get right. The use of synthesis algorithms for parametric Markov chains (pMCs) is a promising direction to support the design process of such controllers. This paper shows how to define and evaluate gradients of pMCs. Furthermore, it investigates varieties of gradient descent techniques from the machine learning community to synthesize the probabilities in a pMC. The resulting method scales to significantly larger pMCs than before and empirically outperforms the state-of-the-art, often by at least one order of magnitude.

AB - Randomization is a powerful technique to create robust controllers, in particular in partially observable settings. The degrees of randomization have a significant impact on the system performance, yet they are intricate to get right. The use of synthesis algorithms for parametric Markov chains (pMCs) is a promising direction to support the design process of such controllers. This paper shows how to define and evaluate gradients of pMCs. Furthermore, it investigates varieties of gradient descent techniques from the machine learning community to synthesize the probabilities in a pMC. The resulting method scales to significantly larger pMCs than before and empirically outperforms the state-of-the-art, often by at least one order of magnitude.

U2 - 10.1007/978-3-030-94583-1_7

DO - 10.1007/978-3-030-94583-1_7

M3 - Conference Article in proceeding

SN - 9783030945824

T3 - Lecture Notes in Computer Science

SP - 127

EP - 150

BT - Verification, model Checking, and Abstract Interpretation

A2 - Finkbeiner, Bernd

A2 - Wies, Thomas

PB - Springer

T2 - The 23rd international conference Verification, Model Checking, and Abstract Interpretation

Y2 - 16 January 2022 through 18 January 2022

ER -

Heck L, Spel J, Junges S, Moerman J, Katoen JP. Gradient-Descent for Randomized Controllers Under Partial Observability. In Finkbeiner B, Wies T, editors, Verification, model Checking, and Abstract Interpretation: 23rd International Conference, VMCAI 2022 Philadelphia, PA, USA, January 16–18, 2022 Proceedings. 1 ed. Springer. 2022. p. 127-150. (Lecture Notes in Computer Science, Vol. 13182). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 13182). doi: 10.1007/978-3-030-94583-1_7

Gradient-Descent for Randomized Controllers Under Partial Observability

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this