Марковские процессы принятия решений

Мир-решётка

Здравствуйте и вновь добро пожаловать на занятия по теме «Искусственный интеллект: обучение с подкреплением на языке Python».

В этой статье мы формализуем некоторые уже изученные понятия обучения с подкреплением. Мы уже знаем термины «агент», «среда», «действие», «состояние», «вознаграждение» и «эпизод». Эта часть полностью посвящена помещению всех этих понятий в формальную структуру, которая называется марковским процессом принятия решений.

Мы опишем игру, которая будет использоваться в оставшейся части курса. Во многих отношениях она проще, чем крестики-нолики, но имеет ряд свойств, позволяющих нам исследовать некоторые более интересные особенности обучения с подкреплением.

Вмире-решётке нашим агентом является робот, а средой, как вы, вероятно, ужедогадались, – решётка. Агент может двигаться в четырёх направлениях – вверх,вниз, влево и вправо. Это и есть весь его набор действий. Решётка же обычносоздаётся следующим образом (см. слайд). Клетка, или позиция, с координатами(1, 1) является стеной, и робот не может туда попасть; если он попытаетсясделать это, то просто врежется в стену. В позициях с координатами (0, 3) и (1,3) у нас есть два конечных состояния. Позиция с координатами (0, 3) являетсяцелевым состоянием – роботу нужно попасть именно туда, поскольку в этомсостоянии он получает максимальное вознаграждение. Позиция с координатами (1,3) является проигрышным состоянием – попав туда, мы проигрываем. Я вольно используюслово «проигрыш», поскольку сейчас нас больше интересуют чётко определённыепонятия вроде общего вознаграждения. В любом случае, в этой позиции мы получаембольшое отрицательное вознаграждение, так что заканчивать игру там не следует.

Как можно заметить, в мире-решётке намного меньшее количество состояний, чем в крестиках-ноликах. Состояние может быть определено как местоположение робота, так что всего есть 11 состояний, поскольку всего 12 клеток, но в одну из них робот попасть не может. При этом, как вы уже знаете, действий всего четыре. Таким образом, это очень маленькая игра – 11 состояний и 4 действия, однако из них мы выведем все остальные понятия этого курса.

Марковское свойство

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

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

Мыможем определить условную вероятность xt с учётом всех предыдущих x:

Мыможем определить условную вероятность xt с учётом всех предыдущих x:

Вобщем случае так упрощать нельзя, но если допустить, что марковское свойствоистинно, то можно. Марковское свойство определяет, от скольких предыдущих x зависит x текущее. Так,марковское свойство первого порядка означает, что xt зависит только от xt-1:

Марковскоесвойство второго порядка значит, что xt зависит только от xt-1 и xt-2:

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

Давайтерассмотрим простой пример с марковским свойством. Разберём предложение «Давайтерассмотрим простой пример». Предположим, я сообщаю вам предыдущие словапредложения, а вам нужно предсказать следующее слово. Если предыдущими словамиявляются «Давайте рассмотрим простой», то, вероятно, вы догадаетесь, чтоследующим словом будет «пример». Но пусть теперь я сообщаю лишь то, чтопредыдущим словом является «простой». Сможете ли вы предсказать следующее? Возможно,но это будет куда труднее. А сможете предсказать слово, если предыдущее –«рассмотрим»? Вероятно, нет. Однако именно в этом и заключается марковскоедопущение. Как видите, оно имеет довольно ограниченную область применения,однако задачу можно сформулировать так, чтобы это не мешало.

Итак,как же выглядит марковское свойство в обучении с подкреплением? Напомню, чтовыполнение действия A(t) в состоянии S(t) приводит к двум последствиям: кследующему состоянию S(t+1) и вознаграждению R(t+1). В этом случаемарковское свойство утверждает, что S(t+1) и R(t+1) зависит только от A(t) и S(t), но ни от какихдругих предыдущих A и S:

Дляудобства также можно использовать сокращённую запись с символами s, r, a и s:

