Индекс Гиттинса

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

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

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

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

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

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

Определение

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

История

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

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

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

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

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

${\displaystyle \nu (i)=\sup _{\tau >0}{\frac {\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]\right\rangle _{Z(0)=i}}{\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}\right\rangle _{Z(0)=i}}}}$

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

${\displaystyle \langle X\rangle _{c}\doteq \sum _{x\in \chi }xP\{X=x|c\}}$

с является доменом из  X .${\displaystyle \chi }$

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

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

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

где - функция цены${\displaystyle v(i,k)}$

${\displaystyle v(i,k)=\sup _{\tau >0}\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]+\beta ^{t}k\right\rangle _{Z(0)=i}}$

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

${\displaystyle \nu (i)=(1-\beta )w(i).}$

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

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

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

${\displaystyle h(i)=\sup _{\pi }\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z^{\pi }(t)]\right\rangle _{Z(0)=i}}$

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

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

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

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

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

куда

${\displaystyle R^{\tau }(i)=\left\langle \sum _{t=0}^{\tau -1}R[Z(t)]\right\rangle _{Z(0)=i}}$

${\displaystyle Q^{\tau }(i)=\left\langle 1-\prod _{t=0}^{\tau -1}\beta [Z(t)]\right\rangle _{Z(0)=i}}$

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

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

${\displaystyle \alpha (i)\neq k\nu (i),\forall k}$

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

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

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

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

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

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

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

Примечания

использованная литература

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

внешние ссылки

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