Минимаксное управление со средневзвешенным горизонтом в бинарной случайной среде Текст научной статьи по специальности «Математика»

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

MINIMAX CONTROL WITH WEIGHTED AVERAGE HORIZON IN A BINARY RANDOM ENVIRONMENT

We propose an algorithm of finding the minimax risk and minimax strategy in a binary stationary random environment. The algorithm is reduced to searching the global maximum of the function being equal to the value of minimax risk for the environment described by some finite subset of the initial parameter set.

Текст научной работы на тему «Минимаксное управление со средневзвешенным горизонтом в бинарной случайной среде»

МИНИМАКСНОЕ УПРАВЛЕНИЕ СО СРЕДНЕВЗВЕШЕННЫМ ГОРИЗОНТОМ В БИНАРНОЙ СЛУЧАЙНОЙ СРЕДЕ

MINIMAX CONTROL WITH WEIGHTED AVERAGE HORIZON IN A BINARY RANDOM ENVIRONMENT

Институт электронных и информационных систем НовГУ, Alexander.Kolnogorov@novsu.ru

Keywords: control in random environment, two-armed bandit problem, minimax approach

Рассматривается задача о целесообразном поведении в стационарной случайной среде [1,2], известная также как задача адаптивного управления (адаптивного выбора вариантов) [3,4] и задача о двуруком бандите [5-7]. В статье развиваются исследования по нахождению минимаксного управления, начатые в [8-10].

Бинарная стационарная случайная среда — это управляемый случайный процесс / = 1,2. значения которого интерпретируются как доходы и зависят только от текущих выбираемых действий следующим образом: Рг& = 1|>>, = £> = ре, Рг& = 0| ^ = £> = qe, £ = 1. К (К>2). Математическое ожидание одноша-гового дохода за выбор £ -го действия в этом случае, очевидно, равно w£ = 1 • р£ + 0 • q£ = р£.

Таким образом, процесс полностью описывается векторным параметром 6 = (р1. рК), который

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

Стратегия ст описывается набором вероятностей, Рг^(У4;^1), £=1. К, определяющих выбор действия у в зависимости от известной предыстории — примененных действий = У\. У^\ и полученных в ответ на них доходов =§1,.",§м. Обозначим через м>* = тах(м>х. м>К) максимальную величину математического ожидания одношагового дохода. Если бы параметр управления 6 был известен, то оптимальная стратегия предписывала бы всегда применять действие, которому соответствует наибольший ожидаемый доход V*, при

этом полный доход на горизонте управления длины T был бы равен Tw*. Поскольку вместо этого применяется стратегия ст, то величина

Lt (ст, 9) = Tw* - Ест,Ъ| (1)

характеризует функцию потерь дохода на горизонте управления T относительно его максимально возможного значения вследствие неполноты информации. Здесь через Ест,е обозначен знак математического ожидания по мере, порожденной стратегией ст и параметром 9. Рассмотрим множество горизонтов управления = и обозначим через

L(CT,9,) = ]Г PiLr (ст,9) (2)

функцию потерь на этом множестве горизонтов

управления. Здесь ^р. =1, р. > 0, i = 1. I. Коэффи-

циент р. характеризует вклад L-. (ст, 9) в общую

функцию потерь. Эти коэффициенты, вообще говоря, произвольны, но их выбор может быть обоснован в каждом конкретном случае. Например, предположим, что все T одинаково важны. Так как большим значениям T соответствуют большие потери, соответствующий коэффициент р. в этом случае естественно выбирать меньше, так, чтобы примерно одинаковыми оказались величины max PL (ст, 9).

RM (0,) = inf sup L(^ 9,) (3)

минимаксный риск, определенный на множестве параметров 0 и горизонтов управления , через

0м (0,) — соответствующую минимаксную стратегию. Целью статьи является описание алгоритма нахождения указанных минимаксных риска и стратегии.

Ранее задача рассматривалась в [8-10] в случае, если значение горизонта управления T фиксировано и известно. В этом случае предложена методика поиска минимаксных стратегии и риска для любого множества параметров 0. В данной статье показано, что результаты [8-10] полностью переносятся на рассматриваемый случай неопределенного горизонта управления, если ввести подходящее дисконтирование доходов. Формулировка полученных результатов приведена в разделе 2. В разделе 3 рассмотрены численные примеры. В заключении проводится обсуждение результатов.

2. Нахождение минимаксных стратегии и риска

Для t, удовлетворяющего условию T—1 < t < T,

положим yt = ^рj. Из (1), (2) следует равенство

т.е. L(a,9,) может рассматриваться как функция потерь с дисконтированными доходами. Поэтому в данном случае справедливы результаты, аналогичные полученным в [8-10]. Приведем эти результаты без доказательства.

Для конечного множества параметров определим минимаксный риск

RM (eb. em;) = min max Lt (a, 9 ;;),

соответствующую минимаксную стратегию обозначим через aM (9b. 9m;). Положим T = max T.

Через n(K,T) обозначим число независимых компонент стратегии (см. [8-10]).

Теорема 1. Минимаксная стратегия aM (©;) совпадает с некоторой минимаксной стратегией a(e°. e°;) на конечном множестве параметров. На этом множестве параметров минимаксный риск достигает своего максимального значения, т.е.

RM(9ь. 9П;Ш) = max RM(^. Д,,;®),

а для числа n справедлива оценка n < n(K, T) +1.

Байесовский риск на конечном множестве параметров 9j. 9m для априорного распределения ХЬ. Хm на нем определяется формулой

соответствующую байесовскую стратегию обозначим aB(91. 9m;X1. Xm;). Эта стратегия может быть вычислена при помощи простого алгоритма динамического программирования, при этом часть вероятностей однозначно определяются равными 0 или 1, а остальные могут выбираться произвольно (см., напр., [6-7]).

Теорема 2. Минимаксный риск и минимаксная стратегия на конечном множестве параметров (9b. 9m) совпадают с байесовским риском и байесовской стратегией для наихудшего априорного распределения на этом множестве, т.е. выполняется равенство

RM (91. 9m;) = RB (9b. 9m; A. A;) = = max RB(91. 9m;X1. Xm;).

Таким образом, поиск минимаксного риска (3) на произвольном замкнутом множестве параметров © может быть сведен к поиску глобального экстремума функции не более чем n(K,T)+1 переменных, т.е.

где m < n(K, T) +1, причем для любого фиксированного набора 9j. 9m функция выпукла вверх по переменным Xj. Xm. Вероятности, которые при вычислении байесовской стратегии определяются произвольно, должны быть доопределены из системы уравнений

L(aM, 9 /;) = RB (901. e0n; X01. X0n;), j = 1. n, которая сводится к линейной.

3. Численные примеры

Рассмотрим множество параметров ©=, т.е. известна максимальная вероятность единичного дохода, равная р = 0,7; вторая вероятность единичного дохода может быть произвольным числом, не превосходящим р. Множество горизонтов управления имеет

вид =. Дисконтирующие множители такие: рг = ¿ТТ172, I = 1,2, где г = (ГГ1/2 + Т2"1/2)_1, т.е. Р] +р2 =1. В этом случае расчеты дают, что множество параметров, на которых функция потерь достигает максимума, равно двум, а сами параметры

следующие: 6° = (р1, р), 62 = (р,р

📎📎📎📎📎📎📎📎📎📎

Минимаксное управление со средневзвешенным горизонтом в бинарной случайной среде Текст научной статьи по специальности «Математика»

Похожие темы научных работ по математике , автор научной работы — Колногоров А.В.

MINIMAX CONTROL WITH WEIGHTED AVERAGE HORIZON IN A BINARY RANDOM ENVIRONMENT

Текст научной работы на тему «Минимаксное управление со средневзвешенным горизонтом в бинарной случайной среде»