25 KiB

Raw Permalink Blame History Unescape Escape

Въведение в Укрепващото Обучение и Q-Learning

Скица от Tomomi Imura

Укрепващото обучение включва три важни концепции: агент, състояния и набор от действия за всяко състояние. Изпълнявайки действие в определено състояние, агентът получава награда. Представете си компютърната игра Super Mario. Вие сте Марио, намирате се на ниво в играта, стоите до ръба на скала. Над вас има монета. Вие, като Марио, на определено място в нивото на играта... това е вашето състояние. Ако направите крачка надясно (действие), ще паднете от скалата и ще получите ниска числена оценка. Но ако натиснете бутона за скок, ще спечелите точка и ще останете жив. Това е положителен резултат и трябва да ви донесе положителна числена оценка.

Използвайки укрепващо обучение и симулатор (играта), можете да научите как да играете играта, за да максимизирате наградата, която е да останете живи и да съберете възможно най-много точки.

🎥 Кликнете върху изображението по-горе, за да чуете Дмитрий да обсъжда Укрепващото Обучение

Тест преди лекцията

Предпоставки и Настройка

В този урок ще експериментираме с код на Python. Трябва да можете да изпълните кода от Jupyter Notebook, или на вашия компютър, или в облака.

Можете да отворите ноутбука на урока и да преминете през урока, за да го изградите.

Забележка: Ако отваряте този код от облака, трябва също да изтеглите файла rlboard.py, който се използва в кода на ноутбука. Добавете го в същата директория като ноутбука.

Въведение

В този урок ще изследваме света на Петър и Вълкът, вдъхновен от музикална приказка на руския композитор Сергей Прокофиев. Ще използваме Укрепващо Обучение, за да позволим на Петър да изследва своята среда, да събира вкусни ябълки и да избягва срещи с вълка.

Укрепващото Обучение (RL) е техника за обучение, която ни позволява да научим оптималното поведение на агент в някаква среда, като провеждаме множество експерименти. Агентът в тази среда трябва да има някаква цел, дефинирана чрез функция за награда.

Средата

За простота, нека разгледаме света на Петър като квадратна дъска с размери ширина x височина, като тази:

Всяка клетка на тази дъска може да бъде:

земя, върху която Петър и други същества могат да ходят.
вода, върху която очевидно не можете да ходите.
дърво или трева, място, където можете да си починете.
ябълка, която представлява нещо, което Петър би се радвал да намери, за да се нахрани.
вълк, който е опасен и трябва да се избягва.

Има отделен Python модул, rlboard.py, който съдържа кода за работа с тази среда. Тъй като този код не е важен за разбирането на нашите концепции, ще импортираме модула и ще го използваме, за да създадем примерна дъска (код блок 1):

from rlboard import *

width, height = 8,8
m = Board(width,height)
m.randomize(seed=13)
m.plot()

Този код трябва да отпечата изображение на средата, подобно на горното.

Действия и политика

В нашия пример целта на Петър е да намери ябълка, като избягва вълка и други препятствия. За да направи това, той може просто да се разхожда, докато намери ябълка.

Следователно, на всяка позиция той може да избира между следните действия: нагоре, надолу, наляво и надясно.

Ще дефинираме тези действия като речник и ще ги свържем с двойки от съответните промени в координатите. Например, движението надясно (R) би съответствало на двойка (1,0). (код блок 2):

actions = { "U" : (0,-1), "D" : (0,1), "L" : (-1,0), "R" : (1,0) }
action_idx = { a : i for i,a in enumerate(actions.keys()) }

За да обобщим, стратегията и целта на този сценарий са следните:

Стратегията на нашия агент (Петър) се дефинира чрез така наречената политика. Политиката е функция, която връща действието за всяко дадено състояние. В нашия случай състоянието на проблема се представя чрез дъската, включително текущата позиция на играча.
Целта на укрепващото обучение е в крайна сметка да научим добра политика, която ще ни позволи да решим проблема ефективно. Въпреки това, като базова линия, нека разгледаме най-простата политика, наречена случайна разходка.

Случайна разходка

Нека първо решим проблема, като приложим стратегията за случайна разходка. При случайна разходка ще избираме следващото действие случайно от позволените действия, докато стигнем до ябълката (код блок 3).

Реализирайте случайната разходка с кода по-долу:

def random_policy(m):
    return random.choice(list(actions))

