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 consider finite-horizon restless bandits with multiple pulls per period,which play an important role in recommender systems, active learning, revenuemanagement, and many other areas. While an optimal policy can be computed, inprinciple, using dynamic programming, the computation required scalesexponentially in the number of arms $N$. Thus, there is substantial value inunderstanding the performance of index policies and other policies that can becomputed efficiently for large $N$. We study the growth of the optimality gap,i.e., the loss in expected performance compared to an optimal policy, for suchpolicies in a classical asymptotic regime proposed by Whittle in which $N$grows while holding constant the fraction of arms that can be pulled perperiod. Intuition from the Central Limit Theorem and the tightest previoustheoretical bounds suggest that this optimality gap should grow like$O(\sqrt{N})$. Surprisingly, we show that it is possible to outperform thisbound. We characterize a non-degeneracy condition and a wide class of novelpractically-computable policies, called fluid-priority policies, in which theoptimality gap is $O(1)$. These include most widely-used index policies. Whenthis non-degeneracy condition does not hold, we show that fluid-prioritypolicies nevertheless have an optimality gap that is $O(\sqrt{N})$,significantly generalizing the class of policies for which convergence ratesare known. We demonstrate that fluid-priority policies offer state-of-the-artperformance on a collection of restless bandit problems in numericalexperiments.

Restless Bandits with Many Arms: Beating the Central Limit Theorem