Введение в Q-Learning

Автор: | 26.12.2021

Введение 
Пример простой программы, демонстрирующей Q-Learning
Вербальная модель Q-Learning
Марковский процесс принятия решений
Формальная модель Q-Learning
Алгоритм обновления Q-value
Выбор гиперпараметров
Введение в Deep Q-Learning
Полезные ссылки

Введение

Среди алгоритмов машинного обучения особое место занимают такие, где алгоритм учится решать поставленную задачу самостоятельно без участия человека, напрямую взаимодействуя со средой в которой он обучается. Такие алгоритмы получили  название —  обучение с подкреплением (Reinforcement Learning, RL). Для реализации RL не нужно собирать базы данных, не нужно производить их классификацию или разметку, достаточно только давать обратный отклик на действия агентов — хороши они были или нет.

Благодаря RL мы все больше приближаемся к глобальному решению задачи создания искусственного интеллекта. В своем новаторском учебнике «Искусственный интеллект: современный подход» авторы Стюарт Рассел и Питер Норвиг дают определение Artificial Intelligence(AI) — это «изучение агентов, которые получают информацию из окружающей среды и выполняют действия».

Среда (Environment) – мир, где приходится выживать Агенту (Agent), который учится действовать и добиваться успеха в этой среде. Чтобы подключить агента к среде, мы предоставляем ему набор действий (Actions), которые он может предпринять. Чтобы подключить среду к агенту, мы постоянно посылаем агенту два сигнала: обновленное состояние (State) и вознаграждение (Reward). Цель обучения — максимизировать вознаграждение, которое получает Агент в результате своих действий.

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

Процесс обучения с подкреплением — это итеративный цикл:

  • Агент получает состояние S0 от Среды
  • Основываясь на этом состоянии, Агент выполняет действие A0
  • Среда дает Агенту некоторую награду R1
  • Среда переходит в новое состояние S1

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

Название Q (от слова quality — подразумевает качество выбора), а метод — Q-Learning.

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

Пример простой программы, демонстрирующей Q-Learning

В программе агент обучается определять траекторию перемещения от стартовой ячейки (S) к целевой (G), минуя blocked ячейку (обозначена на рисунке XXX).

'''  (0,0)(0,1)(0,2)
       ___________
      |   |   |   |
 (0,0)|_S_|___|___|
      |   |   |   |
 (1,0)|___|___|XXX|
      |   |   |   |
 (2,0)|___|___|_G_| 
      Actions - 1:UP
                2:DOWN
                3:RIGHT
                4:LEFT
'''
import random

def game(state,action):
    #Awarding 10 for reaching the goal
    if state[0]==2 and state[1]==1 and action==3:
            return [10,[2,2]]
    # -10 for bumping into the blocked state
    elif state[0]==1 and state[1]==1 and action==3:
            return [-10,[1,1]]
    # -10 for bumping into the blocked state
    elif state[0]==0 and state[1]==2 and action==2:
            return [-10,[0,2]]
    #For all other actions -1 reward
    else:
        if action==1:
            x=state[0]-1
            y=state[1]
            if x<0:
                x=0
            return [-1,[x,y]]
        elif action == 2:
            x=state[0]+1
            y=state[1]
            if x>2:
                x=2
            return [-1,[x,y]]
        elif action ==3:
            x=state[0]
            y=state[1]+1
            if y>2:
                y=2
            return [-1,[x,y]]
        else:
            x=state[0]
            y=state[1]-1
            if y<0:
                y=0
            return [-1,[x,y]]

