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 online restless bandit problem, where the state of each armevolves according to a Markov chain, and the reward of pulling an arm dependson both the pulled arm and the current state of the corresponding Markov chain.In this paper, we propose Restless-UCB, a learning policy that follows theexplore-then-commit framework. In Restless-UCB, we present a novel method toconstruct offline instances, which only requires $O(N)$ time-complexity ($N$ isthe number of arms) and is exponentially better than the complexity of existinglearning policy. We also prove that Restless-UCB achieves a regret upper boundof $\tilde{O}((N+M^3)T^{2\over 3})$, where $M$ is the Markov chain state spacesize and $T$ is the time horizon. Compared to existing algorithms, our resulteliminates the exponential factor (in $M,N$) in the regret upper bound, due toa novel exploitation of the sparsity in transitions in general restless banditproblems. As a result, our analysis technique can also be adopted to tightenthe regret bounds of existing algorithms. Finally, we conduct experiments basedon real-world dataset, to compare the Restless-UCB policy with state-of-the-artbenchmarks. Our results show that Restless-UCB outperforms existing algorithmsin regret, and significantly reduces the running time.

Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits