Optimal solution for a class of multi-armed bandit problems

Question

Consider a setting where we have set of $K$ distributions on $\Bbb R$ given by $f(\theta_1), \dots, f(\theta_K)$, and on each step $i$ we can pick a $k_i\in [1;K]$ and draw a value $x_i\sim f(\theta_{k_i})$. Here $f$ is a parametric family of distributions, e.g. Bernoulli, and $\theta\in \Theta$ is a parameter of this family. It is a setting of a multi-armed bandit (MAB) problem, and usually we want to find a policy of choosing $k_{i+1}$ given past history, which would maximize some performance criterion, e.g. discounted sum of $x_i$'s, or the total amount of trials until we get $x_i = 1$ etc.

I know about many algorithms that can be used to solve these problems approximately, however my question is about optimal solution. For a decision policy $\varphi^*$ to be optimal, it needs to (weakly) dominate any other policy in terms of the given performance criterion. For example, with focus on discounted cost, $\varphi^*$ is said to be optimal iff $$ \Bbb E^{\varphi^*}\left(\sum_{i=0}^\infty \gamma^i x_{k_i}\right) \geq\Bbb E^{\varphi}\left(\sum_{i=0}^\infty \gamma^i x_{k_i}\right) \tag{1} $$ holds for every other policy $\varphi$. Now, to take those expectations, we also need to fix a distribution over $\theta_k$'s, let's call it $P_\theta$.

Now, with all this information: $\Theta,f,p_\theta$ and performance criterion, is necessary to say whether a particular strategy $\varphi$ is optimal or not, e.g. by means of looking at $(1)$. I wonder what are the methods to find optimal strategies given this information, since as I've mentioned above, I am only familiar with approximate methods. They are approximate in a sense that they do something intuitively well (exploring/exploiting), however it seems that there can always be a better method (which contradicts $(1)$ in terms of optimality).

Just to clarify: here I am talking specifically about optimality in theoretical sense, a method I am talking about should not necessarily be the most efficient computationally, or tractable over large state spaces, but guaranteed to provide the best strategy. For example, if I put a problem above in the poMDP formulation, I can use methods that find optimal strategies for poMDPs, and I can be sure that such strategies cannot be beaten by any algorithm developed for MAB (yet again, in terms of best value, not necessarily in terms of efficiency).

Answer 1

There is some middle ground between a heuristic algorithm (which does something intuitive) and an optimal algorithm which dominates all other approaches. The vast majority of the theoretical multi-armed bandit literature is focused on finding bounds on the regret, which is the difference between the reward accumulated by a policy which starts with the relevant parameters (e.g. the values of the $\theta_k$) and the reward accumulated by a policy which learns. Since your criterion is the expected value of the rewards, we would study the expected regret (sometimes called the Bayes regret).

We have lower bounds on how little regret any policy can accumulate (typically $\Omega(\sqrt{T})$), and for many cases there are algorithms with worst-case regret bounds that are within polylogarithmic factors of the known lower bounds. A good survey would be section 2 of the survey by Bubeck and Cesa-Bianchi: "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems".