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

Episodic reinforcement learning and contextual bandits are two widely studiedsequential decision-making problems. Episodic reinforcement learninggeneralizes contextual bandits and is often perceived to be more difficult dueto long planning horizon and unknown state-dependent transitions. The currentpaper shows that the long planning horizon and the unknown state-dependenttransitions (at most) pose little additional difficulty on sample complexity.  We consider the episodic reinforcement learning with $S$ states, $A$ actions,planning horizon $H$, total reward bounded by $1$, and the agent plays for $K$episodes. We propose a new algorithm, \textbf{M}onotonic \textbf{V}alue\textbf{P}ropagation (MVP), which relies on a new Bernstein-type bonus.Compared to existing bonus constructions, the new bonus is tighter since it isbased on a well-designed monotonic value function. In particular, the\emph{constants} in the bonus should be subtly setting to ensure optimism andmonotonicity.  We show MVP enjoys an $O\left(\left(\sqrt{SAK} + S^2A\right) \poly\log\left(SAHK\right)\right)$ regret, approaching the$\Omega\left(\sqrt{SAK}\right)$ lower bound of \emph{contextual bandits} up tologarithmic terms. Notably, this result 1) \emph{exponentially} improves thestate-of-the-art polynomial-time algorithms by Dann et al. [2019] and Zanetteet al. [2019] in terms of the dependency on $H$, and 2) \emph{exponentially}improves the running time in [Wang et al. 2020] and significantly improves thedependency on $S$, $A$ and $K$ in sample complexity.

Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon