Значення дії — це фундаментальне поняття у задачі багаторукого бандита. Воно відіграє ключову роль у різних алгоритмах, зокрема epsilon-жадібному та методі верхньої довірчої межі. Основна мета значення дії — надати оцінку очікуваної винагороди при виборі певної дії. Це схоже на значення стан-дія, але не залежить від стану через безстанову природу задачі багаторукого бандита.

Визначення значення дії

Формально значення дії, що позначається як $Q(a)$, представляє очікувану винагороду за вибір дії $a$:

де:

• $R$ — отримана винагорода;
• $A$ — обрана дія.

Оскільки справжній розподіл винагород зазвичай невідомий, необхідно оцінювати $Q(a)$ на основі спостережуваних даних.

Оцінювання значень дій

Існує кілька способів оцінити $Q(a)$ на основі спостережуваних винагород. Найпоширенішим методом є оцінка середнього зразка, яка обчислює середню винагороду, отриману за вибір дії $a$ до моменту часу $t$:

де:

• $Q_t(a)$ — оцінене значення дії $a$ на кроці часу $t$;
• $N_t(a)$ — кількість разів, коли дія $a$ була обрана до моменту часу $t$;
• $R_i$ — винагорода, отримана в кожному випадку, коли була виконана дія $a$.

У міру накопичення більшої кількості зразків ця оцінка збігається до істинної очікуваної винагороди $Q_*(a)$ за умови, що розподіл винагород залишається стаціонарним.

Правило інкрементного оновлення

Хоча наведена вище формула може бути використана для оцінки значень дій, вона вимагає зберігання всіх попередніх винагород і повторного обчислення їх суми на кожному кроці. Завдяки інкрементним оновленням це стає непотрібним. Формулу для інкрементних оновлень можна вивести так:

де для деякої дії:

• $Q_k$ — це оцінка $k$-ої винагороди, яку можна виразити як середнє перших $k-1$ винагород;
• $R_k$ — це фактична $k$-а винагорода.

Інтуїція

Знаючи оцінку $k$-ої винагороди, $Q_k$, і фактичну $k$-у винагороду, $R_k$, можна виміряти похибку як різницю між цими значеннями. Далі наступну оцінку можна обчислити, трохи скоригувавши попередню оцінку у напрямку фактичної винагороди, щоб зменшити похибку.

Ця інтуїція приводить до іншої формули, яка виглядає так:

де $\alpha$ — це параметр розміру кроку, що визначає швидкість навчання. Як і в попередній формулі, альфа може бути $\frac1k$, і це призведе до оцінки за середнім зразком. Альтернативно, часто використовується стала $\alpha$, оскільки вона не потребує додаткового простору (для зберігання кількості виборів дії) і дозволяє адаптуватися до нестабільних середовищ, надаючи більшу вагу останнім спостереженням.

Оптимістична ініціалізація

На початку процесу навчання оцінки значень дій можуть суттєво відрізнятися, що може призвести до передчасної експлуатації. Це означає, що агент може занадто рано використовувати свої початкові знання, віддаючи перевагу субоптимальним діям на основі обмеженого досвіду. Щоб зменшити цю проблему та стимулювати початкове дослідження, однією з простих та ефективних технік є оптимістична ініціалізація.

При оптимістичній ініціалізації значення дій ініціалізуються відносно високими значеннями (наприклад, $Q_0(a) = 1$ замість 0). Такий підхід створює враження, що всі дії спочатку перспективні. У результаті агент мотивований дослідити кожну дію кілька разів, перш ніж зупинитися на найкращому виборі. Ця техніка є найбільш ефективною у поєднанні з постійним розміром кроку.