🤖 Навігатор робота — ітерація значень MDP наживо

Ітерація значень — це модельний алгоритм динамічного програмування для розв'язання марковського процесу прийняття рішень (MDP): простір станів S, простір дій A, відома модель переходів P(s'|s,a), функція винагороди R(s,a,s') та коефіцієнт дисконтування γ. Починаючи з довільної функції значення V(s), він багаторазово застосовує оновлення оптимальності Беллмана V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] до всіх станів одночасно (синхронний прохід). Оскільки це оновлення є стискаючим відображенням при γ<1, повторні проходи доведено збігаються до єдиної оптимальної функції значення V*, з якої безпосередньо можна прочитати оптимальну політику π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')].

Ітерація значень є модельною: вона вимагає, щоб імовірності переходів P(s'|s,a) та функція винагороди R(s,a,s') були відомі заздалегідь, і обчислює точне математичне сподівання за кожним можливим результатом кожної дії в кожному стані на кожному проході — жодної симуляції чи дослідження середовища взагалі не потрібно. Q-навчання (розглянуте в окремій симуляції навчання з підкріпленням на цьому сайті) є безмодельним: агент не знає P чи R заздалегідь, тож він повинен реально діяти в середовищі, спостерігати вибіркові переходи (s, a, r, s') і поступово оновлювати Q(s,a) за правилом часової різниці Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)]. Ітерація значень збігається до точного V* за обмежену кількість проходів за наявності моделі; Q-навчання збігається лише асимптотично, через дослідження методом спроб і помилок, і взагалі не потребує явної моделі переходів. Ця симуляція навмисно реалізує модельний випадок, щоб чітко розрізнити ці два сімейства алгоритмів.

Реальні роботи та фізичні агенти рідко виконують дію ідеально — колеса ковзають, датчики дрейфують, а підлога нерівна. Ця симуляція моделює це класичною стохастичною моделлю переходів: вибір руху в заданому напрямку вдається з імовірністю P(намічений) (можна налаштувати, за замовчуванням 0.80), а решта ймовірності порівну розподіляється між відхиленням на 90° ліворуч і на 90° праворуч від наміченого напрямку. Оновлення Беллмана підсумовує всі три можливі результати, зважені за їхніми ймовірностями, що якраз і робить це справжнім MDP, а не детермінованим пошуком найкоротшого шляху — оптимальна політика мусить враховувати ризик небажаного зісковзування в стіну чи перешкоду.

Три складові винагороди разом визначають R(s,a,s'): невелика негативна вартість кроку (за замовчуванням −0.04), що стягується за кожен нетермінальний рух і підштовхує оптимальну політику до коротших шляхів; штраф за удар об перешкоду/стіну (за замовчуванням −0.75), що стягується щоразу, коли перехід блокується стіною, перешкодою чи межею сітки, і підштовхує політику зберігати запас безпеки навколо перешкод, особливо коли переходи зашумлені; та термінальна винагорода за ціль (+1), отримана при вході в клітинку цілі, що взагалі й робить досягнення цілі вартим уваги. Ітерація значень поширює всі три складові через оновлення Беллмана, тож клітинки поблизу цілі першими набувають високих значень, і цей сигнал високого значення поширюється назад, прохід за проходом, доки кожен досяжний стан не отримає точну оцінку своєї довгострокової очікуваної віддачі.

Кожен синхронний прохід записує максимальну абсолютну зміну значення будь-якого стану, max_s |V_new(s) − V_old(s)|, і симуляція будує графік цієї величини в логарифмічному масштабі залежно від номера проходу. Оскільки оператор оптимальності Беллмана є γ-стисканням, ця послідовність максимальних дельт гарантовано монотонно зменшується до нуля; симуляція оголошує збіжність, щойно значення падає нижче 1e-4. У цей момент V(s) перебуває в межах невеликої, обмеженої похибки від справжнього V*(s), а жадібна політика, вилучена з нього, π(s) = argmax_a Q(s,a), є оптимальною політикою для налаштованого MDP.

Так. γ контролює, наскільки на значення стану впливають винагороди через багато кроків у майбутньому: при γ, близькому до 1, віддалені винагороди за ціль поширюються майже без ослаблення по всій сітці, тож оптимальна політика планує далеко наперед і готова робити довші, безпечніші обходи перешкод. При γ, ближчому до 0.5, майбутні винагороди дисконтуються різко, тож політика стає короткозорою — вона може прийняти коротший, але ризикованіший шлях повз перешкоду, бо дисконтована цінність досягнення цілі на кілька кроків пізніше не набагато перевищує цінність досягнення її на крок раніше. γ також контролює швидкість збіжності: менше γ змушує оператор Беллмана стискати швидше, тож нижчі коефіцієнти дисконтування зазвичай збігаються за меншу кількість проходів.