- Оптимальное сожаление достижимо с постоянной приблизительной ошибкой вывода: усовершенствованная байесовская структура верхней доверительной границы (arXiv)
Автор: Цзыи Хуан, Генри Лам, Амирхоссейн Мейсами, Хаофэн Чжан.
Аннотация: Алгоритмы байесовских бандитов с приближенным байесовским выводом широко используются в реальных приложениях. Однако существует большое расхождение между превосходными практическими характеристиками этих подходов и их теоретическим обоснованием. Предыдущие исследования указывают только на отрицательный теоретический результат: выборка Томпсона может иметь линейное сожаление в наихудшем случае Ω(T) с постоянным порогом ошибки вывода, измеряемой одним α-расхождением. Чтобы восполнить этот пробел, мы предлагаем структуру Enhanced Bayesian Upper Confidence Bound (EBUCB), которая может эффективно решать проблемы бандитов при наличии приближенного вывода. Наш теоретический анализ показывает, что для многоруких бандитов Бернулли EBUCB может достичь оптимального порядка сожаления O (logT), если ошибка вывода, измеренная двумя различными α-расхождениями, меньше константы, независимо от того, насколько велика эта константа. Насколько нам известно, наше исследование дает первую теоретическую границу сожаления, которая лучше, чем o(T), в условиях постоянной ошибки приблизительного вывода. Кроме того, в соответствии с отрицательными результатами предыдущих исследований, мы показываем, что только одной ограниченной α-дивергенции недостаточно, чтобы гарантировать сублинейное сожаление.
2.Dyna-T: Dyna-Q и верхние доверительные границы, применяемые к деревьям (arXiv)
Автор: Тарек Файкал, Клаудио Зито.
Аннотация: В этой работе мы представляем предварительное исследование нового алгоритма под названием Dyna-T. В обучении с подкреплением (RL) агент планирования имеет собственное представление среды как модели. Чтобы найти оптимальную политику взаимодействия со средой, агент собирает опыт методом проб и ошибок. Опыт можно использовать для изучения лучшей модели или непосредственного улучшения функции ценности и политики. Как правило, Dyna-Q представляет собой гибридный подход, который на каждой итерации использует реальный опыт для обновления модели, а также функции ценности, при этом планируя свои действия с использованием смоделированных данных из своей модели. Однако процесс планирования требует значительных вычислительных ресурсов и сильно зависит от размерности пространства состояний-действий. Мы предлагаем построить Верхнее дерево достоверности (UCT) на смоделированном опыте и искать наилучшее действие, которое будет выбрано в процессе онлайн-обучения. Мы доказываем эффективность предложенного нами метода на серии предварительных тестов на трех тестовых средах от Open AI. В отличие от Dyna-Q, Dyna-T превосходит современные агенты RL в стохастических средах, выбирая более надежную стратегию выбора действий.
