• Статья

МАЙ 2016

ТОМ 31 НОМЕР 5

Тесты - Задача о многоруком бандите

Джеймс Маккафри | МАЙ 2016

Исходный код можно скачать по ссылке

James McCaffreyВообразите, что вы попали в Лас-Вегас и стоите перед тремя игорными автоматами. У вас 20 жетонов, вы опускаете жетон в какой-либо из этих трех автоматов, тянете ручку и получаете случайный выигрыш. Все автоматы платят по-разному, но изначально вы не знаете, какой программе выплат следуют эти автоматы. Какие стратегии можно использовать, чтобы попытаться максимально увеличить свой выигрыш?

Это пример задачи о многоруком бандите (multi-armed bandit problem), названной так потому, что игорный автомат в быту называют одноруким бандитом. Эта задача не столь фантастична, как может показаться с первого взгляда. В реальной жизни существует много важных задач вроде клинических испытаний лекарств, которые подобны примеру с игорным автоматом.

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

Хороший способ получить представление о том, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1. Есть много алгоритмов, применимых к задачам о многоруком бандите. Например, полностью произвольный подход мог бы заключаться в простом случайном выборе автомата для каждого переключения ручки с последующей надеждой на удачу. Демонстрация, представленная здесь, использует базовый метод, называемый алгоритмом «исследуй-используй» (explore-exploit algorithm).

Применение алгоритма «исследуй-используй» к задаче о многоруком бандите
Рис. 1. Применение алгоритма «исследуй-используй» к задаче о многоруком бандите

Демонстрационная программа начинает с создания трех автоматов. Каждый автомат выплачивает случайный выигрыш при каждом переключении ручки, где выигрыш следует нормальному (колоколообразному) распределению с заданным средним линейным (mean deviation) и среднеквадратичным отклонением (standard deviation). Третий автомат является лучшим в одном плане — он дает наивысший средний выигрыш при каждом переключении ручки, равный 0.1 произвольных единиц. В реальном сценарии вам были бы неизвестны характеристики автоматов.

Общее количество доступных переключений установлено равным 20. В алгоритме «исследуй-используй» вы откладываете определенную долю выделенных переключений и используете их для поиска лучшего автомата методом проб и ошибок. Затем вы используете оставшиеся переключения только на лучшем автомате, обнаруженном на предварительном этапе исследования. Ключевой переменной в алгоритме «исследуй-используй» является доля переключений, выделяемая для этапа исследования. В демонстрации эта доля равна 0.40, поэтому сначала выполняется 20 * 0.40 = 8 переключений на этапе исследования, а затем 20 – 8 = 12 переключений на этапе использования. Увеличение доли переключений для этапа исследования повышает вероятность нахождения лучшего автомата за счет меньшей доли переключений, остающихся на этапе использования лучшего автомата.

На этапе исследования по восьми переключениям демонстрационная программа отображает, какой автомат выбран случайным образом и какой выигрыш он дает. За кулисами демонстрация сохраняет накопленные выигрыши по каждому автомату. Автомат 0 был выбран три раза и выплатил –0.09 + 0.12 + 0.29 = +0.32 единицы. Автомат 1 был выбран два раза и выплатил –0.46 + –1.91 = –2.37 единицы. Автомат 2 был выбран три раза и выплатил 0.19 + 0.14 + 0.70 = +1.03 единицы. В случае демонстрации алгоритм «исследуй-используй» правильно идентифицировал автомат 2 как лучший, поскольку он дает наибольшую суммарную награду. К этому моменту алгоритм имеет чистый выигрыш (проигрыш), равный 0.32 + –2.37 + 1.03 = –1.02 единиц.

На этапе использования 12 переключений демонстрационная программа повторно играет только с автоматом 2. На этом этапе выигрыш составляет 0.03 + 0.33 + . . + 0.45 = +2.32 единицы. Следовательно, суммарный выигрыш по всем 20 переключениям равен –1.02 + 2.32 = +1.30 единиц, а средний выигрыш на переключение составляет 1.30 / 20 = 0.065.