def walk(m,policy,start_position=None):
    n = 0 # number of steps
    # set initial position
    if start_position:
        m.human = start_position 
    else:
        m.random_start()
    while True:
        if m.at() == Board.Cell.apple:
            return n # success!
        if m.at() in [Board.Cell.wolf, Board.Cell.water]:
            return -1 # eaten by wolf or drowned
        while True:
            a = actions[policy(m)]
            new_pos = m.move_pos(m.human,a)
            if m.is_valid(new_pos) and m.at(new_pos)!=Board.Cell.water:
                m.move(a) # do the actual move
                break
        n+=1

walk(m,random_policy)

Извикването на walk трябва да върне дължината на съответния път, която може да варира от едно изпълнение до друго.

Изпълнете експеримента за разходка няколко пъти (например 100) и отпечатайте получените статистики (код блок 4):
```
def print_statistics(policy):
    s,w,n = 0,0,0
    for _ in range(100):
        z = walk(m,policy)
        if z<0:
            w+=1
        else:
            s += z
            n += 1
    print(f"Average path length = {s/n}, eaten by wolf: {w} times")

print_statistics(random_policy)
```
Забележете, че средната дължина на пътя е около 30-40 стъпки, което е доста, като се има предвид, че средното разстояние до най-близката ябълка е около 5-6 стъпки.

Можете също така да видите как изглежда движението на Петър по време на случайната разходка:

Функция за награда

За да направим нашата политика по-интелигентна, трябва да разберем кои ходове са "по-добри" от други. За да направим това, трябва да дефинираме нашата цел.

Целта може да бъде дефинирана чрез функция за награда, която ще връща някаква стойност за всяко състояние. Колкото по-висока е стойността, толкова по-добра е наградата. (код блок 5)

move_reward = -0.1
goal_reward = 10
end_reward = -10

def reward(m,pos=None):
    pos = pos or m.human
    if not m.is_valid(pos):
        return end_reward
    x = m.at(pos)
    if x==Board.Cell.water or x == Board.Cell.wolf:
        return end_reward
    if x==Board.Cell.apple:
        return goal_reward
    return move_reward

Интересното при функциите за награда е, че в повечето случаи получаваме значителна награда само в края на играта. Това означава, че нашият алгоритъм трябва по някакъв начин да запомни "добрите" стъпки, които водят до положителна награда в края, и да увеличи тяхната важност. По същия начин всички ходове, които водят до лоши резултати, трябва да бъдат обезкуражени.

Q-Learning

Алгоритъмът, който ще обсъдим тук, се нарича Q-Learning. В този алгоритъм политиката се дефинира чрез функция (или структура от данни), наречена Q-таблица. Тя записва "доброто" на всяко действие в дадено състояние.

Тя се нарича Q-таблица, защото често е удобно да се представи като таблица или многомерен масив. Тъй като нашата дъска има размери ширина x височина, можем да представим Q-таблицата, използвайки numpy масив с форма ширина x височина x len(actions): (код блок 6)

Q = np.ones((width,height,len(actions)),dtype=np.float)*1.0/len(actions)

Забележете, че инициализираме всички стойности на Q-таблицата с еднаква стойност, в нашия случай - 0.25. Това съответства на политиката за "случайна разходка", защото всички ходове във всяко състояние са еднакво добри. Можем да предадем Q-таблицата на функцията plot, за да визуализираме таблицата на дъската: m.plot(Q).

В центъра на всяка клетка има "стрелка", която показва предпочитаната посока на движение. Тъй като всички посоки са равни, се показва точка.

Сега трябва да изпълним симулацията, да изследваме нашата среда и да научим по-добро разпределение на стойностите в Q-таблицата, което ще ни позволи да намерим пътя до ябълката много по-бързо.

Същност на Q-Learning: Уравнението на Белман

След като започнем да се движим, всяко действие ще има съответна награда, т.е. теоретично можем да изберем следващото действие въз основа на най-високата непосредствена награда. Въпреки това, в повечето състояния ходът няма да постигне нашата цел да стигнем до ябълката, и следователно не можем веднага да решим коя посока е по-добра.

Запомнете, че не непосредственият резултат е важен, а крайният резултат, който ще получим в края на симулацията.

За да отчетем тази забавена награда, трябва да използваме принципите на динамичното програмиране, които ни позволяват да мислим за проблема си рекурсивно.

Да предположим, че сега сме в състояние s, и искаме да преминем към следващото състояние s'. Като направим това, ще получим непосредствената награда r(s,a), дефинирана чрез функцията за награда, плюс някаква бъдеща награда. Ако предположим, че нашата Q-таблица правилно отразява "привлекателността" на всяко действие, тогава в състояние s' ще изберем действие a, което съответства на максималната стойност на Q(s',a'). Така най-добрата възможна бъдеща награда, която можем да получим в състояние s, ще бъде дефинирана като max

