# Difference between regret and pseudo-regret definitions

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 ?

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.