Linear Regret for epsilon-greedy algorithm in Multi-Armed Bandit problem I am reading about $\epsilon$-greedy algorithm in Multi-Armed Bandit (or $K$ armed bandit) problem, as can be seen here: https://en.wikipedia.org/wiki/Multi-armed_bandit#Semi-uniform_strategies. 
For the sake of completeness, I am stating the  $\epsilon$-greedy algorithm briefly here. 


*

*The algorithm maintains an estimate $\hat\mu_i$ for the expectation of $i^{th}$ arm. Initially each of the arm is pulled once to initialize $\hat\mu_i$.

*Next for each time step $t$ loop:


*

*$k = arg max_{ 1 \leq i\leq K }\hat\mu_i$

*with probability $1-\epsilon$ pull $arm_k$, and with probability $1-\epsilon$ pull any other arm.



Note that regret at time $T$ in this case is quantified as:
$Regret_T = T\mu^*-\sum_{t=1}^T{x_{i(t)}}$, where $\mu^*=max_{k\in\{1,...,K\}}\mu_k$, and $x_{i(t)}$ is reward at time $t$.
Now, it seems that expected cumulative regret can't be bounded by $log(T)$ (as a function of time $T$), and instead this algorithm has a linear regret. 
It is not very clear to me the how one can prove this claim. Any help to elucidate this will be great. 
 A: If $\epsilon$ is a constant, then this has linear regret. Suppose that the initial estimate is perfect. Then you pull the `best' arm with probability $1-\epsilon$ and pull an imperfect arm with probability $\epsilon$, giving expected regret $\epsilon T = \Theta(T)$. 
However the parameter $\epsilon$ is typically set to be a decreasing function of the iteration $t$. The trick is to decrease fast enough that the regret is close to the optimal $\sqrt{T}$ (or $\Delta \log(T)$ in the distribution dependent case), but slow enough that the estimate of which arm to choose converges to the optimum. For details on how to choose $\epsilon$, see Auer et al., who set it proportional to $1/t$.
A: So this is what I think about this problem:
At each time step $T$, the $ϵ$-greedy algorithm selects between optimal arm $a_k$ with probability $1-ϵ$, and all non-optimal arms $a_i,1≤i≤K∧i≠k$ with probability $ϵ$, where $K$ is the total number of arms, and $k = arg max_{ 1 \leq i\leq K }\hat\mu_i$ , where $μ ̂_i$  is the empirical expectation of arm $a_i$.
From the above argument we can deduce the following: if $ϵ$ is chosen to be small, that is the probability of selecting a non-optimal arm is very small, which means that probability of a super-linear growth of expected cumulative regret is also very small; and for very small $ϵ$, super-linear expected cumulative regret can be technically ruled out.
Now, for each time step $T$, the expected regret is:
$(1-ϵ)(μ_T^*-μ ̂_{k_T})+ϵ∑_{1≤i≤K∧i≠k}(μ_T^*-μ ̂_{i_T} )$
where $μ_T^*$  is the value of $μ^*$ at time step $T$, and $μ^*=max_{1≤i≤K}⁡μ_i$ , where $μ_i$ is the actual underlying expectation of arm $a_i$. However as the true expectation is unknown, $μ^*$ can be redefined as: $μ^*=max_{1≤i≤K}⁡μ ̂_i$.
Note that by the (re)definition of $μ^*$, $μ_T^*=μ ̂_{k_T}$.
Thus, for each time step $T$, the expected regret becomes:
$ϵ∑_{1≤i≤K∧i≠k}(μ_T^*-μ ̂_{i_T} )$.
Now let $μ_{nonOptMax}=max_{1≤i≤K∧i≠k}μ ̂_i$. It is easy to see that at each time step $T$, the expected regret is at minimum:
$ϵ∑_{1≤i≤K∧i≠k}(μ_T^*-μ_{nonOptMax_T}) = ϵ(K-1)(μ_T^*-μ_{nonOptMax_T})$
As $ϵ≥0$, and $μ_T^*>μ_{nonOptMax_T}$(under the assumption that not all expected values $µ_i  = E(X_i)$ are the same), 
$ϵ(K-1)(μ_T^*-μ_{nonOptMax_T})>0$, 
and thus, expected regret at each time step $T$ is $> 0$.
From this, we can deduce that cumulative expected regret is definitely not sub linear. 
We can thereby conclude that the growth of the cumulative expected regret is linear.
P.S.: Please let me know what you think about this argument.
