O algoritmo epsilon-greedy ($\varepsilon$-greedy) é uma estratégia simples, porém altamente eficaz, para abordar o problema do multi-armed bandit. Embora possa não ser tão robusto quanto outros métodos para essa tarefa específica, sua simplicidade e versatilidade o tornam amplamente aplicável no campo de aprendizado por reforço.

Como Funciona

O algoritmo segue estes passos:

1. Inicializar as estimativas dos valores das ações $Q(a)$ para cada ação $a$;
2. Escolher uma ação utilizando a seguinte regra:
   • Com probabilidade $\varepsilon$: selecionar uma ação aleatória (exploração);
   • Com probabilidade $1 - \varepsilon$: selecionar a ação com o maior valor estimado (exploração).
3. Executar a ação e observar a recompensa;
4. Atualizar a estimativa do valor da ação $Q(a)$ com base na recompensa observada;
5. Repetir os passos 2-4 por um número fixo de etapas de tempo.

O hiperparâmetro $\varepsilon$ (epsilon) controla o equilíbrio entre exploração e exploração:

• Um $\varepsilon$ alto (por exemplo, 0.5) incentiva mais exploração;
• Um $\varepsilon$ baixo (por exemplo, 0.01) favorece a exploração da melhor ação conhecida.

Código de Exemplo

class EpsilonGreedyAgent:
  def __init__(self, n_actions, epsilon):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.epsilon = epsilon # epsilon
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters

  def select_action(self):
    """Select an action according to the epsilon-greedy strategy"""
    # With probability epsilon - random action
    if np.random.rand() < self.epsilon:
      return np.random.randint(self.n_actions)
    # Otherwise - action with highest estimated action value
    else:
      return np.argmax(self.Q)

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Informações Adicionais

A eficiência do algoritmo $\varepsilon$-ganancioso depende fortemente do valor de $\varepsilon$. Duas estratégias são comumente utilizadas para selecionar esse valor:

• $\varepsilon$ fixo: esta é a opção mais genérica, onde o valor de $\varepsilon$ é escolhido como uma constante (por exemplo, 0,1);
• $\varepsilon$ decrescente: o valor de $\varepsilon$ diminui ao longo do tempo de acordo com algum cronograma (por exemplo, começa em 1 e diminui gradualmente até 0) para incentivar a exploração nas fases iniciais.

Resumo

O algoritmo $\varepsilon$-ganancioso é uma abordagem de referência para equilibrar exploração e exploração. Embora simples, serve como base para compreender estratégias mais avançadas, como limite superior de confiança (UCB) e bandits de gradiente.