def main():
    #Set the Learning rate
    alpha=0.2
    epsilon=0.2
    #Set the discount factor
    discount=0.9
    #Create an empty table which will hold the Q-value for each action in every state
    #e.g Qvalue[1][2] stores a list of 4 values corresponding to the 4 actions from state (1,2)
    Qvalue=[[[] for x in range(3)] for y in range(3)] 
    for i in range(3):
       for j in range(3):
        # For terminal state set the Q-values to 0
          if i==2 and j==2:
             Qvalue[i][j][:]= [0,0,0,0]
             #For all other states set the Q-values to random integers
          else:
             Qvalue[i][j][:]= random.sample(range(5), 4)
    print("Qvalues before playing :\n",Qvalue)
    #TRAINING GAMES
    #Set the number of games
    numgames=100
    #print("Action, Next state and Qvalues :")
    for i in range(numgames):
       #Starting with state (0,0)
       state=[0,0]
       #Loop untill terminal state
       while state!=[2,2]:
          #Generate a random number between 0 and 1 
          randomnum= random.uniform(0,1)
          #Choose the best action if the random number is greater than epsilon
          if randomnum>=epsilon:
             lst=Qvalue[state[0]][state[1]]
             action=lst.index(max(lst))+1
          #Else choose an action randomly
          else:
             action=random.randint(1,4)
 
          #Play the game
          #The game method will return the reward and next state
          reward,nextstate = game(state,action)
          #nxtlist stores the Qvalue of the actions from the nextstate
          nxtlist=Qvalue[nextstate[0]][nextstate[1]]
          #currval is the Q-value of the action taken in this step 
          currval=Qvalue[state[0]][state[1]][action-1]
          #Update the Q-value according to the equation
          delta = alpha * (reward + discount*max(nxtlist) - currval)
          Qvalue[state[0]][state[1]][action-1]= currval + delta
          state=nextstate
          #print(state)
          #print(Qvalue)
    print("Change in states during training over a period " ,numgames," games :")
    print("Qvalues after playing ",numgames," games :")
    print("                       Actions")
    print("                UP DOWN RIGHT LEFT")
    for i in range(3):
       for j in range(3):
          print("State (",i,",",j,") :",end="")
          for k in range(4):
             print(round(float(Qvalue[i][j][k]),1),end=" ")
          print(" ")
    print()
    #Playing the game by choosing action with max Qvalue from each state encountered
    print("Playing Game :")
    state=[0,0]
    totalreward=0
    print("State[0,0] --->",end=" ")
    #TESTING GAME
    #Loop untill terminal state
    while state!=[2,2]:
         lst=Qvalue[state[0]][state[1]]
         action=lst.index(max(lst))+1
         reward,nxtstate=game(state,action)
         totalreward=totalreward+reward
         state=nxtstate
         print("State[",state[0],",",state[1],"] --->",end=" ")
 
    print("Total reward = ",totalreward)

if __name__=='__main__':
 main()

Подробное описание программы см. в первоисточнике.

Всего в игре задействовано 9 ячеек. Положение каждой ячейки определяется состоянием (State[x,y]). Переход Агента из текущей ячейки в одну из соседних с ней возможен 4-я actions (1-UP, 2-DOWN, 3-RIGHT, 4-LEFT).

В программе Агент сначала учится находить правильное действие на обучающих играх  (TRAINING GAMES). После обучения выполняется тестирование (TESTING GAME). Отличие между этими играми в том, как агент выбирает действие (направление движения).

В TESTING GAME направление для перехода к новому состоянию State[x,y] выбирается по наибольшему значению ценности действия (Qvalue), которое определяется в результате обучения.

В TRAINING GAMES перед первой игрой Qvalue определяется по набору случайных чисел (Qvalue[i][j][:]= random.sample(range(5), 4)). В последующих играх направление выбирается как по наибольшему значению Qvalue так и по одному из 4-х случайных чисел (action=random.randint(1,4)) — это зависит от соотношения (randomnum>=epsilon) между случайным числом (randomnum= random.uniform(0,1)) и заданным параметром (epsilon=0.2).

После окончания первой обучающей игры (while state!=[2,2]:) начинается следующая игра и т.д. При этом, значения Qvalue, полученные в предыдущей игре, передаются в следующую игру. Как видим (см. рисунок ниже) в первой игре движение агента к цели происходит хаотично. С каждой новой игрой поведение агента улучшается.

В тестируемой игре после достаточного обучения в результате указанных на рисунке переходов  агент получает вознаграждение Total reward = 3*(-1) +10=7.

Если агент обучен еще недостаточно, то возможно зависание программы. Например, после 5 обучающих игр (numgames=5) часто при тестировании происходят аварийные ситуации, когда агент выбирает неправильное направление перемещения и зависает на нем (повторяет его бесконечно). Это обусловлено тем, что при тестировании Qvalue уже не изменяется как при обучении, поэтому нельзя уменьшить ценность неправильного действия. И если Qvalue для каких-то ячеек при обучении было подобрано неверно (агент не доучился), то на них происходит зацикливание процесса:

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

После 6000 обучающих игр достигнута стабильность в выборе путей достижения цели, числовые значения (Qvalues) для каждого из возможных вариантов перемещения агента к цели почти одинаковые. Например, Qvalue=4.6 определяет перемещение из ячейки (0,0) в направлениях как DOWN так и RIGHT. Выбор обуславливается лишь различием в сотых и тысячных значений Qvalue.

