Изменения

:: # для всех <tex>t = 1..T</tex>## агент выбирает действие <tex>a_t ∼ \pi_t(a|s_t)</tex>## среда генерирует премию <tex>r_{t + 1} ∼ p(r|a_t, s_t)</tex> и новое состояние <tex>s_{t + 1} ∼ p(s|a_t, s_t)</tex>## агент корректирует стратегию <tex>\pi_{t + 1}(a|s)</tex>

<itex>A</itex> — множество возможных ''действий'' <br />

<tex>\pi_t(a)</tex> — ''стратегия'' агента в момент <itex>t</itex>, распределение на <itex>A</itex> <br />

# инициализация стратегии <tex>/\pi_1(a)</tex>:: # для всех <tex>t = 1..T</tex>## агент выбирает действие <tex>a_t ∼ \pi_t(a)</tex>## среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>## агент корректирует стратегию <tex>\pi_{t+1}(a)</tex>

<tex>Q^∗(a) = \lim \limits_{y \rightarrow \infty} Q_t(a) \rightarrow max </tex> — ценность действия <itex>a</itex>

Задача выглядит следующим образом. <br />У нас есть автомат - “N"<tex>N</tex>-рукий бандит”бандит", на каждом шаге мы выбираем за какую из <tex>N </tex> рук автомата дернуть, т.е. множество действий будет <tex>A={1,2,…,N}</tex>. <br />Выбор действия at<tex>a_t</tex>, на шаге <tex>t</tex>, влечет награду <tex>R(ata_t) </tex> при этом <tex>R(a),a∈A a \in A</tex> есть случайная величина, распределение которой мы не знаем. Состояние среды у нас от шага к шагу не меняется, а значит множество <tex>S={s} </tex> тривиально, ни на что не влияет, так что мы его игнорируем.<br />

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем . Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге. <br />Проблема ровно одна: про распределения мы ничего не знаем.<br />Однако, оценивать математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением мы умеем. Делаем <tex>P</tex> экспериментов, получаем <tex>{\xi_p|p=1..P}<tex> величин, берем среднее арифметическое:

Однако, оценивать математическое ожидание некоторой случайной величины ξ c неизвестным распределением мы умеем. Делаем <tex>\xi′ = \frac{1}{P экспериментов, получаем } \cdot \sum_{ξp|p=1,…,}^{P} величин, берем среднее арифметическое:{\xi_p} </tex>

ξ′=1P∑p=1Pξp,это и будет оценка математического ожидания. Очевидно, что чем больше <tex>P </tex> тем оценка точнее.

== Жадные и эпсилон-жадные стратегии == Объединяя всё вышеизложенное, получаем простую “жадную” <<жадную>> стратегию.

Заведем массивы <br /><tex>{PaP_a=0|a=1,…,N}</tex>, Pa <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex><tex>{QaQ_a=0|a=1,…,N}</tex>, Qa <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>На каждом шаге <tex>t</tex>.

Выбираем действие с максимальной оценкой математического ожидания:<br /> at<tex>a_t =argmax{QaQ_a|a=1,...,N}</tex>Выполняем действие at и получаем награду Rt<tex>R_t</tex>Обновляем оценку математического ожидания для действия at <tex>a_t</tex>: Pat<tex>P_{a_t} =PatP_{a_{t+1}}</tex>Qat<tex>Q_{a_t} =QatQ_{a_{t+1Pat1}} P_{a_t} (Rt−QatR_t − Q_{a_t})</tex>

Пример.<br />Пусть у нас есть “двурукий” <<двурукий>> бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до Q1<tex>Q_1 =1. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.

Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно. , что для нашего примера достаточно попробовать в начале каждую из ручек. Но если награда все-таки случайная величина, то единичной попытки будет явно не достаточно. В связи с этим предлагается следующая модификация жадной стратегии:

ϵ<tex>\epsilon</tex>-жадная (ϵ<tex>\epsilon</tex>-greedy) стратегияЗададимся некоторым параметром ϵ∈<tex>\epsilon \in (0,1)Заведем массивы</tex>

Заведем массивы<br /><tex>{PaP_a=0|a=1,…,N}</tex>, Pa <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex><tex>{QaQ_a=0|a=1,…,N}</tex>, Qa <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>На каждом шаге <tex>t</tex>.

Получаем значение α <tex>\alpha</tex> случайной величины равномерно расределенной на отрезке <tex>(0,1)</tex>Если α∈<tex>\alpha \in (0,ϵ\epsilon)</tex>, то выберем действие at <tex>a_t</tex> из набора <tex>A </tex> случайно и равновероятно .

at<tex>a_t =argmax{QaQ_a|a=1,...,N}</tex>Выполняем действие at <tex>a_t</tex> и получаем награду Rt<tex>R_t</tex>Обновляем оценку математического ожидания для действия at <tex>a_t</tex>: <tex>P_{a_t} = P_{a_{t+1}}</tex><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})

Pat=Pat+1Qat=Qat+1Pat(Rt−Qat)Ясно, что если выбрать ϵ<tex>\epsilon =0 </tex> мы вернемся к просто жадной стратегии. Однако, если ϵ<tex>\epsilon >0</tex>, в отличии от просто “жадной”<<жадной>>, у нас на каждом шаге с вероятностью ϵ <tex>\epsilon</tex> присходит “исследование”<<исследование>>.

Мягкий вариант компромисса «изучение—применение»<<exploitation-exploration>>:<br />чем больше Qt<tex<Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>:πt<tex>\pi_{t+1}(a) = \frac{expQt(Q_t(a)/τ�Pb∈Aτ)}{\sum\limits_{b \in A} {expQt(Q_t(b)/τ�τ)}}</tex>где τ <tex>\tau</tex> — параметр температуры,<br />при τ → <tex>\tau \rightarrow 0 </tex> стратегия стремится к жадной,<br />при τ → ∞ <tex>\tau \rightarrow \infty</tex> — к равномерной, т.е. чисто исследовательской<br />Эвристика: параметр τ <tex>\tau</tex> имеет смысл уменьшать со временем.Какая из стратегий лучше?— зависит от конкретной задачи,— решается в эксперименте