Індекс Гіттінса

Індекс Гіттінса — це показник винагороди, яку можна отримати у відповідності з даним випадковим процесом з певними властивостями, а саме: процес має кінцевий термінальний стан і є можливість завершення на будь-якому проміжному стані. При завершенні в певному стані винагорода, яка отримана, є сумою ймовірнісно-очікуваних винагород, пов'язаних з кожним станом, починаючи з фактичного стану завершення та закінчуючи кінцевим термінальним станом, включно. Індекс є дійсним скаляром.

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

Щоб проілюструвати теорію, розглянемо два приклади з сектору, що розвивається, наприклад, з технологій виробництва електроенергії: енергія вітру та енергія хвиль. Якщо нам буде представлено обидві технології, коли вони пропонуються лише як ідеї, ми не можемо сказати, яка буде кращою у довгостроковій перспективі, оскільки ми ще не маємо даних, на яких ми могли б базувати наші судження. Легко припустити, що хвильова енергія буде більш проблематичною для розвитку, оскільки здається, що легше поставити багато вітрових турбін, ніж виготовити довгі плавучі генератори, відбуксирувати їх у море і прокласти необхідні кабелі.

Якщо ми зробимо висновок на ранньому етапі розвитку, ми можемо відмовитися від однієї технології, та відкласти її на полицю, тоді як інша буде розвиватися та вводитися в експлуатацію. Якщо ми розвиватимемо обидві технології, то зможемо зробити висновки щодо кожної, порівнюючи прогрес через фіксований інтервал часу, наприклад, кожні три місяці. Рішення щодо інвестицій у наступний етап, будуть ґрунтуватися на цих результатах.

У статті 1979 року під назвою «Bandit Processes and Dynamic Allocation Indices» Джон Ч. Гіттінс пропонує рішення для таких проблем. Він бере дві основні функції «проблеми планування» та задачу «багаторукого бандита» і показує, як ці задачі можуть бути вирішені за допомогою динамічних індексів розподілу. Спочатку він розглядає «проблему планування» і зводить її до механізму, який повинен виконувати завдання протягом певного періоду, наприклад, кожну годину чи день, щоб завершити кожне завдання. Механізму надається винагорода на основі завершення або незавершення завдання протягом цього періоду, і розраховується ймовірність завершення або незавершення для кожного завдання. Проблема полягає в тому, «яке завдання обрати для обробки наступним на кожному етапі, щоб максимізувати загальну очікувану винагороду». Потім він переходить до «задачі багаторукого бандита», де кожна дія з важелем «однорукого бандита» відповідає функції винагороди за успіх і нульовій винагороді за невдачу. Послідовність успіхів формує процес Бернуллі і має невідому ймовірність успіху. Є кілька «бандитів», і розподіл успішних важелів розраховується і відрізняється для кожного механізму. Гіттінс стверджує, що проблема полягає в тому, «який важіль обрати наступним на кожному етапі, щоб максимізувати загальну очікувану винагороду з нескінченної послідовності важелів».

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

Визначення

У прикладній математиці «індекс Гіттінса» — це дійсний скаляр, що пов'язаний зі станом випадкового процесу з функцією винагороди та ймовірністю завершення. Це показник винагороди, яку можна досягти через розвиток процесу від цього стану, при ймовірності його завершення у майбутньому. «Стратегія індексу», яка виникає з індексу Гіттінса і полягає у виборі на будь-який момент часу випадкового процесу з поточно найвищим індексом Гіттінса, є рішенням деяких проблем зупинки, таких як проблема динамічного розподілу, де той, хто приймає рішення, повинен максимізувати загальну винагороду, розподіляючи обмежену кількість зусиль на кілька конкуруючих проектів, кожен з яких повертає випадкову винагороду. Якщо проекти незалежні один від одного і тільки один проект може розвиватися в один момент часу, проблема називається багаторуким бандитом (одним з типів задач випадкового планування), і стратегія індексу Гіттінса є оптимальною. Якщо декілька проектів може розвиватися, проблема називається «невгамовний бандит», і стратегія індексу Гіттінса є відомою евристикою, але взагалі не існує оптимального розв'язку. Взагалі ця проблема є NP-повною, і вважається, що неможливо досягнути розв'язку.

Історія

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

