«В.В.Вьюгин ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ТЕОРИИ МАШИННОГО ОБУЧЕНИЯ Допущено Учебно-методическим объединением высших учебных заведений Российской Федерации по образованию в области прикладных математики и физики в качестве ...»

Обозначим 1i = (0,..., 1,..., 0) – чистую стратегию, которая представляет собой распределение вероятностей на множестве X, сосредоточенное на i X (вектор длины N, у которого i-я координата равна 1, остальные координаты равны 0). Аналогичным образом рассматриваются чистые стратегии на Y. Заметим, что f (1i, 1j ) = f (i, j) = ai,j.

Теорема 7.4. Для того чтобы пара смешанных стратегий (, q ) была решением (седловой точкой) смешанного расширения матричной игры (X, Y, f ), необходимо и достаточно, чтобы выполнялось неравенство Доказательство. Необходимость следует из теоремы 7.1. Для доказательства достаточности заметим, что каждая смешанная стратегия p = (p1,..., pN ) матричной игры является линейной комбинацией чистых стратегий p = представляется смешанная стратегия q = но рассмотреть дважды линейную комбинацию неравенства (7.9).

Получим для всех p и q. Отсюда получаем условие седловой точки:

для любых p и q.

Теорема 7.5. Для смешанного расширения произвольной матричной игры справедливы соотношения Доказательство. Очевидно, что Противоположное неравенство следует из неравенства которое имеет место для любого q. Это неравенство означает, что минимум взвешенной линейной комбинации достигается, когда весь вес сосредоточен на наименьшем элементе. Следовательно, Второе неравенство доказывается аналогичным образом.

Из этой теоремы получаем Следствие 7.1. В смешанном расширении произвольной матричной игры выполнено равенство где v – значение игры.

Найдем решение игры в орлянку в смешанных стратегиях.

Матрица выплат этой игры типа (2 2) имеет вид Смешанные стратегии этой игры: p = (p, 1 p) и q = (q, 1 q), а среднее значение выигрыша имеет вид Среднее выигрыша:

представляет собой уравнение однополостного гиперболоида.

Пусть По следствию 7.1 решение игры достигается в точке p, на которой v(p) достигает своего максимума – это p = 1. Аналогичные рассуждения показывают, что q = 1. Значение игры: v = f (, q ) = 0. Точка (p, q ) является седловой точкой однополостного гиперболоида (7.10).

7.3.3. Решение матричной игры типа (2 M ) Для нахождения решений в смешанных расширениях матричных игр (2 M ) (или (N 2)) можно использовать геометрическое представление стратегий. Согласно следствию 7.1 значение такой игры равно Здесь первый игрок выбирает смешанную стратегию – распределение вероятностей p = (p, 1 p) на строках матрицы, а второй игрок выбирает чистую стратегию – столбец j матрицы.

Значит, для нахождения значения игры и ее решения для первого игрока надо просто найти значение p = p, при котором функция достигает своего максимального значения p на отрезке [0, 1]. Это значение v(p ) и будет значением игры.

Для нахождения решения строим все M прямых вида Для каждого p [0, 1] проводим вертикальную прямую до пересечения с прямой с наименьшим значением ординаты. Точки пересечения образуют ломаную линию y = v(p) – нижнюю огибающую для всех этих прямых. Верхняя точка нижней огибающей определяет оптимальную стратегию первого игрока (ее абсцисса p ) и значение игры (ордината точки v(p )).

Задача. Найти решение смешанного расширения матричной игры:

Строим все прямые вида Lj (p) = a1,j p + a2,j (1 p) при j = Строим нижнюю огибающую. Точка p является точкой пересечения прямой 4 и прямой 5, т.е. решаем уравнение p = p + 5(1 p).

Получаем: p = 5/7, v(p ) = 5/7.

Для нахождения оптимальной стратегии второго игрока используем следующую теорему.

Теорема 7.6. Пусть (, q ) – решение матричной игры в смеp шанных стратегиях, v Доказательство. Докажем первое утверждение. По определению f (1i, q ) v, i = 1,..., N.

Допустим, что существует i0 такое, что p0 > 0 и одновременi но f (1i0, q ) < v. Рассмотрим линейную комбинацию неравенств f (1i, q ) v с коэффициентами p, i = 1,..., N, и, так как одно из складываемых неравенств является строгим, получим Это противоречие доказывает первое утверждение.

Второе утверждение доказываем аналогично.

Следствие 7.2. Пусть (, q ) – решение матричной игры в смеp шанных стратегиях, v – значение игры. Тогда Условие f (, 1j ) = pa1,j +(1p)a2,j > v означает, что соответствующая прямая в точке p проходит выше точки пересечения (двух) прямых, на которых достигается значение игры.

Завершим решение задачи – найдем оптимальную стратегию второго игрока.

Для 1-й, 2-й, 3-й, 6-й чистых стратегий второго игрока (т.е.

соответствующих прямых) выполняется неравенство при j = 1, 2, 3, 6.

По следствию 7.2 для оптимальной стратегии будет q1 = 0, q2 = 0, q3 = 0, q6 = 0, q4 = q, q5 = 1 q.

Пусть теперь первый игрок выбирает чистую стратегию на строках – одну из строк i = 1, 2. Второй игрок выбирает смешанную стратегию q = (0, 0, 0, q4, 1 q4, 0) на столбцах. Тогда v = min max (ai,4 q + ai,5 (1 q)) = max (ai,4 q4 + ai,5 (1 q4 )).

Для j = 4, 5 получаем: q4 (1q4 ) = 5/7 и 5(1q4 ) = 5/7. Отсюда Полное решение игры имеет вид 7.3.4. Решение игры типа (N M ) В общем случае рассматривается матричная игра с матрицей A = (ai,j ), где i = 1,..., N, j = 1,..., M. Без ограничения общности можно считать, что все элементы матрицы A строго положительны; поэтому значение v игры в смешанных стратегиях также строго положительно. По следствию 7.1 в смешанном расширении произвольной матричной игры выполнено равенство где v – значение игры. Поэтому существует смешанная стратеp гия p = (p1,..., pN ) первого игрока, такая, что f (, 1j ) v для любой чистой стратегии 1j второго игрока. Иными словами, выполняются условия Введем обозначения xi = pi /v, i = 1,..., M. Тогда эти условия превращаются в соотношения Для того чтобы этого добиться, достаточно прибавить некоторую достаточно большую положительную константу к каждому элементу платежной матрицы игры.

Задача поиска решения в матричной игре сводится к задаче линейного программирования: найти x1,..., xN такие, что при условиях По (7.11) существует смешанная стратегия q = (q1,..., qN ) гии 1i первого игрока. Иными словами, выполняются условия Введем обозначения: xj = qj /v, j = 1,..., M. Тогда эти условия превращаются в соотношения Задача поиска решения в матричной игре сводится к задаче линейного программирования: найти x1,..., xM такие, что при условиях Это – задача линейного программирования, двойственная к прямой задаче для переменных xi, i = 1,..., N.

7.3.5. Конечная игра между K игроками В общем случае конечная игра между K игроками в нормальной форме определяется следующим образом. Игрок k {1,..., K} имеет Nk возможных стратегий (ходов или чистых стратегий).

