Аналiз стратегiй послiдовного розподiлу ресурсiв у стохастичному середовищi

Дисертацiйне дослiдження присвячене вивченню асимптотичних вла- стивостей стратегiй послiдовного розподiлу ресурсiв у стохастичному середовищi зi спостереженнями, якi мають бета-розподiл. Розглядається середовище, яке представлене моделлю стохастичного багаторукого бандита. Головною метою роботи є здiйснення асимптотичного аналiзу стратегiй та розробка алгоритмiв їх застосування. Також вивчається вплив додаткової iнформацiї на ефективнiсть стратегiй.
Розглядається задача послiдовного прийняття рiшення в умовах невизначеностi у контекстi взаємодiї мiж суб’єктом, що приймає рiшення, так званим агентом, i зовнiшнiм середовищем. Ця взаємодiя вiдбувається протягом скiнченого горизонту. На кожному кроцi агент обирає дiю iз заданої множини та у вiдповiдь отримує винагороду вiд середовища. Метою агента є послiдовний вибiр таких дiй, якi призводять до найбiльшої можливої сукупної винагороди за весь горизонт. Основним ускладненням в цiй задачi є те, що параметри процесу винагороди не вiдомi заздалегiдь.
У наведеному оглядi лiтератури бiльшiсть результатiв, опублiкованих до цього часу робiт за даною темою, зосередженi на аналiзi середовищазi спостереженнями, якi мають розподiл Бернуллi чи нормальний. Варто звернути увагу, що бета-розподiл є бiльш вiдповiдним вiдображенням випадкової поведiнки вiдсоткiв i пропорцiй, тож може бути бiльш корисним у моделюваннi клiнiчних випробувань, в системах маршрутизацiї мережi тощо. Отже, в нашiй роботi розглядається стохастичне середовище зi спостереженнями, якi мають бета-розподiл. Для аналiзу оцiнок ефективностi стратегiй використовуються оцiнки хвостiв субгауссових випадкових величин та їх властивостi.
Були розглянутi стратегiя на базi надiйного iнтервалу, баєсова та жадiбна стратегiї. Адаптовано алгоритми для цих стратегiй та отримано асимптотичнi оцiнки очiкуваних сукупних втрат для кожної з них. Наведено асимптотичний аналiз баєсової стратегiї у стохастичному середовищi з додатковою iнформацiєю та побудовано новий алгоритм з використанням зваження вибiрки для зменшення шуму. Проведено математичне моделювання запропонованих у роботi алгоритмiв стратегiй у стохастичному середовищi з рiзними параметрами розподiлiв та кiлькiстю дiй. Одержанi чисельнi результати показали,щостратегiї є асимптотично оптимальними згiдно з отриманими оцiнками верхнiх границь втрат.
Результати проведеної роботи мають теоретичне значення та можливiсть практичного застосування. Отриманi рiшення дозволяють будувати оцiнки ефективностi стратегiї у середовищi з бета-розподiлом, яке представлене моделлю стохастичного багаторукого бандита. Подiбнi моделi мають великий потенцiал використання в адаптивнiй маршрутизацiї для мiнiмiзацiї затримок у мережi, динамiчному цiноутвореннi, клiнiчних випробуваннях тощо.

Ключовi слова: послiдовний розподiл ресурсiв, теорiя прийняття рiшень, стацiонарний розподiл, асимптотична оптимальнiсть, надiйний iнтервал, оптимальне керування, марковськi процеси прийняття рiшень.

The focus of this dissertation study lies in the asymptotic analysis of policies within the context of sequential resource allocation tasks in a stochastic environment. This environment is characterized by a collection of beta distributions with unknown parameters, resembling a stochastic multi-armed bandit model. The central aim of this study is twofold: firstly, to conduct an asymptotic analysis of policies and adapt algorithms tailored to the specific environment; and secondly, to explore the impact of contextual information on the effectiveness of these strategies.
The problem at hand pertains to decision-making under uncertainty, involving a sequential interaction between a decision-maker (referred to as the agent) and the stochastic environment. This interaction unfolds over a finite time horizon. At each step, the agent selects an action from a predefined set and, in return, receives a reward from the environment. The agent’s objective is to consistently select actions that maximize the cumulative reward over the entire horizon. The primary challenge in this task is the lack of prior knowledge regarding the parameters governing the reward process.
It’s noteworthy that most existing literature on this topic has predominantly focused on analyzing environments with observations following Bernoulli or normal distributions. Nevertheless, the beta distribution offers a more suitable representation for modeling random behavior related to percentages and proportions, making it especially relevant for applications such as clinical trial simulations and network routing systems. Therefore, our work delves into a stochastic environment where observations follow a beta distribution. To assess the efficiency of these strategies, we employ estimates of the tails of sub-Gaussian random variables and their associated properties.
The strategies under consideration encompass those based on confidence intervals, Bayesian methods, and greedy approaches. We adapt algorithms tailored to these strategies and derive asymptotic estimates of regrets. Mathematical modeling of these strategy algorithms is conducted within a stochastic environment featuring various distribution parameters and action counts. Our numerical results affirm that these strategies are asymptotically optimal, as substantiated by the upper bounds estimates.
The outcomes of this work hold both theoretical significance and practical applicability. The obtained estimates facilitate evaluations of strategy effectiveness in an environment characterized by a beta distribution, as exemplified by the stochastic multi-armed bandit model. Such models exhibit great potential in diverse applications, including adaptive routing to minimize network delays, dynamic pricing, and clinical trials, among others.

Key words: sequential resource allocation, decision-making theory, stationary distribution, asymptotic optimality, confidence interval, optimal control, Markov process.

Джога А. С. Аналiз стратегiй послiдовного розподiлу ресурсiв у стохастичному середовищi : дис. д-ра філос. : 124 Системний аналiз / Джога Андрiй Сергiйович. - Київ, 2023. - 131 с.