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

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

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

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

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

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

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

Визначення

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

Історія

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

Незабаром після першоджерельної роботи Гіттінса, ^[en] продемонстрував, що індекс виникає як множник Лагранжа з проблеми динамічного програмування під назвою процес відставки, і припустив, що той самий індекс був би гарним евристичним підходом в більш загальній установці, яку назвали «Невгамовний бандит». Питання того, як саме обчислити індекс для ланцюгів Маркова, вперше було розглянуте Варайя та його співробітниками за допомогою алгоритму, що обчислює індекси від найбільшого до найменшого, а також Ченом і Катехакісом, які показали, що стандартне лінійне програмування можна використовувати для обчислення індексу стану, не вимагаючи його обчислення для всіх станів із вищими значеннями індексу. Л. К. М. Калленберг надав параметричну реалізацію лінійного програмування для обчислення індексів для всіх станів марковського ланцюга. Крім того, Катехакіс і Вейнотт продемонстрували, що індекс є очікуваною винагородою марковського процесу прийняття рішень, відомого як «перезапуск у стані», і може бути точно обчислений шляхом розв'язання цієї задачі алгоритмом ітерації стратегії або приблизно алгоритмом ітерації значення. Цей підхід також має перевагу обчислення індексу для конкретного стану без необхідності обчислення всіх більших індексів, і він є дійсним при більш загальних умовах простору станів. У 2004 році Сонін отримав швидший алгоритм для обчислення всіх індексів як наслідок його алгоритму елімінації для оптимальної зупинки ланцюга Маркова. У цьому алгоритмі ймовірність припинення процесу може залежати від поточного стану, а не бути фіксованим фактором. Більш швидкий алгоритм був запропонований у 2007 році Ніно-Мора, який використовував структуру параметричного симплексу для зменшення обчислювальних зусиль опорних кроків, досягаючи такої ж складності, як алгоритм виключення Гауса. У 2014 році Коуен, В. і Катехакіс надають розв'язок проблеми з можливо немарковими, нескінченними процесами винагороди з простором станів під каркасами, в яких або коефіцієнти зниження можуть бути неоднорідними та змінюватися з часом, або періоди активації кожного бандита можуть бути не фіксованими або рівномірними, але піддаються можливо випадковій тривалості активації, перш ніж дозволяється зміна на іншого бандита. Розв'язок ґрунтується на узагальнених індексах перезапусків у станах.

Математичне визначення

Індекс динамічного розподілу

Класичне визначення Гіттінса та ін. це:

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

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

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

де ${\displaystyle \chi }$ — це область визначення X .

Формулювання процесу відставки

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

${\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).}$

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

Коли ${\displaystyle Z(\cdot )}$ — це ланцюг Маркова з винагородами, тоді інтерпретація ^[en] та Вейнота (1987) пов'язує з кожним станом ланцюга дію перезапуску з довільного стану ${\displaystyle i}$, що будує марковський процес прийняття рішень ${\displaystyle M_{i}}$.

Індекс Гіттінса цього стану ${\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)}$ .

Узагальнений індекс

Якщо ймовірність не припинення ${\displaystyle \beta (i)}$ залежить від стану ${\displaystyle i}$, то узагальнення, що введене Соніним (2008), визначає індекс Гіттінса ${\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 \nu (i)}$, а ${\displaystyle \alpha (i)}$ є «справжнім значенням» індексу Гіттінса.

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

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

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

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

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

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

Примітки

1. Cowan, Robin (July 1991). Tortoises and Hares: Choice among technologies of unknown merit. The Economic Journal. 101 (407): 801—814. doi:10.2307/2233856. JSTOR 2233856.
2. Gittins, J. C. (1979). Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society. Series B (Methodological). 41 (2): 148—177. doi:10.1111/j.2517-6161.1979.tb01068.x. JSTOR 2985029. S2CID 17724147.
3. Mitten L (1960). An Analytic Solution to the Least Cost Testing Sequence Problem. Journal of Industrial Engineering. 11 (1): 17.
4. Gittins, J. C.; Jones, D. M. (1979). A Dynamic Allocation Index for the Discounted Multiarmed Bandit Problem. Biometrika. 66 (3): 561—565. doi:10.2307/2335176. JSTOR 2335176.
5. Weitzman, Martin L. (1979). Optimal Search for the Best Alternative. Econometrica. 47 (3): 641—654. doi:10.2307/1910412. JSTOR 1910412. S2CID 32530881. {{}}: |hdl-access= вимагає |hdl= ()
6. Whittle, Peter (1980). Multi-armed Bandits and the Gittins Index. ^[en]. 42 (2): 143—149.
7. Varaiya, P.; Walrand, J.; Buyukkoc, C. (May 1985). Extensions of the multiarmed bandit problem: The discounted case. IEEE Transactions on Automatic Control. 30 (5): 426—439. doi:10.1109/TAC.1985.1103989.
8. Chen, Yih Ren; Katehakis, Michael N. (1986). Linear programming for finite state multi-armed bandit problems. ^[en]. 11 (1): 180—183. doi:10.1287/moor.11.1.180.
9. Kallenberg, Lodewijk C. M. (1986). A Note on M. N. Katehakis' and Y.-R. Chen's Computation of the Gittins Index. ^[en]. 11 (1): 184—186. doi:10.1287/moor.11.1.184.
10. Katehakis, Michael N.; Veinott, Jr., Arthur F. (1987). The multi-armed bandit problem: decomposition and computation. ^[en]. 12 (2): 262—268. doi:10.1287/moor.12.2.262. JSTOR 3689689. S2CID 656323.
11. Sonin I (2008). A generalized Gittins index for a Markov chain and its recursive calculation. Statistics and Probability Letters. 78 (12): 1526—1533. doi:10.1016/j.spl.2008.01.049.
12. Ni , Mora J (2007). A (2/3)^n Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain. INFORMS Journal on Computing. 19 (4): 596—606. doi:10.1287/ijoc.1060.0206. S2CID 122785013.
13. Cowan, Wesley; Katehakis, Michael N. (January 2015). Multi-armed bandits under general depreciation and commitment. Probability in the Engineering and Informational Sciences. 29 (1): 51—76. doi:10.1017/S0269964814000217.
14. 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 (1): 16. doi:10.1145/3179419. S2CID 216145213.
15. Di Gregorio, Lorenzo and Frascolla, Valerio (1 жовтня 2019). Handover Optimality in Heterogeneous Networks. 5G World Forum. arXiv:1908.09991v2.

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

• 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.
• ^[en] and Fristedt, Bert (1985). Bandit problems: Sequential allocation of experiments. Monographs on Statistics and Applied Probability. London: Chapman & Hall. ISBN .
• ^[en] (1989). Multi-armed bandit allocation indices. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. ISBN .
• ^[en] (November 1992). On the Gittins index for multiarmed bandits. The Annals of Applied Probability. 2: 1024—1033. doi:10.1214/aoap/1177005588. JSTOR 2959678.
• ^[en]; Veinott, Jr., Arthur F. (1987). The multi-armed bandit problem: decomposition and computation. ^[en]. 12 (2): 262—268. doi:10.1287/moor.12.2.262. JSTOR 3689689.
• Cowan, W. and ^[en] (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.