Conference item
Stochastic best-effort strategies for Borel goals
- Abstract:
- We study reactive systems with Borel goals operating in a possibly non-Markovian stochastic environment. Moreover, the specific environment is not known, only its support is, i.e., at each step one knows which transitions are possible and which are impossible, but the probability distribution amongst the possible transitions is unknown. We consider system strategies that are maximal in the dominance order, i.e., no other strategy achieves the goal with at least the same probability in all environments, and with a higher probability in some environment. We call such strategies "stochastic best-effort". We prove the very general result that stochastic best-effort strategies exist for any Borel goal. We do this by providing local characterizations in terms of a three-valued abstraction of the probability of achieving the goal at a history. The correctness of the characterization is shown using a version of the Lebesgue Density Theorem from geometric measure theory. On the more practical side, we consider goals given in linear temporal logic. We establish the computational complexity of synthesizing a stochastic best-effort strategy, and show that it is not harder than synthesizing an optimal strategy in a domain with fixed known probabilities.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 425.9KB, Terms of use)
-
- Publisher copy:
- 10.1109/LICS56636.2023.10175747
Authors
- Publisher:
- IEEE
- Host title:
- 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Publication date:
- 2023-07-14
- Acceptance date:
- 2023-04-05
- Event title:
- 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
- Event location:
- Boston, Massachusetts, USA
- Event website:
- https://lics.siglog.org/lics23/
- Event start date:
- 2023-06-26
- Event end date:
- 2023-06-29
- DOI:
- ISSN:
-
1043-6871
- EISBN:
- 9798350335873
- ISBN:
- 9798350335880
- Language:
-
English
- Keywords:
- Pubs id:
-
1515180
- Local pid:
-
pubs:1515180
- Deposit date:
-
2024-04-14
Terms of use
- Copyright holder:
- IEEE
- Copyright date:
- 2023
- Rights statement:
- © 2023 IEEE.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from IEEE at https://dx.doi.org/10.1109/LICS56636.2023.10175747
If you are the owner of this record, you can report an update to it here: Report update to this record