Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications

Wen, Min; Topcu, Ufuk

Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3630-3635.

Abstract

We consider a controller synthesis problem in turn-based stochastic games with both a qualitative linear temporal logic (LTL) constraint and a quantitative discounted-sum objective. For each case in which the LTL specification is realizable and can be equivalently transformed into a deterministic Buchi automaton, we show that there always exists a memoryless almost-sure winning strategy that is epsilon-optimal with respect to the discounted-sum objective for any arbitrary positive epsilon. Building on the idea of the R-MAX algorithm, we propose a probably approximately correct (PAC) learning algorithm that can learn such a strategy efficiently in an online manner with a-priori unknown reward functions and unknown transition distributions. To the best of our knowledge, this is the first result on PAC learning in stochastic games with independent quantitative and qualitative objectives.

Min Wen, and Ufuk Topcu. 2016. Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3630–3635. https://ijcai.org/proceedings/2016/511

@inproceedings{ijcai2016p511,
  title     = {Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications},
  author    = {Wen, Min and Topcu, Ufuk},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {3630--3635},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/511},
}

TY  - CPAPER
TI  - Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications
AU  - Wen, Min
AU  - Topcu, Ufuk
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 3630
EP  - 3635
UR  - https://ijcai.org/proceedings/2016/511
ER  -