Разработан алгоритм UCB-NOM для задач с ненаблюдаемыми состояниями в марковских бандитах
Группа ученых опубликовала в arXiv препринт, посвященный задаче минимизации сожаления в марковских бандитах с ненаблюдаемыми состояниями. В таких системах агент не может напрямую видеть текущее состояние среды, что усложняет принятие решений. Работа также рассматривает случаи с ограниченными эпохами принятия решений.
Авторы вводят новое понятие — самодеградирующие марковские бандиты, обобщающие классическую модель. Для этого класса чистые политики (выбор одного оптимального рычага без переключений) оказываются асимптотически оптимальными. Однако если алгоритм редко переключает рычаги, его сожаление растет сверхлогарифмически — как ?(log(T)), где T — горизонт обучения.
Несмотря на принципиальную недостижимость логарифмического режима, исследователи предложили оптимистичный алгоритм UCB-NOM, вдохновленный знаменитым UCB. Он демонстрирует почти логарифмическое сожаление, что является значительным шагом вперед. Важно, что полученные оценки не зависят от числа состояний марковских цепей.
Если же имеется априорная информация о бандите, а именно — оценка функции смещения его рычагов, то UCB-NOM с соответствующей настройкой достигает сожаления O(log(T)). Кроме того, в наихудшем случае алгоритм гарантирует сожаление O(?(T log T)).
Результаты показывают, что ненаблюдаемость состояний не является критическим препятствием для самодеградирующих марковских бандитов. Разработка открывает новые возможности для применения методов обучения с подкреплением в задачах с частичной наблюдаемостью, таких как интернет-реклама или управление ресурсами.
Полный текст работы доступен на arXiv под номером 2606.27448. Код алгоритма авторы планируют опубликовать позже.
