How do we calculate regret or know best action in a multi armed bandit at run time in a program(python)?

Question

Consider $K$ arms, each having a normal distribution with mean $\mu_k$ taken from:

$$\mu_k ∼ \mathbb{N}(0,1)$$

Then, the reward function $R_t(\mu_k)$ at time $t$ has distribution:

$$R_t(\mu_k) ∼ \mathbb{N}(\mu_k,1)$$

Then, the mean of the best arm is taken to be $\mu_*=\text{max}_k \mu_k$.

From this, assume we have $T$ total pulls of the bandit. Then, the cumulative regret is defined to be:

$$\text{Regret}=T\mu_*−\sum_{t=1}^{T}R_t$$

But at run time , how do we calculate $\mu_*$?

Suppose we have a feedback matrix in implicit form with rows corresponding to users and movies to columns (Movielens dataset binarized) Now we assume movies as arms in a bandit setting Now ho do we get μ∗ here ?

Answer 1

Regret is a quantity to analyse how well you performed on the bandit instance in hindsight.

While calculating the regret, you know the value of $μ_*$ because you know the true values of all $μ_k$. You calculate regret just to gauge how your algorithm did. You, as an observer, know the actual values of the arms.

If you want to evaluate your performance as a bandit instance is running for which you don't know the values of these quantities (this is pretty likely in real world bandit applications), you can simply look at the cumulative reward.

Regret is more useful to analyse theoretically because it gives you a clearer image of how much better you could have done.