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/

Zendy Plus

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

Zendy Tools

Zendy Open

Recently, Sidford, Wang, Wu and Ye (2018) developed an algorithm combiningvariance reduction techniques with value iteration to solve discounted Markovdecision processes. This algorithm has a sublinear complexity when the discountfactor is fixed. Here, we extend this approach to mean-payoff problems,including both Markov decision processes and perfect information zero-sumstochastic games. We obtain sublinear complexity bounds, assuming there is adistinguished state which is accessible from all initial states and for allpolicies. Our method is based on a reduction from the mean payoff problem tothe discounted problem by a Doob h-transform, combined with a deflationtechnique. The complexity analysis of this algorithm uses at the same time thetechniques developed by Sidford et al. in the discounted case and non-linearspectral theory techniques (Collatz-Wielandt characterization of theeigenvalue).

Solving Ergodic Markov Decision Processes and Perfect Information Zero-sum Stochastic Games by Variance Reduced Deflated Value Iteration