A Lower Bound for Identifying the Best Markovian Arm with Fixed Confidence

Vrettos Moulos

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2019-33
May 14, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-33.pdf

We consider the problem of best Markovian arm identification, where we sequentially collect samples from K Markov chains with our goal being to identify the one with the largest stationary mean with some fixed level of confidence. In Theorem 4 we derive an instance specific non-asymptotic lower bound for the sample complexity, which in the high confidence regime (Corollary 5) generalizes the asymptotic lower bound of Garivier and Kaufmann (2016) which deals with the special case where the K stochastic processes are i.i.d. processes.

Advisor: Satish Rao


BibTeX citation:

@mastersthesis{Moulos:EECS-2019-33,
    Author = {Moulos, Vrettos},
    Title = {A Lower Bound for Identifying the Best Markovian Arm with Fixed Confidence},
    School = {EECS Department, University of California, Berkeley},
    Year = {2019},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-33.html},
    Number = {UCB/EECS-2019-33},
    Abstract = {We consider the problem of best Markovian arm identification, where we sequentially collect samples from K Markov chains with our goal being to identify the one with the largest stationary mean with some fixed level of confidence. In Theorem 4 we derive an instance specific non-asymptotic lower bound for the sample complexity, which in the high confidence regime (Corollary 5) generalizes the asymptotic lower bound of Garivier and Kaufmann (2016) which deals with the special case where the K stochastic processes are i.i.d. processes.}
}

EndNote citation:

%0 Thesis
%A Moulos, Vrettos
%T A Lower Bound for Identifying the Best Markovian Arm with Fixed Confidence
%I EECS Department, University of California, Berkeley
%D 2019
%8 May 14
%@ UCB/EECS-2019-33
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-33.html
%F Moulos:EECS-2019-33