Під час розв’язання задачі багаторуких бандитів традиційні методи, такі як epsilon-жадібний та 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) призводить до тієї ж ймовірнісної розподілу;
• Вплив базового рівня в правилі оновлення: хоча у формулі оновлення зазвичай використовується середня винагорода як базовий рівень, це значення можна замінити будь-якою константою, що не залежить від обраної дії. Базовий рівень впливає на швидкість збіжності, але не змінює оптимального розв'язку;
• Вплив розміру кроку: розмір кроку слід налаштовувати відповідно до конкретного завдання. Менший розмір кроку забезпечує більш стабільне навчання, тоді як більший прискорює процес навчання.

Підсумок

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