Создание разумного агента игры в крестики-нолики

Простейшее решение для крестиков-ноликов

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

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

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

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

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

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

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

Компоненты системы обучения с подкреплением

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

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

Обратитевнимание, что состояние включает в себя только то, что может восприниматьагент, а не всю среду. Например, если у меня есть робот-пылесос дома вАвстралии, то происходящее в чьём-то доме где-то в Индии никак на состояниемоего робота-пылесоса не повлияет. Другой пример: если у нас есть беспилотныйавтомобиль с обзором в 360 градусов (то есть круговым обзором) и перед ним едетгрузовик, а перед грузовиком – легковой автомобиль, то этот легковой автомобильне является частью нашего состояния, поскольку мы не можем его видеть. То естьсостояние будет тем же, независимо от того, есть легковой автомобиль передгрузовиком, находящемся перед нами, или нет.

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

Спонятием вознаграждения связано то обстоятельство, что оно просто показывает,насколько хорошим было наше действие, неважно, правильное оно или нет. Ононичего не говорит о том, было ли действие лучшим или худшим, это просто число.Если вы агент, то вознаграждение, получаемое на протяжении своей деятельности,не обязательно представляет возможное вознаграждение, которое можно получить вбудущем. Можно вести поиск в не самой лучшей части пространства состояний идостичь локального максимума в 10 очков при глобальном максимуме в 1000 очков,но если вы агент, вы никогда об этом не узнаете. В данной ситуации мы знаем,поскольку сами создали игру. Вновь-таки, это нечто вроде «божественногознания».

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

Далеепоговорим о занятных обозначениях. Мы знаем, что пребывание в состоянии S(t) и действие A(t) ведут нас квознаграждению R(t+1) и состоянию S(t+1). Если отбросить временные индексы, это можно представить в виде4-кратного кортежа (s, a, r, s). При этом, как ни странно, нетожидаемого обозначения r, но это –стандартная запись, поэтому штрих не обязательно значит «в момент времени t+1».

Атеперь настало время определить новые термины, и первым из них будет понятиеэпизода. Эпизод представляет собой один прогон игры. Например, игру вкрестики-нолики мы начинаем с пустой доски. Как только один из игроков поставиттри своих знака в ряд, это будет означать конец эпизода. Как легко догадаться,наш агент обучения с подкреплением будет обучаться на множестве эпизодов, и,скажем, после 1000, 10 000 или 100 000 сыгранных эпизодов мы,вероятно, обучим разумного агента. Необходимое для это время, конечно, являетсягиперпараметром и зависит от самой игры, количества состояний, насколько в игревелик элемент случайности и так далее. Вы уже должны были привыкнуть кгиперпараметрам, если изучали в прошлом курсы по глубокому обучению.

Играв крестики-нолики называется эпизодической задачей, поскольку в неё можноиграть вновь и вновь. Этим она отличается от непрерывной задачи, котораяникогда не заканчивается. Поэтому если вы только и делаете, что играете в игру,то это непрерывная задача. В этом курсе мы не будем рассматривать непрерывныезадачи.

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

Ещёодна известная задача в обучении с подкреплением и системах управления – проблемаобратного маятника, как её называют в системах управления, или проблема тележки(в обучении с подкреплением). Это одна и та же задача, но если в поиске Google набрать «обратный маятник», то поисковик выдастработы в области систем управления, а если «проблема тележки» (cart-pole) – то работы вобласти обучения с подкреплением.

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

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

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

Замечания по определению вознаграждений

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

Хорошимпримером определения вознаграждений является лабиринт. Представьте, что выробот, никогда ранее не видевший данный лабиринт. Вы двигаетесь в случайномнаправлении, пытаясь найти выход. Достижение цели – выход из лабиринта – даётвознаграждение 1, в противном случае вы не получаете ничего. Большинству людейэто кажется разумным, да так оно и есть. Однако с такой структуройвознаграждения робот может никогда не найти выход из лабиринта. Не забывайте,что робот основывается только на своём опыте, и если он получал только нулевоевознаграждение, то может решить, что это всё, на что он способен. Куда лучшимрешением будет давать роботу вознаграждение в -1 для каждого сделанного шага,что будет поощрять его к как можно более быстрому прохождению лабиринта.

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

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

