English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Markov decision processes (MDPs) provide a standard framework for sequentialdecision making under uncertainty. However, transition probabilities in MDPsare often estimated from data and MDPs do not take data uncertainty intoaccount. Robust Markov decision processes (RMDPs) address this shortcoming ofMDPs by assigning to each transition an uncertainty set rather than a singleprobability value. The goal of solving RMDPs is then to find a policy whichmaximizes the worst-case performance over the uncertainty sets. In this work,we consider polytopic RMDPs in which all uncertainty sets are polytopes andstudy the problem of solving long-run average reward polytopic RMDPs. Our focusis on computational complexity aspects and efficient algorithms. We present anovel perspective on this problem and show that it can be reduced to solvinglong-run average reward turn-based stochastic games with finite state andaction spaces. This reduction allows us to derive several importantconsequences that were hitherto not known to hold for polytopic RMDPs. First,we derive new computational complexity bounds for solving long-run averagereward polytopic RMDPs, showing for the first time that the threshold decisionproblem for them is in NP coNP and that they admit a randomized algorithm withsub-exponential expected runtime. Second, we present Robust Polytopic PolicyIteration (RPPI), a novel policy iteration algorithm for solving long-runaverage reward polytopic RMDPs. Our experimental evaluation shows that RPPI ismuch more efficient in solving long-run average reward polytopic RMDPs comparedto state-of-the-art methods based on value iteration.

Solving Long-run Average Reward Robust MDPs via Stochastic Games