Существует несколько других показателей, которые можно использовать для оценки эффективности алгоритма многорукого бандита. Один из распространенных показателей называют потерями (regret). Потери — это разница между теоретическим базисным суммарным выигрышем и реальным суммарным выигрышем для алгоритма. Теоретическим базисным является ожидаемый выигрыш, если все выделенные переключения были использованы на лучшем автомате. В случае трех автоматов в демонстрации лучший автомат давал средний выигрыш в 0.10 единиц, поэтому ожидаемый выигрыш при условии использования всех 20 переключений составил бы 20 * 0.10 = 2.00 единицы. Поскольку алгоритм «исследуй-используй» дал суммарный выигрыш всего в 1.30 единицы, коэффициент потерь — 2.00 – 1.30 = 0.70 единиц. Алгоритмы с более низкими значениями потерь лучше таковых с более высокими значениями.

В этой статье предполагается, что вы умеете программировать хотя бы на среднем уровне, но ничего не знаете о задаче о многоруком бандите. Полная демонстрационная программа с некоторыми правками для экономии места представлена на рис. 2, но вы можете найти полный исходный код в сопутствующем этой статье пакете кода. Демонстрационная программа написана на C#, но у вас не должно возникнуть особых проблем, если вы захотите выполнить рефакторинг кода под другой язык вроде Python или Java. Я убрал стандартную обработку ошибок, чтобы по возможности не затуманивать основные идеи.

Рис. 2. Полный код демонстрационной программы, решающей задачу о многоруком бандите

using System;
namespace MultiBandit
{
  class MultiBanditProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin multi-armed bandit demo \n");

      Console.WriteLine("Creating 3 Gaussian machines");
      Console.WriteLine("Machine 0 mean =  0.0, sd = 1.0");
      Console.WriteLine("Machine 1 mean = -0.5, sd = 2.0");
      Console.WriteLine("Machine 2 mean =  0.1, sd = 0.5");
      Console.WriteLine("Best machine is [2] mean pay = 0.1");

      int nMachines = 3;
      Machine[] machines = new Machine[nMachines];
      machines[0] = new Machine(0.0, 1.0, 0);
      machines[1] = new Machine(-0.5, 2.0, 1);
      machines[2] = new Machine(0.1, 0.5, 2);

      int nPulls = 20;
      double pctExplore = 0.40;
      Console.WriteLine("Setting nPulls = " + nPulls);

      Console.WriteLine("\nUsing pctExplore = " +
        pctExplore.ToString("F2"));
      double avgPay = ExploreExploit(machines, pctExplore,
        nPulls);
      double totPay = avgPay * nPulls;
      Console.WriteLine("\nAverage pay per pull = " +
        avgPay.ToString("F2"));
      Console.WriteLine("Total payout         = " +
        totPay.ToString("F2"));

      double avgBase = machines[2].mean;
      double totBase = avgBase * nPulls;
      Console.WriteLine("\nBaseline average pay = " +
        avgBase.ToString("F2"));
      Console.WriteLine("Total baseline pay   = " +
        totBase.ToString("F2"));

      double regret = totBase - totPay;
      Console.WriteLine("\nTotal regret = " +
        regret.ToString("F2"));

      Console.WriteLine("\nEnd bandit demo \n");
      Console.ReadLine();

    } // Main

    static double ExploreExploit(Machine[] machines,
      double pctExplore, int nPulls)
    {
      // Применяем базовый алгоритм "исследуй-используй".
      // Возвращает средний выигрыш на одно переключение ручки.
      int nMachines = machines.Length;
      Random r = new Random(2); // какой автомат

      double[] explorePays = new double[nMachines];
      double totPay = 0.0;

      int nExplore = (int)(nPulls * pctExplore);
      int nExploit = nPulls - nExplore;

      Console.WriteLine("\nStart explore phase");
      for (int pull = 0; pull < nExplore; ++pull)
      {
        int m = r.Next(0, nMachines); // выбираем автомат
        double pay = machines[m].Pay(); // играем
        Console.Write("[" +
          pull.ToString().PadLeft(3) + "]  ");
        Console.WriteLine("selected machine " + m + ". pay = "
          + pay.ToString("F2").PadLeft(6));
        explorePays[m] += pay; // обновляем
        totPay += pay;
      } // конец этапа исследования

      int bestMach = BestIdx(explorePays);
      Console.WriteLine("\nBest machine found = " + bestMach);

      Console.WriteLine("\nStart exploit phase");
      for (int pull = 0; pull < nExploit; ++pull)
      {
        double pay = machines[bestMach].Pay();
        Console.Write("[" + pull.ToString().PadLeft(3) + "] ");
        Console.WriteLine("pay = " +
          pay.ToString("F2").PadLeft(6));
        totPay += pay; // суммируем
      } // Конец этапа использования

      return totPay / nPulls; // сред. выигрыш на переключение

    } // ExploreExploit

    static int BestIdx(double[] pays)
    {
      // Индекс массива с наибольшим значением
      int result = 0;
      double maxVal = pays[0];
      for (int i = 0; i < pays.Length; ++i)
      {
        if (pays[i] > maxVal)
        {
          result = i;
          maxVal = pays[i];
        }
      }
      return result;
    }
  } // класс Program

  public class Machine
  {
    public double mean; // сред. выигрыш на переключение
    public double sd;   // дисперсия вокруг среднего
    private Gaussian g; // генератор выигрышей

    public Machine(double mean, double sd, int seed)
    {
      this.mean = mean;
      this.sd = sd;
      this.g = new Gaussian(mean, sd, seed);
    }

    public double Pay()
    {
      return this.g.Next();
    }

    // -----
    private class Gaussian
    {
      private Random r;
      private double mean;
      private double sd;

      public Gaussian(double mean, double sd, int seed)
      {
        this.r = new Random(seed);
        this.mean = mean;
        this.sd = sd;
      }

      public double Next()
      {
        double u1 = r.NextDouble();
        double u2 = r.NextDouble();
        double left = Math.Cos(2.0 * Math.PI * u1);
        double right = Math.Sqrt(-2.0 * Math.Log(u2));
        double z = left * right;
        return this.mean + (z * this.sd);
      }
    }
    // -----

  } // Machine

} // ns