Чемже это отличается от обычного понимания марковского свойства? Обратите вниманиена совместное распределение s и r – оно указываетна совместное распределение двух переменных, обусловленное двумя другимипеременными. Именно в этом отличие от обычной формулировки марковскогосвойства, когда у нас слева и справа лишь по одной переменной.

Имеяэто совместное условное распределение, нахождение частных условныхраспределений становится просто вопросом использования правил теориивероятностей. К примеру, если мы хотим узнать только s или только r при заданных s и a, то можем использовать следующие уравнения:

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

В качества примера того, что марковское допущение не обязательно ограничивает сферу своего применения, можно рассмотреть недавний образец применения обучения с подкреплением. Так, DeepMind использует объединение четырёх новейших фреймов, чтобы представить текущее состояние. Строго говоря, состояние может состоять из чего угодно и какого угодно времени, от прошлого до настоящего. Просто мы обычно полагаем, что сиюминутное состояние является тем, что мы сиюминутно измеряем, однако это не всегда так. Обратите внимание, что нам также не нужны необработанные данные, чтобы представить состояние, – оно может состоять из любых данных, полученных из необработанных. Это можно рассматривать как преобразование признаков необработанных данных. По сути, любые сигналы датчиков агента можно использовать для формирования состояния.

Определение и формализация марковских процессов принятия решений

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

Однако,чтобы собрать головоломку, нам нужна ещё одна часть. Ключевым понятием вмарковском процессе принятия решений является решение. Способ, которым мыпринимаем решение, какие действия предпринять в тех или иных состояниях,называется стратегией. Она обычно обозначается символом π. Формально стратегия не является составной частью собственномарковского процесса принятия решений, но она, наряду с функцией ценности,которую мы вскоре определим более формализовано, является частью решения.Причина, по которой я до сих пор не упоминал стратегию, заключается в том, чтоэто несколько необычное понятие. Мы записываем π в виде математического символа, но для него нет уравнения. Кпримеру, если π – эпсилон-жадныйалгоритм, то как его записать в виде уравнения? Это же алгоритм. Единственноеисключение тут – это когда мы хотим записать оптимальную стратегию, котораяможет быть математически определена в понятиях функции ценности. Мы поговоримоб оптимальных стратегиях и что они означают в следующих лекциях. Но пока что π является скорее сокращённым обозначениемалгоритма, который используется агентом для определения своего поведения всреде.

Всвязи с тем, что марковский процесс принятия решений удовлетворяет марковскомусвойству, мы, как легко догадаться, можем также нарисовать диаграммы переходовсостояний, как мы это делали для марковских и скрытых марковских моделей. Сам яделаю это нечасто, но для вас это может оказаться полезным.

Вновьрассмотрим вероятности перехода состояний p(s’|s,a). Напомню, я утверждал, что, какправило, они определены, хотя это и не всегда так. Почему так? Не забывайте,что состояние – это только то, что возникает из восприятия агентом среды, этоне сама среда. Состояние может быть несовершенным представлением среды, и вэтом случае можно ожидать, что переход состояний будет вероятностным. Например,измеряемое состояние может представлять несколько конфигураций среды. Примеромнесовершенного представления о среде может служить блэк-джек. Можнорассматривать следующую карту крупье как часть состояния, однако если вы –агент, вы не можете видеть эту следующую карту, а значит, она не являетсячастью вашего состояния, она является частью среды.

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

Иногда возникает путаница в вопросе о том, что представляет собой агент, а что – среда. Самостоятельно действуя в среде, вы можете считать себя агентом, но что именно представляете из себя вы? Вы – это ваше тело? Но ваше тело правильнее считать частью среды: тело не принимает решений и не учится. Оно имеет «датчики», передающие сигналы в ваш мозг, и именно он учится и принимает решения. Поэтому следует иметь в виду, где проходит граница между агентом и средой.

Будущие вознаграждения

Формализуем идею общего вознаграждения, в частности нас интересует измерение общего будущего вознаграждения – всего, что начинается с t+1 и далее. Это называется отдачей и обозначается G(t):

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

