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 $\epsilon$-optimal policy inthe Stochastic Shortest Path (SSP) problem. We first derive sample complexitybounds when the learner has access to a generative model. We show that thereexists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost$c_{\min}$, and maximum expected cost of the optimal policy over all states$B_{\star}$, where any algorithm requires at least$\Omega(SAB_{\star}^3/(c_{\min}\epsilon^2))$ samples to return an$\epsilon$-optimal policy with high probability. Surprisingly, this impliesthat whenever $c_{\min}=0$ an SSP problem may not be learnable, thus revealingthat learning in SSPs is strictly harder than in the finite-horizon anddiscounted settings. We complement this result with lower bounds when priorknowledge of the hitting time of the optimal policy is available and when werestrict optimality by competing against policies with bounded hitting time.Finally, we design an algorithm with matching upper bounds in these cases. Thissettles the sample complexity of learning $\epsilon$-optimal polices in SSPwith generative models.  We also initiate the study of learning $\epsilon$-optimal policies withoutaccess to a generative model (i.e., the so-called best-policy identificationproblem), and show that sample-efficient learning is impossible in general. Onthe other hand, efficient learning can be made possible if we assume the agentcan directly reach the goal state from any state by paying a fixed cost. Wethen establish the first upper and lower bounds under this assumption.  Finally, using similar analytic tools, we prove that horizon-free regret isimpossible in SSPs under general costs, resolving an open problem in(Tarbouriech et al., 2021c).

Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path