Индекс Гиттинса - Gittins index

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

Терминология

Чтобы проиллюстрировать теорию, мы можем взять два примера из развивающегося сектора, например, из технологий производства электроэнергии: энергия ветра и энергия волн. Если нам представляют две технологии, когда они обе предлагаются в качестве идей, мы не можем сказать, какая из них будет лучше в долгосрочной перспективе, поскольку у нас пока нет данных, на которых можно было бы основывать наши суждения.^[1] Было бы легко сказать, что развитие энергии волн было бы слишком проблематичным, поскольку кажется, что легче установить много ветряных турбин, чем сделать длинные плавающие генераторы, отбуксировать их в море и проложить необходимые кабели.

Если бы нам пришлось делать суждение на том раннем этапе разработки, мы могли бы приговорить одну технологию к тому, чтобы она была поставлена ​​на полку, а другая была бы разработана и введена в действие. Если мы разработаем обе технологии, мы сможем судить о каждой, сравнивая прогресс каждой технологии в установленный временной интервал, например, каждые три месяца. Решения, которые мы принимаем об инвестициях на следующем этапе, будут основаны на этих результатах.^[1]

В статье 1979 г. Бандитские процессы и индексы динамического размещения Джон С. Гиттинс предлагает решение таких проблем. Он выполняет две основные функции "Планирование Проблема »и проблема« Многорукий бандит ».^[2] и показывает, как эти проблемы могут быть решены с помощью Индексы динамического размещения. Сначала он берет «проблему планирования» и сводит ее к машине, которая должна выполнять задания и имеет установленный период времени, например каждый час или день, для завершения каждой работы. Машине дается вознаграждение, основанное на завершении. или нет в течение периода времени, и рассчитывается значение вероятности того, будет оно завершено или нет для каждой работы. Проблема состоит в том, чтобы «решить, какую работу выполнять следующей на каждом этапе, чтобы максимизировать общее ожидаемое вознаграждение».^[1] Затем он переходит к "проблеме многорукого бандита", где каждый тянет "однорукий бандит "рычагу назначается функция вознаграждения за успешное вытягивание и нулевое вознаграждение за неудачное вытягивание. Последовательность успехов формирует Процесс Бернулли и имеет неизвестную вероятность успеха. Есть несколько «бандитов», и распределение успешных попыток рассчитывается и разное для каждой машины. Гиттинс заявляет, что проблема здесь в том, чтобы «решить, какую руку тянуть следующей на каждом этапе, чтобы максимизировать общую ожидаемую награду от бесконечной последовательности движений».^[1]

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

Определение

В прикладной математике «индекс Гиттинса» - это настоящий скаляр значение, связанное с состоянием случайный процесс с функцией вознаграждения и с вероятностью прерывания. Это мера вознаграждения, которое может быть получено процессом, развивающимся с этого состояния, с вероятностью того, что он будет прекращен в будущем. «Индексная политика», индуцированная индексом Гиттинса, состоящая в выборе в любой момент случайного процесса с наивысшим в настоящее время индексом Гиттинса, является решением некоторых остановка проблем например, при динамическом распределении, где лицо, принимающее решение, должно максимизировать общее вознаграждение, распределяя ограниченное количество усилий между несколькими конкурирующими проектами, каждый из которых возвращает стохастическое вознаграждение. Если проекты независимы друг от друга и одновременно может развиваться только один проект, проблема называется многорукий бандит (один вид Стохастическое планирование проблем), а политика индекса Gittins оптимальна. Если несколько проектов могут развиваться, проблема называется Беспокойный бандит и политика индекса Gittins - это хорошо известная эвристика, но в целом оптимального решения не существует. На самом деле в целом эта проблема НП-полный и общепринято считать, что приемлемого решения найти нельзя.

История

Вопросы об оптимальной политике прекращения приема пищи в контексте клинических испытаний были открыты с 1940-х годов, а в 1960-х годах несколько авторов проанализировали простые модели, ведущие к оптимальной индексной политике.^[3] но только в 1970-х Гиттинс и его сотрудники продемонстрировали в марковской структуре, что оптимальное решение для общего случая - это индексная политика, «индекс динамического распределения» которой вычислим в принципе для каждого состояния каждого проекта в зависимости от динамики отдельного проекта.^[2][4] Параллельно с Гиттинсом, Мартин Вайцман установил такой же результат в экономической литературе.^[5]

Вскоре после основополагающей статьи Гиттинса Питер Уиттл^[6]продемонстрировал, что индекс появляется как Множитель Лагранжа из динамическое программирование постановка проблемы, называемая пенсионный процесс и предположил, что тот же индекс будет хорошей эвристикой в ​​более общей настройке с именем Беспокойный бандит. Вопрос, как на самом деле рассчитать индекс для Цепи Маркова впервые обратился Варайя и его сотрудники^[7] с алгоритмом, который вычисляет индексы от самого большого первого до самого маленького, и Чена и Катехаки ^[8] кто показал этот стандарт LP может использоваться для расчета индекса состояния, не требуя его расчета для всех состояний с более высокими значениями индекса.LCM Kallenberg ^[9] предоставил параметрическую реализацию LP для вычисления индексов для всех состояний цепи Маркова. Далее, Катехакис и Вейнотт^[10] продемонстрировали, что индекс - это ожидаемое вознаграждение Марковский процесс принятия решений построенный над цепью Маркова и известный как Перезагрузка в состоянии и может быть точно рассчитан путем решения этой задачи с помощью итерация политики алгоритм, или примерно с итерация значения алгоритм. Этот подход также имеет то преимущество, что вычисляет индекс для одного конкретного состояния без необходимости вычислять все большие индексы, и он действителен при более общих условиях пространства состояний. Более быстрый алгоритм расчета всех индексов был получен в 2004 г. Сониным.^[11] как следствие его алгоритм исключения для оптимальной остановки цепи Маркова. В этом алгоритме вероятность завершения процесса может зависеть от текущего состояния, а не быть фиксированным фактором. Более быстрый алгоритм был предложен в 2007 году Ниньо-Мора. ^[12] за счет использования структуры параметрического симплекса для уменьшения вычислительных затрат на этапах поворота и, таким образом, достижения той же сложности, что и Гауссово исключение алгоритм. Коуэн, В. и Катехакис (2014),^[13] обеспечить решение проблемы с потенциально немарковскими, бесчисленными процессами вознаграждения в пространстве состояний в рамках, в которых либо коэффициенты дисконтирования могут быть неоднородными и изменяться во времени, либо периоды активации каждого бандита могут не совпадать. фиксированный или равномерный, с учетом возможной стохастической продолжительности активации до того, как будет разрешено изменение на другого бандита. Решение основано на обобщенных индексах перезапуска в состоянии.

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

Индекс динамического размещения

Классическое определение Гиттинса и др. является:

${displaystyle u (i) = sup _ {au> 0} {frac {сумма левого угла _ {t = 0} ^ {au -1} eta ^ {t} R [Z (t)] ightangle _ {Z (0) = i}} {сумма левого угла _ {t = 0} ^ {au -1} eta ^ {t} ightangle _ {Z (0) = i}}}}$

куда ${displaystyle Z (cdot)}$ это случайный процесс, ${displaystyle R (i)}$ полезность (также называемая вознаграждением), связанная с дискретным состоянием ${displaystyle i}$,${displaystyle eta <1}$ вероятность того, что случайный процесс не завершится, и ${displaystyle langle cdot angle _ {c}}$ - это оператор условного ожидания, заданныйc:

${displaystyle langle Xangle _ {c} doteq sum _ {xin chi} xP {X = x | c}}$

с ${displaystyle chi}$ будучи домен изИкс.

Формулировка пенсионного процесса

Формулировка динамического программирования в терминах процесса выхода на пенсию, данная Уиттлом, такова:

${displaystyle w (i) = inf {k: v (i, k) = k}}$

куда ${displaystyle v (i, k)}$ это функция значения

${displaystyle v (i, k) = sup _ {au> 0} сумма левого угла _ {t = 0} ^ {au -1} eta ^ {t} R [Z (t)] + eta ^ {t} kightangle _ {Z (0) = i}}$

с теми же обозначениями, что и выше. Он считает, что

${displaystyle u (i) = (1- eta) w (i).}$

Формулировка перезапуска в состоянии

Если ${displaystyle Z (cdot)}$ цепь Маркова с наградами, интерпретация Катехакис и Вейнотт (1987) связывает с каждым состоянием действие перезапуска из одного произвольного состояния. ${displaystyle i}$, тем самым построив марковский процесс принятия решений ${displaystyle M_ {i}}$.

Индекс Гиттинса этого штата ${displaystyle i}$ это наивысшая общая награда, которую можно получить за ${displaystyle M_ {i}}$ если всегда можно выбрать продолжить или перезапустить из этого состояния ${displaystyle i}$.

