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 problem of learning in the stochastic shortest path (SSP)setting, where an agent seeks to minimize the expected cost accumulated beforereaching a goal state. We design a novel model-based algorithm EB-SSP thatcarefully skews the empirical transitions and perturbs the empirical costs withan exploration bonus to induce an optimistic SSP problem whose associated valueiteration scheme is guaranteed to converge. We prove that EB-SSP achieves theminimax regret rate $\tilde{O}(B_{\star} \sqrt{S A K})$, where $K$ is thenumber of episodes, $S$ is the number of states, $A$ is the number of actions,and $B_{\star}$ bounds the expected cumulative cost of the optimal policy fromany state, thus closing the gap with the lower bound. Interestingly, EB-SSPobtains this result while being parameter-free, i.e., it does not require anyprior knowledge of $B_{\star}$, nor of $T_{\star}$, which bounds the expectedtime-to-goal of the optimal policy from any state. Furthermore, we illustratevarious cases (e.g., positive costs, or general costs when an order-accurateestimate of $T_{\star}$ is available) where the regret only contains alogarithmic dependence on $T_{\star}$, thus yielding the first (nearly)horizon-free regret bound beyond the finite-horizon MDP setting.

Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret