Алгоритм SARSA

SARSA — алгоритм пошуку стратегії Марковського процесу вирішування, який використовується в області навчання з підкріпленням машинного навчання. Цей алгоритм було запропоновано Гевіном Руммері та Махесаном Ніранжаном у статті[1] з назвою «Modified Connectionist Q-Learning» (MCQ-L). Альтернативна назва SARSA, запропонована Річардом Саттоном, згадувалася лише як виноска.

Частина з циклу
Машинне навчання
та добування даних
Навчання з підкріпленням

Ця назва означає, що оновлення Q-функції залежить від поточного стану агента S1, дії A1, яку агент обирає, винагороди R, яку отримує агент за вибір цієї дії, стану S2, в який переходить агент після виконання цієї дії, та, нарешті, наступної дії А2, яку агент обирає виходячи зі свого нового стану. Скорочення букв (st, at, rt, st + 1, at + 1) і дає назву SARSA.[2] Деякі автори використовують інший підхід і записують набір букв у вигляді (st, at, rt + 1, st + 1, at + 1), залежно від того, за який крок агента формально дається винагорода. В решті статті використовується перша домовленість.

Алгоритм

За алгоритмом SARSA, агент взаємодіє з середовищем та оновлює стратегію згідно з виконаними діями, отже, цей алгоритм можна віднести до класу алгоритмів навчання за стратегією. Значення Q-функції для дії та стану оновлюється відповідно похибці, що регулюється за допомогою коефіцієнту швидкості навчання α. Значення Q-функції представляє сумарну винагороду, яку можна отримати за весь залишившийся час у межах цього епізоду, за умови виконання дії a в стані s, з додаванням знеціненої винагороди за виконання дій в наступному стані.

Деякі оптимізації алгоритму Q-навчання можуть бути застосовані і до SARSA.[3]

Гіперпараметри

Коефіцієнт швидкості навчання (α)

Коефіцієнт швидкості навчання визначає, наскільки отримана за дану ітерацію інформація змінює попередню інформацію. Коефіцієнт 0 змусить агента ніяк не навчитися, тоді як коефіцієнт 1 змусить агента враховувати лише інформацію, отриману за останню ітерацію алгоритму.

Коефіцієнт знецінювання (γ)

Коефіцієнт знецінювання (англ. discount factor) визначає важливість майбутніх винагород. Коефіцієнт 0 змушує агента враховувати лише поточну винагороду, тоді як коефіцієнт близький до 1, змусить намагатися досягти максимальної довго-строкової винагороди. Якщо коефіцієнт знецінювання дорівнює або перевищує 1, то значення -функції можуть розбігатися.

Початкові умови (Q(s0, a0))

Оскільки SARSA є ітераційним алгоритмом, він передбачає наявність початкових умов до того, як відбудеться перше оновлення. Низьке (нескінченне) початкове значення, також відоме як «оптимістичні початкові умови»,[4] може заохочувати дослідження: незалежно від того, які дії виконує агент, формула оновлення призводить до того, що наступні ітерації мають більш високі значення винагороди, ніж попередні, тим самим збільшуючи ймовірність їх вибору. У 2013 році була запропонована ідея використання першої винагороди r в якості початкових умов. При такому підході, після виконання агентом першої дії, отримана винагорода використовується як початкове значення Q. Що при фіксованих винагородах, дозволяє навчати відразу після першого кроку. Такий метод обирання початкових умов повторює поведінку людини в багатьох експериментах з бінарним вибором.[5]

Примітки
  1. Online Q-Learning using Connectionist Systems" by Rummery & Niranjan (1994)
  2. Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto (chapter 6.4)
  3. Wiering, Marco; Schmidhuber, Jürgen (1 жовтня 1998). Fast Online Q(λ). Machine Learning (англ.) 33 (1): 105–115. ISSN 0885-6125. doi:10.1023/A:1007562800292. Проігноровано невідомий параметр |doi-access= (довідка); Проігноровано невідомий параметр |s2cid= (довідка)
  4. 2.7 Optimistic Initial Values. incompleteideas.net. Процитовано 28 лютого 2018.
  5. Shteingart, H; Neiman, T; Loewenstein, Y (May 2013). The Role of First Impression in Operant Learning. J Exp Psychol Gen 142 (2): 476–88. PMID 22924882. doi:10.1037/a0029550. Архів оригіналу за 26 січня 2021. Процитовано 18 червня 2020.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.