Пусть = (i1,..., iK ) – некоторый набор стратегий всех K игроi Тогда выигрыш k-го игрока обозначается f k ( = f k (i1,..., iK ) (в другой постановке его потери равны – f k ( i)).

Смешанная стратегия k-го игрока – это распределение вероятностей pk = (pk,..., pk k ) на множестве всех его стратегий {1,..., Nk }. Здесь pk – вероятность выбора игроком стратегии Пусть I k – случайная величина, принимающая значение i {1,..., Nk } с вероятностью pk. i Пусть I = (I 1,..., I K ) – векторная случайная величина, представляющая набор стратегий всех игроков. Значениями такой случайной величины являются векторы = (i1,..., iK ), где Обычно предполагается, что случайные величины I 1,..., I K независимы. На множестве векторов I рассматривается вероятpK, которая определяет вероятность элементарного исхода = (i1,..., iK ), равную произведению веi роятностей исходов:

Математическое ожидание выигрыша k-го игрока равно Равновесие Нэша Набор смешанных стратегий всех K игроков называется равновесием Нэша, если для любого k = 1,..., K и любой смешанной стратегии p k будет где стратегия получена из стратегии заменой вероятностного распределения k-го игрока pk на другое распределение p k.

Можно сказать, что если – равновесие Нэша, то никакому игроку не выгодно изменять свою стратегию, если другие игроки не меняют свои стратегии.

Минимаксная теорема Дж. фон Неймана является частным случаем утверждения о существованиии равновесия Нэша для случая игры с нулевой суммой для двух игроков. В этом случае функции выигрышей игроков равны f 1 (i, j) = f (i, j) и f 2 (i, j) = f (i, j), где f (i, j) – функция выигрыша в игре двух лиц с нулевой суммой.

В частности, седловая точка (0, q 0 ) в игре двух лиц в смешанp ных стратегиях с нулевой суммой является равновесием Нэша, так как для любых смешанных стратегий p и q выполнено где f (, q ) – математическое ожидание выигрыша первого игрока, (, q ) – математическое ожидание выигрыша второго игрока.

В случае игры двух лиц с нулевой суммой множество всех равновесий Нэша описано в следующем утверждении.

Предложение 7.1. Пара (, q ) является точкой равновесия Нэша в игре двух лий с нулевой суммой тогда и только тогда, когда Для любой такой пары (, q ) выполнено f (, q ) = v, где v – цена игры.

Доказательство предложения 7.1 предоставляется читателю в виде задачи.

В общем случае конечной игры K игроков имеет место следующая основная теорема.

Теорема 7.7. Каждая конечная игра имеет по крайней мере одно равновесие Нэша.

Доказательство этой теоремы основано на использовании теоремы Брауэра о неподвижной точке.

Приведем примеры игр и равновесий Нэша. Рассмотрим игры двух игроков, каждый из которых имеет две стратегии.

Пример 1. Первая игра – ранее рассмотренная игра в орлянку, в которой первый игрок загадывает число 0 или 1, а второй отгадывает, с матрицей выплат Эта игра с нулевой суммой не имеет седловой точки, но имеет решение в смешанных стратегиях: для первого и второго игрока соответствующие смешанные стратегии имеют вид p = ( 2, 1 ) и q = ( 2, 1 ). Это решение и является единственным равновесием Нэша в этой игре.

Мы перепишем матрицу выплат этой игры в виде таблицы более общего вида:

Пример 2. Два игрока решают идти на концерт слушать Баха или идти на концерт слушать Пендерецкого. Один предпочитает слушать Баха, а другой Пендерецкого. При этом, оба они предпочитают идти вместе на один концерт, чем каждому на свой концерт. Таблица предпочтений имеет вид:

Имеется два равновесия Нэша в чистых стратегиях в этой игре (Б,Б) и (П,П).

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

В этой игре имеется только одно равновесие Нэша. Это чистая стратегия (T, T ) (доказательство в виде задачи).

Коррелированное равновесие Обобщением равновесия Нэша является коррелированное равновесие Аумана. Распределение вероятностей P на множестве всех возможных наборов = (i1,..., iK ), составленных из всевозi можных стратегий всех K игроков, называется коррелированным равновесием, если для всех k = 1,..., K и для любой функции где вектор = (i1,..., iK ) распределен в соответствии с вероятi ностным распределением P, а также В отличие от равновесия Нэша величины ik более не считаются независимыми, а вероятностная мера P не является произведением мер – смешанных стратегий игроков.

Следующая лемма дает эквивалентное описание коррелированного равновесия в геометрических терминах.

Лемма 7.2. Распределение вероятностей P на множестве последовательностей стратегий типа = (i1,..., iK ) являi ется коррелированным равновесием тогда и только тогда, когда для каждого игрока k {1,..., K} и любых стратегий j, j {1,..., Nk } выполнено Условие (7.13) можно записать также в виде:

где E – условное математическое ожидание относительно распределения P. Доказательство. Условие (7.12) коррелированного равновесия эквивалентно совокупности условий:

Часто именно это условие удобно принять в качестве определения коррелированного равновесия.

где k {1,..., K} и h – произвольная функция типа Для произвольных j, j {1,..., Nk } рассмотрим функцию h, такую, что h(j) = j и h(ik ) = ik для всех ik = j. Тогда в сумме (7.15) останутся только слагаемые, соответствующие наборам в которых ik = j, а в остальных слагаемых соответствующие разности сократятся. Таким образом, сумма (7.15) превратится в сумму (7.13).

В обратную сторону, утверждение тривиально.

Пусть P – некоторое распределение вероятностей на множестве K {1,..., Nk } и a Ak для некоторого 1 k K.

Обозначим посредством Pi (·|ik = a) соответствующее условное распределение на множестве K s=1,s=k {1,..., Ns } произвольных наборов k из этого множества при известном ik = a. Введем также обозначение – математическое ожидание функции выигрыша, в которой ik = a, относительно этого условного распределения. Будем также писать более компактно:

имея ввиду, что Pk есть распределение на k, порожденное расi пределением P при условии ik = a.

Теперь можно записать условие (7.13) коррелированного равновесия в эквивалентной форме:

Следствие 7.3. Распределение вероятностей P на множестве k=1 {1,..., Nk } последовательностей стратегий типа i = (i1,..., iK ) является коррелированным равновесием тогда и только тогда, когда для каждого игрока k {1,..., K} и любых стратегии j, j {1,..., Nk } выполнено Каждое условие типа (7.13) задает замкнутую полуплоскость, поэтому множество всех коррелированных равновесий представляет собой замкнутый выпуклый многогранник в пространстве всех мер на множестве K {1,..., Nk }.

Существование равновесия Нэша в любой конечной игре означает, что коррелированное равновесие существует. Множество всех коррелированных равновесий более обширное и имеет более простое описание, чем множество всех равновесий Нэша.

7.4. Задачи и упражнения 1. Доказать, что в смешанном расширении произвольной матричной игры произвольная максиминная (минимаксная) стратегия одного игрока достигается при чистой стратегии другого игрока:

где (, q ) – решение игры (седловая точка).

2. Доказать предложение 7.1.

3. Доказать, что в игре из Примера 2 (раздел (7.3.5)) имеется также равновесие Нэша в смешанных стратегиях: первый игрок выбирает Б с вероятностью 3 и П с вероятностью 1 ; второй игрок выбирает Б с вероятностью 1 и П – с вероятностью 3.

Имеются ли другие равновесия Нэша в этой игре?

4. Доказать, что в игре из Примера 3 (раздел (7.3.5)) имеется только одно равновесие Нэша. Это чистая стратегия (T, T ).

5. Показать, что произвольная выпуклая комбинация равновесий Нэша является коррелированным равновесием.

Глава Теоретико-игровая интерпретация теории вероятностей В этой главе мы рассмотрим новый теоретико-игровой подход к теории вероятностей, предложенный Вовком и Шейфером [24].

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

Игровая интерпретация теории вероятностей из книги [24] будет продемонстрирована в разделе 8.1 на примере закона больших чисел.

В рамках этого подхода также наиболее естественным образом формулируется задача построения универсальных предсказаний, рассмотренная в главе 3. Игры на универсальные предсказания будут рассмотрены в разделе 8.2.

8.1. Теоретико-игровой закон больших чисел Игровая интерпретация теории вероятностей основана на идех и понятиях из финансов. В игровой постановке Вовка и Шейфера [24] для каждого закона теории вероятностей (например, усиленного закона больших чисел или закона повторного логарифма) формулируется некоторая повторяющаяся игра с полной информацией, в которой на каждом раунде (шаге) игры один участник – Предсказатель, выдает среднее значение будущего исхода, а после этого, другой участник – Природа, выдает новый исход. 1 Третий участник игры – Скептик, определяет цель игры. Зная прогноз, Скептик делает ставку на его отклонение от будущего исхода и выигрывает или проигрывает некоторую величину. Перед началом игры Скептик располагает некоторым начальным капиталом и в течении игры он не может брать в долг – его стратегия должна быть безопасной. Игра устроена таким образом, что если закон теории вероятностей нарушается для последовательности прогнозов и исходов, то Скептик может наращивать свой выигрыш до бесконечности даже находясь в рамках указанных ограничений.

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

Рассмотрим бесконечно повторяющуюся ограниченную игру на предсказания между тремя игроками: Предсказатель, Скептик и Природа.

Действия игроков регулируются следующим протоколом:

FOR n = 1, 2,...

Предсказатель предъявляет прогноз pn [0, 1].

Скептик предъявляет число Mn R.

Природа предъявляет исход n [0, 1].

Скептик обновляет свой выигрыш: Kn = Kn1 + Mn (n pn ).

ENDFOR

Данную игру можно рассматривать как финансовую. В ней на каждом шаге n Скептик покупает Mn единиц некоторого финансового инструмента по pn за каждую единицу. В конце шага объявляется новая цена n и капитал Скептика увеличивается или уменьшается на соответствующую величину. Заметим, что может В случае бинарных исходов 0 и 1 среднее значение равно вероятности 1.

быть Mn < 0. В этом случае Скептик продает некоторое количество единиц финансового инструмента.

sup Kn = (какие бы ходы не предпринимали Предсказатель и Природа); в противном случае выигрывают Природа и Предсказатель.

Траекторией игры называется последовательность ходов всех игроков: p1, M1, 1, p2, M2, 2,.... При этом не предполагается, имеется закон для выбора ходов участников. Если такой закон имеется, называем его стратегией. Например, будет определена стратегия Скептика: на каждом шаге значение Mn будет определяться с помощью последовательности функций Теоретико-игровой закон больших чисел формулируется в виде следующей теоремы.

Теорема 8.1. Можно построить такую безопасную стратегию Скептика, что для любой траектории приведенной выше игры выполнено следующее: если не выполнен усиленный закон больших чисел то Скептик выигрывает в ограниченной игре на предсказание, более того, он может так выбирать свои ходы Mn, что Kn для всех n и lim sup ln n n > 0.

Доказательство. Допустим, что закон больших чисел (8.1) не выполнен. Это означает, что для некоторого > 0 будет выполнено для бесконечно многих n или же для некоторого > 0 будет выполнено для бесконечно многих n.

Используем неравенство t t2 ln(1 + t), которое выполнено при всех t 1/2, и получаем для бесконечно многих n.

Пусть в игре Скептик выбирает на каждом шаге n где Kn1 – его текущий выигрыш. Легко видеть, что выигрыш Скептика на шаге n равен а его логарифм равен Отсюда получаем, что Заметим также, что из определения (8.4), Kn 0 для всех n как бы не выбирались значения i и pi в процессе игры.

Аналогичным образом, в случае когда выполнено (8.3) для бесконечно многих n, можно построить стратегию Скептика где Kn1 – его текущий выигрыш в соответствующей игре.

Недостаток этого рассуждения заключается в том, что Скептик не имеет информации о том, какое из условий (8.2) или (8.3) выполнено для бесконечно многих n, а также для какого > оно выполнено.

Для того, чтобы обойти эту трудность, усложним стратегию Скептика так, чтобы она учитывала оба случая и все возможные значения > 0. Полагаем k = 2k при k = 1, 2,.... Определим K0 = 1 и K0 = 1 для всех k.

Рассмотрим последовательность стратегий и соответствующих вспомогательных игр Объединим вспомогательные игры и стратегии в одну игру и одну смешанную стратегию Mn с одним выигрышем Kn :

Все эти ряды сходятся, так как для любого фиксированного n будет Kn для всех n.

Заметим, что каждый из выигрышей удовлетворяет условиям Если закон больших чисел (8.1) не выполнен, то условие (8.2) или условие (8.3) будет выполнено при некотором = k для бесs,k конечно многих n. Из условия (8.5), в котором Kn = Kn, следует, что для s = 0 или 1. Отсюда следует, что Теорема доказана.

Теоретико-игровую форму закона больших чисел получим путем обращения (и некоторого ослабления) утверждения теоремы 8.1.

Следствие 8.1. Можно построить такую безопасную стратегию Скептика, что для любой реализации ограниченой игры на предсказания выполнена следующая импликация:

где Kn – капитал Скептика на шаге n.

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

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

Рассмотрим некоторую бесконечно повторяющуюся игру между тремя игроками: Предсказатель, Скептик и Природа.

Действия игроков регулируются следующим протоколом:

FOR n = 1, 2,...

Скептик предъявляет функцию Sn : [0, 1] R.

Предсказатель предъявляет прогноз pn [0, 1].

Природа предъявляет исход n {0, 1}.

Скептик обновляет свой выигрыш: Kn = Kn1 + Sn (pn )(n pn ).

ENDFOR

Победители в бесконечной детерминированной игре:

Предсказатель выигрывает в этой игре, если выигрыш Скептика Kn остается ограниченным; в противном случае выигрывают Скептик и Природа.

Теорема 8.2. Скептик и Природа имеют выигрышную стратегию в детерминированной игре на предсказание.

Доказательство. Действительно, Скептик может определить Природа может определять на каждом шаге n игры Тогда в такой игре на каждом шаге n > 0, если n = 0, то pn и поэтому n pn 1 и Sn (pn ) = 1. Отсюда следует, что для всех n, и выигрыш Скептика неограничен.

В этой игре враждебная Природа использует прогноз Предсказателя для формирования своего исхода.

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

Рассмотрим бесконечно повторяющуюся игру между четырьмя игроками: Предсказатель, Скептик, Природа, Генератор случайных чисел, множество исходов – {0, 1}, P{0, 1} – множество всех мер на {0, 1}. Игра регулируется следующим протоколом.

FOR n = 1, 2,...

Скептик предъявляет функцию Sn : [0, 1] R.

Предсказатель предъявляет распределение вероятностей на множестве всех предсказаний: Pn P[0, 1].

Природа предъявляет исход n {0, 1}.

Предсказатель предъявляет тест случайности fn : [0, 1] R, удовлетворяющий условию корректности относительно меры Pn, а именно: fn (p)Pn (dp) 0.

Генератор случайных чисел предъявляет число pn [0, 1].

Скептик обновляет свой выигрыш: Kn = Kn1 + Sn (pn )(n pn ).

Предсказатель обновляет свой выигрыш: Fn = Fn1 + fn (pn ).

ENDFOR

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

Ограничения для Скептика: Скептик должен выбирать Sn так, что его выигрыш Kn 0 для всех n независимо от ходов других игроков.

Ограничения для Предсказателя: Предсказатель должен выбирать Pn и fn так, чтобы его выигрыш Fn 0 для всех n независимо от ходов других игроков. Каждая мера Q P{0, 1} задается двумя числами (q, 1 q), где q = Q{1} – вероятность 1.

Выигрыш Fn соответствует понятию ограниченного снизу супермартинПобедители в рандомизированной игре на предсказания:

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

Предсказатель выигрывает в этой игре, если (i) его выигрыш Fn неограничен или если (ii) выигрыш Скептика Kn остается ограниченным; в остальных случаях выигрывают другие игроки.

В следующей теореме мы докажем, что Предсказатель имеет выигрышную стратегию в этой игре.

Теорема 8.3. Предсказатель имеет выигрышную стратегию в вероятностной игре на предсказания.

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

Предсказатель выбирает число pn [0, 1], Природа выбирает число n {0, 1}. Потери Предсказателя (выигрыш Природы) равны:

Для любой смешанной стратегии Природы Qn P{0, 1}, Предсказатель предъявляет чистую стратегию pn = Q{1}. Чистая стратегия pn соответствует смешанной стратегии Pn (pn ) = 1, Pn (r) = при r [0, 1] \ {pn }.

Тогда математическое ожидание выигрыша Природы относительно смешанной стратегии Q и чистой стратегии pn равно = (1 Q{1})S(pn )(Q{1}) + Q{1}S(pn )(1 Q{1}) = 0.

гала в теории вероятностей, а fn (p) соответствует супермартингал-разности Fn Fn1. Условия игры требуют, чтобы F0 = 1 и в процессе игры Fn для всех n. Условие fn (p)Pn (dp) 0 для всех n влечет Fn Pn (dp) Fn для всех n. Эти свойства составляют определение супермартингала в теории вероятностей. В нашем случае эти свойства должны выполняться только на траектории прогнозов p1, p2,..., которые генерируются в процессе игры.

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

Мы уже имеем две строки, которые соответствуют предсказаниям Природы n {0, 1}.

Рассмотрим некоторое приближение к вспомогательной игре, в котором множество столбцов, соответствующих ходам Предсказателя, конечное. Для произвольного > 0 выберем в множестве [0, 1] конечную -сеть N, состоящую из рациональных точек, такую, что каждая точка этого отрезка находится на расстоянии не более чем от одной из точек этого множества, а также, чтобы значение игры не превосходило /2, если Предсказатель выбирает pn N.

Такую -сеть можно выбрать, так как |Sn (p)| Kn ограничено по p (зависит только от n). 4 Тогда неравенство (8.6) будет преобразовано в неравенство Согласно минимаксной теореме, Поэтому Предсказатель имеет смешанную стратегию P P[0, 1], сосредоточенную на множестве N, такую, что откуда следует, что Скептик должен выбирать Sn (p) так, что Kn 0 для всех n независимо от действий других игроков.

для обоих значений n = 0 и n = 1.

Пусть E – подмножество множества P[0, 1] всех вероятностных мер на единичном отрезке, состоящее из мер P, удовлетворяющих условию (8.7) для n = 0 и n = 1 одновременно.

На множестве мер P[0, 1] можно рассмотреть топологию слабой сходимости. Из теории меры известно, что P[0, 1] компактно в этой топологии. Кроме того, E замкнуто в этой топологии.

Выберем последовательность монотонно убывающих к 0 рациональных чисел i, i = 1, 2,... Пересечение бесконечной последовательности замкнутых вложенных друг в друга подмножеств компакта непусто, поэтому E i =.

Тогда существует вероятностная мера Pn E i P[0, 1], такая, что для n = 0 и n = 1 одновременно.

Вернемся теперь к нашей основной игре. Стратегия Предсказателя будет заключаться в выборе на шаге n вероятностного распределения Pn, которое было определено в вспомогательной игре.

Его вторым ходом будет выбор теста fn для проверки случайного числа Тогда Fn = Kn для всех n.

Среднее значение fn по мере Pn не превосходит 0 по (8.8), т.е.

fn – корректный относительно меры Pn тест.

Из Fn = Kn получаем, что всегда будет выполнено одно из двух: либо выигрыш Скептика ограничен, либо выигрыш Предсказателя неограничен. В обоих случаях Предсказатель выигрывает.

Будем говорить, что Генератор случайных чисел выдает правильные случайные числа, если supn Fn <.

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

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

Пусть – произвольное положительное число такое, что выполнено 0 < < 1. Полагаем K0 = 1. В определенной выше рандомизированной игре на предсказание полагаем т.е. стратегия Скептика не зависит от прогноза Предсказателя на шаге n, а зависит от выигрыша Скептика, полученного им на шагах < n.

В этом случае выигрыш Скептика на шаге n равен где 1,..., n – последовательность исходов, предложенных Природой, а p1,..., pn – последовательность прогнозов, предложенных Предсказателем на шагах 1,..., n.

Так как |i pi | 1 для всех i, Kn 0 для всех n независимо от действий других игроков, т.е. основное требование к к стратегии Скептика выполнено.

По теореме 8.3 Предсказатель имеет выигрышную стратегию в вероятностной игре на предсказания. Это означает, что если Генератор случайных чисел выдает правильные случайные числа, т.е. supn Fn <, то как бы Природа не выдавала свои исходы 1,..., n, Предсказатель обладает методом прогнозирования, при котором для его прогнозов p1,..., pn выигрыш Скептика Kn ограничен, скажем некоторым числом C > 0 :

для всех n. Это неравенство можно переписать в виде для всех n. Здесь мы использовали неравенство ln(1 + t) при |t| 0.5.

Отсюда следует, что Аналогичным образом, полагая K0 = 1 и выбирая стратегию Скептик может добиться того, чтобы Предсказатель выдавал свои прогнозы так, чтобы было выполнено неравенство Обе эти стратегии можно соединить в одну стратегию, которая обеспечивает одновременное выполнение обоих неравенств (8.11) и (8.12). В этом случае стратегии Sn (p) и Sn (p) и соответствующие капиталы Kn (p), Kn (p) рассматриваются Скептиком как вспомогательные в его расчетах.

Для игры Скептик выбирает стратегию Тогда его выигрыш на шаге n будет равен Заметим, что каждый из выигрышей будет удовлетворять условиям Kn 0 и Kn 0 для всех n. На первом шаге S1 (p) = 0, 1 (p) = S 2 (p), затем значения S 1 (p) и S 2 (p) разойдутся, так как они определяются на основании своих выигрышей Kn (p) и Kn (p).

Пусть Генератор случайных чисел выдает правильные случайные числа, т.е. supn Fn <.

Из ограниченности суммарного выигрыша Kn будет следовать ограниченность каждого из выигрышей Kn и Kn. Как было доказано выше, такая ограниченность выигрышей влечет одновременное выполнение предельных неравенств (8.11) и (8.12).

Следующий шаг заключается в том, чтобы построить стратегию Скептика, которая обеспечивает одновременное выполнение неравенств (8.11) и (8.12) для всех > 0.

Для этого введем последовательность k = 2k для всех k.

Определим K0 = 1 и K0 = 1 для всех k. Рассмотрим последовательность стратегий Соответствующие выигрышы связаны условиями Все эти ряды сходятся, так как для любого фиксированного n ления |Sn (p)| 2n1 для всех n.

Заметим, что каждый из выигрышей удовлетворяет условиk 2,k ям Kn 0 и Kn 0 для всех n и k. Поэтому из равномерной ограниченности суммарного выигрыша Kn следует ограниk 2,k ченность каждого из выигрышей Kn и Kn. Как было доказано выше, ограниченность каждого из этих выигрышей влечет одновременное выполнение предельных неравенств (8.11) и (8.12) уже теперь для всех k, k = 1, 2,...

Отсюда получаем, что смешанная стратегия Скептика вынуждает Предсказателя, чтобы выиграть в игре согласно теореме 8.3, выдавать такие прогнозы, что выполнено следующее условие калибруемости:

Определение калибруемости (8.13) обладает очевидным недостатком. Например, хорошо калибруемыми прогнозами для последовательности 1, 2,... = 0, 1, 0, 1, 0, 1, 0, 1,... является последовательность p1, p2,... = 1, 2, 1, 1, 1, 2, 1, 1,... Однако, если рассматривать только члены последовательности исходов, имеющие четные (или нечетные) индексы, подобные прогнозы уже не будут хорошо калибруемыми на соответствующей подпоследовательности. Поэтому необходимо ввести в рассмотрение дополнительные правила выбора подпоследовательностей.

Пусть в процессе игры Природа выдает последовательность исходов 1, 2..., Предсказатель выдает прогнозы p1, p2,... Правилом выбора называется функция определенная на последовательностях типа где pn – прогноз Предсказателя на шаге n, n = 1, 2,..., и принимающая только два значения: 0 и 1.

Последовательность прогнозов p1, p2,... называется хорошо калибруемой на последовательности исходов 1, 2,... относительно правила выбора F (p1, 1, p2, 2,..., pn1, n1, pn ), если выполнено или Основной результат теории универсального прогнозирования утверждает Теорема 8.4. Для любой счетной последовательности правил выбора Fk, k = 1, 2,..., существует такая стратегия Предсказателя (алгоритм вычисления прогнозов Pn по предыстории p1, 1, p2, 2,..., pn1, n1 ), что при любой стратегии Природы, выдающей исходы n на основании известных значений последовательность прогнозов p1, p2,..., выдаваемая генератором случайных чисел, будет хорошо калибруемой относительно любого правила выбора Fk, при условии supn Fn < (т.е. когда генератор случайных чисел выдает правильные случайные числа).

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

В конструкции стратегий Sn (p) и Sn (p) число k заменим на пару k Fs, где k, s = 1, 2,...

Рассмотрим бесконечные последовательности вспомогательных стратегий Скептика:

Введем какую-нибудь эффективную нумерацию всех пар натуральных чисел (k, s). Пусть для такой пары с номером i будет p(i) = и q(i) = s. Такую нумерацию и функции p(i) и q(i) легко опрелелить конкретным образом. Определим Далее доказательство проходит аналогично случаю смешивания стратегий Скептика с множителями k.

Заметим, что суммирование в модернизированном варианте (8.10) должно производиться только по тем i, для которых В модернизированном варианте (8.10) и в (8.13) для того, чтобы получить (8.14), надо n в знаменателе заменить на 8.4. Задачи и упражнения 1. Провести все выкладки для стратегии Sn (p) и получить неравенство (8.12).

2. Завершить доказательство теоремы 8.4.

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

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

В разделе 9.1 мы рассмотрим асимптотические характеристики бесконечно повторяющихся игр с нулевой суммой и покажем, что построенные ранее алгоритмы, машинного обучения приближают точки равновесия Нэша.

В разделе 9.2 мы докажем теорему Блекуэлла о достижимости, которая является обобщением минимаксной теоремы на случай векторно значных функций выигрыша. В разделе 9.3 мы применим эту теорему для построения калибруемых предсказаний для случая произвольного конечного числа исходов.

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

9.1. Бесконечно повторяющиеся игры двух игроков с нулевой суммой Допустим, что на каждом шаге t = 1, 2,... первый игрок выбирает ход It {1,. .., N } в соответствии с распределением вероятностей pt = (p1,t,..., pN,t ) (смешанной стратегией), а второй игрок выбирает ход Jt {1,..., M } в соответствии с распределением вероятностей qt = (q1,t,..., qN,t ). Смешанные стратегии игроков pt и qt могут зависеть от предшествующих ходов игроков и их результатов. Выигрыш первого игрока на шаге t равен f (t, qt ), а выигрыш второго игрока равен f p Будем сравнивать кумулятивный выигрыш каждого игрока за n шагов с кумулятивным выигрышем его наилучшей константной стратегии:

– для первого игрока и для второго игрока.

Мы применим теорию предсказаний с использованием экспертных стратегий для вычисления приближений к равновесию в таких играх. При анализе действий первого игрока множество его ходов {1,..., N } будет рассматриваться как множество вспомогательных экспертов. Каждый эксперт i выдает на всех шагах одно и то же предсказание равное i {1,..., N }. Первый игрок рассматривается как Предсказатель, который выдает на каждом шаге t предсказание It. При этом ходы Jt {1,..., M } второго эксперта интерпретируются как исходы Природы.

Аналогично, при анализе действий второго игрока множество его ходов {1,..., M } также рассматривается как множество вспомогательных экспертов. Каждый эксперт j выдает на всех шагах одно и то же предсказание равное j {1,..., M }. Второй игрок рассматривается как Предсказатель, который выдает на каждом шаге t предсказание Jt. При этом ходы It {1,..., N } второго эксперта интерпретируются как исходы Природы.

Разъясним теперь, какие функции потерь используются при этом анализе. Потери первого игрока равны 1 (Jt, It ) = f (It, Jt ), где Jt – исход Природы, а It – прогноз первого игрока на шаге t.

Потери второго игрока равны 2 (It, Jt ) = f (It, Jt ), где где It – исход Природы, а Jt – прогноз второго игрока на шаге t.

Допустим, что оба игрока выбирают свой ходы в соответствии со смешанными стратегиями, состоятельными по Ханнану (см. определение (4.57)). Например, можно использовать алгоритм экспоненциального взвешивания из разделов 4.2 и 4.6. Согласно этому алгоритму первый игрок выбирает свою смешанную стратегию по формуле где i = 1,..., N, – параметр обучения. При этом ход Js второго игрока рассматривается как исход Природы.

По следствию 4.3 первый игрок является состоятельным по Ханнану, т.е. с вероятностью 1 имеет место при соответствующем выборе параметра.

Второй игрок может также может применять аналогичную стратегию. В этом случаю он также будет состоятельным по Ханнану, т.е. с вероятностью 1 имеет место В терминах выигрышей (9.1) имеет вид: с вероятностью 1 выполнено где траектория I1, I2,... распределена по мере p1 p2... – произведению смешанных стратегий первого игрока.

Соотношение (9.2) имеет вид: с вероятностью 1 имеет место где траектория J1, J2,... распределена по мере q1 q2... – произведению смешанных стратегий второго игрока.

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

Теорема 9.1. Допустим, что в игре двух лиц с нулевой суммой первый игрок выбирает свои ходы согласно смешанной стратегии, состоятельной по Ханнану. Тогда почти всюду, где v – цена игры.

Если каждый игрок придерживается стратегии, состоятельной по Ханнану, то, с вероятностью 1, имеет место равенство Доказательство. Цена игры представляется в виде Кроме того, Согласно соотношению (9.3), для доказательства первого утверждения (9.5) теоремы достаточно показать, что для всех n. Для доказательства заметим, что ции, определенной на симплексе вероятностных распределений на {1,..., N }, достигается в одной из его вершин.

– частота шагов, на которых второй игрок выбирает ход j. Пусть также qn = (1,n,..., qM,n ). Тогда Для доказательства второго утверждения (9.6) теоремы воспользуемся условием (9.4) состоятельности по Ханнану и докажем, что Доказательство этого утверждения аналогично доказательству неравенства (9.7).

Отсюда получим почти всюду, где v – цена игры.

Объединяя (9.8) и (9.5) получим (9.6). Теорема доказана.

9.2. Теорема Блекуэлла о достижимости Теорема 9.1 из предыдущего раздела утверждает, что первый игрок при достаточно большом числе шагов, придерживаясь стратегии состоятельной по Ханнану, может сделать среднее значение своего выигрыша асимптотически не меньше цены игры, какой бы стратегии не придерживался второй игрок.

В этом разделе мы рассмотрим обобщение этого утверждения на случай векторно-значной функции выигрыша и произвольного замкнутого выпуклого множества S вместо цены игры. Будет доказана знаменитая теорема Блекуэлла о достижимости (Blackwell approachability theorem). Эта теорема представляет необходимые и достаточные условия, при которых существует рандомизированная стратегия первого игрока, придерживаясь которой он с вероятностью 1 при неограиченном продолжении игры может как угодно близко приблизить среднее значение вектора своего выигрыша к заданному множеству S, независимо от того, какой бы стратегии не придерживался второй игрок.

В 1956 г. Блекуэлл [7] предложил обобщение минимаксной теоремы на случай векторнозначной функции выигрыша. Позже было замечено, что эта теорема может быть использована для построения калибруемых предсказаний.

По-прежнему рассматривается игра двух лиц. Только теперь функция выигрыша f (i, j) принимает значения в d-мерном пространстве Rd. Напомним, что стратегии первого игрока принадлежат конечному множеству I = {1,..., N }, а стратегии второго игрока принадлежат конечному множеству J = {1,..., M }. Смешанные стратегии игроков – это распределения вероятностей на множествах I и J. Их множества обозначаются P(I) и P(J ) соответственно. При p P(I) и q P(J ) определяется Для смешанных стратегий p = (p1,..., pN ) P(I) и q = (q1,..., qM ) P(J ) получаем линейную комбинацию векторов f (i, j) :

Как обычно, рассматриваем евклидово расстояние между любыми двумя векторами x, y Rd. Если S Rd и x Rd, то расстояние от точки x до множества S определяется как Для замкнутого множества S пусть dS () обозначает какой-нибудь элемент y S, для которого расстояние dist(, S) минимальное.

Если к тому же S – выпуклое, то такой элемент единственный.

Множество S Rd называется достижимым (approachable), если существует такая последовательность p1, p2,... рандомизированных стратегий первого игрока, что для любой последовательности ходов J1, J2,... второго игрока для P -почти всех последовательностей I1, I2,... ходов первого игрока выполнено где P = pt – общее распределение вероятностей на траекториях I1, I2,... ходов первого игрока, которое определяется своими условными распределениями p1, p2,....

Следующая теорема дает достаточное условие достижимостых замкнутого выпуклого подмножества из Rd.

Предполагаем, что рассматриваемые далее множества S и значения f (i, j) находятся в единичном шаре пространства Rd.

Теорема 9.2. Задано замкнутое подмножество S Rd. Для каждого вектора x S рассмотрим гиперплоскость x, проходящую через точку dS () и ортогональную прямой, соединяющей точки x и dS ().

Допустим, что для каждого вектора x S существует распределение p P(I) такое, что все точки f (, 1),..., f (, M ) и точка x лежат по разные стороны гиперплоскости x. Тогда множество S достижимо.

Доказательство. Пусть I1, I2,... и J1, J2,... – какие-либо стратегии первого и второго игроков. Обозначим вектор среднего значения выигрышей за первые t шагов Пусть на шагах < t игры игроки уже произвели ходы I1,..., It и J1,..., Jt1. Уравнение гиперплоскости x, проходящей через точку x = dS (mt1 ) и ортогональную прямой, соединяющей точки mt1 и dS (mt1 ), имеет вид где Предполагаем, что m0 = Заметим, что точка dS (mt1 ) находится выше гиперплоскости (так как является концом направляющего вектора этой гиперплоскости).

По условию теоремы для x = dS (mt1 ) существует смешанная стратегия pt первого игрока, для которой все точки находятся ниже данной гипервлоскости:

для всех j = 1,..., M. Это условие можно также записать в виде Смешанная стратегия pt определяется путем решения задачи линейного программирования (9.9).

Проверим, что точка mt приближается к множеству S. Из определения Нетрудно проверить, что Возведем в квадрат неравенство (9.10) и продолжим выкладки с использованием (9.11) :

Так как множество S и все значения f (i, j) находятся в единичном шаре пространства Rd, выполнено неравенство Используя это неравенство преобразуем неравенства (9.11) и (9.12) в неравенство 4 + 2(t 1)((mt1 dS (mt1 )) · (f (It, Jt ) dS (mt1 ))). (9.13) Обозначим 1,..., T левую и правую части неравенства (9.13) и разделим их на T 2 :

Для получения последнего неравенства мы использовали неравенство (9.10).

Второе слагаемое последнего члена (9.14) представляет собой мартингал-разность. Поэтому оно по следствию 4.9 к неравенству Хефдинга–Азумы почти всюду стремится к 0 при T. Отсюда с вероятностью 1. Теорема доказана.

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

Теорема 9.3. Замкнутое выпуклое подмножество S Rd достижимо тогда и только тогда, когда для каждого q P(J ) существует p P(I) такое, что f (, q ) S.

Доказательство. Допустим, что для каждого q P(J ) существует p P(I) такое, что f (, q ) S. Пусть также x0 S и dS (0 ) – ближайшая к x0 точка из S. Рассмотрим вспомогательную матричную игру с функцией выигрыша a(i, j) = ((dS (0 )0 )·f (i, j)).

По минимаксной теореме По условию теоремы для каждого q P(J ) существует i такое, что f (i, q ) S. Отсюда и из (9.15) получаем Рассмотрим гиперплоскость Легко проверить, что ствует p P(I) такое, что для любого j = 1,..., M выполнено условие теоремы 9.2. Следовательно множество S достижимо.

Для доказательства обратного утверждения, допустим, что существует q0 P(J ) такое что f (, q0 ) S для всех p P(I).

Применим теорему 9.2 для игры с транспонированной матрицей (функцией) выигрыша f (i, j) = f (j, i) и выпуклого замкнутого множества T (0 ) = {f (, q0 ) : p P(I)}.

Существует q0 такое, что все значения f (0, 0),..., f (0, M ) T (0 ). Из выпуклости множества T (0 ) следует, что для любого x T (0 ) точки x и f (0, 0),..., f (0, M ) находятся по разные стороны от гиперплоскости x. Тогда по теореме 9.2 множество T (0 ) достижимо (для второго игрока первоначальной игры с поq стоянной стратегией q0 ). Мы допустили, что T (0 ) S =. Значит множество S не достижимо для первого игрока.

Теорема доказана.

В качестве первого применения теоремы 9.2 построим стратегию предсказания состоятельную по Ханнану.

Пусть заданы множества ходов I = {1,..., N } – первого игрока и J = {1,..., M } – второго игрока. P(I) и P(J ) – множества их смешанных стратегий. Рассматривается игра с функцией потерь l(i, j), где 0 l(i, j) 1 для всех i, j.

Наша цель определить на каждом шаге t смешанную стратегию pt первого игрока такую, что для любой последовательности ходов J1, J2,... второго игрока с вероятностью 1 было выполнено где последовательность ходов I1, I2,... распределена по мере t pt.

Для того, чтобы применить теорему 9.2 рассмотрим выпуклое замкнутое множество а также векторнозначную платежную функцию потерь Заметим, что значения f (i, j) лежат в N -мерном шаре радиуса N с центром в начале координат. Умножая функцию потерь на константу 1/ N можно добиться, чтобы значения f (i, j) лежали в единичном шаре.

Рассмотрим произвольный вектор x0 S. Достаточно рассмотреть случай когда dS (x0 ) = и уравнение гиперлоскости x имеет вид (w · x) = 0, где все компоненты wi нормального вектора w гиперплоскости неотрицательные.

Для доказательства существования стратегии такой, что выполнено (9.17), достаточно доказать, что существует смешанная стратегия p P(I) такая, что все векторы f (, 1),..., f (, M ) лежат ниже гиперплоскости (w · x) = 0, т.е. выполнено для всех j = 1,... M. Легко проверить, что это условие выполнено при По теореме 9.2 существует последовательность смешанных стратегии p1,..., pt,... такая, что условие (9.17) выполнено с вероятностью 1.

9.3. Калибруемые предсказания В этом разделе мы приведем метод построения калибруемых предсказаний в случае произвольного конечного множества исходов на основе теоремы 9.3. Этот метод был предложен в работе Маннора и Штольца [22].

В разделе 3.2 рассматривались задача универсального предсказания среднего значения pi будущего исхода i и соответствующее понятие калибруемости. В этом разделе будет рассматриваться задача универсального предсказания вероятностного распределения будущих исходов. В случае бинарного множества исходов {0, 1} обе эти задачи эквивалентны, так как вероятность единицы pi равна среднему значению будущего исхода i {0, 1}.

Будем предполагать, что исходы принадлежат конечному множеству A = {a1,..., am }. Обозначим P(A) – множество всех распределений вероятностей на множестве A. Каждое такое распределение (смешанная стратегия) есть вектор p = (p1,..., pm ) неотрицательных вещественных чисел сумма которых равна 1. На векторах–распределениях будет рассматриваться норма p 1 = max1 i m |pi |. Можно также рассматривать широко известную эвклидову норму p 2 в Rm. Известно, что эти нормы эквивалентны в пространстве Rm. В дальнейшем мы будем использовать обозначение p имея ввиду любую из этих норм.

Пусть [ai ] = (0,..., 1,..., 0) обозначает вероятностное распределение, сосредоточенное на элементе ai множества A. В этом векторе i-й элемент равен 1, остальные элементы – нулевые.

Рассмотрим игру с полной информацией между Предсказателем и Природой. На каждом шаге t Предсказатель выдает вероятностное распределение pt P(A), после чего Природа выдает исход at A.

В терминах теории игр, pt – смешанная стратегия Предсказателя, [at ] – чистая стратегия Природы.

Для выбора стратегий p1, p2,... Предсказатель будет применять рандомизированную стратегию, точнее, Предсказатель будет выдавать на каждом шаге t случайный вектор pt P(A), распределенный согласно некоторому вероятностному распределению Pt P(P(A)). По теореме Ионеску-Тульчи [3] вероятностные меры Pt можно рассматривать как условные распределения относительно некоторого общего распределения P = Pt на траекториях p1, p2,....

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

Пусть задано число > 0. Цель Предсказателя выдавать рандомизированные прогнозы pt распределенные по мере P так, чтобы для любого p P(A) для произвольной стратегии a1, a2,...

Природы P -почти всюду было выполнено условие -калибруемости:

где векторы p1, p2,... распределены по мере P и Предсказатель будет выбирать свои прогнозы pt из некоторого фиксированного конечного множества стратегий P = {1,..., sN }.

Для задания этого множества построим какую-нибудь -сеть в множестве всех векторов P(A). Таким образом, для любого вектора p P(A) найдется элемент -сети si P такой, что p i <.

Мы будем строить вероятностные распределения Pt P(P(A)), сконцентрированные на конечном множестве P. Для простоты мы отождествляем конечное множество P = {1,..., sN } и мноs жество индексов его элементов I = {1, 2,..., N }, а также будем рассматривать на каждом шаге t вероятностные распределение Pt на I.

Общее распределение на тректориях i1, i2,... номеров определяется как P = Pt. Тогда условие (9.18) очевидным образом следует из следующего условия: P -почти всюду выполнено условие где траектория i1, i2,... распределена по мере P.

Существование -калибруемой стратегии в общей форме утверждается в следующей теореме.

Теорема 9.4. Для произвольного > 0 можно построить вероятностное распределение P такое, что P -почти всюду выполнено условие -калибруемости (9.18), где векторы p1, p2,... распределены согласно P.

Доказательство. Мы применим теорему 9.3, в которой первый игрок – это Предсказатель с множеством стратегий 2 I = {1, 2,..., N }, а второй игрок – Природа с множеством стратегий J = A. Функция выигрыша принимает в качестве значений векторы размерности N |A| :

где k I и a J, – m-мерный нулевой вектор, m = |A|, а также sk [a] – разность двух векторов – столбцов размерности m, которая занимает k-ю компоненту сложного вектора.

Определим теперь выпуклое множество в пространстве RmN.

Мы записываем векторы пространства RmN как сложные векторы размерности N с вектор-компонентами в Rm : X = (1,..., xN ), m. Определим замкнутое выпуклое множество где xi R По теореме 9.3 замкнутое выпуклое подмножество C достижимо тогда и только тогда, когда для каждого q P(J ) существует p P(I) такое, что f (, q ) C.

Условие (9.18) эквивалентно условию (9.19).

Мы отождествляем P = {1,..., sN } и множество индексов I = {1, 2,..., N }.

Условие теоремы 9.3 о достижимости выполнено для множества C, так как для любой смешанной стратегии q P(J ) = P(A) второго игрока, найдется точка sk из P такая, что si q т.е. f (k, q ) C. В этом случае мы берем в теореме 9.2 в качестве p распределение [k] на I = {1,... N }, сосредоточенное на числе k, где 1 k N.

По теореме 9.2 можно построить рандомизированную страPt, где Pt P(I) такую, что как тегию Предсказателя P = бы Природа не выбирала последовательность a1, a2,... последовательность векторно-значных выигрышей P -почти всюду сходится к множеству C, где траектория i1, i2,...

распределена по мере P.

Таким образом, условие калибруемости (9.19) выполнено почти всюду. Теорема доказана Последовательность предсказаний называется калибруемой на последовательности исходов, если она является -калибруемой для любого > 0.

Предсказания, которые выбираются из конечного множества P = {1,..., sN } и удовлетворяют условию (9.19), называются -калибруемыми FV-предсказаниями.

Можно усилить теорему 9.4 и добиться калибруемости предсказаний.

Теорема 9.5. Можно построить рандомизированную стратегию Предсказателя P такую, что для любого p P(A) условие калибруемости выполнено P -почти, где последовательность векторов p1, p2,...

распределена по мере P.

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

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

Каждое распределене вероятностей на конечном множестве мощности N есть N -мерный вектор: обозначим такое распределение p. Поэтому в качестве нормы на таких распределениях можно рассматривать одну их эквивалентных норм p на N (эвклидову или максимум) и соответствующее расстояние ства S R Бесконечная последовательность p1, p2,... сходится к множеству S, если Рассмотрим произвольную игру k игроков, заданную в нормальной форме. Для каждого игрока i задано конечное множество его ходов (стратегий): Ai = {1,..., Ni }, i = 1,..., k. Кроме этого, для каждого игрока i задана функция его выигрыша f i (i1,..., ik ), где is As, s = 1,... k, – ходы всех игроков.

Смешанная стратегия игрока s – это вероятностное распределение на множестве его ходов As. Мы также будем рассматривать смешанные стратегии групп игроков s1,..., sl – совместные вероятностные распределения на множествах их ходов As1... Asl.

Обозначим A = k Aj и Ai = j=i Aj. Пусть pt – про- i извольное распределение вероятностей на множестве ходов всех игроков, кроме i, – их совместная смешанная стратегия. Здесь нижний индекс подчеркивает, что pi P(Ai ).

Будем также использовать обозначения:

где a Ai, ai Ai, E – символ математического ожидания относительно меры pi.

Пусть теперь игроки повторяют свою игру на шагах t = 1, 2,... согласно следующему протоколу.

FOR t = 1, 2,...

Для каждого i = 1,..., k, игрок i выдает предсказание набора будущих ходов своих оппонентов j = i – распределение вероятностей pt (смешанная совместная стратегия этих игроков) и выбирает свою стратегию at Ai, при которой его выигрыш максимален, при условии, что его оппоненты будут придерживаются совместной смешанной стратегии pt : i

ENDFOR

Мы называем любую стратегию a игрока i, на которой достигается максимум функции f i (a, pt ), оптимальным ответом на t ходов остальных игроков. Если имеется нескольпредсказание pi ко таких стратегий, то выбирается одна из них – at, согласi но какому-либо заранее фиксированному правилу. Называем эту стратегию выбранным оптимальным ответом.

Пусть at = (at,..., at ) – набор ходов всех игроков на шаге t.

Обозначим - эмпирическое частотное распределение наборов стратегий, выa бранных всеми игроками за T шагов игры. Здесь [] есть вектор размерности i=1 |Ai |, в котором одна координата, соответствующая набору a, равна 1, а все остальные его координаты равны Координатами вектора pT являются частоты встречаемости каждого набора стратегий a = (a1,..., ak ) в последовательности наборов at = (at,..., at ), выбранных игроками на шагах t = 1,..., T игры. Размерность вектора pT, как и вектора [t ], равна Каждому набору стратегий a = (a1,..., ak ) соответствует число – значение частотного распределения на наборе a (соответствующая координата вектора pT ).

Напомним, что последовательность предсказаний i-го игрока pt калибруется на последовательности исходов всех игроков, кроi ме i-го игрока, at, t = 1, 2,..., если для произвольного вероятi ностного распределения pi Ai 0 – произввольное и I – индикаторная функция соответгде ствующего условия.

Следующая теорема показывает, что если каждый игрок использует предсказания ходов остальных игроков, которые калибруются на наборах стратегий оппонентов, и выбирает оптимальный ответ (9.21) на эти предсказания, то совместное частотное распределение стратегий игроков сходится к множеству C коррелированных равновесий игры.

Теорема 9.6. Если для каждого i предсказания p1, p2,... каi i нентов i, то последовательность частотных эмпирических распределений pT, определенных по (9.22), сходится к множеству C коррелированных равновесий.

Доказательство. Для доказательства теоремы, надо показать, что при T, где C – множество всех коррелированных равновесий игры. Мы также покажем, что C =.

Симплекс всех распределений вероятностей на многограннике A = k Ai (векторов размерности |A|) является компактным множеством. Поэтому последовательность распределений {T : p T = 1, 2,... }, определенных по (9.22), содержит бесконечную сходящуюся подпоследовательность pTj. Пусть p – предельная точка этой подпоследовательности. Мы докажем, что p является коррелированным равновесием.

Фиксируем i и ход a Ai игрока i такие, что Пишем f = f i, и определим два подмножества (зависящие от – множество всех смешанных стратегий оппонентов игрока i, для которых его чистая стратегия a является оптимальным ответом.

Легко видеть, что B – замкнутое выпуклое множество. Определим также Если p (a) = 0, то то ход a можно не учитывать при подсчете частотного распределения; это эквивалентно случаю, когда i-й игрок не использует a. В этом случае a можно игнорировать.

– множество всех смешанных стратегий, выбранных оппонентами игрока i на тех шагах t = 1, 2,... игры, на которых он выбрал ход a в качестве оптимального ответа. Из определения B B.

Из определения следует, что множество B является не более чем счетным, так как на каждом шаге к нему добавляется не более одного элемента.

Рассмотрим условную вероятность произвольного вектора ходов ai всех игроков, кроме i, при известном ai = a (где a было выбрано выше) относительно предельного распределения p : По следствию 7.3 распределение вероятностей p на множестве k=1 {1,..., Nk } последовательностей стратегий a = (a1,..., aK ) является коррелированным равновесием тогда и только тогда, когда для каждого игрока i {1,..., K} и любых стратегий a, a {1,..., Ni } выполнено Отсюда следует, что вероятностное распределение p является коррелированным равновесием тогда и только тогда, когда условное распределение p (·|ai = a) B для всех i и a Ai.

Мы докажем, что p (·|ai = a) B рассматривая приближение к нему с помощью соответствующего частотного распределения.

Пусть – число шагов – число шагов набор смешанных стратегий pi P(Ai ).

Определим соответствующее распределению pT условное частотное распределение pT (·|ai = a) стратегий, выбранных всеми игроками кроме i, а именно, рассмотрим условную вероятность ai при известном ai = a относительно распределения pT :

Согласно (9.25) pTj (ai |ai = a) p (ai |ai = a) при j.

По определению множества B элемент a Ai появляется в Отсюда следует, что частота встречаемости любого набора (a, ai ) в последовательности равна частоте встречаемости набора ai в последовательности Поэтому по (9.23) получаем:

pT (a, ai ) = pT () = По определению pT (ai = a) = NT (a). Отсюда получаем выT ражения для условного частотного распределения, образованного последовательностью at, где at = a, t = 1,..., T :

Пусть > 0 – произвольное. Мы будем считать, что предсказания выбираются из конечного множества P = {1,..., sN } и удоs влетворяют условию (9.19). Такие предсказания были названы калибруемыми FV-предсказаниями. В этом случае множество B конечно. Поэтому из условия (9.19) следует, что Более того, по теореме 9.5 можно постепенно уменьшать число и строить предсказания таким образом, что среднее (9.29) будет стремиться к нулю при T.

Таким образом, сумма (9.27) стремится к нулю при T.

Так как p (ai = a) > 0 и p есть предел распределений pTj при По определению Таким образом, по (9.28) распределение pTj (·|ai = a) сходится при Tj к множеству выпуклых комбинаций элементов из множества B, которое в свою очередь является подмножеством выпуклого замкнутого множества B. Отсюда при Tj.

Из сходимости pTj p следует, что для произвольного вектора ai будет pTj (i |ai = a) p (ai |ai = a) при Tj. Отсюда и из замкнутости множества B следует, что p (·|ai = a) B для всех i и a Ai, и, тем самым, вероятностное распределение p является коррелированным равновесием. Отсюда следует утверждение теоремы.

Литература [1] Беккенбах Э., Беллман Р. Неравенства. – М.: Мир, 1965. – [2] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). – М.: Наука, [3] Ширяев А.Н. Вероятность. – М.: МЦНМО, 2007. – 968 с.

[4] Шикин Е.В., Шикина Г.Е. Исследование операций: учебное пособие. – М.: ТК Велби, изд. Проспект, 2006. – 280 с.

[5] Alon N., Ben-David S., Cesa-Bianchi N., Haussler D. // Scalesensitive dimensions, uniform convergence, and learnability. J.

ACM V. 1997. 44(4). P. 615-631.

[6] Aronszajn N. Theory of reproducing kernels // Transactions of the American Mathematical Society. 1950. V. 68. P. 337Џ404.

[7] Blackwell D. An analog of the minimax theorem for vector payos // Pacic Journal of Mathematics. 1956. V. 6. P. 1–8.

[8] A. Chernov, F. Zhdanov. Prediction with expert advice under discounted loss. Technical report, arXiv:1005.1918v1 [cs.LG], [9] Cover T., Ordentlich E. Universal portfolio with side information // IEEE Transaction on Information Theory – 1996. – V. 42. – P. 348–363.

[10] Cristianini N., Shawe-Taylor J. An Introduction to Support Vector Machines. – Cambridge UK: Cambridge University Press, [11] Dawid A.P. Calibration-based empirical probability [with discussion] // Ann. Statist. – 1985. – V. 13. – P. 1251–1285.

[12] Foster D.P., Vohra R. Asymptotic calibration // Biometrika. – 1998. – V. 85. – P. 379–390.

[13] Freund Y., Schapire R.E. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting // Journal of Computer and System Sciences – 1997. – V. 55. – P. 119–139.

[14] J. Hannan. Approximation to Bayes risk in repeated plays. In M. Dresher, A.W. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games 3, pages 97-139, Princeton University Press, 1957.

[15] M. Hutter and J. Poland. Adaptive online prediction by following the perturbed leader // Journal of Machine Learning Research, 6:639–660, 2005.

[16] Kakade, S.M., Foster, D.P. Deterministic calibration and Nash equilibrium // Lecture Notes in Computer Science – Berlin:

Springer, 2004. – V. 3120. – P. 33–48.

[17] Kakade S., Tewari A. Learning Theory Lectures 1-17. CMSC 35900 (Spring 2008):

http://ttic.uchicago.edu/ tewari/lectures/lecture11.pdf [18] A. Kalai and S. Vempala. Ecient algorithms for online decisions. In Bernhard Scholkopf, Manfred K. Warmuth, editors, Proceedings of the 16th Annual Conference on Learning Theory COLT 2003, Lecture Notes in Computer Science 2777, pages 506–521, Springer-Verlag, Berlin, 2003. Extended version in Journal of Computer and System Sciences, 71:291–307, 2005.

[19] Kimeldorf G. S. and Wahba G. Some results on Tchebychean spline functions // J. Math. Anal. Appl. – 1971 –V. 33 – 82-Џ95.

[20] Littlestone N., Warmuth M. The weighted majority algorithm // Information and Computation – 1994 – V. 108 – P. 212–261.

[21] Lugosi G., Cesa-Bianchi N. Prediction, Learning and Games. – New York: Cambridge University Press, 2006.

[22] Mannor S., Stoltz G. A Geometric Proof of Calibration // arXiv:0912.3604v2. 2009.

[23] McDiarmid C. On the method of bounded dierences. London Mathematical Society Lecture Notes Series. Surveys in Combinatorics. Cambridge University Press. V. 141. pp. 148Џ188. 1989.

[24] Shafer G., Vovk V. Probability and Finance. It’s Only a Game!

– New York: Wiley. 2001.

[25] Shawe-Taylor J., Cristianini N. Margin distribution bounds on generalization // In Proceedings of the European Conference on Computational Learning Theory, EuroCOLT’99. P.263–273.

[26] Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. – Cambridge UK: Cambridge University Press, 2004.

[27] Scholkopf B. and Smola A. Learning with Kernels. MIT Press, Cambridge, MA, 2002.

[28] Vapnik V.N. Statistical Learning Theory. – New York: Wiley, [29] Vovk V. Aggregating strategies // Proceedings of the 3rd Annual Workshop on Computational Learning Theory (M. Fulk and J.

Case, editors,) – San Mateo, CA: Morgan Kaufmann, 1990. – P.

