Изменения

Окружение В обучении с подкреплением существует агент (''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:RL.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>A</tex> — {{---}} множество возможных ''действий'' <br />(ручек автомата), <tex>p_a(r)</tex> — {{---}} неизвестное распределение ''награды'' <tex>r \in R</tex> за <tex>\forall a \in A</tex> <br />, <tex>\pi_t(a)</tex> — {{---}} ''стратегия'' агента в момент <tex>t</tex>, распределение на <tex>\forall a \in A</tex> <br />. 

# * инициализация стратегии <tex>\pi_1(a)</tex>;# * для всех <tex>t = 1..\ldots 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_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max </tex> — {{---}} средняя награда в <i>t</i> играх <br />,<tex>Q^∗(a) = \lim \limits_{y t \rightarrow \infty} Q_t(a) \rightarrow max </tex> — {{---}} ценность действия <tex>a</tex>.

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

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

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

<tex>E(\xi′ xi) = \frac{1}{PK} \cdot \sum_{pk=1}^{PK}{\xi_pxi_k} </tex>,

это и будет оценка математического ожидания. Очевидно, что чем больше <tex>P</tex> тем оценка точнееЗадача является модельной для понимания конфликта между ''exploitation''-''exploration''.

=== Жадные и эпсилон<tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===

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

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

:<tex>\epsilonP_{a_t} = P_{a_t} + 1</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия,

Зададимся некоторым параметром :<tex>Q_{a_t} = Q_{a_t} + \epsilon \in frac{1}{P_{a_t}} (R(0,1a_t) − Q_{a_t})</tex>.

На каждом шаге Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку, так как в начале оценки математических ожиданий равны нулю, увеличим её оценку до <tex>tQ_1 = 1</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>a_t = argmax{Q_a|a=1,...,N}== </tex> <br />Выполняем действие <tex>a_t\epsilon</tex> и получаем награду -жадная (<tex>R_t\epsilon</tex> <br />Обновляем оценку математического ожидания для действия <tex>a_t</tex>:-''greedy'') стратегия ====

<tex>P_{a_t} [[File:Eps-greedy.png|thumb|313px|link= P_{a_{t+1}}<https://vbystricky.github.io/2017/tex> <br 01/>rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})\epsilon</tex>]]

Ясно, что если выбрать Введем параметр <tex>\epsilon = 0</tex> мы вернемся к просто жадной стратегии. Однако, если <tex>\epsilon > in (0</tex>, в отличии от просто "жадной", у нас на каждом шаге с вероятностью <tex>\epsilon1)</tex> присходит "исследование".

Пример. Награда для стратегии с различными На каждом шаге <tex>\epsilont</tex>:[[File:Eps-greedy.png]]

== Метод UCB * Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(upper confidence bound0, 1) == </tex>;* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex> случайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания;* Обновляем оценки так же как в жадной стратегии.

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

Как и в Основная идея алгоритма ''softmax '' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в UCB при выборе рук используется прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала на базе которого происходит выбор действия. Чем больше <tex>Q_t(upper confidence bounda)</tex>, что и дало название алгоритму) значения выигрышатем больше вероятность выбора <tex>a</tex>:

<tex>Q_a \pi_{t+1}(a) = average_arm_reward + arm_bonus<\frac{exp(Q_t(a) /tex><br \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) /><tex>average_arm_reward\tau)}}</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.

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

При <tex>arm_bonus = \sqrt{tau \frac{2 rightarrow \cdot \ln{total_count}}{arm_count}} </tex><tex>total_countinfty</tex> - это суммарное количество использований всех рук стратегия стремится к равномерной, а <tex>arm_count</tex> - это количество использований данной рукито есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration).

Доказательство [http:При <tex>\tau \rightarrow 0<//banditalgstex> стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (exploitation).com/2016/09/18/the-upper-confidence-bound-algorithm здесь]

В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора руки, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждая из рук выбирается по одному разу (это нужно Экспонента используется для того, чтобы можно было вычислить размер бонуса для всех рук). После этого в каждый момент времени выбирается рука с максимальным значением весового коэффициентаданный вес был ненулевым даже у действий, награда от которых пока нулевая.

Несмотря на это отсутствие случайности, результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные рукиЭвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временем.

== Стратегия Softmax = Метод UCB (''upper confidence bound'') ===

Алгоритм мягкого максимума (softmax) - это чуть более сложный алгоритмПредыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Его основная идея Проблема в том, что если действие даёт награду с какой- уменьшение потерь при исследовании за счёт более редкого выбора рукто вероятностью, которые дали маленький выигрыш в прошломто данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие. Чтобы этого добиться для каждой руки вычисляется весовой коэффициент, на базе которого происходит выбор руки:

<tex>Q_a = \expАлгоритм верхнего доверительного интервала (average_arm_reward / temperature''upper confidence bound'' или UCB)</tex>{{---}} семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.

<tex>average_arm_reward</tex> - это среднее значение Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.:

temperature - это параметр, с помощью которого можно настраивать поведение алгоритма <tex>\pi_{t+1}(он называется температураa). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно = Q_t(т.е. перейдёт в режим исследованияa). Если он близок к нулю+ b_a</tex>, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации).

