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.


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.