В качества примера того, что марковское допущение не обязательно ограничивает сферу своего применения, можно рассмотреть недавний образец применения обучения с подкреплением. Так, DeepMind использует объединение четырёх новейших фреймов, чтобы представить текущее состояние. Строго говоря, состояние может состоять из чего угодно и какого угодно времени, от прошлого до настоящего. Просто мы обычно полагаем, что сиюминутное состояние является тем, что мы сиюминутно измеряем, однако это не всегда так. Обратите внимание, что нам также не нужны необработанные данные, чтобы представить состояние, – оно может состоять из любых данных, полученных из необработанных. Это можно рассматривать как преобразование признаков необработанных данных. По сути, любые сигналы датчиков агента можно использовать для формирования состояния.

Определение и формализация марковских процессов принятия решений

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

Однако,чтобы собрать головоломку, нам нужна ещё одна часть. Ключевым понятием вмарковском процессе принятия решений является решение. Способ, которым мыпринимаем решение, какие действия предпринять в тех или иных состояниях,называется стратегией. Она обычно обозначается символом π. Формально стратегия не является составной частью собственномарковского процесса принятия решений, но она, наряду с функцией ценности,которую мы вскоре определим более формализовано, является частью решения.Причина, по которой я до сих пор не упоминал стратегию, заключается в том, чтоэто несколько необычное понятие. Мы записываем π в виде математического символа, но для него нет уравнения. Кпримеру, если π – эпсилон-жадныйалгоритм, то как его записать в виде уравнения? Это же алгоритм. Единственноеисключение тут – это когда мы хотим записать оптимальную стратегию, котораяможет быть математически определена в понятиях функции ценности. Мы поговоримоб оптимальных стратегиях и что они означают в следующих лекциях. Но пока что π является скорее сокращённым обозначениемалгоритма, который используется агентом для определения своего поведения всреде.

Всвязи с тем, что марковский процесс принятия решений удовлетворяет марковскомусвойству, мы, как легко догадаться, можем также нарисовать диаграммы переходовсостояний, как мы это делали для марковских и скрытых марковских моделей. Сам яделаю это нечасто, но для вас это может оказаться полезным.

Вновьрассмотрим вероятности перехода состояний p(s’|s,a). Напомню, я утверждал, что, какправило, они определены, хотя это и не всегда так. Почему так? Не забывайте,что состояние – это только то, что возникает из восприятия агентом среды, этоне сама среда. Состояние может быть несовершенным представлением среды, и вэтом случае можно ожидать, что переход состояний будет вероятностным. Например,измеряемое состояние может представлять несколько конфигураций среды. Примеромнесовершенного представления о среде может служить блэк-джек. Можнорассматривать следующую карту крупье как часть состояния, однако если вы –агент, вы не можете видеть эту следующую карту, а значит, она не являетсячастью вашего состояния, она является частью среды.

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

Иногда возникает путаница в вопросе о том, что представляет собой агент, а что – среда. Самостоятельно действуя в среде, вы можете считать себя агентом, но что именно представляете из себя вы? Вы – это ваше тело? Но ваше тело правильнее считать частью среды: тело не принимает решений и не учится. Оно имеет «датчики», передающие сигналы в ваш мозг, и именно он учится и принимает решения. Поэтому следует иметь в виду, где проходит граница между агентом и средой.

Будущие вознаграждения

Формализуем идею общего вознаграждения, в частности нас интересует измерение общего будущего вознаграждения – всего, что начинается с t+1 и далее. Это называется отдачей и обозначается G(t):

Обратитевнимание, что отдача не зависит от вознаграждения в текущий момент времени. Этосвязано с тем обстоятельством, что, строго говоря, когда мы попадаем внекоторое состояние, то получаем вознаграждение, соответствующее этомусостоянию. Здесь нечего прогнозировать, поскольку всё уже случилось.

