WikiDer > Динамический дискретный выбор

Модели с динамическим дискретным выбором (DDC), также известный как модели дискретного выбора динамическое программирование, смоделируйте выбор агента над отдельными вариантами, которые имеют значение в будущем. Вместо того, чтобы предполагать, что наблюдаемый выбор является результатом статической максимизации полезности, наблюдаемый выбор в моделях DDC предполагается результатом максимизации агентом приведенная стоимость полезности, обобщая теория полезности на которой дискретный выбор модели основаны.^[1]

Цель методов DDC - оценить структурные параметры процесса принятия решения агентом. Как только эти параметры известны, исследователь может затем использовать оценки для моделирования того, как агент будет вести себя в контрфактическом состоянии мира. (Например, как изменится решение потенциального студента о зачислении в колледж в ответ на повышение платы за обучение.)

Математическое представление

Агент ${ displaystyle n}$с проблема максимизации математически можно записать следующим образом:

${ Displaystyle V left (x_ {n0} right) = max _ { left {d_ {nt} right } _ {t = 1} ^ {T}} mathbb {E} left ( sum _ {t ^ { prime} = t} ^ {T} sum _ {i = 1} ^ {J} beta ^ {t'-t} left (d_ {nt} = i right) U_ {nit} left (x_ {nt}, varepsilon _ {nit} right) right),}$

куда

• ${ displaystyle x_ {nt}}$ находятся переменные состояния, с ${ displaystyle x_ {n0}}$ агент начальное состояние
• ${ displaystyle d_ {nt}}$ представляет ${ displaystyle n}$решение из числа ${ displaystyle J}$ дискретные альтернативы
• ${ Displaystyle бета в влево (0,1 вправо)}$ это коэффициент дисконтирования
• ${ displaystyle U_ {nit}}$ это Утилита потока ${ displaystyle n}$ получает от выбора альтернативы ${ displaystyle i}$ в период ${ displaystyle t}$, и зависит как от состояния ${ displaystyle x_ {nt}}$ и ненаблюдаемые факторы ${ displaystyle varepsilon _ {нит}}$
• ${ displaystyle T}$ это временной горизонт
• Ожидание ${ Displaystyle mathbb {E} влево ( cdot right)}$ взят на себя как ${ displaystyle x_ {nt}}$'песок ${ displaystyle varepsilon _ {нит}}$в ${ displaystyle U_ {nit}}$. То есть агент не уверен в будущих переходах в состояниях, а также не уверен в будущих реализациях ненаблюдаемых факторов.

Упрощение предположений и обозначений

Стандартно налагаются следующие упрощающие предположения и обозначения задачи динамического принятия решений:

1. Полезность потока аддитивно разделима и линейна по параметрам.

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

${ displaystyle { begin {alignat} {5} U_ {nit} left (x_ {nt}, varepsilon _ {nit} right) && ; = ; && u_ {nit} && ; + ; && varepsilon _ {nit} && ; = ; && X_ {nt} alpha _ {i} && ; + ; && varepsilon _ {nit} end {alignat}}}$

2. Задачу оптимизации можно записать в виде Уравнение беллмана

Определить ${ Displaystyle V_ {nt} (x_ {nt})}$ в ex ante функция ценности для индивидуального ${ displaystyle n}$ в период ${ displaystyle t}$ непосредственно перед ${ displaystyle varepsilon _ {nt}}$ раскрывается:

${ displaystyle V_ {nt} (x_ {nt}) = mathbb {E} max _ {i} left {u_ {nit} (x_ {nt}) + varepsilon _ {nit} + beta int _ {x_ {t + 1}} V_ {nt + 1} (x_ {nt + 1}) , dF left (x_ {t + 1} mid x_ {t} right) right }}$

где оператор ожидания ${ displaystyle mathbb {E}}$ закончился ${ displaystyle varepsilon}$и где ${ displaystyle dF left (x_ {t + 1} mid x_ {t} right)}$ представляет собой распределение вероятностей по ${ displaystyle x_ {t + 1}}$ при условии ${ displaystyle x_ {t}}$. Ожидание по переходам между состояниями достигается путем вычисления интеграла по этому распределению вероятностей.

Можно разложить ${ Displaystyle V_ {nt} (x_ {nt})}$ на детерминированную и стохастическую составляющие:

${ displaystyle V_ {nt} (x_ {nt}) = mathbb {E} max _ {i} left {v_ {nit} (x_ {nt}) + varepsilon _ {nit} right } }$

куда ${ displaystyle v_ {nit}}$ ценность выбора альтернативы ${ displaystyle i}$ вовремя ${ displaystyle t}$ и записывается как

${ displaystyle v_ {nit} (x_ {nt}) = u_ {nit} left (x_ {nt} right) + beta int _ {x_ {t + 1}} mathbb {E} max _ {j} left {v_ {njt + 1} (x_ {nt + 1}) + varepsilon _ {njt + 1} right } , dF (x_ {t + 1} mid x_ {t} )}$

где теперь ожидание ${ displaystyle mathbb {E}}$ берется за ${ displaystyle varepsilon _ {njt + 1}}$.

3. Задача оптимизации следует за Марковский процесс принятия решений

Штаты ${ displaystyle x_ {t}}$ следовать Цепь Маркова. То есть достижение состояния ${ displaystyle x_ {t}}$ зависит только от государства ${ displaystyle x_ {t-1}}$ и нет ${ displaystyle x_ {t-2}}$ или любое предыдущее состояние.

Функции условного значения и вероятности выбора

Функция значения в предыдущем разделе называется функция условного значения, потому что это функция цены, обусловленная выбором альтернативы ${ displaystyle i}$ в период ${ displaystyle t}$. Такая запись функции условного значения полезна при построении формул для вероятностей выбора.

Чтобы записать вероятности выбора, исследователь должен сделать предположение о распределении ${ displaystyle varepsilon _ {нит}}$с. Как и в статических моделях дискретного выбора, это распределение можно считать iid Тип I экстремальное значение, обобщенное экстремальное значение, полиномиальный пробит, или же смешанный логит.

Для случая, когда ${ displaystyle varepsilon _ {нит}}$ является полиномиальным логитом (т. е. нарисованным iid от Распределение экстремальных значений типа I) формулы для вероятностей выбора будут такими:

${ displaystyle P_ {nit} = { frac { exp (v_ {nit})} { sum _ {j = 1} ^ {J} exp (v_ {njt})}}}$

Оценка

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

Наиболее распространенные методы оценки структурных параметров: оценка максимального правдоподобия и метод моделирования моментов.

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

Методы полного решения

Ярким примером метода полного решения является алгоритм вложенной фиксированной точки (NFXP), разработанный компанией Джон Раст в 1987 г.^[2]Алгоритм NFXP подробно описан в его документации.^[3]

Недавняя работа Че-Лин Су и Кеннет Джадд в 2012^[4] реализует другой подход (отвергнутый Rust как неразрешимый в 1987 г.), который использует ограниченная оптимизация функции правдоподобия, частный случай математическое программирование с равновесными ограничениями В частности, функция правдоподобия максимизируется с учетом ограничений, накладываемых моделью, и выражается в терминах дополнительных переменных, которые описывают структуру модели. Этот подход требует мощного программного обеспечения для оптимизации, такого как Artelys Knitro из-за большой размерности задачи оптимизации. После ее решения находятся как структурные параметры, максимизирующие вероятность, так и решение модели.

В следующей статье^[5] Rust и соавторы показывают, что преимущество MPEC в скорости по сравнению с NFXP незначительно. Тем не менее, поскольку вычисления, требуемые MPEC, не зависят от структуры модели, ее реализация намного менее трудоемка.

Несмотря на многочисленных претендентов, оценка максимального правдоподобия NFXP остается ведущим методом оценки для марковских моделей принятия решений.^[5]

Методы без решения

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

Ведущим методом без решения является условный выбор вероятностей, разработанный В. Джозефом Хотцем и Робертом А. Миллером.^[6]

Примеры

Модель замены двигателя автобуса

Модель замены двигателя автобуса, разработанная в основополагающей статье Ржавчина (1987) является одной из первых динамических стохастических моделей дискретного выбора, оцениваемых с использованием реальных данных, и продолжает служить классическим примером задач этого типа.^[4]

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

Позволять ${ displaystyle x_ {t}}$ обозначить одометр чтение (пробег) за период ${ displaystyle t}$, ${ displaystyle c (x_ {t}, theta)}$ стоимость эксплуатации автобуса, зависящая от вектора параметров ${ displaystyle theta}$, ${ displaystyle RC}$ стоимость замены двигателя, и ${ displaystyle beta}$ в коэффициент дисконтирования. Тогда полезность за период определяется как

${ Displaystyle U (x_ {t}, xi _ {t}, d, theta) = { begin {case} -c (x_ {t}, theta) + xi _ {t, { text {keep}}}, & - RC-c (0, theta) + xi _ {t, { text {replace}}}, & end {case}} = u (x_ {t}, d, theta) + { begin {case} xi _ {t, { text {keep}}}, & { textrm {if}} ; ; d = { text {keep}}, xi _ {t, { text {replace}}}, & { textrm {if}} ; ; d = { text {replace}}, end {case}}}$

куда ${ displaystyle d}$ обозначает решение (оставить или заменить) и ${ displaystyle xi _ {t, { text {keep}}}}$ и ${ displaystyle xi _ {t, { text {replace}}}}$ представляют собой компонент полезности, наблюдаемый Гарольдом Цурчером, но не Джоном Рустом. Предполагается, что ${ displaystyle xi _ {t, { text {keep}}}}$ и ${ displaystyle xi _ {t, { text {replace}}}}$ независимы и одинаково распределены с Распределение экстремальных значений типа I, и это ${ Displaystyle хи _ {т, пуля}}$ не зависят от ${ Displaystyle хи _ {т-1, пуля}}$ при условии ${ displaystyle x_ {t}}$.

Тогда оптимальные решения удовлетворяют Уравнение беллмана

${ Displaystyle V (х, xi, theta) = max _ {d = { text {keep}}, { text {replace}}} left {u (x, d, theta) + xi _ {d} + iint V (x ', xi', theta) q (d xi ' mid x', theta) p (dx ' mid x, d, theta) right }}$

куда ${ displaystyle p (dx ' mid x, d, theta)}$ и ${ Displaystyle д (д хi ' середина х', тета)}$ - соответственно плотности переходов для наблюдаемых и ненаблюдаемых переменных состояний. Индексы времени в уравнении Беллмана опускаются, потому что модель сформулирована в параметрах бесконечного горизонта, неизвестная оптимальная политика стационарный, т.е. не зависящие от времени.

Учитывая предположение о распределении ${ Displaystyle д (д хi ' середина х', тета)}$, вероятность конкретного выбора ${ displaystyle d}$ дан кем-то

${ Displaystyle P (d mid x, theta) = { frac { exp {u (x, d, theta) + beta EV (x, d, theta) }} { sum _ {d ' in D (x)} exp {u (x, d', theta) + beta EV (x, d ', theta) }}}}}$

куда ${ Displaystyle EV (х, d, theta)}$ уникальное решение функциональное уравнение

${ displaystyle EV (x, d, theta) = int left [ log left ( sum _ {d = { text {keep}}, { text {replace}}} exp {u (x, d ', theta) + beta EV (x', d ', theta) } right) right] p (x' mid x, d, theta).}$

Можно показать, что последнее функциональное уравнение определяет сжатие если пространство состояний ${ displaystyle x_ {t}}$ ограничено, поэтому будет единственное решение ${ Displaystyle EV (х, d, theta)}$ для любого ${ displaystyle theta}$, и далее теорема о неявной функции держит, поэтому ${ Displaystyle EV (х, d, theta)}$ также гладкая функция из ${ displaystyle theta}$ для каждого ${ Displaystyle (х, d)}$.

Оценка с помощью вложенного алгоритма с фиксированной точкой

Отображение сжатия, приведенное выше, может быть решено численно для фиксированной точки ${ Displaystyle EV (х, d, theta)}$ что дает вероятности выбора ${ Displaystyle Р (д середина х, тета)}$ для любого заданного значения ${ displaystyle theta}$. В логарифмическая вероятность функция может быть сформулирована как

${ displaystyle L ( theta) = sum _ {i = 1} ^ {N} sum _ {t = 1} ^ {T_ {i}} log (P (d_ {it} mid x_ {it) }, theta)) + log (p (x_ {it} mid x_ {it-1}, d_ {it-1}, theta)),}$

куда ${ displaystyle x_ {i, t}}$ и ${ Displaystyle d_ {я, т}}$ представляют данные о переменных состояния (показания одометра) и решения (оставить или заменить) для ${ Displaystyle я = 1, точки, N}$ отдельные автобусы, каждый в ${ Displaystyle т = 1, точки, Т_ {я}}$ периоды.

Совместный алгоритм решения задачи о неподвижной точке при заданном значении параметра ${ displaystyle theta}$ и максимизируя логарифмическую вероятность ${ Displaystyle L ( theta)}$ относительно ${ displaystyle theta}$ был назван Джоном Растом вложенный алгоритм с фиксированной точкой (NFXP).

Реализация вложенного алгоритма с фиксированной точкой в ​​Rust оптимизирована для решения этой проблемы с использованием Итерации Ньютона – Канторовича. вычислять ${ Displaystyle Р (д середина х, тета)}$ и квазиньютоновские методы, такой как Алгоритм Берндта – Холла – Холла – Хаусмана, для максимизации правдоподобия.^[5]

Оценка с MPEC

Во вложенном алгоритме с фиксированной точкой ${ Displaystyle Р (д середина х, тета)}$ пересчитывается для каждого предположения параметров θ. Вместо этого метод MPEC решает ограниченная оптимизация проблема:^[4]

${ Displaystyle { begin {align} max & qquad L ( theta) & { text {subject to}} & qquad EV (x, d, theta) = int left [ log left ( sum _ {d = { text {keep}}, { text {replace}}} exp {u (x, d ', theta) + beta EV (x', d ', theta) } right) right] p (x ' mid x, d, theta) end {align}}}$

Этот метод быстрее вычисляется, чем неоптимизированные реализации вложенного алгоритма с фиксированной точкой, и занимает примерно столько же времени, сколько и высокооптимизированные реализации.^[5]

Оценка методами без решения

В этом случае можно применить метод вероятностей условного выбора Хотца и Миллера. Хотц, Миллер, Сандерс и Смит предложили более простую в вычислительном отношении версию метода и протестировали ее при изучении проблемы замены двигателя автобуса. Метод работает путем оценки вероятностей условного выбора с использованием симуляция, затем опровергая подразумеваемые различия в функции значения.^[7][8]

Смотрите также

• Обратное обучение с подкреплением

Рекомендации

дальнейшее чтение

• Агиррегабирия, Виктор; Мира, Педро (2010). «Структурные модели динамического дискретного выбора: обзор» (PDF). Журнал эконометрики. Elsevier BV. 156 (1): 38–67. Дои:10.1016 / j.jeconom.2009.09.007. ISSN 0304-4076.CS1 maint: ref = harv (связь)
• Кин, Майкл П.; Вулпин, Кеннет И. (2009). «Эмпирические приложения моделей динамического программирования с дискретным выбором». Обзор экономической динамики. 12 (1): 1–22. Дои:10.1016 / j.red.2008.07.001.CS1 maint: ref = harv (связь)
• Ржавчина, Джон (1987). "Оптимальная замена двигателей автобусов GMC: эмпирическая модель Гарольда Цурчера". Econometrica. 55 (5): 999–1033. Дои:10.2307/1911259. ISSN 0012-9682. JSTOR 1911259.CS1 maint: ref = harv (связь)
• Ржавчина, Джон (1994). «Глава 51 Структурная оценка марковских процессов принятия решений». Справочник по эконометрике. 4. Эльзевир. С. 3081–3143. Дои:10.1016 / с1573-4412 (05) 80020-0. ISBN 978-0-444-88766-5. ISSN 1573-4412.