Вопрос или проблема
Курс Дэвида Сильвера по обучению с подкреплением объясняет, как получить оптимальную стратегию из оптимальной функции ценности.
Это кажется очень простым, нужно всего лишь действовать жадно, максимально увеличивая функцию ценности на каждом шаге.
В случае небольшого мирового сетки, после применения алгоритма оценки стратегии вы получаете, например, следующую матрицу для функции ценности:
Вы начинаете с верхнего левого угла, и уникальные действия – это четыре классических перемещения.
Если мы будем следовать жадному подходу, максимизируя функцию ценности на каждом шаге, мы пойдем вправо, затем вниз, вправо, вверх… никогда не достигнув состояния с наилучшей ценностью (20).
Так что вопрос прост: почему нам не нужно догадываться, какие будут будущие вознаграждения, чтобы получить оптимальную стратегию из оптимальной функции ценности? Другими словами, почему достаточно заглянуть на один шаг вперед, чтобы получить оптимальную стратегию?
Похожая проблема уже возникала с вознаграждениями, и мы решили эту проблему, взвесив сумму будущих ожиданий… Почему нам не нужно делать то же самое?
Можете помочь мне понять, что не так с моей интерпретацией?
Большое спасибо за вашу помощь!
Вы привели пример функции ценности, но не оптимальной функции ценности, которая должна удовлетворять:
$$ V^{*}(s) =max_\pi(V^{\pi}(s)) $$
Такая функция ценности позволила бы использовать подход с заглядыванием на один шаг вперед для получения оптимальной стратегии. Потому что оптимальная функция ценности будет определяться итеративно с учетом соседних значений.
Другими словами, проблема с вашей функцией ценности в том, что она не оптимальна, особенно из-за значительного перехода от 0 до 20. Если бы она была оптимальной, рядом с ней у вас было бы значение ближе к 20, и заглядывание вперед следовало бы по этому пути.
Похоже, ваша функция ценности не оптимальна. После оценки функции ценности стратегию необходимо улучшить в соответствии с ней, затем функция ценности должна быть оценена снова, после чего следует улучшение стратегии, эти шаги продолжаются один за другим, пока функция ценности не сойдется к оптимальной. Тогда оптимальная стратегия может быть получена жадно с помощью оптимальной функции ценности.
Ответ или решение
В вопросе о том, почему жадные действия на основе оптимальной функции ценности приводят к получению оптимальной политики, важно рассмотреть несколько ключевых аспектов, связанных с теорией Reinforcement Learning.
-
Оптимальная функция ценности: Для каждой политики (\pi) в состоянии (s) определяем функцию ценности (V^{\pi}(s)), которая представляет собой ожидаемую сумму вознаграждений, получаемых при следовании политике (\pi) из состояния (s). Оптимальная функция ценности (V^{*}(s)) определяется как максимальная функция ценности среди всех возможных политик:
[
V^{*}(s) = \max_{\pi} V^{\pi}(s)
]Это означает, что для каждого состояния оптимальная функция ценности дает лучшее ожидаемое вознаграждение, которое можно получить, начиная из этого состояния.
-
Жадные действия: Когда мы говорим о жадной политике, мы подразумеваем выбор действия, максимизирующего значение функции ценности для следующего состояния. То есть, в каждом состоянии (s) мы выбираем действие (a), такое что:
[
\pi^(s) = \arg\max_a Q^(s, a)
]где (Q^*(s, a)) — это функция действия ценности, которая равна ожидаемому вознаграждению от действия (a) в состоянии (s) с учетом оптимальной политики.
-
Итеративный процесс получения оптимальной политики: Чтобы получить оптимальную политику, мы обычно используем итеративный процесс, состоящий из двух основных этапов: оценка политики и улучшение политики. На этапе оценки мы вычисляем функцию ценности для текущей политики, а на этапе улучшения мы обновляем политику, выбирая действия, которые максимизируют полученные значения. Эти шаги повторяются, пока не достигнем сходимости, когда и функция ценности и политика перестанут изменяться.
-
Одноступенчатый поиск: В вашем вопросе упоминается, что жадные действия могут не приводить к оптимальным результатам, если функция ценности не является истинной оптимальной. Да, если в функции ценности есть резкие переходы, такие как значительная разница между значениями соседних состояний, одноступенчатый жадный выбор действительно может не помочь получить оптимальную стратегию. Однако, если мы предполагаем, что мы имеем дело с оптимальной функцией ценности, то одноступенчатое максимизирование принесет нам оптимальную политику.
-
Обоснование одного шага: Основная причина, по которой одноступенчатый подход работает с оптимальной функцией ценности, заключается в том, что значение состояния отражает ожидаемые вознаграждения, получаемые в будущем, с учетом всех возможных решений. Таким образом, оптимальная функция ценности учитывает все потенциальные вознаграждения от будущих состояний, делая жадное действие в текущем состоянии эффективным для достижения долгосрочного результата.
Подводя итог, жадные действия на основе оптимальной функции ценности обеспечивают оптимальную политику, поскольку при условии истинной оптимальности оценка текущих значений уже включает в себя все возможности будущего вознаграждения. Таким образом, политика, извлеченная путем жадного максимизирования, будет оптимальной.