Незабаром після першоджерельної роботи Гіттінса, Пітер Уіттлі продемонстрував, що індекс виникає як множник Лагранжа з проблеми динамічного програмування під назвою процес відставки, і припустив, що той самий індекс був би гарним евристичним підходом в більш загальній установці, яку назвали «Невгамовний бандит». Питання того, як саме обчислити індекс для ланцюгів Маркова, вперше було розглянуте Варайя та його співробітниками за допомогою алгоритму, що обчислює індекси від найбільшого до найменшого, а також Ченом і Катехакісом, які показали, що стандартне лінійне програмування можна використовувати для обчислення індексу стану, не вимагаючи його обчислення для всіх станів із вищими значеннями індексу. Л. К. М. Калленберг надав параметричну реалізацію лінійного програмування для обчислення індексів для всіх станів марковського ланцюга. Крім того, Катехакіс і Вейнотт продемонстрували, що індекс є очікуваною винагородою марковського процесу прийняття рішень, відомого як «перезапуск у стані», і може бути точно обчислений шляхом розв'язання цієї задачі алгоритмом ітерації стратегії або приблизно алгоритмом ітерації значення. Цей підхід також має перевагу обчислення індексу для конкретного стану без необхідності обчислення всіх більших індексів, і він є дійсним при більш загальних умовах простору станів. У 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$

Це спостереження приводить Соніна до висновку, що не $\nu (i)$, а $\alpha (i)$ є «справжнім значенням» індексу Гіттінса.

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

У теорії масового обслуговування індекс Гіттінса використовується для визначення оптимального планування завдань, наприклад, у черзі M/G/1. Середній час виконання завдань за графіком індексу Гіттінса можна визначити за допомогою підходу SOAP. Варто зазначити, що динаміка черги є Марковою властивістю, а випадковість виникає через процеси прибуття та обслуговування. Це відрізняється у більшості робіт навчальної літературі, де випадковість явно враховується через параметр .

Проблеми з раціональними винагородами

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

Цей клас задач відрізняється від оптимізації напівмарківського процесу винагород, яка може обирати стани з непропорційним часом перебування лише для накопичення вищої винагороди. З іншого боку, він відповідає класу задач оптимізації дробово-лінійних марківських винагород.

Однак негативним аспектом такої оптимізації співвідношення є те, що при великому співвідношенні у деякому стані оптимізація може обирати стани, які призводять до низького співвідношення через велику ймовірність завершення процесу. Це зумовлено тим, що ймовірно процес завершиться перш, ніж співвідношення значно зменшиться. Формулювання задачі запобігання такого раннього завершення полягає у визначенні оптимізації як максимізації майбутнього співвідношення, яке враховує кожний стан. Припускається, що існує індексація для цієї проблеми, яка може бути обчислена як проста варіація існуючих алгоритмів перезапуску в стані або алгоритмів видалення стану та оцінена як ефективна на практиці.

Список літератури

• Scully, Ziv and Harchol-Balter, Mor and Scheller-Wolf, Alan (2018). SOAP: One Clean Analysis of All Age-Based Scheduling Policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems. ACM. 2: 16. doi:10.1145/3179419.
• Берри, Дональд А. and Fristedt, Bert (1985). Bandit problems: Sequential allocation of experiments. Monographs on Statistics and Applied Probability. London: Chapman & Hall. ISBN 978-0-412-24810-8.
• Гіттінс, Д.Ч. (1989). Multi-armed bandit allocation indices. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. ISBN 978-0-471-92059-5.
• Вебер Р.Р. (November 1992). On the Gittins index for multiarmed bandits. The Annals of Applied Probability. 2: 1024—1033. doi:10.1214/aoap/1177005588. JSTOR 2959678.
• Катехакіс Майкл Н.; Veinott, Jr., Arthur F. (1987). The multi-armed bandit problem: decomposition and computation. Математика дослідження операцій. 12 (2): 262—268. doi:10.1287/moor.12.2.262. JSTOR 3689689.
• Cowan, W. and Катехакіс М.Н. (2014). Multi-armed Bandits under General Depreciation and Commitment. Probability in the Engineering and Informational Sciences. 29: 51—76. doi:10.1017/S0269964814000217.

Посилання

• [1] Matlab/Octave implementation of the index computation algorithms
• Cowan, Robin (1991). Tortoises and Hares: Choice Among Technologies of Unknown Merit. The Economic Journal. 101 (407): 801—814. doi:10.2307/2233856. JSTOR 2233856.