Теперьпредставьте себе очень длительную задачу, содержащую последовательность изтысяч этапов. Наша цель – максимизировать общее вознаграждение. Но есть лиразница между получением вознаграждения прямо сейчас или получением такого жевознаграждения десять лет спустя? Подумаем о деньгах. Мы знаем, что 1000долларов сегодня – это куда меньше, чем 1000 долларов десять лет назад. Если япредложу вам выбор: получить 1000 долларов сейчас или получить 1000 долларовчерез десять лет, вы, конечно же, выберете деньги сейчас.

Тутмы и приходим к так называемому коэффициенту обесценивания будущихвознаграждений. Он обозначается символом γи характеризуется числом между 0 до 1:

Легкопонять, что γ = 1 означает, что насне волнует, через какое время будет получено вознаграждение, все будущиевознаграждения имеют одинаковые весовые коэффициенты. Если же γ = 0, то это значит, что мы совсем недумаем о будущем. В этом случае получается поистине жадный алгоритм, посколькуагент будет стараться максимизировать лишь своё немедленное вознаграждение.Обычно же выбирается что-то среднее, вроде γ= 0,9, а если у нас задача с очень короткими эпизодами, то обесценивания можети не быть вовсе. Интуитивно понятная причина, по которой возникает желаниеобесценить будущие вознаграждения, состоит в том, что чем дальше мы заглядываемв будущее, тем тяжелее его спрогнозировать. Следовательно, нет смыслаприкладывать все усилия для получения чего-то лишь через десять лет, если вы неуверены, что это действительно случится и что обстоятельства не изменятся.

Каквы могли заметить, сумма в отдаче идёт от τ= 0 до бесконечности. Отметим, что это говорит о непрерывной задаче, тогда какв реальности виденные нами игры – и крестики-нолики и мир-решётка – являютсяэпизодическими. Хотя это чисто математическая тонкость, но на самом деле намнужно записать все наши уравнения в непрерывной форме, поскольку, простоговоря, это упрощает работу с математическими выкладками.

Существует способ объединить эпизодические и непрерывные задачи таким образом, чтобы они были эквивалентны. Делается это следующим образом. Эпизодическая задача имеет конечное состояние. Можно сделать вид, что существует переход состояний из конечного состояния к самому себе, который всегда происходит с вероятностью 1 и всегда даёт вознаграждение 0. Таким образом эпизодическая задача остаётся прежней, но поскольку формально она длится вечно, то она же является и непрерывной.

Функции ценности

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

Функцияценности с заданной стратегией в состоянии s равна ожидаемому значению отдачи при условиитекущего пребывания в состоянии s:

Легкопонять, что γ = 1 означает, что насне волнует, через какое время будет получено вознаграждение, все будущиевознаграждения имеют одинаковые весовые коэффициенты. Если же γ = 0, то это значит, что мы совсем недумаем о будущем. В этом случае получается поистине жадный алгоритм, посколькуагент будет стараться максимизировать лишь своё немедленное вознаграждение.Обычно же выбирается что-то среднее, вроде γ= 0,9, а если у нас задача с очень короткими эпизодами, то обесценивания можети не быть вовсе. Интуитивно понятная причина, по которой возникает желаниеобесценить будущие вознаграждения, состоит в том, что чем дальше мы заглядываемв будущее, тем тяжелее его спрогнозировать. Следовательно, нет смыслаприкладывать все усилия для получения чего-то лишь через десять лет, если вы неуверены, что это действительно случится и что обстоятельства не изменятся.

Каквы могли заметить, сумма в отдаче идёт от τ= 0 до бесконечности. Отметим, что это говорит о непрерывной задаче, тогда какв реальности виденные нами игры – и крестики-нолики и мир-решётка – являютсяэпизодическими. Хотя это чисто математическая тонкость, но на самом деле намнужно записать все наши уравнения в непрерывной форме, поскольку, простоговоря, это упрощает работу с математическими выкладками.

