Лекція 13. Навчання з підкріпленням. 1. Зміст навчання з підкріпленням. Розглядається ситуація багатокрокової взаємодії агента з наперед невідомим динамічним середовищем. В процесі цієї взаємодії агент самостійно навчається найкращій (оптимальній) поведінці шляхом спроб та помилок. При цьому розробник вказує агенту що вважати найкращою поведінкою і не вказує як її досягнути. На кожному кроці взаємодії агент обирає та реалізує дію з множини усіх доступних на цьому кроці дій і отримує відгук середовища на цю дію (підкріплення). Приклад: нагорода або покарання. Зміст навчання з підкріпленням полягає у дослідженні агентом характеристик середовища та використанні результатів цього дослідження для вибору дій в наступних кроках взаємодії (набуття та використання досвіду).
- відмінність від навчання під керуванням (supervised learning)
- стратегія (policy): спосіб відображення (mapping) виміряного стану середовища у дію - функція вийграшу (reward function): миттєва оцінка ефективності дій (вийграш) - функція оцінки (value function): довготермінова оцінка ефективності дій (як акумулювати вийграші) - модель середовища (environment model): планування, прогнозування 2. Класифікація задач самонавчання 1. за моделлю оптимальної поведінки 1.1. модель з обмеженим горизонтом (finite-horizon model) 1.2. модель з необмеженим горизонтом (infinite horizon model) 1.3. модель із середнім виграшем (average-reward model) 2. за складністю середовища 2.1. стаціонарне випадкове середовище 2.2. випадкове середовище з переключенням 2.3. марковський процес прийняття рішень (MDP) 3. за оцінкою ефективності навчання 3.1. кінцева сходимість до оптимльної поведінки (eventual convergence to optimal) 3.2. швидкість сходимості до оптимальної поведінки (speed of convergence to optimal) 3.3. втрати в порівнянні з оптимальною від самого початку поведінкою (regret) 4. за способом використання досвіду 4.1. без моделювання середовища (model-free) 4.2. з моделюванням середовища (model-based) 3. Метод зваженної оцінки дій (Action-Value Method). метод зваженної оцінки дій має обмеження, оскількі із збільшенням кількості кроків навчання (k) збільшуєься об’єм необхідної для обчислень пам’яті та об’єми самих обчислень рішення цієї проблеми полягає у модифікації основного рівняння методу зваженної оцінки дій в такий спосіб, щоб зробити його рекурсивним модифікація ( потрібна пам’ять лише для Qk і k загальне правило навчання з підкріпленням 4. Марковський процес прийняття рішень (Markov Decision Processes). В загальному випадку проблема RL полягає в тому, що від дії агента залежить не тільки його біжучий виграш, але і наступний стан середовища, в який воно перейде внаслідок цієї дії. Таке середовище можна розглядати як мережу (ланцюжок Маркова) стаціонарних випадкових середовищ (n-armed bandid problems). При цьому агент, обираючи наступну дію, має одночасно брати до уваги очікуваний виграш (r) та можливу зміну стану середовища (s). Внаслідок цього алгоритм RL повинен враховувати відкладене у часі підкріплення (delayed reinforcement): агент навчається найкращми діям, враховуючи виграші, які він отримує в скіль завгодно далекому майбутньому. Тобто відслідковується той факт, що біжучий виграш агента залежить не лише від дії на даному кроці, але й від усіх попердніх дій. Проблема навчання з відкладеним у часі підкріпленням описується Марківським процесом прийняття рішень (MDP). MDP – це четвірка <S,A,R,T> S – множина станів (в загальному випадку нескінченна) A – множина доступних агенту дій R – функція виграшу R: S(A(( (визначає схему (розподіл) виграшів для кожного стану) T – функція переходу T: S(A(П(S) (визначає розподіл ймовірностей переходу середовища з одного стану в інший під впливом дії агента, тобо це функція від біжучого стану середовища і обраної агентом дії: T(s,a,s')). Процес є марковським, якщо розподіл ймовірностей переходу (функція переходу) не залежить від усіх поперндіх станів середовища та дій агента. Вирішення MDP полягає у знаходженні оптимальної поведінки (policy) (: S(A, яка відображає стани середовища у дії агента і максимізує значення функції оцінки, що відповідає обраній моделі оптимальності (як правило, розглядається модель з необмеженим горизонтом та коефіціентом послаблення минулих виграшів). 5. Навчання зя методом розрізнення у часі (Temporal Difference Learning). Основна проблема: функція розподілу ймовірностей переходу між станами T(s,a,s') невідома агенту наперед (тобто невідома модель середовища). Т.ч. агенту необхідно досліджувати (explore) не тільки схему виграшів для кожного стану, але і вигляд функції переходу. При цьому агент вирішує проблему розподілення виграшу у часі (temporal credit assignment): як визначити, що дія є вдалою, якщо вона має далекойдучі наслідки? або яка з обраних в минулому дій призвела до біжучого виграшу? Загальна ідея: кожному стану середовища ставиться у відповідність пердбачувана вага стану (estimated value of state) V(s), s(S. На кожному кроці взаємодії ця величина певним чином модифікується в такий спосіб, щоб гарантувати сходимість цієї величини з часом до наперед невідомої дійсної ваги стану V*(s). Значення V(s) модифікується на основі біжучого виграшу та передбачуваної ваги стану, в який перейшло середовище внаслідок реалізації обраної дії.
