Алгоритм SARSA

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

Ця назва означає, що оновлення Q-функції залежить від поточного стану агента S₁, дії A₁, яку агент обирає, винагороди R, яку отримує агент за вибір цієї дії, стану S₂, в який переходить агент після виконання цієї дії, та, нарешті, наступної дії А₂, яку агент обирає виходячи зі свого нового стану. Скорочення букв (s_t, a_t, r_t, s_{t + 1}, a_{t + 1}) і дає назву SARSA. Деякі автори використовують інший підхід і записують набір букв у вигляді (s_t, a_t, r_{t + 1}, s_{t + 1}, a_{t + 1}), залежно від того, за який крок агента формально дається винагорода. В решті статті використовується перша домовленість.

Алгоритм

$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, агент взаємодіє з середовищем та оновлює стратегію згідно з виконаними діями, отже, цей алгоритм можна віднести до класу алгоритмів навчання за поточною стратегією (англ. on-policy). Значення Q-функції для дії та стану оновлюється відповідно похибці, що регулюється за допомогою коефіцієнту швидкості навчання $\alpha$. Значення Q-функції представляє сумарну винагороду, яку можна отримати за весь залишившийся час у межах цього епізоду, за умови виконання дії a в стані s, з додаванням знеціненої винагороди за виконання дії в наступному стані.

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

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

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

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

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

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

Початкові умови (Q(s₀, a₀))

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