Существует способ объединить эпизодические и непрерывные задачи таким образом, чтобы они были эквивалентны. Делается это следующим образом. Эпизодическая задача имеет конечное состояние. Можно сделать вид, что существует переход состояний из конечного состояния к самому себе, который всегда происходит с вероятностью 1 и всегда даёт вознаграждение 0. Таким образом эпизодическая задача остаётся прежней, но поскольку формально она длится вечно, то она же является и непрерывной.

Функции ценности

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

Функцияценности с заданной стратегией в состоянии s равна ожидаемому значению отдачи при условиитекущего пребывания в состоянии s:

Обратитевнимание, что по определению функция ценности зависит от стратегии. Это связанос тем, что любые будущие переходы состояний зависят от нашей стратегии.Обратите также внимание на то, что функция ценности зависит только от будущих вознаграждений.Это значит, что ценность любого конечного состояния равна нулю, поскольку поопределению мы не можем более совершать никаких переходов состояний и,следовательно, получать какие-либо будущие вознаграждения.

Займёмсятеперь кое-какими алгебраическими выкладками. Обратите внимание, что отдачарекурсивна – мы можем отделитьR(t+1), R(t+2) и так далее:

Посколькуэто ожидаемое значение по π, этозначит, что мы можем выразить π ввиде распределения вероятностей, а точнее в виде вероятности выполнениядействия при заданном пребывании в состоянии s:

Посколькуожидаемые значения являются линейными операторами, мы можем разделить их на двечасти и найти их ожидаемые значения по отдельности. Вначале рассмотрим толькоожидаемое значение R(t+1) при заданном состоянии s:

Посколькуожидаемые значения являются линейными операторами, мы можем разделить их на двечасти и найти их ожидаемые значения по отдельности. Вначале рассмотрим толькоожидаемое значение R(t+1) при заданном состоянии s:

Посколькутут всё стохастическое, то регулируется двумя распределениями вероятностей.Первое – это стратегия π(a|s), определяющая,какое действие будет предпринято. Имея пару состояние-действие s и a, получаем такжераспределение вероятностей p(s’,r|s,a), которое мыможем ограничить до p(r|s,a). Таким образом, оба эти распределениявероятностей нужны для нахождения ожидаемого значения. И разумеется, всё это мыможем записать в терминах полного совместного распределения вероятностейсостояний путём сложения по s:

В действительности мы можем использовать этот результат длявычисления ценности чего угодно с заданными стратегией и текущим состоянием:

Следовательно,мы также можем использовать его и для вычисления второй части ожидаемогозначения, которое мы видели ранее:

Уделитеминуту, чтобы внимательно изучить всё это, или поставьте видео на паузу, покане усвоите.

Эторекурсивное уравнение занимает особое место в обучении с подкреплением – на нёмоснованы все алгоритмы, которые мы будем изучать. Оно называется уравнениемБеллмана в честь известного математика Ричарда Беллмана. Беллман впервыеприменил метод так называемого динамического программирования, о котором вымогли слышать при изучении алгоритмов. Он связан с рекурсией, но эффективнее,поскольку строит решение с использованием подхода «сверху вниз». На самом делеодна из методик, с которой мы познакомимся для решения марковских процессовпринятия решений, и называется динамическим программированием.

Внашем обсуждении функций ценности необходимо коснуться и ещё одной из них. То,с чем мы только что познакомились, называется функцией ценности состояния.Однако есть и другая функция ценности Q(s,a), котораяназывается функцией ценности действия, поскольку действие a также являетсяпараметром этой функции:

Обратите внимание, что поскольку Q имеет два аргумента, то пространство, необходимое для её хранения, является квадратичным. В частности, необходимое нам пространство равно величине набора состояний, умноженному на величину набора действий: |S|x|A|. В следующих частях курса вы увидите, что применяемая функция ценности зависит от используемого алгоритма – в некоторых алгоритмах используется только функция ценности состояний, а в некоторых – только функция ценности действий.

Оптимальная стратегия и оптимальная функция ценности

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

Поговоримоб относительной «доброкачественности» стратегий. Предположим, у нас есть двестратегии π1 и π2. Можно утверждать, что π1 лучше π2, если для всех состояний ожидаемая отдача от π1 больше или равна ожидаемойотдачи от π2:

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

