77
правок
Изменения
м
Нет описания правки
Заведем массивы <br />
<tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br /><tex>\{Q_a=0|a=1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex> <br />На каждом шаге <tex>t</tex>.
На каждом шаге <tex>t</tex>.<br />
Выбираем действие с максимальной оценкой математического ожидания: <br />
<tex>a_t = argmax\{Q_a|a=1..N\}</tex> <br />
Выполняем действие at и получаем награду <tex>R_t</tex> <br />
Обновляем оценку математического ожидания для действия <tex>a_t</tex>: <br />
Пример.<br />
Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до <tex>Q_1 =1</tex>. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.
Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно, что для нашего примера достаточно попробовать в начале каждую из ручек.
Заведем массивы<br />
<tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br /><tex>\{Q_a=0|a=1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex> <br />На каждом шаге <tex>t</tex>.
На каждом шаге <tex>t</tex>.<br />
Получаем значение <tex>\alpha</tex> случайной величины равномерно расределенной на отрезке <tex>(0,1)</tex> <br />
Если <tex>\alpha \in (0,\epsilon)</tex>, то выберем действие <tex>a_t</tex> из набора <tex>A</tex> случайно и равновероятно. <br />
<tex>P_{a_t} = P_{a_{t+1}}</tex> <br />
<tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})</tex>
Ясно, что если выбрать <tex>\epsilon = 0</tex> мы вернемся к просто жадной стратегии. Однако, если <tex>\epsilon > 0</tex>, в отличии от просто <<"жадной>>", у нас на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование".
== Метод UCB (upper confidence bound) ==
