Искусственный интеллект. Машинное обучение - Джейд Картер

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

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

2. Выбор действия: Агент выбирает действие на основе текущего состояния с помощью некоторой стратегии, такой как epsilon-жадная стратегия. Например, с некоторой вероятностью агент выбирает случайное действие, а с вероятностью 1-epsilon выбирает действие с максимальной оценкой Q-функции.

3. Взаимодействие со средой и получение награды: Агент выполняет выбранное действие и взаимодействует со средой. Он получает награду за свое действие, которая может быть положительной, если он приближается к цели, или отрицательной, если он удаляется от нее.

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

5. Повторение: Процесс выбора действия, взаимодействия со средой и обновления Q-значения повторяется до тех пор, пока агент не достигнет целевой позиции или не выполнит определенное количество шагов.

Приведенный ниже код демонстрирует простую реализацию метода Q-обучения на примере задачи блоков, используя библиотеку `numpy` для вычислений:

```python

import numpy as np

# Инициализация Q-таблицы

num_states = 5 # Количество состояний

num_actions = 4 # Количество действий (вверх, вниз, влево, вправо)

Q_table = np.zeros((num_states, num_actions)) # Инициализация Q-таблицы нулями

# Гиперпараметры

learning_rate = 0.1

discount_factor = 0.9

epsilon = 0.1 # Вероятность выбора случайного действия

# Простая среда блоков (0 – пустое место, 1 – блок)

environment = np.array([

[0, 0, 0, 0, 0],

[0, 1, 1, 1, 0],

[0, 0, 0, 1, 0],

[0, 1, 1, 1, 0],

[0, 0, 0, 0, 0]

])

# Функция для выполнения одного шага Q-обучения

def q_learning_step(state):

# Выбор действия

if np.random.rand() < epsilon:

action = np.random.randint(num_actions) # Случайное действие

else:

action = np.argmax(Q_table[state]) # Действие с наибольшим Q-значением

# Взаимодействие со средой и получение награды

reward = -1 # Негативная награда за каждый шаг

# Обновление Q-значения

next_state = (state[0] + 1, state[1]) # Пример следующего состояния (движение вниз)

max_next_Q = np.max(Q_table[next_state]) if next_state[0] < num_states else 0 # Максимальное Q-значение для следующего состояния

target_Q = reward + discount_factor * max_next_Q # Целевое Q-значение

Q_table[state][action] += learning_rate * (target_Q – Q_table[state][action]) # Обновление Q-значения

# Обучение

num_episodes = 1000

for _ in range(num_episodes):

state = (0, 0) # Начальное состояние

while state[0] < num_states – 1: # Пока не достигнута конечная позиция

q_learning_step(state)

state = (state[0] + 1, state[1]) # Переход к следующему состоянию

# Вывод Q-таблицы

print("Q-таблица:")

print(Q_table)

```

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

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

Динамическое программирование

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

Принцип оптимальности Беллмана является основой динамического программирования в RL. Он утверждает, что оптимальные значения функций ценности удовлетворяют принципу оптимальности, то есть оптимальное значение функции ценности для каждого состояния равно максимальной сумме награды, которую агент может получить, начиная с этого состояния и действуя оптимально в дальнейшем.

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

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

Пример 1

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

1. Определение MDP: В этой задаче состоянием MDP может быть каждая позиция в лабиринте, действиями – движения робота (например, вперед, назад, влево, вправо), наградой – отрицательное значение за каждый шаг и положительная награда за достижение выхода.

2. Функция перехода: Она определяет вероятности перехода из одного состояния в другое при выполнении определенного действия. Например, если робот движется вперед, то с вероятностью 0.8 он останется на месте, с вероятностью 0.1 перейдет в соседнюю клетку влево и с вероятностью 0.1 – вправо.

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

4. Принцип оптимальности Беллмана: Согласно принципу оптимальности, оптимальная функция ценности для каждого состояния равна максимальной сумме награды, которую робот может получить, начиная с этого состояния и действуя оптимальным образом.

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

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

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

Давайте определим лабиринт, где:

– 0 обозначает свободную ячейку,

– 1 обозначает препятствие,

– 2 обозначает выход из лабиринта.

Предположим, что размер лабиринта составляет 5x5:

```

[0, 0, 1, 1, 0]

[0, 1, 1, 0, 1]

[0, 0, 0, 0, 1]

[1, 1, 1, 0, 0]

[0, 0, 1, 0,