Зміст курсу
Вступ до навчання з підкріпленням
Вступ до навчання з підкріпленням
Алгоритм Верхньої Довірчої Межі
Алгоритм верхньої межі довіри (UCB) — це популярний та ефективний підхід для розв'язання задачі багаторукого бандита. Він має сильні математичні гарантії швидкої збіжності, оптимізуючи процес дослідження.
Попри свою ефективність у розв'язанні задачі багаторукого бандита, алгоритм UCB має деякі суттєві обмеження, які звужують його застосування в ширшому підході навчання з підкріпленням:
- Припущення про стаціонарність винагород: алгоритм UCB передбачає, що розподіли винагород не змінюються з часом;
- Обмеження на простори станів і дій: для того, щоб почати вибирати дії за певною логікою, алгоритм UCB вимагає спробувати кожну дію в кожному стані хоча б один раз.
Хоча перше обмеження можна усунути шляхом невеликої модифікації алгоритму, друге обмеження залишається значною проблемою у багатьох практичних застосуваннях.
Як це працює
Алгоритм UCB балансує між дослідженням і використанням, призначаючи довірчий інтервал для кожного оціненого значення дії та вибираючи дію з найвищою верхньою межею. Такий підхід гарантує, що дії з невизначеними винагородами будуть досліджені, водночас надаючи перевагу діям, які здаються оптимальними.
Кроки UCB-алгоритму ідентичні крокам epsilon-жадібного алгоритму, за винятком кроку вибору дії. UCB-алгоритм обирає дію на кроці часу за наступною формулою:
де:
- — оцінене значення винагороди для дії на кроці часу ;
- — кількість разів, коли дія була обрана до моменту ;
- — налаштовуваний параметр, який визначає баланс між дослідженням і використанням, подібно до у -жадібному алгоритмі;
- — функція натурального логарифму;
- — значення аргументу ( у цьому випадку), яке максимізує вираз.
Інтуїція
обирає дію, яка максимізує суму двох частин: оціненого значення дії та довірчого інтервалу. Довірчий інтервал масштабується коефіцієнтом , де більші значення роблять інтервал ширшим, тобто агент менш впевнений у значенні дії, що стимулює дослідження.
Розмір цього довірчого інтервалу залежить від двох факторів:
- Час: з плином часу агент стає менш впевненим у значенні дії;
- Частота вибору дії: чим частіше обирається дія, тим більш впевненим стає агент у її значенні.
Приклад коду
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 включає механізм дослідження, для ефективної роботи якого необхідно ретельно налаштовувати гіперпараметр . Оптимальне значення залежить від конкретної задачі. Ось загальні рекомендації:
- Висока дисперсія винагород: більше значення забезпечує достатнє дослідження;
- Стабільні винагороди: менше значення дозволяє алгоритму швидко зосередитися на оптимальній дії;
- Типове значення за замовчуванням: типовою відправною точкою є , але часто потрібне експериментальне налаштування для досягнення найкращих результатів.
Підсумок
Алгоритм UCB — це потужний і обґрунтований метод для балансування дослідження та використання у задачах багаторукого бандита. Обираючи дії на основі оцінених винагород і невизначеності, він забезпечує ефективне навчання при мінімізації втрат.
Дякуємо за ваш відгук!