371–383.

[30] Vovk V. A game of prediction with expert advice // Journal of Computer and System Sciences – 1998 – V. 56. – No. 2.

P. 153–173.

[31] Vovk V., Watkins C. Universal portfolio selection // Proceedings of the 11th Annual Conference on Computational Learning Theory – New York: ACM Press, 1998. – P. 12–23.

[32] Vovk V. Competitive on-line statistics // International Statistical Review – 2001 – V. 69. – P. 213–248.

[33] Vovk V, Gammerman A., Shafer G. Algorithmic Learning in a Random World. Springer, New York, 2005.

[34] Vovk V., Shafer G. Good randomized sequential probability forecasting is always possible // J. Royal Stat. Soc. B. – 2005 – V.

[35] Vovk V., Takemura A., Shafer G. Defensive forecasting // Proceedings of the 10th International Workshop on Articial Intelligence and Statistics (ed. by R. G. Cowell and Z. Ghahramani) – Cambridge UK: Society for Articial Intelligence and Statistics, 2005. – P. 365–372.

[36] Vovk V. On-line regression competitive with reproducing kernel Hilbert spaces (extended abstract) // Lecture Notes in Computer Science – Berlin: Springer, 2006. – V. 3959. – P. 452–463.

[37] Vovk V. Predictions as statements and decisions // Theoretical Computer Science – 2008. – V. 405. – No. 3. – P. 285–296.