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

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

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

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

course content

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

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