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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we settle the sampling complexity of solving discountedtwo-player turn-based zero-sum stochastic games up to polylogarithmic factors.Given a stochastic game with discount factor $\gamma\in(0,1)$ we provide analgorithm that computes an $\epsilon$-optimal strategy with high-probabilitygiven $\tilde{O}((1 - \gamma)^{-3} \epsilon^{-2})$ samples from the transitionfunction for each state-action-pair. Our algorithm runs in time nearly linearin the number of samples and uses space nearly linear in the number ofstate-action pairs. As stochastic games generalize Markov decision processes(MDPs) our runtime and sample complexities are optimal due to Azar et al(2013). We achieve our results by showing how to generalize a near-optimalQ-learning based algorithms for MDP, in particular Sidford et al (2018), totwo-player strategy computation algorithms. This overcomes limitations ofstandard Q-learning and strategy iteration or alternating minimization basedapproaches and we hope will pave the way for future reinforcement learningresults by facilitating the extension of MDP results to multi-agent settingswith little loss.

Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity