Value of information in a multi-arm bandit problem

Question

Consider a stochastic multi-armed bandit problem, where one of the $N$ arms of a given slot machine must be chosen to be played. Each arm $i$, when played, yields a random real-valued reward $r_i$ according to some fixed (unknown) distribution $p_i(r_i)$ with support over the real line. The random reward obtained from playing an arm repeatedly are i.i.d. and independent of the plays of the other arms. The reward is observed immediately after playing the arm.

Assume that, after $T$ plays of this problem, we have derived an estimate of $p_i(r_i)$ from a limited number of samples, denoted $\hat{p}_i(r_i)$. Clearly, the expected reward obtained in this multi-arm bandit problem should be higher the closer $\hat{p}_i(r_i)$ is from $p_i(r_i)$.

I would like to calculate the utility of knowing the true distribution $p_i(r_i)$, in terms of the expected improvement in rewards from playing according to $p_i(r_i)$ as opposed to $\hat{p}_i(r_i)$.

PS: I realize that the question may require information about which arm is selected based on the various probability distributions estimates $\hat{p}_i(r_i)$. If we assume that the arm with highest $E[r_i]$ is selected, this would suggest that there's no added value in knowing the true distribution $p_i(r_i)$ if $r_i$ has the same mean under both $p_i(r_i)$ and $\hat{p}_i(r_i)$, even if the distributions have different variances. Similarly, if the arm with highest $E[r_i]$ under $\hat{p}_i(r_i)$ is still the best arm under $p_i(r_i)$, this would suggest that learning about $p_i(r_i)$ would have no added value. However, intuitively, it seems like having a more precise and unbiased representation of the reward distributions would be advantageous. Perhaps we need to consider a different action selection approach, such as Thompson-Sampling.

Any pointers towards relevant literature would be greatly appreciated.

Answer 1

The difference in the expected rewards between a policy which knows the true distribution and your policy which must learn the distribution is called the expected regret (sometimes called the Bayes regret). As a general rule of thumb, the best you can hope for is that the expected regret is $\sqrt{T}$, that is, the penalty for having to learn the distribution is $O(\sqrt{T})$. In general, you can find papers which achieve $O(\log(T)\sqrt{T})$ regret. Sometimes regret bounds are given in terms of the `distribution gap' $\Delta$ (difference between the highest and second highest mean of the rewards), in which case the best bounds are $O\left(\frac{1}{\Delta} \log(T)\right)$.

A good starting place is work by Russo and Van Roy in their paper: "An information-theoretic analysis of Thompson sampling" https://arxiv.org/abs/1403.5341

Also consider their other work, "Learning to optimize via posterior sampling", https://arxiv.org/abs/1301.2609 which has a very good background and examples section. Finally, their work on Information directed sampling also may be relevant.

You may also find work on Gaussian process bandits helpful, e.g. `Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting' by Srinivas et al. Note that the results in this paper are high-probability bounds on the regret, which in general is a much stronger guarantee than bounds on the Bayes regret.