Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from that arm, but we get to observe a stochastic sample of the rewards of all arms.

This problem can be reduced to the stochastic expert setting, where the problem independent lower bound of $O(\sqrt{KT})$ is known, where $T$ is the time-horizon.

However, I am interested in a logarithmic regret lower bound that depends on the instance $\mu_1,...,\mu_K$ (similar to Lai and Robbins expression). Somehow I am not being able to find this in the literature. Any references would be helpful. It is known that the optimal algorithm is just following the highest estimated mean.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.