Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part II: Markovian rewards

Abstract

At each instant of time we are required to sample a fixed numberm \geq 1out ofNMarkov chains whose stationary transition probability matrices belong to a family suitably parameterized by a real number\theta. The objective is to maximize the long run expected value of the samples. The learning loss of a sampling scheme corresponding to a parameters configurationC = (\theta_{1}, ..., \theta_{N})is quantified by the regretR_{n}(C). This is the difference between the maximum expected reward that could be achieved ifCwere known and the expected reward actually achieved. We provide a lower bound for the regret associated with any uniformly good scheme, and construct a sampling scheme which attains the lower bound for everyC. The lower bound is given explicitly in terms of the Kullback-Liebler number between pairs of transition probabilities.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 110 citations exist upstream.