§ 14.7. Задачи о «двуруком бандите» в случае зависимых параметров

Материал настоящего параграфа основан на работе Фельдмана (1962). Мы снова предположим, что как X, так и У имеют распределения Бернулли и их при заданных значениях имеют вид (2) § 14.6. Пусть, далее, фиксированные числа, причем и пусть либо либо Таким образом, в этой задаче параметры высшей степени зависимы. Параметрический вектор может принимать только два значения: и Поэтому распределение может быть охарактеризовано единственным числом

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

Для каждой последовательной процедуры обозначим через общее число наблюдений, проводимых над случайной величиной которая принимает значение 1 с вероятностью а. Статистик точно не знает, что это за случайная величина, X или У.

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

Лемма 1. Последовательная процедура максимизирует тогда и только тогда, когда она минимизирует

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

Так как все математические ожидания в соотношении (1) вычисляются при заданных значениях то окончательный результат можно записать в виде

В рассматриваемом нами случае для любой априорной вероятности имеет место следующая цепочка равенств:

Так как то из (3) видно, что процедура максимизирует тогда и только тогда, когда она минимизирует

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

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

первое наблюдение делается над У, второе над X и затем в течение оставшихся наблюдений проводится оптимальная процедура. Обозначим через средние числа ошибок для этих процедур.

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

Лемма 2. При имеем

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

Лемма 3. Для каждогд фиксированного значения из интервала вероятности являются неубывающими функциями от

Доказательство. Пусть Тогда справедлива формула

Далее,

Таким образом, для всякого значения

Правая часть формулы (6) является неубывающей функцией от .

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

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

Теорема 1. Пусть процедура, согласно которой на произвольном шаге наблюдение надо проводить над X, если и над У, если Тогда оптимальная последовательная процедура.

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

Тогда, так как первое наблюдение при оптимальной процедуре проводится либо над X, либо над У, имеем

Положим

Для доказательства того, что оптимальная процедура, достаточно показать, что при при Из симметрии задачи ясно, что Поэтому теорема будет доказана, если мы покажем, что неубывающая функция от для любого фиксированного значения Это утверждение мы установим методом индукции. Так как то

является неубывающей функцией. Предположим теперь, что функции не убывают при и покажем, что тогда и функция не убывает. Рассмотрим процедуры и введенные выше. В силу предположения индукции оптимальная процедура, если число оставшихся наблюдений не превосходит k. Следовательно, после первых двух

наблюдений процедура является оптимальным продолжением на оставшихся шагах. Положим

Из леммы 2 и соотношения (8) видно, что

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

Если аналогичным образом определить случайную величину получим

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

С другой стороны, если то на втором шаге процедура предписывает наблюдать У, в то время как процедура требует проведения наблюдения над X, ибо при последних к наблюдениях надо использовать оптимальный вариант, который по предположению индукции совпадает с Итак, если то

Если же то имеем

Аналогично можно показать, что если первое наблюдение проводится над то

если же

Согласно предположению индукции, функция не убывает Следовательно, из (13) и (14) вытекает, что — невозрастающая функция от а из (15) и (16) что — неубывающая функция от

Пусть Тогда ввиду (11)

Поскольку невозрастающая функция от то из соотношения (17) и леммы 3 вытекает, что невозрастающая функция от [см., например, Леман (1959), стр. 107—108 и 159]. Аналогично из соотношения (12) и леммы 3 следует, что неубывающая функция от ф. Сопоставляя эти утверждения с равенством (10), видим, что является неубывающей функцией от

Рассуждения, с помощью которых была доказана последняя теорема, можно применить и в следующем более общем случае. Предположим, что (не обязательно бернуллиевские) случайные величины с о. в. п. и Пусть две заданные о. в. причем либо либо Допустим, что на каждом из шагов наблюдение может проводиться либо над X, либо над У. Всякий раз, когда наблюдение проводится над случайной величиной с о. в. п. , считается, что статистик допустил ошибку. Задачей статистика является определение процедуры, минимизирующей среднее число ошибок. Пусть

Тогда оптимальная процедура снова предписывает проводить первое наблюдение над X, если и над У, если

Дальнейшие замечания и ссылки на литературу. В качестве основвих ссылок по материалу § 14.5 — 14.7 следует указать работу Брэдта, Джонсона и Карлина (1956) и уже упоминавшуюся работу Фельдмана (1962). Одним из первых авторов,

рассматривавших такие задачи, был Томпсон (1933). Дальнейшие исследования в этой области были стимулированы статьями Роббинса (1952, 1956а). Вот некоторые другие публикации: Беллман (1956), Исбелл (1959), Вогел (1960а, b), Фурукава (1964), Мэллоус и Роббинс (1964), Браун (1965). Обзорное изложение задач о «двуруком бандите» имеется в работе Куизела (1965).

Задача о «двуруком бандите» очевидным образом обобщается на случай «двурукого бандита» . С другой стороны, имеется ряд задач об оптимальной остановке, которые называют задачами об «одноруком бандите» [см. Чернов (1967b)].