---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Filip
foaf_name: Cano, Filip
foaf_surname: Cano
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-2985-7724
- foaf_Person:
foaf_givenName: Bettina
foaf_name: Könighofer, Bettina
foaf_surname: Könighofer
- foaf_Person:
foaf_givenName: Konstantin
foaf_name: Kueffner, Konstantin
foaf_surname: Kueffner
foaf_workInfoHomepage: http://www.librecat.org/personId=8121a2d0-dc85-11ea-9058-af578f3b4515
orcid: 0000-0001-8974-2542
- foaf_Person:
foaf_givenName: Kaushik
foaf_name: Mallik, Kaushik
foaf_surname: Mallik
foaf_workInfoHomepage: http://www.librecat.org/personId=0834ff3c-6d72-11ec-94e0-b5b0a4fb8598
orcid: 0000-0001-9864-7475
bibo_doi: 10.4230/LIPIcs.FSCD.2024.2
bibo_volume: 299
dct_date: 2024^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/9783959773232
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Abstraction-based decision making for statistical properties@
...