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

We introduce two new no-regret algorithms for the stochastic shortest path(SSP) problem with a linear MDP that significantly improve over the onlyexisting results of (Vial et al., 2021). Our first algorithm is computationallyefficient and achieves a regret bound$\widetilde{O}\left(\sqrt{d^3B_{\star}^2T_{\star} K}\right)$, where $d$ is thedimension of the feature space, $B_{\star}$ and $T_{\star}$ are upper bounds ofthe expected costs and hitting time of the optimal policy respectively, and $K$is the number of episodes. The same algorithm with a slight modification alsoachieves logarithmic regret of order$O\left(\frac{d^3B_{\star}^4}{c_{\min}^2\text{gap}_{\min}}\ln^5\frac{dB_{\star}K}{c_{\min}} \right)$, where $\text{gap}_{\min}$ is the minimum sub-optimalitygap and $c_{\min}$ is the minimum cost over all state-action pairs. Our resultis obtained by developing a simpler and improved analysis for thefinite-horizon approximation of (Cohen et al., 2021) with a smallerapproximation error, which might be of independent interest. On the other hand,using variance-aware confidence sets in a global optimization problem, oursecond algorithm is computationally inefficient but achieves the first"horizon-free" regret bound $\widetilde{O}(d^{3.5}B_{\star}\sqrt{K})$ with nopolynomial dependency on $T_{\star}$ or $1/c_{\min}$, almost matching the$\Omega(dB_{\star}\sqrt{K})$ lower bound from (Min et al., 2021).

Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP