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 0, a 0)$ )

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

Примітки

. Архів оригіналу за 8 червня 2013. Процитовано 18 червня 2020.
. Архів оригіналу за 5 липня 2020. Процитовано 18 червня 2020.
Wiering, Marco; Schmidhuber, Jürgen (1 жовтня 1998). (PDF). Machine Learning (англ.). 33 (1): 105—115. doi:10.1023/A:1007562800292. ISSN 0885-6125. S2CID 8358530. Архів оригіналу (PDF) за 30 жовтня 2018. Процитовано 23 листопада 2021.
Arguments against myopic training - LessWrong. www.lesswrong.com (англ.). Процитовано 13 листопада 2022.
. incompleteideas.net. Архів оригіналу за 5 липня 2020. Процитовано 28 лютого 2018.
Shteingart, H; Neiman, T; Loewenstein, Y (May 2013). (PDF). J Exp Psychol Gen. 142 (2): 476—88. doi:10.1037/a0029550. PMID 22924882. Архів оригіналу (PDF) за 26 січня 2021. Процитовано 18 червня 2020.

[1] . Архів оригіналу за 8 червня 2013. Процитовано 18 червня 2020.

[2] . Архів оригіналу за 5 липня 2020. Процитовано 18 червня 2020.

[3] Wiering, Marco; Schmidhuber, Jürgen (1 жовтня 1998). (PDF). Machine Learning (англ.). 33 (1): 105—115. doi:10.1023/A:1007562800292. ISSN 0885-6125. S2CID 8358530. Архів оригіналу (PDF) за 30 жовтня 2018. Процитовано 23 листопада 2021.

[4] Arguments against myopic training - LessWrong. www.lesswrong.com (англ.). Процитовано 13 листопада 2022.

[5] . incompleteideas.net. Архів оригіналу за 5 липня 2020. Процитовано 28 лютого 2018.

[6] Shteingart, H; Neiman, T; Loewenstein, Y (May 2013). (PDF). J Exp Psychol Gen. 142 (2): 476—88. doi:10.1037/a0029550. PMID 22924882. Архів оригіналу (PDF) за 26 січня 2021. Процитовано 18 червня 2020.