1
$\begingroup$

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.

$\endgroup$

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.