В сегодняшней статье мы сосредоточимся на создании основанного на модели агента адаптивного динамического программирования (ADP) для изучения MDP. Как мы подробно объяснили в предыдущих историях, мы можем использовать итерацию политики или итерацию значения для решения MDP, если мы знаем его функцию вознаграждения и модель перехода. Однако в реальных приложениях это не всегда так. В результате прямое использование старой доброй итерации политики или значения может оказаться невозможным. Ученик ADP, который является сегодняшней темой, предлагает один из способов решения MDP, даже если мы не знаем его функцию вознаграждения или модель перехода.

Код в этой истории является частью нашего проекта MAD с нуля, где MAD означает машинное обучение, искусственный интеллект и наука о данных. Полный код, использованный в этой истории, можно найти в этом репозитории: https://github.com/clumsyhandyman/mad-from-scratch.

Оглавление:

  1. MAP как черный ящик, взаимодействующий с агентом
  2. Изучение r(s) и p(s′| s, a) как контролируемая задача
  3. Выбрать следующее действие: добыча или разведка?
  4. Псевдокод для обучения ADP на основе моделей
  5. Внедрение обучающего модуля ADP в Python
  6. Последствия дилеммы разведка-эксплуатация
  7. Модельный vs безмодельный

MDP как черный ящик, взаимодействующий с агентом

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

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

В этом случае среда MDP фактически ведет себя как черный ящик. Наш агент вводит пару состояния и действия (s, a), а MDP выводит пару вознаграждения и следующего состояния (r, с′).

В нашем примере мира сетки взаимодействие выглядит примерно так:

  • MDP: Я хочу сыграть в игру. Вы должны выбрать действие от 1 до 4 на каждом этапе.
  • Агент: Хорошо.
  • MDP: Вы начинаете с состояния 8. Какое действие вы выберете?
  • Агент: Я выбираю действие 4.
  • MDP: Сейчас вы находитесь в состоянии 9. Вы получили вознаграждение в размере -0,04.
  • Агент: Я выбираю действие 2.
  • MDP: Сейчас вы находитесь в состоянии 9. Вы получили вознаграждение в размере -0,04.
  • Агент: Я выбираю действие 4.
  • MDP: Сейчас вы находитесь в состоянии 10. Вы получили вознаграждение в размере -0,04.
  • …
  • MDP: Сейчас вы находитесь в состоянии 2. Вы получили вознаграждение в размере -0,04.
  • Агент: Я выбираю действие 2.
  • MDP: Сейчас вы находитесь в состоянии 3. Вы получили награду 1. Вы выиграли игру.

Из этого взаимодействия агент не знает, что состояние 9 находится справа от состояния 8. На самом деле, агент даже не знает, что каждое состояние представляет местоположение в мире сетки. Точно так же агент не знает, что означает каждое действие. Агент знает только последовательность s= 8, a= 4, r= −0,04, s= 9, a= 2, r= −0,04, s= 9, a = 4, r = −0,04…

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

Дело в том, что наш агент никогда не узнает, что на самом деле означают состояния и действия. Наш агент знает только последовательность состояний, действий и наград. Это [s, a, r, s,a, r, s, a, r…] — единственная игра, которую знает наш агент. Как наш агент должен разобраться в этой игре и в конечном итоге выиграть эту игру? Это главный вопрос, на который обучение с подкреплением пытается ответить.

Изучение r(s) и p(s′| s, а) как контролируемая задача

Учитывая набор последовательностей, таких как [s₁, a₁, r₁, s₂, а₂, р₂, с₃, а₃, р₃…], как мы можем оценить функцию вознаграждения r(s) и модель перехода p(s′| с, а)?

Функция вознаграждения проста. Поскольку r(s) является функцией только состояния, и у нас уже есть пары r и s в заданных последовательностях, мы можем напрямую определить корреляцию между r и s. Например, для данных последовательностей [s₁, a₁, r₁, s₂, а₂, р₂, с₃, а₃, р₃…], в момент времени t = 1 мы остановились на s₁ и выбрали действие a₁. В результате мы получили вознаграждение в размере r₁ и получили s₂. Другими словами, достижение s₂ связано с вознаграждением r₁. Таким образом, награда за состояние s₂ составляет r(s₂) = r₁. Точно так же вознаграждение за состояние s₃ равно r(s₃) = r₂ и так далее.

Модель перехода не так проста, но все же довольно проста. Из заданных последовательностей у нас есть группы (s, a, s′). Подсчитав появление каждого (s, a, s′), мы можем оценить их вероятность, которая равна p(s′| s, a) по определению. Например, s₁ и a₁ связаны с s′ = s₂, что соответствует одному вхождению (s₁, a₁, s₂), s₂ и a ₂ связаны с s₃, что соответствует одному вхождению (s₂, a₂, s₃) , и так далее.

Из всех заданных последовательностей количество определенных (s, a, s′) подсчитывается как n(с, а, с′). Тогда модель перехода можно оценить как

Например, если есть 4 состояния [s₁, s₂, s₃, s₄], и вхождения каждого s′ для (s= s₁, a = a₁, s′) следующие:

Затем,

Тогда модель перехода для (s= s₁, a = a₁) будет

Повторяя это для каждой пары (s, a), мы можем получить оценку каждого элемента матрицы p( с′| с, а).

После того, как у нас есть оценочная функция вознаграждения и оценочная модель перехода, у нас есть оценочная полная картина MDP. Поскольку мы пытаемся оценить модель MDP, этот тип подходов обычно называется на основе модели. Затем мы решаем это, используя итерацию значений или политик так же, как мы объясняли в предыдущих историях. Поскольку итерация значения и итерация политики являются версиями динамического программирования, этот подход называется адаптивным динамическим программированием (ADP).

Выберите следующее действие: эксплуатация или разведка?

Теоретически, используя описанную выше процедуру, мы можем получить оценку r(s) и p(s′| s, a) как можно точнее, если у нас есть бесконечное количество [s, a, r,…] входные последовательности. Тем не менее, бесконечное количество входных последовательностей, по-видимому, нецелесообразно. Лучшее, что мы можем получить, — это достаточно большое количество входных последовательностей. Из этих последовательностей мы можем получить достаточно выборок каждой пары (s, a), чтобы оценить p(s′| s, a) и образцы всех s, чтобы получить r(s). Это означает, что мы должны посетить каждую пару (s, a) большое количество раз. Чтобы гарантировать это, теоретически мы должны сделать так, чтобы каждое действие имело возможность быть выбранным в качестве следующего действия. Это называется исследованием и обычно выполняется путем многократного прохождения игры и случайного выбора действий.

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

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

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

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

Чтобы сбалансировать исследование и эксплуатацию, практический способ состоит в том, чтобы акцентировать внимание на исследовании в начале и постепенно переходить к эксплуатации к концу. Например, если нам разрешено сыграть в 100 игр нашего мира сетки Pac-Man, мы должны сосредоточиться на случайном изучении игры в начале игры, например, в играх с 1 по 30. На этом этапе мы мало что знаем об игре. , и мы должны исследовать как можно больше.

Тогда для игр с 31 по 70, может быть, нам стоит провести половину исследования и половину эксплуатации. Мы кое-чему научились из первых 30 игр, но мы не уверены. Поэтому мы используем эти знания примерно в половине случаев, а в другой половине продолжаем исследовать и изучать новые вещи.

Наконец, для игры с 71 по 100 мы можем предположить, что узнали достаточно, и пришло время выиграть игру. Мы используем знания, полученные в предыдущих 70 играх, и выбираем лучшее из известных нам действий. Наша цель — выиграть эти оставшиеся игры и получить достаточно наград, чтобы покрыть потери, которые мы понесли в предыдущих играх.

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

Псевдокод для обучения ADP на основе моделей

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

Ввод функции восприятия нашего ученика представляет собой набор (s, a, r, s′ ). Это сообщает нашему ученику следующую информацию: если вы стоите в состоянии s и выбираете действие a, вы получаете вознаграждение в размере r и достигаете состояния с’. Затем задача нашего ученика состоит в том, чтобы проанализировать, на что указывает эта информация, и включить ее в свои знания, которые представляют собой предполагаемую функцию вознаграждения и модель перехода.

Вводом функции активации нашего обучаемого является текущее состояние s. Мы задаем нашему ученику вопрос: Эй, ты в состоянии s, какое действие ты выбираешь? Затем задача нашего ученика состоит в том, чтобы выбрать правильное действие a для возврата, уравновешивая исследование и использование на разных этапах обучения.

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

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

Реализовать учащегося ADP в Python

Ученик ADP реализован как класс с функциями восприятия, активации и обновления политики.

Обучающее взаимодействие с черным ящиком MDP также реализовано в виде класса. Проблема в мире сетки MDP, а учащийся — учащийся ADP.

Например, следующий код может быть реализован для решения нашего примера сетки 3 × 4. Пороговое значение вероятности начинается с 1,0 и умножается на коэффициент затухания 0,9 при каждом обновлении политики.

Процесс обучения можно визуализировать на следующем рисунке: нижний подрисунок отображает вознаграждение, полученное в каждой игре с 1 по 100 игру, а верхний подрисунок отображает сумму вознаграждений перед определенной игрой. Например, в первой игре мы получили около 0,25, во второй — -2,5 и так далее. Суммируя вознаграждение за игру 1 и игру 20, мы получили общее вознаграждение около 0, а суммировав вознаграждение за игру 1 и игру 40, мы накопили общее вознаграждение около 20 и так далее.

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

В нашей истории итерации политики мы оценили оптимальную политику и пришли к выводу, что ее ожидаемое вознаграждение составляет около 0,7. Другими словами, если мы заранее знаем весь MDP и оптимально сыграем в игру 100 раз, ожидаемое общее вознаграждение составит около 70. Используя наш обучаемый ADP, ничего не зная о MDP в начале, мы все равно получили общее вознаграждение. около 60 в конце. Это показывает, что наш учащийся ADP может эффективно изучать этот мир сетки MDP.

Последствия дилеммы разведка-эксплуатация

В нашем алгоритме коэффициент затухания ξ регулирует скорость перехода от разведки к эксплуатации. Вначале, предполагая, что ϵ = 1,0, мы на 100 % сосредотачиваемся на исследовании. После первой игры ϵ = ξϵ = ξ, что указывает на то, что у нас есть вероятность ξ исследовать и вероятность использования 1−ξ. Точно так же после n игр ϵ = ξ ⁿ, что указывает на то, что вероятность исследования равна ξ ⁿ .

Давайте посмотрим, если ξ = 0,9 после 100 игр,

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

Напротив, если ξ = 0,99, после 100 игр

В этом случае у нас есть вероятность 36,6% выбора разведки, а остальных 63,4% выбора эксплуатации. Мы предпочитаем эксплуатацию, но у нас еще есть возможность продолжить разведку.

Наш старый добрый пример сетки 3 × 4 кажется слишком маленьким, чтобы показать какие-либо существенные различия при использовании разных коэффициентов затухания. Возьмем более крупный пример. Этот сетчатый лабиринт также взят из книги Стюарта Рассела и Питера Норвига Artificial Intelligence A Modern Approach.

Чтобы упростить сравнение с нашим предыдущим примером, мы реализуем аналогичные правила: красный квадрат — это проигрышное конечное состояние с вознаграждением -2,5, зеленый квадрат — выигрышное конечное состояние с вознаграждением +10,0, а все остальные белые квадраты проходимы. состояния с вознаграждением -0,04.

Стохастика MDP такая же, как и в предыдущем примере: вероятность 0,8 выполнить, как задумано, вероятность 0,1 пойти на 90 градусов по часовой стрелке и вероятность 0,1 пойти на 90 градусов против часовой стрелки.

Поскольку этот мир сетки 19×32 намного больше, чем наш предыдущий мир 3×4, мы ожидаем, что нашему учащемуся потребуется больше игр, чтобы изучить его. Давайте посмотрим, что произойдет, когда мы обучим нашего ученика ADP 1000 играм в этом мире с более крупной сеткой.

Когда коэффициент затухания установлен равным 0,99, наш учащийся ADP, кажется, работает довольно хорошо. Ожидаемое вознаграждение за одну игру составляет около 6,9 (получено путем мошенничества с использованием итерации политики или итерации значения), а наш учащийся ADP получил общее вознаграждение около 4000 из 1000 игр, в результате чего среднее вознаграждение составляет около 4 за игру.

Однако, если коэффициент затухания слишком велик, например, 0,999, наш ученик слишком сосредоточился на исследовании. В результате левая часть V-образной кривой общего вознаграждения очень широкая. Короче говоря, наш ученик потратил слишком много игр на ненужные исследования, и окончательная награда составляет около -20 000, что не так уж хорошо по сравнению с 4 000 в предыдущем случае.

Напротив, если коэффициент затухания слишком мал, например, 0,9, то наш ученик не провел достаточно игр на исследование. Вместо этого наш ученик преждевременно принял решение, которое является неоптимальным. Другими словами, наш ученик слишком рано начал эксплуатировать. В результате левая часть V-образной кривой общего вознаграждения чрезвычайно узкая, и итоговое вознаграждение в размере около –15 000 также не является удовлетворительным.

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

На основе моделей и без моделей

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