Демонстрационная программа

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект MultiBandit. Я использовал Visual Studio 2015, но в этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный MultiBanditProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

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

После нескольких вступительных выражений WriteLine в демонстрации создаются три автомата:

int nMachines = 3;
Machine[] machines = new Machine[nMachines];
machines[0] = new Machine(0.0, 1.0, 0);
machines[1] = new Machine(-0.5, 2.0, 1);
machines[2] = new Machine(0.1, 0.5, 2);

Конструктор класса Machine принимает три аргумента: средний выигрыш, среднеквадратичное отклонение для выигрышей и начальное значение для генератора случайных чисел. Таким образом, machine[1] выплатит в среднем –0.5 единиц на переключение, где большая часть выигрышей (около 68%) будет лежать в диапазоне между –0.5 – 2.0 = –1.5 единицы и –0.5 + 2.0 = +1.5 единицы. Заметьте, что в отличие от реальных игорных автоматов, которые выплачивают либо ноль, либо какое-то положительное значение выигрыша, автоматы в демонстрации могут выплачивать отрицательные значения выигрышей.

Выражения, которые выполняют алгоритм «исследуй-используй» для трех автоматов, выглядят так:

int nPulls = 20;
double pctExplore = 0.40;
double avgPay = ExploreExploit(machines, pctExplore, nPulls);
double totPay = avgPay * nPulls;

Метод ExploreExploit возвращает средний выигрыш (или проигрыш, если значение отрицательное) на переключение после nPulls случайных событий. Поэтому суммарный выигрыш за сеанс равен количеству переключений, умноженному на средний выигрыш для одного переключения. Альтернативный вариант для ExploreExploit — возврат суммарного выигрыша вместо среднего.

Потери вычисляются так:

double avgBase = machines[2].mean;
double totBase = avgBase * nPulls;
double regret = totBase - totPay;

Переменная avgBase — это средний выигрыш на переключение на лучшем автомате: machine[2] = 0.1 единиц. Поэтому совокупный средний ожидаемый выигрыш за два переключения равен 20 * 0.10 = 2.0 единицы.

Генерация гауссовых случайных значений

Как я упоминал, каждый автомат в демонстрационной программе выплачивает некоторый выигрыш, подчиняясь распределению Гаусса (также называемому нормальным или колоколообразным). Например, machine[0] дает средний выигрыш 0.0 со среднеквадратичным отклонением (standard deviation, sd) в 1.0 единиц. Используя код из демонстрации, которая генерирует гауссовы значения, я написал короткую программу для создания 100 случайных выигрышей на первом автомате — machine[0]. Результаты показаны на рис. 3.

 

100 случайных гауссовых значений
Рис. 3. 100 случайных гауссовых значений

100 Random Payouts mean = 0.0 sd = 1.0 100 случайных выигрышей, средний = 0.0, sd = 1.0
Frequency Частота

 

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

