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

At each instant of time we are required to sample a fixed number <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m ≥ 1</tex> out of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> Markov chains whose stationary transition probability matrices belong to a family suitably parameterized by a real number <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">θ</tex> . The objective is to maximize the long run expected value of the samples. The learning loss of a sampling scheme corresponding to a parameters configuration <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C = (θ₁, ..., θN)</tex> is quantified by the regret <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Rₙ(C)</tex> . This is the difference between the maximum expected reward that could be achieved if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</tex> were 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 every <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</tex> . The lower bound is given explicitly in terms of the Kullback-Liebler number between pairs of transition probabilities.