Does there exist a single metric that can compare various Multi-arm Bandit scenarios apples to apples?

I am currently trying to compare how different formulations of a Multi-arm Bandit problem performs across various factors like the variance of the reward distributions of each arm, to the $\epsilon$ parameter used in $\epsilon$-greedy search. Originally, I used the regret as a way of characterizing performance over an epoch of time length $T$. However, I realized that the regret cannot be used to compare a MAB problem with normally distributed rewards with one that has Bernoulli rewards. This is because the regret, defined as the cumulative difference between the optimal mean and the chosen arm's mean, is sensitive to scale. Does there exist a scale-less metric where I can compare a MAB using Normal rewards with one that uses Bernoulli rewards?

• I'm confused why Bernoulli rewards are so special. Presumably each arm's probability of reward $p$ comes from a prior distribution, which has a well defined mean and variance. As an example this is how Thompson sampling works, by assuming the prior distribution is Beta. Apr 22, 2018 at 0:08

1 Answer

You are probably making this problem more difficult than it actually is. In any MAB problem you have a scalar random gain with some distribution under the optimal strategy, and so your problem comes down to finding a scale-free measure of variability for a scalar random variable.

Random gains under MAB: Every MAB problem involves a random gain that is affected by the model parameters and the choice of strategy. Moreover, in different models involving the same number of "bandits" and rounds, you can construct a common strategy-space over the union of the supports of the observable outcomes. The strategy-space is the set of allowable choice functions of $K$ bandits over $N$ rounds, with selection allowed to be affected by outcomes for the chosen bandits in previous rounds.

Suppose we have some MAB model with $K$ bandits and $N$ rounds, using some distribution with parameter vector $\boldsymbol{\theta}$. Let $s$ denote a strategy for the problem and let $\mathscr{S}$ denote the strategy-space. The gain for the MAB problem is a random function $G(s, \omega | \boldsymbol{\theta})$ affected by the model parameters, the strategy $s \in \mathscr{S}$ and the random outcome $\omega \in \Omega$. In any MAB problem this means that the gain has a distribution depending on the strategy:

$$G(s | \boldsymbol{\theta}) \sim \text{Dist}(s, \boldsymbol{\theta}) \quad \quad \text{for all }s \in \mathscr{S}.$$

The distribution differs across different MAB problems, but the basic setup is the same, and hence, it should be possibly to formulate measurements of aspects of the gain that are comparable across different MAB problems. In a particular MAB problem we usually choose a strategy $\hat{s}$ to maximise the expected gain, or to solve some similar optimisation problem (e.g., minimum regret, etc.). This yields a random optimised gain $G(\hat{s}, \boldsymbol{\theta}) \sim \text{Dist}(\hat{s}, \boldsymbol{\theta})$. The optimised gain is a random variable with a distribution that depends only on the model parameters.

Scale-free measures of variability: If I understand your question correctly, you are seeking some scale-free measure of variability of the optimal gain that can be compared across different models, or different parameter specifications within a single model. Once you recognise that the optimal gain in MAB is just a regular random variable, with some distribution that depends on the model parameters, this problem is not really any different to the general problem of using scale-free measure of variability for an arbitrary random variable.

All you need to do to find a scale-free measure of variability is to take any measure of variability and then scale it down by a measure of location on the same scale. One example would be to use the coefficient of variation, though this is not a very good measure in cases where the gains can be negative (e.g., in the normal model). It is legitimate to formulate a scale-free metric and compare it across models, so long as you bear in mind the differences in the models (e.g., different supports for the gains, etc.).

• Thanks! This is very helpful perspective. I have having trouble coming up with an example for the gain in the form of a Bernoulli MAB. Would you know of a simple example there for intuition purposes? Thank you! Apr 22, 2018 at 21:36
• The gain function is usually given by the model specification (e.g., in a Bernoulli MAB the gain is a Bernoulli random variable). Deriving the optimal strategy is complicated, since it requires backwards induction using Bayesian updating of beliefs about unknown parameters. If you are interested in trying this, I suggest starting with a simple model with only two arms and small number of rounds. This will give a basic understanding of the form of the solution, which will give you an optimal gain function and its distribution.
– Ben
Apr 26, 2018 at 1:52
• If you would like help with this, pose it as a new question and I will have a crack at it. A simple two-arm Bernoulli model would have gain probabilities $\boldsymbol{\theta} = (\theta_1, \theta_2)$ and gain function $G(s | \boldsymbol{\theta}) \sim \text{Bern}(\theta_s)$ and the gambler would choose one of the two arms each round, in an attempt to maximise the expected gain.
– Ben
Apr 26, 2018 at 1:55