Title




Learningbased meanpayoff optimization in an unknown MDP under omegaregular constraints


Author






Abstract




We formalize the problem of maximizing the meanpayoff 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 meanpayoff objectives can be achieved depending on how much memory one is willing to use. (i) For all epsilon and gamma we can construct an onlinelearning finitememory strategy that almostsurely satisfies the parity objective and which achieves an epsilonoptimal mean payoff with probability at least 1  gamma. (ii) Alternatively, for all epsilon and gamma there exists an onlinelearning infinitememory strategy that satisfies the parity objective surely and which achieves an epsilonoptimal 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. 


Language




English


Source (journal)




LIPIcs : Leibniz International Proceedings in Informatics.  Place of publication unknown


Source (book)




29th International Conference on Concurrency Theory (CONCUR 2018) / Schewe, Sven [edit.]; et al.


Publication




Germany
:
Schloss Dagstuhl, LeibnizZentrum fuer Informatik
,
2018


ISSN




18688969


ISBN




9783959770873


DOI




10.4230/LIPICS.CONCUR.2018.8


Volume/pages




118
(2018)
, 18 p.


Article Reference




8


Medium




Eonly publicatie


Full text (Publisher's DOI)






Full text (open access)





