Difference between regret and pseudo-regret definitions

Question

I am following the book Bandit Algorithms. In page 48, they introduces regret after $n$ rounds as

$$ \mathbf{R} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mathbf{X}_t\Bigg] \tag{1} $$

In page 55, they also define pseudo-regret as

$$ \bar{\mathbf{R}} = n\mu^\star - \sum_{t=1}^n \mu_{A_t} \tag{2} $$

In the paper Regret Analysis of Stochastic and ..., authors introduces pseudo-regret as

$$ \bar{\mathbf{R}} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mu_{A_t}\Bigg] \tag{3} $$

Can anyone tell me the differences in the three definitions ?

In the first definition, due to the linearity of the expectation, we can write it exactly like (2). Hence (1) and (2) should be referring to the same quantity ?

Since $\mu_{A_t}$ is not a random variable, $\mathbb{E}[\mu_{A_t}] = \mu_{A_t}$, and due to the linearity of expectation, (2) and (3) should be referring to the same quantity.

Anyone can help me out with these definitions ?

Answer 1

I do not think that $\mathbb{E}(X_t) = \mu_{A_t}$. Because $\mu_{A_t}$ is a random variable which depends on which arm you are pulling at time $t$. For example, let's consider a two-arm bandit. The policy is to pull the arms randomly with equal probability. And each arm has its own reward distribution $\mu_1$ and $\mu_2$. In pseudo-regret, you just ignore the randomness of reward distribution (these are very weak words and just for understanding) and you assume that you will get a fixed reward ($\mu_1$ and $\mu_2$) when you pull each of the arms. The only randomness is from your policy i.e. which arm you are pulling at each time step $t$. I think it answers both of your questions.