Off-Policy Керування Методом Монте-Карло
У той час як on-policy методи навчаються, дотримуючись і вдосконалюючи одну й ту ж політику, off-policy методи пропонують інший підхід: вони навчаються щодо однієї політики (цільової політики), виконуючи іншу (поведінкову політику). Такий поділ є потужним — це дозволяє оцінювати або вдосконалювати цільову політику без необхідності фактично дотримуватися її під час збору даних.
Аналогія
Повернімося до магазину морозива з попереднього розділу. Ви та ваш друг заходите всередину, і знову на вибір три знайомі смаки: шоколад, ваніль і полуниця. Шоколад — ваш улюблений смак, і перша думка — замовити саме його. Але цей магазин для вас новий, і ви не впевнені, чи варто обирати шоколад. На щастя, ваш друг — відомий поціновувач морозива, який відвідав майже всі магазини міста. Ви запитуєте його думку. «Шоколад тут непоганий, — каже він, — але повір, полуниця — просто виняткова». Тож, спираючись на його досвід, ви вирішуєте відмовитися від звичного вибору й обрати полуницю.
Це рішення — покладатися на досвід іншого для прийняття власного вибору — і є сутністю off-policy методів. Ви намагаєтеся покращити власне прийняття рішень, використовуючи дані, зібрані під час поведінки іншого. Це все ще дослідження — але воно керується зовнішнім досвідом, а не власним.
Важливість вибірки
Оскільки агент дотримується поведінкової політики під час генерації епізоду, необхідно враховувати невідповідність між тим, що генерує поведінкова політика, і тим, що згенерувала б цільова політика. Саме тут застосовується важливість вибірки.
Важливе вибіркове зважування (importance sampling) надає спосіб скоригувати отримані під політикою поведінки виграші так, щоб вони були коректними оцінками для цільової політики.
Розглянемо траєкторію, яка починається з певного стану St і слідує певній політиці π до завершення епізоду в момент часу T. Зокрема, ми спостерігаємо:
At,St+1,At+1,...,STЯка ймовірність виникнення цієї траєкторії під політикою π? Вона залежить як від ймовірностей дій політики, так і від динаміки переходів середовища:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Тепер припустимо, що траєкторія насправді була згенерована іншою політикою — політикою поведінки b. Щоб коректно використати цю траєкторію для оцінки очікувань під цільовою політикою π, потрібно врахувати, наскільки більшою чи меншою була ймовірність цієї послідовності дій під π порівняно з b.
Тут і з'являється коефіцієнт важливого вибіркового зважування. Він визначається як відносна ймовірність траєкторії під двома політиками:
ρ=p(trajectory∣b)p(trajectory∣π)=k=t∏T−1b(Ak∣Sk)p(Sk+1∣Sk,Ak)π(Ak∣Sk)p(Sk+1∣Sk,Ak)=k=t∏T−1b(Ak∣Sk)π(Ak∣Sk)У підсумку, ймовірності переходів скорочуються, оскільки обидві політики діють в одному середовищі, і значення ρ залежить лише від політик, а не від середовища.
Чому це важливо
Коефіцієнт ρ показує, як потрібно переважити виграш Gt, отриманий під політикою поведінки, щоб він став незміщеною оцінкою того, яким би був виграш під цільовою політикою:
Eπ[Gt]=Eb[ρ⋅Gt]Іншими словами, навіть якщо дані були зібрані за допомогою b, ми все одно можемо оцінити очікувані виграші під π — за умови, що b надає ненульову ймовірність кожній дії, яку може вибрати π (умова покриття).
Практичні аспекти
Дисперсія вибіркового зважування
Використання вибіркового зважування (importance sampling) є концептуально простим. Ми коригуємо оцінку функції значення дії q(s,a), зважуючи кожну спостережувану віддачу відповідним коефіцієнтом вибіркового зважування. Найпростіша формула виглядає так:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)де:
- ρi(s,a) — коефіцієнт вибіркового зважування для i-ї траєкторії, що починається з (s,a);
- Returnsi(s,a) — віддача з цієї траєкторії;
- N(s,a) — кількість відвідувань (s,a).
Цей підхід називається звичайним вибірковим зважуванням. Він забезпечує несмещену оцінку q(s,a), але може мати дуже високу дисперсію, особливо коли поведінкова та цільова політики суттєво відрізняються.
Щоб зменшити дисперсію, можна використати більш стабільний варіант — зважене вибіркове зважування. Цей метод нормалізує ваги, що зменшує вплив великих коефіцієнтів і забезпечує стабільніше навчання:
q(s,a)=∑i=0N(s,a)ρi(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)У цій версії чисельник залишається зваженою сумою віддач, але знаменник тепер — сума ваг вибіркового зважування, а не проста кількість.
Ця оцінка стає зміщеною, але зміщення зменшується зі збільшенням кількості вибірок. На практиці зважене вибіркове зважування є кращим через значно меншу дисперсію та вищу числову стабільність.
Політики
Як і у випадку on-policy, використаємо ε-жадібні політики для цільової політики π(a∣s) та поведінкової політики b(a∣s).
На перший погляд здається природним зробити цільову політику повністю жадібною — зрештою, наша кінцева мета — жадібна політика. Однак на практиці це створює серйозну проблему: якщо на будь-якому кроці π(a∣s)=0 для дії, яку фактично виконала поведінкова політика, коефіцієнт важливості ρ стає нульовим, і решта епізоду фактично відкидається.
Використовуючи мале ε (наприклад, ε=0.01) у цільовій політиці, ми гарантуємо, що π(a∣s)>0 для кожної дії, тому ρ ніколи не обнуляється посеред епізоду. Після завершення навчання легко перетворити отриману ε‑жадібну політику на строго жадібну. Як і при on‑policy навчанні, у поведінковій політиці слід використовувати спадання ε, але цього разу це переважно потрібно для числової стабільності, оскільки ρ все ще може стати нульовим посеред епізоду через особливості представлення чисел у комп'ютерах.
Псевдокод
Дякуємо за ваш відгук!
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Can you explain the difference between ordinary and weighted importance sampling in more detail?
Why does using a fully greedy target policy cause problems in off-policy learning?
Can you summarize the key advantages of off-policy methods compared to on-policy methods?
Awesome!
Completion rate improved to 2.7
Off-Policy Керування Методом Монте-Карло
Свайпніть щоб показати меню
У той час як on-policy методи навчаються, дотримуючись і вдосконалюючи одну й ту ж політику, off-policy методи пропонують інший підхід: вони навчаються щодо однієї політики (цільової політики), виконуючи іншу (поведінкову політику). Такий поділ є потужним — це дозволяє оцінювати або вдосконалювати цільову політику без необхідності фактично дотримуватися її під час збору даних.
Аналогія
Повернімося до магазину морозива з попереднього розділу. Ви та ваш друг заходите всередину, і знову на вибір три знайомі смаки: шоколад, ваніль і полуниця. Шоколад — ваш улюблений смак, і перша думка — замовити саме його. Але цей магазин для вас новий, і ви не впевнені, чи варто обирати шоколад. На щастя, ваш друг — відомий поціновувач морозива, який відвідав майже всі магазини міста. Ви запитуєте його думку. «Шоколад тут непоганий, — каже він, — але повір, полуниця — просто виняткова». Тож, спираючись на його досвід, ви вирішуєте відмовитися від звичного вибору й обрати полуницю.
Це рішення — покладатися на досвід іншого для прийняття власного вибору — і є сутністю off-policy методів. Ви намагаєтеся покращити власне прийняття рішень, використовуючи дані, зібрані під час поведінки іншого. Це все ще дослідження — але воно керується зовнішнім досвідом, а не власним.
Важливість вибірки
Оскільки агент дотримується поведінкової політики під час генерації епізоду, необхідно враховувати невідповідність між тим, що генерує поведінкова політика, і тим, що згенерувала б цільова політика. Саме тут застосовується важливість вибірки.
Важливе вибіркове зважування (importance sampling) надає спосіб скоригувати отримані під політикою поведінки виграші так, щоб вони були коректними оцінками для цільової політики.
Розглянемо траєкторію, яка починається з певного стану St і слідує певній політиці π до завершення епізоду в момент часу T. Зокрема, ми спостерігаємо:
At,St+1,At+1,...,STЯка ймовірність виникнення цієї траєкторії під політикою π? Вона залежить як від ймовірностей дій політики, так і від динаміки переходів середовища:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Тепер припустимо, що траєкторія насправді була згенерована іншою політикою — політикою поведінки b. Щоб коректно використати цю траєкторію для оцінки очікувань під цільовою політикою π, потрібно врахувати, наскільки більшою чи меншою була ймовірність цієї послідовності дій під π порівняно з b.
Тут і з'являється коефіцієнт важливого вибіркового зважування. Він визначається як відносна ймовірність траєкторії під двома політиками:
ρ=p(trajectory∣b)p(trajectory∣π)=k=t∏T−1b(Ak∣Sk)p(Sk+1∣Sk,Ak)π(Ak∣Sk)p(Sk+1∣Sk,Ak)=k=t∏T−1b(Ak∣Sk)π(Ak∣Sk)У підсумку, ймовірності переходів скорочуються, оскільки обидві політики діють в одному середовищі, і значення ρ залежить лише від політик, а не від середовища.
Чому це важливо
Коефіцієнт ρ показує, як потрібно переважити виграш Gt, отриманий під політикою поведінки, щоб він став незміщеною оцінкою того, яким би був виграш під цільовою політикою:
Eπ[Gt]=Eb[ρ⋅Gt]Іншими словами, навіть якщо дані були зібрані за допомогою b, ми все одно можемо оцінити очікувані виграші під π — за умови, що b надає ненульову ймовірність кожній дії, яку може вибрати π (умова покриття).
Практичні аспекти
Дисперсія вибіркового зважування
Використання вибіркового зважування (importance sampling) є концептуально простим. Ми коригуємо оцінку функції значення дії q(s,a), зважуючи кожну спостережувану віддачу відповідним коефіцієнтом вибіркового зважування. Найпростіша формула виглядає так:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)де:
- ρi(s,a) — коефіцієнт вибіркового зважування для i-ї траєкторії, що починається з (s,a);
- Returnsi(s,a) — віддача з цієї траєкторії;
- N(s,a) — кількість відвідувань (s,a).
Цей підхід називається звичайним вибірковим зважуванням. Він забезпечує несмещену оцінку q(s,a), але може мати дуже високу дисперсію, особливо коли поведінкова та цільова політики суттєво відрізняються.
Щоб зменшити дисперсію, можна використати більш стабільний варіант — зважене вибіркове зважування. Цей метод нормалізує ваги, що зменшує вплив великих коефіцієнтів і забезпечує стабільніше навчання:
q(s,a)=∑i=0N(s,a)ρi(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)У цій версії чисельник залишається зваженою сумою віддач, але знаменник тепер — сума ваг вибіркового зважування, а не проста кількість.
Ця оцінка стає зміщеною, але зміщення зменшується зі збільшенням кількості вибірок. На практиці зважене вибіркове зважування є кращим через значно меншу дисперсію та вищу числову стабільність.
Політики
Як і у випадку on-policy, використаємо ε-жадібні політики для цільової політики π(a∣s) та поведінкової політики b(a∣s).
На перший погляд здається природним зробити цільову політику повністю жадібною — зрештою, наша кінцева мета — жадібна політика. Однак на практиці це створює серйозну проблему: якщо на будь-якому кроці π(a∣s)=0 для дії, яку фактично виконала поведінкова політика, коефіцієнт важливості ρ стає нульовим, і решта епізоду фактично відкидається.
Використовуючи мале ε (наприклад, ε=0.01) у цільовій політиці, ми гарантуємо, що π(a∣s)>0 для кожної дії, тому ρ ніколи не обнуляється посеред епізоду. Після завершення навчання легко перетворити отриману ε‑жадібну політику на строго жадібну. Як і при on‑policy навчанні, у поведінковій політиці слід використовувати спадання ε, але цього разу це переважно потрібно для числової стабільності, оскільки ρ все ще може стати нульовим посеред епізоду через особливості представлення чисел у комп'ютерах.
Псевдокод
Дякуємо за ваш відгук!