У навчанні з підкріпленням агент або особа, яка приймає рішення, генерує свої навчальні дані, взаємодіючи зі світом. Агент повинен пізнати наслідки своїх дій методом проб і помилок, а не отримати чітке вказівку правильної дії.
Проблема багаторукого бандита
У Reinforcement Learning ми використовуємо проблему багаторукого бандита, щоб формалізувати поняття прийняття рішень в умовах невизначеності за допомогою k-armed bandit. Особа, яка приймає рішення, або агент присутній у Multi-Armed Bandit Problem, щоб вибирати між k-різними діями та отримує винагороду залежно від вибраної дії. Проблема бандита використовується для опису фундаментальних понять навчання з підкріпленням, таких як винагороди, часові кроки та цінності.
На зображенні вище зображений ігровий автомат, також відомий як бандит з двома важелями. Ми припускаємо, що кожен важіль має окремий розподіл винагород і є принаймні один важіль, який генерує максимальну винагороду.
Розподіл ймовірностей винагороди, що відповідає кожному важелю, різний і невідомий гравцеві (особі, яка приймає рішення). Таким чином, мета полягає в тому, щоб визначити, який важіль натиснути, щоб отримати максимальну винагороду після заданого набору випробувань.
Наприклад:
Уявіть випробування онлайн-реклами, де рекламодавець хоче виміряти рейтинг кліків трьох різних оголошень для того самого продукту. Щоразу, коли користувач відвідує веб-сайт, рекламодавець у випадковому порядку показує оголошення. Потім рекламодавець відстежує, чи натискає користувач оголошення чи ні. Через деякий час рекламодавець помічає, що одне оголошення працює краще за інші. Тепер рекламодавець повинен вирішити, чи залишитися з найефективнішою рекламою, чи продовжити рандомізоване дослідження.
Якщо рекламодавець показує лише одну рекламу, він більше не може збирати дані про дві інші реклами. Можливо, одна з інших реклам є кращою, але випадково вона виглядає гіршою. Якщо інші два оголошення гірші, то продовження дослідження може негативно вплинути на рейтинг кліків. Це рекламне випробування є прикладом прийняття рішень в умовах невизначеності.
У наведеному вище прикладі роль агента виконує рекламодавець. Рекламодавець має вибрати одну з трьох різних дій: відобразити перше, друге чи третє оголошення. Кожна реклама – це дія. Вибір цієї реклами приносить невідому винагороду. Нарешті, прибуток рекламодавця після реклами - це винагорода, яку отримує рекламодавець.
Дія-значення:
Щоб рекламодавець вирішив, яка дія найкраща, ми повинні визначити цінність виконання кожної дії. Ми визначаємо ці значення за допомогою функції дії-значення, використовуючи мову ймовірності. Значення вибору дії q*(а) визначається як очікувана винагорода Рt ми отримуємо під час виконання дії a з можливого набору дій.
Метою агента є максимізація очікуваної винагороди шляхом вибору дії, яка має найвищу цінність дії.
Оцінка цінності дії:
приклади коду c#
Оскільки значення вибору дії, тобто Q*(а) не відомий агенту, тому ми будемо використовувати вибірково-середній метод його оцінки.
Розвідка проти експлуатації:
'число Ейлера в java'
- Жадібна дія: коли агент вибирає дію, яка наразі має найбільшу оціночну цінність. Агент використовує свої поточні знання, обираючи жадібну дію. Нежадібна дія: коли агент не вибирає найбільшу оціночну вартість і жертвує негайною винагородою, сподіваючись отримати більше інформації про інші дії. Дослідження: дозволяє агенту покращити свої знання про кожну дію. Сподіваємось, це призведе до довгострокової вигоди. Експлуатація: дозволяє агенту вибрати жадібні дії, щоб спробувати отримати найбільшу винагороду за короткострокову вигоду. Суто жадібний вибір дій може призвести до неоптимальної поведінки.
Виникає дилема між розвідкою та розробкою, оскільки агент не може вибрати досліджувати та розробляти водночас. Тому ми використовуємо Верхня межа впевненості алгоритм для вирішення дилеми розвідка-розробка
Вибір дії з верхньою довірчою межею:
Вибір дії з верхньою довірчою межею використовує невизначеність в оцінках дії-вартості для збалансування розвідки та експлуатації. Оскільки існує невід’ємна невизначеність у точності оцінок цінності дії, коли ми використовуємо вибірковий набір винагород, тому UCB використовує невизначеність в оцінках, щоб стимулювати дослідження.
Qt(а) тут представлено поточну оцінку дій a вчасно t . Ми вибираємо дію, яка має найвищу оцінену цінність дії плюс термін дослідження з верхньою довірчою межею.
Q(A) на зображенні вище відображає поточну оцінку цінності дії для дії А . Дужки представляють довірчий інтервал Q*(А) який говорить про те, що ми впевнені, що фактична дія-цінність дії А лежить десь у цьому регіоні.
Нижня дужка називається нижньою межею, а верхня — верхньою. Ділянка між дужками - це довірчий інтервал, який представляє невизначеність в оцінках. Якщо регіон дуже малий, то ми стаємо дуже впевненими в фактичній цінності дії А близьке до нашої оціночної вартості. З іншого боку, якщо регіон великий, то ми не впевнені в цінності дії А близьке до нашої оціночної вартості.
The Верхня межа впевненості дотримується принципу оптимізму в умовах невизначеності, який передбачає, що якщо ми не впевнені щодо дії, ми повинні оптимістично припустити, що це правильна дія.
Наприклад, скажімо, ми маємо ці чотири дії з пов’язаними невизначеностями на зображенні нижче, наш агент не знає, яка дія найкраща. Отже, згідно з алгоритмом UCB, він оптимістично вибере дію, яка має найвищу верхню межу, тобто А . Роблячи це, ми або матимемо найвищу цінність і отримаємо найвищу винагороду, або взявши це, ми дізнаємося про дію, про яку найменше знаємо.
Припустимо, що після вибору дії А ми потрапляємо в стан, зображений на малюнку нижче. Цього разу дію обере УКБ Б оскільки Q(B) має найвищу верхню довірчу межу, оскільки його оцінка дії-цінності є найвищою, навіть якщо довірчий інтервал малий.
Спочатку UCB досліджує більше, щоб систематично зменшити невизначеність, але з часом його дослідження зменшується. Таким чином, ми можемо сказати, що UCB отримує в середньому більшу винагороду, ніж інші алгоритми, такі як Epsilon-greedy, Optimistic Initial Values тощо.