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

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/Archive/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.

Advisors: 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