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?
 A: 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.).
