Значення дії — це фундаментальне поняття у задачі багаторукого бандита. Воно відіграє ключову роль у різних алгоритмах, зокрема у 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). Такий підхід створює враження, що всі дії спочатку перспективні. У результаті агент мотивований дослідити кожну дію кілька разів, перш ніж зупинитися на найкращому виборі. Ця техніка є найбільш ефективною у поєднанні з постійним кроком оновлення.