Введение в отбор проб Томпсона | Обучение с подкреплением
Обучение с подкреплением - это ветвь машинного обучения, также называемая онлайн-обучением. Он используется, чтобы решить, какое действие предпринять в момент t + 1 на основе данных до момента времени t. Эта концепция используется в приложениях искусственного интеллекта, таких как ходьба. Популярным примером обучения с подкреплением является шахматный движок. Здесь агент принимает решение о серии ходов в зависимости от состояния доски (окружающей среды), а награда может быть определена как выигрыш или проигрыш в конце игры.
Выборка Томпсона (апостериорная выборка или сопоставление вероятностей) - это алгоритм для выбора действий, которые решают дилемму разведки-эксплуатации в проблеме многорукого бандита . Действия выполняются несколько раз и называются разведкой. Он использует обучающую информацию, которая оценивает предпринятые действия, а не дает инструкции, предлагая правильные действия. Это то, что создает потребность в активном исследовании, в явном поиске хорошего поведения методом проб и ошибок. В зависимости от результатов этих действий автомат получает вознаграждение (1) или штраф (0) за это действие. Дальнейшие действия выполняются, чтобы максимизировать вознаграждение, которое может улучшить производительность в будущем. Предположим, роботу нужно собрать несколько банок и положить в контейнер. Каждый раз, когда он кладет банку в контейнер, он запоминает, какие шаги выполняются, и тренируется выполнять задачу с большей скоростью и точностью (вознаграждение). Если робот не может поместить банку в контейнер, он не запомнит эту процедуру (следовательно, скорость и производительность не улучшатся) и будет считаться штрафом.
Преимущество Thompson Sampling состоит в том, что мы уменьшаем объем поиска по мере того, как мы получаем все больше и больше информации, что имитирует желаемый компромисс в проблеме, когда мы хотим получить как можно больше информации за меньшее количество запросов. Следовательно, этот алгоритм имеет тенденцию быть более «ориентированным на поиск», когда у нас меньше данных, и менее «ориентированным на поиск», когда у нас много данных.
Проблема многорукого бандита
Многорукий бандит является синонимом игрового автомата с множеством оружия. Выбор каждого действия похож на нажатие одного из рычагов игрового автомата, а награды - это выплаты за выигрыш джекпота. Посредством повторяющегося выбора действий вы должны максимизировать свой выигрыш, сосредоточив свои действия на лучших рычагах. Каждая машина обеспечивает различное вознаграждение в зависимости от распределения вероятности относительно среднего вознаграждения, характерного для данной машины. Не зная этих вероятностей, игрок должен максимизировать сумму вознаграждения, полученного в результате серии вытягиваний оружия. Если вы ведете оценки значений действий, то на любом временном шаге существует по крайней мере одно действие, оценочное значение которого является наибольшим. Мы называем это жадным действием. Аналогией с этой проблемой может быть реклама, отображаемая всякий раз, когда пользователь посещает веб-страницу. Оружие - это реклама, показываемая пользователям каждый раз, когда они подключаются к веб-странице. Каждый раз, когда пользователь подключается к странице, делает обход. В каждом раунде мы выбираем одно объявление для показа пользователю. В каждом раунде n, ad i дает вознаграждение ri (n) ε {0, 1}: ri (n) = 1, если пользователь нажимал на объявление i, 0, если пользователь этого не делал. Целью алгоритма будет максимальное вознаграждение. Другая аналогия - это доктор, выбирающий между экспериментальным лечением ряда тяжелобольных пациентов. Каждый выбор действия - это выбор лечения, а каждая награда - это выживание или благополучие пациента.
Алгоритм 
Некоторые практические приложения