Изменения

Окружение В обучении с подкреплением существует агент (''agent'') взаимодействует с окружающей средой (''environment''), предпринимая действия (''actions''). Окружающая среда дает награду (''reward'') за эти действия, а агент продолжает их предпринимать. Алгоритмы с частичным обучением пытаются найти стратегию, приписывающую состояниям (''states'') окружающей среды действия, одно из которых может выбрать агент в этих состояниях. Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.

При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары „входные "входные данные-ответ“ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний(''exploration vs exploitation'').Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандитао многоруком бандите].

Формально простейшая модель обучения с подкреплением состоит из:# * множества состояний окружения (''states'') <itex>S</itex>;# * множества действий (''actions'') <itex>A</itex>;# * множества вещественнозначных скалярных "выигрышей"(''rewards'').

В произвольный момент времени <itex>t</itex> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.

Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию <tex>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</tex> в случае МППР, имеющего терминальное состояние, или величину <br />: ::<tex>R=\sum_t \gamma^t r_t</tex> <br /> , для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{--- }} дисконтирующий множитель для „предстоящего выигрыша“"предстоящего выигрыша").

[[File:Simple_RLRL.png|thumb|RLlink=https://econophysica.ru/services/machine-схемаlearning/|Взаимодействие агента со средой]] <tex>S</tex> {{---}} множество состояний среды

# * инициализация стратегии <tex>\pi_1(a|s)</tex> и состояния среды <tex>s_1</tex>;# * для всех <tex>t = 1..\ldots 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>.

<tex>P(s_{t+1} = s′, r_{t+1} = r | s_t, a_t, r_t, s_{t−1}, a_{t−1}, r_{t−1}, .. ,s_1, a_1) == P(s_{t+1} = s′,r_{t+1} = r | s_t, a_t)</tex>,

# * опробовать все возможные стратегии;# * выбрать стратегию с наибольшим ожидаемым выигрышем.

Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или же бесконечно.

При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния <itex>s</itex>, при дальнейшем следовании стратегии <tex>\pi</tex>, <br /> ::<tex>V(s)=E[R|s,\pi]</tex>, <br />либо ожидаемый выигрыш, при принятии решения <i>a</i> в состоянии <i>s</i> и дальнейшем соблюдении <tex>\pi</tex>, <br />::<tex>Q(s,a)=E[R|s,\pi,a]</tex>. <br />Если для выбора оптимальной стратегии используется функция полезности <i>Q</i>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.Если же мы пользуемся функцией <i>V</i>, необходимо либо иметь модель окружения в виде вероятностей <tex>P(s'|s,a)</tex>, что позволяет построить функцию полезности вида <br />::<tex>Q(s,a)=\sum_{s'}V(s')P(s'|s,a)</tex>, <br />либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния <i>V</i>, и исполнитель, выбирающий подходящее действие в каждом состоянии.

либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>, ::<tex>Q(s, a) = E[R|s, \pi, a]</tex>, Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность. Если же мы пользуемся функцией <tex>V</tex>, необходимо либо иметь модель окружения в виде вероятностей <tex>P(s'|s, a)</tex>, что позволяет построить функцию полезности вида ::<tex>Q(s, a) = \sum_{s'}V(s')P(s'|s, a)</tex>, либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния <tex>V</tex>, и исполнитель, выбирающий подходящее действие в каждом состоянии. Имея фиксированную стратегию <tex>\pi</tex>, оценить <tex>E[R|\cdot]</tex> при <tex>\gamma=01</tex> можно просто усреднив непосредственные выигрыши.Наиболее очевидный способ оценки при <tex>\gamma>\in (0, 1)</tex> — {{---}} усреднить суммарный выигрыш после каждого состояния.

Поэтому построение искомой оценки при <tex>\gamma>\in (0, 1)</tex> неочевидно. Однако, можно заметить, что <itex>R</itex> образуют рекурсивное уравнение Беллмана: <br /> ::<tex>E[R|s_t]=r_t+\gamma E[R|s_{t+1}]</tex>. <br />, Подставляя имеющиеся оценки, <itex>V</itex>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями](''temporal difference (TD) learning'').

== Задача о многоруком бандите (''The multi-armed bandit problem'') ==

[[File:bandit.jpg|thumb|link=http://toppromotion.ru/blog/seo-category/novyij-algoritm-pod-nazvaniem-%C2%ABmnogorukij-bandit%C2%BB.html|Многорукий бандит]]

<tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max A</tex> — средняя награда в <i>t</i> играх <br /><tex>Q^∗(a) = \lim \limits_{y \rightarrow \infty{---}} Q_tмножество возможных ''действий'' (aручек автомата) \rightarrow max </tex> — ценность действия <tex>a</tex>,

Задача является модельной для понимания конфликта между ''exploitation'' <tex>\pi_t(применение, эксплуатацияa) и </tex> {{---}} ''explorationстратегия'' (изучение, исследование)агента в момент <tex>t</tex> <tex>\forall a \in A</tex>.

Задача выглядит следующим образом. <br />Игра агента со средой:У нас есть автомат - "* инициализация стратегии <tex>N\pi_1(a)</tex>-рукий бандит", на каждом шаге мы выбираем за какую из <tex>N</tex> рук автомата дернуть,;т.е. множество действий будет * для всех <tex>At ={1,2,…,N}\ldots T</tex>.<br />:Выбор действия ** агент выбирает действие (ручку) <tex>a_t∼ \pi_t(a)</tex>, на шаге <tex>t</tex>, влечет ;** среда генерирует награду <tex>R(r_t ∼ p_{a_t)</tex> при этом <tex>R}(ar), a \in A</tex> есть случайная величина, распределение которой мы не знаем. ;Состояние среды у нас от шага к шагу не меняется, а значит множество ** агент корректирует стратегию <tex>S = \pi_{s\t+1}(a)</tex> тривиально, ни на что не влияет, так что мы его игнорируем.<br />

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы <tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max </tex> {{---}} средняя награда в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.<br i>t</i>Проблема ровно одна: про распределения мы ничего не знаем.играх <br />,Однако, оценивать математическое ожидание некоторой случайной величины <tex>Q^∗(a) = \lim \limits_{t \rightarrow \infty} Q_t(a) \xirightarrow max </tex> c неизвестным распределением мы умеем. Делаем {{---}} ценность действия <tex>Pa</tex> экспериментов, получаем <tex>{\xi_p|p=1..P}</tex> величин, берем среднее арифметическое:

У нас есть автомат {{---}} <tex>N</tex>-рукий бандит, на каждом шаге мы выбираем за какую из <tex>N</tex> ручек автомата дернуть,т.е. множество действий <tex>\xi′ A = \frac{1}{P} \cdot \sum_{p=1}^{P}{,2 \xi_pldots ,N} </tex>.

это и будет оценка математического ожиданияВыбор действия <tex>a_t</tex> на шаге <tex>t</tex> влечет награду <tex>R(a_t)</tex> при этом <tex>R(a)</tex> <tex>\forall a \in A</tex> есть случайная величина, распределение которой неизвестно. Очевидно Состояние среды у нас от шага к шагу не меняется, что чем больше а значит множество состояний <tex>PS</tex> тем оценка точнеетривиально, ни на что не влияет, поэтому его можно проигнорировать.

== Жадные Для простоты будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали эти распределения, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и эпсилон-жадные стратегии == теперь совершать это действие на каждом шаге.

Объединяя всё вышеизложенноеПроблема в том, получаем простую "жадную" стратегиючто распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением.Для <tex>K</tex> экспериментов <tex>\xi_k</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов:

Жадная <tex>E(greedy\xi) стратегия= \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>,

Заведем массивы <br /><tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> Задача является модельной для понимания конфликта между ''exploitation''- сколько раз было выбрано действие <tex>a</tex> <br /><tex>\{Q_a=0|a=1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>''exploration''.

На каждом шаге <tex>t</tex>.<br />Выбираем действие с максимальной оценкой математического ожидания: <br /><tex>a_t = argmax\{Q_a|a=1..N\}</tex> <br />Выполняем действие at = Жадные и получаем награду <tex>R_t\epsilon</tex> <br />Обновляем оценку математического ожидания для действия -жадные стратегии (''greedy & <tex>a_t\epsilon</tex>: <br /><tex>P_{a_t} -greedy'') == P_{a_{t+1}}</tex> <br /><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t} (R_t − Q_{a_t})</tex>

Пример.* <tex>P_a = 0<br /tex>Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную <tex>\forall a \in \{1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до \ldots N\} </tex> {{---}} сколько раз было выбрано действие <tex>Q_1 = 1a</tex>. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.

Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно, что * <tex>Q_a = 0</tex> <tex>\forall a \in \{1 \ldots N\}</tex> {{---}} текущая оценка математического ожидания награды для нашего примера достаточно попробовать в начале каждую из ручек.Но если награда все-таки случайная величина, то единичной попытки будет явно не достаточнодействия <tex>a</tex>. В связи с этим предлагается следующая модификация жадной стратегии:

На каждом шаге <tex>\epsilont</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия* Выбираем действие с максимальной оценкой математического ожидания:

Зададимся некоторым параметром :<tex>\epsilon a_t = argmax_{a \in (0,1)A} Q_a </tex>,

Заведем массивы<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_aa_t</tex> - текущая оценка математического ожидания награды для действия и получаем награду <tex>aR(a_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>,

:<tex>Q_{a_t } = argmaxQ_{a_t} + \frac{Q_a|a=1,...,N}</tex> <br />Выполняем действие <tex>{P_{a_t}} (R(a_t</tex> и получаем награду <tex>R_t</tex> <br />Обновляем оценку математического ожидания для действия <tex>) − Q_{a_t})</tex>:.

ЯсноПусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, что если выбрать <tex>\epsilon = 0</tex> мы вернемся к просто вторая всегда выдаёт 2. Действуя согласно жадной стратегии. Однакомы дёрнем в начале первую ручку, так как в начале оценки математических ожиданий равны нулю, если увеличим её оценку до <tex>\epsilon > 0Q_1 = 1</tex>. В дальнейшем всегда будем выбирать первую ручку, в отличии от просто "жадной", у нас а значит на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование"будем получать на 1 меньше, чем могли бы.

ПримерВ данном случае достаточно попробовать в начале каждую из ручек вместо того, чтобы фокусироваться только на одной. Награда для стратегии с различными <tex>\epsilon</tex>:[[FileНо если награда случайная величина, то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:Eps-greedy.png]]

== Метод UCB == <tex>\epsilon</tex>-жадная (upper confidence bound<tex>\epsilon</tex>-''greedy'') стратегия ====

Предыдущие алогритмы при принятии решений используют данные о среднем выигрыше[[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github. Проблема заключается в том, что если рука даёт выигрыш io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем считать самой выгодной рукой ту, которая на самом деле таковой не является.различными <tex>\epsilon</tex>]]

Алгоритм верхнего доверительного интервала Введем параметр <tex>\epsilon \in (''Upper confidence bound'' или просто UCB0,1) - это семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять этим значениям выигрыша. В книге описывается один такой алгоритм - UCB</tex>.

* Получим значение <tex>Q_a = average_arm_reward + arm_bonus\alpha</tex>{{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)<br /tex>;* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>average_arm_rewarda_t \in A</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от тогослучайно и равновероятно, что используется иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания;* Обновляем оценки так же как в других алгоритмахжадной стратегии.

Если <tex>arm_bonus\epsilon = 0</tex> - , то это бонусное значениеобычная жадная стратегия. Однако если <tex>\epsilon > 0</tex>, которые показывает, насколько недоисследована эта рука по сравнению то в отличии от жадной стратегии на каждом шаге с остальнымивероятностью <tex>\epsilon</tex> присходит "исследование" случайных действий. Он вычисляется следующим образом:

<tex>arm_bonus = \sqrt{\frac{2 \cdot \ln{total_count}}{arm_count}} </tex><tex>total_count</tex> - это суммарное количество использований всех рук, а <tex>arm_count</tex> - это количество использований данной руки.== Стратегия Softmax ===

Доказательство [http://banditalgsОсновная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия.comЧем больше <tex>Q_t(a)</2016tex>, тем больше вероятность выбора <tex>a</09/18/the-upper-confidence-bound-algorithm здесь]tex>:

В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора руки, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждая из рук выбирается по одному разу <tex>\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(Q_t(это нужно для тогоb) / \tau)}}</tex>, чтобы можно было вычислить размер бонуса для всех рук). После этого в каждый момент времени выбирается рука с максимальным значением весового коэффициента.

Несмотря на это отсутствие случайности<tex>\tau \in (0, результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из\infty)</tex> {{---за того}} параметр, что данный алгоритм сравнительно часто выбирает недоисследованные рукис помощью которого можно настраивать поведение алгоритма.

Алгоритм мягкого максимума При <tex>\tau \rightarrow 0</tex> стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (softmaxexploitation) - это чуть более сложный алгоритм. Его основная идея - уменьшение потерь при исследовании за счёт более редкого выбора рук, которые дали маленький выигрыш в прошлом. Чтобы этого добиться для каждой руки вычисляется весовой коэффициент, на базе которого происходит выбор руки:

Эвристика: параметр <tex>average_arm_reward\tau</tex> - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам. temperature - это параметр, с помощью которого можно настраивать поведение алгоритма (он называется температура). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулю, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации). Экспонента используется для того, чтобы данный вес был ненулевым даже у рук, выигрыш от которых пока нулевойимеет смысл уменьшать со временем.

Мягкий вариант компромисса "exploitation-exploration":<br />чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>: <br /><tex>\pi_{t+1}(a) = \frac{exp(Q_t(a)/τ)}{\sum\limits_{b \in A} {exp(Q_t(b)/τ)}}</tex> <br />где <tex>\tau</tex> — параметр температуры,<br />Предыдущие алгоритмы при <tex>\tau \rightarrow 0</tex> стратегия стремится к жаднойпринятии решения используют данные о среднем выигрыше. Проблема в том,<br />при <tex>\tau \rightarrow \infty</tex> — к равномернойчто если действие даёт награду с какой-то вероятностью, т.е. чисто исследовательской<br />Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временемто данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.

== QАлгоритм верхнего доверительного интервала (''upper confidence bound'' или UCB) {{-learning == --}} семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.

Также как ''softmax'Q-обучение''' (Q-learning) — метод, применяемый в [[Искусственный интеллект|искусственном интеллекте]] UCB при [[Агентный подход|агентном подходе]]. Относится к экспериментам вида [[Обучение с подкреплением|oбучение с подкреплением]]. На основе получаемого от среды вознаграждения [[Интеллектуальный агент|агент]] формирует [[Функция полезности|функцию полезности]] Qвыборе действия используется весовой коэффициент, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ Q-обучения — то, что оно в состоянии сравнить ожидаемую [[Полезность который представляет собой верхнюю границу доверительного интервала (экономикаupper confidence bound)|полезность]] доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде [[Марковский процесс принятия решений|марковского процесса принятия решений]].значения выигрыша:

<tex>\pi_{t+1}(a) === Aлгоритм Q-learning ===[[File:Q-Learning.png|thumb|313px|Процесс Q-обучения]]Q_t(a) + b_a</tex>,

The weight for a step from a state <mathtex>b_a = \Delta t</math> steps into the future is calculated as <math>sqrt{\frac{2 \gamma^ln{\Delta tsum_a P_a}}{P_a}}</math>. <math>\gamma</math> (the ''discount factor'') is a number between 0 and 1 (<math>0 \le \gamma \le 1</math>) and has the effect of valuing rewards received earlier higher than those received later (reflecting the value of a "good start"). <math> \gamma </math> may also be interpreted as the probability to succeed (or survive) at every step <math>\Delta t</mathtex>{{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.

The algorithm, therefore, has a function that calculates Доказательство [http://banditalgs.com/2016/09/18/the quality of a state-action combination:upper-confidence-bound-algorithm здесь]

:<math>Q: S \times A \to \mathbb{R}</math> В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора действия, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждое из действий выбирается по одному разу (для того чтобы можно было вычислить размер бонуса для всех действий). После этого в каждый момент времени выбирается действие с максимальным значением весового коэффициента.

Before learning begins, {{tmath|Q}} is initialized to a possibly arbitrary fixed value (chosen by the programmer)Несмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. ThenЭто происходит из-за того, at each time <math>t</math> the agent selects an action <math>a_t</math>, observes a reward <math>r_t</math>, enters a new state <math>s_{t+1}</math> (that may depend on both the previous state <math>s_t</math> and the selected action), and <math>Q</math> is updatedчто данный алгоритм сравнительно часто выбирает недоисследованные действия. The core of the algorithm is a simple [[Markov decision process#Value iteration|value iteration update]], using the weighted average of the old value and the new information:

:<math>== Q^{new}(s_{t},a_{t}) \leftarrow (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\text{old value}} + \underbrace{\alpha}_{\text{learning rate}} \cdot \overbrace{\bigg( \underbrace{r_{t}}_{\text{reward}} + \underbrace{\gamma}_{\text{discount factor}} \cdot \underbrace{\max_{a}Q(s_{t+1}, a)}_{\text{estimate of optimal future value}} \bigg) }^{\text{learned value}} </math>==

where ''На основе получаемого от среды вознаграждения агент формирует функцию полезности <mathtex>r_{t}Q</mathtex>'' is the reward received when moving from the state , что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <mathtex>s_{t}Q</mathtex> to the state <math>s_-обучения {{t+1---}}</math>то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, and <math>\alpha</math> is the learning rate (<math>0 < \alpha \le 1</math>)которые можно представить в виде МППР.

An episode of the algorithm ends when state <math>s_{t+1}</math> is a final or ''terminal state''. HoweverТаким образом, ''Q''-learning can also learn in non-episodic tasks.{{citation needed|date=December 2017}} If the discount factor is lower than 1, the action values are finite even if the problem can contain infinite loops.алгоритм это функция качества от состояния и действия:

For all final states :<math>s_f</math>, <mathtex>Q(s_f, a)</math> is never updated, but is set : S \times A \to the reward value <math>r\mathbb{R}</math> observed for state <mathtex>s_f</math>. In most cases, <math>Q(s_f,a)</math> can be taken to equal zero.

Обозначения* LF — это фактор обученияПеред обучением <tex>Q</tex> инициализируется случайными значениями. Чем он вышеПосле этого в каждый момент времени <tex>t</tex> агент выбирает действие <tex>a_t</tex>, получает награду <tex>r_t</tex>, тем сильнее агент доверяет новой информации.* DF — это фактор дисконтирования. Чем он меньшепереходит в новое состояние <tex>s_{t+1}</tex>, тем меньше агент задумывается о выгоде которое может зависеть от будущих своих действийпредыдущего состояния <tex>s_t</tex> и выбранного действия, и обновляет функцию <tex>Q</tex>.Обновление функции использует взвешенное среднее между старым и новым значениями:

:<tex>Q^{new}(s_{t},a_{t}) \leftarrow (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\text{old value}} + \underbrace{\alpha}_{\text{learning rate}} \cdot '''fun''' init\overbrace{\bigg(): '''for''' \forall s and underbrace{r_{t}}_{\text{reward}} + \underbrace{\gamma}_{\text{discount factor}} \cdot \underbrace{\max_{a: }Q[s(s_{t+1}, a] = rand()}_{\text{estimate of optimal future value}} \bigg) }^{\text{learned value}} </tex>,

где ''<tex>r_{t}</tex>'fun''' observe(): s' = s /это награда, полученная при переходе из состояния <tex>s_{t}</ Запомнить предыдущие состояния a' = a tex> в состояние <tex>s_{t+1}</tex>, и <tex>\alpha</ Запомнить предыдущие действия s = get_from_sensortex> это скорость обучения () /<tex>0 < \alpha \le 1</ Получить текущие состояния с сенсора r = get_from_sensor(tex>) // Получить вознаграждение за предыдущее действие.

'''fun''' q-update(): Q[s'Алгоритм заканчивается, a'] = Q[s', a'] + LF * (r когда агент переходит в терминальное состояние <tex>s_{t+ DF * MAX(Q,s) — Q[s',a'])1}</tex>.

'''fun''' decision(): a = ARGMAX(== Aлгоритм Q, s) TO_ACTIVATOR -learning === a# '''Repeat''': GO TO 2 ???

'''fun'' max([[File:Q, s)-Learning.png|thumb|313px|link=https: max = minValue for each a of ACTIONS(s) do if //en.wikipedia.org/wiki/Q-learning|Процесс Q[s, a-обучения] > max: max = Q[s, a] return max

'''fun'' argmax(Q* <tex>S</tex> — множество состояний,* <tex>A</tex> — множество действий,* <tex>R = S \times A \rightarrow \mathbb{R}</tex> {{---}} функция награды, s): amax * <tex>T = First of ACTION(s)S \times A \rightarrow S</tex> {{---}} функция перехода, for each a of ACTION* <tex>\alpha \in [0, 1]</tex> {{---}} learning rate (sобычно 0.1) do, чем он выше, тем сильнее агент доверяет новой информации, if Q* <tex>\gamma \in [s0, a1] </tex> Q[s{{---}} discounting factor, чем он меньше, amax]: amax = a return amaxтем меньше агент задумывается о выгоде от будущих своих действий.