Pure exploration in multi-armed bandits with low rank structure using
  oblivious sampler
Yaxiong Liu Atsuyoshi Nakamura Kohei Hatano Eiji Takimoto
In this paper, we consider the low rank structure of the reward sequence of
the pure exploration problems. Firstly, we propose the separated setting in
pure exploration problem, where the exploration strategy cannot receive the
feedback of its explorations. Due to this separation, it requires that the
exploration strategy to sample the arms obliviously. By involving the kernel
information of the reward vectors, we provide efficient algorithms for both
time-varying and fixed cases with regret bound $O(d\sqrt{(\ln N)/n})$. Then, we
show the lower bound to the pure exploration in multi-armed bandits with low
rank sequence. There is an $O(\sqrt{\ln N})$ gap between our upper bound and
the lower bound.