Понимание роли дисконтного фактора в обучении с подкреплением

43

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

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

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

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

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

Пожалуйста, кто-нибудь может помочь мне понять все это? Спасибо :)

Karnivaurus
источник

Ответы:

36

TL; DR.

Тот факт, что учетная ставка ограничена, чтобы быть меньше 1, является математическим трюком, чтобы сделать бесконечную сумму конечной. Это помогает доказать сходимость определенных алгоритмов.

На практике коэффициент дисконтирования можно использовать для моделирования того факта, что лицо, принимающее решение, не уверено в том, что в следующем моменте принятия решения мир (например, среда / игра / процесс ) закончится.

Например:

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

Коэффициент скидки меньше 1 (подробно)

Чтобы более точно ответить, почему ставка дисконта должна быть меньше единицы, я сначала введу Марковские процессы принятия решений (MDP).

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

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

Награда получается при выполнении действия в состоянии и среда / система переходит в состояние после того, как лицо, принимающее решение, предпринимает действие . Лицо, принимающее решение, придерживается политики , которая для каждого состояния выполняет действие . Таким образом, политика - это то, что сообщает лицу, принимающему решение, какие действия необходимо предпринять в каждом штате. Политика может быть рандомизирована, но пока это не имеет значения.Rai(sj,sk)aisjskaiπ π():SAsjSaiAπ

Цель состоит в том, чтобы найти политику такую , чтоπ

maxπ:S(n)ailimTE{n=1TβnRxi(S(n),S(n+1))}(1),
где - коэффициент дисконтирования, а .ββ<1

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

Проблема называется обесцененной, потому что . Если бы это не была проблема со скидкой сумма не сходилась бы. Все политики, которые получают в среднем положительное вознаграждение в каждый момент времени, суммируются до бесконечности. Это будет критерий вознаграждения с бесконечной суммой горизонта , и он не является хорошим критерием оптимизации.β<1β=1

Вот игрушечный пример, чтобы показать вам, что я имею в виду:

Предположим, что есть только два возможных действия и что функция вознаграждения равна если , и если (вознаграждение не зависит от состояния).a=0,1R1a=10a=0

Понятно, что политика, которая получает больше вознаграждений, заключается в том, чтобы всегда совершать действие а не действие . Я назову эту политику . Я сравню с другой политикой которая выполняет действие с малой вероятностью , а действие противном случае.a=1a=0πππa=1α<<1a=0

В критериях вознаграждения со скидкой в ​​бесконечном горизонте уравнение (1) становится (сумма геометрического ряда) для политики а для политики уравнение (1) становится . Поскольку , мы говорим, что - лучшая политика, чем . На самом деле является оптимальной политикой.11βππα1β11β>α1βπππ

В критериях вознаграждения суммы бесконечного горизонта ( ) уравнение (1) не сходится ни для одной из политик (оно суммирует до бесконечности). Таким образом, в то время как политика достигает более высокого вознаграждения, чем обе политики равны в соответствии с этим критерием. Это одна из причин, по которой критерии вознаграждения в виде бесконечной суммы горизонта бесполезны.β=1ππ

Как я уже упоминал ранее, позволяет сделать так, чтобы сумма в уравнении (1) сходилась.β<1

Другие критерии оптимальности

Существуют и другие критерии оптимальности, которые не предполагают, что :β<1

Цель критериев конечного горизонта состоит в том, чтобы максимизировать дисконтированное вознаграждение до временного горизонтаT

maxπ:S(n)aiE{n=1TβnRxi(S(n),S(n+1))},

для и конечно.β1T

В критериях среднего вознаграждения для бесконечного горизонта целью является

maxπ:S(n)ailimTE{n=1T1TRxi(S(n),S(n+1))},

Конечная заметка

В зависимости от критериев оптимальности можно было бы использовать другой алгоритм, чтобы найти оптимальную политику. Например, оптимальная политика задач с конечным горизонтом будет зависеть как от состояния, так и от фактического момента времени. Большинство алгоритмов обучения подкреплению (например, SARSA или Q-learning) сходятся к оптимальной политике только для критериев бесконечного горизонта со скидкой за вознаграждение (то же самое происходит для алгоритмов динамического программирования). Для критерия среднего вознаграждения не существует алгоритма, который, как было показано, сходится к оптимальной политике, однако можно использовать R-обучение, которое имеет хорошую производительность, хотя и не является хорошей теоретической конвергенцией.

PolBM
источник
1
Любая идея о том, что я должен прочитать, чтобы понять все китайцы в вашем ответе?
Тибо Ной
@thibautnoah Это ИМХО лучший справочник по подкреплению: введение от Саттона и Барто. [ people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf]
PolBM
спасибо, приятель, возможно, понадобится еще одна книга по математике, но я думаю, это начало;)
Тибо Ной,
6

Вы правы, что коэффициент дисконтирования (так называемый - обратите внимание, что он отличается от от TD- ) действует как "срочность жизни" и поэтому является частью проблемы - так же, как и в человеческие жизни: некоторые люди живут так, как будто они будут жить вечно; некоторые люди живут так, как будто они умрут завтра.γλλ

Нил Г
источник
2

TL; DR: факторы дисконтирования связаны с временными горизонтами. Более длительные временные горизонты имеют гораздо большую дисперсию, поскольку они включают в себя больше не относящейся к делу информации, в то время как краткосрочные горизонты смещены в сторону только краткосрочных выгод.

Фактор дисконтирования, по существу, определяет, насколько агенты обучения подкрепления заботятся о вознаграждениях в отдаленном будущем по сравнению с вознаграждениями в ближайшем будущем. Если , агент будет полностью близоруким и узнает только о действиях, которые приносят немедленное вознаграждение. Если , агент будет оценивать каждое из своих действий на основе общей суммы всех своих будущих наград.γ=0γ=1

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

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

Gt=Rt+γRt+1+γ2Rt+2+=k=0γkRt+k=Δt=0eΔt/τRt+Δt
γ=e1/τkΔtτγ=1τ=τвременные шаги в будущем экспоненциально подавляются. Как правило, вы должны выбрать коэффициент дисконтирования, чтобы временной горизонт содержал все соответствующие вознаграждения за конкретное действие, но не больше.

clwainwright
источник