Model-Free Reinforcement Learning for Branching Markov Decision Processes

Ernst Moritz Hahn; Mateo Perez; Sven Schewe; Fabio Somenzi; Ashutosh Trivedi; Dominik Wojtczak

doi:10.1007/978-3-030-81688-9_30

Model-Free Reinforcement Learning for Branching Markov Decision Processes

Ernst Moritz Hahn
, Mateo Perez
, Sven Schewe
, Fabio Somenzi
, Ashutosh Trivedi
, Dominik Wojtczak

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

3 Citations (Scopus)

93 Downloads (Pure)

Abstract

We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collection of entities of various types that, while spawning other entities, generate a payoff. In comparison with BMCs, where the evolution of a each entity of the same type follows the same probabilistic pattern, BMDPs allow an external controller to pick from a range of options. This permits us to study the best/worst behaviour of the system. We generalise model-free reinforcement learning techniques to compute an optimal control strategy of an unknown BMDP in the limit. We present results of an implementation that demonstrate the practicality of the approach.

Original language	English
Title of host publication	Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II
Editors	Alexandra Silva, K. Rustan M. Leino
Publisher	Springer
Pages	651-673
Number of pages	23
DOIs	https://doi.org/10.1007/978-3-030-81688-9_30
Publication status	Published - 15 Jul 2021
Event	33rd International Conference on Computer Aided Verification, CAV 2021 - Virtual Event Duration: 20 Jul 2021 → 23 Jul 2021 Conference number: 33

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12760

Conference

Conference	33rd International Conference on Computer Aided Verification, CAV 2021
Abbreviated title	CAV 2021
City	Virtual Event
Period	20/07/21 → 23/07/21

Access to Document

10.1007/978-3-030-81688-9_30Licence: CC BY

Hahn2021_Chapter_Model-FreeReinforcementLearninFinal published version, 510 KBLicence: CC BY

Cite this

Hahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., & Wojtczak, D. (2021). Model-Free Reinforcement Learning for Branching Markov Decision Processes. In A. Silva, & K. R. M. Leino (Eds.), Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II (pp. 651-673). (Lecture Notes in Computer Science; Vol. 12760). Springer. https://doi.org/10.1007/978-3-030-81688-9_30

Hahn, Ernst Moritz ; Perez, Mateo ; Schewe, Sven et al. / Model-Free Reinforcement Learning for Branching Markov Decision Processes. Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II. editor / Alexandra Silva ; K. Rustan M. Leino. Springer, 2021. pp. 651-673 (Lecture Notes in Computer Science).

@inproceedings{4352f483262042d0b04c890952ca55fd,

title = "Model-Free Reinforcement Learning for Branching Markov Decision Processes",

abstract = "We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collection of entities of various types that, while spawning other entities, generate a payoff. In comparison with BMCs, where the evolution of a each entity of the same type follows the same probabilistic pattern, BMDPs allow an external controller to pick from a range of options. This permits us to study the best/worst behaviour of the system. We generalise model-free reinforcement learning techniques to compute an optimal control strategy of an unknown BMDP in the limit. We present results of an implementation that demonstrate the practicality of the approach.",

author = "Hahn, \{Ernst Moritz\} and Mateo Perez and Sven Schewe and Fabio Somenzi and Ashutosh Trivedi and Dominik Wojtczak",

year = "2021",

month = jul,

day = "15",

doi = "10.1007/978-3-030-81688-9\_30",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "651--673",

editor = "Alexandra Silva and Leino, \{K. Rustan M.\}",

booktitle = "Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II",

address = "Germany",

note = "33rd International Conference on Computer Aided Verification, CAV 2021, CAV 2021 ; Conference date: 20-07-2021 Through 23-07-2021",

}

Hahn, EM, Perez, M, Schewe, S, Somenzi, F, Trivedi, A & Wojtczak, D 2021, Model-Free Reinforcement Learning for Branching Markov Decision Processes. in A Silva & KRM Leino (eds), Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II. Lecture Notes in Computer Science, vol. 12760, Springer, pp. 651-673, 33rd International Conference on Computer Aided Verification, CAV 2021, Virtual Event, 20/07/21. https://doi.org/10.1007/978-3-030-81688-9_30

Model-Free Reinforcement Learning for Branching Markov Decision Processes. / Hahn, Ernst Moritz; Perez, Mateo; Schewe, Sven et al.
Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II. ed. / Alexandra Silva; K. Rustan M. Leino. Springer, 2021. p. 651-673 (Lecture Notes in Computer Science; Vol. 12760).

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

TY - GEN

T1 - Model-Free Reinforcement Learning for Branching Markov Decision Processes

AU - Hahn, Ernst Moritz

AU - Perez, Mateo

AU - Schewe, Sven

AU - Somenzi, Fabio

AU - Trivedi, Ashutosh

AU - Wojtczak, Dominik

N1 - Conference code: 33

PY - 2021/7/15

Y1 - 2021/7/15

N2 - We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collection of entities of various types that, while spawning other entities, generate a payoff. In comparison with BMCs, where the evolution of a each entity of the same type follows the same probabilistic pattern, BMDPs allow an external controller to pick from a range of options. This permits us to study the best/worst behaviour of the system. We generalise model-free reinforcement learning techniques to compute an optimal control strategy of an unknown BMDP in the limit. We present results of an implementation that demonstrate the practicality of the approach.

AB - We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collection of entities of various types that, while spawning other entities, generate a payoff. In comparison with BMCs, where the evolution of a each entity of the same type follows the same probabilistic pattern, BMDPs allow an external controller to pick from a range of options. This permits us to study the best/worst behaviour of the system. We generalise model-free reinforcement learning techniques to compute an optimal control strategy of an unknown BMDP in the limit. We present results of an implementation that demonstrate the practicality of the approach.

U2 - 10.1007/978-3-030-81688-9_30

DO - 10.1007/978-3-030-81688-9_30

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 651

EP - 673

BT - Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II

A2 - Silva, Alexandra

A2 - Leino, K. Rustan M.

PB - Springer

T2 - 33rd International Conference on Computer Aided Verification, CAV 2021

Y2 - 20 July 2021 through 23 July 2021

ER -

Hahn EM, Perez M, Schewe S, Somenzi F, Trivedi A, Wojtczak D. Model-Free Reinforcement Learning for Branching Markov Decision Processes. In Silva A, Leino KRM, editors, Computer Aided Verification - 33rd International Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II. Springer. 2021. p. 651-673. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-81688-9_30

Model-Free Reinforcement Learning for Branching Markov Decision Processes

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this