Ao lidar com multi-armed bandits, métodos tradicionais como epsilon-greedy e UCB estimam valores de ação para decidir qual ação tomar. No entanto, gradient bandits adotam uma abordagem diferente — eles aprendem preferências para as ações em vez de estimar seus valores. Essas preferências são ajustadas ao longo do tempo utilizando ascensão estocástica do gradiente.

Preferências

Em vez de manter estimativas de valor de ação $Q(a)$, gradient bandits mantêm valores de preferência $H(a)$ para cada ação $a$. Essas preferências são atualizadas utilizando uma abordagem de ascensão estocástica do gradiente para maximizar as recompensas esperadas. A probabilidade de cada ação é calculada usando uma função softmax:

onde:

• $H_t(a)$ é a preferência pela ação $a$ em um passo de tempo $t$;
• $P(A_t = a)$ é a probabilidade de selecionar a ação $a$ em um passo de tempo $t$;
• O denominador garante que as probabilidades somem 1.

Softmax é uma função fundamental em ML, comumente utilizada para converter listas de números reais em listas de probabilidades. Essa função serve como uma aproximação suave para a função $\argmax$, permitindo exploração natural ao dar às ações de menor preferência uma chance diferente de zero de serem selecionadas.

Regra de Atualização

Após selecionar uma ação $A_t$ no tempo $t$, os valores de preferência são atualizados utilizando a seguinte regra:

onde:

• $\alpha$ é o tamanho do passo;
• $R_t$ é a recompensa recebida;
• $\bar R_t$ é a recompensa média observada até o momento.

Intuição

A cada passo de tempo, todas as preferências são ajustadas levemente. O ajuste depende principalmente da recompensa recebida e da recompensa média, podendo ser explicado da seguinte forma:

• Se a recompensa recebida for maior que a média, a ação selecionada se torna mais preferida e as demais ações se tornam menos preferidas;
• Se a recompensa recebida for menor que a média, a preferência pela ação selecionada diminui, enquanto as preferências pelas outras ações aumentam, incentivando a exploração.

Código de Exemplo

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Informações Adicionais

Os bandits de gradiente possuem diversas propriedades interessantes:

• Relatividade das preferências: os valores absolutos das preferências das ações não afetam o processo de seleção — apenas suas diferenças relativas importam. Alterar todas as preferências pelo mesmo valor constante (por exemplo, somar 100) resulta na mesma distribuição de probabilidades;
• Efeito do baseline na regra de atualização: embora a fórmula de atualização normalmente inclua a recompensa média como baseline, esse valor pode ser substituído por qualquer constante independente da ação escolhida. O baseline influencia a velocidade de convergência, mas não altera a solução ótima;
• Impacto do tamanho do passo: o tamanho do passo deve ser ajustado conforme a tarefa. Um valor menor garante aprendizado mais estável, enquanto um valor maior acelera o processo de aprendizado.

Resumo

Os bandits por gradiente oferecem uma alternativa poderosa aos algoritmos tradicionais de bandit ao utilizar o aprendizado baseado em preferências. Sua característica mais interessante é a capacidade de equilibrar naturalmente exploração e exploração.