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

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

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

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

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

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

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

Определение

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

История

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

Вскоре после основополагающей статьи Гиттинса Питер Уиттл продемонстрировал, что индекс возникает как множитель Лагранжа из формулировки динамического программирования проблемы, называемой процессом выхода на пенсию , и предположил, что тот же индекс будет хорошей эвристикой в ​​​​более общей схеме под названием « Беспокойный бандит» . Вопрос о том, как на самом деле рассчитать индекс для цепей Маркова, впервые был поднят Варайей и его сотрудниками. с алгоритмом, который вычисляет индексыот самого большого до самого маленького, авторы: Чен и Катехакис. который показал, что стандартный LP можно использовать для расчета индекса штата, не требуя его расчета для всех штатов с более высокими значениями индекса.LCM Калленберг предоставил параметрическую реализацию LP для вычисления индексов для всех состояний цепи Маркова. Далее, Катехакис и Вейнотт продемонстрировал, что индекс является ожидаемым вознаграждением процесса принятия решений Маркова , построенного на основе цепи Маркова и известного как перезапуск в состоянии , и может быть рассчитан точно путем решения этой проблемы с помощью алгоритма итерации политики или приблизительно с помощью алгоритма итерации значения . Преимущество этого подхода также состоит в том, что он рассчитывает индекс для одного конкретного состояния без необходимости рассчитывать все более крупные индексы, и он действителен в более общих условиях пространства состояний. Более быстрый алгоритм расчета всех индексов был получен в 2004 году Сониным. как следствие его алгоритма исключения оптимальной остановки цепи Маркова. В этом алгоритме вероятность завершения процесса может зависеть от текущего состояния, а не быть фиксированным фактором. Более быстрый алгоритм был предложен в 2007 году Ниньо-Мора. используя структуру параметрического симплекса для уменьшения вычислительных затрат на поворотных этапах и тем самым достигая той же сложности, что и алгоритм исключения Гаусса . Коуэн, В. и Катехакис (2014), обеспечить решение проблемы с помощью потенциально немарковских, несчетных процессов вознаграждения в пространстве состояний, в рамках которых либо коэффициенты дисконтирования могут быть неоднородными и меняться во времени, либо периоды активации каждого бандита могут быть не одинаковыми. фиксированный или единообразный, вместо этого с учетом, возможно, стохастической продолжительности активации, прежде чем будет разрешен переход на другого бандита. Решение основано на обобщенных индексах перезапуска в состоянии.

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

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

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

$\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}}}$

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

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

с $\chi$ являющийся областью X ​ .

Формулировка процесса выхода на пенсию

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

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

где $v(i,k)$ это функция ценности

$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}$

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

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

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

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

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

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

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

$h(i)=w(i)$.

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

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

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

где

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

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

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

$\alpha (i)=h(i)=w(i)$

$\alpha (i)\neq k\nu (i),\forall k$

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

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

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

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

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

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

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

Ссылки

• Скалли, Зив и Харкол-Балтер, Мор и Шеллер-Вольф, Алан (2018). «SOAP: единый чистый анализ всех политик планирования с учетом возраста». Труды АКМ по измерению и анализу вычислительных систем . 2 (1). ACM: 16. дои : 10.1145/3179419 . S2CID   216145213 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Берри, Дональд А. и Фристедт, Берт (1985). Бандитские задачи: Последовательное распределение экспериментов . Монографии по статистике и прикладной теории вероятности. Лондон: Чепмен и Холл. ISBN  978-0-412-24810-8 . {{cite book}}: 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 . S2CID   656323 .
• Коуэн, В. и М.Н. Катехакис (2014). «Многорукие бандиты в условиях всеобщей амортизации и обязательств». Вероятность в инженерных и информационных науках . 29 : 51–76. дои : 10.1017/S0269964814000217 .

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

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