- Политика LP-обновления для слабосвязанных марковских процессов принятия решений(arXiv)
Автор:Николя Гаст, Бруно Гауджал, Чен Ян
Аннотация: В этой работе мы предлагаем новую политику, называемую политикой LP-обновления, для слабосвязанных марковских процессов принятия решений с конечным горизонтом. Последние можно рассматривать как бандиты с несколькими ограничениями и несколькими действиями, и они обобщают классические задачи о беспокойных бандитах (которые представляют собой бандитов с одним ограничением и двумя действиями), широко изучаемые в литературе. Мы рассматриваем скейлинговую модель с N статистически идентичными плечами. Мы показываем, что наша политика LP-обновления становится асимптотически оптимальной со скоростью O(1/N−−√) для любой проблемы. Эту скорость можно повысить до O(1/N), если задача невырожденная, и даже до e−Ω(N), если, кроме того, задача допускает идеальное округление. Определение невырожденности расширяет то же понятие для классических неугомонных бандитов с двумя действиями. Используя это свойство, мы также обеспечиваем более эффективную реализацию политики LP-update. Мы иллюстрируем эффективность нашей политики на обобщенной задаче отбора кандидатов.
2.Интервальные марковские процессы принятия решений с непрерывными пространствами действий(arXiv)
Автор:Яннис Делимпалтадакис, Мортеза Лахиджанян, Мануэль Мазо-младший, Лука Лауренти
Аннотация: Интервальные марковские процессы принятия решений (IMDP) — это неопределенные марковские модели, в которых вероятности перехода относятся к интервалам. В последнее время наблюдается всплеск исследований по использованию IMDP в качестве абстракций стохастических систем для синтеза управления. Однако из-за отсутствия алгоритмов синтеза над IMDP с непрерывными пространствами действий пространство действий априори предполагается дискретным, что является ограничительным предположением для многих приложений. Руководствуясь этим, мы вводим IMDP непрерывного действия (caIMDP), где границы вероятностей перехода являются функциями переменных действия, и изучаем итерацию значений для максимизации ожидаемого совокупного вознаграждения. В частности, мы показываем, что решение задачи максимального-минимального значения, связанной с итерацией значений, эквивалентно решению |Q| макс задач, где |Q| - количество состояний caIMDP. Затем, используя простую форму этих максимальных задач, мы определяем случаи, когда итерация значений по caIMDP может быть решена эффективно (например, с помощью линейного или выпуклого программирования). Мы также получаем другие интересные сведения: например, в случае, когда множество действий A является многогранником, а границы перехода линейны, для оптимальности достаточно синтезировать IMDP дискретного действия, где действия являются вершинами A. Продемонстрируем наши результаты на численном примере. Наконец, мы включили краткое обсуждение использования caIMDP в качестве абстракций для синтеза управления.
3. Сложность марковских процессов принятия решений: теория и практика(arXiv)
Автор:Микеланджело Консерва, Пауло Раубер
Аннотация. Тщательный анализ эмпирических сильных и слабых сторон методов обучения с подкреплением в сложных (сложных) условиях необходим для вдохновения на инновации и оценки прогресса в этой области. В табличном обучении с подкреплением отсутствует устоявшийся стандартный выбор сред для проведения такого анализа, что отчасти связано с отсутствием широкого понимания богатой теории жесткости сред. Цель этой статьи состоит в том, чтобы раскрыть практическую полезность этой теории с помощью четырех основных вкладов. Во-первых, мы представляем систематический обзор теории твердости, который также определяет перспективные направления исследований. Во-вторых, мы представляем Colosseum, новаторский пакет, который позволяет проводить эмпирический анализ твердости и реализует принципиальный эталонный тест, состоящий из сред, которые различаются по различным показателям твердости. В-третьих, мы представляем эмпирический анализ, который дает новое понимание вычислимых показателей. Наконец, мы тестируем пять табличных агентов в нашем недавно предложенном тесте. Хотя продвижение теоретического понимания сложности в нетабличном обучении с подкреплением остается важным, наш вклад в табличное урегулирование задуман как твердый шаг к принципиальному нетабличному эталону. Соответственно, мы тестируем четыре агента в нетабличных версиях среды Colosseum, получая результаты, демонстрирующие общность табличных показателей твердости.
