Алгоритм SARSA

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

Ця назва означає, що оновлення Q-функції залежить від поточного стану агента SШаблон:Sub, дії AШаблон:Sub, яку агент обирає, винагороди R, яку отримує агент за вибір цієї дії, стану SШаблон:Sub, в який переходить агент після виконання цієї дії, та, нарешті, наступної дії АШаблон:Sub, яку агент обирає виходячи зі свого нового стану. Скорочення букв (sШаблон:Sub, aШаблон:Sub, rШаблон:Sub, sШаблон:Sub, aШаблон:Sub) і дає назву SARSA. Деякі автори використовують інший підхід і записують набір букв у вигляді (sШаблон:Sub, aШаблон:Sub, rШаблон:Sub, sШаблон:Sub, aШаблон:Sub), залежно від того, за який крок агента формально дається винагорода. В решті статті використовується перша домовленість.

Алгоритм

$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]$

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

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

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

Коефіцієнт швидкості навчання (Шаблон:Mvar)

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

Коефіцієнт знецінювання (Шаблон:Mvar)

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

Початкові умови (Шаблон:Math)

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