Мягкий подход для разработчиков к расшифровке математической формулы обучения с подкреплением
Если вы разработчик, не обладающий достаточными знаниями в математике, возможно, вам сложно усвоить базовую формулу обучения с подкреплением.
Понимание этого уравнения может быть сложной задачей для людей с недостаточным математическим образованием. Однако, если не считать загадочных символов, это не так уж и сложно понять.
Все сводится к тому, чтобы задать вопрос: чего стоит быть в состоянии 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) } }
Заключение
Реализация формулы проста. Однако самого по себе этого недостаточно, потому что многие параметры в реальной жизни неизвестны. По этой причине существует множество других методов, которые можно использовать для оценки каждого компонента этой формулы.
Статьи по Теме
- Простая математика, лежащая в основе обучения с подкреплением
- Политика обучения с подкреплением для разработчиков
- Q vs V в обучении с подкреплением, простой способ
- Простая математика, лежащая в основе обучения с подкреплением
- Простое динамическое программирование в обучении с подкреплением
- Монте-Карло в обучении с подкреплением, легкий путь
- TD в обучении с подкреплением, легкий путь