Ниже на примере этой программы отражены теоретические основы Q-Learning

Вербальная модель Q-Learning

В конечном итоге траектория движения к цели предопределяется ценностью (Qvalue) каждого действия Агента в его конкретном положении (состоянии). Т.е., Агент перемещается в том направлении, значение которого наиболее ценно. Каким образом определяется Qvalue?

Изначально  Qvalue для всего множества состояний определяется случайным образом. Затем, в процессе обучения ценность каждого действия (направления) увеличивается либо уменьшается на какую-то величину (delta), определяя оптимальные для решения задачи значения  Qvalue. Каким образом определяется приращение для Qvalue?

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

В состоянии (2,1) приращение для Qvalue может быть определено однозначно (RIGHT) — по максимальной награде (+10). В других состояниях пока возможны только случайные действия. Но, на каком-то этапе обучения в состояниях (2,0) и (1, 1) Qvalue для направлений RIGHT и DOWN можно увеличить по признаку, что у их соседа (2,1) одно из направлений уже получило высокую оценку. После того, как было увеличено Qvalue в этих состояниях, появляются основания увеличить Qvalue для действий из соседних с ними состояний.

Математическая основа для Q-Learning  — Марковский процесс принятия решений (Markov Decision Process, MDP), уравнение Беллмана,  и другие аспекты.

Марковский процесс принятия решений

В типичной проблеме обучения с подкреплением Агент хаотично блуждает.

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

Существуют хорошо известные семейства случайных процессов. Каждое из этих отдельных случаев имеет определённые свойства, позволяющие нам лучше исследовать и понимать их. Одно из свойств, сильно упрощающее исследование случайного процесса — это «марковское свойство». Марковское свойство обозначает, что если мы знаем текущее состояние в заданный момент времени, то нам не нужна никакая дополнительная информация для будущего, собираемая из прошлого. Интуитивно это означает, что наше текущее состояние уже содержит информацию о прошлых состояниях:

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

Случайный процесс с марковским свойством называется Марковским процессом принятия решений.

Марковский процесс Markov Decision Process (MDP) — это случайный процесс без использования памяти, то есть последовательность случайных состояний S[1],S[2],….S[n] с марковским свойством. Динамика MDP может быть полностью определена с использованием матрицы состояний (S) и вероятности перехода (P).

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

Формальная модель Q-обучения

Обучение с подкреплением в основном состоит из двух типов сред:

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

Основная цель в решаемой задаче —  подобрать оптимальную цепочку действий, обеспечивающей максимальное вознаграждение на пути к цели. В каждом состоянии агенту предоставляется набор действий для перехода в другое состояние (1-UP, 2-DOWN, 3-RIGHT, 4-LEFT), которые оцениваются величиной Qvalue. Агент выбирает действие с максимальной величиной Qvalue . При этом происходит переоценка Qvalue выбранного действия с учетом следующей за ним цепочки действий из других состояний. Qvalue переоценивается по алгоритму в основе которого лежит Bellman уравнение.

Уравнение Беллмана для детерминированных сред

gamma — коэффициент дисконтирования, уменьшающий вознаграждение с течением времени

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

Дисконтирование – это определение сегодняшней стоимости будущей денежной суммы. Если вы хотите выяснить, сколько будет стоить сегодня сумма денег, которую вы или получите, или планируете потратить в будущем, то вам надо продисконтировать (уменьшить) эту будущую сумму по заданной ставке процента. Эта ставка называется «ставкой дисконтирования».

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

Уравнение Беллмана для недетерминированных сред

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

Рекурсивная формула переоценки Qvalue для детерминированных сред

Формула переоценки Qvalue для недетерминированных сред

Значение временной разницы TD может не быть равной нулю из-за случайности, существующей в недетерминированной среде

Теперь, когда у нас есть временная разница, вот как мы ее используем при переоценке Qvalue:

alpha -скорость обучения

Формулу можно также записать в виде:

Это элегантное уравнение полезно благодаря своему рекурсивному характеру, что позволяет вознаграждениям из будущих состояний распространяться на предыдущие состояния. Нет необходимости знать, каковы истинные значения Q, когда мы начинаем. Поскольку алгоритм обновления Qvalue рекурсивен, мы можем что-то угадать, и в конечном итоге Q сойдется к реальным значениям.

Алгоритм обновления Qvalue