Функция ценности и ваш первый алгоритм обучения с подкреплением

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

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

Задачаприсвоения коэффициентов доверия проявляется и в сфере интернет-рекламы, но вчуть другой форме. В интернет-рекламе это называется атрибуцией, а суть задачив следующем. Если пользователь наконец-то поверил и купил наш товар, но рекламатовара была размещена в десяти различных местах, то какое из этих рекламныхобъявлений заставило поверить покупателя?

Естьразные схемы распределения коэффициентов доверия, например, линейная. Однаколегко понять, что для нас это куда более глубокая задача. Возможно, этополучилось потому, что реклама была показана 10 раз, и именно это заставилокупить наш товар, – тогда в этом смысле все объявления заслуживают равногодоверия. Но может быть, что пользователь не видел рекламу первые девять раз,потому что на странице было что-то более интересное, а на рекламное объявлениеобратил внимание только на десятый раз. В этом случае заслуживает довериятолько десятое объявление. Таким образом, в обучении с подкреплением насинтересует вся последовательность состояний и как эта конкретнаяпоследовательность приводит к конечному вознаграждению.

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

Представьтесебе следующую ситуацию. Мы находимся в состоянии A, предпоследнем состоянии игры, из которого можнопопасть только в два следующих состояния – В и С, каждое из которых является конечным.Состояние B даёт вознаграждение 1, асостояние C – вознаграждение 0. Приэтом у нас есть 50-процентная вероятность попадания в одно из этих состояний –по-видимому, наше агент ещё не знает, какое из них лучше. Ценность состояния B можно считать равной 1, а ценностьсостояния C – равной 0. Какова жеценность состояния A? Можно считатьеё равной 0,5, поскольку это ожидаемое значение конечного вознаграждения сучётом того, что у нас 50-процентная вероятность попасть в одно из конечныхсостояний.

Теперьпредположим, что мы находимся в состоянии А,которое ведёт к единственному возможному состоянию B. Если B даёт нам вознаграждение 1, то ценность А, надо полагать, также должна бытьравна 1, поскольку при достижении состояния A единственным возможным окончанием будет окончание свознаграждением 1. Таким образом, ценность указывает нам о будущей ценностисостояния.

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

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

Функциюценности можно рассматривать как быстрый и эффективный способ определить,насколько хорошо пребывать в данном состоянии без необходимости в поиске повсему остальному дереву игры. Можно попытаться перечислить все возможныепереходы состояний в игре и определить их вероятности, но только представьтесебе, насколько трудоёмка такая задача. На самом деле для большинства игр этобудет невозможно с вычислительной точки зрения. Крестики-нолики простые,поскольку там поле всего 3×3, поэтомуколичество состояний приблизительно равно 39, то есть 19 683. Сувеличением размера доски эта величина растёт по экспоненте: например, если унас поле 4×4, как в игре «4 в ряд», у нас будет уже 316состояний, то есть 43 миллиона. Поэтому, как вы, вероятно, знаете,экспоненциальный рост – это всегда плохо. Поиск в пространстве состоянийвозможен лишь в простейших случаях, поэтому функция ценности, которая можетуказать, насколько успешными мы будем в будущем, основываясь лишь на текущемсостоянии, чрезвычайно полезна. На самом деле я ещё не рассказывал, как найтифункцию ценности, поэтому мы ещё даже не знаем, возможно ли это вообще. Но мыуже можем утверждать, что если бы такая функция была, то она давала быинформацию, причём давала бы мгновенно, без какой-либо необходимости создаватьцелую модель дерева игры и вероятностей переходов. В действительности это поискс постоянным временем, поскольку состояния прямо отображаются в ценности. Этиценности можно сохранять в массиве, который имеет постоянное время поиска. Этапроблема, кстати, является ещё одним примером «проклятья размерности», скоторым мы встречались в других моих курсах по машинному обучению.

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

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

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

