Linear Regret for epsilon-greedy algorithm in Multi-Armed Bandit problem

Question

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.

Answer 1

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$.

Answer 2

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.