Abstraction-based decision making for statistical properties

Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. 2024. Abstraction-based decision making for statistical properties. 9th International Conference on Formal Structures for Computation and Deduction. FSCD: Conference on Formal Structures for Computation and Deduction, LIPIcs, vol. 299, 2.

Download
OA 2024_LIPICs_Cano.pdf 1.39 MB [Published Version]

Conference Paper | Published | English

Scopus indexed
Author

Corresponding author has ISTA affiliation

Series Title
LIPIcs
Abstract
Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service.
Publishing Year
Date Published
2024-07-01
Proceedings Title
9th International Conference on Formal Structures for Computation and Deduction
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
This work is partly supported by the European Research Council under Grant No.: ERC2020-AdG 101020093. It is also partially supported by the State Government of Styria, Austria – Department Zukunftsfonds Steiermark.
Volume
299
Article Number
2
Conference
FSCD: Conference on Formal Structures for Computation and Deduction
Conference Location
Tallinn, Estonia
Conference Date
2024-07-10 – 2024-07-13
ISSN
IST-REx-ID

Cite this

Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. Abstraction-based decision making for statistical properties. In: 9th International Conference on Formal Structures for Computation and Deduction. Vol 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.FSCD.2024.2
Cano, F., Henzinger, T. A., Könighofer, B., Kueffner, K., & Mallik, K. (2024). Abstraction-based decision making for statistical properties. In 9th International Conference on Formal Structures for Computation and Deduction (Vol. 299). Tallinn, Estonia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSCD.2024.2
Cano, Filip, Thomas A Henzinger, Bettina Könighofer, Konstantin Kueffner, and Kaushik Mallik. “Abstraction-Based Decision Making for Statistical Properties.” In 9th International Conference on Formal Structures for Computation and Deduction, Vol. 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSCD.2024.2.
F. Cano, T. A. Henzinger, B. Könighofer, K. Kueffner, and K. Mallik, “Abstraction-based decision making for statistical properties,” in 9th International Conference on Formal Structures for Computation and Deduction, Tallinn, Estonia, 2024, vol. 299.
Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. 2024. Abstraction-based decision making for statistical properties. 9th International Conference on Formal Structures for Computation and Deduction. FSCD: Conference on Formal Structures for Computation and Deduction, LIPIcs, vol. 299, 2.
Cano, Filip, et al. “Abstraction-Based Decision Making for Statistical Properties.” 9th International Conference on Formal Structures for Computation and Deduction, vol. 299, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSCD.2024.2.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2024-07-29
MD5 Checksum
cc6bb89be0eaa404a6ce019392cd293e


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search