Проверка на политиката

Тъй като Q-таблицата показва "привлекателността" на всяко действие във всяко състояние, е доста лесно да я използваме за определяне на ефективната навигация в нашия свят. В най-простия случай можем да изберем действието, съответстващо на най-високата стойност в Q-таблицата: (код блок 9)

def qpolicy_strict(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = list(actions)[np.argmax(v)]
        return a

walk(m,qpolicy_strict)

Ако опитате кода по-горе няколко пъти, може да забележите, че понякога той "забива" и трябва да натиснете бутона STOP в бележника, за да го прекъснете. Това се случва, защото може да има ситуации, когато две състояния "посочват" едно към друго в контекста на оптималната Q-стойност, което води до това, че агентът се движи между тези състояния безкрайно.

🚀Предизвикателство

Задача 1: Модифицирайте функцията walk, за да ограничите максималната дължина на пътя до определен брой стъпки (например 100), и наблюдавайте как кодът по-горе връща тази стойност от време на време.

Задача 2: Модифицирайте функцията walk, така че да не се връща на места, където вече е бил. Това ще предотврати циклирането на walk, но агентът все пак може да се окаже "заклещен" на място, от което не може да избяга.

По-добра навигационна политика би била тази, която използвахме по време на обучението, комбинираща експлоатация и изследване. В тази политика ще избираме всяко действие с определена вероятност, пропорционална на стойностите в Q-таблицата. Тази стратегия може все още да доведе до връщане на агента на позиция, която вече е изследвал, но, както можете да видите от кода по-долу, тя води до много кратък среден път до желаното местоположение (не забравяйте, че print_statistics изпълнява симулацията 100 пъти): (код блок 10)

def qpolicy(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = random.choices(list(actions),weights=v)[0]
        return a

print_statistics(qpolicy)

След изпълнение на този код, трябва да получите много по-малка средна дължина на пътя от преди, в диапазона 3-6.

Изследване на процеса на обучение

Както споменахме, процесът на обучение е баланс между изследване и използване на придобитите знания за структурата на пространството на проблема. Видяхме, че резултатите от обучението (способността да помогнем на агент да намери кратък път до целта) са се подобрили, но също така е интересно да наблюдаваме как се държи средната дължина на пътя по време на процеса на обучение:

Обобщение на наученото:

Средната дължина на пътя се увеличава. Това, което виждаме тук, е, че в началото средната дължина на пътя се увеличава. Вероятно това се дължи на факта, че когато не знаем нищо за средата, сме склонни да се "заклещим" в лоши състояния, като вода или вълк. Докато научаваме повече и започваме да използваме тези знания, можем да изследваме средата за по-дълго, но все още не знаем добре къде са ябълките.
Дължината на пътя намалява, докато научаваме повече. След като научим достатъчно, става по-лесно за агента да постигне целта, и дължината на пътя започва да намалява. Въпреки това, все още сме отворени към изследване, така че често се отклоняваме от най-добрия път и изследваме нови опции, което прави пътя по-дълъг от оптималния.
Дължината се увеличава рязко. Това, което също наблюдаваме на този график, е, че в даден момент дължината се увеличава рязко. Това показва стохастичния характер на процеса и че в даден момент можем да "развалим" коефициентите в Q-таблицата, като ги презапишем с нови стойности. Това идеално трябва да се минимизира чрез намаляване на скоростта на обучение (например, към края на обучението, коригираме стойностите в Q-таблицата само с малка стойност).

Като цяло е важно да запомним, че успехът и качеството на процеса на обучение значително зависят от параметри като скорост на обучение, намаляване на скоростта на обучение и коефициент на дисконтиране. Те често се наричат хиперпараметри, за да се разграничат от параметри, които оптимизираме по време на обучението (например, коефициентите в Q-таблицата). Процесът на намиране на най-добрите стойности за хиперпараметрите се нарича оптимизация на хиперпараметри, и заслужава отделна тема.

Тест след лекцията

Задание

По-реалистичен свят

Отказ от отговорност:
Този документ е преведен с помощта на AI услуга за превод Co-op Translator. Въпреки че се стремим към точност, моля, имайте предвид, че автоматизираните преводи може да съдържат грешки или неточности. Оригиналният документ на неговия роден език трябва да се счита за авторитетен източник. За критична информация се препоръчва професионален човешки превод. Ние не носим отговорност за недоразумения или погрешни интерпретации, произтичащи от използването на този превод.

25 KiB Raw Permalink Blame History Unescape Escape