O algoritmo do limite superior de confiança (UCB) é uma abordagem popular e eficaz para resolver o problema do multi-armed bandit. Ele possui fortes garantias matemáticas de rápida convergência, otimizando o processo de exploração.

Apesar de sua eficácia na resolução do problema MAB, o algoritmo UCB apresenta algumas limitações notáveis que restringem sua aplicação em contextos mais amplos de aprendizado por reforço:

• Suposição de recompensas estacionárias: o algoritmo UCB assume que as distribuições de recompensas não mudam ao longo do tempo;
• Restrições nos espaços de estados e ações: para começar a escolher ações de acordo com alguma lógica, o algoritmo UCB exige testar cada ação em cada estado pelo menos uma vez.

Enquanto a primeira limitação pode ser contornada com pequenas modificações no algoritmo, a segunda limitação permanece um desafio significativo em muitas aplicações práticas.

Como Funciona

O algoritmo UCB equilibra exploração e exploração atribuindo um intervalo de confiança ao valor estimado de cada ação e selecionando a ação com o maior limite superior. Essa abordagem garante que ações com recompensas incertas sejam exploradas, ao mesmo tempo em que favorece ações que aparentam ser ótimas.

Os passos do algoritmo UCB são idênticos aos passos do algoritmo epsilon-greedy, exceto pelo passo de escolha de uma ação. O algoritmo UCB seleciona uma ação $A_t$ no instante de tempo $t$ utilizando a seguinte fórmula:

onde:

• $Q_t(a)$ é a recompensa estimada da ação $a$ no tempo $t$;
• $N_t(a)$ é o número de vezes que a ação $a$ foi selecionada até o tempo $t$;
• $c > 0$ é um parâmetro ajustável que controla o equilíbrio entre exploração e exploração, semelhante ao $\varepsilon$ no algoritmo $\varepsilon$-greedy;
• $\ln$ é a função logaritmo natural;
• $\argmax$ é o valor do argumento ($a$, neste caso) que maximiza a expressão.

Intuição

$\argmax$ escolhe a ação que maximiza a soma de duas partes: o valor estimado da ação e um intervalo de confiança. O intervalo de confiança é escalado por um fator $c$, onde valores maiores tornam o intervalo mais amplo, indicando que o agente está menos confiante sobre o valor da ação, o que incentiva a exploração.

O tamanho desse intervalo de confiança depende de dois fatores:

1. Tempo: à medida que o tempo passa, o agente se torna menos confiante no valor da ação;
2. Frequência da ação: quanto mais frequentemente uma ação é escolhida, mais confiante o agente se torna em seu valor.

Código de Exemplo

class UpperConfidenceBoundAgent:
  def __init__(self, n_actions, confidence):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.confidence = confidence # c
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the upper confidence bound strategy"""
    # Increase the time step counter
    self.t += 1

    # Each action should be taken at least once
    for action in range(self.n_actions):
      if self.N[action] == 0:
        return action

    # Return the action with highest upper confidence bound
    return np.argmax(self.Q + self.confidence * np.sqrt(np.log(self.t) / self.N))

  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

O algoritmo UCB incorpora um mecanismo de exploração, que exige ajuste cuidadoso do hiperparâmetro $c$ para funcionar de forma eficaz. O valor ideal de $c$ varia conforme o problema específico. Algumas diretrizes gerais:

• Alta variância nas recompensas: um valor maior de $c$ garante exploração suficiente;
• Recompensas estáveis: um valor menor de $c$ permite que o algoritmo foque rapidamente na ação ótima;
• Padrão comum: um ponto de partida típico é $c = 1$, mas geralmente requer ajuste experimental para melhores resultados.

Resumo

O algoritmo UCB é um método robusto e fundamentado para equilibrar exploração e exploração em problemas de multi-armed bandit. Ao selecionar ações com base tanto em recompensas estimadas quanto na incerteza, garante aprendizado eficiente enquanto minimiza o arrependimento.