В рассматриваемом примере программы Qvalue обновляется на каждом шаге перехода агента из одной ячейки (state) в другую (nextstate) в соответствии с установленными вознаграждениями (reward= 10, -10, -1), скоростью обучения alpha=0.2,  коэффициентом дисконтирования discount=0.9 и параметром epsilon=0.2, который вносит случайность в процесс выбора действия.

 #Generate a random number between 0 and 1 
 randomnum= random.uniform(0,1)
 if randomnum>=epsilon:
    lst=Qvalue[state[0]][state[1]]
    action=lst.index(max(lst))+1
 #Else choose an action randomly
 else:
    action=random.randint(1,4)
reward,nextstate = game(state,action)
#nxtlist stores the Qvalue of the actions from the nextstate
nxtlist=Qvalue[nextstate[0]][nextstate[1]]
#currval is the Q-value of the action taken in this step 
currval=Qvalue[state[0]][state[1]][action-1]
#Update the Q-value according to the equation
delta = alpha * (reward + discount*max(nxtlist) - currval)
Qvalue[state[0]][state[1]][action-1]= currval + delta

На нижнем рисунке продемонстрировано, как меняется Qvalue и совершаются переходы из одного состояния в другое согласно формулы:

На 1-м шаге выбирается действие 1 (UP) по максимальному значению Qvalue=4 для состояния (0,0) . При этом  агент остается в исходном состоянии (0,0), а ценность этого действия уменьшается с Qvalue =4 до

 Qvalue=4+0.2*(-1+0.9*4-4)=3.72

На 2-м шаге уже случайным образом (согласно условия randomnum<epsilon) выбирается действие 2(DOWN). При этом  агент переходит в состояние состояние (1,0). Ценность этого действия увеличивается с Qvalue=1 до

Qvalue=1+0.2*(-1+0.9*4-1) =1.32

В состоянии (1,0) max(Qvalue)=4

После этого игра продолжается из состояния (1,0). Здесь выбирается действие 3 (RIGHT) по максимальному значению Qvalue=4 для этого состояния.  При этом  агент переходит в состояние (1,1). Ценность этого действия уменьшается с Qvalue=4 до

Qvalue=4+0.2*(-1+0.9*4-4)=3.72

В состоянии (1,1) max(Qvalue)=4

Из состояния  (1,1) выбирается действие 1 (UP) по максимальному значению Qvalue=4 для этого состояния.  При этом  агент переходит в состояние (0,1). Ценность этого действия уменьшается с Qvalue=4 до

Qvalue=4+0.2*(-1+0.9*4-4)=3.72

Из состояния  (0,1) выбирается действие 1 (DOWN) по максимальному значению Qvalue=4 для этого состояния.  При этом  агент возвращается в состояние (1,1). Ценность этого действия уменьшается с Qvalue=4 до

Qvalue=4+0.2*(-1+0.9*3.72-4)=3.6696

В состоянии (1,1) на этот момент времени было max(Qvalue)=3.72

Далее логику изменения Qvalue можете проследить самостоятельно.

Выбор гиперпараметров

Влияние фактора numgames (Количество игр) на результат было исследовано выше.

Скорость обучения alpha определяет, в какой степени вновь полученная информация превосходит старую. Коэффициент alpha=0 заставляет агента ничего не узнавать (используя исключительно предшествующие знания), в то время как alpha=1 заставляет агента учитывать только самую последнюю информацию (игнорируя предшествующие знания для изучения возможностей).

Коэффициент дисконтирования discount определяет важность будущих вознаграждений. Фактор, равный 0, сделает агента «близоруким» (или недальновидным), учитывая только текущие вознаграждения, т. е. Rt (в правиле обновления), в то время как коэффициент, приближающийся к 1, заставит его стремиться к долгосрочному высокому вознаграждению. Если коэффициент дисконтирования равен или превышает 1, значения действий могут расходиться. При γ = 1, без конечного состояния или если агент никогда его не достигает, все истории окружения становятся бесконечно длинными, а полезности с дополнительными недисконтированными вознаграждениями вообще становятся бесконечными.

Эпсилон. В программе действие с максимальным значением Q с выбирается вероятностью (1- epsilon), а случайное действие — с вероятностью epsilon. Когда значение epsilon слишком мало, то с малой вероятностью алгоритм выбирает случайные действия (исследует). При этом он большую часть времени использует наилучшие действия (эксплуатирует). Если установлено высокое значение epsilon, агент будет исследовать больше, а эксплуатировать меньше.

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

Полезные ссылки:

 

Автор: Николай Свирневский