${displaystyle h (i) = sup _ {pi} сумма левого угла _ {t = 0} ^ {au -1} eta ^ {t} R [Z ^ {pi} (t)] ightangle _ {Z (0) = я}}$

куда ${displaystyle pi}$ указывает на политику ${displaystyle M_ {i}}$. Он считает, что

${displaystyle h (i) = w (i)}$.

Обобщенный индекс

Если вероятность выживания ${displaystyle eta (i)}$ зависит от государства ${displaystyle i}$, обобщение, введенное Сонином (2008), определяет индекс Гиттинса ${displaystyle alpha (i)}$ как максимальное дисконтированное общее вознаграждение за шанс расторжения.

${displaystyle alpha (i) = sup _ {au> 0} {frac {R ^ {au} (i)} {Q ^ {au} (i)}}}$

куда

${displaystyle R ^ {au} (i) = сумма левого угла _ {t = 0} ^ {au -1} R [Z (t)] ightangle _ {Z (0) = i}}$

${displaystyle Q ^ {au} (i) = leftlangle 1-prod _ {t = 0} ^ {au -1} eta [Z (t)] ightangle _ {Z (0) = i}}$

Если ${displaystyle eta ^ {t}}$ заменяется на ${displaystyle prod _ {j = 0} ^ {t-1} eta [Z (j)]}$ в определениях ${displaystyle u (i)}$, ${displaystyle w (i)}$ и ${displaystyle h (i)}$, то выполняется

${displaystyle alpha (i) = h (i) = w (i)}$

${displaystyle alpha (i) eq ku (i), forall k}$

это наблюдение приводит Сонина к выводу, что ${displaystyle alpha (i)}$ и нет ${displaystyle u (i)}$ это «истинное значение» индекса Гиттинса.

Теория массового обслуживания

В теории очередей индекс Гиттинса используется для определения оптимального планирования заданий, например, в очереди M / G / 1. Среднее время завершения заданий по расписанию индекса Gittins можно определить с помощью подхода SOAP.^[14] Обратите внимание, что динамика очереди по сути марковская, а стохастичность обусловлена ​​процессами поступления и обслуживания. Это контрастирует с большинством работ в обучающей литературе, где стохастичность явно учитывается через шумовой член.

Дробные задачи

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

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

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

Примечания

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

• Скалли, Зив и Харчол-Балтер, Мор и Шеллер-Вольф, Алан (2018). «SOAP: Единый чистый анализ всех возрастных политик планирования». Труды ACM по измерению и анализу вычислительных систем. ACM. 2 (1): 16. Дои:10.1145/3179419. S2CID  216145213.CS1 maint: несколько имен: список авторов (связь)
• Берри, Дональд А. и Фристедт, Берт (1985). Бандитские задачи: последовательное размещение экспериментов. Монографии по статистике и прикладной теории вероятностей. Лондон: Чепмен и Холл. ISBN  978-0-412-24810-8.CS1 maint: несколько имен: список авторов (связь)
• Гиттинс, Дж. (1989). Показатели распределения многоруких бандитов. Серия Wiley-Interscience по системам и оптимизации. предисловие Питер Уиттл. Чичестер: John Wiley & Sons, Ltd. ISBN  978-0-471-92059-5.
• Вебер, Р. (Ноябрь 1992 г.). «Об индексе Гиттинса для многоруких бандитов». Анналы прикладной теории вероятностей. 2 (4): 1024–1033. Дои:10.1214 / aoap / 1177005588. JSTOR  2959678.
• Катехакис, М. и А. Ф. Вейнотт младший (1987). «Проблема многорукого бандита: разложение и вычисление». Математика исследования операций. 12 (2): 262–268. Дои:10.1287 / moor.12.2.262. JSTOR  3689689.CS1 maint: несколько имен: список авторов (связь)
• Коуэн, В. и М.Н. Катехакис (2014). «Многорукие бандиты под общей амортизацией и обязательствами». Вероятность в технических и информационных науках. 29: 51–76. Дои:10.1017 / S0269964814000217.

внешняя ссылка

• [1] Реализация в Matlab / Octave алгоритмов вычисления индекса
• Коуэн, Робин (1991). «Черепахи и зайцы: выбор среди технологий с неизведанными достоинствами». Экономический журнал. 101 (407): 801–814. Дои:10.2307/2233856. JSTOR  2233856.