Мягкий подход для разработчиков к расшифровке математической формулы обучения с подкреплением

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

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

Все сводится к тому, чтобы задать вопрос: чего стоит быть в состоянии S?
Чтобы быть более конкретным, представьте, что вы находитесь в телешоу, и, расположившись напротив двух дверей, у одной есть 5000 $ за ним, а в другом 1000 $, и вам предлагается выбрать одну дверь, которую нужно открыть.

Вы понятия не имеете, что есть что, поэтому у вас есть равные шансы открыть любой из них. Возникает вопрос, чего стоит сниматься в этом телешоу?
Ответ довольно прост. В худшем случае он стоит 1000 $ (потому что вы можете выиграть минимум 1000 $), в лучшем случае он стоит 5000 $ (потому что вы можете выиграть максимум 5000 $). Чтобы получить только одно значение, мы вычисляем среднее значение, которое будет 3000 $.

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

Давайте немного изменим гипотезу. Вам говорят, что дверь слева содержит 5000 долларов, а правая - 1000 долларов, но чтобы открыть любую из них, вам нужно ударить по замку мячом, и есть 20% шанс попасть в замок левой двери и 80% шанс попасть в замок правой двери.

В чем будет ценность такой ситуации?

Это будет будущая награда, умноженная на вероятность получить каждую из них, так что:
.2 * 5000 + .8 * 1000 = 1800 $.

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

Необходимость в коэффициенте скидки (γ) возникает из-за того, что вознаграждение, которое вы получите в далеком будущем, менее ценно, чем вознаграждение, которое вы получите на следующем этапе, поэтому оно будет со скидкой на количество шагов, необходимых для его достижения, например: γ * γ *…. * γ * r, где число умножений γ равно числу шагов, чтобы получить награду.

Математические подробности можно найти в статье Математика, лежащая в основе обучения с подкреплением, простой способ.

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

Вы можете видеть, что состояние S имеет 3 возможных действия, каждое из которых приводит к одному или нескольким состояниям с разными вероятностями и разными наградами. Стоит отметить, что состояние S4 недостижимо из S, но S1 доступно, если предпринято действие a1 и приведет к 2 возможным наградам. Состояние S2 доступно из S, если были выполнены действия a2 или a3. На самом деле a2 обязательно достигнет S2, а a3 может достичь S2 или S3 с разными вероятностями.

Значение V (s) состояния s будет вероятностью выполнения действия a, умноженное на вероятность достижения состояния s ' , умноженное на вероятность получения вознаграждения r, умноженное на член (r + 𝛄V (s ')).
Но поскольку на каждом этапе у нас может быть несколько варианты, означающие несколько действий на выбор, что приводит к нескольким возможным состояниям s ' и нескольким возможным вознаграждениям r . Нам нужно суммировать все эти разные варианты.

Исходную формулу можно переписать следующим образом.

Перевести в код

Как эта формула переводится в код, довольно просто.
Каждая сумма (Σ) преобразуется в цикл, как показано на следующем рисунке.

То, что показывает код, может быть странным для разработчика. Он перебирает все действия в наборе действий A и все состояния в наборе состояний S, а также все награды в наборе вознаграждений R.
Однако мы знаем, что бывают случаи, когда не все действия доступны в все состояния, а не все состояния, достижимы из текущего состояния, и, конечно же, не все типы вознаграждений доступны для каждого действия и каждого состояния.
Таким образом, перебор всех этих наборов - просто пустая трата усилий и времени .
Есть способы оптимизировать код для повышения производительности.

Оптимизация

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

Например, не весь набор действий присутствует во всех состояниях, поэтому вместо того, чтобы перебирать A, мы выполняем его над действиями, доступными в этом состоянии, такими как state.getAvailableActions ().
Аналогично, вместо весь набор состояний S, мы перебираем состояния, достижимые из текущего, state.getAccessibleStates (), и вместо всех вознаграждений R мы перебираем возможные вознаграждения, которые связаны с текущим состоянием и выбранным действием, getRewards (state , а).

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

interface IState {
 
// returns list of states accessible from the current state
function getAccessibleStates() 
// returns list of actions that can be performed in current state
function getAvailableActions()
  
// return probability of taking action 'a' in the current state
function getActionProbability(IAction a)
// returns the probability of arriving at state s' when performing
// action a
function getStateProbability(IState s', IAction a)
// get value of the state
function getValue()
// set value to the state
function setValue(double v)
}

Класс R представляет служебный класс, который возвращает вознаграждение с учетом состояния s и действия a. Функция getReward (s, a) возвращает только одно вознаграждение, тогда как getPossibleRewards (s, a) возвращает список вознаграждений.
Функция getRewardProbability (r, s, a) возвращает вероятность получения вознаграждения r в состоянии s и выполняет действие a.

Во многих случаях система вознаграждений проста, то есть есть только одна награда за состояние и действие. Итак, getReward (s, a) и getPossibleRewards (s, a) возвращают одинаковую награду, а getRewardProbability (r, s, a) возвращает 1.

class R {
// returns the reward when at state s and performing action a static static function getReward(IState s, IAction a)
// returns list of rewards when at state s and performing action a
static function getPossibleRewards(IState s, IAction a)
// get the probability of getting reward r when at state s 
// and performing action a
static function getRewardProbability(IReward r, IState s, IAction a)
}

Функция computeStateValue (s) вычисляет значение состояния s в самом общем случае, когда мы предполагаем, что система вознаграждения может быть непростой и может быть несколько возможных вознаграждений для та же пара состояние / действие.

function computeStateValue(IState s){
 sum_s = 0
 
 for( a in ){
  sum_s' = 0
  
  for(s' in s.getAccessibleStates()){
   sum_r = 0
   
   for(r in R.getPossibleRewards(s, a)){
    sum_r += R.getRewardProbability(r, s, a) * (r + gamma 
             * s.getValue())
   }
  
   sum_s' += s.getStateProbability(s', a) * sum_r
  }
  
  sum_s += s.getActionProbability(a) * sum_s'
 }
 
 return sum_s
}

Функция computeStateValueSinpleReward (s) вычисляет значение состояния s с предположением, что система вознаграждения проста. Таким образом, нет необходимости перебирать возможные награды, мы просто вызываем R.getReward (s, a), и вероятность его получения равна 1.

function computeStateValueSinpleReward(IState s){
 sum_s = 0
 
 for( a in s.getAvailableActions()){
  sum_s' = 0
  
  for(s' in s.getAccessibleStates()){
   sum_s' += s.getStateProbability(s', a) * (R.getReward(s, a) 
             + gamma * s.getValue())
  }
  sum_s += s.getActionProbability(a) * sum_s'
 }
 
 return sum_s
}

Нетрудно заметить, что приведенный выше код касается вычисления одного состояния. Чтобы вычислить значения всех состояний, мы перебираем весь набор состояний S, как показано в функции псевдокода computeValueForAllStates ()

function computeValueForAllStates(){
 for( s in S){
  v = computeStateValue(s)
  s.setValue(v)
 }
}

Заключение

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

Статьи по Теме