Экспонента используется для того<tex>b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} </tex> {{---}} бонусное значение, чтобы данный вес был ненулевым даже у руккоторые показывает, выигрыш от которых пока нулевойнасколько недоисследовано действие по сравнению с остальными.

Вероятность выбора руки равна отношению её весового коэффициента и сумме весовых коэффициентов всех рук. При выборе генерируется случайное число от 0 до 1, на основании которого произойдёт выбор конкретной рукиДоказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]

Мягкий вариант компромисса "exploitation-exploration":<br />чем больше <tex>Q_t(a)</tex>В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора действия, ни параметры, тем больше вероятность выбора <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-обучение''' (Q-learning) — метод, применяемый в [[Искусственный интеллект|искусственном интеллекте]] при [[Агентный подход|агентном подходе]]. Относится к экспериментам вида [[Обучение с подкреплением|oбучение с подкреплением]]. На основе получаемого от среды вознаграждения [[Интеллектуальный агент|агент]] формирует [[Функция полезности|функцию полезности]] <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---обучения — }} то, что оно в состоянии сравнить ожидаемую [[Полезность (экономика)|полезность]] доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде [[Марковский процесс принятия решений|марковского процесса принятия решений]]МППР.

=== Aлгоритм Q-learning ===[[FileТаким образом, алгоритм это функция качества от состояния и действия:Q-Learning.png|thumb|313px|Процесс Q-обучения]]

The weight for a step from a state :<mathtex>Q: S \Delta t</math> steps into the future is calculated as <math>times A \to \gamma^mathbb{\Delta tR}</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Перед обучением <tex>Q</tex> инициализируется случайными значениями. После этого в каждый момент времени <tex>t</tex> агент выбирает действие <tex>a_t</tex>, thereforeполучает награду <tex>r_t</tex>, has a function that calculates the quality of a state-action combinationпереходит в новое состояние <tex>s_{t+1}</tex>, которое может зависеть от предыдущего состояния <tex>s_t</tex> и выбранного действия, и обновляет функцию <tex>Q</tex>. Обновление функции использует взвешенное среднее между старым и новым значениями:

:<mathtex>Q: S ^{new}(s_{t},a_{t}) \leftarrow (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\text{old value}} + \underbrace{\alpha}_{\times A text{learning rate}} \to cdot \mathbboverbrace{R\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}}</mathtex> .,

Before learning begins, {{tmath|Q}} is initialized to a possibly arbitrary fixed value (chosen by the programmer). Then, at each time где ''<mathtex>r_{t}</math> the agent selects an action <math>a_t</mathtex>'' это награда, observes a reward полученная при переходе из состояния <mathtex>r_ts_{t}</mathtex>, enters a new state в состояние <mathtex>s_{t+1}</mathtex> (that may depend on both the previous state , и <mathtex>s_t\alpha</mathtex> and the selected action), and это скорость обучения (<mathtex>Q0 < \alpha \le 1</mathtex> 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:

:Алгоритм заканчивается, когда агент переходит в терминальное состояние <mathtex>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}} </mathtex>.

where ''<math>r_{t}</math>'' is the reward received when moving from the state <math>s_{t}</math> to the state <math>s_{t+1}</math>, and <math>\alpha</math> is the === Aлгоритм Q-learning rate (<math>0 < \alpha \le 1</math>).===

An episode of the algorithm ends when state <math>s_{t+1}<[[File:Q-Learning.png|thumb|313px|link=https://math> is a final or ''terminal state''en. However, ''wikipedia.org/wiki/Q''-learning can also learn in non|Процесс Q-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>, <math>Q(s_f, a)</math> is never updated, but is set to the reward value <math>r</math> observed for state <math>s_f</math>. In most cases, <math>Q(s_f,a)</math> can be taken to equal zero. Обозначения* <tex>S</tex> -- — множество состояний,* <tex>A</tex> -- — множество действий,* <tex>R = S * \times A \rightarrow \mathbb{R}</tex> {{--- }} функция награды,* <tex>T = S * \times A -> \rightarrow S</tex> {{-- -}} функция перехода,* <tex>\alpha \in [0, 1]</tex> {{--- }} learning rate (обычно 0.1) // , чем он выше, тем сильнее агент доверяет новой информации,* <tex>\gamma \in [0, 1]</tex> {{--- }} discounting factor // , чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.

Q[(s][, a] ) = rand() '''while''' Q не сошелсяis not converged:

'''while''' s не конечное состояниеis not terminal:

<tex>Q[(s'][, a] ) = (1 - \alpha) Q[(s'][, a] ) + \alpha * (r + \gamma * \max_max\limits_{a'}{Q[(s'][, a'])})</tex>