77
правок
Изменения
м
Нет описания правки
== Метод UCB (upper confidence bound) ==
Предыдущие алогритмы при принятии решений используют данные о среднем выигрыше. Проблема заключается в том, что если рука даёт выигрыш с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем считать самой выгодной рукой ту, которая на самом деле таковой не является.
Алгоритм верхнего доверительного интервала (''Upper confidence bound'' или просто UCB) - это семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять этим значениям выигрыша. В книге описывается один такой алгоритм - UCB.
Как и в softmax в UCB при выборе рук используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound, что и дало название алгоритму) значения выигрыша:
<tex>Q_a = average_arm_reward + arm_bonus</tex><br />
<tex>average_arm_reward</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.
<tex>arm_bonus</tex> - это бонусное значение, которые показывает, насколько недоисследована эта рука по сравнению с остальными. Он вычисляется следующим образом:
<tex>arm_bonus = \sqrt{\frac{2 \cdot \log{total_count}}{arm_count}} </tex>
<tex>total_count</tex> - это суммарное количество использований всех рук, а <tex>arm_count</tex> - это количество использований данной руки.
Доказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]
В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора руки, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждая из рук выбирается по одному разу (это нужно для того, чтобы можно было вычислить размер бонуса для всех рук). После этого в каждый момент времени выбирается рука с максимальным значением весового коэффициента.
Несмотря на это отсутствие случайности, результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные руки.
== Стратегия Softmax ==
Алгоритм мягкого максимума (softmax) - это чуть более сложный алгоритм. Его основная идея - уменьшение потерь при исследовании за счёт более редкого выбора рук, которые дали маленький выигрыш в прошлом. Чтобы этого добиться для каждой руки вычисляется весовой коэффициент, на базе которого происходит выбор руки:
<tex>Q_a = \exp(average_arm_reward / temperature)</tex>
<tex>average_arm_reward</tex> - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.
temperature - это параметр, с помощью которого можно настраивать поведение алгоритма (он называется температура). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулю, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации).
Экспонента используется для того, чтобы данный вес был ненулевым даже у рук, выигрыш от которых пока нулевой.
Вероятность выбора руки равна отношению её весового коэффициента и сумме весовых коэффициентов всех рук. При выборе генерируется случайное число от 0 до 1, на основании которого произойдёт выбор конкретной руки.
Мягкий вариант компромисса "exploitation-exploration":<br />
* [https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html Задача о многоруком бандите]
* [http://www.machinelearning.ru/wiki/images/archive/3/35/20121120213057%21Voron-ML-RL-slides.pdf Обучение с подкреплением (Reinforcement Learning) К.В.Воронцов]
* [https://pryazhnikov.com/ru/bandit-algorithms-for-website-optimization/ Обзор книги «Bandit Algorithms for Website Optimization»]
