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

The fixed-horizon constrained Markov Decision Process (C-MDP) is a well-knownmodel for planning in stochastic environments under operating constraints.Chance-Constrained MDP (CC-MDP) is a variant that allows bounding theprobability of constraint violation, which is desired in many safety-criticalapplications. CC-MDP can also model a class of MDPs, called Stochastic ShortestPath (SSP), under dead-ends, where there is a trade-off between theprobability-to-goal and cost-to-goal. This work studies the structure of(C)C-MDP, particularly an important variant that involves local transition. Inthis variant, the state reachability exhibits a certain degree of locality andindependence from the remaining states. More precisely, the number of states,at a given time, that share some reachable future states is always constant.(C)C-MDP under local transition is NP-Hard even for a planning horizon of two.In this work, we propose a fully polynomial-time approximation scheme for(C)C-MDP that computes (near) optimal deterministic policies. Such an algorithmis among the best approximation algorithm attainable in theory and givesinsights into the approximability of constrained MDP and its variants.

A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions