Обучение агента методом Монте Карло

@Darkos · Регистрация: 16.05.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте. Пытаюсь разобраться с методом Монте Карло.

Есть среда состоящая из пяти состояний связанных в линейный отрезок:
Название: states.PNG
Просмотров: 56

Размер: 1.4 Кб

Название: states.PNG
Просмотров: 56

Размер: 1.4 Кб

Агент может за одно действие перейти в соседнее состояние, т.е. из S1в S2, из S3 в S4, соответственно варианты действий в каждом состоянии у агента A = {влево, вправо}. В крайних состояниях(S1 и S5) действия влево и вправо соответственно оставляют агента в том же состоянии.

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

Правильно ли я понимаю, что стратегия поведения агента будет определятся функцией ценности действия а в состоянии s, а само состояние будет описано координатой состояния и координатой терминального состояния(к примеру если терминальное состояние S5 то состояние S1 будет описано как {1,5})? Тогда получается что необходимо будет хранить 5^2 состояний и для каждого по ценности двух действий?

@Mikhaylo · 27.01.2019, 14:05

Сообщение от Darkos

стратегия поведения агента будет определятся функцией ценности действия а в состоянии s

Я бы не называл "терминальное состояние" состоянием. Состояние - это внутренняя переменная, а в вашем случае "терминал" - это внешний воздействующий фактор.
Это вопрос чисто терминологический.

Сообщение от Darkos

Тогда получается что необходимо будет хранить 5^2 состояний и для каждого по ценности двух действий?

Ага, матрица ценности 2*(5^2). Нарисуйте соответствующую табличку.

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

@Darkos · 27.01.2019, 14:21 **[ТС]**

Сообщение от Mikhaylo

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

Да. Я читаю книгу Р. С. Саттон, Э. Г. Барто. "Обучение с подкреплением", там описано, что в конце эпизода, т.е. когда достигнуто терминальное состояние происходит обновление ценностей посещенных состояний.

Мне только не понятно, если к примеру состояния будут описываться большим числом параметров и вообще их будет больше, не будет ли их слишком много? То есть как то ограничивается количество состояний или это не играет особой роли?

@Mikhaylo · 27.01.2019, 17:07

"эпизод" - это последовательность решений a от начала до победы?
"изучающие старты" - это Return?
"выгода, следующая за первым посещением s, a" - это некоторая константа для данной конкретной задачи?

Этот псевдокод обобщенный для метода Монте-Карло или это чисто для данной среды с пятью состояниями?

@Darkos · 27.01.2019, 17:58 **[ТС]**

Сообщение от Mikhaylo

"эпизод" - это последовательность решений a от начала до победы?

Да.

Сообщение от Mikhaylo

"изучающие старты" - это Return?

Я точно не вник в этот термин, как я понял это тестовые начальные условия для обучения.

Сообщение от Mikhaylo

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

Да.

Сообщение от Mikhaylo

Этот псевдокод обобщенный для метода Монте-Карло или это чисто для данной среды с пятью состояниями?

Это обобщенный псевдокод .

@Mikhaylo · 27.01.2019, 18:38

Ну тогда для метода Монте-Карло имеет место следующее:
1. Коли R является константой (например, R = 1), то Return(s, a) - это счетчик успехов, а Q(s, a) - это тоже константа, равная выгоде R.
2. Стратегия pi(s) - при равнозначности всех Q(s,a) - это произвольное блуждание.

Что-то не так.

Добавлено через 3 минуты
Может R = число шагов от начала до успеха (длина эпизода)? (Только argmax надо заменить на argmin, чтобы минимизировать число шагов).

@Darkos · 27.01.2019, 18:53 **[ТС]**

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

@Mikhaylo · 27.01.2019, 19:18

Что такое r[i]?

@Darkos · 27.01.2019, 21:23 **[ТС]**

Сообщение от Mikhaylo

Что такое r[i]?

По идее награда за действие. Я запутался походу.

Как сейчас у меня работает - записывается список действий до момента наступления терминального состояния, к примеру: агент изначально в состоянии 1, терминальное состояние 5.
В списке действия {(1, вправо),(2, вправо),(3, вправо),(4, вправо)}.
За достижение терминального состояния агент получает награду 1. Оценка всех предшествующих решений корректируется в соответствии с формулой Q(s) = Q(s) + ALPHA*(Q(s+1) - Q(s)), где ALPHA это вручную подбираемый параметр, в моем случае 0.1. То есть в результате получится:
Q(4, вправо) = 1
Q(3, вправо) = 0.1
Q(2, вправо) = 0.01
Q(1, вправо) = 0.001

Как то так, я не знаю, поправьте если я не правильно все понял.

@Mikhaylo · 28.01.2019, 05:02

Сообщение от Darkos

Q(s) = Q(s) + ALPHA*(Q(s+1) - Q(s))

Что-то с рекурсией тут...
Это коррекция выполняется каждый шаг эпизода или реже - каждый эпизод?

@Darkos · 28.01.2019, 08:03 **[ТС]**

Каждый эпизод.

@Mikhaylo · 28.01.2019, 17:22

Сообщение от Mikhaylo

Q(s+1)

А что значит (s+1)? Разве s обозначает разные переменные - здесь Q(s) и здесь Q(s, a)?

@Darkos · 28.01.2019, 19:10 **[ТС]**

Сообщение от Mikhaylo

А что значит (s+1)?

Значение из таблицы ценностей соответствующее следующему состоянию, точнее наиболее выгодному действию в следующем состоянии. Хотя по моему я начал путать ценности действий и ценности состояний, поправьте меня если это так. Я так это рассчитывал - если текущее состояние 3 то Q(s) = Q(3), а Q(s+1) = Q(s, вправо) = max {Q(4,вправо), Q(4, влево)}.

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

@Mikhaylo · 29.01.2019, 05:18

Нет права применять алгебру вида (s+1). У вас среда представлена в виде графа с переходами.

Остановитесь. Начните с самого начала. Перейдите более аккуратно от общей методологии к частной (относящейся к Монте-Карло). Переведите каждую переменную от общего к частному.

@NO_ · 29.01.2019, 17:11

Методом Монте-Карло называется способ приближенного вычисления интегралов.

@Mikhaylo · 29.01.2019, 19:08

А еще способ приближенного вычисления площади сложной фигуры (не обязательно заданной аналитически), а еще...

@Darkos · 29.01.2019, 20:50 **[ТС]**

Сообщение от Mikhaylo

Начните с самого начала.

Хорошо.

Описание среды есть: 5 состояний, по два возможных действия в каждом, вознаграждение в размере 1 при достижении состояния 5 и вознаграждение 0 для остальных состояний.

Агент будет совершать с вероятностью E случайное действие и с вероятностью 1-E жадное, т.е. для которого Q(s,a) максимальное.

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

Название: q.PNG
Просмотров: 29

Размер: 3.0 Кб

Название: q.PNG
Просмотров: 29

Размер: 3.0 Кб

Правильно мыслю?

@Mikhaylo · 30.01.2019, 05:19

Ну да. По псевдокоду вы должны заполнить Q(s,a) и pi(s) произвольными числами. Это два массива - двумерный и одномерный. Заполняйте их.

Изучающие старты, судя по книжке, это эпизоды, полученные по некоторой "изучающей стратегии", которая не исключает ни один переход между состояниями, т.е. вероятность каждого перехода ненулевая. Если бы вероятность была бы равна 0, то обучение этому переходу было бы невозможным. Таких изучающих стратегий бесконечное количество, но надо что-то выбрать.

@Darkos · 31.01.2019, 07:53 **[ТС]**

Заполнил я таблицы, вроде получилось правильно. Возникает такой вопрос, могу ли я в процессе модифицировать состояние?
К примеру, если состояние описывается координатой и координатой терминального состояния {1;5} или {2;5}, могу ли я итоге хранить функцию ценностей где состояние будет описано координатой и положением терминального состояния относительно текущего, т.е. {1;справа} или {5;слева}? Тогда в таблице будет не 2*(5^2) а всего 20 оценок.

@wer1 · 31.01.2019, 09:18

Сообщение от Darkos

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

Уважаемый Darkos,
если я всё правильно понял, то необходимая вам матрица будет обладать следующими свойствами
1. симметрия (пример {1, 5} = {5, 1} или (2, 3) = (3, 2))
2. если новое терминальное состояние совпадает со старым (например {3, 3}), то никуда двигаться не надо. Такие состояния {1, 1}; {2, 2}; {3, 3}; {4, 4}; {5, 5} можно обозначить числом 0?
3. отсюда следует, что у вас всего 20 терминальных состояний.
4. кроме всего прочего, чтобы различать направление движения, достаточно охарактеризовать движение вправо положительным числом (например +1), а влево - отрицательным (например -1)
5. в принципе и терминальным состояниям можно присвоить знак. Но тут надо ещё подумать...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@Darkos 8 / 8 / 12 Регистрация: 16.05.2014 Сообщений: 151

	Обучение агента методом Монте Карло 27.01.2019, 12:07. Показов 2512. Ответов 26 Метки нет (Все метки) Здравствуйте. Пытаюсь разобраться с методом Монте Карло. Есть среда состоящая из пяти состояний связанных в линейный отрезок: Агент может за одно действие перейти в соседнее состояние, т.е. из S1в S2, из S3 в S4, соответственно варианты действий в каждом состоянии у агента A = {влево, вправо}. В крайних состояниях(S1 и S5) действия влево и вправо соответственно оставляют агента в том же состоянии. В одном из состояний находится агент, другое случайным образом выбранное состояние является терминальным. Задачей агента является добраться в терминальное состояние, после чего другое состояние будет выбрано терминальным и уже туда нужно будет добраться агенту, и т.д. Правильно ли я понимаю, что стратегия поведения агента будет определятся функцией ценности действия а в состоянии s, а само состояние будет описано координатой состояния и координатой терминального состояния(к примеру если терминальное состояние S5 то состояние S1 будет описано как {1,5})? Тогда получается что необходимо будет хранить 5^2 состояний и для каждого по ценности двух действий? 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	27.01.2019, 17:07
	"эпизод" - это последовательность решений a от начала до победы? "изучающие старты" - это Return? "выгода, следующая за первым посещением s, a" - это некоторая константа для данной конкретной задачи? Этот псевдокод обобщенный для метода Монте-Карло или это чисто для данной среды с пятью состояниями? 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	27.01.2019, 18:38
	Ну тогда для метода Монте-Карло имеет место следующее: 1. Коли R является константой (например, R = 1), то Return(s, a) - это счетчик успехов, а Q(s, a) - это тоже константа, равная выгоде R. 2. Стратегия pi(s) - при равнозначности всех Q(s,a) - это произвольное блуждание. Что-то не так. Добавлено через 3 минуты Может R = число шагов от начала до успеха (длина эпизода)? (Только argmax надо заменить на argmin, чтобы минимизировать число шагов). 0

@Darkos 8 / 8 / 12 Регистрация: 16.05.2014 Сообщений: 151
	27.01.2019, 18:53 [ТС]
	На сколько я понял выгода R это не константа, а усреднение всех последующих вознаграждений которые можно получить выполняя это действие. 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	27.01.2019, 19:18
	Что такое r[i]? 0

@Darkos 8 / 8 / 12 Регистрация: 16.05.2014 Сообщений: 151
	28.01.2019, 08:03 [ТС]
	Каждый эпизод. 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	29.01.2019, 05:18
	Нет права применять алгебру вида (s+1). У вас среда представлена в виде графа с переходами. Остановитесь. Начните с самого начала. Перейдите более аккуратно от общей методологии к частной (относящейся к Монте-Карло). Переведите каждую переменную от общего к частному. 1

@NO_ 120 / 40 / 9 Регистрация: 29.10.2016 Сообщений: 243
	29.01.2019, 17:11
	Методом Монте-Карло называется способ приближенного вычисления интегралов. 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	29.01.2019, 19:08
	А еще способ приближенного вычисления площади сложной фигуры (не обязательно заданной аналитически), а еще... 0

@Mikhaylo 698 / 574 / 75 Регистрация: 20.09.2014 Сообщений: 3,709
	30.01.2019, 05:19
	Ну да. По псевдокоду вы должны заполнить Q(s,a) и pi(s) произвольными числами. Это два массива - двумерный и одномерный. Заполняйте их. Изучающие старты, судя по книжке, это эпизоды, полученные по некоторой "изучающей стратегии", которая не исключает ни один переход между состояниями, т.е. вероятность каждого перехода ненулевая. Если бы вероятность была бы равна 0, то обучение этому переходу было бы невозможным. Таких изучающих стратегий бесконечное количество, но надо что-то выбрать. 1

@Darkos 8 / 8 / 12 Регистрация: 16.05.2014 Сообщений: 151
	31.01.2019, 07:53 [ТС]
	Заполнил я таблицы, вроде получилось правильно. Возникает такой вопрос, могу ли я в процессе модифицировать состояние? К примеру, если состояние описывается координатой и координатой терминального состояния {1;5} или {2;5}, могу ли я итоге хранить функцию ценностей где состояние будет описано координатой и положением терминального состояния относительно текущего, т.е. {1;справа} или {5;слева}? Тогда в таблице будет не 2*(5^2) а всего 20 оценок. 0