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

In this paper, we revisit the regret of undiscounted reinforcement learningin MDPs with a birth and death structure. Specifically, we consider acontrolled queue with impatient jobs and the main objective is to optimize atrade-off between energy consumption and user-perceived performance. Withinthis setting, the \emph{diameter} $D$ of the MDP is $\Omega(S^S)$, where $S$ isthe number of states. Therefore, the existing lower and upper bounds on theregret at time$T$, of order $O(\sqrt{DSAT})$ for MDPs with $S$ states and $A$actions, may suggest that reinforcement learning is inefficient here. In ourmain result however, we exploit the structure of our MDPs to show that theregret of a slightly-tweaked version of the classical learning algorithm {\scUcrl2} is in fact upper bounded by $\tilde{\mathcal{O}}(\sqrt{E_2AT})$ where$E_2$ is related to the weighted second moment of the stationary measure of areference policy. Importantly, $E_2$ is bounded independently of $S$. Thus, ourbound is asymptotically independent of the number of states and of thediameter. This result is based on a careful study of the number of visitsperformed by the learning algorithm to the states of the MDP, which is highlynon-uniform.

Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space