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

Restless bandits are an important class of problems with applications inrecommender systems, active learning, revenue management and other areas. Weconsider infinite-horizon discounted restless bandits with many arms where afixed proportion of arms may be pulled in each period and where arms share afinite state space. Although an average-case-optimal policy can be computed viastochastic dynamic programming, the computation required grows exponentiallywith the number of arms $N$. Thus, it is important to find scalable policiesthat can be computed efficiently for large $N$ and that are near optimal inthis regime, in the sense that the optimality gap (i.e. the loss of expectedperformance against an optimal policy) per arm vanishes for large $N$. However,the most popular approach, the Whittle index, requires a hard-to-verifyindexability condition to be well-defined and another hard-to-verify conditionto guarantee a $o(N)$ optimality gap. We present a method resolving thesedifficulties. By replacing a global Lagrange multiplier used by the Whittleindex with a sequence of Lagrangian multipliers, one per time period up to afinite truncation point, we derive a class of policies, called fluid-balancepolicies, that have a $O(\sqrt{N})$ optimality gap. Unlike the Whittle index,fluid-balance policies do not require indexability to be well-defined and their$O(\sqrt{N})$ optimality gap bound holds universally without sufficientconditions. We also demonstrate empirically that fluid-balance policies providestate-of-the-art performance on specific problems.

Near-optimality for infinite-horizon restless bandits with many arms