Итак,первое, что нужно сделать, – это инициировать функцию ценности. Для всехсостояний, в которых агент выигрывает, будем считать, что ценность равна 1; длявсех состояний, где агент проигрывает или заканчивает игру вничью, ценность считаетсяравной 0, а для всех остальных состояний ценность будем считать равной 0,5. Валгоритмах, которые мы будем рассматривать в дальнейшем, такая тщательнаяинициация не потребуется. Для данной конкретной игры – но не в общем случае! – можносчитать, что функция ценности равна вероятности выигрыша. Ценность всегданаходится в диапазоне между 0 и 1, так что тут всё логично.

Уравнениеобновления имеет несложный вид, но в нём скрыт ряд неочевидных тонкостей.Выглядит оно похоже на градиентный спуск. Мы берём функцию ценности в состоянииV(s) и обновляем её,добавляя к ней коэффициент обучения, умноженный на разницу V(s’)V(s):

где V(s’) – следующее состояние, а V(s) – текущеесостояние.

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

Ввиде псевдокода это может выглядеть примерно так:

for t in range(max_iterations):

   state_history = play_game

    s =state_history[0]

    for s’ instate_history[1:]:

        V(s) =V(s) + learning_rate*(V(s’) – V(s))

        s = s’

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

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

maxV = 0

maxA = None

for a, s’ in possible_next_states:

    if V(s’)> maxV:

    maxV = V(s’)

    max(A) = a

perform action maxA

Мыперебираем все возможные действия, которые ведут ко всем возможным последующимсостояниям, и смотрим на V(s’). Если V(s’) больше, чем максимальное ужевстречавшееся V,мы сохраняем его и соответствующее действие.

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

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

Одначрезвычайно важная тонкость, которую также чрезвычайно трудно разглядеть,изучая лишь формулу обновления, состоит в порядке, в котором необходимообновлять значение ценности для любого заданного состояния. Мы знаем, что влюбом конкретном эпизоде мы обновляем ценности только для тех состояний,которые встретились в этом эпизоде. Однако ключевым в нашем уравнении являетсято, что мы перемещаем V(s) ближе к V(s’). Это значит, что при обновлениипредполагается, что V(s’) является более точным, чем V(s). Для конечногосостояния это верно, поскольку ценность всегда будет 0 или 1 и никогда неизменится. Но если и V(s), и V(s’) имеют одинаковую точность, и при этомобе величины вовсе не точны, то приближение одной к другой ничего не улучшит.Вследствие этого мы должны двигаться назад по истории состояний, посколькуценность текущего состояния всегда обновляется с использованием ценностиследующего состояния, а поскольку мы хотим, чтобы ценность следующего состояниябыла более точной, мы должны обновлять значения ценности в обратном порядке.Это согласуется с тем, что конечное состояние всегда является абсолютно точнымсо значением 0 или 1 и никогда не меняется.

Итак,подведём итоги обсуждённого материала. Вначале мы рассмотрели задачу присвоениякоэффициентов доверия и понятие отложенного вознаграждения. Суть в том, чтодействие, предпринимаемое прямо сейчас, не обязательно приводит к сиюминутномувознаграждению. На самом деле оно может привести к вознаграждению через многоходов. Замечательным примером тут является учёба. Учёба прямо сейчас, скореевсего, лишь заставит нас почувствовать усталость и не даст пообщаться сдрузьями, так что по сути это можно считать даже немного отрицательнойнаградой. Однако будущая награда состоит в том, что мы хорошо сдадим экзамен,получим хорошие оценки и получим высокооплачиваемую работу.

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

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

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

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

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

Share via
Copy link