Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Алгоритм Верхньої Довірчої Межі | Проблема Багаторукого Бандита
Вступ до навчання з підкріпленням

bookАлгоритм Верхньої Довірчої Межі

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

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

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

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

Як це працює

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

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

At=arg maxa(Qt(a)+clntNt(a))A_t = \argmax_a\Biggl(Q_t(a) + c \sqrt\frac{\ln t}{N_t(a)}\Biggr)

де:

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

Інтуїція

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

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

  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 включає механізм дослідження, для ефективної роботи якого необхідно ретельно налаштовувати гіперпараметр cc. Оптимальне значення cc залежить від конкретної задачі. Ось загальні рекомендації:

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

Підсумок

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

question mark

Як алгоритм UCB вирішує дилему дослідження-використання?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 2. Розділ 4

Запитати АІ

expand

Запитати АІ

ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Awesome!

Completion rate improved to 2.7

bookАлгоритм Верхньої Довірчої Межі

Свайпніть щоб показати меню

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

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

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

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

Як це працює

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

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

At=arg maxa(Qt(a)+clntNt(a))A_t = \argmax_a\Biggl(Q_t(a) + c \sqrt\frac{\ln t}{N_t(a)}\Biggr)

де:

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

Інтуїція

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

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

  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 включає механізм дослідження, для ефективної роботи якого необхідно ретельно налаштовувати гіперпараметр cc. Оптимальне значення cc залежить від конкретної задачі. Ось загальні рекомендації:

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

Підсумок

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

question mark

Як алгоритм UCB вирішує дилему дослідження-використання?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 2. Розділ 4
some-alt