Learning-Based Mean-Payoff Optimization in an Unknown MDP under
Omega-Regular Constraints

D 2018

Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints

KŘETÍNSKÝ, Jan, Guillermo PEREZ a Jean-Francois RASKIN

Základní údaje

Originální název

Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints

Autoři

KŘETÍNSKÝ, Jan (203 Česká republika, garant, domácí), Guillermo PEREZ (188 Kostarika) a Jean-Francois RASKIN (56 Belgie)

Vydání

Dagstuhl, 29th International Conference on Concurrency Theory (CONCUR 2018), od s. 1-18, 18 s. 2018

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00108291

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-087-3

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.8

Klíčová slova anglicky

Learning; Mean-Payoff; Markov decision process; Omega-Regular Specification

Štítky

core_A, firank_A

Změněno: 27. 4. 2020 23:49, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We formalize the problem of maximizing the mean-payoff value with high probability while satisfying a parity objective in a Markov decision process (MDP) with unknown probabilistic transition function and unknown reward function. Assuming the support of the unknown transition function and a lower bound on the minimal transition probability are known in advance, we show that in MDPs consisting of a single end component, two combinations of guarantees on the parity and mean-payoff objectives can be achieved depending on how much memory one is willing to use. (i) For all epsilon and gamma we can construct an online-learning finite-memory strategy that almost-surely satisfies the parity objective and which achieves an epsilon-optimal mean payoff with probability at least 1 - gamma. (ii) Alternatively, for all epsilon and gamma there exists an online-learning infinite-memory strategy that satisfies the parity objective surely and which achieves an epsilon-optimal mean payoff with probability at least 1 - gamma. We extend the above results to MDPs consisting of more than one end component in a natural way. Finally, we show that the aforementioned guarantees are tight, i.e. there are MDPs for which stronger combinations of the guarantees cannot be ensured.

Návaznosti

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Citovat

KŘETÍNSKÝ, Jan, Guillermo PEREZ a Jean-Francois RASKIN. Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints. Online. In 29th International Conference on Concurrency Theory (CONCUR 2018). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, s. 1-18. ISBN 978-3-95977-087-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.8.

@inproceedings{1649044,
   author = {Křetínský, Jan and Perez, Guillermo and Raskin, JeanandFrancois},
   address = {Dagstuhl},
   booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.8},
   keywords = {Learning; Mean-Payoff; Markov decision process; Omega-Regular Specification},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-087-3},
   pages = {1-18},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
   title = {Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints},
   year = {2018}
}

TY  - JOUR
ID  - 1649044
AU  - Křetínský, Jan - Perez, Guillermo - Raskin, Jean-Francois
PY  - 2018
TI  - Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY  - Dagstuhl
SN  - 9783959770873
KW  - Learning
KW  - Mean-Payoff
KW  - Markov decision process
KW  - Omega-Regular Specification
N2  - We formalize the problem of maximizing the mean-payoff value with high probability while satisfying a parity objective in a Markov decision process (MDP) with unknown probabilistic transition function and unknown reward function. Assuming the support of the unknown transition function and a lower bound on the minimal transition probability are known in advance, we show that in MDPs consisting of a single end component, two combinations of guarantees on the parity and mean-payoff objectives can be achieved depending on how much memory one is willing to use. (i) For all epsilon and gamma we can construct an online-learning finite-memory strategy that almost-surely satisfies the parity objective and which achieves an epsilon-optimal mean payoff with probability at least 1 - gamma. (ii) Alternatively, for all epsilon and gamma there exists an online-learning infinite-memory strategy that satisfies the parity objective surely and which achieves an epsilon-optimal mean payoff with probability at least 1 - gamma. We extend the above results to MDPs consisting of more than one end component in a natural way. Finally, we show that the aforementioned guarantees are tight, i.e. there are MDPs for which stronger combinations of the guarantees cannot be ensured.
ER  -

KŘETÍNSKÝ, Jan, Guillermo PEREZ a Jean-Francois RASKIN. Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints. Online. In \textit{29th International Conference on Concurrency Theory (CONCUR 2018)}. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, s.~1-18. ISBN~978-3-95977-087-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.8.

Podrobný výpis o publikaci