Алгоритм Верхньої Довірчої Межі
Алгоритм верхньої межі довіри (UCB) — це популярний та ефективний підхід для розв'язання задачі багаторукого бандита. Він має сильні математичні гарантії швидкої збіжності, оптимізуючи процес дослідження.
Попри свою ефективність у розв'язанні задачі багаторукого бандита, алгоритм UCB має деякі суттєві обмеження, які звужують його застосування в ширшому підході навчання з підкріпленням:
- Припущення про стаціонарність винагород: алгоритм UCB передбачає, що розподіли винагород не змінюються з часом;
- Обмеження на простори станів і дій: для того, щоб почати вибирати дії за певною логікою, алгоритм UCB вимагає спробувати кожну дію в кожному стані хоча б один раз.
Хоча перше обмеження можна усунути шляхом невеликої модифікації алгоритму, друге обмеження залишається значною проблемою у багатьох практичних застосуваннях.
Як це працює
Алгоритм UCB балансує між дослідженням і використанням, призначаючи довірчий інтервал для кожного оціненого значення дії та вибираючи дію з найвищою верхньою межею. Такий підхід гарантує, що дії з невизначеними винагородами будуть досліджені, водночас надаючи перевагу діям, які здаються оптимальними.
Кроки UCB-алгоритму ідентичні крокам epsilon-жадібного алгоритму, за винятком кроку вибору дії. UCB-алгоритм обирає дію At на кроці часу t за наступною формулою:
At=aargmax(Qt(a)+cNt(a)lnt)де:
- Qt(a) — оцінене значення винагороди для дії a на кроці часу t;
- Nt(a) — кількість разів, коли дія a була обрана до моменту t;
- c>0 — налаштовуваний параметр, який визначає баланс між дослідженням і використанням, подібно до ε у ε-жадібному алгоритмі;
- ln — функція натурального логарифму;
- argmax — значення аргументу (a у цьому випадку), яке максимізує вираз.
Інтуїція
argmax обирає дію, яка максимізує суму двох частин: оціненого значення дії та довірчого інтервалу. Довірчий інтервал масштабується коефіцієнтом c, де більші значення роблять інтервал ширшим, тобто агент менш впевнений у значенні дії, що стимулює дослідження.
Розмір цього довірчого інтервалу залежить від двох факторів:
- Час: з плином часу агент стає менш впевненим у значенні дії;
- Частота вибору дії: чим частіше обирається дія, тим більш впевненим стає агент у її значенні.
Приклад коду
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 — це потужний і обґрунтований метод для балансування дослідження та використання у задачах багаторукого бандита. Обираючи дії на основі оцінених винагород і невизначеності, він забезпечує ефективне навчання при мінімізації втрат.
Дякуємо за ваш відгук!
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Awesome!
Completion rate improved to 2.7
Алгоритм Верхньої Довірчої Межі
Свайпніть щоб показати меню
Алгоритм верхньої межі довіри (UCB) — це популярний та ефективний підхід для розв'язання задачі багаторукого бандита. Він має сильні математичні гарантії швидкої збіжності, оптимізуючи процес дослідження.
Попри свою ефективність у розв'язанні задачі багаторукого бандита, алгоритм UCB має деякі суттєві обмеження, які звужують його застосування в ширшому підході навчання з підкріпленням:
- Припущення про стаціонарність винагород: алгоритм UCB передбачає, що розподіли винагород не змінюються з часом;
- Обмеження на простори станів і дій: для того, щоб почати вибирати дії за певною логікою, алгоритм UCB вимагає спробувати кожну дію в кожному стані хоча б один раз.
Хоча перше обмеження можна усунути шляхом невеликої модифікації алгоритму, друге обмеження залишається значною проблемою у багатьох практичних застосуваннях.
Як це працює
Алгоритм UCB балансує між дослідженням і використанням, призначаючи довірчий інтервал для кожного оціненого значення дії та вибираючи дію з найвищою верхньою межею. Такий підхід гарантує, що дії з невизначеними винагородами будуть досліджені, водночас надаючи перевагу діям, які здаються оптимальними.
Кроки UCB-алгоритму ідентичні крокам epsilon-жадібного алгоритму, за винятком кроку вибору дії. UCB-алгоритм обирає дію At на кроці часу t за наступною формулою:
At=aargmax(Qt(a)+cNt(a)lnt)де:
- Qt(a) — оцінене значення винагороди для дії a на кроці часу t;
- Nt(a) — кількість разів, коли дія a була обрана до моменту t;
- c>0 — налаштовуваний параметр, який визначає баланс між дослідженням і використанням, подібно до ε у ε-жадібному алгоритмі;
- ln — функція натурального логарифму;
- argmax — значення аргументу (a у цьому випадку), яке максимізує вираз.
Інтуїція
argmax обирає дію, яка максимізує суму двох частин: оціненого значення дії та довірчого інтервалу. Довірчий інтервал масштабується коефіцієнтом c, де більші значення роблять інтервал ширшим, тобто агент менш впевнений у значенні дії, що стимулює дослідження.
Розмір цього довірчого інтервалу залежить від двох факторів:
- Час: з плином часу агент стає менш впевненим у значенні дії;
- Частота вибору дії: чим частіше обирається дія, тим більш впевненим стає агент у її значенні.
Приклад коду
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 — це потужний і обґрунтований метод для балансування дослідження та використання у задачах багаторукого бандита. Обираючи дії на основі оцінених винагород і невизначеності, він забезпечує ефективне навчання при мінімізації втрат.
Дякуємо за ваш відгук!