В Стэнфордском университете в рамках курса CS234 прошла лекция, посвященная проблеме «быстрого» или эффективного по данным обучения с подкреплением (Reinforcement Learning). Профессор Эмма Бранскилл объясняет, почему в реальных задачах — от медицины до образования — мы не можем полагаться на бесконечные симуляции, и как математический принцип «оптимизма в условиях неопределенности» позволяет алгоритмам принимать лучшие решения при минимальном количестве проб и ошибок.
⚖️ Эффективность данных против вычислительной мощности 0:06
В области машинного обучения часто происходит смешение понятий вычислительной эффективности и эффективности использования данных. По мнению профессора Бранскилл, это разделение критически важно для понимания того, где и как можно применять RL-алгоритмы.
В симуляторах, таких как Atari или среды MuJoCo, время вычислений фактически эквивалентно данным. Если у вас есть мощный компьютер, вы можете генерировать бесконечное количество игровых сессий. Однако в реальном мире ситуация иная. Бранскилл выделяет несколько областей, где данные ограничены и дороги:
- Здравоохранение: мобильные вмешательства для контроля давления или лечения пациентов.
- Маркетинг: выбор объявлений для показа пользователям.
- Образование: адаптивные технологии обучения для студентов.
- Экология: выработка политики по сохранению дикой природы.
В этих случаях у исследователя может быть всего несколько сотен тысяч записей, что ничтожно мало по сравнению с миллионами итераций в AlphaGo. Поэтому главной задачей становится «выжимание» максимума информации из каждого взаимодействия с реальным миром.
🎰 Проблема многорукого бандита 11:10
Для изучения эффективности данных лектор предлагает начать с простейшей модели RL — задачи о многоруком бандите. Эта концепция, изучаемая с 1920-х годов, исключает понятие «состояний» (states) и фокусируется только на выборе действий (ручек).
[Image of the multi-armed bandit problem showing a player choosing between several slot machines with different reward distributions]
Представьте врача, выбирающего метод лечения перелома пальца из трех вариантов: хирургия, фиксация пластырем или отсутствие вмешательства. Каждый пациент — это новый шанс «дернуть за ручку». Бранскилл подчеркивает, что в базовой модели бандитов процессы считаются независимыми и стационарными: распределение вероятности успеха для каждого метода не меняется от пациента к пациенту.
Почему «жадный» алгоритм — это путь к провалу 17:01
Если алгоритм будет просто выбирать действие, которое кажется лучшим на основе текущего среднего результата (жадный подход), он рискует навсегда застрять на субоптимальном решении.
Как утверждает Бранскилл, если в начале эксперимента хирургия случайно даст плохой результат, а пластырь — хороший, жадный алгоритм больше никогда не вернется к хирургии, даже если она объективно эффективнее в 90% случаев. Это иллюстрирует фундаментальную необходимость исследования (exploration).
📉 Математика потерь: понятие «регрета» (Regret) 19:48
Для оценки качества алгоритмов в теории бандитов используется понятие регрета (сожаления) — это разница между наградой, которую агент мог бы получить, выбирая всегда оптимальное действие, и тем, что он получил на самом деле.
[Image of linear vs logarithmic regret growth over time, illustrating sublinear regret]
Профессор классифицирует типы роста регрета:
- Линейный регрет: агент совершает плохие действия бесконечно долго. Это происходит при использовании чисто жадного алгоритма или статичного $\epsilon$-greedy подхода.
- Константный регрет: идеальный случай, когда агент за конечное число шагов находит лучшее действие и далее не ошибается.
- Сублинейный регрет: (например, логарифмический) агент продолжает ошибаться, но всё реже и реже. Это цель большинства современных алгоритмов.
Бранскилл отмечает, что согласно классическим работам Лаи и Роббинса (1950-е гг.), нижняя граница регрета для любой задачи бандитов пропорциональна $\log