Обратитевнимание, что оптимальные стратегии не обязательно уникальны, а вот оптимальныефункции ценности – обязательно. Можно представить, как две стратегии могутприводить к одинаковым вознаграждениям и, следовательно, к одинаковым функциямценности, однако если у нас одна функция ценности, которая больше другой, тооптимальной стратегией будет лишь та, которая приводит к наибольшей функцииценности.

Аналогичнымобразом можно определить оптимальную функцию ценности действий как максимумфункций ценности действий по всем стратегиям:

Обратитевнимание, что оптимальные стратегии не обязательно уникальны, а вот оптимальныефункции ценности – обязательно. Можно представить, как две стратегии могутприводить к одинаковым вознаграждениям и, следовательно, к одинаковым функциямценности, однако если у нас одна функция ценности, которая больше другой, тооптимальной стратегией будет лишь та, которая приводит к наибольшей функцииценности.

Аналогичнымобразом можно определить оптимальную функцию ценности действий как максимумфункций ценности действий по всем стратегиям:

Всвязи с тем, что оптимальная функция ценности действий связана с оптимальнойстратегией, мы можем определить её рекурсивно в понятиях оптимальной функцииценности состояний:

Функцииценности состояний и ценности действий могут быть связаны следующим образом.Функция ценности состояний означает, что мы всегда выбираем лучшие действия и,следовательно, максимум по всем действиям из Q. Обратите внимание, как Q приводит к ряду практических преимуществ при реализации: если унас есть лишь V(s), то мы должныперепробовать все возможные действия a, чтобы перейти в следующие состояния и получить ценности дляэтих состояний. Однако имея Q, мы можем прямо выбрать лучшее из всех действий a из Q:

Продолжимпреобразования нашего уравнения для V*:

Продолжимпреобразования нашего уравнения для V*:

Этоназывается уравнением оптимальности Беллмана для функции ценности состояний.Заметьте, что оно очень похоже, но не идентично уравнению Беллмана.

Тоже самое можно сделать и для получения уравнения оптимальности Беллмана дляфункции ценности действий:

И последнее, что необходимо обсудить. Имея оптимальная функция ценности, как реализовать оптимальную стратегию? Ключевым тут является то, что функция ценности уже учитывает будущие вознаграждения, а потому, чтобы оптимизировать общее ожидаемое будущее вознаграждение, ничего особенного делать не надо. Всё, что нужно, – это выбрать действие, дающее лучшую ценность для следующего состояния. Обратите внимание на то, что для функции ценности состояний V нам необходимо выполнить поиск вперёд, поскольку сама по себе она не зависит от a. Поэтому с точки зрения реализации мы должны выполнить все возможные действия a, посмотреть, к какому состоянию s’ это приводит, и выбрать то, которое даёт наибольшее V(s’). Имея Q(s), этот поиск можно совершить напрямую. Таким образом, Q(s) эффективно кэширует результаты поиска на один шаг вперёд.

Итоги

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

Кромевсего прочего, мы формализовали структуру марковского процесса принятиярешений; поговорили о стратегиях и отдаче, являющейся общим будущим вознаграждением,а также о том, как обесцениваются будущие вознаграждения при помощикоэффициента обесценивания G. Мы более строго определили функцию ценности иознакомились с двумя её типами: функцией ценности состояний и функцией ценностидействий.

Мырассмотрели уравнение Беллмана, которое рекурсивно определяет функцию ценностичерез функцию ценности следующего состояния.

Мытакже ознакомились с понятием оптимальности и определили оптимальную стратегию,оптимальную функцию ценности состояний и оптимальную функцию ценности действий.С их помощью мы также смогли рекурсивно определить оптимальные функции ценностичерез оптимальные функции ценности следующих состояний, что называетсяуравнениями оптимальности Беллмана.

В следующей части мы начнём рассмотрение алгоритмов вычисления функций ценности для заданной стратегии, а также оптимальных функций ценности и оптимальных стратегий.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: