Під час роботи з багаторукими бандитами традиційні методи, такі як epsilon-greedy та UCB, оцінюють значення дій, щоб визначити, яку дію виконати. Однак градієнтні бандити використовують інший підхід — вони навчаються перевагам для дій замість оцінювання їхніх значень. Ці переваги коригуються з часом за допомогою стохастичного градієнтного підйому.

Переваги

Замість підтримки оцінок значень дій $Q(a)$, градієнтні бандити підтримують значення переваг $H(a)$ для кожної дії $a$. Ці переваги оновлюються за допомогою підходу стохастичного градієнтного підйому для максимізації очікуваної винагороди. Ймовірність вибору кожної дії обчислюється за допомогою softmax-функції:

де:

• $H_t(a)$ — перевага для дії $a$ на кроці часу $t$;
• $P(A_t = a)$ — ймовірність вибору дії $a$ на кроці часу $t$;
• Знаменник гарантує, що сума ймовірностей дорівнює 1.

Softmax — це ключова функція в машинному навчанні, яка часто використовується для перетворення списків дійсних чисел у списки ймовірностей. Ця функція є гладким наближенням до функції $\argmax$, що забезпечує природну експлорацію шляхом надання діям з меншою перевагою ненульового шансу бути обраними.

Правило оновлення

Після вибору дії $A_t$ у момент часу $t$, значення переваг оновлюються за наступним правилом:

де:

• $\alpha$ — розмір кроку;
• $R_t$ — отримана винагорода;
• $\bar R_t$ — середня винагорода, отримана до цього моменту.

Інтуїція

На кожному кроці всі переваги трохи зміщуються. Зміщення переважно залежить від отриманої винагороди та середньої винагороди, і це можна пояснити так:

• Якщо отримана винагорода вища за середню, вибрана дія стає більш переважною, а інші дії — менш переважними;
• Якщо отримана винагорода нижча за середню, перевага вибраної дії зменшується, а переваги інших дій збільшуються, що стимулює дослідження.

Приклад коду

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)

Додаткова інформація

Градієнтні бандити мають декілька цікавих властивостей:

• Відносність переваг: абсолютні значення переваг дій не впливають на процес вибору дії — важливими є лише їхні відносні відмінності. Зсув усіх переваг на одну й ту ж константу (наприклад, додавання 100) призводить до тієї ж ймовірнісної розподіленості;
• Вплив базового рівня у правилі оновлення: хоча у формулі оновлення зазвичай використовується середня винагорода як базовий рівень, це значення може бути замінене будь-якою константою, незалежною від обраної дії. Базовий рівень впливає на швидкість збіжності, але не змінює оптимального розв'язку;
• Вплив розміру кроку: розмір кроку слід налаштовувати відповідно до конкретного завдання. Менший розмір кроку забезпечує більш стабільне навчання, тоді як більший прискорює процес навчання.

Підсумок

Градієнтні бандити пропонують потужну альтернативу традиційним алгоритмам бандитів, використовуючи навчання на основі переваг. Їхня найцікавіша особливість — здатність природно балансувати між дослідженням і використанням.