Алгоритм верхньої межі довіри (UCB) — це популярний та ефективний підхід для розв'язання задачі багаторукого бандита. Він має сильні математичні гарантії швидкої збіжності, оптимізуючи процес дослідження.

Попри свою ефективність у розв'язанні задачі багаторукого бандита, алгоритм UCB має деякі суттєві обмеження, які звужують його застосування у ширшому підході до навчання з підкріпленням:

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

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

Як це працює

Алгоритм UCB балансує дослідження та використання, призначаючи довірчий інтервал для кожного оціненого значення дії та обираючи дію з найвищою верхньою межею. Такий підхід забезпечує дослідження дій з невизначеними винагородами, водночас віддаючи перевагу діям, які здаються оптимальними.

Кроки UCB-алгоритму ідентичні крокам epsilon-жадібного алгоритму, за винятком кроку вибору дії. UCB-алгоритм обирає дію $A_t$ на кроці часу $t$ за наступною формулою:

де:

• $Q_t(a)$ — оцінене значення винагороди для дії $a$ у момент часу $t$;
• $N_t(a)$ — кількість разів, коли дія $a$ була обрана до моменту часу $t$;
• $c > 0$ — налаштовуваний параметр, який контролює баланс між дослідженням і використанням, подібно до $\varepsilon$ у $\varepsilon$-жадібному алгоритмі;
• $\ln$ — функція натурального логарифму;
• $\argmax$ — значення аргументу ($a$ у цьому випадку), яке максимізує вираз.

Інтуїція

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

Розмір цього довірчого інтервалу залежить від двох факторів:

1. Час: з плином часу агент стає менш впевненим у значенні дії;
2. Частота вибору дії: чим частіше обирається дія, тим більш впевненим стає агент у її значенні.

Приклад коду

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]

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

Алгоритм UCB включає механізм дослідження, для ефективної роботи якого необхідне ретельне налаштування гіперпараметра $c$. Оптимальне значення $c$ залежить від конкретної задачі. Ось кілька загальних рекомендацій:

• Висока дисперсія винагород: більше значення $c$ забезпечує достатнє дослідження;
• Стабільні винагороди: менше значення $c$ дозволяє алгоритму швидко зосередитися на оптимальній дії;
• Поширене значення за замовчуванням: типовою відправною точкою є $c = 1$, але часто потрібне експериментальне налаштування для досягнення найкращих результатів.

Підсумок

Алгоритм UCB — це потужний і обґрунтований метод для балансування між дослідженням і використанням у задачах багаторукого бандита. Обираючи дії на основі оцінених винагород і невизначеності, він забезпечує ефективне навчання при мінімізації втрат.