Компромисс обучение-применение

Материал из MachineLearning.

Версия от 21:35, 14 июля 2026; Said Mavletov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM Gemini и проверена участником Said Mavletov 01:35, 15 июля 2026 (MSD)


Компромисс обучение-применение (англ. exploration-exploitation tradeoff) — это фундаментальная дилемма в теории принятия решений и машинном обучении, возникающая в условиях, когда агент должен выбирать между исследованием среды для сбора новых знаний и использованием уже имеющейся информации для максимизации выгоды.

Данная проблема является центральной для задач управления в условиях неопределенности, включая задачи о многоруком бандите (англ. multi-armed bandit) и марковские процессы принятия решений. Нахождение баланса между этими стратегиями необходимо для разработки рекомендательных систем, проведения адаптивных клинических испытаний и управления автономными агентами.

Содержание

История исследований

  • Статистические истоки: В 1933 году Уильям Томпсон (William R. Thompson) опубликовал работу, которая позднее стала математической основой алгоритма сэмплирования Томпсона (англ. Thompson sampling).
  • Формализация бандитов: Герберт Роббинс (Herbert Robbins) в 1952 году строго сформулировал задачу последовательного планирования экспериментов, заложив фундамент для анализа этого компромисса.
  • Индексы Гиттинса: В 1979 году Джон Гиттинс доказал существование оптимального решения для байесовской постановки задачи бандита с дисконтированием, введя так называемые индексы Гиттинса.
  • Современный этап: Развитие теории обучения с подкреплением (работы Ричарда Саттона и Эндрю Барто) и потребности интернет-индустрии привели к широкому внедрению алгоритмов балансировки, дополняющих классическое A/B-тестирование.

Математическая постановка задачи

Простейшей моделью для анализа компромисса является стохастический многорукий бандит. Агент на каждом шаге t \in \{1, \dots, T\} выбирает действие a_t, получая вознаграждение r_t с неизвестным математическим ожиданием \mu_{a_t}.

Цель агента — минимизировать совокупное сожаление (англ. cumulative regret) R_T, которое в стандартной литературе определяется как: R_T = \mathbb{E} \left[ \sum_{t=1}^T (\mu^* - r_t) \right] = \sum_{t=1}^T (\mu^* - \mu_{a_t}) где \mu^* — математическое ожидание оптимального действия. Для достижения цели агент должен балансировать между исследованием (поиском \mu^*) и использованием (выбором действия с наибольшим \mu).

Основные методы решения

Жадная и \varepsilon-жадная стратегии

  • Жадная стратегия: Агент всегда выбирает действие с максимальной текущей оценкой вознаграждения. Стратегия подвержена риску застревания в локальном оптимуме.
  • \varepsilon-жадная стратегия: С вероятностью 1-\varepsilon агент выбирает лучшее известное действие, а с вероятностью \varepsilon совершает случайный выбор.

Оптимизм в условиях неопределенности (UCB)

Алгоритм UCB (Upper Confidence Bound) выбирает действие, максимизирующее верхнюю доверительную границу: A_t = \arg\max_a \left( Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right) При выполнении определенных предположений алгоритм UCB1 обладает логарифмической верхней оценкой ожидаемого сожаления.

Сэмплирование Томпсона

Байесовский подход, где агент поддерживает распределение вероятностей параметров среды и на каждом шаге выбирает действие согласно вероятности того, что оно является оптимальным.

Контекстные бандиты

В задачах с признаками пользователя или среды используются контекстные бандиты (англ. contextual bandits), такие как алгоритмы LinUCB или NeuralUCB, учитывающие контекст для более точного выбора стратегии.

Обобщение на сложные среды

В марковских процессах принятия решений (MDP) исследование осложняется тем, что действие влияет не только на мгновенную награду, но и на распределение будущих состояний.

  • Поиск в дереве Монте-Карло (MCTS): Использует принципы UCB для эффективного поиска в пространстве возможных будущих состояний (успешно применяется в AlphaGo).
  • Внутренняя мотивация: В глубоком обучении агентам задают дополнительную «внутреннюю» награду за посещение новых, неожиданных состояний, стимулируя любопытство.

Современные проявления

  • Рекомендательные системы: Платформы (например, YouTube) балансируют между показом знакомого контента и предложением новых категорий.
  • Клинические испытания: Адаптивный дизайн на основе бандитов позволяет максимизировать количество пациентов, получающих наиболее эффективное лечение в ходе испытаний.
  • Динамическое ценообразование: Сервисы тестируют готовность рынка платить, корректируя цены в режиме реального времени.

Литература

  • Саттон Р. С., Барто Э. Дж. Обучение с подкреплением: Введение. — ДМК Пресс, 2020. — ISBN 978-5-97060-845-6
  • Lattimore T., Szepesvári C. Bandit Algorithms. — Cambridge University Press, 2020. — ISBN 978-1-10848-682-8
  • Lai T. L., Robbins H. Asymptotically efficient adaptive allocation rules // Advances in Applied Mathematics. — 1985. — Т. 6. — № 1. — С. 4–22.
  • Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed Bandit Problem // Machine Learning. — 2002. — Т. 47. — С. 235–256.
  • Thompson W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples // Biometrika. — 1933. — Т. 25. — № 3/4. — С. 285–294.
  • Gittins J. C. Bandit Processes and Dynamic Allocation Indices // Journal of the Royal Statistical Society. — 1979. — Т. 41. — № 2. — С. 148–164.
Источник — «http://recognition.su/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%80%D0%BE%D0%BC%D0%B8%D1%81%D1%81_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5-%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5»