Существует несколько алгоритмов, которые можно использовать для генерации нормально распределяемых случайных значений с указанными средним выигрышем и среднеквадратичным отклонением. Я предпочитаю алгоритм Бокса–Мюллера (Box-Muller algorithm). Этот алгоритм сначала генерирует равномерно распределенные значения (вроде тех, которые создавал .NET-класс Math.Random), а затем использует весьма хитроумный математический аппарат для преобразования равномерно распределенных значений в нормально распределенные. У алгоритма Бокса–Мюллера есть несколько вариаций. Демонстрационная программа использует вариацию, которая менее эффективна по сравнению с другими вариациями, но очень проста.

В демонстрационной программе класс Gaussian определен внутри класса Machine. В Microsoft .NET Framework вложенный определения классов в основном предлагаются для удобства в случаях, где вложенный класс является вспомогательным и используется внешним классом, содержащим его. Если вы переносите этот демонстрационный код в язык, не относящийся к .NET, я советую переработать класс Gaussian в автономный. Класс Gaussian имеет единственный конструктор, который принимает средний выигрыш, среднеквадратичное отклонение выигрыша и начальное значение для нижележащего генератора равномерно распределяемых случайных чисел.

Класс Machine

Этот класс определен в демонстрации очень простым образом. В нем три поля:

public class Machine
{
  public double mean; // средний выигрыш на переключение
  public double sd;   // разброс вокруг среднего
  private Gaussian g; // генератор выигрышей
...

Класс Machine является главным образом оболочкой генератора гауссовых случайных чисел. Проектировать его можно самыми разными способами, но, в целом, я предпочитаю сохранять определения своих классов предельно простыми. Вместо использования среднеквадратичного отклонения, как здесь, в некоторых научных статьях применяется математическая дисперсия (mathematical variance). Среднеквадратичное отклонение и дисперсия эквивалентны, поскольку дисперсия — это просто среднеквадратичное отклонение, возведенное в квадрат.

В классе Machine есть единственный конструктор, который настраивает гауссов генератор:

public Machine(double mean, double sd, int seed)
{
  this.mean = mean;
  this.sd = sd;
  this.g = new Gaussian(mean, sd, seed);
}

Класс Machine содержит один открытый метод, возвращающий случайный выигрыш с нормальным распределением:

public double Pay()
{
  return this.g.Next();
}

Альтернатива возврату выигрыша с нормальным распределением — возврат значения с равномерным распределением между указанными конечными точками. Например, можно было бы возвращать случайное значение между –2.0 и + 3.0, где средний выигрыш был бы (–2 + 3) / 2 = +0.5 единиц.

Реализация алгоритма «исследуй-используй»

Определение метода ExploreExploit начинается с:

static double ExploreExploit(Machine[] machines,
  double pctExplore, int nPulls)
{
  int nMachines = machines.Length;
  Random r = new Random(2); // какой автомат
  double[] explorePays = new double[nMachines];
  double totPay = 0.0;
...

Объект Random с именем r используется для случайного выбора автомата на этапе исследования. Массив explorePays хранит накопленные выигрыши для каждого автомата на этом же этапе. Но на этапе использования достаточно единственной переменной, totPay, для хранения накопленного выигрыша, поскольку в этом случае автомат только один.

Затем вычисляется количество переключений для этапов исследования и использования:

int nExplore = (int)(nPulls * pctExplore);
int nExploit = nPulls - nExplore;

Было бы ошибкой вычислять количество переключений на этапе исследования, используя член (1.0 – pctExplore) из-за возможного округления в расчетах.

Этап исследования без выражений WriteLine кодируется так:

for (int pull = 0; pull < nExplore; ++pull)
{
  int m = r.Next(0, nMachines);   // выбор автомата
  double pay = machines[m].Pay(); // игра
  explorePays[m] += pay;          // обновление
  totPay += pay;
}

Random.Next(int minVal, int maxVal) возвращает целое число между minVal (включительно) и maxVal (исключительно), так что, если nMachines = 3, r.Next(0, nMachines) возвращает случайное целое число: 0, 1 или 2.

Далее определяется лучший автомат, найденный на этапе исследования, который применяется на этапе использования:

int bestMach = BestIdx(explorePays);
for (int pull = 0; pull < nExploit; ++pull)
{
  double pay = machines[bestMach].Pay();
  totPay += pay; // накопление
}

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

Метод ExploreExploit завершается вычислением и возвратом среднего выигрыша на переключение по всем nPulls играм:

. . .
  return totPay / nPulls;
}

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

Другие алгоритмы

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

Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Миро Дудику (Miro Dudik) и Крику Олинику (Kirk Olynyk).