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

We study the sample complexity of learning an $\varepsilon$-optimal policy inan average-reward Markov decision process (MDP) under a generative model. Weestablish the complexity bound $\widetilde{O}\left(SA\frac{H}{\varepsilon^2}\right)$, where $H$ is the span of the bias function of the optimal policy and$SA$ is the cardinality of the state-action space. Our result is the first thatis minimax optimal (up to log factors) in all parameters $S,A,H$ and$\varepsilon$, improving on existing work that either assumes uniformly boundedmixing times for all policies or has suboptimal dependence on the parameters.  Our result is based on reducing the average-reward MDP to a discounted MDP.To establish the optimality of this reduction, we develop improved bounds for$\gamma$-discounted MDPs, showing that$\widetilde{O}\left(SA\frac{H}{(1-\gamma)^2\varepsilon^2} \right)$ samplessuffice to learn a $\varepsilon$-optimal policy in weakly communicating MDPsunder the regime that $\gamma \geq 1 - \frac{1}{H}$, circumventing thewell-known lower bound of$\widetilde{\Omega}\left(SA\frac{1}{(1-\gamma)^3\varepsilon^2} \right)$ forgeneral $\gamma$-discounted MDPs. Our analysis develops upper bounds on certaininstance-dependent variance parameters in terms of the span parameter. Thesebounds are tighter than those based on the mixing time or diameter of the MDPand may be of broader use.

Span-Based Optimal Sample Complexity for Average Reward MDPs