Reinforcement learning

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

Элементы обучения с подкреплением:

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

В простейшем случае (игра крестики-нолики) мы подготавливаем таблицу чисел, по одному для каждого возможного состояния игры. Каждое число - это оценка вероятности выиграть, начав с этого состояния. Это ценность состояния, а вся таблица - обученная функция ценности. Мы играем много игр с противником. Для выбора хода мы рассматриваем состояния, котоыре получаются в результате каждого возможного хода и оцениваем их ценности по таблице. В основном мы выбираем ход жадно (с наивысшей ценностью), но иногда мы делаем случайный ход (разведочный ход). В процессе игры мы изменяем ценность состояний, в которых оказались. Для этого мы переносим ценность состояний после каждого жадного хода в состояние до этого хода - текущая ценность предыдущего состояния обновляется, так чтобы стать ближе к ценности следующего состояния. Если обозначить \(S_t\) состояние до жадного хода, \(S_{t+1}\) после, то обновление оценки \(V(S_t)\) будет выглядеть так:

\[V(S_t) \leftarrow (S_t) + \alpha[V(S_{t+1}) - V(S_t)]\]

где \(\alpha\) - небольшой положительный коэффициент, называемый параметром размера шага, который влияет на скорость обучения. Это правило обучения - пример обучения на оснвое [temporal-difference].

Применение [evolution-methods] к данной задаче означало бы, что мы должны провести прямой поиск в пространстве стратегий, чтобы найти стратегию с высокой вероятностью выигрыша. Для каждой стратегии необходимо было бы получить оценку вероятности выигрыша, сыграв несколько партий с противником, что указывало на то, какую стратегию использовать в следующем шаге. Типичный эволюционный метод - “восхождение на гору” в пространстве стратегий, последовательно генерируя и оценивая стратегии, пытаясь добиться улучшения. Если бы мы использовали генетический алгоритм, то хранили бы и оценивали популяцию стратегий.

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

Методы

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

К табличным методам можно отнести:

  • [multi-armed-bandit] многорукие бандиты
  • [mppr] конечные марковские процессы принятия решения
  • [notes/dynamic-programming] динамическое программирование
  • [monte-carlo] методы Монте-Карло
  • [temporal-difference] методы, основанные на временных различиях